JP6939516B2 - Network design equipment, methods, and programs - Google Patents

Description

The present invention relates to network design devices, methods, and programs, and more particularly to network design devices, methods, and programs that design a cost-optimized network while ensuring communication reliability.

The reliability of a communication network is an index showing how robust the network is against the failure of the components constituting the communication network (hereinafter, may be simply referred to as a network). More specifically, it is defined as the probability that communication using a network can be performed when a component of the network fails according to a certain probability distribution. It is important to design a reliable network. In a network that connects multiple devices with communication links, a graph is constructed with each of the multiple devices as the apex and each of the communication links that can be added to the network as an edge, and the graph is constructed and the operation on the graph is performed. There is a technology to design a highly reliable communication network.

T. Koide, S. Shinmori, and H. Ishii, "Topological optimization with a network reliability constraint", Discrete applied mathematics, Vol.115, No.1, pp. 135-149, 2001 G. Hardy, C. Lucet, and N. Limnios "K-terminal network reliability measures with binary decision diagrams", IEEE Trans. Reliability, Vol.56, No.3, p.506-515, 2007

Constructed under the constraint that the reliability of the network being constructed exceeds a reliable reference value when the cost required to add the edge corresponding to each communication link to the graph corresponding to the network is given. It is known that the problem of designing a network that minimizes the cost can be formulated and solved as a combinatorial optimization problem (Non-Patent Document 1). However, since it is a combinatorial optimization problem that is very difficult to find, the existing method can only find the optimal solution in the design of a very small network. Therefore, when designing a network on a scale where the optimum solution cannot be obtained, we have to rely on an approximate solution method with no guarantee of performance.

The present invention has been made to solve the above problems, and provides a network design device, a method, and a program capable of designing a cost-optimized network while ensuring communication reliability. The purpose is to do.

In order to achieve the above object, the network design device according to the present invention is a network design device for designing a communication network in which a plurality of devices are connected by a communication link, with each of the plurality of devices as a peak and the communication network. Assuming that each of the communication links that can be added to is represented by a graph of the communication network, the above is based on the set of the vertices, the set of the sides, and the set of endpoints which is a subset of the set of vertices. Each of the BDD construction unit that builds a dichotomy graph that expresses a set of failure patterns that a communication network can take, and the devices that correspond to the end points even if some of the end nodes of the dichotomy graph fail. With the terminal node of the route corresponding to the network structure capable of communicating by the communication network as the first terminal node, the dichotomy graph, the cost of each side included in the predetermined set of sides, and the cost of each side in advance. based on the operation probability of each side included in the set of defined said side, the total number of the node b _{i (i} = 1 BDD, · · ·, B, provided that B is the BDD node ) cost s (s = 0, 1 that can be taken, · · ·, C, but C is for each of combinations of a predetermined constant), the route to node b _i from the first terminal node of the BDD among them, a value representing the upper limit of the reliability of a communication network in which the total cost of a communication network corresponding to the path corresponding to the path when selecting a route such that the following cost s of the b _i and s set Based on the index calculation unit that calculates as the index corresponding to the index, the index, the cost of each side, and the operation probability of each side, the reliability and the cost are predetermined so as to satisfy the predetermined constraints. It is configured to include an optimization calculation unit that searches for combinations of nodes corresponding to communication links added to the communication network.

The network design method according to the present invention is a network design method in a network design device for designing a communication network in which a plurality of devices are connected by a communication link, and the BDD construction unit has each of the plurality of devices as a peak and the communication. Assuming that the communication network is represented graphically with each of the communication links that can be added to the network as edges, based on the set of vertices, the set of edges, and the set of endpoints that are subsets of the set of vertices. The step of constructing a dichotomy graph expressing a set of failure patterns that the communication network can take, and the index calculation unit correspond to the end point even if a part of the end nodes of the dichotomy graph fails. The dichotomy graph and each side included in the predetermined set of sides are set as the first terminal node of the route corresponding to the network structure in which each of the devices to be used can communicate with the communication network. costs and, based on the operation probability of each side included in the set of predetermined said edges, node b _{i (i} = 1 of the BDD, · · ·, B, provided that B is the BDD the total number of nodes) and cost s (s = 0,1, ···, C, but C is for each of combinations of a predetermined constant), leading to the node b _i from the first terminal node of the BDD of path, a value representing the upper limit of the reliability of the communication network corresponding to the route the b _i and s when the total cost of the communication network corresponding to the route selects a route to be equal to or less than the cost s A step of calculating as an index corresponding to the set of, and an optimization calculation unit predetermined the reliability and cost based on the index, the cost of each side, and the operation probability of each side. It is characterized in that it includes a step of searching for a combination of sides corresponding to a communication link added to the communication network so as to satisfy the constraint.

