公开(公告)号：US06377551B1

公开(公告)日：2002-04-23

申请号：US09134924

申请日：1998-08-17

Applicant: Gang Luo ,  Kaiyuan Huang ,  Jianli Wang

Inventor： Gang Luo ,  Kaiyuan Huang ,  Jianli Wang

IPC: H04L1228

CPC classification number: H04L45/12 ,  H04L45/124 ,  H04L45/306

Abstract: A method is described for route computation in Communications Networks with multiple QoS metrics. This method takes a metric (say, cost) as an optimization target and the other metric (say, delay) as a constraint. A communication network with multiple QoS metrics associated to its links is modelled as a graph with multiple QoS metrics as weights associated to its links. The method associates constraints with nodes in the graph after generating a minimum spanning tree based at a destination node using Dijkstra's algorithm with the constraint metric as link weight. A set is populated with nodes whose path to the destination node satisfies given constraints while endeavouring to optimize another QoS metric. A path may be computed by selecting, from the set, the destination node and associated predecessor nodes through to the start node. The algorithm of the method is very efficient and its computational complexity is O(n2). This method can guarantee to find a nearly optimal path with the given constraint satisfied as long as there exists such a path.

Abstract translation: 描述了具有多个QoS度量的通信网络中的路由计算的方法。 该方法将度量（例如，成本）作为优化目标，另一个度量（例如，延迟）作为约束。 具有与其链接相关联的多个QoS度量的通信网络被建模为具有多个QoS度量作为与其链接相关联的权重的图。 该方法在使用Dijkstra算法，以约束度量为链路权重的目的地节点生成最小生成树后，将约束与图中的节点相关联。 一个集合中填充有到目的节点的路径满足给定约束的节点，同时努力优化另一个QoS度量。 可以通过从集合中选择目的地节点和相关联的前导节点到开始节点来计算路径。 该方法的算法非常有效，其计算复杂度为O（n2）。 只要存在这样的路径，该方法可以保证找到具有给定约束的几乎最优路径。