(57)【特許請求の範囲】
【請求項１】
データ・ファイルのパケットについての、宛先デバイスからの要求を受信し、
（ｉ）各宛先デバイスによって要求される各パケットが、競合グラフの複数の頂点の中の異なる頂点によって表され、（ｉｉ）前記複数の頂点が、前記宛先デバイスに関連づけられ、また（ｉｉｉ）リンクが、前記複数の頂点のうちのどれが同じ要求されたパケットを表すかと、どの要求されたパケットが、宛先デバイスに属するキャッシュに記憶されるかとに基づいて、前記複数の頂点の間で作り出されるように、前記競合グラフを構築し、
前記リンクに基づいて、前記複数の頂点をグループに割り当て、
前記要求されたパケットにラベル付けするために、前記割当てに基づいて、前記複数の頂点を着色し、
同じカラーを有する頂点によって表される前記パケットを結合し、そして
前記結合されたパケットを送信する
ように構成されたプロセッサ
を備えているネットワーク要素。
【請求項２】
前記リンクは、（ｉ）第１の頂点と、第２の頂点とが、同じパケットを表しておらず、且つ、（ｉｉ）前記第１の頂点によって表されるパケットが、前記第２の頂点に関連する宛先デバイスのキャッシュに記憶されず、または前記第２の頂点によって表される前記パケットが、前記第１の頂点に関連する宛先デバイスのキャッシュに記憶されない場合に、あるリンクが、前記複数の頂点のうちの前記第１の頂点と、前記第２の頂点との間で作り出されるように、作り出される、請求項１に記載のネットワーク要素。
【請求項３】
前記グループは、前記複数の頂点に対するリンクの数を示す、請求項１に記載のネットワーク要素。
【請求項４】
プロセッサは、前記複数の頂点のうちのどれが、最小の数のリンクを有しているかと、前記複数の頂点のうちのどれが、最大の数のリンクを有しているかとを決定し、
前記最小の数のリンクを有する前記頂点に対するリンクの前記数と、前記最大の数のリンクを有する前記頂点に対するリンクの前記数とに基づいて、しきい値の値を算出し、そして
前記しきい値の値に基づいて、前記複数の頂点の部分集合を構築する
ように構成されている、請求項３に記載のネットワーク要素。
【請求項５】
前記プロセッサは、
前記部分集合から頂点を選択し、
前記選択された頂点にリンクされる頂点のカラーを決定し、そして
前記決定に基づいて、前記選択された頂点を着色する
ように構成されている、請求項４に記載のネットワーク要素。
【請求項６】
前記プロセッサは、
カラーの第１の集合として、前記選択された頂点にリンクされる頂点のカラーを、またカラーの第２の集合として、前記競合グラフの既存のカラーを識別し、
カラーの前記第１の集合と、カラーの前記第２の集合とが、一致しない場合に、前記第２の集合の中の望ましいカラーを用いて、前記選択された頂点を着色し、そして
カラーの前記第１の集合と、カラーの前記第２の集合とが、一致する場合に、新しいカラーを用いて、前記選択された頂点を着色する
ように構成されている、請求項５に記載のネットワーク要素。
【請求項７】
前記プロセッサは、前記複数の頂点が着色されるまで、着色するように構成されている、請求項６に記載のネットワーク要素。
【請求項８】
前記プロセッサは、前記複数の着色された頂点のカラーを含むように、カラーの前記第２の集合をアップデートするように構成されている、請求項７に記載のネットワーク要素。
【請求項９】
前記プロセッサは、
前記競合グラフの既存のカラーから第１のカラーを選択すること、
前記第１のカラーを有する頂点を識別すること、
前記既存のカラーから第２のカラーを選ぶこと、および
前記識別された頂点にリンクされる頂点が前記第２のカラーを用いて着色されていない場合に、該第２のカラーで前記第１のカラーを置換すること、
により、前記第２の集合の中のカラーの前記数を低減させるように、前記複数の着色された頂点に対してローカル・サーチを実行するように構成されている、請求項８に記載のネットワーク要素。
【請求項１０】
前記プロセッサは、前記同じカラーを有する前記頂点によって表される前記パケットに対して、排他的論理和オペレーションまたは他の線形結合オペレーションを実行することにより、結合するように構成されている、請求項１に記載のネットワーク要素。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、その全体の内容が、参照により本明細書に組み込まれている、２０１４年１月２２日に出願した米国仮出願第６１／９３０，０７２号の３５Ｕ．Ｓ．Ｃ．§１１９（ｅ）の下の優先権を主張するものである。
【０００２】
本発明は、ネットワーク符号化された、またキャッシング支援されたコンテンツ配信のためのデバイスおよび方法に関する。
【背景技術】
【０００３】
現在では、コンテンツ配信ネットワーク（ＣＤＮ：ｃｏｎｔｅｎｔ  ｄｉｓｔｒｉｂｕｔｉｏｎ  ｎｅｔｗｏｒｋｓ）は、オンデマンドのオーディオ／ビデオ・ストリーミングの人気における増大に関連する容量問題と、効率問題とに直面している。これらの問題に対処すべき１つのやり方は、ネットワーク・キャッシングと、ネットワーク符号化とによるものである。例えば、従来のコンテンツ配信ネットワーク（ＣＤＮ）の問題解決手法は、ネットワークの内部のキャッシング・ロケーションの間のコンテンツ・コピーの配置のための中央集中されたアルゴリズムを使用している。従来の問題解決手法はまた、ＬＲＵ（最も長い間使用されていない（ｌｅａｓｔ  ｒｅｃｅｎｔｌｙ  ｕｓｅｄ）ポリシー）やＬＦＵ（使用頻度が最も低い（ｌｅａｓｔ  ｆｒｅｑｕｅｎｔｌｙ  ｕｓｅｄ）ポリシー）などのキャッシュ置換ポリシーを含んでいて、キャッシュ・ヒット率を改善するために分散型キャッシュをローカルに管理している。他の従来の問題解決手法は、ランダム線形ネットワーク符号化を使用して、グループの中でパケットを転送しており、これは、容量の限られたネットワークの中でスループットを改善することができる。
【０００４】
しかしながら、従来のネットワーク・キャッシング問題解決手法と、ネットワーク符号化問題解決手法とは、キャッシング・リソースと、送信リソースとの相対的な効率を考慮してはいない。これは、配信されたオブジェクトまたはファイル当たりの準最適なコストをもたらす。さらに、従来のコンテンツ配信問題解決手法は、ネットワーク・キャッシングと、ネットワーク符号化との可能性のある組み合わされた利点を活用してはいない。
【発明の概要】
【課題を解決するための手段】
【０００５】
少なくとも１つの例示の実施形態によれば、ネットワークの中でデータ・ファイルを送信するための方法は、データ・ファイルのパケットについての宛先デバイスからの要求を受信するステップを含んでいる。（ｉ）各宛先デバイスによって要求される各パケットが、競合グラフの複数の頂点の中の異なる頂点によって表され、（ｉｉ）複数の頂点が、宛先デバイスに関連づけられ、また（ｉｉｉ）リンクが、複数の頂点のうちのどれが同じ要求されたパケットを表すかと、どの要求されたパケットが宛先デバイスに属するキャッシュに記憶されるかとに基づいて、複数の頂点の間に作り出されるように、本方法は、競合グラフを構築するステップを含んでいる。本方法は、それらのリンクに基づいて、複数の頂点をグループに割り当てるステップを含んでいる。本方法は、要求されたパケットにラベル付けするために、その割当てに基づいて、複数の頂点を着色するステップを含んでいる。本方法は、同じカラーを有する頂点によって表されるパケットを結合するステップを含んでいる。本方法は、結合されたパケットを送信するステップを含んでいる。
【０００６】
少なくとも１つの例示の実施形態によれば、（ｉ）第１の頂点と、第２の頂点とが、同じパケットを表しておらず、また（ｉｉ）第１の頂点によって表されるパケットが、第２の頂点に関連する宛先デバイスのキャッシュに記憶されず、または第２の頂点によって表されるパケットが、第１の頂点に関連する宛先デバイスのキャッシュに記憶されない場合に、あるリンクが、複数の頂点のうちの第１の頂点と、第２の頂点との間で作り出されるように、それらのリンクは作り出される。
【０００７】
少なくとも１つの例示の実施形態によれば、それらのグループは、複数の頂点に対するリンクの数を示す。
【０００８】
少なくとも１つの例示の実施形態によれば、着色するステップは、複数の頂点のうちのどれが、最小の数のリンクを有しているかと、複数の頂点のうちのどれが、最大の数のリンクを有しているかとを決定するステップを含んでいる。着色するステップは、最小の数のリンクを有する頂点に対するリンクの数と、最大の数のリンクを有する頂点に対するリンクの数とに基づいて、しきい値の値を算出するステップを含んでいる。着色するステップは、しきい値の値に基づいて、複数の頂点の部分集合を構築するステップを含んでいる。
【０００９】
少なくとも１つの例示の実施形態によれば、着色するステップは、その部分集合から頂点を選択するステップと、選択された頂点にリンクされる頂点のカラーを決定するステップと、その決定に基づいて、選択された頂点を着色するステップを含む。
【００１０】
少なくとも１つの例示の実施形態によれば、カラーを決定するステップは、カラーの第１の集合として、選択された頂点にリンクされる頂点のカラーを、またカラーの第２の集合として、競合グラフの既存のカラーを識別する。選択された頂点を着色するステップは、カラーの第１の集合と、カラーの第２の集合とが、一致しない場合に、第２の集合の中の望ましいカラーを用いて、選択された頂点を着色するステップと、カラーの第１の集合と、カラーの第２の集合とが、一致する場合に、新しいカラーを用いて、選択された頂点を着色するステップとを含む。
【００１１】
少なくとも１つの例示の実施形態によれば、着色するステップは、複数の頂点が着色されるまで、実行される。
【００１２】
少なくとも１つの例示の実施形態によれば、本方法は、複数の着色された頂点のカラーを含むように、カラーの第２の集合をアップデートするステップを含んでいる。
【００１３】
少なくとも１つの例示の実施形態によれば、本方法は、第２の集合の中のカラーの数を低減させるように、複数の着色された頂点に対してローカル・サーチを実行するステップを含んでいる。ローカル・サーチは、競合グラフの既存のカラーからあるカラーを選択するステップと、選択されたカラーを用いて頂点を識別するステップと、識別された頂点にリンクされる頂点が、異なるカラーで着色されない場合に、既存のカラーから選択される異なるカラーで選択されたカラーを置換するステップとを含む。
【００１４】
少なくとも１つの例示の実施形態によれば、結合するステップは、同じカラーを有する頂点によって表されるパケットに対して排他的論理和オペレーションまたは他の線形結合オペレーションを実行する。
【００１５】
上記の方法は、通信ネットワークにおいて、ネットワーク要素（例えば、コンテンツ・ソース）によって実行され得ることを理解すべきである。
【００１６】
例示の実施形態は、以下で本明細書において与えられる詳細な説明と、添付の図面とから、より十分に理解されることになり、そこでは、同様な要素は、同様な参照番号によって表され、この参照番号は、例証としてだけ与えられ、またこのようにして例示の実施形態を限定するものではない。
【図面の簡単な説明】
【００１７】
【図１】少なくとも１つの例示の実施形態によるコンテンツ配信ネットワークを示す図である。
【図２】例示の一実施形態によるネットワーク要素の例示の構造を示す図である。
【図３Ａ】図２におけるネットワーク要素の例示のオペレーションを示すフロー・チャートである。
【図３Ｂ】図２におけるネットワーク要素の例示のオペレーションを示すフロー・チャートである。
【図４】少なくとも１つの例示の実施形態による、配信フェーズについての例示のオペレーションを示す図である。
【図５】少なくとも１つの例示の実施形態による、方向づけのない競合グラフを構築するための例示のオペレーションを示す図である。
【図６】少なくとも１つの例示の実施形態による、競合グラフを着色するための例示のオペレーションを示す図である。
【図７Ａ】少なくとも１つの例示の実施形態による、競合グラフを着色することを示す図である。
【図７Ｂ】少なくとも１つの例示の実施形態による、競合グラフを着色することを示す図である。
【図７Ｃ】少なくとも１つの例示の実施形態による、競合グラフを着色することを示す図である。
【図７Ｄ】少なくとも１つの例示の実施形態による、競合グラフを着色することを示す図である。
【発明を実施するための形態】
【００１８】
様々な例示の実施形態が、次に、いくつかの例示の実施形態が示される添付の図面を参照して、より十分に説明されるであろう。
【００１９】
詳細な実例となる実施形態が、本明細書において、開示される。しかしながら、本明細書において開示される特定の構造的詳細および機能的詳細は、例示の実施形態を説明する目的のための、単に、代表的なものにすぎない。しかしながら、本発明は、多数の代替的な形態で実施されることもあり、また本明細書において説明される実施形態だけに限定されるように解釈されるべきではない。
【００２０】
それに応じて、例示の実施形態は、様々な修正形態および代替形態とすることができるが、それらの実施形態は、図面において例として示され、また本明細書において詳細に説明されるであろう。しかしながら、開示される特定の形態だけに例示の実施形態を限定する意図は存在していないことを理解すべきである。それとは反対に、例示の実施形態は、本開示の範囲内に含まれるすべての修正形態と、同等形態と、代替形態とを対象として含むべきである。同様な番号は、図面の説明の全体を通して、同様な要素のことを意味している。
【００２１】
第１の、第２の、などの用語を本明細書において使用して、様々な要素を説明することができるが、これらの要素は、これらの用語によって限定されるべきではない。これらの用語を使用して、１つの要素を別の要素から区別するだけである。例えば、本開示の範囲を逸脱することなく、第１の要素は、第２の要素と命名される可能性があり、また同様に、第２の要素は、第１の要素と命名される可能性がある。本明細書において使用されるように、用語「および／または」は、１つまたは複数の関連するリストアップされた項目の任意の組合せ、およびすべての組合せを含んでいる。
【００２２】
ある要素が、別の要素に「接続され（ｃｏｎｎｅｃｔｅｄ）」ている、または「結合され（ｃｏｕｐｌｅｄ）」ていると称されるときに、その要素は、他の要素に直接に接続され、または結合される可能性もあり、あるいは介在する要素が存在していてもよい。対照的に、ある要素が、別の要素に「直接に（ｄｉｒｅｃｔｌｙ）接続され」ている、または「直接に結合され」ていると称されるときには、介在する要素は存在していない。要素の間の関係を説明するために使用される他の言葉も、同様なやり方（例えば、「間に（ｂｅｔｗｅｅｎ）」に対して「直接に間に（ｄｉｒｅｃｔｌｙ  ｂｅｔｗｅｅｎ）」、「隣接する（ａｄｊａｃｅｎｔ）」に対して「直接に隣接する（ｄｉｒｅｃｔｌｙ  ａｄｊａｃｅｎｔ）」など）で解釈されるべきである。
【００２３】
本明細書において使用される専門用語は、特定の実施形態を説明する目的のためだけであり、限定することを意図してはいない。本明細書において使用されるように、単数形の形式「１つの（ａ）」、「１つの（ａｎ）」、および「その（ｔｈｅ）」は、文脈が、明らかにそうでない場合を示していない限り、同様に複数形の形式を含むことを意図している。用語「備える／含む（ｃｏｍｐｒｉｓｅｓ）」、「備えている／含んでいる（ｃｏｍｐｒｉｓｉｎｇ）」、「含む（ｉｎｃｌｕｄｅｓ）」、および／または「含んでいる（ｉｎｃｌｕｄｉｎｇ）」は、本明細書において使用されるときに、述べられた特徴、整数、ステップ、オペレーション、要素、および／またはコンポーネントの存在を指定するが、１つまたは複数の他の特徴、整数、ステップ、オペレーション、要素、コンポーネント、および／またはそれらのグループの存在もしくは追加を除外するものではないことが、さらに理解されるであろう。
【００２４】
いくつかの代替的な実装形態においては、指摘される機能／動作は、図面の中で指摘される順序を外れて、起きることができることにも注意すべきでもある。例えば、連続して示される２つの図は、必要とされる機能／動作に依存して、実際には、実質的に同時に実行されることもあり、または時には、逆の順序で実行されることもある。
【００２５】
特定の詳細が、以下の説明において提供されて、例示の実施形態の完全な理解を提供している。しかしながら、例示の実施形態は、これらの特定の詳細なしに、実行され得ることが、当業者によって理解されるであろう。例えば、システムは、不必要な詳細の中で例示の実施形態をあいまいにしないようにするために、ブロック図の形で示されることもある。他の例においては、よく知られているプロセス、構造、および技法は、例示の実施形態をあいまいにすることを回避するために、不必要な詳細なしに示されることもある。
【００２６】
以下の説明においては、実例となる実施形態は、プログラム・モジュールまたは機能プロセスが、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含むように実施され得る、特定のタスクを実行し、または特定の抽象データ型を実施し、また既存のネットワーク要素（例えば、基地局、基地局制御装置、ノードＢ（ＮｏｄｅＢ）、ｅノードＢ（ｅＮｏｄｅＢ）など）における既存のハードウェアを使用して実施され得るオペレーションの動作およびシンボリック表現（例えば、フロー・チャート、流れ図、データ・フロー図、構造図、ブロック図などの形式で）を参照して、説明されるであろう。そのような既存のハードウェアは、１つまたは複数の中央演算処理装置（ＣＰＵ：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｏｒｓ）、デジタル信号プロセッサ（ＤＳＰ：ｄｉｇｉｔａｌ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｏｒｓ）、特定用途向け集積回路（ａｐｐｌｉｃａｔｉｏｎ−ｓｐｅｃｉｆｉｃ−ｉｎｔｅｇｒａｔｅｄ−ｃｉｒｃｕｉｔｓ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ：ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ｇａｔｅ  ａｒｒａｙｓ）コンピュータなどを含むことができる。
【００２７】
フロー・チャートは、逐次的プロセスとしてオペレーションを説明することができるが、オペレーションの多くは、並列に、同時に、または並行して実行されることもある。さらに、オペレーションの順序は、配列し直されることもある。プロセスは、そのオペレーションが完了されるときに終了されることもあるが、図面の中に含まれていない追加のステップを有することもできる。プロセスは、方法、関数、プロシージャ、サブルーチン、サブプログラムなどに対応することができる。プロセスが、ある関数に対応するときに、その終了は、呼び出し関数、またはメイン関数に対する、関数のリターンに対応することができる。
【００２８】
本明細書において開示されるように、用語「ストレージ媒体」または「コンピュータ読取り可能ストレージ媒体」は、リード・オンリー・メモリ（ＲＯＭ：ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、磁気ＲＡＭ、コア・メモリ、磁気ディスク・ストレージ媒体、光ストレージ媒体、フラッシュ・メモリ・デバイス、および／または情報を記憶するための他の有形マシン読取り可能媒体を含めて、データを記憶するための１つまたは複数のデバイスを表すことができる。用語「コンピュータ読取り可能媒体」は、それだけには限定されないが、ポータブル・ストレージ・デバイスもしくは固定ストレージ・デバイスと、光ストレージ・デバイスと、命令（単数または複数）および／またはデータを記憶し、含み、あるいは搬送することができる様々な他の媒体とを含むことができる。
【００２９】
さらに、例示の実施形態は、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、ハードウェア記述言語、またはそれらの任意の組合せによって実施されることもある。ソフトウェア、ファームウェア、ミドルウェア、またはマイクロコードの形で実施されるときに、必要なタスクを実行するプログラム・コードまたはコード・セグメントは、コンピュータ読取り可能ストレージ媒体など、マシン読取り可能媒体またはコンピュータ読取り可能媒体に記憶されることもある。ソフトウェアの形で実施されるときに、１つまたは複数の専用プロセッサが、必要なタスクを実行するであろう。
【００３０】
コード・セグメントは、プロシージャ、関数、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェア・パッケージ、クラス、または命令、データ構造もしくはプログラム・ステートメントの任意の組合せを表すことができる。コード・セグメントは、情報、データ、引き数、パラメータ、またはメモリ・コンテンツを渡すこと、および／または受信することにより、別のコード・セグメントまたはハードウェア回路に結合されることもある。情報、引き数、パラメータ、データなどは、メモリ共有化、メッセージ・パッシング、トークン・パッシング、ネットワーク送信などを含む任意の適切な手段を経由して、渡され、転送され、または送信されることもある。
【００３１】
図１は、少なくとも１つの例示の実施形態によるコンテンツ配信ネットワークを示すものである。
【００３２】
図１に示されるように、コンテンツ配信ネットワーク（ＣＤＮ）は、複数の宛先デバイス２００に接続されたネットワーク要素１５１を含むことができる。ネットワーク要素１５１は、データ・ファイル（例えば、映画ファイル）を配信するためのコンテンツ・ソース（例えば、マルチキャスト・ソース）とすることができる。宛先デバイス２００は、コンテンツ・ソースからデータを要求するエンド・ユーザ・デバイスとすることができる。例えば、各宛先デバイス２００は、ユーザが要求されたデータにアクセスすることができるようにするデバイスの一部分とすることができ、またはそのデバイスに関連づけられることもある。例えば、各宛先デバイス２００は、セット・トップ・ボックス、パーソナル・コンピュータ、タブレット、モバイル電話、あるいはオーディオまたはビデオをストリーミングするために使用される関連する任意の他のデバイスとすることができる。宛先デバイス２００のそれぞれは、ネットワーク要素１５１から受信されるデータを記憶するためのメモリを含むことができる。ネットワーク要素１５１と、宛先デバイス２００との構造およびオペレーションは、図２および３を参照して以下でより詳細に説明されるであろう。
【００３３】
図２は、例示の実施形態によるネットワーク要素の例示の構造を示す図である。少なくとも１つの例示の実施形態によれば、ネットワーク要素１５１は、通信ネットワーク（例えば、図１のコンテンツ配信ネットワーク（ＣＤＮ））における使用のために構成されていることもある。図２を参照すると、ネットワーク要素１５１は、例えば、データ・バス１５９と、トランスミッタ１５２と、レシーバ１５４と、メモリ１５６と、プロセッサ１５８とを含むことができる。簡潔にするために、別個の説明が、ここで含められていないが、各宛先デバイス２００は、ネットワーク要素１５１と同じ、または類似した構造を有することができることが、理解されるべきである。
【００３４】
トランスミッタ１５２と、レシーバ１５４と、メモリ１５６と、プロセッサ１５８とは、データ・バス１５９を使用して互いにデータを送信し、かつ／または互いからのデータを受信することができる。トランスミッタ１５２は、通信ネットワークにおける他のネットワーク要素に対する１つまたは複数のワイヤレス接続を経由して、例えば、データ信号と、制御信号と、信号強度／品質情報とを含むワイヤレス信号を送信するためのハードウェアと、任意の必要なソフトウェアとを含むデバイスである。
【００３５】
レシーバ１５４は、通信ネットワークにおける他のネットワーク要素に対する１つまたは複数のワイヤレス接続を経由して、例えば、データ信号と、制御信号と、信号強度／品質情報とを含むワイヤレス信号を受信するためのハードウェアと、任意の必要なソフトウェアとを含むデバイスである。
【００３６】
メモリ１５６は、磁気ストレージ、フラッシュ・ストレージなどを含む、データを記憶することができる任意のデバイスとすることができる。
【００３７】
プロセッサ１５８は、例えば、入力データに基づいて、特定のオペレーションを実行するように構成された、またはコンピュータ読取り可能コードに含まれる命令を実行することができる、専用プロセッサを含めて、データを処理することができる任意のデバイスとすることができる。例えば、以下で説明される修正形態と、方法とは、メモリ１５６の上に記憶され、またネットワーク要素１５１の内部のプロセッサ１５８によって実施されることもあることを理解すべきである。
【００３８】
さらに、以下の修正形態と、方法とは、ネットワーク要素１５１の１つまたは複数の上記で説明された要素によって実行され得ることを理解すべきである。例えば、レシーバ１５４は、「受信するステップ」と、「獲得するステップ」などとを実行することができ、トランスミッタ１５２は、「送信するステップ」と、「出力するステップ」と、「送るステップ」などとを実行することができ、プロセッサ１５８は、「決定するステップ」と、「生成するステップ」と、「相互に関連づけるステップ」と、「算出するステップ」などとを実行することができ、またメモリ１５６は、「記憶するステップ」と、「保存するステップ」などとを実行することができる。
【００３９】
図３Ａ〜３Ｂは、図２におけるネットワーク要素の例示のオペレーション示すフロー・チャートである。例えば、図３Ａ〜３Ｂは、通信ネットワークにおいて、キャッシングの方法を実行するための例示のオペレーションを示すものである。図４〜６は、キャッシング方法が、実行された後に、データ・ファイルを配信するための例示のオペレーションを示すものである。
【００４０】
図３Ａ〜３Ｂは、以下のアルゴリズム１に関連したキャッシング配信方法を実行するためのものであり、ここで、各データ・ファイル「ｆ」は、有限フィールドのシンボルとして表される「Ｂ」個の等しいサイズのパケットへと分割され、またライブラリ「Ｆ」に属することを理解すべきである。
【００４１】
【表１】
0006313458.tif 000002
【００４２】
アルゴリズム１において、
【数１】
0006313458.tif 000003
は、「ｕ」の宛先デバイス２００のキャッシング分布であり、ここで、ｕ＝１，・・・，ｎを用いた∀ｕに対して、
【数２】
0006313458.tif 000004
であり、また∀ｆ＝１，・・・，ｍ、ｕ＝１，・・・，ｎに対して０≦ｐｕ，ｆ≦１／Ｍｕであり、「ｍ」は、ネットワーク要素１５１によってホストされるファイルの数であり、また「Ｍｕ」は、宛先デバイス「ｕ」（すなわち、宛先デバイス２００）におけるキャッシュのストレージ容量であり、またＭｕ，ｆ＝ｐｕ，ｆＭｕＢは、ユーザｕにおいてキャッシュされるファイルｆのパケットを示している。ネットワーク要素１５１は、宛先デバイス「ｕ」のデバイス２００が、ファイル「ｆ」のＭｕ．ｆ＝ｐｕ，ｆＭｕＢ個のパケットをキャッシュするように、アルゴリズム１を実行する。さらに、アルゴリズム１のランダム化された性質は、２つの宛先が、与えられたファイル「ｆ」について同じ数のパケットをキャッシュする場合、そのときには、２つの宛先デバイス２００のうちのそれぞれが、同じファイル「ｆ」の異なるパケットをキャッシュするように、ネットワーク要素１５１が、オペレーションを実行することを可能にする。アルゴリズム１は、以下で図３Ａ〜３Ｂにおいて説明されるオペレーションに従って、ネットワーク要素１５１によって実施されることもある。
【００４３】
図３Ａを参照すると、オペレーション３００において、ネットワーク要素１５１は、複数のデータ・ファイルについての人気を決定することができる。データ・ファイルは、例えば、ビデオ・ファイルおよび／またはオーディオ・ファイルとすることができる。ネットワーク要素１５１は、宛先デバイス２００のうちの少なくとも１つからの複数のデータ・ファイルについての要求（例えば、ユーザ要求）に基づいて、人気を決定することができる。ユーザ要求は、データ・ファイルについての需要分布を形成することができる。ネットワーク要素１５１は、すべての宛先デバイス２００の需要分布に従って人気を決定することができる。この場合には、需要分布は、Ｚｉｐｆ分布に従うことができる。代わりに、ネットワーク要素１５１は、宛先デバイス当たりに基づいて、人気を決定することができ、ここでは、各宛先デバイス２００は、関連する需要分布を有している。
【００４４】
ネットワーク要素１５１は、宛先デバイス２００からのデータ・ファイルについての要求の数に基づいて人気を決定することができる。例えば、ネットワーク要素１５１は、宛先デバイス２００によって１００回要求されるデータ・ファイルを５０回要求されるデータ・ファイルよりもより高い人気を有するものとして決定する。したがって、人気は、どのデータ・ファイルが、宛先デバイス２００のユーザによって最も頻繁に要求され、また閲覧されるかに基づいたものとすることができる。
【００４５】
ネットワーク要素１５１は、各データ・ファイルを複数のパケットへと分割することができる。例えば、ネットワーク要素１５１は、各データ・ファイルを同じ数のパケット（例えば、３つのパケット）へと分割することができる。それに応じて、オペレーション３１０においては、ネットワーク要素１５１は、オペレーション３００の中で決定される人気に基づいて、少なくとも１つの宛先デバイスに対して複数のデータ・ファイルのランダム・パケットを送信することができる。例えば、ネットワーク要素１５１は、ランダム・パケットが、各宛先デバイス２００に記憶される（またはキャッシュされる）ように各データ・ファイルのランダム・パケットを宛先デバイス２００に対して送信することができる。
【００４６】
ネットワーク要素１５１は、各宛先デバイス２００が、決定された人気と、入力パラメータ（例えば、宛先デバイスの数、人気分布、各宛先デバイスのキャッシュ・サイズ、ネットワーク要素１５１におけるデータ・ファイル・ライブラリのサイズなど）とに基づいて、データ・ファイルのうちの少なくとも１つについての与えられた数のランダム・パケットを受信するように、ランダム・パケットを送信することができる。例えば、宛先デバイス２００が、同じサイズのキャッシュと、同じ需要分布とを有する（例えば、宛先デバイスが、一様である）場合に、ネットワーク要素１５１は、各宛先デバイス２００に対して同じ数のパケットを送信することができる。一例においては、１０個のパケットへと分割される２つの宛先デバイス１および２と、２つのファイルＡおよびＢとが、存在していることを仮定する。（ｉ）宛先デバイス１および２が、同じ頻度でファイルＡおよびファイルＢを要求し、またファイルＡが、ファイルＢよりも多い頻度で両方の宛先によって要求され、また（ｉｉ）２つの宛先デバイス１および２が、同じキャッシュ・サイズを、例えば、パケットの観点から６つのユニットを有する場合、そのときには、ネットワーク要素１５１は、両方の宛先デバイス１および２が、ファイルＡのうちの４つのパケットと、ファイルＢのうちの２つのパケットをキャッシュするように、キャッシングの方法を実行するであろう。
【００４７】
ネットワーク要素１５１が、オペレーション３００において、宛先デバイス当たりに基づいて、人気を決定した場合、そのときには、ネットワーク要素１５１は、オペレーション３１０において、宛先デバイス当たりに基づいて、ランダム・パケットを送信することができる。例えば、宛先デバイス２００が、異なるサイズのキャッシュまたは異なる需要分布を有する場合、ネットワーク要素１５１は、各宛先に対して異なる数のパケットを送信することができる。この場合には、上記の例を参照すると、宛先デバイス１は、ファイルＡのうちの７つのパケットと、ファイルＢのうちの３つのパケットとを受信することができるが、宛先デバイス２は、ファイルＡのうちの２つのパケットと、ファイルＢのうちの５つのパケットとを受信することができる。これは、宛先デバイス１が、ファイルＡをファイルＢよりもずっと多く要求し、またパケットの観点で１０個のユニットの総キャッシュ・サイズを有しているが、宛先２デバイスは、ファイルＢよりもずっと少なくファイルＡを要求し、またパケットの観点で７つのユニットの総キャッシュ・サイズを有していることに起因する可能性がある。
【００４８】
図３Ｂは、必要に応じて、オペレーション３００と、３１０との間で実行され得るネットワーク要素１５１の例示のオペレーションを示すものである。例えば、図３Ａにおけるオペレーション３００に従って、ネットワーク要素１５１は、決定された人気に基づいて、データ・ファイルをランク付けすることができる。例えば、オペレーション３０１において、ネットワーク要素１５１は、オペレーション３００において決定される人気を使用して、最も人気のあるデータ・ファイルから最も人気のないデータ・ファイルへとデータ・ファイルをランク付けすることができる。
【００４９】
オペレーション３０２において、ネットワーク要素１５１は、各データ・ファイルについて、ランキングに基づいて、いくつかのランダム・パケットを選択することができる。例えば、ネットワーク要素１５１は、各データ・ファイルのそれぞれのランクと、ネットワークの入力パラメータ（例えば、宛先デバイスの数、人気分布、各宛先デバイスのキャッシュ・サイズ、ネットワーク要素１５１におけるデータ・ファイル・ライブラリのサイズなど）とのうちの少なくとも１つに従って、各宛先２００について、またデータ・ファイルのそれぞれについて異なる数のランダム・パケットを選択する。オペレーション３０２の後に、ネットワーク要素１５１は、図３Ａにおけるオペレーション３１０へと戻って進んで、各データ・ファイルについての選択された数のランダム・パケットを送信することができる。
【００５０】
オペレーション３０２は、ネットワーク要素１５１が、少なくとも１つのしきい値の値に基づいて、ランク付けされたデータ・ファイルを少なくとも第１の部分集合と、第２の部分集合とに分割することを含むことができることを理解すべきである。少なくとも１つのしきい値の値は、経験的証拠に基づいており、かつ／またはユーザ定義されたものとすることができる。第１の部分集合は、第２の部分集合よりも高くランク付けされたデータ・ファイルを含むことができる。このようにして、オペレーション３１０においては、ネットワーク要素１５１は、第１の部分集合の中のデータ・ファイルだけについて、選択された数のランダム・パケットを送信することができる。これは、宛先デバイス２００におけるパケットのより効率的なキャッシングを可能にし、また従来のマルチキャスティング技法に比べて、配信中に送信の数を低減させることができる。
【００５１】
図３Ａおよび３Ｂを参照して説明されるオペレーションは、より人気のあるファイルのより多くのパケットをキャッシュし、宛先デバイス２００によってまとめてキャッシュされる各ファイルの異なるパケットの量を増大させ（または代わりに、最大にし）、また従来のマルチキャスティング技法に比べて、配信中に送信の数を低減させるスキームの能力のために、ネットワークの改善された実行を可能にすることを理解すべきである。
【００５２】
上記で説明されたキャッシング方法に関連して、本出願は、データ・ファイルの要求されたパケットが、宛先デバイス２００に対して配信される配信フェーズのための例示の方法を開示している。配信フェーズのための例示の方法は、グラフ理論に基づいている。
【００５３】
図４は、少なくとも１つの例示の実施形態による配信フェーズのための例示のオペレーションを示すものである。図４を参照すると、オペレーション４００において、ネットワーク要素１５１は、データ・ファイルのパケットについての、宛先デバイス２００（またはユーザ・デバイス）からの要求を受信する。ネットワーク要素１５１は、上記で説明されるキャッシング方法を既に実行しているので、各宛先デバイス２００は、キャッシング方法の結果として、キャッシュされ（または記憶され）なかったこれらのパケットだけを要求する。したがって、配信フェーズは、各宛先デバイス２００に対して、要求されたファイルのうちの欠けている部分（単数または複数）を、すなわち、その宛先デバイス２００のメモリから失われているパケットを提供することを含んでいる。
【００５４】
オペレーション４１０において、ネットワーク要素１５１は、各宛先デバイス２００によって要求される各パケットが、競合グラフの複数の頂点の中の異なる頂点によって表されるように、複数の頂点を用いて競合グラフを構築する。それゆえに、たとえ同じパケットが、Ｋ人の異なるユーザによって要求されるとしても、パケットは、競合グラフの中のＫ個の異なる頂点として表される。言い換えれば、競合グラフの中の各頂点は、宛先デバイス２００と、要求されたパケットとの固有の対に関連づけられる。したがって、競合グラフの各頂点は、宛先デバイス２００に関連づけられ、またその宛先デバイス２００によって要求されるパケットを表す。さらに、ネットワーク要素１５１は、複数の頂点のうちのどれが、同じ要求されたパケットを表すかと、どの要求されたパケットが、宛先デバイス２００に属するキャッシュに記憶されるかと、に基づいて、競合グラフを構築することができる。オペレーション４１０は、図５および６を参照して、以下でさらに詳細に説明される。
【００５５】
依然として図４を参照すると、オペレーション４２０において、ネットワーク要素１５１は、複数の頂点をグループに割り当てることができる。各グループは、複数の頂点に対するリンクの数を示すことができる。例えば、各頂点は、周囲を取り巻く頂点に対する与えられた数のリンクを有することができる。一例においては、頂点Ａと、頂点Ｂとが、それぞれ、他の頂点に対して３つのリンクを有しており、また頂点Ｃと、頂点Ｄとが、それぞれ、他の頂点に対して４つのリンクを有している場合、そのときには頂点ＡおよびＢは、１つのグループ（例えば、グループ３）に属しており、また頂点ＣおよびＤは、異なるグループ（例えば、グループ４）に属している。
【００５６】
オペレーション４４５において、ネットワーク要素１５１は、競合グラフの上の要求されたパケットをラベル付けするやり方として、複数の頂点に着色する。例えば、ネットワーク要素１５１は、オペレーション４３０において割り当てられたグループに基づいて、複数の頂点に着色する。オペレーション４５５が、図６に関して、以下でさらに詳細に考察される。
【００５７】
オペレーション４８０において、ネットワーク要素１５１は、同じカラーを有する頂点によって表される要求されたパケットを結合する。例えば、ネットワーク要素１５１は、同じカラーを有する頂点によって表されるパケットに対して排他的論理和（ＸＯＲ：ｅｘｃｌｕｓｉｖｅ−ＯＲ）オペレーション（または有限フィールドの上の他の線形結合オペレーション）を実行する。
【００５８】
オペレーション４９０において、ネットワーク要素１５１は、結合されたパケットを送信する。例えば、ネットワーク要素１５１は、マルチキャスト送信を経由して、結合されたパケットを宛先デバイス２００に対して送信する。送信に先立ってパケットを結合することにより、少なくとも１つの例示の実施形態による配信方法が、ネットワーク要素１５１の送信の数を低減させることができ、これは、消費電力を低減させ、またネットワーク効率を改善させることができることを理解すべきである。宛先デバイス２００は、ＸＯＲオペレーション（または有限フィールドの上の他の線形結合オペレーション）を使用して、送信された結合されたパケットを受信し、また復号することができることを理解すべきである。例えば、宛先デバイス２００は、キーとしてキャッシュに記憶されるパケットを使用して、結合されたパケットを復号することができる。
【００５９】
図５は、少なくとも１つの例示の実施形態による競合グラフを構築するための例示のオペレーションを示すものである。例えば、図５は、図４からのオペレーション４１０をさらに詳細に考察している。図５は、方向づけのない競合グラフを構築するための例示のオペレーションを示すものである。方向づけのない競合グラフは、本出願において、グリーディ・ランダム・アルゴリズム・サーチ・プロシージャ（ＧＲＡＳＰ：ｇｒｅｅｄｙ  ｒａｎｄｏｍ  ａｌｇｏｒｉｔｈｍ  ｓｅａｒｃｈ  ｐｒｏｃｅｄｕｒｅ）着色スキームと称される、着色スキームと一緒に使用されることもある。この着色スキームは、図６を参照して、以下でより詳細に説明される。
【００６０】
図５を参照すると、オペレーション５１１において、ネットワーク要素１５１は、オペレーション４１０において追加される複数の頂点からの頂点「Ｖｉ」と、「Ｖｊ」とを分析する。オペレーション５１３において、ネットワーク要素が、頂点ＶｉとＶｊとが同じ要求されたパケットを表すことを決定する場合、そのときにはネットワーク要素１５１は、オペレーション５１５において、２つの頂点の間のリンク（またはエッジ）を作り出さない。次いで、ネットワーク要素１５１は、オペレーション５３１へと進んで、競合グラフの中の頂点のすべてが、分析されているかどうかを決定する。
【００６１】
オペレーション５１３において、ネットワーク要素１５１は、頂点ＶｉとＶｊとが、同じ要求されたパケットを表さないことを決定する場合、そのときにはネットワーク要素１５１は、オペレーション５１７へと進み、頂点Ｖｉによって表されるパケットを要求している、頂点Ｖｉに関連する宛先デバイス２００のキャッシュ（またはメモリ）をチェックする。オペレーション５１９において、ネットワーク要素１５１が、頂点Ｖｊを表すパケットが、頂点Ｖｉによって表されるパケットを要求している、頂点Ｖｉに関連する宛先デバイス２００のキャッシュの中で使用可能ではないことを決定する場合、そのときにはネットワーク要素１５１は、オペレーション５２１において頂点Ｖｉと、頂点Ｖｊとの間にリンクを作り出す。次いで、ネットワーク要素１５１は、オペレーション５３１へと進んで、競合グラフの中の頂点のすべてが、分析されているかどうかを決定する。
【００６２】
オペレーション５１９において、ネットワーク要素１５１が、頂点Ｖｊを表すパケットが、頂点Ｖｉによって表されるパケットを要求している、頂点Ｖｉに関連する宛先デバイス２００のキャッシュにおいて使用可能であることを決定する場合、そのときにはネットワーク要素１５１は、オペレーション５２３において、頂点Ｖｊによって表されるパケットを要求している、頂点Ｖｊに関連する宛先デバイス２００のキャッシュをチェックする。オペレーション５２５において、頂点Ｖｉを表すパケットが、頂点Ｖｊによって表されるパケットを要求している、頂点Ｖｊに関連する宛先デバイス２００のキャッシュにおいて使用可能ではない場合、そのときにはネットワーク要素１５１は、競合グラフの中の頂点のすべてが分析されているかどうかを決定するオペレーション４３１へと進む前に、オペレーション５２７において頂点Ｖｉと、Ｖｊとの間にリンクを作り出す。
【００６３】
オペレーション５２５において、ネットワーク要素１５１が、頂点Ｖｉを表すパケットが、頂点Ｖｊによって表されるパケットを要求している、頂点Ｖｊに関連する宛先デバイス２００のキャッシュにおいて使用可能である場合、そのときにはネットワーク要素１５１は、オペレーション５２９において、頂点Ｖｉと、Ｖｊとの間のリンクを作り出す。次いで、ネットワーク要素１５１は、オペレーション５３１へと進んで、競合グラフの中の頂点のすべてが、分析されているかどうかを決定する。
【００６４】
ひとたびネットワーク要素１５１が、競合グラフの中の頂点のすべてを分析した後に、次いで、ネットワーク要素１５１は、オペレーション５３３において、構築された競合グラフを戻す。
【００６５】
図５を考慮すると、（ｉ）第１の頂点と、第２の頂点とが、同じパケットを表さず、また（ｉｉ）第１の頂点によって表されるパケットが、第２の頂点に関連するユーザ・デバイスのキャッシュに記憶されず、または第２の頂点によって表されるパケットが、第１の頂点に関連するユーザ・デバイスのキャッシュに記憶されない場合に、図４における構築するオペレーション４１０は、複数の頂点のうちの第１の頂点と、第２の頂点との間にリンクを作り出すオペレーションによって要約されることもあることを理解すべきである。
【００６６】
図６は、少なくとも１つの例による、競合グラフを着色するための実施形態のオペレーションを示すものである。本出願においては、着色スキームは、グリーディ・ランダム化アルゴリズム・サーチ・プロシージャ（ＧＲＡＳＰ：ｇｒｅｅｄｙ  ｒａｎｄｏｍｉｚｅｄ  ａｌｇｏｒｉｔｈｍ  ｓｅａｒｃｈ  ｐｒｏｃｅｄｕｒｅ）着色スキームと称されることもある。図６の中のオペレーションは、以下のアルゴリズムに対応することができる。一般的なＧＲＡＳＰ着色スキーム・アルゴリズムは、以下、すなわち、
【００６７】
【表２】
0006313458.tif 000005
である。
【００６８】
関数「ＢｕｉｌｄＧｒｅｅｄｙＲａｎｄＡｄａｐｔｉｖｅ」は、
【００６９】
【表３】
0006313458.tif 000006
として規定される。
【００７０】
関数「ＭａｋｅＲＣＬ」は、
【００７１】
【表４】
0006313458.tif 000007
として規定される。
【００７２】
関数「ＧｅｔＣｏｌｏｒ」は、
【００７３】
【表５】
0006313458.tif 000008
として規定される。
【００７４】
関数「ｌｏｃａｌＳｅａｒｃｈ」は、
【００７５】
【表６】
0006313458.tif 000009
として規定される。
【００７６】
上記の擬似コードにおいては、ＨＭ，Ｗ＝（Ｖ，Ｅ）は、（方向づけのない）競合グラフを表しており、ここで、ＶおよびＥは、図５を参照して上記で考察されるように構築される方向づけのない競合グラフＨＭ，Ｗのそれぞれ頂点と、エッジ（またはリンク）との集合を示している。ＨＭ，Ｗにおいては、各頂点ｉ∈Ｖについて、Ａｄｊ（ｉ）＝｛ｊ∈Ｖ｜［ｉ，ｊ］∈Ｅ｝である。ｃｂｅｓｔ＝アルゴリズムによって見出される最良の関連づけのカラー−頂点を示している。すべてのｉ∈Ｖについて、ｄ（ｉ）＝｜Ａｄｊ（ｉ）｜は、頂点ｉの次数（または頂点ｉに対するリンクの数）であるものとする。ｃｂｅｓｔ＝φは、構築の下での解、すなわち、カラーに既に割り当てられた頂点の集合（最初には空集合）であるものとし、またＣ＝φ（最初には空集合）は、ｃｂｅｓｔの中の少なくとも頂点に関連づけられているカラーの集合であるものとする。各反復において、以下のオペレーションが実行される。すなわち、
１．すべてのｉ∈Ｖについて、ｄ（ｉ）＝｜Ａｄｊ（ｉ）｜は、頂点ｉの次数（または頂点ｉに対するリンクの数）であるものとする。ｃｂｅｓｔ＝φは、構築の下での解（最初には空集合）、すなわち、カラーに既に割り当てられた頂点の集合であるものとし、またＣ＝φ（最初には空集合）は、ｃｂｅｓｔの中の少なくとも頂点に関連づけられているカラーの集合であるものとする。
２．［０，１］の中でランダムに一様にパラメータβを選択する。
３．以下を計算し（関数ＭａｋｅＲＣＬを参照）、すなわち、
ｇｍｉｎ、最小グリーディ値は、すなわち、
【数３】
0006313458.tif 000010
であり、
ｇｍａｘ、最大グリーディ値は、すなわち、
【数４】
0006313458.tif 000011
であり、
しきい値ｔａｕ（τ）は、すなわち、
τ＝ｇｍｉｎ＋［β・（ｇｍａｘ−ｇｍｉｎ）］であり、式中で、β∈［０，１］であり、また
その次数が少なくともτであり、候補の着色されていない頂点の部分集合としてのＲＣＬは、すなわち、
ＲＣＬ＝｛ｉ∈Ｖ＼ｃ｜ｄ（ｉ）≧τ｝である。
４．すべての頂点が、着色されるまで以下のオペレーションを実行する。すなわち、
ａ．頂点ｉが、ＲＣＬからランダムに選択される（（関数ＢｕｌｄＧｒｅｅｄｙＲａｎｄＡｄａｐｔｉｖｅのライン４を、すなわち、ｉ＝ＳｅｌｅｃｔＩｎｄｅｘ（ＲＣＬ）を参照）。β∈［０．１］の値は、各反復において、ＲＣＬの中に挿入されるべき頂点の選択において、グリーディ性（ｇｒｅｅｄｉｎｅｓｓ）対ランダム性のパーセンテージを決定することに注意すべきである。例えば、β＝１では、選択は、全体的にグリーディであり、また次数ｇｍａｘを有する頂点だけが、ＲＣＬへと挿入される。別の例として、β＝０では、選択は、全体的にランダムであり、またすべての候補の頂点が、ＲＣＬへと挿入される（すなわち、ＲＣＬ＝Ｗである）。
ｂ．頂点ｉが選択され、またその隣接する頂点を分析し（関数ＧｅｔＣｏｌｏｒを参照）、４つの可能性のあるシナリオが、起こる可能性がある。すなわち、
Ｉ．すべての隣接する頂点は、依然として着色されておらず、また集合Ｃ＝φであり、すなわち、この場合に、新しいカラーｃが、頂点ｉに割り当てられ、またＣ＝Ｃ∪｛Ｃ｝（図７Ａ）であり、
ＩＩ．すべての隣接する頂点は、依然として着色されておらず、また集合Ｃ≠φであり、すなわち、この場合に、頂点ｉは、使用可能な第１のカラーｃ∈Ｃを用いて着色され（図７Ｂ）、
ＩＩＩ．少なくとも１つの隣接する頂点は、カラーｃ∈Ｃを用いて着色され、またすべての現在使用されるカラーｃ∈Ｃは、既に少なくとも隣接する頂点に割り当てられており、すなわち、この場合に、頂点ｉは、新しいカラーｃ’を用いて着色され、またＣ＝Ｃ∪｛ｃ’｝であり（図７Ｃ）、また
ＩＶ．少なくとも１つの隣接する頂点は、カラーｃ∈Ｃを用いて着色され、またどのような隣接する頂点にも割り当てられていないカラーｃ’∈Ｃが、存在しており、すなわち、この場合に、頂点ｉは、カラーｃ’を用いて着色される（図７Ｄ）。
ｃ．頂点ｉは、構築の下で解に挿入される（シナリオ（Ｉ）から（ＩＶ）と、コヒーレントにアップデートされる目的関数値（すなわち、ｆ（ｃ）＝｜Ｃ｜）とに従って、ｃ［ｉ］＝ｃ’またはｃ［ｉ］＝ｃである）。
５．ひとたび競合グラフのすべての頂点が、着色された後に、次いで、関数ＢｕｌｄＧｒｅｅｄｙＲａｎｄＡｄａｐｔｉｖｅは、解ｃｂｅｓｔを戻す。
６．入力ｃｂｅｓｔとして取得し、また新しい有効なカラーｃ＊を戻すローカル・サーチが、実施される（関数ＬｏｃａｌＳｅａｒｃｈを参照）。反復して、各カラーｃ∈Ｃについて、カラーｃを用いて着色されるすべての頂点の集合Ｇｃを計算し（関数ｌｏｃａｌＳｅａｒｃｈのライン２）、また以下のステップを実行する。
ａ．各頂点ｉ∈Ｇｃについて、頂点Ａｄｊ（ｉ）、すなわち、頂点ｉに隣接した頂点をサーチする。任意の隣接する頂点ｊ∈Ａｄｊ（ｉ）に割り当てられないカラーｃ’∈Ｃ、ｃ’≠ｃが、存在する場合、そのときには頂点ｉは、カラーｃ’を用いて着色されるようになり、
ｂ．何らかのカラーｃ’、ｃ’≠ｃで、各頂点ｉ∈Ｇｃに関連するｃを置換することが、可能であり、また可能であった場合だけに、カラーｃが、集合Ｃから取り除かれる。
７．ｃ＊の中で使用されるカラーの数が、ｃｂｅｓｔの中で使用されるカラーの数よりも小さい場合、そのときにはｃｂｅｓｔをｃ＊に等しく設定し、そうでない場合には、部分解としてｃｂｅｓｔを保持する。（ＧＲＡＳＰアルゴリズムのライン８〜１２を参照）。
８．ｋ＝ＭａｘＩｔｅｒａｔｉｏｎｓまですべての上記のオペレーション１から７を反復し、また解としてｃｂｅｓｔを戻す。
【００７７】
上記説明から、停止判断基準（例えば、反復の最大回数、または望ましい実行時間）が、満たされるまで、ＧＲＡＳＰ着色スキームが、望ましい回数の反復を実行することが、理解されるべきである。各反復においては、グリーディ・ランダム化された適応解ｃが、初期解としてｃから開始して構築され、またローカル・サーチ・フェーズが、実行されて、ローカルに最適な解ｃ＊を戻す。反復の終わりに、最良のローカルに最適な解ｃｂｅｓｔ（すなわち、最良関数目的値ｆ（ｃｂｅｓｔ）に対応する解）は、最終解として戻され、またアルゴリズムは、停止する。
【００７８】
ＧＲＡＳＰ着色スキームは、任意のグラフ・トポロジと、密度／希薄さと、任意のサイズとによって特徴づけられる問題インスタンスに立ち向かうことができる。ローカル・サーチ戦略は、一度に１つずつ、各頂点に焦点を当てることにより、冗長なカラーをチェックする。
【００７９】
上記のアルゴリズムは、次に、図６を参照して、説明されるであろう。オペレーション６００において、ネットワーク要素１５１は、初期状態を設定する。例えば、ネットワーク要素１５１は、ＧＲＡＳＰ着色スキームのために実行されることになる反復の数「ｍａｘｉｔｅｒ」を設定する。反復の回数「ｍａｘｉｔｅｒ」は、ユーザ定義されており、かつ／または経験的証拠に基づいたものとすることができる。以下のオペレーションにおいて、「Ｖ」は、競合グラフの頂点の集合であり、「Ｖ＿１」は、着色された頂点の集合であり、また「Ｖ＿２」は、着色されていない頂点の集合である。第１の反復において、Ｖ＿１は、空集合であり、またＶ＿２＝Ｖである。
【００８０】
オペレーション６０５において、ネットワーク要素１５１は、Ｖの中の頂点のうちのどれが、「ｇｍｉｎ」として、割り当てられたグループに基づいて、最小の数のリンク（またはエッジ）を有しているかを決定する。例えば、グループ２の頂点が、２つのリンクを有しており、グループ３の頂点が、３つのリンクを有しているなどの場合のグループ２から６が、存在している場合、そのときには２つのリンクは、全体の競合グラフについての頂点に対する最小の数のリンクであり、またｇｍｉｎは、「２」として設定される。オペレーション６１０において、ネットワーク要素１５１は、Ｖの中の頂点のうちのどれが、「ｇｍａｘ」として、割り当てられたグループに基づいて最大数のリンク（またはエッジ）を有するかを決定する。上記の例においては、最大のグループ番号は、グループ６であるので、「ｇｍａｘ」は、「６」に設定されることもあり、競合グラフの中の頂点のうちの任意の１つに対する最大数のリンクは、６つのリンクであることを意味している。オペレーション６１５において、ネットワーク要素１５１は、「ｇｍｉｎ」と「ｇｍａｘ」とに基づいて、しきい値ｔａｕを算出する。例えば、ネットワーク要素１５１は、ｔａｕ＝ｇｍｉｎ＋β（ｇｍａｘ−ｇｍｉｎ）であるように、しきい値を算出することができ、式中で、βは、ユーザ定義されており、かつ／または経験的証拠に基づいている定数である（例えば、βは、［０，１］の内部でランダムに一様に選択されることもある）。
【００８１】
オペレーション６２０において、ネットワーク要素１５１は、しきい値ｔａｕ以上のリンクの数を有するグループに属する着色されていない頂点の部分集合（または制限された候補リスト「ＲＣＬ：ｒｅｓｔｒｉｃｔｅｄ  ｃａｎｄｉｄａｔｅｓ  ｌｉｓｔ」）を構築することができる。βの値は、部分集合に含まれる頂点の選択において、「グリーディ性」の量に対する「ランダム性」の量に依存することを理解すべきである。例えば、β＝１では、最大数のリンクを有するこれらの頂点だけが、部分集合に含まれることになるので、選択は、完全にグリーディである。例えば、β＝０である場合、そのときにはすべての頂点が、その部分集合に含まれることになる。
【００８２】
オペレーション６２５において、ネットワーク要素１５１は、オペレーション６２０において作り出される部分集合から頂点「Ｖｉ」を選択する（例えば、ランダムに選択する）。オペレーション６３０において、ネットワーク要素１５１は、カラーの第１の集合として頂点Ｖｉに隣接している（またはリンクされる）頂点のカラーを識別する。オペレーション６３０の一部分として、ネットワーク要素１５１はまた、カラーの第２の集合として競合グラフの既存のカラーを識別することもできる。オペレーション６３５において、ネットワーク要素１５１は、競合グラフの既存のカラーが、頂点Ｖｉに割り当てられ得るかどうかを決定する。例えば、オペレーション６４０において、ネットワーク要素１５１は、カラーの第１の集合と、カラーの第２の集合とが、一致しない場合に、第２の集合からの望ましいカラーを用いて頂点Ｖｉに着色する。そうでなければ、オペレーション６４５において、カラーの第１の集合と、カラーの第２の集合とが、一致する場合、そのときにはネットワーク要素１５１は、新しいカラーを選択し、またオペレーション６５０において、新しいカラーを頂点Ｖｉに割り当て、また競合グラフに着色するために存在しているカラーの集合の中の新しいカラーを含んでいる。オペレーション６３５は、図７Ａ〜７Ｃを参照して、以下でより詳細に考察される。
【００８３】
オペレーション６５５において、ネットワーク要素１５１は、頂点のすべてが着色されているかどうかを決定する。着色されていない場合、そのときにはネットワーク要素１５１は、オペレーション６０５へと戻る。着色されている場合、そのときにはネットワーク要素１５１は、オペレーション６６０においてローカル・サーチ（例えば、上記のｌｏｃａｌＳｅａｒｃｈアルゴリズム）を実行して、競合グラフのために使用されるカラーの数を減少させる（すなわち、集合Ｖ＿１からのカラーの数を減少させる）。例えば、ネットワーク要素１５１は、競合グラフの既存のカラーからあるカラーを選択し、選択されたカラーを有する頂点を識別し、また識別された頂点にリンクされる頂点が、異なるカラーを用いて着色されない場合に、既存のカラーから選択される異なるカラーで、選択されたカラーを置換することができる。このようにして、選択されたカラーは、既存のカラーの集合から取り除かれる。
【００８４】
オペレーション６６５において、ネットワーク要素は、ローカル・サーチによって生成される解から最良の解（すなわち、競合グラフのために使用されるカラーの最小の数をもたらす解）を選択することができる。オペレーション６７０において、ネットワーク要素１５１は、現在の反復「ｉｔｅｒ」が、オペレーション６００の中に設定された反復「ｍａｘｉｔｅｒ」の数よりも少ないかどうかを決定する。少ない場合、そのときにはネットワーク要素１５１は、オペレーション６００へと戻り、また反復「ｉｔｅｒ」の数を１だけ増分する（すなわち、ｉｔｅｒ＝ｉｔｅｒ＋１に設定する）。オペレーション６７０の一部分として、ネットワーク要素１５１は、ローカル・サーチの結果をメモリに記憶することができる（ここで、結果は、着色された競合グラフである）。ネットワーク要素１５１が、反復「ｉｔｅｒ」の現在の数が「ｍａｘｉｔｅｒ」に等しいことを決定する場合、そのときにはネットワーク要素１５１は、オペレーション６８０へと進み、また各反復によって見出される記憶された解のうちから最良の解を戻す。例えば、ネットワーク要素１５１は、最小の数のカラーを使用する競合グラフを戻す。
【００８５】
図７Ａ〜７Ｄは、少なくとも１つの例示の実施形態による着色された競合グラフを示すものである。例えば、図７Ａ〜７Ｄは、図６におけるオペレーション６２５〜６５０に関連した一例を示すものである。図７Ａ〜７Ｄにおいて、オペレーション６２５において選択される頂点Ｖｉは、頂点「ｉ」によって表され、また頂点「ｊ」と、頂点「ｋ」と、頂点「ｘ」と、頂点「ｙ」とは、頂点「ｉ」に隣接しており（またはリンクされている）ものとしてオペレーション６３０において、識別される（すなわち、Ａｄｊ（ｉ）＝｛ｊ，ｋ，ｘ，ｙ｝である）。
【００８６】
図７Ａは、すべての隣接する頂点ｊ、ｋ、ｘ、およびｙが、着色されていない場合のシナリオを表すものである。グラフの中の既存のカラーの集合（すなわち、図６の中のＶ＿１）は、空集合である。この場合には、ネットワーク要素１５１は、オペレーション６４５において、新しいカラー「ｃ」（すなわち、黄色）を選択し、また頂点ｉにカラー黄色を割り当てる。既存のカラーの集合Ｖ＿１は、カラー黄色を含むようにアップデートされる。図７Ｂは、既存のカラーの集合Ｖ＿１が、既にカラー黄色（およびさらに青色）を含んでいる別のシナリオを示すものである。ここで、頂点ｊ、ｋ、ｘ、およびｙのうちのどれも、黄色で着色されていないので、ネットワーク要素１５１は、頂点ｉに黄色を（または他の頂点が、依然として着色されていないので青色でさえも）割り当てることにより、オペレーション６４０を実行する。
【００８７】
図７Ｃは、既存のカラーの集合Ｖ＿１が、頂点ｉにリンクされる頂点に既に割り当てられているカラーを含んでいる場合のシナリオを示すものである。この場合には、ネットワーク要素１５１は、オペレーション６４５および６５０を実行して、新しいカラー「ｃ」（すなわち、黄色）を選択し、またカラー黄色を含むように既存のカラーの集合Ｖ＿１をアップデートする。
【００８８】
図７Ｄは、頂点「ｉ」にリンクされる頂点のうちのどれも、カラー青色を有していないので、またカラー青色は、既に、カラーの既存の集合Ｖ＿１の中にあるので、ネットワーク要素１５１が、頂点「ｉ」にカラー青色を割り当てる場合のシナリオを示すものである。
【００８９】
例示の実施形態が、宛先デバイス２００においてより人気のあるファイルのより多くのパケットをキャッシュし、宛先デバイス２００によってまとめてキャッシュされる各ファイルの異なるパケットの量を増大させ（または代わりに、最大にし）、またデータ・ファイルの要求されたパケットの完全な集合の内部の符号化されたマルチキャスト送信を可能にする能力を可能にするので、上記で説明されるオペレーションは、ネットワークの改善された実行を可能にすることを理解すべきである。さらに、送信に先立って要求されたパケットを結合することにより、少なくとも１つの例示の実施形態による配信の方法および／またはデバイスは、ネットワーク要素１５１の送信の数を低減させることができ、これは、消費電力を低減させ、またネットワーク効率を改善することができることを理解すべきである。
【００９０】
例示の実施形態の変形形態は、例示の実施形態の精神および範囲からの逸脱として見なされるべきではない。当業者には明らかになるような、すべてのそのような変形形態は、本開示の範囲内に含まれることを意図している。
【図１】
0006313458.tif 000012
【図２】
0006313458.tif 000013
【図３Ａ】
0006313458.tif 000014
【図３Ｂ】
0006313458.tif 000015
【図４】
0006313458.tif 000016
【図５】
0006313458.tif 000017
【図６】
0006313458.tif 000018
【図７Ａ】
0006313458.tif 000019
【図７Ｂ】
0006313458.tif 000020
【図７Ｃ】
0006313458.tif 000021
【図７Ｄ】
0006313458.tif 000022