15、第三章数据链路层习题及参考答案

发布时间:2018-12-23 19:46  浏览次数:8

1、一个上层数据包被分成10个帧,每一帧有80%的机会无损地到达目的地。如果数据链路协议没有提供错误控制,试问,该报文平均需要发送多少次才能完整地到达接收方?
答:一次发送成功的概率是0.810=0.107,所以大约需要10次。

2、数据链路层协议使用了下面的字符编码:A:01000111 B:11100011 FLAG:01111110
ESC:11100000。为了传输一个包含4个字符的帧:A B ESC
FLAG,试问使用下面哪种成帧方法时所发送的比特序列是什么(二进制表示)?(1)字节计数(2)字节填充的标志字节(3)比特填充的标志字节
答:(1)字节计数法需要帧的长度信息,所以一共需要发送5个字节。发送序列为:00000100(表示4)01000111 (A)11100011
(B)11100000(ESC)01111110 (FLAG);
(2)FLAG是起始、结束标志。所以发送序列为:01111110(FLAG) 01000111(A) 11100011(B) 11100000(ESC)
11100000(ESC) 11100000(ESC)01111110(FLAG)01111110(FLAG)

(3)数据中若遇到连续5个1则在其后添加0。所以发送序列为:01111110(FLAG)01000111(A)110100011(B)111000000(ESC)011111010
(FLAG)01111110 (FLAG)

3、一个数据流中出现了这样的数据段:A B ESC C ESC FALG FLAG D,假设采用本章介绍的字节填充法,试问填充之后的输出是什么?
答:A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D

4、试问字节填充法的最大开销是多少?
答:如果数据全是ESC和FLAG,那么开销将是100%。

5、你的一个同学Scrooge指出每一帧的结束处和开始处都用一个标志字节,这种做法非常浪费空间,因为用一个标志字节也可以完成相同的任务。你同意这种观点吗?

答:如果可以在一个连续的帧流中计算帧,一个标志字节可能够了。但是用一帧来结尾,接收方可能不知道下一个比特是一个新帧的开始还是线路噪声;如果用一帧来开始,那么之后的比特可能不是前一帧的数据。

6、需要在数据链路层上发送一个比特串:011110111110011111010。试问,经过比特填充之后实际被发送出去的是什么?
答:每5个1后面填充一个0,所以发送比特串是:011110111110011111010。

7、试问在什么样的情况下,一个开环协议(比如海明码)有可能比本章通篇所讨论的反馈协议更加合适?

答:传输延迟非常长,如空间卫星传输,正向纠错是必要的;开环协议也适用于军事上,接受者不希望在传输过程中暴露它的位置;如果错误率非常低,并且纠错码足够好,也可以使用开环协议;实时系统中无法忍受等待重传的情况。


8、为了提供比单个奇偶位的可靠性,一种检错编码方案如下:用一个奇偶位来检查所有奇数序号的位,用另一个奇偶位来检查所有偶数序号的位。试问这种编码方案的海明距离是多少?
答:如同单个奇偶位,任何一位的错误将导致一个奇偶位校检码出错,所以海明距离为2。


9、假设使用海明码来传输16位的报文。试问,需要多少个校检位才能确保接收方能同时检测并纠正单个比特错误?对于报文1101001100110101,试给出传输的比特模式。假设在海明码中使用了偶校检。
答:校检码在2的幂次方处,包括校检码并没有超过31位,所以使用5个校检码就可以了。

10、接收方收到一个12位的海明码,其16进制值为0xE4F。试问该码的原始值是多少?假设至多发生了一位错误。
答:只可能是8位数据和4位校检码,但是第2位校检位出错,需要修正,修正后的值是0xA4F,8位数据值是0xAF。


11、检测错误的一种方法是按n行,每行k位来传输数据,并且在每行和每列加上奇偶位。其中最右下角是一个校检其所在行和列的奇偶位。试问这种方案能检测出所有的1位错误码?2、3位呢?请说明这种方案无法检测出某些4位错误。

答:1位错误,行检验和列检验都能检测出来;2位错误,如果在不同行,行检验就可以检测出来,如果在相同行,列检验就可以检测出来;3位错误与2位错误类似,如果组成一个直角三角形,那么只能检测出一个错误;4位错误如果成方形,那么将检测不出。


12、假设数据以块状形式传输,每块大小1000比特。试问,在什么样的最大错误率下,错误检测和重传机制(每块1个校检位)比使用海明码更好?假设比特错误相互独立,并且在重传过程中不会发生重传错误。

