CN1220353C - 计算数据网络中节点的有效路径成本的方法和设备 - Google Patents

Abstract

一种为数据通信网络中的一组节点得出一组有效路径成本的方法，所述一组节点包括一个源节点和若干目的地节点，其中在网络中确定所述一组节点中节点间路径的路径成本，并且每个路径成本包括限制成本和附加成本，所述方法包括首先迭代地确定带宽较高的路径，当存在两个或多个带宽相同的路径时，选择具有与之相关的较低转接延迟的路径。

Description

计算数据网络中节点的有效路径成本的方法和设备

技术领域

本发明涉及数据通信网络中的成本(cost)，更具体地说，涉及为数据通信网络的一组节点得出一组有效路径成本(path cost)的方法、设备和计算机程序组件。

背景技术

对于不同种类的应用来说，诸如因特网之类大规模网络中的服务质量(QoS)的支持正变得越来越重要。为了确保QoS，连接最终用户的路径必须满足指定的要求。于是在QoS保证的规定中，路由判定是一项重要的考虑因素。于是，路由选择协议应知道网络中各种链路支持的通信特性。

为诸如“开放最短路径优先”(OSPF)协议之类众所周知的路由选择协议提出了QoS扩展。在“ Implementation and Performance Measurements of QoS Routing Extensions to OSPF”，Apostolopoulos et al.Proceeding of IEEE INFOCOM′99，pp.75-83，New York，March，1999中描述了这种扩展的例子。OSPF协议是链路状态路由选择协议的一个例子。众所周知，在大型网络中，这种协议不能有效工作。从而，为了可缩放性起见，OSPF网络被分成几个路由区。在 “OSPF Version2”，Moy，Internet Engineering Task Force(IETF) Request for Comments(RFC)2328，April 1998 中进一步描述了OSPF协议。

本领域中众所周知的另一种类似的路由选择协议是在 “Private Network Interface Specification，Version 1.0”，the ATM Forum， March 1996中描述的专用网络间接口(PNNI)协议。根据PNNI协议，网络被分成几群，从而形成路由层次。

为了提供全局准确的路径选择，应考虑所涉及的每个路由域(不论它是OSPF区，还是PNNI群)的通过特性。 “On Scalable QoS Routing，Performance Evaluation of Topology Aggregation”，Hao et al，Proceedings of IEEE INFOCOM′2000，Tel Aviv，Israel，March 2000和 “QoS Routing：a Precomputation Perspective”，Orda et al， Proceeding of IEEE INFOCOM′99 pp.128-136，Tel Aviv，Israel， March 2000都建议借助网络的层次组织，可显著增加路径计算效率。

“Transition Matrix Generation for Complex NodeR epresentation”，Iliadis et al，Proceedings of the IEEE ATM Workshop′99，pp489-500，Kochi，Japan，May 1999中说明的是一种利用转换矩阵表示路由域的通过特性的方法，所述转换矩阵给出路由域的每对入口-出口节点的路径成本。转换矩阵中的每一项是对应一对入口-出口节点的通过特性的最小表示(minimal representation)。可利用限制成本度量，附加成本度量，或者这两者描述通过特性(traversingcharacteristics)。只利用一种度量描述的转换特性可被看作一维。利用N种度量描述的转换特性可被看作N维。路径的附加度量是路径中所有链路的所有附加度量的和。路径的限制度量是路径中所有链路的限制度量中的最小者。附加度量的例子包括延迟和管理成本。限制度量的例子包括带宽。本领域中，通过特性的最小表示被称为有效边界(frontier)。下面简要说明计算有效边界的常规技术。可按照两种标准对这些技术分类：

计算结果：一些技术计算网络中从一个源入口-出口节点到所有其它入口-出口节点的有效边界。其它技术计算所有各对入口-出口节点之间的有效边界。要认识到属于前一类别的技术必须应用于所有的入口-出口节点。

延迟功能：一些技术只支持固定延迟功能。其它技术既可应用于固定延迟，又可应用于取决于带宽的延迟。

下述三种众所周知的算法可被用于计算最小表示：

在 “Efficient Frontier Formulation for Additive and Restrictive Metrics in Hierarchical Routing”，Bauer et al.Proceedings of the IEEE ICC′00，pp.1353-59，New Orleans，June 2000中描述的Multi-Dijkstra算法；

在 “Introduction to Algorithms”，Corment et al.the MIT Electrical Engineering and Computers Science Series，MIT Press， ISBN 0-262-031412-8，1989中，在 “On a Routing Problem”，Bellman， Quarterly of Applied Mathematics，Vol.16，No.1，pp.87-90，1958中，以及在 “Flows in Networks”，Ford Jr.et al.Princeton University Press， 1962中描述的Bellman-Ford算法；和

在 “Algorithm 97(Shortest Path)”，Floyd，Communications of the ACM，Vol.5，No.6，1965中描述的Floyd-Warshall算法。

所有这三种算法都适用于恒定延迟。但是，只有Bellman Ford和Floyd Warshall算法能够处理取决于带宽的延迟。另外，只有Multi-Dijkstra和Bellman-Ford算法能够为单源节点对所有节点(onesource to all nodes)解决有效边界问题。对于计算有效边界来说，Multi-Dijkstra和Floyd-Warshall一般比Bellman-Ford算法简单。于是应根据应用选择这些算法。例如，如果只存在少数入口-出口顶点，并且只考虑恒定延迟，则Multi-Dijkstra算法优于Floyd-Warshall算法。

