1MITOutline• Basics of switching• Blocking• Interconnection examples• Complexity• Recursive constructionsMITSwitching and Routing• Switching is generally the establishment of connections on a circuitbasis• Routing is generally the forwarding of traffic on a datagram basis• Routing requires switching but not vice-versa – routing usesconnections which are permanently or temporarily set up to in orderto forward datagrams (those datagrams may be in circuit form, forinstance VPs and VCs)2MITPacket routers• A packet switch consists of a routing engine (table look-up), a switchscheduler, and a switch fabric.• The routing engine looks-up the packet address in a routing table anddetermines which output port to send the packet.– Packet is tagged with port number– The switch uses the tag to send the packet to the proper output portMITSwitch fabrics• Simplest switch fabric is simply a shared bus– Most of the processing is done in line cards• Route table look-up• Line cards buffer the packets• Line card send packets to proper output– Bus bandwidth must be N times LC speed (N ports)• In general a switch fabric replaces the bus• Switch fabrics are created from certain building blocks ofsmaller switches arranged in stages• Simplest switch is a 2x2 switch, which can be either in thethrough or crossed positionComputerBusLC LC LC LC3MITDefinitions• A connection state is a mapping from the array of inputs to thatof outputs; connections are either point-to-point or multicast• Basic switch building blocks are:– the distributor– the concentrator– the 2x2 2-state point-to-point switch (switching cell)0100100100100100 01 10 01 1MITBuilding up• Interconnection network: finite collection of nodes togetherwith a set of interconnection lines such that– every node is an object with an array of inputs and anarray of outputs– an interconnection line leads from an output of one nodeto an input of another node– every I/O of a node is incident with at most oneinterconnection line– an I/O is called external if it is not incident with anyinterconnection line• A route from an external input to an external output is a chainof distinct (a0, b0, a1, b1, …, ak, bk) where a0 and bk areexternal, bj-1 is interconnected to aj4MITBuilding up• An interconnection network is called a switching networkwhen:– every node qualifies to be a switch through properspecification of connection states– the network is routable (there exists a route from everyexternal input to every external output)– an ordering is specified on external inputs and on externaloutputs• Unique routing interconnection networks: all routes from anexternal input to an external output are parallel, that is (a0, b0,a1, b1, …, ak, bk) and (a0, b’0, a’1, b’1, …, a’k, bk) are such that aj,a’j reside on the same nodes and bj, b’j reside on the same node• Otherwise: alternate routingMITBlocking• A mxn unique routing network is called a nonblocking networkif for any integer k < min(m,n)+1, any k external inputs, any kexternal outputs and pairing between these external I/O, thereexist k disjoint routes for the matched pairs• For a routable network, the same property is that ot arearrangeably nonblocking, or rearrangeable network• An interconnection network is strictly non-blocking if requestsfor routes are always granted under the rule of arbitrary routeselection, wide-sense non-blocking if there exists an algorithmfor route selection that grants all requestsrearrangeableWSnon-blockingnon-blocking5MITBlocking, Multi-stage networks• Main connection between rearrangeability and non-blockingproperty is given by the following theorem:A switching network composed of non-blocking switches is rearrangeable iff itconstructs a non-blocking switch• A common means of building interconnection networks is touse a multi-stage architecture:– every interconnection line is between two stages– every external input is on a first-stage node– every external output is on a final-stage node– nodes within each stage are linearly orderedMITInterconnection networks• N input, Log(N) stages with N/2 modules per stageExample: Omega (shuffle exchange network)• Notice the order of inputs into a stage is a shuffle of the outputsfrom the previous stage: (0,4,1,5,2,6,3,7)• Easily extended to more stages• Any output can be reached from any input by proper switch settings– Not all routes can be done simultaneously– Exactly one route between each OD pair6MITInterconnection networks• Another example of a multi-stage interconnection network• Built using the basic 2x2 switch module• Recursive construction– Construct an N by N switch using two N/2 by N/2 switches and anew stage of N/2 basic (2x2) modules– N by N switch has Log2(N) stages each with N/2 basic (2x2)modulesMITComplexity issues• There are many different parameters that are used to considerthe complexity of an interconnection network• Line complexity: number of interconnection lines• Node (cell) complexity: number of small nodes (mxn wherem < 3 and n < 3)• Depth: maximum number of nodes on a route (assuming anacyclic interconnection network)• Entropy of a switch: log of the number of connections states• What relations exist between complexity and the capabilitiesof a switch?7MITComplexity• The depth of a mxn routable interconnection network is atleast max(log(m), log(n)).• Proof: for a depth d, there are at most 2d external outputs.Since we have routability, n< 2d+1 and m< 2d+1 .• When a switching network is composed of 2-state switches,the component complexity of the network is at least theentropy of the switch• Proof: for E the number of switches, there are 2E ways toform a combination of one connection state in every node.Each combination corresponds to at most one connectionstate in the node.MITComplexity• When a nxn rearrangeable network is composed of smallnodes, its component complexity is at least log(N!)• Proof: if we take every small node to be replaced by a 2-statepoint-to-point switch, then we have a non-blocking switch.Thus, there is a different connection state for everyone of then! one-to-one mapping between the n inputs and the noutputs. We now use the relation for networks composed of2-state switches.• Note: using Stirling’s formula, we can obtain an approximatesimple bound for
View Full Document