答:使用海明码每个块至少需要10个校检位,总的数据位数是1010位。如果是检错的话,只需要1位检验码。假设出错率是x/bit,那么一个块出错的次数为1000x。每次出错需要重传1001bit,所以总传的位数是1001+1000x*1001。要使检错机制更优秀,那么1001+1000x*1001<1010。所以出错率必须小于9*10
-6

13、一个具有n行k列的块使用水平和垂直奇偶校检位进行检错。假设正好有4位由于传输错误被反转。请推导该错误无法被检测出来的概率表达式。

答:假设正确的bit都是0,错误的bit都是1。那么有nk个位置放置第一个1,nk-1个位置放置第二个1,所以所有可能性为nk(nk-1)(nk-2)(nk-3)。假定离原点的那个点是(p,q),那么合法的矩形个数是(k-p-1)(k-q-1)个。概率表达式如下:

14、利用本章中所述的卷积码,当输入序列是10101010(从左至右)并且内部状态初始为0,试问输出序列是什么?
答:11 01 00 10 10 00 11 00

15、假设使用Internet校检和(4位)来发送一个消息1001 1100 1010 0011,试问校检码的值是什么?
答:按序号按4位一个值分解,从低到高计算,溢出的高位带回低位计算。
0011 + 1010 = 1101
1101 + 1100 = 1001 + 1 = 1010
1010 + 1001 = 0011 + 1 = 1100
所以校检码是1100。

16、x7+x5+1被多项式x3+1除,试问所得余数是多少?
答:-x2+x+1

17、使用本章介绍的标准CRC方法传输比特流10011101。生成的多项式为x3
+1,试问实际传输的位串是什么?假设左边开始的第三个比特在传输过程中变反了。请说明这个错误可以在接收方被检测出来。给出一个该比特传输错误的实例,使得接收方无法检测出该错误。

答:比特流是10011101,生成多项式为1001,多项式阶位为3,所以比特流后面补上3个0得到10011101000,用10011101000整除1001得到余数100,所以最后位串为10011101100。如果第三位变反后,得出的数字不能整除1001,但如果出错后的位串仍能被1001整除,则错误无法检测出来,最简单的就是所以位为0。

18、发送一个长度为1024的消息,其中包含992个数据位和32位CRC校检位。CRC计算采用了IEEE
802标准,即32阶的CRC多项式。对于下面每种情况,说明在信道传输过程中出现的错误能否被接收方检测出来。(1)只有1位错误(2)有2个孤立的1位错误(3)有18个孤立的1位错误(4)有47个孤立的1位错误(5)有一个长度为24位的突发错误(6)有一个长度为35位的突发错误

答:(1)所有的1位错误都能被检测出来(2)所有的双位错误都能检测(3)不能检测出所有偶数个孤立错误(4)可以检测出奇数个孤立错误,以x+1作为因子(5)可以检测出小于r(此处32)突发错误(6)超过r位检测不了

19、在讨论ARQ协议时,概述了一种场景,由于确认帧的丢失导致接收方接受了两个相同的帧。试问如果不会出现丢帧(消息或确认),接收方是否可能会收到帧的多个副本?
答:可能。由于CPU过载,使ACK延迟发送,当ACK到达时,定时器已经超时了。

20、考虑一个具有4kbps速率和20毫秒传输延迟的信道。试问帧的大小在什么范围内,停-等式协议才能获得至少50%的效率。
答:计算带宽-延迟乘积为80bit。要使效率达到50%,必须使传输数据包的时间等于来回传输延迟,所以发送的帧大小至少为160bit。

21、在协议3中,当发送方的计时器已经在运行时,它还有可能启动该计时器吗?如果可能,试问这种情况是如何发生的?如果不可能,试问为什么不可能?

答:可能。假设帧的发送和ACK的回复非常迅速,主函数执行第二个循环的时候,当定时器还在运行时,帧已经被发送出去(但是协议中有stop_timer函数,答案估计有误,除非去掉这个函数)。

22、使用协议5在一条3000千米长的T1中继线上传输64字节的帧。如果信号的传播速度为6微秒/千米,试问序号应该有多少位?
答:为使操作有效,序列空间必须足够大,使得在第一个ACK
返回之前,其他数据还能继续传输。传播时间为3000km*6us/km=18ms。T1是速率是1.536Mbps,64byte 的帧传输需要
0.300ms。所以第一帧到达的时间是18.3ms。ACK
回复需要18ms。所以第一帧发送到收到应答需要36.3ms。所以发送的串口大小必须大到足够保持36.3ms
的传输时间,每个帧需要0.3ms,所以在这段时间内可以传输36.3ms/0.3ms 121个帧。所以需要7位序列。


