HIERARCHICAL LOAD-BALANCED ROUTING VIA BOUNDED RANDOMIZATION BASED ON DESTINATION NODE

摘要

The purpose of routing protocols in a computer network is to maximize network throughput. Popular 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. In this paper, we propose a routing scheme for hierarchically structured computer networks such as Internet. The new hierarchical routing algorithm, which we call the Hierarchical Load-Balanced Routing (HLBR), randomly balances traffic load via unequal paths over the whole network; 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 chooses randomly each of three intermediate nodes from a selected set of network nodes, and routes the data message along a path from s through the three intermediate nodes to d. This increases the effective bandwidth between each pair of nodes.