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 withKoutgoing 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 theKqueues, we find that the average delay for the dynamic system is better by a factor ofK.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 168 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.