Given a network with one source and multiple destinations, the multicast delay variation problem attempts to construct a multicast tree such that the interdestination delay variation among all the paths from the source to each destination is minimized. In this paper, we show that the problem is NP-hard and that it is not approximable within a constant factor in polynomial time unless NP = P. These findings indicate that it is impossible to develop efficient optimal or approximation algorithms for any multicast routing problem under the interdestination delay variation constraint unless NP = P.

Cyclic-reservation multiple-access (CRMA) is an access scheme for high-speed local and metropolitan area networks based on folded-bus or dual-bus configurations. CRMA provides high throughput and fairness independent of the network speed or distance. In CRMA, the headend generates reserve commands periodically. Each station may reserve a number of empty slots in each reserve command if necessary. Corresponding to every reserve command, the headend generates a cycle of length equal to the total number of empty slots reserved. Every cycle is used to serve the reservations made on its corresponding reserve command. Generally, a longer cycle length means a longer access delay and a lower throughput. Therefore, it is desirable to develop a scheme such that the cycle length is the shortest. The authors study the problem of reducing the total number of empty slots generated within every cycle. However, it has been shown that the problem is NP-complete under the constraint that all the empty slots used by a station in a cycle are required to be consecutive. They release the slot-contiguity constraint and propose a fast optimal slot reuse scheme with low time complexity O(M/sup 2/), where M is the number of stations. To evaluate the effectiveness of the slot reuse scheme, a large number of computer simulations are performed. They compare the slot reuse scheme with the original CRMA in terms of the following three important performance measurements: average cycle length, average throughput, and average MAC delay.

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.>

Forward loop backward hop (FLBH) networks, characterized by a forward loop connecting all the adjacent nodes and a backward loop connecting nodes separated by a distance of h hops, have a higher connectivity and therefore a higher potential for fault-tolerance than single-loop networks. How to devise efficient fault-tolerant routing algorithms is an important issue on designing FLBH networks. This paper proposes two new fault-tolerant routing algorithms. One is for optimal FLBH networks with h/sup 2/=N, where N is the number of nodes. The other is for arbitrary FLBH networks (i.e., 1>