Name Services

Names, Identifiers and Addresses exam

The problem. Before two programs can share anything, they must agree on how to refer to it. A distributed system names many kinds of thing: computers, services, remote objects, files and users. Very little works without names. You need a URL to fetch one particular web page; processes cannot share a resource unless they can name it consistently; and people cannot communicate unless they can name each other, for example with an email address.

There are two very different styles of reference. Compare google.com with 74.125.237.83, or /usr/bin/tar with Disk 4, Sector 26, Block 15. Meaningful names are easier for humans to remember and type. Numbers suit programs better, because programs use them to structure data and to locate resources quickly. Both styles can carry structure, as the lower half of the figure shows.

Three kinds of reference exam

CDK (§13.1.1) separates three terms, which run from what a person types to where the object actually sits. Learn these definitions word for word; they are the vocabulary for everything else in this Part.

Pure and non-pure names exam

Names also differ in how much they reveal about the object. A pure name is an uninterpreted bit pattern: it contains no information about the object at all, so it must always be looked up before it can be used. A non-pure name contains information about the object, typically its location, as in tawfiq@128.250.1.25, where the part after the @ is an IP address.

Attributes, bindings and resolution

The rest of the vocabulary describes what a name refers to and how you get there. An attribute is the value of a property of an object; in a distributed system the key attribute is the object's address. A binding is the association between a name and an object, or more precisely between a name and the object's attributes. Resolution is translating a name into data about the named object, usually so that you can act on it, for example to open a connection.

Names are preferable to identifiers or addresses for two reasons. First, the binding to a physical location can change without the name changing: a web site can move to another server and keep its domain name, because only the binding is updated. Second, names mean something to users. The figure shows the first reason.

Service-specific names and contexts

Traditionally each service has its own naming scheme, and each scheme identifies its resource only within some enclosing context, such as one file system or one computer. A process id of 1234 means nothing until you know which computer it is on.

Hierarchy is what lets one simple name recur in different contexts without clashing. The name james can exist in two different domains at once, because each domain is its own context.

Composed naming domains: one URL, several name services

In practice one URL is resolved by several name services working in a chain. Step through the example below. Notice that the output of one stage, an address, is itself a name for the next stage: the IP address is resolved again to an Ethernet address by ARP (the Address Resolution Protocol, which finds the hardware address of a machine on the local network).

Check yourselfDistinguish a name, an identifier and an address. What is a pure name?

A name is human-readable and is resolved to attributes (an identifier or address). An identifier is meant for programs and is chosen to be efficient to store and look up, such as a file handle or a remote object reference. An address gives the object's location, which makes access efficient, but it becomes invalid if the object moves.

A pure name is an uninterpreted bit pattern, so it must always be looked up. A non-pure name, by contrast, contains information about the object, such as its location.

Check yourselfWhich of these is a pure name?

1. tawfiq@128.250.1.25
2. http://www.cdk5.net:8888/WebExamples/earth.html
3. An IP address and port pair, 138.37.88.61:8888
4. A random 64-bit identifier that a lookup table maps to a server

D. It carries no information about the object, so it can only be used by looking it up. A contains an IP address (location), so it is non-pure. B contains the host and port, so it is non-pure too. C is not a name for people at all but an address: it is the location.

Check yourselfA company moves its web site to a new data centre with new IP addresses. Why do users who type the domain name notice nothing, while a script with a hard-coded IP address fails?

The domain name is bound to the address by the name service, and the binding is resolved only when needed. Moving the site only changes the binding, so every later resolution of the name returns the new address. The hard-coded IP is an address: it identifies the old location, not the site, so it breaks when the object moves.

Check yourselfName the separate resolution steps involved in fetching http://www.cdk5.net:8888/WebExamples/earth.html.

(1) DNS resolves www.cdk5.net to IP 138.37.88.61. (2) At the last hop, ARP resolves that IP address to an Ethernet address. (3) A socket is opened to port 8888, reaching the web server. (4) The web server's file system resolves the path WebExamples/earth.html to the file. The lesson is that an address can itself be a name needing further lookup.

URIs, URLs and URNs exam

The problem. The Web needs to identify all sorts of resources: pages, mailboxes, phone numbers, books. If every kind had its own unrelated syntax, every browser and library would need special code for each one. URIs (Uniform Resource Identifiers) solve this with one general, uniform syntax for identifying any kind of resource.

