计算机网络

第3章 数据链路层 数据链路层的服务与功能 成帧方法 差错控制与流量控制 差错检测和纠正 基本数据链路层协议--滑动窗口机制 第3章 数据链路层 数据链路层的服务与功能 成帧方法 差错控制与流量控制 差错检测和纠正 基本数据链路层协议--滑动窗口机制 数据链路层协议实例

数据链路层的服务与功能（1） 使用物理层提供的服务在通信信道上发送和接收比特。完成功能包括： 向网络层提供一个定义良好的服务接口 处理传输错误 调节数据流，确保慢速的接收方不会被快速的发送方淹没

数据链路层的服务与功能（2） 路由器的数据链路层示意

数据链路层的服务与功能（3） 3种可能的服务 无确认无连接—当错误率很低,恢复留给高层,对实时通信很适合.绝大多数局域网采用，以太网 有确认无连接—每一帧都要独立确认，超时重发,使用于不可靠信道,如无线系统，WiFi 有确认有连接—建立连接（初始化变量和计数器）、传输一个或多个帧、释放连接。为网络层进程提供了可靠的位流.

成帧方法 字节计数法 字节填充的标志字节法 比特填充的标志比特法 物理层编码违例法

成帧方法-字节计数法

成帧方法--标志字节填充法（1） 以特殊字符表征帧的起始和结束，并以一个专门字段来标明帧内的字节数。 典型实例是DEC公司的数字数据通信报协议DDCMP（Digital Data Communications Message Protocol）。

成帧方法-标志字节填充法（2） 用特殊的字符作为帧头和帧尾，起始字符 DLE STX，结束字符DLE ETX，接收方一旦丢失了帧信息，只要查找DLE STX就可重新确定帧边界。字符填充局限于8位字符和ASCII字符传送。 透明传输策略：当数据中含有DLE时，在DLE前面加上DLE 帧尾 SYN SYN DLE STX A DLE DLE B DLE DLE C DLE ETX 帧首 同步字符 数据 传输帧 填充字符 字符填充

成帧方法 --PPP协议采用字节填充方案

成帧方法--标志位填充法 帧的起始和结束都用一个特殊的位串“01111110”，称为标记（flag）。在面向二进制位的同步串型通信中常使用带位填充的首尾标志格式，如HDLC 。 透明传输策略：“0”插入法 帧首 数据 帧尾 01111110 01111101101111100 填充位 “0”比特插入删除技术

成帧方法-物理层编码违例法 借用一些违法编码序列来定界帧的起始与终止，局域网IEEE 802标准中就采用了这种方法。违法编码法不需要任何填充技术，便能实现数据的透明性。 数据0：低－高电平对 数据1：高－低电平对 曼彻斯特编码

差错控制和流量控制（1） 基于反馈的流量控制 确保可靠传输 反馈确认 超时重传 流量控制 帧编号（区分原始帧和重传帧） 反馈确认 超时重传 帧编号（区分原始帧和重传帧） 流量控制 基于反馈的流量控制 基于速率的流量控制（限制发送方传输数据的速率）

流量控制 流量控制（Flow Control） 决定帧在什么时候可以或不可以被发送，什么时候这些帧可以被第二次发送。 确保帧能够精确和有序地到达目的地。 典型情况下，流量控制是发送方、接收方某些连续层次的多个实体交互作用的结果，例如OSI模型中数据链路层和网络层的交互关系。 流量控制也存在于较高层协议如TCP，实际上流量控制存在于不同的模型以及不同的层之间。

差错控制方法 利用检纠错码进行差错控制的常用方式 自动请求重发（ARQ）方式 前向纠错（FEC）方式 混合纠错（HEC）方式

自动请求重发（ARQ）方式 发送端发送出可以发现错误的码字 接收端译码,若检测到错误，则主动向发送端发出请求，要求重发以便纠错。 这种系统要求有反馈信道且发送端和接收端都有缓存器。

前向纠错（FEC）方式 发送端发出的码字是具有一定纠错能力的码字。 接收端译码后不仅可以发现错码，而且能够判断错码所在的位置并自动纠正。 这种方法不需反馈信道，实时性好，传输效率较高，但纠错编码方法和设备较复杂。

混合纠错（HEC）方式 结合使用ARQ方式和FEC方式。 在传输错码较少且接收端能纠正时，自动纠正错误； 在错码较多、超出纠正能力但尚能检测时，采用自动请求重发方式，请求发送端重传，直到正确接收为止。 该方式大大提高了通信的可靠性。

