Chapter-2(new)

1、1Chapter 2Chapter 2Chapter 2 Interior Routing ProtocolsInterior Routing ProtocolsInterior Routing Protocols andandand ExteriorExteriorExterior Routing Protocols Routing Protocols Routing Protocols 张沪寅张沪寅2 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 2.1.1 路由选择功能路由选择功能 路由器在互联网中接收和转发路由器在互联网中接

2、收和转发IP数据报数据报 路由器必须通过互联网的路由器必须通过互联网的拓扑结构拓扑结构以及以及运行情况运行情况来来实现路由选择功能实现路由选择功能 路由选择总是基于某种形式的路由选择总是基于某种形式的最小耗费最小耗费原则原则 3 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 1. 固定路由选择方案固定路由选择方案(Fixed Routing) 网络中的每个源网络中的每个源-目的节点对都配置了目的节点对都配置了单一单一、永久永久的的路由路由 路由是路由是固定不变固定不变的的 可能可能在网络拓扑结构改变时才会发生变化在网络拓扑结构改变时

3、才会发生变化 设计路由时的链路耗费设计路由时的链路耗费不基于动态不基于动态的变化的变化 可以基于对可以基于对源源-目目的节点对的节点对预估预估的的通信量通信量或每条链路的或每条链路的容量容量 4 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 配置实例配置实例 ：5个网络，个网络，8个路由器组成个路由器组成 5 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 实例讨论实例讨论 上图的配置由上图的配置由5个网络和个网络和8个路由器组成个路由器组成 与每个网络相连接的路由器的与每

4、个网络相连接的路由器的输出端输出端都标记了一个都标记了一个链路耗费链路耗费 后面幻灯片将给出固定路由选择方案的实现方法后面幻灯片将给出固定路由选择方案的实现方法 每个路由器都有一个路由表每个路由器都有一个路由表 6 路由器中的路由表路由器中的路由表 通常通常IP地址由地址由网络字段网络字段和主机字段组成和主机字段组成 配置中的每一个配置中的每一个网络网络都作为表中的一项都作为表中的一项 并不需要为每个可能的并不需要为每个可能的目的主机目的主机设置一项设置一项(特定主机除外特定主机除外) 路由选择路由选择只与只与网络字段网络字段有关有关 一旦数据报到达与目的网络相连的路由器，该路由一旦数据报到达

5、与目的网络相连的路由器，该路由器就会把数据报传递给网络中正确的主机器就会把数据报传递给网络中正确的主机 路由表中的每一项都给出了一个路由表中的每一项都给出了一个目的网络目的网络以及到达以及到达该网络路由上的该网络路由上的下一个路由器下一个路由器 路由器中不需要为每一个可能的目的网络存储一个路由器中不需要为每一个可能的目的网络存储一个完整完整的路的路由，只需知道到达目的地的由，只需知道到达目的地的下一个路由下一个路由 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 7 主机中的路由表主机中的路由表 在主机中也可能配置路由在主机中也可能配

6、置路由 如果主机只连接到如果主机只连接到一个网络一个网络，且该网络只连接到，且该网络只连接到一个路由器一个路由器，则该主机则该主机不需要不需要路由表路由表 所有出网通信流量都必须指向同一个路由器所有出网通信流量都必须指向同一个路由器(称之为称之为网关网关) 如果网络中连接了如果网络中连接了多个多个路由器，则主机必须有一个路由表，路由器，则主机必须有一个路由表，表中说明哪些流量可以使用哪个路由器转发表中说明哪些流量可以使用哪个路由器转发 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 8 路由表实例路由表实例 2.1 因特网的路由选择原

7、理因特网的路由选择原理(Internet Routing Principles) 636159 2. 自适应路由选择方案自适应路由选择方案(Adaptive Routing) 当互联网的情况变化时，转发数据报的路由也会发当互联网的情况变化时，转发数据报的路由也会发生改变生改变 影响路由选择的主要状况有：影响路由选择的主要状况有： 故障故障(Failure) 能避免故障能避免故障 拥塞拥塞(Congestion) 能避开而不是经过拥塞区域能避开而不是经过拥塞区域 避免拥塞，或至少避免使拥塞恶化，这在高速互联网上非避免拥塞，或至少避免使拥塞恶化，这在高速互联网上非常关键常关键 2.1 因特网的路由

8、选择原理因特网的路由选择原理(Internet Routing Principles) 10 自适应路由选择方案的缺点自适应路由选择方案的缺点 路由选择方案更加复杂路由选择方案更加复杂 加重了路由器的处理负担加重了路由器的处理负担 这种策略取决于在这种策略取决于在一个地方搜索一个地方搜索到而在到而在另一个地方另一个地方应用应用的状态信息的状态信息 交换的信息越多以及越频繁提高了路由选择的正确性，当同交换的信息越多以及越频繁提高了路由选择的正确性，当同时也时也加重了网络的负担加重了网络的负担 自适应策略可能会反映过快，引起因拥塞而造成的自适应策略可能会反映过快，引起因拥塞而造成的振荡振荡 也可能

