動的フローレットスケジューリングシステムおよび方法
【課題】 動的フローレットスケジューリングシステムおよび動的フローレットスケジューリング方法を提供する。
【解決手段】 ホストは、データセンターのフロースケジューラに対し、特定フロー用として予約された帯域幅を申請する。フロースケジューラは、当該特定フローが通過しうるすべてのパスの帯域幅の使用状況をチェックする。これらのパスの残余帯域幅の合計が、当該特定フローの帯域幅要求を満たす場合、このフローは１つ以上のフローレットに分割された後、対応するパスに転送される。これらのパスの残余帯域幅の合計が、当該特定フローの帯域幅要求を満たさない場合には、当該特定フローを転送するための余地を作るために、これらのパス上の既存のフローが他のパスに移動される。
【解決手段】 ホストは、データセンターのフロースケジューラに対し、特定フロー用として予約された帯域幅を申請する。フロースケジューラは、当該特定フローが通過しうるすべてのパスの帯域幅の使用状況をチェックする。これらのパスの残余帯域幅の合計が、当該特定フローの帯域幅要求を満たす場合、このフローは１つ以上のフローレットに分割された後、対応するパスに転送される。これらのパスの残余帯域幅の合計が、当該特定フローの帯域幅要求を満たさない場合には、当該特定フローを転送するための余地を作るために、これらのパス上の既存のフローが他のパスに移動される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データセンターネットワークの分野に関し、特に、動的フローレットスケジューリングのためのシステムおよび方法に関する。
【背景技術】
【０００２】
インターネットや、クラウドコンピューティングサービス等のアプリケーションの発達に伴って、データセンターの規模はますます増大しており、今や数万〜数十万台のサーバおよびスイッチを備えていることも珍しくない。加えて、データセンターは多種多様なアプリケーションを同時にサポートするのが一般的であり、これらのアプリケーションにはデータセンター内の異なるサーバ間で大量なデータ通信を必要とするものも含まれる。こうしたデータセンターの拡大とアプリケーションの発達により、データセンターのネットワークアーキテクチャに新たな課題が生じている。
【０００３】
一般に、スイッチのポート数には限りがあるため、データセンターは複数ルートのツリートポロジ形式となっている。図１に、ホスト間通信用として複数の任意パスを提供する、複数ルートのツリートポロジを示す。このトポロジには複数の任意パスが存在するので、高度に集約された帯域幅を実現するために、これらのパス間のフローを動的にスケジューリングする方法を確立することが重要な課題となる。
【０００４】
現在、フローのスケジューリングにおいて最も一般的に使用されているメカニズムは、等価コストマルチパス（ＥＣＭＰ：Ｅｑｕａｌ Ｃｏｓｔ Ｍｕｌｔｉｐａｔｈ）スキームである。１つの宛先ホストが与えられると、スイッチは当該ホストに関して複数の転送用任意パスが確立されるように構成される。スイッチにパケットが着信すると、スイッチはパケットのヘッダ内の特定フィールドに対してハッシュ演算を実行し、続いて任意パスの総数に関するモジュロ演算を実行して最終的に選択されるパスを決定し、そのパスを介してパケットを転送する。ハッシュアルゴリズムは、複数の任意パスの間でデータトラフィックを無作為に分散して負荷バランスを確保する。
【０００５】
ただし、ＥＣＭＰは静的なマッピングスキームなので、同じフローのすべてのパケットが常に１つの特定のパスにマッピングされる。さらに、ＥＣＭＰによれば、ネットワークの使用状況やフローサイズは無視され、ハッシュ演算の結果だけに基づいて転送用パスが選択される。このような方法であれば、状況によっては、複数の大量フローに対して同じパスが選択される可能性がある。これが発生すると、ネットワーク内にボトルネックが生じて、ネットワーク全体の使用率が低下する。図２に２種類のフロー衝突を示す。図２を見ると、スイッチＡｇｇ０でハッシュ衝突が発生したために、フローＡとフローＢに対して同じパスが選択されている。加えて、スイッチＡｇｇ１およびＡｇｇ２からそれぞれ別個に転送されたフローＣとフローＤのパケットが、スイッチＣｏｒｅ２で衝突している。図２の各リンクの最大帯域は１Ｇｂｐｓとすると、衝突のために、全４つのフローは５００Ｍｂｐｓの帯域幅にしか到達できない。ＥＣＭよりも優れた、ネットワークリソースの使用状況とフロー状態とに基づいてフローをスケジューリングできる方法があれば、例えばフローＡはスイッチＣｏｒｅ１にスケジューリングされ、フローＤはスイッチＣｏｒｅ３にスケジューリングされるので、全４フローの各々が１Ｇｂｐｓの帯域幅に到達することができる。
【０００６】
このように、静的なマッピングスキームであるＥＣＭＰはネットワークの使用状況とフローサイズのいずれも考慮しないため、衝突が発生し、ネットワーク全体の使用率が低下する結果となる。
【０００７】
非特許文献１（“Ｈｅｄｅｒａ：Ｄｙｎａｍｉｃ Ｆｌｏｗ Ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋｓ（Ｈｅｄｅｒａ：データセンターネットワークのための動的フロースケジューリング）”，Ｍｏｈａｍｍａｄ Ａｌ−Ｆａｒｅｓ，ｅｔ ａｌ，ＮＳＤＩ ２０１０）は、データセンターネットワークのための動的フロースケジューリングシステムを提案している。Ｈｅｄｅｒａは、まず、エッジスイッチで大量フローを検出する。次に、大量フローによる帯域幅要求を予想し、これらのフローのための最良のパスを計算する。最後に、計算されたパスがスイッチ上にインストールされる。
【０００８】
図３はＨｅｄｅｒａシステムの構造図である。図３に示すように、Ｈｅｄｅｒａは「ファットツリー」ネットワークトポロジに基づき設計および実装されたフロースケジューリングシステムである（非特許文献２（“Ａ ｓｃａｌａｂｌｅ，Ｃｏｍｍｏｄｉｔｙ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ Ａｒｃｈｉｔｅｃｔｕｒｅ（スケーラブルなコモディティデータセンターネットワークアーキテクチャ）”，Ｍｏｈａｍｍａｄ Ａｌ−Ｆａｒｅｓ，ｅｔ ａｌ，ＳＩＧＣＯＭＭ ２００８）を参照）。ファットツリー内のスイッチは、エッジ層、集約層、コア層（下から上）に編成される。３つの異なる層のすべてのスイッチは同じであり、各々ｋ個のポートを備えている。図３は、ｋ＝４のファットツリートポロジを示す。ファットツリーはｋ個のポッドに分割されており、これはエッジ層と集約層にあるｋ個の点線枠で示されている。ｋ個の点線枠の各々に囲まれたｋ個のスイッチが、１つのポッドを構成する。ファットツリートポロジでは、各々ｋ個のポートを有する５ｋ２／４個のスイッチによって、ｋ３／４個のホストをサポートすることができる。各スイッチではＯｐｅｎＦｌｏｗが稼働している。ＯｐｅｎＦｌｏｗコントローラは、各スイッチ内の転送テーブルにアクセスして、転送テーブル内のフローエントリに対してクエリ、挿入、修正等の操作を実行することができる。フロースケジューラは、現在のネットワーク状態に基づいて、衝突が発生しないパスにフローをスケジューリングする。ＯｐｅｎＦｌｏｗコントローラとフロースケジューラは、論理的に中央化された中央管理装置上で稼働する。
【０００９】
図４はＨｅｄｅｒａシステム４０のブロック図である。図４に示すように、Ｈｅｄｅｒａシステム４０はスイッチ４１０と中央管理装置４２０で構成される。
【００１０】
スイッチ４１０は、転送テーブル４１１０と、パケット転送手段４１２０と、フロー統計報告手段４１３０とを備える。転送テーブル４１１０は、フローと送信ポート間のマッピングを保持する。パケット転送手段４１２０は、転送テーブル４１１０に保持されるマッピングに基づいてパケットを転送する。フロー統計報告手段４１３０はトラフィック統計を生成し、その統計を中央管理装置４２０に定期的（例：５秒間隔）に報告する。
【００１１】
中央管理装置４２０は、スイッチコントローラ４２１０と、フロースケジューリング手段４２２０と、フロー要求予想手段４２３０と、フロー要求テーブル４２４０と、フロー統計収集手段４２５０とを備える。フロー統計収集手段４２５０は、各スケジューリング期間（例：５秒間）にフロー統計報告手段４１３０からトラフィック統計を受信し、大量フローを検出する。フロー要求テーブル４２４０は、全ホストに関するフロー要求行列を保持する。フロー要求予想手段４２３０は、トラフィック統計を使ってフローの帯域幅要求を予想する。フロースケジューリング手段４２２０は、大量フローに、すべての任意パスから適切なパスを選んで割り当てる。スイッチコントローラ４２１０は、フロースケジューリング手段４２２０から受け取ったスケジューリング結果に基づいて、対応するスイッチ内に転送エントリを作成し、大量フローが新たに選択されたパスに転送されるようにする。
【００１２】
具体的に述べると、新たなフローが開始したときにスイッチ４１０がとるデフォルトの振る舞いは、フローのハッシュ値（ＥＣＭＰに関連して説明済み）に基づいて等価コストパスの１つを選択することである。スイッチ４１０はこのパスに沿ってフローを転送し、フローのトラフィック量が事前に決定されたしきい値を超えるまでこれを継続する。しきい値としては、例えば１００ Ｍｂｐｓ（１ＧｉｇＥリンクの帯域幅の１０％）が考えられる。フロー統計収集手段４２５０は、各スケジューリング期間中に、大量フローを検出するためにエッジスイッチからトラフィック統計を１度取得する。その後、フロー要求予想手段４２３０が大量フローの帯域幅要求を予想する。次に、フロースケジューリング手段４２２０が、大量フローの帯域幅要求に基づいて、大量フローに適切なパスを計算する。最後に、スイッチコントローラ４２１０が、転送エントリを修正することにより対応するスイッチ上にパスをインストールし、大量フローはこの新たに選択されたパスに転送されるようになる。
【００１３】
すべての大量フローの現在のトラフィック統計は、Ｎ×Ｎ行列Ｍ（Ｎはホスト数）を保持するフロー要求予想手段４２３０に入力される。行列Ｍの第ｉ行第ｊ列の要素Ｍ（ｉ，ｊ）には、ホストｉからホストｊへのフローの予想要求が保持される。フロー要求予想手段４２３０は、送信元ホストにおいてフローの帯域幅要求を増大させ、かつ宛先ホストの帯域幅限界に基づいてフロー帯域幅を超過分だけ減少させる作業を繰り返し実行し、すべてのフローの帯域幅要求が満たされるまでこれを継続する。
【００１４】
大量フローの帯域幅要求が予想された後、フロースケジューリング手段４２２０は、帯域幅要求に基づいて大量フローに適切なパスを計算する。非特許文献１では、２つのスケジューリングアルゴリズムが使用されている。第１のスケジューリングアルゴリズムは「Ｇｌｏｂａｌ Ｆｉｒｓｔ Ｆｉｔ」と呼ばれるもので、新たな大量フロー検出されると、スケジューラがすべての任意パスを直線的に検索し、そのフローの帯域幅要求をすべて収容可能なリンクを有するパスを発見して、その発見されたパスをスケジューリング結果として選択する。第２のスケジューリングアルゴリズムは「Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ」と呼ばれ、状態空間を検索してほぼ最適な解決法を発見する汎用の確率的アルゴリズムである。Ｈｅｄｅｒａシステム４０は、検索空間内の状態数を削減するため、各フローに１つのコアスイッチを割り当てるのではなく、各宛先ホストに１つのコアスイッチを割り当てる。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】“Ｈｅｄｅｒａ：Ｄｙｎａｍｉｃ Ｆｌｏｗ Ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋｓ（Ｈｅｄｅｒａ：データセンターネットワークのための動的フロースケジューリング）”，Ｍｏｈａｍｍａｄ Ａｌ−Ｆａｒｅｓ，ｅｔ ａｌ，ＮＳＤＩ ２０１０
【非特許文献２】“Ａ ｓｃａｌａｂｌｅ，Ｃｏｍｍｏｄｉｔｙ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ Ａｒｃｈｉｔｅｃｔｕｒｅ（スケーラブルなコモディティデータセンターネットワークアーキテクチャ）”，Ｍｏｈａｍｍａｄ Ａｌ−Ｆａｒｅｓ，ｅｔ ａｌ，ＳＩＧＣＯＭＭ ２００８
【発明の概要】
【発明が解決しようとする課題】
【００１６】
ただし、Ｈｅｄｅｒａシステムで使用されるスケジューリングメカニズムは、以下の欠点を有する。第１に、フローの実際の帯域幅要求はエッジスイッチで測定されたトラフィック統計から予想されるが、この統計は時にアプリケーションの実際の帯域幅要求を正確に反映していないため、実際のフローの帯域幅要求を正確かつ時宜を得て取得することができない。また、スケジューリングは各スケジューリング期間（例：５秒間）に１度しか実行されないため、１つのスケジューリング期間中にトラフィック状態が大幅に変動したという可能性が常に残る。第２に、フローの粒度に基づくスケジューリングは、状況によっては、バランスのとれたネットワーク使用と高度に集約されたネットワーク帯域幅を達成するのには不十分である。
【００１７】
上記の問題に対処するため、本発明は、データセンターネットワークのための動的フローレットスケジューリングシステムを提供する。ホストは、データセンターのフロースケジューラに対し、特定フロー用として予約された帯域幅を申請する。フロースケジューラは、当該特定フローが通過しうるすべてのパスの帯域幅の使用状況をチェックする。これらのパスの残余帯域幅の合計が、当該特定フローの帯域幅要求を満たす場合、このフローは１つ以上のフローレットに分割された後、対応するパスに転送される。これらのパスの残余帯域幅の合計が、当該特定フローの帯域幅要求を満たさない場合には、当該特定フローを転送するための余地を作るために、これらのパス上の既存のフローが他のパスに移動される。
【課題を解決するための手段】
【００１８】
本発明の第１の態様によれば、中央管理装置であって、送信元ホストからの特定フローの帯域幅要求を収集するように構成された帯域幅要求収集手段と、リンクの帯域幅使用状況とホストペアの任意パスとを記憶するように構成された記憶手段と、現在のリンクの帯域幅使用状況に基づいて、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当て、割り当てられたパスを送信元ホストに返し、かつ送信元ホストからフローレット情報を受信するように構成されたフロースケジューリング手段と、フロースケジューリング手段のスケジューリング結果に基づいて、対応するスイッチを設定するように構成されたスイッチコントローラとを備える、中央管理装置が提供される。
【００１９】
フロースケジューリング手段は、当該特定フローの任意パスにおけるアイドル帯域幅の合計を計算し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当てるように構成されるのが望ましい。
【００２０】
フロースケジューリング手段はさらに、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該特定フローの任意パスをアイドル帯域幅の多い順に並び替え、選択したパスのアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上になるまで、前記並び替えられた任意パスからパスを順に選択するように構成されるのが望ましい。
【００２１】
フロースケジューリング手段はさらに、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、当該特定フローの任意パスを通過する他のフローを検出して、当該他のフローの任意パスにおけるアイドル帯域幅の合計を計算し、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該他のフローを再スケジュールして、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当てるように構成されるのが望ましい。
【００２２】
フロースケジューリング手段はさらに、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替えて、並び替えられたフローから１つのフローを順に選択し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、選択したフローを再スケジュールするように構成されるのが望ましい。
【００２３】
フロースケジューリング手段はさらに、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合には、当該他のフローをそのアイドルパスへ再スケジュールして、当該特定フローの任意パスにおけるアイドル帯域幅を、当該特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ当該特定フローの任意パスを通過する残余フローとに割り当てるように構成されるのが望ましい。
【００２４】
フロースケジューリング手段はさらに、送信元ホストから受信されたフローレット情報を宛先ホストへ送信するように構成されるのが望ましい。
【００２５】
記憶手段はさらに、フローレット情報を記憶するように構成されるのが望ましい。
【００２６】
フローレット情報はフローレットのポート番号を含むのが望ましい。
【００２７】
本発明の他の態様によれば、フロースケジューリング方法であって、送信元ホストからの特定フローの帯域幅要求を収集するステップと、現在のリンクの帯域幅使用状況に基づいて、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当てるステップと、割り当てられたパスを送信元ホストに返すステップと、送信元ホストからフローレット情報を受信するステップと、スケジューリング結果に基づいて対応するスイッチを構成するステップとを備えるのが望ましい。
【００２８】
割り当てステップは、当該特定フローの任意パスにおけるアイドル帯域幅の合計を計算するステップと、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合には、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当てるステップとを備えるのが望ましい。
【００２９】
当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合には、当該特定フローの任意パスがアイドル帯域幅の多い順に並び替えられて、並び替えられた任意パスから１つのパスが選択され、選択されたパスのアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまでこれが継続されるのが望ましい。
【００３０】
当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合には、当該特定フローの任意パスを通過するフローが検出されて、当該他のフローの任意パスにおけるアイドル帯域幅の合計が計算され、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合には、当該他のフローが再スケジュールされて、当該特定フローの任意パスから１つ以上のパスが当該特定フロー用として割り当てられるのが望ましい。
【００３１】
当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合には、当該他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替えて、並び替えられたフローから１つのフローが順に選択され、そのフローが再スケジュールされ、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまでこれが継続されるのが望ましい。
【００３２】
当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合には、当該他のフローがそのアイドルパスへ再スケジュールされて、当該特定フローの任意パスにおけるアイドル帯域幅が、当該特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ当該特定フローの任意パスを通過する残余フローとに割り当てられるのが望ましい。
【００３３】
この方法は、送信元ホストから受信されたフローレット情報を宛先ホストへ送信するステップをさらに備えるのが望ましい。
【００３４】
フローレット情報はフローレットのポート番号を含むのが望ましい。
【００３５】
本発明の他の態様によれば、ホストであって、中央管理装置に特定フロー用の帯域幅を申請するように構成された帯域幅予約手段と、中央管理装置から返されたスケジューリング結果に基づいて、当該特定フローを１つ以上のフローレット（分流：flowlet）に分割し、中央管理装置によって割り当てられたパス上で１つ以上のフローレットを転送するための対応する接続を確立するように構成されたフロー制御手段とを備えるホストが提供される。
【００３６】
このホストは、１つ以上のフローレットを介して受信されたデータを再構築するように構成されたデータ再構築手段をさらに備えるのが望ましい。
【００３７】
フロー制御手段は、フローレットを変更するコマンドが中央管理装置から受信された場合には、対応する接続を調整するように構成されるのが望ましい。
【発明の効果】
【００３８】
本発明の動的フローレットスケジューリングシステムおよび動的フローレットスケジューリング方法を使用することにより、フローの実際の帯域幅要求を正確かつ時宜を得て取得でき、かつ、スケジューリングをフローよりも細かい粒度に基づいて（すなわち、フローレットの粒度に基づいて）実行することができる。そのため、本発明の動的フローレットスケジューリングシステムおよび動的フローレットスケジューリング方法は、データセンターネットワーク全体のネットワーク使用率のバランスをとり、さらには、データセンターネットワーク全体の集約帯域幅を増大させることが可能となる。
【図面の簡単な説明】
【００３９】
本発明の上記および他の特徴は、詳細な説明と添付図面を併せて参照することでより明らかとなるであろう。
【００４０】
【図１】従来技術における複数ルートのツリートポロジを示す概略図である。
【図２】従来技術における２種類のフロー衝突を示す概略図である。
【図３】従来技術におけるＨｅｄｅｒａシステムを示す概略図である。
【図４】従来技術におけるＨｅｄｅｒａシステムを示すブロック図である。
【図５】本発明の一実施例による動的フローレットスケジューリングシステムを示すブロック図である。
【図６】本発明の一実施例による動的フローレットスケジューリングシステムの動作を示すフローチャートである。
【図７】本発明の一実施例によるフロースケジューリングアルゴリズムを示すフローチャートである。
【図８】本発明の他の実施例による動的フローレットスケジューリングシステムを示すブロック図である。
【図９】本発明の他の実施例による動的フローレットスケジューリングシステムの動作を示すフローチャートである。
【発明を実施するための形態】
【００４１】
以下では、本発明の原理および実施がより明らかとなるように、添付図面を参照して本発明による特定の実施例を説明する。本発明は以下で説明する特定の実施例に限定されないことに留意されたい。煩雑化を避けるため、本発明に直接関係しないよく知られた技術の詳細な説明は省略する。
【００４２】
図５は、本発明の一実施例による動的フローレットスケジューリングシステム５０を示すブロック図である。図５に示すように、動的フローレットスケジューリングシステム５０は、ホスト５１０、中央管理装置５２０、スイッチ５３０という３種類のノードで構成される。
【００４３】
スイッチ５３０は、転送テーブル５３１０とパケット転送手段５３２０とを備える。転送テーブル５３１０は、フローと送信ポート間のマッピングを保持する。パケット転送手段５３２０は、転送テーブル５３１０に保持されるマッピングに基づいてパケットを転送する。
【００４４】
ホスト５１０は、フロー制御手段５１１０と帯域幅予約手段５１２０とを備える。帯域幅予約手段５１２０は、中央管理装置５２０に対し、特定フロー用として予約された帯域幅を申請する。フロー制御手段５１１０は、中央管理装置５２０からのスケジューリング結果に基づいて、当該特定フローを１つ以上のフローレットに分割し、当該フローレットを各々のパス上で転送する。
【００４５】
中央管理装置５２０は、スイッチコントローラ５２１０と、フロースケジューリング手段５２２０と、帯域幅使用状況・パス情報テーブル記憶手段５２３０と、帯域幅要求収集手段５２４０とを備える。帯域幅要求収集手段５２４０は、ホスト５１０からフローの帯域幅要求を収集する。帯域幅使用状況・パス情報テーブル記憶手段５２３０は、すべてのリンクの帯域幅使用状況と、各ホストペアのすべての任意パスとを記憶する。フロースケジューリング手段５２２０は、ネットワークリンクの現在の帯域幅使用状況に基づいて、特定フロー用のすべての任意パスから１つ以上の適切なパスを割り当てる。スイッチコントローラ５２１０は、当該特定フローを転送するために、フロースケジューリング手段５２２０から受け取ったスケジューリング結果に基づいて、対応するスイッチ内に転送エントリを作成する。
【００４６】
次に、図５に示す動的フローレットスケジューリングシステム５０の動作について、図６を参照しながら詳細に説明する。
【００４７】
図６は、本発明の一実施例による動的フローレットスケジューリングシステム５０の動作を示すフローチャートである。図６においては、ホストＡ、ホストＢ、ホストＣの各々は図５に示すホスト５１０を使用して実施し、中央管理装置は図５に示す中央管理装置５２０を使用して実施し、スイッチは図５に示すスイッチ５３０を使用して実施することができる。具体的な動作は以下のとおりである。
【００４８】
１．１：送信元ホストＡ上で、ある特定のアプリケーションが帯域幅予約手段に対し、このアプリケーションに対応するフローの帯域幅要求を通知する。
１．２：送信元ホストＡの帯域幅予約手段が、中央管理装置に対し帯域幅の予約を申請する。
１．３：中央管理装置のフロースケジューリング手段が、スケジューリングアルゴリズム（後述する）に基づいて、フロースケジューリングを実行する（すなわち、すべての任意パスからの１つ以上のパスを当該特定フロー用に割り当てる）。
１．４：中央管理装置が、帯域幅の予約を申請した送信元ホストＡに、割り当てられたパスと、各パスの予約された帯域幅とを返す。
１．５：送信元ホストＡのフロー制御手段が、スケジューリング結果に基づいて、当該特定フローを１つ以上のフローレットに分割する。
１．６：送信元ホストＡが、中央管理装置にフローレット情報（フローレットが使用するポート番号等）を報告する。
１．７：中央管理装置のスイッチコントローラが、対応するスイッチ内に転送エントリを作成して、対応するスイッチが新たに選択されたパスを介してフローレットを転送するようにする。
１．８：中央管理装置は、状況に応じて、当該特定フローの帯域幅予約に対応するための余地を作るために、他のホスト（例：ホストＣ）に対しいくつかの既存のフローのパスと占有帯域幅を変更するよう指示する。
１．９：このコマンドを受信したホストＣは、中央管理装置の指示に従って、当該いくつかの既存のフローのパスと占有帯域幅を変更する。
１．１０：送信元ホストＡが、各々１つのフローレットに対応する１つ以上の接続を介してデータを送信する。
１．１１：宛先ホストＢが、当該１つ以上のフローレットを介してデータを受信する。
【００４９】
図７は、本発明の一実施例によるフロースケジューリングアルゴリズムを示すフローチャートである。このスケジューリングアルゴリズムは、フロースケジューリングを実行するために、図５に示す中央管理装置５２０のフロースケジューリング手段５２２０によって実行されてもよい。
【００５０】
まず、ステップＳ７０１において、フローＦとその帯域幅要求ＲＦが取得される。
【００５１】
ステップＳ７０２において、フローＦのすべての任意パスが検出される。ここでは、各々アイドル帯域幅Ｃｉを有する合計Ｎ個のパス｛Ｐｉ、１＜＝ｉ＜＝Ｎ｝があると想定する。
【００５２】
ステップＳ７０３において、以下の式を用いて、全Ｎ個のパスのアイドル状態帯域幅の合計が計算される。
【数１】
【００５３】
次に、ステップＳ７０４において、ＳＦはＲＦ以上か否かが判定される。ＳＦがＲＦ以上の場合（これは、既存のＮ個のパスのアイドル帯域幅がフローＦの帯域幅要求を満たすことを意味する）には、処理はステップＳ７０５に進む。ＳＦがＲＦ未満の場合（これは、既存のＮ個のパスのアイドル帯域幅がフローＦの帯域幅要求を満たさず、従ってこれらのパスの他のフローは、フローFが流れる余地を作る必要があることを意味する）には、処理はステップＳ７０７に進む。
【００５４】
ＳＦがＲＦ以上の場合には、ステップＳ７０５において、当該特定フローの任意パスＰｉがそのアイドル帯域幅Ｃｉの多い順に並べ替えられ、これらの並び替えられた任意パスからいくつかのパスＰｉ（この数をＭとする）が選択され、条件
【数２】
が満足されるまでこれが繰り返される。次にステップＳ７０６において、選択されたＭ個のパスがフローＦに割り当てられ、Ｍ個のパスのアイドル帯域幅ＣｉがフローＦのために予約される。これでフロースケジューリング処理は終了し、制御が返される。
【００５５】
ＳＦがＲＦ未満の場合には、ステップＳ７０７において、｛Ｐｉ，１＜＝ｉ＜＝Ｎ｝を通る他のフロー｛Ｆｊ，１＜＝ｊ＜＝Ｌ｝（すなわち、フローＦと同じパスを共有するフロー）が検出される。既存のＮ個のパスのアイドル帯域幅ではフローＦの帯域幅要求を満たすことができないので、Ｌ個のフローのうちいくつかのフローが、フローＦの帯域幅要求を満たすための余地を作る必要がある。
【００５６】
ステップＳ７０８において、各フローＦｊについて、すべての任意パス｛Ｈｊｋ，１＜＝ｋ＜＝Ｎｊ｝が検出される。ここで、ｊ番目のフローＦｊはＮｊ個のパスを有し、各パスＨｊｋはアイドル帯域幅Ｃｊｋを有する。また、パス｛Ｈｊｋ，１＜＝ｋ＜＝Ｎｊ，１＜＝ｊ＜＝Ｌ｝においては、合計Ｔ個のパスがあり、当該Ｔ個のパスの各々はアイドル帯域幅Ｃｔを有すると想定する。異なる複数のフローＦｊは、各々のパスセットＨｊｋ、
【数３】
に共通の要素を有することができる。
【００５７】
ステップＳ７０９において、Ｔ個のパスのアイドル帯域幅の合計
【数４】
と、各フローＦｊのアイドル帯域幅の合計
【数５】
とが、計算される。
【００５８】
ステップＳ７１０において、Ｔ個のパスのアイドル帯域幅の合計ＳｕｍがＲＦ以上かどうかが判定される。ＳｕｍがＲＦ以上の場合には、フローＦが流れる余地を作るためにＬ個のフローＦｊが他のパスに再スケジュールされて、フローＦの帯域幅要求が満足されるので、プロセスはステップＳ７１１に進む。ＳｕｍがＲＦ未満の場合には、Ｌ個のフローＦｊが他のパスに再スケジュールされても、フローＦの帯域幅要求は満足されないので、プロセスはステップＳ７１２に進む。
【００５９】
ＳｕｍがＲＦ以上の場合には、ステップＳ７１１において、フローＦｊはパスＳｊのアイドル帯域幅の合計が多い順に並び替えられ、いくつかのフローＦｊが順に選択され、これらのフローがそれぞれのアイドルパスに再スケジュールされ、解放された帯域幅がフローＦに割り当てられる。この動作は、ＳＦがＲＦ以上になるまで繰り返し継続される。前記再スケジュール動作は、既存のフローレットの再分割、集約、および帯域幅変更で構成される。ＳＦがＲＦ以上になると、プロセスはステップＳ７０５に進む。
【００６０】
ＳｕｍがＲＦ未満の場合には、ステップＳ７１２において、フローＦの追加によりフローＦのどのパスにもアイドル帯域幅はもうないが、Ｆｊの他のパスにはアイドル帯域幅Ｓｊがある可能性があることを考慮して、Ｆｊがそれぞれのアイドルパスに再スケジュールされ、その帯域幅が使い果たされる。その後、ステップＳ７１３において、Ｌ個のフローＦｊを他のパスに再スケジュールしたとしてもフローＦの帯域幅要求は満足されないことを考慮して、パス｛Ｐｉ，１＜＝ｉ＜＝Ｎ｝のアイドル帯域幅が、フローＦと、マキシミン公正原理に基づいた再スケジュール後にもまだパス｛Ｐｉ，１＜＝ｉ＜＝Ｎ｝のいずれかを通過する残余フローとに割り当てられる。このとき、パスＰｉと、計算された対応する帯域幅が、フローＦに割り当てられる。これでフロースケジューリング処理は終了し、制御が返される。
【００６１】
フロースケジューリングの終了後、ホスト５１０のフロー制御手段５１１０は中央管理装置５２０から、スケジューリング結果を取得する。この結果には、当該特定フローに割り当てられたパスと、各パスの予約された帯域幅とが含まれる。フロー制御手段５１１０は、割り当てられたパスに基づいて、当該特定フローを各々１つの割り当てられたパスに対応する１つ以上のフローレットに分割し、その後、各々１つのフローレットに対応する１つ以上の接続を確立する。フロー制御手段５１１０は、このようにして、異なるパス上の帯域幅予約に基づいて、個々のデータトラフィックを送信する。
【００６２】
フロー制御手段５１１０は、データ送信中に中央管理装置５２０からある接続に対応するフローを変更するよう求めるコマンドを受信した場合には、その接続を終了して新たな接続を開始することができる。対応するフローの変更では、フローの分割、フローレットの集約、フローレットの予約済み帯域幅の変更といった動作が実行される。
【００６３】
これに加えて、フロー制御手段５１１０はデータ送信中に、上位層アプリケーションのデータトラフィックも制御する。上位層アプリケーションがデータトラフィックを予約された帯域幅よりも高速で送信する場合には、フロー制御手段５１１０は、上位層アプリケーションのデータをキャッシュして、中央管理装置５２０によって予約された帯域幅に基づいてそのデータを送信することができる。アプリケーション用として大きな帯域幅が予約されたために、一定時間が経過した後もデータ送信速度が予約された帯域幅に到達しなかった場合には、フロー制御手段５１１０は中央管理装置５２０に通知して、リソースの予約を変更するよう求めることができる。
【００６４】
アプリケーションが終了すると、フロー制御手段５１１０は中央管理装置５２０に通知して、対応するリソースの予約をキャンセルするよう求めることができる。
【００６５】
中央管理装置５２０のフロースケジューリング手段５２２０は、フロースケジューリング中には、すべてのリンクの帯域幅使用状況と、各ホストペアのすべての任意パスとを把握している必要がある。この理由から、帯域幅使用状況・パス情報テーブル記憶手段５２３０には、各ホストペアのすべての任意パスを保持するパステーブルと、すべてのフローレットについて、各々が属するフロー、各々が通過するパス、およびこれらのパスの予約された帯域幅を保持する帯域幅使用状況テーブルとが記憶されている。以下の表１および表２は、それぞれ、パステーブルと帯域幅使用テーブルの例を示す。
【表１】
【表２】
【００６６】
メディアストリーミング等の一部のアプリケーションでは、受信されたデータをその順序で保持する必要がある。しかし、データはホストで複数のフローレットに分割された後、複数の接続を介して送信されるので、データの順序は保証されない。そのため、受信側のホストは、データの再構築を実行する必要がある。
【００６７】
図８は、受信されたデータの再構築を可能にした、本発明の他の実施例による動的フローレットスケジューリングシステムを示すブロック図である。図８に示す動的フローレットスケジューリングシステム８０が、図５に示す動的フローレットスケジューリングシステム５０と異なる点は、動的フローレットスケジューリングシステム８０のホスト８１０がデータ再構築手段８１３０をさらに備えることと、中央管理装置８２０の帯域幅使用状況・パス情報テーブル記憶手段８２３０が、帯域幅使用状況・パス情報テーブル記憶手段５２３０とは異なる内容を記憶していることである。具体的には、本実施例においては、データ再構築手段８１３０は複数フローレットから受信したデータを構築し、帯域幅使用状況・パス情報テーブル記憶手段８２３０は、すべてのリンクの帯域幅使用状況、および各ホストペアのすべての任意パスだけでなく、ポート番号等のフローレット情報も記憶する。次に、図８に示す動的フローレットスケジューリングシステム８０の動作について、図９を参照しながら詳細に説明する。
【００６８】
図９は、本発明の一実施例による動的フローレットスケジューリングシステム８０の動作を示すフローチャートである。図９においては、ホストＡ、ホストＢ、ホストＣの各々は図８に示すホスト８１０を使用して実施し、中央管理装置は図８に示す中央管理装置８２０を使用して実施し、スイッチは図８に示すスイッチ８３０を使用して実施することができる。
【００６９】
図から分かるように、図９の動作１．１〜１．１１は図６のそれと同じなので、ここでは動作１．１〜１．１１の詳細な説明は省略する。図６と比較して、図９は、１．１２および１．１３という２つの動作をさらに備える。
【００７０】
宛先ホストＢが複数フローレットから受信したデータを再構築して、上位アプリケーションが元の順序でデータを受信できるようにするためには、データ再構築手段はどのフローレットが同じフローに属するかを把握している必要がある。そのため、中央管理装置はフローレット情報を宛先ホストＢに提供する（動作１．１２）。その後、宛先ホストＢは複数フローレットからデータを受信し、中央管理装置から提供されたフローレット情報に基づいて受信したデータを再構築する（動作１．１３）。
【００７１】
したがって、たとえデータが複数フローレットに分割され、複数の接続を介して送信されたとしても、動的フローレットスケジューリングシステム８０は受信したデータの順序を復元して、メディアストリーミング等の特定のアプリケーションの要件を満たすことができる。
【００７２】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも、上記実施の形態に限定されるものでなく、その技術的思想の範囲内において様々に変形して実施することができる。
【００７３】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【００７４】
（付記１）
送信元ホストからの特定フローの帯域幅要求を収集するように構成された帯域幅要求収集手段と、
リンクの帯域幅使用状況とホストペアの任意パスとを記憶するように構成された記憶手段と、
現在のリンクの帯域幅使用状況に基づいて、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当て、割り当てられたパスを送信元ホストに返し、かつ送信元ホストからフローレット情報を受信するように構成されたフロースケジューリング手段と、
前記フロースケジューリング手段のスケジューリング結果に基づいて、対応するスイッチを設定するように構成されたスイッチコントローラと
を備えることを特徴とする中央管理装置。
【００７５】
（付記２）
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計を計算し、前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるように構成されることを特徴とする付記１に記載の中央管理装置。
【００７６】
（付記３）
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記特定フローの任意パスをアイドル帯域幅の多い順に並び替え、選択したパスのアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上になるまで、前記並び替えた任意パスから１つのパスを順に選択するように構成されることを特徴とする付記２に記載の中央管理装置。
【００７７】
（付記４）
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求を下回る場合、前記特定フローの任意パスを通過する他のフローを検出し、当該他のフローの任意パスにおけるアイドル帯域幅の合計を計算し、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローを再スケジュールして、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるように構成されることを特徴とする付記２に記載の中央管理装置。
【００７８】
（付記５）
前記フロースケジューリング手段は、前記他のフローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替え、並び替えられたフローから１つのフローを順に選択し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、選択したフローを再スケジュールするように構成されることを特徴とする付記４に記載の中央管理装置。
【００７９】
（付記６）
前記フロースケジューリング手段は、前記他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、前記他のフローをそのアイドルパスへ再スケジュールし、前記特定フローの任意パスにおけるアイドル帯域幅を、前記特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ前記特定フローの任意パスを通過する残余フローとに割り当てるように構成されることを特徴とする付記４に記載の中央管理装置。
【００８０】
（付記７）
前記フロースケジューリング手段は、前記送信元ホストから受信されたフローレット情報を宛先ホストへ送信するように構成されることを特徴とする付記１に記載の中央管理装置。
【００８１】
（付記８）
前記記憶手段は、さらに、フローレット情報を記憶するように構成されることを特徴とする付記７に記載の中央管理装置。
【００８２】
（付記９）
前記フローレット情報は、フローレットのポート番号を含むことを特徴とする付記７又は付記８に記載の中央管理装置。
【００８３】
（付記１０）
送信元ホストからの特定フローの帯域幅要求を収集するステップと、
現在のリンクの帯域幅使用状況に基づいて、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるステップと、
割り当てられたパスを送信元ホストに返すステップと、送信元ホストからフローレット情報を受信するステップと、
スケジューリング結果に基づいて対応するスイッチを設定するステップと
を含むことを特徴とするフロースケジューリング方法。
【００８４】
（付記１１）
前記割り当てステップが、
前記特定フローの任意パスにおけるアイドル帯域幅の合計を計算し、
前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、当該特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てることを特徴とする付記１０に記載のフロースケジューリング方法。
【００８５】
（付記１２）
前記割り当てステップが、
前記特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該特定フローの任意パスがアイドル帯域幅の多い順に並び替え、選択したパスのアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、前記並び替えた任意パスから１つのパスを順に選択することを特徴とする付記１１に記載のフロースケジューリング方法。
【００８６】
（付記１３）
前記割り当てステップが、
前記特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、前記特定フローの任意パスを通過する他のフローを検出し、当該他のフローの任意パスにおけるアイドル帯域幅の合計を計算し、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローを再スケジュールし、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てることを特徴とする付記１１に記載のフロースケジューリング方法。
【００８７】
（付記１４）
前記割り当てステップが、
前記他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替え、並び替えたフローから１つのフローを順に選択し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、選択したフローを再スケジュールすることを特徴とする付記１３に記載のフロースケジューリング方法。
【００８８】
（付記１５）
前記割り当てステップが、
前記他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、前記他のフローをそのアイドルパスへ再スケジュールし、前記特定フローの任意パスにおけるアイドル帯域幅を、当該特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ当該特定フローの任意パスを通過する残余フローとに割り当てることを特徴とする付記１３に記載のフロースケジューリング方法。
【００８９】
（付記１６）
前記送信元ホストから受信されたフローレット情報を宛先ホストへ送信するステップをさらに含むことを特徴とする付記１０に記載のフロースケジューリング方法。
【００９０】
（付記１７）
前記フローレット情報はフローレットのポート番号を含むことを特徴とする付記１６に記載のフロースケジューリング方法。
【００９１】
（付記１８）
中央管理装置に特定フロー用の帯域幅を申請するように構成された帯域幅予約手段と、
前記中央管理装置から返されたスケジューリング結果に基づいて、当該特定フローを１つ以上のフローレットに分割し、中央管理装置によって割り当てられたパス上で１つ以上のフローレットを転送するための対応する接続を確立するように構成されたフロー制御手段と
を備えることを特徴とするホスト。
【００９２】
（付記１９）
前記フロー制御手段は、フローレットを変更するコマンドを前記中央管理装置から受信した場合、対応する接続を調整するように構成されることを特徴をとする付記１８に記載のホスト。
【００９３】
（付記２０）
１つ以上のフローレットを介して受信されたデータを再構築するように構成されたデータ再構築手段をさらに備えることを特徴とする付記１８又は付記１９に記載のホスト。
【符号の説明】
【００９４】
４１１０：転送テーブル
４１２０：パケット転送手段
４１３０：フロー統計報告手段
４２１０：スイッチコントローラ
４２２０：フロースケジューリング手段
４２３０：フロー要求予想手段
４２４０：フロー要求テーブル
４２５０：フロー統計収集手段
５１１０：フロー制御手段
５１２０：帯域幅予約手段
５２１０：スイッチコントローラ
５２２０：フロースケジューリング手段
５２３０：帯域幅使用状況・パス情報テーブル
５２４０：帯域幅要求収集手段
５３１０：転送テーブル
５３２０：パケット転送手段
８１１０：フロー制御手段
８１３０：データ再構築手段
８１２０：帯域幅予約手段
８２１０：スイッチコントローラ
８２２０：フロースケジューリング手段
８２３０：帯域幅使用状況・パス情報テーブル記憶手段
８２４０：帯域幅要求収集手段
８３１０：転送テーブル
８３２０：パケット転送手段
８３０：スイッチ
８０：動的フローレットスケジューリングシステム
【技術分野】
【０００１】
本発明は、データセンターネットワークの分野に関し、特に、動的フローレットスケジューリングのためのシステムおよび方法に関する。
【背景技術】
【０００２】
インターネットや、クラウドコンピューティングサービス等のアプリケーションの発達に伴って、データセンターの規模はますます増大しており、今や数万〜数十万台のサーバおよびスイッチを備えていることも珍しくない。加えて、データセンターは多種多様なアプリケーションを同時にサポートするのが一般的であり、これらのアプリケーションにはデータセンター内の異なるサーバ間で大量なデータ通信を必要とするものも含まれる。こうしたデータセンターの拡大とアプリケーションの発達により、データセンターのネットワークアーキテクチャに新たな課題が生じている。
【０００３】
一般に、スイッチのポート数には限りがあるため、データセンターは複数ルートのツリートポロジ形式となっている。図１に、ホスト間通信用として複数の任意パスを提供する、複数ルートのツリートポロジを示す。このトポロジには複数の任意パスが存在するので、高度に集約された帯域幅を実現するために、これらのパス間のフローを動的にスケジューリングする方法を確立することが重要な課題となる。
【０００４】
現在、フローのスケジューリングにおいて最も一般的に使用されているメカニズムは、等価コストマルチパス（ＥＣＭＰ：Ｅｑｕａｌ Ｃｏｓｔ Ｍｕｌｔｉｐａｔｈ）スキームである。１つの宛先ホストが与えられると、スイッチは当該ホストに関して複数の転送用任意パスが確立されるように構成される。スイッチにパケットが着信すると、スイッチはパケットのヘッダ内の特定フィールドに対してハッシュ演算を実行し、続いて任意パスの総数に関するモジュロ演算を実行して最終的に選択されるパスを決定し、そのパスを介してパケットを転送する。ハッシュアルゴリズムは、複数の任意パスの間でデータトラフィックを無作為に分散して負荷バランスを確保する。
【０００５】
ただし、ＥＣＭＰは静的なマッピングスキームなので、同じフローのすべてのパケットが常に１つの特定のパスにマッピングされる。さらに、ＥＣＭＰによれば、ネットワークの使用状況やフローサイズは無視され、ハッシュ演算の結果だけに基づいて転送用パスが選択される。このような方法であれば、状況によっては、複数の大量フローに対して同じパスが選択される可能性がある。これが発生すると、ネットワーク内にボトルネックが生じて、ネットワーク全体の使用率が低下する。図２に２種類のフロー衝突を示す。図２を見ると、スイッチＡｇｇ０でハッシュ衝突が発生したために、フローＡとフローＢに対して同じパスが選択されている。加えて、スイッチＡｇｇ１およびＡｇｇ２からそれぞれ別個に転送されたフローＣとフローＤのパケットが、スイッチＣｏｒｅ２で衝突している。図２の各リンクの最大帯域は１Ｇｂｐｓとすると、衝突のために、全４つのフローは５００Ｍｂｐｓの帯域幅にしか到達できない。ＥＣＭよりも優れた、ネットワークリソースの使用状況とフロー状態とに基づいてフローをスケジューリングできる方法があれば、例えばフローＡはスイッチＣｏｒｅ１にスケジューリングされ、フローＤはスイッチＣｏｒｅ３にスケジューリングされるので、全４フローの各々が１Ｇｂｐｓの帯域幅に到達することができる。
【０００６】
このように、静的なマッピングスキームであるＥＣＭＰはネットワークの使用状況とフローサイズのいずれも考慮しないため、衝突が発生し、ネットワーク全体の使用率が低下する結果となる。
【０００７】
非特許文献１（“Ｈｅｄｅｒａ：Ｄｙｎａｍｉｃ Ｆｌｏｗ Ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋｓ（Ｈｅｄｅｒａ：データセンターネットワークのための動的フロースケジューリング）”，Ｍｏｈａｍｍａｄ Ａｌ−Ｆａｒｅｓ，ｅｔ ａｌ，ＮＳＤＩ ２０１０）は、データセンターネットワークのための動的フロースケジューリングシステムを提案している。Ｈｅｄｅｒａは、まず、エッジスイッチで大量フローを検出する。次に、大量フローによる帯域幅要求を予想し、これらのフローのための最良のパスを計算する。最後に、計算されたパスがスイッチ上にインストールされる。
【０００８】
図３はＨｅｄｅｒａシステムの構造図である。図３に示すように、Ｈｅｄｅｒａは「ファットツリー」ネットワークトポロジに基づき設計および実装されたフロースケジューリングシステムである（非特許文献２（“Ａ ｓｃａｌａｂｌｅ，Ｃｏｍｍｏｄｉｔｙ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ Ａｒｃｈｉｔｅｃｔｕｒｅ（スケーラブルなコモディティデータセンターネットワークアーキテクチャ）”，Ｍｏｈａｍｍａｄ Ａｌ−Ｆａｒｅｓ，ｅｔ ａｌ，ＳＩＧＣＯＭＭ ２００８）を参照）。ファットツリー内のスイッチは、エッジ層、集約層、コア層（下から上）に編成される。３つの異なる層のすべてのスイッチは同じであり、各々ｋ個のポートを備えている。図３は、ｋ＝４のファットツリートポロジを示す。ファットツリーはｋ個のポッドに分割されており、これはエッジ層と集約層にあるｋ個の点線枠で示されている。ｋ個の点線枠の各々に囲まれたｋ個のスイッチが、１つのポッドを構成する。ファットツリートポロジでは、各々ｋ個のポートを有する５ｋ２／４個のスイッチによって、ｋ３／４個のホストをサポートすることができる。各スイッチではＯｐｅｎＦｌｏｗが稼働している。ＯｐｅｎＦｌｏｗコントローラは、各スイッチ内の転送テーブルにアクセスして、転送テーブル内のフローエントリに対してクエリ、挿入、修正等の操作を実行することができる。フロースケジューラは、現在のネットワーク状態に基づいて、衝突が発生しないパスにフローをスケジューリングする。ＯｐｅｎＦｌｏｗコントローラとフロースケジューラは、論理的に中央化された中央管理装置上で稼働する。
【０００９】
図４はＨｅｄｅｒａシステム４０のブロック図である。図４に示すように、Ｈｅｄｅｒａシステム４０はスイッチ４１０と中央管理装置４２０で構成される。
【００１０】
スイッチ４１０は、転送テーブル４１１０と、パケット転送手段４１２０と、フロー統計報告手段４１３０とを備える。転送テーブル４１１０は、フローと送信ポート間のマッピングを保持する。パケット転送手段４１２０は、転送テーブル４１１０に保持されるマッピングに基づいてパケットを転送する。フロー統計報告手段４１３０はトラフィック統計を生成し、その統計を中央管理装置４２０に定期的（例：５秒間隔）に報告する。
【００１１】
中央管理装置４２０は、スイッチコントローラ４２１０と、フロースケジューリング手段４２２０と、フロー要求予想手段４２３０と、フロー要求テーブル４２４０と、フロー統計収集手段４２５０とを備える。フロー統計収集手段４２５０は、各スケジューリング期間（例：５秒間）にフロー統計報告手段４１３０からトラフィック統計を受信し、大量フローを検出する。フロー要求テーブル４２４０は、全ホストに関するフロー要求行列を保持する。フロー要求予想手段４２３０は、トラフィック統計を使ってフローの帯域幅要求を予想する。フロースケジューリング手段４２２０は、大量フローに、すべての任意パスから適切なパスを選んで割り当てる。スイッチコントローラ４２１０は、フロースケジューリング手段４２２０から受け取ったスケジューリング結果に基づいて、対応するスイッチ内に転送エントリを作成し、大量フローが新たに選択されたパスに転送されるようにする。
【００１２】
具体的に述べると、新たなフローが開始したときにスイッチ４１０がとるデフォルトの振る舞いは、フローのハッシュ値（ＥＣＭＰに関連して説明済み）に基づいて等価コストパスの１つを選択することである。スイッチ４１０はこのパスに沿ってフローを転送し、フローのトラフィック量が事前に決定されたしきい値を超えるまでこれを継続する。しきい値としては、例えば１００ Ｍｂｐｓ（１ＧｉｇＥリンクの帯域幅の１０％）が考えられる。フロー統計収集手段４２５０は、各スケジューリング期間中に、大量フローを検出するためにエッジスイッチからトラフィック統計を１度取得する。その後、フロー要求予想手段４２３０が大量フローの帯域幅要求を予想する。次に、フロースケジューリング手段４２２０が、大量フローの帯域幅要求に基づいて、大量フローに適切なパスを計算する。最後に、スイッチコントローラ４２１０が、転送エントリを修正することにより対応するスイッチ上にパスをインストールし、大量フローはこの新たに選択されたパスに転送されるようになる。
【００１３】
すべての大量フローの現在のトラフィック統計は、Ｎ×Ｎ行列Ｍ（Ｎはホスト数）を保持するフロー要求予想手段４２３０に入力される。行列Ｍの第ｉ行第ｊ列の要素Ｍ（ｉ，ｊ）には、ホストｉからホストｊへのフローの予想要求が保持される。フロー要求予想手段４２３０は、送信元ホストにおいてフローの帯域幅要求を増大させ、かつ宛先ホストの帯域幅限界に基づいてフロー帯域幅を超過分だけ減少させる作業を繰り返し実行し、すべてのフローの帯域幅要求が満たされるまでこれを継続する。
【００１４】
大量フローの帯域幅要求が予想された後、フロースケジューリング手段４２２０は、帯域幅要求に基づいて大量フローに適切なパスを計算する。非特許文献１では、２つのスケジューリングアルゴリズムが使用されている。第１のスケジューリングアルゴリズムは「Ｇｌｏｂａｌ Ｆｉｒｓｔ Ｆｉｔ」と呼ばれるもので、新たな大量フロー検出されると、スケジューラがすべての任意パスを直線的に検索し、そのフローの帯域幅要求をすべて収容可能なリンクを有するパスを発見して、その発見されたパスをスケジューリング結果として選択する。第２のスケジューリングアルゴリズムは「Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ」と呼ばれ、状態空間を検索してほぼ最適な解決法を発見する汎用の確率的アルゴリズムである。Ｈｅｄｅｒａシステム４０は、検索空間内の状態数を削減するため、各フローに１つのコアスイッチを割り当てるのではなく、各宛先ホストに１つのコアスイッチを割り当てる。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】“Ｈｅｄｅｒａ：Ｄｙｎａｍｉｃ Ｆｌｏｗ Ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋｓ（Ｈｅｄｅｒａ：データセンターネットワークのための動的フロースケジューリング）”，Ｍｏｈａｍｍａｄ Ａｌ−Ｆａｒｅｓ，ｅｔ ａｌ，ＮＳＤＩ ２０１０
【非特許文献２】“Ａ ｓｃａｌａｂｌｅ，Ｃｏｍｍｏｄｉｔｙ Ｄａｔａ Ｃｅｎｔｅｒ Ｎｅｔｗｏｒｋ Ａｒｃｈｉｔｅｃｔｕｒｅ（スケーラブルなコモディティデータセンターネットワークアーキテクチャ）”，Ｍｏｈａｍｍａｄ Ａｌ−Ｆａｒｅｓ，ｅｔ ａｌ，ＳＩＧＣＯＭＭ ２００８
【発明の概要】
【発明が解決しようとする課題】
【００１６】
ただし、Ｈｅｄｅｒａシステムで使用されるスケジューリングメカニズムは、以下の欠点を有する。第１に、フローの実際の帯域幅要求はエッジスイッチで測定されたトラフィック統計から予想されるが、この統計は時にアプリケーションの実際の帯域幅要求を正確に反映していないため、実際のフローの帯域幅要求を正確かつ時宜を得て取得することができない。また、スケジューリングは各スケジューリング期間（例：５秒間）に１度しか実行されないため、１つのスケジューリング期間中にトラフィック状態が大幅に変動したという可能性が常に残る。第２に、フローの粒度に基づくスケジューリングは、状況によっては、バランスのとれたネットワーク使用と高度に集約されたネットワーク帯域幅を達成するのには不十分である。
【００１７】
上記の問題に対処するため、本発明は、データセンターネットワークのための動的フローレットスケジューリングシステムを提供する。ホストは、データセンターのフロースケジューラに対し、特定フロー用として予約された帯域幅を申請する。フロースケジューラは、当該特定フローが通過しうるすべてのパスの帯域幅の使用状況をチェックする。これらのパスの残余帯域幅の合計が、当該特定フローの帯域幅要求を満たす場合、このフローは１つ以上のフローレットに分割された後、対応するパスに転送される。これらのパスの残余帯域幅の合計が、当該特定フローの帯域幅要求を満たさない場合には、当該特定フローを転送するための余地を作るために、これらのパス上の既存のフローが他のパスに移動される。
【課題を解決するための手段】
【００１８】
本発明の第１の態様によれば、中央管理装置であって、送信元ホストからの特定フローの帯域幅要求を収集するように構成された帯域幅要求収集手段と、リンクの帯域幅使用状況とホストペアの任意パスとを記憶するように構成された記憶手段と、現在のリンクの帯域幅使用状況に基づいて、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当て、割り当てられたパスを送信元ホストに返し、かつ送信元ホストからフローレット情報を受信するように構成されたフロースケジューリング手段と、フロースケジューリング手段のスケジューリング結果に基づいて、対応するスイッチを設定するように構成されたスイッチコントローラとを備える、中央管理装置が提供される。
【００１９】
フロースケジューリング手段は、当該特定フローの任意パスにおけるアイドル帯域幅の合計を計算し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当てるように構成されるのが望ましい。
【００２０】
フロースケジューリング手段はさらに、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該特定フローの任意パスをアイドル帯域幅の多い順に並び替え、選択したパスのアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上になるまで、前記並び替えられた任意パスからパスを順に選択するように構成されるのが望ましい。
【００２１】
フロースケジューリング手段はさらに、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、当該特定フローの任意パスを通過する他のフローを検出して、当該他のフローの任意パスにおけるアイドル帯域幅の合計を計算し、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該他のフローを再スケジュールして、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当てるように構成されるのが望ましい。
【００２２】
フロースケジューリング手段はさらに、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替えて、並び替えられたフローから１つのフローを順に選択し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、選択したフローを再スケジュールするように構成されるのが望ましい。
【００２３】
フロースケジューリング手段はさらに、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合には、当該他のフローをそのアイドルパスへ再スケジュールして、当該特定フローの任意パスにおけるアイドル帯域幅を、当該特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ当該特定フローの任意パスを通過する残余フローとに割り当てるように構成されるのが望ましい。
【００２４】
フロースケジューリング手段はさらに、送信元ホストから受信されたフローレット情報を宛先ホストへ送信するように構成されるのが望ましい。
【００２５】
記憶手段はさらに、フローレット情報を記憶するように構成されるのが望ましい。
【００２６】
フローレット情報はフローレットのポート番号を含むのが望ましい。
【００２７】
本発明の他の態様によれば、フロースケジューリング方法であって、送信元ホストからの特定フローの帯域幅要求を収集するステップと、現在のリンクの帯域幅使用状況に基づいて、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当てるステップと、割り当てられたパスを送信元ホストに返すステップと、送信元ホストからフローレット情報を受信するステップと、スケジューリング結果に基づいて対応するスイッチを構成するステップとを備えるのが望ましい。
【００２８】
割り当てステップは、当該特定フローの任意パスにおけるアイドル帯域幅の合計を計算するステップと、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合には、当該特定フローの任意パスから１つ以上のパスを当該特定フロー用として割り当てるステップとを備えるのが望ましい。
【００２９】
当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合には、当該特定フローの任意パスがアイドル帯域幅の多い順に並び替えられて、並び替えられた任意パスから１つのパスが選択され、選択されたパスのアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまでこれが継続されるのが望ましい。
【００３０】
当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合には、当該特定フローの任意パスを通過するフローが検出されて、当該他のフローの任意パスにおけるアイドル帯域幅の合計が計算され、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合には、当該他のフローが再スケジュールされて、当該特定フローの任意パスから１つ以上のパスが当該特定フロー用として割り当てられるのが望ましい。
【００３１】
当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合には、当該他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替えて、並び替えられたフローから１つのフローが順に選択され、そのフローが再スケジュールされ、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまでこれが継続されるのが望ましい。
【００３２】
当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合には、当該他のフローがそのアイドルパスへ再スケジュールされて、当該特定フローの任意パスにおけるアイドル帯域幅が、当該特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ当該特定フローの任意パスを通過する残余フローとに割り当てられるのが望ましい。
【００３３】
この方法は、送信元ホストから受信されたフローレット情報を宛先ホストへ送信するステップをさらに備えるのが望ましい。
【００３４】
フローレット情報はフローレットのポート番号を含むのが望ましい。
【００３５】
本発明の他の態様によれば、ホストであって、中央管理装置に特定フロー用の帯域幅を申請するように構成された帯域幅予約手段と、中央管理装置から返されたスケジューリング結果に基づいて、当該特定フローを１つ以上のフローレット（分流：flowlet）に分割し、中央管理装置によって割り当てられたパス上で１つ以上のフローレットを転送するための対応する接続を確立するように構成されたフロー制御手段とを備えるホストが提供される。
【００３６】
このホストは、１つ以上のフローレットを介して受信されたデータを再構築するように構成されたデータ再構築手段をさらに備えるのが望ましい。
【００３７】
フロー制御手段は、フローレットを変更するコマンドが中央管理装置から受信された場合には、対応する接続を調整するように構成されるのが望ましい。
【発明の効果】
【００３８】
本発明の動的フローレットスケジューリングシステムおよび動的フローレットスケジューリング方法を使用することにより、フローの実際の帯域幅要求を正確かつ時宜を得て取得でき、かつ、スケジューリングをフローよりも細かい粒度に基づいて（すなわち、フローレットの粒度に基づいて）実行することができる。そのため、本発明の動的フローレットスケジューリングシステムおよび動的フローレットスケジューリング方法は、データセンターネットワーク全体のネットワーク使用率のバランスをとり、さらには、データセンターネットワーク全体の集約帯域幅を増大させることが可能となる。
【図面の簡単な説明】
【００３９】
本発明の上記および他の特徴は、詳細な説明と添付図面を併せて参照することでより明らかとなるであろう。
【００４０】
【図１】従来技術における複数ルートのツリートポロジを示す概略図である。
【図２】従来技術における２種類のフロー衝突を示す概略図である。
【図３】従来技術におけるＨｅｄｅｒａシステムを示す概略図である。
【図４】従来技術におけるＨｅｄｅｒａシステムを示すブロック図である。
【図５】本発明の一実施例による動的フローレットスケジューリングシステムを示すブロック図である。
【図６】本発明の一実施例による動的フローレットスケジューリングシステムの動作を示すフローチャートである。
【図７】本発明の一実施例によるフロースケジューリングアルゴリズムを示すフローチャートである。
【図８】本発明の他の実施例による動的フローレットスケジューリングシステムを示すブロック図である。
【図９】本発明の他の実施例による動的フローレットスケジューリングシステムの動作を示すフローチャートである。
【発明を実施するための形態】
【００４１】
以下では、本発明の原理および実施がより明らかとなるように、添付図面を参照して本発明による特定の実施例を説明する。本発明は以下で説明する特定の実施例に限定されないことに留意されたい。煩雑化を避けるため、本発明に直接関係しないよく知られた技術の詳細な説明は省略する。
【００４２】
図５は、本発明の一実施例による動的フローレットスケジューリングシステム５０を示すブロック図である。図５に示すように、動的フローレットスケジューリングシステム５０は、ホスト５１０、中央管理装置５２０、スイッチ５３０という３種類のノードで構成される。
【００４３】
スイッチ５３０は、転送テーブル５３１０とパケット転送手段５３２０とを備える。転送テーブル５３１０は、フローと送信ポート間のマッピングを保持する。パケット転送手段５３２０は、転送テーブル５３１０に保持されるマッピングに基づいてパケットを転送する。
【００４４】
ホスト５１０は、フロー制御手段５１１０と帯域幅予約手段５１２０とを備える。帯域幅予約手段５１２０は、中央管理装置５２０に対し、特定フロー用として予約された帯域幅を申請する。フロー制御手段５１１０は、中央管理装置５２０からのスケジューリング結果に基づいて、当該特定フローを１つ以上のフローレットに分割し、当該フローレットを各々のパス上で転送する。
【００４５】
中央管理装置５２０は、スイッチコントローラ５２１０と、フロースケジューリング手段５２２０と、帯域幅使用状況・パス情報テーブル記憶手段５２３０と、帯域幅要求収集手段５２４０とを備える。帯域幅要求収集手段５２４０は、ホスト５１０からフローの帯域幅要求を収集する。帯域幅使用状況・パス情報テーブル記憶手段５２３０は、すべてのリンクの帯域幅使用状況と、各ホストペアのすべての任意パスとを記憶する。フロースケジューリング手段５２２０は、ネットワークリンクの現在の帯域幅使用状況に基づいて、特定フロー用のすべての任意パスから１つ以上の適切なパスを割り当てる。スイッチコントローラ５２１０は、当該特定フローを転送するために、フロースケジューリング手段５２２０から受け取ったスケジューリング結果に基づいて、対応するスイッチ内に転送エントリを作成する。
【００４６】
次に、図５に示す動的フローレットスケジューリングシステム５０の動作について、図６を参照しながら詳細に説明する。
【００４７】
図６は、本発明の一実施例による動的フローレットスケジューリングシステム５０の動作を示すフローチャートである。図６においては、ホストＡ、ホストＢ、ホストＣの各々は図５に示すホスト５１０を使用して実施し、中央管理装置は図５に示す中央管理装置５２０を使用して実施し、スイッチは図５に示すスイッチ５３０を使用して実施することができる。具体的な動作は以下のとおりである。
【００４８】
１．１：送信元ホストＡ上で、ある特定のアプリケーションが帯域幅予約手段に対し、このアプリケーションに対応するフローの帯域幅要求を通知する。
１．２：送信元ホストＡの帯域幅予約手段が、中央管理装置に対し帯域幅の予約を申請する。
１．３：中央管理装置のフロースケジューリング手段が、スケジューリングアルゴリズム（後述する）に基づいて、フロースケジューリングを実行する（すなわち、すべての任意パスからの１つ以上のパスを当該特定フロー用に割り当てる）。
１．４：中央管理装置が、帯域幅の予約を申請した送信元ホストＡに、割り当てられたパスと、各パスの予約された帯域幅とを返す。
１．５：送信元ホストＡのフロー制御手段が、スケジューリング結果に基づいて、当該特定フローを１つ以上のフローレットに分割する。
１．６：送信元ホストＡが、中央管理装置にフローレット情報（フローレットが使用するポート番号等）を報告する。
１．７：中央管理装置のスイッチコントローラが、対応するスイッチ内に転送エントリを作成して、対応するスイッチが新たに選択されたパスを介してフローレットを転送するようにする。
１．８：中央管理装置は、状況に応じて、当該特定フローの帯域幅予約に対応するための余地を作るために、他のホスト（例：ホストＣ）に対しいくつかの既存のフローのパスと占有帯域幅を変更するよう指示する。
１．９：このコマンドを受信したホストＣは、中央管理装置の指示に従って、当該いくつかの既存のフローのパスと占有帯域幅を変更する。
１．１０：送信元ホストＡが、各々１つのフローレットに対応する１つ以上の接続を介してデータを送信する。
１．１１：宛先ホストＢが、当該１つ以上のフローレットを介してデータを受信する。
【００４９】
図７は、本発明の一実施例によるフロースケジューリングアルゴリズムを示すフローチャートである。このスケジューリングアルゴリズムは、フロースケジューリングを実行するために、図５に示す中央管理装置５２０のフロースケジューリング手段５２２０によって実行されてもよい。
【００５０】
まず、ステップＳ７０１において、フローＦとその帯域幅要求ＲＦが取得される。
【００５１】
ステップＳ７０２において、フローＦのすべての任意パスが検出される。ここでは、各々アイドル帯域幅Ｃｉを有する合計Ｎ個のパス｛Ｐｉ、１＜＝ｉ＜＝Ｎ｝があると想定する。
【００５２】
ステップＳ７０３において、以下の式を用いて、全Ｎ個のパスのアイドル状態帯域幅の合計が計算される。
【数１】
【００５３】
次に、ステップＳ７０４において、ＳＦはＲＦ以上か否かが判定される。ＳＦがＲＦ以上の場合（これは、既存のＮ個のパスのアイドル帯域幅がフローＦの帯域幅要求を満たすことを意味する）には、処理はステップＳ７０５に進む。ＳＦがＲＦ未満の場合（これは、既存のＮ個のパスのアイドル帯域幅がフローＦの帯域幅要求を満たさず、従ってこれらのパスの他のフローは、フローFが流れる余地を作る必要があることを意味する）には、処理はステップＳ７０７に進む。
【００５４】
ＳＦがＲＦ以上の場合には、ステップＳ７０５において、当該特定フローの任意パスＰｉがそのアイドル帯域幅Ｃｉの多い順に並べ替えられ、これらの並び替えられた任意パスからいくつかのパスＰｉ（この数をＭとする）が選択され、条件
【数２】
が満足されるまでこれが繰り返される。次にステップＳ７０６において、選択されたＭ個のパスがフローＦに割り当てられ、Ｍ個のパスのアイドル帯域幅ＣｉがフローＦのために予約される。これでフロースケジューリング処理は終了し、制御が返される。
【００５５】
ＳＦがＲＦ未満の場合には、ステップＳ７０７において、｛Ｐｉ，１＜＝ｉ＜＝Ｎ｝を通る他のフロー｛Ｆｊ，１＜＝ｊ＜＝Ｌ｝（すなわち、フローＦと同じパスを共有するフロー）が検出される。既存のＮ個のパスのアイドル帯域幅ではフローＦの帯域幅要求を満たすことができないので、Ｌ個のフローのうちいくつかのフローが、フローＦの帯域幅要求を満たすための余地を作る必要がある。
【００５６】
ステップＳ７０８において、各フローＦｊについて、すべての任意パス｛Ｈｊｋ，１＜＝ｋ＜＝Ｎｊ｝が検出される。ここで、ｊ番目のフローＦｊはＮｊ個のパスを有し、各パスＨｊｋはアイドル帯域幅Ｃｊｋを有する。また、パス｛Ｈｊｋ，１＜＝ｋ＜＝Ｎｊ，１＜＝ｊ＜＝Ｌ｝においては、合計Ｔ個のパスがあり、当該Ｔ個のパスの各々はアイドル帯域幅Ｃｔを有すると想定する。異なる複数のフローＦｊは、各々のパスセットＨｊｋ、
【数３】
に共通の要素を有することができる。
【００５７】
ステップＳ７０９において、Ｔ個のパスのアイドル帯域幅の合計
【数４】
と、各フローＦｊのアイドル帯域幅の合計
【数５】
とが、計算される。
【００５８】
ステップＳ７１０において、Ｔ個のパスのアイドル帯域幅の合計ＳｕｍがＲＦ以上かどうかが判定される。ＳｕｍがＲＦ以上の場合には、フローＦが流れる余地を作るためにＬ個のフローＦｊが他のパスに再スケジュールされて、フローＦの帯域幅要求が満足されるので、プロセスはステップＳ７１１に進む。ＳｕｍがＲＦ未満の場合には、Ｌ個のフローＦｊが他のパスに再スケジュールされても、フローＦの帯域幅要求は満足されないので、プロセスはステップＳ７１２に進む。
【００５９】
ＳｕｍがＲＦ以上の場合には、ステップＳ７１１において、フローＦｊはパスＳｊのアイドル帯域幅の合計が多い順に並び替えられ、いくつかのフローＦｊが順に選択され、これらのフローがそれぞれのアイドルパスに再スケジュールされ、解放された帯域幅がフローＦに割り当てられる。この動作は、ＳＦがＲＦ以上になるまで繰り返し継続される。前記再スケジュール動作は、既存のフローレットの再分割、集約、および帯域幅変更で構成される。ＳＦがＲＦ以上になると、プロセスはステップＳ７０５に進む。
【００６０】
ＳｕｍがＲＦ未満の場合には、ステップＳ７１２において、フローＦの追加によりフローＦのどのパスにもアイドル帯域幅はもうないが、Ｆｊの他のパスにはアイドル帯域幅Ｓｊがある可能性があることを考慮して、Ｆｊがそれぞれのアイドルパスに再スケジュールされ、その帯域幅が使い果たされる。その後、ステップＳ７１３において、Ｌ個のフローＦｊを他のパスに再スケジュールしたとしてもフローＦの帯域幅要求は満足されないことを考慮して、パス｛Ｐｉ，１＜＝ｉ＜＝Ｎ｝のアイドル帯域幅が、フローＦと、マキシミン公正原理に基づいた再スケジュール後にもまだパス｛Ｐｉ，１＜＝ｉ＜＝Ｎ｝のいずれかを通過する残余フローとに割り当てられる。このとき、パスＰｉと、計算された対応する帯域幅が、フローＦに割り当てられる。これでフロースケジューリング処理は終了し、制御が返される。
【００６１】
フロースケジューリングの終了後、ホスト５１０のフロー制御手段５１１０は中央管理装置５２０から、スケジューリング結果を取得する。この結果には、当該特定フローに割り当てられたパスと、各パスの予約された帯域幅とが含まれる。フロー制御手段５１１０は、割り当てられたパスに基づいて、当該特定フローを各々１つの割り当てられたパスに対応する１つ以上のフローレットに分割し、その後、各々１つのフローレットに対応する１つ以上の接続を確立する。フロー制御手段５１１０は、このようにして、異なるパス上の帯域幅予約に基づいて、個々のデータトラフィックを送信する。
【００６２】
フロー制御手段５１１０は、データ送信中に中央管理装置５２０からある接続に対応するフローを変更するよう求めるコマンドを受信した場合には、その接続を終了して新たな接続を開始することができる。対応するフローの変更では、フローの分割、フローレットの集約、フローレットの予約済み帯域幅の変更といった動作が実行される。
【００６３】
これに加えて、フロー制御手段５１１０はデータ送信中に、上位層アプリケーションのデータトラフィックも制御する。上位層アプリケーションがデータトラフィックを予約された帯域幅よりも高速で送信する場合には、フロー制御手段５１１０は、上位層アプリケーションのデータをキャッシュして、中央管理装置５２０によって予約された帯域幅に基づいてそのデータを送信することができる。アプリケーション用として大きな帯域幅が予約されたために、一定時間が経過した後もデータ送信速度が予約された帯域幅に到達しなかった場合には、フロー制御手段５１１０は中央管理装置５２０に通知して、リソースの予約を変更するよう求めることができる。
【００６４】
アプリケーションが終了すると、フロー制御手段５１１０は中央管理装置５２０に通知して、対応するリソースの予約をキャンセルするよう求めることができる。
【００６５】
中央管理装置５２０のフロースケジューリング手段５２２０は、フロースケジューリング中には、すべてのリンクの帯域幅使用状況と、各ホストペアのすべての任意パスとを把握している必要がある。この理由から、帯域幅使用状況・パス情報テーブル記憶手段５２３０には、各ホストペアのすべての任意パスを保持するパステーブルと、すべてのフローレットについて、各々が属するフロー、各々が通過するパス、およびこれらのパスの予約された帯域幅を保持する帯域幅使用状況テーブルとが記憶されている。以下の表１および表２は、それぞれ、パステーブルと帯域幅使用テーブルの例を示す。
【表１】
【表２】
【００６６】
メディアストリーミング等の一部のアプリケーションでは、受信されたデータをその順序で保持する必要がある。しかし、データはホストで複数のフローレットに分割された後、複数の接続を介して送信されるので、データの順序は保証されない。そのため、受信側のホストは、データの再構築を実行する必要がある。
【００６７】
図８は、受信されたデータの再構築を可能にした、本発明の他の実施例による動的フローレットスケジューリングシステムを示すブロック図である。図８に示す動的フローレットスケジューリングシステム８０が、図５に示す動的フローレットスケジューリングシステム５０と異なる点は、動的フローレットスケジューリングシステム８０のホスト８１０がデータ再構築手段８１３０をさらに備えることと、中央管理装置８２０の帯域幅使用状況・パス情報テーブル記憶手段８２３０が、帯域幅使用状況・パス情報テーブル記憶手段５２３０とは異なる内容を記憶していることである。具体的には、本実施例においては、データ再構築手段８１３０は複数フローレットから受信したデータを構築し、帯域幅使用状況・パス情報テーブル記憶手段８２３０は、すべてのリンクの帯域幅使用状況、および各ホストペアのすべての任意パスだけでなく、ポート番号等のフローレット情報も記憶する。次に、図８に示す動的フローレットスケジューリングシステム８０の動作について、図９を参照しながら詳細に説明する。
【００６８】
図９は、本発明の一実施例による動的フローレットスケジューリングシステム８０の動作を示すフローチャートである。図９においては、ホストＡ、ホストＢ、ホストＣの各々は図８に示すホスト８１０を使用して実施し、中央管理装置は図８に示す中央管理装置８２０を使用して実施し、スイッチは図８に示すスイッチ８３０を使用して実施することができる。
【００６９】
図から分かるように、図９の動作１．１〜１．１１は図６のそれと同じなので、ここでは動作１．１〜１．１１の詳細な説明は省略する。図６と比較して、図９は、１．１２および１．１３という２つの動作をさらに備える。
【００７０】
宛先ホストＢが複数フローレットから受信したデータを再構築して、上位アプリケーションが元の順序でデータを受信できるようにするためには、データ再構築手段はどのフローレットが同じフローに属するかを把握している必要がある。そのため、中央管理装置はフローレット情報を宛先ホストＢに提供する（動作１．１２）。その後、宛先ホストＢは複数フローレットからデータを受信し、中央管理装置から提供されたフローレット情報に基づいて受信したデータを再構築する（動作１．１３）。
【００７１】
したがって、たとえデータが複数フローレットに分割され、複数の接続を介して送信されたとしても、動的フローレットスケジューリングシステム８０は受信したデータの順序を復元して、メディアストリーミング等の特定のアプリケーションの要件を満たすことができる。
【００７２】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも、上記実施の形態に限定されるものでなく、その技術的思想の範囲内において様々に変形して実施することができる。
【００７３】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【００７４】
（付記１）
送信元ホストからの特定フローの帯域幅要求を収集するように構成された帯域幅要求収集手段と、
リンクの帯域幅使用状況とホストペアの任意パスとを記憶するように構成された記憶手段と、
現在のリンクの帯域幅使用状況に基づいて、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当て、割り当てられたパスを送信元ホストに返し、かつ送信元ホストからフローレット情報を受信するように構成されたフロースケジューリング手段と、
前記フロースケジューリング手段のスケジューリング結果に基づいて、対応するスイッチを設定するように構成されたスイッチコントローラと
を備えることを特徴とする中央管理装置。
【００７５】
（付記２）
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計を計算し、前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるように構成されることを特徴とする付記１に記載の中央管理装置。
【００７６】
（付記３）
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記特定フローの任意パスをアイドル帯域幅の多い順に並び替え、選択したパスのアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上になるまで、前記並び替えた任意パスから１つのパスを順に選択するように構成されることを特徴とする付記２に記載の中央管理装置。
【００７７】
（付記４）
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求を下回る場合、前記特定フローの任意パスを通過する他のフローを検出し、当該他のフローの任意パスにおけるアイドル帯域幅の合計を計算し、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローを再スケジュールして、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるように構成されることを特徴とする付記２に記載の中央管理装置。
【００７８】
（付記５）
前記フロースケジューリング手段は、前記他のフローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替え、並び替えられたフローから１つのフローを順に選択し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、選択したフローを再スケジュールするように構成されることを特徴とする付記４に記載の中央管理装置。
【００７９】
（付記６）
前記フロースケジューリング手段は、前記他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、前記他のフローをそのアイドルパスへ再スケジュールし、前記特定フローの任意パスにおけるアイドル帯域幅を、前記特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ前記特定フローの任意パスを通過する残余フローとに割り当てるように構成されることを特徴とする付記４に記載の中央管理装置。
【００８０】
（付記７）
前記フロースケジューリング手段は、前記送信元ホストから受信されたフローレット情報を宛先ホストへ送信するように構成されることを特徴とする付記１に記載の中央管理装置。
【００８１】
（付記８）
前記記憶手段は、さらに、フローレット情報を記憶するように構成されることを特徴とする付記７に記載の中央管理装置。
【００８２】
（付記９）
前記フローレット情報は、フローレットのポート番号を含むことを特徴とする付記７又は付記８に記載の中央管理装置。
【００８３】
（付記１０）
送信元ホストからの特定フローの帯域幅要求を収集するステップと、
現在のリンクの帯域幅使用状況に基づいて、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるステップと、
割り当てられたパスを送信元ホストに返すステップと、送信元ホストからフローレット情報を受信するステップと、
スケジューリング結果に基づいて対応するスイッチを設定するステップと
を含むことを特徴とするフロースケジューリング方法。
【００８４】
（付記１１）
前記割り当てステップが、
前記特定フローの任意パスにおけるアイドル帯域幅の合計を計算し、
前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、当該特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てることを特徴とする付記１０に記載のフロースケジューリング方法。
【００８５】
（付記１２）
前記割り当てステップが、
前記特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、当該特定フローの任意パスがアイドル帯域幅の多い順に並び替え、選択したパスのアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、前記並び替えた任意パスから１つのパスを順に選択することを特徴とする付記１１に記載のフロースケジューリング方法。
【００８６】
（付記１３）
前記割り当てステップが、
前記特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、前記特定フローの任意パスを通過する他のフローを検出し、当該他のフローの任意パスにおけるアイドル帯域幅の合計を計算し、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローを再スケジュールし、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てることを特徴とする付記１１に記載のフロースケジューリング方法。
【００８７】
（付記１４）
前記割り当てステップが、
前記他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替え、並び替えたフローから１つのフローを順に選択し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、選択したフローを再スケジュールすることを特徴とする付記１３に記載のフロースケジューリング方法。
【００８８】
（付記１５）
前記割り当てステップが、
前記他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、前記他のフローをそのアイドルパスへ再スケジュールし、前記特定フローの任意パスにおけるアイドル帯域幅を、当該特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ当該特定フローの任意パスを通過する残余フローとに割り当てることを特徴とする付記１３に記載のフロースケジューリング方法。
【００８９】
（付記１６）
前記送信元ホストから受信されたフローレット情報を宛先ホストへ送信するステップをさらに含むことを特徴とする付記１０に記載のフロースケジューリング方法。
【００９０】
（付記１７）
前記フローレット情報はフローレットのポート番号を含むことを特徴とする付記１６に記載のフロースケジューリング方法。
【００９１】
（付記１８）
中央管理装置に特定フロー用の帯域幅を申請するように構成された帯域幅予約手段と、
前記中央管理装置から返されたスケジューリング結果に基づいて、当該特定フローを１つ以上のフローレットに分割し、中央管理装置によって割り当てられたパス上で１つ以上のフローレットを転送するための対応する接続を確立するように構成されたフロー制御手段と
を備えることを特徴とするホスト。
【００９２】
（付記１９）
前記フロー制御手段は、フローレットを変更するコマンドを前記中央管理装置から受信した場合、対応する接続を調整するように構成されることを特徴をとする付記１８に記載のホスト。
【００９３】
（付記２０）
１つ以上のフローレットを介して受信されたデータを再構築するように構成されたデータ再構築手段をさらに備えることを特徴とする付記１８又は付記１９に記載のホスト。
【符号の説明】
【００９４】
４１１０：転送テーブル
４１２０：パケット転送手段
４１３０：フロー統計報告手段
４２１０：スイッチコントローラ
４２２０：フロースケジューリング手段
４２３０：フロー要求予想手段
４２４０：フロー要求テーブル
４２５０：フロー統計収集手段
５１１０：フロー制御手段
５１２０：帯域幅予約手段
５２１０：スイッチコントローラ
５２２０：フロースケジューリング手段
５２３０：帯域幅使用状況・パス情報テーブル
５２４０：帯域幅要求収集手段
５３１０：転送テーブル
５３２０：パケット転送手段
８１１０：フロー制御手段
８１３０：データ再構築手段
８１２０：帯域幅予約手段
８２１０：スイッチコントローラ
８２２０：フロースケジューリング手段
８２３０：帯域幅使用状況・パス情報テーブル記憶手段
８２４０：帯域幅要求収集手段
８３１０：転送テーブル
８３２０：パケット転送手段
８３０：スイッチ
８０：動的フローレットスケジューリングシステム
【特許請求の範囲】
【請求項１】
送信元ホストからの特定フローの帯域幅要求を収集するように構成された帯域幅要求収集手段と、
リンクの帯域幅使用状況とホストペアの任意パスとを記憶するように構成された記憶手段と、
現在のリンクの帯域幅使用状況に基づいて、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当て、割り当てられたパスを送信元ホストに返し、かつ送信元ホストからフローレット情報を受信するように構成されたフロースケジューリング手段と、
前記フロースケジューリング手段のスケジューリング結果に基づいて、対応するスイッチを設定するように構成されたスイッチコントローラと
を備えることを特徴とする中央管理装置。
【請求項２】
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計を計算し、前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるように構成されることを特徴とする請求項１に記載の中央管理装置。
【請求項３】
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記特定フローの任意パスをアイドル帯域幅の多い順に並び替え、選択したパスのアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上になるまで、前記並び替えた任意パスから１つのパスを順に選択するように構成されることを特徴とする請求項２に記載の中央管理装置。
【請求項４】
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求を下回る場合、前記特定フローの任意パスを通過する他のフローを検出し、当該他のフローの任意パスにおけるアイドル帯域幅の合計を計算し、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローを再スケジュールして、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるように構成されることを特徴とする請求項２に記載の中央管理装置。
【請求項５】
前記フロースケジューリング手段は、前記他のフローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替え、並び替えられたフローから１つのフローを順に選択し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、選択したフローを再スケジュールするように構成されることを特徴とする請求項４に記載の中央管理装置。
【請求項６】
前記フロースケジューリング手段は、前記他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、前記他のフローをそのアイドルパスへ再スケジュールし、前記特定フローの任意パスにおけるアイドル帯域幅を、前記特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ前記特定フローの任意パスを通過する残余フローとに割り当てるように構成されることを特徴とする請求項４に記載の中央管理装置。
【請求項７】
前記フロースケジューリング手段は、前記送信元ホストから受信されたフローレット情報を宛先ホストへ送信するように構成されることを特徴とする請求項１に記載の中央管理装置。
【請求項８】
前記記憶手段は、さらに、フローレット情報を記憶するように構成されることを特徴とする請求項７に記載の中央管理装置。
【請求項９】
送信元ホストからの特定フローの帯域幅要求を収集するステップと、
現在のリンクの帯域幅使用状況に基づいて、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるステップと、
割り当てられたパスを送信元ホストに返すステップと、送信元ホストからフローレット情報を受信するステップと、
スケジューリング結果に基づいて対応するスイッチを設定するステップと
を含むことを特徴とするフロースケジューリング方法。
【請求項１０】
中央管理装置に特定フロー用の帯域幅を申請するように構成された帯域幅予約手段と、
前記中央管理装置から返されたスケジューリング結果に基づいて、当該特定フローを１つ以上のフローレットに分割し、中央管理装置によって割り当てられたパス上で１つ以上のフローレットを転送するための対応する接続を確立するように構成されたフロー制御手段と
を備えることを特徴とするホスト。
【請求項１】
送信元ホストからの特定フローの帯域幅要求を収集するように構成された帯域幅要求収集手段と、
リンクの帯域幅使用状況とホストペアの任意パスとを記憶するように構成された記憶手段と、
現在のリンクの帯域幅使用状況に基づいて、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当て、割り当てられたパスを送信元ホストに返し、かつ送信元ホストからフローレット情報を受信するように構成されたフロースケジューリング手段と、
前記フロースケジューリング手段のスケジューリング結果に基づいて、対応するスイッチを設定するように構成されたスイッチコントローラと
を備えることを特徴とする中央管理装置。
【請求項２】
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計を計算し、前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるように構成されることを特徴とする請求項１に記載の中央管理装置。
【請求項３】
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記特定フローの任意パスをアイドル帯域幅の多い順に並び替え、選択したパスのアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上になるまで、前記並び替えた任意パスから１つのパスを順に選択するように構成されることを特徴とする請求項２に記載の中央管理装置。
【請求項４】
前記フロースケジューリング手段は、前記特定フローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求を下回る場合、前記特定フローの任意パスを通過する他のフローを検出し、当該他のフローの任意パスにおけるアイドル帯域幅の合計を計算し、当該他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローを再スケジュールして、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるように構成されることを特徴とする請求項２に記載の中央管理装置。
【請求項５】
前記フロースケジューリング手段は、前記他のフローの任意パスにおけるアイドル帯域幅の合計が前記特定フローの帯域幅要求と同じかそれ以上の場合、前記他のフローをその任意パスにおけるアイドル帯域幅合計の多い順に並び替え、並び替えられたフローから１つのフローを順に選択し、当該特定フローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求と同じかそれ以上になるまで、選択したフローを再スケジュールするように構成されることを特徴とする請求項４に記載の中央管理装置。
【請求項６】
前記フロースケジューリング手段は、前記他のフローの任意パスにおけるアイドル帯域幅の合計が当該特定フローの帯域幅要求を下回る場合、前記他のフローをそのアイドルパスへ再スケジュールし、前記特定フローの任意パスにおけるアイドル帯域幅を、前記特定フローと、マキシミン公正原理に基づいた再スケジュール後にもまだ前記特定フローの任意パスを通過する残余フローとに割り当てるように構成されることを特徴とする請求項４に記載の中央管理装置。
【請求項７】
前記フロースケジューリング手段は、前記送信元ホストから受信されたフローレット情報を宛先ホストへ送信するように構成されることを特徴とする請求項１に記載の中央管理装置。
【請求項８】
前記記憶手段は、さらに、フローレット情報を記憶するように構成されることを特徴とする請求項７に記載の中央管理装置。
【請求項９】
送信元ホストからの特定フローの帯域幅要求を収集するステップと、
現在のリンクの帯域幅使用状況に基づいて、前記特定フローの任意パスから１つ以上のパスを前記特定フロー用として割り当てるステップと、
割り当てられたパスを送信元ホストに返すステップと、送信元ホストからフローレット情報を受信するステップと、
スケジューリング結果に基づいて対応するスイッチを設定するステップと
を含むことを特徴とするフロースケジューリング方法。
【請求項１０】
中央管理装置に特定フロー用の帯域幅を申請するように構成された帯域幅予約手段と、
前記中央管理装置から返されたスケジューリング結果に基づいて、当該特定フローを１つ以上のフローレットに分割し、中央管理装置によって割り当てられたパス上で１つ以上のフローレットを転送するための対応する接続を確立するように構成されたフロー制御手段と
を備えることを特徴とするホスト。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−２０９９２８（Ｐ２０１２−２０９９２８Ａ）
【公開日】平成２４年１０月２５日（２０１２．１０．２５）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２４４２４２（Ｐ２０１１−２４４２４２）
【出願日】平成２３年１１月８日（２０１１．１１．８）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２４年１０月２５日（２０１２．１０．２５）
【国際特許分類】
【出願番号】特願２０１１−２４４２４２（Ｐ２０１１−２４４２４２）
【出願日】平成２３年１１月８日（２０１１．１１．８）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]