P1. Consider the figure below. Similar to our discussion of Figure 9.1 , suppose that video is encoded at a fixed bit rate, and thus each video block contains video frames that are to be played out over the same fixed amount of time, Δ. The server transmits the first video block at t₀, the second block at t0+Δ, the third block at t0+2Δ, and so on. Once the client begins playout, each block should be played out Δ time units after the previous block.

Description

In this graph, the x-axis is labeled "Time" and the y-axis is labeled "Video block number." The y-axis omits 0 but moves upwards in increments of one to 9. In the left half of the x-axis we see a blue line rising upwards to the right in a stair-step fashion. This line is labeled "Constant bit rate video transmission by server." It begins at a point labeled "t0." The line rises to 1 on the y-axis then extends horizontally to the right for one unit defined as Delta. It then goes up to 2 and over one Delta, etc. until it reaches 7 on the y-axis.

In the right half of the x-axis we see a dark blue line, labeled "Video reception at client," rise from a point labeled t1 and extend upward to the right in an inconsistent fashion. The x-axis is delineated from this point into units of Delta. This line rises to 1 on the y-axis and then extends horizontally for one and a half Deltas. It rises to 2 and extends into the next Delta. Then it rises to 3 and extends within the same Delta, then rises to 4 and extends just barely into the next Delta. From here it rises to 5 and extends through the Delta and halfway into the next Delta. From here it rises to 6 and extends three Deltas, then rises to seven.

1. Suppose that the client begins playout as soon as the first block arrives at t₁. In the figure below, how many blocks of video (including the first block) will have arrived at the client in time for their playout? Explain how you arrived at your answer.

2. Suppose that the client begins playout now at t1+Δ. How many blocks of video (including the first block) will have arrived at the client in time for their playout? Explain how you arrived at your answer.

3. In the same scenario at (b) above, what is the largest number of blocks that is ever stored in the client buffer, awaiting playout? Explain how you arrived at your answer.

4. What is the smallest playout delay at the client, such that every video block has arrived in time for its playout? Explain how you arrived at your answer.

P2. Recall the simple model for HTTP streaming shown in Figure 9.3 . Recall that B denotes the size of the client’s application buffer, and Q denotes the number of bits that must be buffered before the client application begins playout. Also r denotes the video consumption rate. Assume that the server sends bits at a constant rate x whenever the client buffer is not full.

1. Suppose that x<r. As discussed in the text, in this case playout will alternate between periods of continuous playout and periods of freezing. Determine the length of each continuous playout and freezing period as a function of Q, r, and x.

2. Now suppose that x>r. At what time t=tf does the client application buffer become full?

P3. Recall the simple model for HTTP streaming shown in Figure 9.3 . Suppose the buffer size is infinite but the server sends bits at variable rate x(t). Specifically, suppose x(t) has the following saw-tooth shape. The rate is initially zero at time t=0 and linearly climbs to H at time t=T. It then repeats this pattern again and again, as shown in the figure below.

Description

In this graph, the x-axis is labeled "Time" and the y-axis is labeled "Bit rate x(t)." The x-axis is divided at regular intervals into T, 2T, 3T, and 4T. The y-axis is unmarked except for an H near its top.

A blue line begins at the intersection of x and y and rises sharply to H on the y-axis at T on the x-axis, then drops vertically to the x-axis. From here it rises sharply to H on the y-axis and 2T on the x-axis, then drops vertically to the x-axis. This pattern is repeated twice more.

1. What is the server’s average send rate?

2. Suppose that Q=0, so that the client starts playback as soon as it receives a video frame. What will happen?

3. Now suppose Q>0 and HT/2≥Q. Determine as a function of Q, H, and T the time at which playback first begins.

4. Suppose H>2r and Q=HT/2. Prove there will be no freezing after the initial playout delay.

5. Suppose H>2r. Find the smallest value of Q such that there will be no freezing after the initial playback delay.

6. Now suppose that the buffer size B is finite. Suppose H>2r. As a function of Q, B, T, and H, determine the time t=tf when the client application buffer first becomes full.

P4. Recall the simple model for HTTP streaming shown in Figure 9.3 . Suppose the client application buffer is infinite, the server sends at the constant rate x, and the video consumption rate is r with r<x. Also suppose playback begins immediately. Suppose that the user terminates the video early at time t=E. At the time of termination, the server stops sending bits (if it hasn’t already sent all the bits in the video).

