JP2009260872A - Method for controlling topology of overlay network, system, and program - Google Patents

Abstract

A scalable, high-quality and highly reliable overlay network is configured to efficiently improve end-to-end communication quality and reliability.
As a procedure for determining a connection destination of a new participating node that newly participates in an overlay network as an overlay node, identification information of each existing node already participating in the overlay network as an overlay node and the existing A storage processing procedure (step S301) for storing in the storage device the list information described in association with the degree that is the number of connection destinations of the node, and the existing node that is the connection destination of the new participating node is stored in the storage device A decision processing procedure (step S302) for making a decision with reference to the list information, and the decision processing procedure in step 302 is a probability distribution function defined in advance for the order of each existing node described in the list information. Including a procedure for determining an existing node to which the new participating node is connected with a probability according to .
[Selection] Figure 3

Description

  The present invention relates to a technology for improving end-to-end communication quality and reliability in the Internet, and in particular, communication using an overlay network logically formed on an IP (Internet Protocol) network. The present invention relates to a technique suitable for efficiently improving end-to-end communication quality and reliability in a path.

  The Internet, which represents IP networks, has been developed and spread to accommodate various applications. Recently, it is sensitive to VoIP (Voice over IP) and QoS (Quality of Service) typified by streaming. The containment of time applications etc. is also developing rapidly.

  Along with this, it is an important issue to realize technology ("end-to-end QoS management technology") on the Internet to avoid end-to-end congestion and improve quality. .

  However, there are the following problems in realizing such a technique.

  (1) The Internet has already become a social infrastructure, and it is difficult to expand new functions at the network layer that greatly change the existing network structure.

  (2) The Internet is formed by a plurality of ASs (Autonomous Systems) having different management entities, and it is difficult to extend new functions to all ASs simultaneously.

  Under these circumstances, for example, a QoS management technique using an overlay network described in Non-Patent Document 1 is attracting attention as a promising technique capable of improving end-to-end QoS without changing a lower network layer. .

  As described in Non-Patent Document 2, for example, an overlay network is a network that uses an existing link and forms a logical (virtual) link in an upper layer according to the purpose.

  The basic concept of QoS management by such an overlay network is illustrated in FIG. Consider a case where communication is desired from the node 81a to the node 81c in the network 84 (described as “IP-NW” in the figure) shown in FIG.

  At this time, when the data is directly transferred from the node 81a to the node 81c (the node 81a → the IP router 82a → the IP router 82d → the IP router 82e → the node 81c), the data is temporarily transferred from the node 81a to the node 81b. When the delay time is smaller through the detour route (node 81a-> IP router 82a-> IP router 82b-> IP router 82c-> node 81b-> IP router 82c-> IP router 82e-> node 81c) of transferring from the node to the node 81c (E.g. due to internet interdomain routing policy).

  At this time, each node 81a, 81b, 81c is used as an overlay node, and a route (overlay node 81a →) represented by a solid line arrow in FIG. 8 is used using the overlay network 83 formed by the overlay nodes 81a, 81b, 81c. If the traffic can be bypassed from the overlay node 81b to the overlay node 81c), QoS can be improved.

  In fact, Non-Patent Documents 3, 4, and 5 show that there are many detour routes as described above based on actual measurements.

  However, the results of Non-Patent Document 3 and Non-Patent Document 5 are the evaluations when the topology of the overlay network is a full mesh and the ideal communication path calculation is performed using quality information measured between all overlay nodes. Therefore, the decrease in scalability (system extensibility) when the total number of overlay nodes increases is not considered.

  That is, when the total number of overlay nodes is large, there is a problem that it is difficult to configure a network with a full mesh from the viewpoint of scalability.

  On the other hand, as a technique for determining and controlling the topology in the overlay network instead of the full mesh, there is a technique that considers the topology of the IP layer.

  This is because even if the nodes are connected with one hop on the overlay network, the delay time increases if it seems to have many hops in the IP layer, which is not desirable from the viewpoint of high quality. .

  Although there are such studies, on the overlay network configured in this way, for example, when a node leaves, there is a possibility that connectivity cannot be maintained, and the topology is configured taking into account high reliability There is a need to.

L. Zhi and P.M. Mohapra, “QRON: QoS-aware routing in overlay net-works,” IEEE J. MoI. Select. Areas Commun. , Vol. 22, pp. 29-40, January 2004. WIDE Project, “Integrated Distributed Environment with Overlay Network,” WIDE Project Research Report, Part 17, 2002. Kamei, Kawahara, “Traffic engineering by end-host overlay network and its effectiveness,” Shingaku Sodai, BS-5-3, 2004. S. Rewaskar and J.H. Kaur, “Testing the Scalability of overlay Routing,” Proc. PAM 2004. April 2004. S. Banerjee, T .; G. Grifin and M.M. Pias, “The Interdomain Connectivity of PlanetLab Nodes,” Proc. PAM 2004, April 2004.

  The problem to be solved is that the conventional technology for determining and controlling the topology of the overlay network in consideration of the IP layer topology, for example, cannot maintain connectivity when a node leaves the overlay network. This is a point that cannot maintain high reliability.

  An object of the present invention is to solve these problems of the prior art, configure a scalable high-quality and highly reliable overlay network, and efficiently improve end-to-end communication quality and reliability.

