Dynamic multicommodity flow schedules

Abstract

Some new results in the scheduling of dynamic multicommodity flows in data communication networks are presented. A new performance measure for effective delivery of backlogged data to their destinations is defined and the solution to the resulting delivery problem is obtained through a sequential linear optimization methodology. Properties of an optimal dynamic multicommodity flow schedule are studied in detail, taking advantage where possible of the linear programming formulation. The special case of the delivery problem in a single destination network also is analyzed. Application of the results to stochastic delivery problems in which the data inputs to the network are modelled as Poisson processes is addressed, and a new dynamic data communication network analysis is presented. Finally, the delivery problem on networks with capacitated links and with traversal delays is considered and some new results obtained