前言

参考王道书。
后续会进一步整理，包括添加笔记内容，标明参考资料。

更新中。。。

跳过目录

一、传输数据使用的两种链路

点对点链路

两个相邻节点通过一个链路相连，没有第三者。

应用：PPP协议，常用于广域网。

广播式链路

所有主机共享通信介质。

应用：早期的总线以太网、无线局域网，常用于局域网。

典型拓扑结构：总线型、星型（逻辑总线型）

二、介质访问控制

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

用来决定广播信道中信道分配的协议属于数据链路层的一个子层，称为介质访问控制（Medium Access Control，MAC）子层。

介质访问控制方法分类

静态划分信道

• 信道划分介质访问控制

动态分配信道

动态媒体接入控制/多点接入

特点：信道并非在用户通信时固定分配给用户。

• 随机访问介质访问控制
• 轮询访问介质访问控制

三、信道划分介质访问控制

信道划分介质访问控制

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

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

多路复用

把多个信号组合在一条物理信道上进行传输，使得多个计算机或终端设备共享信道资源，提高信道利用率。


把一条广播信道，逻辑上分成几条用于两个节点之间通信的互不干扰的子信道，实际就是把广播信道转变为点对点信道

信道划分介质访问控制分为以下四种：

• 频分多路复用（FDM）
• 时分多路复用（TDM）
• 波分多路复用（WDM）
• 码分多路复用（CDM）

频分多路复用（FDM）

将多路基带信号调制到不同频率载波上，再叠加形成一个复合信号的多路复用技术。

在物理信道的可用带宽超过单个原始信号所需带宽的情况下，可将该物理信道的总带宽分割成若干与传输单个信号带宽相同（或略宽）的子信道，每个子信道传输一种信号。

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

理解：并行

优点：

• 充分利用传输介质带宽，系统效率较高
• 技术比较成熟，因此实现比较容易。

时分多路复用（TDM）

时分多路复用是将一条物理信道按时间分成若干时间片，轮流地分配给多个信号使用。

每个时间片由复用的一个信号占用。这样，利用每个信号在时间上的交叉，就可以在一条物理信道上传输多个信号。

TDM帧是在物理层传送的比特流所划分的帧，标志一个周期。

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

理解：并发

统计时分复用STDM（改进的时分复用）

每一个STDM帧中的时隙数小于连接在集中器上的用户数。

各用户有了数据就随时发往集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的输入数据放入STDM帧中，一个STDM帧满了就发出。

STDM帧不是固定分配时隙，而是按需动态分配时隙。

波分多路复用（WDM）

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

码分多路复用（CDM）

码分多路复用是采用不同的编码来区分各路原始信号的一种复用方式，它既共享信道的频率，又共享时间。

理解：

假设A站要向C站运输黄豆，B站要向C站运输绿豆，A与C、B与C之间有一条公共的道路（广播信道）。

频分复用：

• 公共道路被划分为两个车道，分别提供给A到C的车和B到C的车行走,两类车可以同时行走，但只分到了公共车道的一半，因此频分复用（波分复用也一样）共享时间而不共享空间。

时分复用：

• 先让A到C的车走一趟,再让B到C的车走一趟，两类车交替地占用公共车道。公共车道没有划分，因此两车共享了空间，但不共享时间。

码分复用：

• 与另外两种信道划分方式大为不同：黄豆与绿豆放在同一辆车上运送，到达C后，由C站负责把车上的黄豆和绿豆分开。因此，黄豆和绿豆的运送,既共享了空间也共享了时间。

码分多址（CDMA）

码分多址（CDMA）是码分复用的一种方式。

其原理是每比特时间被分成 m 个更短的时间槽，称为码片（Chip，通常情况下每比特有64或128个码片）。每个站点被指定一个唯一的 m 位代码或码片序列。

发送1时，站点发送码片序列；发送0时，站点发送码片序列的反码。当两个或多个站点同时发送时，各路数据在信道中线性相加。为从信道中分离出各路信号，要求各个站点的码片序列相互正交。

简单理解就是，A站向C站发出的信号用一个向量来表示，B站向C站发出的信号用另一个向量来表示，两个向量要求相互正交。向量中的分量，就是所谓的码片。

• 如何不打架：多个站点同时发送数据的时候，要求各个站点芯片序列相互正交。

• 如何合并：各路数据在信道中被线性相加。

• 如何分离：合并的数据和源站规格化内积。

如站点A的码片序列被指定为 0001011，则A站发送 00011011 就表示发送比特 1 ，发送 1100100 就表示发送比特 0 。按惯例将码片序列中的 0 写为 -1，将 1 写为 +1，A站的码片序列就是 -1, -1, -1, +1, +1, -1, +1, +1。

令向量 S 表示A站的码片向量，T 表示B站的码片向量。两个不同站的码片序列正交，即向量 S 和 T 的规格化内积为 0：
S ⋅ T ≡ 1 m ∑ i = 1 m S i ⋅ T i = 0 S·T \equiv \dfrac{1}{m}\sum ^{m}_{i=1}S_{i}·T_{i} = 0 S⋅T≡m1​i=1∑m​Si​⋅Ti​=0

