Methods and apparatus for directing packets among a group of processors

• US 7,254,639 B1
• Filed: 05/20/2002
• Issued: 08/07/2007
• Est. Priority Date: 05/20/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Siegel, Kenneth P., Krawczyk, John J.
• Primary Examiner(s): Chang; Jungwon
• Application Number:
  US10/151,132
• Time in Patent Office: 1,905 Days
• Field of Search: 709/226, 709/245, 709/238, 370/395.32, 370/392, 370/389, 370/395.31, 718/105
• US Class Current: 709/238
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

The invention is directed to techniques for allocating packets received by the flow control processor located on the input/output (I/O) communications interface of the data communications device to a forwarding entity or session processor, chosen from a plurality of session processors, for further processing or routing. The session processors have the same ability to make decisions relating to the processing and routing of the packet as does the flow control processor and can have per second packet processing rates that are different from the flow control processor located on the I/O communications interface of the data communications device. To allocate the packets to the session processors for further processing, the flow control processor processes information located within the header component of the received packet. Based upon the results of this processing, the flow control processor selects a session processor from a plurality of session processors and transfers the packet to the selected session processor for further processing and routing of the packet. The flow control processor on the I/O communications interface, therefore, acts to load balance incoming packets among other session processors, thereby alleviating potential congestion on the port caused by the reception of multiple packets from multiple clients and reducing potential degradation of performance of the data communications device.

To allocate the packets to the session processors for further processing, the flow control processor processes information located within the header component of the received packet. Based upon the results of this processing, the flow control processor selects a session processor from a plurality of session processors and transfers the packet to the selected session processor for further processing and routing of the packet. The flow control processor on the I/O communications interface, therefore, acts to load balance incoming packets among other session processors, thereby alleviating potential congestion on the port caused by the reception of multiple packets from multiple clients and reducing potential degradation of performance of the data communications device.

Claims

1. In a data communications device having a plurality of session processors, each session processor capable of performing a routing decision for a packet, a method for directing the packet to a session processor of the plurality of session processors for processing, the method comprising the steps of:

receiving a packet, the packet having a header component;

generating an index value based upon at least a portion of the header component, the index value corresponding to a session processor for the packet;

initializing a lookup table having index value entries and corresponding session processor entries, wherein initializing comprises creating session processor entries in the lookup table for each of the plurality of session processors, the number of session processor entries within the table based upon at least one performance characteristic for each session processor within the plurality of session processors; and

selecting the session processor to process the packet from the plurality of session processors based upon the index value in the lookup table.

2. The method of claim 1 wherein the step of receiving further comprises obtaining at least a portion of the header component from the packet.

3. The method of claim 2 wherein the step of obtaining comprises retrieving transport layer information from the header component.

4. The method of claim 1 wherein the step of generating comprises combining a portion of the header component with a masking function to generate the index value, the index value corresponding to a session processor for the packet, combining including combining transport layer information from the header component with the masking function to generate the index value.

5. The method of claim 1 wherein the step of selecting comprises selecting a routing vector for the packet based upon the index value, the routing vector directing the packet to a corresponding session processor.

6. The method of claim 1 wherein the step of selecting comprises:

comparing the index value with index value entries in a lookup table, each index value entry corresponding to a session processor; and

selecting a session processor for the packet, the session processor corresponding to the index value entry in the lookup table based on the comparison.

7. The method of claim 1 wherein the step of creating further comprises deriving at least one performance characteristic for each session processor.

8. The method of claim 1 further comprising the step of repeating the steps of receiving, generating, and selecting for a plurality of packets to cause load balancing of the packets among the plurality of session processors.

9. The method of claim 1 further comprising:

initializing a lookup table having index value entries and corresponding weighted session processor entries, wherein;

receiving further comprises obtaining at least a portion of the header component from the packet; and

generating the index value further comprises combining a portion of the header component with a masking function to generate the index value, the index value corresponding to a session processor for the packet, combining including combining transport layer information from the header component with the masking function to generate the index value;

comparing the index value with index value entries in a lookup table, each index value entry corresponding to a session processor; and

selecting a session processor for the packet, the session processor corresponding to the index value entry in the lookup table based on the comparison, the lookup table having a plurality of entries for particular ones of the session processors for load balancing among the plurality of session processors.

