US6331986B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for resource allocation and routing in multi-service virtual private networks
Assignee: Nokia of America Corp
•
Filing: 1998-04-24
•
Granted: 2001-12-18
•
Expires: 2018-04-24
Abstract
Abstract We describe a method for solving the joint problem of optimal routing and optimal bandwidth allocation in a network that supports plural subnetworks and plural communication services. Our method involves, for each source-destination pair communicating via a given subnetwork and a given class of service, determining a traffic rate to be offered to each of a set of permissible routes between that source and that destination, in the given subnetwork and service class. Our method further involves allocating a respective bandwidth to each link of each subnetwork. Significantly, the determinations of traffic rate to be offered, and the allocations of bandwidth to respective links of subnetworks, are performed in a mutually responsive manner.
Inventors
- 👤 Debasis Mitra
- 👤 John A. Morrison
- 👤 Kajamalai Gopalaswamy Ramakrishnan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 07:58
CPC Classifications
H; H04; H04Q; H04Q3/00; H04Q3/0016; H04Q3/0062; H04Q3/0091; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04Q3/58; H04Q3/62; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5619; H04L2012/562; H04L2012/5621; H04Q2213/00; H04Q2213/13056; H04Q2213/13141; H04Q2213/13148; H04Q2213/13164; H04Q2213/13332; H04Q2213/13349; H04Q2213/13383; H04Q2213/13384; H04Q2213/13399
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
151 words
A method for allocating bandwidth capacity on links of a communication network that supports plural subnetworks and plural communication services, and in which sets of permissible routes are defined between respective source-destination pairs for each said subnetwork and service, wherein: the method comprises, in each of two or more iterations: (a) partitioning the bandwidth capacity of each of at least some links of the network among the subnetworks that share that link; and (b) in each of two or more subnetworks, for each service and for each source-destination pair served thereby, determining a traffic rate to be offered to each permissible route between said source-destination pair; at least one instance of (a) is based on an allocation of traffic rates resulting from a prior instance of (b); and at least one instance of (b) is based on a partition of link capacity among subnetworks resulting from a prior instance of (a).
Claim 2
Independent Claim
151 words
A method for allocating bandwidth capacity on links of a communication network that supports plural subnetworks and plural communication services, and in which sets of permissible routes are defined between respective source-destination pairs for each said subnetwork and service, wherein: the method comprises, in each of two or more iterations: (a) partitioning the bandwidth capacity of each of at least some links of the network among the subnetworks that share that link; and (b) in each of two or more subnetworks, for each service and for each source-destination pair served thereby, determining a traffic rate to be offered to each permissible route between said source-destination pair; at least one instance of (a) is based on an allocation of traffic rates resulting from a prior instance of (b); and at least one instance of (b) is based on a partition of link capacity among subnetworks resulting from a prior instance of (a).
Claim 3
Dependent Claim
36 words
The method of claim 1 , wherein (a) and (b) are carried out so as to maximize a weighted aggregate measure of bandwidth carried by the network, said measure to be referred to as network revenue.
Claim 4
Dependent Claim
28 words
The method of claim 2 , wherein the network revenue is maximized subject to a constraint that specifies a minimum quality of service in at least one subnetwork.
Claim 5
Dependent Claim
35 words
The method of claim 3 , wherein the constraint specifies that a respective bandwidth carried by said at least one subnetwork in at least one class of service may not fall below a specified level.
Claim 6
Dependent Claim
23 words
The method of claim 4 , wherein said bandwidth is the total subnetwork bandwidth carried in said at least one class of service.
Claim 7
Dependent Claim
29 words
The method of claim 4 , wherein said bandwidth is the subnetwork bandwidth carried in said at least one class of service between at least one specified source-destination pair.
Claim 8
Dependent Claim
30 words
The method of claim 4 , wherein the specified level is a specified fraction of the total traffic offered to the pertinent subnetwork in at least one class of service.
Claim 9
Dependent Claim
24 words
The method of claim 2 , wherein (b) is carried out such that the bandwidth allocated to each link is completely partitioned between subnetworks.
Claim 10
Dependent Claim
53 words
The method of claim 8 , wherein (a) and (b) are carried out iteratively, such that each iteration of (a) is responsive to a prior allocation of bandwidth to links, and at least the second and subsequent iterations of (b) are each responsive to a prior determination of traffic rates to be offered.
Claim 11
Dependent Claim
22 words
The method of claim 9 , wherein in each iteration, (a) is carried out using a deterministic flow model of network traffic.
Claim 12
Dependent Claim
22 words
The method of claim 9 , wherein in each iteration, (b) is carried out using a deterministic flow model of network traffic.
Claim 13
Dependent Claim
34 words
The method of claim 9 , wherein in each iteration, (a) is carried out using a stochastic model of network traffic, and (b) is carried out using a deterministic flow model of network traffic.
Claim 14
Dependent Claim
34 words
The method of claim 9 , wherein in each iteration, (a) is carried out using a deterministic flow model of network traffic, and (b) is carried out using a stochastic model of network traffic.
Claim 15
Dependent Claim
18 words
The method of claim 9 , wherein, in each iteration, (a) is carried out independently for each subnetwork.
Claim 16
Dependent Claim
25 words
The method of claim 14 , wherein (a) is carried out independently for each subnetwork by carrying out respective computations for each subnetwork in parallel.
Claim 17
Dependent Claim
23 words
The method of claim 14 , wherein, in each iteration, (b) is carried out such that bandwidth is reallocated independently to each link.
Claim 18
Dependent Claim
94 words
The method of claim 14 , wherein the network revenue is evaluated by summing respective subnetwork revenues from each of the subnetworks, and the method further comprises, in each iteration: (a) for each link of each subnetwork, calculating a capacity cost that expresses the sensitivity of the pertinent subnetwork revenue to the bandwidth allocated to said link for said subnetwork; and (b) using the capacity costs to extrapolate from a current subnetwork revenue based on a current set of said bandwidth allocations to a new subnetwork revenue based on a reallocation of said bandwidths.
Claim 19
Dependent Claim
17 words
The method of claim 17 , wherein each of the capacity costs is a linearized capacity cost.
Claim 20
Dependent Claim
80 words
The method of claim 17 , wherein: a respective penalty referred to as an implied cost is associated with each link of each subnetwork for each respective service; each implied cost acts to reduce an effective revenue per call of the pertinent subnetwork and service that is routed on the pertinent link; the implied costs reflect probabilities that calls will be lost due to insufficient bandwidth on the various links of each subnetwork; and step (c) comprises evaluating implied costs.
Claim 21
Dependent Claim
43 words
The method of claim 19 , wherein a stochastic model is used to describe network traffic, and for at least some links, the evaluation of implied costs is carried out using the Refined Uniform Asymptotic Approximation to express loss probabilities on said links.
Claim 22
Dependent Claim
40 words
The method of claim 19 , wherein a stochastic model is used to describe network traffic, and for at least some links, the evaluation of implied costs is carried out using exact methods to express loss probabilities on said links.
Claim 23
Dependent Claim
27 words
The method of claim 19 , wherein the evaluation of implied costs is carried out using a deterministic flow model to express loss probabilities on said links.
Claim 24
Dependent Claim
59 words
The method of claim 19 , wherein a stochastic model is used to describe network traffic, the evaluation of implied costs is carried out using exact methods to express loss probabilities on at least some links having relatively low capacities, and an asymptotic approximation is used to express loss probabilities on at least some links having relatively high capacities.
Claim 25
Dependent Claim
78 words
The method of claim 19 , wherein a stochastic model is used to describe network traffic, during at least some relatively early iterations, the evaluation of implied costs is carried out using the Uniform Asymptotic Approximation to express loss probabilities on at least some links, and during at least some relatively late iterations, the evaluation of implied costs is carried out using the Refined Uniform Asymptotic Approximation to Approximation to express loss probabilities on at least some links.
Claim 26
Dependent Claim
33 words
The method of claim 9 , further comprising, after the last iteration of (b), temporarily reallocating bandwidth in at least one link from at least one subnetwork to at least one other subnetwork.
Claim 27
Dependent Claim
65 words
The method of claim 1 , wherein: the method further comprises measuring traffic intensity, in at least one class of service, offered to at least one source-destination pair within at least one subnetwork; steps (a) and (b) are carried out responsively to said measuring step; and the method further comprises, responsively to (a) and (b), setting at least one operating parameter of a network element.
Claim 28
Dependent Claim
25 words
The method of claim 26 , wherein the step of setting at least one operating parameter of a network element comprises setting a scheduling weight.
Claim 29
Dependent Claim
96 words
The method of claim 1 , wherein: the method further comprises measuring traffic intensity, in at least one class of service, offered to at least one source-destination pair within at least one subnetwork; steps (a) and (b) are carried out responsively to said measuring step; the method further comprises, after (a) and (b), making at least one further measurement traffic intensity; and the method further comprises, responsively to said at least one further measurement of traffic intensity, temporarily reallocating bandwidth in at least one link from at least one subnetwork to at least one other subnetwork.
Claim 30
Dependent Claim
24 words
The method of claim 28 , wherein said step of temporarily reallocating bandwidth in at least one link comprises setting a trunk reservation parameter.
References Cited (Backward Citations)
US5850385A
Cited
US5495479A
Cited
US5600638A
Cited
US6084955A
Cited
US6069894A
Cited
US5838663A
Cited
US5953338A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-12-17 | 2005-06-18 | 2005-12-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-12-17 | 2009-06-18 | 2009-12-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-12-17 | 2013-06-18 | 2013-12-18 | $7700.00 | Window Closed / Lapsed |