Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-02-09
2004-07-27
Vu, Huy D. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000, C370S395310, C370S395320, C370S395100, C711S118000, C711S216000, C711S221000
Reexamination Certificate
active
06768739
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a routing technique for use in a router with a cache, and more particularly to a router with a cache which is capable of raising a cache hit probability and reducing the capacity of the cache.
2. Description of the Related Art
A router for connecting plural terminals to plural networks needs to perform transfer or forwarding of a block (packet) of communication information in order to achieve communications over different networks. In each router, a packet inputted from a connected network is received by an interface and a forwarding table possessed by the router is searched according to a final destination address contained in the received packet to determine a number of a transmission interface from which the packet should be sent to a next-hop router or the destination. In such a way, the packet forwarding is performed.
A conventional routing method for rapidly determining a transmission interface by using a cache table provided in the router (hereinafter referred to as “router with a cache”) will be described.
A router having a conventional cache, as disclosed in Japanese Patent Application Laid-Open No. 6-261078, has a forwarding table, a forwarding table retrieval system for retrieving the forwarding table, and a cache table for exact matching retrieval. First, a structure and a retrieval method of each table will be described.
As shown in
FIG. 1
, the forwarding table has a pair of a destination field and a transmission interface number field. The destination field specifies a string of consecutive bits in the direction from the uppermost bit thereof toward a lower-order bit, which indicates a network address. The length of the bit string in called a prefix length and the bit string is called a prefix. To represent such a prefix, the destination field consists of two pieces of information: Prefix bit string and Prefix length.
The prefix bit string is a bit string having the same bit length as address and stores a bit string which is required to be specified continuously from the uppermost bit. Although bits not specified may store any bit, it is assumed hereinafter that bit “0” is stored.
The prefix length is the number of bits required to be specified as the prefix from the uppermost bit of the prefix bit string.
For example, in the case where the network address is 32-bit address, when a prefix of 10000000 01000000 (separated every 8 bits by a space) is required to be specified from the uppermost bit, the prefix bit string is 10000000 01000000 00000000 00000000 (separated every 8 bits by a space) and the prefix length is 16. In a following description, a 32-bit string is frequently separated every 8 bits into four blocks such that each block is expressed by a decimal number and the four blocks are indicated by separating with dots (dotted decimal notation). Further, in the cage of 32-bit network address, sometimes the destination field (prefix) is expressed by decimal notation with dots indicating a prefix bit string followed by the prefix length separated with “/”. For example, the prefix of the above 32 bits is expressed as 129.64.0.0/16.
Further, the prefix length may be expressed in mask bit string. According to this method, the mask bit string is a bit string consisting of consecutive bits of 1 for the prefix length in the direction from the uppermost bit toward a lower-order bit of the network address and the remaining part consisting of consecutive bits of 0. In the above example, the mask bit string is 11111111 11111111 00000000 00000000 (separated every 8 bits by a space). A transmission interface number to which a packet should be transferred is written in the transmission interface number field of the forwarding table. As to a retrieval method of the forwarding table, a method called longest prefix match retrieval (hereinafter referred to as LPM) is employed. In this retrieval, for all entries, the destination address of a packet is compared with a prefix registered in the destination field of the forwarding table. In this comparison, it is determined whether the following bit strings (
1
) and (
2
) match with each other.
The bit string (
1
) is a bit string of consecutive bits corresponding to the prefix length of an entry, extracted from the destination address of a pocket in the direction from the uppermost bit toward a lower-order bit.
The bit string (
2
) is a bit string of consecutive bits corresponding to the prefix length of an entry, extracted from the prefix bit length of the entry in the direction from the uppermost bit toward a lower-order bit.
Although there is a possibility that plural entries in which the bit strings (
1
) and (
2
) match with each other may exist in the forwarding table, an entry having the longest prefix length of them is an entry which is a result of the LPM retrieval.
The cache table has a destination address field and a transmission interface number field. Network addresses are written in the destination address field. In the transmission interface number field, transmission interface numbers are written and a packet whose destination address is the network address written in a corresponding destination address field is forwarded to that interface number. Upon retrieval, a destination address is given as a retrieval key and the cache is searched for an entry whose destination address field completely matches with the retrieval key.
In a router having a conventional cache, a process for determining a transmission interface number is carried out in the following manner. When a packet arrives at the router, the destination address of the packet is picked out. Then, with the destination address as a retrieval key, exact matching retrieval is carried out about the cache table. When a match is found, the interface number to which that packet should be transferred is obtained from the transmission interface number field of that entry. When no match is found, the forwarding table retrieval system carries out the LPM retrieval described above based on the destination field of the packet so as to obtain the transmission interface number.
When the forwarding table is retrieved, the destination address of the packet and the transmission interface number obtained from the table retrieval are stored in the cache in pair. In the aforementioned router having the conventional cache, a previously retrieved destination address of a packet and a result of the LPM retrieval are stored in a cache which can provide retrieval at higher speeds than the forwarding table retrieval. In the case where a packet having the same destination address arrives, a transmission interface number can be obtained by only cache retrieval. As a result, by omitting the forwarding table retrieval which takes longer than the cache retrieval, the interface-number determining processing, that is, path determining processing, is accelerated.
In the conventional cache as described above, however, the destination address of a packet is stored in the cache and the exact matching retrieval is carried out. Thus, the destination address which matches with the cache entry is only one. Therefore, the cache hit probability is low. When no hit is found in the cache, the forwarding table needs to be retrieved. Thus, it takes long until the transmission interface is determined and there is a problem that the packet transmission performance of the router is reduced. Further, when transmission is carried out to N destination addresses through a router, N cache entries are needed in order that a hit for each of these packets can be found in the cache. In other words, the number of cache entries must be identical to that of destination addresses. Thus, when the number of transmission terminals is large, it is necessary to mount a large capacity cache proportional thereto, and consequently, a circuit area of the router increases, thereby leading to an increase of production cost.
SUMMARY OF THE INVENTION
Accordingly, an object of the present invention is to provide a router having a cache therein,
Kobayashi Masayoshi
Murase Tutomu
Shimonishi Hideyuki
NEC Corporation
Volper Thomas E.
Vu Huy D.
Whitham Curtis & Christofferson, P.C.
LandOfFree
Router with a cache having a high hit probability does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Router with a cache having a high hit probability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Router with a cache having a high hit probability will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3221039