JP2010130032A - System and method for selecting overlay network path, and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To prevent traffic concentration associated with selection of a communication path in an overlay network without impairing communication quality of an end host. <P>SOLUTION: When selecting one of overlay paths, a communication path quality acquisition section 30b acquires path quality of an RTT or the like to be stored in a communication path quality storage section 30c; and a communication path selection section 30d selects a communication path used in executing data communication with probability in accordance with the quality stored in the communication path quality storage section 30c. For instance, a probability distribution by weighted average is generated from quality of each communication path, and a communication path used in executing data communication is selected according to the generated probability distribution. A communication path quality update section 30e calculates an update value of the quality of each communication path by an online prediction algorithm based on a learning theory by acquiring and cumulatively using the communication quality of the respective communication paths every time the data communication is completed, and updates storage information in the communication path quality storage section 30c. <P>COPYRIGHT: (C)2010,JPO&INPIT

Description

  The present invention relates to a technique for improving end-to-end communication quality in an IP network, and in particular, end-to-end communication using an overlay network logically formed on an IP network such as the Internet. The present invention relates to a technique suitable for efficiently improving quality.

The Internet, which represents an IP network, has been developed and spread to accommodate various applications. On the other hand, there is an increasing demand for QoS (Quality of Service).

  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 problems shown in the following (1) and (2) 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 such circumstances, as an effective technique that can improve end-to-end QoS without changing a lower network layer, a QoS management technique using an overlay network described in Non-Patent Document 1, for example, has attracted attention.

  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. FIG. 1 is a block diagram illustrating a configuration example of an overlay network. An overlay network (described as “Overlay-NW” in the figure) 4 includes a plurality of overlay nodes 1, 2, and 3, and includes a plurality of IP routers 5-9. Is logically formed on an IP network 10 (described as “IP-NW” in the figure).

  In the IP network 10 having such a configuration, 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 9 on this route, and as a result, the QoS between x and y is lowered.

  At this time, using the overlay network 4 formed by the overlay nodes 1, 2, and 3, traffic is detoured along a route (x → overlay node 1 → overlay node 2 → overlay node 3 → y) represented by a solid line arrow. If possible, the above congestion can be avoided.

  In fact, Non-Patent Documents 3, 4, 5, 6 and the like indicate that there are a large number of such detour routes in the real network based on actual measurements. In the conventional overlay route selection techniques mentioned in Non-Patent Documents 3, 4, 5, 6 and Non-Patent Document 7, etc., each end host selects the one with the best communication quality at that time.

  Here, communication quality refers to the throughput and average delay time observed so far in each overlay route. By measuring this communication quality for each overlay route, the end host selects a route with good communication quality. be able to.

  However, when the number of end hosts that perform such overlay route selection increases in the future, traffic concentrates on the same route by multiple end hosts self-selecting the best quality overlay route. There is a possibility of causing congestion.

  However, whether or not traffic concentration actually occurs depends on the ratio of end hosts that self-select the route, so it is always the end host to select a poor quality overlay route assuming such traffic concentration. Does not necessarily lead to improved communication quality.

  Conventionally, a rational technique for solving such a problem, ensuring communication quality of an end host, and avoiding traffic concentration has not been studied.

