Dynamic bandwidth reallocation

• US 20040028054A1
• Filed: 08/12/2002
• Published: 02/12/2004
• Est. Priority Date: 08/12/2002
• Status: Active Grant

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Samtani, Sunil, Talpade, Rajesh, Khurana, Sumit
• Granted Patent: US 7,359,322 B2
• Time in Patent Office: Days
• US Class Current: 370/395.21
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/765 triggered by the end-points
• 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: H04L 47/825 Involving tunnels, e.g. MPLS

Abstract

Bandwidth allocated between the traffic classes of a network path is dynamically reallocated when one or more traffic classes have insufficient available bandwidth to support a service request for the traffic classes, wherein the reallocation occurs without modifying the traffic class bandwidth allocations enforced by router mechanisms. A provisioning system maintains an available bandwidth indication for each traffic class, which indications are decremented as a service request is admitted to the path. If a requested traffic class has insufficient available bandwidth to support a request, one or more other traffic classes can loan bandwidth to the requested traffic class by decrementing the available bandwidth indicators for the one or more other traffic classes in the amount of the insufficiency, thereby indicating that less bandwidth is available in these classes for future requests. The provisioning system also maintains an indication of the amount of bandwidth each traffic class loans to the other traffic classes.

Claims

1. A method for the reallocation of bandwidth between different traffic classes that comprise a path in a packet network in order to admit a service request for the bandwidth of one or more of said traffic classes, said method comprising the steps of:

storing for each traffic class an available bandwidth indicator that indicates the amount of bandwidth available within that traffic class;

determining if the available bandwidth for a specific traffic class is sufficient to meet the bandwidth requested for said specific traffic class;

if the available bandwidth for said specific traffic class is insufficient to meet the corresponding requested bandwidth, determining if there is excess available bandwidth in one or more other traffic classes sufficient to meet the insufficiency;

if there is sufficient excess available bandwidth in one or more other traffic classes to meet the insufficiency, reallocating bandwidth from these one or more other traffic classes to said specific traffic class in an amount equal to the insufficiency by decrementing the available bandwidth indicator for the one or more other traffic classes in the amount reallocated from these traffic classes; and

admitting the new service request to the network.

2. The method of claim 1 wherein the reconfiguration occurs without reconfiguring the network.

3. The method of claim 1 further comprising the steps of:

if said specific traffic class has sufficient bandwidth to meet the corresponding bandwidth request, decrementing said specific traffic class'"'"' available bandwidth indicator by the amount of the bandwidth request; and

if said specific traffic class has insufficient bandwidth to meet the corresponding bandwidth request, decrementing said specific traffic class'"'"' available bandwidth indicator to zero.

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

storing for each traffic class a plurality of bandwidth loan indicators wherein each loan indicator for a given traffic class specifies the amount of bandwidth reallocated from said given traffic class to another traffic class within the path; and

wherein said reallocating bandwidth step further comprises the step of incrementing the bandwidth loan indicator for the one or more other traffic classes in the amount reallocated from these traffic classes.

5. The method of claim 4 wherein the decrement in the available bandwidth indicators and the increment in the bandwidth loan indicators are not associated with the service request.

6. The method of claim 1 wherein the traffic classes are organized in a higher to lower hierarchical order and wherein bandwidth reallocation occurs from lower order traffic classes to higher order traffic classes.

7. The method of claim 1 wherein the bandwidth of one or more traffic classes is static and cannot be increased or decreased through bandwidth reallocation.

8. The method of claim 1 wherein the packet network comprises a plurality of internal and edge routers configured to perform multi-protocol label switching, wherein the edge routers are further configured to perform differentiated services (Diffserv), wherein the path is a label switched path, and wherein said admitting step comprises the step of performing Diffserv based policing and marking configurations on the edge routers.

9. The method of claim I wherein the packet network comprises a plurality of routers configured with weighted fair queuing or dynamic round robin in order to provide the traffic classes.

10. A system for reallocating bandwidth between different traffic classes that comprise a path in a packet network in order to admit a service request for the bandwidth of one or more of said traffic classes, said system comprising:

a database for storing an available bandwidth indicator for each traffic class;

means for determining if the available bandwidth for any traffic class, as specified by the corresponding available bandwidth indicator, is deficient in that there is not sufficient bandwidth in said any traffic class to meet the bandwidth requested for said any traffic class;

