Search apparatus

• US 6,009,423 A
• Filed: 10/29/1997
• Issued: 12/28/1999
• Est. Priority Date: 10/30/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Technologies Ltd (HP Inc.)
• Inventors: Moran, Paul J.
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/960,239
• Time in Patent Office: 790 Days
• Field of Search: 707/1, 707/2, 707/3, 707/8, 707/5, 395/200.5, 395/200.8, 395/200.57, 395/200.58, 395/200.68, 395/200.51, 370/254, 370/349, 370/389, 370/392, 370/401, 370/402, 370/395, 370/399, 370/465, 370/410, 380/49, 380/23, 340/825.05, 708/491, 708/493, 708/628, 708/656
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A search apparatus and method for establishing efficiently whether a particular number, eg a MAC address, is stored in a database, eg in a communications bridge. The search is conducted stepwise on the basis of portions of the number, until one or zero match is found in the database. In the event that one match is found, a final confirmation is made that the whole of the number located and the number searched for are the same. This provides an efficient way to search among a subset of possible very large numbers.

Claims

1. A device arranged to establish if a particular one of all possible M-digit numbers is stored in a storage means, said storage means being capable of storing a subset of possible M-digit numbers, the device comprising:

search table means comprising a main search table and a plurality of subsidiary search tables having entries stored therein each entry in the main or a subsidiary search table comprising one of (i) an address of one M-digit stored in said storage means, (ii) a pointer to a subsidiary search table from which a further entry should be recovered, and (iii) an end indication being neither a valid said address nor a valid said pointer;

means arranged to recover one or more entries sequentially from said search table means beginning with said main search table on the basis of specified portions of said M-digit number until the recovered entry comprises either a said address being the address of the only M-digit number stored in said storage means which matches said specified M-digit number in the specified portion or portions so far used, or a said end indication indicating that there no such M-digit numbers stored in said storage means; and

means arranged to confirm whether the one M-digit number identified in the former case is the same as said specified M-digit number.

2. A device according to claim 1 in which said specified portions are selected such that portions of said M-digit number which are more likely to vary in said stored subset are used before portions which are less likely to vary.

3. A device according to claim 1 in which said M-digit number is a binary number having 48 bits, the main search table having 65,536 entries and the first specified portion of said 48-bit number being a specified 16 bit portion.

4. A device according to claim 3 in which said 16 bit portion comprises the least significant 16 bits of said 48-bit number.

5. A device according to claim 3 in which each specified portion of the 48-bit number subsequent to the first is a specified 4 bit portion.

6. A communications device comprising a plurality of ports to each of which a computing device may be attached, and which is arranged to receive communications from said computing devices and to transmit said communications from the port or ports necessary for the communications to reach their intended destination(s), said device comprising means for determining, for each received communication, an intended destination address, storage means for storing a subset of the possible destination addresses and information regarding with which of said ports each of said subset is associated, and search means arranged to establish if said intended destination address is stored in said storage means, said search means comprising:

search table means comprising a main search table and a plurality of subsidiary tables having entries stored therein each entry in the main or a subsidiary search table comprising one of (i) a storage means of one possible destination address stored in said storage means, (ii) a pointer to a subsidiary search table from which a further entry should be recovered, and (iii) an end indication being neither a valid said storage means address nor a valid said pointer;

means arranged to recover one or more entries sequentially from said search table means beginning with said main search table on the basis of specified portions of said intended destination address until the recovered entry comprises either a said storage means address being the address of the only possible destination address stored in said storage means which matches said intended destination address in the specified portion or portions so far used, or a said end indication indicating that there are no such possible destination addresses stored in said storage means; and

means arranged to confirm whether the one possible destination address identified in the former case is the same as said intended destination address.

7. A device according to claim 6 being a computer network device and in which said M-digit number is a MAC address.

8. A device according to claim 6 in which said specified portions are selected such that portions of said intended destination address which are more likely to vary in said stored subset are used before portions which are less likely to vary.

9. A device according to claim 6 in which said intended destination address is a binary number having 48 bits, the main search table having 65,536 entries and the first specified portion of said 48-bit number being a specified 16 bit portion.

10. A device according to claim 9 in which said 16 bit portion comprises the least significant 16 bits of said 48-bit binary number.

11. A device according to claim 9 in which each specified portion of the 48-bit binary number subsequent to the first specified 4 bit portion.

12. A method of establishing if a specified one of all possible M-digit numbers is stored in a storage means, said storage means being capable of storing a subset of all possible M-digit numbers, the method comprising:

providing a search table comprising a main search table and a plurality of subsidiary search tables having entries stored therein each entry the main or a subsidiary search table comprising one of (i) an address of one M-digit number stored in said storage means, (ii) a pointer to a subsidiary search table from which a further entry should be recovered, and (iii) an end indication being neither a valid said address nor a valid said pointer;

searching by recovering one or more entries sequentially from said search table means beginning with said main search table on the basis of specified portions of said M-digit number until the recovered entry comprises either a said address being the address of the only M-digit number stored in said storage means which matches said specified M-digit number in the specified portion or portions so far used, or a said end indication indicating that there are no such M-digit numbers stored in said storage means; and

confirming, in the former case, whether the one M-digit number located is the same as said specified M-digit number.

13. A method according to claim 12 in which said specified portions are selected such that portions of said M-digit number which are more likely to vary in said stored subset are used before portions which are less likely to vary.

14. A method according to claim 12 in which said M-digit number is a binary number having 48 bits, the main search table having 65,536 entries and the first specified portion of said 48-bit number being a specified 16 bit portion.

15. A method according to claim 14 in which said 16 bit portion comprises the least significant 16 bits of said 48-bit number.

16. A method according to claim 14 in which each specified portion of the 48-bit number subsequent to the first is a specified 4 bit portion.