第五章 数据链路层

概述

• 数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据报
• 链路层服务
  组帧（framing）、链路接入（link access）、相邻结点间可靠交付、流量控制（flow control）、差错检测（error detection）、差错纠正（error correction）、全双工和半双工通信控制

差错检测

差错编码的基本原理

在数据基础上增加冗余信息，冗余信息在数据的位和位之间建立起了原本不存在的关联关系.
D→DR，其中，R为差错检测与纠正比特（冗余比特）.
差错编码不能保证100%可靠.

检错码和纠错码:

对于检错码，如果编码集的汉明距离$$d_s=r+1$$，则该差错编码可以检测r位的差错;
对于纠错码，如果编码集的汉明距离$$d_s=2r+1$$，则该差错编码可以纠正r位的差错.

常用的差错编码

奇偶校验码

• 1比特校验位：检测奇数位差错
  50％
  效率高
• 二维奇偶校验：
  检测奇数位差错、部分偶数位差错；
  纠正同一行/列的奇数位错
  

Internet校验和（Checksum）

循环冗余校验码（CRC）

• 检错能力更强大的差错编码
• 将数据比特，D，视为一个二进制数
• 选择1个r+1位的比特模式（生成比特模式），G
• 目标：选择r位的CRC比特，R，满足
  • <D,R>刚好可以被G整除（模2）
  • 接收端检错：利用G除<D,R>,余式全0，无错；否则，有错！
  • 可以检测所有突发长度小于r+1位差错
• 例题
  期望：D2^r XOR R = nG
  相当于:D2^r = nG XOR R
  相当于：如果利用G去除D*2^r，则余式即为R
  R=余式[(?∗?^?)/?]
  
  $$进位不进，借位不借or相同为0，不同为1$$

多路访问控制(MAC)协议

概述

点对点链路

• 拨号接入的PPP
• 以太网交换机与主机间的点对点链路

广播链路（共享介质）

• 早期的总线以太网（同轴电缆）
• HFC的上行链路
• 802.11无线局域网

信道划分MAC协议

特点：

1. 无传输频带空闲
2. 网络负载重，信道利用率高；网络负载轻，信道利用率低。
3. 不冲突

TDMA

FDMA

CDMA

WDMA

随机访问MAC协议

特点：

信道不划分，允许冲突
采用冲突“恢复”机制
利用信道全部数据速率R发送分组
没有事先的结点间协调
网络负载重，产生冲突开销；网络负载轻，信道利用率高。

时隙ALOHA

• 结点只能在时隙开始时刻发送帧
• 冲突：
  • 如果2或2个以上结点在同一时隙发送帧，结点检测到冲突
  • 如果冲突：该节点在下一个时隙以概率P重传该帧，直至成功。

ALOHA

• 当有新的帧生成时立即发送

CSMA

• 载波监听多路访问协议 CSMA (carrier sense multiple access)
• 发送帧之前，监听信道 (载波)：
  • 信道空闲：发送完整帧
  • 信道忙：推迟发送
    • 1-坚持CSMA
    • 非坚持CSMA
    • P-坚持CSMA
• 示意图
  

CSMA/CD

• CSMA/CD: CSMA with Collision Detection：“边发边听，不发不听”
  短时间内可以检测到冲突
  冲突后传输中止，减少信道浪费
  CSMA/CD应用于以太网
• 冲突检测:
  • 有线局域网易于实现：测量信号强度，比较发射信号与接收信号
  • 无线局域网很难实现：接收信号强度淹没在本地发射信号强度下
• 示意图
  
• 举例分析
  
• 计算例题
  
• 效率
  Tprop = LAN中2个结点间的最大传播延迟
  ttrans = 最长帧传输延迟
  tprop 趋近于0或者ttrans 趋近于∞时，效率趋近于1
  远优于ALOHA，并且简单、分散！
  

CSMA/CA

CSMA/CA应用802.11无线局域网。
见下面802.11无线局域网部分。

轮转MAC协议

结点轮流使用信道

轮询(polling):

• 主结点轮流“邀请” 从属结点发送数据
• 典型应用：“哑(dumb)” 从属设备
• 问题：
  • 轮询开销
  • 等待延迟
  • 单点故障

令牌传递(token passing):

• 控制令牌依次从一个结点传递到下一个结点.
• 令牌：特殊帧
• 问题：
  • 令牌开销
  • 等待延迟
  • 单点故障

ARP协议

MAC地址（Media Access Control Address）

