第三讲数据链路层

1第三讲数据链路层2本讲要求1理解数据链路层解决的基本问题2掌握数据帧的基本原理和方法3掌握出错处理的几种方式4掌握数据链路层的基本协议5掌握数据链路层的滑动窗口协议6了解典型的数据链路协议3基本问题

如何利用物理层的0-1比特流传输能力在相邻机器间进行数据传输？问题分析◆信道问题广播信道点对点信道每对连接对应一对机器4问题分析（续1）◆地址问题—通信主机标识问题（*）◆面向连接还是非连接？□面向连接——是基于电话系统模型。也就是说，在数据传输前，有一个连接建立的过程，通信结束后，有一个连接断开的过程。（服务质量高）□面向非连接——是基于邮政系统模型。也就是说，任何时候数据都可以直接发送。（服务质量低）5问题分析（续2）◆数据封装问题—帧格式□开始、结束标志□通信地址：面向连接时，建立连接过程需要地址；面向非连接时，数据传输时需要地址。□数据及编码□递交对象——数据链路是数据传输服务层，到达目的机器后，数据必须递交给其他功能函数来处理。◆流量控制问题—发送者、接收者能力不对等问题◆出错处理—什么是错？纠错？检错？不管？结论：数据传输需要协调双方的行为——协议6数据链路层的地址问题◆随机分配—管理员分配配置◆固化设置—将地址固化到物理器械中如令牌环网等如以太网卡

一般来说，通信主体都应该拥有一个标识

——称为地址。小探索：查看以太网卡的物理地址，并修改它。7数据封装问题—帧格式（1）◆问题分析：什么是一个好的帧格式？（1）容易生成（2）重新实现帧同步的难度（3）普遍的适应性■将要传输的数据分成很多小段数据发送出去。8数据封装问题—帧格式（2）◆字符计数法□原理：在头部中的一个域指定该帧中的字符数。5个字符5个字符8个字符8个字符512345678901234568790123第一帧8第二帧第三帧第四帧8字符计数□问题：出错后的帧无法同步512347678901234568790123第一帧8第二帧8字符计数？9数据封装问题—帧格式（3）◆字节填充法□分析：字符计数法失去帧同步后，恢复很难。原因是很难区分计数的字符和数据字符。□原理：使用特殊的字符作为帧的开始和结束标志payloadFLAGFLAGheadertrailer□新的问题：如果负载重出现了FLAG了怎么办？AFLAGBFLAGFLAG10数据封装问题—帧格式（4）◆字节填充法□转义字节技术stuffing“ESC”ESCSamewithflagFLAGAFLAGBFLAGFLAGAFLAGBFLAG□新问题：数据中包含了ESC怎么办？11数据封装问题—帧格式（5）◆字节填充法□转义字节技术data“ESC”stuffing“ESC”ESCFLAGAESCBFLAGFLAGAESCBFLAG□其他问题？遇到第一个ESC，表示后面的是正常数据，不是特殊字符12数据封装问题—帧格式（6）◆字节填充法□字节填充法存在什么问题？

必须紧紧依赖于8位字符模式

不是所有的字符都是8位字符模式，如Unicode使用16位字符。结论：非8位字符模式，需要转换为8位字符模式才能顺利传输□字符填充法分析13数据封装问题—帧格式（7）◆位填充法□

原理：帧开始和结束都有一个特殊的位模式01111110□问题：当传输数据中有01111110如何处理？□

解决办法：碰到连续5连续的位“1”的时候，自动填充一位00111111001011111111011101111110123456123456781234560111111001011111011101110111111012345678□位填充法分析14数据封装问题—帧格式（8）◆物理层编码违例法□原理：使用非数据编码信号来表示帧的边界。如以太网（MAC子层中介绍）——曼彻斯特编码方式传输数据“1”的编码“0”的编码

其他编码方式，可以用作帧的边界□物理层编码违例法分析15流控制问题

