重庆大学：《网络体系结构与协议》研究生课程教学资源（教材）第4章 互联网路由结构与协议

目录 第4章互联网路由结构与协议 4.1互联网路由结构与路由算法 41.1互联网结构特点 4.1.2互联网的路由结构 41.3路由算法分类 42互联网域内路由协议 42.1路由信息协议 422开放最短路径优先协议 43互联网域间路由协议 43.1自治系统级网络拓扑 4.32自治系统间连接关系 4.3.3边界网关协议 4.34BGP中的策略路由 44组播及组播地址 44.1计算机网络中的通信方式 44.2IP组播技术优缺点 44.3IPV4组播地址 444互联网组管理协议IGMP 45组播转发 4.5.1源树 4.52共享树 453源树和共享树的比较 4.54组播转发原理 4.6组播路由协议 46.1域内组播路由协议 462域间组播路由协议 463分析与比较

目    录 第 4 章 互联网路由结构与协议 4.1 互联网路由结构与路由算法 4.1.1 互联网结构特点 4.1.2 互联网的路由结构 4.1.3 路由算法分类 4.2 互联网域内路由协议 4.2.1 路由信息协议 4.2.2 开放最短路径优先协议 4.3 互联网域间路由协议 4.3.1 自治系统级网络拓扑 4.3.2 自治系统间连接关系 4.3.3 边界网关协议 4.3.4 BGP 中的策略路由 4.4 组播及组播地址 4.4.1 计算机网络中的通信方式 4.4.2 IP 组播技术优缺点 4.4.3 IPv4 组播地址 4.4.4 互联网组管理协议 IGMP 4.5 组播转发 4.5.1 源树 4.5.2 共享树 4.5.3 源树和共享树的比较 4.5.4 组播转发原理 4.6 组播路由协议 4.6.1 域内组播路由协议 4.6.2 域间组播路由协议 4.6.3 分析与比较

第4章互联网路由结构与协议 4.1互联网路由结构与路由算法 4.1.1互联网结构特点 从横向来看,包括计算机网络在内的任何通信网都由终端节点和网络节点构成,其 中终端节点是通信的主体(计算机网络中称为主机),网络节点是进行通信的接入和交 换设备,也可称为网络接口信息处理机。由于互联网这样一个广域的计算机网络自始至 终都具有这样一些特点:由国际范围内的组织松散的、自治的计算机网络构成,这些自 治的网络由一些智能的网络节点一路由器连接起来,用户数据封装在IP分组内,由 这些路由器一跳一跳地进行传递,直到目的主机。因此,互联网是一个基于路由器的通 信网络,所有终端节点(主机)都必须通过网络节点(路由器)才能与其它终端节点进 行通信。互联网的网络接口信息处理机就是路由器。图41说明了互联网的这一横向结 构特点(其中H表示主机,R表示路由器)。 图41互联网的横向结构特点 从纵向来看,即从OSI参考模型协议层次的观点来看,互联网为了屏蔽网络层以 下各种不同具体网络实现的差异,各主机之间从网络层及以上都遵守TCPP协议簇, 以实现网络层以上的互连。所有IP层以上协议都直接或间接地建立在IP这种不可靠的 无连接的数据报协议之上,IP分组是整个互联网数据传输的基本单元。因而,对于路 由器来说,最重要的便是实现IP协议,能够根据收到的IP分组的头部信息进行正确地 处理和转发。图42说明了互联网的纵向结构及路由器所处的位置

