APPROXIMATIONS OF QUEUE DYNAMICS AND THEIR APPLICATION TO ADAPTIVE ROUTING IN COMPUTER-COMMUNICATION NETWORKS

被引:17
作者
STERN, TE
机构
[1] Department of Electrical Engineering and Computer Science, Columbia University, New York
关键词
D O I
10.1109/TCOM.1979.1094546
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
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 tfhoer dynamic behavior of the M/M/1 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. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.
引用
收藏
页码:1331 / 1335
页数:5
相关论文
共 9 条