Scheduling Algorithms for Message Transmission Over the GBS Satellite System

摘要

This paper addresses scheduling algorithms for message transmissions over asatellite broadcast system. The system is expected to deliver messages of widely varied length. Our objective is to find a scheduling algorithm that exhibits good delay performance for messages of all sizes. We show that classical scheduling algorithms such as First-Come-First-Serve and Round-Robin perform poorly in this environment. We study two alternative schemes. The first gives preemptive priority to the message with the Shortest Remaining Processing Time (SRPT). This scheme is known to minimize overall average message delays, but results in disproportionately large delays for long messages. The second scheme serves messages based on a dynamic priority function, where the priority of a message varies based on how long the message has been in the system as well as its length. This scheme results in somewhat larger overall average delays, but it is more fair to long messages.