An Optimal Control Approach to Dynamic Routing in Data Communication Networks. Part I. Principles

Abstract : A continuous state space model for the problem of dynamic routing in data communication networks has been recently proposed. In this paper we present an algorithm for finding the feedback solution to the associated linear optimal control problem with linear state and control variable inequality constraints when the inputs are assumed to be constant in time. The Constructive Dynamic Programming Algorithm, as it is called, employs a combination of necessary conditions, dynamic programming and linear programming to construct a set of convex polyhedral cones which cover the admissible state space with optimal controls. Due to several complicating features which appear in the general case the algorithms is presented in a conceptual form which may serve as a framework for the development of numerical schemes for special situations. In this vein the authors present in a forthcoming paper the case of single destination network problems with all equal weightings in the cost functional.