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).
0sec 5 sec 10 sec t (sec)
Data
512kB
Data
6kB
0 0.1
packets Video
512 bytes
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 packets, 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?
. . . . . . . . . . . . . . . . . [10]
1
2. Suppose the burst of data packets at t = 0 also happened. How does
your answer change if you consider the first 30 seconds? How does
retransmission of dropped data packets affect your answer?
. . . . . . . . . . . . . . . . . [10]
3. Suppose at entry, video packets are always inserted at “front” of
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?
. . . . . . . . . . . . . . . . . [10]
4. Create the program that implements Q2 and Q3. The program
should create output to show the status at the end of each second as
follows:
Time Q Length Time Condn HTTP Video HTTP Drops Video Drops
0 512 0 ? ? ? ? ?
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.
