Assignment Overview

Tired of typing in all those IP addresses in Project 3?

In this project you'll implement a distributed name system modelled after the Internet's Domain Name System (DNS). Instead of IP addresses, you'll be able to use character string names to name your code running on a phone or a workstation. The basic functionality of the system is to translate a character string name to an IP address and port. Our system is entirely separate from the Internet system. We're creating our own name space

Because phones go offline a lot, our system supports dynamic registration of IP address/port pairs. Thus its name: Dynamic DNS (DDNS). (DDNS exists in the Internet as well, but doesn't have a well accepted specification.) A phone or other device registers its current location (IP/port) when it comes online, and, with any luck, registers that it is going away before it loses connectivity.

Three things make this project more challenging than the previous ones:

1. In Project 3 you could try to interact with other groups' code. In Project 4, you have to interact with other groups' code. It's one distributed application (DDNS), just with lots of implementations.
2. Project 4 isn't a simple client-server model. Instead, there is a graph of DDNS servers and you may have to interact with many of them to perform a single name to IP/port translation.
3. Your Project 3 code has to work. Communication in Project 4 is by RPC.

On the Android side, you'll adapt your Ping application to work with DDNS names - the user can provide a DDNS name rather than an IP/port. Once again, the main goal is simply to make sure that all components of your system will load and run on Android, using Ping as a test case. That verification is important because Project 5 will be an Android app.

System Architecture

The overall architecture remains basically the same:

The major pieces for this project are the DDNS Service and DDNS Resolver Service. The DDNS Service maintains a piece of the name to IP/port mapping information. It provides access to that mapping information only by RPC. Not every machine needs to run a DDNS Service instance.

The DDNS Resolver Service can be thought of as library code. Clients invoke the local instance to translate a DDNS name to an IP/port pair. The DDNS Resolver Service contacts as many DDNS Services as necessary to resolve the name and returns the result to the caller. Every machine needs to run a DDNS Resolver Service.

Additionally, there are two components that we've supplied that are useful for debugging. The first is the nslookup application, which mimics the similarly named utility found on many systems. It provides a command line interface that lets you present name resolution requests to your DDNS Resolver implementation. The second component is an httpd (web) service. It allows you to examine the internal state of a remote service, to cause a remote service to query your service, and to instrument your implementation so that you can fetch its current state, all using a browser. The httpd service is described in more detail elsewhere.

DDNS Name Resolution, Namespaces, Name Servers, and Resource Records

Note that DDNS is similar in many respects to the Internet's DNS, but also differs in many details. If you understand DDNS, you'll understand a lot about DNS, but they are not exactly the same.

DDNS uses hierarchical names composed of dot separated fields, and with the root to the right. This is the form you're used to from names like www.cs.washington.edu. DDNS names are case sensitive. The Internet's DNS names are not.

Resolving a DDNS name means determining the IP address and port number for the RPC service running in the named instance:

DDNS name → (IP, port)_RPCService

The DDNS name space is a tree. The tree is partitioned into zones. There is a 1-1 mapping between DDNS Service instances and zones: each zone is managed by one server instance, and each server instance manages only one zone.

Here's an example namespace, and its relationship to DDNS Service instances:

The black lines define the tree part of the namespace. There is a root at the top. The root's name is the null string, so you don't see any text. Other names in the namespace include cse461, jz.cse461, emulator.jz.cse461, and galaxy.jz.cse461.

The ovals are zones, which are maintained by DDNS Service instances running on distinct systems. The one containing the root runs on the machine (with DNS name) cse461.cs.washington.edu. It's immediate child might run on some always available system, say attu.cs.washington.edu. The one containing galaxy might run on my phone, which is not always available.

Zones are linked by two nodes with identical names, one in the parent and one in the child. The parent node allows one to find the DDNS Service hosting the child zone; the child node contains an authoritative (IP,port)_RPCService mapping for the name. This simplifies what is actually done in the Internet's DNS system, making implementation of DDNS easier. As a side effect, though, a zone can be hosted only on the node named by the root of that zone; we can't assign zones to arbitrary systems.

Not every DDNS system instance has to be configured to run a DDNS Name Service. My htc and emulator phones don't, in this example. (All systems run DDNS resolvers, however.)

Associated with each name is a resource record. There are four kinds of resource records in DDNS:

• A - An address record holds the basic information (IP, port)_RPCService. For instance, an address record for htc.jz.cse461 would hold the IP/port of the RPC service running in that instance.
• SOA - A start of authority record is the root of the subtree of names located on a single name server. There must be exactly one SOA record on a name server. In the figure, the root node would have an SOA record, as would the lower jz.cse461 and galaxy.jz.cse461 nodes. SOA records contain (IP,port)_RPCService of the system they run on.
• NS - A name server record is a leaf node in its zone. It links to a corresponding SOA record on some other server. The blue lines show those links, with the NS records being those closer to the root. NS records contain (IP,port)_RPCService for the node running the DDNS Service instance that maintains the zone for which the target name is the SOA. Because of simplifications made by DDNS (relative to DNS), the DDNS Service maintaining some zone with SOA name X must run on node X. Logically, though, the NS record names the node on which the zone is hosted, and the SOA record in that zone names the RPC Service associated with its name; it's just that in DDNS these two must be the same.
• CNAME - A canonical name record maps one name to another. These are shown by the red links in the figure. For instance, the CNAME record for root.test.cse461 maps to the root, so names cse461.root.test.cse461 and cse461 are the same thing.

When a DDNS service comes online (is connected to a network), it registers its own (IP,port)_RPCService with DDNS. This sets the IP/port of both the NS and the SOA records associated with it. When it goes offline, it unregisters its address. That doesn't remove its name from the namespace, just flags the name as having no current address.

DDNS Full Names

It's convenient to work in code only with fully qualified DDNS names. A fully qualified DDNS name ends with the name of the root, which is the null string. This means that the fully qualified name of the root is the null string, and that every other fully qualified name ends with a period. For convenience, the final dot of names can be omitted when the names are provided by users. Thus the name you type in a browser, say www.cs.washington.edu, is really www.cs.washington.edu. as a fully qualified name. (Try it.)

Internally, DDNS allows only full names. It accepts shortened names in calls available to client code, but immediately translates those names to full names for exchanging names with the various DDNS components. Using only full names internally makes common operations, like comparing two names, simpler. Full names also make your code simpler, because there is nothing special about the root - you don't have to artificially inject it into the resolution process, or not, depending on whether or not the user has actually typed it.

Name Resolution and Resolvers

Besides registering and unregistering addresses, the other operation supported by DDNS is name resolution, which means looking up a name and returning the resource record associated with it. DDNS name resolution begins at the root, and proceeds component by component of the name, starting from the right. For instance, to resolve htc.jz.cse461 we follow the cse461 edge out of the root, then the jz edge. Because that node has an NS record, we proceed to the next name server, and evaluate htc as a child of its SOA record.

If that procedure encounters a CNAME record, the portion of the name resolved so far is replaced by the the alias contained in the CNAME record, and name resolution restarts at the root. For instance, when resolution of jz.cse461.root.self.test.cse461 encounters the self CNAME record, the name is rewritten to jz.cse461.root.test.cse461 and resolution starts over. This time it encounters the root CNAME, rewrites the name to jz.cse461 and starts over. At this point, resolution can finish without further rewrites.

Name resolution is carried out by name resolvers. Every system must be configured to have a name resolution service component installed. That component resolves names iteratively. It first asks the root name server to resolve the name. If that name server encounters an NS record, it returns information about it to the resolver, which is in charge of continuing the resolution process with the next name server. Similarly, if the name server encounters a CNAME record, it returns that to the resolver, which rewrites the name and restarts resolution. If the name service finds that the name doesn't resolve to anything, it returns an error.

Following some simple rules will keep you from creating code that loops during resolution:

• DDNS name servers never talk directly to each other.
• All invocations of DDNS name server methods is via RPC. There are no local (Java) calls to any of its methods (other than the ones made by the RPC service).
• DDNS name resolution services don't expose any methods via RPC. They provide methods available to local applications and services, but not methods available via RPC.
• DDNS name servers never make local calls to name resolvers. Among other things, this means that cached name records are never communicated to any remote machine.
• Applications never make calls to DDNS name servers. All such calls originate from name resolvers.
• DDNS name resolution always begins at the root, and returns to the root if the name must be rewritten.

These rules ensure that the communication pattern has no loops: it's app to resolver to name server(s). Trying aggressively to optimize by short-circuiting can lead to madness, via many difficult bugs.

Remember that the resolver can't assume there is a name server instance on the machine with it. This means you can't just code Java procedure calls from the name resolver to the name server. In theory, you could do this in some specialized cases, but it's easiest/best for the resolver to always talk to the name servers via RPC, no matter what. It also means your code must work even when there is no name server loaded on some particular device.

Finding the Root Server

You can't use DDNS to find the address of the root server. Your code therefore simply has to know where the root is. It gets this information from the config file, specifically entries ddns.rootserver and ddns.rootport.

Dealing with Naming Loops

You may be wondering if it's guaranteed that the resolution procedure just described eventually terminates. The answer is no. The example namespace contains a simple loop: loopA.test.cse461 evaluates to loopB.test.cse461 and vice versa. While you could think about preventing such loops, it's hopeless: the loops could span any number of name servers and would require complicated and correct implementations across all of them to have any hope. This means your code must deal with the possibility of loops, on its own.

We deal with possible loops using two similar mechanisms, both based on limiting the number of resolution steps we're willing to take. To avoid loops that span multiple zones, the resolver puts a limit on the number of resolve() RPCs it makes to name resolvers. To avoid loops formed within a zone, the name service puts a limit on how many edges it will traverse before giving up. (A conformant name service could skip this check, since the zone is finite. However, using it provides added insurance that your code doesn't go into an infinite loop, especially if you try to optimize CNAME handling.)

