ON THE RATE OF CONVERGENCE OF A DISTRIBUTED ASYNCHRONOUS ROUTING ALGORITHM

被引：9
作者：
LUO, ZQ [1 ]
TSENG, P [1 ]
机构：
[1] UNIV WASHINGTON,DEPT MATH,SEATTLE,WA 98195
来源：
IEEE TRANSACTIONS ON AUTOMATIC CONTROL | 1994年 / 39卷 / 05期
关键词：
D O I：
10.1109/9.284908
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：1123 / 1129
页数：7
相关论文
共 24 条
[1]  
Bertsekas D., 1987, DATA NETWORKS
[2]  
Bertsekas D.P., 1989, PARALLEL DISTRIBUTED
[3]   PROJECTED NEWTON METHODS AND OPTIMIZATION OF MULTICOMMODITY FLOWS [J].
BERTSEKAS, DP ;
GAFNI, EM .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1983, 28 (12) :1090-1096
[4]  
BERTSEKAS DP, 1982, MATH PROGRAM STUD, V17, P139
[5]   2ND DERIVATIVE ALGORITHMS FOR MINIMUM DELAY DISTRIBUTED ROUTING IN NETWORKS [J].
BERTSEKAS, DP ;
GAFNI, EM ;
GALLAGER, RG .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1984, 32 (08) :911-919
[6]  
BERTSEKAS DP, 1980, 5TH P INT C COMP COM, P71
[7]   OPTIMAL ROUTING IN A PACKET-SWITCHED COMPUTER NETWORK [J].
CANTOR, DG ;
GERLA, M .
IEEE TRANSACTIONS ON COMPUTERS, 1974, C 23 (10) :1062-1069
[8]   CONTROL AND OPTIMIZATION METHODS IN COMMUNICATION-NETWORK PROBLEMS [J].
EPHREMIDES, A ;
VERDU, S .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1989, 34 (09) :930-942
[9]  
Fratta L., 1973, NETWORKS, V3, P97, DOI DOI 10.1002/NET.3230030202
[10]   2-METRIC PROJECTION METHODS FOR CONSTRAINED OPTIMIZATION [J].
GAFNI, EM ;
BERTSEKAS, DP .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1984, 22 (06) :936-964
123