L. Zhi and P. Mohapatra, “QRON: QoS-aware routing in overlay net-works,” IEEE J. Select. Area 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. Kaur, “Testing the Scalability of Overlay Infrastructures,” Proc. PAM 2004. April 2004. S. Banerjee, TG Griffin and M. Pias, “The Interdomain Connectivity of PlanetLab Nodes,” Proc. PAM 2004, April 2004. Hiraoka, Hasegawa, Murata, “Evaluation of Overlay Routing Effectiveness Using Delay and Bandwidth Information,” IEICE Technical Report CQ2007-18, July 2007. Kawahara, E .; K. Lua, Kamei, Yoshino, Uchida, “Performance evaluation of QoS overlay routing and application to various QoS metrics,” IEICE Technical Report, IN2007-44, September 2007.

  The problem to be solved is that, in the conventional technology in which multiple end hosts self-select the best quality overlay route based on measured communication quality, the traffic is concentrated on the same route. There is a risk of causing congestion.

  The object of the present invention is to solve these problems of the prior art, and to avoid the concentration of traffic accompanying the selection of the communication path in the overlay network without impairing the communication quality of the end host. It is to improve.

  In order to achieve the above object, according to the present invention, when one communication path is selected from a plurality of data communication path candidates provided in the overlay network, the communication path quality acquisition unit performs an average round trip time (RTT: Round). The quality of each communication path specified based on predetermined criteria such as Trip Time), average packet loss rate, or average throughput is acquired from the overlay network, stored in the storage device in the communication path quality storage unit, and communicated In the route selection unit, the communication route used for data communication is selected with a probability corresponding to the quality stored in the communication route quality storage unit. For example, a probability distribution based on a weighted average is generated from the quality of each communication path stored in the communication path quality storage unit, and a communication path used when performing data communication according to the generated probability distribution is selected. Then, every time data communication on the communication path selected by the communication path selection unit is completed, the communication path quality update unit acquires the communication quality of all communication paths from the overlay network and stores it in the communication path quality storage unit. Update the quality of each communication path. At this time, the communication path quality update unit calculates an update value of the quality of each communication path by an online prediction algorithm based on learning theory using cumulatively the communication quality of each communication path acquired every time data communication is completed. To do. For example, in “Y.Fund and R. Shapire,“ A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, ”Journal of Computer and Scheme 97. By applying and selecting the communication route in the overlay network, the end host communication quality is inferior to the best communication quality when the same overlay route is selected for a certain period of time in the past. To.

  According to the present invention, it is possible to avoid the traffic concentration accompanying the selection of the communication path in the overlay network without impairing the communication quality of the end host, and it is possible to improve the communication quality in the overlay network.

  The best mode for carrying out the present invention will be described below with reference to the drawings. FIG. 2 is a block diagram showing a configuration example of a network to which an overlay network route selection system according to the present invention is provided, and FIG. 3 is a first diagram of a network provided with the overlay network route selection system according to the present invention. 4 is a block diagram showing a configuration example, FIG. 4 is a block diagram showing a second configuration example of a network provided with the overlay network route selection system according to the present invention, and FIG. 5 is a process of the overlay network route selection method according to the present invention. It is a block diagram which shows an operation example.

  FIG. 2 shows an example of the basic configuration of an overlay network and an IP network to which the overlay network routing system according to the present invention is applied.

  It is assumed that the overlay nodes 21a to 21e forming the overlay network 21 are logically connected. The logical connection means that the IP address of the connection destination overlay node is known and communication is possible.

  The IP network 22 is composed of a number of routers 22a to 22g. Further, although the traffic management server 23 for managing the quality information of the overlay nodes 21a to 21e and the routers 22a to 22g in an integrated manner is provided, the traffic management server 23 may not be provided.

  The traffic management server 23 and the overlay nodes 21a to 21e each have a computer configuration including a CPU (Central Processing Unit), a main memory, a display device, an input device, an external storage device, and the like. After the program or data recorded in the storage medium such as the above is installed in the external storage device, the function of each processing unit is executed by reading the program or data from the external storage device into the main memory and processing it by the CPU.

  As described above, in this example, it is assumed that there is an overlay network 21 that is a logical network constructed by several overlay nodes 21 a to 21 e connected to the IP network 22, and traffic information measured in the IP network 22 is displayed on the overlay network 21. A cooperative system of the IP network 22 and the overlay network 21 as used for control in the network 21 is assumed, and each overlay node 21a to 21e can be selected as a route candidate in the overlay network.

  3 shows a configuration in which the central management server 30 having the function of the overlay network routing system according to the present invention is provided in the network shown in FIG. 2, and in FIG. 4, the network shown in FIG. The structure which provided the route selection apparatus 40a-40k provided with the function of the overlay network route selection system which concerns on invention is shown.

  3 and 4, 31a to 31s are overlay nodes, 32a to 32k are IP network areas, the central management server 30 in FIG. 3, the route selection devices 40a to 40k in FIG. 4, and the overlay nodes 31a to 31s. Each has the same computer configuration as the traffic management server 23 and overlay nodes 21a to 21e described in FIG.

  In the centralized management server 30 of FIG. 3, a route selection system 30a having a function as an overlay network route selection system according to the present invention shown in FIG. 3B is provided. As means / functions for executing programmed computer processing, a communication path quality acquisition unit 30b, a communication path quality information storage unit 30c, a communication path selection unit 30d, and a communication path quality update unit 30e are provided.

  The centralized management server 30 of FIG. 3 equipped with the route selection system 30a having such a configuration selects a communication route from a plurality of data communication route candidates provided by the overlay network. In 30b, the quality information of each communication path specified based on a predetermined standard such as the average round trip time (RTT), the average packet loss rate, or the average throughput is used as the overlay nodes 31a to 31s forming the overlay network. And is stored in the storage device in the communication path quality storage unit 30c, and the communication path selection unit 30d selects the communication path used when performing data communication according to the quality stored in the communication path quality storage unit 30c. With a certain probability.

  For example, a probability distribution based on a weighted average is generated from the quality of each communication path stored in the communication path quality storage unit 30c, and a communication path used when performing data communication according to the generated probability distribution is selected.

  Then, the centralized management server 30 in FIG. 3 has each of the overlay nodes 31a to 31s forming the overlay network each time the data communication on the communication path selected by the communication path selection unit 30d is completed in the communication path quality update unit 30e. The communication quality of all the communication paths is acquired from the above, and the quality of each communication path stored in the communication path quality storage unit 30c is updated.

  At this time, the communication path quality update unit 30e cumulatively uses the communication quality of each communication path acquired every time data communication is completed, and uses the online prediction algorithm based on the learning theory to calculate the update value of the quality of each communication path. calculate.

  For example, in “Y.Fund and R. Shapire,“ A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, ”Journal of Computer and Scheme 97. Apply and select the communication route in the overlay network.

  As a result, the communication quality of the end host can be made inferior to the best communication quality among the communication qualities when the same overlay route is continuously selected for a certain period in the past.

  The details of the first technique relating to the operation of the route selection system 30a in the centralized management server 30 shown in FIG. 3 will be described below.

  In the first technique, as a device for determining a route in the overlay network, a centralized management server 30 that acquires and manages route quality information (delay time, throughput, etc.) in each overlay network from each overlay node 31a to 31s. Is used.

  The central management server 30 manages quality information for each pair of transmission area and destination area in the areas 32a to 32k of the IP network, and overlay nodes 31a to 31s at a certain timing (for each transmission packet, every fixed period, for each communication, etc.). Get quality information from and update.

  When a route query is generated from an end host in the areas 32a to 32k of the IP network and received, the central management server 30 follows the stochastic route recommendation algorithm weighted by the cumulative quality of each overlay route. It has a function (route selection system 30a) that selects one route and recommends it to the end host, and specifically follows the following operation.

  Here, the number of areas (32a to 32k) managed by the centralized management server 30 is K, and the number of selection target overlay paths i that can be recommended as overlay paths is N (i = 1, 2,..., N). . Further, communication from one area to another area is identified by rε {1, 2,..., K} × {1, 2,..., K}, and the following information is managed for each communication r.

  Numbering is performed with “1” as the first time for the timing of communication. This number is called time and is represented by “t”. Further, the weight of the overlay route i at time t is expressed as “w_i, t”.

  The following is applied as a communication path selection algorithm recommended for the communication r.

  As an initial setting, the central management server 30 sets initial weights w_i, 1 = 1 / N for each overlay route i (i = 1, 2,..., N).

  Then, the central management server 30 executes the following processes (1) to (3) at times t = 1, 2,...

  (1) The centralized management server 30 selects the communication path i according to the probability distribution pt = (v_1, t,..., V_N, t) and recommends it to the communication r. Here, “v_i, t = w_i, t ÷ Σw_j, t”.

  (2) The centralized management server 30 acquires the communication quality information l_t = (l_1, t,... L_N, t) at the time from each overlay node.

