Computer Networks - Worked out Problems

WORKED OUT PROBLEMS

1.Calculate the total time required to transfer a 1.5MB file in the following cases,assuming a RTT of 80 ms, a packet size of 1 KB data, and an initial 2×RTT of“handshaking” before data is sent.

(a)The bandwidth is 10Mbps, and data packets can be sent continuously.

            The bandwidth is 10Mbps, but after we finish sending each data packet we must wait one RTT before sending the next.

           The link allows infinitely fast transmit, but limits bandwidth such that only 20 packets can be sent per RTT.

            Zero transmit time as in (c), but during the first RTT we can send one packet, during the second RTT we can send two packets, during the third we can send four = 23−1, and so on.

SOLUTION

We will count the transfer as completed when the last data bit arrives at its destination.

           1.5 MB = 12,582,912 bits. 2 initial RTT’s (160 ms) + 12,582,912/10,000,000 bps (transmit)+

RTT/2 (propagation) ≈ 1.458 seconds.

            Number of packets required = 1.5 MB/1 KB = 1,536. To the above we add the time for 1,535 RTTs (the number of RTTs between when packet 1 arrives and packet 1,536 arrives), for a total of 1.458+122.8 = 124.258 seconds.

            Dividing the 1,536 packets by 20 gives 76.8. This will take 76.5 RTTs (half an RTT for the first batch to arrive, plus 76 RTTs between the first batch and the 77th partial batch), plus the initial 2 RTTs, for 6.28 seconds.

            Right after the handshaking is done we send one packet. One RTT after the handshaking we send two packets. At n RTTs past the initial handshaking we have sent 1+2+4+・ ・ ・+2n = 2n+1 −1 packets. At n = 10 we have thus been able to send all 1,536 packets; the last batch arrives 0.5 RTT later. Total time is 2 +10.5 RTTs, or 1 second.

2.Consider a point-to-point link 50 km in length. At what bandwidth would propagation delay (at a speed of 2 × 108 m/sec) equal transmit delay for 100- byte packets? What about 512-byte packets?

SOLUTION :

Propagation delay is 50 × 103 m/(2 × 108 m/sec) = 250 μs 800 bits/250 μs is 3.2 Mbits/sec. For 512-byte packets, this rises to 16.4 Mbit/sec.

3.Suppose a 128-Kbps point-to-point link is set up between Earth and a rover on Mars. The distance from Earth to Mars (when they are closest together) is approximately 55 Gm, and data travels over the link at the speed of light—3×108 m/sec.

           Calculate the minimum RTT for the link.

            Calculate the delay × bandwidth product for the link.

A camera on the rover takes pictures of its surroundings and sends these to Earth. How quickly after a picture is taken can it reach Mission Control on Earth? Assume that each image is 5 MB in size.

SOLUTION :

(a) Propagation delay on the link is (55 × 109)/(3 × 108) = 184 seconds. Thus the RTT is 368 seconds.

            The delay × bandwidth product for the link is = 184 × 128 × 103 = 2.81 MB.

            After a picture is taken it must be transmitted on the link, and be completely propagated before Mission Control can interpret it. Transmit delay

for 5 MB of data is 41,943,040 bits/128×103 = 328 seconds. Thus, the total time required is transmit delay + propagation delay = 328 + 184 = 512 seconds.

4.Calculate the latency (from first bit sent to last bit received) for:

·       A 1-Gbps Ethernet with a single store-and-forward switch in the path, and a packet size of 5,000 bits. Assume that each link introduces a propagation delay of 10 μs and that the switch begins retransmitting immediately after it has finished receiving the packet

            Same as (a) but with three switches.

            Same as (b) but assume the switch implements cut-through switching: it is able to begin retransmitting the packet after the first 128 bits have been received.

SOLUTION :

