Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-11-16
2003-02-04
Ngo, Ricky (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C707S793000
Reexamination Certificate
active
06515998
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a table data retrieving apparatus retrieving a table by using a retrieval key.
2. Description of the Related Art
A router is used when a plurality of communication networks is connected to each other. The router has a table storing a reference data indicative of a communication route. The table is referred when specifying a transfer destination of an IP packet. An address is set at a destination address portion of the IP packet. The table is retrieved by using the address as a retrieval key. The reference data is specified as the retrieved result. The reference data is used as an address of specifying a transfer destination of a packet. A content of the table can be updated. If a communication protocol is TCP/IP (Transmission Control Protocol/Internet Protocol), the content of the table is updated on the basis of information collected through BGP (Border Gateway Protocol) or RIP (Routing Information Protocol) that is a routing protocol.
The router corresponds to many kinds of line interfaces (communication protocols). The router accommodates a large number of lines. The router retrieves a communication route table when the packet is transferred. The router obtains an information of the transfer destination from the communication route table. Increases of the number of line interfaces and the number of accommodation lines cause the registration number of communication route tables to be increased. The increase of the registration number of communication route tables causes a retrieval time of the communication route table to be increased. The increase of the retrieval time causes a throughput of the router to be dropped.
Technique with regard to a process of retrieving a table of a router is disclosed in Japanese Laid Open Patent Application (JP-A Heisei 6-69928), Japanese Laid Open Patent Application (JP-A Heisei 6-261078), Japanese Laid Open Patent Application (JP-A Heisei 8-223207) and Japanese Laid Open Patent Application (JP-A-Heisei 9-107377). These documents disclose a technique reducing a table targeted by retrieval. These documents disclose a technique improving a response speed of a retrieval result.
SUMMARY OF THE INVENTION
Therefore, an object of the present invention is to provide a retrieving system making a retrieval of a table effective and making a table data retrieving process in a routing process faster, and a router having the retrieving system.
In order to achieve an aspect of the present invention, a table data retrieving apparatus includes a plurality of tables in each of which a reference data is stored. Each of the plurality of tables is allocated into one or more groups of a plurality of groups. A management table stores a priority of the each table. A data retrieving section selects one of the plurality of groups based on a retrieving key by which the reference data is selected. A data retrieving section retrieves the allocated table with the highest priority from the selected group.
In the above, a table data retrieving apparatus further includes a counter counting a retrieving hit-value when the data retrieving section retrieves the table. The data retrieving section changing the priority of the each table based on the retrieving hit-value.
In order to achieve another aspect of the present invention, a router includes a communication interface connected with a plurality of communication lines for transmitting communication data. The router further includes a plurality of tables storing transmission addresses of the communication data, each table of the plurality of tables is allocated into any group of a plurality of groups. The router further includes a management table storing a priority data of the each table. An address retrieving section selecting a group based on the retrieving key for selecting the reference data as a selected group. An address retrieving section retrieving the table with the priority from a selected group.
Also, the selected group corresponds with one of the plurality of communication lines.
In order to achieve an aspect of the invention, the router further includes a packet receiver receiving packets as the communication data each of which has a group discrimination flag for discriminating the any group and a destination address for transmitting any packet of the packets. The router includes a routing controller discriminating a receiver of the destination address from the received packet.
In the above, the address retrieving section selecting the any group based on the group destination flag of the any packet and retrieving the selected retrieved table based on the destination address of the any packet.
In the above, the routing controller replaces the destination address by the transmission address which is read from the retrieved table. The communication interface includes a terminator for terminating the communication data. The communication interface includes a flag setting section setting the group destination flag into the communication data for transmission.
In the above, the routing controller includes a counter for counting a hit-value of the retrieved table. The routing controller changes the priority of the retrieved table based on the hit-value.
In the above, the communication data is a packet having a plurality of cells.
In order to achieve an aspect of the invention, a method of retrieving table data includes allocating a plurality of tables into any group of a plurality of groups, each table having a reference data. The router providing a management table having a priority of each of the plurality of tables. The router retrieving a retrieved group from the plurality of groups based on a retrieving key for retrieving the reference data of a target table of one of the plurality of tables.
In the above, the router retrieving the target table with the priority from the retrieved group based on the retrieving key. The router further comprises counting the hit-value of the retrieved table. The router changing the priority of the retrieved table based on the hit-value.
In the above, the router further includes receiving communication data which has a group discrimination flag for discriminating the any group. The router includes destination address for transmitting the communication data.
In the above, the router further includes discriminating the retrieving group based on the group discrimination flag.
In the above, the router further includes providing transmission addresses of the communication data into the plurality of tables. The router discriminating a transmission address from the transmission address based on the retrieving key as a discriminated transmission address. The router replacing the destination address of the communication data by the discriminated transmission address.
A router according to the present invention has a plurality of grouped tables. A priority of the table within the group is indicated by a retrieval order management table. The grouping of the tables is carried out in accordance with a line, a line group, a logical line (for example, VPI/VCI (Virtual Path Identifier/Virtual Channel Identifier) of ATM and a data link connection identifier DLCI of a frame relay) and a logical line group.
A process of retrieving a transfer destination of a traffic is made faster if a priority is set in accordance with a reference frequency (hit rate).
When tables are grouped, one table is allocated into one group. This allocation enables an access of a special table (virtual private network) through general information (group information).
REFERENCES:
patent: 5644571 (1997-07-01), Seaman
patent: 5701300 (1997-12-01), Jeon
patent: 5732078 (1998-03-01), Arango
patent: 5917821 (1999-06-01), Gobuyan
patent: 5938736 (1999-08-01), Muller
patent: 5951649 (1999-09-01), Dobbins
patent: 6069895 (2000-05-01), Ayandeh
patent: 6084877 (2000-07-01), Egbert
patent: 6130891 (2000-11-01), Lam
patent: 6145045 (2000-11-01), Falik
patent: 6370147 (2002-04-01), Beser
patent: 63-29881 (1988-02-01), None
patent: 2-148174 (1990-06-01),
Amagai Tatsuhiko
Aramizu Tatsuo
Yamashita Mikiharu
Emdadi Kamran
Ngo Ricky
LandOfFree
Table data retrieving apparatus retrieving table in which... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Table data retrieving apparatus retrieving table in which..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Table data retrieving apparatus retrieving table in which... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3173822