Dynamic behavioral queue classification and weighting

• US 6,981,052 B1
• Filed: 12/07/2001
• Issued: 12/27/2005
• Est. Priority Date: 12/07/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US10/010,235
• Time in Patent Office: 1,481 Days
• Field of Search: 709/234, 709/232, 709/238, 370/395.4, 370/229, 370/216, 370230-233
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• 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/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 47/626 channel conditions

Abstract

The present invention defines a method and apparatus to extend class-based queuing (CBQ) with multiple “behavioral” queues per class, to include a dynamic weighting mechanism between these queues. The packets are forwarded from the behavioral queues according to the weighting assigned to each queue. The weighting for packet scheduling of the queues is adjusted to account for additional flow going through the queues. The weight of a queue is controlled relative to the weight available to other queues. When a flow is reclassified, the queue weights is readjusted accordingly. Well behaved flows experience low delay and can thus achieve a fair bandwidth allocation without having to have multiple packets queued to compete with non-adaptive aggressive flows.

Claims

1. A method of forwarding packets comprising:

classifying a packet from a plurality of packets according to a classification, wherein the classification is one of a plurality of classifications;

storing the packet in one of a plurality of behavioral queues corresponding to the classification, wherein

each behavioral queue corresponds to one of a plurality of flow behaviors associated with the classification;

assigning a weighting to said plurality of behavioral queues; and

forwarding the packet from said behavioral queue according to said weighting.

2. The method of claim 1, wherein one of said flow behaviors is a well behaved flow.

3. The method of claim 1, wherein one of said flow behavior is a non-adaptive aggressive flow.

4. The method of claim 1, wherein said weighting is predetermined.

5. The method of claim 1 wherein said weighting is dynamically calculated according to a network traffic condition including one or more of:

available output data bandwidth;

available input data buffering space; and

available number of said plurality of behavioral queues.

6. The method of claim 1, wherein said weighting is based on a proportion of a size of said plurality of behavioral queues.

7. The method of claim 1, wherein said weighting is based on a data rate of said plurality of packets.

8. The method of claim 1, further comprising:

classifying said plurality of packets according to said plurality of flow behaviors.

9. The method of claim 8, wherein said plurality of packets is dynamically classified according to said plurality of flow behaviors.

10. The method of claim 8, wherein said plurality of packets is dynamically classified according to a plurality of predefined packet parameters.

11. The method of claim 8, further comprising:

receiving said plurality of packets.

12. The method of claim 11, further comprising:

if said plurality of behavioral queues is full,

dropping said plurality of packets.

13. The method of claim 12, further comprising:

if said plurality of packets have said well behaved flow,

storing said plurality of packets in a well behaved flow behavioral queue.

14. The method of claim 13, further comprising:

forwarding said plurality of packets according to said weighting of said well behaved queue.

15. The method of claim 12, further comprising:

if said plurality of packets have said non-adaptive aggressive flow,

storing said plurality of packets in a non-adaptive aggressive flow behavioral queue.

16. The method of claim 15, further comprising:

determining whether said non-adaptive aggressive flow behavioral queue has reached a scheduling threshold, wherein

said scheduling threshold is a percentage of a length of the non-adaptive aggressive flow behavioral queue.

17. The method of claim 16, wherein said scheduling threshold is predetermined.

18. The method of claim 16, wherein said scheduling threshold is dynamically calculated according to a network condition.

19. The method of claim 16, wherein said scheduling threshold is based on a size of said non-adaptive aggressive flow behavioral queue.

20. The method of claim 16, wherein said scheduling threshold is based on a data rate of said plurality of packets.

21. The method of claim 16, further comprising:

if said non-adaptive aggressive flow behavioral queue has reached said scheduling threshold,

determining whether a packet forwarding schedule of said non-adaptive aggressive flow behavioral queue requires adjustment.

22. The method of claim 21, further comprising:

if said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue requires adjustment,

adjusting said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue.

23. The method of claim 22, further comprising:

forwarding said plurality of packets according to said weighting of said non-adaptive aggressive flow behavioral queue.

24. The method of claim 22, wherein said adjusting of said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue is done according to a predetermined scheme.

25. The method of claim 22, wherein said adjusting of said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue is done dynamically according to said network traffic condition.

26. The method of claim 21, further comprising:

if said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue does not require adjustment,

forwarding said plurality of packets according to said weighting of said non-adaptive aggressive flow behavioral queue.

37. The network element of claim 8, further comprising:

means for receiving said plurality of packets.

38. The network element of claim 37, further comprising:

means for dropping said plurality of packets if said plurality of behavioral queues is full.

39. The network element of claim 38, further comprising:

means for storing said plurality of packets in a well behaved flow behavioral queue if said plurality of packets have said well behaved flow.

40. The network element of claim 39, further comprising:

means for forwarding said plurality of packets according to said weighting of said well behaved queue.

41. The network element of claim 38, further comprising:

means for storing said plurality of packets in a non-adaptive aggressive flow behavioral queue if said plurality of packets have said non-adaptive aggressive flow.

42. The network element of claim 41, further comprising:

