Load-Balanced Routing via Bounded Randomization
Sangman Bak, Jorge A. Cobb · 2003
Future computer networks are expected to carry bursty traffic. Shortest-path routing protocols have the disadvantage of causing bottlenecks due to their single-path routing. That is, the shortest path between a source and a destination may become highly congested even when many other paths have low utilization. We propose a routing scheme that distributes traffic over the whole network via bounded randomization; therefore, it removes bottlenecks and increases network throughput. For each data message 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 message along the shortest path from s to e. Then, it routes the data message via the shortest path from e to d. Intuitively, we would expect that this increases the effective bandwidth between each pair of nodes. Our simulation results indicate that this load-balanced routing protocol distributes traffic evenly over the whole network and, in consequence, increases network throughput.