JP7619487B2 - Distributed computing method, distributed computing device, and program - Google Patents

Description

The present invention relates to a distributed computing method, a distributed computing device, and a program.

In network systems such as communication networks, power grids, and transportation networks, links sometimes fail and become unusable. If such link failures are considered to be probabilistic events, it is possible to calculate the probability that certain specified nodes are connected (i.e., the probability that a path exists connecting any two of certain specified nodes). The problem of finding the probability that k specified nodes are connected is called the k-terminal network reliability problem (hereafter abbreviated as k-NR), and this probability is also called network reliability (or simply reliability).

It is known that k-NR belongs to the category of problems that are difficult to compute, being #P-complete, and straightforward methods require a lot of time to calculate network reliability even for networks with only a few dozen links. In response to this, for example, Non-Patent Documents 1 and 2 propose a method to quickly calculate network reliability using a binary decision diagram (BDD), which can compactly represent a set of combinations. Currently, a large amount of research has made it possible to accurately calculate network reliability for networks with only a few hundred links.

On the other hand, in existing studies, network reliability is calculated under the assumption that the availability of each link (i.e., the probability that each link works correctly) is given accurately. However, in reality, link availability is given with some uncertainty or may be estimated with error, for example, by machine learning. If the availability of each link has uncertainty in the form of variance, the value of network reliability should also have uncertainty in the form of variance. Calculating the uncertainty of such network reliability is important in realistic situations. For example, considering a network system with a network reliability of 99% but a standard deviation (uncertainty) of 1% and a network system with a network reliability of 98.5% but a standard deviation (uncertainty) of 0.1%, although the former has a higher network reliability, it is quite conceivable that the latter would be preferred.

Gary Hardy, Corinne Lucet, and Nikolaos Limnios. K-terminal network reliability measures with binary decision diagrams. IEEE Transactions on Reliability, Vol. 56, pp. 506-515, 2007. Johannes U. Herrmann. Improving reliability calculation with augmented binary decision diagrams. In Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications (AINA 2010), pp. 328-333, 2010.

However, as mentioned above, there is no existing research that takes into account the uncertainty of network reliability, and therefore no method exists to calculate the variance of network reliability.

One embodiment of the present invention has been made in consideration of the above points and aims to calculate the variance of network reliability.

In order to achieve the above object, a distributed computation method according to one embodiment includes the following steps, executed by a computer: an input step of inputting a connected undirected graph G = (V, E), an end vertex set K ⊂ V, and an average p _i and a variance σ _i ² of the availability of links e _i ∈ E that constitute the undirected graph G; a construction step of constructing a binary decision diagram having all states in which all nodes included in the end vertex set K are connected, based on the undirected graph G and the end vertex set K; and a computation step of calculating a _variance value of network reliability that represents the probability that all nodes included in the end vertex set K are connected, based on the binary decision diagram and the average p _i and the variance σ _i ² of the availability of the links e i ∈ E.

The variance of network reliability can be calculated.

FIG. 2 is a diagram illustrating an example of a hardware configuration of a distributed computing device according to the present embodiment. FIG. 2 is a diagram illustrating an example of a functional configuration of a distributed computing device according to the present embodiment. 4 is a flowchart illustrating an example of a flow of processing executed by the distributed computing device according to the present embodiment. 1 is a diagram illustrating an example of a graph G and a set of end points K. FIG. 1 is a diagram showing an example of a BDD that represents a certain reliability logic function. FIG. 13 is a diagram illustrating an example of an algorithm for calculating a variance value of network reliability using a BDD.

The following describes one embodiment of the present invention.

<Problem Setting>
The mathematical formulation of "distribution of network reliability" is as follows:

