Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks

@article{toc84-bertsekas-Second, abstract = {We propose a class of algorithms for finding an optimal quasi-static routing in a communication network. The algorithms are based on Gallager's method [1] and provide methods for iteratively updating the routing table entries of each node in a manner that guarantees convergence to a minimum delay routing. Their main feature is that they utilize second derivatives of the objective function and may be viewed as approximations to a constrained version of Newton's method. The use of second derivatives results in improved speed of convergence and automatic stepsize scaling with respect to level of traffic input. These advantages are of crucial importance for the practical implementation of the algorithm using distributed computation in an environment where input traffic statistics gradually change.}, author = {Bertsekas, D. and Gafni, E. and Gallager, R. }, citeulike-article-id = {760349}, journal = {IEEE Transactions on Communications}, keywords = {delay, minimum}, number = {8}, pages = {911--919}, posted-at = {2006-07-15 21:46:35}, priority = {2}, title = {Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=1096159}, volume = {32}, year = {1984} }

TY - JOUR ID - toc84-bertsekas-Second L3 - citeulike-article-id:760349 TI - Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks JF - IEEE Transactions on Communications VL - 32 IS - 8 SP - 911 EP - 919 N2 - We propose a class of algorithms for finding an optimal quasi-static routing in a communication network. The algorithms are based on Gallager's method [1] and provide methods for iteratively updating the routing table entries of each node in a manner that guarantees convergence to a minimum delay routing. Their main feature is that they utilize second derivatives of the objective function and may be viewed as approximations to a constrained version of Newton's method. The use of second derivatives results in improved speed of convergence and automatic stepsize scaling with respect to level of traffic input. These advantages are of crucial importance for the practical implementation of the algorithm using distributed computation in an environment where input traffic statistics gradually change. KW - delay KW - minimum AU - Bertsekas, D AU - Gafni, E AU - Gallager, R PY - 1984/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1096159 ER -