l……ll……ll……ll…ll…f…ll川Il……………＝‖州…l…＝‖‖……………lll……ll川Il……llll川Illlll川Illll州‖‖‖川Illll川l…………ll川…llll………lll川Ill川…lll川＝‖‖‖‖‖州＝＝‖‖‖‖…………llll…l州】lネットワークシステムの信頼性の定量的評価法

馳枝故障に対する連結性保持の信頼度計算法叩
今井浩

ネットワークシステムは，f附こ故障にさらされている．ネットワーク信頼度は，描こ対応する点，l‖ほ射こ対応する枝で故障が起こった際に，システムがそれでも」仁射こ動作できる確率を刑曲するものである．本稿では，枝故障の場合のネットワーク全端子信頼度の計算について，計算馴勺には困難であるものの，・い規模サイズの問題であれば呪プ引こ角勘ナることを示す．
キーワード：ネットワーク信頼度，＃P完全，2分決定グラフ（BDD）‡…lll川Il川川‖ll……………………llll州l州‖l川‖l川l川Il川Ill川Il…………………………ll川Illl州…l州Il………………削＝…l………………l…llFll州Illll川l…lllllll州川州…llllllll州州‖

本稿では，著者らのグループが提案しているBDD

1．ネットワーク信頼性（2分決定グラフ）という構造を用いた新解法［2，3］

従来の電話網から先端のインターネットの展開を支を簡単な例で説明し，これによって中規模の通信網モえる情報ネットワークは，社会基盤としての重要性をデルの信頼度β（G）を厳軌こ実用時澗Ⅵで計算できるさらに増しており，その信頼性の定量的評仰が望まれことを述べる．さらに通常用いられるループ構造をもる．阿部［1］は，通信網の安全性という観点からの信つネットワークに対して，日本の地理を反映した仮想相性設計について述べている．通信網のみならず，電ネットワークを考え，そのような場合にこの解法が非力やガスといった社会基盤でも同様で，例えば電力綱常に有効に働くことを示す．このような解析を通してについて解説したものに加藤［5］がある．電話を中心ネットワーク構築に資するところまで発展させていくとした通信網の場合，そこでは電話の中継局そのものことが望まれるが，本稿ではそのための土台として必も故障するモデルを検討している．しかし，中継局の要な定量的解析で新たにできるようになったことの解ような一ギ加勺施設については，耐震構造にするなどの反説を試みる

映で中継局は安全であると仮定して対策が立てられて2．ネットワーク信頼度の計算いる場合もある．

本稿では，中継局では故障が生じず，中継局間を結ぶ回線にのみ障害が生じる場合の信頼性を定量的に評価する方法について論じる．ネットワーク構造をグラフとみなすと，回線故障は枝の切断に対応する．ある回線に故障があったとしても，迂回路を使うことにより連結可能にすることは，杖が除去されたネットワークが連結であることに対応する．最も基本的な全端子
ネットワーク信頼度は，故障が確率的に生じたときの定義より枝集合且のグラフCで枝eの消滅確率がカ（e）の場合の全端子信頼度β（C）は姉）＝写也（ト如））・蕊。如））となる．ここで，利は全11を連結する枝部分集合である全域枝集合月⊆g全てについてとる．この信蛸度

β（G）は，枝eに対して次の漸化式を満たす．ここで，G／e，C＼eは杖eを削除・縮約したグラフを表す．
（1−カ（e））斤（G／e） e：橋

ネットワークの耐故障性を確率として評価したものである．具体的には，グラフGの各杖eが確率カ（e）で独立に消滅するとき，残った枝からなる部分グラフがガ（C）＝β（G＼e）

カ（e）斤（C＼e）十（1−カ（e））ガ（G／e）

他の場合連結である確率を，このグラフの全端子信頼度斤（G）と呼ぶ．

e：ループ

ここで杖eが橋であるとは，その杖を開放除去すると元は連結なグラフが連結でなくなることをいう．ル

いまい ひろし東京大学大学院情報哩工学系研究科〒113−0033文京区本郷7−3−1
2003年7月号

ープは自己閉路のことである．その他で，カ（e）β（C＼e）という項は杖eが消滅してしまった場合の信柑度© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（3）467

を，（1−♪（e））斤（C／e）という項は枝eがなくならず，グラフがもつ場合等は，このアプローチが特に有効にしたがって縮約で短絡除去したグラフのβ（G／e）を計なる．

算することに帰着させてこの場合の信頼度を計算する

もので，それを足せば全体の信頼度が出てくる．

枝の順番を一つ固定して，この漸化式をその杖順に適用していくと，2分木構造へ展開して全端子信頼度斤（C）を計算する過程が得られる．その計算過程で，

3．実際の計算例実際にこのくらい大規模でも計算できるのだということを，実例で示していく．

3．1完全グラフの全端子間信頼度の多項式時間計

それまでに同じ枝部分集合を展開していった（展開木構造で同じレベルの）ところに完全に同じグラフがた

算

まず，上述の完全グラフの場合について，対称性をくさん現れる．それらのグラフは，同じなので当然信活用することによってこの場合に特別構成できる多項頼度も同じである．Imai，Sekine，Imai［3］，今井

