l0"
`
`
`
`dnaretupm0C
`Networks
`t
`
`ommunlca
`
`
`
`
`
`M I R
`EMC EXhi
`it 1033
`
`EMC V. Intellectual Ventures
`
`

`

`NETWORKS
`
`Nader F. Mir
`
`COMPUTER AND COMMUNICATION
`
`Sydney ' Tokyo ' Singapore ' Mexico City
`
`0.
`.0
`O.
`F‘ R E NTI C: E
`HALL
`
`Upper Saddle River, NJ ' Boston ' Indianapolis ' San Francisco ' New York
`Toronto ' Montreal
`' London ' Munich ' Paris ' Madrid ' Capetown
`
`

`

`Many ofthe designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where
`those designations appear in this book, and the publisher was aware ol‘a trademark claim, the designations have been printed
`with initial capital letters or in all capitals.
`
`The author and publisher have taken care in the preparation oi‘this book, but make no expressed or implied warranty ofany
`kind and assume no responsibility for errors or omissions. No liability is assumed For incidental or consequential damages
`in connection with or arising out ofthe use oFthe information or programs contained herein
`
`The publisher offers excellent discounts on this book when ordered in quantity For bulk purchases or special sales, which
`may include electronic versions and/or custom covers and content particular to your business, training goals, marketing
`focus, and branding interests. For more information, please contact:
`
`-- This Book Is Safari Enabled
`53151:!
`BOOKS ONLWE The Safari® Enabled icon on the cover ofyour favorite technology book means the book is available through
`Safari Bookshelf. When you buy this book, you get Free access to the online edition {0145 days,
`
`Safari Bookshelfis an electronic reference library that lets you easily search thousands ol‘ technical books, rind code samples,
`download chapters, and access technical information whenever and wherever you need it.
`
`To gain 45—day Safari Enabled access to this book:
`0 Go to http://www.prenhallprofessional.com/salarienabled
`0 Complete the briefregistration form
`0 Enter the coupon code VZGY—SBEH—4Q1D—KBIN—BXSB
`
`If you have difficulty registering on Safari Bookshelf or accessing the online edition, please e—mail customer—
`service@safaribooksonline.com.
`
`
`Visit us on the Web: www.prenhallprofessional.coni
`
`US. Corporate and Government Sales
`(800) 382—3419
`corpsales@pearsontechgroupcom
`For sales outside the United States, please Contact:
`International Sales
`international@pearsoned.com
`
`First printing, November 2006
`
`Library amezgrm Cataloging-in-Publlmlion Dam
`Mir, Nader F.
`Computer and communication networks / Nader F. Mir.
`p.
`cm,
`includes bibliographical references and index.
`ISBN 0—13—174799—1 (hardcover : alk. paper)
`1, Computer networks. 2. Data transmission systems,
`TK51055M567 2006
`004.6—dc22
`
`I, Title.
`
`2006025914
`
`Copyright © 2007 Pearson Education, Inc,
`
`All rights reserved. Printed in the United States ofAmerica. This publication is protected by copyright, and permission must
`be obtained from the publisher prior to any prohibited reproduction. storage in a retrieval system, or transmission in any
`form or by any means, electronic, mechanical, photocopying, recording, or likewise, For information regarding permissions,
`write to:
`
`Pearson Education, lnc.
`Rights and Contracts Department
`One Lake Street
`Upper Saddle River, N] 07458
`Fax: (201) 2363290
`ISBN 0-13-174799—1
`Text printed in the United States on recycled paper at RR. Donnelley in Crawfordsville, lndiana.
`
`

