Method and apparatus for searching a filtering database with one search operation

• US 6,633,567 B1
• Filed: 08/31/2000
• Issued: 10/14/2003
• Est. Priority Date: 08/31/2000
• Status: Expired due to Term

• Current Assignee: MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management)
• Original Assignee: Mosaid Technologies Incorporated (MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management))
• Inventors: Brown, David A.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Le, Debbie M.
• Application Number:
  US09/652,196
• Time in Patent Office: 1,139 Days
• Field of Search: 707/1-3, 370/389, 370/392, 370/395.1, 370/395.3, 370/395.31, 370/395.53, 370/395.54, 370/397, 370/399, 711/108, 709/238, 709/239, 709/245
• US Class Current: 370/395.3
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• 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: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Multiple searches of a filtering database increase the time for filtering a data packet received by a switch. A switch including a translator and a filtering database for performing a single search is presented. The translator provides a translated identifier for an identifier associated with a data packet received by the switch. The translated identifier includes a group identifier corresponding to a virtual LAN group (FID) and a group member number corresponding to an identified virtual LAN (VID). The filter data base stores a static entry and a dynamic entry. The static entry stores a forwarding decision for the data packet associated with the translated identifier. The dynamic entry stores a forwarding decision for the data packet associated with the group identifier included in the translated identifier and the group member number set to don'"'"'t care. The translated identifier allows a filtering database to provide the forwarding decision stored in the static entry or the dynamic entry for the identifier from a single search operation.

Claims

1. A switch comprising:

a translator which provides a translated identifier for a virtual LAN identifier associated with a received data packet, the translated identifier including a group identifier corresponding to a virtual LAN group and a group member number corresponding to the identified virtual LAN; and

a filtering database storing a static entry and a dynamic entry which provides a forwarding decision, for the received data packet, from a single search of the filtering database for a match for the forwarding decision associated with the translated identifier stored in the dynamic entry or the static entry, the dynamic entry storing the forwarding decision associated with the group identifier included in the translated identifier and the group member number set to a don'"'"'t care, the static entry storing the forwarding decision associated with the translated identifier.

2. The switch as claimed in claim 1 wherein the group member number identifies one of a plurality of members associated with the group identifier.

3. The switch as claimed in claim 1 wherein the filtering database is a Content Addressable Memory.

4. The switch as claimed in claim 3 wherein the Content Addressable Memory is a ternary Content Addressable Memory.

5. The switch as claimed in claim 1 wherein the virtual LAN identifier is stored in a header included in the received data packet.

6. The A switch as claimed in claim 1 wherein the virtual LAN identifier is a default virtual LAN identifier assigned by the switch to the received data packet.

7. A method for selecting a forward vector for a received data packet comprising the steps of:

translating a virtual LAN identifier associated with the received data packet to a translated identifier, the translated identifier including a group identifier corresponding to a virtual LAN group and a group member number corresponding to the identified virtual LAN;

storing in a filtering database a static entry and a dynamic entry, the forward vector associated with the translated identifier stored in the static entry associated with the translated identifier or the dynamic entry associated with the group identifier and the group member number set to don'"'"'t care; and

providing, from a single search operation for the translated identifier in the filtering database the forward vector for the received data packet stored in the static entry or the dynamic entry in the filtering database.

8. The method as claimed in claim 7 wherein the group member number identifies one of a plurality of members associated with the group identifier.

9. The method as claimed in claim 7 wherein the filtering database is a Content Addressable Memory.

10. The method as claimed in claim 9 wherein the Content Addressable Memory is a ternary Content Addressable Memory.

11. The method as claimed in claim 7 wherein the virtual LAN identifier is stored in a header included in the received data packet.

12. The method as claimed in claim 9 wherein the virtual LAN identifier is a default virtual LAN identifier assigned by the switch for the received data packet.

13. A method for selecting a forward vector for a received data packet comprising the steps of:

means for translating a virtual LAN identifier associated with the received data packet, the translated identifier including a group identifier corresponding to a virtual LAN and a group member number corresponding to the identified virtual LAN;

means for storing a static entry and a dynamic entry, the forward vector associated with the translated identifier stored in the static entry associated with the translated identifier or in the dynamic entry associated with the group identifier and the group member number set to don'"'"'t care; and

means for providing, from a single search operation for the translated identifier in the filtering database the forward vector for the received data packet stored in the static entry or the dynamic entry in the filtering database.

14. The method as claimed in claim 13 wherein the group member number identifies one of a plurality of members associated with the group identifier.

15. The method as claimed in claim 13 wherein the filtering database is a Content Addressable Memory.

16. The method as claimed in claim 15 wherein the Content Addressable Memory is a ternary Content Addressable Memory.

17. The method as claimed in claim 13 wherein the virtual LAN identifier is stored in a header included in the received data packet.

18. The method as claimed in claim 13 wherein the virtual LAN identifier is a default virtual LAN identifier assigned by the switch for the received data packet.