[网络协议]计算机网络——数据链路层

结点:主机、路由器
链路:网络中两个结点之间的物理通道，链路的传输介质主要有双绞线、光纤和微波。分为有线链路、无线链路。
数据链路: 网络中两个结点之间的逻辑通道，把实现控制数据传输协议的硬件和软件加到链路上就构成数据链路。
帧:链路层的协议数据单元，封装网络层数据报。

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

功能

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

功能一:为网络层提供服务。无确认无连接服务，有确认无连接服务，有确认面向连接服务。有连接一 定 有确认!
功能二:链路管理，即连接的建立、维持、释放(用于面向连接的服务)。
功能三:组帧。
功能四:流量控制。限制发送方
功能五:差错控制(帧错/位错)。

封装成帧和透明传输

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

首部和尾部包含许多的控制信息，他们的一个重要作用:帧定界(确定帧的界限)。

帧同步:接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。

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

透明传输是指不管所传数据是什么样的比特组合，都应当能够在链路上传送。因此，链路层就“看不见”有什么妨碍数据传输的东西。

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

• 字符记数法
  
• 字符填充法（添加转义字符）
  
  
• 零比特填充法
  
• 违规编码法
  

差错控制

差错从何而来：
概括来说，传输中的差错都是由于噪声引起的。
全局性1.由于线路本身电气特性所产生的随机噪声(热噪声)，是信道固有的，随机存在的。
解决办法:提高信噪比来减少或避免干扰。(对传感器下手)
局部性2.外界特定的短暂原因所造成的冲击噪声，是产生差错的主要原因。
解决办法:通常利用编码技术来解决。

ps：数据链路层编码和物理层的数据编码与调制不同。物理层编码针对的是单个比特，解决传输过程中比特的同步等问题，如曼彻斯特编码。而数据链路层的编码针对的是- -组比特，它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。

冗余编码：在数据发送之前，先按某种关系附加上一定的冗余位，构成一个符合某一规则的码字后再发送
当要发送的有效数据变化时，相应的冗余位也随之变化，使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则，从而判断是否出错。

奇偶校验码

CRC循环冗余码

这里的除法是模2除法

在数据链路层仅仅使用循环冗余检验CRC差错检测技术，只能做到对帧的无差错接收，即“凡是接收端数据
链路层接受的帧，我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。接收端丢弃的
帧虽然曾收到了，但是最终还是因为有差错被丢弃。“ 凡是接收端数据链路层接收的帧均无差错”。

海明码

海明距离：两个合法编码(码字)的对应比特取值不同的比特数称为这两个码字的海明距离(码距)，- - 个有效编码集中,任意两个合法编码(码字)的海明距离的最小值称为该编码集的海明距离(码距)。

检验d位错误编码需要d+1位码距
纠正d位错误编码需要2d+1位码距

1. 确定校验码位数r
   
2. 确定校验码和数据的位置
   
3. 求出校验码的值
   
4. 检错并纠错
   

流量控制

较高的发送速度和较低的接收能力的不匹配，会造成传输出错，因此流量控制也是数据链路层的一项重要 工作。

数据链路层的流量控制是点对点的，而传输层的流量控制是端到端的。

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

停止-等待协议（简单，但信道利用率太低）

每发送完一一个帧就停止发送，等待对方的确认，在收到确认后再发送下一个帧。

1. 停等协议——无差错情况
   
2. 停等协议——有差错情况
   
   
   

滑动窗口协议

后退N帧协议（GBN）

发送方必须响应的事情：

1. 上层的调用
   上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送;如果窗口已满，发送方只需将数据返回给上层，暗示上层窗口已满。上层等一 会再发送。(实际实现中， 发送方可以缓存这些数据，窗口不满时再发送帧)。

2. 收到了一个ACK
   GBN协议中，对n号帧的确认采用累积确认的方式，标明接收方已经收到n号帧和它之前的全部帧。

3. 超时事件
   协议的名字为后退N帧/回退N帧，来源于出现丢失和时延过长帧时发送方的行为。就像在停等协议中一样，定时器将再次用于恢复数据帧或确认帧的丢失。如果出现超时，发送方重传所有已发送但未被确认的帧。

接收方要做的事情：

1. 如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK， 并将该帧中的数据部分交付给上层。

2. 其余情况都丢弃帧，并为最近按序接收的帧重新发送ACK。接收方无需缓存任何失序帧，只需要维护一个信息: expectedseqnum ( 下一个按序接收的帧序号)。

滑动窗口长度
若采用n个比特对帧编号，那么发送窗口的尺寸Wr应满足: 1≤Wτ≤（2^n）-1。因为发送窗口尺寸过大，就会使得接收方无法区别新帧和旧帧。

GBN重点总结

1. 累积确认(偶尔捎带确认)
2. 接收方只按顺序接收帧，不按序无情丢弃
3. 确认序列号最大的、按序到达的帧
4. 发送窗口最大为(2^n)-1，接收窗口大小为1

选择重传协议（SR）

发送方必须响应的事情：

1. 上层的调用
   从上层收到数据后，SR发送方检查下一个可用于该帧的序号，如果序号位于发送窗口内，则发送数据帧;否
   则就像GBN-样，要么将数据缓存，要么返回给上层之后再传输。