The network is modeled as a connected undirected graph G = (V, E), where n = |V| is the number of nodes and m = |E| is the number of links. Each link e _i ∈ E is given an availability P _i ∈ [0, 1]. This means that link e _i works correctly with probability P _i and fails with probability 1-P _i . The state of each link (i.e., whether it is working or broken) is assumed to be probabilistically independent of the states of other links. In addition, the set of states of all links included in E is called the "state of E". In this case, when the state X of E is given, we can consider a subgraph G ^X = (V, E ^X ) of G consisting only of working links, with E ^X ⊆ E as the set of working links. The probability of this state X occurring can be calculated using the following formula (1).

ノードの集合Ｋ⊆Ｖが与えられたとき、Ｋに含まれるノードが全て接続する確率（ネットワーク信頼性）Ｒ_Ｇ（Ｋ）は以下の式（２）で計算できる。

When a set of nodes K⊆V is given, the probability that all nodes included in K are connected (network reliability) R _G (K) can be calculated by the following formula (2).

ここで、Γ_ＫはＫに含まれる全てのノードがＧ^Ｘ中で接続しているようなＥの状態Ｘを全て集めた集合である。言い換えれば、Γ_Ｋは、Ｋに含まれる全てのノードが、動作しているリンクの集合Ｅ^Ｘにより全て接続しているようなＥの状態Ｘを全て集めた集合である。

Here, Γ _K is the set of all states X of E such that all nodes in K are connected in G ^X. In other words, Γ _K is the set of all states X of E such that all nodes in K are all connected by a set of working links E ^X.

Now, in order to reflect uncertainty, it is assumed that the availability P _i of each link follows a probability distribution with mean p _i and variance σ _i ^2. In other words, the availability of each link is regarded as a random variable. In this case, in order to ensure the independence of the state of each link, it is assumed that P _i and P _j are statistically independent for i ≠ j. Then, when one state X of E is fixed, P(X) in equation (1) and R _G (K) in equation (2) become random variables dependent on P ₁ , ..., P _m .

Hereinafter, E[.], Var[.], and Cov[.,.] are the expectation, variance, and covariance of P ₁ , ..., P _m , respectively. Considering the conventional network reliability value when the availability of each link is fixed as P _i = p _i , this coincides with the expected value E[R _G (K)] of R _G (K). The "variance of network reliability" we are looking for is the value of the variance Var[R _G (K)] of R _G (K), and the problem to be solved is to find the value of this variance Var[R _G (K)] when the graph G, the set of endpoints K, and the mean p _i and variance σ _i ² of each link e _i are given.

<Prior Art>
The network reliability value calculated by k-NR is expressed by the above formula (2), so it can be calculated if all the states X of E in which all the nodes included in _K are connected in G ^X can be enumerated. However, since the number of states of E is exponentially large with respect to the number of links, a straightforward enumeration would result in a huge calculation time even for a network with several tens of links. Therefore, the calculation time can be reduced by constructing a BDD having all the combinations E ^X of links in which all the nodes included in K are connected, and using the BDD for probability calculation. In particular, Non-Patent Documents 1 and 2 provide a method for directly constructing the above-mentioned BDD without enumerating all the states of E in which all the nodes included in K are connected, so that a significant reduction in calculation time can be achieved compared to straightforward enumeration. Note that the idea based on the method described in Non-Patent Document 1 is proposed, and the method described in Non-Patent Document 2 is a method that improves part of the method described in Non-Patent Document 1 to make it faster.

On the other hand, all existing research, including the methods described in Non-Patent Documents 1 and 2, has been conducted under the assumption that the availability of each link is given accurately, and there is no research that discusses the uncertainty of network reliability when availability is given with the uncertainty of variance. Note that there is research that considers the error when the network reliability value in equation (2) is approximately calculated using the Monte Carlo method, which mentions "variance" in the context of network reliability, but this research only discusses the uncertainty caused by the approximate calculation method and does not take into account the uncertainty of the availability of each link.

<Proposed method>
As mentioned above, there is no existing research that deals with the uncertainty of network reliability, and therefore no method exists for calculating the variance of network reliability. However, it is possible to decompose the variance Var[R _G (K)] using the above formula (2) as follows:

