CS E6998-3: Advanced Internet Services

Spring 1998 Final Exam

This is a closed-book exam. You have 150 minutes to complete the exam. Please make sure that the problems appear in order in your "blue book", with each problem starting on a new page. The exam has a total of 62 points.

1. Give an example of an RSVP killer reservation, using a drawing. What feature of RSVP causes this problem? (5 pts.)

   See class notes and RFC 2205, section 2.5: "The first killer reservation problem (KR-I) arises when there is already a reservation Q0 in place. If another receiver now makes a larger reservation Q1 > Q0, the result of merging Q0 and Q1 may be rejected by admission control in some upstream node. This must not deny service to Q0." [3 points for this part]

   The problem is caused by the merging of different reservations coming from receivers for the same flow and appears in any receiver-oriented reservation protocol with diverse receiver requirements. It is not caused by having small and large reservations for different flows - large flows blocking smaller ones is a generic problem of any reservation protocol. [2]

2. Compare the properties of the E.164 telephone numbering system on one hand and IP addresses and DNS host names on the other. (5 pts.)

   property	E.164	IP	DNS
   format	textual, numbers, < 15 digits	32-bit binary	dot-separated text
   assignment	geographic, function (800)	network topology/provider, function (multicast)	organization
   structure	fixed (NANP: country, area code, exchange)	variable-length prefix	country/type, organization, sub-organization
   capacity	> 1015	109	> 1028 (with 16 letters)
   mapping	800 to landline, directory service	ARP: IP to MAC, RARP: MAC to IP	DNS: DNS to/from IP
   density	very high, with area-code splits	high, but permament	very low
   sharing of names	several home phones = one number; hunt groups	each interface = one IP	several hosts = one name; one host = several names
   local names	yes, several levels	no, but net 10 + NAT	yes, within domain

   [need 3 of the above]
3. Compare the properties of ADSL and cable modems for distribution of Internet multimedia and for Internet telephony. (5 pts.)

   property	ADSL	cable modem
   downstream bandwidth	lower (1.5 Mb/s)	higher (30 Mb/s)
   QoS	dedicated pipe	shared bandwidth
   upstream bandwidth	lower (16...640 kb/s), but fixed; sufficient for video?	lower than downstream (768 to 2 Mb/s, shared)
   multicast	possible, but no efficiency gain	very efficient; downstream only
   Internet telephony	dedicated access bandwidth, may not be sufficient for video	shared, low upstream bandwidth (typically, engineered for 150 kb/s max.); downstream engineered to guarantee at least ISDN (128 kb/s) speed

   [Need at least 2 properties.]

4. The IPv6 header is 40 bytes long, the IPv4 header 20 bytes, while the address size has quadrupled. What functionality has disappeared from the fixed header? (5 pts.)

   Header length, header checksum, fragmentation.

5. Sketch the TCP congestion window size as a function of time (measured in RTTs) if a single loss occurs on the 12th packet. Assume that the MSS is 1000 bytes and that the system uses fast retransmission. (5 pts.)

   The congestion window increases by one for each packet received (i.e., doubles every RTT) until the packet loss occurs. Note that the packet loss occurs after 12 packets, not 12 round-trip times. After the 12th packet is lost, the sender will get duplicate ACKs and reset ssthresh and cwnd to half the current congestion window.

   

6. Assume that all nodes in a network are separated by a propagation delay of 100 ms (one way). Even with conditional reconsideration, (roughly) how many RTCP packets will a user receive in the initial burst assuming that 10,000 users join all at once? (5 pts.)

   All group members are scheduled to transmit their first RTCP in the 2.5 second interval between 1.25 and 3.75 seconds. 0.1/2.5 of the users, or 400, will send a packet before they have received a packet from anybody else. For this initial burst, reconsideration cannot help.

   Note: Due to imprecision in question, have to accept "10,000" as an answer since the total number of packets transmitted will be that high.

7. You can run SIP in proxy or redirect mode. Compute the call-setup delay and compare the server processing requirements for a server handling the cs.columbia.edu domain, assuming that the caller is in California and the callee is at erlang.cs.columbia.edu, with a one-way delay between California and CU of 50 ms. You can ignore the delay within the Columbia local area network. (5 pts.)

   One-way delay coast-to-coast is approximately 30 ms. We assume that no packets are lost. For a redirect server, there would be two trips across the country, for a total delay of 150 ms. The second INVITE would require the caller to wait for the ACK, thus the extra 30 ms.

   For a proxy server, we can ignore the propagation delay within the CUCS domain. The call would take about 90 ms to set up.

   Processing overhead is somewhat less for a redirect server since it does not have to generate its own call.