The program according to the present invention is a program for causing a computer to function as each part of the network design device.

According to the network design device, method, and program of the present invention, it is possible to design a network with optimized cost while ensuring the reliability of communication.

It is a figure which shows an example of BDD. It is a block diagram which shows the structure of the network design apparatus which concerns on 1st and 2nd Embodiment of this invention. It is a figure which shows the detail of the index construction process. It is a figure which shows the detail of the optimization process of 1st Embodiment of this invention. It is a figure which shows the function evaluation processing flow of 1st Embodiment of this invention. It is a figure which shows the prospective calculation flow. It is a flowchart which shows the network design processing routine in the network design apparatus which concerns on embodiment of 1st Embodiment of this invention. It is a figure which shows the detail of the optimization process of the 2nd Embodiment of this invention. It is a figure which shows the function evaluation processing flow of the 2nd Embodiment of this invention. It is a flowchart which shows the network design processing routine in the network design apparatus which concerns on embodiment of the 2nd Embodiment of this invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

<Overview of Embodiments of the Present Invention>

A data structure called a Binary Decision Diagram (BDD) is used to represent a set of all failure patterns in which a network can operate. ^{Furthermore, by executing the A *} search algorithm on the BDD, it is possible to efficiently find the optimum solution even in the design of a large-scale network.

<Principle of the First Embodiment of the Invention>

Here, the principle in the first embodiment of the present invention will be described.

First, the symbols used below are introduced. It is assumed that the communication network is given by the graph G = (V; E). Here, V is a set of vertices and E is a set of edges. Let M be the total number of sides. Given a subset F of E, the induced subgraph derived by E is represented as G [F]. The subset T⊆V of V is called the end point. Let each side be e ₁ , ..., e _M. Edge _{e i} operates with probability _{p i,} and to the possibility of defects _{1-p i} (hereinafter, the _{p i} that the operating probability edges _{e i).} The binary variable y _i ∈ {0,1} is used to indicate whether _{the edge e i is operating.} That is, _{if y i} = 1, it is assumed that _{e i is operating, and if y i} = 0, it is assumed that it is out of order. The reliability of the network can be calculated by the following equation (1).

・・・（１）

... (1)

Here, y is an M-dimensional vector in which ^{each element has a value of either 0 or 1, and {0,1} M} is a set of M-dimensional vectors in which each element has a value of either 0 or 1. Is. Here, I (y) is connected to all the vertices included in the endpoint T by a set of non-failed edges represented by y (a set of edges e _{i corresponding to y i where y i} = 1). A function that returns 1 if it is, and 0 otherwise.

Network design problems are defined as follows.

・・・（２）

・・・（３）

... (2)

... (3)