ここで、共分散Ｃｏｖ［Ｐ（Ｘ），Ｐ（Ｙ）］はリンクの数に比例する時間で計算できるため、Γ_Ｋに含まれる状態を全て列挙できれば上記の式によりネットワーク信頼性の分散の値を計算することができる。しかし、一般に、Γ_Ｋに含まれる状態の個数はリンクの本数ｍに対して指数的に増加するため、数十リンク程度のネットワークでもこの方法で分散の値を計算するのは計算時間的に困難である。このように、ネットワーク信頼性の分散の値を現実的な時間で計算する手法は存在せず、１００リンク以上のネットワークでもネットワーク信頼性の分散の値を計算できるような手法が必要である。

Here, since the covariance Cov[P(X), P(Y)] can be calculated in a time proportional to the number of links, if all the states included in Γ _K can be enumerated, the variance value of the network reliability can be calculated using the above formula. However, since the number of states included in Γ _K generally increases exponentially with the number of links m, it is difficult in terms of calculation time to calculate the variance value using this method even in a network with about several tens of links. Thus, there is no method for calculating the variance value of the network reliability in a realistic time, and a method is needed that can calculate the variance value of the network reliability even in a network with 100 or more links.

Therefore, in this embodiment, we propose a method that can quickly calculate the variance value of network reliability, and explain the distributed computing device 10 that executes this proposed method.

Based on the method described in Non-Patent Document 1, the proposed method uses BDDs to quickly calculate the variance value of network reliability. The BDDs used in Non-Patent Documents 1 and 2 are data structures that represent combination sets with a loop-free graph (called a directed acyclic graph) made up of a collection of vertices and directional edges. Note that to distinguish them from the "nodes" and "links" of the original network, the nodes and links of a directed acyclic graph are called "vertices" and "edges," respectively.

In the methods described in Non-Patent Documents 1 and 2, after constructing a BDD, the network reliability value is calculated by dynamic programming with each vertex of the BDD as one state. On the other hand, in the distributed computing device 10 according to the present embodiment, after constructing a BDD in the same manner as Non-Patent Document 1, the variance value of the network reliability is calculated by a new dynamic programming with each pair of vertices of the BDD as one state. This makes it possible to calculate the variance value of the network reliability in a time proportional to a polynomial of the size of the BDD. In general, the size of the BDD for calculating the network reliability is often very small compared to the number of states included in Γ _K , so that it becomes possible to calculate the variance value even in a network with about 200 links.

<Hardware Configuration Example of Distributed Computing Device 10>
An example of a hardware configuration of a distributed computing device 10 according to this embodiment is shown in Fig. 1. As shown in Fig. 1, the distributed computing device 10 according to this embodiment is realized by the hardware configuration of a general computer or computer system, and has an input device 101, a display device 102, an external I/F 103, a communication I/F 104, a processor 105, and a memory device 106. Each of these pieces of hardware are connected to each other via a bus 107 so as to be able to communicate with each other.

The input device 101 is, for example, a keyboard, a mouse, a touch panel, various physical buttons, etc. The display device 102 is, for example, a display, a display panel, etc. Note that the distributed computing device 10 may not have at least one of the input device 101 and the display device 102, for example.

The external I/F 103 is an interface with an external device such as a recording medium 103a. The distributed computing device 10 can read and write data from and to the recording medium 103a via the external I/F 103. Examples of the recording medium 103a include a CD (Compact Disc), a DVD (Digital Versatile Disk), a SD memory card (Secure Digital memory card), and a USB (Universal Serial Bus) memory card.

The communication I/F 104 is an interface for connecting the distributed computing device 10 to a communication network. The processor 105 is, for example, various types of arithmetic devices such as a CPU (Central Processing Unit) or a GPU (Graphics Processing Unit). The memory device 106 is, for example, various types of storage devices such as a HDD (Hard Disk Drive), an SSD (Solid State Drive), a flash memory, a RAM (Random Access Memory), a ROM (Read Only Memory), etc.