第 4 章 互联网路由结构与协议 4.1 互联网路由结构与路由算法 4.1.1 互联网结构特点 从横向来看，包括计算机网络在内的任何通信网都由终端节点和网络节点构成，其 中终端节点是通信的主体（计算机网络中称为主机），网络节点是进行通信的接入和交 换设备，也可称为网络接口信息处理机。由于互联网这样一个广域的计算机网络自始至 终都具有这样一些特点：由国际范围内的组织松散的、自治的计算机网络构成，这些自 治的网络由一些智能的网络节点——路由器连接起来，用户数据封装在 IP 分组内，由 这些路由器一跳一跳地进行传递，直到目的主机。因此，互联网是一个基于路由器的通 信网络，所有终端节点（主机）都必须通过网络节点（路由器）才能与其它终端节点进 行通信。互联网的网络接口信息处理机就是路由器。图 4.1 说明了互联网的这一横向结 构特点（其中 H 表示主机，R 表示路由器）。 R R R R R R R R H H H H H H H H H 图 4.1 互联网的横向结构特点 从纵向来看，即从 OSI 参考模型协议层次的观点来看，互联网为了屏蔽网络层以 下各种不同具体网络实现的差异，各主机之间从网络层及以上都遵守 TCP/IP 协议簇， 以实现网络层以上的互连。所有 IP 层以上协议都直接或间接地建立在 IP 这种不可靠的 无连接的数据报协议之上，IP 分组是整个互联网数据传输的基本单元。因而，对于路 由器来说，最重要的便是实现 IP 协议，能够根据收到的 IP 分组的头部信息进行正确地 处理和转发。图 4.2 说明了互联网的纵向结构及路由器所处的位置

应用层 主机A 路由器 主机B 示层 应用层 应用层 会话层 TCP UDP TCP UDP 传输层 IP分组 IP 网络层 数据链 数据链路层 数据链路层 数据链路层 物理接口 物理接口 物理接口 物理层 物理网络 物理网络 图42互联网与OSI纵向结构的对应关系 4.12互联网的路由结构 路由器系统组成了互联网的基本结构,运行在路由器上的单播路由协议则是互联网 正常运行的基本保证。互联网的路由选择模型以自治系统为基础,自治系统是指具有统 管理策略并且具有官方自治系统编号的网络,在自治系统内运行路由选择信息协议、 开放最短路径优先协议等内部网关协议,自治系统之间运行边界网关协议交换路由信息, 路由协议交换的路由信息最终会形成路由表保持在路由器中,路由器就是依据路由表来 决定每个到达的分组该往娜里转发。 从上述结构看出,是路由器把主机从繁重的路由负担中解放出来,决定IP分组转 发方向的关键因素是路由表。路由表的查找、建立、维护和更新工作是由路由器完成的 这一部分功能在路由器中占有很重要的地位,它直接涉及IP分组路由的正确与否以及 效率高低,以至整个互联网的稳定性。由于历史原因,本章许多地方用网关来指代路由 ,实际上两者具有相同的意义。 1、路由表的结构 IP地址编码具有其特殊性:可以用主机地址的高位部分来代表其所属网络的地址 IP分组在传送过程中,只有当它到达与其目的主机处于同一网络、同时也是转发途径中 的最后一个路由器时,其中的主机IP地址才对这个路由器有意义,之前的所有路由器 都只关心IP地址中的网络地址(高位部分)。因为具有相同网络地址的主机必定处于同 网络中,所以只要根据主机IP地址中的网络部分查找路由表即可得到下一个路由器

图 4.2 互联网与 OSI 纵向结构的对应关系 4.1.2 互联网的路由结构 路由器系统组成了互联网的基本结构，运行在路由器上的单播路由协议则是互联网 正常运行的基本保证。互联网的路由选择模型以自治系统为基础，自治系统是指具有统 一管理策略并且具有官方自治系统编号的网络，在自治系统内运行路由选择信息协议、 开放最短路径优先协议等内部网关协议，自治系统之间运行边界网关协议交换路由信息， 路由协议交换的路由信息最终会形成路由表保持在路由器中，路由器就是依据路由表来 决定每个到达的分组该往哪里转发。 从上述结构看出，是路由器把主机从繁重的路由负担中解放出来，决定 IP 分组转 发方向的关键因素是路由表。路由表的查找、建立、维护和更新工作是由路由器完成的。 这一部分功能在路由器中占有很重要的地位，它直接涉及 IP 分组路由的正确与否以及 效率高低，以至整个互联网的稳定性。由于历史原因，本章许多地方用网关来指代路由 器，实际上两者具有相同的意义。 1、路由表的结构 IP 地址编码具有其特殊性：可以用主机地址的高位部分来代表其所属网络的地址。 IP 分组在传送过程中，只有当它到达与其目的主机处于同一网络、同时也是转发途径中 的最后一个路由器时，其中的主机 IP 地址才对这个路由器有意义，之前的所有路由器 都只关心 IP 地址中的网络地址（高位部分）。因为具有相同网络地址的主机必定处于同 一网络中，所以只要根据主机 IP 地址中的网络部分查找路由表即可得到下一个路由器

