『computer network-2』data link layer

数据链路层

一、数据链路层设计要点

数据链路层概述
- 数据链路层在物理层（传输比特流）的基础上实现了帧的传输，该层的协议数据单元PDU是帧
- 链路：一条点到点的物理线路，且中间没有任何其它的交换节点；数据链路：链路 + 协议的硬件和软件
- 信道类型：
  - 点对点信道：使用一对一的点对点通信方式
  - 广播信道：使用一对多的广播通信方式，广播信道上连接多个主机，必须采用专门的共享信道协议协调数据发送
- 封装成帧：保证接收方正确识别帧的边界
  - 字符计数法：在帧头部字段指明本帧的字节数，接收方通过该字段得知该接收多少字节
  - 字符填充的首尾定界法：定义专门的字符（SOH, EOT）作为帧的开始/结束标志，并使用字符填充将标志字符与数据区分开
  - 比特填充的首尾定界法：定义专门的比特序列作为帧的开始/结束标志，并使用比特填充将标志序列与数据区分开
    注意：如果不使用填充方式做转义，数据中的控制字符可能会干扰甚至打断帧在数据链路上的传输
  - 物理编码违例法：使用无效的物理编码作为帧的开始/结束标志，供接收方识别
- 透明传输：借助字符or字节填充，帧中无论出现什么样的比特组合，都能按照原样无差错地通过这个数据链路层
  - 若数据中出现控制字符SOH和EOT，就在其前面插入一个转义字符ESC；接收端删除ESC
  - 若数据中出现转义字符ESC，就在其前面再插入一个转义字符ESC；接收端删除前面的ESC

二、错误检测和纠正

误码率（BER）：误码率 = \(\dfrac{\text{出错的比特数}}{\text{传送的总比特数}}\)，衡量链路的可靠性
循环冗余校验（CRC）：检验比特差错（而非传输差错），通常采用硬件电路生成CRC校验和
1. 设生成多项式P有n+1位，发送数据帧M有k位，先在M后补n个0
2. 令M除以生成多项式P（向下采用模二运算、即异或），得到n位的余数R（帧检验序列FCS）
3. 将余数R连接在M的末尾，得到最终发送的帧M'
4. 接收方接收到M'后除以P，得到余数R'，可断言发送数据无差错 \(\Leftrightarrow\) R'=0
注意：CRC只能判断发送帧内部是否存在差错（即检错编码），无法判断具体是哪些比特位出现了差错
纠错编码：通过增加冗余信息得知错误的具体位置，而检错编码只能判断是否存在错误

注意：检错码和纠错码可以保证帧的无差错接收（无比特差错），但不意味着可靠传输，还可能发生帧丢失、帧重复、帧失序

三、基本数据链路协议

无限制的单工协议
- 假设前提：
  - 单向传输
  - 理想信道
  - 发送方总有数据发送
  - 接收方总能及时处理所收到的数据
单工停-等协议：增加流量控制，防止接收方处理帧速度不及发送方从而导致的帧丢失
- 接收方每收到一帧，都向发送方返回一个应答帧
- 发送方每发送一帧，都先等待来自接收方的应答帧，才继续发送
有噪声信道的单工协议（ARQ协议）：在有噪声信道中防止帧的传输出错
- 校验和：使接收方能够检测帧是否出错
- 确认帧：使发送方知道帧已被正确接收
- 超时重发：发送方在规定时间内未收到确认帧，则重发帧
- 帧序号：保证接收方不会收到重复帧（若重复接收则丢弃当前重复帧）

四、滑动窗口协议

ARQ协议的信道利用率 = \(\dfrac{\text{T}_D}{\text{T}_D + \text{RTT} + \text{T}_A}\)，分母代表数据帧发送 \(\rightarrow\) 数据帧传播 \(\rightarrow\) 应答帧发送 \(\rightarrow\) 应答帧传播的总时间
注意：ARQ协议的等待时间很长，大部分时间都花在RTT上，故其信道利用率较低
后退N帧协议：超时只能批量重传
- 发送方：发送窗口长度 \(\in [1, 2^n - 1]\)（n为帧编码位数），表示允许发送的帧（包括已经发送的帧）
- 接收方：接收窗口长度 = 1，表示允许接收的帧（窗口外的帧一律丢弃，直至遇到连续合法的帧）
- 发送过程：
  - 累积确认：发送方收到了来自接收方的ACK k，表示k以及k之前的帧已经被成功接收，窗口下界挪至第一个未被确认的帧
  - 超时重传：发送N个数据帧后，若发现N个帧的前一帧对应的计时器超时后仍未收到其确认信息，重传出错帧与其后的N个帧