一般来说，计算从一个节点到路由域的所有其它节点的有效边界的常规技术计算复杂，应用有限。希望提供一种更简单的计算这种有效边界的方法。另外，希望提供一种解决“单源节点对所有节点”问题的方法。

发明内容

根据本发明，提供一种为数据通信网络中的一组节点得出一组有效路径成本的方法，所述一组节点包括一个源节点和若干目的地节点，其中在网络中确定所述一组节点中节点间路径的路径成本，并且每个路径成本包括限制成本和附加成本，所述方法包括：

a)把从源节点到任意目的地节点的直接路径的路径成本记录在第一数据集合中，在第一数据集合中，每个记录的成本与通过对应路径到达的节点相关；

b)从第一数据集合中选择最佳路径成本，其中该最佳路径成本被确定为包含最佳限制成本的路径成本，或者，如果若干路径成本包括相同的限制成本，则最佳路径成本为具有最佳限制成本和最佳附加成本的路径成本；

c)把在步骤b)中选择的最佳路径成本记录在第二数据集合中，在第二数据集合中，记录的成本与通过对应路径到达的节点相关；

d)从第一数据集合中除去在步骤c)中记录在第二数据集合中的成本；

e)在第一数据集合中，记录从通过对应于步骤c)中记录的成本的路径到达的目的地节点到该组节点中除源节点之外的任意其它节点的直接路径的累积路径成本；在第一数据集合中，每个记录的累积路径成本与通过对应路径到达的节点相关；

f)对于在步骤e)中，把其相关成本记录在第一数据集合中的每个节点，比较第一和第二数据集合中与该节点相关的成本，并从第一数据集合除去和到达该节点的任意其它成本相比具有较差限制成本和较差附加成本的任意到达该节点的成本，或者除去和到达该节点的任意其它成本相比具有相同限制成本和较差附加成本的任意到达该节点的成本；

g)重复步骤b)-f)，直到在步骤f)之后，在第一数据集合中不留下任何成本为止；

从而所得到的第二数据集合包括该组有效路径成本。

这提供了一种更简便并且更快速的计算有效边界的方法。另外，该方法简化了“单源节点对所有节点”问题的求解。此外，该方法既适合于恒定延迟，又适合于取决于带宽的延迟。

每个限制成本最好包括表示对应路径的带宽的数值；最佳限制成本是表示最大带宽的成本。每个附加成本最好包括表示与对应路径相关的转接延迟的数值，最佳附加成本是表示最小转接延迟的成本。至少一个路径可包括若干链路和至少一个中间节点。

本发明还延伸到一种包括计算机程序代码装置的计算机程序组件，所述计算机程序代码当被加载到数据处理系统的处理器中时，配置处理器，以便执行如前所述的得出一组有效路径成本的方法。

从另一方面看本发明，提供一种得出数据通信网络中的一组节点的一组有效路径成本的设备，所述一组节点包括一个源节点和若干目的地节点，其中在网络中确定该组节点中节点间路径的路径成本，每个路径成本包括限制成本和附加成本，该设备包括用于保存路径成本的第一数据集合和第二数据集合的存储器和控制装置，所述控制装置包括：

a)第一记录装置，用于把从源节点到任意目的地节点的直接路径的路径成本记录在第一数据集合中，在第一数据集合中，每个记录的成本与通过对应路径到达的节点相关；

b)选择装置，用于从第一数据集合中选择最佳路径成本，其中该最佳路径成本被确定为包含最佳限制成本的路径成本，或者如果多个路径成本包括相同的限制成本，则为具有最佳限制成本和最佳附加成本的路径成本；

c)第二记录装置，用于把选择装置选择的最佳路径成本记录在第二数据集合中，在第二数据集合中，记录的成本与通过对应的路径到达的节点相关；

d)用于从第一数据集合中除去第二记录装置中记录在第二数据集合中的成本的装置；

e)第三记录装置，用于在第一数据集合中，记录从通过对应于第二记录装置中记录的成本的路径到达的目的地节点到该组节点中除源节点之外的任意其它节点的直接路径的累积路径成本，在第一数据集合中，每个记录的累积路径成本与通过对应路径到达的节点相关；

f)除去装置，用于对在第一数据集合中记录了相关的累积路径成本的每个节点，比较第一数据集合和第二数据集合中与该节点相关的成本，从第一数据集合中除去和到达该节点的任意其它成本相比具有较差限制成本和较差附加成本的任意到达该节点的成本，或者除去和到达该节点的任意其它成本相比具有相同限制成本和较差附加成本的任意到达该节点的成本；

g)重复装置，用于重复b)至f)中所述各装置的操作，直到在第一数据集合中不留下任何成本为止；所得到的第二数据集合包括该组有效路径成本。

本发明延伸到包括分别连接数据通信网络的路径的若干端口，以及如前所述得出一组有效路径成本的设备的数据连网设备。本发明还延伸到数据网络，包含通过若干路径互连的若干节点，至少一个节点包含这样的数据连网设备。

附图说明

下面将参考附图，举例说明本发明的优选实施例，其中：

