Description

A mix of video on demand and data packets arrive at a router along a high bandwidth link. The router has to schedule them to a home client through a low bandwidth link (512 kbps or 64 kbytes per second). The data packets are somewhat sensitive to delay (not more than 30 seconds delay permitted) while the video on demand is very delay sensitive (max of 1 second delay is acceptable) and arrive at a rate of 48 kbytes per second. The data packets are 1024 bytes in size, while the video packets are 512 bytes long. You are to keep dropped video packet rates to below 5% every second (your algorithm should take this into account), and can drop data packets but should minimize the number dropped. Dropped packets are retransmitted, which increases the bandwidth required at a later time.

For the problem on hand, the queue is empty and a 512 kbyte burst of data packets arrives at t =0 and has to be scheduled. Further data packets arrive at the middle of each second, of size 6 kBytes (plus retransmitted packets dropped previous second). Video packets arrive at fixed intervals starting at t =0⁺ (just after the arrival of data packets).

Video

The figure above shows when data and video packets arrive. The queue size is very large and it does not overflow.

1. Suppose we only have the video packets and the periodic data pack- . . . . . . . . . . . . . . . . . [10] ets, but no initial burst of data packets. Design a FIFO queue into which all the packets are inserted as they arrive. Give pseudocode for the queue. There is a period of waiting, and a period of transmission. Include both to compute the delay for each type packet. Assuming packets come out in the order they arrive, what % of dropped packets of each type (data or video) will there be over the first 30 seconds? Does this meet requirements?

1

2. Suppose the burst of data packets at t =0 also happened. How does . . . . . . . . . . . . . . . . . [10] your answer change if you consider the first 30 seconds? How does retransmission of dropped data packets affect your answer?
3. Suppose at entry, video packets are always inserted at “front” of . . . . . . . . . . . . . . . . . [10] the queue, while the data packets are inserted at the “end” (queue length is unlimited, which means here “very large”). The order of packets in the queue should be preserved for video packets (i.e., first one received should be the first one dequeued. Give pseudocode for this and discuss if it will work. Which type of queue is best? What is the value function that ensures video packets are queued in front? What % of dropped packets of each type will there be over the next 30 seconds?
4. Create the program that implements Q2 and Q3. The program . . . . . . . . . . . . . . . . . [20] should create output to show the status at the end of each second as follows:

where “Condn” is the condition you used to decide whether to drop video packets, HTTP is the number of kBytes of HTTP sent this second, and Video is the number of kBytes of Video sent this second.