CS/ECE 438: Communication Networks for Computers Spring 2014

Final Study Guide

Note that this sample is just designed to help you memorize the basic conceptions
mentioned in class. The contents in class are not thoroughly covered though.
This sample doesn’t have any high level questions, but you need to get prepared since there
would be high level questions in final just as it has been in hws and midterm.

1.Error detection and correction.

a. Show that two-dimensional parity provides the receiver enough information to correct any 1
bit error (assuming the receiver knows only 1 bit is bad), but not any 2-bit error. (use your own
examples)
b. Show that two-dimensional parity allows detection of all 3-bit errors. (use your own examples)
c. What is the Hamming distance of two-dimensional parity?
Detection:4
Correction:3

2.Sliding Window Algorithms

Suppose you are designing a sliding window protocol for a 1-Mbps point-to-point link to the
stationary satellite revolving around the Earth at an altitude of 3 × 104 km. Assuming that each
frame carries 1 KB of data, what is the minimum number of bits you need for the sequence
number in the following cases? Assume the speed of light is 3 × 108 m/s.
(a) RWS=1
(b) RWS=SWS

Solution:
One-way latency of the link is100ms.(Bandwidth)×(round trip delay) is about 125 pps × 0.2 sec,
or 25 packets. SWS should be this large.
(a) If RWS=1,the necessary sequence number space is 26. Therefore, 5 bits are needed.
(b) If RWS=SWS, the sequence number space must cover twice the SWS, or up to 50. Therefore,
6 bits are needed.

3.Sliding Window Algorithms

Draw a time line diagram for the sliding window algorithm with SWS = RWS = 4 frames in the
following two situations. Assume the receiver sends a duplicate acknowledgment if it does not
receive the expected frame. For example, it sends DUPACK[2] when it expects to see Frame[2]
but receives Frame[3] instead. Also, the receiver sends a cumulative acknowledgment after it
receives all the outstanding frames. For example, it sends ACK[5] when it receives the lost frame
Frame[2] after it already received Frame[3], Frame[4], and Frame[5]. Use a timeout interval of
about 2 × RTT.
(a) Frame 2 is lost. Retransmission takes place upon timeout (as usual).
(b) Frame 2 is lost. Retransmission takes place either upon receipt of the first DUPACK or upon
timeout. Does this scheme reduce the transaction time? (Note that some end-to-end protocols,
such as variants of TCP, use similar schemes for fast retransmission.)
Solution:
The figure that follows gives the time line for the first case. The second case reduces the total
transaction time by roughly 1 RTT.
CS/ECE 438: Communication Networks for Computers Spring 2014
Final Study Guide

4. Medium access control

(a)Suppose nodes A and B are on the same 10 Mbps Ethernet bus, and the propagation delay
between the two nodes is 325 bit times. Suppose node A begins transmitting a frame and, before
it finishes, node B begins transmitting a frame. Can A finish transmitting before it detects that B
has transmitted? Why or why not? If the answer is yes, then A incorrectly believes that its frame
was success- fully transmitted without a collision. Hint: Suppose at time t = 0 bit times, A begins
transmitting a frame. In the worst case, A transmits a minimum-sized frame of 512 + 64 bit
times. So A would finish transmitting the frame at t = 512 + 64 bit times. Thus, the answer is no,
if B’s signal reaches A before bit time t = 512 + 64 bits. In the worst case, when does B’s signal
reach A?
(b)Explain why a minimum frame size is required for Ethernet. For example, 10Base Ethernet
imposes a minimum frame size constraint of 64 bytes. (If you have done the previous problem,
you might have realized the reason). Now suppose that the distance between two ends of an
Ethernet LAN is d. Can you derive a formula to find the minimum frame size needed for an Eth-
ernet packet? Based on your reasoning, what is the minimum required packet size for an Ethernet
that spans 2 kilometers?

