IPRouting and Forwardingcs144Section 2Juan Batiz-BenetBased on slides by: Phil Levis, David Mazières, Ben NhamFriday, October 9, 2009Announcements•Lab 1 due yesterday•Lab 2 due next thursday (Oct 15)•Midterm looming (Oct 22)Friday, October 9, 2009Lab 2 Overview•Grader will be released so you can test your code for Lab 1•Sliding send and receive window >1 packet•Connection demultiplexingFriday, October 9, 2009Internet ProtocolThin Hourglass of the InternetGlue connecting multiple networksFriday, October 9, 2009IP•Connectionless datagram service-No per-flow state in routers-Packets may appear out of sequence•Benefits from the end to end model:-Unreliable-Best EffortFriday, October 9, 2009IP Traffic•Addressing-Gives hosts unique names-Sets of addresses represented by subnets•Routing-Path from source to destination-Routing algorithms build tables to pick best routes•Forwarding-Use routing table to determine correct egress port for an incoming packetFriday, October 9, 2009IP: Addressing•Every host in the network has a globally unique IP address*•IPv4**: 32-bit number, usually split in 4 octets:-128.12.92.1 = 1000000 . 00001100 . 01011100 . 00000001•Grouped IP address:-Provides hierarchy-Consolidates routing tables* ignoring NAT and other details. More on Lec 12** IPv6 is 128 bit. Replacement for IPv4. More on Lec 9 Friday, October 9, 2009Old Classful AddressingFriday, October 9, 2009Old Classful AddressingDEPRECATEDFriday, October 9, 2009CIDRClassless Inter-Domain Routing•IP address / Netmask Prefix-Variable prefixes provide hierarchy-171.64.0.0/14 (256k hosts) -maps to range 171.64.0.0-171.64.255.255•Consider masked IP address 10.2.0.0 How many networks could be represented?Friday, October 9, 2009CIDRClassless Inter-Domain Routing•IP address / Netmask Prefix-Variable prefixes provide hierarchy-171.64.0.0/14 (256k hosts) -maps to range 171.64.0.0-171.64.255.255•Consider masked IP address 10.2.0.0 How many networks could be represented?18 -- (1.2.0.0/15, 1.2.0.0/16, ..., 1.2.0.0/32)Friday, October 9, 2009Routing with CIDR•Find the entry with the longest prefix matching•What is the LPM for:‣12.1.1.200‣12.1.0.20‣128.12.92.53Friday, October 9, 2009Routing with CIDR•Find the entry with the longest prefix matching•What is the LPM for:‣12.1.1.200‣12.1.0.20‣128.12.92.53Friday, October 9, 2009Fragmentation•When an IP packet needs to traverse a link with a lower MTU, it can be fragmented.•Does fragmenting increase or reduce the likelihood of dropping the packet? Friday, October 9, 2009Fragmentation Problem•Increases it. Each fragment can be dropped independently of the others, yet the packet needs all fragments to be reconstructed.•Consider sending a 2100 byte datagram over a link with MTU of 700 bytes. How many fragments are generated? What fields are changed in the IP frame?Friday, October 9, 2009Fragmentation Problem•Consider sending a 2100 byte datagram over a link with MTU of 700 bytes. •How many fragments are generated? 4 -- 700 MTU = 680b of data + 20b IP header2100 / 680 = 3.08, so at least 4 fragments.•What fields are changed in the IP frame? Total Length, More flag, Fragment Offset, ChecksumIdentifier field is not changed, but used to reconstruct packet.Friday, October 9, 2009Routing Algorithms•Link State -Global state -- Every node knows all link costs-Use Link State Packets (node id, link costs, seqno, TTL)-To Route, use Dijkstra’s Algorithm!•Distance Vector-Only local (neighbors) state-Track only (Destination, Cost, NextHop)-Updates local table if better route received-Propagates over time-Susceptible to loopsFriday, October 9, 2009Dijkstra’s Algorithm•Given a graph G and a starting vertex s, find shortest path from s to any other vertex in G•Use greedy algorithm: -Maintain a set S of nodes for which we know the shortest path-On each iteration, grow S by one vertex, choosing shortest path through S to any other node not in S-If the cost from S to any other node has decreased, update itFriday, October 9, 2009Dist. Vector Example 1DestinationCostNextHopA1AB1BD1DE2AF2AG2DC’s Routing TableFriday, October 9, 2009Dist. Vector Example 11. Link C-D failsDestinationCostNextHopA1AB1BD∞DE2AF2AG2DC’s Routing TableFriday, October 9, 2009Dist. Vector Example 11. Link C-D fails2. C advertises (D, ∞) to B and ADestinationCostNextHopB1BC1CD2CE1EF1FG2FA’s Routing Table(D, ∞)(D, ∞)Friday, October 9, 2009Dist. Vector Example 11. Link C-D fails2. C advertises (D, ∞) to B and A3. A has C as its NextHop for D, so A updates and advertises (D, ∞) to B, E, F(D, ∞)(D, ∞)DestinationCostNextHopB1BC1CD∞CE1EF1FG2FA’s Routing Table(D, ∞)Friday, October 9, 2009Dist. Vector Example 11. Link C-D fails2. C advertises (D, ∞) to B and A3. A has C as its NextHop for D, so A updates and advertises (D, ∞) to B, E, F4. F ignores (D, ∞) as (D, 2, G) is better.(D, ∞)DestinationCostNextHopA1AB2AC2AD2GE2AG1GF’s Routing TableFriday, October 9, 2009Dist. Vector Example 11. Link C-D fails2. C advertises (D, ∞) to B and A3. A has C as its NextHop for D, so A updates and advertises (D, ∞) to E and F4. F ignores (D, ∞) as (D, 2, G) is better.5. F sends an advertisement of (D, 2) to A(D, 2)DestinationCostNextHopB1BC1CD∞CE1EF1FG2FA’s Routing TableFriday, October 9, 2009Dist. Vector Example 11. Link C-D fails2. C advertises (D, ∞) to B and A3. A has C as its NextHop for D, so A updates and advertises (D, ∞) to E and F4. F ignores (D, ∞) as (D, 2, G) is better.5. F sends an advertisement of (D, 2) to A6. A updates and advertises (D, 3) to B, C, E(D, 3)DestinationCostNextHopB1BC1CD3FE1EF1FG2FA’s Routing Table(D, 3)(D, 3)Friday, October 9, 2009Dist. Vector Example 11. Link C-D fails2. C advertises (D, ∞) to B and A3. A has C as its NextHop for D, so A updates and advertises (D, ∞) to E and F4. F ignores (D, ∞) as (D, 2, G) is better.5. F sends an advertisement of (D, 2) to A6. A updates and advertises (D, 3) to B, C, E7. C updates and advertises (D, 4) to BDestinationCostNextHopA1AB1BD4AE2AF2AG2DC’s Routing Table(D, 4)Friday, October 9, 2009Loops!•Happen when old state causes nodes to route through each other ad infinitum.•No split horizon: 2 node loops•Split Horizon: Prevent 2 node loopsNever advertise a route to its next hop•SH with poison reverse: Better prevent 2 node loops. Advertise ∞ to the route’s next hop.Friday, October 9, 2009No split
View Full Document
Unlocking...