Volume 3 : Number 2 : Paper 1 |
|
December 2000 Special Issue of Best Papers presented at CLEI'99. Asuncion
|
Title:
Performance Evaluation of Load-Balanced Routing via Bounded Randomization
Authors and Affiliations:
Ernst L. Leiss, Department of Computer Science, University of Houston, TX 77204, USA
Jorge A. Cobb, Department of Computer Science, University of Texas at Dallas, Dallas, TX 75803-0688, USA
Sangman Bak, Korea Telecom Telecommunications Network Laboratory, Jonmin-Dong, Yusung-Gu, Daejon, South Korea
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 consequence, 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.
|
Received December 1999, Revised February 2001
Full paper, 26 pages
[
PDF, 767 Kb ]
|
|
|
|