(3) The centralized management server 30 updates the weight of each overlay route to “w_i, t + 1 = w_i, t × β ^{l_i, t} ”. Note that the parameter βε (0, 1).

  Hereinafter, when performing route selection in the overlay network using the first technique as described above, an explanation will be given of an embodiment in which an average round trip time per packet in one communication (file transmission / reception, etc.) is used as quality information. Do.

  The central management server 30 acquires the above quality information from each of the overlay nodes 31a to 31s at an arbitrary timing. The method of measuring the quality information depends on the mounting of the overlay nodes 31a to 31s, but it is sufficient that the latest past information is acquired.

  In FIG. 3, the central management server 30 divides the IP network into K areas (32a to 32k), and a set of (K-1) × (K-1) transmission source areas and destination areas. The communication path quality information storage unit 30c includes a table for managing the weights of N overlay communication paths.

  At the start of operation, all values in the table are initialized with a real value “1 ÷ N”. In addition, a parameter β∈ (0, 1) is input. This parameter β can also be set individually for each pair of source and destination.

  The above is the initial setting, and the processing operation by the route selection system 30a of the central management server 30 for route inquiry from the end nodes in each of the areas 32a to 32k will be described.

  The route selection system 30a of the centralized management server 30 acquires a transmission source area and a destination area at the time of route inquiry from an end node, and stores information on the corresponding communication from a table stored and managed by the communication route quality information storage unit 30c. Refer to the weight of each overlay communication path.

  The central management server 30 does not manage the number of inquiries from the end node, but if the cumulative number of inquiries from the end node to the present is t for convenience, the weight of each overlay communication path referred to here is “w_i”. , T ”(i = 1, 2,..., N).

  For example, the weight of each overlay communication path at the time of inquiry of the source / destination pair immediately after initialization is “w_i, 1 = 1 ÷ N” (i = 1, 2,..., N).

  Then, the centralized management server 30 selects a recommended communication path (overlay communication path) according to the distribution of the probability distribution “p_i, t = w_i, t ÷ Σw_j, t”, and returns the selected communication path to the inquiry end node.

  Note that the end node transmits data according to a route recommended by the central management server 30. Further, after the end of data transmission, the end node notifies the central management server 30 of the end.

  When the central management server 30 receives the data transmission end notification from the end node, the communication path quality update unit 30e in the path selection system 30a acquires the quality information about each overlay communication path from the overlay node. The quality information of each overlay node acquired here is expressed as “c_i, t”.

