ECE/CS 438  Communication Networks
Fall 2008

Homework 7

Assigned on November 12, 2008
Due by class time on November 19, 2008

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

Consider a wired link from host A to host B with rate 1 Kbps,
and a link from B to C at the rate of 2 Kbps.

Suppose that flows 1 and 2 originate at node A,
and flow 3 originates at node B. All flows are destined for node C.
Packets shown below arrive at these three flows -- no other packets
are sent in this network. Suppose that the weights of flows 1, 2 and
3 are 1, 2 and 1, respectively (the same wait is used for a given flow
when competing for each link on its route).
Packets on flow 1 and 2 are routed via node B to node C.


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

       1                   2000               0
       2                   1000               1
       3                   4000               1
       1                   2000               2

The packets within each flow are served in a FIFO manner. 
For each of the following schedulers, determine the time at which
each of the above packets will be completely received at node C.

(1) GPS scheduler

(2) PGPS scheduler

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

(3) In a Banyan network with 8 inputs and 8 outputs, show how a packet
    is routed from input port 000 to output port 111. You may print 
    the network from the slides at
    http://www.cs.uiuc.edu/class/fa07/cs438/slides/CS438-09.Switches.ppt

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

(4) Consider an input-queued 4x4 cross-bar switch. Time is measured in slots,
    and one or zero frame may arrive at each input port in each slot.
    Also, one or zero frame may be transferred to any output port in any
    slot. Suppose that the following cells (or frames) arrive:

    Frames arriving in slot i can be scheduled for transmission 
    only in slot i+1 or higher.
    

      arrives on      destined for
      input port      output port     arrival time 

        1                1                0
        2                1                0

        1                1                1
        2                1                1

        1                1                2
        2                1                2
        3                2                2                

        3                1                1
        4                1                2



    Assume that at each input port, a queue is maintained for cells
    destined for each output port. Each arriving cell is added to the
    queue corresponding to its destination port.

    Suppose that the switch uses the "max-weight" policy, which
    chooses a schedule such that the weight of queues from which
    cells are scheduled for transmission is maximized. Ties are
    broken arbitrarily. Assume that
    weight of a queue in slot i is the queue size (excluding new
    arrivals in slot i and excluding departures in slot i).
    Note that in a valid schedule scheduled a conflict should not
    be present -- a conflict occurs if
    we attempt to transmit more than one cell from a single input port,
    or attempt to transmit more than one cell to a single output
    port in the same slot).

    Determine the slot numbers in which cells from input ports 3 and 4
    are transferred to output port 1 (the last 2 cells in the table above).

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

(5) Consider an M/M/1 system with packet arrival rate of 10 packets/second,
    and average packet transmission time of 50 ms. Estimate the
    average number of packets in the system at a given time.
    Estimate the average waiting time in the queue for each packet.
    State any assumptions you have to make to apply the M/M/1 results
    in the context of this problem.

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