(57)【特許請求の範囲】
【請求項１】
ユーザへのデータファイルの送信を管理する方法であって、
第１のファイルを複数の第１のセグメントに分割するステップと、
第２のファイルを複数の第２のセグメントに分割するステップであって、前記第１および第２のファイルは、異なるファイルである、ステップと、
選んだ第１のセグメントを第１のユーザデバイスに、かつ異なる第１のセグメントを第２のユーザデバイスに送信するステップと、
選んだ第２のセグメントを第１のユーザデバイスに、かつ異なる第２のセグメントを第２のユーザデバイスに送信するステップと、
第１のユーザデバイスに送信される、前記選んだ第１のセグメントまたは前記選んだ第２のセグメントの少なくとも部分を、第２のユーザデバイスに送信される、前記異なる第１のセグメントまたは前記異なる第２のセグメントの少なくとも部分と結合して、結合前の前記セグメントの少なくとも部分の合計サイズよりも小さいサイズの結合セグメントを生成するステップと、
各ユーザが、前記結合セグメントと、第１および第２のユーザデバイスに送られた、前記選んだ第１のセグメント、前記異なる第１のセグメント、前記選んだ第２のセグメントおよび前記異なる第２のセグメントの少なくとも部分とを使用して、第１および第２のユーザデバイスに送られた、前記選んだ第１のセグメント、前記異なる第１のセグメント、前記選んだ第２のセグメントおよび前記異なる第２のセグメントの少なくとも部分を復元するために、前記結合セグメントを第１のユーザデバイスおよび第２のユーザデバイスに送信するステップと
を含む、方法。
【請求項２】
第１および第２のユーザデバイスに送信される、前記選んだ第１のセグメント、前記異なる第１のセグメント、前記選んだ第２のセグメントおよび前記異なる第２のセグメントが、前記結合セグメントが第１および第２のユーザデバイスに送信される前に送信される、請求項１に記載の方法。
【請求項３】
前記結合に先立って、前記結合と関係がある、前記選んだ第１のセグメントまたは前記選んだ第２のセグメントと、前記異なる第１のセグメントまたは前記異なる第２のセグメントとのうちの大きい方のセグメントを第１および第２の部分に分割するステップと、
前記結合に当たって、前記結合と関係がある、前記選んだ第１のセグメントまたは前記選んだ第２のセグメントと、前記異なる第１のセグメントまたは前記異なる第２のセグメントとのうちの小さい方のセグメントと共に、前記大きい方のセグメントの前記第１の部分を前記結合セグメントに組み込むステップと、
前記大きい方のセグメントの前記第２の部分を第１および第２のユーザデバイスに送信するステップとを含む、請求項１に記載の方法。
【請求項４】
前記大きい方のセグメントの前記第２の部分を前記結合セグメントとともに送信するステップを含む、請求項３に記載の方法。
【請求項５】
平均送信速度を最小化するために、第１のセグメントのサイズおよび第２のセグメントのサイズを選択するステップをさらに含む、請求項１に記載の方法。
【請求項６】
第１のセグメントのサイズおよび第２のセグメントのサイズを最適化する際に、第１のユーザデバイスおよび／または第２のユーザデバイスによって第１のファイルおよび第２のファイルが要求される確率を使用するステップを含む、請求項１に記載の方法。
【請求項７】
ユーザへのデータファイルの送信を管理するデータ送信管理装置であって、
第１のファイルを複数の第１のセグメントに分割し、第２のファイルを複数の第２のセグメントに分割する分割器であって、第１および第２のファイルは異なるファイルである、分割器と、
選んだ第１のセグメントを第１のユーザデバイスに、異なる第１のセグメントを第２のユーザデバイスに送信し、かつ、選んだ第２のセグメントを第１のユーザデバイスに、異なる第２のセグメントを第２のユーザデバイスに送信する送信機装置と、
第１のユーザデバイスに送信される、前記選んだ第１のセグメントまたは前記選んだ第２のセグメントの少なくとも部分を、第２のユーザデバイスに送信される、前記異なる第１のセグメントまたは前記異なる第２のセグメントの少なくとも部分と結合して、結合前の前記セグメントの少なくとも部分の合計サイズよりも小さいサイズの結合セグメントを生成する結合器とを備え、
前記送信機装置が、第１および第２のユーザのそれぞれが、前記結合セグメントと、第１および第２のユーザデバイスに送られた、前記選んだ第１のセグメント、前記異なる第１のセグメント、前記選んだ第２のセグメントおよび前記異なる第２のセグメントの少なくとも部分とを使用して、第１および第２のユーザデバイスに送られた、前記選んだ第１のセグメント、前記異なる第１のセグメント、前記選んだ第２のセグメントおよび前記異なる第２のセグメントの少なくとも部分を復元するために、前記結合セグメントを第１のユーザデバイスおよび第２のユーザデバイスに送信するように動作可能である、データ送信管理装置。
【請求項８】
分割器が、前記結合に先立って、前記結合と関係がある、前記選んだ第１のセグメントまたは前記選んだ第２のセグメントと、前記異なる第１のセグメントまたは前記異なる第２のセグメントとのうちの大きい方のセグメントを第１および第２の部分に分割するように動作可能であり、
前記結合に当たって、結合器が、前記結合と関係がある、前記選んだ第１のセグメントまたは前記選んだ第２のセグメントと、前記異なる第１のセグメントまたは前記異なる第２のセグメントとのうちの小さい方のセグメントと共に、前記大きい方のセグメントの前記第１の部分を前記結合セグメントに組み込むように動作可能であり、
前記送信機装置が、前記大きい方のセグメントの前記第２の部分を第１および第２のユーザデバイスに送信するように動作可能である、請求項７に記載のデータ送信管理装置。
【請求項９】
平均送信速度を最小化するために、第１のセグメントのサイズおよび第２のセグメントのサイズを選択するためのプロセッサを備える、請求項７に記載のデータ送信管理装置。
【請求項１０】
第１のセグメントのサイズおよび第２のセグメントのサイズを最適化するために、第１のユーザデバイスおよび／または第２のユーザデバイスによって第１のファイルおよび第２のファイルが要求される確率を使用するためのプロセッサを備える、請求項７に記載のデータ送信管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザへのデータファイルの送信を管理する方法および装置に関し、より詳細には、ユーザにとってローカルにキャッシュされるべきデータファイルの送信に関するが、これに限定されるわけではない。
【背景技術】
【０００２】
サーバは、たとえばインターネットまたは何らかの他のネットワークであり得るネットワークを介してユーザに送信されることになるデータファイルを保持することができる。データファイルは、メディアコンテンツファイルであるか、または何らかの他のタイプのものであってもよく、たとえばユーザがそれらを要求したときか、あるいはコンテンツ作成者またはプロバイダがそれらの配信を希望したときに、ユーザに送信されてもよい。ユーザが、データファイルへの即座のアクセスを要求しない場合、または後でアクセスするためにそのデータファイルを入手可能な状態にしておくことを望む場合、データファイルは、ユーザにとってローカルなキャッシュメモリに格納されてもよい。たとえば、キャッシュメモリは、ユーザ機器に備えられたハードディスクドライブであってもよく、あるいは、キャッシュメモリは、たとえば、ネットワークの境界から見てサーバよりも近くに位置することによって、ユーザにとって容易にアクセスできるように設けられ、配置されていてもよい。ユーザが、キャッシュに格納されたファイルを必要とするとき、少ないネットワークリソースで、またはネットワークリソースを使用せず、キャッシュメモリからそのファイルを取得することができる。
【０００３】
データ送信は、キャッシュされることになるデータファイルを、ネットワークリソースが大容量である、かつ／または低コストである時間に送信することによって効率的に管理され得る。たとえば、データファイルは、ＷｉＦｉネットワークが利用可能な場合や、ユーザが低トラフィックの区域にいるかまたは低トラフィックの時間のときに送信されてもよい。
【発明の概要】
【課題を解決するための手段】
【０００４】
本発明の第１の態様によれば、ユーザへのデータファイルの送信を管理する方法において、第１のファイルが複数の第１のセグメントに分割され、第２のファイルが複数の第２のセグメントに分割される。ある第１のセグメントは第１のユーザに送信され、別の第１のセグメントは第２のユーザに送信される。ある第２のセグメントは第１のユーザに送信され、別の第２のセグメントは第２のユーザに送信される。結合前のセグメントの少なくとも部分の合計サイズよりも小さいサイズの結合セグメントを生成するために、第１のユーザに送信されるセグメントの少なくとも部分が、第２のユーザに送信されるセグメントの少なくとも部分と結合される。結合セグメントは、各ユーザが結合セグメントおよびセグメントの少なくとも部分を使用してセグメントを復元するために、第１のユーザおよび第２のユーザに送信される。
【０００５】
結合前のセグメントの少なくとも部分の合計サイズに比べて結合セグメントのサイズがより小さいとは、ユーザにとってローカルな１つまたは複数のキャッシュにキャッシュされることになる場合に、結合セグメントが要求する空間がより小さいことを意味する。さらに、結合セグメントのサイズが小さくなるにつれて、セグメントが結合されない形で個別に送信されることになる場合よりも、送信に必要なネットワークリソースは少なくなる。これは、ユーザにとってローカルな１つまたは複数のメモリキャッシュにセグメントがキャッシュされない構成においてさえも有利である。
【０００６】
１つまたは複数のユーザは、ネットワーク内の任意のノードであってもよい。たとえば、無線ネットワークにおいて、ユーザは、ルータもしくはエンドユーザまたは何らかの他のネットワークノードであり得る。
【０００７】
本発明による方法は、無線、固定回線または他のタイプのネットワークに適用されてもよく、ある特定の技術タイプには限定されない。
【０００８】
本発明による方法は、ｆ個のファイルおよびＫのユーザが存在する場合に適用されてもよく、各ファイルを２のＫ乗個のセグメントに区分するステップを含み、そこには、ユーザの部分集合ごとに、その部分集合内のユーザのすべてに保存されるセグメントが存在する。
【０００９】
一実施形態において、第１のユーザに送信される第１および第２のセグメントは、第１のユーザにとってローカルな第１のキャッシュメモリにキャッシュされてもよい。同様に、第２のユーザに送信される第１および第２のセグメントは、第２のユーザにとってローカルな第２のキャッシュメモリにキャッシュされてもよい。したがって、キャッシュメモリは、第１のファイルの部分および第２のファイルの部分のみを格納するように構成されていてもよく、これは、キャッシュメモリが、完全なファイルを格納するには不十分なサイズであるときに有利であり得る。その後、ユーザの一方または両方が第１のファイルまたは第２のファイルにアクセスしたいとき、ユーザは既にいくつかのセグメントにローカルでアクセスしているので、ファイル全体がユーザに送信される必要はない。したがって、たとえ残りのセグメントが場合により比較的費用のかかる時間に、またはネットワーク負荷が高いときに送信される必要があっても、ファイル全体が送信される必要はないので、ファイルを送信するための全体的なコストが低減され得る。さらに、結合セグメントは寄与セグメントの合計サイズよりも小さく、これによって効率的なファイル送信管理が実現できる。
【００１０】
一実施形態において、有限体における加算を使用して、第１のユーザに送信されるセグメントの少なくとも部分が、第２のユーザに送信されるセグメントの少なくとも部分に結合される。一実施形態において、有限体は２元体である。
【００１１】
ある方法では、第１および第２のユーザに送信される第１および第２のセグメントは、結合セグメントが第１および第２のユーザに送信される前に送信される。しかしながら、別の実施形態では、データが異なる順序で送信される。
【００１２】
一実施形態において、セグメントが第１および第２の部分に分割され、第１の部分は結合セグメントに組み込まれ、第２の部分は第１および第２のユーザに送信される。第２の部分は結合セグメントと同時に送信されてもよいし、個別に送信されてもよい。
【００１３】
本発明の第２の態様によれば、ユーザへのデータファイルの送信を管理するデータ送信管理装置は、第１のファイルを複数の第１のセグメントに分割し、第２のファイルを複数の第２のセグメントに分割する分割器と、ある第１のセグメントを第１のユーザに、別の第１のセグメントを第２のユーザに送信し、かつ、ある第２のセグメントを第１のユーザに、別の第２のセグメントを第２のユーザに送信する送信機装置と、結合前のセグメントの少なくとも部分の合計サイズよりも小さいサイズの結合セグメントを生成するために、第１のユーザに送信されるセグメントの少なくとも部分を、第２のユーザに送信されるセグメントの少なくとも部分と結合する結合器とを備え、前記送信機装置は、第１および第２のユーザのそれぞれが結合セグメントおよびセグメントの少なくとも部分を使用してセグメントを復元するために、結合セグメントを第１のユーザおよび第２のユーザに送信するように動作可能である。
【００１４】
次に、ほんの一例として、本発明のいくつかの実施形態を添付の図面を参照しながら説明する。
【図面の簡単な説明】
【００１５】
【図１】本発明による方法のフローチャートを概略的に示す図である。
【図２】送信を示す概略的なグラフである。
【図３】図１の方法を実施するための装置を概略的に示す図である。
【発明を実施するための形態】
【００１６】
第１の実施形態においては、サーバから入手可能な第１のファイルＡおよび第２のファイルＢが存在し、各ファイルのサイズは１ＭＢであると仮定する。第１のユーザＵ１および第２のユーザＵ２が存在し、各ユーザは、関連付けられたローカルキャッシュメモリＭ１およびＭ２をそれぞれ有し、Ｍ１およびＭ２はそれぞれ１ＭＢである。これら２つのユーザＵ１およびＵ２の履歴が、それぞれファイルＡおよびファイルＢを等しい確率で要求し得ることを示していると仮定する。
【００１７】
このキャッシュ保存方式では、費用のかかるネットワークにおいて平均０．５ＭＢでブロードキャストすることが必要である。さらに、ピーク速度は０．５ＭＢである。
【００１８】
図１を参照すると、１において、第１および第２のファイルがいくつかのセグメントに分割される。ファイルＡは、それぞれ０．５ＭＢである２つの等しいサイズのセグメントＡ１およびＡ２に分割され、したがってＡ＝（Ａ１，Ａ２）である。
【００１９】
同様に、ファイルＢは、それぞれ０．５ＭＢである２つの等しいサイズのセグメントＢ１およびＢ２に分割され、Ｂ＝（Ｂ１，Ｂ２）である。
【００２０】
２において、セグメントＡ１およびＢ１が第１のユーザＵ１に送信され、３において、関連付けられたキャッシュメモリＭ１に保存される。また、Ａ２およびＢ２は、第２のユーザＵ２に送信され、関連付けられたキャッシュメモリＭ２に保存される。キャッシュ保存方策は表１に、確率は表２にまとめられている。
【００２１】
【表１】
0005833737.tif 000002
【００２２】
【表２】
0005833737.tif 000003
したがって、各ユーザは各ファイルの部分を有する。
【００２３】
その後、たとえば、第１のユーザＵ１がファイルＡにアクセスすることを希望し、かつ第２のユーザＵ２がファイルＢを要求する場合、いずれのユーザにも、完全なファイルを得るために十分なセグメントはキャッシュされていない。各ユーザは、４において各々の要求をサーバに送信する。
【００２４】
５において、サーバは、送信機が結合セグメントＡ２＋Ｂ１をブロードキャストするように手配し、式中、＋は結合セグメントを生成するための有限体における加算を示す。この例において、結合は２元体で行われ、したがって、＋は単にビット毎のＸＯＲ演算である。結合セグメントＡ２＋Ｂ１は０．５ＭＢのサイズを有する。これは、セグメントＡ２の０．５ＭＢおよびセグメントＢ１の０．５ＭＢ、すなわち合計で１ＭＢのサイズに匹敵する。
【００２５】
６に示される次の段階では、第１のユーザＵ１がＡ２＋Ｂ１を受け取り、第１のユーザＵ１は既にそのキャッシュメモリＭ１内にＢ１を有している。したがって、第１のユーザＵ１は、（Ａ２＋Ｂ１）−Ｂ１の演算によってＡ２を復元することができる。第１のユーザＵ１はそのキャッシュメモリＭ１内にＡ１も有している。したがって、第１のユーザＵ１はＡ１およびＡ２の両方を有し、要求されるファイルＡを再構成することができる。
【００２６】
第２のユーザＵ２も、送信機によってブロードキャストされたＡ２＋Ｂ１を受け取る。第２のユーザＵ２は既にそのキャッシュメモリ内にＡ２を有しており、したがって、（Ａ２＋Ｂ１）−Ａ２の演算によってＢ１を復元することができる。第２のユーザＵ２は、既にそのキャッシュメモリＭ２内にＢ２も有している。したがって、第２のユーザＵ２が要求するファイルＢを再構成するために、Ｂ１およびＢ２の両方が利用可能である。
【００２７】
別のシナリオにおいては、出発点は表１に示されたものであるとし、第１および第２のユーザの両方がファイルＡを要求すると仮定する。この場合、送信機はＡ２＋Ａ１をブロードキャストし、式中、＋はやはり２元体において結合が行われることを示し、かつビット単位のＸＯＲ演算である。結合セグメントＡ２＋Ａ１は、セグメントＡ２の０．５ＭＢおよびセグメントＡ１の０．５ＭＢ、すなわち合計で１ＭＢのサイズに匹敵する０．５ＭＢのサイズを有する。
【００２８】
したがって、第１のユーザＵ１はＡ２＋Ａ１を受け取り、第１のユーザＵ１は既にそのキャッシュメモリ内にＡ１を有している。したがって、第１のユーザＵ１は（Ａ２＋Ａ１）−Ａ１によってＡ２を復元することができる。したがって、第１のユーザＵ１はセグメントＡ１およびＡ２の両方を有し、したがってファイルＡを再構成することができる。
【００２９】
第２のユーザＵ２も、ブロードキャストされたＡ２＋Ａ１を受け取り、第２のユーザＵ２は既にそのキャッシュメモリＭ２内にＡ２を有している。したがって、第２のユーザＵ２は、（Ａ２＋Ａ１）−Ａ２によってＡ１を復元することができる。したがって、第２のユーザＵ２はＡ１およびＡ２の両方を有し、したがってファイルＡを再構成することができる。
【００３０】
他のケースでは、ブロードキャスティング方策に加えて復元方法も下記の表３に示されている。各ユーザがいずれのファイルを要求したとしても、送信機はブロードキャストするために０．５ＭＢしか必要としないことが分かる。したがって、送信機がブロードキャストするデータの平均速度は０．５ＭＢである。
【００３１】
【表３】
0005833737.tif 000004
本実施形態において、キャッシュ保存方式が最適化され、ネットワークの平均負荷または最大負荷が最小化される。既に述べた簡単な例においては、このキャッシュ保存方式によって、平均負荷を５０％まで、かつ１００％のピーク負荷を減少させることができる。
【００３２】
図２は、サイズがＦの２つのファイルおよびそれぞれキャッシュサイズＭを有する２つのユーザについての、正規化されたキャッシュメモリサイズに対する正規化された平均送信速度を示す。また、各ユーザがそのファイルの一方を求め得る確率は同様に確からしい。
【００３３】
別の実施形態において、Ｍ１およびＭ２の利用可能なキャッシュ保存メモリサイズをそれぞれ有する、第１および第２のユーザであるユーザ１およびユーザ２が存在すると仮定する。また、サーバは、ＦＡおよびＦＢのサイズ、すなわち
｜Ａ｜＝ＦＡ
｜Ｂ｜＝ＦＢ
をそれぞれ有する２つのファイルＡおよびＢを有していると仮定する。
【００３４】
ユーザは、以下の表４に列挙されたいくつかの確率でそのファイルの一方を要求することがある。
【００３５】
【表４】
0005833737.tif 000005
各ファイルは５つの部分に分割され、これらは等しい必要はなく、以下のようになる：
Ａ＝｛Ａ０，Ａ１，Ａ２，Ａ１２｝
Ｂ＝｛Ｂ０，Ｂ１，Ｂ２，Ｂ１２｝
サイズは、
｜Ａ０｜＝ｘ０、｜Ａ１｜＝ｘ１、｜Ａ２｜＝ｘ２、｜Ａ１２｜＝ｘ１２、
｜Ｂ０｜＝ｙ０、｜Ｂ１｜＝ｙ１、｜Ｂ２｜＝ｙ２、｜Ｂ１２｜＝ｙ１２
であり、したがって、
ｘ０＋ｘ１＋ｘ２＋ｘ１２＝ＦＡ
ｙ０＋ｙ１＋ｙ２＋ｙ１２＝ＦＢ
である。
【００３６】
Ａ１およびＢ１で示すファイルの部分は、ユーザ１のメモリにキャッシュされる。
【００３７】
Ａ２およびＢ２で示すファイルの部分は、ユーザ２のメモリにキャッシュされる。
【００３８】
Ａ１２およびＢ１２で示すファイルの部分は、両ユーザのメモリにキャッシュされる。
【００３９】
Ａ０およびＢ０で示すファイルの部分は、いずれのメモリにもキャッシュされない。
したがって、
ｘ１＋ｙ１＋ｘ１２＋ｙ１２≦Ｍ１
ｘ２＋ｙ２＋ｘ１２＋ｙ１２≦Ｍ２
である。
【００４０】
第１のシナリオでは、ユーザ１はファイルＡを所望し、ユーザ２はファイルＢを所望する。したがって、
ユーザ１はサーバからしか入手できないＡ０を要求する。
【００４１】
ユーザ２はサーバからしか入手できないＢ０を要求する。
【００４２】
ユーザ１はＡ１およびＡ１２を既に有する。
【００４３】
ユーザ２はＢ１およびＢ１２を既に有する。
【００４４】
ユーザ１はＡ２を求めるが、ユーザ２はそれをそのキャッシュ保存メモリに有している。
【００４５】
ユーザ２はＢ１を求めるが、ユーザ１はそれをそのキャッシュ保存メモリに有している。
【００４６】
したがって、サーバは、Ａ０およびＢ０の両方をユーザ１および２に送信しなければならない。
【００４７】
｜Ａ２｜＞｜Ｂ１｜であると仮定すると、サーバはセグメントＡ２を、Ａ２ＵおよびＡ２Ｌで示す２つの部分、すなわちＡ２＝｛Ａ２Ｕ，Ａ２Ｌ｝に区分し、ここで｜Ａ２Ｕ｜＝｜Ｂ１｜である。次いで、サーバは結合セグメントＡ２Ｕ＋Ｂ１を送信し、式中、＋は２元体または任意の他の有限体における加算であり、さらにＡ２Ｌも送信する。なお、
｜Ａ２Ｕ＋Ｂ１｜＋｜Ａ２Ｌ｜＝｜Ａ２｜＝ｍａｘ｛｜Ａ２｜，｜Ｂ１｜｝
であり、式中、ｍａｘ｛｜Ａ２｜，｜Ｂ１｜｝はＡ２のサイズおよびＢ１のサイズの最大値であることに留意されたい。
【００４８】
次いで、ユーザ１は、Ａ２Ｕ＋Ｂ１、Ａ２Ｌ、およびＢ１を使用してＡ２＝｛Ａ２Ｕ，Ａ２Ｌ｝を復元することができる。また、ユーザ２は、Ａ２Ｕ＋Ｂ１およびＡ２を使用してＢ１を復元することができる。
【００４９】
一方、｜Ａ２｜＜｜Ｂ１｜である場合、サーバはセグメントＢ１を、Ｂ１ＵおよびＢ１Ｌで示す２つの部分、すなわちＢ１＝｛Ｂ１Ｕ，Ｂ１Ｌ｝に分割し、ここで｜Ｂ１Ｕ｜＝｜Ａ２｜である。次いで、サーバは結合セグメントＢ１Ｕ＋Ａ２を送信し、さらにＢ１Ｌも送信し、＋はやはり２元体または任意の他の有限体における加算である。なお、
｜Ｂ１Ｕ＋Ａ２｜＋｜Ｂ１Ｌ｜＝｜Ｂ１｜＝ｍａｘ｛｜Ａ２｜，｜Ｂ１｜｝
であることに留意されたい。
【００５０】
次いで、ユーザ２は、Ｂ１Ｕ＋Ａ１、Ｂ１Ｌ、Ａ２を使用してＢ１＝｛Ｂ１Ｕ，Ｂ１Ｌ｝を復元することができる。また、ユーザ１は、Ｂ１Ｕ＋Ａ２、およびＢ１を使用してＡ２を復元することができる。
【００５１】
そうして、各ユーザは、自身が要求するファイルを再構成するために必要なセグメントを得る。
【００５２】
第２のシナリオでは、ユーザ１およびユーザ２の両方がファイルＡを要求する。注：
ユーザ１および２は、サーバメモリでしか入手できないＡ０を求める。
【００５３】
ユーザ１および２の両方が既にＡ１２を有する。
【００５４】
ユーザ１はＡ２を求めるが、ユーザ２はそれをそのキャッシュ保存メモリに有している。
【００５５】
ユーザ２はＡ１を求めるが、ユーザ１はそれをそのキャッシュ保存メモリに有している。
【００５６】
したがって、サーバは、Ａ０をユーザ１および２に送信しなければならない。
【００５７】
｜Ａ２｜＞｜Ａ１｜であると仮定すると、サーバはセグメントＡ２を、Ａ２ＵおよびＡ２Ｌで示す２つの部分、すなわちＡ２＝｛Ａ２Ｕ，Ａ２Ｌ｝に区分し、ここで｜Ａ２Ｕ｜＝｜Ａ１｜である。次いで、サーバは結合セグメントＡ２Ｕ＋Ａ１およびＡ２Ｌを送信し、式中、＋は２元体または任意の他の有限体における加算である。なお、
｜Ａ２Ｕ＋Ａ１｜＋｜Ａ２Ｌ｜＝｜Ａ２｜＝ｍａｘ｛｜Ａ２｜，｜Ａ１｜｝であることに留意されたい。
【００５８】
次いで、ユーザ１は、Ａ２Ｕ＋Ａ１、Ａ２Ｌ、およびＡ１を使用してＡ２＝｛Ａ２Ｕ，Ａ２Ｌ｝を復元することができる。また、ユーザ２は、Ａ２Ｕ＋Ａ１およびＡ２を使用してＡ１を復元することができる。
【００５９】
一方、｜Ａ２｜＜｜Ａ１｜である場合、サーバは、Ａ１を、Ａ１ＵおよびＡ１Ｌで示す２つの部分、すなわちＡ１＝｛Ａ１Ｕ，Ａ１Ｌ｝に区分し、ここで｜Ａ１Ｕ｜＝｜Ａ２｜である。次いで、サーバはＡ１Ｕ＋Ａ２およびＡ１Ｌを送信し、式中、＋は２元体または任意の他の有限体における加算である。なお、
｜Ａ１Ｕ＋Ａ２｜＋｜Ａ１Ｌ｜＝｜Ｂ１｜＝ｍａｘ｛｜Ａ２｜，｜Ｂ１｜｝であることに留意されたい。
【００６０】
次いで、ユーザ２は、Ａ１Ｕ＋Ａ１、Ａ１Ｌ、およびＡ２を使用してＡ１＝｛Ａ１Ｕ，Ａ１Ｌ｝を復元する。また、ユーザ１は、Ａ１Ｕ＋Ａ２、およびＡ１を使用してＡ２を復元することができる。
【００６１】
この方策に続いて、異なるケースで要求される速度が、下記の表５に示されている。
【００６２】
【表５】
0005833737.tif 000006
したがって、平均速度は以下に等しい：
ｐＡＡ（ｘ０＋ｍａｘ｛ｘ１，ｘ２｝）＋ｐＡＢ（ｘ０＋ｙ０＋ｍａｘ｛ｘ２，ｙ１｝）＋ｐＢＡ（ｘ０＋ｙ０＋ｍａｘ｛ｘ１，ｙ２｝）＋ｐＢＢ（ｙ０＋ｍａｘ｛ｙ１，ｙ２｝）
したがって、ｘ０、ｘ１、ｘ２、ｘ１２、ｙ０、ｙ１、ｙ２、およびｙ１２が、平均速度を最小化するために選択され得る：
Ｍｉｎ  ｐＡＡ（ｘ０＋ｍａｘ｛ｘ１，ｘ２｝）＋ｐＡＢ（ｘ０＋ｙ０＋ｍａｘ｛ｘ２，ｙ１｝）＋ｐＢＡ（ｘ０＋ｙ０＋ｍａｘ｛ｘ１，ｙ２｝）＋ｐＢＢ  （ｙ０＋ｍａｘ｛ｙ１，ｙ２｝）
以下を条件とする：
ｘ０＋ｘ１＋ｘ２＋ｘ１２＝ＦＡ
ｙ０＋ｙ１＋ｙ２＋ｙ１２＝ＦＢ
ｘ１＋ｙ１＋ｘ１２＋ｙ１２≦Ｍ１
ｘ２＋ｙ２＋ｘ１２＋ｙ１２≦Ｍ２
ｘ０、ｘ１、ｘ２、ｘ１２、ｙ０、ｙ１、ｙ２、およびｙ１２≧０
最大速度が主たる関心事である場合、以下の最適化が使用され得る：
Ｍｉｎ  Ｍａｘ［ｐＡＡ（ｘ０＋ｍａｘ｛ｘ１，ｘ２｝）、ｐＡＢ（ｘ０＋ｙ０＋ｍａｘ｛ｘ２，ｙ１｝）、ｐＢＡ（ｘ０＋ｙ０＋ｍａｘ｛ｘ１，ｙ２｝）、ｐＢＢ（ｙ０＋ｍａｘ｛ｙ１，ｙ２｝）］
以下を条件とする：
ｘ０＋ｘ１＋ｘ２＋ｘ１２＝ＦＡ
ｙ０＋ｙ１＋ｙ２＋ｙ１２＝ＦＢ
ｘ１＋ｙ１＋ｘ１２＋ｙ１２≦Ｍ１
ｘ２＋ｙ２＋ｘ１２＋ｙ１２≦Ｍ２
ｘ０、ｘ１、ｘ２、ｘ１２、ｙ０、ｙ１、ｙ２、およびｙ１２≧０
この方法を改良するために他の態様が使用されてもよい。たとえば、キャッシュ保存にいくらかのコストがかかる場合、相当するコストがデータ速度最適化の目的関数に追加されてもよい。たとえば、両ユーザへのデータ送信にかかるコストが、片方のユーザへのデータ送信にかかるコストと異なる場合、目的関数はそれに応じて修正されてもよい。また、あるユーザがファイルのいくつかの部分を既に有している場合、これが最適化に利用されてもよい。また、各ユーザは、自身のメモリにキャッシュされるべきファイルのセグメントにいくつかの優先度を設けてもよい。そのような優先度が、最適化において考慮されてもよい。ユーザへのデータの送信では、ユーザの優先度が考慮されてもよい。たとえば、ファイルは、ユーザがそのファイルを特定の順序で復元できるようにする様式で送信されてもよい。
【００６３】
この方法は、任意の数のファイルおよび任意の数のユーザに合わせて拡張され得る。たとえば、３つのユーザ、ユーザ１、ユーザ２、およびユーザ３と、３つのファイルＡ、Ｂ、およびＣとが存在すると仮定する。
【００６４】
各ファイルは、以下の８つのセグメントに区分される：
Ａ＝｛Ａ０，Ａ１，Ａ２，Ａ３，Ａ１２，Ａ１３，Ａ２３，Ａ１２３｝
Ｂ＝｛Ｂ０，Ｂ１，Ｂ２，Ｂ３，Ｂ１２，Ｂ１３，Ｂ２３，Ｂ１２３｝
Ｃ＝｛Ｃ０，Ｃ１，Ｃ２，Ｃ３，Ｃ１２，Ｃ１３，Ｃ２３，Ｃ１２３｝
次いで、各セグメントは以下のように保存される：
セグメントＸ０はいずれのユーザにもなく、Ｘ＝Ａ、Ｂ、Ｃ
セグメントＸｉはユーザｉにあり、ｉ＝１、２、３、かつＸ＝Ａ、Ｂ、Ｃ
セグメントＸｉｊはユーザｉおよびｊの両方にあり、ｉ，ｊ＝１、２、３、かつＸ＝Ａ、Ｂ、Ｃ
セグメントＸ１２３はすべてのユーザｉおよびｊにあり、Ｘ＝Ａ、Ｂ、Ｃ
分かりやすくするために、この例では、ｉ＝１、２、３、かつＸ＝Ａ、Ｂ、ＣであるセグメントＸｉは同じサイズを有し、ｉ，ｊ＝１、２、３、かつＸ＝Ａ、Ｂ、ＣであるＸｉｊも同じサイズを有すると仮定する。この仮定は、この例だけについてのものであり、一般的な要件ではない。
【００６５】
次いで、たとえば、ユーザ１がＡを希望し、ユーザ２がＢを希望し、ユーザ３がＣを希望した場合、送信機は、
Ａ０
Ｂ０
Ｃ０
Ａ２＋Ｂ１
Ａ３＋Ｃ１
Ｂ３＋Ｃ２
Ａ２３＋Ｂ１３＋Ｃ１２
を送信する。
【００６６】
そうして、各ユーザは、所望のファイルを読み出すのに十分なセグメントおよび結合セグメントを受け取ったことになる。
【００６７】
たとえばすべてのユーザがＡを希望した場合、送信機は、
Ａ０
ｅ１Ａ１＋ｅ２Ａ２＋ｅ３Ａ３
ｇ１Ａ１＋ｇ２Ａ２＋ｇ３Ａ３
ｑ１Ａ１２＋ｑ２Ａ１３＋ｑ３Ａ２３
を送信し、ここで、演算は十分な大きさの任意の有限体であり、ｅｋ、ｇｊ、ｑｉは同じ体からのものである。そうして、各ユーザは、完全なＡを求めるのに十分な式を得る。
【００６８】
セグメントのサイズは、上記のように最適化できる。ファイルのサイズは同じである必要はない。
【００６９】
ｆ個のファイルおよびＫのユーザが存在する場合、各ファイルは、２のＫ乗個のセグメントに区分され、そこには、ユーザの部分集合ごとに、その部分集合内のユーザのすべてに保存されるセグメントが存在する。これらのセグメントの一部のサイズはゼロであってもよい。
【００７０】
図３を参照すると、図１を参照しながら説明した実施形態を実施するためのデータ送信管理装置７が、データファイルＡおよびＢを保持するコンテンツ格納部８を備える。分割器９が、コンテンツ格納部８にアクセスしてデータファイルＡおよびＢを取得し、各ファイルを複数のセグメントに分割する。セグメントの一部は、ネットワーク容量が大きい、かつ／または要求されるリソースが費用のかからないものであるとき、ユーザ１０および１１に一度に送信されることになる。最初にユーザ１０および１１に送信されるべきセグメントが、制御プロセッサ１２によって選択され、制御プロセッサ１２はまた、いずれのセグメントが送信されるかについての記録を保有する。制御プロセッサ１２はサーバ１３に、いずれのセグメントがいずれのユーザに送信されるべきかについて指令を出す。サーバ１３は、当該セグメントを取得し、それらのセグメントを、送信機１４によってネットワークを介してユーザ１０および１１に送信する。各ユーザ１０および１１は、サーバ１１から送信されるデータセグメントを内部に格納するための関連付けられたメモリキャッシュ１５および１６をそれぞれ有する。各ユーザは、ファイルＡからの、またファイルＢからのセグメントを受け取る。
【００７１】
ユーザ１０および１１は、完全なファイルＡまたはＢを得たいとき、ネットワークを介してサーバ１３にメッセージを送信する。サーバ１３および制御プロセッサ１２は、ユーザの要求を満たすためにどういった結合セグメントが必要であるかを判定する。結合セグメントは、結合器１７によってファイルセグメントから生成され、サーバ１３を経由してユーザ１０および１１に配信される。そうして、ユーザ１０および１１は、以前に送信されたセグメントおよび結合セグメントを使用して完全なファイルを再構成することが可能になる。
【００７２】
図３に示された装置は、他の方法を既に述べたように実施するためのより複雑なデータファイル配信を実行するように構成されていてもよい。
【００７３】
「プロセッサ」の標識が付けられた任意の機能ブロックを含む、図面に示された種々の要素の機能は、専用のハードウェアならびに適切なソフトウェアに関連付けてソフトウェアを実行することが可能なハードウェアを使用することによって実現され得る。プロセッサによって実現されるとき、これらの機能は、単一の専用プロセッサ、単一の共有プロセッサ、または一部が共有であってもよい複数の個々のプロセッサによって実現されてもよい。さらに、用語「プロセッサ」の明示的な使用は、ソフトウェアを実行することが可能なハードウェアのみを指していると解釈されるべきではなく、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、ネットワークプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ソフトウェアを格納するための読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、および不揮発性メモリも暗黙的に含むことがあるが、これらに限定されるわけではない。従来の、かつ／または特注の他のハードウェアも含まれ得る。
【００７４】
本発明は、その趣旨または本質的な特徴から逸脱することなく、他の特定の形態において具体化されてもよい。記載された実施形態は、あらゆる点で例示に過ぎず、限定するものではないと考えられるべきである。したがって、本発明の範囲は、前述の説明ではなく、添付の特許請求の範囲によって示される。特許請求の範囲の意味および均等範囲に属するすべての変更は、その範囲に含まれることになる。
【図１】
0005833737.tif 000007
【図２】
0005833737.tif 000008
【図３】
0005833737.tif 000009