These limits mean that it's conceivable that some valid names can't be resolved. The limits need to be large enough that that's very unlikely. On the other hand, large limits are a performance issue when a loop actually exists.

Caching: Positive and Negative

As you can imagine, this process can be pretty slow. To help speed things up, name resolution service components maintain a cache of recently fetched resource records. The cache is simply a map from a name to a resource record. Records received from name servers are placed in it. Because the cache can go out of date, each cache item is removed from the cache after some timeout interval (of your choosing). This means that the resolver may give incorrect results, because the data associated with a name may change in the name servers while an item is cached. The item will eventually time out, though.

Going over the network is so expensive (in time and energy) that we want to make use of any information we get that way. Some of the information we get is negative. For instance, after resolving name foo.cse461 we learn that name doesn't exist. The resolver records that information in the local cache, so that if the name is used again in the near future we don't have spend even more energy finding out it doesn't exist.

A similar but distinct situation is that some name name exists but there is currently no address associated with it. (htc.jz.cse461 exists, but is offline, say.) We cache that as well. The resolver distinguishes the two cases because it might be important to some of the resolver's clients, which are "any application anyone wants to write, ever."

Registration Keep-Alive

Ideally, a system that registers an address for some DDNS name will unregister the address when that system goes offline. In practice, DDNS can't rely on that happening, since the system can simply lose network connectivity without warning. Because we don't want to advertise a no longer working address for a name indefinitely, DDNS requires that a system registering an address repeat the registration periodically. If the registration is not repeated within a DDNS name server specified period, the name is unregistered by the DDNS name service.

