Jiajun's Blog

计算机网络-数据链路层

•
  • Computer-Network

计算机网络理论，数据链路层。

概述

数据链路层在物理层基础上实现帧（frame）的传输。

信道类型：

  • 点对点信道：一对一的通信；
  • 广播信道：一对多的广播通信。

常用的成帧方法：

  1. 字符计数法：在帧头部字段指明字节数；
  2. 字符填充法：定义专门的字符作为起始/结束标志；
  3. 比特填充法：定义特殊的比特序列作为起始/结束标志。
  4. 物理编码违例法：使用无效的物理编码作为起始/结束标志。

错误检测和纠正

一般用误码率BER（Bit Error Rate）表示链路可靠性：

\[误码率 = \frac{错误比特数}{传送总比特数}\]

检错编码

常用检错编码：

  • 奇偶校验
  • 校验和
  • 循环冗余校验CRC（Cyclic Redundancy Check）

循环冗余校验CRC

对数据M计算n位冗余码，发送方和接收方约定一个除数P：

  • 发送方：
    1. 用M左移n位；
    2. 除以除数P，得到余数R，余数R比除数P少一位；
    3. 将余数R附加到M后面，最终发送 \((M << n) + R\)。
  • 接收方：
    • 接收方对收到的(k+n)比特计算冗余码，结果（余数）为0表示传输正确。

通常用生成多项式P(x)表示除数P

  • 例：除数P=1101的生成多项式\(P(X) = X^3+X^2+X^0\)

纠错编码

纠错编码通过增加冗余信息使得能够检测错误发生所在，以便于纠正，又称为前向纠错(forward error correcting)

  • 海明编码

关于数据链路层检错：

  • 通过纠错码可以做到帧的无差错接收，或者说“无比特差错”
  • 并不意味着可靠传输，其他的错误包括：
    • 帧丢失、帧重复、帧失序

基本数据链路协议

无限制的单工协议

  • 单向传输
  • 理想信道
  • 发送方总有数据发送
  • 接收方总能及时处理收到的数据

无限制的单工协议

单工停-等（stop-and-wait）协议

增加流量控制（flow control）机制，得到单工停等协议：

  • 接收方每收到一帧，都向发送方返回一个应答帧
  • 发送方每发送一帧，都等待来自接收方的应答帧，之后才发送下一帧

单工停-等协议

有噪声信道的单工协议

在有噪声信道中，帧在传输过程中可能出错。

ARQ（Automatic Repeat reQuest）协议：

  • 校验和
  • 确认帧
  • 超时重传
  • 帧序号

协议设计考虑的三种情形：

  1. 数据帧被正确接收
    • 接收方返回确认帧，发送方收到后继续发送下一帧
  2. 数据帧出错或丢失
    • 接收方未收到帧或校验出错丢弃该帧，发送方等待确认帧超时后，重发数据帧
  3. 确认帧出错或丢失
    • 发送方未收到有效的确认帧，重发数据帧，接收方收到后，检查帧序号重复，不上交该帧，只返回确认帧

有噪声信道的单工协议

ARQ协议在同一时刻仅有一个帧在链路上传输（数据帧或确认帧），其对信道的利用率较低（尤其当传输时延较长时）。

\[U = \frac{T_D}{T_D + RTT + T_A}\]

ARQ传输时延

滑动窗口协议

基本思想

  • 允许发送方连续发送多个帧
  • 通过滑动窗口实现流量控制
    • 每个待发送的帧都有一个序列号
    • 发送方维护一个发送窗口，它包含一组序列号，对应允许它发送的帧
    • 接收方维护一个接收窗口，对应允许它接收的帧

发送方：

  • 发送窗口内的序列号代表允许它发送的帧
    • 窗口内最大的序列号称为窗口上边界，或窗口上沿、前沿
    • 窗口内最小的序列号称为窗口下边界，或窗口下沿、后沿
  • 每当从网络层得到一个数据包，将其组成帧发出后，发送窗口的上边界+1
  • 发送窗口下边界的帧被接收方确认后，下边界+1

接收方：

  • 接收窗口内的序列号代表它可以接收的帧
  • 收到的帧序列号等于窗口下边界时，将该帧上交网络层，并返回确认帧，同时整个窗口向前移动1个位置
  • 如果收到帧序列号落在接收窗口之外，则将其丢弃
  • 接收窗口大小总是保持固定

后退N帧的滑动窗口协议（Go Back N）

当某帧出错时，该帧之后的帧全被丢弃，从出错帧开始重新发送。实际上此时接收窗口宽度为1。

