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

• US 7,302,432 B2
• Filed: 07/23/2003
• Issued: 11/27/2007
• Est. Priority Date: 08/31/2000
• Status: Expired due to Fees

• 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): LEROUX, ETIENNE PIERRE
• Application Number:
  US10/625,320
• Publication Number:
  US 20040054655A1
• Time in Patent Office: 1,588 Days
• Field of Search: 707/1, 707/2, 707/3, 707/6, 707/10, 707/104.1, 370/216, 370/229, 370/392, 370/395.3, 370/389, 370/398, 370/400, 370/458, 714/799, 709/225
• US Class Current: 707/754
• 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 for receiving and forwarding data packets comprising:

at least one ingress port for receiving data packets, at least one of the data packets associated with a virtual LAN identifier;

at least one egress port for forwarding the data packets; and

forwarding logic which provides a translated identifier for the virtual LAN identifier, the forwarding logic comprising;

a filtering database that provides a forward vector for the translated identifier from a single search of the filtering database.

2. The switch of claim 1 wherein the forwarding logic assigns a default value to the virtual LAN identifier.

3. The switch of claim 1 wherein the translated identifier includes a group identifier and a group member identifier for the virtual LAN.

4. The switch of claim 3, wherein the filtering database includes a first entry and a second entry.

5. The switch of claim 4 wherein the filtering database provides the forward vector associated with the first entry when the translated identifier matches the first entry and provides the forward vector associated with the second entry when only the group identifier portion of the translated identifier matches the second entry.

6. The switch of claim 1 wherein the filtering database is a content addressable memory.

7. The switch of claim 1 wherein the filtering database is a ternary content addressable memory.

8. The switch of claim 1 wherein the virtual LAN identifier is stored in a header included in the received data packet.

9. The switch of claim 1 wherein the forwarding logic further comprises:

a forward vector table which stores the forward vector associated with the received data packet, the filtering database providing a pointer to the location of the forward vector in the forward vector table.

10. A switch for receiving and forwarding data packets comprising:

at least one ingress port for receiving data packets, each data packet including a MAC destination address;

at least one egress port for forwarding the data packets,

forwarding logic which provides a translated identifier based on a virtual LAN identifier associated with the received data packet, the forwarding logic comprising;

a filtering database which provides a forward vector corresponding to the translated identifier and the MAC destination address from a single search of the filtering database.

11. The switch of claim 10 wherein the forwarding logic assigns a default value to the virtual LAN identifier.

12. The switch of claim 10 wherein the translated identifier includes a group identifier and a group member identifier.

13. The switch of claim 12 wherein the filtering database includes a first entry and a second entry.

14. The switch of claim 13 wherein the filtering database provides the forward vector associated with the first entry when the translated identifier matches the first entry and provides the forward vector associated with a second entry when the group identifier portion of the translated identifier and the second identifier field match the second entry.

15. The switch of claim 10 wherein the filtering database is a content addressable memory.

16. The switch of claim 10 wherein the filtering database is a ternary content addressable memory.

17. The switch of claim 10 wherein the virtual LAN identifier is stored in a header included in the received data packet.

18. The switch of claim 10 wherein the forwarding logic further comprises:

a forward vector table which stores the forward vector associated with the received data packet, the filtering database providing a pointer to the location of the forward vector in the forward vector table.