数据链路层

3.1 数据链路层的功能

3.1.1 为网络层提供服务

  • 无确认的无连接服务
  • 有确认的无连接服务
  • 有确认的面向连接服务 有连接就一定要确认

3.1.2 链路管理

数据链路层的连接的建立，维持和释放过程称为链路管理

链路两端结点通信前必须确认对方已处于就绪状态，这个过程称为链路建立

3.1.3 帧定界，帧同步与透明传输

  • 帧长=数据长度+首部/尾部长度，作用是帧定界
  • 帧同步：帧定界后，接收方要能够识别出帧的边界
  • 透明传输：无论传输的数据是什么样的比特组合，都应当能在链路上传送。

3.1.4 流量控制

限制发送方的发送速率，使接收方能够及时处理接收到的数据，防止接收方的缓冲区溢出。

OSI模型中数据链路层有流量控制功能，但是TCP/IP模型中流量控制功能被转移到了传输层。

3.1.5 差错控制

帧在传输过程中可能出现错误。用以使发送方确定接收方是否正确收到发送数据的方法称为差错控制，其通常可分位位错和帧错

位错通常采用循环冗余检验CRC或者奇偶校验等方法进行检测和纠正，通过自动重传请求来重传出错的帧，这种差错控制的方法称为ARQ法。

帧错可以通过引入定时器和编号机制，保证每一帧最终都能有且仅有一次正确地交付给目的节点

3.2 差错控制

数据帧：两台主机之间传输信息时，必须将网络层的分组封装成帧，以帧的格式进行传送。将一段数据的前后分别添加首部和尾部，就构成了帧。

可靠传输：数据链路层的可靠传输机制通常使用确认和超时重传两种机制来完成。确认是一种无数据的控制帧，使得接收方可以让发送方知道哪些内容被正确接收。有些情况下，为了提高传输效率，将确认捎带在一个回复帧里，称为捎带确认。超时重传是指发送方在发送某个数据帧后就开启一个计时器，在一段时间内，如果没有得到发送的数据帧的确认帧，就重新发送该数据帧，直到发送成功。

3.2.1 检错编码

奇偶校验：由n-1位信息元和1位检验元组成。如果是奇校验码，那么在附加一个校验元后，码长为n的码字中1的个数为奇数。反之亦然。

循环冗余检验(CRC)： 给定一个m bit的帧或报文，发送器生成r bit的序列，称为帧检验序列。发送方和接收方提前商定一个多项式G(x)(最高位和最低位必须是1)，接收方通过检查m+r的帧能否被G(x)整除来判断是否出错。

生成r bit的步骤如下：

  • 假设G(x)阶为r，在帧的低位端加上r个0
  • 利用模2除法，用G(x)去除上一步的数据串，得到的余数为冗余码

eg: 冗余码计算举例，G(x)为1101(r = 3)，待传送数据为M = 101001(m = 6)

所求余数即用G(x)去除101001000

3.3 流量控制与可靠传输

3.3.1 停等式ARQ

停等式较为简单，可以视作窗口为1的滑动窗口，差错处理方案如下：

  • 到达目的站时数据帧被破坏，接收站通过差错检验发现数据帧出问题，丢弃该帧。源站装备了计时器，超时后会重发该帧。
  • 数据帧正确接受但确认帧被破坏，发送方收不到确认帧，会超时重发该数据帧，接收方收到相同的数据帧时，会重传确认帧。

停等式中，发送的数据帧和接收方的确认帧用1 bit进行编号，帧序号0，1交替变换，确认帧ACK0，ACK1交替变换。(因为窗口大小为1)

3.3.2 回退N帧

相比停等式协议，回退N帧允许发送方咔咔连续传送好几个帧过去，而接收端传送的ACKn确认帧表示n帧即之前的帧都已正确接收。发送端没发送完一个帧就要为其设置计时器，而如果某个帧超时没有确认帧，发送方会回退到最早没有得到确认帧的那个帧重新发送。

发送方窗口为$2^n-1$，接收方窗口为1。

3.3.3 选择重传

相比回退N帧，选择重传避免了正确帧还需重发的浪费，哪个帧出问题了就直接发送一个否定帧回去。由于此时需要保存那些正确的帧，接收窗口应和发送窗口一样大($2^{n-1}$，之所以变为一半了可以理解为选择重传有可能传过去的某帧，而如果超出了一半，发送窗口和接收窗口刚好错开，大小超出一倍，发送端传送的新帧可能会被误判为对旧帧的重发)

3.3.4 一些概念

信道效率/信道利用率：指发送方在一个发送周期的时间内，发送有效数据所需要的时间所占的比率

