(57)【特許請求の範囲】
【請求項１】
ネットワークを介して通信されるデータ中の１以上の反復するデータブロックを符号化するシステムであって、
前記ネットワークに接続され、前記データを捕捉し、捕捉されたデータの中から、少なくとも１つの対応するデコーダモジュールにより復号可能な宛先アドレスを有する様々な通信セッションからのデータブロックを抽出し、サポートされた宛先アドレスを持たないデータを通過させる、エンコーダモジュールと、
前記エンコーダモジュールにアクセスすることができ、前記エンコーダモジュールによって過去に送信された１以上のデータブロックの内容を記憶するメモリであって、前記エンコーダモジュールが、抽出された前記データブロックのそれぞれの内容が前記エンコーダモジュールによって過去に送信された前記少なくとも１つデータブロックの内容と一致するか否かを判定する、メモリと、
からなり、前記判定が一致するものであった場合、前記エンコーダモジュールは対応する抽出された前記データブロックを符号化し、該データブロックを符号化形態で前記少なくとも１つの対応するデコーダモジュールへ送信し、前記判定が一致しないものであった場合、前記エンコーダモジュールは対応する抽出された前記データブロックを捕捉時の形態で前記少なくとも１つのデコーダモジュールへ送信する、システム。
【請求項２】
前記符号化形態の抽出されたデータブロックのそれぞれが、前記ネットワーク中の１以上のノードに対して透過的である、請求項１に記載のシステム。
【請求項３】
前記エンコーダモジュールが、前記ネットワークの２つのノード間の物理的接続におけるスイッチを介して接続され、前記スイッチが第１の構成であるときに前記エンコーダモジュールは前記２つのノード間の物理的接続を通るデータを処理し、前記スイッチが第２の構成であるときに該データは前記エンコーダモジュールを通過する、請求項１に記載のシステム。
【請求項４】
前記エンコーダモジュールは前記ネットワーク内のノードで動作し、抽出された前記データブロックのそれぞれについて、該データブロックの宛先アドレスをサポートする少なくとも１つの対応するデコーダモジュールへ至る経路を判定する、請求項１に記載のシステム。
【請求項５】
内容が一致する場合、前記エンコーダモジュールは、対応するデータブロックの内容が過去に送信されたものであることを示すインジケータを送信する、請求項１に記載のシステム。
【請求項６】
前記インジケータは特別な記号である、請求項５に記載のシステム。
【請求項７】
前記インジケータは特別なヘッダである、請求項５に記載のシステム。
【請求項８】
少なくとも１つのデータブロックのそれぞれがパケットペイロードである、請求項１に記載のシステム。
【請求項９】
少なくとも１つのデータブロックのそれぞれがパケットペイロードの一部である、請求項１に記載のシステム。
【請求項１０】
前記エンコーダモジュールは、抽出された前記データブロックを過去に送信された１以上のデータブロックの識別を確認するための同期手段を用いて符号化し、前記少なくとも１つの対応するデコーダモジュールは、抽出された前記データブロックの宛先アドレスをサポートする、請求項１に記載のシステム。
【請求項１１】
ネットワークを介して通信されるデータ中の１以上の反復するデータブロックを符号化する方法であって、
前記データを捕捉するステップと、
捕捉された前記データの中から、復号可能な宛先アドレスを有する様々な通信セッションからのデータブロックを抽出するステップと、
サポートされた宛先アドレスを持たないデータを通過させるステップと、
１以上の過去に送信されたデータブロックの内容を記憶するステップと、
抽出された前記データブロックのそれぞれの内容が少なくとも１つの過去に送信されたデータブロックの内容と一致するか否かを判定するステップと、
前記判定が一致するものであった場合、対応する抽出された前記データブロックを符号化し、該データブロックを符号化形態で前記少なくとも１つの対応するデコーダモジュールへ送信するステップと、
前記判定が一致しないものであった場合、対応する抽出された前記データブロックを捕捉時の形態で前記少なくとも１つのデコーダモジュールへ送信するステップと、
からなる方法。
【請求項１２】
内容が一致した場合、対応するデータブロックの内容が過去に送信されたものであることを示すインジケータを送信するステップを更に含む、請求項１１に記載の方法。
【請求項１３】
前記少なくとも１つの過去に送信されたデータブロックの識別を、抽出された前記データブロックの宛先アドレスをサポートする少なくとも１つ対応するデコーダモジュールに同期させるステップを更に含む、請求項１１に記載の方法。
【請求項１４】
抽出された前記データブロックの内容が前記少なくとも１つの過去に送信されたいずれのデータブロックの内容とも一致しなかった場合、メモリ内にある過去に送信されたデータブロックのうちの少なくとも１つを消去して、対応する抽出された前記データブロックを捕捉時の形態で前記メモリに記憶するか否かを判定するステップを更に含む、請求項１１に記載の方法。
【請求項１５】
前記１以上の過去に送信されたデータブロックの内容を記憶するステップは、１以上の過去に送信された一意のデータブロックを最近使用データ構造に記憶することを含み、該最近使用データ構造は最大容量を有し、前記過去に送信された一意のデータブロックのそれぞれが一意の識別子を有し、前記１以上の記憶されるデータブロックは最後に使用されたものから最も古くに使用されたものの順で配置される、請求項１１に記載の方法。
【請求項１６】
内容が一致した場合、一致する内容を有する前記過去に送信されたデータブロックを、最後に使用された過去に送信されたデータであることを示す前記最近使用データ構造内の位置に関連付けるステップを更に含む、請求項１５に記載の方法。
【請求項１７】
抽出された前記データブロックの内容が過去に送信されたいずれのデータブロックの内容とも一致しなかった場合、該抽出されたデータブロックを前記最近使用データ構造に記憶し、最後に使用された位置を該抽出されたデータブロックに関連付けるステップを更に含む、請求項１５に記載の方法。
【請求項１８】
前記最近使用データ構造が最大容量に達した場合、最も古くに使用されたデータブロックの順番位置にある前記過去に送信されたデータブロックを消去するステップを更に含む、請求項１７に記載の方法。
【請求項１９】
ネットワークを介したデータフローを表すモデルの第１の層で少なくとも１つのデータブロックを符号化し、前記モデルの第２の層で少なくとも１つの抽出されたデータブロックをカプセル化するステップを更に含む、請求項１８に記載の方法。
【請求項２０】
前記層のうちの一方がコネクション指向の層であり、他方の層がコネクションレスの層である、請求項１９に記載の方法。
【請求項２１】
１以上の対応するデコーダモジュールからネットワークを介してルーティング情報を受信するステップと、
前記ルーティング情報から各デコーダモジュールでサポートされる１以上のアドレスを判定するステップと、
を更に含む、請求項１１に記載の方法。
【請求項２２】
前記１以上のデコーダモジュールからの前記ルーティング情報に基づいてネットワークトポロジ情報を判定するステップを更に含む、請求項２１に記載の方法。
【請求項２３】
ネットワーク内の複数のデコーダモジュールが同じアドレスをサポートしている場合、１以上の抽出されたデータブロックの宛先デコーダモジュールを、ネットワークトポロジ情報およびルーティング基準に基づいて判定するステップを更に含む、請求項２２に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はネットワークを介したデータのネットワーキング及び通信に関し、詳しくは、ネットワーク通信データの連続ストリームをオンラインで透過的に符号化及び復号することに関する。
【０００２】
【従来の技術】
ネットワーク通信トラフィックの急激な増加に起因して、伝送すべきデータ量がデータ伝送に利用可能なバンド幅を超えてしまうことが多くなった。バンド幅の高い要求は、ネットワーク混雑を招き、通信遅延を生じさせる。利用可能なバンド幅が限られているという問題を解決する１つの方法は、伝送するデータをもっと効率的な形式に符号化することである。この圧縮処理は、データのサイズを低減するので、データ圧縮と呼ばれる。符号化すなわち圧縮されたデータは、元のデータと同じ情報を含んでいるが、記憶または伝送に必要なビット数は少ない。符号化すなわち圧縮されたデータから元のデータを正確に復元できる場合、その符号化処理すなわち圧縮処理は無損失処理と呼ばれる。
【０００３】
ＯＳＩ(Open Systems Interconnection)参照モデルは、ネットワークを介したデータフローを表現するために広く用いられているモデルである。ＯＳＩ参照モデルは７つの階層からなる。７つの階層の各々は、特定のインタフェースを介して下の階層と通信し、特定のプロトコルを用いてネットワーク上の別のシステムにある同階層と通信する。すべてのネットワーキング層を結合したものは、ネットワークスタックと呼ばれることがある。
【０００４】
ＯＳＩ参照モデルの最下層（第１層）は物理層である。物理層は、物理リンクを介したビット情報の伝送に関する層である。次の層（第２層）はデータリンク層であり、物理層によって提供されたリンクを介するブロックデータの伝送に関する層である。データリンク層は、ネットワーク（例えばイーサネット(R)）に接続された複数のシステムによる媒体の共有、互いに直接接続されたシステムのアドレス指定、及び、伝達されたデータブロックのチェックサムの計算などの問題に対処する層である。次の層（第３層）はネットワーク層であり、ネットワーク上の任意の２つのシステムが物理リンクで直接接続されていなくても互いに通信できるようにする層である。つまり、ネットワーク層は、宛先アドレスに基いてルート計算を実施し、それに従って情報パケットをネットワーク中にルーティングする。次の層（第４層）はトランスポート層であり、２つのシステム間でのデータフローを提供する層である。トランスポート層は、個々のデータパケットに対してではなく、２つのシステム間のデータフロー全体に対する処理を行なう。ＴＣＰ（Transmission Control Protocol）は、トランスポート層のプロトコルの１つである。ＴＣＰは、あるシステムから別のシステムへ送信されたすべての情報が実際に受信されること、及び、それらが送信した順番で受信されることを保証することにより、２つのシステム間に信頼性の高いデータの伝達を提供している。ＴＣＰプロトコルは、失われたパケットや再送されたパケット等の誤りを取り扱うことにより、この機能を提供する。次の３つの層は、セッション層（第５層）、プレゼンテーション層（第６層）、及び、アプリケーション層（第７層）である。アプリケーション層はＯＳＩ参照モデルの最上位層であり、通常、システムユーザに与えられるインタフェースである。例えば、電子メールメッセージは、ユーザによってアプリケーション層で作成され、次いで７つのネットワーキング層の各々で処理され、最終的にネットワーク上に送信される。ＯＳＩ参照モデルについてはTanenbaum著の「Computer Networks」第２版（1989）に詳しい説明があり、ここで参照することにより本明細書に援用する。
【０００５】
２つのシステム間の通信は、コネクションレスとコネクション指向との２つのカテゴリに大きく分類することができる。コネクションレス通信が行なわれるのは、データがアドレス情報を含む個別のパッケージで表現され、ネットワークが各パッケージをネットワーク上で交換されている他のいずれのパッケージとも無関係に配送する場合である。コネクション指向通信が行なわれるのは、２つのシステムがまずセットアップ手順を実行して実際の接続または仮想の接続を作成した後、その接続を介して複数のデータ片を交換する場合である。
【０００６】
パケットベースのＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol)プロトコルは、最もよく知られているインターネットのプロトコルのうちの２つである。ＩＰは、コネクションレスのネットワークを介したパケットのアドレス指定及びルーティングに関する一連の標準を規定するネットワーク層プロトコルである。ＴＣＰは、ネットワークを介した信頼性の高い情報の伝送を保証する手段を規定するコネクション指向のトランスポート層プロトコルである。ＩＰは、各パケットを個別に取り扱うので、コネクションレスであると考えられることに注意して欲しい。一方、ＴＣＰは、まず２つのシステム間にＴＣＰ接続を確立し、その後すべてのデータ片がその仮想リンクを利用するので、コネクション指向である。ＴＣＰ等のコネクション指向のサービスは、ＩＰ等のコネクションレス層の上で実施できることに注意して欲しい。
【０００７】
ネットワーク通信データの符号化すなわち圧縮は、ネットワーキングスタックの様々な階層で実施することができる。伝統的には、データはアプリケーション層（第７層）で符号化される。例えば、画像は、ＧＩＦ（Graphics Interchange Format）やＪＰＥＧ（Joint Photographic Experts Group format）などの様々な形態に符号化することができる。これらの符号化形態は、画像の保管や伝達に必要となる空間を低減させることができる。従って、サーバは、クライアントに送信する前にすべての画像をアプリケーション層で「ＧＩＦ」形態に符号化することができる。その後、クライアントで受信された各画像はアプリケーション層で復号され、元の閲覧可能な画像が生成される。この形態のアプリケーション層符号化すなわち圧縮は通常、送信前に単一のオブジェクトに対してオフラインで実施される。アプリケーション層符号化は、複数のオブジェクトからなる連続した通信ストリームに対してオンラインで実施されることはない。従って、オフラインアプリケーション層エンコーダは、オブジェクト間情報（即ち、１以上のサーバから１以上のクライアントへ送信される様々なオブジェクトすべてから得られる情報）に基づくのではなく、オブジェクト内情報（即ち、単一オブジェクトからの情報）にのみ基いている。
【０００８】
ＯＳＩ参照モデルのトランスポート層はコネクション指向のサービスなので、この層で使用されるオンライン符号化方法は事実上、コネクション指向のリンクを符号化することになる。従って、この符号化は、単一のコネクションまたは単一のフロー内で送信されるデータに対して実施されるだけである。クライアント−サーバアーキテクチャの場合、各コネクションはサーバと１つのクライアントとの間のコネクションであるから、すべてのクライアントについて個別の符号化処理を実行する必要がある。同様に、サーバからデータを受信するすべてのクライアントの各々について、個別のデコーダが必要である。従って、コネクション指向のリンクのオンライン符号化は、コネクション（即ち、セッションまたはフロー）数が少なく、サーバが１つまたは少数のクライアントとしか通信しない場合に効率的になるにすぎない。また、単一コネクション内のデータの符号化は、同一セッション内に存在する反復を検出できるだけであるから、すべてのコネクションをまとめて同じプロセスで符号化すること程効率的にはならない。例えば、個別の第４層セッション（例えばＴＣＰセッション）の各々には、一回しか送信されない複数のデータパターンまたはオブジェクトが存在する場合がある。この例では、エンコーダが各セッションを個別に検査しても、各オブジェクトまたはパターンが１セッションについて一回しか送信されないので、何も反復は検出されない。一方、エンコーダがすべてのセッションにわたるすべてのデータトラフィックを検査した場合、エンコーダはもっと多くの反復を検出するので、データトラフィックはもっと効率的に符号化される。
【０００９】
ネットワーク分野での符号化すなわち圧縮の他の実施形態としては、コネクションレスのレイヤ３におけるトラフィックの符号化に基づくものがある。これらのレイヤ３符号化技術は、パケット内符号化にのみ基いている。つまり、これらのシステムは、各パケットまたはデータグラムを、現在のパケット内の情報にだけ基いて個別に符号化する。従ってこれらのシステムは、パケット全体の反復や、複数のパケットにまたがって存在する反復を検出することができない。従って、これらのパケット内レイヤ３符号化技術では、多数の反復を見落としてしまうので、大量のデータ削減を行なうことができない。
【００１０】
従って、データ伝送の効率及びバンド幅利用率を改善することが望まれている。従来の符号化方法は、検査するデータの量に制限があるため、ネットワーク通信トラフィック全体に存在する反復の総数のうちの一部しか検出することができない。例えば、各パケットを個別に符号化する符号化方法は、同一パケット内に存在する反復だけしか検出することができない。同様に、各セッションを個別に扱う符号化方法は、同一セッション内に存在する反復だけしか検出することができない。また、特定の用途または特定のデータタイプに基づく符号化方法は、その特定タイプのデータ内に存在する反復だけしか検出することができない。これらのいずれの場合においても、複数のパケット、セッションあるいはデータタイプにまたがって発生する反復は、全く検出されない。そのため従来の符号化方法は、比較的少量のデータ削減しか行なうことができない。
【００１１】
発明の概要
本発明は、データパケットをオンラインで透過的にクロスセッションで符号化する方法及びシステムを提供する。本発明の一実施形態は、データパケットのストリームを補足し、符号化し、カプセル化する。次いでこの実施形態は、符号化及びカプセル化されたデータパケットを送信し、そのデータパケットを復号及び分離し、復号及び分離されたデータパケットをコネクションレスのネットワーク層に再注入する。本発明は、データストリーム内のどこに生じた反復でも（即ち、パケット／セッション内に生じた反復も、複数のパケット／セッションにまたがって生じた反復も両方）見つけて除去することにより、複数の通信セッションからの複数のデータストリームを符号化及び復号することができる。本発明の一実施形態は、ネットワークスタックのうちのコネクションレスのネットワーク層（第３層）でパケットを補足する。本発明のこの実施形態は、コネクションレスのネットワーク層（またはそれより下位の層）で動作するので、ネットワーク、サーバ、アプリケーション、及び、その他のネットワーク装置に対して透過的である。本発明は第３層またはそれより下位の層でパケットを補足及び処理しているので、それより上位の層（第４、第５、第６、及び、第７層）は全く同じ方法で第３層と対話することができる。
【００１２】
本発明は、任意の符号化アルゴリズムを用いて処理すべきデータを符号化することができる。従来の符号化方法は、単一パケットまたは単一オブジェクト内の反復を探す符号化アルゴリズムを利用することしかできなかった。本発明は、任意のオブジェクト内、パケット内符号化アルゴリズムに加えて、任意のオブジェクト間、パケット間、または、セッション間符号化アルゴリズムを用いることができる。つまり、本発明によると、データストリーム内にのどこかに生じた間隔の長い反復（即ち、多数の異なる独立したパケット、オブジェクトまたはセッションにまたがる反復）を見つけるための符号化アルゴリズムが利用可能になる。本発明の一実施形態において、この符号化アルゴリズムは、ネットワークを介して伝送される複数のパケットまたはデータグラムの間に生じた任意のデータブロックの反復を探しだす。これらの反復したデータブロックは、そのデータブロックの内容を一意に識別する一意の識別子で置き換えることにより、より効率的な形態に符号化される。
【００１３】
【発明の実施の形態】
次に本発明の好ましい実施形態について図面を参照して説明する。図面中の類似の符号は、同一の要素または機能的に類似した要素を意味している。また、図面において、各符号の一番左端の桁は、その符号が最初に登場した図面の番号に対応している。
【００１４】
本明細書で「一実施形態」または「実施形態」と呼ぶものは、それらの実施形態に関連して説明した特定の特徴、構造、あるいは性質が本発明の少なくとも１つの実施形態に含まれることを意味している。本明細書の様々な場所で使われる「一実施形態において」というフレーズは、すべて同じ実施形態を指している必要はないものとする。
【００１５】
以下の詳細な説明のうちのいくつかの部分は、コンピュータメモリ内のデータビットに対する処理のアルゴリズム及び抽象表現に関するものである。これらのアルゴリズム的な説明及び表現は、データ処理技術の当業者が自分達の成果を他の分野の当業者に効果的に伝達するために用いる手段である。本明細書に示すアルゴリズムは、概して、所望の結果が得られる筋道の通ったステップ（命令）のシーケンスであると考えられる。これらのステップには物理量の操作が必要である。必須ではないが、これらの物理量は通常、記憶、転送、結合、比較、その他操作を施すことが可能な、電気信号、磁気信号、あるいは、光信号の形態をとる。主に共通利用の理由から、これらの信号は、ビット、値、要素、記号、文字、語句、番号などとして示すと便利な場合がある。また、物理量の物理的操作が必要なステップの特定の構成は、モジュールまたはプログラム装置として示すと、汎用性を失わないので便利な場合がある。
【００１６】
しかしながら、これらすべて及び同様の用語は、適当な物理量に関するものであり、それらの物理量に付けられた単なる便宜上のラベルであると考えるべきである。下記の説明から明らかなように、明示的に述べていない限り、「処理」、「算出」、「計算」、「判定」、「表示」、または、「判定」などの用語を用いた説明は、コンピュータのシステムメモリ、レジスタまたはその他の情報記憶、伝達または表示装置内の物理（電子）量として表現されたデータを操作及び変換するコンピュータシステムまたはそれに類似する電子計算装置の動作及び処理を指している。
【００１７】
本発明の特定の態様には、本明細書で説明する処理ステップ及び命令がアルゴリズムの形態で含まれる。本発明のこれらの処理ステップ及び命令は、ソフトウェアでも、ファームウェアでも、あるいはハードウェアでも実現することができ、様々なオペレーティングシステムで使用される異なるプラットフォームにダウンロードしたり、それらから操作することができる。
【００１８】
本発明は、本明細書で説明する処理を実施するための装置に関するものでもある。この装置は、必要な目的に応じて専用に構成することもできるし、コンピュータに格納されたコンピュータプログラムによって選択的に稼動され、再構成される汎用コンピュータを含んでもよい。こうしたコンピュータプログラムは、限定はしないが、フロッピー(R)ディスク、光ディスク、ＣＤ−ＲＯＭ、磁気光ディスク、リードオンリーメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気／光カード、特定用途向け集積回路（ＡＳＩＣ）、及び、電気的命令を記憶するのに適した任意の種類の媒体などのコンピュータ読取可能媒体などに記憶され、各々がコンピュータシステムバスに接続される。さらに、本明細書でコンピュータと呼ぶものは、シングルプロセッサを有する場合もあるし、計算能力を向上させるためにマルチプロセッサ設計を採用したアーキテクチャである場合もある。
【００１９】
本明細書に提示するアルゴリズム及び表示は、何らかの特定のコンピュータまたはその他装置に関連するものではもともとない。本発明の教示に従うプログラムと共に様々な汎用システムも用いることができるし、もっと専用の装置を構成して必要な方法ステップを実施した方が便利であることが判明する場合もある。様々なこれらの構成について、必要な構成は、以下の説明から分かるであろう。さらに、本発明は、何らかの特定のプログラミング言語に関するものとして書かれたものではない。本明細書で説明するように、本発明の教示を実施するためには様々なプログラミング言語を利用することができ、下記では本発明の実施可能形態及び最良形態の開示のために特定の言語を設けているものと考えられる。
【００２０】
最後に、明細書で用いる言語は、可読性と産業上の目的を追求して選択したものであり、本発明の内容を正確に表現したり制限したりするために選択されたものではない。従って、本発明の開示は、本発明の例示を意図するものであり、特許請求の範囲に記載した発明の制限を意図したものではない。
【００２１】
図１は、本発明を含むネットワークを示す図である。この実施形態の場合、ネットワークはネットワーク接続すなわちリンクによって接続された２つのサブネットワーク１０２を含む。ネットワーク接続は、私設専用回線、フレームリレー回線または仮想私設網などの２つの個別ネットワークを相互接続する任意の物理的または論理的手段でよい。この２つのサブネットワーク１０２は、任意の距離だけ地理的に離れている。例えば、この２つのサブネットワーク１０２は、地理的に離れていて、ワイドエリアネットワーク（ＷＡＮ）リンクで互いに接続された２つの企業の遠隔事務所である場合がある。
【００２２】
本発明は、２つのモジュール、即ち、符号化・カプセル化モジュール（ＥＥ）１０４及び復号・分離モジュール（ＤＤ）１０６を含む。ＥＥモジュール１０４は通信トラフィックのパケットを符号化してカプセル化する。ＤＤモジュール１０６は、ＥＥモジュール１０４によって符号化された通信トラフィックを復号して、元の通信トラフィックを再現する。つまり、すべてのＥＥモジュール１０４の各々について、対応するＤＤモジュール１０６が存在しなければならない。図１では、ＷＡＮリンクの両端の各々は、１つのＥＥモジュール及び１つのＤＤモジュール１０６を有している。従ってこの場合、いずれかのサブネットワークから他方のサブネットワークへのトラフィックは、ＥＥモジュール１０４によって符号化され、ＤＤモジュール１０４によって復号される。ネットワークリンクの同じ側にあるＥＥモジュール１０４及びＤＤモジュール１０６は、同一の物理装置またはボックスに存在してもよい。各ＥＥモジュール１０４及びＤＤモジュール１０６は単に、同一のハードウェアプラットフォーム上で動作する異なるプロセスにしてもよい。ＥＥモジュール１０４及びＤＤモジュール１０６は、プロセッサ上で動作するソフトウェアとして実現することもできるし、専用ハードウェア、ファームウェア、あるいはそれらの組み合わせとして実現することもできる。
【００２３】
データパケットはＥＥモジュール１０４によってより小さく効率的な形態に変換され、その後ＤＤモジュール１０６によって再変換されて元の大きさに戻される。従って、図１に示す例の場合、本発明によってデータ伝送の効率の度合いが改善されるネットワークの領域は、ワイドエリアネットワークリンクである。多くの場合、ＷＡＮリンクはネットワークの最も高価な構成要素であるから、この構成要素がバンド幅の最大要求の影響を受ける。従って本発明は、各ＷＡＮパケットをより効率的な小さな形態に符号化してＷＡＮ１０８を通るデータ伝送の効率を向上させるために用いられる。
【００２４】
本発明は、ネットワークのどのポイントでもデータを符号化及びカプセル化し、復号及び分離することができる。上記のように、図１はネットワークのＷＡＮセグメント１０８を通じた本発明の利用を図示している。ＷＡＮに用いられる物理伝送媒体及び通信プロトコルは、ＬＡＮに用いられるものとは異なる場合が多い。本発明は、符号化されたパケットを伝送する前にカプセル化するので、ＷＡＮインタフェースにもＬＡＮインタフェースにも内在させることができる。例えば図１の場合、本発明はＷＡＮを通るトラフィックを最適化しているが、ＬＡＮパケットをＷＡＮを通じた伝送のための正しい形態に変換するＬＡＮ-to-ＷＡＮエッジルータその他の装置の直前のＬＡＮ側にＥＥモジュール１０４を設置することもできる。この場合、このエッジ装置に宛てられたパケットはすべて、本発明のＥＥモジュール１０４にまず転送されることになる。同様に本発明のＤＤモジュール１０６も設置することができ、この場合、ＷＡＮ-to-ＬＡＮエッジ装置の直後のＬＡＮ側に設置することができる。従ってＥＥモジュール１０４及びＤＤモジュール１０６は、いずれもＬＡＮ内に実際に配置されることになるが、それらはＷＡＮ１０８を通るように宛先指定されたトラフィックしか処理しない。本発明をＬＡＮ内に配置するように設計する場合、ＬＡＮ内の本発明の実際の配置はネットワーク構成にかなり依存するものになる。符号化の必要なデータパケットがＥＥモジュール１０４に届きさえすれば、ＥＥモジュール１０４はＬＡＮ内のどこにあってもよい。同様に、符号化されたパケットがＤＤモジュール１０６に送信されて復号され、ＤＤモジュール１０６が復号されたパケットをそれらのパケットの宛先に送信できさえすれば、ＤＤモジュール１０６もＬＡＮ内のどこにあってもよい。
【００２５】
一実施形態において、本発明はＬＡＮネットワーク及びＷＡＮネットワークに対して完全に透過的であり、２ポートのレイヤ３ＬＡＮスイッチのように見える。この実施形態の場合、本発明はルーティングを行うノードではなく、ネットワーク内の経路指定された２つのノード間の中間装置として機能する。この場合、本発明のＥＥモジュール１０４が符号化できるパケットは、ネットワークのこれら２つのノード間でやり取りされるパケットだけである。これは、本発明の非経路指定動作モードと呼ばれる。本発明を非経路指定動作モードで利用する場合、本発明のユーザがすべてのＷＡＮトラフィックを処理することを望む場合（上記のように）には、本発明を取り付けるＬＡＮ内の適当な場所はＬＡＮのエッジルータの直前になる。本発明のもう１つの実施形態は、経路指定動作モードである。この形態の場合、本発明はＬＡＮの経路指定されたノードのように機能する。この場合、ＥＥモジュール１０４によって符号化する必要のあるパケットはすべて本発明に経路指定されるので、本発明はＬＡＮ内のどこにでも仮想的に取り付けることができる。
【００２６】
本発明の非経路指定実施形態及び経路指定実施形態は、いずれもＬＡＮの第３層で動作し、ネットワーキングスタックの第３層よりも上位の層すべてに対して透過的である。そのため本発明は、特定のパケットを処理せずにそれらのパケットをネットワークの次のノードへ透過的に転送するという選択もできる。この場合、本発明は、第３層からパケットを単に補足し、そのパケットを第３層でネットワークに再注入する。パケットが符号化されないので、パケットをカプセル化して対応するＤＤ装置に送信し、分離及び復号する必要はない。
【００２７】
本発明の非経路指定実施形態の場合、本発明はルーティング機能を何も実施しないので、ネットワーク接続性及び設計目的については、物理ワイヤーまたはリンクのように見える。また、本発明は、他のネットワークアプリケーション及びプロトコルに対して論理的に透過的であるので、ネットワークオペレータがパケットの符号化を望まない場合は、ワイヤーで置き換えることもできる。本発明はこのことを利用して、ネットワークから装置を物理的に切り離してその装置を物理的ワイヤーで効率的に置き換えるための「ワイヤーへの切替」モジュールを設けることにより、高レベルの信頼性を提供することができる。この機能は、異なる端点間の接続を切り替えるための物理的リレーを用いることにより実現することができる。このワイヤーへの切り替え機能は、本発明に対する電力の損失などを含む何らかの故障状況でトリガーすることができる。これらの故障状況の場合、リレーは、データパケットを物理入力ポートから直接取り出して物理出力ポートに出力するように、位置を切り替える。非故障状況の場合、リレーは、入力ポートをＥＥモジュール１０４及びＤＤ１０６モジュールの物理入力インタフェースに接続し、出力ポートをＥＥモジュール１０４及びＤＤ１０６モジュールの物理出力インタフェースに接続する。
【００２８】
いずれのＬＡＮベースの実施形態においても、本発明は、ＬＡＮルーティング情報を処理することにより、本発明のＤＤモジュール１０６が通信できるサブネットワーク及びアドレスを見付けることができる。例えば、本発明のＤＤモジュール１０６は、ルーティング情報を伝達するＯＳＰＦ（Open Shortest Path First）またはＲＩＰ（Routing Information Protocol）プロトコルパケットを受信することができる。本発明が非経路指定モードである場合、ＤＤモジュール１０６は、これらのルーティングパケットを受信するだけでよく、これらのルーティングプロトコルに参加する必要はない。本発明のＤＤモジュール１０６は、ＤＤモジュール１０６が通信することのできる相手先の（ローカルＬＡＮ上の）サブネットワーク及びアドレスを、そのＤＤモジュール１０６に対応するＥＥモジュール１０４へ伝達する。対応するＥＥモジュール１０４は、これらのサブネットワーク及びアドレス宛てのパケットだけを符号化してその特定のＤＤモジュール１０６に送信することを請け負う。つまり、ＥＥモジュール１０４は、パケットを受信して処理する際に、そのパケットが対応するＤＤモジュール１０６でサポートされたアドレス宛てのパケットであるか否かをまず判定する。アドレスがＤＤモジュール１０６が通信できるＬＡＮサブネットワークに属するものであった場合、そのパケットを符号化及びカプセル化し、ＤＤモジュール１０６へ送信する。そうではなかった場合、そのパケットは符号化されることなく本発明を通過して透過的に転送される。このように、本発明のＥＥモジュール１０４は、ＤＤモジュール１０６から得たルーティング情報を用いることにより、処理すべきパケットを判定することができる。また、ネットワークに複数のＤＤモジュール１０６が存在し、２以上のＤＤモジュール１０６が同じアドレスまたはサブネットワークを報告してきた場合は、ルーティングコスト、すなわちそのアドレスから複数のＤＤモジュールまでの距離を用いることにより、そのパケットを処理すべきＥＥ／ＤＤのペアを判定することができる。
【００２９】
符号化されたパケットはすべてＤＤモジュール１０６によって復号される必要があるので、ＥＥモジュール１０４は、自分の符号化したパケットが対応するＤＤモジュール１０６で正しく復号されることを保証する必要がある。これを保証するため、本発明は、ＥＥモジュール１０４とＤＤモジュール１０６との間に同期手段を設けることで、符号化アルゴリズムと復号アルゴリズムとが正しく同期することを保証している。このような同期システムの一例を次に示す。
【００３０】
一実施形態において、本発明は、コネクションレスのネットワーク層（即ち第３層）で伝送するためのパケットを取り出す。この実施形態の場合、本発明のＥＥモジュール１０４は、レイヤ３パケットまたはデータグラムの各々を符号化し、符号化されたパケットをカプセル化して、対応するＤＤモジュール１０６行きの通信路に入れる。このカプセル化は、符号化されたパケットが対応するＤＤモジュール１０６へ確実にルーティングされるものであれば、いかなるカプセル化プロトコルによって実施してもよい。考えられるカプセル化プロトコルとしては、ＴＣＰ、ＵＤＰ、及び、ＩＰ-ｉｎ-ＩＰが挙げられる。カプセル化プロトコルの選択は、各パケットを符号化するために用いられる符号化方法に影響を与える。例えば、ＴＣＰのような信頼性の高い伝送プロトコルを符号化された各パケットのカプセル化に用いた場合、符号化アルゴリズムはＤＤモジュール１０６上の復号アルゴリズムと明示的に同期させる必要はない。これに対して、ＵＤＰのような信頼性の無い伝送プロトコルを符号化された各パケットのカプセル化に用いた場合、符号化アルゴリズムは、符号化されたパケットがすべて正しく復号されることを保証するため、ＤＤモジュール１０６に関連する信頼性の高い個別の通信路を必要とする。このような違いがある理由は、ＴＣＰのような信頼性の高い伝送プロトコルをカプセル化に用いた場合、ＥＥモジュール１０４とＤＤモジュール１０６は、それらの間にデータ損失がないこと、及び、ＥＥモジュール１０４から送信されたパケットが同じ順番でＤＤモジュール１０６に配送される（ＴＣＰで）ことが保証されるからである。このような条件下では、ＥＥモジュール１０４と対応するＤＤモジュール１０６とのペアは、各々のアルゴリズムの状態が処理されるデータの関数として確定的に計算されるという事実に基いて、符号化アルゴリズムと復号化アルゴリズムとを確実に同期させることができる。従って、符号化アルゴリズムと復号化アルゴリズムが同じ同期パラメタを有していて、処理すべき同じデータが同じ順序でそれらのアルゴリズムに与えられた場合、自明ではあるが、それらのアルゴリズムは同じ同期状態を常に維持する。これに対して、ＥＥモジュール１０４からＤＤモジュール１０６への符号化されたデータの伝送中にデータ損失やデータの再送要求が起こる可能性がある場合（例えば、符号化されたパケットをＵＤＰを用いてカプセル化した場合）、本発明は、個別の同期通信路を用いてＤＤモジュール１０６をＥＥモジュール１０４に同期させることにより、ＤＤモジュール１０６によって受信された符号化データがすべて正確に復号されることを保証することができる。
【００３１】
図２は、本発明の一実施形態によるＥＥモジュール１０４及びＤＤモジュール１０６を示す図である。ＥＥモジュール１０４は、検出器構成要素２０２と、伝送構成要素２０４と、符号化・カプセル化構成要素とを含む。ＤＤモジュール１０６は、検出器構成要素２０２と、復号・分離構成要素２１０とを含む。これらのモジュールによって実施される処理は、本明細書に記載されている。
【００３２】
ＥＥモジュール１０４の符号化構成要素２０６によるパケットのカプセル化は、様々な方法で実施することができる。一実施形態では、処理された各パケットは、符号化が完了した後で、１つの送信パケットにカプセル化することができる。この場合、本発明を通過する入力パケット数と出力パケット数は同じになる。他の実施形態では、複数の符号化された入力パケットを、まとめて１つの送信カプセル化パケットにカプセル化することもできる。１つの出力パケットの中にカプセル化する符号化パケットの数は、異なっていてよいので、出力パケットのサイズが所与の固定サイズ（例えば、最大送信可能単位サイズ）を超えないように調節することができる。複数のパケットを複数の出力パケットにカプセル化する場合、出力パケット数はＥＥモジュール１０４の入力パケット数より少なくなる。同様に、出力パケット数は、ＤＤモジュール１０６の入力パケット数より多くなる。この実施形態では、符号化された入力パケットをバッファに保持することにより、さらなる入力パケットを一緒にカプセル化することも可能である。例えば、符号化パケットのサイズが５００バイトしかなく、カプセル化パケットの最大サイズが１０００バイトである場合、出力バッファにさらに５００バイトが追加されるまでその符号化パケットをバッファに保持することができる。また、この実施形態は、タイマー手段を用いることにより、符号化パケットの各々が所定の最大時間までしかバッファに保持されないようにすることができる。符号化パケットまたは複数の符号化パケットがこの最大時間制限より長い時間バッファに保持された場合は、出力バッファ内のそれらの符号化パケットをすべてカプセル化し、直ちに送信する（符号化パケットの総サイズが最大サイズに満たなくても）。
【００３３】
図３ａは、本発明の一実施形態によるＥＥモジュール１０４及びＤＤモジュール１０６によって処理されるようなパケットストリームの一例を示す状態図である。符号化後の８パケットは、３パケットしか占めないサイズにまで縮小される。これらの符号化パケット３０８は、カプセル化されてＤＤモジュール１０６に送信される。次に、ＤＤモジュール１０６は、ＥＥモジュール１０４から受信したそのストリームを復号及び分離して、元のコネクションレスストリームのパケットを復元する。次いで、ネットワーク層（第３層）でこれらのパケットをネットワークに直接注入する。従って、本発明は、ＥＥモジュール１０４とＤＤモジュール１０６との間の領域のパケット伝送を横取りして、リダイレクトするものである。ネットワーク層でＥＥモジュール１０４に入るパケットと、ネットワーク層でＤＤモジュール１０４から送信されるパケットが全く同じものであるため、２つのボックスの存在は発信元の機械と宛先の機械にとって透過的なものになる。例えば、ＴＣＰ接続のような発信元と宛先との間のコネクション指向リンクは、本発明の影響を受けることがなく、ＥＥモジュール１０４及びＤＤモジュール１０６が存在しなかったかのように機能し続ける。
【００３４】
図３ｂは、本発明の他の実施形態を示す図である。このネットワークは、図１に示したネットワークの論理的拡張である。図３ｂのネットワークは、１つのサブネットワークが複数のサブネットワークに接続されたポイント・ツー・マルチポイントのネットワークである。この場合も図１と同様に、各サブネットワークはローカルエリアネットワーク（ＬＡＮ）によって接続された複数のシステムを含んでいる。個々のサブネットワーク間の接続は、ワイドエリアネットワーク（ＷＡＮ）を通して行なわれる。この場合、ネットワークの中央、すなわちハブにある包括的なＥＥモジュール１０４及びＤＤモジュール１０６には、複数のＥＥプロセス及びＤＤプロセスが含まれる。これらのＥＥプロセス及びＤＤプロセスは、物理的にすべて同じ装置またはボックスに存在してもよい。ハブにあるＥＥサブプロセス及びＤＤサブプロセス（サブユニット）の各々は、リモートサブネットワークの各々にある特定のＥＥモジュール及びＤＤモジュール１０６に対応している。中央すなわちハブにあるこの包括的なＥＥモジュール１０４は、リモートＤＤモジュール１０６のそれぞれから送信されたネットワーク接続形態情報を収集することにより、いずれのＤＤモジュール１０６がいずれのサブネットワーク及びアドレス空間をサポートしているかを判定することができる。つまり、ハブにある包括的なＥＥモジュール１０４は、パケットを捕捉し、そのパケットの宛先情報とネットワーク接続形態情報とを用いて、いずれのＥＥ／ＤＤペアでそのパケットを処理すべきかを判定する。もしそのパケットがいずれのリモートＤＤモジュールによってもサポートされていないアドレスに宛てられたものであった場合、そのパケットはＥＥモジュール１０４を透過的に通過する（符号化及びカプセル化されることなく）。本発明で使用する符号化アルゴリズムは、様々なＥＥ及びＤＤプロセス間の符号化及び同期データを共有することにより、様々な方法でこのポイント・ツー・マルチポイント拡張を取り扱うことができる。図１及び上で説明した本発明のポイント・ツー・ポイントの様々な実施形態は、すべてこのポイント・ツー・マルチポイントの実施形態にも適用することができる。その理由は、ポイント・ツー・マルチポイント実施形態がポイント・ツー・ポイント実施形態の論理的拡張であるからである。
【００３５】
上で説明した本発明のポイント・ツー・ポイント実施形態及びポイント・ツー・マルチポイント実施形態は、マルチポイント・ツー・マルチポイント構成を含むようにさらに拡張することができる。この場合、グローバルネットワーク中の各サブネットワークは他のサブネットワークの各々に直接接続される。本発明は、複数のＥＥプロセス及びＤＤプロセスをネットワーク中の各サブネットワークに置くことにより、この構成をサポートすることができる。この場合、本発明は、ネットワークの各ＷＡＮについて個別のＥＥ及びＤＤプロセスペアを論理的に作成する。ネットワークリンクの同じ側に存在する複数のＥＥプロセス及びＤＤプロセスは、すべて同じ物理装置に配置することもできるし、複数の装置上に配置することもできる。上で説明したポイント・ツー・ポイント及びポイント・ツー・マルチポイントの本発明の様々な実施形態は、このマルチポイント・ツー・マルチポイント実施形態にも同様に適用することができる。その理由は、マルチポイント・ツー・マルチポイント実施形態がポイント・ツー・ポイント実施形態及びポイント・ツー・マルチポイント実施形態の論理的拡張であるからである。
【００３６】
図４は、本発明の一実施形態によるデータストリームの符号化、復号、及び、分離の処理を示すフロー図である。符号化／カプセル化構成要素２０６の符号化アルゴリズムは、コネクションレスのネットワーク層でパケットを捕捉する（４０２）。次いでこのアルゴリズムは、各パケットを符号化し（４０４）、符号化されたパケットをカプセル化する（４０６）。パケットを符号化するための処理については、以下でさらに説明する。次に、符号化及びカプセル化されたパケットを復号アルゴリズムに送信する（４０８）。次に、復号／分離構成要素２１０によって、このパケットを分離及び復号する（４１０）。パケットを復号するための処理については、以下でさらに詳しく説明する。次いでＤＤモジュール１０６は、この復号及び分離されたパケットをコネクションレスのネットワーク層に注入する。
【００３７】
本発明は、処理するデータを符号化するために、任意の符号化アルゴリズムを用いることができる。上記のように、従来の符号化方法は、１パケットまたは１オブジェクト内の反復を見付ける符号化アルゴリズムを利用することしかできない。本発明は、任意のオブジェクト内、及び、パケット内符号化アルゴリズムに加えて、任意のオブジェクト間、パケット間、または、セッション間符号化アルゴリズムを利用することができる。つまり、データストリーム内のどこかに生じた長い間隔の空いた（即ち、多数の異なる、独立したパケット、オブジェクトまたはセッションにまたがる）反復を見付けるための符号化アルゴリズムを利用できる技術は、本発明だけである。本発明と共に用いることができるクロスセッションな符号化アルゴリズムの１つは、２００１年３月３１日に出願された「System and Method for Incremental and Continuous Data Compression」と題した米国特許出願第０９／８７２，１８４号明細書に記載されており、ここで参照することによりそのすべてが本明細書に取り込まれる。
【００３８】
本発明の他の実施形態では、符号化アルゴリズムは、ネットワークを介して伝送される複数のパケット間またはデータグラム間の何らかのデータブロックの反復を見付ける。これらの反復したデータブロックは、そのデータブロックの内容を一意に識別する一意の識別子で置き換えることにより、さらに効率的な形態に符号化される。この場合、符号化アルゴリズムは、複数のパケットにまたがる同一の２つのブロックデータを識別し、それらを高度に圧縮された形態に符号化する。この符号化アルゴリズムは、グローバルブロック符号化アルゴリズムと呼ばれる。グローバルブロック符号化アルゴリズムのブロックサイズは様々なサイズでよい。一実施形態では、このブロックサイズはそのパケットのペイロード全体と同じにすることができる。本発明の他の実施形態では、このブロックサイズは、任意の固定サイズ（例えば１００バイト）にすることもできるし、パケットごとに異なるサイズ（例えば、現在のパケットのペイロードの４分の１等）にすることもできる。
【００３９】
グローバルブロック符号化アルゴリズムは、署名関数を利用して同じデータブロックを識別する。署名関数は、ハッシュ関数とも呼ばれる。この符号化アルゴリズムは、ハッシュ関数を用い、データブロックの内容に基いてその特定データブロックの署名を計算する。次いで各データブロックの署名を過去に送信したデータブロックの署名と比較する。過去に送信したデータブロックに現在の署名と同じ署名を有するものが無かった場合、現在のデータブロックをデータブロックのテーブルに追加し、そのデータブロック全体を送信する（同期タグを付加する場合もある）。現在のデータブロックの署名と過去に送信されたデータブロックの署名が一致した場合、本発明は、現在のブロックの内容と、その同じ署名を有する過去のブロックの内容とを比較する。同じ署名を有する過去のブロックの内容が一致しない場合、現在のデータブロック全体を送信する（先と同様に）。現在のデータブロックの内容が過去のデータブロックの内容と一致する場合、そのデータブロックを特別な一意の識別子で置き換える。この置き換えは、符号化アルゴリズムが、復号アルゴリズムがこの特定の識別子にそのデータブロックの現在の内容そのものを関連付けていることを確信した場合にしか実施されない。２つのアルゴリズムがこの情報を共有していない場合、そのブロックを識別子で置き換えることはできない。この一意の識別子は、復号アルゴリズムによって元のデータブロックをパケットに置き換えるために使用される。このように、１以上の発信元から複数の類似したパケットあるいは同一のパケットが送信された場合、本発明は、ブロックまたはペイロード全体の伝送を省略することができるので、パケット内の反復だけを省略する場合よりも、多くの帯域幅を削減することができる可能性がある。
【００４０】
図５は、本発明の一実施形態によるグローバルブロック符号化アルゴリズムを示すフロー図である。例示の目的で、使用するブロックサイズはパケットのペイロード全体と同じにしてある。上記のように、ブロックサイズはペイロード全体のサイズである必要はなく、ペイロードのうちの固定数バイトでもよいし、可変数バイトでもよい。あるパケットのペイロードが反復しているか否かを判定する１つの方法は、そのペイロードのデータを既に送信された直前のＮパケットのデータと比較することである。従って、この処理はすべての入力パケットの各々について、ペイロード全体の比較を最大Ｎ回必要とする。このサーチ効率を向上させるため、この符号化アルゴリズムは、すべてのペイロードパケットの各々について特定の署名を確定的に生成する署名関数すなわちハッシュ関数を用いる。署名関数は、ペイロードのビットのうちの一部または全部を分析し、それらのビットに基いて署名を生成する。異なる署名を生成するためには２つのペイロードのうちの少なくとも１ビットが異なる必要があるので、２つのペイロードが異なる署名を有する場合、それら２つのペイロードは異なるものであることが保証される。２つのペイロードが同じ署名を有する場合、それらの異なるものであるか同じものであるかは、使用した署名関数すなわちハッシュ関数によって決まる。各署名値Ｓiについてのペイロードのリストは、標準チェーンのハッシュテーブルを用いて実現することができる。したがって、署名Ｓiを有するすべてのペイロードを検索するためには、プログラムはＳiに対応するハッシュテーブルのビンを見るだけでよい。
【００４１】
符号化アルゴリズム及び復号アルゴリズムは、最大でＮ個のペイロード（またはデータブロック）をローカルテーブルに保持する。このテーブル内の各項目（即ち、ペイロードまたはデータブロック）は、一意の識別番号で与えられる。例えば、これらの識別番号は１〜Ｎの整数とすることができる。符号化アルゴリズムは、ＬＲＵ（Least Recently Used)データ構造を用いることにより、最後のＮ個の一意のパケットのペイロードだけを自分のテーブル内に保持することができる。ＬＲＵは、リストをリンクさせたものや、その他適当なデータ構造によって実現することができる。
【００４２】
グローバルブロック符号化アルゴリズムの能力は、そのアルゴリズムが利用する署名関数によって決まる。署名関数がすべての一意のパケットの各々について完全に一意の署名を生成することができるものであれば、入力パケットの各々は、過去に送信されたパケットとほとんど一回しか比較されない。しかしながら、署名関数が多数のパケットに対して同じ署名を生成するものである場合、各パケットには複数回の比較が必要になる。例えば、署名関数を単にペイロードの最初のビットにした場合、送信されたすべてのパケットのうちの約半分は同じ署名を有する可能性がある。したがって、テーブルがＮ個の場合、各入力パケットついて約Ｎ／２回の比較が必要である。複雑な署名関数を用いるとペイロードの比較回数は少なくなるが、署名を作成するために必要な時間は長くなる。したがって２つの極限の間の優れたトレードオフを用いる必要がある。署名関数の一例としては、あらかじめ選択されたペイロード内のＭ個のランダム位置から取ったＭビットにすることができる。署名関数の他の例としては、ペイロード内のＭ個のランダム位置から取ったＭビットに対する１以上の２進関数とすることもできる。署名関数のさらに別の例としては、ペイロード内の全バイトまたはワードの合計とすることもできる。この署名関数すなわちハッシュ関数は、ペイロードのチェックサムに似ている。他にも多数の署名関数を用いることができる。署名関数によって返される最終的な署名はハッシュテーブルのビンの数よりも小さい数にすると便利であるが、必須ではない。この場合、署名は、単にハッシュテーブル内を索引付けし、同じ署名を生成したすべての過去のペイロードまたはデータブロックを検索するために用いることができる。最終的な署名がハッシュテーブルのビンの数よりも小さくなるようにするため、署名は、ビンの数を法として計算することもできる。
【００４３】
上記のように、符号化アルゴリズムと復号アルゴリズムとは、符号化されたパケットがすべてＤＤモジュール１０６によって実際に復号されるように、同期させる必要がある。グローバルブロック符号化アルゴリズムの場合、いずれの一意の識別子がいずれのデータブロックに対応するものであるかを示すテーブルも同期させる必要がある。符号化アルゴリズムは、テーブル識別番号Ｘを有するデータブロックが与えられても、復号アルゴリズム上のテーブル識別番号Ｘがそのデータブロックにちょうど対応するものであることを確信した場合にしか、そのデータブロックをそのテーブル識別番号Ｘで置き換えることができない。ＥＥモジュール１０４とＤＤモジュール１０６の間に用いるカプセル化プロトコルがＴＣＰのような信頼性の高い伝送プロトコルである場合（即ち、すべてのデータ配送が正しい順序で行なわれることを保証するプロトコルである場合）、２つのテーブルが全く同じパラメタ(例えばテーブルサイズ）を用いていることを確認することにより、それらを確実に同期させることができる。テーブルに記憶されるデータブロック及びＬＲＵに保持されるデータブロックは、それらが到着した順番に基いて選択されるので、符号化テーブルの状態はパケットが符号化アルゴリズムによって処理及び符号化される順番の関数になる。符号化されたパケットが同じ順番で復号アルゴリズムに配送されることを保証するため、２つのシステムは、それらの個々のテーブル及びＬＲＵが常に同期していること（例えば、テーブル及びＬＲＵの同じ位置に同じデータブロックが保持されること）を保証することができる。
【００４４】
図５及び図６は、信頼性の高い伝送プロトコルの使用に基づく符号化パケットのカプセル化を示すフロー図である。これらの図は、グローバルブロック符号化アルゴリズムのブロックサイズがパケットのペイロード全体であることも仮定している。
【００４５】
この符号化アルゴリズムを実施する場合、まず符号化アルゴリズムがデータパケットのストリームの中から次の入力パケットＰiを取り出す（５０２）。次いで符号化アルゴリズムは、そのＰiのペイロードについて署名を計算する（５０４）。符号化アルゴリズムは、Ｐiのペイロードを、同じ署名Ｓiを有する他のすべてのパケットのペイロードと比較する（５０６）。Ｐiのペイロードが他のパケットＰkのペイロードと同じである場合、ＰkをＬＲＵリストの前に移動する（５１０）。符号化アルゴリズムは、Ｐiのヘッダを出力バッファに書き込み（５１２）、特別な記号及びそれに続くＰkの識別番号を出力バッファに書き込む（５１４）。この特別な記号は、ペイロードがすでに送信されたパケットに属するようなヘッダを識別するものである。この特別な記号は、それを用いて復号アルゴリズムがペイロードが識別子で置き換えられたパケットを識別できるものであれば、いかなるインジケータでもよい。例えば、この特別な記号にはヘッダフィールド内の未使用ビットを用いることができ、ペイロードが識別子で置き換えられた場合はこれを「１」に設定し、ペイロードが変更されることなく送信された場合は「０」を設定する場合がある。パケットがカプセル化されているので、復号端でヘッダフィールドの変更を元に戻すことができる限り、ヘッダフィールドは変更してもよい。他の実施形態では、符号化及び復号アルゴリズムは、ペイロードが置き換えられているか否かに関わらず、すべてのパケットが識別子と共にペイロードの状態を示す固定長の特別なヘッダを有しているものと仮定する。この特別なヘッダには、任意の長さの固定長（例えば４バイト）のヘッダを用いることができ、ペイロードの開始に先立って直ちに配置される。ブロックサイズがペイロード全体よりも小さい場合、本発明は、この特別な識別ヘッダを各ブロックの前に挿入することができる。このような方法によると、過去に送信されたパケットがＬＲＵリスト上に存在する限り、同じペイロードを有するパケットは１回しか送信されない。そのデータパケットが処理され終わると、次に、符号化アルゴリズムは次の入力パケットを検査する。
【００４６】
ＰiのペイロードがＰkのペイロードと一致しない場合（５０８）、符号化アルゴリズムは、ＬＲＵの長さがＮであるか否かを判定する（５１６）。ＬＲＵの長さがＮパケットに等しい場合、符号化アルゴリズムはリスト内の最後のペイロードを消去する（５１８）。この最後のペイロードは最も古くに使用されたペイロードであるから、符号化アルゴリズムのテーブルから取り除き、新たなペイロードで置き換える。消去されたペイロードは、ハッシュテーブルからも取り除く。次いで、パケットＰiの新たなペイロードをＬＲＵの先頭に追加する（５２０）。最後のペイロードの消去が必要だった場合（即ち、ＬＲＵの長さがすでにＮであった場合）、新たな追加に用いられるテーブルエントリ番号は、ＬＲＵの最後から消去したテーブルエントリ番号である。何も消去が必要なかった場合はＬＲＵの長さがＮ未満であるから、テーブルエントリ番号は単に新たなペイロードを先頭に追加する前のＬＲＵの長さである。さらに、符号化アルゴリズムは、Ｐiのペイロードを署名Ｓiと共にペイロードのリストに追加する（５２２）。つまり、Ｐiのペイロードは、そのペイロードの署名に対応するハッシュテーブルのビンに入れられる。次いでＥＥモジュール１０４は、パケットＰi全体を出力バッファに書き込み（５２４）、次の入力パケットを検査する。
【００４７】
図６は、本発明の一実施形態による復号アルゴリズムにより実施される復号処理を示すフロー図である。この復号アルゴリズムは、入力バッファの中から次のパケットヘッダＨiを取り出す（６０２）。復号アルゴリズムは、そのヘッダの後に特別な記号が続いているか否かを判定する（６０４）。上記のように、この特別な記号には、ヘッダに設定された１ビットを用いることもできる。その場合、復号アルゴリズムはそのビットを検査した後、そのビットを元の状態に戻す。ヘッダの後に特別な記号が続いている場合、復号／分離構成要素２１０の復号アルゴリズムは、ペイロード識別番号Ｐkを読み出す（６０６）。復号アルゴリズムは、そのペイロードＰkをＬＲＵリストの前に移動する。次いで復号アルゴリズムは、ヘッダＨi及びペイロードＰkを有する新たなデータパケットを作成する（６１０）。復号アルゴリズムは、その新たなパケットをコネクションレスのネットワーク層に直接注入して送信する（６１２）。
【００４８】
次のパケットのヘッダの後に特別な記号が続いていない場合、ＤＤモジュール１０６は、そのヘッダの後にそのパケットの元のペイロードが続いているものと認識する。復号アルゴリズムはペイロードＰi全体を読み出す（６１６）。ＬＲＵの長さがＮである場合、復号アルゴリズムはＬＲＵリストの最後にあるペイロードを消去する（６２０）。例えば、復号アルゴリズムは反復したペイロードを探す必要がないので、すべてのペイロードのハッシュテーブルを保持している必要はない。従って、復号アルゴリズムによって何らかのペイロードが追加または消去された場合でも、ハッシュテーブルは全く更新する必要がない。次いで復号アルゴリズムは、ＰiをＬＲＵリストの先頭に追加する（６２２）。符号化アルゴリズムと同様に、ＬＲＵに新たに追加するためのテーブル番号は、ＬＲＵの最後から消去したペイロードのテーブル番号（ＬＲＵの長さがＮであった場合）、または、新たなペイロードを先頭に追加する前のＬＲＵの長さである。次いで復号アルゴリズムはパケット全体をネットワーク層に直接注入して送信する（６２４）。テーブルサイズ及びＬＲＵの長さが符号化アルゴリズムについても復号アルゴリズムについても同じであり、同じテーブル識別番号はいずれのアルゴリズムについても同じペイロードを指し示すので、これらのテーブルは確実に常に同期している。その理由は、この実施形態の場合、処理されたパケットが符号化アルゴリズムによって信頼性の高い伝送通信路にカプセル化されるからである。従って、符号化アルゴリズムによって処理されるペイロードの順番は復号アルゴリズムによって処理されるペイロードの順番と全く同じになる。これは、いずれのペイロードを記憶しいずれのペイロードを消去するかを判定するＬＲＵの符号化及び復号が常に確実に同期しているので、両方のアルゴリズムについて同じペイロードが追加及び消去されることを意味している。符号化アルゴリズムによって送信されたいかなるテーブル識別子も復号アルゴリズムで常に全く同じ元のペイロードを生成するということを保証する番号体系も同じになる。
【００４９】
上記の符号化アルゴリズム及び復号アルゴリズムは、信頼性の高い伝送通信路を用いることによって、それらのテーブルが確実に同期することを保証している。本発明の他の実施形態では、ＵＤＰ等の信頼性の無い伝送プロトコルを用いて符号化パケットをカプセル化する。この実施形態の場合、本発明は２つのテーブルを確実に同期させるための明示的な同期手段を用いることができる。この明示的な同期は、ＥＥモジュール１０４とＤＤモジュール１０６との間の信頼性の高い個別の伝送通信路を用い、テーブル同期メッセージを伝達する。この明示的同期には、符号化アルゴリズムから送信される各ペイロードに、そのペイロードの現在のステータスを復号アルゴリズムに示すためのステータスヘッダを付ける必要がある。例えば、符号化アルゴリズムが過去に見たことのない一意のペイロードを受信した場合を考える。この場合、図５で説明したように、符号化アルゴリズムはそのペイロードをテーブルに追加し、そのペイロードに一意のテーブル識別番号Ｙを付ける。しかしながら、そのペイロードを有するパケット全体を出力バッファに単に書き込む替わりに、符号化アルゴリズムは、それがテーブルの位置Ｙに今追加されたばかりの新たなペイロードであることを示すステータスヘッダをさらにそのパケットに付加する。この特別なヘッダには、ネットワークとパケットのペイロードとの間に常に配置される固定長の記号（例えば４バイト）を用いることができる。符号化アルゴリズムは、復号アルゴリズムがペイロードのインストールを完了してそのペイロードについての受領応答を返したか否かを示すテーブルに各エントリを有するフラグをさらに用いる。この「インストール」フラグは、そのペイロードが初めてテーブルに追加され、復号アルゴリズムに送信されるとき、０（即ち、偽）に設定される。復号アルゴリズムは、このパケットを受信すると、ステータス情報を用いてそのペイロードを復号テーブルの位置Ｙに配置する。次いで復号アルゴリズムは、位置Ｙにあるペイロードの受信及びインストールが完了したことを伝える受領応答を符号化アルゴリズムに返送する。このメッセージは、同期通信路をベースとする信頼性の高い個別の伝送路を介して送信される。符号化アルゴリズムは、この受領応答を受信すると、自分のテーブルエントリＹのローカルな「インストール」フラグを１（即ち、真）に設定する。これは、復号アルゴリズムがＹを全く同じペイロードとして逆参照できるので、このペイロードのその後のインスタンスは識別子Ｙで置き換えることができるということを、符号化アルゴリズムに示すものである。従って、符号化アルゴリズムで用いられる「インストール」フラグは、符号化アルゴリズムが符号化するすべてのパケットが復号アルゴリズムによって正しく復号できることを保証するものである。符号化アルゴリズムは、過去のペイロードと同じペイロードを見つけると、その過去のペイロードのインストールフラグをまずチェックする。インストールフラグが０の場合、そのペイロードの内容を送信し、そのペイロードは送信されたことがあるということを示すステータスフラグを符号化テーブルのテーブルエントリ番号Ｙに現在あるステータスフラグに追加する。インストールフラグが１の場合、そのペイロードがテーブルエントリ番号Ｙで置き換えられたことを示すようにステータスフラグを設定する。
【００５０】
カプセル化されたパケットの各々は信頼性の無い伝送プロトコルで伝送されるので、伝送中にカプセル化されたパケットが失われる可能性がある。この失われたパケットには、復号テーブルの位置Ｙに追加された新たなペイロードの最初のインスタンスが含まれる場合がある。その場合、復号アルゴリズムはそのペイロードを受信せず、それをテーブルに追加しないので、このペイロードについての受領確認は送信されない。この状況は、そのペイロードの次のインスタンスが符号化アルゴリズムによって受信されるときに対処することができる。次のインスタンスは、そのペイロードのインストールフラグが０のままになっているので、符号化アルゴリズムによって置き換えがなされない。しかしながら、次のインスタンスが失われない場合、復号アルゴリズムはその受信について受領応答を返すので、符号化アルゴリズムはそのペイロードのすべてのその後のインスタンスを識別子Ｙで置き換えできるようになる。
【００５１】
この暗示的テーブル同期方法には、他にも様々な変更を施して、さらに効率的にすることができる。例えば、テーブルエントリの数は限られているので（例えば１〜Ｎ）、テーブル番号Ｘのペイロードを消去することにより、番号Ｘを新たなペイロードを指すことに再利用できる。信頼性の無い伝送プロトコルは誤ったパケット配送をする可能性があるので、特定状況下でのテーブル番号の再利用は、符号化テーブルと復号テーブルとの非同期を引き起こす場合がある。この問題は、符号化テーブル及び復号テーブルにバージョン番号を付加することで回避することができる。このバージョン番号は、そのテーブルエントリを再利用できる時間を示すものである。従って、符号化アルゴリズムは、ペイロードが追加されたテーブルエントリを送信するだけでなく、この特定エントリのバージョン番号も送信しなければならない。復号アルゴリズムは、テーブル番号とバージョン番号との両方を用いることにより、符号化テーブルと復号テーブルが同期していることを保証することができる。
【００５２】
上記の暗示的テーブル同期方法は、テーブル参照の推測的伝送を可能にすることにより、さらに最適化することができる。この場合、所定時間の経過後、「インストール」フラグを０から１へ自動的に変換することができる。この時間は、ＥＥモジュール１０４とＤＤモジュール１０６との間のパケット配送時間のばらつきにほぼ対応する。符号化アルゴリズムは、復号アルゴリズムからの実際の受領応答を待つのではなく、（符号化アルゴリズムからカプセル化されたペイロードを送信した後）所定時間の経過後には、復号アルゴリズムによるペイロードのインストールが完了したものと推測する。この所定時間が経過した後、符号化アルゴリズムは、そのペイロードのその後のインスタンスのテーブル番号での置き換えを開始する。このペイロードが復号アルゴリズムによってインストールされていなかった場合（例えば、そのペイロードが失われた場合）、復号アルゴリズムは、その特定のテーブル及びバージョン番号が同期していないので復号アルゴリズムにより再送信すべきことを示すメッセージを返送することができる。この予測的実施形態により、本発明は、推測的でない明示的同期方法よりも早く特定のテーブル番号でのペイロードの置き換えを開始することができるようになる。これは、符号化アルゴリズムが復号アルゴリズムから戻ってくる受領応答を待つ必要がない替わりに、短時間の経過後にインストールフラグを１に設定するからである。
【００５３】
グローバルブロック符号化アルゴリズムについての上記の詳細な説明のすべて、及び、その複数テーブル同期方法は、任意のブロックサイズに適用することができる。上記の説明では、パケットのペイロードサイズに対応するブロックサイズを用いた。他の実施形態では、ブロックサイズを任意の他の固定サイズまたは可変サイズに設定することもできる。
【００５４】
好ましい実施形態及びいくつかの代替実施形態を参照して本発明を具体的に図示及び説明してきたが、当業者であれば、本発明の思想及び範囲から外れることなくその形態及び細部に様々な変更を施すことが可能であると考えられる。
【図面の簡単な説明】
【図１】  本発明を備えたネットワークを示す図である。
【図２】  本発明の一実施形態によるＥＥッモジュール及びＤＤモジュールを示す図である。
【図３ａ】  本発明の一実施形態によるＥＥモジュール及びＤＤモジュールによる処理を示す図である。
【図３ｂ】  本発明の一実施形態によるポイント・ツー・マルチポイントネットワークを示す図である。
【図４】  本発明の一実施形態によるデータストリームの符号化、カプセル化、復号及び分離の処理を示すフロー図である。
【図５】  本発明の一実施形態によるＥＥモジュールによって実施される符号化アルゴリズムを示すフロー図である。
【図６】  本発明の一実施形態によるＤＤモジュールによって実施される復号処理を示すフロー図である。
【図１】
0004564228.tif 000002
【図２】
0004564228.tif 000003
【図３ａ】
0004564228.tif 000004
【図３ｂ】
0004564228.tif 000005
【図４】
0004564228.tif 000006
【図５】
0004564228.tif 000007
【図６】
0004564228.tif 000008