Minimizing Packet Waiting Time in a Multibeam Satellite System

In this paper, we examine the problem of time-slot assignment in an SS/TDMA system operating in a packet-switched environment. We seek to assign time slots in order to minimize average packet waiting time and in order to maximize transponder utilization. We show that an assignment which achieves both objectives exists and develop a branch-and-bound algorithm to find it. In addition, we suggest several heuristics which require much less computational effort and give very close to optimal results. We derive theoretical bounds on the performance of these heuristics and perform simulation trials to show that, on average, the heuristics are very much better than their bounds suggest, and are, in fact, extremely close to optimal.