Then, the communication path quality update unit 30e sets the weight of each overlay node as “w_i, t + 1 = w_i, t × β ^{c_i, t} ”, and the table stored and managed by the communication path quality information storage unit 30c. Update the contents of.

  The central management server 30 performs the above-described series of procedures independently for each pair of the transmission source area and the destination area.

  Next, details of the second technique, which is an overlay network route selection operation according to the present invention by the route selection devices 40a to 40k in the network configuration shown in FIG. 4, will be described.

  In the second technique, as a device for determining a route in the overlay network, a route selection device 40a that acquires and manages route quality information (delay time, throughput, etc.) in each overlay network from each overlay node 31a to 31s. Use ~ 40k. The route selection devices 40a to 40k are provided in a subscriber termination device or the like.

  Similarly to the centralized management server 30 in FIG. 3, the route selection devices 40a to 40k include a route selection system 30a shown in FIG. 3B. In this route selection system 30a, the destination area ( 32a to 32k), quality information is recorded and managed, and quality information of each overlay path (communication path) is acquired at a certain timing.

  Then, the route selection devices 40a to 40k perform the following specific operations by the route selection system 30a using a stochastic route selection algorithm weighted by the cumulative quality of each overlay route.

  Assume that the number of areas (32a to 32k) managed by the route selection devices 40a to 40k is K, and the number of overlay routes to be selected is N. Further, communication to a certain area is identified by rε {1, 2,..., K}, and the following information is managed for each communication r.

  For the timing at which the route selection devices 40a to 40k select and communicate one of N overlay route candidates, the first time is numbered as "1". This number is called time and is represented as “t”. Further, the weight of the overlay route i at time t is expressed as “w_i, t”.

  The following is applied as a communication path selection algorithm to be selected for the communication r.

  As an initial setting, initial weights “w_i, 1 = 1 ÷ N” are set for all overlay routes i (i = 1, 2,..., N).

  Then, for each time t = 1, 2,..., The following processes (1) to (3) are executed.

  (1) The route selection devices 40a to 40k select the communication route i according to the probability distribution pt = (v_1, t,..., V_N, t). Here, “v_i, t = w_i, t ÷ Σw_j, t”.

  (2) The route selection devices 40a to 40k acquire the communication quality information l_t = (l_1, t,... L_N, t) at each time from each overlay node.

