Weighted fair queuing-based methods and apparatus for protecting against overload conditions on nodes of a distributed network

• US 20030076848A1
• Filed: 04/26/2002
• Published: 04/24/2003
• Est. Priority Date: 04/27/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Touitou, Dan, Tzadikario, Rephael, Horvitz, Keren, Bremler-Barr, Anat, Afek, Yehuda
• Granted Patent: US 7,342,929 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• 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/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• 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/623 Weighted service order
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/1458 Denial of Service
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

An improved network device that controls throughput of packets received thereby, e.g., to downstream devices or to downstream logic contained within the same network device. The network device comprises a scheduler that schedules one or more packets of a selected class for throughput as a function of a weight of that class and weights of one or more other classes. The weight of at least the selected class is dynamic and is a function of a history of volume of packets received by the network device in the selected class. An apparatus for protecting against overload conditions on a network, e.g., of the type caused by DDoS attacks, has a scheduler and a token bucket mechanism, e.g., as described above. Such apparatus can also include a plurality of queues into which packets of the respective classes are placed on receipt by the apparatus. Those packets are dequeued by the scheduler, e.g., in the manner described above, for transmittal to downstream devices (e.g., potential victim nodes) on the network.

Claims

15. In a network device, the improvement for controlling throughput comprising

a scheduler that schedules one or more packets of at least a selected class for throughput as a function of a dynamic weight of that class and dynamic weights of one or more other classes,

any of a leaky bucket mechanism and a token bucket mechanism (collectively, “

token bucket mechanism”

) coupled to the scheduler that (i) uses for each class a bucket whose volume is a function of a history of traffic of packets in the respective class received by the network device, and (ii) determines the dynamic weight of each class as a function of the volume of the respective bucket.

16. In the network device of claim 15, the further improvement wherein the scheduler is any of a

(i) a weighted fair queuing (WFQ) scheduler, or variation thereof,

(ii) a round robin scheduler and

(iii) a deficit round robin scheduler

that uses, as a weight for the one or more packets of the selected class, the dynamic weight of the class.

17. In the network device of claim 16, the further improvement wherein the token bucket mechanism determines a volume of a bucket for at least a class i for an epoch t₂ during which one or more packets for that class are actually or theoretically pending for throughput as a function of a relation

18. In the network device of claim 17, the further improvement wherein the token bucket mechanism determines a volume of a bucket for at least a class i for an epoch t₂ during which one or more packets for that class are not actually or theoretically pending for throughput as a function of a relation

L_i(t₂)=max{B_i^min,min{B_i,L_i(t₁)+(t₂−

t₁)r_i}}.

where

L_i(t₂) is the volume of the bucket for class i during epoch t₂;

L_i(t_l) is the volume of the bucket for class i during epoch t₁;

B_i^min is a minimum capacity for the bucket for class i;

B_i is a maximum capacity for the bucket for class i;

r_i is a filling rate of the bucket for class i.

19. In the network device of claim 16, the further improvement wherein the token bucket mechanism determines the volume of the bucket for class i at epoch t during which one or more packets are throughput as a function of the relation