• 简介：直译为媒体访问控制地址，也称为局域网地址（LAN Address），以太网地址（Ethernet Address）或物理地址（Physical Address），它是一个用来确认网上设备位置的地址。在OSI模型中，第三层网络层负责IP地址，第二层数据链接层则负责MAC地址。MAC地址用于在网络中唯一标示一个网卡，一台设备若有一或多个网卡，则每个网卡都需要并会有一个唯一的MAC地址。
  48位MAC地址(用于大部分LANs)，固化在网卡的ROM中，有时也可以软件设置
• 形式：48位 16进制 -减号
  e.g. : 1A-2F-BB-76-09-AD（16进制）
• 功能
  用于局域网内标识一个帧从哪个接口发出，到达哪个物理相连的其他接口（下一跳地址）

ARP

• 地址解析协议：
  就是主机在发送帧前将目标IP地址转换成目标MAC地址的过程。
• ARP表
  LAN中的每个节点均维护一个ARP表。
  用于存储节点的地址映射关系（IP，MAC，TTL）。
  经过TTL之后，该映射关系会被舍弃。（典型20分钟）
• 局域网内ARP通信过程：

1. A想给同一局域网内的B发送数据报；B的MAC地址不在A的ARP表中
2. A广播ARP查询分组，其中包含B的IP地址；目的MAC地址 = FF-FF-FF-FF-FF-FF，LAN中所有结点都会接收ARP查询
3. B接收ARP查询分组，IP地址匹配成功，向A应答B的MAC地址；利用单播帧向A发送应答。
4. A在其ARP表中，缓存B的IP-MAC地址对，直至超时；超时后，再次刷新。

• 从一个LAN路由至另一个LAN的通信过程：
  A通过路由器R向B发送数据报，跨LAN进行通信。
  
  1.A构造IP数据报，其中源IP地址是A的IP地址，目的IP地址是B的IP地址；
  2.A构造链路层帧，其中源MAC地址是A的MAC地址，目的MAC地址是R(左)接口的MAC地址，封装A到B的IP数据报。
  3.帧从A发送至R；
  4.R接收帧，提取IP数据报，传递给上层IP协议；
  5.R转发IP数据报（源和目的IP地址不变）；
  6.R创建链路层帧，其中源MAC地址是R(右)接口的MAC地址，目的MAC地址是B的MAC地址，封装A到B的IP数据报。

以太网

以太网

• 物理拓扑
  • 总线
    节点点直接连接到一个共用的半双工的线性网络上。
    所有节点在同一冲突域(collision domain) (可能彼此冲突)。
  • 星型
    中心交换机(switch)
    每个节点一个单独冲突域(间彼此不冲突)。
    主要应用于IEEE 802.2、IEEE 802.3标准的以太网中。
• 不可靠、无连接服务
• 以太网协议：采用二进制指数退避算法的CSMA/CD
• 以太网：CSMA/CD算法
  1.NIC从网络层接收数据报，创建数据帧
  2.如果NIC监听到信道空闲，则开始发送帧；如果NIC监听到信道忙， 则一直等待到信道空闲，然后发送帧。
  3.NIC发送完完整的帧，而没有检测到其他结点的数据发送，则NIC确认帧发送成功
  4.如果NIC检测到其他结点传输数据，则中止发送，并发送堵塞信号
  5.中止发送后，NIC进入二进制指数退避
  6.第m次连续冲突后：取n = Min(m, 10)，NIC从{0,1,2,…,2^n-1}中随机选择一个数K，NIC等待K*512比特的传输延迟时间，再返回第2步；连续冲突次数越多，平均等待时间越长。
• 以太网帧结构
  在以太网链路上的数据包称作以太帧。
  以太帧起始部分由前导码和帧开始符组成。后面紧跟着一个以太网报头，以MAC地址说明目的地址和源地址。帧的中部是该帧负载的包含其他协议报头的数据包(例如IP协议)。以太帧由一个32位冗余校验码结尾。它用于检验数据传输是否出现损坏。

前导码(Preamble)(8B):一般不算
7个字节的10101010，第8字节为10101011
用于发送端与接收端的时钟同步
目的MAC地址、源MAC地址(各6B):
如果网卡的MAC地址与收到的帧的目的MAC地址匹配，或者帧的目的MAC地址为广播地址(FF-FF-FF-FF-FF-FF)，则网卡接收该帧，并将其封装的网络层分组交给相应的网络层协议。
否则，网卡丢弃(不接收)该帧。
类型(Type)(2B)：
指示帧中封装的是哪种高层协议的分组(如，IP数据报、Novell IPX数据报、AppleTalk数据报等)
数据(Data)(46-1500B)：
指上层协议载荷。
（计算为什么是46：R=10Mbps，RTTmax=512μs，Lmin / R = RTTmax
Lmin=512bits=64B，Datamin=Lmin-18=46B）
CRC(4B)：
循环冗余校验码——丢弃差错帧