In order to achieve the above object, in the present invention, when determining a connection destination of a new participation node that newly participates in an overlay network as an overlay node, by dynamically controlling a reference for the new participation node to connect to an existing node. By making the resulting network topology have the characteristic of scale-freeness, the network is made highly fault-tolerant. For example, in an overlay network that is a logical network constructed by several overlay nodes connected to the Internet, an already participating overlay node j is connected to k _j overlay nodes (degree k _j ), and A node newly participating in the overlay network determines a connection destination node with a probability corresponding to an arbitrary probability distribution function P (k _j ) defined for the order k _j . As described above, when adding a new node, it is known that if a connection is made in proportion to the degree k of an existing node, the scale becomes free. In the present invention, this characteristic is used, and the characteristic of the network depending on the topology can be controlled by a node selection algorithm and parameters at the time of connection.

  According to the present invention, it is possible to configure a high-quality overlay network that is scalable and excellent in fault tolerance without configuring a network with a full mesh between all nodes.

  The best mode for carrying out the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram illustrating a configuration example of a connection candidate management server used for topology control of an overlay network according to the present invention, and FIG. 2 is an explanatory diagram illustrating a configuration example of an overlay network that performs topology control according to the present invention. It is.

  In FIG. 2, 1 is a connection candidate management server constituting the topology control system of the overlay network according to the present invention, 20a to 20h are existing overlay nodes, and particularly super nodes constituting the super node network layer in the overlay network, 21a to 21k is an existing node that constitutes a general node in the overlay network, and 22 is a new participating node that newly connects and participates in the overlay network.

  The connection candidate management server 1, the super nodes 20a to 20h, the existing nodes 21a to 21k, and the new participation node 22 are input from a CPU (Central Processing Unit), a main memory, a display device such as a CRT or LCD, a keyboard, a mouse, or the like. The computer is composed of an external storage device such as an HDD and an HDD, and after the program or data recorded in the storage medium such as a CD-ROM is installed in the external storage device via the optical disk drive device or the like, the external storage device The topology of the overlay network according to the present invention is controlled by reading into the main memory and processing by the CPU.

  For example, the connection candidate management server 1 includes, as means for executing programmed computer processing, each processing unit of a connection destination determination unit 1a, an order management unit 1b, and a coordinate holding unit 1c as shown in FIG.

  The basic concept of topology control of the overlay network according to the present invention will be described first.

  In this example, the new participating node 22 dynamically controls the criteria for connecting to the existing nodes 21a to 21k, so that the resulting network topology has the characteristic of scale-freeness, thereby providing fault tolerance. Trying to make a high network.

  A scale-free network is a distribution related to the degree of a node (the number of nodes adjacent to that node) (that is, the existence probability p (k) of a node having degree k) is “k ^ {− γ}”. When we follow the power law, we call it scale free.

  Such a network is described, for example, in Reference Document 1 (“R. Albert et al 1,“ Error and attack tolerance of complex networks, ”Nature, vol. 406, pp. 378-382, 2000.). In particular, it is highly robust against network failures.

  In a network with a scale-free topology, even if some percentage of all nodes go down, the connection between nodes can be maintained due to the existence of alternative paths, and the average path length (average shortest distance) of the entire system changes little. do not do.

