(57)【要約】【課題】  通信のボトルネックとなるリンクを回避し、配信サーバやリンクの負荷をできる限り分散させる。【解決手段】  本発明は、配信サーバの情報、該配信サーバを含むリンクの負荷情報、隣接するＡＳ間のネットワークリソース情報、該配信サーバを含む経路情報を、自ＡＳ内及び他のＡＳとの間で情報交換することにより収集して記憶手段に格納し、リクエストを受け付けると、該リクエストに基づいて、記憶手段に格納されている情報を取得し、配信サーバ及び該配信サーバを含むリンクの負荷情報、経路情報、該配信サーバから当該負荷分散サーバまでの経路のホップ数、ボトルネック数を用いてサーバ選択コストを算出し、リクエストの条件及び前記サーバ選択コストに基づいて配信サーバを選択する。【選択図】  図１
2012169789.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツ配信サーバを有する複数の自律システム（ＡＳ：Autonomous System）から構成されるコンテンツ配信ネットワークにおいて、ユーザからのリクエストに対して配信サーバを割り当てる負荷分散サーバであって、
配信サーバの情報、該配信サーバを含むリンクの負荷情報、隣接するＡＳ間のネットワークリソース情報、該配信サーバを含む経路情報を、自ＡＳ内及び他のＡＳとの間で情報交換することにより、定期的に収集して記憶手段に格納する経路情報収集手段と、
前記ユーザから前記リクエストを受け付けると、該リクエストに基づいて、前記記憶手段に格納されている情報を取得し、前記配信サーバ及び該配信サーバを含むリンクの負荷情報、前記経路情報、該配信サーバから当該負荷分散サーバまでの経路のホップ数、該経路のリンクのボトルネックになりやすさを示す値を用いてサーバ選択コストを算出するサーバ選択コスト算出手段と、
前記記憶手段を参照し、前記リクエストの条件及び前記サーバ選択コストに基づいて配信サーバを選択するサーバ割り当て手段と、
を有することを特徴とする負荷分散サーバ。
【請求項２】
前記サーバ選択コスト算出手段は、
前記記憶手段から取得した、ある配信サーバの負荷、該配信サーバと自ＡＳ内の負荷分散サーバ間の経路上のリンクの最大負荷を用いて動的コストを求め、該配信サーバと該自ＡＳ内の負荷分散サーバ間の経路のホップ数及び該経路上のボトルネックリンク数によって静的コストを求め、該動的コスト及び該静的コスト及び該動的コストに対する所定の閾値から前記選択コストを求めるコスト算出手段を含む
請求項１記載の負荷分散サーバ。
【請求項３】
前記ボトルネックリンク数を、
自ＡＳ内の負荷分散サーバから前記配信サーバが属するＡＳまでの経路の経路に含まれるリンクの中で最も残余帯域が低いものをボトルネックとしてカウントした値とする
請求項２記載の負荷分散サーバ。
【請求項４】
コンテンツ配信サーバを有する複数の自律システム（ＡＳ：Autonomous System）から構成されるコンテンツ配信ネットワークにおいて、ユーザからのリクエストに対して配信サーバを割り当てるサーバ選択方法であって、
情報収集手段が、配信サーバの情報、該配信サーバを含むリンクの負荷情報、隣接するＡＳ間のネットワークリソース情報、該配信サーバを含む経路情報を、自ＡＳ内及び他のＡＳとの間で情報交換することにより、定期的に収集して記憶手段に格納する情報収集ステップと、
サーバ選択コスト算出手段が、前記ユーザから前記リクエストを受け付けると、該リクエストに基づいて、前記記憶手段に格納されている情報を取得し、前記配信サーバ及び該配信サーバを含むリンクの負荷情報、前記経路情報、該配信サーバから当該負荷分散サーバまでの経路のホップ数、該経路のリンクのボトルネックになりやすさを示す値を用いてサーバ選択コストを算出するサーバ選択コスト算出ステップと、
サーバ割り当て手段が、前記記憶手段を参照し、前記リクエストの条件及び前記サーバ選択コストに基づいて配信サーバを選択するサーバ割り当てステップと、
を行うことを特徴とするサーバ選択方法。
【請求項５】
前記サーバ選択コスト算出ステップにおいて、
前記記憶手段から取得した、ある配信サーバの負荷、該配信サーバと自ＡＳ内の負荷分散サーバ間の経路上のリンクの最大負荷を用いて動的コストを求め、該配信サーバと該自ＡＳ内の負荷分散サーバ間の経路のホップ数及び該経路上のボトルネックリンク数によって静的コストを求め、該動的コスト及び該静的コスト及び該動的コストに対する所定の閾値から前記選択コストを求める
請求項４記載のサーバ選択方法。
【請求項６】
前記ボトルネックリンク数を、
自ＡＳ内の負荷分散サーバから前記配信サーバが属するＡＳまでの経路の経路に含まれるリンクの中で最も残余帯域が低いものをボトルネックとしてカウントした値とする
請求項５記載のサーバ選択方法。
【請求項７】
請求項１乃至３のいずれか１項に記載の負荷分散サーバを構成する各手段としてコンピュータを機能させるためのサーバ選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、負荷分散サーバ及びサーバ選択方法及びサーバ選択プログラムに係り、特に、複数キャリアで構成されるＩＰ(Internet Protocol)網上のコンテンツ配信ネットワーク（CDN）サービスにおいて、ネットワーク上に複数存在するコンテンツの中から、コンテンツ配信サーバ（以下、単に「配信サーバ」と記す）の負荷の軽減、ネットワークにおけるボトルネックとなるネットワークリンク（以下、単に「リンク」と記す）の発生の回避を行うように、ユーザに配信サーバを割り当てるための負荷分散サーバ及びサーバ選択方法及びサーバ選択プログラムに関する。
【背景技術】
【０００２】
配信サーバの負荷軽減のためには、配信サーバサイトにおいて、複数の複製を用意し、負荷分散をとる局所的な解決方法とプロキシサーバと呼ばれる代理サーバを用意し、そこにアクセス頻度の高いコンテンツを複製し、当該プロキシサーバにアクセスする方式が採られている（例えば、非特許文献１参照）。
【０００３】
また、同じリンク帯域、同じ性能の配信サーバが存在する状況では、各リンク、配信サーバの負荷を動的に平準化するための誘導技術も提案されている（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】安井真伸、横川和哉ら、"サーバ／インフラを支える技術"技術評論社、2008.
【非特許文献２】古谷快，西山大樹，加藤寧，山田博司，矢田健，野村啓仁，"コンテンツ配信ネットワークにおける負荷分散を考慮したサーバ選択法に関する一考察"，電子情報通信学会ソサイエティ大会，2010．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記従来の非特許文献1の技術は、静的な負荷軽減手法であるため、ネットワークやサーバの状態に適応して、トラヒックフローを動的に適応させることができない。
【０００６】
また、コンテンツ提供者側から、ユーザアクセスに関する動的な制御を行うこと（網側でユーザからのアクセスを契約やサーバ、ネットワーク状況に応じて変更させること）が難しく、サーバサイト側における局所最適な方法であった。
【０００７】
その他に、ユーザの近隣の配信サーバにコンテンツが存在するにも関わらず、遠方のコンテンツサイトへのアクセスを行うことにより、キャリアネットワークの通過や余分なリソースの用意が必要になる状況も生じている。なお、ここで「近隣」とは、同一のAS（Autonomous System:自律システム）内、よりホップ数の少ないネットワークに存在している状態をいう。
【０００８】
さらに、このようなキャリアネットワークに対しては、コンテンツ配信にとっての最適経路がネットワークの特定リンクの負荷を増大することによって、ネットワーク全体のリソースの有効利用を阻害している状況も生じ得る。
【０００９】
上記従来の非特許文献２の技術では、各サーバやリンクの性能が異なる不均一な環境では負荷の分散が十分に行えなかったり、学習に時間がかかるため環境変化に動的に対応しきれないなどの問題がある。
【００１０】
本発明は、上記の点に鑑みなされたもので、配信サーバを有する複数のASから構成されるコンテンツ配信ネットワークにおいて、通信のボトルネックとなるリンクを回避し、配信サーバやリンクの負荷をできる限り分散させるためのネットワーク装置及び配信サーバ選択方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、本発明は、コンテンツ配信サーバを有する複数の自律システム（ＡＳ：Autonomous System）から構成されるコンテンツ配信ネットワークにおいて、ユーザからのリクエストに対して配信サーバを割り当てる負荷分散サーバであって、
配信サーバの情報、該配信サーバを含むリンクの負荷情報、隣接するＡＳ間のネットワークリソース情報、該配信サーバを含む経路情報を、自ＡＳ内及び他のＡＳとの間で情報交換することにより収集して記憶手段に格納する経路情報収集手段と、
前記ユーザから前記リクエストを受け付けると、該リクエストに基づいて、前記記憶手段に格納されている情報を取得し、前記配信サーバ及び該配信サーバを含むリンクの負荷情報、前記経路情報、該配信サーバから当該負荷分散サーバまでの経路のホップ数、該経路のリンクのボトルネックになりやすさを示す値を用いてサーバ選択コストを算出するサーバ選択コスト算出手段と、
前記記憶手段を参照し、前記リクエストの条件及び前記サーバ選択コストに基づいて配信サーバを選択するサーバ割り当て手段と、を有する。
【発明の効果】
【００１２】
上記のように本発明によれば、コンテンツ配信ネットワークでのコンテンツの配信において、変化するネットワークや配信サーバの状況に応じて、ユーザからのアクセスをコンテンツ提供者が予め設定した方策に基づいて効果的に配信サーバを割り当てることが可能となる。具体的には、ネットワークで動的に変化するリンクや配信サーバの負荷状況と、配信サーバまでのホップ数や配信サーバまでの経路のボトルネックになりやすさを考慮して方策に従ってより条件のよい配信サーバを選択することが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施の形態におけるネットワーク構成図である。
【図２】本発明の一実施の形態における負荷分散サーバの構成図である。
【図３】本発明の一実施の形態における負荷分散サーバの機能を示す図である。
【図４】本発明の一実施の形態におけるユーザのコンテンツ配信要求に対する動作シーケンスである。
【図５】本発明の一実施の形態における負荷分散サーバの動作のシーケンスチャートである。
【図６】本発明の一実施の形態における負荷分散サーバ間の情報交換シーケンスである。
【図７】本発明の一実施の形態におけるネットワーク装置間の情報交換の例（その１）である。
【図８】本発明の一実施の形態におけるネットワーク装置間の情報交換の例（その２）である。
【図９】本発明の一実施の形態におけるネットワーク装置間の情報交換の例（その３）である。
【図１０】本発明の一実施の形態における複数のリンク情報がある場合の例である。
【図１１】本発明の一実施の形態におけるユーザ品質条件の例である。
【図１２】本発明の一実施の形態における品質（例：処理待ち時間）と負荷量の関係図である。
【図１３】本発明の一実施の形態におけるボトルネックカウントを説明するための図である。
【発明を実施するための形態】
【００１４】
以下図面と共に、本発明の実施の形態を説明する。
【００１５】
［第1の実施の形態］
図１は、本発明の一実施の形態におけるネットワーク構成図である。
【００１６】
同図に示すネットワークは、一例として、5つのＡＳ１ａ，１ｂ，１ｃ，１ｄ，１ｅで接続構成されたＩＰネットワーク（以下、『ＡＳネットワーク』と記す）上に、コンテンツを提供する配信サーバ３０，４０及びユーザからのリクエストを各配信サーバに割り当てる負荷分散サーバ２０が存在するものとする。このうち、配信サーバ３０は、コンテンツＡを、配信サーバ４０はコンテンツＢを配信するものとし、例えば、ＡＳ１ｄには、コンテンツＡを配信する配信サーバ３０ｄ、コンテンツＢを配信する配信サーバ４０ｄの両方が存在する。
【００１７】
各ＡＳ１は、負荷分散サーバ２０、配信サーバ３０，４０を有し、ASBR(AS Border Router:AS境界ルータ)５０1〜５０6により他のＡＳと接続されている。
【００１８】
また、それぞれのASにはユーザが存在し、それぞれコンテンツＡ，Ｂの獲得を考えているものとする。
【００１９】
同じコンテンツを提供する配信サーバ（プロキシサーバのような代理サーバもコンテンツを提供する場合も含む）は、複数ASネットワーク上に存在することが想定され、また、コンテンツの複製を所有する代理サーバも同様に複数ＡＳネットワーク上に存在することが想定される。
【００２０】
負荷分散サーバ２０は、自ＡＳ内のユーザからのリクエストに対して適当な配信サーバを割り当てるサーバであり、自ＡＳが配信サーバ３０，４０の割り当て動作に供する情報を保持する。当該配信サーバの割り当て動作に供する情報には、自ＡＳに存在するコンテンツ名、配信サーバのPrefix(IP address, Subnet mask)情報、配信サーバの負荷状況、隣接するＡＳ間のネットワークリソース状況、配信サーバのスペック情報（メモリ、ＣＰＵ等）、さらには、現在配信サーバがどのＡＳとどのような経路で通信を行っているかという情報が該当する。
【００２１】
また、負荷分散サーバ２０に保持される情報は、予めコンフィグレーションによる設定、及び、情報収集部２７による配信サーバと負荷分散サーバ間のサービス登録・維持管理プロトコルによって自動収集された情報を保持する。
【００２２】
図２は、本発明の一実施の形態における負荷分散サーバの構成を示す。
【００２３】
各ＡＳ１内の負荷分散サーバ２０は、割り当て部２１、記憶部２２、情報収集部２７を有する。
【００２４】
情報収集部２７は、図３に示すように、ルーティングプロトコル機能を有し、当該ルーティングプロトコルの一つであるBGP(Border Gateway Protocol)により、ＡＳの境界ルータであるＡＳＢＲとＢＧＰ接続することで、自ＡＳから他のＡＳに至るＡＳ経路情報を有する。
【００２５】
IPプロトコルレイヤ及びインタフェースでは、負荷分散サーバ２０のIP Address, Subnet mask、default route, DNSなどを設定する。
【００２６】
記憶部２２は、設定情報記憶部２２１、コンテンツ別サーバ情報テーブル２２２、ルーティングテーブル情報記憶部２２３、コスト情報記憶部２２４、リンク使用率情報記憶部２２５、サーバ使用率情報記憶部２２６を有する。
【００２７】
設定情報記憶部２２１は、自ＡＳの配信サーバ情報（コンテンツ名、配信サーバのPrefix情報、配信サーバのスペック情報（メモリ、ＣＰＵ等）やNeighbor情報等を格納する。
【００２８】
コンテンツ別サーバ情報テーブル２２２は、負荷分散サーバ間の情報交換で得られたコンテンツ別のサーバ情報を格納する。
【００２９】
ルーティングテーブル情報記憶部２２３は、設定したルーティング機能により得られるルーティングテーブル情報（算出したコスト、コストに基づく割り当てルール）を格納する。
【００３０】
コスト情報記憶部２２４は、選択コスト算出部２１２によって算出されたコスト情報を格納する。
【００３１】
リンク使用率情報記憶部２２５は、リンクの負荷情報を格納する。
【００３２】
サーバ使用率情報記憶部２２６は、配信サーバの使用率情報を格納する。
【００３３】
割り当て部２１は、配信サーバ選択コストの閾値を決定する閾値決定部２１１、自ＡＳで管理しているコンテンツサーバリスト（IP address, Subnet mask,提供コンテンツ）、リソース情報を取得して、候補配信サーバの選択コストを算出する選択コスト算出部２１２、選択コストに基づいてリクエストに対して割り当てるサーバを決定する配信サーバ割当部２１３、メモリ２１４を有する。詳細については後述する。
【００３４】
以下に、負荷分散サーバ２０の動作を説明する。
【００３５】
図４は、本発明の一実施の形態におけるユーザのコンテンツ配信要求に対する動作シーケンスを示す。
【００３６】
ステップ１０１）  ユーザ端末１０は、負荷分散サーバ２０に対して、自身の認証情報（利用者情報など、コンテンツ提供者等により個別の設定を想定）、要求コンテンツ情報を送信し、配信サーバの案内を依頼する。
【００３７】
ステップ１０２）  負荷分散サーバ２０は、ユーザの認証を行い、要求コンテンツを所持する配信サーバの中で最小のコストを持つ配信サーバを選出する。このとき、負荷分散サーバ２０が備えるフィルタリング機能により、予め管理者による政策を設定することができる。管理者による政策を設定することで、情報交換の相手先によって交換するコンテンツ内容を変化させる。つまり、このコンテンツは、あるプロバイダにはアクセス可能とするが、そうでない場合はアクセスできないよう、アドレス情報を隠蔽するというような処理を可能とする。
【００３８】
ステップ１０３）  負荷分散サーバ２０は、ユーザ端末１０へ選出したサーバの情報を返信する。
【００３９】
ステップ１０４）  ユーザは案内された配信サーバへコンテンツリクエストを送信する。
【００４０】
ステップ１０５）  配信サーバは要求されたコンテンツをユーザ端末１０に送信する。
【００４１】
なお、ステップ１０１において、ユーザｃが負荷分散サーバ２０ｃに、要求コンテンツ情報として「コンテンツＡ」を要求した場合には、配信サーバ３０ｃの情報が返却される。
【００４２】
次に、負荷分散サーバ間の情報維持のための情報交換処理について説明する。
【００４３】
各ＡＳに存在する負荷分散サーバ２０間では、情報収集部２７において、定期的に通信を行い、自ＡＳに存在する配信サーバの割り当て動作に供する情報（コンテンツ名、Prefix、配信サーバの負荷状況、現在配信サーバがどのＡＳとどのような経路で通信を行っているか等）の交換を行う。情報交換相手となる負荷分散サーバは、負荷分散サーバの設定項目に、BGP Neighborとして予め設定する。
【００４４】
図５は、本発明の一実施の形態における負荷分散サーバの動作のフローチャートである。
【００４５】
ステップ２００）  情報収集部２７は、自ＡＳの配信サーバ及びＡＳＢＲ５０を介して他のＡＳの負荷分散サーバとの間で情報交換を行い、収集した情報を記憶部２２に格納する。なお、当該処理は、定期的に実行されているものとする。
【００４６】
ステップ２１０）  選択コスト算出部２１２において、記憶部２２に格納された情報を用いて選択コストを算出し、算出結果をコスト情報記憶部２２４に格納する。なお、当該処理は、ステップ２００に合わせて、定期的に実行されているものとする。
【００４７】
ステップ２２０）  ユーザからユーザＩＤ等の利用者情報及び要求コンテンツ情報を取得する。
【００４８】
ステップ２３０）  負荷分散サーバ２０は、利用者情報に基づいてユーザの認証を行う。
【００４９】
ステップ２４０）  配信サーバ割当部２１３は、設定情報記憶部２２１、コンテンツ別サーバ情報テーブル２２２を参照して、ユーザからのリクエストに合致する配信サーバのうち、選択コストの最も小さい値の配信サーバを選択する。
【００５０】
ステップ２５０）  選択した配信サーバの情報を要求元のユーザに送信する。
【００５１】
次に、図５のステップ２００の情報収集部２７における情報交換の動作について説明する。
【００５２】
図６は、本発明の第１の実施の形態における負荷分散サーバ間の情報交換シーケンスである。同図に示すシーケンスは、負荷分散サーバ２０での配信サーバ選択コストの算出に必要な情報を得るための情報収集動作を示す。
【００５３】
ステップ２０１）  負荷分散サーバ２０の情報収集部２７は、自ＡＳ内に存在する配信サーバ３０または４０から、配信サーバの負荷状況、所持コンテンツ等の情報を定期的に取得し、コンテンツ別サーバ情報テーブル２２２およびサーバ使用率情報記憶部２２６に格納する。
【００５４】
ステップ２０２）  負荷分散サーバ２０は、自ＡＳのＡＳ境界ルータ５０に隣接ＡＳのリンク負荷情報のリクエストを送信する。
【００５５】
ステップ２０３）  ＡＳ境界ルータ５０は、自ＡＳと隣接関係にあるＡＳとの間のリンク負荷情報を負荷分散サーバ２０へ出力する。これにより、情報収集部２７は、取得したリンク間負荷情報をコンテンツ別サーバ情報テーブル２２２に格納する。
【００５６】
上記のステップ２０１〜２０３によって、サーバ選択コストの算出に必要な情報のうち、自ＡＳに関するものを各負荷分散サーバで取得する。
【００５７】
ステップ２０４）  負荷分散サーバ２０は、自身が取得した情報と前回までにコンテンツ別サーバ情報テーブル２２２に格納されていた情報とを比較して更新があった場合は、他ＡＳの負荷分散サーバそれぞれに対して、取得した情報を送信する。
【００５８】
ステップ２０５）  他ＡＳの負荷分散サーバも同様に、自ＡＳの情報取得において、コンテンツ別サーバ情報テーブル２２２に更新があった場合は、これを他ＡＳの負荷分散サーバに送信する。他のＡＳの負荷分散サーバから更新情報を取得すると、コンテンツ別サーバ情報テーブル２２２に格納する。
【００５９】
以下にネットワーク装置間の情報交換について説明する。
【００６０】
図７は、本発明の一実施の形態におけるネットワーク装置間の情報交換の例（その１）を示す。
【００６１】
同図において、「コンテンツＡ」を提供するコンテンツサーバのPrefix情報に対して、ＡＳ経路情報をＢＧＰ情報から得ることができる。同図において、点線は同一ＡＳ内でのＢＧＰを示し、実線は異なるＡＳのＡＳＢＲからＡＳ経路情報を得ることを示している。同図左上に、負荷分散サーバ２０のルーティングプロトコル機能により取得し、ルーティングテーブル情報記憶部２２３に格納された例を示す。
【００６２】
図８は、本発明の一実施の形態におけるネットワーク装置間の情報交換の例（その２）を示す。
【００６３】
同図において、点線は負荷分散サーバ２０間の情報交換を示しており、基本的にはフルメッシュになるが、iBGPのルートリフレクタ技術と同様、階層化を持たせることでスケーラブルとなる。また、実線は、配信サーバから負荷分散サーバ２０へのサーバ負荷情報の報告を示している。
【００６４】
負荷分散サーバ２０は、同一のＡＳ内の配信サーバ３０，４０からサーバ負荷情報を取得して、異なるＡＳの負荷分散サーバ間の通信により配信サーバの負荷状況をルーティングテーブル情報記憶部２３３で管理する。同図左上の表は、ルーティングテーブル情報記憶部２２３の例である。
【００６５】
図９は、本発明の一実施の形態におけるネットワーク装置間の情報交換の例（その３）を示す。実線はＡＳＢＲから隣接ＡＳ間インタフェースのリンク使用率情報の報告を示しており、点線は、ＡＳＢＲから取得したリンク使用率情報を負荷分散サーバ間での交換を示している。
【００６６】
情報収集部２７は、自ＡＳのＡＳＢＲが隣接しているＡＳへのインタフェースのリンク使用率を負荷分散サーバ間で交換し、各負荷分散サーバ２０のリンク使用率情報記憶部２２５に格納する。
【００６７】
負荷分散サーバ２０は、情報収集部２７においてＡＳ間のリンク使用率情報を取得した際に、各ＡＳＢＲにおける測定のタイミングのズレがあり、図１０に示すように、同じリンクについて複数の情報が得られる場合には、最大値を採用するものとする。
【００６８】
次に、図５のステップ２３０の選択コスト算出処理について説明する。
【００６９】
負荷分散サーバ２０は、情報収集部２７によって上記のようにして収集され、記憶部２２に格納されている、各配信サーバやリンクの負荷状況、配信サーバの通信状況（どのＡＳとどの経路で通信を行っているか）の情報に基づいて、サーバの選択コストを算出する。
【００７０】
まず、閾値算出部２１１が、動的コストに対する閾値θ１、θ２を決定し、メモリ２４１に格納する。
【００７１】
以下に閾値の決定方法について説明する。
【００７２】
配信サーバｊ及び経路ｐ（ｊ，ｉ）をひとつの待ち行列として定義し、ユーザ要求品質条件の上限に相当する負荷量を閾値として選出する。
【００７３】
θ２は、コンテンツ提供者の提供ポリシと図１１に示すようなユーザ品質条件（文献１：ITU Y. 1541 http://www.itu.int/ITU-T/worksem/qos/presentations/qos_1003_s5P1_pres.ppt#299,6,Table2/Y.1541 Guidance for IP Qos Classes）から、遅延の許容限界値としてｔ２を設定し、図１２のようにｔ２に相当する負荷量をθ２として設定する。
【００７４】
θ１は、θ２と図１２のような負荷と処理待ち時間の関係式を考慮し、負荷の変動によって急速に処理待ち時間が増大し始める境目をθ１として設定する。
【００７５】
平均処理待ち時間Ｗの算出式は以下の通りである。
【００７６】
【数１】
2012169789.tif 000003
但し、λはパケット平均到着率、μはサーバ処理性能、ρはサーバ稼働率（負荷率）である。
【００７７】
なお、これらの閾値は予めマニュアル（手動）で各負荷分散サーバ２０のメモリ２１４に設定しておくものとする。
【００７８】
選択コスト算出部２１２は、記憶部２２のコンテンツ別サーバ情報テーブル２２２とリンク使用率情報記憶部２２５の情報を読み込み、動的コスト、静的コストを求め、更に、閾値を用いて選択コストを算出する。ある分散サーバｉが配信サーバｊを選択する際のコストｃ（ｉ，ｊ）は動的コストと静的コストの２つの要素から算出される。以下で用いるパラメータを、
・p(i，j)：ｉ−ｊ間の経路
・ｆS_load(j)：配信サーバｊの負荷
・ｆL_load(p(i，j))：経路ｐ（ｉ，ｊ)上のリンクの最大負荷
・ｆHop(p(i，j))：経路ｐ（ｉ，ｊ)のホップ数
・ｆCritical(p(i，j))：経路ｐ（ｉ，ｊ）上のボトルネックリンク数
とすると、動的コスト、静的コストは以下のように求められる。
【００７９】
・動的コスト：ｆdyn(i，j)：配信サーバｊ及びｉ−ｊ間の経路ｐ（i，j）上のリンクの負荷のうち、より大きいもの
【００８０】
【数２】
2012169789.tif 000004
・静的コストｆstat(i，j)：配信サーバｉ−ｊ間の経路のホップ数及び経路上のボトルネックリンク数によって算出される。
【００８１】
【数３】
2012169789.tif 000005
上記から選択コストｃ（i,j）は動的コストに対する閾値θ１、θ２に対して以下のように求められる。
【００８２】
【数４】
2012169789.tif 000006
求められた選択コストｃ（i,j）はコスト情報記憶部２２４に格納される。
【００８３】
次に、上記のｆCritical(p(i，j))で表されるボトルネックについて説明する。
【００８４】
サーバ選択コストの計算では、文献２「K. Kar. et al., "MinimumInterference Routing of Bandwidth Guaranteed Tunnels with MPLS Traffic Engineering," IEEE J. on Selected Areas commun., 2000. http://ieeexplore. Ieee.org/xpls/abs_all.jsp?arnumber=898737&tag=1」で用いられている手法を利用し、配信サーバの属するＡＳまでのパスのボトルネックとなる危険性を考慮している。
【００８５】
あるＡＳｉ−ｊ間のパスｐ（ｉ，ｊ）のボトルネック危険性ｆCritical(p(i，j))は、
【００８６】
【数５】
2012169789.tif 000007
となる。但し、AはＡＳ間の契約などによって決められるリンクの重要度に関する重みである（ここにＡＳ間の方策を反映することができる）。また、ｆbc(ａk)はリンクａkが各ＡＳ間パスの評価において、図１３に示すように、ボトルネックリンクとしてカウントされた回数を意味する。ボトルネックリンクとは、あるＡＳ間のパスに含まれるリンクの中で残余帯域が最も低いものを指す。
【００８７】
最後に、配信サーバ割り当て部２１３は、コスト情報記憶部２２４から選択コストｃ（i,j）を読み出し、コスト値が最も小さい配信サーバを選択し、対応するサーバの情報をコンテンツ別サーバ情報テーブル２３から取得して、サーバ情報をユーザからのリクエストに対する応答としてユーザ端末１０に返却する。
【００８８】
上記のように、負荷分散サーバ２０において、複数のＡＳから構成されるコンテンツ配信ネットワークにおいて、通信のボトルネックとなるリンクを回避し、配信サーバやリンクの負荷をできる限り分散させて配信サーバを決定することが可能となる。
【００８９】
なお、上記の負荷分散サーバの各構成要素の動作をプログラムとして構築し、負荷分散サーバとして利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００９０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００９１】
１０ａ，１０ｂ，１０ｃ，１０ｄ，１０ｅ  ユーザ端末
２０ａ，２０ｂ，２０ｃ，２０ｄ，２０ｅ  負荷分散サーバ
２１  割り当て部
２２  記憶部
２７  情報収集部
３０ｂ，３０ｃ，３０ｄ，３０ｅ  配信サーバ（コンテンツＡ）
４０ａ，４０ｄ，４０ｅ  配信サーバ（コンテンツＢ）
５０１，５０２，５０３，５０４，５０５，５０６  ＡＳＢＲ（ＡＳ境界ルータ）
２１１  閾値決定部
２１２  選択コスト算出部
２１３  配信サーバ割当部
２１４  メモリ
２２１  設定情報記憶部
２２２  コンテンツ別サーバ情報テーブル
２２３  ルーティングテーブル情報記憶部
２２４  コスト情報記憶部
２２５  リンク使用率情報記憶部
２２６  サーバ利用率情報記憶部
【図１】
2012169789.tif 000008
【図２】
2012169789.tif 000009
【図３】
2012169789.tif 000010
【図４】
2012169789.tif 000011
【図５】
2012169789.tif 000012
【図６】
2012169789.tif 000013
【図７】
2012169789.tif 000014
【図８】
2012169789.tif 000015
【図９】
2012169789.tif 000016
【図１０】
2012169789.tif 000017
【図１１】
2012169789.tif 000018
【図１２】
2012169789.tif 000019
【図１３】
2012169789.tif 000020