计算机网络第三章——数据链路层第二部分：实现流量控制和可靠传输还有介质访问控制的各种协议和方法

1.流量控制和可靠传输机制

1.1 什么是流量控制

流量控制是链路层根据接收方的接收能力来限制发送方发送数据的速度的行为。因为如果发送方发的太快，但是接收方的接收速度很慢，就会造成数据溢出，然后就有一些数据收不到，发生错误。
这里必须说明的一个点是，数据链路层考虑的接收方和发送方指的是点到点的，也就是说，两个相邻节点(可以是两个中间节点，也可以是发送的主机和第一个中间节点)之间的事情，所以前面半部分里面说的字符填充或者零比特填充其实是每一个节点都会把被填充的数据给消掉，然后再重新填充，这里做一个修正。
流量控制的操作主要是通过接收方不回复确认帧来实现的，也就是当发送方发现对方对前几个帧的数据进行了回复，但是对后面几个帧的数据没有回复，发送方就会减缓发送的速度，这是其基本的原理。具体要怎么减缓发送，其实是根据不同的协议来实现的，这些协议多是人为规定的，所以学的时候不需要太疑惑。

1.2 什么是可靠传输

可靠传输就是保证接收方能够完整的收到发送方发送的全部帧。目前可靠传输主要是依靠自动重传来实现的，具体也是需要通过协议来规定。下面我们就来依次讲一下相关的这些协议。在正式讲解协议之前，必须说一下，下面这些协议其实都是传输层的协议，这是因为目前的技术相比之前已经更加进步，不需要再在传输层来实现可靠传输，传输层只需要验错和纠错即可。但是因为以前的设备不是那么可靠，所以即便是在数据链路层也需要实现可靠传输。这里再说一下传输层和数据链路层的区别，传输层是端到端的，也就是说只需要发送的主机和接收数据的主机同时遵守这些协议即可，不需要每一个中间节点都遵守，大大节省了资源。所以下面几个协议，大家不需要太纠结处于哪个层次，因为计算机本身就是不断套娃的事情，并不是说一个协议只能在什么地方使用。

1.3 停止-等待协议

停等协议是用来解决数据丢失问题的，电气干扰，设备故障，或者是发送方发送的速度太快，接收方来不及缓存都有可能造成数据丢失，我们也称之为丢包。停止等待协议的内容十分简单，就是当发送方发出一定量的数据以后，不会立刻发送下一份数据，而是等待接收方回复，只有接收方回复已经收到了数据，发送方才会发送下一份数据。

1.3.1 停等协议的具体内容

停止等待协议就是发送方发一帧，接收方就回复一帧：

它的特点有：
（1）每次发送方发出一份数据之后，自带的超时记时器就会启动计时，当计时器归零的时候，重新发送这一份的数据，这个过程也被称为重传。这就要求超时记时器的时间要大于信号在发送方和接收方之间的平均往返传输时延(RTT),如果小于RTT，至于为什么就不用解释了。
（2）在每发送一个帧之前都需要进行备份，来准备重传。
（3）每一个帧都需要一个专门的编号。因为接收方的回复也可能会丢失，这个时候发送方也会因为收不到确认信号进行重传，当接收方收到两个编号一样的数据的时候，会丢弃这个数据，但是返回一个确认帧。
（4）当接收方检查收到的帧的时候，如果发现错误就不会返回一个确认帧，而是直接丢弃这个帧，等待接收方重传。因为返回一个确认帧要比直接等发送方重传要方便，而且时间上也差不了多少。
（5）确认帧信号也可能因为各种原因到达时间要比计时器的时间要大，这个时候发送方会重传，然后出现连续收到两个相同确认帧的情况，一样的，发送方会对收到的第二个确认帧进行忽视。

这个协议看起来很美好，但是实际上信道利用率很低，因为可以从图上看到，信道很多时候都是空着的，不是那么符合通信要求的速率问题。下面学两个考这方面内容会考的名词：

1.3.2 信道利用率

信道利用率是一个常考考点。信道利用率其实就是发送方在一个发送周期内，有效的发送数据所占的时间，占整个发送周期的比率。发送周期其实就是发送方发送数据到收到接收方回复的一个时间，可以更简单的理解为一个发送周期内，信道上发送数据时通过的数据量和信道带宽乘以时间的比值，更直观的可以看作下图的一个面积比值，用整个信道的面积去比上发送方信号传输的面积，这里必须注意的是，要把接收方处理确认帧的时间也算进去：

因为高是一样的，所以直接用时间相比即可。当然，题目不会直接给你这几个数字让你计算，而是给你发送方的发送速率，并且给你一个帧有多少的数据，再给你一个RTT和确认帧的确认时间，让你计算信道利用率，这个时候就需要用数据量除以发送速率先算出发送的时间，然后再计算。
来个例题：

这个题要求的是发送的数据帧的大小，这要求我们灵活利用公式求未知量,我们设这个帧的长度为xkb,单位也要统一，RTT=30msx2=0.06s,题目没有说明处理确认帧的时间，显然这个点可以忽略不计：

x

4

÷

(

x

4

+

0.06

)

=

0.8

frac{x}{4}div(frac{x}{4}+0.06)=0.8

4x​÷(4x​+0.06)=0.8可以算得x=0.06kb=960bit

1.3.3 信道吞吐率