The distributed computing device 10 according to this embodiment has the hardware configuration shown in Fig. 1, and can realize various processes described below. Note that the hardware configuration shown in Fig. 1 is only an example, and the distributed computing device 10 may have, for example, multiple processors 105, multiple memory devices 106, or various other hardware besides the hardware shown in the figure.

<Example of Functional Configuration of Distributed Computing Device 10>
An example of the functional configuration of the distributed computing device 10 according to this embodiment is shown in FIG. 2. As shown in FIG. 2, the distributed computing device 10 according to this embodiment has an input unit 201, a construction unit 202, a calculation unit 203, and an output unit 204. Each of these units is realized, for example, by a process in which one or more programs installed in the distributed computing device 10 are executed by the processor 105. Here, it is assumed that the distributed computing device 10 is given a connected undirected graph G=(V, E), a set of terminal vertices K⊆V, and the average p _i and variance σ _i ² of the availability of each link e _i ∈E. Here, n=|V| is the number of nodes, and m=|E| is the number of links.

The input unit 201 receives a given connected undirected graph G, a set of end vertices K, and the mean p _i and variance σ _i ² of the availability of each link e _i ∈E.

The construction unit 202 generates (constructs) a BDD that has all states in which all nodes included in the end point set K are connected, based on the connected undirected graph G and the end point set K input by the input unit 201.

The calculation unit 203 calculates the variance value of the network reliability by dynamic programming based on the BDD generated by the construction unit 202 and the average p _i and variance σ _i ² of the availability of each link e _i ∈E.

The output unit 204 outputs the value of the variance of the network reliability calculated by the calculation unit 203 to a predetermined output destination. The output destination may be, for example, a display device 102 such as a display, a memory device 106, or another device or equipment connected via a communication network.

<Flow of Processing Executed by Distributed Computing Device 10>
The flow of processing executed by the distributed computing device 10 according to this embodiment will be described with reference to FIG.

First, the input unit 201 receives a given connected undirected graph G, a set of end vertices K, and the average p _i and variance σ _i ² of the availability of each link e _i εE (step S101).

Next, the construction unit 202 generates (constructs) a BDD that has all the states in which all the nodes included in the end set K are connected, based on the connected undirected graph G and the end set K input in the above step S101 (step S102). Details of this step will be described later.

Next, the calculation unit 203 calculates the variance of the network reliability by dynamic programming based on the BDD generated in step S102 and the average p _i and variance σ _i ² of the availability of each link e _i ∈E input in step S101 (step S103). Details of this step will be described later.

Then, the output unit 204 outputs the value of the variance of the network reliability calculated in step S103 above to any predetermined output destination (step S104).

<Details of step S102>
Since the processing executed by construction unit 202 when constructing the BDD in this step is the same as the techniques proposed in Non-Patent Documents 1 and 2, the following mainly describes the structure of the BDD constructed in this step.

Based on the graph G and the end point set K, the constructor 202 constructs a binary decision diagram (BDD) that expresses a set Γ _K that collects all states X of E such that all nodes included in the end point set K are connected in G ^X. Since a BDD is originally a data structure that expresses a logical function, first consider a logical function f _K that corresponds to Γ _K.

The same number of binary variables as the number of links are prepared, and denoted as x ₁ , ..., x _m . Then, for the state X of E, values are assigned to x ₁ , ..., x m, with x _i = true if link e _i is working, and x _i = false if link e _i is faulty. Under the above correspondence, a logic function is denoted as f _K (x ₁ , ..., x _m ) that takes the value true if the state X of E corresponding to x ₁ , ..., x _m is included in Γ _K , and takes the value _false otherwise. Hereinafter, this f _K will be referred to as a reliability logic function.

