JP2007227997A - Communication path determining method and communication path determining system in overlay network - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a communication path determining method and a communication path determining system in an overlay network whereby the number of relay node candidates is always limited to a prescribed number or below and a relay node capable of providing a high quality path is selected with a high probability through actual relay node selection acts. <P>SOLUTION: Each node belonging to the overlay network measures communication quality from its own node to a destination node, and acquires a result of communication quality measurement from a relay candidate node to the destination node from the relay candidate node on the other hand. Each node compares both the communication qualities, uses a path of direct transfer to the destination node as a communication path from its own node to the destination node without using the relay node when the former quality is better, or uses a communication path using a relay node providing the highest quality when the latter quality is better. In the case of selecting a relay node candidate next, the probability of selecting a node selected with a high frequency of selection in the past as the relay node is set higher. <P>COPYRIGHT: (C)2007,JPO&INPIT

Description

  The present invention relates to a technology for improving end-to-end communication quality on the Internet, and more particularly, to improve end-to-end communication quality in a communication path using an overlay network logically formed on an IP network. The present invention relates to a communication path determination method and a communication path determination system that are suitable for improving the performance.

  The Internet, which represents an IP network, has been developed and spread to accommodate various applications. Recently, the Internet 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. Yes. 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, which greatly changes 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 such circumstances, as a promising technology capable of improving end-to-end QoS without changing a lower network layer, for example, L.P. 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. The “QoS management technology by overlay network” described in (Non-patent Document 1) is attracting attention.

  The overlay network is, for example, the WIDE project, “Integrated and distributed environment by overlay network,” WIDE project research report, Part 17, 2002. As described in (Non-patent Document 2), this is a network that uses an existing link to form a logical (virtual) link in the upper layer according to the purpose and configure it.

FIG. 1 is a diagram showing a basic concept of QoS management by an overlay network.
In FIG. 1, it is assumed that traffic flows along a route represented by a broken-line arrow from x to y. Further, it is assumed that there is a congested IP router on this route, and as a result, the QoS between x and y is lowered.
At this time, using the overlay network formed by the overlay nodes a, b, and c, the traffic is detoured along the route (x → overlay node a → overlay node b → overlay node c → y) represented by the practical arrow. If this is possible, the above congestion can be avoided.

  In fact, Kamei and Kawahara, “Traffic on-genering with an end-host overlay network and its effectiveness,” IEICE. BS-5-3, 2004. (See Non-Patent Document 3) or S.A. Rewaskar and J.H. Kaur, “Testing the Scalability of Overlay Infrastructures,” Proc. PAM 2004. April 2004. (See Non-Patent Document 4) or S.A. Banerjee, T .; G. Grifin and M.M. Pias, “The Interdomain Connectivity of PlanetLab Nodes,” Proc. PAM 2004, April 2004. (See Non-Patent Document 5), based on actual measurements, shows that there are many detour paths as described above in the real network.

However, the results of Non-Patent Documents 3 and 5 are evaluations when the topology of the overlay network is a full mesh and ideal communication path calculation is performed using quality information measured between all overlay nodes. The decrease in scalability (system expandability) 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 practically impossible to calculate communication paths using quality measurement information between all overlay nodes.
In order to avoid the above problem, Non-Patent Document 4 evaluates a case where the number of relay node candidates that provide a detour route is limited. However, the relay node candidates are simply selected at random, and the relay node candidate selection method has not been studied.

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 on-genering with an end-host overlay network and its effectiveness,” IEICE. BS-5-3, 2004. S. Rewaskar and J.H. Kaur, “Testing the Scalability of Overlay Infrastructures,” 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. Masato Uchida, Kei Kamei, Ryoichi Kawahara, “Evaluation of QoS Routing Control by Overlay Network,” IEICE Technical Report IN2005-31, pp. 13-18, (2005-07).

  On the other hand, Masato Uchida, Satoshi Kamei and Ryoichi Kawahara, “Evaluation of QoS Routing Control by Overlay Network,” IEICE Technical Report IN2005-31, pp. 11-27. 13-18, (2005-07). (See Non-Patent Document 6) The present inventors appropriately limit the number of relay node candidates based on the measurement data, thereby improving the QoS almost equivalent to the optimum case where the route search is performed with all nodes as relay candidates. It is shown that it can be planned.

  However, this method calculates the optimal route for all node pairs when all nodes are relay node candidates, and calculates how often each node is selected as a relay node that provides the optimal route. In addition, the top M nodes having a high frequency are extracted, and only M relay candidate nodes are used in the subsequent route calculation based on the above preparation. Therefore, there is a problem that it is necessary to search all routes once, and there is still a route calculation cost for that purpose.

  In addition, when the traffic characteristics of the IP network change significantly after determining the upper M node, the M node may no longer be the upper M node and may not be able to follow the change in traffic characteristics. It was.