的地址,这样一跳一跳地查表和转发,直到达到与目的主机直接相连于同一网络的路由 器,这时才利用ARP等地址解析协议把目的主机地址转换为物理地址,把IP分组发送 给目的主机。因此,路由表的表项只需保留目的主机的网络地址,而不是主机地址,这 样可使路由表的规模较小,同时也使查找速度加快。图4.3是说明上述情况的例子, 通向上游 路由器的 路径 ABC Net Nxt Hop default RI Direct RS defauLt[ R2 Net Nxt Hop 转发:次策下灬跳 路由;找钊端到端的路径 ABCDE Direct default 图43路由和转发实例 2、自治系统的概念 路由器在启动时,由外存读入或执行特定命令初始化其路由表,这是由网络管理员 事先配置好的。随着网络运行状态的变化,如链路、路由器和主机的增加和减少,故障 的发生和排除等,路由器必须能及时更新其路由表,以正确反映当前的网络状态,从而 尽可能准确快速地转发IP分组。因此路由器之间要根据事先商定的路由协议定期交换 和学习路由信息。那么,是否路由表中对于每个可能的目的网络都有一个表项,整个互 联网采用同一种全局路由算法呢?答案是否定的。首先,即使是以网络为索引,这也将 是一张非常庞大的表;其次,因为互联网分布范围太广,包括主机太多,动态变化要及 时反映到全部路由表中是不可能的,一旦发生变化,各路由器中的路由表就会在一段时 内丧失一致性;另外,这种全局的路由更新信息会占用大量的带宽,影响正常的数据 传输。因此,互联网采用的方法是把整个网络划分为一些相对自治的局部系统,采用 种或者多种分布式路由算法,路由表中也只保留局部的路由信息 互联网是在 ARPANET的基础上发展起来的。在互联网发展的初期, ARPANET广 域网已开始投入使用,设计者们自然而然地将 ARPANET作为主干,各本地局域网通过 网关(即路由器)连入 ARPANET,从而构成互联网。这些连接本地网络与 ARPANET

的地址，这样一跳一跳地查表和转发，直到达到与目的主机直接相连于同一网络的路由 器，这时才利用 ARP 等地址解析协议把目的主机地址转换为物理地址，把 IP 分组发送 给目的主机。因此，路由表的表项只需保留目的主机的网络地址，而不是主机地址，这 样可使路由表的规模较小，同时也使查找速度加快。图 4.3 是说明上述情况的例子。 图 4.3 路由和转发实例 2、自治系统的概念 路由器在启动时，由外存读入或执行特定命令初始化其路由表，这是由网络管理员 事先配置好的。随着网络运行状态的变化，如链路、路由器和主机的增加和减少，故障 的发生和排除等，路由器必须能及时更新其路由表，以正确反映当前的网络状态，从而 尽可能准确快速地转发 IP 分组。因此路由器之间要根据事先商定的路由协议定期交换 和学习路由信息。那么，是否路由表中对于每个可能的目的网络都有一个表项，整个互 联网采用同一种全局路由算法呢？答案是否定的。首先，即使是以网络为索引，这也将 是一张非常庞大的表；其次，因为互联网分布范围太广，包括主机太多，动态变化要及 时反映到全部路由表中是不可能的，一旦发生变化，各路由器中的路由表就会在一段时 间内丧失一致性；另外，这种全局的路由更新信息会占用大量的带宽，影响正常的数据 传输。因此，互联网采用的方法是把整个网络划分为一些相对自治的局部系统，采用一 种或者多种分布式路由算法，路由表中也只保留局部的路由信息。 互联网是在 ARPANET 的基础上发展起来的。在互联网发展的初期，ARPANET 广 域网已开始投入使用，设计者们自然而然地将 ARPANET 作为主干，各本地局域网通过 网关（即路由器）连入 ARPANET，从而构成互联网。这些连接本地网络与 ARPANET

主干的网关就称为核心网关。核心网关之间要不断交换各自的路由信息,以保证整个互 联网路由的一致性。图44是最初互联网的核心结构。 ARPANET主干网 入人广 核心路由器(网关) LANI 把LAN连接到 LAND ARPANET上 的路由器集 LAN上主机把所有非本地流量交换送给最近的核心路由器 图44互联网的核心结构 随着核心网关的增多,主干网上路由更新信息的开销增大,使得扩展很难。因而要 在核心网关下引入自治系统( Autonomous System,AS)的概念,其中可以包含多个网 络和网关(称为非核心网关),通过唯一核心网关与主干网相连。核心网关由INOC(互 联网网络操作中心)统一管理,可以保证极高的可靠性,并且互相交换路由信息,以保 证整个互联网路由的一致性;非核心网关在本地自行管理,一方面赋予本地网关极大的 灵活性,另一方面大大减轻INOC的负担。当然,自治系统要通过某一授权的非核心网 关向核心系统负责,其中包括向核心网关通告本地路由信息,使核心网关能对本地主机 进行路由;同时核心网关也要通过这个网关报告主干网的路由信息。从上面自治系统的 定义可以看出,各核心网关也构成了一个自治系统,只是由于其特殊性,通常把它独立 出来。 从上面的讨论可以得出互联网的路由模式:在自治系统内部,各外部网关共同完成 本地路由;当分组目的地址位于其它自治系统时,本地网络通过默认路径将数据分组发 往与之相连的核心网关,进入核心主干网,再通过核心网关的协同作用,将数据分组通 过与分组目的地址所在自治系统直接相连的核心网关进入自治系统内,通过自治系统内 部的路由到达目的主机。 各个网关之间通过路由协议来交换路由信息时,会遇到三种情况:核心网关之间、 自治系统内部之间,以及自治系统与核心网关之间。因而路由协议通常可分为三类:第

主干的网关就称为核心网关。核心网关之间要不断交换各自的路由信息，以保证整个互 联网路由的一致性。图 4.4 是最初互联网的核心结构。 LAN 上主机把所有非本地流量交换送给最近的核心路由器 图 4.4 互联网的核心结构 随着核心网关的增多，主干网上路由更新信息的开销增大，使得扩展很难。因而要 在核心网关下引入自治系统（Autonomous System，AS）的概念，其中可以包含多个网 络和网关（称为非核心网关），通过唯一核心网关与主干网相连。核心网关由 INOC（互 联网网络操作中心）统一管理，可以保证极高的可靠性，并且互相交换路由信息，以保 证整个互联网路由的一致性；非核心网关在本地自行管理，一方面赋予本地网关极大的 灵活性，另一方面大大减轻 INOC 的负担。当然，自治系统要通过某一授权的非核心网 关向核心系统负责，其中包括向核心网关通告本地路由信息，使核心网关能对本地主机 进行路由；同时核心网关也要通过这个网关报告主干网的路由信息。从上面自治系统的 定义可以看出，各核心网关也构成了一个自治系统，只是由于其特殊性，通常把它独立 出来。 从上面的讨论可以得出互联网的路由模式：在自治系统内部，各外部网关共同完成 本地路由；当分组目的地址位于其它自治系统时，本地网络通过默认路径将数据分组发 往与之相连的核心网关，进入核心主干网，再通过核心网关的协同作用，将数据分组通 过与分组目的地址所在自治系统直接相连的核心网关进入自治系统内，通过自治系统内 部的路由到达目的主机。 各个网关之间通过路由协议来交换路由信息时，会遇到三种情况：核心网关之间、 自治系统内部之间，以及自治系统与核心网关之间。因而路由协议通常可分为三类：第

类是核心网关协议GGP( Gateway-Gateway Protocol,GGP),这是互联网最早采用的 种路由协议。由于自治系统之间是互相独立的,所以它们可以在内部采用自己的路由 协议而不必互相统一,这些协议统称为内部网关协议( Interior Gateway Protocol,IGP), 包括RIP、IGRP、 HELLO和OSPF等;自治系统与核心网关之间采用外部网关协议 ( Exterior Gateway Protocol,EGP),包括EGP和BGP等。注意,由于互联网是以核心 系统为根的树状体系结构,各自治系统处在不同的分支上,因此对核心的依赖很强。 旦核心出现故障,整个互联网都将受到影响。为了减少这种依赖关系,使互联网的管理 和控制尽可能分散化,进而提高可靠性,需要在各自治系统即各分支之间建立信任关系 信任度高的自治系统之间可以直接交换路由信息,而不需要通过核心系统。它们之间的 协议也属于外部网关协议,并且这个协议只需双方协商认可即可。图45所示的是当前 互联网的树形路由体系结构 核心系统 核心网关 自治系统 自治系统 信任 问非栋心网类 局域网 局域网 图45互联网的树型结构图 图46显示的是互联网自治系统内部路由和自治系统间路由运行情况。随着互联网 的发展,自治系统之间已形成了复杂的网状连接关系,对核心系统依赖越来越小

一类是核心网关协议 GGP（Gateway-Gateway Protocol，GGP），这是互联网最早采用的 一种路由协议。由于自治系统之间是互相独立的，所以它们可以在内部采用自己的路由 协议而不必互相统一，这些协议统称为内部网关协议（Interior Gateway Protocol，IGP）， 包括 RIP、IGRP、HELLO 和 OSPF 等；自治系统与核心网关之间采用外部网关协议 （Exterior Gateway Protocol，EGP），包括 EGP 和 BGP 等。注意，由于互联网是以核心 系统为根的树状体系结构，各自治系统处在不同的分支上，因此对核心的依赖很强。一 旦核心出现故障，整个互联网都将受到影响。为了减少这种依赖关系，使互联网的管理 和控制尽可能分散化，进而提高可靠性，需要在各自治系统即各分支之间建立信任关系， 信任度高的自治系统之间可以直接交换路由信息，而不需要通过核心系统。它们之间的 协议也属于外部网关协议，并且这个协议只需双方协商认可即可。图 4.5 所示的是当前 互联网的树形路由体系结构。 图 4.5 互联网的树型结构图 图 4.6 显示的是互联网自治系统内部路由和自治系统间路由运行情况。随着互联网 的发展，自治系统之间已形成了复杂的网状连接关系，对核心系统依赖越来越小

网关 处理经过自己的 处理经过自己的来 1网-自治系统内 部的路由 树络层 网关Ac处的自治系统 内部和白治系统间 数掘链路层 的路由 ROUTING→ TABLL DL Ab PHY PHY PHY 主机 在ASB内部的目治 杀统内部路由 在ASA内部的治在ASA和B间的自治 系统间路由 系统内部路出 图46自治系统内部和自治系统间路由协议的运行情况 4.1.3路由算法分类 根据当前网络状况〔链路流量和拓扑结构)的变化是否动态调整,路由选择算法分 为非自适应(静态)算法和自适应(动态)算法两大类。非自适应算法不能根据网络当 前实际传输量和拓扑变化来做路由选择,而且按原先设计好的路径传送,路径的设定和 修改是静态的。非自适应路由算法包括扩散式、随机式和固定式等。自适应算法是根据 当前网络流量和拓扑而动态进行的,能较好地适应网络中通信量和拓扑的变化。自适应 算法包含集中式、孤立式、分布式、混合式和分层式等。如图47所示

