Test 3: Questions

X3.1.

[10 pts] The below diagram represents an internetwork; each thick solid line represents a single network, with the IP address block as shown (e.g., 10.0.0.0/16). The squares represent routers, each containing two or three Ethernet cards, identified as eth0, eth1, or eth2, configured with the IP address shown.

For the router named groucho, at left, what should the routing table be? Note that each row of the routing table should contain a network specification (or “default”), an Ethernet card identifier, and either the gateway IP address or the word “direct.”

X3.2.

[10 pts] Suppose a computer A asks a DNS server B for the IP address of www.meteo.an, and B's cache does not have anything related. What happens to resolve the IP address?

X3.3.

[8 pts] Suppose we manage a very busy Web site that overloads a one-server installation, so we decide to include multiple servers side-by-side serving the same data. How can we use DNS to distribute requests among servers?

X3.4.

[8 pts] TCP provides many more features than UDP. Give two reasons why a programmer might still opt for UDP over TCP for an application.

X3.5.

[8 pts] Suppose a TCP host A sends to B the packet sequence 1, 2, 3, 4, 5. Packet 3 is lost, while the rest reach their destination. What does B send back to A as it receives packets 1, 2, 4, and 5?

X3.6.

[8 pts] In TCP, a host tries to determine the appropriate window size for sending messages through a complex adaptation process. Of course, the receiving computer also requests a particular window size. Why can it not just use the window size requested by the receiver?

X3.7.

[8 pts] When a user requests a URL like http://ozark.hendrix.edu/filename.txt, and a day-old version of this URL exists in the browser's cache, what does the browser do to determine whether the cached version is still correct?

X3.8.

[8 pts] SPDY allows a browser to include a priority with each request. While the server cannot work harder in responding to the browser, the server may try to deliver the prioritized request before lower-priority requests on the same SPDY connection. Give an example where prioritizing requests could improve browser performance.

X3.9.

[8 pts] Explain how an OS can implement a memory-mapped file efficiently: That is, how can it allow a process to access the entire file in memory without actually loading the entire file into memory?

X3.10.

[8 pts] Suppose the disk previously served a request at track 52 before going to track 50 to serve another request. It has four outstanding requests that have arrived in this order (listed by track number containing request): 20, 67, 44, 55. What order will these be served with each of the following algorithms?

a.FIFO
b.SSTF
c.SCAN
X3.11.

[8 pts] Give an example of a program where an i-node-based filesystem will perform much better than a FAT-based filesystem, and explain why.

X3.12.

[8 pts] Suppose we have a filesystem with the following distribution of files: 58% of files are 4 kilobytes, 40% are 64 kilobytes, and 2% are 1,024 kilobytes (one megabyte). (These proportions are based on an actual study, but I have rounded the sizes to simplify the problem.) What proportion of used disk space do the one-megabyte files take?

Test 3: Solutions

X3.1.

[This question is actually erroneous, because the default case is supposed to refer to all Internet hosts not appearing explicitly in the diagram, but the diagram does not specific which router groucho can route such traffic to. In the following, I'll naïvely assume that groucho is actually attached directly to all Internet networks not otherwise given in the diagram.]

networkcardgateway
127.0.0.0/8localdirect
209.65.56.1/21eth0direct
10.0.0.0/16eth1direct
10.1.0.0/16eth110.0.0.2
10.2.0.0/16eth110.0.0.2
10.3.0.0/16eth110.0.0.2
10.4.0.0/16eth110.0.0.2
10.5.0.0/16eth110.0.0.3
defaulteth0direct
X3.2.

After A sends its request to B, B will first go to the root DNS servers to give the IP address for an authoritative DNS server (call it C) for the .an domain. It will then ask C for the IP address of an authoritative DNS server (call it D for .meteo.an. Finally, it asks D for the IP address of www.meteo.an. All of these results (the IP addresses for C, D, and www.meteo.an) are stored into B's cache should anybody else ask in the near future, and the final IP address is sent to A in response to its request.

X3.3.

Each Web server can be given its own IP address, and we can configure our DNS server to associate all of the IP addresses with the Web site's DNS address. When somebody browses to www.my-domain.com, the browser first sends a request to the DNS server asking for the Web server's IP address. The DNS server will rotate between which Web server's IP address it lists first, effectively distributing requests among the several IP addresses listed.

X3.4.
  • In an application doing real-time data, like voice calls, TCP's guaranteed delivery feature may be useless: Resending a dropped packet will likely arrive too late to be useful to the recipient.

  • In a simple request-and-response application, where both request and response are quite short, the overhead of establishing and remembering each TCP connection can be prohibitive. DNS is an example of this, which is why DNS is usually implemented over UDP.

X3.5.

Each acknowledgment implies receipt of all packets up to whichever packet is acknowledged. Upon receiving packet 1, B acknowledges packet 1; on receiving 2, B acknowledges 2. However, on receiving 4, B cannot acknowledge 4 since it hasn't received all packets up to 4: Instead, it re-sends acknowledgment of 2. The same thing happens on receiving 5.

X3.6.

The appropriate window size is largely dictated by the network capacity — how busy the intermediate routers are.

X3.7.

The browser opens a TCP connection to port 80 of ozark.hendrix.edu and sends an HTTP request. One line of the HTTP request will be an If-Modified-Since field, providing the timestamp from the cached version of the file. If the server can verify that the file is unchanged since then, it will send a “Not Modified” response, without re-sending the data from the file. However, if the server has a newer version of the file, it sends the normal “OK” response, along with the modifie file.

X3.8.

The multiple resources required for a page will include some resources that are not needed immediately for rendering the page: Images are a typical example where the priority can be lower, as the browser can simply display a placeholder until the image is fully loaded. By contrast, the browser has more of a need for files that dictate the overall page layout, including the HTML and CSS files. Also, it can pay to prioritize requests that are more likely to lead to further requests - JavaScript files would be one example that, when executed, often lead to needing additional resources.

X3.9.

The OS can dedicate a portion of virtual memory space to the file, without yet accessing the file. Instead, the OS marks all pages in the dedicated virtual memory region to be “inaccessible.” When the program accesses one of these “inaccessible” pages, it triggers a protection fault, and the OS can recognize that it is because the program attempted to access one of the pages corresponding to the file. At that time, it can load the corresponding block from the file into memory, repairing the page table to reference the loaded block and marking its page table entry now as “accessible” so that the program can access it. In this way, the OS ends up loading blocks from the file only when they are demanded.

X3.10.
a.FIFO: 20, 67, 44, 55
b.SSTF: 55, 44, 67, 20
c.SCAN: 44, 20, 55, 67
X3.11.

Suppose we have a program that does random seeks within a very large file. With a FAT-based system, finding where a block in the file's middle involves a search through a linked list. This could involve stepping through a large number of blocks within the FAT, particularly if the file is highly fragmented. With an i-node-based system, each seek involves examining at most three blocks - one to access the triple-indirect block, another to access one of the double-indirect blocks it references, and another to access one of the single-indirect blocks it references.

X3.12.

42.3%. (Assuming exactly 100 files for the sake of computation, the total amount of disk space would be 58 × 4 + 40 × 64 + 2 × 1024 = 4840KB. The two 1024KB files would take 2048/4840 = 42.3% of that.)