• 任何一个码片向量和该码片向量自身的规格化内积都是 1：
  S ⋅ S ≡ 1 m ∑ i = 1 m S i ⋅ S i = 1 m ∑ i = 1 m ( ± 1 ) 2 = 1 m ⋅ m = 1 S·S \equiv \dfrac{1}{m}\sum ^{m}_{i=1}S_{i}\cdot S_{i} = \dfrac{1}{m}\sum ^{m}_{i=1}(\pm1)^{2} = \dfrac{1}{m} · m = 1 S⋅S≡m1​i=1∑m​Si​⋅Si​=m1​i=1∑m​(±1)2=m1​⋅m=1
• 任何一个码片向量和该码片反码的向量的规格化内积是 -1：
  S ⋅ S 反 码 ≡ 1 m ∑ i = 1 m S i ⋅ S 反 码 i = 1 m ∑ i = 1 m ( − 1 ) = − 1 m ⋅ m = − 1 S·S_{反码} \equiv \dfrac{1}{m}\sum ^{m}_{i=1}S_{i} · S_{反码i}=\dfrac{1}{m}\sum ^{m}_{i=1}(-1)=- \dfrac{1}{m}·m = -1 S⋅S反码​≡m1​i=1∑m​Si​⋅S反码i​=m1​i=1∑m​(−1)=−m1​⋅m=−1

令向量T为 (-1, -1, +1, -1, +1, +1, +1, -1)。

• 当A站向C站发送数据1时，就发送了向量 (-1, -1, -1, +1, +1, -1, +1, +1)。
• 当B站向C站发送数据0时，就发送了向量 (+1, +1, -1, +1, -1, -1, -1, +1)。

两个向量到了公共信道上就进行叠加，实际上就是线性相加：
S − T = ( 0 , 0 , − 2 , 2 , 0 , − 2 , 0 , 2 ) S-T = (0, 0, -2, 2, 0, -2, 0, 2) S−T=(0,0,−2,2,0,−2,0,2)
到达C站后，进行数据分离。如果要得到来自A站的数据，就让 S 与 S-T 进行规格化内积：
S ⋅ ( S − T ) = 1 S · (S - T) = 1 S⋅(S−T)=1
所以A站发出的数据是1。

同理，如果要得到来自B站的数据，则让 T 与 S-T 进行规格化内积：
T ⋅ ( S − T ) = − 1 T · (S - T) = -1 T⋅(S−T)=−1
因此从B站发送过来的信号向量是一个反码向量，代表0。

码分多路复用技术具有频谱利用率高、抗干扰能力强、保密性强、语音质量好等优点，还可以减少投资和降低运行成本，主要用于无线通信系统，特别是移动通信系统。

记忆：CDMA与CSMA，CD还是CS？

• CD：Code Division
• CS：Carrier Sense

如果想要进一步了解CDMA，可以看看大佬写的博客：码分多址(CDMA)的本质-正交之美

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

所有用户可随机发送信息。发送信息时占全部带宽。

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

存在不协调 → 冲突问题 → 使用协议解决

• ALOHA协议
• CSMA协议
• CSMA/CD协议
• CSMA/CA协议

ALOHA协议

理解：想说就说

ALOHA协议分为两种：

• 纯ALOHA协议
• 时隙ALOHA协议

纯ALOHA协议

思想：不监听信道，不按时间槽发送，随机重发。

特点：想发就发

• T₀：一个数据帧的发送时间（假设每一个站点发送的每一个数据帧，T₀都是相通的）

如何检测冲突

如果发生冲突，接收方在就会检测出差错，然后不予确认，发送方在一定时间内收不到就判断发生冲突。

如何解决冲突

超时后等一随机时间再重传。

时隙ALOHA协议

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

特点：控制想发就发的随意性

ALOHA协议总结

ALOHA协议特点：不听就说

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

CSMA协议

理解：先听再说

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

• CS：载波侦听/监听（carrier sense），每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据

  当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。当一个站检测到的信号电压摆动值超过一定门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞，即发生了冲突。

• MA：多点接入（multiple access），表示许多计算机以多点接入的方式连接在一根总线上。

协议思想：发送帧之前，监听信道。

监听结果

• 信道空闲：发送完整帧
• 信道忙：推迟发送

规定：

• 1-坚持CSMA
• 非坚持CSMA
• p-坚持CSMA

1-坚持CSMA

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

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

• 空闲则直接传输，不必等待。
• 忙则一直监听，直到空闲马上传输
• 如果有冲突（一段时间内未收到肯定回复），则等待一个随机长的时间再监听，重复上述过程。

优点：

• 只要媒体空闲，站点就马上发送，避免了媒体利用率的损失。

缺点：

• 假如有两个或两个以上的站点有数据要发送，冲突就不可避免。

非坚持CSMA

非坚持指的是对于监听信道忙之后就不继续监听。

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