接收方收到帧后，返回ACKn确认帧，表示第n帧前的所有帧都已正确接收。

选择性重传的滑动窗口协议（Selective Repeat）

当某帧出错时，只选择性地重发该帧，该帧之后发送的帧由接收方数据链路层缓存，收到重发的出错帧后上交给网络层。

当接收方检测到出错帧时，发送一个否定的确认(NAK, Negative Acknowledgement)

  • 发送方可以尽快重发出错帧，而不必等到超时

同样会回送ACKn确认帧，表示第n帧前的所有帧都已正确接收。

点对点协议PPP

PPP 协议有三个组成部分

  • 将IP数据报封装到串行链路的方法
  • 链路控制协议LCP (Link Control Protocol)
  • 网络控制协议NCP (Network Control Protocol)

PPP的帧格式

  • PPP 是面向字节的，所有的PPP 帧的长度都是整数字节
  • 标志字段F：=0x7E (二进制：01111110)
  • 地址字段A：置为0xFF，实际上不起作用
  • 控制字段C：通常置为0x03
  • 协议字段：2字节，用于识别信息字段（又称为载荷）的类型
    • 0x0021：PPP 帧的信息字段是IP数据报
    • 0xC021：信息字段是PPP链路控制数据(LCP)
    • 0x8021：信息字段是网络控制数据(NCP)
  • 校验字段FCS：2字节的CRC校验

PPP帧格式

PPP透明传输（帧边界识别）

字符填充：

  • 信息字段(载荷)中的每一个 0x7E -> 0x7D, 0x5E
  • 信息字段中的每一个 0x7D -> 0x7D, 0x5D
  • 信息字段中的每一个ASCII 码控制字符(小于0x20 的字符)前面加入0x7D，且编码增加0x20，例如 0x03 -> 0x7D, 0x23

零比特填充：

  • 发送端：只要发现有5个连续1，则立即填入一个0
  • 接收端：对帧中的比特流进行扫描，每当发现5个连续1时，就把这5个连续1后的一个0删除。

PPP协议的工作状态

PPP支持两种身份认证协议：

  • PAP (Password Authentication Protocol)
  • CHAP (Challenge Handshake Authentication Protocol)

PPP协议的工作状态

介质访问控制

CSMA/CD协议

载波监听多点访问和碰撞检测。

载波监听：

  • 结点在发送数据之前先检测一下总线上是否有其他结点正在发送数据，如有则暂时不要发送数据，以免发生碰撞
    • 发送前先听

碰撞检测：

  • 结点边发送数据边检测信道上是否发生了碰撞(监听总线上传输的信号)
    • 边发送边听
  • 由于线路的传播时延，单纯靠载波监听并不能完全避免碰撞
    • 碰撞仍有可能发生
  • 在发生碰撞时，两个或更多的信号在总线上相互叠加，导致无法识别

碰撞强化

  • 发送方检测到碰撞后，立即停止发送，并发送32或48bit的人为干扰信号（jamming signal），以便让所有用户都知道已经发生了碰撞

碰撞退避：

  • 碰撞后，结点等待一段时间，重新开始载波检测和发送操作
  • 为避免退避后再次碰撞，冲突各方的等待时间应各不相同
  • 以太网采用截断二进制指数退避算法（truncated binary exponential backoff）
    • 退避时间: \(T = 2\tau \times 倍数\)
    • 倍数：在\(0, 1, \dots, 2k-1\)中取随机数，k = min(重传次数, 10)
    • 重传次数超过16后，丢弃该帧，并向上层报告

争用期:

  • 一个站点开始发送数据后，最多经过时间2τ(两倍的端-端时延)就可知道是否发生了碰撞
  • 以太网的端到端往返时延2τ称为争用期，或碰撞窗口
  • 如果经过争用期还没有检测到碰撞，就可以肯定这次发送不会发生碰撞 以太网的争用期:
  • 以太网的争用期长度：51.2us
  • 对于10Mb/s以太网，在争用期内可发送512bit，即64字节
  • 在发送数据时，若前64字节未发生碰撞，就不会发生碰撞
  • 据此规定以太网帧长>=64字节，长度小于64字节的帧为无效帧

CSMA/CD协议的实时性较差。

局域网技术

IEEE802将局域网的数据链路层分为两个子层：

  • 逻辑链路控制子层LLC（Logical Link Control）
  • 媒体访问控制子层MAC（Media Access Control）

局域网技术

以太网

以太网物理层

最初的以太网为总线结构，采用50Ω同轴电缆，传输速率10Mbps

  • 总线上单点故障会导致全网瘫痪，网络中结点数较多时可靠性较差且维护困难；
  • 同轴电缆成本较高