图1图解说明恒定延迟路径的有效边界的一个例子；

图2a是具有四个入口-出口节点的例证网络的简化图；

图2b图解说明了对应于群聚网络的转换矩阵；

图3-13是对应于该网络的定向图；

图14图解说明了从网络的节点0到节点1的有效边界；

图15图解说明了从网络的节点0到节点2的有效边界；

图16图解说明了从网络的节点0到节点3的有效边界；

图17是对应于根据本发明的得出一组有效路径成本的方法的例子的流程图；

图18是具体体现本发明的数据连网设备的方框图。

具体实施方式

在继续说明本发明之前，定义和解释相关术语及措辞。

这里，措辞“限制成本”用于描述随链路的大小或特征，例如带宽而变化的成本。限制成本C可被定义成C＝Max-带宽，或者定义成C＝1/带宽。根据限制成本的定义，路径的最弱链路确定限制成本。与限制成本相反的是附加成本。附加成本取决于，例如链路的延迟。

这里，单词“节点”或者“顶点”用作路由器、交换机、桥接器、桥式路由器、集线器，以及通信网络中传送或接收信息的任意其它连网设备的类属术语。

可借助定向图模拟网络。使用下述约定：

网络的节点被称为定向图的顶点。

两个网络节点之间的链路被称为定向图的两个顶点之间的直接路径或者棱边(edge)。

假定G(V，E)为代表指定时刻时的网络的定向图。V是一组顶点，E是一组定向棱边。于是对于所有v_i，v_j∈V(如果v_i和v_j是连接的)，存在棱边 $v_i\underset{\→}{{\mathrm{\ϵ}}_{v_i,v_j}}{v}_j\∈E.$ 可利用多个平行棱边连接顶点。连接两个顶点v_i和v_j的一组棱边被表示成 $E_{v_i,v_j}\stackrel{\mathrm{\Δ}}{=}\{{\mathrm{\ϵ}}_{v_i,v_j}^0,{\mathrm{\ϵ}}_{v_i,v_j}^1,...,{\mathrm{\ϵ}}_{v_i,v_j}^n\}.$ 符号ε_vi，vj代表连接顶点v_i和v_j的任意棱边。

假定s和t为定向图G(V，E)的两个顶点。假定P_s，t为连接s和t的一组路径

如果不存在从s到t的路径，则P_s，t＝φ。长度‖ρ‖＝n的路径ρ∈P_s，t是一系列{ε_v0，v1，ε_v1，v2，ε_vn-1，vn)的n条棱边，从而v₀＝s

v_n＝t

${\mathrm{\ϵ}}_{v_i,v_{i=1}}\∈E_{v_i,v_{i=1}}\∀i\∈[0,...,n-1].$

如果在v＝v_i或v＝v_i+1的情况下，存在棱边 ${\mathrm{\ϵ}}_{v_i,v_{i=1}}\∈\mathrm{\ρ},$ 则认为顶点v是路径ρ的一部分。

关于路径和棱边的度量提供和网络中的可用资源有关的信息。现在定义可用带宽及转接延迟的度量。但是，要认识到这里给出的意见适用于符合这里提供的定义的任意限制度量和附加度量。

对于棱边 ${\mathrm{\ϵ}}_{v_i,v_j}\∈E,$ 可用带宽将用 $B\left({\mathrm{\ϵ}}_{v_i,v_j}\right){\∈R}^{+}$ 表示。可用带宽被认为是限制性的，因为路径的可用带宽是该路径通过的棱边的可用带霓中的最小者。对于长度为n的从s到t的可行路径ρ来说，可用带宽为

$B\left(\mathrm{\ρ}\right)=\underset{\mathrm{\δ}\∈\mathrm{\ρ}}{\min }\left\{B\left(\mathrm{\ϵ}\right)\right\}---\left(1\right)$

假定，棱边的转接延迟是被请求带宽b的函数。从而，对于棱边ε∈E和被请求带宽b来说，转接延迟由D(ε，b)∈R⁺给出。如果b＞B(ε)，则D(ε，b)＝∞。转接延迟被认为是累积的，因为路径的转接延迟是通过的棱边的转接延迟之和。对于长度为n的从s到t的可行路径来说，转接延迟为

$D(\mathrm{\ρ},b)=\underset{\mathrm{\ϵ}\∈\mathrm{\ρ}}{\mathrm{\Σ}}D(\mathrm{\ϵ},b)---\left(2\right)$

对于棱边ε∈ρ，如果被请求带宽b＞B(ε)，则D(ρ，b)＝∞。否则，D(ρ，b)有限。

下面，定义一对入口-出口顶点的二维转换特征。转换特征的维是带宽和延迟。随后检查相对于一组入口-出口顶点的扩展。

研究前面提及的代表一个路由域的定向图G(V，E)。假定s， t∈V为两个入口-出口顶点。做出路由判定所关心的从s到t的通过(traversing)度量是最大可用带宽B^max，以及被请求带宽b的最大转接延迟函数D^eff(b)。这两者都取决于连接s和t的一组路径P_s，t。具体地说，

$B_{s,t}^{\max }\stackrel{\mathrm{\Δ}}{=}\underset{\mathrm{\ρ}\∈P_{s,t}}{\max }\left(B\left(\mathrm{\ρ}\right)\right),$ 和(3)