• 空闲则直接传输，不必等待。
• 忙则等待一个随机的时间之后再进行监听。

优点：

• 采用随机的重发延迟时间可以减少冲突发生的可能性。

缺点：

• 可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低。

p-坚持CSMA

p-坚持指的是对于监听信道空闲的处理。

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

• 空闲则以p概率直接传输，不必等待；概率1-p等待到下一时间槽再传输
• 忙则等待一个随机的时间之后再进行监听。

优点：

• 既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间的这种方案。

缺点：

• 发生冲突后还是要坚持把数据帧发送完,造成了浪费。

有没有什么办法可以减少资源浪费,一冲突就能发现呢?

三种CSMA对比

信道状况	1-坚持CSMA	非坚持CSMA	p-坚持CSMA
信道空闲	马上发	马上发	p 概率马上发，1-p 概率等到下一个时隙再发送
信道忙	继续坚持监听	放弃监听，等一个随机时间再监听	放弃监听，等一个随机时间再监听

CSMA/CD协议

理解：先听再说，边听边说

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

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

问题：先听后发为什么还会冲突？

答：因为电磁波在总线上总是以有限的速率传播的。

传播时延对载波监听的影响

1. 假设有两台通信的主机A、B：
   τ：单程端到端传播时延
   
2. A开始给B发送数据，此时（时间 t ＜τ）B检测到信道是空闲的
   
3. 因此B会开始给A发送数据，造成冲突，碰撞
   
   
   
   

如何确定碰撞后的重传时机？

截断二进制指数规避算法

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

例：

• 第一次重传，k = 1，r 从 { 0, 1} 选，重传推迟时间为 0 或 2τ，在这两个时间中随机选一个；
• 若再次碰撞，则在第二次重传时，k = 2，r 从 { 0, 1, 2, 3 } 选，重传推迟时间为 0、2τ、4τ、6τ，在这四个时间中随机选一个
• 若再次碰撞，则在第三次重传时，k = 3，r 从 { 0, 1, 2, 3, 4, 5, 6, 7 } 选……

若连续多次发生冲突，就表明可能有较多的站参与争用信道。使用此算法可使重传需要推迟的平均时间随重传次数的增大而增大，因而减小发生碰撞的概率，有利于整个系统的稳定。

例：
在以太网的二进制回退算法中,在11次碰撞之后，站点会在0 ~ ____ 之间选择一个随机数。

答案：1023

解析：

k = min(11, 10) = 10，2¹⁰-1 =1023

最小帧长问题

问题：若发送一个很短的帧时发生了碰撞，在检测到发生碰撞前帧已经发送完毕了，无法停止发送。
解决：设置最小帧长

帧的传输时延至少要两倍于信号在总线中的传播时延。

帧长(bit)/数据传输速率 ≥ 2τ

公式

最小帧长 = 2 × 总线传播时延 × 数据传输速率 = 2τ × 数据传输速率

以太网规定最短帧长为64B，凡是长度小于64B的都是由于冲突而异常终止的无效帧。

通常取51.2微秒为争用期时间，对于10Mb/s以太网，期间可以发送512bit数据，即64字节。

CSMA/CA协议

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

为什么要有CSMA/CA?

无线局域网：

• 无法做到360°全面检测碰撞
• 隐蔽站：当A和C都检测不到信号，认为信道空闲时，同时向终端B发送数据帧，就会导致冲突。

CSMA/CA协议工作原理

发送数据前，先检测信道是否空闲。

空闲则发出RTS（request to send）， RTS包括发射端的地址、接收端的地址、下一份数据将持续发的时间等信息；信道忙则等待。

接收端收到RTS后，将响应CTS（clear to send）

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

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

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

1. 预约信道
2. ACK帧
3. RTS/CTS帧（可选）：用于解决隐蔽站

CSMA/CD与CSMA/CA的比较

相同点：

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

不同点：

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

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

比较三种介质访问控制

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

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

随机访问MAC协议：

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

轮询访问MAC协议/流协议/轮转访问MAC协议:

• 既要不产生冲突，又要发送时占全部带宽。

在轮询访问中，用户不能随机地发送信息，而要通过一个集中控制的监控站，以循环方式轮询每个结点，再决定信道的分配。当某结点使用信道时，其他结点都不能使用信道。

轮询访问介质控制有两种协议：

• 轮询协议
• 令牌传递协议

轮询协议

主结点轮流“邀请”从属结点发送数据。

问题：

1. 轮询开销
2. 等待延迟
3. 单点故障

令牌传递协议

令牌：一个特殊格式的MAC控制帧，不含任何信息。控制信道的使用，确保同一时刻只有一个结点独占信道。

• 令牌环网无碰撞
• 每个结点都可以在一定的时间内(令牌持有时间)获得发送数·据的权利,并不是无限制地持有令牌。

问题：

1. 令牌开销
2. 等待延迟

应用于令牌环网(物理星型拓扑,逻辑环形拓扑)。

采用令牌传送方式的网络常用于负载较重、通信量较大的网络中。