Switching Hardware - UIUC

Switching Hardware Spring 2015 CS 438 Staff, University of Illinois 1

Where are we? n Understand ¡ Different ways to move through a network (forwarding) n n n ¡ n Read signs at each switch (datagram) Follow a known path (virtual circuit) Carry instructions (source routing) Bridge approach to extending LAN concept Next: how switches are built and contention within switches Spring 2015 CS 438 Staff, University of Illinois 2

Switch Design Chicago Bloomington Champaign Indianapolis Springfield St. Louis Spring 2015 Effingham CS 438 Staff, University of Illinois How should we design Champaign to accommodate traffic flows? 3

Switch architecture Juniper EX2200 Juniper EX8200 Spring 2015 CS 438 Staff, University of Illinois Cisco Catalyst 6500 4

Switch Design Input Port Output Port Input Port Output Port Input Port Output Port Input Port Switch Fabric Output Port Input Port Output Port Input Port Output Port Spring 2015 CS 438 Staff, University of Illinois 5

Switch Architecture n Problem ¡ Connect N inputs to M outputs n n n NxM (“N by M”) switch Common case: N M Input Port Output Port Input Port Output Port Input Port Input Port Switch Fabric Output Port Output Port Input Port Output Port Input Port Output Port Goals ¡ ¡ ¡ Avoid contention High throughput Good scalability n Spring 2015 Near-linear size/cost growth CS 438 Staff, University of Illinois 6

Switch high level architecture n Ports handle complexity ¡ ¡ n Forwarding decisions at input ports Buffering at output and possibly input ports Input Port Output Port Input Port Output Port Input Port Input Port Switch Fabric Output Port Output Port Input Port Output Port Input Port Output Port Simple fabric (it seems ) ¡ ¡ Spring 2015 Move packets from inputs to outputs May have a small amount of internal buffering CS 438 Staff, University of Illinois 7

Switch Design Goals n Minimize Contention ¡ ¡ ¡ ¡ Avoid contention through intelligent buffering Use output buffering when possible Apply back pressure through switch fabric Improve input buffering through non-FIFO buffers n ¡ Spring 2015 Reduces head-of-line blocking Drop packets if input buffers overflow CS 438 Staff, University of Illinois 8

Switch Design Goals n Maximize Throughput ¡ ¡ Main problem is contention Need a good traffic model n n n ¡ Telephony modeling is well understood n ¡ Until faxes and modems Data traffic has different properties n Spring 2015 Arrival time Destination port Packet length E.g., phone call arrivals are “Poisson”, but packet arrivals are “heavy-tailed” CS 438 Staff, University of Illinois 9

Contention n Problem ¡ n Solutions ¡ ¡ n Some packets may be destined for the same output port One packet gets sent first Other packets get delayed or dropped Delaying packets requires buffering ¡ ¡ Buffers are finite, so we may still have to drop Buffering at input ports n n ¡ ¡ Spring 2015 Increases, adds false contention Sometimes necessary Buffering at output ports Buffering inside switch CS 438 Staff, University of Illinois 10

Buffering standard checkout lines customer service Waiting to buy food We need “buffering”, places where people can wait before they get service Spring 2015 CS 438 Staff, University of Illinois Waiting for Cust. service 11

Output Port Buffering standard checkout lines Waiting to buy food customer service Waiting for How big should buffers be?service Cust. à Should make sure we can hold enough à But don’t want people to wait forever Spring 2015 CS 438 Staff, University of Illinois 12

Switch Design Input Port 1 Output Queues Output Port 1 Input Port 2 Output Port 2 Input Port 3 Output Port 3 Input Port 4 Output Port 4 Input Port 5 Output Port 5 Input Port 6 Spring 2015 Add output queues to hold packets Packet remains queued here until Output Port 6 output port available to send CS 438 Staff, University of Illinois 13

Input Port Buffering standard checkout lines Waiting to buy food People waiting to get into the store Spring 2015 customer service We also need buffering at the input, sinceWaiting processing for can be slower than input rate, Cust. service or delays at output CS 438 Staff, University of Illinois 14

