CS 636 Internetworking Ramana Kompella ROUTER ALGORITHMICS Lecture 10: Switching Some slides courtesy of Nick McKeown 1Lookup IP Address Update Header Header Processing Address Table Lookup IP Address Update Header Header Processing Address Table Lookup IP Address Update Header Header Processing Address Table Queue Packet Buffer Memory Queue Packet Buffer Memory Queue Packet Buffer Memory Data Hdr Data Hdr Data Hdr 1 2 N 1 2 N N times line rate N times line rate 2 CS 636 Internetworking Generation 1: Bus, shared CPU  Only one pair of lines can communicate  CPU allows simple and changeable forwarding software CPU Bus Line card N Line card 1 3 CS 636 Internetworking Problem: One CPU is a bottleneck  Add multiple CPUs that can figure out the destination  Without care, can lead to packet reordering Bus Line card N Line card 1 CPU CPU CPU 4 CS 636 Internetworking Why bother crossing the bus several times?  Add CPU on the line card itself  Bus is still a big bottleneck allowing only one packet between two line cards Bus Line card N Line card 1 CPU CPU CPU 5 CS 636 Internetworking Crossbar essentially has 2N parallel buses, one per source/dest line card  Best case: all buses used simultaneously giving N-fold speedup Input N Input 1 Output N Output 1 RoutingCPU 6 CS 636 InternetworkingInput Queueing Output Queueing Usually a non-blocking switch fabric (e.g. crossbar) Usually a fast bus 7 CS 636 InternetworkingIndividual Output Queues Centralized Shared Memory Memory b/w = (N+1).R Since N writes + 1 Read 1 2 N Memory b/w = 2N.R 1 2 N 8 CS 636 InternetworkingSWITCH FABRIC 1 1 1 1 1 1 2 2 2 2 2 2 9 CS 636 InternetworkingShared Memory 200 byte bus 5ns SRAM 1 2 N • 5ns per memory operation • Two memory operations per packet • Therefore, up to 160Gb/s • In practice, closer to 80Gb/s 10 CS 636 Internetworkingconfiguration Data In Data Out Scheduler Memory b/w = 2R 11 CS 636 InternetworkingDelay Load 58.6% 100% [Karol88] Throughput ~ 2 - √2 12 CS 636 Internetworking Assume saturation (i.e., all inputs have cells to send at any given instant)  Assume each packet destined to each output with probability 1/N  Equal size packets, probability that an output O is idle is probability that none of the inputs choose O  Each input does not choose O with probability 1 – 1/N. P (O idle) = (1-1/N)N ◦ Converges to (1-1/e) ~ 0.63  Careful analysis that avoids the independence assumption across rounds by Karol shows throughput converges to 2-√2 ~ 0.58 13 CS 636 Internetworking If more than one input has a packet destined to the same output, head of line blocking occurs.  Wastes bandwidth significantly 14 CS 636 Internetworking15 CS 636 Internetworking16 CS 636 Internetworking17 CS 636 InternetworkingDelay Load 100% 18 CS 636 InternetworkingScheduler Memory b/w = 2R Can be quite complex! 19 CS 636 Internetworking20 CS 636 InternetworkingRequest Graph 1 2 3 4 1 2 3 4 2 5 2 4 2 Bipartite Matching 1 2 3 4 1 2 3 4 (Weight = 18) Question: Maximum weight or maximum size? 7 21 CS 636 Internetworking Maximum Size ◦ Maximizes instantaneous throughput ◦ Does it maximize long-term throughput?  Maximum Weight ◦ Can clear most backlogged queues ◦ But does it sacrifice long-term throughput? 22 CS 636 Internetworking1 2 1 2 1 2 1 2 23 CS 636 InternetworkingWeight Waiting Time 100% Queue Length { } = 1 2 3 4 1 2 3 4 10 1 1 10 1 1 1 2 3 4 1 2 3 4 24 CS 636 Internetworking• When traffic is uniformly distributed, servicing the maximum number of queues leads to 100% throughput. • When traffic is non-uniform, some queues become longer than others. • A good algorithm keeps the queue lengths matched, and services a large number of queues. VOQ # Avg Occupancy Uniform traffic VOQ # Avg Occupancy Non-uniform traffic 25 CS 636