式時間アルゴリズムを錯＝50点までの完全グラフに［2］は，この展開の2分木構造で同じグラフを一つに適用し，その信根度関数のグラフを図2に示す．50まとめることが容易にでき（すると展開木構造は木で点と小規模に見えるが，完全グラフであるので50点はなくレベル化されたグラフになる），その構造を計算しながら信頼度斤（C）が計算できることを示した．の場合＝1225本の枝がある．
で （冒）

図1はそれを完全グラフ晶の場合で示したものであ3．2 一般の場合の実験グラフる．図の右側が，BDDに対応した信根度計算の直線

以下では，一般の場合について，上述の関根らのアプログラムである．このまとめ。共有化をせずにどんプローチで分離集合などよい性質がある典型例である

どん展開していった場合，展開木の葉の個数は元のグkxk格子グラフと，Karger，Tai［4］によって実験にラフの全域木の数になる．晶の場合はたかが9であ用いられているグラフ例のDelaunay三角形分割と近るが，実際にはこれが指数的に爆発するので計算が困接グラフの例を示す．ここでの実験は，古いSUN難なのを，この共有化によって中規模問題まで克服す

Ultra170MHz CPU，256MBメモリのワークステるという手法である．詳細は文献［2］を参照されたい．

ーションを用いている．

この展開グラフは，論理関数を表すグラフ構造であ3．2．1格子グラフ

るBDDと関係しており，単にBDDと呼ぶ．この々×た格子グラフC々，々の信根度計算結果を図3，表BDDは，グラフの枝を解放除去。短絡除去していく

1に示す．このように，点数で100弱，枚数で200弱と，根の0レベルから最終的に空グラフに対応する枚のグラフの信根度を正確に計算することができる．

数のレベルまでのグラフ（それぞれマイナーと呼ばれ3．2．2 Delaunay三角形分割る）が得られる．マイナーの総数をBDDの点数といDelaunay三角形分割は，計算幾何で代表的な構造う．同じマイナーを共有することによって，通常はであり，幾何的な近さを素直に実現したグラフである．

倍々で増えていく展開構造をかなりコンパクトにおさえることができる．特に，地理的制約から平面構造をReliabilityR（Kn，P）∫l：＝1；

チ干こ／1：二（1−か）＊Sl；

1一ン／＼＼′2：＝か＊Sl；

く二＞∫−：＝（1−少2）＊fl；1−〝2 S2：＝カ2＊∠1＋（1カ2）＊′2；

l−p2「＼＼＼ごL◎−（■フ⑳β（垢）：＝Sl＋（1−♪3）＊∫2；月（方3）図1BDDによる信楯度計算
468（4）

図2 完全グラフ茸柁の信柏度（乃＝2，‥・，50）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

ここでは，正方形内に50ノ・プ弐が一様分布した例をlぎ‡4

ReliabilityR（Gk．k，P）に示す．BDDアプローチでの杖順は，点をエ座標順に並べ，それから枝順を決定している．

3．2．3 70点の近接グラフ
図5，6に，通信網で近めのところをある程度の冗長度をもって構成したモデルである近接グラフの例を示す（構成法は文献［2］参照）．図5は点数が50ノ．tこ（で信頼度のグラフを示したもの，図6は∴一式数が70点で，枚数205のもので計算過程情報を示したものである．
この場合は，基本的に≠lミ軋・1（の㌃座標順優先で杖を並べて展開すると，BDDでの各レベルの点数（幅）が小さくおさえられる．理論的には，元のグラフで枝川f真
図3 格子グラフCた，カの信頼度（カ＝2，…，10）に対して消去面（図のfront）というものを考えたと

表1格イ▲グラフCた，々の在‡頼度関数尺（G彪，々；♪）
k ReliabilityPolynomialR（G擁；P）

2 −3p4＋8p3−6p2＋1

3 79p12−560pll＋1668plO−2656p9＋2331p8−960p7＋96p5＋21p4−16p3−4p2＋1
4 −17493p24＋232144p23−1409764p22＋5168576p21−12693232p20＋21854512p19−26726036p18＋22824576p17−12739373p16＋3710880p15＋139672p14−370176p13−35464p12＋

63968pll＋5912plO−7808p9−1791p8＋656p7＋204p6＋64p5−8p4−16p3−4p2＋1
5 32126211p40−681809240p39＋6852471548p38−43322118652p37＋192968405711p36−642590690400p35＋1655933457966p34−3370276114636p33＋5476061558391p32−
7122774813980p31＋7375859530466p30【5981426876044p29＋3667377815630p28−
1573096624396p27＋375423772810p26＋9584416484p25−26112103320p24−6268146140p23＋8011274210p22−1051500660p21−575028980p20−53196700p19＋139031550p18−
2265380p17−10705120p16−3593556p15＋1357510p14＋394172p13＋35042p12−49636pll−10290plO−2036p9＋1021p8＋164p7＋250p6＋64p5−11p4−20p3−4p2＋1
Reliability（a）図4（a）50，L．1烹のDelaunay三角形分割，（1〕）4；；
2003年7‖号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）469Reliability（a）

