数据链路层仅将数据帧从导线的一端送到其另一端.ppt

第五章 网络层,2008,数据链路层仅将数据帧从导线的一端送到其另一端。网络层将源端发出的分组经各种途径送到目的端。网络层是处理端到端数据传输的最底层。网络层必须知道通信子网的拓扑结构（即所有路由器的位置），并选择通过子网的合适路径。网络层在选路时，应避免一些通信线路超负荷，而另一些通信线路却处于空闲。当源与目的地不处于同一网络时，应该由网络层来处理这些差异。,网络层设计的有关问题,为传输层提供的服务子网的内部设计,为传输层提供的服务,网络层在网络层/传输层接口上为传输层提供服务。网络层/传输层接口是载体与用户的接口，是通信子网的边界。载体通常决定了直到网络层的各种协议和接口，它的工作是传输由其用户提供的分组。网络层提供的服务按下列目标进行设计：1、服务应与通信子网技术无关。2、通信子网的数量、类型和拓扑结构对于传输层来说是隐蔽的。3、传输层所能获得的网络地址应采用统一的编号方式，即使跨越了多个LAN和WAN。,上述目标导致两个相对集团的激烈冲突。冲突的焦点是网络层该提供什么服务：面向连接，无连接。无连接的观点：通信子网不可靠，主机必须进行差错控制和流量控制。面向连接的观点：子网应该提供一种可靠的、面向连接的服务。面向连接和无连接服务方式间的争论，实质是将复杂的功能放在何处的问题。P260实际上，网络层是否面向连接和网络层是否可靠是两个独立的问题。四种组合：重要的两种组合：可靠的、面向连接；不可靠的、无连接因特网具有一个无连接的网络层，ATM有一个面向连接的网络,存储-转发分组交换,若有一台主机要发送一个分组，则它将分组传送给最近的路由器，该路由器或在它自己的LAN上，或在一条通向承运商的点到点链路上。该分组被存储在路由器上，一直到它完全到达路由器为止，所以路由器可以验证它的校验和。然后它被沿路转发到下一台路由器，直到到达目标主机为止，最后在目标主机上它被递交给相应的进程。,无连接服务的实现,所有的分组都被独立地传送到子网中，并且独立于路由，不需要提前建立任何辅助设施。在此环境中，分组称为数据报，且子网称为数据报子网。,面向连接服务的实现,若使用面向连接的服务，则在发送数据分组之前，必须首先建立一条从源路由器到目的路由器之间的路径。这个连接成为一个VC（虚电路），子网成为虚电路子网。虚电路的思想：不需要每次为一个分组选择一条新路径，当一个连接被建立起来的时候，从源机器到目的机器之间的一条路径被选择作为连接的一部分，并且保存在中间这些路由器的内部表中。对于所有在这个连接上通过的流量，都使用这条路径。在面向连接的服务中，每个分组都包含一个标识符，指明了它属于哪一个虚电路。,虚电路子网和数据报子网的比较,路由器的内存空间和带宽之间的平衡。建立虚电路所需的时间和地址解析的时间。路由器内存需要的表空间数量。在服务质量方面，虚电路有优势。若路由器崩溃，虚电路中断。,路由选择算法,网络层的主要功能是将分组从远端机器经选定的路由送到目的端机器。在大多数子网中，分组的整个旅途需要经过多次转发。路由选择算法和它们使用的数据结构是网络层设计的一个主要区域。路由选择算法是网络层软件的一部分，负责确定所收到分组应传送的外出路线。,若子网内部采用数据报，对收到的每个分组都要重新作路由选择，因为对每个分组来说，上次到达的最佳路由可能已经被改变。若子网采用虚电路，仅需作一次路由选择决策，以后，数据就在这条先前建立的路由上传送。又称会话路由选择，因为在整个用户会话期间都存在同一条有效的路由。不论哪种情况，都希望路由选择算法具有某种特征：正确性、简单性、健壮性、稳定性、公平性、最优性。,路由算法的分类：自适应，非自适应非自适应算法：不根据实测或估计的网络的当前通信量和拓扑结构来作路由选择。路由表是事先计算好的，在网络启动后下载到路由器中。又称静态路由选择。自适应算法：根据拓扑结构，通常还有通信量的变化来改变其路由选择。自适应算法分类的依据：获取信息方式的不同，改变路由选择的条件的不同，用于进行优化的参数的不同。,最优化原则,最优化原则，P265,新书P297汇集树，P265,新书P297,最短路由选择,扩散法,在扩散法中，每一个进来的分组将被发送到除了它进来的那条线路之外的每一条输出线路上。会产生大量重复分组需要采用抑制措施一种方法是计数，计数到0，丢弃分组。另一种方法是记录已被扩散的分组。选择性扩散法P269，新书P301,距离矢量路由,上面介绍的静态路由算法。现代计算机网络通常采用动态路由算法。常见的两个动态路由算法：距离矢量路由算法，链路状态路由算法距离矢量路由算法的工作原理：每个路由器维护一张表（即一个矢量），表中列出了当前已知的到每个目标的最佳距离，以及所使用的线路。通过在邻居之间相互交换信息，路由器不断地更新它们内部的表。,在距离矢量路由算法中，每个路由器维护了一张路由表，它以子网中的每个路由器为索引，并且每个路由器对应一个表项。该表项包含两部分：为了到达该目标路由器而首先使用的输出线路，以及到达该目标路由器的时间估计值或距离估计值。,无穷计算问题,距离矢量路由算法有一个严重缺陷：虽然它总是能够得到正确答案，但是它收敛到正确答案的速度可能非常慢。对好消息的反应快。对坏消息的反应非常迟缓。,链路状态路由,链路状态路由选择的思想：1、发现它的邻居节点，并知道其网络地址。2、测量到各邻居节点的延时或开销。3、构造一个分组，分组中包含所有它刚刚知道的信息。4、将这个分组发送给所有其他的路由器。5、计算出到每个其他路由器的最短距离。,发现邻居节点,当一个路由器启动的时候，它的第一个任务是找出哪些路由器是它的邻居。为了实现这个目标，它只需在每一条点到点线路上发送一个特殊的HELLO分组即可。线路另一端的路由器应该回送一个应答来说明它是谁。这些名字必须是全局唯一的。,测量线路开销,链路状态路由算法要求每一个路由器知道它到各个邻居节点之间的延时，或者至少有一个合理的估计值。为了确定这份延时信息，最直接的办法是在这条线路上发送一个特殊的ECHO分组，另一端必须立即送回一个应答。通过计算出往返时间，再除以2，则发送方路由器就可以得到一个合理的延时估计值。这种方法隐含了一个假设，即两个方向上的延时是对称的，而在实践中并不总是这样的。,创建链路状态分组,一旦所需要的交换信息已经收集到了，每个路由器的下一步工作是建立一个包含所有这些数据的分组。该分组的内容首先是发送方的标识，接着是一个序列号（seq）和（age）,以及一个邻居列表。对于每个邻居，给出到这个邻居的延时。,什么时候创建链路状态分组？定期重要事件发生时,发布链路状态分组,链路状态路由算法最技巧的部分是如何可靠地发布链路状态分组。P277,新书P307基本的思路是，使用扩散法来发布链路状态分组。为了控制扩散过程，每一个分组都包含一个序列号，序列号随着每个新的分组而递增。每个路由器记录下它所看到的所有（源路由器、序列号）对。当一个新的链路状态分组进来的时候，路由器在已经看到的分组列表中检查这个新进来的分组。若它是新的，则除了它到来的那条线路外，在其他线路上都转发该分组。若是重复的，则丢弃。若一个分组的序列号小于当前所看到过的来自该源路由器的最大序列号，则它将被当作过时分组而被拒绝，因为该路由器已经有了更新的数据。,计算新的路由路径,一旦一个路由器已经获得了全部的链路状态分组之后，它就可以构造出完整的子网图了。每条链路被表示了两次，每个方向各一次。用Dijkstra算法构造所有到目标节点的最短路径。,因特网中的路由选择,静态路由选择也叫做非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。动态路由选择也称为自适应路由选择，其特点是能较好地适应网络状态的变化。但实现起来较为复杂，开销也比较大。因特网采用的路由选择协议属于自适应的（即动态的）、分布式路选择协议。,由于以下两个原因，因特网采用分层次的路由选择协议：（1）因特网的规模非常大，已经有几百万个路由器互连在一起。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使因特网的通信链路饱和。（2）许多单位不愿意外界了解自己单位网络的布局细节和本单位所采用的路由选择协议（这属于本单位内部的事情），但同时还希望连接到因特网上。,基于以上原因，因特网将整个互联网划分为许多较小的自治系统（AUTONOMOUS SYSTEM），一般简称为AS。一个自治系统是一个互联网，其最重要的特点就是它有权自主地决定在本系统内应采用何种路由选择协议。因特网就把路由选择协议划分为两大类：内部网关协议IGP（INTERIOR GATEWAY PROTOCOL）外部网关协议EGP（EXTERNAL GATEWAY PROTOCOL）,内部网关协议IGP（INTERIOR GATEWAY PROTOCOL）。这是一个自治系统内部使用的路由协议，而这与在互联网中的其他自治系统选用什么路由选择协议无关。目前这类路由选择协议使用得最多，如RIP和OSPF协议。外部网关协议EGP（EXTERNAL GATEWAY PROTOCOL）。若源站和目的站处在不同的自治系统中（这两个自治系统使用不同的内部网关协议），当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议EGP。在外部网关协议中目前使用最多的是BGP,自治系统之间的路由选择也称为域间路由选择（INTERDOAIN ROUTING），而在自治系统内部的路由选择称为域内路由选择（INTRADONAIN ROUTING）。内部网关协议IGP：具体的协议有多种，如RIP和OSPF等。外部网关协议EGP：目前使用的协议就是BGP。,RIP：是一种分布式的基于距离向量的路由选择协议，是因特网的标准协议，其最大优点就是简单。RIP协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录（因此，这是一组距离，即“距离向量”）。RIP协议将“距离”定义如下：从一路由器到直接连接的网络的距离定义为1。从一种路由器到非直接连接的网络的距离定义为所经过的路由器数加1。,RIP协议让互联网中的所有路由器都和相邻路由器不断交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。这里还应注意：虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也应当是不同的。RIP协议使用传输层的用户数据报UDP进行传送。因此RIP协议的位置应当在应用层。,OSPF：最主要的特征就是使用分布式的链路状态协议（link state protocol）而不是像RIP那样的距离向量协议。和RIP的3个要点相比，OSPF的三个要点和RIP的都不一样：（1）OSPF向本自治系统中所有路由器发送信息。这里使用的方法是洪泛法（flooding），就是路由器通过所有相邻的路由器发送信息。而每一个相邻路由器又再将此信息发往其所有的相邻路由器（但不再发送给刚刚发来信息的那个路由器）。RIP协议是仅仅向自己相邻的几个路由器发送信息。,（2）OSPF发送的信息就是与本路由器相邻的所有路由器的链路状态 所谓“链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”（metric），例如费用、距离、时延、带宽等等。对于RIP协议，发送的信息是：“到所有网络的距离和下一跳路由器”（3）OSPF只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。而不像RIP那样，不管网络拓扑有无发生变化，路由器之间都要定期交换路由表的信息。,为了使OSPF能够用于规模很大的网络，OSPF将一个自治系统再划分为若干个更小的的范围，叫做区域（area）。一个区域也不能太大，在一个区域内的路由器最好不超过200个。,划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统。因此，在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。为了使每一个区域能够和本区域以外的区域进行通信，OSPF使用层次结构的区域划分。在上层的区域叫做主干区域（BACKBONE AREA）。主干区域的标识符规定为。主干区域的作用是用来连通其他在下层的区域。从其他区域来的信息都由区域边界路由器（AREA BORDER ROUTER）进行概括。,在上图中，路由器R3、R4和R7都是区域边界路由器，而显然，每一个区域至少应当有一个区域边界路由器。在主干区域内的路由器叫做主干路由器（BACKBONE ROUTER），如R3、R4、R5、R6和R7。一个主干路由器可以同时是区域边界路由器，如R3、R4和R7。在主干区域内还要有一个路由器专门和本自治系统外的其他自治系统交换路由信息。这样的路由器叫做自治系统边界路由器（如图中R6）。OSPF不用UDP而是直接用IP数据报传送（其IP数据报首部的协议字段值为89）。,OSPF共有以下5种分组类型。类型1，问候（HELLO）分组，用来发现和维持邻站的可达性。类型2，数据库描述（DATABASE DESCRIPTION）分组，向邻站给出自己的链路状态数据库中的所有链路状态项目的摘要信息。类型3，链路状态请求（LINK STATE REPUEST）分组，向对方请求发送某些链路状态项目的详细信息。类型4，链路状态更新（LINK STATE UPDATE）分组，用洪泛法向全网更新的链路状态。这种分组是最复杂的，也是OSPF协议最核心的部分。路由器使用这种分组将其链路状态通知给邻站。链路状态更新分组共有5种不同的链路状态。类型5，链路状态确认（LINK STATE ACKNOWLEDGMENT）分组，对链路更新分组的确认。,OSPF规定，每两个相邻路由器每隔10秒钟要交换一次问候分组。这样就能确知哪些邻站是可达的。在正常情况下，网络中传送的绝大多数OSPF分组都是问候分组。若有40秒钟没有收到某个相邻路由器发来的问候分组，则可认为该相邻路由器是不可达的，应立即修改链路状态数据库，并重新计算路由表。,其他的四种分组都是用来进行链路状态数据库的同步。所谓同步就是指不同路由器的链路状态数据库的内容是一样的。两个同步的路由器叫做“完全邻接的”（FULLY ADJACENT）路由器。不是完全邻接的路由器表明它们虽然在物理上是相邻的，但其链路状态数据库并没有达到一致。,当一个路由器刚开始工作时，它只能通过问候分组得知它有哪些相邻的路由器在工作，以及将数据发往相邻路由器所需要的“费用”。如果所有的路由器都把自己的本地链路状态信息对全网进行广播，那么各路由器只要将这些链路状态信息综合起来就可得出链路状态数据库。但这样做开销太大，因此OSPF采用了另外的办法。即，OSPF让每一个路由器用数据库描述分组和相邻路由器交换本数据库中已有的链路状态摘要信息。摘要信息主要就是指出有哪些路由器的链路状态信息（以及其序号）已经写入了数据库。经过与相邻路由器交换数据库描述分组后，路由器就使用链路状态请求分组，向对方请求发送自己所缺少的某些链路状态项目的详细信息。通过一系列的这种分组交换，全网的同步的链路数据库就建立了。,分级路由,随着网络规模的增长，路由器的路由表也成比例地增长。不断增长的路由表需要占用大量内存，需要更多CPU时间来查找路由表的表项，需要更多的带宽来发送有关的状态报告。因此，路由选择过程必须进行分级。分级之后，路由器被划分成区域，每个路由器知道如何将分组路由到自己所在区域内的目标地址。但不必了解区域外的情况。对于大型的网络，一个两级的分层结构可能还不够；可能有必要组织成群，将群组织成区，将区组织成组。,虽然节省了空间，但也付出了代价。代价的形式是路径长度增加了。对一个单独的网络变得很大时，分多少级比较合适？例子，一个有720个路由器的子网。若分两级，24个区域，每个区域30个路由器，则每个路由器需要的表项数：30个本地，23个远程。若分三级，8个群，每个群9个区域，每个区域10个路由器，则每个路由器需要的表项数：10个本地，8个到群内其它区域，7个到其它群。,广播路由,广播：将消息发送给子网的每个节点。怎样实现？一种不要求子网具有任何特殊特性的广播方式是，让源机器简单地给每个目标单独发送一个分组。缺点是浪费带宽，同时要求源机器拥有所有目标机器的完整地址列表。扩散法，虽然不适合于普通的点到点通信，但对广播而言，值得考虑。缺点是产生太多分组，消耗太多带宽。多目标路由，每个分组或者包含一组目标，或者包含一个位图，由该位图来指定所期望的目标。当分组到达一个路由器时，路由器会根据目标确定必要输出线路，然后为每一条必要线路生成一个副本，在这份副本中只包含了那些使用了这条线路的目标。,第四种，使用以发起广播的路由器为根的汇集树，或使用适当的生成树。若每个路由器都知道它的哪些线路属于一棵生成树，则它就可以将一个进来的广播分组复制到除了该分组到来的那条线路之外的所有生成树线路上。这种方法可以最佳地使用带宽。缺点：每个路由器必须都知道某一棵生成树才可以使用这种方法。采用链路状态路由算法时，可以得到生成树信息，但采用距离矢量路由算法时则无法获得。,第五种广播算法是，即使当路由器根本不知道任何关于生成树的信息时，也要试图达到前一种方法的近似效果。其基本想法称为逆向路径转发：当一个广播分组到达一个路由器的时候，该路由器对它进行检查，看它到来的那条线路是否是通常用来给广播源发送分组的那条线路。若是，那就很有可能该广播分组是沿着最佳路径被转发过来的，因而是到达当前路由器的第一个副本。如果是这种情况，则路由器将该分组转发到除了到来的那条线路之外的所有其他线路上。若广播分组是从其它任何一条并非首选的到达广播源的线路上到来的话，该分组被当作一个可能的重复分组而丢弃。,逆向路径转发的效率相对合理，而且也容易实现。它不要求路由器都知道生成树它不需要像多目标路由方法那样要求每个分组中包含目标列表或位图的开销。它不需要像扩散法那样要求特殊的机制来终止广播。,多播路由,多播传输要求对组进行管理需要一种办法来创建和销毁组，并且允许进程加入或离开组。路由算法关心的是，当一个进程加入组的时候，它需要把这个事实告诉它的主机。知道哪些主机属于组很重要。当主机与组之间的从属关系发生变化时，主机必须将这些变化告诉路由器。或者由路由器定时询问它们的主机。,为了实现多播，每个路由器计算一棵生成树，该生成树覆盖其他的路由器。,修剪生成树的方法：对采用链路状态路由算法的网络，每个路由器都知道完整的拓扑结构。修剪工作从每条路径的末端开始，逐步向根路由器前进，同时去掉所有不属于相应组的路由器。对采用距离矢量路由算法的网络，基本的算法是逆向路径转发。若一个路由器接收到某个特定组的多播消息，但它的主机对这个组不感兴趣，而且它也没连接到其他路由器上，则发一条PRUNE消息作为应答，告诉发送方以后不要再给它发送这个组的消息。若一个路由器自己的主机中没有组成员，并且它在所有的线路上都收到PRUNE消息，则发一条PRUNE消息作为应答。缺点：很难扩展到大型网络。一个网络n个组，每个组m个成员，共需要保存mn棵生成树。改进：基于每个组只计算一棵生成树，其中的根（即核心）在接近组中间的位置上。即基于核心的树。,移动主机的路由,固定主机：永远不会移动迁移主机：从一个固定点移到另一个固定点漫游主机：在移动中执行计算移动主机指后两类,主场所：主机永久不变的位置，用主地址表示。在包含移动主机的系统中，路由算法的目标是，能够做到用移动主机的主地址给它们发送分组，而且不管这些主机在哪里，这些分组都能够被递交给它们。关键是如何找到这些主机。在上图中，整个世界被分成许多小的单元，称为区域，通常一个区域是一个LAN或无线蜂窝单元。每个区域有一个或多个外部代理。每个区域有一个本地代理。外部代理：记录下所有当前正在访问该区域的移动主机。本地代理：记录下那些主场所在本区域，但当前正在访问其他区域的主机。,当一台新的主机进入一个区域，必须在外部代理处注册。注册过程：P281,新书P315,Ad Hoc网络中的路由,前面我们看到了主机移动，路由器固定情况下，路由工作是如何进行的。现在我们看看路由器本身是移动的情况。下面是一些可能的情形：在没有网络基础设施的战场上使用的军用设备。在大海航行的船只。在地震中基础设施被破坏后，那些负责急救工作的人所使用的设备。一群配备了笔记本电脑的人聚集在一个没有802.11网络的地区。,在上述情况，每个节点包含了一个路由器和一个主机，往往是同一台机器。Ad Hoc网络或MANET：网络中的节点两两相邻。在Ad Hoc网络中，有线网络的固定拓扑，固定邻居以及IP地址与场所的固定关系不能用了。AODV路由算法，考虑了移动环境的特点，例如，有限带宽、电源寿命相对较短。AODV是按需算法，只有当有人想给某个目标发送分组时，它才会计算到该目标的路由路径。,AODV中的路径发现,在任何时刻，Ad Hoc网络都可以用一个节点图来描述。若两个节点在它们的半径范围内可以直接通信的话，则将这两个节点连接起来。为简化起见，假设连接是对称的。根据下图来描述AODV算法。,在上图中，节点A上的一个进程想要给节点I发送分组。AODV算法在每个节点上维护了一张表，该表格以目标节点作为关键字，每个表项给出了有关一个目标的信息，包括将分组发送到哪个邻居才可以到达这个目标。假设A检查自己的表，并没有发现针对I的表项。因此，它现在必须要找出一条通向I的路由路径。为了定位到I，A构造一个特殊的ROUTE REQUEST分组，并且将它广播出去。,源地址、目的地址：表示谁在找谁RequestID：每个路由器单独维护的一个本地计数器，每次当一个节点广播ROUTE REQUEST消息时，该计数器增1。源地址和RequestID合起来唯一标识ROUTE REQUEST分组。源序列号、目的序列号：任何时候发送一个ROUTE REQUEST分组（或者应答一个ROUTE REQUEST分组）时候，该序列计数器增1。用来区别新的和旧的路由路径。跳计数：记录了该分组已经经过了多少跳。初始值为0。,当ROUTE REQUEST分组到达一个节点（如B,D）的时候，该节点将按照下面的步骤进行处理。（1）在本地的历史表中查找（源地址，RequestID）对，以确定是否曾经看到过并处理过该请求。若重复，则丢弃；若不重复，则将（源地址，RequestID）对写到历史表中，以便将来的重复分组能被识别。然后处理过程继续进行。（2）接收方在它的路由表中查找该分组中的目标地址。若查到一条较新的通向该目标的路径，则它给源节点送回一个ROUTE REPLY分组。所谓较新的路径是指存储在路由表中的目标序列号大于或等于ROUTE REQUEST分组中的目标序列号。若小于的话，则当前节点存储的路由路径比该源节点以前发送给同一目标的路径还要老，于是执行第三步。,（3）由于接收方并不知道通向该目标的较新的路由路径，所以，它增加跳计数域，并且重新广播ROUTE REQUEST分组。同时它也从分组中提取出数据，并且将它作为一个新的表项保存在逆向路由表中。这份信息将被用来构造逆向路由路径，因此以后应答分组可以回溯到源节点。针对新建立的逆向路由表项，同时启动一个定时器，若定时器到期，该表项被删除。B和D都不知道I在哪里，所以，它们各自创建一个指向A的逆向路由表项，如（b）所示，同时它们也将分组广播出去，其中跳计数被这置为1。B发出的广播分组到达C和D。C在它的逆向路由表中加入一个表项，并且将分组重新广播出去。与此相反，D拒绝该分组，因为这是一个重复分组。如此进行下去，ROUTE REQUEST分组最终到达I。,I接收到ROUTE REQUEST分组之后，它建立一个ROUTE REPLY分组作为应答。源地址、目标地址直接复制请求分组的，目标序列号取自当前内存中的计数器。跳计数置0，Lifetime域控制该路径在多长时间内有效。I节点用单播将ROUTE REPLY分组传送给G，因为它从G接收到ROUTE REQUEST分组。然后该分组沿逆向路径到达D，最后到达A。,AODV中的路径维护,每个节点定期广播HELLO消息，了解邻居状况。活动邻居：在最近的一段时间内曾经给某个节点发送过到达一个目标的分组，这样的邻居称为针对该目标的活动邻居。当D发现G已经死掉，它检查自己的路由表，发现到达E、G、I的路径要经过G，针对这些目标的活动邻居集合是A,B，所以D必须通知它们G不可用。D同时将自己路由表中E、G、I的表项清除。,拥塞控制算法,拥塞：当一个子网或子网的一部分中出现太多分组的时候，网络的性能开始下降。P286图，新书P325拥塞发生的原因：多条输入对一条输出，路由器需建立一个队列，因此需要足够的内存存放分组，若空间不够，则丢弃分组。多增加内存只能提升内存到一定的点，无限增加内存，拥塞会更严重，为什么？P286,新书P325慢速的处理器也可能引起拥塞P286,新书P325,拥塞控制与流控制之间的差异：拥塞控制的任务是确保子网能够承载所到达的流量。是一个全局性的问题，涉及到各方面的行为，包括所有的主机、所有的路由器、路由器内部的存储转发处理过程，以及所有可能会削弱子网承载容量的其他因素。流控制只与特定的发送方和特定的接收方之间的点到点流量有关。,拥塞控制的通用原理,完全开环控制：P287,新书P326闭环控制：P287,新书P326拥塞控制算法：开环与闭环开环：在源端采取动作与在目的端采取动作闭环：显示反馈与隐式反馈显示反馈：从拥塞点向源端发送分组以警告源端。隐式反馈：源端利用本地观察到的现象，比如确认分组送回来所需要的时间，来推断是否存在拥塞。,拥塞预防策略,开环控制拥塞的思想：从一开始就将发生拥塞的可能性降到最小。影响拥塞的策略：P289,P328,虚电路子网中的拥塞控制,上面介绍的拥塞控制方法基本上是开环的。现在介绍几种用于虚电路子网的动态拥塞控制方法。准入控制（admission control）：应用广泛，防止已经拥塞的子网进一步恶化。基本思想：一旦出现拥塞的信号，则不再创建任何虚电路，直到问题排除为止。另一种方法：允许建立新的虚电路，但谨慎地选择路由，使所有新的虚电路都绕开有问题的区域。P295与虚电路有关的另一种策略：建立虚电路时，子网与主机间进行协商以达成一致的约定。P296,新书P330,数据报子网的拥塞控制,现在看看既可用于数据报子网又可用于虚电路子网的拥塞控制方法。每台路由器很容易监测到它的输出线路和其他资源的使用情况。例如，用u表示一条线路最近的利用率，取值范围为01。路由器定期测量瞬时利用率f，然后根据下面公式更新u：u新a u旧（1a）f每当u超过了特定的阀值时，该输出线路进入到一个“警告”状态。路由器对每个新到来的分组都要进行检查，看它的输出线路是否处于警告状态。若是，则需要采取某种措施。例如，警告位、抑制分组、逐跳抑制分组。,警告位,当分组到达它的目标端的时候，传输实体将表示警告状态的一个特殊位复制到下一个确认分组中，所以当这一位被送回到源主机后，源主机就可以削减流量。只要路由器处于警告状态，它就会不停地设置警告位。源主机可以监视这种设置了警告位的确认分组的比例，然后相应地调整它的传输率。,抑制分组,路由器给源主机送回一个抑制分组，并且在抑制分组中指明原分组的目标地址。原来的分组被加上一个标记（设置头部中的一位），因而不会在前行的路上再产生更多的抑制分组。当源主机收到了抑制分组时，按要求，它发送给指定目标的流量必须减少到X百分比。由于发送给同一目标的其他分组可能已经在路上了，并且它们也将会产生更多的抑制分组，所以，在一段固定的时间间隔以内，该主机应该忽略掉所有指向此目标的抑制分组。过了这一段间隔以后，该主机继续监听下一段时间间隔内的抑制分组。,逐跳抑制分组,当网速很高或路由器离源主机的距离很远时，给源主机发送抑制分组并不能很好地起作用。让分组影响到沿途的每一跳。P298,新书P331,负载丢弃,当以上任何一种方法都不能消除拥塞时，路由器就采用负载脱落。到底应该丢弃哪些分组，这应该取决于所运行的应用的类型。葡萄酒策略：P299,新书P333牛奶策略：要实现智能的丢弃策略，应用程序必须在它们的分组中表明优先级。,随机的早期检测,RED：在实际耗尽所有的缓冲区空间之前就开始丢弃分组。在有些传输协议（如TCP）中，针对分组丢弃的响应措施是源主机减慢传输速度。依据是：TCP针对有线网设计的，而有线网非常可靠，所以，分组丢弃的主要原因是缓冲满了，而非传输错误。为了确定该什么时候开始丢弃分组，路由器维护了最近队列的平均长度。当超过一定阀值时，该线路被认定拥塞，从而采取措施。由于路由器无法判定是哪个源引起的，因此，只能从拥塞队列中随机选取分组。路由器通知源端的方法：发抑制分组，只丢弃不报告抑制分组的缺点：在已经拥塞的网络中引入了更多的负载。只丢弃不报告不能用于无线网络。,抖动控制,抖动：分组到达时间的变化量（即标准差）对抖动的控制：当一个分组到达一个路由器时，检查它比预定时间来早了还是来晚了，这些信息保存在分组中，每一跳都更新。若来早了，则多停留一些时间再转发，以便回到预定时间点。若来完了，则路由器尽可能快地将它转发出去。对抖动控制的前提：计算出沿途每一跳的期望传输时间。对于多个正在竞争同一输出线路的分组，所使用的算法总是选择偏离预定时间最远的分组优先转发，这样提前到达的就会减速，而落后的会加速。无论哪种情况，都可以减缓抖动的程度。,服务质量,从一个源到一个目标的分组流称为一个流。在面向连接的网络中，属于同一个流的所有分组将会走同样的路由路径。在无连接的网络中，属于同一个流的所有分组可能走不同的路由路径。描述每个流的需求特征的基本参数：可靠性、延时、抖动、带宽。上述四个特征决定了一个流所要求的服务质量QoS。,过渡提供资源：提供足够的路由器容量、缓冲区空间和带宽。缓冲能力流量整形资源预留准入控制比例路由：将到达每个目标节点的流量分散到多条路径分组调度,获得好的QoS所使用的技术,缓冲能力,流量整形,拥塞发生的原因：流量的突发性解决办法：1、主机以恒定的速率发送 2、流量整形流量整形：强迫分组以某种更有可预见性的速率传送。滑动窗口协议只是限制一次能传送数据的数量，而不是传送的速率。流量整形减少了拥塞，对实时数据很重要。,通信量整形在虚电路子网上容易实现，但在数据报子网上相对较困难。对于数据报子网，可以在传输层连接中使用相同的办法。漏桶算法令牌桶算法,漏桶算法,从概念上讲，每台主机都通过一个包含漏桶的接口与网络相连。漏桶是一个有限内部队列。若分组到达队列时队列已满，分组就会被丢弃。这种管理方式可以作进硬件，也可由操作系统模拟。,主机每隔一个时钟节拍向网络发送一个分组，这可通过接口卡或操作系统强制实施。这一机制将主机中用户进程的不均匀分组流转发为输向网络的匀速分组流，使得突发的数据流变得平滑，并大大减少了拥塞出现的机会。若分组都是同样大小，例如ATM信元，漏桶算法可如上所述那样使用。当使用可变长大小的分组时，最好规定每个节拍发送的字节数，而不是一个节拍发送一个分组。,原始漏桶算法的实现：漏桶由一个有限队列构成。当分组到达时，若队列未满，将其加到队尾，否则丢弃。每个时钟节拍发送一个分组（除非队列为空）。字节计数漏桶的实现也基本相同：每个节拍开始时，计数器初始化为n。若队列的第一个分组的字节数小于当前计数器值，就将其发送出去，计数器减去分组的字节数。只要计数器的值足够大，下一个分组也有可能发送。若计数器的值小于队列中下一个分组的长度字节数，传输便停止，直到下一个节拍开始。,令牌桶算法,漏桶算法强迫输出模式保持一个固定的平均速率，而不管突发通信量的大小。令牌桶算法能够做到当大的通信量到来时，输出也相应地加速。在令牌桶算法中，漏桶可以保留令牌，由一个时钟每隔一个时间间隔生成一个令牌。,令牌桶算法和漏桶算法的区别：漏桶算法不允许空闲主机保留发送权，而令牌桶算法则允许，最大到桶的大小。漏桶算法会在桶满时丢弃分组，而令牌桶算法在桶满时会丢失令牌，但决不会丢弃分组。可能每个令牌代表的不是发送一个分组的权力，而是K个字节。只有当所有的令牌代表的字节长度超过分组长度时，该分组才能被发送，零碎令牌被保留起来供将来使用。,基本令牌桶算法的实现：每隔一个时间间隔，计数器增1，当一个分组被发送出去时，计数器减1。当计数器减到0时，就不再发送分组了。在按字节计数的变种算法中，每隔一个时间间隔，计数器增加K，当发送分组时，减去每一个发送分组的长度。最大速率突发时间长度P293,新书P342,资源预留,前提：一个流的所有分组沿同一条路径转发。可以在特定路径上预留资源。有三种潜在资源可以被预留：带宽、缓冲空间、CPU周期预留带宽不能超额当一个分组到来时，通常被滞留在网络接口卡上，这是由硬件接口卡完成的。然后路由器软件将该分组复制到一个RAM缓冲区中，并且对缓冲区进行排队，以被在选择的输出线路上将分组转发出去。处理分组必须占用路由器的CPU时间。,一个分组所经历的平均延时T为：CPU的利用情况,准入控制,通过前述工作，来自某个分组流的流量已经有了很好的形状，并沿同一路径转发，沿途路由器都预留了资源。即使这样，当分组流被转发到一台路由器时，该路由器必须根据它的能力和它对其他流所作出的承诺，决定是否接受。要决定接收或拒绝一个分组流，不只是简单地比较一下该流所要求的带宽、缓冲区、CPU周期与路由器当前剩余的这三种资源的数量。路由器所做的工作要复杂的多。首先，尽管有的应用可能知道它们的带宽需求，但很少有应用会知道它们对缓冲区和CPU周期的需求，所以，至少需要用一种适当的方式来描述这些流。其次，有的应用比其他应用更能容忍偶然错误的底线。最后，有的应用可能希望对流的参数进行协商。,流规范或流说明（flow specification）：流协商过程会涉及许多方（接收方、发送方、路由器），所以在描述流时，必须要精确地指出可以被协商的参数。这样一组参数被称为一个流规范。通常，发送方生成一个流规范，在其中指出希望使用的参数。当这份流规范沿着路径传播时，每台路由器对它进行检查，并根据需要修改相应的参数。对参数的修改只可以降低该流的质量，而不能提高它的质量。当流规范到达另一端时，其中的参数就建立起来了。,分组调度,若一个路由器正在处理多个流，那么，这样的情形太危险：一个流占用了太多的系统资源，而其他的流的得不到资源。若按照分组到达的顺序来处理分组，则意味着一个激进活跃的发送方将会占用沿途路由器上的大部分资源，同时降低了其它发送方的服务质量。研究人员设计了各种分组调度算法来避免这种情况。公平排队算法公平排队的改进算法加权的公平排队算法,公平排队算法,该算法的本质是，路由器为每一条输出线路使用一组单独的队列，每个流一个队列。当一条线路空闲时，路由器轮流扫描这些队列，从下一个队列中取出第一个分组。按这种方法，若有n台主机争用一条输出线路，那么，在每发送出去的n个分组中，每台主机各有一个分组。,公平排队的改进算法,上述算法存在的问题：使用大分组的主机占用了更多的带宽。在改进算法中，轮流循环扫描是逐个字节进行，而不是逐个分组进行。,加权的公平排队算法,上述算法的问题是，赋予所有的主机同等的优先权。在许多情况下，视频服务器期望获得比普通的文件服务器更多的带宽。因此，通过权值来解决。,综合服务,从1995年到1997年之间，IETF做了很大的努力来设计流式多媒体的体系结构。此工作的一般叫法为基于流的算法或者综合服务。这些算法同时针对单播和多播应用。在多播应用中，组中的成员是动态变化的，在这样的条件下，让发送方提前预留资源并不能很好地工作。,在综合服务体系结构中，主要的IETF协议是资源预留协议（RSVP）。利用RSVP可以完成资源预留工作，若要发送数据则还要使用其他协议。RSVP允许多个发送方给多个接收组传送数据，也允许接收方单独自由地切换信道，并且在优化使用带宽的同时消除拥塞的发生。在RSVP协议最简单的形式中，它通过生成树来实现多播路由。,举例：见图，P301,新书