计算机网络（二）

第三章 数据链路层

术语：

• 主机和路由器：结点(nodes)
• 连接相连节点的通信信道：链路(links)
  • 有线链路(wired links)
  • 无线链路(wireless links)
  • 局域网(LANs)
• 链路层(第2层)数据分组：帧(frame)，封装网络层数据报

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

数据链路层服务

• 组帧(framing)

  • 封装数据报构成数据帧，加首部和尾部
  • 帧同步

• 链路接入(link access)

  • 如果是共享介质，需要解决信道接入(channel access)
  • 帧首部中的"MAC"地址，用于标识帧的源和目的
    • 不同于IP地址！

• 相邻节点间可靠交付

  • 在低误码率的有线链路上很少采用(如光纤，某些双绞线等)
  • 无线链路：误码率高，需要可靠交付

• 流量控制(flow control)

  • 协调(pacing)相邻的发送节点和接受

• 差错检测(error detection)

  • 信号衰减和噪声会引起差错
  • 接受端检测到差错
    • 通知发送端重传或者直接丢弃帧

• 差错纠正(error correction)

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

• 全双工和半双工通信控制

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

链路层的具体实现

网卡间通信

• 发送端
  • 将数据报封装成帧
  • 增加差错检测比特，实现可靠数据传输和流量控制等
• 接收端
  • 检测差错，实现可靠数据传输和流量控制等
  • 提取数据报，交付上层协议实体

差错检测

差错编码基本原理

差错编码的检错能力

• 差错编码可分为检错码与纠错码
• 对于检错码，如果编码集的汉明距离d=r+1，则该差错编码可以检测r位的差错
• 对于纠错码，如果编码集的汉明距离d=2r+1，则该差错编码可以纠正r位的差错

奇偶校验码

1比特校验位：

• 检测奇数位差错

二维奇偶校验：

Internet校验和(Checksum)

• 发送端

  • 将"数据"（校验内容）划分为16位的二进制“整数”序列
  • 求和（sum）：补码求和（最高位进位的"1",返回最低为继续加）
  • 校验和（checksum）：sum的反码
  • 放入分组（UDP、TCP、IP）的校验和字段

• 接收端

  • 与发送端相同算法计算
  • 计算得到的"checksum":
    • 为16位全0(或sum为16位全1)：无错
    • 否则：有错

循环冗余校验码（CRC）

• 检错能力更强大的差错编码
• 将数据比特，D，视为一个二进制数
• 选择一个r+1位的比特模式（生成比特模式），G
• 目标，满足r位的CRC比特，R，满足
  • <D,R>刚好可以被G整除(模2)
  • 接收端检错：利用G除<D,R>,余式全0，无错：否则，有错！
  • 可以检测所有突发长度小于r+1位差错
• 广泛应用于实际网络(以太网，802.11WiFi，ATM)

D*2^r XOR R = nG 相当于 用G去除D左移r位，则余式为R

多路访问控制（MAC）协议

两类"链路"：

• 点对点链路
  • 拨号接入的PPP
  • 以太网交换机与主机间的点对点链路
• 广播链路（共享介质）
  • 早期的总线以太网
  • HFC的上行链路
  • 802.11无线局域网

使用场景

• 单一共享广播信道
• 两个或者两个以上结点同时传输:干扰(interference)
  • 冲突（collision）
    • 节点同时接收到两个或者多个信号->接受失败！

多路访问控制协议(multiple access control protocol)

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

理想MAC协议

给定：速率为R bps的广播信道

期望：

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

MAC协议分类

三大类：

• 信道划分(channel partitioning)MAC协议
  • 多路复用技术
• 随机访问(random access)MAC协议
  • 信道不划分，允许冲突
  • 采用冲突"恢复"机制
• 轮转(“taking turns”)MAC协议
  • 结点轮流使用信道

信道划分MAC协议:TDMA

TDMA: time division multiple access

• “周期性”接入信道
• 每个站点在每个周期，占用固定长度的时隙(e.g.长度=分组传输时间)
• 未用时隙空闲(idle)
• 例如：6-站点LAN，1，3，4传输分组，2，5，6空闲

信道划分MAC协议：FDMA

FDMA: frequency division multiple access

• 信道频谱划分为若干频带(frequency bands)
• 每个站点分配一个固定的频带
• 无传输频带空闲
• 例如：6站点LAN，1，3，4频带传输数据，2，5，6频带空闲。