図5（a）50点の近接グラフ，（b）信頼度100
1ev色1150

図6 70点205枝の近接ネットワーク（左）とその信頼度計算BDDのレベル毎の幅（右）き，それの指数オーダ（正確にはCatalan数）で幅がほぼおさえられることがわかっている．このように200本を超えるネットワークでも漸化式を厳密に展開して信頼度関数を正確に求めることができる．
3．2．4 ループ構造をつないだグラフ

ループ構造は，1枝故障に対し，その枝を含まない方のルートに変更という最も簡単な操作によって耐故障性が実現でき，十分に信頼できる回線を使っているもとで現実的に使いやすいものである．日本のように地理的に細長い場合，各地域でループ構造を構築し，それらをつなぐネットワークも素直である．ここでは，本稿の投稿時点でのNTTホームページの耐災性。信
頼性向上に関するページの模式図や日本の光交換ネッ
耶0（6）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

200理論的。実際的研究が面白いと思、われるし，また離散表2 ループ連結ネットワークでのBDDサイズと幅
場合

点数

枝数

BDD

BDD

全域枝サイズ（a）47（b）

48 114集合数

幅319132629

190 1．9×1032

67

9．6×1013システム論の観ノたからは無向グラフから有向グラフに拡張して，グリードイドと有向グラフの信頼度の解析が関係するなど，面白い題材が多数ある
本稿が少しでも，「とにかく難しい問題を実際に解いて何らかの答を山すことがインパクトを与える」ことにつながっていれば辛である．
トワークの例［6］などを例に，l粟】7のような47点，67枝の仮想ネットワークを考え，謝辞 本研究での成果は，OR学会創立40周年記念（a）このグラフでの信頼度を計算，事業特別研究プロジェクトに選定された「ネットワー（l〕）このネットワークにさらに1∴Il加え，その点を既ク構造を有するライフラインシステムの危機対応管理存の点と全て結んだグラフでの有；頼度を計算体制に関する研究」（代表者：大11▼l達雄）の研究の一する際に，計算構造であるBDDがどのくらいのサイズになるかを表2に示す．上述の近接グラフよ環から得られたものである．
りもも
参考文献

っと小さな計算構造で厳密に圭；蛸度が計算できることがわか−），したがってこのネットワーク上での種々の［1］阿部戚郎：通仁髄のセーフティー電話網の有潤滑三設計−，応川数理，Vol．9，No．4（1999），PP．298−309．

最適化なども容易になっている．

［2］今井浩：ネットワーク信頼度計算の周辺一組合せ数え4．おわりに上げの新展開，離散構造とアルゴリズムⅤ（藤垂悟編），以上，ネットワーク信頼度計算について計算例をI二‡￣l
心に述べてきた．計算の観∴t．（からは，信頼度計算とい近代科学札（1998），pP．ト50．

［3］H．Imai，K．Sekine and K．Imai：ComputationalInvestigations of Al卜TerminalNetwork Reliability

う＃P完全の難しい数え上げ問題などに対して，これVia BDDs，1NCE Tmns．凡ndamenlals，Vol．E82−A，までの手法では解けなかったサイズのl己月題で，実際に解く要請がある問題を解けるようにすることについてNo．5（1999），pp．714−721．
［4］D．Karger and R．P．Tai：Implementing a Fully

述べてきたことになる．

PolynomialTime Approximation Scheme for All

これは，理論を展開することによりそれまでその理

TerminalNetworkReliability，P7VCeedings〆the81h

論なしでは解けなかったl冒1退を現実に解けるようにす．」（1．1トメ／．1．1／下l・川／）りバ／…ノ／り〃 r小川イ（．・帖．り■〟ん川J、るという，理論研究によるインパクトの説明でもある．

（1997），pp．334−343．

実際，BDDの研究は，VLSICADでの応別が華々し［5］加藤守利：電力供給システムにおけるリスク管軋応

川数判と，Vol．9，No．4（1999），pp．310−321．

く展開さズ1，その組合せ論への拡張を通してその離散システム論としての理論が深まるとともに，このよう［6］宮本健太郎，借用二洋明，村附正幸＼宮原秀夫：波長変換に信頼度計算の関係からは計算グラフとしての本質を明らかにするところまでつながっている．計算量理論。アルゴリズム理論の観′・ご弐からはさらなるBDDのに制限のある光交枚ネットワークの性能評価−リンクに複数のファイバがある場合−，電子情報通イ言学会論文誌

B，Vol．J83−B，No．8（2000），Pp．1125−1134．

用語解説

カタラン数（Cata［an numbers）

さまざまなグラフにおける枚挙問題に現れる数字であり，C乃＝嘉2乃C乃の関係式で与えられる．1，2，5，14，42，132，429，…という自然数列になる．乃×乃の刀三方格子：伏の退路をある角から最遠端の角まで行く最短経路の数，乃項式に括弧を挿入する組合せの数，凸町多角形を三角形に分割するプバ去の総数などに現れる．ベルギーの数学者E．C．

Catalan（1814〜1894）に閃んで名付けられた．
2003年7月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）471