第6章数据链路层

1、1第第6章章 数据链路层数据链路层 n6.1 数据链路层的基本概念数据链路层的基本概念 n6.2 差错控制差错控制 n6.3 流量控制流量控制 n6.4 数据链路规程示例数据链路规程示例 2第一节 数据链路层的基本概念n6.1.1 差错产生与差错控制差错产生与差错控制n6.1.2 数据链路控制数据链路控制n6.1.3 数据链路层向网络层提供的服务数据链路层向网络层提供的服务36.1.1 差错产生与差错控制差错产生与差错控制 n传输线路是由传输介质与设备组成的。原始的物理传输线路是指没有采用高层差错控制的基本的物理传输介质与设备。n当数据从信源出发，经过通信信道时，由于通信信道总是有一定的噪声存

2、在，在到达信宿时，接收信号是数据信号与噪声的叠加。在接收端，接收电路在取样时判断信号电平。如果噪声对信号叠加的结果在电平判决时出现错误，就会引起传输数据的错误。4通信信道的噪声分为两类：热噪声和冲击噪声 n热噪声热噪声是由传输介质导体的电子热运动产生的。热噪声的特点是：时刻存在，幅度较小，强度与频率无关，但频谱很宽，是一类随机的噪声。由热噪声引起的差错是一类随机差错。 n冲击噪声冲击噪声是由外界电磁干扰引起的。与热噪声相比，冲击噪声幅度较大，是引起传输差错的主要原因。冲击噪声持续时间与数据传输中每比特的发送时间(T)相比，可能较长，因而冲击噪声引起的相邻多个数据位出错呈突发性。冲击噪声引起的传

3、输差错为突发差错。引起突发差错的位长称为突发长度。在通信过程中产生的传输差错，是由随机差错与突发差错共同构成的。5误码率n描述物理传输线路上传输数据信号出现差错多少的参数为误码率误码率。n误码率是指二进制比特在数据传输过程中被传错的概率，它在数值上近似等于被传错的比特数和传输的二进制比特总数的比值。在实际的物理线路的传输过程中，人们需要进行大量测试，求出各种信道的平均误码率，或者给出某些特殊情况下的平均误码率。n因为计算机网络的平均误码率要求低于10-6，所以普通电话线路如不采取差错控制技术，是不能满足计算机网络的通信要求的。 66.1.2 数据链路控制数据链路控制 n数据链路控制的主要功能有

4、以下几点： n(1)链路管理n(2)帧同步 n(3)流量控制n(4)差错控制n(5)透明传输n(6)寻址76.1.3 数据链路层向网络层提供的服务数据链路层向网络层提供的服务n面向连接确认服务(acknowledged connection-oriented service)；n无连接确认服务(acknowledged connectionless service)；n无连接不确认服务(unacknowledged connectionless service)。8第二节：差错控制第二节：差错控制 n6.2.1 差错控制方法差错控制方法 n6.2.2 奇偶校验法奇偶校验法 n6.2.3 循环冗

5、余校验循环冗余校验(Cyclic Redundancy Cheek，CRC) n6.2.4 海明码海明码96.2.1 差错控制方法差错控制方法 差错控制概念：n所谓差错控制是指在进行数据通信时，如何发现所传送的信息是否有错，以及发现错误时如何处理。10q自动请求重发(ARQ)：n发送端发送能检测差错的抗干扰码，如奇偶校验码、循环冗余校验码(CRC)等。接收端检验传输中有无差错产生，并把检验结果通过反馈信道送回到发送端，发送端根据反馈消息把接收端认为有错的消息再次发送，直到接收端判定无错为止。n特点：q检错码所需加入的冗余码元较少；q只能检测出错码是在哪些接收码之中，但不能确定错码的准确位置；q

6、这种方式只能用在双向通信系统中；q为了重发，必须有存储器；q在信道条件恶劣时需多次重发，接收端收到正确信息要经过较长的延时时间，因此这种方式在数据的实时性要求很高的场合就不能用。11q向前纠错(FEC)n在发送端发送能够纠错纠错的抗干扰编码，如海明码。接收端收到这些码后，通过纠错译码器，不仅能发现错误，而且能自动地纠正传输中的错误。n特点：q接收端能够准确地确定错码的位置，q不存在重发延时，所以实时性强。q适用于单工信道且不可能要求重发的场合。q缺点是附加信息量大、传输效率低、解码设备较复杂。12奇偶校验法q校验方法：n在奇偶校验时，要在每一个字符上增加一个附加位，使该字符中“1”的个数为奇数

