Distributed Systems Assignment 3
Dick Lei
D-A0-1658-9 21/11/2002
Chapter 3
3-2 The following data fragment occurs in the middle of a data stream for which the character-stuffing algorithm described in the text is used: DLE, STX, A, DLE, B, DLE, ETX. What is the output after stuffing?
DLE, STX, A, DLE, DLE, B, DLE, ETX
3-3 If the bit string 0111101111101111110 is bit stuffed, what is the output string?
011110111101011111010
3-9 What is the remainder obtained by dividing x^7 + x^5 + 1 by the generator polynomial x^3 + 1?
Frame : 10100001
Generator : 1001
/ 1 / 0 / 1 / 1 / 0 / 1 / 1 / 11 0 0 1 / 1 / 0 / 1 / 0 / 0 / 0 / 0 / 1 / 0 / 0 / 0
/ 1 / 0 / 0 / 1
0 / 1 / 1 / 0
0 / 0 / 0 / 0
1 / 1 / 0 / 0
/ 1 / 0 / 0 / 1
1 / 0 / 1 / 0
1 / 0 / 0 / 1
0 / 1 / 1 / 1
/ 0 / 0 / 0 / 0
1 / 1 / 1 / 0
/ 1 / 0 / 0 / 1
1 / 1 / 1 / 0
1 / 0 / 0 / 1
1 / 1 / 1 / 0
/ 1 / 0 / 0 / 1
1 / 1 / 1
The Remainder : 1 1 1
3-11. A channel has a bit rate of 4 kbps and a propagation delay of 20 msec. For what range of frame sizes does stop-and-wait give an efficiency of at least 50 percent?
We use the line utilization formula to calculus the frame size
Line utilization = L/(L + bR)
The frame size is L bits
R is the round trip propagation delay, 2 x 20 ms = 40 ms = 40*0.001 sec = 0.004 sec
B is the channel capacity 4000 bits/sec
0.5 = L/(L+ 4000 * 0.004)
0.5 = L/( L + 160)
L = 0.5L + 80
L= 160 bits
Frames of size L > 160 bits would be have an efficiency of 50% and higher.
3-22. Frames of 1000 bits are sent over a 1-Mbps satellite channel. Acknowledgements are always piggybacked onto data frames. The headers are very short. Three-bit sequence numbers are used. What is the maximum achievable channel utilization for
(a) Stop-and-wait
(b) Protocol 5
(c) Protocol 6
NOTE: propagation delay = 270 msec
Let t=0 msec denote the start of transmission.
At t=1, the first frame has been fully transmitted. (transmit time of frame 1000bits / 1Mbps = 0.001 sec = 1 mesc) .
At t = 271, the first frame has fully arrived.
At t = 272, the frame acking the first one has been fully sent.
At t=542, the ack-bearing frame has fully arrived.
Thus, the cycle is 542 msec. A total of k frames are sent in 542 msec.
For an efficiency of k/542. Hence:
a) k=1, efficiency = 1/542 = 0.18%
b) k=7, efficiency = 7/542 = 1.29%
c) k=4, efficiency = 4/542 = 0.74%
Supplementary problems
1.What is the purpose of grouping data in frames at the data link layer?
The purpose of framing is provide synchronization between sender and receiver, sender must inform receiver the beginning and the ending of the transmission and it provide error control function.
2. For M(x) = 111000011, G(x) = 110011. Find the CRC code.
1 / 0 / 1 / 1 / 0 / 1 / 0 / 1 / 1110011 / 1 / 1 / 1 / 0 / 0 / 0 / 0 / 1 / 1 / 0 / 0 / 0 / 0 / 0
1 / 1 / 0 / 0 / 1 / 1
/ 1 / 0 / 1 / 1 / 0
0 / 0 / 0 / 0 / 0
/ 1 / 0 / 1 / 1 / 0 / 1
1 / 1 / 0 / 0 / 1 / 1
/ 1 / 1 / 1 / 1 / 0 / 1
1 / 1 / 0 / 0 / 1 / 1
/ 1 / 1 / 1 / 0 / 0
0 / 0 / 0 / 0 / 0
/ 1 / 1 / 1 / 0 / 0 / 0
1 / 1 / 0 / 0 / 1 / 1
/ 1 / 0 / 1 / 1 / 0
0 / 0 / 0 / 0 / 0
/ 1 / 0 / 1 / 1 / 0 / 0
1 / 1 / 0 / 0 / 1 / 1
/ 1 / 1 / 1 / 1 / 1 / 0
1 / 1 / 0 / 0 / 1 / 1
/ 0 / 1 / 1 / 0 / 1
CRC code: 11100001101101
3. Computer A and computer B communicate using HDLC protocol. Go back N sliding window is used as the flow control method.
A. If computer A received a frame with the following message in the control field, what information does computer B send to computer A?
a. The bit pattern of control field is 01011011
b. The bit pattern of control field is 10011011
a. first bit 1, its mean is I frame, next 3 bits 101 is seq 4 of outbound frame, next bit 1 is Poll, last 3 bits is 011 seq 2 is next frame expect to receive.
So B send to computer A 10111110
b .first two bits10 is S-frame, 01 is type 1 reject, next bit 1 is Poll, next 3 bits 011 it mean retransmit frame 2
so B send to computer A 10111100
B. Suppose that computer A is going to send the 5th data frame to computer B after receiving a frame with C field shown in (a), construct the frame that computer A is going to send.
In this case we don’t know the next frame is what so we let the next frame bits is xxx
So the computer A going to send is 01011xxx