Table searching technique

• US 20030037042A1
• Filed: 12/07/2000
• Published: 02/20/2003
• Est. Priority Date: 12/08/1999
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kametani, Jun
• Granted Patent: US 7,099,324 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 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/54 Organization of routing tables
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A searching system allowing high-speed data searching and operation is disclosed. A search table is provided which stores a copy of an entry that has been retrieved from a database to retrievably store a plurality of retrieved entries. Further, an address pointer table is provided which stores a list of retrieved entries which are linked from a leading one to a bottom one. A search processor can access a plurality of retrieved entries by referring to the list stored in the address pointer table so as to be consistent with a corresponding entry stored in the database when the corresponding entry has been updated.

Claims

1. A data searching system comprising:

a database for storing a plurality of pieces of data;

a search table for storing at least one piece of data which has been selected by the database; and

an address pointer table for storing location information indicating an entry address of each piece of data stored in the search table and/or relationship information among entry addresses of pieces of data stored in the search table.

2. The data searching system according to claim 1, wherein the address pointer table comprises a plurality of memory blocks each having a fixed length on a recording medium, wherein the memory blocks are located at consecutive addresses,

wherein each of the memory blocks comprises:

a first area for storing an entry address indicating a location of a corresponding piece of data stored in the search table; and

a second area for storing one of a next block address and a bottom-indicating flag, the next block address indicating an address of a memory block storing data following the corresponding piece of data, and the bottom-indicating flag indicating that a current memory block is a bottom of a list.

3. The data searching system according to claim 1, further comprising:

a controller controlling such that the search table is searched for a desired piece of data before the database and, if a hit is found in the search table, then a found piece of data is used as a search result, and if no hit is found in the search table, then the database is searched for the desired piece of data and a found piece of data is used as a search result and is registered into the search table, wherein a piece of data with low retrieved frequency is deleted from the search table according to a predetermined condition and all linked memory blocks related to the deleted piece of data are released into available memory blocks.

4. A packet processing system comprising:

a microprocessor;

a routing table;

a memory storing a search table which is used to increase in search speed for packet forwarding; and

an address pointer table for storing location information indicating an entry address of each piece of data stored in the search table and/or relationship information among entry addresses of pieces of data stored in the search table.

5. A packet processing system comprising:

a microprocessor;

a routing table;

a searcher having a search memory connected thereto, wherein the search memory stores a search table which is used to increase in search speed for packet forwarding; and

an address pointer table for storing location information indicating an entry address of each piece of data stored in the search table and/or relationship information among entry addresses of pieces of data stored in the search table.

6. The packet processing system according to claim 5, wherein the address pointer table is provided in a main memory of the microprocessor.

7. The packet processing system according to claim 5, wherein the address pointer table is provided in the search memory.

8. The packet processing system according to claim 5, wherein the address pointer table comprises a plurality of memory blocks each having a fixed length on a recording medium, wherein the memory blocks are located at consecutive addresses,

wherein each of the memory blocks comprises:

a first area for storing an entry address indicating a location of a corresponding piece of data stored in the search table; and

a second area for storing one of a next block address and a bottom-indicating flag, the next block address indicating an address of a memory block storing data following the corresponding piece of data, and the bottom-indicating flag indicating that a current memory block is a bottom of a list.

9. A control method for controlling a packet processing system comprising:

a microprocessor;

a routing table;

a searcher having a search memory connected thereto, wherein the search memory stores a search table which is used to increase in search speed for packet forwarding; and

an address pointer table for storing location information indicating an entry address of each piece of data stored in the search table and/or relationship information among entry addresses of pieces of data stored in the search table,

the control method comprising the steps of;

a) when the routing table has been updated, accessing the address pointer table based on contents of an entry to be changed to obtain location information of the entry to be changed and entries related to the entry to be changed in the search memory; and

b) changing the entry and related entries so as to be consistent with the routing table.

10. A system comprising:

a first memory for retrievably storing a plurality of entries;

a second memory for storing a copy of an entry that has been retrieved from the first memory to retrievably store a plurality of retrieved entries;

a third memory for storing a list of retrieved entries which are linked from a leading one to a bottom one; and

a data controller for accessing a desired retrieved entry by referring to the list stored in the third memory.

11. The system according to claim 10, wherein the data controller processes the desired retrieved entry so as to be consistent with a corresponding entry stored in the first memory when the corresponding entry has been processed.

