计算机网络基础系列（三）

第三章 数据链路层

数据链路层的功能

1. 为网络层提供服务

   • 无确认的无连接服务
   • 有确认的无连接服务
   • 有确认的面向连接服务

2. 链路管理

   连接的建立 -> 传输帧 -> 释放连接

3. 帧定界

   将一段数据的前后添加相应的首部和尾部，确定帧的界限

4. 帧同步

   接收方应能从接收到的二进制比特流中区分帧的起始和终止

5. 透明传输

   不管传的数据是什么样的比特组合，都应能在链路上传送，即避免把传输的数据误解为帧定界

6. 差错控制

   用以使发送方确定接收方是否正确收到由其发送的数据的方法

数据链路层三个重要问题

封装成帧和透明传输

1. 封装成帧

   封装成帧是指将数据链路层给上层交付的协议数据单元添加帧头和帧尾组成为帧

   • 帧头和帧尾有重要的控制信息，其中一个作用就是作为帧定界

2. 透明传输

   数据链路层对上层交付的传输数据没有任何限制，就像链路层不存在一样

   • 字符填充法实现 插入转义字符
   • 零比特填充法实现 插入比特0

为了提高帧的传输速率，帧的数据长度应尽可能大，但<=最大传送单元（MTU）

差错控制

• 传输过程中1可能变成0，0也可能变成1，这就叫比特差错

• 在一段时间内，传输错误的比特占所传输比特总数的比率叫误码率（BER）

可以通过检错编码来检测传输过程中是否产生了比特差错，不过其只能判断是否出现错误，而无法确定错误位置，然后纠正错误。

1. 奇偶校验码

   • 在待发送的数据后面添加一位校验码，使整个数据（包括校验码在内）中“1”的个数为奇数（奇校验）或偶数（偶校验）
   • 若有奇数个位发生误码，则奇偶性发生变化时即可判断出是否出现误码
   • 若有偶数个位发生误码，则奇偶性不发生变化，无法判断是否出现误码（漏检）
   • 该方法漏检率较高，不常用

2. 循环冗余码（CRC）

   • 收发双方约定一个生成多项式G(x)
   • 发送方基于待发送的数据和生成多项式计算差错检测码（冗余码），将其添加到待发送数据后面一起传输
   • 接收方通过生成多项式计算收到的数据是否产生误码

   

循环冗余码（CRC）的漏检率较低，且易于用硬件实现，因此被广泛用于数据链路层

可靠传输

• 数据链路层向上提供的服务类型
  • 不可靠传输服务：仅仅丢弃有误码的帧，其他什么也不做
  • 可靠传输服务：想办法实现发送端发送什么，接收端就接收什么
• 一般情况下，有线链路误码率较低，为减少开销，并不要求向上层提供可靠传输服务；而无线链路误码率较高，因此需要向上提供可靠传输服务
• 传输差错包括分组丢失，分组失序，分组重复和比特差错等
• 可靠传输服务并不局限在数据链路层，其他各层均可选择实现可靠传输
• 可靠传输的开销较大，可根据实际情况选择性实现

下面介绍三种可靠传输协议机制：

1. 停止-等待协议SW

• 确认与否认

  

• 超时重传 一般设定重传时间为略大于“从发送方到接收方的平均往返时间”

  

• 确认丢失 给发送数据添加对应的编号

  

• 确认迟到 给确认添加对应的编号

  

注意事项：

• 对于误码率较高的点对点链路，为了能够让发送方尽早重传，可以给发送方发送NAK分组，这样无需等待超时重传
• 为了让接收方判断收到的数据是否重复，需要给数据分组添加编号，由于停止-等待协议的特性，因此只需要1个比特就够了，即0和1
• 为了让发送方判断收到的确认是否重复，同样也需要给ACK分组添加编号，但数据链路层上基本不会发生确认迟到，因此可以无需编号

信道利用率U = TD / TD + RTT + TA

• TD 发送方耗费的发送时延
• RTT 往返时间
• TA 接收方返回耗费的发送时延（因比TD要小的多，常忽略不计）

