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

1、计算机网络,2014年9月 国防科技学院,第5章 链路层和局域网,计算机网络,我们的目标: 理解支撑数据链路层服务的原则: 差错检测, 纠正 共享广播信道: 多路访问 链路层编址 可靠数据传输, 流量控制: 前面已分析过 各种链路层技术实例与实现,第5章 链路层和局域网,5.1 概述与服务 5.2 差错检测和纠错 5.3 多路访问协议 5.4 链路层编址 5.5 以太网 5.6 链路层交换机 5.7 PPP 5.8 链路虚拟化,某些术语: 主机和路由器是节点 连接沿通信路径的相邻节点的路径是链路 有线链路 无线链路 局域网 第二层的分组叫帧, 封装数据报,数据链路层具有经一条链路从一个节点传输

2、数据到相邻节点的能力,链路层: 概述,使用不同的链路协议经不同的链路传输数据报: 如第一段链路是以太网，中间链路是帧中继，最后链路是 802.11 每个链路协议 提供不同的服务 可能或不能经链路提供可靠数据传输,运输类比 从普林斯顿到洛桑的旅行 豪华轿车:普林斯顿到JFK 飞机: JFK到日内瓦 火车:日内瓦到洛桑 旅行者 = datagram 运输各段 = 通信链路 运输模式 = 链路层协议 旅行代理人= 选路算法,链路层: 相关内容,成帧, 链路访问: 将数据报封装进帧，加上首部和尾部 如果共享媒体，信道访问 位于帧首部的“MAC”地址标识源、目的地 不同于IP地址! 相连节点间的可靠交付

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

4、流量控制, 等 提取数据报，传递到接收节点 适配器是半自治的 链路和物理层,发送节点,接收节点,数据报,适配器,适配器,链路层协议,网络适配器实现链路层通信,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址 5.5 以太网 5.6 链路层交换机 5.7 PPP 5.8 链路虚拟化,EDC= 冗余数据 D = 信息数据 差错检测不是100%可靠 较大的EDC字段产生更好的检测和纠正,差错检测基本原理,发送方：信息数据+冗余数据 接收方：检查信息数据和冗余数据的关系，发现差错,单比特奇偶校验: 检测单个比特差错,二维比特奇偶校验: 检测和纠正单个比特差错,0,0,

5、奇偶 比特,奇偶差错,奇偶差错,可纠正的单比特差错,无差错,奇偶校验,专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。,发送方: 将段内容作为16比特整数序列来处理 检查和: 段内容相加(补码和) 发送方将检查和的值放入 UDP 检查和字段,接收方: 计算接收到段的检查和 检查是否计算的检查和等于 检查和字段的值: NO 检测到差错 YES 没有检测到差错. 尽管如此，还可能有错。详情见后.,互联网检查和,计算步骤: 求和，回卷，求反,循环冗余校验码CRC是计算机网络和数据通信中使用最为广泛的检错码之一。 检错能力强 （硬件）实现简单 广泛用于实践中 (ATM, HDLC),

6、循环冗余码校验,比特 模式,数学公式,被发送的数据比特,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 + 0 x7 + 1x6 + 1x5 + 1x4 + 0 x3 + 0 x2 + 0 x + 0 x0 = x8 + x6 + x

7、5 + 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,多路访问链路和协议,单一共享广播信

8、道 节点的两个或更多的并行传输：干扰 碰撞 如果节点同时接收到两个或更多信号 多路访问协议 决定节点怎样共享信道的分布式算法，如决定何时节点能够传输 有关信道共享的通信必须使用信道本身! 不用带外信道来协调,多路访问协议,速率R bps的广播信道 1. 当一个节点要传输，它能够以速率R发送 2. 当M节点要传输，每个能以平均速率R/M发送 3. 全分散: 无特殊节点来协调传输 无同步时钟、时隙 4. 简单,理想的多路访问协议,三大类: 信道划分 将信道划分为较小的“段” (时隙，频率，编码) 为节点分配一部分专用 随机访问 不划分信道，允许碰撞 从“碰撞”恢复 轮流协议 节点轮流，但有更多信息

9、要发送的能够轮流的较长时间,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):

10、 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 Multiplexi