In terms of implementation, each successful register() call on DDNS returns a "lifetime" value indicating how many seconds the registration will be maintained before it is automatically unregistered. The name should be re-registered before that time expires.

Security

DDNS has no security. However, it has passwords: each node in the distributed name tree has a password associated with it, and updates to its resource record require the password. No password is required to read the record, so anyone can resolve any name. Only the "owner" of the record knows the password, presumably, and so alone is able to set the IP/port information, say.

Our use of passwords has a single, pragmatic motivation. Without something like passwords, any name resolver can trash any part of the name space because of an unintended bug. With passwords, your buggy name resolver can trash only those names you have the password for, which presumably are parts of the name space you own. Thus, passwords provide some failure isolation, which should help everyone debug their code.

The Production Root Server

There is an almost-always-up root server running at cse461.cs.washington.edu:46120. That information is "well-known," and needs to be provided statically to each name server instance. (The name server can't look up the address of the root using DDNS, because it can't ask the root to resolve a name without having the address of the root.) While testing, you can run your own root, of course.

That server runs an HTTPD service on port 46199. That lets you see what the root DDNS name server thinks the current mapps are for the names in its zone. It also lets you request that the DDNS resolver there resolve a name that's in your zone. It's easy to implement this, or expanded, functionality in your own code if you want to run your own root.

