The time slot assignment problem in time-division multiplexed switching systems which can support multicast transmissions is studied. It is shown that this problem is NP-complete, i.e., computationally intractable. Two effective heuristic algorithms are proposed, and computer simulations are also performed to evaluate the performance of both algorithms. The results of the simulations indicate that the solutions generated by these heuristic algorithms are very close to the optimal on the average. In addition, this problem is also examined under a more restrictive condition that the destination sets of any two multicast packets are either identical or disjoint, a situation often encountered in many practical applications. It is proved that this special problem is still NP-complete. Two fast heuristic algorithms are given, which can find solutions not greater than twice the optimal solution. Computer simulations for evaluating these two heuristic algorithms are also performed. Experimental results demonstrate that the solutions of the two algorithms are almost equal to the optimal.>

The time slot assignment problem is studied in time-division multiplexing (TDM) switching systems which can support multicast transmissions. It is shown that this problem is NP-complete, i.e., computationally intractable. Two effective heuristic algorithms are proposed. To evaluate and compare the performance of these algorithms, a lower bound on the solution of this problem is derived and computer simulations are performed. The results of simulations show that the solutions generated by these heuristic algorithms are close to this lower bound on the average.>

A pairwise switch-connection mechanism for interconnecting multiple token passing ring networks is proposed. The total number of internetwork packet store-and-forwards occurring at the bridges can be significantly reduced under the new switching method. A simple scheduling algorithm is developed to guarantee non-overlapped pairwise connection among the interconnected ring networks. Easy network access can be achieved through the use of different types of free tokens and local timers. Only simple table look-up operation is needed for the internetwork address translation. Therefore, the internetwork packets can be routed efficiently. Finally, simulation results are provided to show the fair network throughput under such switch-connection approach.>