Integrated Subset Split for Balancing Network Utilization and Quality of Routing

Authors: S. V. Kasmir Raja, P. Herbert Raj

Abstract:

The overlay approach has been widely used by many service providers for Traffic Engineering (TE) in large Internet backbones. In the overlay approach, logical connections are set up between edge nodes to form a full mesh virtual network on top of the physical topology. IP routing is then run over the virtual network. Traffic engineering objectives are achieved through carefully routing logical connections over the physical links. Although the overlay approach has been implemented in many operational networks, it has a number of well-known scaling issues. This paper proposes a new approach to achieve traffic engineering without full-mesh overlaying with the help of integrated approach and equal subset split method. Traffic engineering needs to determine the optimal routing of traffic over the existing network infrastructure by efficiently allocating resource in order to optimize traffic performance on an IP network. Even though constraint-based routing [1] of Multi-Protocol Label Switching (MPLS) is developed to address this need, since it is not widely tested or debugged, Internet Service Providers (ISPs) resort to TE methods under Open Shortest Path First (OSPF), which is the most commonly used intra-domain routing protocol. Determining OSPF link weights for optimal network performance is an NP-hard problem. As it is not possible to solve this problem, we present a subset split method to improve the efficiency and performance by minimizing the maximum link utilization in the network via a small number of link weight modifications. The results of this method are compared against results of MPLS architecture [9] and other heuristic methods.

Keywords: Constraint based routing, Link Utilization, Subsetsplit method and Traffic Engineering.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1071602

References:

[1] A. Chakrabarti and G. Manimaran, Reliability constrained routing in QoS networks, IEEE/ACM Trans. on Networking, vol. 13, no. 3, pp. 662-675, June 2005.
[2] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, and J. McManus. ''Requirements for traffic engineering over MPLS'', Internet draft, IETF, April 1998, draft-awduche-mpls-traffic-eng-00.txt.
[3] Yufei Wang, Zheng Wang and Leah Zhang ''Internet Traffic Engineering without full mesh overlaying'', Infocom, 2001.
[4] J Moy, ''OSPF version 2'', Internet rfc'', IETF, May 1998, Technical report RFC 2328.
[5] C. Villamizar, ''OSPF optimized multipath'', Internet draft, IETF, March 1998, draft-ietf-ospf-omp-00.txt.
[6] B. Fortz and M. Thorup, ''Internet traffic engineering by optimizing OSPF weights'', Proceedings of INFOCOM'2000, March 2000.
[7] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, and J. McManus. Requirements for traffic engineering over MPLS. IETF RFC 2702, September 1999.
[8] Yufei Wang and Zheng Wang, ''Explicit routing algorithms for internet traffic engineering'', Proceedings of ICCCN'99, Sept 1999.
[9] E. Rosen, A. Viswanathan, and R. Callon. Multiprotocol label switching architecture, IETF RFC 3031, Standards Track, January 2001.
[10] A. Soule, A. Nucci, E. Leonardi, R. cruz and N. Taft, How to identify and estimate top largest OD flows in dynamic environment. In Proceedings of SIGMETRICS'04, pages 49-60. New York, June 2004.
[11] CPLEX: Mathematical Problem Solver. http://www.cplex.com.
[12] V. Chvatal, Linear Programming, W H Freeman and Company, 1983.
[13] D.P Bertsekas and R.G.Gallager, Data Networks (2nd Edition), Printice Hall. pp 434.
[14] Yuxi Li, Janelle Harms and Robert Holte ''A simple method for balancing network utilization and quality of routing'', Proceedings of ICCCN'05. Sept.2005.