Method for controlling data flow associated with a communications node

• US 6,700,869 B1
• Filed: 10/01/1999
• Issued: 03/02/2004
• Est. Priority Date: 10/01/1999
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Tu, Ming-Hsu, Strickland, Stephen Gregory, Falco, Steven Anthony
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): LY, ANH VU H
• Application Number:
  US09/410,615
• Time in Patent Office: 1,614 Days
• Field of Search: 370/230, 370/230.1, 370/231, 370/232, 370/235, 370/363, 370/368, 370/371, 370/374, 370/378, 370/381, 370/412, 370/413, 370/414, 370/428, 370/429
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes

Abstract

A communications node admits the receive data message to the buffer memory if the receive arriving message falls within the capacity range of a class of the receive data messages and if the buffer memory is not congested. A state detector detects if the buffer memory is congested by evaluating the occupancy rate of the buffer memory, or otherwise. The capacity range determines the utilization of buffer memory by a particular class of data messages, which may be defined in accordance with an estimated economic value rating of the data messages.

Claims

1. A method for controlling data flow in a store-and-forward communications node, the method comprising the steps of:

assigning priority value ratings for determining whether to admit a receive data message to a buffer memory of a communications node;

detecting if the buffer memory is congested;

defining a storage capacity range for each class of priority value ratings of the receive data messages;

admitting the receive data message to the buffer memory if the arriving receive data message falls within the capacity range and if the buffer memory is not congested; and

displacing a stored data message in the buffer memory with the arriving receive data message if the arriving receive data message has a first assigned rating value higher than a second assigned value rating of the stored data message and if the buffer memory is congested.

2. The method according to claim 1 wherein the assigning step comprises assigning intra-class priority ranks to establish an admission hierarchy of receive data messages within a particular class.

3. The method according to claim 1 wherein the detecting step comprises:

determining that the buffer memory is congested if an actual occupancy rate of the buffer memory exceeds a threshold occupancy rate.

4. The method according to claim 1 wherein the detecting step comprises:

determining that the buffer memory is congested if an actual occupancy rate of a queue exceeds a queue threshold occupancy rate, the queue being suitable for accepting the receive data message based on its priority class.

5. The method according to claim 1 wherein the detecting step comprises:

determining that the buffer memory is congested if an actual occupancy rate of a combination of queue occupancy rates exceeds a threshold combination occupancy rate, each queue of the combination being suitable for accepting the receive data message based on its priority class.

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

displacing a stored data message in the buffer memory with an arriving receive data message if the arriving receive data message has a first assigned rating value higher than a second assigned value rating of the stored data message and if at least one queue within the buffer memory is congested.

7. The method according to claim 1 further comprising the step of:

assigning the priority value rating to the receive data message based on a revenue generating factor associated with the receive data message.

8. The method according to claim 1 further comprising the step of:

assigning a higher value rating to a first receive data message representing a channel assignment than a second receive data message representing a paging request.

9. The method according to claim 8 wherein the admitting step further comprises:

displacing the second receive data message from the buffer memory upon arrival of the first receive data message at an input, if the detection step determines the buffer memory is congested.

10. The method according to claim 1 wherein the admitting step further comprises:

distributing displacement of receive data messages from the buffer memory among a plurality of queues within the buffer memory when receive data messages with higher value ratings displace data messages with lower value ratings.

11. The method according to claim 1 wherein the defining step comprises:

limiting a maximum number of receive data messages per priority class to be admitted to the buffer memory to comply with an upper boundary of the storage capacity range.

12. The method according to claim 11 further comprising the step of:

not admitting a data message into the buffer memory if the number of stored data messages in the buffer memory for the priority class associated with the held data message exceeds the maximum number.

13. The method according to claim 1 wherein the defining step further comprises:

limiting a maximum storage capacity size for receive data messages per priority class to be admitted to the buffer memory to comply with an upper boundary of the storage capacity range.

14. The method according to claim 13 further comprising the step of:

setting the maximum storage capacity size as one third of the overall memory buffer capacity.

15. The method according to claim 1 wherein the defining step comprises:

reserving a minimum number of queues for data messages of at least one priority class as a lower boundary of the range.

16. The method according to claim 1 wherein the defining step further comprises:

reserving a minimum class storage capacity size for data messages of at least one priority class as a lower boundary of the range.

17. The method according to claim 16 wherein the minimum class storage capacity size is defined as a number of buffers reserved in accordance with the following formula:

$n_i+\underset{j\ne <br><br>i}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\max <br><br>\left(b_j,n_j\right)<<br><br>K,$

wherein b_j is a buffer reserve for priority class j distinct from priority class i, n_i is the current number of buffers used by class i, n_j is the current number of buffers used by class j and K is the total buffer capacity of the buffer memory.

18. The method according to claim 1 wherein the admitting step further comprises:

displacing a stored data message from the buffer memory upon arrival of a later receive data message at an input, where the stored data message has an oldest arrival time within the priority class.

19. The method according to claim 1 wherein the admitting step further comprises:

displacing a stored data message from the buffer memory upon arrival of a later receive data message at an input, where the stored data message has an oldest arrival time within a queue in the buffer memory.

20. The method according to claim 1 wherein the admitting step further comprises:

displacing a stored data message from the buffer memory upon arrival of a later receive data message at an input, where the stored data message has an oldest arrival time in the entire buffer memory.

21. The method according to claim 1 further comprising the step of:

displacing a stored data message in a buffer memory with an arriving receive data message if the arriving receive data message has a more recent arrival time than that of the stored data message and if the buffer memory is congested.

22. A communications node comprising:

an overload controller for assigning priority value ratings for determining whether to admit a receive data message to a buffer memory of a communications node, the overload controller defining a storage capacity range for each class of priority value ratings of the receive data messages;

a detector for detecting if the buffer memory is congested;

a gatekeeper for admitting the receive data message to the buffer memory if the arriving receive data message falls within the capacity range and if the buffer memory is not congested; and

a memory manager for displacing a stored data message in the buffer memory with the arriving receive data message if the arriving receive data message has a first assigned rating value higher than a second assigned value rating of a stored data message and if the buffer memory is congested.

23. The communications node of claim 22 further comprising:

a holding memory for holding the receive data message prior to admittance to the buffer memory.

24. The communications node of claim 23 wherein, the memory manager is for deleting an existing data message in the buffer memory to make room for a more recent receive data message in the holding memory of the communications node.

25. The communications node of claim 22 wherein, the memory manager is for deleting an existing data message in the buffer memory to make room for a more recent receive data message at an input of the communications node.

26. The communications node of claim 22 where in the detector is adapted to detect the occupancy rate of the buffer memory.

27. The communications node of claim 22 where in the detector is adapted to detect the occupancy rate of a group of queues within the buffer memory.

28. A method for controlling data flow in a store-and-forward communications node, the method comprising:

reserving a minimum class storage capacity size for data messages of at least one priority class as a lower boundary of a range;

wherein the minimum class storage capacity is defined as a number of buffers reserved in accordance with the following formula;

$n_i+\underset{j\ne <br><br>i}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\max <br><br>\left(b_j,n_j\right)<<br><br>K,$

wherein b_j is a buffer reserve for priority class j distinct from priority class i, n_i is the current number of buffers used by class i, n_j is the current number of buffers used by class j and K is the total buffer capacity of the buffer memory.