Method and system for dynamically allocating bandwidth to a plurality of network elements

• US 20030200317A1
• Filed: 04/19/2002
• Published: 10/23/2003
• Est. Priority Date: 04/19/2002
• Status: Abandoned Application

• Current Assignee: Native Network Technologies, Inc., Alcatel SA (Nokia Corporation)
• Original Assignee: Native Network Technologies, Inc.
• Inventors: Gat, Omri, Zeitak, Reuven
• Application Number:
  US10/126,488
• Publication Number:
  US 20030200317A1
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 47/627 policing
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/762 triggered by the network
• 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/828 Allocation of resources per group of connections, e.g. per group of users
• CPC Class Codes: H04L 69/24 Negotiation of communication capabilities
• CPC Class Codes: H04W 16/02 Resource partitioning among network components, e.g. reuse partitioning
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 28/16 Central resource management; Negotiation of resources or communication parameters, e.g. negotiating bandwidth or QoS [Quality of Service]
• CPC Class Codes: H04W 28/20 Negotiating bandwidth
• CPC Class Codes: H04W 72/0453 Resources in frequency domain, e.g. a carrier in FDMA

Abstract

The invention allocates a portion of the common bandwidth resource to each network element, and each network element distributes its allocated portion locally using a fair distribution algorithm. In accordance with the invention, each network element determines its “local satisfaction”. “Global fairness” is achieved when local satisfaction is balanced between all of the network elements. This balance can include situations where the satisfaction values of all of the network elements are equal. This balance can also include situations where the working priority class of each of the backlogged network elements is the same. In one embodiment, the invention dynamically allocates portions of the common bandwidth resource using a control algorithm that strives to keep the satisfaction values equal among the network elements.

Claims

1. A method to achieve global fairness in allocating a network bandwidth in a communications network having a plurality of network elements, each network element associated with one or more sources, the method comprising:

determining a satisfaction value for each of the network elements in response to a communication parameter, each of the network elements using the communication parameter to approximate virtual time for its respective one or more sources; and

determining an allocation of a portion of the network bandwidth for each of the network elements in response to a respective one of the satisfaction values.

2. The method of claim 1 further comprising determining a working priority class of each of the plurality of network elements.

3. The method of claim 2 further comprising measuring the communications parameter in response to a working priority class.

4. The method of claim 1 further comprising:

receiving a collect messenger data packet;

obtaining one or more of the satisfaction values from the received collect messenger data packet; and

transmitting an action messenger packet to each of the plurality of network elements, the action messenger packet indicating the respective allocation for each of the plurality of network elements.

5. The method of claim 4 further comprising transmitting a collect messenger data packet to each of a plurality of network elements.

6. The method of claim 4 further comprising modifying, at one of the plurality of network elements, the collect messenger data packet in response to a respective satisfaction value.

7. The method of claim 4 wherein the steps of receiving, determining the satisfaction value, determining the allocation, obtaining and transmitting are all performed at only one of the network elements.

8. The method of claim 4 wherein the steps of receiving, determining the satisfaction value, determining the allocation, obtaining and transmitting are distributed over more than one of the network elements.

9. The method of claim 1 wherein the step of determining a satisfaction value comprises determining a satisfaction value for a first network element in response to a parameter of a queuing algorithm used by the first network element on its one or more sources.

10. The method of claim 9 wherein the step of determining the satisfaction value for the first network element comprises:

determining a number of round-robin rounds completed by the first network element in a predetermined time interval; and

employing the number of round-robin rounds in the predetermined time interval as the parameter.

11. The method of claim 9 wherein the step of determining the satisfaction value for the first network element comprises:

determining a proportion of time between a predefined time interval that the first network element is in an unstressed condition; and

employing the proportion of time in an unstressed condition as the parameter.

12. The method of claim 9 further comprising:

determining a satisfaction value for a second network element in response to a parameter of a queuing algorithm used by the second network element on its one or more sources;

determining an allocation of a portion of the network bandwidth for the second network element in response to its respective satisfaction value; and

determining a first change to an allocation for the first network element in response to the satisfaction value for the first network element and the satisfaction value for the second network element.

13. The method of claim 12 further comprising determining the global working priority class of the communications network, wherein the satisfaction value for the first network element and the satisfaction value for the second network element are in response to the global working priority class.