9、反映过慢，失去自适应的效果也可能反映过慢，失去自适应的效果 自适应策略可能造成路由反常：自适应策略可能造成路由反常： 摆动摆动(Fluttering) 兜圈子兜圈子(Looping) 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 11 摆动摆动(Fluttering) 摆动反映了路由选择的摆动反映了路由选择的快速振荡快速振荡 引起这种现象的原因可能是路由器试图对负荷分流引起这种现象的原因可能是路由器试图对负荷分流或进行或进行负荷平衡负荷平衡 对负载分流的定义：对负载分流的定义： 在下一跳选择过程中，可能会有在下一跳选择过程中，可能会

10、有多条路由可选多条路由可选 路由器可以保存多条路由并采用负荷分流机制让这些路由路由器可以保存多条路由并采用负荷分流机制让这些路由分分担通信量担通信量 其结果可能导致到达一个目的地的一系列分组经过了其结果可能导致到达一个目的地的一系列分组经过了完全不完全不同同的路由的路由 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 12 Example of Fluttering 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) umann13 Problems with Flutterin

11、g 如果出现了摆动，产生摆动的两个方向上的路由特如果出现了摆动，产生摆动的两个方向上的路由特性是不同的性是不同的 其中包含其中包含计时特性计时特性和和差错特性差错特性 这可能对这可能对管理管理应用和应用和故障查找故障查找应用试图测定路由特性造成应用试图测定路由特性造成 混乱混乱 用源端与目的端的两个不同路由，难以用源端与目的端的两个不同路由，难以估算往返传估算往返传输的时间和可用容量输的时间和可用容量 如果两个路由具有不同的传送时间，如果两个路由具有不同的传送时间，TCP分组将分组将不不按序到达按序到达 会导致错误的快速重传会导致错误的快速重传 导致这种错误的原因是产生重复确认导致这种错误的原

12、因是产生重复确认 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 14 兜圈子兜圈子(Looping) 由一个路由器转发出去的分组由一个路由器转发出去的分组又回到又回到了这个路由器了这个路由器 路由选择算法的设计是要防止出现兜圈子的现象路由选择算法的设计是要防止出现兜圈子的现象 当互联网的连通性发生变化，并且这些变化当互联网的连通性发生变化，并且这些变化没有及没有及时时传播到所有其他的路由器时仍然可能会兜圈子传播到所有其他的路由器时仍然可能会兜圈子 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing P

13、rinciples) 15 Adaptive Routing Advantages 自适应路由选择策略可以自适应路由选择策略可以改善性能改善性能 有助于有助于拥塞控制拥塞控制 一般来说自适应路由选择方案是非常复杂的一般来说自适应路由选择方案是非常复杂的 这也是为什么路由选择协议多年来一直都在演进发展这也是为什么路由选择协议多年来一直都在演进发展 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 16 Classification of Adaptive Routing Strategies 分类方法是基于分类方法是基于信息源信息源进行进

14、行(包含包含3点点) 本地本地(Local)：只依赖于本地信息进行自适应选择：只依赖于本地信息进行自适应选择 路由器给每个数据报选择路由时总是往发送队列长度Q最小的网络方向转发 这样做有平衡各网络方向负荷的效果 然而有些网络方向并不是数据报在一般情况下的正确转发方向，应考虑Q+Bi为最小值（Bi为偏向值） 只基于本地信息的自适应方案实际上很少应用 相邻节点相邻节点(Adjacent nodes) 基于相邻路由器信息的策略称为距离向量算法 所有节点所有节点(All nodes) 基于所有路由器信息的策略称为链路状态算法 在采用2、3点的情况下，路由选择协议都需要交换信息 2.1 因特网的路由选择

15、原理因特网的路由选择原理(Internet Routing Principles) 17 2.1.2 Autonomous Systems (AS) 由同类型的路由器（实现由同类型的路由器（实现同样的路由算法同样的路由算法）互联的）互联的由同一机构控制的互联网络部分称为由同一机构控制的互联网络部分称为自治系统自治系统 ,简称为简称为AS AS是一个路由器与网络的集合，是一个路由器与网络的集合，其最重要的特点就其最重要的特点就是它是它有权自主地决定有权自主地决定在本系统内应采用何种路由选择协在本系统内应采用何种路由选择协议议 AS是连通的是连通的 例外的情况是网络出现故障例外的情况是网络出现故障

