Methods and systems providing fair queuing and priority scheduling to enhance quality of service in a network

• US 6,810,426 B2
• Filed: 01/30/2002
• Issued: 10/26/2004
• Est. Priority Date: 01/30/2001
• Status: Active Grant

• Current Assignee: Nomadix, Inc. (Nippon Telegraph and Telephone Corporation)
• Original Assignee: Nomadix, Inc. (Nippon Telegraph and Telephone Corporation)
• Inventors: Short, Joel E., Bhagavath, Vijay Krishna, Mysore, Manamohan D., Pagan, Florence C.
• Primary Examiner(s): Barot, Bharat
• Application Number:
  US10/060,273
• Publication Number:
  US 20020178282A1
• Time in Patent Office: 1,000 Days
• Field of Search: 709/227-228, 709/231-238, 709/242, 707/1, 707/3-7, 707/10, 707/101-102, 707/200-201, 370/229-231, 370/412-413
• US Class Current: 709/234
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6265 past bandwidth allocation
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Integrated Bandwidth Latency Scheduler apparatus, method and system (collectively, IBLS) combines Fair Queuing and Priority Schedulers in a single stage to provide bandwidth fairness guarantees as well as latency prioritization. The IBLS includes a scheduler and process that dequeues packets from multiple queues in an order based upon an algorithm of the IBLS that arranges and dequeues those queues having the highest priority based on content therein. The IBLS also utilizes quotas and deficit counters to ensure that packets from each source receive their fair portion of the outgoing link bandwidth. To determine which first in first out queue an incoming data packet is placed, the enqueue agent utilized by the present invention classifies incoming packets based on the type of data included within the data packet, the source of the packet, the type of data flow, or another attribute of the packet, such as a header associated with the packet. Additionally, a weighted fair queuing algorithm provides express paths to latency critical components of user flows while providing overall bandwidth guarantees, and uses bandwidth borrowing from non-critical flows to ensure latency prioritization for high priority flows.

Claims

1. A method for limiting latency for latency-critical network traffic, comprising:

receiving at a queue structure a plurality of data packets associated with at least one source, wherein said queue structure comprises a plurality of queues, and wherein each queue of said plurality of queues is ranked in said queue structure;

identifying an attribute associated with one of said plurality of data packets;

determining a queue of said plurality of queues to receive said one of said plurality of data packets, wherein said queue is identified based upon said attribute, and wherein said queue is ranked in said queue structure based at least in part upon said attribute;

placing said one of said plurality of data packets into said queue; and

dequeuing said one of said plurality of data packets from said queue structure based at least in part upon the rank of said queue in said queue structure.

2. The method of claim 1, further comprising the step of identifying one or more queues prepared to immediately transmit at least one data packet prior to dequeuing said one of said plurality of data packets.

3. The method of claim 2, wherein the step of dequeuing each data packet comprises dequeuing data packets from said one or more queues that are prepared to immediately transmit at least one data packet based at least in part upon the rank of said one or more queues in said queue structure.

4. The method of claim 1, further comprising the step of maintaining a deficit array, wherein the deficit array contains a respective deficit amount representing the quantity of data, within one or more data packets, that may be immediately dequeued from each queue within the queue structure.

5. The method of claim 4, further comprising the step of updating a deficit bitmap, wherein said deficit bitmap maintains a plurality of bits, wherein each bit represents whether the deficit amount exceeds the quantity of data within an initial data packet that may be immediately dequeued from a corresponding queue within the queue structure.

6. The method of claim 1, further comprising the step of maintaining a quota array, wherein a respective quota amount of the quota array represents an additional quantity of data, within one or more data packets, that may be consecutively dequeued from a respective queue within the queue structure.

7. The method of claim 6, further comprising the step of maintaining a queue bitmap wherein said queue bitmap maintains a plurality of bits, wherein each bit represents whether a corresponding queue within the queue structure has a packet of data.

8. The method of claim 1, wherein the identifying an attribute associated with one of said plurality of data packets comprises identifying the attribute within a header of said one of said plurality of data packets.

9. The method of claim 8, wherein identifying an attribute associated with one of said plurality of data packets comprises identifying, within the header, that said one of said plurality of data packets is a Voice Over Internet Protocol, Hyper Text Transfer Protocol, File Transfer Protocol, or Citrix data type.

10. The method of claim 1, further comprising the step of establishing a byte limit for each queue in said queue structure prior to the step of placing said one of said plurality of data packets into said queue.

