Network topology generation method and node

The present invention relates to a network topology generation method in which a new node participates in a network composed of a plurality of nodes. The present invention also relates to a node that newly participates in a network composed of a plurality of nodes.

A conventional network topology generation method (the method used by Gnutella) will be described with reference to FIGS. 1 to 5. Specifically, the operation in which the node 105 newly joins the network including the nodes 101 to 104 will be described.

First, as shown in FIG. 1, the node 105 establishes a connection with a node 101 that knows an IP address or a URL from among a plurality of nodes 101 to 104 that make up the network.

Second, as shown in FIG. 2, node 105 sends a Ping message to node 101 containing the IP address of node 105.

Third, as shown in FIG. 3, the node 101 returns a Pong message including the IP address of the node 101 to the node 105, and forwards a Ping message including the IP address of the node 105 to the nodes 102 to 104.

Fourth, as shown in FIG. 4, each node 102 to 104 returns a Pong message including its IP address to the node 105.

By repeating the above procedure, the node 105 can acquire the IP address of the node within the range specified in the TTL (Time To Live) field of the Ping message.

Fifth, as shown in FIG. 5, the node 105 refers to the IP address included in the received Pong message and establishes a connection with each of the nodes 101 to 104 constituting the network.

In this way, node 105 can newly join the network composed of nodes 101 to 104.

As described above, in the conventional network topology generation method, the new node 105 is configured to randomly join the network by using the Ping message and the Pong message.

However, in the conventional network topology generation method, when a new network topology is generated, the network condition of the physical layer is not taken into consideration, so that the network delay can be considerably large even between adjacent nodes in the logical layer. There is a problem that the data transfer efficiency may decrease in the newly generated network.

<patcit num="0001"><text>Japanese Unexamined Patent Publication No. 2003-304277</text></patcit> Therefore, the present invention has been made in view of the above points, and by considering the network condition of the physical layer, the network delay is suppressed on average and to the minimum when a new network topology is generated. It is an object of the present invention to provide a network topology generation method and a node capable of the above.

The first feature of the present invention is a node that newly joins a network composed of a plurality of nodes, and has a virtual connection establishment unit that establishes a virtual connection with the plurality of nodes and each virtual connection. By establishing a connection to the average metric value calculation unit that calculates the average metric value of the route to the plurality of nodes via the node and the node for which the virtual connection that minimizes the average metric value of the route is established. The gist is to have a connection establishment unit that participates in the network.

According to such an invention, the connection establishment unit establishes a connection to a node in which a virtual connection is established so that the average metric value calculated in consideration of the network condition of the physical layer is minimized. In generating the network topology, the network delay can be suppressed on average and to the minimum.

In the first feature of the present invention, an acquisition unit for acquiring connection information between nodes related to adjacent nodes of the arbitrary node is further provided from an arbitrary node in the network, and the average metric value calculation unit is the said. It may be configured to calculate the average metric value using the connection information between nodes.

In the first feature of the present invention, the node-to-node connection information includes a node ID for identifying the adjacent node, a metric value of a route between the arbitrary node and the adjacent node, and the adjacent node. It may be configured to include the number of adjacent nodes.

In the first feature of the present invention, the metric value may be configured to include at least one of hop count, network bandwidth, communication cost, delay, load, MTU, and reliability.

In the first feature of the present invention, even if the acquisition unit is configured to notify the arbitrary node of the type of metric value or combination of metric values to be included in the inter-node connection information. Good.

The second feature of the present invention is a network topology generation method in which a new node participates in a network composed of a plurality of nodes, in which the new node establishes a virtual connection with the plurality of nodes. Then, a step is established in which the new node calculates the average metric value of the route to the plurality of nodes via each virtual connection, and a virtual connection is established in which the new node minimizes the average metric value of the route. The gist is to have a process of joining the network by establishing a connection to the node.

