3数据链路层谢希仁计算机网络华科考研复试习题

《3数据链路层谢希仁计算机网络华科考研复试习题》由会员分享，可在线阅读，更多相关《3数据链路层谢希仁计算机网络华科考研复试习题（77页珍藏版）》请在装配图网上搜索。

1、3 数据链路层数据链路层 谢希仁谢希仁 计算机网络计算机网络 华科考研华科考研复试复试 习题习题第三章 数据链路层1 数据链路是什么？物理层实现了bit流透明传输，按bit流进行数据传输存在什么问题？2 如何保证数据在链路上的可靠传输？3 我们以后自己设计一个数据链路层，有没有值得借鉴的案例呢?链路层:工作环境链路层:工作环境n两个 物理上连接的 设备:n主机-路由器,路由器-路由器,主机-主机n数据单元:frame（帧）applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframe物

2、理链路数据链路协议接口卡链路层:实现n通过“adapter（网卡或适配器）”实现ne.g.,PCMCIA 卡,以太网卡 n一般适配器都含有:RAM,DSP 芯片,主机的总线接口,和链路接口applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframephys.linkdata linkprotocoladapter card链路层的服务n帧同步n帧的可靠传输 n什么样的传输是可靠传输？n差错控制n流量控制n链路访问机制（广播式链路）差错控制基本概念n什么是差错控制？n在通信过程中，发现

3、、检测差错并进行纠正n为何要进行差错控制？n不存在理想的信道传输总会出错n产生差错的原因：n信号衰减和热噪声n信道的电气特性引起信号幅度、频率、相位的畸变；n信号反射，串扰；n冲击噪声，闪电、大功率电机的启停等。问题1：帧如何定界（同步）？帧同步n形成帧的四种方法n字符计数法n帧不定长，帧头中用一个字符来表示帧内的字符数n缺点：计数字段一旦出错，将无法再同步帧同步n形成帧的四种方法n带填充字符的首尾界符法n以特定的字符序列为控制字段（起始字符 DLE STX，结束字符DLE ETX）n缺点：依赖于字符集（8位字符和ASCII字符），不通用，也无法扩展帧同步n形成帧的四种方法n带位填充的首尾标记

4、定界法n帧的起始和结束都用一个特殊的位串“01111110”，称为标记（flag）n“0”比特插入删除技术n(参动画)帧同步n形成帧的四种方法n物理层编码违例法nIEEE802协议中：高-低电平对表示“1”，低-高电平对表示“0”。高-高/低-低不表示数据，可以用来做定界符。n只适用于在物理媒体的编码策略中采用了冗余技术的网络；优点：无需填充。n注意n在很多数据链路协议中，使用字符计数法和一种其它方法的组合。第三章 数据链路层1 数据链路是什么？物理层实现了数据链路之间的bit流传输，按bit流进行数据传输存在什么问题？2 如何保证帧在数据链路上的可靠传输？n我们如何知道帧是否出错？n若出错了

5、怎么办?n如何使帧的发送速率和接收速率匹配？问题2差错控制和流量控制n差错控制n差错控制编码n检错码和纠错码n差错控制技术n差错控制的基本方法：接收方进行差错检测，并向发送方应答，告知是否正确接收。n流量控制n自动请求重传Automatic Repeat Request（ARQ）n停等 ARQnGo-back-N ARQn滑动窗口协议 差错控制编码原理EDC=错误检测校正（Error Detection and Correction(冗余数据)）位D =由检验位保护的数据,可包括首部字段 错误检测不可能达到 100%可靠!协议算法可能会忽略了某些错误,但比例极小 较大的 EDC 字段可以产生较

6、好的检错和纠错效果差错控制编码n奇偶检验（检错码）n海明纠错码（纠错码）n循环冗余码(CRC)（检错码）奇偶检验n原理：n在原始数据字节的最高位（或最低位）增加一个奇偶校验位，使结果中1的个数为奇数（奇校验）或偶数（偶校验）。n例如：1100010增加偶校验位后为11100010n注意：n只能检测出奇数个位错，偶数个位错则不能检出。海明纠错码n海明纠错码n海明纠错码的格式n码字的编号从左到右，最左边是第一位，其中2的幂数位是检验位，其余是k个数据位(信息元)。n海明纠错码格式如下：20 21 22 23 24 p1 p2*p3*p4*p5 *-信息元 P-校验位海明纠错码n海明码的编码与译码的

