Broadband Packet Switching Technologies: A Practical Guide to ATM Switches and IP Routers

CHAPTER 5

BANYAN-BASED SWITCHES

The very early theoretical work on multistage interconnection networks (MINs) was done in the context of circuit-switched telephone networks [7, 4]. The aim was to design a nonblocking multistage switch with number of crosspoints less than in a single-stage crossbar switch. After many such networks were studied and introduced for interconnecting multiple processors and memories in parallel computer systems, several types of them, such as banyan and shuffle-exchange networks, were proposed [20, 12, 21] as switching fabrics because in them several cells can be routed in parallel and the switching function can be implemented regularly in hardware.

In this chapter, we describe banyan-family switches, which have attracted many researchers, over more than two decades, for building interconnection networks. Section 5.1 classifies banyan-family switch architectures according to their nature and properties. Section 5.2 describes Batcher-sorting network switch architecture. Section 5.3 introduces Output-contention resolution algorithms in banyan-family switches. Section 5.4 describes the Sunshine switch, which extends the Batcher-banyan switching architecture. Section 5.5 describes some work on deflection routing over banyan-family networks. Section 5.6 introduces ...