23、想象一个滑动窗口协议,它的序号占用的位数相当多,使得序号几乎永远不会回转。试问4个窗口边界和窗口大小之间必须满足什么样的关系?假设这里窗口大小固定不变,并且发送方和接收方的窗口大小相同。(图与题目无关,具体见评论)
答:设发送者的窗口边界是(Sl,Su) ,接收者的窗口边界是(Rl,Ru)。窗口大小为W。它们之间的关系是

24、在协议5中,如果between过程检查的条件是a≦b≦c,而不是a≦b<c。试问这对于协议的正确性和工作性有影响吗?

答:这样协议是错,假设使用3位的序列,考虑以下场景:发送了帧7;接收了帧并返回ACK;收到ACK后,发送帧0-6,所有的帧丢失;定时超时后,重发了ACK7;收到ACK之后,A
的AckExpected 0,r.ack=7,NextFrameToSend=7。使A 认为丢失的帧是已经回复了ACK。


25、在协议6中,当一个数据帧到达时,需要检查它的序号是否不同于期望的序号,并且no_ack为真。如果这两个条件都成立,则发送一个NAK;否则,启动辅助计时器。假定else字据被省略掉,试问这种改变会影响到协议的正确性吗?

答:影响了协议正确性,可能造成死锁。假设一批帧已经到达并且被接收。接收者会推进它的窗口。如果所有ACK丢失,发送定时器会超时,并重新发送一个帧,接收者会发送NAK。
如果这个包丢失,那么发送者会保持超时,并发送第一个已经被接收祯,而接收者不再管它, 那么发送者就会不断发送,最终造成死锁。

26、假设将协议6中接近尾部的内含3条语句的while循环去掉,试问这样会影响协议的正确性吗?或者只是仅仅影响了协议的性能?
答:这会造成死锁,这是唯一用来处理ACK 的进程,如果没有这段代码,那么发送者会保持超时,并不做任何事。

27、地球到一个遥远行星的距离大约是9*1010
米。如果采用停-等式协议在一条64Mbps的点到点链路上传输帧,试问信道的利用率是多少?假设帧的大小为32KB。
答:信道利用率为(w/(1+2BD)) ;BD=带宽延迟输出/帧大小;延迟=9*1010/3*108
=300s;带宽延迟输出=64Mbps*300=19.2GB;BD=19.2GB/32KB*8= 75000;信道利用率=6.67*10-4%

28、在前面的问题中,假设使用滑动窗口协议来代替停-等式协议。试问多大的发送窗口才能使得链路利用率为100%?发送方和接收方的处理时间可以忽略不计。
答:信道利用率为(w/(1+2BD)) ,计算w得150001。


29、在协议6中,frame_arrival代码中有一部分是用来处理NAK的。如果入境帧是一个NAK,并且另一个条件也满足,则这部分代码会被调用。请给出一个场景,在此场景下另一个条件非常关键。
答:考虑一下场景:A发送0到B,B接收后返回ACK,但ACK 丢失,
A超时重发;但现在B期望的是1,所以B返回了NAK。如果此时A将r.ack+1,那么它会发送1,错误就被纠正过来了。


30、考虑在一条1Mbps的完美路线(即无差错)上使用协议6。帧的最大长度为1000位。每秒产生一个新的数据包。超时间隔为10毫秒。如果取消特殊的确认计时器,那么会发生不必要的超时事件。试问,平均报文要被传输多少次?
答:假设A发送一个帧,并且正确到达了,但此时没有确认定时器。A超时重发,B 会注意到序列号出错了,它就会发送NAK。所以每个包平均发送两次。

31、在协议6中,MAX_SEQ=2n
-1。虽然这种情况显然是希望尽可能利用头部空间,但我们无法证明这个条件是基本的。试问,当MAX_SEQ=4时也能够正确工作吗?
答:不能,MAX_SEQ=4
时,NrBufs=2,偶数序列使用buffer0,奇数序列使用buffer1。这样的规划意味着,帧4和帧0使用同一个buffer。假设帧0-3已经接收并确认。接收者的窗口包4和0,如果4丢失了,而0到达,这将被放入buffer0,并且arrive[0]也会标记为真。这样循环在代码中被执行一次,一个不规则的消息就会被传送到主机。这个协议要求MaxSeq
必须是偶数。但是其他滑动窗口协议不一定都有这个特性。


