ON THE RATE OF CONVERGENCE OF A DISTRIBUTED ASYNCHRONOUS ROUTING ALGORITHM

We analyze a distributed asynchronous algorithm, proposed by Tsitsikli s and Bertsekas, 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 converg es 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 explic it estimate of the convergence ratio in terms of the network parameter s.