1. Suppose the video is infinitely long. How many bits are wasted (that is, sent but not viewed)?

2. Suppose the video is T seconds long with T>E. How many bits are wasted (that is, sent but not viewed)?

P5. Consider a DASH system (as discussed in Section 2.6 ) for which there are N video versions (at N different rates and qualities) and N audio versions (at N different rates and qualities). Suppose we want to allow the player to choose at any time any of the N video versions and any of the N audio versions.

1. If we create files so that the audio is mixed in with the video, so server sends only one media stream at given time, how many files will the server need to store (each a different URL)?

2. If the server instead sends the audio and video streams separately and has the client synchronize the streams, how many files will the server need to store?

P6. In the VoIP example in Section 9.3 , let h be the total number of header bytes added to each chunk, including UDP and IP header.

1. Assuming an IP datagram is emitted every 20 msecs, find the transmission rate in bits per second for the datagrams generated by one side of this application.

2. What is a typical value of h when RTP is used?

P7. Consider the procedure described in Section 9.3 for estimating average delay d_i. Suppose that u=0.1. Let r1−t1 be the most recent sample delay, let r2−t2 be the next most recent sample delay, and so on.

1. For a given audio application suppose four packets have arrived at the receiver with sample delays r4−t4, r3−t3, r2−t2, and r1−t1. Express the estimate of delay d in terms of the four samples.

2. Generalize your formula for n sample delays.

3. For the formula in part (b), let n approach infinity and give the resulting formula. Comment on why this averaging procedure is called an exponential moving average.

P8. Repeat parts (a) and (b) in Question P7 for the estimate of average delay deviation.

P9. For the VoIP example in Section 9.3 , we introduced an online procedure (exponential moving average) for estimating delay. In this problem we will examine an alternative procedure. Let t_i be the timestamp of the ith packet received; let r_i be the time at which the ith packet is received. Let d_n be our estimate of average delay after receiving the nth packet. After the first packet is received, we set the delay estimate equal to d1=r1−t1.

1. Suppose that we would like dn=(r1−t1+r2−t2+⋯+rn−tn)/n for all n. Give a recursive formula for d_n in terms of dn−1, rn, and t_n.

2. Describe why for Internet telephony, the delay estimate described in Section 9.3 is more appropriate than the delay estimate outlined in part (a).

P10. Compare the procedure described in Section 9.3 for estimating average delay with the procedure in Section 3.5 for estimating round-trip time. What do the procedures have in common? How are they different?

P11. Consider the figure below (which is similar to Figure 9.3 ). A sender begins sending packetized audio periodically at t=1. The first packet arrives at the receiver at t=8.

Description

In this graph, the x-axis is labeled "Time" and the y-axis is labeled "Packets." The x-axis begins at 0 and moves at regular intervals in increments of one to sixteen. Only 1 and 8 are actually numbered. The y-axis is also is notched at eight regular intervals, though these are not labeled.

At 1 on the x-axis, a line extends upwards to the right in a stair-step fashion. It rises to 1 on the y-axis then over to 2 on the x-axis, then up to 2 on y and 3 on x, etc. to the top of the graph. This line is labeled "Packets generated."

At 8 on the x-axis, a line extends upwards to the right in an inconsistent stair-step fashion. It rises to 1 on the y-axis then extends horizontally over to 9 on the x-axis. From there it rises to 2 on the y-axis and extends to 12 on the x-axis. From there it rises to 5 on the y-axis and extends to 15 on the x-axis. From there it rises to 7 on the y-axis and extends to 16 on the x-axis, then rises to 8 on the y-axis

1. What are the delays (from sender to receiver, ignoring any playout delays) of packets 2 through 8? Note that each vertical and horizontal line segment in the figure has a length of 1, 2, or 3 time units.

2. If audio playout begins as soon as the first packet arrives at the receiver at t=8, which of the first eight packets sent will not arrive in time for playout?

3. If audio playout begins at t=9, which of the first eight packets sent will not arrive in time for playout?

4. What is the minimum playout delay at the receiver that results in all of the first eight packets arriving in time for their playout?

P12. Consider again the figure in P11, showing packet audio transmission and reception times.

1. Compute the estimated delay for packets 2 through 8, using the formula for d_i from Section 9.3.2 . Use a value of u=0.1.