A URI starts with a scheme, such as http:, mailto:, tel: or urn:, and the scheme says how to read the rest. Because the overall syntax is shared, new identifier types can be added, and old ones reused, without disrupting common software such as browsers. There are two kinds of URI, and the difference between them is the one fact to remember: a URL says where the resource is and how to reach it, while a URN only names it.

Dangling links

The weakness of URLs has a name. If a resource is deleted or moved, old links to it dangle: following one gives "not found" or, worse, a different resource that now happens to sit at that location. Nothing warns the reader that the link is wrong.

The debate about what to do continues. One side says "cool URLs don't change": owners should guarantee continuity at the same URL. The other side argues for separate URNs, because not everyone can guarantee a stable domain for ever.

Check yourselfCompare URLs and URNs. What is a dangling link?

A URL holds the resource's location plus the access method, as in http://www.cdk5.net/. That makes it efficient, but it changes when the resource moves. A URN is a pure name, such as urn:ISBN:0-201-62433-8, so it stays stable, but it needs a resolution service.

A dangling link is a URL that points to a moved or deleted resource, so following it gives "not found" or a different resource.

Check yourselfWhich statement is correct?

1. www.cdk5.net is a URL.
2. Every URN is a URL whose host is a resolution service.
3. mailto:fred@flintstone.org is a URL, because it states the access method and the location.
4. A URN stays valid when the resource moves because DNS updates it automatically.

C. The guide lists mailto: addresses as URL examples. A is a bare domain name with no scheme. B is wrong because a URN is a pure name with no host at all. D gets the reason wrong: a URN stays valid because it contains no location in the first place, and it is resolved by a separate resolution service such as the Handle System, not by DNS.

Name Services exam

The problem. Once resources have names, something has to remember which name is bound to which attributes, and answer questions about them. That is the job of a name service.

Why a separate name service?

The slides list three key benefits. Resource localisation: programs can find files, web pages, services and databases. Uniform naming: everything is named the same way. Device-independent addresses: when a site moves to another server, only the binding changes. That last benefit comes from the fact that name services defer binding: a name is resolved to an address only when it is needed, not when the program is written, so the address can change in between.

