TDTS06 Computer Networks

Exercises

Networking basics

Calculate the total time required to transfer a 1000-KB file, with RTT of 100 ms, packet size of 1 KB data, and and initial 2 x RTT of handshaking before data is sent.

a)The bandwidth is 1.5 Mbps, and data packets can be sent continuously ("back-to-back").
b)The bandwidth is 1.5 Mbps, but after we finish sending each data packet we must wait one RTT before sending the next.
c)The bandwidth is "infinite", meaning that we take transmit to be zero, and up to 20 packets can be sent per RTT.
d)The bandwidth is infinite, and during the first RTT we can send one packet (2^1-1), during the second RTT we can send two packets (2^2-1), during the third we can send four (2^3-1), and so on.

A: We count a transfer as completed when the last bit of data has arrived at its destination. (An alternative interpretation would be to count until the last ACK arrives back at the sender, in which case the time would be half an RTT (50 ms) longer.)
a) 2 initial RTTs (200 ms) + 1000 KB/1.5 Mbps (transmit time) + RTT/2 (propagation of data) = 0.20 + 8 Mbit/1.5 Mbps + 0.05 = 0.20 + 5.33 seconds + 0.05 = 5.58 seconds. (With mega = 10⁶.)
b) To a) above we add the time for 999 RTTs, which is the number of RTTS between when packet 1 arrives and packet 1000 arrives. The total time is then 5.53 + 99.9 = 105.43 seconds.
c) This is 49.5 RTTs + the initial handshake of 2 RTTs = 4.95 + 0.20 = 5.15 seconds. (We only count the time for data arriving, not including the final ACK for the last packet, as stated in the introduction above.)
d) Right after the handshaking of 200 ms we send one packet. One RTT after the handshaking we send two packets, after two RTTs four packets, etc. At n> RTTs past the initial handshaking we have sent 1 + 2 + 4 + ... + 2ⁿ = 2ⁿ⁺¹ - 1 packets. At n = 9 we have sent all 1000 packets. The last batch arrives 0.5 later. Total time is 2 + 9.5 RTTs = 0.20 + 0.95 = 1.15 seconds. (This is actually what we do in a slowstart in TCP; see the chapter about congestion control!)
Calculate the bandwidth x delay product for the following links. Use one-way delay, measured from the first bit sent to the last bit received.

a) 10-Mbps Ethernet with a delay of 10 microsecs
b) 10-Mbps Ethernet with a single store-and-forward switch (the switch begins retransmitting after it has finished receiving the packet), packet size 5000 bits, and a 10 microsecs per link propagation delay
c) 1.5-Mbps T1 link, with a transcontinental one-way delay of 50 ms
d) 1.5-Mbps T1 link through a satellite in geosynchronous orbit, 35,900 km high. The only delay is speed-of-light propagation delay.

A:
- a) The b x w product is 10 x 10⁶ bits/sec x 10 x 10^-6 secs = 100 bits = 12.5 bytes
  b) The first-bit delay is 520 microsecs through the store-and-forward switch. The bandwidth x delay product is thus 10 Mbps x 520 microsecs = 5200 bits (Alternatively, you can think of it as each link can hold 100 bits and the switch can hold 5000 bits.)
  c) 1.5 x 10⁶ bits/sec x 50 x 10^-3 sec = 75,000 bits = 9375 bytes
  d) Please note that this should be through a satellite, that is, between two ground stations, not to a satellite. The total one-way travel distance between two ground stations through a satellite is then 2 x 35,900,000 meters. With a propagation speed of c = 3 x 10⁸ meters/sec, the one-way propagation delay is thus 2 x 35,900,000 / c = 0.24 sec. Bandwidth x delay is thus 1.5 x 10⁶ bits/sec x 0.24 sec = 360,000 bits = approx. 45 KBytes.
Imagine that you have trained your polecat Goran to carry a box full of three 8 mm tapes. These tapes each contain 7 GB. The polecat can travel to your side, wherever you are, at 18 km/hour. For what range of distances does Goran have a higher data rate than a transmission line whose data rate (excluding overhead) is 150 Mbps?
A: The polecat can carry 21 GB, or 168 Gbits. A speed of 18 km/hour equals 0.005 km/sec. The time to travel a distance x km is x/0.005 sec = 1/0.005 x sec = 200 x sec, yielding a data rate for the polecat of 168 Gbits/(200x) bits/sec, or 840 Mbits/x bits/sec = 840/x Mbps. Now, if the polecat is to be faster than the transmission line of 150 Mbps, then 840/x > 150 => x = 840/150 = 5.6 km
Calculate the latency for the following (from the first bit to the last bit):

a)10-Mbps Ethernet with a single store-and-forward switch in the path, and a packet size of 5000 bits. Assume that each link introduces a propagation delay of 10 microsecs, and that the switch begins retransmitting immeadiatly after it has finished receigin the packet.
b) as in a), but with three switches
as b) above, but with switches that implement "cut-through switching", which means they are able to begin transmitting the packet after the first 200 bits have been received (another type of switch, which can be found in real life).
A:

a) One packet consists of 5000 bits, so the delay due to bandwidth is 500 microseconds along each link (se the figure in the textbook). The packet is also delayed 10 microseconds on each of the two links due to propagation delay, for a total of 1020 microseconds.
b) With three switches and four links, the delay is 4 x 500 microseconds + 4 x 10 microseconds = 2.04 milliseconds (ms)
c) With cutthrough and three switches, each switch delays the packet by 200 bits = 20 microseconds. There is still one 500 microseconds delay waiting for the last bit, so the total is 500 + 3 x 20 + 4 x 10 = 600 microseconds.
In other words, the last bit still arrives 500 microseconds after the first bit; the first bit now faces four link delays and three switch delays but never has to wait for the last bit along the way.
With cutthrough and one switch, the total is 500 + 1 x 20 + 2 x 10 = 540 microseconds.

