1Routers: ForwardingEECS 122: Lecture 13Department of Electrical Engineering and Computer SciencesUniversity of CaliforniaBerkeleyFebruary 23, 2006EECS122 Lecture 12 (AKP)2Router Architecture OverviewTwo key router functions: run routing algorithms/protocol (RIP, OSPF, BGP) forwarding datagrams from incoming to outgoing linkInterconnectionfabric2February 23, 2006EECS122 Lecture 12 (AKP)3Today: Focus on Forwarding Datagrams Input Ports Output Ports Interconnection Fabric Forwarding Process Datagrams: Lookups (Virtual Circuit next lecture) Examples of RoutersFebruary 23, 2006EECS122 Lecture 12 (AKP)4Input Port FunctionsDecentralized switching: given datagram dest., lookup output port using forwarding table in input port memory goal: complete input port processing at ‘line speed’ queuing: if datagrams arrive faster than forwarding rate into switch fabricPhysical layer:bit-level receptionData link layer:e.g., Ethernet3February 23, 2006EECS122 Lecture 12 (AKP)5Output PortsFebruary 23, 2006EECS122 Lecture 12 (AKP)6Queuing Functions Buffer management: decide when and which packet to drop Scheduler: decide when and which packet to transmit112212SchedulerBuffer4February 23, 2006EECS122 Lecture 12 (AKP)7Output Queued Router Only output interfaces store packets Advantage Easy to design algorithms: only one congestion pointinput interface output interfaceFabricFebruary 23, 2006EECS122 Lecture 12 (AKP)8Output Queued Routers5February 23, 2006EECS122 Lecture 12 (AKP)9Output Queued Router Only output interfaces store packets Advantage Easy to design algorithms: only one congestion point Disadvantage Requires a speedup of a factor of N, where N is the number of interfaces not feasible for large Ninput interface output interfaceFabricFebruary 23, 2006EECS122 Lecture 12 (AKP)10Input Queues Only input interfaces store packets Advantages Easy to build Simple algorithmsinput interface output interfaceFabric6February 23, 2006EECS122 Lecture 12 (AKP)11Input Queues: Head-of-line Blocking The packet at the head of an input queue cannot be transferred, thus blocking the following packets Output 1Output 2Output 3Input 1Input 2Input 3Cannot be transferred because of output contentionCannot be transferred because of HOL blockingWastes router capacityFebruary 23, 2006EECS122 Lecture 12 (AKP)12Input Queues Only input interfaces store packets Advantages Easy to build Simple algorithms Disadvantages HOL Blocking Need a speedup that eliminates HOL but does not create output queues… About 2 suffices…input interface output interfaceFabric7February 23, 2006EECS122 Lecture 12 (AKP)13Advanced Queuing Functions Packet classification: map each packet to a predefined class use to implement more sophisticated services (e.g., QoS) Flow: a subset of packets between any two endpoints in the network12Schedulerclass 1class 2class nClassifierBuffer managementFebruary 23, 2006EECS122 Lecture 12 (AKP)14Three types of switching fabrics8February 23, 2006EECS122 Lecture 12 (AKP)15RouteTableCPULineCardBufferMemoryLineCardMACBufferMemoryLineCardMACBufferMemoryFwdingCacheFwdingCacheFwdingCacheMACBufferMemory•Typically < 5Gb/s aggregate capacity•Limited by shared bus•1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone)Slide by Nick McKeownShared Bus FabricsFebruary 23, 2006EECS122 Lecture 12 (AKP)16RouteTableCPUBufferMemoryLineInterfaceMACLineInterfaceMACLineInterfaceMACTypically < 0.5Gbps aggregate capacityLimited by rate of shared memoryShared BackplaneLine InterfaceCPUMemorySlide by Nick McKeownShared Memory Based Fabrics9February 23, 2006EECS122 Lecture 12 (AKP)17LineCardMACLocalBufferMemoryCPUCardLineCardMACLocalBufferMemorySwitched BackplaneLine InterfaceCPUMemoryFwdingTableRoutingTableFwdingTableTypically < 50Gbps aggregate capacitySlide by Nick McKeownSwitched FabricsFebruary 23, 2006EECS122 Lecture 12 (AKP)18Switched Fabrics Overcome bus bandwidth limitations Banyan networks, other interconnection nets initially developed to connect processors in multiprocessor Advanced design: fragmenting datagram into fixed length cells, switch cells through the fabric. Cisco 12000: switches Gbps through the interconnection network10February 23, 2006EECS122 Lecture 12 (AKP)19Example: Crossbar Switches Basic Idea N2 switching points not scalable Engineering Idea It is very unlikely that more than L packets will want to go to the same output port simultaneously How many switching points can we save for fixed L?February 23, 2006EECS122 Lecture 12 (AKP)20The Knockout Concentrator Goal: If there are greater than L packets that want to go to the same destination, pick L in a fair manner. Organize the switching elements as if they are implementing a multi-round tournament A game consists of two players and the winner is selected at random (at a switching element) The winner moves on to the next round, while the loser plays a “consolation” rank The top L players are selected.11February 23, 2006EECS122 Lecture 12 (AKP)21Knockout Switch ConcentratorD1 2 3 4OutputsInputsDDDD DDDD DDDDDD = delay elements to insureall packets exit at same timeWhat is the complexity?How many 2X2 elements for fixed L?February 23, 2006EECS122 Lecture 12 (AKP)22Why have multiple rounds? Example: N=8, L=4 After one round, there are four winners and four losers Why not just pick the winners and drop the losers?12February 23, 2006EECS122 Lecture 12 (AKP)23ExampleD1 2 3 4OutputsInputsDDDD DDDD DDDDDD = delay elements to insureall packets exit at same timeStopping after the first roundwould mean that two packets aredropped even though all fourShould be deliveredFebruary 23, 2006EECS122 Lecture 12 (AKP)24The Forwarding Decision Process Datagram Routing: Each packet is independently forwarded at each router Must look up IP address ranges Virtual Circuit Routing: call setup, teardown for each call before data can flow each packet carries VC identifier (not destination host address) every router on source-dest path maintains “state” for each passing connection link, router resources (bandwidth, buffers) may be allocated to VC (dedicated resources = predictable service)13February 23, 2006EECS122 Lecture 12 (AKP)25Datagram Route Lookup Longest Prefix Match Not easy to do at line speeds! It is useful to think of the
View Full Document
Unlocking...