第6讲: 数据链路层 本讲目标: 概述: 了解数据链路层服务原理: 各类链路层技术的实现和实例 链路层的服务 错误检测, 校正 共享广播信道 链路层编址 可靠数据传输, 流量控制: done! 各类链路层技术的实现和实例 概述: 链路层的服务 错误检测, 校正 多点访问技术和LAN 链路层寻址, ARP 特定的链路层技术: 以太网 集线器, 网桥, 交换机 IEEE 802.11 LANs PPP ATM 第6讲 数据链路层之一

链路层: 工作环境 第6讲 数据链路层之一

链路层: 工作环境 两个 物理上连接的 设备: 数据单元: frame（帧） application transport network 主机-路由器, 路由器-路由器, 主机-主机 数据单元: frame（帧） application transport network link physical network link physical M H t n l 数据链路协议 H l H t n M frame 物理链路 接口卡 第6讲 数据链路层之一

链路层的服务 成帧, 链路访问: 在两台物理上连接的设备之间实现可靠传递: 将分组封装入帧, 加上帧头, 帧尾 如果是共享介质，则需实现信道的访问, ‘物理地址’ 放在帧首用来确定信源、信宿 不同于IP地址喔! 在两台物理上连接的设备之间实现可靠传递: 可靠传递是什么概念，回顾一下学过的知识! 不太用在误码率低的场合 (光纤, 某些双绞线) 无线链路: 误码率相当高 Q: 为什么在链路层和端到端之间都要做可靠性的校验? 第6讲 数据链路层之一

链路层的服务 (续) 流量控制: 保持收发双方的同步 错误检测: 信号衰减和噪声会导致出错. 接收端检测到错误时: 错误校正: 给发送端信号要求重发或丢弃出错帧 错误校正: 接受端检测多个位错并加以校正 而无需要求发送端重发 第6讲 数据链路层之一

链路层: 实现 通过 “adapter（网卡或适配器）” 实现 e.g., PCMCIA 卡, 以太网卡 一般适配器都含有: RAM, DSP 芯片, 主机的总线接口, 和链路接口 application transport network link physical network link physical M H t n l data link protocol H l H t n M frame phys. link adapter card 第6讲 数据链路层之一

错误检测 EDC= 错误检测校正（Error Detection and Correction (冗余数据)）位 错误检测不可能达到 100% 可靠! 协议算法可能会忽略了某些错误, 但比例极小 较大的 EDC 字段可以产生较好的检错和纠错效果 第6讲 数据链路层之一

奇偶校验 单比特校验: 检测一位错误 两维单比特校验: 检测和校正单比特错误 第6讲 数据链路层之一

因特网校验和 发送端: 目的: 检测 数据段在传输过程中出现的错误 (注意: 仅用在传输层) 接收端: 对接收到的数据段进行校验和计算 检查计算所得的校验和与接收到值的是否相等 : NO – 出错了 YES – 没查出错误. 但有可能存在错误? …. 发送端: 把数据段的内容看成一系列16-bit的整数 校验和: 对内容进行累加 (1’s complement sum) 发送端将校验和放入UDP 的checksum 字段 第6讲 数据链路层之一

校验计算: 循环校验码 把数据比特串, D, 看成二进制数据 选择一个 r+1 bit 型 (generator), G 目的: 选择 r个 CRC位, R, 这样 <D,R> 可为 G 整除(modulo 2) 接收端已知 G, 用G来除 <D,R>. 如果余数不为0: 查出错误! 可以查出所有长度不超过r+1位的突发错误 在实践中被广泛应用 (ATM, HDCL) 第6讲 数据链路层之一

CRC 举例 如果要: D.2r XOR R = nG 则等于: D.2r = nG XOR R 也就等于: 如果要让 D.2r 被 G整除, 则需要余数 R D.2r G R = remainder[ ] 第6讲 数据链路层之一

