ACM Home
SIGMETRICS 2001 / Performance 2001 Home
Call for Papers
Organizing Committee
Technical Program Committee
Registration Information
Advanced Technical Program
Travel Support for Students
Travel Related Information
Other Links of Interest


SIGMETRICS 2001 / Performance 2001

Dynamic Multi-path Routing: Asymptotic Approximation and Simulations

Xun Su
Gustavo de Veciana

Department of Electrical and Computer Engineering, University of Texas, Austin

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.

[Last updated Fri Mar 23 2001]