计算机网络 第三章数据链路层.ppt
《计算机网络 第三章数据链路层.ppt》由会员分享,可在线阅读,更多相关《计算机网络 第三章数据链路层.ppt(71页珍藏版)》请在三一文库上搜索。
1、第三章 数据链路层,数据链路层的功能 组帧 差错检测和纠正 基本数据链路协议 滑动窗口协议 数据链路层协议实例,3.1 数据链路层的功能,物理层只负责在通过传输介质相连的机器之间传输无结构的原始比特流,是不可靠的。 数据链路层将相邻节点间不可靠的物理连接的数据电路转换成为可靠的数据链路,为网络层提供透明的服务。 为实现转换: 将物理层的无结构原始比特流划分成一定长度的结构数据单元帧(frame),即组帧(Framing)。 对帧进行差错控制(error control),实现检错/纠错功能。 通过合适的流量控制(flow control)协议保证收发双方的传输同步。,3.1 数据链路层的功能,
2、Relationship between packets and frames.,3.1 数据链路层的功能,虚拟通信和实际通信,数据链路协议的位置和作用,数据链路协议的位置和作用,数据链路层为网络层提供的服务,3种基本的服务: 无确认的无连接服务: 源机器向目的机器发送独立的帧,而目的机器不需作出确认。事先没有建立连接,事后也不存在释放。对于丢失和错误的帧也不试图去恢复。恢复工作留给上层完成。 适用于误码率很低或音视频实时传输的情况,如LAN。 有确认的无连接服务: 仍然不建立连接,但每一个帧都单独确认。发送方会重发丢失和出错的帧。 适用于无线系统(wireless systems)之类的不可
3、靠信道。 有确认的面向连接服务: 传输分为建立、传输和拆除三个阶段,且每一个帧都单独确认。主要用于WAN。,3.2 组帧,将物理层的比特流划分成帧的4种方法: 字符计数法(Character Count) 带字符填充的首尾定界符法(Starting and ending characters with character stuffing) 带位填充的首尾标志法(Starting and ending flags with bit stuffing) 物理编码的违例码法(Physical layer coding violations),字符计数法,在帧头中使用一个字段来标明帧内的字符数。 一
4、旦计数值出错,将再也无法同步。 很少单独用,一般与其它方法结合使用。,带字符填充的首位定界符法,每一帧以ASCII字符序列DLE STX(Data Link Escape Start of TeXt)开头,以DLE ETX(Data Link Escape End of TeXt )结束。 若帧的数据中出现DLE字符,发送方则插入一个DLE字符,接收方会删除这个DLE字符。 只能用于已被淘汰的面向字符型协议。,带位填充的首位标志法,每一帧使用一个特殊的位模式(如01111110)作为开始和结束的标志字节。 当发送方在帧的数据中遇到5个连续的1时,自动在其后插入一个0,接收方会自动删除5个连续的
5、1后面跟着的一个0。 用于流行的面向比特型协议,如HDLC。,物理编码的违例码法,只能用于当物理信号的编码具有冗余码字时,利用这些冗余的码字来作为帧的边界。 例如采用曼彻斯特编码或差分曼彻斯特编码中1/2位周期处不跳变的违例码来标示帧边界。使用差分曼彻斯特编码的IEEE 802.5令牌环网中: 帧的起始符:JK0JK000 帧的结束符:JK1JK1IE 其中J为“1”的违例码;K为“0”的违例码; I表示后继帧位; E为差错检测位。 帧的其它地方绝对不会出现这样的边界码字。,3.3 差错的检测和纠正,涉及两方面理论与技术: 差错检测 差错控制编码 差错纠正 前项纠错 重发出错帧(可与流量控制一
6、起实现),差错控制编码,发送端在发送的数据块中加入一定的冗余信息,使数据块与冗余信息之间建立某种关联的关系,接收端通过验证这种关系是否存在,来判定数据在传输过程中是否出错。 在数据块中加入冗余信息的过程叫差错编码,有两种基本的差错编码策略: 检错码(error-detecting code):只能检查是否有错,但不知错在何处的编码。 纠错码(error-correcting code):不但能检查出错误,且能确定错误之处并予以纠正的编码。 任何一种差错编码都不能保证百分之百的准确。,检错与纠错能力的分析,设一帧包含m个数据(报文)位和r个冗余位,则总长度为n = m + r。把长度为n位的单元
7、称作n位码字(codeword)。 在n位码字的编码集中,有效码字数为2m个,总码字数为2n个,显然存在2n - 2m个码字是无效的码字。 若一个有效码字由于差错变成一个无效码字,就能判断出有错。 若一个有效码字错成了另一个有效码字,则错误就检测不出来了。 两个码字中对应比特位取值不同的位的个数称作海明距离(Hamming Distance)。如10001001和10110001的海明距离为3。 在一个编码集中,任意两个有效码字的海明距离的最小值称作该编码集的海明距离。检错与纠错的能力取决于海明距离。,有关检错和纠错的两个重要结论,如果要检测出d个比特错误,则编码集的海明距离至少应为d+1。
8、说(证)明:若一个有效码字只出错 d+1个比特,则肯定变为一个无效码字,从而被检测出来。若出错d+1,则变为有效码字,不能检出。 如果要纠正d个比特错误,则编码集的海明距离至少应为2d+1。 所谓纠错是将无效码字恢复成与它海明距离最近的有效码字。显然这并不是百分之百正确。 说(证)明:若出错 d个比特,则该无效码字与有效码字的海明距离仍然是最近的。若出错超过d个比特,就违背了纠错的原则。 考虑一个实例:编码集中有四个有效码字(000000,000111,111000,111111),海明距离为3,则可检测3-1 = 2个比特错,可纠正 (3-1)/2 = 1个比特错。,奇偶校验(Parity
9、Check),在数据后面增加一个奇偶校验位(parity bit)的编码,奇偶校验位的选取原则是使码字内的1的数目为偶数(偶校验)或奇数(奇校验)。 如:10110101变为101101011(偶校验)或101101010(奇校验)。 这种编码可检测单比特错,其海明距离为2。,垂直奇偶校验,水平奇偶校验,水平垂直奇偶校验,海明码(Hamming),海明码由海明于1950年提出,是一种可纠正单比特错的编码。 通过在特定的位置(2k,k0,即1,2,4,8,16)加入与某些特定数据信息位相关的奇偶校验位就构成了海明码。每位数据信息位可用2k的和来表示(如11=20+21+23),则该数据信息位是由
10、展开式中的奇偶校验位(2k )位来校验的,如第11位的数据信息位分别由1,2,8位进行校验。 考虑数据1100001的海明码(偶校验),海明码(Hamming),海明码的纠错,接收方设置一计数器清零。 检查所有的奇偶校验位(2k,k0)。 若校验出错,则将出错的奇偶校验位号加进计数器。 全部检查完后,若计数器为0,则表示没有错误;若不为0,则计数器中的值就是出错的位号,对该位求反即纠正了错误。 在下图中:S表示发送数据;R表示接受数据;C表示检查校验后发现位1和位8校验出错,则是位9=1+8数据位出错;F是对位9数据位求反纠正。,海明码的纠错,CRC检错码,CRC(Cyclic Redunda
11、ncy Code,循环冗余码,也叫多项式编码)是一种高性能的检错编码。 将位串中每一位二进制数看成是一个一元多项式的系数,则一个k位帧可表示成一个阶数为k-1的从xk-1到x0的k次多项式,如110001表示成x5+x4+x0。 多项式以2为模运算,其加减法及除法中的减法都同于异或操作,只有被除数和除数等长时才作减法。,CRC检错码,设发送方发送m位长的帧多项式为M(x),收发双方需共同商定一个r阶的生成多项式G(x),必须m r+1。发送方在M(x)后面增加一个冗余多项式R(x)构成带校验信息的传输帧多项式T(x),T(x)必须能被G(x)整除。当接收方收到T(x)后,只要检查T(x)和G(
12、x)的整除关系是否存在即可判定传输是否出错。具体算法: 对M(x)左移r位,得到多项式xrM(x),帧长为m+r位。 按模2除法将xrM(x)除以G(x)。 按模2减法将xrM(x)减去中所得余数,即得到多项式T(x)。,CRC检错码举例,帧为1101011011,G(x)=x4+x+1(其位串为10011) xrM(x)的位串为11010110110000 xrM(x)除以G(x)的余数位串为1110 最终T(x)的位串为11010110111110,三个国际标准的生成多项式,CRC-12 = x12+x11+x3+x2+x1+1 CRC-16 = x16+x15+x2+1 CRC-CCIT
13、T = x16+x12+x5+1 CRC-16和CRC-CCITT这种16位校验码可检测出所有的单位错、两位错、奇数位错、突发长度小于或等于16的突发错、17位突发错的99.997%、18位或更长突发错的99.998%。,差错控制策略,检/纠错码的检/纠错能力与编码集的海明距离有关,海明距离越大,检/纠错能力就越强,但所需的冗余信息就越多,编码效率就越低。 由于纠错码比检错码要求更大的海明距离,且技术复杂,纠正可靠性不高,所以一般很少使用,只有在没有反馈信道的单工通信中,为了确保可靠才会采用。 在大多数通信中采用的是检错编码。接收方收到帧后,对其进行校验检查,并发回相应的反馈信息。发送方根据反
14、馈信息来决定是继续发送新帧(肯定应答),还是重发出错的旧帧(否定应答)。,3.4 基本数据链路协议,一种无限制的单工协议(An Unrestricted Simplex Protocol) 停-等协议(Stop-and-Wait Protocol) 有噪音信道的停-等协议(Stop-and-Wait Protocol for a Noisy Channel),协议1:一种无限制的单工协议(乌托邦),完全理想的条件:数据单向传输,收发双方的网络层一直处于就绪状态,处理时间可忽略不计,接收缓冲空间无限大,信道不会损坏或丢失帧。 发送端无限循环地重复三个动作: 从网络层取分组。 构造帧。 发出帧。
15、无需任何差错控制和流量控制。 接收端也是无限循环地重复三个动作: 等待事件(唯一的未损坏帧的到达)发生。 帧到达后,从硬件缓冲中取出新到的帧。 将帧的数据部分传给网络层。 无需做其它任何处理。,协议2:停-等协议,条件基本同协议1,只是接收缓冲只能存放一个帧且接收端需要一定的接收处理时间。 为了防止发送快于接收而造成数据丢失,发送端在发送一帧后必须停止发送,等待接收端发回的反馈确认短帧;接收端在收到一个帧并传送网络层后,需向发送端发一反馈确认短帧(不需包含任何信息,因为信道是无差错的),表示可发新帧。 由于需要反馈,且帧的发送和反馈是严格交替进行的,所以一般采用半双工信道。,有噪音信道的停-等
16、协议所涉及的问题,进一步考虑实际的会出错的信道,帧既可能损坏(接收端可通过校验检查出错误),也可能完全丢失。 发送端仍通过接收端的反馈来决定怎么做。但由于帧会丢失,发送端可能收不到反馈的确认帧,因此发送端必须引入超时机制(time out),即增加一个定时计数器,在一定时间后对没有确认的帧进行重发,也称作ARQ(Automatic Retransmit reQuest)。 时间值应选择稍大于两倍端到端的信号传输时间和接收端的接收处理时间之和。,有噪音信道的停-等协议所涉及的问题,当接收端的反馈确认帧丢失时,必须通过为帧编制序号来解决重复帧的问题。 帧的序号位数应尽量的短从而少占用帧头的空间,这
17、里只需1个比特位(“0”“1”,“1”“0”)即可。这是由于在本协议中,发送端每发送一个帧都是建立在此帧之前的所有帧都已正确发送的基础上,只需区分相邻的两个连续帧即可避免重复的可能。,协议3:有噪音信道的停-等协议,收发双方都需维护各自的帧序号(sequence number,初始都为0)。发送端维护的帧序号N(S)表示当前所发帧的序号,接收端维护的帧序号N(R)表示接收端当前所期待接收的帧序号。发送端从网络层取得第一个分组进行组帧,将N(S)=0的序号放入帧头中作为第一个帧,通过物理层的发送缓存器发送出去,并启动定时计数器,然后停下来等待其响应帧。 接收端收到一个帧后,对其序号和N(R)进行
18、比较: 若不等,则将其作为重复帧而丢弃; 若相等则对其接收,经校验正确并送交网络层后,将N(R)加1(模2运算)并放入确认帧中反馈回发送端;若校验出错,则丢弃出错的帧,保持N(R)的值不变并放入确认帧中反馈回发送端。,协议3:有噪音信道的停-等协议,发送端若在规定的时间内没有收到接收端的反馈确认帧(超时),就认为数据帧丢失,在保持N(S)不变的情况下重新发送缓冲器中的(旧)帧;若接收到确认帧后,比较确认帧中的序号和N(S): 若相等,则保持N(S)不变,重新发送缓冲器中的(旧)帧; 若不等,则将确认帧中的序号赋予N(S),从网络层获取新的分组并组成新帧(N(S)作为序号放入帧头中)交由物理层发
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机网络 第三章数据链路层 第三 数据链
链接地址:https://www.31doc.com/p-4157196.html