Computer Network Notes 6：A Top Down Approach
引论和服务
网络节点的连接方式
点到点连接
多点连接：共享型介质；通过网络交换机
数据链路层和局域网
WAN：网络形式采用点到点链路
- 贷款大、距离远 (延迟打)：贷款延迟积大
- 如果采用多点连接方式：竞争方式 (一旦冲突代价大)，令牌等协调方式 (在其中协调节点的发送代价大)
点到点的链路层服务实现非常简单，封装和解封装
LAN：一般采用多点连接方式
- 连接到节点非常方便
- 街道共享型介质上 (或网络交换机)，就可以连接所有其他节点
多点连接方式网络的链路层功能实现相当复杂
- 多点接入：协调各节点对共享型介质的访问和使用
- 竞争方式：冲突之后的协调
- 令牌方式：令牌产生、占有和释放等
链路层概述
术语
主机和路由器是节点 (网桥和交换机也是)：nodes
沿着通信路径，连接相邻节点通信信道的是链路：links
- 有线链路
- 无线链路
- 局域网，共享型链路
第二层协议数据单元帧 (frame)，封装数据报
数据链路层负责从一个节点通过链路将 (帧重点) 数据报发送到物理相邻节点
上下文
数据报 (分组) 在不同的链路上以不同的链路协议传送：
- 第一跳链路：以太网
- 中间链路：帧中继链路
- 最后一跳：802.11
不同的链路协议提供不同的服务，如在链路层上提供 (或没有) 可靠数据传送
链路层服务
成帧，链路接入：
- 将数据报封装在帧中，加上帧头、帧尾部
- 如果采用的是共享型介质，信道接入获得信道访问权
- 在帧头部使用 “MAC” (物理) 地址来标示源和目的 (不同于 IP 地址)
在相邻两个节点完成可靠数据传输
- 在低出错率的链路上 (光纤和双绞线电缆) 很少使用
- 出错率低，没有必要再每一个帧中做差错控制的工作，协议复杂
- 发送端对每一帧进行差错控制编码，根据反馈做相应的动作
- 接收端进行差错控制解码，反馈给发送端 (ACK，NAK)
- 在本层放弃可靠控制的工作，在网络层或传输层做可靠控制的工作，或根本不做可靠控制的工作
- 出错率低，没有必要再每一个帧中做差错控制的工作，协议复杂
- 在高差错链路上需要进行可靠的数据传送
- 高差错链路：无线链路
- 出错率高，如果在链路层不做差错控制工作，漏出去的错误比较高，到了上层如果需要可靠控制的数据传输代价会很大 (不做 local recovery 总体代价大)
流量控制：使得相邻的发送和接收方节点的速度匹配
错误检测：
- 差错由信号衰减和噪声引起
- 接收方检测出的错误：通知发送端进行重传或丢弃帧
差错纠正：接收端检查和纠正 bit 错误，不通过重传来纠正错误
半双工和全双工
- 半双工：链路可以双向传输，但一次只有一个方向
- 全双工：两个方向可以同时
链路层实现位置
在每一个主机上，也在每个路由器上，交换机的每个端口上
链路层功能在 “适配器” 上实现 (network interface card, NIC) 或在一个芯片组上
- 以太网卡，802.11 网卡；以太网芯片组
- 实现链路层和相应的物理层功能
接到主机的系统总线上
硬件、软件和固件的综合体
适配器通信
发送方
- 在帧中封装数据报
- 加上差错控制编码，实现 RDT 和流量控制功能等
接收方
- 检查有无出错，执行 RDT 和流量控制功等
- 解封装数据报，将其交给上层
适配器是半自治的，实现了链路和物理层功能
差错检测和纠正
错误检测
EDC = 差错检测和纠正位 (冗余位)
D = 数据由差错检测保护，可以包含头部字段
错误检测不是 100% 可靠的：
- 协议会漏间一些错误 (很少)
- 更长的 EDC 字段可以得到更好的检测和纠正效果
奇偶校验
单 bit 奇偶校验：检测单个 bit 级错误
2 维奇偶校验：检测和纠正单个 bit 错误
检验和：CRC (循环冗余校验)
将数据比特 D 看作二进制的数据
生成多项式 G：双方协商 r+1 位模式 (r 次方)：生成和检验所使用的位模式
目标：选择 r 位 CRC 附加位 R，使得：
- <D, R> 正好被 G 整除 (modulo 2)
- 接收方直到 G，将 <D, R> 除以 G，如果非 0 余数，检查出错误
- 能检出所有少于 r+1 位的突发错误
实际应用：以太网、802.11 WiFi、ATM
CRC 例子：
多点访协议
多路访问链接和协议
两种类型的链路 (一个子网内部链路链接形式)
点对点
- 拨号访问的 PPP
- 以太网交换机和主机之间的点对点链路
广播 (共享线路或媒体)
- 传统以太网
- HFC 上行链路
- 802.11 无线局域网
多路访问协议
单个共享的广播型链路
2 个或更多站点同时传送：冲突 (collision)，多个节点在同一个时刻发送，则会收到 2 个或多个信号叠加
多路访问协议 (介质访问控制协议：MAC)
分布式算法：决定节点如何使用共享信道，即决定节点什么时候可以发送
关于共享控制的通信必须借助信道本身传输
- 没有带外的信道，各节点使用其协调信道使用
- 用于传输控制信息
理想的多路访问协议
给定：R bps 的广播信道
必要条件：
- 当一个节点要发送时，可以 R 速率发送
- 挡 M 个节点要发送，每个可以以 R/M 的平均速率发送
- 完全分布的：没有特殊节点协调发送，没有时钟和时隙的同步
- 简单
MAC (媒体访问控制) 协议分类
信道划分：
- 把信道划分成小片 (时间、频率、编码)
- 分配片给每个节点专用
随机访问：
- 信道不划分，允许冲突
- 冲突后恢复
依次轮流：
- 节点依次轮流
- 有很多数据传输的节点可以获得较长的信道使用权
信道划分 MAC 协议
TDMA
TDMA： timd division multiple access
- 轮流使用信道，信道的时间分为周期
- 每个站点使用每周期中固定的时隙 (长度 = 帧传输时间) 传输帧
- 如果站点无帧传输，时隙空闲 -> 浪费
- eg. 6 站 LAN，1、3、4 有数据报，时隙 2、5、6 空闲
FDMA
FDMA： frequency division multiple access
- 信道的有效频率范围被分成一个个小的频段
- 每个站点被分配一个固定的频段
- 分配给站点的频段如果没有被使用，则空闲
码分多路访问 (CDMA)
CDMA：code division multiple access
- 所有站点在整个频段上同时进行传输，采用编码原理加以区分
- 完全无冲突
- 假定：信号同步很好，线性叠加
随机存取协议
当节点有帧要发送时
- 以信道带宽的全部 R bps 发送
- 没有节点间的预先协调
两个或更多节点同时传输，会发生冲突 (collision)
随机存取协议规定：
- 如何检测冲突
- 如何从冲突中恢复 (如，通过稍后的重传)
随机 MAC 协议
- 时隙 ALOHA
- ALOHA
- CSMA，CSMA/CD，CSMA/CA
时隙 ALOHA
假设
- 所有帧是等长的
- 时间被划分成相等的时隙，每个时隙可发送一帧
- 节点支在时隙开始时发送帧
- 节点在时钟上是同步的
- 如果两个或多个节点在一个时隙传输，所有的站点都能检测到冲突
运行
- 当节点或去新的帧，在下一个时隙传输
- 传输时没有检测到冲突，成功：节点能够在下一时隙发送新帧
- 传输时检测到冲突，失败：节点在每一个随后的时隙以概率 p 重传帧直到成功
优点
- 节点可以以信道带宽全速连续传输
- 高度分布：仅需要节点之间在时隙上的同步
- 简单
缺点
- 存在冲突，浪费时隙
- 即使有帧要发送，仍然有可能存在空闲的时隙
- 节点检测冲突的时间 < 帧传输的时间，必须传完
- 需要时钟上同步
效率：当有很多节点，每个节点有很多帧要发送时，x % 的时隙是成功传输帧的时隙
纯 ALOHA (非时隙)
无时隙 ALOHA：简单、无须节点间在时间上同步
当有帧需要传输：马上传输
冲突的概率增加：
CSMA 冲突
冲突仍然可能发生：由传播延迟造成，节点可能侦听不到正在进行的传输
冲突：整个冲突帧的传输时间都被浪费了，是无效传输
传播延迟 (距离) 决定了冲突的概率
节点依据本地的信道使用情况来判断全部信道的使用情况
CSMA/CD (冲突检测)
CSMA/CD：
- 载波侦听 CSMA：和在 CSMA 中一样发送钱侦听信道
- 没有传完一个帧就可以在短时间内检测到冲突
- 冲突发送时则传输终止，减少对信道的浪费
冲突检测 CD 技术，有线局域网中容易实现：
- 检测信号强度，比较传输与接收到的信号是否相同
- 通过周期的过零点检测
以太网 CSMA/CD 算法
- 适配器获取数据报，创建帧
- 发送前：侦听信道 CS
- 闲：开始传送帧
- 忙：一直等到闲再发送
- 发送过程中，冲突检测 CD
- 没有冲突：成功
- 检测到冲突：放弃，之后尝试重发
- 发送方适配器检测到冲突，除放弃外，还发送一个 Jam 信号，所有听到冲突的适配器也是如此。
- 强化冲突：让所有站点都知道冲突
- 如果放弃，适配器进入指数退避状态
- 在第 m 次失败后，适配器随机选择一个 {0, 1, 2,…, 2^(m-1)} 中 K，等待 K*512 位时，然后转到步骤 2
- exponential backoff：二进制指数退避算法
指数退避
- 目标：适配器试图适应当前负载，在一个变化的碰撞窗口中随机选择时间点尝试重发
- 高负载：重传窗口时间打，减少冲突，但等待时间长
- 低负载：使得个站点等待时间少，但冲突概率大
- 例：
CSMA/CD 效率
无线局域网 CSMA/CA
WLAN 构成
- 基站：AP
- 无线链路
- 移动主机节点
冲突：2+ 站点 (AP 或者站点) 在同一个时刻发送
802.11：CSMA-发送前侦听信道；不会和其他节点正在进行的传输发生冲突
802.11：没有冲突检测
- 无法检测冲突：自身信号远远大于其它节点信号
- 即使能 CD：冲突 ！= 不成功
- 目标：avoid collisions (CSMA/CollisionAvoudance)
- 无法 CD，一旦发送一股脑全部发送完毕，不 CD
- 为避免无 CD 带来的信道利用率低的问题，事前进行冲突避免
发送方：
- 如果站点侦测到信道空闲持续 DIFS 长，则传输整个帧 (no CD)
- 如果侦测到信道忙碌，则选择一个随机回退值，并在信道空闲时递减该值；如果信道忙碌，回退值不会变化。倒数到 0 时 (只生在信道闲时) 发送整个帧。如果没有收到 ACK，增加回退值，重复 2
802.11 接收方：
- 如果帧正确，则在 SIFS 后发送 ACK
- 无线链路特定，需要每帧确认；由于隐藏终端问题，在接收端可能形成干扰，接收方没有正确地接收到 (链路层可靠机制)
在 count down 时，真听到了信道空闲为什么不发送，而要等到 0 再发送：
- 2 个站点有数据帧需要发送，第三个节点正在发送
- LAN CD：让 2 者听到第三个节点发完，立即发送
- 冲突：放弃当前的发送，避免了信道浪费于无用冲突帧的发送
- 代价不昂贵
- WLAN CA
- 无法 CD，一旦发送就必须发完，如冲突信道浪费严重，代价高昂
- 思想：尽量实现避免冲突，而不是在发生冲突时放弃然后重发
- 听到发送的站点，分别选择随机值，回退到 0 发送：不同随机值，一个站点会胜利；失败站点会冻结计数器，当胜利节点发完再发
无法完全避免冲突
冲突避免
思想：允许发送方 “预约” 信道，而不是随机访问该信道；避免长数据帧的冲突 (可选)
- 发送方首先使用 CSMA 向 BS 发送一个雄安的 RTS 分组：RTS 可能会冲突，但由于比较短，浪费信道较少
- BS 广播 clear-to-send CTS，作为 RTS 的响应
- CTS 能够被所有涉及到的节点听到：发送方发送数据帧；其它节点抑制发送
采用雄安的预约分组可以完全避免数据帧的冲突
线缆接入网络
多个 40 Mbps 下行 (广播) 信道，FDM
- 下行：通过 FDM 分成若干信道，互联网、数字电视等
- 互联网信道：只有 1 个 CMTS 在其上传输
多个 30 Mbps 上行的信道，FDM
- 多路访问：所有用户使用；结者 TDM 分成微时隙
- 部分时隙：分配；部分时隙；竞争
DOCSIS: TMD 上行信道
- 采用 TDM 的方式将上行信道分成若干微时隙：MAP 指定
- 站点采用分配给它的微时隙上行微时隙：分配
- 在特殊的上行微时隙中，个站点请求上行微时隙：竞争
- 个站点对于该时隙的使用时随机访问的
- 一旦碰撞 (请求不臣工，结果是再下行的 MAP 中没有为它分配，则二进制退避) 选择时隙上传输
轮流 (Taking Turns) MAC 协议
轮询
主节点邀请从节点依次传送
从节点一般比较 “dumb”
缺点：
- 轮询开销：轮询本身消耗信道带宽
- 等待时间：每个节点需等到主节点轮询后开始传输，即使只有一个节点，也许要等到轮询一周后才能够发送
- 单点故障：主节点失效时造成整个系统无法工作
令牌传递
控制令牌 (token) 循环从一个节点到下一个节点传递
令牌报文：特殊的帧
缺点：
- 令牌开销：本身消耗带宽
- 延迟：只有等到抓住令牌，才可传输
- 单点故障 (token)：
- 令牌丢失系统级故障，整个系统无法传输
- 复杂机制重新生成令牌
MAC 协议总结
多点介入问题：对于一个共享型介质，各个节点如何协调对它的访问和使用？
- 信道划分：按时间、频率或编码
- TDMA, FDMA, CDMA
- 随机访问 (动态)
- ALOHA, S-ALOHA, CSMA, CSMA/CD
- 载波侦听：有线介质很容易，无线介质比较困难
- CSMA/CD：802.3 Ethernet 网中使用
- CSMA/CA：802.11 WLAN 中使用
- 依次轮流协议
- 集中 (有一个中心节点轮询)；分布 (通过令牌控制)
- 蓝牙、FDDI、令牌环