[网络协议]计算机网络理论课——数据链路层

一、基本概念

结点：主机、路由器

链路：网络中两个结点之间的物理通道，链路的传输介质主要有双绞线、光纤和微波。分为有线链路、无线链路

数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就枃成籹据链路。

帧：链路层的协议数据单元，封装网络层数据报

数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。

二、功能

数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标杋网络层。其主要作用是加强物理层传输原始比特流的珌能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。

1. 为网络层提供服务。无确认无连接服务，有确认无连接服务，有确认面向连接服务。有连接一定有确认

2. 链路管理，即连接的建立、维持、释放（用于面向连接的服务）。

3. 组帧。

4. 流量控制。

5. 差错控制（帧错/位错）。

1、组帧

封装成帧就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。

莨部和尾部包含许多的控制信息，他们的一个重要作用：帧定界（确定帧的界限）。

帧同步：接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。

组帧的四种方法：1.字符计数法，2字符（节）填充法，3.零比特填充法，4违规编码法。

透明传输是指不管所传数据是什么样的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨碍数据传输的东西。
当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的。

（1）字符计数法

帧首部使用一个计数字段（第一个字节，八位）来标明帧内字符数。

（2）字符（节）填充法

当传送的帧是由文本文件组成时（文本文件的字符都是从键盘上输入的，都是ASC码）。
不管从键盘上输入什么字符都可以放在帧里传过去，即透明传输。当传送的帧是由非ASCII码的文本文件组成时（二进制代码的程序或图像等）。就要采用字符填充方法实现透明传输。

（3）零比特填充法

1. 在发送端，扫描整个信息字段，只要连续5个1，就立即填入1个0
2. 在接收端收到一个帧时，先找到标志字段确定边界，再用硬件对比特流进行扫描。发现连续5个1时，就把后面的0删除。

保证了透明传输：在传送的比特流中可以传送任意比特组合，而不会引起对帧边界的判断错误

（4）违规编码法

由于字节计数法中 Count字段的脆弱性（其值若有差错将导致灾难性后果）及字符填充实现上的复杂性和不兼容性，目前较普遍使用的帧同步法是比特填充和违规编码法

2、差错控制

概括来说，传输中的差错都是由于噪声引起的。
全局性1由于线路本身电气特性所产生的随机噪声（热噪声），是信道固有的，随机存在的。
解决办法：提高信噪比来减少或避免干扰。（对传感器下手）局部性2.外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。
解决办法：通常利用编码技术来解决。

数据链路层编码和物理层的数据编码与调制不同。物理层编码针对的是单个比特，解决传输过程中比特的同步等问题，如曼彻斯特编码。数据链路层的编码针对的是一组比特，它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。

冗余编码：在数据发送之前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之变化，使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则，从而判断是否出错。

（1）奇偶校验码

奇偶校验码特点：只能检査出奇数个比特错误，检错能力为50%

（2）CRC循环冗余码

接收端检错过程
把收到的每一个帧都除以同样的除数，然后检査得到的余数R。

• 余数为0，判定这个帧没有差错，接受。
• 余数为不为0，判定这个帧有差错（无法确定到位），丢弃。

FCS的生成以及接收端CRC检验都是由硬件实现，处理很迅速，因此不会延误数据的传输

（3）海明码

海明码：发现双比特错，纠正单比特错。

确定校验码位数r

$$\begin{array}{r}海明不等式：2^r\ge k+r+1\end{array}$$

要发送的数据：D=101101
数据的位数k=6，
满足不等式的最小r为4，
也就是D=101101的海明码应该有6+4=10位，
其中原数据6位，效验码4位

确定校验码和数据的位置

求出校验码的值

$$\begin{array}{r}P1\oplus D1\oplus D2\oplus D4\oplus D5=0\\ P2\oplus D1\oplus D3\oplus D4\oplus D6=0\\ P3\oplus D2\oplus D3\oplus D4=0\\ P4\oplus D5\oplus D6=0\\ 因此，P1=0，P2=0，P3=0，P4=1\end{array}$$

检错并纠错

$$\begin{array}{r}P1\oplus D1\oplus D2\oplus D4\oplus D5=1\\ P2\oplus D1\oplus D3\oplus D4\oplus D6=0\\ P3\oplus D2\oplus D3\oplus D4=1\\ P4\oplus D5\oplus D6=0\\ 0101=5，因此出错位为5\end{array}$$

3、流量控制和可靠传输

较高的发送速度和较低的接收能力的不匹配，会造成传输岀错，因此流量控制也是数据链路层的一项重要工作。

数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。

• 数据链路层流量控制手段：接收方收不下就不回复确认。
• 传输层流量控制手段：接收端给发送端一个窗口公告。

（1）停止等待协议

除了比特出差错，底层信道还会出现丢包问题。

丢包：物理线路故障、设备故障、病毒攻击、路由信息错误等原因，会导致数据包的丢失

讨论的前提

• 虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据（发送方），一方接收数据（接收方）。
• 因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的。
• “停止等待”就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。

