JP3662618B2 - Multi-protocol address search associative memory and its search method - Google Patents

Description

[0001]
[Industrial application fields]
The present invention relates to an associative memory for multi-protocol address search and a search method thereof, and more specifically, a plurality of different protocol addresses (multi-protocol addresses) can be searched according to each protocol in one associative memory, The present invention relates to an associative memory for multiprotocol address search capable of performing network path control at high speed and low cost, and a search method thereof.
[0002]
[Prior art]
The associative memory (CAM) is also called a content addressed memory, and includes a storage unit that stores data like a normal semiconductor memory, and a search unit that searches for data stored in the storage unit. Data to be searched is stored in advance in the storage unit, and in the search unit, the data stored in the storage unit and the data to be searched are searched for coincidence, the presence or absence of matching data, the stored address, etc. Searched and output in a single cycle. By using an associative memory, target data can be obtained instantaneously from a huge amount of data, so that it is used for improving the performance of a system that frequently performs search processing.
[0003]
Here, an application example of the above-mentioned associative memory will be described using network path control as an example. First, an outline of the network will be described.
[0004]
Data communication is performed between computers connected to a network using a specific data communication protocol (hereinafter simply referred to as a protocol). There are many types of such protocols as IP (Internet Protocol), IPX (Internetwork Packet Exchange, used in Novell Netware), DECNet, AppleTalk, etc., and their bit length, data storage order, storage location These are generally different for each protocol. Routers are also used to interconnect different networks, and some routers can route multiple protocols. This is called a multi-protocol router.
[0005]
Each protocol assigns a protocol address (address of the protocol: hereinafter simply referred to as an address) as an identifier to all computers existing on the network. Thereby, each computer is uniquely identified. However, a multi-protocol router cannot uniquely identify a computer by an address alone. This is because if a protocol and another different protocol assign the same address to different computers, the problem arises that the computer cannot be uniquely identified only by the addresses assigned by the respective protocols. is there. For example, when transferring data from the computer 3 to the computer 1 in FIG. 9, the router cannot identify whether the data should be sent to the computer 1 or the computer 2 only from the destination address 1234.
[0006]
In order to solve this problem, an ordinary LAN (Local Area Network) frame includes an identifier for identifying an upper protocol. The router determines the destination by combining the protocol identifier and the address. As such a LAN frame, an Ethernet frame will be described as an example.
[0007]
FIG. 6 is a conceptual diagram of an Ethernet frame that is one of LANs. Although this frame is conceptual and different from the actual one, the destination and source addresses DA and SA of the Ethernet frame, the protocol type TYP of the existing protocol, the datagram of the existing protocol, And communication error detection data CRC. In addition, the datagram of the existing protocol is assumed to be composed of communication source and destination addresses sa and da of the datagram of the existing protocol and data to be communicated.
[0008]
Next, communication via a router will be described. 7A is a conceptual diagram of network connection using a router, FIG. 7B is a conceptual diagram of an Ethernet frame input from the computer A to the router R, and FIG. 2 is a conceptual diagram of an Ethernet frame output to a computer B. FIG. The following description will be continued assuming that the MAC (Media Access Control) addresses (Ethernet addresses) of computers A and B and the addresses of existing protocols are GA, GB, LA, and LB, respectively, and the MAC address of router R is GR. .
[0009]
As shown in FIG. 7A, an Ethernet frame of various protocols is input to the router R that transfers data, and the router R determines a transfer destination according to each protocol. Each frame is output to each communication destination. For example, when data is transmitted from the computer A to the computer B, a frame of the protocol used by the computer A is input to the router R, and the transfer destination is determined in the router R according to the protocol used by the computer A. As a result, the router A frame is output from R to the computer B.
[0010]
As shown in FIG. 7B, the Ethernet frame transferred from the computer A to the router R includes the addresses GR and GA of the transfer destination and source of the frame, the protocol type TYP of the existing protocol, and the existing Protocol datagrams are included. Further, the datagram of the existing protocol includes the addresses LA and LB of the communication source and communication destination and the data data to be communicated. This Ethernet frame means that an existing protocol frame of the protocol type TYP is transferred from the Ethernet transfer source address GA to the transfer destination address GR, that is, from the computer A to the router R.
[0011]
When this Ethernet frame is input to the router R, the router R determines the transfer destination from the protocol types TYP and LB. That is, the router searches the address LB of the computer B in its own table, knows the MAC address of the computer B and which network it is connected to, and connects to the network to which the computer B is connected as shown in FIG. The Ethernet frame indicated by That is, GR is converted to GB, and GA is converted to GR.
[0012]
As shown in FIG. 7C, the Ethernet frame transferred from the router R to the computer B includes the transfer destination and transfer source addresses GB and GR of the frame, the protocol type TYP of the existing protocol, and the existing Contains protocol datagrams. Further, the datagram of the existing protocol includes the addresses LA and LB of the communication source and communication destination and the data data to be communicated. This Ethernet frame means that an existing protocol frame of the protocol type TYP is transferred from the Ethernet transfer source address GR to the transfer destination address GB, that is, from the router R to the computer B.
[0013]
As described above, when the destination is correctly determined by the router R, even when frames of a plurality of different protocols are mixed on a plurality of networks, each computer is uniquely identified and interconnected. Thus, data communication can be performed. The multi-protocol router prepares a separate address search table for each protocol. When a CAM is used for a table, a CAM chip is assigned for each protocol.
[0014]
Finally, an application example of the associative memory for address search performed when the router determines the transmission destination will be described. In the address search by the router R described above, the associative memory is used to obtain the address GB of the Ethernet frame transfer destination from the address LB of the communication destination of the existing protocol.
[0015]
FIG. 8 is a schematic diagram of an example of application of an associative memory to a conventional network address search. In the figure, each associative memory has a one-to-one correspondence with all the protocols used in this network, and the address of the corresponding protocol is stored in advance in each associative memory for all computers connected to the network. Remembered. When an Ethernet frame corresponding to each protocol is input to the router R, the associative memory corresponding to the protocol type TYP is selected by the router R, and the address LB of the communication destination of the existing protocol is used in this associative memory. And the address GB of the Ethernet communication destination can be obtained at high speed.
[0016]
In the application example to the address search of the associative memory described above, the destination address can be searched at high speed. However, conventional associative memories cannot search for datagrams of a plurality of different protocols, in particular, address data having different bit lengths, storage orders, etc. using one associative memory, so different associative memories are used for each protocol. I had to. For this reason, there is a problem that the number of associative memories to be used increases and the cost increases. On the other hand, in order to reduce the cost, if a search is performed by software without using an associative memory, there is a problem that the search by software takes too much time.
[0017]
[Problems to be solved by the invention]
An object of the present invention is to look back on various problems based on the prior art, detect an entry storing a predetermined protocol identifier, and select a sequencer based on the predetermined protocol identifier. By detecting an entry in which a predetermined protocol address is further stored from the entries detected by the identifier, a plurality of different protocol addresses can be searched in one associative memory table, and network routing control can be performed. An object is to provide an associative memory for multi-protocol address search and a search method thereof capable of simultaneously realizing high speed and low cost.
[0018]
[Means for Solving the Problems]
In order to achieve the above object, the present invention comprises an associative memory table having a plurality of entries made up of a plurality of segments each having a predetermined bit length, and a sequencer selection means for controlling a matching search procedure for each protocol,
At least a protocol identifier and a protocol address are stored in the entry, and an entry that matches a predetermined protocol identifier is detected, and a sequencer corresponding to the predetermined protocol identifier is selected by the selection means, and the entry in the detected entry The present invention provides an associative memory for multiprotocol address search, wherein a logical product match search of the protocol address in the segment unit is performed by a selected sequencer.
[0019]
Furthermore, the sequencer is preferably provided for each protocol.
[0020]
In addition, the present invention previously stores a protocol identifier and a protocol address corresponding to each protocol in different segments of each entry,
Performing a match search of the segment in which the protocol identifier is stored, detecting the entry in which the predetermined protocol identifier is stored, and obtaining a sequencer identifier based on the predetermined protocol identifier;
Next, a sequencer corresponding to the predetermined protocol identifier is selected by the sequencer identifier,
After that, according to the control of the selected sequencer, a search is performed for a segment in which the protocol address of the entry detected by the predetermined protocol identifier is stored, and the entry in which the predetermined protocol address is stored is detected. The present invention provides a multi-protocol address search method characterized by:
[0021]
Here, after previously storing the sequencer identifier corresponding to the protocol identifier in a part of the segment,
It is preferable to obtain a sequencer identifier stored in a part of the segment of the entry detected by the predetermined protocol identifier.
[0022]
The sequencer identifier is preferably obtained by decoding the predetermined protocol identifier.
[0023]
[Effects of the Invention]
The associative memory for multi-protocol address search according to the present invention comprises sequencer selection means and sequencers corresponding to the respective protocols. As already described, since each protocol address has a different bit length, storage position, etc., it is not possible to search, for example, an IP address and an IPX address by the same search procedure. Therefore, in the present invention, by providing a lookup table such as a ROM, a RAM, a register, or a sequencer selection means such as a decode circuit, a sequencer is selected according to each protocol, and the corresponding sequence according to each protocol. The protocol address can be retrieved. Therefore, according to the associative memory for multi-protocol address search of the present invention, it is possible to store addresses of a plurality of different protocols in one associative memory table and detect an entry having a predetermined address of a predetermined protocol from among them. it can.
[0024]
In the multi-protocol address search method of the present invention, a protocol identifier and a protocol address are stored in different segments of each entry. First, a segment in which the protocol identifier is stored is searched, and a predetermined protocol identifier is determined. Detects a stored entry, obtains a sequencer identifier from the predetermined protocol identifier, selects a sequencer corresponding to the protocol by the sequencer identifier, and subsequently detects an entry detected by the predetermined protocol identifier according to the sequencer The segment in which the protocol address is stored is searched to detect the entry in which the predetermined protocol address is stored. Therefore, according to the multi-protocol address search method of the present invention, it is possible to recognize which protocol address each protocol address is based on the protocol identifier. Therefore, a plurality of different protocol addresses are stored in one associative memory. These can be retrieved by protocol identifier and protocol address. This makes it possible to perform network path control at high speed and to construct a system at a low cost.
[0025]
【Example】
Hereinafter, a multi-protocol address search associative memory and a search method thereof according to the present invention will be described in detail with reference to the preferred embodiments shown in the accompanying drawings.
[0026]
FIG. 1 is a block diagram of an embodiment of an associative memory for multiprotocol address retrieval according to the present invention. As shown in this block diagram, the multi-protocol address search associative memory 10 of the present invention stores entry data corresponding to each protocol, and an associative memory table 12 for performing a match search between the entry data and the search data. The sequencer (group) 14 is provided for each protocol and controls the entry data search procedure. The sequencer selection means 16 selects the sequencer 14 according to the protocol.
[0027]
FIG. 2 is a conceptual diagram of an embodiment of the associative memory table described above. This associative memory table 12 is composed of entries 0, 1,..., M, and data such as IP entry, IPX entry, DECNet entry, and AppleTalk entry is stored in each entry 0 to m in an arbitrary order. Is done. Each entry 0 to m is divided into segments 0, 1,..., N which are basic units of search. Each segment 0 to n may have the same bit length or a different bit length, and the bit length is not particularly limited.
[0028]
Next, FIG. 3 is a conceptual diagram of an embodiment of an entry in the associative memory table shown in FIG. The segment 0 of the entry stores a protocol ID (identifier) and a sequencer ID, and the segments 1 to n store a protocol address corresponding to the protocol ID. The bit length of each segment 0 to n is about 32 to 64 bits. For example, when the bit length of the segments 1 to n is 32 bits, the protocol address stored in the segments 1 to n is stored only in the segment 1 because the IP address is 32 bits in the case of an IP entry. Similarly, in the case of an IPX entry, since the IPX address is 80 bits, it is stored up to 16 bits of segment 1, 2 and segment 3. Thus, the number of segments is appropriately selected according to the bit length of the segment and the bit length of the protocol address.
[0029]
FIG. 4 shows a specific example of the protocol ID and sequencer ID stored in segment 0. In the same figure, for easy explanation, the data corresponding to which protocol is shown as a comment such as IP or IPX. The protocol ID is based on the Ethernet standard. The sequencer ID is a number for selecting a sequencer corresponding to the protocol ID, and is a number corresponding to each protocol on a one-to-one basis. For example, in the case of IP, the protocol ID is 0800 (hexadecimal), and the sequencer ID for this is number 1. In the example shown in this figure, segment 0 is configured with a 19-bit size of a 16-bit protocol ID and a 3-bit sequencer ID.
[0030]
Next, in the associative memory of the present invention configured as described above using the schematic diagram of the associative memory table shown in FIG. 5 and storing entry data corresponding to a plurality of different protocols, addresses of predetermined protocols are stored. A method for searching for the entry is described. 5 is composed of entries 0, 1,..., 4 and each entry 0, 1,..., 4 is divided into segments 0, 1,.
[0031]
First, in the first search, in the segment 0 of all entries 0 to 4 in this associative memory table, a match search is performed while masking the sequencer ID, and an entry storing a predetermined protocol ID is detected. For example, as in the example shown in FIG. 4, when 0800 (hexadecimal number) is given as search data, only an entry in which 0800 (hexadecimal number) is stored in the protocol ID of segment 0 is detected. As a result, here, it is assumed that a match is detected in entries 0, 2 and 3, and a mismatch is detected in entries 1 and 4.
[0032]
Thereafter, the sequencer ID stored in the segment 0 of the entry 0, 2 or 3 that is detected to be matched by the predetermined protocol ID is read. For example, in the example shown in FIG. 4, the entry whose protocol ID is 0800 (hexadecimal number) The stored sequencer ID, that is, number 1 is read out, and the sequencer is selected according to this sequencer ID. When the sequencer is selected, the protocol address search procedure in the segments 1 to 4 of the entries 0, 2 and 3 that have been detected by the predetermined protocol ID is controlled by the selected sequencer.
[0033]
Here, the sequencer described above will be described. As already described, the protocol addresses stored in the segments 1 to n of the respective entries have different bit lengths, storage orders, etc., if the protocols are different. Therefore, it is necessary to change the search procedure in the segments 1 to n according to the protocol to be searched. The sequencer controls this search procedure. In addition, the sequencer should just be prepared in the inside or the outside of the associative memory with respect to the protocol used in a network.
[0034]
Next, in the second search, a match search is performed in segment 1 of entries 0, 2 and 3 in which a match is detected with a predetermined protocol ID in segment 0 in the first search, and for the first one segment of the predetermined protocol address. The entry storing the data is detected. It should be noted that no match search is performed on segment 1 of entries 1 and 4 where a mismatch is detected. As a result of the second search, here, it is assumed that a match is detected in entries 0 and 3, and a mismatch is detected in entry 2.
[0035]
In the third search, the match detection is performed in the segment 2 of the entries 0 and 3 in which the match is detected by the data of the first one segment of the predetermined protocol address in the segment 1 in the second search. An entry in which data for the second segment is stored is detected. Note that a match search is not performed in segment 2 of entry 2 where no match was detected in segment 1. As a result of the third search, it is assumed that a match is detected in entry 3 and a mismatch is detected in entry 0. Accordingly, it is detected that the predetermined protocol ID and the predetermined protocol address are stored in the entry 3. Thus, an efficient search is performed by performing a logical product search.
[0036]
For example, in the case of an IP entry, since the IP address is 32 bits (one segment), the IP sequencer searches for the segment 1 of the entry whose match is detected by the predetermined protocol ID, and the predetermined protocol address is stored. Detect entry. Thus, in the case of an IP entry, an entry storing a predetermined protocol ID and a predetermined protocol address can be detected by performing a logical AND search on segments 0 and 1.
[0037]
On the other hand, in the case of an IPX entry, since the IPX address is 80 bits (3 segments (2 segments + 16 bits)), the IPX sequencer first searches for the segment 1 of the entry whose match is detected by a predetermined protocol ID, An entry in which data for the first one segment of a predetermined protocol address is stored is detected, and then, in segment 1, a search for segment 2 of an entry that has been detected as being matched by the data for the first segment of the predetermined protocol address To detect an entry in which the data for the second segment of the predetermined protocol address is stored, and also in the segment 2, the entry whose match is detected by the data for the second segment of the predetermined protocol address 16 bits in the second half of segment 3 The masked to search, to detect the entry third 16 bits of data for one segment of a predetermined protocol address is stored. Thus, in the case of an IPX entry, an entry storing a predetermined protocol ID and a predetermined protocol address can be detected by performing a logical product search on the segments 0 to 3.
[0038]
The multi-protocol address associative memory and the search method thereof according to the present invention are basically configured as described above. Although the multi-protocol address associative memory and the search method thereof according to the present invention have been described based on the embodiments, the present invention is not limited to this.
[0039]
For example, in the above-described embodiment, the protocol ID and the sequencer ID are stored in the segment 0 of each entry, but are not limited to the segment 0, and may be stored in any segment. That is, in the first search, a segment in which the protocol ID is stored may be searched.
Further, as a sequencer selection means of the present invention, the sequencer ID is stored in the segment 0, and the sequencer ID corresponding to this is obtained from the predetermined protocol ID, and the sequencer ID is obtained by a so-called lookup method. However, the sequencer ID may be acquired, for example, by decoding a predetermined protocol ID. In this case, the sequencer identifier portion of the entry of FIG. 3 is not necessary. Similarly, the sequencer ID may be stored in another memory device, for example, a register, RAM, ROM, or the like instead of the associative memory table. These memory devices, the above-described decoding circuit, etc. It may be provided inside or outside the associative memory.
Further, at least a protocol ID or a sequencer ID and a protocol address are stored in each entry. For example, data other than these data may be stored.
[0040]
【The invention's effect】
As described in detail above, the multi-protocol address search associative memory of the present invention has sequencer selection means for controlling the protocol address search procedure in accordance with each protocol. In the multi-protocol address search method of the present invention, the protocol ID and the protocol address are stored in different segments in the respective entries in the associative memory table in advance, and then the segment storing the protocol ID is searched first. , An entry in which a predetermined protocol ID is stored is detected, and a sequencer is selected based on the predetermined protocol ID. Subsequently, the protocol address of the entry detected by the predetermined protocol ID is stored by the selected sequencer. The segment in which the predetermined protocol address is stored is detected by searching the segment. That is, according to the associative memory for searching multi-protocol addresses and the search method of the present invention, a plurality of different protocol addresses can be searched with one associative memory. Cost reduction can be realized at the same time.
[Brief description of the drawings]
FIG. 1 is a block diagram of an embodiment of an associative memory for multiprotocol address retrieval according to the present invention.
FIG. 2 is a conceptual diagram of an embodiment of an associative memory table in the associative memory for multiprotocol address search according to the present invention.
FIG. 3 is a conceptual diagram of an example of an entry in an associative memory table in the associative memory for multiprotocol address search according to the present invention.
FIG. 4 is a conceptual diagram of an example of segment 0 of an entry in an associative memory table in the associative memory for multiprotocol address search according to the present invention.
FIG. 5 is a conceptual diagram illustrating an example of a multi-protocol address search method according to the present invention.
FIG. 6 is a conceptual diagram of an Ethernet frame.
7A is a conceptual diagram of network connection using a router, FIG. 7B is a conceptual diagram of an Ethernet frame input from the computer A to the router R, and FIG. 7C is output from the router R to the computer B. FIG. 3 is a conceptual diagram of an Ethernet frame.
FIG. 8 is a schematic diagram of an example of application of an associative memory to a conventional network address search.
FIG. 9 is a conceptual diagram of network connection using a conventional router.
[Explanation of symbols]
1,2,3 computer
10 Associative memory (CAM)
12 Associative memory table
14 Sequencer
16 Sequencer selection means

