A dynamic scheduling problem in packet switched satellite networks

A queueing model and scheduling methods that eliminate transmission overlaps in time and maximize the weighted throughput of satellite networks are considered. A single server provides service to a set of parallel queues. The service of different customers cannot overlap. The service of queue i may be initiated only at certain time instances {t_nⁱ}_n=1^∞ that constitute the transmission opportunity instances for queue i. An anticipative policy that schedules transmissions in cycles is provided. The cycle length h is selected based on the backlog at the beginning of the cycle. The transmissions are scheduled such that the weighted throughput in the cycle is maximized, where the weights are selected according to the individual queue lengths at the beginning of the cycle. It is shown that the policy we propose maximizes the long term throughput for Poisson and periodic connectivity processes. The policy has a low implementation complexity which is bounded for all the achievable throughput vectors