(57)【特許請求の範囲】
【請求項１】
端末間で送受信されるデータを転送する転送装置であって、
プロセッサ、前記プロセッサに接続される主記憶装置、前記プロセッサに接続される副記憶装置、及び前記プロセッサに接続されるネットワークインタフェースを備え、
前記端末間のデータの転送処理を制御する転送制御部を有し、
ネットワークを介して他の転送装置と接続され、
前記副記憶装置は、データを分割することによって生成されるデータブロックであって、前記端末間で過去に送信されたデータブロックを管理するデータブロック情報を格納し、
前記主記憶装置は、前記データブロック情報に格納される前記データブロックを検索するための検索インデックスと、前記データブロックを一時的に保存するバッファとを格納し、
前記検索インデックスは、前記データブロックから算出された比較値及び前記データブロック情報に格納される前記データブロックへアクセスするためのポインタ値の組から構成される要素を複数含み、
前記データブロック情報は、前記ポインタ値及び前記データブロックから構成されるエントリを複数含み、
前記転送制御部は、
前記端末からデータを受信した場合、前記受信したデータから前記データブロックを生成するための分割処理を実行し、
前記分割処理によって生成された第１データブロックから、前記検索インデックスを参照するための検索値及び参照値を算出し、
前記参照値に基づいて、前記検索インデックスに含まれる複数の要素の中から参照する少なくとも一つの要素を特定し、
前記特定された少なくとも一つの要素に含まれる前記比較値と前記検索値とを比較することによって、前記第１データブロックが前記データブロック情報に格納されているか否かを判定し、
前記第１データブロックが前記データブロック情報に格納されていると判定された場合、前記第１データブロックの識別情報を前記他の転送装置に送信し、前記バッファに前記データブロックを保存し、前記他の転送装置から当該第１データブロックの転送完了を通知する応答を受信した後、前記バッファから前記第１データブロックを削除し、
前記第１データブロックが前記データブロック情報に格納されていないと判定された場合、前記第１データブロックの識別情報及び前記第１データブロックを前記他の転送装置に送信し、前記バッファに前記データブロックを保存し、前記他の転送装置から当該第１データブロックの転送完了を通知する応答を受信した後、前記データブロック情報に前記第１データブロックを格納し、前記バッファから前記第１データブロックを削除し、
前記第１データブロックの識別情報を送信した前記他の転送装置から、前記第１データブロックの送信を要求するデータブロック要求を受信した場合、前記バッファに保存される前記第１データブロックを前記他の転送装置に送信することを特徴とする転送装置。
【請求項２】
請求項１に記載の転送装置であって、
前記比較値及び前記検索値は、ハッシュ値であり、
前記転送制御部は、第１ハッシュ関数及び第２ハッシュ関数を保持し、
前記第１ハッシュ関数及び前記第１データブロックを用いて前記参照値を算出し、
前記第２ハッシュ関数及び前記第１データブロックを用いて前記検索値を算出し、
前記検索値及び前記参照値を前記第１データブロックの識別情報として送信し、
前記検索値が前記比較値と一致する場合、前記第１データブロックが前記データブロック情報に格納されると判定することを特徴とする転送装置。
【請求項３】
請求項２に記載の転送装置であって、
前記転送制御部は、
前記第１データブロックの識別情報及び前記第１データブロックを送信した前記他の転送装置から当該第１データブロックの格納完了を通知する応答を受信した場合、前記検索値及び前記参照値を用いて前記ポインタ値を算出し、
前記参照値に基づいて前記検索インデックスを参照して、値を設定する要素を一つ選択し、
前記選択された要素に、前記検索値及び前記算出されたポインタ値を設定し、
前記データブロック情報にエントリを追加し、
前記追加されたエントリに、前記算出されたポインタ値及び前記第１データブロックを格納することを特徴とする転送装置。
【請求項４】
端末間で送受信されるデータを転送する複数の転送装置を備えるネットワークシステムであって、
前記複数の転送装置の各々は、
プロセッサ、前記プロセッサに接続される主記憶装置、前記プロセッサに接続される副記憶装置、及び前記プロセッサに接続されるネットワークインタフェースを有し、
前記端末間のデータの転送処理を制御する転送制御部を有し、
前記副記憶装置は、データを分割することによって生成されるデータブロックであって、前記端末間で過去に送信されたデータブロックを管理するデータブロック情報を格納し、
前記主記憶装置は、前記データブロック情報に格納される前記データブロックを検索するための検索インデックスと、前記データブロックを一時的に保存するバッファとを格納し、
前記検索インデックスは、前記データブロックから算出された比較値及び前記データブロック情報に格納される前記データブロックへアクセスするためのポインタ値の組から構成される要素を複数含み、
前記データブロック情報は、前記ポインタ値及び前記データブロックから構成されるエントリを複数含み、
前記複数の転送装置は、第１検索インデックス及び第１データブロック情報を保持する第１転送装置、並びに、第２検索インデックス及び第２データブロック情報を保持する第２転送装置を含み、
前記第１転送装置は、
前記第１転送装置に接続する端末から送信データを受信した場合、前記送信データから前記データブロックを生成するための分割処理を実行し、
前記分割処理によって生成された第１データブロックから、前記検索インデックスを参照するための検索値と参照値を算出し、
前記参照値に基づいて、前記第１検索インデックスに含まれる複数の要素の中から参照する少なくとも一つの要素を特定し、
前記特定された少なくとも一つの要素に含まれる前記比較値と前記検索値とを比較することによって、前記第１データブロックが前記第１データブロック情報に格納されているか否かを判定し、
前記第１データブロックが前記第１データブロック情報に格納されていると判定された場合、前記検索値及び前記参照値を前記第１データブロックの識別情報として前記第２転送装置に送信し、前記バッファに前記データブロックを保存し、前記第２転送装置から当該第１データブロックの転送完了を通知する応答を受信した後、前記バッファから前記第１データブロックを削除し、
前記第１データブロックが前記第１データブロック情報に格納されていないと判定された場合、前記第１データブロックの識別情報及び前記第１データブロックを前記第２転送装置に送信し、前記バッファに前記データブロックを保存し、前記第２転送装置から当該第１データブロックの転送完了を通知する応答を受信した後、前記データブロック情報に前記第１データブロックを格納し、前記バッファから前記第１データブロックを削除し、
前記第１データブロックの識別情報を送信した前記第２転送装置から、前記第１データブロックの送信を要求するデータブロック要求を受信した場合、前記バッファに保存される前記第１データブロックを前記第２転送装置に送信し、
前記第２転送装置は、
前記第１データブロックの識別情報を受信した場合、前記参照値に基づいて、前記第２検索インデックスに含まれる複数の要素の中から参照する少なくとも一つの要素を特定し、
前記特定された少なくとも一つの要素に含まれる前記比較値と前記第１データブロックの識別情報に含まれる前記検索値とを比較することによって、前記第１データブロックが前記第２データブロック情報に格納されているか否かを判定し、
前記第１データブロックが前記第２データブロック情報に格納されていると判定された場合、前記第２データブロック情報から前記第１データブロックを読み出して、前記第１データブロックを前記第２転送装置に接続される端末に送信し、前記第１データブロックの転送完了を通知する応答を前記第１転送装置に送信し、
前記第１データブロックが前記第２データブロック情報に格納されていないと判定された場合、前記データブロック要求を前記第１転送装置に送信することを特徴とするネットワークシステム。
【請求項５】
請求項４に記載のネットワークシステムであって、
前記第１転送装置は、
第１ハッシュ関数及び第２ハッシュ関数を保持し、
前記第１ハッシュ関数及び前記第１データブロックを用いて前記参照値を算出し、
前記第２ハッシュ関数及び前記第１データブロックを用いて前記検索値を算出し、
前記検索値が前記比較値と一致する場合、前記第１データブロックが前記データブロック情報に格納されると判定することを特徴とするネットワークシステム。
【請求項６】
請求項５に記載のネットワークシステムであって、
前記第１転送装置は、
前記第１データブロックの識別情報及び前記第１データブロックを送信した前記第２転送装置から当該第１データブロックの格納完了を通知する応答を受信した場合、前記検索値及び前記参照値を用いて前記ポインタ値を算出し、
前記参照値に基づいて前記検索インデックスを参照して、値を設定する要素を一つ選択し、
前記選択された要素に、前記検索値及び前記算出されたポインタ値を設定し、
前記データブロック情報にエントリを追加し、
前記追加されたエントリに、前記算出されたポインタ値及び前記第１データブロックを格納することを特徴とするネットワークシステム。
【請求項７】
請求項５に記載のネットワークシステムであって、
前記第２転送装置は、
前記第１データブロック及び前記第１データブロックの識別情報を受信した場合、前記検索値及び前記参照値を用いて前記ポインタ値を算出し、
前記参照値に基づいて前記検索インデックスを参照して、値を設定する要素を選択し、
前記選択された要素に、前記検索値及び前記算出されたポインタ値を設定し、
前記データブロック情報にエントリを追加し、
前記追加されたエントリに、前記算出されたポインタ値及び前記第１データブロックを格納することを特徴とするネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの転送制御に関する。
【背景技術】
【０００２】
クラウドコンピューティングの普及によって、ネットワークを介してデータを利用する機会が増えている。【０００３】
ネットワーク帯域が制限されている場合、データへのアクセス時間がかかり、利用者の快適性が損なわれるという問題がある。また、同一のデータに対して繰り返し、アクセスが行われることによって、システム全体の通信量が増加し、ネットワーク帯域を圧迫するという問題もある。【０００４】
本技術分野の背景技術として、特許文献１に記載の技術が知られている。特許文献１には、通信データを転送する際に、ｐｅｒｓｉｓｔｅｎｔ  ｓｅｇｍｅｎｔ  ｓｔｏｒｅ  に保存されているセグメントをｒｅｆｅｒｅｎｃｅに置き換えて転送することが記載されている。【０００５】
また、特許文献２には、「ネットワークの利用度が利用度閾値に達したまたはこれを超過したときに、暗号化ハッシュ関数を適用して通信トラフィックにハッシュ・ダイジェストを組み込み、データの完全性点検およびデータの重複排除を提供し、これによって、送信側ネットワーク・デバイスと受信側ネットワーク・デバイスとの間で伝送されるデータの量を低減する」ことが開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許出願公開第２０１３／０２４６５０８号明細書
【特許文献２】特表２０１６−５１７５５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、ｐｅｒｓｉｓｔｅｎｔ  ｓｅｇｍｅｎｔ  ｓｔｏｒｅが大きい場合、主記憶装置に格納できないため、二次記憶装置に保存されるｐｅｒｓｉｓｔｅｎｔ  ｓｅｇｍｅｎｔ  ｓｔｏｒｅからセグメントを検索する必要がある。一般に、二次記憶装置はアクセス速度が遅いため、通信データの転送速度が遅くなる。
【課題を解決するための手段】
【０００８】
本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、端末間で送受信されるデータを転送する転送装置であって、プロセッサ、前記プロセッサに接続される主記憶装置、前記プロセッサに接続される副記憶装置、及び前記プロセッサに接続されるネットワークインタフェースを備え、前記端末間のデータの転送処理を制御する転送制御部を有し、ネットワークを介して他の転送装置と接続され、前記副記憶装置は、データを分割することによって生成されるデータブロックであって、前記端末間で過去に送信されたデータブロックを管理するデータブロック情報を格納し、前記主記憶装置は、前記データブロック情報に格納される前記データブロックを検索するための検索インデックスと、前記データブロックを一時的に保存するバッファとを格納し、前記検索インデックスは、前記データブロックから算出された比較値及び前記データブロック情報に格納される前記データブロックへアクセスするためのポインタ値の組から構成される要素を複数含み、前記データブロック情報は、前記ポインタ値及び前記データブロックから構成されるエントリを複数含み、前記転送制御部は、前記端末からデータを受信した場合、前記受信したデータから前記データブロックを生成するための分割処理を実行し、前記分割処理によって生成された第１データブロックから、前記検索インデックスを参照するための検索値及び参照値を算出し、前記参照値に基づいて、前記検索インデックスに含まれる複数の要素の中から参照する少なくとも一つの要素を特定し、前記特定された少なくとも一つの要素に含まれる前記比較値と前記検索値とを比較することによって、前記第１データブロックが前記データブロック情報に格納されているか否かを判定し、前記第１データブロックが前記データブロック情報に格納されていると判定された場合、前記第１データブロックの識別情報を前記他の転送装置に送信し、前記バッファに前記データブロックを保存し、前記他の転送装置から当該第１データブロックの転送完了を通知する応答を受信した後、前記バッファから前記第１データブロックを削除し、前記第１データブロックが前記データブロック情報に格納されていないと判定された場合、前記第１データブロックの識別情報及び前記第１データブロックを前記他の転送装置に送信し、前記バッファに前記データブロックを保存し、前記他の転送装置から当該第１データブロックの転送完了を通知する応答を受信した後、前記データブロック情報に前記第１データブロックを格納し、前記バッファから前記第１データブロックを削除し、前記第１データブロックの識別情報を送信した前記他の転送装置から、前記第１データブロックの送信を要求するデータブロック要求を受信した場合、前記バッファに保存される前記第１データブロックを前記他の転送装置に送信することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、検索インデックスを用いることによって、データブロックの検索を高速に行うことができる。前述した以外の課題、構成及び効果は、以下の実施例の説明によって明らかにされる。
【図面の簡単な説明】
【００１０】
【図１】実施例１のネットワークシステムの構成例を示す図である。
【図２】実施例１の転送装置のハードウェア構成及びソフトウェア構成の一例を示す図である。
【図３】実施例１の転送装置のソフトウェア構成の論理的な接続関係を示す図である。
【図４】実施例１の転送装置がＬＡＮを介して送受信するＴＣＰパケットのフォーマットの一例を示す図である。
【図５】実施例１の転送装置がＷＡＮを介して送受信するＴＣＰパケットのフォーマットの一例を示す図である。
【図６】実施例１のフロー情報の一例を示す図である。
【図７】実施例１の送信検索インデックスの一例を示す図である。
【図８】実施例１の送信データブロック情報の一例を示す図である。
【図９Ａ】実施例１のデータ転送処理の流れを説明するシーケンス図である。
【図９Ｂ】実施例１のデータ転送処理の流れを説明するシーケンス図である。
【図９Ｃ】実施例１のデータ転送処理の流れを説明するシーケンス図である。
【図１０】実施例１の転送制御部がＬＡＮからデータを受信した場合に実行する処理を説明するフローチャートである。
【図１１】実施例１の転送制御部がデータ分割部から応答を受け取った場合に実行する処理を説明するフローチャートである。
【図１２】実施例１の転送制御部がタイマに設定された時間が経過した場合に実行する処理を説明するフローチャートである。
【図１３】実施例１の転送制御部が他の転送装置から応答を受信した場合に実行する処理を説明するフローチャートである。
【図１４】実施例１のデータ分割部が実行する処理を説明するフローチャートである。
【図１５】実施例１の重複排除部が転送制御部によって呼び出された場合に実行する処理を説明するフローチャートである。
【図１６】実施例１の重複排除部が転送制御部から更新指示を受け付けた場合に実行する処理を説明するフローチャートである。
【図１７】実施例１の転送制御部がＷＡＮからデータを受信した場合に実行する処理を説明するフローチャートである。
【図１８】実施例１の重複復元部が転送制御部によって呼び出された場合に実行する処理を説明するフローチャートである。
【図１９】実施例１の重複排除部が実行する処理の具体例を示す図である。
【図２０】実施例２の転送装置のハードウェア構成及びソフトウェア構成の一例を示す図である。
【図２１】実施例２の転送装置のソフトウェア構成の論理的な接続関係を示す図である。
【図２２】実施例２のフロー情報の一例を示す図である。
【図２３】実施例２のデータの分割方法の概念を示す図である。
【図２４】実施例２の副検索インデックスの一例を示す図である。
【図２５】実施例２の転送制御部がＬＡＮからデータを受信した場合に実行する処理を説明するフローチャートである。
【図２６】実施例２の重複排除部が転送制御部から副データブロックの検出指示を受け付けた場合に実行する処理を説明するフローチャートである。
【図２７】実施例２の重複排除部が転送制御部によって呼び出された場合に実行する処理を説明するフローチャートである。
【発明を実施するための形態】
【００１１】
以下、添付図面を参照して本発明の実施例を説明する。各図において共通の構成については同一の参照符号が付されている。
【実施例１】
【００１２】
実施例１では、本発明の基本的な一例として、転送装置が、二次記憶装置に格納されるデータブロック情報からデータブロックを高速に検索する転送制御方法を説明する。これによって、データの高速な転送を実現できる。本実施例では、ＴＣＰ／ＩＰ通信におけるデータ転送を一例として示す。ただし、本発明は、データ転送に用いる通信プロトコルに限定されない。【００１３】
図１は、実施例１のネットワークシステムの構成例を示す図である。【００１４】
ネットワークシステムは、複数の端末１００、複数の転送装置１１０、及び各装置を接続するネットワークから構成される。なお、本発明は、ネットワークシステムに含まれる装置及びネットワークの数には限定されない。【００１５】
端末１００及び転送装置１１０は、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）１４０を介して互いに接続される。また、複数の転送装置１１０は、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）を介して互いに接続される。各ネットワークの接続方式は、無線及び有線のいずれもよい。ＬＡＮ１４０及びＷＡＮ１２０には、中継装置１３０が一つ以上含まれる。【００１６】
なお、各装置を接続するネットワークの種別に限定されず、専用回線及びインターネット等のネットワークでもよい。また、端末１００及び転送装置１１０は、直接接続されてもよい。複数の転送装置１１０は、直接接続されてもよい。【００１７】
図１では、二つの端末１００−１、１００−２が、ＬＡＮ１４０−１、１４０−２、転送装置１１０−１、１１０−２、及びＷＡＮ１２０を介して、互いに通信を行う。【００１８】
端末１００は、通信を行う装置である。端末１００は、物理計算機及びプロキシ装置等が考えられる。端末１００は、図示しない演算装置、主記憶装置、及びネットワークインタフェースを有する。なお、端末１００は、仮想計算機を用いて実現してもよい。【００１９】
中継装置１３０は、ＬＡＮ１４０及びＷＡＮ１２０等のネットワークを構成する装置であり、スイッチ、ルータ、及びゲートウェイ装置等が考えられる。中継装置１３０は、図示しない演算装置、主記憶装置、及びネットワークインタフェースを有する。【００２０】
転送装置１１０は、端末１００間のＴＣＰ通信の終端及び中継を行う装置であり、端末１００間で送受信されるデータを転送する。本実施例の転送装置１１０は、フロー単位で通信を制御するものとする。【００２１】
端末１００−１と端末１００−２との間のＴＣＰ通信１５０において、転送装置１１０−１は、ＴＣＰ通信１５０を終端し、ＬＡＮ１４０−１を介して端末１００−１との間でＴＣＰ通信１５１を行う。なお、ＴＣＰ通信１５１では、転送装置１１０−１は、ＴＣＰ通信１５０において端末１００−２が用いるＩＰアドレス及びポート番号を、転送装置１１０−１のＩＰアドレス及びポート番号として用いる。同様に、ＴＣＰ通信１５０において、転送装置１１０−２は、ＴＣＰ通信１５０を終端し、ＬＡＮ１４０−２を介して端末１００−２とＴＣＰ通信１５３を行う。ＴＣＰ通信１５３では、転送装置１１０−２は、ＴＣＰ通信１５０において端末１００−１が用いるＩＰアドレス及びポート番号を、転送装置１１０−２のＩＰアドレス及びポート番号として用いる。【００２２】
また、転送装置１１０−１及び転送装置１１０−２は、ＷＡＮ１２０を介して、ＴＣＰ通信１５２を行う。ＴＣＰ通信１５２では、転送装置１１０−１は、端末１００−１のＩＰアドレス及びポート番号を用い、また、転送装置１１０−２は、端末１００−２のＩＰアドレス及びポート番号を用いる。【００２３】
前述のようなＴＣＰ通信によって、端末１００−１及び端末１００−２は、端末１００間で直接通信するＴＣＰ通信１５０を行っている場合と同様の動作を行う。【００２４】
また、本実施例の転送装置１１０は、重複したデータの転送を排除するように通信を制御する。具体的には、転送装置１１０は、送信したデータ及び受信したデータを格納する情報を管理する。転送元の端末１００から過去に送信されたデータと同一のデータを受信した場合、転送装置１１０は当該データの識別情報を送信する。データの識別情報を受信した場合、転送装置１１０は、当該データの識別情報に一致するデータを情報から読み出し、転送先の端末１００に読み出されたデータを送信する。【００２５】
前述したようなデータの転送制御を行うことによって、ＷＡＮ１２０へのデータ転送量が削減される。したがって、通信コストの削減及び端末１００間の通信速度の高速化を実現できる。【００２６】
以下の説明では、ネットワークシステム内で過去に送信されたデータと同一のデータの転送を排除する処理を「重複排除」とも記載する。また、以下の説明では、ネットワークシステム内で過去に送信されたデータを転送装置１１０が管理する情報から取得する処理を「重複復元」とも記載する。【００２７】
図２は、実施例１の転送装置１１０のハードウェア構成及びソフトウェア構成の一例を示す図である。図３は、実施例１の転送装置１１０のソフトウェア構成の論理的な接続関係を示す図である。【００２８】
転送装置１１０は、演算装置２０１、主記憶装置２０２、二次記憶装置２０３、及び複数のネットワークインタフェース２０４を有する。転送装置１１０が有するハードウェアは、システムバス２０５を介して互いに接続され、システムバス２０５を介して互いに通信を行う。【００２９】
なお、転送装置１１０が有する各ハードウェアの数は二つ以上でもよい。また、各ハードウェアは、複数のシステムバス２０５を介して、互いに接続されてもよい。また、各ハードウェアは、直接接続されてもよい。【００３０】
なお、前述したハードウェアは、仮想的なハードウェアを用いて実現してもよい。例えば、一つのネットワークインタフェース２０４上に複数の論理的なネットワークインタフェースを構成し、論理的なネットワークインタフェースを用いることもできる。【００３１】
なお、転送装置１１０は、入出力装置を有してもよい。入出力装置には、キーボード、マウス、タッチパネル、及びディスプレイ等が含まれる。【００３２】
演算装置２０１は、主記憶装置２０２に格納されるプログラムを実行する。演算装置２０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）及びＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等が考えられる。演算装置２０１がプログラムを実行することによって転送装置１１０が有する機能を実現できる。以下の説明では、機能部（モジュール）を主語に処理を説明する場合、演算装置２０１が当該機能部を実現するプログラムを実行していることを示す。【００３３】
主記憶装置２０２は、演算装置２０１が実行するプログラム及び当該プログラムによって使用される情報を格納する。主記憶装置２０２は、また、プログラムが使用するワークエリア及びバッファ等の一時記憶領域を含む。主記憶装置２０２は、メモリ等が考えられる。【００３４】
二次記憶装置２０３は、永続的にデータを格納する。また、二次記憶装置２０３は、主記憶装置２０２に格納できないデータを格納する一時記憶領域を含む。二次記憶装置２０３は、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）及びＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等が考えられる。【００３５】
主記憶装置２０２に格納されるプログラム及び情報は、二次記憶装置２０３に格納されてもよい。この場合、演算装置２０１は、二次記憶装置２０３から、プログラム及び情報を読み出し、主記憶装置２０２にプログラム及び情報をロードする。【００３６】
ネットワークインタフェース２０４は、ネットワークと接続するためのインタフェースである。本実施例では、転送装置１１０は、ネットワークインタフェース２０４−１を介してＬＡＮ１４０と接続し、また、ネットワークインタフェース２０４−２を介してＷＡＮ１２０と接続する。【００３７】
ここで、主記憶装置２０２及び二次記憶装置２０３に格納されるプログラム及び情報に吹いて説明する。【００３８】
主記憶装置２０２は、プログラムとして、重複排除部２１１、重複復元部２１２、転送制御部２１３、プロトコル処理部２１４、及びデータ分割部２１５を実現するプログラムを格納する。主記憶装置２０２は、情報として、フロー情報２１７、送信検索インデックス２１８、及び受信検索インデックス２１９を格納する。また、主記憶装置２０２は、一時記憶領域としてデータブロックバッファ２１６を含む。【００３９】
二次記憶装置２０３は、送信データブロック情報２２０及び受信データブロック情報２２１を格納する。【００４０】
フロー情報２１７は、フローを管理するための情報である。フロー情報２１７の詳細は、図６を用いて説明する。【００４１】
送信データブロック情報２２０は、重複排除を行う場合に使用されるデータブロックを格納する。受信データブロック情報２２１は、重複復元を行う場合に使用されるデータブロックを格納する。送信データブロック情報２２０及び受信データブロック情報２２１の詳細は、図８を用いて説明する。【００４２】
送信検索インデックス２１８は、送信データブロック情報２２０に格納されるデータブロックを検索する場合に使用されるインデックスである。受信検索インデックス２１９は、受信データブロック情報２２１に格納されるデータブロックを検索する場合に使用されるインデックスである。送信検索インデックス２１８及び受信検索インデックス２１９の詳細は、図７を用いて説明する。【００４３】
データブロックバッファ２１６は、データブロックを一時的に格納する記憶領域である。【００４４】
転送制御部２１３は、転送装置１１０全体を制御する。転送制御部２１３は、内部変数として更新フラグを保持する。転送制御部２１３は、ネットワークインタフェース２０４−１を介してＬＡＮ１４０からデータを受信した場合、重複排除部２１１及びデータ分割部２１５等と連携して、重複排除を行い、ネットワークインタフェース２０４−２を介してＷＡＮ１２０にデータを転送する。転送制御部２１３は、ネットワークインタフェース２０４−２を介してＷＡＮ１２０からデータを受信した場合、重複復元部２１２等と連携して、重複復元を行い、ネットワークインタフェース２０４−１を介してＬＡＮ１４０にデータを転送する。転送制御部２１３が実行する処理の詳細は後述する。【００４５】
プロトコル処理部２１４は、ネットワークインタフェース２０４を管理し、所定の通信プロトコルに基づく通信処理を実行する。本実施例の通信プロトコルは、ＴＣＰ／ＩＰプロトコルである。また、プロトコル処理部２１４は、アプリケーション等に対して通信を行うためのＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）を提供する。例えば、プロトコル処理部２１４は、送信アドレス及び送信ポート、並びに受信アドレス及び受信ポートを転送制御部２１３に通知する。また、プロトコル処理部２１４は、ネットワークインタフェース２０４を介してデータを受信した場合、転送制御部２１３にデータを出力し、転送制御部２１３からデータを受信した場合、ネットワークインタフェース２０４を介してデータをネットワークに送信する。【００４６】
なお、プロトコル処理部２１４は、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）に含まれるＴＣＰ／ＩＰ機能として実現されてもよいし、専用のプログラムとして実現されてもよい。【００４７】
データ分割部２１５は、所定の分割方法（プロトコル）に基づいて、データを分割することによって複数のデータブロックを生成する。データ分割部２１５が実行する処理の詳細は後述する。【００４８】
重複排除部２１１は、送信検索インデックス２１８を用いて重複排除を行う。また、重複排除部２１１は、送信検索インデックス２１８及び送信データブロック情報２２０を管理する。重複排除部２１１が実行する処理の詳細は後述する。【００４９】
重複復元部２１２は、受信検索インデックス２１９を用いて重複復元を行う。また、重複復元部２１２は、受信検索インデックス２１９及び受信データブロック情報２２１を管理する。重複復元部２１２が実行する処理の詳細は後述する。【００５０】
なお、重複排除部２１１は、第１ハッシュ関数及び第２ハッシュ関数を保持する。ハッシュ関数は、例えば、ｍｄ５及びｓｈａ１等が考えられる。【００５１】
なお、前述した各機能部は、複数の機能部を一つの機能部に集約してもよいし、また、一つの機能部を複数の機能部に分割してもよい。例えば、重複排除部２１１、重複復元部２１２、及びデータ分割部２１５を、転送制御部２１３に集約してもよい。【００５２】
なお、前述した各機能部は、ソフトウェアとして実現されているが、こられの機能の一部又は全てを演算装置２０１及びネットワークインタフェース２０４等のハードウェアを用いて実現されてもよい。【００５３】
本実施例では、送信検索インデックス２１８及び受信検索インデックス２１９を主記憶装置２０２に格納することによって、データブロックの検索処理を高速に行うことができる。また、後述するように、送信検索インデックス２１８及び受信検索インデックス２１９のデータ構造を工夫することによって、検索処理の高速化及び検索精度の向上を実現できる。【００５４】
次に、図４及び図５を用いてＴＣＰ通信に使用されるＴＣＰパケットについて説明する。【００５５】
図４は、実施例１の転送装置１１０がＬＡＮ１４０を介して送受信するＴＣＰパケット４００のフォーマットの一例を示す図である。【００５６】
ＴＣＰパケット４００は、ＭＡＣヘッダ４１０、ＩＰヘッダ４２０、ＩＰオプションヘッダ４３０、ＴＣＰヘッダ４４０、ＴＣＰオプションヘッダ４５０、及びＴＣＰペイロード４６０を含む。【００５７】
ＭＡＣヘッダ４１０は、ＤＭＡＣ４１１、ＳＭＡＣ４１２、ＴＰＩＤ４１３、ＴＣＩ４１４、及びＴｙｐｅ４１５を含む。ＤＭＡＣ４１１は、宛先ＭＡＣアドレスを表す。ＳＭＡＣ４１２は、送信元ＭＡＣアドレスを表す。ＴＰＩＤ４１３は、タグ付きフレームであること及びタグの種類を表す。ＴＣＩ４１４は、タグの情報を表す。Ｔｙｐｅ４１５は、ＭＡＣフレームタイプを表す。【００５８】
ＴＣＩ４１４は、さらに、ＰＣＰ４１６、ＣＦＩ４１７、及びＶＩＤ４１８を含む。ＰＣＰ４１６は優先度を表す。ＣＦＩ４１７は、ＭＡＣアドレスが正規フォーマットであるかを表す。ＶＩＤ４１８は、ＶＬＡＮのＩＤを表す。なお、ＶＬＡＮが使用されていないネットワークの場合、ＴＰＩＤ４１３及びＴＣＩ４１４は存在しない。この場合、転送装置１１０は、ＶＩＤ４１８が「０」であるものとして処理を行う。【００５９】
ＩＰヘッダ４２０は、ＩＰ  ｌｅｎｇｔｈ４２１、ｐｒｏｔｏｃｏｌ４２２、ＳＩＰ４２３、及びＤＩＰ４２４を含む。ＩＰ  ｌｅｎｇｔｈ４２１は、ＭＡＣヘッダ４１０を除くパケット長を表す。ｐｒｏｔｏｃｏｌ４２２は、プロトコル番号を表す。ＳＩＰ４２３は、送信元ＩＰアドレスを表す。ＤＩＰ４２４は、宛先ＩＰアドレスを表す。【００６０】
ＩＰオプションヘッダ４３０は、０又は複数のＩＰオプション情報４３１を含む。【００６１】
ＴＣＰヘッダ４４０は、ｓｒｃ．ｐｏｒｔ４４１、ｄｓｔ．ｐｏｒｔ４４２、ＳＥＱ４４３、ＡＣＫ４４４、ｆｌａｇ４４５、ｔｃｐ  ｈｌｅｎ４４６、及びｗｉｎ＿ｓｉｚｅ４４７を含む。ｓｒｃ．ｐｏｒｔ４４１は、送信元ポート番号を表す。ｄｓｔ．ｐｏｒｔ４４２は、宛先ポート番号を表す。ＳＥＱ４４３は、送信シーケンス番号を表す。ＡＣＫ４４４は、受信シーケンス番号を表す。ｆｌａｇ４４５は、ＴＣＰフラグ番号を表す。ｔｃｐ  ｈｌｅｎ４４６は、ＴＣＰのヘッダ長を表す。ｗｉｎ＿ｓｉｚｅ４４７は、対向装置へ通知する広告ウインドウサイズを表す。【００６２】
ＴＣＰオプションヘッダ４５０は、０又は複数のオプションを含む。例えば、ｏｐｔｉｏｎ  ｋｉｎｄ４５１、ｏｐｔｉｏｎ  ｌｅｎｇｔｈ４５２、及びオプション情報４５３等のオプションが含まれる。ｏｐｔｉｏｎ  ｋｉｎｄ４５１は、オプションの種別を表す。ｏｐｔｉｏｎ  ｌｅｎｇｔｈ４５２は、オプション長を表す。オプション情報４５３は、オプションの種類に応じた情報を表す。【００６３】
図５は、実施例１の転送装置１１０がＷＡＮ１２０を介して送受信するＴＣＰパケット５００のフォーマットの一例を示す図である。【００６４】
ＴＣＰパケット５００は、ＴＣＰパケット４００と同様にＭＡＣヘッダ４１０、ＩＰヘッダ４２０、ＩＰオプションヘッダ４３０、ＴＣＰヘッダ４４０、及びＴＣＰオプションヘッダ４５０を含む。さらに、ＴＣＰパケット５００は、符号化されたデータ部分に対応するＤｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０の組を一つ以上含む。【００６５】
ＴＣＰパケット５００に含まれるＭＡＣヘッダ４１０、ＩＰヘッダ４２０、ＴＣＰヘッダ４４０、及びＴＣＰオプションヘッダ４５０は、ＴＣＰパケット４００に含まれるものと同一である。ＴＣＰパケット５００に含まれるＩＰオプションヘッダ４３０には、オプション情報の一つとしてＤｅｄｕｐ５０１を含む。Ｄｅｄｕｐ５０１は、転送装置１１０によって重複排除が行われたパケットであることを表す。【００６６】
Ｄｅｄｕｐヘッダ５１０は、ｄｅｄｕｐ．ｔｙｐｅ５１１、ｄｅｄｕｐ．ｄａｔａ＿ｌｅｎ５１２、ｄｅｄｕｐ．ｈａｓｈ１  ５１３、及びｄｅｄｕｐ．ｈａｓｈ２  ５１４を含む。Ｄｅｄｕｐヘッダ５１０に含まれる各情報のデータサイズは、一例であって、必要に応じてデータサイズを変更できる。【００６７】
ｄｅｄｕｐ．ｔｙｐｅ５１１は、Ｄｅｄｕｐペイロード５２０の種類を表す。ｄｅｄｕｐ．ｄａｔａ＿ｌｅｎ５１２は、Ｄｅｄｕｐペイロード５２０の長さを表す。ｄｅｄｕｐ．ｈａｓｈ１  ５１３及びｄｅｄｕｐ．ｈａｓｈ２  ５１４は、データブロックを検索するために用いるハッシュ値を表す。本実施例では、ｄｅｄｕｐ．ｈａｓｈ１  ５１３及びｄｅｄｕｐ．ｈａｓｈ２  ５１４が、データブロックの識別情報として用いられる。【００６８】
なお、ｄｅｄｕｐ．ｔｙｐｅ５１１には「１」、「２」、「３」のいずれかが設定される。「１」は、データブロックの識別情報のみを含むＴＣＰパケット５００であることを示す。「２」は、データブロック及びデータブロックの識別情報を含むＴＣＰパケット５００であることを示す。「３」は、分割されなかったデータを含むＴＣＰパケット５００であることを示す。【００６９】
Ｄｅｄｕｐペイロード５２０は、Ｄｅｄｕｐ．ｔｙｐｅ５１１の値に応じて、データブロック又はＬＡＮ１４０から受信したデータ等が格納される。なお、データブロックの識別情報を送信する場合、空のＤｅｄｕｐペイロード５２０が付与されてもよいし、Ｄｅｄｕｐペイロード５２０が付与されなくてもよい。【００７０】
次に、図６、図７、及び図８を用いて、転送装置１１０が管理する情報等について説明する。【００７１】
図６は、実施例１のフロー情報２１７の一例を示す図である。【００７２】
フロー情報２１７は、フローを管理する情報を格納するエントリを含む。エントリは、フローＩＤ６０１、ＶＬＡＮ６０２、ＬＡＮ−ＩＰ６０３、ＷＡＮ−ＩＰ６０４、ＬＡＮ−ＰＯＲＴ６０５、ＷＡＮ−ＰＯＲＴ６０６、バッファ６０７、及びタイマ６０８から構成される。【００７３】
フローＩＤ６０１は、フローを一意に識別するための識別情報である。ＶＬＡＮ６０２は、フローが属するＶＬＡＮの識別情報である。ＬＡＮ−ＩＰ６０３及びＬＡＮ−ＰＯＲＴ６０５は、ＬＡＮ１４０を介して接続される端末１００のＩＰアドレス及びポート番号である。ＷＡＮ−ＩＰ６０４及びＷＡＮ−ＰＯＲＴ６０６は、ＷＡＮ１２０を介して接続される端末１００のＩＰアドレス及びポート番号である。バッファ６０７は、ＬＡＮ１４０から受信したデータをＷＡＮ１２０に転送する場合に、一時的にデータを格納するための領域である。タイマ６０８は、データ転送に用いるタイマ値である。【００７４】
図７は、実施例１の送信検索インデックス２１８の一例を示す図である。なお、受信検索インデックス２１９のデータ構造は、送信検索インデックス２１８と同一であるため、説明を省略する。【００７５】
送信検索インデックス２１８は、２次元配列のデータ構造である。図７では、Ｎ行４列の２次元配列となっている。なお、行及び列の数は一例であって、任意の値に設定できる。【００７６】
２次元配列の一つの要素７０１には、ハッシュ値Ｘ及びポインタ値Ｐが含まれる。ハッシュ値Ｘは、ハッシュ関数にデータブロックを入力することによって算出されるハッシュ値である。ハッシュ値Ｘは、データブロックが送信データブロック情報２２０に格納されているか否かを判定する場合に使用される。ポインタ値は、送信データブロック情報２２０内のデータブロックをアクセスするための値である。ポインタ値には、後述するファイル名８０１の値が設定される。【００７７】
後述するように、重複排除部２１１は、二つのハッシュ関数を用いて、送信検索インデックス２１８を参照する。【００７８】
図８は、実施例１の送信データブロック情報２２０の一例を示す図である。なお、受信データブロック情報２２１のデータ構造は、送信データブロック情報２２０と同一であるため、説明を省略する。【００７９】
送信データブロック情報２２０は、データブロックを格納するエントリを含む。エントリは、ファイル名８０１及びデータブロック８０２から構成される。本実施例では、個々のデータブロックがファイルとして管理される。【００８０】
ファイル名８０１は、データブロックを管理するファイルの識別情報である。本実施例では、ファイルの識別情報に数値を用いる。データブロック８０２は、データブロックそのものである。【００８１】
次に、図９Ａ、図９Ｂ、及び図９Ｃを用いて、データ転送処理の一連の流れについて説明する。以下では、一例として、端末１００−１から端末１００−２へデータを転送する場合のデータ転送処理について説明する。なお、端末１００−２から端末１００−２へデータを転送する場合も同様の処理となる。【００８２】
図９Ａ、図９Ｂ、及び図９Ｃは、実施例１のデータ転送処理の流れを説明するシーケンス図である。なお、ＴＣＰ通信における確認応答等のＴＣＰレイヤの処理については省略している。【００８３】
図９Ａは、転送装置１１０−１及び転送装置１１０−２が、端末１００−１から送信されるデータ（データブロック）を保持している場合のデータ転送処理の流れを示す。【００８４】
端末１００−１が端末１００−２へデータを送信する（ステップＳ９０１）。【００８５】
転送装置１１０−１は、ＬＡＮ１４０−１を介して、端末１００−１からデータを受信した場合、当該データをデータブロックに分割する（ステップＳ９０２）。転送装置１１０−１は、データブロックのハッシュ値に基づいて送信検索インデックス２１８を検索し、データブロックが送信データブロック情報２２０に格納されているか否かを判定する（ステップＳ９０３）。【００８６】
データブロックは送信データブロック情報２２０に格納されているため、転送装置１１０−１は、ＷＡＮ１２０を介して、端末１００−２にデータブロックの識別情報を送信する（ステップＳ９０４）。このとき、転送装置１１０−１は、データブロックバッファ２１６にデータブロックを格納する。【００８７】
転送装置１１０−２は、データブロックの識別情報を受信した場合、データブロックの識別情報に基づいて受信検索インデックス２１９を検索し、データブロックが受信データブロック情報２２１に格納されているか否かを判定する（ステップＳ９０５）。【００８８】
データブロックは受信データブロック情報２２１に格納されているため、転送装置１１０−２は、ＷＡＮ１２０を介して、転送装置１１０−１に復元確認通知を送信する（ステップＳ９０６）。なお、復元確認通知は、データブロックの転送が完了した旨を示す通知である。【００８９】
また、転送装置１１０−２は、データブロックの識別情報に基づいて受信データブロック情報２２１からデータブロックを取得し、ＬＡＮ１４０−２を介して、端末１００−２に取得されたデータブロックを端末１００−１から送信されたデータとして送信する（ステップＳ９０７）。【００９０】
転送装置１１０−１は、ＷＡＮ１２０を介して、復元確認通知を受信した場合、データブロックバッファ２１６に格納されるデータブロックを削除する（ステップＳ９０８）。【００９１】
なお、端末１００−１から受信したデータは複数のデータブロックに分割される。したがって、転送装置１１０−１は、Ｄｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０の組を一つ以上含むＴＣＰパケット５００の送信を一回以上行う。また、転送装置１１０−２は、データブロックを送信する場合、複数のデータブロックを含む一つのＴＣＰパケット４００を送信してもよいし、一つのデータブロックを含むＴＣＰパケット４００を複数回送信してもよい。【００９２】
図９Ｂは、転送装置１１０−１が、端末１００−１から送信されるデータ（データブロック）を保持していない場合のデータ転送処理の流れを示す。【００９３】
端末１００−１が端末１００−２へデータを送信する（ステップＳ９１１）。【００９４】
転送装置１１０−１は、ＬＡＮ１４０−１を介して、端末１００−１からデータを受信した場合、当該データをデータブロックに分割する（ステップＳ９１２）。転送装置１１０−１は、データブロックのハッシュ値に基づいて送信検索インデックス２１８を検索し、データブロックが送信データブロック情報２２０に格納されているか否かを判定する（ステップＳ９１３）。【００９５】
データブロックは送信データブロック情報２２０に格納されていないため、転送装置１１０−１は、ＷＡＮ１２０を介して、転送装置１１０−２にデータブロックを送信する（ステップＳ９１４）。【００９６】
転送装置１１０−２は、データブロックを受信した場合、受信データブロック情報２２１に当該データブロックを格納する（ステップＳ９１５）。転送装置１１０−２は、ＷＡＮ１２０を介して、転送装置１１０−１に復元確認通知を送信する（ステップＳ９１６）。また、転送装置１１０−２は、ＬＡＮ１４０−２を介して、端末１００−２に受信したデータブロックを端末１００−１から送信されたデータとして送信する（ステップＳ９１７）。【００９７】
転送装置１１０−１は、ＷＡＮ１２０を介して、復元確認通知を受信した場合、データブロックバッファ２１６に格納されるデータブロックを送信データブロック情報２２０に格納する（ステップＳ９１８）。【００９８】
図９Ｃは、転送装置１１０−１のみが、端末１００−１から送信されるデータ（データブロック）を保持している場合のデータ転送処理の流れを示す。【００９９】
ステップＳ９２１からステップＳ９２４の処理は、ステップＳ９０１からステップＳ９０４の処理と同一である。【０１００】
転送装置１１０−２は、データブロックの識別情報を受信した場合、データブロックの識別情報に基づいて受信検索インデックス２１９を検索し、データブロックが受信データブロック情報２２１に格納されているか否かを判定する（ステップＳ９２５）。【０１０１】
データブロックは受信データブロック情報２２１に格納されていないため、転送装置１１０−２は、ＷＡＮ１２０を介して、データブロック要求を送信する（ステップＳ９２６）。【０１０２】
転送装置１１０−１は、ＷＡＮ１２０を介して、データブロック要求を受信した場合、ＷＡＮ１２０を介して、転送装置１１０−２にデータブロックバッファ２１６に格納されるデータブロックを送信する（ステップＳ９２７）。【０１０３】
転送装置１１０−２は、ＷＡＮ１２０を介して、データブロックを受信した場合、受信データブロック情報２２１に当該データブロックを格納する（ステップＳ９２８）。転送装置１１０−２は、ＷＡＮ１２０を介して、転送装置１１０−１に復元確認通知を送信する（ステップＳ９２９）。また、転送装置１１０−２は、ＬＡＮ１４０−２を介して、端末１００−２に受信したデータブロックを端末１００−１から送信されたデータとして送信する（ステップＳ９３０）。【０１０４】
転送装置１１０−１は、ＷＡＮ１２０を介して、復元確認通知を受信した場合、データブロックバッファ２１６に格納されるデータブロックを削除する（ステップＳ９３１）。【０１０５】
転送装置１１０−１は、復元確認通知を受信するまで、データブロックバッファ２１６にデータブロックを格納するため、転送装置１１０−２からのデータブロック要求を受信した場合、即座に転送装置１１０−２にデータブロックを送信できる。【０１０６】
また、図９Ｂに示すように、転送装置１１０−１は、復元確認通知を受信した後に、送信データブロック情報２２０にデータブロックを格納する。送信データブロック情報２２０へのデータブロックの格納順番が逆の場合、転送装置１１０−２にデータブロックが登録されていない可能性がある。そのため、図９Ｃに示すようなデータ転送処理が発生する可能性がある。一方、図９Ｂに示すような処理手順にすることによって、図９Ｃに示すようなデータ転送処理が発生する可能性を低くすることができる。図９Ｃに示すデータ転送処理では、転送装置１１０間の通信回数が増えることから、通信の遅延が発生する。したがって、図９Ｃに示すようなデータ転送処理の発生を防止することによって、ネットワークシステム全体の通信速度、通信品質等を向上させることができる。【０１０７】
次に、図１０から図１８を用いて、転送装置１１０の各機能部が実行する処理の詳細を説明する。【０１０８】
図１０は、実施例１の転送制御部２１３がＬＡＮ１４０からデータを受信した場合に実行する処理を説明するフローチャートである。【０１０９】
転送制御部２１３は、プロトコル処理部２１４から、ＬＡＮ１４０から受信したデータを受け取った場合（ステップＳ１００１）、フロー情報２１７にデータを格納する（ステップＳ１００２）。【０１１０】
具体的には、転送制御部２１３は、プロトコル処理部２１４から受け取ったＩＰアドレス、ポート番号、及びＶＬＡＮのＩＤ等に基づいてフロー情報２１７を参照し、フローに対応するエントリを特定する。転送制御部２１３は、特定されたエントリのバッファ６０７に、受け取ったデータ（ＴＣＰペイロード４６０）を格納する。なお、バッファ６０７にデータが格納されている場合、転送制御部２１３は、当該データの後方に受け取ったデータを追加する。【０１１１】
次に、転送制御部２１３は、データ分割部２１５を呼び出す（ステップＳ１００３）。このとき、転送制御部２１３は、受け取ったデータをデータ分割部２１５に出力する。その後、転送制御部２１３は、処理を終了する。【０１１２】
図１１は、実施例１の転送制御部２１３がデータ分割部２１５から応答を受け取った場合に実行する処理を説明するフローチャートである。【０１１３】
転送制御部２１３は、データ分割部２１５から受け取った応答が分割不可通知であるか否かを判定する（ステップＳ１１０１）。【０１１４】
データ分割部２１５から受け取った応答が分割不可通知であると判定された場合、転送制御部２１３は、ステップＳ１１０６に進む。【０１１５】
データ分割部２１５から受け取った応答が分割不可通知ではないと判定された場合、すなわち、データ分割部２１５からデータブロックを受け取った場合、転送制御部２１３は、ステップＳ１００２において特定されたエントリのバッファ６０７に格納されるデータから当該データブロックを削除する（ステップＳ１１０２）。【０１１６】
具体的には、転送制御部２１３は、ステップＳ１００２において特定されたエントリのバッファ６０７に格納されるデータからデータブロックに一致するデータ列を削除する。【０１１７】
次に、転送制御部２１３は、重複排除部２１１を呼び出す（ステップＳ１１０３）。転送制御部２１３は、重複排除部２１１から応答があるまで待ち状態に移行する。このとき、転送制御部２１３は、データブロックを重複排除部２１１に入力する。【０１１８】
転送制御部２１３は、一定時間経過した後、重複排除部２１１から符号化されたデータを取得したか否かを判定する（ステップＳ１１０４）。【０１１９】
重複排除部２１１から符号化されたデータを取得していないと判定された場合、転送制御部２１３は、待ち状態に移行し、一定時間経過した後にステップＳ１１０４に戻る。【０１２０】
重複排除部２１１から符号化されたデータを取得したと判定された場合、転送制御部２１３は、ＷＡＮ１２０を介して、符号化されたデータを送信し、また、データブロックバッファ２１６にデータブロックを格納する（ステップＳ１１０５）。【０１２１】
具体的には、転送制御部２１３は、符号化されたデータをプロトコル処理部２１４に出力する。なお、符号化されたデータとは、一つ以上のＤｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０の組を表す。【０１２２】
ステップＳ１１０１の判定結果がＹＥＳの場合、又は、ステップＳ１１０５の処理が実行された後、転送制御部２１３は、ステップＳ１００２において特定されたエントリのバッファ６０７にデータが残っているか否かを判定する（ステップＳ１１０６）。【０１２３】
ステップＳ１００２において特定されたエントリのバッファ６０７にデータが残っていると判定された場合、転送制御部２１３は、当該エントリのタイマ６０８に任意の時間を設定する（ステップＳ１１０７）。その後、転送制御部２１３は、処理を終了する。【０１２４】
ステップＳ１００２において特定されたエントリのバッファ６０７にデータが残っていないと判定された場合、転送制御部２１３は、当該エントリのタイマ６０８に「０」を設定する（ステップＳ１１０８）。その後、転送制御部２１３は、処理を終了する。【０１２５】
図１２は、実施例１の転送制御部２１３がタイマ６０８に設定された時間が経過した場合に実行する処理を説明するフローチャートである。【０１２６】
転送制御部２１３は、各フローについてタイマをカウントし、タイマ６０８に設定された時間が経過したエントリを検出した場合、以下の処理を開始する。以下では、タイマ６０８に設定された時間が経過したエントリを対象エントリと記載する。【０１２７】
転送制御部２１３は、対象エントリのバッファ６０７に格納されるデータの符号化を重複排除部２１１に指示する（ステップＳ１２０１）。転送制御部２１３は、重複排除部２１１から符号化されたデータを取得するまで待ち状態に移行する。なお、当該指示には、対象エントリのバッファ６０７に格納されるデータが含まれる。【０１２８】
重複排除部２１１は、当該指示を受け付けた場合、ｄｅｄｕｐ．ｔｙｐｅ５１１に「３」を設定し、ｄｅｄｕｐ．ｄａｔａ＿ｌｅｎ５１２にバッファ６０７に格納されるデータの長さを設定し、ｄｅｄｕｐ．ｈａｓｈ１  ５１３及びｄｅｄｕｐ．ｈａｓｈ２  ５１４にダミーの値として「０」を設定することによってＤｅｄｕｐヘッダ５１０を生成する。また、重複排除部２１１は、Ｄｅｄｕｐペイロード５２０に対象エントリのバッファ６０７に格納されるデータを設定する。重複排除部２１１は、Ｄｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０を転送制御部２１３に出力する。【０１２９】
次に、転送制御部２１３は、重複排除部２１１から符号化されたデータを取得した場合、ＷＡＮ１２０を介して、符号化されたデータを送信する（ステップＳ１２０２）。【０１３０】
具体的には、転送制御部２１３は、符号化されたデータをプロトコル処理部２１４に出力する。これによって、Ｄｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０を含むＴＣＰパケット５００が送信される。【０１３１】
次に、転送制御部２１３は、対象エントリのタイマ６０８に「０」を設定する（ステップＳ１２０３）。その後、転送制御部２１３は、処理を終了する。【０１３２】
このように、タイマ６０８に設定された時間が経過した場合に、転送装置１１０がバッファ６０７に格納されるデータを送信することによって、受信したデータが転送されない状態を防止できる。【０１３３】
図１３は、実施例１の転送制御部２１３が他の転送装置１１０から応答を受信した場合に実行する処理を説明するフローチャートである。【０１３４】
転送制御部２１３は、プロトコル処理部２１４から、ＷＡＮ１２０から受信した他の転送装置１１０の応答を受け取った場合（ステップＳ１３０１）、受け取った応答がデータブロック要求であるか否かを判定する（ステップＳ１３０２）。【０１３５】
受け取った応答がデータブロック要求であると判定された場合、転送制御部２１３は、データブロックバッファ２１６からデータブロックを読み出し、重複排除部２１１にデータブロックの符号化を指示する（ステップＳ１３０３）。転送制御部２１３は、重複排除部２１１から符号化されたデータブロックを取得するまで待ち状態に移行する。なお、当該指示には、データブロックが含まれる。【０１３６】
重複排除部２１１は、当該指示を受け付けた場合、第１ハッシュ関数及び第２ハッシュ関数を用いて、変数α及び変数βを算出する。変数α及び変数βの算出方法は、図１５を用いて説明する。重複排除部２１１は、ｄｅｄｕｐ．ｔｙｐｅ５１１に「２」を設定し、ｄｅｄｕｐ．ｄａｔａ＿ｌｅｎ５１２にデータブロックの長さを設定し、ｄｅｄｕｐ．ｈａｓｈ１  ５１３に変数αを設定し、ｄｅｄｕｐ．ｈａｓｈ２  ５１４に変数βを設定することによってＤｅｄｕｐヘッダ５１０を生成する。また、重複排除部２１１は、Ｄｅｄｕｐペイロード５２０にデータブロックを設定する。重複排除部２１１は、Ｄｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０を転送制御部２１３に出力する。【０１３７】
次に、転送制御部２１３は、重複排除部２１１から符号化されたデータブロックを取得した場合、ＷＡＮ１２０を介して、符号化されたデータブロックを送信する（ステップＳ１３０４）。その後、転送制御部２１３は、処理を終了する。【０１３８】
具体的には、転送制御部２１３は、符号化されたデータブロックをプロトコル処理部２１４に出力する。これによって、Ｄｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０を含むＴＣＰパケット５００が送信される。【０１３９】
ステップＳ１３０２において、受け取った応答がデータブロック要求でないと判定された場合、転送制御部２１３は、更新フラグがＯＮであるか否かを判定する（ステップＳ１３０５）。【０１４０】
更新フラグがＯＦＦであると判定された場合、転送制御部２１３は、ステップＳ１３０７に進む。【０１４１】
更新フラグがＯＮであると判定された場合、転送制御部２１３は、重複排除部２１１に更新指示を出力する（ステップＳ１３０６）。このとき、転送制御部２１３は、更新フラグをＯＦＦに設定する。当該更新指示にはデータブロックが含まれる。重複排除部２１１が、更新指示を受け付けた場合に実行する処理は図１６を用いて説明する。【０１４２】
ステップＳ１３０５の判定結果がＮＯである場合、又は、ステップＳ１３０６の処理が実行された後、転送制御部２１３は、データブロックバッファ２１６からデータブロックを削除する（ステップＳ１３０７）。その後、転送制御部２１３は、処理を終了する。【０１４３】
図１４は、実施例１のデータ分割部２１５が実行する処理を説明するフローチャートである。【０１４４】
ここでは、データ分割部２１５が、Ｃｏｎｔｅｎｔ  Ｄｅｆｉｎｅｄ  Ｃｈｕｎｋｉｎｇとして知られるアルゴリズムに基づいて、データを可変長のデータブロックに分割する方法について説明する。Ｃｏｎｔｅｎｔ  Ｄｅｆｉｎｅｄ  Ｃｈｕｎｋｉｎｇでは、計算機が、固定長のウインドウ（例えば、４８バイト）をデータの先頭から１バイトずつスライドし、ウインドウに含まれるデータのハッシュ値を用いて分割位置を決定する。【０１４５】
データ分割部２１５は、転送制御部２１３から呼び出された場合、処理を開始する。まず、データ分割部２１５は、転送制御部２１３からＬＡＮ１４０から受信したデータを取得する（ステップＳ１４０１）。【０１４６】
データ分割部２１５は、データの先頭に所定のサイズのウインドウを配置する（ステップＳ１４０２）。データ分割部２１５は、ウインドウに含まれるデータのハッシュ値を算出する（ステップＳ１４０３）。ハッシュ値を算出するためのハッシュ関数は、例えば、ローリングハッシュとして知られるハッシュ関数を用いる。【０１４７】
次に、データ分割部２１５は、ハッシュ値が所定の条件を満たすか否かを判定する（ステップＳ１４０４）。【０１４８】
例えば、２進法表記におけるハッシュ値の下１０桁が全て１であるか否かが判定される。ハッシュ値が入力されたデータに応じて適切に散らばる場合、２進法表記におけるハッシュ値の下１０桁が全て１になる確率は１０２４分の１である。このとき、データブロックの平均サイズは約１０２４バイトとなる。【０１４９】
ハッシュ値が所定の条件を満たすと判定された場合、データ分割部２１５は、ウインドウに含まれるデータを出力するデータブロックに決定し、転送制御部２１３に当該データブロックを応答として出力する（ステップＳ１４０５）。その後、転送制御部２１３は処理を終了する。【０１５０】
ステップＳ１４０４において、ハッシュ値が所定の条件を満たさないと判定された場合、データ分割部２１５は、ウインドウの移動が可能であるか否かを判定する（ステップＳ１４０６）。【０１５１】
具体的には、データ分割部２１５は、ウインドウの終端がＬＡＮ１４０から受信したデータの終端と一致するか否かが判定される。ウインドウの終端がＬＡＮ１４０から受信したデータの終端と一致しない場合、データ分割部２１５は、ウインドウの移動が可能であると判定する。【０１５２】
ウインドウの移動が不可能であると判定された場合、データ分割部２１５は、転送制御部２１３に分割不可通知を応答として出力する（ステップＳ１４０７）。その後、転送制御部２１３は処理を終了する。【０１５３】
ウインドウの移動が可能であると判定された場合、データ分割部２１５は、ウインドウをデータの後方にスライドさせ（ステップＳ１４０８）、その後、ステップＳ１４０３に戻る。例えば、データ分割部２１５は、ウインドウを１バイト分だけ後方にスライドさせる。【０１５４】
図１５は、実施例１の重複排除部２１１が転送制御部２１３によって呼び出された場合に実行する処理を説明するフローチャートである。【０１５５】
重複排除部２１１は、転送制御部２１３からデータブロックを取得する（ステップＳ１５０１）。重複排除部２１１は、第１ハッシュ関数及び第２ハッシュ関数を用いて、変数α及び変数βを算出する（ステップＳ１５０２）。【０１５６】
具体的には、重複排除部２１１は、第１ハッシュ関数にデータブロックを入力することによって算出された第１ハッシュ値を２次元配列の行数Ｎで除算し、その余りを変数αとして算出する。また、重複排除部２１１は、第２ハッシュ関数にデータブロックを入力することによって算出される第２ハッシュ値を変数βとして算出する。【０１５７】
次に、重複排除部２１１は、送信検索インデックス２１８を参照し（ステップＳ１５０３）、ハッシュ値が変数βに一致する要素７０１が存在するか否かを判定する（ステップＳ１５０４）。【０１５８】
具体的には、重複排除部２１１は、α行目の行に含まれる要素７０１を参照する要素７０１群として特定する。重複排除部２１１は、α行目に含まれる各要素７０１に格納されるハッシュ値Ｘと、変数βとを比較する。【０１５９】
ハッシュ値Ｘが変数βに一致する要素７０１が存在しないと判定された場合、重複排除部２１１は、ステップＳ１５０８に進む。【０１６０】
ハッシュ値Ｘが変数βに一致する要素７０１が存在すると判定された場合、重複排除部２１１は、送信データブロック情報２２０からデータブロックを読み出す（ステップＳ１５０５）。【０１６１】
具体的には、重複排除部２１１は、ハッシュ値Ｘが変数βに一致する要素７０１に含まれるポインタ値Ｐを取得し、送信データブロック情報２２０を参照して、当該ポインタ値Ｐがファイル名８０１に一致するエントリを検索する。重複排除部２１１は、検索されたエントリのデータブロック８０２からデータブロックを読み出す。【０１６２】
次に、重複排除部２１１は、転送制御部２１３から取得したデータブロックと、送信データブロック情報２２０から読み出したデータブロックとが一致するか否かを判定する（ステップＳ１５０６）。【０１６３】
二つのデータブロックが一致しないと判定された場合、重複排除部２１１は、ステップＳ１５０８に進む。【０１６４】
二つのデータブロックが一致すると判定された場合、重複排除部２１１は、転送制御部２１３に、符号化されたデータブロックの識別情報を出力する（ステップＳ１５０７）。その後、重複排除部２１１は、処理を終了する。【０１６５】
具体的には、重複排除部２１１は、ｄｅｄｕｐ．ｔｙｐｅ５１１に「１」を設定し、ｄｅｄｕｐ．ｄａｔａ＿ｌｅｎ５１２に「０」を設定し、ｄｅｄｕｐ．ｈａｓｈ１  ５１３に変数αを設定し、ｄｅｄｕｐ．ｈａｓｈ２  ５１４に変数βを設定することによってＤｅｄｕｐヘッダ５１０を生成する。重複排除部２１１は、Ｄｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０を転送制御部２１３に出力する。なお、Ｄｅｄｕｐペイロード５２０は空であるものとする。【０１６６】
Ｄｅｄｕｐヘッダ５１０のサイズが２８バイト、データブロックのサイズの平均値が４キロバイトである場合、データブロックの識別情報のみを送信する通信は、データブロックを送信する通信より通信量が１００分の１以下となる。なお、前述の比較は、ＴＣＰヘッダ４４０等を除いたものである。【０１６７】
ステップＳ１５０４の判定結果がＮＯである場合、又は、ステップＳ１５０６の判定結果がＮＯである場合、重複排除部２１１は、転送制御部２１３の更新フラグをＯＮに設定する（ステップＳ１５０８）。このとき、重複排除部２１１は、変数α及び変数βを一時的に保持する。【０１６８】
次に、重複排除部２１１は、転送制御部２１３に、符号化されたデータブロックの識別情報及び符号化されたデータブロックを出力する（ステップＳ１５０９）。その後、重複排除部２１１は、処理を終了する。【０１６９】
具体的には、重複排除部２１１は、ｄｅｄｕｐ．ｔｙｐｅ５１１に「２」を設定し、ｄｅｄｕｐ．ｄａｔａ＿ｌｅｎ５１２にデータブロックのサイズを設定し、ｄｅｄｕｐ．ｈａｓｈ１  ５１３に変数αを設定し、ｄｅｄｕｐ．ｈａｓｈ２  ５１４に変数βを設定することによってＤｅｄｕｐヘッダ５１０を生成する。また、重複排除部２１１は、Ｄｅｄｕｐペイロード５２０にデータブロックを設定する。重複排除部２１１は、Ｄｅｄｕｐヘッダ５１０及びＤｅｄｕｐペイロード５２０を転送制御部２１３に出力する。【０１７０】
変数αは、行数Ｎで割った余りであるため、０からＮ−１までの値となる。したがって、任意のデータブロックの変数αは、他のデータブロックを用いて算出された変数αとＮ分の１の確率で一致する。送信検索インデックス２１８のデータサイズは行数Ｎの大きさに依存するため、行数Ｎの大きさには制限がある。一方、変数βは、第２ハッシュ値をそのまま入力したものであり、Ｎより十分大きな値を設定できる。【０１７１】
例えば、変数αのサイズを２０ビット、変数βのサイズを１２８ビット、ポインタ値Ｐのサイズを６４ビットとした場合、送信検索インデックス２１８のサイズは、式（１）に示すように約１００ＭＢとなる。変数αのサイズを１２８ビット、変数βのサイズを２０ビット、ポインタ値Ｐのサイズを６４ビットとした場合、送信検索インデックス２１８のサイズは、式（２）に示すように約１．２×１０１６ＹＢとなる。【０１７２】
【数１】
0006730437.tif 000002
【０１７３】
【数２】
0006730437.tif 000003
【０１７４】
変数βのサイズを大きくすると、ハッシュ値の衝突が発生する確率が非常に低くなる。したがって、変数βとハッシュ値Ｘとが一致する場合、受信したデータブロックと、送信データブロック情報２２０から読み出したデータブロックとは、高い確率で一致する。この場合、変数β及びハッシュ値Ｘの比較のみを行えばよく、データブロック同士を比較する必要はない。そのため、ステップＳ１５０６の省略できる。【０１７５】
ステップＳ１５０６の処理を省略した場合、二次記憶装置２０３へのアクセスする必要がないため、重複排除部２１１は、さらに高速に、データブロックを検索することができる。したがって、処理速度を重視する場合には、変数βのサイズを大きくし、ステップＳ１５０６の処理を行わないように設定すればよい。【０１７６】
図１６は、実施例１の重複排除部２１１が転送制御部２１３から更新指示を受け付けた場合に実行する処理を説明するフローチャートである。【０１７７】
重複排除部２１１は、転送制御部２１３から更新指示を受け取った場合（ステップＳ１６０１）、送信検索インデックス２１８及び送信データブロック情報２２０を更新する（ステップＳ１６０２）。その後、重複排除部２１１は、処理を終了する。具体的には、以下のような処理が実行される。【０１７８】
重複排除部２１１は、ポインタ値Ｐに設定する値を式（３）を用いて算出する。なお、ｍは、第２ハッシュ関数の出力値の最大ビット数である。【０１７９】
【数３】
0006730437.tif 000004
【０１８０】
式（３）に示すように変数α及び変数βに基づいて一意に定まる値をポインタ値に用いることによって、異なるデータブロックのポインタ値が同一となる確率を非常に小さくできる。【０１８１】
重複排除部２１１は、送信検索インデックス２１８のα行目を参照し、α行目に含まれる要素７０１の中に空の要素７０１が存在するか否かを判定する。空の要素７０１とは、ハッシュ値Ｘ及びポインタ値Ｐが設定されていない要素７０１を示す。【０１８２】
空の要素７０１が存在する場合、重複排除部２１１は、当該要素７０１のハッシュ値Ｘに変数βを設定し、ポインタ値Ｐに式（３）を用いて算出された値を設定する。また、重複排除部２１１は、送信データブロック情報２２０にエントリを追加し、追加されたエントリのファイル名８０１に式（３）を用いて算出された値を設定し、データブロック８０２に更新指示に含まれるデータブロックを格納する。【０１８３】
空の要素７０１が存在しない場合、重複排除部２１１は、α行目に含まれる要素７０１の中から値を設定する要素７０１を一つ選択する。要素７０１を選択する方法は様々考えられる。例えば、ランダムに選択する方法、及びＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）アルゴリズムに基づいて選択する方法等が考えられる。【０１８４】
重複排除部２１１は、送信データブロック情報２２０を参照し、ファイル名８０１が選択された要素７０１のポインタ値Ｐに一致するエントリを検索し、検索されたエントリを削除する。重複排除部２１１は、選択された要素７０１のハッシュ値Ｘに変数βを設定し、ポインタ値Ｐに式（３）を用いて算出された値を設定する。また、重複排除部２１１は、送信データブロック情報２２０にエントリを追加し、追加されたエントリのファイル名８０１に式（３）を用いて算出された値を設定し、データブロック８０２にデータブロックを格納する。以上がステップＳ１６０２の処理の説明である。【０１８５】
図１７は、実施例１の転送制御部２１３がＷＡＮ１２０からデータを受信した場合に実行する処理を説明するフローチャートである。【０１８６】
転送制御部２１３は、プロトコル処理部２１４から、ＷＡＮ１２０から受信したデータ（ＴＣＰパケット５００）を受け取った場合（ステップＳ１７０１）、重複復元部２１２を呼び出す（ステップＳ１７０２）。このとき、転送制御部２１３は、受け取ったデータを重複復元部２１２に出力する。転送制御部２１３は、重複復元部２１２から応答を受け付けるまで待ち状態に移行する。【０１８７】
転送制御部２１３は、重複復元部２１２からの応答に基づいて、データブロックを取得する必要があるか否かを判定する（ステップＳ１７０３）。【０１８８】
具体的には、転送制御部２１３は、重複復元部２１２からの応答が「該当データ無し」であるか否かを判定する。重複復元部２１２からの応答が「該当データ無し」である場合、転送制御部２１３は、データブロックを取得する必要があると判定する。【０１８９】
データブロックを取得する必要がないと判定された場合、転送制御部２１３は、ＬＡＮ１４０を介して、復元されたデータを送信する（ステップＳ１７０４）。【０１９０】
具体的には、転送制御部２１３は、復元されたデータをプロトコル処理部２１４に出力する。これによって、Ｄｅｄｕｐペイロード５２０に設定されたデータがＴＣＰペイロード４６０に設定されたＴＣＰパケット４００が送信される。【０１９１】
次に、転送制御部２１３は、ＷＡＮ１２０を介して、復元確認通知を送信する（ステップＳ１７０５）。その後、転送制御部２１３は、処理を終了する。【０１９２】
具体的には、転送制御部２１３は、プロトコル処理部２１４に復元確認通知の送信を指示する。なお、復元確認通知を送信する場合には、ＴＣＰパケット４００及びＴＣＰパケット５００のいずれを用いてもよい。【０１９３】
ステップＳ１７０３において、データブロックを取得する必要があると判定された場合、転送制御部２１３は、ＷＡＮ１２０を介して、データブロック要求を送信する（ステップＳ１７０６）。その後、転送制御部２１３は、処理を終了する。【０１９４】
具体的には、転送制御部２１３は、プロトコル処理部２１４にデータブロック要求の送信を指示する。なお、データブロック要求を送信する場合には、ＴＣＰパケット４００及びＴＣＰパケット５００のいずれを用いてもよい。【０１９５】
図１８は、実施例１の重複復元部２１２が転送制御部２１３によって呼び出された場合に実行する処理を説明するフローチャートである。【０１９６】
重複復元部２１２は、転送制御部２１３からデータを取得し（ステップＳ１８０１）、Ｄｅｄｕｐヘッダ５１０に含まれるｄｅｄｕｐ．ｔｙｐｅ５１１の値が「２」であるか否かを判定する（ステップＳ１８０２）。【０１９７】
ｄｅｄｕｐ．ｔｙｐｅ５１１の値が「２」ではないと判定された場合、重複復元部２１２は、ｄｅｄｕｐ．ｔｙｐｅ５１１の値が「３」であるか否かを判定する（ステップＳ１８０３）。【０１９８】
ｄｅｄｕｐ．ｔｙｐｅ５１１の値が「１」であると判定された場合、重複復元部２１２は、受信検索インデックス２１９を参照し、ハッシュ値Ｘがｄｅｄｕｐ．ｈａｓｈ２  ５１４の値に一致する要素７０１が存在するか否かを判定する（ステップＳ１８０４）。【０１９９】
具体的には、重複復元部２１２は、（ｄｅｄｕｐ．ｈａｓｈ１  ５１３）行目の行に含まれる要素７０１を参照する要素７０１群として特定する。重複復元部２１２は、（ｄｅｄｕｐ．ｈａｓｈ１  ５１３）行目に含まれる各要素７０１に格納されるハッシュ値Ｘと、ｄｅｄｕｐ．ｈａｓｈ２  ５１４の値とを比較する。【０２００】
ハッシュ値Ｘがｄｅｄｕｐ．ｈａｓｈ２  ５１４の値に一致する要素７０１が存在すると判定された場合、重複復元部２１２は、受信データブロック情報２２１からデータブロックを読み出す（ステップＳ１８０５）。【０２０１】
具体的には、重複復元部２１２は、ハッシュ値Ｘがｄｅｄｕｐ．ｈａｓｈ２  ５１４の値に一致する要素７０１からポインタ値Ｐを取得し、受信データブロック情報２２１を参照して、当該ポインタ値Ｐがファイル名８０１に一致するエントリを検索する。重複復元部２１２は、検索されたエントリのデータブロック８０２からデータブロックを読み出す。【０２０２】
次に、重複復元部２１２は、転送制御部２１３に読み出されたブロックデータを応答として出力する（ステップＳ１８０６）。その後、重複復元部２１２は、処理を終了する。【０２０３】
ステップＳ１８０４において、ハッシュ値がｄｅｄｕｐ．ｈａｓｈ２  ５１４の値に一致する要素７０１が存在しないと判定された場合、重複復元部２１２は、転送制御部２１３に「該当データ無し」を応答として出力する（ステップＳ１８０８）。その後、重複復元部２１２は、処理を終了する。【０２０４】
ステップＳ１８０３において、ｄｅｄｕｐ．ｔｙｐｅ５１１の値が「３」であると判定された場合、重複復元部２１２は、転送制御部２１３に、Ｄｅｄｕｐペイロード５２０に設定されたデータを応答として出力する（ステップＳ１８０７）。その後、重複復元部２１２は、処理を終了する。【０２０５】
ステップＳ１８０２において、ｄｅｄｕｐ．ｔｙｐｅ５１１の値が「２」であると判定された場合、重複復元部２１２は、受信検索インデックス２１９及び受信データブロック情報２２１を更新する（ステップＳ１８０９）。具体的には、以下のような処理が実行される。【０２０６】
重複復元部２１２は、ポインタ値Ｐに設定する値を式（４）を用いて算出する。【０２０７】
【数４】
0006730437.tif 000005
【０２０８】
式（４）に示すようにｄｅｄｕｐ．ｈａｓｈ１  ５１３及びｄｅｄｕｐ．ｈａｓｈ２  ５１４に基づいて一意に定まる値をポインタ値に用いることによって、異なるデータブロックのポインタ値が同一となる確率を非常に小さくできる。【０２０９】
重複復元部２１２は、受信検索インデックス２１９の（ｄｅｄｕｐ．ｈａｓｈ１  ５１３）行目を参照し、（ｄｅｄｕｐ．ｈａｓｈ１  ５１３）行目に含まれる要素７０１の中に空の要素７０１が存在するか否かを判定する。【０２１０】
空の要素７０１が存在する場合、重複復元部２１２は、当該要素７０１のハッシュ値Ｘにｄｅｄｕｐ．ｈａｓｈ２  ５１４の値を設定し、ポインタ値Ｐに式（４）を用いて算出された値を設定する。また、重複復元部２１２は、受信データブロック情報２２１にエントリを追加し、追加されたエントリのファイル名８０１に式（４）を用いて算出された値を設定し、データブロック８０２にデータブロックを格納する。【０２１１】
空の要素７０１が存在しない場合、重複復元部２１２は、（ｄｅｄｕｐ．ｈａｓｈ１  ５１３）行目に含まれる要素７０１の中から、値を設定する要素７０１を一つ選択する。要素７０１を選択する方法は重複排除部２１１が使用する方法と同一の方法とする。重複排除部２１１及び重複復元部２１２が同一の方法を用いることによって、送信データブロック情報２２０及び受信データブロック情報２２１の内容が一致する可能性が高くなる。これによって、データブロック要求を送信する回数を低減できる。【０２１２】
重複復元部２１２は、受信データブロック情報２２１を参照し、ファイル名８０１が選択された要素７０１のポインタ値Ｐに一致するエントリを検索し、検索されたエントリを削除する。重複復元部２１２は、選択された要素７０１のハッシュ値Ｘにｄｅｄｕｐ．ｈａｓｈ２  ５１４の値を設定し、ポインタ値Ｐに式（４）を用いて算出された値を設定する。また、重複復元部２１２は、受信データブロック情報２２１にエントリを追加し、追加されたエントリのファイル名８０１に式（４）を用いて算出された値を設定し、データブロック８０２にデータブロックを格納する。以上がステップＳ１８０９の処理の説明である。【０２１３】
次に、重複復元部２１２は、転送制御部２１３に、Ｄｅｄｕｐペイロード５２０に設定されたデータブロックを応答として出力する（ステップＳ１８１０）。その後、重複復元部２１２は、処理を終了する。【０２１４】
次に、図１９を用いて、重複排除部２１１が実行する具体的な処理内容について説明する。【０２１５】
図１９は、実施例１の重複排除部２１１が実行する処理の具体例を示す図である。ここで、送信検索インデックス２１８及び送信データブロック情報２２０は、それぞれ、図１９に示すエントリが格納されるものとする。なお、送信検索インデックスの左側の数字は行数を表す。【０２１６】
まず、重複排除部２１１がデータブロック「ａｂｃ．．．ｚ」を受信した場合を例に説明する。なお、当該データブロックの変数αは「６４２３」、変数βは「０ｘ１１１２１２３９」であるものとする。【０２１７】
ステップＳ１５０３において、重複排除部２１１は、６４２３行目に含まれる四つの要素７０１のハッシュ値Ｘと、変数βとを比較する。このとき、２列目の要素７０１のハッシュ値Ｘと変数βとが一致するため、ステップＳ１５０４の判定結果はＹＥＳとなる。【０２１８】
ステップＳ１５０５では、重複排除部２１１は、２列目の要素７０１のポインタ値Ｐの値「ｐ２」を用いて、送信データブロック情報２２０からデータブロック「ａｂｃ．．．ｚ」を読み出す。【０２１９】
転送制御部２１３から取得したデータブロックと、送信データブロック情報２２０から読み出したデータブロックとは一致するため、ステップＳ１５０６の判定結果はＹＥＳとなる。【０２２０】
したがって、重複排除部２１１は、符号化されたデータブロックの識別情報を出力する（ステップＳ１５０７）。なお、Ｄｅｄｕｐヘッダ５１０のｄｅｄｕｐ．ｈａｓｈ１  ５１３には「６２４２」が設定され、ｄｅｄｕｐ．ｈａｓｈ２  ５１４には「０ｘ１１１２１２３９」が設定される。【０２２１】
次に、重複排除部２１１がデータブロック「０１２．．．９」を受信した場合を例に説明する。なお、当該データブロックの変数αは「３１２」、変数βは「０ｘ１２１ｆ１２ｄ９」であるものとする。【０２２２】
ステップＳ１５０３において、重複排除部２１１は、３１２行目に含まれる四つの要素７０１のハッシュ値Ｘと、変数βとを比較する。このとき、変数βに一致するハッシュ値Ｘを含む要素７０１は存在しないため、ステップＳ１５０４の判定結果はＮＯとなる。【０２２３】
したがって、重複排除部２１１は、更新フラグをＯＮに設定し（ステップＳ１５０８）、符号化されたデータブロックの識別情報及びデータブロックを出力する（ステップＳ１５０９）。なお、Ｄｅｄｕｐヘッダ５１０のｄｅｄｕｐ．ｈａｓｈ１  ５１３には「３１２」が設定され、ｄｅｄｕｐ．ｈａｓｈ２  ５１４には「０ｘ１２１ｆ１２ｄ９」が設定される。また、Ｄｅｄｕｐペイロード５２０にはデータブロック「０１２．．．９」が設定される。【０２２４】
重複排除部２１１は、転送制御部２１３から更新指示を受け取った場合、データブロック「０１２．．．９」から変数α及び変数βを算出し、また、式（３）を用いてポインタ値Ｐに設定する値を算出する。【０２２５】
重複排除部２１１は、送信検索インデックス２１８の３１２行目を参照する。３１２行目には空の要素７０１が存在しないため、重複排除部２１１は、３１２行目に含まれる要素７０１の中から一つの要素を選択する。ここでは、２列目の要素７０１が選択されたものとする。【０２２６】
重複排除部２１１は、送信データブロック情報２２０を参照して、ファイル名８０１がｐ６であるエントリを検索し、検索されたエントリを削除する。【０２２７】
重複排除部２１１は、３１２行目の２列目の要素７０１のハッシュ値Ｘに変数βを設定し、また、ポインタ値Ｐに式（３）を用いて算出された値を設定する。また、重複排除部２１１は、送信データブロック情報２２０にエントリを追加し、追加されたエントリのファイル名８０１に式（３）を用いて算出された値を設定し、データブロック８０２にデータブロック「０１２．．．９」を設定する。【０２２８】
二つのデータブロックを例に、送信検索インデックス２１８及び送信データブロック情報２２０の使用方法について説明した。なお、受信検索インデックス２１９及び受信データブロック情報２２１の使用方法も同様である。【０２２９】
実施例１によれば、転送装置１１０は、送信検索インデックス２１８及び受信検索インデックス２１９を用いることによって、二次記憶装置２０３に格納される送信データブロック情報２２０及び受信データブロック情報２２１にアクセスすることなくデータブロックを保持しているか否かを判定できる。【０２３０】
特に、ｄｅｄｕｐ．ｈａｓｈ２  ５１４（変数β）のサイズを大きくすることによって、ハッシュ値の衝突を回避することができるため、転送装置１１０は、送信検索インデックス２１８及び受信検索インデックス２１９のみを用いてデータブロックを検索することができる。【０２３１】
また、送信検索インデックス２１８及び受信検索インデックス２１９は、送信データブロック情報２２０及び受信データブロック情報２２１よりサイズを小さくできるため、主記憶装置２０２に送信検索インデックス２１８及び受信検索インデックス２１９を格納することができる。【０２３２】
したがって、転送装置１１０は、送信検索インデックス２１８及び受信検索インデックス２１９を用いて、データブロックの重複排除及び重複復元を高速に行うことができる。これによって、データ転送処理の高速化を実現することができる。
【実施例２】
【０２３３】
実施例２では、データブロックの分割方法が実施例１と異なる。以下、実施例１との差異を中心に実施例２について説明する。なお、実施例１と同一の構成、同一の処理には、同一の符号を付し、説明を省略する。【０２３４】
実施例２のネットワークシステムの構成は、実施例１のネットワークシステムの構成と同一であるため説明を省略する。【０２３５】
図２０は、実施例２の転送装置１１０のハードウェア構成及びソフトウェア構成の一例を示す図である。図２１は、実施例２の転送装置１１０のソフトウェア構成の論理的な接続関係を示す図である。【０２３６】
実施例２の転送装置１１０のハードウェア構成は、実施例１の転送装置１１０のハードウェア構成と同一であるため説明を省略する。【０２３７】
実施例２の転送装置１１０の主記憶装置２０２は、副検索インデックス２００１を格納する。副検索インデックス２００１は、送信データブロック情報２２０に格納されるデータブロックを検索する場合に使用されるインデックスである。副検索インデックス２００１の詳細は、図２４を用いて説明する。【０２３８】
実施例２のフロー情報２１７のデータ構造は、実施例１のフロー情報２１７のデータ構造と異なる。実施例２のフロー情報２１７の詳細は、図２２を用いて説明する。【０２３９】
実施例２のデータ分割部２１５は、実施例１とは異なる方法を用いてデータブロックを生成する。データ分割部２１５が生成するデータブロックについて、図２３を用いて説明する。【０２４０】
実施例２の転送制御部２１３が実行する処理は、実施例１の転送制御部２１３が実行する処理と一部異なる。異なる処理については、図２５を用いて説明する。実施例２の重複排除部２１１が実行する処理は、実施例１の重複排除部２１１が実行する処理と一部異なる。異なる処理については、図２６及び図２７を用いて説明する。また、実施例２の重複排除部２１１は、第１ハッシュ関数及び第２ハッシュ関数の他に、第３ハッシュ関数を保持する。【０２４１】
その他の情報及び機能部が実行する処理は、実施例１と同一である。【０２４２】
図２２は、実施例２のフロー情報２１７の一例を示す図である。【０２４３】
フロー情報２１７に含まれるエントリは、ｈｅａｄ２２０１を含む。ｈｅａｄ２２０１は、バッファ６０７に格納されるデータの先頭がデータブロックの先頭であるか否かを示す情報であり、初期値は「ＮＯ」である。エントリに含まれるその他のカラムは実施例１と同一である。【０２４４】
図２３は、実施例２のデータの分割方法の概念を示す図である。【０２４５】
実施例２では、ＬＡＮ１４０を介して受信したデータは、固定長のデータブロックに分割される。図２３では、ｉ番目のデータブロックの識別情報をＭｉと記載している。【０２４６】
さらに、実施例２では、一つのデータブロックが、固定長の副データブロックに分割される。転送装置１１０は、副データブロックの場所を検索するためのインデックスとして、副検索インデックス２００１を保持する。【０２４７】
図２４は、実施例２の副検索インデックス２００１の一例を示す図である。【０２４８】
副検索インデックス２００１は、２次元配列のデータ構造である。図２４では、Ｎ行４列の２次元配列となっている。なお、行及び列の数は一例であって、任意の値に設定できる。【０２４９】
２次元配列の一つの要素２４０１には、ハッシュ値ＸＸ及び添字Ｉが含まれる。ハッシュ値ＸＸは、第３ハッシュ関数にデータブロックを入力することによって算出されるハッシュ値である。ハッシュ値ＸＸは、データブロックが送信データブロック情報２２０に格納されているか否かを判定する場合に使用される。添字Ｉは、データブロックの先頭から何番目の副データブロックであるかを示す値である。【０２５０】
図２５は、実施例２の転送制御部２１３がＬＡＮ１４０からデータを受信した場合に実行する処理を説明するフローチャートである。【０２５１】
転送制御部２１３は、ステップＳ１００２の処理が完了した後、特定されたエントリのバッファ６０７に格納されるデータの先頭がデータブロックの先頭であるか否かを判定する（ステップＳ２５０１）。【０２５２】
具体的には、転送制御部２１３は、特定されたエントリのｈｅａｄ２２０１が「ＹＥＳ」であるか否かを判定する。ｈｅａｄ２２０１が「ＹＥＳ」である場合、転送制御部２１３は、特定されたエントリのバッファ６０７に格納されるデータの先頭がデータブロックの先頭であると判定する。【０２５３】
特定されたエントリのバッファ６０７に格納されるデータの先頭がデータブロックの先頭であると判定された場合、転送制御部２１３は、データ分割部２１５を呼び出す（ステップＳ１００３）。このとき、転送制御部２１３は、受け取ったデータをデータ分割部２１５に出力する。その後、転送制御部２１３は、処理を終了する。【０２５４】
特定されたエントリのバッファ６０７に格納されるデータの先頭がデータブロックの先頭ではないと判定された場合、転送制御部２１３は、特定されたエントリのバッファ６０７に格納されるデータのサイズが比較ブロックサイズ以上であるか否かを判定する（ステップＳ２５０２）。なお、比較ブロックサイズは、予め設定されているものとする。【０２５５】
特定されたエントリのバッファ６０７に格納されるデータのサイズが比較ブロックサイズより小さいと判定された場合、転送制御部２１３は、特定されたエントリのバッファ６０７にデータが残っているか否かを判定する（ステップＳ２５０３）。【０２５６】
特定されたエントリのバッファ６０７にデータが残っていると判定された場合、転送制御部２１３は、当該エントリのタイマ６０８に任意の時間を設定する（ステップＳ２５０４）。その後、転送制御部２１３は、処理を終了する。【０２５７】
特定されたエントリのバッファ６０７にデータが残っていないと判定された場合、転送制御部２１３は、当該エントリのタイマ６０８に「０」を設定する（ステップＳ２５０５）。その後、転送制御部２１３は、処理を終了する。【０２５８】
ステップＳ２５０２において、特定されたエントリのバッファ６０７に格納されるデータのサイズが比較ブロックサイズ以上であると判定された場合、転送制御部２１３は、重複排除部２１１に副データブロックの検出指示を出力する（ステップＳ２５０６）。転送制御部２１３は、重複排除部２１１から応答を受け取るまで待ち状態に移行する。なお、副データブロックの検索処理は、図２６を用いて説明する。【０２５９】
転送制御部２１３は、重複排除部２１１から受け取った応答に基づいて、特定されたエントリのバッファ６０７に格納されるデータに副データブロックが存在するか否かを判定する（ステップＳ２５０７）。【０２６０】
具体的には、転送制御部２１３は、重複排除部２１１からの応答が「該当データ無し」であるか否かを判定する。重複排除部２１１からの応答が「該当データ無し」である場合、転送制御部２１３は、特定されたエントリのバッファ６０７に格納されるデータに副データブロックが存在すると判定する。【０２６１】
特定されたエントリのバッファ６０７に格納されるデータに副データブロックが存在すると判定された場合、転送制御部２１３は、副データブロックを含むデータブロックを特定し、特定されたエントリのバッファ６０７に格納されるデータの先頭から当該データブロックの手前までのデータを削除し、符号化されたデータを出力するとともに、特定されたエントリのｈｅａｄ２２０１を「ＹＥＳ」に更新する（ステップＳ２５０８）。その後、転送制御部２１３は、ステップＳ１００３に進む。具体的には、以下のような処理が実行される。【０２６２】
転送制御部２１３は、重複排除部２１１を介して、検索された副データブロックの識別情報（添字Ｉ）に基づいて、特定されたエントリのバッファ６０７に格納されるデータにおける、データブロックの先頭を特定する。【０２６３】
転送制御部２１３は、重複排除部２１１にデータブロックの符号化を指示する。転送制御部２１３は、重複排除部２１１から符号化されたデータを取得するまで待ち状態に移行する。当該指示には、特定されたエントリのバッファ６０７に格納されるデータが含まれる。以下では、バッファ６０７に格納されるデータの先頭から当該データブロックの手前までのデータを対象データと記載する。【０２６４】
重複排除部２１１は、当該指示を受け付けた場合、ｄｅｄｕｐ．ｔｙｐｅ５１１に「３」を設定し、ｄｅｄｕｐ．ｄａｔａ＿ｌｅｎ５１２に対象データの長さを設定し、ｄｅｄｕｐ．ｈａｓｈ１  ５１３及びｄｅｄｕｐ．ｈａｓｈ２  ５１４にダミーの値として「０」を設定することによってＤｅｄｕｐヘッダ５１０を生成する。また、重複排除部２１１は、Ｄｅｄｕｐペイロード５２０に対象データを設定する。以上がステップＳ２５０８の処理の説明である。【０２６５】
特定されたエントリのバッファ６０７に格納されるデータに副データブロックが存在しないと判定された場合、転送制御部２１３は、特定されたエントリのバッファ６０７に格納されるデータから比較ブロックサイズ分のデータを削除し、符号化されたデータを出力する（ステップＳ２５０９）。【０２６６】
ステップＳ２５０９の処理は、ステップＳ２５０８の処理と同様の処理である。ただし、Ｄｅｄｕｐペイロード５２０にはバッファ６０７から削除されたデータが含まれ、また、特定されたエントリのｈｅａｄ２２０１は更新されない。【０２６７】
比較ブロックサイズは、副データブロックのサイズより大きい値が設定される。比較ブロックサイズが大きい場合、処理の負荷が軽くなるため、データの分割を高速に行うことができる。一方、比較ブロックサイズが大きい場合、重複排除されるデータの割合が小さくなる。【０２６８】
図２６は、実施例２の重複排除部２１１が転送制御部２１３から副データブロックの検出指示を受け付けた場合に実行する処理を説明するフローチャートである。【０２６９】
重複排除部２１１は、転送制御部２１３から副データブロックの検出指示を受け付けた場合、特定されたエントリのバッファ６０７に格納されるデータを取得する（ステップＳ２６０１）。【０２７０】
重複排除部２１１は、変数Ｓに「１」を設定し（ステップＳ２６０２）、また、データの先頭に所定のサイズのウインドウを配置する（ステップＳ２６０３）。データ分割部２１５は、ウインドウに含まれるデータのハッシュ値を算出する（ステップＳ２６０４）。【０２７１】
具体的には、データ分割部２１５は、変数αと同様の手順に基づいてハッシュ値ＳＡを算出し、第３ハッシュ関数にデータを入力することによってハッシュ値ＳＣを算出する。なお、ウインドウのサイズは、副データブロックのサイズと同一のものとする。【０２７２】
次に、重複排除部２１１は、副検索インデックス２００１を参照し（ステップＳ２６０５）、ハッシュ値ＸＸがハッシュ値ＳＣに一致する要素２４０１が存在するか否かを判定する（ステップＳ２６０６）。【０２７３】
具体的には、重複排除部２１１は、ＳＡ行目の行に含まれる各要素２４０１に格納されるハッシュ値ＸＸと、ハッシュ値ＳＣとを比較する。【０２７４】
ハッシュ値ＸＸがハッシュ値ＳＣに一致する要素２４０１が存在すると判定された場合、重複排除部２１１は、転送制御部２１３に、当該要素２４０１に含まれる添字Ｉを応答として出力する（ステップＳ２６０７）。その後、重複排除部２１１は処理を終了する。【０２７５】
ハッシュ値ＸＸがハッシュ値ＳＣに一致する要素２４０１が存在しないと判定された場合、重複排除部２１１は、変数Ｓが閾値以上であるか否かを判定する（ステップＳ２６０８）。閾値は任意に設定できる。【０２７６】
変数Ｓが閾値以上であると判定された場合、重複排除部２１１は、転送制御部２１３に、「該当データ無し」を応答として出力する（ステップＳ２６０９）。【０２７７】
変数Ｓが閾値より小さいと判定された場合、重複排除部２１１は、変数Ｓに「１」を加算し（ステップＳ２６１０）、また、ウインドウをデータの後方にスライドさせる（ステップＳ２６１１）。その後、重複排除部２１１は、ステップＳ２６０４に戻る。例えば、重複排除部２１１は、ウインドウを１バイト分だけ後方にスライドさせる。【０２７８】
図２７は、実施例２の重複排除部２１１が転送制御部２１３によって呼び出された場合に実行する処理を説明するフローチャートである。【０２７９】
実施例２では、重複排除部２１１は、ステップＳ１５０８の処理が完了した後、副検索インデックス２００１を更新する（ステップＳ２７０１）。その後、重複排除部２１１は、ステップＳ１５０９に進む。具体的には、以下のような処理が実行される。【０２８０】
重複排除部２１１は、データブロックに含まれる副データブロックの中から、対象の副データブロックを選択し、当該副データブロックを第１ハッシュ関数及び第２ハッシュ関数に入力し、ハッシュ値Ｓａ及びハッシュ値Ｓｃを算出する。【０２８１】
重複排除部２１１は、副検索インデックス２００１を参照し、Ｓａ行目に含まれる要素２４０１に空の要素２４０１が存在するか否かを判定する。【０２８２】
Ｓａ行目に含まれる要素２４０１に空の要素２４０１が存在する場合、重複排除部２１１は、空きの要素２４０１のハッシュ値ＸＸにハッシュ値Ｓｃを格納し、添字Ｉにデータブロックにおける対象の副データブロックの位置を示す値を格納する。【０２８３】
Ｓａ行目に含まれる要素２４０１に空の要素２４０１が存在しない場合、重複排除部２１１は、所定のアルゴリズムに基づいて、Ｓａ行目に含まれる要素２４０１の中から値を設定する要素２４０１を一つ選択する。重複排除部２１１は、選択された要素２４０１のハッシュ値ＸＸにハッシュ値Ｓｃを格納し、添字Ｉにデータブロックにおける対象の副データブロックの位置を示す値を格納する。以上がステップＳ２７０１の処理の説明である。【０２８４】
実施例２によれば、実施例１と同様にデータ転送処理の高速化を実現することができる。また、実施例２によれば、転送装置１１０は、比較ブロックサイズの間隔をあけながら副データブロックを用いて、データブロックの境界をバイト単位で調べることができる。データ全体に対してデータブロックの境界を特定する処理が転送処理の速度を律速する場合、比較ブロックサイズのサイズを大きくすることによって、データブロックの境界を特定する処理を間引くことができる。【０２８５】
また、データブロックサイズと独立したパラメータである比較ブロックサイズを用いることによって、バイト単位のデータブロックの境界の特定処理の間引き方を調整できる。データブロックサイズを小さくした場合、データブロックが一致する可能性が高まるため重複排除の効果を高めることができ、比較ブロックサイズを大きくした場合、バイト単位のデータブロックの境界の特定処理が間引かれるため処理を高速化できる。【０２８６】
請求の範囲に記載した以外の発明の観点の代表的なものとして、次のものがあげられる。
（１）端末間で送受信されるデータを転送する複数の転送装置を備えるネットワークシステムであって、
前記複数の転送装置の各々は、
前記端末間のデータの転送処理を制御する転送制御部を有し、
データを分割することによって生成されるデータブロックであって、前記端末間で過去に送信されたデータブロックを管理するデータブロック情報と、前記データブロック情報に格納される前記データブロックを検索するための識別情報を管理する検索インデックスと、を保持し、
前記複数の転送装置は、第１検索インデックス及び第１データブロック情報を保持する第１転送装置、並びに、第２検索インデックス及び第２データブロック情報を保持する第２転送装置を含み、
前記第１転送装置は、
前記第１転送装置に接続する端末から送信データを受信した場合、前記送信データから前記データブロックを生成するための分割処理を実行し、
前記分割処理によって生成された第１データブロックから、前記検索インデックスを参照するための第１識別情報を算出し、
前記第１識別情報に基づいて前記第１検索インデックスを参照して、前記第１データブロックが前記第１データブロック情報に格納されているか否かを判定し、
前記第１データブロックが前記第１データブロック情報に格納されていないと判定された場合、前記第１識別情報及び前記第１データブロックを前記第２転送装置に送信し、
前記第２転送装置は、
前記第１識別情報及び前記第１データブロックを受信した場合、前記第２検索インデックスに前記第１識別情報を格納し、前記第２データブロック情報に前記第１データブロックを格納し、
前記第１転送装置に応答を送信し、
前記第１転送装置は、前記第２転送装置からの応答を受信した場合、前記第１検索インデックスに前記第１識別情報を格納し、前記第１データブロック情報に前記第１データブロックを格納することを特徴とするネットワークシステム。【０２８７】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。また、例えば、上記した実施例は本発明を分かりやすく説明するために構成を詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、実施例の構成の一部について、他の構成に追加、削除、置換することが可能である。【０２８８】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、本発明は、実施例の機能を実現するソフトウェアのプログラムコードによっても実現できる。この場合、プログラムコードを記録した記憶媒体をコンピュータに提供し、そのコンピュータが備えるＣＰＵが記憶媒体に格納されたプログラムコードを読み出す。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施例の機能を実現することになり、そのプログラムコード自体、及びそれを記憶した記憶媒体は本発明を構成することになる。このようなプログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、光ディスク、光磁気ディスク、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどが用いられる。【０２８９】
また、本実施例に記載の機能を実現するプログラムコードは、例えば、アセンブラ、Ｃ／Ｃ＋＋、ｐｅｒｌ、Ｓｈｅｌｌ、ＰＨＰ、Ｊａｖａ等の広範囲のプログラム又はスクリプト言語で実装できる。【０２９０】
さらに、実施例の機能を実現するソフトウェアのプログラムコードを、ネットワークを介して配信することによって、それをコンピュータのハードディスクやメモリ等の記憶手段又はＣＤ−ＲＷ、ＣＤ−Ｒ等の記憶媒体に格納し、コンピュータが備えるＣＰＵが当該記憶手段や当該記憶媒体に格納されたプログラムコードを読み出して実行するようにしてもよい。【０２９１】
上述の実施例において、制御線や情報線は、説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。全ての構成が相互に接続されていてもよい。
【図１】
0006730437.tif 000006
【図２】
0006730437.tif 000007
【図３】
0006730437.tif 000008
【図４】
0006730437.tif 000009
【図５】
0006730437.tif 000010
【図６】
0006730437.tif 000011
【図７】
0006730437.tif 000012
【図８】
0006730437.tif 000013
【図９Ａ】
0006730437.tif 000014
【図９Ｂ】
0006730437.tif 000015
【図９Ｃ】
0006730437.tif 000016
【図１０】
0006730437.tif 000017
【図１１】
0006730437.tif 000018
【図１２】
0006730437.tif 000019
【図１３】
0006730437.tif 000020
【図１４】
0006730437.tif 000021
【図１５】
0006730437.tif 000022
【図１６】
0006730437.tif 000023
【図１７】
0006730437.tif 000024
【図１８】
0006730437.tif 000025
【図１９】
0006730437.tif 000026
【図２０】
0006730437.tif 000027
【図２１】
0006730437.tif 000028
【図２２】
0006730437.tif 000029
【図２３】
0006730437.tif 000030
【図２４】
0006730437.tif 000031
【図２５】
0006730437.tif 000032
【図２６】
0006730437.tif 000033
【図２７】
0006730437.tif 000034