第三章数据链路层

此服务的适用范围：无线系统之类的不可靠信道
有确认的面向连接的服务
数据链路层为网络层提供的最复杂的服务 源机器和目的机器在传递任何数据之前，先建立一条
连接。在这条连接上所发送的每一帧都被编上号，数 据链路层保证所发送的每一帧都确实已收到。 保证每帧只收到一次，而且所有的帧都是按正确顺序 收到 为网络层进程间提供可靠传送比特流的服务
接收方也会因无力处理收到的帧而会丢失一些帧。 解决方法：引入流量控制来限制发送方发出的数
据流量，使之不超过接收方的能力。 需要某种反馈机制使发送方知道接收方的情况。 大部分流量控制方案的基本原理相同。
差错检验和纠正
通常数字传输时，差错很少发生 模拟传输经常发生差错 光纤干线差错率很小 无线通信差错率较大 两种基本的处理差错策略： 纠错码 检错码
帧界的确定。2、完全依赖于8位字符，特别是ASCII字 符。 第1点的解决方法：采用字符填充，即在数据中的每个 偶然遇到的DLE字符前，插入一个DLE的ASCII代码。
第2点的解决方法：采用位填充
允许数据帧包含任意个数的比特，而且也允 许每个字符的编码包含任意个数的比特。
工作方式如下：每一帧使用一个特殊的位模 式，即01111110作为开始和结束标志字节。 当发送方的数据链路层在数据中遇到5个连 续的1时，它自动在其后插入一个0到输出比 特流中。
在实际环境中，可能会通过中断来处理，这里 作了简化，忽略了并行活动的细节。
当一个帧到达接收方时，硬件会计算校 验和。若有传输错误，会收到通知 （ event =cksum_err），若无错误，则 收到通知（ event =frame_arrival），利 用from_physical_layer接收进来的帧并做处理。

课件制作人：谢希仁
Note
Byte stuffing is the process of adding 1 extra byte whenever there is a flag or escape character in the text.
课件制作人：谢希仁
Figure 11.2 Byte stuffing and unstuffing
计算机网络（第 5 版）
第 3 章 数据链路层
课件制作人：谢希仁
第 3 章 数据链路层
3.1 使用点对点信道的数据链路层 3.1.1 数据链路和帧 3.1.2 三个基本问题 3.2 点对点协议 PPP 3.2.1 PPP 协议的特点 3.2.2 PPP 协议的帧格式 3.2.3 PPP 协议的工作状态
网络层 链路层
运输层
网络层 链路层
物理层
物理层
物理层
物理层
物理层
课件制作人：谢希仁
3.1 使用点对点信道的数据链路层
3.1.1 数据链路和帧

链路(link)是一条无源的点到点的物理线 路段，中间没有任何其他的交换结点。

一条链路只是一条通路的一个组成部分。

数据链路(data link) 除了物理线路外，还必须 有通信协议来控制这些数据的传输。若把实现 这些协议的硬件和软件加到链路上，就构成了 数据链路。
被接收端 被接收端当作无效帧而丢弃 误认为是一个帧 如果数据中的某个字节的二进制代码恰好和SOH或EOT控制 字符一样，则数据链路层会错误地找到帧的边界，只把部分 帧手下，剩下的丢弃。
以上的传输就不是透明传输，需要解决
课件制作人：谢希仁
解决透明传输问题