Naming is kept separate from other services for reasons of openness (a system's ability to be extended and to interwork, Part I). Separation allows unification: resources managed by different services can share one naming scheme, as URIs do. It also allows integration: resources created in different administrative domains may later need to be shared, and a common name service avoids clashing naming conventions.

The five general requirements exam

These were the design goals of two early large name services, Grapevine and GNS (§9.8). They are a favourite "list and explain" question, so learn each with its reason.

1. Scale. The service must handle an essentially arbitrary number of names and serve an arbitrary number of administrative organisations. (The Internet has billions of names.)
2. Long lifetime. Over the service's life, both the organisation of the name space and the components that implement it will change many times. The design must survive those changes.
3. High availability. Most other systems depend on the name service, so they fail if it fails. If DNS is down, you cannot reach web sites by name.
4. Fault isolation. Local failures must not bring down the whole service. A crashed server in one university should affect only that university's names.
5. Tolerance of mistrust. In a large open system no component is trusted by all clients, so the service must work even though parts of it are run by people who do not trust each other.

Check yourselfList the general requirements of a name service.

1. Scale: handle arbitrary numbers of names and organisations.
2. Long lifetime: survive many changes to the name space organisation and to the implementation.
3. High availability: other systems depend on it, so it must stay up.
4. Fault isolation: local failures must not bring down the whole service.
5. Tolerance of mistrust: cope with the fact that no component is trusted by all clients.

Check yourselfA name server at one university crashes, but names elsewhere on the Internet still resolve. Which requirement does this illustrate?

1. High availability
2. Fault isolation
3. Long lifetime
4. Tolerance of mistrust

B, fault isolation: a local failure stayed local. High availability (A) is the near miss: it is about the service as a whole staying up because everything depends on it, which is usually achieved by replication, not about confining a failure to one part.

Check yourselfWhat does it mean that a name service "defers binding", and which benefit does it give?

Names are resolved to addresses only when they are needed, at run time, rather than being fixed in advance. So if a resource moves, only the binding in the name service changes and every later lookup returns the new address. That is the benefit of device-independent addresses: a site can move to another server seamlessly.

Name Spaces

The problem. A name service must decide which strings even count as names, how they are organised, and who is allowed to hand them out. Those decisions define its name space, and they determine whether the service can grow to Internet size.

Flat and hierarchical name spaces

Name spaces come in two shapes. The contrast to notice is that a flat space is finite and run by one authority, while a hierarchical one can grow indefinitely because its parts (contexts) can be managed separately by different organisations.

To see how a hierarchical name is resolved part by part, take /etc/passwd. First etc is looked up in the context /, which yields a new context; then passwd is looked up in the context /etc. Because each context is separate, the same simple name can mean different things in different contexts.

DNS names

A DNS name is a sequence of labels separated by dots, with the highest-level domain on the right. Names are case-insensitive, so WWW.CDK5.NET and www.cdk5.net are the same name. DNS servers accept only absolute names (complete names, right up to the top-level domain), but client software appends default domains to single-component names: if your machine is in cdk5.net, typing www becomes www.cdk5.net before it is sent.

Aliases

An alias is a name defined to denote the same information as another name, much like a symbolic link in a file system. URL shorteners (bit.ly/...) are aliases, and so are DNS CNAME records, such as one that makes www.cdk5.net stand for cdk5.net. Aliases give convenient names, and if the machine behind a name changes, only one record needs updating. Their risk is cycles, which make resolution loop forever.

Naming domains and delegation

A naming domain is a name space with a single overall administrative authority for assigning names in it. The authority may delegate subdomains to others. For example, cis.unimelb.edu.au is agreed with the authority for unimelb.edu.au, which in turn registered with edu.au. The authority normally also manages the corresponding data on an authoritative name server, the server whose answers for that domain are the official ones.

Combining and customising name spaces

DNS is one global, homogeneous name space: a name means the same thing everywhere. Other services let name spaces be combined or tailored, in three ways.

Merging. Mounting, as in UNIX and NFS, embeds one name space inside another. Suppose you want to merge the file name spaces of two machines, red and blue. You can create a new super-root containing /red and /blue. But then old absolute names such as /etc/passwd break, because they no longer say which machine, so the old roots are kept as well, giving a hybrid name space. The moral: you can always merge under a new root, but you create backward-compatibility problems.

Heterogeneity. DCE (the Distributed Computing Environment, an older middleware platform) names contain junctions, which are like mount points but lead into name spaces with a different syntax, as in /.../dcs.qmul.ac.uk/principals/Jean.Dollimore: the part after the junction follows the rules of a different naming system.

Customisation. Each client can mount remote file systems wherever it likes, so the same file may have different names on different computers. Spring and Plan 9 go further and give each process its own naming context.

Check yourselfWhy can a hierarchical name space grow indefinitely when a flat one cannot?

A flat space is a single set of identifiers whose size is limited by the maximum name length, and one authority manages one large table. A hierarchical space resolves each part of a name in a separate, smaller context, and different contexts can be managed by different organisations; a new level can always be added under any node. So the space is potentially infinite and its management is spread out.

Check yourselfwww.cdk99.net returns "no such name" from DNS. Is it outside the DNS name space?

No. It is syntactically valid, so it is in the name space; it is simply unbound. A name outside the name space would be one with invalid syntax, such as ....

Check yourselfWhat is the risk of aliases, and what are the two fixes?

Aliases can form cycles (a → b → a), which make resolution loop forever. The fixes are to abandon resolution after a threshold number of steps, or to have administrators veto (refuse to create) cyclic aliases.

Check yourselfYou merge two machines' file name spaces under a new super-root. What breaks, and how is it usually patched?

Old absolute names such as /etc/passwd break, because they no longer identify which machine's file is meant (it is now /red/etc/passwd or /blue/etc/passwd). The usual patch is to keep the old roots as well, giving a hybrid name space. The general lesson is that merging under a new root always works but creates backward-compatibility problems.

Name Resolution and Navigation exam

The problem. No single server can hold every name on the Internet. So when a client presents a name, the first server it asks often cannot answer alone, and someone has to find the server that can. This section is about how that search, called navigation, is organised. It is one of the most examined topics in the Part.

Resolution is a loop

Resolution is an iterative or recursive process. A name is presented to a naming context, which returns either the attributes or another context plus a derived name. The derived name is then presented to that context, and this repeats until the attributes come back. Aliases add extra rounds: for example, www.dcs.qmul.ac.uk resolves first to traffic.dcs.qmul.ac.uk, and only then to an IP address.

Why more than one server: partitioning and replication

A large name service's data is partitioned across many name servers, usually by domain, so that each organisation runs the servers for its own names. It is also replicated for availability: DNS, for instance, keeps each zone (a server's unit of data, §9.6) on at least two failure-independent servers. A local server therefore cannot answer every query alone.

The four navigation methods

