Memory for information search through prefix analysis, in particular for building routing tables for nodes of high speed communication networks, such as the internet network

Abstract

A memory for searching information through prefix analysis, in particular for building routing tables for nodes of high speed communication networks, such as Internet network, has a memory element which stores a set of information items each associated with a mask information indicative of the number of significant characters in the respective prefix and with a target information. For the implementation of a search criterion based on the longest prefix match, each cell comprises an information field that provides either an address of a next row for the continuation of a search or an information relating to a target reached, and a pair of flags (GO, TARGET) specifying the contents of the information field. An auxiliary vector (AUX), which has as many cells as there are memory rows is arranged to store, when the flags in a cell in the memory element indicate the reaching of a target together with the need of prosecuting search operations in a next row, the target information in its cell associated to said next row.