7、方法n用矩阵乘法求检验位，并且找出错误位。n设编码长度为 n=2r 1，其中r为校验码的位数。数据位长度 k=n r。n校验位插入到编码序列的2j-1(j=1,2,.,r)的位置上；由r(样本)建立一个(2r-1)行*r列的矩阵。海明纠错码n将编码字写成串形式的一维向量其中，l1=l2=lr=1或0(l=0为偶校验，l=1为奇校验)；bij =1 或 0 海明纠错码n例:按下列步骤将数据(信息)1100进行编码，设校验位为r=3。解:(1)编码长度 n=2r 1=7 数据位 k=n r=4 校验位 r=3 海明纠错码 (2)编码过程由矩阵乘法得，p1=0,p2=1,p3=1 解得海明码为 01

8、11100循环冗余码(CRC)n循环冗余码（CRC）n基本思想n收发双方约定一个生成多项式G(x)（其最高阶和最低阶系数必须为1），发送方在帧的末尾加上校验序列，使带校验序列的帧的多项式能被G(x)整除；接收方收到后，用G(x)除多项式，若有余数，则传输有错。n多项式码n将位串看成系数为0或1的多项式如：110001，表示成多项式 x5+x4+1循环冗余码(CRC)n循环冗余码（CRC）nCRC的计算算法循环冗余码(CRC)n循环冗余码（CRC）n常用的CRC生成多项式nCRC-12=x12+x11+x3+x2+x+1nCRC-16=x16+x15+x2+1nCRC-CCITT=x16+x12

9、+x5+1n检错能力：CRC-16和CRC-CCITT可以捕捉突发错长度小于16的全部错误、长度为17的突发错的99.998、长度为18以上的突发错的99.997。差错编码比较n结论：n 1.CRC检错能力强。n 2.是线性码，有良好的结构，易于硬件实现。差错控制和流量控制n差错控制n差错控制编码n检错码和纠错码n差错控制技术n差错控制的基本方法：接收方进行差错检测，并向发送方应答，告知是否正确接收。n流量控制n自动请求重传Automatic Repeat Request（ARQ）n停等 ARQnGo-back-N ARQn滑动窗口协议 停止等待协议的原理n原理n发送方发送完一帧数据后，必须等

10、待接收方的确认帧返回，确认数据被正确接收后才能继续发送下一帧。停止等待协议的原理n过程从主机取数据上交主机DATA1DATA2结点结点 A结点结点 BACKACK思考n问题1：发送帧出错或丢失怎么办？n设置计时器，利用超时中断防止因帧丢失所造成的死锁。n问题2：应答帧出错或丢失怎么办？n设置帧序号，利用序号检查是新帧还是重复帧。n问题3：帧序号字段需占用多少位？n根据停等协议的定义，表示帧发送序号的字段只需占用一位，因为只需检查前后两帧的顺序是否相同，而不注重各帧的顺序号本身的值是多少。帧序号讨论n例：发送帧本身序号为 0 1 2 3 4 5 6 7 停等协议帧序号为 0 1 0 1 0 1

11、0 1 同理，帧确认序号也只需占用一位。n为便于判断序号的正确性，通常定义帧确认序号(ACK)为期望发送方下次发送的帧序号(SEQ)，表达式为：ACK=SEQ+1(mod 2)单工停等协议n过程n发送方将当前信息帧作为待确认帧保存在缓冲区n发送数据的同时起动计时器n接收方收到数据后返回一个确认帧n若接收方收到的数据有错，则丢弃n发送方若在规定时间内没有收到确认帧，则计时器清零，重发缓冲区内的信息帧 单工停止等待协议n过程(参考动画演示:停止等待协议)frame iACK iframe i+1ACK i+1frame i+2frame i+2ACK i+2frame i+3ACK i+3fram

12、e i+3ACK i+3发送方接收方超时超时帧丢失 重发ACK丢失 重发，丢弃重复帧超时frame i+1丢弃重复帧单工停等协议双工停等协议n问题1：如何区分发送帧(数据帧)和应答帧？n在帧的控制信息中增加一个帧类型的字段。n问题2：如果某站收到对方的数据后，在给对方发送应答帧的同时，又有数据帧要发往对方，能不能只发送一帧？n采用“背回”(Piggybacking)技术。可以在数据帧中增加一个接受顺序号字段(ACK字段)以存放应答信息，于是对方在收到数据帧的同时也得到了应答。背回技术的讨论n背回应答的优点：n减少了帧的发送数目(因为减少了单独应答帧)；n能有效地利用通道，且接收站的“帧正确到达

13、”中断次数和接收站的输入缓冲区均可以减少。n但是背回应答增加了协议的复杂性。背回技术的讨论n问题3：高层并非始终有信息发送，应答帧何时发送？n解决办法：设置ACK计时器连续ARQ协议n连续ARQ又称为Go-Back-N ARQn当出现差错必须重传时，要向回走N个帧，然后开始重传。n原理n发送端连续发送至发送缓冲区窗口满n接收缓冲区窗口大小为1帧，对丢弃帧不确认n发送方设置超时，若超时回退若干帧到未被确认帧开始重传n接收方从出错帧起丢弃所有后继帧连续ARQ协议n特点n发送方需要较大的缓冲区，以便重传n减少了等待时间，提高了吞吐量n发送帧和接受帧都要进行编号n适于信道出错率较少的情况n问题n信道误

