计算机网络教案第四章

1、第4章 数据链路层,主要内容,数据链路层功能 数据成帧 差错校验 流量控制 常用的数据链路层协议,41数据链路层功能,该层的基本目标 如何在有差错的线路上，两台相邻机器间实现无差错传输。 相邻是指两台机器通过一条通信信道连接起来，比如同轴电缆、电话线或者点到点的无线信道。 具体功能包括 向网络层提供一个定义良好的服务接口。 处理传输错误。 调节数据流，确保慢速的接收方不会被快速的发送方淹没。 为网络层提供三种基本服务 无确认的无连接服务 误码率很低的线路，错误恢复留给高层； 实时业务 大部分局域网 有确认的无连接服务 无线系统 有确认的面向连接的服务,42数据成帧,成帧有很多方法，考察4种方法

2、。 1.字符计数法 在帧头中用一个域来表示整个帧的字符个数。 缺点：若计数出错，对本帧和后面的帧有影响。,42数据成帧,2. 带字符填充的首尾界符法 起始字符 DLE STX，结束字符DLE ETX 字符填充 缺点：局限于8位字符和ASCII字符传送。,42数据成帧,3带位填充的首尾标志法 帧的起始和结束都用一个特殊的位串“01111110”，称为标记(flag) “0”比特插入删除技术,42数据成帧,4.物理层编码违例法 只适用于物理层编码有冗余的网络 注意：在很多数据链路协议中，使用字符计数法和一种其它方法的组合。,43错误检测和纠正,基本原理 在原始资料（数码位）基础上增加几位校验（冗余

3、）位。 两种基本策略 纠错码 发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的资料是否有错，并能纠正错误。 检错码 发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的资料是否有错，但不能判断哪里有错。 1基本概念 码字（codeword） 一个帧包括m个数据位，r个校验位，n=m+r，则此n比特单元称为n位码字。 码距 一个编码系统中任意两个合法编码（码字）之间不同的二进数字（bit）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。也称为海明距离（Hamming distance）。 一般检测原则 为了检查出d个错（单比特错

4、），需要使用海明距离为d+1的编码；码距越大，纠错能力越强，但数据冗余也越大 。,43错误检测和纠正,2奇偶校验 奇性 二进制代码字中的码元有奇数个1 。 偶性 二进制代码字中的码元有偶数个1 。 种类 垂直奇（偶）校验 水平奇（偶）校验水平 垂直奇（偶）校验（方阵码 3.循环冗余编码CRC 目前应用最广的检错码编码方法之一,43错误检测和纠正,CRC的基本原理 在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。 对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。 根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC

5、码的生成多项式。 生成多项式是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。 在发送方，利用生成多项式对信息多项式做模2除生成校验码。在接受方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。 CRC的具体生成过程 设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2R，这样C(x)的右边就会空出R位，这就是校验码的位置。 通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。,43错误检测和纠正,具体的CRC码的生成步骤 1、将x的最高幂次为R的生成多项式G(x)转换成对应的R+1位二进制数。 2、将信息码左移

6、R位，相当与对应的信息多项式f(x)*2R 。 3、用生成多项式（二进制数）对信息码做模2除，得到R位的余数。 4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。,43错误检测和纠正,【例】假设使用的生成多项式是G(x)=x3+x+1。4位的原始报文为1010，求编码后的报文。 解： 1、将生成多项式G(x)=x3+x+1转换成对应的二进制除数1011。 2、此题生成多项式有4位（R+1），要把原始报文C(x)左移3（R）位变成1010000。 3、用生成多项式对应的二进制数对左移4位后的原始报文进行模2除。 4、在接收端收到了CRC码后用生成多项式为G(x)去做模2除，若得到余数为0

7、，则码字无误。若如果有一位出错，则余数不为0 。,43错误检测和纠正,已成为国际标准的多项式 CRC-12=x12+x11+x3+x2+x+1 nCRC-16=x16+x15+x2+1 CRC-CCITT=x16+x12+x5+1 CRC-32 硬件实现CRC校验 网卡NIC（Network Interface Card）,44基本的数据链路层协议,1无约束单工协议（An Unrestricted Simplex Protocol） 工作在理想情况，几个前提： (1)、单工传输 (2)、发送方无休止工作（要发送的信息无限多） (3)、接收方无休止工作（缓冲区无限大） (4)、通信线路（信道）不