(3) The route selection devices 40a to 40k update the weight of each communication route (overlay route) to “w_i, t + 1 = w_i, t × ^{βl_i, t} ”. Note that the parameter βε (0, 1).

  Hereinafter, when performing route selection in the overlay network using the second technique, description will be given of an embodiment in which an average round trip time per packet in one communication (such as file transmission / reception) is used as quality information. Do.

  The route selection devices 40a to 40k obtain the above-described quality information from the overlay nodes 31a to 31s at an arbitrary timing. The method of measuring the quality information depends on the mounting of the overlay nodes 31a to 31s, but it is sufficient that the latest past information is acquired.

  In FIG. 4, the route selection devices 40a to 40k divide the IP network into K areas (32a to 32k), and weights of N overlay communication routes for (K-1) destination areas. In the communication route quality information storage unit 30c of the route selection system 30a.

  At the start of operation, all values in the table are initialized with a real value “1 ÷ N”. In addition, a parameter β∈ (0, 1) is input. This parameter β can also be set individually for each destination.

  The above is the initial setting, and the processing operation by the route selection system 30a of the route selection devices 40a to 40k based on such initial setting will be described.

  The route selection system 30a of the route selection devices 40a to 40k refers to the weight of each overlay communication route for the destination area from the table stored and managed by the communication route quality information storage unit 30c when selecting a route at the end node. .

  The route selection system 30a does not manage the number of route selection operations, but for convenience, if the cumulative selection processing count up to now is “t”, the weight of each overlay communication route referred to here is “w_i, t ”(i = 1, 2,..., N).

  For example, the weight of each overlay communication path in the path selection to the destination immediately after initialization is “w_i, 1 = 1 ÷ N” (i = 1, 2,..., N).

  Then, the route selection system 30a selects a communication route (overlay communication route) according to the distribution of the probability distribution “p_i, t = w_i, t ÷ Σw_j, t”, and starts communication.

  When the data transmission is completed, the route selection system 30a of the route selection devices 40a to 40k acquires the quality information about each overlay communication route from the overlay node by the communication route quality update unit 30e. The quality information of each overlay node acquired here is expressed as “c_i, t”.