注意：

1. 发完一个帧后，必须保留它的副本。
2. 数据帧和确认帧必须编号。

协议的性能分析
简单但是信道的利用率低

（2）后退N帧协议（GBN）

发送方：

1. 上层的调用上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送；如果窗口已满，发送方只需将数据返回给上层，暗示上层窗口已满。上层等一会再发送。（实际实现中，发送方可以缓存这些数据，窗口不满时再发送帧）。

2. GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到n号帧和它之前的全部帧。

3. 协议的名字为后退N帧/回退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果岀现超时，发送方重传所有已发送但未被确认的帧

接收方
4. 如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK，并将该帧中的数据部分交付给上层。
5. 其余情况都丢弃帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任何失序帧，只需要维护一个信息：expectedseqnum（下一个按序接收的帧序号）。

注意：

若采用n个比特对帧编号，那么发送窗口的尺寸$W_T$应满足：1≤$W_T$≤2n-1.因为发送窗口尺寸过大，就会使得接收方无法区别新帧和旧帧。

性能分析

• 因连续发送数据帧而提高了信道利用率
• 在重传时必须把原来已经正确传送的数据帧重传，是传送效率降低。

（3）选择重传协议（SR）

解决办法：设置单个确认，同时加大接收窗口，设置接收缓存，缓存乱序到达的帧

发送方：

1. 从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧；否则就像GBN一样，要么将数据缓存，要么返回给上层之后再传输。
2. 如果收到ACK，加入该帧序号在窗口内，则sR发送方将那个被确认的帧标记为已接收。如果该帧序号是窗口的下界（最左边第一个窗口对应的序号），则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了并且有序号在窗口内的未发送帧，则发送这些帧。

接收方

1. SR接收方将确认一个正确接收的帧而不管其是否按序。失序的帧将被缓存，并返回给发送方一个该帧的确认帧【收谁确认谁】，直到所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按序交付给上层，然后向前移动滑动窗口
2. 如果收到了窗口序号外（小于窗口下界）的帧，就返回一个ACK

发送窗口最好等于接收窗口。（大了会溢出，小了没意义）
$$W_{Tmax}=W_{Rmax}=2^{n?1}$$

三、信道

点对点链路：两个相邻节点通过一个链路相连，没有第三者。
应用：PPP协议，常用于广域网。

广播式链路：所有主机共享通信介质。
应用：早期的总线以太网、无线局域网，常用于局域网
典型拓扑结构：总线型、星型（逻辑总线型）

介质访问控制的内容就是，采取一定的措施，使得两对节点之间的通信不会发生互相干扰的情况。

1、信道划分

信道划分介质访问控制：将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备。

（1）频分多路复用FDM

用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。频分复用的所有用户在同样的时间占用不同的**带宽（频率带宽）**资源

（2）时分多路复用TDM

将时间划分为一段段等长的时分复用帧（TDM帧）。每一个时分复用的用户在每一个TDM帧中占用固定序号的时隙，所有用户轮流占用信道

统计时分复用
每一个STDM帧中的时隙数小于连接在集中器上的用户数。各用户有了数据就随时发往集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的输入薮据放入STDM帧中，一个STDM帧满了就发出。STDM帧不是固定分配时隙，而是按需动态分配时隙。

（3）波分多路复用WDM

波分多路复用就是光的频分多路复用，在一根光纤中传输多种不同波长（频率）的光信号，由于波长（频率）不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来

（4）码分多路复用CDM

码分多址（CDMA）是码分复用的一种方式
1个比特分为多个码片/片（chip），每一个站点被指定一个唯一的m位的芯片序列
发送1时站点发送芯片序列，发送0时发送芯片序列反码（通常把0写成-1）

• 如何不打架：多个站点同时发送数据的时候，要求各个站点芯片序列相互正交
• 如何合并：各路数据在信道中被线性相加
• 如何分离：合并的数据和源站规格化内积。

假设芯片序列为a，表1，则0为-a，相加传输之后是a+b，乘以a之后是$（a+b）?a$，等于$a^2$，处以长度之后等于1，则传过来是a，否则就是$?a^2$，为0

2、轮询访问介质访问控制

信道划分介质访问控制（ MAC Multiple Access Control）协议：

• 基于多路复用技术划分资源。
• 网络负载重：共享信道效率高，且公平
• 网络负载轻：共享信道效率低

随机访问MAC协议：冲突

• 用户根据意愿随机发送信息，发送信息时可独占信道带宽。
• 网络负载重：产生冲突开销
• 网络负载轻：共享信道效率高，单个结点可利用信道全部带宽

轮询访问MAC协议/轮流协议/轮转访问MAC协议：既要不产生冲突，又要发送时占全部带宽。

轮询协议
主结点轮流“邀请”从属结点发送数据
问题：1轮询开销2等待延迟3.单点故障

令牌传递协议
令牌：一个特殊格式的MAC控制帧，不含任何信息控制信道的使用，确保同一时刻只有一个结点独占信道。
令牌环网无碰撞
每个结点都可以在一定的时间内（令牌持有时间）获得发送数据的权利，并不是无限制地持有令牌。
问题：1令牌开销2.等待延迟3.单点故障

