Title :
Time complexity of a path formulated optimal routing algorithm
Author :
Antonio, John K. ; Tsai, Wei K. ; Huang, G.M.
Author_Institution :
Sch. of Electr. Eng., Purdue Univ., West Lafayette, IN, USA
fDate :
2/1/1994 12:00:00 AM
Abstract :
A detailed analysis of convergence rate is presented for an iterative path formulated optimal routing algorithm. In particular, it is quantified, analytically, how the convergence rate changes as the number of nodes in the underlying graph increases. The analysis is motivated by a particular path formulated gradient projection algorithm that has demonstrated excellent convergence rate properties through extensive numerical studies. The analytical result proven in this note is that the number of iterations for convergence depends on the number of nodes only through the network diameter
Keywords :
computational complexity; convergence of numerical methods; data communication systems; graph theory; iterative methods; optimisation; telecommunication network routing; convergence rate; gradient projection algorithm; iterative path formulated optimal routing algorithm; time complexity; Algorithm design and analysis; Convergence of numerical methods; Delay estimation; Equations; Iterative algorithms; Performance evaluation; Projection algorithms; Routing; Telecommunication traffic; Traffic control;
Journal_Title :
Automatic Control, IEEE Transactions on
