Routing messages between pairs of nodes is one of the most fundamental tasks in any distributed computing system. An Interval Routing Scheme (IRS) is a well-known, space-efficient routing strategy for routing messages in a network. In this scheme, each node of the network is assigned an integer label and each link at each node is labeled with an interval. The interval assigned to a link l at a node v indicates the set of destination addresses of the messages which should be forwarded through l at v. When studying interval routing schemes, there are two main problems to be considered: a) Which classes of networks do support a specific routing scheme? b) Assuming that a given network supports IRS, how good are the paths traversed by messages? The first problem is known as the characterization problem and has been studied for several types of IRS. In this thesis, we study the characterization problem for various schemes in which the labels assigned to the vertices are d-ary integer tuples (d-dimensional IRS) and the label assigned to each link of the network is a list of d 1-dimensional intervals. This is known as Multi-dimensional IRS (MIRS) and is an extension of the the original IRS. We completely characterize the class of network which support MIRS for linear (which has no cyclic intervals) and strict (which has no intervals assigned to a link at a node v containing the label of v) MIRS. In real networks usually the costs of links may vary over time (dynamic cost links). We also give a complete characterization for the class of networks which support a certain type of MIRS which routes all messages on shortest paths in a network with dynamic cost links. The main criterion used to measure the quality of routing (the second problem) is the length of routing paths. In this thesis we also investigate this problem for MIRS and prove two lower bounds on the length of the longest routing path. These are the only known general results for MIRS. Finally, we study the relationship between various types of MIRS and the problem of drawing a hypergraph. Using some of our results we prove a tight bound on the number of dimensions of the space needed to draw a hypergraph.

Wireless Mesh Networking is envisioned as an economically viable paradigm and a promising technology in providing wireless broadband services. The wireless mesh backbone consists of fixed mesh routers that interconnect different mesh clients to themselves and to the wireline backbone network. In order to approach the wireline servicing level and provide same or near QoS guarantees to different traffic flows, the wireless mesh backbone should be quality-of-service (QoS) aware. A key factor in designing protocols for a wireless mesh network (WMN) is to exploit its distinct characteristics, mainly immobility of mesh routers and less-constrained power consumption. In this work, we study the effect of varying the transmission power to achieve the required signal-to-interference noise ratio for each link and, at the same time, to maximize the number of simultaneously active links. We propose a QoS-aware routing framework by using transmission power control. The framework addresses both the link scheduling and QoS routing problems with a cross-layer design taking into consideration the spatial reuse of the network bandwidth. We formulate an optimization problem to find the optimal link schedule and use it as a fitness function in a genetic algorithm to find candidate routes. Using computer simulations, we show that by optimal power allocation the QoS constraints for the different traffic flows are met with more efficient bandwidth utilization than the minimum power allocations.

A VLSI chip can today contain hundreds of millions transistors and is expected to contain more than 1 billion transistors in the next decade. In order to handle this rapid growth in integration technology, the design procedure is therefore divided into a sequence of design steps. Circuit layout is the design step in which a physical realization of a circuit is obtained from its functional description. Global routing is one of the key subproblems of the circuit layout which involves finding an approximate path for the wires connecting the elements of the circuit without violating resource constraints. The global routing problem is NP-hard, therefore, heuristics capable of producing high quality routes with little computational effort are required as we move into the Deep Sub-Micron (DSM) regime. In this thesis, different approaches for global routing problem are first reviewed. The advantages and disadvantages of these approaches are also summarized. According to this literature review, several mathematical programming based global routing models are fully investigated. Quality of solution obtained by these models are then compared with traditional Maze routing technique. The experimental results show that the proposed model can optimize several global routing objectives simultaneously and effectively. Also, it is easy to incorporate new objectives into the proposed global routing model. To speedup the computation time of the proposed ILP based global router, several hierarchical methods are combined with the flat ILP based global routing approach. The experimental results indicate that the bottom-up global routing method can reduce the computation time effectively with a slight increase of maximum routing density. In addition to wire area, routability, and vias, performance and low power are also important goals in global routing, especially in deep submicron designs. Previous efforts that focused on power optimization for global routing are hindered by excessively long run times or the routing of a subset of the nets. Accordingly, a power efficient multi-pin global routing technique (PIRT) is proposed in this thesis. This integer linear programming based techniques strives to find a power efficient global routing solution. The results indicate that an average power savings as high as 32\% for the 130-nm technology can be achieved with no impact on the maximum chip frequency.

