A Maximal Flow Approach to Dynamic Routing in Communication Networks

摘要

This work presents a new approach for building the feedback solution for the minimum delay dynamic message routing problem for single destination networks. The approach fully exploits the special structure of the constraint matrices obtained in the dynamic state space model suggested in previous works, by transforming every linear program arising from the necessary conditions, into a maximal weighted flow problem. Taking advantage of several properties concerning the networks corresponding to the linear programming problems, all theorems regarding certain simplifying characteristics of the feedback solution that apply in the case of single-destination networks with all unity weightings in the cost functional are reproved in a simplified and more straightforward manner. A compact algorithm for the construction of the feedback solution is presented, the algorithm being implementable on networks of reasonable size. A method for obtaining all solutions of the linear programming problems required by the algorithm, based on the application of linear programming techniques in networks is provided. The method is implemented by a computer program and several examples are run to test its applicability.