(the purpose)
In view of the above-described problems, the object of the present invention is to keep the number of candidate relay nodes below a certain number and to select a relay node that can provide a high-quality route through an actual relay node selection act. Thus, an object of the present invention is to provide a communication path determination method and a communication path determination system that can dynamically change the selection probability and determine a high-quality communication path in an overlay network.

  A first method of the present invention is a communication path determination method for determining a communication path from a source node to a destination node in an overlay network that is a logical network composed of N overlay nodes connected to an IP network. Each node i (i = 1 to N) belonging to the overlay network has its own node as a source and other nodes j (all except i) as destination nodes j, and the source node i and destination node j Communication quality between the relay candidate node k and the destination node j, while selecting the M nodes from among the N nodes as relay node candidates. Is obtained from the relay candidate node, and the communication quality between the own node i and the destination node j and the destination node j are reached from the own node i via the relay candidate node k. If the former gives better quality, the route directly transferred to the destination node j without using the relay node is set as the communication route from the own node i to the destination node j, If the latter gives good quality, the node k * providing the highest quality among them is set as a relay node, the communication path is determined as self node → relay node k * → destination node j, and the next relay node candidate At the time of selection, the probability that a node having a high frequency selected as a relay node in the past is selected is increased.

According to a second method of the present invention, in the first method, there is a server that manages information on candidate relay nodes in the overlay network, and the server is in the nth measurement period (time point n) of each node k. Score C (n, k) is managed. When the source node i determines a route to the destination node j at the time point n, the score C (n, k) of each node k (k = 1 to N) is read from the server, and the probability p_k = C ( n, k) / Σ _k C (n, k) selects node k (k is other than i) as a relay candidate node, and this is repeated until M relay candidate nodes are determined. The source node i determines the route to the destination node j by the first method. At this time, if the node k * is determined as the relay node, the node k * notifies the server to that effect. A similar procedure is performed for all source-destination node pairs. The server receives from each node that it has been determined as a relay node, and counts the number of times C ′ (n, k) at which each node k has become a relay node at time n. Using the value, the score of each node k at the next time point n + 1 is updated by C (n + 1, k) = (1−α) C (n, k) + αC ′ (n, k). Here, α is a smoothing parameter determined in advance, 0 <α <1, and the initial value of C (n, k) is C (0, k) = 1 (all k). To do.
Here, the score C (n, k) of the node is updated so as to increase when the node k provides a high-quality route, and to decrease otherwise. Therefore, by selecting a relay node candidate in proportion to the score, a relay node that provides a high-quality route is easily selected at the next relay node candidate selection.

According to the third method of the present invention, in the method of updating the score C (n, k) of the relay node described in the second method, instead of updating as in the second method, a predetermined parameter β ( > 0) and c (> 1) to calculate t ′ = min {n + β, c} and C (n + 1) = (1-1 / t ′) C (n, k) + 1 / t′C ′ The score is updated by (n, k).
The reason why the minimum value of n + β and c is taken and used as the smoothing parameter 1 / t ′ for score update is that the number of times selected as a relay node at the initial stage of learning (that is, the stage where n is small) This is to positively reflect C ′ (n, k). By doing so, it becomes possible to quickly converge to the target value.

