Multiobjective routing in multiservice MPLS networks with traffic splitting — A network flow approach

Abstract

A multiobjective routing model for Multiprotocol Label Switching networks with multiple service types and traffic splitting is presented in this paper. The routing problem is formulated as a multiobjective mixed-integer program, where the considered objectives are the minimization of the bandwidth routing cost and the minimization of the load cost in the network links with a constraint on the maximal splitting of traffic trunks. Two different exact methods are developed for solving the formulated problem, one based on the classical constraint method and another based on a modified constraint method. A very extensive experimental study, with results on network performance measures in various reference test networks and in randomly generated networks, is also presented and its results are discussed.

Keywords

Routing models / multiobjective optimization / telecommunication networks / network flow approach / traffic splitting

References

[1] Aarts E, Lenstra J K. Local Search in Combinatorial Optimization, 1997.

[2] Agdeppa R P, Yamashita N, Fukushima M. The traffic equilibrium problem with nonadditive costs and its monotone mixed complementarity problem formulation. Transportation Research Part B — Methodological, 2007, 41(8): 862-874.

[3] Avallone S, Manetti V, Mariano M, Romano S P. A splitting infrastructure for load balancing and security in an MPLS network. Proceedings of the 3rd International Conference on Testbeds and Research Infrastructure for the Development of Networks and Communities (TridentCom 2007), Lake Buena Vista (FL), USA, May 21–23, 2007

[4] Bekhor S, Toledo T, Toledo J N. Effects of choice set size and route choice models on path-based traffic assignment. Transportmetrica, 2008, 4(2): 117-133.

[5] Bertsimas D, Tsitsiklis J. Simulated annealing. Statistical Science, 1993, 8(1): 10-15.

[6] Bovy P H L. On modelling route choice sets in transportation networks: A synthesis. Transport Reviews: A Transnational Transdisciplinary Journal, 2009, 29(1): 43-68.

[7] Brands T, van Eck G. Multimodal network design and assessment — Proposal for a dynamic multi-objective approach. 11th TRAIL Congress, The Netherlands Research School on Transport, Infrastructure and Logistics, Nov, 2010

[8] Branke J, Deb K, Miettinen K, Słowiński R. Multiobjective Optimization — Interactive and Evolutionary Approaches, 2008.

[9] Chen A, Zhou Z, Chootinan P, Ryu S, Yang C, Wong S C. Transport network design problem under uncertainty: A review and new developments. Transport Reviews, 2011, 31(6): 743-768.

[10] Clímaco J C N, Craveirinha J M F, Pascoal M M B. An automated reference point-like approach for multicriteria shortest path problems. Journal of Systems Science and Systems Engineering, 2006, 15(3): 314-329.

[11] Clímaco J C N, Craveirinha J M F, Pascoal M M B. Shi Y, Olson D L, Stam A. Multicriteria routing models in telecommunication networks — Overview and a case study. Advances in Multiple Criteria Decision Making and Human Systems Management: Knowledge and Wisdom, 2007 17-46.

[12] Clímaco J, Pascoal M. Finding nondominated shortest pairs of disjoint simple paths. Computers & Operations Research, 2009, 36(11): 2892-2898.

[13] Cohon J L. Multiobjective Programming and Planning, 1978.

[14] Craveirinha J, Gomes T, Pascoal M, Clímaco J. A stochastic bicriteria approach for restorable QoS routing in MPLS. Proceedings of the 2011 International Conference on Telecommunication Systems — Modeling and Analysis (ICTSM2011), 2011 1-15.

[15] Craveirinha J, Clímaco J, Martins L, da Silva C G, Ferreira N. A bi-criteria minimum spanning tree routing model for MPLS/Overlay networks. Telecommunication Systems, 2013, 52(1): 203-215.

[16] Craveirinha J M F, Clímaco J C N, Pascoal M M B, Martins L M R A. Traffic splitting in MPLS networks — A hierarchical multicriteria approach. Journal of Telecommunications and Information Technology, 2007 3-10.

[17] Craveirinha J, Girão-Silva R, Clímaco J. A meta-model for multiobjective routing in MPLS networks. Central European Journal of Operations Research, 2008, 16(1): 79-105.

[18] Dana A, Zadeh A K, Kalantari M E, Badie K. A traffic splitting restoration scheme for MPLS network using case-based reasoning. Proceedings of the 9th Asia Pacific Conference on Communications (APCC 2003), 2003, 2: 763-766.

[19] Dana A, Khademzadeh A, Kalantari M E, Badie K. Fault recovery in MPLS network using case-based reasoning. Modares Technical and Engineering, 2004, 16: 127-138.

[20] Deb K. Multi-Objective Optimization using Evolutionary Algorithms, 2001.

[21] Dial R B. Bicriterion traffic assignment: Basic theory and elementary algorithms. Transportation Science, 1996, 30(2): 93-111.

[22] Dial R B. Bicriterion traffic assignment: Efficient algorithms plus examples. Transportation Research Part B — Methodological, 1997, 31(5): 357-379.

