Route searching circuit and communication apparatus using the same

[0002] 1. Field of the Invention

[0003] The present invention relates to a route searching circuit for determining an apparatus to which a packet should be transferred, based on a destination address which specifies a transmission destination of the packet. Also, the present invention relates to a communication apparatus such as a router which uses the route searching circuit.

[0004] 2. Description of the Related Art

[0005] A route searching circuit determines a network address which is defined based on an address such as an IP address on the internet and a mask length.

[0006] As an apparatus for relaying a packet data between networks or local area networks (LANs) connected to each other, an apparatus such as a bridge and a router is well known. In an Open Systems Interconnection (OSI) reference model which is defined by the International Organization for Standard (ISO), the bridge performs the connection in a data link layer, especially, a media access sub-layer. The router performs the connection in a network layer which is the upper layer of the data link layer.

[0007] A communication control apparatus which is called the bridge or the router needs to determine which apparatus the reception packet received through the network should be next transmitted to, based on a route table data which is previously provided for the communication control apparatus.

[0008] In this determination processing, it is generally determined based on the address stored in an address field of a reception packet data that the reception packet data should be transmitted to which apparatus.

[0009] The address used in an LAN will be described below simply.

[0010] As the address used on the LAN, there are known the address such as a MAC address in an ethernet network and an ATM address in an ATM network which is physically peculiar to the apparatus, a network number of a network to which the apparatus is connected, and a network address indicating a number of the apparatus on the network.

[0011] The data transmitted on the LAN generally contains network addresses of a transmission destination and transmission origin in the network layer. As the internet work address, for example, an IP address of 32 bits in the TCP/IP protocol is well known. In the following explanation, the IP address is used.

[0012] A router refers to a destination IP address of the received packet to determine that the router should next transmit the packet to which router or terminal. In this determining process, it is first determined which network address the destination IP address of the received packet belongs to. Then, a physical address of the transmission destination corresponding to the network address is determined. The network address is determined based on the IP address and the mask length. The mask length is the data that a predetermined number of bits of the IP address from the most significant bit are significant.

[0013] FIG. 1 shows an example of the network address. Referring to FIG. 1, because the mask length is “16”, it can be found that the upper 16 bits of the IP address of “800A0000” is valid as the network address. When the mask length is “16”, the mask address of “FFFF0000” that each of the upper 16 bits is “1” and each of the lower 16 bits is “0” is defined.

[0014] When a result of logical product of the above mask address and the destination IP address of the received packet is coincident with the IP address of “800A0000”, the destination IP address is coincident with the network address. For example, when the destination IP address is “800A40C8”, the logical product of the destination IP address of “800A40C8” and the mask data of “FFFF0000” is calculated. As a result, the address of “800A0000” is obtained. This is coincident with the IP address of “800A0000”. Thus, the destination IP address is coincident with the network address.

[0015] In a conventional example, the correspondence of the destination IP address and the network address could be simply solved under the concept of “class”. More specifically, when each of the upper bits of the IP address is “0”, the IP address belongs to a class A and the mask length is 8 bits. When the upper bit of the IP address is “10”, the IP address belongs to a class B and the mask length is 16 bits. When the IP address is “100”, the IP address belongs to a class C and the mask length is 24 bits.

[0016] At present, the concept of the class is demolished through the spread of subnets and Classless Internet Domain Routing (CIDR). Thus, the network address can not be simply determined from the destination IP address. It takes a long processing time for the determination of the network address. Also, in the network which adopts CIDR, there is a case where one or more network addresses in the route table are coincident with the destination IP address. In this case, the route data of the network address with the longest mask length must be adopted.

[0017] However, in a conventional router apparatus of the Internet, the route solution processing for determining based on the destination IP address that a packet should be transmitted to which apparatus is realized by software.

[0018] As described above, in a conventional communication control apparatus such as a bridge and a router, there is a problem that it takes a very long processing time for the solution of the route data for packet transfer in the network which has a lot of route data. Especially, in the packet transfer in the network in which there are one or more network addresses matching to an address, the algorithm to solve the network address becomes complicated. Therefore, the determination of the route data takes more time. For these reasons, the throughput of the packet transfer processing decreases in the packet transfer apparatus. This is because a specific route data corresponding to the destination address is searched from a lot of route data by the software.

[0019] In addition to the above conventional examples, a routing system is described in Japanese Laid Open Patent Application (JP-A-Heisei 2-206237). In the routing system, a connection apparatus includes an address table for a sub-tree. When a communication frame is received, the address table is referred to. When a destination address is exist in the address table, the communication frame is transferred to a link corresponding to the destination address.

[0020] Also, an address comparing system is described in Japanese Laid Open Patent Application (JP-A-Heisei 4-352534). In the address comparing system, an address common section Acom of terminal addresses Al to An set for a plurality of terminal equipments 1-1 to 1-n is stored in an address register 2. A portion of a terminal address of a reception address RA corresponding to the address common section Acom is compared with the value of the address register 2. More specifically, a control register 4 is provided to have mask bits in which presence or non-presence of address comparison is set in units of bits. The address register 2 value and the reception address RA are compared by a comparing section 3 based on the mask bits of the control register 4.

[0021] Also, a communication network system is described in Japanese Laid Open Patent Application (JP-A-Heisei 6-62029). In the communication network system, a distribution tree is generated based on tree addresses by a tree leader. A tree address correlation is generated using a network identifier and a node identifier, and a list of connected nodes is generated for every member of the multicast tree set.