2. 回退N帧协议GBN

在流水线传输的基础上利用发送窗口来限制发送方连续发送数据分组的数量，是一种连续ARQ协议；在协议工作过程中发送窗口和接收窗口不断向前滑动，因此这类协议又称为滑动窗口协议

• 发送窗口的尺寸记为WT，其取值范围是：1 < WT <= 2^n^ - 1 （n表示比特数）

  

• 接收窗口的尺寸记为WR，对于回退N帧协议，其取值只能为 1

  

• 累计确认：接收方不一定要对收到的数据分组进行逐个发送确认，而是可以根据实际情况在收到多个数据分组后，对按序到达的最后一个数据分组进行发送确认。如ACKn表示数据分组n及其之前的数据分组均已收到。因此确认分组丢失后，发送方也可能不必超时重传

• 发送方收到重复的确认就可以知道之前的传输出现了差错，由此可以不需要等待超时时间即可立即重传

• 当WT超出其上限时，会造成接收方无法分辨新旧数据分组

• 当信道的传输质量很差导致误码率很高的时候，回退N帧协议并不一定优于停止-等待协议

3. 选择重传协议

由于回退N帧协议的接收方窗口尺寸WR只能为1，只能按序接收数据分组，因此当其中一个数据分组出现误码时，会导致其后续的数据分组都会被丢弃然后超时重传，这样极大浪费了通信资源。

若有办法只重传存在误码的数据分组，其效率将会得到提高。因此接收窗口尺寸WR应大于1，以便可以先接收失序到达但其本身并无误码的数据分组，等到所有分组全部到齐后再传输到上层，这就是选择重传协议

• 为了能够使发送方只重传出现误码的数据分组，接收方不能再采用累计确认，只能进行逐个确认
• 发送方的发送窗口尺寸WT必须满足：1 < WT <= 2^(n-1)^
  • WT = 1，则是停止-等待协议
  • WT超出最大范围，则接收方无法区分新旧数据分组
• 接收方的接收窗口尺寸WR必须满足：1 < WR <= WT
  • WR = 1，则是回退N帧协议
  • WR 超出最大范围，无意义

点对点协议PPP

• 目前使用最广泛的点对点数据链路层协议

• PPP协议为在点对点链路传输各种协议数据报提供了一个标准方法，主要有三部分组成：

  • 对各种协议数据报的封装方法（封装成帧）
  • 链路控制协议LCP 用于建立、配置和测试数据链路的连接
  • 一套网络控制协议NCPs 其中的每一个协议支持不同的网络层协议

• PPP帧的透明传输

  • 面向字节的异步链路使用字节填充法（插入转义字符）
  • 面向比特的同步链路是使用比特填充法（插入零比特）

• PPP协议工作状态

  

共享式以太网

网络适配器

• 将计算机连接到以太网需要使用相应的网络适配器，也叫网卡
• 计算机内部中，网卡与CPU之间的通信，一般是通过计算机主板上的I/O总线以并行传输的方式进行
• 网卡与外部以太网（局域网）之间的通信，一般是通过传输媒体（如光纤，同轴电缆）以串行方式进行
• 网卡其中一个重要功能就是要进行并行传输和串行传输的转换
• 为了网卡能够正常工作，一般还需要安装相应的驱动，驱动程序的作用是负责驱动网卡发送和接收帧

MAC地址

• 一般被固化在网卡的电可擦可编程只读存储器EEPROM中，因此也叫硬件地址（物理地址）

• 需要注意的是物理地址属于数据链路层范畴而非物理层

• 一般情况下，普通用户计算机通常包含两块网卡

  • 接入有线局域网的以太网卡
  • 接入无线局域网的WIFI网卡

• 每块网卡都有一个全球唯一的MAC地址

• 交换机和路由器具有更多的网络接口，所以会有更多的MAC地址

• MAC地址是对网络上各接口的唯一标识，不是对网络上各设备的唯一标识

CSMA/CD协议

