Lockless Bandwidth Management for Multiprocessor Networking Devices

• US 20090003204A1
• Filed: 06/29/2007
• Published: 01/01/2009
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Packeteer Incorporated (Gen Digital Inc.)
• Inventors: Riddle, Guy, Okholm, Jon Eric
• Granted Patent: US 7,813,277 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 49/9063 Intermediate storage in different physical parts of a node or terminal
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level

Abstract

An example embodiment of the invention provides a process for lockless processing of hierarchical bandwidth partitions configurations in multiple processor architectures. In one embodiment, the process runs in an NPU'"'"'s data plane and receives a packet for a partition from a child partition through a work queue. The process determines a suggested target bandwidth rate for the receiving partition'"'"'s child partitions, based in part on a count of active child partitions, if a predefined time interval has passed. The process adopts a target bandwidth rate for the receiving partition suggested by the receiving partition'"'"'s parent partition, if the receiving partition is not a root partition and the predefined time interval has passed. The process then transmits the packet to the receiving partition'"'"'s parent partition through the work queue, if the receiving partition is not a root partition. Otherwise, the process transmits the packet to a port.

Claims

1. An apparatus comprising

one or more network interfaces;

a plurality of processors;

a work order module operative to

maintain a queue of work entries, one or more of the work entries including a task description, a packet pointer, and a tag; and

schedule work entries in the queue for the plurality of processors such that only a single processor of the plurality of processors is provided a work entry labeled with a given tag;

a memory operative to define a hierarchical partition configuration, the hierarchical partition configuration comprising a plurality of partitions, the memory further operative to buffer packets received at the one or more network interfaces;

wherein the plurality of processors, to schedule received packets for transmission according to the hierarchical partition configuration, are each operative to;

receive, from the work order module, an indication of a first work entry, wherein the first work entry is associated with a packet to be processed and includes a tag identifying a partition of the plurality of partitions,

forward the packet corresponding to the first work entry to a parent partition of the identified partition by modifying the first work entry to include a tag of the parent partition, and

resubmit the first modified, work entry to the work, order module.

2. The apparatus according to claim 1, wherein the plurality of processors are further operative to

periodically access a parent partition data structure corresponding to the parent partition of the partition associated with the tag to identify a suggested target rate.

3. The apparatus according to claim 1, wherein the plurality of processors are further operative to

periodically compute a suggested target rate for child partitions based on a target rate for the partition associated with the tag and the number of active child partitions.

4. The apparatus according to claim 1, wherein the plurality of processors are further operative to

periodically compute a suggested target rate for child partitions based on a target rate for the partition associated with the tag, an amount of data queued for the partition associated with the tag, and the number of active child partitions.

5. The apparatus according to claim 1, wherein the plurality of processors are further operative to conditionally flag the forwarded packet if the packet is the first packet forwarded during a target rate adjustment interval.

6. The apparatus according to claim 1, wherein the plurality of processors are further operative to increment an active child partition counter responsive to a flag associated with the packet set by a child partition of the partition associated with the tag during execution of a previous work entry.

7. The apparatus according to claim 1, wherein the plurality of processors are further operative to

conditionally forward the packet to the parent partition based on a target rate associated with the partition associated with the tag.

8. The apparatus according to claim 1, wherein the plurality of processors are further operative to

add tokens to a token bucket associated with the partition associated with the tag based on a target rate associated with the partition and a last token update time;

conditionally forward the packet to the parent partition based on a size of the packet and a current number of tokens in the token bucket of the partition associated with the tag.

9. The apparatus according to claim 8 wherein the plurality of processors are further operative to add tokens to the token bucket up to a maximum token limit.

10. The apparatus according to claim 8 wherein the wherein the plurality of processors are further operative to deduct, responsive to forwarding the packet, tokens from the token bucket of the partition associated with the tag.

11. The apparatus according to claim 8 wherein the plurality of processors are further operative to

place the packet on a partition queue if a number of tokens in the token bucket of the partition associated with the tag is insufficient to transmit the packet;

and

compute a delay time based on the target rate of the partition and the size of the packet;