◆问题描述发送方的速度超过了接受方能够接受这些帧的速度◆基本处理方法□基于反馈的流控制□基于速率的流控制定义规则，规范发送者什么时候可以发送帧。（具体协议中介绍）限制发送方的速率。（后面章节中详细介绍）16出错处理（1）

◆定义—什么是错误？□严格意义：凡是接收到的数据和发送的数据不一致□不一致：错误数据*、丢失数据、数据乱序◆基本措施□纠错（错误纠正）：就是将不一致的数据恢复到一致□检错（错误发现）：检查数据中是否存在不一致□不作为先看看错误数据的基本措施，丢失和乱序问题在协议中介绍17出错处理（2）

◆纠错—纠错码□原理：在发送的数据中包含冗余信息，以便接收者可以推断出数据中肯定有哪些内容。包含m个数据位和r个校验位的n-位单元，通常称为n位码字（n=m+r）。mbitsDatabitsrbitsCheckbitsnbitscodeword（n=m+r）—有这么神奇的事情吗？18出错处理（3）

◆纠错码□海明距离——两个码字不相同的位的个数10001001（码字1）10110001（码字2）XOR00111000海明距离d=3

含义理解：如果码字1出错后，变为码字2，则至少要3位数据发生错误

海明距离用来度量最少出错的位数19□海明距离用来度量最少出错的位数出错处理（4）

◆纠错码□纠正d位错误的基本原理即假设传输过程中，最多d位出错。（1）对于传输数据m位，合法的报文有2m种情况；（2）对于传输的n位码字，可能的码字有2n种情况（n=m+r）；（3）从2n中选择2m个n位码字来表示合法的传输数据，并且保证每两个n位码间的距离至少为2d+1;（4）接收到数据A时，与所有的n位合法码字求解海明距离，海明距离小于d的，就是传输的数据。20出错处理（5）

◆纠错码0000000000（码字1）0000011111（码字2）1111100000（码字3）1111111111（码字4）□例子编码距离为5，因此2d+1=5，可得d=2，该方案可以纠错2位以下的错误。接收到数据0000000111，与上面的码字计算海明距离，和码字2距离最小，为2，因此该数据有两位出错了，原始数据应该是000001111121出错处理（6）

◆检错—检错码□原理：在发送的数据中包含冗余信息，以便接收者可以推断出数据中是否发生了错误。□奇偶检错方案——检测单个错误□检错原理：在数据后面加上一个奇偶位，如果码字中的“1”的位为偶数，则填0，如果是奇数，则填1。22出错处理（7）

senderreceivererror□奇偶校验例子□针对突发性长错误，可采用交错奇偶校验位来处理。23出错处理（8）

□

循环冗余校验（CyclicRedundancyCheck,CRC）也称多项式编码（PolynomialCode）

基本思想○前提条件（1）将位串看成是系数为0或1的多项式。如10001011*x6+0*x5+0*x4+0*x3+1*x2+1*x1（2）发送方和接收在数据传输前商定一个生成多项式G(x).如G(x)=x4+x+1------10011（3）传输帧有m位，对应的多项式为M(x)。□

校验和（Checksum）TCP/IP协议中使用的一种校验方法。24出错处理（9）

○CRC校验和计算算法（1）假设G(x)的阶为r。在帧的低位端加上r个0，此时帧长为m+r，对应多项式为xrM(x)；（2）利用模2除法，用对应的G(x)的位串去除xrM(x)对应的位串，余数记为P(x)；（3）利用模2减法，xrM(x)-除法运算中的余数P(x)，结果记为T(x)就是带校验和的帧。25出错处理（10）

○CRC校验和计算例子问题：发送数据帧1101011011m=10，M(x)为(m–1=9)阶多项式M(x)＝x9+x8+x6+x4+x3+x+1第一步：选择生成多项式G(x)=x4+x+1r=4，10011

第二步：形成多项式xrM(x)n=m+r=10+4=14，xrM(x)为13阶多项式x4M(x)＝x13+x12+x10+x8+x7+x5+x411010110110000