3、随机访问介质访问控制

（1）ALOHA协议

纯ALOHA协议思想：不监听信道，不按时间槽发送，随机重发。
冲突如何检测？
如果发生冲突，接收方在就会检测出差错，然后不予确认，发送方在一定时间内收不到就判断发生冲突。
冲突如何解决？
超时后等一随机时间再重传。

时隙 ALOHA协议的思想：把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道若发生冲突，则必须等到下一个时间片开始时刻再发送

纯 ALOHA比时隙 ALOHA吞吐量更低，效率更低。
纯 ALOHA想发就发，时隙 ALOHA只有在时间片段开始时才能发。

（2）载波监听多路访问协议CSMA（ carrier sense multiple access）

CS：载波侦听/滥监听，每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据。
当几个站同时在总线上发送数据时，总线上的信号电压据动值将会增大（互相叠加）当一个站检测到的信号电压摆动值超过一定门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞，即发生了冲突。
MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上

坚持指的是对于监听信道忙之后的坚持。

1-坚持CSMA思想：如果一个主机要发送消息，那么它先监听信道。

• 空闲则直接传输，不必等待。
• 忙则一直监听，直到空闲马上传输。
• 如果有冲突（一段时间内未收到肯定回复），则等待一个随机长的时间再监听，重复上述过程
• 优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失。
• 缺点：假如有两个或两个以上的站点有数据要发送，冲突就不可避免。

非坚持指的是对于监听信道忙之后就不继续监听。
非坚持CSMA思想：如果一个主机要发送消息，那么它先监听信道。

• 空闲则直接传输，不必等待。
• 忙则等待一个随机的时间之后再进行监听。
• 优点：采用随机的重发延迟时间可以减少冲突发生的可能性。
• 缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低。

p-坚持指的是对于监听信道空闲的处理。
p-坚持CSMA思想：如果一个主机要发送消息，那么它先监听信道。

• 空闲则以概率直接传输，不必等待；概率1-p等待到下一个时间槽再传输。
• 忙则等待一个随机的时间之后再进行监听。
• 优点：既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间的这种方案。

（3）CSMA/CD协议

载波监听多点接入/碰撞检测 CSMA/CD（ carrier sense multiple access with collision detection）

CS：载波侦听/滥监听，每一个站在发送数据之前以及发送数据时都要检测一下总线上是否有其他计算机在发送数据
MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。
CD：碰撞检测（冲突检测），“边发送边监听”，适配器边发送数据边检测信道上信号电压的变化情况，以便判断自己在发送数据时其他站是否也在发送数据。

只要经过2τ时间还没有检测到碰撞，就能肯定这次发送不会发生碰撞

二进制指数规避算法

1. 确定基本退避（推迟）时间为争用期2τ。
2. 定义参数k，它等于重传次数，但k不超过10，即k=mn【重传次数，10】。当重传次数不超过10时，k等于重传次数；当重传次数大于10时，k就不再增大而一直等于10。
3. 从离散的整数集合【0,1，，2k-1】中随机取出一个数r，重传所需要退避的时间就是r倍的基本退避时间，即2rT。
4. 当重传达16次仍不能成功时，说明网络太拥挤，认为此帧永远无法正确发出，抛弃此帧并向高层报告出错。

最小帧长：避免检测应发送完的帧
帧的传输时延至少要两倍于信号在总线中的传播时延。

（4）CSMA/CA协议

载波监听多点接入/碰撞避免 CSMA/CA（ carrier sense multiple access with collision avoidance）

发送数据前，先检测信道是否空闲
空闲则发岀RTS（ request to send），RTs包括发射端的地址、接收端的地址、下一份数据将持续发送的时间
等信息；信道忙则等待。
接收端收到RTS后，将响应CTS（ clear to send）

发送端收到CTS后，开始发送数据帧（同时预约信道：发送方告知其他站点自己要传多久数据）。

接收端收到数据帧后，将用CRC来检验数据是否正确，正确则响应AcK帧。

发送方收到AcK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止（采用二进制指数
退避算法来确定随机的推迟时间）。

CSMA/CD与CSMA/CA
相同点

• CSMA/CD与 CSMA/CA机制都从属于CSMA的思路，其核心是先听再说。换言之，两个在接入信道之前都须要进行监听。当发现信道空闲后，才能进行接入。

不同点

1. 传输介质不同：CSMA/CD用于总线式以太网【有线】，而 CSMA/CA用于无线局域网【无线】。
2. 载波检测方式不同：因传输介质不同， CSMA/CD与 CSMA/CA的检测方式也不同。CSMA/CD通过电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化；而 CSMA/CA采用能量检测（ED）、载波检测（σS）和能量载波混合检测三种检测信道空闲的方式。
3. CSMA/CD检测冲突， CSMA/CA避免冲突，二者出现冲突后都会进行有上限的重传。