Description

Design and Analysis of Computer Networks Key to Homework Assignment 1

1. Calculate the total time required to transfer a 1000-KB file in the following cases, assuming an RTT of 50 ms, a packet size of 1 KB data, and an initial 2×RTT of “handshaking” before data is sent. We define the total time of transferring the file as the time elapsed from the starting of initial handshaking to the instant when the last bit arrives at the receiver. (Total: 20 points, each part has 5 points)

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

(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 time 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 (21−1), during the second RTT we can send two packets (22−1), 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. 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 (25ms) longer.

(a) 2 initial RTT’s (100ms) + 1000KB/1.5Mbps (transmit) + RTT/2 (propagation = 25ms) ≈ 0.125 + 8Mbit/1.5Mbps = 0.125 + 5.333 sec = 5.458 sec. If we pay more careful attention to when a mega is 106 versus 220, we get 8,192,000 bits/1,500,000bps = 5.461 sec, for a total delay of 5.586 sec.

(b) To the above we add the time for 999 RTTs (the number of RTTs between when packet 1 arrives and packet 1000 arrives), for a total of 5.586 + 49.95 = 55.536.

(c) This is 49.5 RTTs, plus the initial 2, for 2.575 seconds.

(d) 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 = 9 we have thus been able to send all 1,000 packets; the last batch arrives 0.5 RTT later. Total time is 2+9.5 RTTs, or .575 sec.

2. In the figure below, all frames are generated at node A and sent to node C through node B. Determine the minimum transmission rate required between nodes B and C so that the buffers of node B are not flooded, based on the following conditions: (20 points)
• The data rate between A and B is 100 kilobits/s.
• The propagation delay is 5 µs/km for both lines.
• There are full-duplex lines between the nodes.
• All data frames are 1000 bits long; ACK frames are separate frames of negligible length.
• Between A and B, a sliding-window flow control with a window size of 3 is used.
• Between B and C, stop-and-wait flow control is used.
• There are no errors.

Solution: To avoid overflow (or flooding) at B, the throughput of link AB should be not greater than that of link BC. The period of one round of transmission on link AB = Tx time of 1 frame + 1 RTT, therefore

T_{AB}=1000/100kbps+8000*5us=0.05s
Throughput_{AB}=3000bits/0.05s=60kbps

On link BC, the period of one round of transmission is
T_{BC}=1000/R_{BC}+2000*5us=1000/R_{BC}+0.01s
Throughput_{BC} = 1000/T_{BC}=1000/(1000/R_{BC}+0.01s)

Because we need Throughput_{BC}>Throughput_{AB}, we solve the inequability and get R_{BC}=150kbps.

3. For each of the following sets of codewords, please give the appropriate (n,k,d) designation where n is number of bits in each codeword, k is the number of message bits transmitted by each code word and d is the minimum Hamming distance between codewords. What is the coding rate (k/n), error detection capability, and error correction capability for each coding scheme? (Total: 20 points, each part has 10 pts)

A. {111, 100, 001, 010}

Solution: n=3, k=2 (as there are 4 codewords), d=2. Code rate is 2/3, can detect 1-bit error, can correct 0 bit error.

B. {00000, 01111, 10100, 11011}

Solution: n=5, k=2, d=2. Code rate is 2/5, can detect 1-bit error, can correct 0 bit error.

4. In an error-correction code, an important constraint that the coding scheme must satisfy is that the number of added check bits should be sufficient to identify unique error patterns (note that no error is also a valid error pattern). Now suppose that we decide to use a (n, 20, 3) error correction code to transmit 20-bit messages. What’s the minimum value of n that will allow the code to correct single bit errors? Show the reason and the calculation for full credits. (10 points)

Solution: Note that n+1 <=2^(n-k), where k=20. So the minimum n should be 25.

5. Consider the Markov chain with three states, S={1, 2, 3}, that has the following transition matrix

(a) Draw the state transition diagram for this chain.
(b) If we know P(X1=1)=P(X1=2)=1/4, find P(X1=3, X2=2, X3=1). (Total: 15 points, part (a) has 8 points and part (b) has 7 points.)

Solution:

(a) State transition diagram

(b) P(X1=3) = 1-P(X1=1)-P(X1=2)=1/2

So, P(X1=3, X2=2, X3=1)=P(X3=1|X2=2, X1=3) P(X2=2|X1=3) P(X1=3)
=P(X3=1|X2=2) P(X2=2|X1=3) P(X1=3)
= 1/3 * ½ * ½ = 1/12

6. Consider the Markov chain in the following figure. There are two recurrent classes, R1={1, 2} and
R2={5,6,7}. Assuming initial state X0=3. Find the probability that the chain gets absorbed in R1. (15 points)

Solution: Here, we can replace each recurrent class with one absorbing state. The resulting state diagram is as follows.

Now we can define a_i = P(absorption in R1|X0=i), for all i in S. By this definition we know that aR1=1 and aR2=0. To find the unknow values of a_i’s, we can use the following equations

𝑎𝑖 =∑𝑘 𝑝𝑖𝑘𝑎𝑘 for all i

Then we obtain a3=1/2 aR1+1/2a4=1/2+1/2a4.

a4=1/4aR1+1/4a3+1/2aR2=1/4+1/4a3.

Solving the above equations, we get: a3=5/7, a4=3/7. So if X0=3, then the probability that the process will be absorbed by R1 is a3=5/7.