26出错处理（11）

○CRC校验和计算例子第三步：用以2为模的除法求余数 余数[11010110110000/10011]=1110第四步：用以2为模的减法计算校验和 发送帧T(x)＝1101011011111027出错处理（12）

○

CRC检错能力说明（1）如果传输过程出错了，即有一些位的0或1发生了变化。把发生变化的位记录为1，其他位置为0，它对应一个多项式E(x)。（2）接收者的信息则为T(x)+E(x)；（3）校验时候计算为[T(x)+E(x)]/G(x)=E(x)/G(x)○CRC校验和验证

接收者接收到T(X)后，用T(x)/G(x)，余数应该为0，否则就判定为有错误。T(X)=xrM(x)-P(x)如果E(x)不被G(x)除尽，则可以检测到传输过程中出错了，如果刚好被除尽了，则该错误没有被检测到。所以G(x)很重要。28基本数据链路协议（1）◆应用情况点到点信道，也就是只有一个发送者和接收者。◆几个重要功能函数□from_network_layer□to_network_layer□from_physical_layer□to_physical_layer29基本数据链路协议（2）◆无限制的单工协议□前提条件：

单方向数据传输（即只有一个发送者和接收者）

理想信道（信道不出错，传输速度极快）

通信双方能力无穷（发送者不停发送，接收者不停接收）□发送者基本过程第一步：从网络层获得数据第二步：发送到物理层。□接收者基本过程第一步：等待数据到达第二步：从物理层提取数据第三步：把数据递交给网络层30基本数据链路协议（3）SENDER:from_network_layerframingto_physical_layerto_network_layerRECEIVER:wait_for_eventfrom_physical_layer31基本数据链路协议（4）◆什么是协议？通信双方关于如何进行通信的一种约定◆什么是服务？实体为它的用户提供的功能。如无限制单工协议规范双方的行为来完成数据的传输如数据链路层为网络层提供传输数据的功能如物理层为数据链路层提供0-1比特流传输功能◆什么是接口？定义调用服务的原语操作如from_physical_layer和to_physical_layer等□服务是用户的功能需求（该层要解决的问题）□协议是完成服务功能的实现过程（解决问题的程序）□接口是程序的交互界面（用户操作界面）32基本数据链路协议（5）◆无限制的单工协议分析现实问题：接收方的接收能力是有限制的。◆无限制的单工协议改进□

问题分析：假设接收者处理一帧的时间是t，则希望发送者在t时间后，再发送下一帧。t如何确定？如何知道接收者的t？（很难估计）□解决办法：因为信道是理想信道，速度很快的，让接收者在处理完毕一帧后，反馈一个信息告诉发送继续发送数据（基于反馈的流控制机制）—单工停-等协议

关键问题：如何避免大量数据淹没接收方？——流控制33基本数据链路协议（6）◆单工的停-等协议□前提条件：

单方向数据传输（即只有一个发送者和接收者）

理想信道（信道不出错，传输速度极快）

接收者能力有限34A

Bf1ack□发送者基本过程第一步：从网络层获得数据第二步：发送到物理层第三步：等待对方的反馈第一步：等待数据到达第二步：从物理层提取数据第三步：把数据递交给网络层第四步：发送反馈帧□接收者基本过程基本数据链路协议（7）等待时间35基本数据链路协议（8）SENDER:from_network_layerframingto_physical_layerRECEIVER:wait_for_eventto_network_layerwait_for_eventfrom_physical_layerto_physical_layerWaitforacksendack36基本数据链路协议（9）◆单工的停-等协议分析□问题1：理想信道是不存在的，信道有噪声，即传输过程中，帧可能会出错。

错误类型：（1）数据位出错；（2）数据丢失

