A Minimum Delay Routing Algorithm Using Distributed Computation Export

@article{Gallager1977, abstract = {An algorithm is defined for establishing routing tables in the individual nodes of a data network. The routing table at a node<tex>i</tex>specifies, for each other node<tex>j</tex>, what fraction of the traffic destined for node<tex>j</tex>should leave node<tex>i</tex>on each of the links emanating from node<tex>i</tex>. The algorithm is applied independently at each node and successively updates the routing table at that node based on information communicated between adjacent nodes about the marginal delay to each destination. For stationary input traffic statistics, the average delay per message through the network converges, with successive updates of the routing tables, to the minimum average delay over all routing assignments. The algorithm has the additional property that the traffic to each destination is guaranteed to be loop free at each iteration of the algorithm. In addition, a new global convergence theorem for noncontinuous iteration algorithms is developed.}, author = {Gallager, R.}, citeulike-article-id = {760348}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1093711}, journal = {IEEE Transactions on Communications}, number = {1}, pages = {73--85}, posted-at = {2009-06-28 00:25:55}, priority = {2}, title = {A Minimum Delay Routing Algorithm Using Distributed Computation}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1093711}, volume = {25}, year = {1977} }

TY - JOUR ID - Gallager1977 L3 - citeulike-article-id:760348 N2 - An algorithm is defined for establishing routing tables in the individual nodes of a data network. The routing table at a node<tex>i</tex>specifies, for each other node<tex>j</tex>, what fraction of the traffic destined for node<tex>j</tex>should leave node<tex>i</tex>on each of the links emanating from node<tex>i</tex>. The algorithm is applied independently at each node and successively updates the routing table at that node based on information communicated between adjacent nodes about the marginal delay to each destination. For stationary input traffic statistics, the average delay per message through the network converges, with successive updates of the routing tables, to the minimum average delay over all routing assignments. The algorithm has the additional property that the traffic to each destination is guaranteed to be loop free at each iteration of the algorithm. In addition, a new global convergence theorem for noncontinuous iteration algorithms is developed. IS - 1 JF - IEEE Transactions on Communications EP - 85 TI - A Minimum Delay Routing Algorithm Using Distributed Computation VL - 25 SP - 73 AU - Gallager, R PY - 1977/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1093711 ER -