Network switch with truncated trie look-up facility

• US 6,337,862 B1
• Filed: 05/18/2000
• Issued: 01/08/2002
• Est. Priority Date: 02/26/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Gilbert, Christopher, OʼCallaghan, Sorcha, Loughran, Kevin, OʼMalley, Edele
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): MEHRA, INDER P
• Application Number:
  US09/573,821
• Time in Patent Office: 600 Days
• Field of Search: 370/254, 370/389, 370/392, 370/395, 370/401, 370/466, 370/467, 370/475, 370/492, 370/400, 370/402, 370/403, 705/77, 709/100, 709/104, 709/105, 709/201, 709/219, 709/220, 709/221, 709/223, 709/224, 709/226, 709/227, 709/229, 713/201, 707/2, 707/7, 707/3
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

A network switch including a multiplicity of ports for the reception and forwarding of addressed data packets including network destination data and network source address data, and a forwarding database having a trie search facility organised in blocks of pointers, which are accessed by respective segments of a search key and identify in a last stage of a search forwarding data identifying each port from which a packet should be forwarded and in any stage of the search prior to the last stage a block of pointers, the switch including a device operable before the trie search facility is utilised for a given packet to compare a network destination address of the given packet with at least one stored address and when the network destination address matches the stored address to access the network source address data of the given packet for use as the search key.

Claims

1. A network switch including:

a multiplicity of ports for the reception and forwarding of addressed data packets including network destination data and network source address data; and

a forwarding database having a trie search facility organized in blocks of pointers, said trie search facility accessing said blocks in response to respective segments of a search key, each of said pointers identifying in a last stage of a search forwarding data identifying each port from which a packet should be forwarded and identifying in any stage of the search prior to said last stage a block of pointers;

the switch including means operable before the trie search facility is utilized for a given packet to compare a network destination address of said given packet with at least one stored address and when said network destination address matches said stored address to access the network source address data of said given packet for use as the search key.

2. A network switch according to claim 1 wherein some of said blocks are accessible by different segments of said network destination data and wherein said search key when said network destination address matches said stored address bypasses blocks which are accessible by said different segments of said network destination data.

3. A network switch which includes:

a multiplicity of ports for the reception and forwarding of addressed data packets each including a destination address and a source address;

a forwarding database which is organised in blocks comprising blocks of pointers and blocks of associated data, wherein said pointers identify respective blocks and the blocks of associated data provide forwarding data for packets;

and a searching means which in response to successive segments of a key accesses corresponding pointers until a pointer identifies a block of associated data;

wherein said database has blocks accessible by different segments of the destination address and blocks accessible by different segments of the source address;

and wherein said searching means is operative to compare the destination address of a packet with a set composed of at least one stored address and when said destination addresses matches said one stored address to employ a relatively short key including segments of the source address and not including segments of said destination address.

4. A network switch according to claim 3 wherein said source and destination addresses are network addresses.

5. A network switch according to claim 4 wherein said set includes a virtual network address of a group of servers.

6. A network switch according to claim 4 wherein said set includes network destination addresses of multicast traffic.