ECE/CS 438  Communication Networks
Fall 2008

Homework 6

Assigned on October 29, 2008
Due by class time on November 7, 2008

------------------------------------------------------------------------

Consider a wired link from host A to host B with rate 100 Kbps.
Suppose that traffic from three flows numbered 1, 2 and 3 is to be
scheduled for transmission on this link.

Suppose that only the packets shown below arrive on the three flows.


    flow number         packet size      arrival time ("real" time)
                            (bits)            (millisecond)

       1                   1000               0
       3                   200                1
       2                   1000               2
       1                   500                6                  
       3                   500                8

    The packets within each flow are served in a FIFO manner. 
    Consider two schedulers.
    
(1) A round-robin scheduler, which inspects the flows
        in the order 1, 2, 3 repeatedly.

(2) PGPS scheduler assuming that the weight of flows 1 is 2,
	and that the weight of flows 2 and 3 is 1.
        In case of a tie, the scheduler prefers the flow with the smaller
        flow number.

    In each case above, determine the schedule, and plot the
    "service curves" as in Figure 1 of the paper
    "A generalized processor sharing approach to flow control in
    integrated services networks: the single-node case". A link to
    the paper is  posted on the Lecture Summary page for Lecture 27
    (lecture on 10/27/2008) at
    http://www.crhc.uiuc.edu/~nhv/438.fall08/lectures.html
    Note that the Ai(0,t) curve plots the cumulative transmission time
    of the data received on flow i until time t (that is, total amount
    of data divided by the link rate), and Si(0,t) curve plots the
    total amount of time spent for transmitting data from flow i
    until time t.

--------------------------------------------------------------------

Consider a link from host A to host B with rate 10 Mbps
and propagation delay 50 ms.
Assume that a single TCP connection is set up between A and B,
with data being sent from A to B. There is no other traffic on the
network. TCP data packet size is 1000 bytes.

Since the packet transmission time is small compared the propagation
delay, you may ignore the transmission time when your presenting
your answers to the questions below.

A timeout has just occurred at the TCP sender, while waiting for
acknowldgement for the packet containing data sequence numbers
20000:20999. The "first" packet that the sender will now transmit
is 20000:20999.
The new retransmission timeout interval is
4 second.  The congestion window following the timeout is 1000 bytes
(assume that 1 MSS is equal to 1000 bytes). All previously transmitted
data packets have either been acknowledged or lost.

Assume that the receiver consumes the received data quickly,
so the receiver's advertized window is always more than 32 Kbytes. 
Assume that the TCP sender always has data waiting to be sent.

For both (3) and (4) below,

   (i) Draw a timeline up to the point where the TCP sender receives
    acknoledgement for the K bytes of data, where K is specified in
    each question. For the timeline, use a format similar to
    to Figure 6.12 in the textbook -- for each packet transmission or
    receipt event, show the time at which the event occurs (you can
    approximate the event time, by ignoring the transmission time as
    mentioned above).  

    (ii) Plot the congestion window (cwnd) as a function of time,
     similar to Figure 6.9 in the textbook.  

(3) K = 6000.
    The CongestionThreshold or Slow Start Threshold is 6000 bytes.
    The first retransmission of data packet 20000:20999 is lost.
    There are no further losses.

(4) K = 9000
    The CongestionThreshold or Slow Start Threshold is 16000 bytes.
    Assume that the TCP receiver does NOT use a delayed acknowledgement
    mechanism.
    Data packet 24000:24999 is lost when first transmitted. There are
    no other losses.
          Hint: Does the TCP source perform fast recover in this case?

Notation clarification: Data packet 24000:24999 contains 1000 data bytes
	with sequence numbers 24000 through 24999.

--------------------------------------------------------------------

Suggested exercise (you need not turn in the solution for this):
---------

    In question (2) above, what if some of the packets are lost
	when transmitted on the link ?  How might we modify the
	scheduler to take into accont the packet losses ?
	(assume that node A can detect the packet loss)

--------------------------------------------------------------------