16、 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 18 1. Interior Routing Protocol (IRP) 共同共同的路由选择协议用于在的路由选择协议用于在AS内的路由器之间传递内的路由器之间传递路由选择信息路由选择信息 在在AS内部使用的协议内部使用的协议不要求不要求在在系统外部也实现系统外部也实现 这样的灵活性使这样的灵活性使IRP可以根据客户的特殊应用和需求进行剪可以根据客户的特殊应用和需求进行剪裁裁 不同不同AS中路由器采用的路由选择算法和路由选择表中路由器采用的路由选择算法和路由选择表可能会可能会不一样不一

17、样 要求要求AS中的路由器中的路由器至少至少要知道系统外可通达网络的要知道系统外可通达网络的一些信息一些信息 每个每个AS中至少有一个路由器能与外部联系中至少有一个路由器能与外部联系 要使用外部路由选择协议要使用外部路由选择协议(ERP) 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 19 2. Exterior Routing Protocol (ERP) 通常通常ERP比比IRP少传递一些信息少传递一些信息 理由如下：理由如下： 如果一个如果一个AS中的主机要向另一个中的主机要向另一个AS中的主机传送中的主机传送数据报，第一个系

18、统的路由器只能要确定目标数据报，第一个系统的路由器只能要确定目标AS，并选，并选择能够到达系统的路由即可择能够到达系统的路由即可 一旦数据报进入目标一旦数据报进入目标AS，该系统内的路由器之间就，该系统内的路由器之间就会进行协调以便正确传递数据报会进行协调以便正确传递数据报 ERP不需要不需要关心也不需知道目标关心也不需知道目标AS内内路由走向的细路由走向的细节节 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 20 内部路由协议内部路由协议用的最多的协议用的最多的协议 RIP(Routing Information Protocol

19、)，OSPF(Open Shortest Path First)。 外部路由协议主要考虑的是外部路由协议主要考虑的是路由选择策略路由选择策略（政治、（政治、经济、安全），目前使用的最多的是经济、安全），目前使用的最多的是BGP-4协议。协议。 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 21 IRP and ERP 2.1 因特网的路由选择原理因特网的路由选择原理(Internet Routing Principles) 22 路由信息协议路由信息协议RIP是是IGP中最先得到广泛使用的协中最先得到广泛使用的协议，议，RIP是一种

20、是一种分布式分布式的的基于距离向量基于距离向量的路由选择协议，的路由选择协议，其特点如下：其特点如下： 简单简单 适合小型互联网适合小型互联网 应用广泛应用广泛 关键特性是采用了关键特性是采用了距离向量路由选择距离向量路由选择技术技术 2.2 Routing Information Protocol(RIP)23 Bellman-Ford Algorithm (1) 定义定义 s =源顶点源顶点 w(i,j) = 从顶点从顶点i到顶点到顶点j的链路耗费的链路耗费 w(i,i) = 0 w(i,j) = 如果两个顶点之间不直接相连如果两个顶点之间不直接相连 w(i,j) 0 如果两个顶点之间直接

21、相连如果两个顶点之间直接相连 h =在算法的当前步骤中路径的在算法的当前步骤中路径的最大链路数最大链路数 Lh(n) =从顶点从顶点s到顶点到顶点n的最小耗费路径的耗费，的最小耗费路径的耗费，其中路径的其中路径的链路数不超过链路数不超过h 2.2 Routing Information Protocol(RIP)24 Bellman-Ford Algorithm (2) 步骤步骤 1. 初始化初始化 a. L0(n) = ，对所有，对所有 n s b. Lh(s) = 0 ，对所有，对所有 h 2. 更新更新 a. 对相继的每个对相继的每个 h 0 . 对每个对每个 n s, 计算计算: Lh

22、+1 (n) = minLh(j)+ w(j,n), j . 找到实现最小值的顶点找到实现最小值的顶点j，将，将n与该前趋顶点与该前趋顶点j相连相连 . 删除删除n与所有其他前趋顶点的连接，这些连接是在前面与所有其他前趋顶点的连接，这些连接是在前面迭代中产生的迭代中产生的 . 从从s到到n的路径以的路径以j到到n的链路结束的链路结束 2.2 Routing Information Protocol(RIP)25 14.2 计算最短路径长度计算最短路径长度(Shorted Path Length Determination) Bellman-Ford Algorithm 示例示例 26 2.2.

23、1 距离向量路由选择距离向量路由选择(Distance Vector Routing) 这种选择算法要求每个节点要与其这种选择算法要求每个节点要与其相邻的节点相邻的节点互换互换信息信息 为了实现该协议，每个节点都要维持三个向量为了实现该协议，每个节点都要维持三个向量 Wx：节点：节点X的链路耗费向量的链路耗费向量(直接相连直接相连) Lx： 节点节点X的距离向量的距离向量 Rx： 节点节点X的下一跳转发向量的下一跳转发向量 每隔每隔30秒秒，每个节点与其所有，每个节点与其所有相邻节点相邻节点互换距离向互换距离向量量 节点节点x一般按照一定的规则更新所维持的两个向量一般按照一定的规则更新所维持的

