计算机网络自顶向下方法第五章讲义教材.ppt

计算机网络,2014年9月 国防科技学院,第5章 链路层和局域网,,计算机网络,我们的目标: 理解支撑数据链路层服务的原则: 差错检测, 纠正 共享广播信道: 多路访问 链路层编址 可靠数据传输, 流量控制: 前面已分析过 各种链路层技术实例与实现,第5章 链路层和局域网,5.1 概述与服务 5.2 差错检测和纠错 5.3 多路访问协议 5.4 链路层编址 5.5 以太网 5.6 链路层交换机 5.7 PPP 5.8 链路虚拟化,某些术语: 主机和路由器是节点 连接沿通信路径的相邻节点的路径是链路 有线链路 无线链路 局域网 第二层的分组叫帧, 封装数据报,数据链路层具有经一条链路从一个节点传输数据到相邻节点的能力,链路层: 概述,使用不同的链路协议经不同的链路传输数据报: 如第一段链路是以太网，中间链路是帧中继，最后链路是 802.11 每个链路协议 提供不同的服务 可能或不能经链路提供可靠数据传输,运输类比 从普林斯顿到洛桑的旅行 豪华轿车:普林斯顿到JFK 飞机: JFK到日内瓦 火车:日内瓦到洛桑 旅行者 = datagram 运输各段 = 通信链路 运输模式 = 链路层协议 旅行代理人= 选路算法,链路层: 相关内容,成帧, 链路访问: 将数据报封装进帧，加上首部和尾部 如果共享媒体，信道访问 位于帧首部的“MAC”地址标识源、目的地 不同于IP地址! 相连节点间的可靠交付 在比特差错低的链路很少使用 (光纤，某些双绞线) 无线链路: 高差错率 问题: 为什么同时使用链路级和端到端可靠性?,链路层服务,流量控制: 相邻发送和接收节点间的步调一致 差错检测: 差错由信号衰减、噪声所致 接收方检测差错的存在 信号发送方负责重传或丢弃帧 纠错: 接收方识别和纠正比特差错，而不采取重传 半双工 and 全双工 使用半双工, 链路的两端节点能够传输，但不能同时,链路层服务(续),在“适配器”(又称为NIC)中实现链路层 以太网卡，PCMCIA卡, 802.11卡 发送侧: 将数据报封装在帧中 增加差错检测比特，可靠数据传输，流量控制, 等,接收侧 查找差错，可靠数据传输，流量控制, 等 提取数据报，传递到接收节点 适配器是半自治的 链路和物理层,发送节点,,,,,,接收节点,,数据报,,适配器,适配器,,链路层协议,,网络适配器实现链路层通信,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址 5.5 以太网 5.6 链路层交换机 5.7 PPP 5.8 链路虚拟化,EDC= 冗余数据 D = 信息数据 差错检测不是100%可靠 较大的EDC字段产生更好的检测和纠正,差错检测基本原理,发送方：信息数据+冗余数据 接收方：检查信息数据和冗余数据的关系，发现差错,单比特奇偶校验: 检测单个比特差错,二维比特奇偶校验: 检测和纠正单个比特差错,,0,,0,奇偶 比特,奇偶差错,奇偶差错,可纠正的单比特差错,无差错,奇偶校验,专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。