定义：在星形拓扑中， 每个设备只与中心控 制器有点到点专用链 路。设备并不互相连 接。中心控制器通常 为集线器Hub。 HUB是一个共享设备，主要提供信号放大和中转 的功能，它把一个端口接收的所有信号向所有端 口分发出去。一些集线器在分发之前将弱信号加 强后重新发出，一些集线器则排列信号的时序以 提供所有端口间的同步数据通信。
连接中设备间相互关系：
对等式：设备平等地共享链路。如环形、 网状拓扑。
主从式：由一个设备控制通话而其他设备 必须通过它进行传输。如星形、树形拓扑。 总线式拓扑适合于任意一种模式。
1、Mesh Topology（网状拓扑） 定义：在网状拓扑中，设备之间实现点对点连接， 每条链路只承载所连接的两站点之 间的通信流量。
CRC是基于二进制除法的。 定义
CRC是通过在数据单元末尾附加一串循环冗余码 或循环冗余校验余数使得整个数据单元可被另一个预 定二进制数(生成函数)所整除。在传输终点，用同一 个数去除输入的数据单元。如果此时不产生余数，则 认为数据单元完全正确，接受该数据单元。有余数则 意味着该数据单元在传输过程中被破坏而拒绝该数据 单元。
余数为0， 所以码字正确。
② 因生成码共5位，所以： 冗余码有4பைடு நூலகம்，为1001 ；
信息码是：110011。
注意：
循环冗余校验CRC只能做到差错检测而不能进行 差错纠错。 循环冗余校验CRC只能做到无差错接受，即“凡 是接收端数据链路层接受的帧，都以非常接近于1的 概率认为这些帧在传输过程中没有产生差错”。 但要使传输到接收端的帧无差错、无丢失、无重 复，按发送顺序接受，就必须加上确认和重传机制。
到达接收方的数据单元首先是数据，然后是 CRC码，接收方将整个数据串(数据+CRC码)当作 一个整体去除以用来产生CRC码的同一个除数。 如果数据串无差错到达接收方，则产生余数0， 数据单元将通过校验；如果在传输中数据单元被改 变，则除法将产生非零余数，数据单元将不能通过 校验。

408考研计算机网络——第三章数据链路层第3章数据链路层结点：主机、路由器链路：网络中两个结点之间的物理通道，传输介质有双绞线、光纤和微波。

分为有线、无线链路数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路帧：链路层的协议数据单元，封装网络层数据报功能：为网络层提供服务、链路管理、组帧、流量控制、差错控制3.1 数据链路层的功能数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层。

其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路·为网络层提供服务无确认无连接服务有确认无连接服务有确认面向连接服务·链路管理即连接的建立、维持、释放（用于面向连接的服务)·组帧（帧定界、帧同步、透明传输）封装成帧：在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。

接收端在收到物理层上交的比特流后，根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束首部和尾部包含许多的控制信息，他们的一个重要作用：帧定界（确定帧的界限）帧同步：接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。

最大传送单元MTU：帧的数据部分的长度上限透明传输：当所传数据中的比特组合恰巧与某一个控制信息完全一样时，采取适当的措施，使收方不会将这样的数据误认为是某种控制信息。

保证数据链路层的传输是透明的组帧的四种方法：字符计数法、字符（节）填充法、零比特填充法、违规编码法·流量控制限制发送方的数据流量，使其发送速率不超过接收方的接受能力✳对于数据链路层：控制的是相邻两结点之间数据链路上的流量对于传输层：控制源端到目的端之间的流量·差错控制位错：循环冗余校验CRC差错控制：自动重传请求ARQ帧错：定时器、编号机制*三个基本问题：封装成帧、透明传输、差错检测3.2 组帧·字符计数法帧首部使用一个计数字段（第一个字节，八位）来标明帧内字符数。

3.2 点对点协议 PPP—4帧格式
先发送
首部
FAC 7E FF 03
字节 1 1 1
协议 2
IP 数据报
信息部分 不超过 1500 字节 PPP 帧
尾部
FCS
F 7E
2
1
3.2 点对点协议 PPP—4帧格式
当 PPP 用在同步传输链路时 ，采用比特填充。
在发送端，只要发现有 5 个 连续 1，则立即填入一个 0 。接收端对帧中的比特流进 行扫描。每当发现 5 个连续 1时，就把这 5 个连续 1 后 的一个 0 删除，
1. 进行串行/并行转换 2. 对数据进行缓存 3. 在计算机的操作系统安装设备驱动程序 4. 实现以太网协议
40
3.3 使用广播信道的数据链路层—概述
IP 地址
计算机
硬件地址
CPU 和 存储器
并行 通信
适配器 （网卡）
至局域网 串行通信
生成发送的数据 把帧发送到局域网 处理收到的数据 从局域网接收帧
(1) 封装成帧 (2) 透明传输 (3) 差错控制 (4)最大传送单元 (5)网络层地址协商
1. PPP 协议不需满足的需求 (1) 纠错
(2) 流量控制
3.2 点对点协议 PPP—3组成部分
PPP 协议有三个组成部分 1. 一个将 IP 数据报封装到串行链路的方法 2. 链路控制协议 LCP (Link Control Protocol) 3. 网络控制协议 NCP (Network Control Protocol)
3.2 点对点协议 PPP—1应用范围
现在全世界使用得最多的数据链路层协议是点对 点协议 PPP (Point-to-Point Protocol)。