多点访问链路和协议 有三种类型的 “链路”: 点对点 ( e.g. PPP, SLIP) 广播式 (共享线路或介质; e.g, 以太网, 无线网, etc.) 交换式 (e.g., 交换式以太网, ATM etc) 第6讲 数据链路层之一

多点访问协议 一条共享的通信信道 两个或多个结点可同时发送信号: 相互干扰 多点访问协议: 在某一时刻只有一个结点可以成功地发送信号 分布式的算法来决定如何共享信道, i.e., 决定工作站何时可以发送 注意：有关共享通道的通信（协商）也必须在该通道自身上解决! 我们希望多点访问协议能够解决什么问题: 同步还是异步 了解其他站点的信息 健壮性 (e.g.如何对待信道错误) 性能 第6讲 数据链路层之一

多点访问协议 断言: 人类在许多场合都使用多点访问协议 class can "guess" multiple access protocols multiaccess protocol 1: multiaccess protocol 2: multiaccess protocol 3: multiaccess protocol 4: 第6讲 数据链路层之一

MAC 协议: 分类 通道分割 随机访问 允许冲突 从冲突中“恢复” “排队” 目标: 高效, 公平, 简单, 分散控制 将信道分割成较小的 “片” (时隙, 频率) 将小片分给各站点使用 随机访问 允许冲突 从冲突中“恢复” “排队” 严格协调访问来避免冲突 目标: 高效, 公平, 简单, 分散控制 第6讲 数据链路层之一

信道分割的 MAC 协议: TDMA TDMA: time division multiple access （时分多路） “依次” 访问信道 每次每个站点分得固定长度的时隙 (时长 = 分组的单位传输时间) 未用的时隙被闲置和浪费 例如: 6个站点的LAN, 1,3,4 有分组发送, 而 2,5,6的时隙则被闲置 第6讲 数据链路层之一

信道分割的 MAC 协议: FDMA FDMA: frequency division multiple access（频分复用） 信道按频谱分成若干频段 每个站点分得固定的频段 在频段不用时该部分信道被闲置和浪费 例如: 6各站点的 LAN, 1,3,4 发送分组, 而 2,5,6 的频段被闲置 frequency bands time 第6讲 数据链路层之一

信道分割 (CDMA) CDMA：Code Division Multiple Access（码分多路） 每个用户分得具有唯一性的 “code”; ie, 代码集合的分割 大部分应用在无线通信的场合 (cellular, satellite,etc) 所有用户共享相同的频道, 但每个用户用自己的“码片”序列 (ie, code) 对数据编码 编码信号 = (原始数据) X (码片序列) 解码: 编码信号的内积和码片序列 允许多个用户共存和发送信号,且相互的干扰极小 (假设信号码呈 “正交”状) 第6讲 数据链路层之一

CDMA 编码/解码 第6讲 数据链路层之一

CDMA: 两个用户互扰的情况 第6讲 数据链路层之一

随机访问协议 当结点有数据要发送时： 可能发生两个以上结点同时传输 -> “冲突” 随机访问的 MAC协议定义了: 使用信道全部的传输速率 R. 在诸多结点中不存在“预先”协商的机制 可能发生两个以上结点同时传输 -> “冲突” 随机访问的 MAC协议定义了: 如何检测冲突 如何从冲突中恢复 (e.g., 通过延迟重发) 随机访问 MAC协议的实例: 时隙ALOHA ALOHA CSMA and CSMA/CD 第6讲 数据链路层之一

时隙 Aloha 时间划分成等长的时隙 (=分组单元传送的时长) 对待新近到达的分组结点要: 在下一个时隙开始时传输 如果冲突: 以p的概率再后继的时隙重发分组，直到成功为止. (S)成功, (C)冲突, (E) 空闲的时隙 第6讲 数据链路层之一