11、ng): frequency subdivided.,frequency bands,time,信道划分 MAC协议: FDMA,当 站点有分组要发送 以信道全部速率R传输 节点间无优先权协调 两个或更多传输节点 “碰撞”, 随即访问MAC协议 定义了: 如何检测碰撞 如何从碰撞中恢复 (例如，经延迟的重新传输) 随即访问MAC协议的例子: 时隙ALOHA ALOHA CSMA, CSMA/CD, CSMA/CA,随机访问协议,假定 所有帧有相同长度 时间划分为等长时隙，能够传输1个帧 节点仅在时隙开始时开始传输帧 节点是同步的,操作 当节点获得新帧，将在下一个时隙中传输 无碰撞，节点能够在下

12、一个时隙中发送新帧 如果碰撞，节点在每个后继时隙中以概率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,效率是当有许多节点，且

13、每个都有许多帧要发送时，成功时隙与总时隙的长期比值,最多: 信道用于有用传输的时间是37%！,时隙Aloha效率,非时隙Aloha: 更简单，无同步要求 当帧首个到达 立即传输 碰撞的概率增加: 在t0 发送与在t0-1,t0+1发送的其他帧碰撞,将于i帧起始部分重叠,将于i帧结束部分重叠,纯(非时隙)ALOHA,纯ALOHA的效率仅为 时隙ALOHA效率的一半,CSMA: 在传输前侦听: 如果侦听到信道空闲: 传输整个帧 如果侦听到信道忙, 推迟传输 人类类比: 不要打断他人说话!,CSMA(载波侦听多路访问),碰撞还是会出现 : 传播时延意味着两个节点也许不能听到其他节点传输,碰撞: 整个

14、分组传输时间被浪费,节点的空间设置,注意: 距离与传播时延在决定碰撞概率的作用,空间,CSMA碰撞,CSMA/CD: 载波侦听, 如同在CSMA 在短时间内检测到碰撞 碰撞的传输流产，减少信道浪费 碰撞检测: 在有线的LAN中容易: 测量信号强度，比较传输的和接收的信号 在无线LAN中困难：无线节点为了节省能源，Frame发送完毕后就会关闭而没有载波 人类类比: 礼貌的交谈者,CSMA/CD,a=/T0, a越小，网络性能越好,空间,CSMA/CD碰撞检测,信道划分 MAC协议: 在高负载时高效、公平地共享信道 低负载时低效：信道访问中延时，当1个活跃节点时，甚至仅有分配了 1/N 带宽! 随

15、机访问 MAC协议 低负载是有效：单个节点能够全面利用信道 高负载：碰撞开销 “轮流”协议 兼有这方面的优点!,“轮流” MAC协议,轮询协议: 主节点“邀请”从节点依次传输 关注问题: 轮询开销 轮询延迟 单点故障(主节点),令牌协议: 控制令牌从一个节点顺序地传递到下一个. 令牌报文 关注问题: 令牌开销 时延 单点故障(令牌),“轮流” MAC协议,对共享媒体你需要做些什么? 信道划分, 通过时间、频率或编码 时分, 频分 随机划分 (动态的), ALOHA, S-ALOHA, CSMA, CSMA/CD 载波侦听: 在某些技术(有线)中容易，在另一些(无线)中困难 CSMA/CD 用在

16、以太网中 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,

17、R1,R2,以太网 2,以太网 1,FDDI 网,IP 层上的互联网,IP 数据报,MAC 帧,IB,IP3,MAC 帧,MAC 帧,问题： A如何从B的IP地址得到它的物理地址PB？,地址转换问题,32-bit IP地址: 网络层地址 用于使数据报到达目的IP子网 MAC(或LAN 或物理或以太网)地址: 用于使数据报从一个接口到达另一个物理连接的接口(同一个网络内) 48 bit MAC地址(对多数LAN) 烧在了适配器ROM中,MAC地址和ARP,在LAN中的每块适配器具有独特的LAN地址,广播地址 = FF-FF-FF-FF-FF-FF,= 适配器,LAN 编址和ARP,MAC地址分配

18、由IEEE管理 制造商购买部分MAC地址空间(确保惟一性) 类比: (a) MAC地址：像居民身份证号 (b) IP地址: 像邮政地址 MAC 扁平地址 可移动性 能够将LAN卡从一个LAN移动到另一个去 IP层次地址不可移动 取决于节点联系的子网,LAN地址(续),LAN上的每个IP节点(主机、路由器)都有ARP表 ARP表: 对某些LAN节点的IP/MAC地址映射 TTL (寿命): 地址映射将被忘记的时间长度(通常20分钟),1A-2F-BB-76-09-AD,58-23-D7-FA-20-B0,0C-C4-11-6F-E3-98,71-65-F7-2B-08-53,LAN,237.19

