サーバ選択方法及び装置及びプログラム
【課題】 ネットワーク上の複数の箇所にサービス提供元となるサーバが存在する場合に、適切な提供元サーバを選択する。
【解決手段】 本発明は、サービス提供元となるサーバに対するコンテンツ要求に対して、帯域やトポロジ情報を含むネットワーク情報と観測された要求トラヒック量に基づいて、送信側（サーバ）ノードから流れるトラヒック量の総計が受信側（要求元）ノードの要求トラヒック量と等しくなるように、複発単着のモデルとして線形計画問題を計算することでサービス提供元となるサーバを選択し、選択されたサーバ-要求元ノード間の経路を求める。
【解決手段】 本発明は、サービス提供元となるサーバに対するコンテンツ要求に対して、帯域やトポロジ情報を含むネットワーク情報と観測された要求トラヒック量に基づいて、送信側（サーバ）ノードから流れるトラヒック量の総計が受信側（要求元）ノードの要求トラヒック量と等しくなるように、複発単着のモデルとして線形計画問題を計算することでサービス提供元となるサーバを選択し、選択されたサーバ-要求元ノード間の経路を求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバ選択方法及び装置及びプログラムに係り、特に、映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元がネットワーク上の複数の箇所に存在する環境でサービスを利用する形態において、サービスの要求元に応じて適切なサービス提供元を選択し、サービス要求元とサービス提供元をつなぐネットワーク上の経路を決定するためのサーバ選択方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
ネットワークの普及によってサービスに対する要求数が増大し、サービス提供元（サーバ、ストレージ等）内部における処理量や、サービス提供元-サービス要求元（サービスの利用者）間を流れるトラヒック量も増加している。サービス提供元での処理量が増加すると、サービス要求に対応できなくなりサービスが機能しなくなる。また、トラヒック量が増加するとネットワーク上の輻輳発生によってサービス提供元-サービス要求元間の通信性能が低下してしまいサービスが機能しなくなる。
【０００３】
この問題を解決するための技術としてCDN（Contents Distribution Network）がある。これは、ネットワーク上の複数の箇所にサービス提供元を配置することで、サービス提供元の内部処理量、及び、サービス提供元-サービス要求元間のトラヒック量を分散させるしくみである。
【０００４】
サービス要求元が複数のサービス提供元から適切なサービス提供元を選択する方法として、ネットワーク管理者によるサービス要求元とサービス提供元との対応付けを事前に設定しておく静的な方法や、ラウンドロビン、もしくは各リンクにおけるRTTに対応するといった動的な方法がある（例えば、非特許文献１参照）。
【０００５】
また、サービス提供元-サービス要求元間のネットワーク上の経路は、主に、OSPF(Open Shortest Path First)（例えば、非特許文献２参照）などのリンクにコスト（距離、遅延など）を設定し、それに基づいて決定された最短経路を用いている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−３４９８２８号公報
【非特許文献】
【０００７】
【非特許文献１】J. Moy, "RFC 2328 OSPF Vertion 2," 1998, Apr．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記のサービス要求元が複数のサービス提供元に対して、適切なサービス提供元を選択するために用いられている動的な方法は、各リンクのRTT(Round Trip Time)や利用可能帯域といった間接的なネットワーク内の混雑情報を扱っているため、サーバ選択の適性精度が低い。
【０００９】
また、従来は、サービス提供元-サービス要求元間の通信にコスト最短経路を用いているため、コスト最小のリンクにトラヒックが集中する傾向があり、輻輳発生によってサービスが機能しなくなるという問題がある。
【００１０】
本発明は、上記の点に鑑みなされたもので、
（１）トラヒックの偏りによるリンク負荷を分散し、輻輳を回避する；
（２）ネットワークの混雑情報を用いた線形計画問題による厳密計算によりサーバ選択の適正精度を高める；
ことを可能とし、サービス機能低下を防止するサーバ選択方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するため、本発明（請求項１）は、映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元となるサーバがネットワーク上の複数の箇所に存在する環境において、要求元(サービス利用者が接続している)に応じてサービス提供元サーバを選択するサーバ選択方法であって、
ネットワーク情報を格納した記憶手段と、
定期的にネットワークの混雑状況を観測するネットワーク情報観測手段と、
各要求元ノードの各コンテンツ（サービスの種類）に対する要求トラヒック量を求める要求トラヒック量計算手段と、
前記要求トラヒック量と前記記憶手段のネットワーク情報に基づいて各要求元に適したサーバノードを選択し、要求元-サーバノード間の経路を決定するサーバ・経路決定手段と、を有する装置において、
前記サーバ・経路決定手段が、前記サービス提供元となるサーバに対するコンテンツ要求に対して、前記記憶手段から取得した前記ネットワーク情報と前記要求トラヒック量に基づいて、送信側ノード（サーバ）から流れるトラヒック量の総計が受信側ノード（要求元）の要求トラヒック量と等しくなるような複発単着のモデルを用いて線形計画問題を計算することで適切なサーバを選択し、選択されたサーバ-要求元ノード間の経路を求めるサーバ・経路決定ステップを行うことを特徴とする。
【００１２】
また、本発明（請求項２）は、映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元となるサーバがネットワーク上の複数の箇所に存在する環境において、要求元(サービス利用者が接続している)に応じてサービス提供元サーバを選択するサーバ選択装置であって、
ネットワーク情報を格納した記憶手段と、
定期的にネットワークの混雑状況を観測するネットワーク情報観測手段と、
各要求元ノードの各コンテンツに対する要求トラヒック量を求める要求トラヒック量計算手段と、
前記サービス提供元となるサーバに対するコンテンツ要求に対して、前記記憶手段から取得した前記ネットワーク情報と前記要求トラヒック量計算手段から取得した前記要求トラヒック量に基づいて、送信側ノード（サーバ）から
流れるトラヒック量の総計が受信側ノード（要求元）の要求トラヒック量と等しくなるような複発単着のモデルを用いて線形計画問題を計算することで適切なサーバを選択し、選択されたサーバ-要求元ノード間の経路を求めるサーバ・経路決定手段と、を有することを特徴とする。
【００１３】
また、本発明（請求項３）は、請求項２に記載のサーバ選択装置を構成する各手段としてコンピュータを機能させるためのサーバ選択プログラムである。
【発明の効果】
【００１４】
上述のように本発明によれば、映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元がネットワーク上の複数の箇所に存在する場合に、トラヒックの偏りによるリンク負荷を分散することで、輻輳を回避し、ネットワークの混雑状況（トラヒック量）を用いた線形計画問題による計算により適切な提供元サーバを選択すると共に、サービス要求元（ノード）-選択されたサーバ（ノード）とをつなぐ経路を求めることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施の形態におけるサーバ選択装置の構成図である。
【図２】本発明の一実施の形態における動作のフローチャートである。
【図３】本発明の一実施の形態におけるネットワークの例である。
【図４】本発明の一実施の形態における結果（４９番ノードの場合）である。
【発明を実施するための形態】
【００１６】
以下図面と共に、本発明の実施の形態を説明する。
【００１７】
最初に本発明の概要を説明する。
【００１８】
本発明は、要求元から要求するコンテンツ毎のトラヒックに対して、複数のコンテンツ配信（サービス提供元）サーバから目的に沿ったサーバの選択と、選択したサーバ-要求元間の経路を決定する方法をモデル化し、線形計画問題として計算する。具体的には、入力として、リンクの利用可能帯域、トポロジなどのネットワーク情報と、要求元ノードの各コンテンツに対するトラヒック量（要求トラヒック量）を入力として与え、計算結果である要求元-サーバ間の経路情報をルータ内のルーティングテーブルに反映させることによって、特定のリンクへの負荷を分散し、サービス機能の低下を防ぐ。モデルはネットワークのルータなどの通信機器をノード、機器間をつなぐケーブルをリンクとみなした、グラフ問題としてモデル化したものである。このとき、実際にサービスを利用するために用いる機器(PC等)や、サービス提供のために用いる機器(サーバ、ストレージ等)はグラフ上の要求元ノード、サーバノードに繋がっていると仮定する。
【００１９】
モデルは、リンクが向きを持たない無向グラフを前提として考える。無向グラフ、かつ、複数の種類のトラヒックが流れる通信ネットワークを扱う問題の場合、多品種フロー問題のモデルが用いられる。しかし、多品種フロー問題は1つの送信側ノードから1つの受信側ノードにトラヒックを流すという、単発単着の形になっており、今回想定している複数のサービス提供元があるような複発単着の形には適さない。そのため、本発明では、送信側（サーバ）ノードから流れるトラヒック量の総計が受信側（要求元）ノードの要求トラヒック量と等しくなるようにした複発単着モデルを用いた線形計画問題計算する。
【００２０】
図１は、本発明の一実施の形態におけるサーバ選択装置の構成を示す。
【００２１】
同図に示すサーバ選択装置１は、データベース部１００、計算部２００、ネットワーク運用部３００から構成される。
【００２２】
データベース部１００は、リンクの利用可能帯域、トポロジなどのネットワーク情報を格納し、計算部２００からアクセスされることにより、格納されているデータを出力する。具体的に、データベース部１００に格納される情報は、
・ネットワーク形状：ノード，ノード間におけるリンクの有無
・リンク情報：容量，コスト
・配信サーバの位置：どのノードがサーバノードであるかに関する情報
・要求トラヒック情報(初期値)：各ノードのコンテンツ毎の要求トラヒック量
等である。
【００２３】
計算部２００は、要求トラヒック量計算部２１０とサーバ選択/サーバノード-要求元ノード間経路決定部２２０から構成される。
【００２４】
また、ネットワーク運用部３００は、ネットワーク経路制御部３１０、ネットワーク情報観測部３２０から構成される。
【００２５】
要求トラヒック量計算部２１０は、後述するネットワーク運用部３００のネットワーク情報観測部３２０から定期的に提供される、各ノードにおけるコンテンツ毎のトラヒック量から要求トラヒック情報を作成し、サーバ選択/サーバノード-要求元ノード間経路決定部２２０に出力する。
【００２６】
サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、システム初期はデータベース部１００から提供されるネットワーク情報と前述したモデル（複発単着のモデル）を用いて、目的に沿ったサーバの選択、該当サーバノード-要求元ノード間のネットワーク経路を計算し、解であるネットワーク経路情報をネットワーク運用部３００ネットワーク経路制御部３１０に提供する。初期動作後は、定期的にデータベース部１００のネットワーク情報と、要求トラヒック量計算部２１０から提供される要求トラヒック情報を用いて、同様の計算を行い、ネットワーク経路制御部３１０に提供する。
【００２７】
ネットワーク運用部３００のネットワーク経路制御部３１０は、サーバ選択/サーバノード-要求元ノード間経路決定部２２０から入力されるネットワーク経路情報を用いて、ネットワークの経路設定を行う。経路設定自体は、MPLS（例えば、文献１：E. Rosen, a. Viswanathan and R. Callon, "RFC 3031 Multiprotocol Label Switching Architecture," 2001, Jan.参照）、OpenFlow（例えば、文献２："The OpenFlow Switch Consortium," http://www.openflowswitch.org/）などの既存技術を用いる。
【００２８】
ネットワーク情報観測部３２０は、ネットワークのトラヒック量を定期的に観測し、要求トラヒック量計算部２１０に出力する。トラヒックの観測自体は、OpenFlowなどのフローレベル、もしくはQoSの品質クラスレベルで測定可能な既存技術を用いる。
【００２９】
なお、図１では、サーバ選択装置１内にネットワーク運用部３００を含む構成としているが、これに限定されることなく、サーバ選択装置１の外部に設けることも可能である。
【００３０】
図２は、本発明の一実施の形態における動作のフローチャートである。
【００３１】
ステップ１０１） ネットワーク運用部３００のネットワーク情報観測部３２０は、ネットワークの各ノードにおけるコンテンツ毎のトラヒック量を定期的に観測し、計算部２００の要求トラヒック量計算部２１０に出力する。
【００３２】
ステップ１０２） 要求トラヒック量計算部２１０は、ネットワーク情報観測部３２０から入力された各ノードにおけるコンテンツ毎のトラヒック量から要求トラヒック情報を作成し、サーバ選択/サーバノード-要求元ノード間経路決定部２２０に出力する。
【００３３】
ステップ１０３） サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、データベース部１００から、ネットワーク形状、ノード情報、ノードのリンク情報、容量、コスト、サーバノードの位置情報、要求トラヒックの情報を読み出す。
【００３４】
ステップ１０４） サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、データベース部１００から読み込んだ情報と、要求トラヒック量計算部２１０から入力された要求トラヒック情報から複発単着モデル（後述する変数と制約式を参照）を用いて、サーバを選択し、該当サーバノード-要求元ノード間のネットワーク経路を計算し、ネットワーク運用部３００のネットワーク経路制御部３１０に出力する。
【００３５】
ステップ１０５） ネットワーク運用部３００のネットワーク経路制御部３１０は、入力されたネットワーク経路情報を、ルータ内のルーティングテーブルに反映させることによってネットワークの経路の設定を行う。
【００３６】
以下に、計算部２００のサーバ選択/サーバノード-要求元ノード間経路決定部２２０の処理について詳細に説明する。
【００３７】
計算部２００のサーバ選択/サーバノード-要求元ノード間経路決定部２２０に用いられる数式モデルの一例を以下に示す。
【００３８】
＜変数＞
ｍ：コンテンツを要求する要求元ノードを示す識別番号
ｎ：コンテンツを配信するサーバノードを示す識別番号
ｌ： コンテンツの種類を示す識別番号
ｘ：各リンクにおける要求元ノードmが要求するコンテンツlのトラヒック量
ｄ：要求元ノードmが要求するコンテンツlの需要トラヒック量
U：リンク容量
S：コンテンツlを要求する要求元ノードmの集合
D：コンテンツlを配信するサーバノードnの集合
Ｎ'k：リンクの片端をノードkとしたときの他端ノードの集合
c：リンク上にトラヒックが流れたときのコスト
＜制約式＞
サーバ選択/サーバノード-要求元ノード間経路決定部２２０で用いられる制約式は以下のとおりである。以下の各制約式の変数は上述のとおりである。
【００３９】
【数１】
上記の（１）〜（６）の式の意味は以下のとおりである。
【００４０】
（１）ノードkが要求元ノードの場合、ノードkに流れてくるトラヒック量(流入トラヒック量)とノードkから流れていくトラヒック量(流出トラヒック量)の差が-d(要求トラヒック量)になることを示している。
【００４１】
（２）ノードkが要求元ノード、サーバノードでない場合、ノードkにおける入入トラヒック量と流出トラヒック量が等しく、フロー保存則に従うことを示している。
【００４２】
（３）、（４）ノードkがサーバノードの場合、各ノードkにおける流入トラヒック量と流出トラヒック量の差の総計がd(要求トラヒック量)になることを示している。
【００４３】
（５）各リンクに流れるトラヒック量がリンク容量以下になることを示している。
【００４４】
（６）xはトラヒック量のため、0以上、需要トラヒック量以下の連続値をとることを示している。
【００４５】
＜目的値＞
最適化に用いる目的値は以下のとおりである。
【００４６】
【数２】
（７）リンク毎に流れるトラヒック量とコストの積の総計を最小化することを示している。
【００４７】
サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、上記の（１）〜（７）に示すモデルを用いて図３に示すようなネットワークに対して、経路を決定するものとする。
【００４８】
図３において、黒い三角マークがサーバノードであり、その他のノードを今回は要求元ノードとしている。コンテンツは1種類、各リンク容量は一律15.0Gbps、各要求元ノードの要求トラヒック量は0.1Gbpsから10.0Gbpsの範囲を一様乱数で設定した。
【００４９】
上記の制約式を適用すると、モデルの出力は各リンクにおけるトラヒック量xであり、ノードiからノードjに流れる、要求元ノードm，コンテンツlのトラヒック量を示している。
【００５０】
結果の一例として、図３の49番ノード(要求トラヒック量:9.7Gbps)の場合を述べる。
【００５１】
図４は、m(要求元ノード)=49、l(コンテンツ番号)=1における、各リンクのトラヒック量xを示している。なお、トラヒック量が0のリンクのものに関しては省略している。図４に示すように、49番ノードにサービスを行うサーバは29番ノードと23番ノードになり、それぞれ、(1)-(3)-(5)、(2)-(4)-(6)の経路を使うことになる。
【００５２】
サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、選択されたサーバ及び、求められた経路をネットワーク経路制御部３１０に出力する。これにより、ネットワーク経路制御部３１０は、ネットワーク上の経路に得られた解を反映させて経路設定を行うことができる。
【００５３】
上記のように、本発明はトラヒック発生によるコストを最小化することを目的として、適切なサーバの選択と、選択されたサーバノード-要求元ノード間の経路を最適化する。これにより、最短経路ではリンク容量を超えるトラヒックが生じる場合に、コストを考慮した上でリンク負荷を分散するネットワーク運用を可能にする。
【００５４】
また、上記の式(7)を目的に沿って変更することで、例えばリンク使用率(リンク容量におけるトラヒック量の割合)の最大値を下げると言った効果も期待できる。
【００５５】
また、図１に示すサーバ選択装置の構成要素の各動作をプログラムとして構築し、サーバ選択装置として用いられるコンピュータにインストールする、または、ネットワークを介して流通させることが可能である。
【００５６】
また、構築されたプログラムをハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００５７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５８】
１ サーバ選択装置
１００ データベース部
２００ 計算部
２１０ 需要トラヒック量計算部
２２０ サーバ選択／サーバノード−要求元ノード間経路決定部
３００ ネットワーク運用部
３１０ ネットワーク経路制御部
３２０ ネットワーク情報観測部
【技術分野】
【０００１】
本発明は、サーバ選択方法及び装置及びプログラムに係り、特に、映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元がネットワーク上の複数の箇所に存在する環境でサービスを利用する形態において、サービスの要求元に応じて適切なサービス提供元を選択し、サービス要求元とサービス提供元をつなぐネットワーク上の経路を決定するためのサーバ選択方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
ネットワークの普及によってサービスに対する要求数が増大し、サービス提供元（サーバ、ストレージ等）内部における処理量や、サービス提供元-サービス要求元（サービスの利用者）間を流れるトラヒック量も増加している。サービス提供元での処理量が増加すると、サービス要求に対応できなくなりサービスが機能しなくなる。また、トラヒック量が増加するとネットワーク上の輻輳発生によってサービス提供元-サービス要求元間の通信性能が低下してしまいサービスが機能しなくなる。
【０００３】
この問題を解決するための技術としてCDN（Contents Distribution Network）がある。これは、ネットワーク上の複数の箇所にサービス提供元を配置することで、サービス提供元の内部処理量、及び、サービス提供元-サービス要求元間のトラヒック量を分散させるしくみである。
【０００４】
サービス要求元が複数のサービス提供元から適切なサービス提供元を選択する方法として、ネットワーク管理者によるサービス要求元とサービス提供元との対応付けを事前に設定しておく静的な方法や、ラウンドロビン、もしくは各リンクにおけるRTTに対応するといった動的な方法がある（例えば、非特許文献１参照）。
【０００５】
また、サービス提供元-サービス要求元間のネットワーク上の経路は、主に、OSPF(Open Shortest Path First)（例えば、非特許文献２参照）などのリンクにコスト（距離、遅延など）を設定し、それに基づいて決定された最短経路を用いている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−３４９８２８号公報
【非特許文献】
【０００７】
【非特許文献１】J. Moy, "RFC 2328 OSPF Vertion 2," 1998, Apr．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記のサービス要求元が複数のサービス提供元に対して、適切なサービス提供元を選択するために用いられている動的な方法は、各リンクのRTT(Round Trip Time)や利用可能帯域といった間接的なネットワーク内の混雑情報を扱っているため、サーバ選択の適性精度が低い。
【０００９】
また、従来は、サービス提供元-サービス要求元間の通信にコスト最短経路を用いているため、コスト最小のリンクにトラヒックが集中する傾向があり、輻輳発生によってサービスが機能しなくなるという問題がある。
【００１０】
本発明は、上記の点に鑑みなされたもので、
（１）トラヒックの偏りによるリンク負荷を分散し、輻輳を回避する；
（２）ネットワークの混雑情報を用いた線形計画問題による厳密計算によりサーバ選択の適正精度を高める；
ことを可能とし、サービス機能低下を防止するサーバ選択方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するため、本発明（請求項１）は、映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元となるサーバがネットワーク上の複数の箇所に存在する環境において、要求元(サービス利用者が接続している)に応じてサービス提供元サーバを選択するサーバ選択方法であって、
ネットワーク情報を格納した記憶手段と、
定期的にネットワークの混雑状況を観測するネットワーク情報観測手段と、
各要求元ノードの各コンテンツ（サービスの種類）に対する要求トラヒック量を求める要求トラヒック量計算手段と、
前記要求トラヒック量と前記記憶手段のネットワーク情報に基づいて各要求元に適したサーバノードを選択し、要求元-サーバノード間の経路を決定するサーバ・経路決定手段と、を有する装置において、
前記サーバ・経路決定手段が、前記サービス提供元となるサーバに対するコンテンツ要求に対して、前記記憶手段から取得した前記ネットワーク情報と前記要求トラヒック量に基づいて、送信側ノード（サーバ）から流れるトラヒック量の総計が受信側ノード（要求元）の要求トラヒック量と等しくなるような複発単着のモデルを用いて線形計画問題を計算することで適切なサーバを選択し、選択されたサーバ-要求元ノード間の経路を求めるサーバ・経路決定ステップを行うことを特徴とする。
【００１２】
また、本発明（請求項２）は、映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元となるサーバがネットワーク上の複数の箇所に存在する環境において、要求元(サービス利用者が接続している)に応じてサービス提供元サーバを選択するサーバ選択装置であって、
ネットワーク情報を格納した記憶手段と、
定期的にネットワークの混雑状況を観測するネットワーク情報観測手段と、
各要求元ノードの各コンテンツに対する要求トラヒック量を求める要求トラヒック量計算手段と、
前記サービス提供元となるサーバに対するコンテンツ要求に対して、前記記憶手段から取得した前記ネットワーク情報と前記要求トラヒック量計算手段から取得した前記要求トラヒック量に基づいて、送信側ノード（サーバ）から
流れるトラヒック量の総計が受信側ノード（要求元）の要求トラヒック量と等しくなるような複発単着のモデルを用いて線形計画問題を計算することで適切なサーバを選択し、選択されたサーバ-要求元ノード間の経路を求めるサーバ・経路決定手段と、を有することを特徴とする。
【００１３】
また、本発明（請求項３）は、請求項２に記載のサーバ選択装置を構成する各手段としてコンピュータを機能させるためのサーバ選択プログラムである。
【発明の効果】
【００１４】
上述のように本発明によれば、映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元がネットワーク上の複数の箇所に存在する場合に、トラヒックの偏りによるリンク負荷を分散することで、輻輳を回避し、ネットワークの混雑状況（トラヒック量）を用いた線形計画問題による計算により適切な提供元サーバを選択すると共に、サービス要求元（ノード）-選択されたサーバ（ノード）とをつなぐ経路を求めることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施の形態におけるサーバ選択装置の構成図である。
【図２】本発明の一実施の形態における動作のフローチャートである。
【図３】本発明の一実施の形態におけるネットワークの例である。
【図４】本発明の一実施の形態における結果（４９番ノードの場合）である。
【発明を実施するための形態】
【００１６】
以下図面と共に、本発明の実施の形態を説明する。
【００１７】
最初に本発明の概要を説明する。
【００１８】
本発明は、要求元から要求するコンテンツ毎のトラヒックに対して、複数のコンテンツ配信（サービス提供元）サーバから目的に沿ったサーバの選択と、選択したサーバ-要求元間の経路を決定する方法をモデル化し、線形計画問題として計算する。具体的には、入力として、リンクの利用可能帯域、トポロジなどのネットワーク情報と、要求元ノードの各コンテンツに対するトラヒック量（要求トラヒック量）を入力として与え、計算結果である要求元-サーバ間の経路情報をルータ内のルーティングテーブルに反映させることによって、特定のリンクへの負荷を分散し、サービス機能の低下を防ぐ。モデルはネットワークのルータなどの通信機器をノード、機器間をつなぐケーブルをリンクとみなした、グラフ問題としてモデル化したものである。このとき、実際にサービスを利用するために用いる機器(PC等)や、サービス提供のために用いる機器(サーバ、ストレージ等)はグラフ上の要求元ノード、サーバノードに繋がっていると仮定する。
【００１９】
モデルは、リンクが向きを持たない無向グラフを前提として考える。無向グラフ、かつ、複数の種類のトラヒックが流れる通信ネットワークを扱う問題の場合、多品種フロー問題のモデルが用いられる。しかし、多品種フロー問題は1つの送信側ノードから1つの受信側ノードにトラヒックを流すという、単発単着の形になっており、今回想定している複数のサービス提供元があるような複発単着の形には適さない。そのため、本発明では、送信側（サーバ）ノードから流れるトラヒック量の総計が受信側（要求元）ノードの要求トラヒック量と等しくなるようにした複発単着モデルを用いた線形計画問題計算する。
【００２０】
図１は、本発明の一実施の形態におけるサーバ選択装置の構成を示す。
【００２１】
同図に示すサーバ選択装置１は、データベース部１００、計算部２００、ネットワーク運用部３００から構成される。
【００２２】
データベース部１００は、リンクの利用可能帯域、トポロジなどのネットワーク情報を格納し、計算部２００からアクセスされることにより、格納されているデータを出力する。具体的に、データベース部１００に格納される情報は、
・ネットワーク形状：ノード，ノード間におけるリンクの有無
・リンク情報：容量，コスト
・配信サーバの位置：どのノードがサーバノードであるかに関する情報
・要求トラヒック情報(初期値)：各ノードのコンテンツ毎の要求トラヒック量
等である。
【００２３】
計算部２００は、要求トラヒック量計算部２１０とサーバ選択/サーバノード-要求元ノード間経路決定部２２０から構成される。
【００２４】
また、ネットワーク運用部３００は、ネットワーク経路制御部３１０、ネットワーク情報観測部３２０から構成される。
【００２５】
要求トラヒック量計算部２１０は、後述するネットワーク運用部３００のネットワーク情報観測部３２０から定期的に提供される、各ノードにおけるコンテンツ毎のトラヒック量から要求トラヒック情報を作成し、サーバ選択/サーバノード-要求元ノード間経路決定部２２０に出力する。
【００２６】
サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、システム初期はデータベース部１００から提供されるネットワーク情報と前述したモデル（複発単着のモデル）を用いて、目的に沿ったサーバの選択、該当サーバノード-要求元ノード間のネットワーク経路を計算し、解であるネットワーク経路情報をネットワーク運用部３００ネットワーク経路制御部３１０に提供する。初期動作後は、定期的にデータベース部１００のネットワーク情報と、要求トラヒック量計算部２１０から提供される要求トラヒック情報を用いて、同様の計算を行い、ネットワーク経路制御部３１０に提供する。
【００２７】
ネットワーク運用部３００のネットワーク経路制御部３１０は、サーバ選択/サーバノード-要求元ノード間経路決定部２２０から入力されるネットワーク経路情報を用いて、ネットワークの経路設定を行う。経路設定自体は、MPLS（例えば、文献１：E. Rosen, a. Viswanathan and R. Callon, "RFC 3031 Multiprotocol Label Switching Architecture," 2001, Jan.参照）、OpenFlow（例えば、文献２："The OpenFlow Switch Consortium," http://www.openflowswitch.org/）などの既存技術を用いる。
【００２８】
ネットワーク情報観測部３２０は、ネットワークのトラヒック量を定期的に観測し、要求トラヒック量計算部２１０に出力する。トラヒックの観測自体は、OpenFlowなどのフローレベル、もしくはQoSの品質クラスレベルで測定可能な既存技術を用いる。
【００２９】
なお、図１では、サーバ選択装置１内にネットワーク運用部３００を含む構成としているが、これに限定されることなく、サーバ選択装置１の外部に設けることも可能である。
【００３０】
図２は、本発明の一実施の形態における動作のフローチャートである。
【００３１】
ステップ１０１） ネットワーク運用部３００のネットワーク情報観測部３２０は、ネットワークの各ノードにおけるコンテンツ毎のトラヒック量を定期的に観測し、計算部２００の要求トラヒック量計算部２１０に出力する。
【００３２】
ステップ１０２） 要求トラヒック量計算部２１０は、ネットワーク情報観測部３２０から入力された各ノードにおけるコンテンツ毎のトラヒック量から要求トラヒック情報を作成し、サーバ選択/サーバノード-要求元ノード間経路決定部２２０に出力する。
【００３３】
ステップ１０３） サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、データベース部１００から、ネットワーク形状、ノード情報、ノードのリンク情報、容量、コスト、サーバノードの位置情報、要求トラヒックの情報を読み出す。
【００３４】
ステップ１０４） サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、データベース部１００から読み込んだ情報と、要求トラヒック量計算部２１０から入力された要求トラヒック情報から複発単着モデル（後述する変数と制約式を参照）を用いて、サーバを選択し、該当サーバノード-要求元ノード間のネットワーク経路を計算し、ネットワーク運用部３００のネットワーク経路制御部３１０に出力する。
【００３５】
ステップ１０５） ネットワーク運用部３００のネットワーク経路制御部３１０は、入力されたネットワーク経路情報を、ルータ内のルーティングテーブルに反映させることによってネットワークの経路の設定を行う。
【００３６】
以下に、計算部２００のサーバ選択/サーバノード-要求元ノード間経路決定部２２０の処理について詳細に説明する。
【００３７】
計算部２００のサーバ選択/サーバノード-要求元ノード間経路決定部２２０に用いられる数式モデルの一例を以下に示す。
【００３８】
＜変数＞
ｍ：コンテンツを要求する要求元ノードを示す識別番号
ｎ：コンテンツを配信するサーバノードを示す識別番号
ｌ： コンテンツの種類を示す識別番号
ｘ：各リンクにおける要求元ノードmが要求するコンテンツlのトラヒック量
ｄ：要求元ノードmが要求するコンテンツlの需要トラヒック量
U：リンク容量
S：コンテンツlを要求する要求元ノードmの集合
D：コンテンツlを配信するサーバノードnの集合
Ｎ'k：リンクの片端をノードkとしたときの他端ノードの集合
c：リンク上にトラヒックが流れたときのコスト
＜制約式＞
サーバ選択/サーバノード-要求元ノード間経路決定部２２０で用いられる制約式は以下のとおりである。以下の各制約式の変数は上述のとおりである。
【００３９】
【数１】
上記の（１）〜（６）の式の意味は以下のとおりである。
【００４０】
（１）ノードkが要求元ノードの場合、ノードkに流れてくるトラヒック量(流入トラヒック量)とノードkから流れていくトラヒック量(流出トラヒック量)の差が-d(要求トラヒック量)になることを示している。
【００４１】
（２）ノードkが要求元ノード、サーバノードでない場合、ノードkにおける入入トラヒック量と流出トラヒック量が等しく、フロー保存則に従うことを示している。
【００４２】
（３）、（４）ノードkがサーバノードの場合、各ノードkにおける流入トラヒック量と流出トラヒック量の差の総計がd(要求トラヒック量)になることを示している。
【００４３】
（５）各リンクに流れるトラヒック量がリンク容量以下になることを示している。
【００４４】
（６）xはトラヒック量のため、0以上、需要トラヒック量以下の連続値をとることを示している。
【００４５】
＜目的値＞
最適化に用いる目的値は以下のとおりである。
【００４６】
【数２】
（７）リンク毎に流れるトラヒック量とコストの積の総計を最小化することを示している。
【００４７】
サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、上記の（１）〜（７）に示すモデルを用いて図３に示すようなネットワークに対して、経路を決定するものとする。
【００４８】
図３において、黒い三角マークがサーバノードであり、その他のノードを今回は要求元ノードとしている。コンテンツは1種類、各リンク容量は一律15.0Gbps、各要求元ノードの要求トラヒック量は0.1Gbpsから10.0Gbpsの範囲を一様乱数で設定した。
【００４９】
上記の制約式を適用すると、モデルの出力は各リンクにおけるトラヒック量xであり、ノードiからノードjに流れる、要求元ノードm，コンテンツlのトラヒック量を示している。
【００５０】
結果の一例として、図３の49番ノード(要求トラヒック量:9.7Gbps)の場合を述べる。
【００５１】
図４は、m(要求元ノード)=49、l(コンテンツ番号)=1における、各リンクのトラヒック量xを示している。なお、トラヒック量が0のリンクのものに関しては省略している。図４に示すように、49番ノードにサービスを行うサーバは29番ノードと23番ノードになり、それぞれ、(1)-(3)-(5)、(2)-(4)-(6)の経路を使うことになる。
【００５２】
サーバ選択/サーバノード-要求元ノード間経路決定部２２０は、選択されたサーバ及び、求められた経路をネットワーク経路制御部３１０に出力する。これにより、ネットワーク経路制御部３１０は、ネットワーク上の経路に得られた解を反映させて経路設定を行うことができる。
【００５３】
上記のように、本発明はトラヒック発生によるコストを最小化することを目的として、適切なサーバの選択と、選択されたサーバノード-要求元ノード間の経路を最適化する。これにより、最短経路ではリンク容量を超えるトラヒックが生じる場合に、コストを考慮した上でリンク負荷を分散するネットワーク運用を可能にする。
【００５４】
また、上記の式(7)を目的に沿って変更することで、例えばリンク使用率(リンク容量におけるトラヒック量の割合)の最大値を下げると言った効果も期待できる。
【００５５】
また、図１に示すサーバ選択装置の構成要素の各動作をプログラムとして構築し、サーバ選択装置として用いられるコンピュータにインストールする、または、ネットワークを介して流通させることが可能である。
【００５６】
また、構築されたプログラムをハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００５７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５８】
１ サーバ選択装置
１００ データベース部
２００ 計算部
２１０ 需要トラヒック量計算部
２２０ サーバ選択／サーバノード−要求元ノード間経路決定部
３００ ネットワーク運用部
３１０ ネットワーク経路制御部
３２０ ネットワーク情報観測部
【特許請求の範囲】
【請求項１】
映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスのといった、サービス提供元となるサーバがネットワーク上の複数の箇所に存在する環境において、サービス提供元サーバを選択するサーバ選択方法であって、
ネットワーク情報を格納した記憶手段と、
定期的にネットワークの混雑状況を観測するネットワーク情報観測手段と、
各要求元ノードのコンテンツに対する要求トラヒック量を求める要求トラヒック量計算手段と、
前記要求トラヒック量と前記記憶手段のネットワーク情報に基づいて各要求元に適したサーバノードを選択し、ノード間の経路を決定するサーバ・経路決定手段と、を有する装置において、
前記サーバ・経路決定手段が、前記サービス提供元となるサーバに対するコンテンツ要求に対して、前記記憶手段から取得した前記ネットワーク情報と前記要求トラヒック量に基づいて、送信側（サーバ）ノードから流れるトラヒック量の総計が受信側（要求元）ノードの要求トラヒック量と等しくなるように、複発単着のモデルとして線形計画問題を計算することでサービス提供元となるサーバを選択し、選択されたサーバ-要求元ノード間の経路を求めるサーバ・経路決定ステップを行う
ことを特徴とするサーバ選択方法。
【請求項２】
映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元となるサーバがネットワーク上の複数の箇所に存在する環境において、サービス提供元サーバを選択するサーバ選択装置であって、
ネットワーク情報を格納した記憶手段と、
定期的にネットワークの混雑状況を観測するネットワーク情報観測手段と、
各要求元ノードのコンテンツに対する要求トラヒック量を求める要求トラヒック量計算手段と、
前記サービス提供元となるサーバに対するコンテンツ要求に対して、前記記憶手段から取得した前記ネットワーク情報と前記要求トラヒック量計算手段から取得した前記要求トラヒック量に基づいて、送信側（サーバ）ノードから流れるトラヒック量の総計が受信側（要求元）ノードの要求トラヒック量と等しくなるように、複発単着のモデルとして線形計画問題を計算することでサービス提供元となるサーバを選択し、選択されたサーバ-要求元ノード間の経路を求めるサーバ・経路決定手段と、
を有することを特徴とするサーバ選択装置。
【請求項３】
請求項２に記載のサーバ選択装置を構成する各手段としてコンピュータを機能させるためのサーバ選択プログラム。
【請求項１】
映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスのといった、サービス提供元となるサーバがネットワーク上の複数の箇所に存在する環境において、サービス提供元サーバを選択するサーバ選択方法であって、
ネットワーク情報を格納した記憶手段と、
定期的にネットワークの混雑状況を観測するネットワーク情報観測手段と、
各要求元ノードのコンテンツに対する要求トラヒック量を求める要求トラヒック量計算手段と、
前記要求トラヒック量と前記記憶手段のネットワーク情報に基づいて各要求元に適したサーバノードを選択し、ノード間の経路を決定するサーバ・経路決定手段と、を有する装置において、
前記サーバ・経路決定手段が、前記サービス提供元となるサーバに対するコンテンツ要求に対して、前記記憶手段から取得した前記ネットワーク情報と前記要求トラヒック量に基づいて、送信側（サーバ）ノードから流れるトラヒック量の総計が受信側（要求元）ノードの要求トラヒック量と等しくなるように、複発単着のモデルとして線形計画問題を計算することでサービス提供元となるサーバを選択し、選択されたサーバ-要求元ノード間の経路を求めるサーバ・経路決定ステップを行う
ことを特徴とするサーバ選択方法。
【請求項２】
映像配信サービスや、ネットワーク上でアプリケーションやストレージを提供するクラウドサービスといった、サービス提供元となるサーバがネットワーク上の複数の箇所に存在する環境において、サービス提供元サーバを選択するサーバ選択装置であって、
ネットワーク情報を格納した記憶手段と、
定期的にネットワークの混雑状況を観測するネットワーク情報観測手段と、
各要求元ノードのコンテンツに対する要求トラヒック量を求める要求トラヒック量計算手段と、
前記サービス提供元となるサーバに対するコンテンツ要求に対して、前記記憶手段から取得した前記ネットワーク情報と前記要求トラヒック量計算手段から取得した前記要求トラヒック量に基づいて、送信側（サーバ）ノードから流れるトラヒック量の総計が受信側（要求元）ノードの要求トラヒック量と等しくなるように、複発単着のモデルとして線形計画問題を計算することでサービス提供元となるサーバを選択し、選択されたサーバ-要求元ノード間の経路を求めるサーバ・経路決定手段と、
を有することを特徴とするサーバ選択装置。
【請求項３】
請求項２に記載のサーバ選択装置を構成する各手段としてコンピュータを機能させるためのサーバ選択プログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−４４６２２（Ｐ２０１２−４４６２２Ａ）
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願番号】特願２０１０−１８６６３１（Ｐ２０１０−１８６６３１）
【出願日】平成２２年８月２３日（２０１０．８．２３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願日】平成２２年８月２３日（２０１０．８．２３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]