8、损坏或丢失信息帧 工作过程 (1)、发送程序:取资料，构成帧，发送帧； (2)、接收程序：等待，接收帧，送资料给高层,44基本的数据链路层协议,2单工停等协议（A Simplex Stop-and-Wait Protocol） 增加约束条件：接收方不能无休止接收。 解决办法：接收方每收到一个帧后，给发送方回送一个响应。 工作过程： (1)、发送程序：取资料，成帧，发送帧，等待响应帧； (2)、接收程序：等待，接收帧，送资料给高层，回送回应帧。,44基本的数据链路层协议,3有噪声信道的单工协议（A Simplex Protocol for a Noisy Channel） 增加约束条件：信道（线

9、路）有差错，信息帧可能损坏或丢失。 解决办法：出错重传。 带来的问题： 什么时候重传 定时 响应帧损坏怎么办（重复帧） 发送帧头中放入序号 为了使帧头精简，序号取多少位 1位 发方在发下一个帧之前等待一个肯定确认的协议叫做PAR（Positive Acknowledgement with Retransmission）或ARQ（Automatic Repeat reQuest）,44基本的数据链路层协议,滑动窗口协议（Sliding Window Protocol） 单工 全双工 工作原理 发送的信息帧都有一个序号，从0到某个最大值，0 2n - 1，一般用n个二进制位表示； 在任何时刻，发送

10、方总是维持着一组序列号，分别对应于允许它发送的帧，称这些帧落在发送窗口内。接收方也维持着一个接收窗口，对应于一组允许它接受的帧。 发送端始终保持一个已发送但尚未确认的帧的序号表，称为发送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界表示未得到确认的帧的最小编号。发送窗口大小=上界-下界，大小可变； 发送端每发送一个帧，序号取上界值，上界加1；每接收到一个正确响应帧，下界加1； 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。接收窗口的上界表示允许接收的序号最大的帧，下界表示希望接收的帧； 接收窗口容纳允许接收的信息帧，落在窗口外的帧均被丢弃。序号等于下界的帧被正确接收，并产生一个

11、响应帧，上界、下界都加1。接收窗口大小不变。,44基本的数据链路层协议,4一比特滑动窗口协议（A One Bit Sliding Window Protocol） 捎带/载答（piggybacking） 暂时延迟待发确认，以便附加在下一个待发数据帧的技术。 协议特点： 、窗口大小：N = 1，发送序号和接收序号的取值范围：0，1； 、可进行资料双向传输，信息帧中可含有确认信息（piggybacking技术）； 信息帧中包括两个序号域：发送序号和接收序号（已经正确收到的帧的序号） 工作过程：（略）,44基本的数据链路层协议,问题： 卫星信道传输速率50kbps，往返传输延迟500ms，若传100

12、0bit的帧，使用协议4，则传输一个帧所需时间？信道利用率为多少？ 计算： 传输一个帧所需时间 发送时间+信息信道延迟+确认信道延迟1000bit/50kbps+250ms+250ms=520ms 信道利用率=20/5204% 一般情况： 信道带宽b比特/秒，帧长度L比特，往返传输延迟R秒，则信道利用率为(L/b)/(L/b+R)=L/(L+Rb) 结论： 传输延迟大，信道带宽高，帧短时，信道利用率低。,解决办法： 连续发送多帧后再等待确认，称为流水线技术（pipelining）。 带来的问题： 信道误码率高时，对损坏帧和非损坏帧的重传非常多。 两种基本解决方法： （1）退后n帧协议（A Pr

13、otocol Using Go Back n） （2）选择重传协议（A Protocol Using Selective Repeat）,44基本的数据链路层协议,44基本的数据链路层协议,5.退后n帧协议 基本原理： 当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧； 当发送方发送了N个帧后，若发现该N帧的前一个帧在定时器超时后仍未返回其确认信息，则该帧被判为出错或丢失。 此时发送方就不得不重新发送出错帧及其后的N帧。 特点： 接收方从出错帧起丢弃所有后继帧； 接收窗口为1； 对于出错率较高的信道，浪费带宽。,44基本的数据链路层协议,6.选择重传协

