Timotheos Aslanidis and Leonidas Tsepenekas, National Technical University of Athens, Greece

In an era where communication has a most important role in modern societies, designing efficient algorithms for data transmission is of the outmost importance. TDMA is a technology used in many communication systems such as satellites and cell phones. In order to transmit data in such systems we need to cluster them in packages. To achieve a faster transmission we are allowed to preempt the transmission of any packet in order to resume at a later time. Such preemptions though come with a delay in order to setup for the next transmission. In this paper we propose an algorithm which yields improved transmission scheduling. This algorithm we call MGA. We have proven an approximation ratio for MGA and ran experiments to establish that it works even better in practice. In order to conclude that MGA will be a very helpful tool in constructing an improved schedule for packet routing using preemtion with a setup cost, we compare its results to two other efficient algorithms designed by researchers in the past.

Communication networks, setup delay, preemption, packet routing