JPH09247202A - Node device - Google Patents

Abstract

The present invention relates to a node device that performs storage and exchange, and an object thereof is to flexibly adapt to the number of ports and hosts to be accommodated and to greatly improve the efficiency of route selection. A route table storing a host address of a data terminal of its own station, a network address indicating a logical network, and a pseudo host address and a network address of another network,
Of these combinations of addresses, both for the data terminals accommodated by the own station, for the networks connected via other stations, a mask table storing a mask pattern indicating only the network address, and a logical network An outgoing route table in which route identification information indicating a route to another network is stored,
The route table is searched using the logical product of the network address and the host address given by the mask pattern and the accumulated message as a key, and the network address and the host address equal to the logical product are stored in the outgoing route table. And a route selecting means for obtaining route identification information.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a node which is arranged at a node of a plurality of networks to which TCP / IP or a communication procedure based on TCP / IP or a similar network is applied or at one end of similar networks and which stores and exchanges based on the communication procedure. Regarding the device.

[0002]

2. Description of the Related Art In recent years, TCP / IP, which is an international standard protocol, has been widely applied to the field of data communication performed between computers via a wide area network or a local network. , News, file transfer (FTP), remote login (Te
Lenet), IP connection that can realize many functions such as transmission and reception of multimedia information.

FIG. 9 is a diagram showing a configuration example of a network to which IP connection is applied. In the figure, a network computer 100 _A includes host computers (hereinafter simply referred to as “hosts”) 101 ₀₁ , 101 ₀₂ , 101 ₀₃ , 101.
₀₄ is accommodated, and one end of the network is the router 102.
Connected to port x of ₁ . Port z of router 102 ₁
Is connected to one end of a network 100 _B , and hosts 101 ₀₅ , 101 ₀₆ , 101 ₀₇ , 1 are connected to the network.
01 ₀₈ is accommodated. The other end of the network 100 _B is connected to the first port of the router 102 ₂ , and the network 100 _D is connected to the second port of the router 102 ₂ .
Further, hosts 101 ₀₉ , 101 ₁₀ and 101 ₁₁ are connected to the ports l, m and n of the router 102 ₁ , respectively. In the following, for simplicity, the host 101 ₀₉ , 1
Assume that the network to which 01 ₁₀ , 101 ₁₁ belongs is network 100 _C.

