Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL


13.4 The Take-a-Ticket Crossbar Scheduler 307 to handle. These sources and destinations add extra electrical loading that slows down signal rise times and ultimately the speed of sending bits on the bus. Other electrical effects include that of multiple connectors (from each line card) and reflections on the line [McK97]. The classical way to get around this bottleneck is to use a crossbar switch, as shown in Figure 13.3, part d. A crossbar switch essentially has a set of 2N parallel buses, one bus per source line card and one bus per destination line card. If one thinks of the source buses as being horizontal and the destination buses as being vertical, the matrix of buses forms what is called a crossbar. Potentially, this provides an N-fold speedup over a single bus, because in the best case all N buses will be used in parallel at the same time to transfer data, instead of a single bus. Of course, to get this speedup requires finding N disjoint source­destination pairs at each time slot. Trying to get close to this bound is the major scheduling problem studied in this chapter. Although they do not necessarily go together, another design change that accompanied crossbar switches designed between 1995 and 2002 is the use of special-purpose integrated circuits (ASICs) as forwarding engines instead of general-purpose CPUs. These forwarding engines are typically faster (because they are designed specifically to process Internet pack- ets) and cheaper than general-purpose CPUs. Two disadvantages of such forwarding engines include design costs for each suchASIC and the lack of programmability (which makes changes in the field difficult or impossible). These problems have again led to proposals for faster but yet programmable network processors (see Chapter 2). 13.4 THE TAKE-A-TICKET CROSSBAR SCHEDULER The simplest crossbar is an array of N input buses and N output buses, as shown in Figure 13.4. Thus if line card R wishes to send data to line card S, input bus R must be connected to output bus S. The simplest way to make this connection is via a "pass" transistor, as shown in Figure 13.5.