HP Labs Technical Reports

Multicast Scheduling for Input-Queued Switches

Prabhakar, Balaji; McKeown, Nick; Ahuja,

HPL-BRIMS-96-16

Keyword(s): multicast; high-speed switch; tetris models; schedules

Abstract:The demand for network bandwidth is growing much faster than the increase in commercially available memory bandwidth, causing a growing interest in input-queued switches. Furthermore, an increase in the proportion of multicast traffic in today's networks makes it important that they support such traffic efficiently. This paper presents the design of the scheduler for an MxN input-queued multicast switch. It is assumed that: (i) Each input maintains a single queue for arriving multicast cells, and (ii) Only the cell at the head of the line (HOL) can be observed and scheduled at one time. The scheduler is required to be: (i) Work-conserving, which means that no output port may be idle as long as there is of residue (for high throughput), strictness of fairness (to prevent starvation), and implementational simplicity (for the design of {\em high-speed} switches). By mapping the general multicast switching problem onto a variation of the popular block-packing game, Tetris, we are able to analyse, in an intuitive and geometric fashion, various scheduling policies which possess these attributes in different proportions. We present a novel scheduling policy, called TATRA, which performs extremely well and is strict in fairness. We also present a simple weight based algorithm, called WBA, that is simple to implement in hardware, fair, and performs well when compared to a concentrating algorithm.

Back to Index