A Basic Dynamic Routing Problem and Diffusion

Abstract

Diffusion theory has sometimes been successful in providing excellent approximate solutions to difficult queueing problems. Here we explore whether such methods can be used to analyze a basic dynamic routing strategy associated with a single idealized node in a data network. We analyze a dynamic routing policy where messages, or packets, that arrive at a certain node are routed to leave the node on the link having the shorter queue. In the model, message or packet arrivals are Poisson and the service time is exponentially distributed. We explore a heavy traffic diffusion method and we also discuss the limitations of an ad hoc approach to applying diffusion. For a node with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</tex> outgoing queues we find, under the assumption of heavy traffic, the optimum dynamic strategy, in the sense of minimizing the average delay. When this optimum dynamic strategy is compared to a static strategy where the outgoing traffic is split among the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</tex> queues, we find that the average delay for the dynamic system is better by a factor of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</tex> .