Skip to main content
SpringerLink
Log in

Increasing Internet Capacity Using Local Search

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to the physical lengths of the links, but often the main goal is to avoid congestion, i.e. overloading of links, and the standard heuristic recommended by Cisco (a major router vendor) is to make the weight of a link inversely proportional to its capacity.

We study the problem of optimizing OSPF weights for a given a set of projected demands so as to avoid congestion. We show this problem is NP-hard, even for approximation, and propose a local search heuristic to solve it. We also provide worst-case results about the performance of OSPF routing vs. an optimal multi-commodity flow routing. Our numerical experiments compare the results obtained with our local search heuristic to the optimal multi-commodity flow routing, as well as simple and commonly used heuristics for setting the weights. Experiments were done with a proposed next-generation AT&T WorldNet backbone as well as synthetic internetworks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E.H.L. Aarts and J.K. Lenstra, Local Search in Combinatorial Optimization. Discrete Mathematics and Optimization Wiley-Interscience: Chichester, England, 1997.

    Google Scholar 

  2. D. Applegate and M. Thorup, “Load optimal mpls routing with n+ mlabels,” in Proc. 22nd IEEE Conf. on Computer Communications (INFOCOM), (to appear), 2003.

  3. R. Battiti and G. Tecchiolli, “The reactive tabu search,” ORSA Journal on Computing, vol. 6, no. 2, pp. 126–140, 1994.

    Google Scholar 

  4. W. Ben-Ameur and E. Gourdin, “Internet routing and related topology issues,” Technical report, France Telecom R&D, 2001.

  5. W. Ben-Ameur, N. Michel, E. Gourdin, and B. Liau, “Routing strategies for IP networks,” Telektronikk, vols. 2/3, pp. 145–158, 2001.

    Google Scholar 

  6. A. Bley, M. Grötchel, and R. Wessäly, “Design of broadband virtual private networks: Model and heuristics for the B-WiN,” in Proc. DIMACS Workshop on Robust Communication Networks and Survivability, AMSDIMACS Series, vol. 53, 1998, pp. 1–16.

    Google Scholar 

  7. L.S. Buriol, M.G.C. Resende, C.C. Ribeiro, and M. Thorup, “A memetic algorithms for OSPF routing,” in Proceedings of the 6th INFORMS Telecom, 2002, pp. 187–188.

  8. K. Calvert, M. Doar, and E.W. Zegura, “Modeling internet topology,” IEEE Communications Magazine, vol. 35, no. 6, pp. 160–163, 1997.

    Article  Google Scholar 

  9. W. Carlton and J. Barnes, “A note on hashing functions and tabu search algorithms,” European Journal of Operational Research, vol. 95, pp. 237–239, 1996.

    Article  Google Scholar 

  10. J.L. Carter and M.N. Wegman, “Universal classes of hash functions,” Jounal of Computer and System Sciences, vol. 18, pp. 143–154, 1979.

    Article  Google Scholar 

  11. Cisco, “Configuring OSPF,” 1997, Documentation at http://www.cisco.com/[4]univercd/cc/td/doc/product/ software/ios113ed/113ed cr/np1 c/1cospf.htm.

  12. S. Cook, “The complexity of theorem proving procedures,” in Proc. 3rd ACMSymp. on Theory of Computing (STOC), 1971, pp. 151–158.

  13. M. Dietzfelbinger, “Universal hashing and k-wise independent random variables via integer arithmetic without primes,” in Proc. 13th Symp. on Theoretical Aspects of Computer Science (STACS), LNCS vol. 1046, Springer, 1996, pp. 569–580.

    Google Scholar 

  14. M. Ericsson, M. Resende, and P. Pardalos, “A genetic algorithm for the weight setting problem in OSPF routing,” 2001, To appear in J. Combinatorial Optimization in 2002.

  15. B. Fortz, J. Rexford, and M. Thorup, “Traffic engineering with traditional IP routing protocols,” IEEE Communications Magazine, vol. 40, no. 10, pp. 118–124, 2002.

    Article  Google Scholar 

  16. B. Fortz and M. Thorup, “Increasing internet capacity using local search,” Technical Report IS-MG 2000/21, Université Libre de Bruxelles, 2000a. http://smg.ulb.ac.be/Preprints/Fortz00 21.html.

  17. B. Fortz and M. Thorup, “Internet traffic engineering by optimizing OSPF weights,” in Proc. 19th IEEE Conf. on Computer Communications (INFOCOM), 2000b, pp. 519–528.

  18. B. Fortz and M. Thorup, “Optimizing OSPF/IS-IS weights in a changing world,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 4, pp. 756–767, 2002.

    Article  Google Scholar 

  19. D. Frigioni, M. Ioffreda, U. Nanni, and G. Pasqualone, “Experimental analysis of dynamic algorithms for the single-source shortest path problem,” ACM Jounal of Experimental Algorithmics, vol. 3, no. 5, 1998.

  20. F. Glover, “Future paths for integer programming and links to artificial intelligence,” Computers & Operations Research, vol. 13, pp. 533–549, 1986.

    Google Scholar 

  21. F. Glover, “Tabu search-Part I,” ORSA Journal on Computing, vol. 1, no. 3, pp. 190–206, 1989.

    Google Scholar 

  22. F. Glover, “Tabu search-Part II,” ORSA Journal on Computing, vol. 2, no. 1, pp. 4–32, 1990.

    Google Scholar 

  23. F. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997.

  24. J. Hâstad, “Some optimal inapproximability results,” Journal of the ACM, vol. 48, no. 4, pp. 798–859, 2001.

    Article  Google Scholar 

  25. D.E. Knuth, “The Art of Computer Programming III: Sorting and Searching,” Addison-Wesley: Reading, MA, 1973.

    Google Scholar 

  26. F. Lin and J. Wang, “Minimax open shortest path first routing algorithms in networks supporing the smds services,” in Proc. IEEE International Conference on Communications (ICC), vol. 2, 1993, pp. 666–670.

    Article  Google Scholar 

  27. D. Mitra and K. Ramakrishnan, “A case study of multiservice, multipriority traffic engineering design for data networks,” in Proc. IEEE GLOBECOM, 1999, pp. 1077–1083.

  28. J.T. Moy, OSPF: Anatomy of an Internet Routing Protocal, Addison-Wesley, 1999.

  29. G. Ramalingam and T. Reps, “An incremental algorithm for a generalization of the shortest-path problem,” Jounal of Algorithms, vol. 21, no. 2, pp. 267–305, 1996.

    Article  Google Scholar 

  30. M. Rodrigues and K. Ramakrishnan, “Optimal routing in data networks,” Presentation at International Telecommunications Symposium (ITS), Rio de Genero, Brazil, 1994.

  31. E.C. Rosen, A. Viswanathan, and R. Callon, “Multiprotocol label switching architecture,” Network Working Group, Internet Draft (work in progress), 1999. http://search.ietf.org/internet-drafts/draft-ietf-mpls-arch-05.txt.

  32. M. Roughan and M. Thorup, “Avoiding ties in shortest path first routing,” Technical report, AT&T Labs-Research, 2002.

  33. Sprint, “Sprint IP backbone network and MPLS,” 2002, White Paper http://www.sprintbiz.com/resource library/resources/SprintCiscoMPLS.pdf.

  34. M. Thorup, “Even strongly universal hashing is pretty fast,” in Proc. 11th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2000, pp. 496–497.

  35. B.M. Waxman, “Routing of multipoint connections,” IEEE Jour. Selected Areas in Communications (Special Issue on Broadband Packet Communications), vol. 6, no. 9, pp. 1617–1622, 1988.

    Google Scholar 

  36. D.L. Woodruff and E. Zemel, “Hashing vectors for tabu search,” Annals of Operations Research, vol. 41, pp. 123–137, 1993.

    Google Scholar 

  37. X. Xiao, A. Hannan, B. Bailey, and L. Ni, “Traffic engineering with MPLS in the Internet,” IEEE Network Magazine, vol. 14, no. 2, pp. 28–33, 2000.

    Google Scholar 

  38. E.W. Zegura, “GT-ITM: Georgia tech internetwork topology models (software),” 1996. http://www.cc.gatech. edu/fac/Ellen.Zegura/gt-itm/gt-itm.tar.gz.

  39. E.W. Zegura, K.L. Calvert, and S. Bhattacharjee, “How to model an internetwork,” in Proc. 15th IEEE Conf. on Computer Communications (INFOCOM), 1996, pp. 594–602.

  40. A.L. Zobrist and F.R. Carlson, Jr., “Detection of combined occurrences,” Comm. ACM, vol. 20, no. 1, pp. 31–35, 1977.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut d'Administration et de Gestion, Université, Catholique de Louvain, Louvain-la-Neuve, Belgium

    Bernard Fortz & Mikkel Thorup

Authors
  1. Bernard Fortz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mikkel Thorup
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fortz, B., Thorup, M. Increasing Internet Capacity Using Local Search. Computational Optimization and Applications 29, 13–48 (2004). https://doi.org/10.1023/B:COAP.0000039487.35027.02

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:COAP.0000039487.35027.02

Search

Navigation