In the fourth method of the present invention, in the method of selecting relay node candidates described in the second method, p_k = {exp (C (n, k)) instead of selecting as in the second method. −1} / Σ _k {exp (C (n, k) −1)}.
By taking the exponential, the node k having a large value of C (n, k) is more easily selected.

  The fifth method of the present invention uses the delay time d (i, j) as the communication quality between the own node i and the destination node j in the first method, and the destination node j When deciding whether to make a detour using any of the M relay candidate nodes when determining the route to the node, the delay time d (i, k) from the node i to the relay candidate node k Is there a k that satisfies d (i, j)> d (i, k) + d (k, j) using the delay time d (k, j) between the relay candidate node k and the destination node j? If it does not exist, the direct communication from node i to j is determined as the communication path. It is characterized by determining node k * → destination node j.

  The sixth method of the present invention uses the packet loss rate p (i, j) between the nodes i and j and uses the packet loss rate p (i, j) between the nodes i and j instead of using the delay time as the quality as in the fifth method. When deciding whether to make a detour using any of the M relay candidate nodes when determining the route to the destination node j, the packet loss rate p (i) of the relay candidate node k from its own node i is determined. , K) and the packet loss rate p (k, j) from the relay candidate node k to the destination node j, p (i, j)> 1- {1-p (i, k)} {1-p It is checked whether or not k satisfying (k, j)} exists. If there is no k, the direct communication from the node i to j is determined as the communication path, and if it exists, the right side is minimized k Is determined as relay node k *, and the communication path is determined as own node i → relay node k * → destination node j. The features.

  The seventh method of the present invention uses the available bandwidth B (i, j) between the nodes i and j and uses the available bandwidth B (i, j) instead of using the delay time as the quality as in the fifth method. When determining whether to make a detour using any of the M relay candidate nodes when determining the route to the destination node j, the available bandwidth B (i , K) and B (k, j) between the relay candidate node k and the destination node j, B (i, j) <min {B (i, k), B (k, j)} If there is no k that satisfies the condition, if it does not exist, the direct communication from node i to j is determined as the communication path. If it exists, k that maximizes the right side is set as the relay node k *. The communication path is determined as self node i → relay node k * → destination node j.

In the eighth method of the present invention, in the relay node candidate management server described in the second method, the number of times C ′ (n, k) at which each node k becomes a relay node at time n is counted. When the total value Σ _k C ′ (n, k) is smaller than a predetermined threshold value, the score C (n, k) of each node is initialized again and C (0, k) (k = 1˜ N).
Since Σ _k C ′ (n, k) represents the number of times a node providing a high-quality route has been appropriately selected, the fact that this value is small means that the traffic conditions of the IP layer and the routing of the IP layer This means that the learning result so far (that is, the score C (n, k) of each node) is inappropriate due to factors such as change. Therefore, by resetting the score, the score is learned again so that a state suitable for the new traffic condition can be quickly dealt with.

  According to a ninth system of the present invention, means for measuring communication quality between nodes by any one of the first, fifth, sixth and seventh methods, and determining whether or not to make a detour using the measured communication quality, A means for selecting a relay candidate node and determining a relay node by any one of methods 2, 3, 4, and 8 is provided.

  ADVANTAGE OF THE INVENTION According to this invention, it becomes possible to aim at the improvement of communication quality, reducing the cost accompanying the communication path calculation in an overlay network.

Embodiments of the present invention will be described below in detail with reference to the drawings.
Example 1
FIG. 2 is a basic configuration diagram of the overlay network according to the first embodiment of the present invention.
Each overlay node 1-5 is logically connected to other nodes. That is, the overlay nodes 1 to 5 know the IP addresses of other nodes existing in the overlay network and are in a communicable state. In addition, there is a management server 10 that manages relay node candidates. Each of the nodes 1 to 5 updates the communication path with other nodes at regular intervals.
Hereinafter, the description will be focused on the node 1 (the other nodes 2 to 5 perform the same behavior independently). The solid line in FIG. 2 is a communication path, and the broken line is a control line from the management server 10 to each overlay node 1-5.

FIG. 3 shows a configuration example of the overlay node 1 that selects a relay candidate by the second method of the present invention, measures the communication quality between the nodes by the fifth method, and determines whether or not to make a detour by using the communication quality. FIG. 6 is a block diagram illustrating a configuration example of the management server.
As shown in FIG. 3, the communication quality measuring unit 21 calculates a delay time d (1, j) between itself (overlay node 1) and another node j (j = 2 to 5) every measurement period τ. Measure (similarly, the node i (i = 2 to 5) also measures the delay time d (i, j) with other nodes j (j = 1 to 5 excluding j = i)) ) If the delay time is measured, the relay candidate selection unit 24 is notified of this. Further, the delay time measurement result is notified in accordance with an instruction from the communication quality acquisition unit 22 of another node.