$D_{s,t}^{\mathrm{eff}}\left(b\right)\stackrel{\mathrm{\Δ}}{=}\underset{{\mathrm{\ρ}\∈P}_{s,t}}{\min }\left\{D(\mathrm{\ρ},b)\right\}---\left(4\right)$

根据可用带宽和转接延迟的定义，得出结论，对于 $b\&le;B_{s,t}^{\max },$ 则 $D_{s,t}^{\mathrm{eff}}\left(b\right)<\&infin;,$ 并且对于 $b>B_{s,t}^{\max },$ 则 $D_{s,t}^{\mathrm{eff}}\left(b\right)=\&infin;.$ 于是，由于 代表对于每个带宽，具有最小延迟的路径，因此

足以描述入口-出口对s，t的通过度量。

还确定适用带宽及从s到t的转接延迟的有效边界。根据定义，

取决于路径组P_s，t。但是，只有路径组P_s，t的子集对有效边界产生影响。下面把该子集称为s和t的有效路径或者

$P_{s,t}^E\stackrel{\mathrm{\&Delta;}}{=}\left\{{\mathrm{\&rho;}\&Element;P}_{s,t}\right|\&Exists;:b(\mathrm{\&rho;},b)<\&infin;\&And;D(\mathrm{\&rho;},b)=D_{s,t}^{\mathrm{eff}}\left(b\right)\}---\left(5\right)$

有效边界可被看成一系列的分段，每一段对应于路径的传输延迟函数

$D_{s,t}^{\mathrm{eff}}\left(b\right)=\left\{\begin{array}{c}D({\mathrm{\&rho;}}_1,b)\&ForAll;b\&Element;(b_0,b_1)\\ D({\mathrm{\&rho;}}_2,b)\&ForAll;b\&Element;(b_1,b_2)\\ \&CenterDot;\\ \&CenterDot;\\ D({\mathrm{\&rho;}}_n,b)\&ForAll;b\&Element;(b_{n-1},b_n)\\ \&infin;\&ForAll;b>b_n\end{array}\right\}---\left(6\right)$

其中 $b_n=B_{s,t}^{\max },$ b₀＝0，在i∈[1，n]的情况下，如下给出ρ_i： ${\mathrm{\&rho;}}_i=P_{s,t}^E,$ 从而 $D({\mathrm{\&rho;}}_i,b)=D_{s,t}^{\mathrm{eff}}<mrow>\; </mrow>\left(b\right)\&ForAll;b\&Element;[b_{i-1},b_i].---\left(7\right)$

注意ρ_i可以不是唯一的，因为可能存在满足等式(7)的多个路径。另外，对于一些形式的延迟函数来说，可能发生单一路径影响多个分段的情况。例如，在等式(6)中，对于一些i≠j，有可能ρ_i≡ρ_j。

现在参见图1，图中举例说明了恒定延迟路径的有效边界的一个例子。这些路径是D(ρ，b)与b无关，从而可被写成D(ρ)的路径。本例中，包括四个路径。这些路径的转接延迟-带宽特征被表示成有效边界上的黑点。这些有效边界的可用带宽和转接延迟完整地确定 阴影区还包括不是 一部分的无效解答(solution)，这些无效解答被表示成白点。对于恒定延迟路径，能够如下定义可实现的最小延迟