发送周期(T)：发送方从开始发送数据到收到第一个确认帧为止所花的时间

设数据传输速率为C，发送了L比特的数据，则信道利用率为(L/C)/T

3.4 介质访问控制

3.4.1 CSMA/CD算法的原理和应用

多点接入说明是总线型网络，计算机以多点接入的方式连接在一根总线上，协议的实质是“载波监听”和“碰撞检测”。

载波监听就是利用电子技术检测总线上有没有其他计算机也在发送。载波监听实际上就是检测信道。在发送前，每个站不停地检测信道，是为了获得发送权；在发送中检测信道，是为了及时发现有没有其他站的发送和本站发送的碰撞，这就是碰撞检测。总之，载波监听是全程都在进行的。

碰撞检测就是边发送边监听。就是网卡边发送数据边检测新岛上的信号电压的变化情况，以便判断自己在发送数据的时候其他站是否也在发送数据。当几个站同时在总线上发送数据时，总线上的信号电压变化幅度将会增大（互相叠加），当网卡检测到的信号电压超过一定的门限值时，说明总线上至少有两个站同时在发送数据，表明产生了碰撞（冲突），所以也称为冲突检测。这时，由于接收的信号已经识别不出来，所以任何一个正在发送的站就会立即停止发送数据，然后等待一段随机事件以后再次发送。

工作原理

  • 先听后发：侦听信道空闲，则开始发送帧，否则等到信道上没信号能量后再发送。

  • 边听边发：发送过程中持续监测信道

  • 冲突停发：若未检测到碰撞，则发送完毕该帧；否则终止数据发送，并发送一个拥塞信号，以便通知其他站点发生了碰撞。

  • 随即重发：终止发送后，执行指数退避算法，等待一段时间后执行边听边发步骤。

  • CSMA/CD中的站点不能同时发送和接收，故采用此协议的网络只能是半双工通信。

  • 争用期&帧长：

    • 设t为单程传播时延，则发送数据后至多经过 2t 时间后，就能知道是否发生了碰撞。
    • 因此，把以太网端到端往返时间 2t 称为 争用期（冲突窗口或碰撞窗口），在争用期内未检测到碰撞，就确定这次发送不会发生碰撞。故收到小于一个最小帧长的帧会默认发生了碰撞，直接丢弃。（最小帧长是为了避免帧的碰撞信号还没传输回来时，帧已经完全传输完）

指数退避算法

  • 协议规定基本退避时间为2t
  • 定义参数k = min(重传次数，10)
  • 求退避时间T：从[0, $2^k-1$]任取一个r，T = 2rt
  • 重传 16 次仍不成功，说明网络拥挤，放弃发送，抛弃此帧，向高层报告错误

3.5 局域网

局域网：较小地理范围内的计算机互联网络。

主要特点：

  • 为一个单位所有，地理范围和站点数目有限
  • 所有站点共享较高总带宽
  • 较低时延和较低误码率
  • 各站为平等关系而非主从关系
  • 能进行广播和组播

特殊的局域网：

  • 以太网：逻辑拓扑为总线形，物理拓扑是星形和拓展星形
  • 令牌环
  • FDDI

网卡中的MAC地址也称为物理地址，以太网中的MAC地址为48位，前24位为厂商代码，后24位为厂商自定义，全球唯一。

以太网的MAC帧：

  • 前导码：使得接收端和发送端时钟同步，8字节。
    • 前同步码：7字节，实现MAC帧的比特同步
    • 帧开始界定符：1字节，标识MAC帧的开始
  • 目的地址：6字节，目的主机的MAC地址
  • 源地址：6字节，源主机的MAC地址
  • 类型：2字节，指出数据域中携带的数据应交给哪个协议实体处理
  • 数据：46-1500字节，数据域中的数据，包含高层协议信息，由于CSMA/CD算法限制，以太网帧必须满足最小长度64B，标准帧首部有18B，因此数据最少46B。
  • 填充：0-46字节，填充帧，使之达到64字节最小长度。
  • 校验码(FCS)：4字节，用于检测帧中的差错，由CRC-32算法生成。

3.6 广域网