`

`
`Networks in Switch Fabrics
`
`CHAPTER 13
`
`
`T. . » - x
`
`
`
`
`
`
`
`
`A switc/afizkric is the core switching engine in switching devices as routers. Chapter 3
`
`presented an overview of switching devices. This chapter analyzes this core segment of
`such devices and introduces several topologies for switching networks.
`This chapter explores the following topics:
`
`' Characteristics andfeatures ofswitch fakrics
`
`' Crosskar switc/afakrics
`
`' Blocking switc/afizkrics
`
`' Nonklocking switc/afa/rrics
`
`' Concentration and expansion switc/aes
`
`' Shared—memory switc/afa/rrics
`
`' YEckniqnesfor improvingperj‘orrnance
`
`' Case study mnltipatk kit/fired crosskar
`
`We begin by classifying characteristics of switching networks and presenting fea—
`tures and definitions of switch fabrics. Crosskar switc/aes are the building blocks of
`switching fabrics, so all aspects of this switch are covered. The case study at the end of
`this chapter combines several buffered crosspoints to form a buffered crossbar. Block—
`
`ing switches are constructed with crossbar switches, including Omega networks, Banyan
`networks, Delta networks and Benesv networks. Nonblocking switches constructed with
`
`
`
`
`
`349
`
`

`

`350
`
`Chapter 13. Networks in Switch Fabrics
`
`crossbars include C105 networks. ContmtmtioriJmsed and expansion—based switching
`
`networks—two special—purpose switch fabrics—are investigated as well.
`A quite different approach for switching in time domain uses shared memory, with—
`
`out using any switch elements. Switch fabric techniques that offer better performance
`
`include the use of buffering, combined networks, and parallel-plane switching net—
`works.
`
`13.1 Characteristics and Features of Switch Fabrics
`
`The switching function takes place in the switching fabric. The switching structure
`
`depends on the need of network operation, available technology, and the required
`capacity. A switch fabric is an interconnected network ofsmaller switching units. Several
`
`factors can be used to characterize switching systems: buffering, complexity, capability
`of multipoint connections, speed, performance, cost, reliability, fault tolerance, and
`scalability. Here, we focus on the topology ofthe interconnection network as the heart
`
`ofmodern switching systems. The key factors for classifying switching networks are
`
`' Single path versus multipath
`
`' Fixed interstages versus variable interstages
`
`' Deflection routing versus packet discard
`
`' Blocking versus nonblocking
`
`path to be rerouted. A network is rearranged/91y nonblocking if, for connecting an input
`
`has exactly one route between each input port and output port. However, this property
`can be a source oftraffic congestion and traffic blocking. In a multipath network, any
`connection can be established through more than one path. Each ofthese two groups
`of networks can be further classified as either single—stage or multistage networks. In a
`single-stage network, a connection is established through one stage ofswitching; in a
`multistage network, a packet must pass through several switching stages. In a multistage
`network, the number of stages often grows with increasing network size.
`
`Switching networks are either single—path or multipath networks. A single—path network
`
`13.1.1 Blocking and Nonblocking Networks
`
`A switching network is said to be blocking ifan input port cannot be connected to an
`unused output port. Otherwise, the switching network is nonblocking. A nonblocking
`
`switching network can be either of two types. A network is wide—same nonblocking
`if any input port can be connected to any unused output port without requiring a
`
`

`

`
`
`13.1 Characteristics and Features 0? Switch Fabrics
`
`351
`
`port to an unused output port, rearranging other paths may be required. A wide—sense
`nonblocking network is strictly nonblocking if there is an idle path from any idle input
`to idle output for all states of the network. Rearangeably nonblocking architectures
`have a more complex control algorithm to make connections, since fewer switches are
`used. The complexity of the routing algorithm is a trade—off with cost.
`
`13.1.2 Features of Switch Fabrics
`
`Switching networks have several features and options.
`
`' Switching networks may be either bufihed or iméiifiiered. Buffers may be used to
`reduce traffic congestion.
`
`' To regulate the flow of packets and prevent buffer overflow, flow control can be
`
`provided between stages in a multistage network.
`
`° Discard versus deflection. At each stage ofa switching network, a conflict may arise if
`several packets request the same output. In networks without flow control, arriving
`packets that cannot be buffered can be either discarded or deflected. Or, these two
`methods can be combined in a switch.
`
`0 Modern switching networks are expected to have the capability of mtdtierzstingm
`copying to any subset of the outputswalong with broadcasting.
`
`13.1.3 Complexity of Switching Networks
`
`A useful measure for approximating the cost of a network is to consider the number
`of crosspoints and links. In practice, the number of crosspoints has greater impact
`on the cost of the switching network. Thus, complexity refers to the total number of
`crosspoints used in a switching network. It is important to note that the integrated
`circuit pin constraints also influence implementation oflarge—scale networks, especially
`those with parallel data paths. Practically, a switching network or portions of a network
`
`can be placed entirely on a single integrated circuit package. In such cases, the area
`occupied by the circuits becomes an important complexity measure.
`
`
`
`13.1.4 Definitions and Symbols
`
`The topic of switch networking entails a number of definitions and symbols. Consider
`a network, N, with n inputs and m outputs. This network is referred to as an (n, m)
`network. An (n, n) network is referred to as an n network. A connection for a given
`network is identified by (x, y), where x is an input port and y is an output port. Inputs
`and outputs to a network are numbered in decimal or binary, starting from 0. Switch
`
`
`
`
`
`

`

