M_CSPF: A Scalable CSPF Routing Scheme with Multiple QoS Constraints for MPLS Traffic Engineering

ETRI Journal

关键词: QoS;    DiffServ;    IntServ;    rate control;    flow aggregation;    Packet scheduler;   

Others  :  1185200
DOI  :  10.4218/etrij.05.0104.0117

【 摘 要 】

In the context of multi-protocol label switching (MPLS) traffic engineering, this paper proposes a scalable constraint-based shortest path first (CSPF) routing algorithm with multiple QoS metrics. This algorithm, called the multiple constraint-based shortest path first (M_CSPF) algorithm, provides an optimal route for setting up a label switched path (LSP) that meets bandwidth and end-to-end delay constraints. In order to maximize the LSP accommodation probability, we propose a link weight computation algorithmto assign the link weight while taking into account the future traffic load and link interference and adopting the concept of a critical link from the minimum interference routing algorithm. In addition, we propose a bounded order assignment algorithm (BOAA) that assigns the appropriate order to the node and link, taking into account the delay constraint and hop count. In particular, BOAA is designed to achieve fast LSP route computation by pruning any portion of the network topology that exceeds the end-to-end delay constraint in the process of traversing the network topology. To clarify the M_CSPF and the existing CSPF routing algorithms, this paper evaluates them from the perspectives of network resource utilization efficiency, end-to-end quality, LSP rejection probability, and LSP route computation performance under various network topologies and conditions.

   

【 参考文献 】

• [1]D. Awduche, J. Malcolm, J. Agogbua, and M. O’Dell, Requirements for Traffic Engineering Over MPLS, RFC 2702, Sept. 1999.
• [2]R. Guerin, Ariel Orda, and D. Williams, "QoS Routing Mechanisms and OSPF Extension," Proc. of 2nd Global Internet Miniconference (Joint with Globecom’97), Nov. 1997.
• [3]B. Davie and Y. Rekhter, "MPLS Technology and Applications," Morgan Kaufmann Publishers, 2000.
• [4]R. Guerin, A. Orda, and D. Williams, "QoS Routing Mechanism and OSPF Extensions," Proc. of IEEE GLOBECOM’97, Nov. 1997.
• [5]P. Aukia, M. Kodianlam, P.V. Koppol, T.V. Lakeshman, H. Sarin, and B. Suter "RATES: A Server for MPLS Traffic Engineering," IEEE Network, vol. 14. no. 2, Mar.-Apr. 2000.
• [6]Int’l Eng. Consortium, A Comparison of Multiprotocol Label Switching (MPLS) Traffic-Engineering Initiatives, http://www.iec.org/online/tutorials/, Web ProForum Tutorials, 2003.
• [7]Nortel Network, "Using Constraint-Based Routing to Deliver New Services," http://www.nortelnetworks.com/products/library/collateral/ 55046.25-10-99.pdf.
• [8]Q. Ma and P. Steenkiste, "On Path Selection for Traffic with Bandwidth Guarantees," Proc. of IEEE Int’l Conf. on Network Protocol, Oct. 1997.
• [9]Q. Ma and P. Steenkiste, "On Path Selection for tra.c with Bandwidth Guarantees," Proc. of IEEE ICNP, 1997, pp. 191-202.
• [10]M. Kodialam and T.V. Lakshman, "Minimum Interference Routing with Applications to MPLS Traffic Engineering," Proc. of INFOCOM, Mar. 2000.
• [11]Z. Wang and J. Crowcroft, "QoS Routing for Supporting Multimedia Applications," IEEE JSAC, vol. 14, no. 7, 1996, pp. 1228-1234.
• [12]P.S. Qingming Ma, "On Path Selection for Traffic with Bandwidth Gurantees," Proc. of IEEE Int’l Conf. on Network Protocols, Oct. 1997, pp. 191-202.
• [13]Yufei Wang and Zheng Wang, "Explicit Routing Algorithms for Internet Traffic Engineering," Computer Commun. and Networks, 1999, pp. 582-588.
• [14]E. Crawley, R. Nair, and H. Sandick, "A Framework for QoS-based Routing in the Internet," IETF RFC2386, Aug. 1998.
• [15]Z. Wang and J. Crowcroft, "Quality of Service Routing for Supporting Multimedia Applications," IEEE J. on Selected Areas in Comm., vol. 14, no. 7, Sept. 1996, pp. 1228-1234.
• [16]R. Boutaba, W. Szeto, and Y. Iraqi, "DORA: Efficient Routing Algorithm for MPLS Traffic Engineering," Int’l J. of Network and Systems Management, Special Issue on Traffic Eng. and Management, vol. 10, no. 3, 2002, pp. 311-327.
• [17]Woo-Seop Rhee, Jun-Hwa Lee, Jea-Hoon Yu, and Sang-Ha Kim, "Scalable Quasi-Dynamic-Provisioning-Based Admission Control Mechanism in Differentiated Service Networks," ETRI J., vol. 26, no. 1, Feb. 2004, pp. 27-37.
• [18]Hun-Jeong Kang, Myung-Sup Kim, and James W. Hong, "Streaming Media and Multimedia Conferencing Traffic Analysis Using Payload Examination," ETRI J., vol. 26, no. 3, June 2004, pp. 203-217.
• [19]X. Xiao and L.Ni, "Internet QoS: A Big Picture," IEEE Network, vol. 13, no. 2 , Mar.-Apr. 1999, pp. 8-18.
• [20]Y. Wang and Z. Wang, "Explicit Routing Algorithms for Internet Traffic Engineering," Proc. of IEEE ICCCN99, Oct. 11-13, 1999.
• [21]K. Kompella and D.O. Awduche, "Notes on Path Computation in Constraint-Based Routing," Internet-Draft, July 1999.
• [22]L.L.H. Andrew and A.A.N.A. Kusuma, "Generalised Analysis of a QoS-Aware Routing Algorithm," Proc. of IEEE Globecom’98, 1998, pp. 118-123.
• [23]Satoshi Kamei and Takumi Kimura, "Evaluation of Routing Algorithms and Network Topologies for MPLS Traffic Engineering," Proc. of IEEE GLOBECOM 2001, no. 1, Nov 2001, pp. 25-29.
• [24]E. Crawley, R. Nair, B. Rajagopalan, and H. Sandick, A Framework for QoS-Based Routing in the Internet, RFC 2386, Aug. 1998.
• [25]G.R. Ash, Traffic Engineering & QoS Methods for IP-, ATM-, & TDM-Based Multiservice Networks, Internet-Draft, July 2000.
• [26]X. Xiao, A. Hanan, and B. Bailey, "Traffic Engineering with MPLS in the Internet," IEEE Network, vol. 14, no. 2, Mar.-Apr. 2000.