Journal Home > Volume 6 , Issue 1

Segment routing has been a novel architecture for traffic engineering in recent years. However, segment routing brings control overheads, i.e., additional packets headers should be inserted. The overheads can greatly reduce the forwarding efficiency for a large network, when segment headers become too long. To achieve the best of two targets, we propose the intelligent routing scheme for traffic engineering (IRTE), which can achieve load balancing with limited control overheads. To achieve optimal performance, we first formulate the problem as a mapping problem that maps different flows to key diversion points. Second, we prove the problem is nondeterministic polynomial (NP)-hard by reducing it to a k-dense subgraph problem. To solve this problem, we develop an ant colony optimization algorithm as improved ant colony optimization (IACO), which is widely used in network optimization problems. We also design the load balancing algorithm with diversion routing (LBA-DR), and analyze its theoretical performance. Finally, we evaluate the IRTE in different real-world topologies, and the results show that the IRTE outperforms traditional algorithms, e.g., the maximum bandwidth is 24.6% lower than that of traditional algorithms when evaluating on BellCanada topology.


menu
Abstract
Full text
Outline
About this article

Intelligent Segment Routing: Toward Load Balancing with Limited Control Overheads

Show Author's information Shu Yang1Ruiyu Chen1Laizhong Cui1( )Xiaolei Chang2
College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518000, China
Tsinghua Shenzhen International Graduate School, Tsinghua University, Shenzhen 518071, China

Abstract

Segment routing has been a novel architecture for traffic engineering in recent years. However, segment routing brings control overheads, i.e., additional packets headers should be inserted. The overheads can greatly reduce the forwarding efficiency for a large network, when segment headers become too long. To achieve the best of two targets, we propose the intelligent routing scheme for traffic engineering (IRTE), which can achieve load balancing with limited control overheads. To achieve optimal performance, we first formulate the problem as a mapping problem that maps different flows to key diversion points. Second, we prove the problem is nondeterministic polynomial (NP)-hard by reducing it to a k-dense subgraph problem. To solve this problem, we develop an ant colony optimization algorithm as improved ant colony optimization (IACO), which is widely used in network optimization problems. We also design the load balancing algorithm with diversion routing (LBA-DR), and analyze its theoretical performance. Finally, we evaluate the IRTE in different real-world topologies, and the results show that the IRTE outperforms traditional algorithms, e.g., the maximum bandwidth is 24.6% lower than that of traditional algorithms when evaluating on BellCanada topology.

Keywords:

