AN INCREMENTAL ALGORITHM FOR TDM SWITCHING ASSIGNMENTS IN SATELLITE AND TERRESTRIAL NETWORKS

We present an incremental algorithm for scheduling traffic in a general class of time division multiplexed (TDM) switching systems employed in satellite and terrestrial communication networks. This class of switching systems, known as hierarchical switching systems (HSS's), has a three-tiered structure with one stage of concentration followed by switching and distribution. Instead of recomputing the time slot assignment (TSA) for each frame of traffic, our algorithm computes a TSA for a new frame by modifying the known TSA of the previous frame. The algorithm takes O(M2 + cM) time for finding an optimal TSA in a hierarchical switching system, where M is the number of users and c the number of changes between the traffic demands of two consecutive frames. The algorithm uses a two-step process. The first step transforms the TSA problem in the HSS into an equivalent TSA problem in a simple TDM switching system. The second step uses an incremental algorithm to find a TSA for the latter. The second step exploits the correspondence between the TSA problem and the rearrangement problem in a Clos three-stage network. When the traffic demands in consecutive frames overlap to a significant extent, the incremental algorithm provides considerable speedup over previous algorithms.