Optimal Oblivious Load-Balancing for Sparse Traffic in Large-Scale Satellite Networks

Oblivious load-balancing involves routing traffic from sources to destinations using predetermined paths independent of the traffic to minimize the maximum load on any link in the network. This paper addresses oblivious load-balancing in large-scale Low-Earth Orbit satellite networks which are modeled as torus networks with sparse traffic localized to certain hotspot regions. For an N × N torus network with at most k active source-destination pairs, we establish that any oblivious routing scheme incurs a worst-case load of at least √ 2k/4 for 1 < k ≤ N 2 /2, and N/4 for N 2 /2 ≤ k ≤ N 2 , by using a linear programming formulation. Moreover, we demonstrate that the celebrated Valiant Load-Balancing scheme is suboptimal under sparse traffic and construct an optimal oblivious load-balancing scheme that achieves the proposed lower bound. Further, we identify a √ 2 multiplicative gap between the worst-case load of an optimal non-oblivious routing and the worst-case load of any optimal oblivious routing. We extend the load-balancing results to N × M tori with unequal link capacities along the vertical and horizontal directions, which model satellite network topologies more realistically. Additionally, we extend the result to higherdimensional torus networks, also known as N -ary m-cubes, which are relevant to datacenter and interconnection networks.