There are four ways to navigate, and they differ in who drives the lookup: the client, a multicast group, or the servers themselves. The four steppers below use exactly the same cast and layout, so you can flip between them and see only the differences. Watch who sends each message, and whose activation bar stays open.

Recursive navigation is required across administrative domains that forbid outside clients, or even outside name servers, from discovering how their naming data is spread. Authorised servers then request data from designated servers, which return the attributes without revealing where the data is stored.

Iterative navigation in DNS and in NFS

DNS and NFS (the Network File System, Part VIII) both navigate iteratively, but they present the name differently. In DNS, the client presents the entire name each time, starting at a local server; if that server can't resolve it, it suggests a server for a domain that includes the name. In NFS, the client splits the pathname into simple names and presents them one at a time, each with the handle of the directory that contains it. NFS must work this way, because only the client knows its own mount points and symbolic links. The lecturer's example is a path through /server1/mnt/ that points to /server2/mnt/file, a file on a different server.

Comparing the four methods

Each method moves the work between client and servers. Notice that recursive navigation's big cost is the thread it holds in every server on the chain.

Caching exam

Resolvers and servers both cache (keep a local copy of) the results of previous resolutions. Caching greatly improves response time, because it saves server round trips. It also improves availability, because it removes high-level servers such as the root from the path, so resolution can proceed even if some of them have failed. And it works well here because naming data changes rarely: addresses typically stay the same for months.

The cost is that cached attributes can be out of date: if the binding changes, a cache may go on returning the old value. DNS limits this staleness with a per-record time-to-live (TTL): a lifetime in seconds after which a cached copy must be thrown away. §9.6 traces a cache with real TTL values.

Check yourselfExplain the four navigation methods (the exam would want a diagram of each).

1. In iterative navigation, the client asks NS1, gets a referral to NS2, asks NS2, and so on until a server returns the attributes. DNS and NFS work this way.
2. In multicast navigation, the client multicasts the name (and object type) to a group of servers and only the holder replies, so an unbound name gives silence.
3. In non-recursive server-controlled navigation, the client asks NS1, which navigates (iteratively or by multicast) on the client's behalf and returns the result.
4. In recursive server-controlled navigation, each server forwards the request to the next, and the results return along the chain.

The diagrams are the four steppers above, or the at-a-glance figure.

Check yourselfWhen must recursive navigation be used, and what is its cost?

It must be used across administrative domains that forbid clients or outside servers from learning where their naming data lives. The designated server then returns the attributes without revealing where they are placed.

Its cost is that a thread is held in every server on the chain until the answer returns, which delays other requests.

Check yourselfA client gets no reply to a name query, and cannot tell whether the name is unbound or a message was lost. Which navigation method was it using?

1. Iterative
2. Multicast
3. Non-recursive server-controlled
4. Recursive server-controlled

B, multicast. Only the server holding a name replies, so an unbound name produces silence, which looks the same as a lost message. In the other three methods some server always answers, even if only to say "unknown" or "try elsewhere".

Check yourselfGive two reasons why caching helps a name service, and the price paid for it.

It improves response time (fewer server round trips) and it improves availability (high-level servers such as the root are taken off the path, so lookups succeed even if they fail). It suits naming because naming data changes rarely. The price is staleness: a cached binding may be out of date, which DNS bounds with a per-record TTL.

The Domain Name System (DNS) exam

The problem. Every computer on the Internet needs to turn host names into IP addresses, billions of times a day, and the names are owned by millions of different organisations. DNS (designed by Mockapetris; specified in RFC 1034 and RFC 1035) is the distributed naming database that does this. It is the case study for everything in the previous sections.

Why DNS replaced a single hosts file

Before DNS, all host names and addresses were kept in one central master file, and every computer that needed it downloaded a copy by FTP (the File Transfer Protocol). That approach had three problems: it did not scale to large numbers of computers; it did not allow local administration, though organisations wanted to manage their own names; and it was not a general name service, only a way to look up computer addresses.

The structure of DNS names reflects the administrative structure of the Internet. DNS mainly names computers, along with mail hosts and name servers. It is fast (a typical query takes about 100 ms) because of heavy caching; it scales by partitioning the database; and it is resilient through replication. In Java, InetAddress.getByName() invokes DNS, as the code at the end of this section shows.

Domain names

The domain name space is partitioned both organisationally and geographically. The original generic top-level domains are com (commercial), edu (universities), gov (US government), mil (US military), net (network support centres), org (other organisations) and int (international organisations). Alongside them are the country domains, such as .au, .uk and .cn, which often have their own subdomains, for example edu.au, com.au and ac.uk.

