Dying Memory

Keep moving

0%

计算机网路数据链路层

Posted on In
Symbols count in article: 2.9k Reading time ≈ 3 mins.
计算机网络数据链路层

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

术语

结点 nodes

主机和路由器

连接相邻结点的通信信道，有数据链路和物理链路之分，数据链路基于物理链路。

  • 有线链路 wired links
  • 无线链路 wireless links
  • 局域网 LANs

帧 Frame

链路层数据分组，封装网络层数据报。

链路层服务

组帧 framing

  1. 封装数据报构成数据帧，加首部和尾部
  2. 帧同步（帧定界符）
  1. 如果是共享介质，需要解决信道接入（channel access）
  2. 帧首部中的 MAC 地址，用于标识帧的源和目的，物理层寻址

相邻结点间可靠交付

  1. 根据具体链路采用不同的手段。在低误码率的有线链路上很少采用（如光纤、某些双绞线）一些可靠交付手段。
  2. 无线链路：误码率高，需要可靠交付。（确认、重传等）

流量控制 flow control

协调 pacing 相邻的发送结点和接收结点

差错控制 error detection

  1. 信号衰减和噪声会引起差错。
  2. 接收端检测到差错，根据具体的交付协议可能需要发送端重传也有可能直接丢弃由上层来决定。

差错纠正 error correction

接收端直接纠正比特差错。

全双工和半双工通信控制

  • 全双工链路两端结点同时双向传输
  • 半双工链路两端结点交替双向传输

链路层具体实现 （网卡）

链路层的具体实现是由每个主机或路由器接口实现。链路层在适配器（网路接口卡-NIC）中实现或者在一个芯片上实现。

差错编码

基本原理

在数据基础上增加一些冗余信息，这些冗余信息建立起了数据位和位或者 bit 与 bit 之间原本不存在的关联关系，把这个
冗余信息随数据发送出去吗，由接收方判断这种关联关系是否存在。

根据冗余信息是由数据中的一个分组还是多个连续分组获取的，可以把差错编码分为分组码和卷积码。

差错编码

R 称为冗余比特或监督位。如果 R'= f(D') 并不能保证数据完全不错。

差错编码不能保证 100% 可靠！

差错编码能力

检测能力强，冗余信息小，信道利用率高的要求。
差错编码可以分为 检错码 与 纠错码。

汉明距离。

奇偶校验码 Parity Bit

检错能力是50%，漏检率50%，编码效率好。
奇偶校验码（Parity Bit）是一种简单的错误检测机制，用于检测数据传输中的单比特错误。它通常在数据传输和存储过程中用于验证数据的完整性。奇偶校验有两种类型：奇校验和偶校验。

基本概念

奇校验（Odd Parity）

奇校验码确保数据中1的个数是奇数。如果数据中1的个数已经是奇数，则校验位设为0；如果是偶数，则校验位设为1。

偶校验（Even Parity）

偶校验码确保数据中1的个数是偶数。如果数据中1的个数已经是偶数，则校验位设为0；如果是奇数，则校验位设为1。

限制

奇偶校验只能检测单个比特错误，对于偶数个比特错误无法检测（如两个比特同时错误）。因此，虽然它简单且计算开销低，但适用于低误码率场景。在需要更高可靠性的场景中，通常使用更复杂的错误检测和纠正码（如CRC、Hamming码）。

二维奇偶校验

  1. 检测奇数位差错、部分偶数位差错
  2. 纠正同一行/列的奇数位差错

Internet校验和（checksum）

发送端将数据划分为16位的二进制整数序列，补码求和（sum）（最高位进位的1，返回最低位继续加）。

循环冗余校验码 CRC

多路访问控制协议 MAC

解决单一共享广播信道的两个或两个以上结点同时传输的干扰（interference）问题。
冲突 collision：结点同时接收到两个或者多个信号–接收失败。

两类链路

点对点链路

  1. 拨号接入的 PPP
  2. 以太网交换机与主机间的点对点链路

广播链路 共享介质

  1. 早期的总线以太网
  2. HFC 的上行链路
  3. 802.11 无线局域网

