トラヒック制御方法
【課題】複数のデータセンタが協調して、複数のデータセンタ間での負荷分散を実現するためのトラヒック制御方法を提供する。
【解決手段】各データセンタはリクエスト受け入れ制御装置を備えており、リクエストを受信したデータセンタのリクエスト受け入れ制御装置が、過去にリクエストを受け入れた際に蓄積した蓄積データを用いて、当該リクエストを受け入れるか否かを判定し、前記リクエストを受け入れないと判定した場合に、過去にリクエストを転送した際の蓄積データを用いて、転送先データセンタを決定し、当該転送先データセンタにリクエストを転送し、１回又は複数回のリクエスト転送が行われた後に、転送に係るリクエストを受信したリクエスト受け入れ制御装置が、前記リクエストを受け入れる場合に、トラヒックフローが確立した後のネットワーク状況を測定するとともに、当該ネットワーク状況と転送回数を転送元のリクエスト受け入れ制御装置に送信する。
【解決手段】各データセンタはリクエスト受け入れ制御装置を備えており、リクエストを受信したデータセンタのリクエスト受け入れ制御装置が、過去にリクエストを受け入れた際に蓄積した蓄積データを用いて、当該リクエストを受け入れるか否かを判定し、前記リクエストを受け入れないと判定した場合に、過去にリクエストを転送した際の蓄積データを用いて、転送先データセンタを決定し、当該転送先データセンタにリクエストを転送し、１回又は複数回のリクエスト転送が行われた後に、転送に係るリクエストを受信したリクエスト受け入れ制御装置が、前記リクエストを受け入れる場合に、トラヒックフローが確立した後のネットワーク状況を測定するとともに、当該ネットワーク状況と転送回数を転送元のリクエスト受け入れ制御装置に送信する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データセンタのトラヒック制御に関するものであり、特に、複数のデータセンタ間でトラヒックの負荷分散を行う技術に関するものである。
【背景技術】
【０００２】
クラウドコンピューティングの普及やトラフィックの増大に伴って、データセンタのマネジメントに関する研究が盛んに行われている。このような研究では、帯域使用率の向上や消費電力の削減に力点が置かれている（非特許文献１〜３）。中でも、帯域使用率の向上のためにデータセンタ内におけるTCPフローの制御技術が注目されている。TCPのフローを制御することにより、データセンタ内のネットワークで発生する輻輳を回避し、提供しているサービスの可用性を向上させることが可能になる。しかし、TCPフローは、バッチ処理を用いて複数のフローがまとめて制御されたり、アプリケーション層で制御されるため、フロー制御の粒度が荒く、ネットワークのスループット（帯域利用率・RTT）が悪化する問題がある（非特許文献４）。
【０００３】
そこで、近年、データセンタ特有の閉路なトポロジーを考慮したTCPフロー制御技術の発展やネットワーク機器の高機能化により、TCPフローのスループットを向上させるフロー制御方式が提案されるようになった（非特許文献５、６）。例えば、リクエストに対して、TCPフローを確立する際、複数のTCPフローに分割して、コンテンツを配信することにより、帯域利用率を向上させる手法が提案されている（非特許文献７）。また、B-cube やDCell などのデータセンタ構造では、アプリケーション層でフロー制御を行うことで、コンテンツのトレーサビリティの向上を目指している（非特許文献８、９）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】A. Greenberg, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. Maltz, P. Patel, and S. Sengupta, "VL2: A scalable and flexible data center network." Proc. ACM SIGCOMM, Aug. 2009.
【非特許文献２】R. Niranjan Mysore, et. al "Portland: a scalable fault-tolerant layer 2 data center network fabric." Proc. ACM SIGCOMM, Aug. 2009.
【非特許文献３】A. Greenberg, et.al "Networking The Cloud." Proc. The 29th Int'l Conference on Distributed Computing Systems (ICDCS 2009), June. 2009.
【非特許文献４】R. Griffith, Y. Chen, J. Liu, A. Joseph, and R. Katz, "Understanding TCP incast throughput collapse in data center networks." Proc. ACM SIGCOMM WREN Workshop, Aug. 2009.
【非特許文献５】M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan, "Dctcp: Efficient packet transport for the commoditized data center." Proc. ACM SIGCOMM, Aug. 2010.
【非特許文献６】C. Raiciu, C. Pluntke, S. Barre, A. Greenhalgh, D. Wischik, and M. Handley, "Data center networking with multipath TCP." Proc. ACM SIGCOMM Workshop Hotnets, Sept. 2010.
【非特許文献７】D. Wischik, C. Raiciu, A. Greenhalgh,and M. Handley, "Design, implementation and evaluation of congestion control for multipath TCP." USENIX on NSDI'11, Mar. 2011.
【非特許文献８】C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, "BCube: A high performance, server-centric network architecture for modular data centers." Proc. ACM SIGCOMM, Aug. 2009.
【非特許文献９】C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang, and S. Lu, "DCell: A scalable and fault-tolerant network structure for data centers." Proc. ACM SIGCOMM, Aug. 2008.
【非特許文献１０】K. Pawelzik, J. Kohlmorgen, and K. R. Muller, "Annealed competition of experts for a segmentation and classification of switching dynamics," Neural Computation, vol.8(2), pp. 340-356, 1996.
【非特許文献１１】M. Kodialam, T. V. Lakshman, J. B.Orlin, and S. Sengupta, "A Versatile Scheme for Routing Highly Variable Traffic in Service Overlays and IP Backbones." Proc. IEEE INFOCOM, 2006.
【非特許文献１２】A. Greenberg, P. Lahiri, D. A. Maltz, P. Patel, and S.~Sengupta, "Towards a next generation data center architecture: scalability and commercialization." Proc. Workshop on Programmable Routers for Extensible Services of Tomorrow, Aug.~2008.
【非特許文献１３】Moshe Babaioff and John Chuang, "On the Optimality and Interconnection of Valiant Load-Balancing Networks." Proc. IEEE INFOCOM, pp. 80-88, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
近年、サービスの耐故障性やスケーラビリティを考慮するため、複数データセンタの連携を通して、大規模なサービスを運用するようになってきた。複数のデータセンタが接続され、連携してサービスを提供するネットワークの構成例を図１に示す。図１の例では、３つのデータセンタA、B、Cがネットワーク接続されている。図１に示すように、各データセンタは、スイッチ、ルータ、サーバ等のノード（ネットワークコンポーネント）が互いに接続されて構成されている。
【０００６】
また、一般に各データセンタは階層構造を有しており、本明細書で対象とするデータセンタも階層構造を有するものを想定している。このようなデータセンタでは、階層の上位にアグリゲータ（aggregator)と呼ばれるプロキシ等の機能を有するノードが配置され、アグリゲータがサービスのリクエストを受信すると、リクエストを下位のノードに配信する動作や、リクエストに対応するTCPコネクションを確立する動作等を行う。
【０００７】
前述したような既存のデータセンタ内におけるフロー制御は、単一のデータセンタの帯域使用率の向上を期待することができるが、複数のデータセンタを用いてサービスを運用している場合には、必ずしもデータセンタ全体の帯域使用率を向上させることができないという問題がある。
【０００８】
複数のデータセンタ間で帯域使用率を向上させるためには、各データセンタ間でリソース情報などを統合管理し、ユーザ（ユーザ端末、ユーザネットワーク等、総称してユーザ装置と称してもよい）からのリクエストを効率的に各データセンタに配分しなければならない。しかし、複数のデータセンタのリソース状況を一元に管理することは、負荷分散を目的としてサービスを分散管理しているデータセンタの構造に相反する。
【０００９】
複数のデータセンタ間で負荷分散を行う従来技術として、Valiant Load Balancing(VLB) と呼ばれる手法を用いた負荷分散方法がある（例えば、非特許文献１３）。VLBは複数のデータセンタの運用において、ランダムにリクエストを転送することで、TCPフローが一定のデータセンタに集中しないようにすることで、輻輳を回避する。VLBにより、複数のデータセンタのスループットが充分に担保できる場合は、負荷分散の効果が見込める。しかしながら、複数のデータセンタが混雑してきた場合、ランダムにリクエストを転送し、TCPフローを確立するデータセンタを決定することは、必ずしも負荷を分散できるとは限らない。
【００１０】
本発明は上記の点に鑑みてなされたものであり、複数のデータセンタが協調することにより、複数のデータセンタ間での負荷分散を実現するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、本発明は、複数のデータセンタが接続されたネットワークシステムにおけるトラヒック制御方法であって、
前記複数のデータセンタの各データセンタはリクエスト受け入れ制御装置を備えており、
サービスのリクエストを受信したデータセンタのリクエスト受け入れ制御装置は、過去にリクエストを受け入れた際に取得したネットワーク状況に基づく第１の蓄積データを用いて、当該リクエストを受け入れるか否かを判定し、
前記リクエスト受け入れ制御装置が、前記リクエストを受け入れないと判定した場合に、過去にリクエストを転送した際に取得したネットワーク状況及びリクエスト転送回数に基づく第２の蓄積データを用いて、転送先データセンタを決定し、当該転送先データセンタにリクエストを転送し、
１回又は複数回のリクエスト転送が行われた後に、転送に係るリクエストを受信したリクエスト受け入れ制御装置が、前記リクエストを受け入れる場合に、当該リクエストに対応するサービスのトラヒックフローが確立した後のネットワーク状況を測定するとともに、当該ネットワーク状況とリクエスト転送回数を転送元のリクエスト受け入れ制御装置に送信し、前記転送元のリクエスト受け入れ制御装置が、前記ネットワーク状況とリクエスト転送回数を受信する、ことを特徴とするトラヒック制御方法として構成される。
【００１２】
前記複数のデータセンタにおける各リクエスト受け入れ制御装置は、第１の学習器と第２の学習器を備えており、前記第１の学習器が、リクエストを受け入れた際に測定されたネットワーク状況、及び当該リクエストに対応するサービスの優先度を用いて、当該リクエストを受け入れたことについての学習を行い、学習結果を前記第１の蓄積データとして記憶手段に蓄積し、前記第２の学習器が、転送したリクエストを受け入れた他のリクエスト受け入れ制御装置から受信した当該他のリクエスト受け入れ制御装置により取得されたネットワーク状況及び転送回数を用いて、当該リクエストを転送したことについての学習を行い、学習結果を前記第２の蓄積データとして記憶手段に蓄積するように前記トラヒック制御方法を構成してもよい。
【００１３】
また、前記第１の学習器と前記第２の学習器を備えるリクエスト受け入れ制御装置が、サービスのリクエストを受信した際に、前記第１の学習器が、前記第１の蓄積データである学習結果に基づいて、受信した前記リクエストを受け入れるか否かの判定を行い、前記第１の学習器が、前記リクエストを受け入れないと判定した場合に、前記第２の学習器が、前記第２の蓄積データである学習結果に基づいて、転送先データセンタを決定するように前記トラヒック制御方法を構成してもよい。
【００１４】
また、前記第１の学習器は、リクエストを受け入れた場合に、当該リクエストに係るサービスの優先度が高く、ネットワーク状況が良好な場合において、当該リクエストを受け入れた行動に対する報酬値が高くなるように報酬値の計算を行い、前記第２の学習器は、リクエストを転送した場合に、転送回数が少なく、リクエストを受け入れたデータセンタでのネットワーク状況が良好な場合において、当該リクエストを転送した行動に対する報酬値が高くなるように報酬値の計算を行うように前記トラヒック制御方法を構成してもよい。
【発明の効果】
【００１５】
本発明によれば、複数のデータセンタが協調することにより、複数のデータセンタ間での負荷分散を実現するための技術を提供することが可能となる。すなわち、各データセンタの分散構造を維持しつつ、特定のデータセンタに負荷が集中することを防いだ負荷分散を実現できる。
【図面の簡単な説明】
【００１６】
【図１】複数データセンタの連携構造の例を示す図である。
【図２】リクエスト受け入れ制御装置１０の機能構成図である。
【図３】システムの動作概要を説明するための図である。
【図４】システムの動作の具体例を説明するための図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例であり、本発明の実施の形態は以下に記述した形態に限られるものではない。また、以下で説明するデータセンタは、エンタープライズネットワークであってもよい。
【００１８】
（システム構成及び動作の概要）
本実施の形態に係るシステムの全体構成は、図１に示したように複数データセンタがネットワーク接続された構成である。そして、各データセンタには、リクエスト受け入れ制御装置１０が備えられ、複数データセンタのリクエスト受け入れ制御装置１０が協調してフロー制御（トラヒック制御）を行う。
【００１９】
ここで、本実施の形態における「サービス」は、特定のサービスに限定されないが、一例を挙げれば、動画配信等のコンテンツ提供サービス、検索サービス等がある。「リクエスト」は、例えば、コンテンツ要求、検索クエリー等である。
【００２０】
図２に、各データセンタに備えられるリクエスト受け入れ制御装置１０の機能構成図を示す。図２に示すように、リクエスト受け入れ制御装置１０は、リクエスト転送処理部１１、リクエスト受け入れ判定部１２、リクエスト転送先決定部１３、及びデータ格納部１４を備える。
【００２１】
本実施の形態では、データセンタにおいてアグリゲータとなるノードをリクエスト受け入れ制御装置１０とすることを想定しており、リクエスト転送処理部１１は、当該アグリゲータの機能（例えば、SSHやProxy等の機能）を備え、リクエストの転送処理やコネクション確立のための処理等を行う。
リクエスト受け入れ判定部１２は、リクエスト転送処理部１１から受け取ったリクエストを受け入れるか否か判定し、受け入れる場合にリクエスト転送処理部１１にリクエスト受け入れ処理（コネクション確立等）を行わせるとともに後述する学習を行い、受け入れない場合に、リクエストをリクエスト転送先決定部１３に渡す機能を有する。リクエスト転送先決定部１３は、リクエスト受け入れ判定部１２により受け入れを拒否されたリクエストの転送先を決定し、リクエスト転送処理部１１を介して当該転送先にリクエストを転送し、後述する学習を行う機能を有する。
【００２２】
本実施の形態では、各データセンタにおけるリクエスト受け入れ制御装置１０のリクエスト受け入れ判定部１２及びリクエスト転送先決定部１３は、それぞれ学習器１２２、１３２を備え、これらにより階層型強化学習を行うことで、データセンタ間のフロー制御を行っている。また、リクエスト受け入れ判定部１２及びリクエスト転送先決定部１３がそれぞれ備える学習用データ取得部１２１、１３１により、学習のために使用するデータ（ネットワーク状況や転送回数等）が取得され、データ格納部１４に格納される。データ格納部１４は、学習のために必要な種々のデータを格納する機能部である。なお、リクエスト受け入れ判定部１２とリクエスト転送先決定部１３における各学習器の処理内容については、後の詳細説明のところでより詳細に説明する。
【００２３】
本実施の形態に係るリクエスト受け入れ制御装置１０は、CPU、記憶装置等からなるコンピュータ（コンピュータの機能を備える通信装置等を含む）に、リクエスト受け入れ制御装置１０の各機能部の機能を実現するためのプログラムを実行させることにより実現できる。当該プログラムは可搬メモリ等の記録媒体からコンピュータにインストールすることとしてもよいし、ネットワーク上のサーバからダウンロードすることとしてもよい。また、リクエスト受け入れ判定部１２とリクエスト転送先決定部１３をハードウェア回路として構成し、アグリゲータ機能を有する装置に組み込むことによりリクエスト受け入れ制御装置１０を実現してもよい。
【００２４】
図３を参照してシステムの動作の概要を説明する。図３の例では、ノードP（アグリゲータノード）がリクエスト受け入れ制御装置１０であるものとする。
【００２５】
図３に示すように、時刻t にて、ユーザからのサービス1 に対するリクエストが、データセンタAに対して送信されてきた場合、まずノードPのリクエスト受け入れ判定部１２は、リクエストの受け入れの可否を決定する。この時、ノードPは学習を行っておらず、一旦、当該リクエストを受け入れ、サービスの優先度に応じたフローを確立し、TCPのスループットの状態（RTT等）を計測し、計測結果を用いて、「受け入れる」という行動に対して学習器１２２が評価を行う。
【００２６】
なお、ネットワーク状況としてのスループットの計測はどのような手法を用いて行ってもよい。例えば、学習用データ取得部１２１が計測機能を備えることにより計測を行ってもよいし、ノードP内の他の機能部が計測を行って、計測結果を学習用データ取得部１２１に渡してもよいし、ノードPの外部にある計測装置が計測を行って、計測結果を学習用データ取得部１２１に渡してもよい。フロー数の計測等についても同様である。
【００２７】
時間a後に、同じ状態遷移が発生した場合、ノードPのリクエスト受け入れ判定部１２は、過去の経験（蓄積した学習結果）に基づいて、リクエストを他のデータセンタに転送するかどうかを判断する。図３の例では、リクエストを受け入れず、リクエスト転送先決定部１３によりリクエストをデータセンタBに転送し、データセンタBから、スループットが高い状態で当該リクエストを受け入れることができたという情報を得る。この時、ノードP（リクエスト転送先決定部１３の学習用データ取得部１２１）では、当該情報や「Bに転送する」という状態遷移を記録する。
【００２８】
本実施の形態では、各データセンタにおけるリクエスト受け入れ制御装置１０は、これらのプロセスを通して最適な状態遷移を学習する。最適な状態遷移が確立されることで、複数のデータセンタが連携して輻輳を抑え、サービスの差別化を達成することができるフロー制御が可能になる。
【００２９】
（処理の詳細）
以下では、本実施の形態に係るシステムの処理内容をより詳細に説明する。
【００３０】
まず、本実施の形態における複数データセンタの運用モデルを示し、運用モデルに基づいた階層型強化学習法を説明する。以下で説明する学習に用いる各種パラメータはデータ格納部１４に格納され、システム管理者等により適宜変更可能である。
【００３１】
＜複数データセンタの運用モデル＞
本実施の形態に係る複数データセンタの運用モデルは以下のとおりである。
・データセンタの数をM とし、提供しているサービスの数をNとし、データセンタk(0≦k≦M)は全てのサービスNを運用している事とする。
・1≦i≦j≦Nの時、サービスiはサービスjよりも優先度が高い。
・データセンタk(0≦k≦M)は、時刻tにおいて収容している全てのフロー数Lkall(t)とサービス別のフロー数Lki(t)(1≦i≦N)をデータ格納部１４に記録している。
・データセンタk における、サービスiの最大フロー数をLmkiとする。
・優先度が高いサービスほど、多くのフローを受け入れることができ、1≦i≦j≦Nの時、Lmj≦Lmiを満たす。
・データセンタkは、他の全てのM−1個のデータセンタと接続されている。
・セッション要求の到着過程・到着率とサービス時間分布・平均時間には特定の仮定を置かずに未知とする。
【００３２】
＜階層型強化学習＞
階層型強化学習では、複数の学習器を用いて階層化することで、複数の目的を達成することが可能になる。本実施の形態では、サービスの優先度と帯域使用率を考慮した負荷分散を達成するために、サービスの優先度に応じた学習器１２２と帯域使用率を考慮した学習器１３２の２つの学習器を各データセンタのリクエスト受け入れ制御装置１０に配置し、サービスの優先度に応じた学習器１２２と帯域使用率を考慮した学習器１３２を連携させる。なお、本実施の形態では各学習器はQ-learningによって学習することとするが、本発明に適用可能な学習の手法はQ-learningに限られるわけではない。
【００３３】
――――― Q-learning ―――――
Q-learningで代表される強化学習では、学習エージェントが現在の状態を観測し、行動を通して得られる報酬が最大になるように、各状態における最適行動を学習する。
【００３４】
今、時刻tでエージェントがいる状態をstとし、stでエージェントがとる行動をatとする。さらに、行動atにより得られる報酬を
【００３５】
【数１】
とする。状態stからst+1に行動atを通して遷移した時、stとatに対するQ値Q(st, at) は以下のように更新される。
【００３６】
【数２】
ここで、α(0 <α≦1) は学習率を示し、γ(0 <γ≦1) は割引率を示している。αが大きい場合には最新の報酬を重視し、αが１の場合には、過去の報酬を全く考慮しない。また、γは遷移先の状態に対するQ値が現在のQ値に与える影響を表し、γが0 の時は遷移先の状態st+1に対するQ値が現在の状態stのQ値に依存しない。本実施の形態では、α及びγを予め決めておき、データ格納部１４に格納しておく。また、学習結果もデータ格納部１４に格納する。
【００３７】
――――― 各学習器の状態集合と行動集合 ―――――
時刻tにおける、各学習器のエージェントが観測する状態を以下のように定義する。なお、各定義に係る情報は、データ格納部１４に格納される。また、各データセンタは自分及び他のデータセンタのフローを計測しているものとする。各データセンタにおける自分及び他のデータセンタのフローの計測の方法は特定の方法に限定されない。リクエスト受け入れ制御装置１０が自分及び他のデータセンタのフローの情報を取得できる方法であればどのような方法でもよい。リクエスト受け入れ制御装置１０は、自分及び他のデータセンタのフローの情報を取得し、データ格納部１４に格納する機能を備えているものとする。
【００３８】
【数３】
【００３９】
【数４】
ここで、式（２）のsfk(t)は、時刻tにおいて、データセンタkが観測している、他のデータセンタの収容しているフロー数を示している。また、式（３）のspk(t)は、データセンタkのサービス別の収容フロー数を示している。すなわち、Lk1はサービス1の収容フロー数を示しており、Lkallは全てのサービスの収容フロー数の和(ΣNi=1Lki) を示している。なお、サービスiはサービスk(1≦i≦k≦N) よりも優先度が高いとする。
【００４０】
次に、時刻tにおけるエージェントがとりうる行動を定義する。リクエスト受け入れ判定部１２が備える、優先度に基づいたサービスの差別化を行う学習器１２２では以下のように行動を定義する。以下のどの定義がどのデータセンタに適用されるかは、予め定めておくものである。
・サービスi(1≦i≦N) のフローのみ受け入れる。
・サービスiおよびj(1≦j≦N)のフローのみ受け入れる。
・m(2≦m≦N)個のサービスに対するフローを受け入れる。
・全てのサービスのフローを受け入れる。
【００４１】
上記の定義において、「サービスi(1≦i≦N) のフローのみ受け入れる。」は、特定のサービスを定めておき、その特定のサービスのリクエストであれば受け入れ可能、という意味であり、「サービスiおよびj(1≦j≦N)のフローのみ受け入れる。」は、２つの特定のサービスを定めておき、その２つの特定のサービスのうちいずれかであれば受け入れ可能、という意味であり、「m(2≦m≦N)個のサービスに対するフローを受け入れる。」は、ｍ個の特定のサービスを定めておき、そのうちのいずれかであれば受け入れ可能、という意味であり、「全てのサービスのフローを受け入れる。」は、いずれのサービスも受け入れ可能、という意味である。
【００４２】
なお、実際にリクエストを受け入れるかどうかは、学習器での行動選択法（本実施の形態では後述するsoft-max法）に基づく。本実施の形態のように、サービス数がＮの時、本学習器１２２における行動数はＮとなる。
【００４３】
次に、リクエスト転送先決定部１３が備える、データセンタの帯域使用率を考慮した学習器１３２の行動を定義する。本学習器１３２は、サービスの差別化を行う学習器１２２の行動が発生した後に動作するものとする。
・リクエストを他のデータセンタに転送する。
【００４４】
データセンタ数がM個の時、データセンタiの、本学習器における行動数はM−1となる。
【００４５】
これらの学習器は階層構造を持ち、ユーザからのリクエストに応じて階層的に連続して学習を行う。まず、ユーザからのリクエストがデータセンタiに到達する場合を考える。まず、データセンタi のサービスの差別化を行う学習器１２２によってデータセンタiでの当該リクエストの受け入れの可否を決定する。受け入れが可決された場合、当該リクエストを送信したユーザに対してのフローを確立する。リクエストが拒否された場合、帯域使用率を考慮した学習器１３２によって受け入れが可能なデータセンタを模索し、リクエストを転送する。
【００４６】
なお、本実施の形態において、各学習器の行動選択にはsoft-max法を用いる（非特許文献１０）。ただし、行動選択の方法はsoft-max法に限られるわけではない。soft-max 法によって、行動pが選択される確率は、以下の式（４）に従う。以下の式（４）のΣにおけるＮ｜Ｍ−１はＮ or Ｍ−１の意味であり、サービスの差別化を行う学習器１２２についてはＮ（サービスの数）をとり、もう一方の学習器１３２についてはデータセンタの数Ｍから１を引いたＭ−１をとることを意味する。
【００４７】
【数５】
式（４）では、各行動の価値Qk(p) の大きさに応じて行動が選択される。つまり、各学習器は、リクエストに対する行動を選択する際に、soft-max 法で算出された確率に基づいて行動を選択する（リクエストを受け入れるか否か、どのデータセンタに転送するか、等）。
【００４８】
――――― 報酬関数 ―――――
ユーザからのリクエストがデータセンタkに到達し、２つの学習器によってリクエストを処理した時に発生する報酬を定義する。サービスの差別化を行う学習器１２２によってリクエストの受け入れが許可された場合、リクエストが指定するサービスの種類に応じて以下の優先度係数が考慮される。以下の優先度係数は、データ格納部１４に予め格納されているデータである。
【００４９】
【数６】
式（５）では、高優先のサービスへのフローを優先的に確立することで、より多くの報酬を獲得できる。ここでriを用いて、サービスの差別化を行う学習器１２２が状態spk(t) からspk(t +1)に行動ak(t)で遷移した際の報酬関数
【００５０】
【数７】
を以下の式（６）で与える。なお、式（６）でのSTkiはデータセンタkにおける、サービスiのTCPフローの最短応答時間(Shortest RTT)を示し、RTkiはサービスiのフローを確立した際の応答時間(RTT) を示す。さらに、Lossはパケットロス率を示す。なお、ここでのRTTやパケットロス率はデータセンタ内（アグリゲータとサーバ間等）でのものであるが、これに限られるわけではない。また、下記のΣは、新たに受けたリクエストで確立された新たなフローのRTTやパケットロス率等を測定するとともに、既に確立されているフローについてのその時点でのRTTやパケットロス率等も測定して、下記の式に基づき加え合わせることを意味している。
【００５１】
【数８】
式（６）から、新たに確立されたフローの優先度が高く、確立したフローのRTTが最も短いRTTに近く、パケットロス率が低い場合において、学習エージェントは高い報酬値を得ることができ、式（１）に示したようにQ値が大きくなるので、当該フローの受け入れ確率が向上する。もし、新たなフローを確立した際に輻輳が発生し、パケットロス率やRTTが急激に遅くなった場合、エージェントが獲得できる報酬値が小さくなり、新たなフローを受け入れる確率が減少する。なお、上記の例では、ネットワーク状況としてスループットの状態であるshortest RTT、RTT、Lossを用いているが、ネットワーク状況に関するデータはこれらに限られるわけではない、ネットワーク状況を表せるパラメータであれば上記以外のものを用いてもよい。
【００５２】
次に、帯域使用率を考慮する学習器１３２の報酬関数を以下に示す。なお、式（７）において、transfer は、リクエストを転送した結果、最終的にリクエストを受け入れたデータセンタまでの転送回数(ホップ数) を示す。
【００５３】
【数９】
式（７）では、サービスの差別化を行う学習器１２２によって棄却されたリクエストを他のデータセンタに転送した際に、転送回数と転送先の輻輳状況によってエージェントが獲得できる報酬が決定される。つまり、転送回数が少なく、輻輳の可能性が低いデータセンタに転送するほど、エージェントは高い報酬を獲得することができる。つまり、当該データセンタに転送するという行動のQ値が高くなり、当該データセンタに転送される確率が高くなる。
【００５４】
最終的にエージェントは、 サービスの差別化を行う学習器１２２にて、できるだけ輻輳が発生しないように優先度が高いフローを優先的に確立し、帯域使用率を考慮する学習器１３２にて、データセンタ間で負荷分散を達成するフロー制御が可能になる。
【００５５】
（動作の具体例）
次に、図４に示すように、データセンタA、B、Cが接続されたシステム構成を例に挙げて、動作の具体例を説明する。図４に示すTransfer_numは、帯域使用率を考慮する学習器１３２の報酬関数におけるtransferに対応する。
【００５６】
まず、データセンタAにあるサービスに対するリクエストが到達するとする。データセンタAのリクエスト転送処理部１１（Ａ）は、当該リクエストの受け入れの可否を決定するリクエスト受け入れ判定部１２（Ａ）に対して、リクエストを転送する。この時、リクエスト受け入れ判定部１２（Ａ）がリクエストの受け入れを拒否すると、当該リクエストをリクエスト転送先決定部１３（Ａ）に転送し、リクエスト転送先決定部１３（Ａ）がリクエストの受け入れが可能なデータセンタを探し、データセンタB に転送することにする。この時、Transfer_numのパラメータを１とし、パラメータもリクエストに付随して転送する。
【００５７】
転送されたリクエストがデータセンタBに到達し、データセンタAと同様に、リクエスト受け入れ判定部１２（Ｂ）が当該リクエストの受け入れを拒否し、リクエスト転送先決定部１３（Ｂ）が当該リクエストをデータセンタA 以外のデータセンタCに転送するとする。この時、リクエスト転送先決定部１３（Ｂ）は、Transfer_numのパラメータを２とし、パラメータもリクエストに付随して転送する。
【００５８】
転送されたリクエストがデータセンタC に到達し、データセンタCのリクエスト受け入れ判定部１２（Ｃ）が当該リクエストの受け入れを許可することにする。リクエストの受け入れが許可され、TCPフローが確立されると同時に、リクエスト受け入れ判定部１２（Ｃ）は当該フローのデータセンタCにおけるスループットに関する情報（例えば、shortest RTT、RTT、Loss等）を計測もしくは取得する。なお、データセンタのスループットは、例えば、階層的なデータセンタの構造を利用して、ボトムアップで各ネットワークコンポネント（ルータ、スイッチ、サーバ、etc）のリソース状況を集約する方法を用いて計測することができるが、計測方法はこの方法に限られない。計測後、リクエスト受け入れ判定部１２（Ｃ）はデータセンタAのリクエスト受け入れ判定部１２（A）に対して、転送されてきたリクエストを受け入れた結果として、Transfer_numと計測したスループットを伝える。また、リクエスト受け入れ判定部１２（C）は、このリクエストを受け入れたという行動に対して学習（報酬計算、Q値更新等）を行い、学習結果をデータ格納部１４（Ｃ）に格納する。
【００５９】
データセンタAのリクエスト受け入れ判定部１２（A）は、データセンタC から送られてきた、転送リクエストの転送回数とスループットをリクエスト転送先決定部１３（A）に転送し、リクエスト転送先決定部１３（A）は、データセンタBに転送するという行動に対して学習（報酬計算、Q値更新等）を行い、学習結果をデータ格納部１４（A）に格納する。
【００６０】
これらのプロセスを通して、データセンタAは、各データセンタのリソース状況を学習し、転送回数が少なく、スループットが高い転送先を発見できるようになる。
【００６１】
また、各データセンタで、受け入れの可否をサービスの優先度別に決定することにより、サービスの優先度に応じた、サービスの差別化を達成することができる。
【００６２】
（実施の形態のまとめ、効果）
本実施の形態によれば、複数のデータセンタやが、ネットワーク（インターネット）を通して相互接続された環境において、各データセンタのTCP を管理できる機器（リクエスト受け入れ制御装置等）にて、前記環境下でのTCPフローの解析と制御を自律的に行うネットワーク管理システムが提供される。前記各TCP を管理できる機器は、相互接続されている、異なるデータセンタネットワークのTCP を管理可能な機器との協調動作を通して、互いにTCP のスループットの状態を計測する機能と、当該TCP を管理できる機器に対して、あるサービスへのリクエストが送られてきた場合、サービスの種別データ（優先度）と蓄積した計測結果を用いた、複数のパラメータによって動作が決定される学習アルゴリズムを通して、リクエストの送信元（ユーザ）に対して、当該TCP を管理できる機器より、TCPフローを確立するかどうかを判断する機能と、当該TCPを管理できる機器において、前記の判断機能を通して、リクエストに対するTCP フローの確立が不可能と判断した際に、相互接続されている、他のデータセンタのTCPを管理できる機器から、TCPフローを確立した際にスループットを最大化できるTCPを管理できる機器を、サービスの種別データ（優先度）と蓄積した計測結果を用いた、複数のパラメータによって動作が決定される学習アルゴリズムを通して決定し、転送する機能を有している。
【００６３】
より詳細には、本実施の形態では、ユーザからの接続頻度と接続時間の周期性を考慮した階層型強化学習のモデルを利用することでフローの確立やリクエストの転送を決定する。階層型強化学習は、データセンタ間で帯域の使用率を考慮し、負荷分散を達成する学習器と各データセンタにてサービスの差別化を図る学習器を階層的に連携させることで学習を行う。
【００６４】
これらの学習器を階層化することで、単一の学習器を用いた場合よりも、学習を高速に進めることができる。さらに、各データセンタの分散構造を維持しつつ、複数のデータセンタを統一的に管理することが可能になる。学習が進むことで、ユーザの接続特性に学習が適応していくため、特定のデータセンタに負荷が集中することを防ぎ、サービスの優先度に基づいたフロー制御をすることが可能になる。
【００６５】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００６６】
１０ リクエスト受け入れ制御装置
１１ リクエスト転送処理部
１２ リクエスト受け入れ判定部
１３ リクエスト転送先決定部
１４ データ格納部
１２１、１３１ 学習用データ取得部
１２２、１３２ 学習器
【技術分野】
【０００１】
本発明は、データセンタのトラヒック制御に関するものであり、特に、複数のデータセンタ間でトラヒックの負荷分散を行う技術に関するものである。
【背景技術】
【０００２】
クラウドコンピューティングの普及やトラフィックの増大に伴って、データセンタのマネジメントに関する研究が盛んに行われている。このような研究では、帯域使用率の向上や消費電力の削減に力点が置かれている（非特許文献１〜３）。中でも、帯域使用率の向上のためにデータセンタ内におけるTCPフローの制御技術が注目されている。TCPのフローを制御することにより、データセンタ内のネットワークで発生する輻輳を回避し、提供しているサービスの可用性を向上させることが可能になる。しかし、TCPフローは、バッチ処理を用いて複数のフローがまとめて制御されたり、アプリケーション層で制御されるため、フロー制御の粒度が荒く、ネットワークのスループット（帯域利用率・RTT）が悪化する問題がある（非特許文献４）。
【０００３】
そこで、近年、データセンタ特有の閉路なトポロジーを考慮したTCPフロー制御技術の発展やネットワーク機器の高機能化により、TCPフローのスループットを向上させるフロー制御方式が提案されるようになった（非特許文献５、６）。例えば、リクエストに対して、TCPフローを確立する際、複数のTCPフローに分割して、コンテンツを配信することにより、帯域利用率を向上させる手法が提案されている（非特許文献７）。また、B-cube やDCell などのデータセンタ構造では、アプリケーション層でフロー制御を行うことで、コンテンツのトレーサビリティの向上を目指している（非特許文献８、９）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】A. Greenberg, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. Maltz, P. Patel, and S. Sengupta, "VL2: A scalable and flexible data center network." Proc. ACM SIGCOMM, Aug. 2009.
【非特許文献２】R. Niranjan Mysore, et. al "Portland: a scalable fault-tolerant layer 2 data center network fabric." Proc. ACM SIGCOMM, Aug. 2009.
【非特許文献３】A. Greenberg, et.al "Networking The Cloud." Proc. The 29th Int'l Conference on Distributed Computing Systems (ICDCS 2009), June. 2009.
【非特許文献４】R. Griffith, Y. Chen, J. Liu, A. Joseph, and R. Katz, "Understanding TCP incast throughput collapse in data center networks." Proc. ACM SIGCOMM WREN Workshop, Aug. 2009.
【非特許文献５】M. Alizadeh, A. Greenberg, D. A. Maltz, J. Padhye, P. Patel, B. Prabhakar, S. Sengupta, and M. Sridharan, "Dctcp: Efficient packet transport for the commoditized data center." Proc. ACM SIGCOMM, Aug. 2010.
【非特許文献６】C. Raiciu, C. Pluntke, S. Barre, A. Greenhalgh, D. Wischik, and M. Handley, "Data center networking with multipath TCP." Proc. ACM SIGCOMM Workshop Hotnets, Sept. 2010.
【非特許文献７】D. Wischik, C. Raiciu, A. Greenhalgh,and M. Handley, "Design, implementation and evaluation of congestion control for multipath TCP." USENIX on NSDI'11, Mar. 2011.
【非特許文献８】C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu, "BCube: A high performance, server-centric network architecture for modular data centers." Proc. ACM SIGCOMM, Aug. 2009.
【非特許文献９】C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang, and S. Lu, "DCell: A scalable and fault-tolerant network structure for data centers." Proc. ACM SIGCOMM, Aug. 2008.
【非特許文献１０】K. Pawelzik, J. Kohlmorgen, and K. R. Muller, "Annealed competition of experts for a segmentation and classification of switching dynamics," Neural Computation, vol.8(2), pp. 340-356, 1996.
【非特許文献１１】M. Kodialam, T. V. Lakshman, J. B.Orlin, and S. Sengupta, "A Versatile Scheme for Routing Highly Variable Traffic in Service Overlays and IP Backbones." Proc. IEEE INFOCOM, 2006.
【非特許文献１２】A. Greenberg, P. Lahiri, D. A. Maltz, P. Patel, and S.~Sengupta, "Towards a next generation data center architecture: scalability and commercialization." Proc. Workshop on Programmable Routers for Extensible Services of Tomorrow, Aug.~2008.
【非特許文献１３】Moshe Babaioff and John Chuang, "On the Optimality and Interconnection of Valiant Load-Balancing Networks." Proc. IEEE INFOCOM, pp. 80-88, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
近年、サービスの耐故障性やスケーラビリティを考慮するため、複数データセンタの連携を通して、大規模なサービスを運用するようになってきた。複数のデータセンタが接続され、連携してサービスを提供するネットワークの構成例を図１に示す。図１の例では、３つのデータセンタA、B、Cがネットワーク接続されている。図１に示すように、各データセンタは、スイッチ、ルータ、サーバ等のノード（ネットワークコンポーネント）が互いに接続されて構成されている。
【０００６】
また、一般に各データセンタは階層構造を有しており、本明細書で対象とするデータセンタも階層構造を有するものを想定している。このようなデータセンタでは、階層の上位にアグリゲータ（aggregator)と呼ばれるプロキシ等の機能を有するノードが配置され、アグリゲータがサービスのリクエストを受信すると、リクエストを下位のノードに配信する動作や、リクエストに対応するTCPコネクションを確立する動作等を行う。
【０００７】
前述したような既存のデータセンタ内におけるフロー制御は、単一のデータセンタの帯域使用率の向上を期待することができるが、複数のデータセンタを用いてサービスを運用している場合には、必ずしもデータセンタ全体の帯域使用率を向上させることができないという問題がある。
【０００８】
複数のデータセンタ間で帯域使用率を向上させるためには、各データセンタ間でリソース情報などを統合管理し、ユーザ（ユーザ端末、ユーザネットワーク等、総称してユーザ装置と称してもよい）からのリクエストを効率的に各データセンタに配分しなければならない。しかし、複数のデータセンタのリソース状況を一元に管理することは、負荷分散を目的としてサービスを分散管理しているデータセンタの構造に相反する。
【０００９】
複数のデータセンタ間で負荷分散を行う従来技術として、Valiant Load Balancing(VLB) と呼ばれる手法を用いた負荷分散方法がある（例えば、非特許文献１３）。VLBは複数のデータセンタの運用において、ランダムにリクエストを転送することで、TCPフローが一定のデータセンタに集中しないようにすることで、輻輳を回避する。VLBにより、複数のデータセンタのスループットが充分に担保できる場合は、負荷分散の効果が見込める。しかしながら、複数のデータセンタが混雑してきた場合、ランダムにリクエストを転送し、TCPフローを確立するデータセンタを決定することは、必ずしも負荷を分散できるとは限らない。
【００１０】
本発明は上記の点に鑑みてなされたものであり、複数のデータセンタが協調することにより、複数のデータセンタ間での負荷分散を実現するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、本発明は、複数のデータセンタが接続されたネットワークシステムにおけるトラヒック制御方法であって、
前記複数のデータセンタの各データセンタはリクエスト受け入れ制御装置を備えており、
サービスのリクエストを受信したデータセンタのリクエスト受け入れ制御装置は、過去にリクエストを受け入れた際に取得したネットワーク状況に基づく第１の蓄積データを用いて、当該リクエストを受け入れるか否かを判定し、
前記リクエスト受け入れ制御装置が、前記リクエストを受け入れないと判定した場合に、過去にリクエストを転送した際に取得したネットワーク状況及びリクエスト転送回数に基づく第２の蓄積データを用いて、転送先データセンタを決定し、当該転送先データセンタにリクエストを転送し、
１回又は複数回のリクエスト転送が行われた後に、転送に係るリクエストを受信したリクエスト受け入れ制御装置が、前記リクエストを受け入れる場合に、当該リクエストに対応するサービスのトラヒックフローが確立した後のネットワーク状況を測定するとともに、当該ネットワーク状況とリクエスト転送回数を転送元のリクエスト受け入れ制御装置に送信し、前記転送元のリクエスト受け入れ制御装置が、前記ネットワーク状況とリクエスト転送回数を受信する、ことを特徴とするトラヒック制御方法として構成される。
【００１２】
前記複数のデータセンタにおける各リクエスト受け入れ制御装置は、第１の学習器と第２の学習器を備えており、前記第１の学習器が、リクエストを受け入れた際に測定されたネットワーク状況、及び当該リクエストに対応するサービスの優先度を用いて、当該リクエストを受け入れたことについての学習を行い、学習結果を前記第１の蓄積データとして記憶手段に蓄積し、前記第２の学習器が、転送したリクエストを受け入れた他のリクエスト受け入れ制御装置から受信した当該他のリクエスト受け入れ制御装置により取得されたネットワーク状況及び転送回数を用いて、当該リクエストを転送したことについての学習を行い、学習結果を前記第２の蓄積データとして記憶手段に蓄積するように前記トラヒック制御方法を構成してもよい。
【００１３】
また、前記第１の学習器と前記第２の学習器を備えるリクエスト受け入れ制御装置が、サービスのリクエストを受信した際に、前記第１の学習器が、前記第１の蓄積データである学習結果に基づいて、受信した前記リクエストを受け入れるか否かの判定を行い、前記第１の学習器が、前記リクエストを受け入れないと判定した場合に、前記第２の学習器が、前記第２の蓄積データである学習結果に基づいて、転送先データセンタを決定するように前記トラヒック制御方法を構成してもよい。
【００１４】
また、前記第１の学習器は、リクエストを受け入れた場合に、当該リクエストに係るサービスの優先度が高く、ネットワーク状況が良好な場合において、当該リクエストを受け入れた行動に対する報酬値が高くなるように報酬値の計算を行い、前記第２の学習器は、リクエストを転送した場合に、転送回数が少なく、リクエストを受け入れたデータセンタでのネットワーク状況が良好な場合において、当該リクエストを転送した行動に対する報酬値が高くなるように報酬値の計算を行うように前記トラヒック制御方法を構成してもよい。
【発明の効果】
【００１５】
本発明によれば、複数のデータセンタが協調することにより、複数のデータセンタ間での負荷分散を実現するための技術を提供することが可能となる。すなわち、各データセンタの分散構造を維持しつつ、特定のデータセンタに負荷が集中することを防いだ負荷分散を実現できる。
【図面の簡単な説明】
【００１６】
【図１】複数データセンタの連携構造の例を示す図である。
【図２】リクエスト受け入れ制御装置１０の機能構成図である。
【図３】システムの動作概要を説明するための図である。
【図４】システムの動作の具体例を説明するための図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例であり、本発明の実施の形態は以下に記述した形態に限られるものではない。また、以下で説明するデータセンタは、エンタープライズネットワークであってもよい。
【００１８】
（システム構成及び動作の概要）
本実施の形態に係るシステムの全体構成は、図１に示したように複数データセンタがネットワーク接続された構成である。そして、各データセンタには、リクエスト受け入れ制御装置１０が備えられ、複数データセンタのリクエスト受け入れ制御装置１０が協調してフロー制御（トラヒック制御）を行う。
【００１９】
ここで、本実施の形態における「サービス」は、特定のサービスに限定されないが、一例を挙げれば、動画配信等のコンテンツ提供サービス、検索サービス等がある。「リクエスト」は、例えば、コンテンツ要求、検索クエリー等である。
【００２０】
図２に、各データセンタに備えられるリクエスト受け入れ制御装置１０の機能構成図を示す。図２に示すように、リクエスト受け入れ制御装置１０は、リクエスト転送処理部１１、リクエスト受け入れ判定部１２、リクエスト転送先決定部１３、及びデータ格納部１４を備える。
【００２１】
本実施の形態では、データセンタにおいてアグリゲータとなるノードをリクエスト受け入れ制御装置１０とすることを想定しており、リクエスト転送処理部１１は、当該アグリゲータの機能（例えば、SSHやProxy等の機能）を備え、リクエストの転送処理やコネクション確立のための処理等を行う。
リクエスト受け入れ判定部１２は、リクエスト転送処理部１１から受け取ったリクエストを受け入れるか否か判定し、受け入れる場合にリクエスト転送処理部１１にリクエスト受け入れ処理（コネクション確立等）を行わせるとともに後述する学習を行い、受け入れない場合に、リクエストをリクエスト転送先決定部１３に渡す機能を有する。リクエスト転送先決定部１３は、リクエスト受け入れ判定部１２により受け入れを拒否されたリクエストの転送先を決定し、リクエスト転送処理部１１を介して当該転送先にリクエストを転送し、後述する学習を行う機能を有する。
【００２２】
本実施の形態では、各データセンタにおけるリクエスト受け入れ制御装置１０のリクエスト受け入れ判定部１２及びリクエスト転送先決定部１３は、それぞれ学習器１２２、１３２を備え、これらにより階層型強化学習を行うことで、データセンタ間のフロー制御を行っている。また、リクエスト受け入れ判定部１２及びリクエスト転送先決定部１３がそれぞれ備える学習用データ取得部１２１、１３１により、学習のために使用するデータ（ネットワーク状況や転送回数等）が取得され、データ格納部１４に格納される。データ格納部１４は、学習のために必要な種々のデータを格納する機能部である。なお、リクエスト受け入れ判定部１２とリクエスト転送先決定部１３における各学習器の処理内容については、後の詳細説明のところでより詳細に説明する。
【００２３】
本実施の形態に係るリクエスト受け入れ制御装置１０は、CPU、記憶装置等からなるコンピュータ（コンピュータの機能を備える通信装置等を含む）に、リクエスト受け入れ制御装置１０の各機能部の機能を実現するためのプログラムを実行させることにより実現できる。当該プログラムは可搬メモリ等の記録媒体からコンピュータにインストールすることとしてもよいし、ネットワーク上のサーバからダウンロードすることとしてもよい。また、リクエスト受け入れ判定部１２とリクエスト転送先決定部１３をハードウェア回路として構成し、アグリゲータ機能を有する装置に組み込むことによりリクエスト受け入れ制御装置１０を実現してもよい。
【００２４】
図３を参照してシステムの動作の概要を説明する。図３の例では、ノードP（アグリゲータノード）がリクエスト受け入れ制御装置１０であるものとする。
【００２５】
図３に示すように、時刻t にて、ユーザからのサービス1 に対するリクエストが、データセンタAに対して送信されてきた場合、まずノードPのリクエスト受け入れ判定部１２は、リクエストの受け入れの可否を決定する。この時、ノードPは学習を行っておらず、一旦、当該リクエストを受け入れ、サービスの優先度に応じたフローを確立し、TCPのスループットの状態（RTT等）を計測し、計測結果を用いて、「受け入れる」という行動に対して学習器１２２が評価を行う。
【００２６】
なお、ネットワーク状況としてのスループットの計測はどのような手法を用いて行ってもよい。例えば、学習用データ取得部１２１が計測機能を備えることにより計測を行ってもよいし、ノードP内の他の機能部が計測を行って、計測結果を学習用データ取得部１２１に渡してもよいし、ノードPの外部にある計測装置が計測を行って、計測結果を学習用データ取得部１２１に渡してもよい。フロー数の計測等についても同様である。
【００２７】
時間a後に、同じ状態遷移が発生した場合、ノードPのリクエスト受け入れ判定部１２は、過去の経験（蓄積した学習結果）に基づいて、リクエストを他のデータセンタに転送するかどうかを判断する。図３の例では、リクエストを受け入れず、リクエスト転送先決定部１３によりリクエストをデータセンタBに転送し、データセンタBから、スループットが高い状態で当該リクエストを受け入れることができたという情報を得る。この時、ノードP（リクエスト転送先決定部１３の学習用データ取得部１２１）では、当該情報や「Bに転送する」という状態遷移を記録する。
【００２８】
本実施の形態では、各データセンタにおけるリクエスト受け入れ制御装置１０は、これらのプロセスを通して最適な状態遷移を学習する。最適な状態遷移が確立されることで、複数のデータセンタが連携して輻輳を抑え、サービスの差別化を達成することができるフロー制御が可能になる。
【００２９】
（処理の詳細）
以下では、本実施の形態に係るシステムの処理内容をより詳細に説明する。
【００３０】
まず、本実施の形態における複数データセンタの運用モデルを示し、運用モデルに基づいた階層型強化学習法を説明する。以下で説明する学習に用いる各種パラメータはデータ格納部１４に格納され、システム管理者等により適宜変更可能である。
【００３１】
＜複数データセンタの運用モデル＞
本実施の形態に係る複数データセンタの運用モデルは以下のとおりである。
・データセンタの数をM とし、提供しているサービスの数をNとし、データセンタk(0≦k≦M)は全てのサービスNを運用している事とする。
・1≦i≦j≦Nの時、サービスiはサービスjよりも優先度が高い。
・データセンタk(0≦k≦M)は、時刻tにおいて収容している全てのフロー数Lkall(t)とサービス別のフロー数Lki(t)(1≦i≦N)をデータ格納部１４に記録している。
・データセンタk における、サービスiの最大フロー数をLmkiとする。
・優先度が高いサービスほど、多くのフローを受け入れることができ、1≦i≦j≦Nの時、Lmj≦Lmiを満たす。
・データセンタkは、他の全てのM−1個のデータセンタと接続されている。
・セッション要求の到着過程・到着率とサービス時間分布・平均時間には特定の仮定を置かずに未知とする。
【００３２】
＜階層型強化学習＞
階層型強化学習では、複数の学習器を用いて階層化することで、複数の目的を達成することが可能になる。本実施の形態では、サービスの優先度と帯域使用率を考慮した負荷分散を達成するために、サービスの優先度に応じた学習器１２２と帯域使用率を考慮した学習器１３２の２つの学習器を各データセンタのリクエスト受け入れ制御装置１０に配置し、サービスの優先度に応じた学習器１２２と帯域使用率を考慮した学習器１３２を連携させる。なお、本実施の形態では各学習器はQ-learningによって学習することとするが、本発明に適用可能な学習の手法はQ-learningに限られるわけではない。
【００３３】
――――― Q-learning ―――――
Q-learningで代表される強化学習では、学習エージェントが現在の状態を観測し、行動を通して得られる報酬が最大になるように、各状態における最適行動を学習する。
【００３４】
今、時刻tでエージェントがいる状態をstとし、stでエージェントがとる行動をatとする。さらに、行動atにより得られる報酬を
【００３５】
【数１】
とする。状態stからst+1に行動atを通して遷移した時、stとatに対するQ値Q(st, at) は以下のように更新される。
【００３６】
【数２】
ここで、α(0 <α≦1) は学習率を示し、γ(0 <γ≦1) は割引率を示している。αが大きい場合には最新の報酬を重視し、αが１の場合には、過去の報酬を全く考慮しない。また、γは遷移先の状態に対するQ値が現在のQ値に与える影響を表し、γが0 の時は遷移先の状態st+1に対するQ値が現在の状態stのQ値に依存しない。本実施の形態では、α及びγを予め決めておき、データ格納部１４に格納しておく。また、学習結果もデータ格納部１４に格納する。
【００３７】
――――― 各学習器の状態集合と行動集合 ―――――
時刻tにおける、各学習器のエージェントが観測する状態を以下のように定義する。なお、各定義に係る情報は、データ格納部１４に格納される。また、各データセンタは自分及び他のデータセンタのフローを計測しているものとする。各データセンタにおける自分及び他のデータセンタのフローの計測の方法は特定の方法に限定されない。リクエスト受け入れ制御装置１０が自分及び他のデータセンタのフローの情報を取得できる方法であればどのような方法でもよい。リクエスト受け入れ制御装置１０は、自分及び他のデータセンタのフローの情報を取得し、データ格納部１４に格納する機能を備えているものとする。
【００３８】
【数３】
【００３９】
【数４】
ここで、式（２）のsfk(t)は、時刻tにおいて、データセンタkが観測している、他のデータセンタの収容しているフロー数を示している。また、式（３）のspk(t)は、データセンタkのサービス別の収容フロー数を示している。すなわち、Lk1はサービス1の収容フロー数を示しており、Lkallは全てのサービスの収容フロー数の和(ΣNi=1Lki) を示している。なお、サービスiはサービスk(1≦i≦k≦N) よりも優先度が高いとする。
【００４０】
次に、時刻tにおけるエージェントがとりうる行動を定義する。リクエスト受け入れ判定部１２が備える、優先度に基づいたサービスの差別化を行う学習器１２２では以下のように行動を定義する。以下のどの定義がどのデータセンタに適用されるかは、予め定めておくものである。
・サービスi(1≦i≦N) のフローのみ受け入れる。
・サービスiおよびj(1≦j≦N)のフローのみ受け入れる。
・m(2≦m≦N)個のサービスに対するフローを受け入れる。
・全てのサービスのフローを受け入れる。
【００４１】
上記の定義において、「サービスi(1≦i≦N) のフローのみ受け入れる。」は、特定のサービスを定めておき、その特定のサービスのリクエストであれば受け入れ可能、という意味であり、「サービスiおよびj(1≦j≦N)のフローのみ受け入れる。」は、２つの特定のサービスを定めておき、その２つの特定のサービスのうちいずれかであれば受け入れ可能、という意味であり、「m(2≦m≦N)個のサービスに対するフローを受け入れる。」は、ｍ個の特定のサービスを定めておき、そのうちのいずれかであれば受け入れ可能、という意味であり、「全てのサービスのフローを受け入れる。」は、いずれのサービスも受け入れ可能、という意味である。
【００４２】
なお、実際にリクエストを受け入れるかどうかは、学習器での行動選択法（本実施の形態では後述するsoft-max法）に基づく。本実施の形態のように、サービス数がＮの時、本学習器１２２における行動数はＮとなる。
【００４３】
次に、リクエスト転送先決定部１３が備える、データセンタの帯域使用率を考慮した学習器１３２の行動を定義する。本学習器１３２は、サービスの差別化を行う学習器１２２の行動が発生した後に動作するものとする。
・リクエストを他のデータセンタに転送する。
【００４４】
データセンタ数がM個の時、データセンタiの、本学習器における行動数はM−1となる。
【００４５】
これらの学習器は階層構造を持ち、ユーザからのリクエストに応じて階層的に連続して学習を行う。まず、ユーザからのリクエストがデータセンタiに到達する場合を考える。まず、データセンタi のサービスの差別化を行う学習器１２２によってデータセンタiでの当該リクエストの受け入れの可否を決定する。受け入れが可決された場合、当該リクエストを送信したユーザに対してのフローを確立する。リクエストが拒否された場合、帯域使用率を考慮した学習器１３２によって受け入れが可能なデータセンタを模索し、リクエストを転送する。
【００４６】
なお、本実施の形態において、各学習器の行動選択にはsoft-max法を用いる（非特許文献１０）。ただし、行動選択の方法はsoft-max法に限られるわけではない。soft-max 法によって、行動pが選択される確率は、以下の式（４）に従う。以下の式（４）のΣにおけるＮ｜Ｍ−１はＮ or Ｍ−１の意味であり、サービスの差別化を行う学習器１２２についてはＮ（サービスの数）をとり、もう一方の学習器１３２についてはデータセンタの数Ｍから１を引いたＭ−１をとることを意味する。
【００４７】
【数５】
式（４）では、各行動の価値Qk(p) の大きさに応じて行動が選択される。つまり、各学習器は、リクエストに対する行動を選択する際に、soft-max 法で算出された確率に基づいて行動を選択する（リクエストを受け入れるか否か、どのデータセンタに転送するか、等）。
【００４８】
――――― 報酬関数 ―――――
ユーザからのリクエストがデータセンタkに到達し、２つの学習器によってリクエストを処理した時に発生する報酬を定義する。サービスの差別化を行う学習器１２２によってリクエストの受け入れが許可された場合、リクエストが指定するサービスの種類に応じて以下の優先度係数が考慮される。以下の優先度係数は、データ格納部１４に予め格納されているデータである。
【００４９】
【数６】
式（５）では、高優先のサービスへのフローを優先的に確立することで、より多くの報酬を獲得できる。ここでriを用いて、サービスの差別化を行う学習器１２２が状態spk(t) からspk(t +1)に行動ak(t)で遷移した際の報酬関数
【００５０】
【数７】
を以下の式（６）で与える。なお、式（６）でのSTkiはデータセンタkにおける、サービスiのTCPフローの最短応答時間(Shortest RTT)を示し、RTkiはサービスiのフローを確立した際の応答時間(RTT) を示す。さらに、Lossはパケットロス率を示す。なお、ここでのRTTやパケットロス率はデータセンタ内（アグリゲータとサーバ間等）でのものであるが、これに限られるわけではない。また、下記のΣは、新たに受けたリクエストで確立された新たなフローのRTTやパケットロス率等を測定するとともに、既に確立されているフローについてのその時点でのRTTやパケットロス率等も測定して、下記の式に基づき加え合わせることを意味している。
【００５１】
【数８】
式（６）から、新たに確立されたフローの優先度が高く、確立したフローのRTTが最も短いRTTに近く、パケットロス率が低い場合において、学習エージェントは高い報酬値を得ることができ、式（１）に示したようにQ値が大きくなるので、当該フローの受け入れ確率が向上する。もし、新たなフローを確立した際に輻輳が発生し、パケットロス率やRTTが急激に遅くなった場合、エージェントが獲得できる報酬値が小さくなり、新たなフローを受け入れる確率が減少する。なお、上記の例では、ネットワーク状況としてスループットの状態であるshortest RTT、RTT、Lossを用いているが、ネットワーク状況に関するデータはこれらに限られるわけではない、ネットワーク状況を表せるパラメータであれば上記以外のものを用いてもよい。
【００５２】
次に、帯域使用率を考慮する学習器１３２の報酬関数を以下に示す。なお、式（７）において、transfer は、リクエストを転送した結果、最終的にリクエストを受け入れたデータセンタまでの転送回数(ホップ数) を示す。
【００５３】
【数９】
式（７）では、サービスの差別化を行う学習器１２２によって棄却されたリクエストを他のデータセンタに転送した際に、転送回数と転送先の輻輳状況によってエージェントが獲得できる報酬が決定される。つまり、転送回数が少なく、輻輳の可能性が低いデータセンタに転送するほど、エージェントは高い報酬を獲得することができる。つまり、当該データセンタに転送するという行動のQ値が高くなり、当該データセンタに転送される確率が高くなる。
【００５４】
最終的にエージェントは、 サービスの差別化を行う学習器１２２にて、できるだけ輻輳が発生しないように優先度が高いフローを優先的に確立し、帯域使用率を考慮する学習器１３２にて、データセンタ間で負荷分散を達成するフロー制御が可能になる。
【００５５】
（動作の具体例）
次に、図４に示すように、データセンタA、B、Cが接続されたシステム構成を例に挙げて、動作の具体例を説明する。図４に示すTransfer_numは、帯域使用率を考慮する学習器１３２の報酬関数におけるtransferに対応する。
【００５６】
まず、データセンタAにあるサービスに対するリクエストが到達するとする。データセンタAのリクエスト転送処理部１１（Ａ）は、当該リクエストの受け入れの可否を決定するリクエスト受け入れ判定部１２（Ａ）に対して、リクエストを転送する。この時、リクエスト受け入れ判定部１２（Ａ）がリクエストの受け入れを拒否すると、当該リクエストをリクエスト転送先決定部１３（Ａ）に転送し、リクエスト転送先決定部１３（Ａ）がリクエストの受け入れが可能なデータセンタを探し、データセンタB に転送することにする。この時、Transfer_numのパラメータを１とし、パラメータもリクエストに付随して転送する。
【００５７】
転送されたリクエストがデータセンタBに到達し、データセンタAと同様に、リクエスト受け入れ判定部１２（Ｂ）が当該リクエストの受け入れを拒否し、リクエスト転送先決定部１３（Ｂ）が当該リクエストをデータセンタA 以外のデータセンタCに転送するとする。この時、リクエスト転送先決定部１３（Ｂ）は、Transfer_numのパラメータを２とし、パラメータもリクエストに付随して転送する。
【００５８】
転送されたリクエストがデータセンタC に到達し、データセンタCのリクエスト受け入れ判定部１２（Ｃ）が当該リクエストの受け入れを許可することにする。リクエストの受け入れが許可され、TCPフローが確立されると同時に、リクエスト受け入れ判定部１２（Ｃ）は当該フローのデータセンタCにおけるスループットに関する情報（例えば、shortest RTT、RTT、Loss等）を計測もしくは取得する。なお、データセンタのスループットは、例えば、階層的なデータセンタの構造を利用して、ボトムアップで各ネットワークコンポネント（ルータ、スイッチ、サーバ、etc）のリソース状況を集約する方法を用いて計測することができるが、計測方法はこの方法に限られない。計測後、リクエスト受け入れ判定部１２（Ｃ）はデータセンタAのリクエスト受け入れ判定部１２（A）に対して、転送されてきたリクエストを受け入れた結果として、Transfer_numと計測したスループットを伝える。また、リクエスト受け入れ判定部１２（C）は、このリクエストを受け入れたという行動に対して学習（報酬計算、Q値更新等）を行い、学習結果をデータ格納部１４（Ｃ）に格納する。
【００５９】
データセンタAのリクエスト受け入れ判定部１２（A）は、データセンタC から送られてきた、転送リクエストの転送回数とスループットをリクエスト転送先決定部１３（A）に転送し、リクエスト転送先決定部１３（A）は、データセンタBに転送するという行動に対して学習（報酬計算、Q値更新等）を行い、学習結果をデータ格納部１４（A）に格納する。
【００６０】
これらのプロセスを通して、データセンタAは、各データセンタのリソース状況を学習し、転送回数が少なく、スループットが高い転送先を発見できるようになる。
【００６１】
また、各データセンタで、受け入れの可否をサービスの優先度別に決定することにより、サービスの優先度に応じた、サービスの差別化を達成することができる。
【００６２】
（実施の形態のまとめ、効果）
本実施の形態によれば、複数のデータセンタやが、ネットワーク（インターネット）を通して相互接続された環境において、各データセンタのTCP を管理できる機器（リクエスト受け入れ制御装置等）にて、前記環境下でのTCPフローの解析と制御を自律的に行うネットワーク管理システムが提供される。前記各TCP を管理できる機器は、相互接続されている、異なるデータセンタネットワークのTCP を管理可能な機器との協調動作を通して、互いにTCP のスループットの状態を計測する機能と、当該TCP を管理できる機器に対して、あるサービスへのリクエストが送られてきた場合、サービスの種別データ（優先度）と蓄積した計測結果を用いた、複数のパラメータによって動作が決定される学習アルゴリズムを通して、リクエストの送信元（ユーザ）に対して、当該TCP を管理できる機器より、TCPフローを確立するかどうかを判断する機能と、当該TCPを管理できる機器において、前記の判断機能を通して、リクエストに対するTCP フローの確立が不可能と判断した際に、相互接続されている、他のデータセンタのTCPを管理できる機器から、TCPフローを確立した際にスループットを最大化できるTCPを管理できる機器を、サービスの種別データ（優先度）と蓄積した計測結果を用いた、複数のパラメータによって動作が決定される学習アルゴリズムを通して決定し、転送する機能を有している。
【００６３】
より詳細には、本実施の形態では、ユーザからの接続頻度と接続時間の周期性を考慮した階層型強化学習のモデルを利用することでフローの確立やリクエストの転送を決定する。階層型強化学習は、データセンタ間で帯域の使用率を考慮し、負荷分散を達成する学習器と各データセンタにてサービスの差別化を図る学習器を階層的に連携させることで学習を行う。
【００６４】
これらの学習器を階層化することで、単一の学習器を用いた場合よりも、学習を高速に進めることができる。さらに、各データセンタの分散構造を維持しつつ、複数のデータセンタを統一的に管理することが可能になる。学習が進むことで、ユーザの接続特性に学習が適応していくため、特定のデータセンタに負荷が集中することを防ぎ、サービスの優先度に基づいたフロー制御をすることが可能になる。
【００６５】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００６６】
１０ リクエスト受け入れ制御装置
１１ リクエスト転送処理部
１２ リクエスト受け入れ判定部
１３ リクエスト転送先決定部
１４ データ格納部
１２１、１３１ 学習用データ取得部
１２２、１３２ 学習器
【特許請求の範囲】
【請求項１】
複数のデータセンタが接続されたネットワークシステムにおけるトラヒック制御方法であって、
前記複数のデータセンタの各データセンタはリクエスト受け入れ制御装置を備えており、
サービスのリクエストを受信したデータセンタのリクエスト受け入れ制御装置は、過去にリクエストを受け入れた際に取得したネットワーク状況に基づく第１の蓄積データを用いて、当該リクエストを受け入れるか否かを判定し、
前記リクエスト受け入れ制御装置が、前記リクエストを受け入れないと判定した場合に、過去にリクエストを転送した際に取得したネットワーク状況及びリクエスト転送回数に基づく第２の蓄積データを用いて、転送先データセンタを決定し、当該転送先データセンタにリクエストを転送し、
１回又は複数回のリクエスト転送が行われた後に、転送に係るリクエストを受信したリクエスト受け入れ制御装置が、前記リクエストを受け入れる場合に、当該リクエストに対応するサービスのトラヒックフローが確立した後のネットワーク状況を測定するとともに、当該ネットワーク状況とリクエスト転送回数を転送元のリクエスト受け入れ制御装置に送信し、
前記転送元のリクエスト受け入れ制御装置が、前記ネットワーク状況とリクエスト転送回数を受信する
ことを特徴とするトラヒック制御方法。
【請求項２】
前記複数のデータセンタにおける各リクエスト受け入れ制御装置は、第１の学習器と第２の学習器を備えており、
前記第１の学習器が、リクエストを受け入れた際に測定されたネットワーク状況、及び当該リクエストに対応するサービスの優先度を用いて、当該リクエストを受け入れたことについての学習を行い、学習結果を前記第１の蓄積データとして記憶手段に蓄積し、
前記第２の学習器が、転送したリクエストを受け入れた他のリクエスト受け入れ制御装置から受信した当該他のリクエスト受け入れ制御装置により取得されたネットワーク状況及び転送回数を用いて、当該リクエストを転送したことについての学習を行い、学習結果を前記第２の蓄積データとして記憶手段に蓄積する
ことを特徴とする請求項１に記載のトラヒック制御方法。
【請求項３】
前記第１の学習器と前記第２の学習器を備えるリクエスト受け入れ制御装置が、サービスのリクエストを受信した際に、
前記第１の学習器が、前記第１の蓄積データである学習結果に基づいて、受信した前記リクエストを受け入れるか否かの判定を行い、
前記第１の学習器が、前記リクエストを受け入れないと判定した場合に、前記第２の学習器が、前記第２の蓄積データである学習結果に基づいて、転送先データセンタを決定する
ことを特徴とする請求項２に記載のトラヒック制御方法。
【請求項４】
前記第１の学習器は、リクエストを受け入れた場合に、当該リクエストに係るサービスの優先度が高く、ネットワーク状況が良好な場合において、当該リクエストを受け入れた行動に対する報酬値が高くなるように報酬値の計算を行い、
前記第２の学習器は、リクエストを転送した場合に、転送回数が少なく、リクエストを受け入れたデータセンタでのネットワーク状況が良好な場合において、当該リクエストを転送した行動に対する報酬値が高くなるように報酬値の計算を行う
ことを特徴とする請求項２又は３に記載のトラヒック制御方法。
【請求項１】
複数のデータセンタが接続されたネットワークシステムにおけるトラヒック制御方法であって、
前記複数のデータセンタの各データセンタはリクエスト受け入れ制御装置を備えており、
サービスのリクエストを受信したデータセンタのリクエスト受け入れ制御装置は、過去にリクエストを受け入れた際に取得したネットワーク状況に基づく第１の蓄積データを用いて、当該リクエストを受け入れるか否かを判定し、
前記リクエスト受け入れ制御装置が、前記リクエストを受け入れないと判定した場合に、過去にリクエストを転送した際に取得したネットワーク状況及びリクエスト転送回数に基づく第２の蓄積データを用いて、転送先データセンタを決定し、当該転送先データセンタにリクエストを転送し、
１回又は複数回のリクエスト転送が行われた後に、転送に係るリクエストを受信したリクエスト受け入れ制御装置が、前記リクエストを受け入れる場合に、当該リクエストに対応するサービスのトラヒックフローが確立した後のネットワーク状況を測定するとともに、当該ネットワーク状況とリクエスト転送回数を転送元のリクエスト受け入れ制御装置に送信し、
前記転送元のリクエスト受け入れ制御装置が、前記ネットワーク状況とリクエスト転送回数を受信する
ことを特徴とするトラヒック制御方法。
【請求項２】
前記複数のデータセンタにおける各リクエスト受け入れ制御装置は、第１の学習器と第２の学習器を備えており、
前記第１の学習器が、リクエストを受け入れた際に測定されたネットワーク状況、及び当該リクエストに対応するサービスの優先度を用いて、当該リクエストを受け入れたことについての学習を行い、学習結果を前記第１の蓄積データとして記憶手段に蓄積し、
前記第２の学習器が、転送したリクエストを受け入れた他のリクエスト受け入れ制御装置から受信した当該他のリクエスト受け入れ制御装置により取得されたネットワーク状況及び転送回数を用いて、当該リクエストを転送したことについての学習を行い、学習結果を前記第２の蓄積データとして記憶手段に蓄積する
ことを特徴とする請求項１に記載のトラヒック制御方法。
【請求項３】
前記第１の学習器と前記第２の学習器を備えるリクエスト受け入れ制御装置が、サービスのリクエストを受信した際に、
前記第１の学習器が、前記第１の蓄積データである学習結果に基づいて、受信した前記リクエストを受け入れるか否かの判定を行い、
前記第１の学習器が、前記リクエストを受け入れないと判定した場合に、前記第２の学習器が、前記第２の蓄積データである学習結果に基づいて、転送先データセンタを決定する
ことを特徴とする請求項２に記載のトラヒック制御方法。
【請求項４】
前記第１の学習器は、リクエストを受け入れた場合に、当該リクエストに係るサービスの優先度が高く、ネットワーク状況が良好な場合において、当該リクエストを受け入れた行動に対する報酬値が高くなるように報酬値の計算を行い、
前記第２の学習器は、リクエストを転送した場合に、転送回数が少なく、リクエストを受け入れたデータセンタでのネットワーク状況が良好な場合において、当該リクエストを転送した行動に対する報酬値が高くなるように報酬値の計算を行う
ことを特徴とする請求項２又は３に記載のトラヒック制御方法。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−２５３４４１（Ｐ２０１２−２５３４４１Ａ）
【公開日】平成２４年１２月２０日（２０１２．１２．２０）
【国際特許分類】
【出願番号】特願２０１１−１２２５９０（Ｐ２０１１−１２２５９０）
【出願日】平成２３年５月３１日（２０１１．５．３１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１２月２０日（２０１２．１２．２０）
【国際特許分類】
【出願日】平成２３年５月３１日（２０１１．５．３１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]