Method for sharing network resources by virtual partitioning

• US 5,781,624 A
• Filed: 05/17/1996
• Issued: 07/14/1998
• Est. Priority Date: 02/16/1996
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Mitra, Debasis, Ziedins, Ilze
• Primary Examiner(s): Zele, Krista
• Assistant Examiner(s): Wolinsky, Scott
• Application Number:
  US08/649,502
• Time in Patent Office: 788 Days
• Field of Search: 379/242, 379/243, 379/244, 379/245, 379/246, 379/219, 379/220, 379/221, 379/222, 379/223, 379/202, 379/207, 379/111, 379/112, 379/113, 379/120, 379/137, 379/265, 379/266, 379/309
• US Class Current: 379/244
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5631 Resource management and allocation
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/782 Hierarchical allocation of resources, e.g. involving a hierarchy of local and centralised entities
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method of operating a network by sharing resources associated with various classes among calls in the various classes according to a state dependent reservation parameter. Nominal amounts of one or more resources are allocated to each call class. When a call of a class of service operating in the network requires resources in excess of those allocated to the class, resources allocated to other classes of service are advantageously shared with the class of service. The sharing is based on a reservation parameter associated with the class of service of the call. The reservation parameter is advantageously a function of the network state. The role of the reservation parameter is to protect underloaded classes (i.e., those classes not using all of their allocated nominal capacity) from excessive borrowing by overloaded classes (i.e., classes using more than their allocated nominal capacity). More generally, the inventive method is used to determine if sufficient resources are available for routing calls and to route calls based on the determined available resources.

Claims

1. A method of operating a network by sharing resources associated with said network, wherein:

(a) each of plural classes of service is allocated a respective portion of said resources;

(b) a particular class of service operating in the network requires a greater portion of said resources than its allocated portion;

the method comprising;

(i) receiving a request to accept a call associated with said particular class of service;

(ii) applying a criterion for acceptance of the call, wherein;

said criterion invokes a respective reservation parameter specifically assigned to said particular class of service; and

the reservation parameter represents a quantity of network resources that is excluded from sharing by said particular class or service; and

(iii) accepting the call only if the criterion is satisfied, thereby permitting said particular class of service to share network resources exceeding its allocated portion; and

(c) a different reservation parameter is assigned to each of said plural classes of service.

2. The method of claim 1 wherein said network is characterized by a network state and wherein said reservation parameter associated with said particular class of service is a function of said network state.

3. The method of claim 2 wherein said resources comprise capacity in a link in said network, wherein the capacity is shared by a set of calls, wherein each call in said set of calls is associated with a class of service in said plurality of classes of service, and wherein said network state characterizes the number of calls associated with each class of service in said plurality of classes of service.

4. The method of claim 2 wherein said reservation parameter is also a function of an arrival rate process for calls associated with said particular class of service.

5. The method of claim 2 wherein said reservation parameter is also a function of a mean holding time for calls associated with said particular class of service.

6. The method of claim 1 further comprising the step of:

routing said call on a path through said network.

7. The method of claim 6 wherein said network is a centralized network.

8. The method of claim 6 wherein said network is a distributed network, said method further comprising the step of:

if said step of routing is unsuccessful, routing said call on another path.

9. The method of claim 1 wherein said respective portion of said resources allocated to each class of service is sufficient to satisfy a quality of service requirement associated with said each class of service.

10. A method of operating a network by routing a call on a path through said network, wherein said call is associated with a particular class of service, said network comprising links having associated resources, wherein said particular class of service is allocated a particular respective amount of the resources associated with each link, and wherein said call requires a given amount of the associated resources, said method comprising the steps of:

receiving a request to route said call through said network,

identifying a set of links capable of accepting said call requiring said given amount of associated resources, wherein a link in the identified set of links is such that either;

     1) said particular class of service is not overloaded and said link has sufficient associated resources to accommodate said call, or

     2) said particular class of service is overloaded and said particular class of service may share, in accordance with a reservation parameter associated with said particular class, resources associated with said link allocated to other classes of service,

identifying a set of paths on which said call may be routed, wherein each path in said set of paths comprises links in the identified set of links,

selecting a path from said set of paths according to a criterion, and

routing said call on said selected path.

11. The method of claim 10 wherein said reservation parameter represents an amount of resources associated with said network that cannot be shared by said particular class of service when said particular class of service is overloaded.

12. The method of claim 10 wherein said network is characterized by a network state and wherein said reservation parameter associated with said particular class is a function of said network state.

13. The method of claim 12 wherein said reservation parameter is also a function of an arrival rate process for calls associated with said particular class of service.

14. The method of claim 12 wherein said reservation parameter is also a function of a mean holding time for calls associated with said particular class of service.

15. The method of claim 10 wherein said network is a centralized network.

16. The method of claim 10 wherein said network is a distributed network, said method further comprising the steps of:

if said step of routing is unsuccessful, selecting another path from said set of paths according to said criterion and routing said call on said another selected path.

17. The method of claim 10 wherein said particular class of service is one class of service in a plurality of classes of service and wherein said network state characterizes the number of calls associated with each class of service in said plurality of classes of service.

18. The method of claim 10 wherein the particular respective amount of the resources associated with each link allocated to said particular class of service is sufficient to satisfy a quality of service requirement associated with said particular class.

19. A method of operating a network by sharing resources associated with said network, wherein:

(a) the network is a hierarchical network having plural levels;

(b) associated with each said level are plural classes;

(c) each of said plural classes is allocated a respective portion of said resources; and

(d) a particular class or a particular level requires a greater portion of said resources than its allocated portion;

such that said level is allocated the total of the respective portions allocated to its associated classes;

the method comprising;

(i) receiving a request to accept a call associated with a particular level;

(ii) applying a criterion for acceptance of the call; and

(iii) accepting the call only if the criterion is satisfied, thereby permitting said particular class or said particular level to share netwotk resources exceeding its allocated portion, wherein;

(A) said criterion invokes a reservation parameter specifically associated with said particular class or said particular level; and

(B) the reservation parameter represents a quantity of network resources that is excluded from sharing by said particular class or said particular level.

20. The method of claim 19 wherein said hierarchical network is characterized by a network state and wherein said reservation parameter associated with said particular level and said reservation parameter associated with said particular class associated with said particular level are each a function of said network state.