• 共享总线以太网有天然的广播特性，总线上连接有多个站点，当某个站点发送帧时，总线资源会被该站点独占，若此时其他站点也在总线上发送帧，就会产生信号碰撞

  

• 为解决碰撞问题，就采用了CSMA/CD协议，即载波监听多址接入/碰撞检测协议

• 载波监听到总线空闲的时候，总线实际上可能并不空闲
• CSMA/CD协议只是尽量避免碰撞，但无法实现完全不碰撞
• 使用该协议时，由于正在发送帧的站点必须边发送帧边检测碰撞，所以站点不可能一边发送一边接受的，因此只能进行半双工通信

共享式以太网的争用期

• 站点从发送帧开始，最多经过时长2τ（即δ->0）就可以检测出所发送的帧是否遇到了碰撞
• 共享总线以太网的端到端往返时间2τ被称为争用期或碰撞窗口
• 若在时间2τ内未检测到碰撞就可以认定该次发送不再会发生碰撞

共享式以太网的最小帧长和最大帧长

1. 最小帧长

• 最小帧长 = 数据传输速率 * 争用期2τ

• 为了确保共享总线以太网上的每个站点在发送完一个完整的帧之前能够检测出是否发生了碰撞，帧的发送时延就不能少于共享总线以太网端到端的往返时间，即2τ

• 对于10Mb/s的共享总线以太网，其争用期2τ的值规定为51.2μs，因此其最小帧长为512b，即64B

• 若遭遇碰撞，则一定发生在帧的前64B之内，因此，若接收点收到长度小于64B的帧，就可以判定这是一个遭遇了碰撞而异常终止的无效帧，将其丢弃即可

2. 最大帧长

• 一般来说，帧的数据载荷长度应远大于帧首部和尾部的总长度，这样可以提升帧的传输效率
• 若不限制数据载荷长度的上限，令帧的长度过长，也会产生一些问题，例如长期占用总线，某站点缓冲区溢出等

共享式以太网的退避算法

• 又称截断二进制指数退避算法
• 退避时间 = 基本退避时间（即争用期2τ） * 随机数r（r从离散的整数集合中[0,1…2^k^-1]随机挑选一个数，k = min[重传次数, 10]）

• 若连续发生多次的碰撞，表明可能有多个站点在竞争信道，使用上述的退避算法可以令重传需要推迟的平均时间随着重传次数增加而延长，从而减小发生碰撞的概率
• 当重传次数达16次仍未成功时，应放弃重传并向高层汇报

共享式以太网的信道利用率

网桥

• 利用网桥在数据链路层扩展共享式以太网

  • 利用网桥可将两个或多个的以太网连接起来，成为一个覆盖范围更大的以太网，而原来的每个以太网都称为一个网段

  

• 网桥可以识别帧的结构

• 可以根据帧首部中的目的Mac地址和网桥自身的帧转发表来转发或丢弃所收到的帧

1. A向D发送单播帧（不同网段）

• 同一网段的根据MAC地址发现不是自己的帧，将其丢弃
• 到达网桥处的帧根据网桥转发表找到转发接口
• 通过接口顺利转发到目的站点

2. A向C发送单播帧（同一网段）

• 同一网段的根据MAC地址发现是否属于自己的帧，是则接收，否则丢弃
• 到达网桥处的帧根据网桥转发表找到转发接口，发现无需转发，因此丢弃

3. 发送广播帧

• 所有站点均会接收该广播帧
• 到达网桥处的帧无需查找转发表，而是会通过除接收该帧接口外的其他接口转发该广播帧

透明网桥的自学习和转发帧

• 透明网桥通过自学习算法建立转发表

• 透明网桥中的透明，是指以太网中各网桥对于各站点而言是看不见的

• 透明网桥通过自学习算法基于以太网中各站点间的相互通信逐步建立起自己的转发表

  • 网桥收到帧后进行登记（即自学习）。登记内容为帧的源MAC地址和进入网桥的接口号
  • 网桥根据帧的目的MAC地址和网桥转发表对帧进行转发，其可能出现以下三种情况
    1. 明确转发：网桥清楚知道应从哪个接口进行转发
    2. 盲目转发：网桥转发表中无登记，网桥无法知道应从哪个接口进行转发，因此只能从进入接口外的其他所有接口都进行转发
    3. 丢弃：网桥知道无需转发帧，直接丢弃

