>
 
  
 
15-441 
 Computer Networking 
 
Lecture 13 00DNS
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
2  
 
 
Outline 
   
 
   DNS Design
 
   
 
   DNS Today
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
3  
 
 
Naming 
 
 
   How do we efficiently locate 
   resources?
   
     DNS: name 00/font> IP address
     
   Challenge
   
     How do we scale these to 
     the wide area?
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
4  
 
 
Obvious Solutions (1) 
 
 
Why not centralize DNS?
 
   Single point of failure
   Traffic volume
   Distant centralized database
   Single point of update
 
  
 
   Doesn00 scale!
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
5  
 
 
Obvious Solutions (2) 
 
 
Why not use /etc/hosts?
 
   Original Name to Address Mapping
   
     Flat namespace
     /etc/hosts 
     SRI kept main copy
     Downloaded regularly
     
   Count of hosts was increasing: 
   machine per domain 00/font> machine per user
   
     Many more downloads
     Many more updates
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
6  
 
 
Domain Name System Goals 
 
 
   Basically a wide-area distributed 
   database
   Scalability
   Decentralized maintenance
   Robustness
   Global scope 
   
     Names mean the same thing 
     everywhere
     
   Don00 need
   
     Atomicity
     Strong consistency
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
7  
 
 
Programmer00 View of 
 DNS 
 
   Conceptually, programmers 
   can view the DNS database as a collection of millions of host entry 
   structures:
 
      
 
     in_addr is a struct consisting 
     of 4-byte IP address
     
   Functions for retrieving host 
   entries from DNS:
   
     gethostbyname: query key is a DNS host name.
     gethostbyaddr: query key is an IP address.
 
  
 
/* DNS host entry structure */ 
 
struct hostent { 
 
   
 char    *h_name;       
  /* official domain name of host */ 
 
   
 char    **h_aliases;   
  /* null-terminated array of domain names */ 
 
   
 int     h_addrtype;    
  /* host address type (AF_INET) */ 
 
   
 int     h_length;      
  /* length of an address, in bytes */ 
 
   
 char    **h_addr_list;  /* null-terminated array of in_addr 
 structs */ 
 
}; 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
8  
 
 
DNS Message Format 
 
 
Identification 
 
 
No. of Questions 
 
 
No. of Authority RRs 
 
 
Questions (variable number 
 of answers) 
 
Answers (variable number 
 of resource records) 
 
Authority (variable number 
 of resource records) 
 
Additional Info (variable 
 number of resource records) 
 
Flags 
 
 
No. of Answer RRs 
 
 
No. of Additional RRs 
 
 
Name, type fields 
 for a query 
 
RRs in response to 
 query 
 
Records for authoritative 
 servers 
 
Additional 00elpful 
 info that may be used 
 
12 bytes
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
9  
 
 
DNS Header Fields 
 
 
   Identification
   
     Used to match up request/response
     
   Flags
   
     1-bit to mark query or response
     1-bit to mark authoritative 
     or not
     1-bit to request recursive 
     resolution
     1-bit to indicate support 
     for recursive resolution
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
10  
 
 
DNS Records 
 
 
RR format: (class, name, value, type, ttl) 
 
 
   DB contains tuples called 
   resource records (RRs)
   
     Classes = Internet (IN), Chaosnet 
     (CH), etc.
     Each class defines value associated 
     with type
 
  
 
FOR IN class: 
 
 
   Type=A
   
     name is hostname
     value is IP address
     
   Type=NS
   
     name is domain (e.g. 
     foo.com)
     value is name of authoritative 
     name server for this domain
 
  
 
   Type=CNAME
   
     name is an alias name 
     for some 00anonical00(the real) name
     value is canonical 
     name
     
   Type=MX
   
     value is hostname of 
     mailserver associated with name
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
11  
 
 
Properties of DNS Host 
 Entries 
 
   Different kinds of mappings 
   are possible:
   
     Simple case: 1-1 mapping between 
     domain name and IP addr:
     
       kittyhawk.cmcl.cs.cmu.edu maps to 128.2.194.242
       
     Multiple domain names maps 
     to the same IP address:
     
       eecs.mit.edu and 
       cs.mit.edu both map to 18.62.1.6
       
     Single domain name maps to 
     multiple IP addresses:
     
       aol.com and 
       www.aol.com map to multiple IP addrs.
       
     Some valid domain names don00 
     map to any IP address:
     
       for example: cmcl.cs.cmu.edu
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
12  
 
 
DNS Design: Hierarchy 
 Definitions 
 