means for determining if there is excess available bandwidth in one or more other traffic classes sufficient to meet any bandwidth deficiencies;

means for reallocating bandwidth, sufficient to meet any bandwidth deficiencies, from said one or more other traffic classes with excess available bandwidth to traffic classes with deficient bandwidth, said means for reallocating comprising means for decrementing the available bandwidth indicators for the traffic classes with excess available bandwidth in an amount equal to the bandwidth deficiencies; and

a configuration interface comprising means for configuring the network for the new service request.

11. The system of claim 10 further comprising:

means for decrementing a traffic class'"'"' available bandwidth indicator by the amount of the bandwidth requested for that traffic class when the traffic class has sufficient bandwidth to meet the bandwidth requested, and for decrementing a traffic class'"'"' available bandwidth indicator to zero when the traffic class has insufficient bandwidth to meet the bandwidth requested.

12. The system of claim 10 wherein the database further stores for each traffic class a plurality of bandwidth loan indicators wherein each loan indicator for a given traffic class specifies the amount of bandwidth reallocated from the traffic class to another traffic class within the path, and wherein the means for reallocating bandwidth further comprises means for incrementing the loan indicators for the traffic classes with excess available bandwidth in an amount equal to the bandwidth deficiencies.

13. The system of claim 12 wherein an admitted service request may be removed from the network, said system further comprising:

means for determining, upon removing the admitted service request from the network, each traffic class that has had bandwidth reallocated to another traffic class to which bandwidth is being returned as a result of removing the service request from the network;

means for returning bandwidth to one or more of the determined traffic classes that have had bandwidth reallocated to another traffic class, said means comprising;

means for decrementing the bandwidth loan indicators for the one or more determined traffic classes by an amount up to but not exceeding the amount of bandwidth being returned by the, service request; and

means for incrementing the available bandwidth indicators for the one or more determined traffic classes in an amount equal to the amount the corresponding loan indicators were decremented; and

wherein the configuration interface further comprises means for removing the service request from the network.

14. The system of claim 10 wherein the system does not associate the decrement in the available bandwidth indicators and the increment in the bandwidth loan indicators with the service request.

15. The system of claim 10 wherein the system organizes the traffic classes in a higher to lower hierarchical order and wherein the system reallocates bandwidth from lower order traffic classes to higher order traffic classes.

16. The system of claim 10 wherein the system statically maintains the bandwidth of one or more traffic classes and does not increment or decrement through reallocation the bandwidth of said on or more traffic classes whose bandwidth is statically maintained.

17. The system of claim 10 wherein the packet network comprises a plurality of internal and edge routers configured to perform multi-protocol label switching, wherein the edge routers are further configured to perform differentiated services (Diffserv), wherein the path is a label switched path, and wherein said configuration interface further comprises means for performing Diffserv based policing and marking configurations on the edge routers.

18. A method for reallocating bandwidth between a plurality of traffic classes that comprise a label switched path (LSP) within a multi-protocol label switching and differentiated services based network, wherein the reallocation occurs in response to receiving a bandwidth request for one or more traffic classes of the LSP, said method comprising the steps of:

determining whether a requested traffic class has sufficient available bandwidth to support the bandwidth request for that traffic class by examining an available bandwidth indicator for that traffic class;

if a requested traffic class has insufficient bandwidth to support the bandwidth request for that traffic class, determining whether one or more other traffic classes can loan the insufficient bandwidth to the requested traffic class, said determination being made by examining the available bandwidth indicators for the one or more other traffic classes;

if the one or more other traffic classes have insufficient bandwidth to loan to the requested traffic class, denying the bandwidth request; and

if the one or more other traffic classes have sufficient bandwidth to loan to the requested traffic class, decrementing the available bandwidth indicators for the one or more other traffic classes in the amount of the insufficiency and admitting the request.

19. The method of claim 18 wherein said decrementing step further comprises the step of:

incrementing a bandwidth loan indicator for each of the one or more other traffic classes in the amount of the insufficiency.

20. The method of claim 18 further comprising the steps of:

if a requested traffic class has sufficient available bandwidth to support the bandwidth request for that traffic class, decrementing the available bandwidth indicator for that traffic class by an amount equal to the bandwidth request; and

if a requested traffic class has insufficient bandwidth to support the bandwidth requested for that traffic class, decrementing the requested traffic class'"'"' available bandwidth indicator to zero.