JP2006245874A - Communication path computation system and communication path computation method using partial measurement in overlay network, and program therefor - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To curtail an amount of computation broadly by computing by using quality information measured partially between partial overlay nodes. <P>SOLUTION: In a means for measuring communication quality q(t, c<SB>i, 1</SB>, c<SB>j, 1</SB>) at a time t between representative nodes, to set a best-fit path from a node c<SB>i, k</SB>to a node c<SB>j, 1</SB>at time a t of communication, a value v' of v is acquired so that q(t, c<SB>i, 1</SB>, c<SB>v, 1</SB>)+q(t, c<SB>v, 1</SB>, c<SB>j, 1</SB>) is minimized, and q(t, c<SB>i, 1</SB>, c<SB>j, 1</SB>) is compared with q(t, c<SB>i, 1</SB>, c<SB>v', 1</SB>)+q(t, c<SB>v', 1</SB>, c<SB>j, 1</SB>). When the former is smaller, a communication path is set as q(c<SB>i, k</SB>→ c<SB>j, 1</SB>), and when the latter is smaller, the communication path is set as c<SB>i, k</SB>→ c<SB>v', 1</SB>→ c<SB>j, 1</SB>. Note that when q(t, c<SB>i, k</SB>, c<SB>j, 1</SB>) or q(t, c<SB>i, 1</SB>, c<SB>j, 1</SB>) is smaller than a threshold, the communication path is set as c<SB>i, k</SB>→ c<SB>j, 1</SB>, and when greater, the communication path may be computed by the above algorithm. <P>COPYRIGHT: (C)2006,JPO&NCIPI

Description

  The present invention relates to a communication path calculation system, a communication path calculation method, and a program therefor that can improve end-to-end communication quality in an IP network.

  The Internet has been developed and spread to accommodate a variety of applications, and nowadays it can also accommodate real-time applications that are sensitive to VoIP (Voice over IP) and QoS (Quality of Service) such as streaming. It is progressing rapidly.

  Along with this, it is an important issue to realize end-to-end congestion avoidance technology and quality improvement technology --- end-to-end QoS management technology-on the Internet. ing.

However, there are the following problems in realizing such a technique.
(A) 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.

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

  Under these circumstances, QoS management technology using an overlay network is attracting attention as a promising technology capable of improving end-to-end QoS without changing the lower network layer (see Non-Patent Document 1).

  An overlay network is a network that uses an existing link to form a logical (virtual) link according to the purpose in the upper layer (see Non-Patent Document 2).

The basic concept of QoS management by an overlay network is illustrated in FIG.
In FIG. 5, it is assumed that traffic flows from x to y along a route through IP routers R1, R2, and R3 represented by dotted arrows. 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 an overlay network (Overlay NW) formed by overlay nodes a, b, and c, a route (x → overlay node a → overlay node b → overlay node c → y) represented by a solid line arrow is used. If the traffic can be detoured, the above congestion can be avoided.

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

L. Zhi and P. Mohapatra, “QRON: QoS-aware routing in overlay networks,” IEEE J. Select. Areas Commun., Vol. 22, pp. 29-40, January 2004. WIDE Project, “Integrated Distributed Environment by Overlay Network” WIDE Project Research Report, Part 17, 2002. Kamei, Kawahara “Traffic Engineering with End-Host Overlay Network and Its Effectiveness” Shingaku Sodai, BS-5-3, 2004. S. Rewaskar and J. Kaur, “Testing the Scalability of Overlay Routing Infrastructures,” Proc. PAM 2004, April 2004. S. Banerjee, T. G. Griffin and M. Pias, “The Interdomain Connectivity of PlanetLab Nodes”, Proc. PAM 2004, April 2004.

  However, these results are evaluations when the ideal network is calculated using quality information measured between all overlay nodes with the overlay network topology set to full mesh, and the total number of overlay nodes It does not take into account the decrease in scalability when the value increases.

  That is, when the total number of overlay nodes is large, it is practically impossible to calculate the communication path after measuring quality information between all the overlay nodes because the calculation amount is enormous. There's a problem.

  In view of the above problems, the object of the present invention is not to measure quality information among all overlay nodes but to calculate using quality information partially measured between some overlay nodes. It is an object of the present invention to provide a communication path calculation system and method, and a program therefor, which can greatly reduce the amount of calculation.

  In order to achieve the above object, in the present invention, a communication path is calculated using only quality information measured between representative nodes of each cluster in an overlay network clustered in advance. As a result, even when the total number of overlay nodes is large, the amount of calculation is reduced, and communication paths that can improve end-to-end communication quality in the IP network can be calculated.

  More specifically, in order to calculate a communication path, the present invention includes the following means.

(A) Means (i, j = 1, 2,..., M, i ≠ j) for measuring the communication quality q (t, c _{i, 1} , c _{j, 1} ) at time t between representative nodes

(B) Means (k = 1, 2,..., Ni, l = 1, 2) for calculating the optimum route at time t of communication from the node c _{i, k} to the node c _{j, 1} in the following procedure. , ..., nj)
<Step 1>: q (t, c _{i, 1} , c _{v, 1} ) + q (t, c _{v, 1} , c _{j, 1} ) obtains the minimum value v ′ of v (v ′ = 1) , 2,..., M, v ′ ≠ i, j).
<Step 2>: q (t, ci _{, 1} , _{cj, 1} ) and q (t, ci _{, 1} , _{cv ′, 1} ) + q (t, _{cv ′, 1} , _{cj, 1} ) If the former is small, the communication path is set as ci _{, k.fwdarw.cj, l.} If the latter is small, the communication path is set as ci _{, k.fwdarw.cv ' , 1.fwdarw.cj, l} .

If q (t, ci _{, k} , _{cj, l} ) or q (t, ci _{, 1} , _{cj, 1} ) is smaller than a predetermined threshold, the communication path is designated ci _{, k} → c _{j, l,} and if larger, the communication path may be calculated according to the above steps <Step 1> and <Step 2>.

  As described above, according to the present invention, communication path calculation is performed by using only quality information partially measured between some overlay nodes without measuring quality information between all overlay nodes. It can be carried out. Further, since the QoS can be improved by using the calculated communication path, the communication path calculation according to the present invention is useful.

  The best mode for carrying out the present invention will be described below with reference to the drawings.

  FIG. 1 is an explanatory diagram for explaining an embodiment of the present invention, FIG. 2 is a block diagram showing a configuration example of a communication path calculation system according to the present invention, and FIG. 3 is a procedure example of the communication path calculation system according to the present invention. It is a flowchart which shows.

Note that all nodes belonging to the overlay network in advance and m are classified into individual clusters, the clusters C1, C2, write and · · · Cm, the nodes belonging to the cluster Ci _{c i,} 1, _{c i , 2} ,..., Ci _{, ni} (i = 1, 2,..., M). Therefore, when the total number of nodes belonging to the overlay network is n, the n = n1 + n2 + ···· + n m.

Further, it is assumed that a unique representative node is set in advance for each cluster Ci, and that it is set as ci _{, 1} (i = 1, 2,..., M) without loss of generality. Furthermore, it is assumed that the standard of the communication quality q referred to when calculating the communication path is set in advance.

  As the standard of the communication quality q, for example, the delay time d (t, a, b) between the nodes a and b at the time t is used, or the delay time d (t, a, b) is used instead of the delay time d (t, a, b). Any of statistical values such as a minimum value, an average value, or a maximum value within a predetermined time of d (t, a, b) may be used.

  Further, as the standard of the communication quality q, for example, the packet loss rate p (t, a, b) between the nodes a and b at the time t is used, and the communication quality q (t, a, b) = − log (1 -P (t, a, b)) or the minimum of the packet loss rate p (t, a, b) within a predetermined time instead of the packet loss rate p (t, a, b) in the above formula Any of statistical values such as a value, an average value, or a maximum value may be used.

The operation when a communication request from the node c _{a, x} to the node c _{b, y} occurs at time t (step S1) will be described.

  At this time, the communication path calculation unit 1 calculates a path using the communication quality information between the representative nodes stored in the information storage unit 2 (step S2).

  Note that the communication path calculation unit 1 may be provided in all overlay nodes, may be provided only in some overlay nodes (for example, representative overlay nodes), or is not an overlay node. It may be deployed in another node (for example, an external server).

  On the other hand, the communication quality measurement unit 3 measures the communication quality between representative nodes for each predetermined unit time for all combinations of grounds of representative nodes regardless of whether or not a communication request is generated. The measurement results are stored in the information storage unit 2 in a concentrated or distributed manner (step S4).

The stored information is, for example, communication quality q (t, c _{1, ni} , c _{1, nj} ) (i, j = 1, 2,..., M, i ≠ j).

  Details of the route calculation procedure (step S2) in the communication route calculation unit 1 are as follows.

<Step S2-1>: The value v ′ of v at which q (t, c _{a, 1} , c _{v, 1} ) + q (t, c _{v, 1} , c _{b, 1} ) is minimized is obtained.

<Step S2-2>: q (t, c _{a, 1} , c _{b, 1} ) and q (t, c _{a, 1} , c _{v ′, 1} ) + q (t, c _{v ′, 1} , c _{b, 1} ), if the former is small, the communication path is set to ca _{, x} → c _{b, y,} and if the latter is small, the communication path is set to ca _{, x} → c _{v ′, 1} → c _{b, y} . .

However, when q (t, c _{a, x} , c _{c, y} ) or q (t, c _{a, 1} , c _{b, 1} ) is separately measured and the value is smaller than a predetermined threshold value The communication path may be c _{a, x} → c _{b, y,} and if larger, the communication path may be calculated according to the procedure of <Step S2-1> and <Step S2-2>.

  The above processes in the communication path calculation unit 1, the information storage unit 2, and the communication quality measurement unit 3 are computerized and distributed via a recording medium such as a CD-ROM, FD, or DVD, or a network such as the Internet. Can be made.

  The user installs the programs obtained via these recording media and networks into a computer and executes them by the CPU to perform the above-described processes in the communication path calculation unit 1, information storage unit 2, and communication quality measurement unit 3. realizable.

  In order to see the effect of the present invention, an evaluation result when the above procedure is executed using data measured on the actual Internet is shown.

  The data used for the evaluation is the delay measurement (ping) at each ground at a terminal contracted as a user with 18 geographically separated ISPs in Japan for 3 minutes at 1 packet per second per hour. (180 packets). The analysis target is the maximum delay time in the 3-minute measurement between the terminals x and y at the t-th time for each ground in the data for one day.

In this evaluation, geographically close nodes are grouped into four clusters (clusters: C1, C2, C3, and C4 (the number of nodes included in each cluster is 4, 4, 4, and 6), respectively. The representative nodes are appropriately calculated one by one for each cluster (representative nodes: c _1,1 , c _2,1 , c _3,1 , c _4,1 (in this evaluation, an appropriate representative node is The communication path was calculated using only the quality information measured between the representative nodes.

FIG. 4 shows the cumulative distribution (line ₁ ) of the maximum delay time when the communication path is calculated by the above method, and the above method is applied only when the maximum delay time of c _{a, 1} → c _{b, 1} exceeds 200 ms. The maximum delay time cumulative distribution (line 2) and the maximum delay time cumulative distribution (line 3) when the default route is used without calculating the communication route according to the present invention are shown.

  From this figure, it can be seen that when the maximum end-to-end delay time exceeds a certain threshold (200 ms in this case), the QoS can be improved by calculating the communication path by the method of the present invention.

It is a figure for demonstrating embodiment of this invention. It is a block diagram which shows the structural example of the communication path | route calculation system concerning this invention. It is a flowchart which shows the example of a procedure of the communication path | route calculation system concerning this invention. When the above method is applied only when the maximum delay time cumulative distribution (line1) and the maximum delay time of c _{a, 1} → c _{b, 1} exceed 200 ms when the communication path is calculated by the method of the present invention. It is a figure which shows the cumulative distribution (line 3) of the maximum delay time at the time of using the default path | route, without calculating the cumulative distribution (line 2) of a maximum delay time, and calculating the communication path | route by this invention. It is a figure which illustrates the basic concept of QoS management by an overlay network.

Explanation of symbols

1: communication path calculation unit 2: information storage unit 3: communication quality measurement unit c _{a, 1} , C _{b, 1} , C _v1,1 , C _V2,1 : representative node c _{a, 2} ,..., C _{a , x, ···, c a,} na, c b, 2, ···, c b, y, ··· c b, nb, c v1,2, c v1,3, ···, c v1 _{, Nv1} , _cv2 , _{2, cv2} , 3,..., _Cv2 , _nv2 : Nodes a, b, c: Overlay nodes R1 to R5: IP routers Ca, Cb, Cv1, Cv2: Cluster

Claims (9)

A communication path calculation system for calculating a communication path between any two nodes belonging to an overlay network logically formed on an IP network by using partial measurement in the network,
Wherein all nodes of m clusters C1 belonging to the overlay network, C2, ···, classified into Cm, the nodes belonging to the cluster _{Ci c i, 1, c i} , 2, ··· ,, c i, _ni, and a single representative node c _{i, 1} (i = 1, 2,..., m) is set in advance in each cluster Ci, and the time t for the two nodes a and b belonging to the overlay network is set. The communication quality when communicating from a to b on a default route in q is denoted as q (t, a, b), and when the route is denoted as a → b, the communication comprises the following means: Route calculation system.
(A) Means (i, j = 1, 2,..., M, i ≠ j) for measuring the communication quality q (t, c _{i, 1} , c _{j, 1} ) at time t between the representative nodes,
(B) The optimal route at time t of communication from c _{i, k} to c _{j, l} is q (t, c _{i, 1} , c _{v, 1} ) + q (t, c _{v, 1} , c _{j, 1} ) Obtains the minimum value v ′ of v (v ′ = 1, 2,..., M, v ′ ≠ i, j), q (t, c _{i, 1} , c _{j, 1} ) and q (t, c _{i, 1} , c _{v ′, 1} ) + q (t, c _{v ′, 1} , c _{j, 1} ) are compared, and if the former is smaller, the communication path is set to c _{i, k} → c _{j, l,} and when the latter is smaller, the means for calculating the communication path as c _{i, k} → c _{v ′, 1} → c _{j, l} (k = 1, 2,..., ni, l = 1) , 2, ..., nj) The communication path calculation system according to claim 1, further comprising:
q (t, c _{i, k} , c _{j, l} ) or q (t, c _{i, 1} , c _{j, 1} ) has a means for comparing a predetermined threshold value, and q (t, c _{i, If k} , c _{j, l} ) or q (t, c _{i, 1} , c _{j, 1} ) is smaller than the predetermined threshold, the communication path is set to c _{i, k} → c _{j, l} The communication path calculation system is characterized in that the processing of each means in (A) and (B) is performed when the threshold value is larger than a predetermined threshold value. A communication path calculation method for calculating a communication path between any two nodes belonging to an overlay network logically formed on an IP network by using partial measurement in the network,
Wherein all nodes of m clusters C1 belonging to the overlay network, C2, ···, classified into Cm, the nodes belonging to the cluster _{Ci c i, 1, c i} , 2, ··· ,, c i, _ni, and a single representative node c _{i, 1} (i = 1, 2,..., m) is set in advance in each cluster Ci, and the time t for the two nodes a and b belonging to the overlay network is set. The communication quality at the time of communication from a to b via a default route is denoted as q (t, a, b), and when the route is denoted as a → b, the communication comprises the following steps: Route calculation method.
(C) a step (i, j = 1, 2,..., M, i ≠ j) of measuring the communication quality q (t, c _{i, 1} , c _{j, 1} ) at time t between the representative nodes;
(D) The optimal route at time t of communication from c _{i, k} to c _{j, l} is q (t, c _{i, 1} , c _{v, 1} ) + q (t, c _{v, 1} , c _{j, 1} ) Obtains the minimum value v ′ of v (v ′ = 1, 2,..., M, v ′ ≠ i, j), q (t, c _{i, 1} , c _{j, 1} ) and q (t, c _{i, 1} , c _{v ′, 1} ) + q (t, c _{v ′, 1} , c _{j, 1} ) are compared, and if the former is smaller, the communication path is set to c _{i, k} → c _{If j and l} are smaller and the latter is smaller, the communication path is calculated as c _{i, k} → c _{v ′, 1} → c _{j, l} (k = 1, 2,..., ni, l = 1) , 2, ..., nj) The communication path calculation method according to claim 3, further comprising:
When q (t, ci _{, k} , _{cj, l} ) or q (t, ci _{, 1} , _{cj, 1} ) is smaller than a predetermined threshold, the communication path is designated ci _{, k} → c. _The communication path calculation method is characterized in that _{j and l} are set, and the processing of each step in (C) and (D) is sequentially performed when it is larger than a predetermined threshold value. In the communication path calculation method according to claim 3 or 4,
Using the delay time d (t, a, b) at the time t between the nodes a and b, the communication quality q (t, a, b) = d (t, a, b) a communication path calculation method. In the communication path calculation method according to claim 3 or 4,
A communication path characterized in that any one of a minimum value, an average value, and a maximum value of a delay time d (t, a, b) at a time t between the nodes a and b is used as the communication quality. Method of calculation. In the communication path calculation method according to claim 3 or 4,
Using the packet loss rate p (t, a, b) at time t between the nodes a and b, the communication quality q (t, a, b) = − log ( 1-p (t, a, b)). In the communication path calculation method according to claim 3 or 4,
As the communication quality, any one of a minimum value, an average value, and a maximum value at a predetermined time of the packet loss rate p (t, a, b) at the time t between the nodes a and b is used. Route calculation method.   A communication path calculation program for causing a computer to execute the processing of each step in the communication path calculation method according to claim 3.

Images