<figref num="1">FIG. 1 is a diagram showing an operation in which a node 105 establishes a connection with a node 101 in the prior art.</figref><figref num="2">FIG. 2 is a diagram showing an operation in which the node 105 sends a Ping message to the node 101 in the prior art.</figref><figref num="3">FIG. 3 is a diagram showing an operation in which a node 101 transmits a Pong message to a node 104 and a Ping message is transmitted to each of the nodes 102 to 104 in the prior art.</figref><figref num="4">FIG. 4 is a diagram showing an operation in which nodes 102 to 104 send a Pong message to node 101 in the prior art.</figref><figref num="5">FIG. 5 is a diagram showing an operation in which the node 101 establishes a connection with the nodes 102 to 104 in the prior art.</figref><figref num="6A">FIG. 6A is a functional block diagram of the node X according to the embodiment of the present invention.</figref><figref num="6B">FIG. 6B is a functional block diagram of node A according to an embodiment of the present invention.</figref><figref num="7">FIG. 7 is a flowchart showing an operation in which the node X according to the embodiment of the present invention newly joins the network.</figref><figref num="8">FIG. 8 is a diagram showing an operation in which node X according to an embodiment of the present invention acquires node-to-node connection information from node A.</figref><figref num="9">FIG. 9 is a diagram showing an example of node-to-node connection information acquired by the node X according to the embodiment of the present invention.</figref><figref num="10">FIG. 10 is a diagram showing an operation in which node X according to an embodiment of the present invention establishes a virtual connection with nodes A to D.</figref><figref num="11">FIG. 11 is a diagram showing route information from node X to nodes A to D via a virtual connection established between node X and node D according to the embodiment of the present invention.</figref><figref num="12">FIG. 12 is a diagram showing route information from node X to nodes A to D via a virtual connection established between node X and node A according to the embodiment of the present invention .</figref><figref num="13">FIG. 13 is a diagram showing route information from node X to nodes A to D via a virtual connection established between node X and node B according to the embodiment of the present invention.</figref><figref num="14">FIG. 14 is a diagram showing route information from node X to nodes A to D via a virtual connection established between node X and node C according to an embodiment of the present invention.</figref><figref num="15">FIG. 15 is a diagram showing a calculation formula in which node X according to an embodiment of the present invention calculates an average metric value of a route from nodes A to D via each virtual connection.</figref><figref num="16">FIG. 16 is a diagram showing an example in which node X according to an embodiment of the present invention calculates an average metric value of a route from nodes A to D via each virtual connection.</figref><figref num="17">FIG. 17 is a diagram showing an operation in which a node X according to an embodiment of the present invention establishes a connection with a node D.</figref>

(Configuration of a node that realizes the network topology generation method according to the first embodiment of the present invention) Hereinafter, the configuration of the node that realizes the network topology generation method according to the first embodiment of the present invention will be described with reference to FIGS. 6A and 6B. In the present embodiment, node X is configured to be able to newly participate in a network including a plurality of nodes A to D.

As shown in FIG. 6A, the node X according to the present embodiment includes the node-to-node connection information acquisition unit 11, the virtual connection establishment unit 12, the average metric value calculation unit 13, the connection establishment unit 14, and the metric value specification unit. It has 15 and.

The inter-node connection information acquisition unit 11 acquires inter-node connection information related to adjacent nodes (for example, nodes B to D) of the arbitrary node from any node (for example, node A) in the network. .. The inter-node information includes a "node name (node ID)" for identifying an adjacent node, a "node address (for example, IP address)" of the adjacent node, and an arbitrary node and the adjacent node. Includes the "metric value" of the route and the "number of nodes" adjacent to the adjacent node. In addition, the "metric value" includes at least one of hop count, network bandwidth, communication cost, delay, load, MTU, and reliability.

Here, the number of hops indicates the number of hops in the physical layer, that is, the number of hops of a router or the like in the link established with the node. The network bandwidth indicates the communication bandwidth (for example, 64 kbps, etc.) that can be used in the link established with the node. The communication cost indicates the communication charge of the link established with the node. The delay indicates the propagation delay time in the link established with the node. The load indicates the usage status of the link established with the node (for example, 50%). The MTU indicates the minimum transfer unit used in the link established with the node. Reliability indicates the failure rate in the link established with the node.