[0022] Also, a LAN connecting apparatus is described in Japanese Laid Open Patent Application (JP-A-Heisei 7-254912). In the LAN connecting apparatus, an IP header 4 is detected from a reception communication packet 5, and a destination IP address is detected from the IP header 4. An output port number and the destination target IP address corresponding to the IP address are searched from the routing table 11astoring target IP addresses and an output port number for designating a transmission destination LAN for every IP address.

[0023] Also, a memory is described in Japanese Laid Open Patent Application (JP-A-Heisei 7-143156). In the memory, an input register for storing an L-bit data and M data base registers for storing X-bit data. The content of the input register is compared with each of the M data base registers in units of bits. When all bits are coincident with each other in one or more of the M registers, a coincidence signal is outputted. A data base mask register is provided for each of the M data base registers to designate whether the comparing operation is to be performed in units of bits.

[0024] Also, a route determining apparatus is described in Japanese Laid Open Patent Application (JP-A-Heisei 4-140948). In the route determining apparatus, there is a node address register for storing an address to determine a communication route of a node. Also, an upper mesh register, a gate way address register and a channel bit register are provided. An exclusive OR of the value of the node address register and the destination node address is calculated, and the calculation result is masked with the value of the upper mesh register. When the masked value is not 0, a destination unit is determined from the value of the gate way register. When the masked value is 0, the exclusive OR calculating result is masked with the value of the channel bit register for every communication unit. When the masked data is not 0, a communication request is issued. Then, one is selected from the communication units which issue the transmission requests.

[0025] The present invention is accomplished to solve the above problems. Therefore, an object of the present invention is to provide a route searching circuit in which the time required to determine a route can be reduced, so that the load to a CPU can be reduced.

[0026] Another object of the present invention is to provide a communication control apparatus using such a route searching circuit.

[0027] In order to achieve an aspect of the present invention, a communication control apparatus includes an input and output unit responsive to reception of a packet, for generating a search request and a destination address of the packet to receive a resultant route data, and for transmitting the packet based on the resultant route data. A memory stores a route tree table having a tree structure of a plurality of nodes, each of which has a node data. A route searching circuit refers to the route tree table in response to the search request to determine a route data of a final node data as the resultant route data from the destination address, and outputs the resultant route to the input and output unit.

[0028] The route searching circuit includes a next node selecting circuit for referring to the route tree table using the destination address and a predetermined mask data in response to the search request to retrieve a first next node data, for repeatedly referring to the route tree table using an address and mask data of a current node data to retrieve a second next node data, while the first next node data or the second next node data is set as the current node data, until the final node data is obtained.

[0029] The route tree table may have a dichotomy tree structure, and each of the plurality of nodes as a parent node is connected to a left child node and a right child node. In this case, the next node selecting circuit selects one of the left child node and the right child node based on a set of the destination address and a predetermined mask data or a set of the address and mask data of the current node data each time the route tree table is referred to.

[0030] Also, the next node selecting circuit may select one of the left child node and the right child node based on a (the mask data +1)-th bit of the destination address. In this case, when the next node selecting circuit refers to the route tree table based on a node number, the next node selecting circuit includes a first selector for determining an evaluation bit based on the mask data and the destination address, a second selector for selecting one of a number of the left child node and a number of the right child node based on the evaluation bit, a storing circuit for storing a top node number, and a third selector for selecting one of a top node number and the selected child node number in response to the search request.

[0031] Also, the route searching circuit may further include a search end determining circuit for determining whether the final node data is obtained. In this case, the search end determining circuit desirably determines that the final node data is obtained, when there is no node to be referred to or when the second next node data includes an invalidity indicating data.

[0032] Also, the route searching circuit may further include a route updating circuit for selectively updating a held route data to a route data of the first or second next node data. In this case, the route updating circuit may update the held route data to the route data of the first or second next node data, when a logical product of the mask data and the destination address is coincident with the address of the first or second next node data. Also, the route updating circuit may include a masking circuit for masking the destination address using the mask data, an address comparing circuit for comparing the masked destination address and the address of the first or second next node data, and a resultant route data updating circuit for updating the held route data to the route data of the first or second next node data, when the masked destination address is coincident with the address of the first or second next node data, and when a validity data of the first or second next node data indicates that the route data of the first or second next node data is valid.

[0033] Further, the route searching circuit includes a next mask selecting circuit for selecting one of a right child node mask data and left child node mask data of the route data as a selected child node mask data for a next clock cycle based on an evaluation bit determined based on the destination address and the selected child node mask data for a current clock cycle.

[0034] In this case, the route searching circuit may include a next node selecting circuit for referring to the route tree table using the destination address and a predetermined mask data in response to the search request to retrieve a first next node data including the right child node mask data and the left child node mask data, for repeatedly referring to the route tree table using an address of a current node data and the selected child node mask data to retrieve a second next node data including the right child node mask data and the left child node mask data, while the first next node data or the second next node data is set as the current node data, until the final node data is obtained.

[0035] The route tree table may has a dichotomy tree structure, and each of the plurality of nodes as a parent node is connected to a left child node and a right child node. Also, the next node selecting circuit selects one of the left child node and the right child node based on a set of the destination address and a predetermined mask data or a set of the address of the current node data and the selected child node mask data each time the route tree table is referred to.

