Random algorithms for scheduling multicast traffic in WDM broadcast-and-select networks

We develop and analyze simple algorithms for scheduling multicast traffic i n wavelength division multiplexing (WDM) broadcast-and-select networks with N nodes, W wavelengths, and a single receiver per node that can be tuned t o any of the W wavelengths. Each message is addressed to k randomly chosen nodes. Since optimal message scheduling in a WDM network is known to be ver y difficult, we study two simple scheduling schemes: in the first, a messag e is continuously retransmitted until it is received by all of its intended recipients; and in the second, a random delay is introduced between retran smissions of the same message. We develop a throughput analysis for both sc hemes using methods from discrete-time queueing systems and show that the a lgorithm with random delays between retransmissions results in higher throu ghput. We also consider a number of receiver algorithms for selecting among multiple simultaneous transmissions and show, through simulation, that an algorithm where the receiver selects the message with the least number of i ntended recipients performs better than a random selection algorithm. Final ly, we show that channel utilization can be significantly increased with mu ltiple receivers/node.