Network Routing Optimization: Theory and Practice

Networks such as the internee, corporate networks, and even social ones, are an integral part of today's society. The utility of the network depends in a fundamental way on the routing protocols that are used to transmit information from a point to another in a network. This thesis focuses on important routing issues in both the wired and the wireless domains. There are multiple objectives, at times conflicting, that one would like to optimize in a routing protocol such as the storage space necessary for the routing scheme, the bandwidth utilization or the amount of information aggregation permitted by the routing scheme. The first problem we will present is from the wireless domain, in which maximizing information aggregation is of foremost importance. We propose a simple randomized algorithm for routing information on a grid of sensors that allows for a high level data aggregation. Data aggregation is crucial given the severe energy constraints of the sensors. We prove that our routing scheme is a constant factor approximation (in expectation) to the optimum aggregation tree simultaneously for a class of aggregation functions. We also present a deterministic algorithm, which requires additional global information about the number of sensors present, and which provides a slightly improved constant factor approximation to all optimal aggregation trees considered. Next we study how to use routes that are as short as possible (i.e. have low stretch) while keeping routing tables small in the wired domain. The motivation here is scalability. We derive the specific space-stretch tradeoffs of routing in Bernoulli random graphs, and provide the first proof that stretch less than 3 can be obtained in conjunction with sublinear routing tables in this class of graphs. We also develop an efficient algorithm that finds the near-optimum space-stretch tradeoff for landmark-based schemes in any given network. Our algorithm produces routing tables that use no more than O(log n) more space than the optimum landmark-based scheme for achieving stretch s with L landmarks. This is a novel tool for obtaining near-optimum stretch-space tradeoffs for specific graphs. Finally, we address the placement of relay service agents (routelets) in the Internet to assist multipath transport protocols; these protocols are designed to achieve better network utilization and fairness by exploiting path diversity in the Internet. We identify three different routelet deployment scenarios, provide LP formulations for routelet placement in each of the scenarios, and prove that the placement problem is NP-complete in two of the scenarios. We provide rounding algorithms with provable properties for a subset of the scenarios, and compare their performance through simulations on several topologies of varying scales.