[0036] Also, the next node selecting circuit may select one of the left child node and the right child node based on a (the selected child node mask data +1)-th bit of the destination address. In this case, the next node selecting circuit refers to the route tree table based on a node number. The next node selecting circuit may include a first selector for determining an evaluation bit based on the selected child node mask data and the destination address in the current clock cycle, a flip-flop circuit for holding the evaluation bit to output in the next clock cycle, a second selector for selecting one of a number of the left child node and a number of the right child node based on the evaluation bit in the next clock cycle, a storing circuit for storing a top node number, and a third selector for selecting one of the top node number and the selected child node number in the next clock cycle in response to the search request.

[0037] Further, the route searching circuit further includes a search end determining circuit for determining whether the final node data is obtained. In this case, the search end determining circuit determines that the final node data is obtained, when there is no node to be referred to or when the second next node data includes an invalidity indicating data.

[0038] In addition, the route searching circuit may further include a route updating circuit for selectively updating a held route data to a route data of the first or second next node data. In this case, the route updating circuit updates the held route data to the route data of the first or second next node data, when a logical product of the selected child node mask data and the destination address is coincident with the address of the first or second next node data. Also, the route updating circuit may include a masking circuit for masking the destination address using the mask data in the current clock cycle, a flip-flop for holding the masked destination address to output in the next clock cycle, an address comparing circuit for comparing the masked destination address and the address of the first or second next node data in the next clock cycle, and a resultant route data updating circuit for updating the held route data to the route data of the first or second next node data in the next clock cycle, when the masked destination address is coincident with the address of the first or second next node data, and when a validity data of the first or second next node data indicates that the route data of the first or second next node data is valid.

[0039] In order to achieve another aspect of the present invention, a method of determining a route to a destination unit based on a destination address of a packet in a communication control apparatus, includes the steps of:

[0040] generating a search request and a destination address of a packet;

[0041] referring to a route tree table in response to the search request to determine a route data of a final node data as the resultant route data from the destination address, the route tree table having a tree structure of a plurality of nodes, each of which has a node data; and

[0042] transmitting the packet to a destination unit based on the resultant route data.

[0043] The referring step may include repeatedly referring to the route tree table using the destination address and a predetermined mask data or using an address and mask data of a current node data to retrieve a second next node data, while the first next node data or the second next node data is set as the current node data, until the final node data is obtained.

[0044] In this case, the repeatedly referring step may include selecting one of a right child node mask data and left child node mask data of the route data as a selected child node mask data for a next clock cycle based on an evaluation bit determined based on the destination address and the selected child node mask data for a current clock cycle.

[0045] FIG. 1A is a diagram illustrating an example of a network address, and

[0046] FIG. 1B is a diagram illustrating a destination address;

[0047] FIG. 2 is a block diagram illustrating the structure of a communication control apparatus using a route searching circuit according to a first embodiment of the present invention;

[0048] FIG. 3 is a diagram illustrating a route tree corresponding to a route table;

[0049] FIG. 4 is a block diagram illustrating the structure of a route searching circuit according to a first embodiment of the present invention;

[0050] FIG. 5 is a block diagram illustrating the structure of a next node selecting circuit shown in FIG. 4;

[0051] FIG. 6 is a block diagram illustrating the structure example of a route updating circuit of FIG. 4;

[0052] FIGS. 7A to 7N are timing charts to explain the operation of the route searching circuit of FIG. 3;

[0053] FIG. 8 is a block diagram illustrating the structure of the route searching circuit according to a second embodiment of the present invention;

[0054] FIG. 9 is a block diagram illustrating the structure of a next node selecting circuit of FIG. 8; and

[0055] FIG. 10 is a block diagram illustrating the structure of a route updating circuit of FIG. 8.

[0056] A communication control apparatus using a route searching circuit of the present invention will be described below in detail with reference to the attached drawings.

[0057] First, the communication control apparatus using the route searching circuit according to the first embodiment of the present invention will be described below. FIG. 2 is a block diagram illustrating the structure of the communication control apparatus according to the first embodiment of the present invention.

[0058] The communication control apparatus in the first embodiment is, for example, a bridge or a router. The communication control apparatus is composed of an input and output unit 1 such as a central processing unit (CPU), a route searching circuit 2 for performing a route search process, and a route tree storing memory 3 for storing route data in the form of a dichotomy tree structure.

[0059] The input and output unit 1 is an apparatus for processing a reception packet. The input and output unit 1 issues a search request signal S of the route data to the route searching circuit 2 together with a destination IP address A. Also, the input and output unit 1 determines the destination of the reception packet based on a resultant route data R outputted from the route searching circuit 2.

[0060] The route searching circuit 2 performs the search of the route data corresponding to the destination IP address A, when the search request signal S and the destination IP address A are inputted from the input and output unit 1. Then, the route searching circuit 2 outputs a search end signal E and the resultant route data R to the input and output unit 1, after the search ends. The route searching circuit 2 supplies a node number N to the route tree storing memory 3 to acquire a node data D, and compares the destination IP address A and the node data D.

[0061] As the route searching circuit 2, it is desirable that a high-speed logic circuit such as an LSI (Large Scale Integrated Circuit). However, a programmable logic device (PLD) may be used in consideration of a short development period and reduction of a manufacturing cost.

