JP6581546B2 - Reliability evaluation method, reliability evaluation apparatus and program - Google Patents
Reliability evaluation method, reliability evaluation apparatus and program Download PDFInfo
- Publication number
- JP6581546B2 JP6581546B2 JP2016146887A JP2016146887A JP6581546B2 JP 6581546 B2 JP6581546 B2 JP 6581546B2 JP 2016146887 A JP2016146887 A JP 2016146887A JP 2016146887 A JP2016146887 A JP 2016146887A JP 6581546 B2 JP6581546 B2 JP 6581546B2
- Authority
- JP
- Japan
- Prior art keywords
- binary decision
- decision diagram
- branch
- probability
- network
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Description
本開示は、通信ネットワークの信頼性を評価する信頼性評価方法、信頼性評価装置及びプログラムに関する。 The present disclosure relates to a reliability evaluation method, a reliability evaluation apparatus, and a program for evaluating the reliability of a communication network.
通信ネットワークにおいて、ノード同士が通信できるためには、ノード間にパスが存在しており、連結されていなければならない。ノードやリンクの故障率が与えられると、パスが存在する確率を計算することができる。ネットワークの信頼性評価において、ノードの連結確率は重要な基礎データとなる。 In the communication network, in order for nodes to communicate with each other, a path must exist between the nodes and be connected. Given the failure rate of a node or link, the probability that a path exists can be calculated. In network reliability evaluation, node connection probabilities are important basic data.
たとえば、図１においてリンク故障率が１０％のとき、ノードＡとＣとの連結確率は０．９２＝８１％である（本稿ではノードは故障しないとする）。一方で、図２においてリンク故障率が２５％であれば、ノードＡとＤの連結確率は１−（１−０．７５２）２＝８０．８５９３７５％である。このように、ネットワークとしての信頼性は、リンクの信頼性だけでなく、ネットワークの形状によっても変化する。 For example, in FIG. 1, when the link failure rate is 10%, the connection probability between nodes A and C is 0.9 2 = 81% (in this paper, the node is assumed not to fail). On the other hand, if the link failure rate in FIG. 2 is 25%, the connection probability between nodes A and D is 1− (1−0.75 2 ) 2 = 80.859375%. As described above, the reliability of the network varies depending not only on the reliability of the link but also on the shape of the network.
ネットワークの規模が大きくなるとノード間には膨大な数のパスが存在し、さらにそれらには依存関係があるため、連結確率の計算は容易ではない。非特許文献１は、二分決定図（ＢＤＤ：ｂｉｎａｒｙ ｄｅｃｉｓｉｏｎ ｄｉａｇｒａｍ）というデータ構造を用いた効率的な計算手法を提案している。
As the scale of the network increases, there are a huge number of paths between nodes, and there are dependencies among them, so it is not easy to calculate the connection probability. Non-Patent
非特許文献１の概要を説明する。図３のネットワークにおいて、ノードｓとｔの連結確率を計算する。まず、ｓとｔが連結になるようなネットワーク状態をＢＤＤとして列挙する。辺ｅｉは、故障か稼働（０ ｏｒ １）のいずれかの状態をとる。図３には５つの辺があるため、５つのバイナリ変数からなるベクトルによって個々のネットワーク状態を表現できる。すべての辺が故障していれば（０，０，０，０，０）であり，すべて稼働していれば（１，１，１，１，１）である。なお、連結状態に影響しない辺の状態は＊で表す。たとえば，ｅ１とｅ２が故障していれば、他の辺の状態にかかわらずｓとｔは非連結になる。この条件は（０，０，＊，＊，＊）と表される。
The outline of
ここで、ＢＤＤ構築アルゴリズムについて説明する。本アルゴリズムは次のルールに従って、辺（リンク）ｅｉ（図３であればｉ＝１〜５）を故障とした場合と稼働とした場合についてネットワーク状態を決め、順にＢＤＤの節点を構築していく。
・ルール１
リンク状態を稼働とした場合、辺の両端のノードが連結になると決めて縮退（合体）させる。ただし、リンク自体は合体させずに残す。
・ルール２
リンク状態を故障とした場合、当該リンクを除去する。
・ルール３
ルール１とルール２によって生成されたネットワーク状態が「等価」になる場合、同じ節点にまとめる。
・ルール４
連結対象ノード（通信対象の２つのノード）がひとつに縮退した場合、他のリンク状態にかかわらず連結であるので最終節点“┬”へつなぐ。
・ルール５
２つのノード間のリンク状態が故障である場合、最終節点“┴”へつなぐ。
図３のネットワークにおいて上記ルール１〜５を用いてＢＤＤを構築すると図４のようになる。
Here, the BDD construction algorithm will be described. In accordance with the following rules, this algorithm determines the network state when the side (link) ei (i = 1 to 5 in FIG. 3) is faulty and when it is active, and constructs BDD nodes in order. .
・
When the link state is active, it is determined that the nodes at both ends of the side are connected and degenerate (join). However, the link itself is left unmerged.
・
If the link status is a failure, the link is removed.
・
When the network states generated by
・
When the connection target node (two nodes to be communicated) is reduced to one, it is connected regardless of other link states, and is connected to the final node “最終”.
・
If the link state between the two nodes is faulty, it is connected to the final node “┴”.
When the BDD is constructed using the
ＢＤＤはグラフであり、最上位の頂点（根節点）から最下位の頂点（終端節点）へのパス（ｐａｔｈ）が個々のネットワーク状態を表す。終端節点が┬に到達するパスは連結状態を表し、┴に到達するパスは非連結状態を表す（┬は真，┴は偽を表す論理記号である）。根節点はｅ１の状態を表し、点線（０枝）をたどると故障、実線（１枝）をたどると稼働となる。たとえば、最も左のパスはｅ１＝０、ｅ２＝０であり、┴終端節点に到達している。つまりｅ１とｅ２が故障すると、ｓとｔは非連結になることを表しており、（０，０，＊，＊，＊）ということである。最も右のパスは（１，１，＊，１，＊）であり、┬終端節点に到達していることから連結状態を表しているとわかる。このＢＤＤは、ノードｓとｔを連結するすべてのネットワーク状態を過不足なく表している。なお、あるネットワーク状態が┬終端節点に到達するパスとして表現されている場合，「ＢＤＤがその状態を含む」と言うことにする。 BDD is a graph, and a path from the highest vertex (root node) to the lowest vertex (end node) represents each network state. A path where the terminal node reaches を represents a connected state, and a path that reaches ┴ represents a disconnected state (┬ is a logical symbol representing true and ┴ is false). The root node represents the state of e 1 , and failure occurs when the dotted line (branch 0) is followed, and operation starts when the solid line (branch 1) is followed. For example, the leftmost path is e 1 = 0 and e 2 = 0, and has reached the heel end node. That is, when e 1 and e 2 fail, s and t are disconnected, and (0, 0, *, *, *). The rightmost path is (1, 1, *, 1, *), and it can be understood that it represents a connected state because it has reached the heel terminal node. This BDD represents all network states connecting nodes s and t without excess or deficiency. When a certain network state is expressed as a path that reaches the end node, it is said that “BDD includes that state”.
次に、構築したＢＤＤを用いて連結確率を計算する。このＢＤＤはノードｓとｔを連結するすべてのネットワーク状態を過不足なく表しているので、各状態（例えば、ｒ１−ｒ４−ｒ７−ｒ１５の状態やｒ２−ｒ６−ｒ１６の状態）が実現する確率を求めて、┬終端節点に到達する枝の確率を足し合わせれば、ネットワーク全体としての連結確率を得られる。 Next, the connection probability is calculated using the constructed BDD. Since this BDD represents all network states that connect nodes s and t without excess or deficiency, the probability that each state (for example, the state of r1-r4-r7-r15 or the state of r2-r6-r16) will be realized. If the probability of the branch reaching the end node of the heel is added, the connection probability of the entire network can be obtained.
具体的に計算してみる。すべてのリンクの故障率を１０％とする。ＢＤＤの根節点から┬終端節点に向かって確率を足し合わせていく。まず、根節点から出ている０枝の確率を０．１、１枝の確率を０．９とする。さらに下へと進むたびに、０枝を通るときは０．１、１枝を通るときは０．９を掛けていく。右側のｅ４節点のようにパスが合流する場合、合流するすべての枝の確率を足し合わせてから、次の枝の確率を掛ける。このようにして、┬終端節点に合流するすべての枝の確率を足し合わせると、ネットワーク全体の連結確率となる。図４の例では、０．９７８４８となる。
Let's calculate concretely. The failure rate of all links is 10%. The probabilities are added from the root node of the BDD to the end node of the heel. First, the probability of the 0 branch coming out from the root node is 0.1, and the probability of the 1 branch is 0.9. Each time it goes further down, it will be multiplied by 0.1 when passing through branch 0 and by 0.9 when passing through
非特許文献１は、すべての連結状態を過不足なくＢＤＤとして表す。このため、厳密に正確な連結確率を得られるが、一方でネットワークの複雑さによってはＢＤＤが肥大化し、節点数が膨大になることがある。つまり、非特許文献１で説明される連結確率計算手法には、ＢＤＤ節点が計算機のメモリに収まらないほど多くなると確率計算の実行が困難になるという課題があった。
Non-Patent
そこで、本発明は、上記課題を解決するために、大規模なネットワークであっても連結確率を計算でき、ネットワークの信頼性を評価できる信頼性評価方法、信頼性評価装置及びプログラムを提供することを目的とする。 Therefore, in order to solve the above problems, the present invention provides a reliability evaluation method, a reliability evaluation apparatus, and a program capable of calculating the connection probability even in a large-scale network and evaluating the reliability of the network. With the goal.
上記目的を達成するために、本発明に係る信頼性評価方法は、連結状態を表すＢＤＤを近似的に２つ構築することで、ＢＤＤ節点数を減らし、メモリ不足を回避することとした。 In order to achieve the above object, the reliability evaluation method according to the present invention reduces the number of BDD nodes and avoids memory shortage by constructing approximately two BDDs representing a connected state.
具体的には、本発明に係る信頼性評価方法は、
複数のノードが複数のリンクで接続されたネットワークにおけるノード間の連結確率を、二分決定図を用いて算出し、ネットワークの信頼性を評価する信頼性評価方法であって、
前記二分決定図の任意の節点において任意の基準値を満たす枝を選択する枝選択手順と、
前記枝選択手順で選択した枝を連結状態を表す終端節点へ接続して過大評価二分決定図を構築し、前記枝選択手順で選択した枝を非連結状態を表す終端節点へ接続して過小評価二分決定図を構築する二分決定図構築手順と、
前記二分決定図構築手順で構築した前記過大評価二分決定図と前記過小評価二分決定図それぞれについて、各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する連結確率算出手順と、
前記確率算出手順で算出した２つの前記連結確率から前記ネットワークの真の連結確率が存在する範囲を見出す真値推定手順と、
を順に行う。
Specifically, the reliability evaluation method according to the present invention is:
A reliability evaluation method for calculating a connection probability between nodes in a network in which a plurality of nodes are connected by a plurality of links, using a binary decision diagram, and evaluating the reliability of the network,
A branch selection procedure for selecting a branch satisfying an arbitrary reference value at an arbitrary node of the binary decision diagram;
An overestimation binary decision diagram is constructed by connecting the branch selected in the branch selection procedure to a terminal node representing a connected state, and an underestimation is performed by connecting the branch selected in the branch selection procedure to a terminal node representing an unconnected state. A binary decision diagram construction procedure for constructing a binary decision diagram;
For each of the overestimated binary decision diagram and the underestimated binary decision diagram constructed in the binary decision diagram construction procedure, the probability of each node is calculated, and the calculated probability is used to connect the nodes to be connected in the network. A connection probability calculation procedure for calculating a connection probability;
A true value estimation procedure for finding a range where the true connection probability of the network exists from the two connection probabilities calculated in the probability calculation procedure;
Repeat in order.
また、本発明に係る信頼性評価装置は、複数のノードが複数のリンクで接続されたネットワークにおけるノード間の連結確率を、二分決定図を用いて算出し、ネットワークの信頼性を評価する信頼性評価装置であって、
前記二分決定図の任意の節点において任意の基準値を満たす枝を選択する枝選択部と、
前記枝選択部が選択した枝を連結状態を表す終端節点へ接続して過大評価二分決定図を構築し、前記枝選択部が選択した枝を非連結状態を表す終端節点へ接続して過小評価二分決定図を構築する二分決定図構築部と、
前記二分決定図構築部が構築した前記過大評価二分決定図と前記過小評価二分決定図それぞれについて、各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する連結確率算出部と、
前記確率算出部が算出した２つの前記連結確率から前記ネットワークの真の連結確率が存在する範囲を見出す真値推定部と、
を備える。
The reliability evaluation apparatus according to the present invention calculates a connection probability between nodes in a network in which a plurality of nodes are connected by a plurality of links, using a binary decision diagram, and evaluates the reliability of the network. An evaluation device,
A branch selector that selects a branch that satisfies an arbitrary reference value at an arbitrary node of the binary decision diagram;
An overestimation binary decision diagram is constructed by connecting the branch selected by the branch selection unit to a terminal node representing a connected state, and an underestimation is performed by connecting the branch selected by the branch selection unit to a terminal node representing a non-connected state. A binary decision diagram construction unit for constructing a binary decision diagram;
For each of the overestimated binary decision diagram and the underestimated binary decision diagram constructed by the binary decision diagram construction unit, the probability of each node is calculated, and the calculated probability is used to connect the nodes to be connected in the network. A connection probability calculation unit for calculating a connection probability;
A true value estimation unit for finding a range in which the true connection probability of the network exists from the two connection probabilities calculated by the probability calculation unit;
Is provided.
本発明に係る信頼性評価方法及び装置は、厳密に正確なＢＤＤを構築するのではなく、過大評価あるいは過小評価のＢＤＤを構築することでＢＤＤ節点数を削減する。それぞれのＢＤＤによる連結確率に挟まれる範囲に正確なＢＤＤの連結確率が存在することになる。つまり、本発明に係る信頼性評価方法及び装置は、厳密な連結確率ではないが、ある程度の精度を持った連結確率の範囲を得ることができ、大規模なネットワークの信頼性を評価することができる。 The reliability evaluation method and apparatus according to the present invention reduce the number of BDD nodes by constructing an overestimated or underestimated BDD instead of constructing a strictly accurate BDD. An accurate BDD connection probability exists in a range between the connection probabilities of the respective BDDs. In other words, the reliability evaluation method and apparatus according to the present invention can obtain a range of connection probabilities with a certain degree of accuracy but not a strict connection probability, and can evaluate the reliability of a large-scale network. it can.
従って、本発明は、大規模なネットワークであっても連結確率を計算でき、ネットワークの信頼性を評価できる信頼性評価方法及び信頼性評価装置を提供することができる。 Therefore, the present invention can provide a reliability evaluation method and a reliability evaluation apparatus that can calculate a connection probability even in a large-scale network and can evaluate the reliability of the network.
例えば、本発明に係る信頼性評価方法及び装置は、前記基準値を満たす枝が連結確率が所定値より小さい枝とすることができる。 For example, in the reliability evaluation method and apparatus according to the present invention, a branch satisfying the reference value can be a branch having a connection probability smaller than a predetermined value.
本発明に係るプログラムは、前記信頼性評価方法をコンピュータに実行させるためのプログラムである。本発明に係るの信頼性評価装置はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。 A program according to the present invention is a program for causing a computer to execute the reliability evaluation method. The reliability evaluation apparatus according to the present invention can be realized by a computer and a program, and the program can be recorded on a recording medium or provided through a network.
本発明は、大規模なネットワークであっても連結確率を計算でき、ネットワークの信頼性を評価できる信頼性評価方法、信頼性評価装置及びプログラムを提供することができる。 The present invention can provide a reliability evaluation method, a reliability evaluation apparatus, and a program that can calculate a connection probability even in a large-scale network and can evaluate the reliability of the network.
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。 Embodiments of the present invention will be described with reference to the accompanying drawings. The embodiments described below are examples of the present invention, and the present invention is not limited to the following embodiments. In the present specification and drawings, the same reference numerals denote the same components.
本実施形態の信頼性評価方法は、複数のノードが複数のリンクで接続されたネットワークにおけるノード間の連結確率を、二分決定図を用いて算出し、ネットワークの信頼性を評価する信頼性評価方法であって、
前記二分決定図の任意の節点において任意の基準値を満たす枝を選択する枝選択手順と、
前記枝選択手順で選択した枝を連結状態を表す終端節点へ接続して過大評価二分決定図を構築し、前記枝選択手順で選択した枝を非連結状態を表す終端節点へ接続して過小評価二分決定図を構築する二分決定図構築手順と、
前記二分決定図構築手順で構築した前記過大評価二分決定図と前記過小評価二分決定図それぞれについて、各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する連結確率算出手順と、
前記確率算出手順で算出した２つの前記連結確率から前記ネットワークの真の連結確率が存在する範囲を見出す真値推定手順と、
を順に行う。
The reliability evaluation method of the present embodiment calculates a connection probability between nodes in a network in which a plurality of nodes are connected by a plurality of links using a binary decision diagram, and evaluates the reliability of the network. Because
A branch selection procedure for selecting a branch satisfying an arbitrary reference value at an arbitrary node of the binary decision diagram;
An overestimation binary decision diagram is constructed by connecting the branch selected in the branch selection procedure to a terminal node representing a connected state, and an underestimation is performed by connecting the branch selected in the branch selection procedure to a terminal node representing an unconnected state. A binary decision diagram construction procedure for constructing a binary decision diagram;
For each of the overestimated binary decision diagram and the underestimated binary decision diagram constructed in the binary decision diagram construction procedure, the probability of each node is calculated, and the calculated probability is used to connect the nodes to be connected in the network. A connection probability calculation procedure for calculating a connection probability;
A true value estimation procedure for finding a range where the true connection probability of the network exists from the two connection probabilities calculated in the probability calculation procedure;
Repeat in order.
まず、過大評価ＢＤＤについて説明する。過大評価ＢＤＤは、すべての連結状態を含み、さらに一部の非連結状態も含むように構築したＢＤＤである。過大評価ＢＤＤを用いて計算した連結確率は、ＢＤＤに余計に含まれた非連結状態の分だけ過大に見積もられることになる。図５は、図３のネットワークにおいて構築した過大評価ＢＤＤである。例えば、図５の過大評価ＢＤＤは、厳密に構築した図４のＢＤＤより節点数が２つ少ないが、図４には含まれていなかった（１，０，０，０，０）という非連結状態を含んでいる。図５に基づいて連結確率を計算すると０．９８０１９となり、図４に基づく厳密な連結確率の値０．９７８４８より大きくなっている。 First, overestimated BDD will be described. The overestimated BDD is a BDD constructed so as to include all connected states and further include some unconnected states. The connection probability calculated using the overestimated BDD is overestimated by the amount of the unconnected state that is included in the BDD. FIG. 5 is an overestimated BDD constructed in the network of FIG. For example, the overestimated BDD in FIG. 5 has two fewer nodes than the strictly constructed BDD in FIG. 4, but is not included in FIG. 4 (1, 0, 0, 0, 0) Includes state. When the connection probability is calculated based on FIG. 5, it becomes 0.98019, which is larger than the strict connection probability value 0.978848 based on FIG.
次に過小評価ＢＤＤを説明する。過小評価ＢＤＤは、連結状態しか含まれないが、必ずしもすべての連結状態を含まないように構築したＢＤＤである。過小評価ＢＤＤを用いて計算した連結確率は、ＢＤＤに含まれなかった連結状態の分だけ過小評価されることになる。図６は、図３のネットワークにおいて構築した過小評価ＢＤＤである。例えば、図６の過小評価ＢＤＤは、厳密に構築した図４のＢＤＤより節点数が２つ少ないが、図４には含まれていた（１，０，０，１，０）という連結状態を含んでいない。図６に基づいて連結確率を計算すると０．８９０１９となり、図４に基づく厳密な連結確率の値０．９７８４８より小さくなっている。 Next, the underestimated BDD will be described. The underestimated BDD is a BDD constructed so as to include only the connected state but not necessarily all the connected states. The connection probability calculated using the underestimated BDD is underestimated by the amount of the connection state not included in the BDD. FIG. 6 is an underestimated BDD constructed in the network of FIG. For example, the underestimated BDD in FIG. 6 has two nodes less than the strictly constructed BDD in FIG. 4, but the connected state (1,0,0,1,0) included in FIG. Does not include. When the connection probability is calculated based on FIG. 6, it is 0.89019, which is smaller than the strict connection probability value 0.978848 based on FIG.
このように、過大評価のＢＤＤと過小評価のＢＤＤを用いて連結確率を計算した場合、厳密なＢＤＤに基づく連結確率（真の連結確率）が必ず両者の間に存在する（一致することもある）。つまり、真の連結確率の上限と下限を得ることができる。上限と下限の差が小さければ、実用上十分な精度の連結確率を取得できる。 As described above, when the connection probability is calculated using the overestimated BDD and the underestimated BDD, the connection probability (true connection probability) based on the strict BDD always exists between the two (they may match). ). That is, the upper limit and lower limit of the true connection probability can be obtained. If the difference between the upper limit and the lower limit is small, a practically sufficient connection probability can be obtained.
続いて、過大評価と過小評価のＢＤＤを構築する方法を説明する。
本実施形態でも非特許文献１と同様に、ＢＤＤを上から下へと構築していく。この構築過程において、何らかの基準で「重要ではない枝」を見つける（枝選択手順）。重要度の決め方は任意であるが、ここでは一例を示す。
Next, a method for constructing an overestimated and underestimated BDD will be described.
Also in this embodiment, as in
前記枝選択手順において、前記基準値を満たす枝が連結確率が所定値より小さい枝とする。ＢＤＤの構築過程において、連結確率も一緒に計算していくことで、各枝の確率値が与えられる。ｉが同じである節点ｅｉの全ての枝のうち、この確率値が所定値より小さい枝を「重要ではない」、あるいは最小の枝を「重要ではない」としてもよい。たとえば、図４において、ｅ２の節点から出ている枝まで計算したとする。┴節点に到達する枝（ｒ３）を除くと３本の枝（ｒ４，ｒ５，ｒ６）があり、それぞれの確率値は左から０．０９、０．０９、０．８１である。同じ確率値の枝が複数ある場合は、当該枝の中からランダムに選択してもよい。本実施形態では確率値が最小のふたつの枝のうち、中央の枝（ｒ５）を選ぶことにする。 In the branch selection procedure, a branch satisfying the reference value is a branch having a connection probability smaller than a predetermined value. In the BDD construction process, the probability of each branch is given by calculating the connection probability together. Of all the branches of the node e i having the same i , a branch having a probability value smaller than a predetermined value may be “not important”, or a minimum branch may be “not important”. For example, in FIG. 4, and was calculated to branches emanating from the node of e 2. Excluding the branch (r3) reaching the saddle node, there are three branches (r4, r5, r6), and the respective probability values are 0.09, 0.09, and 0.81 from the left. When there are a plurality of branches having the same probability value, the branches may be randomly selected from the branches. In the present embodiment, the center branch (r5) is selected from the two branches having the smallest probability values.
続けて、以下の操作（二分決定図構築手順）を行い、過大評価、あるいは過小評価のＢＤＤを構築する。
過大評価ＢＤＤを構築するときは、上述のように選択した「重要ではない」枝を┬終端節点に接続する。このようにすることで、以降のリンク状態に関わらず、その枝を通過する状態はすべてＢＤＤに含まれることになるため過大評価となる。具体的には、図４の枝ｒ５を┬終端節点に接続し、枝ｒ５以下の節点（ｅ３，ｅ４）と枝（ｒ９，ｒ１０，ｒ１１，ｒ１２）を削除すると図５の過大評価ＢＤＤになる。
Subsequently, the following operation (binary decision diagram construction procedure) is performed to construct an overestimated or underestimated BDD.
When building an overestimated BDD, the “not important” branch selected as described above is connected to the heel end node. By doing so, all the states passing through the branch are included in the BDD regardless of the subsequent link states, which is overestimated. Specifically, when the branch r5 in FIG. 4 is connected to the heel end node, and the nodes (e3, e4) and the branches (r9, r10, r11, r12) below the branch r5 are deleted, the overestimated BDD in FIG. 5 is obtained. .
過小評価ＢＤＤを構築するときは、上述のように選択した「重要ではない」枝を┴終端節点に接続する。このようにすることで、以降のリンク状態に関わらず、その枝を通過する状態はＢＤＤに含まれなくなるため過小評価となる。図４の枝ｒ５を┴終端節点に接続し、枝ｒ５以下の節点（ｅ３，ｅ４）と枝（ｒ９，ｒ１０，ｒ１１，ｒ１２）を削除すると図６の過小評価ＢＤＤになる。 When building an underestimated BDD, connect the “not important” branch selected as described above to the heel end node. By doing so, the state passing through the branch is not included in the BDD regardless of the subsequent link state, and thus is underestimated. If the branch r5 in FIG. 4 is connected to the heel end node and the nodes (e3, e4) and branches (r9, r10, r11, r12) below the branch r5 are deleted, the underestimated BDD in FIG. 6 is obtained.
この操作は、任意の枝に対して行えるし、任意の数の枝に対して行うことができる。このようにして構築した過大評価あるいは過小評価のＢＤＤは、元のＢＤＤより必ず小さくなる（節点が少なくなる）。よって、メモリを削減できる。ただし、この操作を行う枝の数によっては真の連結確率に近似する精度が低下することになる。 This operation can be performed on an arbitrary branch or an arbitrary number of branches. The overestimated or underestimated BDD constructed in this way is always smaller than the original BDD (the number of nodes is reduced). Therefore, the memory can be reduced. However, the accuracy of approximating the true connection probability decreases depending on the number of branches on which this operation is performed.
また、「重要ではない」枝の選択手法として次のような方法も考えられる。たとえば、図９のように、ｅ１がｅ２と同じ土管（経路）を通過しているとき、ｅ１のみが稼働し、ｅ２が故障するという状況は極めて起こりにくい。この状況を簡単に表すため、（１，０，・・・）という状態の確率を無視してｅ２から┴節点に接続する。 In addition, as a method for selecting an “unimportant” branch, the following method may be considered. For example, as shown in FIG. 9, when e1 passes through the same earth pipe (route) as e2, only e1 operates and a situation where e2 fails is extremely unlikely. In order to express this situation simply, the probability of the state of (1, 0,...) Is ignored and connection is made from e2 to the saddle node.
実際には「重要ではない」枝を選択するための所定値を設定し、「重要ではない」枝全てに対して、あるいは「重要ではない」枝のうち任意の枝に対してこの操作を行い、メモリ使用量が物理メモリサイズを下回る程度に調整することが望ましい。たとえば、各辺（ｅｉ）に対応する節点数に上限を設けることで、メモリ使用量を制限できる。具体的には、辺ごとの最大節点数をｕ、辺数をｍ、節点あたりのメモリ使用量をｂとすると、メモリ使用量ｕ×ｍ×ｂが物理メモリサイズを超えないようにｕ，ｍ，ｂを設定することができる。図５や図６では、ｅ３以下の辺について、辺ごとの節点数が１以下になるようにしている。 Actually, a predetermined value for selecting the “unimportant” branch is set, and this operation is performed on all the “unimportant” branches or on any of the “unimportant” branches. It is desirable to adjust the memory usage amount to be less than the physical memory size. For example, the memory usage can be limited by setting an upper limit on the number of nodes corresponding to each side (e i ). Specifically, if the maximum number of nodes per side is u, the number of sides is m, and the memory usage per node is b, u, m so that the memory usage u × m × b does not exceed the physical memory size. , B can be set. In FIGS. 5 and 6, the number of nodes per side is set to 1 or less for the sides of e 3 or less.
そして、過大評価ＢＤＤと過小評価ＢＤＤについて図４で説明したように連結確率を計算し（連結確率算出手順）、真の連結確率に近似する確率値を取得する（真値推定手順）。 Then, the connection probability is calculated for the overestimated BDD and the underestimated BDD as described with reference to FIG. 4 (connection probability calculation procedure), and a probability value approximate to the true connection probability is acquired (true value estimation procedure).
図７は、図５及び図６で説明した二分決定図構築手順を説明するフローチャートである。ＢＤＤ節点の作成を一回のループとし、各ループで節点の作成と枝の接続を行う。節点作成ステップＳ０１と、従来通りの枝接続ステップ（Ｓ０４、Ｓ０７）は、非特許文献１と同じである。枝選択手順での枝の重要度判定ステップ（Ｓ０２、Ｓ０５）と、二分決定図構築手順での重要ではないと判定された枝の接続ステップ（Ｓ０３、Ｓ０６）が、本実施形態に特徴的なステップとなる。
FIG. 7 is a flowchart for explaining the binary decision diagram construction procedure described in FIGS. 5 and 6. BDD nodes are created as a single loop, and nodes are created and branches are connected in each loop. The node creation step S01 and the conventional branch connection steps (S04, S07) are the same as in
図８は、本実施形態の信頼性評価装置を説明する図である。信頼性評価装置は、複数のノードが複数のリンクで接続されたネットワークにおけるノード間の連結確率を、二分決定図を用いて算出し、ネットワークの信頼性を評価する信頼性評価装置であって、
前記二分決定図の任意の節点において任意の基準値を満たす枝を選択する枝選択部（枝重要度判定部）２３と、
前記枝選択部が選択した枝を連結状態を表す終端節点へ接続して過大評価二分決定図を構築し、前記枝選択部が選択した枝を非連結状態を表す終端節点へ接続して過小評価二分決定図を構築する二分決定図構築部１３と、
前記二分決定図構築部が構築した前記過大評価二分決定図と前記過小評価二分決定図それぞれについて、各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する連結確率算出部１５と、
前記確率算出部が算出した２つの前記連結確率から前記ネットワークの真の連結確率が存在する範囲を見出す真値推定部（不図示）と、
を備える。
信頼性評価装置は、さらに、ネットワーク情報入力部１１、ネットワーク情報データベース１２、節点作成部２１、枝接続部２２、及び二分決定図データベース１４を備える。
FIG. 8 is a diagram for explaining the reliability evaluation apparatus according to the present embodiment. The reliability evaluation device is a reliability evaluation device that calculates the connection probability between nodes in a network in which a plurality of nodes are connected by a plurality of links, using a binary decision diagram, and evaluates the reliability of the network.
A branch selecting unit (branch importance determining unit) 23 for selecting a branch satisfying an arbitrary reference value at an arbitrary node of the binary decision diagram;
An overestimation binary decision diagram is constructed by connecting the branch selected by the branch selection unit to a terminal node representing a connected state, and an underestimation is performed by connecting the branch selected by the branch selection unit to a terminal node representing a non-connected state. A binary decision
For each of the overestimated binary decision diagram and the underestimated binary decision diagram constructed by the binary decision diagram construction unit, the probability of each node is calculated, and the calculated probability is used to connect the nodes to be connected in the network. A connection
A true value estimation unit (not shown) for finding a range in which the true connection probability of the network exists from the two connection probabilities calculated by the probability calculation unit;
Is provided.
The reliability evaluation apparatus further includes a network
ネットワーク情報入力部１１は、ネットワーク形状とリンク稼働率をネットワーク情報データベース１２に保存する。次に、ＢＤＤ構築部１３が２つＢＤＤ（過大評価ＢＤＤ及び過小評価ＢＤＤ）を構築し、二分決定図データベース１４に保存する。このとき、節点作成部２１と枝接続部２２とが連携し、枝重要度判定部２３が判定した枝の重要度によって接続先を変える、図７に示したステップ（Ｓ０３、Ｓ０６）が、本信頼性評価装置の特徴点である。具体的には、節点作成部２１がステップＳ０１を行い、枝重要度判定部２３がステップＳ０２とＳ０５を行い、枝接続部２２がステップＳ０３、Ｓ０４、Ｓ０６及びＳ０７を行う。確率計算部１５は、ＢＤＤとネットワーク情報（リンク稼働率）から、過大評価ＢＤＤ及び過小評価ＢＤＤに基づく連結確率を計算する。そして、計算された連結確率に基づき真値推定部が真の連結確率が存在する範囲を推定する。
The network
（効果）
本実施形態の信頼性評価装置は、メモリ使用量を削減し、従来は不可能だった規模のネットワークに対して、連結確率を計算できるようになる。
(effect)
The reliability evaluation apparatus according to the present embodiment can reduce the amount of memory used and calculate the connection probability for a network of a scale that has been impossible in the past.
１１：ネットワーク情報入力部
１２：ネットワーク情報データベース
１３：二分決定図構築部
１４：二分決定図データベース
１５：連結確率算出部
２１：節点作成部
２２：枝接続部
２３：枝選択部（枝重要度判定部）
11: Network information input unit 12: Network information database 13: Binary decision diagram construction unit 14: Binary decision diagram database 15: Connection probability calculation unit 21: Node creation unit 22: Branch connection unit 23: Branch selection unit (Branch importance determination) Part)
Claims (3)
前記二分決定図の任意の節点において連結確率が所定値より小さいもしくは最小の枝を選択する枝選択手順と、
前記枝選択手順で選択した枝を連結状態を表す終端節点へ接続して過大評価二分決定図を構築し、前記枝選択手順で選択した枝を非連結状態を表す終端節点へ接続して過小評価二分決定図を構築する二分決定図構築手順と、
前記二分決定図構築手順で構築した前記過大評価二分決定図と前記過小評価二分決定図それぞれについて、各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する連結確率算出手順と、
前記確率算出手順で算出した２つの前記連結確率から前記ネットワークの真の連結確率が存在する範囲を見出す真値推定手順と、
を順に行う信頼性評価方法。 A reliability evaluation method for calculating a connection probability between nodes in a network in which a plurality of nodes are connected by a plurality of links, using a binary decision diagram, and evaluating the reliability of the network,
A branch selection procedure for selecting a branch having a connection probability smaller than or equal to a predetermined value at an arbitrary node of the binary decision diagram;
An overestimation binary decision diagram is constructed by connecting the branch selected in the branch selection procedure to a terminal node representing a connected state, and an underestimation is performed by connecting the branch selected in the branch selection procedure to a terminal node representing an unconnected state. A binary decision diagram construction procedure for constructing a binary decision diagram;
For each of the overestimated binary decision diagram and the underestimated binary decision diagram constructed in the binary decision diagram construction procedure, the probability of each node is calculated, and the calculated probability is used to connect the nodes to be connected in the network. A connection probability calculation procedure for calculating a connection probability;
A true value estimation procedure for finding a range where the true connection probability of the network exists from the two connection probabilities calculated in the probability calculation procedure;
Reliability evaluation method to perform in order.
前記二分決定図の任意の節点において連結確率が所定値より小さいもしくは最小の枝を選択する枝選択部と、
前記枝選択部が選択した枝を連結状態を表す終端節点へ接続して過大評価二分決定図を構築し、前記枝選択部が選択した枝を非連結状態を表す終端節点へ接続して過小評価二分決定図を構築する二分決定図構築部と、
前記二分決定図構築部が構築した前記過大評価二分決定図と前記過小評価二分決定図それぞれについて、各節点の確率を算出し、算出した確率を用いて、前記ネットワークにおける前記連結対象のノード間の連結確率を算出する連結確率算出部と、
前記確率算出部が算出した２つの前記連結確率から前記ネットワークの真の連結確率が存在する範囲を見出す真値推定部と、
を備える信頼性評価装置。 A reliability evaluation apparatus for calculating a connection probability between nodes in a network in which a plurality of nodes are connected by a plurality of links, using a binary decision diagram, and evaluating the reliability of the network,
A branch selection unit that selects a branch having a connection probability smaller than or equal to a predetermined value at an arbitrary node of the binary decision diagram;
An overestimation binary decision diagram is constructed by connecting the branch selected by the branch selection unit to a terminal node representing a connected state, and an underestimation is performed by connecting the branch selected by the branch selection unit to a terminal node representing a non-connected state. A binary decision diagram construction unit for constructing a binary decision diagram;
For each of the overestimated binary decision diagram and the underestimated binary decision diagram constructed by the binary decision diagram construction unit, the probability of each node is calculated, and the calculated probability is used to connect the nodes to be connected in the network. A connection probability calculation unit for calculating a connection probability;
A true value estimation unit for finding a range in which the true connection probability of the network exists from the two connection probabilities calculated by the probability calculation unit;
A reliability evaluation apparatus comprising:
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2016146887A JP6581546B2 (en) | 2016-07-27 | 2016-07-27 | Reliability evaluation method, reliability evaluation apparatus and program |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2016146887A JP6581546B2 (en) | 2016-07-27 | 2016-07-27 | Reliability evaluation method, reliability evaluation apparatus and program |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2018019192A JP2018019192A (en) | 2018-02-01 |
| JP6581546B2 true JP6581546B2 (en) | 2019-09-25 |
Family
ID=61082078
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2016146887A Active JP6581546B2 (en) | 2016-07-27 | 2016-07-27 | Reliability evaluation method, reliability evaluation apparatus and program |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP6581546B2 (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP7093972B2 (en) * | 2019-06-06 | 2022-07-01 | 日本電信電話株式会社 | Approximate ZDD construction method, approximate ZDD construction device and program |
| WO2023017565A1 (en) * | 2021-08-10 | 2023-02-16 | 日本電信電話株式会社 | Reliability calculation method, reliability calculation device, and program |
| JP7773729B2 (en) * | 2022-07-13 | 2025-11-20 | Ｎｔｔ株式会社 | Network reliability calculation method, network reliability calculation device and program |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4558768B2 (en) * | 2007-08-15 | 2010-10-06 | 日本電信電話株式会社 | Communication network reliability approximate calculation method and apparatus |
| JP2009272856A (en) * | 2008-05-07 | 2009-11-19 | Nippon Telegr & Teleph Corp <Ntt> | Method and device for calculating reliability approximation of communication network with approximation precision security |
| US8121042B2 (en) * | 2008-06-30 | 2012-02-21 | The Boeing Company | Reliability estimation methods for large networked systems |
| JP6282606B2 (en) * | 2015-03-17 | 2018-02-21 | 日本電信電話株式会社 | Network evaluation apparatus, network evaluation method, and network evaluation program |
-
2016
- 2016-07-27 JP JP2016146887A patent/JP6581546B2/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| JP2018019192A (en) | 2018-02-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US9705773B2 (en) | Parallelized network traffic flow availability simulation using stochastic process and traffic engineering algorithms | |
| CN108667727B (en) | Network link fault processing method and device and controller | |
| US8935142B2 (en) | Simulation of communication networks | |
| JP6581546B2 (en) | Reliability evaluation method, reliability evaluation apparatus and program | |
| US8665731B1 (en) | Reliability estimation methods for large networked systems | |
| CN114298431B (en) | A network path selection method, device, equipment and storage medium | |
| JP6282606B2 (en) | Network evaluation apparatus, network evaluation method, and network evaluation program | |
| JP7131393B2 (en) | Information processing device, information processing method and program | |
| JP2016532181A (en) | System and method for distance approximation in graphs | |
| JP2010011285A (en) | Network topology candidate listing method and apparatus, and network topology designing method, system, and program | |
| JP6981232B2 (en) | Network design equipment, methods, and programs | |
| JP7063274B2 (en) | Information processing equipment, neural network design method and program | |
| EP3225000A1 (en) | Determining bandwidth requirements for network services | |
| Hui | Monte Carlo network reliability ranking estimation | |
| US10103971B2 (en) | Route search apparatus and route search method | |
| JP5060515B2 (en) | Ground-to-ground traffic estimation method, ground-to-ground traffic estimation device and program | |
| Blom et al. | A benders-type approach for robust optimization of kidney exchanges under full recourse | |
| Perry et al. | Diffusion approximation for an overloaded X model via a stochastic averaging principle | |
| Won et al. | A greedy algorithm for faster feasibility evaluation of all-terminal-reliable networks | |
| JP7587188B2 (en) | NETWORK MANAGEMENT DEVICE, NETWORK MANAGEMENT METHOD AND PROGRAM | |
| JP2010206581A (en) | Topology generation system, method, network topology design system, and program | |
| JP6939516B2 (en) | Network design equipment, methods, and programs | |
| JP6602259B2 (en) | State transition evaluation device, state transition evaluation method, and state transition evaluation program | |
| US12513054B2 (en) | System configuration derivation device, system configuration derivation method, and computer-readable medium | |
| WO2024250199A1 (en) | Device and method for network performance analysis |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A821 Effective date: 20160727 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20180810 |
|
| A711 | Notification of change in applicant |
Free format text: JAPANESE INTERMEDIATE CODE: A711 Effective date: 20180810 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A821 Effective date: 20180810 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20190520 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20190625 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20190806 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20190827 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20190830 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 6581546 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |