链路层与局域网

《链路层与局域网》由会员分享，可在线阅读，更多相关《链路层与局域网（100页珍藏版）》请在金锄头文库上搜索。

1、数据链路层与局域网,1,第5章 链路层与局域网 Link Layer and LANs,计算机网络：自顶向下方法 (原书第三版) 陈鸣译，机械工业出版社，2005年 Computer Networking: A Top Down Approach Featuring the Internet, 3rd edition. Jim Kurose, Keith Ross Addison-Wesley, July 2004.,数据链路层与局域网,2,第5章 链路层和局域网,我们的目标: 理解支撑数据链路层服务的原则: 差错检测, 纠正 共享广播信道: 多路访问 链路层编址 可靠数据传输, 流量控制:

2、前面已分析过 各种链路层技术实例与实现,数据链路层与局域网,3,第5章 链路层,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址,5.5 以太网 5.6 集线器和交换机 5.7 PPP 5.8 链路虚拟化: ATM和MPLS,数据链路层与局域网,4,链路层: 概述,某些术语: 主机和路由器是节点 连接沿通信路径的相邻节点的路径是链路 有线链路 无线链路 局域网 第二层的分组叫帧, 封装数据报,数据链路层具有经一条链路从一个节点传输数据到相邻节点的能力,数据链路层与局域网,5,链路层: 相关内容,使用不同的链路协议经不同的链路传输数据报: 如第一段链路是以太网，

3、中间链路是帧中继，最后链路是 802.11 每个链路协议 提供不同的服务 可能或不能经链路提供可靠数据传输,运输类比 从 Princeton到 Lausanne的旅行 豪华轿车: Princeton到JFK 飞机: JFK到Geneva 火车: Geneva到Lausanne 旅行者 = datagram 运输各段 = 通信链路 运输模式 = 链路层协议 旅行代理人= 选路算法,数据链路层与局域网,6,链路层 Services,帧, 链路访问: 将数据报封装进帧，加上首部和尾部 如果共享媒体，信道访问 位于帧首部的“MAC”地址标识源、目的地 不同于IP地址! 相连节点间的可靠交付 我们已经知

4、道如何做了 (第三章)! 在比特差错低的链路很少使用 (光纤，某些双绞线) 无线链路: 高差错率 问题: 为什么同时使用链路级和端到端可靠性?,数据链路层与局域网,7,链路层服务(续),流量控制: 相邻发送和接收节点间的步调一致 差错检测: 差错由信号衰减、噪声所致 接收方检测差错的存在 信号发送方负责重传或丢弃帧 纠错: 接收方识别和纠正比特差错，而不采取重传 半双工 and 全双工 使用半双工, 链路的两端节点能够传输，但不能同时,数据链路层与局域网,8,适配器通信,在“适配器”(又称为NIC)中实现链路层 以太网卡，PCMCI卡, 802.11卡 发送侧: 将数据报封装在帧中 增加差错检

5、测比特，可靠数据传输，流量控制, 等,接收侧 查找差错，可靠数据传输，流量控制, 等 提取数据报，传递到接收节点 适配器是半自治的 链路和物理层,发送节点,接收节点,数据报,适配器,适配器,链路层协议,数据链路层与局域网,9,第5章 链路层,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址,5.5 以太网 5.6 集线器和交换机 5.7 PPP 5.8 链路虚拟化: ATM和MPLS,数据链路层与局域网,10,差错检测,EDC= 差错检测和纠错 bits (冗余) D = 数据由差错校验保护，可能包括首部字段 差错检测不是100%可靠! 协议可能漏掉某些差错，

6、但是非常少 较大的EDC字段产生更好的检测和纠正,数据链路层与局域网,11,奇偶校验,单比特奇偶校验: 检测单个比特差错,二维比特奇偶校验: 检测和纠正单个比特差错,0,0,奇偶 比特,奇偶差错,奇偶差错,可纠正的单比特差错,无差错,数据链路层与局域网,12,互联网检查和,发送方: 将段内容作为16比特整数序列来处理 检查和: 段内容相加(补码和) 发送方将检查和的值放入 UDP 检查和字段,接收方: 计算接收到段的检查和 检查是否计算的检查和等于 检查和字段的值: NO 检测到差错 YES 没有检测到差错. 尽管如此，还可能有错。详情见后.,目标：检测传输段中的“差错” (如比特翻转) (注

7、意: 仅用于运输层),数据链路层与局域网,13,检查和:循环冗余码校验,将数据比特D看作一个二进制数 选择r+1比特模式(生成式), G 目标：选择r个CRC 比特R, 使得 被G整除 (以2为模) 接收方知道G, 用G除以. 如果有非零余数：检测到差错! 能够检测所有小于r+1比特的突发差错 广泛用于实践中 (ATM, HDCL),比特 模式,数学公式,被发送的数据比特,数据链路层与局域网,14,CRC例子,希望: D.2r XOR R = nG 等价为: D.2r = nG XOR R 等价为: 如果我们用G除以D.2r, 余数为 R,R = 余数 ,D.2r G,数据链路层与局域网,15

8、,第5章 链路层,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址,5.5 以太网 5.6 集线器和交换机 5.7 PPP 5.8 链路虚拟化: ATM和MPLS,数据链路层与局域网,16,多路访问链路和协议,两类 “链路”: 点对点 用于拨号接入的PPP 在以太网交换机和主机之间的点对点链路 广播 (共享线路或媒体) 传统的以太网 向上游的HFC 802.11无线LAN,数据链路层与局域网,17,多路访问协议,单一共享广播信道 节点的两个或更多的并行传输：干扰 碰撞 如果节点同时接收到两个或更多信号 多路访问协议 决定节点怎样共享信道的分布式算法，如决定何时

9、节点能够传输 有关信道共享的通信必须使用信道本身! 不用带外信道来协调,数据链路层与局域网,18,理想的多路访问协议,速率R bps的广播信道 1. 当一个节点可传输，它能够以速率R发送 2. 当M节点要传输，每个能以平均速率R/M发送 3. 全分散: 无特殊节点来协调传输 无同步时钟、时隙 4. 简单,数据链路层与局域网,19,MAC协议: 分类,三大类: 信道划分 将信道划分为较小的“段” (时隙，频率，编码) 为节点分配一部分专用 随即访问 不划分信道，允许碰撞 从“碰撞”恢复 “轮流” 节点轮流，但有更多信息要发送的能够轮流的较长时间,数据链路层与局域网,20,信道划分MAC协议: T

10、DMA,TDMA: 时分多路访问 ”循环“访问信道 每个站点在每个循环中获得固定长度时隙(长度=分组传输时间) 不使用的时隙空闲 例子：6个站点的LAN, 时隙1、3、4 有分组, 时隙2、5、6 空闲 TDM (Time Division Multiplexing): channel divided into N time slots, one per user; inefficient with low duty cycle users and at light load. FDM (Frequency Division Multiplexing): frequency subdivide

11、d.,数据链路层与局域网,21,信道划分 MAC协议: FDMA,FDMA: 频分多路访问 信道频谱划分为频带 每个站点分配固定的频带 频带中未使用的传输时间空闲 例子： 6个站点的LAN, 频带1、3、4 有分组, 频带2、5、6 空闲 TDM (Time Division Multiplexing): channel divided into N time slots, one per user; inefficient with low duty cycle users and at light load. FDM (Frequency Division Multiplexing): f