32、利用地球同步卫星在一个1Mbps的信道上发送长度为1000位的帧,该信道的传播延迟为270毫秒。确认总是被捎带在数据帧中。帧头非常短,序号使用了3位。试问,在下面的协议中,可获得的最大信道利用率是多少?(1)停-等式(2)协议5(3)协议6
答:帧发送时间需要1000bit/1Mbps=1ms,假设t=0,在t=1ms 时,第一个帧被发送出来。在 t=270+1=271ms
时,第一个帧达到。T=271*2=542ms 时,第一个帧的ACK 到达。所以循环周期是542ms。总共有k 个帧在542ms
被发送,信道利用率=k/542。 k=1,信道利用率为1/542=0.18%(k必须=1)
;k=7,信道利用率为7/542;k=4,信道利用率为4/542=0.74%(窗口空间不应超过序列空间的一半为4))


33、在一个负载很重的50kbps卫星通道上使用协议6,数据帧包含为40位的头和长度为3960位的数据,试问浪费的带宽开销(帧头和重传)占多少比例?假设从地球到卫星的传播时间是270毫秒。ACK帧永远不会发生。NAK帧长40位。数据帧的错误率是1%,NAK帧的错误率忽略不计。序号占8位。
答:50kbps 的信道上使用8 位的序列号,重传率为0.01(错误率为1%),每个安全到达的帧会浪费40bit (header)。每100
帧需要增加40bit
的NAK帧,平均每祯需要付出0.4bit。重传平均每个帧需要付出1%*4000bits=40bit的代价。所以平均每帧需要浪费40+40+0.4=80.4。所以浪
费的带宽和开销占80.4/(80.4+3960)=1.99%。


34、考虑在一个无错的64kbps卫星信道上单向发送512字节长的数据帧,来自另一个方向反馈的确认帧非常短。对于窗口大小为1、7、15、和127的情形,试问最大吞吐量分别是多少?从地球到卫星的传播时间为270毫秒。

答:.假设传输开始时间t=0,第一个帧发送时间为512*8/64kbps=64ms,t=64+270=334ms时到达。t=334+270=604ms时,ACK
返回。这里数据吞吐量为512*8/604ms=6781bps(窗口大小为1)。
若窗口大小为7,发送出去的时间为448ms,在604ms内,可以传输7*512*8=28672bit,吞吐量为28672/604ms=47470.2 bps。
若窗口大小为15、127则超过了卫星通信全速,所以速度为64kbps。

35、在一条100千米长的线缆上运行T1数据速率。线缆的传播速度是真空中光速的2/3.试问线缆中可以容纳多少位?
答:线缆传播速度是200km/ms。所以100km,需要传输时间为500us。每个T1帧为193bit,
在125us内发送出去,所以线上的帧总是为4个帧为772bit。

36、PPP使用字节填充而不是比特填充,这样做的目的是防止有效载荷字段偶尔出现的标志字节造成的混乱。试给出理由说明PPP为什么这么做。
答:PPP 是被设计用来软件处理的,并不是用硬件处理的。对于软件来说处理byte数据,显然比处理bit
数据要简单的多。另外PPP是设计用在modem上,而modem允许按字节传输而不是按bit传输。

37、试问,使用PPP发送一个IP数据包的最低开销是多少?如果只计算PPP自身引入的开销,而不计IP头开销,试问最大开销又是多少?
答:PPP
至少含有2个标志字节,1个协议字节,2个校验字节,总共5字节开销。最大含有2位协议字节,地址和控制各需1个字节,2个协议字节,4个校验字节,总共10 字节开销。

38、在本地回路上使用ADSL协议栈来发送一个长为100个字节的IP数据包。试问一共发送多少个ATM信元?请简要描述这些信元的内容。
答:AAL5帧含有2 个PPP 协议位,100 个有效负载字节,一些填充字节,和8个帧尾。要使这个帧长度为48的整数,填充字节需要34
个。这使得最终AAL5帧长为144bytes。可以分3个ATM信元。第一个信元包含2个PPP 协议字节,46字节的IP包。第二个信元包含后继的48字节IP
包。第三个信元包含最后6个字节IP包,34个填充字节和8个帧尾。

标签

归档

阅读排行

支付宝搜索“559315787”,天天领红包