Chapter3 THE DATA LINK LAYER2.The following data fragment occurs in the middle of a data stream for which thebyte-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 ：This 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: 2+x x+1+111111lim=lim =lim +=+lim =2+2x 2x+122x+122x+12x x x x →∞→∞→∞→∞（）（）（）（） 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 ：FLAG FLAG Payload field4.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. It’s 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?According to rr m 2)1(≤++，m=8 r=4P1=B1⊕B3⊕B5⊕B7⊕B9⊕B11 =∑(0,1,0,0,1,1)=1P2=B2⊕B3⊕B6⊕B7⊕B10⊕B11=∑(0,1,1,0,1,1)=0P3=B4⊕B5⊕B6⊕B7 ⊕B12 =∑(0,0,1,0,1)=0P4=B8⊕B9⊕B10⊕B11⊕B12 =∑(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:100111001010+ 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 dividing 751x x ++by the generator polynomial 31x +?42375745452424211111x x xx x x x x x x x x x x x xx x ++++++++++++++The remainder is 21x x ++.15.A bit stream 10011101 is transmitted using the standard CRC method described in the text. Thegenerator 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 receiv er’s 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 ：10011101100→10111101100 10111101100 mod 1001 = 100 ≠ 0 →error!(3)example: 10011101100→1001111010110011110101 mod 1001 = 0So the receiver may think that the received bit string is right while it ’s wrong in fact.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 propagat ion 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 bitsFrames 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)=1msRound trip time: R=270ms*2=540msIt 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)1＜W≤-1=7 →W=7(c)W≤=4→W=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,that’s mean: if w>9 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) 15>9&&127>9, 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 causing confusion.Answer:(1) PPP was clearly designed to be implemented in software, not in hardware as HDLC nearly always is. With a software implementation, working entirely with bytes is muc h simpler than working with individual bits.(2) PPP was designed to be used with modems, and modems accept and transmit data in units of 1 byte, not 1 bit.33. What is the minimum overhead to send an IP packet using PPP? Count only the overhead introduced by PPP itself, not the IP header overhead. What is the maximum overhead?Solution:the PPP full frame format for unnumbered mode is：And Address and control could be ignored if sender and receiver have approve it.The minimum overhead=1+1+2+1=5bytesThe maximum overhead=1+1+1+2+4+1=10bytes。