7、或偶数。如在奇校验时，如果该字符位串中“1”的个数为奇数，则增加的附加位置“0”，否则置“1”，使该字符位串中“1”的个数为奇数。偶校验的附加位要保证字符位串中的“1”为偶数个。q奇偶校验并不是一种十分安全可靠的检错方法，如果有偶数个数据位在传输中同时出错，接收端将无法检测出差错，所以其检错概率为50。q通常偶校验常用于异步传输或低速传输，而奇校验常用于同步传输。13循环冗余校验q校验方法：n将所传输的数据除以一个预先设定的除数，所得的余数作为冗余比特，附加在要发送数据的末尾，被称为循环冗余校验码(CRC码)，这样，实际传输的数据就能够被预先设定的除数整除。当整个数据传送到接收方后，接收方就利

8、用同一个除数去除接收到的数据，如果余数为0，即表明数据传输正确，否则即意味着数据传输出现了差错。14循环冗余校验q计算方法：n在数据的末尾加上n个0，n等于除数的位数减1。n采用二进制除法规则，计算加长的数据除以预先设定的除数，得到的余数即为循环冗余校验码。n将循环冗余校验码替换数据末尾的n个0，即得出整个传输的数据。15 例如，如果除数为10011，写出数据1011010的循环冗余码 例如，如果除数为10011，写出数据1011010的循环冗余码 因为除数为10011，所以 N=4, 1011010 000016循环冗余校验CRC校验码为相除的余数，校验码为相除的余数，即即 1111 实际发

9、送的比特串则为：实际发送的比特串则为：10110101111 17循环冗余校验q实际上，循环冗余校验的数学基础是多项式除法。从数学角度看，任何数都可以表示成多项式的形式，因此二进制序列也可以表示成多项式形式。例如，1011010 就可表示成： 126 + 025 + 124 + 123 + 022 + 121 + 020 即 26+24+23+2 q基于上述理论，所传输的数据即可表示成一个信息多项式m(x)，而除数多项式即被称为生成多项式g(x)。循环冗余校验码就是扩充n个0后的m(x)除以g(x)的余数。18循环冗余校验CRC标准：nCRC-12 = x12+x11+x3+x2+1 nCRC

10、-16 = x16+x15+x2+1 nCRC-ITU-T = x16+x12+x5+1 nCRC-32 = x32+x25+x23+x22+x16+x12+X11+x10+x8+x7+x5+x4+x2+x+1 19n理论上，自动纠正每一个二进制代码的传输差错是可以做到的。但纠错码比检错码复杂得多，而且需要更多的冗余位。用于多位或突发差错纠错的位数太大的，以致大部分情况下，将使编码效率低到不可接受的程度。为此，大部分纠错码只限于处理1位、2位或3位差错。n在数据通信中，最常用的纠错码是所谓“海明码” (Hamming Code)，是贝尔实验室的科学家R.W.Hamming 于1950年提出的，

11、主要用来纠正1位差错。4.海明码201 1位差错的纠错位差错的纠错Single-bit Error Correctionn奇偶校验可以检测出1位差错的情况，方法是加上一个冗余的奇校验位或偶校验位。纠错则需确定其中哪位有差错。n如果要确定一个ASCII字符（7位）中的某位差错，此时需要区别8种情况：没差错，第1位错，第2位错，第7位错。于是，需要3个冗余位来表示8种不同的状态（000 -111）。n实际上，3位冗余是不够的。因为，冗余位本身也可能出现差错！21纠错码纠错码Error Correction22冗余位冗余位n如何计算m位数据纠错时所需的冗余位数 r 呢? n此时数据传输的总位数是m+

