(57)【要約】転送されるデータパケットの目的地アドレス識別子（ＡＤＲ）が解凍され、解凍された目的地アドレス識別子（ＡＤＲ）をロスレスデータ圧縮アルゴリズムを使用して圧縮し、圧縮された目的地アドレス識別子（ＡＤＲ）とルーティングテーブル（４）に格納されたエントリーとを比較する。ルーティングテーブル（４）の各エントリーは、ＩＰルーターの利用可能な転送アドレスに対応する。転送アドレスは目的地アドレス識別子と同一のデータ圧縮アルゴリズムによって圧縮される。目的地アドレス識別子（ＡＤＲ）とルーティングテーブル（４）に格納された圧縮された転送アドレスの１つとの一致が見出された後、ＩＰルーターのスイッチ（６）は、目的地アドレス識別子と一致する各転送アドレスと関連して、各データパケットを出力リンク（ＯＵＴ）にスイッチする。
2005535240.tif 000002
【特許請求の範囲】
【請求項１】
デーダパケットのルーティング方法であって、以下の工程：
（ａ）  転送されるデータパケットからの目的地アドレス識別子（ＡＤＲ）を解凍する工程と、
（ｂ）  該目的地アドレス識別子（ＡＤＲ）とルーティングテーブル（４）のエントリーとを比較する工程と、ここで、各エントリーはルーティングのために利用可能な転送アドレスに対応し、
（ｃ）  該目的地アドレス識別子（ＡＤＲ）と該ルーティングテーブル（４）に格納された該転送アドレスの１つとの一致が工程（ｂ）において見出された場合、該目的地アドレス識別子と一致する該各転送アドレスと関連して、該データパケットを出力リンク（ＯＵＴ）にスイッチする工程とを包含する、方法において、
該工程（ｂ）の実行の前に、該解凍された目的地アドレス識別子（ＡＤＲ）はデータ圧縮アルゴリズムに応じて圧縮され、該転送アドレスは該同一のデータ圧縮アルゴリズムにしたがって圧縮され、かつ該ルーティングテーブル（４）に格納され、そして、
該工程（ｂ）において、該圧縮された目的地アドレス識別子は該ルーティングテーブル（４）に格納された該圧縮された転送アドレスと比較されることを特徴とする、方法。
【請求項２】
前記データ圧縮アルゴリズムは、前記目的地アドレス識別子および前記転送アドレス内の冗長性を、各々いかなる情報内容の損失をも伴わずに削減する、ロスレスデータ圧縮アルゴリズムであることを特徴とする、請求項１に記載の方法。
【請求項３】
前記データ圧縮アルゴリズムは、ハフマンアルゴリズム、演算アルゴリズム、およびレンペル−ジブアルゴリズムよりなる群から選択されることを特徴とする、請求項２に記載の方法。
【請求項４】
前記データ圧縮アルゴリズムの少なくとも１つは、前記目的地アドレス識別子（ＡＤＲ）のデータ特性に依存して適合されていることを特徴とする、請求項１から３のいずれか一項に記載の方法。
【請求項５】
前記目的地アドレス識別子と一致する前記転送アドレスは、前記目的地アドレス識別子と先行する目的地アドレス識別子との類似性を考慮して決定されることを特徴とする、請求項１から４のいずれか一項に記載の方法。
【請求項６】
前記データ圧縮アルゴリズムは、前記目的地アドレス識別子（ＡＤＲ）のシンボルおよび各転送アドレスのシンボルの各々にコード語を割り当てるコード表を使用することを特徴とする、請求項１から５のいずれか一項に記載の方法。
【請求項７】
前記目的地アドレス識別子（ＡＤＲ）の各シンボルは該目的地アドレス識別子（ＡＤＲ）の複数のビットを含み、転送アドレスの各シンボルは該転送アドレスの複数のビットを含むことを特徴とする、請求項６に記載の方法。
【請求項８】
前記目的地アドレス識別子（ＡＤＲ）の各シンボルは該目的地アドレス識別子の連続する４ビットを含み、前記転送アドレスの各シンボルは該転送アドレスの連続する４ビットを含むことを特徴とする、請求項７に記載の方法。
【請求項９】
前記データ圧縮アルゴリズムは、その長さが所定のアドレステーブル内における出現確率に反比例するコード語を、前記目的地アドレス識別子の各シンボルおよび前記転送アドレスの各シンボルに、それぞれ割り当てるように構成されることを特徴とする、請求項６から８のいずれか一項に記載の方法。
【請求項１０】
前記データ圧縮アルゴリズムは、入力データパケットの前記目的地アドレス識別子の出現確率に依存して、前記コード語を、前記目的地アドレス識別子の各シンボルおよび前記転送アドレスの各シンボルに、それぞれ割り当てるように構成されることを特徴とする、請求項６から９のいずれか一項に記載の方法。
【請求項１１】
該方法は、ＩＰｖ６データパケットのルーティングに使用されることを特徴とする、請求項１から１０のいずれか一項に記載の方法。
【請求項１２】
データパケットをルーティングするためのルーティング装置であって、
転送されるデータパケットからの目的地アドレス識別子（ＡＤＲ）を解凍する解凍手段（２）と、
各エントリーがルーティングのために利用可能な転送アドレスに対応する複数のエントリーを格納する、ルーティングテーブル格納手段（４）と、
該目的地アドレス識別子（ＡＤＲ）と該転送アドレスの１つとの一致を見出すために、該目的地アドレス識別子（ＡＤＲ）と該ルーティングテーブル格納手段（４）内に格納された該エントリーとを比較するルーティングユニット（３）と、
該目的地アドレス識別子（ＡＤＲ）と一致する該各転送アドレスと関連して、該データパケットを出力リンク（ＯＵＴ）にスイッチするスイッチ手段（６）とを含む、ルーティング装置において、
該解凍手段（２）によって解凍された目的地アドレス識別子（ＡＤＲ）をデータ圧縮アルゴリズムにしたがって圧縮する第１のアドレス圧縮手段（７）と、
該転送アドレスを該データ圧縮アルゴリズムにしたがって圧縮し、かつ該圧縮された送アドレスを該ルーティングテーブル格納手段（４）に格納する第２のアドレス圧縮手段（８）とを備え、
該ルーティングユニット（３）が、該圧縮された目的地アドレス識別子と、該ルーティングテーブル（４）に格納された該圧縮された転送アドレスとを比較するように構成されてなることを特徴とする、ルーティング装置。
【請求項１３】
前記第１および第２の前記圧縮手段（７，８）は、前記目的地アドレス識別子および前記転送アドレス内の冗長性を、各々いかなる情報内容の損失をも伴わずに削減する、ロスレスデータ圧縮アルゴリズムを使用するように構成されることを特徴とする、請求項１２に記載のルーティング装置。
【請求項１４】
前記第１および第２の前記圧縮手段（７，８）は、ハフマンアルゴリズム、演算アルゴリズム、およびレンペル−ジブアルゴリズムよりなる群から選択されるデータ圧縮アルゴリズムを使用するように構成されることを特徴とする、請求項１３に記載のルーティング装置。
【請求項１５】
前記第１および第２の前記圧縮手段（７，８）の少なくとも１つを、前記解凍手段（２）によって解凍された前記目的地アドレス識別子（ＡＤＲ）のデータ特性に依存して適合する圧縮パラメータ適合手段（９）を備えることを特徴とする、請求項１２から１４のいずれか一項に記載のルーティング装置。
【請求項１６】
前記ルーティングユニット（３）と前記第１の圧縮手段（７）との間に、時間領域内の冗長性を低減するフィードバック接続を備えることを特徴とする、請求項１２から１５のいずれか一項に記載のルーティング装置。
【請求項１７】
該ルーティング装置は、請求項１から１１のいずれか一項に記載のデーダパケットのルーティング方法を実行するために構成されることを特徴とする、請求項１２から１６のいずれか一項に記載のルーティング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データパケットのルーティング方法およびそのルーティング装置に関する。特に、本発明は、ＩＰｖ６プロトコル（「インターネットプロトコル  バージョン６」）に準拠するデータパケットのルーティング方法およびそのルーティング装置に関する。
【背景技術】
【０００２】
インターネットデータ転送システムの基本構成の１つとして、ＩＰルーター（「インターネットプロトコル」）は、入力データパケットのための転送決定を行う。すなわち、ＩＰルーターは、パケットヘッダー内において運ばれる目的地アドレス識別子をチェックし、該目的地アドレス識別子を、データパケットがそれを介して送られる次の出力ポートあるいは出力リンクへ導く。例えば、入力データパケットの目的地アドレス識別子に依存して、ＩＰルーターは、各出力リンクを経由した転送のためのＮｅｘｔ  ＨｏｐルーターあるいはＥｇｒｅｓｓＴＭにデータパケットを導き得る。コンピュータネットワークにおいて、ＮＨＲＰプロトコル（「Ｎｅｘｔ  Ｈｏｐ  Ｒｅｓｏｌｕｓｉｏｎ  Ｐｒｏｔｏｃｏｌ」）は、他のコンピュータへのコンピュータ送信データが受信コンピュータへの最も直接的なルートを学習し得るように使用可能なプロトコルである。ＥｇｒｅｓｓＴＭポートは、最新のＩＰルーターに使用される新型のポートである。
【０００３】
次に、データのルーティングが、従来技術によるＩＰルーターの概略的構成を示す図７を参照して簡潔に説明される。
【０００４】
図７に示されるＩＰルーターは、Ｎ個の入力リンクあるいは入力ポート（ＩＮ１〜ＩＮＮ）を経由した複数の入力データパケットを受信する入力ブロック１を含む。入力ブロック１は入力キューとして機能し、受信データパケットを「ファーストインファーストアウト（ＦＩＦＯ）」方式によって出力する。パケットヘッダーに含まれる目的地アドレス識別子を得るために、転送される各データパケットからのパケットヘッダーを解凍するヘッダー解凍ブロック２が設けられる。さらに、データパケットは、スイッチとして機能する出力ブロック６に転送される。ルーティングテーブル４は、可能あるいは利用可能な全ての転送アドレスおよびルーターの各出力リンク／ポートを格納する。すなわち、ルーティングテーブルは複数のエントリーを含む。各エントリーは、データパケットがＩＰルーターによって転送され得る各転送アドレスに対応する。ルーティングテーブル４は、ルーティングプロトコルを用いて、ブロック５によって生成されかつ更新される。図７において、ルーティング更新は、サインＵＰＤを参照して指示される。ルーティングユニット３は、ヘッダー解凍ブロック２によって解凍された目的地アドレス識別子を受信し、かつ該目的地アドレス識別子を、ルーティングテーブル４内における一致を検索するためのキーとして使用する。すなわち、ルーティングユニット３は、目的地アドレス識別子と、ルーティングテーブル４内に格納された各転送アドレスに対応する全てのエントリーとを比較する。ルーティングユニット３が目的地アドレス識別子とルーティングテーブル４内に格納された１つの転送アドレスとの一致を見出した場合、各出力リンク／ポート番号はスイッチ６に転送され、スイッチ６は、Ｍ個の複数の出力リンク／ポート（ＯＵＴ１〜ＯＵＴＭ）の各１つにデータパケットをスイッチする。
【０００５】
そのため、ルーティングユニット３が、ヘッダー解凍ブロック２によって解凍された目的地アドレス識別子とルーティングテーブル４内に格納された少なくとも１つのエントリーとの一致を見出す限りにおいて、各データパケットは出力リンク（ＯＵＴ１〜ＯＵＴＭ）の１つにスイッチされ得る。しかしながら、ルーティングテーブル４内に一致がない場合、スイッチ６はデータパケットを出力リンクの１つにスイッチすることができず、データパケットは目的地に転送されない。
【０００６】
図７に示されるタイプのＩＰルーターに関連するコストおよびその機能がルーティングテーブル４の大きさに依存することは、明らかである。特に、ルーティングテーブル４が大きい場合、ルーティングテーブル４はシリコンを消費し、照合手順は時間および電力を消費する。
【０００７】
この問題は、特に、インターネットの急速な拡張によってますます深刻化している。最近導入されたＩＰｖ６プロトコルは、１２８ビットのアドレス識別子を含む。理論上、ｎビットのアドレス識別子に対して、ルーティングテーブル４は２ｎまでのエントリーを有し得る。そのため、ＩＰｖ６プロトコルに関して、そのように大きなルーティングテーブル４を格納するための莫大な記憶容量が必要である。しかしながら、そのような大きなルーティングテーブル４は、照合手順を実益的でないものにする。そのため、ルーティングテーブル照合は、今日のルーターにおいて、主要な障害と見なされている。
【０００８】
ルーティングテーブル照合の最も直接的な方法は、線形検索である。すなわち、アドレス識別子とルーティングテーブル内のエントリーの１つとの一致が確認されるまで、入力データパケットの目的地アドレス識別子とルーティングテーブルの各エントリーとを比較することである。このアプローチは簡単ではあるが、その低機能性のために、ほとんど実用されていない。
【０００９】
照合手順をスピードアップするために、様々な方法が使用されている。その最も重要な方法は、いわゆるコンテンツアドレスメモリ（ＣＡＭ）の使用、ツリーデータ構造に従った検索、およびいわゆるハッシュ法の使用である。これらの既知の方法の各々は、その長所および短所を有する。しかしながら、これら方法の全ては、目的地アドレス識別子のオリジナルなデータ領域の検索に基づいている。そのため、これら方法の全ては、比較的複雑な検索手順および比較的大きなルーティングテーブルサイズを必要とする。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
従って、本発明の目的は、ルーティングテーブルサイズの低減を可能にし、それにより各目的地アドレス識別子とルーティングテーブル内に格納されたエントリーとの間の一致検索を速め、かつルーティングテーブルに関連するコストを削減する、データパケットのルーティング方法およびルーティング装置を提供することにある。
【課題を解決するための手段】
【００１１】
本発明によれば、この目的は、請求項１に規定されたデータパケットのルーティング方法および請求項１２に規定されたデータパケットのルーティングのためのルーティング装置によって達成される。従属請求項は、本発明の好ましくかつ有利な実施形態を規定する。
【００１２】
本発明の基本理念は、ルーティングテーブル照合が圧縮領域（ｃｏｍｐｒｅｓｓｅｄ  ｄｏｍａｉｎ）において行われ得ることにある。すなわち、入力データパケットの照合動作が実行される前に、まず、入力データパケットの目的地アドレス識別子が、冗長性を除去するために圧縮される。次いで、照合動作が、圧縮された入力データパケットをルーティングテーブルに関連するキーとして、実行される。その際、ルーティングテーブルのエントリーも、入力データパケットの目的地アドレス識別子と同様な方法によって圧縮される。
【００１３】
そのため、照合動作がより小規模のルーティングテーブルに関連して実行され得、それにより、各ルーターに関連するコストおよび電力が削減され得るとともに、ルーターの性能が改善され得る。
【００１４】
目的地アドレス識別子の圧縮およびルーティングテーブルの転送アドレス情報エントリーの圧縮は、１つの同一のデータ圧縮アルゴリズムにしたがって行われる。特に、いかなる情報内容の犠牲をも伴わずにデータ内の冗長性を低減する、いわゆるロスレス（ｌｏｓｓｌｅｓｓ）データ圧縮アルゴリズムが使用される。ロスレス圧縮に使用され得る一般的なアルゴリズムおよびその変形が存在する。最も有力な例は、ハフマンアルゴリズム、演算アルゴリズム、およびレンペル−ジブアルゴリズムファミリーである。
【００１５】
圧縮効率はルーターが関わる目的地アドレス識別子のデータ特性に依存するため、各圧縮手段、例えばコード表は、該データ特性にしたがって割り当てられ、あるいは適合される必要がある。
【００１６】
データ圧縮アルゴリズムに関しては、各コード語（ｃｏｄｅ  ｗｏｒｄ）に圧縮されるアドレス情報のシンボルを割り当てるコード表を利用するデータ圧縮アルゴリズムが使用される。各コード語は、好ましくは、所定のアドレステーブル、例えばＩＰｖ６アドレステーブル内におけるシンボルの出現確率に反比例する長さを有する。勿論、ルーター入力におけるシンボルの出現確率もまた、全体性能の改善のために考慮され得る。
【００１７】
上記データ圧縮アルゴリズムの適用の際に、目的地アドレス識別子におけるシンボルあるいはビット組み合わせの出現分布の冗長性が考慮される。そのため、一種の空間的な冗長性が除去され得る。しかしながら、他の冗長性、例えば、連続的なデータパケットのための目的地アドレス識別子に類似性がある場合、時間領域での冗長性が存在し得る。そのような時間領域での冗長性も同様に除去するために、好ましくは、ルーティングユニットから目的地アドレス識別子を圧縮のために使用される圧縮ユニットへのフィードバックが行われる。このフィードバックは、そのような時間領域での冗長性を除去するため、およびデータパケットシーケンス内での複数の目的地アドレス識別子の類似性を考慮するために行われる。
【００１８】
本発明は好ましくはＩＰｖ６データパケットのルーティングに使用され得るが、本発明はこの好ましい応用分野に限られるものではなく、勿論、全種類のデータパケットに使用され得る。
【発明を実施するための最良の形態】
【００１９】
以下において、本発明の好ましい実施形態が、添付図面を参照して詳細に説明される。
【００２０】
実際、多くの冗長性が、ＩＰルーターによって処理される目的地アドレス識別子内に含まれ得る。ＩＰアドレス内にどれくらいの冗長性が含まれ得るかを調査するために、ＩＰｖ６アドレスのクワッド（ｑｕａｄ）すなわち４ビット内に含まれる情報を表現するためには現実に何ビットが必要かを、種々のアドレステーブルを用いてテストする実験が行われた。
【００２１】
図６において、テスト結果がＩＰｖ６アドレステーブルサイズに対応して示される。グラフ（ｉ）は、ＩＰｖ６アドレスの各４ビット−クワッドがハフマンエンコーダを使用して圧縮された場合のテスト結果を示す。すなわち、グラフ（ｉ）は、ハフマン符号化の後に得られる平均化されたビット数を、アドレステーブルサイズに対応して示す。さらに、グラフ（ｉｉ）は、クワッド毎のエントロピービット数を、アドレステーブルサイズに対応して示す。すなわち、グラフ（ｉｉ）は、理論的結果、すなわちクワッドの情報を運ぶために実際に必要なビット数を示す。図６から、４ビットの代りに、必要なビット数は１．５〜２の間で変化することが確認される。アドレステーブルサイズが３×１０６を超える場合、各アドレス情報を運ぶために実際に必要なビット数は、ほぼ１．８の一定値に達する。これは、圧縮可能性がほぼ（少なくとも）５０％であることを意味する。この実験においては、アドレス識別子内の一部のシンボル（ビット組み合わせ）の出現分布の冗長性のみが考慮されたことに留意すべきである。これは一種の空間的冗長性に対応する。他の種類の冗長性、例えば、連続的に処理されるデータパケットのためのアドレス識別子にかなりの類似性がある場合、時間領域での冗長性が存在し得る。
【００２２】
一般的な照合方法にとって、全種類の冗長性を完全に考慮することは容易ではない。しかしながら、以下に詳述されるアプローチは、ルーティングテーブル照合技術とデータ圧縮技術との結合を可能にする。ルーティングテーブル照合技術はコンパクトなアドレステーブル内での検索動作に関連し、一方、データ圧縮技術は全種の冗長可能性に関わる。両技術の利点の結合によって、ルーティングテーブル照合にかかる問題の好適な解決が達成され得る。
【００２３】
図１は、本発明の好ましい実施形態によるＩＰルーターの構成を示す。図７に示される要素および既に説明された要素は、図７と同一の部材番号で示される。繰り返しを避けるために、図７に関連する記載に対して参照がなされ得る。
【００２４】
図１のＩＰルーターは、圧縮されたアドレス領域において動作する点において、図７に示されたＩＰルーターと異なる。第１のアドレス圧縮器７が、ヘッダー解凍ブロック２とルーティングユニット３との間の経路に配置される。このアドレス圧縮器７は、ヘッダー解凍ブロック２によって提供された、ＩＰｖ６目的地アドレス識別子用に１２８ビットを含む目的地アドレス識別子を、例えばデータ圧縮アルゴリズムを使用する平均して短縮化された形式に変換する。圧縮された目的地アドレス識別子は、次に、ルーティングユニット３に転送され、ルーティングテーブル４に関連した照合動作のためのキーとして使用される。さらに、同一のアドレス圧縮器８が、ルーティングテーブル４を生成および更新するブロック５とルーティングテーブル４との間の経路に配置される。それにより、アドレス圧縮器８は、アドレス圧縮器７と同一のデータ圧縮アルゴリズムを使用して、転送アドレス情報を圧縮された形でルーティングテーブル４に格納する。それにより、ルーティングテーブル４は非常にコンパクトな形で提供され、また、特に、ルーティングテーブル４は、アドレス圧縮器７から出力され、かつルーティングユニット３によって照合動作のためのキーとして使用される圧縮された目的地アドレス識別子に合致する。ルーティングユニット３は、圧縮された目的地アドレス識別子とルーティングテーブル４内に格納された圧縮された転送アドレスの１つとの一致を検索するために、従来の方法を使用し得る。
【００２５】
アドレス圧縮器（７，８）によって使用されるデータ圧縮アルゴリズムは、特にいわゆるロスレスデータ圧縮アルゴリズムである。そのようなロスレスデータ圧縮アルゴリズムは、いかなる情報内容の犠牲をも伴わずにデータ内の冗長性を低減する。そのようなロスレス圧縮に使用され得る一般的なアルゴリズムおよびその変形が存在する。最も有力な例は、ハフマンアルゴリズム、演算アルゴリズム、およびレンペル−ジブアルゴリズムファミリーである。
【００２６】
圧縮効率はルーターが関わる目的地アドレス識別子のデータ特性に依存するため、アドレス圧縮器（７，８）のパラメータの少なくとも一部、例えばアドレス圧縮器によって使用されるコード表は、これらデータ特性にしたがってあるいは依存して割り当てられ、または適合される必要がある。そのため、図１に示されるＩＰルーターは圧縮パラメータブロック９を含む。圧縮パラメータブロック９は、ヘッダー解凍ブロック２から、各目的地アドレス識別子のデータ特性に関する情報を収集し、かつアドレス圧縮器（７，８）によって使用されるデータ圧縮アルゴリズムのための圧縮パラメータを計算する。
【００２７】
既に上記したように、アドレス圧縮器（７，８）によって実施されたアドレス圧縮は、各目的地アドレス識別子内の一部のシンボル（ビット組み合わせ）の出現分布の冗長性を考慮する。しかしながら、複数の連続するデータパケットの目的地アドレス識別子の類似性に関する他の種類の冗長性が存在し得る。そのような時間領域での冗長性も同様に除去するために、図１に示されるＩＰルーターは、ルーティングユニット３から、目的地アドレス識別子の圧縮のために使用されるドレス圧縮器７へのフィードバック接続を含む。そのようなルーティングユニット３からドレス圧縮器７へのフィードバックによって、データパケットシーケンス内での目的地アドレス識別子の類似性が考慮され得る。これは、例えば、転送アドレスがルーティングユニット３によって決定される新しい目的地アドレス識別子が各先行する目的地アドレス識別子に非常に類似する場合、その事前に決定される接続アドレスに基づき、スイッチ６に対する転送を決定することによってなされ得る。
【００２８】
図２は、図１に示されるアドレス圧縮器７、ルーティングユニット３、およびルーティングテーブル４の実施例を示す。特に、この実施例は、ＩＰｖ６データパケットを処理するためのアーキテクチャーに対応する。図２は各要素のハードウェア図を示すが、勿論、アーキテクチャーはソフトウェア内の異なるハードウェア、あるいはハードウェアとハードウェアの組み合わせによっても実施され得る。
【００２９】
図２に示されるアドレス処理器７は、図１に示されるヘッダー解凍ブロック２から圧縮された目的地アドレス識別子ＡＤＲを受け取る。ＩＰｖ６データパケットの場合、目的地アドレス識別子ＡＤＲは、ブロック１０によって３２個の４ビット−クワッドに分割される１２８ビットを含む。次に、各クワッドは、例えば図３に示されたコード表を使用して、数ビットを含むコード語に変換される。これはコード化ブロック１３によって行われる。
【００３０】
図３に示されるコード表は、４ビットのクワッドの１６進数値を示す第１列（Ａ）を含む。第２列（Ｂ）には、各クワッド値に割り当てられた各２進数コードが示される。さらに第３列（Ｃ）には、各コード語のコード長が示される。
【００３１】
コード化ブロック１３によって出力された３２個のコード語は、次に、圧縮された目的地アドレスを得るために、アドレス生成ブロック１４によって結合される。圧縮された目的地アドレスは、次にルーティングユニット３の第１のバッファ２０にバッファされる。さらに、図３の第３列（Ｃ）に対応して各コード長テーブルを格納するブロック１１、および各アドレス識別子ＡＤＲのために、ブロック１１によって出力されるコード長を合計するブロック１２が存在する。この結果は、次に、第２のバッファ１５にバッファされる。そのため、バッファ１５は、各目的地アドレス識別子ＡＤＲのためのコード語の長さの合計、すなわち、圧縮されたアドレス識別子の長さを格納する。一方、バッファ２０は、各目的地アドレス識別子ＡＤＲに割り当てられたコード語の組み合わせ、すなわち圧縮されたアドレス識別子を格納する。バッファ１５に格納される結果は、図３に示された列（Ｃ）に基づいてブロック１２によって計算され、一方、バッファ２０に格納される結果は、図３に示された列（Ｂ）に基づいてブロック１４によって決定される。
【００３２】
図４は、図３に示されたコード表にしたがって圧縮された目的地アドレス識別子ＡＤＲの例を示す。図３のコード表によれば、このアドレスは５６ビットからなる。各「Ｆ」値は圧縮されたアドレスの１ビットとなり、各「Ｅ」値は圧縮されたアドレスの１ビットとなり、各「Ｄ」値は圧縮されたアドレスの３ビットとなり、「Ｂ」値は圧縮されたアドレスの５ビットとなり、「７」値もまた圧縮されたアドレスの５ビットとなり、「４」値は圧縮されたアドレスの６ビットとなり、「３」値もまた圧縮されたアドレスの６ビットとなる。そのため、図３のコード表によって決定される圧縮アドレスは、入力目的地アドレスの、全ての「Ｆ」値に対する２２×１＝２２ビット、「４」値に対する１×６＝６ビット、「Ｂ」値に対する１×５＝５ビット、「３」値に対する１×６＝６ビット、「７」値に対する１×５＝５ビット、全ての「Ｅ」値に対する３×１＝３ビット、および全ての「Ｄ」値に対する３×３＝９ビットを含む。これにより、圧縮されたアドレスは全体で５６ビットを含む。
【００３３】
図３に示されるコード表は、図２に示されるアドレス圧縮器７のブロック（１１、１３）によって使用される圧縮パラメータＣＰＡＰを出力する、図１に示される圧縮パラメータブロック９によって生成される。特に、図３に示されるコード表は、ハフマンエンコーダによって実施されるコードに対応する。この場合、ハフマンエンコーダは、各シンボル（クワッド）に、８７２６４０のエントリー（１３９６２２４０バイト）を含むＩＰｖ６アドレステーブル内における各シンボルの出現確率に反比例する長さを有するコード語を割り当てる。ソフトウェアあるいはハードウェア内におけるそのようなハフマンエンコーダの実施は、データ圧縮を扱う多くの文書あるいは出版物に見出される。そのため、そのようなハフマンエンコーダの詳細、あるいはハフマンエンコーダを用いて実施される圧縮パラメータブロック９の詳細は、考慮から省く。
【００３４】
図２に示されるルーティングテーブル４は、同一の圧縮パラメータ、すなわちアドレス圧縮器７によって使用されるのと同一のコード表を用いて圧縮された、可能な転送アドレスによって構成される。これら圧縮された転送アドレスは、その長さに応じてサブテーブルに配置される。圧縮されたアドレス長ｂ０〜ｂＮ、エントリーの番号ｎ０〜ｎＮ、および各テーブルのベースアドレスａ０〜ａＮは、リーディング（ｌｅａｄｉｎｇ）テーブル２７内に格納される。ルーティングユニット３は、圧縮されたルーティングテーブル４内において圧縮された入力目的地アドレスのための一致を見出すために動作する。これは以下のように実施される。
【００３５】
ブロック１７は、リーディングテーブル２７内のエントリーを読み出し、かつそのアドレス長ｂｉを長さ比較器１６に送る。長さ比較器１６は、バッファ１５に格納された圧縮入力アドレス長と、ブロック１７によって読み出された各エントリーとを比較する。長さ比較器１６は、一致するサブテーブルを見つけるために、圧縮入力アドレス長と、リーディングテーブル２７内に格納された各アドレス長ｂｉとを比較する。長さ比較器１６によって一致が見出された場合、ブロック１８がリセットされる。その後、ブロック１８は見出されたサブテーブルのベースアドレスａｉをブロック２４に送り、かつ続くアドレス照合動作のために、各サブテーブルのエントリー番号ｎｉにカウンタ２３を初期化する。
【００３６】
次に、ルーティングユニット３は、バッファ２０に格納された圧縮入力アドレスと、上記検索動作によって決定されたサブテーブルに格納された圧縮アドレスＣｊ，ｉとを比較する。ブロック２４は各サブテーブル２８からエントリーを読み出し、かつアドレスＣｊ，ｉをアドレス比較器２１に送る。アドレス比較器２１は、バッファ２０内の圧縮入力アドレスと、ブロック２４によって提供された転送アドレスとを比較する。アドレス比較器２１によって実施される各比較動作によって、ＡＮＤゲート２２はカウンタ２３をデクリメントする。それにより、アドレス比較器２１の比較動作は、圧縮された目的地アドレスとサブテーブル２８内に格納された圧縮された転送アドレスの１つとの間の一致が見出されるまで、あるいはカウンタ２３がゼロまでデクリメントされるまで、繰り返される。１ビットラッチ２５はアドレス比較器２１の最後の比較結果を保持する。圧縮された目的地アドレスとサブテーブル２８内に格納された圧縮された転送アドレスの１つとの間の一致があった場合、１ビットラッチ２５は、該１ビットラッチ２５の出力信号とカウンタ２３の反転出力信号との間の論理ＡＮＤ動作を行う論理ゲート２６に対する信号を生成する。カウンタ２３の出力信号は、カウンタ２３の値がゼロに達しない限り、ローレベルを有する。それにより、論理ゲート２６の出力信号ＶＡＬＩＤは、ブロック２４によって現在、処理されている出力ポート番号あるいは出力リンク番号ｏｊ，ｉが有効か否かを示し、かつスイッチ６（図１参照）の転送動作のために使用され得る。ここで、指標「ｉ」は各サブテーブルの番号を示し、一方、指標「ｊ」はサブテーブル内の各エントリーの番号を示す。
【００３７】
ルーティングユニット３のさらなるブロック１９は、バッファ２０に格納されている、コード化されたあるいは圧縮された入力アドレスのバイト調節動作を、残りビットへのゼロの充填によって行う。
【００３８】
図２に示された実施例によれば、各目的地アドレス識別子ＡＤＲは４ビットシンボルに分割される。しかしながら、目的地アドレスは、勿論、他の態様に分割され得る。さらに、図３に示されるテーブルは、所定のアドレステーブル内の、本例の場合ＩＰｖ６アドレステーブル内の各シンボル（クワッド）の出現確率のみによって決定される。しかしながら、ルーター入力におけるシンボルの出現確率もまた、ＩＰルーターの性能の改善のために考慮され得る。最後に、上記したように、本発明はハフマンコードに限定されるものではない。任意のロスレスデータ圧縮アルゴリズムが、アドレス圧縮器（７，８）、ルーティングユニット３、およびルーティングテーブル４の実施のために使用され得る。
【００３９】
圧縮された目的地アドレス識別子および圧縮された転送アドレスのモデルが、様々なサイズの複数のＩＰｖ６アドレステーブルを使用してテストされた。図５は、そのテスト結果を示す。列（Ａ）は各ＩＰｖ６アドレステーブルの番号を示し、列（Ｂ）は各ＩＰｖ６アドレステーブルのエントリーの数を含み、列（Ｃ）は各ＩＰｖ６アドレステーブルのオリジナルサイズ(バイト)を含み、列（Ｄ）はＩＰｖ６アドレステーブルの圧縮サイズ（バイト）を含み、列（Ｅ）は達成された圧縮率（％）を示す。認められるように、ルーティングテーブルの要求サイズは、劇的に低減され得る。これは、ＩＰルーターの改善された性能を導き、かつ照合動作のためのメモリーおよび電力の節約に役立つ。テスト結果は、図６の論理的分析と一致する。
【図面の簡単な説明】
【００４０】
【図１】本発明の好ましい一実施形態によるＩＰルーターを概略的に示す図である。
【図２】ハフマンデータ圧縮アルゴリズムを使用した、図１に示されるアドレス圧縮器、ルーティングユニットおよびルーティングテーブルの実施例を示す図である。
【図３】図２に示されるアドレス圧縮器のためのコード表の例を示す図である。
【図４】図３に示されたコード表にしたがってアドレス圧縮器によって処理される１６進数のアドレスの例を示す図である。
【図５】様々なＩＰｖ６アドレステーブルの圧縮率に関するテスト結果を表すテーブルを示す図である。
【図６】ＩＰｖ６アドレスにおける、バイト毎の平均ビット数とエントリービット数との依存性を示す図である。
【図７】従来技術によるＩＰルーターを概略的に示す図である。
【図１】
2005535240.tif 000003
【図２】
2005535240.tif 000004
【図３】
2005535240.tif 000005
【図４】
2005535240.tif 000006
【図５】
2005535240.tif 000007
【図６】
2005535240.tif 000008
【図７】
2005535240.tif 000009
【国際調査報告】
2005535240.tif 000010
2005535240.tif 000011
2005535240.tif 000012