信道吞吐率就是计算一个传输周期内，发送方的平均发送速率，公式是：

信道吞吐率

=

信道利用率

×

发送方的发送速率

信道吞吐率=信道利用率times发送方的发送速率

信道吞吐率=信道利用率×发送方的发送速率

1.4 后退N帧协议

后退N帧协议简称GBN，它是对停等协议的一个改进。其主要思想是利用流水线技术(计组里面有过相关学习)，发送方一次发送多个帧，然后接收方也一次性回复多个帧。

显然，和停等协议相比，发送方每次都需要额外保存N个帧，所以对发送方的缓存容量要求更高。

1.4.1 后退N帧的滑动窗口

这里先理解一下两个概念：
（1）发送窗口：指的是发送方维持一组连续的，允许发送的帧的序号。听着比较绕口，其实就是如果我们一组要一起发送的帧有五个，我们就给它们编上0，1，2，3，4这样的帧序号，同时这些帧序号是允许被下一组要发送的帧复用的，比如我们第一次发送的一组帧的序号是0，1，2，3，我们第二次也可以用0，1，2，3来作下一组帧的序号。至于如何区别同序号的帧来自于哪一组呢？这个不用担心，这是因为停等协议里面，只有接收方表示它收到了这一组的全部内容，发送方才会发送下一组，所以序号可以复用。这也就要求发送窗口的大小最少要比当前的序号小一位，否则接收方无法区分是哪一组。比如当前的编号是0，1，2，3，那么滑动窗口只能有3位。

（2）接收窗口：接收方维持一组连续的，允许接收的帧序号。简单来说就是接收方希望收到哪个序号的帧。在后退N帧协议里面，接收方的接收窗口始终只有一个数字：

从上面就可以看出来，这些即将被发送或者接收的数据组成了一个序列，我们可以把这些序列看作是窗子，接收方和发送方通过窗子进行通话，当0号窗口通话结束之后(也就是接收方返回ACK0)，发送方和接收方都会同时把窗口左移一格。如图：

为什么接收窗口的数量为1呢，这是为了保险起见，因为如果同时确认多个窗口，会消耗很多资源，但是如果第一个错了，那就需要全部重传，所以接收方是一个接一个的确认的。虽然是一个接一个确认的，但是接收方也是在连续确认N个之后进行一次性回复的，比如确认了0，1，2，3 之后一次性回复ACK0，ACK1，ACK2，ACK3。

其实从底层硬件来看，所谓发送窗口，其实就是在发送端口寄存器里面存着随时能发出去的数据，接收窗口也是接收器里面一旦接收到就能检验的数据列表。

1.4.2 后退N帧协议的具体内容

（1）物理层把要发送的数据传递到数据链路层，然后数据链路层如果有较大的额外缓存的话，会把这些数据全部接收下来， 然后把根据发送缓存的大小(也就是发送窗口大小)，把一部分数据给放入其中。如果数据链路层这里没有更大的缓存了(现在的电脑一般都是有的)，就会反馈网络层一个当前发送窗口已满的信号，当窗口滑动之后再向网络层索要下一部分的数据。
（2）在GBN中，发送方一次发送多个帧的数据，之后接收方会依次确认，最后返回的是最后确认到的哪个帧的回复，这被称为累积确认方式。比如说发送方一次性发送了0，1，2，3，4，5，接收方依次确认，确认到5全部没有问题，接收方就只会返回一个ACK5，而不是ACK0，ACK1…这样全部回复。接收方也有一个计时器，在依次确认中，如果等了一定的时间还没有新的数据发过来，它就会进行回复。

（3）当发送超时时：因为GBN其实是特殊的停等协议，所以它也有一个超时计时器，超时计时器的时间应该是稍大于全部帧发送出去以后的RTT。当超时发生时，如果没有任何回复，那么发送方会重新发送发送窗口里面的全部内容，如果回复的ACK不是当前窗口里面的最后一个帧的序号，那么发送方会把发送窗口进行一个滑动，起点滑动到接收方回复的那个帧的下一个帧，然后再次发送。这其实也就是它为什么被称为后退N帧协议的原因，当发送方把数据发送出去以后，发送窗口本应”滑动“整个窗口的距离，但是因为有部分数据丢失，所以窗口会“倒退”到丢失的那个数据。比如序号是0，1，2，3，发送窗口大小是3，那么当2丢失以后，发送方会退到2的位置，发送2，3，0。这也是为什么发送窗口大小至少比序号小一位的原因，因为如果发送窗口大小是4，那么当0丢失之后，接收方无法确认重新发送过来的0是当前的0还是下一组的0（虽然一般而言，发送方会重传当前这一组的数据，但是程序难免出错，这等于是一个双重保险）。

（4）接收方不会接收除了接收窗口里面序号的任何数据。比如现在3号数据丢失了，但是接收窗口里面的序号是3，那么接下来发送过来的4，5…等帧都会被丢弃。一段时间之后，接收方就会发送ACK2，这个时候发送方就会明白3号帧没有被传出去。当然，有的接收设备里面也没有计时器，它会在收到任何当前接收窗口以外的帧的时候，发出一个回复。比如3丢失了，那么当接收方收到4的时候就会把4丢弃并发送ACK2。当然，有的机器是这样的，每隔一段时间发送一次确认。但是不管它是怎么确认法，我们只需要牢记接收方收到的最大的一个确认序号前面的全部帧接收方都收到了即可。

