Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-10-20
2003-05-27
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S212000, C711S218000, C707S793000, C370S391000
Reexamination Certificate
active
06571313
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a memory for information search through a prefix analysis, devoted in particular to building routing tables for high speed communication networks, preferably for the Internet network.
BACKGROUND OF THE INVENTION
Communication protocols for modern high speed networks, such as the ATM networks, the Internet network etc., are based on the transmission of information packets containing, in the header, information relating to the destination address of the packet. In a node of the network, when receiving a packet, the routing control units use the address to perform a search inside a suitable table or data base and to locate the output interface to which the packet must be supplied for further forwarding to a successive network unit. Presently, transmission rates of the order of the Gbits/s are common and therefore routing time in a node must be very short to prevent impairing regular traffic flow. To provide a quantitative indication, it must be considered that a 1 Gbit/s transmission with packets of about 1000 bits requires for the nodes to handle about 1 million packets per second. Taking into account the switching time, the time necessary for possible packet header processing and possible guard times between consecutive packets, the search in the routing table, which is the longest operation, must be performed in a time somewhat less than 1 &mgr;s. The situation becomes more critical with increasing communication speed.
Referring for simplicity of description and just as an example to the Internet network, there is an exponential growth of both the number of host computers connected to the network and the traffic, as well as of the band requirements, also due to the continuous development of new applications using the Internet network. All this results in an increase in the routing table size, which causes in turn a longer search operation. Now it is well known to the technicians that, while it is easier and easier to have high memory capacity at low cost, reduction of access time to large memories involves considerable technological problems.
In order to have an easier adaptation to the network expansion, the Internet addresses can be organized according to a hierarchical structure, in the sense that groups of addresses corresponding e.g. to the same geographical region or to the same provider share the most significant address bits (prefix). These prefixes have variable lengths and can in turn constitute the most significant part of other prefixes (prefixes of prefixes). Further details on the structure of the Internet addresses can be found for example in the documents “Das Internet-Protokoll der nachsten Generation” by H. P. Giesiger, Comtec 5, 1998, pages 20 to 26, or “IP Next Generation Overview”, by R. M. Hinden, dated May 14, 1995 and available at the Internet site http:playground.sun. com/pub/ipng/html/INET-Ipng-Paper.html.
In order to reduce the search complexity, the routing information in the network is related above all to the address of a subsequent node in the path leading to the destination of the packet being processed. That address is commonly indicated with the term “next hop”. Since the possible different next hops in a routing table may be of the order of a hundred, it is possible to extract the relevant information and store it into another data structure. Given the small dimensions, this structure can be accessed by using direct access through an index, designated in literature “TARGET”, which is identified starting from the address of the received packet. In practice, in a routing management unit, by using as a search key the packet destination address, access is gained to a forwarding table which is a subset of the complete routing table of a network and where each row contains a prefix (addressmask.pair, where the mask indicates the number of significant bits of the address, i.e. the bits constituting the prefix) and a corresponding data (the target, commonly a pointer to the output interface, together with further information). A prefix originates a match for the search key (i.e. it allows reaching a target) if the bit-by-bit AND of the key with the mask associated to the address is equal to the address itself.
The variability of the prefix lengths causes a further complication since the index search may result in retrieving several targets, since the comparison may give a positive result for several prefixes of different lengths. In these conditions the actual target is that corresponding to the longest prefix, i.e. the most specific one for the destination. This criterion is known as the “longest prefix match”.
Theoretically, the most efficient and fastest method to perform a search based on the longest prefix match is storing the information items (entries) into one or more ternary CAMs (CAM=Content Addressable Memory). In a ternary CAM, each memory bit may assume three values: 0, 1 and (“don't care”). The comparison between the bits of the comparison register and the memory bits set at a “don't care” logic value obviously is always positive. It is therefore possible to implicitly implement the masks associated to a data by simply setting at don't care level the relevant bits of the data itself. The drawback of this type of device mainly lies in the high price and poor integration capability.
In order for low cost conventional memories to be used, it is therefore necessary to utilize algorithms for searching in data bases which are both fast and compact. The speed of a search algorithm is strictly connected to the number of memory accesses, while the compactness is determined by the quantity of memory needed for storing the data structure being used. The final aim is that of minimizing as much as possible both the access number and the memory size required to store the information for the search process.
The practical implementations of the routing algorithms suitable for satisfying the criterion of the longest prefix match may be both of the software type and of the hardware type. In general, they must meet anyhow a certain number of common requirements such as:
search speed as independent as possible from the table dimensions;
small variance of algorithm performance between the worst case and the best case;
easy incremental (or localized) table updating (i.e. the insertion or cancellation of some information items should not require re-writing the entire table or substantial portions of the same);
flexibility, so as to-be easily adaptable to future technological developments and to variations in the address organization;
memory organization as regular as possible for preventing waste.
Several solutions have already been proposed for solving the problem of the Internet network routing in such a manner as to take into account the need of implementing the longest prefix match.
A first group of solutions is based on an algorithm known as “PATRICIA”, which is an algorithm for the storage, indexing and retrieval of information in large files, particularly catalogues of libraries. The principles of this algorithm are described in the article “PATRICIA—Practical Algorithm To Retrieve Information Coded In Alphanumeric”, by D. R. Morrison, Journal of the Association for Computing Machinery, Vol. 15., No. 4, October 1968, pages 155 and following, and its application in solving routing problems in the Internet network is widely documented in the relevant technical literature. The PATRICIA algorithm is substantially an algorithm operating on a prefix tree, built on the address bits, where each bit corresponds to a node. The address bits are examined one at a time. To avoid examining nodes which correspond to nonexisting branches, each bit is associated to an indication of the successive bit to be examined. Once the search is over, a check is performed on the real existence of the prefix. Since each node corresponds to one or more memory access, and considering that the memory access is much slower than the data processing, the algorithm provides a real reduction of the total time f
Filippi Enrica
Innocenti Viviana
Bataille Pierre-Michel
Dubno Herbert
Kim Matthew
Telecom Italia Lab S.P.A.
LandOfFree
Memory for information search through prefix analysis, in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory for information search through prefix analysis, in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory for information search through prefix analysis, in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3022020