Efficient time slot assignment algorithms for TDM hierarchical and nonhierarchical switching systems

Two efficient time slot assignment algorithms, called the two-phase algorit hm for the nonhierarchical and the three-phase algorithm for the hierarchic al time-division multiplex (TDM) switching systems, are proposed. The simpl e idea behind these two algorithms is to schedule the traffic on the critic al lines/trunks of a traffic matrix first. The time complexities of these t wo algorithms are found to be O(LN2) and O(LM2), where L is the frame lengt h, N is the switch size, and M is the number of input/output users connecte d to a hierarchical TDM switch. Unlike conventional algorithms, they are fa st, iterative and simple for hardware implementation, Since no backtracking is used, pipelined packet transmission and packet scheduling can be perfor med for reducing the scheduling complexity of a transmission matrix to O(N- 2) and O(M-2), respectively, Extensive simulations reveal that the two prop osed algorithms give close-to-optimal performance under various traffic con ditions.