24、两个向量L(x,j)和和R(x,j)，j表示网络号表示网络号 2.2 Routing Information Protocol(RIP)27 Distance Vector Example F15.5 2.2 Routing Information Protocol(RIP)111128 Distance Vector Example F15.5 2.2 Routing Information Protocol(RIP)12345629 RIP采用的路由选择算法是采用的路由选择算法是Bellman-Ford算法的算法的分布式分布式版本版本 每一次重复地执行所有路由器之间同时交换其距离向量每一次

25、重复地执行所有路由器之间同时交换其距离向量的操作都等的操作都等效于在效于在每个节点执行每个节点执行Bellman-Ford算法第二步的算法第二步的一次迭代计算一次迭代计算 实际上，实际上，RIP以及有其他基于距离向量路由选择的路由以及有其他基于距离向量路由选择的路由协议都采用异步方式协议都采用异步方式 当一个节点启动后当一个节点启动后 首先初始化并在收到所有相邻节点的距离向量后进行更新 然后根据自己的定时器，每个路由器隔然后根据自己的定时器，每个路由器隔30秒都要向其相邻节点发秒都要向其相邻节点发送距离向量送距离向量 如果链路耗费发生了变化将传播到网上如果链路耗费发生了变化将传播到网上 新的最

26、短路径计算过程将在新的最短路径计算过程将在一段有限时间一段有限时间收敛于正确结果收敛于正确结果 这段有限时间与路由器数量成正比 2.2 Routing Information Protocol(RIP)30 2.2.2 RIP的细节的细节 首先算法是首先算法是异步执行异步执行的，所以的，所以无法保证无法保证所有的最新距离所有的最新距离向量都在一个给定的时间传内收到向量都在一个给定的时间传内收到 其次，其次，RIP报文是用报文是用UDP 的的520端口传送的，会有部分传送的，会有部分分组丢失分组丢失 RIP被设计成采用被设计成采用增量执行方式增量执行方式，只要收到一个距离向，只要收到一个距离向量

27、就执行算法并更新路由选择表量就执行算法并更新路由选择表 RIP服从以下的规则服从以下的规则 如果收到的距离向量中包括了如果收到的距离向量中包括了新新的的目标网络目标网络，则直接，则直接加到加到路由选路由选择表中择表中 如果收到的距离向量中有一条到达某目标网络如果收到的距离向量中有一条到达某目标网络值更小值更小的路由，则的路由，则替换替换现有的路由现有的路由 如果从路由器如果从路由器R收到更新向量，且当前路由选择表中有一个和更收到更新向量，且当前路由选择表中有一个和更新记录是以新记录是以R为下一个转发节点的，那么为下一个转发节点的，那么所有这些记录项都要更新所有这些记录项都要更新，以，以反映来自

28、反映来自R的最新信息的最新信息 2.2 Routing Information Protocol(RIP)31 Counting to Infinity Problem (1)-无穷计数无穷计数 RIP中一个比较严重的问题是它对拓扑变化的中一个比较严重的问题是它对拓扑变化的收敛收敛速度较低速度较低，这样可能导致下面的现象，这样可能导致下面的现象 首先我们假设有如下配置首先我们假设有如下配置: 所有的链路耗费都为所有的链路耗费都为1 B到网络到网络5的距离是的距离是2，下一个转发节点是，下一个转发节点是D A和和C到网络到网络5的距离都是的距离都是3，下一个转发节点都是，下一个转发节点都是B 2

29、.2 Routing Information Protocol(RIP)32 Counting to Infinity Problem (2)-无穷计数无穷计数 现假定路由器现假定路由器D失效：失效： B检测到网络检测到网络5不能通过不能通过D到达到达 于是通过来自A和C的报告将其到网络5的距离设置为4，因A和C到网络5的距离为3 下一个报告周期中，下一个报告周期中，B将这个信息传递给将这个信息传递给A和和C A和和C接到这个消息后将其到网络接到这个消息后将其到网络5的距离增加到的距离增加到5 从B到目标网络的距离加上A和C到B的距离1 B收到了距离计数值收到了距离计数值5，并认为现在到达网络

30、，并认为现在到达网络5的距离是的距离是6 这个过程会一直持续下去，直到距离值达到无穷大，在这个过程会一直持续下去，直到距离值达到无穷大，在RIP中是中是16 以以30秒的报告间隔，上述情况要持续秒的报告间隔，上述情况要持续816分钟才能结束分钟才能结束 2.2 Routing Information Protocol(RIP)33 Counting to Infinity Diagram F15.6 (N5,1)(N5,D,2)(N5,B,3)(N5,B,3) 2.2 Routing Information Protocol(RIP)34 水平拆分水平拆分(Split Horizon) 无穷计

