Martingale dynamics and optimal routing in a network

摘要

In this paper, we consider a dynamic routing problem in a store-and-forward computer-communication network which consists of l parallel channels connected between the source and the destination. We prove that if messages arrive at the network in accordance with a Poisson process and all nodes have an exponential service rate, then the routing strategy that minimizes the total expected time in transmitting all messages that arrive before T>0 is to route the arriving message to the channel along which the sum of all queue sizes is minimum. Techniques of martingale and dynamic programming are used in obtaining the result.