System and method for processing packets
First Claim
Patent Images
1. A data searching system comprising:
- a routing table for storing a plurality of next-hop addresses;
a cache memory storing an IP flow table for storing at least one next-hop address which has been selected from the routing table; and
an address pointer table for storing location information indicating an entry address of each next-hop address stored in the IP flow table and relationship information among entry addresses of next-hop address stored in the IP flow table, wherein the address pointer table comprises a plurality of memory blocks each having a fixed length on a recording medium, located at consecutive addresses,each memory block comprising;
a first area for storing an entry address indicating a location of a corresponding piece of data stored in the IP flow 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.
1 Assignment
0 Petitions
Accused Products
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.
28 Citations
22 Claims
-
1. A data searching system comprising:
-
a routing table for storing a plurality of next-hop addresses; a cache memory storing an IP flow table for storing at least one next-hop address which has been selected from the routing table; and an address pointer table for storing location information indicating an entry address of each next-hop address stored in the IP flow table and relationship information among entry addresses of next-hop address stored in the IP flow table, wherein the address pointer table comprises a plurality of memory blocks each having a fixed length on a recording medium, located at consecutive addresses, each memory block comprising; a first area for storing an entry address indicating a location of a corresponding piece of data stored in the IP flow 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. - View Dependent Claims (2)
-
-
3. A packet processing system comprising:
-
a microprocessor; a routing table; a cache memory storing an IP flow table which is used to increase 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 IP flow table and relationship information among entry addresses of pieces of data stored in the IP flow table, wherein the address pointer table comprises a plurality of memory blocks each having a fixed length on a recording medium, located at consecutive addresses. each memory block comprising; a first area for storing an entry address indicating a location of a corresponding piece of data stored in the IP flow 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.
-
-
4. A packet processing system comprising:
-
a microprocessor; a routing table; a searcher having a cache memory connected thereto, wherein the cache memory stores a search table to increase 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 relationship information among entry addresses of pieces of data stored in the search table, wherein the address pointer table comprises a plurality of memory blocks each having a fixed length on a recording medium, located at consecutive addresses, 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. - View Dependent Claims (5, 6)
-
-
7. A control method for controlling a packet processing system comprising:
-
a microprocessor; a routing table; a searcher having a cache memory connected thereto, wherein the cache memory stores a search table 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 relationship information among entry addresses of pieces of data stored in the search table, the control method comprising; 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 cache memory; and b) changing the entry and related entries so as to be consistent with the routing table, wherein the address pointer table comprises a plurality of memory blocks each having a fixed length on a recording medium, located at consecutive addresses, each memory block comprising; a first area for storing an entry address indicating a location of a corresponding piece of data stored in the IP flow 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.
-
-
8. A system comprising:
-
a first memory for retrievably storing a plurality of next-hop address entries; a cache memory for storing a copy of a next-hop address entry that has been retrieved from the first memory to retrievably store a plurality of retrieved next-hop address entries; a second memory for storing a list of retrieved next-hop address entries which are linked from a leading one to a bottom one; and a data controller for accessing a desired retrieved next-hop address entry by referring to the list stored in the second memory. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A packet switching system comprising:
-
a routing table for retrievably storing a plurality of routing entries; a cache memory for storing a flow table having 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. - View Dependent Claims (15, 16, 17, 18, 19)
-
-
20. A packet switching method comprising:
-
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 cache memory; 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 cache memory by referring to the list stored in the address pointer table. - View Dependent Claims (21, 22)
-
Specification