IP选路

       根据上面的讨论，我们知道IP网络选路采用的是路由表驱动的下一跳路由方法。路由器每收到一个数据报，就根据目的IP地址查询路由表，找出匹配网络号及相应的下一跳路由器，完成数据转发。如果IP报指定至目的主机的路由，则按此路由转发；如果找不到匹配网络，则发往默认路由器；如果已到达本网络，则转换成物理地址、重新封装数据报后将其发给主机。

        本节进一步讨论路由器中的路由表是如何形成和更新的，也就是路由算法问题。

1.基本原理

       虽然路由表只给出至给定目的地的下一跳地址，但是路由器知道这一定是通往该目的地的最佳路由，最佳的含义根据需要可以是时延、可靠度或吞吐昼等，在理论上都可以对应为一个成本函数，最佳路由就是最低成本路由。另外，当网络局部出现故障或拥塞时，路由表应能动态调整，以绕过这些出问题的区域。

为此必须解决两个问题：

       为了降低问题的复杂性，从路由的角度可以将一个互联网视为由许多个独立的子系统组成。每个子系统归属一个组织运行，内部的路由器执行同样的路由算法，具有相同的路由表，这样的子系统称作自治系统(AS-AutonomousSystem)。例如3个公司的内部网络X、Y、Z，都连在Internet上，各自使用不同的路由算法，则就是3个AS。在自治系统内部执行的、用于内部路由器之间交换网络状态信息的路由协议称之为内部网关协议(IGP-InteriorGatewayPratocol)。目前应用最广泛的IGP就是开放式最短路经优先(OSPF-OpenShortestPathFirst)协议，在1990年成为IETF标准。

      在不同自治系统之间也必须交换信息，以便路由器确定至系统外网络的路由。每个系统是由边界路由器作为代表和相邻系统交换路由信息的，所使用的协议就称为外部网关协议(EGP-ExteriorGate-way Protocol)。典型的EGP就是边界网关协议(BGP-BorderGatewayProtocol)。

 

 

图2.27   内部和外部网关协议

       上述概念可用图2.27予以说明。R₁-R₄位于自治系统AS1  中，它们之间执行OSPF协议，由此每个路由器可以确定至AS₁ 中所有网络的最佳路由。R₅-R₈位于AS2中，也执行OSPF协议。R₁和R₅为边界路由器，分别代表AS₁和AS₂，它们之间执行BGP，相互告之经过自己能到达哪些网络，。R₁ 和R₅再将此信息转告本系统内部的路由器。如果一个数据报要从一个自治系统的一台主机发往另一个自治系统的一台主机，第一个系统的路由器只需要决定下一跳自治系统，将其转发给对应的边界路由器。如此接力传送至目的自治系统后，该系统的路由器就可根据路由表将数据报送达目的网络。相对来说，EGP传递的信息较IGP要少，且较简单。

2.OSPF协议

        OSPF是一种链路状态协议。每个路由器负责监视和它直接相连的发送链路的状态，包括链路的通达性，对端节点和链路成本（时延、距离等），当链路状态发生变化时，用OSPF更新消息通过洪泛方法及时将此信息告之自治系统中所有的路由器。执行BGP协议的边界路由器还要负责维护至外部系统中网络的路由状态信息，用OSPF消息通告状态变化信息。

       每个路由器根据上述信息，将自治系统抽象为一个有向图。有向图的节点就是路由器和网络，包括边界路由器可通达的外部网络。有向图的边就是连接两个路由器或路由器和连接网络的链路。每条边赋予一定的成本，链路双向成本一般不相同，且规定从网络到路由器的边的成本为零。图2.28为一个自治系统的示例，其中，H₁ 为和路由器直接相连的主机，也作为有向图节点处理；R₅～R₇为边界路由器，分别可通达外部网络Nl2~  Nl4及N12、Nl5。图2.29为该自治系统对应的有向图，图中标出各边的成本。根据此图，各路由器就可利用图论中的最短路径算法计算出至各网络和各边界路由器的最小成本路由。表2.2给出从路由器6转发至各目的网络的数据报的最优路由及下一跳路由器。

 

图2.28   自治系统示例

图2.29   系统的有向图

 

        如果要提供不同服务类别的选路，OSPF就需要建立若干个有向图，每个图中边的成本不同。例如一个图按时延度量给出成本，一个图按吞吐量度置给出成本，另一个图按可靠度给出成本。对于不同的数据报，可根据其应用采用相应的图算出最优路由，其代价是要维护三套路由表，协议通信量和计算量都要增加三倍。

 

           表2.2     RT6的OSPF路由计算结果

目的网络	下一跳路由器	最优路由	成本
Nl	R3	R3 - N3 - Rl - Nl	10
N2	R3	R3-N3-R2-N2	10
N3	R3	R3-N3	7
N4	R3	R3-N4	8
HI	RI0	R10 - N8 - Rll - N9 - Rl2 - Hl	21
N6	Rl0	R10- N6	8
N7	Rl0	R10 - N6 - R8 - N7	12
N8	RI0	R10 N8	10
N9	RI0	R10-N8-R11-N9	11
NI0	RI0	R10 - NS - R11 - N9 - R12 - NI0	13
N11	R10	R10 - N8 - R11 - N9 - R9 - N11	14
N12	RI0	R10- N6- R7 - --N12	10
N13	R5	R5---NI3	14
Nl4	R5	R5--Nl4	14
N15	RI0	RI0- N6- R7- -N15	17

 

3.BGP协议

        如前所述，BGP协议由边界路由器执行。从BGP路由器角度来看，整个互联网仅由BGP路由器构成，相邻路由器间有链路相连。所谓相邻指的是和同一网络相连的BGP路由器，如图2.27中的RI和R5，常称其为邻居。

        和OSPF协议类似，各BGP路由器通过BGP协议消息告之其它路由器，通过它可以抵达哪些网络。它不但要告之至这些网络的＂距离”，而且还要告之至这些网络的完整路径，也就是经过哪些自治系统能到达该网络。

        BGP路由器选路时不但要考虑至该网络的＂距离＂，还要考虑选路策略，这些策略包括政治、安全、经济等方面的考虑，例如不能经微软网络转发以IBM网络为源点或目的地点的数据报等。在每个BGP路由器中装有计分模块，基千综合因素计算路由的得分。BGP实际上是一种距离矢量协议。

        图2.30给出一个BGP路由器组成的抽象网络。设路由器F要确定至D的最优路由。它从其邻居B、G、I、E收到至D的转发路由分别为：

图2.30  BGP路由器网络

        B:B-C-D

       G:G-C-D

        I:I-F-G-C-D

       E:E-F-G-C-D

       F收到上述更新消息后，立即舍弃经I和E的路由，因为它们经由F本身。然后，它将经B、G的两条路由交计分模块打分，如果某条路由违反某条策略规定，则其得分为无穷大。最后F选择得分最小的路由作为最优路由，并将此结果经OSPF告之本自治系统内的各路由器。

       最后说明一点，上述OSPF和BGP配合有效地解决了路由器如何确定最优路由和下一跳路由器的问题，另外还有一个问题就是主机如何选定初始路由器。这个问题比较简单，首先该主机需判断目的主机是否在同一网络中，如果是，则使用网络访问协议直接将数据报送交目的主机；如果不是，则将数据报送给连在同一网络中的路由器，如有多个这样的路由器，则可简单地任选一个。