• 注意事项：

  • 若网桥收到有误码的帧，直接丢弃
  • 若网桥收到无误码的广播帧，无需查表，直接从进入接口外的其他所有接口进行转发
  • 转发表中的每条记录都是有有效时间的，到期自动删除。因为各站点MAC地址和网桥接口的对应关系并不是永久性的，例如某个站点更换了网卡，其MAC地址就会改变

  

透明网桥的生成树协议STP

• 为了提高以太网的可靠性，有时需要在两个以太网之间使用多个透明网桥来提供冗余链路

• 在增加冗余链路提高以太网可靠性的同时，却给网络引入了环路

• 网络中的广播帧将在环路中永久兜圈，造成广播帧充斥整个网络，浪费了网络资源，使得网络中各主机间无法正常通信

• 为避免广播帧在环路中兜圈，透明网桥利用生成树协议（STP），可以在增加冗余链路提高网络可靠性的同时，又避免环路带来的问题

  • 不管网桥之间连接成了怎样复杂的带环拓扑，网桥之间通过交互网桥协议单元（BPDU），找出原网络拓扑的一个连通子集（即生成树），在这个子集里整个连通的网络不存在环路

  

  • 当首次连接网桥或网络拓扑发生变化时（认为改变或出现故障），网桥都会重新构造生成树，以确保网络的连通

交换式以太网

• 仅使用交换机而不使用集线器的以太网就是交换式以太网

以太网交换机

• 本质上是多接口的网桥
• 交换机的每个接口可以连接计算机，也可以连接集线器或另一个交换机
  • 当连接的是计算机或交换机时，工作在全双工方式，并能在自身内部同时连通多对接口，无需使用CSMA/CD协议
  • 当连接的是集线器时，工作在半双工方式，需要使用CSMA/CD协议
• 一般交换机都采用“存储转发”方式；为减少转发时延，某些交换机采用了直通交换方式
• 采用直通交换方式的交换机，在接收帧的同时就立即按帧的目的MAC地址决定该帧的转发接口，然后通过其内部基于硬件的交叉矩阵进行转发，而不必进行缓存
  • 直通交换时延非常小
  • 直通交换不检查差错就直接转发出去，有可能转发一些无用帧

共享式以太网与交换式以太网的对比

• 本质上可以理解为集线器与交换机的对比

  • 集线器扩大了广播域，扩大了碰撞域

  

  • 交换机扩大了广播域，隔离了碰撞域

  

• 交换式以太网网络性能远高于共享式以太网，所以集线器早已被交换机替代

以太网MAC帧格式

接收方可能收到的无效MAC帧包括：

• MAC帧长度不是整数个字节
• 通过MAC帧的FCS字段的值检测出帧有误码
• MAC帧的长度不在64~1518字节之间

接收方收到无效的MAC帧时，就简单将其丢弃，以太网的数据链路层没有重传机制

虚拟局域网VLAN

VLAN（Virtual Local Area Network）是一种将局域网内的设备划分为与物理位置无关的逻辑组技术，这些逻辑组有某些共同的需求

实现机制

• IEEE 802.1Q帧（Dot One Q帧）对以太网的MAC帧格式进行了扩展，插入了4字节的VLAN标记

• VLAN标记的最后12比特称为VLAN标识符VID，其唯一标志了以太网帧属于哪个VLAN

  • VID取值0~4095
  • 0和4095都不用来表示VLAN，故用于表示VLAN的有效取值范围为1~4094

• 802.1Q帧是由交换机来处理的，而不是用户主机来处理的

  • 当交换机收到普通的以太网帧时，会将其插入4字节的VLAN标记转变为802.1Q帧，称为“打标签”
  • 当交换机转发802.1Q帧时，可能会删除其4字节VLAN标记转变为普通以太网帧，称为“去标签”

