Question :

Suppose a network with 10^9 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.

Each nameserver has N names in its database. (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.

**Update: (Hint):

In the proposed network:

Root nameserver stores N entries of top level domains (TLDs).

Each TLD stores N entries of local nameservers.

Each local server stores N entries of host names.

For M=1, there is one level of nameservers between local nameservers and the root nameserver.

You may consider the whole network as a tree in which root of the tree is the root nameserver which has N children (TLDs). Each TLD has N children (local nameservers) . that each one has N children (host names).

Shortly, we have a tree with three type of intermediate (non-leaf) nodes including root nameserver, TLDs, and local name servers. Each non-leaf node of the tree has N children. Leaves of the tree are host names (10^9 in total).

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.