计算机网络网络层路由算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,路由算法（,Routing Algorithm）,是网络层软件的一部分，负责所收到数据包发送到哪一条线路上。,路由选择算法应具有下列特性：正确性、简单性、鲁棒性、稳定性、公平性和最优性。,路由算法应该能够处理拓扑结构和流量方面的各种变化，而不能要求所有主机停止所有工作。,1,路由选择算法可以分为两大类：,非自适应,-不会根据当前测量或者估计的流量和拓扑结构，来调整它的路由决策。所用的路由选择是在预先离线情况下计算好的，并在网络启动时被下载到路由器中的。,自适应,-根据拓扑结构、通信量的变化来改变其路由选择2,5.2.1,优化原则,最优路径一般陈述,：如果路由器,J,在路由器,I,到,K,的最优路径上，那么,J,到,K,的最优路径也必须遵循同样的路径。,汇集树：,B,A,C,D,E,G,F,H,I,J,路由器,B,的汇集树,3,5.2.2 最短路径算法,基本想法,：构造一张网络图中每个节点代表一个路由器，每条边代表一条通信线路或链路，为了选择给定路由器之间的路由，只需找出他们的最短路径。,最短路径,：,度量方法：跳数，以千米为单位的距离。标准测试包的平均延迟。,Dijksstra,算法,4,5,5.2.3 泛洪算法,泛洪,：将每一个入境数据包发送到了除该数据包到达的那条线路外的每条出境线路。缺点,：产生大量重复数据包。,措施,：（,1,）设置跳计数器；,（,2,）跟踪数据包。,优点：,确保数据包被传送到每个网络中的节点；,泛洪途径的鲁棒性非常好；,即使大量路由器被炸成碎片路由器也能找到一条路径使得数据包到达目的地。,6,距离矢量路由算法（,Distance Vector Routing,）,工作原理:,每个路由器维护一张表，表中给出了到每个目的路由器的已知最短“距离”和相应输出线路,并通过与相邻路由器交换距离信息来更新表。,“距离”,:到目的路由器的跳数、估计的,时间延迟,、,路由排队的分组估计总数或类似的值。,假设使用延迟作为距离度量，并且路由器知道他到每个邻居的延迟。每隔,T,秒每个路由器向他的每个邻居发送一个表，该表记录了它到每个目标的延迟，同时它也从邻居那里收到一个类似的表。,7,交换距离信息更新路由表示例,8,无穷计算问题,第1次交换后,第3次交换后,A,B,C,D,E,1,2,3,4 初始时,3,2,3,4 第1次交换后,3,4,3,4 第2次交换后,5,4,5,4 第3次交换后,5,6,5,6 第4次交换后,7,6,7,6 第5次交换后,7,8,7,8 第6次交换后,（,b）,.,.,.,A,B,C,D,E,初始时,1,1,2,第2次交换后,1,2,3,1,2,3,4 第4次交换后,（,a）,问题的核心在于当,X,告诉,Y,自己有一条通往某个地方的路径的,Y,不知道自己是否在这条路径上。,9,链路状态路由算法,发现邻居，了解其网络地址,设置到每个邻居节点的距离或成本度量值。,构造一个包含所有刚刚获知的链路信息包。,将这个包发送给所有其他的路由器，并接受来自其他路由器的信息包。,计算每个到其他路由器的最短路径。,10,发现邻居,在每一条点到点的线路上发送一个特殊的,HELLO,数据包，线路另一端的路由器返回一个应答说明自己是谁。,两个或多个路由器通过一个广播链路连接的情况：,11,设置链路成本,一种与带宽成反比；,链路延迟是成本的组成部分。,方法：通过线路给另一边发送一个特殊的,ECHO,数据包，要求对方立即发回，通过测量往返时间再除以,2,发送路由器可以得到一个合理的延迟估算值。,构造链路状态包,内容：发送方的标示符，接着是一个序号和年龄，邻居列表。,创建时间：周期性，发生重要事情时。,12,链路状态包,一个网络示例,13,分发链路状态数据包,（,1,）,泛洪法,：为了控制泛洪规模，每个数据包包含一个序号，序号随着每个数据包发出逐一递增，路由器记录下它所看到的所有（源路由器，序号）对，当一个新的链路状态数据包到达时，路由器检查这个数据包是否已经出现在上述观察到的列表中，若是新的数据包，则转发，若重复或过时则丢弃。,（,2,）,改进方法,：当数据包被泛洪到其他路由器时并没有被立即排入队列等待，首先放到保留区。在它被转发出去前另一个来自同一源路由器的链路状态数据包也到来，就比较他们的序号来判定转发哪一个。,14,路由器,B,的状态包缓冲区,特殊情况,：如果一个重复数据包到来时，原来的数据包仍然在缓冲区。此时标志位的变化。,C,的副本从,F,到达，那么标志位变为,100011.,计算新路由,：利用,Dijikstra,算法。,链路状态路由算法优点：没有慢收敛问题。,15,5.2.6 层次路由,原理：路由器被划成了区域，每个路由器知道如何将数据包路由到自己所在区域内的目标地址，但是对于其他区域的内部结构毫不知情，当不同的网络相互连在一起，很自然地就会将每个网络当做一个独立的区域，一个网络中的路由器并不知道其他路由器的拓扑结构。,对于大型网络，两级层次结构可能不够，一般将区域组织成簇，将簇组织成区，将区组织成群。,16,1A,完整表,1A,层次表,区域,1,区域,5,区域,4,区域,3,区域,2,两级分层实例,17,优点,：随着区域数与每个区域中路由器数量之比值的增加，节省下来的空间也随之增加。,缺点,：增加了路径长度。,经科学发现,，对于一个包含,N,个路由器的网络，最优的层数是,lnN,，每个路由器所需的路由器表项是,elnN,个。当然由分层引起的路径长度的实际增长非常小。,18,广播路由,同时给全部的目标地址发送一个数据包称为广播,扩散法。,多目标路由：每个数据包含一组目标地址，经过路由器，针对目标选路，目标分散,逆向路径转发（reverse path forwarding),沿汇集树（sink tree）生成树（spanning tree）扩散,19,路由器收到广播分组，看到来那条路径是否是用来给广播源发送分组的那条线路，是，转发到其他所有线路上，否则，丢弃。,逆向路径转发的优点：有效而且易于实现。,20,组播路由,定义：给明确定义的组发送消息称为组播。,如果组的分布是密集的我们可以通过修剪广播生成树把不通往组成员的链路从树种减掉。修剪结果得到的是一颗有效的组播生成树。,21,组播路由,(,a),网络实例,.,(b),最左边路由器的一颗生成树,.,(c),组,1,的一颗组播树,(d),组,2,的一颗组播树,22,修剪生成树的方法,链路状态路由算法网络中，每个路由器知道完整的拓扑结构，哪些主机属于哪个组。修剪从每条路径末端开始，逐步向根，将不属于相应组的路由器去掉。,距离矢量路由协议,距离矢量路由算法中，逆向路径转发。如果一个路由器没有任何主机对某个组感兴趣，并且没有连接到需要接收该组播消息的其它路由器，则回送,PRUNE,信息告诉发送该消息的邻居不要再给自己发送该组的任何消息；一个路由器的主机没有一个属于该组成员，且在所有线路上收到,PRUNE,信息，则回送,PRUNE,信息。通过这种方式最终修剪一棵生成树。,缺点：生成树的存储 需要大量的空间。,23,5.2.9选播路由,选播：数据包被传递给最近的一个组成员。,距离矢量和链路状态路由算法都可以用来生成新的选播路由。假设我们需要选播数据包到组,1,的成员，该组成员都将被赋予一个组地址“,1”,，而不是一个独立的地址，距离矢量路由像往常一样分发数据包，并且节点只选择到目的地,1,的最短路径。,24,组,1,的选播路由,路由协议看到的拓扑结构,1,1,1,1,1,25,5.2.10 移动主机路由,Internet和蜂窝网络的移动路由基本想法是移动主机把当前自己在那里告诉家乡位置的一台主机，这台主机称为家乡代理。它将以移动主机的名义采取行动，一旦知道移动主机的位置，就可以转发数据包给移动主机。,26,首先,;,移动主机获得一个本地网络地址，这个地址也称为转交地址，来告诉家乡代理它在哪，它给家乡代理发送一个带有转交地址的注册消息。,接下来：发送者使用其永久地址发送一个数据包给移动主机，这个数据包被网络路由到其家乡地址，因为移动主机已离家，家乡地址用一个新的头包裹或封装该数据包，并把捆绑后的结果转发给转交地址，这种机制称为隧道。,封装后的数据包到达转交地址，移动主机解开它并提取出来自发送者的数据包，然后移动主机直接给发送者一个应答信号。发送者可以借助当前的转交地址把随后的数据包直接发送给移动主机。,27,移动用户的路由转发过程,发送者,2,往家乡地址发送数据包,1,注册转交地址,3,隧道到转交地址,家乡代理,移动主机,4,应答,发送者,5,隧道到转交地址,28,自组织网络的路由,移动自组网MANET(Mobile Ad hoc NETworks),节点既是主机又是路由器,拓扑结构时刻在变化,很多路由算法。按需矢量路由算法,是相对的矢量路由算法；考虑到节点带宽有限和电池寿命短，适合在移动环境中工作。,29,AODV路由算法,路径发现,(,a),Range of As broadcast.,(b),After B and D have received As broadcast.,(c),After C,F,and G have received As broadcast.,(d),After E,H,and I have received As broadcast.,Shaded nodes are new recipients.Arrows show possible reverse routes.,30,路径维护,每个节点周期性的广播一个,HELLO,消息并期望它的邻居做出回应，如果回应没有到来说明消息广播者已经知道它的邻居已失效或离开接收范围，因而不再跟自己有连接。这些信息用来清除掉那些不再有效的消息。,31,在最近的T时间内曾经给它发送过到达该目标的邻居该目标的活动邻居,当节点N的任何一个邻居变得不可到达时,检查路由表,看那些目标路径用到了这些邻居,删除这些路径,同时对应于每条这样的路径,通知对应的活动邻居,告诉经过N的路径不再有效了.如此递归下去知道所有依赖该节点的路由从全部的路由表中删除。,32,