Content area
Abstract
This dissertation presents a new approach to routing in computer networks such as the Internet. Future computer networks are expected to carry bursty traffic. Shortest-path routing protocols have the disadvantage of causing bottlenecks due to their inherent single-path routing. That is, the designated shortest path between a source and a destination may become highly congested even when there exist many other paths with low utilization between them. This congestion may trigger the loss of valuable data packets due to buffer overflow at some node along the shortest path.
We propose a family of multi-path routing schemes that distribute traffic over the whole network via bounded randomization; therefore, they remove bottlenecks and consequently improve network performance. Our new schemes provide multiple paths of unequal cost to each source-destination pair. First, each of our routing schemes selects a set of nodes from the entire network nodes. For each data packet to be sent from a source s to a destination d, the proposed, routing protocol randomly chooses an intermediate node e from a selected set of network nodes, and routes the data packet along a shortest path from s to e. Then, it routes the data packet via a shortest path from e to d. Intuitively, we would expect that this increases the effective bandwidth between each source-destination pair. This dissertation implements and analyzes algorithms for these routing schemes.
Our simulation results indicate that these load-balanced routing protocols distribute data traffic evenly over the whole network, make better use of network resources than single path routing and, in consequence, significantly improve network performance with respect to throughput, average delay, packet loss and link utilization. Moreover, the implementation of our routing schemes require only a simple extension to any shortest-path routing protocol.