Here c _i is cost to add an edge e _i in the communication network, theta is the confidence threshold. That is, the problem of constructing a network with the minimum cost is that the total value of the costs is the minimum under the constraint that G [E'] is equal to or more than the threshold value from the set E of edge candidates that can be added to the network. It is a problem of selecting a set of edges E'to be added so as to be. Here, _{if e i} ∈ E', x _i = 1,

ならばｘ_ｉ＝０であるような二値変数ｘ_１,...,ｘ_Ｍを導入すると、上記の最適化問題は以下（４）式のように書くことができる。

Then, if we introduce binary variables x ₁ , ..., X _{M such that x i} = 0, the above optimization problem can be written as the following equation (4).

・・・（４）

... (4)

Here, x = (x ₁ , ..., x _M ). That is, x _i is a variable indicating whether or not the side e _{i is added to the communication network.} R (x) defines the reliability as a function of x, and is defined as the following equation (5).

・・・（５）

... (5)

BDD is a data structure that expresses a logical function as a directed acyclic graph. FIG. 1 shows an example of BDD expressing a logical function (x ₁ ∧ _{x 2} ) ∨ (x ₁ ∧ _{x 3} ) ∨ (x ₂ ∧ _{x 3).} BDD has two types of nodes, a terminal node and a branch node. In BDD, the line connecting nodes is called an "arc" or "branch". The terminal node is a node that does not have an arc starting from that node, and is represented by a square in FIG.

終端ノード（以下「第２終端ノード」という）と

終端ノード（以下「第１終端ノード」という）の２種類の終端ノードがあり、一つのＢＤＤには各終端ノードは高々一つずつ存在する。分岐ノードは終端ノードではないノードのことである。各分岐ノードには、そのノードを始点とするアークが必ず２つ存在し、それぞれｌｏ枝、ｈｉ枝とよばれる。また、各分岐ノードには論理関数の引数が１つラベルとして対応付けられる。図１中では各分岐ノードは円として表現され、ｈｉ枝は実線、ｌｏ枝は点線によって表現される。図１中のノードｂ１は分岐ノードであり、要素ｘ１がラベルとして付与され、ｌｏ枝はｂ２を、ｈｉ枝はｂ３を指している。ＢＤＤ中では親をもたないノードが必ず１つのみ存在し、根ノードとよばれる。

With a terminal node (hereinafter referred to as "second terminal node")

There are two types of terminal nodes (hereinafter referred to as "first terminal nodes"), and one BDD has at most one terminal node. A branch node is a node that is not a terminal node. Each branch node always has two arcs starting from that node, and are called lo branch and hi branch, respectively. Further, each branch node is associated with one argument of the logical function as a label. In FIG. 1, each branch node is represented by a circle, the hi branch is represented by a solid line, and the lo branch is represented by a dotted line. The node b1 in FIG. 1 is a branch node, the element x1 is given as a label, the lo branch points to b2, and the hi branch points to b3. In BDD, there is always only one node that has no parent, and it is called a root node.

Each path from the root node to the first terminal node corresponds to the assignment of variables such that the logical function represented by BDD is true.

In the BDD of FIG. 1, there are three types of routes from the root node b1 to the first terminal node. Since the BDD in FIG. 1 represents a logical function with three arguments, it is assumed that the route can be represented by three variables. If the function represented by BDD has N arguments, the route is represented by 0,1 of N variables.

And represent the route in three variables _{(x 1, x 2, x} 3), if a variable that indicates follow either branch lo branches and hi branches x _i at the node of the node label i, from the root node b1 The three types of routes leading to the first terminal node can be expressed as (1,1, *), (1,0,1), (0,1,1). Note that * indicates that the node corresponding to x3 does not appear in the route. Each route corresponds to the assignment of a variable that is true. For a variable in which the corresponding node does not appear in the route, it is true regardless of whether 0 or 1 is assigned to the variable. In the BDD example of FIG. 1, the path (1,1, *) shows the assignment of values to the two variables (1,1,0) and (1,1,1). Therefore, (1,1,0), (1,1,1), (1,0,1), (0,1,1) are assigned variables so that the logical function represented by BDD is true. Is.

In the following, it is assumed that there are B BDD nodes, and each node is represented _{as b 1} , ..., b _B. Note that b ₁ corresponds to the root node, and if j <k for _{b j} and b _{k , then b j} cannot be a child of b _k. It is assumed that b _B is the first terminal node and b _B-1 is the second terminal node. Further, a set of indices of the cut-node at the level i a D _i, of the BDD node, label 1, ..., rather than any of the i-1, and 1, ..., i-1 It is a set of subscripts of those having a parent node whose label is any of.

,−,−）,（ｂ６,

,−,−）］というテーブルを用意することで表現することができる。 BDD can be expressed by preparing a quadruple (node ID, label, node pointed to by hi branch, node pointed to by lo branch) for each node. Since the example BDD has 6 nodes, [(b1,1, b3, b2), (b2,2, b4, b5), (b3,2, b6, b4), (b4,3, b6, b5). ), (B5,

,-,-), (B6,

,-,-)] Can be expressed by preparing a table.

In the present invention, a BDD is constructed from a graph corresponding to a communication network (hereinafter referred to as an "input graph").

In the input graph, the communication devices constituting the communication network correspond to each vertex, and the communication link between each communication device corresponds to an edge.

In the BDD constructed, each node has a label corresponding to each side of the input graph. Then, when a certain partial structure (subgraph) of the input graph includes an edge e _i (i = 1, ..., M), the hi branch is traced from the node whose label is i, and the edge e _i is included. If not, follow the lo branch from the node labeled i. Therefore, each path from the root node to the terminal node corresponds to the partial structure of the input graph.

Each of the "assignments of variables that make the logical function represented by BDD true" corresponds to the partial structure of the input graph. This partial structure represents a graph corresponding to a network obtained by removing a broken link in a communication network. The logical function becomes true when communication is possible between all endpoints in the communication network obtained by removing the broken link.

<Structure of the network design device according to the first embodiment of the present invention>

Next, the configuration of the network design device according to the first embodiment of the present invention will be described. As shown in FIG. 2, the network design device 100 according to the first embodiment of the present invention includes a CPU, a RAM, a ROM that stores a program for executing a network design processing routine described later, and various data. It can be configured with a computer that includes. The network design device 100 functionally includes an input unit 10, a calculation unit 20, and an output unit 50 as shown in FIG.

