第4章 网络层.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 网络层,主讲人 陈慧,学习目的和要求,本章介绍网络层的内容，网络层设计的是将源端发出的分组经过各种途径传送到目的端，在数据链路层提供的两个相邻节点之间的数据帧的传输功能上，进一步管理网络中的数据通信，将数据从源端经过若干中间节点传送到目的端。网络层是,OSI,模型中面向数据通信的底三层中最为复杂、关键的一层。,网络层,5.1,通信子网的操作方式和网络层提供的服务,5.2,路由选择,5.3,拥塞控制,5.4,服务质量,5.5,网络互连,5.6,因特网的互连层协议,通信子网的操作方式和网络层提供的服务,考核要求：,领会：网络层的功能,领会：通信子网的两种操作方式：虚电路和数据报，两种操作所提供的两种服务，两种子网的比较。,网络层的功能,网络层是,OSI,参考模型中的第三层,网络层关系到通信子网的运行控制，体现了网络应用环境中资源子网访问通信子网的方式，是,OSI,模型中面向数据通信的低三层,(,也即通信子网,),中最为复杂、关键的一层。,网络层的目的是实现两个端系统之间的数据透明传送，具体功能包括路由选择、阻塞控制和网际互连等。,5.1,通信子网的操作方式和网络层提供的服务,端点之间的通信是依靠通信子网中的节点间的通信来实现的,在分组交换方式中，通信子网向端系统提供虚电路和数据报两种网络服务，而通信子网内部的操作也有虚电路和数据报两种方式。,通信子网的操作方式：虚电路操作方式和数据报操作方式,网络层提供的服务：虚电路服务和数据报服务,5.1.1,虚电路操作方式,网络的源节点和目的节点之间先要建立一条逻辑通路，因为这条逻辑通路不是专用的，所以称之为“虚”电路。,节点间的物理信道在逻辑上均可看做由多条逻辑信道组成，这些逻辑信道实际上由节点内部的,分组缓冲器,来实现。,不同的逻辑信道在节点内部通过,逻辑信道号,加以区分，各条逻辑信道,异步分时复用,同一条物理信道。,各节点内部必须建立一张,虚电路表,，用以记录该点的各条虚电路所占用的各个逻辑信号。,相关名词,H,1,H,5,H,2,H,4,H,3,A,C,D,B,H,6,E,分组交换网,端系统,节点,虚电路,逻辑信道,物理信道,虚,电路的特点,一条,物理链路可以对应多条逻辑信道,一条虚电路由各物理链路上的逻辑信道级联而成，占用了节点上的一条逻辑信道实际上就是占用了该节点上的分组缓冲器,分组靠逻辑信道号选择路由，因逻辑信道号只有局部意义，所以减少了分组头部的开销和处理的复杂度,一个虚电路表建立,各节点的虚电路表是在虚电路建立过程中建立的。,第一步：源端系统可发出一个呼叫请求分组，该分组除了包含目的地址外，还包含源端系统所选取的不用的最小逻辑信道号,N,。,第二步：,A,节点收到请求分组后，在,A,节点与下一节点,B,间所有已使用的逻辑信道号之外，选取一个最小编号,N,A,，,并将请求分组中的逻辑信道号,N,替换成该逻辑信道号,N,A,，,再将分组发送给节点,B,。,中间：此后的各节点依次逐个根据自身实际情况，选取新的逻辑信道号,(,如,N,B,、,N,C,、,N,D,等,),来替换收到的分组中的逻辑信道号。,最后：目的节点将请求分组传送给连接它的端系统。,每个节点的虚电路表中要记录两个逻辑信道：前一个节点所选取的逻辑信道号和本节点所选取的逻辑信道号。,虚电路建立示例,5.1.2,数据报操作方式,在数据报操作方式中，每个分组被称为一个数据报，若干个数据报构成一次要传送的报文或数据块。每个数据报自身携带有足够的信息，它的传送是被单独处理的。,发送一个报文时，将报文拆成若干个带有序号和地址信息的数据报，依次发给网络节点。,各个数据报所走的路径就可能不同，网络节点要为每个数据报做路由选择。,数据报的特点,每个分组的寻路是独立的，可以合理利用网络资源,如果途中一个节点或一条链路发生故障，能给分组重选路由,分组头需要包含地址字段，也会增加开销,各分组途经的路径可能不同，因此有可能出现先发后到现象,5.1.3,虚电路服务,虚电路服务是网络层向传输层提供的一种使所有分组按顺序到达目的端系统的可靠的数据传送方式。,OSI,中面向连接的网络服务就是虚电路服务。,虚电路的服务是网络层向传输层提供的服务，也是通信子网端向系统提供的网络服务。,虚电路服务的实际操作,提供这种虚电路服务的通信子网内部的实际操作既可是虚电路方式的，也可以是数据报方式的。,以虚电路操作方式的网络，一般总是提供虚电路服务。,SNA,就是采用这种虚电路操作支持虚电路服务方式的实例。,以数据报方式操作的网络,也可以提供虚电路服务,通信子网内部节点按数据报方式交换数据,而与端系统相连的网络节点则向端系统提供虚电路服务。,在,ARPANET,中，其内部使用数据报操作方式，但可以向端系统提供数据报和虚电路两种服务。,5.1.4,数据报服务,数据报服务一般仅由数据报交换网来提供。,端系统的网络层同网络节点中的网络层之间，一致地按照数据报操作方式交换数据。,当端系统要发送数据时，网络层给该数据附加上地址、序号等信息，然后作为数据报以发送给网络节点；目的端系统收到的数据报可能是不按序到达的，也可能有数据报的丢失。,操作和服务,虚电路操作方式,数据报操作方式,虚电路服务,数据报服务,SNA,ARPANET,5.1.5,虚电路子网和数据报子网的比较,路由器的内存空间和带宽之间的平衡,建立虚电路所需要的时间和地址解析的时间,路由器内存中所需要的表空间的数量,虚电路子网可以提前预留资源,需要建立和消除虚电路,路由器失效的影响,虚电路和数据报子网比较,数据报子网,虚电路子网,建立电路,不需要,需要,地址信息,每个分组包括完整的源地址和目的地址,每个分组含有一个短的虚电路号,状态信息,路由器不保留任何有关连接的状态信息,每个虚电路都要求路由器为每个连接建立表项,路由选择,每个分组单独选择路由,建立虚电路时选择路由，以后所有分组都使用该路由,路由器,失败的影响,除了在崩溃时正在由该,路由器,处理的分组都丢失外，无其他影响,所有经过失效,路由器,的虚电路都要被终止,服务质量和拥塞控制,很难实现,如果有足够的缓冲区分配给已建立的虚电路，则容易控制,习题,4.,考虑下面虚电路服务实现涉及的设计问题。如果虚电路用在子网内部，每个数据报文必须有一个,3,字节的报文，每个路由器必须留有,8,字节的空间来标示虚电路。如果内部使用数据报，则需要使用一个,15,字节的分组头。假定每站段传输带宽的费用为每,10,6,字节,1,元人民币；路由器存储器的价格为每字节,0.1,元人民币，并且在未来两年会下降。平均每次会话的长度为,1000,秒，传输,200,分组；分组平均需传,4,个站段。试问子网内部采用虚电路或数据报哪个更便宜？便宜多少？,答：每个分组经过,4,段链路意味链路上包括,5,个路由器。,虚电路实现方案：需在,1000,秒内固定分配,5,8=40bytes,存储空间，,存储器使用的时间是,2,年，即,2,52,（一年,52,个星期）,40,（每星期工作,40,个小时）,3600=1.5,10,7,sec,每字节每秒的费用,=0.1/,（,1.5,10,7,）,=6.7,10,-9,元,总费用即,1000,秒,40,字节的费用,=1000,40,6.7,10,-9,=2.7,10,-4,元,数据报实现方案：比上述虚电路实现方案需多传,(15-3),4,200=9600bytes,，,每字节每链路的费用,=1/10,6,=10,-6,元,总费用，即,9600,字节每链路的费用,=9600,10,-6,=96,10,-4,元,96-2.7=93.3,毫分,可见，本题中采用虚电路实现方案更为经济，在,1000,秒的时间内便宜,93.3,10,-4,元。,5.2,路由选择,考核要求：,识记：最优化的定义,领会：静态路由选择策略：泛射路由选择算法。动态路由选择策略：链路状态路由算法。移动主机的路由选择。广播路由选择。多播路由选择。,简单应用：最短路有选择算法，距离矢量路由算法。,5.2,路由选择,网络节点在收到一个分组后后，要确定向下一节点传送的路径，这就是路由选择。,在数据报方式中，网络节点要为每个分组路由做出选择；,在虚电路方式中，只需在连接建立时确定路由。,路由选择的两个基本操作：最佳路径的判定和网间信息包的传送（交换）。,确定路由选择的策略称路由选择算法。,设计路由算法时要考虑诸多技术要素。,What does a Routing Table Look Like,路由选择,路由算法有两类：,非自,适应,自,适应,静态路由,动态路由,路由表固定,路由表定时刷新,路由协议,简便、可靠、易行，适用于负荷稳定、拓扑结构变化不大的网络,算法复杂，会增加网络负担，但能够改善网络的性能，并有利于流量控制,5.2.1,最优化原则,如果路由器,J,在从路由器,I,到,K,的最佳路由上，那么从,J,到,K,的最佳线路就会在同一路由之中。,假设称,从,I,到,J,的路由为,r1,，,而路由其余部分成为,r2,。,如果,J,到,K,还有在一条比,r2,更好的路由，那么它可以同,r1,联系起来，以改进,I,到,K,的路由，这与,r1r2,是最优路由的断言相悖。,I,J,K,B,B,一个子网,路由器,B,的汇集树,汇集树（,sink tree,）,从所有源端到目的端的最佳路由集合，形成了以目的地为根的树。,汇集树不包含任何循环,最优化原则和汇集树为路由选择算法提供了一种衡量标准,A,E,D,C,F,I,J,O,L,M,K,G,H,N,5.2.2,静态路由选择算法,静态路由选择策略不用测量也不需利用网络信息，这种策略按某种固定规则进行路由选择；,可分为最短路由选择法、扩散法和基于流量的路由选择法。,1.,最短路由选择法（简单应用）,基本思想,:,建立一个子网图,图中的每个节点代表一台路由器,每条弧线代表一条通信线路,(,链路,),弧上的数字代表该线路的权重。,为了在一对给定的路由器之间选择一条路由路径，路由算法只需在图中找到这对节点之间的最短路径即可。,最著名的,Dijkstra,算法,Dijkstra,算法,算法要求每个节点用从源节点沿已知最佳路径到本节点的距离来标注。,1,、开始所有节点标注为无穷大,2,、改变与源点相邻节点的标注,3,、找到新标注点中的最小的点,M,4,、以,M,为新工作点，标注其相邻节点（若某点曾经标记过，并且新标记小于老标记，则更新其标记）,5,、返回第,3,步,利用,Dijkstra,算法求,A,到,D,的最短通路,A,B,C,E,F,G,H,D,2,2,1,6,4,2,7,3,2,2,3,A,B(2,A),E(,-,),G(6,A),C(,-,),F(,-,),H(,-,),D(,-,),A,B(2,A),E(,4,B,),G(6,A),C(,9,B,),F(,-,),H(,-,),D(,-,),A,B(2,A),E(,4,B,),G(5,E),C(,9,B,),F(,6,E,),H(,-,),D(,-,),A,B(2,A),E(,4,B,),G(5,E),C(,9,B,),F(,6,E,),H(,9,G,),D(,-,),A,B(2,A),E(,4,B,),G(5,E),C(,9,B,),F(6,E),H(8,F),D(,-,),A,B(2,A),E(,4,B,),G(5,E),C(9,B),F(6,E),H(8,F),D(,10,H,),A,B(2,A),E(,4,B,),G(5,E),C(9,B),F(6,E),H(8,F),D(10,H),A,B(2,A),E(,4,B,),G(5,E),C(9,B),F(6,E),H(8,F),D(10,H),最短通路为：,A-B-E-F-H-D,，,权值为,10,A,B,E,G,H,F,C,D,2,2,6,1,7,4,2,2,2,3,3,最短路由选择,练习,找出,V0,到,V3,的最短距离,v,5,v,4,v,3,v,2,v,1,v,0,100,60,30,10,10,20,5,50,5,2.,扩散法,又称为：泛射路由选择法,一个网络节点从某条线路收到一个分组后，再向除该线路外的所有线路重复发送收到分组。,结果，最先到达目的的节点的一个或若干个分组肯定经过了最短的路径，而且所有可能的路径都被尝试过。,没有考虑网路负载,应用：,强壮性要求很高的场合，只要源、目间有一条信道存在，仍能保证数据的可靠传送。,也可用于广播式数据交换中。,进行网络的最短路径及最短传输延迟的测试。,无线网络中,扩散法,产生大量的重复分组，解决办法：,每个分组头包含站计数器，每经过一个站点计数器减一。当计数器为,0,时就扔掉分组。,记录下分组扩散的路径，防止第二次再扩散到已扩散的路径中,改进成选择扩散法，仅发送到与正确方向接近的那些线路上。,3.,基于流量的路由选择,是既考虑拓扑结构又兼顾网络负载的静态路由算法。,基本思想：,对某一给定的线路，如果已知负载与平均流量，那么可以根据排队理论计算出该线路上的平均分组延迟。由所有的线路平均延迟可直接计算出流量的加权平均值，从而得到整个网络的平均分组延迟，这样路由选择问题就归结为如何找出产生网络最小平均延迟的路由算法。,需要预知的信息：,网络的拓扑结构,通信量矩阵,线路容量矩阵,选定一种路由算法,5.2.3,动态路由选择算法,节点的路由选择要依靠网络当前的状态来决定的策略。,也称为自适应路由选择算法,特点：,能较好的适应网络的流量、拓扑结构的变化，有利于改善网络环境,算法复杂,距离矢量路由算法和链路状态路由算法,1.,距离矢量路由算法（简单应用）,每个路由器维护一张路由表，以子网中的每个路由器为索引，表中列出当前已知的路由器到每个目标路由器的,最佳距离,，以及所使用的,线路,。通过在邻居之间交换信息，路由器不断地更新他们内部的路有表。,解释,:,每个节点都定期地将它们的路由表传送给所有相邻节点，这里的路由表所包含的内容有：,每条路径的经过的节点,线路,本节点到该目的地址的代价,距离,每个节点根据收到的相邻节点的路由信息更新自己的路由表,A,J,K,X,I,4,3,5,距离矢量路由算法举例,8,10,12,6,距离矢量路由算法的应用,距离矢量路由算法（,distance vector routing,）是现代计算机网络两个最常使用的动态路由选择算法之一。,最初是,ARPAnet,使用的路由算法；,Internet,的一种路由信息协议,RIP,（,Route Information Protocol,）；,2.,链路状态路由算法,链路状态路由算法于,1979,年出现在,ARPAnet,上，作为一种用来取代距离矢量路由算法的动态路由选择算法，得到了广泛的应用。,算法描述（每个路由器需要完成的工作）：,发现它的相邻节点，并且知道其网络地址；,测量到各邻居节点的延迟或者开销；,构造一个分组，分组中包含所有它刚刚知道的信息；,将这个分组发送给所有其他的路由器,计算出到每一个其他路由器的最短路径,链路状态路由算法步骤,发现邻居结点，并学习它们的网络地址；,路由器启动后，通过发送,HELLO,包发现邻居结点；,测量到每个邻居结点的延迟或开销；,一种直接的方法是：发送一个要对方立即响应的,ECHO,包，来回时间除以,2,即为延迟。,将所有学习到的内容封装成一个分组；,分组以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；,列表中对应每个邻居结点，都有发送方到它们的延迟或开销；,链路状态分组定期创建或发生重大事件时创建。,将这个分组发送给所有其它路由器；,基本思想：扩散法发布状态分组，为控制洪泛，每个分组包含一个序号，每次发送新分组时加,1,。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；,计算到每个其它路由器的最短路径。,根据,Dijkstra,算法计算最短路径；,子网,链路状态分组,链路状态路由算法应用,Internet,中广泛使用的,OSPF,（,Open Shortest Path,Frist,）开放最短路径优先协议,Distance Vector vs.Link State,距离矢量路由算法,节点,向相邻节点,告诉它,所知道的所有节点,的路由信息,节点根据相邻节点的路由信息更新自己的路由表,链路状态路由算法,节点,向所有节点,告诉,其相邻节点,的状态信息,每个路由器利用收到的路由信息画出一张完整的子网拓扑结构图,5.2.4,移动主机的路由选择,固定主机,永远不会动的主机，常通过有线介质连入网络,迁移主机,基本上是固定的，移动到另一个固定点后，连接到网络才使用主机,移动主机,漫游主机,希望在移动的时候还能保持与网络的连接,把移动主机连入网络,路由算法的目标：,在包含移动主机的系统中，能够做到用移动主机的地址给他们发送分组，而不管这些主机在哪里，这些分组都能够被递交给它们。,问题的解决：,将空间划分成区域,每个区域有一个或多个,外地代理,，用来,管理所有来到当地的移动主机,（负责对外接待）,还有一个,主代理,，用来,管理原本属于本区域,，但当时在外地的用户,（负责对内管理）,网络结构示意图,移动用户进入一个新区域,必须首先向外部代理注册,外地代理定期广播一个分组，声明自己的存在和地址，新到达的移动主机接收该信息；若移动用户未能收到该信息，则移动主机广播包，询问外地代理的地址；,移动主机向外地代理注册，告知其原来所在的地址、目前的数据链路层地址和一些安全信息；,外地代理与移动主机的主代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息；,主代理检查安全信息，通过，则给外地代理确认；,外地代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。,移动用户的路由转发过程,当一个分组发给移动用户时，首先被转发到用户的主局域网；,该分组到达移动用户的主局域网后，被主代理接收，主代理查询移动用户的新位置和与其对应的外地代理的地址；,主代理将收到的分组作为净荷封装到一个新分组中，发给外地代理；,主代理告诉发送方，发给移动用户的后续包作为净荷封装成分组直接发给外地代理，再由外地代理发送给移动主机，这样随后的分组就可以绕过主代理直接通过外地代理路由到移动主机。,发送者,外地代理,主代理,广播路由选择,广播（,broadcasting,）：,同时发送一个分组给所有目的地。,实现广播路由的方法,1,、源主机给每个目标单独发送一个分组，通过多个点到点通信实现，缺点：浪费带宽，源主机需要知道所有目的地；,2,、扩散法，缺点：浪费带宽,3,、多目标路由（,multidestination,routing,）,每个分组包括一个目的地列表或一个目的地位图；,路由器根据目的地做路由选择，在相应输出线路上复制一个分组，并将该线路对应的目的地填入分组中。,4,、广播算法（使用汇集树或者生成树）,5,、逆向路径转发,广播算法,利用汇集树（,sink tree,）,或生成树（,spanning tree,）,生成树是通信子网的一个子集，能将所有路由器连接起来，并且没有回路；,汇集树是,最佳路由集合,如果每个路由器知道它的哪些线路属于生成树，则将收到的广播包拷贝到输入线路以外的所有其它生成树线路上；,算法评价,优点：最优利用带宽，产生最小数目的分组,缺点：每个路由器都需要构造生成树,链路状态路由算法可以使用,距离矢量路由算法不可以使用,逆向路径转发,当广播分组到达一个路由器时，路由器对它进行检查，查看它到来的那条线路是否是通常用来给广播源发送分组的那条线路，如果是，该路由器将把这个广播分组复制转发到除输入线路外的所有线路。如果不是，则这个分组将被废弃。,优点：效率相对合理，而且容易实现,逆向路径转发,汇集树,第一跳：,F,H,N,J;,第二跳：,A,D,M,O,G,；第三跳,:C,E,K,；第四跳,:B,L,逆向路径转发,第一跳：,F,H,N,J;,第二跳：,A,D,E,K,G,O,M,O,；第三跳,:E,C,G,D.N,K,；第四跳,:H,B,L,H;,第五跳：,L,B,汇集树,H,5.2.6,多播,路由选择,能够给一些有明确定义的组发送消息称为多点播送，简称多播，又称组播，它的路由算法称为多播路由选择。,实现多点播送需要有良好的小组管理机制；,创建或销毁组，允许加入或离开组,为了实现多点播送路由选择，每个路由器需要计算出一棵覆盖整个子网的生成树；,修剪生成树,生成树的修剪工作可以从树的端点开始，向树根发展，除去所有不属于相应小组的路由器,修剪方法：链路状态路由算法,多播,路由选择,1,2,1,2,2,2,2,1,1,1,1,2,1,2,2,2,2,1,1,1,1,1,1,1,1,2,2,2,2,2,一个子网,最左边路由器的生成树,小组,1,的多点播送树,小组,2,的多点播送树,拥塞控制 考核要求,识记：拥塞现象的原因，流量控制和拥塞控制的差异。拥塞控制的必要性。,领会：拥塞控制的基本原理，拥塞控制方法。,5.3,拥塞控制,什么是网络的拥塞,当大量分组进入通信子网，超出了网络的处理能力时，就会引起网络局部或整体性能下降，这种现象称为,拥塞,。,严重时导致网络通信业务陷入停顿，出现,死锁现象,。,拥塞会导致什么后果,拥塞使许多分组重传,导致更多的业务量，直至崩溃,拥塞控制,图 当通信量太大时,会发生拥塞,性能显著降低,.,发送的分组,提交的分组,子网的,最大,传输容量,完美的,理想的,拥塞的,5.3.1,拥塞发生的原因,（,1,）多条流入线路有分组到达，并需要同一输出线路，若路由器没有足够的内存来存放这些分组，那么有的分组就会丢失。,（,2,）路由器的处理速度较慢,拥塞控制与流量控制,拥塞控制,任务是确保子网能够承载所到达的流量,是全局问题，涉及的节点包括主机、路由器,流量控制,任务是确保接收端或所在网络的接收速度小于发送端的发送速度,只与特定的发送方和特定的接收方之间的点到点流量相关，是局部问题,由于解决方法相似，两者经常混淆,拥塞控制,2.,拥塞控制与流量控制的关系,图 拥塞控制所起的作用,输入负载,吞吐量,子网的,最大,传输容量,理想的流量控制,实际的流量控制,0,网络吞吐量,=,网络负载,吞吐量饱和,无,流量控制,轻度,拥塞,拥塞,死锁,当网络负载,继续增大到,某一数值,时,网络的吞吐,量就下降为,零,网络已无,法工作,.,这就,是所谓的,“死锁”,5.3.2,拥塞控制的通用原则,从,控制理论观点出发，可分为两类：,开环控制，基于良好的设计,确定何时接受新分组、何时丢弃分组及丢弃哪些分组，以及在网络的不同点上执行调度决策。,闭环控制，基于反馈概念,监测系统何时、何处发生拥塞,指示网络拥塞的参数,分组丢失率、平均队列长度、分组重传率、平均分组延时,将拥塞信息传到能控制它的地方,路由器给流量源发送分组,在每个分组头中保留一个位或域，当拥塞超过一定值时，路由器就在该位或域上填上拥塞信息通知网络节点,由主机或路由器发送询问分组打听拥塞情况,调整系统操作,算法和解决方案,开环算法,在源端采取行动,在目的端采取行动,闭环算法,显式反馈,从拥塞点向源端发送分组以警告,隐式反馈,源端利用本地观察判断是否存在拥塞,出现拥塞的解决方案,增加资源（带宽）,降低负载,拒绝为某些用户服务,给某些用户或全部用户降低服务等级,用户以一种有预见性的方式安排需求,5.3.3,拥塞预防策略,传输层,重传机制,乱序缓存策略,确认策略,流控制策略,确认超时策略,网络层：,虚电路或数据报？,分组排队和服务策略：,分组丢弃策略,路由选择算法,分组生存期管理,数据链路层：,重传机制：选择重传或,Go-Back-N,乱序缓存策略：,排队,确认策略：反馈延迟,流量控制：基于窗口和基于速率。,5.3.4,虚电路子网中的拥塞控制,虚电路子网的动态拥塞控制方法：,准入控制（,admission control,），基本思想：一旦发生拥塞，在问题解决之前，不允许建立新的虚电路；,另一种方法是发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区；,资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。,5.3.5,数据报子网中的拥塞控制,路由器可以监视它的输出线路和其他资源的使用情况，如线路使用率,U,，如果输出线路处于警告状态，需要采取下列措施：,警告位：,在分组的头部设置一个特殊的位来指示警告状态，传输实体将这一位复制到下一个确认分组中，送回主机，源主机就可消减流量。,抑制分组：,路由器向有关源主机发送抑制分组，,指出发生拥塞的目的地址。同时将原分组打上标记（为了以后不再产生抑制包），正常转发；,源主机收到抑制包后，按一定比例减少发向特定目的地的流量，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、忽略抑制包；若在监听周期内没有收到抑制包，则增加负载；,逐跳抑制分组：,抑制分组影响到沿途的每一跳,a,抑制分组只影响源主机,b,抑制分组影响到沿途的每一跳,5.3.6,负载丢弃,上述算法都不能消除拥塞时，路由器只得将分组丢弃，实施,负载脱落,；,针对不同服务，可采取不同丢弃策略,文件传输，优先丢弃新分组，葡萄酒,(wine),策略；,流媒体服务，优先丢弃旧分组，牛奶,(milk),策略；,智能丢弃策略，按照分组的优先级先丢弃低优先级的,早期丢弃包，会减少拥塞发生的概率，提高网络性能。,RED,随机的早期预测算法,当某条线路上的队列平均长度超过一定阈值的时候，该线路被认为是拥塞的，需要采取措施。,5.3.7,抖动控制,分组到达时间的变化量（即标准偏差）被称为,抖动,路由器转发的分组可以选定为偏离预定时间最远的分组,消除抖动：接收方将分组缓存,5.4,服务质量（,QoS,),考核要求：,识记：集成服务和区分服务，标签交换和,MPLS,的概念,从一个源到一个目标的分组流称为一个流。,面向连接的网络,一个流的所有分组会走同样的路由路径,面向无连接的网络,一个流的所有分组可能会走不同的路径,服务质量的四个特征：可靠性、延迟、抖动、带宽,不同业务对服务质量的需求,应用,可靠性,延迟,抖动,带宽,E-mail,high,low,low,low,文件传输,High,low,low,medium,Web,访问,High,medium,low,medium,远程登录,High,medium,medium,low,音频点播,low,low,high,medium,视频点播,low,low,high,high,电话,low,high,high,low,视频会议,low,high,high,high,服务质量（,QoS,),控制方法,高可靠性：发送方计算每一个分组的校验和，接收方验证此校验和。,不同的应用对性能的需求各不相同。,提高服务质量可将多种技术结合：,过度提供资源,流量整形,资源预留,准入控制,分组调度,5.4.1,集成服务和区分服务,集成服务,基于流的算法,针对单播或多播应用,资源预留，要求提前一步建立每个流,区分服务,基于类别的,不要求提前建立流,主要由每台路由器在局部范围内实现，不牵涉到整条路径,5.4.2,标签交换和,MPLS,标签交换,在每个分组的前端增加一个标签，然后根据这个标签进行路由选择。,做法接近虚电路的思想,MPLS,IETF,对标签交换的思想标准化为：多协议标签交换（,MPLS,）,是实现服务质量（,QoS,）的保障,目的是提高网络设备的性价比，提高网络设备的转发能力,MPLS,是实现通过,ATM,网络来传输,IP,分组的最佳途径,把二层交换和三层路由与网络业务结合在一起，利用标签识别减少了寻址路由的复杂性。,MPLS Operation,1a.,使用路由协议做,寻址路由,1b.,使用标签交换的方式,2.,在分组前端加上标签,IP,IP,10,3.,用表格查询将分组转发,IP,20,IP,40,4.,将分组前端的标签去除,IP,5.5,网络互连 考核要求,识记：网络互连的基本原理，网桥技术。,领会：,RIP,和,OSPF,，网桥、路由器和网关等网际互连所使用的中继设备及其对应的,OSI,层次，网桥、交换机、路由器的基本工作原理。,综合应用：网络互连的概念，网络互连模型，网络互连设备。,5.5.1,网络互连原理,网际互连的目的是使一个网络上的用户能访问其它网络上的资源，使不同网络上的用户互相通信和交换信息。,要实现网际互连，必须：,(1),在网络之间至少提供一条物理上连接的链路，并具有对这条链的控制规程；,(2),在不同网络的进程之间提供合适的路由实现数据交换；,(3),有一个始终记录不同网络使用情况并维护该状态信息的统一的记费服务；,(4),在提供以上服务时，尽可能不对互连在一起的网络的体系结构做任何修改。,网络的差异,表现在寻址方式、路由选择、最大分组长度、网络接入机制、用户接入控制、超时控制、差错恢复方法、状态报告方法、服务（面向连接服务还是无连接服务）、管理方式等诸方面的不同。,局域网,(LAN),、广域网,(WAN),的网际互连,LAN-LAN,LAN-WAN,WAN-WAN,LAN-WAN-LAN,网络互连设备,用于网络之间互连的中继设备称为网间连接器，按它们对不同层次的协议和功能转换，可以分为以下几类：,(1),转发器,(Repeater),，实现物理层的连接，对信号进行放大整形或再生，扩展了网段距离。,(2),网桥,(Bridge),，提供链路层间的协议转换，在局域网之间存储和转发帧；,(3),路由器,(Router),，作用于网络层，提供网络层上的协议转换，在不同的网络之间存储和转发分组；,(4),网关,(Gateway),，提供传输层及传输以上各层间的协议转换。,网络互连设备,转发器,Repeater,网桥,Bridge,路由器,Router,网关,Gateway,5.5.2,网桥技术,网桥工作在,OSI,模型的第二层，进行相似网络间帧的转发。,IEEE802.1,定义了网桥的协议结构。,网桥的作用,网桥可跨网段传输数据帧,网桥可接收控制帧、目的地址为桥的帧,网桥要有足够缓冲区,网桥应有寻址和路由功能,(,转发,MAC,帧,),网桥的作用通过过滤和转发功能实现的。,网桥按照其路由表的建立方法分为两类,-,透明网桥（,transparent bridge,）,-,源路选网桥（,source routing bridge,）,网桥过滤和转发功能,1.,透明网桥,网桥按照路由选择可以分为透明网桥和源路由网桥。,透明网桥的设计目标：把几个局域网连接在网桥上之后立即可以运行，不需要进行硬软件配置，不用装入路由表参数。,透明网桥的路由机制,采用生成树算法的技术,。,透明网桥,以混杂方式工作,每个网桥维护一个基于,MAC,地址的过滤数据库，内容包括目的地、线路、超时。,透明网桥,有一个自动学习的机制,采用逆向学习法，从收到帧的源地址确定端口连接的,LAN,位置。,生成树算法,生成树协议,通过实现生成树协议相互的交换信息,利用交换的信息将网络中的环路断开,逻辑上形成一种树形结构,按照逻辑结构转发信息,生成树的根选择序列号最小的网桥,生成树算法的技术,通信过滤,1.,目的：隔离本地信息，避免不必要的数据流动,2.,方法：,利用端口,/MAC,地址映射表和帧的目的地址决定是否转发或转发到何处,如果地址表中不存在帧的目的地址，交换机则需要向除接收端口以外的所有端口转发,通信过滤举例,透明网桥,计算机,A,A,到,F,，查表后发往,4,号端口,A,到,C,，查表后发往,1,号端口,A,到,G,，查表后发往所有端口,自动学习的机制,1.,建立端口,/MAC,地址映射表需要解决的问题,透明网桥怎样知道哪台计算机连接哪个端口,透明网桥怎样维护地址映射表以保持其“新鲜”,2.,地址学习,读取帧的源地址并记录帧进入透明网桥的端口（节点只要发送信息，透明网桥就能建立该表项）,利用计时器维护表项的“新鲜”性,2.,源路由选择网桥,核心思想,假定发送者知道接收者是否在同一个,LAN,上。当发送一帧到另外的网段时，源机器将目的地址的高位设置成,1,作为标记。另外，它还在帧头加进此帧应走的实际路径。,构造过程,源路由选择网桥要求,信息源,(,不是网桥本身,),提供传递帧到目的站点所需的路由信息,放在帧头，网桥读取帧头，判断如何转发。,源路由选择前提,互联网中的每台机器都知道所有其他机器的最佳路径。,源机器发送广播帧，途经的网桥将他们自己的标识纪录在应答帧中。,透明网桥一般用于连接以太网段，而源路由选择网桥则一般用于连接令牌环网段。,5.5.3,网络互连协议,1.,路由信息协议,RIP,RIP,是一种基于,距离向量,的路由选择协议。,可以在主机或路由器中实现,在主机中实现是被动状态，只接收其他,RIP,路由器的广播路由信息。,在路由器中实现是主动状态，发送和接收,RIP,消息。,RIP,协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。,“距离”的定义,RIP,中采用的,距离量度是站点计数度量,。,从一路由器到,直接连接,的网络的距离定义为,1,。,如果距离是,n,，表示到达目的地途中要经过,n,个路由器。,RIP,认为一个好的路由就是它通过的路由器的数目少，即“距离短”。,RIP,不能在两个网络之间同时使用多条路由。,RIP,协议的三个要点,仅和相邻路由器交换信息。,交换的信息是当前本路由器所知道的全部信息，即自己的路由表。,按固定的时间间隔交换路由信息，例如，每隔,30,秒。,六次交换信息中至少一次收到关于某路由的消息（,180,秒），才会认为该路由合法，否则该路由会在路由表中删除。,1 1,2 1,3 1,F,E,D,C,B,A,5 1,6 1,2 1,5 1,3 1,4 1,4 1,6 1,1 1,5 1,一开始，各路由表只有到相邻路由器的信息,网,3,网,2,网,4,网,6,网,5,网,1,“,4”,表示“从本路由器到网,4”,“,1”,表示“距离是,1”,“,”表示“直接交付”,1 1,2 1,3 1,F,E,D,C,B,A,5 1,6 1,2 1,5 1,3 1,4 1,4 1,6 1,1 1,5 1,路由器,B,收到相邻路由器,A,和,C,的路由表,网,3,网,2,网,4,网,6,网,5,网,1,1 1,2 1,3 1,4 1,6 1,1 2 A,2 2 A,3 1,4 1,6 2 C,更新后,A,说：“我到网,1,的距离是,1,。”,因此,B,现在也可以到网,1,，,距离是,2,，经过,A,。”,1 1,2 1,3 1,F,E,D,C,B,A,5 1,6 1,2 1,5 1,3 1,4 1,4 1,6 1,1 1,5 1,路由器,B,收到相邻路由器,A,和,C,的路由表,网,3,网,2,网,4,网,6,网,5,网,1,1 1,2 1,3 1,4 1,6 1,1 2 A,2 2 A,3 1,4 1,6 2 C,更新后,A,说：“我到网,2,的距离是,1,。”,因此,B,现在也可以到网,2,，,距离是,2,，经过,A,。”,1 1,2 1,3 1,F,E,D,C,B,A,5 1,6 1,2 1,5 1,3 1,4 1,4 1,6 1,1 1,5 1,路由器,B,收到相邻路由器,A,和,C,的路由表,网,3,网,2,网,4,网,6,网,5,网,1,1 1,2 1,3 1,4 1,6 1,1 2 A,2 2 A,3 1,4 1,6 2 C,更新后,A,说：“我到网,3,的距离是,1,。”,但,B,没有必要绕道经过路由器,A,再到达网,3,，因此这一项目不变。,1 1,2 1,3 1,F,E,D,C,B,A,5 1,6 1,2 1,5 1,3 1,4 1,4 1,6 1,1 1,5 1,路由器,B,收到相邻路由器,A,和,C,的路由表,网,3,网,2,网,4,网,6,网,5,网,1,1 1,2 1,3 1,4 1,6 1,1 2 A,2 2 A,3 1,4 1,6 2 C,更新后,C,说：“我到网,4,的距离是,1