3.6.2 PPP协议

  • PPP协议是串行线路通信的面向字节的协议，设计的目的是建立点对点连接发送数据
  • 组成部分
    • 链路控制协议（LCP）: 用于建立，配置，测试和管理数据链路。
    • 网络控制协议（NCP）：PPP协议允许多种网络层协议，每个不同的网络层协议要用一个相应的NCP来配置，为网络层协议建立和配置逻辑链接。
    • 封装方法：需要将IP数据报封装到串行链路，IP数据报在PPP帧中就是其信息部分，这个信息部分长度受到最大传送单元（MTU）的限制。
  • PPP帧的格式：因为PPP面向字节，所以PPP帧长度一定是整数字节
    • 标志字段F：7E，1字节（如果出现在信息字段，需要做字节填充，转义字节7D）
    • 地址字段A：FF，1字节
    • 控制字段C：03，1字节
    • 协议字段：2字节，例如比特0开始的有诸如IP, IPX, AppleTalk等，比特1开始的有诸如LCP, NCP等
    • 信息部分：0-1500字节，长度可变，即IP数据报（无需采用CSMA/CD，故没有最短帧）
    • 帧检验序列（FCS）：2字节，CRC中的冗余码，用于检验帧是否出错
    • 标志字段F：7E，1字节（如果出现在信息字段，需要做字节填充，转义字节7D）
  • PPP提供差错检测，不提供差错纠正，保证无差错接收，是不可靠传输协议，不使用序号和确认机制。
  • 仅支持点对点链路通信，不支持多点线路
  • PPP只支持全双工链路
  • PPP两端可以运行不同的网络层协议，但仍可以使用同一个PPP进行通信
  • PPP面向字节，信息字段出现和标志字段一致的比特时
    • 若异步线路：采用字节填充
    • 若同步线路：用协议规定采用硬件来完成比特填充

3.6.3 HDLC协议

高级数据链路控制(HDLC)是面向比特的数据链路层协议

  • 不依赖任何字符编码集，数据报文采用0比特插入法，可实现透明传输，易于硬件实现
  • 全双工通信，数据链路传输效率高
  • 采用CRC校验，可对信息帧进行顺序编号，防止漏收重发，传输可靠性高
  • 传输控制功能与处理功能分离，具有较大灵活性。
  • 组成部分
    • 标志字段F：01111110（数据流中如果出现五个连续的1时，在其后填一个0）
    • 地址字段A：8比特，根据不同的传送方式，表示从站或应答站的地址
    • 控制字段C：8比特，HDLC的许多重要功能都靠控制字段来实现
    • 信息部分：可变长度
    • 帧检验序列（FCS）：16比特
    • 标志字段F：01111110（数据流中如果出现五个连续的1时，在其后填一个0）

3.8 数据链路层设备

3.8.1 网桥的基本概念

  • 网桥连接两个或多个以太网，就会称为一个覆盖范围更大的以太网，而原来的每个以太网称为一个网段。
  • 其工作在链路层的MAC子层，可以使以太网各网段称为隔离开的冲突域。
  • 各个网段相对独立，故一个网段故障不会影响另一个网段。
  • 网桥的作用
    • 连接两个或多个以太网
    • 过滤不属于自己网段的帧
    • 转发属于自己网段的帧
    • 学习每个网段的MAC地址
    • 维护每个网段的MAC地址表

3.8.2 局域网交换机

3.8.2.1 交换机原理和特点

  • 以太网交换机是一个多端口的网桥
  • 将网络划分成小的冲突域，为每个工作站提供更高的带宽
  • 工作原理：检测MAC地址，查找表（若不在表中则添加），转发数据。

对于$N$个用户，共享式以太网每个用户平均带宽是原来的 1/$N$倍，而使用以太网交换机，交换机的总容量是原来的$N$倍

  • 以太网交换机特点:
    • 交换机每个端口直接与主机相连，且工作在全双工方式
    • 交换机能同时联通多个端口，使每对主机都能无碰撞地传输数据
    • 即插即用，内部帧的转发表通过自学习算法自动建立
    • 交换机使用专门的交换结构芯片，交换效率高
    • 交换机独占传输媒体的带宽
  • 交换模式：
    • 直通式交换机器：只检查帧的目的地址
      • 优点：交换机的转发速度快，帧在接收后几乎能马上被传送出去
      • 缺点：缺乏智能性和安全性，无法支持不同速率端口的交换
    • 存储转发式交换机：将接收到的帧缓存到高速缓存器中，并检查数据是否正确，然后再转发出去。若帧有错则直接丢弃
      • 优点：可靠性高，支持不同速率端口的转换
      • 缺点：速度慢，延迟大

3.8.2.2 交换机的自学习功能

  • 交换机的过滤和转发功能依靠交换表完成，其中每一项包含MAC地址，连通该MAC地址的交换机接口
  • 交换表的建立：自学习：交换机在接收到帧时，若该帧的源地址不在交换表中，则将该帧的源地址和接口号添加到交换表中
  • 交换表的维护：每一个表项超过有效时间自动删除，保证交换表符合当前网络实际情况，做到即插即用