As an input, the input unit 10 has a set of vertices V = {v ₁ , v ₂ , ..., v _N } (N is the total number of vertices) of the graph corresponding to the communication network, a set of end points T⊆V, and a communication network. set of edges _E = that can be added to _{{e 1, e 2, ···} , e M} ( the total number of M are side), the cost _{c 1} of the sides, _..., c M _{(c i} is the side e _i Cost), the operation probability of each side p ₁ , ..., p _M (p _i is the operation probability of the side e _i ), and the reliability threshold θ are received as inputs. Here, the cost of edge e _i, represents the cost to add a communications link corresponding to the communication network to the side e _i.

The calculation unit 20 includes a BDD construction unit 30, an index calculation unit 32, an optimization calculation unit 34, and a storage unit 40.

The BDD construction unit 30 has a graph G = (V) based on the vertex set V of the network received by the input unit 10, the edge set E that can be added to the network, and the end point set T of the vertex set V. In (E), a binary determination graph (BDD) representing a set of failure patterns, which is a combination of edges to which all the vertices are connected, is constructed.

As a result, each path of BDD is a graph consisting of vertices included in the set V, and is a graph in which the vertices are connected by the sides specified by the path. That is, each path of BDD corresponds to a graph in which some or all sides of the graph corresponding to G = (V; E) are missing. Missing edges, since they represent a communication link is faulty in a communication network, for example, the graph to the lack of edges e _i, corresponding to the failure patterns such as communication links corresponding to the side e _i is faulty do. That is, the set of BDD routes represents a set of all possible failure patterns in the communication network corresponding to the graph G.

Then, each path from the root node to the first terminal node corresponds to a failure pattern in which all the end points can communicate by the network even if some sides are missing (communication link fails). The set of routes from the root node to the first terminal node represents a set of all failure patterns in which all endpoints can be communicated by a network.

The BDD is constructed by using the method described in Non-Patent Document 2 above.

The index calculation unit 32 includes the BDD constructed by the BDD construction unit 30, the costs c ₁ , ..., c _M of each side required for addition, and the operation probability p ₁ , of each side. .., based on the _{p M,} the combination of the cost (s = 0,1,2, ···, C ) in a communication network corresponding to the partial structure from node _{b i} and the terminal node of the BDD to node _{b i} Calculate the index for each of. Here, the index corresponding to the set of b _i and s, of the graph corresponding to each path from the terminal node to node b _i, when the cost selects a combination of the following become such sides s, This is the upper limit of the reliability of the communication network corresponding to the combination of the relevant sides. The details of the processing of the index calculation unit 32 will be described later.

The optimization calculation unit 34 includes the index calculated by the index calculation unit 32, the costs c ₁ , ..., c _M of each side, and the operation probabilities p ₁ , ..., p _{M of each side.} , The network is designed by selecting a combination of sides that satisfies a predetermined constraint on reliability expressed by the above equation (5) based on the reliability threshold value θ. Specifically, the optimization calculation unit 34 selects a combination of edges so as to satisfy the constraint that the reliability is equal to or higher than the threshold value θ and minimize the cost, and minimizes the cost of the combination. It is output by the output unit 50 as information for specifying the configuration of a network.

In the storage unit 40, an estimated value of the minimum cost of the communication network corresponding to the combination, which is calculated for each candidate of the side combination in the optimization calculation unit 34, is stored in association with the storage unit 40.

Next, the details of the index construction process of the index calculation unit 32 will be described with reference to FIG. In the index calculation unit 32, as inputs, the BDD constructed by the BDD construction unit 30, the maximum value C of the cost, the operation probability of the edge p ₁ , ..., p _M , and the cost c ₁ , ..., c of the edge. _{Receive M} and calculate index A. The index A is a table composed of B × (C + 1) elements, and the elements in the j-th row and s-th column of the table are A [i] [s]. A [i] [s], of the graph corresponding to each of the path from the BDD of the termination node to node b _i, when the cost selects an edge to be equal to or less than s, the estimated value of the reliability ( The upper limit) is held. Note that the edges of the network which is associated with a label to the i-th node of the BDD and e _k. Further, C is the maximum value of the cost and is an arbitrary integer value. for example,

として設定してもよい。

May be set as.

In the process of FIG. 3, first, for each i = 1, ..., B, s = 0,1, ..., C, the value 0 is set in A [i] [s] to initialize the index. To become. Next, set A [B] [s] ← 1.0 for all s = 0,1, ..., C. In the following, the values of A [i] and [s] are recursively calculated for all combinations of i and s.

Next, the details of the optimization process of the optimization calculation unit 34 will be described with reference to FIG. In the following, a partial vector in which values are assigned only to the i-th or lower _{elements of x (that is, x 1} , x ₂ , ..., X _i ) is expressed as _{x ≤ i.} Further, each combination of possible values of each element in _{x ≤ i is called a "state".} For example, _{if x ≦ 2} , each of (0,0), (0,1), (1,0), and (1,1) is a “state”.