·       For each link, it takes 1 Gbps/5 kb = 5 μs to transmit the packet on the link, after which it takes an additional 10 μs for the last bit to propagate across the link. Thus, for a LAN with only one switch that starts forwarding only after receiving the whole packet, the total transfer delay is two transmit delays + two propagation delays = 30 μs.

            For three switched and thus four links, the total delay is four transmit delays + four propagation delays = 60 μs.

            For “cut-through,” a switch need only decode the first 128 bits before beginning to forward.

This takes 128 ns. This delay replaces the switch transmit delays in the previous answer for a total delay of one Transmit delay + three cut-through decoding delays + four propagation delays =45.384 μs.

5. For the following, as in the previous problem, assume that no data compression is done. Calculate the bandwidth necessary for transmitting in real time:

           HDTV high-definition video at a resolution of 1,920 × 1,080, 24 bits/pixel, 30 frames/sec.

            Plain old telephone service (POTS) voice audio of 8-bit samples at 8 KHz.

           GSM mobile voice audio of 260-bit samples at 50 Hz.

            HDCD high-definition audio of 24-bit samples at 88.2 kHz.

SOLUTION :

·      1,920×1,080×24×30 = 1,492,992,000 ≈ 1.5 Gbps.

            8×8,000 = 64 Kbps.

           260 ×50 = 13 Kbps.

24×88,200 = 216,800 ≈ 2.1 Mbps.

6. Show the 4B/5B encoding, and the resulting NRZI signal, for the following bit sequence:

1101 1110 1010 1101 1011 1110 1110 1111

SOLUTION :

The 4B/5B encoding of the given bit sequence is the following. 11011 11100 10110 11011 10111 11100 11100 11101

7 Suppose the following sequence of bits arrive over a link: 011010111110101001111111011001111110

Show the resulting frame after any stuffed bits have been removed. Indicate any errors that might have been introduced into the frame.

SOLUTION :

Let ∧ mark each position where a stuffed 0 bit was removed. There was one error where the sever consecutive 1s are detected (err). At the end of the bit sequence, the end of frame was detected (eof ).

01101011111∧101001111111err0 110 01111110eof

         Suppose we want to transmit the message 1011 0010 0100 1011 and protect it from errors using the CRC8 polynomial x8 +x2 +x1 + 1.

(a) Use polynomial long division to determine the message that should be transmitted.

(b) Suppose the leftmost bit of the message is inverted due to noise on the transmission link.

What is the result of the receiver’s CRC calculation? How does the receiver know that an error has occurred?

SOLUTION :

·       We take the message 1011 0010 0100 1011, append 8 zeros and divide by 1 0000 0111 (x8 + x2 + x1 + 1). The remainder is 1001 0011. We transmit the original message with this remainder appended, resulting in 1011 0010 0100 0011 1001 0011.

(b) Inverting the first bit gives 0011 0010 0100 1011 1001 0011. Dividing by 1 0000 0111 (x8 +x2 +x1 + 1) gives a a remainder of 1011 0110.

         Suppose you are designing a sliding window protocol for a 1-Mbps pointto-point link to the stationary satellite evolving around Earth at 3 × 104 km altitude. 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 meters per second.

(a) RWS=1.

(b) RWS=SWS.

SOLUTION :

One-way latency of the link is 100 msec. (Bandwidth) × (roundtrip delay) is about 125 pps×0.2 sec, or 25 packets. SWS should be this large.

           If RWS = 1, the necessary sequence number space is 26. Therefore, 5 bitsare needed.

IfRWS = SWS, the sequence number space must cover twice the SWS, or up to 50. Therefore, 6 bits are needed.

10.Given the extended LAN shown in Figure 3.34, assume that bridge B1 suffers catastrophic failure. Indicate which ports are not selected by the spanning tree algorithm after the recovery process and a new tree has been formed.

SOLUTION :

The following list shows the mapping between LANs and their designated bridges. B1 dead[B7]

B2 A,B,D

B3 E,F,G,H

B4 I

B5 idle

B6 J

B7 C

11.Suppose we have the forwarding tables shown in Table 4.13 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.

SOLUTION :

The following is an example network topology.