1.4.3 例题

来做个题目加深一下印象：

因为要求最大传输率，所以我们不需要考虑到其出错的情况。我们一次发送

1

0

6

×

8

10^6times8

106×8bit的数也就是8Mbit据（要注意字节和bit的换算）。但是每一秒发送的其实不止一组数据帧，因为滑动窗口一直前进，现在就是要计算一秒内能发几组数据。因为忽略接收方的传输时延，所以只需要计算接收方的传播时延即可，并且因为是累积确认，所以我们相当于发送一个组数据到确认需要的是100ms，也就是0.1s。那么一秒内就可以发送10组数据，一组数据是8M，那么最大的传输速率其实是80Mb/s。选C。当然，你也可以考虑得更深入一些，因为发送也需要时间，题目里面没有说明，所以要用8000bit/100Mb/s得到每一次发送都需要0.08ms(这里注意，只需要算一个帧的时间即可，因为后面的帧的传输的时间不会影响整体时间)，带入之后就是一组需要100.08ms,因为0.08很小，所以算出来还是约等于80Mb/s。

1.4.4 GBN协议的优缺点

GBN的优点就是信道利用率比停等协议要更高。
GBN的缺点很明显，就是还是存在浪费的现象，比如我们发送了5个帧，除了2号帧，其他帧都正常抵达了，但是接收方不会接收，从而需要重新传递好几个帧，造成了浪费。

1.5 选择重传协议

选择重传协议简称SR，又是对后退N帧协议的一种改进。目前基本都是这种协议。它的思想是用空间换时间(当前空间不值钱的)，也就是接收方会把发送方发过来的全部帧都存下来，然后保存至缓冲器内，根据序号进行排序并且进行检测，每检测一个帧且这个帧没有出错就发回一个确认帧。

1.5.1 选择重传协议的窗口滑动机制

选择重传协议的滑动窗口也没有那么复杂，如图所示：

接收方每收到一个信息就回复一个确认信息，当发送窗口或者是接收窗口的第一个序号被确认收到的时候，发送窗口或者接收窗口就会右移一格，如果发送窗口或者是接收窗口的第一个序号的数据没有被确认，那么窗口就不会滑动。

1.5.2 选择重传协议的特点

（1）接收方给窗口内的每一个帧都设置了单独的确认标志以及计时器。当计时器超时且确认标志位没有被激活的时候，就会重新发送这个帧。接收方从网络层获得数据的规则和后退N帧协议是一样的这里不再赘述。
（2）接收方会接收任何属于接收窗口的帧，不管它是不是按序到达的，不是按序的帧接收方会把它暂存到一个缓冲区并且给发送方一个接收到该帧的确认，等这个帧前面的帧到达以后接收方再把这个帧放入到接收区，这样就能保证接收区的数据是有序的，后面一次交付给上层。和前面两个协议一样，当接收方收到当前窗口前面的帧的时候，说明前面的帧的回复丢失了，接收方会立即进行二次回复。
(3)对于选择重传协议，其滑动窗口的大小要比后退N帧更小。这是因为它的接收窗口有多个，这就导致它很多时候无法区别新的帧还是旧的帧，如图：

图中两个例子里面接收方都接收到了错误的0号帧。所以本协议中接收窗口需要满足以下几个条件：
（1）接收窗口大小等于发送窗口大小；
（2）如果序号一共有n个比特，则两个窗口的大小应该是

2

(

n

−

1

)

2^{(n-1)}

2(n−1)。
在上面的例子中,n显然是2，所以窗口大小不应该超过2。

2.介质访问控制

前面学习了如何编码一个帧以及如何保证这个帧能准确无误地被接收方接收，现在介质访问控制则是学习如何避免两个相邻信号之间的互相干扰。在前面我们学习过，在一个局域网中，通信是广播式进行的，也就是通过空气作为介质，那么如何保证两个设备同时给对方发消息，信息不会出错呢？这就需要介质访问控制来实现，具体方式就是划分信道的方法。目前信道的划分一共有两种方式：静态和动态划分。我们来依次学习。

2.1 静态划分信道

静态划分信道也被称为信道划分介质访问控制，其基本原理就是在每一个设备进行通信之前，就给每一个设备划分好它能用的信道，避免在信道上出现冲突。光这么说很抽象，我画一个图来解释一下：

如图，我们可以根据频率，时间等把信道分成两半，通信的两个设备A和B各用一半，就比如我们的收音机的电台各占一个频段，它们之间就不会产生冲突。这种把多个信号组合到同一个信道上的技术也被称为多路复用技术，它可以大大提高信道利用率。如图，在一个局域网中，会有一个复用器来专门整合这些要传输的数据到一个信道上，在接收方前面也会有一个分用器来把这些复用的信号拆开,把物理上是广播的信道变成逻辑上的点对点信道。

这就是静态划分信道的基本方法，根据分的方法，我们又可以进一步将其划分成四种，我们来依次讲解。

2.1.1 频分多路复用技术

频分多路复用技术简称FDM，它的基本思想就是把一个信道根据频率的高低进行分割，每一个频段传递一个设备的信息，这样分用器就可以直接根据频率的高低快速地把各个信息分离出来。

