Method for resource allocation and routing in multi-service virtual private networks
First Claim
1. 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).
3 Assignments
0 Petitions
Accused Products
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.
145 Citations
29 Claims
-
1. 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). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29)
(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.
-
-
18. The method of claim 17, wherein each of the capacity costs is a linearized capacity cost.
-
19. 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.
-
-
20. 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.
-
21. 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.
-
22. 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.
-
23. 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.
-
24. 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.
-
25. 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.
-
26. 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.
-
-
27. The method of claim 26, wherein the step of setting at least one operating parameter of a network element comprises setting a scheduling weight.
-
28. 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.
-
-
29. The method of claim 28, wherein said step of temporarily reallocating bandwidth in at least one link comprises setting a trunk reservation parameter.
Specification