以太网交换机

• 透明(Transparent)：主机感知不到交换机的存在
• 即插即用(Plug&Play)
• 自学习：交换机无需配置
• 交换机缓存帧
• 交换机在每段链路上利用CSMA/CD收发帧，但无冲突，可全双工；每段链路一个独立的冲突域。
• 交换(Switching)：A-A’与B-B’的传输可以同时进行，但没有冲突。
• 交换表：
  • 与路由表相似，每个交换机有一个交换表(Switch table)，每个入口(Entry):（主机的MAC地址，到达主机的接口，时间戳）
  • 交换机通过自学习获知接口信息
    • 收到帧时，交换机“学习”到发送帧的主机，位于收到该帧的接口所连接的LAN网段；
    • 将发送主机的MAC地址/接口记录到交换表中。
• 目的MAC地址位置未知：泛洪
• 比较
  

虚拟局域网VLAN

• 支持VLAN划分的交换机，可以在一个物理LAN上配置多个VLAN。可以实现广播域隔离。
• 在VLAN间转发：通过路由，如同在独立的交换机之间
• 中继端口：在跨越多个物理交换机定义的VLAN承载帧。
  为多VLAN转发802.1帧容易产生歧义，必须携带VLANID信息；802.1q协议为经过中继端口转发的帧增加/去除额外的首部域。

PPP协议

• 无需介质访问控制
• 无需明确的MAC地址
• 例如：拨号链路，ISDN链路
• 常见的点对点数据链路控制协议
  HDLC（高级数据链路控制）
  PPP

功能：

1.组帧：将网络层数据报封装到数据链路层帧中
可以同时承载任何网络层协议分组(不仅IP数据报)
可以向上层实现分用（多路分解）
2.比特透明传输：数据域必须支持承载任何比特模式
3.差错检测：(无纠正)
4.连接活性检测：检测、并向网络层通知链路失效
5.网络层地址协商：端结点可以学习/配置彼此网络地址
无需差错纠正/恢复、无需流量控制 、不存在乱序交付 、无需支持多点链路 。

PPP数据帧

标志(Flag): 定界符(delimiter)
地址(Address): 无效(仅仅是一个选项)
控制(Control): 无效；未来可能的多种控制域
协议(Protocol): 上层协议 (eg, PPP-LCP, IP, IPCP, etc)
信息(info): 上层协议分组数据
校验(check): CRC校验，用于差错检测

注：还可以省掉地址1和控制1.

字节填充（Byte Stuffing）

• 发送端: 在数据中的<01111110>和<01111101>字节前添加额外的字节<01111101> (“填充(stuffs)”)
• 接收端:
  单个字节<01111101>表示一个填充字节；
  连续两个字节<01111101>：丢弃第1个，第2个作为数据接收
  单个字节<01111110>: 标志字节

802.11无线局域网

• 均使用CSMA/CA多路访问控制协议 ;
  均有基础设施(基站)网络模式和特定网(自组网)网络模式 .

• 802.11：多路访问控制
  避免冲突: 2+结点同时传输
  802.11: CSMA – 发送数据前监听信道 (避免与正在进行传输的其他结点冲突)
  802.11: 不能像CSMA/CD那样，边发送、边检测冲突！
  · 无线信道很难实现
  · 无法侦听到所有可能的冲突：隐藏站、信号衰落
  · 目标: 避免冲突(avoid collisions)-CSMA/C(ollision)A(voidance)

IEEE 802.11 MAC协议: CSMA/CA

• 802.11 sender
  1 if 监听到信道空闲了DIFS时间，then发送整个帧(无同时检测冲突，即CD)
  2 if 监听到信道忙，then 开始随机退避计时 ，当信道空闲时，计时器倒计时 ；当计时器超时时，发送帧 ；if 没有收到ACK，then 增加随机退避间隔时间 ，重复第2步 。
• 802.11 receiver
  if 正确接收帧 ，延迟SIFS时间后，向发送端发送ACK (由于存在隐藏站问题)
  
• 避免冲突
  基本思想：允许发送端“预约”(reserve)信道，而不是随机发送数据帧，从而避免长数据帧的冲突 。
  发送端首先利用CSMA向BS发送一个很短的RTS (request-to-send)帧。（RTS帧仍然可能彼此冲突 (但RTS帧很短) ）；
  BS广播一个CTS(clear-to-send)帧作为对RTS的响应 ；
  CTS帧可以被所有结点接收（消除隐藏站影响；发送端可以发送数据帧 ；其他结点推迟发送 ）。
  

IEEE 802.11 MAC帧

• 802.11数据帧地址
  802.11数据帧有4个地址字段
  地址 4 用于自组网络
  地址1~地址3：