频分多路复用技术是目前使用时间最长，最为成熟的技术，收音机收到的各个广播电台就是使用了频分多路复用的原理，收音机既是分用器也是接收方。这其实是一种并行的传输效率

2.1.2 时分多路复用技术

时分多路复用技术，简称TDM，这个技术和操作系统里面的并发执行非常相似，具体原理就是每一个时间段都有一个设备独占整个信道，分用器在信道的终点根据时间片来提取出各个信息，每一个设备的信息在上面称为一个时隙。

这里的TDM帧不是指数据链路层的帧，而是物理层的一种传输划分，具体怎么定义一个TDM帧是通信方面的知识，我们只需要知道一个TDM帧里面根据位置不同，包含了各个要传输的信息，每一个信息都是根据时间放到信道上的，但是这样组成的TDM帧里面各个时隙的位置不变，这样就便于分用器对各个信息进行区分。
从图上可以看到，每一个时间片中间都有一段空隙，这是为了能更方便的确定各个信息的起点和终点，但是这也导致了它信道利用率不高(因为有空白)，而且它还有一个致命的缺点，就是如果一个设备在一段时间内没有发送信息，TDM帧里面关于它的这一部分就必须空着，形成浪费。于是目前就改进出了统计时分复用技术，简称STDM技术:

如图所示，复用器改成了集中器(本质上还是复用器)，它负责收集各个信号，然后根据时间进行一个整合，虽然整合出来的信号和信号之间还是是空隙，但是这个空隙远小于单纯的时分复用技术，使用STDM技术获得的传输单元被称为STDM帧，同时，每一个STDM帧的时隙都是固定的，可以是两个也可以是三个，具体需要进行人为规定，所以和TDM帧不一样的是STDM帧的时隙位置并不固定，这也就克服了TDM里面的致命缺点，当一个设备没有使用信道时，其他设备就可以占用更多的信道，并不会降低信道的利用率。

2.1.3 波分多路复用

波分多路复用，简称WDM，你也可以将其称之为光的频分多路复用。因为这技术是针对光信号而言的，对于光而言，波长不一样，频率也就不一样。因为也是频分多路复用，所以基本原理上面是一致的，每一个设备发出的光信号都占有一个波段，一起在光纤等信道上传输，到最后分用器根据波长把各个信号分开。

2.1.4 码分多路复用

码分多路复用，简称CDM，也常称之为码分多址CDMA。要比前面三个都复杂，具体可以看一下王道的PPT：

举一个有点怪的例子：时分多路复用好比某一个时间段内只允许尾号是单号的车走，另一段时间内只允许双号车行走，频分多路复用和波分多路分页则是把路分成两边，一边让单号车走，一边让双号车走；而码分多路复用，它把单号车和双号车叠加在一起组成一个双层小车，两车一起走。具体的码分多址技术有如下的特征：
（1）分用器会分别对每一个设备的数据分配一个码片序列。码片是用来代替原本信息里面一个bit数据的一组二进制编码，常见的是64位或者128位，这里为了方便就设置成8位，比如00011011.把0变成-1，这样的每一个编码称为一个码片(也可以叫做芯片)，这样就组成了两个码片序列。比如S设备的码片是00011011，T设备的码片是11010001，那么它们的码片序列各是：-1-1-111-111和11-11-1-1-11。在给每一个设备都分配一个码片以后，设备发出信息里面的1就用码片来代替，0就用码片的反码来代替。比如：S的码片是-1-1-111-111，那么如果S想要发送一个数据110，这个时候发出去的就是-1-1-111-111 -1-1-111-111 111-1-11-1-1。
（2）每一个需要共享同一个信道的设备的码片都是唯一且互相正交的，具体体现为其规格化内积为0。什么是规格化内积呢，就是两个向量点积再除以它们的维度。首先是点积：

之后是向量的维度其实就是一个向量里面数字的数量，比如上面的两个向量里面都有3个数字，维度就是3，所以可以得到上面的向量的规格化内积为38/3。如果还没有看懂可以看一下这篇博客。这里从几何上解释一下原理，就是每一个通信设备的码片都代表多维空间上的一个向量，它们互相垂直(就好比二维空间最多两个轴垂直，3维空间最多三个轴垂直，以此类推)，所以它们在传递信息的过程中互不干扰，维度越大(也就是码片序列的位数越多)，能同时支持的设备也就越多。
（3）很显然，每一个码片序列对自己的规格化内积为1，对自己反码的规格化内积为-1。比如

(

−

1

−

1

−

111

−

111

)

⋅

(

−

1

−

1

−

111

−

111

)

÷

8

=

1

,

(

−

1

−

1

−

111

−

111

)

⋅

(

111

−

1

−

11

−

1

−

1

)

÷

8

=

−

1

(-1-1-111-111)cdot(-1-1-111-111)div8=1,(-1-1-111-111)cdot(111-1-11-1-1)div8=-1

(−1−1−111−111)⋅(−1−1−111−111)÷8=1,(−1−1−111−111)⋅(111−1−11−1−1)÷8=−1。
（4）在信道上，分用器会把不同设备发过来的用码片序列表示的信息按照向量的加法加起来，形成混合向量。比如上面PPT里面S发出了1，T发出了0。至于向量的加法其实就是对应元素相加形成新的向量。
（5）只要接收方用发送方的码片和发送过来的混合向量做规格化内积，就可以解码出发送方的信息。这个原理很简单，但是需要一点点的线性代数基础，我们用T来表示码片序列：