Below, we will explain the structure of a BDD. A BDD is a data structure that represents a logical function as a rooted, directed acyclic graph B = (N, A). Here, N is a set of vertices, and A is a set of edges. A root is a vertex that has no edges pointing to it, and will be represented as r∈N from now on.

The vertices in a vertex set N are broadly divided into terminal vertices, which are special vertices with no outgoing edges, and other internal vertices. In the following, terminal vertices are

と表す。以下、これらの終端頂点をそれぞれ「第１の終端頂点」、「第２の終端頂点」ともいう。

Hereinafter, these terminal vertices are also referred to as the "first terminal vertex" and the "second terminal vertex", respectively.

Each internal vertex

は、ＬＯ辺及びＨＩ辺と呼ばれる２つの出る辺と、ラベルと呼ばれる整数値とを持つ。内部頂点ｖのＬＯ辺及びＨＩ辺が指す先の頂点をそれぞれＬＯ子頂点及びＨＩ子頂点と呼び、それぞれｌｏ（ｖ）及びｈｉ（ｖ）と表す。また、ｖのラベルはｌｂ（ｖ）∈｛１，・・・，ｃ｝と表す。ここで、ｃはＢＤＤが表現する論理関数が入力として取る二値変数の個数である。ＢＤＤのラベルは、根から辺を辿って行くに従い値が大きくなっていく必要がある。すなわち、各内部頂点ｖに対してｌｂ（ｖ）＜ｌｂ（ｌｏ（ｖ））かつｌｂ（ｖ）＜ｌｂ（ｈｉ（ｖ））である必要がある。なお、終端頂点については、それぞれ

has two outgoing edges called LO edges and HI edges, and an integer value called a label. The vertices pointed to by the LO edges and HI edges of an internal vertex v are called the LO child vertices and the HI child vertices, respectively, and are denoted as lo(v) and hi(v), respectively. The label of v is denoted as lb(v) ∈ {1, ..., c}, where c is the number of binary variables that the logic function represented by the BDD takes as input. The labels of a BDD must increase in value as one traces the edges from the root. In other words, it is necessary that lb(v) < lb(lo(v)) and lb(v) < lb(hi(v)) for each internal vertex v. For the terminal vertices,

と仮定する。最後に、ＢＤＤのサイズは、頂点の個数｜Ｎ｜として定義される。

Finally, the size of a BDD is defined as the number of vertices, |N|.

Given the structure of a BDD, for each vertex v of the BDD, a logic function f _v corresponding to that vertex is recursively defined.

に対しては、それぞれｆ_ｖ＝ｔｒｕｅ、ｆ_ｖ＝ｆａｌｓｅとする。これらはそれぞれ恒真関数（入力値に関わらずｔｒｕｅとなる論理関数）、恒偽関数（入力値に関わらずｆａｌｓｅとなる論理関数）である。それ以外の内部頂点ｖに対しては、

For each internal vertex v, f _v = true and f _v = false. These are truth functions (logical functions that are true regardless of the input value) and falsity functions (logical functions that are false regardless of the input value), respectively. For other internal vertices v,

とする。

Let us assume that.

As an example, Fig. 5 shows a BDD expressing a reliability logic function _fK corresponding to _ΓK when the graph G and the end point set K shown in Fig. 4 are given. In the example shown in Fig. 4, the circles represent the nodes of the graph G, and the black circles represent the end points (i.e., the nodes of the graph G that are included in the end point set K). In the example shown in Fig. 5, _a1 to _a8 represent the internal vertices, _a9 and _a10 represent the terminal vertices, the solid lines represent the HI edges, the dashed lines represent the LO edges, and the numbers in the circles represent the labels of the internal vertices.

A BDD that represents a reliability logic function _fK is a BDD that is a set of vertices from its root r to its first terminal vertex.

までの経路が、Γ_Ｋの中の一部の状態に対応している。すなわち、ＢＤＤの根ｒから第１の終端頂点までの各経路のそれぞれは、Γ_Ｋに含まれる１つ以上の状態に対応している。