The relay candidate selection unit 24 downloads the score C (n, k) at the n-th measurement period (hereinafter referred to as time point n) of each node k from the management server 10 and the probability p_k = C (n, k ) / Σ _k C (n, k), node k (k is other than i) is selected as a relay candidate node, and this is repeated until M relay candidate nodes are selected. The relay node determination unit 23 is notified of the selected M relay candidate nodes.

The relay node determination unit 23 instructs the communication quality acquisition unit 22 to acquire the delay time measurement result d (k, j) of the nodes k and j from the relay candidate node k. After acquiring d (k, j), the communication quality acquisition unit 22 notifies the relay node determination unit 23 of it.
The above procedure is performed for all relay candidate nodes.

The relay node determination unit 23 acquires the delay time d (k, j) of the relay candidate node k from the own node 1 from the communication quality measurement unit 22, and delay time d between the relay candidate node k and the destination node j. (K, j) is used to check whether or not k satisfying d (1, j)> d (1, k) + d (k, j) exists in M candidates. In this case, the direct path from node 1 to j is determined as the communication path, and if it exists, k that minimizes the right side is determined as the relay node k *.
After the determination, the node k * is requested to set the communication path as self node 1 → relay node k * → destination node j. The above procedure is performed for all destination nodes j (j = 2 to 5).

  The relay node k * sets a route of node 1 → relay node k * → destination node j. Thereafter, it notifies the management server 10 that it has been selected as a relay node.

When the management server 10 receives a notification from the relay node k *, the management server 10 determines the number C ′ (n, k) at which the node k * has become a relay node in the relay node selection count management unit 31 as C ′ (n, k, k) Count up to ← C ′ (n, k) +1. The above operation is repeated until the n-th measurement cycle ends, and the number of times that each node becomes a relay node is counted.
When the (n + 1) th measurement cycle is reached, the node score update unit 32 of the management server 10 sets the scores C (n + 1, k) of all nodes to C (n + 1, k) = (1-α) C (n, k ) + ΑC ′ (n, k). Here, α is a smoothing parameter determined in advance, 0 <α <1, and the initial value of C (n, k) is C (0, k) = 1 (all k).

(Example 2)
Hereinafter, only the changes in the first embodiment are described in the second embodiment, and the other processes are the same as those in the first embodiment, and thus the other description is omitted.
In the second embodiment, instead of performing the procedure for updating the score in the management server 10 in the first embodiment as in the first embodiment, t ′ = using predetermined parameters β (> 0) and c (> 1). min {n + β, c} is calculated, and the score is updated by C (n + 1) = (1-1 / t ′) C (n, k) + 1 / t′C ′ (n, k).