The optimization calculation unit 34 initializes the list Open that stores the set of states in step 1 of FIG. In step 2, the initial state is added to Open. Next, unless Open is empty, _{one state x ≤ j} that minimizes the score is selected (steps 3 and 4). Here, the score in each state is an estimated value of the cost of the communication network when the value of each element of _{the partial vector x ≤ j is in the state.} Details will be described later. If the magnitude of the partial vector corresponding to the state x _{≤ j} is M, it is output as a solution and the process ends (step 6). Here, the magnitude of the partial vector is the number of elements of the partial vector, and the magnitude of _{x ≦ j is j.} If not, create a x _{≦ j} of j + 1-th new element was set to 1 vector x _{≦ j} ^{+ 1 (1),} a new vector was set j + 1 th element to 0 x _{≦ j} ^{+ 1} a ^(0). Scores are calculated for each, and if the score value is less than ∞, it is added to Open (steps 8 to 13).

The above procedure is repeated, and the process ends when the magnitude of the _{minimum score partial vector x ≤ j} extracted from Open in steps 3 and 4 is M. Each x _j takes a value of either 0 or 1, means adding the edge e _j to the communication network if x j _{= 1.} Thus, _x j = 1 to become edge _{e j} of the x _{≦ M} becomes the side to be added to the communication network.

That is, the optimization calculation unit 34 stores the candidate of the side combination method ( _{the combination of the sides e i} in which x _i = 1 in _{x ≤ j} ) together with the estimated value of the minimum cost for the combination method in Open. By executing the best-first search that expands and expands in order from the one with the smallest estimated cost value, the combination of edges to be added to the communication network is selected. In this way, the process of executing the best-first search and selecting the combination of edges to be added to the communication network is the process by the search means (whether or not to add each edge in order from the first edge included in the set of edges). This is an example of the process of finding the combination of edges by determining. Further, the storage in Open is an example in which the storage unit 40 stores the cost of the communication network corresponding to the combination for each candidate of the side combination in association with each other.

The calculation of the scores in steps 10 and 13 of FIG. 4 will be described with reference to the function evaluation processing flow of FIG.

First, the edge motion probability p ′ _j is set in step 1 of FIG. Next, in Step 2, using the process of forward calculation flow in Fig. 6 to determine the value of each subscript I∈D _j corresponding sequence F _{j [i]} included in the cut-node set D _j. Then, in step 3, using the value of _{index A and the value of Fj [i],}

を満たすような最小のｓを求め、部分ベクトルｘ_≦ｊに対するコストの推定値ｈ(ｘ_≦ｊ)とする。これをスコアとして用いる。そのようなｓを求めるためには、０≦ｓ≦Ｃの全ての値を試してもよいし、あるいは

The minimum s that satisfies the condition is obtained, and _{the estimated value h (x ≤ j} ) of the cost with respect to the _{partial vector x ≤ j} is used. This is used as a score. In order to obtain such s, all the values of 0 ≦ s ≦ C may be tried, or

がｓの値に対して単調に変動することを利用して、二分探索を利用して求めてもよい。

It may be obtained by using a binary search by utilizing the fact that is monotonously fluctuating with respect to the value of s.

<Operation of the network design device according to the first embodiment of the present invention>

Next, the operation of the network design device 100 according to the first embodiment of the present invention will be described. In the input unit 10, the vertex set V of the communication network, the end point set T⊆V, the side set E that can be added to the network, the cost required to add each side c ₁ , ..., c _M , and each side Upon receiving the operation probabilities p ₁ , ..., p _M , and the reliability threshold θ, the network design device 100 executes the network design processing routine shown in FIG. 7.

First, in step S100, the graph G = (V) based on the vertex set V of the network received by the input unit 10, the set E of the edges that can be added to the network, and the set T of the end points of the vertex set V. In (E), a BDD expressing a set of failure patterns, which is a combination of edges to which all the vertices are connected, is constructed.

Next, in step S102, the BDD constructed in step S100, the cost _{c 1} needed to add each edge in the graph G, ..., and _{c M,} the operation probability _{p 1} of each of the sides, ..., based on the p _M, according to the algorithm shown in FIG. 3, for each of combinations of node b _i and cost s of BDD, corresponds to a node b _i, and the total cost is less cost s Calculate the index that stores the value that represents the upper limit of the reliability when the combination of edges to be added is selected.

In step S104, the index calculated in step S102, the costs c ₁ , ..., c _M required to add each side, and the operation probabilities p ₁ , ..., p _{M of} each side are displayed. Based on the reliability threshold θ, the combination of edges to be added to the network is selected so as to satisfy the constraint that the reliability is equal to or higher than the threshold θ and to minimize the cost. Here, the network is designed by performing a best-first search according to the algorithm shown in FIG. 4 and selecting a combination of sides to be added to the network.