The geographic-sounding names are conventional only: a .co.uk name may refer to a computer in Spain. A domain's name is the common suffix of the names in it, but only some domain names denote domains; others denote computers. cis.unimelb.edu.au is a domain, while dsys.cis.unimelb.edu.au is a computer.

What you can ask DNS exam

DNS answers five kinds of query. A query names a domain name, a class (IN for Internet) and a type (A, MX, NS and so on, see the record table below), and one message can carry several queries.

Name servers, zones and authoritative data exam

The DNS database is spread across a logical network of servers. Each server holds part of it, mainly the data for its local domain, so local queries are answered locally. So that names outside its domain can be resolved, each server also records the names and addresses of other name servers: at least the root servers, and usually its parent domain's server.

Authoritative and cached data

Authoritative data comes from the zone's own servers and is reasonably up to date. It is held by two kinds of server. The primary (master) server reads the zone data from a local master file that administrators edit. Secondary servers download the whole zone from the primary (a zone transfer) and then periodically check whether their copy still matches, typically once or twice a day, as set in the SOA record. A secondary whose copy is out of date is sent the latest version. Each zone must be replicated on at least two servers so that it survives a server failure.

Cached (non-authoritative) data. Any server may cache data it obtained from other servers, but it must tell clients that the data is non-authoritative. Each record has a TTL, and a caching server serves the record only until the TTL expires; after that it must go back to an authoritative server. Administrators set long TTLs for stable data and shorten the TTL before a planned change, which balances traffic against flexibility.

BIND (Berkeley Internet Name Domain), the standard UNIX implementation, consists of a resolver library plus the named daemon (a background server process). A server is configured as primary, secondary or caching-only, where a caching-only server stores only what it learns while resolving. A typical organisation runs one primary, several secondaries, and caching-only servers on hosts.

Resource records exam

DNS stores its data as resource records of different types. Several of them match the queries above: A and AAAA serve host name resolution, MX serves mail host location, PTR serves reverse lookups, and HINFO holds host information.

The zone data below is the CDK example for dcs.qmul.ac.uk (Queen Mary, University of London). A zone starts with its SOA record (omitted here), followed by NS and then MX records, and most of the remaining records are A records. Each line reads: name, TTL, class, type, value.

dcs.qmul.ac.uk   1D  IN  NS     dns0
dcs.qmul.ac.uk   1D  IN  MX     1 mail1.qmul.ac.uk
dcs.qmul.ac.uk   1D  IN  MX     2 mail2.qmul.ac.uk
www              1D  IN  CNAME  traffic
traffic          1D  IN  A      138.37.95.150

• 1D is a TTL of one day: a cache may keep any of these records for up to a day.
• The NS line names dns0 (short for dns0.dcs.qmul.ac.uk) as an authoritative name server for the zone.
• In the MX records a lower preference number is tried first, so mail goes to mail1 and falls back to mail2.
• www is an alias (CNAME) for traffic, whose A record gives the IPv4 address 138.37.95.150. This is the alias step you saw in §9.5.

Because dcs is a delegated subdomain, the parent zone qmul.ac.uk holds dcs NS dns0.dcs plus a glue A record for dns0.dcs.

Check yourselfWhat is a DNS zone, and how is zone data kept available and up to date?

A zone holds the domain's data minus any delegated subdomains, at least two authoritative name servers, the NS and glue records for its subdomains, and the management parameters in the SOA record.

Zone data is kept available and current by replication. The primary server reads it from a master file, and the secondaries obtain it by zone transfer and check once or twice a day that their copy is current. Every zone is held on at least two servers. Other servers may cache the data with a TTL, but they must mark it as non-authoritative.

Check yourselfWhich record type would you query to find where to deliver mail for cis.unimelb.edu.au, and which for turning 128.250.1.22 back into a name?

1. A and CNAME
2. MX and PTR
3. NS and SOA
4. MX and HINFO

B. MX gives the list of ⟨preference, mail host⟩ pairs. Reverse resolution uses PTR records in the special in-addr.arpa domain. HINFO (D) is host information, the record you should not publish.

Check yourselfA server answers a query from its cache, two minutes after fetching the record. Is the answer authoritative?

No. Only the zone's own primary and secondary servers give authoritative answers. Cached data is non-authoritative however recent it is, and the server must say so. It may serve the record only until the record's TTL expires.

Navigation and query processing