图 4.6 自治系统内部和自治系统间路由协议的运行情况 4.1.3 路由算法分类 根据当前网络状况（链路流量和拓扑结构）的变化是否动态调整，路由选择算法分 为非自适应（静态）算法和自适应（动态）算法两大类。非自适应算法不能根据网络当 前实际传输量和拓扑变化来做路由选择，而且按原先设计好的路径传送，路径的设定和 修改是静态的。非自适应路由算法包括扩散式、随机式和固定式等。自适应算法是根据 当前网络流量和拓扑而动态进行的，能较好地适应网络中通信量和拓扑的变化。自适应 算法包含集中式、孤立式、分布式、混合式和分层式等。如图 4.7 所示

路由算法 非自适应算法 自适应算法 扩随固 集孤分混分 散机定 中立布合层 式式式 式式式 图47路由算法分类 从宏观上看,互联网采用的是一种分层、分布式的路由算法;从微观上看,在局部 范围内可能采用各种不同的路由算法。目前常用的自适应的分布式路由算法有距离向量 法、链路状态算法两种。 1、距离向量法 距离向量法( Vector- Distance)又称为Ford- Fulkerson、 Bellman-Ford或 Bellman算 法。这种算法的思想比较简单,每台路由器周期性地与相邻路由器交换路由表中的信息。 这种信息是由若干(V,D)序偶组成的序偶表。在(V,D)序偶中,V代表向量,指 出该路由器可以到达的目标(网络或主机),D代表去往目标Ⅴ的距离。D按照路径上 的hop个数来计数。其它路由器收到(V,D)报文后,根据最短路径原则对各自的路 由表进行刷新 距离向量算法的优点在于易于实现,但它不适应路径的剧烈变动或大型的网络环境, 因为路由器的路径变化像波动一样从相邻路由器传播出去,其过程是非常缓慢的,网络 规模较大时尤其明显。因此在VD刷新过程中可能会出现路由不一致问题。VD算法的 另一个缺点是它需要大量的信息交换,VD报文中每一个目标网络都占用一个条目,则 报文大小相当于一个路由表,而许多表项都是与路由刷新无关的,而且每个路由器都参 与了信息交换,造成交换的信息量比较大。 2、链路状态算法 链路状态(Link- State,L-S)算法又称为最短路径优先( Shortest Path First,SPF) 算法。按照SPF的要求,路由器中路由表依赖于一张能表示整个网络拓扑结构的无向图 Gv,E)。在G中,节点V表示路由器,边E表示连接路由器的链路。可以把G称为LS 图。在信息一致的情况下,所有路由器的LS图都应该是相同的。各路由器的路由表通

