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

• US 7,342,929 B2
• Filed: 04/26/2002
• Issued: 03/11/2008
• Est. Priority Date: 04/27/2001
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Tzadikario, Rephael, Horvitz, Keren, Touitou, Dan, Bremler-Barr, Anat, Afek, Yehuda
• Primary Examiner(s): Orgad; Edan
• Assistant Examiner(s): PARK, JUNG H
• Application Number:
  US10/134,048
• Publication Number:
  US 20030076848A1
• Time in Patent Office: 2,146 Days
• Field of Search: None
• US Class Current: 370/395.4
• 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

1. In a network device deployed on a network, 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,

a bucket mechanism comprising any of a leaky bucket mechanism and a 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 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 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 so as to protect against overload conditions caused by traffic on the network.

2. In the network device of claim 1, 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.

3. In a method of operating a network device deployed on a network, 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 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, so as to protect against overload conditions caused by traffic on the network,

C. exercising (A) and (B) only to an extent substantially necessary to keep overall throughput under a second selected level, wherein the scheduling step includes scheduling one or more packets of a selected class for throughout as a function of a weight of that class and weights of one or more other classes, the weight of at last 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.

4. In the method of claim 3, 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.

5. In the method of claim 3, 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.

6. In the method of any one of claims 4-5, the further improvement comprising determining the dynamic weights by rate-limiting.

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

8. In the method of claim 7, 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.

9. In the method of claim 8, 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.

10. In the method of claim 9, 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.

11. In the method of claim 8, 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

12. In the method of claim 11, 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₁.

13. In the method of claim 8, 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

14. In the method of claim 13, 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₁.

15. In the method of claim 13, 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.

16. 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,

a bucket mechanism comprising any of a leaky bucket mechanism and a 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 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 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 so as to protect against overload conditions caused by traffic on the network.

17. The apparatus of claim 16, 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.

18. The apparatus of claim 16 or 17, comprising one or more classifiers that classify packets received by the apparatus for placement in queues associated with those classes.

19. The apparatus of claim 18, 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.

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

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

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

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

24. The apparatus of claim 16 or 17, 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.

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

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

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

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

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

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

31. The apparatus of claim 24, 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.

32. The apparatus of claim 16 or 17, 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.

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

34. The apparatus of claim 32, 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.

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

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

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