, r, corresponds to some state in Γ _K. That is, each path from the root r of the BDD to the first terminal vertex corresponds to one or more states in Γ _K.

Given a path from the root r of a BDD to the first terminal vertex, tracing the LO edge from a vertex whose label is i means that the link e _i corresponding to the label i is faulty, tracing the HI edge means that the link e _i corresponding to the label i is working, and not passing through a vertex whose label is i means that the state of the link e _i corresponding to the label i is not taken into consideration.

For example, in FIG. 5, the path from vertex a1 with label ₁ → HI edge of vertex _a1 → vertex _a2 with label ₂ → HI edge of vertex a2 → vertex _a6 with label 4 → LO edge of vertex _a6 → vertex _a8 with label 5 → HI edge of vertex _a8 → first terminal vertex corresponds to two states: ( _e1 , _e2 , _e3 , _e4 , _e5 ) = (action, action, action, fault, action) and (action, action, fault, fault, action).

Efficiently constructing a BDD that expresses a reliability logic function _fK is a method described in Non-Patent Documents 1 and 2. Therefore, please refer to Non-Patent Documents 1, 2, etc. for a specific method of constructing a BDD that expresses a reliability logic function _fK .

<Details of step S103>
In this step, the calculation unit 203 calculates the variance of the network reliability by a new dynamic programming method in which a pair of vertices of the BDD is one state. In the following, the idea of calculating the variance of the network reliability is first explained, and then an algorithm showing a specific procedure for performing the calculation is explained.

First, for each vertex v of the BDD expressing the reliability logic function f _K , the conditional probability that all the end points (i.e., the nodes included in the end point set K) are connected under the fixed state of e ₁ , ..., e lb _(v)-1 is defined as R _v . Then, the following equations (3) and (4) hold using the availability P _i of each link.

このとき、根ｒに対応するＲ_ｒがネットワーク信頼性Ｒ_Ｇ（Ｋ）である。

In this case, R _r corresponding to the root r is the network reliability R _G (K).

Here, if P ₁ , ..., P _m are random variables, R _v is a random variable dependent on P ₁ , ..., P _m . Therefore, for a pair of vertices u, v ∈ N of the BDD, we can consider the covariance Cov[R _u , R _v ] of R _u and R _v with respect to P ₁ , ..., P _m . In this case, the variance Var[R _G (K)] of the network reliability can be expressed as Cov[R _r , R _r ].

By using the equality for covariance, the covariance Cov[R _u , R _v ] can be decomposed into the covariances for its child vertices. For example, if the labels of u and v are equal, i.e., lb(u)=lb(v)=i, then the equality shown in the following formula (5) holds with q _i =1−p _i .

また、ｕのラベルがｖのラベルより小さい場合、すなわちｉ＝ｌｂ（ｕ）＜ｌｂ（ｖ）の場合、以下の式（６）に示す等式が成立する。

Furthermore, when the label of u is smaller than the label of v, that is, when i=lb(u)<lb(v), the equality shown in the following equation (6) holds.

ｌｂ（ｕ）＞ｌｂ（ｖ）の場合も同様の等式（つまり、上記の式（６）と対称な式）が成立する。更に、ｕとｖの少なくともいずれか一方が終端頂点である場合、Ｃｏｖ［Ｒ_ｕ，Ｒ_ｖ］＝０となる。

A similar equality (i.e., an equation symmetrical to equation (6) above) holds when lb(u)>lb(v). Furthermore, if at least one of u and v is a terminal vertex, then Cov[R _u , R _v ]=0.

By recursively using the above equation, it becomes possible to recursively divide and calculate Var[ _RG (K)]=Cov[ _Rr , _Rr ].

Procedure for Calculating the Variance of Network Reliability Below, an algorithm representing a procedure for calculating the variance of network reliability using a BDD will be described with reference to Fig. 6. Here, the input of this algorithm is a BDD B = (N, A) and the average p _i and variance σ _i ² of the availability of link e _i , and the output is the variance of the network reliability represented by B. Note that the procedure represented by each line of this algorithm is executed by the calculation unit 203.

