An optimal control approach to decentralized dynamic virtual circuit routing in computer networks

The problem of virtual circuit routing in data communication networks under nonstationary conditions is considered. A state variable modeling approach is adopted to describe the dynamic behavior of the possible paths for the virtual circuit through the network. The state model is developed by representing each link in a path as a set of nonlinear differential equations describing the dynamics of the virtual circuit and the network traffic in terms of time-varying mean quantities. An optimal control problem is formulated to determine the virtual circuit routing path which minimizes the number of packets in the network. The solution of the optimal control problem by Hamilton-Jacobi arguments is discussed leading to a threshold routing policy which can be implemented in a decentralized fashion. The performance of the routing algorithm is studied under both steady-state and nonstationary conditions, and its superiority over the performance of previous schemes in a dynamic load environment is demonstrated