[计算机网络004]链路层概述

一、链路层的常用术语以及提供的服务：

一句话概括其功能:负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。

术语集合：

1.主机和路由器：结点（nodes)

2.连接相邻结点的通信信道：链路（links）包括：

有线链路（wired links）

无线链路 （wiredless links）

局域网（LANS）

3.链路层数据分组：帧（frame），封装网络层数据报。

链路层服务：

1.组帧（framing）：封装数据报构成数据帧，加首部和尾部。

2.链路接入（link access）：如果是共享介质，那么需要解决信道接入（channel access），对于帧的首部的MAC地址，是用于标识帧的源和目的地

3.相邻节点间的可靠交付：在低误码率的有线链路上很少采用（如光纤、某些双绞线等等）。无线链路：误码率比较高，需要我们采用可靠交付的服务。

4.流量控制（flow control)：协调相邻的发送节点和接收。

5.差错检测：信号衰减和噪声会导致引起差错，接收端检测到差错后会通知发送端重传或者直接丢弃帧。

6.差错纠正（error correction）：接收端直接纠正比特差错。 

7.全双工和半双工通信控制：

全双工：链路两端节点同时双向传输。

半双工：链路两端节点交替双向传输。

二、链路层的具体实现：

1. 硬件实现

   • 网络适配器（网卡）：网络适配器，也称为网卡，是计算机与物理网络之间的接口，负责接收和发送数据帧，并通过物理介质与其他设备进行通信。

   • 链路层控制器：位于网卡核心的链路层控制器是一个专用芯片，实现了众多链路层服务，如帧封装、解封装和差错检测等。（即网卡之中包含有链路层控制器）

   • 

2. 软件实现

   • 驱动程序：操作系统或网络协议栈中的驱动程序与硬件设备进行交互，控制数据链路层的操作，管理帧的封装和解封装、错误检测和纠正、流量控制等功能。

   • 帧格式设计：合理设计帧的格式，包括帧头、帧尾和帧中的字段，以适应不同的网络需求和协议要求。

   • 差错检测与纠正技术：选择适合的差错检测与纠正技术，确保数据传输的可靠性。

   • 流量控制和拥塞控制：设计合理的流量控制和拥塞控制机制，以避免数据发送过程中的丢包和拥塞。

   • 多路访问控制：在共享介质的网络中，实现多路访问控制，以允许多个发送端共享网络资源。

二、差错编码： 

1.基本原理:

 2.差错编码的检错/纠错能力：

(1)汉明距离的概念：

汉明距离是以理查德·卫斯里·汉明的名字命名的，在信息论中，它表示两个等长字符串在对应位置上不同字符的个数。那么再引出编码集的汉明码：作为一个编码集内的所有的有效码字，在任意两码子之间的汉明距离的最小值。例如{0000，0101，1010，1111}这样一个编码集之中，其汉明距离为2。

(2)差错编码的检错能力：

对于检错码而言：如果一个，编码集的汉明距离d=r+1，则该差错编码可以检测出r位错误。{0000，0101，1010，1111}这样一个编码集之中，其汉明距离为2。则可以检测出1比特差错。

(3)差错编码的纠错能力：

对于纠错码而言：如果汉明距离d=2r+1,则该纠错码可以纠正r位的差错。

例如：编码集{000000，010101，101010，111111}的汉明距离为3，则可以纠正1比特差错：例如将010001纠正为010101

