こわれにくいネットワークをデザインする 〜二分化グラフを用いたネットワーク信頼性最大化〜 NTTコミュニケーション科学基礎研究所

私たちNTTグループが提供する通信ネットワークの構築には、さまざまな条件が求められます。例えば、「高速な通信を実現できるかどうか」、「構築に予算がかかりすぎないか」、「遅延なく伝送できるか」、「こわれにくいネットワークかどうか」などです。今回ご紹介するのは、既存の通信ネットワークをこわれにくくするための増強方法を、自動的に見つけるという技術です。万が一、ネットワークを構築している1本の線が切れたとしても、通信できる状態が続くネットワークを「強い」と表現しますが、そういった故障に強いネットワークの形をいかにして見つけられるかを技術開発の目的としています。本技術の優位性や技術を用いることで実現できる未来について、NTTコミュニケーション科学基礎研究所の西野氏に詳しく伺いました。

西野氏（以下、敬称略）：本技術は、「電線に故障が起きる」という現象に限定した「ネットワークのこわれにくさ」を算出しようとしています。では、「こわれにくいネットワーク」とはそもそも何なのか。まずはそこから説明したいと思います。下図のように、2つのネットワークが存在するとします。左の図では、一本の電線が切れた場合、完全にネットワークが使用できなくなります。対して、右のネットワークは、片方の電線が切れた場合でも、もう一本の電線が残っていますから、通信できる状態が続きます。一本の電線が故障するという条件で考えたとき、「左の図と比べて、右の図の方がこわれにくいネットワークである」ということがいえます。つまり、「こわれにくいネットワーク」とは、万が一電線に故障が生じても、通信できる確率が高いネットワークのことを指します。

こうした「ネットワークのこわれにくさ、故障に対する強さ」を「ネットワークの信頼性」と呼んでいます。「信頼性」という尺度は世の中に知られているものですし、既存技術で計算することはできます。しかし、信頼性の計算には非常に時間がかかることが知られており、そのため、信頼性を一番高くするネットワークの構成を見つけることは実現できていませんでした。ですから、ネットワークの設計時には、「できるだけ密に線を張っておく」とか「設備を多めに準備したり、部品を組み合わせたりすることで冗長化する」といった経験則やノウハウを頼りにしていたところがありました。本技術のポイントは、信頼性が最も高いネットワークの構成を自動で計算できるようにした点です。

「信頼性」を算出する問題は非常に難しいものだったというお話をしましたが、難しい理由は2つありました。一つは、ネットワークを構築するための電線（リンク）の配置方法が大量に存在する点です。例えば、電線（リンク）を敷設できる場所の候補が10箇所あるとし、そのうち4箇所を選んでリンクを敷設することでネットワークを構築するとします。たったそれだけでも、100通りを越える候補が存在するわけです。もし、拠点（ノード）と電線（リンク）の数がさらに増えたら、考慮すべきネットワークの候補は、指数的に増加してしまうのです。2 つめの難しさは、こうした天文学的な数の候補から、「最も信頼性の高いネットワークを見つけましょう」というときに、膨大な候補の一つひとつに対して信頼性を計算しなければならない点です。信頼性を調べるためには、ネットワークに配置されている電線の切れ方（故障パターン）を全て調べあげる必要があります。「答えの候補が膨大である点」と、「そのたくさんある答えの候補それぞれに対して、故障パターンを求めなければならない点」が掛け合わさって、計算量が膨れあがっていくのです。とても小さなネットワークを作るにしても、普通の計算機では全く計算ができないくらい時間がかかっていました。

そこで私たちは、こうした難点から、「二分決定グラフ」を用いて、故障パターンの共通項をまとめて小さく表現することで、計算が必要な候補を減らそうと考えました。もともと先行研究などで、「二分決定グラフを用いると、故障パターンを小さく表現することができる」ということは知られていました。先行研究を用いることで故障パターンを圧縮し、その上で、最も信頼性の高いネットワークの候補を特定するところまで計算できる技術を実現しました。これまで計算機で解けなかった「最も信頼性が高いネットワーク」を、高速に、しかも一般的なコンピューターで算出できるようになったのです。

ここからは、本技術を用いた計算機を用いるとどんなことが可能になるのか、実用的な成果についてお話していきます。成果は大きく分けて３つあります。

