On the rate of convergence of a distributed asynchronous routing algorithm

We analyze a distributed asynchronous algorithm, proposed by Tsitsiklis and Bertsekas (1986), for optimal routing in a virtual-circuit data network. We show that, under a strict convexity assumption on the link delay functions, the sequence of routings generated by the algorithm converges in the space of path flows and the convergence rate is linear. Our analysis is based on estimating the distance from a routing to the set of optimal routings and, for the synchronous case, it gives an explicit estimate of the convergence ratio in terms of the network parameters