Utilizing such basic characteristics, in this example, in an overlay network that is a logical network constructed by, for example, several overlay nodes connected to the Internet, an already participating overlay node j is k _j overlays. It is assumed that the node is connected to the node, and the node participating in the overlay network determines the connection destination node with a probability corresponding to an arbitrary probability distribution function P (k _j ) defined for the order k _j .

  As described in Reference Document 1 above, when a new node (22) is added, if it is connected in proportion to the degree k of the existing nodes (21a to 21k), the scale becomes free. It is known.

  First to tenth examples for performing topology control of the overlay network according to the present invention using such characteristics will be described below.

  In the first example, the characteristics of the network depending on the topology are controlled by the node selection algorithm and parameters at the time of connection using the above-described characteristics. Note that here, only when a new participating node joins, the connection destination is changed by a similar procedure for a certain period or for several existing nodes according to the network status. You may let them.

  Further, in the second example, each of the existing nodes 21a to 21k that have already participated runs as a connection candidate list with a probability p every fixed period, and this is indicated together with the order of the node. 1, when the new participation node 22 participates, the new participation node 22 obtains a connection candidate list from the connection candidate management server 1, and from among them, m connection destination nodes are obtained with a probability corresponding to the order. select.

  This is because, in the first example, the order information of all nodes is required. However, as the network scale becomes large, a problem arises in the scale property. Therefore, not all nodes but only some of them are candidates. Guarantee sex.

  Further, in the third example, instead of randomly running with probability p as in the second example, the existing nodes 21a to 21k are configured according to resource conditions such as their own bandwidth and CPU usage rate. If there is a vacancy, the candidate is established as a connection candidate. This facilitates connection to a more stable node.

  Further, in the fourth example, a plurality of connection candidate lists are prepared, and each of them is managed by a plurality of connection candidate management servers (1). After selecting the list and determining the list, the connection destination node is determined according to the same procedure as in the second example. In this way, even if a failure occurs in the connection candidate management server (1), information can be obtained from other servers.

  Further, in the fifth example, the new participation node 22 selects m ′ connection destination nodes according to any of the first to fourth examples, and from among the m ′ pieces, the new participation node 22 In this order, m are selected in order from the one having the best quality metric (delay time, packet loss rate, throughput), and the m are determined as connection destination nodes. This makes it possible to consider the quality while considering a scale-free network (= a network with excellent fault tolerance) in consideration of the order.

  Further, in the sixth example, instead of installing the connection candidate management server 1 as a central management server as in the second example, first, an inquiry about the degree is made to any of the existing nodes 21a to 21k that have already participated. The existing node that sent the message and received this inquiry message transfers the inquiry message to its adjacent node, and implements it within the range of a certain number of hops from the new participating node 22. The node that has received the inquiry message returns its own order to the new participating node 22 as the inquiry source. The new participating node 22 that has received it determines the connection destination according to the degree from the node group that has returned.

  In the sixth example, the connection candidate management server 1 is necessary in the second example described above. However, the centralized management by such a server is not performed, and connection candidates are searched autonomously and distributed. Overcoming bottleneck avoidance and scale limitations due to management.

  Further, in the seventh example, in the sixth example, each existing node transmits information on the resource in addition to the information on the degree to the new participating node 22, and the new participating node 22 receives the order and Select m 'connection destination nodes according to the resource status, and select m in descending order of the quality metric (delay time, packet loss rate, throughput) with the new participating node. These are extracted and m are determined as connection destination nodes.

  In the eighth example, a distributed hash table used as a technology related to P2P is used, and an existing node registers its degree and resource information as an index in the distributed hash table, The new participating node 22 searches the distributed hash table for an existing node having a certain degree and resource information, performs this for a plurality of orders and resource information, and among the obtained node group. Then, m 'number of connection destination nodes is selected, and m pieces are extracted from the m' pieces in descending order of quality metrics (delay time, packet loss rate, throughput) with the newly participating node 22. , M are determined as connection destination nodes.

  As described in the sixth example, instead of extracting the order information on the basis of flooding, the order information is efficiently distributed and managed using a technique called a distributed hash table. As for P2P technology including such a distributed hash table, for example, Non-Patent Document 2 and Reference Document 2 (“Fujiwara Hiroshi, Internet Mathematical Sciences 13th-P2P Technology and the Future” Outlook-January 25, 2007, Graduate School of Mathematical Sciences, The University of Tokyo, Information Theory 901-35 Lecture Materials: http://www.ms.u-tokyo.ac.jp/lecture/2006/901-35/2007 -01-25.pdf) and Reference 3 ("Hideki Sunahara, Satoshi Yuya Peer to Peer: Basic knowledge and network operation technology for the full P2P application era, Nara Institute of Science and Technology, Information Science Center, http: /// www.jpnic.net/ja/materials/iw/20 06 / processedings / T3-1.pdf "and the like.

  Further, in the ninth example, each cluster is composed of a plurality of clusters each composed of a plurality of super nodes (20a to 20h in FIG. 2) and a plurality of general nodes (21a to 21k in FIG. 2) connected to each super node. A connection destination in the case of newly joining a new participating node as an overlay node in the super overlay network is determined. In addition, regarding the P2P technology including such super nodes and clusters, Reference Documents 2 and 3 and Reference Document 4 described above (“Eng Keong Lua“ Network-aware SuperPeers-Peers Geometric Overlay Network, ”Proc. IEEE 200 PIC and Grid Networking Track, Hawaii, USA, August 13-16, 2007. ") and the like.

  In other words, when an existing node is divided into a plurality of clusters, each cluster has two types of super nodes and many other general nodes, and the super nodes between the clusters are connected by a full mesh. To do. The super node knows the order and resource information of the general node in the cluster to which the super node belongs, and the new participating node belongs to one of the clusters. At this time, the order of the general node in the cluster and Resource information is obtained from a super node, m ′ number of connection destination nodes are selected using the degree, and quality metrics (delay time, packet loss rate, throughput) with the newly participating node are selected from the m ′ number. ) Are extracted in order from the best), and m are determined as connection destination nodes.

  In the tenth example, when the new participation node 22 participates, a connection destination node is selected according to the order, and at the same time, a random connection is made regardless of the order. As a result, not only a scale-free network but also a random network can be used. It has been pointed out that a scale-free network is excellent in fault tolerance, but is vulnerable to attacks such as DDoS (Distributed Denial of Devices attack). On the other hand, a random network is inferior in fault tolerance, but is strong against attacks. Therefore, by using both together, it becomes possible to make the network resistant to faults and attacks.

  Hereinafter, in a situation where the existing nodes 21a to 21k in the overlay network shown in FIG. 2 are logically connected to each other, when the new participation node 22 participates in the overlay network, the new participation node 22 An operation when the connection candidate management server 1 shown in FIG. 1 is inquired to determine a connection destination node from the participating nodes 21a to 21k will be described.

  As shown in FIG. 1, the connection candidate management server 1 first receives an inquiry from the new participation node 22 at the connection destination determination unit 1a.