12、r，且要求 r必须能够至少表示 m+r+1 种状态。其中，一种状态表示无差错，m+r 种状态分别表示在 m+r 位每个位置上发生的差错。n由于r 位二进制数可以表示2r种不同的状态,所以，2r必须大于或等于 m+r+1。 2 r m+r+1 如果m=7（ASCII代码），则能满足上式的最小 r 值是4。因为： 24 7+4+123数据位数数据位数 m 与冗余位数与冗余位数 r 的关系 1234567 2333444 356791011 下表为一些可能的 m 值及其对应的 r 值。24纠错原理纠错原理n冗余位的定位冗余位的定位 海明码可用于任何长度的数据块，并利用了上面讨论的数据位数和冗余位数的

13、关系。例如，一个7位ASCII码要求4个冗余位，它们可以附加在数据位的后面，亦可散布在数据位之中。下图中，各冗余位处于第1、2、4、8位（2的n次方处），分别用r1，r2，r4，r8表示。25确定冗余位的位置确定冗余位的位置n在海明码中，每一个r位都是一组数据位的奇偶校验码。用于计算7数据位4个r值（奇偶校验码）的方案是： r1 : 第第 1，3，5，7，9，11 位位 r2 : 第第 2，3，6，7，10，11 位位 r3 : 第第 4，5，6，7 位位 r4 : 第第 8，9，10，11 位位26r1和和r2值的计算值的计算27r4和和r8值的计算值的计算28 纠错码的计算纠错码的计算为了

14、搞清楚这种技术后面的窍门，不妨看看每一数位的位置号（用二进制表示）。r1位使用的是所有位置号右侧为1开头的数位。r2使用的是所有位置号第2位为1的数位，以此类推。29示例：各示例：各r位值的计算位值的计算假设使用偶校验。30检错与纠错检错与纠错 如果数据发送后，接收端收到的数据发送后，接收端收到的海明码为: : 10010100101， 请问接收是否正确？如不正确，如何纠错？请问接收是否正确？如不正确，如何纠错？31假设上述数据发送后，接收端收到的:10010100101（第7位差错）。 此时接收端取出接收结果，并使用与发送端相同的方法计算出一组新的奇偶校验码。然后将这些奇偶校验码按r的顺序（

15、r8,r4,r2,r1）组成一个二进制数。本例中，组成的二进制数是0111（十进制数7），这就是准确的差错位置。一旦找出差错位，接收端即可将该位的值反转，以纠正差错。检错与纠错132海明码q基本思想： 在数据中加入足够多的冗余位(满足2r=m+r+1)，将这些冗余位分别放置在2的幂的位置上，每个冗余位都是一组比特的奇偶校验位。33海明码例如所传输的数据为 1011010，构成海明码的过程如下:(1)对于7位的数据，24 7+4+1，即取r=4个冗余位。海明码共11位。 (2)将这4个比特，分别放置在第1，2，4，8位上，记为 r1，r2，r4，r8。 (3) r1为位置的二进制表示的最低位是1

16、的各位的校验，r2为位置的二进制表示的次低位是1的各位的校验，r4 、r8依此类推。即：r1为第1，3，5，7，9，11位的偶校验。r2为第2，3，6，7，10，11位的偶校验。r4为第4，5，6，7位的偶校验。r8为第8，9，10，11位的偶校验。即：34海明码q数据： 1 0 1 1 0 1 0 d7 d6 d5 d4 d3 d2 d1 q位置: 11 10 9 8 7 6 5 4 3 2 1 q海明码：1 0 1 0 1 0 1 0 0 0 0 d7 d6 d5 r8 d4 d3 d2 r4 d1 r2 r1 35第三节第三节 流量控制流量控制n6.6.1 非受限协议非受限协议n6.6.

17、2 停停等协议等协议n6.6.3 滑动窗口协议滑动窗口协议366.6.1 非受限协议非受限协议n非受限协议是最简单的流量控制协议，其基本思路基本思路是：发送方只要有信息要发送，就可以不受限制地发送数据帧；并假定接收方有足够大的缓存区，可以缓存发送方发送的数据帧，或假定接收方的处理速度足够快，快到可以完全来得及处理发送方发送的数据。n非受限协议不检测帧是否损坏、丢失，不控制发送数量；即没有任何限制。这种协议适用于高质量的网络传输信道，几乎没有错误发生的情况；或者传输信息不重要，即使发生个别信息的丢失也没有太大影响阶情况。就如同我们生活中邮寄平信，一般都是不重要的内容，并且信任邮局能够安全将信送达

