计算机网络第三章作业参考答案.doc

Chapter3 THE DATA LINK LAYER2. The following data fragment occurs in the middle of a data stream for which the byte-stuffing algorithm described in the text is used: A B ESC C ESC FLAG FLAG D. What is the output after stuffing?Answer:A B ESC C ESC FLAG FLAG D= A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D3. What is the maximum overhead in byte-stuffing algorithm?Answer：FLAGFLAGPayload fieldThis a frame delimited by flag bytes. (Ignore the header and trailer)Suppose that there is x bytes in payload field, and the worst case is that all of them are flag bytes or ESC, there should be 2x bytes in total. So the max overhead in byte-stuffing should be:Or: (from 袁子超)if it has n bytes to send, and has m ESC. So the overhead is： .If the n bytes are all ESC, the overhead is maximum as： 4.When bit stuffing is used, is it possible for the loss, insertion, or modification of a single bit to cause an error not detected by the checksum? If not, why not? If so, how? Does the checksum length play a role here?Answer：It is possible. Suppose that the original text contains the bit sequence 01111110 as data. After bit stuffing, this sequence will be rendered as 011111010. If the second 0 is lost due to a transmission error, what is received is 01111110, which the receiver sees as end of frame. It then looks just before the end of the frame for the checksum and verifies it. If the checksum is 16 bits, there is 1 chance in 216 that it will accidentally be correct, leading to an incorrect frame being accepted. The longer the checksum, the lower the probability of an error getting through undetected, but the probability is never zero.6. To provide more reliability than a single parity bit can give, an error-detecting coding scheme uses one parity bit for checking all the odd-numbered bits and a second parity bit for all the even-numbered bits. What is the Hamming distance of this code?Answer:Any single-bit error in the odd-numbered bits could change parity bit. Its the same as the even-numbered bits. And both two errors occur in the odd-numbered bits or in the even-numbered bits will not change the parity bit. That is to say , this code could only detect single-bit errors, which means the Hamming distance is 2.7.An 8-bit byte with binary value 10101111 is to be encoded using an even-parity Hamming code. What is the binary value after encoding?Answer：According to ，m=8 r=4P1=B1B3B5B7B9B11 =(0,1,0,0,1,1)=1 P2=B2B3B6B7B10B11=(0,1,1,0,1,1)=0P3=B4B5B6B7 B12 =(0,0,1,0,1)=0 P4=B8B9B10B11B12 =(0,1,1,1,1)=0So, Hamming code is: 10100100111113. Suppose that a message 1001 1100 1010 0011 is transmitted using Internet Checksum (4-bit word). What is the value of the checksum?Solution:1001 1100 1010 + 0011- 0010 (have 2 added bit),so: +1+1- 0100So, the Internet checksum is the ones complemnet of 0100, or 1011.14. What is the remainder obtained by dividingby the generator polynomial ?Solution：The remainder is .15.A bit stream 10011101 is transmitted using the standard CRC method described in the text. The generator polynomial is ,. Show the actual bit string transmitted. Suppose that the third bit from the left is inverted during transmission. Show that this error is detected at the receivers end. Give an example of bit errors in the bit string transmitted that will not be detected by the receiver.Solution:(1) 100110011101000 mod 1001 = 100The actual bit string transmitted: 10011101000+100=10011101100(2) The bit string receiver receives：100111011001011110110010111101100 mod 1001 = 100 0 error!(3)example: 1001110110010011110101 10011110101 mod 1001 = 0 So the receiver may think that the received bit string is right while its wrong in fact.16. Data link protocols almost always put the CRC in a trailer than in a header. Why?Answer:CRC is calculated during sending. It could be appended to the data bit string as soon as the last data bit is send to the path. If it is put in the header, it must scan the whole frame in order to calculate CRC. It means that we should dispose the code 2 times. And CRC in the trailer could help to drop the half time.Or: (from 袁子超 )CRC calculate during transmission. Once the last data sent out line, immediately put CRC code attached to the output stream from the back. If put CRC on the head of the frame, then we should check the frame to calculate CRC before sending. So that each byte has to deal with two times, the first is to calculate the check code, second times to send. Put CRC in the tail of the processing time can be halved.20. A 3000-km-long T1 trunk is used to transmit 64-byte frames using protocol 5. If the propagation speed is 6 sec/km, how many bits should the sequence numbers be?Solution： delay= 3000-km* 6 sec/km=18msBecause the bandwidth of T1 trunk = 1.544Mbps ，so：send time=64*8bits/1.544Mbps=0.33msthe time of send a frame and receive the acknowledge frame=18ms+0.33ms+18ms=36.33msthe number of frames: 36.33ms/0.33ms=11064=110=128sequence number should be 7 bits29. Frames of 1000 bits are sent over a 1-Mbps channel using a geostationary satellite whose propagation time from the earth is 270 msec. 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?Solution：Time for send a frame is: 1000bits/(1Mbps)=1ms Round trip time: R=270ms*2=540ms It takes R+2=542ms to send a frame (be acknowledged). Therefore, a transmission cycle is 542ms. If the 542ms can send w frame, as a result of each frame transmission time is 1ms, the channel utilization rate is w/542.Three-bit sequence numbers are used, so the max window for (a),(b),(c) are :(a):W=1(b)1W-1=7 W=7(c)W=4W=4So line utilization rate is: (a) 1*1ms/542ms * 100%=0.184% (b)7*1ms/542ms * 100%=1.292% (c)4*1ms/542ms*100%=0.738%30. Consider an error-free 64-kbps satellite channel used to send 512-byte data frames in one direction, with very short acknowledgements coming back the other way. What is the maximum throughput for window sizes of 1, 7, 15, and 127? The earth-satellite propagation time is 270 msec.Solution:Time for send a frame: 512*8bits/64kbps=64msSo, a transmission cycle: T=270ms*2+64ms=604ms and transmission window is: 604ms/64ms=9.4,thats mean: if w9 the channel is full, the throughput cannot rise, (1) W=1: throughout=512*8b/604ms=6781bps=6.78kbps(2) W=7: throughout=7*512*8b/604ms=47.47kbps(3)(4) 159&1279, so throughout= 64kbps32. Give at least one reason why PPP uses byte stuffing instead of bit stuffing to prevent accidental flag bytes within the payload from c