链路层（一）

博主： Xherlock
发布时间：2022 年 06 月 06 日
413 次浏览
暂无评论
4500字数
分类：计算机网络

# 链路层（一）

## 概述

结点：运行链路层协议的设备，包括主机、路由器、交换机

链路：沿着通信路径连接相邻结点的通信信道

传输结点将数据报（datagram）封装在链路层帧（frame）中

（链路层协议：Ethernet、frame relay帧中继、802.11）

**提供的服务**

* 成帧（framing）：header+datagram+trailer
* 链路接入（link access）：MAC（媒体访问控制，medium access control）协议规定了帧在链路上传输的规则
* 可靠交付（reliable delivery）：主要在无线链路上使用，错误率较高
* 流量控制
* 错误检测：由信号衰减和电磁噪声导致的
* 错误纠正：接收方检测并准确纠错
* 半双工和全双工

**何处实现**

链路层主体：网络适配器（network adaptor，也称网卡NIC）

![image-20220605214734128.png](http://xherlock.top/usr/uploads/2022/06/4203325970.png)

## 差错检测和纠正

EDC=Error Detection and Correction bits错误检测和纠正位

D=Data protected by error checking

![image-20220605215336940.png](http://xherlock.top/usr/uploads/2022/06/1420977691.png)

### 奇偶校验（parity checking）

单个奇偶校验位：设发送信息里有d个比特

**偶校验方案**：发送方附加一个比特，使得d+1个比特中1的总数是偶数；若发现接收到的有奇数个1比特，说明出现了至少一个比特差错（奇数个）；若发生偶数个比特差错会无法检测到错误

**奇校验方案**：发送方附加一个比特，使得d+1个比特中1的总数是奇数

*需要更健壮的差错检测方案*：二维奇偶校验（two-dimensional parity）

包含比特值改变的行与列的校验值都将出现差错，可以用行和列的索引定位差错比特来纠正

![image-20220605220936766.png](http://xherlock.top/usr/uploads/2022/06/2216955882.png)

FEC：前向纠错（forward error correction），接收方检测和纠正错误的能力

### 因特网校验和（internet checksum）

16-bit处理，同传输层校验和

链路层使用CRC而不是校验和：在适配器中专用硬件实现，可以快速执行复杂的CRC操作

### 循环冗余检测（cyclic redundancy check）

广泛应用，也称多项式编码（polynomial code）

发送方和接收方首先协商一个r+1比特模式称为生成多项式（generator，G，最高有效位为1）

![image-20220605222403332.png](http://xherlock.top/usr/uploads/2022/06/4073378681.png)

d+r比特模式恰好能被G整除

计组学过了

## 多路访问链路和协议

点对点链路（point-to-point）：由链路一端的单个发送方和链路另一端的单个接收方组成，协议有PPP、HDLC

广播链路（broadcast）：能够让多个发送和接收结点都连接到相同的、单一的、共享的广播信道上

多个结点可能会同时传输帧，结点可能会同时接收到多个帧，发生碰撞（collide），此时所有帧均丢失，碰撞时间间隔内的广播信道被浪费掉了。

MAC（multiple access protocol，多路访问协议）的作用就是决定结点如何共享信道，如何传输

理想化的多路访问协议应该有（速率R bps的广播信道）：

* 当仅有1个结点想发送数据时，该结点具有R bps的吞吐量
* 当有M个结点想发送数据时，每个结点吞吐量为R/M bps，具有R/M 的平均传输速率
* 协议是分散的（去中心化的）：不会因为某主节点的故障而使整个相同崩溃
* 简单、不贵

### 信道划分协议（channel partitioning protocol）

**TDMA**：时分多路访问（time division multiple access）

TDM将时间划分为时间帧，并进一步划分每个时间帧为N个时隙（slot），然后把每个时隙分给N个结点中的一个

eg：发送1、3、4

![image-20220606092531109.png](http://xherlock.top/usr/uploads/2022/06/72686385.png)

特点：消除了碰撞且公平；得到专用的传输速率R/N bps；但被限制速率，且必须按顺序传输

**FDMA**：频分多路访问（frequency division multiple access）

![image-20220606093037050.png](http://xherlock.top/usr/uploads/2022/06/2915436837.png)

**CDMA**：码分多址（code division multiple access）

为每个结点分配一种不同的编码，每个结点使用它唯一的编码对传输的数据进行编码；各自对应的接收方可正确接收发送方编码后的数据而不在乎其他结点的干扰传输（用于军用系统、蜂窝电话cellular telephony）

### 随机访问协议（random access protocol）

在这个协议中，一个传输节点总是以信道的全部速率进行发送，当有碰撞时，涉及碰撞的每个结点反复地重发它的帧，直到无碰撞（允许碰撞）；但是当一个结点经历一次碰撞后，不必立即重发帧，而是等待一个随机时延（时延选择相互独立）。

#### 时隙slotted ALOHA

假设：

* 所有帧大小为L比特
* 时间被划分为长度为L/R秒地时隙
* 结点只在时隙起点开始传输帧
* 结点是同步的，每个结点都知道时隙何时开始
* 若在一个时隙中，有两个或更多个帧碰撞，则所有结点在该时隙结束前检测到该碰撞事件

操作：

* 当结点有新帧要发送时，等到下一个时隙开始并在该时隙传输整个帧
* 有碰撞：时隙结束前检测到碰撞，以概率p在后续的每个时隙重传帧，直到帧无碰撞的传输出去
* 无碰撞：成功传输

![image-20220606100906644.png](http://xherlock.top/usr/uploads/2022/06/2565194181.png)

**时隙多路访问协议的效率**：当有大量的活跃结点且每个结点总有大量的帧要发送时，长期运行中成功时隙的份额

时隙ALOHA：N个活跃结点——$Np(1-p)^{N-1}$，最大1/e，0.37

#### 纯pure ALOHA

当第一个帧首次到达，结点立刻将该帧完整地传输进广播信道；

若有碰撞：立即以p概率重传

若无碰撞：以1-p的概率等待一段时间后传输下一帧，以p概率传输下一帧

![image-20220606102022244.png](http://xherlock.top/usr/uploads/2022/06/2883028743.png)

P(success by given node) = P(node transmits)·P(no other node transmits in [t0-1,t0 ]·P(no other node transmits in [t0 ,t0 +1]=$p·(1-p)^{N-1}·(1-p)^{N-1}$=$ p·(1-p)^{2(N-1)}$

P(success for *any* node) = $ N·p·(1-p)^{2(N-1)}$

最大效率：1/2e=0.18

#### CSMA（carrier sense multiple access，载波侦听多路访问）

* 如果信道空闲：传输整个帧
* 如果信道繁忙（其他结点在传输数据），以随机时间推迟传输直到信道空闲

但是推迟传输仍可能出现碰撞，因为两个结点都听不到对方；同时碰撞后两者仍继续传输，浪费时间

#### CSMA/CD（具有碰撞检测的载波侦听多路访问）

有碰撞立刻停止传输，这样就可以停止传输一个无用的、（由另一个结点的帧干扰）损坏的帧

![image-20220606223001756.png](http://xherlock.top/usr/uploads/2022/06/1154274331.png)

**算法**

1. NIC适配器从网络层接收数据报，准备好帧
2. 如果NIC侦听到信道空闲，开始传输帧；若侦听到忙，将等待直到空闲
3. 传输过程中，若NIC传输完整个帧而没有监听到其他适配器的信号能量，完成传输
4. 若监听到其他适配器能量，终止传输（发送48比特拥堵信号）
5. 等待一个随机时间后返回步骤2（使用二进制指数后退，binary exponential backoff）

发生n次冲突后，NIC从{$0,1,2,3…, 2^{n-1}$}中随机选择一个值赋给K，并等待K·512 bit times，即K倍发送512bit数据所消耗的时间，n最大取10

效率接近1

### 轮流协议

**轮询协议**（polling protocol）

主结点以循环的方式轮询每个结点，告诉每个结点最多传输帧的数量

**令牌传递协议**（token-passing protocol）

没有主结点，一个称为令牌的小的特殊帧在结点之间以某种固定的次序进行交换；当一个结点收到令牌时，如果有帧发送就持有这个令牌，否则传给下一个结点

分散的，效率很高，但是可能会出现一个结点故障或忘记释放令牌导致整个信道崩溃

### 小结

![image-20220606225714313.png](http://xherlock.top/usr/uploads/2022/06/2416437842.png)

最后修改：2022 年 06 月 16 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

链路层（一）

Xherlock • 2022 年 06 月 06 日

# 链路层（一）

## 概述

结点：运行链路层协议的设备，包括主机、路由器、交换机

链路：沿着通信路径连接相邻结点的通信信道

传输结点将数据报（datagram）封装在链路层帧（frame）中

（链路层协议：Ethernet、frame relay帧中继、802.11）

**提供的服务**

**何处实现**

链路层主体：网络适配器（network adaptor，也称网卡NIC）

![image-20220605214734128.png](http://xherlock.top/usr/uploads/2022/06/4203325970.png)

## 差错检测和纠正

EDC=Error Detection and Correction bits错误检测和纠正位

D=Data protected by error checking

![image-20220605215336940.png](http://xherlock.top/usr/uploads/2022/06/1420977691.png)

### 奇偶校验（parity checking）

单个奇偶校验位：设发送信息里有d个比特

**奇校验方案**：发送方附加一个比特，使得d+1个比特中1的总数是奇数

*需要更健壮的差错检测方案*：二维奇偶校验（two-dimensional parity）

包含比特值改变的行与列的校验值都将出现差错，可以用行和列的索引定位差错比特来纠正

![image-20220605220936766.png](http://xherlock.top/usr/uploads/2022/06/2216955882.png)

FEC：前向纠错（forward error correction），接收方检测和纠正错误的能力

### 因特网校验和（internet checksum）

16-bit处理，同传输层校验和

链路层使用CRC而不是校验和：在适配器中专用硬件实现，可以快速执行复杂的CRC操作

### 循环冗余检测（cyclic redundancy check）

广泛应用，也称多项式编码（polynomial code）

发送方和接收方首先协商一个r+1比特模式称为生成多项式（generator，G，最高有效位为1）

![image-20220605222403332.png](http://xherlock.top/usr/uploads/2022/06/4073378681.png)

d+r比特模式恰好能被G整除

计组学过了

## 多路访问链路和协议

点对点链路（point-to-point）：由链路一端的单个发送方和链路另一端的单个接收方组成，协议有PPP、HDLC

广播链路（broadcast）：能够让多个发送和接收结点都连接到相同的、单一的、共享的广播信道上

多个结点可能会同时传输帧，结点可能会同时接收到多个帧，发生碰撞（collide），此时所有帧均丢失，碰撞时间间隔内的广播信道被浪费掉了。

MAC（multiple access protocol，多路访问协议）的作用就是决定结点如何共享信道，如何传输

理想化的多路访问协议应该有（速率R bps的广播信道）：

### 信道划分协议（channel partitioning protocol）

**TDMA**：时分多路访问（time division multiple access）

TDM将时间划分为时间帧，并进一步划分每个时间帧为N个时隙（slot），然后把每个时隙分给N个结点中的一个

eg：发送1、3、4

![image-20220606092531109.png](http://xherlock.top/usr/uploads/2022/06/72686385.png)

特点：消除了碰撞且公平；得到专用的传输速率R/N bps；但被限制速率，且必须按顺序传输

**FDMA**：频分多路访问（frequency division multiple access）

![image-20220606093037050.png](http://xherlock.top/usr/uploads/2022/06/2915436837.png)

**CDMA**：码分多址（code division multiple access）

### 随机访问协议（random access protocol）

#### 时隙slotted ALOHA

假设：

操作：

![image-20220606100906644.png](http://xherlock.top/usr/uploads/2022/06/2565194181.png)

**时隙多路访问协议的效率**：当有大量的活跃结点且每个结点总有大量的帧要发送时，长期运行中成功时隙的份额

时隙ALOHA：N个活跃结点——$Np(1-p)^{N-1}$，最大1/e，0.37

#### 纯pure ALOHA

当第一个帧首次到达，结点立刻将该帧完整地传输进广播信道；

若有碰撞：立即以p概率重传

若无碰撞：以1-p的概率等待一段时间后传输下一帧，以p概率传输下一帧

![image-20220606102022244.png](http://xherlock.top/usr/uploads/2022/06/2883028743.png)

P(success by given node) = P(node transmits)·P(no other node transmits in [t0-1,t0 ]·P(no other node transmits in [t0 ,t0 +1]=$p·(1-p)^{N-1}·(1-p)^{N-1}$=$ p·(1-p)^{2(N-1)}$

P(success for *any* node) = $ N·p·(1-p)^{2(N-1)}$

最大效率：1/2e=0.18

#### CSMA（carrier sense multiple access，载波侦听多路访问）

* 如果信道空闲：传输整个帧
* 如果信道繁忙（其他结点在传输数据），以随机时间推迟传输直到信道空闲

但是推迟传输仍可能出现碰撞，因为两个结点都听不到对方；同时碰撞后两者仍继续传输，浪费时间

#### CSMA/CD（具有碰撞检测的载波侦听多路访问）

有碰撞立刻停止传输，这样就可以停止传输一个无用的、（由另一个结点的帧干扰）损坏的帧

![image-20220606223001756.png](http://xherlock.top/usr/uploads/2022/06/1154274331.png)

**算法**

发生n次冲突后，NIC从{$0,1,2,3…, 2^{n-1}$}中随机选择一个值赋给K，并等待K·512 bit times，即K倍发送512bit数据所消耗的时间，n最大取10

效率接近1

### 轮流协议

**轮询协议**（polling protocol）

主结点以循环的方式轮询每个结点，告诉每个结点最多传输帧的数量

**令牌传递协议**（token-passing protocol）

分散的，效率很高，但是可能会出现一个结点故障或忘记释放令牌导致整个信道崩溃

### 小结

![image-20220606225714313.png](http://xherlock.top/usr/uploads/2022/06/2416437842.png)

链路层（一）

发表评论取消回复

Reverse（十一）

Win11新机鼓捣记录

栈~数制转换

C++学习

Python实现文件管理系统（重命名和删除）

汇编语言学习（六）基本指令系统2

pytorch tensor处理

C++数据结构2

序列密码

修改搜索引擎已访问的超链接颜色

链路层（一）

发表评论 取消回复

链路层（一）

发表评论取消回复