SwitchesOutlineSwitch CharacteristicsExamplesExamples (cont’d)Slide 6Slide 7FunctionsFunctions (cont’d)Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Output BufferInput BufferVirtual Output BufferVirtual Output Buffer (cont’d)Slide 26Slide 27Shared BufferModular SwitchesModular Switches (cont’d)UCBSwitchesJean WalrandU.C. Berkeleywww.eecs.berkeley.edu/~wlrUCBOutlineSwitch CharacteristicsExamplesFunctionsOutput BufferInput BufferVirtual Output BufferShared MemoryModularUCBSwitch CharacteristicsPortsFast Ethernet, OC-3, ATM, …ProtocolsST, Link Agg., VLAN, OSPF, RIP, BGP, …PerformanceThroughput, 8-classes CoS, …UCBExamplesCisco 12416:The Cisco 12416 Internet router is a 10 Gigabit, 16-slot chassis member of the Cisco 12000 series that provides a total switching capacity of 320 Gigabits per second (Gbps), with 20 Gbps (10 Gbps full duplex) capacity per slot. With its 16-slot chassis and extensive portfolio of line cards including the new Cisco 1-port OC-192c/STM-64c and Cisco 4-port OC-48c/STM-16c POS interfaces, the Cisco 12416 Internet router supports high-density ISP aggregation and point-of-presence (POP) consolidation.UCBExamples (cont’d)Cisco 3600Voice over Frame relay (VoFR) and Voice over ATM (VoATM-AALS) on the digital voice interfaces (T1 and E1). Gateways for the PBX and PSTN for IP telephony, enabling applications like call transfers, holds, and conferencing.UCBExamples (cont’d)Extreme Networks - Summit• 48 10/100 ports• 2 GE (SX, LX, or LX-70)• 17.5Gbps non-blocking• 10.1 Mpps• Wire speed L2• Wire speed L3 static or RIP• OSPF, DVRMP, PIM, …UCBExamples (cont’d)Foundry ServerIron•Server Load Balancing •Transparent Cache Switching •Firewall Load Balancing •Global Server Load Balancing •Extended Layer 4-7 functionality including URL-, Cookie-, and SSL Session ID-based switching •Secure Network Address Translation (NAT) and Port address translation (PAT)UCBFunctionsData Path and Control Path:Note: Figure from Prof. Varaiya’s notes for EE228bUCBFunctions (cont’d)Data Path:Extract headerLookup forwarding ruleQueuing decision (drop, mark, queue)Modify headerStore packetSchedule transmissionSend packetUCBFunctions (cont’d)Control PathRouting table (IP, MPLS, ST, …)Forwarding policies (RED, Policing, …)Scheduling rules (WFQ, Priority, …)UCBFunctions (cont’d)Timing:Note: Figure from Prof. Varaiya’s notes for EE228bUCBFunctions (cont’d)Table Lookup Example (routing)Note: Figure from Prof. Varaiya’s notes for EE228bUCBFunctions (cont’d)CIDR Lookup001010011**00011***001*****11******3214234Ternary CAMAssociated Data = Port* = don’t careReturns first matchUCBFunctions (cont’d)Policing: Leaky BucketLeak Rate RCapacity BP bytesAdd P unitsIf overflow, drop packetor mark packetUCBFunctions (cont’d)RED: Random Early DiscardObjectives: Reduce synchronization of sources Avoid penalizing bursts Drop more from more active sourcesEffectiveness: so soOperations:qAVqProb.(drop)0.1LHLHUCBFunctions (cont’d)RED In and Out (RIO)qAVProb.(drop OUT)Prob.(drop IN)IN = unmarkedOUT = markedUCBFunctions (cont’d)Priority Scheduling:Priority123When finished transmitting a packet, serve next from first nonempty queue in order (1, 2, 3)UCBFunctions (cont’d)Deficit Round Robin (DRR)Weight523(5/10)R(5/10)R(5/10)RGet to new queue: Empty: Skip; Else: Add weight to creditsCredits > 0 => serve one packet, subtract 1 credit per byteCredits < 0 => Go to next queueRepeatUCBFunctions (cont’d)DRR (cont’d)101437205ABCredits A: 0 7 -3 4 -16 - 9 -2 5 2 -16 …Credits B: 0 3 -11 - 8 -5 -2 1 -4 …31830Send 10 14 20 3 18 5UCBFunctions (cont’d)Weighted Fair Queuing (WFQ)Weight523(5/10)R(5/10)R(5/10)RCompute departure times from processor sharing queue with these weights. Serve next the queue with earliest deadline.UCBFunctions (cont’d)WFQ (cont’d)523101414- 3/8Leaves at tt10- 5/8=> Serve AABCUCBOutput BufferBuffers at output portsLimitation: Throughput < rate of shared busNote: Figure from Prof. Varaiya’s notes for EE228bUCBInput BufferBuffers at input portsLimitation: Head-of-Line blockingNote: Figure from Prof. Varaiya’s notes for EE228bUCBVirtual Output BufferOUT buffers at each input portComplexity: Matching ProblemNote: Figure from Prof. Varaiya’s notes for EE228bUCBVirtual Output Buffer (cont’d)Full-Throughput Scheduling:Maximum Weighted MatchingA = 14B = 11C = 15D = 10B + C > A + D=> Serve (B, C)UCBVirtual Output Buffer (cont’d)i-SLIP1. Request: Nonempty VOBs request to outputs2. Grant: Outputs grant (in RR order) VOBs3. Accept: Granted VOBs accepts (in RR order)4. Iterate: Repeat after removing acceptsUCBVirtual Output Buffer (cont’d)i-SLIP (cont’d) Request Grant213312Last GrantLast AcceptAccept IterUCBShared BufferOne memory pool shared by flowsLimitation: Memory SpeedNote: Figure from Prof. Varaiya’s notes for EE228bUCBModular SwitchesSpace-Division SwitchingBlockingUCBModular Switches
View Full Document