Distributed Multicast Traffic Engineering for Multi-Domain Software-Defined Networks

• Published in: IEEE transactions on parallel and distributed systems 2023-02, Vol.34 (2), p.446-462
• Main Authors: Chiang, Sheng-Hao, Wang, Chih-Hang, Yang, De-Nian, Liao, Wanjiun, Chen, Wen-Tsuen
• Format: Article
• Language: English
• Subjects: Algorithms; Bandwidth; Communications traffic; Competitive ratio; Costs; distributed algorithm; Distributed algorithms; Domains; Forestry; multi-domain SDN; Multicasting; Network topology; Optimization; Rerouteing; Routing; Software engineering; Software-defined networking; Traffic control; Traffic engineering; Unicast
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2022.3205219

Previous research on SDN multicast traffic engineering mainly focused on intra-domain optimization. However, the main traffic on the Internet is inter-domain, and the selection of border nodes and sharing of network information between domains are usually distributed but ignored in previous works. In this article, we explore multi-domain online distributed multicast traffic engineering (MODMTE). To effectively solve MODMTE, we first prove that MODMTE is inapproximable within |D_{\max }| |Dmax| , which indicates that it is impossible to find any algorithm with a ratio better than |D_{\max }| |Dmax| for MODMTE, and |D_{\max }| |Dmax| is the maximum number of destinations for a multicast tree. Then, we design a |D_{\max }| |Dmax| -competitive distributed algorithm with the ideas of Domain Tree, Dual Candidate Forest Construction, and Forest Rerouting to achieve the tightest performance bound for MODMTE. Experiments on a real SDN with YouTube traffic manifest that the proposed distributed algorithm can reduce more than 30% of the total cost of bandwidth consumption and rule updates for multicast tree rerouting compared with the state-of-the-art algorithms.