UMR: A utility-maximizing routing algorithm for delay-sensitive service in LEO satellite networks

Abstract This paper develops a routing algorithm for delay-sensitive packet transmission in a low earth orbit multi-hop satellite network consists of micro-satellites. The micro-satellite low earth orbit (MS-LEO) network endures unstable link connection and frequent link congestion due to the uneven user distribution and the link capacity variations. The proposed routing algorithm, referred to as the utility maximizing routing (UMR) algorithm, improve the network utility of the MS-LEO network for carrying flows with strict end-to-end delay bound requirement. In UMR, first, a link state parameter is defined to capture the link reliability on continuing to keep the end-to-end delay into constraint; then, on the basis of this parameter, a routing metric is formulated and a routing scheme is designed for balancing the reliability in delay bound guarantee among paths and building a path maximizing the network utility expectation. While the UMR algorithm has many advantages, it may result in a higher blocking rate of new calls. This phenomenon is discussed and a weight factor is introduced into UMR to provide a flexible performance option for network operator. A set of simulations are conducted to verify the good performance of UMR, in terms of balancing the traffic distribution on inter-satellite links, reducing the flow interruption rate, and improving the network utility.