[0062] The route tree storing memory 3 is desirably composed of a high-speed SRAM (Static Random Access Memory). However, if it is possible to provide a large capacity of high speed storage block in an LSI, the route tree storing memory 3 is desirably provided in the LSI in which the route searching circuit 2 is provided. This is because the processing speed can be increased to a large extent in addition to a small circuit size.

[0063] A table 1 shows an example of the route table which is stored in the route tree storing memory 3.

[0064] The node number N is equivalent to an address of a memory. When the node number N is inputted, the node data D as information of each node (a route entry) can be read. The node data D is composed of an IP address Da, a mask data Db, a right child node number Dc, a left child node number Dd, a route valid flag De, and a route data Df.

[0065] Each node corresponds to a network address which is defined by the IP address Da and the mask data Db. The IP address Da is represented in the hexadecimal notion in the table 1.

[0066] The mask data Db describes the length of the effective address of a network address in the IP address Da of 32 bits, that is, the length of the mask. The mask data takes a value of 0 to 32 bits.

[0067] A right child node number Dc is a node number of the right side child node which is connected to the node with the node number N as a parent node.

[0068] A left child node number Dd is a node number of the left side child node which is connected to the node with the node number N as a parent node.

[0069] A route valid flag De indicates whether or not the node has the route data. When the node has a route data, the route valid flag De is set to the value indicating validity, e.g., “1”. Also, when the node does not have any route data, the route valid flag De is set to the value indicating invalidity, e.g., “0”.

[0070] A route data Df is a data which is necessary to determine where the reception packet having the destination IP address A which is coincident with the network address of the node which has this route date Df should be transferred. In this embodiment, this route data Df data is used as an address which is peculiar to the transmission destination apparatus.

[0071] FIG. 3 is a diagram illustrating the route tree which corresponds to the route table shown in the table 1. In FIG. 3, “NOD1” indicates the node which has the route data Df, and “NOD2” indicates the node which does not have the route data Df. A numerical value of the upper section in the block of each node is a node number N. Also, a numerical value before the symbol “/” in the lower section is an IP address Da, and a numerical value after the symbol “/” indicates the mask data Db.

[0072] In the route tree in this embodiment, it is supposed that the IP address Da which a node (a route entry) as an object to be structured has is a bit string. A node that the evaluation bit in the IP address Da is “0” is arranged as a child node in the lower left of the parent node. A node that the evaluation bit is “1” is arranged as the 5 child node in the lower right of the parent node. Thus, a dichotomy tree is structured. Unnecessary branch is removed in order to speed up the searching operation.

[0073] Each node has two child node numbers as a node data D, i.e., a right child node number Dc and a left child node number Dd. Thus, the connection relation with the child nodes is defined.

[0074] The above evaluation bit is determined based on the mask data Db. More specifically, when the mask length of the mask data Db is m, the an evaluation bit is the (m+1)-th bit of the IP address Da from the uppermost bit.

[0075] Also, the evaluation bit is shifted from the upper bit of the IP address Da to a lower bit as the searching operation is performed to the route tree in the lower direction. Therefore, the value of the mask data Db becomes large as the searching operation is performed to the route tree in the lower direction.

[0076] It should be noted that when unnecessary branch is removed so as to speed up the searching operation, the evaluation bit does not change continuously as the first bit of the IP address Da, the second bit, the third bit . . . , but changes discretely as the first bit of the IP address Da, the ninth bit, the 16th bit . . . .

[0077] Next, a specific method of structuring the route tree shown in FIG. 3 will be described below.

[0078] First, the mask data Db of the top node with the node number of “1” has is “0”. Accordingly, the first evaluation bit is the first bit of the IP address Da of the concerned node. Because there are a node with the node number of “2” and a node with the node number of “10” as the nodes having the smaller mask data Db next to the top node, these nodes are set as the concerned nodes.

[0079] The IP address Da of the node with the node number of “2” is “80000000”. Because the value of the evaluation bit of this IP address Da is “1”, the node with the node number of “2” is arranged in the lower right of the top node as a parent node. On the other hand, the IP address Da of the node with the node number of “10” is “40000000”. Also, the value of the evaluation bit of this IP address Da is “0”. Therefore, the node with the node number of “10” is arranged in the lower left of the top node as the parent node.

[0080] Next, the mask data Db of the node with the node number of “2” is “8”. Accordingly, the next evaluation bit is the ninth bit of the IP address Da of the concerned node.

[0081] Because there are a node with the node number of “11” and a node with the node number of “3” as the nodes with the next smaller value of the mask data Db. These node are set as the concerned node. The IP address Da of the node with the node number of “11” has is “80B80000”. Because the value of the evaluation bit of this IP address Da is “1”, the node with the node number of “11” is arranged in the lower right of the node with the node number of “2” as a parent node.

[0082] On the other hand, the IP address Da of the node with the node number of “3” is “800A0000”. Because the value of the evaluation bit of this IP address Da is “0”, the node with the node number of “3” is arranged in the lower left of the node with the node number of “2” as the parent node.

[0083] Hereinafter, the route tree of FIG. 3 can be structured in the same way. The route table shown in the table 1 can be provided based on the structured route tree.

[0084] When the route searching circuit 2 is used actually, the structuring and updating operations of the route tree needs to be performed. In order to structure the route tree, an exclusive use hardware circuitry for the route tree may be used or software by a CPU may be used.