10. The method of claim 9 wherein the step of initializing comprises creating session processor entries in the lookup table for each of the plurality of session processors, the number of session processor entries within the table based upon at least one performance characteristic for each session processor within the plurality of session processors, and the step of creating further comprises deriving at least one performance characteristic for each session processor, the load balancing operable to include more lookup table entries for session processors having a greater processing capability.

11. The method of claim 1 wherein initializing the lookup table comprises populating the lookup table with session processor entries such that session processors having one or more powerful performance characteristics have more session processor entries in the lookup table than session processors having one or more less powerful performance characteristics.

12. A data communications device comprising:

at least one communications interface having a flow distribution processor;

at least two session processors coupled to the flow distribution processor;

a memory coupled to the flow distribution processor; and

an interconnection mechanism coupling the at least one communications interface, the memory, and the at least two session processors;

wherein the flow distribution processor is configured to;

receive a packet, the packet having a header component;

generate an index value based upon at least a portion of the header component, the index value corresponding to a session processor for the packet;

initialize a lookup table having index value entries and corresponding performance characteristic weighted session processor entries;

create session processor entries in the lookup table for each of the plurality of session processors, the number of session processor entries within the table based upon at least one performance characteristic for each session processor within the plurality of session processors, the flow distribution processor further operable to perform load balancing by maintaining entries such that session processors having greater processing capabilities are more likely to process the received packet; and

select the session processor to process the packet from the plurality of session processors based upon the index value in the lookup table.

13. The data communications device of claim 12 wherein the flow distribution processor, when receiving, is further configured to obtain at least a portion of the header component from the packet.

14. The data communications device of claim 13 wherein the flow distribution processor, when obtaining, is further configured to receive transport layer information from the header component.

15. The data communications device of claim 12 wherein the flow distribution processor, when generating, is configured to combine a portion of the header component with a masking function to generate the index value, the index value corresponding to a session processor for the packet, the flow distribution processor, when combining, being configured to combine transport layer information from the header component with a masking function to generate the index value, the index values based on load balanced session processor selection.

16. The data communications device of claim 12 wherein the flow distribution processor, when selecting, is configured to select a routing vector for the packet based upon the index value, the routing vector indicative of a network address and directing the packet to a corresponding session processor.

17. The data communications device of claim 12 wherein the flow distribution processor, when selecting, is configured to compare the index value with index value entries in a lookup table, each index value entry corresponding to a session processor and is configured to select a session processor corresponding to the index value entry in the lookup table based on the comparison.

18. The data communications device of claim 12 wherein the flow distribution processor is further configured to derive at least one performance characteristic for each session processor.

19. The data communications device of claim 12 wherein the flow distribution processor is further configured to repeat the steps of receiving, generating, and selecting for a plurality of packets to cause load balancing of the packets among the plurality of session processors.

20. The data communications device of claim 12 wherein one of the at least two session processors is integrally formed with the flow distributor processor.

21. The data communications device of claim 12 wherein the flow distribution processor comprises a lookup table having a plurality of index value entries and a plurality of session processor entries, each session processor entry corresponding to at least one index value entry.

22. A computer program product having a computer-readable medium including computer program logic stored thereon that, when performed on a computer, causes the computer to:

receive a packet, the packet having a header component;

generate an index value based upon at least a portion of the header component, the index value corresponding to a session processor for the packet;

initialize a lookup table having index value entries and corresponding session processor entries, wherein initializing comprises creating session processor entries in the lookup table for each of the plurality of session processors, the number of session processor entries within the table based upon at least one performance characteristic for each session processor within the plurality of session processors; and

select the session processor to process the packet from the plurality of session processors based upon the index value in the lookup table.

23. A data communications device comprising:

at least one communications interface having a flow distribution processor;

at least two session processors coupled to the flow distribution processor;

a memory coupled to the flow distribution processor; and

an interconnection mechanism coupling the at least one communications interface, the memory, and the at least two session processors;

wherein the flow distribution processor includes;

means for receiving a packet, the packet having a header component;

means for generating a performance weighted index value based upon at least a portion of the header component, the index value corresponding to a session processor for the packet

means for initializing a lookup table having index value entries and corresponding performance characteristic weighted session processor entries;

means for creating session processor entries in the lookup table for each of the plurality of session processors, the number of session processor entries within the table based upon at least one performance characteristic for each session processor within the plurality of session processors, the flow distribution processor further operable to perform load balancing by maintaining entries such that session processors having greater processing capabilities are more likely to process the received packet; and

means for selecting the session processor to process the packet from the plurality of session processors based upon the index value in the lookup table.