The connection destination determination unit 1a reads the order k _j existing participating nodes j which is stored and managed in order management section 1b, and selecting m number of the connection candidate with a probability that is proportional to the read order k _j, connected A candidate list is generated, and the generated connection destination candidate list is returned to the new participating node 22 as the inquiry source.

  The new participation node 22 that has received the connection candidate list from the connection destination determination unit 1a connects to the m connection destination nodes.

  On the other hand, each of the existing nodes 21a to 21k is established as a connection candidate list with a probability p every fixed period and notifies the degree management unit 1b in the connection candidate management server 1 together with the degree.

  Further, each of the existing nodes 21a to 21k notifies the connection destination determination unit 1a in the connection candidate management server 1 of the connection destination change with a probability p ′ every fixed period, and the connection candidate management receiving the notification The connection destination determination unit 1a in the server 1 returns a connection candidate list in the same manner as at the time of a new participation node, and the existing node changes the connection destination.

  Moreover, the coordinate holding | maintenance part 1c is prepared in the connection candidate management server 1, and each existing participating node 21a-21k runs as a connection candidate list | wrist with probability p for every fixed period, and a degree is ahead of it. Is notified to the degree management unit 1b, and at the same time, the coordinates of the white body are notified to the coordinate holding unit 1c.

  Here, it is assumed that the node has a coordinate position by mapping each node on the coordinate space using a distance (RTT (Round Trip Time), throughput, etc.) regarding the quality between the nodes. In addition, the technique described in the above-mentioned reference literature 4 can be used for such a coordinate position determination.

  At this time, the connection destination determination unit 1a in the connection candidate management server 1 first selects m ′ connection destination nodes using the degree information, and uses the coordinate position from among the m ′ new connection nodes. M pieces are extracted in order from the one having the best quality metric (delay time, packet loss rate, throughput) with the participating nodes, the m pieces are determined as connection destination nodes, and returned to the new participating node 22.

  The topology control processing operation of the overlay network according to the present invention including such a procedure and other procedures will be described with reference to FIGS.

  FIG. 3 is a first flowchart showing a procedure example of the overlay network topology control method according to the present invention, and FIG. 4 is a second flowchart showing another procedure procedure of the overlay network topology control method according to the present invention. FIG. 5 is a third flowchart showing another procedure example of the overlay network topology control method according to the present invention, and FIG. 6 is a flowchart showing another procedure example of the overlay network topology control method according to the present invention. FIG. 7 is a fifth flowchart showing another example of the procedure for controlling the topology of the overlay network according to the present invention.

  In the example (I) illustrated in FIG. 3, as the processing execution procedure of the programmed computer, the identification information of each existing node that has already participated in the overlay network as an overlay node and the number of connection destinations of the existing node are included. A storage processing procedure (step S301) for storing the list information described in association with the degree in the storage device, and an existing node as a connection destination of the new participating node are determined with reference to the list information stored in the storage device. A decision processing procedure (step S302), and the decision processing procedure in step 302 includes the new participation with a probability according to a probability distribution function defined in advance for the degree of each existing node described in the list information. Includes a procedure for determining an existing node to which a node is to be connected.

  Further, in the example (II) shown in FIG. 4, as a programmed computer processing procedure, for each existing node that has already joined the overlay network as an overlay node, the identification information of the existing node and A transmission procedure (step S401) for transmitting a message for inquiring the order that is the number of connection destinations of the existing node and a predetermined number of hops, and the existing node that has received the message and the number of hops received the message and the number of hops. Is transferred to an adjacent existing node (step S402), and a reply procedure (step S403) is sent back from each existing node that has received the message to each newly participating node with identification information and the order of each existing node. ) And repeat this forwarding procedure for each existing node within the range of hops In order (step S404), the new participating node generates list information in which the identification information and the degree of the existing node received from each existing node are associated with each other, and stores the list information in the storage device (step S405). And a determination processing procedure (step S406) for determining an existing node as a connection destination of the local node with reference to the list information stored in the storage device, and the determination processing procedure in step S406 is included in the list information. It includes a procedure for determining an existing node to be a connection destination of a new participating node with a probability corresponding to a probability distribution function defined in advance for the degree of each existing node described.

  As an example (III), in the example (II) shown in FIG. 4, each existing node uses the resource usage information including the bandwidth usage rate and CPU usage rate of its own device together with the identification information and the order for the new participating node. The procedure for returning the rate is executed, and the new participating node performs the connection destination determination process according to the determination process procedure for the existing node that has returned the resource usage rate better than a predetermined threshold value. It can be done.

  Further, as an example (IV), in the example (II) shown in FIG. 4, an existing node registers its own identification information, degree, resource usage rate including bandwidth usage rate and CPU usage rate as an index in the distributed hash table. The new participating node searches the distributed hash table to extract existing nodes having a plurality of predetermined orders and resource information, and executes the above determination processing procedure for each extracted existing node. It is also possible to select an existing node as a connection destination.

  In the example (V) shown in FIG. 5, as a programmed computer processing procedure, super nodes (20a to 20h in FIG. 2) exist as general nodes (21a to 21k in FIG. 2) in the cluster to which they belong. The procedure for storing the identification information of each existing node and the order that is the number of connection destinations of the existing node in the storage device (step S501), and the new participating node from the super node in the cluster to which it belongs, A determination processing procedure (step S502) for acquiring identification information and order of each existing node in the cluster, and determining an existing node to which the local node is connected using the acquired order and identification information; and The determination processing procedure in step S502 is a probability distribution function defined in advance for the degree of each existing node described in the list information. Including the procedure for determining the existing node to which the connection destination of the new entry node in response probability.

  As an example (VI), in the example (V) shown in FIG. 5, each super node (20a to 20h in FIG. 2) identifies each existing node (21a to 21k in FIG. 2) in the cluster to which it belongs. The resource usage rate including the bandwidth usage rate and CPU usage rate of the existing node is stored in the storage device together with the information and the number, and each existing node in the cluster from the super node in the cluster to which the new participating node belongs The resource usage rate is acquired together with the identification information and the order, and the determination process of the connection destination by the determination processing procedure is executed for each existing node whose acquired resource usage rate is better than a predetermined threshold. That's fine.

  In the example (VII) shown in FIG. 6, the management server device that executes the programmed computer processing previously identifies the identification information of each existing node already participating in the overlay network as an overlay node and the connection of the existing node. A storage processing procedure (step S601) for storing in the storage device the list information described in association with the degree that is the previous number, and the list information in which the existing node that is the connection destination of the new participating node is stored in the storage device. A determination processing procedure (step S602) that is determined by reference and notified to the new participating node is executed, and the order of each existing node described in the list information is previously defined as the determination processing procedure in step S602. A method for determining an existing node as a connection destination of a new participating node with a probability according to the determined probability distribution function To run.

  In the example (VIII) shown in FIG. 7, when determining the connection destination of a new participating node that newly participates in the overlay network as an overlay node by programmed computer processing, the management server device preliminarily enters the overlay network. A storage processing procedure (step S701) for storing, in the storage device, list information in which identification information of each existing node already participating as an overlay node and the degree that is the number of connection destinations of the existing node are associated and described; In response to a request from the new participating node, the transmission processing procedure (step S702) for transmitting the list information stored in the storage device to the new participating node is executed, and the new participating node receives the list information received from the management server. Refer to the decision to determine the existing node to which the new participating node is connected. In addition to executing the processing procedure (step S703), the new participating node has a probability corresponding to the probability distribution function defined in advance for the order of each existing node described in the list information as the determination processing procedure in step S703. A procedure for determining an existing node as a connection destination of the new participating node is executed.

