计算机网络网络近期软件学院

1、第6讲 数据链路层之一6a-1第6讲: 数据链路层本讲目标: r了解数据链路层服务原理:m错误检测, 校正m共享广播信道m链路层编址m可靠数据传输, 流量控制: done!r各类链路层技术的实现和实例概述:r链路层的服务r错误检测, 校正r 多点访问技术和LANr链路层寻址, ARPr特定的链路层技术:m以太网m集线器, 网桥, 交换机mIEEE 802.11 LANsmPPPmATM第6讲 数据链路层之一6a-2链路层: 工作环境第6讲 数据链路层之一6a-3链路层: 工作环境r两个 物理上连接的 设备:m主机-路由器, 路由器-路由器, 主机-主机r数据单元: frame（帧）applic

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

3、6讲 数据链路层之一6a-5链路层的服务 (续)r流量控制: m保持收发双方的同步r错误检测: m信号衰减和噪声会导致出错. m接收端检测到错误时: 给发送端信号要求重发或丢弃出错帧 r错误校正: m接受端检测多个位错并加以校正 而无需要求发送端重发第6讲 数据链路层之一6a-6链路层: 实现r通过 “adapter（网卡或适配器）” 实现me.g., PCMCIA 卡, 以太网卡 m一般适配器都含有: RAM, DSP 芯片, 主机的总线接口, 和链路接口applicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnH

4、tHnHlMHtHnHlframephys. linkdata linkprotocoladapter card第6讲 数据链路层之一6a-7错误检测EDC= 错误检测校正（Error Detection and Correction (冗余数据)）位D = 由检验位保护的数据, 可包括首部字段 错误检测不可能达到 100% 可靠! 协议算法可能会忽略了某些错误, 但比例极小 较大的 EDC 字段可以产生较好的检错和纠错效果第6讲 数据链路层之一6a-8奇偶校验单比特校验:检测一位错误检测一位错误两维单比特校验:检测和校正单比特错误检测和校正单比特错误00第6讲 数据链路层之一6a-9因特网校

5、验和发送端:r把数据段的内容看成一系列16-bit的整数r校验和: 对内容进行累加 (1s complement sum)r 发送端将校验和放入UDP 的checksum 字段接收端:r对接收到的数据段进行校验和计算r检查计算所得的校验和与接收到值的是否相等 :mNO 出错了mYES 没查出错误. 但有可能存在错误? .目的: 检测 数据段在传输过程中出现的错误 (注意: 仅用在传输层)第6讲 数据链路层之一 6a-10校验计算: 循环校验码r把数据比特串, D, 看成二进制数据r选择一个 r+1 bit 型 (generator), G r目的: 选择 r个 CRC位, R, 这样m 可为

6、G 整除(modulo 2) m接收端已知 G, 用G来除 . 如果余数不为0: 查出错误!m可以查出所有长度不超过r+1位的突发错误r在实践中被广泛应用 (ATM, HDCL)第6讲 数据链路层之一 6a-11CRC 举例如果要:D.2r XOR R = nG则等于:D.2r = nG XOR R 也就等于: 如果要让 D.2r 被 G整除, 则需要余数 RR = remainder D.2rG第6讲 数据链路层之一 6a-12多点访问链路和协议有三种类型的 “链路”:r点对点 ( e.g. PPP, SLIP)r广播式 (共享线路或介质; e.g, 以太网, 无线网, etc.)r交换式

7、(e.g., 交换式以太网, ATM etc)第6讲 数据链路层之一 6a-13多点访问协议r一条共享的通信信道 r两个或多个结点可同时发送信号: 相互干扰 m在某一时刻只有一个结点可以成功地发送信号 r多点访问协议:m分布式的算法来决定如何共享信道, i.e., 决定工作站何时可以发送m注意：有关共享通道的通信（协商）也必须在该通道自身上解决! m我们希望多点访问协议能够解决什么问题: 同步还是异步 了解其他站点的信息 健壮性 (e.g.如何对待信道错误) 性能第6讲 数据链路层之一 6a-14多点访问协议r断言: 人类在许多场合都使用多点访问协议 rclass can guess mult

8、iple access protocols mmultiaccess protocol 1:mmultiaccess protocol 2:mmultiaccess protocol 3:mmultiaccess protocol 4:第6讲 数据链路层之一 6a-15MAC 协议: 分类r通道分割m将信道分割成较小的 “片” (时隙, 频率)m将小片分给各站点使用r随机访问m允许冲突m从冲突中“恢复”r“排队排队”m严格协调访问来避免冲突目标: 高效, 公平, 简单, 分散控制第6讲 数据链路层之一 6a-16信道分割的 MAC 协议: TDMATDMA: time division mul