8. One would imagine that on average, a silence detector would reduce the bandwidth of packet telephone conversation to half of a circuit-switched conversation. Name two or more reasons why the efficiency is typically not quite as good as that. (4 pts.)

   Packetization overhead; double talk; "hang-over" at the end of words and sentences; background noise. [Any two]

9. What are the three components of delay in a WFQ system, besides the propagation delay determined by the speed of light? (You don't have to know their quantitative value, just explain intuitively what they are caused by and what they depend on.) (6 pts.)

   • Buffered packets due to burstiness; depends on bucket depth and rate share.
   • Transmission delay caused by bandwidth share, depends on hop count, bandwidth share and maximum own packet length.
   • Interference by other packets, depends on number of hops and max. length of all packets.

   [2 pts. each; if factors such as bandwidth share, hop count, etc. are listed, 1 pt. each]

10. You are asked to develop a web site containing a listing of students, their interests, year of graduation and such. Give an example of how this might look like in structural or semantic formats, using HTML and XML as appropriate. (Make up XML tags as needed.) Give an example of how CSS would be used for this web page to guide the presentation. (Don't worry about the exact CSS syntax or names of parameters.) (6 pts.)

    A structural/presentation oriented version would use HTML, e.g.,

    <h2>John Doe</h2>
    <dl>
    <dt>School:
    <dd>FUSEAS
    <dt>Year of graduation:
    <dd>2002
    <dt>GPA:
    <dd>2.9
    </dl>
    

    For XML: see class notes.

    <student>
    <school>FUSEAS </school>
    <graduation>2002 </graduation>
    </student>
    

    CSS: see class notes. [2 pts. each for HTML, XML and CSS.]

11. You want to create a home page in both English and Chinese, so that people who have indicated in their web browser which language they prefer will see their desired web page. You only want to "advertise" one URL. Describe how HTTP can be used for this. How are caches impacted? (5 pts.)

    This can be accomplished within HTTP using server-driven Content-negotiation using the HTTP Accept-Language header or 300 Multiple Choices. Caches need to keep track of the Content-Language or ETag field to make sure they return the correct version. Apache, for example, supports having a single URL return two different files.

    As an alternative, cgi-bin scripts could be used to either return the appropriate page or redirect the client to the right URL. The script would read the Accept-Language header and return the appropriate version. However, for appropriate caching, it must set the same Content-Language or ETag fields as in the server-supported solution. Redirects are less appropriate due to the additional round-trip delays.

    JavaScript cannot be used, since it does not provide a good indication of the user's language preferences. It only contains a parameter indicating the language version of the browser. [Also, the question explicitly asked how HTTP can be used.]

    A page with clickable links is not as convenient.

    URNs (together with URCs) could be used, but not in this question.

12. Imagine that a wireless network was installed on the Columbia campus and around Morningside Heights. It is also used to distribute radio programs on and around campus. The radio program uses RTP over UDP. Describe briefly (using diagrams of packet flows and network entities) how you might use (a) SIP and (b) mobile IP to make sure that the "radio" reception is continuous. Please describe both solutions and possible problems they cause. Is there another design approach for this application? (6 pts.)

    Assume first, that this radio program is distributed via unicast, as in today's RealAudio.

    With SIP, the radio receiver would "invite" (using INVITE) the radio station when joining a new subnet (with a new unicast address) and send a BYE request when leaving the subnet. Alternatively, the sender could also use the receiver's RTP reports to discover the new location. Having the radio server issue an invitation is inappropriate since the server doesn't know the identity of radio receivers.

    SIP does not have a "redirect" request (RTSP does). Registration is not helpful, as it only affects new, server-initiated invitations.

    Another design alternative is to announce the radio program using SAP/SDP, and then receive the program using multicast. This requires that join latencies are low enough. Any delay in canceling the transmission will lead to unnecessary traffic in the subnet that the receiver just left.

    Another design alternative would be RTSP, using the REDIRECT request.