Lectures 17&18 Fast packet switching Eytan Modiano Massachusetts Institute of Technolog
Lectures 17 & 18 Fast packet switching Eytan Modiano Massachusetts Institute of Technology Eytan Modiano Slide 1
Packet switches engine Switch Scheduler Packet DataReader→[ Packet Tag DestinationAddress Output port number or vc number a packet switch consists of a routing engine(table look-up),a switch scheduler and a switch fabric The routing engine looks-up the packet address in a routing table and determines 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 port
Packet switches Packet Routing engine Switch Scheduler Packet Data Header Packet Tag DestinationAddress Output port number or VC number • A packet switch consists of a routing engine (table look-up), a switch scheduler, and a switch fabric. • The routing engine looks-up the packet address in a routing table and determines 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 port Eytan Modiano Slide 2
First Generation Switches CPU output buffer LC-1 LC-2 LC-3 Input buffer Computer with multiple line cards CPU polls the line cards CPU processes the packets Simple, but performance is limited by processor speeds and bus speeds Examples: Ethernet bridges and low end routers
First Generation Switches CPU LC-1 LC-2 LC-3 output buffer Input buffer • Computer with multiple line cards – CPU polls the line cards – CPU processes the packets • Simple, but performance is limited by processor speeds and bus speeds • Examples: Ethernet bridges and low end routers Eytan Modiano Slide 3
Second Generation switches Bus LC LC LC Most of the processing is now done in the line cards Route table look-up etc Line cards buffer the packets Line card send packets to proper output port Advantages: CPU and main Memory are no longer the bottleneck Disadvantage: Performance limited by bus speeds Bus Bw must be n times LC speed(N ports Example: cisco 7500 series router
Second Generation switches Computer LC LC LC LC Bus • Most of the processing is now done in the line cards – Route table look-up, etc. – Line cards buff er the packets – Line card send packets to proper output port • Advantages: CPU and main Memory are no longer the bottleneck • Disadvantage: Performance limited by bus speeds – Bus BW must be N times LC speed (N ports) • Example: CISCO 7500 series router Eytan Modiano Slide 4
Third generation switches Input LC Output LC Input LC SWITCH Output LC FABRIC Input LC Output LC Controll Replace shared bus with a switch fabric Performance depends on the switch fabric, but potentially can alleviate the bus bottleneck
Third generation switches N by N SWITCH FABRIC Input LC Input LC Input LC Output LC Output LC Output LC Controller • Replace shared bus with a switch fabric • Performance depends on the switch fabric, but potentially can alleviate the bus bottleneck Eytan Modiano Slide 5
Switch Architectures Distributed buffer Output buffer Input buffer
Switch Architectures • Distributed buffer • Output buffer • Input buffer Eytan Modiano Slide 6
Distributed buffer Modular architecture Basic module is a 2x 2 switch which can be either in the through or crossed position Switch buffers: None, at input, or at output of each module Switch fabric consists of many 2x2 modules □口□ N
Distributed buffer • Modular Architecture Basic module is a 2x2 switch, which can be either in the through or crossed position • Switch buffers: None, at input, or at output of each module Switch fabric consists of many 2x2 modules N N inputs outputs Eytan Modiano Slide 7
Interconnection networks N input Log(N) stages with N/2 modules per stage Example: Omega(shuffle exchange network) 0000 2010 3011 4567 11 0 17 Notice the order of inputs into a stage is a shuffle of the outputs from 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 SD pair Self-routing network
Interconnection networks • N input • Log(N) stages with N/2 modules per stage Example: Omega (shuffle exchange network) 0 1 2 3 4 5 6 7 0 000 1 001 2 010 3 011 4 100 5 101 6 110 7 117 • Notice the order of inputs into a stage is a shuffle of the outputs from 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 SD pair Eytan Modiano – Self-routing network Slide 8
Self Routing Use a tag: n bit sequence with one bit per stage of the network E.g., Tag= b3b2b, Module at stage i looks at bit i of the tag (b), and sends the packet up if b =0 and down if b =1 In omega network, for destination port with binary address abc the tag is cba EXample: output 100=> tag=001 Notice that regardless of input port, tag 001 will get you to output 100
Self Routing • Use a tag: n bit sequence with one bit per stage of the network – E.g., Tag = b3b2b1 • Module at stage i looks at bit i of the tag (bi), and sends the packet up if bi=0 and down if bi=1 • In omega network, for destination port with binary address abc the tag is cba – Example: output 100 => tag = 001 – Notice that regardless of input port, tag 001 will get you to output 100 Eytan Modiano Slide 9
Baseline network 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 a new stage of N/2 basic(2X 2 )modules N by N switch has Log2(N)stages each with N/2 basic (2x2) modules 2x2 N/2 X N/2 2x2 2x2 2x2 N inputs 4 x 4 switch example 2x2 2x2 2x2 N/2X NA 2x2 N/2 basic mods 2 N/2 by n/2 switches
Baseline network • 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 a new stage of N/2 basic (2x2) modules – N by N switch has Log2(N) stages each with N/2 basic (2x2) modules N inputs 4 x 4 switch example 2x2 2x2 2x2 2x2 N/2 x N/2 N/2 x N/2 2x2 2x2 2x2 2x2 N/2 basic mods 2 N/2 by N/2 switches Eytan Modiano Slide 10