T

混

=

T

发

+

T

其他

T_混=T_发+T_{其他}

T混​=T发​+T其他​，所以

T

发

⋅

T

混

=

T

发

⋅

T

发

+

T

发

⋅

T

其他

T_发cdot T_混=T_发cdot T_发+T_发cdot T_{其他}

T发​⋅T混​=T发​⋅T发​+T发​⋅T其他​，因为

T

发

T_发

T发​和其他码片都是正交的，规格化内积为0，而

T

发

⋅

T

发

T_发cdot T_发

T发​⋅T发​或者

T

发

⋅

T

发反

T_发cdot T_{发反}

T发​⋅T发反​为1或者-1，这样就可以完美的把信息过滤出来，而且有很强的保密性(因为别的设备不知道你的码片序列)。

那么至此，全部静态信道划分的方法就学完了，接下来我们学习动态的。

2.2 动态信道划分

动态信道划分的思想就是不提前分割信道，而是让用户可以随时随地想发就发，到时候在动态地划分，上面的统计时分复用技术就和动态有些类似。举个简单的例子，比如电视台的信号是一直在发送的，那么几个电视台就可以约好用频分还是时分还是码分来传数据。但是像是手机信号，你无法和几个人商议好大家什么时候一起打电话，所以需要动态的来解决。

2.2.1 ALOHA协议

ALOHA协议又分为两种，分别是纯ALOHA和时隙ALOHA(时隙这个词在时分多路复用讲过)。这个协议没有中文名词，因为本身就是夏威夷的地方方言。

2.2.1.1 纯ALOHA协议

纯ALOHA协议的思想就是想什么时候发送数据就什么时候发送数据。如图所示：

对于纯ALOHA协议而言，一个帧的大小不是用它的比特数来表示的，而是用其发送的时间来表示(从开始从主机进行信道到全部进入信道需要的时间)，如图上的T0。从图上可以看到，如果信道上同时存在两个信号，那么信号就会互相冲突，冲突的后果就是接收方在收到信号以后会发现信号出错了。纯ALOHA协议的解决办法就是让接收方发现信号出错的时候，将其丢弃，然后发送方有一个超时计时器，当计时器超时的时候没有收到接收方回复，则重传数据。当然，如果只是这样，那么显然冲突率是很高的，所以当计时器超时的时候，接收方不会立即重传，而是等一段时间(因为冲突说明当前信道忙碌)，这段时间是随机的，然后接收方会随机性地决定是否重传(就好比抛了一次硬币，正面就重传，反面就继续再等一段时间以后抛下一次硬币)。举个更直观的例子，你打电话给某人，结果他那边正在通话中，你一般不会立即再打一个，而是等一段时间以后思考一下是否再打一个。

2.2.1.2 时隙ALOHA协议

时隙ALOHA是对纯ALOHA的改进。如图：

它和纯ALOHA的区别在于，每一个设备都只能在某一个时间片发送数据，当出错以后也必须等待到下一个节点才能发送，并且时间片（也被称为时隙）大于设备的发送时间T0。这样改的优点就是，如果一台设备在发出的时候没有冲突，那么它的数据就会成功发送(因为其他的设备只能等下一个时间点才能发送)。如果出现了冲突，那么这两个设备也会等待一段随机时间后再重传，因为等待的时间是随机的，然后等待了一段随机时间以后发送的点又是规定好的，也就相当于两个设备大概率会等待不同的时隙再重传，所以比起上面的纯ALOHA协议，冲突的可能性也大大降低。所以时隙ALOHA协议的吞吐量更高。但是它的冲突率其实也不低。

2.2.2 CSMA协议

CSMA中文是载波监听多路访问协议，它和ALOHA不同之处在于，它发不发不是由设备来决定的，设备会预先监听一下当前信道里面有没有数据正在传输，有的话它就不发，没有它才发。
其中，CS就是监听的意思。其原理是设备会一直查看与其相连的数据线或者是当前空气中的信号值，具体表现为电压或者是电磁波是否存在较大波动，如果波动大就表明当前信道忙碌。
MA就是总线型的意思，这个需要先学习一下计组，和计组多个元件连接在同一个总线上一样，MA表示多个设备连接在同一个总线上。
在信道空闲时，发送数据的方法也可以分为三种：

2.2.2.1 1-坚持CSMA

1-坚持CSMA思想很简单，就是一旦监听到信道空闲，立马发送数据，信道忙的时候就一直监听，直到信道空闲。当发送的数据一直得不到回复时，会等待任意时间之后，在信道空闲的时候重发。这里说一下为什么有收不到回复的情况，这是因为对于CSMA协议而言，如果两个设备同时发送，还是会出现冲突(因为它们在上一秒都认为信道空闲)。

2.2.2.2 非坚持CSMA

这是对1-坚持CSMA的改进，它相比于CSMA在信道忙的时候一直监听，它在信道忙的时候会等待一个随机时间之后再监听，如果空闲就发送，如果还忙就再等一个随机时间。除了这里不同，其他和上面的1-坚持CSMA一样。相比之下，设备就不需要浪费很多不必要的时间在监听上面。同时，因为如果有两台以上的电脑都在信道忙的时候要发送数据，那么使用1-坚持CSMA它们就会同时发送造成冲突，然而非坚持CSMA中每一个设备等待时间不同，所以冲突率也会降低。

