10/16/2012

Link-Layer and ICMP

EE122 Fall 2012
Scott Shenker
http://inst.eecs.berkeley.edu/~ee122/
Materials with thanks to Jennifer Rexford, Ion Stoica, Vern Paxson
and other colleagues at Princeton and UC Berkeley

Project 1 Midterm
• Distribution of grades: • Average score 104 (out of 119)
– 50% perfect score of 240
• Standard deviation 11
– 90% above 140
• 50th percentile 107
• Giving people a second chance: • 90th percentile 115
– Fix your project, get it running
– We’ll figure out the penalties later

• Constraints:
– Fix must cause multiple test cases to go from fail to pass
– Regrades get maximum score of 200
– Contact Anand/Colin for details……
3 4

Question-by-question…. Question-by-question….
1. True/False: about 10% got full credit 6. Timer values: about 50% got full credit
Peak about 18 out of 20
7. Addressing: about 70% got full credit
2. Multiple choice: about 8% got full credit
Peak about 18 out of 20
8. Learning switch: about 60% got full credit
IP checksum only looks at header 9. DNS: about 70% got full credit
UDP header does not include addresses
10.Sliding window: about 70% got full credit
3. TCP Basics: about 50% got full credit
4. Seq. of Messages: about 80% got full credit
5. The Real World: about 90% got full credit

5 6

1
10/16/2012

Humorous answers…. Suggested Bonus Questions…

• Who is the unsung hero? • What is Scott Shenker’s brother’s profession?
– “me”
– “Al Gore” (surprisingly popular answer)
• How many citations does Shenker have?

• What letter caused the first demo to fail? • Draw a giraffe

– “love letter”
– “S for shenker”

• In what year?
– “1776”,
– “122 BCE”
– “12000 BC (there was time travel involved)” 7 8

The Bet…. Victory is Mine!

• 8 people with a score of 119 on questions 1-10
– I geared the review to the test way too closely
– But I felt like I had not sufficiently covered the “putting it
all together” questions in lecture/sections

• 5 of the 119 scores got three bonus questions right

– The fact you knew the answers to the bonus questions is
a very bad sign….

• 0 of the 119 scores got four bonus questions

9 10

But in the spirit of fair play….

• I won’t collect on the bet

• I will donate my stake of $220 to the EE122 review

sessions refreshment fund Where Are We?

• I’m taking bets for the final….(10:1 odds again)

• I was accused (in writing) for “cheating” on the bet

– I won’t forget who you are…….
– P. S. My TAs agree with you
– P. P. S. None of them will ever graduate
11 12

2
10/16/2012

What Do We Know? Missing Pieces (covered today)

• How to route • Basics of link-layer (L2) networks
– L2 (learning switches) – Will do details of ethernet later
– L3 (DV, LS)

• How to get an IP address (DHCP) • Using link-layer networks to reach destination

– L2 involved at first/last hops (and in between)
• How to resolve names to IP addresses (DNS)
• How to forward packets (LPM) • How do I find out about network problems?
– Loops, MTU limitations, etc.
• How to deliver packet reliably (TCP)
• How to access content (HTTP)
• ……
13 14

Message, Segment, Packet, and Frame

host host

HTTP message
HTTP HTTP

Background on Link-Layer TCP segment

TCP TCP

router router

IP packet IP packet IP packet

IP IP IP IP

Ethernet Ethernet SONET SONET Ethernet Ethernet

interface interface interface interface interface interface

15 16
Ethernet frame SONET frame Ethernet frame

Focus on Link-Layer Adapter-to-Adapter Communication

Ethernet Ethernet SONET SONET Ethernet Ethernet datagram
interface interface interface interface interface interface link layer protocol

Ethernet frame SONET frame frame frame

Ethernet frame
sending adapter adapter receiving
node node

• Link layer implemented in adapter (network interface card; NIC)

– Ethernet card, 802.11 card
• Sending side:
– Encapsulates datagram in a frame
– Determines local addressing, adds error checking, controls
transmission
• Receiving side
– Recognizes arrival, looks for errors, possibly acknowledges
17 – Extracts datagram and passes to receiving node 18

3
10/16/2012

Link-Layer Services MAC Address vs. IP Address