As an example (IX), in the determination processing procedure of any of examples (I) to (VIII), n is the number of all existing nodes, and k _j is the order of existing nodes j (1 <j ≦ n). and, _k 1 _{+ k} 2 ₊ in descending order of the order, ···, + _k is _n, the existing node j of the order _{k j,} the probability _{P (k j) = k j} ÷ (k 1 + k 2 +, ··· , can be selected by the + _{k n).}

Further, as an example (X), in the determination processing procedure in the example (IX), a procedure for generating a random number x between 0 and 1, and using the generated random number x {(k ₁ + k ₂ +,... , + K _j−1 ) ÷ {k ₁ + k ₂ +,..., + K _n )} <x ≦ {(k ₁ + k ₂ +,..., + K _j ) ÷ {k ₁ + k ₂ +,. .., + K _n )}, and a procedure for selecting the existing node j from the conditional expression.

  For example, as a simple example for explanation, if there are three existing nodes, node 1 is of degree 5, node 2 is of degree 3, and node 3 is of order 2, probability = 5 ÷ 10 = 0 for node 1 .5, for node 2, probability = (5 + 3) ÷ 10 = 0.8, for node 3, probability = (5 + 3 + 2) ÷ 10 = 1.0, and the random number x (0 <x ≦ 1) is 0. In the case of 5, only the node 1 is selected from the above conditional expression, and when the random number x (0 <x ≦ 1) is 0.8, only the node 2 is selected from the conditional expression, Further, when the random number x (0 <x ≦ 1) is 1.0, only the node 3 is selected from the conditional expression.

  Further, as an example (XI), in the determination processing procedure in the example (X), the determination processing procedure is repeated using m (1 <m ≦ n) different random numbers x that are determined in advance, and m existing It is also possible to select a node.

  In addition, as an example (XII), in any of the examples (VII) to (XI), each existing node sends the identification information of its own node to the management server at a predetermined probability for each predetermined period T1. Executing a procedure of transmitting the order, and the management server updating the list information stored in the storage device by using the identification information and the order of the existing node received from the existing node every predetermined period T1. It can be done.

  In addition, as an example (XIII), in any of the examples (VII) to (XII), each existing node is free in resources including the bandwidth usage rate and the CPU usage rate of its own device every predetermined period T2. A procedure for determining whether or not there is a resource, and a procedure for transmitting the identification information and the degree of the own node to the management server if the resource is available, and the management server performs a predetermined cycle T2 A procedure for updating the list information stored in the storage device using the identification information and the degree of the existing node received from the existing node may be executed.

  In addition, as an example (XIV), in either the example (XII) or the example (XIII), the management server stores the list information before the update in the storage device every time the list is updated. It is also possible to randomly select one of a plurality of list information stored in the storage device, and execute the determination process of an existing node that is a connection destination of the new participating node using the selected list information.

  In addition, as an example (XV), in any one of the examples (II) to (XIV), the new participating node determines from the m ′ existing nodes determined in the determination processing procedure, It is also possible to extract m pieces in order from the one having the best quality metric including the packet loss rate and throughput, and execute a procedure for determining the extracted m existing nodes as connection destinations.

  In addition, as an example (XVI), in any of the examples (II) to (XIV), the new participating node randomly extracts m pieces from the m ′ existing nodes determined in the determination processing procedure, and the m pieces The procedure of determining the existing node as the connection destination may be executed.

  In addition, as an example (XVII), in any of the examples (I) to (XVI), a predetermined existing period is detected every predetermined period or whenever a predetermined network state change is detected. It is also possible to include a procedure for executing the determination processing procedure for the node and changing the connection destination of the existing node.

