路由表的建立算法

1、路由表

1）什么是路由表

路由表是指路由器或者其他互联网网络设备上存储的一张路由信息表，该表中存有到达特定网络终端的路径，在某些情况下，还有一些与这些路径相关的度量。

2）路由表分类

（1）静态路由表

由系统管理员事先设置好固定的路由表称之为静态路由表，一般是在系统安装时就根据网络的配置情况预先设定的，它不会随未来网络结构的改变而改变。

（2）动态路由表

动态路由表是路由器根据网络系统的运行情况而自动调整的路由表。路由器根据路由选择协议（Routing Protocol）提供的功能，自动学习和记忆网络运行情况，在需要时自动计算数据传输的最佳路径。

2、路由表项

• 目的地址：用来标识IP包的目的地址或者目的网络。

• 网络掩码：与目的地址一起标识目的主机或者路由器所在的网段的地址。

pre：标识路由加入IP路由表的优先级。可能到达一个目的地有多条路由，但是优先级的存在让他们先选择优先级高的路由进行利用。

cost：路由开销，当到达一个目的地的多个路由优先级相同时，路由开销最小的将成为最优路由。

interface：输出接口，说明IP包将从该路由器哪个接口转发。

nexthop：下一跳IP地址，说明IP包所经过的下一个路由器。

3、路由表的相关算法

1）总体式路由算法。

采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。

2）分散式路由算法

采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。

距离向量路由算法，也叫做最大流量演算法，其被距离向量协议作为一个算法，如RIP就是一种分布式的基于距离向量的路由选择协议。使用这个算法的路由器必须掌握这个距离表，它告诉在网络中每个节点的最远和距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直接和它相连的邻居，行代表在网络中的所有目的地。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”)。这个在那个算法中的度量公式是跳跃的次数， 等待时间，流出数据包的数量，等等。

在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。

链路状态算法的思想是要求网络中所有参与链路状态路由协议的路由器都掌握网络的全部拓扑结构信息，并记录在路由数据库中。链路状态算法中路由数据库实质上是一个网络结构的拓扑图，该拓扑图由一个节点的集合和一个边的集合构成。在网络拓扑图中，结点代表网络中路由器，边代表路由器之间的物理链路。在网络拓扑结构图中，每一条链路上可以附加不同的属性，例如链路的状态、距离或费用等。如果没一个路由器所保存的网络拓扑结构图都是一致的，那么个路由器生成的路由表也是最佳的，不存在错误路由或循环路由。

特征一：向本自治系统中的所有路由器发送信息。这里使用的方法是洪泛法（Flooding），即路由器通过所有的输出端口向所有的相邻路由器发送信息。而每一个路由器又将此信息发往其所有的相邻的路由器（但不包括刚刚发来信息的那个路由器）。

特征二：发送的信息就是本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。所谓“链路状态”就是说明本路由器和那些路由器相邻，以及该链路的“度量”。对于OSPF，链路状态的“度量”主要用来表示费用、距离、时延、带宽等。

特征三：只有当链路状态发生改变时，路由器才用洪泛法向所有路由器发送此信息。

OSPF就是使用分布式的链路状态协议。