链路层和局域网.ppt
计算机网络,第5章 链路层和局域网,2,链路层,5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6互联:集线器和交换机5.7点到点协议PPP,3,链路层:概述,术语节点:主机和路由器链路:沿着通信路径连接 相邻节点的通信信道有线链路无线链路LANs帧:链路层协议交换的数据单元,数据链路层 负责将数据报通过链路从一个节点传输到相邻节点,4,链路层:工作环境,数据报在不同链路上可能由不同的链路层协议进行处理例如:第一段链路上由以太网处理,最后一段链路上由PPP处理,中间链路上由广域链路层协议处理不同的链路层协议可能提供不同的服务例如:可靠传递、不可靠传递,5,数据链路层的简单模型,局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 H2 发送数据,从层次上来看数据的流动,6,数据链路层的简单模型(续),局域网,广域网,主机 H1,主机 H2,路由器 R1,路由器 R2,路由器 R3,电话网,局域网,主机 H1 向 H2 发送数据,链路层,应用层,运输层,网络层,物理层,链路层,应用层,运输层,网络层,物理层,链路层,网络层,物理层,链路层,网络层,物理层,链路层,网络层,物理层,R1,R2,R3,H1,H2,仅从数据链路层观察帧的流动,7,链路层服务,成帧、链路访问将数据加上头部和尾部,封装成数据帧共享介质的信道访问帧头部用MAC地址标识源和目的(不同于IP地址)可靠传递很少用于误码率低的链路(光纤、双绞线链路)用于误码率高的链路(无线链路),8,链路层服务,流量控制在相邻的收发节点间限制流量差错检测信号衰减和电磁干扰噪声导致出错接收方检测到错误存在:给发送方发送信号要求重传或丢弃该数据帧差错纠正接收方检测和纠正帧中错误,不用重传半双工和全双工半双工时,链路两端的节点都能传输分组,但不能同时传输,9,适配器通信,发送方,接收方,数据报,适配器卡,适配器卡,链路层协议,链路层协议在适配器中实现(aka NIC)以太网卡,PCMCI卡,802.11 卡发送方:在一个帧内封装数据报增加差错检测位,可靠交付,流量检测等,接收方查找错误,可靠交付,流量控制等取出数据报,交给网络层适配器是半自治单元帧的接收和发送、检错、丢弃均是自主进行向上提交数据时,需要节点干预最终受控于节点,10,链路层,5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6互联:集线器和交换机5.7点到点协议PPP,11,差错检测,EDC=Error Detection and Correction bits 差错检测和纠错比特(冗余)D=Data 差错检测位保护的数据,可包括首部 差错检测不是100%可靠!协议算法可能漏掉某些错误 EDC域越大,差错检测和纠错效果更好,12,奇偶校验,单比特奇偶校验:检测单个比特错误,二维奇偶校验:检测和纠正单个比特错误,13,因特网校验和,目的:检测数据段在传输过程中出现的错误(注意:仅用在传输层),发送方:将数据段的内容作为16比特的整数序列校验和:累加求和,计算和的1的补码发送方将得到的校验和值放入UDP校验和字段,接收方:计算收到的数据段的校验和检查计算出的校验和与校验和字段中的值是否相同:NO 检测到错误YES 没有错误,14,循环冗余检测,d比特的数据,D选择r1比特模式(生成多项式),表示为G目标:选择r个CRC比特,R,以便恰好能被G整除(模2计算)接收方已知G,用G去除,若余数非0,则检测到错误能检测到所有少于r+1比特的错误在实践中被广泛应用(ATM,HDLC),15,CRC举例,如果要:D.2r XOR R=nG两边都异或R,得到:D.2r=nG XOR R 即:D.2r 除以G,得到余数 R,R=余数,D.2rG,16,链路层,5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6互联:集线器和交换机5.7点到点协议PPP,17,多址访问链路和协议,两种链路点到点链路PPP以太网交换机和主机之间的点到点链路广播链路(共享线路或介质)传统以太网802.11无线LAN,共享线路(如以太网),共享无线(如Wi-Fi),卫星,鸡尾酒会,18,多址访问协议,单个共享广播信道两个或多个节点同时传输:相互干扰 碰撞:一个节点同时收到两个或多个信号多址访问协议分布式算法决定节点如何共享信道,如节点何时可以传输数据注意:有关共享信道的通信(协商)需使用信道本身没有额外的信道来进行协调,19,理想的多址访问协议,速率为R bps的广播信道1.当只有一个节点有数据发送时,该节点的吞吐量为R2.当M个节点有数据发送时,每个节点吞吐量为R/M3.分散:没有特定节点用于调整传输没有时钟同步4.简单,20,多址访问协议:分类,信道划分协议将信道划分成小的“片”(时隙、频率、编码)将“片”分配给节点使用随机访问协议信道没有被分割,允许碰撞碰撞恢复轮流协议节点轮流传送,但数据量大的节点轮流更长时间,21,信道划分协议:TDMA,TDMA:循环访问信道每个节点在每次循环中得到固定长度的时隙(时隙长度传输单个分组时间)没有数据发送的时隙空闲,时间,22,时分复用,频率,时间,B,C,D,B,C,D,B,C,D,B,C,D,23,时分复用,频率,时间,C,D,C,D,C,D,A,A,A,A,C,D,24,时分复用,频率,时间,B,D,B,D,B,D,A,A,A,A,B,D,25,时分复用,频率,时间,B,C,B,C,B,C,A,A,A,A,B,C,26,时分复用可能会造成线路资源的浪费,A,B,C,D,a,a,b,b,c,d,b,c,a,t,t,t,t,t,4 个时分复用帧,#1,a,c,b,c,d,时分复用,#2,#3,#4,用户,27,信道划分协议:FDMA,FDMA:频分复用信道按频谱分成若干频段每个节点分配固定频段在频段不用时该部分信道被闲置和浪费,频率,时间,频率 1,频率 2,频率 3,频率 4,频率 5,28,码分复用 CDM,常用的名词是码分多址 CDMA(Code Division Multiple Access)。各用户使用经过特殊挑选的不同码型,因此彼此不会造成干扰。这种系统发送的信号有很强的抗干扰能力,其频谱类似于白噪声,不易被敌人发现。每一个比特时间划分为 m 个短的间隔,称为码片(chip)。,29,码片序列(chip sequence),每个站被指派一个惟一的 m bit 码片序列。如发送比特 1,则发送自己的 m bit 码片序列。如发送比特 0,则发送该码片序列的二进制反码。例如,S 站的 8 bit 码片序列是 00011011。发送比特 1 时,就发送序列 00011011,发送比特 0 时,就发送序列 11100100。S 站的码片序列:(1 1 1+1+1 1+1+1),30,CDMA 的重要特点,每个站分配的码片序列不仅必须各不相同,并且还必须互相正交(orthogonal)。在实用的系统中是使用伪随机码序列。,31,CDMA 的工作原理,S 站的码片序列 S,1,1,0,t,t,t,t,t,t,m 个码片,t,S 站发送的信号 Sx,T 站发送的信号 Tx,总的发送信号 Sx+Tx,规格化内积 S Sx,规格化内积 S Tx,数据码元比特,发送端,接收端,32,随机访问协议,当节点有数据发送时以信道全部速率R传输没有主节点起协调作用两个或多个节点传送时碰撞随机访问协议特点:如何检测碰撞如何从碰撞中恢复(如:延时后重传)随机访问协议举例:ALOHA时隙ALOHACSMA,CSMA/CD,CSMA/CA,33,ALOHA,1.ALOHA的由来 ALOHA 乃Additive Link On-Line HAwaii system简写,ALOHA恰好还是夏威夷方言的“你好”。ALOHA网是计算机网络早期发展中一个著名的网络,也是第一个无线计算机网络,现仍在运行之中2.ALOHA网的特征 因群岛位置的散布,网络拓扑采用了星型结构;因陆地上的不连接,为节省费用和易于组网,网络中各站点的通信采用了无线传输介质 由于采用无线电信道,考虑到无法申请更多的频率点,因而所有站点都使用统一的频率通过主机交换信息。,34,纯ALOHA,35,纯ALOHA效率,P(给定节点成功概率)=P(给定节点传送).P(在 p0-1,p0没有其它节点传送).P(在 p0,p0+1没有其它节点传送)=p.(1-p)N-1.(1-p)N-1=p.(1-p)2(N-1)选择最合适p,n趋于无穷,取极限.=1/(2e)=0.18,36,时隙ALOHA,37,时隙ALOHA效率,假定 N 个节点有大量帧发送,每个节点在每个时隙传送帧的概率为p一个给定节点成功传送的概率为p(1-p)N-1任意一个节点成功的概率=Np(1-p)N-1,为获得N个节点的最大效率,需要找到使Np(1-p)N-1最大化的p*当N趋于无穷时,求Np*(1-p*)N-1 的极限,得到最大效率为 1/e=0.37,效率:当有大量活动节点、每个节点总有大量帧发送、长期运行时成功时隙的份额,最佳情况:信道使用率只有37%!,38,CSMA(Carrier Sense Multiple Access),CSMA:传输前监听,如果信道空闲,传送整个帧如果信道忙,推迟传送为人处事的规则之一:不要打断别人的发言!,39,CSMA的类型,非坚持(nonpersistent)CSMA 一旦监听到信道忙(即发现有其他站在发送数据),就不再坚持听下去,而是根据协议的算法延迟一个随机的时间后重新再监听。若进行载波监听时发现信道空闲,则将准备好的帧发送出去时隙非坚持CSMA 采用划分时隙的随机接入CSMA协议,协议规定只能在每个时隙开始时才能发送帧,40,CSMA的类型,1坚持CSMA 当一个站点要传送数据时,首先侦听信道,看是否有其他站点正在传送。如果信道正忙,它就持续等待直到它侦听到信道空闲时,便将数据送出。若发生冲突,站点就等待一个随机长的时间,然后重新开始。P坚持CSMA 当一个站点要传送数据时,首先侦听信道,看是否有其他站点正在传送。如果信道正忙,它就持续等待直到它侦听到信道空闲时,以概率P发送数据,而以概率(1P)延迟一段时间(网络中最远的端到端的传播时延),重新监听信道。若发生冲突,站点就等待一个随机长的时间,然后重新开始。,41,三种CSMA坚持的比较,非坚持:不能充分利用信道刚刚转入空闲期的这段时间1坚持:容易在上述这段时间产生冲突。P坚持:可以在一定程度上克服这些缺点,但却很难选择一个能用于各种通信量强度的P值。所以在实际网络中常选择1坚持。,42,CSMA随机接入流程图,43,CSMA/CD(碰撞检测),CSMA/CD:载波侦听,CSMA中的延时在短时间内碰撞被检测碰撞后停止传输,减少信道浪费碰撞检测:在有线LANs中比较容易:测量信号强度,比较收、发的信号在无线LANs中比较困难:传输时接收器是关闭的人类社会的范例:谈话礼貌,44,1 km,A,B,t,t=0,单程端到端传播时延记为,45,1 km,A,B,t,t=B 检测到信道空闲发送数据,t=/2发生碰撞,A,B,A,B,t=0 A 检测到信道空闲发送数据,A,B,t=0,A,B,单程端到端传播时延记为,46,强化碰撞,当发送数据的站一旦发现发生了碰撞时,除了立即停止发送数据外,还要再继续发送若干比特的人为干扰信号(jamming signal),以便让所有用户都知道现在已经发生了碰撞。,47,人为干扰信号,A,B,t,B 也能够检测到冲突,并立即停止发送数据帧,接着就发送干扰信号。这里为了简单起见,只画出 A 发送干扰信号的情况。,48,争用期,最先发送数据帧的站,在发送数据帧后至多经过时间 2(两倍的端到端往返时延)就可知道发送的数据帧是否遭受了碰撞。以太网的端到端往返时延 2 称为争用期,或碰撞窗口。经过争用期这段时间还没有检测到碰撞,才能肯定这次发送不会发生碰撞。,49,轮流协议,信道划分协议在重负荷时,共享信道有效、公平在轻负荷时效率低:信道访问延时,即使只有一个活动节点,也只能分配到1/N的带宽随机访问协议轻负荷时效率高:只有一个节点时,能充分利用信道在重负荷下:碰撞的开销轮流协议在两个方面寻求最佳的解决方案!,50,轮流协议,轮询协议:主节点邀请从节点轮流传输关注:轮询开销 等待时间单点失效(主节点),令牌传递协议:控制令牌依次通过各个结点令牌报文关注:令牌的开销 等待时间 单点失效(token),51,多址访问协议总结,对于共享介质能做什么?信道划分,基于时间、频率、编码时分,频分随机划分(动态),ALOHA,S-ALOHA,CSMA,CSMA/CD载波侦听:有线“易行”、无线“困难”CSMA/CD 用于以太网CSMA/CA 用于 802.11轮流主节点轮询,令牌传递,52,局域网技术,数据链路层:服务,错误检测/纠错,多路访问下面讨论局域网技术:编址以太网集线器、交换机PPP,53,链路层,5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6互联:集线器和交换机5.7点到点协议PPP,54,MAC地址和ARP,32-bit IP 地址:网络层地址用于将数据报发往目的IP子网MAC(或局域网或物理或以太网)地址:用于将数据报从一个接口传送到与之物理相连的另一个物理接口(同一网络)48 bit MAC 地址(对大多数的局域网)烧入适配器的 ROM中,55,局域网地址和ARP,局域网中每个适配器有唯一的局域网地址,广播地址=FF-FF-FF-FF-FF-FF,=适配器,56,局域网地址,MAC 地址由IEEE分配管理厂商需要购买MAC地址空间(来保证唯一性)类比:(a)MAC 地址:象社会安全号码(b)IP地址:象邮政地址 MAC 平面地址 可以迁移 能将LAN卡在不同LAN间移动,地址保持不便IP 地址是分层的,不可迁移取决于某个站点接入的网络,57,ARP:地址解析协议,每个IP节点(主机,路由器)都有一个ARP表ARP表:局域网节点的IP/MAC地址映射 TTL(Time To Live):超过TTL的地址映射会被删除(一般为20分钟),1A-2F-BB-76-09-AD,58-23-D7-FA-20-B0,0C-C4-11-6F-E3-98,LAN,58,ARP协议:同一局域网(网络),59,ARP协议:同一局域网(网络),建立ARP请求包广播发送该ARP请求包,60,ARP协议:同一局域网(网络),目的接收到该ARP请求包,建立包含自己MAC地址的ARP应答包(请注意,应答包和请求包的源、目标是不一致的)直接向源发送该ARP应答包更新ARP高速缓存,61,A,Y,X,B,Z,主机 B 向 A 发送ARP 响应分组,主机 A 广播发送ARP 请求分组,ARP 请求,ARP 请求,ARP 请求,00-00-C0-15-AD-18,08-00-2B-00-EE-0A,我是,硬件地址是 00-00-C0-15-AD-18我想知道主机 209.0.0.6 的硬件地址,我是 硬件地址是 08-00-2B-00-EE-0A,A,Y,X,B,Z,00-00-C0-15-AD-18,62,ARP协议:路由到其它 LAN,63,互联网环境下的ARP,64,链路层,5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6互联:集线器和交换机5.7点到点协议PPP5.8链路虚拟化:ATM和MPLS,65,以太网,“统治”有线局域网技术:便宜最先被广泛用于局域网技术简单,比令牌网和ATM便宜能跟上速率的快速提高:10 Mbps 10 Gbps,Metcalfe的以太网草图,66,最初的以太网是将许多计算机都连接到一根总线上。当初认为这样的连接方法既简单又可靠,因为总线上没有有源器件。,以太网,B向 D发送数据,C,D,A,E,匹配电阻(用来吸收总线上传播的信号),匹配电阻,不接受,不接受,不接受,接受,B,只有 D 接受B 发送的数据,67,星形拓扑,90年代中期流行总线形拓扑现在流行星形拓扑连接设备:集线器或交换机(以后会有更多),集线器或交换机,68,以太网帧结构,发送方适配器在以太网帧中封装IP数据报(或其它网络层协议包)数据字段:(46字节,1500字节)前同步码:总共8字节,前7 字节的格式为 10101010,最后一个字节格式为10101011 用于同步发送方与接收方时钟,69,以太网帧结构(续),地址:6 字节若适配器收到以太网帧,目的地址为自己的MAC地址或广播地址(如ARP包),就将帧中的数据传给网络层。否则,适配器丢弃该帧类型:上层协议类型(大多为IP协议,也支持其它协议如Novell IPX 和AppleTalk)CRC:由接收方检查,若检测到错误,就将该帧丢弃,70,不可靠的、无连接服务,无连接服务:在送适配器和接收适配器之间不需要握手不可靠服务:接收适配器不发送确认帧或否认帧给发送方交给网络层的数据报可能存在间隙若应用使用TCP,间隙会被填充否则,应用就会看见间隙,71,以太网使用 CSMA/CD,没有时隙当适配器侦听到其它适配器在传输,则它不传输帧,即载波侦听正在传输的适配器若检测到其它适配器也在传输,则它中止自己的传输,即碰撞检测,在重新传输之前,适配器要等待一段随机时间,即随机访问,72,以太网的CSMA/CD 算法,1.适配器收到来自网络层的数据报,创建帧2.若适配器检测到信道空闲,则开始传输帧;若检测到信道忙,就开始等待,直到信道空闲再开始传输该帧3.若适配器传输了整个帧而没有检测到其它适配器的传输,则该适配器完成该帧的传输,4.若适配器在传输时检测到其它适配器也在传输,则停止传输,发送拥塞信号5.中止传输后,适配器进入指数回退阶段,在经历第m次碰撞后,适配器随机从0,1,2,2m-1中选择K值。适配器在等待 K512比特时间后,返回第2步,73,以太网的CSMA/CD(续),拥塞信号:用来确保所有传输者都能检测到碰撞而传输的信号;48比特长比特时间:传输1比特所需时间。在10Mbps的以太网中,当K=1023时,等待时间大约为50ms,指数回退:目的:适配器重传时试图估计正确的负载重载:随机等待的时间可能会更长第一次碰撞:从 0,1中选择K;延迟是 K 512 比特传输时间第二次碰撞后:从 0,1,2,3中选择K第十次碰撞后:从 0,1,2,3,4,1023中选择K,See/interact with Javaapplet on AWL Web site:highly recommended!,74,重要特性,使用 CSMA/CD 协议的以太网不能进行全双工通信而只能进行双向交替通信(半双工通信)。每个站在发送数据之后的一小段时间内,存在着遭遇碰撞的可能性。这种发送的不确定性使整个以太网的平均通信量远小于以太网的最高数据率。,75,争用期的长度,以太网取 51.2 s 为争用期的长度。对于 10 Mb/s 以太网,在争用期内可发送512 bit,即 64 字节。以太网在发送数据时,若前 64 字节没有发生碰撞,则后续的数据就不会发生碰撞。,76,最短有效帧长,如果发生碰撞,就一定是在发送的前 64 字节之内。由于一检测到碰撞就立即中止发送,这时已经发送出去的数据一定小于 64 字节。以太网规定了最短有效帧长为 64 字节,凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。,77,传统以太网的连接方法,传统以太网可使用的传输媒体有四种:铜缆(粗缆或细缆)铜线(双绞线)光缆这样,以太网就有四种不同的物理层。,78,10BaseT and 100BaseT,10/100 Mbps 速率;称为快速以太网T 代表双绞线(Twisted Pair)节点连接到集线器:“星形拓扑”;在节点和集线器之间的最大距离为100 米,79,10Base5,粗同轴电缆,可靠性好,抗干扰能力强 收发器:发送/接收,冲突检测,电气隔离AUI:连接件单元接口总线型拓扑用于网络骨干连接,最大段长度 500米每段最多站点数 100,两站点间最小距离 2.5米,粗缆,Vampire tap,BNC端子,收发器,AUI 电缆,NIC,网络最大跨度 2.5公里,80,10Base2,细同轴电缆,可靠性稍差 BNC T型接头连接 总线型拓扑用于办公室LAN,细缆,BNC 接头,NIC,每段最大长度 185m每段最多站点数 30,两站点间最短距离 0.5 m,网络最大跨度 925 m,网络最多5个段,81,集线器,集线器本质上是物理层的中继器:从一个接口收到的比特流会传给其它所有接口同样速率没有帧缓存集线器没有 CSMA/CD:由适配器检测碰撞提供网络管理功能,82,吉比特以太网,使用标准以太网帧格式允许点对点链路和共享的广播信道共享信道时,使用CSMA/CD;为了得到可接受的效率,节点之间的距离要短使用集线器,在这里称为“缓冲式分配器”对于点到点链路,可以以1Gbps的速率全双工工作现在已经达到10 Gbps!,83,曼彻斯特编码,将每一个码元再分成两个相等的间隔。码元1是在前一个间隔为高电平而后一个间隔为低电平。码元0则正好相反,从低电平变到高电平,NRZ,曼彻斯特,0:,1:,84,差分曼彻斯特编码,若码元为1,则其前半个码元的电平与上一个码元的后半个码元的电平一样;但若码元为0,则其前半个码元的电平与上一个码元的后半个码元的电平相反。不论码元是l或0,在每个码元的正中间的时刻,一定要有一次电平的转换,NRZ,差分曼彻斯特,1:不翻转,0:翻转,中间翻转,85,链路层,5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6互联:集线器和交换机5.7点到点协议PPP,86,集线器互联,主干集线器将LAN网段互联起来扩展了节点间的最大距离原先独立的网段碰撞域变成了一个大的碰撞域不能将10BaseT 和 100BaseT以太网互联,10BaseT集线器,10BaseT集线器,10BaseT集线器,主干集线器,87,网桥/链路层交换机互联,网桥(Bridge)/链路层交换机实质上就是一种存储转发设备,用来实现MAC层的LAN互连,88,网桥与集线器的区别,集线器只是将网络的覆盖距离简单的延长,而且距离有限,具体实现在物理层;网桥不仅具有将LAN的覆盖距离延长的作用,而且理论上可做到无限延长,具体实现在MAC层集线器仅具有简单的信号整形和放大的功能;网桥则属于一种智能互连设备,它主要提供信号的存储/转发、数据过滤、路由选择等能力集线器仅是一种硬设备,而网桥既包括硬件又包括软件集线器仅只能互连同类LAN,而网桥可支持不同类型的LAN互连,89,网桥的概念结构,90,网桥的工作原理,不断监听各端口是否有信号收到无差错的帧则缓存,反之将差错帧丢弃若所收帧的目的MAC地址属另一网段,则通过站表决定向何端口转发网桥不转发同一网段内通信的帧网桥不修改所转发的帧的源地址,91,网桥的优势,过滤通信量扩大了局域网的物理范围提高了可靠性可互连不同物理层、不同MAC子层和不同速率的局域网,92,网桥的缺点,由于要接收和转发,增加了时延MAC子层没有流量控制功能,网络负荷重时,网桥缓存空间可能发生溢出,产生帧丢失现象不同MAC子层的网段桥接时,在转发帧之前要修改帧的某些字段,这也需要耗费时间出现广播风暴。网桥只适合用户少于几百个和通信量不太大的局域网,否则有时会因传播过多广播信息而产生网络拥塞,93,透明网桥,所谓透明网桥就是由各网桥自己来决定路由选择,而局域网上的各站都不管路由选择。这种网桥的标准由IEEE802.1(D)或IS08802.1d给出。这里所谓“透明”是指局域网上的每个站并不知道所发送的帧将经过哪几个网桥,即网桥对各站来说是看不见的。,94,透明网桥选路原理,从端口x收到帧,有差错则丢弃,否则在站表中查找目的站MAC地址;找到有,则取出相应的端口d,转,否则转;如果所给MAC地址的端口d=x,则丢弃此帧(不需要转发),否则从端口d转发此帧;转到;向网桥除x以外的所有端口转发此帧(可保证找到目的站)如源站不在站表中,则将源站MAC地址写入站表,登记该帧进入网桥的端口号和时间,设置计时器,然后转。否则转;更新计时器(由于网络拓扑经常变化,因此,超时记录要删除,以反映最新状态);等待新的数据帧。转,95,透明网桥存在的一个问题兜圈子,96,解决方案支撑树算法,互连在一起的网桥彼此通信后,就能找出原来的网络拓扑的一个子集,在这个子集里整个连通的网络中不存在回路。一旦支撑树确定了网桥就会将某些端口断开,以确保从原来的拓扑得出一个支撑树支撑树算法选择一个网桥为树的根,然后以最短路径为依据,找到树上的每一个结点为了使支撑树能反映网络拓扑的变化,每隔几秒钟每个网桥要广播其标识号,和它所知道的所有其他网桥缺点:互连局域网数目非常大时,支撑树算法可能花很多时间。,97,多端口网桥以太网(二层)交换机,链路层设备存储和转发以太网帧检查帧头部,根据目的MAC地址转发帧当帧转发到LAN网段,用CSMA/CD 访问 LAN网段透明主机不知道交换机的存在即插即用,自学习交换机不需配置,98,交换机转发,转发帧时,如何决定转发到那个LAN网段?看起来象一个路由问题.,集线器,集线器,集线器,交换机,1,2,3,99,自学习,交换机有一个交换表 交换表项:(MAC地址,接口,时间戳)老的表项被删除(TTL 可能为 60分钟)交换机能学习到哪个主机从哪个接口到达当收到帧的时候,交换机学习到发送者的位置:进入的LAN网段在交换表中记录发送者/位置对,100,过滤/转发,当交换机收到帧:用MAC地址来索引交换表if 目的地址在表中then if 目的地址在帧来自的LAN网段 then 丢弃该帧 else 转发到合适的接口 else 将帧转发到其它所有接口,101,交换机举例,假定C发送帧到D,交换机收到来自C的帧在表中记录C在接口1因为D不在表中,交换机将帧转发到接口2和3帧被 D收到,集线器,集线器,集线器,交换机,A,B,C,D,E,F,G,H,I,地址,接口,ABEG,1123,1,2,3,102,交换机举例,假定D返回数据给.,交换机收到来自D的帧在表中记录D在接口2因为C在表中,交换机只将帧转发给接口1C收到该帧,集线器,集线器,集线器,交换机,A,B,C,D,E,F,G,H,I,地址,接口,ABEGC,11231,103,交换机:流量隔离,交换机将子网分成了LAN网段交换机包过滤:同一LAN网段的帧通常不会转发到其它LAN网段网段保持独立的碰撞域,集线器,集线器,集线器,交换机,碰撞域,碰撞域,碰撞域,104,交换机:专用接入,交换机有很多接口主机直接连到交换机没有碰撞;全双工交换:A-to-A 和 B-to-B 同时传输,没有碰撞,交换机,A,A,B,B,C,C,105,交换机的其它特点,直通交换:帧从入端口转发到出端口不需收集整个帧能少量减少延迟共享/专用的、10/100/1000Mbps接口的结合,106,学院网络,集线器,集线器,集线器,交换机,到外部网络,路由器,IP 网络,邮件服务器,web 服务器,107,交换机和路由器,两者都是存储转发设备路由器:网络层设备(检查网络层头部)交换机是链路层设备路由器维护路由表,实现路由算法交换机维护交换表,实现MAC地址过滤、学习算法,主机,主机,网桥,路由器,108,总结比较,集线器,路由器,交换机,流量隔离,无,有,有,即插即用,有,无,有,优化选路,无,有,无,直通交换,有,无,有,109,虚拟局域网 VLAN 是由一些局域网网段构成的与物理位置无关的逻辑组。这些网段具有某些共同的需求。每一个 VLAN 的帧都有一个明确的标识符,指明发送这个帧的工作站是属于哪一个 VLAN。虚拟局域网其实只是局域网给用户提供的一种服务,而并不是一种新型局域网。,虚拟局域网,110,以太网交换机,A4,B1,以太网交换机,VLAN3,C3,B3,VLAN1,VLAN2,C1,A2,A1,A3,C2,B2,以太网交换机,以太网交换机,三个虚拟局域网 VLAN1,VLAN2和 VLAN3 的构成,111,以太网交换机,A4,B1,以太网交换机,VLAN3,C3,B3,VLAN1,VLAN2,C1,A2,A1,A3,C2,B2,以太网交换机,以太网交换机,三个虚拟局域网 VLAN1,VLAN2和 VLAN3 的构成,当 B1 向 VLAN2 工作组内成员发送数据时,工作站 B2 和 B3 将会收到广播的信息。,112,以太网交换机,A4,B1,以太网交换机,VLAN3,C3,B3,VLAN1,VLAN2,C1,A2,A1,A3,C2,B2,以太网交换机,以太网交换机,三个虚拟局域网 VLAN1,VLAN2和 VLAN3 的构成,B1 发送数据时,工作站 A1,A2 和 C1都不会收到 B1 发出的广播信息。,113,以太网交换机,A4,B1,以太网交换机,VLAN3,C3,B3,VLAN1,VLAN2,C1,A2,A1,A3,C2,B2,以太网交换机,以太网交换机,三个虚拟局域网 VLAN1,VLAN2和 VLAN3 的构成,虚拟局域网限制了接收广播信息的工作站数,使得网络不会因传播过多的广播信息(即“广播风暴”)而引起性能恶化。,114,链路层,5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6互联:集线器和交换机5.7点到点协议PPP,115,点到点数据链路控制,一个发送方,一个接收方,一条链路;比广播链路更容易实现:没有媒体访问控制不需要 MAC地址如:拨号链路,ISDN电路流行的点到点DLC协议:PPP(point-to-point protocol)HDLC:High level data link control(数据链路被认为是协议栈中的高层),116,PPP 设计要求 RFC 1557,分组成帧:网络层的数据报封装成帧的数据携带任意网络层协议(不仅仅IP)的网络层数据有向上分用的能力比特透明:携带的数据可以是任何比特模式的差错检测(不纠错)连接的活性:检测链路层故障,并向网络层通知该差错情况网络层地址协商:端点能获知/配置相互通信的网络层地址,117,PPP不要求实现的,错误纠错/恢复流量控制有序 多点链路(如:轮询),错误恢复,流量控制,数据排序交给上层处理,118,PPP 数据帧,标志:分隔符(标志帧的开始和结束)地址:没有用(只是一个选项)控制:没有用;今后可能使用控制域协议:帧中封装的数据所属的上层协议(如PPP-LCP,IP,IPCP等),119,PPP 数据帧,信息:携带的上层数据校验和:用于差错检测的循环冗余校验和,120,字节填充,“数据透明”要求:数据域可以使用标志字段的值(7E)Q:收到的(7E)是数据还是标志?发送方:(7E)(7D 5E)(7D)(7D 5D)接收方:反之即可,121,PPP 数据控制协议,在交换网络层数据之前,数据链层双方必须配置 PPP 链路(最大帧长度,认证)学习/配置网络层信息 对 IP:携带IP控制协议(IPCP)消息(协议域:8021)配置/学习IP地址,122,第五章:总结,数据链路层服务原理:错误检测,纠错共享广播信道:多路访问链路层寻址不同链路层技术示例和实现以太网交换局域网PPP,123,课后思考题,复习题 1、3、6、8、10、12、13习 题 1、2、4、8、11、12、14、15讨论题 3,124,作业题,习题 4、8、12、14、15,