(Example 3)
Hereinafter, only the changes in the first embodiment will be described in the third embodiment, and the other processes are the same as those in the first embodiment, and thus the other description is omitted.
In the relay (node) candidate selection unit 24 in the first embodiment, the node k (k is other than i) is selected as the relay candidate node with the probability p_k = C (n, k) / Σ _k C (n, k). Instead, a relay node is selected by p_k = {exp (C (n, k) −1) / Σ _k (exp (C (n, k) −1)}.

Example 4
Hereinafter, only the changes in the first embodiment are described in the fourth embodiment, and the other processes are the same as those in the first embodiment.
In the communication quality measuring unit 21 according to the first embodiment, instead of using the delay time as the quality, the packet loss rate p (i, j) between the nodes i and j is used, and the relay node determining unit 23 uses M packets. When determining whether to make a detour using any one of the relay candidate nodes, the packet loss rate p (i, k) from the local node i to the relay candidate node k, the relay candidate node k, and the destination node j K that satisfies p (i, j)> 1- {1-p (i, k)} {1-p (k, j)} using the packet loss rate p (k, j) between If it does not exist, the direct communication from the node i to j is determined as the communication path, and if it exists, k that minimizes the right side is determined as the relay node k *.

(Example 5)
Hereinafter, only the changes in the first embodiment are described in the fifth embodiment, and the other processes are the same as those in the first embodiment, and thus the other description is omitted.
Instead of using the delay time as the quality in the communication quality measuring unit 21 in the first embodiment, the available bandwidth B (i, j) between the nodes i and j is used, and the relay node determining unit 23 uses the M B (i, j) <min {B using the available bandwidth B (i, k) of the relay candidate nodes k and that B (k, j) between the relay candidate nodes k and the destination node j It is checked whether or not k satisfying (i, k), B (k, j)} exists. If not, the direct communication from node i to j is determined as the communication path. Then, k that maximizes the right side is determined as the relay node k *.

(Example 6)
Hereinafter, only the changes of the first to fifth embodiments will be described with respect to the sixth embodiment, and the other processes are the same as those of the first embodiment, and thus other explanations are omitted.
In the management server 10 according to the first to fifth embodiments, the number of times C ′ (n, k) at which each node k becomes a relay node at time n is counted, and the total value Σ _k C ′ (n, k ) Is smaller than a predetermined threshold value, the score C (n, k) of each node is initialized again to C (0, k).

(Evaluation of Examples)
Hereinafter, the evaluation result when the procedure of Example 2 of the present invention is executed will be described.
FIG. 4 is a diagram illustrating a cumulative distribution of delay times of all node pairs.
In this evaluation, a computer terminal contracted as a user with 18 ISPs that are geographically separated in Japan as a user sends out one packet every second for 3 minutes between each terminal, and the delay time (3 Data measuring the maximum delay in minutes) were used. Using the delay time d (n, i, j) between the terminals i and j at the n-th time (n = 1, 2,..., 24), 18 terminals are regarded as overlay nodes, and each node i is A communication path to another node j is determined according to the procedure of the embodiment of the present invention. Note that the number of candidate relay nodes M = 4, β = 0.5, and c = 4. FIG. 4 shows a cumulative distribution (24 hours) of delay times of all node pairs at this time. In the figure, “proposed” is the case of the second embodiment.

In FIG. 4, for comparison, the case where the route control is not performed, that is, the case where all the straight paths are selected is indicated by default. Also, the optimal case where all N = 18 nodes can be used as relay candidates without limiting the number of relay node candidates is indicated by “optimal”. In addition, a case where four relay node candidates are simply selected at random is indicated by random.
Thereby, in the present invention, it can be seen that the quality improvement is almost the same as that in the entire route search (optimal).

FIG. 5 is a diagram showing a time series of delay times every n hours.
Here, a time series of delay times every n hours, that is, the nth measurement period is shown. That is, the 95th percentile of the delay time of all node pairs at the nth time is plotted. Also from this figure, it can be confirmed that the present invention can stably maintain the low delay time.

It is a figure explaining the concept of the route control by an overlay network. 1 is a basic configuration diagram of an overlay network according to Embodiment 1 of the present invention. It is a figure which shows the structural example of the overlay node in this invention. It is explanatory drawing which shows the effect of this invention. It is the figure which showed the behavior of the delay time at the time of applying this invention. It is a figure which shows the structural example of the management server in this invention.

Explanation of symbols

1, 2, 3, 4, 5 Overlay node 10 Management server 21 Communication quality measurement unit 22 Communication quality acquisition unit 23 Relay node determination unit 24 Relay candidate selection unit 31 Relay node selection frequency management unit 32 Node score update unit a, b, c Overlay node

Claims (9)

In a communication path determination method for determining a communication path from an origination node to a destination node in an overlay network, which is a logical network composed of N overlay nodes connected to an IP network,
Each node i (i = 1 to N) belonging to the overlay network has its own node as a source and other nodes j (all except i) as destination nodes j, and the source node i and destination node j Measure the communication quality between
Each node i selects M nodes from among the N nodes as relay node candidates, and the communication quality measurement result between the relay candidate node k and the destination node j is transmitted from the relay candidate node. Acquired,
Each node i compares the communication quality between its own node i and the destination node j with the communication quality when it reaches the destination node j via the relay candidate node k from its own node i. When better quality is given, the relay node is not used, and the route directly transferred to the destination node j is the communication route from the own node i to the destination node j, and the latter gives better quality. The node k * that provides the highest quality among them is the relay node, and the communication path is determined as the local node → the relay node k * → the destination node j,
A method for determining a communication path in an overlay network, characterized in that, when selecting a relay node candidate next time, a probability of selecting a node having a high frequency selected as a relay node in the past is increased. The communication path determination method in the overlay network according to claim 1,
A server for managing information on candidate relay nodes is arranged in the overlay network,
The server manages the score C (n, k) in the nth measurement period of each node k,
At time n, the source node i reads the score C (n, k) of each node k (k = 1 to N) from the server when determining the route to the destination node j, and the probability p_k = C (n, k) / Σ _k C (n, k) selects node k (k is other than i) as a relay candidate node, and repeats this until M relay candidate nodes are determined.
The source node i determines a route to the destination node j by the method according to claim 1,
At that time, if the node k * is determined as the relay node, the node k * notifies the server to that effect,
Perform the same procedure for all source-destination node pairs,
The server receives from each node that it has been determined as a relay node, counts the number of times C ′ (n, k) each node k has become a relay node at time n,
The server uses the counted value to update the score of each node k at the next time point n + 1 by C (n + 1, k) = (1−α) C (n, k) + αC ′ (n, k). A method for determining a communication path in an overlay network.
(Α is a predetermined smoothing parameter, 0 <α <1, and the initial value of C (n, k) is C (0, k) = 1 (all k)) The communication path determination method in the overlay network according to claim 2,
When updating the score C (n, k) of the relay node, instead of updating as described in claim 2, t ′ = min using predetermined parameters β (> 0) and c (> 1) {N + β, c} is calculated,
A method for determining a communication path in an overlay network, wherein the score is updated by C (n + 1) = (1-1 / t ′) C (n, k) + 1 / t′C ′ (n, k). The method for determining a communication path in an overlay network according to claim 2,
When selecting the relay node candidate, instead of selecting as in claim 2,
p_k = {exp (C (n, k)) − 1} / Σ _k {exp (C (n, k) −1)} in an overlay network characterized by having node k as a relay node candidate with a probability of Communication path determination method. The communication path determination method in the overlay network according to claim 1,
When measuring the communication quality, the delay time d (i, j) is used as the communication quality between the own node i and the destination node j, and the route from the own node i to the destination node j is determined. When deciding whether to make a detour using any of the M relay candidate nodes, the delay time d (i, k) from the node i to the relay candidate node k, the relay candidate node k, and the destination node Using the delay time d (k, j) between j, it is determined whether or not k satisfying d (i, j)> d (i, k) + d (k, j) exists.
If it does not exist, the direct communication from the node i to j is determined as the communication path. If it exists, the relay node k * of k that minimizes the right side is set, and the communication path is changed from the own node i to the relay node k *. -> A communication path determination method in an overlay network, characterized in that it is determined as a destination node j. In the communication path determination method in the overlay network according to any one of claims 1 to 5,
The path from the node i to the destination node j using the packet loss rate p (i, j) between the nodes i and j instead of using the delay time as the quality as in the method according to claim 5 When determining whether to bypass using any of the M relay candidate nodes when determining the packet loss rate p (i, k) from the node i to the relay candidate node k and the relay candidate Using packet loss rate p (k, j) from node k to destination node j, p (i, j)> 1- {1-p (i, k)} {1-p (k, j)} If there is no k that satisfies the condition, the direct communication from node i to j is determined as the communication path, and if it exists, k that minimizes the right side is set as the relay node k *. , And determining the communication path from its own node i → relay node k * → destination node j Communication route determination method in the overlay network. In the communication path determination method in the overlay network according to any one of claims 1 to 5,
A route from the local node i to the destination node j using the available bandwidth B (i, j) between the nodes i and j instead of using the delay time as the quality as in the method according to claim 5 When deciding whether to make a detour using any of the M relay candidate nodes, the available bandwidth B (i, k) from the node i to the relay candidate node k and the relay candidate Using B (k, j) between the node k and the destination node j, there exists k satisfying B (i, j) <min {B (i, k), B (k, j)}. If it does not exist, the direct communication from nodes i to j is determined as the communication path. If it exists, k that maximizes the right side is set as the relay node k *, and the communication path is the own node. Overlay net characterized in that i → relay node k * → destination node j Communication route determination method in over click. The method for determining a communication path in an overlay network according to claim 2,
The server managing the relay node candidates counts the number of times C ′ (n, k) at which each node k becomes a relay node at time n, and the total value Σ _k C ′ (n, k) is preliminarily determined. If it is smaller than the predetermined threshold, the score C (n, k) of each node is initialized again to C (0, k) (k = 1 to N), and the communication path in the overlay network Decision method.   Means for measuring communication quality between nodes by the method according to any one of claims 1, 5, 6, and 7, and determining whether or not to make a detour using the measurement result, and claims 2, 3, and 4 , 8 comprises a means for selecting a relay candidate node and determining a relay node by any one of the methods described in claim 8.

Images