(57)【要約】  制御サーバを用いて、確率的に経由ノードを選択し、経路決定を行う際に、迅速にループのない経路決定を行う経路選択方法、情報処理装置、ネットワークシステムおよび経路選択プログラムを提供する。送信元から宛先へ複数の経路が存在するネットワークを制御する。そして、ノード間転送確率に基づいて経路を形成するノードを選択し、選択したノードがその経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように転送確率を再設定する。
2011114627.tif 000002
【特許請求の範囲】
【請求項１】
送信元から宛先へ複数の経路が存在するネットワークを制御する経路選択方法において、
ノード間転送確率に基づいて前記経路を形成するノードを選択し、
選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する
ことを特徴とする経路選択方法。
【請求項２】
選択した前記ノードが前記経路で既に経由されたノードである場合に、該ノードへの転送確率を、該ノードを経由しない場合の転送確率に対して小さな値に再設定する
請求項１に記載の経路選択方法。
【請求項３】
０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させ、
次ホップノードを確率的に選択する
請求項１に記載の経路選択方法。
【請求項４】
送信元から宛先へ複数の経路が存在するネットワークシステムを制御する情報処理装置であって、
ノード間転送確率に基づいて前記経路を形成するノードを選択する手段と、
選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する手段とを有する
ことを特徴とする情報処理装置。
【請求項５】
選択した前記ノードが前記経路で既に経由されたノードである場合に、該ノードへの転送確率を、該ノードを経由しない場合の転送確率に対して小さな値に再設定する手段を有する
請求項４に記載の情報処理装置。
【請求項６】
０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させ、次ホップノードを確率的に選択する手段を有する
請求項４に記載の情報処理装置。
【請求項７】
送信元から宛先へ複数の経路が存在するネットワークシステムにおいて、
前記複数の経路から所定の経路を設定する制御サーバを有し、
前記制御サーバは、
ノード間転送確率に基づいて前記経路を形成するノードを選択する手段と、
選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する手段とを有する
ことを特徴とするネットワークシステム。
【請求項８】
選択した前記ノードが前記経路で既に経由されたノードである場合に、該ノードへの転送確率を該ノードを経由しない場合の転送確率に対して小さな値に再設定する手段を有する
請求項７に記載のネットワークシステム。
【請求項９】
０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させ、次ホップノードを確率的に選択する手段を有する
請求項７に記載のネットワークシステム。
【請求項１０】
送信元から宛先へ複数の経路が存在するネットワークシステムにおいて前記複数の経路から所定の経路を設定するコンピュータに、
ノード間転送確率に基づいて前記経路を形成するノードを選択する処理と、
選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する処理とを
実行させるための経路選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路選択方法、情報処理装置、ネットワークシステムおよび経路選択プログラムに関し、特に、ネットワークに配置されたノードによりフローを転送して通信を実現する経路選択方法、情報処理装置、ネットワークシステムおよび経路選択プログラムに関する。
【背景技術】
【０００２】
複数のノードを含む通信ネットワークが管理サーバによって集中的に管理される通信ネットワークシステムが知られている。管理サーバは、あるフローに関する経路設定要求を受け取ると、通信ネットワークにおける当該フローの通信経路を決定する。このようにフローの通信経路を決定する管理サーバは、以下、「制御サーバ」とも参照される。【０００３】
ある送信元ノードからある送信先ノードへの最短経路を求めるアルゴリズムとして、非特許文献１では、ダイクストラ法（Dijkstra's Algorithm）が記載されている。しかしながら、それら送信元ノードと送信先ノードとの間で複数のフローの通信が行われる場合、単純にダイクストラ法を用いるだけでは、それら複数のフローに対して同じ通信経路（最短経路）が設定されてしまう。このことは、当該通信経路にかかる負荷を増大させ、通信効率を低下させる。【０００４】
負荷を分散させるためには、同じ送信元ノードと送信先ノードとの間の異なるフローに対して、異なる通信経路を設定することが好適である。そのためには、それら送信元ノードと送信先ノードとの間で、最短経路だけでなく他の通信経路をも抽出することが考えられる。送信元ノードから送信先ノードへの複数の通信経路を求める技術として、次のものが知られている。【０００５】
非特許文献２には、k番目に短い経路までをダイクストラ法によって抽出し、パケットまたはフローの経路をk番目に短い経路の中からランダムに割り当てるk-shortest path が記載されている。これにより、送信元ノードから送信先ノードへ複数の経路を求めることが出来る。【０００６】
しかしながら、k-shortest path 方法を用いる場合、ダイスクストラ法によって通信経路を求めるため、計算量が膨大になってしまうという問題がある。【０００７】
計算量を抑えつつ、負荷を分散させ、ある送信元ノードから送信先ノードへの経路を求める方法として、非特許文献３に記載の方法がある。非特許文献３には、経路中のノードがある送信先への転送確率テーブルを生成し、その転送確率テーブルを用いて、確率に基づいてパケットを転送させる方法が記載されている。この場合、転送確率テーブルは、送信先ノードに対する、隣接スイッチとそれへの転送確率を保持する。送信先ノードのアドレスが決定されると、確率的に隣接するノードへパケットを転送する。【０００８】
非特許文献３に記載の方法は、転送確率テーブルの構築が容易であるため、計算量を抑えることが可能である。【０００９】
なお、非特許文献３に記載の方法は、確率的なパケット転送のための方法であるが、この方法はフロー転送のための方法として適用可能である。【００１０】
同じ送信元ノードと送信先ノードとの間の異なるフローに対して、異なる通信経路を設定する方法として、非特許文献４にオープンフロー（ＯｐｅｎＦｌｏｗ）という技術が提案されている。オープンフローは、通信をエンドツーエンドのフローとして捉え、フロー単位で経路制御、障害回復、負荷分散、最適化を行うものである。転送ノードとして機能するオープンフロースイッチは、オープンフローコントローラとの通信用のセキュアチャネルを備え、オープンフローコントローラから適宜追加または書き換え指示されるフローテーブルに従って動作する。フローテーブルには、フロー毎に、パケットヘッダと照合するルールと、処理内容を定義したアクションと、フロー統計情報との組が定義される。【００１１】
例えば、オープンフロースイッチは、最初のパケット（ｆｉｒｓｔ  ｐａｃｋｅｔ）を受信すると、フローテーブルから、受信パケットのヘッダ情報に適合するルール（ＦｌｏｗＫｅｙ）を持つエントリを検索する。検索の結果、受信パケットに適合するエントリが見つかった場合、オープンフロースイッチは、受信パケットに対して、当該エントリのアクションフィールドに記述された処理内容を実施する。一方、前記検索の結果、受信パケットに適合するエントリが見つからなかった場合、オープンフロースイッチは、セキュアチャネルを介して、オープンフローコントローラに対して受信パケットを転送し、受信パケットの送信元・送信先に基づいたパケットの経路の決定を依頼し、これを実現するフローエントリを受け取ってフローテーブルを更新する。【００１２】
転送確率テーブルを用いて確率的にフローを転送させる方法では、確率的に次ホップを選択するため、ルーティングループが発生する可能性がある。ルーティングループの発生は、通信効率を低下させる。【００１３】
特許文献１には、転送確率テーブルを用いて確率的にフローを転送させる方法において、ルーティングループが発生した場合に、それを回避する方法が記述されている。【００１４】
特許文献１に記載の方法では、次ホップノードの候補から１つのノードをランダムに選択し、対象ノードを上記選択された１つの次ホップノードに更新し、対象ノードが既に経由しているノードであるか否かを確認する。この結果、対象ノードが既に経由しているノードであれば、ループが発生していると判断し、経路をループが発生する前の状態に縮退する。つまり、ループの発生が検出される度に、次ホップのノード選択をやり直すという方法である。【００１５】
特許文献１に記載の方法では、ルーティングループを発生させずに経路決定を行うことができるものの、ルーティングループが多く発生するような環境においては、対象ノードが既に経由しているノードである可能性が高く、かつ、それに伴い経路縮退を多数繰り返す可能性が高くなる。これにより、特許文献１に記載の方法では経路計算のための計算量が増大し、経路計算を迅速に行うことが出来ない。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２０００−１１５２５５号公報
【非特許文献】
【００１７】
【非特許文献１】Edsger W. Dijkstra, "A Note on Two Problems in Connexion with Graphs" Numerische Mathematik, vol.1, pp.269-271 (1959)
【非特許文献２】David Eppstein, “Finding the k Shortest Path”, March,1997
【非特許文献３】Y. Honma, M. Aida, H. Shimonishi and A. Iwata, A New Multi-path Routing Methodology Based on Logit Type Assignment, In FutureNet II, 2009.ｐ．１３−１８
【非特許文献４】Nick McKeown et al.,“OpenFlow: enabling innovation  in  campus  networks,”  ACM  SIGCOMM Computer  Communication  Review,  vol.38, issue  2, pp.69-74, April 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１８】
通信効率低下を防止するため、ルーティングループを含まない経路を迅速に決定する必要がある。【００１９】
しかしながら、上述の技術では、ルーティングループが多発する環境においては、通信経路を決定する制御サーバにおける計算量が膨大となり、迅速に経路決定を行うことが出来ない。【００２０】
本発明の目的は、制御サーバを用いて、確率的に経由ノードを選択し、経路決定を行う際に、迅速にループのない経路決定を行うことにある。
【課題を解決するための手段】
【００２１】
本発明による経路選択方法は、送信元から宛先へ複数の経路が存在するネットワークを制御する経路選択方法において、ノード間転送確率に基づいて経路を形成するノードを選択し、選択したノードがその経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように転送確率を再設定することを特徴とする。【００２２】
また、本発明による情報処理装置は、送信元から宛先へ複数の経路が存在するネットワークシステムを制御する情報処理装置であって、ノード間転送確率に基づいて経路を形成するノードを選択する手段と、選択したノードがその経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように転送確率を再設定する手段とを有することを特徴とする。【００２３】
また、本発明によるネットワークシステムは、送信元から宛先へ複数の経路が存在するネットワークシステムにおいて、複数の経路から所定の経路を設定する制御サーバを有し、制御サーバが、ノード間転送確率に基づいて経路を形成するノードを選択する手段と、選択したノードがその経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように転送確率を再設定する手段とを有することを特徴とする。【００２４】
また、本発明による経路選択プログラムは、送信元から宛先へ複数の経路が存在するネットワークシステムにおいて複数の経路から所定の経路を設定するコンピュータに、ノード間転送確率に基づいて経路を形成するノードを選択する処理と、選択したノードがその経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように転送確率を再設定する処理とを実行させることを特徴とする。
【発明の効果】
【００２５】
本発明によれば、転送確率テーブルを用いて確率的にフローを転送させる方法において、迅速にルーティングループを形成するノードの選択が抑制されるように転送確率の再設定を行うことにより、ループを形成するノードの選択に伴って経路縮退を多数繰り返す可能性を大幅に減少させることが可能になる。よって、通信効率を向上させ、経路設定を迅速に行うことが可能となるという優れた効果を奏する。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施形態に係る通信ネットワークシステムを示す概略図である。
【図２】送信元ノードから送信先ノードへの通信経路を示す概念図である。
【図３】転送確率テーブルを示す概念図である。
【図４】本発明の実施形態に係る制御サーバの構成を示すブロック図である。
【図５】実施形態に係る経路設定方法を示すフローチャートである。
【図６】本発明の情報処理装置の主要部の例を示すブロック図である。
【図７】本発明のネットワークシステムの主要部の例を示すブロック図である。
【発明を実施するための形態】
【００２７】
添付図面を参照して、本発明の実施形態を説明する。
【００２８】
１．通信ネットワークシステム
図１は、本発明の実施形態に係る通信ネットワークシステム１を示す概略図である。通信ネットワークシステム１は、複数のノード５を含む通信ネットワーク（ＮＥＴ）を備えている。本実施形態では、通信ネットワーク（ＮＥＴ）はｎ個（ｎは２以上の整数）のノード５−１〜５−ｎを含んでいるとする。
【００２９】
通信経路が決定されると、制御サーバ１０は、決定された通信経路上の各ノード５に対して、当該フローのデータ（パケット、フレーム）を当該決定された通信経路に沿って転送するように指示する。各ノード５は、その指示に従って、自身の設定を行う。
【００３０】
例えば、各ノード５に「転送テーブル」が設けられる。転送テーブルは、フロー、もしくはパケットデータの入力元と転送先との対応関係を示すテーブルである。各ノード５は、その転送テーブルを参照することによって、入力元から受け取ったフロー、もしくはパケットデータを指定された転送先に転送することができる。この場合、制御サーバ１０は、上記決定された通信経路に沿ってフロー、もしくはパケットデータが転送されるように、各ノード５に対して転送テーブルを設定するよう指示する。各ノード５は、制御サーバ１０からの指示に従って、自身の転送テーブルの内容を設定する。
【００３１】
２．経路設定処理の概要
図２は、送信元ノード５−Ｓから送信先ノード５−Ｄへの複数の通信経路を示す概念図である。図２に示されるように、多くの場合、送信元ノード５−Ｓから送信先ノード５−Ｄへは複数の通信経路が存在する。各通信経路はいくつかの中継ノード５−ｒを含んでおり、異なる通信経路は異なる中継ノード５−ｒの組み合わせで構成されている。
【００３２】
３．転送確率テーブル
通信ネットワークからのネットワーク情報に基づいて、転送確率テーブル４００が構成することができる。転送確率テーブル４００を説明するために、図３を参照して、「対象ノード」と「次ホップノード」を説明する。対象ノード５−ｉは、ノード５−１〜５−ｎのいずれかである（ｉ＝１〜ｎ）。また、送信先ノード５−ｊは、ノード５−１〜５−ｎのいずれかであり、対象ノード５−ｉとは異なる（ｊ＝１〜ｎ、ｊ≠ｉ）。対象ノード５−ｉから送信先ノード５−ｊへフローデータを伝達することを考える。このとき、対象ノード５−ｉからのフローデータの転送先となる次のノードが、「次ホップノード５−ｉｊ」である。つまり、次ホップノード５−ｉｊは、フローデータが経由する対象ノード５−ｉの次のホップのノードである。ある対象ノード５−ｉに関して、次ホップノード５−ｉｊの候補は複数存在し得る。候補がｍ個（ｍは自然数）ある場合、それらは５−ｉｊ（１）〜５−ｉｊ（ｍ）で表される。一般化すれば、ある対象ノード５−ｉに関して、次ホップノード候補５−ｉｊ（ｋ）；ｋ＝１〜ｍが存在する。尚、次ホップノード候補５−ｉｊ（ｋ）は、送信先ノード５−ｊから遠ざかるようなものであっても構わない。
【００３３】
転送確率テーブル４００は、以上に説明された次ホップノードの候補を示す「次ホップ情報」である。より詳細には、ノード５−１〜５−ｎのそれぞれに対して転送確率テーブル４００−１〜４００−ｎが設けられている。つまり、ある対象ノード５−ｉと転送確率テーブル４００−ｉは互いに関連付けられている。転送確率テーブル４００−ｉは、対象ノード５−ｉに関する次ホップノード候補５−ｉｊ（ｋ）を示す。
【００３４】
図３は、対象ノード５−ｉに対する転送確率テーブル４００−ｉの一例を示している。図３に示されるように、転送確率テーブル４００−ｉは、送信先ノード５−ｊ（ｊ＝１〜ｎ、ｊ≠ｉ）毎に、次ホップノード候補５−ｉｊ（ｋ）を示している。更に、転送確率テーブル４００−ｉは、各次ホップノード候補５−ｉｊ（ｋ）に対して規定される「選択確率Ｐｉｊ（ｋ）」も示している。選択確率Ｐｉｊ（ｋ）は、ｍ個の次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（ｍ）の中から次ホップノード５−ｉｊ（ｋ）が選択される確率である。
【００３５】
本実施形態に係る制御サーバ１０は、転送確率テーブル４００に基づいて確率的にフロー、もしくはパケットを転送させる。この際、効率的にルーティングループを回避することにより、通信効率を低下させない経路決定を行うことが可能となる。
【００３６】
尚、以上に説明された経路設定処理は、制御サーバ１０が経路設定プログラムを実行することにより実現されてもよい。経路設定プログラムは、制御サーバ１０によって実行されるコンピュータプログラムであり、コンピュータ読み取り可能な記録媒体に記録されていてもよい。
【００３７】
４．制御サーバの例
図４は、実施形態に係る制御サーバ１０の構成を示すブロック図である。制御サーバ１０は、次ホップノード決定部１００、ノード設定部２００、ループ検出部３００、転送確率テーブル４００、経路ノードリスト５００を備えている。
【００３８】
次ホップノード決定部１００は、対象ノードに関する次ホップノードの候補とそれへの転送確率を転送確率テーブル４００より取得し、次ホップノードの候補から１つのノードをランダムに選択し、対象ノードを上記選択された１つの次ホップノードに更新し、経路ノードリスト５００に追加書き込みをする。
【００３９】
図５は、本実施形態に係る経路設定処理を示すフローチャートである。以下、本実施形態に係る経路設定処理を詳細に説明する。
【００４０】
ステップＳ２０：
あるフローが発生した場合、次ホップノード決定部１００は、当該フローに関する経路設定要求ＲＥＱを通信ネットワーク（ＮＥＴ）から受け取る。経路設定要求ＲＥＱは、当該フローの送信元ノード５−Ｓと送信先ノード５−Ｄを示している。
【００４１】
ステップＳ２１：
次ホップノード決定部１００は、経路設定要求ＲＥＱを受け取り、送信元ノード５−Ｓと送信先ノード５−Ｄを認識する。そして、次ホップノード決定部１００は、対象ノード５−ｉを送信元ノード５−Ｓに初期設定する。
【００４２】
ステップＳ２２：
次ホップノード決定部１００は、対象ノード５−ｉに関連付けられた、転送確率テーブル４００から次ホップ候補とそれへの転送確率を取得する。
【００４３】
ステップＳ２３：
ループ検出部３００は、ステップＳ２２で取得した次ホップ候補のうち、既に経路ノードリスト５００に書き込まれているノード（既に経由したノード）への転送確率を、次ホップ候補の中で経路ノードリスト５００に書込まれていないノードへの転送確率に対して小さな値に再設定して、既に経由したノードが次ホップのノードとして選択されることを抑制する。なお、既に経由したノードが次ホップのノードとして選択されることを抑制する方式として、既に経由したノードへの転送確率を小さくすることに限定されるものではない。次ホップ候補のうち、既に経由ノードリスト５００に書込まれているノードは、フロー送信の経路においてループを形成してしまう。このノードへの転送確率を、上述のように再設定することにより、以降に転送確率に基づいて次ホップを決定する際、ループを形成するノードを選択することを抑制することができる。その結果、ループを形成する経路縮退等の処理を実行する必要がなくなり、ルーティングループが多発する環境においても、計算量を抑止することができるので、迅速な経路設定が可能となる。なお、既に経路ノードリスト５００に書込まれているノードへの転送確率を小さな値に再設定する例について説明したが、本発明はこれに限定されるものではない。既にノードリスト５００に書込まれているノードへの転送確率を、そのノードが次ホップとして決定されることを抑制するように再設定する方式であればよい。例えば、既にノードリスト５００に書込まれているノードについて、転送確率を”0”に設定すること、次ホップ候補から除かれるような処理を実行すること、等が本発明に含まれる。
【００４４】
ステップＳ２４：
ステップS２３での処理の結果、全ての次ホップ候補への転送が抑制される状態になることが考えられる。例えば、全ての次ホップ候補への転送確率が所定の閾値を下回った場合、全ての次ホップ候補への転送確率が”0”に設定された場合、全ての次ホップ候補が次ホップとしての転送対象から除かれた場合等が該当する。よって、ステップS２４では、全ての次ホップ候補への転送が抑制される状態になっているか否かを判定する。以下、図５のフローチャートでは、既にノードリスト５００に書込まれているノードへの転送確率を”0”に再設定する例を用いて説明する。既に経路ノードリスト５００に書込まれているノードステップＳ２３で経路ノードリスト５００に書き込まれているノードへの転送確率を０にした結果、全ての次ホップ候補ノードへの転送確率が０になっているか否かを調べる。
【００４５】
ステップＳ２５：
ステップＳ２３で経路ノードリスト５００に書き込まれているノードへの転送確率を０にした結果、全ての次ホップ候補ノードへの転送確率が０になった場合（ステップＳ２４；Ｙｅｓ）、前ホップノードを対象ノード５−ｉとして、再度ステップＳ２２を実行する。
【００４６】
ステップＳ２６：
ステップＳ２３で経路ノードリスト５００に書き込まれているノードへの転送確率を０にした結果、全ての次ホップ候補ノードへの転送確率が０にならなかった場合（ステップＳ２４；Ｎｏ）、次ホップノード決定部１００は、転送確率テーブルから次ホップ候補と転送確率を取得し、次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（ｍ）の中から１つの次ホップノード５−ｉｊをランダムに選択する。例えば、次ホップノード決定部１００は、乱数と選択確率Ｐｉｊ（ｋ）を利用する。なお、転送確率の合計値は必ずしも１．０にならなくともよい。
【００４７】
例として、ｍ＝３であり、次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（３）の選択確率Ｐｉｊ（１）〜Ｐｉｊ（３）がそれぞれ０．２、０．３、０．６である場合を考える。このとき、次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（３）に関し、それぞれの選択確率Ｐｉｊ（１）〜Ｐｉｊ（３）に応じた数値範囲が規定される。例えば、次ホップノード決定部１００は、０．０以上０．２未満の範囲を次ホップノード候補５−ｉｊ（１）に対応づけ、０．２以上０．５未満の範囲を次ホップノード候補５−ｉｊ（２）に対応づけ、０．５以上１．１未満の範囲を次ホップノード候補５−ｉｊ（３）に対応づける。その上で、次ホップノード決定部１００は、転送確率の合計値が１．０であるとは限らないため、０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させる。そして、次ホップノード決定部１００は、発生した乱数Ｘを含む数値範囲に対応付けられた次ホップノード候補を選択する。例えば、乱数Ｘが０．３の場合、次ホップノード決定部１００は、次ホップノード候補５−ｉｊ（２）を選択する。このようにして、上記選択確率Ｐｉｊ（ｋ）に従って、且つ、ランダムに、１つの次ホップノード５−ｉｊを選択することができる。
【００４８】
ステップＳ２７：
次ホップノード５−ｉｊが選択されると、次ホップノード決定部１００は、その選択された次ホップノード５−ｉｊを中継ノード５−ｒとして経路ノードリスト５００に保持する。さらに、次ホップノード決定部１００は、対象ノード５−ｉを、選択された次ホップノード５−ｉｊに更新する。
【００４９】
ステップＳ２８：
次ホップ決定処理が完了すると、次ホップノード決定部１００は、更新後の対象ノード５−ｉ（選択された次ホップノード）が送信先ノード５−Ｄと一致しているか否かを調べる。つまり、次ホップノード決定部１００は、対象ノード５−ｉが送信先ノード５−Ｄまで到達したか否かを調べる。
【００５０】
対象ノード５−ｉが未だ送信先ノード５−Ｄに到達していない場合（ステップＳ２８；Ｎｏ）、処理はステップＳ１２に戻り、次ホップノード決定部１００は、新たな対象ノード５−ｉに関する次ホップ決定処理を実行する。
【００５１】
以上に説明された処理が繰り返され、次ホップノード決定部１００は、送信元ノード５−Ｓから送信先ノード５−Ｄに向かって１ホップずつランダムに中継ノード５−ｒを決定していく。最終的に、対象ノード５−ｉは送信先ノード５−Ｄに到達する（ステップＳ２８；Ｙｅｓ）。すなわち、送信元ノード５−Ｓから送信先ノード５−Ｄへの通信経路が決定される。このように、本実施形態に係る次ホップノード決定部１００は、次ホップ決定処理を繰り返すことによって、送信元ノード５−Ｓから送信先ノード５−Ｄへの通信経路を１ホップずつランダムに決定する。
【００５２】
ステップＳ２９：
通信経路が決定されると、ノード設定部２００は、決定された通信経路上の各ノード５に対して、フローまたはパケットデータを当該決定された通信経路に沿って転送するように指示する。より詳細には、ノード設定部２００は、経路ノードリスト５００に登録されている各ノード５に対して、転送テーブル設定コマンドＣＭＤを送出する。転送テーブル設定コマンドＣＭＤは、上記決定された通信経路に沿ってフロー、またはパケットデータが転送されるように転送テーブルを設定するよう指示するコマンドである。
【００５３】
決定された通信経路上の各ノード５は、制御サーバ１０から転送テーブル設定コマンドＣＭＤを受け取り、それに従って自身の転送テーブルの内容を設定する。これにより、当該フローのデータが、送信元ノード５−Ｓから送信先ノード５−Ｄまで伝達されるようになる。
【００５４】
なお、本実施形態は、集中制御によるループを除去した経路設定方法であったが、分散制御によるループを除去した経路設定方法としても実現可能である。
【００５５】
以下、本発明の主要部について説明する。図６は、本発明の情報処理装置の主要部の例を示すブロック図である。本発明の情報処理装置は、送信元から宛先へ複数の経路が存在するネットワークシステムを制御する。そして、本発明の情報処理装置は、選択部３１と、確率再設定部３２とを備える。
【００５６】
選択部３１（例えば、次ホップノード決定部１００）は、ノード間転送確率に基づいて経路を形成するノードを選択する。
【００５７】
確率再設定部３２（例えば、ループ検出部３００）は、選択したノードが経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように転送確率を再設定する。
【００５８】
また、図７は、本発明のネットワークシステムの主要部の例を示すブロック図である。本発明のネットワークシステムは、送信元から宛先へ複数の経路が存在するネットワークシステムであり、その複数の経路から所定の経路を設定する制御サーバ３３を備える。制御サーバ３３は、選択部３１と、確率再設定部３２とを備える。選択部３１および確率再設定部３２の動作は、図６に示したそれらの動作と同様である。
【００５９】
上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６０】
（付記１）送信元から宛先へ複数の経路が存在するネットワークを制御する経路選択方法において、ノード間転送確率に基づいて前記経路を形成するノードを選択し、選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定することを特徴とする経路選択方法。
【００６１】
（付記２）選択した前記ノードが前記経路で既に経由されたノードである場合に、該ノードへの転送確率を、該ノードを経由しない場合の転送確率に対して小さな値に再設定する付記１に記載の経路選択方法。
【００６２】
（付記３）０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させ、次ホップノードを確率的に選択する付記１に記載の経路選択方法。
【００６３】
（付記４）送信元から宛先へ複数の経路が存在するネットワークシステムを制御する情報処理装置であって、ノード間転送確率に基づいて前記経路を形成するノードを選択する手段と、選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する手段とを有することを特徴とする情報処理装置。
【００６４】
（付記５）選択した前記ノードが前記経路で既に経由されたノードである場合に、該ノードへの転送確率を、該ノードを経由しない場合の転送確率に対して小さな値に再設定する手段を有する付記４に記載の情報処理装置。
【００６５】
（付記６）０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させ、次ホップノードを確率的に選択する手段を有する付記４に記載の情報処理装置。
【００６６】
（付記７）送信元から宛先へ複数の経路が存在するネットワークシステムにおいて、前記複数の経路から所定の経路を設定する制御サーバを有し、前記制御サーバは、ノード間転送確率に基づいて前記経路を形成するノードを選択する手段と、選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する手段とを有することを特徴とするネットワークシステム。
【００６７】
（付記８）選択した前記ノードが前記経路で既に経由されたノードである場合に、該ノードへの転送確率を該ノードを経由しない場合の転送確率に対して小さな値に再設定する手段を有する付記７に記載のネットワークシステム。
【００６８】
（付記９）０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させ、次ホップノードを確率的に選択する手段を有する付記７に記載のネットワークシステム。
【００６９】
（付記１０）送信元から宛先へ複数の経路が存在するネットワークシステムにおいて前記複数の経路から所定の経路を設定するコンピュータに、ノード間転送確率に基づいて前記経路を形成するノードを選択する処理と、選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する処理とを実行させるための経路選択プログラム。
【００７０】
（付記１１）送信元から宛先へ複数の経路が存在するネットワークシステムを制御する情報処理装置であって、ノード間転送確率に基づいて前記経路を形成するノードを選択する選択部と、選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する確率再設定部とを有することを特徴とする情報処理装置。
【００７１】
（付記１２）選択した前記ノードが前記経路で既に経由されたノードである場合に、該ノードへの転送確率を、該ノードを経由しない場合の転送確率に対して小さな値に再設定する確率再設定部を有する付記１１に記載の情報処理装置。
【００７２】
（付記１３）０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させ、次ホップノードを確率的に選択する選択部を有する付記１１に記載の情報処理装置。
【００７３】
（付記１４）送信元から宛先へ複数の経路が存在するネットワークシステムにおいて、前記複数の経路から所定の経路を設定する制御サーバを有し、前記制御サーバは、ノード間転送確率に基づいて前記経路を形成するノードを選択する選択部と、選択した前記ノードが前記経路上で既に経由されたノードである場合に、該ノードの選択が抑制されるように前記転送確率を再設定する確率再設定部とを有することを特徴とするネットワークシステム。
【００７４】
（付記１５）選択した前記ノードが前記経路で既に経由されたノードである場合に、該ノードへの転送確率を該ノードを経由しない場合の転送確率に対して小さな値に再設定する確率再設定部を有する付記１４に記載のネットワークシステム。
【００７５】
（付記１６）０．０以上、転送確率の合計値未満の範囲内で乱数Ｘを発生させ、次ホップノードを確率的に選択する選択部を有する付記１４に記載のネットワークシステム。
【００７６】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００７７】
この出願は、２０１０年３月１７日に出願された日本特許出願２０１０−０６１１１８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００７８】
１  通信ネットワークシステム
５  ノード
５−Ｓ  送信元ノード
５−Ｄ  送信先ノード
５−ｉ  対象ノード
５−ｊ  隣接ノード
１０  制御サーバ
１００  次ホップノード決定部
２００  ノード設定部
３００  ループ検出部
４００  転送確率テーブル
５００  経路ノードリスト
ＮＥＴ  通信ネットワーク
ＲＥＱ  経路設計要求
ＣＭＤ  転送テーブル設定コマンド
【図１】
2011114627.tif 000003
【図２】
2011114627.tif 000004
【図３】
2011114627.tif 000005
【図４】
2011114627.tif 000006
【図５】
2011114627.tif 000007
【図６】
2011114627.tif 000008
【図７】
2011114627.tif 000009
【国際調査報告】
2011114627.tif 000010
2011114627.tif 000011
2011114627.tif 000012
2011114627.tif 000013