2. 收到了-一个ACK
   如果收到ACK，加入该帧序号在窗口内，则SR发送方将那个被确认的帧标记为已接收。如果该帧序号是窗口的下界(最左边第一一个窗口对应的序号)，则窗口向前移动到具有最小序号的未确认帧处。如果窗口移动了并且有序号在窗口内的未发送帧，则发送这些帧。
3. 超时事件
   每个帧都有自己的定时器，一个超时事件发生后只重传一一个帧。

接收方要做的事情：

1. 来者不拒(窗口内的帧)
   SR接收方将确认一个正确接收的帧而不管其是否按序。失序的帧将被缓存，并返回给发送方-一个该帧的确认帧[收谁确认谁]，直到所有帧(即序号更小的帧)皆被收到为止，这时才可以将一-批帧按序交付给上层，然后向前移动滑动窗口。
2. 如果收到了窗口序号外(小于窗口下界)的帧，就返回一个ACK。

可靠传输

可靠传输:发送端发啥，接收端收啥。
流量控制:控制发送速率，使接收方有足够的缓冲空间来接收每一个帧。

应用

点对点（广域网）

两个相邻节点通过一一个链路相连，没有第三者。
应用: PPP协议， 常用于广域网。

广播（局域网）

所有主机共享通信介质。
应用:早期的总线以太网、无线局域网，常用于局域网。
典型拓扑结构:总线型、星型(逻辑总线型)

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

以太网

以太网(Ethernet)指的是由Xerox公司创建并由Xerox、Intel和DEC公 司联合开发的基带总线局域网规范，是当今现有局域网采用的最通用的通信协议标准。以太网络使用CSMA/CD (载波监听多路访问及冲突检测)技术。

以太网在局域网各种技术中占统治性地位:
1.造价低廉(以太网网卡不到100块) ;
2.是应用最广泛的局域网技术;
3.比令牌环网、ATM网便宜，简单;
4.满足网络速率要求: 10Mb/s~10Gb/s.

以太网只实现无差错接收，不实现可靠传输。

介质访问控制

介质访问控制的内容就是，采取一定的措施，使得两对节点之间的通信不会发生互相干扰的情况。

信道划分介质访问控制

信道划分介质访问控制:将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开，把时域和频域资源合理地分配给网络上的设备。

多路复用技术：把多个信号组合在一条物理信道上进行传输，使得多个计算机或终端设备共享信道资源，提高信道利用率。

把一条广播信道，逻辑上分成几条用于两个节点之间通信的互不干扰的子信道，实际就是把广播信道转变为点对点信道。

1. 频分多路复用FDM
   
   充分利用传输介质带宽，系统效率较高;由于技术比较成熟，实现也比较容易。

2. 时分多路复用TDM
   

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

4. 码分多路复用CDM
   

动态分配信道

随机访问介质访问控制

1. ALOHA协议
   不监听信道，不按时间槽发送，随机重发。想发就发
   

2. CSMA协议
   CS:载波侦听/监听，每一个站在发送数据之前要检测一下 总线上是否有其他计算机在发送数据。
   MA:多点接入，表示许多计算机以多点接入的方式连接在一根总线上。
   

   • 1-坚持CMSA
     如果一个主机要发送消息，那么它先监听信道。空闲则直接传输，不必等待。忙则一直监听，直到空闲马上传输。如果有冲突(一.段时间内未收到肯定回复)，则等待-一个随机长的时间再监听，重复上述过程
   • 非坚持CMSA
     如果一个主机要发送消息，那么它先监听信道，空闲则直接传输，不必等待。忙则等待一个随机的时间之后再进行监听。
   • p-坚持CSMA
     如果一个主机要发送消息，那么它先监听信道。空闲则以p概率直接传输，不必等待;概率1-p等 待到下一一个时间槽再传输。忙则持续监听直到信道空闲再以p概率发送。若冲突则等到下一一个时间槽开始再监听并重复上述过程。

   

3. CSMA/CD协议（总线式以太网）
   CD:碰撞检测(冲突检测)，“ 边发送边监听”，适配器边发送数据边检测信道上信号电压的变化情况，以便判
   断自己在发送数据时其他站是否也在发送数据。

只要经过2τ时间还没有检测到碰撞，就能肯定这次发送不会发生碰撞。

4. CSMA/CA协议（无线局域网）
   

发送数据前，先检测信道是否空闲。
空闲则发出RTS (request to send)，RTS包括发射端的地址、接收端的地址、下 一份数据将持续发送的时间等信息;信道忙则等待。
接收端收到RTS后，将响应CTS (clear to send)。
发送端收到CTS后，开始发送数据帧(同时预约信道:发送方告知其他站点自己要传多久数据)。
接收端收到数据帧后，将用CRC来检验数据是否正确，正确则响应ACK帧。
发送方收到ACK就可以进行下-一个数据帧的发送，若没有则一-直重传至规定重发次数为止(采用二进制指数退避算法来确定随机的推迟时间)。

轮询访问介质访问控制

1. 轮询协议
   主节点轮流邀请从属结点发送数据
   问题：轮询开销、等待延迟、单点故障

2. 令牌传递协议