(57)【要約】【課題】ＳＬＡを保証するトラフィックの通信経路を効率的に選択することができる経路選択装置を提供する。【解決手段】次ホップノード選択手段９１は、トラフィックの送信元ノードを起点とし、１ホップずつ、複数の次ホップノード候補の中から確率的に次ホップノードを選択する。性能判定手段９２は、１つの次ホップノードが選択されたときに、送信元ノードからその次ホップノードまでの経路における通信性能が、サービスレベルアグリーメントで規定された基準を満たしているか否かを判定する。次ホップノード選択手段９１は、通信性能が基準を満たしていると判定された場合に、さらに次の次ホップノードを選択する。また、通信性能が基準を満たしていないと判定された場合に、次ホップノードの選択を、送信元ノードに対する次ホップノードの選択からやり直す。【選択図】図６
2013197734.tif 000002
【特許請求の範囲】
【請求項１】
トラフィックの送信元ノードを起点とし、１ホップずつ、複数の次ホップノード候補の中から確率的に次ホップノードを選択する次ホップノード選択手段と、
１つの次ホップノードが選択されたときに、前記送信元ノードから当該次ホップノードまでの経路における通信性能が、サービスレベルアグリーメントで規定された基準を満たしているか否かを判定する性能判定手段とを備え、
次ホップノード選択手段は、
前記通信性能が前記基準を満たしていると判定された場合に、さらに次の次ホップノードを選択し、
前記通信性能が前記基準を満たしていないと判定された場合に、次ホップノードの選択を、前記送信元ノードに対する次ホップノードの選択からやり直す
ことを特徴とする経路選択装置。
【請求項２】
性能判定手段は、
１つの次ホップノードが選択されたときに、送信元ノードから当該次ホップノードまでの経路における通信性能として、当該経路における通信遅延を算出し、当該通信遅延が、通信遅延に関する基準を満たしているか否かを判定する
請求項１に記載の経路選択装置。
【請求項３】
性能判定手段は、
１つの次ホップノードが選択されたときに、送信元ノードから当該次ホップノードまでの経路における通信性能として、当該経路における１フロー当たりの使用可能帯域を算出し、当該１フロー当たりの使用可能帯域が、１フロー当たりの使用可能帯域に関する基準を満たしているか否かを判定する
請求項１に記載の経路選択装置。
【請求項４】
性能判定手段は、
１つの次ホップノードが選択されたときに、送信元ノードから当該次ホップノードまでの経路における通信性能として、当該経路におけるトラフィックのロス率を算出し、当該ロス率が、ロス率に関する基準を満たしているか否かを判定する
請求項１に記載の経路選択装置。
【請求項５】
次ホップノード選択手段は、
送信元ノードに対する次ホップノードの選択から、次ホップノードの選択をやり直した回数が閾値を超えた場合、通信性能が、サービスレベルアグリーメントで規定された基準を満たしていなくても、さらに次の次ホップノードを選択する
請求項１から請求項４のうちのいずれか１項に記載の経路選択装置。
【請求項６】
トラフィックの送信元ノードを起点とし、１ホップずつ、複数の次ホップノード候補の中から確率的に次ホップノードを選択し、
１つの次ホップノードを選択したときに、前記送信元ノードから当該次ホップノードまでの経路における通信性能が、サービスレベルアグリーメントで規定された基準を満たしているか否かを判定し、
前記通信性能が前記基準を満たしていると判定した場合に、さらに次の次ホップノードを選択し、
前記通信性能が前記基準を満たしていないと判定した場合に、次ホップノードの選択を、前記送信元ノードに対する次ホップノードの選択からやり直す
ことを特徴とする経路選択方法。
【請求項７】
１つの次ホップノードが選択されたときに、送信元ノードから当該次ホップノードまでの経路における通信性能として、当該経路における通信遅延を算出し、当該通信遅延が、通信遅延に関する基準を満たしているか否かを判定する
請求項６に記載の経路選択方法。
【請求項８】
１つの次ホップノードが選択されたときに、送信元ノードから当該次ホップノードまでの経路における通信性能として、当該経路における１フロー当たりの使用可能帯域を算出し、当該１フロー当たりの使用可能帯域が、１フロー当たりの使用可能帯域に関する基準を満たしているか否かを判定する
請求項６に記載の経路選択方法。
【請求項９】
１つの次ホップノードが選択されたときに、送信元ノードから当該次ホップノードまでの経路における通信性能として、当該経路におけるトラフィックのロス率を算出し、当該ロス率が、ロス率に関する基準を満たしているか否かを判定する
請求項６に記載の経路選択方法。
【請求項１０】
コンピュータに、
トラフィックの送信元ノードを起点とし、１ホップずつ、複数の次ホップノード候補の中から確率的に次ホップノードを選択する次ホップノード選択処理、および、
１つの次ホップノードを選択したときに、前記送信元ノードから当該次ホップノードまでの経路における通信性能が、サービスレベルアグリーメントで規定された基準を満たしているか否かを判定する性能判定処理を実行させ、
前記通信性能が前記基準を満たしていると判定した場合に、前記次ホップノード選択処理で、さらに次の次ホップノードを選択させ、
前記通信性能が前記基準を満たしていないと判定した場合に、前記次ホップノード選択処理で、次ホップノードの選択を、前記送信元ノードに対する次ホップノードの選択からやり直させる
ための経路選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク内のトラフィックの通信経路を選択する経路選択装置、経路選択方法および経路選択プログラムに関する。
【背景技術】
【０００２】
複数のノードを含む通信ネットワークが管理サーバによって集中的に管理される通信ネットワークシステムが知られている。管理サーバは、あるトラフィックに関する経路設定要求をノードから受け取ると、通信ネットワーク内におけるそのトラフィックの通信経路を決定する。このようにトラフィックの通信経路を決定する管理サーバを、以下、「制御サーバ」と記す。
【０００３】
制御サーバと通信ネットワーク内のノードとのインタフェース方式として、オープンフロー（ＯｐｅｎＦｌｏｗ）という方式が提案されている（非特許文献１参照）。オープンフローは、通信をフロー単位で識別し、フロー単位で経路制御、障害回復、負荷分散および最適化を行う技術である。転送ノードとして機能するオープンフロースイッチは、オープンフローコントローラとの通信用のセキュアチャネルを備える。そして、オープンフロースイッチは、オープンフローコントローラから適宜、追加されるか、または書き換えられるフローテーブルに従って動作する。フローテーブルには、フロー毎に、パケットヘッダと照合されるルールと、処理内容を定義したアクションと、フロー統計情報との組が定義される。
【０００４】
例えば、オープンフロースイッチは、パケットを受信すると、そのパケットのヘッダ情報に適合するルール（FlowKey ）を持つエントリをフローテーブルから検索する。そのパケットに適合するエントリの検索に成功した場合、オープンフロースイッチは、そのエントリのアクションフィールドに記述された処理を実行する。例えば、指定されたノードにそのパケットを転送する。
【０００５】
一方、受信したパケットに適合するエントリの検索に失敗した場合、オープンフロースイッチは、セキュアチャネルを介して、オープンフローコントローラに対してそのパケットを転送し、そのパケットの送信元および送信先に応じたパケットの通信経路の決定を依頼する。そして、そのオープンフロースイッチは、オープンフローコントローラから、そのパケットに対して決定されたフローエントリを受け取り、フローテーブルを更新する。この結果、オープンフロースイッチは、そのパケットに対する処理を決定することができる。
【０００６】
また、非特許文献２には、ある送信元ノードからある送信先ノードへの最短経路を決定するアルゴリズムとして、ダイクストラ法（Dijkstra’s Algorithm）が記載されている。しかし、その送信元ノードと送信先ノードとの間で複数のトラフィックの通信が行われる場合、単純にダイクストラ法を用いるだけでは、それらの複数のトラフィックに対して同じ通信経路（最短経路）が設定されてしまう。すると、その通信経路にかかる負荷が増大し、通信効率が低下する。
【０００７】
負荷を分散させるためには、同じ送信元ノードと送信先ノードとの間の異なるトラフィックに対して、異なる通信経路を設定することが好ましい。そのためには、一組の送信元ノードと送信先ノードの組に対して、最短経路だけでなく、他の通信経路も抽出することが考えられる。送信元ノードから送信先ノードへの複数の通信経路を定める技術が非特許文献３に記載されている。
【０００８】
非特許文献３には、ｋ番目に短い通信経路までをダイクストラ法によって抽出し、トラフィックの経路をｋ番目に短い通信経路までの中からランダムに割り当てるk-shortest path が記載されている。これにより、送信元ノードから送信先ノードへの複数の通信経路を定めることができる。
【０００９】
しかし、k-shortest path では、ダイクストラ法によって通信経路を抽出するため、計算量が膨大になる。
【００１０】
計算量を抑えつつ、負荷を分散させ、ある送信元ノードから送信先ノードへの通信経路を求める方法として、非特許文献４に記載の方法がある。非特許文献４には、通信経路中のノードがある送信先への転送確率テーブルを生成し、その転送確率テーブルを用いて、確率に基づいてパケットを転送させる方法が記載されている。転送確率は、送信先ノードに送られるトラフィックが個々のリンクを通過する確率である。転送ノードは、送信先ノード毎に、各リンクに対して定められる。転送確率は、通信経路中のリンクコストと、リンクコストから算出される重み行列、および設定パラメータγに基づいて算出される。転送確率テーブルは、送信先ノードに対する、隣接ノードとその隣接ノードへの転送確率を保持する。ノードは、送信先ノードのアドレスが決定されると、隣接ノードに確率的にパケットを送信する。
【００１１】
非特許文献４に記載の方法は、確率的なパケット転送の方法である。非特許文献５には、この方法をフロー転送に拡張した方法が記載されている。
【００１２】
転送確率テーブルの構築は容易である。従って、非特許文献４に記載の方法では、計算量を抑えることができる。
【００１３】
また、一般のネットワークシステムにおいて、ＳＬＡ（Service Level Agreement ）とは、サービス提供者とサービスを受ける者との間での、遅延、帯域、ロス率等の性能に関する取り決めである。サービス提供者がＳＬＡを保証する方法として、効率のよい経路制御を行うことが挙げられる。
【００１４】
また、特許文献１には、ネットワークが品質変更指示に従って経路変更等を実行することで、携帯電話装置間の音声品質を変更することが記載されている。
【００１５】
特許文献２には、各ノードにおける宛先ノードへの配送確率の大小に基づいて、データを転送する際の次ホップノードを決定することが記載されている。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２００７−１８９４４４号公報（段落００３２）
【特許文献２】再公表特許  国際公開番号ＷＯ２００９／０７８４２７（段落００２１）
【非特許文献】
【００１７】
【非特許文献１】Nick McKeown, Tom Anderson, Hari Balakrishnan, Guru Parulkar, Larry Peterson, Jennifer Rexford, Scott Shenker, Jonathan Turner, “OpenFlow: Enabling Innovation in Campus Networks”, ２００８年３月１４日、［２０１２年２月１２日検索］、インターネット<URL: http://www.openflowswitch.org/documents/openflow-wp-latest.pdf>
【非特許文献２】Edsger W. Dijkstra, “A Not on Two Problems in Connexion with Graphs”, Numerische Mathematik, vol1, pp.269-271, １９５９年
【非特許文献３】David Eppstein, “Finding the k Shortest Paths”, March 31, 1997
【非特許文献４】Yudai Honma, Hideyuki Shimonishi, “A New Multi-path Routing Methodology Based on Logit Type Assignment”, In FutureNet II, ２００９年
【非特許文献５】篠原悠介、千葉靖信、下西英之、本間裕大、会田雅樹、“データセンタネットワークにおける効率的マルチパスルーティングとそのＯｐｅｎＦｌｏｗネットワークへの適用”、信学技法、社団法人電子情報通信学会、vol.109, No.448, NS2009-164, pp.13-18
【発明の概要】
【発明が解決しようとする課題】
【００１８】
転送確率テーブルを構築し、転送確率テーブルを用いて確率的にトラフィックを転送するアルゴリズムでは、低い確率であるが、通信性能が悪い通信経路で転送されるトラフィックが生じる。そのため、全てのトラフィック関して常にＳＬＡの性能要件を達成することは困難である。
【００１９】
この問題を解決する方法として、考え得る全ての通信経路に対してＳＬＡの性能要件を達成できるか否かを確認することが考えられる。具体的には、各通信経路にダミートラフィックを配送させ、通信経路の遅延、帯域、ロス率等の性能を計測し、ＳＬＡの性能要件を達成しているか否かを確認する。この場合、経路の通信性能は時々刻々と変化するため、定期的に性能測定を行う必要がある。
【００２０】
しかし、考え得る全ての通信経路に対してダミートラフィックを配送させると、ネットワーク資源を多大に消費してしまう。
【００２１】
そこで、本発明は、ＳＬＡを保証するトラフィックの通信経路を効率的に選択することができる経路選択装置、経路選択方法および経路選択プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２２】
本発明による経路選択装置は、トラフィックの送信元ノードを起点とし、１ホップずつ、複数の次ホップノード候補の中から確率的に次ホップノードを選択する次ホップノード選択手段と、１つの次ホップノードが選択されたときに、送信元ノードから当該次ホップノードまでの経路における通信性能が、サービスレベルアグリーメントで規定された基準を満たしているか否かを判定する性能判定手段とを備え、次ホップノード選択手段が、その通信性能が基準を満たしていると判定された場合に、さらに次の次ホップノードを選択し、その通信性能が基準を満たしていないと判定された場合に、次ホップノードの選択を、送信元ノードに対する次ホップノードの選択からやり直すことを特徴とする。
【００２３】
また、本発明による経路選択方法は、トラフィックの送信元ノードを起点とし、１ホップずつ、複数の次ホップノード候補の中から確率的に次ホップノードを選択し、１つの次ホップノードを選択したときに、送信元ノードから当該次ホップノードまでの経路における通信性能が、サービスレベルアグリーメントで規定された基準を満たしているか否かを判定し、その通信性能が基準を満たしていると判定した場合に、さらに次の次ホップノードを選択し、その通信性能が基準を満たしていないと判定した場合に、次ホップノードの選択を、送信元ノードに対する次ホップノードの選択からやり直すことを特徴とする。
【００２４】
また、本発明による経路選択プログラムは、コンピュータに、トラフィックの送信元ノードを起点とし、１ホップずつ、複数の次ホップノード候補の中から確率的に次ホップノードを選択する次ホップノード選択処理、および、１つの次ホップノードを選択したときに、送信元ノードから当該次ホップノードまでの経路における通信性能が、サービスレベルアグリーメントで規定された基準を満たしているか否かを判定する性能判定処理を実行させ、その通信性能が基準を満たしていると判定した場合に、次ホップノード選択処理で、さらに次の次ホップノードを選択させ、その通信性能が基準を満たしていないと判定した場合に、次ホップノード選択処理で、次ホップノードの選択を、送信元ノードに対する次ホップノードの選択からやり直させることを特徴とする。
【発明の効果】
【００２５】
本発明によれば、ＳＬＡを保証するトラフィックの通信経路を効率的に選択できる。
【図面の簡単な説明】
【００２６】
【図１】本発明の経路選択装置が適用される通信ネットワークの例を示す概念図である。
【図２】送信元ノードから送信先ノードへの複数の通信経路を示す概念図である。
【図３】転送確率テーブルの例を示す模式図である。
【図４】制御サーバの構成例を示すブロック図である。
【図５】本発明の処理経過の例を示すフローチャートである。
【図６】本発明の最小構成の例を示すブロック図である。
【発明を実施するための形態】
【００２７】
以下、本発明の実施形態を図面を参照して説明する。
図１は、本発明の経路選択装置１０が適用される通信ネットワークの例を示す概念図である。通信ネットワーク５０は、複数のノード５を含む。本実施形態では、通信ネットワーク５０がｎ個のノードを含んでいるものとする。ただし、ｎは２以上の整数である。以下、個々のノード５を区別するために、例えば、ノード５−ｉ等のように記し、“−”以降の符号で個々のノードを区別する場合がある。
【００２８】
本発明の経路選択装置１０は、各ノード５に接続される。そして、経路選択装置１０は、発生したトラフィックに関する経路設定要求をネットワーク５０から受信すると、そのトラフィックの通信経路を選択し、通信経路上の各ノードに、その通信経路に沿ってトラフィックを転送するように指示する。各ノード５は、その指示を受信すると、その指示に従って自身の設定を行う。
【００２９】
例えば、各ノード５には「転送テーブル」が設けられる。転送テーブルは、トラフィックの転送先を記述したテーブルである。転送テーブルとして、例えば、トラフィックの識別情報とそのトラフィックの転送先との対応関係を記述したテーブルが考えられる。各ノード５は、このような転送テーブルを参照することによって、受信したトラフィックを指定された転送先に転送することができる。この場合、経路選択装置１０は、決定した通信経路に沿ってトラフィックが転送されるように、各ノード５に対して転送テーブルを設定するように指示する。各ノード５は、経路選択装置１０からの指示に従って、自身の転送テーブルの内容を設定する。
【００３０】
従って、経路選択装置１０は制御サーバであると言うことができ、以下、経路選択装置１０を制御サーバ１０と記す。
【００３１】
また、上記のような処理を実現するために、本発明において、オープンフローが適用されてもよい。すなわち、制御サーバ１０は、オープンフローコントローラであってもよい。そして、各ノードは、トラフィックとなるパケットまたはフレームのヘッダ情報と照合されるルールと、そのルールに対応するアクションとを記述したテーブルを転送テーブルとして保持してもよい。
【００３２】
図２は、送信元ノードから送信先ノードへの複数の通信経路を示す概念図である。図２において、送信元ノードを符号“５−Ｓ”で示す。また、送信先ノードを符号“５−Ｄ”で示す。また、送信元ノードから送信先ノードまでの中継ノードを符号“５−ｒ”で示す。図２に示すように、多くの場合、送信元ノード５−Ｓから送信先ノード５−Ｄまでの経路として複数の通信経路が存在する。各通信経路は、いくつかの中継ノード５−ｒを含む。通信経路が異なれば、通信経路上の中継ノード５−ｒの組み合わせも異なる。
【００３３】
制御サーバ１０は、ノード５毎に予め定められた転送確率テーブルを保持する。転送確率テーブルは、次ホップノードを決定する処理の対象となるノードから、個々の次ホップノード候補への転送確率を、トラフィックの送信先ノード毎に記述したテーブルである。以下、次ホップノードを決定する処理の対象となるノードを、対象ノードと記す。個々のノード５がそれぞれ対象ノードとなるので、転送確率テーブルは、ノード５毎に生成される。従って、転送確率テーブルとノード５とは一対一に対応する。
【００３４】
図３は、転送確率テーブルの例を示す模式図である。ここで、通信ネットワーク５０内のｎ個のノードをそれぞれノード５−１〜ノード５−ｎと記す。また、通信ネットワーク５０内の任意のノードをノード５−ｉと記す。ｉ＝１〜ｎである。
【００３５】
図３では、対象ノード５−ｉに対応する転送確率テーブルを示している。また、個々のノード５は、それぞれトラフィックの送信先ノードにもなる。任意の送信先ノードをノード５−ｊと記す。ただし、対象ノード５−ｉの次ホップノードを決定するときに、対象ノード５−ｉが送信先ノードに該当することはない。従って、ｊは、１〜ｎのうち、ｉ以外の整数である。
【００３６】
送信先ノード５−ｊに向けてトラフィックを順次、転送していくときに、対象ノード５−ｉがそのトラフィックを転送する次のノードが次ホップノードである。そして、対象ノード５−ｉにリンクを介して接続された各ノードが次ホップノードの候補になる。以下、最終的な送信先が送信先ノード５−ｊである場合、対象ノード５−ｉの次ホップノードを、符号“ｉ”，“ｊ”を用いて、“次ホップノード５−ｉｊ（または、単にノード５−ｉｊ）”と記す。すなわち、送信先ノード５−ｊに向けて順次転送されるトラフィックは、対象ノード５ｉの次にノード５−ｉｊを経由する。
【００３７】
また、ある対象ノード５−ｉに関して、次ホップノード候補は複数存在し得る。次ホップノード候補の数がｍ個（ｍは自然数）である場合、対象ノード５−ｉの次ホップノード候補を符号“５−ｉｊ（１）”〜“５−ｉｊ（ｍ）”で表す。一般化すると、対象ノード５−ｉには、次ホップノード候補５−ｉｊ（ｋ）が存在する。ただし、ｋ＝１〜ｍである。なお、次ホップノード候補５−ｉｊ（ｋ）は、対象ノード５−ｉから見て、送信先ノード５−ｊから遠ざかる側のノードであってもよい。
【００３８】
図３に示すように、転送確率テーブルには、トラフィックの送信先ノード５−ｊ毎に、対象ノード５−ｉの次ホップノード候補５−ｉｊ（ｋ）が記述されている。ｊ＝１〜ｎ（ただし、ｊ≠ｉ）である。さらに、転送確率テーブルには、各次ホップノード候補５−ｉｊ（ｋ）に対して規定される転送確率も記述される。対象ノード５−ｉから次ホップノード候補５−ｉｊ（ｋ）への転送確率を、Ｐｉｊ（ｋ）と記す。
【００３９】
図４は、制御サーバ１０の構成例を示すブロック図である。制御サーバ１０は、次ホップノード決定部１００と、ノード設定部２００と、経路ノードリスト記憶部３００と、転送確率テーブル記憶部４００と、通信品質管理部５００と、リンク上フロー数管理部６００とを備える。
【００４０】
転送確率テーブル記憶部４００は、ノード５毎に予め生成された各転送確率テーブルを記憶する記憶装置である。なお、転送確率テーブルは、リンクコストおよびトポロジ情報を含むネットワーク情報に基づいて、予め定めておけばよい。
【００４１】
経路ノードリスト記憶部３００は、経路ノードリストを記憶する記憶装置である。経路ノードリストは、送信元ノードを起点として次ホップノードとして決定されたノードを順次記述した情報である。また、経路ノードリスト記憶部３００は、経路ノードリストに記述されたノードを結ぶリンクに関して、そのリンクを通過するフロー数も記憶する。
【００４２】
次ホップノード決定部１００は、通信ネットワーク５０内の各ノード５から対象ノードを選択し、その対象ノードに対応する転送確率テーブルを転送確率テーブル記憶部４００から読み込む。そして、次ホップノード決定部１００は、転送確率テーブルを用いて、対象ノードの次ホップノード候補から次ホップノードを選択し、経路ノードリストにその次ホップノードを追加書き込みする。また、次ホップノード決定部１００は、選択した次ホップノードを対象ノードとして、同様の処理を繰り返す。
【００４３】
通信品質管理部５００は、経路ノードリストが表す通信経路が、ＳＬＡで規定された性能要件を満たすか否かを判定する。以下、ＳＬＡで規定された性能要件を符号“ＳＰＱ”で表す。性能要件ＳＰＱは、外部から通信品質管理部５００に入力される。また、通信品質管理部５００には、通信経路の性能を算出するための情報（例えば、リンク利用率等）が入力される。
【００４４】
ノード設定部２００は、通信経路が確定したときに、その通信経路上の各ノードに転送テーブル設定コマンドを送信する。ノード設定部２００は、個々のノード毎に次ホップノードを転送テーブル設定コマンドで指定する。
【００４５】
リンクフロー管理部６００は、各リンクを通過するフロー数を管理する。具体的には、ノード設定部２００が各ノードに対して通信経路に応じた次ホップノードを転送テーブルに設定させるときに、リンクフロー管理部６００は、経路ノードリスト記憶部３００に記憶された各リンクのフロー数のうち、その通信経路上のリンクのフロー数をインクリメントする。すなわち、フロー数の値を１増加させる。また、任意のフローの削除を指示するフロー削除情報が外部から入力されると、リンクフロー管理部６００は、経路ノードリスト記憶部３００に記憶された各リンクのフロー数のうち、そのフローが通過している各リンクのフロー数をデクリメントする。すなわち、フロー数の値を１減少させる。
【００４６】
次ホップノード決定部１００、ノード設定部２００、通信品質管理部５００およびリンク上フロー数管理部６００は、例えば、経路選択プログラムに従って動作するコンピュータのＣＰＵによって実現される。この場合、ＣＰＵが経路選択プログラムを読み込み、そのプログラムに従って、上記の各部として動作すればよい。また、上記の各部が別々のハードウェアによって実現されてもよい。
【００４７】
次に、動作について説明する。
図５は、本発明の処理経過の例を示すフローチャートである。通信ネットワーク５０にトラフィックが発生した場合、次ホップノード決定部１００は、通信ネットワーク５０から、そのトラフィックの経路設定要求を受信する（ステップＳ１０）。例えば、次ホップノード決定部１００は、そのトラフィックを受信した中継ノードから経路設定要求を受信する。経路設定要求は、そのトラフィックの送信元ノード５−Ｓと送信先ノード５−Ｄを示している。以下、送信先ノード５−Ｄが、“送信先ノード５−ｊ”であるものとして説明する。
【００４８】
ステップＳ１０の後、次ホップノード決定部１００は、経路選択試行回数を０に初期化する。経路選択試行回数については後述する。
【００４９】
続いて、次ホップノード決定部１００は、経路設定要求を参照して、送信元ノード５−Ｓと送信先ノード５−ｊを認識する。そして、次ホップノード決定部１００は、対象ノード５−ｉとして送信元ノード５−Ｓを選択する（ステップＳ１１）。
【００５０】
ステップＳ１１の後、次ホップノード決定部１００は、対象ノード５−ｉに対応する転送確率テーブルから、送信先ノード５−ｊについて定められた各次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（ｍ）と、それらの次ホップノード候補に定められた各転送確率Ｐｉｊ（１）〜Ｐｉｊ（ｍ）を取得する（ステップＳ１２）。これらの転送確率の合計値は、必ずしも１．０にならなくてもよい。
【００５１】
ステップＳ１２の後、次ホップノード決定部１００は、転送確率Ｐｉｊ（１）〜Ｐｉｊ（ｍ）に基づいて、次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（ｍ）の中から、次ホップノードを確率的に選択する（ステップＳ１３）。
【００５２】
次ホップノード決定部１００は、例えば、乱数および転送確率Ｐｉｊ（１）〜Ｐｉｊ（ｍ）を利用して、次ホップノードを選択すればよい。例えば、次ホップノード候補の個数ｍが３であり、次ホップノード候補５−ｉｊ（１）〜５−ｉｊ（３）の転送確率Ｐｉｊ（１）〜Ｐｉｊ（３）がそれぞれ０．２，０．３，０．６である場合を例にして説明する。次ホップノード決定部１００は、それぞれの次ホップノード候補に対して、次ホップノード候補の転送確率に応じた数値範囲を規定する。例えば、次ホップノード決定部１００は、次ホップノード候補５−ｉｊ（１）に対して、０．０以上０．２未満の範囲を対応づける。また、次ホップノード候補５−ｉｊ（２）に対して、０．２以上０．５未満の範囲を対応付ける。また、次ホップノード候補５−ｉｊ（３）に対して、０．５以上１．１未満の範囲を対応付ける。そして、次ホップノード決定部１００は、０．０以上、転送確率Ｐｉｊ（１）〜Ｐｉｊ（３）の合計値未満の範囲内で乱数Ｘを発生させる。なお、前述のように、転送確率の合計値は必ずしも１．０とは限らない。そのため、０．０から、転送確率の合計値未満の範囲で乱数Ｘを発生させる。そして、次ホップノード決定部１００は、乱数Ｘを含む数値範囲に対応付けられた次ホップノード候補を、次ホップノードとして選択する。例えば、乱数Ｘが０．３である場合、次ホップノード候補５−ｉｊ（２）を選択する。このようにして、次ホップノード決定部１００は、転送確率の大きさに基づいて、確率的に次ホップノード５−ｉｊを選択する。
【００５３】
次ホップノードの選択後、通信品質管理部５００は、送信元ノード５−Ｓから次ホップノード５−ｉｊまでの経路（以下、符号“Ｒ”で示す。）における通信品質が、ＳＬＡで規定された性能要件ＳＰＱを満たすか否かを判定する（ステップＳ１４）。なお、経路Ｒは、経路ノードリスト記憶部３００に記憶された経路ノードリストに、ステップＳ１３で選択した次ホップノードを追加した経路である。ただし、ステップＳ１１の後、最初にステップＳ１４を実行する際には、経路ノードリストは記憶されていない。この場合、送信元ノード５−Ｓ（ステップＳ１１の後、最初にステップＳ１４を実行する際の対象ノード５−ｉ），次ホップノード５−ｉｊというノード順の経路を、経路Ｒとする。
【００５４】
性能要件ＳＰＱと比較する通信品質には、遅延（通信遅延）、１フロー当たりの使用可能帯域、ロス率がある。
【００５５】
以下、経路Ｒの遅延に着目して、性能要件ＳＰＱを満たしているか否かを判定する処理について説明する。通信品質管理部５００は、経路Ｒの遅延値（以下、ＥＤと記す。）を推定し、遅延値ＥＤと、ＳＬＡで規定された遅延に関する要求値とを比較すればよい。本実施形態では、経路Ｒ上のリンクにおいてＭ／Ｍ／１モデルが成立するものとする。この場合、経路Ｒの遅延値ＥＤは、以下の式（１）の計算で算出できる。
【００５６】
【数１】
2013197734.tif 000003
【００５７】
なお、ρｉｊは、対象ノード５−ｉから次ホップノード５−ｉｊへのリンクのリンク利用率である。
【００５８】
また、μｉｊは、対象ノード５−ｉから次ホップノード５−ｉｊへのリンクのリンク速度である。リンク速度は、リンクで１秒間に転送できるトラフィックの量であり、リンク速度の単位はｂｐｓ（Bit Per Second）である。
【００５９】
Ｎｉｊは、対象ノード５−ｉから次ホップノード５−ｉｊへのリンクのバッファ容量である。リンクのバッファ容量は、トラフィックの量に対してリンク速度が遅い場合に、一時的にトラフィックを保存するバッファの容量である。
【００６０】
通信ネットワーク内の各リンクのリンク利用率、リンク速度およびバッファ容量は、予め通信品質管理部５００に入力される。従って、ρｉｊ，μｉｊ，Ｎｉｊは、既知の値である。
【００６１】
通信品質管理部５００は、式（１）によって、経路Ｒの遅延値ＥＤを算出し、ＥＤと、ＳＬＡで規定された遅延に関する要求値とを比較する。ＥＤが遅延に関する要求値以下であれば、通信品質管理部５００は、経路Ｒの遅延が性能要件ＳＰＱを満たしていると判定する。一方、ＥＤが遅延に関する要求値を超えていれば、通信品質管理部５００は、経路Ｒの遅延が性能要件ＳＰＱを満たしていないと判定する。
【００６２】
式（１）において、
【数２】
2013197734.tif 000004
は、経路Ｒにおける１つのノード５−ｉから、そのノード５−ｉについて選択された次ホップノード５−ｉｊまでのリンクにおける遅延である。従って、式（１）の計算を行うということは、経路Ｒ内のリンク毎に遅延を算出し、各リンクの遅延の総和を計算するということである。各リンクの遅延の総和が、経路Ｒの遅延である。
【００６３】
遅延に関する判定は、他の方法で行ってもよい。例えば、ＳＬＡで、経路内に含まれるノード数の最大値（以下、最大経路ノード数と記す。）が規定されているとする。通信品質管理部５００は、経路Ｒに含まれるノード数をカウントし、そのノード数が最大経路ノード数以下であれば、経路Ｒの遅延が性能要件ＳＰＱを満たしていると判定する。一方、経路Ｒに含まれるノード数が最大経路ノード数を超えていれば、通信品質管理部５００は、経路Ｒの遅延が性能要件ＳＰＱを満たしていないと判定する。
【００６４】
次に、経路Ｒにおいて１フロー当たりの使用可能帯域に着目して、性能要件ＳＰＱを満たしているか否かを判定する処理について説明する。通信品質管理部５００は、経路Ｒにおいて１フロー当たりの使用可能帯域（以下、ＥＢと記す。）を推定し、ＥＢと、ＳＬＡで規定された、１フロー当たりの使用可能帯域に関する要求値とを比較すればよい。
【００６５】
通信品質管理部５００は、経路Ｒ上のリンク毎に、リンクの帯域を、そのリンクを通過するフローの数で除算し、リンク毎に計算した除算結果の最小値をＥＢとする。なお、通信ネットワーク内の各リンクの帯域は、予め通信品質管理部５００に入力される。従って、経路Ｒ上の各リンクの帯域は、既知の値である。また、リンクを通過するフローの数は、リンク上フロー数管理部６００によって更新され、最新の値が経路ノードリスト記憶部３００に記憶されている。通信品質管理部５００は、リンクを通過するフローの数を、経路ノードリスト記憶部３００から読み込めばよい。
【００６６】
ＥＢが、１フロー当たりの使用可能帯域に関する要求値以上であれば、通信品質管理部５００は、１フロー当たりの使用可能帯域が性能要件ＳＰＱを満たしていると判定する。一方、ＥＢがその要求値未満であれば、通信品質管理部５００は、１フロー当たりの使用可能帯域が性能要件ＳＰＱを満たしていないと判定する。
【００６７】
次に、経路Ｒにおけるトラフィックのロス率に着目して、性能要件ＳＰＱを満たしているか否かを判定する処理について説明する。通信品質管理部５００は、経路Ｒにおけるロス率（以下、ＥＰと記す。）を推定し、ロス率ＥＰと、ＳＬＡで規定されたロス率に関する要求値とを比較すればよい。前述のように、経路Ｒ上のリンクにおいてＭ／Ｍ／１モデルが成立するものとする。この場合、経路Ｒにおけるトラフィックのロス率ＥＰは、以下の式（２）の計算で算出できる。
【００６８】
【数３】
2013197734.tif 000005
【００６９】
ρｉｊおよびＮｉｊについては既に説明しているので、ここでは説明を省略する。
【００７０】
通信品質管理部５００は、式（２）によって、経路Ｒにおけるロス率ＥＰを算出し、ＥＰと、ＬＡで規定されたロス率に関する要求値とを比較する。ＥＰがロス率に関する要求値以下であれば、通信品質管理部５００は、経路Ｒにおけるロス率が性能要件ＳＰＱを満たしていると判定する。一方、Ｐがロス率に関する要求値を超えていれば、通信品質管理部５００は、経路Ｒにおけるロス率が性能要件ＳＰＱを満たしていないと判定する。
【００７１】
式（２）において、
【数４】
2013197734.tif 000006
は、経路Ｒにおける１つのノード５−ｉから、そのノード５−ｉについて選択された次ホップノード５−ｉｊまでのリンクにおけるロス率である。従って、式（２）の計算は、経路Ｒ内のリンク毎に、ロス率を推定し、１からそのロス率を減じる計算を行い、リンク毎に算出したその値（１からロス率を減じた値）の積を計算し、１からその積を減じるということである。
【００７２】
通信品質管理部５００は、例えば、遅延、１フロー当たりの使用可能帯域、およびロス率の一部について、性能要件を満たしているか否かを判定してもよい。例えば、遅延に着目して、遅延が性能要件を満たしていれば、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていると判定し、遅延が性能要件を満たしていなければ、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていないと判定してもよい。また、例えば、通信品質管理部５００は、１フロー当たりの使用可能帯域に着目して、１フロー当たりの使用可能帯域が性能要件を満たしていれば、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていると判定し、１フロー当たりの使用可能帯域が性能要件を満たしていなければ、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていないと判定してもよい。また、例えば、通信品質管理部５００は、ロス率に着目して、ロス率が性能要件を満たしていれば、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていると判定し、ロス率が性能要件を満たしていなければ、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていないと判定してもよい。
【００７３】
また、通信品質管理部５００は、遅延と、１フロー当たりの使用可能帯域に着目してステップＳ１４の判定を行ってもよい。また、通信品質管理部５００は、１フロー当たりの使用可能帯域と、ロス率に着目してステップＳ１４の判定を行ってもよい。また、通信品質管理部５００は、遅延とロス率に着目してステップＳ１４の判定を行ってもよい。
【００７４】
また、通信品質管理部５００は、例えば、遅延、１フロー当たりの使用可能帯域、およびロス率がそれぞれ性能要件を満たしている場合に、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていると判定し、いずれか１つが性能要件を満たしていない場合、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていないと判定してもよい。
【００７５】
経路Ｒにおける通信品質が性能要件ＳＰＱを満たしている場合（ステップＳ１４におけるＹｅｓ）、次ホップノード決定部１００は、選択した次ホップノードを経路ノードリストに追加する（ステップＳ１５）。このとき、経路ノードリストが示す経路の最後のノードとして、次ホップノードを追加する。このことは、送信元ノード５−Ｓを起点として探索している経路が延びたことを意味する。なお、ステップＳ１１の後、最初にステップＳ１５を実行する場合には、経路ノードリストとして、送信元ノード５−Ｓ，次ホップノード５−ｉｊというノード順の経路を経路ノードリスト記憶部３００に記憶させればよい。
【００７６】
さらに、ステップＳ１５において、次ホップノード決定部１００は、ステップＳ１３で選択した次ホップノード５−ｉｊを、新たに対象ノードとして定める。すなわち、対象ノードを、ステップＳ１３で選択した次ホップノード５−ｉｊで更新する。
【００７７】
また、経路Ｒにおける通信品質が性能要件ＳＰＱを満たしていない場合（ステップＳ１４におけるＮｏ）、次ホップノード決定部１００は、経路選択試行回数が、試行回数閾値を超えているか否かを判定する（ステップＳ１６）。
【００７８】
経路選択試行回数とは、送信元ノードを起点として経路探索をやり直した回数である。また、試行回数閾値とは、送信元ノードを起点として経路探索をやり直す回数に上限を設定するために予め定められた閾値である。
【００７９】
経路選択試行回数が試行回数閾値を超えていれば（ステップＳ１６におけるＹｅｓ）、ステップＳ１５に移行し、経路探索を継続する。
【００８０】
一方、経路選択試行回数が試行回数閾値以下であれば（ステップＳ１６におけるＮｏ）、次ホップノード決定部１００は、経路選択試行回数を１インクリメントする。さらに、次ホップノード決定部１００は、経路ノードリスト記憶部３００に記憶されている経路ノードリストを消去する（ステップＳ１７）。すなわち、次ホップノード決定部１００は、送信元ノードを起点とする探索中の経路を消去する。ステップＳ１７の後、ステップＳ１１以降の処理を繰り返す。ステップＳ１７で経路ノードリストを消去し、ステップＳ１１以降の処理を繰り返すということは、送信元ノードを起点とする経路探索を、送信元ノードからやり直すことを意味する。
【００８１】
また、ステップＳ１６で経路選択試行回数が試行回数閾値を超えたということは、送信元ノードを起点とする経路探索をやり直すことを所定回数行っても、ＳＬＡの性能要件を満たす経路を探索できなかったことを意味する。この場合であっても、送信元ノードから送信先ノードまでの経路を決定する必要がある。そこで、経路選択試行回数が試行回数閾値を超えている場合、ステップＳ１５に移行し、経路探索を継続する。
【００８２】
ステップＳ１５の後、次ホップノード決定部１００は、ステップＳ１５での更新後の対象ノード（換言すれば、直近のステップＳ１３で選択した次ホップノード）と、送信先ノード５−ｊとが一致しているか否かを判定する（ステップＳＳ１８）。
【００８３】
ステップＳ１５での更新後の対象ノードと送信先ノード５−ｊとが一致していなければ（ステップＳ１８におけるＮｏ）、未だ、送信先ノード５−ｊまでの経路探索が完了していないということである。この場合、ステップＳ１２以降の処理を繰り返す。すなわち、更新後の対象ノードに対する次ホープノードを選択し、経路探索を継続する。
【００８４】
制御サーバ１０は、ステップＳ１２〜Ｓ１８の処理を繰り返すことで、１ホップずつ、確率的に中継ノード５−ｒを決定していく。そして、ステップＳ１５での更新後の対象ノードと送信先ノード５−ｊとが一致した場合、送信元ノード５−Ｓから送信先ノード５−ｊへの通信経路が確定したことになる。
【００８５】
テップＳ１５での更新後の対象ノードと送信先ノード５−ｊとが一致した場合（ステップＳ１８におけるＹｅｓ）、ノード設定部２００は、確定した通信経路上の各ノードに転送テーブル設定コマンドを送信する（ステップＳ１９）。転送テーブル設定コマンドは、具体的には、通信経路上のノードに対して、そのノードの次ホップノードとなるノードを指定して、経路設定要求の基となったトラフィックに関して、その次ホップノードを転送先とするように転送テーブルを設定することを指示するコマンドである。ノード設定部２００は、経路ノードリストに登録されている各ノードに対して、転送テーブル設定コマンドを送信する。
【００８６】
なお、ステップＳ１９において、リンク上フロー数管理部６００は、確定した通信経路上の各リンクのフロー数を、それぞれ１インクリメントする。
【００８７】
転送テーブル設定コマンドを受信した各ノード５は、転送テーブル設定コマンドに応じて自身の転送テーブルを設定する。すなわち、経路設定要求の基となったトラフィックの識別情報と、指定された転送先ノードとを対応付けて転送テーブルに追加する。そして、各ノード５は、その識別情報に合致するトラフィックを受信したときには、そのトラフィックに対応する転送先ノードにトラフィックを転送する。この結果、トラフィックは、送信元ノードから送信先ノードまで順次転送されることになり、送信先ノードに到達する。
【００８８】
本発明によれば、制御サーバ１０は、送信元ノードから、１ホップずつ、確率的に次ホップノードを選択していき、送信先ノードまでの経路を確定する。そして、次ホップノードを選択したときに、制御サーバ１０は、送信元ノードからからその次ホップノードまでの経路Ｒにおける通信性能が性能要件ＳＰＱを満たしているか否かを判定する。制御サーバ１０は、経路Ｒにおける通信性能が性能要件ＳＰＱを満たしていれば、次ホップノードの選択を再度繰り返す。また、経路Ｒにおける通信性能が性能要件ＳＰＱを満たしていなければ、送信元ノードから経路の探索をやり直す。このように、本発明によれば、ダミートラフィックを流さなくても、ＳＬＡで規定された性能要件を満たす、送信元ノードから送信先までの経路を探索することができる。よって、ＳＬＡを保証するトラフィックの通信経路を効率的に探索することができる。
【００８９】
上記の実施形態は、制御サーバ１０における集中制御によって、ＳＬＡを保証する経路を探索する。本発明は、分散制御によってＳＬＡを保証する経路探索方法として実現されてもよい。
【００９０】
次に、本発明の最小構成について説明する。図６は、本発明の最小構成の例を示すブロック図である。本発明の経路選択装置は、次ホップノード選択手段９１と、性能判定手段９２とを備える。
【００９１】
次ホップノード選択手段９１（例えば、次ホップノード決定部１００）は、トラフィックの送信元ノードを起点とし、１ホップずつ、複数の次ホップノード候補の中から確率的に次ホップノードを選択する。
【００９２】
性能判定手段９２（例えば、通信品質管理部５００）は、１つの次ホップノードが選択されたときに、送信元ノードからその次ホップノードまでの経路における通信性能が、サービスレベルアグリーメント（ＳＬＡ）で規定された基準を満たしているか否かを判定する。
【００９３】
次ホップノード選択手段９１は、通信性能が基準を満たしていると判定された場合に、さらに次の次ホップノードを選択する。また、通信性能が基準を満たしていないと判定された場合に、次ホップノードの選択を、送信元ノードに対する次ホップノードの選択からやり直す。
【００９４】
そのような構成により、ＳＬＡを保証するトラフィックの通信経路を効率的に選択できる。
【００９５】
また、性能判定手段９２は、１つの次ホップノードが選択されたときに、送信元ノードからその次ホップノードまでの経路における通信性能として、その経路における通信遅延を算出し、通信遅延が、通信遅延に関する基準を満たしているか否かを判定してもよい。
【００９６】
また、性能判定手段９２は、１つの次ホップノードが選択されたときに、送信元ノードからその次ホップノードまでの経路における通信性能として、その経路における１フロー当たりの使用可能帯域を算出し、その１フロー当たりの使用可能帯域が、１フロー当たりの使用可能帯域に関する基準を満たしているか否かを判定してもよい。
【００９７】
また、性能判定手段９２は、１つの次ホップノードが選択されたときに、送信元ノードからその次ホップノードまでの経路における通信性能として、その経路におけるトラフィックのロス率を算出し、そのロス率が、ロス率に関する基準を満たしているか否かを判定してもよい。
【００９８】
次ホップノード選択手段９１が、送信元ノードに対する次ホップノードの選択から、次ホップノードの選択をやり直した回数が閾値を超えた場合、通信性能が、サービスレベルアグリーメントで規定された基準を満たしていなくても、さらに次の次ホップノードを選択する構成であってもよい。
【産業上の利用可能性】
【００９９】
本発明は、通信ネットワーク内のトラフィックの通信経路を選択する経路選択装置に好適に適用される。
【符号の説明】
【０１００】
５  ノード
１０  制御サーバ（経路選択装置）
１００  次ホップノード決定部
２００  ノード設定部
３００  経路ノードリスト記憶部
４００  転送確率テーブル記憶部
５００  通信品質管理部
６００  リンク上フロー数管理部
【図１】
2013197734.tif 000007
【図２】
2013197734.tif 000008
【図３】
2013197734.tif 000009
【図４】
2013197734.tif 000010
【図５】
2013197734.tif 000011
【図６】
2013197734.tif 000012