最短路径路由算法

计算机网络COMPUTERNETWORKS第7章网络层学习本章方法本章是本书最重要的一章,其中7.5节是重中之重.1)算法着重理解,也可自己发明新的算法或改进已有的算法,并能根据现有的算法编写程序2)IP地址,子网的划分,超网的构造,路由选择网络层是向传输层提供以下服务:路由选择拥塞控制网络互联第7章网络层ISO定义网络层为一个网络连接的两个传送实体间交换网络服务数据单元提供功能和规程的方法，它使传送实体独立于路由选择和交换的方式。网络层与数据链路层的区别：网络层是将源端发出的分组经各种途径送到目的端。而数据链路层仅将数据帧从传输介质的一端送到另一端。因此，网络层是处理端到端数据传输的最低层。网络层要解决的关键问题了解通信子网的拓扑结构，选择路由。7.2路由算法•路由算法–就是产生路由表的算法；–是网络层软件的一部分。–子网采用数据报方式，每个包都要做路由选择；–子网采用虚电路方式，只需在建立连接时做一次路由选择。•理想的路由算法–正确性（correctness）：算法必须正确；–简单性（simplicity）：算法开销小，效率高；–健壮性（robustness）：算法能适应网络负荷和拓朴的变化；–稳定性（stability）：算法必须收敛，不能振荡发散；振荡：算法得出的路由是在一些路由之间回荡。–公平性（fairness）：算法对所有用户必须是平等的；–最优性（optimality）：算法应提供最佳路径选择；最佳：链路长度、传输时延、数据速率、链路容量、链路差错率、链路丢失率等。路由算法分类–非自适应算法（静态路由算法）；简单、开销小，但不能适应网络状态变化；采用离线方式求出路由表。–自适应算法（动态路由算法）；复杂、开销大，但能适应网络状态变化；7.2.1最优化原则（optimalityprinciple）•从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树（sinktree）；•路由算法的目的是找出并使用汇集树。最短路径路由算法属于静态路由算法基本思想构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。测量路径长度的方法结点数量地理距离传输延迟距离、信道带宽等参数的加权函数Dijkstra算法采用标注的方式求出某一结点的汇集树和路由表。①每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注；②初始时，所有结点都为临时性标注，标注为无穷大；③将源结点标注为0，且为永久性标注，并令其为工作结点；④检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点；⑤在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点；重复第④、⑤步，直到所有结点成为工作结点；请指出AD最短路径Dijkstra算法程序7.2.3洪泛算法（也叫扩散算法）属于静态路由算法基本思想把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。主要问题产生大量重复包，导致出现拥塞现象。解决措施方法1：每个包头包含站点计数器（端到端的最大段数），每经过一站计数器减1，为0时则丢弃该包。方法2：在每个节点建立一个登记表，凡经过此节点的进行登记，若再次经过该节点，丢弃该包。选择性扩散算法（selectiveflooding）扩散法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。应用情况路由器和线路的资源过于浪费，实际很少直接采用；具有很强的健壮性，常用于军用网；作为衡量标准评价其它路由算法。7.2.4基于流量的路由算法属于静态路由算法基本思想既考虑拓扑结构，又兼顾网络负荷；前提：每对结点间平均数据流相对稳定和可预测；根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法;提前离线计算。需要预知的信息网络拓扑结构；通信量矩阵Fij，即线路ij之间的平均通信量。线路带宽矩阵Cij，即线路ij之间允许的最大通信量。路由算法（可能是临时的）。7.2.5距离矢量路由算法属于动态路由算法最初应用于ARPANET，后来应用于因特网的RIP协议（路由信息协议）。基本思想每个结点通过测取与相邻结点的距离，再依据与其相邻结点交换的距离信息，间接地求出路由表；各结点周期性地测取相邻结点的距离；向相邻结点发送它到每个目的结点的距离表，同时，它也接收每个邻居结点发来的距离表；结点中的老路由表在计算中不被使用。操作过程：每个路由器维护一张表，表中列出了到每个目的地址的最佳距离和线路，并通过与邻居结点交换信息来更新表。表(路由表)的构成：以子网中其它路由器为表的索引，到达目的结点的最佳输出线路，和到达目的结点所需时间或距离。路由器需要知晓自己到邻居结点的“距离”。所用的度量标准可以为站点、估计的时间延迟等。如果为站点，本路由器到每个邻居结点的距离都为1。如果是延迟，本路由器就发送一个要对方立即响应的ECHO分组，用来回时间除以2即得到延迟时间，每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表。邻居结点X发来的表中，X到路由器i的距离为Xi。本路由器到X的距离为m，则本路由器经过X到i的距离为Xi+m。根据不同邻居发来的信息，计算Xi+m，取最小值，更新本路由器的表。注意：在计算中不使用本路由器中的老路由表。路由器J计算到达路由器C的最新路由JAC=8+25=33msJIC=10+18=28msJHC=12+19=31msJKC=6+36=42ms其中JIC是最好的。因此在路由器J的新路由表中填上到C的延迟为28ms，经过路由器I。距离向量路由算法的缺陷缺陷——无穷计算问题对好消息反应迅速：在最长路径为N各结点的子网中，在N次交换之内，所有的路由器都会指导新增的线路和路由器。对坏消息反应迟钝：对于已经消失的结点，相互欺骗。图例如下。水平分裂算法基本思想工作过程与距离向量算法相同，区别在于到X的距离不向真正通向X的邻居结点报告。从而使得坏消息以每次一个结点的速度传播。举例：如右图。在路由信息的交换中，B知道可以直达A，并告诉C，通过B到C路径为1。C得到B发来的路由信息后，告诉D通过C到达A距离为2，告诉B通过C到达A为无穷。D得到C发来的路由信息后，告诉E通过D到达A距离为3，告诉C通过D到达A为无穷。当A下网后，•第一次交换：B发现到达A的直达路线没有了，而且C也向B说到达A为无穷，故B将其到达A的距离设置为无穷。•第二次交换：C得到B的通知，B到达A为无穷；同时D也告诉C，通过D到达A为无穷，故C将其到达A的距离设置为无穷。•以次类推，在第四次交换的时候，E也知道A不可达了。解决方案之一水平分裂ABCDE水平分裂不能解决所有的问题水平分裂虽然广泛使用，但有时候会失败。如右图。开始时，A和B到D的举例都为2，C到D的举例为1。假设CD线路断了，使用水平分裂，A和B都告诉C，它们不能到达D，同时C自己也发现直达D的线路断了，于是C很快认定D不可达了。但是，A认为B有一条通向D长度为2的路径，通过B经过3个结点可到达D。类似，B也这样认为。于是两个结点每交换一次信息，到达D的距离就增加1，直至加大无穷。7.2.6链路状态路由算法距离向量路由算法的主要问题由于延迟度量仅仅是队列长度，在选择路由时没有考虑线路带宽。即使使用了水平分裂，路由收敛速度依然慢。在1979年前，ARPANET上都采用距离向量路由算法，但是之后，即为链路状态路由算法所替代。链路状态路由算法的简单步骤发现邻居结点，并学习它们的网络地址。测量到每个邻居结点的延迟或开销。将所有学习到的内容封装成一个分组。将这个分组发送给所有其它路由器。计算到每个其它路由器的最短路径。步骤1：发现邻居结点发现邻居结点，并学习它们的网络地址。路由器启动后，通过发送HELLO分组，并得到邻居路由器的响应来发现邻居结点。路由器的名称必须是唯一的。当两个或多个路由器连在一个LAN时，引入人工结点。图例。步骤2/3：测量线路开销和封装分组测量到每个邻居结点的延迟或开销，一种直接的方法是：发送一个要对方立即响应的ECHO分组，来回时间除以2即为延迟时间。如果在测量延迟时间的时候，考虑负载，会是什么情况？将所有学习到的内容封装成一个分组，即在信息收集完毕后，构造一个包含所有数据的分组。该分组的结构为：发送方的标识符、序号、年龄、邻居结点列表（邻居结点标识符，线路开销值）。创建链路状态分组的时机：一是定期创建，一是在发生重大事件后创建。步骤4：发布链路状态分组链路状态分组的发布算法基本思想：洪泛链路状态分组。为控制洪泛，每个分组中增加一个序号域，每次发送新分组时加1。路由器记录信息对(源路由器，序号)，当一个链路状态分组到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃。基本算法所产生的问题序号循环使用会混淆。路由器崩溃后，所有的序号丢失，从0开始记，以后所有的新到分组都可能被当作重复分组而被拒绝。序号在发送出去后出现错误。步骤4：发布链路状态分组基本算法的改进方案为了避免序号重复，使用32位的序号。解决序号丢失和出错的方法是增加年龄(age)域，每秒钟年龄减1，至零则丢弃。链路状态分组到达后，延迟一段时间(被放置在一个保持区中)，并与其它已到达的来自同一路由器的链路状态分组比较序号，丢弃重复分组和超龄分组。为了防止链路出错，所有的链路状态分组都需要应答。步骤5：计算新路由在路由器积累了一整套网络的链路状态分组后，就可以通过计算得到整个网络的结构。可以利用Dijkstra算法计算得到每个其它路由器的最短路径。基于链路状态的路由协议OpenShortestPathFirst(OSPF)IntermediateSystem-IntermediateSystem(IS-IS)7.2.7分层路由网络规模增长带来的问题路由器中的路由表增大。路由器为选择路由而占用的内存、CPU时间和网络带宽增大。解决办法——分层路由对于大型网络分而治之，每个路由器只知道自己所在子网的路由信息，而不去了解其他子网的内部结构。根据需要，可以分成区域(regions)、聚类(clusters)、区(zones)和组(groups)…图例。分级路由带来的问题路由表中的路由不一定是最优路由。分级路由图例小结—路由算法最优化原则路由算法的目的是找出并使用汇集树。最短路径路由算法目的是构建两个路由器间的路由，算法是在子网拓扑图中找出最短路径。Dijkstra算法。洪泛算法把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。基于流量的路由算法根据网络带宽和平均流量，可得出平均延迟，因此路由问题归结为找产生网络最小延迟的路由算法。距离向量路由算法根据两个结点间的队列长度来完成路由选择，但是最大的问题是无穷计算，而且水平分裂也不能完全解决所有的问题。链路状态路由算法发现邻居结点测量线路开销将所有学习到的内容封装成一个分组发布链路状态信息计算新路由分级路由对于大型网络分而治之，每个路由器只知道自己所在子网的路由信息，而不去了解其他子网的内部结构。7.3拥塞控制算法拥塞（congestion）网络资源上有太多的分组时，导致性能会下降。Σ对资源的需求可用资源资源：链路容量、交换结点中的缓存和处理机等。拥塞产生的原因–结点缓存容量太小；多个输入对应一个输出；–结点处理机速度不高；–低带宽线路；针对某个因素改善拥塞若结点缓存容量太小，到达结点的分组无空间暂存;