Future low Earth orbit (LEO) mega-constellations will feature large-scale, dynamic, and multi-layer network topologies, posing new challenges for efficient routing. Traditional shortest-path algorithms, originally designed for two-dimensional planar networks, are inadequate for the three-dimensional, time-varying structure of LEO networks. The deployment of laser inter-satellite links (LISLs), while extending communication reach, significantly increases node density and exacerbates computational complexity. To address these issues, we propose Dynamic topology and Bidirectional Search (DBS), a novel algorithm tailored for routing in LISL-enabled multi-layer LEO mega-constellations. DBS integrates a bidirectional search strategy with customized cost functions for effective search-space pruning, substantially reducing computational overhead while preserving path optimality. We develop three DBS variants: DBS-OP for optimal routing, DBS-FS for fast routing, and DBS-RC for rapid path recovery. Theoretical analysis and extensive simulations demonstrate that DBS-OP achieves optimal paths with a significantly smaller search space than conventional methods, DBS-FS delivers near-optimal performance with accelerated execution, and DBS-RC ensures robust recovery under diverse failure scenarios. Overall, DBS provides an efficient, scalable, and adaptable routing solution for future large-scale LEO networks.

Multi-view videos (MVV) have emerged to provide users with immersively interactive experiences with 3D multimedia content. Compared with traditional 2D videos, MVV offers multiple view angles to avoid generating occluded regions from a single viewpoint and allows users to receive different view angles, which consume much higher bandwidth. In this paper, we leverage multicast and view synthesis to effectively reduce the number of transmitted views and total bandwidth consumption in software-defined content delivery networks (SD-CDN). By exploiting the SDN architecture, SD-CDN can optimize traffic engineering and the selection of multi-view sources to serve users. We formulate a new optimization problem, (), prove the NP-hardness, and design an online algorithm with the ideas of View Popularity Cost Ratio, View Watching Possibility, and synthesis tree, to achieve the tightest competitive ratio. The experiment on real networks and implementation in an experimental SDN manifest that the proposed algorithm outperforms state-of-the-art algorithms regarding the total cost, bandwidth consumption, synthesis quality, and link and node utilization.

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 }|$, which indicates that it is impossible to find any algorithm with a ratio better than$|D_{\max }|$for MODMTE, and$|D_{\max }|$is the maximum number of destinations for a multicast tree. Then, we design a$|D_{\max }|$-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.

Social Internet of Things (SIoT) has become an emerging network paradigm, where IoT devices with Artificial Intelligence (AI) and social relations can automatically establish a collaborative group to identify events locally. On the other hand, mobile users can act as ubiquitous and versatile sensors to improve the accuracy of SIoT event detection. In this paper, we explore the SIoT Collaboration with Crowdsourcing (SCC) problem to jointly select SIoT devices and hire users to monitor events and locations with accuracy requirements, while minimizing the total SIoT communication and computation costs and the user hiring cost. We prove that SCC is NP-hard and cannot be approximated by any factor unless P = NP. Then, we propose a new algorithm, Accuracy- and Social-aware SIoT and User Selection (ASSUS), with the idea of Collaborative Tree (CT) and Accuracy Profit (AP), where CT exploits users’ social relations to properly choose intermediate SIoTs. Simulation results manifest that ASSUS can effectively reduce more than 50% of the total cost compared with state-of-the-art algorithms.

With the emergence of innovative applications for Virtual Reality (VR) in touring, E-commerce, and social activities, high-quality VR video streaming becomes essential. To support numerous wireless VR users, this paper aims to leverage video synthesis techniques to effectively reduce the multicast bandwidth consumption. It synthesizes the view in the video for a user from the one of a nearby user with similar Field of View (FoV), under the virtual distance and view angle constraints. We first formulate a new optimization problem, named VR Content Sharing and Multicasting (VCSM), and prove the NP-hardness. Then, we propose View Sharing Relation Graph (VSRG) to model the synthesis relation between each pair of views. We then design a new algorithm, named Bandwidth-Efficient Multicast with Synthesis (BEMS) to select multicast views and the corresponding MCS in wireless networks. Simulation results show that BEMS can effectively reduce bandwidth consumption by more than 50% compared with state-of-the-art wireless transmission schemes.

Previous research on Segment Routing (SR) mostly focused on unicast, whereas online SDN multicast with segment trees supporting IETF dynamic group membership has not been explored. Compared with unicast SR, online SDN multicast with segment trees is more challenging since finding an appropriate size, shape, and location for each segment tree is crucial to deploy it in more multicast trees. In this paper, we explore Multi-tree Multicast Segment Routing (MMSR) to jointly minimize the bandwidth consumption and forwarding rule updates over time by leveraging segment trees. We prove MMSR is NP-hard and design an online competitive algorithm, named Segment Tree Routing and Update Scheduling (STRUS) to achieve the tightest bound. STRUS includes Segment Tree Merging and Segment Tree Pruning to merge smaller overlapping subtrees into segment trees, and then tailor them to serve more multicast trees. We design Stability Indicator and Reusage Indicator to carefully construct segment trees at the backbone of multicast trees and reroute multicast trees to span more segment trees. Simulation and implementation on real SDNs with YouTube traffic manifest that STRUS outperforms state-of-the-art algorithms regarding the total cost and TCAM usage. Moreover, STRUS is practical for SDN since its running time is about 1 second, even for massive networks with thousands of nodes.

Traffic engineering (TE) and efficient network updating have been considered as separate problems in previous SDN research. Traffic engineering mostly focuses on static traffic and does not consider the rerouting overheads to support dynamic traffic. Efficient network updating assumes the new routing is provided by TE and focuses on minimizing only the rerouting overheads, and therefore, the improved new routing with bandwidth consumption similar to the new routing from TE but much lower rerouting overheads has not been explored. In this paper, we explore Multi-tree Low-overhead Multicast Rerouting (MLMR) to jointly solve both problems for SDN multicast. We prove that MLMR is NP-hard and design a new approximation algorithm, named Multicast Rerouting and Update Scheduling Algorithm (MRUSA). Equipped with the notions of deterioration indicator, motivator, and inhibitor, MRUSA provides incremental tree updating and multi-tree update scheduling to address the trade-off between the bandwidth consumption and rerouting overheads. Frequent rerouting due to tiny changes of multicast users can be effectively avoided, because rerouting time for each group can be correctly identified. Simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 35% compared with SPT and ST, and the computation time is small for massive SDN.

Previous research on SDN traffic engineering mostly focuses on static traffic, whereas dynamic traffic, though more practical, has drawn much less attention. Especially, online SDN multicast that supports IETF dynamic group membership (i.e., any user can join or leave at any time) has not been explored. Different from traditional shortest-path trees (SPT) and graph theoretical Steiner trees (ST), which concentrate on routing one tree at any instant, online SDN multicast traffic engineering is more challenging because it needs to support dynamic group membership and optimize a sequence of correlated trees without the knowledge of future join and leave, whereas the scalability of SDN due to limited TCAM is also crucial. In this paper, therefore, we formulate a new optimization problem, named Online Branch-aware Steiner Tree (OBST), to jointly consider the bandwidth consumption, SDN multicast scalability, and rerouting overhead. We prove that OBST is NP-hard and does not have a |Dmax|1-ε-competitive algorithm for any , where |Dmax| is the largest group size at any time. We design a |Dmax|-competitive algorithm equipped with the notion of the budget, the deposit, and Reference Tree to achieve the tightest bound. The simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 25% compared with SPT and ST, and the computation time is small for massive SDN.