Then, the communication path quality update unit 30e sets the weight of each overlay node as “w_i, t + 1 = w_i, t × β ^{c_i, t} ”, and the table stored and managed by the communication path quality information storage unit 30c. Update the contents of.

  The route selection devices 40a to 40k perform the above-described series of procedures independently for each destination area by the route selection system 30a.

  When the communication route (overlay route) in the overlay network is selected by the first and second techniques described above, the expected value “Σp_t · l_t” of the cumulative communication quality of each communication is the communication quality measured so far. The best “minΣl_i, t” of the cumulative communication quality of each overlay path in the information can be suppressed as shown by the following equation (1).

  However, the above equation (Equation 1) is for a measure that favors a small numerical value, such as a delay time, as communication quality. In the formula (1), “T” is the elapsed time up to the present, and “M” is the worst value of the communication quality measured up to the present.

  In the above example, the average round trip time (RTT) per packet in one communication (such as file transmission / reception) is used as the communication quality of the overlay path. However, the present invention is not limited to this. Instead, for example, the average delay time per communication may be used as the communication path quality. In this case, since a route is selected for each communication in this example, reverse arrival order of packets due to arrival delay can be avoided.

  Further, the average throughput per communication may be used as the quality information of the overlay route. In this case, α∈ (1, ∞) is used as a parameter of the route recommendation algorithm or the route selection algorithm.

  Furthermore, a score combining delay time, throughput, or other measurable quality information may be used as the communication quality of the overlay route. This makes it possible to select a route when composite communication quality is used as an evaluation measure.

  The timing (timing) for acquiring quality information of each overlay route is the combination of the next communication when it occurs or periodically, or when the communication ends and when the next communication occurs and periodically It may be done.

  Next, the processing operation according to the present invention of the route selection system 30a shown in FIG. 3B will be described with reference to FIG.

  The route selection system 30a provided in the centralized management server 30 in FIG. 3 or the route selection devices 40a to 40k in FIG. 4 selects one communication route from a plurality of data communication route candidates provided in the overlay network. As a function of executing the programmed computer processing, the communication path quality acquisition unit 30b, the communication path quality storage unit 30c, the communication path selection unit 30d, and the communication path quality update unit 30e are provided. In the acquisition unit 30b, the quality information of each communication path specified on the basis of a predetermined standard such as an average round trip time (RTT), an average packet loss rate, or an average throughput is converted into each overlay node ( 31a to 31s) (step S50) ), Stores and stored in the storage device in the communication path quality storage unit 30c (step S502).

  In this state, waiting for the start of data communication (step S503), and before the predetermined time (T) elapses (step S504), when the data communication starts, the communication path selection unit 30d performs data communication. The communication path used at this time is selected with a probability corresponding to the quality stored in the communication path quality storage unit 30c (step S505).

  Thereafter, or when a predetermined time (T) elapses before data communication starts in step S504, the process returns to step S501, and the communication path quality update unit 30e determines the quality of each communication path. Information is acquired from each overlay node (31a to 31s), and the communication path quality storage unit 30c overwrites and updates the communication quality information stored / stored in the storage device.

  Here, the timing of communication path quality acquisition by the communication path quality acquisition unit 30b and the timing of communication path quality update by the communication path quality update unit 30e are a combination of the occurrence of communication and a regular period.

  The communication path quality acquisition unit 30b acquires any of the quality measures in data communication including the average round trip time, the average packet loss rate, and the average throughput as the quality of the communication path, and the communication path quality storage unit 30c Stores the quality of the communication path acquired by the communication path quality acquisition unit 30b.

  Further, the communication path selection unit 30d generates a probability distribution by weighted average from the quality of each communication path stored in the communication path quality storage unit 30c, and the communication path used when performing data communication according to the generated probability distribution. Make a selection.

  Further, the communication path quality update unit 30e calculates an update value of the quality of each communication path by an online prediction algorithm based on a learning theory using cumulatively the communication quality of each communication path acquired every time data communication is completed. To do.

  For example, the communication path quality update unit 30e uses a hedge algorithm as an online prediction algorithm.

