§3.1 数据链路层功能概述
1.节点：
计算机网络中的中的主机路由器等都可以叫节点。
2.链路：
网络中两个节点之间的物理通道，链路的传输介质主要有双绞线光纤和微波。分为有线链路、无线链路。
3.数据链路：
网络中两个节点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成了数据链路。
4.帧：
链路层的协议数据单元，封装网络层数据报。
5.链路与数据链路之间的区别：
链路是物理通道、而数据链路是逻辑通道。数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。
6.数据链路层的功能：
数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
网络层是大老板、数据链路层是秘书、物理层是跑腿的。现在老板A要送文件给老板B，老板A就让秘书发文件，秘书把文件分成五段并标号，然后让跑腿的送文件，老板B的秘书一看文件不对，怎么只有三段，就得改正文件，保证让老板B拿到的是正确文件。
-
为网络层提供服务：
- 无确认无连接服务：适用于误码率低的通信。接收端收到信息不用发出响应。若物理层并没有成功传送数据，数据链路层也一声不吭悄悄地。
- 有确认无连接服务：收发双发无需建立连接，但数据成功发送到的话、接收端要发送响应。
- 有确认面向连接服务：收发双方建立连接。有连接必然有确认，所以不存在无确认有连接服务。
-
链路管理，即连接的建立、维持、释放（用于面向连接的服务）。
-
组帧：详见下一节讲解。
-
流量控制：接收端收不过来的话，就得让发送方慢点儿。这就叫流量控制。
-
差错控制：帧错 / 位错
§3.2 组装成帧和透明传输
一、封装成帧
1.概念：
封装成帧就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。首部和尾部包含许多的控制信息，他们的一个重要作用：帧定界（确定帧的界限)。
2.帧同步：
接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。
3.帧长：
如图所示
4.MTU：
即最大传输单元，帧的数据部分要不大于MTU。
5.组帧的四种方法：
- ① 字符计数法
- ② 字符（节）填充法
- ③ 零比特填充法
- ④ 违规编码法
二、透明传输
透明传输是指不管所传数据是什么样的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨碍数据传输的东西。
当所传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的。
三、组帧的四种方式
1.字符计数法：
帧首部用一个计数字段（第一个字节，八位）来表明帧内的元素。
缺点：如果第一个字符发生失真编成了4，那后面就全乱了。所以这种方法其实也不常用。
2.字符填充法
当传送的帧是由文本文件组成时（文本文件的字符都是从键盘上输入的，都是ASClI码）。不管从键盘上输入什么字符都可以放在帧里传过去，即透明传输。
当传送的帧是由非ASClI码的文本文件组成时（二进制代码的程序或图像等就要采用字符填充方法实现透明传输。
字符填充具体实现方法是这样的，有三种字节，开始字节、结束字节、转义字节。如果刚好传送的正常数据和开始字节结束字节或者转义字节一样，那就在他前面插入一个转义字节。如图：
3.零比特传输法
标志字段01111110同时代表开始结束，并且严格遵守5110，即没出现五个连续的1，就在后面插入一个0，就算传输的数据中有01111110，那他也会变成011111010，不会与标志字段发生混淆。实现了透明传输。
4.违规编码法
用违法的编码方式来表示起始结束，例如曼彻斯特编码中，只能有 低-高、高-低 两种编码方式，那就用高-高和低-低表示起始结束。
5.总结：
由于字节计数法中Count字段的脆弱性（其值若有差错将导致灾难性后果）及字符填充实现上的复杂性和不兼容性，目前较普遍使用的帧同步法是零比特填充和违规编码法。
§3.3.1 差错控制（检错编码）
一、差错从何而来？
主要还是由噪声而来。而差错的分类可以根据成因分两种、根据形式也分两种。
1.根据成因分：
-
① 全局性：
- 由于线路本身电气特性所产生的随机噪声(热噪声)，是信道固有的，随机存在的。
- 解决办法:提高信噪比来减少或避免干扰。(对传感器下手）
- 信道电流流过发生的呲呲声导致。
-
② 局部性：
- 由于外界特定的短暂原因所造成的冲击噪声，产生差错，这是主要原因。
- 解决办法:通常利用编码技术来解决。
- 熊孩子拿木头棍子敲网线
2.按形式分：
-
位错：1变0 0变1这种
-
帧错：例如 [#1] - [#2] - [#3] 发生帧错
- 丢失：收到 [#1] - [#3]
- 重复：收到 [#1] - [#2] - [#2] - [#3]
- 失序：收到 [#1] - [#3] - [#2]
二、数据链路层的差错控制
1.位错差错控制的方式：
假设主机A和主机B进行通信，信道上有20个路由器等链路层设备。在数据在第五个路由器上发生了位错，第五个路由器就不会发位错的数据，然后往回发，五四三二一往回发到主机A上告诉主机A数据错了让它重新发。
这比直接一股脑不管对错发到主机B上，然后发现错误又重新王芳一轮回要节省不少资源呢。
2.位错差错控制的编码方式：
-
纠错编码：
- 海明码
-
检错编码：
- 奇偶效验码
- 循环冗余码
3.物理层的编码和数据链路层的编码的不同点
数据链路层编码和物理层的数据编码与调制不同。物理层编码针对的是单个比特，解决传输过程中比特的同步等问题，如曼彻斯特编码。而数据链路层的编码针对的是一组比特，它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。
3.冗余编码：
在数据发送之前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时，相应的冗余位也随之变化，使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则，从而判断是否出错。
我上淘宝买了五十颗糖，商家会把它打包起来，然后在上面写：“共计五十颗，没颗重2g，连带包装共计150g。”，这个就是冗余码。然后一路上会有一些相当于是路由器的官员，比如糖运到曹县了，曹县的负责官员就要称一下包裹，要是发现重量不对，与冗余码不符合，哦吼，原来是有一颗糖坏了。就让送货的把坏掉的扔了，没坏的继续送，并且再派一众人马去出发地商家，让商家的工作人员重新送一颗没坏的糖过来。不用说是我收到了糖，发现有一颗坏的，这时才给商家反馈。浪费时间浪费资源。
三、检错编码 — 奇偶效验码
1.概念：
奇偶校验码分为一位校验码和 n - 1 位信息元。其编码方式分为奇校验偶校验。奇校验是在数据前面加一位0或1，使1的个数为奇数。偶校验码就是加一位1的数量变偶数
对于奇（偶）校验只能检测出奇数个位==（1位错误、3位错误）==的比特错误，因而检错能力只有 50 %
2.例题：
如果一个字符S的ASCI编码从低到高依次为1100101，采用奇校验，在下述收到的传输后字符中，哪种错误不能检测?
A.11000011 B.11001010
C. 11001100 D.11010011
答案：D
解析：
显而易见的，S的正确奇校验码应该是11100101，四个答案都是错误的编码，但是错误的编码也有可能不会被找到对吧。ABC三项，1的个数均为4，是偶数，而奇校验需满足1的个数为奇数，那么ABC的错误必然能被检测出来。但是D中的1的个数是5个，是奇数，所以即便他是错的，数据链路层也看不来。就像是要买的五个十个糖，少了一颗糖，但放了一颗一样重的石头，冗余码也没用，只能默默认栽。
四、检错编码 — CRC循环冗余码
1.编码思想：
比如发送端要发送的发送数据是5，生成多项式是2，然后5 % 2 = 1，那么1就是冗余码 / FCS帧检测序列。5 + 1 是6，所以发送端不发5发6，接收端一看：哦吼，666，发的是6，这玩意儿是2的倍数，那就没得错了。
这个玩意儿有点麻烦，就不说他具体是怎么操作的了，直接上例题反而更好理解。
2.例题：
假如我们要发的数据是1101011011，采用CRC校验，生成多项式为10011。
10011表达成多项式应该是 x 4 + x + 1，阶数为4，那么我们就先用原始数据1101011011乘以2 4 也就是10000，得到的11010110110000，然后用这个11010110110000除以10011得到余数是1110，也就是说FCS就是1110，然后用11010110110000加上1110得到11010110111110即是要发送的数据。具体二进制除法要用到异或运算，如图（没必要怎么掌握，估计到时候数电要学二进制除法器）
然后对于接收端而言，他应该如何将11010110111110进行检错呢？很简单，判断11010110111110是不是生成多项式10011的倍数。
另外FCS的生成以及接收端CRC检验都是由硬件实现，处理很迅速，因此不会延误数据的传输。
为啥硬件就快，想想晚上睡觉前要关灯，你现在就在开关面前，直接按开关快还是掏出手机用智能开关装逼快。
3.总结：
在数据链路层仅仅使用循环冗余检验CRC差错检测技术，只能做到对帧的无差错接收，即“凡是接收端数据链路层接受的帧，我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。接收端丢弃的帧虽然曾收到了，但是最终还是因为有差错被丢弃。“凡是接收端数据链路层接收的帧均无差错”。
这种传输方式仍然不能称作“可靠传输”，可靠传输是发送端数据链路层发什么，接收端数据链路层就收到什么。CRC检验虽然能实现无比特差错的传输，但这还不是可靠传输。
§3.3.2 差错控制（纠错编码）
1.海明码的特点：可以发现双比特错，纠正单比特错。
2.海明码的特点：动一发而牵全身。
3.海明码的工作原理：
确定校验码位数r
确定校验码和数据的位置
求出校验码的值
检错并纠错
一、确定校验码位数r
1.海明不等式：
2 r ≥ k + r + 1
r为冗余信息位，k为信息位。
2.海明不等式的应用
设要发送的数据为 D = 101101 ，数据的位数 k = 6 ，满足不等式的最小 r 为4，也就是说 D = 101101 的海明码应该有 6 + 4 = 10 位，其中原数据 6 位，校验码 4 位。
二、确定校验码和数据的位置
对于原始数据 D = 101101 ，已知应有四位校验码，设它们分别为P1 , P2 , P3 , P4；数据从左到右为D1 , D2 , D3 , D4 , D5 , D6
校验码Pn只能放在第 2 n，n ∈ N 位 上，将校验码填好后，再按顺序把原数据填好，填满这十位。
| 数据位 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 代码 | P1 | P2 | D1 | P3 | D2 | D3 | D4 | P4 | D5 | D6 |
| 实际值 | ? | ? | 1 | ? | 0 | 1 | 1 | ? | 0 | 1 |
三、求出校验码的值
首先，我们上一步已经得到了数据 D = 101101中相关数据的位置，如下表所示。
| 数据位 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 二进制 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
| 代码 | P1 | P2 | D1 | P3 | D2 | D3 | D4 | P4 | D5 | D6 |
| 实际值 | ? | ? | 1 | ? | 0 | 1 | 1 | ? | 0 | 1 |
如何计算P1：P1所在位数的二进制位是0001，从右往左第一位为1，而除P1 外，D1 , D2 , D4 , D5的所在位数的二进制位从右往左的第二位也为1，那就另P1 ⊕ D1 ⊕ D2 ⊕ D4 ⊕ D5 = 0，即可算出 P1 的值为0 。
如何计算P2：P2所在位的数的二进制位是0010，从左往右第二位是1，那就找他后面从左往右第二位也是1的，即D1 , D3 , D4 , D6，同样的令P2 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6 = 0，即可得到P2 = 0 。
同样的方法可得：P3 ⊕ D2 ⊕ D3 ⊕ D4 = 0 => P3 = 0，P4 ⊕ D5 ⊕ D6 = 0 => P4 = 1 。
那么101101的海明码就为0010011101
上面那个表就可以写完整了：
| 数据位 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 二进制 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
| 代码 | P1 | P2 | D1 | P3 | D2 | D3 | D4 | P4 | D5 | D6 |
| 实际值 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
（想出这个的科学家真的是太牛太厉害了）
上网查了一下，人家就是因为发明这个拿到了图灵奖。要多向牛人学习。没准将来我也能那个图领奖呢。狗屁个，拿个蓝桥杯三等奖都够呛了 ,这是本人黑历史
（Richard W. Hamming，美国数学家，图灵奖得主，“汉明码”的发明人。）
四、检错并纠错
我们从上面几步得知原始数据 D = 101101 对应的十位海明码是0010011101，假如第五位发生错误，导致接收端收到的信息是0010111101，我们来探讨一下接收端到底是怎样检错纠错的。
| 数据位 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 二进制 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
| 代码 | P1 | P2 | D1 | P3 | D2 | D3 | D4 | P4 | D5 | D6 |
| 正确值 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 错误值 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
首先我们根据海明公式可以判断出来第1 , 2 , 4 , 8 四位是校验码。然后我们开始计算。
P1 ⊕ D1 ⊕ D2 ⊕ D4 ⊕ D5 = 1 ······ ①
P2 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6 = 0 ······ ②
P3 ⊕ D2 ⊕ D3 ⊕ D4 = 1·············· ③
P4 ⊕ D5 ⊕ D6 = 0 ····················· ④
我们把四个式子中格式为Dn的二进制位的集合分别设为A1 ， A2 ， A3 ， A4四个集合。发生错误的二进制位设为X
由 ② ④ 得知：对于 ∀ 二进制位位N ∈ A2 ∪ A4， N没有发生错误。
由 ① ③ 得知：发生错误的二进制位 X ∈ A1 ∩ A3 ，A1 ∩ A2 = { D2 , D4 }，而D4 ∈ A2 ∪ A4，D4 不可能发生错误，所以发生错误的就是D2，也就是第五位二进制位。
那么纠错后的海明码就应该是0010011101
五、本节思维导图
§3.4.1 流量控制与可靠传输机制
零、前言
这一节主要是大体的、笼统的介绍流量控制可靠传输相关的协议，不会展开的说，所以你会看到笔者究竟能有多敷衍。
不过后面几节会将这几个协议逐个细细地讲一下。
一、数据链路层的流量控制
1.概念：
较高的发送速度和较低的接收速度的不匹配，会造成传输出错，流量控制就是控制发送方发送速度的过程。是数据链路层的一项重要工作。
2.链路层流量控制和传输层流量控制的区别：
数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。
链路层流量控制手段：接收方接收不下就不回复确认。
传输层流量控制的手段：接收端给发送端一个窗口公告。
比如说是有人在笼子里养了一条狗娃子，给碗里盛了点狗粮，喂给狗娃子，狗娃子吃完了把空碗推开，这个空就是确认帧。如果狗娃子饱了，不吃了，就不会有空碗，也就是不会发送确认帧。
二、流量控制的方法
1.停止 — 等待协议：
每发送完一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。
因为存在等待的过程，所以这个协议是比较低效的。一般不使用。
（停止等待协议是一种特殊的滑动窗口协议）
2.滑动窗口协议：
如图，上面是发送端，下面是接收端，发送端发送窗口有N帧长，接收端接收窗口有M帧长，接收端每接收一帧，接收窗口就往前一位，然后向发送端发送确认信息，接收端收到后，接收窗口也会往前一位。
而停止 — 等待协议收一个确认一个就相当于是两个滑动窗口都只有一帧的滑动窗口协议。
3.三种协议的区别：
- 停止 — 等待协议：发送窗口为1，接收窗口为1。
- 后退N帧协议（GBN）：发送窗口>1，接收窗口为1 。
- 选择重传协议（SR）：发送窗口＞1，接收窗口＞1 。
三、可靠传输、滑动窗口、流量控制
1.回顾可靠传输和流量控制的概念：
可靠传输：发送端发啥，接收端收啥。
流量控制：控制发送速率，使接收方有足够的缓冲空间来接收每一个帧。
2.滑动窗口解决的问题：
- 流量控制：假如发送端发太快，接收端收不下就不确认，发送端想发也发不了。
- 可靠传输：发送短长时间没有收到确认，就会重新发送一遍原数据。（男朋友打游戏时，女朋友发微信：“在？”，五秒后未回，又发“在？”，又来又来，知道男朋友打完游戏回消息发送确认为止。）
四、本节思维导图
§3.4.2 停止 --- 等待协议
一、停止 — 等待协议的归属：数据链路层 or 传输层？
过去技术不成熟，传输数据可能出现这样那样的问题，因而步骤繁琐，传输层和数据链路层都要进行流量控制。而现在通信技术成熟了，出错的可能性没有那么大了，只需要传输层保留流量控制这个功能就行了。数据链路层只需要进行差错控制。所以有的书会把停止 — 等待协议只放到传输层里。
二、停止等待协议的内核
1.为什么要有停止 — 等待协议？
除了比特出差错，底层信道还会出现 丢包 ① 问题。为了实现流量控制。
注：① 丢包:物理线路故障、设备故障、病毒攻击、路由信息错误等原因，会导致数据包的丢失。不是某个位丢失，而是丢失了一个数据包，一个帧。
2.研究停止等待协议的前提？
虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据（发送方)，一方接收数据(接收方)。
因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的。
“停止-等待”就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。
3.停止等待协议的应用情况：
- ① 有差错情况
- ② 无差错情况
三、停止等待协议的无差错情况
如图，发送方的0帧成功发给了接收方。↓↓↓
然后接收方发送了一个确认帧ACK0（ACK是acknowledge的意思）↓↓↓
然后发送方接受收到了确认帧ACK0，就会继续发送1帧。↓↓↓
然后1帧顺利的到达了接收方，接收方就又会给发送方发送确认帧ACK1，如此往返数次。最后数据就能传送完毕了。↓↓↓
四、停止等待协议的有差错情况
1.发生了丢包：
如图，出现了错误 — 丢包！（噔噔咚~）↓↓↓
那接收端没有接收导数据，所以发送端接一直收不到确认帧，怎么办呢？其实啊发送端在发送某个帧的时候，会启动一个超时计时器。然后只要在一定时间内接收到接收端发来的确认帧，那这个超时计时器就归零了，free()了，然后发送端发送下一个帧，启动下一个超时计时器。但是如果计时器都超时了，确认帧还是没有传过来，那么发送端就会再把这个帧发送一遍。
超时计时器的时间设置应当比帧传输的平均RTT更长一些。（RTT，第一章的东西，反正我写到这里的时候就感觉自己把物理层的东西都忘到沟子上咧。RTT，往返时延，就是一个数据正常情况下从发送方到接收方，再将确认信息从接收方发送到发送方的过程中产生的时延。）
几点注意：
- 发送完一个帧后，一定要保存它的副本，不然东西发出去了，半路没了，丢包了，人家接收端蛮横地要你重发，你副本都没有，本体又丢了，你说你发啥呀。 不过等人家确认信息都传过来了，那这个副本就没得用了，该扔就扔了。
- 数据帧和确认帧都必须要编号。
- 对于帧出错的问题如何解决我们这里没有讲，因为帧出错和丢帧差不多实际上，接收方发现帧错了，就会手动丢掉帧，然后耍脾气不给人家发送方确认帧。
2.确认帧ACK丢失：
如图所示↓↓↓
这种情况下超时计时器的时间到了，确认帧还是没有传来，发送方就会重新发送数据，而接收方已经接收过这个帧，所以就把之前接收的丢弃，重新接收。
3.ACK迟到
确认帧迟迟不来，发送方超时重传，接收方收到重传帧后再次传确认帧。然后过一会儿都已经传到第二三个帧了，发送方收到了第一个帧的确认帧，就会将它丢弃掉。
五、停止等待协议的性能分析
优点：操作简单
缺点：信道利用率太低
如图，TD为发送帧发送时延，RTT为往返时延，TA为确认帧发送时延。
信 道 利 用 率 U = T D T D + R T T + T A 信道利用率U=\frac{T_D}{T_D+RTT+T_A} 信道利用率U=TD+RTT+TATD
信道利用率，第一章的东西，忘了吧忘了吧哈哈哈，其实我也忘了。
信道利用率指：发送方在一个发送周期内,有效地发送数据所需要的时间占整个发送周期的比率。
信 道 利 用 率 = L C T 信道利用率=\frac{\frac{L}{C}}{T} 信道利用率=TCL
T是发送周期，L是发送周期T内发送的比特数据，C是发送方数据传输率。
还有一个类似的概念，信道吞吐率
信 道 吞 吐 率 = 信 道 利 用 率 × 发 送 方 发 送 速 率 信道吞吐率=信道利用率\times发送方发送速率 信道吞吐率=信道利用率×发送方发送速率
放了这么多概念，我脑子都然成糊糊了，放例题先：
例题:一个信道的数据传输率为4kb/s，单向传播时延为30ms，如果使停止-等待协议的信道最大利用率达到80%，要求的数据帧长度至少为( )。
来，咱们分析一波，题上没有给确认帧的发送时延是多少，那就是忽略不计了，单向传播要30ms，那双向传播就是60ms，也就是说 R T T = 2 × 30 m s = 60 m s RTT=2\times30ms=60ms RTT=2×30ms=60ms，再加之题上说信道利用率为80%，我们设信道长度为L，那就能列出这样的方程。
U = 80 % = L C T = T D T D + R T T = L 4 L 4 + 60 m s U=80\%=\frac{\frac{L}{C}}{T}=\frac{T_D}{T_D+RTT}=\frac{\frac{L}{4}}{\frac{L}{4}+60ms} U=80%=TCL=TD+RTTTD=4L+60ms4L
解得 L = 960 b i t e L=960bite L=960bite
六、本节思维导图
可以明显的看来停止等待协议的发送方要等待确认帧，所以他长时间都在闲着，利用率不高，所以我们就有下面几节课要介绍的的两个协议来克服这一点。
§3.4.3 后退N帧协议（GBN）
一、停止等待协议的弊端
1.流水线技术：
停止等待协议的弊端是信道利用率低，详见上一节的分析。
想要克服这种弊端，我们可以尝试多个帧同时来发送。同时等待确认帧ACK。这种技术叫做流水线技术（我感觉有点像多进程 ）
2.流水线技术对停止等待协议弊端的改进方式：
- 必须增加序号范围：这一组同时发送的帧里面，哪个是几号要搞清楚，不然接收方给的确认帧也不知道他确认的究竟是哪个。
- 发送方需要缓存多个分组：容易出现帧丢失的情况，所以要多弄几个缓存。停等协议一次一帧，只需要一个帧的缓存，这种方式一次传几帧，就要多大的缓存空间。
二、后退N帧协议的滑动窗口
1.一些概念：
滑动窗口分为发送窗口和接收窗口。
发送窗口：发送方维持一组连续的允许发送的帧的序号。
接收窗口：接收方维持一组连续的允许接收帧的序号。
（GBN协议接收窗口为1，SR协议接收窗口大于1，停止等待协议都为一）
2.具体步骤
我们来模拟一下GBN的发送过程，首先，发送窗口中0号帧和1号帧先后发送出去。橙色代表副本，如果帧丢失，需要进行超时重传，就传橙色的副本。
然后0号帧被接收到了，并且接收方发送了确认帧ACK0，但1号帧还在路上。
接收方发完确认帧后，接收窗口就往后滑一格。
发送方收到确认帧后，发送滑动窗口也会往后滑一格。
然后1号帧到了以后接收窗口又滑一格，发送方收到确认帧又往后滑，就这样子一直滑，知道所有帧都被传完。
3.窗口的各个部分：
三、GBN发送方必须响应的三件事
1.上层的调用：
上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送;如果窗口已满,发送方只需将数据返回给上层，暗示上层窗口已满。上层等一会再发送。(实际实现中，发送方可以缓存这些数据，窗口不满时再发送帧）。
2.收到了一个ACK
GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到n号帧和它之前的全部帧。
3.超时事件：
协议的名字为后退N帧 / 回退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被确认的帧。
比如发送方发0号帧，接收方确认了，且返回了确认帧ACK0。但是发送1号帧的时候丢包了，然后又发2号帧。接收方想要得到的是1号帧，所以二号帧到他手里他直接丢弃了，并不会返回ACK2。然后发送方继续发3 4 5 号帧，接收方全部丢弃。这个时候长时间没有收到确认帧，超时计时器时间到了，就会启动重传机制。从1号帧开始重新传一遍。
四、GBN接收方要做的事
1.返回确认帧：
如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK，并将该帧中的数据部分交付给上层。
2.丢弃错误帧：
如果不满足返回确认帧的条件，那就丢弃掉帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任何失序帧，只需要维护一个信息: expectedseqnum (下一个按序接收的帧序号）。
先收到0，再1，再2，然后是4，5，接收方说：窝里乖乖，什么鬼，因为他所维护的expectedseqnum应该是3号，所以它就把4和5全都扔了，然后给发送方返回ACK2，给发送方催更。
五、GBN过程图解
六、滑动窗口长度
窗口长度可以无限长吗？
想多了，显然不能，若用n个比特对帧进行编号，那么发送窗口的尺寸 W T W_T WT 应满足 1 ≤ W T ≤ 2 n − 1 1≤W_T≤2^n-1 1≤WT≤2n−1 。因为发送尺寸过大，会使得接收方无法区分新帧旧帧。
比如把帧编码成0 1 2 3，算是两个比特，那就应该满足 1 ≤ W T ≤ 3 1≤W_T≤3 1≤WT≤3，我们试试反例，让 W T = 4 W_T=4 WT=4，然后0，1，2，3同时发送，确认帧全部丢失，那就会触发超时计时器，发送方重传0，1，2，3号帧，接收方不知道这是第一轮的崇川还是第二轮。
七、GBN协议重点总结（考研会考）
- 积累确认（偶尔捎带确认）
- 接收方只按序接收帧，不按序丢弃帧。
- 确认序列号最大的、按序到达的帧。
- 发送窗口最大为 2 n − 1 2^n-1 2n−1，接收窗口为1 。
八、GBN协议性能分析
优点：因连续发送提高了信道利用率
缺点：在重传时必须把原来已经正确传送的数据帧重传，使传送效率降低。
选择重传协议（SR）继承了后退 N 帧协议（GBN）的优点，并修补了他的缺点。
九、本节思维导图
§3.4.4 选择重传协议（SR）
一、GBN的弊端
累积确认导致的批量重传，例如0，1帧正常传送并确认，然后3帧丢失，4 5 6正确传输，结果接收方浪费资源，把这几个扔掉了。当超时计时器到时后，超时重传的是3 4 5 6一起重传，但是明明当时4 5 6传的没问题啊。那人家不管，把正确的扔了，必须重传，这就是GBN的弊端。
解决办法：设置单个确认，同时加大接收窗口，设置接收缓存，缓存乱序到达的帧。
二、选择重传协议中的滑动窗口
二、SR发送方必须响应的三件事
1.上层的调用：
从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧;否则就像GBN一样，要么将数据缓存，要么返回给上层之后再传输。
2.收到了一个ACK：
如果收到ACK，加入该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收。如果该帧序号是窗口的下界（最左边第一个窗口对应的序号），则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了并且有序号在窗口内的未发送帧，则发送这些帧。
如图，0 1 已发送确认，且不在窗口内。2 4 发送但未确认，3 发送确认。5在窗口内但未发送。大于五的不在窗口内。那么当发送方收到确认帧后，发送窗口就会滑两位，下界变成 4 号帧。
3.超时事件：
每个镇都有自己的计时器，一个超时事件发生后只重传一个帧。
三、SR接收方要做的事情
1.来者不拒（窗口内的帧）：
SR接收方将确认一个正确接收的帧而不管其是否按序。失序的帧将被缓存，并返回给发送方一个该帧的确认帧【收谁确认谁】，直到所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按序交付给上层，然后向前移动滑动窗口。
如果收到一个窗口外的，小于窗口下界的帧，就返回一个ACK。
四、运行中的SR
五、滑动窗口长度
SR协议窗口可以无限长吗？
不能！如图：接收方无法确认是传来的新帧还是重传的旧帧。
发送窗口最好等于接收窗口，太大了会溢出，太小了没意义。
设 W T m a x W_{T_{max}} WTmax是发送窗口大小， W R m a x W_{R_{max}} WRmax是接收窗口大小，n表示用几个比特来对帧编号，则对滑动窗口长度的限制是 W T m a x = W R m a x = 2 ( n − 1 ) W_{T_{max}}=W_{R_{max}}=2^{(n-1)} WTmax=WRmax=2(n−1)
六、SR协议重点总结
- 对数据帧逐一确认，收一个确认一个。
- 只重传出错的帧。
- 接收方有缓存。
- W T m a x = W R m a x = 2 ( n − 1 ) W_{T_{max}}=W_{R_{max}}=2^{(n-1)} WTmax=WRmax=2(n−1)
七、本节思维导图
§3.5.1 信道划分介质访问控制
一、传输数据使用的两种链路
-
点对点链路
- 概念：两个相邻节点通过一个链路相连，没有第三者。
- 应用：PPP协议，常用于广域网。
-
广播式链路
- 概念：所有主机共享通信介质。
- 应用：早期的总线以太网、无线局域网，常用于局域网。
- 拓扑结构：总线型、星型（逻辑总线型）
二、介质访问控制
1.概念：
介质访问控制的内容就是，采取一定的措施，使得两对节点之间的通信不会发生互相干扰的情况。
说白了就是你在你们村找二狗有点事，就开始大喇叭放广播找二狗，结果二傻子以为是找他嘞，屁颠屁颠跑到广播室。
为了防止这种现象发生，就要有介质访问控制。
2.分类：
-
静态划分信道
-
信道划分介质访问控制
- 频分多路复用 FDM (Frequence)
- 时分多路复用 TDM (Time)
- 波分多路复用 WDM (Wave)
- 码分多路复用 CDM (Code)
-
-
动态划分信道
-
轮询访问介质控制
- 令牌传递协议
-
随机访问介质控制
- ALOHA 协议
- CSMA 协议
- CSMA / CD 协议
- CSMA / CA 协议
-
三、信道划分介质访问控制
1.概念：
信道划分介质访问控制:将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备。
多路复用技术：把多个信号组合在一条物理信道上进行传输，使得多个计算机或终端设备共享信道资源,提高信道利用率。
把一条广播信道，逻辑上分成几条用于两个节点之间通信的互不干扰的子信道，实际就是把广播信道转变为点对点信道。
四、频分多路复用FDM
用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。频分复用的所有用户在同样的时间占用不同的带宽（频率带宽）资源。
也就是说每个主机发出的信号频率不一样。
FDM充分利用传输介质带宽，系统效率较高；由于技术比较成熟，实现也比较容易。
五、时分多路复用TDM
将时间划分为一段段等长的时分复用帧（TDM帧)。每一个时分复用的用户在每一个TDM帧中占用固定序号的时隙，所有用户轮流占用信道。
TDM帧就类似于操作系统中的时间片 （梦回操作系统课）
注意：TDM帧不是链路层的帧，是在物理层传送的比特流所划分的帧，标志一个周期。
频分复用类似于操作系统中的“并行”，时分复用类似于操作系统中的“并发”
六、改进的时分复用 — 统计时分复用STDM
1.为啥要改进？
比如说一个TDM帧里面为四个主机ABCD划分了时间，但ABC都没有任务，空闲状态，而D处于工作。明明ABC不用工作，却占用时间，纯属占着茅坑不拉shi，让D白等，所以要改进。
2.改进的内容：
每一个STDM帧中的时隙数小于连接在集中器上的用户数。各用户有了数据就随时发往集中器的输入缓存，然后集中器按顺序依次扫描输入缓存，把缓存中的输入数据放入STDM帧中，一个STDM帧满了就发出。STDM帧不是固定分配时隙，而是按需动态分配时隙。
假如说四个主机一同工作，信道最高速率是8000b / s （网恋被骗8000）。对TDM而言，主机最高速率是2000b / s，因为是四个主机分享一条信道，信道雨露均沾。而对于STDM一台主机最高就可以达到8000b / s，如果剩下三台不工作，那信道就能后宫主机有四台，四份宠爱在一身了。
七、波分多路复用WDM
波分多路复用就是光的频分多路复用，在一根光纤中传输多种不同波长（频率）的光信号，由于波长（频率)不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来。
八、码分多路复用CDM
1.码分多址（CDMA）：
码分多址（CDMA） 是码分复用的一种方式。
考试可能会为了刁难你，把这个和CDM然。
2.CDM常用技术：
1个比特分为多个码片/芯片(chip），每一个站点被指定一个唯一的m位的芯片序列。
发送1时发送芯片序列，发送0时发送芯片序列反码（通常把0写成-1）
例如A和B都要发送信息，A发送10，B发送01 。令m=8，假设A的芯片序列是+1 -1 -1 +1 +1 +1 +1 -1，那么A发送10就是发送(+1 -1 -1 +1 +1 +1 +1 -1)(-1 +1 +1 -1 -1 -1 -1 +1)。假设B的芯片序列是-1 +1 -1 +1 -1 +1 +1 +1，那么B发送的01就是(+1 -1 +1 -1 +1 -1 -1 -1)(-1 +1 -1 +1 -1 +1 +1 +1)
3.如何保证区分两台主机：
当多个站点同时发送数据的时候，要求各个站点芯片序列相互正交。就能实现正确区分每台主机。
也就是说，设A的芯片序列为 A = ( + 1 , − 1 , − 1 , + 1 , + 1 , + 1 , + 1 , − 1 ) A=\left(\begin{matrix}+1,-1,-1,+1,+1,+1,+1,-1\end{matrix}\right) A=(+1,−1,−1,+1,+1,+1,+1,−1)
设B的芯片序列为 B = ( − 1 , + 1 , − 1 , + 1 , − 1 , + 1 , + 1 , + 1 ) B=\left(\begin{matrix}-1,+1,-1,+1,-1,+1,+1,+1\end{matrix}\right) B=(−1,+1,−1,+1,−1,+1,+1,+1)
∵ A ⋅ B T m = 0 8 = 0 ∵\frac{A\cdot B^T}{m}=\frac{0}{8}=0 ∵mA⋅BT=80=0
即 两 个 芯 片 序 列 相 互 正 交 即两个芯片序列相互正交 即两个芯片序列相互正交
∴ 能 实 现 正 确 区 分 每 台 主 机 ∴能实现正确区分每台主机 ∴能实现正确区分每台主机
3.如何合并：
各路数据在信道中被线性相加。
A 发送(+1 -1 -1 +1 +1 +1 +1 -1)(-1 +1 +1 -1 -1 -1 -1 +1)
B 发送(+1 -1 +1 -1 +1 -1 -1 -1)(-1 +1 -1 +1 -1 +1 +1 +1)
那把他们拧成一股，就发送(+2 -2 0 0 +2 0 0 -2)(-2 +2 0 0 -2 0 0 +2)
4.如何分离：
合并的数据和源站规格化内积。
例如我们收到了一个比特-2 +2 0 0 -2 0 0 +2，让他先于A的芯片序列+1 -1 -1 +1 +1 +1 +1 -1进行规格化内积，
( − 1 , + 1 , − 1 , + 1 , − 1 , + 1 , + 1 , + 1 ) ⋅ ( − 2 , + 2 , 0 , 0 , − 2 , 0 , 0 , + 2 ) T 8 = − 1 \frac{\left(\begin{matrix}-1,+1,-1,+1,-1,+1,+1,+1\end{matrix}\right)\cdot \left(\begin{matrix}-2,+2,0,0,-2,0,0,+2\end{matrix}\right)^T}{8}=-1 8(−1,+1,−1,+1,−1,+1,+1,+1)⋅(−2,+2,0,0,−2,0,0,+2)T=−1
而-1对应的是0，说明主机A发送的比特是0
九、本节思维导图
选择题中常会出现CDMA和CSMA的混淆，要注意CS是动态的分配信道，CD是静态的。
§3.5.2 ALOHA协议
一、ALOHA协议
1.概念：
广义的ALOHA协议包含纯ALOHA协议和时隙ALOHA协议，狭义的ALOHA协议指的是纯ALOHA协议。
2.小故事：
就是有个计算机科学家norm abramson，他去夏威夷岛玩儿，然后发现夏威夷岛各个岛屿通信不方便，就在夏威夷岛边玩便想办法解决这个通信问题，然后就想出法子来了，因为“aloha”在夏威夷语里面是“你好、再见”的意思，所以这个协议就起了名儿叫ALOHA
诺曼·艾布拉姆森（Norman Abramson，1932年4月1日－2020年12月1日），生于美国麻塞诸塞州波士顿，计算机科学家，开发出ALOHAnet无线通讯系统。
希望有那么一天，有个大学生在写博客的时候，会把我的照片这样放在这里
3.纯ALOHA协议：
不监听信道，不按时间槽发送，随机重发。老子想发啥就发啥。
如果两个站点发生冲突，接收方在就会检测出差错,然后不予确认，发送方在一定时间内收不到就判断发生冲突。
然后ALOHA协议也有类似滑动窗口协议的一个叫做确认帧的东西，如果没有冲突，接收方收到正确信息，返回确认帧。否则接收方不返回确认帧，等超时计时器到时间后超时重传。不过和滑动窗口协议不同的是，这个超时计时器的时间是随机的。
二、时隙ALOHA协议
时隙ALOHA协议的思想:把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等到下一个时间片 / 时隙开始时刻再发送。
比起纯ALOHA协议，时隙ALOHA协议控制了纯ALOHA想发就发的随机性。
就像是有个强迫症，出门必须是整点，哪怕现在是9:55，他也非要等到10:00才走。
而如果发生冲突，照样超时重传，但是必须在下一个时隙开始时超时重传。
三、关于ALOHA协议要知道的一些事情
- 纯ALOHA比时隙ALOHA吞吐量更低，效率更低。
- 纯ALOHA想发就发，时隙ALOHA只有在时间片段开始时才能发。
§3.5.3 CSMA协议
一、CSMA协议
CSMA协议，全程载波监听多路访问协议（Carrier Sense Multiple Access）
1.CS（载波侦听/监听Carrier Sense）
概念：每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据。
监听的方式：当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大(互相叠加)。当一个站检测到的信号电压摆动值超过一定门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞，即发生了冲突。
2.MA（多点接入Multiple Access）
概念：表示许多计算机以多点接入的方式连接在一根总线上。
3.CSMA协议思想：
发送帧之前，先监听信道。
若信道空闲，则发送完整的帧；若信道忙，就推迟发送。
而至于推迟多久，是否立即发送完整的帧，有三种不同的协议，分别为：1-坚持CSMA、非坚持CSMA、p-坚持CSMA
二、1-坚持CSMA
1.概念：坚持指的是对于监听信道忙之后的坚持。
2.思想：
- 如果一个主机要发送信息，那么先监听信道。
- 空闲则直接传输，不必等候。
- 忙则一直监听，直至空闲马上传输。
- 如果有冲突（一段时间内未收到肯定回复)，则等待一个随机长的时间再监听，重复上述过程。
3.利弊：
- 优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失。
- 缺点：假如有两个或两个以上的站点有数据要发送，冲突就不可避免。
三、非坚持CSMA
1.概念：非坚持指的是对于监听信道忙之后就不继续监听。
2.思想：
- 如果一个主机要发送信息，那么先监听信道。
- 空闲则直接传输，不必等候。
- 忙则等待一个随机的时间之后再进行监听。
3.利弊：
- 优点：采用随机的重发延迟时间可以减少冲突发生的可能性。
- 缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低。
四、p-坚持CSMA
1.概念：p-坚持指的是对于监听信道空闲的处理。
2.思想：
- 如果一个主机要发送消息，那么它先监听信道。
- 空闲则以p概率直接传输，不必等待；概率1-p等待到下一个时间槽再传输。
- 忙则等待一个随机的时间之后再进行监听。
3.利弊：
- 优点：既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间的这种方案。
- 缺点：发生冲突后还是要坚持把数据帧发送完，造成了浪费。
五、三种协议的对比
| 1-坚持CSMA | 非坚持CSMA | p-坚持CSMA | |
|---|---|---|---|
| 信道空闲 | 马上发 | 马上发 | p概率马上发1-p概率等到下一个时隙再发送 |
| 信道忙 | 继续坚持监听 | 放弃监听，等一个随机时刻再监听 | 放弃监听，等一个随机时刻再监听 |
| 买蜜雪冰城时 | 你爱我，我爱你喝不到就不走滴（一直在这排队） | 你爱我，我爱你到我就买我不急（没人排队就买，有人排队就去一边玩，过会看有没有人） | 你爱我，我爱你排队人多就扔色子（不管队伍空不空闲，摇到偶数就排队买，摇到奇数就一边玩） |
§3.5.4 CSMA/CD协议
一、CSMA/CD协议
1.概念：
全称载波监听多点接入/碰撞检测协议 (carrier sense multiple access with collision detection)
如果说和别人交谈时，ALOHA协议是还没听人家说话就说话，CSMA协议是先听人家说话再说话，那么CSMA-CD就是先听再说，边听边说。
CS:载波侦听/监听，每一个站在发送数据之前以及发送数据时都要检测一下总线上是否有其他计算机在发送数据。
MA:多点接入，表示许多计算机以多点接入的方式连接在一根总线上。总线型网络
CD:碰撞检测（冲突检测)，“边发送边监听”，适配器边发送数据边检测信道上信号电压的变化情况，以便判断自己在发送数据时其他站是否也在发送数据。半双工网络
即便是先听后发，也会发生冲突，因为传播时延对载波监听是有一定影响的。
二、传播时延对载波监听的影响
设现在有AB两台主机发送信息，数据在信道上的单程端到端传播时延为 τ \tau τ，也就是说一串数据从这头到那头需要 τ \tau τ时间。那么假设A已经发送了数据，然后在A发送数据一段时间后B也要发送数据，但是因为A距离发送数据的时间不足 τ \tau τ，所以B发送数据前的监听会产生错误，误以为信道空闲。
就比如说A往B运沙子，B往A运水，而且共用一条管道。A已经运了沙子，但还在路上，B不知道，就把水给运了，然后两个一碰就变成了泥水。
那发生碰撞了会怎样呢？两个信号互相干扰，就好像沙子变成了泥水，水也变成了泥水。然后两方发现自己这边收到了泥水，就知道出现问题了，就不发东西了。
假设A在 t = 0 t=0 t=0时刻发送数据，那么B发送数据必然是在一个小于 τ \tau τ的时刻，设B在 t = τ − δ t=\tau-\delta t=τ−δ时刻发送数据。那么A的数据到达B是在 t = τ t=\tau t=τ时刻，B的数据到达A是在 t = 2 τ − δ t=2\tau-\delta t=2τ−δ时刻，两者发生碰撞发生在 t = τ − δ 2 t=\tau-\frac{\delta}{2} t=τ−2δ时刻。
最迟多久才能知道自己和别人发生了碰撞？当 δ = 0 \delta=0 δ=0时， t m a x = 2 τ − δ = 2 τ t_{max}=2\tau-\delta=2\tau tmax=2τ−δ=2τ，也就是两倍的总线端到端时延，也称总线的端到端往返时延。还叫争用期/冲突窗口/碰撞窗口。
我们还可以得到一个推论，只要经过2t时间还没有检测到碰撞，就能肯定这次发送不会发生碰撞。
三、如何确定碰撞后的重传时机？
1.为什么不能是一发现碰撞就重传？
如果两者都是在 t = 0 t=0 t=0时刻发送数据，那就会在 t = τ 2 t=\frac{\tau}{2} t=2τ时刻发生碰撞，然后双方均在 t = τ t=\tau t=τ时刻检测到冲突，如果这个时候双方都立即重传，那就又会在 t = 3 2 τ t=\frac{3}{2}\tau t=23τ时刻碰撞，然后又重传，又在 t = 5 2 τ t=\frac{5}{2}\tau t=25τ碰撞，没完没了了。一直冲突一直重发。
实际上，确定重传时间用到了截断二进制规避算法。
2.截断二进制规避算法：
- step 1：确定一个基本退避（推迟）时间为争用期 2 τ 2\tau 2τ
- step 2：定义参数 k k k，它等于重传次数，但 k k k不超过10，即 k = m i n [ 重 传 次 数 , 10 ] k=min[重传次数, 10] k=min[重传次数,10]。当重传次数不超过十， k k k等于重传次数；当重传次数超过十， k k k等于十。
- step 3：从离散的整数集合 { 0 , 1 , ⋯ ⋯ , 2 k − 1 } \{0, 1,\cdots\cdots, 2^k-1\} {0,1,⋯⋯,2k−1}中随机取一个数 r r r，重传所需要退避的时间就是r倍的基本退避时间，即 2 r τ 2r\tau 2rτ
- step 4：当重传达16次仍不能成功时，说明网络太拥挤，认为此帧永远无法正确发出，抛弃此帧并向高层报告出错。
比如说站点A需要重传数据，第一次重传， k = 1 k=1 k=1， r r r从 { 0 , 1 } \{0, 1\} {0,1}里面选，那么重传的推出时间 2 r τ 2r\tau 2rτ要么是0要么是 2 τ 2\tau 2τ，从这中间随机取一个。
若再发生碰撞，则在第二次重传时， k = 2 k=2 k=2， r r r从 { 0 , 1 , 2 , 3 } \{0,1,2,3\} {0,1,2,3}选；重传推迟时间为 0 0 0或 2 τ 2\tau 2τ或 4 τ 4\tau 4τ或 6 τ 6\tau 6τ，任选一个。
若再碰撞， r ∈ { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } r\in\{0,1,2,3, 4, 5, 6, 7\} r∈{0,1,2,3,4,5,6,7}
⋯ ⋯ ⋯ ⋯ ⋯ ⋯ \cdots\cdots\cdots\cdots\cdots\cdots ⋯⋯⋯⋯⋯⋯
若第十六次碰撞，就说明网络实在太拥挤，放弃了
若连续多次发生冲突，就表明可能有较多的站参与争用信道。使用此算法可使重传需要推迟的平均时间随重传次数的增大而增大，因而减小发生碰撞的概率，有利于整个系统的稳定。
例题：在以太网的二进制回退算法中，在11次碰撞之后，站点会在什么范围内选择一个随机数。
这个题有个坑点嗷，有的人一上来就是 r ∈ [ 1 , 2 11 − 1 ] ∩ Z r\in[1, 2^{11}-1]∩Z r∈[1,211−1]∩Z，但是需要注意的是， k = m i n [ 重 传 次 数 , 10 ] k=min[重传次数, 10] k=min[重传次数,10]，那么这里的 k k k应该是 10 10 10，答案应该是 r ∈ [ 1 , 2 10 − 1 ] ∩ Z r\in[1, 2^{10}-1]∩Z r∈[1,210−1]∩Z
四、最小帧长问题
如果站点A要发送的帧实在太短，那么发送碰撞后也可能无法停止发送，因为发完了。而CSMA-CD协议的作用就是想让碰撞发生时立马叫停帧的发送，因而需要对帧的长度作出规定。
我们只需要保证帧的传输时延至少要两倍于信号在总线中的传播时延。
最 小 帧 长 = 2 τ × 数 据 传 输 速 率 最小帧长=2\tau\times数据传输速率 最小帧长=2τ×数据传输速率
以太网规定最短帧长为64B，凡是长度小于64B的都是由于冲突而异常终止的无效帧。
五、本节思维导图
§3.5.5 CSMA-CA协议
一、CSMA-CA协议
0.首先这玩意不是考研重点，有点理解就行了。隔壁CSMA/CD才是考研重点。
1.概念：
CSMA/CA协议全称载波监听多点接入/碰撞避免协议(carrier sense multiple access with collision avoidance)
CD只能检测出碰撞，不能避免碰撞发生。而CA可以避免碰撞发生。
2.既然CSMA/CD已经很棒了，那为什么还要有CSMA/CA呢？
两者的应用情景是不一样的，CA往往应用于无线局域网，而CD往往应用于总线式以太网。
无线通信不同于有线通信，它的范围是360°的，难以进行检测冲突，在硬件上难以实现。同样是CSMA/CD检测碰撞，有线通信只用瞅准一端，无线通信需要东西南北前后左右上下的检测。而且由于无线通信会出现隐蔽站（后面会介绍到隐蔽站问题）的问题，也难以监听碰撞
如果说让CSMA/CA协议和别人开会，他没说一句话前都要等一等，没人抢话再说，然后下该一句话时又停住不说，没人说话再说。
二、CSMA/CA协议工作原理
发送数据之前，先检测信道是否空闲。
空闲则发送端发出RTS （request to send）,RTS包括发射端的地址、接收端的地址、下一份数据将持续发送的时间等信息；信道忙则等待。
接收端收到RTS后，将响应CTS (clear to send)
然后如果还有别的站点发送RTS则接收端不响应，这样就解决了隐蔽站问题。
啥叫隐蔽站问题，就是说A检测信道空闲，于是给B发送信息，C也检测到信道空闲，给B发送信息，然后AC的信息就会发生碰撞。
A：在？B：嗯。C：在？B：滚！
发送方收到CTS后会开始发送数据帧，同时预约信道（发送方告知其他站点自己要传多久数据）
接收端收到数据帧后，将用CRC循环冗余码检错，正确则返回ACK（CRC和ACK前面都讲过，忘了自己找）
发送方收到ACK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止(采用截断二进制规避算法来确定随机的推迟时间)。
三、CSMA/CA实现碰撞避免的三个手段
1.预约信道：
告诉其他站点自己这次传输数据大概需要多久。
2.ACK帧：
接收方返回确认帧
3.RTS/CTS帧（可选）：
可用可不用，内容详见上文。它主要用来解决隐蔽站问题。
四、CSMA/CD与CSMA/CA相比
1.相同点：
CSMA/CD与CSMA/CA机制都从属于CSMA的思路，其核心是先听再说。换言之，两个在接入信道之前都须要进行监听。当发现信道空闲后，才能进行接入。
2.不同点：
① 传输介质不同：CSMA/CD 用于总线式以太网【有线】，而CSMA/CA用于无线局域网【无线】。
② 载波检测方式不同：因传输介质不同：CSMA/CD与CSMA/CA的检测方式也不同。CSMA/CD通过电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化;而CSMA/CA采用能量检测（ED)、载波检测(CS）和能量载波混合检测三种检测信道空闲的方式。
③ CSMA/CD检测冲突，CSMA/CA避免冲突，二者出现冲突后都会进行有上限的重传。
§3.5.6 轮询访问介质访问控制
一、介质访问控制
-
信道划分介质访问控制(MAC Multiple Access Control）协议：
- 基于多路复用技术划分资源。
- 网络负载重：共享信道效率高。
- 且公平网络负载轻：共享信道效率低。
-
随机访问MAC协议：
- 网络负载重：产生冲突开销。
- 网络负载轻：共享信道效率高，单个结点可利用信道全部带宽。
-
轮询访问MAC协议 / 轮流协议 / 轮转访问MAC协议：
- 既要不产生冲突，又要发送时占全部带宽。
- 包括了：轮询协议、令牌传递协议。
二、轮询协议
主结点轮流“邀请”从属结点发送数据。轮流询问嘛，就叫轮询，询问用到的就是一个比较短的数据帧。
听起来似乎不错但是轮询也存在一定的问题。
① 轮询开销：如果说主节点的从属节点过多，就得不停地询问，开销太大。
② 等待延迟：我主机D要发送数据了，但是主节点还在询问ABC，我得等好久。
③ 单点故障：主节点宕机，从属节点全部用不了了。但实际应用中会有备用的主节点。
三、令牌传递协议
令牌指的是一个特殊格式的MAC控制帧，不含任何信息。他可以控制信道的使用，确保同一时刻只有一个结点独占信道。
若信道空闲，令牌在几个主机中不停地传来传去，比如传到了主机D，D要发送数据，发给A，它就改变令牌里面的关键位，把自己要发送的数据附加到令牌上，继续转圈圈地传送令牌。传到BC，BC发现跟他们没关系，就不管了，往下传。传到A的话，A就接受，在往下传，重新到D手里，D发现数据有错，就重新发送数据，若发现数据没有错误。把自己附加在令牌上的数据拔掉，把关键位改成原来的样子。每个主机手握令牌的时间都是有限的，如果D的时间到了，数据还没有发到，就拔掉数据改关键位，剩下的数据等令牌再次传到他手上再继续发。
-
令牌协议的问题：
- 令牌开销：传令牌要一定时间
- 等待延迟：等令牌到自己手里也要时间
- 单线故障：圈圈中的某个主机有问题了，整个圈圈都有问题。解决方法当然也是使用备用机。
令牌传递协议应用于令牌环网（物理星型拓扑，逻辑环形拓扑）。
采用令牌传送方式的网络常用于负载较重、通信量较大的网络中。负载较轻，其他协议就什么都不用传，令牌协议却要把令牌传来传去。
§3.6.1 局域网基本概念和体系结构
一、局域网
1.概念：
局域网(Local Area Network):简称LAN，是指在某一区域内由多台计算机互联成的计算机组，使用广播信道。
2.局域网的特点：
① 覆盖的地理范围较小，只在一个相对独立的局部范围内联，如一座或集中的建筑群内。
② 使用专门铺设的传输介质（双绞线、同轴电缆）进行联网，数据传输速率高( 10Mb/s～10Gb/s) 。
③ 通信延迟时间短，误码率低，可靠性较高。
④ 各站为平等关系，共享传输信道。
⑤ 多采用分布式控制和广播式通信，能进行广播和组播。
3.决定局域网的主要要素：
① 网络拓扑
② 传输介质
③ 介质访问控制的方法
二、局域网拓扑结构
中心节点是控制中心，任意两个节点间的通信最多只需==两步=，传输速度快,并且网络构形简单、建网容易、便于控制和管理。但这种网络系统，网络可靠性低，网络共享能力差,有单点故障问题。
网络可靠性高、网络节点间响应速度快、共享资源能力强、设备投入量少、成本低、安装使用方便,当某个工作站节点出现故障时，对整个网络系统影响小。
对于星型而言，集线器宕机了，其他就都坏了。对于总线型则不存在这个问题。
系统中通信设备和线路比较节省。有单点故障问题；由于环路是封闭的，所以不便于扩充，系统响应延时长，且信息传输效率相对较低。
易于拓展，易于隔离故障,也容易有单点故障。
某个节点出现问题，其子孙节点都出现问题。如果出问题的还是根节点，那这造成的单点故障将是毁灭性的。
三、局域网传输介质
-
有线局域网传输介质：
- 双绞线
- 同轴电缆
- 光纤
-
无线局域网：
- 电磁波
四、局域网介质访问控制的方法
1.CSMA / CD：
常用于总线型局域网，也用于树型网络。（树形网络不考，不用记）
2.令牌总线：
常用于总线型局域网，也用于树型网络。它是把总线型或树型网络中的各个工作站按一定顺序如按接口地址大小排列形成一个逻辑环。只有令牌持有者才能控制总线，才有发送信息的权力。
3.令牌环：
常用于环形局域网，如令牌环网。其物理结构是星型拓扑，逻辑拓扑是环形。
五、局域网的分类
1.以太网：
以太网是应用最为广泛的局域网，包括标准以太网（10Mbps)、快速以太网（100Mbps)、千兆以太网(1000 Mbps）和10G以太网，它们都符合IEEE802.3系列标准规范。逻辑拓扑总线型，物理拓扑是星型或拓展星型。使用CSMA/CD。
2.令牌环网：
物理上采用了星形拓扑结构，逻辑上是环形拓扑结构。已是“明日黄花”。
3.FDDI网(Fiber Distributed Data Interface)：
物理上采用了双环拓扑结构，逻辑上是环形拓扑结构。
4.ATM网Asynchronous Transfer Mode)：
较新型的单元交换技术,使用53字节固定长度的单元进行交换。
5.无线局域网(Wwireless Local Area Network; WLAN）：
采用IEEE 802.11标准。wifi就是无线局域网具体上的一个应用。
六、IEEE802标准
IEEE 802系列标准是IEEE 802 LAN/MAN标准委员会制定的局域网、城域网技术标准(1980年2月成立）。其中最广泛使用的有以太网、令牌环、无线局域网等。这一系列标准中的每一个子标准都由委员会中的一个专门工作组负责。
IEEE 802.3 ：以太网介质访问控制协议 （CSMA/CD）及物理层技术规范。
IEEE 802.5 ：令牌环网（Token-Ring)的介质访问控制协议及物理层技术规范。
IEEE 802.8 ：光纤技术咨询组，提供有关光纤联网的技术咨询。广泛应用于FDDI，因为光纤广泛应用于FDDI
IEEE 802.11：无线局域网（WLAN）的介质访问控制协议及物理层技术规范。
七、MAC子层和LLC子层
IEEE 802标准所描述的局域网参考模型只对应OSI参考模型的数据链路层与物理层，它将数据链路层划分为逻辑链路层LLC子层和介质访问控制MAC子层。
LLC子层（逻辑链路控制子层）负责识别网络层协议，然后对它们进行封装。LLC报头告诉数据链路层一旦帧被接收到时，应当对数据包做何处理。为网络层提供服务:无确认无连接、面向连接、带确认无连接、高速传送。
MAC子层（介质访问控制子层）的主要功能包括数据帧的封装/卸装，帧的寻址和识别，帧的接收与发送，链路的管理，帧的差错控制等。MAC子层的存在屏蔽了不同物理链路种类的差异性。
八、本节思维导图
§3.6.2 以太网
一、以太网概述
1.概念：
以太网(Ethernet)指的是由Xerox公司创建并由Xerox、Intel和DEC公司联合开发的基带总线局域网规范，是当今现有局域网采用的最通用的通信协议标准。以太网络使用CSMA / CD（载波监听多路访问及冲突检测）技术。
以太网在局域网各种技术中占统治性地位。
2.为何以太网在局域网各种技术中占统治性地位：
① 造价低廉（以太网网卡造价不到100）
② 是应用最广泛的局域网技术。
③ 比令牌环网、ATM网更便宜，简单。
④ 可以满足网络速率的要求（10Mb/s~10Gb/s.）
3.以太网标准：
① DIX Ethernet V2:第一个局域网产品（以太网）规约。
② IEEE 802.3:IEEE 802委员会802.3工作组制定的第一个IEEE的以太网标准。（帧格式有一丢丢改动)
因而以太网又称802.3局域网。
二、以太网所提供的无连接、不可靠服务
无连接:发送方和接收方之间无“握手过程”。
不可靠:不对发送方的数据帧编号，接收方不向发送方进行确认，差错帧直接丢弃，差错纠正由高层负责。
以太网只实现无差错接收，不实现可靠传输。
三、以太网传输介质与拓扑结构的发展
粗同轴电缆
细同轴电缆
双绞线+集线器
粗同轴电缆和细同轴电缆的物理拓扑结构都是总线型，而后面的双绞线+集线器的拓扑结构是星型。（你看他有个集线器么，肯定是星型）
使用集线器的以太网在逻辑上仍是一个总线网，各站共享逻辑上的总线，使用的还是CSMA/CD协议。
以太网拓扑：物理上是星型，逻辑上和传统以太网一样是总线型。
四、10 BASE-T以太网
1.概念：
10BASE-T是传送基带信号的双绞线以太网，T表示采用双绞线，现10BASE-T采用的是无屏蔽双绞线(UTP)，传输速率是10Mb/s。
2.特点及相关规定：
① 物理上采用星型拓扑，逻辑上总线型，每段双绞线最长为100m。也就是说从主机到集线器最长100米。
② 采用的编码方式是曼彻斯特编码。
③ 采用CSMA / CD介质访问控制
五、适配器和MAC地址
1.适配器：
计算机与外界有局域网的连接是通过通信适配器的。它是一个网络接口板，又称网络接口卡NIC ( network interface card)，其实就是网卡。现如今已不再使用单独网卡，且适配器上装有处理器和存储器（包括RAM和ROM) 。
2.MAC地址：
在局域网中，硬件地址又称为物理地址，或MAC地址【实际上是标识符】。在适配器上装有的ROM上会有计算机硬件地址MAC地址。
MAC地址:每个适配器有一个全球唯一的48位二进制地址，前24位代表厂家（由IEEE规定)，后24位厂家自己指定。常用6个十六进制数表示，如02-60-8c-e4-b1-21。这个就是MAC地址。
六、以太网MAC帧
最常用的MAC帧是以太网V2的格式。
前面的八个字节是前导码，用于同步，并不属于MAC帧。
目的地址如果为广播式的，那发送全1的六个字节，也就是ffffffffffff，两个字节的类型用来指明上面的网络层使用的是什么协议。
数据链路层需要加头加尾来界定数据帧的开始结束，这里不需要，因为以太网使用的是曼彻斯特编码，用变化的电压表示0和1，若无电压变化，那必然是数据帧结束传输了。
v2和IEEE 802.3的区别在于：
① 第三个字段是长度 / 类型
② 当长度 / 类型字段值小于0x0600时，数据字段必须装入LLC子层。
七、高速以太网
1.概念：
速率≥100Mb/s的以太网称为高速以太网。
2.分类：
-
① 100BASE-T以太网：
- 在双绞线上传送100Mb/s基带信号的星型拓扑以太网，仍使用IEEE802.3的CSMA/CD协议。
- 支持全双工和半双工，可在全双工方式下工作而无冲突。
-
② 吉比特以太网：
- 在光纤或双绞线上传送1Gb/s信号。
- 支持全双工和半双工，可在全双工方式下工作而无冲突。
-
③ 10吉比特：
- 10吉比特以太网在光纤上传送10Gb/s信号。
- 只支持全双工，无争用问题。
八、本节思维导图
§3.6.3 IEEE 802.11无线局域网
一、IEEE 802.11 无线局域网
IEEE 802.11是无线局域网通用的标准，它是由IEEE所定义的无线网络通信的标准。
WiFi是无线局域网的一种，无线局域网不一定就是WiFi，无线局域网可以覆盖的范围可以是几千米，WiFi只能覆盖一个房子。
二、802.11的MAC帧头格式
SA就是西安的mac地址，DA就是曹县mac地址，西安到曹县可能有一段路是渭南到济南，那这段路的TA是渭南mac地址，RA就是济南mac地址。
这玩意考试不咋考，懂了就行。
三、无线局域网的分类
1.有固定基础设施的无线局域网：
这样一个东西，叫做基站，我们把它设为ap1，
设为ap2
基站可以让它的范围内的主机相互通信，也就是漫游。同一个基站范围内的两台计算机进行通信需要由A发送数据给基站，然后基站发送数据给B。囊括了基站和基站覆盖范围内的计算机的集合叫做服务集（ESS），只要在同一个BSS内就可以实现直接通信。
如果是西安的计算机A要和曹县的计算机B实现通信，仅通过无线通信是不现实的，毕竟人家曹县咱们高攀不起，毕竟距离较远。那方法就是A主机通过无线通信把数据发送给它所属的ESS中的基站那里，基站通过有线通信把数据发送给B所属的ESS的基站那里，然后再由B的基站通过无线通信运输给B。
我们连WiFi的时候，看到的WiFi名字，其实就是服务集标识符。每个标识符都对应一个基站。
2.无固定基础设施无线局域网的自组织网络：
这种情况下每一个节点都是既可以当数据发送接收端，也可以当基站，既能收发数据，还能帮忙转发数据。各节点的地位相互平等，而且节点位置可以随便移动。
（这玩意基本不考，了解就行）
§3.7 PPP协议和HDLC协议
一、广域网
PPP协议和HDLC协议广泛应用于广域网当中，所以我们先看一下广域网是个什么东东。
广域网（WAN，Wide Area Network)，通常跨接很大的物理范围，所覆盖的范围从几十公里到几千公里，它能连接多个城市或国家，或横跨几个洲并能提供远距离通信，形成国际性的远程网络。互联网Internet就是广域网的一个例子。
广域网的通信子网主要使用分组交换技术。广域网的通信子网可以利用公用分组交换网、卫星通信网和无线分组交换网，它将分布在不同地区的局域网或计算机系统互连起来，达到资源共享的目的。如因特网（Internet)是世界范围内最大的广域网。
叫做节点交换机，属于链路层设备，但是他和路由器（路由器是网络层设备）的功能很像，都是用来发分组的。不同的是节点交换机只能在单个网络中转发分组，但是路由器可以在多个网络中转发分组。
除了节点交换机，广域网甚至还包含集线器，路由器等等。也就是说局域网仅包含物理层、数据链路层，而广域网包含了网络层、数据链路层、物理层。局域网看起来更像线性表，而广域网实质上是加权无向图。广域网涵盖范围大，所以延迟也就比局域网中的大。
二、PPP协议的特点
1.概念：
点对点协议PPP(Point-to-Point Protocol）是目前使用最广泛的数据链路层协议，用户使用拨号电话接入因特网时一般都使用PPP协议。它仅支持全双工链路。
2.需要满足的要求：
① 简单：对于链路层的帧，无需纠错，无需序号，无需流量控制。
② 封装成帧：帧定界符
③ 透明传输：与帧定界符一样比特组合的数据应该如何处理：异步线路用字节填充，同步线路用比特填充。
④ 多种网络层协议：封装的IP数据报可以采用多种协议。
⑤ 多种类型链路：串行/并行，同步/异步，电/光……
⑥ 差错检测：错就丢弃。
⑦ 检测连接状态：链路是否正常工作。
⑧ 最大传送单元：数据部分最大长度MTU。
⑨ 网络层地址协商：知道通信双方的网络层地址。
⑩ 数据压缩协商：发送数据时，要把数据进行压缩。
3.无需满足的要求：
① 无需纠错，检错就行。
② 无需流量控制，全部交给上层负责。
③ 无需对帧编编号。
④ 不支持多点线路，只支持点对点。
3.三个组成部分 / 需要实现的三个主要功能：
① 一个将IP数据报封装到串行链路（同步串行/异步串行）的方法。
② 链路控制协议LCP：建立并维护数据链路连接。LCP协议的一个重要应用就是身份验证，例如拨号上网时账号密码输的不对，LCP就不会建立数据链路连接，就没网了。
③ 网络控制协议NCP：PPP可支持多种网络层协议，每个不同的网络层协议都要一个相应的NCP来配置，为网络层协议建立和配置逻辑连接。
4.PPP协议工作状态图：
5.PPP协议的帧格式：
① 标志字段F：前后两个7E（0111 1110）是标志字段，也就是帧定界符。同样的，如果信息部分也有7E的字节，那前面就要有转义字符7D（0111 1101），当然如果传输的数据是转义字符7D，那就传7D7D，类似“\”。
② 地址字段A和控制字段C：第二三个字节FF03（1111 1111 0000 0011），创作的时候希望将来在给它定义意义，但是到现在都是没有意义的，没有任何有用信息。
③ 协议部分：那两个没用字节后面的俩个字节，用于标识信息部分是什么，IP数据报，LCP数据报，或者还是别的什么。
④ 冗余码FCS：就是用CRC循环冗余检验算法在后面插入的帧检验序列。
三、HDLC协议
这个协议是广域网领域的，但很少应用。
1.概念：
高级数据链路控制（(High-Level Data Link Control或简称HDLC)，是一个在同步网上传输数据、面向比特的数据链路层协议，它是由国际标准化组织(ISO)根据IBM公司的SDLC(SynchronousData Link Control)协议扩展开发而成的。
数据报文可透明传输，用于实现透明传输的“0比特插入法”易于硬件实现。（零比特插入，遇到五个一就插入一个零，忘了的话翻前面，我正我写到这里就是把这个忘了）
HDLC和PPP一样是全双工通信。它的所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏收或重份，传输可靠性高。
2.HDLC的三种站：
① 主站的主要功能是发送命令〈包括数据信息）帧、接收响应帧，并负责对整个链路的控制系统的初启、流程的控制、差错检测或恢复等。
② 从站的主要功能是接收由主站发来的命令帧，向主站发送响应帧，并且配合主站参与差错恢复等链路控制。
③ 复合站的主要功能是既能发送，又能接收命令帧和响应帧，并且负责整个链路的控制。
3.相应的三种数据操作方式：
① 正常响应方式：从站要发送消息，需要经过主站同意。
② 异步平衡方式：每一个复合站都可以实现对别的站的数据传输。
③ 异步响应方式：从站恶意不经过主站同意就发消息
4.HDLC的帧格式：
① 标志字段F：和PPP一样，首尾都有0111 1110，不过不同的是，HDLC不需要转义字符，只需要在透明传输区间中使用零比特传输即可。
② 地址A：如果使用正常响应方式或异步响应方式，地址为都是从站地址。如果是异步平衡方式，填入接收方地址，
③ 控制C：决定了这个HDLC帧的类型，就类似PPP中的协议部分。
1）信息帧(I）第1位为0，用来传输数据信息，或使用捎带技术对数据进行确认;
2）监督帧(S)10，用于流量控制和差错控制，执行对信息帧的确认、请求重发和请求暂停发送等功能
3)无编号帧(U) 11，用于提供对链路的建立、拆除等多种控制功能。
四、PPP协议和HDLC协议的异同
1.相同点：
① HDLC、PPP只支持全双工链路。
② 都可以实现透明传输。
③ 都可以实现差错检测，但不纠正差错。
2.不同点：
PPP一定是整字节正字节的传输，HDLC是一个比特一个比特。
五、本节思维导图
§3.8 链路层设备
一、物理层拓展以太网
1.方式一：光纤
集线器与主机之间的距离不能超过一百米，否则会失真。因此远距离的通信就要用物理层拓展以太网。比如用光纤和集线器连接，在发送端利用光纤调制器把电信号转化成光信号，在接收端利用光纤解调器把光信号转化成电信号。
2.方式二：主干集线器
所谓冲突域，就是在这个区域内，只能有一个主机进行通信，若有一个以上就会冲突。一般是指一个集线器所连接的主机的集合。为了让不同的冲突与中的主机进行通信，就要把不同的集线器连接在主干集线器上。这样冲突域A中的计算机就能与冲突域C中的计算机进行通信了。多个小冲突域就能连接成一个大冲突域。这样做的缺点就是通信效率贬低了，以前的小冲突域中主机少，冲突概率低，而大冲突域主机多，那冲突概率就大了。
二、链路层扩展以太网
1.网桥：
网桥根据MAC帧的目的地址对帧进行转发和过滤。当网桥收到一个帧时，并不向所有接口转发此帧，而是先检查此帧的目的MAC地址，然后再确定将该帧转发到哪一个接口，或者是把它丢弃（即过滤）。
如图，网桥连接起来了一个个的以太网，每个以太网就是一个冲突域，或者也称为网段。
2.网段：
网段一般指一个计算机网络中使用同一物理层设备(传输介质，中继器，集线器等）能够直接通讯的那一部分。
3.网桥的优点：
网桥有四大优点：一、过滤通信量，增大吞吐量。二、扩大了物理范围。三、提高了可靠性。四、可互连不同物理层、不同MAC子层和不同速率的以太网。
三、网桥的分类
1.透明网桥：
透明网桥：“透明”指以太网上的站点并不知道所发送的帧将经过哪几个网桥，是一种即插即用设备――自学习。
网桥并不知道网络的拓扑结构，所以才需要通过自学习算法构造转发表。
2.源路由网桥：
源路由网桥会在发送帧时，把详细的最佳路由信息（路由最少/时间最短）放在帧的首部中。
它所采用的方法是：源站以广播方式向欲通信的目的站发送一个发现帧。
四、多接口网桥 — 以太网交换机
1.概念：
以太网交换机的接口可以接在集线器上，也可以直接接在主机上。取决于网络复杂程度。
以太网交换机的每一个端口都是一个冲突域，以太网交换机独占传输媒体带宽。
2.交换方式：
-
① 直通式交换机：
- 检查完六个字节的目的地址就立刻转发。
- 延迟小，可靠性低，无法支持具有不同速率的端口的交换。
-
② 存储转发式交换机：
- 将帧放入高速缓存，并检查否正确，正确则转发，错误则丢弃。
- 延迟大，可靠性高，可以支持具有不同速率的端口的交换。
五、冲突域与广播域
冲突域：在同一个冲突域中的每一个节点都能收到所有被发送的帧。简单的说就是同一时间内只能有一台设备发送信息的范围。
广播域：网络中能接收任一设备发出的广播帧的所有设备的集合。简单的说如果站点发出一个广播信号，所有能接收收到这个信号的设备范围称为一个广播域。
| 能否隔离冲突域 | 能否隔离广播域 | |
|---|---|---|
| 物理层设备【傻瓜】中继器、集线器) | × | × |
| 链路层设备【路人】(网桥、交换机） | √ | × |
| 网络层设备【大佬】(路由器) | √ | √ |
（这张表格十分重要）
例题：
该拓扑结构中一共有几个冲突域？几个广播域？
解答：从上面那个表可以知道只有网络层设备路由器才能分割广播域，而上图中没有路由器，所以只有一个广播域。这个以太网交换机连接了三个主机和一个集线器，三个主机各自构成一个冲突域，集线器及其上连接的主机有构成了一个冲突域。所有上图共有一个广播域，四个冲突域。
六、本节思维导图
§3.9 第三章思维导图
（PS：该笔记所对应的学习资料b站链接：2019 王道考研 计算机网络）
