Hop-by-Hop Adaptive linking A Novel Approach for Finest routing

Sunkara Mounika, Md Amanatulla


Using Hop-by-Hop Adaptive linking for achieving finest routing is an unprecedented approach. And it is the first link-state routing solution carrying traffic through packet-switched networks. At each node, for every other node, the algorithm independently and iteratively updates the fraction of traffic destined to that leaves on each of its outgoing links. At each iteration, the updates are calculated based on the shortest path to each destination as determined by the marginal costs of the network’s links. The marginal link costs used to find the shortest paths are in turn obtained from link-state updates that are flooded through the network after each iteration. For stationary input traffic, we prove that our project converges to the routing assignment that minimizes the cost of the network. Furthermore, I observe that our technique is adaptive, automatically converging to the new optimal routing assignment for quasi-static network changes. I also report numerical and experimental evaluations to confirm our theoretical predictions, explore additional aspects of the solution, and outline a proof-of-concept implementation of proposal.


M. Wang, C. W. Tan, W. Xu, and A. Tang, “Cost of not splitting in routing: characterization and estimation,” IEEE/ACM Trans. Netw., vol. 19, no. 6, pp. 1849–1859, Dec. 2011.

R. Gallager, “A minimum delay routing algorithm using distributed computation,” IEEE Trans. Commun., vol. COM-25, no. 1, pp. 73–85,

Jan. 1977.

L. Fratta,M.Gerla, and L. Kleinrock, “The flow deviation method: An approach to store-and-forward communication network design,” Networks,

vol. 3, no. 2, pp. 97–133, 1973.

J. F. Kurose and K. W. Ross, Computer Networking: A Top-Down Approach, 5/E. New York, NY, USA: Addison-Wesley, 2010.

D. Bertsekas and E. Gafni, “Projected newton methods and optimization of multicommodity flows,” IEEE Trans. Autom. Control, vol. AC-28, no. 12, pp. 1090–1096, Dec. 1983.

D. Xu, M. Chiang, and J. Rexford, “Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering,” IEEE/ACMTrans.

Netw., vol. 19, no. 6, pp. 1717–1730, Dec. 2011.

A. Sridharan, R. Guerin, and C. Diot, “Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks,” IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 234–247, Apr. 2005.

S. Srivastava, G. Agrawal, M. Pioro, and D. Medhi, “Determining link weight system under various objectives for OSPF networks using a lagrangian relaxation-based approach,” IEEE Trans. Netw. Service Manag., vol. 2, no. 1, pp. 9–18, Nov. 2005.

Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg, “Fast accurate computation of large-scale IP traffic matrices from link loads,” in Proc. ACM SIGMETRICS, New York, NY, USA, 2003, pp. 206–217.

D. Awduche, “MPLS and traffic engineering in IP networks,” IEEE Commun. Mag., vol. 37, no. 12, pp. 42–47, Dec. 1999.

A. Elwalid, C. Jin, S. Low, and I. Widjaja, “MATE: MPLS adaptive traffic engineering,” in Proc. 20th Annu. IEEE INFOCOM, 2001, vol.

C. E. Agnew, “On quadratic adaptive routing algorithms,” Commun. ACM, vol. 19, no. 1, pp. 18–22, Jan. 1976.

M. Kodialam, T. V. Lakshman, J. Orlin, and S. Sengupta, “Oblivious

routing of highly variable traffic in service overlays and IP backbones,”

IEEE/ACM Trans. Netw., vol. 17, no. 2, pp. 459–472, Apr. 2009.

S. Boyd and L. Vandenberghe, Convex Optimization. NewYork,NY,

USA: Cambridge Univ. Press, 2004.

Full Text: PDF [Full Text]


  • There are currently no refbacks.

Copyright © 2013, All rights reserved.| ijseat.com

Creative Commons License
International Journal of Science Engineering and Advance Technology is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJSEat , Permissions beyond the scope of this license may be available at http://creativecommons.org/licenses/by/3.0/deed.en_GB.