traffic engineering, segment routing, bandwidth load balancing, ant colony optimization
Received: 18 December 2021 Revised: 22 June 2022 Accepted: 24 June 2022 Published: 24 November 2022 Issue date: March 2023
References(44)
[1]
D. O. Awduche and B. Jabbari, Internet traffic engineering using multi-protocol label switching (MPLS), Comput. Netw., vol. 40, no. 1, pp. 111–129, 2002.
[2]
N. Wang, K. H. Ho, G. Pavlou, and M. Howarth, An overview of routing optimization for internet traffic engineering, IEEE Commun. Surv. Tut., vol. 10, no. 1, pp. 36–56, 2008.
[3]
Y. Wang, Z. Wang, and L. Zhang, Internet traffic engineering without full mesh overlaying, in Proc. IEEE INFOCOM 2001. Conf. Computer Communications. Twentieth Annual Joint Conf. IEEE Computer and Communications Society (Cat. No. 01CH37213), Anchorage, AK, USA, 2001, pp. 565–571.
[4]
A. Mendiola, J. Astorga, E. Jacob, and M. Higuero, A survey on the contributions of software-defined networking to traffic engineering, IEEE Commun. Surv. Tut., vol. 19, no. 2, pp. 918–953, 2017.
[5]
M. Karakus and A. Durresi, A survey: Control plane scalability issues and approaches in software-defined networking (SDN), Comput. Netw., vol. 112, pp. 279–293, 2017.
[6]
S. H. Yeganeh, A. Tootoonchian, and Y. Ganjali, On scalability of software-defined networking, IEEE Commun. Mag., vol. 51, no. 2, pp. 136–141, 2013.
[7]
P. L. Ventre, M. M. Tajiki, S. Salsano, and C. Filsfils, SDN architecture and southbound APIs for IPv6 segment routing enabled wide area networks, IEEE Trans. Netw. Serv. Manag., vol. 15, no. 4, pp. 1378–1392, 2018.
[8]
Z. N. Abdullah, I. Ahmad, and I. Hussain, Segment routing in software defined networks: A survey, IEEE Commun. Surv. Tut., vol. 21, no. 1, pp. 464–486, 2019.
[9]
P. L. Ventre, S. Salsano, M. Polverini, A. Cianfrani, A. Abdelsalam, C. Filsfils, P. Camarillo, and F. Clad, Segment routing: A comprehensive survey of research activities, standardization efforts, and implementation results, IEEE Commun. Surv. Tut., vol. 23, no. 1, pp. 182–221, 2021.
[10]
J. Zhang and C. Zhao, Q-SR: An extensible optimization framework for segment routing, Comput. Netw., vol. 200, p. 108517, 2021.
[11]
X. Li and K. L. Yeung, Bandwidth-efficient network monitoring algorithms based on segment routing, Comput. Netw., vol. 147, pp. 236–245, 2018.
[12]
X. Jia, Q. Li, Y. Jiang, Z. Guo, and J. Sun, A low overhead flow-holding algorithm in software-defined networks, Comput. Netw., vol. 124, pp. 170–180, 2017.
[13]
R. Banerjee and S. Das Bit, Low-overhead video compression combining partial discrete cosine transform and compressed sensing in WMSNs, Wirel. Netw., vol. 25, no. 8, pp. 5113–5135, 2019.
[14]
A. Cianfrani, M. Listanti, and M. Polverini, Incremental deployment of segment routing into an ISP network: A traffic engineering perspective, IEEE/ACM Trans. Netw., vol. 25, no. 5, pp. 3146–3160, 2017.
[15]
X. Xiao, A. Hannan, B. Bailey, and L. M. Ni, Traffic engineering with MPLS in the internet, IEEE Netw., vol. 14, no. 2, pp. 28–33, 2000.
[16]
B. Fortz, J. Rexford, and M. Thorup, Traffic engineering with traditional IP routing protocols, IEEE Commun. Mag., vol. 40, no. 10, pp. 118–124, 2002.
[17]
A. Elwalid, C. Jin, S. Low, and I. Widjaja, Mate: MPLS adaptive traffic engineering, in Proc. IEEE INFOCOM 2001, Conf. Computer Communications, Twentieth Annual Joint Conf. IEEE Computer and Communications Societies, Anchorage, AK, USA, 2001, pp. 1300–1309.
[18]
A. Feldmann and J. Rexford, IP network configuration for intradomain traffic engineering, IEEE Netw., vol. 15, no. 5, pp. 46–57, 2001.
[19]
S. Kandula, D. Katabi, B. Davie, and A. Charny, Walking the tightrope: Responsive yet stable traffic engineering, ACM SIGCOMM Comput. Commun. Rev., vol. 35, no. 4, pp. 253–264, 2005.
[20]
S. Agarwal, M. Kodialam, and T. V. Lakshman, Traffic engineering in software defined networks, in 2013 Proc. IEEE INFOCOM, Turin, Italy, 2013, pp. 2211–2219.
[21]
I. F. Akyildiz, A. Lee, P. Wang, M. Luo, and W. Chou, Research challenges for traffic engineering in software defined networks, IEEE Netw., vol. 30, no. 3, pp. 52–58, 2016.
[22]
A. Guezzaz, Y. Asimi, M. Azrour, and A. Asimi, Mathematical validation of proposed machine learning classifier for heterogeneous traffic and anomaly detection, Big Data Mining and Analytics, vol. 4, no. 1, pp. 18–24, 2021.
[23]
M. Chiesa, G. Kindler, and M. Schapira, Traffic engineering with equal-cost-MultiPath: An algorithmic perspective, IEEE/ACM Trans. Netw., vol. 25, no. 2, pp. 779–792, 2017.
[24]
A. Bahnasse, F. E. Louhab, H. A. Oulahyane, M. Talea, and A. Bakali, Novel SDN architecture for smart MPLS Traffic engineering-DiffServ Aware management, Future Gener. Comput. Syst., vol. 87, pp. 115–126, 2018.
[25]
B. Zhou, J. Li, X. Wang, Y. Gu, L. Xu, Y. Hu, and L. Zhu, Online internet traffic monitoring system using spark streaming, Big Data Mining and Analytics, vol. 1, no. 1, pp. 47–56, 2018.
[26]
G. Trimponias, Y. Xiao, X. Wu, H. Xu, and Y. Geng, Node-constrained traffic engineering: Theory and applications, IEEE/ACM Trans. Netw., vol. 27, no. 4, pp. 1344–1358, 2019.
[27]
C. Filsfils, N. K. Nainar, C. Pignataro, J. C. Cardona, and P. Francois, The segment routing architecture, presented at the 2015 IEEE Global Communications Conf. (GLOBECOM), San Diego, CA, USA, 2015, pp. 1–6.
[28]
R. Bhatia, F. Hao, M. Kodialam, and T. V. Lakshman, Optimized network traffic engineering using segment routing, presented at the 2015 IEEE Conf. Computer Communications (INFOCOM), Hong Kong, China, 2015, pp. 657–665.
[29]
T. Schüller, N. Aschenbruck, M. Chimani, M. Horneffer, and S. Schnitter, Traffic engineering using segment routing and considering requirements of a carrier IP network, IEEE/ACM Trans. Netw., vol. 26, no. 4, pp. 1851–1864, 2018.
[30]
M. C. Lee and J. P. Sheu, An efficient routing algorithm based on segment routing in software-defined networking, Comput. Netw., vol. 103, pp. 44–55, 2016.
[31]
Y. Desmouceaux, P. Pfister, J. Tollet, M. Townsley, and T. Clausen, 6LB: Scalable and application-aware load balancing with segment routing, IEEE/ACM Trans. Netw., vol. 26, no. 2, pp. 819–834, 2018.
[32]
M. Jadin, F. Aubry, P. Schaus, and O. Bonaventure, CG4SR: Near optimal traffic engineering for segment routing with column generation, presented at the IEEE INFOCOM 2019 - IEEE Conf. Computer Communications, Paris, France, 2019, pp. 1333–1341.
[33]
T. Schüller, N. Aschenbruck, M. Chimani, and M. Horneffer, Failure resiliency with only a few tunnels-enabling segment routing for traffic engineering, IEEE/ACM Trans. Netw., vol. 29, no. 1, pp. 262–274, 2021.
[34]
J. Haxhibeqiri, I. Moerman, and J. Hoebeke, Low overhead scheduling of LoRa transmissions for improved scalability, IEEE Internet of Things Journal, vol. 6, no. 2, pp. 3097–3109, 2019.
[35]
G. Wang, S. Chattopadhyay, I. Gotovchits, T. Mitra, and A. Roychoudhury, oo7: Low-overhead defense against spectre attacks via program analysis, IEEE Trans. Softw. Eng., vol. 47, no. 11, pp. 2504–2519, 2021.
[36]
V. Freschi and E. Lattanzi, A study on the impact of packet length on communication in low power wireless sensor networks under interference, IEEE Internet of Things Journal, vol. 6, no. 2, pp. 3820–3830, 2019.
[37]
Y. H. Robinson, R. S. Krishnan, E. G. Julie, R. Kumar, L. H. Son, and P. H. Thong, Neighbor knowledge-based rebroadcast algorithm for minimizing the routing overhead in mobile ad-hoc networks, Ad Hoc Netw., vol. 93, p. 101896, 2019.
[38]
V. S. Devi, T. Ravi, and S. B. Priya, Cluster based data aggregation scheme for latency and packet loss reduction in WSN, Comput. Commun., vol. 149, pp. 36–43, 2020.
[39]
H. Zhu, B. Smida, and D. J. Love, Optimization of two-way network coded HARQ with overhead, IEEE Trans. Commun., vol. 68, no. 6, pp. 3602–3613, 2020.
[40]
U. Feige, D. Peleg, and G. Kortsarz, The dense k-subgraph problem, Algorithmica, vol. 29, no. 3, pp. 410–421, 2001.
[41]
P. Raghavan and C. D. Tompson, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, vol. 7, no. 4, pp. 365–374, 1987.
[42]
S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, and M. Roughan, The internet topology zoo, IEEE J. Sel. Areas Commun., vol. 29, no. 9, pp. 1765–1775, 2011.
[43]
R. Trestian, K. Katrinis, and G. M. Muntean, OFLoad: An OpenFlow-based dynamic load balancing strategy for datacenter networks, IEEE Trans. Netw. Serv. Manag., vol. 14, no. 4, pp. 792–803, 2017.
[44]
C. S. Mbacke Babou, D. Fall, S. Kashihara, Y. Taenaka, M. H. Bhuyan, I. Niang, I. Diané, and Y. Kadobayashi, D-LBAH: Dynamic load balancing algorithm for HEC-SDN systems, presented at the 2021 8th Int. Conf. Future Internet of Things and Cloud (FiCloud), Rome, Italy, 2021, pp. 304–310.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 18 December 2021
Revised: 22 June 2022
Accepted: 24 June 2022
Published: 24 November 2022
Issue date: March 2023

Copyright

© The author(s) 2023.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Nos. 61772345 and 61902258), the Major Fundamental Research Project in the Science and Technology Plan of Shenzhen (Nos. JCYJ20190808142207420, GJHZ20190822095416463, and RCYX20200714114645048), the Natural Science Foundation of Guangdong Basic and Applied Basic Research (No. 2021A1515011857), and the Pearl River Young Scholars Funding of Shenzhen University.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return