On the computational complexity and effectiveness of N-hub shortest-path routing

ABSTRACT

In this paper, we study the computational complexity and effectiveness of a concept we term "N-hub Shortest-Path Routing" in IP networks. N-hub Shortest-Path Routing allows the ingress node of a routing domain to determine up to N intermediate nodes ("hubs") through which a packet will pass before reaching its final destination. This facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. Although this concept has been proposed in the past, this paper is the first to investigate it in depth. We apply N-hub Shortest-Path Routing to the problem of minimizing the maximum load in the network. We show that the resulting routing problem is NP-complete and hard to approximate. However, we propose efficient algorithms for solving it both in the online and the offline contexts. Our results show that N-hub Shortest-Path Routing can increase network utilization significantly even for N = 1. Hence, this routing paradigm should be considered as a powerful mechanism for future datagram routing in the Internet.

REFERENCES

• 1: Z. Wang , J. Crowcroft, Shortest path first with emergency exits, Proceedings of the ACM symposium on Communications architectures & protocols, p.166-176, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 2: J. Chen, P. Druschel, and D. Subramanian, "An efficient multipath forwarding method," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 1998, pp. 1418-1425.
• 3: J. Garcia-Luna-Aceves, S. Vutukury, and W. Zaumen, "A practical approach to minimizing delays in Internet routing protocols," in Proc. IEEE ICC, Vancouver, BC, Canada, Jun. 1999, pp. 479-483.
• 4: Srinivas Vutukury , J. J. Garcia-Luna-Aceves, A simple approximation to minimum-delay routing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.227-238, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 5: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 6: D. K. et al., "Traffic Engineering (TE) Extensions to OSPF Version 2," IETF RFC 3630, Sep. 2003.
• 7: S. B. et al., "An architecture for differentiated services," IETF RFC 2475, Dec. 1998,.
• 8: J. Postel, "Internet Protocol," IETF RFC 791, Sep. 1981.
• 9: S. M. Bellovin, Security problems in the TCP/IP protocol suite, ACM SIGCOMM Computer Communication Review, v.19 n.2, p.32-48, April 1, 1989 [doi>10.1145/378444.378449]
• 10: R. Govindan and H. Tangmunarunkit, "Heuristics for internet map discovery," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, pp. 1371-1380.
• 11: S. Deering , R. Hinden, Internet Protocol, Version 6 (IPv6) Specification, RFC Editor, 1998
• 12: C. Perkins, IP Encapsulation within IP, RFC Editor, 1996
• 13: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 14: Paul Francis , Ramesh Govindan, Flexible routing and addressing for a next generation IP, Proceedings of the conference on Communications architectures, protocols and applications, p.116-125, August 31-September 02, 1994, London, United Kingdom
• 15: I. Castineyra , N. Chiappa , M. Steenstrup, The Nimrod Routing Architecture, RFC Editor, 1996
• 16: M. Kodialam, T. V. Lakshman, and S. Sengupta, "Efficient and robust routing of highly variable traffic," in Proc. HotNets-III, Nov. 2004.
• 17: R. Zhang-Shen and N. McKeown, "Designing a predictable internet backbone network," in Proc. HotNets-III, Nov. 2004.
• 18: M. Kodialam, T. V. Lakshman, J. B. Orlin, and S. Sengupta, "Preconfiguring IP-over-optical networks to handle router failures and unpredictable traffic," in Proc. IEEE INFOCOM, Mar. 2006, pp. 1-12.
• 19: M. Kodialam, T. V. Lakshman, and S. Sengupta, "Maximum throughput routing of traffic in the hose model," in Proc. IEEE IN-FOCOM , Mar. 2006, pp. 1-11.
• 20: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 21: Stavros G. Kolliopoulos , Clifford Stein, Improved Approximation Algorithms for Unsplittable Flow Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.426, October 19-22, 1997
• 22: N. G. Y. Dinitz and M. Goemans, "On the single-source unsplittable flow problem," Combinatorica, vol. 19, pp. 17-41, 1999.
• 23: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 24: J. T. Havill and W. Mao, "Greedy online algorithms for routing permanent virtual circuits," Networks, vol. 34, pp. 136-153, 1999.
• 25: W. Mao and R. Simha, "Routing and scheduling file transfers in packet-switched networks," J. Comput. Inf., vol. 1, pp. 559-574, 1994.
• 26: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 27: R. M. Karp, "Online algorithms versus offline algorithms: How much is it worth to know the future?" Int. Computer Sci. Inst., Tech. Rep. TR-92-044, 1992.
• 28: E. W. Zegura, K. L. Calvert, and S. Bhattacharjee, "How to model an in-ternetwork," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 1996, vol. 2, pp. 594-602, IEEE.
• 29: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 30: M. Berkelaar, Lp_Solve Software. [Online]. Available: ftp.es.tue.nl/ pub/lp_solve
• 31: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 32: Ratul Mahajan , Neil Spring , David Wetherall , Tom Anderson, Inferring link weights using end-to-end measurements, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637237]
• 33: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 34: L. Khachiyan, "A polynomial time algorithm for linear programming," Docl. Akad. Nauk SSSR, vol. 244, pp. 1093-1096, 1979.
• 35: W. Hoeffding, "On the distribution of the number of successes of independent trials," Ann. Math. Stat., vol. 27, pp. 713-721, 1956.
• 36: H. Chernoff, "A measure of asymptotic efficiency for tests of a hypothesis based on the sums of observations," Ann. Math. Stat., vol. 23, pp. 493-509, 1952.
• 37: W. Hoeffding, "Probability inequalities for sums of bounded random variables," Amer. Stat. Assoc. J., vol. 58, pp. 13-30, 1963.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Performance

Keywords:
load balancing, routing