CS E6181: Advanced Internet Services

Spring 2000 Final Exam

This is an open-book exam. You have 150 minutes to complete the exam. Please make sure that the problems appear in numerical order in your "blue book", with each problem starting on a new right page. Points are given in [].

1. [10] You are asked to provide seating for the students waiting in the mail pickup counter in Lerner Hall. Assume that students arrive at a rate of one student every minute and that it takes the clerk 40 seconds to fetch the parcel, with students arriving as a Poisson process and requiring exponentially distributed service time. On average, how many students are waiting in line and how long does a student have to wait? (Hint: compute the time-in-system T).

   This is an example for an M/M/1 queue with arrival rate lambda = 1/60 = 0.0167 and service rate mu = 1/40 = 0.025. Thus, the system time T = 1/(0.025 - 0.0167) = 120.5 s. According to Little's Law, the number in system is then N = lambda T = 2. However, this includes the student being helped, so we compute the waiting time as 120.5 s - 40 s = 80.5 s, yielding a waiting line length of 1.34. (Note that this is not just one less than the number in system.)

2. [6] We have seen leaky buckets in a variety of applications. Name three actions that a leaky bucket can take. Where would each of these actions be appropriate?

   mark packets	diff-serv three-color marker
   delay packets	edge shaping (within host)
   drop packets	protection in network

3. [4] What are the advantages and disadvantages of using RTP-over-TCP to carry (a) video-on-demand, (b) Internet phone calls, compared to RTP-over-UDP? (Name at least two advantages/disadvantages each.)

   	TCP	UDP
   video-on-demand	+: bandwidth-adaptive, delays and packet header size (since payload is bigger) don't much matter, reliable, works through firewalls; -: rate averaging may cause receiver starvation	+: avoid receiver starvation; -: no congestion control
   Internet phone calls	-: longer delays due to retransmission; +: easier to get through firewalls; compensates for packet losses	+: lower packet-header overhead, no delays imposed by retransmission or flow/congestion control; -: needs application-layer reliability;

4. [10] Consider the packet arrival sequence below, consisting of two talkspurts. These are PCMU (mu-law) RTP packets, with transmission starting at time 10.00.

   RTP sequence number	RTP timestamp	network delay (seconds)
   1	160	0.4
   2	320	0.3
   3	480	0.35
   4	800	0.32
   5	960	0.27
   6	1120	0.45

   Show a timeline as to when the packets are played out at the receiver. Your "algorithm" should minimize the end-to-end delay (a) without losing any packets, (b) while being allowed to drop one packet. Your algorithm can be non-causal, i.e., may look ahead in time. Compute the delay for the two cases.

   The sampling and RTP clock rate is 8000 Hz, with each 160 RTP clock units corresponding to 0.02 s. Thus, we have, assuming that the first packet is transmitted at time zero:

   RTP sequence number	RTP timestamp	network delay (seconds)	arrival time	playout time, with no loss	playout time, with one loss
   1	160	0.40	0.40	0.40	0.40
   2	320	0.30	0.32	0.42	0.42
   3	480	0.35	0.39	0.44	0.44
   4	800	0.32	0.40	0.53	0.40
   5	960	0.27	0.37	0.55	0.42
   6	1120	0.45	0.57	0.57	drop

   The packets with sequence numbers 4, 5 and 6 are part of the second talkspurt, as can be seen by the jump in timestamp. If there is no loss allowed, the average delay is (3*0.40 + 3*0.45)/6 = 0.425 s. If we drop one packet, we can decrease the delay to (3*0.40 + 2*0.08)/5 = 0.272 s.

5. [10] Instead of transmitting music via analog FM radio, we want to send MP3's, digitally modulated, across the same radio band. Assume that we need an SNR of 10 dB and that each channel is 200 kHz wide. What is the maximum bandwidth that we can squeeze into one FM station?

   Shannon's channel capacity can be computed as

   C = B log2 (1 + S/N)
   

   Here, the S/N ratio is 10, for C = 200 kHz log₂ 11 = 200 kHz * 3.46 = 692 kb/s. Thus, we can easily fit (several) MP3 streams, at about 56 to 128 kb/s, into the existing analog channel, assuming that our channel coding scheme comes close to the Shannon limit.

6. [8] Sketch the SIP INVITE request, with SDP, when you call up gore@whitehouse.gov from your office.

   INVITE sip:gore@whitehouse.gov SIP/2.0
   To:      Al Gore <sip:gore@whitehouse.gov>
   From:    Henning Schulzrinne <sip:hgs@cs.columbia.edu>
   Call-ID: 1234@bart.cs.columbia.edu
   CSeq:    1 INVITE
   Via:     bart.cs.columbia.edu
   Content-Type: application/sdp
   Content-Length: 50
   
   v=0
   c=IN IP4 128.59.19.191
   m=audio 3456 RTP/AVP 0
   

