(57)【要約】【課題】ルータによって構成されるネットワーク通信において、宛先に到達可能な複数の経路のコストが等しくならないように設定するコスト設定装置及び方法を提供すること。【解決手段】ネットワークを構成するルータ４１間のリンクＬのコストを設定するコスト設定装置１０は、ルータ４１間のリンク情報を取得するリンク情報取得手段と、リンク情報取得手段によって取得されたリンク情報に基づいて、ルータ４１間のリンクＬのユニークなバイアスを導出するバイアス導出手段と、バイアス導出手段によって導出されたバイアスを、リンクＬのコストに付加されるバイアスとして、ルータ４１に送信するバイアス送信手段と、を備える。【選択図】図１
2014192760.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを構成するルータ間のリンクのコストを設定するコスト設定装置であって、
前記ルータ間のリンク情報を取得するリンク情報取得手段と、
前記リンク情報取得手段によって取得されたリンク情報に基づいて、前記ルータ間のリンクの、ユニークなバイアスを導出するバイアス導出手段と、
前記バイアス導出手段によって導出されたバイアスを、前記リンクのコストに付加されるバイアスとして、前記ルータに送信するバイアス送信手段と、
を備えるコスト設定装置。
【請求項２】
前記バイアス導出手段は、前記ルータ間の全てのリンクごとの、ユニークなバイアスを導出する、請求項１に記載のコスト設定装置。
【請求項３】
前記バイアス導出手段は、ルータを階層ごとに分け、当該階層を跨ぐリンクごとの、ユニークなバイアスを導出する、請求項１に記載のコスト設定装置。
【請求項４】
前記バイアス導出手段は、前記リンク情報に基づいて、等コストの経路が存在しないリンクの初期集合を抽出し、抽出した初期集合に属さないリンクを初期集合に１つずつ加えるごとに等コストの経路が発生するか否かを判断し、等コストの経路が発生すると判断したリンクの、ユニークなバイアスを導出する、請求項１に記載のコスト設定装置。
【請求項５】
請求項１に記載のコスト設定装置が実行する方法であって、
前記リンク情報取得手段が、前記ルータ間のリンク情報を取得するリンク情報取得ステップと、
前記バイアス導出手段が、前記リンク情報取得ステップによって取得されたリンク情報に基づいて、前記ルータ間のリンクの、ユニークなバイアスを導出するバイアス導出ステップと、
前記バイアス送信手段が、前記バイアス導出ステップによって導出されたバイアスを、前記リンクのコストに付加されるバイアスとして、前記ルータに送信するバイアス送信ステップと、
を備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コスト設定装置及び方法に関する。
【背景技術】
【０００２】
従来のＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）を用いたネットワークでは、リンクごとにコストが設定されており、ルータ間で当該リンクコストの情報が交換される。また当該ネットワークで使用されるＩＰアドレス（プレフィックス）への最短経路はルータごとに計算される。最短経路は、到達可能な経路のうち通過するリンクのコストの総和が最小となる経路が選ばれる（ダイクストラアルゴリズム）。このとき、同一のコスト和をもつ経路が複数あった場合は、それら全てが等コスト経路として経路表に載り、トラヒックをロードバランシングする際等に使い分けがされる。当コスト経路は、負荷分散の観点からは非常に効果的な手法となるが、ＤＰＩ（Ｄｅｅｐ  Ｐａｃｋｅｔ  Ｉｎｓｐｅｃｔｉｏｎ）等のトラヒック解析やデバックを行う際にはフローのトレースを困難にする可能性がある。
【０００３】
リンクコストを変更する技術としては、特許文献１が知られている。特許文献１のトラヒック分散方式は、ルーティングプロトコルとしてＯＳＰＦを使用しているネットワークにおいて、ネットワーク中の特定個所にトラヒックが集中した際に、該特定個所のリンクコストを自動で一時的に増加させることによってトラヒックの分散を図ることを可能とする。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−２１８９１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、等コスト経路が存在する場合の問題について説明する。通常５−ｔｕｐｌｅ（発着信アドレスとポート番号、及びプロトコル番号）をベースにロードバランシングの計算が行われるため、同一フロー（当該５−ｔｕｐｌｅをベースとして−定義されたフロー）であれば、パケットが通過する経路は同じになる（パケットごとに異なる経路を通ることはない）。しかし、往復のトラヒックを考えた場合、例えば、返答トラヒック等、５−ｔｕｐｌｅのうち、発信アドレス・ポート番号と着信アドレス・ポート番号を入れ替えたフローにおいて、その経路は同じになるとは限らない。
例えば、ＤＰＩ等の解析においては、ｒｅｑｕｅｓｔに対するｒｅｐｌｙ等のトラヒックもあわせて解析することがあるため、ネットワーク上でキャプチャしたデータには往復のトラヒックが含まれる必要がある。
しかし、さきほど述べた様に等コスト経路が存在する場合は往復の経路が同じになるとは限らないため、キャプチャポイントを増やす必要性がでてくる。
したがって、ネットワークに等コスト経路が多数あるとそれらを網羅するようにキャプチャポイントを増やす必要性がでてくるため（実用上トラヒックキャプチャポイントは少ない方が良い）、このようなケースでは等コスト経路は好ましくない。
【０００６】
等コスト経路による往復経路の不一致を解消することが可能と思われる従来技術について説明する。特許文献１の技術は、トラヒックが集中している箇所のリンクのコストを増加させる技術であり、等コストの経路が発生しないようにする技術ではない。
等コスト経路をなくすだけであれば、ロードバランシング機能をＯＦＦにすればよいが、これによって一意に選択された経路が両方向で同じになることは保証されない。
Ｓｔａｔｉｃルートを用いて、プレフィックスごとに経路表を細かく設定する方法も考えられるが、大規模ネットワークで使用するのは運用上困難である（全ての経路表を手動で書く作業になる。また既にＯＳＰＦを用いていないことになる）。
ＭＰＬＳ−ＴＥのｅｘｐｌｉｃｉｔオプションを用いて、ルータ間の往復経路を一致させることも可能である。一方で、フルメッシュでＴＥトンネルを定義する必要があったり、同じくトンネルごとに経路を指定する必要があったりするので、運用負荷は増える。また、ルータがＭＰＬＳ−ＴＥをサポートする必要がある。
Ｏｐｅｎｆｌｏｗでは、ＶＬＡＮやｓｔａｔｉｃルート等を用いてフローごとに通る経路を動的に変更することができるため、往復の経路を一致させることは簡単である。一方で、Ｏｐｅｎｆｌｏｗ対応スイッチが必要であったり、フロー毎制御やＶＬＡＮ数の制限に起因するスケーラビリティの問題があったりする（フロー毎の制御はテーブル爆発等が発生しやすく、コントローラやＯｐｅｎｆｌｏｗスイッチがボトルネックになりやすい。もしくはボトルネックにならないレベルのハイエンドな機器が必要となる）。
【０００７】
いずれも、等コスト経路を発生させないようにするためには不十分である。そこで、ＯＳＰＦ等のリンクコストベースで最短経路を計算するネットワークにおいて、当該ネットワークで等コスト経路を発生させないように外部からリンクコストを適切に制御する装置、及びそのリンクコストの割り振りを行うアルゴリズムが求められている。
【０００８】
本発明は、ルータによって構成されるネットワーク通信において、宛先に到達可能な複数の経路のコストが等しくならないように設定するコスト設定装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
具体的には、以下のような解決手段を提供する。
（１）  ネットワークを構成するルータ間のリンクのコストを設定するコスト設定装置であって、前記ルータ間のリンク情報を取得するリンク情報取得手段と、前記リンク情報取得手段によって取得されたリンク情報に基づいて、前記ルータ間のリンクのユニークなバイアスを導出するバイアス導出手段と、前記バイアス導出手段によって導出されたバイアスを、前記リンクのコストに付加されるバイアスとして、前記ルータに送信するバイアス送信手段と、を備えるコスト設定装置。
【００１０】
（１）の構成によれば、（１）に係るコスト設定装置は、ネットワークを構成するルータ間のリンク情報を取得し、取得したリンク情報に基づいて、ルータ間のリンクのユニークなバイアスを導出し、導出したバイアスを、リンクのコストに付加されるバイアスとして、ルータに送信する。
本明細書において、ユニークとは、線形空間的に一次独立な値の集合に属することをいう。すなわち、本明細書におけるユニークな値とは、個々の値が一意な値であり、かつ、個々の値同士を加算した加算値も一意な値であることをいう。よって、ユニークなバイアスとは、個々のバイアスが一意な値であり、かつ、バイアス同士を加算した加算値も一意な値であるようなバイアスをいう。
ユニークなバイアスの具体的な値は、例えば、＋１、＋２、＋４・・・、＋２ｉ（ｉ＝０，１，２，３，…）である。このような一意の値であれば、個々のバイアスは一意な値であり、かつ、バイアス同士を加算した場合、加算結果（＋３、＋６、等）も一意な値である。
【００１１】
したがって、（１）に係るコスト設定装置は、ルータ間のリンクのコストに付加されるユニークなバイアスを設定することによって、宛先に到達可能な複数の経路のコストが等しくならないようにすることができる。
【００１２】
（２）  前記バイアス導出手段は、前記ルータ間の全てのリンクごとの、ユニークなバイアスを導出する、（１）に記載のコスト設定装置。
【００１３】
したがって、（２）に係るコスト設定装置は、ルータ間の全てのリンクごとに、ユニークなバイアスを設定することによって、宛先に到達可能な複数の経路のコストが等しくならないように確実にすることができる。
【００１４】
（３）  前記バイアス導出手段は、ルータを階層ごとに分け、当該階層を跨ぐリンクごとの、ユニークなバイアスを導出する、（１）に記載のコスト設定装置。
【００１５】
したがって、（３）に係るコスト設定装置は、階層を跨ぐリンクごとに、ユニークなバイアスを設定することによって、より少ない設定で、宛先に到達可能な複数の経路のコストが等しくならないように確実にすることができる。
【００１６】
（４）  前記バイアス導出手段は、前記リンク情報に基づいて、等コストの経路が存在しないリンクの初期集合を抽出し、抽出した初期集合に属さないリンクを初期集合に１つずつ加えるごとに等コストの経路が発生するか否かを判断し、等コストの経路が発生すると判断したリンクの、ユニークなバイアスを導出する、（１）に記載のコスト設定装置。
【００１７】
したがって、（４）に係るコスト設定装置は、等コストの経路が存在しない集合にリンクを追加し、追加することによって等コストの経路が発生するか否かを判断して、ユニークなバイアスを設定することによって、さらにより少ない設定で、宛先に到達可能な複数の経路のコストが等しくならないように確実にすることができる。
【００１８】
（５）  （１）に記載のコスト設定装置が実行する方法であって、前記リンク情報取得手段が、前記ルータ間のリンク情報を取得するリンク情報取得ステップと、前記バイアス導出手段が、前記リンク情報取得ステップによって取得されたリンク情報に基づいて、前記ルータ間のリンクのユニークなバイアスを導出するバイアス導出ステップと、前記バイアス送信手段が、前記バイアス導出ステップによって導出されたバイアスを、前記リンクのコストに付加されるバイアスとして、前記ルータに送信するバイアス送信ステップと、を備える方法。
【００１９】
したがって、（５）に係る方法は、（１）と同様に、宛先に到達可能な複数の経路のコストが等しくならないようにすることができる。
【発明の効果】
【００２０】
本発明によれば、ネットワーク上から等コスト経路がなくなることで、詳細なトラヒック解析を少ないＤＰＩポイントで行うことができる。
また、本発明によれば、リンク障害が発生したときに、影響の出るユーザ数を抑えることができ、また影響範囲の絞り込みが容易になり、曖昧性が少なくなる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施形態に係るコスト設定装置の構成を示す図である。
【図２】本発明の一実施形態に係るコスト設定装置の処理内容を示すフローチャートである。
【図３】本発明の一実施形態に係るコスト設定装置によるバイアスの設定の例を示す図である。
【図４】本発明の一実施形態に係るコスト設定装置のアプローチ１の処理内容を示すフローチャートである。
【図５】本発明の一実施形態に係るコスト設定装置のアプローチ１によるバイアスの設定の例を示す図である。
【図６】本発明の一実施形態に係るコスト設定装置のアプローチ２の処理内容を示すフローチャートである。
【図７】本発明の一実施形態に係るコスト設定装置のアプローチ２によるバイアスの設定の例を示す図である。
【図８】本発明の一実施形態に係るコスト設定装置のアプローチ２によるバイアスの設定の別の例を示す図である。
【図９】本発明の一実施形態に係るコスト設定装置のアプローチ３の処理内容を示すフローチャートである。
【図１０】本発明の一実施形態に係るコスト設定装置のアプローチ３によるバイアスの設定の例を示す図である。
【図１１】図１０に続くバイアスの設定の例を示す図である。
【図１２】図１１に続くバイアスの設定の例を示す図である。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について、図を参照しながら説明する。
図１は、本発明の一実施形態に係るコスト設定装置１０の構成を示す図である。コスト設定装置１０は、リンク情報取得手段１１と、バイアス導出手段１２と、バイアス送信手段１３とを備え、ネットワークを構成するルータ（後述する図３におけるルータ４１ａ〜４１ｌ、以下、ルータを区別しない場合、ルータ４１という）間のリンク（後述する図３におけるリンクＬ１〜Ｌ１４、以下、リンクを区別しない場合、リンクＬという）のコストにバイアスを設定し、等コスト経路が発生しないようにする。コスト設定装置１０は、リンクＬのコストにバイアスを設定する以外の処理について、通常のプロトコル動作に従うものとする、例えば、経路計算部分については通常のＯＳＰＦの処理に従うものとする。
【００２３】
リンク情報取得手段１１は、ルータ４１間のリンク情報を取得する。具体的には、リンク情報取得手段１１は、対象ネットワークのルータ４１間のリンク情報を、ルータ４１や他のシステムから取得する。例えば、リンク情報取得手段１１は、ルータ４１にｔｅｌｎｅｔやＳＮＭＰ（Ｓｉｍｐｌｅ  Ｎｅｔｗｏｒｋ  Ｍａｎａｇｅｍｅｎｔ  Ｐｒｏｔｏｃｏｌ）でアクセスし、当該ネットワークで使用しているＯＳＰＦのリンク情報（コスト値を含む）を取得する。なお、ＯＳＰＦでは同一エリア内の全てのルータ４１が当該エリア内のリンクＬの情報を共有しているので、エリア内で１台のルータ４１からリンク情報を取得すれば十分である。
なお、リンク情報取得手段１１は、ネットワーク管理システム（図示せず）からネットワークのルータ４１間のリンク情報をダウンロードするとしてもよい。
【００２４】
バイアス導出手段１２は、リンク情報取得手段１１によって取得されたリンク情報に基づいて、ルータ４１間のリンクＬの、ユニークなバイアスを導出する。具体的には、バイアス導出手段１２は、取得されたリンク情報に基づいてネットワークのトポロジを解析し、ルータ４１の接続関係の抽出を行い、コスト設定アルゴリズムによって、ルータ４１間のリンクＬのユニークなバイアスを導出する。
コスト設定アルゴリズムには、ルータ４１の全てのリンクＬごとにユニークなバイアスを設定するアプローチ１、ルータ４１の階層を抽出し、抽出した階層を跨ぐリンクＬに対してユニークなバイアスを設定するアプローチ２、等コストのないリンクＬの初期集合に基づいて等コストが発生するリンクＬを抽出し、抽出したリンクＬに対してユニークなバイアスを設定するアプローチ３が有り、バイアス導出手段１２は、いずれかのコスト設定アルゴリズムに従って、ユニークなバイアスを導出する。
【００２５】
バイアス送信手段１３は、バイアス導出手段１２によって導出されたバイアスを、リンクＬのコストに付加されるバイアスとして、ルータ４１に送信する。具体的には、バイアス送信手段１３は、該当するルータ４１に、例えば、ｔｅｌｎｅｔによるコマンドであるｃｏｎｆｉｇやＮｅｔｃｏｎｆ等を用いてアクセスし、導出されたバイアスを送信する。
【００２６】
図２は、本発明の一実施形態に係るコスト設定装置１０の処理内容を示すフローチャートである。コスト設定装置１０は、コンピュータ及びその周辺装置が備えるハードウェア並びに該ハードウェアを制御するソフトウェアによって構成され、以下の処理は、制御部（例えば、ＣＰＵ）が所定のソフトウェアに従い実行する処理である。
【００２７】
ステップＳ１１において、ＣＰＵ（リンク情報取得手段１１）は、リンク情報を取得する。より具体的には、ＣＰＵは、ルータ４１にｔｅｌｎｅｔでアクセスし、ＯＳＰＦのリンク情報（コスト値を含む）を取得する。
【００２８】
ステップＳ１２において、ＣＰＵ（バイアス導出手段１２）は、ルータ４１の接続関係の抽出を行う。より具体的には、ＣＰＵは、ステップＳ１１で取得したリンク情報に基づいてネットワークのトポロジを解析し、ルータ４１の接続関係の抽出を行う。
【００２９】
ステップＳ１３において、ＣＰＵ（バイアス導出手段１２）は、リンクＬのユニークなバイアスの導出を行う。より具体的には、ＣＰＵは、取得されたリンク情報に基づいてネットワークのトポロジの解析を行い、ルータ４１の接続関係の抽出を行い、コスト設定アルゴリズムによって、ルータ４１間のリンクＬのユニークなバイアスを導出する。
【００３０】
ステップＳ１４において、ＣＰＵ（バイアス送信手段１３）は、バイアスをルータ４１に送信する。より具体的には、ＣＰＵは、ステップＳ１３において導出されたバイアスを、リンクＬのコストに付加されるバイアスとして、ルータ４１に送信する。
【００３１】
図３は、本発明の一実施形態に係るコスト設定装置１０によるバイアスの設定の例を示す図である。図３の例は、コスト設定装置１０が取得したリンク情報に基づいて、ネットワークのトポロジを解析し、ルータ４１ａ〜４１ｌと、ルータ４１間の接続関係としてリンクＬ１〜Ｌ１４との抽出を行ったことを示している。さらに、図３の例は、コスト設定装置１０が、導出したバイアスを、例えば、該当するルータ４１ｃ、４１ｄ、４１ｊに送信したことを矢印で示している。
【００３２】
コスト設定アルゴリズムについて、アプローチ１〜３について説明する。なお、リンクコストにバイアスを付加するためには、リンクコスト空間を確保する必要があるため、現状のコストを１０００倍や１００００倍する。いくつかのリンクを選び、空いたリンクコスト空間の範囲内でバイアスを割り振る。例えば、リンクコストが１〜１００であるとすると、１００００倍して、１００００〜１００００００のうち空いたリンクコスト空間である１〜９９９９の範囲内でバイアスを割り振る。
【００３３】
適切なリンク選択と適切なバイアスを導出することができれば、ネットワーク上から等コスト経路を排除することができ、結果として往復経路の不一致を解消することができる。ＯＳＰＦではあるリンクの双方向に異なるコストを割り振ることができるが、本発明はバイアスを含めて、同一のコストを割り振るものとする。
【００３４】
アプローチ１におけるバイアス導出手段１２は、ルータ４１間の全ての経路ごとに、ユニークなバイアスを導出する。
【００３５】
図４は、本発明の一実施形態に係るコスト設定装置１０のアプローチ１の処理内容を示すフローチャートである。
【００３６】
ステップＳ１０１において、ＣＰＵ（バイアス導出手段１２）は、全てのリンクＬを抽出する。より具体的には、ＣＰＵは、解析したトポロジに基づいて、全てのリンクＬを抽出する。
【００３７】
ステップＳ１０２において、ＣＰＵ（バイアス導出手段１２）は、抽出した全てのリンクＬのユニークなバイアスを導出する。より具体的には、ＣＰＵは、抽出した全てのリンクＬに、２ｉ（ｉ＝０，１，２，３，…）を割り振る。
【００３８】
図５は、本発明の一実施形態に係るコスト設定装置１０のアプローチ１によるバイアスの設定の例を示す図である。
【００３９】
図５の例は、全てのリンクＬに対して、例えば、＋１、＋２、＋４・・・と２ｉ（ｉ＝０，１，２，３，…）のバイアスが設定されている例である。これにより、任意の２点間でのリンクＬのバイアスがユニークになる。この場合、バイアスの総和により、どのリンクＬを通ったかも示すことができる。ただし、バイアスがバイアス空間を超過しないようにする。例えば、バイアスを１６ビットで構成する場合、アプローチ１は、リンク数が１６本未満のネットワークで用いられる。
【００４０】
アプローチ２におけるバイアス導出手段１２は、ルータ４１を階層ごとに分け、当該階層を跨ぐリンクＬごとの、ユニークなバイアスを導出する。
【００４１】
具体的には、バイアス導出手段１２は、ネットワークを、２つのルータ４１間の経路が１つしかない階層にスライスする。次に、バイアス導出手段１２は、スライスされた階層ごとのリンクＬに対してバイアスを、例えば、＋１、＋２、＋４・・・２ｉ（ｉ＝１，２，３，…）のように導出する。
ここで、階層は、当該階層内の２つのルータ４１間のリンクＬが１つしかないように構成される。すなわち、階層は、ひも状のトポロジである。したがって、同一の階層内には等コストがなく、異なる階層を跨ぐ経路においては、バイアスを付けたリンクＬを通ることになるので、かならずユニークなコスト値になる。ゆえに、当該トポロジ内の２つのルータ間に等コストは発生しない。
スライスするときにネットワーク内で２点間が最も遠いものを基準にするとバイアスを付ける箇所が少なくて済む。本アプローチは、元々振られているリンクコスト値に依存していない点、並びにリンク断の場合も等コスト経路が発生しない点が優れている。
【００４２】
図６は、本発明の一実施形態に係るコスト設定装置１０のアプローチ２の処理内容を示すフローチャートである。
【００４３】
ステップＳ２０１において、ＣＰＵ（バイアス導出手段１２）は、階層を抽出する。より具体的には、ＣＰＵは、２つのルータ４１間のリンクＬが１つしかないように階層を抽出する。
【００４４】
ステップＳ２０２において、ＣＰＵ（バイアス導出手段１２）は、階層を跨ぐリンクＬを抽出する。より具体的には、ＣＰＵは、抽出した階層の一方の階層に含まれるルータ４１と、他方の階層に含まれるルータ４１とを接続するリンクＬを抽出する。
【００４５】
ステップＳ２０３において、ＣＰＵ（バイアス導出手段１２）は、抽出したリンクＬのユニークなバイアスを導出する。より具体的には、ＣＰＵは、抽出したリンクＬに、２ｉ（ｉ＝０，１，２，３，…）を割り振る。
【００４６】
図７は、本発明の一実施形態に係るコスト設定装置１０のアプローチ２によるバイアスの設定の例を示す図である。
図７の例は、ネットワークを２つのルータ間の経路が１つしかない階層にスライスし、その結果、階層１０１と、階層１０２と、階層１０３とを抽出し、抽出した階層を跨ぐリンクＬを抽出し、抽出した跨ぐリンクＬに２ｉ（ｉ＝０，１，２，３，…）のバイアスを割り振ったことを示している。
【００４７】
図８は、本発明の一実施形態に係るコスト設定装置１０のアプローチ２によるバイアスの設定の別の例を示す図である。
図８の例は、ネットワークを２つのルータ間の経路が１つしかない階層にスライスするときにネットワーク内で２点間が最も遠いものを基準にした場合の例である。階層１０１と、階層１０２と、階層１０３とを抽出し、抽出した階層を跨ぐリンクＬを抽出し、抽出した跨ぐリンクＬに２ｉ（ｉ＝０，１，２，３，…）のバイアスを割り振ったことを示している。
【００４８】
アプローチ３におけるバイアス導出手段１２は、リンク情報に基づいて、等コストの経路が存在しないルータ４１の初期集合を抽出し、抽出した初期集合に属さないルータ４１を初期集合に加えるごとに等コストの経路が発生するか否かを判断し、等コストの経路が発生すると判断するごとに、加えるルータ４１のリンクＬのユニークなバイアスを導出する。
【００４９】
具体的には、バイアス導出手段１２は、以下の（１）から（５）のステップにより集合Ｃを抽出する。集合Ｃ内のリンクＬに対して、ユニークなバイアスを導出する。
（１）ネットワーク（例えば、図２）上の任意のルータ４１（例えば、ルータ４１ｂ）をノードとして最初に選択する。選択したノードを根とする全域木３００（例えば、後述する図１０）を１つ抽出する。抽出した全域木３００を構成するリンクＬの集合を集合Ａとする。集合Ａ以外のリンクＬの集合（例えば、後述する図１０の場合、リンクＬ２、リンクＬ８〜リンクＬ１２、リンクＬ１８の集合）を、集合Ｂとする。
最初に選択するルータ４１は、ノードとして最も次数が多いノードを選択するとしてもよい。また、抽出した全域木３００が、等コスト経路を含む場合は、等コスト経路のうちどれか１つを適当に選ぶ。
（２）集合Ｂから１つのリンクＬを選択する（選択したリンクＬは集合Ｂから削除する）。
（３）選択したリンクＬを集合Ａに追加してできた集合Ａ’において、集合Ａ’内に等コスト経路がない場合、集合Ａ＝集合Ａ’とする。選択したリンクＬを集合Ａに追加してできた集合Ａ’において、集合Ａ’内に等コスト経路がある場合、選択したリンクＬを集合Ａ’から除き集合Ａとし、除いたリンクＬを集合Ｃに加える。
（４）集合ＢのリンクＬがなくなるまで（２）及び（３）を実行する。
（５）集合ＣのリンクＬに対し、ユニークなバイアスを導出する。
【００５０】
なお、リンク断等による障害時においても等コスト経路を発生させたくない場合は、各ステップの等コスト判定において想定する障害時にも等コストが発生しないことを基準とするとよい。
【００５１】
図９は、本発明の一実施形態に係るコスト設定装置１０のアプローチ３の処理内容を示すフローチャートである。
【００５２】
ステップＳ３０１において、ＣＰＵ（バイアス導出手段１２）は、集合Ａ及び集合Ｂを抽出する。集合Ｃを空集合にする。より具体的には、ＣＰＵは、ルータ４１をノードとした場合、ノードとして最も次数が多いノードであるルータ４１を選択し、選択したルータ４１を根とする１つの全域木を抽出し、全域木を構成するリンクＬを集合Ａとする。集合Ａ以外のリンクＬの集合を集合Ｂとする。
【００５３】
ステップＳ３０２において、ＣＰＵ（バイアス導出手段１２）は、集合Ｂが空集合か否かを判断する。この判断がＹＥＳの場合、ＣＰＵは処理をステップＳ３０６に移し、この判断がＮＯの場合、ＣＰＵは処理をステップ３０３に移す。
【００５４】
ステップＳ３０３において、ＣＰＵ（バイアス導出手段１２）は、集合Ｂから１つのリンクＬを集合Ａに加え、集合Ａに加えたリンクＬを集合Ｂから除く。
【００５５】
ステップＳ３０４において、ＣＰＵ（バイアス導出手段１２）は、集合Ａに等コスト経路があるか否かを判断する。この判断がＹＥＳの場合、ＣＰＵは処理をステップ３０５に移し、この判断がＮＯの場合、ＣＰＵは処理をステップ３０２に移す。
【００５６】
ステップＳ３０５において、ＣＰＵ（バイアス導出手段１２）は、集合Ａに加えたリンクＬを集合Ａから除き、集合Ｃに加える。その後、ＣＰＵは処理をステップ３０２に移す。
【００５７】
ステップＳ３０６において、ＣＰＵ（バイアス導出手段１２）は、集合ＣのリンクＬに対し、ユニークなバイアスを導出する。その後、ＣＰＵは処理を終了する。
【００５８】
図１０は、本発明の一実施形態に係るコスト設定装置１０のアプローチ３によるバイアスの設定の例を示す図である。図１１は、図１０に続くバイアスの設定の例を示す図である。図１２は、図１１に続くバイアスの設定の例を示す図である。
【００５９】
図１０の例は、アプローチ３における集合Ａの例である。図１１は、集合Ａに集合ＢのリンクＬ２、リンクＬ８〜リンクＬ１２、リンクＬ１８を１つずつ追加し、等コスト経路が発生しない場合（リンクＬ２、リンクＬ１２、リンクＬ１８の場合）に、追加した集合Ａに更新した例である。図１２は、集合ＣのリンクＬ８〜リンクＬ１１に対し、ユニークなバイアスを導出し、ネットワークを構成した例である。
【００６０】
本実施形態によれば、コスト設定装置１０は、ネットワークを構成するルータ４１間のリンク情報を取得し、取得したリンク情報に基づいて、ルータ４１間のリンクＬのユニークなバイアスを導出し、導出したバイアスを、リンクＬのコストに付加されるバイアスとして、ルータ４１に送信する。コスト設定装置１０は、バイアスの導出について、ルータ４１間の全てのリンクＬごとの、ユニークなバイアスを導出するアプローチ１、ルータ４１を階層ごとに分け、当該階層を跨ぐリンクＬごとの、ユニークなバイアスを導出するアプローチ２、リンク情報に基づいて、等コストの経路が存在しないリンクＬの初期集合を抽出し、抽出した初期集合に属さないリンクＬを初期集合に１つずつ加えるごとに等コストの経路が発生するか否かを判断し、等コストの経路が発生すると判断したリンクＬの、ユニークなバイアスを導出するアプローチ３のいずれかのアプローチにより、リンクＬのユニークなバイアスを導出し、導出したバイアスを、リンクＬのコストに付加されるバイアスとして、ルータ４１に送信する。
したがって、コスト設定装置１０は、ルータ４１によって構成されるネットワーク通信において、宛先に到達可能な複数の経路のコストが等しくならないようにすることができる。
【００６１】
本実施形態では、アプローチ１〜３のいずれかのコスト設定アルゴリズムに基づいて、ユニークなバイアスを設定するとしたが、解析したトポロジにしたがって、アプローチ１〜３のうち最適なアプローチを選択するとしてもよい。
本実施形態では、リンクＬのコストに付加されるバイアスとして、ルータ４１に送信するとしたが、リンクＬのコストをバイアスに変更するために、ルータ４１に送信するとしてもよい。
本実施形態では、ユニークなバイアスとして、＋１や＋２を用いているが、積極的にトラヒックを流したいリンクＬに対しては−１や−２を用いることもできる。
本実施形態では、任意のリンク断でも等コスト経路が存在しないようにしているが、リンク断の数に制約を設け、所定の数以上のリンク断の場合には等コスト経路が存在するようなバイアスを導出するとしてもよい。ユニークなバイアスを設定する数を少なくすることができる。
【００６２】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【符号の説明】
【００６３】
１０    コスト設定装置
１１    リンク情報取得手段
１２    バイアス導出手段
１３    バイアス送信手段
【図１】
2014192760.tif 000003
【図２】
2014192760.tif 000004
【図３】
2014192760.tif 000005
【図４】
2014192760.tif 000006
【図５】
2014192760.tif 000007
【図６】
2014192760.tif 000008
【図７】
2014192760.tif 000009
【図８】
2014192760.tif 000010
【図９】
2014192760.tif 000011
【図１０】
2014192760.tif 000012
【図１１】
2014192760.tif 000013
【図１２】
2014192760.tif 000014