处理错误方式分析：（1）数据位出错：纠错，检错+重传（如何选择？）（2）数据丢失：将丢失的数据重传（解决问题效果如何？）37基本数据链路协议（10）◆单工的停-等协议分析□问题2：发送方如何知道数据丢失？——没有接收到对方的反馈帧，则认为数据丢失！□后续问题：如果数据并没有丢失，而是反馈帧丢失了呢？接收到两个A帧，都递交给了上层协议数据重复，协议出错了。发送者接收者AA反馈帧丢失BAA解决办法：每一帧都带上一个编号，称为序列号定时器！38◆单工的停-等协议分析基本数据链路协议（11）□序列号几位合适？发送者接收者ABCBBCQ

发送B帧时，A帧以及之前的帧已经发送并正确接收。

如果要重传，则发送B帧，否则发送C帧。

对于接收到的Q帧，它可能是B帧或C帧。结论：对于停-等协议接收者而言，可能引起混淆的帧最多是2帧，因此需要1位的序列号。39基本数据链路协议（12）◆有噪声的单工协议□前提条件：

单方向数据传输（即只有一个发送者和接收者）

噪声信道（信道会出错：数据位错或丢失）

接收者能力有限□基本思想

在停-等协议的基础上，增加出错处理机制（超时重传输机制）40基本数据链路协议（13）◆有噪声的单工协议□发送者基本过程第一步：从网络层获得数据第二步：将帧编号，发送到物理层，启动超时定时器第三步：等待对方的反馈第四步：如果当前帧的确认帧到达，则跳到第一步第五步：如果超时定时器超时，则重传当前帧，并跳到第三步。第一步：等待数据到达第二步：从物理层提取数据，查看帧编号，确定是否是新的数据帧，如果不是，则跳到第一步，否则第三步，第三步：把数据递交给网络层第四步：发送反馈帧□接收者基本过程41next_frame_tosend=0from_network_layerframingto_physical_layerstart_timerstop_timer(next_frame_to_send

+1)mod2timeoutframe_arrivalwaitfrom_network_layer●SENDER42frame_expected=0waitfrom_physical_layerexpected?to_network_layer(frame_expected+1)mod2sendackYNframe_arrivalCksum_err●RECEIVER43基本数据链路协议（14）◆基本数据链路协议分析□

问题：单工或半双工（即任何时候，线路上只有一个传输者和一个接收者），造成带宽浪费。□需求：单工协议的双工改造，即支持双向数据传输□方法1：双独立信道+2单工协议信道1（A数据信道/B确认信道）信道2（B数据信道/A确认信道）主机A主机B带宽浪费！主机A租用两条信道，实际使用的只有一条的容量44基本数据链路协议（15）□方法2：一条线路+2逻辑信道+2单工协议主机A主机B

方法分析：对于主机A，发送两种独立数据：○主机A数据帧○主机B确认帧｝帧结构很相似，如目的地址、源地址等。

改进思路：将数据帧和确认帧合并一起发送？也就是发送数据的同时，将确认信息附到外发的数据帧上。——捎带确认技术（Piggybacking）

新的问题：如果主机暂时没有数据帧发送呢？——等待一段时间后，独立确认45基本数据链路协议（16）□方法3一条线路+2逻辑信道+（2单工协议+捎带技术）双工协议

数据帧和确认帧使用同一种格式（捎带技术）

收到数据帧后，等待一段时间后，发送独立确认帧□方法3分析发送方接收方分组1分组1ACK1分组2分组2ACK2分组3确认机制发送方接收方分组1定时器分组1ACK1分组1定时器分组1ACK1分组2定时器重传机制任何时候，线路上只有一个方向的数据。效率低！46滑动窗口协议（1）发送方接收方数据帧1数据帧1ACK1数据帧2数据帧2ACK2数据帧3数据帧3ACK3◆基本思想在等待确认的时候，继续发送数据帧

一次最多能发送多少帧数据？——窗口值如上例中，窗口值为347滑动窗口协议（2）□数据传输的基本过程12345678910111213141516数据帧WindowSize=8已发并得到确认不能发送已发未得到确认未发但可以发——滑动窗口的来由！48滑动窗口协议（3）◆

