“本文总结了链路层的基本知识点，有助于学习者快速了解链路层知识架构，老手快速复习链路层相关知识。”

思维导图 

基本概念

• 结点nodes:主机、路由器
• 链路links：连接相邻结点的信道。eg:有线链路、无线链路、局域网
• 数据单位：帧frame，MAC地址
• IP地址：门牌号，不可移动，可改变
• MAC地址：身份证，可移动，一般不改变——网卡
• 链路接入：共享介质需要解决接入问题

差错编码

基本分类

• 分类：检错码+纠错码
• 编码集汉明距离：集合元素中最小不同比特位数之和
• 例如：{0000，0101，1010，1111}汉明距离d=2
• 检错码：编码集汉明距离d=r+1，纠错r位错误

• 纠错码：编码集合汉明距离d=2r+1，纠错r位错误

Internet校验和(Checksum)

• 发送端：data划分为16位二进制整数——补码求和sum(最高位进1返回最低位继续加)——checksum=sum的反码——tcp\udp\ip分组字段(ip是头部校验、tcp\udp是data校验)
• 接收端：check=16位全0——无错

循环冗余校验码CRC

奇偶校验码

• 50%的校验能力

多路访问控制协议MAC

• MAC(multiple access control protocol)
• 本质原因：广播链路——共享介质
• 分类：
• 信道划分MAC:TDMA、FDMA、CDMA
• 随机访问MAC:不划分信道、+允许冲突、冲突恢复机制
• 轮转MAC

信道划分MAC

• 划分不同频段，比如1-2GHZ，2-3GHZ

随机访问MAC

• 基本概念：全部速率R发送分组→冲突问题→冲突检测+冲突恢复
• 时隙ALOHA(slot):
  • 假定:所有frame大小相同,time被划分为等长的时隙slot
  • 运行：冲突后，冲突结点在下一个slot以概率P重传
  • 需要同步
  • max效率：1/e=0.37

• ALOHA:
  • 不需要同步
  • 新帧生成就发送→冲突可能性增大
  • max效率=1/2e=0.18

• CSMA协议：
  • 载波感知多路访问协议(carrier sense multiple access)
  • 机制：发送frame之前，监听信道
  • 信道空闲：发送完整帧
  • 信道忙：推迟发送
    • 1坚持=一直监听
    • 非坚持=随机监听
    • p坚持=概率监听
  • 冲突发生:信号传播延迟导致
• CSMA/CD协议：
  • CD(collision detection)
  • 边发边听，不发不听

• 带宽R，帧长度min=L，信号传播速度V——L/R≥2dmax/v
• 极端情况，A-B瞬时冲突，帧传输必须正在进行才能监听，最短时间为2d=RTT

 轮转访问MAC协议

• 方式
• 主节点轮询polling：master轮流询问属下的计算机是否发送数据

• 令牌(特殊帧)传递：持令牌者可发送数据，master定时检测令牌存在性，更新丢失令牌

MAC总结

• 信道划分MAC：TDMA、FDMA、CDMA
• 随机访问MAC:CSMA/CD以太网、CSMA/CA无线局域网802.11、ALOHA
• 轮转访问MAC：蓝牙

ARP协议

• ARP(Address Resolution Protocol)
• MAC地址(LAN地址、物理地址)：48位——表示哪一个帧从哪一个网卡接口出发，在ROM中设定，特殊情况可以修改，但要保证LAN中唯一性；16进制表示。例如1C-2B-BB-14-35-AD(＃分隔也可)
• 局域网中每块网卡都有唯一MAC地址

• ARP表：MAC地址和IP地址的映射，LAN中每个结点(主机/路由维护一个表)
• ARP表格式：，超时则映射删除，可能网卡位置移动
• LAN内路由：
• ARP运作机制：A传数据给B，局域网广播请求B的IP对应的网卡MAC地址——应答——缓存MAC地址并传输
• LAN间路由：
• ARP运作机制：通过默认网关(路由器)接入，不同路由接口对应不同MAC地址访问

以太网

• 有限局域网
• 无连接(网卡之间没有握手)、不可靠(没有确认机制)
• 拓扑方式：总线(有冲突域)、星型(无冲突域)

• 以太网MAC协议：二进制指数退避的CSMA/CD
  • 网卡创建数据帧——监听
  • 监听——信道空闲——发送完整帧
  • 监听——信道繁忙——中止发送
  • m次连续冲突后，取n=Min{m，10}——网卡从{0，1，......，(2的N次方)-1}随机取一个K——网卡等待K·512bits(一个时间间隔是512bits)——再次监听
  • 连续冲突次数越多，等待时延越长
• 帧结构
  • 前导码proamble=8B(10101010x7+10101011)——Tx/Rx同步用
  • 目的MAC地址=6B，源MAC地址=6B
  • data=46-1500B

交换机

• 路由器：网络层设备，存储转发数据报分组，IP地址
• 交换机：链路层设备，存储转发数据帧分组，MAC地址
• 集线器：物理层设备
• 特点：主机无法感知、即插即用、自学习传输路径(收到帧即可得到上级MAC，未知路径则洪泛传播)

• 常见网络设备对比

虚拟局域网VLAN

• 基于端口(MAC地址也可以区分)的VLAN
  • 实现：交换机的不同端口——不同VLAN
  • 实际中交换机+路由器被集成

• 跨越交换机的VLAN

• 端口1和端口16为中继端口，传输时须携带VLAN ID！

802.11无线局域网

基础

• MAC协议：CSMA/CA
• AP(Access Point)接入点
• 接入方式：无线主机+AP关联(每个AP一个频段)
• 主机行为：至少与一个AP关联，可能需要身份认证(如WIFI)，获取AP(SSID服务集标识符，MAC信标帧beacon)——例如：运行DHCP获取IP。
• 主机AP关联：主动扫描(主机发送请求帧)、被动扫描(AP发送beacon)
• CSMA/CA(Collision Avoidance)协议因为无线信号衰减问题无法做到边发边收，所以需要避免冲突

CSMA/CA过程

• 正常流程：
  • 信道空闲DIFS——发送方发送data整个帧——延迟SIFS——接收方发送ACK
• 发送方——监听信道忙——持续监听——随机退避计时——计时结束后——若信道空闲达DIFS——发送帧——如果没有收到ACK则增加退避时间继续监听

CA:RTS-CTS交换

• sender向基站发送RTS(Request-To-Send)(很短可忽略)——类似预约功能
• 基站广播CTS(Clear-To-Send)响应避免数据冲突

参考资料：bilibili哔哩哔哩 

💗 “骄傲的雄鹰从不为暴风颔首，折翼的天使向来不惧地狱的严冬。” 

                                                                ——Created By 是羽十八ya