计算机网络笔记No.22

数据链路层概述

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

术语：
主机和路由器：结点(nodes)
连接相邻结点的通信信道：链路(links)
链路层(第2层)数据分组：帧(frame)，封装网络层数据报

链路层服务

1. 组帧(framing)
   封装数据报构成数据帧，加首部和尾部
   帧同步
2. 链路接入(link access)
   如果是共享介质，需要解决信道接入(channel access)
3. 相邻结点间可靠交付
   在低误码率的有线链路上很少采用 (如光纤，某些双绞线等)
   无线链路：误码率高，需要可靠交付
4. 流量控制(flow control)
   协调(pacing)相邻的发送结点和接收
5. 差错检测(error detection)
   信号衰减和噪声会引起差错
   接收端检测到差错
6. 差错纠正(error correction)
   接收端直接纠正比特差错
7. 全双工和半双工通信控制
   全双工：链路两端结点同时双向传输
   半双工：链路两端结点交替双向传输

链路层的具体实现
每个主机或路由器接口
链路层在“适配器”(即网络接口卡-NIC)中实现或者在一个芯片上实现
链接主机的系统总线
由硬件、软件与固件组成

网卡间通信
发送端：

• 将数据报封装成帧
• 增加差错检测比特，实现可靠数据传输和流量控制等

接收端：

• 检测差错，实现可靠数据传输和流量控制等
• 提取数据报，交付上层协议实体

差错编码

差错编码基本原理：

差错编码不能保证100%可靠

差错编码的检错能力：

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

奇偶校验码

Internet校验和(Checksum)
发送端：

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

接收方：

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

循环冗余校验码(CRC)
CRC是检错能力更强大的差错编码

将数据比特，D，视为一个二进制数
选择一个r+1位的比特模式 (生成比特模式)，G
目标：选择r位的CRC比特，R，满足

• <D,R>刚好可以被G整除(模2)
• 接收端检错：利用G除<D,R>，余式全0，无错；否则，有错
• 可以检测所有突发长度小于r+1位差错

广泛应用于实际网络 (以太网，802.11 WiFi，ATM)

CRC举例：

多路访问控制(MAC)协议

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

用于：单一共享广播信道
当信道中两个或者两个以上结点同时传输，产生干扰(interference)冲突

理想MAC协议
给定：速率为R bps的广播信道

期望：

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

MAC协议分类

信道划分(channel partitioning)MAC协议

• 多路复用技术：TDMA、FDMA、CDMA、WDMA等

随机访问(random access)MAC协议

• 信道不划分，允许冲突；采用冲突“恢复”机制

轮转(“taking turns”)MAC协议

• 结点轮流使用信道

信道划分MAC协议
TDMA

• “周期性”接入信道
• 每个站点在每个周期，占用固定长度的时隙(e.g.长度=分组传输时间)
• 未用时隙空闲(idle)

FDMA

• 信道频谱划分为若干频带(frequency bands)
• 每个站点分配一个固定的频带
• 无传输频带空闲

随机访问MAC协议

当结点要发送分组时：

• 利用信道全部数据速率R发送分组
• 没有事先的结点间协调

两个或多个结点同时传输：➜ “冲突”

随机访问MAC协议需要定义：

• 如何检测冲突
• 如何从冲突中恢复 (eg：通过延迟重传)

典型的随机访问MAC协议：

• 时隙(sloted)ALOHA
• ALOHA
• CSMA、CSMA/CD、CSMA/CA

时隙ALOHA协议

假定：

• 所有帧大小相同
• 时间被划分为等长的时隙(每个时隙可以传输1个帧)
• 结点只能在时隙开始时刻发送帧结点间时钟同步
• 如果2个或2个以上结点在同一时隙发送帧，结点即检测到冲突

运行：

• 当结点有新的帧时，在下一个时隙(slot)发送
• 如果无冲突：该结点可以在下一个时隙继续发送新的帧
• 如果冲突：该结点在下一个时隙以概率p重传该帧，直至成功

最大效率= 1/e = 0.37

ALOHA协议
非时隙(纯)Aloha：更加简单，无需同步
当有新的帧生成时，立即发送
冲突可能性增大

最大效率=1/(2e) = 0.18

CSMA协议——载波监听多路访问协议

• 发送帧之前，监听信道：
  • 信道空闲：发送完整帧
  • 信道忙：推迟发送

冲突可能仍然发生：信号传播延迟
继续发送冲突帧：浪费信道资源

CSMA/CD协议——边发边听，不发不听

• 短时间内可以检测到冲突
• 冲突后传输中止，减少信道浪费

冲突检测：

• 有线局域网易于实现：测量信号强度，比较发射信号与接收信号
• 无线局域网很难实现：接收信号强度淹没在本地发射信号强度下

CSMA/CD效率

轮转访问MAC协议

信道划分MAC协议：

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

随机访问MAC协议：

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

轮转访问MAC协议综合两者的优点

轮询(polling)：主结点轮流“邀请”从属结点发送数据

令牌传递(token passing)：控制令牌依次从一个结点传递到下一个结点

• 令牌：特殊帧

存在问题：

• 令牌开销
• 等待延迟
• 单点故障

MAC协议总结

—————————————————————————————————————————————————————
由于水平有限及时间仓促或疏忽大意以及其他的一些原因，文中难免会存在一些错误，如若有发现不正确的地方，还请大佬们评论或私信告之于我，以便及时纠错