• 交换机端口类型

  • Access
    • 连接用户计算机
    • 只能属于一个VLAN
    • PVID与端口所属VLAN的ID相同，默认为1
    • 接收处理：一般只接收未打标签的普通以太网帧，并给其打标签
    • 发送处理：若帧中VID等于端口PVID，则去标签后转发；否则丢弃

  

  • Trunk

    • 交换机之间或交换机与路由器之间的连接
    • 可以属于多个VLAN
    • 用户可以设置PVID，默认为1
    • 接收处理：
      • 接收已打标签的帧
      • 接收未打标签的帧，根据端口的PVID值给帧打标签
    • 发送处理：
      • 帧中VID等于端口PVID，则去标签后转发
      • 不等则直接转发

    

  • Hybrid

    • 交换机之间、交换机与路由器、交换机与用户计算机之间的连接

    • 可以属于多个VLAN

    • 用户可以设置PVID，默认为1

    • 接收处理：

      • 接收已打标签的帧
      • 接收未打标签的帧，根据端口的PVID值给帧打标签

    • 发送处理：

      • 查看数据帧中VID是否在端口的去标签列表中
        • 若存在，则去标签后转发
        • 不存在，则直接转发

      

无线局域网WLAN

WLAN（Wireless Local Area Network）

组成

1. 有固定基础设施的802.11无线局域网

   • AP：Access Point 接入点
   • BSS：Basic Service Set 基础服务集

   

2. 无固定基础设施移动自组织网络

   自组织网络没有基本服务集中的AP，而是由一些平等状态的移动站相互通信组成的临时网络，各结点地位平等，中间结点均为转发结点，因此都具有路由器的功能

   

CSMA/CA协议

802.11无线局域网采用了CSMA/CA协议，即载波监听多址接入/碰撞避免

注意的是CA并不能避免所有碰撞，而是尽量减少发生碰撞的概率

基本工作原理

• 等待DIFS：主要是考虑到可能有其他站的高优先级帧需要发送

• 等待SIFS：短帧间间隔。

• NAV：指出了完成这次帧的传送且信道转入空闲状态所需的时间

目的站收到源站发送的数据帧后，等待SIFS间隔后发送确认帧，这期间信道忙，其他站要发送只能推迟;当该次传输完成后，其他站需要等待DIFS间隔和随机退避时间后再发送帧

为了进一步降低发生碰撞的概率，802.11无线局域网允许源站对信道进行预约

• RTS：短的控制帧，包括源地址，目的地址和本次通信（包括目的站发回确认帧所需的时间）所需的持续时间
• CTS：短的响应控制帧，包括本次通信所需的持续时间

RTS若发生碰撞，源站就不可能接收到CTS帧，此时源站就会执行退避算法重传RTS帧；虽然进行信道预约会带来额外的开销，但由于两个帧都很短，且发生碰撞概率，碰撞产生及其自身的开销都很小，因此为降低碰撞概率。这点小代价还是值得的

退避算法

• 站点会为退避计时器设置一个随机的退避时间
  • 当退避时间减小到0时，就开始发送
  • 当退避时间未到0而信道又转为忙态时，此时需要冻结退避计时器的值，重新等待信道转为空闲，再经过帧间间隔DIFS后，继续启动退避计时器

A开始发送帧，BCD也想发送，发现信道处于忙状态，等待DIFS间隔后，启动退避计时器；假如C的退避时间最短，此时信道也处于空闲状态，C立即发送帧，BD对应退避时间冻结，等待信道转为空闲及DIFS间隔后，退避计时器解冻，重新开始计时…然后依次类推（如图所示）

MAC帧

• 数据帧
  • 用于站点间传输数据

• 控制帧
  • 通常与数据帧搭配使用
  • 负责区域清空，虚拟载波监听的维护及信道的接入，并于收到数据帧时予以确认
  • ACK帧、RTS帧及CTS帧等都属于该范畴
• 管理帧
  • 用于加入或退出无线网络，以及处理AP之间连接的转移事宜
  • 信标帧、关联请求帧以及身份认证帧等都属于管理帧