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.