means for determining whether said non-adaptive aggressive flow behavioral queue has reached a scheduling threshold, wherein

said scheduling threshold is a percentage of a length of the non-adaptive aggressive flow behavioral queue.

43. The network element of claim 42, wherein said scheduling threshold is predetermined.

44. The network element of claim 42, wherein said scheduling threshold is dynamically calculated according to a network condition.

45. The network element of claim 42, wherein said scheduling threshold is based on a size of said non-adaptive aggressive flow behavioral queue.

46. The network element of claim 42, wherein said scheduling threshold is based on a data rate of said plurality of packets.

47. The network element of claim 42, further comprising:

means for determining whether a packet forwarding schedule of said non-adaptive aggressive flow behavioral queue requires adjustment if said non-adaptive aggressive flow behavioral queue has reached said scheduling threshold.

48. The network element of claim 47, further comprising:

means for adjusting said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue if said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue requires adjustment.

49. The network element of claim 48, further comprising:

means for forwarding said plurality of packets according to said weighting of said non-adaptive aggressive flow behavioral queue.

50. The network element of claim 48, wherein said adjusting of said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue is done according to a predetermined scheme.

51. The network element of claim 48, wherein said adjusting of said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue is done dynamically according to said network traffic condition.

52. The network element of claim 47, further comprising:

means for forwarding said plurality of packets according to said weighting of said non-adaptive aggressive flow behavioral queue if said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue does not require adjustment.

27. A network element comprising:

means for classifying a packet from a plurality of packets according to a classification, wherein

the classification is one of a Plurality of classifications;

means for storing the packet in one of a plurality of behavioral queues corresponding to the classification, wherein

each behavioral queue corresponds to one of a plurality of flow behaviors associated with the classification;

means for assigning a weighting to said plurality of behavioral queues; and

means for forwarding the packet from said behavioral queue according to said weighting.

28. The network element of claim 27, wherein one of said flow behaviors is a well behaved flow.

29. The network element of claim 27, wherein one of said flow behavior is a non-adaptive aggressive flow.

30. The network element of claim 27, wherein said weighting is predetermined.

31. The network element of claim 27 wherein said weighting is dynamically calculated according to a network traffic condition including one or more of:

available output data bandwidth;

available input data buffering space; and

available number of said plurality of behavioral queues.

32. The network element of claim 27, wherein said weighting is based on a proportion of a size of said plurality of behavioral queues.

33. The network element of claim 27, wherein said weighting is based on a data rate of said plurality of packets.

34. The network element of claim 27, further comprising:

means for classifying said plurality of packets according to said plurality of flow behaviors.

35. The network element of claim 34, wherein said plurality of packets is dynamically classified according to said plurality of flow behaviors.

36. The network element of claim 34, wherein said plurality of packets is dynamically classified according to a plurality of predefined packet parameters.

53. A computer program product for forwarding packets, encoded in computer readable media, said program product comprising a set of instructions executable on a computer system, said set of instructions is configured to

classify a packet from a plurality of packets according to a classification, wherein the classification is one of a plurality of classifications;

store the packet in one of a plurality of behavioral queues corresponding to the classification,

wherein

each behavioral queue corresponds to one of a plurality of flow behaviors associated with the classification;

assign a weighting to said plurality of behavioral queues; and

forward the packet from said behavioral queue according to said weighting.

54. The computer program product of claim 53, wherein one of said flow behaviors is a well behaved flow.

55. The computer program product of claim 53, wherein one of said flow behavior is a non-adaptive aggressive flow.

56. The computer program product of claim 53, wherein said weighting is predetermined.

57. The computer program product of claim 53 wherein said weighting is dynamically calculated according to a network traffic condition including one or more of:

available output data bandwidth;

available input data buffering space; and

available number of said plurality of behavioral queues.

58. The computer program product of claim 53, wherein said weighting is based on a proportion of a size of said plurality of behavioral queues.

59. The computer program product of claim 53, wherein said weighting is based on a data rate of said plurality of packets.

60. The computer program product of claim 53, said set of instructions is further configured to:

classify said plurality of packets according to said plurality of flow behaviors.

61. The computer program product of claim 60, wherein said plurality of packets is dynamically classified according to said plurality of flow behaviors.

62. The computer program product of claim 60, wherein said plurality of packets is dynamically classified according to a plurality of predefined packet parameters.

63. The computer program product of claim 60, said set of instructions is further configured to receive said plurality of packets.

64. The computer program product of claim 63, said set of instructions is further configured to

if said plurality of behavioral queues is full,

drop said plurality of packets.

65. The computer program product of claim 64, said set of instructions is further configured to

if said plurality of packets have said well behaved flow,

store said plurality of packets in a well behaved flow behavioral queue.

66. The computer program product of claim 65, said set of instructions is further configured to

forward said plurality of packets according to said weighting of said well behaved queue.

67. The computer program product of claim 64, said set of instructions is further configured to

if said plurality of packets have said non-adaptive aggressive flow,

store said plurality of packets in a non-adaptive aggressive flow behavioral queue.

68. The computer program product of claim 67, said set of instructions is further configured to

determine whether said non-adaptive aggressive flow behavioral queue has reached a scheduling threshold, wherein

