Method for resource allocation and routing in multi-service virtual private networks

• US 6,331,986 B1
• Filed: 04/24/1998
• Issued: 12/18/2001
• Est. Priority Date: 04/24/1998
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Morrison, John A., Mitra, Debasis, Ramakrishnan, Kajamalai Gopalaswamy
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US09/065,506
• Time in Patent Office: 1,334 Days
• Field of Search: 370/252, 370/253, 370/254, 370/255, 370/256, 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/238, 370/468, 370/400, 370/401, 370/402, 370/409, 370/408, 370/395, 370/396, 370/397, 370/399, 370/389, 370/392
• US Class Current: 370/468
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5621 Virtual private network [VPN]; Private-network - network-interface (P-NNI)
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04Q 2213/13056 Routines, finite state machines
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13148 Maximum profit routing
• CPC Class Codes: H04Q 2213/13164 Traffic (registration, measurement,...)
• CPC Class Codes: H04Q 2213/13332 Broadband, CATV, dynamic bandwidth allocation
• CPC Class Codes: H04Q 2213/13349 Network management
• CPC Class Codes: H04Q 2213/13383 Hierarchy of switches, main and subexchange, e.g. satellite exchange
• CPC Class Codes: H04Q 2213/13384 Inter-PBX traffic, PBX networks, e.g. corporate networks
• CPC Class Codes: H04Q 2213/13399 Virtual channel/circuits
• CPC Class Codes: H04Q 3/0091 Congestion or overload control
• CPC Class Codes: H04Q 3/62 for connecting to private branch exchanges

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.

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).

2. 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.

3. 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.

4. 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.

5. The method of claim 4, wherein said bandwidth is the total subnetwork bandwidth carried in said at least one class of service.

6. 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.

7. 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.

8. The method of claim 2, wherein (b) is carried out such that the bandwidth allocated to each link is completely partitioned between subnetworks.

9. 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.

10. The method of claim 9, wherein in each iteration, (a) is carried out using a deterministic flow model of network traffic.

11. The method of claim 9, wherein in each iteration, (b) is carried out using a deterministic flow model of network traffic.

12. 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.

13. 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.

14. The method of claim 9, wherein, in each iteration, (a) is carried out independently for each subnetwork.

15. The method of claim 14, wherein (a) is carried out independently for each subnetwork by carrying out respective computations for each subnetwork in parallel.

16. The method of claim 14, wherein, in each iteration, (b) is carried out such that bandwidth is reallocated independently to each link.

17. 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.

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.