繰り返しになりますが、成果の1つめは、複数のネットワークの候補から、「最も信頼性が高い（故障に強い）構造」を自動で求めることができるようになったことです。ここで、本技術を用いて開発したデモアプリを紹介します。このデモアプリは鉄道網を用いていて、20の駅と20本の線路を使ったネットワークのうち、最も信頼性が高い構造を自動で算出するというものです。これまで通信ネットワークについてお話してきましたが、鉄道網や道路網、配電網も、どこかが故障してもできる限り動作し続けることが求められます。本技術は、通信以外の様々なネットワークに適応できるため、一例として、鉄道網を使ったデモアプリを作成することにしました。デモアプリで計算すると、一兆越えの候補の中から、わずか0.06秒で、一番故障に強い鉄道網が算出されます。一般的な家庭用PCを用いて、この速さを実現しています。

■デモの実行画面（左）と開発した技術を用いて計算を実行した結果画面（右）

2つめは、計算できる拠点の数を100まで増やし、実際のネットワークの設計時に活用できるようになった点です。拠点とはつまり、鉄道網でいうところの駅の数です。従来技術で求められる拠点は、せいぜい10程度でした。しかし、本技術を用いると、100以上の拠点を用いたネットワークを算出できるようになります。現実的なネットワークの中には、それくらいの規模のものもあると思います。より実用的な技術だといえるのではないでしょうか。

3つめは、「予算」や「信頼性の目標値」といった制限条件を入力し、どの場所に、どんなリンクを張れば制限をクリアできるかを求めることができる点です。「予算を入力し、最も信頼性の高いネットワークを算出する場合」、「信頼性の目標値を入力し、予算をいくらまで下げられるかを算出する場合」どちらも算出可能です。リンクごとに故障率を設定できますし、「まったく何もない状態から、予算いくらでネットワークを構築する場合」も算出することができます。

通信網以外にも、世の中には様々なネットワークがあります。本技術は、鉄道網、道路網、配電網においても、少しだけアレンジを加えれば同様に使える技術だと思います。成果として、「100拠点の問題が解けるようになった」というお話をしましたが、100拠点解けたからといって、200拠点の問題が簡単に解けるかというと、そうではありません。10個拠点が増えるだけで、問題サイズが数千倍まで大きくなってしまう。そんな世界ですから、今後さらなる規模の拡大を目指していきたいと思っています。さらに、現段階は「各電線で独立に故障が起きる」という想定上の研究ですが、台風などの災害時はまとめて故障が起きてしまいます。そういった多様な故障に対応できる技術にしていかなければなりません。「信頼性」以外の尺度を増やすという課題もあります。先日出展した「NTTコミュニケーション科学基礎研究所オープンハウス2018」では、現場の方から「信頼性の尺度だけでは実用化は厳しい」というお話をいただきました。確かに、こわれにくいネットワークが社会にとって一番嬉しいネットワークかというと、そんなことはないわけです。遅延なく伝送できるネットワークや、構築にお金がかかりすぎないネットワークなど、さまざまな尺度が求められています。今後は、信頼性以外の尺度も考慮した技術を開発しなければと考えています。

私たちは基礎研究を行っているため、何か特定の問題だけに活用するのではなく、いろいろな問題に広く使える汎用的な技術にしていきたいという考えがあります。最終的にはどこかで実際に活用していただきたいです。また、今回のお話を通して、「ネットワークを設計する際に、信頼性を数値化して計算機で解いていくという手法が存在すること」を知っていただけたら嬉しいです。今は手動で頑張っているところかもしれませんが、計算化できれば時間もコストも短縮することができます。人手不足にも対応できるかもしれません。

研究は、問題を一つ見つけて、その問題を解くことを追求しているのですが、現場から離れた場所にいると、その問題を見つけること自体が難しくなっていきます。ですから、現実離れしないという点でも、現場の皆さん、利用者の皆さんからいただくお話は、とても貴重な視点だと思っています。現場に近いお話をいろいろ聞いてみたいです。興味がある方は、ぜひ相談に乗っていただけると嬉しいです。よろしくお願いいたします。

2018年9月21日
有限会社ハッテンボール　外山夏央

西野　正彬、井上　武、安田　宜仁、湊　真一、永田　昌明、「二分決定グラフを用いたネットワーク信頼性最適化法」NTT技術ジャーナル Vol.30, No.9 , pp 16-19, 2018
https://journal.ntt.co.jp/backnumber2/1809/files/JN20180916.pdf

M. Nishino, T. Inoue, N. Yasuda, S. Minato, and M. Nagata：“Optimizing Network Reliability via Best-first Search over Decision Diagrams,” Proc. of INFOCOM 2018，pp.1817-1825，Honolulu，U.S.A.，April 2018