11. The method of claim 10, wherein the step of placing said one of said plurality of data packets into said queue comprises the step of determining whether said one of plurality of data packets includes a number of bytes that exceeds the byte limit for said queue.

12. The method of claim 1, further comprising the step of maintaining a deficit for each queue, wherein said deficit represents the quantity of data, within one or more data packets, that may be immediately dequeued from each respective queue within the queue structure.

13. The method of claim 12, further comprising the step of maintaining a quota for each queue, wherein said quota represents an additional quantity of data, within one or more data packets, that may be consecutively dequeued from a respective queue within the queue structure.

14. The method of claim 13, wherein said step of dequeuing comprises dequeuing subsequent data packets from said queue structure based upon the rank of each other queue in said queue structure.

15. The method of claim 14, wherein the step of dequeuing further comprises updating the deficit of each empty queue to the quota.

16. The method of claim 14, wherein the step of dequeuing further comprises adding the quota to the deficit of each non-empty queue.

17. The method of claim 14, wherein dequeuing subsequent data packets from said queue structure based upon the rank of each other queue in said queue structure comprises repeatedly dequeuing subsequent data packets from said queue structure until said initial data packets in each respective queue are larger than the deficit for respective queues.

18. The method of claim 1, further comprising the step of identifying whether said attribute indicates whether said one of said plurality of data packets represents data that is latency critical or latency non-critical.

19. The method of claim 18, further comprising the steps of:

establishing a latency critical second stage queue structure; and

receiving at said latency critical second stage queue structure said one of said plurality of data packets where said attribute indicates that said one of said plurality of data packets represents data that is latency critical.

20. The method of claim 19, further comprising the steps of:

establishing a latency non-critical second stage queue structure; and

receiving at said latency non-critical second stage queue structure said one of said plurality of data packets where said attribute indicates that said one of said plurality of data packets represents data that is latency non-critical.

21. The method of claim 20, wherein said step of establishing a latency non-critical second stage queue structure comprises establishing a latency non-critical second stage queue structure comprising a plurality of latency non-critical queues.

22. The method of claim 21, further comprising the step of maintaining a non-critical queue structure deficit for each latency non-critical queue, wherein said deficit represents the quantity of data, within one or more data packets, that may be immediately dequeued from each respective queue within the non-critical second stage queue structure.

23. The method of claim 22, further comprising the step of maintaining a critical queue structure quota for each latency critical queue within said critical queue structure quota, wherein said quota represents an additional quantity of data, within one or more data packets, that may be consecutively dequeued from a respective queue within the critical second stage queue structure.

24. The method of claim 23, further comprising the steps of borrowing at least a portion of said non-critical queue structure deficit and adding said portion to said critical queue structure quota.

25. The method of claim 20, wherein the step of receiving comprises receiving at said latency non-critical second stage queue structure said one of said plurality of data packets subsequent to said one of said plurality of data packets being dequeued from said queue structure.

26. The method of claim 1, further comprising the step of mapping each one of said plurality of queues within said queue structure to an associated element within an active priority bucket, wherein said associated element points to an active list or inactive list associated with said active priority bucket, wherein said active list identifies the queues prepared to immediately dequeue a data packet, and wherein said inactive list identifies the queues that contain data packets but are not prepared to immediately dequeue the data packets.

27. A computer program product for limiting latency for latency-critical network traffic, comprising:

a computer readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising;

computer readable program code means for receiving at a queue structure a plurality of data packets associated with at least one source, wherein said queue structure comprises a plurality of queues, and wherein each queue of said plurality of queues is ranked in said queue structure;

computer readable program code means for identifying an attribute associated with one of said plurality of data packets; and

computer readable program code means for determining a queue of said plurality of queues to receive said one of said plurality of data packets, wherein said queue is identified based upon said attribute, and wherein said queue is ranked in said queue structure based at least in part upon said attribute;

computer readable program code means for placing said one of said plurality of data packets into said queue; and

computer readable program code means for dequeuing said one of said plurality of data packets from said queue structure based at least in part upon the rank of said queue in said queue structure.

28. The computer program product of claim 27, further comprising computer readable program code means for identifying one or more queues prepared to immediately transmit at least one data packet prior to dequeuing said one of said plurality of data packets.

29. The computer program product of claim 28, wherein the computer readable program code means for dequeuing each data packet comprises computer readable program code means for dequeuing data packets from said one or more queues that are prepared to immediately transmit at least one data packet based at least in part upon the rank of said one or more queues in said queue structure.