DDNS Protocol Overview

The protocol description is located on another page.

Implementation Details

Also neatly kept out of the way on another page.

Suggested Extension

Make more aggressive use of the resolver cache to avoid querying the root server so often.

Submit online three things:

1. Three directories and their contents: ConsoleApps/, Net/src/.../DDNS/, and ConfigFiles/.
2. A text file, named results.txt, that are the cut-and-paste output of running the testing application described below.
3. A short writeup answering the questions listed below.

Because of the somewhat unexpected appearance of the writeup, the due date has been extended slightly more than one day (to 11:00 AM (i.e., the morning) of Friday, 11/16).

The Test Application

The test application performs some simple resolve() calls. It is by no means an exhaustive test suite. To run it, do the following:

1. Fetch file DDNSTester.jar into the Lib/ directory of your workspace.
2. Right-click on the Lib project in Eclipse and choose Refresh. (The new jar file should appear.)
3. Right-click on the ConsoleApps project. Choose Build Path then Configure Build Path. Click on the Libraries tab, then the Add JARs... button. Open the Lib Folder, select DDNSTester.jar and click on the OK button. A DDNSTest.jar icon should appear in the ConsoleApps project.
4. Edit your config file to load the console application edu.uw.cs.cse461.ConsoleApps.DDNSTester.
5. Edit your config file to set debug.level to 5.
6. Launch your code and run application ddnstester. Type the names of the people on your team when prompted. Wait a bit and some tests runs.
7. Cut-and-paste the output that appears in the console window into a text file, results.txt, and submit as part of your turn-in.

Note: the test application both prints its results on the console and sends them to a server that records them.

The Short Report

Please answer the following questions about your implementation. Answers should be concise. Attending section this Thursday could be very useful.

1. What does your resolver do if an RPC invocation of resolve() on a DDNS service fails with a DDNSRuntimeException?
2. What does your resolver do if an RPC invocation of register() on a DDNS service fails with a DDNSRuntimeException?
3. What does your resolver do if an RPC invocation of unregister() on a DDNS service fails with a DDNSRuntimeException?
4. Suppose some console application code makes three successive calls, all for a single name (e.g., "foo.uw12au.cse461."). The calls, in order, are register(), unregister(), and resolve(). It does this even if one or more of the RPC calls of similar names fail. (There are no local (same node) failures, though.) Does your implementation guarantee that the final resolve() returns the same result, no matter which RPC calls have failed? If so, explain how it manages that. If not, explain what the possible answers might be, and why.
5. Does your DDNS implementation provide "eventual consistency"? That is, suppose that all DDNS zones are running your code. There is a period of time during which applications run and issue queries and updates to the DDNS system. During that period of time, nodes may crash and network disconnections may occur. After that, all nodes have restarted and no further DDNS calls are made by any application code. If enough time passes with no further updates, will all nodes agree about the outcome of resolve() for every possible name? Very briefly explain your answer. (This is really a question about your design, not your code. Asume your code has no bugs in answering.)

Notes

• The DDNS specification is precise about what information goes on the wire. It's fuzzy about what the receiver of that information should do with it -- we know that calling resolve() should result in name resolution, but we don't specify all details of how that works, or what to do in every case. You should keep clear that there are implementation choices, and you're free to make whatever decisions about them you want, so long as you interact with other DDNS implementations in sensible ways.