INFORMATION RETRIEVAL MEMORY BY PREFIX ANALYSIS FOR BUILDING-UP ROUTING TABLE OF NODE FOR HIGH SPEED COMMUNICATION NETWORK SUCH AS INTERNET

摘要

PROBLEM TO BE SOLVED: To provide a memory structure that ensures incremental update of a routing table and optimum utilizing of a physical memory. ;SOLUTION: A memory to retrieve information by a prefix analysis in order to build up a routing table for a node of a high speed communication network such as the Internet especially includes a memory element M1 that stores one set of information items and each of the information items relates to mask information and target information denoting a number of important characters in respective prefixes. In order to realize a retrieval reference based on coincidence of a longest prefix, each cell includes an information field to provide an address of a succeeding line for consecutive retrieval or an arrived target and a couple of flags specifying contents of the information field. An auxiliary vector AUX includes cells of the same number as memory lines and when a flag in a cell of the memory element indicates necessity for retrieval of a succeeding line and read of the target, the target information is stored in a cell relating to the succeeding line.;COPYRIGHT: (C)2000,JPO