14. The method of claim 12 wherein the step of determining the first change further comprises determining the first change such that the difference between a second satisfaction value of the first network element and a second satisfaction value of the second network element is less than a difference between the first satisfaction value of the first network element and the first satisfaction of the second network element.

15. The method of claim 12 wherein the first change to the allocation for the first network element is equal to a predetermined bandwidth value.

16. The method of claim 15 further comprising modifying the predetermined bandwidth value to control the rate at which a future satisfaction value of the first network element and a future satisfaction value of the second network element are made equal.

17. The method of claim 12 further comprising determining a second change to the allocation for the first network element in response to a second satisfaction value for the first network element and a second satisfaction value for the second network element.

18. The method of claim 17 further comprising determining a magnitude of the second change to the first bandwidth allocation for the first network element in response to the polarity of the first and second changes to the allocation for the first network element.

19. The method of claim 9 further comprising:

determining a satisfaction value for a second network element in response to a parameter of a queuing algorithm used by the second network element on its one or more sources;

determining a satisfaction value for a third network element in response to a parameter of a queuing algorithm used by the third network element on its one or more sources;

determining an allocation of a portion of the network bandwidth for the second network element in response to the respective satisfaction values of the first network element, the second network element and the third network element; and

determining an allocation of a portion of the network bandwidth for the third network element in response to the respective satisfaction values of the first network element, the second network element and the third network element,

wherein the determining an allocation of a portion of the network bandwidth for the first network element step comprises determining an allocation of a portion of the network bandwidth for the first network element in response to the respective satisfaction values of the first network element, the second network element and the third network element.

20. A system for allocating bandwidth in a communications network comprising:

a first network element interactive with one or more sources; and

a second network element in communication with the first network element, the second network element being interactive with one or more sources and including an allocation module configured to obtain a satisfaction value for the first network element in response to a parameter of a queuing algorithm used by the first network element on the one or more sources associated therewith, and to determine an allocation of a portion of the network bandwidth for the first network element in response to the satisfaction value.

21. The first network element of claim 20 further comprising a satisfaction value generator module, the satisfaction value generator module determining the satisfaction value for the first network element.

22. The first network element of claim 20 further comprising a satisfaction value generator module, the satisfaction value generator module determining a number of round-robin rounds completed by the first network element in a predefined time interval and employing the number of round-robin rounds in the predefined time interval as the parameter.

23. The first network element of claim 20 further comprising a satisfaction value generator module, the satisfaction value generator module determining a proportion of time between a predefined time interval that the first network element is in an unstressed condition and employing the proportion of time in an unstressed condition as the parameter.

24. The system of claim 20 wherein the second network element is further configured to transmit a collect messenger data packet to the first network element and receive a modified collect messenger data packet transmitted by the first network element, the second network element generating an action messenger data packet in response thereto.

25. The system of claim 24 wherein the second network element comprises a trigger clock, the trigger clock initiating the transmitting of the collect messenger data packet to the first network element.

26. The system of claim 20 further comprising:

a third network element including one or more sources, and

wherein the second network element is further configured (i) to be in communication with the third network element, (ii) to obtain a satisfaction value for the third network element in response to a parameter of a queuing algorithm used by the third network element on its one or more sources, (iii) to determine an allocation of a portion of the network bandwidth for the first network element in response to the satisfaction values of the first network element, the second network element and the third network element, (iv) to determine an allocation of a portion of the network bandwidth for the second network element in response to the satisfaction values of the first network element, the second network element and the third network element and (v) to determine an allocation of a portion of the network bandwidth for the third network element in response to the satisfaction values of the first network element, the second network element and the third network element.

27. A common point for allocating a network bandwidth in a communications network having a plurality of network elements, the common point comprising an allocation module configured (i) to receive data indicative of a satisfaction value from each of the network elements and (ii) to determine a portion of the network bandwidth for each of the network elements in response to its respective satisfaction value.

28. The common point of claim 27 wherein the allocation module is further configured (i) to receive data indicative of a working class priority from each of the network elements and (ii) to determine a portion of the network bandwidth for each of the network elements in response to its respective satisfaction value and working class priority.

29. An article of manufacture having computer-readable program portion contained therein for allocating a network bandwidth in a communications network having a plurality of network elements, the article comprising:

a computer-readable program portion for determining a satisfaction value for a first network element in response to a parameter of a queuing algorithm used by the first network element on its one or more sources; and

a computer-readable program portion for determining an allocation of a portion of the network bandwidth for the first network element in response to the satisfaction value.