Networking Area Examination -- Spring 2000

This exam consists of 8 questions. Please answer exactly six of them. Typed answers are preferred, but don't spend a lot of time typesetting equations, etc. -- hand-written equations are fine.

If you have questions during the exam, please contact Mostafa Ammar ammar@cc.gatech.edu, (404) 894-3292 (office), (770) 493-4592 (home).

1. This question concerns modeling the topological structure of the Internet.
   1. Is the transit-stub method for generating topologies capable of producing graphs in which some nodes have high degree and others have low degree? Explain.
   2. Describe a modification to the transit-stub method that allows the inclusion of network exchange points. An exchange point is a node where multiple transit domains peer, for example on a high-speed ring.

2. This question concerns the host anycasting service, as defined in RFC 1546.
   1. Why does the service definition state that delivery is to "at least one host, and preferably only one host, which serves the anycast address"?
   2. What would be necessary for the service to provide delivery to "exactly one host"?

3. Provide a concise definition of `soft-state''. Describe an efficient implementation of a soft-state storage system. Why is soft-state used in many network protocols?

4. Queueing Models
   1. For the same arrival and service rates, rank the following models as far as average system delay performance: M/M/1, M/E2/1, and M/D/1? Is such performance affected by the queueing discipline (e.g., FCFS, LCFS) being used? Explain your answer?
   2. What is `Kleinrock's Independence Assumption" and why is it necessary to make when modeling a packet switched network with a queueing network model?

5. Consider packets arriving from 11 connections to be transmitted on a link. Connection 1 is allocated 0.5 of the link's bandwidth and connections 2-11 are allocated 0.05 of the link's bandwidth. Assuming all packets from all connections are the same length and that our unit of time is the time it takes to transmit one packet on this link.

   Consider the following packet arrival patterns:

   • Connection 1: Packets arrive at times 0,1,2,3,4,6,8,10,12,14
   • Connection 2: packets arrive at times 0,2
   • Connections 3-11: on each connection one packet arrives at time 0.

   For the following scheduling disciplines determine, the order of service of the packets:

   1. Fluid Fair Queuing (or Bit by bit Fair Queueing)
   2. Weighted Fair Queueing
   3. Virtual Clock
   4. Self Clocked Fair Queueing

   Explain the reasoning behind your answer.

6. The reuse of existing unicast routing protocols to support multicast routing protocols was first viewed as a desrieable feature. Later it was argued that it was not desireable.
   1. Explain, with appropriate reference to the literature, the arguments on both sides of this issue.
   2. Do the same arguments apply to unicast state (i.e., routing tables) or only to unicast protocols.

7. TCP
   1. Explain how the throughput of a TCP connection varies as function of the Round Trip Time (RTT) experienced by the connection.
   2. What other factor(s) may affect TCP's throughput?
   3. With appropriate reference to the literature, describe an architecture that allows TCP's throughput to be less dependent on the RTT? Is this architecture sucessful in completely removing this RTT dependence? why or why not?

8. Video Communication
   1. What are the factors that can affect the bit rate at the output of an MPEG coder? How is the bit rate affected by changes to these factors?
   2. Explain the following sentence that is taken out of the MPEG paper by LeGall (end of page 52): `There is a trade-off between the coding gain provided by the motion information and the cost associated with coding the motion information.''
   3. Consider a unicast path from a video source to a video receiver with variable losses running as high as 10% for streams running at 10 Mbps.

      We have two options for transmitting the video

      1. A single 10Mbps video stream from source to receiver, or
      2. Two layers of video: `base" at 9Mbps and `enhancement" at 1Mbp s.

      Describe the network context in which the second option above would be preferrable.