(57)【要約】【課題】高精度な経路障害シミュレーションを実現する技術を提供することを目的とする。【解決手段】障害伝搬シミュレータ１は、複数のＡＳのＢＧＰルータからＢＧＰアップデートメッセージを取得するＢＧＰアップデートメッセージ取得部１０と、ＢＧＰアップデートメッセージ取得部１０によって取得されたＢＧＰアップデートメッセージに基づいて、各ＡＳの優先関係を推定する優先関係推定部２０と、優先関係推定部２０によって推定されたＡＳの優先関係に基づいて各ＢＧＰルータのルータＩＤを決定するルータＩＤ割当部３０とを備える。【選択図】図１
2010178172.tif 000002
【特許請求の範囲】
【請求項１】
複数のＡＳのＢＧＰルータからＢＧＰアップデートメッセージを取得するＢＧＰアップデートメッセージ取得部と、
前記ＢＧＰアップデートメッセージ取得部によって取得されたＢＧＰアップデートメッセージに基づいて、各ＡＳの優先関係を推定する優先関係推定部と
を備えることを特徴とする優先関係推定装置。
【請求項２】
前記優先関係推定部は、
前記ＢＧＰアップデートメッセージ取得部によって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報および時刻情報に基づいて、ＡＳパス毎の利用時間を集計する利用時間集計部と、
前記ＢＧＰアップデートメッセージ取得部によって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報に基づいて、同一の始点および終点のＡＳを有し同一のパス長であるＡＳパスの組であってパス内のＡＳの１つが相違するＡＳパスの組を抽出し、前記ＡＳパスの組内の各ＡＳパスから前記相違するＡＳの組を抽出する抽出部と、
前記抽出部によって抽出された前記ＡＳパスの組内の各ＡＳパスについて前記利用時間集計部によって集計された前記利用時間の長短に基づいて、当該ＡＳパスの組内の各ＡＳパスから抽出された前記ＡＳの組内の両ＡＳの前記優先関係を決定する個別優先関係決定部と
を備えることを特徴とする請求項１に記載の優先関係推定装置。
【請求項３】
前記優先関係推定部は、更に、
前記個別優先関係決定部によって決定された前記優先関係にあるＡＳの組が抽出された抽出回数を、前記優先関係毎に集計する抽出回数集計部と、
前記個別優先関係決定部によって決定された前記優先関係にある各ＡＳの抽出元である各ＡＳパスについて前記利用時間集計部によって集計された利用時間を、前記優先関係毎に合算する利用時間合算部と、
前記抽出回数集計部によって集計された前記優先関係毎の抽出回数、および、前記利用時間合算部によって合算された前記優先関係毎の利用時間に基づいて、前記抽出部によって抽出された複数のＡＳの組内の全ＡＳの前記優先関係を決定する全体優先関係決定部と
を備えることを特徴とする請求項２に記載の優先関係推定装置。
【請求項４】
通信ネットワークシステム内を構成する複数のＡＳの各ＢＧＰルータのルータＩＤを推定し、当該通信ネットワークシステム内における障害伝搬をシミュレートする障害伝搬シミュレータであって、
複数のＡＳのＢＧＰルータからＢＧＰアップデートメッセージを取得するＢＧＰアップデートメッセージ取得部と、
前記ＢＧＰアップデートメッセージ取得部によって取得されたＢＧＰアップデートメッセージに基づいて、各ＡＳの優先関係を推定する優先関係推定部と、
前記優先関係推定部によって推定されたＡＳの前記優先関係に基づいて前記各ＢＧＰルータのルータＩＤを決定するルータＩＤ割当部と
を備えることを特徴とする障害伝搬シミュレータ。
【請求項５】
前記優先関係推定部は、
前記ＢＧＰアップデートメッセージ取得部によって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報および時刻情報に基づいて、ＡＳパス毎の利用時間を集計する利用時間集計部と、
前記ＢＧＰアップデートメッセージ取得部によって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報に基づいて、同一の始点および終点のＡＳを有し同一のパス長であるＡＳパスの組であってパス内のＡＳの１つが相違するＡＳパスの組を抽出し、前記ＡＳパスの組内の各ＡＳパスから前記相違するＡＳの組を抽出する抽出部と、
前記抽出部によって抽出された前記ＡＳパスの組内の各ＡＳパスについて前記利用時間集計部によって集計された前記利用時間の長短に基づいて、当該ＡＳパスの組内の各ＡＳパスから抽出された前記ＡＳの組内の両ＡＳの前記優先関係を決定する個別優先関係決定部と、
前記個別優先関係決定部によって決定された前記優先関係にあるＡＳの組が抽出された抽出回数を、前記優先関係毎に集計する抽出回数集計部と、
前記個別優先関係決定部によって決定された前記優先関係にある各ＡＳの抽出元である各ＡＳパスについて前記利用時間集計部によって集計された利用時間を、前記優先関係毎に合算する利用時間合算部と、
前記抽出回数集計部によって集計された前記優先関係毎の抽出回数、および、前記利用時間合算部によって合算された前記優先関係毎の利用時間に基づいて、前記抽出部によって抽出された複数のＡＳの組内の全ＡＳの前記優先関係を決定する全体優先関係決定部と
を備えることを特徴とする請求項４に記載の障害伝搬シミュレータ。
【請求項６】
通信ネットワークシステム内を構成する複数のＡＳの各ＢＧＰルータのルータＩＤを推定し、当該通信ネットワークシステム内における障害伝搬をシミュレートする障害伝搬シミュレータのコンピュータに、
複数のＡＳのＢＧＰルータからＢＧＰアップデートメッセージを取得するＢＧＰアップデートメッセージ取得ステップと、
前記ＢＧＰアップデートメッセージ取得ステップによって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報および時刻情報に基づいて、ＡＳパス毎の利用時間を集計する利用時間集計ステップと、
前記ＢＧＰアップデートメッセージ取得ステップによって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報に基づいて、同一の始点および終点のＡＳを有し同一のパス長であるＡＳパスの組であってパス内のＡＳの１つが相違するＡＳパスの組を抽出し、前記ＡＳパスの組内の各ＡＳパスから前記相違するＡＳの組を抽出する抽出ステップと、
前記抽出ステップによって抽出された前記ＡＳパスの組内の各ＡＳパスについて前記利用時間集計ステップによって集計された前記利用時間の長短に基づいて、当該ＡＳパスの組内の各ＡＳパスから抽出された前記ＡＳの組内の両ＡＳの前記優先関係を決定する個別優先関係決定ステップと、
前記個別優先関係決定ステップによって決定された前記優先関係にあるＡＳの組が抽出された抽出回数を、前記優先関係毎に集計する抽出回数集計ステップと、
前記個別優先関係決定ステップによって決定された前記優先関係にある各ＡＳの抽出元である各ＡＳパスについて前記利用時間集計ステップによって集計された利用時間を、前記優先関係毎に合算する利用時間合算ステップと、
前記抽出回数集計ステップによって集計された前記優先関係毎の抽出回数、および、前記利用時間合算ステップによって合算された前記優先関係毎の利用時間に基づいて、前記抽出ステップによって抽出された複数のＡＳの組内の全ＡＳの前記優先関係を決定する全体優先関係決定ステップと、
前記優先関係決定ステップによって決定されたＡＳの前記優先関係に基づいて前記各ＢＧＰルータのルータＩＤを決定するルータＩＤ割当ステップと
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、優先関係推定装置、障害伝搬シミュレータおよびプログラムに関する。
【背景技術】
【０００２】
多数のＡＳ（Autonomous System）が相互接続されて構成されるインターネットにおいては、機器（例えば、ルータ）の故障、経路情報の設定ミス、不正な経路制御などにより経路障害が発生する。局所にて発生した経路障害は、ＢＧＰ経路更新メッセージ（「ＢＧＰアップデートメッセージ」とも称する）により伝播され、やがて広範囲において、通信品質劣化やインターネット到達性低下（通信品質劣化等）などを招来させる遅延、遅延ゆらぎ（ジッタ）、パケットロスが発生する場合がある。
【０００３】
通信品質劣化等は、多大な損害を与える危険性があるため、リスク管理の観点から損害の規模を見積ることが重要となる。損害の規模は、経路障害発生後において通信品質劣化等が生じた範囲と関係することから、損害の規模を見積るためには、経路障害発生時に通信品質劣化等が生じる範囲の拡大を予測する必要がある。そのため、経路障害の伝搬をシミュレーションする技術が研究されている。
【０００４】
経路障害の伝搬を高精度にシミュレーションするためには、以下の２つのステップが必要になる。
ステップ１：各ＡＳのＢＧＰ経路制御ポリシー（各ＡＳが複数の経路候補の中から最適経路を選択し、他のＡＳに広報するかというポリシー。以下、単に「経路制御ポリシー」という）を推定するステップ。
ステップ２：推定した各ＡＳの経路制御ポリシーを障害シミュレーションに適用するステップ。
【０００５】
ステップ１に関して、ＡＳトポロジーに基づいてＡＳ間のピアリング関係を推定し、ピアリング関係の特徴に応じて各ＡＳの経路制御ポリシーを推定する手法が提案されている。具体的には、図８に示すように、ＡＳトポロジーに基づいて、ＡＳ間のピアリング関係を“ｐｒｏｖｉｄｅｒ−ｃｕｓｔｏｍｅｒ”，“ｐｅｅｒ−ｔｏ−ｐｅｅｒ”に分類し、分類したピアリング関係の特徴に応じて各ＡＳの経路制御ポリシーを推定する。即ち、例えば、ＡＳはｐｒｏｖｉｄｅｒＡＳに対し、自ＡＳとｃｌｉｅｎｔＡＳの経路を広報するが、他のｐｒｏｖｉｄｅｒＡＳから学習した経路は広報しないというような一般的な経路制御ポリシーを推定する。また、ステップ１に関して、インターネット全体のＢＧＰ経路制御情報のデータベース（例えば、Ｉｎｔｅｒｎｅｔ  Ｒｏｕｔｉｎｇ  Ｒｅｇｉｓｔｒｙ）を用いて、各ＡＳの経路制御ポリシーを推定する手法も存在する。
【０００６】
ステップ２に関しては、経路障害の伝搬をシミュレーションするシミュレータ（以下、単に「シミュレータ」という）上で動作させる各ＢＧＰルータの設定ファイルに、各ＡＳの経路制御ポリシーを記述する方法、例えば、ＢＧＰの最適経路計算に使用されるＬｏｃａｌ  ＰｒｅｆｅｒｅｎｃｅやＭＥＤ値、フィルタ設定を詳細に記述する方法が考えられる。なお、非特許文献１には、ＡＳのトポロジーにおける階層化について開示されている。非特許文献２には、経路制御ポリシーについて開示されている。非特許文献３には、ＢＧＰ経路制御情報のデータベースについて開示されている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】F.Wang and L.Gao.“Inferring and Characterizing Internet Routing Policies,”in Proc.ACM SIGCOMM Internet Measurement Conference. 2003.
【非特許文献２】Lakshminarayanan Subramanian, Sharad Agarwal, Jennifer Rexford, and Randy H. Katz.“Characterizing the Internet hierarchy from multiple vantage points,” in Proc. IEEE INFOCOM, June 2002.
【非特許文献３】IRRd、［online］、［平成２１年１月７日検索］、インターネット＜URL：http://www.irrd.net/＞.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来技術を用いて経路障害の伝搬をシミュレーションする場合、以下の問題がある。まず、上述のステップ１に係るピアリング関係の特徴に応じて各ＡＳの経路制御ポリシーを推定する手法では、ピアリング関係の推定、および、ピアリング関係の特徴に応じた経路制御ポリシーの推定の両推定において、推定誤差が発生するという問題がある。また、最適経路に関する経路制御ポリシーの推定は可能であるものの、バックアップ経路に関する経路制御ポリシーの推定は困難であるという問題がある。また、ステップ１に係る経路制御情報のデータベースを用いて各ＡＳの経路制御ポリシーを推定する手法では、データベース内の経路制御ポリシーが最新状態でない場合や、情報が不十分である可能性があるという問題がある。
【０００９】
また、ステップ２においても、ステップ１において推定した各ＡＳの経路制御ポリシーが不完全であるため（あくまで推定結果やポリシー情報の一部であるため）、全ＢＧＰルータの設定ファイルを記述できないという問題がある。また、不完全な経路制御ポリシーをシミュレーションに適用した場合、各ＡＳの経路制御ポリシーに不整合が生じ、結果的に、経路障害の伝搬を高精度にシミュレーションできないという問題がある。
【００１０】
本発明は、上述した課題に鑑みてなされたものであって、経路障害の伝搬を高精度にシミュレーションするための技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記問題を解決するために、本発明の一態様である優先関係推定装置は、複数のＡＳのＢＧＰルータからＢＧＰアップデートメッセージを取得するＢＧＰアップデートメッセージ取得部と、ＢＧＰアップデートメッセージ取得部によって取得されたＢＧＰアップデートメッセージに基づいて、各ＡＳの優先関係を推定する優先関係推定部とを備えることを特徴とする。
【００１２】
上記優先関係推定装置において、優先関係推定部は、ＢＧＰアップデートメッセージ取得部によって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報および時刻情報に基づいて、ＡＳパス毎の利用時間を集計する利用時間集計部と、  ＢＧＰアップデートメッセージ取得部によって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報に基づいて、同一の始点および終点のＡＳを有し同一のパス長であるＡＳパスの組であってパス内のＡＳの１つが相違するＡＳパスの組を抽出し、ＡＳパスの組内の各ＡＳパスから相違するＡＳの組を抽出する抽出部と、抽出部によって抽出されたＡＳパスの組内の各ＡＳパスについて利用時間集計部によって集計された利用時間の長短に基づいて、当該ＡＳパスの組内の各ＡＳパスから抽出されたＡＳの組内の両ＡＳの優先関係を決定する個別優先関係決定部とを備えるようにしてもよい。
【００１３】
上記優先関係推定装置において、優先関係推定部は、更に、個別優先関係決定部によって決定された優先関係にあるＡＳの組が抽出された抽出回数を、優先関係毎に集計する抽出回数集計部と、個別優先関係決定部によって決定された優先関係にある各ＡＳの抽出元である各ＡＳパスについて利用時間集計部によって集計された利用時間を、優先関係毎に合算する利用時間合算部と、抽出回数集計部によって集計された優先関係毎の抽出回数、および、利用時間合算部によって合算された優先関係毎の利用時間に基づいて、抽出部によって抽出された複数のＡＳの組内の全ＡＳの優先関係を決定する全体優先関係決定部とを備えるようにしてもよい。
【００１４】
上記問題を解決するために、本発明の他の態様である障害伝搬シミュレータは、通信ネットワークシステム内を構成する複数のＡＳの各ＢＧＰルータのルータＩＤを推定し、当該通信ネットワークシステム内における障害伝搬をシミュレートする障害伝搬シミュレータであって、複数のＡＳのＢＧＰルータからＢＧＰアップデートメッセージを取得するＢＧＰアップデートメッセージ取得部と、ＢＧＰアップデートメッセージ取得部によって取得されたＢＧＰアップデートメッセージに基づいて、各ＡＳの優先関係を推定する優先関係推定部と、優先関係推定部によって推定されたＡＳの優先関係に基づいて各ＢＧＰルータのルータＩＤを決定するルータＩＤ割当部とを備えることを特徴とする。
【００１５】
上記障害伝搬シミュレータにおいて、優先関係推定部は、ＢＧＰアップデートメッセージ取得部によって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報および時刻情報に基づいて、ＡＳパス毎の利用時間を集計する利用時間集計部と、ＢＧＰアップデートメッセージ取得部によって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報に基づいて、同一の始点および終点のＡＳを有し同一のパス長であるＡＳパスの組であってパス内のＡＳの１つが相違するＡＳパスの組を抽出し、ＡＳパスの組内の各ＡＳパスから相違するＡＳの組を抽出する抽出部と、抽出部によって抽出されたＡＳパスの組内の各ＡＳパスについて利用時間集計部によって集計された利用時間の長短に基づいて、当該ＡＳパスの組内の各ＡＳパスから抽出されたＡＳの組内の両ＡＳの優先関係を決定する個別優先関係決定部と、個別優先関係決定部によって決定された優先関係にあるＡＳの組が抽出された抽出回数を、優先関係毎に集計する抽出回数集計部と、個別優先関係決定部によって決定された優先関係にある各ＡＳの抽出元である各ＡＳパスについて利用時間集計部によって集計された利用時間を、優先関係毎に合算する利用時間合算部と、抽出回数集計部によって集計された優先関係毎の抽出回数、および、利用時間合算部によって合算された優先関係毎の利用時間に基づいて、抽出部によって抽出された複数のＡＳの組内の全ＡＳの優先関係を決定する全体優先関係決定部とを備えるようにしてもよい。
【００１６】
上記問題を解決するために、本発明の他の態様であるプログラムは、通信ネットワークシステム内を構成する複数のＡＳの各ＢＧＰルータのルータＩＤを推定し、当該通信ネットワークシステム内における障害伝搬をシミュレートする障害伝搬シミュレータのコンピュータに、  複数のＡＳのＢＧＰルータからＢＧＰアップデートメッセージを取得するＢＧＰアップデートメッセージ取得ステップと、ＢＧＰアップデートメッセージ取得ステップによって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報および時刻情報に基づいて、ＡＳパス毎の利用時間を集計する利用時間集計ステップと、  ＢＧＰアップデートメッセージ取得ステップによって取得された各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報に基づいて、同一の始点および終点のＡＳを有し同一のパス長であるＡＳパスの組であってパス内のＡＳの１つが相違するＡＳパスの組を抽出し、ＡＳパスの組内の各ＡＳパスから相違するＡＳの組を抽出する抽出ステップと、抽出ステップによって抽出されたＡＳパスの組内の各ＡＳパスについて利用時間集計ステップによって集計された利用時間の長短に基づいて、当該ＡＳパスの組内の各ＡＳパスから抽出されたＡＳの組内の両ＡＳの優先関係を決定する個別優先関係決定ステップと、個別優先関係決定ステップによって決定された優先関係にあるＡＳの組が抽出された抽出回数を、優先関係毎に集計する抽出回数集計ステップと、個別優先関係決定ステップによって決定された優先関係にある各ＡＳの抽出元である各ＡＳパスについて利用時間集計ステップによって集計された利用時間を、優先関係毎に合算する利用時間合算ステップと、抽出回数集計ステップによって集計された優先関係毎の抽出回数、および、利用時間合算ステップによって合算された優先関係毎の利用時間に基づいて、抽出ステップによって抽出された複数のＡＳの組内の全ＡＳの優先関係を決定する全体優先関係決定ステップと、優先関係決定ステップによって決定されたＡＳの優先関係に基づいて各ＢＧＰルータのルータＩＤを決定するルータＩＤ割当ステップとを実行させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、経路障害の伝搬を高精度にシミュレーションすることができるようになる。即ち、ステップ１においてバックアップ経路に関する経路制御ポリシーも含め各ＡＳの経路制御ポリシーを高精度に推定できるようになる。そして、ステップ１において高精度に推定した各ＡＳの経路制御ポリシーをステップ２において適用し、高精度に経路障害の伝搬をシミュレーションすることができるようになる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態による障害シミュレータの構成例である。
【図２】ＢＧＰアップデートメッセージとＲＩＢ（Ｒｏｕｔｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ）情報の一例である。
【図３】優先関係推定部２０の動作を説明するための図である。
【図４】優先関係推定部２０の動作を説明するための図である。
【図５】優先関係推定部２０の動作を説明するための図である。
【図６】優先関係推定部２０の動作を説明するための図である。
【図７】障害伝搬シミュレータ１の動作の一例を示すフローチャートである。
【図８】ＡＳの階層化の模式図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態について図面を参照して詳細に説明する。障害伝搬シミュレータ１は、通信ネットワークシステム内を構成する複数のＡＳの各ＢＧＰルータのルータＩＤを推定し、当該通信ネットワークシステム内における障害伝搬をシミュレートする。障害伝搬シミュレータ１は、図１に示すように、ＢＧＰアップデートメッセージ取得部１０、優先関係推定部２０、ルータＩＤ割当部３０およびエンジン４０を備える。また、優先関係推定部２０は、利用時間集計部２１０、抽出部２２０、個別優先関係決定部２３０、抽出回数集計部２４０、利用時間合算部２５０および全体優先関係決定部２６０から構成される。
【００２０】
ＢＧＰアップデートメッセージ取得部１０は、複数のＡＳのＢＧＰルータ（公開ＢＧＰデータサーバ）からＢＧＰアップデートメッセージ（「受信ｕｐｄａｔｅメッセージ」とも称する）を取得する。ＢＧＰアップデートメッセージ取得部１０は、ＢＧＰアップデートメッセージを優先関係推定部２０に出力する。なお、図２（ａ）は、ＢＧＰアップデートメッセージの一例である。また、ＢＧＰアップデートメッセージ取得部１０は、ＢＧＰアップデートメッセージに加え、経路表のスナップショットであるＲＩＢ（Ｒｏｕｔｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ）情報を取得してもよい。図２（ｂ）は、ＲＩＢ情報の一例である。なお、各公開ＢＧＰデータサーバは、複数のＡＳと接続しており、ＢＧＰアップデートメッセージとＲＩＢ情報を５〜１５分単位の圧縮ファイルで保存する（ｅ．ｇ．  ＲｏｕｔｅＶｉｅｗｓ  プロジェクト：ｈｔｔｐ：／／ｗｗｗ．ｒｏｕｔｅｖｉｅｗｓ．ｏｒｇ／，ＲＩＳプロジェクト：ｈｔｔｐ：／／ｗｗｗ．ｒｉｐｅ．ｎｅｔ／ｒｉｓ／  ）。
【００２１】
優先関係推定部２０は、ＢＧＰアップデートメッセージ取得部１０からＢＧＰアップデートメッセージを取得する。優先関係推定部２０は、ＢＧＰアップデートメッセージ取得部１０から取得したＢＧＰアップデートメッセージに基づいてＡＳの優先関係を推定する。優先関係推定部２０は、推定したＡＳの優先関係をルータＩＤ割当部３０に出力する。なお、優先関係推定部２０を構成する利用時間集計部２１０、抽出部２２０、個別優先関係決定部２３０、抽出回数集計部２４０、利用時間合算部２５０および全体優先関係決定部２６０については後述する。
【００２２】
ここで優先関係推定部２０が推定するＡＳの優先関係について補足説明する。以下、ＡＳの優先関係は、２つのＡＳの不等式によって表現し（例えば、ＡＳｉ＞ＡＳｊ）、優先関係において優先される方のＡＳを「優先ＡＳ」という（ＡＳｉ＞ＡＳｊにおいてＡＳｉは優先ＡＳ）。
【００２３】
ルータＩＤ割当部３０は、優先関係推定部２０からＡＳの優先関係を取得する。ルータＩＤ割当部３０は、優先関係推定部２０から取得した優先関係に基づいてＡＳの各ＢＧＰルータのルータＩＤを割り当てる。具体的には、ルータＩＤ割当部３０は、優先ＡＳであるＢＧＰルータから順に小さい値のルータＩＤを割り当てる。ルータＩＤ割当部３０は、割り当てた各ＢＧＰルータのルータＩＤをエンジン４０に出力する。なお、ルータＩＤは、ユニークな自然数であって例えばＩＰアドレスである。また、ＢＧＰでは、ＡＳパス長などの属性が等しい場合、ルータＩＤの小さいルータから受信したＡＳパスを最適経路として選択する。
【００２４】
エンジン４０は、ルータＩＤ割当部３０から各ＢＧＰルータのルータＩＤを取得する。エンジン４０は、ルータＩＤ割当部３０から取得した各ＢＧＰルータのルータＩＤを適用（設定）して当該通信ネットワークシステム内における経路障害の伝搬をシミュレーションし、結果を外部に出力する。
【００２５】
以下、優先関係推定部２０を構成する利用時間集計部２１０、抽出部２２０、個別優先関係決定部２３０、抽出回数集計部２４０、利用時間合算部２５０および全体優先関係決定部２６０について説明する。
【００２６】
利用時間集計部２１０は、ＢＧＰアップデートメッセージ取得部１０からＢＧＰアップデートメッセージを取得する。利用時間集計部２１０は、ＢＧＰアップデートメッセージ取得部１０から取得した各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報および時刻情報に基づいて、ＡＳパス毎の利用時間を集計（算出）する。
【００２７】
具体的には、利用時間集計部２１０は、ＢＧＰアップデートメッセージとＲＩＢ情報とを解析し、例えば図３（ａ）に示すように、ＡＳパス毎の平均利用時間を算出する。なお、利用時間集計部２１０は、図３（ａ）に示すように、ＡＳパス毎の平均利用時間に加え平均利用時間の割合を算出してもよい。なお、図３（ａ）に示す例は、利用時間集計部２１０が、始点のＡＳ（ＢＧＰメッセージの観測ＡＳ。以下、「始点ＡＳ」という）をＡＳ１および終点のＡＳ（プレフィックス（ｐｒｅｆｉｘ）の広報ＡＳ。以下、「終点ＡＳ」という）をＡＳ９とするプレフィックスの５つのＡＳパス（Ｐ０１、Ｐ０２、Ｐ０３、Ｐ０４、Ｐ０５）の平均利用時間および平均利用時間の割合を算出した場合の例である。なお、集計期間は数ヶ月程度を想定する。利用時間集計部２１０は、集計したＡＳパス毎の平均利用時間を個別優先関係決定部２３０および利用時間合算部２５０に出力する。
【００２８】
抽出部２２０は、ＢＧＰアップデートメッセージ取得部１０からＢＧＰアップデートメッセージを取得する。抽出部２２０は、ＢＧＰアップデートメッセージ取得部１０から取得した各ＢＧＰアップデートメッセージ内に記述されたＡＳパス情報に基づいて、同一の始点ＡＳおよび終点ＡＳを有し同一のパス長であるＡＳパスの組であってパス内のＡＳの１つが相違するＡＳパスの組を抽出する。例えば、抽出部２２０は、図３（ｂ）に示すように、２つのＡＳパスの組（Ｐ０３：Ｐ０４の組、Ｐ０４：Ｐ０５の組）を抽出する。
【００２９】
また、抽出部２２０は、ＡＳパスの組内の各ＡＳパスから上述の相違するＡＳの組を抽出する。例えば、抽出部２２０は、図３（ｂ）に示すように、ＡＳパスの組「Ｐ０３：Ｐ０４」からＡＳの組「ＡＳ７：ＡＳ８」を抽出し、ＡＳパスの組「Ｐ０４：Ｐ０５」からＡＳの組「ＡＳ５：ＡＳ６」を抽出する。抽出部２２０は、抽出したＡＳパスの組およびＡＳの組を個別優先関係決定部２３０に出力し、ＡＳの組を抽出回数集計部２４０に出力する。
【００３０】
個別優先関係決定部２３０は、利用時間集計部２１０からＡＳパス毎の平均利用時間を取得し、抽出部２２０からＡＳパスの組およびＡＳの組を取得する。個別優先関係決定部２３０は、抽出部２２０から取得したＡＳパスの組内の各ＡＳパスについて利用時間集計部２１０によって集計された利用時間の長短（大小）に基づいて、当該ＡＳパスの組内の各ＡＳパスから抽出されたＡＳの組内の両ＡＳの優先関係を決定する。
【００３１】
例えば、個別優先関係決定部２３０は、図３（ｃ）に示すように、ＡＳパスの組「Ｐ０３：Ｐ０４」内のＡＳパス「Ｐ０３」の利用時間「１００００（分）」とＡＳパス「Ｐ０４」の利用時間「５０００（分）」とを比較し、当該ＡＳパスの組「Ｐ０３：Ｐ０４」内の各ＡＳパス「Ｐ０３、Ｐ０４」から抽出されたＡＳの組「ＡＳ７：ＡＳ８」内のＡＳ同士の優先関係を、利用時間が長い方のＡＳパス「Ｐ０３」から抽出されたＡＳ「ＡＳ７」が優先ＡＳとなるように優先関係「ＡＳ７＞ＡＳ８」を決定し、同様に、ＡＳパスの組「Ｐ０４：Ｐ０５」内のＡＳパス「Ｐ０４」の利用時間「５０００（分）」とＡＳパス「Ｐ０５」の利用時間「１０００（分）」とを比較し、当該ＡＳパスの組「Ｐ０４：Ｐ０５」内の各ＡＳパス「Ｐ０４、Ｐ０５」から抽出されたＡＳの組「ＡＳ５：ＡＳ６」内のＡＳ同士の優先関係を、利用時間が長い方のＡＳパス「Ｐ０４」から抽出されたＡＳ「ＡＳ５」が優先ＡＳとなるように優先関係「ＡＳ５＞ＡＳ６」を決定する。なお、個別優先関係決定部２３０は、決定した優先関係を利用時間合算部２５０および抽出回数集計部２４０に出力する。
【００３２】
抽出回数集計部２４０は、抽出部２２０からＡＳの組を取得し、個別優先関係決定部２３０から優先関係を取得する。具体的には、抽出回数集計部２４０は、抽出部２２０が複数のプレフィックスにおいて抽出したＡＳの組を取得し、個別優先関係決定部２３０が複数のプレフィックスにおいて決定した優先関係を取得する。抽出回数集計部２４０は、例えば、図４（ａ）に示すように、個別優先関係決定部２３０から取得した優先関係毎に、当該優先関係にあるＡＳの組が抽出された抽出回数（優先関係の取得回数）を集計する。抽出回数集計部２４０は、優先関係毎に集計した抽出回数を全体優先関係決定部２６０に出力する。
【００３３】
利用時間合算部２５０は、利用時間集計部２１０からＡＳパス毎の平均利用時間を取得し、個別優先関係決定部２３０から優先関係を取得する。具体的には、利用時間合算部２５０は、利用時間集計部２１０が複数のプレフィックスにおいて集計したＡＳパス毎の平均利用時間を取得し、個別優先関係決定部２３０が複数のプレフィックスにおいて決定した優先関係を取得する。利用時間合算部２５０は、例えば、図４（ａ）に示すように、個別優先関係決定部２３０から取得した優先関係毎に、当該優先関係にある各ＡＳの抽出元である各ＡＳパスについて利用時間集計部２１０によって集計された利用時間を合算する。利用時間合算部２５０は、優先関係毎に合算した利用時間を全体優先関係決定部２６０に出力する。
【００３４】
全体優先関係決定部２６０は、利用時間合算部２５０から優先関係毎に合算した利用時間を取得し、抽出回数集計部２４０から優先関係毎に集計した抽出回数を取得する。具体的には、全体優先関係決定部２６０は、図４（ａ）に示すように、利用時間合算部２５０が複数のプレフィックスにおいて優先関係毎に合算した合算利用時間を取得し、抽出回数集計部２４０が複数のプレフィックスにおいて優先関係毎に集計した抽出回数を取得する。全体優先関係決定部２６０は、抽出回数集計部２４０から取得した優先関係毎の抽出回数、および、利用時間合算部２５０から取得した優先関係毎の利用時間に基づいて、抽出部２２０によって抽出された複数のＡＳの組内の全ＡＳの優先関係を決定する。
【００３５】
具体的には、まず、全体優先関係決定部２６０は、抽出回数の降順に優先関係をソートするとともに、優先関係にある各ＡＳパスの合算利用時間の比率（ＡＳパスの組内の各ＡＳパスの合算利用時間の比率）を算出する。例えば、全体優先関係決定部２６０は、図４（ａ）に示す情報から図４（ｂ）に示す情報を生成（算出）する。
【００３６】
続いて、全体優先関係決定部２６０は、優先関係として対応付けられているＡＳ同士を深さ優先探索アルゴリズムに基づいて、複数の優先関係を幾つかのグループにグループ化（グラフ化）する。まず、全体優先関係決定部２６０は、何れかの優先関係に属する各ＡＳを深さ優先探索アルゴリズムに基づいてグループ化し、各グループに属する各ＡＳから構成される優先関係に纏めることによって複数の優先関係を幾つかのグループにグループ化する。例えば、全体優先関係決定部２６０は、図４（ｂ）に示す７つの優先関係に含まれる９つのＡＳ（ＡＳ１、ＡＳ２、ＡＳ３、ＡＳ５、ＡＳ６、ＡＳ７、ＡＳ８、ＡＳ９、ＡＳ１０）を深さ優先探索アルゴリズムによって、図５（ａ）に示す６つのＡＳ（ＡＳ５、ＡＳ６、ＡＳ７、ＡＳ８、ＡＳ９、ＡＳ１０）と図５（ｂ）に示す３つのＡＳ（ＡＳ１、ＡＳ２、ＡＳ３）とにグループ化し、図５（ａ）に示すグループに属する各ＡＳから構成される図５（ｃ）の優先関係のグループと図５（ｂ）に示すグループに属する各ＡＳから構成される図５（ｄ）の優先関係のグループとにグループ化する。
【００３７】
続いて、全体優先関係決定部２６０は、以下の手順に従って、抽出部２２０によって抽出された複数のＡＳの組内の全ＡＳに擬似ＩＤを付与し、全ＡＳの優先関係を決定する。全体優先関係決定部２６０は、決定した全ＡＳの優先関係をルータＩＤ割当部３０に出力する。
【００３８】
手順１：抽出回数が多い優先関係を含むグループにおいて、抽出回数最大の優先関係に着目し、当該優先関係の優先ＡＳに擬似ＩＤ「１」を付与し、当該優先関係の他方のＡＳ（優先ＡＳでないＡＳ）の擬似ＩＤの値として、優先ＡＳに付与した擬似ＩＤ「１」に合計利用時間の比率を乗じて得た値を付与する。つまり、優先関係の両ＡＳの擬似ＩＤの比率を合計利用時間の比率と一致させる。
手順２：当該グループにおいて、抽出回数が次に多い優先関係に着目し、当該優先関係の何れかのＡＳの擬似ＩＤが既に付与されている場合、擬似ＩＤが付与されていない一方のＡＳの擬似ＩＤの値として、他方のＡＳに既に付与されている擬似ＩＤの値に合計利用時間の比率を乗じて得た値を付与する。一方、当該優先関係の何れのＡＳの擬似ＩＤも未だ付与されていない場合、何れかのＡＳの擬似ＩＤが付与されるまで当該優先関係を保留する。
手順３：手順２（または当該手順３）において擬似ＩＤを付与したＡＳを含む優先関係を保留している場合、保留している当該優先関係に着目し、擬似ＩＤが付与されていないＡＳの擬似ＩＤの値として、手順２（または当該手順３）において付与した擬似ＩＤの値に合計利用時間の比率を乗じて得た値を付与し、当該優先関係の保留を解除する。一方、手順２において擬似ＩＤを付与したＡＳを含む優先関係を保留していない場合、手順２に戻る。
手順４：当該グループ内の優先関係の全てを確認した場合、擬似ＩＤの昇順に優先関係を決定する。同様に、抽出回数が次に多い優先関係を含むグループにおいて、手順１から４を実行する。
手順５：全てのグループを確認した場合、抽出回数の多い優先関係を含むグループ内のＡＳが上位となるように各グループのＡＳの優先関係を結合する。
例えば、全体優先関係決定部２６０は、図５に示す例の場合、図６に示すように、全ＡＳ（ＡＳ１、ＡＳ２、ＡＳ３、ＡＳ５、ＡＳ６、ＡＳ７、ＡＳ８、ＡＳ９、ＡＳ１０）の優先関係（ＡＳ７＞ＡＳ８＞ＡＳ５＞ＡＳ６＞ＡＳ９＞ＡＳ１０＞ＡＳ２＞ＡＳ１＞ＡＳ３）を決定する。
【００３９】
なお、全体優先関係決定部２６０から全ＡＳ（ＡＳ１、ＡＳ２、ＡＳ３、ＡＳ５、ＡＳ６、ＡＳ７、ＡＳ８、ＡＳ９、ＡＳ１０）の優先関係（ＡＳ７＞ＡＳ８＞ＡＳ５＞ＡＳ６＞ＡＳ９＞ＡＳ１０＞ＡＳ２＞ＡＳ１＞ＡＳ３）を取得したルータＩＤ割当部３０は、優先ＡＳの順（ＡＳ７、ＡＳ８、ＡＳ５、ＡＳ６、ＡＳ９、ＡＳ１０、ＡＳ２、ＡＳ１、ＡＳ３）に、ＡＳ７のＢＧＰルータに最小のルータＩＤ（ＩＰアドレス）、ＡＳ３に最大のルータＩＤ（ＩＰアドレス）を決定する（割り当てる）。ルータＩＤ割当部３０は、決定した各ＢＧＰルータのルータＩＤをエンジン４０に出力する。
【００４０】
以下、図７を用いて障害伝搬シミュレータ１の動作を説明する。ＢＧＰアップデートメッセージ取得部１０は、各公開ＢＧＰデータサーバからＢＧＰアップデートメッセージおよびＲＩＢ情報を取得する（ステップＳ１０）。
【００４１】
利用時間集計部２１０は、ＢＧＰアップデートメッセージとＲＩＢ情報とを解析し、プレフィックス毎、ＡＳパス毎の平均利用時間を集計（算出）し、プレフィックス毎の利用時間をＡＳパス毎に集計（集約）し、ＡＳパス毎の平均利用時間を算出する（ステップＳ２０）。
【００４２】
抽出部２２０は、ＡＳパス長および両端のＡＳ（始点ＡＳおよび終点ＡＳ）が同一のＡＳパスの組であって、組内のＡＳの差異が高々１ＡＳであるＡＳパスの組を抽出する（ステップＳ３０）。即ち、抽出部２２０は、両端のＡＳ（始点ＡＳおよび終点ＡＳ）を有し同一のパス長であるＡＳパスの組であってパス内のＡＳの１つが相違するＡＳパスの組を抽出する。組内のＡＳの差異が高々１ＡＳであることを条件とする理由は、何れのＡＳの経路制御ポリシーが有効であるか（寄与しているか）判別できないからである。また、抽出部２２０は、ＡＳパスの組内の各ＡＳパスからＡＳの組を抽出する（ステップＳ４０）。
【００４３】
個別優先関係決定部２３０は、ステップＳ４０において抽出されたＡＳの組内の両ＡＳの優先関係を決定する（ステップＳ５０）。抽出回数集計部２４０は、ステップＳ５０において決定した優先関係にある両ＡＳの組毎の抽出回数を集計する（ステップＳ６０）。利用時間合算部２５０は、ステップＳ５０において決定した優先関係にある各ＡＳの抽出元である各ＡＳパスの各利用時間を合算する（ステップＳ７０）。
【００４４】
全体優先関係決定部２６０は、抽出回数の昇順に優先関係をソートする（ステップＳ８０）。全体優先関係決定部２６０は、ステップＳ７０において合算した合算利用時間の比率を算出する（ステップＳ９０）。全体優先関係決定部２６０は、深さ優先探索アルゴリズムに基づいて優先関係をグループ化（グラフ化）する（ステップＳ１００）。
【００４５】
全体優先関係決定部２６０は、グループ毎にグループ内のＡＳに擬似ＩＤを付与し、全グループのＡＳ（ステップＳ４０において抽出された全ＡＳの組内の全ＡＳ）の優先関係を決定する（ステップＳ１１０）。より詳細には、全体優先関係決定部２６０は、グループ毎に、グループ内のＡＳの優先関係を決定し、全グループの優先関係を決定した後、抽出回数の多い優先関係を含むグループ内のＡＳが上位となるように全グループのＡＳの優先関係を決定する。
【００４６】
ルータＩＤ割当部３０は、ステップＳ１１０において決定した優先関係に従って各ＢＧＰルータのルータＩＤ（ＩＰアドレス）を割り当てる（ステップＳ１２０）。エンジン４０は、ルータＩＤ割当部３０から取得した各ＢＧＰルータのルータＩＤを適用して（例えば、ＢＧＰの最適経路計算に使用されるＬｏｃａｌ  Ｐｒｅｆｅｒｅｎｃｅ、ＭＥＤ値などを設定して）、当該通信ネットワークシステム内における経路障害の伝搬をシミュレーションする（ステップＳ１３０）。そして本フローチャートは終了する。
【００４７】
以上、説明した様に、優先関係推定部２０は、利用時間が長いＡＳは優先経路上のＡＳであるとの仮説の下、複数のＡＳの優先関係を決定している。換言すれば、利用時間の長いＡＳパスほど優先度の高い経路であると想定（バックアップ経路は現用経路よりも利用時間が短いと想定）して、ＢＧＰ経路制御ポリシーを推定している。
【００４８】
以上、本実施形態の障害伝搬シミュレータによれば、高精度な経路障害シミュレーションを実現することができるようになる。即ち、ステップ１に関しては、バックアップ経路に関する経路制御ポリシーも含め各ＡＳの経路制御ポリシーを高精度に推定することができるようになる。また、ステップ２に関しては、適用する各ＡＳの経路制御ポリシーの精度が向上するため、経路障害シミュレーションの精度の向上を図ることができるようになる。つまり、ステップ２の解決方法として、既存のネットワークシミュレータ（例えば、ｎｓ２、ＢＧＰ＋＋）を利用して、ＢＧＰ経路障害シミュレーションを実行する際に、設定する各ＢＧＰルータのルータＩＤの大小関係により、ステップ１にて推定した経路制御ポリシーを適用する（ＢＧＰでは、ＡＳパス長などの属性が同じ場合、ルータＩＤの小さいルータからの広報パスが最適経路として選択されることを利用する）。
【００４９】
なお、本発明の一実施形態による障害伝搬シミュレータの各処理を実行するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、当該記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、本発明の一実施形態によるｘｘに係る上述した種々の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００５０】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００５１】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００５２】
１  障害伝搬シミュレータ  １０  ＢＧＰアップデートメッセージ取得部  ２０  優先関係推定部  ３０  ルータＩＤ割当部  ４０  エンジン  ２１０  利用時間集計部  ２２０  抽出部  ２３０  個別優先関係決定部  ２４０  抽出回数集計部  ２５０  利用時間合算部  ２６０  全体優先関係決定部
【図１】
2010178172.tif 000003
【図２】
2010178172.tif 000004
【図３】
2010178172.tif 000005
【図４】
2010178172.tif 000006
【図５】
2010178172.tif 000007
【図６】
2010178172.tif 000008
【図７】
2010178172.tif 000009
【図８】
2010178172.tif 000010