Switch Design Input Port 1 Input Queues Output Queues Output Port 1 Input Port 2 Output Port 2 Input Port 3 Output Port 3 Input Port 4 Output Port 4 Add input queues to temporarily hold received packets until they can be processed Input Port 5 queued until input queue Packet remains empties, until output queue has free slots InputSpring Port 6 2015 CS 438 Staff, University of Illinois Output Port 5 Output Port156

Switch design: putting the pieces together Input Port 1 Input Queues Interconnection Network Output Queues Output Port 1 Input Port 2 Output Port 2 Input Port 3 Output Port 3 Input Port 4 Output Port 4 Input Port 5 Output Port 5 InputSpring Port 6 2015 CS 438 Staff, University of Illinois Output Port166

Switch design: putting the pieces together Looks in forwarding table, finds output port 3 is associated Interconnection with destination Input Output Input Port 1 Queues Network Queues Output Port 1 Input Port 2 Output Port 2 Input Port 3 Output Port 3 Input Port 4 Output Port 4 Packet remains queued until input queue empties and Input Port 5 output queue 3 has free slots InputSpring Port 6 2015 Output Port 5 Packet remains queued until output port available to send CS 438 Staff, University of Illinois Output Port176

Contention – Head of Line Blocking standard checkout lines customer service cashiers are standing by! waiting for free slots in cust. svc line “Head of line blocking” slows throughput People waiting to get into the store Spring 2015 CS 438 Staff, University of Illinois 18

Head of Line Blocking Two packets with same output Interconnection port à contention Input Port 1 Input Queues network: “switch fabric” Output Queues Output Port 1 Input Port 2 Output Port 2 Input Port 3 Output Port 3 Input Port 4 Output Port 4 Input Port 5 Output Port 5 We can’t send this packet, even for resources! InputSpring Port 6 though it’s not contending 2015 CS 438 Staff, University of Illinois Output Port196

Unblocking head of line blocking n Solution 1: No input queue ¡ n Solution 2: No need to always serve packet at head of queue. Could pick any! ¡ n Switching fabric (hopefully) keeps up with input rate Each input port has separate queue for each output port Next question: which packet do we pick? Spring 2015 CS 438 Staff, University of Illinois 20

Picking packets’ ports Input port 1 2 Input port 2 3 1 Output port 1 1 4 Output port 2 Switching fabric Input port 3 Input port 4 Spring 2015 2 4 4 Output port 3 4 1 Output port 4 CS 438 Staff, University of Illinois 21

Picking packets’ ports Input port 1 2 Input port 2 3 1 Output port 1 1 4 Output port 2 Switching fabric Input port 3 Input port 4 n 2 4 4 Output port 3 4 1 Output port 4 Underlying problem for max throughput in single timestep: bipartite matching ¡ Spring 2015 Pick max subset of edges using 1 edge per node CS 438 Staff, University of Illinois 22

Picking packets’ ports Input port 1 2 Input port 2 3 1 Output port 1 1 4 Output port 2 Switching fabric Input port 3 Input port 4 n 2 4 4 Output port 3 4 1 Output port 4 Switches may not find optimal solution: we also want ¡ ¡ Spring 2015 Fairness Simplicity of implementation CS 438 Staff, University of Illinois 23

What we know so far n n Buffering masks temporary contention Need to carefully manage queues ¡ ¡ ¡ Spring 2015 Head-of-line blocking problem Fairness Throughput CS 438 Staff, University of Illinois 24

What we know so far n Did we completely solve contention problem? Could a packet ever be dropped? ¡ ¡ ¡ Spring 2015 Yes: queues can still overflow Solution 1: plan allowed packet rates in advance – virtual circuit switching Solution 2: dynamically request rate reduction – backpressure CS 438 Staff, University of Illinois 25

Contention – Back Pressure n Let the receiver tell the sender to slow down ¡ ¡ Propagation delay requires that the receiver react before the buffer is full Typically used in networks with small propagation delay switch 1 switch 2 “no more, please” Spring 2015 CS 438 Staff, University of Illinois 26

