Multiplex communications – Pathfinding or routing
Reexamination Certificate
1999-03-11
2003-05-27
Cangialosi, Salvatore (Department: 2664)
Multiplex communications
Pathfinding or routing
C370S392000
Reexamination Certificate
active
06570866
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a router, and relates, more particularly, to a longest match retrieval device and method suitable for application to a packet switching device such as an IP (Internet Protocol) router.
2. Description of Related Art
A packet switching device called an IP router (hereinafter to be simply referred to as a “router” in the description of the prior art) determines next hop information from the ultimate destination address of an input packet, and then forwards the packet to the determined next hop node. The next hop node is determined by searching for matching entry with longest prefix (longest match routing information) using the destination address of the input packet as a key.
As a method for retrieving the longest match routing information, there has been know a method using a Radix Tree as shown in
FIG. 1
(UNIX MAGAZINE 1997.4, pp 20-25). Another method using a reduced radix tree has been described in “A Tree-Based Packet Routing Table for Berkeley Unix” by Keith Sklower (USENIX - Winter '91 - Dallas, Tex.). According to the conventional methods, the radix tree is used to make a decision as to where the packet will be sent next. More specifically, the radix tree is used to find the most specific entry matching the destination address of the input packet, that is, the best next-hop entry among possible entries matching the destination address. In other words, the longest match routing information is an entry corresponding to a mask having the longest non-masking bit length, which is used to identify the next hop node.
According to the above-described methods, however, the longest match routing information is retrieved by software-based system where a retrieval program runs on a processor, and therefore, it takes a long time for the retrieval processing. In other words, when this router is modeled as a queue, an average service time becomes very long, resulting in a long response time. Therefore, in the conventional router, there has been a problem that a delay occurs in packet forwarding, particularly in the router with heavy traffic.
To solve this problem, it is theoretically possible to structure a logic circuit by hardware for carrying out the same processing as carried out by software, to retrieve the longest match routing information at high speed.
However, for structuring the routing information retrieval system by hardware, it is necessary to change connections each time a new entry is added. Therefore, the expansion of entry data is very difficult, and it has been unrealistic to achieve this from cost viewpoint.
SUMMARY OF THE INVENTION
The present invention has been made to solve the above-described problems, and it is an object of the present invention to provide a longest match retrieval device and method which can retrieve longest match routing information at high speed and which easily allows the expansion of entry data.
It is another object of the present invention to provide a router, which can determine the most specific next hop node at high speed.
According to the present invention, the plurality of entries are divided into a plurality of primary retrieving circuits each retrieving a primary match mask and a primary match entry depending on a given address and the primary match masks and entries obtained by the primary retrieving circuits are used to determine the longest match routing information.
According to a first aspect of the present invention, a longest match retrieving device includes a plurality of primary retrieving circuits each comprising a memory storing at least one entry with a mask associated therewith so that the primary retrieving circuits store the plurality of entries. Each of the primary retrieving circuits retrieves a primary match entry which is a longest match to the given address to produce a primary match mask associated with the primary match entry. Further, a logic circuit is provided which selects a longest match mask from primary match masks obtained by the primary retrieving circuits. The longest match mask has a longest non-masking bit length among the primary match masks. At least one associative memory is provided which stores a plurality of second entries each formed by coupling an entry with a corresponding mask together, wherein the associative memory accesses a second entry associated with a combination of the given address and the longest match mask to output data corresponding to an entry included in the second entry accessed as the longest match.
When it is desired to add an entry to be used for routing, this can be achieved by such an arrangement that a new primary retrieving circuit is added, and a second entry corresponding to the new entry is added to the associative memory. If the capacity of the associative memory is full, the new entry data can be added by adding a new associative memory to the existing associative memories.
Further, since the primary retrieving operation and the associative memory-operation are performed in pipelines, it is possible to carry out the retrieval of the longest match routing information at high speed, and the entry data can be expanded easily.
According to a second aspect of the present invention, the device may include a plurality of associative memories provided corresponding to the primary retrieving circuits, respectively, each of the associative memories storing said at least one entry stored in a corresponding primary retrieving circuit, wherein each of the associative memories outputs an entry associated with the given address. A logic circuit is provided for selectively enabling the associative memories depending on which primary match mask has a longest non-masking bit length among primary match masks obtained by the primary retrieving circuits. And a combiner is provided to combine an entry of each enabled associative memory to produce the longest match.
According to a third aspect of the present invention, a longest match retrieving device includes a plurality of primary retrieving circuits. Each of them includes a memory storing at least one entry with a mask associated therewith so that the primary retrieving circuits store the plurality of entries, and a searcher for searching the memory for an entry which is a longest match to the given address to output a primary match mask associated with the entry and further searching the memory for a primary match entry matching to the primary match mask.
In addition, a first logic circuit is provided which selects a longest match mask from primary match masks inputted from the primary retrieving circuits, the longest match mask having a longest non-masking bit length among the primary match masks. And a second logic circuit is provided which selects a longest match entry from primary match entries inputted from the primary retrieving circuits depending on which primary match mask is the longest match mask to output the longest match entry as the longest match.
The first logic circuit may select a longest match mask from primary match masks inputted from the primary retrieving circuits to output the longest match mask as the input mask to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associated with the longest match mask, the longest match mask having a longest non-masking bit length among the primary match masks. And the second logic circuit may select a longest match entry from primary match entries inputted from the primary retrieving circuits depending on which primary match mask is the longest match mask to output the longest match entry as the longest match.
In addition to the primary retrieving circuits, a logic circuit may be provided which, when the selection clock signal is in the first state, selects a longest match mask from primary match masks inputted from the primary retrieving circuits to output the longest match mask as the input mask to the primary retrieving circuits so that each of the primary retrieving circuits outputs the primary match entry associa
Murase Tutomu
Ogura Naoyuki
Cangialosi Salvatore
Dickstein Shapiro Morin & Oshinsky LLP.
NEC Corporation
LandOfFree
High-speed flexible longest match retrieval does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-speed flexible longest match retrieval, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed flexible longest match retrieval will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3084380