(57)【特許請求の範囲】
【請求項１】
複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定サーバであって、
前記複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報と、フローの送信元ノードと送信先ノードの組み合わせに対する通信経路の候補を含む経路キャッシュ情報が格納される記憶部と、
フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、前記送信元ノードから前記送信先ノードへの通信経路を設計する経路設計部と
を備え、
前記経路設計部は、
前記経路設定要求に応じた経路候補が前記経路キャッシュ情報にない場合、前記次ホップ情報を参照しながら次ホップ決定処理を実行する次ホップ決定部と、
前記経路設定要求に応じた経路候補が前記経路キャッシュ情報に含まれる場合、前記経路キャッシュ情報を参照しながら、経路候補決定処理を実行する検索部と、
ループ検出部と、
ループ解消部と
を含み、
前記次ホップ情報は、対象ノードに関する前記次ホップノードの候補を複数含み、
前記次ホップ決定処理において、前記次ホップ決定部は、前記複数の候補のそれぞれを選択する確率に応じた数値範囲が設定された所定の範囲内で乱数を発生させ、前記発生した乱数を含む数値範囲に対応する候補を選択し、前記対象ノードを前記選択された１つの次ホップノードに更新し、
前記次ホップ決定部は、前記対象ノードを前記送信元ノードに初期設定した後、前記対象ノードが前記送信先ノードとなるまで前記次ホップ決定処理を繰り返すことによって前記通信経路を１ホップずつ決定し、
前記ループ検出部は、現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された前記通信経路上のループを検出し、
前記ループが検出された場合、前記ループ解消部は、前記対象ノードを過去のいずれかの対象ノードに戻すことによって前記ループを解消し、
前記ループが解消された後、前記次ホップ決定部は、前記過去のいずれかの対象ノードから前記次ホップ決定処理をやり直し、
前記経路キャシュ情報は、送信元ノード及び送信先ノードに対応する経路候補を複数含み、
前記複数の経路候補のそれぞれに含まれるノードを前記候補としたときの選択確率に基づいて、前記複数の経路候補のそれぞれを選択する確率が設定され、
前記経路候補決定処理において、前記検索部は、前記複数の経路候補のそれぞれを選択する確率に応じた数値範囲が設定された所定の範囲内で乱数を発生させ、前記発生した乱数を含む数値範囲に対応する経路候補を前記経路設定要求に応じた通信経路として選択する
経路設定サーバ。
【請求項２】
請求項１に記載の経路設定サーバであって、
前記ループ解消部は、前記対象ノードを１ホップだけ戻すことによって前記ループを解消する
経路設定サーバ。
【請求項３】
請求項１に記載の経路設定サーバであって、
前記ループ解消部は、前記対象ノードを、前記現在の対象ノードと重複しているものまで戻すことによって前記ループを解消する
経路設定サーバ。
【請求項４】
請求項１乃至３のいずれか一項に記載の経路設定サーバであって、
前記次ホップ決定処理をやり直す場合、前記次ホップ決定部は、前回に選択された次ホップノードを前記候補から除外する
経路設定サーバ。
【請求項５】
請求項４に記載の経路設定サーバであって、
前記候補が前回に選択された次ホップノードだけの場合、前記次ホップ決定部は、前記対象ノードを更に１ホップだけ戻した後、前記次ホップ決定処理をやり直す
経路設定サーバ。
【請求項６】
請求項１乃至５のいずれか１項に記載の経路設定サーバであって、
前記選択する確率は、前記対象ノードから前記選択された候補を経由して前記送信先ノードへ向かう経路のコストに反比例する
経路設定サーバ。
【請求項７】
請求項１乃至６のいずれか一項に記載の経路設定サーバであって、
前記記憶部には更に、経路キャッシュ情報が格納され、
前記経路キャッシュ情報は、前記送信元ノードと前記送信先ノードとの組み合わせに対して過去に決定された前記通信経路を経路候補として示し、
前記次ホップ決定部は、前記決定された通信経路を、前記経路設定要求で示される前記送信元ノードと前記送信先ノードとの組み合わせに対する前記経路候補として、前記経路キャッシュ情報に追加する
経路設定サーバ。
【請求項８】
請求項７に記載の経路設定サーバであって、
前記経路設計部は更に、キャッシュ検索部を含み、
前記キャッシュ検索部は、前記経路設定要求に応答して前記経路キャッシュ情報を検索し、
前記経路キャッシュ情報が前記経路設定要求に対応する前記経路候補を含んでいる場合、前記キャッシュ検索部は、前記経路候補の中から前記通信経路を確率的に決定する
経路設定サーバ。
【請求項９】
請求項１乃至８のいずれか一項に記載の経路設定サーバであって、
前記経路設計部は更に、ノード設定部を備え、
前記ノード設定部は、前記決定された通信経路上の各ノードに対して、前記フローのデータを前記決定された通信経路に沿って転送するように指示する
経路設定サーバ。
【請求項１０】
複数のノードを含む通信ネットワークと、
前記通信ネットワークにおけるフローの通信経路を決定する経路設定サーバと
を備え、
前記経路設定サーバは、
前記複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報と、フローの送信元ノードと送信先ノードの組み合わせに対する通信経路の候補を含む経路キャッシュ情報が格納される記憶部と、
フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、前記送信元ノードから前記送信先ノードへの通信経路を設計する経路設計部と
を備え、
前記経路設計部は、
前記経路設定要求に応じた経路候補が前記経路キャッシュ情報にない場合、前記次ホップ情報を参照しながら次ホップ決定処理を実行する次ホップ決定部と、
前記経路設定要求に応じた経路候補が前記経路キャッシュ情報に含まれる場合、前記経路キャッシュ情報を参照しながら、経路候補決定処理を実行する検索部と、
ループ検出部と、
ループ解消部と
を含み、
前記次ホップ情報は、対象ノードに関する前記次ホップノードの候補を複数含み、
前記次ホップ決定処理において、前記次ホップ決定部は、前記複数の候補のそれぞれを選択する確率に応じた数値範囲が設定された所定の範囲内で乱数を発生させ、前記発生した乱数を含む数値範囲に対応する候補を選択し、前記対象ノードを前記選択された１つの次ホップノードに更新し、
前記次ホップ決定部は、前記対象ノードを前記送信元ノードに初期設定した後、前記対象ノードが前記送信先ノードとなるまで前記次ホップ決定処理を繰り返すことによって前記通信経路を１ホップずつ決定し、
前記ループ検出部は、現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された前記通信経路上のループを検出し、
前記ループが検出された場合、前記ループ解消部は、前記対象ノードを過去のいずれかの対象ノードに戻すことによって前記ループを解消し、
前記ループが解消された後、前記次ホップ決定部は、前記過去のいずれかの対象ノードから前記次ホップ決定処理をやり直し、
前記経路キャシュ情報は、送信元ノード及び送信先ノードに対応する経路候補を複数含み、
前記複数の経路候補のそれぞれに含まれるノードを前記候補としたときの選択確率に基づいて、前記複数の経路候補のそれぞれを選択する確率が設定され、
前記経路候補決定処理において、前記検索部は、前記複数の経路候補のそれぞれを選択する確率に応じた数値範囲が設定された所定の範囲内で乱数を発生させ、前記発生した乱数を含む数値範囲に対応する経路候補を前記経路設定要求に応じた通信経路として選択する
通信ネットワークシステム。
【請求項１１】
複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定方法であって、
前記複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報と、フローの送信元ノードと送信先ノードの組み合わせに対する通信経路の候補を含む経路キャッシュ情報を、記憶装置に格納するステップと、
フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、前記送信元ノードから前記送信先ノードへの通信経路を設計するステップと
を含み、
前記通信経路を設計するステップは、
前記経路設定要求に応じた経路候補が前記経路キャッシュ情報にない場合、前記次ホップ情報を参照しながら次ホップ決定処理を実行するステップと、
前記経路設定要求に応じた経路候補が前記経路キャッシュ情報に含まれる場合、前記経路キャッシュ情報を参照しながら、経路候補決定処理を実行するステップと
を含み、
ここで、
前記次ホップ情報は、対象ノードに関する前記次ホップノードの候補を複数含み、
前記経路キャシュ情報は、送信元ノード及び送信先ノードに対応する経路候補を複数含み、
前記次ホップ決定処理は、
前記複数の候補のそれぞれを選択する確率に応じた数値範囲が設定された所定の範囲内で乱数を発生させ、前記発生した乱数を含む数値範囲に対応する候補を選択するステップと、
前記対象ノードを前記選択された１つの次ホップノードに更新するステップと
を含み、
前記対象ノードを前記送信元ノードに初期設定した後、前記対象ノードが前記送信先ノードとなるまで前記次ホップ決定処理を繰り返すことによって前記通信経路を１ホップずつ決定するステップと、
現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された前記通信経路上のループを検出するステップと、
前記ループが検出された場合、前記対象ノードを過去のいずれかの対象ノードに戻すことによって前記ループを解消するステップと、
前記ループが解消された後、前記過去のいずれかの対象ノードから前記次ホップ決定処理をやり直すステップと
を含み、
前記複数の経路候補のそれぞれに含まれるノードを前記候補としたときの選択確率に基づいて、前記複数の経路候補のそれぞれを選択する確率が設定され、
前記経路候補決定処理を実行するステップは、前記複数の経路候補のそれぞれを選択する確率に応じた数値範囲が設定された所定の範囲内で乱数を発生させ、前記発生した乱数を含む数値範囲に対応する経路候補を前記経路設定要求に応じた通信経路として選択するステップを含む
経路設定方法。
【請求項１２】
複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定処理をコンピュータに実行させる経路設定プログラムであって、
前記経路設定処理は、
前記複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報と、フローの送信元ノードと送信先ノードの組み合わせに対する通信経路の候補を含む経路キャッシュ情報を、記憶装置に格納するステップと、
フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、前記送信元ノードから前記送信先ノードへの通信経路を設計するステップと
を含み、
前記通信経路を設計するステップは、
前記経路設定要求に応じた経路候補が前記経路キャッシュ情報にない場合、前記次ホップ情報を参照しながら次ホップ決定処理を実行するステップと、
前記経路設定要求に応じた経路候補が前記経路キャッシュ情報に含まれる場合、前記経路キャッシュ情報を参照しながら、経路候補決定処理を実行するステップと
を含み、
ここで、
前記次ホップ情報は、対象ノードに関する前記次ホップノードの候補を複数含み、
前記経路キャシュ情報は、送信元ノード及び送信先ノードに対応する経路候補を複数含み、
前記次ホップ決定処理は、
前記複数の候補のそれぞれを選択する確率に応じた数値範囲が設定された所定の範囲内で乱数を発生させ、前記発生した乱数を含む数値範囲に対応する候補を選択するステップと、
前記対象ノードを前記選択された１つの次ホップノードに更新するステップと
を含み、
前記対象ノードを前記送信元ノードに初期設定した後、前記対象ノードが前記送信先ノードとなるまで前記次ホップ決定処理を繰り返すことによって前記通信経路を１ホップずつ決定するステップと、
現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された前記通信経路上のループを検出するステップと、
前記ループが検出された場合、前記対象ノードを過去のいずれかの対象ノードに戻すことによって前記ループを解消するステップと、
前記ループが解消された後、前記過去のいずれかの対象ノードから前記次ホップ決定処理をやり直すステップと
を含み、
前記複数の経路候補のそれぞれに含まれるノードを前記候補としたときの選択確率に基づいて、前記複数の経路候補のそれぞれを選択する確率が設定され、
前記経路候補決定処理を実行するステップは、前記複数の経路候補のそれぞれを選択する確率に応じた数値範囲が設定された所定の範囲内で乱数を発生させ、前記発生した乱数を含む数値範囲に対応する経路候補を前記経路設定要求に応じた通信経路として選択するステップを含む
経路設定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路設定サーバを用いて通信ネットワークにおけるフローの通信経路を決定する技術に関する。
【背景技術】
【０００２】
複数のノードを含む通信ネットワークが管理サーバによって集中的に管理される通信ネットワークシステムが知られている。管理サーバは、あるフローに関する経路設定要求を受け取ると、通信ネットワークにおける当該フローの通信経路を決定する。このようにフローの通信経路を決定する管理サーバは、以下、「経路設定サーバ」とも参照される。【０００３】
ある送信元ノードからある送信先ノードへの最短経路を求めるアルゴリズムとしては、「ダイクストラ法（Dijkstra's Algorithm）」が一般によく知られている。しかしながら、それら送信元ノードと送信先ノードとの間で複数のフローの通信が行われる場合、単純にダイクストラ法を用いるだけでは、それら複数のフローに対して同じ通信経路（最短経路）が設定されてしまう。このことは、当該通信経路にかかる負荷を増大させ、通信効率を低下させる。【０００４】
負荷を分散させるためには、同じ送信元ノードと送信先ノードとの間の異なるフローに対して、異なる通信経路を設定することが好適である。そのためには、それら送信元ノードと送信先ノードとの間で、最短経路だけでなく他の通信経路をも抽出することが考えられる。送信元ノードから送信先ノードへの複数の通信経路を求める技術として、次のものが知られている。【０００５】
特許文献１（特開２００３−２３３７６８号公報）には、デュアルダイクストラ法によって、始点から終点への複数の通信経路を求める手法が記載されている。具体的には、全中間ノードに関して、始点からの最短経路木がそれぞれダイクストラ法により作成される。また、全中間ノードに関して、終点からの最短経路木がそれぞれダイクストラ法により作成される。そして、それら２つの最短経路木を組み合わせることによって、始点から異なる中間ノードを経由して終点へ向かう複数の通信経路が算出される。ダイクストラ法を複数回組み合わせて複数経路を求める方式は、他に特許文献２（特開２００３−２３４４６号公報）にも記載されている。【０００６】
非特許文献１（稲垣潤  他，遺伝的アルゴリズムを用いた経路探索における複数経路候補の決定法，電子情報通信学会論文誌．Ｄ−Ｉ，情報・システム，Ｉ−情報処理，Ｖｏｌ．Ｊ８２−Ｄ−Ｉ，Ｎｏ．８（１９９９０８２５），ｐｐ．１１０２−１１１１）には、遺伝的アルゴリズムを利用して複数の通信経路を同時に求める方式が記載されている。【０００７】
特許文献３（特表２００７−５１５９０６号公報）には、マルチホップ通信ネットワークにおけるコスト決定方法が記載されている。そのコスト決定方法は、ネットワークの送信元ノードから宛先ノードへの複数のノードの少なくとも１つに対し、同時に可能性のある複数の次ホップノードを決定するステップ、を含む。それら同時に可能性のある複数のノードは共に、所定のコスト関数を最適化する。更に、コスト決定方法は、複数のノードの少なくとも１つについての最適コストを、上記所定のコスト関数の上記最適化された値に等しくなるように決定するステップ、を含む。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００３−２３３７６８号公報
【特許文献２】特開２００３−２３４４６号公報
【特許文献３】特表２００７−５１５９０６号公報
【非特許文献】
【０００９】
【非特許文献１】稲垣潤  他，遺伝的アルゴリズムを用いた経路探索における複数経路候補の決定法，電子情報通信学会論文誌．Ｄ−Ｉ，情報・システム，Ｉ−情報処理，Ｖｏｌ．Ｊ８２−Ｄ−Ｉ，Ｎｏ．８（１９９９０８２５），ｐｐ．１１０２−１１１１
【発明の概要】
【００１０】
通信ネットワークにかかる負荷を分散させるためには、同じ送信元ノードと送信先ノードとの間の異なるフローに対して、異なる通信経路を設定することが好ましい。そのために、上述の関連技術に記載されているように、送信元ノードから送信先ノードへの複数の通信経路を求めることが考えられる。新たなフローが発生した際、それら複数の通信経路から適切な１つを選択し、選択された通信経路を当該フローに割り当てることによって、負荷を分散することができる。
【００１１】
しかしながら、上述の関連技術では、通信経路を決定する経路設定サーバにおける計算量が膨大となる。ダイクストラ法を利用する方式の場合、その計算量は、全ノード数に比例して指数的に増加する。例えば、８次のハイパーキューブネットワークの場合、ある送信元ノードとある送信先ノードとの間の通信経路は約４万パターンあり、それら全てを事前に算出しておくことは実質的に不可能である。また、遺伝的アルゴリズムを利用する方式の場合も、計算が収束するまでの時間が長く、やはり計算量が多いという問題がある。
【００１２】
本発明の１つの目的は、経路設定サーバを用いて通信ネットワークにおけるフローの通信経路を決定する際に、当該経路設定サーバにおける計算量を削減することにある。
【００１３】
本発明の１つの観点において、複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定サーバが提供される。その経路設定サーバは、記憶部と経路計算部とを備える。記憶部には、複数のノードの各々に関してデータの転送先となる次ホップノードの候補を示す次ホップ情報が格納される。経路計算部は、フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、送信元ノードから送信先ノードへの通信経路を設計する。詳細には、経路設計部は、次ホップ情報を参照しながら「次ホップ決定処理」を実行する次ホップ決定部と、ループ検出部と、ループ解消部とを含む。次ホップ決定処理において、次ホップ決定部は、対象ノードに関する次ホップノードの候補の中から１つの次ホップノードをランダムに選択し、対象ノードを上記選択された１つの次ホップノードに更新する。次ホップ決定部は、対象ノードを送信元ノードに初期設定した後、対象ノードが送信先ノードとなるまで次ホップ決定処理を繰り返すことによって通信経路を１ホップずつ決定する。ループ検出部は、現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された通信経路上のループを検出する。ループが検出された場合、ループ解消部は、対象ノードを過去のいずれかの対象ノードに戻すことによってループを解消する。ループが解消された後、次ホップ決定部は、上記過去のいずれかの対象ノードから次ホップ決定処理をやり直す。
【００１４】
本発明の他の観点において、通信ネットワークシステムが提供される。通信ネットワークシステムは、複数のノードを含む通信ネットワークと、その通信ネットワークにおけるフローの通信経路を決定する経路設定サーバと、を備える。経路設定サーバは、記憶部と経路計算部とを備える。記憶部には、複数のノードの各々に関してデータの転送先となる次ホップノードの候補を示す次ホップ情報が格納される。経路計算部は、フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、送信元ノードから送信先ノードへの通信経路を設計する。詳細には、経路設計部は、次ホップ情報を参照しながら「次ホップ決定処理」を実行する次ホップ決定部と、ループ検出部と、ループ解消部とを含む。次ホップ決定処理において、次ホップ決定部は、対象ノードに関する次ホップノードの候補の中から１つの次ホップノードをランダムに選択し、対象ノードを上記選択された１つの次ホップノードに更新する。次ホップ決定部は、対象ノードを送信元ノードに初期設定した後、対象ノードが送信先ノードとなるまで次ホップ決定処理を繰り返すことによって通信経路を１ホップずつ決定する。ループ検出部は、現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された通信経路上のループを検出する。ループが検出された場合、ループ解消部は、対象ノードを過去のいずれかの対象ノードに戻すことによってループを解消する。ループが解消された後、次ホップ決定部は、上記過去のいずれかの対象ノードから次ホップ決定処理をやり直す。
【００１５】
本発明の更に他の観点において、複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定方法が提供される。その経路設定方法は、（Ａ）複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報を、記憶装置に格納するステップと、（Ｂ）フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、送信元ノードから送信先ノードへの通信経路を設計するステップと、を含む。上記（Ｂ）ステップは、（Ｂ１）次ホップ情報を参照しながら「次ホップ決定処理」を実行するステップ、を含む。ここで、次ホップ決定処理は、対象ノードに関する次ホップノードの候補の中から１つの次ホップノードをランダムに選択するステップと、対象ノードを上記選択された１つの次ホップノードに更新するステップと、を含む。上記（Ｂ）ステップは、更に、（Ｂ２）対象ノードを送信元ノードに初期設定した後、対象ノードが送信先ノードとなるまで次ホップ決定処理を繰り返すことによって通信経路を１ホップずつ決定するステップと、（Ｂ３）現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された通信経路上のループを検出するステップと、（Ｂ４）ループが検出された場合、対象ノードを過去のいずれかの対象ノードに戻すことによってループを解消するステップと、（Ｂ５）ループが解消された後、上記過去のいずれかの対象ノードから次ホップ決定処理をやり直すステップと、を含む。
【００１６】
本発明の更に他の観点において、複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定処理をコンピュータに実行させる経路設定プログラムが提供される。その経路設定処理は、（Ａ）複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報を、記憶装置に格納するステップと、（Ｂ）フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、送信元ノードから送信先ノードへの通信経路を設計するステップと、を含む。上記（Ｂ）ステップは、（Ｂ１）次ホップ情報を参照しながら「次ホップ決定処理」を実行するステップ、を含む。ここで、次ホップ決定処理は、対象ノードに関する次ホップノードの候補の中から１つの次ホップノードをランダムに選択するステップと、対象ノードを上記選択された１つの次ホップノードに更新するステップと、を含む。上記（Ｂ）ステップは、更に、（Ｂ２）対象ノードを送信元ノードに初期設定した後、対象ノードが送信先ノードとなるまで次ホップ決定処理を繰り返すことによって通信経路を１ホップずつ決定するステップと、（Ｂ３）現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された通信経路上のループを検出するステップと、（Ｂ４）ループが検出された場合、対象ノードを過去のいずれかの対象ノードに戻すことによってループを解消するステップと、（Ｂ５）ループが解消された後、上記過去のいずれかの対象ノードから次ホップ決定処理をやり直すステップと、を含む。
【００１７】
本発明によれば、経路設定サーバを用いて通信ネットワークにおけるフローの通信経路を決定する際に、当該経路設定サーバにおける計算量を削減することが可能となる。
【図面の簡単な説明】
【００１８】
上記及び他の目的、長所、特徴は、次の図面と共に説明される本発明の実施の形態により明らかになるであろう。
【図１】図１は、本発明の実施の形態に係る通信ネットワークシステムを示す概略図である。
【図２】図２は、送信元ノードから送信先ノードへの複数の通信経路を示す概念図である。
【図３】図３は、本発明の第１の実施の形態に係る経路設定サーバの構成を示すブロック図である。
【図４】図４は、対象ノードと送信先ノードと次ホップノードとの間の関係を示す概念図である。
【図５】図５は、ルーティングテーブルを示す概念図である。
【図６】図６は、第１の実施の形態に係る経路設定方法を示すフローチャートである。
【図７】図７は、経路ノードリストを示す概念図である。
【図８】図８は、第１の実施の形態における次ホップ決定処理を示すフローチャートである。
【図９】図９は、本発明の第２の実施の形態に係る経路設定サーバの構成を示すブロック図である。
【図１０】図１０は、経路キャッシュ情報を示す概念図である。
【図１１】図１１は、第２の実施の形態に係る経路設定方法を示すフローチャートである。
【図１２】図１２は、本発明の第３の実施の形態に係る経路設定サーバの構成を示すブロック図である。
【図１３】図１３は、リンクコストテーブルを示す概念図である。
【図１４】図１４は、経路コストテーブルを示す概念図である。
【図１５】図１５は、第３の実施の形態における次ホップ決定処理を示すフローチャートである。
【発明を実施するための形態】
【００１９】
添付図面を参照して、本発明の実施の形態を説明する。
【００２０】
１．通信ネットワークシステム
図１は、本発明の実施の形態に係る通信ネットワークシステム１を示す概略図である。通信ネットワークシステム１は、複数のノード５を含む通信ネットワークＮＥＴを備えている。本実施の形態では、通信ネットワークＮＥＴはｎ個（ｎは２以上の整数）のノード５−１〜５−ｎを含んでいるとする。
【００２１】
通信ネットワークシステム１は更に、経路設定サーバ１０を備えている。経路設定サーバ１０は、通信ネットワークＮＥＴを集中的に管理する管理サーバ（管理計算機）であり、複数のノード５−１〜５−ｎのそれぞれと双方向に通信可能である。特に、経路設定サーバ１０は、通信ネットワークＮＥＴにおけるフローの通信経路を決定する。具体的には、あるフローが発生した場合、経路設定サーバ１０は、当該フローに関する経路設定要求を通信ネットワークＮＥＴから受け取る。経路設定要求は、当該フローの送信元ノードと送信先ノードを示している。経路設定サーバ１０は、その経路設定要求に応答して、送信元ノードから送信先ノードへの通信経路を決定する。
【００２２】
通信経路が決定されると、経路設定サーバ１０は、決定された通信経路上の各ノード５に対して、当該フローのデータ（パケット、フレーム）を当該決定された通信経路に沿って転送するように指示する。各ノード５は、その指示に従って、自身の設定を行う。
【００２３】
例えば、各ノード５に「転送テーブル」が設けられる。転送テーブルは、フローデータ（パケット、フレーム）の入力元と転送先との対応関係を示すテーブルである。各ノード５は、その転送テーブルを参照することによって、入力元から受け取ったフローデータを指定された転送先に転送することができる。この場合、経路設定サーバ１０は、上記決定された通信経路に沿ってフローデータが転送されるように、各ノード５に対して転送テーブルを設定するよう指示する。各ノード５は、経路設定サーバ１０からの指示に従って、自身の転送テーブルの内容を設定する。
【００２４】
このような処理を実現するための経路設定サーバ１０とノード５との間のインターフェイス方式としては、様々考えられる。例えば、Ｏｐｅｎｆｌｏｗを利用することができる（http://www.openflowswitch.org/を参照）。その場合、“Ｏｐｅｎｆｌｏｗ  Ｃｏｎｔｒｏｌｌｅｒ”が経路設定サーバ１０となり、“Ｏｐｅｎｆｌｏｗ  Ｓｗｉｔｃｈ”が各ノード５となる。Ｏｐｅｎｆｌｏｗの“Ｓｅｃｕｒｅ  Ｃｈａｎｎｅｌ”を利用することにより、転送テーブルの設定が可能である。
【００２５】
２．経路設定処理の概要
図２は、送信元ノード５−Ｓから送信先ノード５−Ｄへの複数の通信経路を示す概念図である。図２に示されるように、多くの場合、送信元ノード５−Ｓから送信先ノード５−Ｄへは複数の通信経路が存在する。各通信経路はいくつかの中継ノード５−ｒを含んでおり、異なる通信経路は異なる中継ノード５−ｒの組み合わせで構成されている。通信ネットワークＮＥＴにかかる負荷を分散させるためには、同じ送信元ノード５−Ｓと送信先ノード５−Ｄとの間の異なるフローに対して、異なる通信経路を設定することが好ましい。
【００２６】
本実施の形態に係る経路設定サーバ１０は、通信ネットワークＮＥＴにかかる負荷が分散されるように、フローの通信経路を決定する。すなわち、経路設定サーバ１０は、同じ送信元ノード５−Ｓと送信先ノード５−Ｄとの間の異なるフローに対して、なるべく異なる通信経路を決定する。そのために、経路設定サーバ１０は、ある１つのフローの通信経路を決定する際、当該フローの送信元ノード５−Ｓから送信先ノード５−Ｄに向かって、１ホップずつ“ランダム”に中継ノード５−ｒを決定していく。つまり、経路決定に際し、１ホップ毎にランダム性が導入される。その結果、フロー毎に異なる通信経路が決定される可能性が極めて高くなる。これにより、通信ネットワークＮＥＴにかかる負荷が分散され、通信効率が向上する。
【００２７】
本実施の形態では、ある１つのフローの通信経路を決定する際に、送信元ノード５−Ｓから送信先ノード５−Ｄへの複数の通信経路が算出されるわけではない。その代わり、１ホップ毎に、中継ノード５−ｒの候補からランダムな１つが選択される。このとき、経路設定サーバ１０における計算回数は、たかだか、当該通信経路の総ホップ数である。従って、経路設定サーバ１０における計算量は大幅に削減される。すなわち、本実施の形態によれば、経路決定サーバ１０における計算量を削減しながら、通信ネットワークＮＥＴにかかる負荷を分散させることが可能となる。
【００２８】
尚、以上に説明された経路設定処理は、経路設定サーバ１０が経路設定プログラムを実行することにより実現される。経路設定プログラムは、経路設定サーバ１０によって実行されるコンピュータプログラムであり、コンピュータ読み取り可能な記録媒体に記録されていてもよい。
【００２９】
３．経路設定サーバの様々な例
３−１．第１の実施の形態
図３は、第１の実施の形態に係る経路設定サーバ１０の構成を示すブロック図である。経路設定サーバ１０は、ネットワーク情報収集管理部１００、記憶部２００、及び経路設計部３００を備えている。
【００３０】
ネットワーク情報収集管理部１００は、ネットワーク情報ＩＮＦを収集する。ネットワーク情報ＩＮＦは、通信ネットワークＮＥＴに関する情報であり、ノード５間の接続状況やリンクコストに関する情報を含む。そして、ネットワーク情報収集管理部１００は、収集したネットワーク情報ＩＮＦに基づいて、記憶部２００に格納される各種情報やテーブルを作成・更新する。尚、コンピュータ情報収集管理部１００は、経路設定サーバ１０が経路設定プログラムを実行することにより実現される。
【００３１】
記憶部２００は、ＲＡＭやＨＤＤ等の記憶装置である。記憶部２００には、トポロジ情報２１０、ルーティングテーブル２２０−１〜２２０−ｎ、経路ノードリスト２３０等が格納される。
【００３２】
トポロジ情報２１０は、ノード５間の接続状況、すなわち、通信ネットワークＮＥＴの物理トポロジを示す。トポロジ情報２１０は、ネットワーク情報収集管理部１００によって作成・更新される。
【００３３】
次に、ルーティングテーブル２２０を説明するために、図４を参照して、「対象ノード」と「次ホップノード」を説明する。対象ノード５−ｉは、ノード５−１〜５−ｎのいずれかである（ｉ＝１〜ｎ）。また、送信先ノード５−ｊは、ノード５−１〜５−ｎのいずれかであり、対象ノード５−ｉとは異なる（ｊ＝１〜ｎ、ｊ≠ｉ）。対象ノード５−ｉから送信先ノード５−ｊへフローデータを伝達することを考える。このとき、対象ノード５−ｉからのフローデータの転送先となる次のノードが、「次ホップノード５−ｉｊ」である。つまり、次ホップノード５−ｉｊは、フローデータが経由する対象ノード５−ｉの次のホップのノードである。ある対象ノード５−ｉに関して、次ホップノード５−ｉｊの候補は複数存在し得る。候補がｍ個（ｍは自然数）ある場合、それらは５−ｉｊ（１）〜５−ｉｊ（ｍ）で表される。一般化すれば、ある対象ノード５−ｉに関して、次ホップノード候補５−ｉｊ（ｋ）；ｋ＝１〜ｍが存在する。尚、次ホップノード候補５−ｉｊ（ｋ）は、送信先ノード５−ｊから遠ざかるようなものであっても構わない。
【００３４】
ルーティングテーブル２２０は、以上に説明された次ホップノードの候補を示す「次ホップ情報」である。より詳細には、ノード５−１〜５−ｎのそれぞれに対してルーティングテーブル２２０−１〜２２０−ｎが設けられている。つまり、ある対象ノード５−ｉとルーティングテーブル２２０−ｉは互いに関連付けられている。ルーティングテーブル２２０−ｉは、対象ノード５−ｉに関する次ホップノード候補５−ｉｊ（ｋ）を示す。
【００３５】
図５は、対象ノード５−ｉに対するルーティングテーブル２２０−ｉの一例を示している。図５に示されるように、ルーティングテーブル２２０−ｉは、送信先ノード５−ｊ（ｊ＝１〜ｎ、ｊ≠ｉ）毎に、次ホップノード候補５−ｉｊ（ｋ）を示している。更に、ルーティングテーブル２２０−ｉは、各次ホップノード候補５−ｉｊ（ｋ）に対して規定される「選択確率Ｐｉｊ（ｋ）」も示している。選択確率Ｐｉｊ（ｋ）は、ｍ個の次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（ｍ）の中から次ホップノード５−ｉｊ（ｋ）が選択される確率である。ｍ個の選択確率Ｐｉｊ（ｋ）の和は１である。
【００３６】
（数１）
0005532347.tif 000002
【００３７】
選択確率Ｐｉｊ（ｋ）の計算方法としては様々考えられる。例えば、対象ノード５−ｉから次ホップノード候補５−ｉｊ（ｋ）を経由して送信先ノード５−ｊへ向かう最短経路のコスト（経路コスト）が算出される。経路コストは、当該経路を構成するリンクのそれぞれのリンクコストの和である。リンクコストは、回線容量が少ないほど、空き容量が少ないほど、遅延時間が大きいほど、パケットロスが多いほど、増加する。そして、算出された経路コストに反比例する値が、選択確率Ｐｉｊ（ｋ）として用いられる。ネットワーク情報収集管理部１００は、上述のネットワーク情報ＩＮＦやトポロジ情報２１０を用いることによって、各選択確率Ｐｉｊ（ｋ）を算出し、また、各ルーティングテーブル２２０−ｉを作成・更新する。
【００３８】
再度図３を参照して、記憶部２００に格納される経路ノードリスト２３０は、次に説明される経路設計部３００によって設計される通信経路を示す情報である。
【００３９】
経路設計部３００は、経路設定サーバ１０が経路設定プログラムを実行することにより実現される。この経路設計部３００は、次ホップ決定部３３０、ループ検出部３５０、ループ解消部３７０、及びノード設定部３９０を含んでいる。これら機能ブロックは、記憶部２００に格納されている情報やテーブルを参照して、本実施の形態に係る経路設定処理を実行する。図６は、本実施の形態に係る経路設定処理を示すフローチャートである。図７は、経路ノードリスト２３０を概念的に示している。以下、本実施の形態に係る経路設定処理を詳細に説明する。
【００４０】
ステップＳ１０：
あるフローが発生した場合、経路設計部３００は、当該フローに関する経路設定要求ＲＥＱを通信ネットワークＮＥＴから受け取る。経路設定要求ＲＥＱは、当該フローの送信元ノード５−Ｓと送信先ノード５−Ｄを示している。
【００４１】
ステップＳ３２０：
次ホップ決定部３３０は、経路設定要求ＲＥＱを受け取り、送信元ノード５−Ｓと送信先ノード５−Ｄを認識する。そして、次ホップ決定部３３０は、対象ノード５−ｉを送信元ノード５−Ｓに初期設定する。次ホップ決定部３３０は、その送信元ノード５−Ｓを最初のエントリとして経路ノードリスト２３０に書き込む（図７参照）。
【００４２】
ステップＳ３３０：
次ホップ決定部３３０は、現在の対象ノード５−ｉに関して「次ホップ決定処理」を実行する。次ホップ決定処理では、次ホップ決定部３３０は、対象ノード５−ｉに関連付けられたルーティングテーブル２２０−ｉ（次ホップ情報）を参照して、次ホップノードを“ランダム”に選択する。図８は、本実施の形態における次ホップ決定処理を示すフローチャートである。
【００４３】
ステップＳ３３１：
次ホップ決定部３３０は、現在の対象ノード５−ｉのためのルーティングテーブル２２０−ｉを参照する。そして、次ホップ決定部３３０は、送信先ノード５−ｊ（＝ノード５−Ｄ）への次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（ｍ）を抽出する。
【００４４】
ステップＳ３３５：
続いて、次ホップ決定部３３０は、抽出された次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（ｍ）の中から１つの次ホップノード５−ｉｊをランダムに選択する。例えば、次ホップ決定部３３０は、乱数と選択確率Ｐｉｊ（ｋ）を利用する。次ホップノード候補５−ｉｊ（ｋ）の選択確率Ｐｉｊ（ｋ）は、ルーティングテーブル２２０−ｉから読み出される。
【００４５】
例として、ｍ＝３であり、次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（３）の選択確率Ｐｉｊ（１）〜Ｐｉｊ（３）がそれぞれ０．２、０．３、０．５である場合を考える。このとき、次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（３）に関し、それぞれの選択確率Ｐｉｊ（１）〜Ｐｉｊ（３）に応じた数値範囲が規定される。例えば、次ホップ決定部３３０は、０．０以上０．２未満の範囲を次ホップノード候補５−ｉｊ（１）に対応づけ、０．２以上０．５未満の範囲を次ホップノード候補５−ｉｊ（２）に対応づけ、０．５以上１．０未満の範囲を次ホップノード候補５−ｉｊ（３）に対応づける。その上で、次ホップ決定部３３０は、０．０以上１未満の範囲内で乱数Ｘを発生させる。そして、次ホップ決定部３３０は、発生した乱数Ｘを含む数値範囲に対応付けられた次ホップノード候補を選択する。例えば、乱数Ｘが０．３の場合、次ホップ決定部３３０は、次ホップノード候補５−ｉｊ（２）を選択する。このようにして、上記選択確率Ｐｉｊ（ｋ）に従って、且つ、ランダムに、１つの次ホップノード５−ｉｊを選択することができる。
【００４６】
ステップＳ３３６：
次ホップノード５−ｉｊが選択されると、次ホップ決定部３３０は、その選択された次ホップノード５−ｉｊを中継ノード５−ｒとして経路ノードリスト２３０に追加登録する（図７参照）。そして、次ホップ決定部３３０は、対象ノードｉを、選択された次ホップノード５−ｉｊに更新する。
【００４７】
ステップＳ３４０：
図６に戻り、次ホップ決定処理（ステップＳ３３０）が完了すると、次ホップ決定部３３０は、更新後の対象ノード５−ｉ（選択された次ホップノード）が送信先ノード５−Ｄと一致しているか否かを調べる。つまり、次ホップ決定部３３０は、対象ノード５−ｉが送信先ノード５−Ｄまで到達したか否かを調べる。
【００４８】
ステップＳ３５０：
対象ノード５−ｉが未だ送信先ノード５−Ｄに到達していない場合（ステップＳ３４０；Ｎｏ）、ループ検出部３５０が、これまでに決定された経路上にループが発生しているか否かを判定する。具体的には、ループ検出部３５０は、経路ノードリスト２３０を参照して、現在の対象ノード５−ｉ（経路ノードリスト２３０中の最も下のエントリ）が過去の対象ノード（最下エントリ以外のエントリ）と重複しているか否かを調べる。現在の対象ノード５−ｉが過去のいずれかの対象ノードと重複する場合、ループ検出部３５０は、これまでに決定された経路上にループが発生していることを検出する。
【００４９】
ループが発生していない場合（ステップＳ３５０；Ｎｏ）、処理はステップＳ３３０に戻り、次ホップ決定部３３０は、新たな対象ノード５−ｉに関する次ホップ決定処理を実行する。一方、ループが検出された場合（ステップＳ３５０；Ｙｅｓ）、処理はステップＳ３７０に移る。
【００５０】
ステップＳ３７０：
ループ解消部３７０は、検出されたループを解消する。そのために、ループ解消部３７０は、経路ノードリスト２３０に登録されているエントリの後ろからいくつかを削除する。すなわち、ループ解消部３７０は、対象ノード５−ｉを過去のいずれかの対象ノードに戻す。言い換えれば、ループ解消部３７０は、これまでに決定された経路を縮退させる。
【００５１】
エントリの削除方針としてはいくつか考えられる。例えば、ループ解消部３７０は、経路ノードリスト２３０中の最後のエントリを削除する。これは、対象ノード５−ｉを１ホップだけ前に戻すことに相当する。あるいは、ループ解消部３７０は、ループ開始位置（重複ノードが最初に出現する位置）までエントリを削除してもよい。これは、対象ノード５−ｉを、現在のものから、現在のものと重複している過去のものまで戻すことに相当する。あるいは、ループ解消部３７０は、１ホップずつ戻りながらルーティングテーブル２２０−ｉを参照し、選択確率Ｐｉｊ（ｋ）が減少しはじめた位置までエントリを削除してもよい。
【００５２】
ステップＳ３３０’：
ループ解消部３７０によってループが解消された後、次ホップ決定部３３０は、新たな対象ノード５−ｉから、次ホップ決定処理（ステップＳ３３０）をやり直す。この再決定処理において、次ホップ決定部３３０は、前回一度選択された次ホップノード５−ｉｊを候補から除外してもよい。その場合、次ホップ決定部３３０は、次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（ｍ）の中から、前回選択されたものではない１つをランダムに選択する。次ホップノード候補が前回に選択されたものだけしかない場合、次ホップ決定部３３０は、経路ノードリスト２３０中の最後のエントリを更に削除して対象ノード５−ｉを更に１ホップだけ戻し、その後、次ホップ決定処理をやり直す。次ホップ決定処理の後、処理は、ステップＳ３４０に戻る。
【００５３】
以上に説明された処理が繰り返され、次ホップ決定部３３０は、送信元ノード５−Ｓから送信先ノード５−Ｄに向かって１ホップずつランダムに中継ノード５−ｒを決定していく。最終的に、対象ノード５−ｉは送信先ノード５−Ｄに到達する（ステップＳ３４０；Ｙｅｓ）。すなわち、送信元ノード５−Ｓから送信先ノード５−Ｄへの通信経路が決定される。このように、本実施の形態に係る経路設計部３３０は、次ホップ決定処理を繰り返すことによって、送信元ノード５−Ｓから送信先ノード５−Ｄへの通信経路を１ホップずつランダムに決定する。
【００５４】
ステップＳ３９０：
通信経路が決定されると、ノード設定部３９０は、決定された通信経路上の各ノード５に対して、フローデータ（パケット、フレーム）を当該決定された通信経路に沿って転送するように指示する。より詳細には、ノード設定部３９０は、経路ノードリスト２３０に登録されている各ノード５に対して、転送テーブル設定コマンドＣＭＤを送出する。転送テーブル設定コマンドＣＭＤは、上記決定された通信経路に沿ってフローデータが転送されるように転送テーブルを設定するよう指示するコマンドである。
【００５５】
決定された通信経路上の各ノード５は、経路設定サーバ１０から転送テーブル設定コマンドＣＭＤを受け取り、それに従って自身の転送テーブルの内容を設定する。これにより、当該フローのデータが、送信元ノード５−Ｓから送信先ノード５−Ｄまで伝達されるようになる。
【００５６】
３−２．第２の実施の形態
図９は、第２の実施の形態に係る経路設定サーバ１０の構成を示すブロック図である。第１の実施の形態と重複する説明は、適宜省略される。第２の実施の形態において、記憶部２００には、更に、経路キャッシュ情報２４０が格納されている。また、経路設計部３００は、更に、キャッシュ検索部３１０を含んでいる。
【００５７】
図１０は、経路キャッシュ情報２４０を概念的に示している。経路キャッシュ情報２４０は、送信元ノード５−Ｓと送信先ノード５−Ｄの組み合わせに対する通信経路の候補（以下、「経路候補」と参照される）を示す。ここでの経路候補とは、過去に決定された通信経路（経路ノードリスト２３０）である。ある送信元ノード５−Ｓとある送信先ノード５−Ｄの１つの組み合わせに対して、複数の経路候補が既に存在している場合もある。
【００５８】
また、図１０に示されるように、各経路候補に対して選択確率も規定されている。経路候補の選択確率は、当該経路候補（経路ノードリスト２３０）の決定時に選択された全ての次ホップノード５−ｉｊ（ｋ）の選択確率Ｐｉｊ（ｋ）の積である。
【００５９】
図１１は、本実施の形態に係る経路設定処理を示すフローチャートである。ステップＳ１０は、第１の実施の形態の場合と同様である。第２の実施の形態では、まず最初に、キャッシュ検索部３１０が経路設定要求ＲＥＱを受け取る。
【００６０】
ステップＳ３１０：
キャッシュ検索部３１０は、経路設定要求ＲＥＱに応答して、経路キャッシュ情報２４０を検索する。つまり、キャッシュ検索部３１０は、経路設定要求ＲＥＱで指定される送信元ノード５−Ｓと送信先ノード５−Ｄの組み合わせに対する経路候補（過去の経路ノードリスト２３０）が経路キャッシュ情報２４０に含まれているか否かを調べる。
【００６１】
ステップＳ３１２：
キャッシュヒットの場合、すなわち、経路キャッシュ情報２４０が経路設定要求ＲＥＱに対応する経路候補を含んでいる場合（ステップＳ３１１；Ｙｅｓ）、キャッシュ検索部３１０は、その経路候補を経路キャッシュ情報２４０から抽出する。経路候補は複数存在する場合もある。そして、キャッシュ検索部３１０は、抽出された経路候補の中から、通信経路を確率的に選択する。具体的には、上述の次ホップノード候補の選択処理（ステップＳ３３５）の場合と同様に、乱数と経路候補の選択確率が利用される。但し、経路候補に関しては、選択確率の和は必ずしも１ではない。従って、経路候補が存在していても、発生した乱数によっては、１つの経路候補が選択されない場合もある。その意味で、経路候補からの通信経路の選択は確率的である。
【００６２】
ステップＳ３１４：
経路候補の中から１つの通信経路が選択された場合（ステップＳ３１３；Ｙｅｓ）、キャッシュ検索部３１０は、選択された通信経路（経路ノードリスト２３０）を今回の通信経路として採用する。その後、上述のステップＳ３２０〜Ｓ３７０はスキップされ、処理はステップＳ３９０に移る。
【００６３】
経路キャッシュ情報２４０が経路設定要求ＲＥＱに対応する経路候補を含んでいない場合（ステップＳ３１１；Ｎｏ）、あるいは、経路候補から通信経路が選択されない場合（ステップＳ３１３；Ｎｏ）、キャッシュ検索部３１０は、経路設定要求ＲＥＱを次ホップ決定部３３０に送る。その後、第１の実施の形態と同様にステップＳ３２０〜Ｓ３７０が実行され、経路設定要求ＲＥＱに応じた新たな通信経路が決定される。
【００６４】
ステップＳ３８０：
次ホップ決定部３３０は、決定された新たな通信経路（経路ノードリスト２３０）を、経路キャッシュ情報２４０に追加登録する。追加された通信経路は、今回の経路設定要求ＲＥＱで示される送信元ノード５−Ｓと送信先ノード５−Ｄとの組み合わせに対する新たな経路候補となる。その後、処理はステップＳ３９０に移る。
【００６５】
本実施の形態によれば、キャッシュヒットの場合に、通信経路決定までの時間が短縮される。
【００６６】
３−３．第３の実施の形態
図１２は、第３の実施の形態に係る経路設定サーバ１０の構成を示すブロック図である。第１の実施の形態と重複する説明は、適宜省略される。第３の実施の形態において、記憶部２００には、ルーティングテーブル２２０−１〜２２０−ｎの代わりに、リンクコストテーブル２５０と経路コストテーブル２６０が格納される。
【００６７】
図１３は、リンクコストテーブル２５０を概念的に示している。リンクコストテーブル２５０は、リンク毎にリンクコストを示している。１つのリンクは、隣り合うノードであるリンク始点ノードとリンク終点ノードで規定されている。リンク始点ノードとリンク終点ノードとは、１ホップ離れた関係にある。従って、リンクコストテーブル２５０は、各ノード５に関する次ホップノードの候補を示す「次ホップ情報」にもなる。
【００６８】
図１４は、経路コストテーブル２６０を概念的に示している。経路コストテーブル２６０は、送信元ノード５−１〜５−ｎと送信先ノード５−１〜５−ｎとの全ての組み合わせに関する経路コストを示している。経路コストは、送信元ノードから送信先ノードへの最短経路を構成するリンクのそれぞれのリンクコストの和である。任意の２ノード間の経路コストは、この経路コストテーブル２６０を参照することにより得ることができる。
【００６９】
これらリンクコストテーブル２５０及び経路コストテーブル２６０も、ネットワーク情報収集管理部１００によって作成・更新される。
【００７０】
第３の実施の形態では、次ホップ決定処理（ステップＳ３３０）において、ルーティングテーブル２２０の代わりに、リンクコストテーブル２５０と経路コストテーブル２６０が参照される。それ以外は、第１の実施の形態と同じである。図１５は、本実施の形態における次ホップ決定処理（ステップＳ３３０）を示すフローチャートである。
【００７１】
ステップＳ３３２：
次ホップ決定部３３０は、リンクコストテーブル２５０を参照して、対象ノード５−ｉに対する次ホップノード候補５−ｉｊ（ｋ）を抽出する。具体的には、次ホップ決定部３３０は、リンク始点ノードが対象ノード５−ｉに一致するエントリを、リンクコストテーブル２５０から抽出する。抽出されたエントリに含まれるリンク終点ノードが、次ホップノード候補５−ｉｊ（ｋ）である。
【００７２】
ステップＳ３３３：
次に、次ホップ決定部３３０は、対象ノード５−ｉから次ホップノード候補５−ｉｊ（ｋ）を経由して送信先ノード５−ｊへ向かう経路の経路コストを算出する。対象ノード５−ｉ（リンク始点ノード）から次ホップノード候補（リンク終点ノード）への経路コストは、リンクコストテーブル２５０で示されるリンクコストである。次ホップノード候補５−ｉｊ（ｋ）から送信先ノード５−ｊへの経路コストは、経路コストテーブル２６０から得られる。それら２つの経路コストの和が、求めるべき経路コストである。更に、次ホップ決定部３３０は、算出された経路コストから、次ホップノード候補５−ｉｊ（ｋ）の選択確率Ｐｉｊ（ｋ）を算出する。経路コストと選択確率Ｐｉｊ（ｋ）の関係は、第１の実施の形態と同じである。
【００７３】
このようにして、次ホップ決定部３３０は、次ホップノード候補５−ｉｊ（ｋ）を抽出し、また、選択確率Ｐｉｊ（ｋ）を算出することができる。すなわち、第１の実施の形態におけるルーティングテーブル２２０−ｉ（図５参照）で与えられる情報と同じものが得られる。その後は、第１の実施の形態と同様に、ステップＳ３３５、Ｓ３３６が実行される。
【００７４】
尚、第２の実施の形態と第３の実施の形態を組み合わせることも可能である。
【００７５】
以上、本発明の実施の形態が添付の図面を参照することにより説明された。但し、本発明は、上述の実施の形態に限定されず、要旨を逸脱しない範囲で当業者により適宜変更され得る。
【００７６】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００７７】
（付記１）
複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定サーバであって、
前記複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報が格納される記憶部と、
フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、前記送信元ノードから前記送信先ノードへの通信経路を設計する経路設計部と
を備え、
前記経路設計部は、
前記次ホップ情報を参照しながら次ホップ決定処理を実行する次ホップ決定部と、
ループ検出部と、
ループ解消部と
を含み、
前記次ホップ決定処理において、前記次ホップ決定部は、対象ノードに関する前記次ホップノードの前記候補の中から１つの次ホップノードをランダムに選択し、前記対象ノードを前記選択された１つの次ホップノードに更新し、
前記次ホップ決定部は、前記対象ノードを前記送信元ノードに初期設定した後、前記対象ノードが前記送信先ノードとなるまで前記次ホップ決定処理を繰り返すことによって前記通信経路を１ホップずつ決定し、
前記ループ検出部は、現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された前記通信経路上のループを検出し、
前記ループが検出された場合、前記ループ解消部は、前記対象ノードを過去のいずれかの対象ノードに戻すことによって前記ループを解消し、
前記ループが解消された後、前記次ホップ決定部は、前記過去のいずれかの対象ノードから前記次ホップ決定処理をやり直す
経路設定サーバ。
【００７８】
（付記２）
付記１に記載の経路設定サーバであって、
前記ループ解消部は、前記対象ノードを１ホップだけ戻すことによって前記ループを解消する
経路設定サーバ。
【００７９】
（付記３）
付記１に記載の経路設定サーバであって、
前記ループ解消部は、前記対象ノードを、前記現在の対象ノードと重複しているものまで戻すことによって前記ループを解消する
経路設定サーバ。
【００８０】
（付記４）
付記１乃至３のいずれか一項に記載の経路設定サーバであって、
前記次ホップ決定処理をやり直す場合、前記次ホップ決定部は、前回に選択された次ホップノードを前記候補から除外する
経路設定サーバ。
【００８１】
（付記５）
付記４に記載の経路設定サーバであって、
前記候補が前回に選択された次ホップノードだけの場合、前記次ホップ決定部は、前記対象ノードを更に１ホップだけ戻した後、前記次ホップ決定処理をやり直す
経路設定サーバ。
【００８２】
（付記６）
付記１乃至５のいずれか一項に記載の経路設定サーバであって、
前記対象ノードに関する前記候補は第１候補と第２候補を含み、
前記次ホップ決定処理において、前記次ホップ決定部は、所定の範囲内で乱数を発生させ、
前記発生した乱数が前記所定の範囲に含まれる第１範囲内の場合、前記次ホップ決定部は、前記第１候補を選択し、
前記発生した乱数が前記所定の範囲に含まれる第２範囲内の場合、前記次ホップ決定部は、前記第２候補を選択する
経路設定サーバ。
【００８３】
（付記７）
付記６に記載の経路設定サーバであって、
前記第１範囲は、前記第１候補が選択される第１選択確率に基づいて規定され、
前記第２範囲は、前記第２候補が選択される第２選択確率に基づいて規定される
経路設定サーバ。
【００８４】
（付記８）
付記７に記載の経路設定サーバであって、
前記第１選択確率は、前記対象ノードから前記第１候補を経由して前記送信先ノードへ向かう経路のコストに反比例し、
前記第２選択確率は、前記対象ノードから前記第２候補を経由して前記送信先ノードへ向かう経路のコストに反比例する
経路設定サーバ。
【００８５】
（付記９）
付記１乃至８のいずれか一項に記載の経路設定サーバであって、
前記記憶部には更に、経路キャッシュ情報が格納され、
前記経路キャッシュ情報は、前記送信元ノードと前記送信先ノードとの組み合わせに対して過去に決定された前記通信経路を経路候補として示し、
前記次ホップ決定部は、前記決定された通信経路を、前記経路設定要求で示される前記送信元ノードと前記送信先ノードとの組み合わせに対する前記経路候補として、前記経路キャッシュ情報に追加する
経路設定サーバ。
【００８６】
（付記１０）
付記９に記載の経路設定サーバであって、
前記経路設計部は更に、キャッシュ検索部を含み、
前記キャッシュ検索部は、前記経路設定要求に応答して前記経路キャッシュ情報を検索し、
前記経路キャッシュ情報が前記経路設定要求に対応する前記経路候補を含んでいる場合、前記キャッシュ検索部は、前記経路候補の中から前記通信経路を確率的に決定する
経路設定サーバ。
【００８７】
（付記１１）
付記１乃至１０のいずれか一項に記載の経路設定サーバであって、
前記経路設計部は更に、ノード設定部を備え、
前記ノード設定部は、前記決定された通信経路上の各ノードに対して、前記フローのデータを前記決定された通信経路に沿って転送するように指示する
経路設定サーバ。
【００８８】
（付記１２）
複数のノードを含む通信ネットワークと、
前記通信ネットワークにおけるフローの通信経路を決定する経路設定サーバと
を備え、
前記経路設定サーバは、
前記複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報が格納される記憶部と、
フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、前記送信元ノードから前記送信先ノードへの通信経路を設計する経路設計部と
を備え、
前記経路設計部は、
前記次ホップ情報を参照しながら次ホップ決定処理を実行する次ホップ決定部と、
ループ検出部と、
ループ解消部と
を含み、
前記次ホップ決定処理において、前記次ホップ決定部は、対象ノードに関する前記次ホップノードの前記候補の中から１つの次ホップノードをランダムに選択し、前記対象ノードを前記選択された１つの次ホップノードに更新し、
前記次ホップ決定部は、前記対象ノードを前記送信元ノードに初期設定した後、前記対象ノードが前記送信先ノードとなるまで前記次ホップ決定処理を繰り返すことによって前記通信経路を１ホップずつ決定し、
前記ループ検出部は、現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された前記通信経路上のループを検出し、
前記ループが検出された場合、前記ループ解消部は、前記対象ノードを過去のいずれかの対象ノードに戻すことによって前記ループを解消し、
前記ループが解消された後、前記次ホップ決定部は、前記過去のいずれかの対象ノードから前記次ホップ決定処理をやり直す
通信ネットワークシステム。
【００８９】
（付記１３）
複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定方法であって、
前記複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報を、記憶装置に格納するステップと、
フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、前記送信元ノードから前記送信先ノードへの通信経路を設計するステップと
を含み、
前記通信経路を設計するステップは、
前記次ホップ情報を参照しながら次ホップ決定処理を実行するステップと、
ここで、
前記次ホップ決定処理は、
対象ノードに関する前記次ホップノードの前記候補の中から１つの次ホップノードをランダムに選択するステップと、
前記対象ノードを前記選択された１つの次ホップノードに更新するステップと
を含み、
前記対象ノードを前記送信元ノードに初期設定した後、前記対象ノードが前記送信先ノードとなるまで前記次ホップ決定処理を繰り返すことによって前記通信経路を１ホップずつ決定するステップと、
現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された前記通信経路上のループを検出するステップと、
前記ループが検出された場合、前記対象ノードを過去のいずれかの対象ノードに戻すことによって前記ループを解消するステップと、
前記ループが解消された後、前記過去のいずれかの対象ノードから前記次ホップ決定処理をやり直すステップと
を含む
経路設定方法。
【００９０】
（付記１４）
複数のノードを含む通信ネットワークにおけるフローの通信経路を決定する経路設定処理をコンピュータに実行させる経路設定プログラムが記録された記録媒体であって、
前記経路設定処理は、
前記複数のノードの各々に関して、データの転送先となる次ホップノードの候補を示す次ホップ情報を、記憶装置に格納するステップと、
フローの送信元ノードと送信先ノードを示す経路設定要求に応答して、前記送信元ノードから前記送信先ノードへの通信経路を設計するステップと
を含み、
前記通信経路を設計するステップは、
前記次ホップ情報を参照しながら次ホップ決定処理を実行するステップと、
ここで、
前記次ホップ決定処理は、
対象ノードに関する前記次ホップノードの前記候補の中から１つの次ホップノードをランダムに選択するステップと、
前記対象ノードを前記選択された１つの次ホップノードに更新するステップと
を含み、
前記対象ノードを前記送信元ノードに初期設定した後、前記対象ノードが前記送信先ノードとなるまで前記次ホップ決定処理を繰り返すことによって前記通信経路を１ホップずつ決定するステップと、
現在の対象ノードが過去の対象ノードと重複しているか否かを調べることによって、それまでに決定された前記通信経路上のループを検出するステップと、
前記ループが検出された場合、前記対象ノードを過去のいずれかの対象ノードに戻すことによって前記ループを解消するステップと、
前記ループが解消された後、前記過去のいずれかの対象ノードから前記次ホップ決定処理をやり直すステップと
を含む
記録媒体。
【００９１】
本出願は、２００９年３月２３日に出願された日本国特許出願２００９−０６９７９４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
0005532347.tif 000003
【図２】
0005532347.tif 000004
【図３】
0005532347.tif 000005
【図４】
0005532347.tif 000006
【図５】
0005532347.tif 000007
【図６】
0005532347.tif 000008
【図７】
0005532347.tif 000009
【図８】
0005532347.tif 000010
【図９】
0005532347.tif 000011
【図１０】
0005532347.tif 000012
【図１１】
0005532347.tif 000013
【図１２】
0005532347.tif 000014
【図１３】
0005532347.tif 000015
【図１４】
0005532347.tif 000016
【図１５】
0005532347.tif 000017