《数据链路层知识概述》由会员分享，可在线阅读，更多相关《数据链路层知识概述（82页珍藏版）》请在金锄头文库上搜索。
1、,1,数据链路层,第三章,,2,主要内容,3.1 数据链路层设计要点 3.2 错误检测和纠正 3.3 基本数据链路层协议 3.4 滑窗协议 3.5 协议验证 3.6 数据链路层协议示例,,3,3.1 数据链路层的设计要点,为网络层提供的服务 成帧 差错控制 流量控制,,4,链路层基本功能,向网络层提供一个服务接口 处理传输错误 调节数据流（流控）,,5,分组与帧之间的关系,,6,虚拟通信和实际通信,(a) 虚拟通信. (b) 实际通信.,,7,数据链路层提供的服务,无确认的无连接服务 用于低误码率链路或对误码不敏感的业务. (fiber, utp, real-time ) 有确认的无连接服务
2、用于高误码率链路 (Wireless) 有确认的面向连接的服务 保证每个帧真正接收到且只接收一次。 为网络层进程提供一个可靠的位流。,,8,例子,数据链路协议的位置,,9,DLL 将原始码流分解为离散的单元，该单元称为帧。那么接收端如何检测帧的边界呢？或者说接收端如何界定帧的开始和结束呢？讨论4种方法： 字符计数法 含字节填充的分界符法 含位填充的分界标志法 编码违例,成帧,,10,字符计数法,一个字符流 (a) 无差错. (b)有一个差错.,,11,字符填充,(a) 有标志字节作为分界的帧. (b) 字节填充前后的4个字节序列例子.,,12,比特填充,Bit 填充， 标记 01111110
3、(a) 原始数据. (b) 线路上的数据. (c) 删除填充后存储在接收方存储器中的数据.,,13,编码违例,适用于“物理介质上的编码方法中包含冗余信息”的网络。例如有些LAN用2个物理位来编码1位数据。“1”位是“高-低”电平对，“0”位是“低-高”电平对。而“高高”“低低”电平对不用于数据，则可用于帧定界。 优点是没有额外带宽开销,,14,为了保证所有的帧最终传送到（有可能顺序的）目的端，需要三个部件。 Acknowledgments, Timers, Sequence Numbers Acknowledgments: 当接收端正确接收一个帧，它会向发送端返回一个ACK帧用于指示发端该帧已
4、正确接收。 在某些系统，如果接收的帧不正确，接收端会发端返回一个NACK （ Negative ACK ）用于指示该帧没有正确接收. 提示发端不用等待定时器超时就立即发送（重传）一个帧.,错误控制,,15,Timers: 如果没有定时器，当帧丢失或者 ACK/NACK 丢失，会出现什么情况？ 定时器怎么工作呢？当发送一个帧的时候，发端开启一个定时器，当在约定的时间内，发端接收到ACK/NACK，则立即发送（重发）一个帧，且重置定时器，否则当定时超时时，重发该帧。 Sequence Numbers: 主要解决接收端接收到重复帧的问题. 为了避免接收重复帧的问题，给发送的帧分配序列号，这样接收端就
5、能够区分原始帧和重传帧。.,Error Control,,16,流控,流控主要是处理发端与接收端之间速率匹配的问题。通常，流控是个动态的过程，取决于负载强度、接收端缓存大小等，常用的方法： 基于反馈的流控制 基于速率的流控制（从来没有用于DDL）,,17,3.2 错误检测和纠正,纠错码 检错码,,18,错误,数据通信中，链路噪声无处不在，并且研究发现，链路噪声引起的比特错误通常是突发性的，而不是独立的，单比特错误，例如：闪电会引起短暂的突发比特错误。,,19,纠错码,检测和纠正数据中的错误 冗余（redundancy） - 在数据中加入附加的信息。 两种策略： 检错码: 包含足够的冗余比特检错
6、，然后使用NACK告知发端重传。 纠错码:包含足够的冗余比特检测和纠正错误。,,20,海明距离,给定两个码子，对其进行异或运算，然后计算出异或结果中1的个数，两个码子中不相同的位的个数称为海明距离. 它的意义在于：如果两个码子的海明距离为d，则需要d个1位错误才能将一个码子转变成另一个码子。,,21,海明距离,通常，所有2m 种可能的数据报文都是合法的，但是并非所有的2n （n = m+r； m为数据位，r为冗余位）种码子都被用到。给定计算校验位的算法后，可以构造合法码子列表，并且可以从该表中找到海明距离最小的两个码子，此距离是整个编码方案的海明距离。 为了检测d个错误，需要一个距离为d +
7、1 的编码方案 为了纠正t个错误，需要一个距离为2t + 1 的编码方案,,22,奇偶位,保证码子中“1”位的数目是偶数（或者奇数）。. 1000000(1) 1111101(0) 奇偶位的海明距离为2，因此它可以检测单比特错误，但是不能纠错 考虑以下的例子，4个有效码子的编码： “00000 00000“, “00000 11111“, “11111 00000“, and “11111 11111“. 编码距离为5, 可以纠正2个错误。,,23,纠错,设计一种编码方案，每个码子有m个报文位和r个校验位，并且能够纠正所有的单个错误。对于2m 合法报文，任一个报文都对应有n个非法的码子，它们与
8、该报文的距离为1。因此每个合法的报文都要求n+1个位模式供他使用。由于总共有2n个位模式，所以有( n + 1 ) * 2m 4,,24,检错码,纠错码代价很大（计算量和带宽），因此用在无线通信较为合适，但是在铜线或者光缆，错误检测和重传机制往往更加有效。 例如，若误码是独立的，误码率为10-6。则对于1000bit的数据块，需要10个校验位纠正1个单bit错误，1Mbit的需要10Kbit，显然如果仅仅检测错误，每个数据块1个奇偶位就足够了，每一千个数据块额外传输一个块，因此开销小，利用检错/重传机制，则1Mbit只需2001位，相比之下，海明码需要10000位。 最广泛使用的检错码是多项式
9、编码，也称CRC。,,25,Cyclic Redundancy Check,基本思想：将位串看成系数为0或1的多项式。 多项式的算术运算以2为模完成，加减法等同于异或，除法为长除运算。 生成多项式G(x)：事先约定的，最低位，最高位必须是1。 校验和：添加到帧序列多项式中，用于检测传输是否有错误。,,26,Cyclic Redundancy Check,校验和的计算方法： (1) 假设G(x)的阶为r。在帧的低位端加上r个0位，所以该帧现在包含m+r位。对应的多项式为xrM(x)。 (2) 利用模2除法，用对应于G(x)的位串去除xrM(x)的位串。 (3) 利用模2减法，从对应于xrM(x)
10、的位串中减去余数，结果就是将被传输的带校验和的帧，记为：T(x)。,,27,Cyclic Redundancy Check,校验和的计算过程,,28,Cyclic Redundancy Check,分析： 1. 所有的错误都能检测出吗？ 错误多项式E(x)能被G(x)除尽，则这类错误无法被检测。 2. 所有的一位错误都将被检测到。 低阶的多项式可以保护长的帧（K= i j,两个独立的一位错误） 奇数项多项式不可能被x+1除尽(奇数个位发生错误)。 带r个校验位的多项式编码可以检测到所有长度小于等于r的突发性错误。,,29,Cyclic Redundancy Check,通常用到的3种CRC生成
11、多项式： CRC-16 = x16+x15+x2+1 (used in HDLC) CRC-CCITT = x16+x12+x5+1 CRC-32 = x32+x26+x23+ x22+x16+x12+ x11+x10+x8+ x7+x5+x4+ x2+x1+1(used in Ethernet) 尽管复杂，可以用硬件构造出来,,30,3.3 基本数据链路协议,一个无限制的单工协议 一个单工的停等协议 有噪声信道的单工协议,,31,基本数据链路协议,几个假设： 物理层、数据链路层和网络层都是独立的进程，它们通过报文来相互通信。 可靠的、面向连接的服务 机器不会崩溃,,32,协议定义,Conti
12、nued ,协议中需要用到的一些定义。这些定义包含在头文件protocol.h中.,,33,协议定义 (ctd.),协议中需要用到的一些定义。这些定义包含在头文件protocol.h中.,,34,无限制的单工协议,假设条件: 数据单向传输 物理信道无误码，即无帧损坏或丢失 发/接收端缓存无限大 发端/收端的网络层总是处于准备就绪状态,,35,无限制的 单工协议,,36,一个单工的停/等协议,假设: 不再假设收端能够无限快速的处理到来的数据. 基本思想和特点 发端发送一个帧，然后等待确认 (stop and wait.) 确认帧的内容并不重要 数据传输是单向的，但是必须是双向链路，因此用一个半双
13、工的物理信道就足够了,,37,单工的等/停协议,,38,有噪声信道的单工协议,假设: 信道有噪声，因此可能会丢/损坏帧 简单的方法: 发端设置一个定时器，如果在规定的时间内没有接收到ACK，则重发该帧. 这种方法有没有问题？,,39,有噪声信道的单工协议,考虑下面的场景： A 传输一个帧 B 接收到A传来的帧A1 B 产生 ACK ACK 丢失 A 定时器超时, 重传 B 得到A1的副本 ( 将会把副本送到网络层.) (另外一种出现副本的情况是长的时延) 使用序列号 在这个例子里，1bit就够了。 在协议中，发送方在准备下一个数据项目之前先等待一个肯定的确认，则这样的协议称为（ Positiv
14、e Acknowledgment with Retransmission (PAR)/Automatic Repeat reQuest (ARQ)）,,40,有噪声信道的单工协议,一个支持重传的肯定确认协议,Continued ,,41,有噪声信道的单工协议,一个支持重传的肯定确认协议,,42,3.4 滑窗协议,用于双向通信 使用同一条线路来传输两个方向上的数据 反向信道与前向信道有相同的容量. 有两种类型的帧( “kind“ field): 数据（Data） ACK ( 含有最新接收帧的序号).,,43,捎带确认（Piggybacking）,Piggybacking 确认信息附在往外（反向链路）发送的数据帧上的行为。 优点 : 更好的利用信道带宽。 问题: 为了更好的利用带宽，数据链路
