printable version
Test 3
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
Problem 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.”
[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.]
| network | card | gateway |
| 127.0.0.0/8 | local | direct |
| 209.65.56.1/21 | eth0 | direct |
| 10.0.0.0/16 | eth1 | direct |
| 10.1.0.0/16 | eth1 | 10.0.0.2 |
| 10.2.0.0/16 | eth1 | 10.0.0.2 |
| 10.3.0.0/16 | eth1 | 10.0.0.2 |
| 10.4.0.0/16 | eth1 | 10.0.0.2 |
| 10.5.0.0/16 | eth1 | 10.0.0.3 |
| default | eth0 | direct |
Problem 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?
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.
Problem 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?
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.
Problem 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.
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.
Problem 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?
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.
Problem 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?
The appropriate window size is largely dictated by the
network capacity — how busy the intermediate routers
are.
Problem 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?
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.
Problem 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.
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.
Problem 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?
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.
Problem 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: |
20, 67, 44, 55 |
| b. | SSTF: |
55, 44, 67, 20 |
| c. | SCAN: |
44, 20, 55, 67 |
Problem 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.
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.
Problem 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?
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.)