$D_{s,t}^{\min }=\underset{{\mathrm{\&rho;}\&Element;P}_{s,t}^B}{\min }\{D\left(\mathrm{\&rho;}\right)---\left(8\right)$

一般情况下，对于被请求的带宽 不可能实现

只有当路径 $\mathrm{\&rho;}\&Element;P_{s,t}^E$ 的延迟D(ρ)都相等时，才可能实现 例如，如果 只包含单一路径，则情况就是这样。于是，对于任意网络，如果 $D_{s,t}^{\mathrm{eff}}\left(B_{s,t}^{\max }\right)=D_{s,t}^{\min },$ 则存在“单一路径解答”。

现在假定定向图包括称为R₀...，R_N-1∈V的N个入口-出口顶点。对于每对入口-出口顶点R_i，R_j，存在一个有效边界

该组所有有效边界完整地确定网络的通过度量。用称为转换矩阵的矩阵给出任意一对入口-出口顶点之间的所有有效边界的代数表达。可如下规定该转换矩阵：

转换矩阵是基础路由域的布局的代数表示。在它完整保持关于带宽和延迟度量的通过特性的意义上，它是路由域的准确表示。

如前所述，本发明解决的问题涉及转换矩阵的计算。具体地说，该问题涉及转换矩阵每一项的计算。参考图2a，研究包含四个入口-出口顶点0、1、2和3的例证网络。参见图2b，每一项是每对入口-出口顶点之间的有效边界。

在本发明的一个优选实施例中，并行地并且以“降序”方式迭代确定对应于各个顶点的有效边界。“降序”意指首先找出带宽较大的有效边界点，在具有相同带宽的点之中，首先找出延迟较小的点。通过考虑有效边界的图形表示(如前所述，延迟沿y轴，带宽沿x轴)，这种方法能够从右(较高的带宽)向左(较低的带宽)有效地清除有效边界。下面简要地详细说明根据本发明确定有效边界的程序的优选例子。不过，预先给出一些预备定义。

预备定义

假定G(V，E)为代表指定时刻时的网络的图。V是一组顶点，E是一组定向棱边。于是对于所有v_i，v_j∈V(如果v_i和v_j是连接的)，存在棱边 $v_i\underset{\&RightArrow;}{{\mathrm{\&epsiv;}}_{v_i,v_j}}{v}_j\&Element;E.$ 可利用多个平行棱边连接顶点。连接两个顶点坪和v_i的一组棱边被表示成 $E_{v_i,v_j}\stackrel{\mathrm{\&Delta;}}{=}\{{\mathrm{\&epsiv;}}_{v_i,v_j}^0,{\mathrm{\&epsiv;}}_{v_i,v_j}^1,...,{\mathrm{\&epsiv;}}_{v_i,v_j}^n\}.$ 符号ε_vi，vj代表连接顶点v_i和v_j的任意棱边。对于棱边 ${\mathrm{\&epsiv;}}_{v_i,v_j}\&Element;E,$ 其用带宽和延迟来表示的度量(成本)将由 $C\left({\mathrm{\&epsiv;}}_{v_i,v_j}\right)\stackrel{\mathrm{\&Delta;}}{=}(B\left({\mathrm{\&epsiv;}}_{v_i,v_j}\right),D\left({\mathrm{\&epsiv;}}_{v_i,v_j}\right)).$ 表示，其中B(ε_vi，vj)和D(ε_vi，vj)分别表示与该棱边相关的可用带宽和延迟。假定这些度量是非负实数。换句话说， $B\left({\mathrm{\&epsiv;}}_{v_i,v_j}\right)\&Element;R^{+},$ 并且 $D\left({\mathrm{\&epsiv;}}_{v_i,v_j}\right)\&Element;R^{+}.$

如下比较两个成本C_i＝(B_i，D_i)和C_j＝(B_j，D_j)：

当且仅当B_i＝B_j，并且D_i＝D_j时，成本C_i等于C_j(C_i＝C_j)。否则，成本C_i不等于C_j(C_i≠C_j)。

当且仅当B_i≥B_j，D_i≤D_j，并且(C_i≠C_j)时，成本C_i好于C_j，或者说，成本C_j差于C_i。

当且仅当B_k＝nin(B_i，B_j)并且D_k＝D_i+D_j时，成本C_k扩大成本C_i和C_i(C_k＝ext(C_i，C_i))。

过程

假定v₀是要从其计算有效边界的源顶点。假定r_i，i＝1...N-1为从v₀到达顶点v_i的成本列表。假定f_i，i＝1...N-1为与顶点v_i相关的有效边界。假定 和 分别为包含对应列表的数据集，即 和 这些数据集可被排列成表格。

在继续说明之前，给出下述辅助定义：

i为迭代计数值；

v_m(i)为第i次迭代的标记顶点；

E_vj是从顶点v_j发出的一组棱边；

r_j是从v₀到达顶点v_i的成本列表；

f_j是包含和顶点v_j对应的有效边界的列表；

下面是呈一系列规则1)-3)形式的过程的伪代码表示。初始化：

i＝1

m(1)＝0

f₀(∞，0)

第i步迭代：

1)对于集合E_vm(i)中的每个棱边ε_vm(i)，vj， do

a)根据f_m(i)列表的最后一项和成本C(ε_vm(i)，vj)，计算扩展路径 $v_0\&RightArrow;v_{m\left(i\right)}\stackrel{{\mathrm{\&epsiv;}}_{v_{m\left(i\right)},v_j}}{\&RightArrow;}{v}_j$ 的成本C_j＝(B_j，D_j)，即， $C_j=\mathrm{ext}(f_{m\left(i\right)},C\left({\mathrm{\&epsiv;}}_{v_{m\left(i\right)},v_j}\right)).$

b) if等于或差于列表f_j的任意项， then丢弃C_j，

c) else ifC_j等于或差于列表r_j的任意项， then丢弃C_j，

     else do

d)通过使列表继续按照带宽，以及延迟(对于相同带宽的项)分类，把C_j输入列表r_j。

e)丢弃列表r_j的差于C_j的任意项。

     done

2) if

数据集为空， then STOP。

3) else do

a)选择 数据集合的最佳项，假定包含在列表r_k中。最佳项可被认为是具有最大带宽的一项，并在存在多项的情况下，具有最低延迟的一项。根据另一标准，例如中继段计数，或者随意地打破剩余线路。

b)从列表r_k中除去该项，并将其放入列袁f_k。

c)增大计数值：i＝i+1。

d)设置m(i)＝k(从而v_m(i)＝v_k)

done返回步骤。

例子

参见图3，现在说明具体体现本发明，确定从顶点0到例证的四节点网络的剩余顶点1、2和3的有效边界的方法的例子。要认识到本发明同样适用于具有四个以上或者四个以下节点的网络。

步骤1：

现在参见图4，该方法从顶点0开始，并且考虑从顶点0发出的所有棱边。三个棱边分别提供与顶点1、2和3的连接。目前不存在与顶点0相关的成本。于是，按照上述规则1d)把相对于顶点1、2和3的相应棱边的成本插入 数据集合中。

在

