第三章数据链路层_第1页
第三章数据链路层_第2页
第三章数据链路层_第3页
第三章数据链路层_第4页
第三章数据链路层_第5页
已阅读5页,还剩32页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、计算机网络 第三章 数据链路层主要内容z组帧z差错检测z可靠交付y停-等协议y滑动窗口协议z数据链路层协议举例yHDLC协议yPPP协议1. 组帧z 使用字符填充的起止标记法y使用特殊的字符表示帧的开始与结束。y使用字符填充(在特殊字符前加转义字符)解决透明传输问题。y该方法依赖于特定的字符编码集,帧长必须是8比特的整倍数,灵活性差,处理开销大。z 使用比特填充的起止标记法y使用一个特殊的比特模式(01111110)作为帧的起始与结束标志。y使用比特填充(连续5个1后插入一个0)解决透明传输问题。y该方法不依赖于特定的字符编码集,灵活性强,处理简单。z 违法编码法y使用物理层编码中的无效编码表

2、示帧的边界。字符填充示例比特填充示例2. 差错检测z出错的类型y单个错:由随机的信道热噪声引起,一次只影响1位。y突发错:由瞬间的脉冲噪声引起,一次影响许多位,用突发长度表示突发错影响的最大数据位数。z差错编码的类型y检错码:只能检测出传输错误,但无法自行纠正,通常与反馈重传结合起来进行差错恢复。y纠错码:能够检测出传输错误并纠正。如何检测与纠正错误?z 码字(codeword):由m比特的数据(消息)加上 r 比特的冗余(校验位)构成。z 有效编码集:由2m个有效码字组成。z 检错:当收到的码字为无效码字时检测出错误。z 海明距离(Hamming Distance):两个码字的对应位上取值不

3、同的位数。z 纠错:将收到的无效码字纠正到距其最近的有效码字。z 检错码与纠错码的能力都是有限的。编码集的检错与纠错能力z 编码集的海明距离:编码集中任意两个有效码字的海明距离的最小值。z 检错能力:为检测出 d 比特错误,编码集的海明距离至少应为 d+1;奇偶校验是能够检测出1比特错误的检错码。z 纠错能力:为纠正 d 比特错误,编码集的海明距离至少应为 2d+1。z 结论:差错编码的检错/纠错能力与编码集的海明距离有关。海明距离越大,检错纠错能力就越强;但所需的冗余信息也越多,编码效率就越低。 二维奇偶校验z 对一个 kn 比特的信息矩阵的每一行和每一列计算奇偶校验位。 循环冗余码(CRC

4、)z CRC是一种多项式编码,它将位串看成是某个一元多项式的系数,如1011001看成是一元多项式X6 + X4 + X3 + 1的系数。z 信息多项式M(x):由 m 个信息比特为系数构成的多项式。z 冗余多项式R(x):由 r 个冗余比特为系数构成的多项式。z 码多项式T(x):在 m 个信息比特后加上 r 个冗余比特构成的码字所对应的多项式,表达式为 T(x) = xrM(x) + R(x)。z 生成多项式G(x):双方预先确定用来计算R(x)的一个多项式。z 编码方法:用对应于 G(x) 的位串去除对应于 xrM(x) 的位串,所得的余式即为 R(x),将其附加到信息比特串的后面一起发

5、送。z 校验方法:用对应于 G(x) 的位串去除对应于 T(x) 的位串,若余式为0则认为传输正确,否则认为传输错误。z CRC码检错能力强,实现简单快捷,是应用最广泛的检错码。CRC的编码及校验z 例1:G(X) = X4 + X + 1,对10110011进行CRC编码。z 例2:仍取G(X) = X4 + X + 1,判断收到的位串100101111001是否有错? 常见的CRC多项式CRCC(x)CRC-8X8 + X2 + X1 + 1CRC-10X10 + X9 + X5 + X4 + X1 + 1CRC-12X12 + X11 + X3 + X2 + 1 CRC-16X16 +

6、X15 + X2 + 1 CRC-CCITTX16 + X12 + X5 + 1 CRC-32X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1 3. 可靠交付z差错恢复的两种办法:y使用纠错码,由接收端自动纠正错误。y使用检错码,采用自动重传请求(ARQ)保证可靠交付。这是数据链路层(及传输层)上最常使用的可靠交付方式。z两种ARQ算法:y停-等y滑动窗口 3.1 停-等算法z 基本思想:发送方发完一帧后即停下来等待确认;如果收到一个确认,接着发送下一个帧;如果定时器超时,重发刚才的帧

7、。z 停-等算法的四种情形。z 停-等算法的超时值对性能影响很大,必须仔细选择。z 为区分新帧和重发帧,停-等算法使用一比特的帧序号。停-等算法的四种情形停-等算法的过-发送方 1)帧序号初始化为0 2)从缓冲区中取出一个帧,加上当前帧序号发送。 3)等待确认 i)收到确认帧,且帧序号与当前维护的帧序号不同,将 帧序号加1,从缓冲区中取出一个新的帧,加上当前 帧序号发送。 ii)收到确认帧,且帧序号与当前维护的帧序号相同,重 发当前序号的帧。 iii)收到错误的确认帧,重发当前序号的帧。 iv)定时器超时,重发当前序号的帧。停-等算法的过程-接收方 1)帧序号初始化为0(表示当前期望接收的帧序

8、号) 2)等待接收 3)帧到达 i)帧校验正确,且序号为当前期望接收的帧序号,将帧 放入接收缓冲区,帧序号加1,放入确认帧中发送。 ii)帧校验正确,但序号与当前期望接收的帧序号不同, 丢弃帧,重发确认帧。 iii)帧校验错误,丢弃帧,重发确认帧。信道利用率与流水线技术z停-等算法在传输延迟较长的信道上传输效率很低。z假如将链路看成是一根管道,数据是管道中流动的水,那么停-等算法无法使数据充满管道,因而信道利用率很低。z管道的容量通常用延迟-带宽乘积表示,它表示发送端在收到第一个帧的确认前最多可以发送的数据量。z滑动窗口机制允许发送端连续发送多个帧来尽可能多地填充管道,从而提高信道的利用率。3

