(57)【要約】      （修正有）【課題】データグラフ上でのパターングラフの出現を探索する部分グラフ同型判定問題を、より短時間で解くこと。【解決手段】通信ネットワーク設計装置１０は、通信ネットワークを構成するネットワークトポロジにおけるコンポーネントの出現を解析する。探索部１０４２は、ネットワークトポロジをデータグラフ、コンポーネントをパターングラフとみなし、データグラフ上におけるパターングラフの出現を探索する部分グラフ同型判定問題を解く。ラベル値付与部１０４１は、ネットワークトポロジ上における各ノードが取り得る属性を取得し、データグラフ上のノードに対して属性を示すラベル値を付与する。探索部１０４２は、ラベル値に基づいてパターングラフ中の特定のノードとなり得るノードをデータグラフから抽出してパターングラフの出現を探索する。【選択図】図２
2018042101.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークを構成するネットワークトポロジにおけるコンポーネントの出現を解析する通信ネットワーク解析装置であって、
前記ネットワークトポロジをデータグラフ、前記コンポーネントをパターングラフとみなし、前記データグラフ上における前記パターングラフの出現を探索する部分グラフ同型判定問題を解く探索部と、
前記ネットワークトポロジ上における各ノードが取り得る属性を取得し、前記データグラフ上のノードに対して前記属性を示すラベル値を付与するラベル値付与部と、を備え、
前記探索部は、前記ラベル値に基づいて前記パターングラフ中の特定のノードとなり得るノードを前記データグラフから抽出して前記パターングラフの出現を探索する、
ことを特徴とする通信ネットワーク解析装置。
【請求項２】
前記探索部により探索された出現を出現パターンとして登録する登録部を更に備え、
前記探索部は、複数のパターングラフに対してそれぞれ設定された優先度の低い順に出現の探索を行い、
前記登録部は、順次探索される出現を出現パターンとして登録するとともに、新たに登録する新規出現パターンが既に登録されている登録済み出現パターンを全て含む場合には前記登録済み出現パターンを削除して前記新規出現パターンを登録し、前記新規出現パターンが前記登録済み出現パターンの一部を含む場合には前記登録済み出現パターンを削除して前記新規出現パターンを登録した上で前記登録済み出現パターンと前記新規出現パターンとの差分を登録する、
ことを特徴とする請求項１に記載の通信ネットワーク解析装置。
【請求項３】
前記優先度は、トポロジ構成において上位集合となるパターングラフほど高く設定されている、
ことを特徴とする請求項２に記載の通信ネットワーク解析装置。
【請求項４】
通信ネットワークを構成するネットワークトポロジにおけるコンポーネントの出現を解析する通信ネットワーク解析方法であって、
前記ネットワークトポロジをデータグラフ、前記コンポーネントをパターングラフとみなし、前記ネットワークトポロジ上における各ノードが取り得る属性を取得し、前記データグラフ上のノードに対して前記属性を示すラベル値を付与するラベル値付与ステップと、
前記データグラフ上における前記パターングラフの出現を探索する部分グラフ同型判定問題を解く探索ステップと、を含み、
前記探索ステップでは、前記ラベル値に基づいて前記パターングラフ中の特定のノードとなり得るノードを前記データグラフから抽出して前記パターングラフの出現を探索する、
ことを特徴とする通信ネットワーク解析方法。
【請求項５】
前記探索ステップで探索された出現を出現パターンとして登録する登録ステップを更に含み、
前記探索ステップでは、複数のパターングラフに対してそれぞれ設定された優先度の低い順に出現の探索を行い、
前記登録ステップでは、順次探索される出現を出現パターンとして登録するとともに、新たに登録する新規出現パターンが既に登録されている登録済み出現パターンを全て含む場合には前記登録済み出現パターンを削除して前記新規出現パターンを登録し、前記新規出現パターンが前記登録済み出現パターンの一部を含む場合には前記登録済み出現パターンを削除して前記新規出現パターンを登録した上で前記登録済み出現パターンと前記新規出現パターンとの差分を登録する、
ことを特徴とする請求項４に記載の通信ネットワーク解析方法。
【請求項６】
前記優先度は、トポロジ構成において上位集合となるパターングラフほど高く設定されている、
ことを特徴とする請求項５に記載の通信ネットワーク解析方法。
【請求項７】
コンピュータに請求項４から６のいずれか１項に記載の通信ネットワーク解析方法を実行させるための通信ネットワーク解析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークを構成するネットワークトポロジにおけるコンポーネントの出現を解析する通信ネットワーク解析装置、通信ネットワーク解析方法および通信ネットワーク解析プログラムに関する。
【背景技術】
【０００２】
ネットワーク事業者においては、ネットワークを適切に設計することで、ネットワーク全体の資源を有効に利用し、転送品質の維持、ネットワークコストの低減を図ることが重要である。通常、ネットワークオペレータは、ノード間で発生する交流トラヒック流量を需要として必要資源量や各ノードの接続構成（トポロジ）を決定する。
一方で、ネットワークの運用フェーズに入ると、交流トラヒックは単調増加するだけでなく、設計当初に予測しなかったサービスの出現や予測誤りによって交流トラヒック構造が変化する場合がある。この場合、当初に設計したトポロジが必ずしも最適ではなくなるため、トポロジの構成変更が必要となる。
このため、変化した交流トラヒックに応じてネットワークトポロジをどのように構成変更するべきかを決定する技術が数多く検討されている（例えば、下記非特許文献１および非特許文献２）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】K. Shiomoto, W. Imajuku, S. Okamoto, N. Yamanaka, "Distributed virtual network topology control mechanism in GMPLS-based multiregion networks," in  IEEE Journal on Selected Areas in Communications (JSAC), Vol. 21(8), pp. 1254-1262, Oct. 2003.
【非特許文献２】Y. Koizumi, T. Miyamura, S. Arakawa, E. Oki, K. Shiomoto, and M. Murata, “Adaptive virtual network topology control based on attractor selection,” IEEE/OSA Journal of Lightwave Technology, vol. 28, pp. 1720-1731, June 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１および非特許文献２に記載の技術では、収容効率等の目的関数に基づいてネットワークを構成変更しており、構成変更に伴うオペレーション負荷への影響は考慮されていない。実際には、通信パスの再構成に伴って、上位レイヤ（例えばＩＰレイヤ）の設定変更やその設定変更に伴う通信正常性の検証が発生するため、ネットワーク事業者網の構成変更には膨大な作業が発生する。
【０００５】
このような作業負担を軽減するため、ネットワークトポロジが特定の構成要素（コンポーネント）の組合せで構成可能と仮定し、コンポーネント及びコンポーネント間の遷移オペレーションを定義することで、簡易な構成変更を実現する手法が検討されている。
この手法では、まず図１０（ｂ）に示すように、ネットワークトポロジを複数のコンポーネントに分割する。ここで、アルファベットＡ〜Ｚは地域を示すＩＤであり、地理的にトポロジが分割されていることを示す。
つぎに、図１０（ａ）に示すように、イベントの発生によるトラヒック構造の変化（例えばオリンピック特需など。図中符号Ａ）やトラヒックが単調増加した場合（図中符号Ｂ）など、ネットワークを再構成する必要があるイベントが発生すると、図１０（ｃ）に示すようにコンポーネント単位で各トラヒック変化に対応したコンポーネントに切り替える。すなわち、例えばイベントの発生によるトラヒック構造の変化に対応して、ＩＤ：Ｇ〜Ｉのコンポーネントをスター型からリング型に切り替える。また、トラヒックの単調増加に対応して、ＩＤ：Ｓ〜ＵおよびＶ〜Ｘのコンポーネントに含まれるリンクを多重化する。
このようなコンポーネント及びコンポーネント間の遷移オペレーションは、事前に定義しておき、ネットワークの構成変更を全て予測された規定のオペレーションとして行う。これにより、上記非特許文献に示すような任意の構成への変更という概念が無くなり、構成変更に伴うオペレーション稼働が削減されることが期待される。
【０００６】
ここで、ネットワークトポロジにおけるコンポーネントの出現確認問題は、コンポーネントをパターングラフ、ネットワークトポロジをデータグラフとみなし、データグラフ上でのパターングラフの出現を探索する部分グラフ同型判定問題とみなすことができる。
しかしながら、部分グラフ同型判定問題はＮＰ困難な問題に分類され、ネットワーク事業者網のような大規模なネットワークを対象としたとき、現実的な時間でコンポーネントへの分割ができないという課題がある。
【０００７】
本発明は、このような事情に鑑みてなされたものであり、データグラフ上でのパターングラフの出現を探索する部分グラフ同型判定問題を、より短時間で解くことを目的とする。
【課題を解決するための手段】
【０００８】
上述の目的を達成するため、請求項１に記載の発明は、通信ネットワークを構成するネットワークトポロジにおけるコンポーネントの出現を解析する通信ネットワーク解析装置であって、前記ネットワークトポロジをデータグラフ、前記コンポーネントをパターングラフとみなし、前記データグラフ上における前記パターングラフの出現を探索する部分グラフ同型判定問題を解く探索部と、前記ネットワークトポロジ上における各ノードが取り得る属性を取得し、前記データグラフ上のノードに対して前記属性を示すラベル値を付与するラベル値付与部と、を備え、前記探索部は、前記ラベル値に基づいて前記パターングラフ中の特定のノードとなり得るノードを前記データグラフから抽出して前記パターングラフの出現を探索する、ことを特徴とする通信ネットワーク解析装置とした。
【０００９】
また、請求項４に記載の発明は、通信ネットワークを構成するネットワークトポロジにおけるコンポーネントの出現を解析する通信ネットワーク解析方法であって、前記ネットワークトポロジをデータグラフ、前記コンポーネントをパターングラフとみなし、前記ネットワークトポロジ上における各ノードが取り得る属性を取得し、前記データグラフ上のノードに対して前記属性を示すラベル値を付与するラベル値付与ステップと、前記データグラフ上における前記パターングラフの出現を探索する部分グラフ同型判定問題を解く探索ステップと、を含み、前記探索ステップでは、前記ラベル値に基づいて前記パターングラフ中の特定のノードとなり得るノードを前記データグラフから抽出して前記パターングラフの出現を探索する、ことを特徴とする通信ネットワーク解析方法とした。
【００１０】
このように、ノードに付したラベル値を用いて探索範囲を絞り込むことによって、絞り込みを行わない場合比較して短時間にパターングラフの出現を探索することができ、通信ネットワークの規模が大きい場合などでも現実的な時間内での探索が可能となる。また、通信ネットワークのコンポーネントへの分割を行うことにより、コンポーネントの切り替えによるネットワークの簡易な構成変更が可能となり、通信事業者の運用コストを削減することができる。
【００１１】
また、請求項２に記載の発明は、前記探索部により探索された出現を出現パターンとして登録する登録部を更に備え、前記探索部は、複数のパターングラフに対してそれぞれ設定された優先度の低い順に出現の探索を行い、前記登録部は、順次探索される出現を出現パターンとして登録するとともに、新たに登録する新規出現パターンが既に登録されている登録済み出現パターンを全て含む場合には前記登録済み出現パターンを削除して前記新規出現パターンを登録し、前記新規出現パターンが前記登録済み出現パターンの一部を含む場合には前記登録済み出現パターンを削除して前記新規出現パターンを登録した上で前記登録済み出現パターンと前記新規出現パターンとの差分を登録する、ことを特徴とする通信ネットワーク解析装置とした。
【００１２】
また、請求項５に記載の発明は、前記探索ステップで探索された出現を出現パターンとして登録する登録ステップを更に含み、前記探索ステップでは、複数のパターングラフに対してそれぞれ設定された優先度の低い順に出現の探索を行い、前記登録ステップでは、順次探索される出現を出現パターンとして登録するとともに、新たに登録する新規出現パターンが既に登録されている登録済み出現パターンを全て含む場合には前記登録済み出現パターンを削除して前記新規出現パターンを登録し、前記新規出現パターンが前記登録済み出現パターンの一部を含む場合には前記登録済み出現パターンを削除して前記新規出現パターンを登録した上で前記登録済み出現パターンと前記新規出現パターンとの差分を登録する、ことを特徴とする通信ネットワーク解析方法とした。
【００１３】
このようにすることで、パターングラフの出現の探索結果を、優先度がより高いパターングラフの探索結果で上書きすることができ、通信ネットワークの実情に合わせて優先度を設定することにより探索の利便性を向上させることができる。
【００１４】
また、請求項３に記載の発明は、前記優先度が、トポロジ構成において上位集合となるパターングラフほど高く設定されている、ことを特徴とする通信ネットワーク解析装置とした。
【００１５】
また、請求項６に記載の発明は、前記優先度が、トポロジ構成において上位集合となるパターングラフほど高く設定されている、ことを特徴とする通信ネットワーク解析方法とした。
【００１６】
このようにすることで、トポロジ構成において上位集合となる大規模なネットワークを優先的に探索結果に含ませることができる。
【００１７】
また、請求項７に記載の発明は、コンピュータに通信ネットワーク解析方法を実行させるための通信ネットワーク解析プログラムとした。
【００１８】
このようにすることで、コンピュータに本発明にかかる通信ネットワーク解析方法を実行させることができる。
【発明の効果】
【００１９】
本発明によれば、データグラフ上でのパターングラフの出現を探索する部分グラフ同型判定問題を、より短時間で解くことができる。
【図面の簡単な説明】
【００２０】
【図１】実施の形態にかかる通信ネットワーク設計装置を含むネットワークＮＷの構成例を示す説明図である。
【図２】通信ネットワーク設計装置の機能的構成を示すブロック図である。
【図３】ネットワーク解析部の処理の概要を示す説明図である。
【図４】処理１の手順を示すフローチャートである。
【図５】処理２の手順を示すフローチャートである。
【図６】処理１の処理内容を模式的に示す説明図である。
【図７】処理２の処理内容を模式的に示す説明図である。
【図８】パターングラフの一例を示す説明図である。
【図９】出現集合を用いたネットワークの分割例を示す説明図である。
【図１０】コンポーネント分割によるネットワーク構成の最適化を模式的に示す説明図である。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態（以下、実施の形態とする）について説明する。
本実施の形態では、本発明にかかる通信ネットワーク解析装置を、通信ネットワーク設計装置１０の一機能として搭載した場合について説明する。
【００２２】
図１は、実施の形態にかかる通信ネットワーク設計装置１０を含むネットワークＮＷの構成例を示す説明図である。
図１に示すように、ネットワークＮＷは、端末装置２４同士が通信を行うための通信ネットワーク２０と、通信ネットワーク２０の構成情報や状態情報に基づき、ネットワーク構成を設計する通信ネットワーク設計装置１０と、通信ネットワーク２０のトラヒック発生状態を管理する通信ネットワーク運用装置１２とを含んで構成される。
【００２３】
通信ネットワーク２０は、端末装置２４から送信されたパケットを転送する複数のノード２２と、これらノード２２同士、および、ノード２２と端末装置２４を接続するリンクによって構成される。ノード２２は、例えば、汎用的なＩＰルータである。それぞれのノード２２は複数のインターフェース（ポート）を有しており、インターフェース毎に入出力トラヒック量を計測している。計測したトラヒック量の情報は、通信ネットワーク運用装置１２へと出力される。
この他、ネットワークＮＷには、通信ネットワーク２０のネットワーク構成情報を管理するオペレーション装置（図示なし）が設けられている。
【００２４】
図２は、通信ネットワーク設計装置１０の機能的構成を示すブロック図である。
なお、通信ネットワーク設計装置１０として、例えばＣＰＵ、ＲＯＭ、ＲＡＭ、ハードディスク装置、キーボード、マウス、ディスプレイ、入出力インターフェース、他装置インターフェース（通信ネットワーク運用装置１２やオペレーション装置とのインターフェース）等を備えた一般的なコンピュータを用いることができる。
通信ネットワーク設計装置１０は、上記ＣＰＵが上記ＲＯＭ等に記憶された交流トラヒック推定プログラムを実行することにより、経路設計部１０２およびネットワーク解析部１０４を実現する。また、通信ネットワーク設計装置１０のハードディスク装置またはＲＯＭには、網構成情報データベース（ＤＢ）１０６、パス・経路管理データベース１０８、トラヒック情報データベース１１０が記録されている。
【００２５】
経路設計部１０２は、後述する網構成情報データベース１０６に基づいて、通信ネットワーク２０における通信パスの経路を設計（計算）する。
ネットワーク解析部１０４は、本発明にかかる通信ネットワーク解析装置に対応し、通信ネットワーク２０のネットワークトポロジを複数のコンポーネントに分割し、その結果を網構成情報データベース１０６に格納する。ネットワーク解析部１０４は、更にラベル値付与部１０４１、探索部１０４２、登録部１０４３を備えている。ネットワーク解析部１０４の処理の詳細は後述する。
【００２６】
網構成情報データベース１０６は、トポロジ情報（ノードとリンクの接続関係）および各ノードやリンクが所属するコンポーネント情報を管理する。トポロジ情報は、通信ネットワーク運用装置１２経由で取得するか、またはオペレータから入力される。また、コンポーネント情報は、ネットワーク解析部１０４によって探索された結果を記録する。
パス・経路管理データベース１０８は、各ノード間で設定される通信パスやその経路情報を管理する。パス・経路管理データベース１０８内の情報は、経路設計部１０２で計算するか、またはオペレータから入力される。
トラヒック情報データベース１１０は、リンクごとのトラヒック情報やノード間の交流トラヒック情報を管理する。トラヒック情報データベース１１０内の情報は、通信ネットワーク運用装置１２から取得する。
【００２７】
つぎに、ネットワーク解析部１０４の処理について説明する。
図３は、ネットワーク解析部１０４の処理の概要を示す説明図である。
ネットワーク解析部１０４は、通信ネットワーク２０を構成するネットワークトポロジにおけるコンポーネント（特定の構成要素）の出現を解析する。具体的には、ネットワーク解析部１０４は、探索部１０４２（図２参照）において、ネットワークトポロジをデータグラフ、コンポーネントをパターングラフとみなし、データグラフ上におけるパターングラフの出現を探索する部分グラフ同型判定問題を解く。
【００２８】
すなわち、図３（ａ）に示すように、ネットワーク解析部１０４は、入力として通信ネットワーク２０のネットワークトポロジに対応するデータグラフ、および所定のコンポーネントを示すパターングラフ（図３（ａ）の例ではパターン１およびパターン２）を受けると、データグラフ上における各パターングラフの出現を探索し、その結果を出力する。
【００２９】
具体的な演算としては、図３（ｂ）に示すように、データグラフはＧｄ＝（Ｖｄ，Ｅｄ，ｌａｂｅｌ）、パターングラフは個々のパターングラフを要素とする集合Ｇ＝（Ｇ１，Ｇ２，・・・，ＧＬ）として示される。そして、これらの入力値に対して後述する処理１および処理２を実行することにより、データグラフＧｄにおける各パターングラフＧｌの出現を示す出現集合Ｓ（Ｇｌ，Ｇｄ），ｌ＝（１，２，・・・，Ｌ）を出力する。ここで、処理１は、複数のパターングラフに対して繰り返しコンポーネントの出現を確認するコンポーネント分析法の骨子となるアルゴリズムであり、処理２は、出現の確認を高速化するアルゴリズムである。
【００３０】
図４は、処理１の手順を示すフローチャートである。
処理１における入力情報は、パターングラフを要素とする集合Ｇ＝（Ｇ１，Ｇ２，・・・，ＧＬ）、各パターングラフの優先度Ｗｌ（ｌ＝１，２，・・・，Ｌ）、データグラフＧｄ＝（Ｖｄ，Ｅｄ，ｌａｂｅｌ）である。ここで、Ｖｄはノードの集合、Ｅｄはリンクの集合、ｌａｂｅｌはノードの属性を示すラベル値である。パターングラフ集合Ｇの各要素Ｇｉも同様に、ノードの集合とリンクの集合を持つ。
【００３１】
パターングラフの一例を図８上段に示す。図８には２−チェーン型グラフ、３−チェーン型グラフ、３−リング型グラフ、４−リング型グラフ、１−ランクスター型グラフ、２−ランクスター型グラフが示されている。本実施の形態では、トポロジ構成においてより上位集合となるパターングラフほど優先度を高くしている。すなわち、図８の例では、優先度が最も低いパターングラフは２−チェーン型グラフであり、優先度が最も高いパターングラフは２−ランクスター型グラフとなる。なお、パターングラフに対する優先度の決定方法は上記に限らず、各パターングラフに対する優先度を任意に指定できるようにしてもよい。図８下段については、後記する。
【００３２】
また、ラベル値とは、ラベル値付与部１０４１（図２参照）において、実際の通信ネットワーク（実網）における条件に基づいてデータグラフＧｄ上の各ノードに付与するものであり、所定のパターングラフにおいて特定の属性のノードとなり得るノードを絞り込むために付与される。例えば、スター型グラフの根（ｒｏｏｔ）となり得るノードは、事業条件から既知であるので、対応するノードにｒｏｏｔを示すラベル値を付与する。すなわち、ラベル値付与部１０４１は、処理１に先立って、ネットワークトポロジ上における各ノードが取り得る属性を取得し、データグラフ上のノードに対して属性を示すラベル値を付与する。
【００３３】
また、パターングラフＧｌのデータグラフＧｄへの出現集合（Ｏｃｃｕｒｒｅｎｃｅ  Ｓｅｔ）をＳ（Ｇｌ，Ｇｄ）とし、その数を｜Ｓ（Ｇｌ，Ｇｄ）｜とする。処理１における出力情報は、全てのパターングラフＧｌの出現集合である全体出現集合Ｓ（Ｇｌ，Ｇｄ），ｌ＝（１，２，・・・，Ｌ）である。
【００３４】
図４のフローチャートにおいて、ネットワーク解析部１０４の探索部１０４２は、まずパターングラフ集合Ｇの要素を、優先度Ｗｌの小さい順にソートする（ステップＳ４００）。
つぎに、優先度の低いパターングラフから順に、処理対象とするパターングラフＧｌを選択し（ステップＳ４０２）、図５に示す処理２を用いてパターングラフＧｌのデータグラフＧｄに対する部分グラフ同型判定問題を解き、その結果である出現集合Ｓｌ（Ｇｌ，Ｇｄ）＝｛Ｓｌ１，Ｓｌ２，・・・，Ｓｌｋ｝を算出する（ステップＳ４０４）。
【００３５】
続いて、ネットワーク解析部１０４の登録部１０４３は、探索部１０４２により探索された出現（出現集合）を出現パターンとして全体出現集合Ｓ（Ｇｌ，Ｇｄ）に登録する（ステップＳ４０６〜Ｓ４１６）。以下、今回の登録対象である新規集合をＳｔｍｐ（Ｇｌ，Ｇｄ）＝｛Ｓｌ１，Ｓｌ２，・・・，Ｓｌｋ｝とし、Ｓｌｉは新規集合Ｓｔｍｐ（Ｇｌ，Ｇｄ）の要素であり（Ｓｌｉ∈Ｓｔｍｐ（Ｇｌ，Ｇｄ））、Ｓｍｊは既に登録されている登録済み集合Ｓ（Ｇｍ，Ｇｄ）（ｍ＝１，２，・・・，ｌ−１）の要素である（Ｓｍｊ∈Ｓ（Ｇｍ，Ｇｄ），ｍ＝１，２，・・・，ｌ−１）ものとする。
【００３６】
ここで、処理１における重複回避条件を定義する。パターングラフＧｉ，Ｇｊ（ｉ≠ｊ）において、ＧｉがＧｊの部分集合であるとき（Ｇｉ⊆Ｇｊ）は、ＧｉはＳ（Ｇｉ，Ｇｊ）に含まないものとする。すなわち、登録部１０４３は、新規集合がこれまでに登録された登録済み集合のサブセットになっていなければ全体出現集合Ｓ（Ｇｌ，Ｇｄ）に登録する。
【００３７】
具体的には、新規集合の要素である新規パターン（新規出現パターン）と、登録済み集合の要素である登録済みパターン（登録済み出現パターン）とに重複がない場合には（ステップＳ４０６：Ｙｅｓ）、そのまま新規パターンを登録する（ステップＳ４０８）。すなわち、ＳｌｉがＳｍｊの部分集合ではない場合は、ＳｌｉをＳ（Ｇｌ，Ｇｄ）に登録する。
例えば、図６（ａ）に示すように、データグラフがノードａ，ｂ，ｃ，ｄで構成される場合、登録済みパターンがノードａ，ｂ，ｃを含む３−リング型グラフであり、新規パターンがノードｃ，ｄを含む２−チェーン型グラフである場合、新規パターンと登録済みパターンに重複する部分はないため、そのまま新規パターンを登録する。
【００３８】
また、新規パターンと登録済みパターンとに重複がある場合で（ステップＳ４０６：Ｎｏ）、新規パターンが登録済みパターンの要素を全て含む場合（ステップＳ４１０：Ｙｅｓ）、つまり新規パターンの部分集合が登録済みパターンになっている場合には、登録済みパターンを削除して新規パターンを登録する（ステップＳ４１２）。すなわち、ａがＳｍｊの要素であり（ａ⊂Ｓｍｊ）、かつａがＳｌｉの要素である（ａ⊂Ｓｌｉ）場合は、ＳｍｊをＳ（Ｇｍ，Ｇｄ）から削除し、ＳｌｉをＳ（Ｇｌ，Ｇｄ）に登録する。
例えば、図６（ｂ）に示すように、登録済みパターンがノードａ，ｂ，ｃを含む３−リング型グラフであり、新規パターンがノードａ，ｂ，ｃ，ｄを全て含むグラフである場合、登録済みパターンを削除し、新規パターンを登録する。
【００３９】
また、新規パターンと登録済みパターンとに重複がある場合で（ステップＳ４０６：Ｎｏ）、新規パターンが登録済みパターンの要素の全ては含んでいない場合（ステップＳ４１０：Ｎｏ）、つまり新規パターンの部分集合が登録済みパターンの部分集合になっている場合には、登録済みパターンを削除して新規パターンを登録するとともに（ステップＳ４１４）、登録済みパターンと新規パターンの差分に一致するパターンを登録する（ステップＳ４１６）。すなわち、ａがｂの要素であり（ａ⊂ｂ）、ａがＳｌｉの要素であり（ａ⊂Ｓｌｉ）、ｂがＳｍｊの要素（ｂ⊂Ｓｍｊ）である場合、ＳｍｊをＳ（Ｇｍ，Ｇｄ）から削除し、ＳｌｉをＳ（Ｇｌ，Ｇｄ）に登録するとともに。ｂ／ａ（ｂからａに属する要素を除いた差集合）に一致するパターングラフｍをＳ（Ｇｌ，Ｇｄ）に登録する。
例えば、図６（ｃ）に示すように、登録済みパターンがノードａ，ｂ，ｃを含む３−リング型グラフであり、新規パターンがノードｃをｒооｔとし、ノードａ，ｂ，ｄを結ぶ１−ランクスター型グラフである場合、登録済みパターンを削除し、新規パターンを登録するとともに、差分パターンであるノードａとｂを含む２−チェーン型グラフを登録する。
【００４０】
すなわち、探索部１０４２は、複数のパターングラフに対してそれぞれ設定された優先度の低い順に出現の探索を行い、登録部１０４３は、順次探索される出現を出現パターンとして登録するとともに、新たに登録する新規パターン（新規出現パターン）が既に登録されている登録済みパターン（登録済み出現パターン）を全て含む場合には登録済みパターンを削除して新規パターンを登録し、新規パターンが登録済みパターンの一部を含む場合には登録済みパターンを削除して新規パターンを登録した上で登録済みパターンと新規パターンとの差分を登録する。
【００４１】
このような処理を、パターングラフ集合Ｇの全てのパターングラフを対象に順次くり返し（ステップＳ４１８：Ｎｏのループ）、パターングラフ集合Ｇの全てのパターングラフに対する処理が終了すると（ステップＳ４１８：Ｙｅｓ）、全体出現集合Ｓ（Ｇｌ，Ｇｄ），ｌ＝（１，２，・・・，Ｌ）を出力して（ステップＳ４２０）、本フローチャートの処理を終了する。
【００４２】
図５は、処理２の手順を示すフローチャートである。
処理２における入力情報は、１つのパターングラフＧｌ＝（Ｖｌ，Ｅｌ）およびデータグラフＧｄ＝（Ｖｄ，Ｅｄ，ｌａｂｅｌ）である。また、処理２における出力情報は、パターングラフＧｌの出現集合Ｓｌ（Ｇｌ，Ｇｄ）＝｛Ｓｌ１，Ｓｌ２，・・・，Ｓｌｋ｝である。
処理２の基本的な考え方は、パターングラフの形やラベル値に基づいて探索を簡易化したり、探索範囲を限定したりすることにより、短時間にパターングラフの出現を探索することにある。すなわち、探索部１０４２は、ノードに付されたラベル値に基づいてパターングラフ中の特定のノードとなり得るノードをデータグラフから抽出してパターングラフの出現を探索する。
【００４３】
図５のフローチャートにおいて、ネットワーク解析部１０４の探索部１０４２は、今回の処理対象のパターングラフＧｌが、２−チェーン型グラフの場合（ステップＳ５００：Ｙｅｓ）、またはスター型グラフの場合（ステップＳ５０４：Ｙｅｓ）、またはこれ以外のグラフの場合（ステップＳ５０４：Ｎｏ）でそれぞれ異なる処理を行う。なお、図５のフローチャートの順番は便宜的なものであり、この順に処理を行う必要はない。
【００４４】
まず、処理対象のパターングラフＧｌが２-チェーン型グラフの場合（ステップＳ５００：Ｙｅｓ）、探索部１０４２は、データグラフＧｄ上のリンク（ｉ，ｊ）（（ｉ，ｊ）∈Ｅｄ））及びノードｉ，ｊ（ｉ，ｊ∈Ｖｄ）を２-チェーン型グラフとして、出現集合Ｓｌ（Ｇｌ，Ｇｄ）に登録し（ステップＳ５０２）、出現集合Ｓｌ（Ｇｌ，Ｇｄ）を出力して（ステップＳ５１４）、本フローチャートによる処理を終了する。
【００４５】
つぎに、処理対象のパターングラフＧｌがスター型グラフである場合（ステップＳ５０４：Ｙｅｓ）、探索部１０４２は、ルース検索モードが有効であるか否かを判断する（ステップＳ５０６）。ルース検索モードは事前に指定するオプションであり、このオプションが有効である場合は、ラベル値がｒｏｏｔであるノードに接続するリンクは、パターングラフＧｌの形に依存せずに全て出現集合に登録する。また、このオプションが無効である場合は、パターングラフＧｌと完全一致した場合に出現集合に登録する。
すなわち、ルース検索モードが有効である場合には（ステップＳ５０６：Ｙｅｓ）、データグラフＧｄにおけるラベル値がrootであるノードをｒ（ｒ∈Ｖｄ）とし、ノードｒに接続するリンク（ｒ，ｉ）およびこのリンクに接続するノードｉ（（ｒ，ｉ）∈Ｅｄ、ｉ∈Ｖｄ）を全て該当パターングラフとして出現集合Ｓｌ（Ｇｌ，Ｇｄ）に登録し（ステップＳ５０８）、出現集合Ｓｌ（Ｇｌ，Ｇｄ）を出力して（ステップＳ５１４）、本フローチャートによる処理を終了する。
【００４６】
また、ルース検索モードが有効でない場合（ステップＳ５０６：Ｎｏ）、処理対象のパターングラフＧｌの根をＧｄにおけるラベル値がｒｏｏｔであるノードｒ（ｒ∈Ｖｄ）に写像した上で探索木を作成する。そして、探索木に対してＵｌｌｍａｎｎアルゴリズムによりパターングラフを探索し、パターングラフが発見された場合には出現集合Ｓｌ（Ｇｌ，Ｇｄ）に登録する（ステップＳ５１０）。その後、出現集合Ｓｌ（Ｇｌ，Ｇｄ）を出力して（ステップＳ５１４）、本フローチャートによる処理を終了する。
【００４７】
つぎに、処理対象のパターングラフＧｌが、２−チェーン型グラフおよびスター型グラフ以外のグラフである場合（ステップＳ５０４：Ｎｏ）、探索部１０４２は、パターングラフＧｌとデータグラフＧｄから、パターン数ＶｄＰＶｌ個の探索木を作成する（Ｏｒｉｇｉｎａｌ  Ｓｅａｒｃｈ）。つぎに、探索木に対してＵｌｌｍａｎｎアルゴリズムによりパターングラフを探索し、パターングラフが発見された場合には出現集合Ｓｌ（Ｇｌ，Ｇｄ）に登録する（ステップＳ５１２）。そして、出現集合Ｓｌ（Ｇｌ，Ｇｄ）を出力して（ステップＳ５１４）、本フローチャートによる処理を終了する。
【００４８】
ステップＳ５１０およびＳ５１２の処理の概要を図７に示す。なお、簡単のため探索対象のグラフを１−ランクスター型グラフとして説明する。
ステップＳ５１０では、図７（ａ）に示すように、例えばノードａ〜ｊを含むデータグラフにおいて、ノードａにｒｏｏｔノードであることを示すラベル値が付与されているものとする。処理対象のパターングラフは、ノードＡ〜Ｄで構成される１−ランクスター型グラフである。このパターングラフにおけるｒｏｏｔノードはノードＡであり、データグラフにおいてノードＡとなり得るのはノードａのみとなる。よって、探索範囲は図７（ｂ）の左側に示すように、ノードａと接続する６つのノードｂ，ｃ，ｄ，ｅ，ｆ，ｇから３つを選択する順列６Ｐ３＝１２０となる。
【００４９】
一方、ステップＳ５１２では、従来のようにノードの属性による絞り込みを行わないため、データグラフ上の全てのノードがパターングラフのノードＡの候補となり、これに対応させた探索木が作成される。すなわち、ノードａ〜ｊの１０個のノードから１−ランクスター型グラフを構成する４つのノードを選択するため、探索範囲は順列１０Ｐ４＝５０４０と、絞り込みを行った場合の４２倍となる。
【００５０】
このようにノードの属性による絞り込みを行わない場合、パターングラフの大きさ次第で計算時間が膨大となる。例えば、図９（ａ）に示すデータグラフ上で、６ノードからなる１−ランクスター型グラフを探索する場合は約９００秒を要する。さらにノードを１つ増加させ、７ノードからなる１−ランクスター型グラフを探索する場合には約３６０００秒と、６ノードの場合と比較して約４０倍の時間を要する。
本実施の形態のように、ラベル値を用いて探索範囲を絞り込むことによって、従来の方法と比較して短時間に探索を行うことができ、現実的な時間内での探索が可能となる。
なお、ステップＳ５１０およびＳ５１２におけるＵｌｌｍａｎｎアルゴリズムの詳細は、下記参考文献１に記載されている。
（参考文献１）J. R. Ullmann: An Algorithm for Subgraph Isomorphism, Journal of the Association for Computing Machinery, Vol. 23, No. 1, pp. 31-42, 1976.
【００５１】
図９は、出現集合を用いたネットワークの分割例を示す説明図である。
図９（ｂ）、（ｃ）は、図９（ａ）に示すデータグラフを異なる探索パターンで探索した結果を示している。なお、図９（ａ）にはラベル値がｒｏｏｔであるルートノードを他のノードと識別可能に図示している。
図９（ｂ）に結果を示す探索パターン１（図８下段参照）は、２−チェーン型グラフ、３−チェーン型グラフ、３−リング型グラフ、４−リング型グラフおよび１−ランクスター型グラフで分割した場合である。
図９（ｃ）に結果を示す探索パターン２（図８下段参照）は、２−チェーン型グラフ、３−チェーン型グラフ、３−リング型グラフ、４−リング型グラフおよび２−ランクスター型グラフで分割した場合である。
このように、本願発明によれば、パターングラフ（コンポーネント）の種類を指定したネットワークの分割を容易に実行することができる。
【００５２】
以上説明したように、実施の形態にかかる通信ネットワーク設計装置１０によれば、ノードに付したラベル値を用いて探索範囲を絞り込むことによって、絞り込みを行わない場合と比較して短時間にパターングラフの出現を探索することができ、通信ネットワークの規模が大きい場合などでも現実的な時間内での探索が可能となる。また、通信ネットワークのコンポーネントへの分割を行うことにより、コンポーネントの切り替えによるネットワークの簡易な構成変更が可能となり、通信事業者の運用コストを削減することができる。
また、パターングラフの出現の探索結果を、優先度がより高いパターングラフの探索結果で上書きするので、通信ネットワークの実情に合わせて優先度を設定することにより探索の利便性を向上させることができる。
【符号の説明】
【００５３】
ＮＷ  ネットワーク
１０  通信ネットワーク設計装置
１０２  経路設計部
１０４  ネットワーク解析部
１０４１  ラベル値付与部
１０４２  探索部
１０４３  登録部
１０６  網構成情報データベース
１０８  パス・経路管理データベース
１１０  トラヒック情報データベース
１２  通信ネットワーク運用装置
２０  通信ネットワーク
２２  ノード
２４  端末装置
【図１】
2018042101.tif 000003
【図２】
2018042101.tif 000004
【図３】
2018042101.tif 000005
【図４】
2018042101.tif 000006
【図５】
2018042101.tif 000007
【図６】
2018042101.tif 000008
【図７】
2018042101.tif 000009
【図８】
2018042101.tif 000010
【図９】
2018042101.tif 000011
【図１０】
2018042101.tif 000012