31、数问题由于是无穷计数问题由于是B和和A（以及（以及B和和C之间）互相之间）互相误解造成的误解造成的 彼此之间都认为通过双方可以到达网络彼此之间都认为通过双方可以到达网络5 RIP中的水平拆分规则是将一条路由中的水平拆分规则是将一条路由信息发回到它信息发回到它来的方向来的方向是永远无用的是永远无用的 因为发送给你信息的路由器到达目标的距离总要比你因为发送给你信息的路由器到达目标的距离总要比你近近 水平拆分方法确实提高了速度，错误的路由可以在水平拆分方法确实提高了速度，错误的路由可以在180 秒秒的的超时间隔内被消除超时间隔内被消除 2.2 Routing Information Protocol

32、(RIP)35 反向恶化的水平拆分反向恶化的水平拆分(Poisoned Reverse) 这条规则与简单的水平拆分这条规则与简单的水平拆分不同不同，它要向从其得到，它要向从其得到路由信息的相邻节点发送距离计数为路由信息的相邻节点发送距离计数为16的更新向量的更新向量 如果两个路由器中有互相指向对方的如果两个路由器中有互相指向对方的路由路由，那么用，那么用16作为距作为距离计数值进行离计数值进行逆向逆向路由通知可以很快消除兜圈子现象路由通知可以很快消除兜圈子现象 2.2 Routing Information Protocol(RIP)36 2.2.4 RIP的局限性（的局限性（RIP Limi

33、tations） 随着互联网的增长，目的端的距离值随着互联网的增长，目的端的距离值超过超过15就不可达就不可达 另一方面，如果允许更大的距离值，初始化或拓扑变化时协议的另一方面，如果允许更大的距离值，初始化或拓扑变化时协议的收敛时间可能会很长收敛时间可能会很长 过分简化的过分简化的距离值距离值导致路由选择达不到最佳状态导致路由选择达不到最佳状态 会使分组在过于低速的链路上传送会使分组在过于低速的链路上传送(或成本过高的链路或成本过高的链路) 当网络出现故障时，要经过较长的时间才能将信息传送当网络出现故障时，要经过较长的时间才能将信息传送到所有的路由器到所有的路由器(坏消息反应慢坏消息反应慢)

34、开销大开销大。每个结点不仅要记录大量数据，而且还要周期每个结点不仅要记录大量数据，而且还要周期性地与邻结点交换信息，增加大量的通信开销性地与邻结点交换信息，增加大量的通信开销 使使更新更新路由表的过程路由表的过程较长较长，不适合，不适合规模较大规模较大的网络的网络 2.2 Routing Information Protocol(RIP)37 2.3 Open Shortest Path First(OSPF) RIP的局限性逐渐影响到它的流行的局限性逐渐影响到它的流行 OSPF是基于是基于TCP/IP的互联网上被优先选用的内部的互联网上被优先选用的内部路由选择协议路由选择协议 OSPF计算的

35、中心思想是采用计算的中心思想是采用链路状态路由选择链路状态路由选择方方案案 OSPF是分布式是分布式链路状态路由协议链路状态路由协议，而，而RIP是分布式是分布式距离向量路由协议距离向量路由协议 38 OSPF协议与协议与RIP协议不同协议不同特点特点： 采用采用洪泛法洪泛法向本自治系统中所有路由器发送信息。向本自治系统中所有路由器发送信息。RIP仅仅向自己仅仅向自己相邻相邻的几个路由器发送信息的几个路由器发送信息 发送的信息就是与本路由器发送的信息就是与本路由器相邻相邻的所有路由器的的所有路由器的链链路状态路状态信息和度量值信息和度量值(费用、距离、时延、带宽等费用、距离、时延、带宽等)。R

36、IP协议发送的信息是协议发送的信息是“到到所有所有网络的网络的距离和下一跳路由器距离和下一跳路由器” 只有当只有当链路状态发生变化链路状态发生变化时，路由器才用洪泛法向时，路由器才用洪泛法向所有路由器发送此信息。所有路由器发送此信息。RIP不管网络拓扑结构不管网络拓扑结构有无变有无变化化，路由器都要，路由器都要定期定期交换路由表的信息交换路由表的信息 2.3 Open Shortest Path First(OSPF)39 2.3.1 链路状态路由选择链路状态路由选择(Link State Routing) 当路由器进行当路由器进行初始化初始化时，要确定其时，要确定其每个每个网络接口上网络接口

37、上所连所连链路链路的的耗费耗费 路由器将这些链路耗费播发到互联网拓扑中的其他路由器将这些链路耗费播发到互联网拓扑中的其他所有路由所有路由器器 从这时开始，路由器一直从这时开始，路由器一直监测监测其相连的链路耗费其相连的链路耗费 一旦发生重大变化，路由器将再次播发其链路耗费到配置中的所有一旦发生重大变化，路由器将再次播发其链路耗费到配置中的所有其他其他路由器路由器 因为每个路由器都会接收到所有其他路由器的链路耗费，每因为每个路由器都会接收到所有其他路由器的链路耗费，每个路由器都能构造出个路由器都能构造出整个整个配置的拓扑，然后用配置的拓扑，然后用Dijkstra算法算法计算到计算到达达每个每个目

