路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。

路由器使用路由算法来找到到达目的地的最佳路由。

关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：总体式路由算法和分散式路由算法。

采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。

这些算法也被称为DV（距离向量）算法。

采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。

这些算法也被称为LS（链路状态）算法。

收敛是在最佳路径的判断上所有路由器达到一致的过程。

当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。

路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。

收敛慢的路由算法会造成路径循环或网络中断。

路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有：1、选择最短路由还是最佳路由；2、通信子网是采用虚电路操作方式还是采用数据报的操作方式；3、采用分布式路由算法还是采用集中式路由算法；4、考虑关于网络拓扑、流量和延迟等网络信息的来源；5、确定采用静态路由还是动态路由。

各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。

链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。

距离向量算法（也叫做 Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。

也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。

metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。

路由选择协议（Routing protocol）当两台非直接连接的计算机需要经过几个网络通信时，通常就需要路由器。

路由器提供一种方法来开辟通过一个网状联结的路径。

路由选择协议的任务是，为路由器提供他们建立通过网状网络最佳路径所需要的相互共享的路由信息。

当一个计算机发送一个分组时，在网络上网络协议栈的每一层都附加一些信息给它。

在接收方的对等层协议可以读出这些信息。

这些信息类似于通信会话的某些部分。

网络层的协议附加路由选择信息，这可能是通过一个网络的完整的路径或是一些指示分组应该采用那条路径的优先值。

发送方添加的网络层信息只能由路由器或接收方的网络层协议读取。

中继器和桥接器不能识别网络层信息，只能传送和转发分组。

Routing Algorithms 路由选择算法一个路由器设备可能有两个或多个可以发送数据分组的端口。

它必须有一张转发表（forwarding table）为每一个端口标明一个特定地址。

早期路由器不和其它路由器交换网络上有关路由器的信息，因此，一个路由器通常沿着每条路径发送数据分组，分组充满网络，并且发送的一些分组在网络上无休止地循环。

为了避免这些问题，路由器可以依赖人工编程把选择的路径输进设备。

这被称为静态路由选择。

动态路由选择是一个更好的方式，它依靠路由器收集网络信息和建立自己的路由表。

路由器相互交换路由表，并且归并这些路由信息建立更新的路由表。

从其它路由器上获得的信息，提供到网络上目的站点的路由中继（hop）数或与路径相关的费用。

同时，每个路由选择设备上的路由表，应该包含大体上一致的路由选择信息。

路由选择协议基本上有两类：距离向量和链路状态，将在下面用两段文字介绍这两类协议。

距离向量路由选择协议的分组传送路由是根据到接收站的hop数或费用决定的，这些信息由各相邻的路由器提供。

技术上通常都遵循Bellman－Ford算法。

一个路由器有几个端口，每个端口都有指定的价值，这些价值是由网络管理员设定的。

用使用一条线路实际费用的多少，作为一种衡量手段表明一条线路比另一条好或坏。

此外，相邻的那些路由器告诉它们把分组送往目的站要花费的代价。

路由器将端口的价值加到相邻路由器的价值上，如下面的例子：端口1价值10 + 相邻路由器价值17＝27。

端口2价值20 + 相邻路由器价值5＝25。

端口3价值30 + 相邻路由器价值7＝37。

在这种情况下，路由器将通过端口2传送分组，因为它表明到接收站的代价最少。

假如有必要，用邻接端口2的路由器再计算到下一个路由器的路径价值。

路由信息，如下一个hop的地址等都存在表中，并且路由器大约每隔30秒互相交换表。

初始时，每一个网络只知道直接相连的路由器。

当一个路由器得到一张表，它将表项与自己的表进行比较。

根据这些信息，它用新增路由或删除路由来修改表。

表中信息包含：网络号；端口号；价值度量；下一个hop的地址。

价值度量是路由器向前传送分组到网中下一个路由器时选择路径所用的量值。

通用距离向量路由选择协议有：路由选择信息协议（RIP）是一个首先在Xerox网络系统（XNS）中实现，而后又在Novell的NetWare中实现的距离向量路由选择协议。

内部网关路由选择协议（IGRP）是由Cisco开发的距离向量路由选择协议。

路由选择表维护协议（RTMP）是一个在两个AppleTalk区中选取最佳路径的Apple协议，大约每10秒广播一次。

距离向量路由选择不适合于有几百个路由器的大型网或经常要更新的网。

在大型网中，表的更新过程可能过长，以至于最远的路由器的选择表不大可能与其它表同步更新。

在这种情况下，链路状态路由选择更可取些。

另外，链路状态协议能够为安全起见把机密信息隔离在特殊区域，或避开网上正在进行计算机辅助设计（CAD）、多媒体通讯等拥挤区域。

并且，路由选择信息表在必要时进行交换而不是规律性地交换，这样可以减少网络上的信息流量。

链路状态路由选择比距离向量路由选择需要更强的处理能力，但它可以对路由选择过程提供更多的控制和对变化响应更快。