[23] Dixit A, Prakash P, Kompella R R. On the efficacy of fine-grained traffic splitting protocols in data center networks. Proceedings of SIGCOMM11, 2011 430-431.

[24] Doar M, Leslie I M. How bad is naive multicast routing?. Proceedings of INFOCOM, 1993, 1: 82-89.

[25] Ehrgott M, Gandibleux X. A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 2000, 22(4): 425-460.

[26] Elwalid A, Jin C, Low S, Widjaja I. MATE: MPLS Adaptive Traffic Engineering. Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), 2001, 3: 1300-1309.

[27] Erbas S C, Erbas C. Charzinski J, Lehnert R, Tran-Gia P. A multiobjective off-line routing model for MPLS networks. Proceedings of the 18th International Teletraffic Congress (ITC-18), 2003, Amsterdam: Elsevier 471-480.

[28] Ferng H-W, Peng C-C. Traffic splitting in a network: Split traffic models and applications. Computer Communications, 2004, 27(12): 1152-1165.

[29] Fortz B, Thorup M. Internet traffic engineering by optimizing OSPF weights. Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2000), 2000, 2: 519-528.

[30] Fortz B, Thorup M. Optimizing OSPF/IS-IS weights in a changing world. IEEE Journal on Selected Areas in Communications, 2002, 20(4): 756-767.

[31] Gandibleux X, Sevaux M, Sőrensen K, T’Kindt V. Metaheuristics for Multiobjective Optimisation, 2004.

[32] Gendreau M, Potvin J-Y. Tabu search. Handbook of Metaheuristics, International Series in Operations Research & Management Science, 2010, 146: 41-59.

[33] Ghosh A, Dehuri S. Evolutionary algorithms for multi-criterion optimization: A survey. International Journal of Computing & Information Sciences, 2004, 2(1): 38-57.

[34] Girão-Silva R, Craveirinha J, Clímaco J. Hierarchical multiobjective routing in Multiprotocol Label Switching networks with two service classes — A heuristic solution. International Transactions in Operational Research, 2009, 16(3): 275-305.

[35] Girão-Silva R, Craveirinha J, Clímaco J, Captivo M E. Multiobjective Routing in Multiservice MPLS Networks with Traffic Splitting — Report on a Network Flow Approach, 2013

[36] Gomes T, Martins L, Craveirinha J. An algorithm for calculating k shortest paths with a maximum number of arcs. Investigação Operacional, 2001, 21: 235-244.

[37] Guihaire V, Hao J-K. Transit network design and scheduling: a global review. Transportation Research Part A: Policy and Practice, 2008, 42(10): 1251-1273.

[38] He J, Rexford J. Towards Internet-wide multipath routing. IEEE Network, 2008, 22(2): 16-21.

[39] Huang H-J, Li Z-C. A multiclass, multicriteria logit-based traffic equilibrium assignment model under ATIS. European Journal of Operational Research, 2007, 176(3): 1464-1477.

[40] Knowles J, Oates M, Corne D. Advanced multi-objective evolutionary algorithms applied to two problems in telecommunications. BT Technology Journal, 2000, 18(4): 51-65.

[41] Krishnadas C S, Roy R. Quality of Experience (QoE) assurance by a multipath balanced traffic splitting algorithm in MPLS networks. Annales UMCS Informatica AI, 2009, 9(1): 165-177.

[42] Lee G M, Choi J S. A survey of multipath routing for traffic engineering, 2002

[43] Lee Y, Seok Y, Choi Y, Kim C. A constrained multipath traffic engineering scheme for MPLS networks. Proceedings of the IEEE International Conference on Communications (ICC 2002), New York, USA, Apr.28–May2, 2002

[44] Lee K, Toguyeni A, Noce A, Rahmani A. Kim C. Comparison of multipath algorithms for load balancing in a MPLS network. Proceedings of the International Conference on Information Networking, Convergence in Broadband and Mobile Networking (ICOIN2005), 2005 463-470.

[45] Lee K, Toguyeni A, Rahmani A. Hybrid multipath routing algorithms for load balancing in MPLS based IP network. Proceedings of the 20th International Conference on Advanced Information Networking and Applications (AINA 2006), Apr.18–20, 2006

[46] Liu Y, Bunker J, Ferreira L. Transit users’ route-choice modelling in transit assignment: A review. Transport Reviews: A Transnational Transdisciplinary Journal, 2010, 30(6): 753-769.

[47] Lo H K, Chen A. Reformulating the traffic equilibrium problem via a smooth gap function. Mathematical and Computer Modelling, 2000, 31(2–3): 179-195.

[48] Lo H K, Chen A. Traffic equilibrium problems with route-specific costs: formulation and algorithms. Transportation Research Part B — Methodological, 2000, 34(6): 493-513.

[49] Lu C-C, Mahmassani H S, Zhou X. A bi-criterion dynamic user equilibrium traffic assignment model and solution algorithm for evaluating dynamic road pricing strategies. Transportation Research Part C, 2008, 16: 371-389.

[50] Marcotte P, Patriksson M. Traffic equilibrium. Transportation, Handbooks in Operations Research and Management Science, 2007, 14: 623-713.

