Patent US6256309B1 successfully refreshed from Google Patents.
US6256309B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Quality of service sensitive routes precomputed in bandwidth brackets
Assignee: Cisco Technology Inc
•
Filing: 1998-04-28
•
Granted: 2001-07-03
•
Expires: 2018-04-28
Abstract
Abstract A routing scheme generates a selection of precomputed routes that provide a wide range of available bandwidths while keeping delay (e.g., measure by cell transfer delay and cell delay variation), or cost, to a minimum, thus enabling high call rates at an overall lower call blocking rate. The routing scheme achieves this end by generating routes using a set of preconfigured bandwidth thresholds for pruning lower bandwidth links while least-cost optimizing on delay-based optimization functions, using for example, maximum cell transfer delay and maximum cell rate, or a cost-based function, using for example, administrative weight. The optimization function is determined during configuration by the selection of either cost-based or delay-based routing.
Inventors
- 👤 Patrick D. Daley
- 👤 David A. Hughes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 11:11
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
38 words
A method, comprising organizing a plurality of shortest path routes for a network computed according to a network constraint into two or more bandwidth brackets, each bandwidth bracket including a lower bandwidth threshold and an upper bandwidth threshold.
Claim 2
Independent Claim
38 words
A method, comprising organizing a plurality of shortest path routes for a network computed according to a network constraint into two or more bandwidth brackets, each bandwidth bracket including a lower bandwidth threshold and an upper bandwidth threshold.
Claim 3
Dependent Claim
17 words
The method of claim 1 further comprising selecting the network constraint prior to the step of organizing.
Claim 4
Dependent Claim
29 words
The method of claim 1 further comprising searching the shortest path routes according to the bandwidth brackets upon receipt of a call request for a route within the network.
Claim 5
Dependent Claim
13 words
The method of claim 2 wherein the network constraint is a delay-based constraint.
Claim 6
Dependent Claim
25 words
The method of claim 4 wherein the delay-based constraint comprises a function of cell transfer delay and a computed per-hop penalty (PHP) within the network.
Claim 7
Dependent Claim
18 words
The method of claim 5 wherein the PHP is computed as a function of a maximum cell rate.
Claim 8
Dependent Claim
13 words
The method of claim 2 wherein the network constraint is a cost-based constraint.
Claim 9
Dependent Claim
25 words
The method of claim 7 wherein the cost-based constraint comprises a function of the relative desirability of using a link or node within the network.
Claim 10
Dependent Claim
37 words
The method of claim 3 further comprising configuring an on-demand route when none of the shortest path routes satisfy the call request and a bandwidth requested in the call request exceeds a highest of the bandwidth brackets.
Claim 11
Dependent Claim
39 words
The method of claim 3 further comprising blocking the call request when none of the shortest path routes satisfy the call request but a bandwidth requested in the call request does not exceed a highest of the bandwidth brackets.
Claim 12
Dependent Claim
26 words
The method of claim 3 further comprising selecting one of the shortest path routes in response to a call request for a route within the network.
Claim 13
Dependent Claim
23 words
The method of claim 11 wherein the step of selecting comprises sequentially searching the shortest path routes until an acceptable route is found.
Claim 14
Dependent Claim
37 words
The method of claim 12 further comprising randomly selecting one of a number of routes when more than one route having the same cost according to the network constraint is found during the step of sequentially searching.
Claim 15
Dependent Claim
37 words
The method of claim 13 further comprising configuring an on-demand route when none of the shortest path routes satisfy the call request and a bandwidth requested in the call request exceeds a highest of the bandwidth brackets.
Claim 16
Dependent Claim
34 words
The method of claim 12 further comprising blocking the call request when no acceptable route is found and a bandwidth requested in the call request does not exceed a highest of the bandwidth brackets.
Claim 17
Dependent Claim
32 words
The method of claim 12 further comprising configuring an on-demand route when no acceptable route is found and a bandwidth requested in the call request exceeds a highest of the bandwidth brackets.
Claim 18
Dependent Claim
41 words
A shortest path tree comprising a plurality of shortest path routes for a network optimized according to a network constraint and organized into two or more bandwidth brackets, each bandwidth bracket including a lower bandwidth threshold and an upper bandwidth threshold.
Claim 19
Dependent Claim
41 words
A shortest path tree comprising a plurality of shortest path routes for a network optimized according to a network constraint and organized into two or more bandwidth brackets, each bandwidth bracket including a lower bandwidth threshold and an upper bandwidth threshold.
Claim 20
Dependent Claim
15 words
The shortest path tree of claim 17 wherein the network constraint is a delay-based constraint.
Claim 21
Dependent Claim
27 words
The shortest path tree of claim 18 wherein the delay-based constraint comprises a function of cell transfer delay and a computed per-hop penalty (PHP) within the network.
Claim 22
Dependent Claim
20 words
The shortest path tree of claim 19 wherein the PHP is computed as a function of a maximum cell rate.
Claim 23
Dependent Claim
15 words
The shortest path tree of claim 17 wherein the network constraint is a cost-based constraint.
Claim 24
Dependent Claim
27 words
The shortest path tree of claim 21 wherein the cost-based constraint comprises a function of the relative desirability of using a link or node within the network.
Claim 25
Dependent Claim
18 words
The shortest path tree of claim 17 wherein the shortest path routes are organized into four bandwidth brackets.
Claim 26
Dependent Claim
46 words
A switch configured to compute a shortest path tree having a plurality of shortest path routes for a network optimized according to a network constraint and organized into two or more bandwidth brackets, each bandwidth bracket including a lower bandwidth threshold and an upper bandwidth threshold.
Claim 27
Dependent Claim
46 words
A switch configured to compute a shortest path tree having a plurality of shortest path routes for a network optimized according to a network constraint and organized into two or more bandwidth brackets, each bandwidth bracket including a lower bandwidth threshold and an upper bandwidth threshold.
Claim 28
Dependent Claim
45 words
The switch of claim 24 , wherein the switch is further configured to block a call request when none of the shortest path routes satisfy the call request but a bandwidth requested in the call request does not exceed a highest of the bandwidth brackets.
Claim 29
Dependent Claim
45 words
The switch of claim 24 , wherein the switch is further configured to route a call request on demand when none of the shortest path routes satisfy the call request but a bandwidth requested in the call request exceeds a highest of the bandwidth brackets.
Claim 30
Dependent Claim
44 words
The switch of claim 24 , wherein the switch is further configured to randomly select one of a number of equal-cost routes when more than one route having the same cost according to the network constraint is found in response to a call request.
Claim 31
Independent Claim
38 words
A method, comprising creating a plurality of shortest path routes for a network computed according to a network constraint and a plurality of bandwidth brackets, each bandwidth bracket including a lower bandwidth threshold and an upper bandwidth threshold.
Claim 32
Independent Claim
38 words
A method, comprising creating a plurality of shortest path routes for a network computed according to a network constraint and a plurality of bandwidth brackets, each bandwidth bracket including a lower bandwidth threshold and an upper bandwidth threshold.
Claim 33
Dependent Claim
23 words
The method of claim 28 further comprising selecting the network constraint prior to the step of creating the plurality of shortest path trees.
Claim 34
Dependent Claim
27 words
The method of claim 28 further comprising searching the shortest path routes by bandwidth bracket upon receipt of a call request for a route within the network.
Claim 35
Dependent Claim
13 words
The method of claim 29 wherein the network constraint is a delay-based constraint.
Claim 36
Dependent Claim
25 words
The method of claim 31 wherein the delay-based constraint comprises a function of cell transfer delay and a computed per-hop penalty (PHP) within the network.
Claim 37
Dependent Claim
18 words
The method of claim 32 wherein the PHP is computed as a function of a maximum cell rate.
Claim 38
Dependent Claim
13 words
The method of claim 29 wherein the network constraint is a cost-based constraint.
Claim 39
Dependent Claim
25 words
The method of claim 34 wherein the cost-based constraint comprises a function of the relative desirability of using a link or node within the network.
Claim 40
Dependent Claim
37 words
The method of claim 30 further comprising configuring an on-demand route when none of the shortest path routes satisfy the call request and a bandwidth requested in the call request exceeds a highest of the bandwidth brackets.
Claim 41
Dependent Claim
39 words
The method of claim 30 further comprising blocking the call request when none of the shortest path routes satisfy the call request but a bandwidth requested in the call request does not exceed a highest of the bandwidth brackets.
Claim 42
Dependent Claim
26 words
The method of claim 30 further comprising selecting one of the shortest path routes in response to a call request for a route within the network.
Claim 43
Dependent Claim
23 words
The method of claim 38 wherein the step of selecting comprises sequentially searching the shortest path routes until an acceptable route is found.
Claim 44
Dependent Claim
37 words
The method of claim 39 further comprising randomly selecting one of a number of routes when more than one route having the same cost according to the network constraint is found during the step of sequentially searching.
Claim 45
Dependent Claim
37 words
The method of claim 40 further comprising configuring an on-demand route when none of the shortest path routes satisfy the call request and a bandwidth requested in the call request exceeds a highest of the bandwidth brackets.
Claim 46
Dependent Claim
34 words
The method of claim 40 further comprising blocking the call request when no acceptable route is found and a bandwidth requested in the call request does not exceed a highest of the bandwidth brackets.
Claim 47
Dependent Claim
32 words
The method of claim 41 further comprising configuring an on-demand route when no acceptable route is found and a bandwidth requested in the call request exceeds a highest of the bandwidth brackets.
References Cited (Backward Citations)
US6041059A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-07-02 | 2005-01-01 | 2005-07-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-07-02 | 2009-01-01 | 2009-07-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-07-02 | 2013-01-01 | 2013-07-03 | $7700.00 | Window Closed / Lapsed |