Efficient time slot assignments for TDM multicast switching systems

This paper focuses on designing efficient multicast time slot assignment (MTSA) algorithms for TDM switching systems. Based on a packet compatibility matrix, the MTSA can be transformed to the well-known graph-coloring problem. We thus show that the MTSA problem is NP-complete. A lower bound on the frame length of a multicast time slot assignment is then found to be the clique number of the MTSA equivalent graph. Two efficient MTSA algorithms, called the contention-based ordering (CBO) algorithm and the hybrid ordering algorithm, are proposed. Their performance is compared with the three existing algorithms and the lower bound through extensive simulations. We found that the CBO algorithm, which has one of the lowest computational complexities, gives the best performance among all five algorithms studied. The average frame length generated by the CBO algorithm is within 1% above the lower bound. We also show that (i) the previously reported DAC algorithm has the poorest performance despite its highest complexity, and (ii) the previously reported CCBO algorithm has only a comparable performance to the simple greedy algorithm. © 1997 IEEE