(57)【特許請求の範囲】
【請求項１】
インターネットプロトコルテレビ（ＩＰＴＶ）ネットワークのプロセッサを有するネットワークノードにおけるキャッシュのキャッシュメモリ割当を最適化するための方法であって、前記方法が、前記プロセッサにより実行される、
キャッシュ可能性関数を定義するステップと、
該キャッシュ可能性関数を最適化するステップと
を含み、
前記キャッシュ可能性関数を定義するステップにより定義される該キャッシュ可能性関数が、ネットワークノードのｉ番目のサービスに関するキャッシュ可能性ファクタｆｉ（ｍ）、
【数１】
0005427176.tif 000023
を計算し、ここで
Ｔｉはサービスｉに関するトラフィックであり、
Ｓｉはサービスｉに関するタイトルあたりのサイズであり、
ｍは使用されるメモリのユニットあたりのキャッシュであり、
Ｆｉ（ｍ／Ｓｉ）はサービスｉに関するキャッシュ有効性関数である、
方法。
【請求項２】
該キャッシュ可能性関数を最適化する前記ステップが、該キャッシュ可能性関数にメモリ限界を適用するステップを含む、請求項１に記載の方法。
【請求項３】
該キャッシュ可能性関数を最適化する前記ステップが、該キャッシュ可能性関数に処理能力トラフィック限界を適用するステップを含む、請求項１に記載の方法。
【請求項４】
前記ｉ番目のサービスが、ＩＰＴＶネットワークのＮサービスのｉ番目のサービスである、請求項１に記載の方法。
【請求項５】
前記プロセッサにより実行される、前記キャッシュ有効性関数を決定するステップを含む、請求項１に記載の方法。
【請求項６】
該キャッシュ有効性関数を決定する前記ステップが、式
【数２】
0005427176.tif 000024
を解くステップを含み、ここで、Ｍｉはサービスｉに関するキャッシュメモリであり、λ１およびλ２はラグランジュ乗数である、
請求項５に記載の方法。
【請求項７】
Ｍｉ≦Ｍであり、Ｍがキャッシュメモリのサイズである、請求項６に記載の方法。
【請求項８】
Ｍがネットワークノードにおける少なくとも１つのキャッシュメモリモジュールのサイズである、請求項７に記載の方法。
【請求項９】
前記プロセッサにより実行される、該キャッシュ有効性関数の最適解に基づいて、メモリ（ｍ）をｉ番目のサービスに割り当てるステップをさらに含む、請求項６に記載の方法。
【請求項１０】
キャッシュを備えるインターネットプロトコルテレビネットワークのネットワークノードであって、そのキャッシュのメモリサイズが、そのネットワークに関するキャッシュ可能性関数の最適解に基づき、
該キャッシュ可能性関数がキャッシュ有効性関数を含み、
キャッシュが少なくとも１つのキャッシュモジュールを含み、
該キャッシュ可能性関数が、キャッシュ有効性関数を最適化するためにその少なくとも１つのキャッシュモジュールを分割し、
キャッシュ有効性関数が最適化されるように、キャッシュメモリがネットワークのｉ番目のサービスに割り当てられ、
ネットワークのｉ番目のサービスに関するキャッシュ有効性関数が
【数３】
0005427176.tif 000025
を解くことによって決定され、この式は
【数４】
0005427176.tif 000026
および
【数５】
0005427176.tif 000027
という条件に従い、ここで、
【数６】
0005427176.tif 000028
−  ＜ｘである最大整数値であり、
Ｎ  −  サービスの総数であり、
Ｔｉ  −  サービスｉに関するトラフィックで、ｉ＝１、２、・・・、Ｎであり、
Ｆｉ（ｎ）  −  サービスｉに関する、キャッシュされたタイトルの数ｎに応じたキャッシュの有効性で、ｉ＝１、２、・・・、Ｎであり、
Ｍｉ  −  サービスｉに関するキャッシュメモリで、ｉ＝１、２、・・・、Ｎであり、
Ｓｉ  −  サービスｉに関するタイトルあたりのサイズで、ｉ＝１、２、・・・、Ｎである
ネットワークノード。
【請求項１１】
第１のプロセッサおよびその第１のプロセッサと通信する第２のプロセッサによって実行されるためのコンピュータ実行可能命令を含むコンピュータ可読媒体であって、実行時に
第１のプロセッサによって入力パラメータを第２のプロセッサに提供させ、
第２のプロセッサにＩＰＴＶネットワークのネットワークノードにおけるキャッシュのキャッシュメモリ割当を最適化するために
キャッシュ可能性関数を定義することと、
該キャッシュ可能性関数を最適化することと
を実行させる、
コンピュータ実行可能命令を含み、
前記キャッシュ可能性関数を定義することにより定義される該キャッシュ可能性関数が、ネットワークノードのｉ番目のサービスに関するキャッシュ可能性ファクタｆｉ（ｍ）、
【数７】
0005427176.tif 000029
を計算し、ここで
Ｔｉはサービスｉに関するトラフィックであり、
Ｓｉはサービスｉに関するタイトルあたりのサイズであり、
ｍは使用されるメモリのユニットあたりのキャッシュであり、
Ｆｉ（ｍ／Ｓｉ）はサービスｉに関するキャッシュ有効性関数である、
コンピュータ可読媒体。
【請求項１２】
さらに、第２のプロセッサに該キャッシュ有効性関数を決定させるコンピュータ実行可能命令を含む、請求項１１に記載のコンピュータ可読媒体。
【請求項１３】
さらに、第２のプロセッサに、式
【数８】
0005427176.tif 000030
を解かせるコンピュータ実行可能命令を含み、ここで、Ｍｉはサービスｉに関するキャッシュメモリであり、λ１およびλ２はラグランジュ乗数である、請求項１２に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、参照によりその開示が本明細書に組み込まれる、２００７年８月３０日に出願された米国仮出願第６０／９６９，１６２号の優先権を主張するものである。
【０００２】
本発明は、インターネットプロトコルテレビ（ＩＰＴＶ）ネットワークに関し、具体的にはそのネットワーク内のノードにおいてビデオコンテンツをキャッシュすることに関するものである。
【背景技術】
【０００３】
ＩＰＴＶネットワークでは、ビデオオンデマンド（ＶＯＤ）および他のビデオサービスが、ビデオ本局（ＶＨＯ）（Ｖｉｄｅｏ  Ｈｅａｄ  Ｏｆｆｉｃｅ）から加入者への大量のユニキャストトラフィックを生成するため、ネットワーク内でかなりの帯域幅および機器資源を必要とする。このトラフィックを減らし、その後全体的なネットワーク費用を減らすため、最も人気のあるタイトルなど、ビデオコンテンツの一部を加入者にとってより近くにあるキャッシュ中に記憶することができる。例えば、キャッシュは、デジタル加入者線アクセスマルチプレクサ（ＤＳＬＡＭ）（Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ  Ａｃｃｅｓｓ  Ｍｕｌｔｉｐｌｅｘｅｒ）、中央局（ＣＯ）、または中間局（ＩＯ）内に設けることができる。キャッシュするためのコンテンツの選択は、キャッシュのサイズ、コンテンツの人気、等を含むいくつかの要素によって決まり得る。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＩＰＴＶネットワーク内で、キャッシュメモリのサイズおよび位置を最適化するためのシステムおよび方法が求められている。
【課題を解決するための手段】
【０００５】
本開示の一態様では、インターネットプロトコルテレビ（ＩＰＴＶ）ネットワークのネットワークノードにおけるキャッシュのキャッシュメモリ割当を最適化するための方法であって、キャッシュ可能性関数（ｃａｃｈｅａｂｉｌｉｔｙ  ｆｕｎｃｔｉｏｎ）を定義するステップと、そのキャッシュ可能性関数を最適化するステップとを含む、方法が提供されている。
【０００６】
本開示の一態様では、キャッシュを備えるインターネットプロトコルテレビネットワークのネットワークノードであって、そのキャッシュのメモリサイズが、そのネットワークに関するキャッシュ関数の最適解に基づく、ネットワークノードが提供されている。
【０００７】
本開示の一態様では、第１のプロセッサおよびその第１のプロセッサと通信する第２のプロセッサによって実行されるためのコンピュータ実行可能命令を含むコンピュータ可読媒体であって、実行時に第１のプロセッサによって入力パラメータを第２のプロセッサに提供させ、第２のプロセッサにＩＰＴＶネットワークのネットワークノードにおけるキャッシュ用の少なくとも１つのキャッシュ関数を計算させるコンピュータ実行可能命令を含む、コンピュータ可読媒体が提供されている。
【０００８】
次に、例としてのみ提供する具体的な実施形態および添付の図面について言及する。
【図面の簡単な説明】
【０００９】
【図１】ＩＰＴＶネットワークの概略図である。
【図２】人気分布曲線を示す図である。
【図３】搬送帯域幅の問題を示す図である。
【図４】入力パラメータテーブルを示す図である。
【図５】ネットワーク費用計算の流れ図である。
【図６】キャッシュ関数の最適化を示す図である。
【図７】システムプロセッサおよびユーザプロセッサを示す図である。
【発明を実施するための形態】
【００１０】
図１に示す典型的なＩＰＴＶアーキテクチャ１０では、数名の加入者１２がデジタル加入者線アクセスマルチプレクサ（ＤＳＬＡＭ）１４に接続されている（例えば１９２：１の比率）。ＤＳＬＡＭ１４は、中央局ＣＯ１６に接続されている（例えば１００：１の比率）。いくつかのＣＯ１６が、中間局（ＩＯ）１８に、そして最終的にはビデオ本局（ＶＨＯ）１９に接続されている（例えば６：１の比率）。ＶＨＯ１９は、ビデオオンデマンド（ＶｏＤ）コンテンツのタイトルを、例えばコンテンツデータベース２２に記憶する。１ギガビットイーサネット（登録商標）（ＧＥ）接続２３がＤＳＬＡＭ１４をＣＯ１６に接続するのに対し、１０ＧＥ接続２４、２５がＣＯ１６をＩＯ１８に、そしてＩＯ１８をＶＨＯ１９にそれぞれ接続する。
【００１１】
ＩＰＴＶネットワーク１０上のユニキャストＶｏＤトラフィックの費用影響を減らすために、ビデオコンテンツの一部を加入者にとってより近くにあるキャッシュ中に記憶することができる。様々な実施形態において、キャッシュは、ＤＳＬＡＭ、ＣＯ、またはＩＯのうちの一部もしくはすべてにおいて備えることができる。一実施形態では、キャッシュは、限られた量のデータ、例えば最大３０００テラバイト（ＴＢ）まで記憶可能なキャッシュモジュール１５の形で提供することができる。さらに、各キャッシュモジュールは限られた量のトラフィック、例えば最大２０Ｇｂｓまでサポート可能とすることができる。このキャッシュモジュールは、対応するネットワーク機器において１つのスロットを使用するように提供され得るので便利である。
【００１２】
一実施形態では、キャッシュはレイヤ、例えばＤＳＬＡＭ、ＣＯ、またはＩＯのうちの１つのあらゆる位置に設けられる。つまり、キャッシュはこのネットワークの各ＤＳＬＡＭ１４、各ＣＯ１６、または各ＩＯ１８内に設けられる。
【００１３】
各キャッシュの有効性は、そのキャッシュから供給され得るビデオコンテンツ要求の割合として表すことができる。キャッシュの有効性は、ＩＰＴＶネットワークの経済的側面の重要な要素である。
【００１４】
キャッシュの有効性は、（キャッシュメモリおよびビデオサイズと相関関係にある）キャッシュに記憶されているタイトルの数や、人気分布によって表すことができる、キャッシュに記憶されているタイトルの人気を含むいくつかの要素によって決まる。
【００１５】
キャッシュメモリが増加するにつれてキャッシュの有効性も増加するが、費用も同様に増す。ビデオコンテンツの搬送費用は、ネットワーク上のすべてのキャッシュの合計費用と引き換えられる。キャッシュの有効性は、人気曲線とも相関関係にある。図２に、人気分布の一例２０を示す。この人気分布曲線２０は、Ｚｉｐｆ関数または一般Ｚｉｐｆ関数（ｇｅｎｅｒａｌｉｚｅｄ  Ｚｉｐｆ  ｆｕｎｃｔｉｏｎ）によって表される：
Ｚｉｐｆ＝１／ｘａ
【００１６】
この人気曲線が平らになるにつれ、キャッシュの有効性は低下する。
【００１７】
キャッシュメモリの最適な位置およびサイズを見つけるために、最適化モデルおよびツールが提供される。このツールは、典型的なメトロトポロジ、ビデオコンテンツの人気曲線、費用／トラフィック想定、等を所与として、最適なキャッシュサイズおよびそのキャッシュのネットワーク位置を選択する。一実施形態では、このツールは、キャッシュの有効性、キャッシュの位置、等に基づいてネットワーク費用全体も最適化する。キャッシングの有効性は、メモリおよび人気曲線と相関関係にあり、メモリが増加すると効率（およびキャッシュ費用）の増加をもたらすが、搬送費用は低減される。したがってこの最適化ツールは、キャッシュ用の最適なメモリを選択して、全体的なネットワーク費用を低減するために使用することができる。
【００１８】
ネットワーク総費用の一要素は、搬送帯域幅の費用である。搬送帯域幅の費用は加入者あたりの帯域幅、および加入者数と相関関係にある。キャッシュすることは、上述のようにメモリおよび人気分布と相関関係にあるキャッシュの有効性により、上流の帯域幅を低減する。図３に、搬送帯域幅の費用の問題を図示する。Ｔｄは、ＤＳＬＡＭノード（ｄ）３１への搬送費用を表し、加入者（ｓｕｂ）数および加入者あたりの帯域幅（ＢＷ）に依拠する。したがってＴｄは次式で表すことができる：
Ｔｄ＝加入者数＊ＢＷ／加入者
【００１９】
ＴＣＯは中央局３２への搬送費用であり、次式で表される：
ＴＣＯ＝ｄの数＊Ｔｄ
【００２０】
ＴＩＯは中間局３３への搬送費用であり、次式で表される：
ＴＩＯ＝ＩＯの数＊ＴＣＯ
【００２１】
ＶＨＯトラフィックは、ＶＨＯ３４からのネットワーク上のすべてのＶＨＯトラフィックの搬送費用であり、次式で表される：
ＶＨＯトラフィック＝Σ  ＴＩＯ
【００２２】
要求される搬送帯域幅は、ＤＳＬＡＭ、ＣＯ、ＩＯなどの機器を寸法決定し、ネットワーク内で必要とされるこれらの要素それぞれの数を決定するために使用することができる。
【００２３】
図４は、最適化ツール用の入力パラメータのパラメータテーブル４０を示す。パラメータテーブル４０に関するサンプルデータも提供されている。例えばこのパラメータテーブルは、ユーザが活動中の加入者あたりの平均トラフィック４１や、ＤＳＬＡＭあたりの活動中の加入者数４２などの主要パラメータを入力できるようにする。ＤＳＬＡＭの数４３、ＣＯの数４４、ＩＯの数４５などのネットワーク構成パラメータも与えることができる。キャッシュモジュールあたりのメモリ４６、最大キャッシュトラフィック４７、キャッシュモジュールの費用４８などのキャッシュモジュールパラメータも与えることができる。人気曲線パラメータ４９も入力することができる。スイッチ、ルータ、他のハードウェアコンポーネントなど、他のネットワーク機器の費用５１も規定することができる。
【００２４】
このパラメータテーブル４０は、ネットワーク費用計算で使用する、より広範な最適化ツールに組み込むことができる。
【００２５】
図５に、ネットワーク費用を特定するための流れ図５０を示す。このネットワーク費用は、次式で表すことができる：
ネットワーク費用５１０＝機器費用＋搬送費用
【００２６】
機器費用は、ＤＳＬＡＭ、ＣＯ、ＩＯ、およびＶＨＯ、ならびにＶｏＤサーバおよびキャッシュすべての費用である。この機器費用は、ＤＳＬＡＭ、ＣＯ、およびＩＯのそれぞれについての寸法決定を検討することによって分類できる。ＤＬＳＡＭの寸法決定（ステップ５０１）は、以下の費用検討を必要とする：
ａ．ＤＳＬＡＭあたりの合計キャッシュメモリ＝ユニットあたりのキャッシュメモリ×ＤＳＬＡＭあたりのキャッシュユニット数
ｂ．キャッシュ中のコンテンツユニット数＝ＤＳＬＡＭあたりの合計キャッシュメモリ／コンテンツのユニットあたりの平均所要メモリ量
ｃ．キャッシュの有効性（すなわちキャッシュによって供給される要求の割合）＝ＣＤＦ−１（キャッシュ中のコンテンツユニット数）、ここで、ＣＤＦは人気分布の累積密度関数である
ｄ．合計キャッシュ処理能力＝キャッシュユニット数×ユニットあたりのキャッシュ処理能力
ｅ．ＤＳＬＡＭに接続されているすべての加入者からのトラフィック総需要（ＤＳＬＡＭトラフィック）＝ＤＳＬＡＭあたりの加入者数×加入者あたりの平均トラフィック
ｆ．ＤＳＬＡＭあたりのＣＯからＤＳＬＡＭへのトラフィック＝ＤＳＬＡＭトラフィック−ｍｉｎ（合計キャッシュ処理能力、キャッシュの有効性×ＤＳＬＡＭトラフィック）
ｇ．
【数１】
0005427176.tif 000002
ｈ．
【数２】
0005427176.tif 000003
【００２７】
ＣＯの寸法決定（ステップ５０２）は以下を必要とする：
ａ．ＣＯあたりのＤＳＬＡＭに向いたＧＥ接続の数＝ＤＳＬＡＭあたりのＧＥ接続の数×ＣＯあたりのＤＳＬＡＭの数
ｂ．ＣＯに接続されているすべてのＤＳＬＡＭからのトラフィック総需要（ＣＯトラフィック）＝ＤＳＬＡＭあたりのＣＯからＤＳＬＡＭへのトラフィック×ＣＯあたりのＤＳＬＡＭの数
ｃ．ＧＥ平均利用率＝ＣＯトラフィック／ＣＯあたりのＤＳＬＡＭに向いたＧＥ接続の数
ｄ．イーサネット（登録商標）サービススイッチ（例えばＡｌｃａｔｅｌ  Ｌｕｃｅｎｔによって製造される７４５０イーサネット（登録商標）サービススイッチ）あたりの、ＤＳＬＡＭに向いたＧＥポートの最大数（ｎ）の計算であり、
【数３】
0005427176.tif 000004
となり、
ここで：
ｉ．７４５０あたりのＩＯからＣＯへのトラフィック＝７４５０あたりのＣＯからＤＳＬＡＭへのトラフィック−ｍｉｎ（合計キャッシュ処理能力、キャッシュの有効性×７４５０あたりのＣＯからＤＳＬＡＭへのトラフィック）であり、
ｉｉ．７４５０あたりのＣＯからＤＳＬＡＭへのトラフィック＝ｎ×ＧＥ平均利用率である。
ｅ．
【数４】
0005427176.tif 000005
ｆ．
【数５】
0005427176.tif 000006
ｇ．ＣＯあたりのＧＥ  ＭＤＡ、１０ＧＥ  ＭＤＡ、およびＩＯＭの総数の計算。
【００２８】
ＩＯの寸法決定（ステップ５０３）は以下を必要とする：
ａ．ＩＯあたりのＣＯに向いた１０ＧＥ接続の数＝ＣＯあたりの１０ＧＥ接続の数×ＩＯあたりのＣＯの数
ｂ．ＩＯに接続されているすべてのＣＯからのトラフィック総需要（ＩＯトラフィック）＝ＣＯあたりのＩＯからＣＯへのトラフィック×ＩＯあたりのＣＯの数
ｃ．１０ＧＥ平均利用率＝ＩＯトラフィック／ＩＯあたりのＣＯに向いた１０ＧＥ接続の数
ｄ．サービスルータ（例えばＡｌｃａｔｅｌ−Ｌｕｃｅｎｔによる７７５０サービスルータ）あたりの、ＣＯに向いた１０ＧＥポートの最大数（ｍ）の計算であり、
【数６】
0005427176.tif 000007
となり、
ここで：
ｉ．７７５０あたりのＶＨＯからＩＯへのトラフィック＝７７５０あたりのＩＯからＣＯへのトラフィック−ｍｉｎ（合計キャッシュ処理能力、キャッシュの有効性×７７５０あたりのＩＯからＣＯへのトラフィック）であり、
ｉｉ．７７５０あたりのＩＯからＣＯへのトラフィック＝ｍ×１０ＧＥ平均利用率である。
ｅ．
【数７】
0005427176.tif 000008
ｆ．
【数８】
0005427176.tif 000009
ｇ．ＩＯあたりの１０ＧＥ  ＭＤＡおよびＩＯＭの総数の計算。
【００２９】
ＶＨＯの寸法決定（ステップ５０４）は以下を必要とする：
ａ．ＶＨＯあたりのＩＯに向いた１０ＧＥ接続の数＝ＩＯあたりのＶＨＯからＩＯへの１０ＧＥ接続の数×ＶＨＯあたりのＩＯの数
ｂ．ＶＨＯに接続されているすべてのＩＯからのトラフィック総需要（ＶＨＯトラフィック）＝ＣＯあたりのＩＯからＣＯへのトラフィック×ＩＯあたりのＣＯの数
ｃ．１０ＧＥ平均利用率＝ＶＨＯトラフィック／ＶＨＯあたりのＩＯに向いた１０ＧＥ接続の数
ｄ．ＶＨＯ内の７７５０（サービスルータ）あたりの、ＩＯに向いた１０ＧＥポートの最大数（ｋ）の計算であり、
【数９】
0005427176.tif 000010
となり、
ここで：
ｉ．ＶＨＯ内の７７５０あたりのＶＨＯからＩＯへのトラフィック＝ｋ×１０ＧＥ平均利用率である。
ｅ．
【数１０】
0005427176.tif 000011
ｆ．
【数１１】
0005427176.tif 000012
ｇ．ＶＨＯあたりの１０ＧＥ  ＭＤＡおよびＩＯＭの総数の計算。
【００３０】
機器費用は、キャッシュの共通費にメモリ費用を加えたものに等しいキャッシュ費用も含む。ネットワークの搬送費用は、ネットワークノード間のすべてのＧＥ接続５０６および１０ＧＥ接続５０５の費用である。
【００３１】
様々なビデオサービス（例えばＶｏＤ、ＮＰＶＲ、ＩＣＣ、等）は、様々なキャッシュの有効性（またはヒット率）を有し、様々なタイトルのサイズを有する。対処すべき問題は、キャッシングの全体的な費用有効性を高めるために、どのように限られた資源、すなわちキャッシュメモリを様々なサービス間で分割できるのかである。
【００３２】
いくつかのユニキャストビデオサービス間でキャッシュメモリを最適に分割するこの問題は、「ナップザック問題」と同様の制約最適化問題とみなすことができ、例えば線形整数計画法によって解くことができる。しかし、上述の変数の数を所与として、解を探すにはかなりの計算時間を要する可能性がある。したがって本開示の一実施形態では、最適解を見つけるプロセスを迅速化する専用のメトリック「キャッシュ可能性」を定義することにより、この計算の問題が低減される。このキャッシュ可能性ファクタは、サービスあたりのキャッシュの有効性、合計トラフィック、および１タイトルのサイズを考慮に入れる。
【００３３】
この方法では、キャッシュメモリおよび処理能力限界の制約を受ける全体的なキャッシュヒット率を最大化する、（サービスごとの）キャッシュされるタイトルの最適数を見つけるために、キャッシュ可能性ファクタおよび反復プロセスを使用する。
【００３４】
キャッシュ有効性関数（またはヒット率関数）は、トラフィックの統計的特徴（長期／短期のタイトル人気度）、およびキャッシュコンテンツを更新するためのキャッシングアルゴリズムの有効性によって決まる。様々なサービスは、様々なキャッシュ有効性関数を有する。目標は、利用可能なキャッシュメモリＭおよびキャッシュトラフィック処理能力Ｔの制約を受ける、キャッシュの有効性を最大化することである。一実施形態では、キャッシュの有効性は、トラフィック量によって重み付けされた合計キャッシュヒット率として定義される。代替実施形態では、キャッシュの有効性は、使用されるキャッシュメモリの最小化（ｍｉｎｉｍｉｚａｔｉｏｎ）で重み付けすることができる。
【００３５】
この問題は制約最適化問題として表すことができ、すなわち次式が成立する：
【数１２】
0005427176.tif 000013
であって、この式は
【数１３】
0005427176.tif 000014
および
【数１４】
0005427176.tif 000015
という条件に従い、ここで、
【数１５】
0005427176.tif 000016
−  ＜ｘである最大整数値であり、
Ｎ  −  サービスの総数であり、
Ｔｉ  −  サービスｉに関するトラフィックで、ｉ＝１、２、・・・、Ｎであり、
Ｆｉ（ｎ）  −  サービスｉに関する、キャッシュされたタイトルの数ｎに応じたキャッシュの有効性で、ｉ＝１、２、・・・、Ｎであり、
Ｍｉ  −  サービスｉに関するキャッシュメモリで、ｉ＝１、２、・・・、Ｎであり、
Ｓｉ  −  サービスｉに関するタイトルあたりのサイズで、ｉ＝１、２、・・・、Ｎである。
【００３６】
キャッシュの有効性Ｆｉ（ｎ）は、ｉ番目のサービスのｎ個のアイテム（タイトル）がキャッシュされ得る場合に、キャッシュから供給され得るこのｉ番目のサービスについてのトラフィックの比率である。
【００３７】
この問題は、線形整数計画として公式化し、ＬＰ解法によって解くことができる。
【００３８】
この問題の連続的な公式化は、上記の公式化と似ている：
【数１６】
0005427176.tif 000017
であって、この式は
【数１７】
0005427176.tif 000018
および
【数１８】
0005427176.tif 000019
という条件に従い、
ラグランジュ乗数手法を使用して解くことができる。ラグランジュ乗数法は、１つまたは複数の制約を受ける多変数関数の極値を見つけるために使用され、非線形制約付き最適化における基本ツールである。ラグランジュ乗数は、制約付き関数の定留点（ｓｔａｔｉｏｎａｒｙ  ｐｏｉｎｔｓ）を計算する。極値は、これらの点において、またはこの関数が微分不可能である境界上もしくは点において存在する。この問題にラグランジュ乗数法を適用すると次式が得られる：
【数１９】
0005427176.tif 000020
または
【数２０】
0005427176.tif 000021
ｉ＝１、２、・・・、Ｎである。
【００３９】
これらの等式は、制約関数の定留点を表す。最適解は、（例えばＭｉ＝０またはＭｉ＝Ｍである）定留点においてまたは境界上で得ることができる。
【００４０】
以下に「キャッシュ可能性」関数を定義する：
【数２１】
0005427176.tif 000022
この式は、ｉ番目のサービス（ｉ＝１、２、・・・、Ｎ）に関する、使用されるメモリ（ｍ）のユニットあたりのキャッシングの効果を数量化する。
【００４１】
この問題の最適解を見つけるためにキャッシュ可能性関数をどのように使用できるのかを示すために、サービスが２つしかない簡略化された例を検討することができる。関数ｆ１およびｆ２が同じグラフ上にプロットされる場合（図６）、キャッシュ可能性曲線ｆ１およびｆ２と交差する横線Ｈ（水平線）ごとに、サービスに使用されるキャッシュメモリの量および対応するトラフィック処理能力が推定され得る。水平線Ｈが下に移動されると、使用されるキャッシュメモリの量ならびにトラフィック処理能力が増加する。メモリまたはトラフィックの限界（いずれか早い方）に到達するとき、最適解が得られる。状況に応じて、最適解は、水平線が（ａ）１つの曲線に交差し（水平線Ｈ１）、または（ｂ）両方の曲線に交差する（水平線Ｈ２）場合に得ることができる。（ａ）の場合では、キャッシュメモリは１つだけのサービス（ｆ１）に対して割り当てられることになる。（ｂ）の場合では、サービスｆ１およびｆ２の両方が、キャッシュｍ１およびｍ２においてキャッシュメモリを共用することになる。
【００４２】
キャッシュ可能性関数およびキャッシュ有効性関数を使用してキャッシュメモリが決定されると、このキャッシュ割当を、ネットワーク総費用を決定するためのネットワーク費用計算に入れることができる。さらに、このキャッシュ可能性関数およびキャッシュ有効性関数は、キャッシュの性能を最適化するために、キャッシュメモリが各サービスのために確保された状態でキャッシュが適当に分割されることを確実にするために、継続的ベースで計算することができる。
【００４３】
一実施形態では、この最適化ツールは、図７に示すような１つまたは複数のプロセッサ上に実施することができる。第１のプロセッサ７１は、キャッシュ可能性関数および／またはキャッシュ有効性関数を計算するためのソフトウェアなど、１組の命令を記憶するシステムメモリ７２に動作可能に関連するシステムプロセッサとすることができる。システムプロセッサ７１は、同様にメモリ７６に動作可能に関連するユーザプロセッサなどの第２のプロセッサ７３からパラメータ情報を受け取ることができる。メモリ７６は、実行時にユーザプロセッサ７３がユーザから入力パラメータ等を受け取ることを可能にする１組の命令を記憶することができる。キャッシュ可能性関数および／またはキャッシュ有効性関数の計算は、システムプロセッサ７１またはユーザプロセッサ７３のいずれにおいて実行されてもよい。例えば、ユーザからの入力パラメータを、ユーザプロセッサ７３からシステムプロセッサ７１に渡して、計算を行うための命令をシステムプロセッサ７１が実行できるようにすることができる。あるいは、このシステムプロセッサが公式および他の必要なコードをメモリ７２からユーザプロセッサ７３に渡すこともでき、それらが入力パラメータと組み合わせられるとき、プロセッサ７３がキャッシュ可能性関数および／またはキャッシュ有効性関数を計算することを可能にする。追加のプロセッサおよびメモリを設けることができ、キャッシュ関数の計算は任意の適当なプロセッサ上で実行できることが理解されよう。一実施形態では、これらのキャッシュ関数を継続的に計算することによりキャッシュ分割を最適な状態に維持できるように、プロセッサのうちの少なくとも１つがネットワークノード内に設けられ、そのネットワークノードのキャッシュに動作可能に関連し得る。
【００４４】
本発明の実施形態を添付の図面に示し前述の記載において説明してきたが、本発明は開示した実施形態に限定されず、添付の特許請求の範囲に明記し、定義する本発明の趣旨から逸脱することなく多数の再構成、修正、および代用が可能であることが理解されよう。例えば本発明の諸機能はブロック、モジュール、プロセッサ、またはメモリの１つもしくは複数によって完全におよび／または部分的に実行することができる。また、これらの機能は現行の方法でもしくは広まっている方法等で、または情報を提供しかつ／または受け取ることができる任意の装置によって実行することができる。さらに、特定の方法で示したが、本発明の範囲から逸脱することなく様々なモジュールまたはブロックは再配置することができる。なおさらに、特定の方法で示したが、本発明を達成し、本発明にさらなる知られている特徴を提供し、かつ／または本発明をより効率的にするために、本発明に関してより多数のまたはより少数のモジュールおよび接続を利用することができる。また、様々なモジュール間で送信される情報は、データネットワーク、インターネット、インターネットプロトコルネットワーク、無線ソース、および有線ソースのうちの少なくとも１つを介して、かつ複数のプロトコルによりそれらのモジュール間で送信することができる。
【図１】
0005427176.tif 000031
【図２】
0005427176.tif 000032
【図３】
0005427176.tif 000033
【図４】
0005427176.tif 000034
【図５】
0005427176.tif 000035
【図６】
0005427176.tif 000036
【図７】
0005427176.tif 000037