Outline 15-441 Computer Networking ICMP Lecture 10- Routers and routing Departments of Computer Science and Routing e Distance vector 15-441 Networking, Spring http://www.cs.cmu.edu/-dgal15-441/s08 Internet Control Message Protocol(ICMP IP MTU Discovery with ICMP Short messages used to send error& other control Typically send series of packets from one host to another Makes sense to determine path MTU before sending real packets Send max-sized packet with"do not fragment"flag set newty connected host discover local router " Destination unreachable: Fragmentation Packet exceeded maximum hop lim Usually indicates MTU encountered IP MTU Discovery with ICMP IP MTU Discovery with ICMP MTUE400 MTU#40
2/16/2008 1 15-441 Computer Networking Lecture 10 – Routers and Routing 1 Peter Steenkiste Departments of Computer Science and Electrical and Computer Engineering 15-441 Networking, Spring 2008 http://www.cs.cmu.edu/~dga/15-441/S08 Outline z ICMP z How do Routers Works? 2 2 z Routing z Distance vector Internet Control Message Protocol (ICMP) z Short messages used to send error & other control information z Examples » Ping request / response – Can use to check whether remote host reachable D i i h bl 3 3 » 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 limit IP MTU Discovery with ICMP z Typically send series of packets from one host to another host host router router MTU = 4000 MTU = 1500 MTU = 2000 4 4 yp y p z Typically, all will follow same route » Routes remain stable for minutes at a time z Makes sense to determine path MTU before sending real packets z 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 encountered IP MTU Discovery with ICMP host router MTU = 1500 MTU = 2000 t ICMP Frag. Needed MTU = 2000 5 5 MTU = 4000 host MTU = 1500 IP Packet Length = 4000, Don’t Fragment router IP MTU Discovery with ICMP host MTU = 1500 MTU = 2000 t ICMP Frag. Needed MTU = 1500 router 6 6 MTU = 4000 host MTU = 1500 IP Packet Length = 2000, Don’t Fragment router
IP MTU Discovery with ICMP Outline ICMP e How do Routers works o When successful, no reply at IP level e Distance vector gher level protocol might have some form of Router Architecture: Key Functions Router Physical layout Run routing algorithms/protocol (RIP, OSPF, BGP) Juniper T series Switching datagrams from incoming to outgoing link s Common case handled by line cards Inecards switching fabric Cisco 12000 Li ine car Line Card: Input Port Often uses special purpose hardware(e. g. dada Ink ASICs switch e Network interface cards · Fast path( commo n Decrement TTl ata link layer packet, update ched Forward to next hop line card Queue needed if datagrams Forwarding engine forwarding rate into switch fabric
2/16/2008 2 MTU = 4000 IP MTU Discovery with ICMP host host MTU = 1500 MTU = 2000 router router 7 7 » When successful, no reply at IP level – “No news is good news” » Higher level protocol might have some form of acknowledgement IP Packet Length = 1500, Don’t Fragment Outline z ICMP z How do Routers Works? 8 8 z Routing z Distance vector Router Architecture: Key Functions z Run routing algorithms/protocol (RIP, OSPF, BGP) » Done by routing processor z Switching datagrams from incoming to outgoing link » Common case handled by line cards 9 9 L input port output port Line Card Line Card Line Card Router Physical Layout Juniper T series Crossbar 10 10 Cisco 12000 Linecards Switch Line Cards z Often uses special purpose hardware (e.g. ASICs) 11 11 z Network interface cards z Fast path (common-case) processing » Decrement TTL » Recompute checksum » Forward to next hop line card – Forwarding engine Line Card: Input Port 12 12 Decentralized switching: z Process common case (fast-path) packets » Decrement TTL, update checksum, forward packet z Given datagram dest., lookup output port using routing table in input port memory z Queue needed if datagrams arrive faster than forwarding rate into switch fabric Physical layer: bit-level reception Data link layer: e.g., Ethernet
Line Card: Output Port Router processor Runs routing protocol and downloads 置 forwarding table to forwarding engines Performs"slow"path processing ICMP error messages ster than the line transmission rate w Packets destined to router Three Types of Switching Fabrics Switching via a Memory First generation routers- looked like PCs 口 Packet copied by system's(single) CPU Speed limited by memory bandwidth(2 bus c口m nemory crossbar Modern routers nput port processor performs lookup, copy into memory Cisco Catalyst 8500 Switching Via an Interconnection Switching via a bus Datagram from input port Overcome bus bandwidth memory to output port memory via a shared bus Crossbar provides full NxN speed limited by bus and enterprise routers(not bus Cisco 12000: switches Gbps rough the interconnection
2/16/2008 3 Line Card: Output Port 13 13 z Queuing required when datagrams arrive from fabric faster than the line transmission rate Router Processor z Runs routing protocol and downloads forwarding table to forwarding engines z Performs “slow” path processing 14 14 » ICMP error messages » IP option processing » Fragmentation » Packets destined to router Three Types of Switching Fabrics 15 15 Switching Via a Memory First generation routers Æ looked like PCs z Packet copied by system’s (single) CPU z Speed limited by memory bandwidth (2 bus crossings per datagram) Input P t Output P t Memory 16 16 Port Port System Bus Modern routers • Input port processor performs lookup, copy into memory • Cisco Catalyst 8500 Switching Via a Bus z Datagram from input port memory to output port memory via a shared bus z Bus contention: switching speed limited by bus 17 17 p y bandwidth z 1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone) Switching Via an Interconnection Network z Overcome bus bandwidth limitations z Crossbar provides full NxN interconnect » Expensive 18 18 z Banyan networks & other interconnection nets initially developed to connect processors in multiprocessor » Typically less capable than complete crossbar z Cisco 12000: switches Gbps through the interconnection network
Bufferin Outline Suppose we have N inputs and M outputs ICMP >Multiple packets for same output utput contention o Switching fabric may force different inputs to wait- Switch contention Solution- buffer packets when/where What happens when these buffers fill up? e Distance vector o Packets are THROWN AWAY! This is where packet loss comes from IP Forwarding versus Routing Graph Model Represent each router as node · The Story So Far. Direct link between routers represented by edge Symmetric links undirected graph >IP packet headers carry these addresse Edge" c(x, y) denotes measure of difficulty of using link delay, s cost, or congestion level when Packet Ar Examine header to determine intended ode to every other node Send packet out appropriate port enerate the forwarding table? Routes from node a Ways to Compute Shortest Paths raph structure in one place A0A dard graph algorithm ate routing table ery node collects complete graph structure e Distance-vector has copy of grap n Nodes construct their E.g, A-E-F-C-D also has cost 7 p Each sends information
2/16/2008 4 Buffering z Suppose we have N inputs and M outputs »Multiple packets for same output Æ output contention Switching fabric may force different 19 19 »Switching fabric may force different inputs to wait Æ Switch contention z Solution – buffer packets when/where needed: input, switch, or output z What happens when these buffers fill up? »Packets are THROWN AWAY!! This is where packet loss comes from Outline z ICMP z How do Routers Works? 20 20 z Routing z Distance vector IP Forwarding versus Routing z The Story So Far… » IP addresses are structure to reflect Internet structure » IP packet headers carry these addresses Router 21 21 » 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 port z How do we generate the forwarding table? Graph Model z Represent each router as node z Direct link between routers represented by edge » Symmetric links ⇒ undirected graph z Edge “cost” c(x,y) denotes measure of difficulty of using link » delay, $ cost, or congestion level 22 22 z Task » Determine least cost path from every node to every other node – Path cost d(x,y) = sum of link costs A E F C D B 2 3 6 4 1 1 1 3 Routes from Node A A E F C D 2 3 6 4 1 1 1 3 Forwarding Table for A Dest Cost Next Hop A0A B4B C 6 E 23 23 z 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 7 A B C 6 D7B E2E F5E Ways to Compute Shortest Paths z Centralized » Collect graph structure in one place » Use standard graph algorithm » Disseminate routing tables 24 24 z Link-state » Every node collects complete graph structure » Each computes shortest paths from it » Each generates own routing table z Distance-vector » No one has copy of graph » Nodes construct their own tables iteratively » Each sends information about its table to neighbors
Outline Distance- Vector Method Initial Table forA ●LcMP ● How do routers works? p口 Routing Idea: At any time have costinext hop of best known path to e Distance vector o Use cost oo when no path is known Only have entries for directly connected nodes Distance-Vector Update Algorithm Repeat For every node x ,z) +cx z)+dz,y #cost of path from x to y with first hopz For every destination y f Found d(xy)← Update(xy,z) return dz 8 Updated cost/ next hop return d(x,y), nexthop(x,y) .Existing cost/next hop Start Iteration #1 F1 F*-F3FFOF 1FF2cF3[FF。F
2/16/2008 5 Outline z ICMP z How do Routers Works? 25 25 z Routing z Distance vector Distance-Vector Method E F C D 2 3 6 1 1 1 3 Initial Table for A Dest Cost Next Hop A0A B4B C ∞ – 26 26 z Idea: At any time, have cost/next hop of best known path to destination » Use cost ∞ when no path is known z Initially » Only have entries for directly connected nodes A D B D ∞ – 4 E2E F6F Distance-Vector Update x z y c(x,z) d(z,y) d(x y) 27 27 z Update(x,y,z) d ← c(x,z) + d(z,y) # Cost of path from x to y with first hop z if d < d(x,y) # Found better path return d,z # Updated cost / next hop else return d(x,y), nexthop(x,y) # Existing cost / next hop d(x,y) Algorithm z Bellman-Ford algorithm z Repeat For every node x 28 28 For every neighbor z For every destination y d(x,y) ← Update(x,y,z) z Until converge Start A E F C D 2 3 6 1 1 1 3 Table for A Dst Cst Hop A0A B4B C ∞ – D ∞ – Table for B Dst Cst Hop A4A B0B C ∞ – D3D Optimum 1-hop paths 29 29 A B 4 E2E F6F E ∞ – F1F Table for C Dst Cst Hop A ∞ – B ∞ – C0 C D1 D E ∞ – F1 F Table for D Dst Cst Hop A ∞ – B3B C1C D0D E ∞ – F ∞ – Table for E Dst Cst Hop A2A B ∞ – C ∞ – D ∞ – E0E F3F Table for F Dst Cst Hop A6A B1B C1C D ∞ – E3E F0F Iteration #1 Table for A Dst Cst Hop A0A B4B C 7 F D 7 B Table for B Dst Cst Hop A4A B0B C 2 F D3D Optimum 2-hop paths A E F C D 2 3 6 1 1 1 3 30 30 E2E F 5 E E 4 F F1F Table for C Dst Cst Hop A 7 F B 2 F C0C D1D E 4 F F1F Table for D Dst Cst Hop A 7 B B3B C1C D0D E ∞ – F 2 C Table for E Dst Cst Hop A2A B 4 F C 4 F D ∞ – E0E F3F Table for F Dst Cst Hop A 5 B B1B C1C D 2 C E3E F0F A B 4
Distance Vector: Link Cost Iteration #2 Changes Link cost chang ode detects local link cost change Updates distance table cost change in least cost path, notify neighbors gorithm d fas"xs⑥ Distance Vector: Link Cost Distance Vector: Split Horizon If z routes through Y to get to X Bad news trave Z does not advertise its route to x back to y xs⑥xs⑥x5⑦xs⑦xs Distance Vector: Poison reverse Poison reverse Failures Z routes through Y to get to x tataB tata D匚kF Z tells Y its(2s) distance to x is infinite(so Y won't route to x via z) s 5Ac当c W this completely solve count to infinity problem? Iterations don't converge “ Count to infinity maximum path length3
2/16/2008 6 Iteration #2 Table for A Dst Cst Hop A0A B4B C 6 E D7B Table for B Dst Cst Hop A4A B0B C2F D3D Optimum 3-hop paths A E F C D 2 3 6 1 1 1 3 31 31 E2E F5E E4F F1F Table for C Dst Cst Hop A 6 F B2F C0C D1D E4F F1F Table for D Dst Cst Hop A7B B3B C1C D0D E 5 C F2C Table for E Dst Cst Hop A2A B4F C4F D 5 F E0E F3F Table for F Dst Cst Hop A5B B1B C1C D2C E3E F0F A B 4 Distance Vector: Link Cost Changes Link cost changes: • Node detects local link cost change • Updates distance table • If cost change in least cost path, notify neighbors X Z 4 1 50 Y 1 32 32 algorithm terminates “good news travels fast” Distance Vector: Link Cost Changes Link cost changes: • Good news travels fast • Bad news travels slow - “count to infinity” problem! X Z 4 1 50 Y 60 33 33 algorithm continues on! Distance Vector: Split Horizon If Z routes through Y to get to X : • No need for Z to tell Y about its route to X • Z does not advertise its route to X back to Y algorithm X Z 4 1 50 Y 60 34 34 algorithm terminates ? ? ? Distance Vector: Poison Reverse If Z routes through Y to get to X : • Z tells Y its (Z’s) distance to X is infinite (so Y won’t route to X via Z) • Eliminates some possible timeouts with split horizon • Will this completely solve count to infinity problem? X Z 4 1 50 Y 60 algorithm 35 35 terminates Poison Reverse Failures Table for A Dst Cst Hop C7F Table for B Dst Cst Hop C8A Table for F Dst Cst Hop C1C Table for F Dst Cst Hop C ∞ – Table for A Dst Cst Hop C ∞ – Forced Update F C 6 1 1 A ∞ Table for D Dst Cst Hop C9B Forced Update Table for A 36 36 z Iterations don’t converge z “Count to infinity” z Solution » Make “infinity” smaller » What is upper bound on maximum path length? Table for B Dst Cst Hop C 14 A Forced Update 1 B D 4 Table for A Dst Cst Hop C 13 D Better Route Table for D Dst Cst Hop C 15 B Table for A Dst Cst Hop C 19 D Forced Update • • • Forced Update
Routing Information Protocol (RIP) RIP Updates Earliest IP routing protocol (1 b When router first starts, asks for copy of table for b Neighbors use to iteratively update their tables Sending Updates P Every router listens for updates on UDP port 520 RIP message can contain entries for up to 25 table When every entry changes, send copy of entry to xcept for one causing update(split horizon rule) RIP Staleness/Oscillation Small Infinity Route Timer b Every route has timeout limit of 180 seconds
2/16/2008 7 Routing Information Protocol (RIP) z Earliest IP routing protocol (1982 BSD) » Current standard is version 2 (RFC 1723) z Features » Every link has cost 1 37 37 Every link has cost 1 » “Infinity” = 16 – Limits to networks where everything reachable within 15 hops z Sending Updates » Every router listens for updates on UDP port 520 » RIP message can contain entries for up to 25 table entries RIP Updates z Initial » When router first starts, asks for copy of table for every neighbor » Uses it to iteratively generate own table z Periodic 38 38 » Every 30 seconds, router sends copy of its table to each neighbor » Neighbors use to iteratively update their tables z Triggered » When every entry changes, send copy of entry to neighbors – Except for one causing update (split horizon rule) » Neighbors use to update their tables RIP Staleness / Oscillation Control z Small Infinity » Count to infinity doesn’t take very long z Route Timer 39 39 » Every route has timeout limit of 180 seconds – Reached when haven’t received update from next hop for 6 periods » If not updated, set to infinity » Soft-state refresh Æ important concept!!! z Behavior » When router or link fails, can take minutes to stabilize
