(57)【特許請求の範囲】
【請求項１】
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置であって、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力部と、
前記パラメタ入力部において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計部と、
前記選択確率設計部において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力部と、
を有し、
前記選択確率設計部は、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、キャッシュサーバの選択確率を設計する配信サーバ又は配信ルート設計装置。
【請求項２】
前記パラメタ入力部は、
コンテンツ数M、
ノード数N、
モデル予測制御の予測ホライズンH、
キャッシュサーバsのキャッシュサーバ配信容量CC,s、
タイムスロットtにおけるユーザuからのコンテンツmに対して発生する配信デマンド量du,m,tの需要推定量
【数５８】
0005888687.tif 000063
タイムスロットtにおいてコンテンツmを保持するキャッシュサーバ集合
【数５９】
0005888687.tif 000064
キャッシュサーバsからユーザuまでの経路候補集合
【数６０】
0005888687.tif 000065
t+1≦k≦t+Hの範囲のタイムスロットkにおけるキャッシュサーバsからユーザuまでのホップ長hs,u,k、
超過配信要求数の抑制のための目的関数Jsに対する配信フローの平均ホップ数の低減ための目的関数Jhの重みパラメタwh、及び
目的関数Jsに対するキャッシュサーバsの選択確率pu,m,k(s)の変化量の抑制のための目的関数Jv,pの重みパラメタwv,pを受け取り、
前記選択確率設計部は、
タイムスロットt-1におけるキャッシュサーバsの超過配信回数ζs,t-1に対して、タイムスロットtにおいてキャッシュサーバsから配信される配信フローの総数gs,tを
【数６１】
0005888687.tif 000066
により計算し、また、x＞0のときにxを、x≦0のときに0をとる演算子[x]+を用いて、ζs,t-1=[gs,t-1-CC,s]+でζs,t-1を算出し、
目的関数Jsを
【数６２】
0005888687.tif 000067
により定義し、
更に、目的関数Jhを
【数６３】
0005888687.tif 000068
により定義し、
更に、目的関数Jv,pを
【数６４】
0005888687.tif 000069
により定義し、
Js+whJh+wv,pJv,pを最小化する非線形計画問題によって、タイムスロットtの終了時点においてt+1≦k≦t+Hの範囲のタイムスロットkに対する選択確率pu,m,k(s)を最適化する、請求項１に記載の配信サーバ又は配信ルート設計装置。
【請求項３】
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置であって、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力部と、
前記パラメタ入力部において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計部と、
前記選択確率設計部において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力部と、
を有し、
前記選択確率設計部は、リンクを通る配信フローの総数の低減、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、配信ルートの選択確率を設計する配信サーバ又は配信ルート設計装置。
【請求項４】
前記パラメタ入力部は、
コンテンツ数M、
ノード数N、
モデル予測制御の予測ホライズンH、
キャッシュサーバsのキャッシュサーバ配信容量CC,s、
リンクeのリンク転送容量CL,e、
タイムスロットtにおけるユーザuのコンテンツmに対する配信ルート集合
【数６５】
0005888687.tif 000070
タイムスロットtにおけるユーザuからのコンテンツmに対して発生する配信デマンド量du,m,tの需要推定量
【数６６】
0005888687.tif 000071
タイムスロットtにおいてコンテンツmを保持するキャッシュサーバ集合
【数６７】
0005888687.tif 000072
キャッシュサーバsからユーザuまでの経路候補集合
【数６８】
0005888687.tif 000073
タイムスロットtにおいてキャッシュサーバsからユーザuへの経路候補rがリンクeを通る場合に1となる二値変数Is,u,t(r,e)、
t+1≦k≦t+Hの範囲のタイムスロットkにおけるキャッシュサーバsからユーザuまでのホップ長hs,u,k、
超過配信要求数の抑制のための目的関数Jsに対するリンクeを通る配信フローの総数の低減のための目的関数Jeの重みパラメタwe、
超過配信要求数の抑制のための目的関数Jsに対する配信フローの平均ホップ数の低減ための目的関数Jhの重みパラメタwh、及び
目的関数Jsに対する送信元がsで経路がrの配信ルートφu,m,t(s,r)の選択確率
【数６９】
0005888687.tif 000074
の変化量の抑制のための目的関数
【数７０】
0005888687.tif 000075
の重みパラメタ
【数７１】
0005888687.tif 000076
を受け取り、
前記選択確率設計部は、
タイムスロットt-1におけるリンクeの超過配信回数ηe,t-1に対して、タイムスロットtにおいてリンクeを通る配信フローの総数fe,tを
【数７２】
0005888687.tif 000077
により計算し、また、x＞0のときにxを、x≦0のときに0をとる演算子[x]+を用いて、ηe,t-1=[fe,t-1-CL,e]+でηe,t-1を算出し、
目的関数Jeを
【数７３】
0005888687.tif 000078
により定義し、
タイムスロットt-1におけるキャッシュサーバsの超過配信回数ζs,t-1に対して、タイムスロットtにおいてキャッシュサーバsから配信される配信フローの総数gs,tを
【数７４】
0005888687.tif 000079
により計算し、また、x＞0のときにxを、x≦0のときに0をとる演算子[x]+を用いて、ζs,t-1=[gs,t-1-CC,s]+でζs,t-1を算出し、
目的関数Jsを
【数７５】
0005888687.tif 000080
により定義し、
更に、目的関数Jhを
【数７６】
0005888687.tif 000081
により定義し、
更に、目的関数
【数７７】
0005888687.tif 000082
を
【数７８】
0005888687.tif 000083
により定義し、
【数７９】
0005888687.tif 000084
を最小化する非線形計画問題によって、タイムスロットtの終了時点においてt+1≦k≦t+Hの範囲のタイムスロットkに対する選択確率
【数８０】
0005888687.tif 000085
を最適化する、請求項３に記載の配信サーバ又は配信ルート設計装置。
【請求項５】
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置における配信サーバ又は配信ルート設計方法であって、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るステップと、
前記受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計するステップと、
前記設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力するステップと、
を有し、
前記設計するステップにおいて、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、キャッシュサーバの選択確率を設計する配信サーバ又は配信ルート設計方法。
【請求項６】
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置における配信サーバ又は配信ルート設計方法であって、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るステップと、
前記受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計するステップと、
前記設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力するステップと、
を有し、
前記設計するステップにおいて、リンクを通る配信フローの総数の低減、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、配信ルートの選択確率を設計する配信サーバ又は配信ルート設計方法。
【請求項７】
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計するために、コンピュータを、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力手段、
前記パラメタ入力手段において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計手段、及び
前記選択確率設計手段において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力手段、
として機能させ、
前記選択確率設計手段は、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、キャッシュサーバの選択確率を設計するためのプログラム。
【請求項８】
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計するために、コンピュータを、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力手段、
前記パラメタ入力手段において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計手段、及び
前記選択確率設計手段において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力手段、
として機能させ、
前記選択確率設計手段は、リンクを通る配信フローの総数の低減、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、配信ルートの選択確率を設計するためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配信サーバ又は配信ルート設計装置、配信サーバ又は配信ルート設計方法及びプログラムに関する。特に、本発明は、ネットワーク(NW)の複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信するコンテンツ配信NW(Contents Delivery Network、以下、CDN)において、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置、配信サーバ又は配信ルート設計方法及びプログラムに関する。
【背景技術】
【０００２】
インターネットは個々のフローの状態を網内で管理せず受信アドレスに基づきルーティング処理を行う。各ISP(Internet Service Provider)が管理する単一AS(Autonomous System)内では、OSPF(Open Shortest Path First)により固定的に設定されたリンク重みの総和が最小となる経路上にパケットが転送される。また、フローの受付制御を行わず転送レートは送信ホストが自律的に決定するため、原理的にリンク輻輳が発生し得る。そのため適切な通信品質を維持するために、NWを構成する全てのリンクの負荷が適切な水準以下となるようNWを設計・管理することがISPの主要な課題の一つとなる。リンク負荷は交流トラヒックデマンドの変動や各種障害に起因する経路の変更によって常に変化する。そのため使用率の低いリンクを積極的に利用するようパケットの流れる経路を動的に設定し、リンク負荷の分散を図る経路制御法が数多く検討されている。
【０００３】
ところで近年、インターネットのトラヒックの多くの部分をWebサービスで用いられるHTTP(Hypertext Transfer Protocol)トラヒックが占めている。例えば2006年〜2008年の間に日米間のバックボーンリンクで測定されたトラヒックの分析によると、HTTPパケットが約60%を占めている。またYouTube(登録商標)等のUGC(User-Generated Contents)やVoD(Video On Demand)のリッチコンテンツのトラヒック量も急増しており、インターネット上のトラヒックの多くは、これらコンテンツ配信によるものが大部分を占めている。コンテンツ配信はCDN事業者が運用するCDNを用いて配信される形態が一般的であり、例えばアクセス数上位1,000のサイトの中では74%がCDNを利用している。CDNは多数のNW上に分散配置されたキャッシュサーバにコンテンツのコピーを置きオリジナルサーバに代わって配信することで、ユーザ品質の向上とNW内トラヒック量の抑制を図っている。そのためコンテンツ配信において発生する配信フローの発ノード位置は、コンテンツ配置法やサーバ選択法によって決まり、ユーザ品質やNW内トラヒック量はこれらの制御法に強く影響を受ける。CDNはISPとは独立したAkamai等のCDN事業者により運営され、アプリケーション層においてオーバレイ的にキャッシュサーバから配信を行っており、ISPがサーバ選択法やコンテンツ配置法についての情報を得ることは困難である。そのためISPが経路制御を、CDN事業者がサーバ選択(もしくはコンテンツ配置)を各々、独立して実施している。
【０００４】
ISPがパケットの転送経路を制御する方式については、これまでに多くの研究が見られる。例えばFortzらはリンクを流れるトラヒック量の関数として定義されたリンクコストの総和が最小化するよう、OSPFのリンク重みを設計する方法を提案している。またBensonらは短期間先のトラヒック交流の予測に基づき短い時間周期で経路制御を行う方式を提案しており、Dannaらはユーザに割当てられる帯域の公平性とネットワーク資源の利用効率との間のトレードオフを考慮して適正な経路制御を行う問題を線形計画問題で定式化している。さらにKandulaらはスループットの測定値に基づき適応的に経路を設定する方式を提案している。また目的アドレスより細かな粒度で経路制御を行う方式も検討されており、例えばElwalidらはMPLS(Multi-Protocol Label Switching)を対象に、LSP(Label Switched Path)の経路を総リンクコストが最小化するよう最適設計する問題を線形計画問題で定式化しており、HongらやJainらはデータセンタ間NWにSDN(Software Defined Network)を用いることで、細粒度で短期間に経路を切替るTE(Traffic Engineering)方式を提案している。これらの方式はISPが経路制御を行うことを想定しているが、エンドユーザが実測情報に基づきオンライン最適化により経路を最適選択する方式も検討されている。また様々な経路制御方式の効果を、ユーザ体感品質の観点から分析した研究も見られる。
【０００５】
同様にCDN事業者が配信要求に対してどのサーバから配信するかを選択するサーバ選択法に関しても様々な研究が見られる。例えばPoeseらは、ISPがCDN事業者に対してネットワーク状態に関する情報を提供することで、CDN事業者がサーバ選択を適正に行うことを提案している。またサーバ選択ではなく、コンテンツをどの位置にキャッシュするかを制御することで配信元位置の適正化を図る研究も見られる。例えばApplegateらは、キャッシュ容量とリンク帯域との制約条件のもとで、ネットワーク内を流れる総トラヒック量を最小化するよう各コンテンツの配置位置を決める問題を混合整数計画問題で定式化している。またTangらはユーザ品質の制約条件を考慮してコンテンツ配置に要するレプリケーションコストを最小化するコンテンツ配置設計法を提案している。
【０００６】
以上の技術については、非特許文献1、2を参照されたい。
【０００７】
しかしISPの経路制御はCDN事業者のサーバ選択の効果に影響を与え、逆にCDN事業者のサーバ選択はISPの経路制御の効果に影響を与えることから、各々の制御方式を検討する際にはISPとCDN事業者の制御が相手の制御結果に与える影響を考慮する必要がある。例えばDiPalantinoらはゲーム理論を用いて両者の戦略をモデル化し、実現される均衡状態について分析している。またISPとCDN事業者が協調してサーバ選択を行う研究も見られ、例えばPoeseらはパッシブキャプチャデータを分析することで、コンテンツ配信時にDNS(Domain Name System)が回答する配信サーバのアドレスには多様性があり、ISPがサーバ選択を行うことでレスポンス時間の改善が期待されることを述べている。またFrankらはCDN事業者とISPとが協調してサーバ選択を行うための必要な情報を交換する方法について提案している。
【０００８】
また、JiangらはISPが経路を、CDN事業者がサーバ選択を各々独立に行う状況において、互いの保有する情報を相手に伝えることでどの程度、全体最適な状態に近づくかを分析している。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】I. Poese, B. Frank, B. Ager, G. Smaragdakis, and A. Feldmann, Improving Content Delivery Using Provider-aided Distance Information, ACM IMC 2010.
【非特許文献２】I. Poese, B. Frank, G. Smaragdakis, S. Uhlig, A. Feldmann, and B. Maggs, Enabling Content-aware Traffic Engineering, ACM SIGCOMM Computer Communication Review, Vol.42, NO.5, pp.22-28, 2012.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
このようにISPが経路制御を、CDN事業者がサーバ選択(もしくはコンテンツ配置)を各々、適切に行う方式に関して様々な検討が見られる。しかしISPの経路制御はCDN事業者のサーバ選択の効果に影響を与え、逆にCDN事業者のサーバ選択はISPの経路制御の効果に影響を与える。そのためISPとCDN事業者の制御が相手の制御結果に与える影響を考慮する必要がある。
【００１１】
ところが近年、Google等の大規模コンテンツプロバイダや、AT&T等のTier-1 ISPが自身でCDNを運用するケースも増えてきている。またISPとCDN事業者とが協力し、互いの情報を交換しながら経路制御とサーバ選択を適切に行う方式も提案されている。このようにコンテンツ配信における配信経路とサーバ選択を同時に最適化することが可能な環境が整いつつある。
【００１２】
上記のISPとCDN事業者が協調してサーバ選択を行うPoeseらの文献やFrankらの文献では、ISPがサーバ選択を行うことが提案されているが、ISPが同時に経路制御を行うことは考慮されていない。
【００１３】
また、コンテンツ配信における各コンテンツに対する需要量や人気度は時間的に大きく変化することから、配信経路とサーバ選択を最適化するためには、ダイナミックに変化する需要に対して適応的に制御する必要がある。そのためには将来の需要を精度よく推定できることが望ましい。コンテンツ人気度の時間的な推移の予測手法が検討されているが、高精度に予測を行うことは困難である。そのため予測誤差も考慮に入れトラヒック予測と連携して各種制御を行うことが有効と思われる。
【００１４】
Jiangらの文献では、単一時点における全体最適化を目指しており、将来にわたってトラヒック交流が変化し続ける実際のネットワークには適用が困難である。将来のトラヒック需要の予測が困難な複数の期間において適正な状態を実現するためには、時系列的に最適化処理が反復できる方式が求められる。
【００１５】
本発明は、CDNにおいて、ユーザからの配信要求が時間的に変化するときにユーザからの配信要求が棄却される頻度を抑制し、CDNサービスの向上を図ることを目的とする。
【課題を解決するための手段】
【００１６】
本発明の一形態に係る配信サーバ又は配信ルート設計装置は、
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置であって、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力部と、
前記パラメタ入力部において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計部と、
前記選択確率設計部において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力部と、
を有し、
前記選択確率設計部は、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、キャッシュサーバの選択確率を設計することを特徴とする。
また、本発明の一形態に係る配信サーバ又は配信ルート設計装置は、
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置であって、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力部と、
前記パラメタ入力部において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計部と、
前記選択確率設計部において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力部と、
を有し、
前記選択確率設計部は、リンクを通る配信フローの総数の低減、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、配信ルートの選択確率を設計することを特徴とする。
【００１７】
また、本発明の一形態に係る配信サーバ又は配信ルート設計方法は、
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置における配信サーバ又は配信ルート設計方法であって、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るステップと、
前記受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計するステップと、
前記設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力するステップと、
を有し、
前記設計するステップにおいて、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、キャッシュサーバの選択確率を設計することを特徴とする。
また、本発明の一形態に係る配信サーバ又は配信ルート設計方法は、
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置における配信サーバ又は配信ルート設計方法であって、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るステップと、
前記受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計するステップと、
前記設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力するステップと、
を有し、
前記設計するステップにおいて、リンクを通る配信フローの総数の低減、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、配信ルートの選択確率を設計することを特徴とする。
【００１８】
また、本発明の一形態に係るプログラムは、
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計するために、コンピュータを、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力手段、
前記パラメタ入力手段において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計手段、及び
前記選択確率設計手段において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力手段、
として機能させ、
前記選択確率設計手段は、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、キャッシュサーバの選択確率を設計することを特徴とする。
また、本発明の一形態に係るプログラムは、
ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信する際に、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計するために、コンピュータを、
ネットワークに関するパラメタと、ユーザからのコンテンツに対して発生する配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力手段、
前記パラメタ入力手段において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計手段、及び
前記選択確率設計手段において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力手段、
として機能させ、
前記選択確率設計手段は、リンクを通る配信フローの総数の低減、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行いつつ、超過配信要求数を抑制するよう、配信ルートの選択確率を設計することを特徴とする。
【発明の効果】
【００１９】
本発明によれば、CDNにおいて、ユーザからの配信要求が変化するときにユーザからの配信要求が棄却される頻度を抑制し、CDNサービスの向上を図ることが可能になる。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施形態に係る配信サーバ又は配信ルート設計装置の構成図
【図２】本発明の一実施形態に係る配信サーバ選択確率最適設計装置の構成図
【図３】本発明の一実施形態に係る配信ルート選択確率最適設計装置の構成図
【図４】CDNの動作メカニズムを示す概略図
【図５】モデル予測制御の最適化フローを示す概略図
【図６】本発明の一実施形態に係る配信ルート選択確率最適設計装置に入力される配信ルート集合の例を示す図
【図７】本発明の一実施形態に係る配信サーバ又は配信ルート設計装置の性能評価に用いたネットワークトポロジの図
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施形態について説明する。
【００２２】
本発明の実施形態では、ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信するCDNにおいて、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバを選択する確率や、配信経路と配信サーバの組である配信ルートを選択する確率を、配信要求が棄却される超過配信要求を抑制するように設計する手法について説明する。
【００２３】
＜装置構成＞
図１は、本発明の一実施形態に係る配信サーバ又は配信ルート設計装置１００の構成図である。配信サーバ又は配信ルート設計装置１００は、ネットワークの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信するCDNにおいて、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバを選択する確率を、配信要求が棄却される超過配信要求を抑制するように設計する装置である。また、配信サーバ又は配信ルート設計装置１００は、配信経路と配信サーバの組である配信ルートを選択する確率を、配信要求が棄却される超過配信要求を抑制するように設計する装置でもある。
【００２４】
配信サーバ又は配信ルート設計装置１００は、プロセッサ等のＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）等のメモリ装置、ハードディスク等の記憶装置等から構成されたコンピュータでもよい。例えば、配信サーバ又は配信ルート設計装置１００の機能及び処理は、記憶装置又はメモリ装置に格納されているデータやプログラムをＣＰＵが実行することによって実現される。
【００２５】
配信サーバ又は配信ルート設計装置１００は、パラメタ入力部１０１と、選択確率設計部１０２と、選択確率出力部１０３とを有する。
【００２６】
パラメタ入力部１０１は、配信サーバの選択確率又は配信ルートの選択確率をモデル予測制御（MPC：Model Predictive Control）を用いて設計するために必要な入力パラメタ値を受け取る。具体的には、パラメタ入力部１０１は、ネットワークに関するパラメタ及びユーザからのコンテンツに対して発生する配信要求の需要推定量を受け取る。
【００２７】
選択確率設計部１０２は、パラメタ入力部１０１において受け取った入力パラメタ値に基づき、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率をモデル予測制御を用いて設計する。また、選択確率設計部１０２は、キャッシュサーバの選択確率だけでなく、配信サーバがユーザにコンテンツを配信する配信経路も同時に設計してもよい。この場合、選択確率設計部１０２は、ユーザからのコンテンツに対して発生する配信要求が棄却される超過配信要求を抑制するよう、配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する。
【００２８】
選択確率出力部１０３は、選択確率設計部１０２において設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する。
【００２９】
図１の配信サーバ又は配信ルート設計装置１００は、図２に示すように、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバを選択する確率を、キャッシュサーバの容量超過により、すなわち、キャッシュサーバの配信能力超過により配信要求が棄却される超過配信要求の頻度を最小化するよう最適設計する配信サーバ選択確率最適設計装置２００として構成されてもよい。
【００３０】
図２は、本発明の一実施形態に係る配信サーバ選択確率最適設計装置２００の構成図である。配信サーバ選択確率最適設計装置２００は、パラメタ入力部２０１と、キャッシュサーバ選択確率最適設計部２０２と、キャッシュサーバ選択確率出力部２０３とを有する。ここで、キャッシュサーバ選択確率最適設計部２０２は、超過配信要求数を抑制すると共に、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行ってもよい。すなわち、キャッシュサーバ選択確率最適設計部２０２は、超過配信要求数の抑制のための目的関数Js、配信フローの平均ホップ数の低減ための目的関数Jh、キャッシュサーバの選択確率の変化量の抑制のための目的関数Jv,pを同時に最適化してもよい。
【００３１】
パラメタ入力部２０１は、ネットワークにおけるコンテンツに関するパラメタ、キャッシュサーバに関するパラメタ及びユーザからのコンテンツに対して発生する配信要求の需要推定量を入力パラメタとして受け取る。具体的には、パラメタ入力部２０１によって、以下のパラメタが入力される。
【００３２】
・コンテンツ数M
・ノード数N
・MPCの予測ホライズンH、
・キャッシュサーバsのキャッシュサーバ配信容量CC,s、
・タイムスロットtにおけるユーザuからのコンテンツmに対して発生する配信デマンド量du,m,tの需要推定量
【００３３】
【数１】
0005888687.tif 000002
・タイムスロットtにおいてコンテンツmを保持するキャッシュサーバ集合
【００３４】
【数２】
0005888687.tif 000003
・キャッシュサーバsからユーザuまでの経路候補集合
【００３５】
【数３】
0005888687.tif 000004
・t+1≦k≦t+Hの範囲のタイムスロットkにおけるキャッシュサーバsからユーザuまでのホップ長hs,u,k
・目的関数Jsに対する目的関数Jhの重みパラメタwh
・目的関数Jsに対する目的関数Jv,pの重みパラメタwv,p
キャッシュサーバ選択確率最適設計部２０２は、パラメタ入力部２０１から入力されたパラメタ値に基づき、キャッシュサーバsの選択確率pu,m,k(s)を最適設計し、キャッシュサーバ選択確率出力部２０３によってpu,m,k(s)の設計値が出力される。
【００３６】
また、図１の配信サーバ又は配信ルート設計装置１００は、図３に示すように、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバを選択する確率を、配信サーバがユーザにコンテンツを配信する配信経路と共に、配信要求が棄却される超過配信要求の頻度を最小化するよう最適設計する配信ルート選択確率最適設計装置３００として構成されてもよい。
【００３７】
図３は、本発明の一実施形態に係る配信ルート選択確率最適設計装置３００の構成図である。配信ルート選択確率最適設計装置３００は、パラメタ入力部３０１と、配信ルート選択確率最適設計部３０２と、配信ルート選択確率出力部３０３とを有する。ここで、配信ルート選択確率最適設計部３０２は、超過配信要求数を抑制すると共に、リンクを通る配信フローの総数の低減、配信フローの平均ホップ数の低減及び選択確率の変化量の抑制を行ってもよい。すなわち、配信ルート選択確率最適設計部３０２は、超過配信要求数の抑制のための目的関数Js、リンクを通る配信フローの総数の低減のための目的関数Je、配信フローの平均ホップ数の低減ための目的関数Jh、配信ルートの選択確率の変化量の抑制のための目的関数
【００３８】
【数４】
0005888687.tif 000005
を同時に最適化してもよい。
【００３９】
パラメタ入力部３０１は、ネットワークにおけるコンテンツに関するパラメタ、キャッシュサーバに関するパラメタ及びユーザからのコンテンツに対して発生する配信要求の需要推定量に加えて、リンクに関するパラメタを入力パラメタとして受け取る。具体的には、パラメタ入力部３０１によって、以下のパラメタが入力される。
【００４０】
・コンテンツ数M
・ノード数N
・MPCの予測ホライズンH、
・キャッシュサーバsのキャッシュサーバ配信容量CC,s、
・リンクeのリンク転送容量CL,e、
・タイムスロットtにおけるユーザuのコンテンツmに対する配信ルート集合
【００４１】
【数５】
0005888687.tif 000006
・タイムスロットtにおけるユーザuからのコンテンツmに対して発生する配信デマンド量du,m,tの需要推定量
【００４２】
【数６】
0005888687.tif 000007
・タイムスロットtにおいてコンテンツmを保持するキャッシュサーバ集合
【００４３】
【数７】
0005888687.tif 000008
・キャッシュサーバsからユーザuまでの経路候補集合
【００４４】
【数８】
0005888687.tif 000009
・タイムスロットtにおいてキャッシュサーバsからユーザuへの経路候補rがリンクeを通る場合に1となる二値変数Is,u,t(r,e)、
・t+1≦k≦t+Hの範囲のタイムスロットkにおけるキャッシュサーバsからユーザuまでのホップ長hs,u,k
・目的関数Jsに対する目的関数Jeの重みパラメタwe、
・目的関数Jsに対する目的関数Jhの重みパラメタwh
・目的関数Jsに対する目的関数
【００４５】
【数９】
0005888687.tif 000010
の重みパラメタ
【００４６】
【数１０】
0005888687.tif 000011
配信ルート選択確率最適設計部３０２は、パラメタ入力部３０１から入力されたパラメタ値に基づき、配信ルートの選択確率
【００４７】
【数１１】
0005888687.tif 000012
を最適設計し、配信ルート選択確率出力部３０３によって
【００４８】
【数１２】
0005888687.tif 000013
の設計値が出力される。
【００４９】
次に、本発明の実施形態に係る配信サーバの選択手法及び配信ルートの選択手法について、詳細を説明する。
【００５０】
＜想定条件＞
ユーザのコンテンツ配信要求に対してCDNは、コンテンツを配信するキャッシュサーバ(もしくはオリジナルサーバ)を選択した後に配信を開始する。これら配信に先立つ処理として、本発明の実施形態では、一般的なCDN事業者で用いられている配信処理を想定する。代表的なCDN事業者の例にはAkamaiがある。
【００５１】
図４は、CDNの動作メカニズムを示す概略図である。ユーザは配信元サーバのIPアドレスをDNSにより解決する必要があるが、図４の(1)で示すように最初にローカルDNSサーバにIPアドレスを問い合わせる。要求コンテンツがローカルDNSにキャッシュされている場合にはそこからユーザ端末にコンテンツが配信される。キャッシュされていない場合は、CDN事業者のDNSサーバに問い合わせるようユーザ端末に回答され、ユーザ端末は図４の(2)に示すようにCDN事業者のDNSサーバに配信サーバのIPアドレスを問い合わせる。CDN事業者のDNSサーバは配信に用いるキャッシュサーバを選択してそのIPアドレスをユーザ端末に回答する。キャッシュサーバの選択基準はCDN事業者によって決められるが、多くの場合、実測レスポンス時間が短いものやユーザ端末の近くに存在するものが選択される。
【００５２】
ユーザ端末は図４の(3)に示すように、回答されたキャッシュサーバにコンテンツの配信を要求し、該当コンテンツがキャッシュされている場合にはそこから配信される(キャッシュヒット)。キャッシュされていない場合(キャッシュミス)には、そのキャッシュサーバは該当コンテンツのオリジナルを保有するオリジナルサーバに対して要求し、コンテンツを取得する(図４の(4))。そして取得コンテンツをキャッシュしてユーザ端末に配信する。キャッシュ容量が不足する場合には、キャッシュ済みコンテンツの中から何らかのポリシィに基づき選択したものを削除した後に新たに取得したコンテンツをキャッシュする。削除コンテンツの選択ポリシィとしては、最後に要求されてからの経過時間が最大のものを削除するLRU(least recently used)が用いられることが多い。
【００５３】
システム全体が固定時間長Tのタイムスロット(TS)に離散化されていることを想定する。NWとしては、単一のISPが管理するN個のノードとE本のリンクから構成された任意トポロジのNWを想定し、リンクeの伝送容量(各TS内で転送可能な総配信回数)はCL,eで与えられる。各ノードペアiからjのコンテンツ配信に用いる経路の候補集合
【００５４】
【数１３】
0005888687.tif 000014
が固定的に与えられ、ノードペアiからjに各コンテンツを配信する際、
【００５５】
【数１４】
0005888687.tif 000015
の任意の経路rを選択することで配信経路を決定する。ノードuが収容するユーザをユーザuと表記する。ユーザuには、ノードuに直接収容されたユーザや、ノードuが収容する下位のNWが収容するユーザが含まれる。ユーザuに対するコンテンツ配信フローの目的ノードはノードuとなる。
【００５６】
同一サイズのM個のコンテンツがNW全体で提供されており、TStにおいてユーザuから生じるコンテンツmの配信デマンド量(TSt内で生じる要求数)をdu,m,tとする。全てのノードにはオリジナルサーバが設置されており、各コンテンツは、任意の一つのノードにのみオリジナルが用意され、全期間を通してオリジナルの位置は不変とし、コンテンツmのオリジナルはノードomに存在する。ノードnに設置されたオリジナルサーバとキャッシュサーバを各々、オリジナルサーバn、キャッシュサーバnと表記し、オリジナルサーバnとキャッシュサーバnを合わせてサーバnと表記する。また配信フローのスループットは同一とする。
【００５７】
NW上の全てのノードにキャッシュサーバが設置されており、キャッシュサーバsのストレージ容量(最大キャッシュ可能コンテンツ数)をBsとする。キャッシュサーバやオリジナルサーバの配信処理容量は有限であり、キャッシュサーバsが各TS内で配信可能な総配信回数の上限をCC,sとする。ユーザuのコンテンツmへの配信要求に対して選択されたキャッシュサーバsにコンテンツmが保持されており(キャッシュヒット)、かつキャッシュサーバsの配信容量と選択された経路rが経由する全てのリンクに余裕がある場合には、キャッシュサーバsからコンテンツmが配信され、ノードsからユーザuに対して配信フローが発生する。
【００５８】
一方、キャッシュミス時やサーバやリンクの配信容量超過時には、コンテンツmのオリジナルサーバomの配信容量に余裕がある場合にはオリジナルサーバomからコンテンツmが配信され、ノードomからノードsへの配信フローとノードsからユーザuへの配信フローが発生し、新たにキャッシュサーバsにコンテンツmがキャッシュされる。キャッシュ容量が不足する場合の置換方式としてはLRUを想定する。さらにオリジナルサーバomからのサーバや経由リンクの配信容量が不足する場合には配信要求は棄却され、棄却された要求は超過配信要求として次のTSにおいて再度、発生するものとする。各キャッシュが保持するコンテンツはダイナミックに変化するが、TStの開始時点においてコンテンツmを保持しているキャッシュの集合を
【００５９】
【数１５】
0005888687.tif 000016
とする。
【００６０】
＜モデル予測制御(MPC)＞
MPCはシステムの動作(出力)が設定したターゲットに近づくようにシステムのパラメタ(入力)を最適化するのは従来のシステム制御と同様であるが、その際に現時刻だけではなく将来のある一定の区間(予測ホライズン)におけるシステムの振る舞いを考慮した上で、入力の最適化を行う。すなわちTSkの出力をyk、出力値のターゲットをYkとすると、現TStにおいて将来のHステップ先の区間[t+1,t+H]全体に渡ってykのターゲットからのずれ
【００６１】
【数１６】
0005888687.tif 000017
を最小化する入力列u(t+1),u(t+2),…,u(t+H)を導出する。ここで
【００６２】
【数１７】
0005888687.tif 000018
はxのユークリッドノルムを表す。上記の最適化を行う際には、TStにおいて入力xkが与えられた際の出力ykを予測することが必要となる。システムに入力を与えた時の出力の時間発展関係はシステムモデルとして表され、次式のようなシステムの各TSでの状態zkも考慮した状態空間モデルが主に用いられる。
zk+1=f(k,zk,xk)
yk=g(k,zk,xk)
ここでfとgは入力・出力・状態の関係性を表す関数である。しかしシステムのモデル化の際に誤差が含まれることがあり、それに基づいた出力の予測値
【００６３】
【数１８】
0005888687.tif 000019
は誤差が生じ得る。特に先の将来の予測ほど予測誤差が大きくなるため、予測ホライズン[t+1,t+H]において最適化した入力xt+1,…,xt+Hの内、実際にシステムに投入するのは直近のxt+1のみとする。以降の入力設定は観測フィードバックを元に予測値を修正し、再度入力の最適化を行うことで決定する。また予測誤差の影響を受けて過剰に入力変更を行いシステムが不安定になる可能性があるため、各TSでの入力の変更量Δxk=xk-xk-1を抑えることでシステムを安定化させる。すなわち予測ホライズン[t+1,t+H]全体においての入力の変更量
【００６４】
【数１９】
0005888687.tif 000020
をJ1と同時に最小化することを考え、J1とJ2のバランスを表すパラメタwを導入し、J1+wJ2を最小化する入力列xt+1,xt+2,…,xt+Hを導出する。J2の重みパラメタwが大きなほど、入力の変更量を抑えて現状の入力を維持した制御となる。
【００６５】
図５にMPCにおける最適化プロセスを図示する。各TSt+1におけるシステム状態zt+1は、1時刻前のTStにおけるシステム状態ztと入力xtから決まる。そしてTSt+1における出力yt+1は外部から与えられ、TSt+1におけるシステム状態zt+1と入力xt+1から決まる。よってt+1≦k≦t+Hの範囲の各TSkにおける入力xkを与えたときの、この範囲の各TSkにおける出力ykをk=t+1から順に再帰的に算出することができ、最適化目的関数J1+wJ2が得られる。そして本目的関数を最小化する非線形最適化問題をt+1≦k≦t+Hの各xtを対象に求め、TSt+1の入力値xt+1をシステムに投入する。
【００６６】
＜配信サーバ選択最適化制御へのMPCの適用＞
キャッシュサーバ選択確率最適設計部２０２における配信サーバ選択最適化のためにMPCを適用するときの具体例について以下に説明する。
【００６７】
MPCのシステム状態ztはコンテンツに対して発生する配信デマンド量du,m,tとなり外部から与えられる。ただしTStの開始時点ではk≧tのdu,m,kは未知であることから、その推定値
【００６８】
【数２０】
0005888687.tif 000021
を代わりに用いる。コンテンツmをユーザuに配信する際に用いる配信キャッシュサーバを確定的に設定すると、MPCの最適化関数を最小化する問題は整数計画問題となり短時間で入力値xtの最適値を導出することが困難となる。そこで配信キャッシュサーバを確定的ではなく確率的に選択することを考える。すなわちTStにおけるユーザuのコンテンツmに対する各要求に対して、
【００６９】
【数２１】
0005888687.tif 000022
のキャッシュサーバの中から確率pu,m,t(s)でキャッシュサーバsを選択する。そのためpu,m,t(s)がMPCの入力xtとなり、各TSの開始時点において
【００７０】
【数２２】
0005888687.tif 000023
となる制約条件を考慮して目的関数を最小化する非線形計画問題として定式化できるため、高速にpu,m,t(s)の解を得ることが可能となる。
【００７１】
コンテンツ配信における配信サーバ選択を最適化する目的としては、キャッシュサーバの負荷の平準化、輻輳によって収容できない超過配信数の抑制、配信フローホップ長の低減、が考えられる。TSt-1におけるサーバsの超過配信回数をζs,t-1とすると、TStにおいてサーバsから配信される配信フローの総数gs,tは、
【００７２】
【数２３】
0005888687.tif 000024
で与えられ、[x]+をx＞0のときにxを、x≦0のとき0を表す演算子とすると、ζs,t-1=[gs,t-1-CC,s]+で得られる。そしてキャッシュサーバの輻輳に関連する目的関数Jsを次式で定義する。
【００７３】
【数２４】
0005888687.tif 000025
そして配信フローの平均ホップ長を同時に抑えることを考え、目的関数Jhを次式で定義する。
【００７４】
【数２５】
0005888687.tif 000026
ただしhs,u,kはTSkにおけるノードsからノードuに至る配信経路のホップ長で、ここでは最短ホップ数を用いる。さらにpu,m,t(s)の変化量を抑えるために目的関数Jv,pを次式で定義する。
【００７５】
【数２６】
0005888687.tif 000027
これら三つの目的関数を同時に考慮するため、JhとJv,pのJsに対する重みを表す実数パラメタwhとwv,pを用いて、Js+whJh+wv,pJv,pを最小化する以下の非線形計画問題によりTStの終了時点において、t+1≦k≦t+Hの範囲の各kに対するpu,m,k(s)を最適化する。
【００７６】
【数２７】
0005888687.tif 000028
＜MPCを用いた配信サーバ選択と経路選択の同時最適化＞
配信ルート選択確率最適設計部３０２における配信サーバ選択と配信経路選択の同時最適化のためにMPCを適用するときの具体例について以下に説明する。
【００７７】
便宜上、配信経路と配信キャッシュサーバの組を配信ルートと呼び、MPCを用いてユーザuからのコンテンツmの配信要求に対して用いる配信ルートを最適設計することを考える。TStにおいて、任意のユーザuとコンテンツmの組に対して存在する配信ルートの集合を
【００７８】
【数２８】
0005888687.tif 000029
とし、当該配信ルートの集合に含まれる配信ルートの中で配信元がs
【００７９】
【数２９】
0005888687.tif 000030
で経路がr
【００８０】
【数３０】
0005888687.tif 000031
のものをφu,m,t(s,r)と表記する。図６にコンテンツmがキャッシュXとキャッシュYに存在する場合の、ユーザAとユーザBに対するコンテンツmの配信ルートを例示する。キャッシュXからユーザAに対しては1本の配信ルートφA,m,t(X,1)が、キャッシュYからユーザAに対しては2本の配信ルートφA,m,t(Y,1)とφA,m,t(Y,2)が各々存在し、同様にキャッシュXとキャッシュYからユーザBに対しては3本と2本の配信ルートが各々存在する場合の例を示している。
【００８１】
やはり短時間で入力値xtの最適値を導出するために、配信ルートを確定的ではなく確率的に選択することを考える。すなわちTStにおけるユーザuのコンテンツmに対する各要求に対して、
【００８２】
【数３１】
0005888687.tif 000032
の配信ルートの中から確率
【００８３】
【数３２】
0005888687.tif 000033
で配信ルートφu,m,t(s,r)を選択する。そのため
【００８４】
【数３３】
0005888687.tif 000034
がMPCの入力xtとなり、各TSの開始時点において
【００８５】
【数３４】
0005888687.tif 000035
となる制約条件を考慮して、目的関数を最小化する非線形計画問題として定式化できるため、高速に
【００８６】
【数３５】
0005888687.tif 000036
の解を得ることが可能となる。
【００８７】
コンテンツ配信における配信キャッシュサーバと配信経路選択を最適化する目的として、NW内に流れるトラヒック量の抑制と、輻輳によって収容できない超過配信数を抑制することが考えられる。トラヒック量抑制のためには配信フローのホップ長の低減が必要であり、超過配信数抑制のためにはリンクや配信サーバの負荷を容量以内に抑える必要がある。配信フローの経路制御はリンク負荷や配信フローホップ長に影響を与える。一方で配信サーバの選択はリンク負荷や配信フローホップ長に加えて、配信サーバ負荷に影響を与える。そのため配信経路と配信キャッシュサーバの組の選択確率を設計する際には、リンク負荷と配信フローホップ長と配信サーバ負荷の三つを予測ホライズン[t+1,t+H]にわたり抑制することを同時に考慮する必要がある。
【００８８】
Is,u,t(r,e)をTStにおいてノードsからノードuへの経路候補rがリンクeを通る場合に1となる二値変数とし、TSt-1におけるリンクeの超過配信回数をηe,t-1とすると、TStにおいてリンクeを通る配信フローの総数fe,tは、
【００８９】
【数３６】
0005888687.tif 000037
で与えられる。ただしηe,t-1はηe,t-1=[fe,t-1-CL,e]+で得られる。そしてリンク輻輳に関する目的関数Jeを次式で定義する。
【００９０】
【数３７】
0005888687.tif 000038
また
【００９１】
【数３８】
0005888687.tif 000039
の変化量を抑えるために、やはり目的関数
【００９２】
【数３９】
0005888687.tif 000040
を次式で定義する。
【００９３】
【数４０】
0005888687.tif 000041
そして二つの目的関数Js、Jhに加えて、
【００９４】
【数４１】
0005888687.tif 000042
とそれらのJsに対する重み
【００９５】
【数４２】
0005888687.tif 000043
を用いて、
【００９６】
【数４３】
0005888687.tif 000044
を最小化する以下の非線形計画問題によりTStの終了時点において、t+1≦k≦t+Hの範囲の各kに対する
【００９７】
【数４４】
0005888687.tif 000045
を最適化する。
【００９８】
【数４５】
0005888687.tif 000046
＜性能評価＞
配信サーバ選択法としては、ユーザuからの配信要求に対して常にキャッシュサーバuのみを使用する場合(L: Local)と、要求されたコンテンツmのコピーを保持する全てのキャッシュサーバの中からユーザuへのホップ長が最短のものを選択する場合(C: Cooperative)と、MPCを用いて配信サーバを最適選択する場合(M: MPC)の三つを考える。一方、経路設定法としては、最短ホップ経路を常に選択する場合(S: Shortest)と、MPCを用いて経路を最適化する場合(M: MPC)の二つを考える。そのためコンテンツ配信NWの実現形態としては、3×2=6の場合について比較し、各々の形態を(配信サーバ選択法)×(経路設定法)という命名規則で表記すると、例えば従来のCDNはL×Sに相当し、M×SとM×Mが本発明の実施形態で説明した形態に相当する。
【００９９】
性能評価の比較のため、経路設定法にのみMPCを用いる形態について簡単に説明する。経路設定法にのみMPCを用いる形態は、CDNを運用していないISPがMPCを用いた制御を行う場合に相当し、サーバsからユーザuへの配信要求に対して
【０１００】
【数４６】
0005888687.tif 000047
の経路rを配信経路として選択する確率
【０１０１】
【数４７】
0005888687.tif 000048
が設計対象となる。ISPにとって各コンテンツがキャッシュされている場所や、CDN事業者の配信サーバ選択ポリシィは未知であるため、各ノードペア間に生じるトラヒック需要量を推定することは困難である。しかし多くの場合、要求ユーザの存在するキャッシュが選択されると考えると、キャッシュヒット時にはNW内にトラヒックが発生しないことから、コンテンツmの配信要求に対してはそのオリジナルサーバomからユーザuにコンテンツが配信されるものと考え、MPCにより
【０１０２】
【数４８】
0005888687.tif 000049
を設計する。
【０１０３】
【数４９】
0005888687.tif 000050
の変化量に対する目的関数
【０１０４】
【数５０】
0005888687.tif 000051
をJv,pや
【０１０５】
【数５１】
0005888687.tif 000052
と同様に定義すると、最適化の目的関数は
【０１０６】
【数５２】
0005888687.tif 000053
となる。
【０１０７】
CAIDAで公開されている米国の二つの商用ISPバックボーンNW、CAISとVerioのNWトポロジを評価に用いた。図７にこれら二つのNWのトポロジを示す。各々のNWのノード数Nは37と35で、リンク数Eは88と152であり、平均ノード次数は2.38と4.11である。VerioはCAISと比較してノード次数が高く、次数が大きなハブノードが存在するのに対してCAISはノード次数が低くハブノードが存在しない。Verioにおいてはハブノードを経由することで各ノードペア間のホップ距離を短縮することができるため、平均ノード間距離が2.51であるのに対して、CAISの平均ノード間距離は5.05と大きい。
【０１０８】
そしてChina Telecomが提供する商用VoDサービスPowerInfo VoDシステムにおいて収集されたアクセスログデータに従いコンテンツ配信要求を発生させた。本ログデータには2004年6月から12月の7ヶ月間に発生した20,921,657の全配信要求が含まれているが、第162日目から171日目の10日間のログデータを評価に用い、各配信要求に対して各ノードの人口比に比例する確率でランダムに選択したノードから要求を発生させた。ただしキャッシュサーバに全くコンテンツがキャッシュされていない状態からシミュレーションを開始し、最初の3日間はワームアップ期間として評価対象外として、残りの7日間で得られたデータを評価に用いた。
【０１０９】
全てのノードにキャッシュサーバが配置されているものとする。評価ログデータに含まれるコンテンツ数が7,500であったが、各キャッシュサーバのストレージ容量をBs=7,500/Nに設定した。ログデータの評価に用いた7日間における一日あたりの最大視聴回数は5,700であったが、各配信サーバの配信容量をCC,s=5,700×2/Nに、各リンクの伝送容量をCL,e=5,700×4/Nに設定した。また各コンテンツのオリジナルサーバomを、シミュレーション開始時に各ノードの人口比に比例する確率でランダムに設定し、シミュレーション期間中は不変とした。
【０１１０】
TSの期間長をT=30分とし、経路設定法と配信サーバ選択法のどちらか一方、もしくは経路設定法と配信サーバ選択法の両方にMPCを用いる場合、予測ホライズンをH=2に、各目的関数の重みを
【０１１１】
【数５３】
0005888687.tif 000054
に設定した。また需要予測が正確に行われていることを想定し、配信需要の予測値
【０１１２】
【数５４】
0005888687.tif 000055
に実際の値du,m,tを用いた。そしてアクセスログに従い発生させたノードu(ユーザu)からのコンテンツmの各配信要求に対して、pu,m,t(s)や
【０１１３】
【数５５】
0005888687.tif 000056
や
【０１１４】
【数５６】
0005888687.tif 000057
に従い、各々、キャッシュサーバ、配信ルート、経路をランダムに選択した。ただし経路候補
【０１１５】
【数５７】
0005888687.tif 000058
をノードペアi,j間の3本のk-shortest path(ホップ長が最小となる3本の経路)とした。
【０１１６】
＜評価結果＞
各TSにおいて発生した配信要求の中で、受付けられなかった超過配信要求数の平均値と、配信フローの平均ホップ長に関して6つの形態を比較する。表１と表２に、CAISとVerioの各NWに対して6つの各形態を用いた場合の平均超過配信要求数を各々まとめる。
【０１１７】
【表１】
0005888687.tif 000059
【０１１８】
【表２】
0005888687.tif 000060
同一の経路設定法を用いて配信サーバ選択法のみを変えた場合の結果の差異は、同一の配信サーバ選択法を用いて経路設定法のみを変えた場合の結果の差異と比較して遥かに大きく、配信サーバ選択法が平均超過配信要求数を決める主要因であることが確認できる。
【０１１９】
配信サーバ選択法がLocalの場合、各配信要求に対して選択候補となるキャッシュサーバが要求発生ノードに限定されるため、複数のノードのキャッシュサーバが選択候補となるCooperateやMPCの場合と比較して、超過配信要求数が1桁〜2桁大きくなる。一方、配信サーバ選択法がCooperateとMPCの場合を比較すると、Cooperateは各配信要求発生時点のキャッシュ状態を考慮して、常に、該当コンテンツが存在するキャッシュサーバの中で要求ユーザへのホップ長が最小となるものが選択されるのに対して、MPCはTSの開始時点におけるコンテンツの配置状態のみに基づきキャッシュサーバの選択確率を設計するため、要求発生時点のコンテンツ配置状態を必ずしも反映したサーバ選択とはなっていない。そのためMPCはCooperateと比較して、NW全体のコンテンツの配置状態を把握することが必要な周期が遥かに長く、制御負荷が低い反面、超過配信要求数は増加することが予想される。
【０１２０】
しかしCAISにおけるCooperateの結果はMPCより僅かに良好な程度に留まっている。さらにVerioにおいては逆に、MPCがCooperateより一桁程度も小さく、遥かに良好な結果を示している。これはVerioには高次数のハブノードが存在するがハブノードは他ノードからのホップ距離が短く、Cooperateにおいてはハブノードに存在するキャッシュサーバが配信サーバとして選択される機会が多く、これらキャッシュサーバに負荷が集中するためである。そのためハブノードが存在するハブ&スポーク型のNWの場合には、多数のキャッシュサーバが確率的に選択され、選択サーバの多様性が高いMPCを用いた配信サーバ選択法の効果が高くなる。
【０１２１】
また表３と表４に、CAISとVerioの各NWに対して6つの各形態を用いた場合の平均配信フローホップ長を各々まとめる。
【０１２２】
【表３】
0005888687.tif 000061
【０１２３】
【表４】
0005888687.tif 000062
やはり経路設定法の違いが結果に与える影響は僅かであり、配信サーバ選択法が平均配信フローホップ長を決める支配要因であることが確認できる。いずれのNWにおいても該当コンテンツを保有する最近接キャッシュサーバからコンテンツを取得するCooperateを配信サーバ選択法に用いた場合に平均ホップ長が最小となっているが、MPCを配信サーバ選択法に用いた場合もほぼ同等の効果が得られる。
【０１２４】
＜本発明の実施形態の効果＞
以上説明したように、本発明の実施形態によれば、NWの複数のノードに分散配置されたキャッシュサーバを用いてコンテンツを配信するCDNにおいて、各配信要求に対して配信に用いるキャッシュサーバを選択する確率や、キャッシュサーバと経路の組である配信ルートを選択する確率を、MPCを用いて最適設計することで、キャッシュサーバの容量超過により配信要求が棄却される超過配信要求の頻度を最小化できる効果がある。
【０１２５】
説明の便宜上、本発明の実施形態に係る配信サーバ又は配信ルート設計装置（配信サーバ選択確率最適設計装置、配信ルート選択確率最適設計装置）は機能的なブロック図を用いて説明しているが、本発明の実施形態に係る配信サーバ又は配信ルート設計装置は、ハードウェア、ソフトウェアまたはそれらの組み合わせで実現されてもよい。例えば、本発明の実施形態は、コンピュータに対して本発明の実施形態に係る配信サーバ又は配信ルート設計装置の各機能を実現させるプログラム、コンピュータに対して本発明の実施形態に係る方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。
【０１２６】
以上、CDNにおいて、ユーザからの配信要求が変化するときにユーザからの配信要求が棄却される頻度を抑制し、CDNサービスの向上を図るための手法について説明したが、本発明は、上記の実施形態に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【０１２７】
１００  配信サーバ又は配信ルート設計装置
１０１  パラメタ入力部
１０２  選択確率設計部
１０３  選択確率出力部
２００  配信サーバ選択確率最適設計装置
２０１  パラメタ入力部
２０２  キャッシュサーバ選択確率最適設計部
２０３  キャッシュサーバ選択確率出力部
３００  配信ルート選択確率最適設計装置
３０１  パラメタ入力部
３０２  配信ルート選択確率最適設計部
３０３  配信ルート選択確率出力部
【要約】
【課題】CDNにおいて、ユーザからの配信要求が棄却される頻度を抑制し、CDNサービスの向上を図る。
【解決手段】CDNにおいて、ユーザからの配信要求に対してコンテンツの配信に用いられる配信サーバ又は配信ルートを選択する確率を設計する配信サーバ又は配信ルート設計装置は、ネットワークに関するパラメタと、配信要求の需要推定量とを入力パラメタ値として受け取るパラメタ入力部と、前記受け取った入力パラメタ値に基づき、ユーザからの配信要求が棄却される超過配信要求を抑制するよう、キャッシュサーバが配信サーバとして選択される選択確率、又は、配信サーバがコンテンツを配信する配信経路と配信サーバの組である配信ルートの選択確率をモデル予測制御を用いて設計する選択確率設計部と、前記設計されたキャッシュサーバの選択確率又は配信ルートの選択確率を出力する選択確率出力部とを有する。
【選択図】図１【図１】
0005888687.tif 000086
【図２】
0005888687.tif 000087
【図３】
0005888687.tif 000088
【図４】
0005888687.tif 000089
【図５】
0005888687.tif 000090
【図６】
0005888687.tif 000091
【図７】
0005888687.tif 000092