差错检测和纠正 前向纠错（FEC）利用纠错码 反馈重传 利用检错码 纠错码的冗余量>检错码的冗余量 反馈重传 利用检错码 纠错码的冗余量>检错码的冗余量 对信道质量较好的有线链路一般都用检错码 对信道质量较差的无线链路采用纠错码 纠错码出现在物理层、链路层和高层多个层次 检错码更是经常应用于链路层、网络层和传输层

检错纠错的基本原理 在被传送的信息中附加一些冗余信息，使信息传输码元和冗余传输码元两者之间建立某种校验监督关系，当传输过程产生错误时，在接收端可利用监督关系进行检测并予以纠正。这种检纠错的能力是用信息量的冗余度来换取的。 码距和检纠错能力的关系 编码效率

码距和检纠错能力的关系 码重：指码字中非零码元的数目，即“1”的个数。码字（C表示）由许多码元组成，码字中码元的个数称为码长（n表示）。 码距：也称海明距离（Hamming distance），是一个码组中任意两码字之间对应位上码元取值不同的数目。用d表示，即 意义—任意两个码字的海明距离为d,则需要d个一位错误才能将一个码字变成另一个码字。

编码方案的检错和纠错能力与海明距的关系 为了检测d个错误，需用距离为d+1的编码方案，因为d个1位错误不可能将一个有效码字变成另一个有效码字。接收到无效码字，就知道发生了传输错误。 为了纠正d个错误，需要一个距离为2d+1的编码方案，即使发生了d位错误，还是原来的码字离它最近。从而可以唯一的确定原来的码字。 若码组中用于纠t个错，同时检e个错，则距离d≥e+t+1，其中e>t

纠错码 4种不同的纠错编码 海明码 二进制卷积码 里德所罗门码 低密度奇偶效验码

纠错码---海明码 设计一种编码方案 每个码字有m个报文位和r个校验位，n=m+r,可以纠正所有的单个错。 共有2n种符号表示。 任意一个合法报文，发生单个错（n位中的任一位都有可能），可能造成n个与合法报文的距离是1的非法码字 因此编码方案中，n必须满足 （n+1）2m<=2n

海明的方法（1950）：纠正单个差错. 码字中（1,2,4,8…)为校验位;剩下的位是数据.每个校验位迫使某一组位的奇偶值为偶数或奇数. 当一个码字到来时,接收方将重新计算所收到的每个校验位,看是否有正确的奇偶性。 若有错，将有错的位置相加，就是错误位置.若检验出第1位和第4位校验位有误，则表示第5位出错

7位ASCII码编成11位 满足27+ n* 27<=2n

校验位生成方法 a1=a3+a5+a7+a9+a11 a2=a3+a6+a7+a10+a11 a4=a5+a6+a7 a8=a9+a10+a11 若检验出第1位和第4位校验位有误，则表示第5位出错 3=1+2 5=1+4 6=2+4 7=1+2+4 9=1+8 10=2+8 11=1+2+8 第1个校验位分别对3,5,7,9,11位做校验

纠错码---卷积码（convolution code） 卷积码（n,k,m)不属于块码，主要用来纠随机错误 码元与前后码元有一定的约束关系，编码复杂度可用编码约束长度m*n来表示。 n个码元不仅与当前段的k个信息有关，而且与前面的（m－1）段信息有关（m为编码的约束长度）。 已经成为GSM移动电话系统的一部分，在卫星通信和802.11中都得到应用。 例 NASA卷积码 第一个被用于1977年旅行者航天飞行任务中的编码 卷积码的纠错能力不仅与约束长度有关，还与采用的译码方式有关。 卷积码的性能至少不比分组码差

纠错码---里德所罗门码（Reed-Solomon code） 类比方案描述：两个数据点代表一条线，选自同一条线上的额外两个点充当校验位，当有一个点出现错误，仍然可以通过拟合线恢复这个点。 得到广泛应用，强大的纠错能力。用在DSL、线缆上的数据通信、卫星通信、CD、DVD。加入2t个冗余符号后，可以纠正传输符号中的任意t个错误。 通常和其他编码结合一起用，如卷积码。