[0085] FIG. 4 is a block diagram illustrating the structure of the route searching circuit 2. The route searching circuit 2 is composed of a state control circuit 20, a flip-flop (EDFF) 21 with an enable terminal, a next node selecting circuit 22, a route updating circuit 23, a search end determining circuit 24, and a flip-flop (DFF) 25.

[0086] The state control circuit 20 generates a search execution duration signal W which indicates whether or not the searching operation is being executed in response to two input signals, i.e., the search request signal S and the search end signal E′. The search execution duration signal W is set to a level indicating that the searching process is being executed, e.g., a high (H) level when the search request signal S is received. On the other hand, when the search end signal E′ is received, the search execution duration signal W is set to a level indicating the end of the searching process, e.g., a low (L) level.

[0087] The node data D outputted from the route tree storing memory 3 is supplied to the EDFF 21. As mentioned above, the node data D is composed of an IP address Da, a mask data Db, a right child node number Dc, a left child node number Dd, a route valid flag De, and a route data Df. The EDFF 21 outputs the node data D in synchronous with the rising edge of the clock signal. Also, the search execution duration signal W is supplied to the enable terminal ena of the EDFF 21. The EDFF 21 updates the output only when the search execution duration signal W is in the level illustrating the execution of the searching process.

[0088] The next node selecting circuit 22 selects either one of the right child node number Dc or the left child node number Dd based on the mask data Db in the destination IP address A which is outputted from the input and output unit 1 and the node data D which is outputted from the route tree storing memory 3. The next node selecting circuit 22 outputs the selected number to the route tree storing memory 3 as the node number N.

[0089] The route updating circuit 23 compares the destination IP address A and the network address which is defined based on the IP address Da and the mask data Db to output the address coincidence indicating signal C representing the comparing result. This address coincidence indicating signal C has a level indicating coincidence, e.g., the high (H) level in this embodiment when the address comparing result indicates the coincidence, and a level indicating non-coincidence, e.g., the low (L) level when the address comparing result indicates the non-coincidence.

[0090] Then route updating circuit 23 updates the resultant route data R as its output to the route data Df in the node data D when the address comparing result indicates the coincidence and the route valid flag De is set to the value representing the validity. Also, the route updating circuit 23 holds the resultant route data R when the address comparing result indicates the non-coincidence or when the route valid flag De is set to the value representing invalidity.

[0091] The search end determining circuit 24 generates the search end signal E′ of the “H” level when the node number N outputted from the next node selecting circuit 22 is the address which meets an end condition or when the address coincidence indicating signal C is set to the value representing the non-coincidence.

[0092] The DFF 25 outputs this search end signal E′ to the input and output unit 1 as the search end signal E which is synchronized with the rising edge of the clock signal.

[0093] FIG. 5 is a block diagram illustrating the structure of the next node selecting circuit 22. The next node selecting circuit 22 will be described below with reference to FIG. 5.

[0094] The next node selecting circuit 22 is 10 composed of a 32-1 selector 200, a 2-1 selector 201, a 2-1 selector 202, and a top node number storage circuit 203.

[0095] The 32-1 selector 200 extracts and outputs a 1 bit from the 32-bit destination IP address A based on the mask data Db. More specifically, when the mask length of the mask data Db is m, the (m+1)-th bit of the destination IP address A is extracted and outputted from the upper bit. The output of the 32-1 selector 200 is supplied to the control terminal sell of the 2-1 selector 201 as the selection signal.

[0096] The 2-1 selector 201 selects and outputs the right child node number Dc of the node data D, when the selection signal is “1”, and selects and outputs the left child node number Dd of the node data D, when the selection signal is “0”.

[0097] The search execution duration signal W is supplied to the control terminal sel of the 2-1 selector 202 as the selection signal. The 2-1 selector 202 selects and outputs the node number outputted from the 2-1 selector 201 when the search execution duration signal W is set to the level representing the execution of the searching process. Also, the 2-1 selector 202 selects and outputs the node number of the top node which is stored in the top node number storing circuit 203, when the search execution duration signal W is not set to the level representing the execution of the searching process.

[0098] FIG. 6 is a block diagram illustrating the structure of the route updating circuit 23. The route updating circuit 23 will be described with reference to FIG. 6.

[0099] The route updating circuit 23 is composed of a mask processing circuit 210, an address comparing circuit 211, and a resultant route data updating circuit 212.

[0100] The mask processing circuit 210 outputs a part of the destination IP address A corresponding to the valid bit of the network address of the node by a masking process based on the destination IP address A and the mask data Db the node data D. More specifically, when the ask length of the mask data Db is m, a mask address is produced in which each of the upper m bits is “1” and each of the lower (32−m) bits is “0”. A logical product of the mask address and the destination IP address A is calculated. As a result, an address is outputted in which a portion of the network address other than the portion corresponding to the valid bit.

[0101] The address comparing circuit 211 compares the IP address Da and the output of the mask processing circuit 210 to output the address coincidence indicating signal C indicating the comparing result. The address coincidence indicating signal C has the level representing the coincidence, e.g., the high (H) level in this embodiment, when the address comparing result indicates the coincidence, and the level representing the non-coincidence, e.g., the low (L) level in this embodiment, when the comparing result indicates the non-coincidence.