root 
 
 
edu 
 
 
net 
 
 
org 
 
 
uk 
 
 
com 
 
 
gwu 
 
 
ucb 
 
 
cmu 
 
 
bu 
 
 
mit 
 
 
cs 
 
 
ece 
 
 
cmcl 
 
 
   Each node in hierarchy stores 
   a list of names that end with same suffix
   
     Suffix = path up tree
     
   E.g., given this tree, where 
   would following be stored:
   
     Fred.com
     Fred.edu
     Fred.cmu.edu
     Fred.cmcl.cs.cmu.edu
     Fred.cs.mit.edu
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
13  
 
 
DNS Design: Zone Definitions 
 
 
root 
 
 
edu 
 
 
net 
 
 
org 
 
 
uk 
 
 
com 
 
 
ca 
 
 
gwu 
 
 
ucb 
 
 
cmu 
 
 
bu 
 
 
mit 
 
 
cs 
 
 
ece 
 
 
cmcl 
 
 
Single node 
 
 
Subtree 
 
 
Complete Tree 
 
 
   Zone = contiguous section 
   of name space
   
     E.g., Complete tree, single 
     node or subtree
     
   A zone has an associated set 
   of name servers
   
     Must store list of names and 
     tree links
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
14  
 
 
DNS Design: Cont. 
 
 
   Zones are created by convincing 
   owner node to create/delegate a subzone
   
     Records within zone stored 
     multiple redundant name servers
     Primary/master name server 
     updated manually
     Secondary/redundant servers 
     updated by zone transfer of name space
     
       Zone transfer is a bulk 
       transfer of the 00onfiguration00of a DNS server 00uses TCP to 
       ensure reliability
       
   Example:
   
     CS.CMU.EDU created by CMU.EDU 
     administrators
     Who creates CMU.EDU or .EDU?
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
15  
 
 
DNS: Root Name Servers 
 
 
   Responsible for 00oot00
   zone
   Approx. 13 root name servers 
   worldwide
   
     Currently {a-m}.root-servers.net
     
   Local name servers contact 
   root servers when they cannot resolve a name
   
     Configured with well-known 
     root servers
     Newer picture 00/font> 
     Local servers
     
       Do lookup of distant host 
       names for local hosts
       Typically answer queries about 
       local zone
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
17  
 
 
Typical Resolution 
 
 
Client 
 
 
Local 
 
DNS server 
 
 
root & edu 
 
DNS server 
 
 
ns1.cmu.edu 
 
DNS server 
 
 
www.cs.cmu.edu 
 
 
NS ns1.cmu.edu 
 
 
www.cs.cmu.edu 
 
 
NS ns1.cs.cmu.edu 
 
 
A www=IPaddr 
 
 
ns1.cs.cmu.edu
 
DNS
 
