11Final ReviewEE 122: Intro to Communication NetworksFall 2006 (MW 4-5:30 in Donner 155)Vern PaxsonTAs: Dilip Antony Joseph and Sukun Kimhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Additional office hours– Sukun next week: Friday 1-3PM– Dilip: likely next Weds & Thurs (along with regular Fri)– Me next week: regular Weds + by appointment• Course evaluations today ~5:20PM– No 5-minute break during this lecture3Final Review• Saturday Dec. 16, 8AM-11AM, in 2 Le Conte– Near Evans / Bancroft Library• Closed book• You can have one regular-sized (8.5”x11”) sheet ofpaper with notes on both sides• No PDAs, calculators, electronic/Internet gadgets,smart cell phones, jeweler’s loupes, etc.• No Blue Books - all answers on exam sheets• Ensure legibility (pencil + eraser)• Emphasis is on material since midterm4Fundamental Challenges for Networking• Speed-of-light• Desiring a pervasive global network• Need for it to work efficiently/cheaply• Failure of components• Enormous dynamic range– “no such thing as typical”• Disparate parties must work together• Rapid growth/evolution• Crooks & other bad guys5Avoiding Manual Configuration• Dynamic Host Configuration Protocol (DHCP)– End host learns how to send packets– Learn IP address, DNS servers, “gateway”, what’s local• Address Resolution Protocol (ARP)– For local destinations, learn mapping between IPaddress and MAC addresshosthost DNS...hosthost DNS...router router1.2.3.0/23255.255.254.05.6.7.0/241.2.3.7 1.2.3.1561.2.3.481.2.3.19router1A-2F-BB-76-09-AD6Key Ideas in Both Protocols• Broadcasting: when in doubt, shout!• Caching: remember the past for a while• Soft state: eventually forget the past– Key for robustness in the face of unpredictable change27Dynamic Host Configuration ProtocolarrivingclientDHCP server203.1.2.5DHCP discover(broadcast)DHCP offerDHCP requestDHCP ACK(broadcast)8Figuring Out Where To Send Locally• Two cases:– Destination is on the local network So need to address it directly– Destination is not local (“remote”) Need to figure out the first “hop” on the local network• Determining if it’s local: use the netmask– E.g., mask destination IP address w/ 255.255.254.0– Is it the same value as when we mask our own address? Yes = local No = remotehosthost DNS...hosthost DNS...router router1.2.3.0/23255.255.254.05.6.7.0/241.2.3.7 1.2.3.1561.2.3.481.2.3.19router1A-2F-BB-76-09-AD9Address Resolution Protocol• Every node maintains an ARP table– <IP address, MAC address> pair• Consult the table when sending a packet• But: what if IP address not in the table?– Sender broadcasts: “Who has IP address 1.2.3.156?”– Receiver responds: “MAC address 58-23-D7-FA-20-B0”– Sender caches result in its ARP table• Link-layer protocol (RFC826)– Not IP (or UDP or TCP over IP) because IP requires thatyou already know the destination IP address10Example: A Sending a Packet to BHow does host A send an IP packet to host B?ARB11Security Analysis of ARP• Impersonation– Any node that hears request can answer …– … and can say whatever they want• Actual legit receiver never sees a problem– Because even though later packets carry its IP address,its NIC doesn’t capture them since not its MAC address• Or: Man-in-the-middle attack– Imposter forwards everything it receives for destinationbut gets to inspect (& maybe alter) it first• Does the attacker have to “win” a race?– Maybe not, if sender blindly believes ARP responses• Different attack: overflow ARP table, force evictions12Internet Control Message Protocol• ICMP runs on top of IP– Viewed as an integral part of IP Not viewed as a transport protocol• Diagnostics– Triggered when an IP packet encounters a problem E.g., Time Exceeded or Destination Unreachable– ICMP packet sent back to the source IP address Includes the error information (e.g., type and code) … and IP header plus 8+ byte excerpt from original packet– Source host receives the ICMP packet Inspects excerpt (e.g., protocol and ports) … to identify which socket should receive the error313Path MTU Discovery• MTU = Maximum Transmission Unit– Largest IP packet that a link supports• Path MTU (PMTU) = minimum end-to-end MTU– Sender must keep datagrams no larger to avoidfragmentation• How does the sender know the PMTU is?• Strategy (RFC 1191):– Try a desired value– Set DF to prevent fragmentation– Upon receiving Need Fragmentation ICMP … … oops, that didn’t work, try a smaller value14traceroute to www.whitehouse.gov (204.102.114.49), 30 hops max, 40 byte packets 1 cory115-1-gw.EECS.Berkeley.EDU (128.32.48.1) 0.829 ms 0.660 ms 0.565 ms 2 cory-cr-1-1-soda-cr-1-2.EECS.Berkeley.EDU (169.229.59.233) 0.953 ms 0.857 ms 0.727 ms 3 soda-cr-1-1-soda-br-6-2.EECS.Berkeley.EDU (169.229.59.225) 1.461 ms 1.260 ms 1.137 ms 4 g3-8.inr-202-reccev.Berkeley.EDU (128.32.255.169) 1.402 ms 1.298 ms * 5 ge-1-3-0.inr-002-reccev.Berkeley.EDU (128.32.0.38) 1.428 ms 1.889 ms 1.378 ms 6 oak-dc2--ucb-ge.cenic.net (137.164.23.29) 1.731 ms 1.643 ms 1.680 ms 7 dc-oak-dc1--oak-dc2-p2p-2.cenic.net (137.164.22.194) 3.045 ms 1.640 ms 1.630 ms 8 * * * 9 dc-lax-dc1--sac-dc1-pos.cenic.net (137.164.22.126) 13.104 ms 13.163 ms 12.988 ms10 137.164.22.21 (137.164.22.21) 13.328 ms 42.981 ms 13.548 ms11 dc-tus-dc1--lax-dc2-pos.cenic.net (137.164.22.43) 18.775 ms 17.469 ms 21.652 ms12 a204-102-114-49.deploy.akamaitechnologies.com (204.102.114.49) 18.137 ms 14.905 ms 19.730 msLost ReplyRouter doesn’t send ICMPsFinal HopNo PTR record for address15• Each router has a complete picture of the network• How does each router get the global state?– Each router reliably floods information about its neighbors to everyother router (more later)• Each router independently calculates the shortest path fromitself to every other router– Dijkstra’s Shortest Path AlgorithmLink State RoutingHost AHost BHost EHost DHost CN1N2N3N4N5N7N6ABEDCABEDCABEDCABEDCABEDCABEDCABEDC16Dijsktra’s Algorithm1 Initialization:2 S = {A};3 for all nodes v4 if v adjacent to A5 then D(v) = c(A,v);6 else D(v) = ;78 Loop9 find w not in S such that D(w) is a minimum;10 add w to S;11 update D(v) for all v adjacent to w and not in
View Full Document
Unlocking...