IEEE Transactions on Network and Service Management · 2022 · 33 citations · 39 references
ComputingComputer ScienceComputer SystemsComputer NetworksDigital CommunicationInterconnection NetworksRoutingSatellite Constellation ArchitectureLow Earth OrbitsMulticast CommunicationMulticast RoutingMulticast TopologySatellite ConstellationsScalabilitySpanning Tree ConstructionSteiner Tree Problem
The emerging large-scale low earth orbit (LEO) broadband satellite networks manifest great potentials in distributing videos across the globe via efficient multicast techniques. However, existing work only studied IP multicast (IPMC) for LEO constellations, which suffers from limited scalability and tree performance. In this paper, we employ the promising software defined multicast (SDM) techniques in large-scale LEO constellations to empower satellite-based Internet video distribution. We present a multi-layer rectilinear Steiner tree (ML-RST) construction algorithm for multicast routing in large-scale LEO constellations. We extend the spanning graph and edge substitution to three-dimensional (3D) scenes. Based on multi-layer spanning graphs and multi-layer edge substitution approaches, we manage to efficiently construct ML-RSTs with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${O}$ </tex-math></inline-formula> ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> log <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> ) complexity. Experimental results show that our approach can achieve an average 10% improvement in bandwidth saving compared with existing algorithms.
39
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text
A sweepline algorithm for Voronoi diagrams
Steven Fortune · Algorithmica · 1987 · 1.1K citations
F. K. Hwang, Dana Richards · Networks · 1992 · 664 citations