Optimal dynamic routing in communication networks with continuous traffic

New characterizations of optimal state-dependent routing strategies are obtained for the continuous traffic network model proposed by A. Segall for linear cost with unity weighting at each node and for constant inputs. The concept of flow relaxation is introduced and is used to transform the optimal routing problem into an initial flow optimization problem with convex cost and linear constraints. Three algorithms are given for open-loop computation of the optimal initial flow. The first is a simple iterative algorithm based on gradient descent with bending and it is well suited for decentralized computation. The second algorithm reduces the problem to a series of max-flow problems and it computes the exact optimal initial flow in O(|N|4) computations where |N| is the number of nodes in the network. The third algorithm is based on a search for successive bottlenecks in the network.