Abstract
Scheduling algorithms for multicast packets in single-hop WDM networks can be classified into three categories, namely, random-access based, pre-allocation based and reservation-based scheduling algorithms. Reservation-based scheduling algorithms can be further classified as one-by-one scheduling or batch scheduling depending on whether reservation requests are processed one at a time or a batch at a time. In this thesis, we focus on the reservation-based multicast scheduling algorithms. Our goal is to develop the multicast scheduling algorithms that produce lower mean packet delay. We first investigate a batch-scheduling scheme which does not partition a multicast transmission into multiple unicast or multicast transmissions. The key to produce low average packet delay is to minimize the number of data slots used for scheduling a batch of multicast packets. The problem is formulated as a minimization problem and shown to be NP-complete. A heuristic multicast scheduling algorithm is proposed for this problem. The simulation results show that the proposed scheduling algorithm produces significantly lower mean packet delays when the load of the system is medium to heavy. Next, we investigate a one-by-one scheduling scheme in which partitioning a multicast transmission into multiple unicast or multicast transmissions is allowed. The problem of minimizing the number of transmissions for a multicast transmission under the condition that the packet delay is minimum in single-hop WDM networks is studied. This problem is proved to be NP-complete. A heuristic multicast scheduling algorithm, namely, maximum-available-destination scheduling algorithm, is proposed for this problem. Extensive simulations are performed to compare the performance of the proposed heuristic algorithm with two other multicast scheduling algorithms, namely, the greedy and no-partition scheduling algorithms. The greedy algorithm schedules as many destination nodes as possible at the earliest data slot. The no-partition algorithm schedules the destination nodes of a multicast packet to receive the packet in the same data slot without partitioning the multicast transmission into multiple unicast or multicast transmissions. Our simulation results show that the proposed heuristic algorithm produces lower mean packet delay than the greedy and no-partition scheduling algorithms. Finally, the performance of the greedy scheduling algorithm and the no-partition scheduling algorithm are further studied. We show that the greedy scheduling algorithm may not always produce lower mean packet delay than the no-partition scheduling algorithm. The reason for this phenomenon is analyzed using several examples. The performance of a multicast scheduling algorithm may depend on the traffic conditions (e.g., the load, the maximum multicast group size, the percentage of unicast traffic, and etc.) and the availability of the channel resource in the network. A hybrid multicast scheduling algorithm that can produce good performance for wide ranges of the traffic conditions and the availability of the channel resource in the network is proposed. Depending on the average utilizations of the data channels and the receivers, the proposed hybrid multicast scheduling algorithm dynamically chooses to employ a multicast scheduling algorithm which always tries to partition multicast transmissions or a multicast scheduling algorithm which does not partition multicast transmissions. Extensive simulations are performed to study the performance of the proposed hybrid algorithm. Our simulation results show that the proposed hybrid algorithm produces lower mean packet delay for wide ranges of the load, the maximum multicast group size, the percentage of unicast traffic, and the number of data channels in the network compared with a multicast scheduling algorithm which always tries to partition multicast transmissions and a multicast scheduling which does not partition multicast transmissions.