- 接收过程：必须保证按序接收，即仅成功接收从头开始的最长连续帧
  - 如果正确且按序收到k号帧，那么接收方为k号帧发送ACK k，单窗口后移一帧
  - 否则，直接丢弃发送帧，并仅为最近成功接收的帧发送ACK；发送方的等待ACK的计时器超时后，会重发错误帧
选择重传协议：超时可以仅重传异常帧；发送方和接收方的窗口大小相同
- 发送方 or 接收方：窗口长度 = \(2^{\text{n-1}}\)，其中n为标记帧号所需要的比特位数
- 发送过程：
  - 逐个确认：收到窗口内某个帧的ACK后，就将该帧标记为“已接收”；若该帧是窗口下界，则将窗口右移到第一个未被确认的帧
  - 超时重传：每个帧有对应的定时器，一个超时事件发生后只重传对应的那个帧
- 接收过程：
  - 来者不拒：收到窗口内的某个帧后，将其缓存并返回对应的ACK；若收到连续下界帧，就右移窗口下界至首个未收到的帧
  - 及时查错：若接收方发现有帧传输错误，会及时回复对应的NAK，直至错误帧重发前都只回复最近一个正确接收帧的ACK 注意：NAK可以让错误重传更及时，不必让发送方等到ACK超时后才重传（帧丢失只能依靠超时检测重传对应帧）

注意：两种窗口协议都要保证接收方按照帧序号顺序上交网络层

五、点对点协议PPP

PPP协议的组成：PPP协议是一种广泛应用于点到点链路的数据传输的数据链路层协议
- 将IP数据报封装成串行链路的方法：IP数据报是PPP帧中的信息部分，其长度受最大传送单元MTU的限制
- 一个链路控制协议（LCP）：用以建立、配置、测试数据链路连接的协议
- 一套网络控制协议（NCP）：其中每个协议支持不同的网络层协议，如IP、OSI的网络层
PPP协议的特点：
- 设计简单，无纠错功能、无序号、无流量控制
- 封装成帧（首尾F字段） + 透明传输
- 在同一条物理链路上同时支持多种网络协议（如IP or IPx）
- 支持多种链路（串行or并行、同步or异步、低速or高速、电or光、交换or非交换）
PPP协议的帧格式：所有PPP帧的长度都是整数字节
- 标志字段F：首部第一个字段 + 尾部最后一个字段，规定为0x7E，用作起始 + 结束的定界符
- 地址字段A：首部第二个字段，规定为0xFF，无实际作用
- 控制字段C：首部第三个字段，规定为0x03，无实际作用
- 协议字段：首部第四个字段，占两个字节，协议字段决定了信息字段的数据类型
  - 0x0021：信息字段是IP数据报
  - 0xC021：信息字段是PPP的链路控制协议LCP的数据
  - 0x8021：信息字段是网络层的控制数据
  - 0xC023：信息字段是鉴别数据
  注意：信息字段（载荷）的长度是可变的，不超过1500字节
- 帧检验序列：尾部的第一个字段，占两个字节，使用CRC的FCS
字节填充：应用在异步填充（逐个字符发送）中，使用字符0x7D对信息字段进行转义
- 信息字段中的0x7E (标志字段) \(\Rightarrow\) (0x7D, 0x5E)
- 信息字段中的0x7D (转义字符) \(\Rightarrow\) (0x7D, 0x5D)
- 信息字段中的ASCII控制符 (\(\le\) 0x20)：如 0x03 \(\Rightarrow\) (0x7D, 0x23)，注意插入0x7D后要改变原字节
注意：接收端只需要进行与发送端字节填充相反的变换，就可以正确恢复发送前的信息
零比特填充：应用在同步填充（一连串比特连续发送）中，即暂时破坏原先的标志字段0x7E
- 发送端：只要发现信息字段中有5个连续1，就立即填入一个0（01111110 \(\Rightarrow\) 011111010）
- 接收端：对帧中的比特流进行扫描，每当发现5个连续1时，就把这5个连续1后的一个0删除
PPP协议的工作状态：
1. 链路静止：PPP链路的起始or终止状态，PC和ISP之间还不存在物理层连接
2. 链路建立：双方建立了物理层连接后，进入"链路建立"状态，目的是建立链路层的LCP连接
  - 配置请求帧：一种PPP帧，其协议字段为0xC021，其信息字段为特定的配置请求；另一端可返回如下相应
    - 配置确认帧：所有选项都接受
    - 配置否认帧：所有选项都理解，但都不接受
    - 配置拒绝帧：选项中有的无法识别或不能接收，需要协商
  - 配置选项：包括链路最大帧长、鉴别协议的规约、不使用地址和控制字段
  协商结束后，双方建立LCP链路，进入"鉴别"状态
