2/16/2008115-441 Computer NetworkingLecture 10 – Routers and Routing1Peter SteenkisteDepartments of Computer Science andElectrical and Computer Engineering15-441 Networking, Spring 2008http://www.cs.cmu.edu/~dga/15-441/S08Outlinez ICMPz How do Routers Works?22z Routingz Distance vectorInternet Control Message Protocol (ICMP)z Short messages used to send error & other control informationz Examples» Ping request / response– Can use to check whether remote host reachableDii hbl33»Destination unreachable– Indicates how packet got & why couldn’t go further» Flow control– Slow down packet delivery rate» Redirect– Suggest alternate routing path for future messages» Router solicitation / advertisement– Helps newly connected host discover local router» Timeout– Packet exceeded maximum hop limitIP MTU Discovery with ICMPz Typically send series of packets from one host to anotherhosthostrouterrouterMTU = 4000MTU = 1500MTU = 200044yp y pz Typically, all will follow same route» Routes remain stable for minutes at a timez Makes sense to determine path MTU before sending real packetsz Operation» Send max-sized packet with “do not fragment” flag set» If encounters problem, ICMP message will be returned– “Destination unreachable: Fragmentation needed”– Usually indicates MTU encounteredIP MTU Discovery with ICMPhostrouterMTU = 1500MTU = 2000tICMPFrag. NeededMTU = 200055MTU = 4000hostMTU = 1500IPPacketLength = 4000, Don’t FragmentrouterIP MTU Discovery with ICMPhostMTU = 1500MTU = 2000tICMPFrag. NeededMTU = 1500router66MTU = 4000hostMTU = 1500IPPacketLength = 2000, Don’t Fragmentrouter2/16/20082MTU = 4000IP MTU Discovery with ICMPhosthostMTU = 1500MTU = 2000routerrouter77» When successful, no reply at IP level– “No news is good news”» Higher level protocol might have some form of acknowledgementIPPacketLength = 1500, Don’t FragmentOutlinez ICMPz How do Routers Works?88z Routingz Distance vectorRouter Architecture: Key Functionsz Run routing algorithms/protocol (RIP, OSPF, BGP)» Done by routing processorz Switching datagrams from incoming to outgoing link» Common case handled by line cards99Linput portoutput portLine CardLine Card Line CardRouter Physical LayoutJuniper T seriesCrossbar1010Cisco 12000LinecardsSwitchLine Cardsz Often uses special purpose hardware (e.g. ASICs)1111z Network interface cardsz Fast path (common-case) processing» Decrement TTL» Recompute checksum» Forward to next hop line card– Forwarding engineLine Card: Input Port1212Decentralized switching:z Process common case (fast-path) packets» Decrement TTL, update checksum, forward packetz Given datagram dest., lookup output port using routing table in input port memoryz Queue needed if datagrams arrive faster than forwarding rate into switch fabricPhysical layer:bit-level receptionData link layer:e.g., Ethernet2/16/20083Line Card: Output Port1313z Queuing required when datagrams arrive from fabric faster than the line transmission rateRouter Processorz Runs routing protocol and downloads forwarding table to forwarding enginesz Performs “slow” path processing1414» ICMP error messages» IP option processing» Fragmentation» Packets destined to routerThree Types of Switching Fabrics1515Switching Via a MemoryFirst generation routers Æ looked like PCsz Packet copied by system’s (single) CPUz Speed limited by memory bandwidth (2 bus crossings per datagram)InputPtOutputPtMemory1616PortPortSystem BusModern routers•Input port processor performs lookup, copy into memory• Cisco Catalyst 8500Switching Via a Busz Datagram from input port memory to output port memory via a shared busz Bus contention: switching speed limited by bus 1717pybandwidthz 1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone)Switching Via an InterconnectionNetworkz Overcome bus bandwidth limitationsz Crossbar provides full NxN interconnect» Expensive1818z Banyan networks & other interconnection nets initially developed to connect processors in multiprocessor» Typically less capable than complete crossbarz Cisco 12000: switches Gbps through the interconnection network2/16/20084Bufferingz Suppose we have N inputs and M outputs»Multiple packets for same output Æoutput contentionSwitching fabric may force different1919»Switching fabric may force different inputs to wait Æ Switch contentionz Solution – buffer packets when/where needed: input, switch, or outputz What happens when these buffers fill up?»Packets are THROWN AWAY!! This is where packet loss comes fromOutlinez ICMPz How do Routers Works?2020z Routingz Distance vectorIP Forwarding versus Routingz The Story So Far… » IP addresses are structure to reflect Internet structure» IP packet headers carry these addressesRouter2121» When Packet Arrives at Router– Examine header to determine intended destination– Look up in table to determine next hop in path– Send packet out appropriate portz How do we generate the forwarding table?Graph Modelz Represent each router as nodez Direct link between routers represented by edge» Symmetric links ⇒ undirected graphz Edge “cost” c(x,y) denotes measure of difficulty of using link» delay, $ cost, or congestion level2222z Task» Determine least cost path from every node to every other node– Path cost d(x,y) = sum of link costsAEFCDB23641113Routes from Node AAEFCD23641113Forwarding Table for ADest Cost Next HopA0AB4BC6E2323z Properties» Some set of shortest paths forms tree– Shortest path spanning tree» Solution not unique– E.g., A-E-F-C-D also has cost 7ABC6D7BE2EF5EWays to Compute Shortest Pathsz Centralized» Collect graph structure in one place» Use standard graph algorithm» Disseminate routing tables2424z Link-state» Every node collects complete graph structure» Each computes shortest paths from it» Each generates own routing tablez Distance-vector» No one has copy of graph» Nodes construct their own tables iteratively» Each sends information about its table to neighbors2/16/20085Outlinez ICMPz How do Routers Works?2525z Routingz Distance vectorDistance-Vector MethodEFCD2361113Initial Table for ADest Cost Next HopA0AB4BC ∞ –2626z Idea: At any time, have cost/next hop of best known path to destination» Use cost ∞ when no path is knownz Initially» Only have entries for directly connected nodesADB4D∞–E2EF6FDistance-Vector Updatexzyc(x,z)d(z,y)d(x y)2727z Update(x,y,z)d ← c(x,z) + d(z,y) # Cost of path from x
View Full Document