A scheduling algorithm for communication satellite networks

Communication satellites used for area communication require careful scheduling to share the transponder bandwidth between ground stations. The scheduling problem is made more difficult by unbalanced traffic maps and by restricted frequency agility for some of the ground stations. An algorithm for finding schedules in networks with realistic constraints is described. The algorithm uses simple heuristic bandwidth partitioning and box filling strategies to pack the transmitted data into bursts that use the available satellite bandwidth efficiently. It is shown that for typical traffic maps obtained from real telephone communications systems, over 90% scheduling efficiency can be achieved compared with the 50% efficiency achieved by the traditional greedy algorithm