First, in lines 1 to 3, e[v] = E[R _v ] is calculated for each v∈N. Specifically, in line 1, 1.0 is assigned to the first terminal vertex, and 0.0 is assigned to the second terminal vertex. Then, in lines 2 to 3, the value of e[v] is calculated in order by e[v]←q _i · e[lo(v)] + p _i · e[hi(v)] in bottom-up order, where the vertices with larger labels are scanned first. In this process, the expected value of the network reliability E[R _G (K)] = e[r] is also calculated. Note that q _i = 1 - p _i .

Next, in line 4, a recursive procedure (function) Cov(r,r) is called. Procedure Cov(u,v) is a recursive procedure that calculates the covariance Cov[R _u ,R _v ], and its contents are described in lines 5 to 17. First, in lines 6 to 7, if at least one of u and v is a terminal vertex, 0 is returned as the answer. Next, in lines 8 to 9, if the covariance Cov[R _u ,R _v ] has already been calculated, the calculated value is returned as the answer. Here, an associative array c is prepared as a cache for storing the calculated Cov[R _u ,R _v ], and the value of Cov[R _u ,R _v ] is stored in c[(u,v)].

Thereafter, Cov[R _u , R _v ] is calculated by recursively calling the procedure Cov(u, v) using formula (5) and formula (6). That is, after storing the smaller of the labels of u and v in i on line 10, if the label of u is smaller than the label of v, Cov[R _u , R _v ] is calculated using formula (6) (lines 11 to 12), if the label of v is smaller than the label of u, Cov[R _u , R _v ] is calculated using a formula symmetric to formula (6) (lines 13 to 14), and if the label u and the label v are equal, Cov[R _u , R _v ] is calculated using formula (5). Finally, the calculated value of Cov[R _u , R _v ] is returned (line 17). This allows the variance value of the network reliability to be obtained.

<Summary>
As described above, the distributed computing device 10 according to this embodiment is capable of quickly calculating the variance value of network reliability, which could not be calculated by any method other than a simple one up until now. In particular, it has been confirmed that the variance value of network reliability can be calculated even for an actual network with a scale of about 100 to 200 links. This makes it possible to quantitatively evaluate the effect of the uncertainty of the availability of each link on the uncertainty of the network reliability. Therefore, for example, when a link that has no operational history and whose accurate availability is unknown is added to a network, it is possible to quantitatively analyze how the link affects the uncertainty of the network reliability.

The distributed computing device 10 according to this embodiment may perform various network controls using the calculated variance value of the network reliability. For example, it may perform control so that the network has a low variance value if the network reliability is the same, or it may perform control so that the network has a low variance value if the network reliability is low but within a certain reference range.

The present invention is not limited to the specifically disclosed embodiments above, and various modifications, variations, and combinations with known technologies are possible without departing from the scope of the claims.

10 Distributed computing device 101 Input device 102 Display device 103 External I/F
103a Recording medium 104 Communication I/F
105 Processor 106 Memory device 107 Bus 201 Input section 202 Construction section 203 Calculation section 204 Output section

Claims (8)