30. The computer program product of claim 27, further comprising computer readable program code means for maintaining a deficit array, wherein the deficit array contains a respective deficit amount representing the quantity of data, within one or more data packets, that may be immediately dequeued from each queue within the queue structure.

31. The computer program product of claim 30, further comprising computer readable program code means for updating a deficit bitmap, wherein said deficit bitmap maintains a plurality of bits, wherein each bit represents whether the deficit amount exceeds the quantity of data within an initial data packet that may be immediately dequeued from a corresponding queue within the queue structure.

32. The computer program product of claim 27, further comprising computer readable program code means for maintaining a quota array, wherein a respective quota amount of the quota array represents an additional quantity of data, within one or more data packets, that may be consecutively dequeued from a respective queue within the queue structure.

33. The computer program product of claim 32, further comprising computer readable program code means for maintaining a queue bitmap wherein said queue bitmap maintains a plurality of bits, wherein each bit represents whether a corresponding queue within the queue structure has a packet of data.

34. The computer program product of claim 27, wherein the computer readable program code means for identifying an attribute associated with one of said plurality of data packets comprises computer readable program code means for identifying the attribute within a header of said one of said plurality of data packets.

35. The computer program product of claim 34, wherein the computer readable program code means for identifying an attribute associated with one of said plurality of data packets comprises computer readable program code means for identifying, within the header, that said one of said plurality of data packets is a Voice Over Internet Protocol, Hyper Text Transfer Protocol, File Transfer Protocol, or Citrix data type.

36. The computer program product of claim 27, wherein the computer readable program code means for identifying an attribute associated with one of said plurality of data packets comprises computer readable program code means for establishing a byte limit for each queue in said queue structure prior to the step of placing said one of said plurality of data packets into said queue.

37. The computer program product of claim 36, wherein the computer readable program code means for placing said one of said plurality of data packets into said queue comprises computer readable program code means for determining whether said one of plurality of data packets includes a number of bytes that exceeds the byte limit for said queue.

38. The computer program product of claim 27, further comprising computer readable program code means for maintaining a deficit for each queue, wherein said deficit represents the quantity of data, within one or more data packets, that may be immediately dequeued from each respective queue within the queue structure.

39. The computer program product of claim 38, further comprising computer readable program code means for maintaining a quota for each queue, wherein said quota represents an additional quantity of data, within one or more data packets, that may be consecutively dequeued from a respective queue within the queue structure.

40. The computer program product of claim 39, wherein said computer readable program code means for dequeuing comprises computer readable program code means for dequeuing subsequent data packets from said queue structure based upon the rank of each other queue in said queue structure.

41. The computer program product of claim 40, wherein said computer readable program code means for dequeuing further comprises computer readable program code means for updating the deficit of each empty queue to the quota.

42. The computer program product of claim 40, wherein said computer readable program code means for dequeuing further comprises computer readable program code means for adding the quota to the deficit of each non-empty queue.

43. The computer program product of claim 40, wherein said computer readable program code means for dequeuing subsequent data packets from said queue structure based upon the rank of each other queue in said queue structure comprises computer readable program code means for repeatedly dequeuing subsequent data packets from said queue structure until said initial data packets in each respective queue are larger than the deficit for respective queues.

44. The computer program product of claim 27, further comprising computer readable program code means for identifying whether said attribute indicates whether said one of said plurality of data packets represents data that is latency critical or latency non-critical.

45. The computer program product of claim 44, further comprising:

computer readable program code means for establishing a latency critical second stage queue structure; and

computer readable program code means for receiving at said latency critical second stage queue structure said one of said plurality of data packets where said attribute indicates that said one of said plurality of data packets represents data that is latency critical.

46. The computer program product of claim 45, further comprising:

computer readable program code means for establishing a latency non-critical second stage queue structure; and

computer readable program code means for receiving at said latency non-critical second stage queue structure said one of said plurality of data packets where said attribute indicates that said one of said plurality of data packets represents data that is latency non-critical.

47. The computer program product of claim 46, wherein said computer readable program code means for establishing a latency non-critical second stage queue structure comprises computer readable program code means for establishing a latency non-critical second stage queue structure comprising a plurality of latency non-critical queues.

48. The computer program product of claim 47, further comprising computer readable program code means for maintaining a non-critical queue structure deficit for each latency non-critical queue, wherein said deficit represents the quantity of data, within one or more data packets, that may be immediately dequeued from each respective queue within the non-critical second stage queue structure.