38、标网络的目标网络的最短路径最短路径 2.3 Open Shortest Path First(OSPF)40 Dijkstras Algorithm (1) 定义定义 N=网络中的顶点集合网络中的顶点集合 s=源顶点源顶点 T=算法中用到的临时顶点集合算法中用到的临时顶点集合 Tree=T中顶点组成的生成树，它包括从中顶点组成的生成树，它包括从s到到T中中每个每个顶点顶点的的最小耗费最小耗费路径上的边路径上的边 w(i,j) = 从顶点从顶点i到顶点到顶点j的链路耗费的链路耗费 w(i,i) = 0 w(i,j) = 如果两个顶点之间不直接相连如果两个顶点之间不直接相连 w(i,j) 0 如果

39、两个顶点之间直接相连如果两个顶点之间直接相连 L(n) = 从顶点从顶点s到顶点到顶点n的最小耗费路径的耗费，此的最小耗费路径的耗费，此项是项是已知的已知的(在图中标出在图中标出) 算法结束时，也就是图中算法结束时，也就是图中s到到n的最小的最小耗费路径的耗费耗费路径的耗费 2.3 Open Shortest Path First(OSPF)41 Dijkstras Algorithm (2) 步骤步骤 1. 初始化初始化 a. T = Tree = s 临时顶点集合中只有源顶点 b. L(n) = w(s,n) for n s 到相邻顶点的初始路径耗费就是链路耗费 2. 取下一个顶点取下一个

40、顶点 a. Find x T 且 L(x) = min L(j), j T (找到不在T中且到顶点s有最小耗费路径的邻接顶点x) b. 将 x 加入到 T 和Tree中 c. 将关联x且使L(x) 成为最小耗费的边加入到Tree中 路径的最后一跳也加入到Tree中 3. 更新最小耗费路径更新最小耗费路径 a. L(n) = minL(n), L(x) + w(x,n) n T 如果第二项最小，则从s到n的路径从现在起就是从s到x再连上x与n之间的边 2.3 Open Shortest Path First(OSPF)42 14.2 计算最短路径长度计算最短路径长度(Shorted Path L

41、ength Determination) Dijkstras Algorithm (3) 示例示例 43 洪泛（洪泛（Flooding） 分组的分组的源源路由器将分组发送给它的路由器将分组发送给它的所有相邻所有相邻路由器路由器 R接收到分组以后在所有的出向链路上发出，但接收到分组以后在所有的出向链路上发出，但接接收到该分组的链路除外收到该分组的链路除外 OSPF采用了让每个节点采用了让每个节点记住所转发分组的标识记住所转发分组的标识，当当重复到达该节点重复到达该节点时将它们时将它们丢弃丢弃的方法的方法 这种方法防止了无休止的转发过程这种方法防止了无休止的转发过程 2.3 Open Shorte

42、st Path First(OSPF)44 洪泛法有三个洪泛法有三个特点特点： (1) 源点和终点之间源点和终点之间所有的路由都试过所有的路由都试过了，只要有一条路径存在，了，只要有一条路径存在，分组就一定能到达目的地分组就一定能到达目的地 这一特性反映了洪泛技术是非常这一特性反映了洪泛技术是非常坚实坚实的的 (2) 所有路由都试过了，至少有一个分组副本会沿着所有路由都试过了，至少有一个分组副本会沿着最小时延路最小时延路由由到达目的地到达目的地 第二条特性反映了洪泛中的信息第二条特性反映了洪泛中的信息会很快到达所有路由器会很快到达所有路由器 (3) 直接或间接连接于源节点的所有节点都遍历了直接

43、或间接连接于源节点的所有节点都遍历了 这条特性说明这条特性说明所有路由器会收到所有路由器会收到创建路由选择表所需的创建路由选择表所需的信息信息 洪泛技术的主要缺点是它产生的通信量洪泛技术的主要缺点是它产生的通信量负荷大负荷大，与网络，与网络连通连通性成正比性成正比 2.3 Open Shortest Path First(OSPF)45 Flooding Example 2.3 Open Shortest Path First(OSPF)46 Sample Autonomous System 2.3 Open Shortest Path First(OSPF)47 Resultant Dire

44、cted Graph 2.3 Open Shortest Path First(OSPF)48 SPF Tree for Router 6 2.3 Open Shortest Path First(OSPF)49 2.3.2 OSPF的工作过程：的工作过程： 通过通过可靠的洪泛法可靠的洪泛法将邻居信息广播到所有节点，将邻居信息广播到所有节点，构构造造链路状态数据库。链路状态数据库。 每个节点利用最短路径算法，依据收集到的网络拓每个节点利用最短路径算法，依据收集到的网络拓扑信息计算到目的节点的扑信息计算到目的节点的最短路径，生成最短路径树最短路径，生成最短路径树。 每个每个OSPF路由器使用这些