18、。376.6.2停停等协议等协议n停等协议的基本思想基本思想是：发送方每发送完一个数据帧，都要等待接收方的确认帧到来后，再发送下一帧：接收方每接收到一个数据帧后，都要向发送方发送一个正确接收到数据帧的确认帧。n停等协议的控制过程简单，每次发送一个数据帧，要求节点的缓冲区小；但停等协议也存在以下问题：存在以下问题： (1)如果发送方发送的数据帧丢失，接收方接收不到数据帧，也就不会返回确认帧，则造成发送方永久等待。 (2)如果接收方的确认帧丢失，同样会造成发送方的永久等待。 (3)如果确认帧在传输过程出现错误，会引起发送方的错误判断，造成协议失效。386.6.3 滑动窗口协议滑动窗口协议n滑动窗口

19、协议可以做到双向通信，此外，还可以通过“捎带确认”不用单独发送确认帧。n所谓“捎带确认捎带确认”是将确认信息附加在要发送的数据帧中一起发送。“捎带确认”也称为“捎带技术”。391滑动窗口协议的规定 n(1)每一个发送的帧都包含一个序列号，范围从0到某个最大值；最大值一般取2n-1，则序列号可以用N位(二进制)表示；停等滑动窗口协议的最大值取N=1，则序列号为0和1，其他滑动窗口协议的最大值不受限制。n (2)滑动窗口协议中，有一个发送窗口，其中放置允许发送的帧；一个接收窗口，对应于允许接收的帧。发送窗口与接收窗口的最大值可以不同。发送窗口中的序列号表示的是已经发送等待确认的帧的序列号；接收窗口

20、中的序列号是准备接收的帧的序列号，凡是到来的数据帧的序列号落在接收窗口内的都予以接收，序列号不在接收窗口内的拒绝接收。n (3)发送窗口随着发送帧的被确认，从缓冲区删除而向前滑动：接收窗口随着接收帧上交给网络层而向前滑动。n (4)在发送方为发送的帧设置定时器，如果在规定的时间内没有收到确认帧，则认为超时。这时发送方就要重传已经超时的帧。402一位滑动窗口协议416.退后N帧协议42 4选择重传协议43第四节 数据链路规程示例n6.4.1 数据链路层协议的分类数据链路层协议的分类n6.4.2 面向字符型协议实例面向字符型协议实例BSCn6.4.3 面向比特型数据链路协议实例面向比特型数据链路协

21、议实例HDLCn6.4.4 Internet数据链路层协议数据链路层协议 446.4.1 数据链路层协议的分类数据链路层协议的分类数据链路层协议点-点线路广播线路面向字符型面向比特型逻辑链路子层逻辑链路子层IBM BSCISO BMIBM SDLCANSI ADLCISO HDLCIEEE 802.2IEEE 802.3IEEE 802.4IEEE 802.5类型子层456.4.2 面向字符型数据链路层协议实例：面向字符型数据链路层协议实例：BSCn什么是面向字符型协议什么是面向字符型协议? 以字符为控制传输信息的基本单元以字符为控制传输信息的基本单元n ASIIC码：码： 格式字符：格式字符

22、：SOH（start of heading） STX（start of text） ETB（end of transmission block） ETX（end of text） 控制字符：控制字符：ACK（acknowledge） NAK（negative acknowledge） ENQ（enquire） EOT（end of transmission） SYN（synchrous） DLE（data link escape）46面向字符型面向字符型BSC协议的数据报文格式协议的数据报文格式SYNSYNSOH报头STX正文ETB/ETXBCC报文开始同步字符用户定义报头结束分组结束报文结束

23、校验字段正文字段47建立、维护建立、维护与释放数据与释放数据链路流程图链路流程图发送ENQ接收ACKACK?发送数据接收应答ACK/NAK结束?重发发送EOT准备数据放送ENQ发送ACK接收数据,EOT发送ACK发送NAKENQ?EOT?BCC正确?结束结束YYYYNNNNNYACKNAK486.4.3 面向比特型数据链路协议实例面向比特型数据链路协议实例HDLC面向字符型数据链路层协议的缺点面向字符型数据链路层协议的缺点：n报文格式不一样；报文格式不一样；n传输透明性不好；传输透明性不好；n等待发送方式，传输效率低。等待发送方式，传输效率低。面向比特型协议的设计目标面向比特型协议的设计目标：