TCP

Suppose TCP operates over a 1-Gbps link.

a) How long would it take for the TCP sequence numbers to wrap around completely?
b) Suppose an added 32-bit timestamp field increments 1000 times during the wraparound time you found out above. How long would it take for the timestamp to wrap around?

A:
- a) First, we convert the speed of the link to the unit of bytes: 1 Gbps = (1 Gbits / 8 bits) = 125 MB/sec. The sequence numbers wrap around when we have sent 2³² B worth of segments = 4 GB. On the link given in the question, the wrap-around would take 4 GB / (125 MB/sec) = 32 seconds.
- b) Incrementing every 32 ms (32 secs/1000), it would take about 32 x 4 x 10⁹ ms, or about four years, for the timestamp field to wrap.

Checksum example exercise. Q: Suppose the following block of 16 bits is to be sent using a checksum of 8 bits (we simplify the original Internet checksum algorithm, which uses 16 bits):

       <--- 10101001 00111001

a) What is the final pattern sent?

b) Show how the receiver determines if there is an error or not in the message pattern sent!

c) Suppose there is a burst error of length five that affects four bits in the message:

       <--- 10101111 11111001
                 ^^  ^^
                errors

Show how the error is detected by the receiver!

a) First, the numbers are added using one's complement arithmetic to get the checksum:

                  10101001
                  00111001
                  --------
       Sum        11100010
       Checksum:  00011101

The pattern sent is then:

       <--- 10101001 00111001 00011101
                              checksum

b) When the receiver adds the three sections together, it will get all 1s, which, after complementing is all 0s and shows that there is no error:

                   10101001
                   00111001
                   00011101
                   --------
       Sum         11111111
       Complement  00000000  means that the pattern is O.K.

c) When the receiver adds the three sections together, it gets

                   10101111
                   11111001
                   00011101
                -----------
       Result   1  11000101
       Carry              1
                -----------
       Sum         11000110
       Complement  00111001  means that the pattern is corrupted, because the complement is not zero

IP

The table below is a routing table using CIDR. Address bytes are in hexadecimal. The notation "/12" in C4.50.0.0.0/12 denotes a netmask with 12 leading 1 bits, that is, FF.F0.0.0. Note that the last three entries cover every address and thus serve in lieu of a default route. State to what next hop the following will be delivered:

C4.5E.13.87
C4.5E.22.09
C3.41.80.02
5E.43.91.12
C4.6D.31.2E
C4.6B.31.2E
```
	    Routing table:
	    -----------------------------
	    Net/Mask Length     Next Hop
	    -----------------------------
	    C4.50.0.0/12        A
	    C4.5E.10.0/20       B
	    C4.60.0.0/12        C
	    C4.68.0.0/14        D
	    80.0.0.0/1          E
	    40.0.0.0/2          F
	    00.0.0.0/2          G
	    -----------------------------
	    
```
A: The destinations are as follows:

a) B.
b) A.
c) E.
d) F.
e) C.
f) D (note that the first 14 bits of C4.6B and C4.68 match!).
A computer on a 6-Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 1 Mbps. It is initially filled to the capacity with 8 Mbps. How long can the computer transmit at the full 6 Mbps?
A: Let us denote the call burst length S secs, token bucket capacity C bytes, token arrival rate p bytes/sec, and max. output rate M bytes/sec. Then the output burst contains a maximum of C + pS bytes. We also know that the number of bytes in a max-speed burst of length S seconds i MS. So we have C + pS = MS. We solve the equation and get S = C / (M - p). If we denote the capacity of the token bucket with C = 8 megabits, the token generation rate with p = 1, the transmission rate of the computer with M = 6; then we get the time (or burst length) as S = C / (M p) = 8 / (6 1) = 1.6 seconds.

Routing

Consider the network below and assume each node initially knows the costs to each of its neighbours. Consider the distance-vector algorithm and show the distance table entries at node z when the algorithm has stabilized itself.

A: The first table below shows the initial values at z. The second table shows the contents after one hop of information received from the neighbours, the third after two hops, and the last after three hops (where the least-cost path from x-to-u via z is found).

LANs

Consider the arrangement of self-learning switches shown in the figure below. Assuming all are initially empty, give the forwarding tables for each of the switchs B1-B4 after the following transmission:
A sends to C
C sends to A
D sends to C.
```
               B3 ---- C
               |
               |
A ---- B1 ---- B2
               |
               |
               B4 ---- D
```
A: When A sends to C, all switchs B1-B4 see the packet and learn where A is because the packet is flooded. However, when C then sends to A, the packet is routed directly to A and B4 does not learn where C is. Similarly, when D sends to C, the packet is routed by B2 towards B3 only, and B1 does not learn where D is. The ports of the switchs after the transmissions are as follows.

Switch B1: A-interface = A; B2-interface = C (not D)
Switch B2: B1-interface = A; B3-interface = C; B4-interface = D
Switch B3: B2-interface = A,D; C-interface = C
Switch B4: B2-interface = A (not C); D-interface = D.

Page responsible: Andrei Gurtov
Last updated: 2009-10-21

IDA - Department of Computer and Information Science

TDTS06 Computer Networks

Exercises

Networking basics

TCP

IP

Routing

LANs