# US 2004/0071089 A1 · Costs in data networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0071089 A1
- Document ID: US20040071089A1
- Status: Published application
- Kind: A1
- Application number: 10/432,453
- Filed: 2003-11-17
- Published: 2004-04-15
- Earliest claimed: 2000-11-21
- Assignees: International Business Machines Corporation
- Inventors: Daniel Bauer; John N. Daigle; Ilias Iliadis; Paolo Scotton
- Web page: https://patentgrep.com/patent/US20040071089A1

## CPC

- H04Q 11/0478: {Provisions for broadband connections}
- H04L 45/124: {using a combination of metrics}
- H04Q: SELECTING (switches, relays, selectors H01H; wireless communication networks H04W)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

A method as claimed in claim 1, wherein each restrictive cost comprises a value indicative of bandwidth of the corresponding path; and the best restrictive cost is the cost indicative of the maximum bandwidth.

### Claim 3 (depends on 1, 2)

A method as claimed in claim 1 or claim 2, wherein each additive cost comprises a value indicative of transit delay associated with the corresponding path and the best additive cost is the cost indicative of the minimum transit delay.

### Claim 4

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.

### Claim 5 (depends on 1, 2, 3, 4)

A computer program element comprising computer program code means which, when loaded in a processor of a data processing system, configures the processor to perform the method for deriving a set of efficient path costs as claimed in any one of claims 1 to 4.

### Claim 6

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.

### Claim 7 (depends on 6)

Apparatus as claimed in claim 6, wherein each restrictive cost comprises a value indicative of bandwidth of the corresponding path; and the best restrictive cost is the cost indicative of the maximum bandwidth.

### Claim 8 (depends on 6, 7)

Apparatus as claimed in claim 6 or claim 7, wherein each additive cost comprises a value indicative of transit delay associated with the corresponding path and the best additive cost is the cost indicative of the minimum transit delay.

### Claim 9 (depends on 6, 7, 8)

Apparatus as claimed in any of claims 6 to 8, wherein at least one of the paths comprises a plurality of links and at least one intermediate node.

### Claim 10 (depends on 6, 7, 8, 9)

A data networking device comprising a plurality of ports each for connection to a path of a data communications network, and apparatus for deriving a set of efficient path costs as claimed in any of claims 6 to 9 coupled to the paths.

### Claim 11 (depends on 10)

A data network comprising a plurality of nodes interconnected by plurality of paths, at least one of the nodes comprising a data networking device as claimed in claim 10.