said scheduling threshold is a percentage of a length of the non-adaptive aggressive flow behavioral queue.

69. The computer program product of claim 68, wherein said scheduling threshold is predetermined.

70. The computer program product of claim 68, wherein said scheduling threshold is dynamically calculated according to a network condition.

71. The computer program product of claim 68, wherein said scheduling threshold is based on a size of said non-adaptive aggressive flow behavioral queue.

72. The computer program product of claim 68, wherein said scheduling threshold is based on a data rate of said plurality of packets.

73. The computer program product of claim 68, said set of instructions is further configured to

if said non-adaptive aggressive flow behavioral queue has reached said scheduling threshold,

determine whether a packet forwarding schedule of said non-adaptive aggressive flow behavioral queue requires adjustment.

74. The computer program product of claim 73, said set of instructions is further configured to

if said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue requires adjustment,

adjust said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue.

75. The computer program product of claim 74, said set of instructions is further configured to

forward said plurality of packets according to said weighting of said non-adaptive aggressive flow behavioral queue.

76. The computer program product of claim 74, wherein said adjusting of said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue is done according to a predetermined scheme.

77. The computer program product of claim 74, wherein said adjusting of said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue is done dynamically according to said network traffic condition.

78. The computer program product of claim 73, said set of instructions is further configured to

if said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue does not require adjustment,

forward said plurality of packets according to said weighting of said non-adaptive aggressive flow behavioral queue.

79. A network element comprising:

a processor;

a memory coupled to said processor; and

a network interface coupled to said processor, said processor is configured to

classify a packet from a plurality of packets according to a classification,

wherein

the classification is one of a plurality of classifications;

store the packet in one of a plurality of behavioral queues corresponding to the classification, wherein

each behavioral queue corresponds to one of a plurality of flow behaviors associated with the classification,

assign a weighting to said plurality of behavioral queues, and

forward the packet from said behavioral queue according to said weighting.

80. The network element of claim 79, wherein one of said flow behaviors is a well behaved flow.

81. The network element of claim 79, wherein one of said flow behavior is a non-adaptive aggressive flow.

82. The network element of claim 79, wherein said weighting is predetermined.

83. The network element of claim 79 wherein said weighting is dynamically calculated according to a network traffic condition including one or more of:

available output data bandwidth;

available input data buffering space; and

available number of said plurality of behavioral queues.

84. The network element of claim 79, wherein said weighting is based on a proportion of a size of said plurality of behavioral queues.

85. The network element of claim 79, wherein said weighting is based on a data rate of said plurality of packets.

86. The network element of claim 79, said processor is further configured to classify said plurality of packets according to said plurality of flow behaviors.

87. The network element of claim 86, wherein said plurality of packets is dynamically classified according to said plurality of flow behaviors.

88. The network element of claim 86, wherein said plurality of packets is dynamically classified according to a plurality of predefined packet parameters.

89. The network element of claim 86, said processor is further configured to

receive said plurality of packets.

90. The network element of claim 89, said processor is further configured to

if said plurality of behavioral queues is full,

drop said plurality of packets.

91. The network element of claim 90, said processor is further configured to

if said plurality of packets have said well behaved flow,

store said plurality of packets in a well behaved flow behavioral queue.

92. The network element of claim 91, said processor is further configured to

forward said plurality of packets according to said weighting of said well behaved queue.

93. The network element of claim 90, said processor is further configured to

if said plurality of packets have said non-adaptive aggressive flow,

store said plurality of packets in a non-adaptive aggressive flow behavioral queue.

94. The network element of claim 93, said processor is further configured to

determine whether said non-adaptive aggressive flow behavioral queue has reached a scheduling threshold, wherein

said scheduling threshold is a percentage of a length of the non-adaptive aggressive flow behavioral queue.

95. The network element of claim 94, wherein said scheduling threshold is predetermined.

96. The network element of claim 94, wherein said scheduling threshold is dynamically calculated according to a network condition.

97. The network element of claim 94, wherein said scheduling threshold is based on a size of said non-adaptive aggressive flow behavioral queue.

98. The network element of claim 94, wherein said scheduling threshold is based on a data rate of said plurality of packets.

99. The network element of claim 94, said processor is further configured to

if said non-adaptive aggressive flow behavioral queue has reached said scheduling threshold,

determine whether a packet forwarding schedule of said non-adaptive aggressive flow behavioral queue requires adjustment.

100. The network element of claim 99, said processor is further configured to

if said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue requires adjustment,

adjust said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue.

101. The network element of claim 100, said processor is further configured to

forward said plurality of packets according to said weighting of said non-adaptive aggressive flow behavioral queue.

102. The network element of claim 100, wherein said adjusting of said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue is done according to a predetermined scheme.

103. The network element of claim 100, wherein said adjusting of said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue is done dynamically according to said network traffic condition.

104. The network element of claim 99, said processor is further configured to

if said packet forwarding schedule of said non-adaptive aggressive flow behavioral queue does not require adjustment,

forward said plurality of packets according to said weighting of said non-adaptive aggressive flow behavioral queue.