As described above with reference to FIGS. 1 to 7, in this example, when determining the connection destination of a new participating node that newly participates as an overlay node in the overlay network, a criterion for the new participating node to connect to the existing node By dynamically controlling the network topology, the resulting network topology has a characteristic of scale-freeness, thereby making it possible to provide a highly fault-tolerant network. For example, in an overlay network that is a logical network constructed by several overlay nodes connected to the Internet, an already participating overlay node j is connected to k _j overlay nodes (degree k _j ), and A node newly participating in the overlay network determines a connection destination node with a probability corresponding to an arbitrary probability distribution function P (k _j ) defined for the order k _j . As described above, when adding a new node, it is known that if a connection is made in proportion to the degree k of an existing node, the scale becomes free. In the present invention, this characteristic is used, and the network characteristic depending on the topology is controlled by a node selection algorithm and parameters at the time of connection.

  As a result, a scalable high-quality and highly reliable overlay network can be configured, and end-to-end communication quality and reliability can be improved efficiently.

  In addition, this invention is not limited to the example demonstrated using FIGS. 1-7, A various change is possible in the range which does not deviate from the summary. For example, in this example, as illustrated in FIG. 2, a super overlay network including super nodes 20a to 20h and existing nodes 21a to 21k is described as an example, but the present invention can also be applied to a general overlay network.

  The computer configuration example of this example may also be a computer configuration without a keyboard or optical disk drive. In this example, an optical disk is used as a recording medium. However, an FD (Flexible Disk) or the like may be used as a recording medium. As for the program installation, the program may be downloaded and installed via a network via a communication device.

It is a block diagram which shows the structural example of the connection candidate management server used for topology control of the overlay network which concerns on this invention. It is explanatory drawing which shows the structural example of the overlay network which performs topology control which concerns on this invention. It is a 1st flowchart which shows the example of a procedure of the topology control method of the overlay network which concerns on this invention. It is a 2nd flowchart which shows the other example of a procedure of the topology control method of the overlay network which concerns on this invention. It is a 3rd flowchart which shows the other example of a procedure of the topology control method of the overlay network which concerns on this invention. It is a 4th flowchart which shows the other example of a procedure of the topology control method of the overlay network which concerns on this invention. It is a 5th flowchart which shows the other example of a procedure of the topology control method of the overlay network which concerns on this invention. It is explanatory drawing which shows the basic concept of the QoS management by the conventional overlay network.

