US5253161A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for routing data in a near-optimal manner in a distributed data communications network
Assignee: Individual
•
Filing: 1990-02-06
•
Granted: 1993-10-12
•
Expires: 2010-02-06
Abstract
Abstract A method to produce near-optimal routes for the flow of data between clusters in a distributed data communications network. A backbone traffic matrix and a backbone topology at the cluster level are used to produce minimum hop routes, minimum delay routes, or routes which maximize throughput. The inputs of the system are the number of requirements, the number of backbone links, and the number of backbone nodes.
Inventors
- 👤 Paul Nemirovsky
- 👤 Michael Ball
- 👤 Michael Post
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 18:32
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/04; H04L45/12; H04L45/121; H04Q; H04Q3/00; H04Q3/64; H04Q3/66
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
224 words
A method for constructing a data communication network having: a) a backbone including i) backbone nodes for routing data traffic within sad backbone, and ii) a plurality of first links for connecting said backbone nodes, b) terminals; c) concentrators; d) a plurality of second links for connecting said terminals with said concentrators; and e) a plurality of third links for connecting said concentrators with said backbone nodes, wherein each of said first, second, and third links has an associated traffic delay time and data flow, comprising the steps of: 1) assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow; 2) determining the shortest routes between each pair of said backbone nodes; 3) placing requirements corresponding to a current data flow pattern onto said shortest routes; 4) storing said shortest routes; 5) determining an approximation of a second derivative of traffic delay time with respect to data flow; 6) determining an amount of slack on each of said shortest routes; 7) rerouting said data flow from all other routes onto said shortest routes based on said first derivative, said second derivative, and said slack; 8) determining an updated data flow of the network; and 9) determining an updated traffic delay time for the updated data flow of the network.
Claim 2
Independent Claim
224 words
A method for constructing a data communication network having: a) a backbone including i) backbone nodes for routing data traffic within sad backbone, and ii) a plurality of first links for connecting said backbone nodes, b) terminals; c) concentrators; d) a plurality of second links for connecting said terminals with said concentrators; and e) a plurality of third links for connecting said concentrators with said backbone nodes, wherein each of said first, second, and third links has an associated traffic delay time and data flow, comprising the steps of: 1) assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow; 2) determining the shortest routes between each pair of said backbone nodes; 3) placing requirements corresponding to a current data flow pattern onto said shortest routes; 4) storing said shortest routes; 5) determining an approximation of a second derivative of traffic delay time with respect to data flow; 6) determining an amount of slack on each of said shortest routes; 7) rerouting said data flow from all other routes onto said shortest routes based on said first derivative, said second derivative, and said slack; 8) determining an updated data flow of the network; and 9) determining an updated traffic delay time for the updated data flow of the network.
Claim 3
Dependent Claim
38 words
The method for constructing a data communication network according to claim 1 further comprising repeating the steps (1) through (9) and selecting for operation the network having a network data flow which incurs a minimum traffic delay time.
Claim 4
Dependent Claim
22 words
The method according to claim 1 for constructing a data communication network wherein the concentrators are statistical multiplexers with protocol conversion capabilities.
Claim 5
Dependent Claim
19 words
The method according to claim 1 for constructing a data communication network wherein said backbone nodes include data switches.
Claim 6
Dependent Claim
23 words
The method for constructing a data communication network according to claim 1 wherein said second links are data lines of telephone service providers.
Claim 7
Dependent Claim
21 words
The method for constructing a data communication network according to claim 1 wherein said first links are high volume data lines.
Claim 8
Dependent Claim
22 words
The method for constructing a data communication network according to claim 6 wherein said high volume data lines are fiber optic lines.
Claim 9
Dependent Claim
243 words
A computer system for constructing a data communication network having: a) a backbone including, i) backbone nodes for routing data traffic within said backbone, and i) a plurality of first links for connecting said backbone nodes, b) terminals; c) concentrators; d) a plurality of second links for connecting said terminals with said concentrators; and e) a plurality of third links for connecting said concentrators with said backbone nodes, wherein each of said first, second and third links has an associated traffic delay time and data flow, said computer system comprising: 1) means for assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow; 2) means for determining the shortest routes between each pair of said backbone nodes; 3) means for placing requirements corresponding to a current data flow pattern onto said shortest routes; 4) means for storing said shortest routes; 5) means for determining an approximation of a second derivative of traffic delay time with respect to data flow; 6) means for determining an amount of slack on each of said shortest routes; 7) means for rerouting said data flow from all other routes onto said shortest routes based on said first derivative, said second derivative, and said slack; 8) means for determining an updated data flow of the network; and 9) means for determining an updated traffic delay time for the updated data flow of the network.
Claim 10
Dependent Claim
243 words
A computer system for constructing a data communication network having: a) a backbone including, i) backbone nodes for routing data traffic within said backbone, and i) a plurality of first links for connecting said backbone nodes, b) terminals; c) concentrators; d) a plurality of second links for connecting said terminals with said concentrators; and e) a plurality of third links for connecting said concentrators with said backbone nodes, wherein each of said first, second and third links has an associated traffic delay time and data flow, said computer system comprising: 1) means for assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow; 2) means for determining the shortest routes between each pair of said backbone nodes; 3) means for placing requirements corresponding to a current data flow pattern onto said shortest routes; 4) means for storing said shortest routes; 5) means for determining an approximation of a second derivative of traffic delay time with respect to data flow; 6) means for determining an amount of slack on each of said shortest routes; 7) means for rerouting said data flow from all other routes onto said shortest routes based on said first derivative, said second derivative, and said slack; 8) means for determining an updated data flow of the network; and 9) means for determining an updated traffic delay time for the updated data flow of the network.
Claim 11
Dependent Claim
23 words
The computer system according to claim 8 for constructing a data communication network wherein the concentrators are statistical multiplexers with protocol conversion capabilities.
Claim 12
Dependent Claim
20 words
The computer system according to claim 8 for constructing a data communication network wherein said backbone nodes include data switches.
Claim 13
Dependent Claim
24 words
The computer system for constructing a data communication network according to claim 8 wherein said second links are data lines of telephone service providers.
Claim 14
Dependent Claim
21 words
The computer system for constructing data communication network according to claim 8 wherein said first links are high volume data lines.
Claim 15
Dependent Claim
23 words
The computer system for constructing a data communication network according to claim 12 wherein said high volume data lines are fiber optic lines.
Claim 16
Independent Claim
281 words
A method for constructing a data communication network having, a) a backbone including, i) a plurality of first links for connecting said backbone nodes, b) terminals; c) concentrators; d) a plurality of second links for connecting said terminals with said concentrators; and e) a plurality of third links for connecting said concentrators with said backbone nodes, and having an associated traffic delay and data flow, comprising steps of: (1) assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow; (2) determining the shortest routes between each pair of said backbone nodes; (3) assigning at least one requirement to each route; (4) diverting flow from other routes to the shortest route which meets each of the assigned requirements; (5) determining a slack value based on a minimum spare capacity of any link in the route; (6) determining a correction factor based on an estimate of the second derivative of traffic delay with respect to flow, for each link; (7) determining the amount of diverted flow based on the requirements assigned to each route, a step size, said correction factor, the length of the route and the length of the shortest path, for each route; (8) setting the amount of diverted flow equal to the slack value divided by the number of nodes when the amount of diverted flow is greater than the slack value divided by the number of nodes; (9) determining a link delay for each link; (10) determining a length of each link based on said link delay; and (11) repeat steps (1) through (10) until change in length is less than said step size.
Claim 17
Independent Claim
281 words
A method for constructing a data communication network having, a) a backbone including, i) a plurality of first links for connecting said backbone nodes, b) terminals; c) concentrators; d) a plurality of second links for connecting said terminals with said concentrators; and e) a plurality of third links for connecting said concentrators with said backbone nodes, and having an associated traffic delay and data flow, comprising steps of: (1) assigning a length of each of said plurality of first links based on a derivative of traffic delay time with respect to the data flow; (2) determining the shortest routes between each pair of said backbone nodes; (3) assigning at least one requirement to each route; (4) diverting flow from other routes to the shortest route which meets each of the assigned requirements; (5) determining a slack value based on a minimum spare capacity of any link in the route; (6) determining a correction factor based on an estimate of the second derivative of traffic delay with respect to flow, for each link; (7) determining the amount of diverted flow based on the requirements assigned to each route, a step size, said correction factor, the length of the route and the length of the shortest path, for each route; (8) setting the amount of diverted flow equal to the slack value divided by the number of nodes when the amount of diverted flow is greater than the slack value divided by the number of nodes; (9) determining a link delay for each link; (10) determining a length of each link based on said link delay; and (11) repeat steps (1) through (10) until change in length is less than said step size.
References Cited (Backward Citations)
US4081612A
Cited
US4974224A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-10-11 | 1997-04-12 | 1997-10-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-10-11 | 2001-04-12 | 2001-10-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-10-11 | 2005-04-12 | 2005-10-12 | $7700.00 | Window Closed / Lapsed |