The inter-node connection information acquisition unit 11 notifies the type of the metric value (or a combination of metric values) specified by the metric value specification unit 15 when acquiring the inter-node information from any node in the network. It may be configured in.

The virtual connection establishment unit 12 establishes a virtual connection with a plurality of nodes A to D by referring to the node address in the node-to-node connection information acquired by the node-to-node connection information acquisition unit 11.

The average metric value calculation unit 13 calculates the average metric value of the route to a plurality of nodes via each virtual connection by using the inter-node connection information acquired by the inter-node connection information acquisition unit 11. The specific calculation method of the average metric value will be described later.

The connection establishment unit 14 establishes a connection to the node on which the virtual connection that minimizes the average metric value of the route is established.

The metric value specification unit 15 specifies the type of metric value (or combination of metric values) that should be included in the inter-node connection information acquired from any node when node X newly joins the network. is there. When a predetermined metric value is not specified by the metric value specifying unit 15, the inter-node connection information provided by any node includes the metric value (or a combination of metric values) set by default.

As shown in FIG. 6B, the node A according to the present embodiment includes the node-to-node connection information acquisition unit 31, the node-to-node connection information storage unit 32, the virtual connection establishment unit 33, and the node-to-node connection information providing unit 34. It has a connection establishment unit 35.

The inter-node connection information acquisition unit 31 acquires inter-node connection information related to the adjacent node from the adjacent nodes (for example, nodes B to D) adjacent to the node X in the network. The metric value in the link between each node is updated as appropriate.

For example, the inter-node connection information acquisition unit 31 may be configured to periodically acquire the update result of the inter-node connection information by broadcasting the update notification packet to all the nodes in the network.

In addition, the inter-node connection information acquisition unit 31 is configured to periodically acquire the update result of the inter-node connection information by transmitting an update notification packet to the range in which the TTL (Time To Live) is set. May be good.

The inter-node connection information storage unit 32 stores the inter-node connection information acquired by the inter-node connection information acquisition unit 31.

The virtual connection establishment unit 33 establishes a virtual connection with the node X in response to the virtual connection establishment request from the node X.

The inter-node connection information providing unit 34 acquires the inter-node connection information related to the adjacent node adjacent to the node A from the inter-node connection information storage unit 32, and connects to the node X established by the virtual connection establishing unit 33. The connection information between the nodes is provided to the node X via the virtual connection.

When the node X notifies the type of the metric value (or the combination of the metric values), the node-to-node connection information providing unit 34 provides the inter-node connection information including the metric value (or the combination of the metric values). It may be configured as follows.

Further, when the node X does not notify the type of the metric value (or the combination of the metric values), the node-to-node connection information providing unit 34 sets the metric value (or the combination of the metric values) set by default. It may be configured to provide inter-node connection information including.

The connection establishment unit 35 establishes a virtual connection with the node X in response to the connection establishment request from the node X.

(Operation of the network topology generation method according to this embodiment) The operation of the network topology generation method according to the present embodiment will be described with reference to FIGS. 7 to 17. Specifically, the operation when node X newly joins the network including nodes A to D will be described.

As shown in FIGS. 7 and 8, in step S1, the node-to-node connection information acquisition unit 11 of the node X acquires the node-to-node connection information managed by the node A from the node A. Here, the node-to-node connection information acquisition unit 11 of the node X may be configured to notify the type of the metric value (or the combination of the metric values) to be included in the inter-node connection information to be acquired.

FIG. 9 shows the connection information between nodes managed by node A in this embodiment. As shown in FIG. 9, the adjacent nodes of node A are nodes B to D. The node address of node B is "BIP", the node address of node C is "CIP", and the node address of node D is "DIP". Also, the metric value between node A and node B is "2", the metric value between node A and node C is "3", and the metric value between node A and node D is It is "2". The number of nodes adjacent to node B is "2", the number of nodes adjacent to node C is "2", and the number of nodes adjacent to node D is "3".

As shown in FIGS. 7 and 10, in step S2, the virtual connection establishment unit 12 of the node X virtualizes between the nodes A and D based on the node address included in the acquired node-to-node connection information. Establish a connection.

