更新时间：2024-07-05 23:07
metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。为了帮助选路，路由算法初始化并维护包含路径信息的路由表，路径信息根据使用的路由算法不同而不同。
在进行通信网网络设计和规划时，经常会遇到这样的问题，路径的选择和网络的方案可以有很多种，但是如何在保证所有站点都可靠地连通的前提下，选择费用最小的网络结构，这里就有一个路径优化问题。
路由算法根据许多信息来填充路由表。目的/下一跳地址对告知路由器到达该目的最佳方式是把分组发送给代表“下一跳”的路由器，当路由器收到一个分组，它就检查其目标地址，尝试将此地址与其“下一跳”相联系。路由表还可以包括其它信息。路由表比较metric以确定最佳路径，这些metric根据所用的路由算法而不同，下面将介绍常见的metric。路由器彼此通信，通过交换路由信息维护其路由表，路由更新信息通常包含全部或部分路由表，通过分析来自其它路由器的路由更新信息，该路由器可以建立网络拓扑细图。路由器间发送的另一个信息例子是链接状态广播信息，它通知其它路由器发送者的链接状态，链接信息用于建立完整的拓扑图，使路由器可以确定最佳路径。
给定连通图G=(V，X)，w(x)是定义在X上的非负函数，称w(x)是x的权。设T=(V，XT)是G的一个支撑树，定义树的权为
最小支撑树就是w(T)为最小的一颗支撑树。权值可以是距离、费用，或根据各种因素综合评定后得出的数据。
下面介绍两种最小支撑树的算法。
（1）算法一
在赋权图G中任取一个回路，然后去掉这个回路中权最大的边，如此继续进行，直到G中不再有回路为止。这时剩下的边组成的子图就是最小支撑树。此法最适合于图上操作，当图较大时，可以几个人同时在各子图上工作，比较实用，方便。
（2）算法二
这是Kruskal在1956提出的最小支撑树的算法，又称Kruskal法，具体步骤如下：设图G有n个点。
① 把赋权图G的各条边按权的递增顺序排列，如表01所示。
② 取最小权值的边作树枝。
③ 重复第2步，如果与已选边不形成回路，作为新的树枝，否则删去。
④ 至选出n－1条边结束。
图1给出了图G及根据算法二求出的最小费用网络拓扑图。
图1 算法二示例
表1的各边按权递增排列
在通信网的网络结构确定以后，选择最佳路由（用图论的术语就是选择点间最短路径），便要提到日程上来。选择最佳路由的方法很多，应用也很广。
下面介绍一种在数据通信网中常用的最佳路由的选择方法。以图2中的节点v6为例。
图2 最佳路由算法
（1）从v6点出发，画出指向各邻近节点v1，v7，v5的箭头，并在节点处，记下它们的权数。
（2）然后，从这3个邻近节点v1，v7，v5出发，向各相邻的节点画出箭头，如从v7向v3画箭头，v3节点处标上的权数，应是(v6,v7)和(v7,v3)之权数之和6。如到达某一节点的箭头有2个或2个以上，则选取最小的一个。
（3）直至找到从v6出发到达所有其他的节点为止。图2.32(b)给出了从v6到所有其他节点的最短路径。
可以用同样的步骤找出节点v1,v2,…等通向其余各节点的最短路径，编制出最小权数路由表。
在通信网中除了要求最佳路由之外，还须计算迂回路由，以便在通信网某两点间出现故障后发生拥塞时使用。
迂回路由的算法是在计算出的最佳路由上，去掉某一条或几条边，然后在剩下的图中求最佳路径，所得即为迂回路由，依次可求出第二，第三迂回路由。图3中分别给出了去掉(v6,v1)，以及同时去掉(v2,v7)、(v6,v1)的迂回路由。
图3 迂回路由