EECS 122: Introduction to Computer Networks Switch and Router ArchitecturesToday’s LectureIP RoutersGeneric ArchitectureShared Memory (1st Generation)Shared Bus (2nd Generation)Point-to-Point Switch (3rd Generation)What a Router Looks LikeInterconnectOutput Queued RoutersInput Queued RoutersHead-of-line BlockingA Router with Input Queues Head of Line BlockingSolution to Avoid Head-of-line BlockingCombined Input-Output Queued (CIOQ) RoutersInput InterfaceLookupIP RoutingPatricia TriesAnother Forwarding Technique: Source RoutingSource Routing (cont’d)Output FunctionsExample: FIFO routerOutput Functions (cont’d)Packet ClassificationExample of Classification RulesSchedulerExample: Priority SchedulerExample: Round Robin SchedulerDiscussionBig PicturePacket (Datagram) Switching PropertiesVirtual Circuit (VC) SwitchingVC Forwarding: ExampleVC Forwarding (cont’d)VC Switching PropertiesCircuit SwitchingCircuit Switching PropertiesForwarding ComparisonSummaryKatz, Stoica F04EECS 122: Introduction to Computer Networks Switch and Router ArchitecturesComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04Today’s LectureNetwork (IP)ApplicationTransportLinkPhysicalToday!3Katz, Stoica F04IP Routers6785431212101311RouterRouter consists of-Set of input interfaces where packets arrive-Set of output interfaces from which packets depart-Some form of interconnect connecting inputs to outputsRouter implements-(1) Forward packet to corresponding output interface-(2) Manage bandwidth and buffer space resources4Katz, Stoica F04Generic ArchitectureInput and output interfaces are connected through an interconnectInterconnect can be implemented by-Shared memory •Low capacity routers (e.g., PC-based routers)-Shared bus•Medium capacity routers-Point-to-point (switched) bus • High capacity routersinput interface output interfaceInter-connect5Katz, Stoica F04Shared Memory (1st Generation)RouteTableCPUBufferMemoryLineInterfaceMACLineInterfaceMACLineInterfaceMACTypically < 0.5Gbps aggregate capacityLimited by rate of shared memoryShared BackplaneLine InterfaceCPUMemory(* Slide by Nick McKeown)6Katz, Stoica F04Shared Bus (2nd Generation)RouteTableCPULineCardBufferMemoryLineCardMACBufferMemoryLineCardMACBufferMemoryFwdingCacheFwdingCacheFwdingCacheMACBufferMemoryTypically < 5Gb/s aggregate capacity; Limited by shared bus(* Slide by Nick McKeown)7Katz, Stoica F04Point-to-Point Switch (3rd Generation)LineCardMACLocalBufferMemoryCPUCardLineCardMACLocalBufferMemorySwitched BackplaneLine InterfaceCPUMemoryFwdingTableRoutingTableFwdingTableTypically < 50Gbps aggregate capacity(*Slide by Nick McKeown)8Katz, Stoica F04What a Router Looks LikeCisco GSR 12416 Juniper M1606ft19”2ftCapacity: 160Gb/sPower: 4.2kW3ft2.5ft19”Capacity: 80Gb/sPower: 2.6kWSlide by Nick McKeown9Katz, Stoica F04Interconnect Point-to-point switch allows simultaneous transfer of packet between any two disjoint pairs of input-output interfacesGoal: come-up with a schedule that-Provides Quality of Service-Maximizes router throughputChallenges:-Address head-of-line blocking at inputs-Resolve input/output speedups contention-Avoid packet dropping at output if possibleNote: packets are fragmented in fix sized cells at inputs and reassembled at outputs10Katz, Stoica F04Output Queued RoutersOnly output interfaces store packetsAdvantages-Easy to design algorithms: only one congestion pointDisadvantages-Requires an output speedup of N, where N is the number of interfaces not feasibleinput interface output interfaceBackplaneCRO11Katz, Stoica F04Input Queued RoutersOnly input interfaces store packetsAdvantages-Easy to build •Store packets at inputs if contention at outputs -Relatively easy to design algorithms•Only one congestion point, but not output…•Need to implement backpressureDisadvantages-Hard to achieve utilization 1 (due to output contention, head-of-line blocking) •However, theoretical and simulation results show that for realistic traffic an input/output speedup of 2 is enough to achieve utilizations close to 1input interface output interfaceBackplaneCRO12Katz, Stoica F04Head-of-line BlockingCell at head of an input queue cannot be transferred, thus blocking the following cells Cannot betransferred because output buffer overflowCannot be transferred because is blocked by red cell Output 1Output 2Output 3Input 1Input 2Input 313Katz, Stoica F040% 20% 40% 60% 80% 100%LoadDelayA Router with Input QueuesHead of Line BlockingThe best that any queueing system can achieve.2 2 58%- �Slide by Nick McKeown14Katz, Stoica F04Solution to Avoid Head-of-line BlockingMaintain at each input N virtual queues, i.e., one per output portOutput 1Output 2Output 3Input 1Input 2Input 315Katz, Stoica F04Combined Input-Output Queued (CIOQ) RoutersBoth input and output interfaces store packetsAdvantages-Easy to built •Utilization 1 can be achieved with limited input/output speedup (<= 2)Disadvantages-Harder to design algorithms•Two congestion points•Need to design flow controlinput interface output interfaceBackplaneCRO16Katz, Stoica F04Input InterfacePacket forwarding: decide to which output interface to forward each packet based on the information in packet header-Examine packet header-Lookup in forwarding table-Update packet headerinput interface output interfaceInter-connect17Katz, Stoica F04LookupIdentify the output interface to forward an incoming packet based on packet’s destination addressRouting tables summarize information by maintaining a mapping between IP address prefixes and output interfaces-How are routing tables computed?Route lookup find the longest prefix in the table that matches the packet destination address18Katz, Stoica F04IP RoutingPacket with destination address 12.82.100.101 is sent to interface 2, as 12.82.100.xxx is the longest prefix matching packet’s destination address…… 312.82.xxx.xxx 1128.16.120.xxx12128.16.120.11112.82.100.10112.82.100.xxx 219Katz, Stoica F04Patricia TriesUse binary tree paths to encode prefixesAdvantage: simple to implementDisadvantage: one lookup may take O(m), where m is number of bits (32 in the case of IPv4)001xx 2 0100x 310xxx 101100 501010110000235120Katz, Stoica F04Another Forwarding Technique: Source RoutingEach packet specifies the sequence of routers, or alternatively
View Full Document
Unlocking...