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,
implementing our routing schemes require only a simple extension to any
shortest-path routing protocol.