AN ADAPTIVE SCHEDULING ALGORITHM FOR TDM SWITCHING SYSTEMS

In this paper, we consider the scheduling problem in time-division mul tiplexed (TDM) switching systems. In previous works, the interdependen ce between traffic demands in two consecutive frames is neglected, and scheduling algorithms found up to now have time complexities O(N-5) o r O(N-4.5), where N is the switch size. However, in many applications like voice or video communications, if a source transmits a packet to a destination in a frame, it is highly probable that it will also tran smit a packet to the same destination in the next frame. So it is not necessary to schedule incoming packets for every frame it we can prese rve all the switching patterns for the nearest scheduled frame and upd ate the patterns appropriately according to the changes of traffic dem ands. The adaptive algorithm proposed in this paper assigns time slots to packets according to the changes of traffic demands. This algorith m has the worst case time complexity O(N-2 L), where L is the TDM fram e length. Comparing the time complexity of the adaptive algorithm with those of previous scheduling algorithms, the adaptive algorithm can p erform better than previous scheduling algorithms when N is large and/ or L is small. Since traffic demands in consecutive frames are expecte d to be interdependent in many applications, the proposed algorithm ma y offer as an efficient alternative for scheduling time slots in these applications.