12. The system according to claim 10, wherein each of the entries stored in the first memory has a first indicator and a second indicator, the first indicator indicating which one of a single entry and an aggregated entry the entry relates to, wherein the aggregated entry has a plurality of single entries belonging thereto, and the second indicator indicating a leading address of the list in the third memory.

13. The system according to claim 10, wherein the list of retrieved entries comprises a plurality of memory blocks each corresponding to the retrieved entries, each of the memory blocks comprising an address of a corresponding retrieved entry in the second memory and a next pointer indicating one of an address of a next memory block following the memory block and an address of the memory block itself.

14. The system according to claim 12, wherein, when an aggregated entry stored in the first memory is designated, the data controller accesses the third memory depending on the second indicator of the aggregated entry to trace the list of single entries related to the aggregated entry so as to access the single entries related to the aggregated entry.

15. The system according to claim 14, wherein, when contents of the first memory have been updated, the data controller processes the single entries related to the aggregated entry so as to be consistent with the contents of the first memory.

16. A packet switching system comprising:

a routing table for retrievably storing a plurality of routing entries;

a flow table for storing a copy of a routing entry indicating a packet flow that has been retrieved from the routing table to retrievably store a plurality of retrieved packet flows;

an address pointer table for storing a list of retrieved packet flows which are linked from a leading one to a bottom one;

a search processor for accessing a desired retrieved packet flow in the flow table by referring to the list stored in the address pointer table; and

a microprocessor performing a packet routing control.

17. The packet switching system according to claim 16, wherein, when a routing entry has been designated to be processed according to predetermined routing processing, the search processor processes a corresponding retrieved packet flow in the flow table so as to be consistent with the designated routing entry stored in the routing table.

18. The packet switching system according to claim 16, wherein each of the routing entries stored in the routing table has a first indicator and a second indicator, the first indicator indicating which one of a single packet flow and an aggregated packet flow the routing entry relates to, wherein the aggregated packet flow has a plurality of single packet flows belonging thereto, and the second indicator indicating a leading address of the list in the address pointer table.

19. The packet switching system according to claim 16, wherein the list of retrieved packet flows comprises a plurality of memory blocks each corresponding to the retrieved packet flows, each of the memory blocks comprising an address of a corresponding retrieved packet flow in the flow table and a next pointer indicating one of an address of a next memory block following the memory block and an address of the memory block itself.

20. The packet switching system according to claim 18, wherein, when an aggregated routing entry stored in the routing table is designated, the search processor accesses the address pointer table depending on the second indicator of the aggregated routing entry to trace the list of single packet flows related to the aggregated routing entry so as to access the single packet flows related to the aggregated routing entry.

21. The packet switching system according to claim 20, wherein the search processor processes the single packet flows related to the aggregated routing entry so as to be consistent with the routing table when the routing table has been updated.

22. A packet switching method comprising the steps of:

a) retrievably storing a plurality of routing entries in a routing table;

b) storing a copy of a routing entry indicating a packet flow that has been retrieved from the routing table to retrievably store a plurality of retrieved packet flows in a flow table;

c) storing a list of retrieved packet flows which are linked from a leading one to a bottom one in an address pointer table; and

d) accessing a desired retrieved packet flow in the flow table by referring to the list stored in the address pointer table.

23. The packet switching method according to claim 22, wherein the step (d) comprises the steps of:

when a packet flow corresponding to a received packet fails to be found in the search table, searching the routing table for the packet flow;

registering the found packet flow as a routing result into the search table;

determining whether the found packet flow is a micro flow belonging to an aggregated flow;

when the found packet flow is the micro flow, searching the search table for a bottom retrieved packet flow of the list corresponding to the aggregated flow;

adding the found packet flow to the bottom retrieved packet flow stored in the search table; and

when the found packet flow is not the micro flow, storing an address of the found packet flow in the search table into a corresponding routing entry in the routing table.

24. The packet switching method according to claim 22, wherein the step (d) comprises the steps of:

when an aggregated routing entry has been designated to be deleted, deleting each of the retrieved packet flows included in a list related to the aggregated routing entry from the address pointer table until finding a bottom retrieved packet flow of the list;

releasing a chain of the retrieved packet flows formed in the address pointer table to make them available;

deleting a retrieved packet flow corresponding to the aggregated routing entry from the flow table; and

deleting the aggregated routing entry from the routing table.