`352
`
`Chapter 13. Networks in Switch Fabrics
`
`is the
`is the stage number of the switch, and
`elements are labeled by (i, j), where i
`location of the switch in that stage. We use (i, j)h to identify input or output port 12
`on switch (i, j).
`
`A network is zmzfirm if all switch elements have the same dimensions and is square
`ifit has the same number ofinputs and outputs. The mirror ofa network N is denoted
`N’" and is obtained by exchanging inputs and outputs and reversing the directions of
`all links. Consider network N1 with n1 outputs and network N2 with r12 inputs. The
`concatenation of two networks N1 and N2 is represented by N1 + N2 and is realized
`by using output i of N1 through input i of NZ. Iii is a positive integer and N is an
`(n, m) network, LN realizes the network obtained by taking i copies of N, without
`interconnecting them. The product term N1 >< N2 is the series connection of N1 and
`N2 and is defined by
`
`particular input/output pair.
`
`Crossed)” switches are the building blocks of switching fabrics. A crossbar switch with 1'2.
`inputs and n outputs is shown by XHW. Figure 13.1 shows a X44, or a 4X4 crossbar
`switching fabric. In a crossbar, every input can be uniquely connected to every output
`through a erosspoz'm. A crosspoint is the smallest unit ofthe switching function and can
`be built using a variety ofelectronic or digital elements, such as photodiodes, transistors,
`and AND gates.
`Crossbar switches are considered strictly (wide—sense) nonblocking, as a dedicated
`crosspoint exists for every connection. This is clearly an attractive feature of a crossbar.
`The blocking, however, may occur when multiple packets are sent to the same output
`simultaneously. If a particular output port of the crossbar is idle, the desired connec—
`tion can always be established by selecting the particular crosspoint dedicated to the
`
`N1 >< N2:(IZZ.N1)+¢111,HZ+(l11.N2),
`
`(13.1)
`
`where qfinl’flz is the permutation among I11 and 122 points. Similarly, for network N1
`with 111 outputs, network N2 with F12 inputs and n3 outputs, and network N3 with 111
`inputs, the product term N1N2N3 is defined as
`
`N1N2N3 :(nZ'N1)+¢/11,nz + (nl'NZ) + $225,111 + (’13'N3)
`
`and is called the parallel connection of‘Nl and N2.
`
`13.2 Crossbar Switch Fabrics
`
`

`