多路访问控制协议

mutiple access control protocol

  • 采用分布式算法决定结点如何共享信道，即决策结点何时可以传输数据
  • 必须基于信道本身，通信信道共享协调信息，无需第三方信道用于协调

理想 MAC 协议

给定速率位 R bps 的广播信道。期望：

  1. 当只有一个结点希望传输数据时，它可以以速率 R 发送。
  2. 当有 M 个结点期望发送数据时，每个结点平均发送数据的平均速率是 R/M。
  3. 完全分散控制，无需特定结点协调，无需时钟同步、时隙同步。
  4. 简单。

MAC 协议分类

三大类

信道划分（channel partitioning）MAC 协议

多路复用技术，TDMA time divison multiple access。

  • 网络负载重时，共享信道效率高，且公平
  • 网络负载轻时，共享信道效率低

随机访问（random access）MAC 协议

信道不划分，允许冲突，采用冲突恢复机制。

网络负载轻时，共享信道效率高，单个结点可以利用信道的全部带宽。网络负载重时，产生冲突开销。

当结点要发送分组时，利用信道全部数据速率 R 发送分组，动态性强，没有事先的结点间协调，两个或多个结点同时传输就会
造成冲突。随机访问 MAC 协议需要定义如何检测冲突，如何从冲突中恢复（比如延迟重传）。

典型的随机访问 MAC协议
  • 时隙（sloted）ALOHA
  • ALOHA
  • CSMA、CSMA/CD、CSMA/CA
时隙 ALOHA 协议

假定：

  • 所有帧大小相同
  • 时间被划分为等长的时隙（每个时隙可以传输1个帧）
  • 结点只能在时隙开始时刻发送帧
  • 结点间时钟同步
  • 如果两个或两个以上结点在同一时隙发送帧，结点即检测到冲突
    运行：
  • 当结点有新的帧时，在下一个时隙发送
  • 如果没有冲突，该结点可以在下一个时隙继续发送新的帧
  • 如果冲突，该结点在下一个时隙以概率P重传该帧，直至成功
    优点：
  • 单个结点活动时，可以连续以信道全部速率传输数据
  • 高度分散化，只需同步时隙
  • 简单
    缺点：
  • 易冲突，浪费时隙
  • 空闲时隙
  • 结点也许能以远小于分组传输时间检测到冲突
  • 时钟同步
    最好情况：信道被成功利用的时间仅占37%！
ALOHA 协议
  1. 非时隙（纯）ALOHA：更加简单，无需同步
  2. 当有新的帧生成时立即发送
  3. 冲突可能性增大
    最好情况：信道被成功利用的时间仅占18%！ALOHA = Hello 第一个 MAC 协议。
    ALOHA 协议损人不利己、自私的。
CSMA 协议

载波监听多路访问协议 carrier sense multiple access，发送帧之前监听信道（载波）。

信道空闲则发送完整帧，信道忙则推迟发送：

  • 1-坚持 CSMA
  • 非坚持 CSMA
  • P-坚持 CSMA 以概率 P 随机检测信道

冲突可能仍然发生，信号传播延迟，此时继续发送冲突帧会导致信道资源浪费。

CSMA/CD 协议

CSMA with Collision Detection，边发送边检测冲突，效率高。只要是随机访问协议都会有冲突检测机制，只不过机制不同。

  • 短时间内可以检测到冲突
  • 冲突后传输终止，减少信道浪费

冲突检测：

  • 有线局域网易于实现：测量信号强度，比较发射信号与接收信号。
  • 无线局域网很难实现：接收信号强度淹没在本地发送信号强度下。
    边发边听，不发不听。

轮转（taking truns）MAC 协议

结点轮流使用信道。综合以上协议的优点。

轮询 polling

主结点轮询邀请从属结点发送数据。典型应用：哑（dumb）从属设备，比如传感器。

问题：轮询开销，等待延迟，单点故障。

令牌传递 token passsing

控制令牌依次从一个结点传递到下一个结点。 令牌：特殊帧。一般会形成环形网络。

问题：令牌开销，等待延迟，单点故障。