(4）奇偶校验码：

①1比特法：

当确定是奇偶校验以后，我们选择添加一位0或者1，以满足我们的奇偶规则。

②二维奇偶校验：

假设发送的数据：10101 11110 01110共15比特。将要传的信息D（d比特）划分为i行j列，即i个组，每组j位。这里我们划分为3组每一组有5位。对每行和每列分别计算奇偶值。如果采用偶校验，则使每行和每列中1的个数为偶数；如果采用奇校验，则使每行和每列中1的个数为奇数。结果的i+j+1个奇偶比特构成了帧的差错检测比特，这些校验位被附加到原始数据后面

三、MAC协议：

1.定义：

多路访问控制协议是数据链路层中用于管理多个设备如何共享通信介质的一组规则和算法。

2.理想的MAC协议：

理想MAC：

当我们给定速率为Rbps的广播通道时，我们期望当只有一个节点接入我们的链路想传输数据时，它可以以Rbps的速率传输。当有M个节点期望发送数据的时候，每个节点平均发送数据的速率为R/M。并且无需特定的节点协调，无需时钟。

3.信道划分MAC协议：

(1).TDMA协议：

1. 时间划分：TDMA将时间划分为一系列连续的时隙，每个时隙分配给一个节点使用。这些时隙按照固定的顺序循环，确保所有节点都有机会发送数据。

2. 帧结构：一个复用帧内包含了所有结点在自己时隙里发送的数据。每个节点只能在自己的时隙内发送数据，而不能占用其他节点的时隙。

3. 同步机制：TDMA需要严格的时间同步机制，以确保所有节点都能准确地在指定的时隙内发送数据。这通常通过全局时钟或网络中的主节点来实现。

4. 资源保留：即使某个节点在某个时隙内没有数据要发送，该时隙也会被保留给这个节点，不能被其他节点占用。这种方式虽然简单，但在网络负载较低时可能会导致信道资源的浪费。

(2).FDMA协议： 

FDMA通过将可用的带宽划分成不同的频带，为每个站点分配一个特定的频带用于数据传输。这种技术特别适用于模拟信号的传输，并且可以通过带通滤波器来限定传输器的频率，以防止站点间的冲突。在FDMA系统中，每个用户以单一频率发送和接收，从而避免了时间同步问题，使得流数据可以容易地用于FDMA。

4.随机访问MAC协议： 

当节点要发送分组的时候：利用信道的全部数据速率R发送分组，无需进行事先的节点之间的协调。如果遇到两个或者更多的节点同时传输的时候：会进一步导致冲突。所以在该协议之中我们需要解决：①如何检测出冲突，②如何从冲突之中恢复。

(1)时隙ALOHA协议：

我们设计这样的假定前提条件：

所有的帧大小相等。

时间被划分为等长的时隙，每一个等长的时隙只可以传输一个帧。节点只能在时隙开始的时刻发送帧，节点之间时钟同步。如果两个或高度的帧在他同一个时隙发送帧，那么节点就可以检测到冲突。

这样以后我们就有可以运行的过程：

当节点有了新的帧以后，会在下一个时隙发送：

若当前没有冲突：该节点可以在下一个时隙继续发送新的帧。

如果当前有冲突：那么该节点在下一个时隙会以概率p重传该帧，直到成功。

上述过程是同步进行的一个过程

下面是一个示意图：

在初始的时刻，三个节点同时向链路传输数据，显然这样导致了冲突（conflict），接下来三个节点都会以概率p去重新发送数据，下一阶段显然没有一个节点重新发送（empty）接下来节点1和节点2同时发送了数据帧，显然这导致了冲突，下一阶段只有节点2发送了数据帧，成功了（succeed）后续过程类似。

对于效率分析：

假设有N个节点有很多帧待传输，每个节点在每个时隙下均以概率P发送数据，对于一个给定的节点，在一个间隙将帧成功的发送成功的概率=p(1-p)的N-1的次方。那么进一步对于任意节点可以成功发送的概率=N*p(1-p)的N-1的次方。当获取最大的效率时，即令该表达式最大：此时的概率为p*，当N区域无穷的时候，最大效率=1/e=0.37。

(2)ALOHA协议：

相比于时隙ALOHA协议而言更加的简单，无需考虑同步的问题，有新的帧就立刻发送，不过这样导致了冲突的可能性增大。此时效率为1/2e=0.18.

这两种协议都有损人不利己的特点哈哈哈哈

(3)CSMA协议：

即载波监听多路访问协议CSMA。

①载波监听（CS）：在发送数据之前，设备会监听传输介质上是否有其他设备正在传输数据。如果介质闲置，设备将开始发送数据；如果介质忙碌，设备将等待一段随机的时间后再次尝试。②多点访问（MA）：多个设备共享同一介质，因此可能会出现竞争。CSMA协议使用随机等待时间来减少冲突，以避免多个设备同时发送数据。

根据侦听方式和侦听到信道忙后的处理方式不同，CSMA协议分为三种。
1-坚持CSMA:一个结点要发送数据时，首先侦听信道，如果信道空闲，那么立即发送数据；侦听到信道忙后，继续坚持侦听信道；侦听到信道空闲后，发送帧的概率为1，即立即发送数据。
非坚持CSMA：一个结点要发送数据时，首先侦听信道，如果信道空闲，那么立即发送数据；如果信道忙，那么放弃侦听，等待一个随机的时间后再重复上述过程。
p-坚持CSMA：用于时分信道。一个结点要发送数据时，首先侦听信道，如果信道忙，就持续侦听，直至信道空闲；如果信道空闲，那么以概率p发送数据，以概论1-p推迟到下一个时隙。

这里我有一个问题：

为什么明明在CSMA协议之中，我们拥有了检测链路是否空闲的功能，那我们为什么还要引入冲突检测呢？

回答来自讯飞星火：

在CSMA（载波侦听多路访问）协议中，设备在发送数据前会先检测媒体是否空闲，这确实减少了数据碰撞的可能性。然而，仅仅依赖载波侦听并不能完全避免碰撞，尤其是在以下情况下：

1. 传播延迟：信号从发送端传播到接收端需要时间。如果两个设备相隔较远，它们可能同时检测到媒体空闲，并同时开始发送数据，导致在信号传播的途中发生碰撞。

2. 隐藏终端问题：在无线局域网中尤为常见，当两个设备都在彼此的通信范围之外，但都能与同一个设备通信时，它们可能同时尝试与该设备通信，从而发生碰撞。

3. 暴露终端问题：当一个设备因为检测到媒体上有传输而选择不发送数据时，它实际上可能会阻止对其他设备的传输，即使这些传输并不冲突。

①CSMA/CD协议：

这里的CD:Collision Detection（冲突检测）

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

CSMA/CD的工作流程可简单概括为“先听后发，边听边发，冲突停发，随机重发”。

在发送过程中出现碰撞的原因：电磁波在总线上的传播速率总是有限的，因此，当某个时刻发送站检测到信道空闲时，此时信道并不一定是空闲的。

若在发送过程中检测到碰撞，则中止数据的发送，并发送一个拥塞信号，让所有用户都知道。在中止发送后，适配器就执行指数退避算法，等待一段时间后重新发送。

我们如何可靠的实现这个碰撞检测呢？我们考虑最极限的一个情况：

如图所示：四台主机都共享怎么一条链路，我们令其最大长度为dmax,网络带宽为：Rbps，数据帧最小长度为Lmin(bits)，信号传播速度V(m/s)。

现在主机A向主机B发送数据帧，当第一个比特的数据即将到达B的时候，此时主机B想要发送数据帧进而导致冲突。对于主机B它接受到链路非空闲的时间：time1=2dmax/V。对于A发出的数据帧而言其到达B的用时也可以计算出来：time2=R/L我们必须满足我们的冲突信号比A发送的数据帧先一步到达B。即time1<=time2.

例题：在一个采用CSMA/CD协议的网络之中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆之中信号传输速度为200000km/s，如果最小数据帧的长度减少800比特，则最远的两个站点中间的距离至少需要一个怎么样的变化？

特点： CSMA/CD协议之中的节点无法同时进行发送和接受，只可以进行半双工通信。不足之处：但是在无线局域网中不能使用碰撞检测CD，由于无线信道的传输条件特殊，其信号强度的波动范围非常大，无线网卡上接收到的信号强度往往会远远小于发送信号的强度，可能相差百万倍。如果要在无线网卡上实现碰撞检测，对硬件的要求非常高。

②CSMA/CA协议： 

 即载波侦听多路访问/碰撞避免协议，对·CSMA/CD协议进行修改，将碰撞检测更新为碰撞避免。（这里的避免是指尽量减少碰撞发生的概率）

这里的CA:Collision Avoid（冲突避免）

CS:载波侦听/监听，每一个站在发送数据之前以及在发送数据时都要检测一下总线上是否有其他计算机在发送数据。
MA:多点接入，表示许多计算机以多点接入的方式连接在一根总线上

CA:主机发送信号时，尽可能地避免发送碰撞

协议的具体工作方式包括载波监听、随机等待和渐进增加重传三个主要步骤：

1. 载波监听：在发送数据之前，设备会先监听信道是否空闲。如果信道空闲，设备可以开始发送数据；如果信道忙，则设备需要等待直到信道变为空闲状态。
2. 随机等待：当设备检测到信道被占用时，它会随机选择一个等待时间，然后在等待时间结束后再次侦听信道是否空闲。这个过程称为随机退避，它有助于减少多个设备同时尝试发送数据时发生冲突的可能性。
3. 渐进增加重传：如果设备在等待时间结束后发现信道仍然被占用，它将等待一个更长的等待时间，并在之后再次尝试发送数据。这个过程称为渐进增加重传，它可以进一步减少冲突的可能性