计算机网络网络层路由算法课件

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