A DNS client is a resolver, which is library code linked into the program. It formats queries and sends them using a simple request-reply protocol over UDP (the connectionless datagram protocol, Part III) to a well-known port. Because UDP may lose messages, the resolver times out and resends when no reply arrives. It can be configured with a list of initial servers in order of preference.

Iterative navigation is the standard in DNS. Recursive navigation is optional: the resolver asks for it, and servers may decline, because it ties up threads. Recursive navigation must be used in domains that restrict client access to their DNS data for security reasons.

In practice, according to the lecturer's notes, a lookup happens in three stages:

1. The resolver looks in its local cache.
2. It asks its local or ISP DNS server, which navigates on its behalf.
3. That server consults root and authoritative servers as needed. Each server returns either a referral to another server or the answer.

Root servers hold entries for several levels of the tree to cut the number of navigation steps, so a name like www.berkeley.edu takes at worst two steps even with an empty cache.

Walk-through: resolving dsys.cis.unimelb.edu.au exam

This is the slide example, and any host such as a.cis.unimelb.edu.au resolves the same way. It brings together referrals down the tree, delegation with glue records, and caching. Step through it slowly: this is the picture to reproduce if asked to "explain how a name is resolved in DNS".

Check yourselfWalk through resolving a.cis.unimelb.edu.au with an empty cache.

The resolver asks the local server, which starts at a root server. The root refers it to the au name servers, ns1.nic.au refers it to edu.au, and the edu.au server refers it to unimelb.edu.au. The unimelb.edu.au server holds only the NS and glue records for cis.unimelb.edu.au, so it refers the query to ns.cis.unimelb.edu.au, which returns the authoritative A record.

Each result is cached with its TTL, so later queries skip the upper levels.

Tracing a cache with TTLs exam

Caching makes DNS fast, but a cached copy is a snapshot. If the authoritative data changes, a cache goes on serving the old value until the record's TTL runs out. The 2026 practice exam tested exactly this with concrete numbers, so step through its scenario.

Check yourselfSame setup, but the cached TTL is 100 s instead of 300 s. What does the client get at t = 180?

The entry cached at t = 0 is valid only until t = 100, so at t = 180 it has expired. The local server does a fresh lookup and returns the new address, 192.0.2.20. With this TTL the cached copy expired at t = 100, before the change at t = 120, so no client could have been given the stale address for this change.

Load sharing with DNS

Heavily used services such as web and FTP can run on a group of computers that share one domain name, with one A record per computer. The name server returns all the addresses in rotated (round-robin) order, and because clients usually use the first address, successive clients go to different servers.

Caching spoils this, since a resolver keeps using the answer it cached, so these records are given a short TTL. Even so, client selection and caching mean that an even load is not guaranteed, and DNS is unaware of server load or failure: it will keep handing out the address of a crashed server.

Past exam 2016 · Q8(b) · 2 marksExplain how DNS can be used to distribute the load of incoming requests over a set of servers.

• Register several A records under the same domain name, one for each server.
• On successive queries, the name server returns the addresses in rotated (round-robin) order. Clients normally use the first address, so successive clients reach different servers.
• Give these records a short TTL, because cached answers keep sending a resolver's clients to the same server.
• One caveat is that caching and client choice mean the load is not evenly balanced, and DNS knows nothing about server load or failures.

DNS issues and discussion exam

DNS has three weaknesses worth being able to discuss.

DNS from Java

You rarely talk to DNS directly. In Java, the class InetAddress calls the resolver for you. The example shows host name resolution, a name with several A records (the load-sharing case), and reverse resolution.

import java.net.InetAddress;
import java.net.UnknownHostException;

public class DnsDemo {
    public static void main(String[] args) {
        try {
            // Host name resolution: local cache first, then DNS
            InetAddress a = InetAddress.getByName("www.unimelb.edu.au");
            System.out.println(a.getHostAddress());
            // A name shared by several servers may return several A records
            for (InetAddress x : InetAddress.getAllByName("www.google.com"))
                System.out.println(x.getHostAddress());
            // Reverse resolution (PTR record via in-addr.arpa)
            System.out.println(InetAddress.getByName("128.250.1.22").getCanonicalHostName());
        } catch (UnknownHostException e) {         // unbound name or DNS unreachable
            System.err.println("Lookup failed: " + e.getMessage());
        }
    }
}

• InetAddress.getByName("www.unimelb.edu.au") is host name resolution: it checks the local cache first, then asks DNS for the A record, and returns an InetAddress. getHostAddress() prints it as a dotted string.
• getAllByName("www.google.com") returns every address bound to the name. A popular service shared by several servers has several A records, which is exactly the load-sharing set-up above.
• getByName("128.250.1.22") given a literal IP address just wraps it; getCanonicalHostName() then does reverse resolution, a PTR lookup in in-addr.arpa.
• UnknownHostException is thrown when the name is unbound or DNS cannot be reached, so lookups must always be wrapped in try/catch.

