(57)【要約】【課題】限られた検証回数内で検証カバレッジを最大化できるネットワークの検証最適化方法およびシステムを提供する。【解決手段】経路探索部１０は、クライアントペアごとに最短経路を計算する。障害ユニット登録部２０は、クライアントペアとその経路上の各一のリンクを障害発生リンクeと想定する障害ユニットを登録する。類似度指標値計算部３０は、障害ユニットごとにリンクe障害時のネットワークトポロジの類似度指標値を計算する。類似度評価部４０は、障害ユニットごとに計算された各類似度指標値に基づいて障害ユニット同士の類似度を評価する。最適化部５０は、相互に類似する障害ユニットについては、いずれか一の障害ユニットのみに検証を実施すれば他の障害ユニットについては検証したものとみなし、限られた検証回数内で「実施した検証回数」＋「みなし検証回数」が最大となる障害発生箇所のセットを導出する。【選択図】図１
2018137668.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークに接続するクライアントペア（ci，cj）とその経路上の各一のリンクekとのセットに係る障害ユニット(ci，cj，ek)ごとに、当該一のリンクekが障害個所である場合の類似度指標値を計算する手段と、
障害ユニット(ci，cj，ek)間の類似度を、その類似度指標値に基づいて評価する類似度評価手段と、
相互に類似する障害ユニット(ci，cj，ek)の検証を、当該類似する障害ユニット(ci，cj，ek)のいずれか一の障害ユニットに対して実施すれば他の類似する障害ユニットは実施済みとみなし、実施した検証回数とみなし検証回数との総和を最大化する障害個所を抽出する手段とを具備したことを特徴とするネットワークの検証最適化装置。
【請求項２】
前記類似度指標値が、障害発生前の経路のパス長、障害発生後に再探索された迂回経路のパス長および前記障害個所のネットワーク階層の少なくとも一つを含むことを特徴とする請求項１に記載のネットワークの検証最適化装置。
【請求項３】
前記類似度指標値が、リンク帯域、スイッチ接続次数、遅延およびリンクの重要度の少なくとも一つを含むことを特徴とする請求項１または２に記載のネットワークの検証最適化装置。
【請求項４】
ネットワークに接続するクライアントペア（ci，cj）とその経路上の各一のリンクekとのセットに係る障害ユニット(ci，cj，ek)ごとに、当該一のリンクekが障害個所である場合の類似度指標値を計算する第1手順と、
ネットワーク上の障害箇所ごとに、当該障害個所を経路に含む各障害ユニット間の類似性を前記類似度指標値に基づいて評価する第２手順と、
障害個所ごとに相互に類似する障害ユニットの集合Dを導出する第３手順と、
検証する障害個所に係る障害ユニットの集合Dを集合Zに集約する第４手順と、
検証数に制約条件を設定する第５手順と、
前記集合Zの障害ユニット数を最大化する障害個所を前記第２ないし第５手順を用いて整数計画問題として計算する第６手順とを含むネットワークの検証最適化方法。
【請求項５】
前記類似度指標値が、障害発生前の経路のパス長、障害発生後に再探索された迂回経路のパス長および前記障害個所のネットワーク階層の少なくとも一つを含むことを特徴とする請求項４に記載のネットワークの検証最適化方法。
【請求項６】
前記類似度指標値が、リンク帯域、スイッチ接続次数、遅延およびリンクの重要度の少なくとも一つを含むことを特徴とする請求項４または５に記載のネットワークの検証最適化方法。
【請求項７】
前記請求項４ないし６のいずれかに記載のネットワークの検証最適化方法をコンピュータに実行させるネットワークの検証最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの検証最適化方法、プログラムおよび装置に係り、特に、検証工数の削減により、限られた検証回数内で検証カバレッジを最大化できるネットワークの検証最適化方法、プログラムおよび装置に関する。
【背景技術】
【０００２】
ネットワーク障害試験の効率化として、従来から障害試験の自動化手法が各種提案されている。非特許文献１には、既存の商用ネットワークに対して装置の増設、変更、ネットワークOSのバージョンアップなどを実施する前に、商用ネットワークを模擬した検証環境でネットワークの振る舞いや動作検証を行うために、検証環境の構築、検証の実施、結果分析を自動実行するシステムが提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】「ホワイトボックススイッチとOSSを活用したネットワークに対する検証自動化システム設計に関する一提案」、渋谷惠美・川上秀彦・長谷川輝之・山口弘純、信学技報、vol. 116、no. 111、NS2016-34、pp. 35-40、2016年6月。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１は、検証環境の構築から検証の実施、結果分析等を自動で行うことで、従来検証作業者が人手で行っていた検証作業の工数を大きく削減している。しかしながら、自動で実行できるようになるため、検証者はそれまで人手では対応しきれなかったネットワーク全体を網羅的に検証することで検証性能の向上を目指すようになることから、検証項目がさらに増加することが考えられる。
【０００５】
さらに、検証時間は限られているため、与えられた検証時間内で網羅的な障害試験が完了できるとは限らないという課題がある。
【０００６】
本発明の目的は、上記の技術課題を解決し、限られた検証回数内で検証カバレッジを最大化でき、効率的な検証を可能にするネットワークの検証最適化方法、プログラムおよび装置を提供することにある。
【課題を解決するための手段】
【０００７】
上記の目的を達成するために、本発明は以下の構成を具備した点に特徴がある。
【０００８】
(1) 本発明のネットワーク障害試験装置は、ネットワークに接続するクライアントペア（ci，cj）とその経路上の各一のリンクekとのセットに係る障害ユニット(ci，cj，ek)ごとに、当該障害ユニットのリンクekが障害個所である場合の類似度指標値を計算する手段と、障害ユニット(ci，cj，ek)間の類似度を、その類似度指標値に基づいて評価する類似度評価手段と、相互に類似する障害ユニット(ci，cj，ek)の検証を、当該類似する障害ユニット(ci，cj，ek)のいずれか一の障害ユニットに対して実施すれば他の類似する障害ユニットは実施済みとみなし、実施した検証回数とみなし検証回数との総和を最大化する障害個所を抽出する手段とを具備した。
【０００９】
(2) 本発明のネットワーク障害試験方法は、ネットワークに接続するクライアントペア（ci，cj）とその経路上の各一のリンクekとのセットに係る障害ユニット(ci，cj，ek)ごとに、当該障害ユニットのリンクekが障害個所である場合の類似度指標値を計算する第1手順と、ネットワーク上の障害箇所ごとに、当該障害個所を経路に含む各障害ユニット間の類似性を前記類似度指標値に基づいて評価する第２手順と、障害個所ごとに相互に類似する障害ユニットの集合Dを導出する第３手順と、検証する障害個所に係る障害ユニットの集合Dを集合Zに集約する第４手順と、検証数に制約条件を設定する第５手順と、前記集合Zの障害ユニット数を最大化する障害個所を前記第２ないし第５手順を整数計画問題として計算する第６手順とを設けた。
【００１０】
(3) 前記類似度指標値が、障害発生前の経路のパス長、障害発生後に再探索された経路のパス長および前記障害個所のネットワーク階層の少なくとも一つを含むこととした。
【００１１】
(4) 前記類似度指標値が、リンク帯域、スイッチ接続次数、遅延、リンク数、次数およびリンクの重要度の少なくとも一つを含むこととした。
【発明の効果】
【００１２】
本発明によれば、以下のような効果が達成される。
【００１３】
(1) 検証が実質的に重複することになる障害ユニットをそのトポロジの類似性に基づいて探索し、トポロジが類似する障害ユニット集合においては、その一の障害ユニットを検証すれば他の検証ユニットも検証したと見なすので、重複検証が回避されて検証回数が減ぜられ、効率的な検証が可能になる。
【００１４】
(2) 予め指定された検証回数内で、「実施した検証回数」と「みなし検証回数」との総和を最大化する障害個所を探索するので、限られた検証回数内で検証カバレッジを最大化でき、効率的な検証が可能になる。
【００１５】
(3) トポロジの類似性が、採用する指標値に依存するので、検証対象のネットワークに応じて類似度指標値を変更することでネットワーク毎に適正な類似判断が可能になる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態に係るネットワークの検証最適化装置の機能ブロック図である。
【図２】リンク障害の発生前後で経路が変化する様子を示した図である。
【図３】ネットワークトポロジの類似性を説明するための図である。
【図４】類似セット集合D(e)の導出例を示した図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態について詳細に説明する。ここでは、初めに本発明の概要について説明し、次いでその実施形態を説明する。
【００１８】
本発明は、ネットワークプロバイダが運用する商用ネットワークを検証対象とし、このようなネットワーク上には、その形状や階層などが類似したトポロジ（サブトポロジ）が存在する。トポロジは、図２に示すように複数の階層kで構成され、クライアントcはトポロジのリーフに収容される。
【００１９】
一般的に、単一リンク障害試験では、ネットワーク上の全リンクに対して各１回の障害を発生させることで検証を試行する。クライアントペア間の疎通検証は、全てのクライアントペア間の経路を対象に、当該経路を構成する各リンクの障害毎に確認を行う。従って、検証の最小単位は、クライアントペアとその障害発生前経路上の障害発生リンクとのセットである。本実施形態では、このようなセットを「障害ユニット」と表現し、後に詳述するように、前記最小単位のトポロジの類似性を定量的に評価する一指標として採用している。
【００２０】
クライアントペアci，cj間の障害発生前の経路のパス長がHijの場合、次式(1)に示すように、ネットワークを網羅的に検証するためにはF回の検証が必要となる。
【００２１】
【数１】
2018137668.tif 000003
【００２２】
これに対して、本発明では限られた検証回数で最大限の検証カバレッジ（カバー率）を得るために、相互に類似する障害ユニットに対しては1度だけ検証を行なえば、他の障害ユニットについても検証したものとみなせるという考えの下、どのリンクを対象に障害試験を行なえば、最小の検証回数で最大の検証カバレッジを得られるかを算出する。すなわち、本発明では障害試験を行うリンク（障害個所）の組み合わせを導出することを考える。
【００２３】
そして、本発明ではネットワーク検証の最小単位ごとにトポロジの類似性を定量的に評価するための指標として前記障害ユニットという概念を導入した。そして、障害ユニットが類似するトポロジを検証の観点から類似と評価し、相互に類似する障害ユニットについては、その一つについて検証を行えば他の障害ユニットについても検証を行ったとみなし、「実施した検証回数」と「実施したとみなす検証回数（みなし検証回数）」との総和を最大化する障害個所を導出するようにしている。
【００２４】
図1は、本発明の一実施形態に係る検証最適化システムの主要部の構成を示した機能ブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。このようなシステムは、汎用のコンピュータやサーバに、後述する各機能を実現するアプリケーション（プログラム）を実装することで構成できる。あるいは、アプリケーションの一部がハードウェア化またはROM化された専用機や単能機とし構成しても良い。
【００２５】
検証最適化システム１において、経路探索部１０は、別途に与えられるネットワークトポロジに基づいて、当該ネットワークに接続するクライアントの組み合わせ（クライアントペアci，cj）ごとに最短の経路を計算する。
【００２６】
障害ユニット登録部２０は、クライアントペア（ci，cj）とその経路上の各一のリンクを障害発生リンクeと想定する障害ユニット(ci，cj，e)を登録する。したがって、経路長がnのクライアントペア（ci，cj）については、ｎ個の障害ユニット(ci，cj，e1），(ci，cj，e2）…(ci，cj，en）が登録されることになる。
【００２７】
類似度指標値計算部３０は、全ての障害ユニットに関して、リンクeに障害が発生した場合のネットワークトポロジの類似度指標値を計算する。本実施形態が検証対象とする商用ネットワークは、図２に示したように一般的には層型構造であり，階層ごとに同じような振る舞いやほぼ同等の装置を使用することが知られている。従って、階層が同じで、かつ障害発前後のパス長が同じであればほぼ同じような振る舞い等の経路を通るパスと判断できることから、本実施形態では類似度指標値として以下の３つが計算される。
【００２８】
q：障害発生前経路のパス長 
r：経路上のリンクeで障害が発生した後のパス長
k：経路上の障害発生リンクeのネットワーク階層
【００２９】
ここで、パス長qは前記クライアントペア（ci，cj）ごとに計算された最短経路のパス長である。パス長rは前記障害発生リンクeを考慮して再計算した前記クライアントペア（ci，cj）間の迂回経路である。
【００３０】
類似度評価部４０は、障害ユニット(ci，cj，e)ごとに計算された３つの類似度指標値q，r，kを、全ての障害ユニットペア間でそれぞれ比較する。そして、３つの類似度指標値q，r，kが全て一致する障害ユニット同士を類似（類似度=1）、一つでも異なる場合は非類似（類似度=0）と評価し、類似する障害ユニットは同一の障害ユニット集合に集約する。
【００３１】
最適化部５０は、同一の障害ユニット集合に集約された障害ユニット(ci，cj，e)については、いずれか一の障害ユニットのみに検証を実施すれば他の障害ユニットについては検証したものとみなして、限られた検証回数内で検証カバレッジすなわち「実施した検証回数」と「みなし検証回数」との総和が最大となる障害発生箇所（リンク）のセットを導出する。なお、限られた検証時間内に試験を完了させるため、検証回数Nを指定することもできる。
【００３２】
前記導出された障害発生箇所のセットは検証施行部２へ通知され、自動又は手動で当該各障害発生箇所に障害を発生させてクライアントペア間の疎通確認が実施される。
【００３３】
次いで、前記最適化部５０が障害発生箇所のセットを最適解としてコンピュータで演算する最適化問題としての定式化を考える。
【００３４】
ここでは、S個のスイッチV={v1、v2…vS}およびL個のリンクE={e1、e2、…、eL}で構成される階層kのネットワークを想定する。このようなネットワークは、リンクEおよびスイッチVで構成されるネットワークグラフG=(V、E)で、E⊆V×Vと表すことができる。
【００３５】
クライアント数をMとし、全てのクライアントはクライアント集合C={c1，c2，…cM}に属して各スイッチの配下に収容される。クライアントペアci，cj間の最短経路に属するリンクe∈Eの集合をPrimary(ci，cj)で表し、これを障害発生前経路とする。そして、Primary(ci，cj)に属する単一リンクe (e∈Primary(ci，cj))の障害により再計算される迂回経路に属するリンク集合をSecondary(ci，cj，e)とする。
【００３６】
例えば、図２のクライアントペアc1，c3間の障害発生前経路のリンク集合Primary(c1，c3)={17、11、5、1、7、15、19}であり、経路上のリンクe5に障害を発生させた場合、迂回経路のリンク集合はSecondary(c1、c3、e5)={17、13、6、4、8、16、19}となる。なお、障害発生前経路および迂回経路は、いずれも最短経路算出アルゴリズムDijkstra等を用いて算出できる。
【００３７】
ここで、あるリンクeの障害（障害リンクe）に対して、当該障害リンクeを障害発生前経路に含む任意のクライアントペアcx，cyに関する障害ユニット(cx，cy，e)と、任意のクライアントペアca，cbおよび任意の障害リンクezに関する障害ユニット(ca，cb，ez)との類似性Sim((cx，cy，e)、(ca，cb，ez))を、各障害ユニットの前記３つの類似度指標値q，r，kが全て一致すれば類似(=1)、一つでも不一致であれば非類似(=0)と評価する。したがって、２つの障害ユニット(cx，cy，e)，(ca，cb，ez)の類似性Simは次式(2)で表せる。
【００３８】
【数２】
2018137668.tif 000004
【００３９】
例えば、図２における２つの障害ユニット(c1，c3，e11)，(c2，c3，e12)は、共にq=7，r=7，k=3なので類似し、Sim((1、3、11)、(2、3、12))=1となる。本実施形態では、上式(2)の類似性Simを全ての障害ユニット間で計算する。
【００４０】
類似性の計算結果に基づき、リンクe障害における類似セット集合D(e)を導出する。D(e)は次式(3)で表すことができる。
【００４１】
【数３】
2018137668.tif 000005
【００４２】
一例として、図２におけるD(e)の導出結果を図４に示す。図４では、リンクe1障害に関しては２つの障害ユニット(1，3，1)，(2，3，1)が相互に類似し、リンクe5障害に関しては４つの障害ユニット(1，3，5)，(2，3，5)，(1，3，7)，(2，3，7)が相互に類似していることを表している。
【００４３】
さらに、リンクeの検証を実施するか否かを示すバイナリ関数down(e)を定義し、"1"は検証を実施、"0"は検証を実施しないと定義すると、リンクeの検証試験を実施する試行類似セットの集合Z(e)は次式(4)で表現できる。
【００４４】
【数４】
2018137668.tif 000006
【００４５】
ここで、検証回数をN以下とする制約条件は次式(5)で表せる。
【００４６】
【数５】
2018137668.tif 000007
【００４７】
上式(2)-(5)の制約条件のもと、「類似セット数の総和が最大」となる組み合わせについて、次式(6)を目的関数として算出する。
【００４８】
【数６】
2018137668.tif 000008
【００４９】
上式(2)-(6)は整数計算問題で表現されているため、汎用のソルバ(IBM ILOG CPLEX等のソフトウェア)によって最適解を計算することが可能である．
【００５０】
なお、本定式では、障害発生前後のパス長および障害発生リンクeの階層を基にした類似性を用いて説明したが、本発明は、類似性を異なる指標で分類・定義することで、他の類似性手法を適用することが可能である．
【００５１】
なお、上記の実施形態では、トポロジの類似度指標値として、害発生前経路のパス長q、経路上のリンクeで障害が発生した後のパス長rおよび経路上の障害発生リンクeのネットワーク階層kを採用するものとして説明したが、本発明はこれのみに限定されるものではなく、上記の類似度指標値に代えて、または上記の類似度指標値に加えて、リンク帯域、スイッチ接続次数、遅延、リンクの重要度などを採用しても良い。
【符号の説明】
【００５２】
１…検証最適化システム，２…検証施行部，１０…経路探索部，２０…障害ユニット登録部，３０…類似度指標値計算部，４０…類似度評価部，５０…最適化部
【図１】
2018137668.tif 000009
【図２】
2018137668.tif 000010
【図３】
2018137668.tif 000011
【図４】
2018137668.tif 000012