计算机网络——第三章 数据链路层
本帖最后由 dingallen216 于 2021-8-27 17:45 编辑本文属于是计算机考研408的笔记，记录的都是关键性的浓缩知识点，方便复习也方便记忆。计网统共六章，分为六篇文章，希望能保证1-2天更新一篇的更新速度。
数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
数据链路层的功能：
[*]为网络层提供服务；
[*]链路管理；
[*]组帧；
[*]流量控制；
[*]差错控制（帧错/位错）。
封装成帧
封装成帧就是在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。首部和尾部包含许多的控制信息，他们的一个重要作用：帧定界（确定帧的界限）。
帧同步：接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。
组帧的四种方法：
[*]字符计数法：每个帧都利用第一个计数字段来表明当前帧的长度。
[*]字符填充法：在数据内填充转义字符，避免错误识别帧边界。
[*]零比特填充法：在发送端，信息字段只要遇到5个1就立即填入一个0；在接收端，发现5个1就去掉一个0。这种做法的原因是标记头尾的数据是01111110。
[*]违规编码法：用“高-高”、“低-低”来界定帧的开始和终止（结合曼彻斯特编码来看）。
差错控制
奇偶校验码
通过查看数据中有奇数个还是偶数个1来确认数据是否发生差错。
特点：只能检查出奇数个比特错误，检错能力为50%。
CRC循环冗余码
步骤：1、准备待传有效数据；2、每个组都加上冗余码构成帧再发送；3、接收方检验。
计算冗余码步骤：1、加0；2、模2除法；3、余数拼接。
检错过程：把收到的每一个帧都除以同样的除数，然后检查得到的余数。余数为0，判断没有差错，接受；余数不为0，判定该帧有差错，丢弃。
这里如果是第一次看到的同学，有可能看不明白，该笔记更加侧重于用于强化记忆，若不理解可搜索相关文章进行学习。
海明码
这部分依然是考察重点且描述起来啰嗦，故只记下一些零碎的重点方便记忆。
[*]要检测d位的错误，需要d+1位的码距；要纠正d位错误，需要2d+1位的码距。
[*]海明不等式：数据有 https://www.zhihu.com/equation?tex=m位，校验码有 https://www.zhihu.com/equation?tex=rr 位，则 https://www.zhihu.com/equation?tex=2%5E%7Br%7D%5Cgeq%20m%2Br%2B1 。
[*]校验码放在序号位 https://www.zhihu.com/equation?tex=2%5E%7Bn%7D的位置。余下的位置，数据按序填上。
流量控制
较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。
数据链路层流量控制手段：接收方收不下就不回复确认。
传输层流量控制手段：接收端给发送端一个窗口公告。
停止-等待协议
每发送完一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。有一个计时器，发送超时就重传。
发送窗口大小=1，接收窗口大小=1。
后退N帧协议（GBN）
发送窗口大小>1，接收窗口大小=1。累积确认。如果chaos，重传所有已发送但未被确认的帧。
滑动窗口长度：若采用 https://www.zhihu.com/equation?tex=nn 个比特对帧编号，那么发送窗口的尺寸https://www.zhihu.com/equation?tex=W_%7BT%7DW_{T} 应满足： https://www.zhihu.com/equation?tex=1%5Cleq%20W_%7BT%7D%5Cleq%202%5E%7Bn%7D-11\leq W_{T}\leq 2^{n}-1 。因为发送窗口尺寸过大，就会使得接收方无法区别新帧和旧帧。
选择重传协议（SR）
发送窗口大小>1，接收窗口大小>1。
滑动窗口长度：发送窗口最好等于接收窗口，大了会溢出，小了没意义。若采用 https://www.zhihu.com/equation?tex=nn 个比特对帧编号，那么发送窗口的尺寸https://www.zhihu.com/equation?tex=W_%7BT%7DW_{T} 和接收窗口尺寸 https://www.zhihu.com/equation?tex=W_%7BR%7DW_{R} 应满足： https://www.zhihu.com/equation?tex=W_%7BTmax%7D%3DW_%7BRmax%7D%3D2%5E%7Bn-1%7DW_{Tmax}=W_{Rmax}=2^{n-1} 。
ALOHA协议
纯ALOHA协议
思想：不监听信道，不按时间槽发送，随机重发，想发就发。
如果发生冲突，接收方在就会检测出差错，然后不予确认，发送方在一定时间内收不到就判断发生冲突。超时后等一随机时间再重传。
时隙ALOHA协议
思想：把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等到下一个时间片开始时刻再发送。
CSMA协议
CSMA：载波监听多路访问协议（carrier sense multiple access）
CS：载波侦听/监听，每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据。
MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。
协议思想：发送帧之前，监听信道。
当监听结果空闲时，发送完整帧；信道忙时，推迟发送。
1-坚持CSMA
如果一个主机要发送消息，那么它先监听信道。空闲则直接传输，不必等待。忙则一直监听，直到空闲马上传输。如果有冲突（一段时间内未收到肯定回复），则等待一个随机长的时间再监听，重复上述过程。
优点：只要媒体空闲，站点就马上发送，避免了媒体利用率的损失。
缺点：假如有两个或两个以上的站点有数据要发送，冲突就不可避免。
非坚持CSMA
如果一个主机要发送消息，那么它先监听信道。空闲则直接传输，不必等待。忙则等待一个随机的时间之后再进行监听。
优点：采用随机的重发延迟时间可以减少冲突发生的可能性。
缺点：可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低。
p坚持CSMA
如果一个主机要发送消息，那么它先监听信道。空闲则以p概率直接传输，不必等待；概率1-p等待到下一个时间槽再传输。忙则持续监听直到信道空闲再以p概率发送。若冲突则等到下一个时间槽开始再监听并重复上述过程。
优点：既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间的这种方案。
缺点：发生冲突后还是坚持把数据帧发完，造成了浪费。
CSMA/CD协议
CD：碰撞检测（冲突检测），边发送边监听，适配器边发送数据边检测信道上信号电压的变化情况，以便判断自己在发送数据时其他站是否也在发送数据。
截断二进制指数规避算法
1、确定基本退避（推迟）时间为争用期 https://www.zhihu.com/equation?tex=2%5Ctau2\tau 。
2、定义参数 https://www.zhihu.com/equation?tex=kk，它等于重传次数，但 https://www.zhihu.com/equation?tex=kk 不超过10，即 https://www.zhihu.com/equation?tex=k%3Dmin%5Cleft%5C%7B%20%E9%87%8D%E4%BC%A0%E6%AC%A1%E6%95%B0%EF%BC%8C10%20%5Cright%5C%7Dk=min\left\{ 重传次数，10 \right\} 。当重传次数不超过10时， https://www.zhihu.com/equation?tex=kk 等于重传次数；当重传次数大于10时， https://www.zhihu.com/equation?tex=kk 就不再增大而一直等于10。
3、从离散的整数集合 https://www.zhihu.com/equation?tex=%5Cleft%5C%7B%200%2C1%2C%5Ccdot%5Ccdot%5Ccdot%2C2%5E%7Bk%7D-1%20%5Cright%5C%7D\left\{ 0,1,\cdot\cdot\cdot,2^{k}-1 \right\} 中随机取出一个数 https://www.zhihu.com/equation?tex=rr ，重传所需要退避的时间就是 https://www.zhihu.com/equation?tex=rr 倍的基本退避时间，即 https://www.zhihu.com/equation?tex=2r%5Ctau2r\tau 。
4、当重传达16次仍不能成功时，说明网络太拥挤，认为此帧永远无法正确发出，抛弃此帧并向高层报告出错。
CSMA/CA协议
原理
发送数据前，先检测信道是否空闲。
空闲则发出RTS（request to send），RTS包括发射端的地址、接收端的地址、下一份数据将持续发送的时间等信息；信道忙则等待。
接收端收到RTS后，将响应CTS（clear to send）。
发送端收到CTS后，开始发送数据帧（同时预约信道：发送方告知其他站点自己要传多久数据）。
接收端收到数据帧后，将用CRC来检验数据是否正确，正确则响应ACK帧。
发送方收到ACK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止（采用二进制指数退避算法来确定随机的推迟时间）。
第三章和第四章是重中之重，内容多且杂。以下部分记录琐碎的、需要记忆的知识点。
[*]介质访问控制所要完成的主要任务是，为使用介质的每个结点隔离来自同一信道上其他结点所传送的信号，以协调活动结点的传输。用来决定广播信道中信道分配的协议属于数据链路层的一个子层，称为介质访问控制（Medium Access Control，MAC）子层。
[*]信道划分介质访问控制将使用介质的每个设备与来自同一通信信道上的其他设备的通信隔离开来，把时域和频域资源合理地分配给网络上的设备。这种划分方式是静态划分，包括频分多路复用（FDM）、时分多路复用（TDM）、波分多路复用（WDM）、码分多路复用（CDM）。如果对这几种方式有不了解或者遗忘的地方，需查阅相关资料。
[*]上文提到的ALOHA、CSMA、CSMA/CD、CSMA/CA协议都属于随机访问介质访问控制。在这个大类之下，除了上述协议之外，还有轮询访问介质访问控制，其典型协议为令牌传递协议，主结点轮流“邀请”从属结点发送数据。采用令牌传送方式的网络常用于负载较重、通信量较大的网络中。
[*]局域网使用广播信道。局域网拓扑结构包括星型拓扑、总线型拓扑、环形拓扑、树型拓扑。
[*]有线局域网常用介质：双绞线、同轴电缆、光纤；无线局域网常用介质：电磁波。
[*]属于局域网的有以太网、令牌环网、FDDI网、ATM网、无线局域网。
[*]IEEE 802系列标准是IEEE 802 LAN/MAN 标准委员会制定的局域网、城域网技术标准（1980年2月成立）。其中最广泛使用的有以太网、令牌环、无线局域网等。这一系列标准中的每一个子标准都由委员会中的一个专门工作组负责。
[*]IEEE 802标准所描述的局域网参考模型只对应OSI参考模型的数据链路层与物理层，它将数据链路层划分为逻辑链路层LLC子层和介质访问控制MAC子层。
[*]以太网(Ethernet)指的是由Xerox公司创建并由Xerox、Intel和DEC公司联合开发的基带总线局域网规范，是当今现有局域网采用的最通用的通信协议标准。以太网络使用CSMA/CD（载波监听多路访问及冲突检测）技术。
[*]10BASE-T是传送基带信号的双绞线以太网，T表示采用双绞线，现10BASE-T采用的是无屏蔽双绞线（UTP），传输速率是10Mb/s。物理上采用星型拓扑，逻辑上总线型，每段双绞线最长为100m。采用曼彻斯特编码。
[*]计算机与外界有局域网的连接是通过通信适配器的。
[*]最常用的MAC帧是以太网V2的格式。DIX Ethernet V2：第一个局域网产品（以太网）规约。IEEE 802.3：IEEE 802委员会802.3工作组制定的第一个IEEE的以太网标准（帧格式有一丢丢改动）。
[*]速率≥100Mb/s的以太网称为高速以太网。
[*]IEEE 802.11是无线局域网通用的标准，它是由IEEE所定义的无线网络通信的标准。
[*]广域网的通信子网主要使用分组交换技术。广域网的通信子网可以利用公用分组交换网、卫星通信网和无线分组交换网，它将分布在不同地区的局域网或计算机系统互连起来，达到资源共享的目的。如因特网（Internet）是世界范围内最大的广域网。
[*]点对点协议PPP（Point-to-Point Protocol）是目前使用最广泛的数据链路层协议，用户使用拨号电话接入因特网时一般都使用PPP协议。
[*]PPP协议包含三个部分：1、一个将IP数据报封装到串行链路（同步串行/异步串行）的方法；2、链路控制协议LCP：建立并维护数据链路连接；3.网络控制协议NCP：PPP可支持多种网络层协议，每个不同的网络层协议都要一个相应的NCP来配置，为网络层协议建立和配置逻辑连接。
[*]HDLC协议：高级数据链路控制（High-Level Data Link Control或简称HDLC），是一个在同步网上传输数据、面向比特的数据链路层协议，它是由国际标准化组织(ISO)根据IBM公司的SDLC(SynchronousData Link Control)协议扩展开发而成的。数据报文可透明传输，用于实现透明传输的“0比特插入法”易于硬件实现。采用全双工通信所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏收或重份，传输可靠性高。
[*]值得注意的是，PPP协议和HDLC协议都只支持全双工链路。都可以实现透明传输，都可以实现差错检测，但不纠正差错。PPP协议面向字节，而HDLC面向比特。PPP协议无编号和确认机制，不可靠；而HDLC协议有编号和确认机制，可靠。
[*]链路层设备：网桥和交换机。
[*]网桥分类：透明网桥、源路由网桥。
第一章链接：https://www.52pojie.cn/thread-1500148-1-1.html
第二章链接：https://www.52pojie.cn/thread-1500750-1-1.html 大佬牛逼，感谢分享！ 感谢分享，一起学习 正好我也在学网络原理，膜拜，追更 感谢分享！！！
页:
[1]