Translating Addresses

Computer Networks

 Three different kinds of addresses

Host names (e.g., www.cnn.com)
IP addresses (e.g., 64.236.16.20)
MAC addresses (e.g., 00-15-C5-49-04-A9)

Protocols for translating between addresses

Domain Name System (DNS)
Dynamic Host Configuration Protocol (DHCP)
Address Resolution Protocol (ARP)

Two main topics

Decentralized management of the name space
Boot-strapping an end host that attaches to the net
2

Domain Name System (DNS)

Proposed in 1983 by Paul Mockapetris
3

Domain Name System

Computer science concepts underlying DNS
Indirection: names in place of addresses
Hierarchy: in names, addresses, and servers
Caching: of mappings from names to/from addresses

DNS software components

DNS resolvers
DNS servers

DNS queries
Iterative queries
Recursive queries

DNS caching based on time-to-live (TTL)

Host Names vs. IP addresses

Host names
Mnemonic name appreciated by humans
Variable length, alpha-numeric characters
Provide little (if any) information about location
Examples: www.cnn.com and ftp.eurocom.fr

IP addresses
Numerical address appreciated by routers
Fixed length, binary number
Hierarchical, related to host location
Examples: 64.236.16.20 and 193.30.227.161
5

Separating Naming and Addressing

Names are easier to remember
www.cnn.com vs. 64.236.16.20

Addresses can change underneath

Move www.cnn.com to 173.15.201.39
E.g., renumbering when changing providers

Name could map to multiple IP addresses

www.cnn.com to multiple replicas of the Web site

Map to different addresses in different places

Address of a nearby copy of the Web site
E.g., to reduce latency, or return different content

Multiple names for the same address

E.g., aliases like ee.mit.edu and cs.mit.edu

Strawman Solution #1: Local File

Original name to address mapping
Flat namespace
/etc/hosts
SRI kept main copy
Downloaded regularly

Count of hosts was increasing: moving from

a machine per domain to machine per user
Many more downloads
Many more updates
7

Strawman Solution #2: Central Server

Central server
One place where all mappings are stored
All queries go to the central server

Many practical problems

Single point of failure
High traffic volume
Distant centralized database
Single point of update
Does not scale
Need a distributed, hierarchical collection of servers

Domain Name System (DNS)

Properties of DNS
Hierarchical name space divided into zones
Distributed over a collection of DNS servers

Hierarchy of DNS servers

Root servers
Top-level domain (TLD) servers
Authoritative DNS servers

Performing the translations

Local DNS servers
Resolver software

DNS Root Servers