Designing a name for speed

The 2016 exam turned the ideas of this Part around: instead of resolving names, design one.

Past exam 2016 · Q8(c) · 3 marksResource objects are stored across a multi-server system. Given an object's name, the object must be accessible as fast as possible. Describe a name space and name format best suited to this, and explain why. Is your name a pure name?

• Use a flat, two-part, location-bearing name of the form serverID:objectID. The serverID identifies the storage server, and is mapped to an address by a small, locally cached table, or could even be the IP and port itself. The objectID is unique within that server, for example a local index or file handle.
• This is fast because the client extracts the server directly from the name and sends one request to the right server. There is no name-service lookup and no navigation through a hierarchy of name servers, either of which would cost extra round trips, and the server can use the objectID as a direct index.
• It is a non-pure name, because it contains information about the object's location. A pure name would carry no location, so it would always need a lookup (resolution) before access, which is slower.
• The trade-off is that the scheme loses mobility/location transparency. If an object moves, its name changes or a forwarding pointer must be left behind, as with dangling URLs.
• An alternative is a flat ID hashed to a server (for example, hash(id) mod N). This also avoids lookups, at the cost of rehashing when the servers change.

Check yourselfWhich statement about DNS is correct?

1. Recursive navigation is the DNS standard, and servers must accept it.
2. A secondary server's copy of a zone is non-authoritative.
3. DNS detects stale cached data and refreshes it when the authoritative record changes.
4. The resolver uses request-reply over UDP and retransmits after a timeout.

D. A is backwards: iterative is the standard and servers may decline recursion. B is wrong: secondaries hold authoritative data, obtained by zone transfer. C is wrong: DNS does not detect staleness; a cached record is simply served until its TTL expires.

Directory and Discovery Services

The problem. A name service answers "what are the attributes of this name?". Often you don't know the name; you know what you want. "Who has phone number 03-8344 1344?" "Where can I print a high-resolution colour image?" Directory and discovery services start from attributes instead of names.

Directory services are also called yellow pages or attribute-based name services, while name services are the white pages (after the two printed telephone books). Examples are X.500, LDAP and Microsoft Active Directory; UDDI (a registry for web services) provides both white and yellow pages. Attributes have two advantages: they allow more powerful selection, and they don't expose organisational structure the way hierarchical names do. Their drawback is that textual names are simpler, so names remain dominant.

Discovery services

A discovery service is a directory service for spontaneous networks, where devices come and go without any administrator. It is automatically updated as devices join and leave, and it finds the services that a client, possibly a mobile one, needs within the current scope, such as the best printer after you arrive at a hotel. An ordinary directory's address is preconfigured, but a newcomer to a spontaneous network must use multicast to find the discovery service, at least the first time. Examples are Jini discovery, Service Location Protocol (SLP), Bonjour and SSDP (used by media devices). DNS itself should stay a plain name-to-IP service.

X.500 and LDAP (brief)

X.500 is an ITU/ISO standard directory service. Its entries are sets of typed attributes arranged in a tree, the Directory Information Tree (DIT), and the whole database is the Directory Information Base (DIB). Servers are DSAs (Directory Service Agents) and clients are DUAs (Directory User Agents). A DSA that cannot answer either chains the query to other DSAs or refers the client to another DSA, the server-controlled and iterative styles of §9.5. There are two types of access: read, which looks up an entry by its name, and search, which takes a base node plus a filter on attributes.

