US6574669B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for routing traffic within a network utilizing linear optimization
Assignee: RPX Clearinghouse LLC
•
Filing: 1998-08-31
•
Granted: 2003-06-03
•
Expires: 2018-08-31
Abstract
Abstract A method and an apparatus for routing packets within a computer network uses linear optimization techniques to distribute the packet traffic over all potential links between a source and a destination node within the network. Network traffic is allocated to links coupled to a source node in a manner that is proportional to the bandwidth of links across complete paths which are fed from such links coupled to the source node. A set of metrics, in the form of complex numbers, is determined for a predetermined set of links within the network. The metrics are arranged as a matrix, and a linear optimization operation is performed using the matrix to determine percentage traffic distribution over links coupling the source node and the destination node in the network. Routing tables are then established to route traffic within the network according to the percentage values resulting from the linear optimization operation.
Inventors
- 👤 Jeffrey Charles Weaver
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 15:13
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/24; H04L45/243
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
95 words
A method comprising: determining a set of metrics for a corresponding set of links within a network; performing a linear optimization utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network each metric including a phase component comprising a sum of bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link; and routing traffic within the network according to the traffic flow values.
Claim 2
Independent Claim
95 words
A method comprising: determining a set of metrics for a corresponding set of links within a network; performing a linear optimization utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network each metric including a phase component comprising a sum of bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link; and routing traffic within the network according to the traffic flow values.
Claim 3
Dependent Claim
44 words
The method of claim 1 wherein the sum of bandwidth values comprises bandwidth values of the links feeding into the input end-point node including incoming bandwidth of the link corresponding to the metric less an outgoing bandwidth of the link corresponding to the metric.
Claim 4
Dependent Claim
32 words
The method of claim 1 wherein each the traffic flow values represent a percentage of the traffic from the source node to the destination node to be route via an associated link.
Claim 5
Dependent Claim
55 words
The method of claim 3 wherein the step of routing the traffic comprises generating a routing table for channeling network traffic from the source node to the destination node via links coupled to the source node according to the percentages represented by the traffic values associated with the respective links coupled to the source node.
Claim 6
Dependent Claim
20 words
The method of claim 1 wherein each metric includes a magnitude component comprising a bandwidth value of a corresponding link.
Claim 7
Dependent Claim
24 words
The method of claim 1 wherein each metric is modulated by a dynamic load scalar indicative of the effective bandwidth of the corresponding link.
Claim 8
Independent Claim
95 words
A method comprising: determining a set of metrics for a corresponding set of links within a network; performing a linear optimization utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network, the performing of the linear optimization operation comprises generating a flow matrix populated by the metrics for the set of links, the flow matrix represents a plurality of equilibrium equations for a set of nodes within the network; and routing traffic within the network according to the traffic flow values.
Claim 9
Independent Claim
95 words
A method comprising: determining a set of metrics for a corresponding set of links within a network; performing a linear optimization utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network, the performing of the linear optimization operation comprises generating a flow matrix populated by the metrics for the set of links, the flow matrix represents a plurality of equilibrium equations for a set of nodes within the network; and routing traffic within the network according to the traffic flow values.
Claim 10
Dependent Claim
42 words
The method of claim 7 wherein the step of generating the flow matrix comprises the step of inserting a diagonal value into each row of the matrix, each diagonal value including a negative sum of all metrics included within a respective row.
Claim 11
Dependent Claim
34 words
The method of claim 7 wherein the step of performing the linear optimization operation comprises the step of performing a routing analysis for a plurality of source and destination node pairs within the network.
Claim 12
Dependent Claim
19 words
The method of claim 9 wherein each routing analysis is performed on a network device comprising the source node.
Claim 13
Independent Claim
79 words
A method comprising: determining a set of metrics for a corresponding set of links within a network; performing a linear optimization utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network the performing of the linear optimization operation comprises generating a flow matrix populated by the metrics for the set of links by inserting an additional N+1th column into the flow matrix comprising null values.
Claim 14
Independent Claim
79 words
A method comprising: determining a set of metrics for a corresponding set of links within a network; performing a linear optimization utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network the performing of the linear optimization operation comprises generating a flow matrix populated by the metrics for the set of links by inserting an additional N+1th column into the flow matrix comprising null values.
Claim 15
Dependent Claim
31 words
The method of claim 11 wherein the step of performing the linear optimization operation comprises swapping a column associated with the source node and the N+1th column within the flow matrix.
Claim 16
Dependent Claim
27 words
The method of claim 12 , wherein the step of performing the linear optimization operation comprises negating the column associated with the source node for the swapping.
Claim 17
Dependent Claim
45 words
The method of claim 13 wherein the step of performing the linear optimization operation comprises solving an equation I=V*F for I, where I is a routing matrix indicating available bandwidth of each link, F is the flow matrix, and V is a potential difference matrix.
Claim 18
Dependent Claim
24 words
The method of claim 14 wherein the step of performing the linear optimization operation comprises normalizing the routing matrix to generate a probability matrix.
Claim 19
Dependent Claim
75 words
A network device configured to route network traffic as determined by a linear optimization operation performed utilizing a set of metrics, corresponding to a set of links within a network, each metric of the set of metrics includes a phase component comprising at most a sum of bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link.
Claim 20
Dependent Claim
75 words
A network device configured to route network traffic as determined by a linear optimization operation performed utilizing a set of metrics, corresponding to a set of links within a network, each metric of the set of metrics includes a phase component comprising at most a sum of bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link.
Claim 21
Dependent Claim
36 words
The network device of claim 16 wherein the set of metrics is manipulated during the linear optimization operation as a reduced matrix comprising only those metrics for links of the network coupled to the network device.
Claim 22
Dependent Claim
79 words
A network comprising a plurality of network devices, wherein each network device is configured to route network traffic as determined by a linear optimization operation performed utilizing a set of metrics, corresponding to a set of links within the network, wherein the network performing a linear optimization operation comprises generating a flow matrix populated by the metrics for the set of links, the flow matrix represents a plurality of equilibrium equations for a set of nodes within the network.
Claim 23
Dependent Claim
79 words
A network comprising a plurality of network devices, wherein each network device is configured to route network traffic as determined by a linear optimization operation performed utilizing a set of metrics, corresponding to a set of links within the network, wherein the network performing a linear optimization operation comprises generating a flow matrix populated by the metrics for the set of links, the flow matrix represents a plurality of equilibrium equations for a set of nodes within the network.
Claim 24
Dependent Claim
35 words
The network of claim 18 wherein each set of metrics is manipulated during the linear optimization operation as a reduced matrix comprising only those metrics for links of the network coupled to the network device.
Claim 25
Dependent Claim
115 words
Apparatus for routing traffic within a network including a plurality of nodes coupled by links, the apparatus comprising: a processor to perform a linear optimization operation utilizing a set of metrics, corresponding to a set of links within the network, to determine respective traffic flow values for links coupling a source and destination node within the network, each metric of the set of metrics includes a phase component comprising a sum of bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link; and a router to route traffic within the network according to the traffic flow values.
Claim 26
Dependent Claim
115 words
Apparatus for routing traffic within a network including a plurality of nodes coupled by links, the apparatus comprising: a processor to perform a linear optimization operation utilizing a set of metrics, corresponding to a set of links within the network, to determine respective traffic flow values for links coupling a source and destination node within the network, each metric of the set of metrics includes a phase component comprising a sum of bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link; and a router to route traffic within the network according to the traffic flow values.
Claim 27
Dependent Claim
32 words
The apparatus of claim 20 wherein each the traffic flow values represent a percentage of the traffic from the source node to the destination node to be routed via an associated link.
Claim 28
Dependent Claim
50 words
The apparatus of claim 21 including a memory to store a routing table for channeling network traffic from the source node to the destination node via links coupled to the source node according to the percentages represented by the traffic values associated with the links coupled to the source node.
Claim 29
Dependent Claim
26 words
The apparatus of claim 20 wherein the processor modulates each metric with a dynamic load scalar value indicative of the effective bandwidth of the corresponding link.
Claim 30
Dependent Claim
16 words
The apparatus of claim 20 wherein the router comprises a switch, routing switch or switching router.
Claim 31
Dependent Claim
13 words
The apparatus of claim 20 wherein the apparatus comprises a switching system product.
Claim 32
Dependent Claim
13 words
The apparatus of claim 20 wherein the apparatus comprises a transmissions system product.
Claim 33
Dependent Claim
117 words
A machine-readable medium embodying a plurality of instructions that, when executed by a machine, cause the machine to perform the steps of: (a) performing a linear optimization operation utilizing a set of metrics, corresponding to a set of links within a network, to determine respective traffic flow values for links coupling a source node and a destination node within the network each metric of the set of metrics includes a phase component comprising a sum of bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link; and (b) routing traffic within the network according to the traffic flow values.
Claim 34
Dependent Claim
117 words
A machine-readable medium embodying a plurality of instructions that, when executed by a machine, cause the machine to perform the steps of: (a) performing a linear optimization operation utilizing a set of metrics, corresponding to a set of links within a network, to determine respective traffic flow values for links coupling a source node and a destination node within the network each metric of the set of metrics includes a phase component comprising a sum of bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link; and (b) routing traffic within the network according to the traffic flow values.
Claim 35
Independent Claim
97 words
A method comprising: determining a set of metrics for a corresponding set of links within a network, each metric including a phase component that comprises the sum of incoming bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link; performing a linear optimization utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network; and routing traffic within the network according to the traffic flow values.
Claim 36
Independent Claim
97 words
A method comprising: determining a set of metrics for a corresponding set of links within a network, each metric including a phase component that comprises the sum of incoming bandwidth values of links feeding into a node comprising an input end-point for the link corresponding to the metric, divided by the outgoing bandwidth of the corresponding link; performing a linear optimization utilizing the set of metrics to determine respective traffic flow values for links coupling a source node and a destination node within the network; and routing traffic within the network according to the traffic flow values.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-06-02 | 2006-12-02 | 2007-06-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-06-02 | 2010-12-02 | 2011-06-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-06-02 | 2014-12-02 | 2015-06-03 | $7700.00 | Window Closed / Lapsed |