Further, the communication path quality storage unit 30c uses a weight “w_i, 1” which is a weighted average value for the quality of each communication path as an initial value of the quality of the communication path i (i = 1, 2,..., N). = 1 ÷ N ”, and the communication path quality update unit 30e performs the time t (t = 1, t) when the data communication occurs for the initial weight“ w_i, 1 ”(= 1 ÷ N) of the communication path i. 2), the quality information l_t (= l_1, t,... L_N, t) of each communication path is acquired from each overlay network, and the quality weight of each communication path is set to “w_i, t + 1 = w_i”. , T × β ^{l — i, t} ”, (βε (0, 1)), the communication path selection unit 30d generates a probability distribution pt“ = ”by weighted average of communication quality when data communication r occurs at time t. v_1, t, ..., v_N, t ", (v_i, t = w_i, t / w_j, according t) ", to select a communication path.

  In addition, when the data communication r occurs at the time t, the communication path selection unit 30d selects a communication path weighted with communication probability with the probability in the probability distribution pt.

  For example, the communication path selection unit 30d randomly calculates a value A of 0 to 1 using a random function when the data communication r occurs at time t, and the calculated value A is calculated in advance for each communication quality in the probability distribution pt. It is specified which of the ranges associated with each of the weighting probabilities is included, and a communication path having a communication quality with a weight corresponding to the specified range is selected.

  Hereinafter, overlay network route selection processing performed by the route selection system 30a using the communication route quality acquisition unit 30b and the communication route quality storage unit 30c, and the communication route selection unit 30d and the communication route quality update unit 30e is performed. This will be described using a specific example.

  Here, to simplify the description, for example, the quality (weight) of the first route is “0.1”, the quality (weight) of the second route is “0.15”, and the third route A route selection procedure in a simple case where the quality (weight) of the route is “0.05” and the quality (weight) of the fourth route is “0.2” will be described.

  Thus, in this example, assuming that there are four routes, the weights are “w — 1, t = 0.1”, “w — 2, t = 0.15”, “w — 3, t = 0.05”, “ w_4, t = 0.2 ".

  Here, “Σw_j, t = 0.1 + 0.15 + 0.05 + 0.2 = 0.5”, and normalizing each weight (adjusting so that Σp_i, t = 1 while maintaining the ratio) “P — 1, t = 0.2” (first route), “p — 2, t = 0.3” (second route), “p — 3, t = 0.1” (third route), “p — 4 , T = 0.4 ”(fourth route).

  Then, a random function is used to output a value of “0 to 1” uniformly and randomly, and by setting the interval using the probability distribution, the probability corresponding to the communication quality is as follows. It is possible to select a communication path at. The random function is assumed to be general purpose.

  That is, when the output of the random function is A, when A is 0 or more and less than 0.2, the first path is selected, and when A is 0.2 or more and less than 0.5, the second path is selected. A route is selected, and further, when A is 0.5 or more and less than 0.6, a third route is selected, and when A is 0.6 or more and 1.0 or less, a fourth route is selected.

  In addition, when a plurality of routes have the same random variable, a plurality of routes are selected. In this case, the routes are arbitrarily selected with equal probability.

  As described above with reference to FIGS. 1 to 5, in this example, when one communication path is selected from a plurality of data communication path candidates provided by the overlay network, the communication path quality acquisition unit 30 b The quality of each communication path specified based on a predetermined standard such as average round trip time, average packet loss rate or average throughput is acquired from the overlay network and stored in the storage device in the communication path quality storage unit 30c. Then, the communication path selection unit 30d selects a communication path used when performing data communication with a probability corresponding to the quality stored in the communication path quality storage unit 30c.

  For example, a probability distribution based on a weighted average is generated from the quality of each communication path stored in the communication path quality storage unit 30c, and a communication path used when performing data communication according to the generated probability distribution is selected.

  Then, every time data communication on the communication path selected by the communication path selection unit 30d is completed in the communication path quality update unit 30e, the communication quality of all communication paths is acquired from the overlay network, and the communication path quality storage unit 30c. The quality of each communication path stored in is updated.

  At this time, the communication path quality update unit 30e cumulatively uses the communication quality of each communication path acquired every time data communication is completed, and uses the online prediction algorithm based on the learning theory to calculate the update value of the quality of each communication path. calculate.

  For example, in “Y.Fund and R. Shapire,“ A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, ”Journal of Computer and Scheme 97. Apply and select the communication route in the overlay network.

  By doing in this way, the communication quality of the end host can be made inferior to the best communication quality among the communication qualities when the same overlay route is continuously selected for a certain period in the past.

  In addition, as above-mentioned, this invention is not limited to the example demonstrated using FIGS. 1-5, In the range which does not deviate from the summary, various changes are possible. For example, the computer configuration example of this example may 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 an overlay network. It is a block diagram which shows the structural example of the network used as the object which provides the overlay network path | route selection system which concerns on this invention. It is a block diagram which shows the 1st structural example of the network which provided the overlay network route selection system which concerns on this invention. It is a block diagram which shows the 2nd structural example of the network which provided the overlay network route selection system which concerns on this invention. It is a block diagram which shows the processing operation example of the overlay network path | route selection method based on this invention.