45、路由器使用这些最短路径树构造路由表。最短路径树构造路由表。 OSPF的更新过程收敛的很的更新过程收敛的很快快。 2.3 Open Shortest Path First(OSPF)50 2.3.3 链路耗费（链路耗费（Link Costs） 每一跳每个方向的耗费称为路由选择度量值每一跳每个方向的耗费称为路由选择度量值 OSPF提供了基于服务类型提供了基于服务类型(TOS)概念的灵活的路由概念的灵活的路由度量值方案度量值方案 正常正常(TOS 0) 最小经济成本最小经济成本(TOS 2) 最大可靠性最大可靠性(TOS 4) 最大吞吐率最大吞吐率(TOS 8) 最小时延最小时延(TOS 16) 每

46、个路由器每个路由器可能可能会构造多达会构造多达5个不一样的路由选择个不一样的路由选择表，每种表，每种TOS一个。事实上，每个路由器都会为具体配一个。事实上，每个路由器都会为具体配置产生置产生5棵生成树棵生成树，从而为，从而为IP数据报按照数据报按照TOS来选择路由来选择路由 2.3 Open Shortest Path First(OSPF)51 2.3.4 OSPF Packet Format IP 数据报IP数据报首部OSPF 分组OSPF 分组首部类型 1 至类型 5 的 OSPF 分组24 字节081631版 本路 由 器 标 识 符类 型分 组 长 度检 验 和鉴 别比特鉴 别区 域

47、 标 识 符鉴 别 类 型 2.3 Open Shortest Path First(OSPF)52 2.3.5 OSPF Packet Types (1) OSPF的五种分组类型的五种分组类型 a.类型类型1，问候问候分组，用来发现和维护邻站的可达性。分组，用来发现和维护邻站的可达性。 b.类型类型2，数据库描述数据库描述分组，向邻站给出自己的链路状态数据库分组，向邻站给出自己的链路状态数据库中的所有链路状态项目的中的所有链路状态项目的摘要摘要信息信息(主要是结构，如：拓扑主要是结构，如：拓扑)。 c.类型类型3，链路状态请求链路状态请求分组，向对方请求发送某些链路状态项分组，向对方请求发送

48、某些链路状态项目的详细信息目的详细信息(如增加的新信息如增加的新信息)。 d.类型类型4，链路状态更新链路状态更新分组，用洪泛法对全网更新链路状态。分组，用洪泛法对全网更新链路状态。 e.类型类型5，链路状态确认链路状态确认分组，对链路更新分组确认。分组，对链路更新分组确认。 2.3 Open Shortest Path First(OSPF)53 (2) 各种分组的工作过程各种分组的工作过程问候问候数据库描述数据库描述数据库描述数据库描述链路状态请求链路状态更新链路状态确认确定可达性达到数据库的同步新情况下的同步 2.3 Open Shortest Path First(OSPF)54 2.

49、4 路径向量协议：路径向量协议：BGP 距离向量距离向量协议和协议和路径状态路径状态协议的不足协议的不足 RIP和和OSPF协议作为外部路由选择协议都不是很有协议作为外部路由选择协议都不是很有效。效。 距离向量和链路状态协议假设所有路由器采用距离向量和链路状态协议假设所有路由器采用同同样的度量样的度量 不同的自治系统间有不同的不同的自治系统间有不同的优先级优先级，采用不同的，采用不同的度量方案度量方案以及不同的限制以及不同的限制策略策略，距离向量算法，距离向量算法无法无法给出给出沿途经过的各个沿途经过的各个AS的内部信息的内部信息 链路状态的链路状态的洪泛洪泛涉及到多个自治系统中的路由器，涉及

50、到多个自治系统中的路由器，这很可能是这很可能是无法管理无法管理的的55 2.4 路径向量协议：路径向量协议：BGP 2.4.1 路径向量路由选择路径向量路由选择(Path Vector Routing) 另一种方法称为另一种方法称为路径向量路径向量方法，它方法，它舍弃了路由度量舍弃了路由度量值值 只提供以下信息：只提供以下信息： 哪个网络经由哪个路由器可达哪个网络经由哪个路由器可达 必须经过哪些自治系统必须经过哪些自治系统 与距离向量算法有与距离向量算法有两点不同两点不同： 首先是路径向量方法首先是路径向量方法不包括距离或耗费的估计值不包括距离或耗费的估计值 其次每个其次每个路由信息块列出沿着

