Costs in data networks
AssigneeInternational Business Machines Corporation
InventorsDaniel Bauer, John N. Daigle, Ilias Iliadis, Paolo Scotton
Life of this patent
Estimating the term…
Abstract
A method for deriving a set of efficient path costs for 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, comprises iteratively identifying the paths of higher bandwidth first and, when two or more paths of equal bandwidth are encountered, selecting the path having a lower transit delay associated therewith.
Claims11
A method for deriving a set of efficient path costs for 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 the best path cost from the first data set, wherein the best path cost is determined as that comprising the best restrictive cost, or, if a plurality of the path costs comprise equal restrictive costs, the or 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 the 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.
A method as claimed in any preceding claim, wherein at least one of the paths comprises a plurality of links and at least one intermediate node.
Apparatus for deriving a set of efficient path costs for 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 apparatus comprising memory for storing first and second data sets of the path costs and control logic configured to:
- a) record, in the 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) select the best path cost from the first data set, wherein the best path cost is determined as that comprising the best restrictive cost, or, if a plurality of the path costs comprise equal restrictive costs, the or a path cost having the best restrictive cost and the best additive cost;
- c) record the best path cost selected in step b) in the second data set, the recorded cost being associated in the second data set with the node reached by the corresponding path;
- d) eliminate the cost recorded in step c) in the second data set from the first data set;
- e) in the first data set, record the 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) compare 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) repeat 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.
Dependencies are inferred from the claim text.