Performance Evaluation of Load-Balanced Routing via Bounded Randomization

Abstract

Future computer networks are expected to carry bursty traffic. Shortest -path routing protocols such as OSPF and RIP have t he disadvantage of causing bottlenecks due to their inherent single -path routing. That is, the uniformly selected shortest path between a source and a destination may become highly congested even when many other paths have low utilization. We propose a family of routing schemes that distribute data traffic over the whole network via bounded randomization; in this way, they remove bottlenecks and consequently improve network performance. For each data message to be sent from a source s to a destination d, each of the proposed routing protocols randomly choose an intermediate node e from a selected set of network nodes, and routes the data message along a shortest path from s to e. Then, it routes the data message via a shortest path from e to d. Intuitively, we would expect that this increase the effective bandwidth between each source -destination pair. Our simulation results indicate that the family of proposed load -balanced routing protocols distribute traffic evenly over the whole network and , in consequenc e, increases network performance with respect to throughput, message loss, message delay and link utilization. Moreover, implementing our scheme requires only a simple extension to any shortest-path routing protocol.