(57)【特許請求の範囲】
【請求項１】
ネットワークを構成する各ネットワークノードからネットワークのトラフィック情報とトポロジ情報とを取得してリンク利用率が上昇したかまたは輻輳が発生した１以上の連続したリンクを迂回対象リンクとして検出するネットワーク情報収集装置と、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を作成するトラフィック交流情報作成装置と、前記迂回対象リンクを利用しているトラフィックの一部を迂回させる迂回経路を決定する迂回経路決定装置と、前記迂回経路にパスを新たに設定する迂回パス設定装置とを備える通信システムの前記迂回経路決定装置であって、
前記ネットワーク情報収集装置から、前記迂回対象リンクに関する情報をトラフィック退避要求と共に取得するトラフィック退避要求受付手段と、
前記ネットワーク情報収集装置からネットワークのトポロジ情報を取得し、この取得したトポロジ情報と前記迂回対象リンクに関する情報とを利用することで、前記迂回対象リンクを利用するトラフィックの始点および終点を示すエッジノードの情報と、迂回路となる始点候補および終点候補として当該トラフィックの経路において前記迂回対象リンクの上流側の輻輳始点を頂点とするツリー構造に含まれるノードと、当該リンクの下流側の輻輳終点を頂点とするツリー構造に含まれるノードとの情報とを示す端点候補情報を抽出する端点候補抽出手段と、
前記端点候補情報を前記トラフィック交流情報作成装置に通知することで、前記トラフィック交流情報作成装置から、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を取得するトラフィック交流情報取得手段と、
前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報と前記端点候補情報とを記憶するトラフィック交流情報データベースと、
ネットワーク全体に共通に、またはグループ単位に個別に、またはリンク単位に個別に予め設定された、前記迂回対象リンクを利用しているトラフィックのうち迂回させるトラフィック量を示す迂回対象トラフィック量を取り除いた後のトラフィック量の所定範囲またはリンクの最大帯域に対するリンク利用率の所定範囲を、前記迂回対象リンクに設定されている目標帯域として記憶する目標帯域データベースと、
前記迂回対象リンクに関する情報と前記トラフィック交流情報データベースに記憶されたトラフィック交流情報および前記端点候補情報とを利用して、前記迂回対象リンクに流れているトラフィック量を特定し、前記目標帯域データベースから前記迂回対象リンクに設定されている目標帯域を取得し、取得した目標帯域と前記迂回対象リンクに流れているトラフィック量との差分を示す所定範囲を前記迂回対象トラフィック量として決定する迂回対象トラフィック量決定手段と、
前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報に基づいて、トラフィックマトリクスの分割を行い、前記端点候補情報における１つの始点候補と組になる対向側の終点候補すべての組についてマトリクス要素で示される帯域の合計値が、前記決定された迂回対象トラフィック量の範囲に含まれるか否かについて、前記迂回対象リンクの上流側および下流側の前記ツリー構造のそれぞれの頂点から下の階層へ向かって前記トラフィック交流情報の大きい順に探索し、前記帯域の合計値が前記迂回対象トラフィック量の範囲に含まれるような組み合わせの始点候補および終点候補を前記迂回路の始点および終点として決定する迂回端点決定手段と、
前記決定された迂回路の始点と終点とを連結する経路の計算を行うことで前記迂回経路を決定する経路計算手段とを備えることを特徴とする迂回経路決定装置。
【請求項２】
前記経路計算手段は、
前記ネットワーク情報収集装置から、前記ネットワークのトポロジ情報およびトラフィック情報を取得し、前記取得したネットワークのトポロジ情報から、前記迂回対象トラフィック量が収容できないリンク利用状態のリンクを取り除いた経路計算用のトポロジ情報を作成し、前記作成した経路計算用のトポロジ情報を用いて、前記迂回路の始点から終点までの最短経路を前記迂回経路として計算し、前記迂回路の始点から終点までの経路が得られなかった場合には、新たな迂回路の始点と終点を決定するように前記迂回端点決定手段に対して要求することを特徴とする請求項１に記載の迂回経路決定装置。
【請求項３】
前記退避要求受付手段は、前記トラフィック退避要求を取得する前に予め、前記ネットワーク情報収集装置から、前記ネットワークのトポロジ情報およびトラフィック情報を取得し、前記取得したネットワークのトポロジ情報およびトラフィック情報に基づいて前記ネットワーク全体に共通に設定する、リンクの最大帯域に対するリンク利用率の所定範囲を前記目標帯域として算出し、前記目標帯域データベースに格納することを特徴とする請求項１または請求項２に記載の迂回経路決定装置。
【請求項４】
前記経路計算手段で決定された迂回経路の経路情報を取得し、前記ネットワーク情報収集装置から前記ネットワークのトポロジ情報を取得し、前記取得したネットワークのトポロジ情報から、前記迂回経路のメトリックを計算し、このメトリックとして迂回元の経路よりも小さい値を算出し、迂回パスとしてＭＰＬＳ（Multi-Protocol Label Switching）またはＧＭＰＬＳ（Generalized Multi-Protocol Label Switching）のパスを設定する迂回パス設定装置に対して、迂回パス設定要求と、前記迂回経路の経路情報と、前記迂回経路のメトリックの情報とを通知する迂回パス設定要求手段をさらに備えることを特徴とする請求項１ないし請求項３のいずれか一項に記載の迂回経路決定装置。
【請求項５】
前記経路計算手段で決定された迂回経路の経路情報を取得し、トラフィックの終点となるＩＰアドレス・ネットワークアドレスに関してスタティックルーティングの設定を行い、ＭＰＬＳまたはＧＭＰＬＳのパスを利用するようにパス設定を行う迂回パス設定装置、または、指定されたネットワークノード間で通信パケットのマーキングの設定を行い前記迂回対象リンクを利用しているトラフィックが前記指定された経路を利用するようにパス設定を行う迂回パス設定装置のいずれかに対して、迂回パス設定要求と、前記決定された迂回経路の経路情報とを通知する迂回パス設定要求手段をさらに備えることを特徴とする請求項１ないし請求項３のいずれか一項に記載の迂回経路決定装置。
【請求項６】
ネットワークを構成する各ネットワークノードからネットワークのトラフィック情報とトポロジ情報とを取得してリンク利用率が上昇したかまたは輻輳が発生した１以上の連続したリンクを迂回対象リンクとして検出するネットワーク情報収集装置と、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を作成するトラフィック交流情報作成装置と、前記迂回対象リンクを利用しているトラフィックの一部を迂回させる迂回経路を決定する迂回経路決定装置と、前記迂回経路にパスを新たに設定する迂回パス設定装置とを備える通信システムの前記迂回経路決定装置による迂回経路決定方法であって、
前記迂回経路決定装置は、トラフィック退避要求受付手段と、端点候補抽出手段と、トラフィック交流情報取得手段と、迂回対象トラフィック量決定手段と、迂回端点決定手段と、経路計算手段と、迂回パス設定要求手段と、
ネットワーク全体に共通に、またはグループ単位に個別に、またはリンク単位に個別に予め設定された、前記迂回対象リンクを利用しているトラフィックのうち迂回させるトラフィック量を示す迂回対象トラフィック量を取り除いた後のトラフィック量の所定範囲またはリンクの最大帯域に対するリンク利用率の所定範囲を、前記迂回対象リンクに設定されている目標帯域として記憶する目標帯域データベースとを備え、
前記トラフィック退避要求受付手段によって、前記ネットワーク情報収集装置から前記迂回対象リンクに関する情報をトラフィック退避要求と共に取得するステップと、
前記端点候補抽出手段によって、前記ネットワーク情報収集装置からネットワークのトポロジ情報を取得するステップと、
前記迂回対象リンクに関する情報と前記ネットワークのトポロジ情報とを利用することで、前記迂回対象リンクを利用するトラフィックの始点および終点を示すエッジノードの情報と、迂回路となる始点候補および終点候補として当該トラフィックの経路において前記迂回対象リンクの上流側の輻輳始点を頂点とするツリー構造に含まれるノードと、当該リンクの下流側の輻輳終点を頂点とするツリー構造に含まれるノードとの情報とを示す端点候補情報を抽出する端点候補抽出ステップと、
前記トラフィック交流情報取得手段によって、前記端点候補情報を前記トラフィック交流情報作成装置に通知することで、前記トラフィック交流情報作成装置から、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を取得するトラフィック交流情報取得ステップと、
前記取得したトラフィック交流情報と前記端点候補情報とをトラフィック交流情報データベースに記録するステップと、
前記迂回対象トラフィック量決定手段によって、前記迂回対象リンクに関する情報と前記トラフィック交流情報データベースに記憶されたトラフィック交流情報および前記端点候補情報とを利用して、前記迂回対象リンクに流れているトラフィック量を特定し、前記目標帯域データベースから前記迂回対象リンクに設定されている目標帯域を取得し、取得した目標帯域と前記迂回対象リンクに流れているトラフィック量との差分を示す所定範囲を前記迂回対象トラフィック量として決定する迂回対象トラフィック量決定ステップと、
前記迂回端点決定手段によって、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報に基づいて、トラフィックマトリクスの分割を行い、前記端点候補情報における１つの始点候補と組になる対向側の終点候補すべての組についてマトリクス要素で示される帯域の合計値が、前記決定された迂回対象トラフィック量の範囲に含まれるか否かについて、前記迂回対象リンクの上流側および下流側の前記ツリー構造のそれぞれの頂点から下の階層へ向かって前記トラフィック交流情報の大きい順に探索し、前記帯域の合計値が前記迂回対象トラフィック量の範囲に含まれるような組み合わせの始点候補および終点候補を前記迂回路の始点および終点として決定する迂回端点決定ステップと、
前記経路計算手段によって、前記決定された迂回路の始点と終点とを連結する経路の計算を行うことで前記迂回経路を決定する経路計算ステップとを含んで実行することを特徴とする迂回経路決定方法。
【請求項７】
前記迂回経路決定装置は、
前記経路計算ステップの前に、前記経路計算手段によって、前記ネットワーク情報収集装置から、前記ネットワークのトポロジ情報およびトラフィック情報を取得する情報取得ステップと、
前記取得したネットワークのトポロジ情報から、前記迂回対象トラフィック量が収容できないリンク利用状態のリンクを取り除いた経路計算用のトポロジ情報を作成する計算用トポロジ情報作成ステップとをさらに実行し、
前記経路計算ステップにて、前記作成した経路計算用のトポロジ情報を用いて、前記迂回路の始点から終点までの最短経路を前記迂回経路として計算し、
前記迂回路の始点から終点までの経路が得られなかった場合には、前記迂回端点決定手段によって、前記迂回端点決定ステップにて、新たな迂回路の始点と終点を決定することを特徴とする請求項６に記載の迂回経路決定方法。
【請求項８】
前記迂回経路決定装置は、
前記トラフィック退避要求受付手段によって、前記トラフィック退避要求を取得する前に予め、前記ネットワーク情報収集装置から取得した前記ネットワークのトポロジ情報およびトラフィック情報に基づいて前記ネットワーク全体に共通に設定する、リンクの最大帯域に対するリンク利用率の所定範囲を前記目標帯域として算出し、前記目標帯域データベースに格納する目標帯域算出ステップをさらに実行することを特徴とする請求項６または請求項７に記載の迂回経路決定方法。
【請求項９】
前記迂回経路決定装置は、
前記迂回パス設定要求手段によって、前記ネットワーク情報収集装置から取得したネットワークのトポロジ情報から、前記経路計算ステップで決定された迂回経路のメトリックを計算し、このメトリックとして迂回元の経路よりも小さい値を算出し、迂回パスとしてＭＰＬＳまたはＧＭＰＬＳのパスを設定する迂回パス設定装置に対して、迂回パス設定要求と、前記経路計算ステップで決定された迂回経路の経路情報と、前記迂回経路のメトリックの情報とを通知する迂回パス設定要求ステップをさらに実行することを特徴とする請求項６ないし請求項８のいずれか一項に記載の迂回経路決定方法。
【請求項１０】
前記迂回経路決定装置は、
前記迂回パス設定要求手段によって、トラフィックの終点となるＩＰアドレス・ネットワークアドレスに関してスタティックルーティングの設定を行い、ＭＰＬＳまたはＧＭＰＬＳのパスを利用するようにパス設定を行う迂回パス設定装置、または、指定されたネットワークノード間で通信パケットのマーキングの設定を行い前記迂回対象リンクを利用しているトラフィックが前記指定された経路を利用するようにパス設定を行う迂回パス設定装置のいずれかに対して、迂回パス設定要求と、前記経路計算ステップで決定された迂回経路の経路情報とを通知する迂回パス設定要求ステップをさらに実行することを特徴とする請求項６ないし請求項８のいずれか一項に記載の迂回経路決定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおいてリンク利用率が上昇した場合や輻輳が発生した場合に、過剰なトラフィックを退避させることでネットワークのリンク利用率を平準化する技術に関する。
【背景技術】
【０００２】
一般的に、インターネットなどのネットワークの経路を選択するダイナミックルーティングプロトコルとして、例えばＯＳＰＦ（Open Shortest Path First）やＢＧＰ（Border Gateway Protocol）が用いられている。例えば、利用者の需要を考慮してＯＳＰＦの重みを最適化することによってインターネットのトラフィック制御を行う技術が知られている（非特許文献１参照）。従来、このようなネットワークにおいて、リンク利用率が上昇したりや輻輳が発生した場合に、その問題を解消してネットワークのリンク利用率を平準化するために、ＯＳＰＦのメトリック（metric）を調節したり、ＢＧＰの属性値(Path Attribute)を調節したりしている。
【０００３】
また、ネットワークのトラフィック制御を行うことで自由に経路を設定できる技術としてＭＰＬＳ（Multi-Protocol Label Switching）が知られている。経路を設定する対象のネットワークのリンク接続をメッシュトポロジ（Mesh Topology）で表し、ＭＰＬＳのＬＳＰ（Label Switched Path）をフルメッシュ（Full Mesh）に設定しておけば、リンク利用率が上昇したりや輻輳が発生した場合に、迂回させるトラフィックを選別することは容易になる。
【非特許文献１】B. Fortz, M. Thorup, ”Internet Traffic Engineering by Optimizing OSPF Weights”，INFOCOM2000, Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings, IEEE, vol.2, pp. 519-528
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来のＯＳＰＦのメトリックを調節したりＢＧＰの属性値を調節したりする方法の場合、非常に複雑な計算を行う必要があるため以下の問題がある。すなわち、ネットワークオペレータの判断でメトリック等を決定する場合には、手作業が含まれるため設定完了までに多大な時間を要する。また、自動的にメトリック等の計算を行う場合には、最適な値を算出するまでに多大な時間を要する。
【０００５】
また、ＭＰＬＳのＬＳＰをフルメッシュに設定しておく場合には、フルメッシュにしない場合に比べて、設定対象とするＬＳＰの本数が多い。このＬＳＰの本数は、ネットワークノードの個数が増加するにつれて、幾何級数的に増大する。そのため、ＬＳＰの管理に手間がかかり、大規模なネットワークに適用することができなくなってしまう。
【０００６】
そこで、本発明では、前記した問題を解決し、リンク利用率が上昇したリンクや輻輳が発生したリンクから、過剰なトラフィックを迅速に退避させることのできる技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
前記課題を解決するため、請求項１に記載の迂回経路決定装置は、ネットワークを構成する各ネットワークノードからネットワークのトラフィック情報とトポロジ情報とを取得してリンク利用率が上昇したかまたは輻輳が発生した１以上の連続したリンクを迂回対象リンクとして検出するネットワーク情報収集装置と、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を作成するトラフィック交流情報作成装置と、前記迂回対象リンクを利用しているトラフィックの一部を迂回させる迂回経路を決定する迂回経路決定装置と、前記迂回経路にパスを新たに設定する迂回パス設定装置とを備える通信システムの前記迂回経路決定装置であって、前記ネットワーク情報収集装置から、前記迂回対象リンクに関する情報をトラフィック退避要求と共に取得するトラフィック退避要求受付手段と、前記ネットワーク情報収集装置からネットワークのトポロジ情報を取得し、この取得したトポロジ情報と前記迂回対象リンクに関する情報とを利用することで、前記迂回対象リンクを利用するトラフィックの始点および終点を示すエッジノードの情報と、迂回路となる始点候補および終点候補として当該トラフィックの経路において前記迂回対象リンクの上流側の輻輳始点を頂点とするツリー構造に含まれるノードと、当該リンクの下流側の輻輳終点を頂点とするツリー構造に含まれるノードとの情報とを示す端点候補情報を抽出する端点候補抽出手段と、前記端点候補情報を前記トラフィック交流情報作成装置に通知することで、前記トラフィック交流情報作成装置から、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を取得するトラフィック交流情報取得手段と、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報と前記端点候補情報とを記憶するトラフィック交流情報データベースと、ネットワーク全体に共通に、またはグループ単位に個別に、またはリンク単位に個別に予め設定された、前記迂回対象リンクを利用しているトラフィックのうち迂回させるトラフィック量を示す迂回対象トラフィック量を取り除いた後のトラフィック量の所定範囲またはリンクの最大帯域に対するリンク利用率の所定範囲を、前記迂回対象リンクに設定されている目標帯域として記憶する目標帯域データベースと、前記迂回対象リンクに関する情報と前記トラフィック交流情報データベースに記憶されたトラフィック交流情報および前記端点候補情報とを利用して、前記迂回対象リンクに流れているトラフィック量を特定し、前記目標帯域データベースから前記迂回対象リンクに設定されている目標帯域を取得し、取得した目標帯域と前記迂回対象リンクに流れているトラフィック量との差分を示す所定範囲を前記迂回対象トラフィック量として決定する迂回対象トラフィック量決定手段と、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報に基づいて、トラフィックマトリクスの分割を行い、前記端点候補情報における１つの始点候補と組になる対向側の終点候補すべての組についてマトリクス要素で示される帯域の合計値が、前記決定された迂回対象トラフィック量の範囲に含まれるか否かについて、前記迂回対象リンクの上流側および下流側の前記ツリー構造のそれぞれの頂点から下の階層へ向かって前記トラフィック交流情報の大きい順に探索し、前記帯域の合計値が前記迂回対象トラフィック量の範囲に含まれるような組み合わせの始点候補および終点候補を前記迂回路の始点および終点として決定する迂回端点決定手段と、前記決定された迂回路の始点と終点とを連結する経路の計算を行うことで前記迂回経路を決定する経路計算手段とを備えることを特徴とする。
【０００８】
また、前記課題を解決するため、請求項６に記載の迂回経路決定方法は、ネットワークを構成する各ネットワークノードからネットワークのトラフィック情報とトポロジ情報とを取得してリンク利用率が上昇したかまたは輻輳が発生した１以上の連続したリンクを迂回対象リンクとして検出するネットワーク情報収集装置と、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を作成するトラフィック交流情報作成装置と、前記迂回対象リンクを利用しているトラフィックの一部を迂回させる迂回経路を決定する迂回経路決定装置と、前記迂回経路にパスを新たに設定する迂回パス設定装置とを備える通信システムの前記迂回経路決定装置による迂回経路決定方法であって、前記迂回経路決定装置が、トラフィック退避要求受付手段と、端点候補抽出手段と、トラフィック交流情報取得手段と、迂回対象トラフィック量決定手段と、迂回端点決定手段と、経路計算手段と、迂回パス設定要求手段とネットワーク全体に共通に、またはグループ単位に個別に、またはリンク単位に個別に予め設定された、前記迂回対象リンクを利用しているトラフィックのうち迂回させるトラフィック量を示す迂回対象トラフィック量を取り除いた後のトラフィック量の所定範囲またはリンクの最大帯域に対するリンク利用率の所定範囲を、前記迂回対象リンクに設定されている目標帯域として記憶する目標帯域データベースとを備え、前記トラフィック退避要求受付手段によって、前記ネットワーク情報収集装置から前記迂回対象リンクに関する情報をトラフィック退避要求と共に取得するステップと、前記端点候補抽出手段によって、前記ネットワーク情報収集装置からネットワークのトポロジ情報を取得するステップと、前記迂回対象リンクに関する情報と前記ネットワークのトポロジ情報とを利用することで、前記迂回対象リンクを利用するトラフィックの始点および終点を示すエッジノードの情報と、迂回路となる始点候補および終点候補として当該トラフィックの経路において前記迂回対象リンクの上流側の輻輳始点を頂点とするツリー構造に含まれるノードと、当該リンクの下流側の輻輳終点を頂点とするツリー構造に含まれるノードとの情報とを示す端点候補情報を抽出する端点候補抽出ステップと、前記トラフィック交流情報取得手段によって、前記端点候補情報を前記トラフィック交流情報作成装置に通知することで、前記トラフィック交流情報作成装置から、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を取得するトラフィック交流情報取得ステップと、前記取得したトラフィック交流情報と前記端点候補情報とをトラフィック交流情報データベースに記録するステップと、前記迂回対象トラフィック量決定手段によって、前記迂回対象リンクに関する情報と前記トラフィック交流情報データベースに記憶されたトラフィック交流情報および前記端点候補情報とを利用して、前記迂回対象リンクに流れているトラフィック量を特定し、前記目標帯域データベースから前記迂回対象リンクに設定されている目標帯域を取得し、取得した目標帯域と前記迂回対象リンクに流れているトラフィック量との差分を示す所定範囲を前記迂回対象トラフィック量として決定する迂回対象トラフィック量決定ステップと、前記迂回端点決定手段によって、前記迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報に基づいて、トラフィックマトリクスの分割を行い、前記端点候補情報における１つの始点候補と組になる対向側の終点候補すべての組についてマトリクス要素で示される帯域の合計値が、前記決定された迂回対象トラフィック量の範囲に含まれるか否かについて、前記迂回対象リンクの上流側および下流側の前記ツリー構造のそれぞれの頂点から下の階層へ向かって前記トラフィック交流情報の大きい順に探索し、前記帯域の合計値が前記迂回対象トラフィック量の範囲に含まれるような組み合わせの始点候補および終点候補を前記迂回路の始点および終点として決定する迂回端点決定ステップと、前記経路計算手段によって、前記決定された迂回路の始点と終点とを連結する経路の計算を行うことで前記迂回経路を決定する経路計算ステップとを含んで実行することを特徴とする。
【０００９】
請求項１に記載の迂回経路決定装置または請求項６に記載の迂回経路決定方法によれば、迂回経路決定装置は、ネットワークにおいて、迂回対象リンクに関する情報を取得したときに、ネットワークのトポロジ情報から迂回路の始点候補および終点候補を抽出する。そして、迂回経路決定装置は、迂回対象リンクを実際に利用しているトラフィックと目標帯域とに基づいて、迂回対象トラフィック量を決定する。そして、迂回経路決定装置は、迂回対象トラフィック量と実際の交流トラフィック情報とにより、迂回路の始点候補および終点候補の中から最適な迂回路の始点と終点とを決定し、始点と終点間の経路の計算を行う。これに基づいて、迂回パス設定装置は、迂回経路にパスを設定する。したがって、迂回経路決定装置は、迂回対象リンクが検出されたときのリンク利用状況に応じて、ネットワーク全体の中で決定された始点と終点間の経路について経路の計算を行うので、過剰なトラフィックを退避させることのできる迂回経路を迅速に決定できる。
【００１０】
また、請求項２に記載の迂回経路決定装置は、請求項１に記載の迂回経路決定装置において、前記経路計算手段が、前記ネットワーク情報収集装置から、前記ネットワークのトポロジ情報およびトラフィック情報を取得し、前記取得したネットワークのトポロジ情報から、前記迂回対象トラフィック量が収容できないリンク利用状態のリンクを取り除いた経路計算用のトポロジ情報を作成し、前記作成した経路計算用のトポロジ情報を用いて、前記迂回路の始点から終点までの最短経路を前記迂回経路として計算し、前記迂回路の始点から終点までの経路が得られなかった場合には、新たな迂回路の始点と終点を決定するように前記迂回端点決定手段に対して要求することを特徴とする。
【００１１】
また、請求項７に記載の迂回経路決定方法は、請求項６に記載の迂回経路決定方法において、前記迂回経路決定装置が、前記経路計算ステップの前に、前記経路計算手段によって、前記ネットワーク情報収集装置から、前記ネットワークのトポロジ情報およびトラフィック情報を取得する情報取得ステップと、前記取得したネットワークのトポロジ情報から、前記迂回対象トラフィック量が収容できないリンク利用状態のリンクを取り除いた経路計算用のトポロジ情報を作成する計算用トポロジ情報作成ステップとをさらに実行し、前記経路計算ステップにて、前記作成した経路計算用のトポロジ情報を用いて、前記迂回路の始点から終点までの最短経路を前記迂回経路として計算し、前記迂回路の始点から終点までの経路が得られなかった場合には、前記迂回端点決定手段によって、前記迂回端点決定ステップにて、新たな迂回路の始点と終点を決定することを特徴とする。
【００１２】
請求項２に記載の迂回経路決定装置または請求項７に記載の迂回経路決定方法によれば、迂回経路決定装置は、迂回対象トラフィック量が収容できないリンク利用状態のリンクを取り除いた経路計算用のトポロジ情報を作成して最短経路を計算するので、取得したネットワークのトポロジ情報をそのまま用いた場合に比べて、最短経路を計算するために必要なネットワークノードの個数が少なくなり、最短経路を高速に計算できる。また、たとえ最短経路が一度で得られなかったとしても、新たに取得した始点および終点を用いて最短経路を計算することができる。
【００１３】
また、請求項３に記載の迂回経路決定装置は、請求項１または請求項２に記載の迂回経路決定装置において、前記退避要求受付手段が、前記トラフィック退避要求を取得する前に予め、前記ネットワーク情報収集装置から、前記ネットワークのトポロジ情報およびトラフィック情報を取得し、前記取得したネットワークのトポロジ情報およびトラフィック情報に基づいて前記ネットワーク全体に共通に設定する、リンクの最大帯域に対するリンク利用率の所定範囲を前記目標帯域として算出し、前記目標帯域データベースに格納することを特徴とする。
【００１４】
また、請求項８に記載の迂回経路決定方法は、請求項６または請求項７に記載の迂回経路決定方法において、前記迂回経路決定装置が、前記トラフィック退避要求受付手段によって、前記トラフィック退避要求を取得する前に予め、前記ネットワーク情報収集装置から取得した前記ネットワークのトポロジ情報およびトラフィック情報に基づいて前記ネットワーク全体に共通に設定する、リンクの最大帯域に対するリンク利用率の所定範囲を前記目標帯域として算出し、前記目標帯域データベースに格納する目標帯域算出ステップをさらに実行することを特徴とする。
【００１５】
請求項３に記載の迂回経路決定装置または請求項８に記載の迂回経路決定方法によれば、迂回経路決定装置は、トラフィック退避要求を受け付ける前に、最新のネットワークのトポロジ情報およびトラフィック情報を取得して最新のネットワークの利用状況を反映した目標帯域を算出することができる。したがって、算出された目標帯域を用いることで現状のリンク利用状況に応じて過剰なトラフィックを退避させることのできる最適な迂回経路を決定することができる。
【００１６】
また、請求項４に記載の迂回経路決定装置は、請求項１ないし請求項３のいずれか一項に記載の迂回経路決定装置において、前記経路計算手段で決定された迂回経路の経路情報を取得し、前記ネットワーク情報収集装置から前記ネットワークのトポロジ情報を取得し、前記取得したネットワークのトポロジ情報から、前記迂回経路のメトリックを計算し、このメトリックとして迂回元の経路よりも小さい値を算出し、迂回パスとしてＭＰＬＳ（Multi-Protocol Label Switching）またはＧＭＰＬＳ（Generalized Multi-Protocol Label Switching）のパスを設定する迂回パス設定装置に対して、迂回パス設定要求と、前記迂回経路の経路情報と、前記迂回経路のメトリックの情報とを通知する迂回パス設定要求手段をさらに備えることを特徴とする。
【００１７】
また、請求項９に記載の迂回経路決定方法は、請求項６ないし請求項８のいずれか一項に記載の迂回経路決定方法において、前記迂回経路決定装置が、前記迂回パス設定要求手段によって、前記ネットワーク情報収集装置から取得したネットワークのトポロジ情報から、前記経路計算ステップで決定された迂回経路のメトリックを計算し、このメトリックとして迂回元の経路よりも小さい値を算出し、迂回パスとしてＭＰＬＳまたはＧＭＰＬＳのパスを設定する迂回パス設定装置に対して、迂回パス設定要求と、前記経路計算ステップで決定された迂回経路の経路情報と、前記迂回経路のメトリックの情報とを通知する迂回パス設定要求ステップをさらに実行することを特徴とする。
【００１８】
請求項４に記載の迂回経路決定装置または請求項９に記載の迂回経路決定方法によれば、迂回経路決定装置は、ＭＰＬＳまたはＧＭＰＬＳのパスを設定する迂回パス設定装置に対して、迂回パス設定要求と、迂回経路の経路情報と、迂回経路のメトリックの情報とを通知する。したがって、通知を受けた迂回パス設定装置が迂回経路の経路情報とメトリックの情報を用いて迂回パスを設定することで迂回対象リンクの過剰トラフィックを退避させることができる。さらに、ＭＰＬＳまたはＧＭＰＬＳのパスを設定する既存の迂回パス設定装置が設置されたネットワークに対してこの迂回経路決定装置を適用することで、装置コストを抑制することができる。
【００１９】
また、請求項５に記載の迂回経路決定装置は、請求項１ないし請求項３のいずれか一項に記載の迂回経路決定装置において、前記経路計算手段で決定された迂回経路の経路情報を取得し、トラフィックの終点となるＩＰアドレス・ネットワークアドレスに関してスタティックルーティングの設定を行い、ＭＰＬＳまたはＧＭＰＬＳのパスを利用するようにパス設定を行う迂回パス設定装置、または、指定されたネットワークノード間で通信パケットのマーキングの設定を行い前記迂回対象リンクを利用しているトラフィックが前記指定された経路を利用するようにパス設定を行う迂回パス設定装置のいずれかに対して、迂回パス設定要求と、前記決定された迂回経路の経路情報とを通知する迂回パス設定要求手段をさらに備えることを特徴とする。
【００２０】
また、請求項１０に記載の迂回経路決定方法は、請求項６ないし請求項８のいずれか一項に記載の迂回経路決定方法において、前記迂回経路決定装置が、前記迂回パス設定要求手段によって、トラフィックの終点となるＩＰアドレス・ネットワークアドレスに関してスタティックルーティングの設定を行い、ＭＰＬＳまたはＧＭＰＬＳのパスを利用するようにパス設定を行う迂回パス設定装置、または、指定されたネットワークノード間で通信パケットのマーキングの設定を行い前記迂回対象リンクを利用しているトラフィックが前記指定された経路を利用するようにパス設定を行う迂回パス設定装置のいずれかに対して、迂回パス設定要求と、前記経路計算ステップで決定された迂回経路の経路情報とを通知する迂回パス設定要求ステップをさらに実行することを特徴とする。
【００２１】
請求項５に記載の迂回経路決定装置または請求項１０に記載の迂回経路決定方法によれば、迂回経路決定装置は、スタティックルーティングを設定する迂回パス設定装置、または、パケットのマーキングを設定する迂回パス設定装置のいずれかに対して、迂回パス設定要求と、迂回経路の経路情報とを通知する。したがって、通知を受けた迂回パス設定装置が迂回経路の経路情報を用いて迂回パスを設定することで迂回対象リンクの過剰トラフィックを退避させることができる。また、迂回経路決定装置は、迂回経路のメトリックの情報を計算する必要がないので処理負荷を低減すると共に迂回パス設定要求を早く通知することができる。
【発明の効果】
【００２２】
本発明によれば、迂回経路決定装置は、迂回対象リンクが検出されたときのリンク利用状況に応じて、過剰なトラフィックを退避させる迂回経路を迅速に決定できる。そのため、大規模なネットワークに適用可能であり、かつ、リンク利用率が上昇した場合や輻輳が発生した場合にネットワークのリンク利用率の平準化を高速に行うことができる。
【発明を実施するための最良の形態】
【００２３】
以下、図面を参照して本発明の迂回経路決定装置および迂回経路決定方法を実施するための最良の形態（以下「実施形態」という）について詳細に説明する。ここでは、本発明の迂回経路決定装置を含む通信システムの構成、次いで、ネットワークにおいてリンク利用率が上昇したリンクや輻輳が発生したリンク（迂回対象リンク）の例、さらに、迂回対象リンクから過剰なトラフィックを迅速に退避させる迂回経路決定装置を含む通信システムの各装置の構成、最後に、通信システム全体の動作について順次説明する。
【００２４】
［通信システム］
図１は、過剰トラフィックの退避が実施される通信システムの全体構成を示す図である。図１に示すように、通信システム１は、ネットワーク事業者が運用するバックボーンネットワーク２と、一般の利用者（ユーザ）が運用する複数のユーザネットワーク３（３ａ，３ｂ，３ｃ，３ｄ，３ｅ，３ｆ，３ｇ，３ｈ，３ｉ，３ｊ）とを備えている。本実施形態では、バックボーンネットワーク２と、各ユーザネットワーク３とは、ＩＰ（Internet Protocol）による通信装置を有し、ＩＰを利用した通信が可能であることとする。なお、通信システム１は、ＩＰｖ６（Internet Protocol Version６）等により構成されたネットワークで実現することもできる。
【００２５】
バックボーンネットワーク２は、広帯域なリンクで構成され、ＯＳＰＦプロトコルや、ＢＧＰプロトコルによって、ネットワークの経路が管理されている。また、本実施形態では、ＭＰＬＳやＧＭＰＬＳによりトラフィックの経路を自由に設計することが可能であるものとする。バックボーンネットワーク２は、ネットワークノード１０１，１０２，１０３，１０４，１０５，１０６，１０７，１０８を備えている。バックボーンネットワーク２と、各ユーザネットワーク３とは、エッジルータ１１１，１１２，１１３，１１４，１１５，１１６，１１７，１１８により接続されている。ネットワークノードやエッジルータは、例えば、光クロスコネクト（ＯＸＣ：Optical Cross Connect）、ルータ、スイッチ等からなる装置である。なお、前記したネットワークノード、エッジルータ、ユーザネットワークの個数は特に限定されるものではない。
【００２６】
ユーザネットワーク３は、例えばイーサネット（登録商標）のようなＬＡＮ（Local Area Network）のネットワークケーブル（図示せず）が、ネットワークハブ（図示せず）、ルータ（図示せず）、ユーザエッジ（図示せず）の各インターフェイス（図示せず）に接続されて構成されている。
【００２７】
通信システム１は、迂回経路決定装置２００と、ネットワーク情報収集装置３００と、迂回パス設定装置４００と、トラフィック交流情報作成装置５００とを備える。迂回経路決定装置２００と、ネットワーク情報収集装置３００と、迂回パス設定装置４００と、トラフィック交流情報作成装置５００は、例えば、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、ＨＤＤ（Hard Disk Drive）と、通信を行うためのＮＩＣ（Network Interface Card）等を備えている。
【００２８】
迂回経路決定装置２００は、ネットワーク情報収集装置３００で検出された迂回対象リンクを利用しているトラフィックの一部を迂回させる迂回経路を決定するものである。
【００２９】
ネットワーク情報収集装置３００は、各ネットワークノード１０１〜１０８からネットワークのトラフィック情報とトポロジ情報とを取得してリンク利用率が上昇したかまたは輻輳が発生した１以上の連続したリンクを迂回対象リンクとして検出するものである。
【００３０】
迂回パス設定装置４００は、迂回経路決定装置２００で決定された迂回経路にパスを新たに設定するものである。本実施形態では、迂回パス設定装置４００は、迂回パスとしてＭＰＬＳまたはＧＭＰＬＳのパスを設定することとする。
【００３１】
トラフィック交流情報作成装置５００は、ネットワーク情報収集装置３００で検出された迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を作成するものである。なお、トラフィック交流情報は一方向のトラフィック情報だけではなく、他方向のトラフィック情報を含むトラフィック情報を示す。
【００３２】
［迂回対象リンクの例］
次に、本発明の実施形態に係る迂回経路決定装置２００で扱う迂回対象リンクの例について図６および図７を参照して説明する。図６は、迂回対象リンクの一例を示す構成図であり、図７は、迂回経路決定装置による迂回対象のトラフィックを決定する方法の一例を示す説明図である。図６の例では、２つのノード（輻輳始点６０１、輻輳終点６０２）を接続するリンクが迂回対象リンクであるものとする。ここでは、具体的には、この２つのノード（輻輳始点６０１、輻輳終点６０２）を接続するリンクには、例えば、１Ｇｂｐｓの帯域がリンクの最大帯域として設定されていることとする。この例では、このリンクに、最大帯域を超える１．２Ｇｂｐｓのトラフィックが利用されている。また、迂回端点決定手段２５０が取得する迂回対象とする目標トラフィック量を５００〜７００Ｍｂｐｓであるものとする。
【００３３】
輻輳リンク（迂回対象リンク）６０３を利用しているトラフィックの経路は、輻輳リンク６０３の上流（一方）に輻輳始点６０１を頂点（ルート）とするツリー構造と、輻輳リンク６０３の下流（他方）に輻輳終点６０２を頂点（ルート）とするツリー構造とから形成されているものとして表現できる。迂回経路決定装置２００は、輻輳リンク６０３を利用していうるトラフィックのうちから迂回させるべきトラフィック量（迂回対象トラフィック量）に対応した始点および終点を検出する目的で、まず、迂回路の始点候補と終点候補とを設定するために図６のツリー構造を利用する。なお、経路が計算された迂回路のことを迂回経路と呼ぶこととする。つまり、迂回路という場合には、始点または終点を示す端点（迂回端点）しか定まっておらず、まだ経路が計算されていないものとする。
【００３４】
迂回端点となるべき候補としての最初の始点候補は、図６において符号Ａで示すノード（以下、「ノードＡ」という）と、図６において符号Ｂで示すノード（以下、「ノードＢ」という）である。同様に、最初の終点候補は、「ノードＣ」と「ノードＤ」である。迂回経路決定装置２００は、次の始点候補および終点候補として、ツリー上で１階層下のすべてのノードを追加する。つまり、追加される始点候補は、「ノードＡ−１」、「ノードＡ−２」、「ノードＡ−３」、「ノードＢ−１」、「ノードＢ−２」である。同様に、次の階層に追加される終点候補は、「ノードＤ−１」、「ノードＤ−２」である。さらに下の階層に追加される始点候補は、「ノードＡ−１−１」、「ノードＢ−１−１」、「ノードＢ−１−２」である。
【００３５】
迂回経路決定装置２００（後記する迂回端点決定手段２５０）は、以下の処理を行う。すなわち、迂回経路決定装置２００は、図６に示すツリー構造を探索する処理に合わせて図７に示すトラフィックマトリクスの分割を行う。そして、迂回経路決定装置２００は、追加した始点候補（または終点候補）と組になる対向側の終点候補（または始点候補）すべての組の中で、退避に適したトラフィックがあるか否かを探索する。この例では、退避に適したトラフィックは、退避処理後の迂回パス（迂回経路にパス設定がされたパス）の目標帯域を示す５００〜７００Ｍｂｐｓとして設定されているものとしている。図７の例では、始点候補「ノードＡ−１−１」を始点として、終点候補「ノードＣ」を終点とするトラフィックの利用する帯域（交流トラフィック量）は、１００Ｍｂｐｓである。また、始点候補「ノードＡ−１−１」を始点として、終点候補「ノードＤ−１」を終点とする交流トラフィック量は、２００Ｍｂｐｓである。以下、同様に、図７では合計１８個のマトリクス要素として帯域（交流トラフィック量）が記載されている。
【００３６】
符号７０１で示した６個のマトリクス要素で示される帯域の合計値は、５６０Ｍｂｐｓである。その帯域の合計値は、５００＜５６０＜７００の関係から目標帯域（５００〜７００Ｍｂｐｓ）に含まれるものである。したがって、図７に示した例では、輻輳始点「ノードＢ−１」から、輻輳終点「ノードＣ，ノードＤ−１，ノードＤ２」までのトラフィックが、迂回対象トラフィック量（目標帯域）に対応することとなる。その結果、「ノードＢ−１」が迂回路の始点として決定される。また、「ノードＣ，ノードＤ−１，ノードＤ２」が迂回路の終点としてそれぞれ決定される。この迂回路の始点と終点の情報から、これらを連結する経路が計算されて迂回経路が決定されることとなる。そして、この迂回経路にパスが設定され（迂回パス）、輻輳リンク６０３（迂回対象リンク）から過剰なトラフィックを迅速に退避させることが可能となる。
【００３７】
このように例えば輻輳リンク６０３（迂回対象リンク）から過剰なトラフィックを迅速に退避させる機能を実現する装置として、以下、迂回経路決定装置２００と、ネットワーク情報収集装置３００と、迂回パス設定装置４００と、トラフィック交流情報作成装置５００についてその詳細な構成を説明する。
【００３８】
［迂回経路決定装置］
図２は、本発明の実施形態に係る迂回経路決定装置の一例を模式的に示すブロック図である。迂回経路決定装置２００は、退避要求受付手段２１０と、端点候補抽出手段２２０と、トラフィック交流情報取得手段２３０と、迂回対象トラフィック量決定手段２４０と、迂回端点決定手段２５０と、経路計算手段２６０と、迂回パス設定要求手段２７０とを備えている。
【００３９】
＜退避要求受付手段＞
退避要求受付手段２１０は、ネットワーク情報収集装置３００から、迂回対象リンクを検出したことを示すトラフィック退避要求を受け付けるものである。本実施形態では、退避要求受付手段２１０は、ネットワーク情報収集装置３００からトラフィック退避要求の通知を受信することとする。ここで、迂回対象リンクは、隣り合った２つのネットワークノード間の１つのリンクを示すだけではなく、２つ以上の連続したリンクのことも意味する。なお、退避要求受付手段２１０から、ネットワーク情報収集装置３００に対して、迂回対象リンクを検出したか否かについて定期的または不定期に問い合わせるように構成することも可能である。
【００４０】
本実施形態では、退避要求受付手段２１０は、トラフィック退避要求と迂回対象リンクに関する情報とを受信したときに迂回経路の決定手続きを開始する。具体的には、退避要求受付手段２１０は、端点候補抽出手段２２０、トラフィック交流情報取得手段２３０、迂回対象トラフィック量決定手段２４０および迂回端点決定手段２５０に対して以下の処理動作を要求する。
【００４１】
退避要求受付手段２１０は、端点候補抽出手段２２０に対して、迂回対象リンクに関する情報を通知すると共に、端点候補情報の取得を要求する（端点候補情報要求を出力する）。端点候補情報は、迂回対象リンクを利用するトラフィックの始点および終点を示すネットワークノードの対の情報（エッジノードの情報）と、迂回路となる始点候補および終点候補の情報を示す。
【００４２】
退避要求受付手段２１０は、トラフィック交流情報取得手段２３０に対して、端点候補情報を通知すると共に、迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報の取得を要求する（トラフィック交流情報取得要求を出力する）。
【００４３】
退避要求受付手段２１０は、迂回対象トラフィック量決定手段２４０に対して、迂回対象リンクに関する情報を通知すると共に、迂回対象トラフィック量の決定を要求する（迂回対象トラフィック量決定要求を出力する）。迂回対象トラフィック量は、迂回対象リンクを利用しているトラフィックのうち迂回させるトラフィック量を示す。
【００４４】
退避要求受付手段２１０は、迂回端点決定手段２５０に対して、迂回対象トラフィック量を通知すると共に、迂回端点の決定を要求する（迂回端点決定要求を出力する）。
【００４５】
また、本実施形態では、退避要求受付手段２１０は、ネットワーク情報収集装置３００から、ネットワークのトポロジ情報およびトラフィック情報を取得し、取得したネットワークのトポロジ情報およびトラフィック情報に基づいてネットワーク全体のリンク利用率を目標帯域として算出する。算出された目標帯域は、目標帯域ＤＢ２９０に格納される。なお、目標帯域を算出するためにネットワークのトポロジ情報およびトラフィック情報を取得する方法は、任意である。以下では、取得という場合、受動的に取得先の装置から定期的または不定期に通知を受けることと、能動的に取得先の装置に対して定期的または不定期に情報の取得を要求することの両方を含むこととする。
【００４６】
＜端点候補抽出手段＞
端点候補抽出手段２２０は、ネットワーク情報収集装置３００から取得したネットワークのトポロジ情報と迂回対象リンクに関する情報とに基づいて、迂回路の始点候補および終点候補としてネットワークノード１０１〜１０８の情報を抽出するものである。端点候補抽出手段２２０は、退避要求受付手段２１０から、端点候補情報要求と迂回対象リンクに関する情報とを受けたときに、ネットワーク情報収集装置３００に対して、ネットワークトポロジ情報を要求する（ネットワークトポロジ情報要求を出力する）。端点候補抽出手段２２０は、取得したネットワークトポロジ情報（単にトポロジ情報という）を利用することで、どの対地間のトラフィックが迂回対象リンクを利用しているのかを示す情報として端点候補情報を抽出し、退避要求受付手段２１０に対して通知する。また、本実施形態では、端点候補抽出手段２２０は、迂回対象リンクを利用しているトラフィックの途中経路において、迂回対象リンクより上流（一方）に位置するネットワークノードはすべて迂回路の始点の候補、迂回対象リンクより下流（他方）に位置するネットワークノードはすべて迂回路の終点の候補として定義して抽出する。なお、退避要求受付手段２１０において、迂回対象リンクより上流に位置するネットワークノードはすべて迂回路の始点の候補、迂回対象リンクより下流に位置するネットワークノードはすべて迂回路の終点の候補として定義して端点候補情報要求を出力するように構成することもできる。
【００４７】
＜トラフィック交流情報取得手段＞
トラフィック交流情報取得手段２３０は、トラフィック交流情報作成装置５００から、迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を取得するものである。トラフィック交流情報取得手段２３０は、退避要求受付手段２１０から、トラフィック交流情報取得要求と、端点候補情報とを受け取り、トラフィック交流情報作成装置５００に対して、端点候補情報を通知すると共に、迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報を要求する（トラフィック交流情報要求を出力する）。トラフィック交流情報取得手段２３０は、取得したトラフィック交流情報と端点候補情報とをトラフィック交流情報ＤＢ２８０に記録する。
【００４８】
＜迂回対象トラフィック量決定手段＞
迂回対象トラフィック量決定手段２４０は、迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報と目標帯域とに基づいて、迂回対象リンクを利用しているトラフィックのうち迂回させるトラフィック量を示す迂回対象トラフィック量を決定するものである。迂回対象トラフィック量決定手段２４０は、退避要求受付手段２１０から、迂回対象トラフィック量決定要求と迂回対象リンクに関する情報とを受け取る。本実施形態では、迂回対象トラフィック量決定手段２４０は、迂回対象リンクに関する情報とトラフィック交流情報ＤＢ２８０に格納されている情報（トラフィック交流情報、端点候補情報）とを利用して、迂回対象リンクに流れているトラフィック量（トラフィック交流情報）を特定する。迂回対象トラフィック量決定手段２４０は、目標帯域ＤＢ２９０から、迂回対象リンクに設定されている目標帯域を取得し、取得した目標帯域と、特定したトラフィック量とから、迂回対象トラフィック量を決定し、退避要求受付手段２１０に対して通知する。なお、図２において破線で示すように、迂回対象トラフィック量決定手段２４０は、トラフィック量（トラフィック交流情報）を独自に特定することなく、ネットワーク情報収集装置３００から通知されたものを活用する構成とすることもできる。
【００４９】
＜迂回端点決定手段＞
迂回端点決定手段２５０は、迂回対象トラフィック量決定手段２４０で決定された迂回対象トラフィック量と迂回対象リンクを利用しているトラフィックに関するトラフィック交流情報とに基づいて、迂回路の始点と終点とを決定するものである。迂回端点決定手段２５０は、退避要求受付手段２１０から、迂回端点決定要求と迂回対象トラフィック量の情報を受け取り、トラフィック交流情報ＤＢ２８０に格納されたトラフィック交流情報を参照して、迂回対象トラフィック量に一致する始点および終点の対を発見し、迂回路の始点および終点を決定する。迂回端点決定手段２５０は、トラフィック交流情報ＤＢ２８０において、迂回路の始点候補と終点候補との間の中でそれぞれ１ノードを選択することで、選択ノード間のトラフィック量を特定することができる。迂回端点決定手段２５０は、経路計算手段２６０に対して、迂回路の始点および終点の情報と、迂回対象トラフィック量の情報とを通知すると共に、その経路の計算を要求する（経路計算要求を出力する）。
【００５０】
＜経路計算手段＞
経路計算手段２６０は、迂回端点決定手段２５０で決定された迂回路の始点と終点とを連結する経路の計算を行うことで迂回経路を決定するものである。経路計算手段２６０は、迂回端点決定手段２５０から、経路計算要求と、迂回路の始点と終点の情報と、迂回対象トラフィック量の情報とを受け取り、ネットワーク情報収集装置３００に対して、ネットワークトポロジ情報とトラフィックに関する情報を要求する（トポロジ・トラフィック情報要求を送信する）。
【００５１】
また、経路計算手段２６０は、ネットワーク情報収集装置３００から、ネットワークのトポロジ情報およびトラフィック情報（トポロジ・トラフィック情報）を取得し、取得したネットワークのトポロジ情報から、迂回対象トラフィック量が収容できないリンク利用状態のリンクを取り除いた経路計算用のトポロジ情報を作成する。経路計算手段２６０は、作成した経路計算用のトポロジ情報を用いて、迂回経路の始点から終点までの最短経路を迂回経路として計算し、最短経路が得られなかった場合には、新たな迂回路の始点と終点を決定するように迂回端点決定手段２５０に対して要求する。ここで、最短経路を計算する方法は、任意であり、例えば、ダイクストラアルゴリズム（Dijkstra algorithm）を利用することができる。経路計算手段２６０は、最短経路が得られた場合には、迂回パス設定要求手段２７０に対して、迂回パスの経路情報を通知すると共に、迂回パスの設定を要求する（迂回パス設定要求を出力する）。
【００５２】
＜迂回パス設定要求手段＞
迂回パス設定要求手段２７０は、経路計算手段２６０で決定された迂回経路の経路情報を取得し、ネットワーク情報収集装置３００からネットワークのトポロジ情報を取得し、取得したネットワークのトポロジ情報から、迂回元の経路よりもメトリックが小さくなるように、経路計算手段２６０で決定された迂回経路のメトリックを計算し、迂回パス設定装置４００に対して迂回パス設定要求と、迂回経路の経路情報と、迂回経路のメトリックの情報とを通知するものである。迂回パス設定要求手段２７０は、経路計算手段２６０から、迂回パス設定要求と迂回経路の経路情報とを受け取り、ネットワーク情報収集装置３００に対して、ネットワークトポロジ情報を要求する（トポロジ情報要求を送信する）。
【００５３】
＜トラフィック交流情報ＤＢ＞
トラフィック交流情報ＤＢ２８０は、トラフィック交流情報取得手段２３０により更新され、迂回端点決定手段２５０によって利用するトラフィック交流情報を記憶するデータベースである。
【００５４】
＜目標帯域ＤＢ＞
目標帯域ＤＢ２９０は、ネットワーク全体、またはグループ単位、またはリンク単位に予め決定された、迂回対象トラフィック量を取り除いた後のトラフィック量またはリンク利用率を目標帯域として記憶するデータベースである。本実施形態では、目標帯域ＤＢ２９０に格納された目標帯域は、退避要求受付手段２１０によって、ネットワークのトポロジ情報およびトラフィック情報に応じて自動的に算出されるものとしている。トラフィック交流情報ＤＢ２８０および目標帯域ＤＢ２９０は、例えば、一般的なハードディスク等に蓄積されている。
【００５５】
なお、退避要求受付手段２１０、端点候補抽出手段２２０、トラフィック交流情報取得手段２３０、迂回対象トラフィック量決定手段２４０、迂回端点決定手段２５０、経路計算手段２６０および迂回パス設定要求手段２７０は、ＣＰＵが記憶手段に格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【００５６】
［ネットワーク情報収集装置］
図３は、図１に示したネットワーク情報収集装置の一例を模式的に示すブロック図である。ネットワーク情報収集装置３００は、図３に示すように、ネットワーク情報収集手段３１０と、ネットワーク情報通知手段３２０と、トポロジ情報ＤＢ３３０と、トラフィック情報ＤＢ３４０とを備えている。
【００５７】
＜ネットワーク情報収集手段＞
ネットワーク情報収集手段３１０は、例えば、ＯＳＰＦ、ＢＧＰ、ＳＮＭＰ（Simple Network Management Protocol）、ＣＬＩ（Command Line Interface）等を利用してバックボーンネットワーク２中のネットワークノード１０１〜１０８と接続を行ってトポロジ情報やトラフィック情報を取得し、取得したトポロジ情報をトポロジ情報ＤＢ３３０に格納し、取得したトラフィック情報をトラフィック情報ＤＢ３４０に格納するものである。
【００５８】
ここで、ネットワーク情報収集手段３１０は、ネットワークノード１０１〜１０８からトポロジ情報を取得するために、ＳＮＭＰを利用して定期的に収集することができる。
【００５９】
また、ネットワーク情報収集手段３１０は、ＯＳＰＦやＢＧＰを利用して、定期的または変更があった際などの不定期に通知を受け取ることによってトポロジ情報を取得することもできる。
【００６０】
また、ネットワーク情報収集手段３１０は、バックボーンネットワーク２中に変化があった場合に、トラップ（例えば、coldStart Trap、linkDown Trap、linkUp Trap）を受信することによって、ネットワーク情報の変化の通知を受けることもできる。
【００６１】
また、ネットワーク情報収集手段３１０は、例えば、ＳＮＭＰ、Ｎｅｔ Ｆｌｏｗ、ｎＦｌｏｗ等を利用して、ネットワークノード１０１〜１０８からからトラフィックに関する情報を定期的に取得することができる。なお、Ｎｅｔ Ｆｌｏｗ、ｎＦｌｏｗは、米国のシスコシステムズ社が開発したトラフィック管理用技術を示す。
【００６２】
また、ネットワーク情報収集手段３１０は、ネットワークノード１０１〜１０８に対して能動的に情報を要求して収集した際、または、ネットワークノード１０１〜１０８から受動的にトラップ等の通知を受けることによって、バックボーンネットワーク２中のリンク利用率の上昇や輻輳を検出する。ネットワーク情報収集手段３１０は、リンク利用率の上昇や輻輳を検出したリンクを迂回対象リンクとして設定し、迂回経路決定装置２００に対して、トラフィック退避要求と迂回対象リンクの情報とを通知する。
【００６３】
＜ネットワーク情報通知手段＞
ネットワーク情報通知手段３２０は、迂回経路決定装置２００やトラフィック交流情報作成装置５００から、トポロジ情報要求、トラフィック情報要求、トポロジ・トラフィック情報要求を受け取り、要求された情報をトポロジ情報ＤＢ３３０やトラフィック情報ＤＢ３４０から読み出して通知するものである。なお、場合によっては、ネットワーク情報通知手段３２０は、トポロジ情報要求、トラフィック情報要求、トポロジ・トラフィック情報要求の情報の条件を受け取り、受け取った条件に応じた情報だけをトポロジ情報ＤＢ３３０やトラフィック情報ＤＢ３４０から読み出し通知することもある。
【００６４】
＜トポロジ情報ＤＢ＞
トポロジ情報ＤＢ３３０は、ネットワーク情報収集手段３１０によって更新が行われ、ネットワークのトポロジに関する情報（ネットワークトポロジ情報）を記憶するデータベースである。
【００６５】
＜トラフィック情報ＤＢ＞
トラフィック情報ＤＢ３４０は、ネットワーク情報収集手段３１０によって更新が行われ、ネットワークのトラフィックに関する情報（トラフィック交流情報等）を記憶するデータベースである。トポロジ情報ＤＢ３３０およびトラフィック情報ＤＢ３４０は、例えば、一般的なハードディスク等に蓄積されている。
【００６６】
［迂回パス設定装置］
図４は、図１に示した迂回パス設定装置の一例を模式的に示すブロック図である。迂回パス設定装置４００は、パス設定手段４１０を備えている。パス設定手段４１０は、迂回経路決定装置２００から、迂回パス設定要求と、迂回パスの経路情報と、迂回パスのメトリックの情報とを受け取り、ＲＳＶＰ（Resource reSerVation Protocol）やＣＬＩ等を利用して、指定した対地間（ネットワークノード間）に、ＭＰＬＳまたはＧＭＰＬＳのパスを設定し、設定したパスに対して、指定されたメトリックを付与するものである。なお、迂回パス設定装置４００は、迂回パス設定要求と共に、迂回トラフィックに関する情報（トラフィック量）も取得するように構成することができる。また、迂回パスの情報は、１つまたは複数の迂回パスに対応させることができる。
【００６７】
［トラフィック交流情報作成装置］
図５は、図１に示したトラフィック交流情報作成装置の一例を模式的に示すブロック図である。トラフィック交流情報作成装置５００は、トラフィック交流情報作成手段５１０を備えている。トラフィック交流情報作成手段５１０は、迂回経路決定装置２００から、トラフィック交流情報要求と、端点候補情報とを受け取る。トラフィック交流情報作成手段５１０は、ネットワーク情報収集装置３００から、ネットワークトポロジ情報やトラフィックに関する情報を要求するか、または通知を受けることにより取得する。トラフィック交流情報作成手段５１０は、端点候補情報と、ネットワークトポロジ情報やトラフィックに関する情報とを利用してトラフィック交流情報を作成し、迂回経路決定装置２００に対して通知する。なお、トラフィック交流情報作成手段５１０は、迂回経路決定装置２００から、トラフィック交流情報要求と、迂回対象リンクに関する情報とを受け取って、迂回対象リンクに関する情報と、ネットワークトポロジ情報やトラフィックに関する情報とを利用してトラフィック交流情報を作成するようにしてもよい。
【００６８】
［通信システムの全体動作］
図１に示した通信システムにおいて過剰トラフィックの退避の実施について図８を参照（適宜図１および図２参照）して説明する。図８は、本発明の実施形態に係る迂回経路決定方法による過剰トラフィックの退避を示すシーケンス図である。予め、ネットワーク情報収集装置３００は、バックボーンネットワーク２のネットワークノード１０１〜１０８から、ネットワークの情報（トポロジ情報、トラフィック情報）を収集しているものとする（ステップＳ１）。また、迂回経路決定装置２００は、現状のネットワークの情報を用いて、目標帯域を算出して目標帯域ＤＢ２９０に格納しているものとする（ステップＳ２：目標帯域算出ステップ）。
【００６９】
ネットワーク情報収集装置３００は、輻輳リンク（迂回対象リンク）を検出する（ステップＳ３）と、迂回対象リンクに関する情報と共にトラフィック退避要求を迂回経路決定装置２００に送信する（ステップＳ４）。迂回経路決定装置２００は、退避要求受付手段２１０によって、トラフィック退避要求を受信する（ステップＳ５：トラフィック退避要求受付ステップ）と、端点候補抽出手段２２０によって、ネットワーク情報収集装置３００に対して、トポロジ情報要求を送信する（ステップＳ６）。
【００７０】
ネットワーク情報収集装置３００は、トポロジ情報要求を受信する（ステップＳ７）と、ネットワークのトポロジ情報を迂回経路決定装置２００に送信する（ステップＳ８）。迂回経路決定装置２００は、端点候補抽出手段２２０によって、ネットワークのトポロジ情報を受信する（ステップＳ９：トポロジ情報取得ステップ）と、ネットワークのトポロジ情報に基づいて迂回対象リンクについての端点候補（端点候補情報）を抽出する（ステップＳ１０：端点候補抽出ステップ）。そして、迂回経路決定装置２００は、トラフィック交流情報取得手段２３０によって、トラフィック交流情報作成装置５００に対して端点候補情報と共にトラフィック交流情報要求を送信する（ステップＳ１１）。
【００７１】
トラフィック交流情報作成装置５００は、トラフィック交流情報要求を受信する（ステップＳ１２）と、ネットワーク情報収集装置３００に対して、トポロジ・トラフィック情報要求を送信する（ステップＳ１３）。ネットワーク情報収集装置３００は、トポロジ・トラフィック情報要求を受信する（ステップＳ１４）と、トポロジ情報ＤＢ３３０およびトラフィック情報ＤＢ３４０から読み出したトポロジ・トラフィック情報をトラフィック交流情報作成装置５００に送信する（ステップＳ１５）。
【００７２】
トラフィック交流情報作成装置５００は、トポロジ・トラフィック情報を受信する（ステップＳ１６）と、迂回対象リンクを利用するトラフィックを示すトラフィック交流情報を作成する（ステップＳ１７）。そして、トラフィック交流情報作成装置５００は、作成したトラフィック交流情報を迂回経路決定装置２００に送信する（ステップＳ１８）。迂回経路決定装置２００は、トラフィック交流情報取得手段２３０によって、迂回対象リンクのトラフィック交流情報を受信する（ステップＳ１９：トラフィック交流情報取得ステップ）。
【００７３】
そして、迂回経路決定装置２００は、迂回対象トラフィック量決定手段２４０によって、トラフィック交流情報ＤＢ２８０および目標帯域ＤＢ２９０を参照して迂回対象トラフィック量を決定する（ステップＳ２０：迂回対象トラフィック量決定ステップ）。そして、迂回経路決定装置２００は、迂回端点決定手段２５０によって、迂回対象トラフィック量に基づいて、迂回路の始点候補および終点候補の中から、迂回路の始点および終点（迂回端点）を決定する（ステップＳ２１：迂回端点決定ステップ）。
【００７４】
そして、迂回経路決定装置２００は、経路計算手段２６０によって、ネットワーク情報収集装置３００に対して、トポロジ情報要求を送信する（ステップＳ２２）。ネットワーク情報収集装置３００は、トポロジ情報要求を受信する（ステップＳ２３）と、トポロジ情報ＤＢ３３０およびトラフィック情報ＤＢ３４０から読み出したトポロジ情報およびトラフィックに関する情報を迂回経路決定装置２００に送信する（ステップＳ２４）。そして、迂回経路決定装置２００は、経路計算手段２６０によって、以下の動作を行う。すなわち、経路計算手段２６０は、トポロジ情報およびトラフィックに関する情報を受信する（ステップＳ２５：情報取得ステップ）。そして、経路計算手段２６０は、受信したトポロジ情報から計算に使用しないリンクを除去した計算用のトポロジ情報を作成する（ステップＳ２６：計算用トポロジ情報作成ステップ）。そして、経路計算手段２６０は、作成した計算用のトポロジ情報を用いて、迂回路の始点・終点を連結する最短経路を計算する（ステップＳ２７：経路計算ステップ）。
【００７５】
ステップＳ２７において、最短経路が得られない場合には、迂回経路決定装置２００は、ステップＳ２１に戻る。一方、ステップＳ２７において、最短経路が得られた場合には、迂回経路決定装置２００は、迂回パス設定要求手段２７０によって、迂回経路のメトリックを計算し、迂回経路の経路情報およびメトリックの情報と共に迂回パス設定要求を迂回パス設定装置４００に送信する（ステップＳ２８：迂回パス設定要求ステップ）。迂回パス設定装置４００は、迂回パス設定要求を受信する（ステップＳ２９）と、迂回経路の経路情報およびメトリックの情報に基づいて、迂回パスを設定する（ステップＳ３０）。
【００７６】
本実施形態によれば、迂回経路決定装置２００は、バックボーンネットワーク２においてリンク利用率が上昇した場合や輻輳が発生した場合に、まず、ネットワークのトポロジ情報から迂回路の始点候補および終点候補を抽出し、迂回対象リンクを利用しているトラフィックと目標帯域とに基づいて、迂回対象トラフィック量を決定する。続いて、迂回経路決定装置は、迂回対象トラフィック量と交流トラフィック情報とにより、最適な迂回路の始点と終点とを決定し、その始点と終点間の経路を計算することで迂回経路を決定する。したがって、迂回経路決定装置２００は、迂回対象リンクが検出されたときのリンク利用状況に応じて、ネットワーク全体の中で決定された迂回路の始点と終点間について経路の計算を行うので、迂回経路を迅速に決定できる。そのため、迂回パス設定装置４００は、この迂回経路にパスを迅速に設定することができる。したがって、迂回対象リンクから、過剰なトラフィックを迅速に退避させることができる。その結果、ネットワークのリンク利用率の平準化を高速に行うことができる。
【００７７】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、本実施形態では、迂回経路決定装置２００の目標帯域ＤＢ２９０に格納された目標帯域は、退避要求受付手段２１０によって、ネットワークのトポロジ情報およびトラフィック情報に応じて自動的に算出されるものとしたが、例えば、ネットワークオペレータが予め入力したり、定期的または非定期に更新入力したりすることで設定できる。この場合の入力方法としては、ネットワークオペレータは、ＦＴＰ（File Transfer Protocol）などのプロトコル通信を利用してネットワークを介して入力することができる。また、ネットワークオペレータは、入力装置（キーボード、マウス、スキャナ等）や記憶媒体（フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フラッシュメモリ等）を用いて迂回経路決定装置２００に直接入力することもできる。
【００７８】
また、本実施形態では、迂回パス設定装置４００は、迂回パスとしてＭＰＬＳまたはＧＭＰＬＳのパスを設定することとして、これに対応するように、迂回経路決定装置２００の迂回パス設定要求手段２７０は、迂回経路のメトリックを計算し、迂回経路のメトリックを迂回経路の経路情報と共に迂回パス設定装置４００に送信することとしたが、本発明はこれに限定されるものではない。以下では、迂回パス設定装置４００および迂回経路決定装置２００の迂回パス設定要求手段２７０のバリエーションを示す。
【００７９】
［迂回パス設定装置のバリエーション１］
バリエーション１の迂回パス設定装置は、図４に示した迂回パス設定装置４００と同様な構成なので同じ符号を付して異なる部分のみ説明する。バリエーション１の迂回パス設定装置４００では、パス設定手段４１０は、迂回経路決定装置２００から、迂回パス設定要求と、迂回パスの経路情報とを受け取り、ＣＬＩ等を利用して、トラフィックの終点となるＩＰアドレス・ネットワークアドレスに関してスタティックルーティング（static routing）の設定を行い、ＭＰＬＳまたはＧＭＰＬＳのパスを利用するようにパス設定を行う。これにより、スタティックルーティングで指定した宛先が設定されたパケットのみが迂回路を選択することとなる。この場合、迂回経路決定装置２００の迂回パス設定要求手段２７０は、迂回経路のメトリックを計算する必要がないので、処理負荷を低減すると共に迂回パス設定要求を迂回パス設定装置４００に対して早く通知することができる。
【００８０】
［迂回パス設定装置のバリエーション２］
バリエーション２の迂回パス設定装置は、図４に示した迂回パス設定装置４００と同様な構成なので同じ符号を付して異なる部分のみ説明する。バリエーション２の迂回パス設定装置４００では、パス設定手段４１０は、迂回経路決定装置２００から、迂回パス設定要求と、迂回パスの経路情報とを受け取り、ＣＬＩ等を利用して、指定した対地間（ネットワークノード間）で通信パケットのマーキング等の設定を行い、迂回対象のトラフィックが、指定した経路を利用するようにパス設定を行う。これにより、例えばネットワークオペレータによるマーキング等で指定した宛先が設定されたパケットのみが迂回路を選択することとなる。この場合、迂回経路決定装置２００の迂回パス設定要求手段２７０は、迂回経路のメトリックを計算する必要がないので、処理負荷を低減すると共に迂回パス設定要求を迂回パス設定装置４００に対して早く通知することができる。
【図面の簡単な説明】
【００８１】
【図１】本発明の実施形態に係る迂回経路決定方法による過剰トラフィックの退避が実施される通信システムの全体構成を示す図である。
【図２】本発明の実施形態に係る迂回経路決定装置の一例を模式的に示すブロック図である。
【図３】図１に示したネットワーク情報収集装置の一例を模式的に示すブロック図である。
【図４】図１に示した迂回パス設定装置の一例を模式的に示すブロック図である。
【図５】図１に示したトラフィック交流情報作成装置の一例を模式的に示すブロック図である。
【図６】本発明の実施形態に係る迂回経路決定装置で扱う迂回対象リンクの一例を示す構成図である。
【図７】本発明の実施形態に係る迂回経路決定装置による迂回対象のトラフィックを決定する方法の一例を示す説明図である。
【図８】本発明の実施形態に係る迂回経路決定方法による過剰トラフィックの退避を示すシーケンス図である。
【符号の説明】
【００８２】
１      通信システム
２      バックボーンネットワーク
３（３ａ〜３ｉ）  ユーザネットワーク
１０１〜１０８  ネットワークノード
１１１〜１１８  エッジルータ
２００  迂回経路決定装置
２１０  退避要求受付手段
２２０  端点候補抽出手段
２３０  トラフィック交流情報取得手段
２４０  迂回対象トラフィック量決定手段
２５０  迂回端点決定手段
２６０  経路計算手段
２７０  迂回パス設定要求手段
２８０  トラフィック交流情報ＤＢ
２９０  目標帯域ＤＢ
３００  ネットワーク情報収集装置
３１０  ネットワーク情報収集手段
３２０  ネットワーク情報通知手段
３３０  トポロジ情報ＤＢ
３４０  トラフィック情報ＤＢ
４００  迂回パス設定装置
４１０  パス設定手段
５００  トラフィック交流情報作成装置
５１０  トラフィック交流情報作成手段
【図１】
0004825229.tif 000002
【図２】
0004825229.tif 000003
【図３】
0004825229.tif 000004
【図４】
0004825229.tif 000005
【図５】
0004825229.tif 000006
【図６】
0004825229.tif 000007
【図７】
0004825229.tif 000008
【図８】
0004825229.tif 000009