计算机网络第3 章数据链路层第3 章数据链路层3.1 数据链路层的基本概念3.1.1 数据链路和帧3.1.2 三个基本问题3.2 点对点协议PPP3.2.1 PPP 协议的特点3.2.2 PPP 协议的帧格式3.2.3 PPP 协议的工作状态第3 章数据链路层（续）3.3 使用广播信道的数据链路层3.3.1 局域网的数据链路层3.3.2 CSMA/CD 协议3.4 使用广播信道的以太网3.4.1 使用集线器的星形拓扑3.4.2 以太网的信道利用率3.4.3 以太网的MAC 层第3 章数据链路层（续）3.5 扩展的以太网3.5.1 在物理层扩展以太网3.5.2 在数据链路层扩展以太网3.6 高速以太网3.6.1 100BASE-T 以太网3.6.2 吉比特以太网3.6.3 10 吉比特以太网3.6.4 使用高速以太网进行宽带接入数据链路层⏹数据链路层使用的信道主要有以下两种类型：⏹点对点信道。

一对一的点对点通信方式。

⏹广播信道。

这种信道使用一对多的广播通信方式，因此过程比较复杂。

广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发送。

数据链路层的简单模型局域网广域网主机H 1主机H 2路由器R 1路由器R 2路由器R 3电话网局域网主机H 1向H 2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R 1R 2R 3H 1H 2从层次上来看数据的流动数据链路层的简单模型( 续）局域网广域网主机H 1主机H 2路由器R 1路由器R 2路由器R 3电话网局域网主机H 1向H 2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R 1R 2R 3H 1H 2仅从数据链路层观察帧的流动3.1 数据链路层的基本概念3.1.1 数据链路和帧⏹链路(link)，即物理链路：⏹指从一个结点到另一个结点的物理线路，中间没有任何其他的交换结点。

第三章数据链路层重点内容（⼀）数据链路层的功能（⼆）组帧（三）差错控制1、检错编码2、纠错编码（四）流量控制与可靠传输机制1、流量控制、可靠传输与滑动窗⼝机制2、停⽌-等待协议3、后退N帧协议（GBN）4、选择重传协议（SR）⼀、使⽤点对点信道的数据链路层1、数据链路和帧链路是⼀条⽆源的点到点的物理线路段，中间没有任何其他的交换结点数据链路除了物理线路外，还必须有通信协议来控制这些数据的传输。

若把实现这些协议的硬件和软件加到链路上，就构成了数据链路常常在两个对等的数据链路层之间有⼀个数字管道，⽽在这条数字管道上传输的数据是帧2、基本问题（功能）（1）封装成帧封装成帧就是在⼀段数据的前后分别添加⾸部和尾部，这样就构成了⼀个帧。

接收端在收到物理层上交的⽐特流，就能根据⾸部和尾部的标记，从收到的⽐特流区别帧的开始和结束（⾸部和尾部还夹杂着控制信息）数据链路帧的特点数据部分的前⾯和后⾯分别添加上⾸部和尾部，构成⼀个完整的帧。

帧是数据链路层的数据传送单元。

⾸部和尾部还包括许多必要的控制信息每⼀种链路层协议都规定了所能传送的帧的数据部分长度上限——最⼤传送单元MTU⼀个控制字符SOH放在⼀个帧的最前⾯，表⽰帧的⾸部开始。

另⼀个控制字符EOT表⽰帧的结束（⼀般情况下，⾸部和尾部的长度加起来⼀般⼩于原始报⽂的长度）（2）透明传输“在数据链路层透明传输数据”表⽰⽆论什么样的⽐特组合的数据都能够通过这个数据链路层链路采⽤字节填充法，来确保上⽅情况的发⽣（3）差错检测传输错误的⽐特占所传输⽐特总数的⽐率称为误码率BER。

例如，误码率为10的负⼗次⽅时，表⽰平均每传送10的⼗次⽅个⽐特就会出现⼀个⽐特的差错在计算机⽹络传输数据时，必须采⽤各种差错检测措施。

⽬的在数据链路层⼴泛使⽤了循环冗余校验技术（CRC）CRC①在发送端，先把数据划分组，假定每组k个⽐特。

现假定待传送的数据M=1010001101（k=10）。

CRC运算就是在数据M的后⾯添加供差错检验⽤的冗余吗，然后构成⼀个帧发送出去，⼀共发送（k+n）位设n=5，P=110101（P是除数），模2运算的结果是：Q=1101010110余数R=01110将余数R作为冗余码添加在数据M的后⾯发送出去，即发送的数据是101000110101110，或2的n次⽅乘以M+R在数据后⾯添加上的冗余码称为帧检验序列FCS循环冗余检验CRC和帧检验序列FCS并不等同CRC是⼀种常⽤的检错⽅法，⽽FCS是添加在数据后⾯的冗余码FCS可以⽤CRC这种⽅法得出，但CRC并⾮⽤来获得到FCS的唯⼀⽅法②在接收端把接收到的数据以帧为单位进⾏CRC检验：把收到的每⼀个帧都除以同样的除数P（摸2运算），然后检验得到的余数R③在接收端对收到的每⼀帧经过CRC检验后，有以下两种情况：（a）若得出的余数R=0，则判定这个帧没有差错，就接受（b）若余数R≠0，则判定这个帧有差错，（但⽆法确定究竟是哪⼀位或哪⼏位出现了差错），就丢弃仅⽤循环冗余检验CRC差错检测技术只能做到⽆差错接受“⽆差错接受”是指：“凡是接受的帧（不包括丢弃的帧），我们都能以⾮常接近于1的概率认为这些帧在传输过程中没有产⽣差错”。

第三章数据链路层1. 一个上层信息被分为10帧，每帧有80%无损坏到达的可能性。

如果数据链路层协不进行差错控制，那么这一信息平均发送多少次，才能完整到达接收方。

２．以下数据碎片出现在一个数据流的中间，在数据流中使用的是课文中的字符填充算法：DEL, STX, A, DLE, ETX,填充后输出是什么？３．如果位串01111011111001111110是经过位填充的，那么输出串是什么？４．帧识别的方法有哪些？各自的优缺点是什么？５．用海明校验码对ASCII字符”Z”（二进制位相编码为1011010）进行编码，并写出ASCII中第四位（即海明码第七位）如果出错的校验过程。

６．证明（m+r+1）<=2r是纠正一比特错的理论底限。

７．数据链路层为什么要引入计时器超时机制和帧编号？８．比较停等式ARQ，退后N帧的ARQ和选择性重传协议的区别？９．在一个1Mb/S的卫星信道上，发送1000bit 长的帧，确认总捎带在数据帧中，帧头很短，使用3位序列号，对于3种协议可以获得的最大信道利用率是多少？10．在HDLC中，控制字段起的作用是什么？它的每一个表示什么意思？答案：1．解：∵每帧有80%正确到达的可能性∴10帧都安全到达的可能性为（80%）10≈10.74%∴这一信息大约传送1/10.74%≈10次可以完整到达2、答：填充后的输出如下：DLE DLE STX A DLE DLE DLE DLE ETX3、答：删除填充位后，输出串应是：011110111114、答：帧识别的方法有五种：(1)计时法；(2)字符计数法；(3)带字符填充的首尾界符法；(4)带位填充的首尾标志法；(5)物理编码违例法。

各自优缺点：(1)计时法其缺点是每帧中间有时间间隔，不能充分利用线路；(2)字符计数法是在帧头部使用一字段来整数标明该帧的长度，并且可以知道下一个帧的开始位置；其缺点是标识位错时不可修复；(3)带字符填充的首尾界符法是每一帧以ASCII字符序列DLE STX头，以DLE ETX结束，可方便目的机丢失帧边界的查找；其缺点可能会导致干扰帧界的确定，该方法所传输的帧必须是7/8bit的整数倍(即ASCII编码整数倍)(4)带位填充的首尾标志法的优点是对通信双方计算机的网络层都是透明的，使用一个特定的位模式，即01111110作为帧的开始和结束标志，为使之不出出错误判断，发送方在连续5个1后自动插入一个0，接收方将会自动删除。

停止等待协议的定量分析 (图3-5)
两个发送成功的数据帧间的最小时间间 隔tT为：
tT= tf+tout= tf+2tp
正确传送一个数据帧所需的平均时间t 正确传送一个数据帧所需的平均时间tav 为：
tav=tT/(1-p) /(1最大吞吐量λmax=
(3(3-5)
(1(1-p)/ tT
(念
数据链路： 把实现用来控制数据传输的规程的硬件 和软件加到链路上，就构成了数据链路。 链路： 一条无源的点到点的物理线路段，中间 无交换结点。（物理链路）
数据链路层的功能
1. 2. 3. 4. 5. 6. 7. 链路管理 帧同步 流量控制 差错控制 将数据和控制信息区分开 透明传输 寻址
发送窗口
接收窗口
发送窗口的最大值
WT≤
n-1 2
3.4 选择重传ARQ协议
可以避免重复传送已正确到达接收端的数 据帧。但要在接收端设置缓存空间。
WR≤ WR(max) WT= WR=2n/2 n=4 WT= WR=4
n/2 2
3.5面向比特的链路控制规程HDLC
面向字符 在链路上所传送的数据是规定的字符集 （如ASCII码）中的字符所组成；并且， （如ASCII码）中的字符所组成；并且， 传送的控制信息也是同一个字符集中的 若干控制字符构成。 缺点与发展
标志 8
地址 8
控制 8
信息 可变
FCS 16
标志 8
地址： 在用非平衡方式传送数据时，地址字段总是 写入次站的地址； 在平衡方式（采用ABM），总是填入应答站 在平衡方式（采用ABM），总是填入应答站 的地址。 全1地址：广播方式 全0地址：无效地址 扩展地址：第1 扩展地址：第1位表扩展位，其余表地址位。 (0 或1)

物理层用不同的信号表示二进制数据位，从而把帧用一 段连续的信号串表示并传送到目的主机
目的主机的物理层将信号还原成比特串交数据链路层， 井数据链路层确认正确后送到网络层
数据链路层为源和目的主机的网络层之间提供一条可靠
的数据链路
第3章 数据链路层 3 / 169
《Computer Networks v5》 cs.sjtu 1/16/2020
第3章 数据链路层 28 / 169
《Computer Networks v5》 cs.sjtu 1/16/2020
差错检测和校正
《Computer Networks v5》 cs.sjtu 1/16/2020
第3章 数据链路层
定义和功能 数据帧的组成 可靠性传输 数据链路层示例
第3章 数据链路层 1 / 169
《Computer Networks v5》 cs.sjtu 1/16/2020
数据链路层的定义
数据链路层的上层是网络层，数据链路层 将借助于物理层为网络层提供服务
确认和连接
确认：接收方在收到数据帧后，必须给 发送方发回一个确认
面向连接：发送方和接收方在传输数据 之前必须建立一条数据链路，传输结束 后必须释放该链路
第3章 数据链路层 6 / 169
《Computer Networks v5》 cs.sjtu 1/16/2020
数据链路层的服务
无确认无连接的服务 有确认无连接的服务 有确认有连接的服务
第3章 数据链路层
定义和功能 数据帧的组成 可靠性传输 数据链路层示例
第3章 数据链路层 14 / 169
《Computer Networks v5》 cs.sjtu 1/16/2020

第3章 数据链路层
应当注意




仅用循环冗余检验 CRC 差错检测技术只能做到 无差错接受(accept)。 “无差错接受”是指：“凡是接受的帧（即不 包括丢弃的帧），我们都能以非常接近于 1 的 概率认为这些帧在传输过程中没有产生差错”。 也就是说：“凡是接收端数据链路层接受的帧 都没有传输差错”（有差错的帧就丢弃）。 要做到“可靠传输”（即发送什么就收到什么） 就必须再加上确认和重传机制。 注意“无比特差错”和“无传输差错”的区别。
传输差错的种类
例如发送方连续发送三个帧： [#1]-[#2]-[#3] ，以下 情况属于传输差错： 帧丢失。 接收方收到[#1]-[#3]，即丢失[#2]。 帧重复。 接收方收到[#1]-[#2]-[#2]-[#3]，即重复[#2]。 帧失序。 接收方收到[#1]-[#3]-[#2]，即[#2]与[#3]颠倒。
第3章 数据链路层
标准的CRC生成多项式

CRC-12 CRC-16
G(x)=x12+x11+x3+x2+x+1 G(x)=x16+x15+x2+1

CRC-CCITT G(x)=x16+x12+x5+1 CRC-32 G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8 +x7+x5+x4+x2+x+1
仅从数据链路层观察帧的流动
第3章 数据链路层
3.1 使用点对点信道的数据链路层 3.1.1 数据链路和帧


链路(link)是一条无源的点到点的物理线路段， 中间没有任何其他的交换结点。 一条链路只是一条通路的一个组成部分。 数据链路(data link) 除了物理线路外，还必须 有通信协议来控制这些数据的传输。若把实现 这些协议的硬件和软件加到链路上，就构成了 数据链路。 现在最常用的方法是使用适配器（即网卡） 来实现这些协议的硬件和软件。 一般的适配器都包括了数据链路层和物理层 这两层的功能。

§3.4 基本数据链路协议
• 一种无限制的单工协议（An Unrestricted Simplex Protocol）
• 停-等协议（Stop-and-Wait Protocol） • 有噪音信道的停-等协议（Stop-and-Wait
Protocol for a Noisy Channel）
协议1：一种无限制的单工协议（乌托邦）
差错控制策略
• 检/纠错码的检/纠错能力与编码集的海明距离有关，海 明距离越大，检/纠错能力就越强，但所需的冗余信息 就越多，编码效率就越低。
• 由于纠错码比检错码要求更大的海明距离，且技术复 杂，纠正可靠性不高，所以一般很少使用，只有在没 有反馈信道的单工通信中，为了确保可靠才会采用。
• 在大多数通信中采用的是检错编码。接收方收到帧后， 对其进行校验检查，并发回相应的反馈信息。发送方 根据反馈信息来决定是继续发送新帧（肯定应答）， 还是重发出错的旧帧（否定应答）。
• 两个码字中对应比特位取值不同的位的个数称作海明距离 （Hamming Distance）。如10001001和10110001的海明距离为3。
• 在一个编码集中，任意两个有效码字的海明距离的最小值称作该 编码集的海明距离。检错与纠错的能力取决于海明距离。
有关检错和纠错的两个重要结论
• 如果要检测出d个比特错误，则编码集的海明距离至少应为d+1。 – 说（证）明：若一个有效码字只出错< d+1个比特，则肯定变 为一个无效码字，从而被检测出来。若出错d+1，则变为有效 码字，不能检出。
• 帧的其它地方绝对不会出现这样的边界码字。
§3.3 差错的检测和纠正
涉及两方面理论与技术： • 差错检测
– 差错控制编码