ECS 122 - COMMUNICATION NETWORKS - Spring 2003
Midterm - SOLUTIONS
1. Multiple Choice [40%]
(Check all the boxes that correspond to a correct answer, if
any.)
1.1. [4%] A world-wide layer 2 network is not feasible with no layer 3 because
|
a. The bandwidth of the links is too small |
[ ] |
|
b. Layer 2 switches don't have enough memory for data packets |
[ ] |
|
c. The headers are too long |
[ ] |
|
d. The flat address space leads to unmanageable forwarding tables |
[X] |
1.2 [4%] In IP, a router
|
a. Retransmits packets that are not acknowledged in time |
[ ] |
|
b. Drops packets whose data is corrupted |
[ ] |
|
c. Drops packets when they become congested |
[X] |
|
d. Sends back 3DAs to tell the sources to slow down |
[ ] |
1.3 [4%] The functions that UDP adds to IP are
|
a. Retransmission of erroneous packets |
[ ] |
|
b. Detection of erroneous packets |
[X] |
|
c. Multiplexing of transmissions to and from other applications |
[X] |
|
d. Flow and congestion control |
[ ] |
1.4 [4%] HTTP 1.1
|
a. Is a transport layer protocol |
[ ] |
|
b. Establishes TCP connections faster than HTTP 1.0 |
[ ] |
|
c. Utilizes a proxy cache more effectively than HTTP 1.0 |
[X] |
|
d. Establishes fewer TCP connections than HTTP 1.0 |
[X] |
1.5 [4%] CIDR (classless interdomain routing) is designed to
|
a. Provide fair service across different classes of traffic |
[ ] |
|
b. Regulate the flow of traffic between domains |
[ ] |
|
c. Improve the utilization of the IP address space |
[X] |
|
d. Speed up the table lookups that routers perform |
[ ] |
1.6 [4%] Fast retransmit is intended to
|
a. Increases the bandwidth of router links |
[ ] |
|
b. Retransmit a missing packet without waiting for a timeout |
[X] |
|
c. Increase the transmission rate of links |
[ ] |
|
d. Modify the increase rate in AIMD |
[ ] |
1.7 [4%] The IP routing is decomposed into intradomain and interdomain routing
|
a. Because a flat address space is not scalable |
[ ] |
|
b. To limit the waste of IP addresses |
[ ] |
|
c. Because there are different routing objectives to satisfy |
[X] |
|
d. To optimize the links utilization |
[ ] |
1.8 [4%] AIMD (additive increase - multiplicative decrease)
|
a. Attempts to share links fairly among connections |
[X] |
|
b. Is used in the slow start phase of TCP |
[ ] |
|
c. Increases the number of connections to multiply throughput |
[ ] |
|
d. Adjusts the receiver advertised window |
[ ] |
1.9 [4%] WFQ
|
a. Is applied at the input queue of a router |
[ ] |
|
b. Affects the performance of packet dropping schemes such as RED |
[X] |
|
c. Requires that the traffic be fluid (i.e., not packetized) |
[ ] |
|
d. Provides explicit congestion notification |
[ ] |
1.10 [4%] TCP
|
a. Is particularly efficient with noisy links because of fast retransmit |
[ ] |
|
b. Favors connections with a large round trip time |
[ ] |
|
c. Reduces the number of packet retransmissions caused by errors |
[ ] |
|
d. Avoids saturating the receiver by implementing slow start |
[ ] |
2. Problem [20%]. Fill in the routing tables of the routers below using CIDR. That is, specify the prefixes of the ports of the routers. All the nodes of the network 128.32 are shown in the figure.
Show your work here:
00000000, 51 = 00110011, 58 = 00110110, 64 =
01000000,
120 = 01111000, 128 = 10000000, 134 = 10000110, 255 = 11111111
3. Problem [20%]. The figure below shows a multiplexer MPX that receives data from 10 sources (S1 - S10). The link rates (including that of the outgoing link) are all equal to 10Mbps. In this problem, we investigate the delays and the buffer requirements of the multiplexer under different multiplexing schemes.
(a) Assume that the sources send packets of 10kbits precisely every 20ms and that MPX uses statistical multiplexing. (MPX uses store-and-forward, with no cut-through.) What is the maximum buffer occupancy at MPX and what is the maximum delay of packets through MPX? (Define the delay pf a packet as the difference between the departure time of the last bit of the packet and the arrival time of that last bit.)
(b) Assume that the sources send packets of 10kbits precisely every 20ms and that MPX uses time division multiplexing. Specifically, MPX divides its outgoing link into frames of 1ms. Each frame consists of 10 slots that MPX allocates to the 10 sources in a round-robin way. That is, Sk uses the k-th slot of each frame, for k = 1, 2, ..., 10. For simplicity, we ignore any overhead that the frames and slots might require to keep the receiver synchronized. What is the maximum buffer occupancy at MPX and what is the maximum delay of packets through MPX?
(c) Assume that the sources send bursts of packets. Specifically, assume that in any 1 second epoch each source can send up to 50 packets of 10kbits. Assume that MPX uses statistical multiplexing. What is the maximum buffer occupancy at MPX and what is the maximum delay of packets through MPX?
Show your work here:
(a) The maximum
occupancy is 100kbits. It occurs when the packets from the 10 sources arrive at
the same time. The maximum delay is then 10 ms.
(b) We show the 10kbit
packet from one source that arrives at time 0. The first 1kbit chunk leaves
during the next slot allocated to that source. This slot may come at time 1ms,
in the worst case. In that case, the last chunk of the packet leaves at
time 10.1ms. The maximum delay is then approximately 10ms. The
maximum occupancy is again 100kbits.
(c) The maximum delays
occur when the bursts of packets from the 10 sources occur back-to-back for
each source and at the same time for all the sources. The worst delay is about
0.5 second and the worst occupancy is approximately 4.5Mbits (5Mbits is an
acceptable approximation).
4. Problem [20%]. In the six-node network shown below the nodes compute shortest path distances using the Bellman Ford distance vector method.
(*) Assume that time is slotted (t = 1,2,…) and that a node sends its distance vectors at the beginning of a slot. A distance vector transmitted on a link in the beginning of a slot arrives at its destination before the end of that slot. All distance estimates are computed using the most recently available information.
What are node A’s distance vectors at the end of time slots 1, 2, 3, 4 when:
(a) The problem is as stated in (*)
(b) The problem is as stated in (*), except that nodes B and F send estimates only every third time slot (A, C, D and E send estimates at the beginning of every time slot).
(c) The problem is as stated in (*) except that the link (E,F) has become so congested that it takes three timeslots to traverse, i.e. a distance vector from either E or F sent over the link at the beginning of time slot j, is only received at the other end of the link at the end time slot j+2. All of the nodes and the rest of the links behave as in (*).
Show your work here:
The distance estimate tables show the estimates at the end of time slots 0,1,2,3,4. Time slot 0 was not required for the solutions shows the initial conditions.
NOTE: Many
of you stated the answers in terms of estimates at the beginning of each slot,
which we did not take any points off for.
(a) The problem
is as stated in (*)
In iteration h,
node A knows h-hop shortest distances to each of the other nodes.
|
|
A |
B |
C |
D |
E |
F |
|
0 |
0 |
0.1 |
1 |
∞ |
0.9 |
∞ |
|
1 |
0 |
0.1 |
1 |
1.9 |
0.9 |
0.2 |
|
2 |
0 |
0.1 |
1 |
1.9 |
0.3 |
0.2 |
|
3 |
0 |
0.1 |
1 |
1.3 |
0.3 |
0.2 |
|
4 |
0 |
0.1 |
1 |
1.3 |
0.3 |
0.2 |
(b) The problem is as stated in (*), except that nodes B and F send estimates only every third time slot , at time slots 3,,6,9…(A,C,D and E send estimates at the beginning of every time slot).
Node A’s estimates at time 3 include all 3-hop shortest distances, except those which go through B or F. At the end of time slot 3, node A hears from B but the estimate from B includes no information from node F. That is why A still does not know of the shortest paths to D and E that will go through F. At the end of time slot 4, node A will have the correct estimates.
|
|
A |
B |
C |
D |
E |
F |
|
0 |
0 |
0.1 |
1 |
∞ |
0.9 |
∞ |
|
1 |
0 |
0.1 |
1 |
1.9 |
0.9 |
1 |
|
2 |
0 |
0.1 |
1 |
1.9 |
0.9 |
1 |
|
3 |
0 |
0.1 |
1 |
1.3 |
0.9 |
0.2 |
|
4 |
0 |
0.1 |
1 |
1.3 |
0.3 |
0.2 |
Note: Due to
the way in which some questions of
interpretation were answered during the exam, we may have given you credit for
the answer if you answered it using different assumptions.
(c) The problem is as stated in (*) except that the link (E,F) has become so congested that it takes three timeslots to traverse, i.e. a distance vector from either E or F sent over the link at the beginning of time slot j, is only received at the other end of the link at the end time slot j+2. All of the nodes and the rest of the links behave as in (*).
The estimates received by B from F in time slots 1, 2 and 3 do not reflect any information sent by E. However, since node B does hear from F in each time slot it can correctly compute the shortest path to E and reflect that information to node A by the end of slot 2. At the end of time slot 3, node F receives the time slot 1 update of node E. This information is reflected in the update from node E to B in time slot 4. Thus, in time slot 5 B can send the estimate informing A that B is 1.2 away from D. This implies that A figures out the correct shortest path distance vector only at the beginning of time slot 6.
|
|
A |
B |
C |
D |
E |
F |
|
0 |
0 |
0.1 |
1 |
∞ |
0.9 |
∞ |
|
1 |
0 |
0.1 |
1 |
1.9 |
0.9 |
0.2 |
|
2 |
0 |
0.1 |
1 |
1.9 |
0.3 |
0.2 |
|
3 |
0 |
0.1 |
1 |
1.9 |
0.3 |
0.2 |
|
4 |
0 |
0.1 |
1. |
1.9 |
0.3 |
0.2 |