49. The computer program product of claim 48, further comprising computer readable program code means for maintaining a critical queue structure quota for each latency critical queue within said critical queue structure quota, wherein said quota represents an additional quantity of data, within one or more data packets, that may be consecutively dequeued from a respective queue within the critical second stage queue structure.

50. The computer program product of claim 49, further comprising computer readable program code means for borrowing at least a portion of said non-critical queue structure deficit and adding said portion to said critical queue structure quota.

51. The computer program product of claim 46, wherein the computer readable program code means for receiving comprises computer readable program code means for receiving at said latency non-critical second stage queue structure said one of said plurality of data packets subsequent to said one of said plurality of data packets being dequeued from said queue structure.

52. The computer program product of claim 27, further comprising computer readable program code means for mapping each one of said plurality of queues within said queue structure to an associated element within an active priority bucket, wherein said associated element points to an active list or inactive list associated with said active priority bucket, wherein said active list identifies the queues prepared to immediately dequeue a data packet, and wherein said inactive list identifies the queues that contain data packets but are not prepared to immediately dequeue the data packets.

53. A system for limiting latency for latency-critical network traffic, comprising:

a queue structure comprising a plurality of ranked queues, wherein said queue structure receives a plurality of data packets from a source;

an enqueue agent, wherein said enqueue agent identifies an attribute associated with one of said plurality of data packets, and wherein said enqueue agent determines a queue of said plurality of queues to receive said one of said plurality of data packets, wherein said queue is identified based upon said attribute, and wherein said queue is ranked in said queue structure based at least in part upon said attribute; and

a dequeue agent, wherein said dequeuing agent dequeues said one of said plurality of data packets from said queue structure based at least in part upon the rank of said queue in said queue structure.

54. The system of claim 53, wherein the dequeue agent is operable to dequeue data packets from said one or more queues that are prepared to immediately transmit at least one data packet based at least in part upon the rank of said one or more queues in said queue structure.

55. The system of claim 53, further comprising a deficit array, wherein the deficit array contains a respective deficit amount representing the quantity of data, within one or more data packets, that may be immediately dequeued from each queue within the queue structure.

56. The system of claim 55, further comprising a deficit bitmap, wherein said deficit bitmap is operable to maintain a plurality of bits, wherein each bit represents whether the deficit amount exceeds the quantity of data within an initial data packet that may be immediately dequeued from a corresponding queue within the queue structure.

57. The system of claim 53, further comprising a quota array, wherein a respective quota amount of the quota array represents an additional quantity of data, within one or more data packets, that may be consecutively dequeued from a respective queue within the queue structure.

58. The system of claim 57, further comprising a queue bitmap wherein said queue bitmap is operable to maintain a plurality of bits, wherein each bit represents whether a corresponding queue within the queue structure has a packet of data.

59. The system of claim 53, wherein said enqueue agent is operable to identify an attribute within a header of said one of said plurality of data packets.

60. The system of claim 59, wherein said attribute associated with one of said plurality of data packets comprises an attribute that identifies that said one of said plurality of data packets is a Voice Over Internet Protocol, Hyper Text Transfer Protocol, File Transfer Protocol, or Citrix data type.

61. The system of claim 60, further comprising a byte limit associated with each queue in said queue structure, and wherein said enqueue agent comprises an enqueue agent operable to determine whether said one of plurality of data packets includes a number of bytes that exceeds the byte limit for said queue.

62. The system of claim 53, further comprising a deficit for each queue, wherein said deficit represents the quantity of data, within one or more data packets, that may be immediately dequeued from each respective queue within the queue structure.

63. The system of claim 62, wherein each queue has an associated quota representing an additional quantity of data, within one or more data packets, that may be consecutively dequeued from a respective queue within the queue structure.

64. The system of claim 63, wherein said dequeue agent is operable to dequeue subsequent data packets from said queue structure based upon the rank of each other queue in said queue structure.

65. The system of claim 64, wherein dequeue agent is operable to update the deficit of each empty queue to the quota.

66. The system of claim 53, further comprising an active priority bucket, wherein said active priority bucket maps each one of said plurality of queues within said queue structure to an associated element within said active priority bucket, wherein said associated element points to an active list or inactive list associated with said active priority bucket, wherein said active list identifies the queues prepared to immediately dequeue a data packet, and wherein said inactive list identifies the queues that contain data packets but are not prepared to immediately dequeue the data packets.