12、requency subdivided.,frequency bands,time,数据链路层与局域网,22,随即访问协议,当 站点有分组要发送 以信道全部速率R传输 节点间无优先权协调 两个或更多传输节点 “碰撞”, 随即访问MAC协议 定义了: 如何检测碰撞 如何从碰撞中恢复 (例如，经延迟的重新传输) 随即访问MAC协议的例子: 时隙ALOHA ALOHA CSMA, CSMA/CD, CSMA/CA,数据链路层与局域网,23,时隙ALOHA,假定 所有帧有相同长度 时间划分为等长时隙，能够传输1个帧 节点仅在时隙开始时开始传输帧 节点是同步的 如果2个或多个节点在时隙中传输，所有节点检

13、测碰撞,操作 当节点获得新帧，将在下一个时隙中传输 无碰撞，节点能够在下一个时隙中发送新帧 如果碰撞，节点在每个后继时隙中以概率p重传帧知道成功,数据链路层与局域网,24,时隙ALOHA,优点 单个活跃节点能够连续地以信道的全速传输 高速分散：仅节点中的时隙需要同步 简单,缺点 碰撞，浪费时隙 空闲时隙 节点可能能够以小于传输分组的时间检测到碰撞 时钟同步,数据链路层与局域网,25,时隙Aloha效率,假定N个有许多帧要发送节点，每个时隙以概率p发送 节点1在一个时隙中成功发送的概率= p(1-p)N-1 任何节点成功发送的概率= Np(1-p)N-1,对N节点为使效率最大化，求p* 使得Np

14、(1-p)N-1最大化 对许多节点，当N趋近无穷大，取Np*(1-p*)N-1 极限, 得到1/e = 0.37,效率是当有许多节点，且每个都有许多帧要发送时，成功时隙与总时隙的长期比值,最多: 信道用于有用传输的时间是37%！,数据链路层与局域网,26,纯(非时隙)ALOHA,非时隙Aloha: 更简单，无同步要求 当帧首个到达 立即传输 碰撞的概率增加: 在t0 发送与在t0-1,t0+1发送的其他帧碰撞,将于i帧起始部分重叠,将于i帧结束部分重叠,数据链路层与局域网,27,纯Aloha效率,P(给定节点成功) = 节点传输) . P(在p0-1,p0中无其他节点传输) = p . (1-

15、p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) 选择最适合的p并令 n - infty . = 1/(2e) = 0.18,甚至更差 !,数据链路层与局域网,28,CSMA (载波侦听多路访问),CSMA: 在传输前侦听: 如果侦听到信道空闲: 传输整个帧 如果侦听到信道忙, 推迟传输 人类类比: 不要打断他人说话!,数据链路层与局域网,29,CSMA碰撞,碰撞还是会出现 : 传播时延意味着两个节点也许不能听到其他节点传输,碰撞: 整个分组传输时间被浪费,节点的空间设置,注意: 距离与传播时延在决定碰撞概率岁的作用,空间,数据链路层与局域网,30,CSMA/CD (碰撞检

16、测),CSMA/CD: 载波侦听, 如同在CSMA 在短时间内检测到碰撞 碰撞的传输流产，减少信道浪费 碰撞检测: 在有线的LAN中容易: 测量信号强度，比较传输的和接收的信号 在无线LAN中困难：传输中接收方切断 人类类比: 礼貌的交谈者,数据链路层与局域网,31,CSMA/CD 碰撞检测,a=/T0, a越小，网络性能越好,空间,数据链路层与局域网,32,“轮流” MAC协议,信道划分 MAC协议: 在高负载时高效、公平地共享信道 低负载时低效：信道访问中延时，当1个活跃节点时，甚至仅有分配了 1/N 带宽! 随机访问 MAC协议 低负载是有效：单个节点能够全面利用信道 高负载：碰撞开销 “轮流”协议 兼有这方面的优点!,数据链路层与局域网,33,“轮流” MAC协议,轮询: 主节点“邀请”从节点依次传输 关注问题: 轮询开销 时延 单点故障(主节点),令牌传递: 控制令牌从一个节点顺序地传递到下一个. 令牌报文 关注问题: 令牌开销 时延 单点故障(令牌),数据链路层与局域