2.2.2.3 p-坚持CSMA

它是对上面两种CSMA的一种综合改进，有以下特点：
（1）信道是时隙信道，也就是说即便当前信道空闲，设备也只能在下一个时隙的时候发送数据。
（2）设备的传输协议是可控的，也就是p的值可以改变，当p=1的时候，设备使用1-坚持CSMA(但是依然使用时隙信道)，当p的值为小于1的值的时候:
【1】每一次发送前监听信道，如果忙就等待一个时隙之后再监听。
【2】如果当前信道空闲，也不会马上发送，而是有p的概率发送，如果这次没有发送，那么就再等一个时隙，再用p作为概率看是否发送。
这么说有些抽象，其实就是这样的，之前的非坚持CSMA是在信道忙以后等待任意的时间，但是这样随机性很大，于是我们就限制其时间只能是一个时隙，为了避免多个设备同时发送，于是可以让这个设备发送的概率是p，也就是每一次发送前都丢筛子，丢中了就发，没有丢中就再等一个时隙，然后监听，如果空闲就丢筛子，以此类推，直到发出去为止。这样即避免了潜在的冲突的可能性，还可以区分设备的重要性(重要的设备p值就大)。同时如果设备比较少，或者这个设备要发的信息比较重要，就把p设成1，则可以实现立即重发。所以p设成1是1-坚持CSMA不是其本意，而是恰好如此而以。再举一个可能错误的例子：百度网盘对用户发下载的数据用的就是p-坚持CSMA协议，普通用户的p值可能只有0.01，VIP有0.1，SVIP有0.5，这就能解释为什么不开会员下载那么慢了(因为现在这些协议多用于传输层进行端到端的控制，所以这确实是有可能的)。
虽然它既能像1坚持那样减少冲突，也能像非坚持那样让设备有空闲时间，但是它还是会有冲突的可能性(两个设备的随机时间相同，然后同时发送)，而且出现了冲突设备还是无法得知，会继续发送。于是又有了后面两种协议来改进。

最后对比一下它们三个：

2.2.3 CSMA-CD协议

其中的CD是碰撞检测的缩写，也就是说CSMA-CD协议可以做到一边发送数据，一边检测当前的数据是否和其他数据发生了冲突。如果冲突，则立即停止发送，避免不必要的浪费。检测冲突的方式是设备一边发送数据，一边检测当前信道的电压波动，存在除自己以外的波动则说明出现了冲突，这就要求该协议只能是半双工的通信，因为如果是全双工，那么对面在发消息设备也会认为是冲突。

2.2.3.1 争用期及其意义

这里要引出一个重要的概念：争用期。附上一张王道的PPT进行讲解：

如图，我们假设A主机和B主机因为同时向对方发送消息导致了碰撞。假设设备间的单程传播时延是

τ

tau

τ，要求设备A最多多久可以知道发生了碰撞。我们一步步来：
（1）我们假设B的发送时间是

τ

−

δ

tau-delta

τ−δ。为什么要这样假设呢，这是因为图上的时间轴是向下的，我们以A发送出数据的时间为坐标原点，那么A的信息经过

τ

tau

τ的时间传递到B，如果B和A发生了冲突，那么B发送信息的时间就一定要大于等于0，且小于

τ

tau

τ(这里不考虑B比A先发送信息的情况，因为如果是B先发信息，那么把当前情况对调即可)，所以我们假设的是在A发送消息之后，经过

τ

−

δ

tau-delta

τ−δ的时间，B也发出了信息，显然

0

≤

δ

<

τ

0leqdelta<tau

0≤δ<τ（带入上面的结论就行）。
（2）因为B会在时间点为

τ

tau

τ的时候收到A发来的信号，这个时候它就会知道发生了碰撞。因为电磁波的传递速度是一样的，所以从B发送消息到A和B碰撞的时间，应该和AB发生碰撞的时间到B知道的碰撞的时间相同，所以图上应该是一个等腰三角形(如果还是理解不了，可以试想一下生活中的例子：你和妻子的步行速度是一样的，你出门散步，走了100米遇到了你的妻子，她正好要回家，那么她回家是不是也要走100米，你们的速度是一样的，所以她走回家这一百米用的时间也是一样的)。所以B在

τ

−

δ

tau-delta

τ−δ的时间发送数据，在时间点为

τ

tau

τ的时候知道了碰撞，那么碰撞的时间节点在

τ

−

δ

2

tau-frac{delta}{2}

τ−2δ​。同时，我们还可以知道B需要

δ

delta

δ的时间从发出到知晓发生了碰撞。
（3）对于A而言，它需要收到B的信息才能知道发生了碰撞(才检测得到信道电压的波动)。所以可以直接计算B发送的消息传递到A需要的时间，也就是

τ

−

δ

+

τ

=

2

τ

−

δ

tau-delta+tau=2tau-delta

τ−δ+τ=2τ−δ。因为A是从0开始发数据，所以A需要

2

τ

−

δ

2tau-delta

2τ−δ的时间才能知道发生了碰撞。
（4）因为

0

≤

δ

<

τ

0leqdelta<tau

0≤δ<τ，所以当

δ

=

0

delta=0

δ=0(这里等于是无限趋近的意思)的时候，A知道发生了碰撞的时间最大，是