In this way, the network 100_A, 100_B
Router 102 placed at the connection point ₁ Then store exchange
The main memory of the processor (not shown) for executing the process is shown in FIG.
As shown in 0, only the ports x and z of the router are
And connect other routers directly to these ports.
A network showing networks that are indirectly connected via
Network where the network address (= A, (B, D)) is stored
The clute table 111 is stored in advance. In addition,
Data 102₁ As shown in FIG. 11, the main memory of
All hosts 101 housed in₀₉, 101_Ten, 101
₁₁About network 100_C Indicating
Network address (here, for simplicity, subscript
Assume "C". ) And individual identification
Host address (Here, for simplicity, subscript "0
Assume equal to 9 "," 10 "," 11 ". )And
Host identification information and a port indicating the connected port.
Host route table that is associated with
Module 121 is stored in advance.

For example, when the router 102 ₁ receives a packet (or message) which is a target of relay exchange from port x and includes a network layer address composed of a network address and a host address, these network addresses ( The search processing is performed by referring to the host route table 121 using the destination and the host address as search keys (FIG. 12 (1)).

Further, the router 102₁ Of the search process
If the port identification information corresponding to the search key is obtained during the process,
The port indicated by the port identification information
(Fig. 12 (2)). But such a po
If the router identification information is not obtained, the router 102 ₁ 
Is a network address contained in a similar network layer address.
Network route with network address as search key
Search processing is performed by referring to the table 111
(Fig. 12 (3)).

Further, when the router 102 ₁ obtains the port identification information corresponding to the search key in the course of the search processing, the router 102 ₁ selects the port indicated by the port identification information as the outgoing route (FIG. 12). (Four)). However, when such port identification information is not obtained, the router 102
₁ discards the corresponding packet (FIG. 12 (5)).

[0008]

By the way, in such a conventional example, the route is selected by performing the search process based on different search keys for the host route table 121 and the network route table 111. , The processing efficiency is low, and the efficiency is router 10
The larger the number of ports that 2 ₁ has, the more markedly decreased.

Further, in recent years, the number of hosts has increased, the amount of information to be transmitted has remarkably increased, and the types of the information and the types of required services have tended to be diversified. There is a strong demand for faster route selection.
Furthermore, such a request is not limited to routers, but is also applicable to any of node devices, bridges, and hubs installed at connection points between networks, and in particular, address space is provided for the purpose of dealing with a shortage of IP addresses. IP standardized from 32 bits to 128 bits
When v6 is applied, the word length of the calculation target of the above-described search processing also becomes large, so there has been a strong demand for reduction of the calculation required time.

It is an object of the present invention to provide a node device in which the efficiency of route selection is greatly improved while flexibly adapting to the number of ports and accommodated hosts.

[0011]

FIG. 1 is a block diagram showing the principle of the invention described in claims 1 to 4.

According to the first aspect of the invention, a network address given from a plurality of routes and indicating a network accommodating a destination data terminal, and a host address used for identification with other data terminals are provided. The exchanging means 12 is provided with an accumulating means 11 for accumulating a message containing
Contains the host address and the network address indicating the logical network to which the data terminal belongs, and the pseudo host address for networks connected via other stations. And a network address indicating the network are stored in advance, and under the addressing common to the route table 13, the host address and the network address stored in the route selection table,
Both the data terminals accommodated in the own station, the mask table 14 in which the mask pattern indicating only the network address is stored in advance for the network connected through the other station, and the addressing common to the route table 13 For a plurality of routes, an outgoing route table 15 in which route identification information indicating a route connected to a logical network and a network connected via another station is stored in advance, and an addressing table Below, for each of the messages stored in the storage means 11, the route table 13 is searched using the logical product of the included network address and host address and the mask pattern stored in the mask table 14 as a key. Among the plurality of routes, the route identification information stored in the output route table 15 is obtained corresponding to the network address and the host address which are equal to the logical product, and And having a route selecting means 16 for selecting a route indicated by the road identification information as output path.

According to a second aspect of the present invention, a network address, which is given from a plurality of routes and indicates a network accommodated by a destination data terminal, and a host address, which is used for identification with other data terminals, are provided. The exchanging means 12 is provided with an accumulating means 11 for accumulating a message containing
Includes a combination of a host address indicating a data terminal accommodated in the local station and a network address indicating a logical network to which the data terminal belongs, a pseudo host address, and a network connected via another station. Of the plurality of routes in the ascending or descending order of the binary number indicated by the combination with the indicated network address,
A route table 2 in which control information indicating the presence / absence of a route to these networks and route identification information indicating the route are stored in advance.
1 and the host address and the network address stored in the route table 21, both of the data terminals accommodated in the own station, and the mask pattern indicating only the network address of the network connected through the other station. Is stored in advance, and for each message accumulated in the accumulating means 11, while scanning the mask pattern stored in the mask table 23, the mask pattern obtained under the scanning and the message The logical product of the included network address and the host address is calculated, and the route identification information stored together with the control information indicating that there is some route in the route table 21 is obtained for the logical product, and the route identification is performed. And a route selecting means 25 for selecting the route indicated by the information as the outgoing route.

According to a third aspect of the present invention, in the node device according to the first aspect, in the route table 13, the storage area for storing the host address and the network address is a binary number indicated by the combination thereof. The routes are assigned in ascending or descending order, and the route selecting means 16 is characterized by performing a search based on the binary search method. The invention described in claim 4 is
The node device according to any one of claims 1 to 3, wherein all or part of a route table, a mask table, and an outgoing route table are made redundant, and a route table is provided in the route selecting means. , A mask table and an outgoing route table, including means for limiting the reference target to the one that is redundant and is the active system under the system configuration,
Of the mask table and the outgoing route table, the updating means 3 for updating a redundant system that is a standby system under the system configuration.
It is characterized by having 1.

In the node device according to the first aspect of the present invention, the route table 13 includes a host address for a data terminal accommodated in the local station and a network address indicating a logical network to which the data terminal belongs. Is stored, and for a network connected via another station, a pseudo host address and a network address indicating the network are stored in advance. Further, the mask table 14 includes the above-mentioned route table 1
Among the host addresses and network addresses stored in the route selection table under the same addressing as that of No. 3, for both data terminals accommodated in the own station, for networks connected via other stations, A mask pattern for selecting only the network address is stored in advance, and the output route table 15 is provided under the same addressing for a plurality of routes via a logical network to which the data terminal belongs and another station. The route identification information indicating the route to the network to be connected is stored in advance.

Further, the storage means 11 is provided with a plurality of routes described above, and a network address indicating a network in which a destination data terminal is accommodated, and a host address used for identification with other data terminals. Accumulate messages containing. The route selecting means 16 searches the route table 13 using the logical product of the network address and the host address included in the message thus accumulated and the mask pattern stored in the mask table 14 as a key. Thus, the route identification information stored in the output route table 15 corresponding to the network address and the host address equal to the logical product is obtained, and the route indicated by the route identification information is selected as the output route. Further, the exchanging means 12 accumulates and exchanges the messages accumulated in the accumulating means 11 under such route selection.

That is, route selection is performed based on the same procedure regardless of whether the destination is a data terminal accommodated in the own station or a network connected via another station.
The procedure of processing relating to storage exchange is simplified. In the node device according to the invention described in claim 2, the route table 21 is a combination of the route table 13 and the outgoing route table 15 which constitute the invention described in claim 1, and the mask table 23 and the route table 21 are combined. Since the route selecting means 25 has a function equivalent to that of the mask table 14 and the route selecting means 16 under such merging, the description of the operation of each of these means will be omitted here.

Therefore, as in the case of the first aspect of the invention, the procedure of processing relating to route selection is simplified and the hardware configuration is also simplified. In the node device according to the third aspect of the present invention, the route table 13 is allocated with storage areas for storing host addresses and network addresses in ascending or descending order of the binary numbers indicated by these combinations, and the route is selected. The means 16 performs the search based on the binary search method.

That is, for each message accumulated in the accumulating means 11, reference is made to the route table 13, mask table 14 and outgoing route table 15 which the route selecting means 16 should perform prior to the completion of route selection. The number of times is a value proportional to log ₂ N with respect to the number N of routes that can be outgoing routes, and high responsiveness is secured even when the number N is large.

In the node device according to the fourth aspect of the present invention, all or part of the route table, the mask table and the output route table are made redundant, and the route selecting means is provided with these route tables. Of the mask table and the output route table, the reference target is limited to the one that is made redundant and is the active system under the system configuration. Also, the updating means 31
Among the route table, the mask table and the output route table thus made redundant, the one which is the backup system under the same system configuration is updated.

That is, when routes are selected with reference to the route table, mask table, and output route table of the active system, the backup systems of these tables are reliably updated in parallel. Therefore, it is possible to flexibly adapt to the addition and modification of the data terminals accommodated in the network and the local station and other stations without interruption of the operation.

[0022]

Embodiments of the present invention will be described below in detail with reference to the drawings.

FIG. 2 is a diagram showing an embodiment corresponding to the invention described in claims 1, 3, and 4. The configuration of this embodiment is characterized in that the routing control unit shown in FIG. 2 is replaced by the router 1 instead of the conventional routing control unit shown by the dotted line in FIG.
It provided 02 _1, and the network route table 1
11 and the host route table 121 are not provided. Since the network and the host connected to the router 102 ₁ are the same as those in the conventional example shown in FIG. 9, the description thereof will be omitted here.

In such a routing control unit, a search is performed.
The address output of the control unit 51 is a mask data memo.
Ri 52₁ , Routing memory 53₁ And output memory
54 ₁ Address input A₁ Connected to that mask day
Memory 52₁ Output D₀₁Is one of the masking parts 55
Connected to input. For the other input of the masking section 55
The IP address is given, and the output of the masking section is
It is connected to one input of the comparator 56. Routing notes
Re 53₁ Output D₀₁Is connected to the other input of comparator 56
The first output of the comparator is the output memory 54.₁ Control
Connected to input. The second output of the comparator 56 is a search system.
It is connected to the control input of the control unit 51. Output memory 54₁ of
The port identification information is obtained in the output, and the control of the search control unit 51 is performed.
A discard control signal is obtained at the output.

Regarding the correspondence relationship between this embodiment and the block diagram shown in FIG. 1, the router 102 ₁ has the storage means 1
1 and the exchange means 12, corresponding to the routing memory 5
3 ₁ corresponds to the route table 13, the mask data memory 52 ₁ corresponds to the mask table 14, and the output memory 54
₁ corresponds to the outgoing route table 15, and the search control unit 51, the masking unit 55 and the comparator 56 correspond to the route selecting means 16.

Hereinafter, referring to FIG. 2 and FIG.
The operation of the present embodiment corresponding to the invention described in (1) will be described.
As shown in FIG. 3, in the routing memory 53 ₁ , for the networks 100 _A , 100 _B and 100 _D directly or indirectly connected to the router 102 ₁ , the individual network addresses “A” of these networks,
The host 101 accommodated in the router is set with “B” and “D” and the default value of the host address (here, it is assumed that the logical values of all bits are “0” for simplicity). _{09-101 11} for, the network address of the network to which these hosts belong to "C"
And individual host addresses "09", "10", "1"
The routing table 71 in which “1” is set is stored in advance.

Further, as shown in FIG. 4, in the output memory 54 ₁ , under the addressing common to the routing table 71, the networks 100 _A , 10
An outgoing route table 81 which gives port identification information of outgoing ports for 0 _B and 100 _D and hosts 101 _{09 to} 101 ₁₁ is stored in advance. Further, the mask data memory 5
2 ₁ includes the routing table 7 as shown in FIG.
1 and the outgoing route table 81, under the common addressing, among the network addresses and host addresses included in the IP address, the networks 100 _A , 100
_{For B} and 100 _D , only the former is supported, and host 1
For 01 _{09 to} 101 ₁₁ , a mask table 91 that gives a bit string (hereinafter, referred to as a “mask pattern”) corresponding to both is stored in advance.

The router 102 ₁ is the network 10
0 _A, 100 _B, 100 _D and the host 101 _{09-101
When a} packet is received from any of _11, the IP address included in the packet is extracted. Search control unit 51
Gives the IP address extracted in this way to the masking unit 55, and the mask data memory 52 ₁ , the routing memory 53 ₁ , and the output memory 54 ₁ have a routing table 71, an outgoing route table 81 and a mask table 91. Outputs an address that goes through the storage area in word units.

The mask data memory 52 ₁ sequentially reads out the mask pattern from the area of the mask table 91 indicated by the address and outputs it. Furthermore, the masking section 5
5 obtains only the network address of the networks 100 _A , 100 _B , and 100 _D among the network addresses and host addresses included in the IP address by taking the logical product of the above-mentioned IP address and its mask pattern. selected, host 101 _{09-101 11}
For, select both its network address and host address.

Further, the routing memory 53 ₁ reads the combination of the network address and the host address from the area of the routing table 71 indicated by the similar address. The comparator 56 compares the network address and the host address thus read with the network address and the host address selected by the masking unit 55 as described above to determine whether or not they match. If the result of the determination is true, the search control unit 51 and the output memory 54 ₁ are notified of that fact. When the search control unit 51 recognizes the notification, the search control unit 51 cancels the above address update. Further, when recognizing the similar notification, the output memory 54 ₁ reads the port identification information from the output route table 81 indicated by the address given by the search control unit 51 at that time and outputs it.

However, when the result of the above-mentioned discrimination is false, the comparator 56 determines that the search controller 51 and the output memory 5
4 ₁ any does not emit notification to and, the search control unit 51
Will continue to update the address. Furthermore, the search control unit 51
When the address is updated in this way and the address goes through the storage areas of the routing table 71, the output table 81 and the mask table 91 in units of words, a discard control signal requesting the discard of the corresponding packet is sent. Output.

As described above, according to this embodiment, whether the destination indicated by the IP address is the host accommodated in the router or the network directly or indirectly connected to the router, the routing table 71 is used. Since the route is surely selected based on the search process performed while referring to the outgoing route table 81 and the mask table 91 in parallel, the processing procedure is simplified and the responsiveness is improved as compared with the conventional example. Is increased.

FIG. 6 is a diagram showing an embodiment corresponding to the invention described in claim 2. In FIG. In the figure, components having the same functions and configurations as those shown in FIG. 2 are denoted by the same reference numerals, and description thereof is omitted here.

The difference between the present embodiment and the embodiment corresponding to the invention according to claim 1 is that a routing memory 59 is provided in place of the routing memory 53 ₁ , the output memory 54 ₁ and the comparator 56. The output of the masking section 55 is connected to the address input of the routing memory, and a specific 1 bit of the output of the routing memory 59 is connected to the control input of the search control section 51.

Regarding the correspondence relationship between this embodiment and the block diagram shown in FIG. 1, the router 102 ₁ has the storage means 1
1 and the exchange means 12, corresponding to the routing memory 5
9 corresponds to the route table 21, and the mask data memory 5
Reference numeral 2 corresponds to the mask table 23, and the search control unit 51 and the masking unit 55 correspond to the route selecting means 25. The operation of this embodiment will be described below with reference to FIGS. 5, 6 and 9.

The operations of the search control unit 51, the mask data memory 52 and the masking unit 55 are the same as those in the embodiment corresponding to the invention described in claim 1, and therefore the description thereof is omitted here. . As shown in FIG. 7, in the routing memory 59, the combination of the network address and the host address obtained at the output of the masking unit 55, the default of the network address and the host address in which the logical values of all bits are “0” For all bit patterns that can be given as a combination with a value, (1) If an outgoing route should be assigned, a control bit with a logical value of "1" and port identification information indicating that outgoing route. (2) On the contrary, if no outgoing route is assigned, the logical value is "0".
And the illegal port identification information indicating the port that the router 102 ₁ does not have (here, for simplicity, it is assumed that the logical values of all the bits are given by a bit pattern of “1”). _A routing table 71 _A is stored in advance, each of which indicates the ascending order of the address indicated by the bit pattern.

Therefore, the routing memory 59 is
In the area of the routing table 71 _A, the mask patterns given by the mask table 91 and the received IP addresses are sequentially indicated by the addresses given by the masking section 55 under the initiative of the search control section 51. The port identification information (or illegal port identification information) and the control bit stored in the area are read and output.

Therefore, according to this embodiment, the routing memory 53 ₁ , the output memory 54 ₁ and the comparator 5
In the same manner as the embodiment corresponding to the invention described in claim 1, route selection is efficiently performed under a simple hardware configuration including a routing memory 59 instead of 6.
In the above-described embodiment, the output of the masking unit 55 is directly connected to the address input of the routing memory 59, but the present invention is not limited to such a configuration. For example, the port of the node device and its node When the total number of hosts accommodated in the device is small, by adding a means for performing address conversion between the masking section 55 and the routing memory 59, the illegal area in the storage area of the routing table 71 _A is added. It is also possible to reduce the number of areas in which the port identification information is stored and compress the storage capacity of the routing memory 59.

An embodiment corresponding to the invention of claim 3 will be described below. The difference between the present embodiment and the embodiment corresponding to the invention according to claim 1 is that a search control unit 60 having the structure shown in FIG. 8 is provided in place of the search control unit 51. In the search control unit 60, a start signal is given to the reset terminals of the D flip-flop 61 and the RS flip-flop 62, and the inverted output of the RS flip-flop 62 is connected to the D input of the D flip-flop 61. The inverted output of the D flip-flop 61 is connected to the set input of the RS flip-flop 62. The non-inverted output of the D-type flip-flop 61 is connected to the selection inputs of the selectors 63 _L and 63 _H , and a clock is given to the clock terminals of the D-type flip-flop 61 and the registers 64 _L and 64 _H. A mask table 91, a routing table 71, and an output route table 81 in the storage areas of the mask data memory 52 ₁ , the routing memory 53 ₁ and the output memory 54 ₁ are provided at the first inputs A of the selectors 63 _L and 63 _H. Addresses (hereinafter, referred to as “initial addresses”, which are assumed to be “0” and “N−1”, respectively, for simplicity) of the allocated storage area are given respectively. Selector 63 _L , 63 _H
The output of is connected to the inputs of registers 64 _L and 64 _H , respectively. The output of the register 64 _L is connected to one input of the adder 65 and the comparator 66 and the input A of the selector 67 _L , and the output of the register 64 _H is the other input of these adder and comparator and the selector 67 _H. Connected to one input B. The outputs of the selectors 67 _L and 67 _H are connected to the other inputs B of the selectors 63 _L and 63 _H , respectively, and the output of the adder 65 is passed through a divider 68 to the incrementer 6
9 input and the other input A of the selector 67 _H ,
Mask data memory 52 ₁ , routing memory 53 ₁
And the address input A ₁ of the output memory 54 ₁ . The output of the incrementer 69 is connected to the other input B of the selector 67 _L , and the discard signal is given to the output of the comparator 66. The selection inputs of the selectors 67 _L and 67 _H are
The second output of the comparator 56 is connected.

Regarding the correspondence relationship between this embodiment and the block diagram shown in FIG. 1, the router 102 ₁ has the storage means 1
1 and the exchange means 12, corresponding to the routing memory 5
3 ₁ corresponds to the route table 13, the mask data memory 52 ₁ corresponds to the mask table 14, and the output memory 54
₁ corresponds to the outgoing route table 15, and the search control unit 51, the masking unit 55 and the comparator 56 correspond to the route selecting means 16.

Hereinafter, referring to FIG. 2 and FIG.
The operation of the embodiment corresponding to the invention described in (1) will be described. The feature of this embodiment is that the contents of the routing table 71, the outgoing route table 81, and the mask table 91 are set in the ascending order of the binary numbers indicated by the bit string consisting of the combination of the network address and the host address, and the mask. Data memory 52 ₁ , routing memory 5
3 ₁ and the procedure for updating the address provided to the output memory 54 ₁ .

The operation performed by each unit other than the search control unit 60 in response to such an address is the same as the operation of the embodiment corresponding to the invention described in claim 1, and therefore its description will be given here. Omit it. In the search control unit 60, the D-type flip-flop 61 and the RS flip-flop 62 are provided with an activation signal issued from the router 102 ₁ each time a packet for route selection is received. The logical value of such a start signal changes from a steady value "0" to "1" corresponding to each of the above-mentioned packets, and the route selection is completed or the corresponding packet is discarded. Then, it returns to its steady value.

Therefore, when the logical value becomes "1", the D-type flip-flop 61 clocks the logical value of the non-inverted output of the RS flip-flop 62 which was forcibly reset according to the steady value of the activation signal. Hold at the leading edge of. The selectors 63 _L and 63 _H are thus set to D
The initial addresses "0" and "N-1" are selected in accordance with the logical value "1" held in the type flip-flop 61.

The registers 64 _L and 64 _H respectively hold such initial addresses at the timing of the subsequent trailing edge of the clock. The adder 65 and the divider 68 find the median value (= (N-1) / 2) of these initial addresses, and use the median value as an address for the mask data memory 52 ₁ ,
It is given to the routing memory 53 ₁ and the output memory 54 ₁ . Further, the median is the input A of the selector 67 _H.
Is given to the input B of the selector 67 _L after being incremented by “1” by the incrementer 69. In the following, the selector 67 _L
The address given to the input B of is referred to as an "updated top address".

Further, the judgment result output from the comparator 56 is I
Regarding the binary number indicated by either the combination of the network address and the host address included in the P address or the combination of the network address and the default value of the host address, "the bit given by the routing table 71 to the above-mentioned address If it is larger than the binary number indicated by the pattern, the selector 67 _L selects the above-mentioned updated top address, and the selector 67 _H has the “existing bottom address” currently held in the register 64 _H. Select.

However, when a determination result opposite to such a determination result is given, the selector 67 _H selects the "update bottom address" given as the above-mentioned average value, and the selector 67 _L is at that time. The "existing top address" held in the register 64 _L is selected by. On the other hand, the RS flip-flop 62 is set according to the binary signal of the logical value "0" given from the non-inverted output of the D-type flip-flop 61 at the time of the leading edge of the clock, so that the D-type flip-flop 62 is set. At the subsequent leading edge of the clock, and remains in that state until the logic value of the activation signal returns to a steady value again.

Therefore, the logical values of the selection signals given to the selectors 63 _L and 63 _H are inverted, and these selectors respectively combine the existing top address and the updated bottom address and the updated top address and the existing bottom address. Either one of the combinations is selected and given to the registers 64 _L and 64 _H. The registers 64 _L and 64 _H , the adder 65 and the divider 68 update the address by averaging the thus updated top address and bottom address, and further, the incrementer 69 and the selectors 67 _L and 67. _H , 63 _L , 63 _H , register 64 _L ,
64 _H , the adder 65 and the divider 68 repeatedly and similarly update the address based on the address obtained as a result of the update.

Further, the comparator 66 indicates that the route selection of the corresponding packet is impossible when the existing top address and the existing bottom address are in the same state in the process of updating the address. Output the discard control signal. As described above, according to the present embodiment, since the addressing for the routing table 71, the outgoing route table 81, and the mask table 91 is performed based on the binary search method, these tables necessary for achieving the route selection of individual packets are provided. The number of times of reference becomes a value proportional to (log ₂ N), and even when the exact number N is large, the responsiveness is maintained higher than that of the embodiment corresponding to the invention described in claim 1.

An embodiment corresponding to the invention of claim 4 will be described below with reference to FIG. The difference between the present embodiment and the embodiment corresponding to the invention described in claim 1 is that the mask data memory 52 ₁ , the routing memory 53 ₁ and the output memory 54 ₁ are all configured with dual port RAMs and are duplicated. (Hereinafter, those added with the duplication thereof are indicated by adding the subscript "2" to the same code.), And the data input D among the second ports of all these memories is provided. _i2 update information from the external is given to, and with the address input a ₂ is given address indicating a storage area to the update information is stored, the upper address and the external is the highest 2 bits of the address The supplied binary switching signal is connected to the input of the decoder 57. Further, among the outputs of the decoder, the upper address is common and the logical value of the switching signal is The output of each pair corresponding to the differences mask data memory 52 _1, 52 _2, are individually connected to the routing memory 53 _1, 53 ₂ and the output memory 54 _1, 54 ₂ of the control input R / W, the pair of memory One of the read control inputs RE is provided with a switching signal directly and the other is provided with the switching signal via an inverter 58.

The operation of this embodiment will be described below. Mask data memories 52 ₁ and 52 ₂ and routing memory 5
With respect to each pair of 3 ₁ and 53 ₂ and output memories 54 ₁ and 54 ₂ , the logical values of the above-mentioned read control inputs are mutually different according to the logical value of the switching signal applied from the outside directly or via the inverter 58. Since they are set to opposite values, one is allowed to read and the other is restricted from reading.

The mask data memory, the routing memory, and the output memory which are permitted to be read in this manner are the address input A of the first port from the search controller 51.
_The address is given to ₁ . Therefore, no matter which of the combination of the mask data memory 52 ₁ , the routing memory 53 ₁ and the output memory 54 _{1 and} the combination of the mask data memory 52 ₂ , the routing memory 53 ₂ and the output memory 54 ₂ can be read, , Claim 1
The route can be efficiently selected in the same manner as the invention described in (1).

On the other hand, the mask data memory, the routing memory and the output memory whose reading is restricted are
The decoder 57 decodes the above-mentioned switching signal and the upper address, and according to the logical value of the binary signal given to the control input R / W, the writing is permitted and the address is synchronized with the address including the upper address. Then, the update information given to the second data input D _i2 is sequentially stored in the storage area indicated by the address.

As described above, according to this embodiment, the duplicated mask data memories 52 ₁ and 52 ₂ , the routing memories 53 ₁ and 53 ₂ and the output memories 54 ₁ and 54 ₂ are operated by the hot standby system, respectively. In parallel with the route selection, the routing table 71, the outgoing route table 81, and the mask table 9 which are the reference for the route selection.
The contents of 1 are surely updated.

Therefore, the router 102 ₁ can flexibly adapt to the addition or modification of the host to be accommodated or the network to be connected without interruption of operation. In the above-described embodiment, the mask data memories 52 ₁ , 5 2,
2 ₂ , the routing memories 53 ₁ and 53 ₂ and the output memories 54 ₁ and 54 ₂ are configured by dual port RAM, but the present invention is not limited to such a configuration, and the search control units 51 and 60 and external These memories may be composed of any element as long as they can be accessed reliably.

Further, in the above-mentioned embodiment, the mask data memories 52 ₁ , 52 ₂ , the routing memories 53 ₁ , 5
3 ₂ and the output memories 54 ₁ and 54 ₂ are all duplicated, but the present invention is not limited to such a configuration, and those of these memories that do not need to be updated during operation are It may be excluded from the object of duplication.

Further, in each of the above-mentioned embodiments, all are adapted to TCP / IP, but the present invention is not limited to such a procedure, and the destination host address is applied to the packet or the like to be stored and exchanged. And a network address indicating the network in which the host is accommodated, it is applicable to any communication procedure. Further, in each of the above-described embodiments, the target of storage exchange is a packet, but the present invention is not limited to such a packet,
It may be a cell or other message as long as it conforms to the communication procedure described above.

Further, although the present invention is applied to the router 102 ₁ in each of the above-described embodiments, the present invention is not limited to such a router, and stores and exchanges based on the above-mentioned communication procedure. If, for example, it is applicable to bridges and hubs as well.

[0058]

As described above, according to the first aspect of the invention, the processing relating to the storage exchange can be simplified.

The invention described in claim 2 simplifies the processing in the same manner as the invention described in claim 1.
In addition, the hardware configuration is simplified. Further, in the invention according to the third aspect, high responsiveness is secured even when the number N of routes that can be outgoing routes is large. Also,
According to the invention described in claim 4, it is possible to flexibly adapt to the addition or modification of the network and the data terminals accommodated in the own station and other stations without interruption of the operation.

Therefore, in the communication system to which these inventions are applied, the scale of hardware and software is suppressed to be small, the cost related to operation is reduced, and the availability and service quality are improved.

[Brief description of drawings]

FIG. 1 is a block diagram showing the principle of the present invention.

FIG. 2 is a diagram showing an embodiment corresponding to the invention described in claims 1, 3, and 4.

FIG. 3 is a diagram showing a configuration of a routing table.

FIG. 4 is a diagram showing a configuration of an outgoing route table.

FIG. 5 is a diagram showing a configuration of a mask table.

FIG. 6 is a diagram showing an embodiment corresponding to the invention described in claim 2.

FIG. 7 is a diagram showing another configuration of a routing table.

FIG. 8 is a diagram showing a detailed configuration of a search control unit.

FIG. 9 is a diagram illustrating a configuration example of a network to which IP connection is applied.

FIG. 10 is a diagram showing a configuration of a network route table.

FIG. 11 is a diagram showing a configuration of a host route table.

FIG. 12 is a diagram illustrating a routing process in a conventional example.

[Explanation of symbols]

 11 storage means 12 exchange means 13,21 route table 14,23,91 mask table 15 output route table 16,25 route selection means 31 update means 51,60 search control unit 52 mask data memory 53,59 routing memory 54 Output memory 55 Masking unit 56,66 Comparator 57 Decoder 58 Inverter 61 D-type flip-flop 62 RS flip-flop 63,67 Selector 64 Register 65 Adder 68 Divider 69 Incrementer 71 Routing table 81 Outgoing route table 100 Network 101 Host Computer 102 Router 111 Network route table 121 Host route table

Claims (4)

[Claims] 1. A storage for storing a message including a network address given from a plurality of routes and indicating a network accommodated for a destination data terminal, and a host address used for identification with other data terminals. Means and an exchange means for storing and exchanging the messages accumulated by the accumulating means, wherein the exchanging means includes a host address for a data terminal accommodated in its own station and a logical network to which the data terminal belongs. And a network address that stores a network address indicating that the network is connected via another station, a route table in which a pseudo host address and a network address indicating the network are stored in advance, and a route table common to the route table. Under addressing, of the host address and network address stored in the route selection table, for the data terminal accommodated in its own station, A mask table in which a mask pattern indicating only a network address is stored in advance for connected networks, and the logical network and the logical network for the plurality of routes under the same addressing as the route table. An outgoing route table in which route identification information indicating a route connected to a network connected via another station is stored in advance, and each of the messages stored in the storing means under the addressing Is searched for in the route table using the logical product of the included network address and host address and the mask pattern stored in the mask table as a key, and is equal to the logical product of the plurality of routes. The route identification information stored in the output route table corresponding to the network address and the host address is obtained, and the route indicated by the route identification information is set as the output route. Node device; and a route selection means for constant. 2. A storage for storing a message including a network address given from a plurality of routes and indicating a network accommodated for a destination data terminal, and a host address used for identification with other data terminals. Means and a switching means for storing and exchanging the messages accumulated by the accumulating means, wherein the exchanging means includes a host address indicating a data terminal accommodated in its own station and a logical network to which the data terminal belongs. Of the plurality of routes in the ascending or descending order of the binary number indicated by the combination of the network address indicating the network address and the network address indicating the network connected via the other station. A route table in which control information indicating the presence or absence of a route to these networks and route identification information indicating the route are stored in advance, and a host address stored in the route table. Of the network address and the network address, both of the data terminals accommodated in the local station, and a mask table in which a mask pattern indicating only the network address is stored in advance for the network connected via the other station, and the storage means. For each message stored in
While the mask pattern stored in the mask table is scanned, the mask pattern obtained under the scan is ANDed with the network address and host address included in the message, and the logical product is compared with the above A route selection means for determining route identification information stored together with control information indicating that there is a route in the route table, and selecting the route indicated by the route identification information as an output route. Node device. 3. The node device according to claim 1, wherein storage areas for storing host addresses and network addresses are allocated to the route table in ascending or descending order of binary numbers indicated by these combinations, The node device, wherein the route selection means performs a search based on a binary search method. 4. The node device according to claim 1, wherein all or part of a route table, a mask table, and an outgoing route table are made redundant, and a route selecting means is provided. The route table, the mask table and the output route table, including means for limiting the reference target to those that are redundant and are the current system under the system configuration, the route table, the A node device comprising: a mask table and an output route table, which are provided with updating means for updating a redundant system under the system configuration, which is redundant.