Claims (5)

An associative memory table having a plurality of entries made up of a plurality of segments each having a predetermined bit length, and a sequencer selection means for controlling a matching search procedure for each protocol,
At least a protocol identifier and a protocol address are stored in the entry, and an entry that matches a predetermined protocol identifier is detected, and a sequencer corresponding to the predetermined protocol identifier is selected by the selection means, and the entry in the detected entry A multi-protocol address search associative memory, wherein a logical product match search of the protocol address in the segment unit is performed by a selected sequencer. The multi-protocol address search associative memory according to claim 1, further comprising a sequencer for each protocol. After storing the protocol identifier and protocol address corresponding to each protocol beforehand in different segments of each entry,
Performing a match search of the segment in which the protocol identifier is stored, detecting the entry in which the predetermined protocol identifier is stored, and obtaining a sequencer identifier based on the predetermined protocol identifier;
Next, a sequencer corresponding to the predetermined protocol identifier is selected by the sequencer identifier,
After that, according to the control of the selected sequencer, a search is performed for a segment in which the protocol address of the entry detected by the predetermined protocol identifier is stored, and the entry in which the predetermined protocol address is stored is detected. A method for searching for a multi-protocol address. After previously storing the sequencer identifier corresponding to the protocol identifier in a part of the segment,
4. The multi-protocol address search method according to claim 3, wherein a sequencer identifier stored in a part of the segment of an entry detected by matching with the predetermined protocol identifier is acquired. The multi-protocol address search method according to claim 3, wherein the sequencer identifier is obtained by decoding the predetermined protocol identifier.

Images