[0102] The resultant route data updating circuit 212 updates the resultant route data R as its output to the route data Df in synchronous with the clock signal, when the address coincidence indicating signal C indicates the coincidence and when the route valid flag De is set to the value indicating the validity. However, the resultant route data updating circuit 212 holds the resultant route data R when the route valid flag De is set to the value indicating invalidity or when the address coincidence indicating signal C is set to the level indicating the non-coincidence.

[0103] Next, the operation of the communication control apparatus using the route searching circuit 2 according to the first embodiment of the present invention will be described below. In this case, it supposes that the route table of the table 1 corresponding to the route tree of FIG. 3 is stored in the route tree storing memory 3. Also, the operation will be described, taking the case where the packet has the destination IP address A of “800A9011” is received as an example.

[0104] When the packet is received, the destination IP address A is supplied from the input and output unit 1 to the route searching circuit 2 together with the search request signal S. In the route searching circuit 2, the route data corresponding to the destination IP address A is searched while the node data as an object to be compared is read from the route tree storing memory 3. After the searching operation ends, the resultant route data R is outputted to the input and output unit 1 together with the search end signal E.

[0105] The detailed operation of the route searching circuit 2 will be described with the timing charts of FIGS. 7A to 7N.

[0106] In case that the search execution duration signal W is set to the “L” level to indicate that the searching process is not being executed, the 2-1 selector 202 of the next node selecting circuit 22 selects and outputs the output of the top node number storage circuit 203. Therefore, an initial value of the node number N which is outputted from the next node selecting circuit 22 is set to “1” which is the node number of the top node of the route tree, as shown in FIG. 7D. In this way, the initial value of the node data D which is outputted from the route tree storing memory 3 is the node data D1 of the top node with the node number “1”, as shown in FIG. 6E.

[0107] When the search request signal S of the “H” level is received from the input and output unit 1, the state control circuit 20 sets the search execution duration signal W to the “H” level, as shown in FIG. 7C. When the search execution duration signal W is set to the “H” level, the EDFF 21 updates its output to the supplied node data D in synchronous with a rising edge of the lock signal.

[0108] Therefore, the EDFF 21 outputs the node data D1 of the top node in synchronous with the rising edge of the clock signal which is used to start the first node processing (time t1 of FIG. 7). More specifically, the node data D1 of the top node is as follows: the IP address Da is “00000000”, the mask data Db is “0”, the right child node number Dc is “2”, the left child node number Dd is “10”, the route valid flag De is “1” (valid) and the route data Df is Df1.

[0109] The next node selecting circuit 22 selects one to be read next of the right child node number Dc and the left child node number Dd, based on the mask data Db of the node data D and the destination IP address A. More specifically, In the case where the mask length of the mask data Db is m, when the (M+1)-th bit from the uppermost bit of the destination IP address A is “1”, the right child node number Dc is selected and is output. On the other hand, when the same bit is “0”, the left child node number Dd is selected and is output.

[0110] As mentioned above, in the first node processing, the mask data Db is “0”. Since the (0+1)-th bit from the uppermost of the destination IP address A of “800A9011” is “1”, the node number to be read out next is the right child node number Dc. Thus, a value of “2” indicating the right child node number Dc is outputted from the next node selecting circuit 22 as node number N, as shown in FIG. 7D.

[0111] The route tree storing memory 3 outputs the node data D2 of the node with the node number of “2”, when the node number of “2” is supplied, as shown in FIG. 7E. The node data D2 outputted from the route tree storing memory 3 is taken in by the EDFF 21 at the rising edge of the next clock signal, i.e., at the time t2 of FIG. 7. Thus, the first node processing ends and the second node processing is started.

[0112] The node data D2 has the IP address Da of “80000000”, the mask data of “8”, the right child node number Dc of “11”, the left child node number Dd of “3”, the route valid flag De of “0”, and no route data.

[0113] In the second node processing, the next node selecting circuit 22 selects one to be read out next of the right child node number Dc and the left child node number Dd, as in the first node processing. In the second node processing, the mask data Db is “8”. Because the ninth (=8+1) bit from the uppermost bit of the destination IP address A of “800A9011” is “0”, the node number to be read next is the left child node number Dd. Thus, as shown in FIG. 7D, the value of “3” of the left child node number Dd is outputted from the next node selecting circuit 22 as the node number N.

[0114] The route tree storing memory 3 outputs the node data D3 of the node with the node number of “3”, when the node number of “3” is supplied, as shown in FIG. 7E. As mentioned above, the node number N of the node to be processed next in the next clock cycle is outputted for every clock cycle. Then, the node data D is read out from the route tree storing memory 3.

[0115] Next, the operation of the route updating circuit 23 of the route searching circuit 2 will be described below.

[0116] An address obtained by masking the destination IP address A by the mask processing circuit 210 using the mask data Db and the IP address Da of the node data D are compared by the address comparing circuit 211. The address comparing circuit 211 sets the address coincidence indicating signal C to the “H” level, when the address comparing result indicates coincidence.

[0117] The result route data updating circuit 212 pdates the resultant route data R as its output the route data Df in synchronous with the clock signal, when the address coincidence indicating signal C is set to the “H” level indicating the coincidence, and when the route valid flag De is set to the value indicating validity.

[0118] In the above-mentioned first node processing, the mask data Db is “0”. Accordingly, even if the destination IP address A is any value, the output of the mask processing circuit 210 is “00000000” which is coincident with the IP address Da of “00000000”. As a result, in case of the first node processing, the address coincidence indicating signal C is set to the “H” level indicating the coincidence, as shown in FIG. 7L.