数据集合中，用带宽表示的最佳成本是到顶点3的成本：9，5。随后按照规则3b)，把该成本从 数据集合转移为顶点3的有效边界。

   

该方法现在转移到具有相关成本9，5的顶点3。

步骤2：

现在参见图5，顶点3具有去往顶点1和2的两个棱边。图5中表示了由与设置在

数据集合中的顶点3(9，5)相关的成本扩展的这些棱边的成本。由于在

数据集合中仍然不存在关于顶点1和2的项目，因此这些成本被输入

数据集合。

最宽的带宽值对应于顶点2：8，10。从 数据集合把该值转移为顶点2的有效边界。

   

该方法现在转移到具有相关成本8，10的顶点2。

步骤3：

现在参见图6，顶点2具有去往顶点1和3的两个棱边。图6中表示了由与设置在

数据集合中的顶点2(8，10)相关的成本扩展的这些棱边的成本。到达顶点l的成本等于(6，12)，它差于r₁列表中的成本(6，9)，于是，按照规则1c)，该成本被丢弃。到达顶点3的成本等于(1，11)，它差于f₃列表中的成本(9，5)。于是，按照规则1b)，该成本被丢弃。最宽的带宽值对应于顶点2：7，6。

从 数据集合把该值转移为顶点2的有效边界。

   

该方法转到具有相关成本7，6的顶点2。

步骤4：

参见图7，顶点2具有去往顶点1和3的两个棱边。图7中表示了由与设置在 数据集合中的顶点2(7，6)相关的成本扩展的这些棱边的成本。到达顶点1的成本等于(6，8)，它既不等于又不差于r₁的任意项。于是，按照规则ld)，该成本被输入 数据集合。但是，项目(6，9)差于(6，8)。于是，按照规则1e)丢弃项目(6，9)。到达顶点3的成本等于(1，7)，它差于f₃列表中的成本(9，5)。于是，按照规则1b)，该成本被丢弃。

最宽的带宽值对应于顶点1：6，8。从 数据集合把该值转移为顶点1的有效边界。

   

该方法现在转到具有相关成本6，8的顶点1。

步骤5：

现在参见图8，顶点1具有去往顶点2和3的两个棱边。到达顶点2的成本等于(2，9)，它差于f₂列表中的成本(7，6)。于是，按照规则1b)，该成本被丢弃。到达顶点3的成本等于(3，11)，它差于f₃列表中的成本(9，5)。于是，按照规则1b)，该成本被丢弃。

最宽的带宽值对应于顶点1。从

数据集合把该值转移为顶点1的有效边界。

   

该方法现在转到具有相关成本4，1的顶点1。

步骤6：

参见图9，顶点1具有去往顶点2和3的两个棱边。到达顶点2的成本等于(2，2)，它既不等于又不差于f₂的任意项。于是，按照规则1d)，该成本被输入 数据集合。到达顶点3的成本等于(3，4)，它既不等于又不差于f₃的任意项。于是，按照规则1d)，该成本被输入

数据集合。

最宽的带宽值对应于顶点3：3，4。从 数据集合把该值转移为有效边界。

   

该方法现在转到具有相关成本3，4的顶点3。

步骤7：

现在参见图10，顶点3具有去往顶点1和2的两个棱边。到达顶点1的成本等于(3，8)，它差于f₁列表中的成本(4，1)。于是，按照规则1b)，该成本被丢弃。但是，到达顶点2的成本等于(3，5)，它既不等于又不差于f₂或r₂的任意项。于是，按照规则1d)，该成本被输入 数据集合。

最宽的带宽值对应于顶点2：3，5。从 数据集合把该值转移为顶点2的有效边界。

   

该方法现在转到具有相关成本3，5的顶点2。

步骤8：

参见图11，顶点2具有去往顶点1和2的两个棱边。到达顶点1的成本等于(3，7)，它差于f₁列表中的成本(4，1)。于是，按照规则1b)，该成本被丢弃。到达顶点3的成本等于(1，6)，它差于f₃列表中的成本(3，4)。于是，按照规则1b)，该成本被丢弃。

最宽的带宽值对应于顶点2：2，2。从

数据集合把该值转移为顶点2的有效边界。

   

现在该方法转到具有相关成本2，2的顶点2。

步骤9

现在参见图12，顶点2具有去往顶点1和3的两个棱边。到达顶点1的成本等于(2，4)，它差于f₁列表中的成本(4，1)。于是，按照规则1b)，该成本被丢弃。但是，到达顶点3的成本等于(1，3)，它既不等于又不差于f₃列袁中的任意项。于是，按照规则1d)，该成本被输入 数据集合。

最宽的带宽值对应于顶点3：1，3。从 数据集合把该值转移为顶点3的有效边界。

   

该方法转到具有相关成本1，3的顶点3。

步骤10

现在参见图13，顶点3具有去往顶点1和2的两个棱边。到达顶点1的成本等于(1，7)，它差于f₁列表中的成本(4，1)。于是，按照规则1b)，该成本被丢弃。到达顶点2的成本等于(1，4)，它差于f₂列表中的成本(2，2)。于是，按照规则lb)，该成本被丢弃。

由于在 数据集合中没有留下其它项目，因此按照规则2)结束该方法。

最终结果：

从顶点0到顶点1、2、3的有效边界如下：

