The Estimation of Delay Gradients for Purposes of Routing in Data-Communication Networks

摘要

The derivatives with respect to message flow of the total delay accumulated per unit time on each link in a Data-Communication network have been shown to be fundamental quantities in the solution of the routing problem. Casting the problem of estimating these delay gradients in a queueing theory framework, and making no statistical assumptions other than stationarity, we propose three algorithms that process the record of arrivals and departures of a single-server queue to derive an estimate for the derivative, with respect to arrival rate, of the total delay accumulated per unit time. Through simulation and analysis we show that all three algorithms are asymptotically unbiased and efficient for M/D/1 queues. By simulation of other queues we investigate the relative robustness of the three procedures. Finally, through examination of the storage and computational requirements we identify a single most promising algorithm. (Author)