1位滑动窗口协议——滑动窗口大小为1□基本过程:发送一帧，等待确认，然后下一帧（停-等协议）一切OK？next_frame_to_send=0;frame_expected=0;from_network_layer(&buffer);=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expected;to_physical_layer(&s);start_timer(s.seq);while(true){…………49□问题1：如果通信双方同时发送数据呢？A发送（0，1，A0）B发送（0，1，B0）B得到（0，1，A0）*B发送（0，0，B0）*A得到（0，1，B0）A发送（0，0，A0）B得到（0，0，A0）B发送（1，0，B1）B发送（0，0，B0）A发送（1，0，A1）即使没有传输错误，也会有一半的帧是重复的！如果提前超时，也会出现类型情况！HOW？滑动窗口协议（4）1位滑动窗口协议分析50滑动窗口协议（5）◆

1位滑动窗口协议分析□问题2：效率低下

卫星通信的例子○

卫星信道50kbps○

往返延时500ms（单程时间为250ms）○数据帧长度为1000bits发送数据时间=1000b/50kbps=20ms确认帧收到时间=500+20=520ms带宽利用率=20/520=3.85%太浪费了！51滑动窗口协议（6）□那么窗口大小为多少帧合适呢？□理想状态：当窗口数据全部发送完毕时，正好第一帧的确认到达！发送者接收者1帧2帧收到1帧，ACK1收到2帧，ACK2n-1帧n帧收到n-1帧，ACKn-1收到n帧，ACKn发送窗口值为nn+1帧n+2帧——管道化技术◆

滑动窗口协议改进52滑动窗口协议（7）□理想的窗口值

假设信道带宽为b位/秒、往返时间为r秒、帧长为m位发送完窗口中n帧的时间=(m*n)/b第一帧确认的时间=m/b+r(m*n)/b=m/b+rn=1+rb/m如卫星通信例子中，理想窗口值n=1+rb/m=1+0.5*50K/1000=26◆

管道技术分析53滑动窗口协议（8）◆

管道技术分析□问题如果在一个很长的帧流中有一帧出错了，如何对待后续的正确帧？□两种基本方法

方法1(回退n帧方法）接收方丢弃所有后续的帧，并且不为丢弃的帧发送确认帧。

方法2(选择性重传）给所有正确接收的帧发送确认帧，给检查到错误的帧发送否定的确认。54滑动窗口协议（9）◆回退n帧技术errordiscardacksendtimeout0

1

E

D

D

D

D

D

D

2

3

4

5

6

7

8

0

1

2

3

4

5

6

7

8

2

3

4

5

6

7

8

resend55滑动窗口协议（10）◆使用回退n帧技术的协议

情况1：发送上层数据第一步：组装帧，捎带确认；第二步：发送数据；第三步：启动定时器；

情况3：定时器超时第一步：将超时间数据帧重新发送一次。第二步：重新启动定时器

情况2：接收到一帧第一步：检查数据是否是新鲜的，如果是，则将数据递交给上层；第二步：检查确认信息，如果是已经发送数据的确认，将有关的定时器终止，发送窗口前移动一格；通信进程基本过程：56滑动窗口协议（11）◆选择性重传技术数据发送方数据接收方1帧2帧3帧4帧ACK1ACK3ACK4NAK257滑动窗口协议（12）◆使用选择性重传技术的协议通信进程基本过程：

情况1：发送上层数据第一步：组装帧，捎带确认；第二步：发送数据；第三步：启动定时器；

情况2：接收到一帧第一步：检查数据是否是新鲜的，如果是，则将数据递交给上层；如果数据出错，则发送否定确认。第二步：检查确认信息，如果是已经发送数据的确认，将有关的定时器终止，发送窗口前移动一格；第三步：如果是否定确认，则将否定确认对应的帧重发；

情况3