This thesis contributes toward the design of a quality-of-service (QoS) aware network layer for wireless ad hoc networks. With the lack of an infrastructure in ad hoc networks, the role of the network layer is not only to perform multihop routing between a source node and a destination node, but also to establish an end-to-end connection between communicating peers that satisfies the service level requirements of multimedia applications running on those peers. Wireless ad hoc networks represent autonomous distributed systems that are infrastructure-less, fully distributed, and multi-hop in nature. Over the last few years, wireless ad hoc networks have attracted significant attention from researchers. This has been fueled by recent technological advances in the development of multifunction and low-cost wireless communication gadgets. Wireless ad hoc networks have diverse applications spanning several domains, including military, commercial, medical, and home networks. Projections indicate that these self-organizing wireless ad hoc networks will eventually become the dominant form of the architecture of telecommunications networks in the near future. Recently, due to increasing popularity of multimedia applications, QoS support in wireless ad hoc networks has become an important yet challenging objective. The challenge lies in the need to support the heterogeneous QoS requirements (e.g., data rate, packet loss probability, and delay constraints) for multimedia applications and, at the same time, to achieve efficient radio resource utilization, taking into account user mobility and dynamics of multimedia traffic. In terms of research contributions, we first present a position-based QoS routing framework for wireless ad-hoc networks. The scheme provides QoS guarantee in terms of packet loss ratio and average end-to-end delay (or throughput) to ad hoc networks loaded with constant rate traffic. Via cross-layer design, we apply call admission control and temporary bandwidth reservation on discovered routes, taking into consideration the physical layer multi-rate capability and the medium access control (MAC) interactions such as simultaneous transmission and self interference from route members. Next, we address the network-layer resource allocation where a single-hop ad hoc network is loaded with random traffic. As a starting point, we study the behavior of the service process of the widely deployed IEEE 802.11 DCF MAC when the network is under different traffic load conditions. Our study investigates the near-memoryless behavior of the service time for IEEE 802.11 saturated single-hop ad hoc networks. We show that the number of packets successfully transmitted by any node over a time interval follows a general distribution, which is close to a Poisson distribution with an upper bounded distribution distance. We also show that the service time distribution can be approximated by the geometric distribution and illustrate that a simplified queuing system can be used efficiently as a resource allocation tool for single hop IEEE 802.11 ad hoc networks near saturation. After that, we shift our focus to providing probabilistic packet delay guarantee to multimedia users in non-saturated IEEE 802.11 single hop ad hoc networks. We propose a novel stochastic link-layer channel model to characterize the variations of the IEEE 802.11 channel service process. We use the model to calculate the effective capacity of the IEEE 802.11 channel. The channel effective capacity concept is the dual of the effective bandwidth theory. Our approach offers a tool for distributed statistical resource allocation in single hop ad hoc networks, which combines both efficient resource utilization and QoS provisioning to a certain probabilistic limit. Finally, we propose a statistical QoS routing scheme for multihop IEEE 802.11 ad hoc networks. Unlike most of QoS routing schemes in literature, the proposed scheme provides stochastic end-to-end delay guarantee, instead of average delay guarantee, to delay-sensitive bursty traffic sources. Via a cross-layer design approach, the scheme selects the routes based on a geographical on-demand ad hoc routing protocol and checks the availability of network resources by using traffic source and link-layer channel models, incorporating the IEEE 802.11 characteristics and interaction. Our scheme extends the well developed effective bandwidth theory and its dual effective capacity concept to multihop IEEE 802.11 ad hoc networks in order to achieve an efficient utilization of the shared radio channel while satisfying the end-to-end delay bound.

Modern routers use specialized hardware, such as Ternary Content Addressable Memory (TCAM), to solve the Longest Prefix Matching Problem (LPMP) quickly. Due to the fact that TCAM is a non-standard type of memory and inherently parallel, there are concerns about its cost and power consumption. This problem is exacerbated by the growth in routing tables, which demands ever larger TCAMs. To reduce the size of the TCAMs in a distributed forwarding environment, a batch caching model is proposed and analyzed. The problem of determining which routing prefixes to store in the TCAMs reduces to the In-tree Knapsack Problem (ITKP) for unit weight vertices in this model. Several algorithms are analysed for solving the ITKP, both in the general case and when the problem is restricted to unit weight vertices. Additionally, a variant problem is proposed and analyzed, which exploits the caching model to provide better solutions. This thesis concludes with discussion of open problems and future experimental work.

To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes.To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook

An ad hoc network is a collection of mobile wireless devices that cooperate with each other to route packets amongst themselves. The main difficulty in designing routing algorithms for such a network is the large number of topology changes that the network undergoes due to device movement. Selective flooding is a routing technique that is more resilient to topology changes than traditional algorithms but is more bandwidth efficient than pure flooding. An on-demand selective flooding algorithm has been designed and tested on the ns-2 simulator. In scenarios involving a large number of topology changes, selective flooding outperforms other ad hoc network routing techniques. Unfortunately, selective flooding is much more bandwidth hungry and is unable to scale to handle reasonable traffic loads. Interestingly, the analysis of selective flooding reveals major problems with traditional ad hoc networking techniques. Many current algorithms demonstrate shortcomings when dealing with bursty traffic, and current wireless hardware cannot handle ad hoc networking traffic in an efficient manner. These issues need to be addressed before ad hoc networking technology can become feasible for widespread use.