14、码率高时，对损坏帧和非损坏帧的重传非常多，反而降低效率连续ARQ协议n注意的问题n接收端按序接收。例如：2号帧出错但收到正确的3号帧仍然丢弃3号帧从2号帧开始重传nACK1表示确认0号帧DATA0，期望下次收到1号帧，依次类推n思考n实际的连续ARQ利用一个计时器实现N个独立超时计数器的功能，思考这如何实现？滑动窗口协议n采用窗口的原因n应对以发送出去但尚未被确认的帧的数目加以限制。n要重复循环使用帧的序号，避免无止境的帧序号的增大。n发送窗口n在发送端。用来对发送方进行流量控制。n发送窗口的大小：能够存放的待确认帧的最大数目。n接收窗口n在接收端。用来指示接收方允许接收的帧的序号。滑动窗口协

15、议n滑动窗口实例：发送窗口=2；接收窗口=1 n初态：发送端无数据发出，接受端0号窗口打开准备接收数据n发送端发出0号帧，0号窗口被占用；此时接收端尚未收到数据n发送端发出1号帧，1号窗口被占用；此时接收端尚未收到数据。发送方停止发送数据。n接收端0号帧收到，关闭其0号窗口，打开1号窗口等待接受n发送方收到接收端发来的确认后，关闭0号窗口n发送方发送2号帧，占用2号窗口，然后暂停发送n依次类推循环，达到了限止发送帧的数目，又避免了帧序号重复时的歧义。滑动窗口协议n滑动窗口实例：发送窗口=2；接收窗口=1滑动窗口协议n各种协议规定的缓冲窗口大小n停止等待：发送窗口=1，接收窗口=1nGo Bac

16、k n：发送窗口1，接收窗口=1n滑动窗口：发送窗口1，接收窗口1 滑动窗口结论n令发送窗口为WT，接收窗口为WR。发送序号用n个比特表示。n结论1：若WR1，则WT2n1n例如n=3，（WT）max7n结论2：WR2n/2，WT=WR=2n/2n例如n=3，则WT=WR=4链路层的服务n帧同步n帧的可靠传输 n什么样的传输是可靠传输？n差错控制n流量控制n链路访问机制（广播式链路）？链路和协议有三种类型的“链路”:n点对点(e.g.PPP,SLIP)n广播式(共享线路或介质;e.g,以太网,无线网,etc.)n交换式(e.g.,交换式以太网,ATM etc)点对点的数据链路协议（DLC）n一

17、方发,一方收,一条链路:比广播信道简单的多n无需介质访问控制n不必进行MAC寻址ne.g.,拨号链路,ISDN 线路等n常见的点对点DLC协议:nSLIP(Serial Line Internet Protocol)nPPP(point-to-point 协议)nSDLC:Synchronous Data Link Control(SNA的面向比特的数据链路规程)nHDLC:High level data link control(ISO高级数据链路控制)多点访问协议n一条共享的通信信道 n两个或多个结点可同时发送信号:相互干扰 n在某一时刻只有一个结点可以成功地发送信号 n多点访问协议:n分