3. 鉴别：双方建立了LCP链路后，进入”鉴别状态“；PPP支持以下两种身份认证协议：
  - 口令鉴别协议(PAP)：发起通信的一方需要发送身份标识符和口令，允许用户重试多次
  - 口令握手鉴别协议(CHAP)：比PAP更复杂，安全性更好
  鉴别失败，则转入”链路终止“状态；鉴别成功，则转入”网络层协议“状态
4. 网络层协议：PPP链路两端的NCP根据网络层的不同协议互相交换特定的NCP分组 若上层运行的是IP协议，则为PPP链路的两端配置IP协议模块时就要使用NCP中的IPCP协议，其分组被封装成PPP帧（0x8021）
5. 链路打开：网络层配置好后，链路两个PPP端点可以彼此向对方发送分组，或回送请求LCP or 回送回答LCP 以检查链路状态
6. 链路终止：数据传输结束后，一方发送终止请求LCP，收到终止确认LCP后转入“链路终止”状态；链路故障时也会转入“链路终止”

六、使用广播信道的数据链路层

局域网的数据链路层：
- 局域网的特点：网络被一个单位所拥有，且地理范围和站点数目均有限
- 局域网使用的信道类型：广播信道，其拓扑结构包括环形网、星形网、总线网
划分信道方式：让多用户合理方便地共享通信媒体资源
- 静态划分信道：频分复用 + 时分复用 + 波分复用 + 码分复用
  - 特点：代价较高，不适合局域网使用
- 动态介质访问控制：即多点接入，信道并非固定分配给用户（随机访问使用较多）
  - 随机访问：所有用户可随时发送消息，可能导致在共享媒体上发生碰撞；CSMA/CD(以太网) or CSMA/CA(无线网)
  - 受控访问：用户发送消息必须服从一定控制；多点线路探询
局域网技术标准：
- LLC与MAC：IEEE 802标准将局域网数据链路层分为逻辑链路控制子层 + 介质访问控制子层
  - 逻辑链路控制子层(LLC)：存放与传输媒体无关的内容，屏蔽局域网底层差异；传输媒体和MAC层均对LLC透明
  - 介质访问控制子层(MAC)：存放与接入到传输媒体有关的内容，不同局域网采用不同的MAC方法
- IEEE 802.3：CSMA/CD介质访问控制 + 物理层技术规范，包括：
  - IEEE 802.3u：快速以太网
  - IEEE 802.3z：千兆以太网
- IEEE 802.11：无线局域网介质访问控制与物理层技术规范

载波监听多点接入/碰撞检测（CSMA/CD）协议：只能进行半双工通信（双向交替通信）
- 多点接入：总线型网络，许多计算机以多点接入的方式连接在一根总线上
- 载波监听：节点在发送数据前 + 发送数据时检测总线上是否有其它节点正在发送数据；若其它站正在发送数据就暂时不发送
- 碰撞检测：节点边发送数据边检测信道上是否发生了碰撞；若其它站也在发送就立即中断本站发送
  注意：若至少有两个站同时在发送数据，总线电压会因为互相叠加而增大变化幅度
- 碰撞强化：发送方检测到信号碰撞后，立即停止发送，并发送 32or48bit 的干扰信号，让所有用户都知道发生了碰撞
- 碰撞避退：采用截断二进制指数退避算法，生成最小退避时间的站最先获得发送权
  - 倍数r = 0, 1, ..., \(2^k - 1\) 中随机选取一个数，其中 k = min(当前重传次数, 10)
  - 退避时间T = 2\(\tau\) \(\times\) r，检测到碰撞后，经过退避时间T后才重发，避免再次碰撞
  重传次数 > 16后，丢弃该帧，并向上层报告（表明同时打算发送数据的站太多）
- 争用期：即碰撞窗口，时长 = \(2\tau\)
  - 若过了争用期仍未检测到碰撞，就肯定没发生碰撞
  - 争用期内检测到冲突时，立即停止发送
