Suppose a network with 109 hostnames (not including the names of the nameservers themselves) uses non-recursive DNS.
Assume that there is a single root nameserver, multiple local nameservers, and M levels of nameservers in between local nameservers and the root nameserver. (The top level domain (TLD) nameservers are on the highest level of these M levels.)
Each nameserver has N names in its database. For instance, the root nameserver stores the N names of the TLD nameservers, and the local nameservers each store N names of host names. The local nameservers are authoritative for the N host names.
You may consider all of these nameservers as organized in a tree. The root of the tree is the single name server, and the second level of the tree has N TLD nameservers. The bottom of the tree consists of local nameservers, which collectively store 109 hostnames. For M=1, there is one level of nameservers between local nameservers and the root nameserver. For M=2: there are two levels of nameservers between local nameservers and the root nameserver. For M=3, there are three levels of nameservers between local nameservers and the root nameserver.
(a) If M=1, find N. If M=2, find N. If M=3, find N. [Hint: First, draw the DNS tree for M=1, and make sure you know what entries are in each DNS table.]
(b) Assume that the total of transmission, propagation and queueing delay for each message takes 0.2 seconds. Assume that the processing delay of a single DNS nameserver to respond to a DNS query takes 0.5 log(N) seconds, if the nameserver has N names in its database, where the log is base 10. Compare the time for a query and response for a complete DNS query and response (to all required nameservers) if M=1, M=2, and M=3.
