EE 122: Router DesignRoutersWhat a Router Looks LikeWhy Understand Router DesignWhy Do We Need Faster Routers?Why we Need Faster Routers 1: To prevent routers from being the bottleneckWhy we Need Faster Routers 2: To reduce cost, power & complexity of POPsRequirementsGeneric Router ArchitecturePowerPoint PresentationSlide 11Slide 12SpeedupTypical Functions Performed by Input Interface on Data PathTypical Functions Performed by Output InterfaceTypical Functions Performed by Output Interface (cont’d)InterconnectOutput Queued (OQ) RoutersInput Queueing (IQ) RoutersHead-of-line BlockingA Router with Input Queues Head of Line BlockingSolution to Avoid Head-of-line BlockingCombined Input-Output Queueing (CIOQ) RoutersEE 122: Router DesignKevin LaiSeptember 25, [email protected] 2RoutersA router consists-A set of input interfaces at which packets arrive-A set of output interfaces from which packets depart-Some form of interconnect connecting inputs to outputsRouter implements two main functions-Forward packet to corresponding output interface-Manage bandwidth and buffer space [email protected] 3What a Router Looks LikeCisco GSR 12416 Juniper M1606ft19”2ftCapacity: 160Gb/sPower: 4.2kW3ft2.5ft19”Capacity: 80Gb/sPower: 2.6kWSlide by Nick [email protected] 4Why Understand Router DesignMany companies make switches and routers-e.g., Cisco, Juniper, NortelMany other devices have a similar structure-e.g., PC’s internal interconnect, multi-processor interconnectSwitch design dictates what can be done at higher layers-e.g., per flow state is expensive,the need to minimize per packet processing [email protected] 5Why Do We Need Faster Routers?1. To prevent routers becoming the bottleneck in the Internet.2. To increase POP capacity, and to reduce cost, size and [email protected] 60,11101001000100001985 1990 1995 2000Spec95Int CPU resultsWhy we Need Faster Routers 1: To prevent routers from being the bottleneck0,11101001000100001985 1990 1995 2000Fiber Capacity (Gbit/s)TDM DWDMPacket processing Power Link Speed2x / 18 months 2x / 7 monthsSource: SPEC95Int & David Miller, Stanford.Slide by Nick [email protected] 7POP with smaller routersWhy we Need Faster Routers 2: To reduce cost, power & complexity of POPsPOP with large routersPorts: Price >$100k, Power > 400W. It is common for 50-60% of ports to be for interconnection.Slide by Nick [email protected] 8RequirementsPower-generates heat, costs money- < 5kWSize-space costs money- < 2m3BandwidthPorts-number of external linksPriceSome customers want-Multicast-Quality of [email protected] 9Generic Router ArchitectureInput and output interfaces are connected through an interconnectA interconnect 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 [email protected] 10RouteTableCPUBufferMemoryLineInterfaceMACLineInterfaceMACLineInterfaceMACTypically <0.5Gb/s aggregate capacityFirst Generation RoutersShared BackplaneLine InterfaceCPUMemorySlide by Nick [email protected] 11Second Generation RoutersRouteTableCPULineCardBufferMemoryLineCardMACBufferMemoryLineCardMACBufferMemoryFwdingCacheFwdingCacheFwdingCacheMACBufferMemoryTypically <5Gb/s aggregate capacitySlide by Nick [email protected] 12Third Generation RoutersLineCardMACLocalBufferMemoryCPUCardLineCardMACLocalBufferMemorySwitched BackplaneLine InterfaceCPUMemoryFwdingTableRoutingTableFwdingTableTypically <50Gb/s aggregate capacitySlide by Nick [email protected] 13SpeedupC – input/output link capacityRI – maximum rate at which an input interface can send data into interconnectRO – maximum rate at which an output can read data from interconnectB – maximum aggregate interconnect transfer rateInterconnect speedup: B/CInput speedup: RI/COutput speedup: RO/Cinput interface output [email protected] 14Typical Functions Performed by Input Interface on Data PathPacket 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 [email protected] 15Typical Functions Performed by Output InterfaceBuffer management: decide when and which packet to dropScheduler: decide when and which packet to [email protected] 16Typical Functions Performed by Output Interface (cont’d)Packet classification: map each packet to a predefined flow/connection (for datagram forwarding)-use to implement more sophisticated services (e.g., QoS)Flow: a subset of packets between any two endpoints in the network12Schedulerflow 1flow 2flow nClassifierBuffer [email protected] 17Interconnect Point-to-point switch allows to simultaneously transfer a packet between any two disjoint pairs of input-output interfacesGoal: come-up with a schedule that-Provide Quality of Service-Maximize 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 [email protected] 18Output Queued (OQ) 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 [email protected] 19Input Queueing (IQ) RoutersOnly input interfaces store packetsAdvantages-Easy to built •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 [email protected] 20Head-of-line BlockingThe cell at the head of an input queue cannot be transferred, thus blocking the following cells Cannot betransferred because output buffer
View Full Document