后发展为采用更便宜和灵活的非屏蔽双绞线，使用集线器(HUB)连接各个结点，物理上呈星形结构

  • 此种技术称为10Base-T
    • 10：10Mbps
    • Base：基带传输
    • T：双绞线(Twisted pair)
  • 使用集线器的以太网在逻辑上仍是一个总线网
  • 集线器很像一个多接口的转发器，工作在物理层

采用曼彻斯特(Manchester)编码，用电平的跳变表示0或1，即每个码元都有电平跳变。

以太网MAC层

以太网采用CSMA/CD介质访问控制协议

MAC地址：

  • 结点发送数据时，以太网总线结构，总线上的所有结点都能收到帧
  • 按照IEEE802.3标准，给每个结点分配唯一的MAC地址
  • MAC地址为48bit，高24bit为厂商标识符，低24位由厂商自行分配，须保证每个网络接口具有全球唯一的MAC地址
  • 适配器每收到一个帧就检查帧中的目的MAC地址，如果是发往本站的帧则进行处理，否则丢弃
  • 发往本站的帧包括以下三种帧：
    • 单播(unicast)帧(一对一)
    • 广播(broadcast)帧(一对全体)，MAC地址为全1表示广播
    • 组播/多播(multicast)帧(一对多)

以太网帧格式

5个字段：

  • 目的地址、源地址：各6字节的MAC地址
  • 类型：2字节，标明上层协议类型，如0x0800表示IP包
  • 数据：网络层数据报，长度46 ~ 1500字节
  • FCS：4字节，帧校验序列，采用CRC校

注：6+6+2+46+4=64字节，以太网帧最小长度为64字节。

以太网帧格式

高速以太网

  • 快速以太网（Fast Ethernet）：100Mbps
  • 千兆以太网（Gigabit Ethernet）：1Gbps
  • 万兆以太网（10-Gigabit Ethernet）：10Gbps
  • 更高速的以太网：40Gbps、100Gbps

局域网互联

物理层互连

使用中继器（repeater）或集线器（HUB）可实现局域网在物理层的互连。

优点：可以方便地实现网络的扩展，且成本较低。

缺点：碰撞域增大，碰撞发生概率增大，可能影响网络性能。

数据链路层互连

网桥

使用网桥（bridge）可实现局域网在数据链路层的互连。

网桥的基本工作原理：

  • 根据MAC帧的目的地址对收到的帧进行转发
  • 具有过滤帧的功能：当收到一个帧时，检查该帧的目的MAC地址，确定将该帧转发到哪一个接口。
  • 并不向所有的接口转发帧。

用网桥实现局域网互连的优点：

  • 过滤通信量、增大吞吐量，各网段是独立的碰撞域
  • 扩大了物理范围
  • 提高了可靠性
  • 可互连不同物理层、不同MAC子层和不同速率的局域网

网桥实现局域网互连的局限性：

  • 存储转发增加了时延
  • 在MAC子层并没有流量控制功能
  • 网桥只适合于用户数不太多(不超过几百个)和通信量不太大的局域网
    • 广播风暴：因某些站点频繁发送广播帧产生网络拥塞

交换机

交换机（switch）是一种多端口的网桥。

与集线器相比：

  • 交换机工作在数据链路层，每个接口为一个网段（碰撞域），可以大幅提高网络性能
  • 集线器由所有接口共享传输介质的带宽，而交换机为每个接口独享带宽

交换机按照自学习算法(self-learning)建立转发表

  • 原理：若从A发出的帧从接口x进入了某网桥，那么从这个接口出发沿相反方向一定可把一个帧传送到A
  • 首先进行自学习，检查帧中源地址在交换表中是否存在，如不存在，则在交换表添加一项，记下源地址和进入交换机的接口
  • 然后转发帧，根据收到的帧中的目的地址在交换表中查找：如果找到，则对应的接口即为转发接口；如果未找到，则向除进入接口外的所有其他接口转发。

生成树

交换机互连时可能出现环路，导致广播风暴。

互连在一起的网桥彼此通信后，能找出网络拓扑的一个子集。在该子集中，整个连通的网络中不存在回路，即在任何两个站之间只有一条路径。考虑到网络拓扑动态变化，生成树需定期更新。

虚拟局域网VLAN

VLAN是一种将局域网划分为多个逻辑上的局域网的技术。

帧不会在两个VLAN之间自动转发，包括广播帧。

IEEE 802.1Q在以太网帧中扩展VLAN标记（tag），供交换机识别和转发。以太网最大帧长从1518字节增加到1522字节。