图 4.7 路由算法分类 从宏观上看，互联网采用的是一种分层、分布式的路由算法；从微观上看，在局部 范围内可能采用各种不同的路由算法。目前常用的自适应的分布式路由算法有距离向量 法、链路状态算法两种。 1、距离向量法 距离向量法（Vector-Distance）又称为 Ford-Fulkerson、Bellman-Ford 或 Bellman 算 法。这种算法的思想比较简单，每台路由器周期性地与相邻路由器交换路由表中的信息。 这种信息是由若干（V，D）序偶组成的序偶表。在（V，D）序偶中，V 代表向量，指 出该路由器可以到达的目标（网络或主机），D 代表去往目标 V 的距离。D 按照路径上 的 hop 个数来计数。其它路由器收到（V，D）报文后，根据最短路径原则对各自的路 由表进行刷新。 距离向量算法的优点在于易于实现，但它不适应路径的剧烈变动或大型的网络环境， 因为路由器的路径变化像波动一样从相邻路由器传播出去，其过程是非常缓慢的，网络 规模较大时尤其明显。因此在 V-D 刷新过程中可能会出现路由不一致问题。V-D 算法的 另一个缺点是它需要大量的信息交换，V-D 报文中每一个目标网络都占用一个条目，则 报文大小相当于一个路由表，而许多表项都是与路由刷新无关的，而且每个路由器都参 与了信息交换，造成交换的信息量比较大。 2、链路状态算法 链路状态（Link-State，L-S）算法又称为最短路径优先（Shortest Path First，SPF） 算法。按照 SPF 的要求，路由器中路由表依赖于一张能表示整个网络拓扑结构的无向图 G  V，E 。在G中，节点V 表示路由器，边 E 表示连接路由器的链路。可以把G称为 L-S 图。在信息一致的情况下，所有路由器的 L-S 图都应该是相同的。各路由器的路由表通

