CS 218 -Sample Midterm W 99 - Solutions

1. (10) How does slow frequency hopping improve the performance of
a GSM system?

....By shifting to a new frequency every few fractions of a second, 
a station will get out of a "deep fade" condition.

2. (20) Differentiated QoS multicast

A source  transmits a file to a multicast group using a shared
tree approach (eg, sparse mode PIM). Suppose that 10 of the nodes
can receive the file @ 10MBPS, and the other 10 @ 1MBPS. You want to 
minimize average time to complete the file transfer (averaged over all
destinations), subject to the obvious trunk capacity constraints.

(a) Define the optimal transmission policy

...In this case, transmit at 10MBPS first, and if there is
bandwidth left, transmit at rate < = 1MBPS

(b) How can the source get the information necessary to implement
the optimal policy? Assume OSPF (ie, link state) routing.

....With OSPF, each source has full topology information. 
>From each destination, it must find out (via RSVP for example)
the allowed received rate. Then, by allocating the traffic 
requirements on the tree it can determine residual bandwidth and
optimal rates.

(c) Can you generalize the optimal policy to arbitray number
of nodes with multiple receive rate values?

... This is mixed linear-integer programming problem, of difficult
    soluton. A reasonable heuristic is to extend the answer to (a).
    Namely, carry out separate multicasts progressively, favoring
    the high rate destinations (which can be completed fast) and
    the very popular rates (with a lot of users subscribing to them).
    The separate multicasts can be overlapped if bandwidth is
    available.

3.(20)(a) Explain how deflection routing prevents switch buffer overflow 
   if switches have same number of inputs as outputs, no matter how
   high the offered load is.

...With IN = OUT ports there is never queueing (and therefore
   overflow) at a switch. If two inputs request the same output,
   one of them is randomly routed to a "wrong" output.

  (b) Next, explain how Myrinet avoids buffer overflow at heavy
   load. 

.... In myrinet buffer overflow is prevented by backpressure
   (from switch to source).

  (c) How do Myrinets and deflection routing nets (eg, Manhattan
    network) avoid deadlocks?

.... In myrinet deadlocks are avoided with up-down routing. In
deflection routing nets, there are no deadlocks, just livelocks,
which are avoided using random output selection.


4.(20) Why is deflection routing more appropriate than conventional
   P/S in a multihop optical network with "all-optical" switching
   (no electronics)?

....Not easy to implement store-and-forward buffers all in optics.
While it is relatively easy to implement on-the-fly transfers in
optics.
 

5. (20) Why is it more difficult to implement "fair queueing" in a
   broadcast channel (such as a wireless channel) than in a wired
   channel?

...The queue is a "distributed" queue. Neighboring nodes do not
know the lenght of their respective queues, thus cannot properly
schedule packet tx, unless they exchange such info (with a token
protocol, for example).

6. (10) Pros and cons of on-demand vs table driven routing in
   wireless nets

On-demand scales better to large nets (with sparse demands); ie.
less line and processing O/H. However, On-demand introduces
latency on first message of a file transfer (since path must be
found on-demand); also, no notion of QoS or connectivity available
from the network before connection has been set up.