计算机网络 CH3
计算机网络 CH3： 链路层
CRC校验的方法很重要！
3.1 数据链路层概述
首先掌握链路的概念：
要记住链路需要中间没有其他节点 
可以理解为：数据链路=链路+相应的协议 网卡实现了相应的协议，包含了物理层和数据链路层的功能 
Frame是基本通信单元，以帧为单位进行数据传输 为了简化考虑，这里抽象成只在链路层之间进行数据传输，不考虑其他层
3.2 数据链路层的三个重要问题
3.2.1 封装成帧和透明传输
从上层传下来到链路层的数据，需要加上首部和尾部进行封装之后进行传输；我们要求实现数据链路层对于上层的数据没有要求，也就是即使数据载荷里包含了链路层封装的头部或者尾部，也不会使得对于帧的总体进行误判。如图所示 
详细的解释：首先思考这样的问题：数据本质上是会通过物理层进行传输的，那么数据链路层怎么知道这些传输的0/1比特帧是如何划分的？这就需要帧的首部和尾部进行帧定界
比如说，这里采取一个byte的01111110进行定界
另外一种方式没有帧定界，而是采用前导码+帧间间隔进行区分
显然，帧中的有效数据越多传输效率会越高，但是所有数据链路需要规定最大传送单元：需要记忆：以太网的MTU为1500byte
对于透明传输，解决方法是在主数据段，对于和首尾部一样的内容，在前面插入一个转义字符（escape）
这样接收方读到转义字符，就可以判断其为正文；同样地；如果正文内容中有转义字符esc，那么在其前面再加一个essc就可以区分。
另外一种方法是比特填充：以我前后的flag为01111110为例，我们直接确保数据内容不会与这个重复，因此我们在数据中，如果连续出现五个1，就在后面插入一个0。接收方接收到数据之后，还原的过程也很简单：每次遇到五个1之后，就删掉一个后面跟着的0，这样一定可以恢复到原始数据。关于这个部分的一个总结性例子：
3.2.2 差错检测
如何知道传输的数据中是否有出错？
大致的方法是，在帧的尾部加上一个检错码
3.2.2.1 误码的相关概念
比特在传输过程中可能出现的差错称为比特错误，
使用差错检测技术来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一。
主要的检测方法是通过检错码（fcs）进行检测：接收端通过按照相同的方法生成这个检错码，如果最终生成的结果不同，说明数据出错。
3.2.2.2 奇偶校验
一种最基础的方法就是奇偶校验：
无论是数据还是校验位出错，均可以检测出来 但是显然，只能检验出出现奇数位误码的情况
3.2.2.3 CRC校验（循环冗余校验）
这是实际中广为使用的方法，基本思想如下：
发送方和接收方采取的操作如下：
总的来说计算过程如下： 1. 传输的数据+多项式的次数个0，作为被除数 2. 对于多项式，对应的项分别填1和0，作为除数 3. 循环进行二进制的除法计算（实际上进行异或操作），得到商和余数 4. 在余数前面补0，使得最终长度与多项式次数相同，得到结果 如图所示：
CRC校验可以很好地判断是否出错，但是对于错误位置无法判断；下面介绍的海明码方法用于确认位置，提供了一位的纠错能力
总的来说，海明码的方法实际上就是结合了多个奇偶校验综合使用的方法：比如说一共有n个数据位，我们使用k位校验位，使得2k可以涵盖n+k所有的位置；这个时候，我们数据的第1，2，4，8，…位均为校验位。对于这些校验位，将其转化为二进制，之后每一个校验数会负责整个序列中，转化为二进制编号第t位为1的这些位。
确定位置的方法：
可以看到，把它列成一个类似于表格的内容之后，可以通过不同校验位的检测来确定错误可能出现在哪些行或者列；最后去交集就可以定位。
3.2.3 可靠传输
也就是说，发送方保证发送正确的信息，如果接收端收到错误，要求重传；这个部分的核心就是重传机制
根据前面的知识：我们可以采用3.2.2中的差错检验技术检查出传输来的某一个帧中是否有错误；
有限链路的误码率比较低；而无线链路的误码率比较高，必须提供可靠传输服务。
在这个部分，我们使用“分组”的概念来代替之前提到的帧的概念，因为这个部分的内容不仅仅是针对数据链路层的，对于别的部分也适用。
传输差错的主要原因和类别如下：
3.2.3.2 停止-等待协议的实现原理
基本的思想是这样的： 这样可以解决掉误码的情况。但是，对于发送数据丢失的情况不好处理，这时候需要设置一个timer：
也就是说，超过一段时间没有收到反馈的话，就重新传输一下数据
然而这个时候，如果我的问题是接收方发送的反馈丢失，就会重复录入数据：
一种简单的解决方法是，我不断对于数据进行0/1编号，这样接收方可以判断数据是否重复并且删掉重复的数据
更进一步地，如果发生了ack迟到的情况，会导致发送方无法判断ack是对于哪一个数据而言的；因此针对这样的情况，有时需要对于ack也加上一个编号（但是在实际上，由于ack携带的信息非常少，这个编号也并不必要）对于所有数据的设置，如下所示：
总结一下：由于这个设置的特点，在引入重传之后就可以不用nck，直接实现一个发送方一旦超时，就自动进行重传的情况。
3.2.3.3 停止-等待协议的信道利用率
其中，RTT位发送最后一个分组的数据到接收到ack回馈的间隔时间。 因此，由于只有TD的时间我的信道是被有效利用的，而RTT时间在不同链路差距很大
在很多情况下，信道利用率会比较低。
3.2.3.4 回退N帧协议
主要的思想是，之前是发一个等一个反馈，现在想做的是一次性发送多个数据，采用流水线的传输方式管理数据
这个协议的核心是发送方和接收方各自维护一个窗口
如图所示，发送方维护一个序号0到2n − 1，同时双方各自维护一个窗口（发送方窗口大小小于编号，接收方必须是1）之后，发送方一次发送一组数据，接收方一个一个接收；没问题了之后，发送方接收到所有ack之后，就可以开始发送下一个组数据了。
有误码的情况：
比如说data2有误码，这时候窗口到了data2之后会无法ack，之后接收方无论接收到哪一个帧，都会卡在ACK1无法向前；之后会一直到第二个帧超时为止，会重新传一组数据（具体看ppt）
以及一个采用的累计确认的方式：
也就是说，收到ack n就会确认n以前的所有帧
一个例子：
这个例子说，累计确认的时候，比如说收到了3号帧的确认，说明03顺利接受，而47均没有接收到；这个时候超市，就需要发411的帧，而这其中47是属于重新发的。
3.2.3.5 选择重传协议
选择重传协议抛弃了累计确认的方法，而是采用对于数据逐个确认；同时，接收方的窗口也不是只有一个，需要满足如下的条件：
需要注意，如果两个加起来比2n更大，这显然会导致前一轮的帧和后一轮的帧前面的序号重复的问题，无法分辨。 
选择重传协议是最正常的，也就是说每次谁不合格，谁超时就会在发送方超时，这样发送方只要重传超时的这些帧就可以了。对于两个窗口，都是窗口内的内容全部确认之后，才可以向前滑动。
3.3 点对点协议（ppp）
这个部分没有这么重要，考试不一定考，了解即可
3.3.1 点对点协议PPP概述
在整个结构中的位置如下 核心概念：点对点的广域网链路层协议
3.3.2 PPP的帧格式
大概为这样的一个数据结构，根据协议的值不同里面的数据就不同
对于实现字节的透明传输，针对同步和异步两种情况有如下实现：
或者
这部分内容确实没啥，也不太重要
3.4 共享式以太网
3.4.1 网络适配器和MAC地址
要让计算机连接到以太网，就需要网络适配器，也就是常说的网卡 
复习一下前面说的传输方式
另外，驱动程序可以使网卡正常工作，驱动程序负责驱动网卡发送和接收帧
- mac地址
显然，广播的时候需要使用mac地址来区分不同的主机；在发送的时候，每一个主机都会收到帧，这时候mac地址就可以区分是不是发给自己的
也被称为硬件地址、物理地址 
mac地址的表示方法如下：
其中，mac地址的第一字节的b0 和 b1位有如下的四种区分：
对于这个的传输方式，有如下的说明： 
也就是说，可以简单理解为这是三种接收广播信息的不同取舍方式。
3.4.2 CSMA/CD协议
3.4.2.1 CSMA/CD协议基本原理
基本背景就是，由于早期的ethernet都是采用有线总线的方式进行传输，这个时候由于多个站点都连接在一条总线上，这时候不管采用什么传输方式，都会像广播一样所有站点都会收到信息。这时候，如果两个站点同时发送信息，就会导致信号碰撞。因此：
具体的基本原理如下：
主要是“先听后说”以及检测到碰撞就停止发送退避的机制。
3.4.2.2 共享式以太网的争用期
主要的计算原理如下：
也就是说，由于经过时间τ之后，设备D一定可以检测到总线被占用，那么在这个时间点前一点的时候D发送帧，这之后发生碰撞的信号返回A的时候的总体时延会最大。因此，当D发送时间距离τ的差距δ很小的时候，最大的碰撞窗口为2τ
3.4.2.3 共享式以太网的最小帧长和最大帧长
为什么会需要这个所谓的最小和最大帧长的概念？比如说我的帧很短，那么我在发送的过程中，如果我发送过程中没有检测到碰撞但是发送完成之后出现碰撞，这样一来发送端会以为已经发送成功，但是事实上因为冲突这个帧无法被接收到。如图所示：
因此：
也就是说，需要至少达到一个争用期，这样就可以排除传输过程中路上可能碰到的所有碰撞。
这个的逻辑相当于：经过2τ时间，当前帧（或者，前64字节）一定会已经在整个网络中“充满”了；这个时候，其他网点检测到的一定是有信息在传输，因此也不会发送信息。
但是很显然，如果我的帧太长，肯定也会带来相应的问题：
对于帧的最长长度，也有相应的规定
3.4.2.4 共享式以太网的退避算法
这个方法指的是，会从中随机选择一个时间，在检测到冲突之后退避一段时间，然后再从先听86bit时间开始。
3.4.2.5 共享式以太网的信道利用率
最大的利用率就是指，所有时间都在有效使用网络。为了提高利用率：
3.4.3 使用集线器的共享式以太网
使用集线器的以太网如图所示，实际上虽然长得像星型图，但是实际的运转逻辑是和总线型的是一样的，仍然使用CSMA/CD协议，会发生相应的碰撞等等 这部分应该记住这个10BASE-T标准就可以了
3.4.4 在物理层扩展以太网
使用集线器、光纤等等设备，可以扩展站点之间的距离
使用主干集线器可以增大总站点数量，但是会扩大碰撞域
3.4.5 在数据链路层扩展以太网
网桥（bridge）工作在数据链路层，不会扩大
3.6 以太网的MAC帧协议
这里以以下的这个协议的标准为例：
FCS是通过使用CRC协议检测前面这些内容生成的校验码，可以知道是否出错 以及
3.7 虚拟局域网
在使用交换机进行连接的交换是局域网中，有一个问题就是没有隔离广播的地址，会有一个巨大的广播域；也就是说，一个pc广播所有设备都要接受，许多终端接收到了不必要的信息。
大体来说，虚拟局域网做的是把这些pc划分成了不同的部门（也就是vlan），这样同一个vlan下的pc可以相互通信，但是不同vlan的就被分开了 
事实上，对于vlan的划分与你连接在哪一个交换机是实际上无关的。
vlan实现的原理：其会在一个帧原来的格式里插入一个字段（tag）这个vlan标签的具体结构如下：
最重要的就是vid规定的这个vlan编号，根据这个编号广播帧只会在同一个vlan中进行转发。 对于vlan标签的操作，是通过交换机对于pc发来的帧进行打标签和删除标签来实现的。 access端口和trunk端口的区别：trunk端口可以支持多个vlan的转发，access端口只能转发并且标记一个接口。也就是相当于，access端口只能“通过”特定的一种广播帧，但是trunk接口无论其自身的vlan是什么，所有的vlan类型的帧都可以通过。
3.8 802.11无线局域网
在这个结构中，所有传输信息都需要通过AP来进行转发；这里的接入点AP会分配一个名字（也就是wifi的名字）
下面的一个重点是无线局域网使用的一个协议： 
这个协议和之前的 CSMA/CD 协议很类似，都是采用先监听后发送信号的方式；这里面后面写的CA代表着collision avoidance，也就是（尽量要做到）冲突避免
其主要工作流程如下：每次先等待一段时间，之后当发送开始了之后，维护一个时间窗口，这个窗口里包含发送帧的时间以及后续的等待ack的时间。之后，当信道空闲的时候，需要根据退避算法随机等待一个时间，再等待一个DIFS，然后让另一个设备发送（否则，比如说我同时有多个设备在监听，没有随即等待时间的话就会几乎同时发送） 
一般来说，在CSMA/CA中，还会采用一个预约的机制：
这个相当于先去试探了一下
3.8.5 802.11无线局域网的MAC帧
根据这个网络的工作原理，其中的帧分为以下的三种类型：