路由选择可以基于避开拥塞区、线路的速度、线路的费用或各种优先级别。

Dijkstra算法用于计算路由，根据如下：分组到达目的站经过的路由器数量，这叫做路由中继（hop），并且hop数越少越好。

局域网间传输线路的速度。

有些路由使用低速异步连接，而另一些路由使用高速数字链路。

信息拥塞将造成延迟。

如果一台工作站传送一个大文件，路由器可以通过不同的路径发送分组以避免交通阻塞。

路由的费用路由的费用，网络管理员定义的一个度量，通常是根据传输介质确定的。

最便宜的路径可能不是最快的，但对某些类型的传输却更为可取。

最常用的链路状态路由选择协议是优先开放最短路径（OSPF），它和OSI的中间系统到中间系统（IS－IS）是类似的。

OSPF的原型是Proten开发的，是从OSIIS －IS的一个早期版本中派生出来的。

OSPF在Internet和TCP／IP网上IP通信的路由选择中使用。

IS－IS既可在IP通信中使用，也可在OSI通信中使用。

OPSF路由选择表OPSF路由选择表仅当在需要时更新，而不是定时更换。

这有效地减少了通信流量和节省了网络带宽。

通过网络的路径由上述标准选定。

一个网络管理员可以根据信息传送的类型编制通过网络的路径。

例如，当线路有较高数据传输率时，即使通过网络的那条路径有较多的hop数也是很可取的；另一方面，对于不大重要的信息将安排在低速低值的线路上传送。

Autonomous Environments 自治环境Internet路由选择（TCP／IP）和OSI路由选择使用了一个自治系统（AS）或管理区域（AD）的概念，可以简单地理解成区域（domains）。

一个区域是一些使用相同路由选择协议的主机和路由器的集合，如图R－11中所示，它们使用相同的路由选择协议和由单一机构管理。

换句话说，一个区域可以是一所大学或其它机构管理的一个互联网。

例如Internet是一个由教育部门、政府机关和各个公司管理的自治系统链接起来的互联网络。

每个机构都有自己的内部网络，通过外部网关与Internet网连接（Internet 网以前把路由器称作网关，但现在已把它们叫做路由器了）。

Internet有内部网关协议和外部网关协议。

OSI协议也使用了自治系统的概念，但在一个区域内的路由选择称为域内路由选择，区域之间的路由选择称为域间路由选择。

内部／域内协议有许多种内部网关协议，并有几种在Internet网上常用，这些协议已在条目“AppleTalk路由选择”，“Internet路由选择”和“OSI的路由选择”中讨论。

地址解析协议（ARP）是一个Internet（TCP／IP）协议，它为内部路由器传递数据报提供了一种方法。

路由选择信息协议（RIP）是一种距离向量路由选择协议。

优先开放最短路径（OSPF）是一种链路状态路由选择协议，它优于RIP。

OSPF是Internet网中最常用的内部网关协议，但OSI IS－IS协议也用于Internet。

端系统到中间系统（ES－IS）是OSI公布的一种协议，它帮助端系统（如用户的计算机）寻找定位路由器，并提供一种方法使路由器告知端系统（ES）它们的存在。

中间系统到中间系统（IS－IS）也是OSI的一种路由选择协议，它为一个域内两个路由器之间传送信息分组提供动态路由。

IS－IS是一种链接状态协议。

内部网关路由选择协议（IGRP）是Cisco开发的一种距离向量路由选择协议。

外部／域间协议在自治域的边界是路由器（以前在Internet网上被称为网关）。

这些路由器和其它路由器用外部协议或Internet术语的外部网关协议（EGP）交换信息。

外部网关协议（EGP）是Internet上最初的域间路由选择协议。

现在它已被周边网关协议（BGP）取代了。

支持EGP的路由器也必须支持BGP。

周边网关协议（BGP）提供有关相邻点可达性信息。

BGP可以减低带宽需求，这是因为路由选择信息是增量交换的，而不是在路由器间发送路由选择数据库信息。

BGP也提供了基于策略的算法，使网络管理者对路由选择有较多的控制权，例如对某些信息传输实行优化的能力。

域间路由选择协议（IDRP）是一种OSI无连接分组（CLNP）的OSI路由选择协议。

IDRP包含路由选择的策略，但它不大可能在Internet上代替BGP。

IDRP可用一种协议进行IP和CLNP的域间路由选择来增加对IP的支持。

距离向量路由算法(Bellman-Ford Routing Algorithm)，也叫做最大流量演算法(Ford-FulkersonAlgorithm)，其被距离向量协议作为一个算法，如RIP, BGP, ISO IDRP, NOVELL IPX。

使用这个算法的路由器必须掌握这个距离表(它是一个一维排列-“一个向量”)，它告诉在网络中每个节点的最远和最近距离。

在距离表中的这个信息是根据临近接点信息的改变而时时更新的。