过LS图计算。LS算法包含以下三个步骤。 ①各路由器主动测试所有与之相邻的路由器的状态,周期性地向相邻路由器发出 简短的查询报文,询问相邻路由器当前是否能够访问,假如对方作出反应,则说明链接 状态为UP,否则为DOwN。 ②各路由器周期性地向所有参与SPF的路由广播其LS信息,而不像VD算法那 样只向相邻路由器发送信息。 ③路由器收到LS报文后,利用它刷新网络拓扑图,将相应的连接状态改为UP 或DOWN。假如LS发生了变化,路由器立即利用 Dijkstra算法,这个算法可以求出 加权无向图中从某给定节点到目的节点的最小耗费路由或最佳路由。 Dijkstra算法是典型的最短路径算法,用于计算一个节点到其它所有节点的最短路 径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra算法能 得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 Dijkstra算法是已知整个网络拓扑和各链路的长度,寻找从源节点到网络中其它各 节点最短路径的算法。 Dijkstra算法如下。 方法:设某一节点为源节点,然后逐步寻找,每次找一个节点到源节节点的最短路 径,直至将所有的节点都找到为止。 步骤:令N表示所有网络节点的集合,M表示已由算法归并的节点的集合,C(n)为 源节点到节点n的距离,它是沿某一通路的所有链路的长度之和。len(,j为节点i至 之间的距离。 ①初始化 设节点1为源节点,先令M={}。对所有不在M中的节点n,写出 cl=lan)节点n与节点1直接相连 节点n与节点1不直接相连 ②寻找一个不在M中的节点w,其C(n)值为最小。把w加入到M中。然后对所 有不在M中的节点n,用[(n)C(w)+len(w,n中较小的值去更新原有的C(n)值,即 C(n):=Minc(n), c(w)+len(w, n)] ③重复步骤②,直到所有的网络节点都在M中为止。 例41某网络如图48所示,链路旁边注明的数字代表链路的长度。试利用 Dijkstra 算法求出从节点1到所有其它节点的最短路由

过 L-S 图计算。L-S 算法包含以下三个步骤。 ① 各路由器主动测试所有与之相邻的路由器的状态，周期性地向相邻路由器发出 简短的查询报文，询问相邻路由器当前是否能够访问，假如对方作出反应，则说明链接 状态为 UP，否则为 DOWN。 ② 各路由器周期性地向所有参与 SPF 的路由广播其 L-S 信息，而不像 V-D 算法那 样只向相邻路由器发送信息。 ③ 路由器收到 L-S 报文后，利用它刷新网络拓扑图，将相应的连接状态改为 UP 或 DOWN。假如 L-S 发生了变化，路由器立即利用 Dijkstra 算法，这个算法可以求出 加权无向图中从某给定节点到目的节点的最小耗费路由或最佳路由。 Dijkstra 算法是典型的最短路径算法，用于计算一个节点到其它所有节点的最短路 径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法能 得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra 算法是已知整个网络拓扑和各链路的长度，寻找从源节点到网络中其它各 节点最短路径的算法。Dijkstra 算法如下。 方法：设某一节点为源节点，然后逐步寻找，每次找一个节点到源节节点的最短路 径，直至将所有的节点都找到为止。 步骤：令 N 表示所有网络节点的集合，M 表示已由算法归并的节点的集合，Cn为 源节点到节点 n 的距离，它是沿某一通路的所有链路的长度之和。len  i, j 为节点 i 至 j 之间的距离。 ① 初始化 设节点 1 为源节点，先令M  1。对所有不在 M 中的节点 n，写出          节点n与节点1不直接相连 len 1,n 节点n与节点1直接相连 C n ② 寻找一个不在 M 中的节点 w，其Cn值为最小。把 w 加入到 M 中。然后对所 有不在 M 中的节点 n，用  C   n ,C w  lenw,n 中较小的值去更新原有的C  n 值，即， C  n ：= Min  C  n ,Cw   len w,n 。 ③ 重复步骤②，直到所有的网络节点都在 M 中为止。 例 4.1 某网络如图 4.8 所示，链路旁边注明的数字代表链路的长度。试利用 Dijkstra 算法求出从节点 1 到所有其它节点的最短路由

图48用 Dijkstra算法求最短路径的网络举例 解:表41是对题图48所给网络按照 Dijkstra算法进行求解的详细步骤。 表41计算图48网络的最短路径 「步骤 C(2 C (4) C(5) C(6) 初始化 1,4} 222 5433 4 2345 1,2,45} (2) 2 (3) 4 1,2,3,4,56} (4) 初始化:因为选择了节点1为源节点,因此一开始在集合M中只有节点1。节点 1只与节点2、3和4直接相连,因此在初始化时,在C(2),C(3)和C(4)下面就填入节 点1到这些节点相应的距离,在C5)和C(6)下面填入∞。 步骤1:在节点1以外的节点中,找出一个距节点1最近的节点w,这应当是w=4 因为在C(2),C(3)和C(4)中,C(4)=1,它的权值最小。于是将节点4加入到节点集合 M中。这时,在步骤1这一行和C(4)这一列相交处填写(1),数字1表示节点4到节点 1的距离,数字1的括号表示节点4在这个步骤加入到节点集合M中了。 接着就要对所有不在集合M中的节点(即节点2、3、5和6)逐个执行: C(n):=Min(C(n), c(w)+ len(w, n) 对于节点2,原来的C(2)=2。现在C(w)+en(w,n)=C(4)+len(4,2)=1+2=3>C(2) 因此节点2到节点1距离不变,仍为2。 对于节点3,原来的C(3)=5。现在C(w)+en(w,n)=C(4)+len(4,3)=1+3=4<C(3) 因此节点3到节点1的距离要更新,从5减小到4。 对于节点5,原来的C(5)=∞。现在Cw)+len(w,n=C(4)+en(4,5)=1+1=2<C(5)

图 4.8 用 Dijkstra 算法求最短路径的网络举例 解：表 4.1 是对题图 4.8 所给网络按照 Dijkstra 算法进行求解的详细步骤。 表 4.1 计算图 4.8 网络的最短路径 步骤 M C2 C3 C4 C5 C6 初始化 {1} 2 5 1   1 {1,4} 2 4 （1） 2  2 {1,4,5} 2 3 1 （2） 4 3 {1,2,4,5} （2） 3 1 2 4 4 {1,2,3,4,5} 2 （3） 1 2 4 5 {1,2,3,4,5,6} 2 3 1 2 （4） 初始化：因为选择了节点 1 为源节点，因此一开始在集合 M 中只有节点 1。节点 1 只与节点 2、3 和 4 直接相连，因此在初始化时，在C2，C3和C  4 下面就填入节 点 1 到这些节点相应的距离，在C5和C6下面填入。 步骤 1：在节点 1 以外的节点中，找出一个距节点 1 最近的节点 w，这应当是 w=4， 因为在C  2 ，C  3 和C  4 中，C  4  1，它的权值最小。于是将节点 4 加入到节点集合 M 中。这时，在步骤 1 这一行和C4这一列相交处填写（1），数字 1 表示节点 4 到节点 1 的距离，数字 1 的括号表示节点 4 在这个步骤加入到节点集合 M 中了。 接着就要对所有不在集合 M 中的节点（即节点 2、3、5 和 6）逐个执行： C  n ：= Min  C     n ,C w  len w,n 。 对于节点 2，原来的C  2  2 。现在 C（w）+len(w，n)=C（4）+len（4，2）=1+2=3>C(2)。 因此节点 2 到节点 1 距离不变，仍为 2。 对于节点 3，原来的C  3  5。现在 C(w)+len(w，n)=C(4)+len（4，3）=1+3=4<C(3)。 因此节点 3 到节点 1 的距离要更新，从 5 减小到 4。 对于节点 5，原来的C  5   。现在 C(w)+len(w，n)=C(4)+len（4，5）=1+1=2<C(5)