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

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.

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.

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.