Contention – Back Pressure n n Need to send backpressure before queue fills So, better when propagation delay small e.g., switch fabrics e.g., Ethernet pause-based flow control (IEEE 802.3x) used to run FibreChannel over Ethernet ¡ ¡ Switch stop stop stop 2 3 1 4 5 9 6 7 8 1 2 3 4 8 5 6 7 9 1 2 3 7 4 5 6 8 9 Discard: Spring 2015 CS 438 Staff, University of Illinois Switch 6 5 4 3 2 1 7 8 9 27

Switch Design Goals n High Throughput ¡ n High Scalability ¡ n Number of packets a switch can forward per second How many input/output ports can it connect Low Cost ¡ Spring 2015 Per port monetary costs CS 438 Staff, University of Illinois 28

Two simple fabrics Two simple fabrics for very large highperformance switches! Shared bus or memory: Low , low throughput Spring 2015 Full mesh: High , high throughput CS 438 Staff, University of Illinois 29

Special Purpose Switches n Problem ¡ Connect N inputs to M outputs n n n NxM (“N by M”) switch Often N M Goals ¡ High throughput n ¡ ¡ Output Port Input Port Output Port Input Port Input Port Switch Fabric Output Port Output Port Input Port Output Port Input Port Output Port Best is MIN(sum of inputs, sum of outputs) Avoid contention Good scalability n Spring 2015 Input Port Linear size/cost growth CS 438 Staff, University of Illinois 30

Switch Design n Ports handle complexity ¡ ¡ n Forwarding decisions Buffering Simple fabric ¡ ¡ Spring 2015 Input Port Output Port Input Port Output Port Input Port Input Port Switch Fabric Output Port Output Port Input Port Output Port Input Port Output Port Move packets from inputs to outputs May have a small amount of internal buffering CS 438 Staff, University of Illinois 31

Switch Design Goals n Throughput ¡ ¡ Main problem is contention Need a good traffic model n n n ¡ Telephony modeling is well understood n ¡ Until faxes and modems Modeling of data traffic is new n n Spring 2015 Arrival time Destination port Packet length Not well understood Will good models help? CS 438 Staff, University of Illinois 32

Switch Design Goals n Contention ¡ ¡ ¡ ¡ Avoid contention through intelligent buffering Use output buffering when possible Apply back pressure through switch fabric Improve input buffering through non-FIFO buffers n ¡ Spring 2015 Reduces head-of-line blocking Drop packets if input buffers overflow CS 438 Staff, University of Illinois 33

Switch Design Goals n Scalability ¡ ¡ ¡ Spring 2015 O(N) ports Port design complexity O(N) gives O(N2) for entire switch Port design complexity of O(1) gives O(N) for entire switch CS 438 Staff, University of Illinois 34

Switch Design n n n n Crossbar Switches Banyan Networks Batcher Networks Sunshine Switch Spring 2015 CS 438 Staff, University of Illinois 35

Crossbar Switch n Every input port is connected to every output port ¡ n NxN Output ports ¡ Spring 2015 Complexity scales as O(N2) CS 438 Staff, University of Illinois 36

Crossbar Switch Input Port Input Port Input Port Input Port Output Port Output Port Output Port Output Port Spring 2015 CS 438 Staff, University of Illinois 37

Knockout Switch n Problem ¡ n Assumption ¡ n It is unlikely that N inputs will have packets destined for the same output port Instead ¡ n Full crossbar requires each output port to handle up to N input packets implement each port to handle L N packets at the same time Challenges ¡ ¡ Spring 2015 What value of L to use Managing hotspots CS 438 Staff, University of Illinois 38

Knockout Switch n Output port design ¡ Packet filters n ¡ Concentrator n n ¡ Selects up to L packets from those destined for this port “Knocks out” (discards) excess packets Queue n Spring 2015 Recognize packets destined for a specific port Length L CS 438 Staff, University of Illinois 39