2

τ

2tau

2τ。正好是总线端到端的往返时延。
所以在CSMA-CD协议中，设备间在总线(也就是信道)上的端到端往返时延还代表了设备发现冲突所需要的最大时间，所以也把这段时间称为争用期，冲突窗口或者是碰撞窗口。也就是说，设备在发出信息之后就会开始计时，并且一直检测当前的信道电压，如果出现了电压波动，且距离开始发送要小于等于

2

τ

2tau

2τ的时间，那么说明前面发生的信息都碰撞了，设备会停止发送数据，过一段随机时间后再重发(这一点和前面的CSMA协议是类似的)。这就是争用期的意义所在，它能告诉我们是否发生了碰撞，同样的，信息发出去

2

τ

2tau

2τ之后还没有碰撞，那么就说明信息没有问题，设备可以把当前滑动窗口的数据备份删除，窗口右移。

2.2.3.2 截断二进制指数规避算法

相比于前面的CSMA重传等待的时间是完全随机的，CSMA-CD协议有更完善的做法，那就是用截断二进制指数规避算法来决定碰撞之后什么时候重传，这个算法分为这么几步：
（1）设备一开始就会确认争用期(

2

τ

2tau

2τ)是多少(发一个小数据，看往返时间)，争用期在这个算法里面也被称为基本退避时间。
（2）定义两个计数器，k和m。当重传之后k和m就会同时加1，也就是说k和m同时记录了当前的重传次数，区别是k不能大于10，最多只能等于10(至于为什么看第三条)。
（3）设备重传需要等待的时间是：从[

0

,

2

0

,

2

1

.

.

.

(

2

k

−

1

)

0,2^0,2^1… (2^k-1)

0,20,21…(2k−1)]之间随机取出的一个数字r，用r*

2

τ

2tau

2τ就是需要等待的时间，也就是说，重传等待的时间是r倍的基本退避时间。其实仔细推敲一下，我们可以发现一开始k=0,所以设备最多等个

2

τ

2tau

2τ就发送数据了，但是随着k的增大，设备有可能等的时间就越来越长。当k大于10的时候，用户的设备就有可能等很长很长时间，所以k不能大于10，也就是r最多等于1023。这里还需要注意的一点是，取值的范围最后是

2

k

−

1

2^k-1

2k−1,而不是

2

k

2^k

2k，做题的时候不能粗心。
（4）最后，m最大值为16，也就是当m=16的时候，设备会向用户表示当前网络繁忙，请稍后尝试，或者让用户检查网络连接。所以当重传16次之后，设备就不会继续自动重传，除非人为干预。
因重传的越多，等待时间的可选项也就越多，而且每一次等待的时间都是争用期的倍数，那么即便是多个设备同时碰撞，它们在多次重传之后还碰撞的可能性就会大大降低，这就是截断二进制指数规避算法的优点。

2.2.3.3 最小帧长

为了进一步发挥这个协议的作用，不浪费信道，所以CSMA-CD协议还规定了一个最小的帧长。也就是设备要完整发送这个帧的时间需要大于争用期，否则争用期没有结束，帧就发送完毕了，则检测到碰撞也不存在及时停止发送的说法，那么就退化成非坚持CSMA了(而且等待的随机时间更长，所以性能还不如非坚持CSMA)。用书面语表示就是帧的传输时延需要两倍于信号在总线中的传播时延，即：

帧长

设备的数据传输速率

≥

2

τ

frac{帧长}{设备的数据传输速率}ge 2tau

设备的数据传输速率帧长​≥2τ
可以解出：

最小帧长

=

总线的传输速率

(

τ

)

×

设备的传输速率

×

2

最小帧长=总线的传输速率(tau)times 设备的传输速率times 2

最小帧长=总线的传输速率(τ)×设备的传输速率×2。

2.2.3 CSMA-CA协议

CA是碰撞避免的意思，所以CSMA-CA便是载波监听多点接入/碰撞避免协议。就目前而言，CA协议更广泛的应用于我们日常生活中，这是因为CD协议的碰撞检测需要检测当前的信道电压波动，而我们日常生活中的无线网络一直在波动，使用CD协议的话根本发送不了任何数据。所以CD协议适用于设备之间直接连接的有线网络，而无线网络通信还得要CA协议来。
CA既然表示碰撞避免，顾名思义，其核心思想就是在发送前避免碰撞，而不是一直检测当前是否发生了碰撞。

2.2.3.1 CSMA-CA协议的具体内容

分为以下几点：
（1）设备在每次发送数据前，都会检测当前信道是否空闲，这和之前的几种CSMA一致。
（2）如果当前信道空闲，设备会先发送一个RTS帧，这个RTS包括了发送端和接收端的地址，以及即将发送的数据将要持续大约多少时间。如果信道繁忙则等待一段随机时间之后再检测一下信道(和前面的非坚持CSMA类似)。
（3）接收端收到RTS之后，会立即返回一个回复CTS。这样两个设备之间就会建立一个连接。这个时候如果其他设备向接收方发送新的RTS，接收方就会全部拒收，那么其他的设备就需要等待一段时间才会重复RTS，在这段时间内，一开始的发送方和接收方就是独享信道的。
（4）因为无线网络的信号几乎是广播的，所以RTS和CTS的信息所有站点都会收到，这些其他站点会根据里面的发送时长来确定自己要等多久。就好比大家一起抽奖，可以抽很多次，但是每次只有一个人中将，中将的那个人领奖需要一段时间，你如果没有中将，那么你只需要等待中将者领奖结束以后继续去抽奖即可。这种让其他站点了解信道需要被占用多久的方法也被称为信道预约。
（5）然而，上面这四步只能避免其他准备发送给接收方的设备发送的信息不会和发送方发生碰撞，还是无法避免其他设备之间的通信，甚至是接收方给发送方发的数据也会和发送方数据碰撞，所以碰撞还是时常会有。当碰撞发生时，还是采用二进制指数退避算法来等一段时间再重发。
（6）CSMA-CA检测碰撞的方式不是看