19、6.7.23,237.196.7.78,237.196.7.14,237.196.7.88,ARP: 地址解析协议,A要向B发送数据报, 并且B的MAC地址不在A的ARP表中. A广播ARP 请求分组, 包含B的IP地址 目的地MAC地址 = FF-FF-FF-FF-FF-FF 在 LAN上的所有机器接收ARP请求 B接收ARP分组，用它的MAC地址回答 A 帧发送到A的MAC地址 (单播),A在它的ARP表中缓存(保存) IP到MAC的地址对，直到信息变得超时 软状态: 信息超时除非被更新 ARP是“即插即用”: 节点创建它们的ARP表无需网络管理员干预,ARP协议: 相同的LAN (网络)

20、,目的: 从A到B经R发送数据报 假定A知道B的IP地址 在路由器R中有两个ARP表, 每张表对应一个IP网络 (LAN) In routing table at source Host, find router 111.111.111.110 In ARP table at source, find MAC address E6-E9-00-17-BB-4B, etc,A,R,B,选路到另一个LAN,A生成具有源A、目的地B的数据报 A使用ARP从111.111.111.110得到R的MAC地址 A生成以R的MAC地址作为目的地的链路层帧,帧包含A-to-B IP 数据报 A的适配器发送帧

21、B的适配器接收帧 R从以太网帧取出IP数据报，看到它目的地是B R使用ARP得到B的MAC地址 R生成包含A-to-B IP数据报的帧向B发送,A,R,B,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址 5.5 以太网 5.6 链路层交换机 5.7 PPP 5.8 链路虚拟化,“占支配性的” 有线LAN技术: 首先广泛使用的LAN技术 比令牌LAN和ATM更便宜 跟上了速率的竞赛: 10 Mbps 10 Gbps,Metcalfe的以太网草图,以太网,IEEE802.3 以太网标准 IEEE802.3u 100BASE-T快速以太网标准 IEEE802.3z

22、/ab 1000Mb/s千兆以太网标准 IEEE802.3ae 10GE以太网标准,48,70年代,80年代,90年代,以太网产生,10M以太网发展成熟,共享式转向LAN交换机,100M快速以太网,92年,96年,千兆以太网迅速发展,万兆以太网出现,2002年,以太网技术的发展,网络中所有主机的收发都依赖于同一套物理介质，即共享介质。 同一时刻只能有一台主机在发送，各主机通过遵循CSMA/CD规则来保证网络的正常通讯。,49,发送,监听,监听,监听,共享式以太网,扩展了网络带宽。 分割了网络冲突域，使得网络冲突被限制在最小的范围内。 交换机作为更加智能的交换设备，能够提供更多用户所要求的功能：

23、优先级、虚拟网、远程检测,50,交换式以太网,发送适配器在以太网帧(或其他网络层协议分组)中封装IP数据报 前导码: 模式为10101010 的7个字节，后跟模式为 10101011 的一个字节 用于同步接收方，发送方时钟速率,以太网帧结构,地址: 6字节 如果适配器接收具有匹配的目的地址或广播地址(如ARP分组)的帧, 它将帧中的数据提交给网络层协议 否则, 适配器丢弃帧 类型: 指示较高层协议 (大多数为IP但也可以支持其他类型如 Novell IPX和AppleTalk) CRC: 在接收方核对，如果检测到差错，该帧就被丢弃,以太网帧结构(续),以太网的一些标准,技术标准,线缆类型,10

24、Base5,100BaseTX,AUI(DB15)接口电缆,100BaseFX,EIA/TIA5类（UTP）非屏蔽双绞线2对,多模光纤（MMF）线缆,传输距离,500m,100m,550m-2km,2km-15km,单模光纤（SMF）线缆,1000BaseT,铜质EIA/TIA5类（UTP）非屏蔽双绞线4对,100m,1000BaseSX,多模光纤，使用波长为850nm的激光,550m/275m,1000BaseLX,单模光纤，使用波长为1310nm的激光,2km-15km,以太网物理接口,双绞线（网线）,RJ45（水晶头）,SC,光纤接口,LC,ST,FC,以太网使用CSMA/CD协议,CS