[0119] The address coincidence indicating signal C is set to the “H” level indicating the coincidence and the route valid flag De is set to the value of “1” which indicates the validity. Therefore, the result route data updating circuit 212 updates the resultant route data R to the route data Df1 at the timing of the next rising edge of the clock signal, e.g., at the time t2 of FIG. 7N.

[0120] In the second node processing, mask data Db is “8”. Accordingly, the upper 8 bits of the estination IP address A of “800A9011” is taken out and the output of the mask processing circuit 210 is set to “80000000”. This value is coincident with the IP address Da of “80000000”. As a result, in case of the second node processing, the address coincidence indicating signal C is set to the “H” level indicating the coincidence. In this case, however, because the route valid flag De is set to the value of “0” indicating the invalidity, the resultant route data R is not updated at the time of the rising edge of the next clock signal, as shown in FIG. 7 as time t3. As a result, the resultant route data R is held, as shown in FIG. 7N.

[0121] In the third node processing, the mask data Db is set in the value of “16”. Accordingly, the upper 16 bits of the destination IP address A of “800A9011” are taken out and the output of the mask processing circuit 210 is set to the value of “800A0000”. This value is coincident with the IP address Da of “800A0000”. As a result, in case of the third node processing, the address coincidence indicating signal C is set to the of “H” level indicating coincidence. The result route data updating circuit 212 updates the resultant route data R to the route data Df3 at the time of the rising edge of the next clock signal, as shown in FIG. 7N at the time t4. This is because the address coincidence indicating signal C is set to the “H” level indicating the coincidence and moreover the route valid flag De is set to the value of “1” indicating the validity.

[0122] In the fourth node processing, the mask data Db is set to the value of “24”. Accordingly, the upper 24 bits the destination IP address A of “800A9011” is taken out and the output of the mask processing circuit 210 is set to the value of “800A9000”. This value is not coincident with the IP address Da of “800AC000”. As a result, in the fourth node processing, the address coincidence indicating signal C is set to the “L” level indicating non-coincidence, as shown in FIG. 7L. Because the address coincidence indicating signal C is set to the “L” level indicating the non-coincidence, the resultant the route data R is not updated at the time of the rising edge of the next clock signal, i.e., the time t5 of FIG. 7. The resultant the route data R is maintained, as shown in FIG. 7N.

[0123] Next, the operation of the search ending determining circuit 24 will be described below.

[0124] The search ending determining circuit 24 generates the search end signal E′ of the “H” level, when the node number N outputted from the next node selecting circuit 22 is the address which meets an end condition or when the address coincidence indicating signal C is set to the level indicating non-coincidence. More specifically, the above address when the node number N meets an ending condition means that there is no address to be read out next.

[0125] Referring to FIG. 7, in the fourth node processing, because the address coincidence indicating signal C is set to the “L” level indicating a non-coincidence, the search ending signal E′ is set to the “H” level. When receiving the search end signal E′ of the “H” level, the state control circuit 20 sets to the search execution duration signal W of the “L” level, as shown in FIG. 7C. The search execution duration signal W is set to the “L” level, the EDFF 21 stops the updating of the output. As a result, the resultant the route data R outputted from the route updating circuit 23 is maintained at the route data Df3. Then, since the search ending signal E′ is set to of “H”, this search end signal E′ is outputted from the DFF 25 as the search end signal E at the rising edge of the next clock signal at the time t5 of FIG. 7.

[0126] When receiving the search end signal E of the “H” level, the input and output unit 1 receives the route data R at that time as the final resultant the route data. As a result, the input and output unit 1 determines the destination of the reception packet based on the route data R.

[0127] The communication control apparatus according to the second embodiment of the present invention will be described below.

[0128] FIG. 8 is a block diagram illustrating the structure of the route searching circuit of the present invention. The structure of the communication control apparatus in the second embodiment is same as that in the first embodiment shown in FIG. 2. However, in the second embodiment, the route searching circuit 2ais used instead of the route searching circuit 2 shown in FIG. 2.

[0129] The route searching circuits is composed of the state control circuit 20, the EDFF 21, a next node selecting circuit 22a, a route updating circuit 23a, the search ending determining circuit 24, the DFF 25, a next mask selecting circuit 26. The next mask selecting circuit 26 is newly provided as one unit connected to the output of the EDFF 21 in the route searching circuit 2 in the first embodiment.

[0130] A next node bit B, a right child node the mask Dg, and a left child node mask Dh are supplied to the next mask selecting circuit 26. The next node bit B is a signal indicating whether the node to be read out next is a right child node or a left child node. When the next node bit B is “0”, the next node is the left child node. On the other hand, when the next node bit B is “1”, the next node is the right child node.

[0131] The right child node mask Dg and the left child node mask Dh are data which are newly added to each node data D in the route table as the components of the node data D. The right child node mask Dg is the mask data of the right child node of the node read out currently. The left child node mask Dh is the mask data of the left child node of the node read out currently.

[0132] The next mask selecting circuit 26 selects either one of the right child node mask Dg and the left child node mask Dh in accordance with the next node bit B. The next mask selecting circuit 26 outputs the selected data as the next mask data 9ito the next node selecting circuit 22aand the route updating circuit 23a. In other words, the next mask selecting circuit 26 selects and outputs the left child node mask Dh when the next node bit B is “0”, and selects and outputs the right child node mask Dg when the next node bit B is “1”.

