|
SIGMETRICS 2001 / Performance 2001Dynamic Multi-path Routing: Asymptotic Approximation and Simulations |
| Authors |
|
Xun Su Gustavo de Veciana
Department of Electrical and Computer Engineering,
University of Texas, Austin
|
| Abstract |
|
In this paper we study the dynamic multi-path routing problem.
We focus on an operating regime where traffic flows
arrive at and depart from the network in a bursty fashion, and where
the delays involved in link state
advertisement may lead to ``synchronization'' effects that adversely
impact the performance of dynamic single-path routing schemes.
We start by analyzing a simple network of parallel links, where the goal is to minimize the average increase in network congestion on the time scale of link state advertisements. We consider an asymptotic regime leading to an optimization problem permitting closed-form analysis of the number of links over which dynamic multi-path routing should be conducted. Based on our analytical result we examine three types of dynamic routing schemes, and identify a robust policy, i.e., routing the traffic to a set of links with loads within a factor of the least loaded, that exhibits robust performance. We then propose a similar policy for mesh networks and show by simulation some of its desirable properties. The main results suggest that our proposal would provide significant performance improvement for high speed networks carrying bursty traffic flows. |