纠错码---低密度奇偶校验码（LDPC） Robert Gallagher 1962年博士论文中提出 每个输出位由一小部分输入位形成，编码可以用一个1的密度很低的矩阵表示。接收码字通过一个近似算法解码获得，该算法通过迭代不断改进接收到的数据域合法码字的最佳匹配。 适用于大块数据，纠错能力强。被新的协议所采纳，成为数字视频广播、万兆以太网、电力线网以及新版802.11标准的一部分。

检错码 纠错码广泛应用于无线链路,而有线链路,通常使用检错码. 例如:错误率为10-6,1000 位数据块,需要10位纠错码,能纠正1位错,而用检错码只需1个奇偶位,1M数据位需要的纠错和检错的开销? 三种检错码—线性块码 奇偶 校验和 循环冗余校验（CRC）

检错码--奇偶校验 奇偶监督码是一种最基本的、最常用的、最简单的检错码。它可分为奇监督码和偶监督码两种，基本编码原理相同。奇偶监督码中，监督位仅有1位，设监督位为c0，奇偶监督码的编码规则是加入c0后，码字中“1”的个数满足奇数或偶数，用下式表示：

检错码--二维奇偶监督码 二维奇偶监督码又称方阵码，是在奇偶校验码的基础上产生的。它把奇偶监督码的若干码字排列呈矩阵，每个码字一行，增加一位监督位，再按列的方向增加垂直监督位，构成水平—垂直奇偶监督码。

检错码--校验和 Internet校验和 待校验的相邻字节成对组成16比特整数,并计算其和的二进制反码(二进制反码求和). 二进制反码求和:从低位到高位逐列进行和计算,如果最高位(16位)进位,则得到的结果加1,一直循环到最高位没有进位为止.最后把得到的结果取反. 检查校验和,将所有字节,包括校验和,进行相加并求二进制反码.如果结果为全1(即二进制反码算术中的0),检查通过. 简单的求和，无法检测出0数据的增加和删除，保护很弱

Fletcher校验和 Fletcher 1982年提出，将数据和位置的乘积添加到总和中，能对数据位置的变化提供更强大的检测作用。

检错码--循环冗余校验码（CRC） 循环码又称为多项式码，是一种线性分组码。它是在严格的代数学理论基础上建立起来的，检纠错能力非常强，且广泛应用在计算机网络和数据通信中。循环码除了具有线性分组码的一般性质外，还有一个显著的特点就是循环性，即循环码中任一码字循环左移（右移）一位或多位所形成的码字仍旧是循环码中的码字。

循环码的编码 第一步 若生成多项式G(x)的阶是r, 将信息位左移r位，得xrM(x)； 第三步，根据T(x)=xrM(x)+r(x)，求出码字。

CRC的检错能力分析 接收方:T(x)+E(x) 当E(x)/G(x)为0时,错误无法检出 (1)1位错能够检出.E(x)=xi (2)两个独立的一位错,E(x)=xi+xj=xj(x i-j+1) 除非i-j很大,要不然E(x)/G(x)!=0.如对于任何k<32,768,x15+x14+1不能被xk+1除尽 (3)奇数个错误,在模2的系统中,没有一个奇数项多项式包含x+1因子,因此只要使G(x)中含有x+1因子,就能检出所有奇数个错.

(4)突发性错误.长度为k的突发错误 xi(x k-1+…+1) . 若共有r个校验位,则所有k小于或等于r的突发错误都能被检出 长度为r+1,则当且仅当错误多项式等于G(x)时,概率为(1/2)r-1 长度大于r+1位的突发错误,通过检测的概率的是(1/2)r IEEE802使用多项式为x32+x26+x23+x22+x16+x11+x10+x8+x7+x5+x4+x2+x+1

基本数据链路层协议 物理层进程和某些数据链路层进程运行在网卡上 链路层进程的软件通常以设备驱动形式存在。

协议公用的一些声明（1） 一个帧的4部分，kind seq ack 做控制用 info是要传输的信息 定义放置在文件protocol.h.

协议公用的一些声明（2） 定义放置在文件protocol.h.

协议公用的一些声明（3） 定义放置在文件protocol.h.

一个无限制的单工协议（1） 发送进程

一个无限制的单工协议（2） 接收进程

一个无限制的单工协议（3） 发送进程 接收进程

无错信道上的单工停等协议（1） 可以实现流量控制，防止发送速度过快

无错信道上的单工停等协议（2）

无错信道上的单工停等协议（2） 发送进程 接收进程

