(57)【要約】【課題】ネットワークの経路と帯域を検証できる経路テーブル検証装置および経路テーブル検証方法を提供する。【解決手段】生成部４２は、ネットワークに対して通信経路および帯域の割当てを求めたデマンドに基づいて、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。算出部４３は、ネットワークの各ノードの経路テーブルに基づいて、生成されたパケットの転送経路を算出する。経路検証部４４は、算出により最終ノードに到達したパケットの送信元アドレスと宛先アドレスから、デマンドの通信経路との整合性を検証する。帯域検証部４５は、算出された転送経路とパケットの帯域情報から、ノード間のリンクごと帯域を積算してリンクの帯域量との整合性を検証する。【選択図】図３
2016158232.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークに対して通信経路および帯域の割当てを求めたデマンドに基づいて、前記通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する生成部と、
前記ネットワークの各ノードの経路テーブルに基づいて、前記生成部により生成されたパケットの転送経路を算出する算出部と、
前記算出部による算出により最終ノードに到達したパケットの送信元アドレスと宛先アドレスから、前記デマンドの通信経路との整合性を検証する経路検証部と、
前記算出部による算出された転送経路とパケットの帯域情報から、ノード間のリンクごと帯域を積算してリンクの帯域量との整合性を検証する帯域検証部と、
を有することを特徴とする経路テーブル検証装置。
【請求項２】
前記生成部は、前記デマンドごとに、当該デマンドの通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成し、
前記算出部は、前記生成部により生成されたパケットごとに、転送経路を算出し、
前記経路検証部は、最終ノードに到達したパケットごとに、当該パケットの送信元アドレスと宛先アドレスから、前記デマンドの通信経路との整合性を検証し、
前記帯域検証部は、ノード間のリンクごとに、リンクを通過するパケットの帯域を積算してリンクの帯域量との整合性を検証する
ことを特徴とする請求項１に記載の経路テーブル検証装置。
【請求項３】
前記生成部は、各デマンドの通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報を含んだパケットを生成し、
前記算出部は、ノードごとに、当該ノードの経路テーブルに基づいて、パケットに含まれる各デマンドの送信先アドレスに対応する転送先を識別し、転送先ごとに、当該転送先と識別されたデマンドの送信元アドレス、宛先アドレス、帯域情報を含んだパケットを転送して転送経路を算出し、
前記帯域検証部は、ノード間のリンクごとに、リンクを通過するパケットに含まれる各帯域を積算してリンクの帯域量との整合性を検証する
ことを特徴とする請求項１に記載の経路テーブル検証装置。
【請求項４】
前記生成部は、時間帯ごとに使用する帯域情報が付されたパケットを生成し、
前記帯域検証部は、リンクを通過するパケットの帯域を時間帯ごとに積算して時間帯ごとにリンクの帯域量との整合性を検証する
ことを特徴とする請求項１〜３の何れか１つに記載の経路テーブル検証装置。
【請求項５】
前記生成部は、デマンドの通信経路のアドレスの補集合となるアドレスのデマンド外のパケットを生成し、
前記算出部は、前記ネットワークの各ノードの経路テーブルに基づいて、前記生成部により生成されたデマンド外のパケットの転送経路を算出し、
前記経路検証部は、前記算出部による算出結果から、デマンド外のパケットが前記ネットワークの何れかのノードで転送されずにドロップしたかを検証する
ことを特徴とする請求項１〜４の何れか１つに記載の経路テーブル検証装置。
【請求項６】
前記デマンドが複数ある場合、各デマンドの通信経路のアドレスを隣接するアドレス空間となるように変換すると共に、当該アドレスの変換に対応させて、前記各ノードの経路テーブルのアドレスを変換する変換部をさらに有し、
前記生成部は、各デマンドの変換されたアドレスの和の補集合となるアドレスのデマンド外のパケットを生成し、
前記算出部は、アドレスが変換された前記各ノードの経路テーブルに基づいて、前記デマンド外のパケットの転送経路を算出する
ことを特徴とする請求項５に記載の経路テーブル検証装置。
【請求項７】
前記生成部は、変換された各デマンドのアドレスの和を示すアドレスが、ワイルドカードを用いた場合に１つのアドレスとなるように補完する補完アドレスを求め、前記補完アドレスと前記各デマンドのアドレスとの和の補集合となるアドレスおよび前記補完アドレスをアドレスとしたデマンド外のパケットを生成する
ことを特徴とする請求項６に記載の経路テーブル検証装置。
【請求項８】
ネットワークに対して通信経路および帯域の割当てを求めたデマンドに基づいて、前記通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成し、
前記ネットワークの各ノードの経路テーブルに基づいて、生成されたパケットの転送経路を算出し、
最終ノードに到達したパケットの送信元アドレスと宛先アドレスから、前記デマンドの通信経路との整合性を検証し、
前記転送経路とパケットの帯域情報から、ノード間のリンクごと帯域を積算してリンクの帯域量との整合性を検証する
処理をコンピュータが実行することを特徴とする経路テーブル検証方法。
【請求項９】
ネットワークに対して通信経路の割当てを求めたデマンドに基づいて、前記通信経路のアドレスの補集合となるアドレスのパケットを生成する生成部と、
前記ネットワークの各ノードの経路テーブルに基づいて、前記生成部により生成されたパケットの転送経路を算出する算出部と、
前記算出部による算出結果から、前記パケットが前記ネットワークの何れかのノードで転送されずにドロップしたかを検証する検証部と、
を有することを特徴とする経路テーブル検証装置。
【請求項１０】
前記デマンドが複数ある場合、各デマンドの通信経路のアドレスを隣接するアドレス空間となるように変換すると共に、当該アドレスの変換に対応させて、前記各ノードの経路テーブルのアドレスを変換する変換部をさらに有し、
前記生成部は、各デマンドの変換されたアドレスの和の補集合となるアドレスのパケットを生成し、
前記算出部は、宛先アドレスが変換された前記各ノードの経路テーブルに基づいて、前記パケットの転送経路を算出する
ことを特徴とする請求項９に記載の経路テーブル検証装置。
【請求項１１】
前記生成部は、変換された各デマンドのアドレスの和を示すアドレスが、ワイルドカードを用いた場合に１つのアドレスとなるように補完する補完アドレスを求め、前記補完アドレスと前記各デマンドのアドレスとの和の補集合となるアドレスおよび前記補完アドレスをアドレスとしたパケットを生成する
ことを特徴とする請求項１０に記載の経路テーブル検証装置。
【請求項１２】
ネットワークに対して通信経路の割当てを求めたデマンドに基づいて、前記通信経路のアドレスの補集合となるアドレスのパケットを生成し、
前記ネットワークの各ノードの経路テーブルに基づいて、生成されたパケットの転送経路を算出し、
算出結果から、前記パケットが前記ネットワークの何れかのノードで転送されずにドロップしたかを検証する
処理をコンピュータが実行することを特徴とする経路テーブル検証方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路テーブル検証装置および経路テーブル検証方法に関する。
【背景技術】
【０００２】
近年、ネットワークの制御に関する技術として、ＳＤＮ（Software  defined  networking)の認知が高まっている。ＳＤＮは、ネットワークを構成する通信機器をソフトウェアによって集中的に制御し、ネットワークの構造や構成、設定などを柔軟に、動的に変更可能とする。これにより、今後、ネットワークは、プログラマビリティ、オープン化が進展すると予測される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００５−１９１７６３号公報
【特許文献２】特開２００９−１３０９０９号公報
【特許文献３】国際公開第２０１１／０８３７８６号
【特許文献４】特開２００４−２１５００６号公報
【特許文献５】特開２００８−１１５３８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＳＤＮでは、ネットワークを利用する網利用者がソフトウェアによってネットワークを変更することが可能となる。しかしながら、網利用者によってネットワークを変更可能とした場合、ネットワークを提供する網提供者がネットワークを全て一元管理していた場合に比べて、ネットワークの動作に不整合や想定外の事象が起きる可能性が高くなる。例えば、ネットワークでパケットが転送先に転送されなくなる場合や帯域を確保できない場合がある。
【０００５】
一つの側面では、ネットワークの経路と帯域を検証できる経路テーブル検証装置および経路テーブル検証方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
第１の案では、経路テーブル検証装置は、生成部と、算出部と、経路検証部と、帯域検証部とを有する。生成部は、ネットワークに対して通信経路および帯域の割当てを求めたデマンドに基づいて、前記通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。算出部は、ネットワークの各ノードの経路テーブルに基づいて、生成部により生成されたパケットの転送経路を算出する。経路検証部は、算出部による算出により最終ノードに到達したパケットの送信元アドレスと宛先アドレスから、デマンドの通信経路との整合性を検証する。帯域検証部は、算出部による算出された転送経路とパケットの帯域情報から、ノード間のリンクごと帯域を積算してリンクの帯域量との整合性を検証する。
【発明の効果】
【０００７】
本発明の一の実施態様によれば、ネットワークの経路と帯域を検証できるという効果を奏する。
【図面の簡単な説明】
【０００８】
【図１】図１は、ネットワークの設計の流れを模式的に示した図である。
【図２】図２は、システムの全体の概略構成の一例を示す図である。
【図３】図３は、経路テーブル検証装置の機能的な構成の一例を示す図である。
【図４】図４は、ネットワーク情報に記憶されたネットワークの一例を模式的に示した図である。
【図５】図５は、デマンド情報のデータ構成の一例を示す図である。
【図６Ａ】図６Ａは、経路テーブルのデータ構成の一例を示す図である。
【図６Ｂ】図６Ｂは、経路テーブルのデータ構成の一例を示す図である。
【図６Ｃ】図６Ｃは、経路テーブルのデータ構成の一例を示す図である。
【図７】図７は、リンク帯域管理テーブルのデータ構成の一例を示す図である。
【図８】図８は、実施例１に係るパケットのヘッダの一例を示す図である。
【図９】図９は、ビット演算の一例を示す図である。
【図１０Ａ】図１０Ａは、デマンドに対応するパケットの転送経路を算出した結果の一例を示す図である。
【図１０Ｂ】図１０Ｂは、デマンド外のパケットの転送経路を算出した結果の一例を示す図である。
【図１１】図１１は、転送経路の一例を示す図である。
【図１２】図１２は、リンク帯域管理テーブルの一例を示す図である。
【図１３】図１３は、実施例１に係る検証処理の手順の一例を示すフローチャートである。
【図１４】図１４は、実施例１に係る転送経路算出処理の手順の一例を示すフローチャートである。
【図１５】図１５は、実施例２に係るパケットのヘッダの構成の一例を示す図である。
【図１６】図１６は、実施例２に係るパケットのヘッダの一例を示す図である。
【図１７】図１７は、デマンドに対応するパケットの転送経路を算出した結果の一例を示す図である。
【図１８】図１８は、転送経路の一例を示す図である。
【図１９】図１９は、実施例２に係る検証処理の手順の一例を示すフローチャートである。
【図２０】図２０は、実施例２に係る転送経路算出処理の手順の一例を示すフローチャートである。
【図２１】図２１は、経路テーブル検証装置の機能的な構成の一例を示す図である。
【図２２】図２２は、アドレスの変換を模式的に示した図である。
【図２３Ａ】図２３Ａは、平行移動の一例を示す図である。
【図２３Ｂ】図２３Ｂは、ビットシフトの一例を示す図である。
【図２４Ａ】図２４Ａは、デマンド外のパケットのアドレスの求め方の一例を示す図である。
【図２４Ｂ】図２４Ｂは、デマンド外のパケットのアドレスの求め方の一例を示す図である。
【図２５】図２５は、アドレス空間でのアドレスと補完アドレスを模式的に示した図である。
【図２６】図２６は、検証環境の変換を模式的に示した図である。
【図２７Ａ】図２７Ａは、変換前の検証環境の一例を説明する図である。
【図２７Ｂ】図２７Ｂは、変換後の検証環境の一例を説明する図である。
【図２８Ａ】図２８Ａは、変換前の検証環境の一例を説明する図である。
【図２８Ｂ】図２８Ｂは、変換後の検証環境の一例を説明する図である。
【図２９Ａ】図２９Ａは、変換前の検証環境の一例を説明する図である。
【図２９Ｂ】図２９Ｂは、変換後の検証環境の一例を説明する図である。
【図３０】図３０は、実施例３に係る生成処理の手順の一例を示すフローチャートである。
【図３１】図３１は、実施例３に係る変換処理の手順の一例を示すフローチャートである。
【図３２】図３２は、パケットのヘッダの一例を示す図である。
【図３３】図３３は、リンク帯域管理テーブルのデータ構成の一例を示す図である。
【図３４】図３４は、ネットワークに設定された経路テーブルがデマンドを満たすか検証する例を模式的に示した図である。
【図３５】図３５は、検証の流れの他の例を模式的に示した図である。
【図３６】図３６は、経路テーブル検証プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【０００９】
以下に、本発明に係る経路テーブル検証装置および経路テーブル検証方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。そして、各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１０】
［ネットワークの設計および検証］
最初に、ネットワークの設計および検証について説明する。近年、ネットワークは、ネットワークを構成する通信機器をソフトウェアによって集中的に制御することが可能とされている。このようにネットワークの制御に関する技術として、ＳＤＮがある。ＳＤＮは、ネットワークを構成する通信機器をソフトウェアによって集中的に制御し、ネットワークの構造や構成、設定などを柔軟に、動的に変更可能とする。
【００１１】
ＳＤＮでは、ネットワークを利用する網利用者がソフトウェアによってネットワークを変更することが可能となる。図１は、ネットワークの設計の流れを模式的に示した図である。網利用者は、ネットワークに対するデマンドを入力する。例えば、網利用者は、ネットワークに対する通信経路および帯域の割当てを求めたデマンドを入力する。図１の例では、デマンドとして、通信経路の送信元および送信先に対応させて、通信経路で確保したい帯域がマトリクス状に示されている。デマンドの「Ｓｒｃ」の項目は、通信経路の送信元を記憶する領域である。デマンドの「Ｄｓｔ」の項目は、通信経路の宛先を記憶する領域である。図１の例では、送信元および宛先として、ネットワークで末端のノード（エッジノード）となるノードＡ、ノードＢ、ノードＣの情報と、送信元のノードアドレスまたは宛先のノードアドレスが設定されている。例えば、送信元および宛先には、「ノードＡ：ＩＰ＿ａ」、「ノードＢ：ＩＰ＿ｂ」および「ノードＣ：ＩＰ＿ｃ」が設定されている。なお、送信元のノードアドレスまたは宛先のノードアドレスはエッジノードのアドレスであってもよい。デマンドの送信元と宛先に対応する領域には、確保したい帯域を示す数値が設定されている。図１の例では、送信元「ノードＡ：ＩＰ＿ａ」と宛先「ノードＢ：ＩＰ＿ｂ」と間で確保したい帯域が「１００」Ｍｂｐｓであることを示す。また、図１の例では、送信元「ノードＡ：ＩＰ＿ａ」と宛先「ノードＣ：ＩＰ＿ｃ」と間で確保したい帯域が「５０」Ｍｂｐｓであることを示す。また、図１の例では、送信元「ノードＢ：ＩＰ＿ｂ」と宛先「ノードＣ：ＩＰ＿ｃ」と間で確保したい帯域が「１００」Ｍｂｐｓであることを示す。なお、「−」が設定された領域は、通信経路の設定がないことを示す。
【００１２】
ネットワーク設計では、デマンドに従い、経路設計が行われる。例えば、ネットワーク設計では、実際のネットワークを構成する各ノードに対して、デマンドの通信経路および帯域に応じて経路設計が行われる。図１の例では、「Ａ−Ｄ−Ｂ；１００」として、ノードＡ、ノードＤ、ノードＢの経路で１００Ｍｂｐｓの経路を確保することを示す。また、図１の例では、「Ａ−Ｄ−Ｆ−Ｅ−Ｃ；５０」として、ノードＡ、ノードＤ、ノードＦ、ノードＥ、ノードＣの経路で５０Ｍｂｐｓの経路を確保することを示す。
【００１３】
ネットワーク設計では、経路設計に従い、実際のネットワークを構成する各通信機器をそれぞれノードとして、各ノードの経路テーブルが生成される。例えば、ネットワーク設計では、経路設計の経路情報から、各ノードに設定する経路テーブルのエントリ情報を導出する。
【００１４】
このように、網利用者によってネットワークを変更可能とした場合、ネットワークを提供する網提供者がネットワークを全て一元管理していた場合に比べて、ネットワークの動作に不整合や想定外の事象が起きる可能性が高くなる。例えば、ネットワークでパケットが転送先に転送されなくなる場合や帯域を確保できない場合がある。そこで、本実施例では、生成された経路テーブルを実際のネットワークに適用する前に、生成された経路テーブルの妥当性の検証をソフトウェア上で行う。例えば、生成された各ノードの経路テーブルが、元のデマンドを満たすか、かつ、ミスを含まないかを検証する。このように検証を行った後に経路テーブルを実際のネットワークに適用することで、実際のネットワークの動作に不整合や想定外の事象が起きることを抑制できる。
【００１５】
［システム構成］
次に、本実施例に係るシステム１について説明する。システム１は、ＳＤＮを適用して、実際のネットワーク１４を構成する通信機器をソフトウェアによって集中的に制御するシステムである。図２は、システムの全体の概略構成の一例を示す図である。システム１は、経路テーブル検証装置１０と、ＮＷ（ネットワーク）設計装置１１と、ＮＷ設定装置１２とを有する。
【００１６】
ＮＷ設計装置１１は、ネットワーク設計を行う装置である。ＮＷ設計装置１１は、例えば、パーソナルコンピュータやサーバコンピュータなどのコンピュータなどである。ＮＷ設計装置１１は、ネットワーク１４に対して通信経路および帯域の割当てを求めたデマンドの入力を受け付ける。例えば、ＮＷ設計装置１１は、デマンドとして、通信経路の送信元および送信先と、通信経路で確保したい帯域の入力を受け付ける。ＮＷ設計装置１１は、デマンドに従い、パケットを転送させる経路を設計する。そして、ＮＷ設計装置１１は、設計された経路に従い、実際のネットワーク１４を構成する各ノードの経路テーブルを生成する。ＮＷ設計装置１１は、受け付けたデマンドと、生成した各ノードの経路テーブルを経路テーブル検証装置１０へ送信して検証を要求する。
【００１７】
経路テーブル検証装置１０は、経路テーブルの検証を行う装置である。経路テーブル検証装置１０は、例えば、パーソナルコンピュータやサーバコンピュータなどのコンピュータなどである。経路テーブル検証装置１０は、各ノードの経路テーブルが、元のデマンドを満たすか、かつミスを含まないかを検証し、検証結果をＮＷ設計装置１１へ通知する。
【００１８】
ＮＷ設計装置１１は、経路テーブル検証装置１０による検証結果に異常が無い場合、各ノードの経路テーブルをＮＷ設定装置１２へ送信する。
【００１９】
ＮＷ設定装置１２は、実際のネットワーク１４に対して各種の設定を行う装置である。ＮＷ設定装置１２は、例えば、パーソナルコンピュータやサーバコンピュータなどのコンピュータなどである。ＮＷ設定装置１２は、各ノードの経路テーブルを、経路テーブルを設定する所定の設定コマンドを用いて、ネットワーク１４の各ノードに設定する。これにより、ネットワーク１４は、構造や構成、設定が変更され、デマンドとして要求された通信経路および帯域が確保される。システム１では、経路テーブルを実際のネットワーク１４に設定する前に、経路テーブル検証装置１０により経路テーブルの検証を行う。これにより、システム１では、網利用者がネットワークを変更する場合でも、ネットワークの動作に不整合や想定外の事象が起きることを抑制できる。
【００２０】
［経路テーブル検証装置の構成］
次に、本実施例に係る経路テーブル検証装置１０の構成について説明する。図３は、経路テーブル検証装置の機能的な構成の一例を示す図である。図３に示すように、経路テーブル検証装置１０は、通信Ｉ／Ｆ（インタフェース）部２０と、入力部２１と、表示部２２と、記憶部２３と、制御部２４とを有する。なお、経路テーブル検証装置１０は、上記の機器以外の他の機器を有してもよい。
【００２１】
通信Ｉ／Ｆ部２０は、他の装置との間で通信制御を行うインタフェースである。通信Ｉ／Ｆ部２０としては、ＬＡＮカードなどのネットワークインタフェースカードを採用できる。
【００２２】
通信Ｉ／Ｆ部２０は、不図示のネットワークを介して他の装置と各種情報を送受信する。例えば、通信Ｉ／Ｆ部２０は、ＮＷ設計装置１１から受け付けたデマンドの情報や各ノードの経路テーブルを受信する。
【００２３】
入力部２１は、各種の情報を入力する入力デバイスである。入力部２１としては、マウスやキーボードなどの操作の入力を受け付ける入力デバイスが挙げられる。入力部２１は、各種の情報の入力を受け付ける。例えば、入力部２１は、検証に関する各種の操作入力を受け付ける。入力部２１は、ユーザからの操作入力を受け付け、受け付けた操作内容を示す操作情報を制御部２４に入力する。
【００２４】
表示部２２は、各種情報を表示する表示デバイスである。表示部２２としては、ＬＣＤ（Liquid  Crystal  Display）やＣＲＴ（Cathode  Ray  Tube）などの表示デバイスが挙げられる。表示部２２は、各種情報を表示する。例えば、表示部２２は、各種の操作画面や検証結果を示した画面など、検証に関する各種の画面を表示する。
【００２５】
記憶部２３は、各種のデータを記憶する記憶デバイスである。例えば、記憶部２３は、ハードディスク、ＳＳＤ（Solid  State  Drive）、光ディスクなどの記憶装置である。なお、記憶部２３は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ、ＮＶＳＲＡＭ（Non  Volatile  Static  Random  Access  Memory）などのデータを書き換え可能な半導体メモリであってもよい。
【００２６】
記憶部２３は、制御部２４で実行されるＯＳ（Operating  System）や各種プログラムを記憶する。例えば、記憶部２３は、後述する各種の処理を実行するプログラムを含む各種のプログラムを記憶する。さらに、記憶部２３は、制御部２４で実行されるプログラムで用いられる各種データを記憶する。例えば、記憶部２３は、ネットワーク情報３０と、デマンド情報３１と、経路テーブル３２と、リンク帯域管理テーブル３３とを記憶する。
【００２７】
ネットワーク情報３０は、実際のネットワーク１４に関する各種の情報を記憶したデータである。例えば、ネットワーク情報３０には、ネットワーク１４を構成する各通信機器をそれぞれノードとした接続関係を示すネットワークトポロジーや、各ノードの設定が記憶されている。また、ネットワーク情報３０には、接続されたノード間のリンクの帯域量の情報が記憶されている。
【００２８】
図４は、ネットワーク情報に記憶されたネットワークの一例を模式的に示した図である。図４の例では、ネットワーク１４は、ノードＡ、ノードＢ、ノードＣ及びノードＤを有し、ノードＤを介してノードＡ、ノードＢ、ノードＣが接続されている。ノードＡ、ノードＢおよびノードＣは、外部と通信を行うエッジノードである。ノードＤは、エッジノードからのデータを中継する中継ノードである。
【００２９】
ノードＡは、アドレス「１０ＸＸ」の外部ポートと、インタフェースｉｆ＿ａ１を有し、インタフェースｉｆ＿ａ１を介してノードＤと接続されている。ノードＢは、アドレス「００ＸＸ」の外部ポートと、インタフェースｉｆ＿ｂ１を有し、インタフェースｉｆ＿ｂ１を介してノードＤと接続されている。ノードＣは、アドレス「０１ＸＸ」の外部ポートと、インタフェースｉｆ＿ｃ１を有し、インタフェースｉｆ＿ｃ１を介してノードＤと接続されている。ノードＤは、インタフェースｉｆ＿ｄ１、ｉｆ＿ｄ２、ｉｆ＿ｄ３を有し、インタフェースｉｆ＿ｄ１を介してノードＡと接続され、インタフェースｉｆ＿ｄ２を介してノードＢと接続され、インタフェースｉｆ＿ｄ３を介してノードＣと接続されている。なお、本実施例では、説明を簡易化するため、アドレスを例えば「１０ＸＸ」と４ビットで示している。また、アドレスの「Ｘ」は、アドレスのビットが「０」でも「１」でも該当するものとみなすワイルドカードを表す。
【００３０】
図３に戻り、デマンド情報３１は、ネットワーク１４に対して要求されたデマンドの情報を記憶したデータである。例えば、デマンド情報３１には、ネットワーク１４に対して割当てが求められた通信経路および帯域の情報が記憶されている。
【００３１】
図５は、デマンド情報のデータ構成の一例を示す図である。図５に示すように、デマンド情報３１は、「Ｓｒｃ」、「Ｄｓｔ」、「帯域」の各項目を有する。Ｓｒｃの項目は、割当てが求められた通信経路の送信元を記憶する領域である。Ｄｓｔの項目は、割当てが求められた通信経路の宛先を記憶する領域である。帯域の項目は、通信経路に対して割当てが求められた帯域を記憶する領域である。図５の右側には、通信経路の送信元および送信先に対応させて、通信経路で確保したい帯域がマトリクス状に示されている。なお、「−」が設定された領域は、通信経路の設定がないことを示す。図５の例では、送信元「ノードＡ：１０ｘｘ」と宛先「ノードＢ：００ｘｘ」と間で確保したい帯域が「１０」Ｍｂｐｓであることを示す。また、図５の例では、送信元「ノードＡ：１０ｘｘ」と宛先「ノードＣ：０１ｘｘ」と間で確保したい帯域が「１０」Ｍｂｐｓであることを示す。また、図５の例では、送信元「ノードＣ：０１ｘｘ」と宛先「ノードＢ：００ｘｘ」と間で確保したい帯域が「１０」Ｍｂｐｓであることを示す。
【００３２】
図３に戻り、経路テーブル３２は、各ノードのパケットの転送する経路を定義したエントリ情報を記憶したデータである。例えば、経路テーブル３２には、エントリ情報ごとに、パケットの宛先に応じた出力先が記憶されている。
【００３３】
図６Ａ〜６Ｃは、経路テーブルのデータ構成の一例を示す図である。なお、本実施例では、説明を簡易化するため、経路テーブル３２には、エントリ情報として宛先に応じた出力先のみを示している。図６Ａは、ノードＡの経路テーブルの一例を示している。図６Ｂは、ノードＤの経路テーブルの一例を示している。図６Ｃは、ノードＣの経路テーブルの一例を示している。図６Ａ〜６Ｃに示すように、経路テーブル３２は、「Ｄｓｔ」、「ＩＦ」の各項目を有する。Ｄｓｔの項目は、パケットの宛先を記憶する領域である。ＩＦの項目は、パケットの出力先を記憶する領域である。経路テーブル３２は、それぞれのレコードがエントリ情報に対応する。図６Ａの例では、宛先「００ｘｘ」及び「０１ｘｘ」のパケットは、出力先がインタフェースｉｆ＿ａ１であることを示す。図６Ｂの例では、宛先「００ｘｘ」のパケットは、出力先がインタフェースｉｆ＿ｄ２であることを示す。また、宛先「０１ｘｘ」のパケットは、出力先がインタフェースｉｆ＿ｄ３であることを示す。図６Ｃの例では、宛先「００ｘｘ」のパケットは、出力先がインタフェースｉｆ＿ｃ１であることを示す。
【００３４】
図３に戻り、リンク帯域管理テーブル３３は、ノード間のリンクごとの帯域に関する情報を記憶したデータである。例えば、経路テーブル３２には、ノード間のリンクごとに使用された帯域および使用可能な帯域量が記憶されている。
【００３５】
図７は、リンク帯域管理テーブルのデータ構成の一例を示す図である。図７に示すように、リンク帯域管理テーブル３３は、「リンク」、「記録帯域」、「物理リンク速度」の各項目を有する。リンクの項目は、「ｆｒｏｍ」と「ｔｏ」の項目に分かれている。ｆｒｏｍの項目は、リンクでパケットの送信元となるノードを記憶する領域である。ｔｏの項目は、リンクでパケットの送信先となるノードを記憶する領域である。記録帯域の項目は、リンクを通過したパケットの帯域を積算した値を記憶する領域である。記録帯域の項目には、初期値として０がセットされる。物理リンク速度の項目は、使用可能な帯域量としてリンクの物理リンク速度を記憶する領域である。リンクの物理リンク速度は、例えば、リンクを構成するケーブルなどの通信速度の上限値が用いられる。図７の例では、ノードＡからノードＤへのリンクは、記録帯域が０Ｍｂｐｓであり、使用可能な帯域量が１００Ｍｂｐｓであることを示す。
【００３６】
図３に戻り、制御部２４は、経路テーブル検証装置１０を制御するデバイスである。制御部２４としては、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等の電子回路や、ＡＳＩＣ（Application  Specific  Integrated  Circuit）、ＦＰＧＡ（Field  Programmable  Gate  Array）等の集積回路を採用できる。制御部２４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部２４は、各種のプログラムが動作することにより各種の処理部として機能する。例えば、制御部２４は、取得部４０と、受付部４１と、生成部４２と、算出部４３と、経路検証部４４と、帯域検証部４５と、出力部４６とを有する。
【００３７】
取得部４０は、各種の取得を行う。例えば、取得部４０は、ＮＷ設計装置１１からデマンドの情報や各ノードの経路テーブルを取得する。取得する情報は、ＮＷ設計装置１１が自立的に送信してもよい。また、取得する情報は、取得部４０がＮＷ設計装置１１に対して送信を要求し、ＮＷ設計装置１１が要求に応じて送信してもよい。取得部４０は、取得した情報を記憶部２３へ格納する。例えば、取得部４０は、取得したデマンドの情報をデマンド情報３１に格納する。また、取得部４０は、取得した各ノードの経路テーブルを経路テーブル３２に格納する。
【００３８】
受付部４１は、各種の受け付けを行う。例えば、受付部４１は、各種の操作指示を受け付ける。例えば、受付部４１は、検証に関する操作画面を表示部２２に表示させて、入力部２１から、検証開始などの操作指示を受け付ける。なお、本実施例では、入力部２１から検証開始などの操作指示を受けるものとするが、他の装置に操作画面を表示させ、他の装置から遠隔で操作指示を受けてもよい。また、受付部４１は、ＮＷ設計装置１１からデマンドの情報や各ノードの経路テーブルを取得したことを検証開始の受け付けとしてもよい。
【００３９】
生成部４２は、各種の生成を行う。例えば、生成部４２は、デマンド情報３１に記憶された各デマンドに基づいて、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。例えば、生成部４２は、帯域情報を収容できるようにパケットのヘッダを拡張する。拡張する領域は、ヘッダの使用されない領域を用いてもよく、ヘッダに新たに領域を追加してもよい。生成部４２は、パケットヘッダを拡張して、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。
【００４０】
図８は、実施例１に係るパケットのヘッダの一例を示す図である。なお、本実施例では、説明を簡易化するため、パケットのヘッダの宛先、帯域のみを示している。Ｄｓｔは、宛先を示す。ｂｗは、帯域を示す。例えば、デマンド情報３１には、図５に示すデマンドが記憶されている。この場合、生成部４２は、送信元「ノードＡ：１０ｘｘ」、宛先「ノードＢ：００ｘｘ」、確保したい帯域「１０」Ｍｂｐｓに対応して、ヘッダのＤｓｔを「００ｘｘ」とし、ｂｗを「１０」としたパケット５０Ａを生成する。また、生成部４２は、送信元「ノードＡ：１０ｘｘ」、宛先「ノードＣ：０１ｘｘ」、確保したい帯域「１０」Ｍｂｐｓに対応して、ヘッダのＤｓｔを「０１ｘｘ」とし、ｂｗを「１０」としたパケット５０Ｂを生成する。また、生成部４２は、送信元「ノードＣ：０１ｘｘ」、宛先「ノードＢ：００ｘｘ」、確保したい帯域「１０」Ｍｂｐｓに対応して、ヘッダのＤｓｔを「００ｘｘ」とし、ｂｗを「１０」としたパケット５０Ｃを生成する。
【００４１】
なお、生成部４２は、送信元ノード情報、宛先ノード情報、送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成してもよい。例えば、生成部４２は、送信元ノード情報として、パケットの入口となる送信元のエッジノードを示す情報、送信元アドレスとして、送信元のエッジノードのアドレス、宛先ノード情報として、パケットの出口となる宛先のエッジノードを示す情報、送信元アドレスとして、送信元のエッジノードのアドレス、宛先アドレスとして、宛先のエッジノードのアドレスをヘッダに格納したパケットを生成してもよい。例えば、生成部４２は、送信元「ノードＡ：１０ｘｘ」、宛先「ノードＢ：００ｘｘ」、確保したい帯域「１０」Ｍｂｐｓに対応して、ヘッダの送信元ノード情報を送信元のノードである「Ａ」とし、宛先ノード情報を宛先のノードである「Ｂ」とし、Ｄｓｔを「００ｘｘ」とし、ｂｗを「１０」としたパケット５０Ａを生成してもよい。
【００４２】
また、生成部４２は、デマンド情報３１に記憶された何れのデマンドにも該当しないデマンド外のパケットを生成する。例えば、生成部４２は、デマンドに宛先アドレスとしてＤ１とＤ２がある場合、以下の（１）式に示すようにＤ１とＤ２の和の補集合のアドレスＤ０を宛先としたデマンド外のパケットを生成する。
【００４３】
【数１】
2016158232.tif 000003
【００４４】
算出部４３は、各種の算出を行う。例えば、算出部４３は、経路テーブル３２に基づいて、生成部４２により生成された各パケットの転送経路を算出する。例えば、算出部４３は、デマンドに対応するパケットを送信元のノードからネットワーク１４に入力し、各ノードの経路テーブル３２に従って、パケットの転送経路を算出する。また、算出部４３は、デマンド外のパケットを各エッジノードからネットワーク１４に入力し、各ノードの経路テーブル３２に従って、パケットの転送経路を算出する。
【００４５】
ここで、算出部４３が転送経路を算出する流れについてより詳細に説明する。例えば、算出部４３は、パケットを受信したノードごとに、受信したパケットのヘッダと、当該ノードの経路テーブル３２の各エントリ情報を順に比較し、該当するエントリ情報を検索する。例えば、算出部４３は、経路テーブル３２のエントリ情報を順に読み出す。そして、算出部４３は、パケットの宛先アドレスと読み出したエントリ情報の宛先アドレスとのビット演算を行う。図９は、ビット演算の一例を示す図である。例えば、算出部４３は、図９に示すビット演算表に従い、パケットの宛先アドレスと読み出したエントリ情報の宛先アドレスのビット演算を行う。算出部４３は、演算結果がｅｍｐｔｙを含むか否かを判定する。算出部４３は、演算結果がｅｍｐｔｙを含む場合、パケットの宛先アドレスがエントリ情報の宛先アドレスに該当しないので、次のエントリ情報と比較を行う。算出部４３は、演算結果がｅｍｐｔｙを含まない場合、パケットの宛先アドレスがエントリ情報の宛先アドレスに該当するので、該当したエントリ情報の出力先へパケットを出力する。一方、算出部４３は、パケットの宛先アドレスが何れのエントリ情報にも該当しない場合、パケットが転送されないため、経路無しとする。
【００４６】
算出部４３は、パケットがエッジノードから出力されるまで、または、経路無しとされてドロップするまで、パケットを受信したノードごとに、上述の処理を行って転送経路を算出する。
【００４７】
デマンドに対応するパケットは、各ノードの経路テーブル３２にデマンドに対応して正しく生成されている場合、デマンドの通信経路に沿って転送される。一方、デマンド外のパケットは、各ノードの経路テーブル３２が正しく生成されている場合、入力ポートでドロップする。よって、算出部４３によって算出されるパケットの転送経路からデマンドごとの転送経路を算出できる。
【００４８】
図１０Ａは、デマンドに対応するパケットの転送経路を算出した結果の一例を示す図である。図１０Ａには、パケット５０Ａ〜５０Ｃの転送経路を算出した結果が示されている。パケット５０Ａは、ノードＡから入力されて、ノードＤ、ノードＢへ転送される。パケット５０Ｂは、ノードＡから入力されて、ノードＤ、ノードＣへ転送される。パケット５０Ｃは、ノードＣから入力されて、ノードＤ、ノードＢへ転送される。
【００４９】
図１０Ｂは、デマンド外のパケットの転送経路を算出した結果の一例を示す図である。図１０Ｂには、ノードＡ、Ｂ、Ｃからそれぞれのデマンド外のパケットを入力した結果が示されている。図１０Ｂに示すようにデマンド外のパケットは、何れも経路が無く、ドロップとなる。
【００５０】
図１１は、転送経路の一例を示す図である。図１１に示すように、パケット５０Ａは、ノードＡからノードＤへ転送され、ノードＤからノードＢへ転送される。よって、パケット５０Ａに対応するデマンドの転送経路は、ノードＡ、ノードＤ、ノードＢと求まる。パケット５０Ｂは、ノードＡからノードＤへ転送され、ノードＤからノードＣへ転送される。よって、パケット５０Ｂに対応するデマンドの転送経路は、ノードＡ、ノードＤ、ノードＣと求まる。パケット５０Ｃは、ノードＣからノードＤへ転送され、ノードＤからノードＢへ転送される。よって、パケット５０Ｃに対応するデマンドの転送経路は、ノードＣ、ノードＤ、ノードＢと求まる。
【００５１】
経路検証部４４は、通信経路の整合性を検証する。例えば、経路検証部４４は、算出部４３により算出されたパケットの転送経路とデマンドの通信経路との整合性を検証する。例えば、経路検証部４４は、最終ノードに到達したパケットの送信元アドレスと宛先アドレスから、デマンドの通信経路との整合性を検証する。例えば、経路検証部４４は、最終ノードに到達したパケットの送信元アドレスと宛先アドレスをデマンドの送信元と宛先と比較し、一致する場合、通信経路との整合性が取れていると判定する。一方、経路検証部４４は、最終ノードに到達したパケットの送信元アドレスと宛先アドレスがデマンドの送信元と宛先と一致しない場合、通信経路との整合性が取れていないと判定する。最終ノードは、送信先アドレスに応じて転送経路を算出してパケットがネットワークのエッジノードに到達した場合、エッジノードとし、パケットが何れかでノードで転送されなくなる場合、転送されなくなったノードとする。後述するように、転送経路にループが発生していないかの検証を行う場合、ノード間を転送できる回数の上限を設けて、転送回数が上限に達したノードを最終ノードとしてもよい。ノード間を転送できる回数の上限は、ユーザが指定してもよく、検証対象のネットワークに応じて自動的定めてよい。例えば、ネットワークのエッジノード間のノード数の最大値の所定倍（例えば、２倍）を、ノード間を転送できる回数の上限としてもよい。整合性の検証は、アドレスまたはノードの情報のみ行ってもよく、アドレスおよびノードの情報を両方用いてもよい。例えば、経路検証部４４は、最終ノードに到達したパケットの送信元アドレスと宛先アドレスが、当該パケットに対応するデマンドの送信元アドレスと宛先アドレスに一致するか検証する。また、経路検証部４４は、パケットが到達した最終ノードとパケットを最初に入力した送信元のノードが、当該パケットに対応するデマンドの宛先ノードと送信元ノードに一致するか検証する。パケットに送信元ノード情報、宛先ノード情報が含まれる場合、経路検証部４４は、パケットが到達した最終ノードとパケットを最初に入力した送信元のノードが、パケットに含まれる送信元ノード情報のノードと宛先ノード情報のノードに一致するか検証してもよい。なお、経路検証部４４は、最終ノードに到達したパケットの送信元アドレスと宛先アドレスがデマンドの送信元と宛先の範囲内となる場合、通信経路との整合性が取れていると判定してもよい。経路検証部４４は、最終ノードに到達したパケットごとに、当該パケットの送信元アドレスと宛先アドレスから、デマンドの通信経路との整合性を検証する。
【００５２】
また、経路検証部４４は、通信経路の整合性として、転送経路にループが発生していないかを検証する。例えば、経路検証部４４は、算出部４３により算出されたパケットの転送経路にループが発生していないかを検証する。例えば、パケットの転送経路で通過したノードに再度出力される場合、ループが発生していると判定する。また、経路検証部４４は、通信経路の整合性として、デマンド外のパケットの通信経路が無いことを検証する。例えば、経路検証部４４は、デマンド外のパケットがネットワークの何れかのノードで転送されずにドロップしたかを検証する。
【００５３】
帯域検証部４５は、通信帯域の整合性を検証する。例えば、帯域検証部４５は、算出部４３による算出された転送経路とパケットの帯域情報から、ノード間のリンクごと帯域を積算してリンクの帯域量との整合性を検証する。例えば、帯域検証部４５は、算出部４３による算出においてパケットがノード間を転送されるごとに、リンク帯域管理テーブル３３のパケットが転送されたノード間のリンクの記録帯域の領域に、転送されたパケットの帯域の値を累計する。これにより、算出部４３による転送経路の算出が終了すると、リンク帯域管理テーブル３３には、リンクごとに、転送されたパケットの合計の帯域が記録される。
【００５４】
図１２は、リンク帯域管理テーブルの一例を示す図である。図１２の例は、パケット５０Ａ、５０Ｂ、５０Ｃの転送経路を算出した場合のリンクごとの合計の帯域を示している。ノードＡからノードＤへのリンクは、合計の帯域が２０Ｍｂｐｓと記録されている。
【００５５】
帯域検証部４５は、リンクごとに、記録された合計の帯域が、物理リンク速度の値以下であるか判定する。帯域検証部４５は、合計の帯域が、物理リンク速度の値以下の場合、通信帯域の整合性が取れていると判定する。一方、帯域検証部４５は、合計の帯域が、物理リンク速度の値よりも大きい場合、通信帯域の整合性が取れていないと判定する。
【００５６】
出力部４６は、各種の出力を行う。例えば、出力部４６は、経路検証部４４および帯域検証部４５の検証の結果を表示部２２に出力する。また、例えば、出力部４６は、経路検証部４４および帯域検証部４５の検証の結果の情報をＮＷ設計装置１１に出力して検証の結果を通知する。
【００５７】
経路テーブル検証装置１０から通知された検証結果に異常が無い場合、生成した各ノードの経路テーブルがＮＷ設計装置１１からＮＷ設定装置１２へ送信され、実際のネットワーク１４に適用される。
【００５８】
このように、システム１は、経路テーブル検証装置１０により各ノードの経路テーブルを検証することにより、ネットワーク１４の動作に不整合や想定外の事象が起きることを抑制できる。
【００５９】
［処理の流れ］
実施例１に係る経路テーブル検証装置１０が経路テーブルを検証する検証処理の流れについて説明する。図１３は、実施例１に係る検証処理の手順の一例を示すフローチャートである。この検証処理は、所定のタイミング、例えば、入力部２１から検証開始の操作指示を受け付けたタイミングで実行される。
【００６０】
図１３に示すように、生成部４２は、デマンド情報３１に記憶された各デマンドに基づいて、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する（Ｓ１０）。算出部４３は、生成されたパケットのうち、１つのパケットを検証対象のパケットと選択する（Ｓ１１）。
【００６１】
算出部４３は、検証対象のパケットの転送経路の算出する転送経路算出処理を実行する（Ｓ１２）。
【００６２】
図１４は、実施例１に係る転送経路算出処理の手順の一例を示すフローチャートである。この転送経路算出処理は、例えば、検証処理のＳ１２から実行される。
【００６３】
図１４に示すように、算出部４３は、検証対象のパケットの送信元のノードに検証対象のパケットを入力する（Ｓ５０）。算出部４３は、変数ｉを１に初期化する（Ｓ５１）。算出部４３は、パケットを受信したノードの経路テーブル３２から変数ｉ番目のエントリ情報を読み出す（Ｓ５２）。算出部４３は、検証対象のパケットの宛先アドレスと読み出したエントリ情報の宛先アドレスとのビット演算を行う（Ｓ５３）。
【００６４】
算出部４３は、演算結果がｅｍｐｔｙを含むかどうかを判定する（Ｓ５４）。演算結果がｅｍｐｔｙを含む場合（Ｓ５４肯定）、算出部４３は、変数ｉの値を１加算する（Ｓ５５）。そして、算出部４３は、パケットを受信したノードの経路テーブル３２に変数ｉ番目のエントリ情報があるか否かを判定する（Ｓ５６）。変数ｉ番目のエントリ情報がある場合（Ｓ５６肯定）、上述のＳ５２へ移行する。
【００６５】
一方、変数ｉ番目のエントリ情報がない場合（Ｓ５６否定）、算出部４３は、パケットの転送先がないため、経路無しとして（Ｓ５７）、転送経路算出処理を終了し、検証処理のＳ１３へ移行する。
【００６６】
一方、演算結果がｅｍｐｔｙを含まない場合（Ｓ５４否定）、算出部４３は、エントリ情報の出力先へ検証対象のパケットを出力する（Ｓ５８）。
【００６７】
帯域検証部４５は、リンク帯域管理テーブル３３の検証対象のパケットが転送されたノード間のリンクの記録帯域の領域に、検証対象のパケットの帯域の値を累計する（Ｓ５９）。
【００６８】
算出部４３は、検証対象のパケットがエッジノードから出力されたか否かを判定する（Ｓ６０）。検証対象のパケットがエッジノードから出力された場合（Ｓ６０肯定）、転送経路算出処理を終了し、検証処理のＳ１３へ移行する。
【００６９】
一方、検証対象のパケットがエッジノードから出力されていない場合（Ｓ６０否定）、算出部４３は、上述のＳ５１へ移行して検証対象のパケットが入力したノードについての経路の算出処理を実行する。
【００７０】
図１３に戻り、算出部４３は、生成された全てのパケットについて転送経路算出処理を実行したか否かを判定する（Ｓ１３）。全てのパケットについて転送経路算出処理を実行していない場合（Ｓ１３否定）、上述のＳ１１へ移行する。
【００７１】
一方、全てのパケットについて転送経路算出処理を実行した場合（Ｓ１３肯定）、経路検証部４４は、生成された各パケットの転送経路とデマンドの通信経路との整合性を検証する（Ｓ１４）。帯域検証部４５は、リンク帯域管理テーブル３３に記録されたリンクごとの合計の帯域を物理リンク速度と比較して、リンクごとに帯域の整合性を検証する（Ｓ１５）。
【００７２】
出力部４６は、経路検証部４４および帯域検証部４５の検証の結果の情報をＮＷ設計装置１１に出力し（Ｓ１６）、処理を終了する。
【００７３】
［効果］
上述してきたように、本実施例に係る経路テーブル検証装置１０は、ネットワーク１４に対して通信経路および帯域の割当てを求めたデマンドに基づいて、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。経路テーブル検証装置１０は、ネットワーク１４の各ノードの経路テーブルに基づいて、生成されたパケットの転送経路を算出する。経路テーブル検証装置１０は、算出により最終ノードに到達したパケットの送信元アドレスと宛先アドレスから、デマンドの通信経路との整合性を検証する。経路テーブル検証装置１０は、算出された転送経路とパケットの帯域情報から、ノード間のリンクごと帯域を積算してリンクの帯域量との整合性を検証する。これにより、経路テーブル検証装置１０は、ネットワークの経路と帯域を検証できる。
【００７４】
また、本実施例に係る経路テーブル検証装置１０は、デマンドごとに、当該デマンドの通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。経路テーブル検証装置１０は、生成されたパケットごとに、転送経路を算出する。経路テーブル検証装置１０は、最終ノードに到達したパケットごとに、当該パケットの送信元アドレスと宛先アドレスから、デマンドの通信経路との整合性を検証する。経路テーブル検証装置１０は、ノード間のリンクごとに、リンクを通過するパケットの帯域を積算してリンクの帯域量との整合性を検証する。これにより、経路テーブル検証装置１０は、デマンドごとに、ネットワークの経路と帯域を検証できる。
【実施例２】
【００７５】
次に、実施例２ついて説明する。実施例２に係るシステム１および経路テーブル検証装置１０の構成は、図２、図３に示した実施例１と同様であるため、主に異なる部分について説明する。
【００７６】
実施例２では、生成部４２は、送信元が同じノードとなるデマンドごとに、各デマンドを集約したヘッダのパケットを生成する。例えば、生成部４２は、送信元が同じノードごとに、各デマンドの送信元アドレスと宛先アドレスを集約した集約型デマンドヘッダと、各デマンドの送信元アドレス、宛先アドレス、帯域情報をデマンドリストとして含んだパケットを生成する。より具体的には、生成部４２は、帯域情報を収容できるようにパケットのヘッダを拡張する。拡張する領域は、ヘッダの使用されない領域を用いてもよく、ヘッダに新たに領域を追加してもよい。生成部４２は、各デマンドの送信元アドレスの論理和となる集約した送信元アドレスと、各デマンドの宛先アドレスの論理和となる集約した宛先アドレスとを求める。そして、生成部４２は、集約型デマンドヘッダとして集約した送信元アドレスおよび宛先アドレスと、デマンドリストとして各デマンドの送信元アドレス、宛先アドレスおよび帯域情報とが付されたパケットを生成する。
【００７７】
図１５は、実施例２に係るパケットのヘッダの構成の一例を示す図である。図１５に示すように、パケットのヘッダは、集約型デマンドヘッダとして、集約した送信元アドレスおよび宛先アドレスを記憶する領域と、デマンドリストとして、各デマンドの送信元アドレス、宛先アドレスおよび帯域情報を記憶する領域を有する。
【００７８】
図１６は、実施例２に係るパケットのヘッダの一例を示す図である。なお、本実施例では、説明を簡易化するため、パケットのヘッダの宛先、帯域のみを示している。例えば、デマンド情報３１には、図５に示すデマンドが記憶されている。この場合、生成部４２は、ノードＡが送信元となる２つのデマンドを集約したパケット６０Ａを生成する。例えば、生成部４２は、集約型デマンドヘッダとして宛先アドレス「０ｘｘｘ」と、デマンドリストとして宛先「００ｘｘ」、帯域「１０」Ｍｂｐ、宛先「０１ｘｘ」、帯域「１０」Ｍｂｐｓを含んだパケット６０Ａを生成する。また、生成部４２は、ノードＣが送信元となる１つのデマンドからパケット６０Ｂを生成する。例えば、生成部４２は、集約型デマンドヘッダとして宛先アドレス「００ｘｘ」と、デマンドリストとして宛先「００ｘｘ」、帯域「１０」Ｍｂｐｓを含んだパケット６０Ｂを生成する。
【００７９】
また、生成部４２は、実施例１と同様に、デマンド情報３１に記憶された何れのデマンドにも該当しないデマンド外のパケットを生成する。
【００８０】
算出部４３は、経路テーブル３２に基づいて、生成部４２により生成された各パケットの転送経路を算出する。算出部４３は、複数のデマンドを集約していないパケットについては実施例１と同様に、転送経路を算出する。
【００８１】
一方、算出部４３は、複数のデマンドを集約したパケットについては、パケットを受信したノードごとに、受信したパケットの集約型デマンドヘッダと、当該ノードの経路テーブル３２の各エントリ情報を順に比較し、該当するエントリ情報を検索する。例えば、算出部４３は、経路テーブル３２のエントリ情報を順に読み出す。そして、算出部４３は、パケットの集約した宛先アドレスと読み出したエントリ情報の宛先アドレスとのビット演算を行う。ここで、集約した宛先アドレスは、各デマンドの宛先アドレスの論理和である。このため、エントリ情報に何れのデマンドの宛先アドレスが該当する場合、集約した宛先アドレスも該当する。
【００８２】
算出部４３は、演算結果がｅｍｐｔｙを含むか否かを判定する。算出部４３は、演算結果がｅｍｐｔｙを含む場合、パケットの宛先アドレスがエントリ情報の宛先アドレスに該当しないので、次のエントリ情報と比較を行う。このように、算出部４３は、最初に、集約した宛先アドレスを用いて該当するエントリ情報を検索する。これにより、算出部４３は、デマンドリストの各宛先アドレスがエントリ情報に該当するかを個々に検索する場合と比較して、該当するエントリ情報かを速やかに検索できる。
【００８３】
算出部４３は、演算結果がｅｍｐｔｙを含まない場合、デマンドリストの各宛先アドレスをエントリ情報の宛先アドレスと比較して、該当する宛先アドレスを求める。例えば、算出部４３は、デマンドリストの各宛先アドレスをそれぞれエントリ情報の宛先アドレスとビット演算を行い、演算結果がｅｍｐｔｙを含まない宛先アドレスを求める。
【００８４】
算出部４３は、エントリ情報からデマンドリストの各デマンドの宛先アドレスに対応する出力先を求める。そして、算出部４３は、出力先ごとに、ヘッダを書替えるとともに関連するデマンドのみをヘッダに残し、エントリ情報で指定された出力先へパケットを出力する。例えば、算出部４３は、出力先ごとに、出力先が同じ各デマンドの送信元アドレスと宛先アドレスを集約した集約型デマンドヘッダと、各デマンドの送信元アドレス、宛先アドレス、帯域情報をデマンドリストとして含んだパケットを生成し、出力先へ出力する。算出部４３は、ノードごとに、上述の処理を順次繰り返して転送経路を算出する。
【００８５】
図１７は、転送経路を算出した結果の一例を示す図である。図１７には、パケット６０Ａ、６０Ｂの転送経路を算出した結果が示されている。パケット６０Ａは、ノードＡから入力されて、ノードＤへ転送され、ノードＤで出力先となるノードＢ、ノードＣごとにパケット６０Ｃ、６０Ｄが生成され、それぞれ転送される。一方、パケット６０Ｂは、ノードＣから入力されて、ノードＤ、ノードＢへ転送される。エッジノードに転送されたパケットのヘッダのデマンドリストに含まれる各デマンドの送信元アドレスと宛先アドレスから、デマンドごとに転送経路が求まる。
【００８６】
図１８は、転送経路の一例を示す図である。図１８に示すように、Ｓｒｃ（送信元）：１０ＸＸ、Ｄｓｔ（宛先）：００ＸＸのデマンドの転送経路は、ノードＡ、ノードＤ、ノードＢと求まる。Ｓｒｃ：１０ＸＸ、Ｄｓｔ：０１ＸＸのデマンドの転送経路は、ノードＡ、ノードＤ、ノードＣと求まる。Ｓｒｃ：０１ＸＸ、Ｄｓｔ：００ＸＸのデマンドの転送経路は、ノードＣ、ノードＤ、ノードＢと求まる。
【００８７】
このように複数のデマンドを集約した集約型デマンドヘッダと、デマンドリストがパケットに追加した場合、算出部４３は、複数のデマンドに対応する転送経路をまとめて算出できる。これにより、デマンドごとのパケットから転送経路を算出する場合と比べて、各デマンドに対応した転送経路を速やかに算出できる。
【００８８】
経路検証部４４は、算出部４３により算出されたパケットの転送経路とデマンドの通信経路との整合性を検証する。また、経路検証部４４は、転送経路にループが発生していないかを検証する。
【００８９】
帯域検証部４５は、パケットがノード間を転送されるごとに、リンク帯域管理テーブル３３のパケットが転送されたノード間のリンクの記録帯域の領域に、転送されたパケットの各デマンドの帯域の値を累計する。これにより、複数のデマンドに対応する転送経路をまとめて算出する場合でも、図１２に示したように、リンクごとに、合計の帯域が記録できる。帯域検証部４５は、リンクごとに、記録された合計の帯域が、物理リンク速度の値以下であるか判定する。
【００９０】
［処理の流れ］
実施例２に係る経路テーブル検証装置１０が経路テーブルを検証する検証処理の流れについて説明する。図１９は、実施例２に係る検証処理の手順の一例を示すフローチャートである。なお、上述の実施例１に係る検証処理と同一の部分については、同一の符号を付してその説明を省略する。
【００９１】
図１９に示すように、生成部４２は、送信元が同じノードとなるデマンドごとに、各デマンドを集約したヘッダのパケットを生成する（Ｓ１００）。例えば、生成部４２は、送信元が同じノードごとに、各デマンドの送信元アドレスと宛先アドレスを集約した集約型デマンドヘッダと、各デマンドの送信元アドレス、宛先アドレス、帯域情報をデマンドリストとして含んだパケットを生成する。
【００９２】
図２０は、実施例２に係る転送経路算出処理の手順の一例を示すフローチャートである。なお、上述の実施例１に係る転送経路算出処理と同一の部分については、同一の符号を付してその説明を省略する。
【００９３】
図２０に示すように、算出部４３は、検証対象のパケットの集約型デマンドヘッダと、
読み出したエントリ情報の宛先アドレスとのビット演算を行う（Ｓ１５３）。
【００９４】
そして、演算結果がｅｍｐｔｙを含まない場合（Ｓ５４否定）、算出部４３は、デマンドリストの各宛先アドレスをエントリ情報の宛先アドレスと比較して、該当する宛先アドレスを求める（Ｓ１５８）。算出部４３は、エントリ情報からデマンドリストの各デマンドの宛先アドレスに対応する出力先を求める（Ｓ１５９）。算出部４３は、出力先ごとに、出力先が同じ各デマンドの送信元アドレスと宛先アドレスを集約した集約型デマンドヘッダと、各デマンドの送信元アドレス、宛先アドレス、帯域情報をデマンドリストとして含んだパケットを生成し、出力先へ出力する（Ｓ１６０）。
【００９５】
帯域検証部４５は、リンク帯域管理テーブル３３のパケットが転送されたノード間のリンクの記録帯域の領域に、転送されたパケットの各デマンドの帯域の値を累計する（Ｓ１６１）。
【００９６】
［効果］
上述してきたように、本実施例に係る経路テーブル検証装置１０は、各デマンドの通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報を含んだパケットを生成する。経路テーブル検証装置１０は、ノードごとに、当該ノードの経路テーブルに基づいて、パケットに含まれる各デマンドの送信先アドレスに対応する転送先を識別する。経路テーブル検証装置１０は、転送先ごとに、当該転送先と識別されたデマンドの送信元アドレス、宛先アドレス、帯域情報を含んだパケットを転送して転送経路を算出する。経路テーブル検証装置１０は、ノード間のリンクごとに、リンクを通過するパケットに含まれる各帯域を積算してリンクの帯域量との整合性を検証する。これにより、経路テーブル検証装置１０は、各デマンドの経路と帯域を速やかに検証できる。
【実施例３】
【００９７】
次に、実施例３ついて説明する。実施例３に係るシステム１の構成は、図２に示した実施例１および実施例２と同様であるため、説明を省略する。本実施例に係る経路テーブル検証装置１０の構成について説明する。図２１は、経路テーブル検証装置の機能的な構成の一例を示す図である。実施例３に係る経路テーブル検証装置１０の構成は、図２、図３に示した実施例１および実施例２と一部が同一であるため、同一の部分については、同一の符号を付し、主に異なる部分について説明する。
【００９８】
実施例３に係る経路テーブル検証装置１０の制御部２４は、変換部４７をさらに有する。
【００９９】
生成部４２は、デマンド情報３１に記憶された各デマンドに基づいて、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。また、生成部４２は、デマンド情報３１に記憶された何れのデマンドにも該当しないデマンド外のパケットを生成する。例えば、生成部４２は、デマンドで割当てが求められた通信経路のアドレスの和の補集合となるアドレスのデマンド外のパケットを生成する。デマンドの通信経路のアドレスは、送信元アドレスと宛先アドレスの両方を用いてもよい。また、通信経路のアドレスは、送信元アドレスまたは宛先アドレスの一方のみを用いてもよい。例えば、生成部４２は、送信元アドレスと宛先アドレスを通信経路のアドレスとして、アドレスの和の補集合となるアドレスの範囲を表す複数のアドレスを求める。補集合となる複数のアドレスは、範囲が一部重複してもよい。そして、生成部４２は、求めたアドレスをそれぞれアドレスとした複数のデマンド外のパケットを生成する。例えば、生成部４２は、求めたアドレスの送信元アドレス、宛先アドレスの範囲をそれぞれ送信元アドレス、宛先アドレスとしたデマンド外のパケットを生成する。
【０１００】
ところで、デマンド情報３１に記憶された各デマンドのアドレスのアドレス空間（ヘッダ空間）内での配置が離散的である場合、各デマンドのアドレスの和の補集合のアドレスの範囲を表すアドレス数が多くなる。デマンド外のパケットは、補集合のアドレスの範囲を表すアドレスごとに生成される。このため、アドレスの範囲を表すアドレス数が多くなると、デマンド外のパケットの数も多くなる。デマンド外の検証では、デマンド外のパケットごとに転送経路の算出が行われる。このため、デマンド外のパケットの数が多くなると、デマンド外の検証にかかる検証時間の増大を招いてしまう。以下では、送信元アドレスと宛先アドレスをそれぞれ３ビットとし、デマンドのアドレスを「送信元アドレス３ビット  宛先アドレス３ビット」の６ビットで表した例を用いて説明する。なお、送信元アドレスと宛先アドレスはそれぞれ３ビットに限定されるものではない。例えば、デマンドのアドレスが「０００  ＸＸＸ」、「１１１  ＸＸＸ」の２つである場合、デマンド外を表現するには、「Ｘ０１  ＸＸＸ」、「Ｘ１０  ＸＸＸ」、「０１１  ＸＸＸ」、「１００  ＸＸＸ」の４個になる。「Ｘ」は、「０」、「１」の何れもよいワイルドカードを示す。ワイルドカードＸは、don't  care  bitとも称される。デマンド外を表現する４つのアドレスは、マージすることができず、これより少ない数でデマンド外のアドレスの範囲を表すことができない。
【０１０１】
デマンド外のパケットは、ネットワークで中継されないことがネットワークの正常動作である。しかし、デマンド外のパケットは、ネットワークの入力されたエッジノードでドロップするとは限らず、ネットワークの内部の中継ノードでドロップしてもよい。このように、デマンド外のパケットが中継ノードでドロップする場合、デマンド外の検証に要する時間が大きくなる。また、デマンド外の検証は、すべてのエッジノードから、デマンド外のパケットを入力して行われる。このため、外部ポート数が増えれば、デマンド外の検証に要する時間が大きくなる。そこで、実施例３に係る経路テーブル検証装置１０は、各デマンドのアドレスの和の補集合となるデマンド外のアドレスの範囲を少ないアドレスで表せるようにアドレスの変換を行う。
【０１０２】
変換部４７は、各種の変換を行う、例えば、変換部４７は、デマンド情報３１に複数のデマンドが記憶されている場合、各デマンドの通信経路のアドレスを隣接するアドレス空間となるように変換する。例えば、変換部４７は、アドレス空間において、ワイルドカードＸの数が同一のアドレスを隣接し、アドレス空間でアドレスが連続する変換先のアドレスがあるか否かを判定する。変換先のアドレスがある場合、変換部４７は、変換先のアドレスに各デマンドのアドレスを変換する。
【０１０３】
図２２は、アドレスの変換を模式的に示した図である。図２２は、アドレスを所定ビット単位でそれぞれを軸としたｎ次元のアドレス空間に、アドレスが示す範囲を示したものである。図２２では、アドレス空間を３次元として模式的に示している。なお、アドレス空間は、アドレスの各ビットをそれぞれ軸とした空間としてもよい。図２２の左側には、３つのデマンドのアドレスＤ１〜Ｄ３に対応して、アドレス空間の領域Ｄ１〜Ｄ３が示されている。図２２の左側では、領域Ｄ１〜Ｄ３は、離れている。例えば、変換部４７は、各アドレスの領域Ｄ１〜Ｄ３が隣接するように変換する。図２２の右側には、各アドレスの領域Ｄ１〜Ｄ３を隣接するように変換した結果の一例が示されている。
【０１０４】
変換部４７は、各デマンドのアドレスの平行移動、ビットシフトを行って、各デマンドのアドレスを隣接する空間に移動するよう変換を行う。例えば、変換部４７は、何れのデマンドのアドレスにも該当しない空きのアドレスのなかから、アドレスの和を求めた場合にワイルドカードＸで表記されるビット数が多くなるようなアドレスを求める。例えば、変換部４７は、ワイルドカードＸの数が同一の複数のデマンドのアドレスについて、ワイルドカードＸの位置を同じにして、ワイルドカードＸ以外で１ビットだけ異なるように隣接させることが可能な変換先のアドレスをそれぞれ求める。変換部４７は、変換先のアドレスに各デマンドのアドレスを変換する。ワイルドカードＸ以外で１ビットだけ異なるアドレスは、アドレスの和を求めた場合、異なる１ビットをワイルドカードＸで表すことで、１つのアドレスで表すことができる。なお、変換部４７は、一部または全部のアドレスが、ワイルドカードＸで表記されるビット数が多くなるような状態である場合、当該一部または全部のアドレスについてはアドレスの変換を行わなくもよい。このように、変換部４７は、ワイルドカードＸで表記されるビット数が多くなるように、各デマンドのアドレスを隣接する空間に変換する。
【０１０５】
平行移動の一例を示す。例えば、２つのデマンドのアドレスについて、Ｘの数および位置が同じ場合、変換部４７は、一方のアドレスを他のアドレスの隣接するアドレス空間に移動する。これにより、変換後の２つのアドレスのアドレス空間は、１つのアドレスで表現できる。なお、変換部４７は、移動先の領域が他のデマンドのアドレスの領域ではない場合に移動を行う。
【０１０６】
図２３Ａは、平行移動の一例を示す図である。図２３Ａの例では、２つのデマンドのアドレスＤ１、Ｄ２として、「Ｄ１：０００  ＸＸＸ」と、「Ｄ２：１１１  ＸＸＸ」が示されている。この場合、変換部４７は、アドレスＤ２をアドレス空間で平行移動して、アドレスＤ１の隣接となるようにアドレスＤ２´に変換する。例えば、変換部４７は、「Ｄ２：１１１  ＸＸＸ」を「Ｄ２´：００１  ＸＸＸ」に変換する。アドレスＤ１とアドレスＤ２´の和は、００Ｘ  ＸＸＸと表せる。
【０１０７】
次に、ビットシフトの一例を示す。例えば、２つのデマンドのアドレスについて、Ｘの数が同じで、位置が異なる場合、変換部４７は、一方のアドレスのＸの位置を、他方のアドレスと一致するようにビットをシフトし、さらにこれを平行移動する。この場合も、変換後の２つのアドレスのアドレス空間は、１つのアドレスで表現できる。なお、変換部４７は、最終的な移動先の領域が他のデマンドのアドレスの領域ではない場合にシフトや平行移動を行う。
【０１０８】
図２３Ｂは、ビットシフトの一例を示す図である。図２３Ｂの例では、２つのデマンドのアドレスＤ１、Ｄ２として、「Ｄ１：０００  ＸＸＸ」と、「Ｄ２：１Ｘ１  Ｘ１Ｘ」が示されている。この場合、変換部４７は、アドレスＤ２をアドレス空間でビットシフトして、アドレスＤ１とＸの位置が同じなるようにアドレスＤ２´に変換する。例えば、変換部４７は、「Ｄ２：１Ｘ１  Ｘ１Ｘ」の先頭から４ビット目のＸを５ビット目の１と入れ替え、先頭から２ビット目のＸを４ビット目の位置まで右隣のビットと入れ替える。なお、変換部４７は、「Ｄ２：１Ｘ１  Ｘ１Ｘ」の先頭から２ビット目のＸを５ビット目の１と入れ替えてＸの位置が同じとしてもよい。そして、変換部４７は、アドレスＤ２´をアドレス空間で平行移動して、アドレスＤ１の隣接となるようにアドレスＤ２´´に変換する。例えば、変換部４７は、「Ｄ２´：１１１  ＸＸＸ」を「Ｄ２´´：００１  ＸＸＸ」に変換する。アドレスＤ１とアドレスＤ２´´の和は、「００Ｘ  ＸＸＸ」と表せる。
【０１０９】
変換部４７は、各デマンドのアドレスの変換に対応させて、各ノードの経路テーブル３２のアドレスを変換する。例えば、変換部４７は、経路テーブル３２の送信元アドレス、宛先アドレスに、デマンドで変換したアドレスがある場合、経路テーブル３２の送信元アドレス、宛先アドレスをデマンドで変換したアドレスに変換する。
【０１１０】
生成部４２は、各デマンドの変換されたアドレスに基づいて、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。例えば、生成部４２は、各デマンドの変換されたアドレスの和のアドレスの送信元アドレス、宛先アドレスをそれぞれ送信元アドレス、宛先アドレスとするパケットを生成する。
【０１１１】
また、生成部４２は、各デマンドの変換されたアドレス何れにも該当しないデマンド外のパケットを生成する。例えば、生成部４２は、各デマンドのアドレスの和の補集合となるアドレスをアドレスとしたデマンド外のパケットを生成する。例えば、生成部４２は、各デマンドのアドレスの補集合となるアドレスの送信元アドレス、宛先アドレスの範囲を網羅する複数のデマンド外のパケットを生成する。
【０１１２】
ところで、各デマンドのアドレスを隣接させても、各デマンドのアドレスの和が、複数のアドレスで表される場合がある。例えば、平行移動またはビットシフト後のアドレスの数が２n（ｎは１以上の自然数）でない場合は、アドレスの和が、複数のアドレスで表される。このように、アドレスの和が複数のアドレスとなる場合、和の補集合を求めると表現式の数が多くなる可能性がある。
【０１１３】
例えば、アドレスの数が２n個の場合は、アドレスの和を１つの表現形式で表せる。図２４Ａは、デマンド外のパケットのアドレスの求め方の一例を示す図である。図２４Ａの例は、２つのデマンドのアドレスＤ１、Ｄ２として、「Ｄ１：０００  ＸＸＸ」と、「Ｄ２：００１  ＸＸＸ」が示されている。このアドレスＤ１、Ｄ２の和（Ｄ１＋Ｄ２）は、「００Ｘ  ＸＸＸ」と１つのアドレスで表せる。このアドレスＤ１、Ｄ２の和の補集合は、「１ＸＸ  ＸＸＸ」＋「Ｘ１Ｘ  ＸＸＸ」となる。
【０１１４】
一方、アドレスの数が２n個ではない場合は、アドレスの和の表現形式が複数のアドレスによるものとなる。図２４Ｂは、デマンド外のパケットのアドレスの求め方の一例を示す図である。図２４Ｂの例は、３つのデマンドのアドレスＤ１、Ｄ２、Ｄ３として、「Ｄ１：０００  ＸＸＸ」と、「Ｄ２：００１  ＸＸＸ」と、「Ｄ３：０１０  ＸＸＸ」が示されている。このアドレスＤ１、Ｄ２、Ｄ３の和（Ｄ１＋Ｄ２＋Ｄ３）は、「００Ｘ  ＸＸＸ」および「０１０  ＸＸＸ」となる。
【０１１５】
そこで、生成部４２は、各デマンドのアドレスの和を示すアドレスが、ワイルドカードＸを用いた場合に１つのアドレスとなるように補完する補完アドレスを求める。例えば、図２４Ｂの場合、生成部４２は、補完アドレスとして、「Ｚ４：０１１  ＸＸＸ」を求める。アドレスＤ１、Ｄ２、Ｄ３、Ｚ４の和（Ｄ１＋Ｄ２＋Ｄ３＋Ｚ４）は、「０ＸＸ  ＸＸＸ」と１つのアドレスで表せる。このアドレスＤ１、Ｄ２、Ｄ３、Ｚ４の和の補集合は、「１ＸＸ  ＸＸＸ」となる。
【０１１６】
図２５は、アドレス空間でのアドレスと補完アドレスを模式的に示した図である。図２５には、アドレスＤ１〜Ｄ３と補完アドレスＺ４に対応して、アドレス空間の領域Ｄ１〜Ｄ３、Ｚ４が示されている。領域Ｄ１〜Ｄ３の和の領域は、アドレス空間内で凹凸部分があり、１つの表現形式で表すことができない。生成部４２は、この凹凸部分を埋めて、アドレス空間内で全ての軸に対して、それぞれ対向する２つの面で構成された領域となるように補完アドレスを求める。例えば、図２５の例では、生成部４２は、領域Ｄ１〜Ｄ３、Ｚ４が、各軸に対して、それぞれ対向する２つの面で構成された直方体となるように補完アドレスＺ４を求める。
【０１１７】
生成部４２は、デマンドのアドレスの数が２n個の場合、アドレスが変換された各デマンドのアドレスの和の補集合となるアドレスをアドレスとしたデマンド外のパケットを生成する。例えば、生成部４２は、各デマンドのアドレスの補集合となるアドレスの送信元アドレス、宛先アドレスの範囲を網羅する複数のデマンド外のパケットを生成する。図２４Ａの場合、生成部４２は、送信元アドレスと宛先アドレスを「１ＸＸ  ＸＸＸ」、「Ｘ１Ｘ  ＸＸＸ」とした２つのデマンド外のパケットを生成する。
【０１１８】
一方、生成部４２は、デマンドのアドレスの数が２n個ではない場合、アドレスが変換された各デマンドのアドレスの和を示すアドレスが、ワイルドカードＸを用いた場合に１つのアドレスとなるように補完する補完アドレスを求める。そして、生成部４２は、補完アドレスと各デマンドのアドレスとの和の補集合となるアドレスおよび補完アドレスをアドレスとしたデマンド外のパケットを生成する。図２４Ｂの場合、生成部４２は、アドレスＤ１〜Ｄ３に対して、補完アドレスＺ４を求める。そして、生成部４２は、送信元アドレスと宛先アドレスを、各デマンドのアドレスとの和の補集合となるアドレス「１ＸＸ  ＸＸＸ」、補完アドレスＺ４「０１１  ＸＸＸ」とした２つのデマンド外のパケットを生成する。
【０１１９】
算出部４３は、変換部４７によりアドレスが変換された経路テーブル３２に基づいて、生成部４２により生成された各パケットの転送経路を算出する。例えば、算出部４３は、デマンドに対応するパケットを送信元のノードからネットワーク１４に入力し、各ノードの経路テーブル３２に従って、パケットの転送経路を算出する。また、算出部４３は、デマンド外のパケットを各エッジノードからネットワーク１４に入力し、各ノードの経路テーブル３２に従って、パケットの転送経路を算出する。
【０１２０】
経路検証部４４は、算出部４３により算出されたパケットの転送経路と、アドレスが変換されたデマンドの通信経路との整合性を検証する。例えば、経路検証部４４は、最終ノードに到達したパケットの送信元アドレスと宛先アドレスから、アドレスが変換されたデマンドの通信経路との整合性を検証する。
【０１２１】
また、経路検証部４４は、通信経路の整合性として、デマンド外のパケットの通信経路が無いことを検証する。例えば、経路検証部４４は、デマンド外のパケットがネットワーク１４の何れかのノードで転送されずにドロップしたかを検証する。
【０１２２】
図２６は、検証環境の変換を模式的に示した図である。図２６の上部には、アドレスを変換する前のネットワークの検証環境が模式的に示されている。図２６の例は、ノードＡ〜Ｆによるネットワークが示されている。ノードＡ〜Ｃは、エッジノードとなっている。ノードＡは、ＩＰアドレスが「ＩＰ＿ａ」とする。ノードＢは、ＩＰアドレスが「ＩＰ＿ｂ」とする。ノードＣは、ＩＰアドレスが「ＩＰ＿ｃ」とする。図２６には、３つのデマンドＡ〜Ｃが示されている。デマンドＡは、送信元アドレスがＩＰ＿ｂ、宛先アドレスがＩＰ＿ｃとされている。デマンドＢは、送信元アドレスがＩＰ＿ｃ、宛先アドレスがＩＰ＿ａとされている。デマンドＣは、送信元アドレスがＩＰ＿ａ、宛先アドレスがＩＰ＿ｂとされている。ネットワーク設計では、デマンドに従い、経路設計が行われる。例えば、ネットワーク設計では、デマンドＡ〜Ｃに従い、ノードＡ〜Ｆの経路テーブルＴａ〜Ｔｆが生成される。本実施例に係るシステム１では、経路テーブルＴａ〜Ｔｆを実際のネットワークに適用する前に、生成された経路テーブルＴａ〜Ｔｆの妥当性の検証をソフトウェア上で行う。例えば、経路テーブル検証装置１０は、デマンドＡ〜Ｃに基づいて、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成して、デマンドの通信経路を検証する。また、経路テーブル検証装置１０は、デマンドＡ〜Ｃの通信経路のアドレスの補集合となるアドレスのデマンド外のパケットを生成して、デマンド外の通信経路を検証する。しかし、各デマンドのアドレスのアドレス空間内での配置が離散的である場合、生成されるデマンド外のパケット数が多くなる。
【０１２３】
そこで、本実施例に係る経路テーブル検証装置１０では、変換部４７が、デマンドのアドレスを隣接するように変換する。図２６の例では、ＩＰアドレス「ＩＰ＿ａ」がＩＰアドレス「ＩＰ＿ａ´」に変換され、ＩＰアドレス「ＩＰ＿ｂ」がＩＰアドレス「ＩＰ＿ｂ´」に変換され、ＩＰアドレス「ＩＰ＿ｃ」がＩＰアドレス「ＩＰ＿ｃ´」に変換されている。図２６の例では、このアドレスの変換を変換ｆとして示している。
【０１２４】
生成部４２は、各デマンドの変換されたアドレスに基づいて、通信経路および帯域に対応する送信元アドレス、宛先アドレス、帯域情報が付されたパケットを生成する。例えば、生成部４２は、各デマンドの変換されたアドレスの和のアドレスの送信元アドレス、宛先アドレスを送信元アドレス、宛先アドレスとするパケットを生成する。
【０１２５】
変換部４７は、各デマンドのアドレスの変換ｆに対応させて、各ノードの経路テーブル３２のアドレスを変換する。図２６の例では、ノードＡ〜Ｆの経路テーブルＴａ〜Ｔｆが経路テーブルＴａ´〜Ｔｆ´に変換されている。経路テーブル検証装置１０は、このような変換ｆを施した後、変換後の検証環境で検証を行う。
【０１２６】
次に、具体例を用いて経路テーブルの検証を説明する。以下では、アドレスを宛先アドレスのみとして、宛先アドレスの検証を行う場合と例に説明する。図２７Ａは、変換前の検証環境の一例を説明する図である。図２７Ａには、検証を行うネットワーク１４の一例が示されている。ネットワーク１４は、ノードＡ、ノードＢ、ノードＣ及びノードＤを有し、ノードＤを介してノードＡ、ノードＢ、ノードＣが接続されている。ノードＡ、ノードＢおよびノードＣは、外部と通信を行うエッジノードである。ノードＤは、エッジノードからのデータを中継する中継ノードである。
【０１２７】
ノードＡは、アドレス「１００  ＸＸＸ」の外部ポートＡと、インタフェースｉｆ＿ａ１を有し、インタフェースｉｆ＿ａ１を介してノードＤと接続されている。ノードＢは、アドレス「０００  ＸＸＸ」の外部ポートＢと、インタフェースｉｆ＿ｂ１を有し、インタフェースｉｆ＿ｂ１を介してノードＤと接続されている。ノードＣは、アドレス「１１１  ＸＸＸ」の外部ポートＣと、インタフェースｉｆ＿ｃ１を有し、インタフェースｉｆ＿ｃ１を介してノードＤと接続されている。ノードＤは、インタフェースｉｆ＿ｄ１、ｉｆ＿ｄ２、ｉｆ＿ｄ３を有し、インタフェースｉｆ＿ｄ１を介してノードＡと接続され、インタフェースｉｆ＿ｄ２を介してノードＢと接続され、インタフェースｉｆ＿ｄ３を介してノードＣと接続されている。なお、本実施例では、説明を簡易化するため、アドレスを例えば「１００  ＸＸＸ」と６ビットで示している。また、アドレスの「Ｘ」は、アドレスのビットが「０」でも「１」でも該当するものとみなすワイルドカードを表す。
【０１２８】
また、図２７Ａには、デマンド情報３１の一例が示されている。なお、図２７Ａの例では、外部ポートに対応させて、割当てが求められた通信経路の宛先となる６ビットの宛先アドレスが示され、括弧内に割当てが求められた帯域が示されている。また、図２７Ａの例では、デマンド情報３１の左側に、通信経路の送信元および送信先に対応させて、通信経路で確保したい帯域がマトリクス状に示されている。
【０１２９】
また、図２７Ａには、ノードＡ、ノードＤの経路テーブル３２の一例が示されている。なお、本実施例では、説明を簡易化するため、経路テーブル３２には、エントリ情報として宛先に応じた出力先のみを示している。図２７Ａの例では、ノードＡは、宛先「０００  ＸＸＸ」及び「１１１  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ａ１とされている。ノードＤは、宛先「０００  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ｄ２とされ、宛先「１１１  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ｄ３とされている。
【０１３０】
図２７Ａの例では、外部ポートＡに宛先アドレス「０００  ＸＸＸ」と「１１１  ＸＸＸ」の２つのデマンドがあり、外部ポートＢ、Ｃにデマンドは存在しない。そこで、経路テーブル検証装置１０は、外部ポートＡの２つのデマンドの宛先アドレス「０００  ＸＸＸ」及び「１１１  ＸＸＸ」について隣接空間への変換を行う。この変換は、図２３Ａと同様であるから、「０００  ＸＸＸ」及び「００１  ＸＸＸ」の２つに変換される。この変換を変換ｆ１とすると、変換ｆ１は、宛先アドレスについて、以下のように表すことができる。
【０１３１】
ｆ１：（１１１  ＸＸＸ  →  ００１  ＸＸＸ)
【０１３２】
経路テーブル検証装置１０は、各ノードの経路テーブルに変換ｆ１を適用して、アドレスを変換する。図２７Ｂは、変換後の検証環境の一例を説明する図である。各ノードの経路テーブルに変換ｆ１を適用することで、例えば、ノードＡは、宛先「００１  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ａ１と変換される。ノードＤは、宛先「００１  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ｄ３と変換される。
【０１３３】
経路テーブル検証装置１０は、デマンドのアドレスからデマンド外のパケットを生成する。図２３Ａに示すように、「０００  ＸＸＸ」及び「００１  ＸＸＸ」の和が「００Ｘ  ＸＸＸ」であることから、経路テーブル検証装置１０は、「１ＸＸ  ＸＸＸ」と「Ｘ１Ｘ  ＸＸＸ」を宛先アドレスとした２つのデマンド外のパケットを生成する。
【０１３４】
ここで、デマンドのアドレスが「０００  ＸＸＸ」、「１１１  ＸＸＸ」の２つである場合、アドレスの変換を行わずにデマンド外を表現するには、「Ｘ０１  ＸＸＸ」、「Ｘ１０  ＸＸＸ」、「０１１  ＸＸＸ」、「１００  ＸＸＸ」の４個になる。本実施例に係る経路テーブル検証装置１０は、アドレスの変換を行うことで、デマンド外のパケットのアドレスを「１ＸＸ  ＸＸＸ」と「Ｘ１Ｘ  ＸＸＸ」の２個に減らすことができる。
【０１３５】
経路テーブル検証装置１０は、各ノードの経路テーブル３２に基づいて、生成したデマンド外のパケットを外部ポートＡから入力した場合の転送経路を算出し、算出結果から、デマンド外のパケットが何れかのノードで転送されずにドロップしたかを検証する。
【０１３６】
また、経路テーブル検証装置１０は、外部ポートＢ、Ｃについてはデマンドヘッダが存在しないため、その補集合である「ＸＸＸ  ＸＸＸ」を宛先アドレスとしたデマンド外のパケットを生成する。経路テーブル検証装置１０は、各ノードの経路テーブル３２に基づいて、生成したデマンド外のパケットを外部ポートＢ、Ｃからそれぞれ入力した場合の転送経路を算出する。経路テーブル検証装置１０は、算出結果から、デマンド外のパケットが何れかのノードで転送されずにドロップしたかを検証する。
【０１３７】
続いて他の具体例を説明する。図２８Ａは、変換前の検証環境の一例を説明する図である。図２８Ａには、図２７Ａと同様のネットワーク１４が示されている。また、図２８Ａにも、デマンド情報３１の一例が示され、デマンド情報３１の左側に、通信経路の送信元および送信先に対応させて、通信経路で確保したい帯域がマトリクス状に示されている。また、図２８Ａには、ノードＡ、ノードＤの経路テーブル３２の一例が示されている。なお、本実施例でも、説明を簡易化するため、経路テーブル３２には、エントリ情報として宛先に応じた出力先のみを示している。図２８Ａの例では、ノードＡは、宛先「０００  ＸＸＸ」及び「１Ｘ１  Ｘ１Ｘ」のパケットの出力先がインタフェースｉｆ＿ａ１とされている。ノードＤは、宛先「０００  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ｄ２とされ、宛先「１Ｘ１  Ｘ１Ｘ」のパケットの出力先がインタフェースｉｆ＿ｄ３とされている。
【０１３８】
図２８Ａの例では、外部ポートＡに宛先アドレス「０００  ＸＸＸ」と「１Ｘ１  Ｘ１Ｘ」の２つのデマンドがあり、外部ポートＢ、Ｃにデマンドは存在しない。そこで、経路テーブル検証装置１０は、外部ポートＡの２つのデマンドの宛先アドレス「０００  ＸＸＸ」及び「１Ｘ１  Ｘ１Ｘ」について隣接空間への変換を行う。この変換は、図２３Ｂと同様であるから、「０００  ＸＸＸ」及び「００１  ＸＸＸ」の２つに変換される。この変換を変換ｆ２とすると、変換ｆ２は、宛先アドレスについて、以下のように表すことができる。
【０１３９】
ｆ２：（１Ｘ１  Ｘ１Ｘ  →  ００１  ＸＸＸ)
【０１４０】
経路テーブル検証装置１０は、各ノードの経路テーブルに変換ｆ１を適用して、アドレスを変換する。図２８Ｂは、変換後の検証環境の一例を説明する図である。各ノードの経路テーブルに変換ｆ２を適用することで、例えば、ノードＡは、宛先「００１  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ａ１と変換される。ノードＤは、宛先「００１  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ｄ３と変換される。
【０１４１】
経路テーブル検証装置１０は、デマンドのアドレスからデマンド外のパケットを生成する。図２３Ｂに示すように、「０００  ＸＸＸ」及び「００１  ＸＸＸ」の和が「００Ｘ  ＸＸＸ」であることから、経路テーブル検証装置１０は、「１ＸＸ  ＸＸＸ」と「Ｘ１Ｘ  ＸＸＸ」を宛先アドレスとした２つのデマンド外のパケットを生成する。
【０１４２】
ここで、デマンドのアドレスが「０００  ＸＸＸ」、「１Ｘ１  Ｘ１Ｘ」の２つである場合、各アドレスがアドレス空間で離散的であるため、アドレスの変換を行わずにデマンド外を表現するには、アドレスの数が多くなる。本実施例に係る経路テーブル検証装置１０は、アドレスの変換を行うことで、デマンド外のパケットのアドレスを「１ＸＸ  ＸＸＸ」と「Ｘ１Ｘ  ＸＸＸ」の２個に減らすことができる。
【０１４３】
経路テーブル検証装置１０は、各ノードの経路テーブル３２に基づいて、生成したデマンド外のパケットを外部ポートＡから入力した場合の転送経路を算出し、算出結果から、デマンド外のパケットが何れかのノードで転送されずにドロップしたかを検証する。
【０１４４】
また、経路テーブル検証装置１０は、外部ポートＢ、Ｃについてはデマンドヘッダが存在しないため、その補集合である「ＸＸＸ  ＸＸＸ」を宛先アドレスとしたデマンド外のパケットを生成する。経路テーブル検証装置１０は、各ノードの経路テーブル３２に基づいて、生成したデマンド外のパケットを外部ポートＢ、Ｃからそれぞれ入力した場合の転送経路を算出する。経路テーブル検証装置１０は、算出結果から、デマンド外のパケットが何れかのノードで転送されずにドロップしたかを検証する。
【０１４５】
続いて他の具体例を説明する。図２９Ａは、変換前の検証環境の一例を説明する図である。図２９Ａには、検証を行うネットワーク１４の一例が示されている。ネットワーク１４は、ノードＡ、ノードＢ、ノードＣ、ノードＤ及びノードＥを有し、ノードＥを介してノードＡ、ノードＢ、ノードＣ、ノードＤが接続されている。ノードＡ、ノードＢ、ノードＣおよびノードＤは、外部と通信を行うエッジノードである。ノードＥは、エッジノードからのデータを中継する中継ノードである。
【０１４６】
ノードＡは、アドレス「１００  ＸＸＸ」の外部ポートＡと、インタフェースｉｆ＿ａ１を有し、インタフェースｉｆ＿ａ１を介してノードＥと接続されている。ノードＢは、アドレス「０００  ＸＸＸ」の外部ポートＢと、インタフェースｉｆ＿ｂ１を有し、インタフェースｉｆ＿ｂ１を介してノードＥと接続されている。ノードＣは、アドレス「００１  ＸＸＸ」の外部ポートＣと、インタフェースｉｆ＿ｃ１を有し、インタフェースｉｆ＿ｃ１を介してノードＥと接続されている。ノードＤは、アドレス「０１０  ＸＸＸ」の外部ポートＤと、インタフェースｉｆ＿ｄ１を有し、インタフェースｉｆ＿ｄ１を介してノードＥと接続されている。ノードＥは、インタフェースｉｆ＿ｅ１、ｉｆ＿ｅ２、ｉｆ＿ｅ３、ｉｆ＿ｅ４を有する。ノードＥは、インタフェースｉｆ＿ｅ１を介してノードＡと接続され、インタフェースｉｆ＿ｅ２を介してノードＢと接続され、インタフェースｉｆ＿ｅ３を介してノードＣと接続され、インタフェースｉｆ＿ｅ４を介してノードＤと接続されている。なお、本実施例では、説明を簡易化するため、アドレスを例えば「０００  ＸＸＸ」と６ビットで示している。また、アドレスの「Ｘ」は、アドレスのビットが「０」でも「１」でも該当するものとみなすワイルドカードを表す。
【０１４７】
また、図２９Ａには、デマンド情報３１の一例が示されている。なお、図２９Ａの例では、外部ポートに対応させて、割当てが求められた通信経路の宛先となる６ビットの宛先アドレスが示され、括弧内に割当てが求められた帯域が示されている。また、図２９Ａの例では、デマンド情報３１の左側に、通信経路の送信元および送信先に対応させて、通信経路で確保したい帯域がマトリクス状に示されている。
【０１４８】
また、図２９Ａには、ノードＡ、ノードＥの経路テーブル３２の一例が示されている。なお、本実施例では、説明を簡易化するため、経路テーブル３２には、エントリ情報として宛先に応じた出力先のみを示している。図２９Ａの例では、ノードＡは、宛先「０００  ＸＸＸ」、「００１  ＸＸＸ」及び「０１０  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ａ１とされている。ノードＥは、宛先「０００  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ｅ２とされ、宛先「００１  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ｅ３とされ、宛先「０１０  ＸＸＸ」のパケットの出力先がインタフェースｉｆ＿ｅ４とされている。
【０１４９】
図２９Ａの例では、外部ポートＡに宛先アドレス「０００  ＸＸＸ」と「００１  ＸＸＸ」と「０１０  ＸＸＸ」の３つのデマンドがあり、外部ポートＢ〜Ｄにデマンドは存在しない。そこで、経路テーブル検証装置１０は、外部ポートＡの３つのデマンドの宛先アドレス「０００  ＸＸＸ」、「００１  ＸＸＸ」及び「０１０  ＸＸＸ」について隣接空間への変換を行うが、これらは既に隣接空間に配置されている。このため、これ以上の変換は、必要なく、そのまま変換後のアドレスになる。この時のヘッダ空間の変換を変換ｆ３とすると、変換ｆ３は、宛先アドレスについて、変換なしを意味する、以下のように表すことができる。
【０１５０】
ｆ３：（φ  →  φ)
なお、φは、空集合を意味するものとする。
【０１５１】
経路テーブル検証装置１０は、各ノードの経路テーブルに変換ｆ３を適用して、アドレスを変換する。図２９Ｂは、変換後の検証環境の一例を説明する図である。変換ｆ３で変換されるアドレスが無いため、図２９Ｂに示す各ノードの経路テーブルは、図２９Ａと同じとなる。
【０１５２】
経路テーブル検証装置１０は、デマンドのアドレスからデマンド外のパケットを生成する。図２４Ｂに示すように、「０００  ＸＸＸ」、「００１  ＸＸＸ」、「０１０  ＸＸＸ」から、経路テーブル検証装置１０は、「１ＸＸ  ＸＸＸ」と「００１  ＸＸＸ」を宛先アドレスとした２つのデマンド外のパケットを生成する。
【０１５３】
ここで、デマンドのアドレスが「０００  ＸＸＸ」、「００１  ＸＸＸ」、「０１０  ＸＸＸ」の３つである場合、各アドレスの和を表すアドレスの数が多くなるため、補完アドレスを補完せずにデマンド外を表現するには、アドレスの数が多くなる。本実施例に係る経路テーブル検証装置１０は、補完アドレスを補完することで、デマンド外のパケットのアドレスを「１ＸＸ  ＸＸＸ」と「Ｘ１Ｘ  ＸＸＸ」の２個に減らすことができる。
【０１５４】
経路テーブル検証装置１０は、各ノードの経路テーブル３２に基づいて、生成したデマンド外のパケットを外部ポートＡから入力した場合の転送経路を算出し、算出結果から、デマンド外のパケットが何れかのノードで転送されずにドロップしたかを検証する。
【０１５５】
また、経路テーブル検証装置１０は、外部ポートＢ〜Ｄについてはデマンドヘッダが存在しないため、その補集合である「ＸＸＸ  ＸＸＸ」を宛先アドレスとしたデマンド外のパケットを生成する。経路テーブル検証装置１０は、各ノードの経路テーブル３２に基づいて、生成したデマンド外のパケットを外部ポートＢ〜Ｄからそれぞれ入力した場合の転送経路を算出する。経路テーブル検証装置１０は、算出結果から、デマンド外のパケットが何れかのノードで転送されずにドロップしたかを検証する。
【０１５６】
このように、経路テーブル検証装置１０は、少ないデマンド外のパケット数でデマンド外の検証を行うことができる。これにより、経路テーブル検証装置１０は、デマンド外の検証にかかる検証時間の増大を抑制できる。
【０１５７】
［処理の流れ］
実施例３に係る経路テーブル検証装置１０がデマンド外のパケットを生成する生成処理の流れについて説明する。図３０は、実施例３に係る生成処理の手順の一例を示すフローチャートである。この生成処理は、例えば、図１３に示す検証処理のＳ１０の処理の後や、例えば、図１９に示す検証処理のＳ１００の後にサブルーチンとして追加されて実行される。
【０１５８】
図３０に示すように、変換部４７は、検証を行うネットワーク１４の未処理の外部ポートを１つ選択し、選択した外部ポートを入力とするデマンドをデマンド情報３１からすべて抽出する（Ｓ２００）。変換部４７は、Ｓ２００で抽出したデマンドのうち、アドレスに含まれるワイルドカードＸのビット数が最小となるアドレスのワイルドカードＸのビット数を変数ｍにセットする（Ｓ２０１）。変換部４７は、Ｓ２００で抽出したデマンドのなかから、アドレスに含まれるワイルドカードＸのビット数が変数ｍに該当するデマンドをすべて抽出する（Ｓ２０３）。変換部４７は、Ｓ２００で抽出したデマンドに対して、アドレスの変換処理を行う（Ｓ２０４）。
【０１５９】
図３１は、実施例３に係る変換処理の手順の一例を示すフローチャートである。この変換処理は、例えば、生成処理のＳ２０４から実行される。
【０１６０】
図３１に示すように、変換部４７は、Ｓ２０３で抽出された各デマンドのアドレスに含まれる変数ｍ個のワイルドカードＸのビットを全て同じ位置に変更するビットシフトを行う（Ｓ２５０）。例えば、変換部４７は、各デマンドのアドレスに含まれる変数ｍ個のワイルドカードＸのビットをアドレス内で最下位ビット(ＬＳＢ（least  significant  bit）)側に寄せるビットシフトを行う。変換部４７は、各デマンドのアドレスのワイルドカードＸのビット以外のビット例を、順に隣り合うアドレスを示すようにへ平行移行させる変換を行う（Ｓ２５１）。例えば、変換部４７は、各デマンドのアドレスのワイルドカードＸのビット以外のビット例を、００・・・０からシーケンシャルな番号になるように新たなビット例に変換する。
【０１６１】
生成部４２は、Ｓ２０３で抽出された各デマンドのアドレスの数ｋが２nとなる自然数ｎがあるか否かを判定する（Ｓ２５２）。自然数ｎがある場合（Ｓ２５２肯定）、生成部４２は、アドレスが変換された各デマンドのアドレスの和の補集合となるアドレスをアドレスとしたデマンド外のパケットを生成して（Ｓ２５３）、変換処理を終了し、生成処理のＳ２０５へ移行する。
【０１６２】
一方、自然数ｎがない場合（Ｓ２５２否定）、生成部４２は、アドレスが変換された各デマンドのアドレスの和を示すアドレスが、ワイルドカードＸを用いた場合に１つのアドレスとなるように補完する補完アドレスを求める（Ｓ２５４）。生成部４２は、補完アドレスと各デマンドのアドレスとの和の補集合となるアドレスおよび補完アドレスをアドレスとしたデマンド外のパケットを生成して（Ｓ２５５）、変換処理を終了し、生成処理のＳ２０５へ移行する。
【０１６３】
図３０に戻り、変換部４７は、変換処理での各デマンドのアドレスの変換に対応させて、各ノードの経路テーブル３２のアドレスを変換する（Ｓ２０５）。
【０１６４】
変換部４７は、Ｓ２００で抽出したデマンドに、アドレスに含まれるワイルドカードＸのビット数が変数ｍ＋１以上のものがあるか否かを判定する（Ｓ２０６）。ワイルドカードＸのビット数が変数ｍ＋１以上のものがある場合（Ｓ２０６肯定）、変換部４７は、ワイルドカードＸのビット数が変数ｍ＋１以上のワイルドカードＸのビット数のうち、最小となるアドレスのワイルドカードＸのビット数を変数ｍにセットし（Ｓ２０７）、上記のＳ２０３へ移行する。
【０１６５】
一方、ワイルドカードＸのビット数が変数ｍ＋１以上のものがない場合（Ｓ２０６否定）、変換部４７は、検証を行うネットワーク１４に未処理の外部ポートがあるか否かを判定する（Ｓ２０８）。未処理の外部ポートがある場合（Ｓ２０８肯定）、上記のＳ２００へ移行する。
【０１６６】
一方、未処理の外部ポートがない場合（Ｓ２０８否定）、処理を終了する。
【０１６７】
［効果］
上述してきたように、本実施例に係る経路テーブル検証装置１０は、デマンドの通信経路のアドレスの補集合となるアドレスのデマンド外のパケットを生成する。経路テーブル検証装置１０は、ネットワークの各ノードの経路テーブルに基づいて、生成されたデマンド外のパケットの転送経路を算出する。経路テーブル検証装置１０は、算出結果から、デマンド外のパケットがネットワークの何れかのノードで転送されずにドロップしたかを検証する。これにより、経路テーブル検証装置１０は、デマンド外のパケットがネットワークで転送されないことを容易に検証できる。
【０１６８】
また、本実施例に係る経路テーブル検証装置１０は、デマンドが複数ある場合、各デマンドの通信経路のアドレスを隣接するアドレス空間となるように変換すると共に、当該アドレスの変換に対応させて、各ノードの経路テーブルのアドレスを変換する。経路テーブル検証装置１０は、各デマンドの変換されたアドレスの和の補集合となるアドレスのデマンド外のパケットを生成する。経路テーブル検証装置１０は、アドレスが変換された各ノードの経路テーブルに基づいて、デマンド外のパケットの転送経路を算出する。これにより、経路テーブル検証装置１０は、デマンドが複数あり、各デマンドのアドレスが離散的である場合でも、少ないデマンド外のパケット数でデマンド外の検証を行うことができる。これにより、経路テーブル検証装置１０は、デマンド外の検証にかかる検証時間の増大を抑制できる。
【０１６９】
また、本実施例に係る経路テーブル検証装置１０は、変換された各デマンドのアドレスの和を示すアドレスが、ワイルドカードを用いた場合に１つのアドレスとなるように補完する補完アドレスを求める。経路テーブル検証装置１０は、補完アドレスと各デマンドのアドレスとの和の補集合となるアドレスおよび補完アドレスをアドレスとしたデマンド外のパケットを生成する。これにより、経路テーブル検証装置１０は、各デマンドのアドレスの和をワイルドカードを用いた場合に１つのアドレスで表せない場合でも、少ないデマンド外のパケット数でデマンド外の検証を行うことができる。これにより、経路テーブル検証装置１０は、デマンド外の検証にかかる検証時間の増大を抑制できる。
【実施例４】
【０１７０】
さて、これまで開示の装置に関する実施例について説明したが、開示の技術は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【０１７１】
例えば、上記の実施例では、リンク帯域管理テーブル３３のリンクの記録帯域の領域に、リンクを転送されたパケットの帯域を累計する場合について説明したが、開示の装置はこれに限定されない。例えば、帯域を使用する時間帯の情報をパケットに含め、リンク帯域管理テーブル３３に時間帯ごとに、リンクを転送されたパケットの帯域を累計してもよい。例えば、デマンドに帯域を使用する時間帯の情報を設定させ、生成部４２は、帯域を使用する時間帯ごとに使用する帯域情報が付されたパケットを生成する。図３２は、パケットのヘッダの一例を示す図である。図３２の例では、ヘッダのＤｓｔを「００ｘｘ」とし、ｂｗを「１０」とし、帯域を使用する使用時間帯が「２１：００〜２１：５９」としたパケット７０が示されている。帯域検証部４５は、リンク帯域管理テーブル３３に、リンクを通過するパケットの帯域を時間帯ごとに積算する。図３３は、リンク帯域管理テーブルのデータ構成の一例を示す図である。図３３の例では、時間帯の項目がさらに設けれ、リンクを通過するパケットの帯域が時間帯ごとに積算される。例えば、ノードＡからノードＤへのリンクは、使用時間帯が「２１：００〜２１：５９」に合計の帯域が１０Ｍｂｐｓと記録されている。帯域検証部４５は、時間帯ごとにリンクの帯域量と積算された帯域の整合性を検証する。これにより、ネットワーク１４が使用される時間帯ごとにリンクの帯域量の整合性を検証できる。実施例２についてもデマンドリストに、各デマンドの使用時間帯を含めることで、ネットワーク１４が使用される時間帯ごとにリンクの帯域量の整合性を検証できる。
【０１７２】
また、上記の実施例では、ネットワーク設計において、実際のネットワーク１４に設定する前の経路テーブルがデマンドを満たすか検証する場合について説明したが、開示の装置はこれに限定されない。例えば、実際のネットワーク１４に設定された経路テーブルがデマンドを満たすか検証してもよい。図３４は、ネットワークに設定された経路テーブルがデマンドを満たすか検証する例を模式的に示した図である。ＮＷ設定装置１２は、ネットワーク１４のルータやスイッチなどの各ノードから経路テーブルを収集して経路テーブル検証装置１０へ送信する。ＮＷ設計装置１１は、指定されたデマンドの情報を経路テーブル検証装置１０へ送信する。経路テーブル検証装置１０は、ネットワーク１４に設定された経路テーブルが、ＮＷ設計装置１１から入力されたデマンドを満たすか否かを検証してもよい。これにより、経路テーブル検証装置１０は、実際のネットワーク１４に設定された経路テーブルがデマンドを満たすかを検証できる。
【０１７３】
また、上記の実施例では、パケットのヘッダに含まれる宛先アドレスにより、転送先を判別する場合について説明したが、開示の装置はこれに限定されない。例えば、送信元アドレス、プロトコル番号、サービス・タイプ（ToS値）、VLAN番号、宛先ポート番号（TCP/UDP）、送信元ポート番号（TCP/UDP）を用いて転送先を判別してもよい。
【０１７４】
経路テーブル検証装置１０は、経路テーブルがデマンドを満たすかを次の手順で検証してもよい。図３５は、検証の流れの他の例を模式的に示した図である。経路テーブル検証装置１０は、全ての外部ポートから宛先アドレスを全ワイルドカードとしたパケットを入力して転送経路の算出を行い、ループの発生およびエッジノードに到達したパケットのヘッダから到達可能性をチェックする（図３５（Ａ））。次に、経路テーブル検証装置１０は、エッジノードに到達したパケットの転送経路を逆にたどる。例えば、経路テーブル検証装置１０は、エッジノードに到達したパケットの送信元アドレスと宛先アドレスと入れ替え、転送経路を逆にたどるリバース処理を行う。そして、経路テーブル検証装置１０は、リバース処理の結果、パケットが完全に同じ転送経路で入力ノードに戻るかの等価クラスの検証を行う（図３５（Ｂ））。経路テーブル検証装置１０は、等価クラスに該当するデマンドの帯域情報を設定して再度パケットを伝搬させ、各リンク毎に、通過するパケットの帯域を累積して記録する。そして、経路テーブル検証装置１０は、全てのパケットの伝搬後、リンク毎に累積された帯域値がリンク速度を超えていないか帯域の検証を行う（図３５（Ｃ））。
【０１７５】
また、上記の実施例では、経路テーブル検証装置１０、ＮＷ設計装置１１およびＮＷ設定装置１２の３台の装置によりシステム１を構成する場合について説明した。しかしながら、これらに限定されるものではなく、適宜変更可能である。例えば、経路テーブル検証装置１０、ＮＷ設計装置１１およびＮＷ設定装置１２の各装置を統合・分散してもよい。例えば、経路テーブル検証装置１０、ＮＷ設計装置１１およびＮＷ設定装置１２を統合して１台の装置としてもよい。
【０１７６】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、取得部４０、受付部４１、生成部４２、算出部４３、経路検証部４４、帯域検証部４５、出力部４６および変換部４７の各処理部が適宜統合されてもよい。また、各処理部の処理が適宜複数の処理部の処理に分離されてもよい。さらに、各処理部にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１７７】
［経路テーブル検証プログラム］
また、上記の実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータシステムの一例を説明する。図３６は、経路テーブル検証プログラムを実行するコンピュータを示す図である。
【０１７８】
図３６に示すように、コンピュータ３００は、ＣＰＵ（Central  Processing  Unit）３１０、ＨＤＤ（Hard  Disk  Drive）３２０、ＲＡＭ（Random  Access  Memory）３４０を有する。これら３００〜３４０の各部は、バス４００を介して接続される。
【０１７９】
ＨＤＤ３２０には上記の取得部４０、受付部４１、生成部４２、算出部４３、経路検証部４４、帯域検証部４５、出力部４６および変換部４７と同様の機能を発揮する経路テーブル検証プログラム３２０ａが予め記憶される。なお、経路テーブル検証プログラム３２０ａについては、適宜分離しても良い。
【０１８０】
また、ＨＤＤ３２０は、各種情報を記憶する。例えば、ＨＤＤ３２０は、ＯＳや分析に用いる各種データを記憶する。
【０１８１】
そして、ＣＰＵ３１０が、経路テーブル検証プログラム３２０ａをＨＤＤ３２０から読み出して実行することで、実施例の各処理部と同様の動作を実行する。すなわち、経路テーブル検証プログラム３２０ａは、取得部４０、受付部４１、生成部４２、算出部４３、経路検証部４４、帯域検証部４５、出力部４６および変換部４７と同様の動作を実行する。
【０１８２】
なお、上記した経路テーブル検証プログラム３２０ａは、必ずしも最初からＨＤＤ３２０に記憶させることを要しない。
【０１８３】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【０１８４】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などにプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１８５】
１  システム
１０  経路テーブル検証装置
１１  ＮＷ設計装置
１２  ＮＷ設定装置
１４  ネットワーク
２３  記憶部
２４  制御部
３０  ネットワーク情報
３１  デマンド情報
３２  経路テーブル
３３  リンク帯域管理テーブル
４０  取得部
４１  受付部
４２  生成部
４３  算出部
４４  経路検証部
４５  帯域検証部
４６  出力部
４７  変換部
【図１】
2016158232.tif 000004
【図２】
2016158232.tif 000005
【図３】
2016158232.tif 000006
【図４】
2016158232.tif 000007
【図５】
2016158232.tif 000008
【図６Ａ】
2016158232.tif 000009
【図６Ｂ】
2016158232.tif 000010
【図６Ｃ】
2016158232.tif 000011
【図７】
2016158232.tif 000012
【図８】
2016158232.tif 000013
【図９】
2016158232.tif 000014
【図１０Ａ】
2016158232.tif 000015
【図１０Ｂ】
2016158232.tif 000016
【図１１】
2016158232.tif 000017
【図１２】
2016158232.tif 000018
【図１３】
2016158232.tif 000019
【図１４】
2016158232.tif 000020
【図１５】
2016158232.tif 000021
【図１６】
2016158232.tif 000022
【図１７】
2016158232.tif 000023
【図１８】
2016158232.tif 000024
【図１９】
2016158232.tif 000025
【図２０】
2016158232.tif 000026
【図２１】
2016158232.tif 000027
【図２２】
2016158232.tif 000028
【図２３Ａ】
2016158232.tif 000029
【図２３Ｂ】
2016158232.tif 000030
【図２４Ａ】
2016158232.tif 000031
【図２４Ｂ】
2016158232.tif 000032
【図２５】
2016158232.tif 000033
【図２６】
2016158232.tif 000034
【図２７Ａ】
2016158232.tif 000035
【図２７Ｂ】
2016158232.tif 000036
【図２８Ａ】
2016158232.tif 000037
【図２８Ｂ】
2016158232.tif 000038
【図２９Ａ】
2016158232.tif 000039
【図２９Ｂ】
2016158232.tif 000040
【図３０】
2016158232.tif 000041
【図３１】
2016158232.tif 000042
【図３２】
2016158232.tif 000043
【図３３】
2016158232.tif 000044
【図３４】
2016158232.tif 000045
【図３５】
2016158232.tif 000046
【図３６】
2016158232.tif 000047