数据链路层和局域网.ppt

第5章 数据链路层和局域网,主讲：韩爱庆Email:北京中医药大学信息中心,教程:计算机网络自顶向下方法(第4版)Jame F.Kurose,Keith W.Ross著,陈鸣译 机械工业出版社PPT英文原稿：Jim Kurose,Keith RossPPT中文翻译：韩爱庆，2009.8PPT翻译参考：计算机网络PPT，程向前，2008,计算机网络,教材,第6讲 数据链路层之一,6a-2,第5章 数据链路层和局域网,本讲目标:了解数据链路层服务原理:错误检测,校正共享广播信道链路层编址可靠数据传输,流量控制:done!各类链路层技术的实现和实例,概述:链路层的服务错误检测,校正 多点访问技术和LAN链路层寻址,ARP特定的链路层技术:以太网集线器,网桥,交换机,5:DataLink Layer,5-3,Link Layer,5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.4 Link-layer Addressing5.5 Ethernet,5.6 Link-layer switches5.7 PPP5.8 Link virtualization:ATM,MPLS,第6讲 数据链路层之一,6a-4,链路层:工作环境,第6讲 数据链路层之一,6a-5,链路层:工作环境,把沿着通信路径连接相邻节点的通信信道称为链路:主机-路由器,路由器-路由器,主机-主机数据单元:frame（帧）链路层协议任务：将网络层的数据报通过路径中的单端链路节点到节点的传送。,networklinkphysical,M,frame,物理链路,数据链路协议,接口卡,第6讲 数据链路层之一,6a-6,链路层的服务,成帧,链路接入:将分组封装入帧,加上帧头解决多路访问问题物理地址 放在帧首用来确定信源、信宿 不同于IP地址喔!在两台物理上连接的设备之间实现可靠交付:不太用在误码率低的场合(光纤,双绞线)无线链路:误码率相当高,第6讲 数据链路层之一,6a-7,链路层的服务(续),流量控制:保持收发双方的同步错误检测:信号衰减和噪声会导致出错.接收端检测到错误时:给发送端信号要求重发或丢弃出错帧 错误纠正:接受端检测多个位错并加以校正 而无需要求发送端重发,第6讲 数据链路层之一,6a-8,链路层:实现,通过“adapter（网卡或适配器）”实现,networklinkphysical,M,frame,phys.link,data linkprotocol,adapter card,5:DataLink Layer,5-9,Link Layer,5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.4 Link-layer Addressing5.5 Ethernet,5.6 Link-layer switches5.7 PPP5.8 Link virtualization:ATM,MPLS,第6讲 数据链路层之一,6a-10,差错检测和纠错,EDC=错误检测校正（Error Detection and Correction(冗余数据)）位D=由检验位保护的数据,可包括首部字段 错误检测不可能达到 100%可靠!协议算法可能会忽略了某些错误,但比例极小 较大的 EDC 字段可以产生较好的检错和纠错效果,第6讲 数据链路层之一,6a-11,奇偶校验,奇偶校验:检测单个的奇偶校验位,二维奇偶校验:通过检测和校正单比特错误,0,0,二维偶校验,1比特奇校验,第6讲 数据链路层之一,6a-12,检验和方法,发送端:把数据段的内容看成一系列16-bit的整数校验和:对内容进行累加(1s complement sum)发送端将校验和放入UDP 的checksum 字段,接收端:对接收到的数据段进行校验和计算检查计算所得的校验和与接收到值的是否相等:NO 出错了YES 没查出错误.但有可能存在错误?.,目的:检测 数据段在传输过程中出现的错误(注意:仅用在传输层),第6讲 数据链路层之一,6a-13,校验计算:循环校验码,自学 P287,5:DataLink Layer,5-14,Link Layer,5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.4 Link-layer Addressing5.5 Ethernet,5.6 Link-layer switches5.7 PPP5.8 Link virtualization:ATM,MPLS,5:DataLink Layer,5-15,Link Layer,5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.3.1 信道划分协议5.3.2 随机接入协议5.3.3 轮流协议5.3.4 局域网,5.4 Link-layer Addressing5.5 Ethernet5.6 Link-layer switches5.7 PPP5.8 Link virtualization:ATM,MPLS,第6讲 数据链路层之一,6a-16,多路访问链路和协议,有三种类型的“链路”:点对点(e.g.PPP)广播式(共享线路或介质;e.g,集线器以太网,无线网,etc.)交换式(e.g.,交换式以太网,ATM etc),第6讲 数据链路层之一,6a-17,多路访问协议,广播链路一条共享的通信信道 两个或多个结点可同时发送信号:相互干扰 在某一时刻只有一个结点可以成功地发送信号 多路访问协议:节点通过这些协议来规范它们在共享的广播信道上的传输行为。三种类型：信道划分协议随机接入协议轮流协议,第6讲 数据链路层之一,6a-18,信道划分协议:TDM,TDM:time division multiplexing（时分多路）“依次”访问信道每次每个站点分得固定长度的时隙(时长=分组的单位传输时间)未用的时隙被闲置和浪费 例如:6个站点的LAN,1,3,4 有分组发送,而 2,5,6的时隙则被闲置,第6讲 数据链路层之一,6a-19,信道分割协议:FDM,FDM:frequency division multiplexing（频分复用）信道按频谱分成若干频段每个站点分得固定的频段在频段不用时该部分信道被闲置和浪费 例如:6各站点的 LAN,1,3,4 发送分组,而 2,5,6 的频段被闲置,第6讲 数据链路层之一,6a-20,信道分割(CDMA),CDMA：Code Division Multiple Access（码分多路）每个节点分配一种不同的编码所有用户共享相同的频道,但每个用户用自己的“码片”序列(ie,code)对数据编码不同节点可同时发送，也可同时接收，不受其它节点干扰已经广泛用于民用，如手机,5:DataLink Layer,5-21,Link Layer,5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.3.1 信道划分协议5.3.2 随机接入协议5.3.3 轮流协议5.3.4 局域网,5.4 Link-layer Addressing5.5 Ethernet5.6 Link-layer switches5.7 PPP5.8 Link virtualization:ATM,MPLS,第6讲 数据链路层之一,6a-22,随机访问协议,当节点有数据要发送时：使用信道全部的传输速率 R.在诸多结点中不存在“预先”协商的机制可能发生两个以上结点同时传输-“冲突”随机访问的 MAC协议定义了:如何检测冲突如何从冲突中恢复(e.g.,通过延迟重发)随机访问协议的实例:时隙ALOHAALOHACSMA and CSMA/CD,第6讲 数据链路层之一,6a-23,时隙 Aloha,时间划分成等长的时隙(=分组单元传送的时长)对待新近到达的分组结点要:在下一个时隙开始时传输 如果冲突:以p的概率再后继的时隙重发分组，直到成功为止.,(S)成功,(C)冲突,(E)空闲的时隙,第6讲 数据链路层之一,6a-24,时隙 Aloha 的效率,Q:时隙的利用情况如何?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讲 数据链路层之一,6a-25,纯(无时隙)ALOHA,无时隙 Aloha:简单,没有同步信号需要传输分组时:立即发送而不必等待时隙的开始冲突的概率增加了:在 t0 时刻发送的分组与在 t0-1,t0+1时刻发送的分组冲突,第6讲 数据链路层之一,6a-26,纯 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,第6讲 数据链路层之一,6a-27,CSMA:载波侦听多路访问,CSMA:（载波侦听多路访问）发送前侦听:如果信道闲置:发送整个分组如果信道忙,推迟发送 坚持性 CSMA:当信道闲置时，以p的概率立即重试(可能导致不稳定)非坚持性 CSMA:在某个随机间隔以后再试为人处事的规则之一:不要打断别人的发言!,第6讲 数据链路层之一,6a-28,CSMA 的冲突,冲突可能发生在:由于传播延迟两个节点可能听不到对方的发送,冲突:整个分组的传输时间被浪费,以太网结点间的时空图,注意:这里的冲突概率是由距离和 传播延迟来决定的,第6讲 数据链路层之一,6a-29,CSMA/CD(Collision Detection，冲突检测),CSMA/CD:在冲突发生后，短时间内可探测到立即中断传输,减少信道的时间浪费 坚持性或非坚持性重传冲突检测:在有线 LAN中简便易行:检测信号强度,比较收、发的信号在无线 LAN比较困难:传输时接收器是关闭的人类社会的范例:彬彬有礼的交谈者,第6讲 数据链路层之一,6a-30,CSMA/CD 冲突检测,第6讲 数据链路层之一,6a-31,轮流协议,P297自学,6b-32,信道划分协议小结,对于共享介质可以做些什么?信道分割,按时间,频率或编码时分、码分、频分随机分割(动态)时隙ALOHA,ALOHA,CSMA,CSMA/CDCSMA/CD 被用在以太网中轮流协议,6b-33,LAN 技术,网络范围:LAN:Local Area NetMAN:Metropolitan Area NetWAN:Wide Area Net下面:讨论LAN 技术链路层编址以太网（Ethernet）集线器、交换机802.11无线LAN协议,6b-34,LAN 地址和 ARP,32位的IP地址:网络层 地址LAN(或MAC 或物理)地址:用来(在同一网络中)物理上互相连接的接口之间获取分组（或帧）48 位MAC 地址(绝大部分 LANs)烧制在适配器的 ROM中,6b-35,LAN 地址和 ARP,每个 LAN上的网卡都有具唯一性的LAN 地址,6b-36,LAN 地址(续),MAC 分配由 IEEE管理制造商购买部分MAC地址空间(以保证唯一性)比方:(a)MAC地址:美国人的社会保险号(b)IP地址:类似邮政地址 MAC 扁平结构=可以迁移 可以将 LAN卡从一个LAN换到另一个IP 具有层次结构，不可迁移 取决于某个站点接入的网络,网卡厂家查询：,6b-37,有关路由选择的讨论,A站点要给B站点发送IP分组：查找 B站点的网络地址,发现B站点与其在同一网络中给B站点发送的分组是通过链路层的帧来传送的,Bs MACaddr,As MACaddr,As IPaddr,Bs IPaddr,IP payload,分组,帧,帧的源、宿地址,分组的源、宿地址,6b-38,ARP:地址解析协议（Address Resolution Protocol）,每个LAN 上的IP 结点(主机,路由器)都有 ARP 模块,和表ARP 表:是某些LAN 结点的IP/MAC 地址映射 TTL(Time To Live):超过TTL的地址映射会被删除(一般为 20 分钟),6b-39,ARP 协议,A 知道 B的 IP 地址,需要了解B的物理地址 A 广播 ARP 查询帧,包含了 B的 IP地址 所有 LAN 的主机都收到 ARP 查询 B接收到 ARP帧,将其物理地址返回给A A 对收到的IP/MAC地址对进行缓存直到信息过期(超时)软状态:除非定期刷新，否则超时信息将被删除,6b-40,LAN之间的路由选择,穿越:经由R将A的数据传输到B在源主机的配置表中发现了路由器在源主机的ARP 表中,发现 MAC 地址E6-E9-00-17-BB-4B,etc,A,R,B,6b-41,A 创建了 IP分组，源地址为 A,宿地址为 B A 使用 ARP 来获取 R的与对应的物理地址A 创建了以R的物理地址为宿地址的以太网帧，该帧包含的A-to-B的 IP分组A的数据链路层发送以太网的帧 R的数据链路层接收到以太网的帧 R 从以太网帧中取出 IP分组,知道该分组的信宿为 BR使用ARP 来取得 B的物理层地址 R创建了包含了 A-to-B IP 分组的帧并发给 B,A,R,B,6b-42,以太网（Ethernet）,“统治”LAN的技术:不是一种具体的网络，是一种技术规范。CSMACD（带有碰撞检测的载波侦听多路访问）的访问控制方法主要有两种传输介质，那就是双绞线和光纤遵循IEEE 802.3标准IEEE 802.3的一些以太网络标准,6b-43,以太网帧结构,发送适配器将IP分组(或其他网络层协议分组)封装在以太网帧中Preamble（前同步码）:7 个 10101010 字节尾随一个 10101011字节 用来同步收发双方的时钟速率,6b-44,以太网帧结构(续),目的地址（destination address）:6 个字节,目的适配器的MAC地址源地址（source address）：源适配器的MAC地址类型（type field）:说明其上层协议,大部分为 IP，但其他协议如Novell IPX和 AppleTalk也支持数据字段（data field）：承载IP数据报。CRC:在接收端校验,如果出错，则将该帧丢弃,6b-45,以太网:应用CSMA/CD,A:检测信道,if 闲置 then 发送并检测信道;If 检测到了其他站点传输 then 中止传输并发送冲突信号;更新冲突 次数;按指数退避算法延迟发送;goto A else 帧发送结束;将冲突次数置0else 等待正在进行的传输结束并goto A,6b-46,以太网的 CSMA/CD(续),冲突信号（Jam Signal）:保证所有其他的收发器能够意识到发生的冲突;48 bits;指数退避（Exponential Backoff）:Goal目的:使得重发的企图能够与推测出的当前负载相适应在重负荷下:随机等待的时间将更长些首次冲突:从0,1中选择 K；延迟的时长为 K x 512 bit 传输时间第二次冲突后:从 0,1,2,3选择K在10次或更多的冲突发生后：从 0,1,2,3,4,1023选择K,6b-47,集线器（Hubs）,物理层设备:本质上是工作在位流层面上的中继器:将接收到的位流在所有其他接口上复制发送基于集线器星型拓扑的以太网也是一个广播LAN,5:DataLink Layer,5-48,交换机（Switch）,链路层设备:比集线器更智能化，采取主动角色存储，转发以太网帧检测到达帧的MAC地址，有选择的转发到相应一个或多个输出链路，使用CSMA/CD 协议透明的主机并不知晓交换机的转发行为即插即用，自学习无需配置,5-49,交换机：允许多路同步传输,主机直接连接交换机输出接口设有缓存每一个输入连路上使用以太网协议，但没有冲突每一个链路构成自己的冲突域交换:A-to-A and B-to-B 同步进行而不会产生碰转 在集线器中不可能实现,A,A,B,B,C,C,switch with six interfaces(1,2,3,4,5,6),1,2,3,4,5,6,5-50,交换机:帧过滤/转发,当帧到达时:过滤（filtering）：交换机决定一个帧是应该转发到某个接口还是应当将其丢弃的功能。转发(forwarding):决定一个帧应该被导向哪个接口，并把该帧移动这些接口。1.使用MAC地址检索交换机表2.if entry found for destination then if dest on segment from which frame arrived then drop the frame else forward the frame on interface indicated else flood,forward on all but the interface on which the frame arrived,5-51,交换机表（Switch Table）,Q:交换机如何知道4号接口可达A，而5号接口可达B？A:每一个交换机有一个交换机表，每一个表项包括:节点的MAC地址与节点连接的交换机接口用于节点的表项放置在表中的时间Q:how are entries created,maintained in switch table?something like a routing protocol?,A,A,B,B,C,C,switch with six interfaces(1,2,3,4,5,6),1,2,3,4,5,6,5-52,交换机：自学习,交换机自学习哪个主机与哪个接口相连当帧到达时，交换机可学习在该帧源地址字段中的MAC地址该帧到达的接口当前的时间,A,A,B,B,C,C,1,2,3,4,5,6,Switch table(initially empty),5-53,自学习,转发示例,A,A,B,B,C,C,1,2,3,4,5,6,Switch table(initially empty),不知道目标接口:flood老化期后一直沉默的节点帧地址被删除,5:DataLink Layer,5-54,机构网络,to externalnetwork,router,IP subnet,mail server,web server,5:DataLink Layer,5-55,交换机 vs 路由器,都是存储、转发设备路由:网络层设备（检查网络层头部）交换机：链路层设备（检查链路层头部）路由器维持路由表，执行路由算法交换机维持交换机表，执行过滤和自学习,