计算机网络（三）———数据链路层（w字最强总结）

秋名山码神

发布于 2022-12-13 14:59:37

5320

发布于 2022-12-13 14:59:37

文章被收录于专栏：码神随笔

📢目录

前言

计算机网络，操作系统，数据结构，算法是计算机专业所必须要学的4件套，本文将详细的叙述计算机网络——数据链路层和网络层的相关知识，由于篇幅原因，打算分为4章节进行写作，建议收藏后慢慢品读

😁往期推荐：计算机网络(一)——概述计算机网络（二）——物理层

数据链路层

基本概念

结点：主机和路由器
链路：网络中俩个结点之间的物理通道，链路的传输介质主要有双绞线，光纤和微波，分为有线链路，和无线链路
数据链路：网络中俩个结点的逻辑通道
帧：链路层的协议数据单元，封装网络层数据报

数据链路负责通过一条链路从一个结点向另一个物理链路直接相邻结点传送数据报

功能

数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。

透明传输

指：不管传输数据时社么样的比特组合，都应当在链路上传送。因此，链路层就看不见有社么妨碍数据传输的东西

当所传数据中的比特组合恰好与某个控制信息完全一样的时候，就必须采取措施，使得接受方，不会将这样的数据误认为是某种控制信息，这样才能保证数据链路层的传输是透明的

封装成帧

封装成帧就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。

首部和尾部包含许多的控制信息，他们的一个重要作用:帧定界(确定帧的界限)。帧同步:接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。

为了提高传输速率，应该数据部分应该尽可能的提高，也就是说大于帧的首部和尾部

组帧的四种方法: 1.字符计数法，2.字符(节)填充法，3.零比特填充法，4.违规编码法。

下面我们说一下这4种方法：

字符计数法

痛点：当一个出错时候，都出错

字符(节)填充法

那么社么时候使用字节填充法呢？试想一下，当数据帧中也出现了EOT的时候

既当传送的帧是由非ASCLL码的文本文件（二进制代码或图像等）就要采用字符填充的方法实现透明传输

实现过程

主要就是在控制字符前添加转义字符，在接收端删除转义字符

零比特填充法

也就是说，在发送端，扫描整个信息字段，只要有5个1，就填充一个0， 在接收端收到一个帧的时候，先找到标志字段确定边界，在用硬件对比比特流进行扫描，发现5个1，就删除后面的0 保证了透明传输：在发送的比特流中可以传送任意的比特组合，不会引发对帧边界的判断错误

违规编码法

可以用高 -高 ，低低来界定帧的起始和终止

由于字节计数法中Count字段的脆弱性，及字符填充实现上的复杂性和不兼容性，目前较普遍的帧同步法是比特填充和违规编码法

差错控制

上面我们说了，在传输过程中可能出现数据差错，目前差错主要从噪声引起

全局性：由于链路本身电气特性所产生的随机噪声，是信道固有的，随机存在的，解决：提高信噪比来减少干扰 局部性：外界特定的短暂原因造成的冲击噪声，产生差错的主要原因，解决通常利用编码技术来解决

检测编码只能检查错误，纠错编码可以纠正错误

物理层编码：单个比特数据链路层：一组比特

CRC循环冗余校验

把收到的每一个帧都除以同样的除数，然后检查得到的余数R。

余数为0，判定这个帧没有差错，接受。
余数为不为0，判定这个帧有差错(无法确定到位)，丢弃。

凡是接收端数据链路层接收的帧均无差错

纠错编码

海明码发现双比特错，纠正单比特错。。动一发，而牵全身

工作流程：

1：解释一下汉明不等式的原因 2：r位冗余位的组合共有2^r种 3：选择2^r种组合中的一种用于表示数据正确 4：其余的2^r-1种组合用于表示编码中产生一位错误 5：已知信息分组长度，代入不等式，则可以计算出所需要的冗余信息位数

海明码详解

流量控制与可靠传输机制

流量控制

也就是说，如果较高的发送速度与较低的接收能力不匹配，或会导致传输出错

链路层流量控制：点对点，传输层流量控制：端对端

数据链路层流量控制手段：接收方收不下就不回复确认传输层：接收端给发送端一个窗口公告

流量控制方法

停止等待协议：每发送完一个帧就停止发送，等待对方的确认（导致效率低），在收到确认后再发送下一个帧

滑动窗口协议

发送窗口有多个，当确认一个帧以后，才往前走

三个协议的不同：

停止等待协议

出了比特出差错，底层信道还会出现丢包问题，为了实现流量控制

虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据(发送方)，一方接收数据(接收方)。因为是在讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传送的。 “停止-等待”就是每发送完一个分组就停止发送，等待对下方确认，在收到确认后再发送下一个分组。

主要有俩种应用情况：无差错&有差错情况

无差错

有差错

信道利用率（低）

信道利用率：发送方在一个发送周期内，有效的发送数据所需实际占整个发送周期的比率。

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

选择重传协议（SR）

停等协议，会一直等待，等待就会浪费，效率低，

我们想要发送完一个，再发送一个，然后再发送一个

必须增加序号范围
发送方需要缓存多个分组

有俩种解决方式：后退N帧协议GBN，选择重传协议（SR）

SR发送方必须响应的三件事

上层调用从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送帧，否则像GBN一样，要么将数据缓存，要么返回给上层后再传输
收到了一个ACK 如果收到ACK，加入该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收，如果该帧序号是窗口的下界，则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了，并且有序号在窗口内未发送帧，则发送这些帧
超时当超时后只重新发送一个帧

SR接收方