2. Compute the estimated deviation of the delay from the estimated average for packets 2 through 8, using the formula for v_i from Section 9.3.2 . Use a value of u=0.1.

P13. Recall the two FEC schemes for VoIP described in Section 9.3 . Suppose the first scheme generates a redundant chunk for every four original chunks. Suppose the second scheme uses a low-bit rate encoding whose transmission rate is 25 percent of the transmission rate of the nominal stream.

1. How much additional bandwidth does each scheme require? How much playback delay does each scheme add?

2. How do the two schemes perform if the first packet is lost in every group of five packets? Which scheme will have better audio quality?

3. How do the two schemes perform if the first packet is lost in every group of two packets? Which scheme will have better audio quality?

P14.

1. Consider an audio conference call in Skype with N>2 participants. Suppose each participant generates a constant stream of rate r bps. How many bits per second will the call initiator need to send? How many bits per second will each of the other N−1 participants need to send? What is the total send rate, aggregated over all participants?

2. Repeat part (a) for a Skype video conference call using a central server.

3. Repeat part (b), but now for when each peer sends a copy of its video stream to each of the N−1 other peers.

P15.

1. Suppose we send into the Internet two IP datagrams, each carrying a different UDP segment. The first datagram has source IP address A1, destination IP address B, source port P1, and destination port T. The second datagram has source IP address A2, destination IP address B, source port P2, and destination port T. Suppose that A1 is different from A2 and that P1 is different from P2. Assuming that both datagrams reach their final destination, will the two UDP datagrams be received by the same socket? Why or why not?

2. Suppose Alice, Bob, and Claire want to have an audio conference call using SIP and RTP. For Alice to send and receive RTP packets to and from Bob and Claire, is only one UDP socket sufficient (in addition to the socket needed for the SIP messages)? If yes, then how does Alice’s SIP client distinguish between the RTP packets received from Bob and Claire?

P17. Consider the figure below, which shows a leaky bucket policer being fed by a stream of packets. The token buffer can hold at most two tokens, and is initially full at t=0. New tokens arrive at a rate of one token per slot. The output link speed is such that if two packets obtain tokens at the beginning of a time slot, they can both go to the output link in the same slot. The timing details of the system are as follows:

1. Packets (if any) arrive at the beginning of the slot. Thus in the figure, packets 1, 2, and 3 arrive in slot 0. If there are already packets in the queue, then the arriving packets join the end of the queue. Packets proceed towards the front of the queue in a FIFO manner.

2. After the arrivals have been added to the queue, if there are any queued packets, one or two of those packets (depending on the number of available tokens) will each remove a token from the token buffer and go to the output link during that slot. Thus, packets 1 and 2 each remove a token from the buffer (since there are initially two tokens) and go to the output link during slot 0.

3. A new token is added to the token buffer if it is not full, since the token generation rate is r = 1 token/slot.

4. Time then advances to the next time slot, and these steps repeat.

Answer the following questions:

1. For each time slot, identify the packets that are in the queue and the number of tokens in the bucket, immediately after the arrivals have been processed (step 1 above) but before any of the packets have passed through the queue and removed a token. Thus, for the t=0 time slot in the example above, packets 1, 2, and 3 are in the queue, and there are two tokens in the buffer.

2. For each time slot indicate which packets appear on the output after the token(s) have been removed from the queue. Thus, for the t=0 time slot in the example above, packets 1 and 2 appear on the output link from the leaky buffer during slot 0.

P18. Repeat P17 but assume that r=2. Assume again that the bucket is initially full.

P19. Consider P18 and suppose now that r=3 and that b=2 as before. Will your answer to the question above change?

P20. Consider the leaky bucket policer that polices the average rate and burst size of a packet flow. We now want to police the peak rate, p, as well. Show how the output of this leaky bucket policer can be fed into a second leaky bucket policer so that the two leaky buckets in series police the average rate, peak rate, and burst size. Be sure to give the bucket size and token generation rate for the second policer.

P21. A packet flow is said to conform to a leaky bucket specification (r, b) with burst size b and average rate r if the number of packets that arrive to the leaky bucket is less than rt+b packets in every interval of time of length t for all t. Will a packet flow that conforms to a leaky bucket specification (r, b) ever have to wait at a leaky bucket policer with parameters r and b? Justify your answer.

P22. Show that as long as r1<Rw1/(∑ wj), then d_max is indeed the maximum delay that any packet in flow 1 will ever experience in the WFQ queue.