CS E6998-043: Advanced Internet Services

Fall 1996 Final Exam

This is a closed-book exam. You have 120 minutes to complete the exam.
  1. What happens if host tune.cs.columbia.edu and host www.ibm.com (by accident) get assigned the same MAC address? (5 pts.)
    Nothing happens, as the two hosts are on different IP subnets and thus no single network element (router or host) will ever see MAC-layer packets from both hosts. Example of MAC-layer addresses include the 48-bit Ethernet addresses which are typically assigned to each Ethernet card by the manufacturer. Note: theoretically, two hosts with different domain names could be on the same subnet (see question below on virtual hosting), but the example was chosen to make it clear that these two hosts are not.

  2. Give one example each of a soft state and a hard state protocol. Justify your choice. (5 pts.)

    Only protocols that establish state outside the originating host count. Thus, it makes little sense to classify UDP, ARP, RARP, HTTP, etc. in this way. Indeed, these protocols are often referred to as stateless. Whether routing protocols are soft or hardstate is a matter of debate.

    Softstate protocols establish state "optimistically", without explicit handshake. Periodic messages are used to set up and refresh state. There is no explicit teardown, except as hints to increase efficiency. Examples include RSVP to establish reservation state in routers, IGMP to set up local multicast forwarding state in routers and RTCP to maintain group membership.

    Hardstate protocols set up and tear down state by explicit handshake protocols. The state request is repeated until the other systems acknowledges state establishment. Examples include H.323 for setting up Internet telephone calls, ST-II for setting up point-to-multipoint data flows, Q.2931 for establishing ATM virtual circuits and TCP for setting up a transport association.

  3. The minimal audible difference in loudness is 3 dB. What power ratio (or ratio in air pressure) does this correspond to? (5 pts.)
    Decibels are defined as
    dB = 10 log10 p = 20 log10 v,
    where p is a power ratio and v is a voltage (or air pressure) ratio. Thus,
    p = 103/10 = 1.995
    v = 103/20 = 1.413

  4. At 10 pm on some evening in the not too distant future, 1,000 users on a CATV network (bandwidth 10 Mb/s) have set their timers to start their video program to watch the evening news. The news are carried as a 20 kb/s bitstream using RTP and RTCP over multicast IP. How long, on average, does it take until everybody knows the number of other receivers? RTCP packets are 100 bytes long and the standard RTCP bandwidth (5% of data stream) is used.

    Estimate a lower bound on the time it would take if the users are connected by modems. Explain the simplifications that you are making. Hint: Your estimate should differ from the CATV case. (10 pts.)

    Note that the problem addresses the transient, not the steady-state behavior of the RTCP bandwidth scaling mechanism.

    According to RFC 1889 (and the code in the appendix), the first RTCP packet is sent within one half the minimum RTCP interval of 5 seconds, that is between 1.25 and 3.75 seconds after joining the conference. The overall RTCP bandwidth is 1 kb/s or 125 bytes/s or 1.25 packet/s. If all receivers send their first RTCP packet in these 2.5 seconds, 1000 * 100 bytes will be sent in that time interval, or 320,000 bits/s.

    For the CATV case, this is unlikely to cause a problem, so that all receivers know about the other 999 after the first transmission. After that, every receiver would send an RTCP packet after, on average, 1000 seconds.

    For the modem case, only 28.8 kb/s of this RTCP burst is received. This is equivalent to 36 packets/s, so that after 2.5 seconds, each receiver will think that there are 90 others in the group. Based on that, it will set its retransmission rate to 1 kb/s divided by 90, that is, 1.4 bytes/second or one RTCP packet every 71 seconds. Thus, the overall rate will be 14 packets/second or 11.2 kb/s for RTCP traffic, causing severe packet loss on the modem line.

    The next batch of packets will arrive at between about 35 seconds and 106 seconds after the first RTCP burst. Thus, assuming no additional RTCP packet loss, all modem users will know the group size after 106 seconds.

    For simplicity, we are ignoring the bandwidth division between senders and receivers, which would decrease the sending rate somewhat.

    Note that the RTCP packet interval never depends directly on the line speed, but only at the nominal rate of the RTP data rate. In most cases, an RTCP sender would have no way of ascertaining the minimum bandwidth among all the group members, for one. Also, if every session would have an RTCP bandwidth which is a fraction of the physical layer speed, 20 sessions on a physical medium would always saturate the wire with RTCP traffic.

  5. Alice is connected to the Internet via a 28.8 kb/s modem and wants to participate in an audio conference with Bob, Charlie and David. The three men are talking (usually being polite) at 20 kb/s codec using RTP. Alice's ISP is offering her to connect to the conference through either a translator or a mixer. The translator converts the audio to a 10 kb/s codec. Explain the trade-offs between the two choices. (10 pts.)

    With a translator, Alice will hear the men at 10 kb/s, that is, with reduced speech quality. If all three talk at once (or one's office has sufficiently loud background noise to trigger the silence detector), packets will be dropped since the total line capacity is insufficient for three simultaneous speakers. Since the streams are transmitted separately, Alice can mute each speaker separately.

    Note that since Alice is on the other side of the modem link, she can still speak simultaneously with the men, regardless of whether her ISP uses a mixer or a translator.

    With a mixer, there is no limit on the number of simultaneous speakers and the audio quality is not reduced. However, Alice cannot select among the possible speakers. Also, a mixer introduces higher delay since it has to do playout delay compensation prior to mixing, in addition to the playout delay inserted by Alice's audio receiver software.

    Note that a mixer does not degrade the sound quality, it simply adds the linear sound samples. There is one exception: if a sender's silence detection malfunctions and this sender transmits background noise, Alice could mute this one sender. However, this only helps if the bottleneck bandwidth can support the extra sender. Note that some multicast routing protocols support sender selection at the IP level, which would solve this particular problem to some extent - except that Alice would have no way of knowing when the conversation partner with a noisy office actually has something to say.

    For block-oriented codecs, mixing requires conversion to and from a linear encoding. A translator would require a similar conversion between codecs, which is also typically done by decoding the incoming stream into either 16-bit linear samples or mu-law samples and then re-coding with the outgoing codec. Mixers require playout delay adaptation, the complexity of which can range from trivial to extremely involved. However, implementation complexity was not one of the considerations since Alice's ISP has already implemented both.

  6. A simple cache checks only whether the URL specified in the HTTP GET command is already stored in the cache (and has not expired). Name two cases where this may lead to the display of the wrong document. (5 pts.)
    The simple cache checks expiration only locally, that is, by remembering the value of the Expires header. This can fail if
    • the document has no expiration header and the document on the server has changed, for example, documents which are dynamically generated by cgi-bin scripts,
    • the URL refers to a collection of documents, say, of different content types or languages.

    Thus, the cache must store the Content-Type and Content-Language values of the cached document and compare them with the request. For documents without explicit expiration data, the cache must issue a GET with an If-Modified-Since header to the original location.

    Beyond these cases, there are a number of error conditions where this could (but should not) happen:

    • implementation mistakes (don't count...);
    • the document has been deleted (doesn't count since it's not the wrong document);
    • a document which has not reached its expiration time, but is nevertheless modified;
    • the browser could have a wrong notion of time, so that it misses the fact that a document has already expired.

    Side note: The Netscape browser does not necessarily check the server if the "reload" button is pressed, depending on how the browser is configured. "shift-reload" will always trigger a reload. The "back" button explicitly should not check, since it is supposed to show the URL as it was displayed, not as it may look now.

  7. A GCRA policer has parameters L = 100 microseconds and T = 200 microseconds. Sketch the packet departure pattern for cells arriving at intervals of 50 microseconds. (10 pts.)

    The first cell arrives at t=0 and is accepted. It sets the next theoretical arrival time (TAT) to T = 200 us. The second cell arrives at t=50 us, is early and discarded (or marked). The third cell arrives at 100 us and is within the window L and accepted, setting the next TAT to 400 us (adding T to the time this cell "should" have arrived according to the PCR). The fourth cell arrives at t=150 us and is early again, and so on. Overall, three-quarters of the cell are dropped. Note that L affects the identity of the cells dropped, but not the rate.

    From the value of T it is clear that the policer has to drop or mark 3/4 of all packets. A policer by definition does not delay packets.

  8. Why might a web server have several IP addresses for a single interface? (5 pts.)

    A single network interface on a web server (say, an Ethernet card) may have several IP addresses to allow virtual hosting, where a single host serves several web domains. Different IP addresses are needed since the HTTP/1.0 request does not contain the name of the host the request is meant for, just the path name of the resource. The web server then uses the destination address of the request to determine which virtual host the request was meant for. Each IP address may have its own MAC address or they may all share the same address.

    A host does not need separate IP addresses just to have several names. The DNS CNAME facility allows this at the DNS level. Indeed, most web servers have at least two names, "www" and their "real" name.

    Having more IP addresses on a single interface in no way improves performance.

    Stub or "one-armed" routers also have interfaces with multiple IP addresses. For example, there may be single Ethernet carrying multiple IP subnets, with an IP router to connect them. (This was not discussed in class, but is a valid answer.)

  9. What is an important difference between writing a Java program and a Java applet? (5 pts.)
    • A Java program has to have a main.
    • A Java applet has to be derived from the applet class.
    • A Java applet can only connect via TCP to the host where it was loaded from and cannot receive or send multicast packets.

  10. Chaining and redirection are concepts found in a number of Internet protocols. What mechanisms does HTTP offer to implement these? (5 pts.)

    HTTP implements chaining, that is, passing on a request and the response through a set of intermediaries, via HTTP proxies.

    HTTP implements redirection through 3xx Redirection status codes and the Location header as well as the Refresh header, a Netscape proprietary extension. Even though the Refresh header is often included in the HTML http-equiv meta tag, it is independent of HTML.

    Note that HTTP is not restricted to transporting HTML, even though its name may indicate that.

  11. Sketch the packets exchanged for a web page protected by the "basic" HTTP authentication mechanism. (5 pts.)
    The client requests a document:
    GET / HTTP/1.0
    The server refuses the request with status code 401:
    HTTP/1.0 401 Unauthorized
    WWW-Authenticate: Basic realm="WallyWorld"
    The client then re-issues the request and includes the base-64 encoded user name:password:
    GET / HTTP/1.0
    Authorization: Basic QWxhZGRpbjpvcGVuIHNlc2FtZQ==
    The server then responds by sending the document:
    HTTP/1.0 200 OK
    Content-Type: text/html
    Protected document.

  12. How can one convey forms data to a program? Briefly describe two different methods (not involving Java), as they affect HTML, HTTP and the server-side program. (5 pts.)
    See the HTML forms tutorial.

Course grade distribution:
grade>= pts.count
A 9013
B 7511
C 605
D 501
F 01
I  3
F* 3
total 70

Last modified: December 27, 1996 by Henning Schulzrinne