Method and apparatus for performing packet classification for policy-based packet routing

• US 7,143,231 B1
• Filed: 09/23/1999
• Issued: 11/28/2006
• Est. Priority Date: 09/23/1999
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan
• Primary Examiner(s): To, Doris H.
• Assistant Examiner(s): BLOUNT, STEVEN
• Application Number:
  US09/406,170
• Time in Patent Office: 2,623 Days
• Field of Search: 370/412, 370/229, 370/230.1, 370/230, 370/235, 370/395.2, 370/395.42, 370/395.4, 370/395.41, 370/428, 370/429, 370/395.43, 711/108, 365/49, 712/300
• US Class Current: 711/108
• CPC Class Codes: G11C 15/04 using semiconductor elements
• CPC Class Codes: G11C 8/04 using a sequential addressing device, e.g. shift register, counter
• CPC Class Codes: H03K 23/56 Reversible counters H03K23/52 and H03K23/548 take precedence
• CPC Class Codes: H03K 3/356139 with synchronous operation

Abstract

A method and apparatus for performing packet classification in a digital signal processor for policy-based packet routing. For one embodiment, the digital signal processor includes a policy statement table for storing policy statements. Each policy statement has associated with it a priority number that indicates the priority of the policy statement relative to other policy statements. The priority numbers are separately stored in a priority index table. The priority index table includes priority logic that determines the most significant priority number from among the policy statements that match an incoming packet during a classification of filter operation. The priority logic also identifies the location in the priority index table of the most significant priority number. The identified location in the priority index table can be used to access associated route information or other information stored in a route memory array. New policy statements can be added at any location in the policy statement table, and the associated priority numbers loaded into corresponding locations in the priority index table. Priority numbers of previously stored priority policy statements may be updated such that the new policy statement does not have the same priority number as the previously stored policy statements.

Claims

1. A method of adding a new policy statement to a plurality of policy statements stored in a first memory, comprising:

comparing a new priority number associated with the new policy statement

to a plurality of priority numbers stored in a second memory, the plurality of priority numbers each associated with a respective one of the plurality of policy statements stored in the first memory;

determining that the new priority number is more significant than one of the plurality of priority numbers stored in the second memory;

updating the one of the plurality of priority numbers in the second memory without changing its physical location in the second memory;

writing the new priority number to an available location in the second memory; and

writing the new policy statement to an available location in the first memory.

2. The method of claim 1, wherein the new priority number is more significant than the one of the plurality of priority numbers when the new priority number is greater than or equal to the one of the plurality of priority numbers.

3. The method of claim 1, wherein the new priority number is more significant than the one of the plurality of priority numbers when the new priority number is less than or equal to the one of the plurality of priority numbers.

4. A method of adding a new policy statement to a plurality of policy statements stored in a first memory, comprising:

altering a new priority number associated with the new policy statement;

comparing the altered new priority number to a plurality of priority numbers stored in a second memory, the plurality of priority numbers each associated with a respective one of the plurality of policy statements stored in the first memory;

determining that the altered new priority number is more significant than one of the plurality of priority numbers stored in the second memory;

updating the one of the plurality of priority numbers in the second memory without changing its physical location in the second memory;

writing the unaltered new priority number to an available location in the second memory; and

writing the new policy statement to an available location in the first memory.

5. The method of claim 4, wherein the altered new priority number is more significant than the one of the plurality of priority numbers when the altered new priority number is greater than the one of the plurality of priority numbers.

6. The method of claim 4, wherein the altered new priority number is more significant than the one of the plurality of priority numbers when the altered new priority number is less than the one of the plurality of priority numbers.

7. The method of claim 4, wherein altering the new priority number comprises decrementing the new priority number.

8. The method of claim 4, wherein altering the new priority number comprises incrementing the new priority number.