corresponds, for example, to a cell header, a frame header, or a packet header, will automatically be routed to the corresponding output. The switch does this by reading and applying one bit at a time extracting bits from the header and doing SO for each stage. For example, an arriving input sequence as the header of a frame containing the bits 010 in the arrangement of Figure 14.11(b) will mean that in the first stage, the first 0 (read from the left) will be used to route traffic to the bottom output lead. Then the second bit of the sequence, here a 1, will be used to further route the path to the top output lead of the second stage (wherever this stage might be in the web network). Finally, the 0 will be used in the last stage to route the connection to the bottom lead of the last stage. The switching path has thus been produced between the input and output based on the address header of the frame. These networks are discussed in more detail in the fundamental switching literature listed at the end of the chapter. Batcher-Banyan Switches Banyan switches have earned the reputation of being efficient, but they can suffer from internal block- ing, which requires buffering to avoid possible traffic loss by discarding packets. This situation can be avoided if no idle input exists between any two active inputs and if the output addresses of cells/frames are sorted in either ascending or descending order. Once a special network presorts the frames/cells, they can safely enter the Banyan-based fabric core. Such a presorting-based topology is called the Batcher-Banyan switch. The sorting network is based on the Batcher architecture, which combines multiple simpler merge networks (all the way down to simple 2X2 modules) that sort their FIGURE 14.11 (a) Binary tree topology (b) Banyan class network. Downloaded from Digital Engineering Library @ McGraw-Hill (www.digitalengineeringlibrary.com) Copyright © 2004 The McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. SW