FIFO-based multicast scheduling algorithm for virtual output queued packet switches Article

Pan, D, Yang, Y. (2005). FIFO-based multicast scheduling algorithm for virtual output queued packet switches . IEEE TRANSACTIONS ON COMPUTERS, 54(10), 1283-1297. 10.1109/TC.2005.164

cited authors

  • Pan, D; Yang, Y

authors

abstract

  • Many networking/computing applications require high speed switching for multicast traffic at the switch/router level to save network bandwidth. However, existing queuing-based packet switches and scheduling algorithms cannot perform well under multicast traffic. While the speedup requirement makes the output queued switch difficult to scale, the single input queued switch suffers from head of line (HOL) blocking, which severely limits the network throughput. An efficient yet simple buffering strategy to remove the HOL blocking is to use the virtual output queued (VOQ) switch structure, which has been shown to perform well under unicast traffic. However, the traditional VOQ switch is impractical for multicast traffic because a VOQ switch for multicast traffic has to maintain an exponential number of queues in each input port (i.e., 2N - 1 queues for a switch with N output ports). In this paper, we give a novel queue structure for the input buffers of a multicast VOQ switch by separately storing the address information and data information of a packet so that an input port only needs to manage a linear number (N) of queues. In conjunction with the multicast VOQ switch, we present a first-in-first-out based multicast scheduling algorithm, FIFO Multicast Scheduling (FIFOMS), and conduct extensive simulations to compare FIFOMS with other popular scheduling algorithms. Our results fully demonstrate the superiority of FIFOMS in both multicast latency and queue space requirement. © 2005 IEEE.

publication date

  • October 1, 2005

published in

Digital Object Identifier (DOI)

start page

  • 1283

end page

  • 1297

volume

  • 54

issue

  • 10