25、MA/CD协议原理 载波侦听：先听再说 适配器在发送前监听总线是否空闲，总线空闲则发送数据，不空闲则继续监听 冲突检测：边说边听 数据在发送的同时保持对总线的监听，发现冲突则停止发送 随机延迟后重发 冲突发生后，采用指数回退方法等待一段随机时间后，再进行监听和发送,指数回退方法: 目标：估计当前负载，适应重传尝试 重负载: 随机等待将更长 首次碰撞: 从0,1 中 选择K；时延是K 512 bit 传输时间 第二次碰撞后: 从0,1,2,3选择 K 10次碰撞后, 从0,1,2,3,4, 1023 选择K,以太网的CSMA/CD (续),用于10BaseT 每个比特具有一个跃迁 允许发送和接收

26、节点中的时钟互相同步 节点之间的集中式、全局时钟没有必要! 这是物理层事情!,曼彻斯特编码（以太网编码技术之一）,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址 5.5 以太网 5.6 链路层交换机 5.7 PPP 5.8 链路虚拟化,集线器基本上是物理层中继器 : 来自一条链路的比特从其他所有链路出去 以相同的速率 无帧缓存 在集线器中无CSMA/CD : 适配器检测碰撞 提供网络管理功能,集线器,主干集线器互联LAN网段 扩展节点之间的最大距离 但单独段碰撞域成为一个大的碰撞域,集线器,集线器,集线器,集线器,用集线器互联,交换一词最早出现于电话系统，特

27、指实现两个不同电话机之间话音信号的交换，完成该工作的设备就是电话交换机。 从本意上来讲，交换只是一种技术概念，即完成信号由设备入口到出口的转发。因此，只要是和符合该定义的所有设备都可被称为交换设备。 我们经常说到的以太网交换机实际是一个基于网桥技术的多端口第二层网络设备，它为数据帧从一个端口到另一个任意端口的转发提供了低时延、低开销的通路。 工作在链路层 即插即用，自学习 线速转发,交换机,按网络层次划分 第二层交换机（以太网交换机） 第三层交换机（路由交换机） 按网络构成方式 接入层交换机 汇聚层交换机 核心层交换机,交换机的分类,怎样决定向哪个LAN段上转发帧呢? 看起来像选路问题.,1,

28、2,3,转发,一个交换机具有一个交换机表（转发表） 交换机表中的项: (MAC地址, 接口, 时戳) 表中的陈旧项丢弃 交换机学习到通过哪个接口能够到达哪台主机 当帧收到, 交换机“得知” 发送方的位置 在交换机中记录了发送方/位置对,自学习,假定C向D发送帧,交换机从C接收帧 注意到交换机表中C位于接口1 因为D不在表中, 交换机将向接口2和3转发帧 D接收帧,集线器,集线器,集线器,交换机,A,B,C,D,E,F,G,H,I,地址,接口,A B E G,1 1 2 3,1,2,3,交换机例子,假定D回答C的帧,交换机从D接收帧 注意到在交换机表中D位于接口 2 因为C在表中, 交换机仅向接

29、口1转发帧 C接收帧,集线器,集线器,集线器,交换机,A,B,C,D,E,F,G,H,I,地址,接口,A B E G C,1 1 2 3 1,交换机例子,交换机安装将子网分割成LAN段 交换机过滤分组: 相同LAN段的帧通常不在其他LAN段上转发 段成为分离的碰撞域,碰撞域,碰撞域,碰撞域,交换机: 流量隔离,两者都是存储转发设备 路由器: 网络层设备(检查网络层首部) 交换机是链路层设备 路由器维护选路表，实现选路算法 交换机维护交换机表, 实现过滤、学习算法,交换机 vs. 路由器,5.1 概述与服务 5.2 差错检测和纠错 5.3多路访问协议 5.4 链路层编址 5.5 以太网 5.6

30、链路层交换机 5.7 PPP 5.8 链路虚拟化,一个发送方、一个接收方、一段链路：比广播链路容易处理: 无媒体访问控制 不需要明确的MAC编址 流行的点对点DLC协议: PPP (point-to-point协议) HDLC: 高级数据链路控制,点对点链路层控制,PPP（Point to Point Protocol）协议是在点对点链路上运行的数据链路层协议 用户使用拨号电话线接入Internet时，一般都是使用 PPP 协议 PPP协议支持用户的认证，是广域网接入使用最广泛的协议,PSTN,PPP协议,PPP协议概述,PPP主要包括三个部分 在串行链路上封装上层数据报文的方法 采用LCP（Link-Control Protocol，链路控制协议）来建立、控制数据链路 采用NCP（Network-Control Protocol，网络控制协议）来支持多种网络协议,物理介质（同/异步）,LCP,NCP,PPP,IP,IPX,其它网络协议,IPCP,IPXCP,其它NCP,网络层,数据链路层,物理层,PPP的组成