To see the other types of publications on this topic, follow the link: Channel routing.
Dissertations / Theses on the topic 'Channel routing'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Channel routing.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Domke, Jens. "Routing on the Channel Dependency Graph:." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-225902.
Full textAbstract:
In the pursuit for ever-increasing compute power, and with Moore's law slowly coming to an end, high-performance computing started to scale-out to larger systems. Alongside the increasing system size, the interconnection network is growing to accommodate and connect tens of thousands of compute nodes. These networks have a large influence on total cost, application performance, energy consumption, and overall system efficiency of the supercomputer. Unfortunately, state-of-the-art routing algorithms, which define the packet paths through the network, do not utilize this important resource efficiently. Topology-aware routing algorithms become increasingly inapplicable, due to irregular topologies, which either are irregular by design, or most often a result of hardware failures. Exchanging faulty network components potentially requires whole system downtime further increasing the cost of the failure. This management approach becomes more and more impractical due to the scale of today's networks and the accompanying steady decrease of the mean time between failures. Alternative methods of operating and maintaining these high-performance interconnects, both in terms of hardware- and software-management, are necessary to mitigate negative effects experienced by scientific applications executed on the supercomputer. However, existing topology-agnostic routing algorithms either suffer from poor load balancing or are not bounded in the number of virtual channels needed to resolve deadlocks in the routing tables.
Using the fail-in-place strategy, a well-established method for storage systems to repair only critical component failures, is a feasible solution for current and future HPC interconnects as well as other large-scale installations such as data center networks. Although, an appropriate combination of topology and routing algorithm is required to minimize the throughput degradation for the entire system. This thesis contributes a network simulation toolchain to facilitate the process of finding a suitable combination, either during system design or while it is in operation. On top of this foundation, a key contribution is a novel scheduling-aware routing, which reduces fault-induced throughput degradation while improving overall network utilization. The scheduling-aware routing performs frequent property preserving routing updates to optimize the path balancing for simultaneously running batch jobs. The increased deployment of lossless interconnection networks, in conjunction with fail-in-place modes of operation and topology-agnostic, scheduling-aware routing algorithms, necessitates new solutions to solve the routing-deadlock problem. Therefore, this thesis further advances the state-of-the-art by introducing a novel concept of routing on the channel dependency graph, which allows the design of an universally applicable destination-based routing capable of optimizing the path balancing without exceeding a given number of virtual channels, which are a common hardware limitation. This disruptive innovation enables implicit deadlock-avoidance during path calculation, instead of solving both problems separately as all previous solutions.
2
Lavén, Andreas. "Multi-Channel Anypath Routing for Multi-Channel Wireless Mesh Networks." Thesis, Karlstad University, Faculty of Economic Sciences, Communication and IT, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:kau:diva-5370.
Full textAbstract:
Increasing capacity in wireless mesh networks can be achieved by using multiple channels and radios. By using different channels, two nodes can send packets at the same time without interfering with each other. To utilize diversity of available frequency, typically cards use channel-switching, which implies significant overhead in terms of delay. Assignment of which channels to use needs to be coupled with routing decisions as routing influences topology and traffic demands, which in turn impacts the channel assignment.
Routing algorithms for wireless mesh networks differ from routing algorithms that are used in wired networks. In wired networks, the number of hops is usually the only metric that matters. Wireless networks, on the other hand, must consider the quality of different links, as it is possible for a path with a larger amount of hops to be better than a path with fewer hops.
Typical routing protocols for wireless mesh networks such as Optimized Link State Routing (OLSR) use a single path to send packets from source to destination. This path is precomputed based on link state information received through control packets. The consideration of more information than hop-count in the routing process has shown to be beneficial as for example link quality and physical layer data rate determines the quality of the end-to-end path. In multi-channel mesh networks, also channel switching overhead and channel diversity need to be considered as a routing metric. However, a major drawback of current approaches is that a path is precomputed and used as long as the path is available and shows a good enough metric. As a result, short term variations on link quality or channel switching are not considered.
In this thesis, a new routing protocol is designed that provides a set of alternative forwarding candidates for each destination. To minimize delay (from both transmission and channel switching), a forwarding mechanism is developed to select one of the available forwarding candidates for each packet. The implementation was tested on an ARM based multi-radio platform, of which the results show that in a simple evaluation scenario the average delay was reduced by 22 % when compared to single path routing.
3
Chiu, Hon-sun, and 邵漢新. "Channel assignment and routing in multi-channel multi-interface wireless networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2009. http://hub.hku.hk/bib/B42182050.
Full text
4
Chiu, Hon-sun. "Channel assignment and routing in multi-channel multi-interface wireless networks." Click to view the E-thesis via HKUTO, 2009. http://sunzi.lib.hku.hk/hkuto/record/B42182050.
Full text
5
McKay, Kristi Ann. "Hydraulic flood routing with minimal channel data." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp04/mq21190.pdf.
Full text
6
Islam, Taj-ul. "Channel routing : efficient solutions using neural networks /." Online version of thesis, 1993. http://hdl.handle.net/1850/11154.
Full text
7
Jackson, Crystal A. "Channel-access and routing protocols to utilize multiple heterogeneous channels for ad hoc networks." Connect to this title online, 2008. http://etd.lib.clemson.edu/documents/1219849356/.
Full text
8
Roderick, Michael J. "Channel and switchbox routing using a greedy based channel algorithm with outward scanning technique." Thesis, Monterey, California. Naval Postgraduate School, 1988. http://hdl.handle.net/10945/22939.
Full text
9
袁志勤 and Chi-kan Yuen. "A double-track greedy algorithm for VLSI channel routing." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1997. http://hub.hku.hk/bib/B31220241.
Full text
10
Yuen, Chi-kan. "A double-track greedy algorithm for VLSI channel routing /." Hong Kong : University of Hong Kong, 1997. http://sunzi.lib.hku.hk/hkuto/record.jsp?B19656373.
Full text
11
He, Jingyi. "Routing and channel assignment in optical and wireless networks /." View abstract or full-text, 2004. http://library.ust.hk/cgi/db/thesis.pl?ELEC%202004%20HE.
Full text
12
Shah, Ibrar Ali. "Channel assignment and routing in cooperative and competitive wireless mesh networks." Thesis, Brunel University, 2012. http://bura.brunel.ac.uk/handle/2438/6568.
Full textAbstract:
In this thesis, the channel assignment and routing problems have been investigated for both cooperative and competitive Wireless Mesh networks (WMNs). A dynamic and distributed channel assignment scheme has been proposed which generates the network topologies ensuring less interference and better connectivity. The proposed channel assignment scheme is capable of detecting the node failures and mobility in an efficient manner. The channel monitoring module precisely records the quality of bi-directional links in terms of link delays. In addition, a Quality of Service based Multi-Radio Ad-hoc On Demand Distance Vector (QMR-AODV) routing protocol has been devised. QMR-AODV is multi-radio compatible and provides delay guarantees on end-to-end paths. The inherited problem of AODV’s network wide flooding has been solved by selectively forwarding the routing queries on specified interfaces. The QoS based delay routing metric, combined with the selective route request forwarding, reduces the routing overhead from 24% up to 36% and produces 40.4% to 55.89% less network delays for traffic profiles of 10 to 60 flows, respectively. A distributed channel assignment scheme has been proposed for competitive WMNs, where the problem has been investigated by applying the concepts from non-cooperative bargaining Game Theory in two stages. In the first stage of the game, individual nodes of the non-cooperative setup is considered as the unit of analysis, where sufficient and necessary conditions for the existence of Nash Equilibrium (NE) and Negotiation-Proof Nash Equilibrium (N-PNE) have been derived. A distributed algorithm has been presented with perfect information available to the nodes of the network. In the presence of perfect information, each node has the knowledge of interference experience by the channels in its collision domain. The game converges to N-PNE in finite time and the average fairness achieved by all the nodes is greater than 0.79 (79%) as measured through Jain Fairness Index. Since N-PNE and NE are not always a system optimal solutions when considered from the end-nodes prospective, the model is further extended to incorporate non-cooperative end-users bargaining between two end user’s Mesh Access Points (MAPs), where an increase of 10% to 27% in end-to-end throughput is achieved. Furthermore, a non-cooperative game theoretical model is proposed for end-users flow routing in a multi-radio multi-channel WMNs. The end user nodes are selfish and compete for the channel resources across the WMNs backbone, aiming to maximize their own benefit without taking care for the overall system optimization. The end-to-end throughputs achieved by the flows of an end node and interference experienced across the WMNs backbone are considered as the performance parameters in the utility function. Theoretical foundation has been drawn based on the concepts from the Game Theory and necessary conditions for the existence of NE have been extensively derived. A distributed algorithm running on each end node with imperfect information has been implemented to assess the usefulness of the proposed mechanism. The analytical results have proven that a pure strategy Nash Equilibrium exists with the proposed necessary conditions in a game of imperfect information. Based on a distributed algorithm, the game converges to a stable state in finite time. The proposed game theoretical model provides a more reasonable solution with a standard deviation of 2.19Mbps as compared to 3.74Mbps of the random flow routing. Finally, the Price of Anarchy (PoA) of the system is close to one which shows the efficiency of the proposed scheme.
13
Hurtig, Patrik. "On Routing Two-Point Nets Across a Three-Dimensional Channel." Thesis, Linköping University, Department of Electrical Engineering, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-2948.
Full textAbstract:
Routing techniques for plain ’flat’ microchips have been developed extensively and will soon reach its limitations. One natural step would be to develop chips which are manufactured in a more cubic type of volume, as oppose to the classical flat design.
This thesis proposes a method for routing two-point nets across a three- dimensional channel. The height required by this algorithm is of the order O(n (3/2)), where n is the number of terminals on a square top-layer with the side 2 (n(1/2)).
The algorithm proposed here is based on"On Routing Two-Point Nets Across a Channel", by Ron Y. Pinter [9], and the concepts from this paper are explainedin this thesis to familiarise the reader these.
It is also shown that the proposed algorithm is more effective in its volume than the two-dimensional counterpart. The algorithm here is of the order O(n(3/2)) with the two-dimensional algorithm of the order O(n2).
14
Ahuja, Sandeep Kour. "ALGORITHMS FOR ROUTING AND CHANNEL ASSIGNMENT IN WIRELESS INFRASTRUCTURE NETWORKS." Diss., The University of Arizona, 2010. http://hdl.handle.net/10150/195190.
Full textAbstract:
Wireless communication is a rapidly growing segment of the communication industry, with the potential to provide low-cost, high-quality, and high-speed information exchange between portable devices. To harvest the available bandwidth efficientlyin a wireless network, they employ multiple orthogonal channels over multiple ra-dios at the nodes. In addition, nodes in these networks employ directional antennasas radios to improve spatial throughput. This dissertation develops algorithms forrouting and broadcasting with channel assignment in such networks. First, we com-pute the minimum cost path between a given source-destination pair with channelassignment on each link in the path such that no two transmissions interfere witheach other. Such a path must satisfy the constraint that no two consecutive links onthe path are assigned the same channel, referred to as "channel discontinuity con-straint." To compute such a path, we develop two graph expansion techniques basedon minimum cost perfect matching and dijkstra's algorithm. Through extensive sim-ulations, we study the effectiveness of the routing algorithms developed based onthe two expansion techniques and the benefits of employing the minimum cost per-fect matching based solution. Secondly, we study the benefits of sharing channelbandwidth across multiple flows. We model the routing and channel assignmentproblem in two different ways to account for the presence and absence of inter-flowbandwidth sharing. Benefits of multiple paths between a source-destination pairmotivates the problem of computing multiple paths between a source-destinationpair with channel assignment such that all the paths can be active simultaneouslyto achieve maximal flow between the pair in the considered network. Since finding even two such paths is NP-hard, we formulate the problem as an integer linearprogram and develop efficient heuristic to find these paths iteratively. Thirdly, wecompute a broadcast tree from a given root with channel assignment such that all the links in the broadcast tree can be active simultaneously without interferingwith each other. Since finding such a tree is an NP-hard problem, we formulatethe problem as an integer linear program (ILP) and develop heuristics to find thebroadcast tree with channel assignment. We evaluate and compare the performanceof the developed heuristics with respect to their success rate, average depth of theobtained tree, and average path length from root to a node in the network. Thisdissertation also analyzes the blocking performance of a channel assignment schemein a multi-channel wireless line network. We assume that the existing calls in thenetwork may be rearranged on different channels to accommodate an incoming call.The analysis is limited to single-hop calls with different transmission ranges.Finally, this dissertation evaluates the performance of disjoint multipath routingapproaches for all-to-all routing in packet-switched networks with respect to packetoverhead, path lengths, and routing table size. We develop a novel approach basedon cycle-embedding to obtain two node-disjoint paths between all source-destinationpairs with reduced number of routing table entries maintained at a node (hence thereduced look up time), small average path lengths, and less packet overhead. Westudy the trade-off between the number of routing table entries maintained at anode and the average length of the two disjoint paths by: (a) formulating the cycle-embedding problem as an integer linear program; and (b) developing a heuristic.We show that the number of routing table entries at a node may be reduced toat most two per destination using cycle-embedding approach, if the length of thedisjoint paths are allowed to exceed the minimum by 25%.
15
Markowicz, Federico. "Optimizing order-routing decisions : leveraging omni-channel supply chain fulfillment." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/111492.
Full textAbstract:
Thesis: M.B.A., Massachusetts Institute of Technology, Sloan School of Management, in conjunction with the Leaders for Global Operations Program at MIT, 2017.Thesis: S.M., Massachusetts Institute of Technology, Department of Mechanical Engineering, in conjunction with the Leaders for Global Operations Program at MIT, 2017.
Cataloged from PDF version of thesis.
Includes bibliographical references (page 73).
This thesis provides a deep mathematical analysis of the diverse alternatives for routing models considering an Omni-channel supply chain. The natural evolution of supply chains from traditional brick-and-mortar stores to an omni-channel supply chain, encompassing and merging e-commerce together with a multi-channel concept, allows businesses to reach new levels of operational efficiency by leveraging inventory closer to the customer and making decisions on the fly on how to better and more cheaply provide a service/product to the final consumer. The flexibility and benefits, unfortunately, do not come without a certain dose of complexity and further development of the supply chain tactical implementation and systems. New alternatives to fulfill customer orders are available, which require greater screening among the different alternatives. An effective routing model becomes essential to make sure these alternatives are properly considered in order to satisfy both the consumer and retailer objectives, such as on-time delivery of orders, retail stores' service levels, and fulfillment costs.
by Federico Markowicz.
M.B.A.
S.M.
16
Reid, Stephen Scott. "Uncertainty and sensitivity analyses of the Muskingum-Cunge channel routing model." College Park, Md.: University of Maryland, 2008. http://hdl.handle.net/1903/8972.
Full textAbstract:
Thesis (M.S.) -- University of Maryland, College Park, 2008.Thesis research directed by: Dept. of Civil and Environmental Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
17
Lavén, Andreas. "Anypath Routing for Reducing Latency in Multi-Channel Wireless Mesh Networks." Licentiate thesis, Karlstads universitet, Institutionen för matematik och datavetenskap, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kau:diva-29359.
Full textAbstract:
Increasing capacity in wireless mesh networks can be achieved by using multiple channels and radios. By using different channels, two nodes can send packets at the same time without interfering with each other. To utilize diversity of available frequency, a channel assignment scheme is required. Hybrid channel assignment is an interesting approach where at least one radio is tuned to a fixed channel for receiving and the remaining interfaces switch their channels dynamically in order to match the receiving channel at the receiving node. This provides full connectivity, but at the expense of introduced switching costs. Due to hardware limitations it is too costly to switch channels on a per packet basis. Instead, this thesis proposes an anypath routing and forwarding mechanism in order to allow each node along the route to select the best next hop neighbor on a per packet basis. The routing algorithm finds for each destination a set of next hop candidates and the forwarding algorithm considers the state of the channel switch operation when selecting a next hop candidate. Also, in order to allow latency-sensitive packets to be transmitted before other packets, latency-awareness has been introduced to distinguish e.g. VoIP flows from FTP traffic. The ideas have been implemented and tested using real-world experiments, and the results show a significant reduction in latency.
18
Lee, Unghee. "A Proactive Routing Protocol for Multi-Channel Wireless Ad-hoc Networks." Diss., Virginia Tech, 2006. http://hdl.handle.net/10919/28127.
Full textAbstract:
Wireless mobile ad-hoc networks consist of a collection of peer mobile nodes that form a network and are capable of communicating with each other without help from stationary infrastructure such as access points. The availability of low-cost, com-modity network interface cards (NICs) has made the IEEE 802.11 medium access control (MAC) protocol the de facto MAC protocol for wireless mobile ad-hoc net-works, even though it is not optimal. The IEEE 802.11 MAC protocol is designed to have stations share a single channel in a given network. However, many of the IEEE 802.11 physical (PHY) layer specifications define multiple channels and allow the simultaneous, non-interfering use of some of these channels. Therefore, multiple communications can occur at the same time, offering the opportunity to increase the effective network capacity.
We present an innovative routing protocol that utilizes multiple channels to im-prove the performance of wireless ad-hoc networks. The basic idea of the protocol is to use multiple channels so that multiple useful transmissions can occur simultane-ously, thus increasing network capacity. The proposed scheme requires minor changes to existing proactive ad-hoc routing protocols and no modifications to the current IEEE 802.11 MAC protocol. To reduce inefficiencies due to periodic updates in the proactive routing protocols, the proposed scheme divides the network layer into control and data planes. Nodes send routing updates using the control channel and user packets using the data channel.
To demonstrate the multi-channel routing scheme, we extend the Destination-Sequenced Distance-Vector (DSDV), Open Shortest Path First-Minimal Connected Dominating Set (OSPF-MCDS), and Optimized Link State Routing (OLSR) protocol to multiple channel (MC) versions, denoted as DSDV-MC, OSPF-MCDS-MC, and OLSR-MC, respectively. Simulation results for DSDV-MC, OSPF-MCDS-MC, and OLSR-MC are presented and experimental results for OLSR-MC are presented. Simulation results indicate that DSDV-MC and OSPF-MCDS-MC effectively exploit multiple channels to improve network capacity. Goodput, the throughput consider-ing only useful error-free packets, increases with an increased number of available channels as the number of nodes and network load increase in both single-hop and multiple-hop networks. Experimental results with OLSR-MC also support that the proposed scheme increases network capacity without modification to the MAC proto-col in a real implementation.
Although simulation and experimental results show that proposed scheme im-proves network capacity by exploiting multiple channels, problems exist with channel distribution. We introduce a new metric, the Channel Distribution Index (CDI) to in-vestigate these issues. The CDI indicates the fairness of the channel distribution. We identify the channel convergence problem, where a particular channel is over-utilized, and propose a channel reallocation scheme to mitigate the impact of the channel convergence problem using the CDI.Ph. D.
19
Siam, Mohammad Zakariya. "POWER-CONTROLLED CHANNEL ACCESS AND ROUTING PROTOCOLS FOR MIMO-CAPABLE WIRELESS NETWORKS." Diss., The University of Arizona, 2009. http://hdl.handle.net/10150/194750.
Full textAbstract:
Transmission power control (TPC) has been used in wireless networks to improve channel reuse and/or reduce energy consumption. It has been mainly applied to single-input single-output (SISO) systems. Significant improvement in performancecan be achieved by employing multi-input multi-output (MIMO) techniques. In this dissertation, we propose adaptive medium-access control (MAC) protocols for power-controlled MIMO-capable wireless networks. In these protocols, we adapt the number of transmit/receive antennas, along with the transmission powers/rates, for the purpose of minimizing total energy consumption and/or maximizing network throughput. Our first protocol, called E-BASIC, exploits the diversity gain of MIMO by adapting the transmission mode, transmission power, and modulation order so as to minimize the total energy consumption. We incorporate E-BASIC in the design of an energy-efficient routing (EER) scheme that selects the least-energy end-to-end path. We then propose two MAC protocols that exploit the multiplexing gain of MIMO, and consider their integration into legacy systems. We alsopropose a combined energy/throughput MAC protocol, called CMAC, which dynamically switches between diversity and multiplexing modes so as to maximize a utility function that depends on both energy consumption and throughput. Finally, we consider employing "virtual" MIMO capability into single-antenna wireless sensor networks (WSNs). We propose a distributed MIMO-adaptive energy-efficient clustering/routing protocol, coined CMIMO, which aims at reducing energy consumption in multi-hop WSNs. In CMIMO, each cluster has up to two cluster heads (CHs), which are responsible for routing traffic between clusters. Simulation results indicate that our proposed protocols achieve significant energy/throughput improvement compared with non-adaptive protocols.
20
Chukwudebe, Gloria Azogini. "An efficient channel routing algorithm and its application to sparse matrix superchips." Thesis, University of Newcastle Upon Tyne, 1992. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.308919.
Full text
21
Lin, Christopher C. (Christopher Cheyih). "A decision system for routing returned product to the optimal recovery channel." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/59185.
Full textAbstract:
Thesis (M.B.A.)--Massachusetts Institute of Technology, Sloan School of Management; and, (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science; in conjunction with the Leaders for Manufacturing Program at MIT, 2010.Cataloged from PDF version of thesis.
Includes bibliographical references (p. 62-63).
Dell, a leading computer manufacturer, must deal with systems returned from its customers. Historically, it has refurbished most of its returned systems for resale on its Dell Outlet website. While this has provided high net recoveries (revenue less incurred costs) compared to its peers, Dell believes there is ample opportunity in cannibalizing some returned systems for the piece parts (i.e. "teardown"). These harvested piece parts can be used to service field systems, repair refurbished systems, or directly sold to customers as spare parts. Dell is concerned about ensuring an optimal disposition of system to teardown vs. direct resale. Written as part of research internship at Dell, this paper proposes, simulates, and evaluates a decision support system to address the question of disposition. The decision engines use historical data and statistics to estimate net recoveries in resale and forecasted demand to estimate net recoveries through teardown. Linear regressions were found to have poor power in predicting overall net recoveries; however, simple heuristics were found to identify likely low recovery systems. Overall, the implementation of the decision support system will drive improved net recoveries, with savings estimated to be greater than $1 million annually.
by Christopher C. Lin.
S.M.
M.B.A.
22
West, Dustin Wayne. "A Multidimensional Discontinuous Galerkin Modeling Framework for Overland Flow and Channel Routing." The Ohio State University, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=osu1429626041.
Full text
23
Swaminathan, Arvind. "Channel-access and routing protocols for wireless ad hoc networks with directional antennas." Connect to this title online, 2006. http://etd.lib.clemson.edu/documents/1171041434.
Full text
24
Qayyum, Amir. "Analysis and evaluation of channel access schemes and routing protocols in wireless LANS." Paris 11, 2000. http://www.theses.fr/2000PA112262.
Full textAbstract:
Cette these s'interesse a deux problemes majeurs dans le domaine des reseaux mobiles sans fil : - l'acces multiple au canal, - le routage dynamique. Le choix d'un protocole d'acces multiple qui permet a des utilisateurs geographiquement repartis et mobiles de partager un canal commun est tres important pour une utilisation efficace et equitable de la bande passante disponible. La these presente differents mecanismes d'acces multiple et analyse ensuite plus finement csma (carrier sense multiple access). Elle decrit la technique de signalisation active qui est une amelioration de csma. Elle compare les performances de csma avec et sans signalisation active, en ayant recours a des simulations. La deuxieme partie de la these traite des protocoles de routage pour des reseaux mobiles sans fil. Elle presente le mecanisme d'inondation de message dans un reseau, afin d'etablir une base de comparaison pour les protocoles de routage etudies. Elle montre comment les relais multipoint offrent une alternative plus efficace a l'inondation de message. C'est pourquoi les relais multipoint sont utilises dans le protocole de routage proactif, appele olsr (optimized link state routing). Les principes de ce protocole sont detailles. Des resultats de simulations montrent les performances d'olsr dans des conditions de charge variees et avec differents scenarios de mobilite de reseau.
25
Gao, Xingbo. "DESIGN AND ANALYSIS OF EFFECTIVE ROUTING AND CHANNEL SCHEDULING FOR WAVELENGTH DIVISION MULTIPLEXING OPTICAL NETWORKS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2810.
Full textAbstract:
Optical networking, employing wavelength division multiplexing (WDM), is seen as the technology of the future for the Internet. This dissertation investigates several important problems affecting optical circuit switching (OCS) and optical burst switching (OBS) networks. Novel algorithms and new approaches to improve the performance of these networks through effective routing and channel scheduling are presented. Extensive simulations and analytical modeling have both been used to evaluate the effectiveness of the proposed algorithms in achieving lower blocking probability, better fairness as well as faster switching. The simulation tests were performed over a variety of optical network topologies including the ring and mesh topologies, the U.S. Long-Haul topology, the Abilene high-speed optical network used in Internet 2, the Toronto Metropolitan topology and the European Optical topology. Optical routing protocols previously published in the literature have largely ignored the noise and timing jitter accumulation caused by cascading several wavelength conversions along the lightpath of the data burst. This dissertation has identified and evaluated a new constraint, called the wavelength conversion cascading constraint. According to this constraint, the deployment of wavelength converters in future optical networks will be constrained by a bound on the number of wavelength conversions that a signal can go through when it is switched all-optically from the source to the destination. Extensive simulation results have conclusively demonstrated that the presence of this constraint causes significant performance deterioration in existing routing and wavelength assignment (RWA) algorithms. Higher blocking probability and/or worse fairness have been observed for existing RWA algorithms when the cascading constraint is not ignored. To counteract the negative side effect of the cascading constraint, two constraint-aware routing algorithms are proposed for OCS networks: the desirable greedy algorithm and the weighted adaptive algorithm. The two algorithms perform source routing using link connectivity and the global state information of each wavelength. Extensive comparative simulation results have illustrated that by limiting the negative cascading impact to the minimum extent practicable, the proposed approaches can dramatically decrease the blocking probability for a variety of optical network topologies. The dissertation has developed a suite of three fairness-improving adaptive routing algorithms in OBS networks. The adaptive routing schemes consider the transient link congestion at the moment when bursts arrive and use this information to reduce the overall burst loss probability. The proposed schemes also resolve the intrinsic unfairness defect of existing popular signaling protocols. The extensive simulation results have shown that the proposed schemes generally outperform the popular shortest path routing algorithm and the improvement could be substantial. A two-dimensional Markov chain analytical model has also been developed and used to analyze the burst loss probabilities for symmetrical ring networks. The accuracy of the model has been validated by simulation. Effective proactive routing and preemptive channel scheduling have also been proposed to address the conversion cascading constraint in OBS environments. The proactive routing adapts the fairness-improving adaptive routing mentioned earlier to the environment of cascaded wavelength conversions. On the other hand, the preemptive channel scheduling approach uses a dynamic priority for each burst based on the constraint threshold and the current number of performed wavelength conversions. Empirical results have proved that when the cascading constraint is present, both approaches would not only decrease the burst loss rates greatly, but also improve the transmission fairness among bursts with different hop counts to a large extent.Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
26
Kallio, Rebecca Mae. "Evaluation of Channel Evolution and Extreme Event Routing for Two-Stage Ditches in a Tri-State Region of the USA." The Ohio State University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=osu1275424336.
Full text
27
Cavalcanti, de Castro Marcel. "Enhancing P2P Systems over Wireless Mesh Networks." Doctoral thesis, Karlstads universitet, Avdelningen för datavetenskap, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kau:diva-8691.
Full textAbstract:
Due to its ability to deliver scalable and fault-tolerant solutions, applications based on the peer-to-peer (P2P) paradigm are used by millions of users on the internet. Recently, wireless mesh networks (WMNs) have attracted a lot of interest from both academia and industry, because of their potential to provide flexible and alternative broadband wireless internet connectivity. However, due to various reasons such as unstable wireless link characteristics and multi-hop forwarding operation, the performance of current P2P systems is rather low in WMNs. This dissertation studies the technological challenges involved while deploying P2P systems over WMNs. We study the benefits of location-awareness and resource replication to the P2P overlay while targeting efficient resource lookup in WMNs. We further propose a cross-layer information exchange between the P2P overlay and the WMN in order to reduce resource lookup delay by augmenting the overlay routing table with physical neighborhood and resource lookup history information. Aiming to achieve throughput maximization and fairness in P2P systems, we model the peer selection problem as a mathematical optimization problem by using a set of mixed integer linear equations. A study of the model reveals the relationship between peer selection, resource replication and channel assignment on the performance of P2P systems over WMNs. We extend the model by formulating the P2P download problem as chunk scheduling problem. As a novelty, we introduce constraints to model the capacity limitations of the network due to the given routing and channel assignment strategy. Based on the analysis of the model, we propose a new peer selection algorithm which incorporates network load information and multi-path routing capability. By conducting testbed experiments, we evaluate the achievable throughput in multi-channel multi-radio WMNs. We show that the adjacent channel interference (ACI) problem in multi-radio systems can be mitigated, making better use of the available spectrum. Important lessons learned are also outlined in order to design practical channel and channel bandwidth assignment algorithms in multi-channel multi-radio WMNs.
28
Marlow, Jonathan Edward, and Jonathan Edward Marlow. "The inclusion of channel variability in flow routing: an assessment of model performance for the Colorado River through Grand Canyon." Thesis, The University of Arizona, 1995. http://hdl.handle.net/10150/626816.
Full textAbstract:
An unsteady discharge wave routing model for the Colorado River through
Grand Canyon was modified to include variability in channel geometric and hydraulic
properties. First, a classification scheme was devised to facilitate division of the riparian corridor into eight subreaches of geomorphic similarity. Channel variability was characterized by averaging geometric and hydraulic properties over the length of each subreach. The
subreaches were then treated as separate modules through which three different discharge
patterns were routed and model results compared with results from the unmodified model
relative to United States Geological Survey stream gaging station records. The new model
exhibited some increased accuracy in the timing and magnitude of discharge waves as well
as wave shape. Model results were also found to be particularly sensitive to the friction co
efficient used--a variable parameter designed to incorporate the effects of channel variabil
ity on the flow. Results also show that a more detailed understanding and characterization
of the friction coefficient used within the model would lead to greater overall improve
ments in discharge predictions at particular points. The results of this study should serve as
well to assist researchers pursuing similar studies in planning the types and amounts of field
data to be collected, in order to optimize available research funding.
29
Ivo, Akum Nji. "Comparative Analysis of Performance Routing Metrics for Multi-radio Wireless Mesh Networks." Thesis, Blekinge Tekniska Högskola, Avdelningen för telekommunikationssystem, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-5056.
Full textAbstract:
Traditional Ad Hoc network wireless communication in the past years have contributed tremendously to the dawn of wireless mesh networks (WMNs) which have so far been able to provide a significant improvement in capacity and scalability. Routing metrics which form the basic element for the routing protocol in this innovative communication technology is a call for concern as they must take into consideration the wireless medium network characteristics in order to provide a optimum appreciable QoS performance. In the past many single-radio routing metrics have been proposed for Ad Hoc networks which are not compatible with the multi-radio routing scenario demanded by WMNs. In our work, we provide a comparative analysis of most recently proposed multi-radio routing metrics for WMNs. We begin by providing an overview of the features of a wireless mesh network thereby presenting a better understanding of some of the research challenges of WMNs. Also, since single-radio routing forms the basis of multi-radio routing, we in this regard provide a review of some single-radio routing metrics. In our comparative analysis, an overview of routing protocols for WMNs is provided enabling an understanding of the demands to be included in a routing metric to ensure efficient routing in WMNs since different routing protocols may impose different demands; we then identify the requirements of multi-radio routing metrics from which we base our comparative analysis.
30
Domke, Jens [Verfasser], Wolfgang E. [Akademischer Betreuer] [Gutachter] Nagel, and Tor [Gutachter] Skeie. "Routing on the Channel Dependency Graph: : A New Approach to Deadlock-Free, Destination-Based, High-Performance Routing for Lossless Interconnection Networks / Jens Domke ; Gutachter: Wolfgang E. Nagel, Tor Skeie ; Betreuer: Wolfgang E. Nagel." Dresden : Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://d-nb.info/1135907439/34.
Full text
31
Gong, Michelle Xiaohong. "Improving the Capacity in Wireless Ad Hoc Networks through Multiple Channel Operation: Design Principles and Protocols." Diss., Virginia Tech, 2005. http://hdl.handle.net/10919/28052.
Full textAbstract:
Despite recent advances in wireless local area network (WLAN) technologies, today's WLANs still cannot offer the same data rates as their wired counterparts. The throughput problem is further aggravated in multi-hop wireless environments due to collisions and interference caused by multi-hop routing. Because all current IEEE 802.11 physical (PHY) standards divide the available frequency into several orthogonal channels, which can be used simultaneously within a neighborhood, increasing capacity by exploiting multiple channels becomes particularly appealing.
To improve the capacity of wireless ad hoc networks by exploiting multiple available channels, I propose three principles that facilitate the design of efficient distributed channel assignment protocols. Distributed channel assignment problems have been proven to be NP-complete and, thus, computationally intractable. Though being a subject of many years of research, distributed channel assignment remains a challenging problem. There exist only a few heuristic solutions, none of which is efficient, especially for the mobile ad hoc environment. However, protocols that implement the proposed design principles are shown to require fewer channels and exhibit significantly lower communication, computation, and storage complexity, compared with existing approaches. As examples, I present two such protocols that build on standard reactive and proactive routing protocols. In addition, I prove the correctness of the algorithms and derive an upper bound on the number of channels required to both resolve collisions and mitigate interference.
A new multi-channel medium access control (MC-MAC) protocol is also proposed for multi-hop wireless ad hoc networks. MC-MAC is compatible with the IEEE 802.11 medium access control (MAC) standard and imposes the minimum system requirements among all existing multi-channel MAC protocols. In addition, simulation results show that even with only a single half-duplex transceiver, MC-MAC, by exploiting multiple channels, can offer up to a factor of four improvement in throughput over the IEEE 802.11 MAC protocol. The reduction in delay is even more significant.
Therefore, the MC-MAC protocol and the accompanying distributed channel assignment protocols constitute an effective solution to the aforementioned performance problem in a multi-hop wireless network.
Finally, I generalize the cross-layer design principle to more general networking functions and present a network architecture to motivate and facilitate cross-layer designs in wireless networks. A literature survey is provided to validate the proposed cross-layer design architecture. Current cross-layer design research can be categorized into two classes: joint-layer design using optimization techniques, and adaptive techniques based on system-profile and/or QoS requirements. Joint-layer design based on optimization techniques can achieve optimal performance, but at the expense of complexity. Adaptive schemes may achieve relatively good performance with less complexity. Nevertheless, without careful design and a holistic view of the network architecture, adaptive schemes may actually cause more damage than benefit.Ph. D.
32
Marciszko, Tobias. "A tool for optimized layout of flat cable harnesses for future on-board cabling systems in cars." Thesis, Linköping University, Department of Computer and Information Science, 2004. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-2325.
Full textAbstract:
Current cabling systems in cars are about to be, completely or partially, replaced by a cabling technology called flexible flat cables, FFCs. This new technology requires tools that can assist engineers in the design process of the cable layouts. The aim of this thesis is to develop a software demonstrator of a concept tool for this purpose.
The task is divided into three problem areas. Topology modeling, optimization and visualization. An editor is to be implemented which handles creation and modification of topologies which represents FFC harnesses. The optimization is performed using global and local routing. The global routing handles optimization on topology level, defining net paths in the topology. Local routing handles the exact net placement on each bus cable. Finally, the local routing solutions should be graphically presented to the user.
The topology modeling requirement was implemented as a graph layouteditor. Global routing is performed using graph search techniques and local routing is based on VLSI channel routing methods. Visualization is implemented for the local routing solutions using the SVG format.
The developed application handles most of the requirements. The editor has support for an XML netlist which is used for specifying connectors and nets used in the topology. Global routing and local routing can be performed on the topology. Prerouting of nets can be performed on both global and local level. Support for assigning specific cables, from a library, to bus cables is possible.
33
Catalán, Cid Miguel. "Contributions to the routing of traffic flows in multi-hop IEEE 802.11 wireless networks." Doctoral thesis, Universitat Politècnica de Catalunya, 2016. http://hdl.handle.net/10803/386561.
Full textAbstract:
The IEEE 802.11 standard was not initially designed to provide multi-hop capabilities. Therefore, providing a proper traffic performance in Multi-Hop IEEE 802.11 Wireless Networks (MIWNs) becomes a significant challenge. The approach followed in this thesis has been focused on the routing layer in order to obtain applicable solutions not dependent on a specific hardware or driver. Nevertheless, as is the case of most of the research on this field, a cross-layer design has been adopted. Therefore, one of the first tasks of this work was devoted to the study of the phenomena which affect the performance of the flows in MIWNs. Different estimation methodologies and models are presented and analyzed.
The first main contribution of this thesis is related to route creation procedures. First, FB-AODV is introduced, which creates routes and forwards packets according to the flows on the contrary to basic AODV which is destination-based. This enhancement permits to balance the load through the network and gives a finer granularity in the control and monitoring of the flows. Results showed that it clearly benefits the performance of the flows. Secondly, a novel routing metric called Weighted Contention and Interference routing Metric (WCIM) is presented. In all analyzed scenarios, WCIM outperformed the other analyzed state-of-the-art routing metrics due to a proper leveraging of the number of hops, the link quality and the suffered contention and interference.
The second main contribution of this thesis is focused on route maintenance. Generally, route recovery procedures are devoted to the detection of link breaks due to mobility or fading. However, other phenomena like the arrival of new flows can degrade the performance of active flows. DEMON, which is designed as an enhancement of FB-AODV, allows the preemptive recovery of degraded routes by passively monitoring the performance of active flows. Results showed that DEMON obtains similar or better results than other published solutions in mobile scenarios, while it clearly outperforms the performance of default AODV under congestion
Finally, the last chapter of this thesis deals with channel assignment in multi-radio solutions. The main challenge of this research area relies on the circular relationship between channel assignment and routing; channel assignment determines the routes that can be created, while the created routes decide the real channel diversity of the network and the level of interference between the links. Therefore, proposals which join routing and channel assignment are generally complex, centralized and based on traffic patterns, limiting their practical implementation. On the contrary, the mechanisms presented in this thesis are distributed and readily applicable. First, the Interference-based Dynamic Channel Assignment (IDCA) algorithm is introduced. IDCA is a distributed and dynamic channel assignment based on the interference caused by active flows which uses a common channel in order to assure connectivity. In general, IDCA leads to an interesting trade-off between connectivity preservation and channel diversity. Secondly, MR-DEMON is introduced as way of joining channel assignment and route maintenance. As DEMON, MR-DEMON monitors the performance of the active flows traversing the links, but, instead of alerting the source when noticing degradation, it permits reallocating the flows to less interfered channels. Joining route recovery instead of route creation simplifies its application, since traffic patterns are not needed and channel reassignments can be locally decided. The evaluation of MR-DEMON proved that it clearly benefits the performance of IDCA. Also, it improves DEMON functionality by decreasing the number of route recoveries from the source, leading to a lower overhead.El estándar IEEE 802.11 no fue diseñado inicialmente para soportar capacidades multi-salto. Debido a ello, proveer unas prestaciones adecuadas a los flujos de tráfico que atraviesan redes inalámbricas multi-salto IEEE 802.11 supone un reto significativo. La investigación desarrollada en esta tesis se ha centrado en la capa de encaminamiento con el objetivo de obtener soluciones aplicables y no dependientes de un hardware específico. Sin embargo, debido al gran impacto de fenómenos y parámetros relacionados con las capas físicas y de acceso al medio sobre las prestaciones de los tráficos de datos, se han adoptado soluciones de tipo cross-layer. Es por ello que las primeras tareas de la investigación, presentadas en los capítulos iniciales, se dedicaron al estudio y caracterización de estos fenómenos. La primera contribución principal de esta tesis se centra en mecanismos relacionados con la creación de las rutas. Primero, se introduce una mejora del protocolo AODV, que permite crear rutas y encaminar paquetes en base a los flujos de datos, en lugar de en base a los destinos como se da en el caso básico. Esto permite balacear la carga de la red y otorga un mayor control sobre los flujos activos y sus prestaciones, mejorando el rendimiento general de la red. Seguidamente, se presenta una métrica de encaminamiento sensible a la interferencia de la red y la calidad de los enlaces. Los resultados analizados, basados en la simulación de diferentes escenarios, demuestran que mejora significativamente las prestaciones de otras métricas del estado del arte. La segunda contribución está relacionada con el mantenimiento de las rutas activas. Generalmente, los mecanismos de mantenimiento se centran principalmente en la detección de enlaces rotos debido a la movilidad de los nodos o a la propagación inalámbrica. Sin embargo, otros fenómenos como la interferencia y congestión provocada por la llegada de nuevos flujos pueden degradar de forma significativa las prestaciones de los tráficos activos. En base a ello, se diseña un mecanismo de mantenimiento preventivo de rutas, que monitoriza las prestaciones de los flujos activos y permite su reencaminamiento en caso de detectar rutas degradadas. La evaluación de esta solución muestra una mejora significativa sobre el mantenimiento de rutas básico en escenarios congestionados, mientras que en escenarios con nodos móviles obtiene resultados similares o puntualmente mejores que otros mecanismos preventivos diseñados específicamente para casos con movilidad. Finalmente, el último capítulo de la tesis se centra en la asignación de canales en entornos multi-canal y multi-radio con el objetivo de minimizar la interferencia entre flujos activos. El reto principal en este campo es la dependencia circular que se da entre la asignación de canales y la creación de rutas: la asignación de canales determina los enlaces existentes la red y por ello las rutas que se podrán crear, pero son finalmente las rutas y los tráficos activos quienes determinan el nivel real de interferencia que se dará en la red. Es por ello que las soluciones que proponen unificar la asignación de canales y el encaminamiento de tráficos son generalmente complejas, centralizadas y basadas en patrones de tráfico, lo que limita su implementación en entornos reales. En cambio, en nuestro caso adoptamos una solución distribuida y con mayor aplicabilidad. Primero, se define un algoritmo de selección de canales dinámico basado en la interferencia de los flujos activos, que utiliza un canal común en todos los nodos para asegurar la conectividad de la red. A continuación, se introduce un mecanismo que unifica la asignación de canales con el mantenimiento preventivo de las rutas, permitiendo reasignar flujos degradados a otros canales disponibles en lugar de reencaminarlos completamente. Ambas soluciones demuestran ser beneficiosas en este tipo de entornos.
34
Goudarzi, Forough. "Non-cooperative beaconing control in vehicular ad hoc networks." Thesis, Brunel University, 2017. http://bura.brunel.ac.uk/handle/2438/15608.
Full textAbstract:
The performance of many protocols and applications of Vehicular Ad hoc Networks (VANETs), depends on vehicles obtaining enough fresh information on the status of their neighbouring vehicles. This should be fulfilled by exchanging Basic Safety Messages (BSMs) also called beacons using a shared channel. In dense vehicular conditions, many of the beacons are lost due to channel congestion. Therefore, in such conditions, it is necessary to control channel load at a level that maximizes BSM dissemination. To address the problem, in this thesis algorithms for adaptation of beaconing to control channel load are proposed. First, a position-based routing protocol for VANETs is proposed and the requirement of adaptive beaconing to increase the performance of the protocol is indicated. The routing protocol is traffic-aware and suitable for city environments and obtains real-time traffic information in a completely ad hoc manner without any central or dedicated control, such as traffic sensors, roadside units, or information obtained from outside the network. The protocol uses an ant-based algorithm to find a route that has optimum network connectivity. Using information included in small control packets called ants, vehicles calculate a weight for every street segment that is proportional to the network connectivity of that segment. Ant packets are launched by vehicles in junction areas. To find the optimal route between a source and destination, a source vehicle determines the path on a street map with the minimum total weight for the complete route. The correct functionality of the protocol design has been verified and its performance has been evaluated in a simulation environment. Moreover, the performance of the protocol in different vehicular densities has been studied and indicated that in dense vehicular conditions the performance of the protocol degrades due to channel load created by uncontrolled periodic beaconing. Then, the problem of beaconing congestion control has been formulated as non-cooperative games, and algorithms for finding the equilibrium point of the games have been presented. Vehicles as players of the games adjust their beacon rate or power or both, based on the proposed algorithms so that channel load is controlled at a desired level. The algorithms are overhead free and fairness in rate or power or both rate and power allocation are achieved without exchanging excess information in beacons. Every vehicle just needs local information on channel load while good fairness is achieved globally. In addition, the protocols have per-vehicle parameters, which makes them capable of meeting application requirements. Every vehicle can control its share of bandwidth individually based on its dynamics or requirements, while the whole usage of the bandwidth is controlled at an acceptable level. The algorithms are stable, computationally inexpensive and converge in a short time, which makes them suitable for the dynamic environment of VANETs. The correct functionality of the algorithms has been validated in several high density scenarios using simulations.
35
CHUNG, CHIN-MIN, and 鍾志敏. "Channel Routing Crosstalk Minimization." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/35725423861820758657.
Full textAbstract:
碩士中原大學
資訊工程學系
88
As the VLSI fabrication tevhnology rapidly evolves, interconnection wires are placed in closer proximity and circuits operate at higher frequencies. Accordingly, it becomes important to consider crosstalk caused by coupling capacitance between adjacent interconnection wires in the layout design for the fast and VLSI circuits. The researches of the channel routing problem in the past usually focus on area of routing without the coupling effect between the interconnection. In this thesis, we propose a method to the gridded channel routing problem with objectives of satisfying crosstalks of the all net. We use Simulated-Annealing approach with considering both segment reassignment and doglegs to get the channel routing problem with minimum crosstalk without changing the height of channel. Experimental result shows that our method can significantly gets better solutions of the minslack and total crosstalk than the other method such as track permutation[4] and the segment reassignment[9] and [8].
36
CHEN, CONG-MIN, and 陳聰敏. "VLSI multi-layer channel routing." Thesis, 1991. http://ndltd.ncl.edu.tw/handle/01171891948013845965.
Full text
37
Lin, Tong Hong, and 林東弘. "Channel Routing by Interval Sorting." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/69076405656026648271.
Full text
38
Chih, Hsu Kuo, and 徐國智. "Minimum Crosstalk Channel Routing with Dogleg." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/30736939623456364118.
Full textAbstract:
碩士中原大學
資訊工程學系
87
As the VLSI fabrication technology rapidly evolves, interconnection wires are placed in closer proximity and circuits operate at higher frequencies. Accordingly, it becomes important to consider crosstalk caused by the coupling capacitance between adjacent interconnection wires in the layout design for the fast and safe VLSI circuits. Usually, in the design specification, the maximum tolerable crosstalk for each net that will guarantee the proper functioning of the circuit is given, and crosstalk in each net should not exceed its corresponding maximum tolerable crosstalk in a valid design. In this thesis, we present an approach to the gridded channel routing problem with the objectives of satisfying crosstalk constraints on the nets and minimizing the total crosstalk among all of the nets. Given an initial routing solution generated by a conventional channel routing algorithm, the reduction of crosstalks is carried out by the reassignment of the horizontal wire segments. In order to further reduce the crosstalks, doglegs are allowed for some specified wire segments. To effectively and optimally perform the reassignment process, an integer linear programming (ILP) formulation is proposed. Experimental results show that our algorithm can improve the minslack and the total crosstalks significantly. Comparing to the track permutation approach[11] (resp. the segment reassignment approach[12]), we has 142.86% (resp. 54.55%) improvement for minslack and 127.72% (resp. 30.68%) reduction for total crosstalks.
39
Lin, Yow-Ru, and 林佑儒. "The Studies of Channel Routing Problems." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/78072799917905260876.
Full textAbstract:
碩士中原大學
資訊工程研究所
83
In this thesis, two routing problems are discussed . (1) Mixed slope channel routing problem. (2) Over the cell channel routing problem. These two routing problems use the similar channel compression method. (1) Mixed slope channel routing problem To transform the two layer channel routing solutions to multi-layer channel routing solutions, our algorithm examines all segments of two layer channel routing solutions and converts them into linked-lists. From linked-lists structure, we construct the so-called bipartied crossing graph corresponding to two layer routing solution. And then the layer- assignment problem can be treated as a graph coloring problem. So ,we showed that no matter how the original channel model is in the manhattan model or a mixed-slope model, we are sure that these channel routing solutions can be translated into multi- layer channel routing by our proposed algorithm. (2) Over the cell channel routing problem First we use the output of an existence channel router proposed by [HsKa,1994]as the input of our algorithm. Then we choose some proper segments inside the channel, and reroute them to minimize as channel width. The minimization of number of vias is also discussed. Extensive experiments show that our algorithm performs very well.
40
Lin, Yi-Chen, and 林奕辰. "Star-Routing Algorithm For Three-Layers Channel Routing Using Manhattan-Diagonal Model." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/15776886691018725408.
Full textAbstract:
碩士淡江大學
電機工程學系碩士班
96
The Very Large Scale Integration (VLSI) manufacturing technology progresses is increasingly in recent year, Integrated Circuit (IC) design cannot be accomplished successfully by the pure manpower. The complexity of the IC is the major cause. In order to deal with that, Electronic Design Automation (EDA) has greatly decreased the time form establishing the system specifications to tape-out and reduced the manpower. In nanometer-scale processing, a VLSI chip may contain several million transistors. As a result, it is highly probable that tens of millions of connecting nets have to be routed completely and successfully in the layout step. The problem of the routing becomes more and more complicated. We must finish the all routing nets in the finite routing region, or going back to replace the whole components in prior step. It is in order to adjust to more suitable routing region, then expending too much time in placement and routing. In a word, a nice router is very important for IC design. In this paper, we use the grid-model to deal with the routing problem. The advantage of using grid-model needs not too complex data structure to solve it, and making the complexity of routing lower. Besides, we use the three metal-layers to be the major components of routing. We also use the positive and negative 45 degrees routing path, and therefore reduce the routing path and length. In our proposed algorithm, we draw up the smaller grid-model, and in order to avoid violating the Design Rule Check (DRC), so the algorithm has a restriction for the third metal-layer in routing step. Although we use three metal-layers in our algorithm, this way can not only reduce the signal length but also decrease the antenna effect between signals than the other multilayer routing algorithm. We needn’t increasing the other spaces and moving any pins to finish the routing completely. The foregoing is good for hard blocks to finish the routing easily, and it does not replace the location of hard blocks because of routing incompletely. Therefore, the height of the entire routing channel can reduce a lot. In the test cases, we use several test benchmarks of channel routing, including YK3a, YK3b, YK3c, Deutsch’s Difficult Example (DDE) and ISCAS 85 benchmarks. In the simulation results, the result of YK3c has more numbers of the routing track than others, even so, our routing channel height after conversion still less than others, because our unit of grid-model is smaller than others. The height of routing channel decrease 30% in average and it can guarantee to achieve 100% routing.
41
CAI, MING-XIAN, and 蔡明憲. "A study of permutation channel routing problem." Thesis, 1988. http://ndltd.ncl.edu.tw/handle/00362009900065953878.
Full text
42
Chen, Ying-Chih, and 陳盈志. "Crosstalk Minimization in Non-Manhattan Channel Routing." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/37254163438749009478.
Full textAbstract:
碩士中原大學
資訊工程學系
87
Recently, with the VLSI fabrication technology rapidly evolves and the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of decreasing crosstalk. Non-Manhattan channel routing has been proposed, and shown , in many cases, the channel width generated by non-Manhattan channel routers will be lesser than those generated by Manhattan channel routers. Although non-Manhattan channel routing algorithms have be well developed, the problem of decreasing crosstalk has never been formulated and studied. Hence, in this thesis, we propose a method for calculating crosstalk of the non-Manhattan channel. The proposed new algorithm accepts a minimum with routing solution as input and uses the techniques of routing regularization and layer assignment to minimize the crosstalk and vias in two-layer and two-terminal channel. The time complexity of this new algorithm is proven to be in O(K2*N) time where N is the number of nets in a channel and K is the number of tracks of a channel. This new algorithm is further extended to deal with the problem of increasing number of tracks、the problem of crosstalk minimization for a specified critical path、vias problem、multi-terminal and multi-layer routing problem. In our experiments, it shows that our new algorithm reduces the crosstalk by 30% compared with Chen’s algorithm[21]. An algorithm for minimizing the crosstalk of a specified critical path is also proposed. Experiments show that it can obtain fairly good solutions. The post vias-minimization algorithm reduces the vias by 14%. We also discuss the problem of increasing number of tracks to reduce the crosstalk.
43
GUO, MA-ZHEN, and 郭雅貞. "A new approach for channel routing problem." Thesis, 1992. http://ndltd.ncl.edu.tw/handle/77931350421081880286.
Full text
44
ZHANG, GUO-EN, and 張國恩. "Three-layer channel routing with via minimization." Thesis, 1989. http://ndltd.ncl.edu.tw/handle/55166935606565557954.
Full text
45
Chan, Hsuan-Hao, and 詹烜皓. "Rate-Adaption Channel Assignment and Routing Algorithm forMulti-Channel WirelessMAN Mesh Networks." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/65vm8a.
Full textAbstract:
碩士國立中央大學
資訊工程研究所
94
Wireless mesh networks provide an easy deployed and extensi- ble solution to access Internet or communicate with each other for both enterprises and individuals. With the help of multi-channel and multi- radio, wireless mesh network can support more tra¢ c load to meet higher and higher bandwidth requirement in this modern time. There have been researches that focus on channel assignment and routing al- gorithm for IEEE 802.11 multi-channel environment to achieve better network throughout. However, the data rate and transmission range of 802.11 is limited and is not suitable for a large area metropolitan mesh network deployment. This thesis presents a rate-adaption chan- nel assignment and routing algorithm for IEEE 802.16 multi-channel multi-radio network in mesh mode which is expected as the last-mile wireless broadband connectivity. We takes 802.16 TDMA characteris- tic and modulation/rate adaption into consideration. The Simulation results show that our channel assignment procedure uses fewer chan- nels and better channel utilization than the migrated 802.11 greedy approach. Among the three comparing routing protocols, our protocol performs better in multi-rate 802.16 mesh network and results in higher aggregate throughput.
46
Hsu, Yi-hsiang, and 許益祥. "An Effective Crosstalk Optimizer in Gridded Channel Routing." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/15240217195902731878.
Full textAbstract:
碩士中原大學
電子工程研究所
90
The wire-to-wire spacing in a VLSI chip becomes closer as the VLSI fabrication technology rapidly evolves in current years. With VLSI design entering the deep sub-micron, the feature sizes continues to decrease and the operating frequency more and more highly. Many of digital and analog circuits were integrated into single chip. When the circuits work at low-voltage system, the chip becomes very sensitivity for noise. The crosstalk effects are between coupling capacitance of two parallel wires that becomes the main source of signal delay. The coupling effect can affect speed of signal transition, then the crosstalk can make fault function of chip. In this thesis, we will propose a timing driven gridded channel routing algorithms for the minimization of crosstalk problem. Compared with previous works, the main distinction of our approach is that it considers the signal arrival time. So that we can precisely estimate the actual delay degradation caused by crosstalk effect. This algorithm was implemented in C++ programming language and run on different benchmark circuits. Experimental data consistently shows that our approach is effective and efficient for crosstalk minimization.
47
Chang, Yu-hsiang, and 張宇翔. "Channel Sticks Routing for a Resistor-string Array." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/94210487432083430393.
Full textAbstract:
碩士國立中央大學
電機工程學系
102
As the evolution of the semiconductor process technology, the process variation will be more and more serious in device mismatch and wire parasitic. In addition, analog circuit design process can easily become the bottleneck in the overall SoC design process, mainly because it is much more complicated and error-prone. A reliable automation tool will become the key point to enhance the efficiency of the overall circuit design. For the series resistor array in resistor-string DAC, we can effectively reduce the random error by the permutation and space correlation of resistors. However, the high precision resistor string and resistor array permutation will increase the difficulty of the physical layout, and the inconsistency of the parasitic resistance will cause the circuit system error. In this consideration, if a good arrangement can not be achieved in the physical layout automation and balance parasitic effects, it will eventually fall short. So the automated routing and interconnect resistance balance has already indispensable. In this thesis, first, we define the matrix model of the series resistor array routing problem. On the basis of this model, we can ensure that each resistor connected wires having the same layer distribution, the same number of VIA block, and the consistent connection form. Then we propose a channel sticks routing for a resistor-string array, which applied to arbitrary permutation, any bits resistor strings automation layout and routing. Furthermore, this method will achieve in extremely irregular Tango march permutation, and balance the drastic interconnect resistance variation. While developing a graphical user interface (GUI) tool, it can provide users to set routing information, and present the parasitic resistance analysis of each wire in the overall routing clearly.
48
Liu, Shang-Chun, and 劉上群. "Channel Assignment and Routing for Multi-Channel Wireless Mesh Networks Using Generic Algorithms." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/98973267316416636809.
Full textAbstract:
碩士國立交通大學
資訊科學系所
94
In recent years, the application of wireless mesh network has provided a quite attractive solution for last-mile broadband internet access service. Despite the unceasing advance in wireless physical-layer technologies, interference is still the major factor that limits the bandwidth in conventional single-channel wireless networks. Therefore, by exploiting multiple non-overlap channels and multiple NICs environment, interference can be decreased and the available bandwidth can be increased substantially. In this study, a heuristic routing and channel assignment algorithm, called Load aware Single Request Routing algorithm (LASRR) is first proposed to route a single traffic request and assigns channels to the links on the route that have not been assigned yet. Base on LASRR, we further develop two generic based algorithms that aim at different traffic requirements; Hill-Climbing based Routing and Channel Assignment algorithm (HCRCA) for static traffic requirement and Simulated-Annealing based Routing and Channel Assignment algorithm (SARCA) for dynamic traffic requirement. While the former simply commits several iterations to maximize the network throughput, the later also utilizes a pre-defined cost functions to minimize the blocking probability for each coming request. Finally, simulation is conducted to demonstrate the performance improvement compared to an existing algorithm.
49
尹廣淳. "Channel-hopping Scheme and Channel-diverse Routing in Multi-radio Multi-hop Wireless Networks." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/39283070138850719865.
Full textAbstract:
碩士國立交通大學
電信工程研究所
99
In modern wireless networks with multiple orthogonal (non-overlapping) channels available, one essential performance topic is how to effectively exploit channel diversity to enable parallel communications. Generally, having a radio interface hop through all available channels produces better spectrum diversity than binding it permanently to one channel, at the cost of channel switching delays and potentially compromised network connectivity. Moreover, multi-hop communications become challenging due to the lack of a common rendezvous for discovering routes and the difficulty of relaying packets from hop to hop. In this thesis, we propose a multi-radio channel-hopping scheme (CHS) that preserves network connectivity. We prove that less than three radios are required by CHS in order to achieve good channel overlapping in widespread IEEE 802.11-based wireless systems. Corresponding channel-diverse routing (CDR) protocol is devised to realize efficient multi-hop communications. Simulation results demonstrate that the proposed CDR outperforms other strategies in an IEEE 802.11a multi-hop networking environment.
50
溫穗安. "An Efficient Approcah to Over-the -Cell Channel Routing." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/66827344020559008301.
Full textAbstract:
碩士中原大學
資訊工程學系
85
In this thesis, we study the over-the-cell channel routing problem for the new cell model in which all the pins are positioned along a horizontal line inside the corresponding cells. We present a three-step approach to this problem under the assumption that two metal layers are available for routing in the two over-the-cell regiongs and three metal layers are available for routing in the channel. The first step is to consider the three routing regions ( i.e, the channel and the two over-the-cell regions ) as an expended channel. and to apply any existing two-layer channel router to generate a routing solution that consists of a set of tracks. The second step is to assign each track to exactly one of the three routing regions, and to re-arrange under the three-layer environment the set of tracks that are assigned tothe channel in such a way that without violating any constraints, the resulting channel has as less number of tracks as possible. The problem to be solved in the second step can be formulated as a constrained two-processor scheduling problem, for which we develop an optimal algorithm of polynomial time. The last step of our approach is to generate the final over-the-cell channel routing solution by connecting each vertical wire to its corresponding track(s). Our approach has been implemented in C language, and expenimented reaults are also provided to support it.