A Numerical Study of Two Measures of Delay for Network Routing

摘要

This work presents computational results relating to the solution of convex multicommodity network flow problems by using an algorithm developed by D. P. Bertsekas from the ideas of Gallagher's method for distributed optimization of delay in data communication networks and gradient projection ideas from nonlinear programming. This algorithm is described and results are given for two measures of 'delay' in the network. In the first case, the formula for delay was based on the expression for queuing delay in M/M/1 queues suggested by Kleinrock. Here several versions of the algorithm (including with and without line search) are discussed. In the second case, the algorithm is applied to the dual problem in an approximation scheme based on a method of multipliers with exponential penalty function due to Kort and Bertsekas. Here the measure of delay being minimized is the largest link utilization in the network. Finally the two measures of delay are compared. In the examples we find that a fairly good solution to each of the problems may be found near the optimal point for the other problem.