Bandwidth guaranteed routing with fast restoration against link and node failures

ABSTRACT

An important feature of MPLS networks is local restoration where detour paths are set-up a priori. The detour is such that failed links or nodes can be bypassed locally from the first node that is upstream from the failures. This local bypass activation from the first detection point for failures permits much faster recovery than end-to-end path based mechanisms that require failure information to propagate to the network edges. However, local restoration of bandwidth guaranteed connections can be expensive in the additional network capacity needed. Hence, it is important to minimize and share restoration capacity. The problem of routing with local restoration requirements has been studied previously in a dynamic on-line setting. However, there are no satisfactory algorithms for the problem of preprovisioning fast restorable connections when the aggregate traffic demands are known (as would be the case when a set of routers are to be interconnected over an optical network or for pre-provisioned ATM over MPLS overlays). The contribution of this paper is a fast combinatorial approximation algorithm for maximizing throughput when the routed traffic is required to be locally restorable. To the best of our knowledge, this is the first combinatorial algorithm for the problem with a performance guarantee. Our algorithm is a Fully Polynomial Time Approximation Scheme (FPTAS), i.e., for any given Ε > 0, it guarantees (1 + Ε)-factor closeness to the optimal solution, and runs in time polynomial in the network size and 1/Ε. We compare the throughput of locally restorable routing with that of unprotected routing and 1+1-dedicated path protection on actual US/European ISP topologies taken from the Rocketfuel project [14].

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: D. Awduche and Y. Rekhter, "Multiprotocol lambda switching: Combining MPLS traffic engineering control with optical crossconnects," IEEE Commun. Mag., vol. 39, no. 3, pp. 111-116, Mar. 2001.
• 3: "Configuring OSPF," Cisco Systems [Online]. Available: http://www. cisco.com/univercd/home/home.htm
• 4: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 5: O. Hauser, M. Kodialam, and T. V. Lakshman, "Capacity design of fast path restorable optical networks," in IEEE INFOCOM, New York, 2002.
• 6: M. Kodialam and T. V. Lakshman, "Dynamic routing of locally restorable bandwidth guaranteed tunnels using aggregated link usage information," in IEEE INFOCOM, Anchorage, AK, 2001.
• 7: M. Kodialam, T. V. Lakshman, and S. Sengupta, "Capacity allocation and routing of locally restorable bandwidth guaranteed connections," in IEEE INFOCOM, Miami, FL, 2005.
• 8: E. Mannie et al., "Generalized Multi-Protocol Label Switching (GMPLS) architecture," RFC 3945, 2004.
• 9: P. Pan et al., "Fast reroute extensions to RSVP-TE for LSP tunnels," RFC 4090, 2004.
• 10: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 11: Matthew Roughan , Albert Greenberg , Charles Kalmanek , Michael Rumsewicz , Jennifer Yates , Yin Zhang, Experience in measuring backbone traffic variability: models, metrics, measurements and meaning, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637213]
• 12: S. Sengupta and R. Ramamurthy, "From network design to dynamic provisioning and restoration in optical cross-connect mesh networks: An architectural and algorithmic overview," IEEE Network Mag., vol. 15, no. 4, pp. 46-54, Jul./Aug. 2001.
• 13: V. Sharma , F. Hellstrand, Framework for Multi-Protocol Label Switching (MPLS)-based Recovery, RFC Editor, 2003
• 14: Neil Spring , Ratul Mahajan , David Wetherall , Thomas Anderson, Measuring ISP topologies with rocketfuel, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.2-16, February 2004 [doi>10.1109/TNET.2003.822655]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance

Keywords:
MPLS, fast restoration, optical networks, protection, routing, traffic engineering