介绍链路层

概述

结点（nodes）：主机和路由器

链路（links）：连接相邻结点的通信信道，有线链路，无线链路，局域网等

帧（frame）：封装网络层数据报

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

链路层服务：

  • 组帧（framing）：封装数据报构成数据帧，加首部和尾部，帧同步，识别帧，如在首尾加特殊比特串等方式
  • 链路接入（link access）：如果共享介质，需要解决信道接入，MAC地址
  • 相邻结点之间的可靠交付：在低误码率的有线链路（光纤，某些双绞线）很少采用，无线链路等误码率高的链路需要可靠交付
  • 流量控制：协调相邻结点的发送和接收
  • 差错检测
  • 全双工和半双工通信控制

一般由网卡实现，以太网网卡、WiFi网卡等，同时实现链路层和物理层，与主机总线连接

差错编码

基本原理：增加冗余信息

差错编码可分为检错码和纠错码

检错码：如果编码集的汉明距离为r+1，则差错编码可以检测r位的差错。汉明距离为对应比特不同位的个数，编码集的汉明距离为所有码之间汉明距离的最小值

纠错码：如果编码集的汉明距离为2r+1，则可以纠正r位的差错

奇偶校验码

1bit校验位：检测奇数位差错，编码效率高，但只有百分之五十概率检测

二位奇偶校验：每一行每一列都计算，可以检测奇数位差错，部分偶数位差错

checksum

将数据划分为16bit的二进制整数序列，补码求和，最高位进位1返回最低为继续加，最后求反码

循环冗余校验码（CRC）

检错能力很强

将数据看为二进制数D，选择一个r+1位的比特模式G，目标：选择r位的CRC比特R，满足<D，R>可以被G整除（模2）

广泛用于实际网络

多路访问控制协议（MAC）

两类链路：

  • 点对点，如拨号接入的PPP，以太网交换机与主机间的点对点链路
  • 广播链路（共享介质），如早期总线以太网，WIFI，传播声音的空气

MAC协议解决单一共享广播信道时两个或两个以上结点同时传输，产生冲突的问题

多路访问控制协议（multiple access control protocol）

  • 采用分布式算法决定结点如何共享信道
  • 必须基于信道本身，不依赖第三方信道

理想MAC协议：

给定速率为R bps的广播信道，期望

  • 只有一个结点希望传输数据，可以以数据R传输
  • 多个结点希望传输时，可以平均分配R
  • 完全分散控制
  • 简单

分类：

  • 信道划分，多路复用技术，TDMA、FDMA、CDMA、WDMA等
  • 随机访问，信道不划分，允许冲突，采用冲突恢复机制
  • 轮转，结点轮流使用信道，每个结点使用时可以得到全部带宽

随机访问MAC协议

结点利用全部带宽发送分组，没有事先的结点间协调，可能发送冲突

时隙ALOHA协议

假定：

  • 所有帧大小相同
  • 时间被划分成等长的时隙
  • 结点只能在时隙开始时刻发送帧
  • 结点间时钟同步
  • 如果两个或两个以上结点在同一时隙发送帧，则结点检测到冲突

运行：

  • 当结点有新的帧时，在下一个时隙发送。如果无冲突，该结点可以在下一个时隙继续发送，如果冲突，该结点在下一个时隙以概率p发送帧，直到成功

优点：

  • 单个结点活动时，可以以信道全部带宽传输数据
  • 高度分散化
  • 简单

缺点：

  • 冲突，浪费时隙
  • 出现空闲时隙
  • 结点也许能以远小于分组传输时间检测到冲突
  • 时钟同步

效率：长期运行时，成功发送帧占用的时隙所占比例

一个结点在一个时隙成功发送的概率 $ p(1-p)^{N-1} $

任意结点 $ Np(1-p)^{N-1} $

最大效率为1/e=0.37 （N趋于无穷）

ALOHA协议

无需同步，当有新的帧时，立即发送，冲突可能性增大，效率更低

CSMA协议（载波监听多路访问协议）

发送帧之前，监听信道（载波）

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

冲突仍然可能发生，信号延迟传播，多节点同时向空闲信道发生数据等

CSMA/CD协议

带有冲突检测（Collision Detection）的CSMA协议，边发送数据边检测冲突，一旦检测冲突，就停止发送，减少浪费资源

冲突检测：

  • 有线局域网易于实现，测量信号强度，比较发射信号和接收信号
  • 无线局域网难以实现，信号衰减快

“边发边听，不发不听”

轮转访问的MAC协议

信道划分MAC协议：

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

随机访问MAC协议：

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

轮询（polling）：

  • 主节点轮流邀请从属结点发送数据
  • 典型应用，哑（dumb）从属设备

问题：

  • 轮询开销
  • 等待延迟
  • 单点故障，主节点宕机，整个网络瘫痪

令牌传递（token passing）：

  • 控制令牌一次从一个结点传递到下一个结点
  • 令牌：特殊帧

问题：

  • 令牌开销
  • 等待延迟
  • 单点故障，一个结点丢失令牌，整个网络都发生问题