X.500 is complex and saw little uptake. LDAP (the Lightweight Directory Access Protocol) lets a DUA access a directory directly over TCP/IP, with a simpler API and a textual encoding instead of ASN.1 (X.500's binary data-description notation). LDAP does not require X.500 behind it (Active Directory, for example, has an LDAP interface), and it is widely used in intranets for authenticated directory access.

Check yourselfName service vs directory service vs discovery service?

A name service (white pages) maps a name to attributes. A directory service (yellow pages) works the other way, taking an attribute specification and returning the matching entries; X.500, LDAP and Active Directory are examples. A discovery service is a directory that is updated automatically in spontaneous networks, and clients find it by multicast; examples are Jini, SLP and Bonjour.

Check yourselfYou arrive at a conference venue and your phone finds the nearest projector without any setup. Which kind of service did it use, and how did it find that service?

1. DNS, by asking its configured local name server
2. A directory service, at an address configured by the venue's administrator
3. A discovery service, located by multicast on the local network
4. LDAP over TCP/IP to the venue's X.500 directory

C. A spontaneous network has no preconfigured addresses, so a newcomer must multicast to find the discovery service, which is kept current automatically as devices join and leave. B describes an ordinary directory, whose address is preconfigured.

Global Name Service (Brief)

The problem. DNS is rigid: merging two trees or moving a subtree breaks names (§9.6). GNS, the Global Name Service from DEC and a descendant of Grapevine, targets the requirements of §9.3, especially restructuring over a long lifetime. It is only briefly examinable, so focus on the idea of the directory identifier.

Its structure is a directory tree in which each directory has a unique directory identifier (DI), a unique number that identifies the directory itself rather than its position in the tree. Names have the form ⟨directory, value name⟩: a path to a directory, plus a simple name inside it.

Check yourselfHow does GNS keep old absolute names working after two trees are merged under a new root?

Every directory has a permanent directory identifier (DI). When a new root (e.g. WORLD) is placed above old roots, a client prefixes the DI of its working root to its old names, so ⟨/UK/AC/QMUL, Peter.Smith⟩ becomes ⟨#599/UK/AC/QMUL, Peter.Smith⟩. A table of well-known directories maps #599 to its current path, /EC. Moved subtrees leave symbolic links behind. The cost is that the well-known directories table must be replicated everywhere.

Pitfalls and Tutorial 9

This last section collects the mistakes that cost marks on this topic and the official Tutorial 9 answers. The tutorial answers are from the tutors on Ed (Tutorial 09, Week 10); staff confirmed that tutorial content is examinable, so treat these as model answers. (The TLS part of that tutorial belongs to Part X.)

Common pitfalls

Tutorial 9 official answers

Tutorial 9 · Q1Define and discuss uniform resource identifiers.

URIs identify resources on the Web and other Internet resources, such as electronic mailboxes. They give a generic way to write identifiers, so common software can process any identifier. As a result, new types of identifier can be introduced easily, and existing ones can be used by many different programs and services.

A URL is a URI that includes a network location: the protocol (how) and the remote name (where). URLs suffer when a resource is renamed or moved, because the links to it break. A URN, by contrast, is a URI that holds a name within a given name space but no location.

Tutorial 9 · Q2What are name services and why do we need them?

Definition: a name service is a service that gives resources a consistent and uniform naming, so other programs or services can locate them and obtain the metadata they need to interact with them. Its main operation is to resolve a name, that is, to look up the attributes bound to it.

Naming is a separate service because distributed systems are open. Separating it gives unification: resources managed by different services use the same naming scheme, as with URIs. It also supports integration: sharing resources created in different administrative domains needs a common naming service, because without one each domain may use an entirely different name format.

The key benefits are that resources can be located (files, web pages, services, databases), that naming is uniform, and that addresses are device-independent, so that, for example, a website can move to another server seamlessly. A name service also returns other attributes of a resource, such as its domain and type.

Tutorial 9 · Q3What is navigation, and what are the approaches?

When a name service is distributed, one server may not be able to resolve a name, so the request is passed from server to server. This is called navigation, and there are four approaches (§9.5):

• Iterative. The client asks servers one at a time, usually following the domain hierarchy. Always starting at the root would put excessive load on the root.
• Multicast. The client multicasts the request to the group of name servers, and only the server holding the name replies.
• Non-recursive server-controlled. The client sends the request to one server, which continues iteratively on the client's behalf.
• Recursive server-controlled. Each server passes the request on to the next server itself, recursively.

Tutorial 9 · Q4What is DNS, and how does it improve on a file-based implementation?

DNS is a name service design whose main naming database is used across the Internet. Before DNS, all host names and addresses were held in one central master file, which every computer that needed it downloaded by FTP. That approach had three problems: it did not scale to large numbers of computers; local organisations wanted to administer their own names; and a general name service was needed, not one only for looking up computer addresses.

DNS is designed for use in multiple implementations, each with its own name space, although in practice the Internet DNS name space is the one in widespread use.

The tutors' figure is the partial DNS tree (CDK Fig. 13.4) with Australian domains. The authoritative path for xyz.cis.unimelb.edu.au runs from the root to au, then to edu.au and unimelb.edu.au, and finally to cis.unimelb.edu.au. Each zone has its own name server, which holds entries pointing to the servers for the next level down (see the figure below).