Explanation of symbols

  1: connection candidate management server, 1a: connection destination determination unit, 1b: degree management unit, 1c: coordinate holding unit, 20a-20h: super node, 21a-21k: existing node (general node), 22: new participation node, 81a to 81c: Super node, 82a to 82e: IP router, 83: Overlay network, 84: IP network.

Claims (19)

An overlay network topology control method for determining a connection destination of a new participating node newly participating as an overlay node in an overlay network by programmed computer processing,
As a process execution procedure of the programmed computer,
A storage processing procedure for storing, in a storage device, list information in which identification information of each existing node that has already participated in the overlay network as an overlay node and a degree that is the number of connection destinations of the existing node are associated with each other. When,
A determination processing procedure for determining an existing node as a connection destination of the new participation node with reference to the list information stored in the storage device,
And the said determination process procedure determines the existing node which becomes the connection destination of the said new participating node with the probability according to the probability distribution function defined beforehand with respect to the degree of each existing node described in the said list information An overlay network topology control method comprising: An overlay network topology control method for determining a connection destination of a new participating node newly participating as an overlay node in an overlay network by programmed computer processing,
As a programmed computer processing procedure
The new participating node is predetermined as a message for inquiring each existing node already participating in the overlay network as an overlay node with the identification information of the existing node and the order that is the number of connection destinations of the existing node. A transmission procedure for transmitting a specified number of hops;
A transfer procedure in which the existing node receiving the message and the hop number transfers the received message and the hop number to the adjacent existing node;
A reply procedure for returning the identification information and the order of each existing node from each existing node receiving the message to the new participating node;
Repeating the forwarding procedure and the reply procedure at each existing node within the hop count range;
A procedure in which the new participating node generates list information in which the identification information and the degree of the existing node received from each existing node are associated with each other and stores the list information in the storage device, and the list information stored in the storage device. And a determination processing procedure for determining an existing node to which the local node is connected,
And,
The determination processing procedure includes a procedure of determining an existing node to be a connection destination of the new participating node with a probability according to a probability distribution function defined in advance for the degree of each existing node described in the list information. A method for controlling the topology of an overlay network. The overlay network topology control method according to claim 2,
Each of the existing nodes executes a procedure for returning the resource usage rate including the bandwidth usage rate and CPU usage rate of the own device together with the identification information and the order to the new participating node,
The new participating node performs connection destination determination processing according to the determination processing procedure for the existing nodes that have replied and the resource usage rate is better than a predetermined threshold. To control topology of overlay network. The overlay network topology control method according to claim 2,
The existing node registers its own identification information, degree, resource usage rate including bandwidth usage rate and CPU usage rate as an index in the distributed hash table,
The new participating node searches the distributed hash table, extracts existing nodes having a plurality of predetermined different orders and resource information, and executes the determination processing procedure for each extracted existing node. A method for controlling the topology of an overlay network, wherein an existing node to be connected is selected. Through programmed computer processing, the connection destination of a new participating node that newly participates as an overlay node in an overlay network composed of a plurality of clusters each composed of a plurality of supernodes and a plurality of general nodes connected to each supernode. An overlay network topology control method to be determined, comprising:
As a programmed computer processing procedure
A procedure in which the super node stores, in a storage device, identification information of each existing node existing as a general node in the cluster to which the super node belongs and a degree that is the number of connection destinations of the existing node;
The new participating node acquires the identification information and order of each existing node in the cluster from the super node in the cluster to which the new participating node belongs, and the existing node that is the connection destination of its own node using the acquired order and identification information And a determination processing procedure for determining
And the said determination process procedure determines the existing node which becomes the connection destination of the said new participating node with the probability according to the probability distribution function defined beforehand with respect to the degree of each existing node described in the said list information An overlay network topology control method comprising: The overlay network topology control method according to claim 5,
Each super node stores the resource usage rate including the bandwidth usage rate and CPU usage rate of the existing node in the storage device together with the identification information and the number of each existing node in the cluster to which the super node belongs,
The new participating node acquires the resource usage rate together with the identification information and order of each existing node in the cluster from the super node in the cluster to which the new participating node belongs. A topology control method for an overlay network, characterized in that a connection destination determination process according to the determination process procedure is executed for a value better than a predetermined threshold value. An overlay network topology control method for determining a connection destination of a new participating node newly participating as an overlay node in an overlay network by programmed computer processing,
A management server device that executes programmed computer processing,
A storage processing procedure for storing, in a storage device, list information in which identification information of each existing node that has already participated in the overlay network as an overlay node and a degree that is the number of connection destinations of the existing node are associated with each other. When,
A determination process procedure for determining an existing node to be a connection destination of the new participation node with reference to the list information stored in the storage device and notifying the new participation node;
As the determination processing procedure, a procedure for determining an existing node to be a connection destination of the new participating node with a probability corresponding to a probability distribution function defined in advance for the order of each existing node described in the list information is executed. A topology control method for an overlay network. An overlay network topology control method for determining a connection destination of a new participating node newly participating as an overlay node in an overlay network by programmed computer processing,
Management server device
A storage processing procedure for storing, in a storage device, list information in which identification information of each existing node that has already participated in the overlay network as an overlay node and a degree that is the number of connection destinations of the existing node are associated with each other. When,
In response to a request from the new participation node, execute a transmission processing procedure for transmitting the list information stored in the storage device to the new participation node,
The new participating node refers to the list information received from the management server and executes a determination processing procedure for determining an existing node to which the new participating node is connected,
The new participating node is an existing node that becomes a connection destination of the new participating node with a probability according to a probability distribution function defined in advance for the degree of each existing node described in the list information as the determination processing procedure. A method for controlling the topology of an overlay network, characterized in that a procedure for determining the topology is executed. The overlay network topology control method according to any one of claims 1 to 8,
In the above decision processing procedure,
All existing node number n, the degree of the existing nodes j (1 <j ≦ n) and _{k j,} and, _k 1 _{+ k} 2 ₊ in descending order of the order, ..., and + _{k n,}
An existing node j of the order k _j is
Probability _{P (k j) = k j} ÷ (k 1 + k 2 +, ···, + k n) topology control method of the overlay network, characterized by selected. The overlay network topology control method according to claim 9, comprising:
The above decision processing procedure is as follows:
A procedure for generating a random number x between 0 and 1;
{(K ₁ + k ₂ +,..., + K _j-1 ) / {k ₁ + k ₂ +,..., + K _n )} <x ≦ {(k ₁ + k ₂ + ,..., + K _j ) ÷ {k ₁ + k ₂ +,..., + K _n )}, and a procedure for selecting an existing node j. The overlay network topology control method according to claim 10, comprising:
In the above decision processing procedure,
A topology control method for an overlay network, wherein the determination processing procedure is repeated using m (1 <m ≦ n) different random numbers x determined in advance, and m existing nodes are selected. The overlay network topology control method according to any one of claims 7 to 11,
Each existing node executes a procedure of transmitting its own node identification information and order to the management server with a predetermined probability for each predetermined period T1,
The management server executes a procedure of updating the list information stored in the storage device by using the identification information and the order of the existing node received from the existing node every predetermined cycle T1. To control topology of overlay network. The overlay network topology control method according to any one of claims 7 to 12,
Each existing node determines, for each predetermined period T2, whether or not there is a free resource including the bandwidth usage rate and CPU usage rate of its own device, and if there is a free resource, the management server To send the identification information and the order of the own node,
The management server executes a procedure for updating the list information stored in the storage device by using the identification information and the order of the existing node received from the existing node every predetermined period T2. To control topology of overlay network. The overlay network topology control method according to any one of claims 12 and 13,
The management server
Each time the list is updated, the list information before the update is also stored in the storage device,
In the above decision processing procedure,
An overlay network characterized in that any one of a plurality of list information stored in the storage device is selected at random, and a determination process of an existing node as a connection destination of the new participating node is executed using the selected list information Topology control method. The overlay network topology control method according to any one of claims 2 to 14,
The new participating node is
From m ′ existing nodes determined by the above determination procedure,
It is characterized by extracting m pieces in order from the one having the best quality metric including delay time, packet loss rate, and throughput with the own apparatus, and executing a procedure for determining the m existing nodes as connection destinations. Topology control method for overlay network. The overlay network topology control method according to any one of claims 2 to 14,
The new participating node is
An overlay network topology control method, comprising: extracting m m random nodes from m ′ existing nodes determined in the determination processing procedure, and determining the m existing nodes as connection destinations. The overlay network topology control method according to any one of claims 1 to 16, comprising:
As a programmed computer processing procedure
Every time a predetermined period or a change in the state of a predetermined network is detected, the above determination processing procedure is executed for a predetermined existing node, and the connection destination of the existing node is changed. A method for controlling the topology of an overlay network, comprising a procedure.   A program for causing a computer to execute each procedure in the overlay network topology control method according to any one of claims 1 to 17. A topology control system for an overlay network that determines a connection destination of a new participating node that newly participates in the overlay network as an overlay node by programmed computer processing,
As a processing execution means of a programmed computer,
An overlay network topology control system comprising means for executing each procedure in the overlay network topology control method according to any one of claims 1 to 17.

Images