Routing messages between pairs of nodes is one of the most fundamental tasks in any distributed computing system. An Interval Routing Scheme (IRS) is a well-known, space-efficient routing strategy for routing messages in a network. In this scheme, each node of the network is assigned an integer label and each link at each node is labeled with an interval. The interval assigned to a link l at a node v indicates the set of destination addresses of the messages which should be forwarded through l at v. When studying interval routing schemes, there are two main problems to be considered: a) Which classes of networks do support a specific routing scheme? b) Assuming that a given network supports IRS, how good are the paths traversed by messages? The first problem is known as the characterization problem and has been studied for several types of IRS. In this thesis, we study the characterization problem for various schemes in which the labels assigned to the vertices are d-ary integer tuples (d-dimensional IRS) and the label assigned to each link of the network is a list of d 1-dimensional intervals. This is known as Multi-dimensional IRS (MIRS) and is an extension of the the original IRS. We completely characterize the class of network which support MIRS for linear (which has no cyclic intervals) and strict (which has no intervals assigned to a link at a node v containing the label of v) MIRS. In real networks usually the costs of links may vary over time (dynamic cost links). We also give a complete characterization for the class of networks which support a certain type of MIRS which routes all messages on shortest paths in a network with dynamic cost links. The main criterion used to measure the quality of routing (the second problem) is the length of routing paths. In this thesis we also investigate this problem for MIRS and prove two lower bounds on the length of the longest routing path. These are the only known general results for MIRS. Finally, we study the relationship between various types of MIRS and the problem of drawing a hypergraph. Using some of our results we prove a tight bound on the number of dimensions of the space needed to draw a hypergraph.

Wireless Mesh Networking is envisioned as an economically viable paradigm and a promising technology in providing wireless broadband services. The wireless mesh backbone consists of fixed mesh routers that interconnect different mesh clients to themselves and to the wireline backbone network. In order to approach the wireline servicing level and provide same or near QoS guarantees to different traffic flows, the wireless mesh backbone should be quality-of-service (QoS) aware. A key factor in designing protocols for a wireless mesh network (WMN) is to exploit its distinct characteristics, mainly immobility of mesh routers and less-constrained power consumption. In this work, we study the effect of varying the transmission power to achieve the required signal-to-interference noise ratio for each link and, at the same time, to maximize the number of simultaneously active links. We propose a QoS-aware routing framework by using transmission power control. The framework addresses both the link scheduling and QoS routing problems with a cross-layer design taking into consideration the spatial reuse of the network bandwidth. We formulate an optimization problem to find the optimal link schedule and use it as a fitness function in a genetic algorithm to find candidate routes. Using computer simulations, we show that by optimal power allocation the QoS constraints for the different traffic flows are met with more efficient bandwidth utilization than the minimum power allocations.

A VLSI chip can today contain hundreds of millions transistors and is expected to contain more than 1 billion transistors in the next decade. In order to handle this rapid growth in integration technology, the design procedure is therefore divided into a sequence of design steps. Circuit layout is the design step in which a physical realization of a circuit is obtained from its functional description. Global routing is one of the key subproblems of the circuit layout which involves finding an approximate path for the wires connecting the elements of the circuit without violating resource constraints. The global routing problem is NP-hard, therefore, heuristics capable of producing high quality routes with little computational effort are required as we move into the Deep Sub-Micron (DSM) regime. In this thesis, different approaches for global routing problem are first reviewed. The advantages and disadvantages of these approaches are also summarized. According to this literature review, several mathematical programming based global routing models are fully investigated. Quality of solution obtained by these models are then compared with traditional Maze routing technique. The experimental results show that the proposed model can optimize several global routing objectives simultaneously and effectively. Also, it is easy to incorporate new objectives into the proposed global routing model. To speedup the computation time of the proposed ILP based global router, several hierarchical methods are combined with the flat ILP based global routing approach. The experimental results indicate that the bottom-up global routing method can reduce the computation time effectively with a slight increase of maximum routing density. In addition to wire area, routability, and vias, performance and low power are also important goals in global routing, especially in deep submicron designs. Previous efforts that focused on power optimization for global routing are hindered by excessively long run times or the routing of a subset of the nets. Accordingly, a power efficient multi-pin global routing technique (PIRT) is proposed in this thesis. This integer linear programming based techniques strives to find a power efficient global routing solution. The results indicate that an average power savings as high as 32\% for the 130-nm technology can be achieved with no impact on the maximum chip frequency.