24、n以比特作为传输控制信息的基本单元；以比特作为传输控制信息的基本单元；n数据帧与控制数据帧与控制 帧格式相同；帧格式相同；n传输透明性好；传输透明性好；n连续发送，传输效率高。连续发送，传输效率高。492 数据链路的配置和数据传送方式数据链路的配置数据链路的配置n非平衡配置非平衡配置n平衡配置平衡配置非平衡配置中的主站与从站非平衡配置中的主站与从站n主站：控制数据链路的工作过程。主站发出命令主站：控制数据链路的工作过程。主站发出命令 n从站：接受命令，发出响应，配合主站工作从站：接受命令，发出响应，配合主站工作非平衡配置中的结构特点非平衡配置中的结构特点n点点- -点方式点方式n多点方式多点方

25、式50数据链路的非平衡配置方式数据链路的非平衡配置方式51非平衡配置方式非平衡配置方式正常响应模式（正常响应模式（normal response mode，NRM）n主站可以随时向从站传输数据帧；主站可以随时向从站传输数据帧；n从站只有在主站向它发送命令帧进行探询（从站只有在主站向它发送命令帧进行探询（poll），从站响应），从站响应后才可以向主站发送数据帧。后才可以向主站发送数据帧。 异步响应模式（异步响应模式（asynchronous response mode，ARM）n主站和从站可以随时相互传输数据帧；主站和从站可以随时相互传输数据帧；n从站可以不需要等待主站发出探询就可以发送数据；从

26、站可以不需要等待主站发出探询就可以发送数据；n主站负责数据链路的初始化、链路的建立、释放与差错恢复等主站负责数据链路的初始化、链路的建立、释放与差错恢复等功能。功能。52平衡配置方式平衡配置方式 n链路两端的两个站都是复合站（链路两端的两个站都是复合站（combined station）；）；n复合站同时具有主站与从站的功能；复合站同时具有主站与从站的功能；n每个复合站都可以发出命令与响应；每个复合站都可以发出命令与响应；n平衡配置结构中只有异步平衡模式（平衡配置结构中只有异步平衡模式（asynchronous balanced mode，ABM）；）；n异步平衡模式的每个复合站都可以平等地发

27、起数据传输，而不异步平衡模式的每个复合站都可以平等地发起数据传输，而不需要得到对方复合站的许可。需要得到对方复合站的许可。53数据链路的平衡配置方式数据链路的平衡配置方式543 HDLC的帧结构 nF（flag） ：固定格式固定格式 01111110 作用作用 帧同步帧同步 传输数据的透明性（传输数据的透明性（零零比特插入与删除）比特插入与删除） nA（address） ：地址地址nC（control） ：帧的类型、帧的编号、命令与控制信息帧的类型、帧的编号、命令与控制信息nI（information） ：网络层数据，网络层数据，Nmax = 256BnCRC（checksum） ：校验校验A

28、、C、I字段的数据字段的数据 G(X)= X16+X12+X5+1标志字段F(8位)地址字段A(8/16位)控制字段C(8/16位)信息字段I(长度可变)帧校验字段FCS(16/32位)标志字段F(8位)55零比特插入/删除工作过程56帧类型及控制字段的意义标志字段F（8 位 ）地址字段A（8 /16位 ）控制字段C（8 位 ）信息字段I(长度可变)帧校验字段F C S（1 6/32位 ）标志字段F(8位)0N(S)P/FN(R)1 0监控P/FN(R)1 1未分配P/F未分配信息帧( I ) ：信息帧( I ) ：监控帧( S ) ：监控帧( S ) ：无编号帧无编号帧(U)：(U)：b0b

29、4b7b1b2b3b5b657帧类型nI帧帧 ： N（S） 发送帧的顺序号发送帧的顺序号 N（R） 接收帧的顺序号接收帧的顺序号 P/F= Poll / Final， P=1 询问，询问，F=1 响应响应 P与与F成对出现成对出现nS帧帧 ：监控功能位监控功能位 S = 00，RR（receive ready） S = 01，RNR（receive not ready） S = 10，RJE（reject） S = 11，SREJ（select reject）nU帧帧 ：用于实现数据链路控制功能用于实现数据链路控制功能58U帧的格式与链路控制功能MP/FM1 1A01111110FCS0111