set a timer for the delay time, wherein the timer, when triggered, is operative to return the work entry identifying the partition associated with the tag to the corresponding processor.

12. The apparatus according to claim 11 wherein the partition queue is selected from a plurality of partition queues based on a priority associated with the packet.

13. The apparatus according to claim 11 wherein the delay time used to set the timer is constrained by a minimum delay time.

14. The apparatus according to claim 1 wherein the plurality of processors are further operative to

receive a work entry identifying a packet;

associate the packet with a data flow entry, wherein the flow entry identifies a partition;

place the work entry on a flow queue corresponding to the flow entry.

15. The apparatus according to claim 14 wherein the plurality of processors are further operative to

change the tag of the work entry to a tag corresponding to the partition identified in data flow entry;

and

submit the work entry to the work order module.

16. The apparatus according to claim 1 wherein the plurality of processors are further operative to

receive a work entry identifying a packet;

associate the packet with a data flow entry, wherein the flow entry identifies a partition and a priority;

place the work entry on a flow queue corresponding to the flow entry.

17. The apparatus according to claim 16 wherein the plurality of processors are further operative to

change the tag of the work entry to a tag corresponding to the partition identified in data flow entry;

add an indication of the priority to the work entry; and

submit the work entry to the work order module.

18. The apparatus according to claim 1 wherein the plurality of processors are further operative to

schedule, if the partition associated with the tag is a root partition, a packet for transmission from a network interface.

19. A method comprising

maintaining a queue of work entries, one or more of the work entries including a task description, a packet pointer, and a tag;

and

scheduling work entries in the queue for a plurality of processors such that only a single processor of the plurality of processors is provided a work entry labeled with a given tag;

maintaining in a memory a hierarchical partition configuration, the hierarchical partition configuration comprising a plurality of partitions;

iteratively executing a partition scheduling process across the plurality of processors, the partition scheduling process comprising

receiving, at a processor of the plurality of processors, an indication of a first work entry, wherein the first work entry is associated with a packet to be processed and includes a tag identifying a partition of the plurality of partitions;

forwarding the packet corresponding to the first work entry to a parent partition of the identified partition by modifying the first work entry to include a tag of the parent partition; and

resubmitting the first modified work entry to a work order module.

20. The method of claim 19 wherein the partition scheduling process further comprises

selecting, if the parent partition of the identified partition is a root partition, a ghost root partition from a plurality of ghost root partitions;

and

identifying a tag of the selected ghost root partition.

21. The method of claim 19 wherein the partition scheduling process further comprises

periodically accessing a parent partition data structure corresponding to the parent partition of the partition associated with the tag to identify a suggested target rate.

22. The method of claim 19 wherein the partition scheduling process further comprises

periodically computing a suggested target rate for child partitions based on a target rate for the partition associated with the tag and the number of active child partitions.

23. The method of claim 19 wherein the partition scheduling process further comprises

periodically computing a suggested target rate for child partitions based on a target rate for the partition associated with the tag, an amount of data queued for the partition associated with the tag, and the number of active child partitions.

24. The method of claim 19 wherein the partition scheduling process further comprises conditionally flagging the forwarded packet if the packet is the first packet forwarded during a target rate adjustment interval.

25. The method of claim 19 wherein the partition scheduling process further comprises incrementing an active child partition counter responsive to a flag associated with the packet set by a child partition of the partition associated with the tag during execution of a previous work entry.

26. The method of claim 19 wherein the partition scheduling process further comprises conditionally forwarding the packet to the parent partition based on a target rate associated with the partition associated with the tag.

27. The method of claim 19 wherein the partition scheduling process further comprises

adding tokens to a token bucket associated with the partition associated with the tag based on a target rate associated with the partition and a last token update time;

conditionally forwarding the packet to the parent partition based on a size of tire packet and a current number of tokens in the token bucket of the partition associated with the tag.

28. The method according to claim 27 wherein the partition scheduling process further comprises adding tokens to the token bucket up to a maximum token limit.

29. The method according to claim 27 wherein the partition scheduling process further comprises deducting, responsive to forwarding the packet, tokens from the token bucket of the partition associated with the tag.