图14-16分别图解说明了从顶点0到顶点1、2和3的有效边界。

现在参见图17，在本发明的一个优选实施例中，提供一种包含计算机程序代码的计算机程序组件，所述计算机程序代码当被加载到数据处理系统的处理器中时，配置处理器执行得出数据通信网络中的一组节点的一组有效路径成本的方法，所述一组节点包括一个源节点和若干目的地节点，其中在网络中确定该组节点中节点间路径的路径成本，每个路径成本包括诸如表示可用带宽的数值之类的限制成本和诸如表示转接延迟的数值之类的附加成本。

该方法包括在步骤10，把从源节点到任意目的地节点的直接路径的路径成本记录在数据处理系统的存储器中的第一数据集合中。在第一数据集合中，每个记录的成本与通过对应路径到达的节点相关。

在步骤20，从第一数据集合中选择最佳路径成本。该最佳路径成本被确定为包含最佳限制成本的路径成本，或者如果若干路径成本包括相同的限制成本，则为具有最佳限制成本和最佳附加成本的路径成本。例如，如果限制成本是表示带宽的数值，则最佳限制成本是表示最大带宽的成本。类似地，如果附加成本是表示转接延迟的数值，则最佳附加成本是表示最小转接延迟的成本。

在步骤30，把在步骤20中选择的最佳路径成本记录在数据处理系统的存储器中的第二数据集合中。在第二数据集合中，记录的成本与通过对应的路径到达的节点相关。

在步骤40，从第一数据集合中除去在步骤30中记录在第二数据集合中的成本。这种除去可涉及删除、标记或者把该成本排除在考虑范围之外的任意其它操作。

在步骤50，从通过对应于步骤30中记录的成本的路径到达的目的地节点到该组节点中的任意其它节点的直接路径的累积路径成本被记录在第一数据集合中。在第一数据集合中，每个记录的累积路径成本与通过对应路径到达的节点相关。

在步骤60，对于在步骤50中，把其相关成本记录在第一数据集合中的每个节点，比较第一和第二数据集合中与该节点相关的成本。从第一数据集合除去和到达该节点的任意其它成本相比，到达该节点的具有较差限制成本和较差附加成本的任意成本，或者和到达该节点的任意其它成本相比，到达该节点的具有相同限制成本和较差附加成本的任意成本。

在步骤70，重复步骤20-60，直到在步骤60之后，在第一数据集合中不留下任何成本。在步骤80，所得到的第二数据集合包括该组有效成本。换句话说，该组有效成本包括源节点的有效边界。要认识到数据处理系统可以是路由器、交换机、桥接器、桥式路由器、集线器、或者在通信网络中传送或接收信息的任意其它网络连网设备。

现在参见图18，在本发明的另一实施例中，提供一种数据连网设备100，所述数据连网设备100包括连接数据通信网络170的输入/输出(I/O)端口110，与I/O端口110耦接的处理器120，和与处理器耦接的存储器130。存储器包括分配的存储第一数据集合140的空间，分配的存储第二数据集合150的空间和控制逻辑程序代码160。操作上，数据连网设备得出数据通信网络中包括源节点和若干目的地节点的一组节点的一组有效路径成本。数据处理设备可包括数据通信网络的源节点。在网络中确定该组节点中节点之间路径的路径成本，并且每个路径成本包括限制成本和附加成本。操作上，控制逻辑160配置处理器，以便：

a)把从源节点到任意目的地节点的直接路径的路径成本记录在第一数据集合140中，在第一数据集合中，每个记录的成本与通过对应路径到达的节点相关；

b)从第一数据集合140中选择最佳路径成本，其中该最佳路径成本被确定为包含最佳限制成本的路径成本，或者如果若干路径成本包括相同的限制成本，则为具有最佳限制成本和最佳附加成本的路径成本；

c)把在步骤b)中选择的最佳路径成本记录在第二数据集合150中，在第二数据集合150中，记录的成本与通过对应的路径到达的节点相关；

d)从第一数据集合140中除去在步骤c)中记录在第二数据集合150中的成本；

e)在第一数据集合140中，记录从通过对应于步骤c)中记录的成本的路径到达的目的地节点到该组节点中的任意其它节点的直接路径的累积路径成本，每个记录的累积路径成本与通过对应路径到达的节点相关；

f)对于在步骤e)中，把其相关成本记录在第一数据集合中的每个节点，比较第一数据集合140和第二数据集合150中与该节点相关的成本，从第一数据集合140中除去和到达该节点的任意其它成本相比，到达该节点的、具有较差限制成本和较差附加成本的任意成本，或者除去和到达该节点的任意其它成本相比，到达该节点的、具有相同限制成本和较差附加成本的任意成本；和。

g)重复步骤b)-f)，直到在步骤f)之后，在第一数据集合中不留下任何成本为止。

所得到的第二数据集合包括该组有效成本。虽然，在前面参考图18说明的本发明的实施例中，控制逻辑160是计算机程序代码，不过要认识到，在本发明的其它实施例中，至少可利用硬连线逻辑电路部分实现控制逻辑。另外要认识到，至少一个路径可包括若干链路和至少一个中间节点。