In step S106, the output unit 50 outputs the network configuration designed in step S104 that minimizes the cost, and ends the process.

As described above, according to the network design device according to the first embodiment of the present invention, it is based on the constructed BDD, the cost required for adding each side, and the operation probability of each side. Te, for each of combinations of node b _i and cost s of BDD, corresponds to a node b _i, and the reliability when the total cost of the selected combinations of edges to be added to be equal to or less than the cost s An index calculation unit that calculates an index that stores a value representing the upper limit, the calculated index, the cost of each side required for addition, the operation probability of each side, and the reliability threshold θ Based on the above, it is possible to design a network that optimizes the cost while ensuring the reliability of communication by selecting the combination of edges to be added to the network so as to satisfy the predetermined constraint on reliability. can. This can contribute to the design of a network with higher fault tolerance.
<Outline and Principle of the Second Embodiment of the Present Invention>

Next, the network design device according to the second embodiment of the present invention will be described. The description of the part similar to that of the first embodiment will be omitted.

In the network design apparatus according to the second embodiment of the present invention, there is a construction cost when the cost required for adding the side corresponding to each communication link to the graph corresponding to the network is given. The problem of designing a network that maximizes the reliability of the network to be constructed under the constraint that it falls below the reference value can also be formulated and solved as a combinatorial optimization problem.

The second embodiment of the present invention is for solving the above-mentioned problems, and it is possible to design a network that maximizes the reliability of communication while satisfying the cost constraint.

In the second embodiment of the present invention, the network design problem is defined as follows.

・・・（６）

・・・（７）

... (6)

... (7)

