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.

[Adapted from Walrand 2nd edition problems 3.1 and 3.2]