2

τ

2tau

2τ时间内是否有数据传过来，而是让接收方去检测数据是否出错(前面学的CRC检验)。如果没有错，接收方会返回一个ACK，如果出错，则不反回任何信息，发送方在计时器超时的时候就会知道发生了碰撞。

2.2.3.2 CSMA-CD和CSMA-CA两种协议的区别

直接看PPT即可：

2.3 轮询访问介质访问控制

轮询访问介质访问控制是在静态访问信道划分和动态信道访问划分外的第三种介质访问控制方法。它也被称为轮询访问MAC协议，轮流协议，轮转访问MAC协议等。

2.3.1 为什么需要这么一种额外的方法

（1）静态访问的方法好处是在设备都很忙的时候，信道利用率高，且公平，关键是不会产生信号的冲突。但是一旦有些设备空闲，信道的利用率就会下降，而且这个时候即使有些设备依然忙碌，但是信道也无法有效被利用。所以现实情况是静态访问的信道利用率一直不高（因为你很难保证全部设备都忙碌）。
（2）动态信道划分的优缺点和静态信道划分正好相反。它信道利用率很高，但是它时常发生冲突导致信息的传递效率不高。这里要注意的是，在三大类协议里面，只有它会产生冲突。
于是就出现了轮询访问介质访问控制，来平衡二者的优缺点。 它的目标就是在不产生冲突的情况下占用全部带宽。它的协议有很多，但是考试只考我们接下来讲的这两种。

2.3.2 轮询协议

这是最简单的一个协议，如图：

很多宾馆的网络结构都是这样的，有一个主设备(不一定是电脑)，它负责和外部进行通信，然后一个局域网里面的设备都和它连接。这个主设备会轮流的询问每一个设备是否需要发信息，如果设备表示需要，则就发送数据，其他设备不能动，如果被询问的设备不需要，则主设备就去询问下一个设备，这样依次循环。所以，如果一个宾馆人很多，我们会发现有时候手机有信号有时候没有，而且还挺有规律。
这种方式有三大问题：
1.轮询开销：轮询开销就是指主设备给每一个从设备发送询问帧和从设备给主设备返回一个确认帧需要时间。
2.等待延迟：等待延迟就是如果排序较后的设备需要使用信道，但是排前的设备都不需要，这个时候需要的设备还是得等待主设备一个个全部询问过来。
3.单点故障：主设备坏了，全部设备都无法发数据了。所以实际上会有一些备用主节点，它们会监视主设备，当主设备不问了，它们立即开始询问，并且向上层报错。

这个协议在负载小，通信量不大的环境中还是挺好用的，比如家庭网络。

2.3.3 令牌传递协议

这是目前的一个主要考点，具体过程如图所示，就和丢手绢游戏一样：

这个协议的特点是：
（1）令牌：它是一个特殊的MAC控制帧，不包含任何信息。(这里把MAC理解为设备的编号即可，后面会细讲什么是MAC地址)。拥有令牌的设备才能发信息。
（2）每一个设备都有一个TCU接口，这个接口可以把令牌转发给下一个设备，这样只需要有一个设备发出令牌，然后大家就可以轮流使用，就省去了询问和回复的时间。
（3）就像图上那样，当一台设备不需要使用信道还持有令牌的时候，它就会把令牌转发给下一台设备，形成循环。而且，TCU接口间转发令牌的速度还挺快，这就大大减少了轮询开销和等待延迟。
（4）令牌上面的一个标志位代表这个令牌是否空闲，令牌本身就可以作为帧首部加一堆要发送的数据 ，这样当其他的设备收到了令牌，如果令牌是忙碌的(空闲标志位为0)，也会忽视这个令牌。
（5）每一个设备都只能持有令牌一段时间，时间到了就只能停止发送数据，把令牌传给下一个设备。这样就避免了盲等待。

令牌传递协议还是存在几个问题：
（1）令牌开销：令牌的传递需要时间，令牌的的生成也会需要时间(一般为了防止出错，每一个拿到令牌的设备都会用CRC检查一下当前令牌，出错的话要重新生成)。
（2）等待延迟：虽然比轮流询问更少，但是还是有。
（3）单点故障：每一个设备都需要备用机，用于防止某一个设备坏了，不传递令牌。

这种协议常用于负载量大(设备多)，通信量大的环境中，而且设备间常组成星型或者逻辑环形拓扑结构。至于为什么，其实就是因为如果设备较多，那么令牌一直传总是有设备需要的，但是设备简单，大家都不发数据，那么令牌的传递就没有意义，TCU接口还需要额外的硬件。设备少的情况下，用简单轮询访问显然更好。