In step S3, the average metric value calculation unit 13 of node X from node X to node A to node A to node X via each virtual connection based on the metric value and number of nodes included in the acquired node-to-node connection information. Calculate the average metric value of the route to each of D.

Specifically, the average metric value is calculated as follows. The metric value of virtual connection # 1 established between node X and node D is "1", and the metric value of virtual connection # 2 established between node X and node A is "5". The metric value of virtual connection # 3 established between node X and node B is "3", and the metric value of virtual connection # 4 established between node X and node C is "3". It is assumed that the person is "1".

FIG. 11 correlates the "metric value" in the routes # A1 to # D1 from node X to each of nodes A to D via virtual connection # 1 and the "number of nodes" adjacent to each node A to D. Shows route information.

Further, FIG. 12 shows the metric value in the routes # A2 to # D2 from the node X to each of the nodes A to D via the virtual connection # 2 and the number of nodes adjacent to each node A to D. Indicates the route information associated with.

Further, FIG. 13 shows the "metric value" in the routes # A3 to # D3 from node X to each of nodes A to D via virtual connection # 3 and the "number of nodes" adjacent to each node A to D. Indicates the route information associated with.

Further, FIG. 14 shows the metric value in the routes # A4 to # D4 from the node X to each of the nodes A to D via the virtual connection # 4, and the number of nodes adjacent to each node A to D. Indicates the route information associated with.

The average metric value calculation unit 13 of node X uses the route information shown in FIGS. 11 to 14 and uses the calculation formula shown in FIG. 15 to transfer from node X to node i via the virtual connections # 1 to # 4. Calculate the average metric value Vi of the route to be reached. In the formula shown in FIG. 15, n indicates the total number of nodes belonging to the network, VMi indicates the metric value of the route from node X to node i, and Ni indicates 1 for the number of adjacent nodes of node i. Shows the added value. Here, it is assumed that node A corresponds to node 1, node B corresponds to node 2, node C corresponds to node 3, and node D corresponds to node 4.

In FIG. 16, in the present embodiment, the average metric value calculation unit 13 of the node X refers to the route information shown in FIGS. 11 to 14, and the node X to the node via the virtual connections # 1 to # 4. An example of how to calculate the average metric value of the route reaching each of A to D is shown.

As shown in Fig. 16, the average metric value of the route from node X to each of nodes A to D via the virtual connection # 2 established between node X and node A is "78/11". Yes, the average metric value of the path that node X reaches each of nodes A to D from node X via the virtual connection # 3 established with node B is "59/11", and node X has The average metric value of the route from node X to each of nodes A to D via virtual connection # 4 established with node C is "50/11", and node X is between node D and node D. The average metric value of the route from node X to each of nodes A to D via the virtual connection # 1 established in is "40/11".

Based on this result, in step S4, as shown in FIG. 17, the connection establishment unit 14 of the node X establishes the virtual connection # 1 having the minimum average metric value (40/11) of the above-mentioned route. By establishing a connection to the created node D, a new member joins the network. As a result, the network topology is changed. That is, the node X can communicate with all the nodes in the network including the nodes A to D and the like via the virtual connection # 1.

(Action / effect of network topology generation method according to this embodiment) According to the network topology generation method according to the present embodiment, the virtual connection # 1 is established by the connection establishment unit 14 of the node X so that the average metric value calculated in consideration of the network condition of the physical layer is minimized. Since the connection is established with the node D, the network delay can be suppressed on average and to the minimum when a new network topology is generated.

Although the present invention has been described in detail with reference to Examples, it is clear to those skilled in the art that the present invention is not limited to the Examples described in the present application. The apparatus of the present invention can be implemented as a modified or modified mode without departing from the spirit and scope of the present invention determined by the description of the claims. Therefore, the description of the present application is for the purpose of exemplification and does not have any limiting meaning to the present invention.

As described above, according to the present invention, when a new network topology is generated by considering the network condition of the physical layer, the network topology that can suppress the network delay on average and to the minimum can be suppressed. A method of generating and a node can be provided.