有错信道上的单工停等协议（1） 发送方在前移到下一个数据之前必须等待一个肯定的确认 需解决的问题：如何区分新帧还是重传的老帧---帧序号

有错信道上的单工停等协议（2）

有错信道上的单工停等协议（3）

有错信道上的单工停等协议（4）

滑动窗口协议（1） 全双工 使用同一条链路来传输两个方向的数据。 用kind 来区分是数据帧还是确认帧 捎带确认(piggybacking) 延缓确认以便搭载在下一个数据包上----等多久？ 帧序号 0-2n-1 正好填入n位的域 停-等协议使用n=1,序号是0或1

滑动窗口协议（2） 滑动窗口的本质：任何时候发送方维持一组序号，对应于允许发送的帧或那些已经被发送还没被确认的帧 接收方维持着一个接收窗口，对应于可以接收的帧。 两窗口不一定一样大 发送窗：任何时候有新的数据包从网络层来，被赋予窗口中的下一个最高序号，并且窗口的上边界前移一格；当接收到确认时，窗口的下边界也前移一格。 发送方需缓存发送窗口中的帧，当达到最大窗口尺寸，强行关闭网络层。等待确认。 接收窗：任何落在接收窗口外的帧将被丢弃，当收到一个帧，其序号等于窗口下界时，整个窗口向前移动1个位置.

滑动窗口协议（3） 大小为1的滑动窗口 A sliding window of size 1, with a 3-bit sequence number. (a) Initially. (b) After the first frame has been sent.

A sliding window of size 1, with a 3-bit sequence number 滑动窗口协议（4） 大小为1的滑动窗口 A sliding window of size 1, with a 3-bit sequence number (c) After the first frame has been received. (d) After the first acknowledgement has been received.

滑动窗口协议-1位滑动窗口协议（1）

滑动窗口协议-1位滑动窗口协议（2）

Two scenarios for protocol 4. (a) Normal case. (b) Abnormal 滑动窗口协议-1位滑动窗口协议（4） A，B同时发，多次重发，造成带宽浪费 Two scenarios for protocol 4. (a) Normal case. (b) Abnormal case. The notation is (seq, ack, packet number). An asterisk indicates where a network layer accepts a packet

1位滑动窗口协议的效率 η=tf/(tf+2tp)=1/(1+2(tp/tf)) tf是发送一帧的时间 tp是从发送端到接收端链路的传播时间 举例 卫星链路 50kbps 往返传播延迟500毫秒 帧长1000位 tf=20ms 2tp=500ms η =4% A方 B方 DATA(0，0) 时间 DATA(0，1) DATA(1，1) DATA(1，0) 停等式ARQ

提高效率的方法 在发送方被阻塞前发送w帧 链路利用率η≤ w/(1+2α) α为链路传播延迟/帧的发送时间 如何处理管道化传送中的错误 回退n帧ARQ（GO-BACK-N） 选择重传ARQ（Selective Repeat）

回退N帧协议(1) 接收窗口为1

