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

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

1.基本原理

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

为此必须解决两个问题：

　　路由器之间如何交换网络的拓扑和状态信息，使每个路由器都能掌握全网的状态，这就是路由协议问题。

　　路由器如何根据所掌握的网络状态，计算至各目的地点的最佳路由，这就是路由算法问题。

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

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

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

2.OSPF协议

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

　　每个路由器根据上述信息，将自治系统抽象为一个有向图。有向图的节点就是路由器和网络，包括边界路由器可通达的外部网络。有向图的边就是连接两个路由器或路由器和连接网络的链路。每条边赋予一定的成本，链路双向成本一般不相同，且规定从网络到路由器的边的成本为零。图2.28为一个自治系统的示例:

　　其中，H1为和路由器直接相连的主机，也作为有向图节点处理；R5、凡为边界路由器，分别可通达外部网络N12-N14及N12、N15。图2.'29为该自治系统对应的有向图，图中标出各边的成本。根据此图，各路由器就可利用图论中的最短路径算法计算出至各网络和各边界路由器的最小成本路由。表2.2给出从路由器6转发至各目的网络的数据报的最优路由及下一跳路由器。