- 最小帧长：\(2\tau\) \(\times\) 数据传输率，以太网数据传输率取 10Mbit/s
  - 小于最小帧长的帧是因冲突而截断的无效帧
  - 如果发送帧内容小于最小帧长，要加入填充字节
  注意：以太网的最小帧长 = 64B = 512b，规定争用期 = 51.2us，发送最小帧长的时间 = 争用期
- 极限信道利用率 = \(\dfrac{\text{T}_0}{\text{T}_0 + \tau} = \dfrac{1}{1 + a}\)，其中 \(\tau\) 为单项传播时间，\(\text{T}_0\) 为发送时间，\(a = \dfrac{\tau}{\text{T}_0}\)；a \(\rightarrow\) 0 说明一旦碰撞就能检测出来
- CSMA/CD协议的特点：
  - 优点：
    - 网络负载较轻时效率高
    - 硬软件实现简单、灵活
  - 缺点：
    - 网络负载较重时，碰撞发生概率增大，网络效率较低
    - 由于存在多次冲突的可能，数据从发送方到接收方的时间缺少保证，实时性较差

七、以太网

以太网物理层：使用便宜灵活的非屏蔽双绞线，使用集线器连接各个节点，物理上呈星形结构
- 10Base-T技术：10Mbit/s + 基带传输 + 双绞线，用于星形局域网，使用方便但通信距离稍短（两站间距 \(\le\) 200m）
- 集线器：采用星形拓扑结构组成的局域网，在星形的中心设置的高可靠的收发设备
  - 使用集线器的以太网在逻辑上仍是一个总线网，各站均使用CSMA/CD协议（同一时刻最多允许一个站发送数据）
  - 集线器很像一个多端口的转发器，一个端口使用两对双绞线与一台计算机的适配器连接
  - 集线器工作在物理层，每个端口仅简单转发比特，而不进行碰撞检测
- 曼彻斯特编码：用电平跳变表示 0 or 1，即每个码元都有电平跳变
以太网MAC层：采用CSMA/CD介质访问控制协议
- MAC地址：表示某个站的"标识符"；占48bit，高24bit表示厂商标识符、低24bit由厂商自行分配
  - 全球每个网络接口具有唯一的MAC地址
  - MAC地址固化在网卡的ROM中
  注意：若一个主机或路由器安装有多个适配器，这台设备就拥有多个"地址"
- 适配器（adapter）：进行串行数据(主机外) \(\Leftrightarrow\) 并行数据(主机内) 的转化
  - 发送数据：以太网总线上的所有节点都能收到帧
  - 过滤数据：根据MAC帧中的MAC地址判断是否是发往本站的帧：
    - 单播：收到帧的MAC地址 = 本站MAC地址（一对一）
    - 广播：发送给本局域网上所有站点的帧（一对全体）
    - 多播：发送给本局域网上一部分站点的帧（一对多）
    注意：若适配器受到有差错的帧，就把该帧直接丢弃无需通知CPU；若受到正确帧，就用中断通知CPU
- MAC帧的帧格式：5个字段
  - 目的地址 + 源地址：各6字节的MAC地址
  - 类型：2字节，标明上层协议的类型
  - 数据：网络层数据报，46 ~ 1500字节（可变长，46=64-len(首部)-len(尾部FCS), 1500同理）
  - FCS：4字节，帧校验序列，采用CRC校验
  注意："前同步码"的作用在于接收MAC帧时能够迅速调整时钟频率，与发送端实现比特同步；SONET/SDH 无需同步码
高速以太网：传统以太网的数据率只有10Mbit/s
- 快速以太网：IEEE802.3u标准、传输速率100Mb/s，在半双工模式下必须使用CSMA/CD协议（全双工反而不用）
- 千兆以太网：IEEE802.3z标准、传输速率1Gb/s，在半双工模式下必须使用CSMA/CD协议（全双工反而不用）
  - 载波延伸：由 \(a = \dfrac{\tau}{\text{T}_0}\) 可知，要想让 a 减小，可以增大 \(\text{T}_0\)，即增大争用期至512B（原64B），但额外填充开销较大
  - 分组突发：第一个帧采用"载波延伸"方法填充，后面的短帧一个接一个地发送（保证短帧之间的最小间隔）
  注意：全双工模式下，吉比特以太网不需要使用以上两种方法降低参数 a 的值
- 万兆以太网：IEEE802.3ae标准、传输速率10Gb/s，只工作在全双工模式下（无需CSMA/CD协议）