回退N帧协议（2） 发送窗口与接收窗口大小 sws>1, rws=1 设窗口序列号分别是0、1、2..MAX-SEQ(2n-1) sws应小于N =2n ,最大未确认帧数是2n-1 累计确认（cumulative acknowledgement） 若取sws=N,会导致某些情况下协议失败 如当发送0-7号帧,成功，返回ACK=0(应答帧全部丢失） 又发送0-7号帧，成功？全部丢失？无法区分

Protocol Using Go-Back-N (3) A sliding window protocol using go-back-n. . . .

Protocol Using Go-Back-N (4) . . .

Protocol Using Go-Back-N (5) . . .

Protocol Using Go-Back-N (6) . . .

Protocol Using Go-Back-N (7) A sliding window protocol using go-back-n. . . .

Protocol Using Go-Back-N (8) *累计确认的处理 A sliding window protocol using go-back-n. *重传 . . .

Protocol Using Go-Back-N (9) 用于流量控制，diable_network_layer()阻止网络层给予太多的工作

Protocol Using Go-Back-N (10) 多个计时器的软件实现 Simulation of multiple timers in software. (a) The queued timeouts (b) The situation after the first timeout has expired.

选择重传协议 Pipelining and error recovery. Effect of an error when (b) receiver’s window size is large.

选择重传协议—非顺序接收带来的问题 (a)Initial situation with a window of size7 (b)After 7 frames sent and received but not acknowledged. (c)Initial situation with a window size of 4. (d)After 4 frames sent and received but not acknowledged.

sws>1, rws>1 举例说明选择性重传在发送窗口和接收窗口都取7时，在某些情况失效 ①       设 2n = 8，设sws=7, rws = 7； ②       发方发帧 0 - 6，收方全部收到； ③       接收窗口前移（7 - 5）； ④       现在发生意外，确认帧全部丢失； ⑤       由于超时，发方重传帧0； ⑥       收方作为新帧接收，并对帧6确认（因为0-6都收 到） ⑦       发送方发出新帧 7-5， ⑧       收方已收过帧 0，丢弃新帧 0，协议出错。 选择性拒绝ARQ中，显然接收窗口不应该大于发送窗口，当接收窗口尺寸取最大时，rws=sws，明显地， rws=sws < 2n /2=2n-1，只有满足这个条件才能不发生混帧的问题。（前后两个接收窗口不能重叠）

Protocol Using Selective Repeat (1) A sliding window protocol using selective repeat. . . .

Protocol Using Selective Repeat (2) A sliding window protocol using selective repeat. . . . 发送过程，可以发送数据、携带ack、或nak

Protocol Using Selective Repeat (3) A sliding window protocol using selective repeat. . . .

Protocol Using Selective Repeat (4) . . .

Protocol Using Selective Repeat (5) . . .

Protocol Using Selective Repeat (6) . . .

Protocol Using Selective Repeat (7) 将接收到的数据帧递交给网络层，接收窗口滑动 . . .

Protocol Using Selective Repeat (8) 重传 . . . 检测到帧错误，发送nak

Protocol Using Selective Repeat (9)

数据链路协议实例 高级数据链路控制（HDLC- High-level Data Link Control）是由国际标准化组织ISO于1976年提出制定的面向位的有序链路级协议。 HDLC的帧格式，由标志、地址、控制、信息和帧检验序列（FCS）等段构成。

HDLC帧的类型 1、信息帧（Information）； 2、监控帧（Supervisory）； 3、无编号帧（U帧）

数据链路协议实例 Internet两种常见情况下 通过广域网中的SONET光纤链路发送数据包 Internet边缘的电话网络本地回路上的ADSL链路 数据链路协议都采用点到点协议（PPP）RFC1661，1662

Packet over SONET. (a) A protocol stack. (b) Frame relationships 数据链路协议实例（1) Packet over SONET. (a) A protocol stack. (b) Frame relationships

数据链路协议实例（2) PPP功能 三个主要部分 处理错误、检测链路配置、支持多种协议、允许身份认证 成帧方法 明确地定界一个帧的结束 和下一个帧的开始，也允许进行错误检测。 链路控制协议（LCP，Link Control Protocol） 负责启动线路、测试线路和选项协商，并在它们不再被需要时稳妥地释放。 网络控制协议（NCP，Network Control Protocol） 协商网络层选项，对于所支持的每一个网络层协议都有一个不同的用来建立和配置不同的网络层协议。PPP允许使用多个网络层协议链路控制协议

数据链路协议实例（3) PPP帧格式 标志：01111110。地址：11111111。控制段：缺省值是00000011。 协议段：说明在载荷段中的分组种类（可以是LCP,NCP,IP,IPX,AppleTalk等）。 载荷段长度是可变的,在没有经过LCP协商时，缺省是1500字节 校验和采用32位或16位CRC SONET采用32位CRC，同时建议不压缩Address，control和protocol字段

数据链路协议实例（4) SONET线路在发送PPP帧前，必须建立和配置PPP链路。 初始状态

数据链路协议实例（5) 对称数字用户线 提取IP包，并注入到ISP网络

数据链路协议实例（6) ATM (Asynchronous Transfer Mode) 20世纪90年代提出，承诺的网络技术将语音、数据、有限电视、电报等并成宽带综合业务系统，目前仍被应用在DSL宽带线路和电话网络内部的广域网链路。 ATM是一种链路层，信元（cell）,虚电路，交换设备以此标识符转发信元。 ATM适配层完成将数据映射成信元，分段，重组。AAL5是针对数据包数据的适配层. ATM上的PPP（PPPoA标准） 协议字段—告诉有效载荷是IP包、LCP包等。

作业 P195 1,3,6,16,18,20,22,27,28,34,39(课外编程)