Method for comparison between a pattern sequence and a variable length key

• US 6,341,346 B1
• Filed: 02/05/1999
• Issued: 01/22/2002
• Est. Priority Date: 02/05/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Benayoun, Alain, Le Pennec, Jean-Francois, Michel, Patrick, Pin, Claude
• Primary Examiner(s): Treat, William M.
• Application Number:
  US09/245,182
• Time in Patent Office: 1,082 Days
• Field of Search: 712/36, 712/200, 712/223, 712/245, 712/248, 370/392, 709/238
• US Class Current: 712/223
• CPC Class Codes: G06F 9/30018 Bit or string instructions
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX

Abstract

A method is disclosed for comparing a pattern sequence with a variable length key. A first bit of this sequence is identified by a pointer, the length and the location of the key are identified by a code word (W, S), the method includes a preliminary step of identifying the sequence and then performing a comparison with the variable length key.

Claims

1. A method for comparing a pattern sequence with a variable length key wherein, a first bit of said pattern sequence is identified by a pointer, the length and a location of said key are identified by a code word (W, S), comprising the steps of identifying said sequence and comparing said pattern sequence with said variable length key to determine if they match.

2. The method according to claim 1, wherein a further step is identified by a first address (LEFT ADDRESS) when said comparison is true indicating a match.

3. The method according to claim 2, wherein said pattern sequence is shifted by a first shifting value (W, S) equal to the length of said variable length key prior to said further step.

4. The method according to claim 2, wherein said first address (LEFT ADDRESS) includes a zone indication (ZL).

5. The method according to claim 1, wherein a further step is identified by a second address (RIGHT ADDRESS) when said comparison is false indicating no match.

6. The method according to claim 5, wherein said second address (RIGHT ADDRESS) includes a zone indication (ZR).

7. The method according to claim 2 wherein a predetermined value of a field (ZL) of said first address (LEFT ADDRESS) identifies a part of said first address as an external return address.

8. The method according to claim 5 wherein a predetermined value of a field (ZR) of said second address (RIGHT ADDRESS) identifies a part of said second address as an external return address.

9. The method according to claim 8, wherein said second address (RIGHT ADDRESS) is a predetermined function of a first address (LEFT ADDRESS).

10. The method according to anyone of claims 1-9, wherein an age word (AGE) associated with said comparison step is incremented when said comparison step is performed.

11. The method according to anyone of claims 1-9, wherein a parent word (PARENT ADDRESS) associated with said comparison step identifies the address of a step preceding said comparison step.

12. The method according to claim 11, wherein said parent word includes a zone indication (ZC).

13. The method according to anyone of claims 1-9 wherein, when said comparison step is used in conjunction with other steps, it is identified by a mode indication.