An optimal packet scheduling and load balancing algorithm for LEO/MEO satellite networks

ABSTRACT

LEO/MEO constellations of communication satellites have recently been proposed as a powerful tool for improving internet performance and for extending it beyond the earth (InterPlanetary Internet). Several aspects of such usage must still be investigated. Among them, proper routing and MAC protocols play a prominent role. In this paper,we assume that the MAC protocol is an MF/TDMA one (as usual in satellite communication), and we consider the problem of assigning packets to a set of shortest paths in a satellite constellation, with the goal of minimizing the overall packet scheduling problem. We present an optimal polynomial time algorithm which works offline and balances the load over all possible shortest paths, allowing a minimum schedule length for the entire constellation to be found in polynomial time.

REFERENCES

• 1: P. Agrawal, J. C. Chen, and K. Sivalingam. Wireless Multimedia Network Technologies for the New Millennium, chapter 11. Kluwer Academic Press, 1999.
• 2: O. B. Akan, J. Fang, and I. F. Akyildiz. TP-Planet: A reliable transport protocol for interPlanetary internet. IEEE Journal on Selected Areas in Communications, 22(2):348--361, February 2004.
• 3: Ian F. Akyildiz , Özgür B. Akan , Chao Chen , Jian Fang , Weilian Su, InterPlaNetary internet: state-of-the-art and research challenges, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.2, p.75-112, 7 October 2003 [doi>10.1016/S1389-1286(03)00345-1]
• 4: Piera Barcaccia , Maurizio A. Bonuccelli, Polynomial time optimal algorithms for time slot assignment of variable bandwidth systems, IEEE/ACM Transactions on Networking (TON), v.2 n.3, p.247-251, June 1994 [doi>10.1109/90.311622]
• 5: Piera Barcaccia , Maurizio A. Bonuccelli , Miriam Di Ianni, Complexity of Minimum Length Scheduling for Precedence Constrained Messages in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1090-1102, October 2000 [doi>10.1109/71.888647 ]
• 6: A. A. Bertossi, G. Bongiovanni, and M. A. Bonuccelli. Time slot assignment in SS/TDMA systems with intersatellite links. IEEE Transactions on Communications, 35:602--608, 1987.
• 7: G. Bongiovanni, D. Coppersmith, and C. K. Wong. An optimal time slot assignment algorithm for a SS/TDMA system with variable number of transponders. IEEE Transactions on Communications, 29:721--726, 1981.
• 8: M. A. Bonuccelli, F. Martelli, and S. Pelagatti. Load balancing in LEO/MEO satellite IP networks. http://www.di.unipi.it/~f.martel/publications.html.
• 9: Maurizio A. Bonuccelli , Francesca Martelli , Susanna Pelagatti, Optimal packet scheduling in tree-structured LEO satellite clusters, Mobile Networks and Applications, v.9 n.4, p.289-295, August 2004 [doi>10.1145/1012215.1012220]
• 10: Rainer E. Burkard, Time-slot assignment for TDMA-systems, Computing, v.35 n.2, p.99-112, 1985 [doi>10.1007/BF02260498]
• 11: C. S. Chang, W. J. Chen, and H. Y. Huang. Birkhoff-von Neumann input buffered crossbar switches. In INFOCOM 2000, Tel Aviv, Israel, March 26-30 2000.
• 12: Chao Chen , Eylem Ekici , Ian F. Akyildiz, Satellite grouping and routing protocol for LEO/MEO satellite IP networks, Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570790.570809]
• 13: Hongsik Choi , Hyeong-Ah Choi , Murat Azizoğlu, Efficient scheduling of transmissions in optical broadcast networks, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.913-920, Dec. 1996 [doi>10.1109/90.556359]
• 14: A. Ganz and Y. Gao. Efficient algorithms for SS/TDMA scheduling. IEEE Transactions on Communications, 8:1367--1374, 1992.
• 15: B. Gavish. LEO/MEO systems - global mobile communication systems. Telecommunication Systems, 8:99--141, 1997.
• 16: I. S. Gopal, G. Bongiovanni, M. A. Bonuccelli, D. T. Tang, and C. K. Wong. An optimal switching algorithm for multibeam satellite systems with variable bandwidth. IEEE Transactions on Communications, 30:2475--2481, 1982.
• 17: T. Inukai. SS/TDMA networking via ISL. In ICC'81, pages 70.6.1--70.6.5, 1981.
• 18: Feiling Jia , Biswanath Mukherjee , Jason Iness, Scheduling variable-length messages in a single-hop multichannel local lightwave network, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.477-488, Aug. 1995 [doi>10.1109/90.413222]
• 19: J. Lee and S. Kang. Satellite over satellite (SOS) network: A novel architecture for satellite network. In Proceedings of IEEE INFOCOM 2000, pages 315--321, March 2000.
• 20: A. Mekkittikul and N. McKeown. A practical scheduling algorithm to achieve 100% throughput in input-queued switches. In INFOCOM 1998, S. Francisco, March 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Theory

Keywords:
LEO/MEO satellite networks, MF/TDMA, load balancing, optimal algorithm, packet scheduling