• Encoding • MAC addresses (used in link-layer)
– Representing the 0s and 1s – Hard-coded in read-only memory when adapter is built
• Framing – Like a social security number
– Encapsulating packet into frame, adding header, trailer – Flat name space of 48 bits (e.g., 00-0E-9B-6E-49-76)
– Using MAC addresses rather than IP addresses – Portable, and can stay the same as the host moves
– Used to get packet between interfaces on same network
• Error detection
– Errors caused by signal attenuation, noise • IP addresses
– Receiver detects presence, may ask for repeat – Configured, or learned dynamically
• Resolving contention – Like a postal mailing address
– Deciding who gets to transmit when multiple senders – Hierarchical name space of 32 bits (e.g., 12.178.66.9)
want to use a shared media – Not portable, and depends on where the host is attached
– Used to get a packet to destination IP subnet
• Flow control (pacing between sender & receiver)
19 20

Broadcast at Link-Level Broadcast at IP Level

• Use broadcast address: ff:ff:ff:ff:ff:ff • Can't broadcast to all IP hosts

• If have return MAC address, use that in response • But application might want to send “local”
broadcast

• Unless want everyone to know result

• Uses IP broadcast address 255.255.255.255

• Link-layer then uses link-layer broadcast

21 22

Sending Packets Over Link-Layer

1.2.3.53 1.2.3.156
host ... DNS
host
IP packet
1.2.3.53 Steps in Sending a Packet
1.2.3.156
router

Mask: 255.255.255.0
What do hosts need to know?
And how do they find out?
• Adapters only understand MAC addresses
– Translate the destination IP address to MAC address
– Encapsulate the IP packet inside a link-level frame
23 24

4
10/16/2012

Steps in reaching a Host Sending a Packet

• First look up IP address • On same subnet:
– Use MAC address of destination.
– How do hosts know?
• Need to know where local DNS server is
– DHCP • On some other subnet:
– Use MAC address of first-hop router.
• Also needs to know its own IP address – How do they know?
– DHCP
• And how can a host tell whether destination is on
same or other subnet?
– Use the netmask
26
– DHCP 27

DHCP Refresher DHCP Supplies Basic Information

• Dynamic Host Configuration Protocol (DHCP) • IP address
– End host learns how to send packets
• Mask
– Learn IP address, DNS servers, “gateway”, what’s local
• Gateway router
• Have already described DHCP operation • DNS server
– Sequence of broadcasts, no configuration needed

1.2.3.48 1.2.3.7 1.2.3.156

... ...
• Now what?
host host DNS 1A-2F-BB-76-09-AD host host DNS

1.2.3.0/24 5.6.7.0/24
255.255.255.0 1.2.3.19
router router router
28 29

Sending A Packet: Which Destination? Determining if Address is Local

• If destination is on the local network • Use the netmask
– Need to address it directly (MAC address) – E.g., mask destination IP address w/ 255.255.255.0
• If destination is not local (“remote”) • Is it same value as our own masked address?
– Need to figure out the first “hop” on the local network o Yes = local
– Need MAC address of first hop router o No = remote

1.2.3.48 1.2.3.7 1.2.3.156 1.2.3.48 1.2.3.7 1.2.3.156

host ... DNS 1A-2F-BB-76-09-AD host host ... DNS host ... DNS 1A-2F-BB-76-09-AD host host ... DNS
host host

1.2.3.0/24 5.6.7.0/24 1.2.3.0/24 5.6.7.0/24

255.255.255.0 1.2.3.19 255.255.255.0 1.2.3.19
router router router 30 router router router 31

5
10/16/2012

In Both Cases, Need to Send Locally Address Resolution Protocol

• If it’s remote, look up first hop in (very small) local • Every node maintains an ARP table
routing table (in case there are multiple first hops) – <IP address, MAC address> pair
– E.g., by default, route via 1.2.3.19
– Now do the local case but for 1.2.3.19 rather than
ultimate destination IP address • Consult the table when sending a packet
– Map destination IP address to destination MAC address
1.2.3.48 1.2.3.7 1.2.3.156
... ... – Encapsulate and transmit the data packet
host host DNS 1A-2F-BB-76-09-AD host host DNS

1.2.3.0/24 5.6.7.0/24
255.255.255.0 1.2.3.19
• But: what if IP address not in the table?
– Sender broadcasts: “Who has IP address 1.2.3.156?”
router router router
– Receiver responds: “MAC address 58-23-D7-FA-20-B0”
– Sender caches result in its ARP table
• For the local case, need to determine the
destination’s MAC address 32 33

Example: A Sending a Packet to B Example: A Sending a Packet to B

How does host A send an IP packet to host B? How does host A send an IP packet to host B?

A A

R R
B B

Take a few minutes, break into groups, 1. A sends packet to R.