八、局域网互连

在物理层扩展局域网：使用集线器实现局域网在物理层的（多级结构）互连
- 优点：可以方便地实现网络的扩展、且成本较低
- 缺点："碰撞域"指的是在同一时刻域内至多仅有一个站可发送数据
  - 碰撞域扩大至原先各子域的并集、碰撞发生概率增大、可能影响网络性能
  - 若不同局域网使用不同的以太网技术，就不能使用集线器将各局域网连接
  注意：扩展后的局域网数据率 = \(\min\)(各站集线器的转发数据率)
在数据链路层扩展局域网：使用网桥实现局域网在数据链路层的互连（比物理层扩展更常用）
- 网桥：工作在数据链路层，对收到的帧进行转发和过滤，后被以太网交换机淘汰
  - 转发：根据MAC帧的目的地址，查找网桥地址表，确定将该帧转发至哪个接口（而不是转发到所有接口）
  - 过滤：不转发，直接丢弃MAC帧
  - 优势：
    - 过滤通信量、增大吞吐量
    - 扩大了物理范围
    - 提高了可靠性
    - 可互连不同物理层、不同MAC子层和不同速率的互联网（优于物理层的集线器）
  - 局限性：
    - 存储转发增加了时延，一次只能分析并转发一个帧
    - 在MAC子层中并没有流量控制功能
    - 网桥只适合于用户不多且通信量不太大的局域网
- 以太网交换机：多端口网桥，一个网络端口可连接主机 or 其它交换机，N个端口\(\Leftrightarrow\) N个碰撞域
  - 以太网交换机的特点：
    - 采用全双工方式，多主机可同时通信（不受CSMA/CD约束）；相互通信的主机独占传输媒体，无碰撞地传输数据
    - 拥有存储器，能在输出端口繁忙时把发来的帧进行缓存
    - 即插即用，内部交换表通过自学习算法逐步建立
    注意：交换机使用两对线，支持同时发送和接收帧，故不受CSMA/CD的限制，传输距离也够长
  - 与集线器的区别：
    - 交换机工作在数据链路层，集线器工作在物理层；交换机的每个接口为一个碰撞域（网段），可大幅提高网络性能
    - 交换机的每个接口独享带宽（各主机独占传输媒体），集线器的所有接口共用传输介质的带宽
    - 交换机的一个端口对应一个冲突域；集线器连接的各网络构成一个冲突域（一次仅允许一个站发送）
  - 自学习过程：交换表记录了 MAC地址 \(\rightarrow\) 端口号的映射；设A向B途经交换机发送一帧
    1. 填表：若无表项(A, A的端口号)，填写该表项（自学习过程）
    2. 转发：若无表项(B, B的端口号)，向除了“A端口”的所有端口广播；否则只向B端口转发即可 <
      注意：如果MAC目的地址与接收方地址不匹配，会被接收方过滤
    3. 刷新：每个写入项目预设有生存时间（改变端口连的主机 or 主机更换adapter），超过生存时间该项就自动被删除
    4. 直通：将收到的帧直接转发，无需先存储后转发（提高转发速度）
  - 透明网桥生成树算法：多个局域网互连可能形成环路（存在交换机互连），应避免帧的无休止绕环转发
    - 生成树协议STP：不改变实际的网络拓扑，而是切断某些链路，形成无环路树状结构
    - 广播风暴：某些站点频繁发送广播帧，导致网络拥塞
  注意：通过交换机（网桥）互连的一组主机构成广播域；交换机（网桥）的一个端口构成一个冲突域
- 虚拟局域网(VLAN)：在现有局域网的基础上，通过将网络站点分组，构成若干逻辑上独立的虚拟局域网
  - VLAN的优势：提高安全性 + 控制广播风暴（大量广播帧在网络中无限制兜圈子，消耗整个带宽资源）
  - VLAN划分规则：按交换机端口、MAC地址、协议等进行逻辑分组；每个VLAN内部构成一个广播域（无法跨VLAN广播）
  - 802.1Q帧：在以太网帧中类型字段前新插入一个4字节的VLAN标签
  - 同交换机下同VLAN内的转发：普通以太网中的帧转发（#1根据帧首部目的MAC得知其属于VLAN-10），无需使用VLAN标签
  - 跨交换机下同VLAN内的转发：#1插入VLAN标签（指导#2转发给VLAN-10），#2删除VLAN标签（形成标准以太帧）