[51] Mavrotas G. Effective implementation of the ɛ-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 2009, 213(2): 455-465.

[52] Medhi D, Tipper D. Some approaches to solving a multi-hour broadband network capacity design problem with single-path routing. Telecommunication Systems, 2000, 13(2): 269-291.

[53] Messac A, Ismail-Yahaya A, Mattson C A. The normalized normal constraint method for generating the Pareto frontier. Structural and Multidisciplinary Optimization, 2003, 25(2): 86-98.

[54] Mitra D, Ramakrishnan K G. Techniques for traffic engineering of multiservice, multipriority networks. Bell Labs Technical Journal, 2001, 6(1): 139-151.

[55] Murugesan G, Natarajan A M, Venkatesh C. Enhanced variable splitting ratio algorithm for effective load balancing in MPLS networks. Journal of Computer Science, 2008, 4(3): 232-238.

[56] Nagurney A, Dong J, Mokhtarian P L. Kontoghiorghes E, Rustem B, Siokos S. Traffic network equilibrium and the environment: A multicriteria decision-making perspective. Computational Methods in Decision-Making, Economics and Finance, 2002 501-523.

[57] Nelakuditi S, Zhang Z-L. Wolf L, Hutchison D, Steinmetz R. On selection of paths for multipath routing. Proceedings of IWQoS 2001, 2001, Karlsruhe, Germany: Springer 170-184.

[58] Patriksson M. The Traffic Assignment Problem — Models and Methods. Topics in Transportation, VSP, 1994

[59] Pióro M, Szentesi, Harmatos J, Jüttner A, Gajowniczek P, Kozdrowski S. On open shortest path first related network optimization problems. Performance Evaluation, 2002, 48: 201-223.

[60] Prashker J N, Bekhor S. A review on route choice models used in the stochastic user equilibrium problem. Transport Reviews, 2004, 24(4): 437-463.

[61] Prato C G. Route choice modeling: past, present and future research directions. Journal of Choice Modelling, 2009, 2(1): 65-100.

[62] Raith A, Wang J Y T, Ehrgott M, Mitchell S A. Solving multi-objective traffic assignment. In ORP3 Meeting, Cádiz, Spain, Sep.13–17, 2011

[63] Ran B, Boyce D. Modeling Dynamic Transportation Networks — An Intelligent Transportation System Oriented Approach, 1996, 2nd ed.

[64] Sheffi Y. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, 1985

[65] Singh R K, Chaudhari N S, Saxena K. Load balancing in IP/MPLS networks: A survey. Communications and Network, 2012, 4: 151-156.

[66] Song J, Kim S, Lee M. Kahng H-K. Dynamic load distribution in MPLS networks. Proceedings of the International Conference on Information Networking, Convergence in Broadband and Mobile Networking (ICOIN2003), 2003 989-999.

[67] Srivastava S, Krithikaivasan B, Medhi D, Pióro M. Charzinski J, Lehnert R, Tran-Gia P. Traffic engineering in the presence of tunneling and diversity constraints: Formulation and Lagrangean decomposition approach. Proceedings of the 18th International Teletraffic Congress (ITC-18), 2003, Amsterdam: Elsevier 461-470.

[68] Srivastava S, Agrawal G, Pióro M, Medhi D. Determining link weight system under various objectives for OSPF networks using a Lagrangian relaxation-based approach. IEEE Transactions on Network and Service Management, 2005, 2(1): 9-18.

[69] Steuer R E. Multiple Criteria Optimization: Theory, Computation and Application. Probability and Mathematical Statistics, 1986

[70] Talbi E-G, Basseur M, Nebro A J, Alba E. Multi-objective optimization using metaheuristics: non-standard algorithms. International Transactions in Operational Research, 2012, 19(1–2): 283-305.

[71] Wang J, Patek S, Wang H, Liebeherr J. Carle G, Zitterbart M. Traffic engineering with AIMD in MPLS networks. Proceedings of the 7th IFIP/IEEE International Workshop on Protocols for High Speed Networks (PfHSN 2002), 2002 192-210.

[72] Wang J Y T, Ehrgott M. Modelling stochastic route choice with bi-objective traffic assignment. Proceedings of International Choice Modelling Conference 2011, Leeds, UK, Jul.4–6, 2011

[73] Wang J Y T, Ehrgott M. Modelling route choice behavior in a tolled road network with a time surplus maximisation bi-objective user equilibrium. Procedia — Social and Behavioral Sciences, 2013, 80: 266-288.

[74] Wierzbicki A P, Burakowski W. A conceptual framework for multiple-criteria routing in QoS IP networks. International Transactions in Operational Research, 2011, 18(3): 377-399.

[75] Yang H, Huang H-J. The multiclass, multi-criteria traffic network equilibrium and systems optimum problem. Transportation Research Part B — Methodological, 2004, 38: 1-15.

[76] Zhang Q, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.

[77] Zitzler E. Rozenberg G, Bäck T, Kok J N. Evolutionary multiobjective optimization. Handbook of Natural Computing, 2012 871-904.

[78] gt-itm Modeling Topology of Large Internetworks, 2000