Multi-dimensional computation distribution in a packet processing device having multiple processing architecture

• US 7,610,330 B1
• Filed: 03/30/2006
• Issued: 10/27/2009
• Est. Priority Date: 03/30/2006
• Status: Expired due to Fees

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Packeteer Incorporated (Gen Digital Inc.)
• Inventors: Quinn, Michael J., Stabile, James J., Hankins, Scott A., Archard, Paul Leslie
• Primary Examiner(s): Abdullahi; Salad
• Assistant Examiner(s): SCOTT, RANDY A
• Application Number:
  US11/396,070
• Time in Patent Office: 1,307 Days
• Field of Search: 709/201, 709/219, 709/251, 709/220, 709/221, 709/203, 709/206, 709/207
• US Class Current: 709/201
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/2483 involving identification of individual flows

Abstract

Flow-aware task distribution in network devices having multiple processor architectures. In one embodiment, the present invention can be used for high bandwidth network processing in an application and flow aware Quality of Service (QoS) network device. In some implementations, the present invention provides a task distribution architecture capable of flow state awareness and link level QoS control. In some implementations, the present invention can incorporate one or more processes, such as flow distributors and device distributors, that route packets for processing among different processing units on the basis flow correspondence and/or link or network path attributes. The flow and device distributors, in one implementation, allow for the separation and paralletization of packet processing functionality into flow-specific and link-specific processing units, allowing for a highly-scalable, flow-aware task distribution in a network device that processes network application traffic.

Claims

1. An apparatus, comprising

one or more network interfaces;

a memory;

a plurality of processing units, each processing unit comprising;

one or more processors;

one or more processing queues;

a framework array, stored in the memory, comprising a plurality of hook points, each hook point corresponding to a framework functional module;

a framework processor module, stored in the memory, comprising instructions operative to cause the one or more processors and the processing unit to

read a packet from the one or more processing queues;

starting with the framework functional module corresponding to the hook point identifier associated with the packet, successively invoke the framework functional modules in the framework array to operate on the packet until an invoked framework functional module abducts the packet;

a message router operative to

transmit processing of packets to selected processing units;

place packets received from message routers of the plurality of processing units in a processing queue of the one or more processing queues; and

a plurality of framework functional modules, wherein, for at least one of the processing units, at least one framework functional module of the plurality of framework functional modules, comprises a flow distributor module, wherein the flow distributor module is operative to

when invoked by the framework processor module, abduct packets from the framework processor module;

select processing units to process packets based on data flows the packets belong, wherein two packets belong to the same data flow when the two packets have at least the same source network address, destination network address, and port number, and packets belonging to the same data flow are processed by the same processing unit,

identify, for packets associated with existing data flows, previously selected processing units, and

pass packets to the message router for routing to selected processing units.

2. The apparatus of claim 1 wherein the plurality of framework functional modules comprises one or more of a receive module, a de-tunnel module, a de-compression module, a flow update module, an inspection module, a policy identification module, a flow policy enforcement module, link-level control module, a pre-tunnel module, a compression module, a tunnel module and a transmit module.

3. The apparatus of claim 1 wherein, for at least one of the processing units, the plurality of framework functional modules comprises a device distributor module, wherein the device distributor module is operative to

abduct packets from the framework processor module;

select processing units to process packets based on one or more network path attributes corresponding to the respective packets; and

pass packets to the message router for routing to selected processing units.

4. The apparatus of claim 3 wherein the one or more network path attributes comprise one or more of an ingress network interface and an egress network interface.

5. The apparatus of claim 1 wherein at least one of the processing units in the plurality of processing units is an input/output processing unit, and wherein the framework functional modules corresponding to the input/output unit comprise a receive module and a transmit module;

wherein the receive module is operative to

parse packets relative to one or more attributes;

associate packets with respective data flows; and

populate one or more fields of data structures corresponding to the packets; and

wherein the transmit module is operative to

cause packets to be transmitted from a selected network interface of the one or more network interfaces.

6. The apparatus of claim 5 and wherein at least two of the processing units in the plurality of processing units are flow-level processing units, and wherein the framework functional modules corresponding to the flow-level processing units comprise one or more of a flow update module, an inspection module, a policy identification module, a flow policy enforcement module;

wherein the flow update module is operative to maintain one or more statistics, metrics and/or variables for respective data flows;

wherein inspection module is to identify one or more network applications corresponding to data flows;

wherein the policy identification module is operative to identify one or more policies for respective data flows; and

wherein flow policy enforcement module is operative to apply one or more policies identified by the policy identification module to individual data flows or individual packets.

7. The apparatus of claim 6 wherein the input/output processing unit comprises a flow distributor module operative to distribute processing of packets to the at least two flow-level processing units.

8. The apparatus of claim 3 and wherein at least two of the processing units in the plurality of processing units are link-level processing units each corresponding to a respective link, and wherein the framework functional modules corresponding to the link-level processing units comprise one or more of a partition module, and a rate control module;

wherein the partition module is operative to partition a link into a plurality of virtual links, and wherein the rate control module is operative to apply one or more rate control policies to data flows traversing a link.

9. The apparatus of claim 8 wherein at least one of the processing units comprises the device distributor module operative to transfer processing of packets to selected link-level processing units.

10. The apparatus of claim 1 wherein two or more hook points in the framework array correspond to the same framework functional module in the plurality of framework functional modules.

11. The apparatus of claim 1 wherein the message router is further operative to discover message routers of other processing units.

12. The apparatus of claim 1 wherein one of the processing units of the plurality of processing units contains the one or more network interfaces.

13. The apparatus of claim 1 wherein at least one processing unit of the plurality of the processing units comprises a memory.

14. The apparatus of claim 1 wherein at least one processing unit of the plurality of the processing units is implemented as a server blade.

15. The apparatus of claim 1 further comprising an interconnect communicably coupling the processing units.

16. An apparatus comprising:

a plurality of flow-level processing units each operative to perform one or more operations on data flows traversing a communications path; and

at least one input-output processing unit comprising

at least one network interface for receiving and transmitting packets, and

a flow distributor operative to

identify data flows corresponding to packets;

distribute, based on the identified data flow, processing of the packet to a select processing unit from the plurality of flow level processing units, such that packets belonging to the same data flow are processed by the same processing unit and two packets belong to the same data flow when the two packets have at least the same source network address, destination network address, and port number;

identify a network path attribute corresponding to the packet; and

distribute, based on the identified network path attribute, processing of the packet to a select processing unit from the plurality of processing units of the network device,

wherein at least one of the processing units comprises

a memory;

one or more processors;

one or more processing queues;

a framework array, stored in the memory, comprising a plurality of hook points, each hook point corresponding to a framework functional module;

a framework processor module, stored in the memory, comprising instructions operative to cause the one or more processors and the processing unit to read packets from the one or more processing queues;

starting with the framework functional module corresponding to the hook point identifier associated with the packet, successively invoke the framework functional modules in the framework array until an invoked framework functional module abducts the packet;

a message router operative to transmit processing of packets to selected processing units;

place packets received from message routers of the plurality of processing units in a processing queue of the one or more processing queues; and

a plurality of framework functional modules.