7. [6] Name two advantages and two disadvantages of proxying (vs. redirecting) SIP requests.

   	proxy	redirect
   advantage	hide callee address; may hide caller address; lower delay	caller gets choice as to whether to go to forwarded address
   disadvantage	proxy is more complicated than redirect server	delay, exposure of addresses

8. [6] How is RTSP similar to HTTP? How is RTSP different from HTTP? Can HTTP be used to request a stream? Which is in-band vs. out-of-band? How much state is maintained between requests in each protocol?

   RTSP is similar to HTTP in its message format, i.e., the use of request line, headers a message body. It differs from HTTP in:

   • character set (UTF-8 vs. ISO 8859-1);
   • state maintenance: HTTP is stateless except through cookies, while RTSP sets up a session via SETUP;
   • in-band vs. out-of-band: HTTP sends data in-band, i.e., through the same TCP connection as the request, while RTSP generally sets up one or more external (UDP) channels for media data;
   • different methods;
   • HTTP only uses TCP, while RTSP can also use UDP.

9. [10] Suppose that the WFQ scheduling policy is applied to a buffer that supports three classes, with weights 0.5, 0.25 and 0.25. Each class has a large number of packets in the buffer. The packets in the first class are 100 bytes long, the packets in the other classes 300 bytes. In what order might the scheduler serve the packets? Specify the class sequence, e.g., 1 2 3 1 2 3...

   It is easiest to compute the sequence by looking that the GPS departure times and scheduling time in slots of 100 bytes. The first stream, for example, needs to get half the "slots", while the other two streams needs to get 3 out of 12 slots. Thus, a virtual time sequence for the first stream could be 2, 4, 6, 8, ..., while for the second class 6.1, 18.1, 30.1, ..., and for the third class 12.2, 24.2, 36.2, ... The fractions and offsets are arbitrary and are simply chosen to avoid having to worry about what to do with two packets having the same virtual departure time.

10. [10] Reverse path forwarding: Consider the topology and link costs below and suppose that node E is the multicast source. Using arrows to indicate flows, with "-->|" indicating a packet that is not forwarded beyond the receiving router, indicate links over which packets will be forwarded using RPF, and links over which packets will not be forwarded, given that node E is the source.

    

11. [8] The audio and video stream shown below need to be lip-synched. The figure shows the timing in the sender report. For simplicity, assume that the network has no jitter, so that the packets arrive, somewhat delayed, at the receiver. The delay for both audio and video packets is the same. (Is this a realistic assumption?) What audio packet should be played out when the video frame with timestamp 9000 is being displayed? Justify your answer!

    For the video stream, RTP ts 1800 corresponds to 17.18 s real-time, so that RTP ts 9000 corresponds to 17.26 s real-time. (Recall that RTP video stream clocks tick at 90,000 Hz.) For the audio stream, timestamp 560 corresponds to 17.23 s. 17.26 s is thus 30 ms away, or 240 timestamp units. Thus, the audio packet with timestamp 800 needs to be played out together with the video frame with timestamp 9000.

    It is not a realistic assumption that audio and video frames experience the same delay. For example, video frames are usually substantially longer than audio frames, so that the transmission time is longer. (Video frames typically occupy a whole packet of 1500 bytes, while low-rate audio frames are typically less than 200 bytes long.)

12. [4] If you were to listen to the error signal transmitted for an ADPCM codec, what would you hear? (E.g., a reduced-volume version of the input signal?)

    Roughly white noise, if the predictor is good.

13. [8] You are given a 16-bit digital signal, as found on an audio CD. You re-code the result into 8-bit samples at 8 kHz sampling rate. How many dB of noise are you adding, how much dynamic range are you sacrificing and how much frequency range are you losing? (Samples are evenly distributed across the value range; the 8-bit encoding is linear.)

    An 8-bit signal has a dynamic range of 256:1 or 48 dB. A CD has a dynamic range of 96 dB.

    Noise: All 16-bit values between -128 and 127 will be translated to the 8-bit value of 0, with an average error of 64. The average absolute value of the signal is 16,384, assuming uniform distribution of samples (which is not strictly correct). This leads to a signal/noise ratio of 10 log₁₀ 16,384² / 64² = 48 dB, or a loss of 48 dB compared to the CD. (You could arrive at this simply by subtracting the two range values above.)

    The frequency range decreases from about 20 kHz to about 3.4 kHz. (It's not quite half the sampling rate due to imperfect roll-off of the anti-aliasing filters.)