Approximations of Queue Dynamics and Their Application to Adaptive Routing in Computer Communication Networks

Various adaptive algorithms have been proposed for routing, flow and congestion control in packet-switched computer communication networks. In most of them, information on queue lengths, or equivalently, time delays, at various points in the network is required for proper adaptation. Since up-to-date information is not always available, these quantities must be estimated based on prior information. This paper presents approximations for the dynamic behavior of the queue which is used to yield the desired estimates of queue lengths. Based on the assumption of finite (but arbitrarily large) storage, a closed form expression for the evolution in time of the queue length distribution is obtained. From this expression various approximations for estimated queue length are extracted. A simple expression for the "relaxation time" of the queue is also deduced as a function of utilization factor and service time. The approximations are applied to a simple adaptive routing example in which packets are routed along the transmission path having the shortest estimated queue, based on delayed information.