On the Rate of Convergence of a Distributed Asynchronous Routing Algorithm

Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We analyze a distributed asynchronous algorithm, proposed by Tsitsiklis 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 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.

Original languageEnglish (US)
Pages (from-to)1123-1129
Number of pages7
JournalIEEE Transactions on Automatic Control
Volume39
Issue number5
DOIs
StatePublished - May 1994

Fingerprint Dive into the research topics of 'On the Rate of Convergence of a Distributed Asynchronous Routing Algorithm'. Together they form a unique fingerprint.

Cite this