Distributed algorithms for efficient routing in computer communication networks

In this thesis, we discuss the design implications of compact routing algorithms on both wired and wireless networks. We begin by exploring algorithms for wireless ad-hoc networks that restrict control signaling in an effort to quantify and limit messaging complexity. We introduce Elliptic Demarcation of Information Transfer (EDIT) as an approach to limit the signaling within specific regions of the network as opposed to flooding all the nodes with control packets. We further explore the design space by learning from some of the drawbacks of this design and then describe a detailed approach that reaches farther in the goal of minimizing resources consumed by the routing plane. We present Automatic Incremental Routing (or AIR), as the unified framework that supports both unicast and multicast operations in the underlying routing structure. We verify that AIR provides correct unicast and multicast routing, and present simulation results comparing AIR with AODV, OLSR, MAODV and ODMRP in MANETs. The results from these simulation experiments, as well as from tests carried out in a small testbed running AIR in wireless routers, illustrate that AIR offers substantial performance advantages over traditional unicast and multicast routing protocols, even in the case of small networks.;We then describe our efforts at applying our algorithm design to wired networks. We begin by discussing the algorithm in the context of enterprise scale wired local area networks and demonstrate the scalability of our scheme in the face of a large enterprises. We then discuss applications of our algorithms in the context of routing in data centers by robustly routing in the face of virtual host mobility. We embrace the design decision of using DHTs to resolve the mapping between host identifiers and their locations, and apply the AIR framework to move away from the need to use link-state information. Our framework pushes the responsibility of searching for destinations to nodes in the network in such a way that neither the network nor any single node is burdened with the task of discovering routes. As a result, we reduce the state stored at each node and improve the latency compared to Ethernet, without flooding messages network-wide.;Lastly, we engage in a detailed analysis of our algorithm design in the context of wireless ad-hoc networks. We introduce and describe the conditions that allow us to realize a constant stretch routing algorithm. A constant stretch algorithm provides bounded path-lengths which in turn lends itself to providing guarantees of services that can run on top of such a scheme. We introduce the trade-offs of building such a scheme and prove its correctness. In this work, we begin by discussing the trade-offs involved in developing a distributed routing algorithm that balances different complexities efficiently. We model wireless networks as a particular class of graphs called Random Geometric Graphs (RGGs) as they best capture the characteristics of such networks. In RGGs each node/vertex of the graph is geometrically constrained such that links to other nodes exist only within a radius range. Besides, the RGGs posses certain characteristics that allow us to define the bounds of certain complexities in an elegant manner. The three key complexities that describe any compact routing algorithm are stretch, space complexity and messaging complexity. We define stretch as the ratio of the algorithmic path length to the shortest path in the network. Ideally, we would like stretch to be as close to 1 as possible. Space complexity describes the amount of information that can be fetched from a local cache to identify the shortest path within finite time. If the local cache contained the entire topology, the shortest path to a destination can be trivially computed by any variant of Dijkstra's algorithm in 0(n) time. Messaging complexity becomes important when the communication occurs over a broadcast medium. Collisions of messages are costly since they require retransmissions and incur significant delays. The lesser the number of signaling messages, the fewer such collisions. While it might be trivial to optimize any one criteria individually, optimizing all of them, cumulatively is certainly non-trivial. This is so because, any attempt at reducing space or message complexity increases stretch and the same holds for the reverse as well. (Abstract shortened by UMI.)...