Solution:
(a)At t = 0 A transmits. At t = 576 , A would finish transmitting. In the worst case, B begins
transmitting at time t=324, which is the time right before the first bit of A’s frame arrives at B.
At time t=324+325=649 B 's first bit arrives at A . Because 649> 576, A finishes transmitting
CS/ECE 438: Communication Networks for Computers Spring 2014
Final Study Guide
before it detects that B has transmitted. So A incorrectly thinks that its frame was successfully
transmitted without a collision.
(b)
Following the same reasoning as in last problem, we need to make sure that one end of the
Ethernet is able to detect the collision before it completes its transmission of a frame. Thus, a
minimum frame size is required.
Let BW denote the bandwidth of the Ethernet. Consider the worst case for Ethernet’s collision
detection:1. At t=0 (bit times): A sends a frame2. At t=dprop-1 (bit times): B sends a frame right
before it can sense A’s first bit.
3. At t=2dprop-2 (bit times): If A finishes its transmission of its last bit just before B’s frame
arrives at A, then, A won’t be able to detect a collision before finishing its transmission of a
frame. Thus, in order for A to detect collision before finishing transmission, the minimum
required frame size should be >= 2dprop-1 (bit times).
Assume that the signal propagation speed in 10BASE-T Ethernet is 1.8*108m/sec.As
dprop=d/(1.8*108)*BW(here, we need to convert the propagation delay in seconds to bit times
for the specific Ethernet link), we find the minimum required frame size is 2*d/(1.8*108)*BW-1
(bits). Or approximately we choose 2*d/(1.8*108)*BW (bits).If d=2km, then minimum required
frame size is: 222 bits.

5.IP Fragmentation
Consider sending a 2400-byte datagram into a link that has an MTU of700 bytes. Suppose the
original datagram is stamped with the identification number 422. How many fragments are
generated? What are the values in the various fields in the IP datagram(s) generated related to
fragmentation?
Solution:
The maximum size of data field in each fragment = 680 (because there are 20 bytes IP
header).Thus the number of required fragments (2400-20)/680 = 4
Each fragment will have Identification number 422. Each fragment except the last one
will be of size 700 bytes (including IP header). The last datagram will be of size 360 bytes
(including IP header). The offsets of the 4 fragments will be 0, 85, 170, 255. Each of the first 3
fragments will have flag=1; the last fragment will have flag=0.

6. Forwarding tables
Suppose we have the forwarding tables shown in Table3.17 for nodes A and F, in a network
where all links have cost 1. Give a diagram of the smallest network consistent with these tables.

The following is an example network topology.

CS/ECE 438: Communication Networks for Computers Spring 2014
Final Study Guide

7.TCP
Suppose TCP operates over a 40-Gbps STS-768 link.
(a) Assuming TCP could utilize the full bandwidth continuously, how long would it take the
sequence numbers to wrap around completely?
(b) Suppose an added 32-bittimestampfieldwhichincrements 1000 times during the wraparound
time you found above. How long would it take for the timestamp to wrap around?

(a) 232 B / (5GB) = 859ms.

(b) 1000ticksin859msisonceeach859μsindicatingwrap
around in 3.7 Ms or approximately 43 days.

8.Multicast Routing
Consider multicast routing over an internet built from local area networks and routers as shown.
A certain multicast group Z has members Alpha, Beta, Gamma and Delta. Suppose that Alpha
wishes to send a packet to Z. To do so, suppose Alpha sends a packet to router R4 with a “Z” in
the address field of the packet and “Alpha” as the source address. (This initial packet is NOT
read by routers R5 and R6). Use hop count as the metric for all measurements, disambiguating
ties with node ID. Explain all of your answers.

Beta
H
A R8 F
R1 Gamma
I

D R3
R2

R4 R5 E
C
R7
Alpha
Delta
B G
R6

a.For this part, suppose the link state method is used and that all routers have all LSP's reflecting
membership in Z. What local area networks will carry copies of the packet?
b.Under the assumptions of part (a), which hosts (if any) will receive packets that have passed
through Net B on their way from router R4?
c.For this part, suppose that reverse-path broadcast is used to send the packet from router R4.
What local area networks will carry copies of the packet?
d.For this part, suppose that reverse-path multicast is used to send the packet from router R4.
Suppose that the multicast group has been used frequently in the recent past so that the maximum
amount of helpful information about the multicast group is in the router caches. What local area
CS/ECE 438: Communication Networks for Computers Spring 2014
Final Study Guide
networks will carry copies of the packet?

Solution:

Beta
H
A R8 F
R1 Gamma
I

D R3
R2

R4 R5 E
C
R7
Alpha
Delta
B G
R6

a. Link State routing protocol will compute the shortest-path multicast tree at each router.
So the local area networks that will carry copies of the packet are:
A, H,B,E,G,C,F
b. Gamma and Delta
c. All LANs in the network
d. A,H,B,E,G,C,F.(pruning D and I).