三、数据链路层（上）
目录
3.1数据链路层概述
3.1.1术语
3.1.2功能
3.2封装成帧和透明传输
3.2.1封装成帧
①字符计数法
②字符（节）填充法
③零比特填充法
④违规编码法
3.2.2透明传输
3.2.3差错控制
差错原因
检错编码
奇偶校验
☆循环冗余码CRC
例题
纠错编码
海明码
3.3流量控制与可靠传输机制
3.3.1流量控制的手段
停止-等待协议
滑动窗口协议
GBN(后退N帧协议)
SR(选择重传协议)
3.3.2二者关系
3.3.3停止等待协议
1.无差错
2.数据帧丢失（超时重传）
3.确认帧丢失（超时重传，丢弃重复）
4.确认帧迟到（同上）
3.3.4后退N帧协议(GBN)
1.GBN中的滑动窗口机制
2.发送方必须响应的三件事
3.接收方要做的事
4.运行中的GBN
5.发送窗口大小上限
6.GBN重点总结
7.GBN性能分析
8.例题
3.3.5选择重传协议(SR)
1.SR中的滑动窗口机制
2.发送方必须响应的三件事
3.接收方要做的事情
4.运行中的SR
5.滑动窗口的大小
6.SR协议总结
7.例题
3.3.6信道利用率和信道吞吐率
3.4介质访问控制
3.4.1传输数据使用的两种链路
3.4.2介质访问控制的概念
3.4.3静态划分信道
信道划分介质访问控制(MAC multiple Access Control)
1.频分多路复用(FDM)
2.时分多路复用(TDM)
3.统计时分复用(STDM)
4.波分多路复用(WDM)
5.码分多路复用(CDM)
3.4.5动态分配信道
轮询访问介质访问控制
1.轮询协议
2.轮牌转递协议
随机访问介质访问控制
1.ALOHA协议(不听就说)
2.CSMA协议(先听再说)
3.CSMA/CD协议(先听再说，边听边说)
4.CSMA/CA协议
3.5局域网基本概念和体系结构
局域网的拓扑结构
3.1数据链路层概述
3.1.1术语
结点：主机，路由器
链路：网络中两个结点之间的物理通道，链路的传输介质主要有双绞线，光纤和微波，分为有线线路和无线线路。
数据链路：网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路。
帧：链路层的协议控制单元，封装网络层数据报。
数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报。
3.1.2功能
数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务就是将源自网络层来的数据可靠地传输到相邻结点的目标机网络层。
其主要作用就是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。
功能一：为网络层提供服务。无确认无连接服务，有确认无连接服务，有确认面向连接服务。【有连接一定有确认】
功能二：链路管理，即连接的建立，维持，释放(用于面向连接的服务)
功能三：组帧
功能四：流量控制。【限制发送方哦~】
功能五：差错控制(帧错/位错)
3.2封装成帧和透明传输
3.2.1封装成帧
封装成帧就是在数据的前后加上首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从收到的比特流中识别帧的开始和结束。
首部和尾部包含了许多控制信息，他们的一个重要作用就是：帧定界（确定帧的界限）。
帧同步：接收方应当能从收到的二进制比特流中区分出帧的起始和终止。
组帧的四种方法：由于字节计数法中Count字段的脆弱性（其值若有差错将导致灾难性后果）及字符填充实现上的复杂性和不兼容性，目前较普遍使用帧同步的方式是零比特填充和违规编码法。
①字符计数法
易出错，一错全错~
②字符（节）填充法
类似于编程语言中的转义符，
③零比特填充法
5 1 1 0
④违规编码法
用编码方式中非法的形式表示帧的开始和结束
3.2.2透明传输
透明传输是指不管所传数据是什么样的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨碍数据传输的东西。
当多传数据中的比特组合恰巧与某一个控制信息完全一样时，就必须采取适当的措施，使收方不会将这样的数据误认为是某种控制信息。这样才能保证数据链路层的传输是透明的。
3.2.3差错控制
差错原因
概括的来说，传输中的差错都是由于噪声引起的。
全局性：由于线路本身电气特性所产生的随机噪声（热噪声），是信道固有的，随机存在的。
解决方法：提高信噪比来减少或避免干扰。（对传感器下手）
局部性：外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。
解决办法：通常利用编码技术来解决。
差错：1.位错【比特位出错，1变0，0变1】
2.帧错（1，2，3）【丢失（1，2），重复（1，2，2，3），失序（1，3，2）】
检错编码
奇偶校验
☆循环冗余码CRC
在数据链路层仅仅使用循环冗余码校验CRC差错检测技术，只能做到对帧的无差错接收，即“凡是接收端数据链路层接收的帧，我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。接收端丢弃的帧虽然曾收到了，但是最终还是因为有差错被丢弃。“凡是接收端数据链路层接收的帧均无差错”。
但这并不是可靠传输，因为可靠传输是指“数据链路层发送端发什么，接收端就收到什么。”
链路层使用CRC检验，能够实现无比特差错的传输，但这还不是可靠传输。
①准备待传数据
②每个组都加上冗余码构成帧再发送
③接收方检验
例题
纠错编码
海明码
能发现错误，找到位置，并纠正错误。
海明距离/海明距/码距
在信息编码中，两个合法代码对应位上编码不同的位数称为码距，又称海明距离。举例如下：10101和00110从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。
工作流程：
①确定校验码位数r
2r >= m+r+1
②确定校验码和数据的位置
③求出校验码的值
④检错并纠错
3.3流量控制与可靠传输机制
较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要工作。
数据链路层的流量控制是点到点的，而传输层的流量控制是端到端的。
数据链路层的流量控制手段是：接收方收不下就不回复确认帧。
传输层的流量控制手段是：接收端给发送端一个窗口公告。
3.3.1流量控制的手段
停止-等待协议
每发送完一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。
也可以说是一种特殊的滑动窗口协议，发送窗口和接收窗口的大小都是一。
滑动窗口协议
连续发送一个窗口的帧，只有收到确认帧后，窗口向前移一格。
GBN(后退N帧协议)
Go-Back-N Automatic Repeat reQuest
发送窗口>1，接收窗口=1.
SR(选择重传协议)
Selective Repeat Automatic Repeat reQuest
发送窗口>1，接收窗口>1.
3.3.2二者关系
可靠传输：发送端发啥，接收端接收啥。
流量控制：控制发送速率，使接收方有足够的缓冲空间来接收每一个帧。
滑动窗口就是为了解决：①可靠传输（发送方自动重传），②流量控制（收不了不给确认，想发也发不了）
3.3.3停止等待协议
1.为什么要有停止-等待协议？
除了比特出差错，底层信道还会出现丢包问题。
为了实现流量控制。
丢包：物理线路故障，设备故障，病毒攻击，路由信息错误等原因，会导致数据包的丢失。
数据包在各层也叫的不同，例如比特，帧，IP数据包，分组等等
2.研究停止等待协议的前提是啥？
虽然现在常用全双工通信方式，但为了讨论问题方便，仅考虑一方发送数据（发送方），一方接收数据（接收方）
因为是讨论可靠传输的原理，所以并不考虑数据是在哪一个层次上传输的。（计算机网络早期由于数据链路的质量不好，所以数据链路层一边担任检错纠错一边还要进行流量控制，而现在基本上就是数据链路进行纠错检错就好了，已经将流量控制交给运输层了【谢希仁版的计网就是，在运输层数据单位是分组】）
“停止-等待”协议就是每发送完一个分组就停止发送，等待对方确认，在收到确认后再发送下一个分组。
3．停止等待协议有哪几种情况？
无差错情况&有差错情况。
1.无差错
2.数据帧丢失（超时重传）
3.确认帧丢失（超时重传，丢弃重复）
4.确认帧迟到（同上）
3.3.4后退N帧协议(GBN)
1.GBN中的滑动窗口机制
上链路
存副本
2.发送方必须响应的三件事
①上层的调用
上层要发送数据时，发送方先检查发送窗口是否已经满，如果未满，则产生一个帧并将其发送；
如果窗口已满，发送方只需要将数据返回上层，暗示上层窗口满了。上层等一会再发。（实际上发送方可以缓存这些数据，窗口不满时发送）
②收到一个ACK
GBN协议中，对n号帧的确认采用累计确认的方式，标明接收方已经收到n号帧和它之前的全部帧。
③超时事件
协议的名字为后退N帧，起源于出现丢失和时延过长帧时发送方的行为。就像停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被发送但未被确认的帧。
3.接收方要做的事
①如果正确有序收到n号帧，那么接收方未n号帧发送一个ack，并将该帧中的数据部分交付给上层。
②其余情况都丢弃帧，并为最近按序接收的帧重新发送ack。(累计确认)接收方无需缓存任何时序帧，只需要维护一个信息：expectedseqnum（下一个按序接收的帧序号）
4.运行中的GBN
从上往下一层一层吃汉堡，吃不到汉堡的肉饼，将没吃的全扔了，等到肉饼到了再重新吃下去。（深情~）
5.发送窗口大小上限
若采用n个比特位对帧进行编号，那么发送窗口的大小WT应该满足：1 <= WT <= 2n-1
6.GBN重点总结
1.累计确认（偶尔捎带确认）
2.接收方只按序接收帧，不按序无情丢弃
3.确认序列号最大的，按序到达的帧
4.发送窗口最大为2n-1，接收窗口大小为1
7.GBN性能分析
停等<GBN<SR
8.例题
发送速率，就是要知道再某个时间内，一共发送了多少数据，两者相除就好！
3.3.5选择重传协议(SR)
1.SR中的滑动窗口机制
2.发送方必须响应的三件事
1.上层的调用
从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧；否则就像GBN一样，要么将数据缓存，要么返还给上层之后再传输。
2.收到一个ACK
如果收到ACK，假如该帧序号在窗口内，则SR发送方将那个被确认的帧标记位已接受。如果该帧序号是窗口的下界（最左边第一个窗口对应序号），则窗口向前移动到具有最小序号的未被确认帧处。如果窗口移动了，并且有序号在窗口在内的未发送帧，则发送这些帧。
3.超时事件
每个帧都有自己的定时器，一个超时事件发生后只重传一个帧。
3.接收方要做的事情
1.对接收窗口内的帧“来者不拒”
SR接收方将确认一个正确接收的帧而不管其是否乱序。失序的将被缓存，并返还给发送方一个该帧的确认帧【收谁确认谁】，直到所有帧（即序号更小的帧）皆被收到为止，这时才可以将一批帧按序交付给上层，然后向前滑动窗口。
2.如果收到窗口序号外（小于窗口下界）的帧，就返回一个ACK。其他情况就忽略掉。
4.运行中的SR
5.滑动窗口的大小
发送窗口最好等于接收窗口。（大了就出现二义性，小了没意义）n为编码比特数。
WTMAX = WRMAX = 2(n-1)
N=2,w=3出现二义性
N=2,w=2不会出现二义性
6.SR协议总结
1.对数据帧逐个确认，收一个确认一个
2.只重传出错帧
3.接收方有缓存
4. WTMAX = WRMAX = 2(n-1)
7.例题
3.3.6信道利用率和信道吞吐率
看一下停止等待协议的图示：
发的时间/总时间=信道利用率
3.4介质访问控制
3.4.1传输数据使用的两种链路
点对点
两个相邻节点之间通过一个链路相连，没有第三者，应用：PPP协议，常用于广域网。
广播式。（范围广）
所有主机共享通信介质，应用：早期的总线型以太网，无线局域网，常用于局域网。（范围小）典型拓扑结构：总线型，星型。
3.4.2介质访问控制的概念
介质访问控制所要完成的主要任务是，为使用介质的每个结点隔离来自同一信道上其他结点所传送的信号，以协调活动结点的传输。用来决定广播信道中信道分配的协议属于数据链路层的一个子层，称为介质访问控制(Medium Access Control，MAC)子层。
多路复用技术，其实就是把多个信号拧成一股绳，用的时候各找各的。
3.4.3静态划分信道
信道划分介质访问控制(MAC multiple Access Control)
1.频分多路复用(FDM)
用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。频分复用的所有用户在同样的时间占用不同的带宽（频率带宽）资源。（类似于并行）
2.时分多路复用(TDM)
将时间划分为一段段等长的时分复用帧（TDM帧）。每一个时分复用的用户在每一个TDM帧中占用固定序号的时隙，所有用户轮流占用信道。（类似于并发）
3.统计时分复用(STDM)
时分复用的改进版，为了增加信道利用率。（statistics）
4.波分多路复用(WDM)
波分多路复用就是光的频分多路复用，在一根光纤中传输多种不同波长（频率）的光信号，由于波长（频率)不同，所以各路光信号互不干扰，最后再用波长分解复用器将各路波长分解出来。
5.码分多路复用(CDM)
把多种数据拧在一起，到地儿自己分离。
常用于无线局域网、蜂窝网
码分多址（CDMA）是码分复用的一种方式。1个比特分为多个码片/芯片（chip），每一个站点被指定一个唯一的m位的芯片序列，发送1时发送芯片序列(通常把o写成-1）。
发送1时站点发送芯片序列，发送o时发送芯片序列反码。
3.4.5动态分配信道
轮询访问介质访问控制
既不会产生冲突，且主机发送数据时还可以占用全部带宽。可谓是集大成者，即不会像基于多路复用技术的信道划分介质访问控制那样不能占用全部带宽，更不会像随机访问介质访问控制一样产生冲突。
1.轮询协议
主节点“邀请”从属结点发送数据。
大哥询问二弟是否要说话，三弟四弟不可以插嘴，二哥回答完/说完，大哥再问三弟四弟…
问题：1.产生轮询开销，2.等待延迟，3.单点故障
2.轮牌转递协议
令牌：
一个特殊格式的mac控制帧，不含任何信息。控制信道的使用，确保同一时刻只有一个结点独占信道。
且令牌环网无碰撞，每个结点都可以在一定的时间内（令牌持有时间）获得发送数据的权利，并不是无限制地持有令牌。
问题：
1.令牌开销，2.等待延迟，3.单点故障
应用于令牌环网（物理层星型拓扑，逻辑环形拓扑）。
采用令牌传送方式的网络常用于负载较重，通信量较大的网络中。
环路闲着
环路中有人发售那个数据，将“令牌”状态修改为忙，与数据组成数据帧出发。
是谁的数据谁要。
回头数据源接收到自己发送的数据帧，检查是否出错，来决定是否重传。
紧接着，令牌就在环路中以时间片的速度转啊转。
随机访问介质访问控制
1.ALOHA协议(不听就说)
纯aloha协议：
不监听信道，不按时间槽发动，随机重发。想发就发。
冲突如何检测？
如果发生冲突，接收方就会检测出差错，然后不予确认，发送方在一定时间内收不到就判断发生冲突。
冲突如何解决？
超时后等一随机时间再重传。
时隙aloha协议的思想：
把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道，若发生冲突，则必须等到下一个时间片开始时刻再发送。控制了想发就发的随意性。
-
- 纯aloha协议比时隙aloha协议吞吐量更低，效率更低。
- 纯aloha协议想发就发，时隙aloha协议只有在时间片段开始时才能发。
2.CSMA协议(先听再说)
载波监听多路访问协议Carrier sense multiple access
Cs:载波监听，每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据。
监听：当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。当一个站检测到的信号电压摆动值超过一定门限值时，就认为总线上至少有两个站在同时发送数据，表明了发生了碰撞，即发生了冲突。
Ma：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。
协议思想：发送帧之前，监听信道。
监听结果：
1.信道空闲：发送完整帧
2.信道忙：推迟发送
1-坚持CSMA
非坚持CSMA
p-坚持CSMA
三种对比：
3.CSMA/CD协议(先听再说，边听边说)
像csma中发生冲突后还要坚持将数据发送完，就造成了资源浪费，有什么办法可以减少资源浪费，一冲突就能发现呢？
载波监听多点接入/碰撞检测（适用于总线以太网）
CSMA/CD(carrier sense multiple access with collision detection)
CS: 载波侦听/监听，每一个站在发送数据之前以及发送数据时都要检测一下总线上是否有其他计算机在发送数据
MA:多点接入，表示许多计算机以多点接入的方式连接在一根总线上。（总线型网络）
CD:碰撞检测(冲突检测)，“边发送边监听”，适配器边发送数据边检测信道上信号电压的变化情况，以便判断自己在发送数据时其他站是否也在发送数据。（半双工网络）
因为电磁波在总线上总是以有限的速率传播的，所以先听后发是会发生冲突的。
如何确定碰撞后的重传时机？
立即重发当然是不好的，这样会使其陷入恶性循环。
CSMA/CD协议使用截断二进制指数规避算法“避其锋芒，躬耕南阳”
-
- 确定基本规避时间为2τ
- 定义参数k，它等于重传次数，但k不超过10，即k=min[重传次数，10]。当重传次数不超过10时，k等于重传次数:当重传次数大于10时，k就不再增大而一直等于10。
- 从离散的整数集合[0,1,,2k-1]中随机取出一个数r，重传所需要退避的时间就是r倍的基本退避时间，即2rτ
- 当重传达16次仍不能成功时，说明网络太拥挤，认为此帧永远无法正确发出，抛弃此帧并向高层报告出错
实例：
最小帧长问题：
一个大前提，该csma/cd协议就是为了在发生冲突时立即叫停双方，使双方不再做无用功而是找合适的时机将数据成功的正确的发送出去。
而现在，有一个帧，超级短，短到发生冲突叫停时，它已经发完了（“吴帧”），哪这个算法对于这个帧就没有多大意义了。
所以我们为了提高传输效率，要规定一个最小帧长度：
4.CSMA/CA协议
载波监听多点接入/碰撞避免（适用于无线局域网）
CSMA/CA(carrier sense multiple access with collision avoidance)
为什么要有csma/ca?
1.因为无线局域网不像总线的以太网有实际的电路连接，可以实时查看线路上的电压变化，而在无线局域网中以空气为介质进行电磁波的传播是很难做到全方位实时（发的时候也检测）检测碰撞的。
2.再者就是，无线局域网下的设备不是互相知道对方存在的，当大家都以为信道空闲时，同时发送数据，那不就g了嘛。这就是隐蔽站的问题，手机1和手机2在发送数据时就互为隐蔽站。
而且csma/ca协议还是十分礼貌的，发送数据之前会“大家好，我要说话了”~过了一会（没人碰撞）~“巴拉巴拉”
其算法详情：
1.发送数据前，先检测信道是否空闲。
2.空闲则发出RTS(requesttosend)，RTS包括发射端的地址、接收端的地址、下一份数据将持续发送的时间等信息;信道忙则等待。
3.接收端收到RTS后，将响应CTS(clear to send)发送端收到CTS后，开始发送数据帧(同时预约信道:发送方告知其他站点自己要传多久数据)
4.接收端收到数据帧后，将用CRC来检验数据是否正确，正确则响应ACK帧
5.发送方收到ACK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止(采用二进制指数退避算法来确定随机的推迟时间)。
1.预约信道 2.ACK帧 3.RTS/CTS帧(可选)
CAMA/CD与CSMA/CA对比
相同点:
CSMA/CD与CSMA/CA机制都从属于CSMA的思路，其核心是先听再说。换言之，两个在接入信道之前都须要进行监听。当发现信道空闲后，才能进行接入。
不同点:
1.传输介质不同:CSMA/CD用于总线式以太网【有线】，而CSMA/CA用于无线局域网【无线】
2.载波检测方式不同:因传输介质不同，CSMA/CD与CSMA/CA的检测方式也不同。CSMA/CD通过电缆中电压的变化来检测，当数据发生碰撞时，电缆中的电压就会随着发生变化;而CSMA/CA采用能量检测(ED)、载波检测(CS)和能量载波混合检测三种检测信道空闲的方式。
3.CSMA/CD检测冲突，CSMA/CA避免冲突，二者出现冲突后都会进行有上限的重传。
3.5局域网基本概念和体系结构
局域网的英文全称是“Local Area Network”，缩写为“LAN”,是指在某一个区域内由多台计算机互联成的计算机组。局域网可以实现文件管理、应用软件共享、打印机共享、工作组内的日程安排、电子邮件和传真通信服务等功能。
局域网是指在某一区域内由多台计算机互联成的计算机组。一般是方圆几千米以内。局域网可以实现文件管理、应用软件共享、打印机共享、工作组内的日程安排、电子邮件和传真通信服务等功能。局域网是封闭型的，可以由办公室内的两台计算机组成，也可以由一个公司内的上千台计算机组成。
局域网一般为一个部门或单位所有，建网、维护以及扩展等较容易，系统灵活性高。其主要特点是：
- 覆盖的地理范围较小，只在一个相对独立的局部范围内联，如一座或集中的建筑群内。
- 使用专门铺设的传输介质进行联网，数据传输速率高（10Mb/s～10Gb/s）。
- 通信延迟时间短，可靠性较高。
局域网的类型很多，若按网络使用的传输介质分类，可分为有线网和无线网；若按网络拓扑结构分类，可分为总线型、星型、环型、树型、混合型等；若按传输介质所使用的访问控制方法分类，又可分为以太网、令牌环网、FDDI网和无线局域网等。
局域网的拓扑结构
局域网络拓扑结构是指用传输介质互联各种设备的物理布局，网络中的计算机等设备要实现互联，就需要以一定的结构方式进行连接。 这种连接方式就叫做拓扑结构。 目前常见的网络拓扑结构主要有总线型结构、环形结构、树形结构和网状结构等形状。
目前常见的网络拓扑结构主要有以下三大类：
（1）星型结构
（2）环型结构
（3）总线型结构
星型结构：
优点：
- 网络结构简单，易于维护和管理；
- 控制简单，便于建网；
- 网络可靠性高，稳定性好。单个节点的故障只影响一个设备；
- 传输速度快，延迟小，误差低；
- 系统容易扩容。
缺点：
- 对中心节点的要求极高（包括中心节点的可靠性和冗余度）；2. 如果中心节点出故障，可能造成大面积网络瘫痪；3. 中心节点负担过重，结构较复杂，容易出现瓶颈。4. 系统安全性较差，资源共享性能较差。
环型结构：
优点：
- 各工作站地位相等；2. 系统中无信道选择问题；3. 网络数据传输不会出现冲突和堵塞现象。
缺点：
- 可靠性低，节点的故障将会引起全网的故障；2. 故障诊断困难；3. 不易重新配置网络；4. 当环中节点过多的时候，将会影响信息传输速率。
总线型结构：
优点：
- 网络结构简单，可靠性高；2. 电缆长度短，易于布线和维护；3. 节点间响应速度快，共享资源能力强；4. 设备投入量少，成本低；5. 易于扩充，数据端用户入网灵活。
缺点：
- 故障诊断困难；2. 故障隔离困难，任何节点的故障都有可能导致全网问题；3. 实时性较差；4. 网络规模较大时，传输效率下降幅度大。