来者不拒 SR接收方将确认一个正确接收的帧而不管其是否按序，失序的帧将被缓存，并返回给发送方一个该帧的确认帧（收谁确认谁），直到所有帧都被接收到为止，这时才能将一批帧按顺序交付给上层，然后向前移动滑动窗口

运行中的SR

假设发送窗口和接收窗口尺寸都是4

当2号帧确认后，发送窗口往前移动

窗口长度

窗口长度可以无限吗？

一般来说发送窗口最好等于接收窗口（大了会溢出，小了没有意义）

后退N帧协议

后退 N 帧协议滑动窗口 :

① 发送窗口 : 发送方维持的一组连续的允许发送的帧序号 ; ( 本质是序号 ) , 可以有多个 ;

② 接收窗口 : 接收方维持的一组连续的允许接受的帧序号 ; ( 本质是序号 ) , 只有 1 11 个 ;

GBN发送方必须响应的三件事

上层的调用上层要发送数据时，发送方先检查发送窗口是否已满，如果果未满，则产生一个帧并将其发送;如果窗口已满，发送方只需将数据返回给上层，暗示上层窗口已满。上层等等一会再发送。(实际实现中，发送方可以缓存这些数据，窗口不满时再发送帧)。
收到了一个ACK GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到n号帧和它之前的全部帧。
超时事件办议的名字为后退N帧/回退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现走绍时，发送方重传所有已发送但未被确认的帧。

GBN接收方要做的事情

如果正确收到N号帧，并且按序，那么接收方为n帧发送一个ACK，并将该帧中的数据部分交付给上层其余情况都丢弃帧，并为最近按序接收的帧重新发送ACK，接收方无需缓存任何失序帧，只需要维护一个信息：下一个按序接收的帧序号

运行中的GB N

当2号帧超时后，重新发送2号帧，包括3，4，5号帧都需要重新发送

GBN重点

累积确认
接收方只按顺序接收帧，不按序的无情丢弃
确认顺序号最大的，按序到达的帧
发送窗口最大的为2^n-1,接收窗口大小为1

信道划分介质访问控制

点对点链路

俩个相邻节点通过一个链路相连，没有第三者应用：ppp协议，常用于广域网 例如：电话

广播式链路

所有主机共享通信介质应用：早期的总线以太网，无线局域网，常用于局域网

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

星型总线型

介质访问控制

采取一定的措施，使得俩对节点之间的通信不会发生相互干扰的情况

频分多路复用FDM

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

时分多路复用TDM

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

TDM帧标志是一个周期

频分复用：“并行” 时分复用：“并发”

波分多路复用WDM

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

码分多路复用CDM

码分多址（CDMA）是码分复用的一种方式 1个比特分为多个码片/芯片，每个站点被指定一个唯一的m位芯片序列发送1时站点发送芯片序列，发送0时发送芯片序列反码（通常把0写成-1）

如何不打架：多个站点同时发送数据的时候，要求各个站点芯片序列相互正交如何合并：各路数据在信道中被线性相加如何分离：合并的数据和源站规格化内积

随机访问介质访问控制

ALOHA协议

有个故事，说是有个人去夏威夷要解决通信问题发明了ALOHA协议，ALOHA在夏威夷语中是“你好”的意思

纯ALOHA协议思想：不监听信道，不按时间槽发送，随机重发（想发就发）

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

解决：超时后等一随机时间再次发送

时隙ALOHA协议

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

控制想发就发的随意性

CSMA协议

CS：载波监听，在每一个站在发送数据前都要检测一下总线上是否有其他计算机在发送数据 MA：多点接入，表示多计算机以多点接入的方式接如的方式连接在一根线上思想：发送帧前，监听信道

1.坚持CSMA

如果一个主机要发送消息，那么它先监听信道。 空闲则直接传输，不必等待。 忙则一直监听，直到空闲马上传输。如果有冲突(一段时间内未收到肯定回复)，则等待一个随材机长的时间再监听，重复上述过程

非坚持CSMA

非坚持就是对于监听信道忙之后就不要继续监听非坚持的CSMA思想：如果一个主机要发送消息，那么他先监听信道 空闲则直接传输，不等待 忙则等待一个随机的时间之后再进行监听

优点：采用随机的重发延迟时间可以减少冲突发生的可能性缺点：可能存在大家都再延迟等待的过程中，是得媒体仍可能处于空闲的状态，媒体使用率低

p-坚持CSMA

p-指的是对于监听信道空闲的处理 p-坚持CSMA思想：如果一个主机要发送信息，那么它先监听信道 空闲则以p概率直接传输，不必等待，概率1-p等待到下一个时间槽再传输 忙则等待一个随机的时间之后再进行监听

优点：既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间

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

轮询访问介质控制

信道划分介质访问控制（MAC）协议基于多路复用技术划分资源 网络负载重：共享信道效率高，公平网络负载轻：共享信道效率低

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

轮询访问MAC协议：既要不产生冲突，又要发送时占全部带宽

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

轮询开销
等待延迟
单点故障

令牌传递协议

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

令牌环网无碰撞

问题：

令牌开销
等待延迟
单点故障

CSMA/CA协议

局域网基本概念

局域网(Local Area Network):简称LAN，是指在某一区域为由多台计算机互联成的计算机组，使用广播信道。

特点1:覆盖的地理范围较小，只在一个相对独立的局部范围围内联，如一座或集中的建筑群内。特点2:使用专门铺设的传输介质(双绞线、同轴电缆)进行行联网，数据传输速率高(10Mb/s~10Gb/s)。特点3:通信延迟时间短，误码率低，可靠性较高。特点4:各站为平等关系，共享传输信道。特点5:多采用分布式控制和广播式通信，能进行广播和组技播。决定局域网的主要要素为:网络拓扑，传输介质与介质访问控制方法。

网络拓扑