Journal Home > Volume 6 , Issue 1
Big Data Mining and Analytics 2023, 6(1): 55-71 https://doi.org/10.26599/BDMA.2022.9020018
Open Access | Issue | Published: 24 November 2022

Intelligent Segment Routing: Toward Load Balancing with Limited Control Overheads

Show Author's Information Shu Yang1,  Ruiyu Chen1,  Laizhong 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
Keywords:
ant colony optimization, traffic engineering, segment routing, bandwidth load balancing
Cite this article:
Yang S, Chen R, Cui L, et al. Intelligent Segment Routing: Toward Load Balancing with Limited Control Overheads. Big Data Mining and Analytics, 2023, 6(1): 55-71. https://doi.org/10.26599/BDMA.2022.9020018
Download citation
EndNote(RIS)
BibTeX

673

Views

65

Downloads

Citations

0

Crossref

0

WoS

2

Scopus

0

CSCD

Abstract Full text About this article

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 Yang1, Ruiyu Chen1, Laizhong 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: ant colony optimization, traffic engineering, segment routing, bandwidth load balancing

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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[10]
J. Zhang and C. Zhao, Q-SR: An extensible optimization framework for segment routing, Comput. Netw., vol. 200, p. 108517, 2021.
DOI Google Scholar
[11]
X. Li and K. L. Yeung, Bandwidth-efficient network monitoring algorithms based on segment routing, Comput. Netw., vol. 147, pp. 236–245, 2018.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
Google Scholar
[18]
A. Feldmann and J. Rexford, IP network configuration for intradomain traffic engineering, IEEE Netw., vol. 15, no. 5, pp. 46–57, 2001.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[40]
U. Feige, D. Peleg, and G. Kortsarz, The dense k-subgraph problem, Algorithmica, vol. 29, no. 3, pp. 410–421, 2001.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
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