Pipelined searches with a cache table

• US 20020039365A1
• Filed: 11/06/2001
• Published: 04/04/2002
• Est. Priority Date: 03/17/1999
• Status: Abandoned Application

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Kalpathy, Paul, Jorda, Mike
• Application Number:
  US09/985,763
• Publication Number:
  US 20020039365A1
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 12/4645 Details on frame tagging routing of packets H04L45/00; support for virtual LAN H04L49/354
• CPC Class Codes: H04L 12/467 Arrangements for supporting untagged frames, e.g. port-based VLANs
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/9015 for supporting a linked list
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

The invention is table search device having a table that has a plurality of entries and a cache having a subset of entries of the plurality of entries of the table. A search engine is configured to first search the cache in a first number of search cycles and then search the table in a second number of search cycles based on search results of the cache. The search engine connected to the table and the cache.

Claims

1. A table search device comprising:

a table having a plurality of entries;

a cache having a subset of entries of said plurality of entries of said table; and

a search engine configured to first search said cache in a first number of search cycles and then search said table in a second number of search cycles based on search results of said cache, said search engine connected to said table and said cache.

2. The device as recited in claim 1 wherein said search engine comprises:

a search stage zero segment configured to search said cache in said first number of search cycles, said search stage zero segment connected to said cache; and

a search stage one segment configured to search said table in a second number of search cycles based on search results of said cache, said search stage one segment connected to said search stage zero segment and said table.

3. The device as recited in claim 1 wherein:

said first number of search cycles is less than said second number of search cycles.

4. The device as recited in claim 1 wherein:

said first number of search cycles is equal to said second number of search cycles.

5. The device as recited in claim 2 wherein:

said first number of search cycles is less than said second number of search cycles.

6. The device as recited in claim 2 wherein:

said first number of search cycles is equal to said second number of search cycles.

7. A table search system comprising:

a table means for storing a plurality of entries;

a cache means for storing a subset of entries of said plurality of entries of said table means; and

a search engine means for initially searching said cache means in a first number of search cycles and then searching said table means in a second number of search cycles based on search results of said cache means.

8. The system as recited in claim 7 wherein said search engine means comprises:

a search stage zero segment means for searching said cache means in said first number of search cycles, said search stage zero segment means being connected to said cache means; and

a search stage one segment means for searching said table means in said second number of search cycles based on search results of said cache means, said search stage one segment means being connected to said table and said search stage zero means.

9. The system as recited in claim 7 wherein:

said first number of search cycles is less than said second number of search cycles.

10. The system as recited in claim 7 wherein:

said first number of search cycles is equal to said second number of search cycles.

11. The system as recited in claim 8 wherein:

said first number of search cycles is less than said second number of search cycles.

12. The system as recited in claim 8 wherein:

said first number of search cycles is equal to said second number of search cycles.

14. The method as recited in claim 13 wherein:

said first number of search cycles used to search said cache is less than said second number of search cycles used to search said table.

15. The method as recited in claim 13 wherein:

said first number of search cycles used to search said cache is equal to said second number of search cycles used to search said table.

17. The network switch as recited in claim 16 wherein said search engine comprises:

a search stage zero segment configured to search said ARL cache in said first number of search cycles, said search stage zero segment connected to said ARL cache; and

a search stage one segment configured to search said ARL table in a second number of search cycles based on search results of said ARL cache, said search stage one segment connected to said search stage zero segment and said ARL table.

18. The network switch as recited in claim 16 wherein:

said first number of search cycles is less than said second number of search cycles.

19. The device as recited in claim 16 wherein:

said first number of search cycles is equal to said second number of search cycles.

20. The network switch as recited in claim 17 wherein:

said first number of search cycles is less than said second number of search cycles.

21. The network switch as recited in claim 17 wherein:

said first number of search cycles is equal to said second number of search cycles.

13. A method for performing a table lookup comprising the steps of:

creating a table having a plurality of entries;

creating a cache having a subset of entries of said plurality of entries of said table;

searching said cache in a first number of search cycles; and

searching said table in a second number of search cycles based on search results of said cache.

16. A network switch comprising:

an ARL table having a plurality of entries;

a ARL cache having a subset of entries of said plurality of entries of said ARL table; and

a search engine configured to first search said ARL cache in a first number of search cycles and then search said ARL table in a second number of search cycles based on search results of said ARL cache, said search engine connected to said ARL table and said ARL cache.