MULTICAST SCHEDULING FOR INPUT-QUEUED SWITCHES

This paper presents the design of a scheduler for an M x N input-queue d multicast switch, It is assumed that: 1) each input maintains a sing le queue for arriving multicast cells and 2) only the cell at the head of line (HOL) can be observed and scheduled at one time, The schedule r is required to be: 1) work-conserving, which means that no output po rt may be idle as long as there is an input cell destined to it and 2) fair, which means that no input cell may be held at HOL for more than a fixed number of cell times, The aim of our work is to find a work-c onserving, fair policy that delivers maximum throughput and minimizes input queue latency, and yet is simple to implement in hardware, When a scheduling policy decides which cells to schedule, contention may re quire that it leave a residue of cells to be scheduled in the next cel l time, The selection of where to place the residue uniquely defines t he scheduling policy, Subject to a fairness constraint, we argue that a policy which always concentrates the residue on as few inputs as pos sible generally outperforms all other policies, We find that there is a tradeoff among concentration of residue (for high throughput), stric tness of fairness (to prevent starvation), and implementational simpli city (for the design of high-speed switches), By mapping the general m ulticast switching problem onto a variation of the popular block-packi ng game Tetris, we are able to analyze, in an intuitive and geometric fashion, various scheduling policies which possess these attributes in different proportions, We present a novel scheduling policy, called T ATRA, which performs extremely well and is strict in fairness. We also present a simple weight-based algorithm, called WBA, that is simple t o implement in hardware, fair, and performs well when compared to a co ncentrating algorithm.