51、某路由到达目标网络路由信息块列出沿着某路由到达目标网络经过的所有经过的所有自治系统自治系统 这样提供的路径信息使路由器可以这样提供的路径信息使路由器可以按照某种策略选择路由按照某种策略选择路由(安全、性能、质量、自治系统个数最少等安全、性能、质量、自治系统个数最少等) 56 4.4.2 边界网关协议边界网关协议(Boarder Gateway Protocol,BGP) BGP设计设计目标目标是使不同自治系统中的路由器是使不同自治系统中的路由器(网关网关)能够互相协作、交换路由信息能够互相协作、交换路由信息 协议的运行要交换一些报文，报文协议的运行要交换一些报文，报文通过通过TCP连接传连接传

52、递报文递报文 见下一张幻灯片见下一张幻灯片 BGP包括三个功能性过程：包括三个功能性过程： 邻站获知邻站获知 邻站可达性邻站可达性 网络可达性网络可达性 2.4 路径向量协议：路径向量协议：BGP57 BGP v4 报文报文(BGP v4 Messages) 打开打开(Open)报文报文 用于与另一个路由器用于与另一个路由器(BGP发言人发言人)建立相邻关系建立相邻关系 更新更新(Update)报文报文 传送传送单条单条路由的信息路由的信息 列出要撤除的列出要撤除的多条多条路由路由 保活保活(Keepalive)报文报文 对对Open报文的确认报文的确认 周期性地证实相邻关系周期性地证实相邻关

53、系 通知通知(Notification)报文报文 用来发送检测到的差错用来发送检测到的差错 2.4 路径向量协议：路径向量协议：BGP58 邻站获知邻站获知(Neighbor Acquisition)过程过程： 两个路由器连接于同一个子网，称它们是两个路由器连接于同一个子网，称它们是邻站邻站 如果两个路由器在如果两个路由器在不同不同的自治系统中，它们之间就的自治系统中，它们之间就可能要交换路由信息可能要交换路由信息 当两个不同自治系统中的相邻路由器同意经常性地当两个不同自治系统中的相邻路由器同意经常性地互换路由信息时就产生了互换路由信息时就产生了邻站获知过程邻站获知过程 由于有的路由器可能不想

54、参加路由信息互换，因此需要有一由于有的路由器可能不想参加路由信息互换，因此需要有一个标准的获知过程个标准的获知过程 一个路由器向另一个路由器发送请求报文一个路由器向另一个路由器发送请求报文(Open)，后者后者可以接受可以接受也也可以拒绝可以拒绝前者的请求前者的请求 2.4 路径向量协议：路径向量协议：BGP59 邻站可达性邻站可达性(Neighbor Reachability)过程过程： 一旦邻站关系建立，两个路由器都要一旦邻站关系建立，两个路由器都要周期性周期性地发送地发送keepalive报文，保持邻站关系报文，保持邻站关系 在在所有所有是邻站的路由器之间都要发送，以保持邻站是邻站的路由

55、器之间都要发送，以保持邻站可达性可达性 2.4 路径向量协议：路径向量协议：BGP60 网络可达性网络可达性(Network Reachability)过程过程： 每个每个路由器路由器要保持一个要保持一个数据库数据库，其中记录可达的，其中记录可达的子子网网及到达该及到达该子网的优选路由子网的优选路由 一旦数据库内容发生变化，路由器就要向实现了一旦数据库内容发生变化，路由器就要向实现了BGP的其他路由器发送一个的其他路由器发送一个 Update报文报文 通过通过Update报文的广播，所有的报文的广播，所有的BGP路由器都能建路由器都能建立并保持路由信息立并保持路由信息 2.4 路径向量协议：路

56、径向量协议：BGP61 BGP 报文格式报文格式 (BGP Message Formats) 每个报文包含了每个报文包含了三个字段三个字段： 标记标记(Marker)： 为身份鉴别保留的，为身份鉴别保留的， 发方填入，收发验证发方填入，收发验证 长度长度(Length)： 报文的长度报文的长度, 以字节为单位以字节为单位 类型类型(Type)： Open, Update, Keepalive, Notification 报文类型报文类型,分为以上四种分为以上四种62 邻站获知过程细节邻站获知过程细节 路由器路由器首先首先要与想要联系的要与想要联系的邻站邻站路由器建立路由器建立一个一个TCP连连接接 然后发送然后发送Open报文报文 Open报文中报文中给出给出发送方所在的发送方所在的自治系统自治系统以及以及路由器的路由器的IP地址地址 报文中还包括一个报文中还包括一个保持时间参数保持时间参数 指明发送方保持定时器(Hold Timer)的定时秒数 如果接收方准备建立邻站关系如果接收方准备建立邻站关系 它就计算保持定时器的值它就计算保持定时器的值 该值是它自己的保持时间和Open报文中保持时间的最小值 所计算出的值是发送方前后两次接收keepalive/update报文的最大时间间隔 以以keepalive报文应答报文应答 2.4 路径向量协议：路径向量协议：BGP63 Keep