Explanation of symbols

  1-3, 21a-21e, 31a-31s: overlay node, 4, 21: overlay network, 5-9, 22a-22g: IP router, 10, 22: IP network, 23: traffic management server, 30: centralized management Server, 30a: Route selection system, 30b: Communication route quality acquisition unit, 30c: Communication route quality information storage unit, 30d: Communication route selection unit, 30e: Communication route quality update unit, 32a to 32k: Area (IP network area) , 40a to 40k: route selection device.

Claims (10)

An overlay network route selection system that selects one communication route from a plurality of data communication route candidates provided by an overlay network composed of overlay nodes logically formed on an IP network by programmed computer processing. And
As a means of performing programmed computer processing,
Communication path quality storage means for storing the quality of each communication path specified on the basis of a predetermined criterion;
A communication path selection means for selecting a communication path used when performing data communication with a probability corresponding to the quality stored in the communication path quality storage means;
Each time data communication on the communication path selected by the communication path selection means is completed, the communication quality of all communication paths is acquired from the overlay network and stored in the communication path quality storage means. An overlay network route selection system comprising communication route quality update means for updating quality. The overlay network routing system of claim 1, comprising:
As a means of performing programmed computer processing,
Communication path quality acquisition means for acquiring any of the quality measures in data communication including the average round trip time, average packet loss rate, and average throughput as the quality of the communication path,
The overlay network path selection system, wherein the communication path quality storage means stores the quality of the communication path acquired by the communication path quality acquisition means. An overlay network routing system according to claim 1 or claim 2,
The communication path selection means is
An overlay characterized by generating a probability distribution by weighted average from the quality of each communication path stored in the communication path quality storage means and selecting a communication path to be used when performing the data communication according to the generated probability distribution Network routing system. An overlay network routing system according to any of claims 1 to 3,
The communication path quality update means
An overlay network path characterized by calculating an update value of the quality of each communication path by an online prediction algorithm based on learning theory using cumulatively the communication quality of each communication path acquired every time data communication is completed Selection system. An overlay network routing system according to claim 4,
An overlay network route selection system, wherein the communication route quality update means uses a hedge algorithm as the online prediction algorithm. An overlay network routing system according to any of claims 1 to 5, comprising:
The communication path quality storage means is
As an initial value of the quality of the communication path i (i = 1, 2,..., N), a weight “w_i, 1 = 1 ÷ N” that is a weighted average value for the quality of each communication path is stored.
The communication path quality update means
For the initial weight “w_i, 1” (= 1 ÷ N) of the communication path i,
Quality information l_t (= l_1, t,... L_N, t) of each communication path at the occurrence time t (t = 1, 2,...) Of data communication r is acquired from each overlay network, and the quality of each communication path is obtained. , And update the weight to “w_i, t + 1 = w_i, t × β ^{l_i, t} ”, (β∈ (0, 1))
The communication path selection means is
When data communication r occurs at time t,
An overlay characterized by selecting a communication path according to the probability distribution pt “= v — 1, t,... Network routing system. The overlay network routing system according to claim 6, comprising:
The communication path selection means is
When data communication r occurs at time t,
An overlay network route selection system, wherein a communication route weighted with communication probability is selected based on the probability in the probability distribution pt. The overlay network routing system according to claim 6, comprising:
The communication path selection means is
When data communication r occurs at time t,
A random function is used to randomly calculate a value A between 0 and 1,
Specify which of the ranges in which the calculated value A is included in advance for each probability of weighting of each communication quality in the probability distribution pt,
An overlay network route selection system, wherein a communication route having a communication quality with a weight corresponding to a specified range is selected. A method of selecting one communication path from among a plurality of data communication path candidates provided by an overlay network logically formed on an IP network by programmed computer processing,
As a programmed computer procedure,
A processing procedure executed by each unit in the overlay network routing system according to claim 1,
By the processing procedure of each means,
An overlay network route selection method, wherein one communication route is selected from the plurality of data communication route candidates each time data communication is performed.   The program for functioning a computer as each means in the overlay network routing system in any one of Claims 1-8.

Images