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

类是核心网关协议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)