figure out how this would work….. 2. R sends packet to B.
34 35

Host A Decides to Send Through R Host A Sends Packet Through R

• Host A constructs an IP packet to send to B • Host A learns the MAC address of R’s interface
– Source 111.111.111.111, destination 222.222.222.222 – ARP request: broadcast request for 111.111.111.110
• Host A has a gateway router R – ARP response: R responds with E6-E9-00-17-BB-4B
– Used to reach destinations outside of 111.111.111.0/24 • Host A encapsulates the packet and sends to R
– Address 111.111.111.110 for R learned via DHCP

A A

R R
B36 B37

6
10/16/2012

Two points: how to Forward Packet

R Decides R Sends Packet to B
• Routing table points to this port
• Router R’s adapteraddress
• Destination receivesisthe packet
within • Router R’s learns the MAC address of host B
– R extracts the IP packet from the Ethernet frame – ARP request: broadcast request for 222.222.222.222
mask of port’s address (i.e., local)
– R sees the IP packet is destined to 222.222.222.222 – ARP response: B responds with 49-BD-D2-C7-56-2A
• Router R consults its forwarding table
• Router R encapsulates the packet and sends to B
– Packet matches 222.222.222.0/24 via other adapter

A A

R R
B38 B39

Security Analysis of ARP Key Ideas in Both ARP and DHCP

• Impersonation • Broadcasting: Can use broadcast to make contact
– Any node that hears request can answer … – Scalable because of limited size
– … and can say whatever they want

• Caching: remember the past for a while

• Actual legit receiver never sees a problem – Store the information you learn to reduce overhead
– Because even though later packets carry its IP address, – Remember your own address & other host’s addresses
its NIC doesn’t capture them since not its MAC address

• Soft state: eventually forget the past

– Associate a time-to-live field with the information
– … and either refresh or discard the information
– Key for robustness in the face of unpredictable change
40 41

Why Not Use DNS-Like Tables? Two Different Issues

• When host arrives: • Setting up the database:
– Assign it an IP address that will last as long it is present – Names: explicit creation, tied to “static” addresses
– Add an entry into a table in DNS-server that maps MAC o DNS need only handle occasional updates
to IP addresses (i.e., no need for ARP!) – Hosts: come and go without explicitly informing network
o Must do MAC-IP mapping on demand
– But could leverage DHCP
o DHCP knows when a host arrives
• Think about it for a few minutes, talk in groups o And DHCP messages already contain MAC addresses

• Using the MAC address:

– So if I get MAC address when I look up address in DNS,
how can I use that information?
– The database must live in each router and host for it to
save any time….but it does cut down on broadcasting
42 43

7
10/16/2012

Network Control Messages

5 Minute Break
(and how to use them for discovery)

44 45

What Errors Might A Router See? Which should network tell host about?
• Dead-end: No route to destination • No route to destination?
– Host can’t detect or fix routing failure.
• Sign of a loop: TTL expires • TTL expires?
– Host can’t detect or fix routing loop.
• Can’t physically forward: packet too big • Packet too big (with DF set)?
– And has DF flag set –This
Hostassumes
can adjustwe want
packet to but
size, bind thetell difference
can’t
meaning of packet drops
between congestion dropsand to congestion
MTU drops
• Can’t keep up with traffic: buffer overflowing • Buffer overflowing?
– Transport congestion control can detect/deal with this
• Header corruption or ill-formed packets
• Header corruption or ill-formed packets?
• …. 46 – Host can’t fix corruption, but can fix formatting errors47

Router Response to Problems? Error Reporting Helps Diagnosis

• Router doesn’t really need to respond • Silent failures are really hard to diagnose
– Best effort means never having to say you’re sorry
– So, IP could conceivably just silently drop packets
• IP includes feedback mechanism for network
problems, so they don’t go undetected
• Network is already trying its best
– Routing is already trying to avoid loops/dead-ends
– Network can’t reduce packet size (in DF packets) • Internet Control Message Protocol (ICMP)
– Network can’t reduce load, nor fix format problems
• The Internet “print” statement
• What more can/should it do?
• Runs on IP, but viewed as integral part of IP
48 49

8
10/16/2012

Internet Control Message Protocol Types of Control Messages

• Triggered when IP packet encounters a problem • Need Fragmentation
– E.g., Time Exceeded or Destination Unreachable – IP packet too large for link layer, DF set