L_i(t)=max{B_i^min,min{B_i,L_i(t)−

D}

where

L_i(t) is the volume of the bucket for class i during epoch t;

B_i^min is a minimum capacity for the bucket for class i;

B_i is a maximum capacity for the bucket for class i;

D is an actual or estimated size of the one or more packets throughput.

20. In a network device, the improvement for controlling throughput comprising

a scheduler that schedules one or more packets of at least a selected class for throughput as a function of a dynamic weight of that class and dynamic weights of one or more other classes,

any of a leaky bucket mechanism and a token bucket mechanism (collectively, “

token bucket mechanism”

) coupled to the scheduler that (i) uses for each class a bucket whose volume is a function of a history of traffic of packets in the respective class received by the network device, and (ii) determines the dynamic weight of each class as a function of the volume of the respective bucket,

the token bucket mechanism models each bucket as (i) filling at a rate associated with the respective class, (ii) having a minimum capacity associated with that class, and a maximum capacity associated with that class, and

the token bucket mechanism reduces each bucket proportionally to a volume of packets throughput for the respective class by the scheduler,

the scheduler schedules for throughput at a time t a volume of packets of the selected class that is proportional to a content of the bucket for that class at that time.

21. In the network device of claim 21, the further improvement wherein scheduler (i) schedules for throughput only whole packets of the selected class, and (ii) credits the bucket associated with the selected class if the volume of packets of that class that would be scheduled for throughput includes a fraction of a packet.

22. In a method of operating a network device, the improvement for controlling throughput comprising the step of scheduling packets, if any, in each of a plurality of classes for throughput,

the scheduling step including

A. allowing throughput bursts of packets from the respective classes so long as each an average rate therefrom does not exceed a first selected level,

B. discriminating against throughput of streams of packets that exceed an average for more than a selected period, where a stream comprises a plurality of packets from a given source to a given destination,

C. exercising (A) and (B) only to an extent substantially necessary to keep overall throughput under a second selected level.

1. In a network device, the improvement for controlling throughput comprising

a scheduler that schedules one or more packets of a selected class for throughput as a function of a weight of that class and weights of one or more other classes,

the weight of at least the selected class being a dynamic weight that is a function of a history of volume of packets received by the network device in the selected class.

2. In the network device of claim 1, the further improvement wherein the scheduler is substantially a weighted fair queuing (WFQ) scheduler that uses, as a weight for the one or more packets of the selected class, the dynamic weight of the class.

3. In the network device of claim 1, the further improvement wherein the scheduler is substantially any of a round robin and a deficit round robin (DRR) scheduler that uses, as a weight for the one or more packets of the selected class, the dynamic weight of the class.

4. In the network device of any of claims 1-3, the further improvement comprising a rate-limiter that determines the dynamic weight of at least the selected class.

5. In the network device of claim 4, the further improvement wherein the rate-limiter is substantially any of a leaky bucket mechanism and a token bucket mechanism (collectively, “

token bucket mechanism”

)

6. In the network device of claim 5, the further improvement wherein the token bucket mechanism uses a bucket for each of at least the selected class and one or more other classes, and models each bucket as (i) filling at a rate associated with the respective class, (ii) having a minimum capacity associated with that class, and a maximum capacity associated with that class.

7. In the network device of claim 6, the further improvement wherein the token bucket mechanism reduces each bucket proportionally to a volume of packets throughput for the respective class by the scheduler.

8. In the network device of claim 7, the further improvement wherein the token bucket mechanism reduces each bucket proportionally to a volume any of actually and theoretically throughput for the respective class.

9. In the network device of claim 6, the further improvement wherein the token bucket mechanism determines a volume of a bucket for at least a class i as a function of a relation

10. In the network device of claim 9, the further improvement wherein

the token bucket mechanism determines the volume of the bucket for class i in accord with the foregoing relation if one or more packets for that class were actually or theoretically throughput (or pending therefor) during the epoch t₁,

a limiter coupled to the scheduler that limits overall traffic throughput to a selected amount.

11. In the network device of claim 6, the further improvement wherein the token bucket mechanism determines a volume of a bucket for at least a class i as a function of a relation

L_i(t₂)=max{B_i^min,min{B_i,L_i(t₁)+(t₂−

t₁)r_i}}.

where

L_i(t₂) is the volume of the bucket for class i during epoch t₂;

L_i(t₁) is the volume of the bucket for class i during epoch t₁;

B_i^min is a minimum capacity for the bucket for class i;

B_i is a maximum capacity for the bucket for class i;

r_i is a filling rate of the bucket for class i.

12. In the network device of claim 11, the further improvement wherein the token bucket mechanism determines the volume of the bucket for class i in accord with the foregoing relation if one or more packets for that class were not actually or theoretically throughput (or pending therefor) during the epoch t₁.

13. In the network device of claim 11, the further improvement wherein the token bucket mechanism decrements the volume of the bucket for class i at an epoch t during which one or more packets are throughput by an amount proportional to any of a size and number of those one or more packets.

14. In the network device of claim 13, the further improvement wherein the token bucket mechanism determines the volume of the bucket for class i at epoch t during which one or more packets are throughput as a function of the relation

L_i(t)=max{B_i^min,min{B_i,L_i(t)−

D}}

where

L_i(t) is the volume of the bucket for class i during epoch t;

B_i^min is a minimum capacity for the bucket for class i;

B_i is a maximum capacity for the bucket for class i;

D is an actual or estimated size of the one or more packets throughput.

23. In the method of claim 22, the further improvement wherein the scheduling step includes

scheduling one or more packets of a selected class for throughput as a function of a weight of that class and weights of one or more other classes,

the weight of at least the selected class being a dynamic weight that is a function of a history of volume of packets received by the network device in the selected class.

24. In the method of claim 23, the further improvement wherein the scheduling step operates in accord with weighted fair queuing (WFQ) using, as a weight for the one or more packets of the selected class, the dynamic weight of the class.

25. In the method of claim 23, the further improvement wherein the scheduling step operates in accord with any of round robin and deficit round robin (DRR) scheduling using, as a weight for the one or more packets of the selected class, the dynamic weight of the class.

26. In the method of claim 25, the further improvement wherein the rate-limiting operates in accord with any of a leaky bucket and a token bucket.

27. In the method of claim 26, the further improvement wherein the rate-limiting includes applying a bucket for each of at least the selected class and one or more other classes, and modelling each bucket as (i) filling at a rate associated with the respective class, (ii) having a minimum capacity associated with that class, and a maximum capacity associated with that class.

28. In the method of claim 27, the further improvement wherein the rate-limiting includes reducing each bucket proportionally to a volume of packets throughput for the respective class by the scheduler.

29. In the method of claim 28, the further improvement wherein the rate-limiting includes reducing each bucket proportionally to a volume any of actually and theoretically throughput for the respective class.

30. In the method of claim 27, the further improvement wherein the rate-limiting includes determining a volume of a bucket for at least a class i as a function of a relation

31. In the method of claim 30, the further improvement wherein the rate-limiting includes determining the volume of the bucket for class i in accord with the foregoing relation if one or more packets for that class were actually or theoretically throughput (or pending therefor) during the epoch t₁.

32. In the method of claim 27, the further improvement wherein the rate-limiting includes determining a volume of a bucket for at least a class i as a function of a relation

L_i(t₂)=max{B_i^min,min{B_i,L_i(t₁)+(t₂−

t₁)r_i}}.

where

L_i(t₂) is the volume of the bucket for class i during epoch t₂;

L_i(t₁) is the volume of the bucket for class i during epoch t₁;

B_i^min is a minimum capacity for the bucket for class i,

B_i is a maximum capacity for the bucket for class i;

r_i is a filling rate of the bucket for class i.

33. In the method of claim 32, the further improvement wherein the rate-limiting includes determining the volume of the bucket for class i in accord with the foregoing relation if one or more packets for that class were not actually or theoretically throughput (or pending therefor) during the epoch t₁.

34. In the method of claim 32, the further improvement wherein the rate-limiting includes decrementing the volume of the bucket for class i at an epoch t during which one or more packets are throughput by an amount proportional to any of a size and number of those one or more packets.

35. In the method of claim 34, the further improvement wherein the rate-limiting includes determining the volume of the bucket for class i at epoch t during which one or more packets are throughput as a function of the relation

L_i(t)=max{B_i^min,min{B_i,L_i(t)−

D}}

where

L_i(t) is the volume of the bucket for class i during epoch t;

B_i^min is a minimum capacity for the bucket for class i,

B_i is a maximum capacity for the bucket for class i;

D is an actual or estimated size of the one or more packets throughput.

25-1. In the method of any of claims 23-25, the further improvement comprising determining the dynamic weights by rate-limiting.

36. An apparatus for protecting against overload conditions on a network comprising

a plurality of queues,

a scheduler coupled to the queues that schedules packets therein for dequeuing for output as a function of a dynamic weight of associated with each queue,

any of a leaky bucket mechanism and a token bucket mechanism (collectively, “

token bucket mechanism”

) coupled to the scheduler that (i) uses for each queue a bucket whose volume is a function of a history of traffic of packets received by the network device and placed in the respective queue, and (ii) determines the dynamic weight of each queue as a function of the volume of the respective bucket.

37. The apparatus of claim 36, the further improvement wherein the scheduler is any of a

(i) a weighted fair queuing (WFQ) scheduler,

(ii) a round robin scheduler and

(iii) a deficit round robin scheduler that uses, as weights for the queues, the aforementioned dynamic weights.

38. The apparatus of claim 37, the further improvement wherein the token bucket mechanism determines a volume of a bucket for at least a queue i for an epoch t₂₄ during which one or more packets for that queue are actually or theoretically pending for dequeuing as a function of a relation

39. The apparatus of claim 38, the further improvement wherein the token bucket mechanism determines a volume of a bucket for at least a queue i for an epoch t₂₄ during which one or more packets for that queue are not actually or theoretically pending for dequeuing as a function of a relation

L_i(t₂₄)=max{B_i^min,min{B_i,L_i(t₂₃)+(t₂₄−

t₂₃)r_i}}.

where

L_i(t₂₄) is the volume of the bucket for queue i during epoch t₂₄;

L_i(t₂₃) is the volume of the bucket for queue i during epoch t₂₃;

B_i^min is a minimum capacity for the bucket for queue i;

B_i is a maximum capacity for the bucket for queue i;

r_i is a filling rate of the bucket for queue i.

40. The apparatus of claim 37, the further improvement wherein the token bucket mechanism determines the volume of the bucket for queue i at epoch t during which one or more packets are throughput as a function of the relation

L_i(t)=max{B_i^min,min{B_i,L_i(t)−

D}

where

L_i(t) is the volume of the bucket for queue i during epoch t;

B_i^min is a minimum capacity for the bucket for queue i,

B_i is a maximum capacity for the bucket for queue i;

D is an actual or estimated size of the one or more packets throughput.

43. The apparatus of any of claims 36-42, comprising one or more classifiers that classify packets received by the apparatus for placement in queues associated with those classes.

44. The apparatus of claim 43, wherein an aforesaid classifier classifies a packet according to any combination of one or more of a source IP address, source TCP/IP port, destination IP address, destination TCP/IP port number, and protocol type, or other parameter, associated with that packet.

45. The apparatus of claim 43, comprising functionality, coupled with one or more classifiers, that determines suspiciousness of a packet.

46. The apparatus of claim 45, wherein a classifier places a packet in a queue based on a classification and a suspiciousness of the packet.

47. The apparatus of claim 46, wherein packets of a higher degree of suspiciousness are placed in different queues from packets of a lower degree of suspiciousness.

48. The apparatus of claim 47, wherein the scheduler schedules with lower priority a queue allocated to packets of a higher degree of suspiciousness.

49. The apparatus of any of claims 36-42, comprising a marking mechanism that transmits a cookie to a packet source on the network and causes that source to include the cookie in packets transmitted by it to on the network to a destination associated with the apparatus.

50. The apparatus of claim 49, wherein the marking mechanism transmits the cookie in a packet directed from the destination to the source.

51. The apparatus of claim 49, wherein the marking mechanism strips the cookie from any packets transmitted by the source to the destination.

52. The apparatus of claim 49, wherein the marking mechanism determines suspiciousness of a packet based on a cookie, or absence therein.

53. The apparatus of claim 52, comprising a classifier that places a packet in a queue based, in part, on the suspiciousness of the packet.

54. The apparatus of claim 53, wherein packets of a higher degree of suspiciousness are placed in different queues from packets of a lower degree of suspiciousness.

55. The apparatus of claim 54, wherein the scheduler schedules with lower priority a queue allocated to packets of a higher degree of suspiciousness.

56. The apparatus of claim 49, wherein the marking mechanism distinguishes among packets having at least like source and destination IP addresses, which packets are attributable to different user sessions, wherein the marking mechanism so distinguishes among the packets attributable to different user sessions based on cookies.

57. The apparatus of any of claim 36-42, comprising an authentication module that transmits a challenge to a source on the network and that analyzes a response thereto to determine the suspiciousness of the source.

58. The apparatus of claim 57, wherein a proper response to the challenge is not readily generated by a pre-programmed source.

59. The apparatus of claim 57, wherein responses attributable to pre-programmed sources are deemed to be of higher suspiciousness, while those attributable to human controlled sources are deemed to be of lower suspiciousness.

60. The apparatus of claim 59, comprising a classifier that places a packet in a queue based, in part, on the suspiciousness of the packet.

61. The apparatus of claim 60, wherein packets of a higher degree of suspiciousness are placed in different queues from packets of a lower degree of suspiciousness.

62. The apparatus of claim 61, wherein the scheduler schedules with lower priority a queue allocated to packets of a higher degree of suspiciousness.

41. An apparatus for protecting against overload conditions on a network, comprising

a plurality of queues,

a scheduler coupled to the queues that schedules packets therein for dequeuing for output as a function of a dynamic weight of associated with each queue,

any of a leaky bucket mechanism and a token bucket mechanism (collectively, “

token bucket mechanism”

) coupled to the scheduler that (i) uses for each queue a bucket whose volume is a function of a history of traffic of packets received by the apparatus and placed in the respective queue, and (ii) determines the dynamic weight of each queue as a function of the volume of the respective bucket,

the token bucket mechanism models each bucket as (i) filling at a rate associated with the respective queue, (ii) having a minimum capacity associated with that queue, and a maximum capacity associated with that queue, and

the token bucket mechanism reduces each bucket proportionally to a volume of packets throughput for the respective queue by the scheduler,

the scheduler schedules for dequeuing at a time t a volume of packets of the selected queue that is proportional to a content of the bucket for that queue at that time.

42. The apparatus of claim 41, wherein the scheduler (i) schedules for dequeuing only whole packets of the selected queue, and (ii) credits the bucket associated with the selected queue if the volume of packets of that queue that would be scheduled for dequeuing includes a fraction of a packet.

63. In a network device, the improvement for controlling throughput comprising

a scheduler that schedules one or more packets of a selected class for throughput as a function of a weight of that class and weights of one or more other classes,

a marking mechanism that transmits a cookie to a packet source on the network and causes that source to include the cookie in packets transmitted by it to on the network to a destination coupled to the network device.

64. In the network device of claim 63, wherein the marking mechanism transmits the cookie in a packet directed from the destination to the source.

65. In the network device of claim 63, wherein the marking mechanism strips the cookie from any packets transmitted by the source to the destination.

66. In the network device of claim 63, wherein the marking mechanism determines suspiciousness of a packet based on a cookie, or absence therof, in the packet.

67. In the network device of claim 66, comprising a classifier that places a packet in a queue based, in part, on the suspiciousness of the packet.

68. In the network device of claim 67, wherein packets of a higher degree of suspiciousness are placed in different queues from packets of a lower degree of suspiciousness.

69. In the network device of claim 68, wherein the scheduler schedules with lower priority a queue allocated to packets of a higher degree of suspiciousness.

70. In the network device of claim 63, wherein the marking mechanism distinguishes among packets having at least like source and destination IP addresses, which packets are attributable to different user sessions, wherein the marking mechanism so distinguishes among the packets attributable to different user sessions based on cookies.

71. In a network device, the improvement for controlling throughput comprising

a scheduler that schedules one or more packets of a selected class for throughput as a function of a weight of that class and weights of one or more other classes,

an authentication module that transmits a challenge to a source on the network and that analyzes a response thereto to determine the suspiciousness of the source.

72. In the network device of claim 71, wherein a proper response to the challenge is not readily generated by a pre-programmed source.

73. In the network device of claim 71, wherein responses attributable to pre-programmed sources are deemed to be of higher suspiciousness, while those attributable to human controlled sources are deemed to be of lower suspiciousness.

74. In the network device of claim 73, comprising a classifier that places a packet in a queue based, in part, on the suspiciousness of the packet.

75. In the network device of claim 74, wherein packets of a higher degree of suspiciousness are placed in different queues from packets of a lower degree of suspiciousness.

76. In the network device of claim 71, wherein the scheduler schedules with lower priority a queue allocated to packets of a higher degree of suspiciousness.

a marking mechanism that transmits a cookie to a packet source on the network and causes that source to include the cookie in packets transmitted by it to on the network to a destination coupled to the network device.

77. In the network device of claim 76, wherein the marking mechanism transmits the cookie in a packet directed from the destination to the source.

78. In the network device of claim 76, wherein the marking mechanism strips the cookie from any packets transmitted by the source to the destination.

79. In the network device of claim 76, wherein the marking mechanism determines suspiciousness of a packet based on, or absence thereof, in the packet.

80. In the network device of claim 79, comprising a classifier that places a packet in a queue based, in part, on the suspiciousness of the packet.

81. In the network device of claim 80, wherein packets of a higher degree of suspiciousness are placed in different queues from packets of a lower degree of suspiciousness.

82. In the network device of claim 81, wherein the scheduler schedules with lower priority a queue allocated to packets of a higher degree of suspiciousness.

83. In the network device of claim 76, wherein the marking mechanism distinguishes among packets having at least like source and destination IP addresses, which packets are attributable to different user sessions, wherein the marking mechanism so distinguishes among the packets attributable to different user sessions based on cookies.