18、布式的算法来决定如何共享信道,i.e.,决定工作站何时可以发送n注意：有关共享通道的通信（协商）也必须在该通道自身上解决!n我们希望多点访问协议能够解决什么问题:n同步还是异步 n了解其他站点的信息 n健壮性(e.g.如何对待信道错误)n性能点到点数据链路层协议案例案例1：高级数据链路控制规程nHDLCn面向比特的数据链路层协议(规程）n使用HDLC的语法可以定义多种具有不同操作特点的链路层协议。案例1：HDLCn链路基本配置原理图命令命令(B)响应响应(B)主站主站A从站从站B非平衡配置：点非平衡配置：点-点点命令命令(B/C/D)响应响应(B)响应响应(C)响应响应(D)主站主站A从站从站

19、B从站从站C从站从站D非平衡配置：点非平衡配置：点-多点多点命令命令(B)命令命令(A)响应响应(B)响应响应(A)复合站复合站A复合站复合站B平衡配置平衡配置案例1：HDLCnHDLC链路基本配置类型n非平衡配置：点对点工作；多点工作n由一个主站控制整个链路的工作。主站发出的帧叫做命令。受控各站叫做次站或从站。从站发出的叫做响应。多点工作时主站与每个从站都有分开的逻辑链路。n平衡配置：点对点工作n链路上都是复合站，平等发送数据，不需要对方的允许。案例1：HDLCnHDLC涉及三种类型的站：n主站（Primary Station）n主要功能是发送命令（包括数据），接收响应，负责整个链路的控制（

20、如系统的初始、流控、差错恢复等）；n从站（Secondary Station）n主要功能是接收命令，发送响应，配合主站完成链路的控制；n复合站（Combined Station）n同时具有主、从站功能，既发送又接收命令和响应，并负责整个链路的控制。案例1：HDLCn帧的一般结构案例1：HDLCn标志字段n以0111 1110作为起止的帧边界标记n零比特填充法n原因n避免数据信息字段与标志字段F相同，引起帧边界错误，达到透明传输。n采用方法n发送端：n利用硬件扫描数据信息字段，遇到5个1即添加一个0n接受端：n硬件扫描到连续5个1，因为发送端扫描填充过0，紧接的必然是0，去掉这个0案例1：HDL

21、Cn地址字段n非平衡方式写入从站地址，平衡方式写入确认站地址n全1地址为广播方式，全0为无效地址，有效地址254个n地址字段可扩展案例1：HDLCnHDLC的三种帧类型n信息帧（Information Frame）n监督帧（Supervisory Frame）n无编号帧（Unnumbered Frame）案例1：HDLCn三种HDLC帧的控制字段案例1：HDLCn三种HDLC帧的控制字段n序号（Seq）n当前发送的信息帧的序号。使用滑动窗口技术，3位序号，发送窗口大小为4。n捎带确认（Next）n捎带下一个准备接受的帧序号，而不是最后一个已收到的帧序号。n探询/结束 P/F位（Poll/Fin

22、al）n命令帧置“P”，响应帧置“F”。有些协议，P/F位用来强迫对方机器立刻发监督帧；n多终端系统中，计算机置“P”，允许终端发送数据；终端发向计算机的帧中，最后一个帧置为“F”，其它置为“P”。案例1：HDLCn三种HDLC帧的控制字段n监督帧的类型（Type）案例1：HDLC程n三种HDLC帧的控制字段n无编号帧n可以用来传控制信息，也可在不可靠无连接服务中传数据；n利用3、4、6、7、8共5个bit来表示不同的功能。案例1：HDLCn n半双工“点-点”数据传送n n全双工链路，单向传输n n全双工链路，双向同时传输案例1：HDLCn n半双工“点-点”数据传送n几点说明：n类型(TY

23、PE)：对于信息使用I帧，对于S帧则使用RR、REJ、RNR或SREJ。nP/F指明探询或最后帧是否建立。案例1：HDLC案例1：HDLC案例1：HDLCn n全双工链路，单向传输全双工链路，单向传输主站从站I,0,0I,1,0I,2,0I,3,0,PRR,1,FI,1,0I,2,0I,3,0,PI,4,0RR,4,FI,5,0I,6,0X 干扰案例1：HDLCn注意：n主站在发送了探询之后仍能继续发送数据。另外，在发送信息帧7以后，发送顺序计数复原为“0”，这个系统在收到确认信息以前所能发送的最大信息帧数目等于4。案例2：PPP 设计要求 RFC 1557n分组成帧:将网络层的分组封装入数据

24、链路层的帧 n同时可以承载任意网络协议的网络层数据(不仅仅是 IP)n提供向上分用的能力n位流透明:在数据字段中，必须能携带任意组合的位流n错误检测(无需校正)nPPP 无需做的工作n无错误校正/恢复n无流量控制n允许失序递交 n无需支持多点链路(e.g.,轮询)出错恢复、流量控制、分组重新排序 都被赶到更高层去解决了!PPP 数据帧nFlag:定界符(成帧)nAddress:没用(只有一种选择)nControl:没用;将来可能会用作多点控制字段nProtocol:本帧传递数据的上层协议(eg,PPP-LCP,IP,IPCP,etc)PPP 数据帧ninfo:所携带的上层数据ncheck:CR

25、C 进行错误检测PPP 数据控制协议在交换网络层数据之前,数据链路的对等双方必须n配置 PPP 链路(最大帧长度,认证等)n学习/配置网络 就IP而言:携带 IP 控制协议(IPCP)报文(protocol field:8021)给出比要配置/学习的IP 地址本章小结n数据链路层的基本概念(数据链路层的基本功能，帧的格式，形成帧的四种方法)n差错控制中的编码技术(海明纠错码，循环冗余码(CRC)n停止等待协议的原理(单工，双工停等协议)n连续ARQ协议n滑动窗口协议及分析方法n高级数据链路控制规程的相关概念nHDLC的帧格式及各字段的意义nHDLC的三种帧类型n半双工“点-点”数据传送n全双工“点-点”数据传送