Performance analysis of large multicast packet switches with multiple input queues and gathered traffic

The well-known head-of-line blocking compromises the performance of input-queued switches with single first-in-first-out (FIFO) queue per input port. For unicast traffic, the virtual output queueing technique can be used to completely avoid the head-of-line blocking. However, since a multicast packet typically has more than one destination, the exhaustive multicast virtual output queueing is impractical and results in out-of-order delivery. One interesting approach to alleviate the head-of-line blocking is to allocate a certain number of FIFO queues at each input port. In this paper, we theoretically analyze the performance of large multicast packet switches with multiple FIFO queues per input port and gathered traffic. With the gathered-traffic scenario, multicast flows gather among fewer input ports and engage more output ports. A model of Markov chain is proposed in this paper to deduce the probability distribution function of residue size at the beginning of a time slot and analyze the probability that an input port is available after a certain number of iterations’ competition for service. The closed-form expressions are deduced for saturation throughput, average service time, and average delay for an M × N switch, where both M and N   are assumed to be large numbers. Extensive simulations are preformed to verify the theoretical analysis. Numerical results are studied to compare the performance of multicast switches under different configurations. Our theoretical analysis and simulation studies indicate that (1) a small number of queues (e.g., 10 queues in the cases studied in this paper), which is much less than 2N-12N-1, are a reasonable choice for the tradeoff between the scheduling overhead and the saturation throughput and delay performances; (2) the saturation and delay performances decrease as the traffic gathers among fewer input ports; (3) the analytical results based on the assumption of large switch size are valid for practical large-sized switches.