US 7,453,804 B1Granted

Aggregate network resource utilization control scheme

AssigneePacketeer, Inc.

InventorsAzeem Feroz, Wei-Lung Lai, Roopesh R. Varier, James J. Stabile, Jon Eric Okholm

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods, apparatuses and systems directed to an aggregate bandwidth utilization control scheme including fair share bandwidth allocation and dynamic allocation of bandwidth in response to detected traffic utilization. In one implementation, the present invention includes a weighted, fair share aggregate bandwidth allocation mechanism that dynamically responds to observed bandwidth utilization to provide unutilized or excess bandwidth to flows and partitions that require it. In another implementation, the present invention features a weighted fair share allocation scheme for hierarchical partition configurations. In other implementations, the present invention provides a per-flow target rate assignment mechanism that prevents spiraling decline of data flow rates.

Claims11

Dependent claims

In a network device including a flow control module operative to allocate network bandwidth into a plurality of partitions, wherein each partition in the plurality of partitions includes an aggregate bandwidth allocation, a method directed to an aggregate bandwidth utilization control scheme, the method comprising

receiving a packet;
associating the packet with a data flow;
measuring a data rate for the data flow;
identifying a partition for the data flow, wherein the partition includes an aggregate bandwidth allocation, and wherein each partition has associated therewith a low priority partition queue and a high priority partition queue;
buffering the packet in a flow queue corresponding to the data flow;
computing a per-flow fair share bandwidth allocation based on the number of active data flows associated with the partition and the aggregate bandwidth allocation;
determining a per-flow target rate for the data flow based on the per-flow fair share bandwidth allocation and the measured data rate;
pushing an identifier for the flow queue in a partition queue corresponding to the identified partition, wherein the pushing an identifier comprises pushing the identifier for the flow queue on the high priority partition queue associated with the identified partition if the measured data rate is less than the per-flow fair share bandwidth allocation, else, pushing the identifier for the flow queue on the low priority partition queue associated with the identified partition;
enforcing the target rate on the data flow;
and
passing the packet to the flow control module, wherein the flow control module is operative to enforce the aggregate bandwidth allocation associated with the partition, and prioritize, relative to a given partition, packets of data flows corresponding to high priority partition queues over low priority partition queues.

8 more elements

An apparatus enabling a fair share bandwidth utilization control scheme, comprising

a memory for buffering packets;
a packet processor, coupled to the memory, and operative to associate received packets with data flows;
a flow control module comprising
a partitioning module operative to allocate network bandwidth into a plurality of partitions, wherein each partition in the plurality of partitions includes an aggregate bandwidth allocation and a partition queue, and
a per-flow rate control module operative to apply per-flow target rates to data flows traversing the apparatus;
wherein the flow control module is operative to
identify a partition corresponding to a data flow;
estimate the data rate of the data flow;
assign a target rate for the data flow based on the per-flow fair share of the aggregate bandwidth allocation corresponding to the identified partition, and the estimated data rate;
create a flow queue responsive to detection of the data flow;
push the data packet onto a flow queue;
and
push a pointer to the flow queue containing the data packet on the partition queue corresponding to the identified partition for the data flow;
and
wherein the flow control module further comprises an output scheduling data structure comprising a partition object corresponding to each partition queue;
wherein the partition object comprises a partition identifier and a time stamp;
and
wherein the flow control module further comprises an output scheduler operative to:
sort partition objects in the output scheduling data structure based on the corresponding time stamps;
select the partition object in the output scheduling data structure with the lowest time stamp;
pop the next flow queue buffered in the partition queue corresponding to the selected partition object;
pop the next packet in the next flow queue and schedule the packet for output;
and
update the time stamp of the selected partition object based in part on the aggregate bandwidth setting corresponding to the selected partition.

21 more elements

Dependencies are inferred from the claim text.