13 root servers (see http://www.root-servers.org/)
Labeled A through M

E NASA Mt View, CA
F Internet Software C. Palo
Alto, CA (and 17 other
locations)

A Verisign, Dulles, VA
C Cogent, Herndon, VA (also Los Angeles)
D U Maryland College Park, MD
G US DoD Vienna, VA
K RIPE London (also Amsterdam, Frankfurt)
H ARL Aberdeen, MD
I Autonomica, Stockholm
J Verisign, ( 11 locations)
(plus 3 other locations)

m WIDE Tokyo

B USC-ISI Marina del Rey, CA

L ICANN Los Angeles, CA
10

TLD and Authoritative DNS Servers

Top-level domain (TLD) servers
Generic domains (e.g., com, org, edu)
Country domains (e.g., uk, fr, ca, jp)
Typically managed professionally
Network Solutions maintains servers for com
Educause maintains servers for edu

Authoritative DNS servers

Provide public records for hosts at an organization
For the organizations servers (e.g., Web and mail)
Can be maintained locally or by a service provider

11

Distributed Hierarchical Database

unnamed root

com

edu

org
generic domains

bar

uk

ac

zw

arpa

country domains
ac

inaddr

west

east

cam

12

foo

my

usr

34

my.east.bar.edu

usr.cam.ac.uk
56
12
12.34.56.0/24

Using DNS
Local DNS server (default name server)
Usually near the end hosts who use it
Local hosts configured with local server (e.g.,
/etc/resolv.conf) or learn the server via DHCP

Client application
Extract server name (e.g., from the URL)
Do gethostbyname() to trigger resolver code

Server application
Extract client IP address from socket
Optional gethostbyaddr() to translate into name 13

Example
root DNS server

Host at cis.poly.edu
wants IP address for
gaia.cs.umass.edu

2
3

TLD DNS server

4

local DNS server

dns.poly.edu

requesting host
cis.poly.edu

authoritative DNS server

dns.cs.umass.edu
gaia.cs.umass.edu
14

Recursive vs. Iterative Queries

root DNS server

Recursive query
Ask server to get
answer for you
E.g., request 1
and response 8

Iterative query
Ask server who
to ask next
E.g., all other
request-response
pairs

2
3

TLD DNS server

4

local DNS server

dns.poly.edu

requesting host

authoritative DNS server

dns.cs.umass.edu

cis.poly.edu
15

DNS Caching
Performing all these queries take time
And all this before the actual communication takes place
E.g., 1-second latency before starting Web download

Caching can substantially reduce overhead

The top-level servers very rarely change
Popular sites (e.g., www.cnn.com) visited often
Local DNS server often has the information cached

How DNS caching works

DNS servers cache responses to queries
Responses include a time to live (TTL) field
Server deletes the cached entry after TTL expires
16

Negative Caching
Remember things that dont work
Misspellings like www.cnn.comm and www.cnnn.com
These can take a long time to fail the first time
Good to remember that they dont work
so the failure takes less time the next time around

17

DNS Resource Records

DNS: distributed db storing resource records (RR)
RR format: (name,
Type=A
name is hostname
value is IP address

Type=NS

value, type, ttl)

Type=CNAME
name is alias name for some
canonical (the real) name
www.ibm.com is really
servereast.backup2.ibm.com

name is domain (e.g. foo.com)

value is canonical name
value is hostname of
authoritative name server for
Type=MX
this domain
value is name of mailserver
associated with name
18

DNS Protocol
DNS protocol : query and reply messages, both with
same message format
Message header
Identification: 16 bit # for
query, reply to query uses
same #
Flags:
Query or reply
Recursion desired
Recursion available
Reply is authoritative

19

Reliability
DNS servers are replicated
Name service available if at least one replica is up
Queries can be load balanced between replicas

UDP used for queries

Need reliability: must implement this on top of UDP

Try alternate servers on timeout

Exponential backoff when retrying same server

Same identifier for all queries

Dont care which server responds

20

Inserting Resource Records into DNS

Example: just created startup FooBar
Register foobar.com at Network Solutions
Provide registrar with names and IP addresses of your
authoritative name server (primary and secondary)
Registrar inserts two RRs into the com TLD server:
(foobar.com, dns1.foobar.com, NS)
(dns1.foobar.com, 212.212.212.1, A)

Put in authoritative server dns1.foobar.com

Type A record for www.foobar.com
Type MX record for foobar.com

21

Playing With Dig on UNIX

Dig program
Allows querying of DNS system
Use flags to find name server (NS)
Disable recursion so that operates one step at a time
unix> dig +norecurse @a.root-servers.net NS www.cs.princeton.edu

;; AUTHORITY SECTION:
edu.
2D IN NS
edu.
2D IN NS
edu.
2D IN NS
edu.
2D IN NS
edu.
2D IN NS
edu.
2D IN NS
edu.
2D IN NS
edu.
2D IN NS

L3.NSTLD.COM.
D3.NSTLD.COM.
A3.NSTLD.COM.
E3.NSTLD.COM.
C3.NSTLD.COM.
G3.NSTLD.COM.
M3.NSTLD.COM.
H3.NSTLD.COM.

22

Boot-Strapping an End Host

DHCP and ARP

23

How To Bootstrap an End Host?

What local Domain Name System server to use?
What IP address the host should use?
How to send packets to remote destinations?
How to ensure incoming packets arrive?

??? 1.2.3.7 1.2.3.156

host

host ...

DNS

host

host ...

DNS

5.6.7.0/24

1.2.3.0/24
1.2.3.19
router

router

router

24

Avoiding Manual Configuration

Dynamic Host Configuration Protocol (DHCP)
End host learns how to send packets
Learn IP address, DNS servers, and gateway

Address Resolution Protocol (ARP)

Others learn how to send packets to the end host
Learn mapping between IP address & interface address
??? 1.2.3.7 1.2.3.156
host

host ...

DNS

host

host ...

DNS

5.6.7.0/24

1.2.3.0/24
1.2.3.19
router

router

router

25

Key Ideas in Both Protocols

Broadcasting: when in doubt, shout!
Broadcast query to all hosts in the local-area-network
when you dont know how to identify the right one

Caching: remember the past for a while

Store the information you learn to reduce overhead
Remember your own address & other hosts addresses

Soft state: but 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
26

Need Yet Another Kind of Identity

LANs are designed for arbitrary network protocols
Not just for IP and the Internet

Using IP address would require reconfiguration

Every time the adapter was moved or powered up

Broadcasting all data to all adapters is expensive

Requires every host on the LAN to inspect each packet

Motivates separate Medium Access Control (MAC) addresses

27

MAC Address vs. IP Address

MAC addresses
Hard-coded in read-only memory when adaptor is built
Like a social security number
Flat name space of 48 bits (e.g., 00-0E-9B-6E-49-76)
Portable, and can stay the same as the host moves
Used to get packet between interfaces on same network

IP addresses
Configured, or learned dynamically
Like a postal mailing address
Hierarchical name space of 32 bits (e.g., 12.178.66.9)
Not portable, and depends on where the host is attached
Used to get a packet to destination IP subnet
28

MAC Addresses on a LAN

1A-2F-BB-76-09-AD

LAN
71-65-F7-2B-08-53

= adapter
58-23-D7-FA-20-B0

0C-C4-11-6F-E3-98

29

Bootstrapping Problem
Host doesnt have an IP address yet
So, host doesnt know what source address to use

Host doesnt know who to ask for an IP address

So, host doesnt know what destination address to use

Solution: shout to discover a server who can help

Broadcast a server-discovery message
Server sends a reply offering an address
host

host ...

host

DHCP server

30

Broadcasting
Broadcasting: sending to everyone
Special destination address: FF-FF-FF-FF-FF-FF
All adapters on the LAN receive the packet

Delivering a broadcast packet

Easy on a shared media
Like shouting in a room everyone can hear you

31

Response from the DHCP Server

DHCP offer message from the server
Configuration parameters (proposed IP address, mask,
gateway router, DNS server, ...)
Lease time (the time the information remains valid)

Multiple servers may respond

Multiple servers on the same broadcast media
Each may respond with an offer
The client can decide which offer to accept

Accepting one of the offers

Client sends a DHCP request echoing the parameters
The DHCP server responds with an ACK to confirm
and the other servers see they were not chosen

32

Dynamic Host Configuration Protocol

arriving
client

DHCP server
233.1.2.5

33

Deciding What IP Address to Offer

Server as centralized configuration database
All parameters are statically configured in the server
E.g., a dedicated IP address for each MAC address
Avoids complexity of configuring hosts directly
while still having a permanent IP address per host

Or, dynamic assignment of IP addresses

Server maintains a pool of available addresses
and assigns them to hosts on demand
Leads to less configuration complexity
and more efficient use of the pool of addresses
Though, it is harder to track the same host over time
34

Soft State: Refresh or Forget

Why is a lease time necessary?
Client can release the IP address (DHCP RELEASE)
E.g., ipconfig /release at the DOS prompt
E.g., clean shutdown of the computer

But, the host might not release the address

E.g., the host crashes (blue screen of death!)
E.g., buggy client software

And you dont want the address to be allocated forever

Performance trade-offs
Short lease time: returns inactive addresses quickly
Long lease time: avoids overhead of frequent renewals
35

So, Now the Host Knows Things

IP address
Mask
Gateway router
DNS server

And can send packets to other IP addresses

But, how to learn the MAC address of the destination?
36

Sending Packets Over a Link

1.2.3.53
host

1.2.3.156
host ...

Web

IP packet
1.2.3.53
1.2.3.156

router

Adaptors only understand MAC addresses

Translate the destination IP address to MAC address
Encapsulate the IP packet inside a link-level frame
37

Address Resolution Protocol Table

Every node maintains an ARP table
(IP address, MAC address) pair

Consult the table when sending a packet

Map destination IP address to destination MAC address
Encapsulate and transmit the data packet

But, what if the IP address is 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 the result in its ARP table

No need for network administrator to get involved

38

Example: A Sending a Packet to B

How does host A send an IP packet to B (www.cnn.com)?

www.cnn.com
A sends packet to R, and R sends packet to B.

39

Basic Steps
Host A must learn the IP address of B via DNS
Host A uses gateway R to reach external hosts
Host A sends the frame to Rs MAC address
Router R forwards IP packet to outgoing interface
Router R learns Bs MAC address and forwards frame

A
B
R

www.cnn.com 40

Host A Learns the IP Address of B

Host A does a DNS query to learn Bs address
Suppose gethostbyname() returns 222.222.222.222

Host A constructs an IP packet to send to B

Source 111.111.111.111, destination 222.222.222.222

41

Host A Learns the IP Address of B

IP header

Ethernet frame

From A: 111.111.111.111
To B: 222.222.222.222

From A: 74-29-9C-E8-FF-55
To gateway: ????

42

Host A Decides to Send Through R

Host A has a gateway router R
Used to reach destinations outside of 111.111.111.0/24
Address 111.111.111.110 for R learned via DHCP

But, what is the MAC address of the gateway?

43

Host A Sends Packet Through R

Host A learns the MAC address of Rs interface
ARP request: broadcast request for 111.111.111.110
ARP response: R responds with E6-E9-00-17-BB-4B

Host A encapsulates the packet and sends to R

44

Host A Sends Packet Through R

IP header

Ethernet frame

From A: 111.111.111.111
To B: 222.222.222.222

From A: 74-29-9C-E8-FF-55
To R: E6-E9-00-17-BB-4B

45

R Decides how to Forward Packet

Router Rs adaptor receives the packet
R extracts the IP packet from the Ethernet frame
R sees the IP packet is destined to 222.222.222.222

Router R consults its forwarding table

Packet matches 222.222.222.0/24 via other adaptor

46

Router R Wants to Forward Packet

IP header

Ethernet frame

From A: 111.111.111.111 From R: 1A-23-F9-CD-06-9B

To B: 222.222.222.222
To B: ???

47

R Sends Packet to B
Router Rs learns the MAC address of host B
ARP request: broadcast request for 222.222.222.222
ARP response: B responds with 49-BD-D2-C7-56-2A

Router R encapsulates the packet and sends to B

48

Router R Wants to Forward Packet

IP header

Ethernet frame

From A: 111.111.111.111 From R: 1A-23-F9-CD-06-9B

To B: 222.222.222.222
To B: 49-BD-D2-C7-56-2A

49

Conclusion
Domain Name System
Distributed, hierarchical database
Distributed collection of servers
Caching to improve performance

Bootstrapping an end host

Dynamic Host Configuration Protocol (DHCP)
Address Resolution Protocol (ARP)

50