[0133] FIG. 9 is a block diagram illustrating the structure example of the next node selecting circuit 22ain the second embodiment. Referring to FIG. 9, the next node selecting circuit 22ais composed of the 32-1 selector 200, the 2-1 selector 201, the 2-1 selector 202, the top node number storage circuit 203, a flip-flop (DFF) 204. The DFF 204 is newly provided between the 32-1 selector 200 and the 2-1 selector 201 in addition to the next node selecting circuit 22 in the first embodiment.

[0134] The mask data supplied to the 32-1 selector 200 is the next mask data 9i. Because this next mask data 9I is the data which becomes necessary in case of node processing in the next clock cycle, the output of the 32-1 selector 200 is delayed by 1 clock by the DFF 204. Thus, the synchronization can be established. The next node bit B is the output of the DFF 204, and supplied to the 2-1 selector 201 and the next mask selecting circuit 26.

[0135] It should be noted that the DFF 204 outputs the 0th bit from the uppermost bit of the destination IP address A, i.e., the most significant bit as an initial value of the next node bit B, when the search execution duration signal W is set to the “L” level indicating that the operation is not during execution of the searching process. The other operation is same as in the first embodiment.

[0136] By adopting such a structure, in this embodiment, because the bit select processing in the 32-1 selector 200 can be executed in the clock cycle before one cycle, the processing time required to output the node number N can be reduced.

[0137] FIG. 10 is a block diagram illustrating the structure example of the route updating circuit 23ain the second embodiment. The route updating circuit 23ais composed of the mask processing circuit 210, the address comparing circuit 211, the resultant the route data updating circuit 212, and a flip-flop (DFF) 213. The DFF 213 is newly provided between the mask processing circuit 210 and the address comparing circuit 211 in addition to the route updating circuit 23 in the first embodiment.

[0138] The mask data supplied to the mask processing circuit 210 is the next mask data 9i. Because the next mask data 9I is the data which becomes necessary in case of node processing in the next clock cycle, the output of the mask processing circuit 210 is delayed by 1 clock by the DFF 213. Thus, the synchronization is established. By adopting such a structure in the second embodiment, the mask processing by the mask processing circuit 210 can be executed in the clock cycle before by one, the processing time required to output the address coincidence indicating signal C and the resultant the route data R can be reduced.

[0139] As mentioned above, the next mask data 9ias the mask data Db of the node data D to be read in the next clock cycle is earlier outputted from the next mask selecting circuit 26. In this way, because the processing relating to the mask data Db is earlier executed by one clock cycle, the processing time required in the next node selecting circuit 22aand the route updating circuit 23acan be reduced. Also, the clock frequency required to operate the route searching circuit 23acan be increased to a higher frequency. Because the clock frequency can be increased to the higher frequency, the retrieval time of the route searching circuit 22acan be made short.

[0140] Next, the communication control apparatus according to the third embodiment of the present invention will be described below.

[0141] In the first and second embodiments, it is supposed that the route data Df in the route table is the address which is peculiar to the transmission destination apparatus. If this the route data Df is a pointer to the data which is necessary to transmit the reception packet, e.g., the value which is identical with the node number, the capacity of the route tree storing memory 3 can be reduced, because the route tree table is not necessary to have the route data (address) Df as the component of the node data D. As a result, an interface part of the route searching circuit can be made small in size. In this case, however, means for acquiring a necessary route data to transmit a reception packet from the above pointer must be provided for the input and output unit 1.

[0142] It should be noted that in the above embodiments, the descriptions are given using the route data retrieval from the destination IP address as examples. However, the present invention is not limited to this. The present invention can be applied to the route searching process in which the apparatus for a packet to be transmitted next is determined based on an address which specifies a communication destination.

[0143] Also, in the above embodiment, the route tree storing memory is provided outside the route searching circuit. However, the route tree storing memory may be provided in the route searching circuit.

[0144] As described above, according to the present invention, the address solving process can be executed at high speed to light the load of the CPU. As a result, the throughput of the processing in the communication control apparatus can be increased. This is because the address solving process is executed by the selecting process and the route data determining process are executed by the exclusive use hardware so that each entry can be for 1 clock cycle.

[0145] Also, the route searching circuit can be made small in size. Even if the number of entries in the route table increases, the route searching circuit never becomes large in size. This is because in the route searching circuit, only one route entry is always read, and the comparing process is performed. Therefore, even if the number of entries in the route table increases, it is sufficient to make the capacity of the route tree storing memory large.

[0146] Also, even when the destination address is coincident with the network addresses of a plurality of route entries in the route table, the route data corresponding to the network address which has the longest network mask is searched. Therefore, even if the present invention can be applied to the network in which the destination address has the possibility to coincident with the plurality of network addresses, like the IP address. This is because the route data updating process is performed based on the address comparison in parallel with the processing for determining the next route entry. When the address comparison indicates the coincidence, the resultant route data is updated, and when the address comparison indicates non-coincidence, the resultant route data is maintained. In the route tree, the mask length becomes long in order of the read route entry. Therefore, the route data of the route entry in which the address comparison result finally indicates coincidence is maintained. Thus, the route data corresponding to the network address which has the longest network mask can be searched.