Patent ID: 7355980
Filing Date: 2008-04-08
Classification: H04L,H04Q

Abstract:
1. A method for deriving a set of efficient path costs to facilitate path selection for routing communications among a group of nodes comprising a source node and a plurality of destination nodes in a data communications networks, wherein the path costs for paths between nodes in the group are defined in the network and each path cost comprises a restrictive cost and an additive cost, the method comprising: a) recording, in a first data set, the path costs for direct paths from the source node to any of the destination nodes, each recorded cost being associated in the first data set with the node reached by the corresponding path; b) selecting a best path cost from the first data set, wherein the best path cost is determined as that comprising a best restrictive cost, or, if a plurality of the path costs comprise equal restrictive costs, a path cost having the best restrictive cost and the best additive cost; c) recording the best path cost selected in step b) in a second data set, the recorded cost being associated in the second data set with the node reached by the corresponding path; d) eliminating the cost recorded in step c) in the second data set from the first data set; e) in the first data set, recording a cumulative path costs for direct paths from the destination node reached by the path corresponding to the cost recorded in step c) to any other node in the group, each recorded cumulative path cost being associated in the first data set with the node reached by the corresponding path; f) for each node for which an associated cost was recorded in first data set in step e) comparing the costs associated with that node in the first and second data sets and eliminating from the first data set any such cost for reaching that node which has both a worse restrictive cost and a worse additive cost than any other such cost for reaching that node or any such cost for reaching that node which has an equal restrictive and a worse additive cost than any other such cost for reaching that node; and g) repeating steps b) to f) until no costs remain in the first data set after step f); whereby the resulting second data set comprises the set of efficient costs for direct paths from the source node to destination nodes in said communications network, for use in selecting paths for routing communications in said data communications network.