• TTL Expired
• ICMP packet sent back to the source IP address
– Includes the error information (e.g., type and code) – Decremented at each hop; generated if  0
– IP header plus 8+ byte excerpt from original packet • Unreachable
– Subtypes: network / host / port
• Source host receives the ICMP packet o (who generates Port Unreachable?)
– Inspects excerpt (e.g., protocol/ports) to identify socket
• Source Quench
– Old-style signal asking sender to slow down
• Exception: not sent if problem packet is ICMP
– And just for fragment 0 of a group of fragments • Redirect
50 – Tells source to use a different local router 51

Using ICMP Discovering Network Path Properties

• ICMP intended to tell host about network problems • PMTU Discovery: What is largest packet that go
– Diagnosis through the network w/o needing fragmentation?
– Won’t say more about this…. – Most efficient size to use
– (Plus fragmentation can amplify loss)

• Can exploit ICMP to elicit network information

– Discovery • Traceroute:
– Will focus on this…. –What is the series of routers that a packet
traverses as it travels through the network?

• Ping:
52 – Simple RTT measurements 53

Ping: Echo and Reply Path MTU Discovery

• ICMP includes simple “echo” functionality • MTU = Maximum Transmission Unit
– Sending node sends an ICMP Echo Request message – Largest IP packet that a link supports
– Receiving node sends an ICMP Echo Reply
• Path MTU (PMTU) = minimum end-to-end MTU
– Must keep datagrams no larger to avoid fragmentation
• Ping tool
– Tests connectivity with a remote host • How does the sender know the PMTU is?
– … by sending regularly spaced Echo Request • Strategy (RFC 1191):
– … and measuring delay until receiving replies – Try a desired value
– Set DF to prevent fragmentation
• If you have never used ping, do it tonight! – Upon receiving Need Fragmentation ICMP …
– One of the few ways you actually “see” the network o … oops, that didn’t work, try a smaller value

54 55

9
10/16/2012

Issues with Path MTU Discovery Discovering Routing via Time Exceeded
• What set of values should the sender try? • Host sends an IP packet
– Usual strategy: work through “likely suspects” – Each router decrements the time-to-live field
– E.g., 4352 (FDDI), 1500 (Ethernet),
1480 (IP-in-IP over Ethernet), 296 (some modems) • If TTL reaches 0
– Router sends Time Exceeded ICMP back to the source
• What if the PMTU changes? (how could it?) – Message identifies router sending it
– Sender will immediately see reductions in PMTU (how?) o Since ICMP is sent using IP, it’s just the IP source address
– Sender can periodically try larger values o And can use PTR record to find name of router

1.2.3.7 5.6.7.156
• What if Needs Fragmentation ICMP is lost? host ... DNS host ... DNS
host host
– Retransmission will elicit another one

• How can The Whole Thing Fail? 8.9.10.11

– “PMTU Black Holes”: routers that don’t send the ICMP Time exceeded router router router
56 57

traceroute to www.whitehouse.gov (204.102.114.49),

30 hops max, 40 byte packets
Traceroute: Exploiting Time Exceeded
• Time-To-Live field in IP packet header
– Source sends a packet with TTL ranging from 1 to n
– Each router along the path decrements the TTL
– “TTL exceeded” sent when TTL reaches 0
• Traceroute tool exploits this TTL behavior

Time
TTL=1 exceeded

destination
source TTL=2

Send packets with TTL=1, 2, …

and record source of Time Exceeded message
58 59

traceroute to www.whitehouse.gov (204.102.114.49), traceroute to www.whitehouse.gov (204.102.114.49),

30 hops max, 40 byte packets 30 hops max, 40 byte packets
1 cory115-1-gw.EECS.Berkeley.EDU (128.32.48.1) 1 cory115-1-gw.EECS.Berkeley.EDU (128.32.48.1)
0.829 ms 0.660 ms 0.565 ms 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

60 61

10
10/16/2012

traceroute 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 * Lost Reply
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*** Router doesn't send ICMPs
9 dc-lax-dc1--sac-dc1-pos.cenic.net (137.164.22.126)
13.104 ms 13.163 ms 12.988 ms No PTR record for address
10 137.164.22.21 (137.164.22.21) Final Hop
13.328 ms 42.981 ms 13.548 ms
11 dc-tus-dc1--lax-dc2-pos.cenic.net (137.164.22.43)
18.775 ms 17.469 ms 21.652 ms
12 a204-102-114-49.deploy.akamaitechnologies.com (204.102.114.49)
18.137 ms 14.905 ms 19.730 ms 62

11