14、议 基本原理： 当接收方发现某帧出错后，其后继续送来的正确的帧虽然不能立即递交给接收方的高层，但接收方仍可收下来，存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以原已存于缓冲区中的其余帧一并按正确的顺序递交高层。 特点： 接收窗口大于1，先暂存出错帧的后继帧； 只重传坏帧； 对最高序号的帧进行确认； 接收窗口较大时，需较大缓冲区,44基本的数据链路层协议,发送窗口大小 ： 若帧序号采用n位二进制编码，由最大序号为Smax=2n-1。 有序接收方式 发送窗口最大为Smax 无序接收方式 发送窗口最大至多是序号范围的一半,45常用的数据链路层协议,一数据链路层

15、协议分类 面向字符型 ISO的IS1745，基本型传输控制规程及其扩充部分（BM和XBM） IBM的二进制同步通信规程（BSC） DEC的数字数据通信报文协议（DDCMP） PPP 面向比特型 IBM的SNA使用的数据链路协议SDLC（Synchronous Data Link Control protocol）； ANSI修改SDLC，提出ADCCP（Advanced Data Communication Control Procedure）； ISO修改SDLC，提出HDLC（High-level Data Link Control）； CCITT修改HDLC，提出LAP（Link Acc

16、ess Procedure）作为X.25网络接口标准的一部分，后来改为LAPB。,45常用的数据链路层协议,二高级数据链路控制规程HDLC HDLC（High-level Data Link Control） 1数据链路的配置方式和操作方式 （1）非平衡配置方式 属于主站与从站的结构 ; 主站控制数据链路的工作过程 ; 主站发出命令；从站接收命令，发出响应 ; 两种类型：点对点方式和多点方式。 两种操作模式 正常响应模式 异步响应模式,45常用的数据链路层协议,（2）平衡配置方式 链路两端的两个站都是复合站。 操作模式为异步平衡模式。,45常用的数据链路层协议,2帧结构,F（flag） ：固定

17、格式 01111110 作用 帧同步 传输资料的透明性（零比特插入与删除） A（address） ：地址 C（control） ：帧的类型、帧的编号、命令与控制信息 I（information） ：网络层资料，Nmax = 256B CRC（checksum） ：校验A、C、I字段的资料 G(X)= X16+X12+X5+1 帧类型 信息帧（Information） 监控帧（Supervisory） 无序号帧（Unnumbered）,45常用的数据链路层协议,控制域,序号（Seq） 使用滑动窗口技术，3位元序号，发送窗口大小为7 捎带确认（Next） 捎带第一个未收到的帧序号，而不是最后一个已

18、收到的帧序号 探询/结束 P/F位（Poll/Final）,45常用的数据链路层协议,监控帧类型（Type） “0”表示确认帧 RR（RECEIVE READY）；希望收到一个确认帧。 “1”表示否定性确认帧 REJ（REJECT）；next字段元指出需要重传的帧。 “2”表示接收未准备好 RNR（RECEIVE NOT READY）；告诉发送过程停止发送。 “3”表示选择拒绝 SREJ（SELECTIVE REJECT）；要求指定的帧重传。 无序号帧 主要起控制作用，可以在需要时随时发出，而不影响带序号的信息帧的交换。,45常用的数据链路层协议,45常用的数据链路层协议,3工作过程 分为3个

19、阶段： 建立数据链路 帧传输 释放数据链路。 实例： 正常响应模式的数据链路工作过程。 （1）主站使用无序号帧SNRM命令向从站请求建立数据链路连接。 （2）数据传输过程中，主站首先发送一个信息帧，如seq=1，next0。若在发送第二个信息帧时，同时询问从站是否有帧要发送，则第二个信息帧中，seq2，next0，P1。如从站有两个帧要发送，则其发送的第一个信息帧中seq1，next3，第二个信息帧中seq2，那next3，若此时再无数据要发送，则F1。 （3）若双方没有数据发送，则释放数据链路。主站发送命令DISC。从站若同意发回确认帧UA。主站接收到无序号确认UA时，释放数据链路。,45常

20、用的数据链路层协议,三Internet数据链路层协议 1点到点通信的两种主要情形 路由器到路由器（router-router leased line connection） 通过modem拨号上网，连到路由器或接入服务器（Access Server）（dial-up host-router connection） 2PPP协议簇的三个主要组成部分： （1）一种成帧方法。 （2）链路控制协议LCP（Link Control Protocol （3）络控制协议NCP（Network Control Protocols）簇 3PPP的帧格式,45常用的数据链路层协议,标记域：01111110，即7E，字符