Here c _i is cost to add an edge e _i in the communication network, C is an upper limit of cost. That is, the problem of maximizing reliability is the network obtained by selecting and adding edges from a set of edge candidates E that can be added to the network within a range in which the total cost does not exceed the upper limit C. This is a problem of maximizing the reliability of G [E']. Here, _{if e i} ∈ E', x _i = 1,

ならばｘ_ｉ＝０であるような二値変数ｘ_１,...,ｘ_Ｍを導入すると、上記の最適化問題は以下（８）式のように書くことができる。

Then, if we introduce binary variables x ₁ , ..., X _{M such that x i} = 0, the above optimization problem can be written as the following equation (8).

・・・（８）

... (8)

Here, x = (x ₁ , ..., x _M ). That is, x _i is a variable indicating whether or not the side e _{i is added to the communication network.} R (x) defines the reliability as a function of x, and is defined as the following equation (9).

・・・（９）

... (9)

Since the BDD is the same as that of the first embodiment, the description thereof will be omitted.

<Structure of the network design device according to the second embodiment of the present invention>

Next, the configuration of the network design device according to the second embodiment of the present invention will be described. As shown in FIG. 2, the network design device 100 according to the second embodiment of the present invention is a ROM that stores a CPU, a RAM, a program for executing a network design processing routine described later, and various data. And can be configured with a computer that includes. The network design device 100 functionally includes an input unit 10, a calculation unit 20, and an output unit 50 as shown in FIG.

As an input, the input unit 10 has a set of vertices V = {v ₁ , v ₂ , ..., v _N } (N is the total number of vertices) of the graph corresponding to the communication network, a set of end points T⊆V, and a communication network. set of edges _E = that can be added to _{{e 1, e 2, ···} , e M} ( the total number of M are side), the cost _{c 1} of the sides, _..., c M _{(c i} is the side e _i Cost), operation probability of each side p ₁ , ..., p _M (p _i is the operation probability of side e _i ), and the upper limit C of cost is received as input. Here, the cost of edge e _i, represents the cost to add a communications link corresponding to the communication network to the side e _i.

The calculation unit 20 includes a BDD construction unit 30, an index calculation unit 32, an optimization calculation unit 34, and a storage unit 40. Since the BDD construction unit 30 and the index calculation unit 32 are the same processes as those in the first embodiment, the description thereof will be omitted.

The optimization calculation unit 34 includes the index calculated by the index calculation unit 32, the costs c ₁ , ..., c _M of each side, and the operation probabilities p ₁ , ..., p _{M of each side.} The network is designed by selecting a combination of sides that satisfies a predetermined constraint on the cost represented by the above equation (4) based on the upper limit C of the cost. Specifically, the optimization calculation unit 34 selects an edge combination so that the cost of the selected edge combination satisfies the constraint that the cost upper limit C or less is equal to or less than the cost upper limit C, and the reliability is maximized, and the combination thereof. The output unit 50 outputs as information for specifying the network configuration that maximizes the reliability of the above.

The storage unit 40 stores an estimated value of the maximum reliability (upper limit of reliability) of the communication network corresponding to the combination, which is calculated by the optimization calculation unit 34 for each candidate for the combination of sides. Will be done.

The details of the index construction process of the index calculation unit 32 will be omitted because the process is the same as that of the first embodiment. However, as the maximum cost value C, an arbitrary integer value is not used, but the cost upper limit C, which is the upper limit value of the total cost received by the input unit 10, is used.

Next, the details of the optimization process of the optimization calculation unit 34 will be described with reference to FIG. In the following, a partial vector in which values are assigned only to the i-th or lower _{elements of x (that is, x 1} , x ₂ , ..., X _i ) is expressed as _{x ≤ i.} Further, each combination of possible values of each element in _{x ≤ i is called a "state".} For example, _{if x ≦ 2} , each of (0,0), (0,1), (1,0), and (1,1) is a “state”.

The optimization calculation unit 34 initializes the list Open that stores the set of states in step 1 of FIG. In step 2, the initial state is added to Open. Next, unless Open is empty, _{one state x ≤ j} that maximizes the score is selected (steps 3 and 4). Here, the score in each state is an estimated value of the reliability of the communication network when the value of each element of _{the partial vector x ≤ j is in the state.} Details will be described later. If the magnitude of the partial vector corresponding to the state x _{≤ j} is M, it is output as a solution and the process ends (step 6). Here, the magnitude of the partial vector is the number of elements of the partial vector, and the magnitude of _{x ≦ j is j.} If not, create a x _{≦ j} of j + 1-th new element was set to 1 vector x _{≦ j} ^{+ 1 (1),} a new vector was set j + 1 th element to 0 x _{≦ j} ^{+ 1} a ^(0). Scores are calculated for each and added to the Open (steps 8-13).

The above procedure is repeated, and the process ends when the magnitude of the _{maximum score partial vector x ≤ j} extracted from Open in steps 3 and 4 is M. Each x _j takes a value of either 0 or 1, means adding the edge e _j to the communication network if x j _{= 1.} Thus, _x j = 1 to become edge _{e j} of the x _{≦ M} becomes the side to be added to the communication network.

That is, the optimization calculation unit 34 stores the candidate of the side combination method (the combination of the sides e _i in which x _{i = 1 out of x ≤ j} ) in Open together with the estimated value of the maximum reliability for the combination method. , Select the combination of edges to be added to the communication network by executing the best-first search that expands and expands in order from the one with the highest estimated reliability. In this way, the process of executing the best-first search and selecting the combination of edges to be added to the communication network is the process by the search means (whether or not to add each edge in order from the first edge included in the set of edges). This is an example of the process of finding the combination of edges by determining. Further, the storage in Open is an example in which the storage unit 40 stores the reliability of the communication network corresponding to the combination for each candidate of the side combination in association with each other.

The calculation of the scores in steps 10 and 13 of FIG. 8 will be described with reference to the function evaluation processing flow of FIG.

First, in steps 1 and 2 of FIG. 9, _{the sum s of the costs corresponding to the partial vectors x ≦ j} is calculated, and the edge motion probability p ′ _j is set. Next, in step 3, the value of the array F _{j [i] corresponding to the cut node set D j} is obtained by using the process of the forward calculation flow shown in FIG. Then, in step 4, the reliability score is calculated using the value of the index A and the value of _{Fj [i].}

<Operation of the network design device according to the second embodiment of the present invention>

Next, the operation of the network design device 100 according to the second embodiment of the present invention will be described. In the input unit 10, the vertex set V of the communication network, the end point set T⊆V, the side set E that can be added to the network, the cost required to add each side c ₁ , ..., c _M , and each side Upon receiving the operation probabilities p ₁ , ..., p _M , and the upper limit C of the total cost, the network design device 100 executes the network design processing routine shown in FIG.

First, in step S200, the graph G = (V) based on the vertex set V of the network received by the input unit 10, the set E of the edges that can be added to the network, and the set T of the end points of the vertex set V. In (E), a BDD expressing a set of failure patterns, which is a combination of edges to which all the vertices are connected, is constructed.

Next, in step S202, the BDD built at step S200, the cost _{c 1} needed to add each edge in the graph G, ..., and _{c M,} the operation probability _{p 1} of each of the sides, ..., based on the p _M, according to the algorithm shown in FIG. 3, for each of combinations of node b _i and cost s of BDD, corresponds to a node b _i, and the total cost is less cost s Calculate the index that stores the value that represents the upper limit of the reliability when the combination of edges to be added is selected.

In step S204, the index calculated in step S202, the costs c ₁ , ..., c _M required to add each side, and the operation probabilities p ₁ , ..., p _{M of} each side, respectively. Based on the upper limit C of the cost, the combination of the edges to be added to the network is selected so that the cost of the combination of the selected edges satisfies the constraint that the cost is equal to or less than the upper limit C of the cost and the reliability is maximized. Here, the network is designed by performing a best-first search according to the algorithm shown in FIG. 8 and selecting a combination of sides to be added to the network.

In step S206, the output unit 50 outputs the network configuration designed in step S204 that maximizes the reliability, and ends the process.

As described above, according to the network design device according to the second embodiment of the present invention, it is based on the constructed BDD, the cost required for adding each side, and the operation probability of each side. Te, for each of combinations of node b _i and cost s of BDD, corresponds to a node b _i, and the reliability when the total cost of the selected combinations of edges to be added to be equal to or less than the cost s Based on the index calculation unit that calculates the index that stores the value representing the upper limit, the calculated index, the cost of each side required for addition, the operation probability of each side, and the upper limit C of the cost. By selecting the combination of edges to be added to the network so that the cost of the combination of selected edges is less than or equal to the cost upper limit C, a network that maximizes the reliability of communication while satisfying the cost constraint can be created. Can be designed. This can contribute to the design of a network with higher fault tolerance.

The present invention is not limited to the above-described embodiments, and various modifications and applications can be made without departing from the gist of the present invention.

20 Calculation unit 30 BDD construction unit 32 Index calculation unit 34 Optimization calculation unit 50 Output unit 100 Network design device

Claims (5)

A network design device that designs a communication network that connects multiple devices with a communication link.
The communication network is represented graphically with each of the plurality of devices as the apex and each of the communication links that can be added to the communication network as an edge.
A BDD construction unit that builds a binary decision graph that expresses a set of failure patterns that the communication network can take based on the set of vertices, the set of edges, and the set of endpoints that is a subset of the set of vertices. ,
Among the terminal nodes of the dichotomy graph, the terminal node of the route corresponding to the network structure is the first terminal so that each of the devices corresponding to the end points can communicate with each other even if a part of the side fails. As a node
Nodes of the binary decision graph based on the binary decision graph, the cost of each side included in the predetermined set of sides, and the operation probability of each side included in the predetermined set of sides. _{b i (i = 1, ···} , B, provided that B is the total number of nodes of the BDD) cost s (s = 0,1, ···, C, but C is a predetermined constant) to a can take for each combination of, among the route to node b _i from the first terminal node of the binary decision diagram, when the total cost of a communication network corresponding to the route selects a route to be equal to or less than the cost s and an index calculator for calculating a value representing the upper limit of the reliability of the communication network corresponding to the relevant route as an index corresponding to the set of the b _i and s,
Based on the index, the cost of each side, and the operating probability of each side, the side corresponding to the communication link added to the communication network so as to satisfy predetermined constraints on the reliability and cost. An optimization calculation unit that searches for combinations, and
Network design equipment including. The optimization calculation unit
The network design device according to claim 1, wherein among the combinations of sides that satisfy the constraint that the reliability is equal to or higher than a predetermined threshold value θ, the combination of sides that minimizes the cost is searched for. The optimization calculation unit includes a search means for obtaining a combination of the edges by determining whether or not to add each edge in order from the first edge included in the set of edges.
The network design device according to claim 2, further comprising a storage unit that stores the costs of the communication network corresponding to the combination for each candidate for the combination of the sides. It is a network design method in a network design device that designs a communication network that connects multiple devices with a communication link.
Assuming that the BDD construction unit graphically represents the communication network with each of the plurality of devices as vertices and each of the communication links that can be added to the communication network as sides, the set of vertices and the set of sides , A step of constructing a dichotomy graph representing a set of failure patterns that the communication network can take, based on a set of endpoints that is a subset of the set of vertices.
The index calculation unit terminates the route corresponding to the network structure such that each of the devices corresponding to the end points can communicate with the communication network even if some of the end nodes of the dichotomy graph fails. Based on the dichotomy graph, the cost of each side included in the predetermined set of sides, and the operation probability of each side included in the predetermined set of sides, with the node as the first terminal node. Te, the node _b i BDD (i = 1, · · ·, B, provided that B is the total number of nodes of the BDD) cost s (s = 0,1, ···, C, except C is for each of combinations of a predetermined constant), among the route to node b _i from the first terminal node of the binary decision diagram, so that the total cost of a communication network corresponding to the route becomes less cost s calculating a value representing the upper limit of the reliability of the communication network corresponding to the route when selecting a route as an index corresponding to the set of the b _i and s in,
Communication added to the communication network by the optimization calculation unit so as to satisfy predetermined constraints on reliability and cost based on the index, the cost of each side, and the operation probability of each side. Steps to search for the combination of edges corresponding to the link,
Network design methods including. A program for causing a computer to function as each part of the network design apparatus according to any one of claims 1 to 3.

Images