时隙 Aloha 的效率 Q: 时隙的利用情况如何? … 选择最佳的 p 当 n -> infty ... A: 假设有 N站点有数据发送 每个站点以p的概率在时隙中传输数据 传输成功的概率 S为: 对单个结点来说: S= p (1-p)(N-1) 对N个节点中的任何一个： S = 概率 (仅有一个站点传输的) = N p (1-p)(N-1) … 选择最佳的 p 当 n -> infty ... = 1/e = .37 最佳情况: 信道的 使用率为 37% ! 第6讲 数据链路层之一

纯 (无时隙) ALOHA 无时隙 Aloha: 简单, 没有同步信号 需要传输分组时: 冲突的概率增加了: 立即发送而不必等待时隙的开始 在 t0 时刻发送的分组与在 [t0-1, t0+1]时刻发送的分组冲突 第6讲 数据链路层之一

纯 Aloha (续) … 选择最佳的 p 当 n -> infty ... = 1/(2e) = .18 P(给定节点的成功率) = P(节点传输) . P(无其他节点在 [p0-1,p0]时刻传输） . P(无其他节点在[p0-1,p0]时刻传输） = p . (1-p) . (1-p) P(在N结点中任意结点的成功率) = N p . (1-p) . (1-p) … 选择最佳的 p 当 n -> infty ... = 1/(2e) = .18 G = offered load = Np 0.5 1.0 1.5 2.0 0.1 0.2 0.3 0.4 Pure Aloha Slotted Aloha S = throughput = “goodput” (success rate) 协议 限制了信道吞吐 量的有效利用! 第6讲 数据链路层之一

CSMA: Carrier Sense Multiple Access 如果信道闲置: 发送整个分组 如果信道忙, 推迟发送 坚持性 CSMA: 当信道闲置时，以p的概率立即重试 (可能导致不稳定) 非坚持性 CSMA: 在某个随机间隔以后再试 为人处事的规则之一: 不要打断别人的发言! 第6讲 数据链路层之一

CSMA 的冲突 冲突可能发生在: 冲突: 注意: 由于传播延迟两个节点可能听不到对方的发送 整个分组的传输时间被浪费 以太网结点间的时空图 冲突可能发生在: 由于传播延迟两个节点可能听不到对方的发送 冲突: 整个分组的传输时间被浪费 注意: 这里的冲突概率是由距离和 传播延迟来决定的 第6讲 数据链路层之一

CSMA/CD (Collision Detection，冲突检测) 在冲突发生后，短时间内可探测到 立即中断传输, 减少信道的时间浪费 坚持性或非坚持性重传 冲突检测: 在有线 LAN中简便易行: 检测信号强度, 比较收、发的信号 在无线 LAN比较困难: 传输时接收器是关闭的 人类社会的范例: 彬彬有礼的交谈者 第6讲 数据链路层之一

CSMA/CD 冲突检测 第6讲 数据链路层之一

“轮转式” MAC 协议 信道分割的 MAC 协议: 在重负荷时共享信道的效率高 在轻负荷时效率低: 延迟了信道访问, 当只有一个结点激活时，分到的带宽只有信道带宽的1/N! 随机访问 MAC 协议 在轻负荷时有效率: 单个节点可以充分利用信道的 带宽 在重负荷下: 冲突的开销 “轮转式”协议 在两个方面寻求最佳的解决方案! 第6讲 数据链路层之一

“轮转式” MAC 协议 轮询（Polling）: 由主结点“邀请”从结点依次传输 令牌传递（Token passing）: 控制令牌依次通过各个结点 令牌报文 关注: 令牌的开销 等待时间 单点失效(token) 轮询（Polling）: 由主结点“邀请”从结点依次传输 Request to Send, Clear to Send 报文 关注: 轮询的开销 等待时间 单点失效 (主结点) 第6讲 数据链路层之一

基于预留的协议 分布式轮询（Distributed Polling）: 将时间划分成时隙 开始时使用N个较短的预留时隙 预留时隙的时长等于信道端对端的传播延迟 需发报文的站点先发预留信息 预留信息被所有其他站点接收到 在预留时隙后, 报文传输按已知的优先顺序进行 第6讲 数据链路层之一