9、tiple access （时分多路）r“依次” 访问信道r每次每个站点分得固定长度的时隙 (时长 = 分组的单位传输时间)r未用的时隙被闲置和浪费 r例如: 6个站点的LAN, 1,3,4 有分组发送, 而 2,5,6的时隙则被闲置 第6讲 数据链路层之一 6a-17 信道分割的 MAC 协议: FDMAFDMA: frequency division multiple access（频分复用） r信道按频谱分成若干频段r每个站点分得固定的频段r在频段不用时该部分信道被闲置和浪费 r例如: 6各站点的 LAN, 1,3,4 发送分组, 而 2,5,6 的频段被闲置 frequency ban

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

11、6讲 数据链路层之一 6a-20CDMA: 两个用户互扰的情况第6讲 数据链路层之一 6a-21随机访问协议r当结点有数据要发送时：m使用信道全部的传输速率 R.m在诸多结点中不存在“预先”协商的机制r可能发生两个以上结点同时传输 - “冲突”r随机访问的 MAC协议定义了: m如何检测冲突m如何从冲突中恢复 (e.g., 通过延迟重发)r随机访问 MAC协议的实例:m时隙ALOHAmALOHAmCSMA and CSMA/CD第6讲 数据链路层之一 6a-22时隙 Alohar时间划分成等长的时隙 (=分组单元传送的时长)r对待新近到达的分组结点要: 在下一个时隙开始时传输 r如果冲突: 以

12、p的概率再后继的时隙重发分组，直到成功为止.(S)成功, (C)冲突, (E) 空闲的时隙第6讲 数据链路层之一 6a-23时隙 Aloha 的效率Q: 时隙的利用情况如何?A: 假设有 N站点有数据发送m每个站点以p的概率在时隙中传输数据m传输成功的概率 S为:对单个结点来说: S= p (1-p)(N-1) 对N个节点中的任何一个： S = 概率 (仅有一个站点传输的) = N p (1-p)(N-1) 选择最佳的 p 当 n - infty . = 1/e = .37最佳情况: 信道的使用率为 37%!第6讲 数据链路层之一 6a-24纯 (无时隙) ALOHAr无时隙 Aloha: 简

13、单, 没有同步信号r需要传输分组时:m 立即发送而不必等待时隙的开始r冲突的概率增加了:m在 t0 时刻发送的分组与在 t0-1, t0+1时刻发送的分组冲突第6讲 数据链路层之一 6a-25纯 Aloha (续)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 S = throughput = “goodput” (

14、success rate)G = offered load = Np0.51.01.52.00.10.20.30.4Pure AlohaSlotted Aloha协议 限制了信道吞吐量的有效利用!第6讲 数据链路层之一 6a-26CSMA: Carrier Sense Multiple AccessCSMA: （载波检测多路访问）发送前侦听:r如果信道闲置: 发送整个分组r如果信道忙, 推迟发送 m坚持性 CSMA: 当信道闲置时，以p的概率立即重试 (可能导致不稳定)m非坚持性 CSMA: 在某个随机间隔以后再试r为人处事的规则之一: 不要打断别人的发言!第6讲 数据链路层之一 6a-27C

15、SMA 的冲突冲突可能发生在:由于传播延迟两个节点可能听不到对方的发送冲突:整个分组的传输时间被浪费以太网结点间的时空图注意:这里的冲突概率是由距离和 传播延迟来决定的第6讲 数据链路层之一 6a-28CSMA/CD (Collision Detection，冲突检测)CSMA/CD:m在冲突发生后，短时间内可探测到m立即中断传输, 减少信道的时间浪费 m坚持性或非坚持性重传r冲突检测: m在有线 LAN中简便易行: 检测信号强度, 比较收、发的信号m在无线 LAN比较困难: 传输时接收器是关闭的r人类社会的范例: 彬彬有礼的交谈者 第6讲 数据链路层之一 6a-29CSMA/CD 冲突检测第6讲 数据链路层之一 6a-30“轮转式” MAC 协议信道分割的 MAC 协议:m在重负荷时共享信道的效率高m在轻负荷时效率低: 延迟了信道访问, 当只有一个结点激活时，分到的带宽只有信道带宽的1/N! 随机访问 MAC 协议m在轻负荷时有效率: 单个节点可以充分利用信道的 带宽m在重负荷下: 冲突的开销“轮转式”协议在两个方面寻求最佳的解决方案!第6讲 数据链路层之一 6a-31“轮转式” MAC 协议轮询（Polling）: r由主结点“邀请”从结点依次传输rRequest to Send, Clear to Send