发送方: 将段内容作为16比特整数序列来处理 检查和: 段内容相加(补码和) 发送方将检查和的值放入 UDP 检查和字段,接收方: 计算接收到段的检查和 检查是否计算的检查和等于 检查和字段的值: NO – 检测到差错 YES – 没有检测到差错. 尽管如此，还可能有错详情见后….,互联网检查和,计算步骤: 求和，回卷，求反,循环冗余校验码CRC是计算机网络和数据通信中使用最为广泛的检错码之一 检错能力强 （硬件）实现简单 广泛用于实践中 (ATM, HDLC),循环冗余码校验,比特 模式,数学公式,被发送的数据比特,CRC原理,将待发送的位串D看成系数为 0 或 1 的多项式,收发双方约定一个生成多项式 G(x) 发送方用位串D及 G(x)进行某种运算得到校验和R，并在帧的末尾加上校验和，使带校验和的帧的多项式(D+R)能被 G(x) 整除 接收方收到后，用 G(x) 除多项式，若有余数则传输有错CRC-16 ：x16+x15+x2+1,CRC-8 : x8+x2+x+1,例：D=101110000 D(x)=1x8 + 0x7 + 1x6 + 1x5 + 1x4 + 0x3 + 0x2 + 0x + 0x0 = x8 + x6 + x5 + x4,希望: D.2r XOR R = nG 等价为: D.2r = nG XOR R 等价为: 如果我们用G除以D.2r, 余数为 R,R = 余数[ ],D.2r G,,,CRC例子,多项式除法：模2除法（具体使用模2减法，即模2加法）,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址 5.5 以太网 5.6 链路层交换机 5.7 PPP 5.8 链路虚拟化,两类 “链路”: 点对点 用于拨号接入的PPP 在以太网交换机和主机之间的点对点链路 广播 (共享线路或媒体) 传统的以太网 向上游的HFC 802.11无线LAN,多路访问链路和协议,单一共享广播信道 节点的两个或更多的并行传输：干扰 碰撞 如果节点同时接收到两个或更多信号 多路访问协议 决定节点怎样共享信道的分布式算法，如决定何时节点能够传输 有关信道共享的通信必须使用信道本身! 不用带外信道来协调,多路访问协议,速率R bps的广播信道 1. 当一个节点要传输，它能够以速率R发送 2. 当M节点要传输，每个能以平均速率R/M发送 3. 全分散: 无特殊节点来协调传输 无同步时钟、时隙 4. 简单,理想的多路访问协议,三大类: 信道划分 将信道划分为较小的“段” (时隙，频率，编码) 为节点分配一部分专用 随机访问 不划分信道，允许碰撞 从“碰撞”恢复 轮流协议 节点轮流，但有更多信息要发送的能够轮流的较长时间,MAC协议: 分类,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 subdivided.,信道划分MAC协议: TDMA,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): frequency subdivided.,,,,,,,,,frequency bands,time,信道划分 MAC协议: FDMA,当 站点有分组要发送 以信道全部速率R传输 节点间无优先权协调 两个或更多传输节点➜ “碰撞”, 随即访问MAC协议 定义了: 如何检测碰撞 如何从碰撞中恢复 (例如，经延迟的重新传输) 随即访问MAC协议的例子: 时隙ALOHA ALOHA CSMA, CSMA/CD, CSMA/CA,随机访问协议,假定 所有帧有相同长度 时间划分为等长时隙，能够传输1个帧 节点仅在时隙开始时开始传输帧 节点是同步的,操作 当节点获得新帧，将在下一个时隙中传输 无碰撞，节点能够在下一个时隙中发送新帧 如果碰撞，节点在每个后继时隙中以概率p重传帧,时隙ALOHA,优点 单个活跃节点能够连续地以信道的全速传输 高速分散：仅节点中的时隙需要同步 简单,缺点 碰撞，浪费时隙 空闲时隙 节点可能能够以小于传输分组的时间检测到碰撞 时钟同步,时隙ALOHA,假定N个有许多帧要发送节点，每个时隙以概率p发送 节点1在一个时隙中成功发送的概率= p(1-p)N-1 任何节点成功发送的概率= Np(1-p)N-1,对N节点为使效率最大化，求p* 使得Np(1-p)N-1最大化 对许多节点，当N趋近无穷大，取Np*(1-p*)N-1 极限, 得到1/e = 0.37,效率是当有许多节点，且每个都有许多帧要发送时，成功时隙与总时隙的长期比值,最多: 信道用于有用传输的时间是37%！,时隙Aloha效率,非时隙Aloha: 更简单，无同步要求 当帧首个到达 立即传输 碰撞的概率增加: 在t0 发送与在[t0-1,t0+1]发送的其他帧碰撞,将于i帧起始部分重叠,将于i帧结束部分重叠,纯(非时隙)ALOHA,纯ALOHA的效率仅为 时隙ALOHA效率的一半,CSMA: 在传输前侦听: 如果侦听到信道空闲: 传输整个帧 如果侦听到信道忙, 推迟传输 人类类比: 不要打断他人说话!,CSMA(载波侦听多路访问),碰撞还是会出现 : 传播时延意味着两个节点也许不能听到其他节点传输,碰撞: 整个分组传输时间被浪费,节点的空间设置,注意: 距离与传播时延在决定碰撞概率的作用,空间,CSMA碰撞,CSMA/CD: 载波侦听, 如同在CSMA 在短时间内检测到碰撞 碰撞的传输流产，减少信道浪费 碰撞检测: 在有线的LAN中容易: 测量信号强度，比较传输的和接收的信号 在无线LAN中困难：无线节点为了节省能源，Frame发送完毕后就会关闭而没有载波 人类类比: 礼貌的交谈者,CSMA/CD,a=τ/T0, a越小，网络性能越好,空间,CSMA/CD碰撞检测,信道划分 MAC协议: 在高负载时高效、公平地共享信道 低负载时低效：信道访问中延时，当1个活跃节点时，甚至仅有分配了 1/N 带宽! 随机访问 MAC协议 低负载是有效：单个节点能够全面利用信道 高负载：碰撞开销 “轮流”协议 兼有这方面的优点!,“轮流” MAC协议,轮询协议: 主节点“邀请”从节点依次传输 关注问题: 轮询开销 轮询延迟 单点故障(主节点),令牌协议: 控制令牌从一个节点顺序地传递到下一个. 令牌报文 关注问题: 令牌开销 时延 单点故障(令牌),“轮流” MAC协议,对共享媒体你需要做些什么? 信道划分, 通过时间、频率或编码 时分, 频分 随机划分 (动态的), ALOHA, S-ALOHA, CSMA, CSMA/CD 载波侦听: 在某些技术(有线)中容易，在另一些(无线)中困难 CSMA/CD 用在以太网中 CSMA/CA 用在 802.11中 轮流 从中心站点轮询，令牌传递,MAC协议小结,数据链路层前面讲过: 服务, 差错检测/纠正, 多路访问 下面: LAN技术 编址 以太网 集线器, 交换机 PPP,LAN技术,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址 5.5 以太网 5.6 链路层交换机 5.7 PPP 5.8 链路虚拟化,两台机器A和B,它们IP地址分别是IA、 IB ，物理地址分别是PA和PB 高层程序仅希望与IP地址交往，而实际通信必须使用物理地址,,,,,,,,,,,,IP4,IA,PA,HA4,HA3,HA2,,,HA5,PB,IP5,,,A,B,IP2,,R1,R2,以太网 2,以太网 1,FDDI 网,,,,IP 层上的互联网,,IP 数据报,MAC 帧,IB,IP3,MAC 帧,MAC 帧,问题： A如何从B的IP地址得到它的物理地址PB？,地址转换问题,32-bit IP地址: 网络层地址 用于使数据报到达目的IP子网 MAC(或LAN 或。