9、.2 滑动窗口z滑动窗口是计算机网络中最著名的算法,它可以应用在数据链路层及传输层,用来完成三个不同的任务:y在不可靠的链路(网络)上可靠地传输数据y保持数据的传输顺序y支持流量控制z在数据链路层上,以上三个功能组合在一个滑动窗口协议中。发送窗口z 发送窗口:发送端允许发送的帧序号表。z 发送窗口大小:发送端最大允许的未确认帧数目。z 发送窗口下沿:最早发送但尚未被确认的帧序号。z 发送窗口上沿:(发送窗口下沿发送窗口大小1)mod 2n。 z 当收到对发送窗口下沿帧的确认时,发送窗口整体向前滑动一个序号,将已被确认的帧移出发送窗口,并加入一个新的序号。(图)z 发送窗口中的帧都保留在缓冲区中

10、以备重传,当某个帧被移出发送窗口时,同时从缓冲区中删除。z 当发送窗口满时,停止从网络层接收数据,直到有一个缓冲区空出来为止。发送窗口和接收窗口图示接收窗口z 接收窗口:接收端允许接收的帧序号表。z 接收窗口大小:接收端允许接收的最大帧数。z 接收窗口下沿:接收端按顺序期待接收的帧序号。z 当接收端收到窗口下沿帧且校验正确时,将帧交给网络层,向发送方发回一个确认,然后窗口整体向前滑动一个序号。(图)z 接收窗口的大小可以设为任意值,通常的设置有两种:y接收窗口大小 = 1:意味着接收方只能按顺序接收;y接收窗口大小 = 发送窗口大小:意味着接收方可以不按顺序接收,但接收方交给上层实体的数据总是

11、有序的。捎带确认z 捎带确认(piggybacking):将确认序号携带在数据帧中传输,提高线路的效率。z 推迟确认:当需要发送确认但没有要发送的数据时,可以让确认信息推迟一小段时间再发送;这一小段时间后若数据仍未准备好,接收端必须立即发送一个单独的确认帧。z 接收端对正确收到的若干个帧同时进行确认,通常用对某一个帧的确认来表示对该帧之前的所有帧进行确认。Go Back nzGo back ny当接收端收到一个出错帧或乱序帧时,丢弃所有的后继帧,并且不为这些帧发送确认;发送端超时后,重传所有未被确认的帧。y该策略对应接收窗口为1的情况,即只能按顺序接收帧。y若信道的误码率较高,这种方法会浪费很

12、多带宽,但对接收端内存的需求不大。Go Back N 示意图选择重传z选择重传y当接收端收到一个出错帧或乱序帧时,后续到达的帧只要校验正确且落在接收窗口内,都放入接收缓冲区中;发送端超时后只重传最早发送但未被确认的帧。y该策略对应接收窗口大于1的情况。y选择重传通常使用一个否定的确认(NAK)对校验出错或疑为丢失的帧进行确认,以便发送端尽快重传该帧。y当接收窗口很大时,这种方法要求接收端有较大的内存,但它不浪费带宽。选择重传示意图有限序号与窗口限制z 使用Go Back N协议,发送窗口的大小不能超过 2n-1。z 使用选择重传协议,若发送窗口与接收窗口大小相同,则发送窗口的大小不能超过2n-

13、1。4. 数据链路协议举例z高级数据链路控制(HDLC)z点到点协议(PPP)4.1 HDLCz 帧结构:y标志:01111110,标识一帧的开始与结束,以及作为帧间填充。y地址:在点到多点线路中用于指明通信的终端地址,在点到点线路中用于区分命令和响应。y控制:用于构成各种命令和响应,对链路进行监控。y信息:可以是任意的二进制比特串。y校验:CRC码,对两个标志之间的帧内容进行校验。帧类型z 信息帧:y以控制字段的第一比特为“0”标志。y用于传送数据,数据放在信息字段中。y采用滑动窗口协议,N(S)为发送序号,N(R)为捎带确认。帧类型(续)z 监视帧:y以控制字段的第一、二比特为“10”标志

14、。y用于差错控制和流量控制,没有信息字段。yS1S2:决定监控帧的类型 类型0:接收准备好 类型1:否定确认 类型2:接收未准备好 类型3:选择拒绝帧类型(续)z 无编号帧:y以控制字段的第一、二比特为“11”标志。y提供链路的建立、拆除及其它控制功能。y不包含 N(S) 或 N(R) 字段。y M1M5:修正位,构成各种链路命令和响应HDLC的访问规程z链路层的操作分为三个阶段:y建立链路:一方发送一个置模式命令,另一方发送UA帧进行响应,并初始化链路变量。y传输信息:x双方使用滑动窗口协议进行数据传输控制;x对收到的信息帧使用捎带确认或监视帧进行响应;x对检测到错误的帧使用否定确认或选择拒绝要求重发;x未准备好接收下一帧时,用接收未准备好暂停对方的发送。y断开链路:一方发送一个断连命令,另一方用一个UA帧进行响应。4.2 PPP协议zPPP是因特网中广泛使用的点到点

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论