server
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
18  
 
 
Typical Resolution 
 
 
   Steps for resolving www.cmu.edu
   
     Application calls gethostbyname() 
     (RESOLVER)
     Resolver contacts local name 
     server (S1)
     S1 queries root 
     server (S2) for (
 
  
 
Workload impact on choice?
 
   Local server typically does 
   recursive
   Root/distant server does iterative
 
  
 
requesting host
 
surf.eurecom.fr 
 
 
gaia.cs.umass.edu 
 
 
root name server 
 
 
local name server
 
dns.eurecom.fr 
 
 
1 
 
 
2 
 
 
3 
 
 
4 
 
 
5 
 
 
6 
 
 
authoritative name server
 
dns.cs.umass.edu 
 
 
intermediate name server
 
dns.umass.edu 
 
 
7 
 
 
8 
 
 
iterated 
 query
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
20  
 
 
Workload and Caching 
 
 
   Are all servers/names likely 
   to be equally popular?
   
     Why might this be a problem? 
     How can we solve this problem?
     
   DNS responses are cached 
   
     Quick response for repeated 
     translations
     Other queries may reuse some 
     parts of lookup
     
       NS records for domains 
       
   DNS negative queries are cached
   
     Don00 have to repeat past 
     mistakes
     E.g. misspellings, search 
     strings in resolv.conf
     
   Cached data periodically times 
   out
   
     Lifetime (TTL) of data controlled 
     by owner of data
     TTL passed with every record
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
21  
 
 
Typical Resolution 
 
 
Client 
 
 
Local 
 
DNS server 
 
 
root & edu 
 
DNS server 
 
 
ns1.cmu.edu 
 
DNS server 
 
 
www.cs.cmu.edu 
 
 
NS ns1.cmu.edu 
 
 
www.cs.cmu.edu 
 
 
NS ns1.cs.cmu.edu 
 
 
A www=IPaddr 
 
 
ns1.cs.cmu.edu
 
DNS
 
server
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
22  
 
 
Subsequent Lookup Example 
 
 
Client 
 
 
Local 
 
DNS server 
 
 
root & edu 
 
DNS server 
 
 
cmu.edu 
 
DNS server 
 
 
cs.cmu.edu
 
DNS
 
server 
 
 
ftp.cs.cmu.edu 
 
 
ftp=IPaddr 
 
 
ftp.cs.cmu.edu
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
23  
 
 
Reliability 
 
 
   DNS servers are replicated
   
     Name service available if 
     00one replica is up
     Queries can be load balanced 
     between replicas
     
   UDP used for queries
   
     Need reliability 00/font> must 
     implement this on top of UDP!
     Why not just use TCP?
     
   Try alternate servers on timeout
   
     Exponential backoff when retrying 
     same server
     
   Same identifier for all queries
   
     Don00 care which server 
     responds
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
24  
 
 
Reverse DNS 
 
 
   Task
   
     Given IP address, find its 
     name
     
   Method
   
     Maintain separate hierarchy 
     based on IP names
     Write 128.2.194.242 as 242.194.128.2.in-addr.arpa
     
       Why is the address reversed?
       
   Managing
   
     Authority manages IP addresses 
     assigned to it
     E.g., CMU manages name space 
     128.2.in-addr.arpa
 
   
 
edu 
 
 
cmu 
 
 
cs 
 
 
kittyhawk
 
128.2.194.242 
 
 
cmcl 
 
 
unnamed root 
 
 
arpa 
 
 
in-addr 
 
 
128 
 
2 
 
194 
 
242
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
25  
 
 
.arpa Name Server Hierarchy 
 
 
   At each level of hierarchy, 
   have group of servers that are authorized to handle that region of hierarchy
 
  
 
128 
 
 
2 
 
 
194 
 
 
kittyhawk
 
128.2.194.242 
 
 
in-addr.arpa 
 
 
a.root-servers.net 
 000000nbsp; m.root-servers.net 
 
chia.arin.net
 
(dill, henna, 
 indigo, epazote, figwort, ginseng) 
 
cucumber.srv.cs.cmu.edu,
 
t-ns1.net.cmu.edu
 
t-ns2.net.cmu.edu 
 
 
mango.srv.cs.cmu.edu
 
(peach, banana, 
 blueberry)
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
26  
 
 
Prefetching 
 
 
   Name servers can add additional 
   data to response
   Typically used for prefetching
   
     CNAME/MX/NS typically point 
     to another host name
     Responses include address 
     of host referred to in 00dditional section00/font>
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
27  
 
 
Mail Addresses 
 
 
   MX records point to mail exchanger 
   for a name
   
     E.g. mail.acm.org is MX for 
     acm.org
     
   Addition of MX record type 
   proved to be a challenge
   
     How to get mail programs to 
     lookup MX record for mail delivery?
     Needed critical mass of such 
     mailers
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
28  
 
 
Outline 
   
 
   DNS Design
 
   
 
   DNS Today
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
29  
 
 
Root Zone 
 
 
   Generic Top Level Domains 
   (gTLD) = .com, .net, .org, etc00/font>
   Country Code Top Level Domain 
   (ccTLD) = .us, .ca, .fi, .uk, etc00/font>
   Root server ({a-m}.root-servers.net) 
   also used to cover gTLD domains
   
     Load on root servers was 
     growing quickly!
     Moving .com, .net,  .org 
     off root servers was clearly necessary to reduce load 00/font> done Aug 2000
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
30  
 
 
gTLDs 
 
 
   Unsponsored
   
     .com, .edu, .gov, .mil, .net, 
     .org
     .biz 00/font> businesses
     .info 00/font> general info
     .name 00/font> individuals
     
   Sponsored (controlled by a 
   particular association)
   
     .aero 00/font> air-transport industry
     .cat 00/font> catalan related
     .coop 00/font> business cooperatives
     .jobs 00
     job announcements
     .museum 00museums
     .pro 00/font> accountants, lawyers, and physicians
     .travel 00/font> travel industry
     
   Starting up
   
     .mobi 00
     mobile phone targeted domains
     .post 00postal 
     .tel 00telephone related
     
   Proposed
   
     .asia, .cym, .geo, .kid, .mail, 
     .sco, .web, .xxx
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
31  
 
 
New Registrars 
 
 
   Network Solutions (NSI) used 
   to handle all registrations, root servers, etc00/font>
   
     Clearly not the democratic 
     (Internet) way
     Large number of registrars 
     that can create new domains 00/font> However NSI still handles A root server
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
32  
 
 
Measurements of DNS 
 
 
   No centralized caching per 
   site
   
     Each machine runs own caching 
     local server
     Why is this a problem?
     How many hosts do we need 
     to share cache? 00/font> recent studies suggest 10-20 hosts
     
   00it rate for DNS = 80% 00/font> 1 
   - (#DNS/#connections)
   
     Is this good or bad?
     Most Internet traffic was 
     Web with HTTP 1.0
     
       What does a typical page 
       look like? 00/font> 
       average of 4-5 imbedded objects 00
       needs 4-5 transfers
       This alone accounts for 80% 
       hit rate!
       
   Lower TTLs for A records does 
   not affect performance
   DNS performance really relies 
   more on NS-record caching
 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
33  
 
 
Tracing Hierarchy (1) 
 
 
   Dig Program
   
     Allows querying of DNS 
     system
     Use flags to find name server 
     (NS)
     Disable recursion so that 
     operates one step at a time
 
       
    
 
     All .edu names handled by 
     set of servers
 
  
 
unix> dig 
 +norecurse @a.root-servers.net NS kittyhawk.cmcl.cs.cmu.edu 
 
 
;; AUTHORITY SECTION:
 
edu.                    
 172800  IN      NS      
 L3.NSTLD.COM.
 
edu.                    
 172800  IN      NS      
 D3.NSTLD.COM.
 
edu.                    
 172800  IN      NS      
 A3.NSTLD.COM.
 
edu.                    
 172800  IN      NS      
 E3.NSTLD.COM.
 
edu.                    
 172800  IN      NS      
 C3.NSTLD.COM.
 
edu.                    
 172800  IN      NS      
 F3.NSTLD.COM.
 
edu.                    
 172800  IN      NS      
 G3.NSTLD.COM.
 
edu.                    
 172800  IN      NS      
 B3.NSTLD.COM.
 
edu.                    
 172800  IN      NS      
 M3.NSTLD.COM.
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
34  
 
 
Tracing Hierarchy (2) 
 
 
   3 servers handle CMU names
 
  
 
unix> dig 
 +norecurse @e3.nstld.com NS kittyhawk.cmcl.cs.cmu.edu 
 
 
;; AUTHORITY SECTION:
 
cmu.edu.                
 172800  IN      NS      
 CUCUMBER.SRV.cs.cmu.edu.
 
cmu.edu.                
 172800  IN      NS      
 T-NS1.NET.cmu.edu.
 
cmu.edu.                
 172800  IN      NS      
 T-NS2.NET.cmu.edu.
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
35  
 
 
Tracing Hierarchy (3 
 & 4) 
 
   4 servers handle CMU CS names
 
      
 
   Quasar is master NS for this 
   zone
 
  
 
unix> 
 dig +norecurse @t-ns1.net.cmu.edu NS kittyhawk.cmcl.cs.cmu.edu 
 
 
;; AUTHORITY SECTION:
 
cs.cmu.edu.             
 86400   IN      NS      
 MANGO.SRV.cs.cmu.edu.
 
cs.cmu.edu.             
 86400   IN      NS      
 PEACH.SRV.cs.cmu.edu.
 
cs.cmu.edu.             
 86400   IN      NS      
 BANANA.SRV.cs.cmu.edu.
 
cs.cmu.edu.             
 86400   IN      NS      
 BLUEBERRY.SRV.cs.cmu.edu. 
 
unix>dig 
 +norecurse @blueberry.srv.cs.cmu.edu NS 
   kittyhawk.cmcl.cs.cmu.edu 
 
;; AUTHORITY SECTION:
 
cs.cmu.edu.             
 300     IN      SOA     
 QUASAR.FAC.cs.cmu.edu. 
 
 
 
  
 
Lecture 
 13: 10-10-2006 
 
36  
 
 
DNS (Summary) 
 
 
   Motivations 00/font> large distributed database
   
     Scalability
     Independent update
     Robustness
     
   Hierarchical database structure
   
     Zones
     How is a lookup done
     
   Caching/prefetching and TTLs
   Reverse name lookup
   What are the steps to creating 
   your own domain?