Document Type

Technical Report

Publication Date

2005-04-22

Filename

WUCSE-2005-14.pdf

Technical Report Number

WUCSE-2005-14

Abstract

Crossbar-based switches are commonly used to implement routers with throughputs up to about 1 Tb/s. The advent of work-conserving crossbar scheduling algorithms now makes it possible to engineer sys-tems that perform well, even under extreme traffic conditions. Unfortunately, all the published work-conservation results for crossbar scheduling apply only to systems that switch fixed-length cells, not variable length packets. Routers that use a cell-based crossbar with a nominally work-conserving scheduler to switch variable length packets can fail to be work-conserving at the external links, since the router cannot forward a packet until all of its constituent cells reach the output line card. Speedups as large as the number of inputs and outputs can be required to achieve work-conservation, using schedulers that operate only on cells. There appear to be fundamental obstacles to achieving practical work-conservation for variable length packet switches based on unbuffered crossbars. However, we show that adding buffers to crossbars allows work-conservation to be achieved for variable length packet switching, using modest speedups. In particular we define packet versions of the Group by Vir-tual Output Queue (GVOQ) scheduler of Chuang et. al. and the Least Occupied Output First (LOOFA) scheduler of Krishna et. al. and show that they are both work-conserving for speedups ≥2. Specific versions of both algorithms are also shown to be order-preserving for speedups ≥2, meaning that they can exactly emulate an ideal, output queued switch.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7G15Z5N

Download

Share

COinS