`
`
`13.3 Blocking Switch Fabrics
`
`
`
`n
`
`Inputs
`
`l’l
`
`Outputs
`
`
`
`Crossbar switches are conceptually simple. Their only potential problem is output
`port contention. The complexity of a switch lies in the complexity of its crosspoints.
`For an n X n crossbar, the complexity rises in a quadratic fashion and is equal to 122
`crosspoints. By some clever design work, the complexity can be reduced at the price of
`bringing certain blocking into the switching.
`
`Figure 13.1 A crossbar switching fabric with n 2 4 inputs/outputs
`
`13.3 Blocking Switch Fabrics
`
`it may also be used
`Although, a crossbar can be deployed solely as a switch fabric,
`to construct other multistage switch fabrics, with the trade—off of cost versus higher
`blocking. This section looks at types of blocking switches: Omega networks, Banyan
`networks, Delta networks, and Benesv networks.
`
`13.3.1 Omega Network
`
`The Omega network, 9,1,4, is shown in Figure 13.2 (21). Using 52(1),, 2 Xd’d, we define
`the Omega network by
`
`971,11: ¢n/d.d + (n/d'Xcl,d) + ¢(/,rz/(l + (d'Qn/(l,(1)‘
`
`

`

`Chapter 13. Networks in Switch Fabrics
`
`Figure 13.2 (a) An Omega network with an example of its routing; (b) a Banyan network with an
`example of its routing
`
`In an Omega network, only one route exists between each input ix and output 0x. This
`fact explains the potential for blocking. The path uniqueness in this network can be
`shown by the induction on the number of stages, S. The number of stages is exactly
`
`and is achieved by comparing bit by bit between a source address and a destination
`
`S =logd n.
`The Omega network has some useful unique properties. One is that the intercon—
`nection segment between each two consecutive stages is identical to that of all other
`segments. Each of these identical interconnection segments is configured with a s/auf—
`fling property. The shuffling property is easy to understand: An interconnection link
`starting at the output number of a given crossbar stage ends at the input of the next
`crossbar stage with the same number but one step rotated to left. For example, consider
`the second interconnection segment between stages 1 and 2. In this segment, suppose
`that we are interested in finding the address of the crossbar input this link is connecting
`to. According to the rotation property, this address is obtained by one left rotation of
`010, which results in 100.
`
`The Omega network is also self—routing. The routing in this network is very simple
`
`

`

` 13.3 Blocking Switch Fabrics
`
`
`355
`
`
`
`address. At each stage, we look at the corresponding bits, starting at the most~significant
`
`bit (MSB) of the source and the destination addresses. If bits are the same, a message
`passes through; otherwise, it is crossed over. For example, consider a case with the
`
`source address 010 and the destination address 110, as shown in Figure 13.2. In the
`first stage, the message is crossed over, as the M8135 of the two addresses are different (0—
`1). In the second stage, the next corresponding bits are the same (1—1), so the message
`is sent straight along the crossbar. The case for the third stage is also the same as for the
`second stage but with corresponding bits of 0—0.
`
`Using the method of blocking probability estimation presented in Section 7.6.4,
`we can easily obtain an estimation of blocking for the Omega network. Finding all the
`
`paths that connect any given input to a given output and assigning p to each and every
`link of paths as the blocking probability of that link, estimate the blocking probability
`for an Omega network, 52,1)(1, to be 1 — (1 — p)s‘1, where s = logd n.
`
`13.3.2 Banyan Network
`
`The Banyan network, Y” ) d, as shown in Figure 13.2 (b), is similar to the Delta network.
`Using Yd’d = XdJ], we define the Banyan network by
`
`Yn,d : ¢fl/(1,(l+ ("/d-Xd,d) + ¢d,n/tl + (d-Yn/d,(l)-
`
`The Banyan network has some useful unique properties. Similar to the Omega network,
`the Banyan network also has the property ofself—routing. Identical to Omega networks,
`the blocking probability for a Banyan network, 3,111, is estimated to be 1 — (1 — p)s—1,
`where S = logd n.
`
`13.3.3 Delta Networks
`
`The Delta network consists of a network of crossbar switch elements with shared
`
`crosspoints, thus raising the possibility of blocking. The Delta network Dmtl, using
`d X d crossbars, Xd‘d, and with n input/output ports, is defined by
`
`Dn,(1= X(l,d X Dn/dfl'
`
`In a Delta network, only one route between each input ix and output 0,. exists.
`This fact explains the fundamental reason for blocking. The path uniqueness in this
`network can be shown by the induction on the number of stages, 5. The number of
`stages is exactly 5 = log(I 11. As with Omega networks, the blocking probability for a
`Delta network, Dull, is estimated to be 1 — (1 —— p)“—1
`,where s = logd n.
`Ifs = 1, the network becomes Ddfli, or simply a crossbar. For S > 1, the output 0x
`belongs to one of d subnetworks denoted by Dn/d’d. Let SI be the first—stage switch,
`
`
`
`

`

`Chapter 13. Networks in Switch Fabrics
`
`Figure 13.3
`
`(a) A 08.2 Delta network with the realization of its routing; (b) extension of the Delta
`network to a 88,; Benes
`
`(13.6)
`
`in which ix is an input. Since there is only one link] connecting 51 to the subnetwork
`containing 0x, the only route connecting ix to 0x is the route consisting of ix, together
`with the route connecting Z to 0x, which is unique. As seen in Figure 13.3, the Delta
`network self—routing. A path from any input ix to output 0y is performed by selecting
`links determined by successive digits of olys label. This process is also reversible, so we
`can route from output 0v back to ix by following the links determined by successive
`digits of i1.3 label.
`
`13.3.4 Benes Networks
`
`The Bane} network consists of a combination of two networks: a Delta network and
`its mirrored overlapped in one stage, as shown in Figure 13.3. This network is capable
`of realizing all possible input/output permutations and is defined by Bdfl : Xd) d and
`expanded by
`
`Bad = X(I,dBn/d,dXd,d'
`
`

`

`The recursive structure of the network leads us to decomposition of the routing
`problem into a set of smaller problems corresponding to each of the stages in the
`recursion. The top—level problem consists of selecting, for each connection, one of the
`d subnetworks Bn/(Ad to route through. The routing problems for the d subnetworks
`can be solved independently The following algorithm can be used to route a packet to
`a specific output port:
`
`CSJI‘k:X£{,kXII/(/,I1/11Xk,d‘
`
`13.4 Nonblocking Switch Fabrics: Clos Networks
`
`357
`
`Define:
`d
`Crossbar switch eiement dimension
`
`log, n,
`k
`Number of stages, r = 2 logd n — 1
`r
`Stage number, j e {1, 2,
`r}
`j
`A Output address of packet
`Address in stage j
`[U
`Bit vector specifying outputs that receive copies
`
`W B
`
`egin Benes Network Routing Algorithm
`For 13 j 5 k ~ 1 =>
`aj 2 random number 6 [0, d — 1]
`
`With this algorithm, packets in the routing network are guided to the requested
`outputs. As a result ofits structure using Delta networks, we can derive the complexity
`of the Benes network by
`
`X, = :17(210gdn ~ m2 = nd(210gdn — 1)
`
`(13,7)
`
`knowin
`
`that
`
`11-
`d
`g
`complexity 0ch X d crossbars.
`
`is the number of crossbar switches
`
`er sta e and that d2 is the
`g
`
`P
`
`13.4 Nonblocking Switch Fabrics: Clos Networks
`
`Figure 13.4 shows a C10: network with n = 8 inputs, d = 2, and k = 5. If the number
`of middle‘stage crossbar switch elements k is greater than or equal to 261 M 1, C3’ d, k
`is strictly nonblocking. Let d and k be integers with 2 f d f k. The three—stage Clos
`network Clid’k is defined by
`
`

`

`Chapter 13. Networks in Switch Fabrics
`
`Figure 13.4 A Clos network with n = 8 inputs, (1 = 2, and k 2 5
`
`the three—stage Clos network is
`
`The proof of this claim can be derived by first observing that a connection through
`the three~stage switch requires a middle—stage switch element having an idle link from
`the first stage and an idle link to the third stage, as shown in Figure 13.5. In CS’d’k, we
`search for a route realizing a connection request from input x to output y. Thus, the
`number of outputs of the stage 1 switch elements containing input x that are busy is
`at most d — 1. This means that there are at most d — 1 middle—stage switch elements
`that are not accessible form )6. Similarly, there are at most (Z —- 1 middle—stage switch
`elements that are not accessible from y.
`Clearly, there are at most 2d —— 2 middle—stage switches that are either not accessible
`from x or not accessible from y. Hence,
`the worstwcase situation for blocking is
`that these two sets of middle-stage switch elements are unavailable for connection
`request (x, y). However, if one additional free middle‘stage switch element exists
`as shaded in the figure, that element can be used to set up the connection (x, y).
`Hence ifk = (d -— 1) + (d —~ 1) + 1: 2d -— 1, the switch is strictly nonblocking. More
`generally, at least one middle—stage switch that is accessible from both sides or a state
`that blocks connection request (x, y) can be found ifk 3 2d — 1. The complexity of
`
`

`

`13.4 Nonblocking Switch Fabrics: Clos Networks
`
`Figure 13.5 Analysis of blocking in the three-stage Clos network
`
`(13.11)
`
`In order to find the complexity of the Clos network under nonblocking conditions,
`we can substitute k = 2d — 1 in Equation 13.9. Thus, the complexity ofa nonblocking
`network, X2'17 ', becomes
`
`Xf-b-=(2d—1) 2n+ g—
`
`.
`
`(13.10)
`
`It is always useful to optimize the complexity of switching networks, especially for
`the nonblocking Clos networks, in which finding the best d would be beneficial. To
`achieve this goal, we can optimize the network by
`
`8X2“
`8d
`
`3
`3d
`
`(2d— 1) 2n+ g—
`
`.
`
`

`

`Chapter 13, Networks in Switch Fabrics
`
`Figure 13.6 A blocking model for Clos switching network
`
`This procedure releases (1 = a/ n / 2, which is the absolute minimized value of d. The
`optimized crosspoint count under this optimization, therefore, is
`
`Wh:MMJE—D.
`0,01)!
`
`nun
`
`first node, we want the external and internal traffic to be equal, such that kpl = (11) or
`
`To estimate the internal blocking probability of a Clos network, consider d X k switch
`elements in the first stage. Figure 13.6 shows a probability graph of a three—stage
`network. All possible internal paths for an input/output connection pair are shown. For
`the middle—stage crossbars, the blocking—probability estimation for n parallel links, each
`with probability p, is generally B = p"; for a series ofrz links, the blocking probability
`is generally 8 = 1 —— (1 — 1))”. To apply this rule, let p1 be the probability that an
`internal link is busy, as shown in the figure, and thus 1 - [)1 is the probability that a
`link is idle. Then, B, the internal blocking probability of the switching network, or the
`probability that all paths are busy, is
`
`the number of crosspoints for large three—stage switches is still quite
`However,
`prohibitive. Large switching systems typically use more than three stages to provide
`greater reductions in crosspoints. Three—stage Clos networks can be enhanced by
`substituting another three—stage Clos network for the middle—stage crossbars, resulting
`in a five—stage Clos network. We can continue in this fashion to construct networks
`with many stages.
`
`1&41 EfihnafionomecMnglWobabMfies
`
`Bzu~n—mflh
`
`nun
`
`We want the traffic load to balance at both sides of each node. Specifically, at the
`
`

`

`13.5 Concentration and Expansion Switches
`
`pl 2 p(d/ k). Using this and Equation (13.13) leads to B in terms ofp:
`k
`
`B = [1~— <1- pal/W]
`
`,
`
`(13.14)
`
`For a Clos network with k = 8, d = 8, and p = 0.8, find the internal
`Example.
`blocking probability.
`
`Solution. Obviously, k/d = 1, and therefore the internal blocking probability B =
`(1 — (1 —- 0.8)2)8 : 072.
`
`For the Clos network presented in the previous example, if we add up to
`Example.
`100 percent more crossbar switches into the middle stage of the network, how much
`reduction in internal blocking probability do we obtain?
`
`Since k = 16, d = 8, and p = 0.8, then k/d :2 2, and thus B 2 ((1 —-
`Solution.
`(1 — 0.8 X 1/2)2)16 : 0.0008. The impact is remarkable, as the internal blocking
`probability is reduced 900 times.
`
`13.4.2 Five-Stage Clos Networks
`
`of output ports is more than the number ofinput ports.
`
`Figure 13.7 shows a five—stage Clos network obtained by replacing every middle-stage
`switch element in a three—stage Clos network. This structure provides less complexity,
`as the complexity of each middle three—stage network has been reduced as was explained
`for a three-stage network. Note that this statement can be true only if a five—stage switch
`is strictly nonblocking, where [(1 3 2d1 -— 1 and also [(2 3 2(12 —- 1. This type ofdesign
`is especially useful for 1arge~scale switching systems, in which a substantial reduction in
`the overall complexity of a network is targeted. The blocking probabiiity of a five—stage
`network is modeled in Figure 13.8 and is determined as follows:
`
`Bz:{1~(1—p1)2[1—(1—(1—192)2)k3]}k1.
`
`(15.15)
`
`13.5 Concentration and Expansion Switches
`
`This section introduces switching networks that either expand or concentrate incoming
`traffic. In a concentration—based switching network, the number of output ports is less
`than the number of input ports. In an expansion—based switching network, the number
`
`

`

`_.________._——.‘
`
`Figure 13.8 A blocking mode! for the five-stage Clos network
`
`Figure 13.7 Constructing a five-stage Clos network by using three-stage networks to reduce blocking
`probability.
`
`

`

`Outputs
`
`Figure 13.9 The knockout switching network
`
`13.5.1 Knockout Switching Network
`
`Otherwise, a losing packet is knocked out to the next column of switch elements for
`
`One of the simplest concentration switching networks is called a knockout switck, shown
`in Figure 13.9. The knockout switch is a blocking network and is constructed with
`interconnected crossbars with less complexity than a crossbar switch of the same size.
`The knockout switch is a good substitution for a crossbar switch when the likelihood
`is small that many inputs will need to send packets to the same output simultaneously.
`The idea of this switch is based on the concept of knocking a possible k packets out
`ofn active inputs ifthe number ofswitch outputs is m, where m < 11. To implement this
`mechanism, consider the example illustrated in Figure 13.9, where n = 8 and m z: 4.
`Assume that all the eight inputs have packets to transmit to outputs; obviously, the
`system would need to discard a minimum of four packets. The switching network
`consists of a number of either 2 x 2 switch elements and delay elements.
`The switch elements act as concentrators, ensuring fairness to all entering packets.
`The eight incoming packets from eight switch inputs compete in the first four switch
`elements. A packet that wins the competition, based on a random selection in a switch
`element, stays in the same column ofswitches and continues to reach its desired output.
`
`13.5 Concentration and Expansion Switches
`
`Inputs
`
`.J,.-i
`ii"I!", f
`
`ai
`
`

`

`364
`
`Chapter 13. Networks in Switch Fabrics
`
`13.5.2 Expansion Network
`
`An expansion network with n1 inputs and I12 outputs, where 711 < n2, can scale up
`the number of receivers from ml to 112. A three—stage expansion network is shown in
`Figure 13.10. This network is constructed with three types ofcrossbars of sizes (11 X in,
`)1]
`fl?
`— x 3:, and m X (12, respectively, and is defined by
`
`M(n1’ d1,7127 ([2, m) : XrlwnX111/d1,712/([2XI'21,612'
`
`An expansion network is a generalization of the three—stage Clos network and is
`useful in applications in which an incoming signal is to be sent to multiple outputs.
`Such networks are also called distribution networks. Considering the previous network
`dimensions, the complexity of a three~stage expansion network, Xe, is derived by
`
`the next round of competition. Thus, the first—round losers in this process go straight to
`the second column and play off against one another and at later stages, face the second—
`and the third—round losing packets from the first column.
`Note that the system needs to ensure that no input port is singled out for bad
`treatment every time the output is overloaded. This fairness task is implemented
`by playing packets against one another in a form of a knockout column-by—column
`scenario to select m winners. In the second column, two packets, including those losing
`packets, are competing in a similar fashion to reach their desired outputs, and so on.
`Finally, all the losing packets are dropped, and eventually, we select up to m = 4 packets,
`dropping all the rest. Note that this process requires timing synchronization if all the
`incoming packets are to experience the same switching delay. To ensure packet time
`synchronization, the delay elements present units of delay to packets, as shown in the
`figure by additional delay units.
`
`Since m is greater than the sum of these two values, at least one middle—stage switch
`
`Xe=d1n1£+mm+d2m£2a
`(Z1
`(1 1612
`([2
`
`(13.17)
`
`An expansion network is nonblocking if m 2 (d1 — 1)n2/([2 —l— (12. We can prove
`this claim by assuming that if‘a given connection goes to two or more outputs of the
`same third—stage switch, the connection branches in the third—stage switch supply all
`the outputs. Suppose that we want to add a new end point to an existing connection
`from an input )6 to an idle output y. If an output is in the same third~stage switch
`as y, we can add the necessary branch at that point. Note that (12 —— 1 middle—stage
`switches are inaccessible from y, and at most ((11 - 1)n2/d2 are inaccessible from x.
`
`

`

`
`
`<(—-——————————-——-———--—-—-—.§~——-——————————~———-—-—-——-—-—>
`
`13.6
`
`Shared—Memory Switch Fabrics
`
`Figure 13.10 A three-stage expansion switching network
`
`must be accessible to both x and y. A similar argument applies if we wish to create a
`new connection from an idle input x to an idle input y.
`
`Suppose that n1 2: n2 2 256,611 = 16, and d2 = 64. From the preceding
`Example.
`theorem, if m 2 1024 + 64 = 1,088, the network becomes nonblocking.
`
`13.6 Shared—Memory Switch Fabrics
`
`A totally different approach for switching can be achieved in time domain and without
`using any switch elements: the shared—memory switcbfizbrz'c. As shown in Figure 13.11,
`the distinctive feature of this switch fabric is the use of a high-speed n : 1, time-division
`multiplexer (TDM) with a bit rate n times as large as the rate on each individual
`input/output line. Assume packet 61 at input 1' needs to be switched on output j and
`that packet b at input j is supposed to be switched on output 1'. First, the multiplexer
`creates an n—channel—long frame from the n inputs. Each frame created at the output
`
`

`

`Chapter 13. Networks in Switch Fabrics
`
`Switch Fabric
`
`Shared Memory
`
`z'Hj
`
`Memory Control
`
`Figure 13.11
`
`Shared-memory switch fabric
`
`thus increases system throughput. With the use of buffers in a switch, packets are
`
`of the multiplexer is Stored in shared memory in the same order as the frames channels.
`Thus, a is written at location i, and b is written at location
`of memory.
`To implement the switching action between the two channels i and j, the memory
`control exchanges the reading order of the two memory locations i and
`This way,
`the new frame made out of memory contains packet a placed in channel j and packet
`I) placed in channel 1'. This frame is scanned by a demultiplexer for output ports. If the
`memory partition for an output is empty, the corresponding minislot remains unfilled.
`It is a matter of implementation whether frame size in shared memory should be rigid
`or flexible. Clearly, variable—size frames require more sophisticated hardware to manage,
`but the packet—loss rate improves, since memory does not suffer from overflow until all
`memory slots are occupied. See Chapter 3 for more on multiplexers handling variable—
`size frames.
`
`13.7 Techniques for Improving Performance
`
`Several practical methods can be used to improve the performance ofswitching systems.
`The enhancement ofa switch performance is typically related to speed, throughput, and
`therefore the possibility ofblocking. Some possible methods for enhancing performance
`in switching systems are as follows:
`
`' Buflferz'ng. The use of buffers in switching networks reduces traffic congestion and
`
`

`

`
`13.7 Techniques for Improving Performance
`367
`
`
`
`not discarded when they request the same switch output but instead are kept in
`buffers for a later contention resolution.
`
`° Contained networks. Combined networks consists of several cascaded switch fab—
`
`rics, providing extra stages and producing extra paths, although a combined net—
`work can also be designed for other purposes, such as multicasting.
`
`' Randomizz'ng trafife. This technique is used to distribute traffic evenly across the
`switching network to prevent local congestion.
`
`° Recirculation oftraflia A packet that is not successfully delivered to a given port
`can be recirculated. Such packets contend for delivery—possibly with higher
`priorities—4n the next cycle.
`
`° Increase 5peeal~up fizctor. This speea’ advantag