An input procedure for inputting a connected undirected graph G=(V, E), a set of end vertices K⊂V, and the mean p _i and variance σ _i ² of the availability of links e _i ∈E constituting the undirected graph G;
A construction step of constructing a binary decision diagram having all states in which all nodes included in the end point set K are connected, based on the undirected graph G and the end point set K;
A calculation procedure for calculating a variance value of network reliability representing a probability that all nodes included in the end point set K are connected based on the binary decision diagram and the average p _i and variance σ _i ² of the availability of the link e _i ∈E;
A distributed computing method in which a computer performs The calculation procedure is as follows:
The variance calculation method according to claim 1 , further comprising the steps of: calculating a variance value of the network reliability by recursively calculating a covariance for a pair of vertices of the binary decision diagram using the mean _{p i and} variance σ _i ² of the availability of the link e i ∈E. The calculation procedure is as follows:
3. The method of claim 1, further comprising the steps of: fixing a state indicating whether each of links e ₁ , ..., e _lb(v)-1 (where lb(v) is the label of vertex v) is working or broken for each vertex v of the binary decision diagram; defining a conditional probability that all nodes included in the terminal set K are connected as R _v , defining the availability of the link e _i as P _i , and defining a vertex that is the root of the binary decision diagram as r; and calculating a covariance value of R _r and R _r with respect to P ₁ , ..., P _m (where m = |E|) as the variance value of the network reliability. The calculation procedure is as follows:
When an arbitrary pair of vertices in the BDD is (u, v), the covariance of R _u and R _v with respect to P ₁ , . . . , P _m is Cov[R _u , R _v ],
4. The variance calculation method according to claim 3, wherein the covariance Cov[R u , R v ] is calculated by recursively calculating the covariance Cov[R _u , R _{v ]} using any one of a first equation that holds when the label of vertex u is equal to the label of vertex v, a second equation that holds when the label of vertex u is smaller than the label of vertex v, and a third equation that holds when the label of vertex v is _smaller than the label of vertex u, thereby calculating the value Cov[R _r , R _r ] of the covariance of R _r and R _r with respect to P 1 , ..., P _m . The calculation procedure is as follows:
Let the label of the vertex u be lb(u), the label of the vertex v be lb(v), the child vertex pointed to by the HI edge of the vertex u be hi(u), the child vertex pointed to by the LO edge of the vertex u be lo(u), the child vertex pointed to by the HI edge of the vertex v be hi(v), the child vertex pointed to by the LO edge of the vertex v be lo(v), q _i =1-p _i , and E(·) be the expected value,
If lb(u)=lb(v)=i, then the first equation is Cov[R _u , R _v ]=(q _i ² +σ _i ² )Cov[R _lo(u) ,R _lo(v) ]+(p _i q _i −σ _i ² )(Cov[R _lo(u) ,R _hi(v) ]+Cov[R _hi(u) ,R _lo(v) ])+(p _i ² −σ _i ² )Cov[R _hi(u) ,R _hi(v) ]+σ _i ² (E[R _hi(u) ]−E[R _lo(u) ])(E[R _hi(v) ]−E[R _lo(v) ]),
If i=lb(u)<lb(v), the second equation is Cov[R _u , R _v ]=q _i Cov[R _lo(u) , R _v ]+ _pi Cov[R _hi(u) , R _v ];
5. The method of claim 4, wherein if i=lb(v)<lb(u), the third equation is Cov[ _Ru , _Rv ]= _qiCov [ _Ru , _Rlo(v) ]+ _piCov [ _Ru , _Rhi(v) ]. The construction procedure is as follows:
6. The distributed computing method according to claim ₁ , further comprising: constructing _{a binary decision diagram expressing a logical function that takes binary variables x1, ..., xm as} input, where _xi = true if link e _{i ∈} E is working, and xi = false if link e i ∈ E is faulty, and outputs true if all nodes included in the end point set K are connected, and false otherwise. An input unit configured to input a connected undirected graph G=(V, E), a set of edge vertices K⊂V, and the mean p _i and variance σ _i ² of the availability of links e _i ∈E constituting the undirected graph G;
A construction unit configured to construct a binary decision diagram having all states to which all nodes included in the end point set K are connected, based on the undirected graph G and the end point set K;
A calculation unit configured to calculate a variance value of a network reliability representing a probability that all nodes included in the end point set K are connected based on the binary _decision diagram and the average p _i and variance σ _i ² of the availability of the link e i ∈E;
A distributed computing device having: A program for causing a computer to execute the distributed computing method described in any one of claims 1 to 6.

Images