总之，在前面说明的本发明的优选实施例中，为数据通信网络中包括源节点和若干目的地节点的一组节点得出一组有效路径成本，其中在网络中确定该组节点中节点间路径的路径成本，每个路径成本包括限制成本和附加成本，包括首先迭代识别带宽较高的路径，并且当存在两个或多个带宽相同的路径时，选择具有与其相关的较低转接延迟的路径。

Claims (11)

1、一种为数据通信网络中的一组节点得出一组有效路径成本的方法，所述一组节点包括一个源节点和多个目的地节点，其中在网络中确定所述一组节点中节点间路径的路径成本，并且每个路径成本包括限制成本和附加成本，所述方法包括：

a)把从源节点到任意目的地节点的直接路径的路径成本记录在第一数据集合中，在第一数据集合中，每个记录的成本与通过对应路径到达的节点相关；

b)从第一数据集合中选择最佳路径成本，其中该最佳路径成本被确定为包含最佳限制成本的路径成本，或者，如果多个路径成本包括相同的限制成本，则最佳路径成本为具有最佳限制成本和最佳附加成本的路径成本；

c)把在步骤b)中选择的最佳路径成本记录在第二数据集合中，在第二数据集合中，记录的成本与通过对应路径到达的节点相关；

d)从第一数据集合中除去在步骤c)中记录在第二数据集合中的成本；

e)在第一数据集合中，记录从通过对应于步骤c)中记录的成本的路径到达的目的地节点到该组节点中除源节点之外的任意其它节点的直接路径的累积路径成本；在第一数据集合中，每个记录的累积路径成本与通过对应路径到达的节点相关；

f)对于在步骤e)中，把其相关成本记录在第一数据集合中的每个节点，比较第一和第二数据集合中与该节点相关的成本，并从第一数据集合除去和到达该节点的任意其它成本相比具有较差限制成本和较差附加成本的任意到达该节点的成本，或者除去和到达该节点的任意其它成本相比具有相同限制成本和较差附加成本的任意到达该节点的成本；

g)重复步骤b)-f)，直到在步骤f)之后，在第一数据集合中不留下任何成本为止；

从而所得到的第二数据集合包括该组有效路径成本。

2、按照权利要求1所述的方法，其中每个限制成本包括表示对应路径的带宽的数值；最佳限制成本是表示最大带宽的成本。

3、按照权利要求1或2所述的方法，其中每个附加成本包括表示与对应路径相关的转接延迟的数值，最佳附加成本是表示最小转接延迟的成本。

4、按照权利要求1或2所述的方法，其中至少一个路径包括多个链路和至少一个中间节点。

5、按照权利要求3所述的方法，其中至少一个路径包括多个链路和至少一个中间节点。

6、一种得出数据通信网络中的一组节点的一组有效路径成本的设备，所述一组节点包括一个源节点和多个目的地节点，其中在网络中确定该组节点中节点间路径的路径成本，并且每个路径成本包括限制成本和附加成本，该设备包括用于保存路径成本的第一数据集合和第二数据集合的存储器和控制装置，所述控制装置包括：

a)第一记录装置，用于把从源节点到任意目的地节点的直接路径的路径成本记录在第一数据集合中，在第一数据集合中，每个记录的成本与通过对应路径到达的节点相关；

b)选择装置，用于从第一数据集合中选择最佳路径成本，其中该最佳路径成本被确定为包含最佳限制成本的路径成本，或者如果多个路径成本包括相同的限制成本，则为具有最佳限制成本和最佳附加成本的路径成本；

c)第二记录装置，用于把选择装置选择的最佳路径成本记录在第二数据集合中，在第二数据集合中，记录的成本与通过对应的路径到达的节点相关；

d)用于从第一数据集合中除去第二记录装置中记录在第二数据集合中的成本的装置；

e)第三记录装置，用于在第一数据集合中，记录从通过对应于第二记录装置中记录的成本的路径到达的目的地节点到该组节点中除源节点之外的任意其它节点的直接路径的累积路径成本，在第一数据集合中，每个记录的累积路径成本与通过对应路径到达的节点相关；

f)除去装置，用于对在第一数据集合中记录了相关的累积路径成本的每个节点，比较第一数据集合和第二数据集合中与该节点相关的成本，从第一数据集合中除去和到达该节点的任意其它成本相比具有较差限制成本和较差附加成本的任意到达该节点的成本，或者除去和到达该节点的任意其它成本相比具有相同限制成本和较差附加成本的任意到达该节点的成本；

g)重复装置，用于重复b)至f)中所述各装置的操作，直到在第一数据集合中不留下任何成本为止；所得到的第二数据集合包括该组有效路径成本。

7、按照权利要求6所述的设备，其中每个限制成本包括表示对应路径的带宽的数值；最佳限制成本是表示最大带宽的成本。

8、按照权利要求6或7所述的设备，其中每个附加成本包括表示与对应路径相关的转接延迟的数值，最佳附加成本是表示最小转接延迟的成本。

9、按照权利要求6或7所述的设备，其中至少一个路径包括多个链路和至少一个中间节点。

10、一种数据连网设备，包括用于分别连接到数据通信网络的路径的多个端口，以及与路径耦接、如权利要求6-9任一所述的得出一组有效路径成本的设备。

11、一种数据网络，包含通过多个路径互连的多个节点，至少一个节点包含如权利要求10中所述的数据连网设备。

Images