On the rate of convergence of a distributed asynchronous routing algorithm

Author

Luo, Zhi-Quan ; Tseng, Paul

Author_Institution

Dept. of Electr. & Comput. Eng., McMaster Univ., Hamilton, Ont., Canada

Volume

39

Issue

5

fYear

1994

fDate

5/1/1994 12:00:00 AM

Firstpage

1123

Lastpage

1129

Abstract

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

Keywords

data communication systems; delays; optimisation; telecommunication network routing; convergence rate; convergence ratio; distributed asynchronous routing algorithm; link delay functions; optimal routing; routing sequence; strict convexity assumption; virtual-circuit data network; Algorithm design and analysis; Context modeling; Convergence; Delay effects; Delay estimation; Mathematical model; Performance analysis; Routing; Stochastic processes; Telecommunication traffic;

fLanguage

English

Journal_Title

Automatic Control, IEEE Transactions on

Publisher

ieee

ISSN

0018-9286

Type

jour

DOI

10.1109/9.284908

Filename

284908