30、1110110000000111100000100011010001UACMADSARMSNRMSABMDISC命令响应置异步响应置正常响应置异步平衡响应拆链无编号确认命令拒绝建立主从的点-点结构建立主从的多点结构建立复合站的平衡结构结束已建立的数据链路从站响应主站的命令从站报告帧传输异常594 数据链路层的工作过程n简化的信息帧结构的表示方法简化的信息帧结构的表示方法n一个信息帧的表示一个信息帧的表示 IN(S)N(R)P/FData高层数据探询/终止位接收帧序号发送帧序号I帧标志I， N(S)=3， N(R)=4， P=160n无编号帧的表示方法无编号帧的表示方法 nSNRM帧与帧与UA帧

31、结构的表示方法帧结构的表示方法 U ， SNRM ， P=1U ， UA ， F=1置异步响应模式：置异步响应模式：无编号确认：无编号确认：01111110A11001001FCS0111111001111110A11001110FCS01111110置异步响应模式：置异步响应模式：无编号确认：无编号确认：61正常响应正常响应模式数据模式数据链路工作链路工作62讨论：数据链路层与物理层的关系634. Internet中主要的数据链路层协议nSLIP （Serial Line IP） 串行线路的串行线路的Internet数据链路层协议数据链路层协议nPPP （ Point-to-Point Pr

32、otocol） 点点-点协议点协议nSLIP与与PPP用于串行通信的拨号线路上，是目前家庭计算机用于串行通信的拨号线路上，是目前家庭计算机或公司用户通过或公司用户通过ISP接到接到Internet主要的协议。主要的协议。 64SLIP协议nSLIP出现于出现于20世纪世纪80年代初，最早是在年代初，最早是在BSD UNIX 4.2版操作版操作系统上实现的系统上实现的;nSLIP协议支持协议支持TCP/IP协议协议;n对数据报进行了简单的封装，然后来用对数据报进行了简单的封装，然后来用RS-232接口串行线路接口串行线路进行传输进行传输;nSLIP通常也用来将远程终端连接到通常也用来将远程终端连

33、接到UNIX主机，也可通过租用主机，也可通过租用或拨号串行线路进行主机到路由器，以及路由器到路由器的通或拨号串行线路进行主机到路由器，以及路由器到路由器的通信。信。65典型的SLIP接入方式nInternet的家庭或小型公司用户通过调制解调器、电话网络连接的家庭或小型公司用户通过调制解调器、电话网络连接到到ISP的调制解调器；的调制解调器；nISP的调制解调器再通过它的路由器接入的调制解调器再通过它的路由器接入Internet；nSLIP系统一般可以发送和接收系统一般可以发送和接收1006B的的IP数据报。数据报。66SLIP协议的帧结构nRFC 1055文件对文件对SLIP帧格式进行了讨论帧

34、格式进行了讨论;nSLIP帧头与帧尾的帧头与帧尾的“CO”，是协议使用的惟一的一个控制字，是协议使用的惟一的一个控制字符符;nCO的二进制编码比特序列是的二进制编码比特序列是1000011 0000000;nCO的使用将影响的使用将影响SLIP帧数据的透明性帧数据的透明性; IP数据包EndEndIP数据包C0C0C0在数据传送中以“DB”“DC”表示DB在数据传送中以“DB”“DD”表示67 SLIP协议的缺点n使用使用SLIP协议时，通信的双方都必须知道对方的协议时，通信的双方都必须知道对方的IP地址，因地址，因为为SLIP协议没有为它们提供相互交换地址信息的方法；协议没有为它们提供相互交换地址信息的方法；n没有设置协议类型字段，不具备同时处理多种网络层协议的能没有设置协议类型字段，不具备同时处理多种网络层协议的能力；力；n没有校验和字段，差错控制功能由高层的协议承担；没有校验和字段，差错控制功能由高层的协议承担；nSLIP协议并不是协议并不是Internet的协议标准，因此不同版本的之间就的协议标准，因此不同版本的之间就会存在着差别，使得互连变得困难。会存在着差别，使得互连变得困难。68CSLIP协议n