バイナリ識別子の圧縮方法、ハッシャ、及び、コンピュータ・プログラム
【課題】バイナリ識別子の圧縮を提供する。
【解決手段】１度に４バイトの累積ＸＯＲベースのプリハッシュに基づき、ハッシュ・キーに必要な特性を保ちながら、大きな（１６バイト）ＩＰｖ６アドレスを通例の（４バイト）アドレス・フィールドに圧縮することについて記載する。
【解決手段】１度に４バイトの累積ＸＯＲベースのプリハッシュに基づき、ハッシュ・キーに必要な特性を保ちながら、大きな（１６バイト）ＩＰｖ６アドレスを通例の（４バイト）アドレス・フィールドに圧縮することについて記載する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バイナリ識別子、特にＩＰｖ６アドレスの圧縮に関する。
【背景技術】
【０００２】
インターネット・プロトコル・バージョン４（ＩＰｖ４：Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ，Ｖｅｒｓｉｏｎ４）は、その原型の３２ビットでインターネットのアドレス指定の機能を定義し、合計２３２、すなわち４３億の可能なアドレスを与えている。ネットワークの爆発的な成長および世界的な増設は、ＩＰｖ４のもとで利用可能なアドレスがすべて、２０１２年までに枯渇することを意味した。
【０００３】
そこで、ＩＰｖ４に代わるＩＰｖ６プロトコルが定義されており、３．４×１０３８のアドレスという理論上の容量の１２８ビット・アドレスを規定することによって、特にＩＰｖ４の特定の欠点に対処する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
それにもかかわらず、実際のところ、既存のハードウェアおよびソフトウェアの大部分は、ＩＰｖ４技術に基づいている。新たなハードウェアおよびソフトウェアがＩＰｖ６と互換性を持つように設計されている場合であっても、できる限り既存のライブラリおよびルーチンを再利用することが望ましい。
【課題を解決するための手段】
【０００５】
本発明によれば、添付の独立請求項１に記載の、圧縮されたバイナリ識別子（ｃｏｍｐａｃｔｅｄ ｂｉｎａｒｙ ｉｄｅｎｔｉｆｉｅｒ）を生成する方法と、添付の請求項１０に記載の圧縮器（ｃｏｍｐａｃｔｏｒ）と、添付の請求項１１に記載のハッシャ（ｈａｓｈｅｒ）と、添付の請求項１２に記載のコンピュータ・プログラムとが提供される。
【０００６】
好適な実施形態が、添付の従属請求項において定義される。
【０００７】
１度に４バイトの累積ＸＯＲベースのプリハッシュ（ｐｒｅｈａｓｈｉｎｇ）に基づき、ハッシュ・キーに必要な特性を保ちながら、大きい（１６バイト）ＩＰｖ６アドレスを通例の（４バイト）アドレス・フィールドに圧縮することについて記載する。
【０００８】
これは、例えば、「５タプル」のようなキーを典型的には受け入れるハッシャにおいてＩＰｖ６アドレスをサポートするために使用されるロジックおよびシリコン面積を最小化することによる利点を提供する。このようなキーは、パケット・ヘッダから抽出される５つのフィールドを用いてアセンブル（ａｓｓｅｍｂｌｅ）され、これらは共に、そのパケットが属するパケット・フローを非常によく表す。ＴＣＰ接続を識別するために使用される５タプルの典型的な例は、次のアセンブリである。
【０００９】
−ＩＰソース・アドレス
−ＩＰ宛先アドレス
−プロトコル・バイト
−ＴＣＰソース・ポート
−ＴＣＰ宛先ポート
【００１０】
パケットが、ＩＰｖ６レイヤ３ヘッダを有する場合、実装問題が生じる。４バイトＩＰアドレスを運ぶＩＰｖ４ヘッダと対照的に、ＩＰｖ６ヘッダは、１６バイトＩＰアドレスを運ぶ。これは、５タプル・キーが、ＩＰｖ４レイヤ３ヘッダよりもＩＰｖ６に関してずっと大きくなるということを意味する。
【００１１】
−ＩＰｖ４＝ＩＰ ＳＡ（４Ｂ）＋ＩＰ ＤＡ（４Ｂ）＋プロトコル（１Ｂ）＋ＴＣＰ ＳＰ（２Ｂ）＋ＴＣＰ ＤＰ（２Ｂ）＝１３バイト
−ＩＰｖ６＝ＩＰ ＳＡ（１６Ｂ）＋ＩＰ ＤＡ（１６Ｂ）＋プロトコル（１Ｂ）＋ＴＣＰ ＳＰ（２Ｂ）＋ＴＣＰ ＤＰ（２Ｂ）＝３７バイト
【００１２】
３７バイトの入力レジスタを備えるハッシャの実装は、シリコン面積の点ではるかに高価である。これは、より大きなＩＰｖ６アドレスを保持するのに必要な、２４×８＝１９２の追加のラッチだけではなく、１３×８＝１０４に対し３７×８＝２９６の入力から始まるはるかに大きな組み合わせロジック・コーン（ｃｏｍｂｉｎａｔｏｒｉａｌ ｃｏｎｅ ｏｆ ｌｏｇｉｃ）が原因でもある。
【００１３】
ハッシャを構成するロジック・コーンのサイズは、その入力の数と線形でないため、２つのソリューション間の面積比は、少なくとも４倍である。
【００１４】
本開示で提案されるソリューションは、もとのキー入力レジスタおよびロジック・コーンを維持するために、ＩＰｖ６アドレスをＩＰｖ４サイズに縮小するようＩＰｖ６アドレスの予備処理を実行することである。
【００１５】
図面および詳細な説明を検討すれば、本発明のさらなる利点が当業者には明白となる。任意のさらなる利点が、本願明細書に包含されるものとする。
【図面の簡単な説明】
【００１６】
【図１】第１の実施形態によるネットワーク・プロセッサのハッシャを示す。
【図２】標準のハッシャ入力構造を示す。
【図３】実施形態による圧縮器アレイのコンポーネントの詳細を示す。
【図４】本発明による方法のステップを示す。
【図５】イーサネット（Ｒ）パケットにカプセル化されたＩＰｖ６パケットの一部を表す。
【図６】第１の実施形態による、データの処理のサポートにおいて、パーサ制御モジュールにてとられるとよいステップを表すフロー図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について、添付の図面を参照して例として記載する。図面では、同じ参照符号は同様の構成要素を示す。
【００１８】
上記に鑑み、圧縮されたバイナリ識別子を使用できるように、ＩＰｖ６アドレスなどの圧縮されたバイナリ識別子を生成することを提案する。
【００１９】
提案される圧縮プロセスは、非決定性であり、すなわち、いくつかの異なるバイナリ識別子が同じ圧縮された識別子をもたらすことがあり得、バイナリ識別子の圧縮された識別子からもとのバイナリ識別子を再構成することは不可能であるということが、この提案される圧縮プロセスの特徴である。この特性により、特定の用途では、本発明による圧縮された識別子の使用が不可能となるかもしれないが、それでも、特許請求される手法が十分である用途は多数ある。特に、特許請求される手法は、アイデンティティ情報に基づくパケットまたは他のデータの特徴付けであって、一意のアイデンティティのレベルまでは粒度が細かくない、該特徴付けが望まれる多数の用途に適する。そのような用途の例には、以下により詳しく説明する、パケット識別子およびＩＰフィルタがある。
【００２０】
上記のように、本発明が有用な例の１つは、ネットワーク・プロセッサにおいてパケット・フローを識別するハッシュ関数などのハッシュ関数においてである。ハッシュ関数の柔軟性は、典型的には、２つのパラメータによって定義される。
【００２１】
−ハッシュ・キーがアセンブルされる方法
−ハッシュ関数自体の特性
【００２２】
これら２つの特性の変化を利用して柔軟性のあるハッシャを実装するには、いくつかのトレード・オフがあることが多い。
【００２３】
従来、ハッシャのソフトウェア実装においてキー・アセンブリ（ｋｅｙ ａｓｓｅｍｂｌｙ）の柔軟性が好まれてきたが、柔軟性のあるハッシュ関数には、通常、ハッシャの何らかの形の構成可能なハードウェア実装が必要である。
【００２４】
ハッシャの柔軟性の各側面には、通常、以下の限界がある。
【００２５】
−ハッシュ・キーの構築に複雑なパターンが必要な場合、特に、キー・アセンブリがビットレベルの粒度で行われる場合、ソフトウェア・キー・アセンブリに性能限界がある。
−典型的には単純なＸＯＲゲートを用いて実装される基本のハッシング構成要素を補完する構成ロジックが原因で、構成可能なハードウェア・ハッシュ関数にはシリコン面積の制約がある。
【００２６】
これらの限界は、非常に高速なインターフェース（１０Ｇｂｐｓ以上）上のパケット・フローを識別するためにハッシャが使用される場合、非常に短いパケット周期性（６７．２ｎｓ以下）が主な理由となって、特に顕著となるようである。
【００２７】
以下、ハッシャの柔軟性の特徴の、中間のトレード・オフに基づき、実施形態を例として記載する。
【００２８】
図１は、第１の実施形態によるネットワーク・プロセッサのハッシャを示す。
【００２９】
ネットワーク・プロセッサのハッシャの役割は、特定の受信または送信キューにパケットを割り当てることを可能にする程度の粒度までパケットの識別が可能な値をもたらし、その結果、類似のパケットが同じキューに割り当てられるようにすることである。
【００３０】
図のように、ハッシャは、パーサ１１０、分配バス（ｄｉｓｔｒｉｂｕｔｉｏｎ ｂｕｓ）１２０、リセット・ライン（ｒｅｓｅｔ ｌｉｎｅ）１３０、圧縮アレイ（ｃｏｍｐａｃｔｉｏｎ ａｒｒａｙ）１４０、およびハッシャ組み合わせコーン（ｈａｓｈｅｒ ｃｏｍｂｉｎａｔｏｒｉａｌ ｃｏｎｅ）１５０を含む。パーサは、パケットを受け取り、パケットは、レジスタ１１１にロードされる。パーサは、レジスタ１１１のコンテンツを調べて、考えられるパケット・フォーマットに関する知識と、パケット内、特にパケットのヘッダ部の特定の位置にある値とに基づき、特定の重要な情報部分の位置を識別して、これらを必要に応じて抽出することができる。現在の例では、この対象となる情報は、そのパケットが属するネットワーク通信を一意的に識別するのに役立つ情報である。
【００３１】
キー・アセンブリに関する柔軟性は、分配バス１２０によって実現される。分配バス１２０は、パケット・パーサからバイト単位で圧縮アレイの任意の入力に入れることができ、パケット・パーサは、ピココードＦＳＭ（ｐｉｃｏ−ｃｏｄｅｄ ＦＳＭ）として実装されることが好ましい。これは、パーサによってパケットから抽出されたバイトの任意の組み合わせを用いてロー・キー（ｒａｗ ｋｅｙ）をアセンブルすることを可能にする。
【００３２】
圧縮アレイ、および同様にハッシャ・コーンの入力段階は、１６バイト幅のレジスタのセットから成り、これらは、パケット・ヘッダもしくはペイロードまたはその両方からバイトを抽出できる任意のパケット・パーサによってロードされるように個々にアドレス指定可能である。様々なバイトがロードされる順序は、特に、フローの識別に貢献できる、抽出された各バイトに含まれる情報量によって決定される。
【００３３】
ハッシャ・コーンによって実装されるハッシュ関数は、ＸＯＲゲートに基づく標準的な組み合わせロジック・コーンであり、ハッシュ・キーの１２８ビットすべてを組み合わせて、結果として生じる３２ビットのハッシュ値をもたらす。
【００３４】
圧縮アレイ１４０が実装する圧縮機能は、長いキー構成要素をより小さなフィールドに縮小することによって、キー・アセンブリ面積のサイズの最小化を可能にし、その結果キーを受け取るハードウェア・ハッシュ関数のシリコン面積のサイズの最小化を可能にする。この機能の典型的な用途は、ＩＰｖ６ヘッダの１６バイト・アドレス・フィールドを４バイトの構成要素に縮小することであり、４バイト構成要素は、ＩＰｖ４ヘッダから抽出される４バイト・アドレスと同じ入力レジスタを使用できる。圧縮アレイの動作については、以下にさらに詳しく記載する。
【００３５】
上記のように、キーの構築に利用可能であり、ハッシャ結合（ｈａｓｈｅｒ ｃｏｍｂ）への入力として使用するのに望ましいと考えられる特定の情報部分は、状況により変化するが、一般的なシナリオには以下が含まれる。
【００３６】
【表１】
【００３７】
状況に応じて、パーサ制御モジュール１１２は、データセットの完成に必要な、レジスタ１１１内のパケットの様々なコンポーネントを抽出し、各コンポーネントを圧縮アレイ１４０の個別の入力に送る。
【００３８】
好適な実施形態によれば、パーサ制御モジュール１１２は、パケットから抽出された情報を、例えば上記で列挙されたシナリオに従って、標準の入力構造へとマップする。
【００３９】
図２は、標準のハッシャ入力構造を示す。図２に示すように、標準のハッシャ入力構造は、１６バイトを含む。４バイトを含む第１のセクション２１０は、ソース・アドレスに使用される。２バイトを含む第２のセクション２２０は、ソース・ポート値に使用される。２バイトを含む第３のセクション２３０は、ＭＰＬＳラベル値に使用される。４バイトを含む第４のセクション２４０は、宛先アドレスに使用される。２バイトを含む第５のセクション２５０は、宛先ポート値に使用される。４ビットを含む第６のセクション２６０は、第３のセクション２３０の続きとしてＭＰＬＳラベル値に使用される。４ビットを含む第７のセクション２７０は、予約される。１バイトを含む第８のセクション２８０は、プロトコル値に使用される。
【００４０】
当然のことながら、他の実施形態では、別の同様の構造が使用されてもよく、または、このような構造は実際には定義されなくてもよい。その場合、パーサ制御モジュールは、データが連続するフィールドのセットに再アセンブルされさえすれば、単にパケットから抽出された順序にデータを保ってもよいであろう。
【００４１】
なお、図２に基づいて、ＩＰｖ６アドレスを扱う必要があるバイトは第１〜第４および第９〜第１２のバイトのみであるため、実際には圧縮アレイがインターセプトする必要があるのは、第１〜第４および第９〜第１２のバイトの値のみである。それでも圧縮アレイは、好適には、種々の入力にデータを割り当てる完全な柔軟性を実現するように、ハッシャ・コーンのあらゆる入力に対して圧縮モジュールを提供するべきである。
【００４２】
圧縮アレイは、ハッシャ組み合わせコーン１５０の入力の数に等しい数のデータ入力、およびさらに出力を有する。図のように、入力は、オクテットにグループ化され、８つの入力の各グループが、分配バス１２０を介してアドレス指定可能である。この方法により、パーサ制御モジュールは、パケットから抽出されるデータのバイトを、圧縮アレイ１４０の入力のオクテット・グループのいずれかに送ることができる。図のように、圧縮アレイは、１６のオクテット入力グループを含み、したがって、１６バイトをパーサ１１０から受け取って同じ数をハッシャ組み合わせコーン１５０に伝えることができる。図２に関して上記で説明したように、一般に、ハッシャ結合の入力において利用可能な合計１６バイトのうち、ソース（第１のセクション、２１０）または宛先（第４のセクション、２４０）の所与のＩＰアドレス用に、４バイトが予約される。上記のように１６バイトを必要とするＩＰｖ６アドレスの場合、これでは明らかに不十分であり、ここで圧縮アレイが重要となる。以下により詳しく記載するように、ＩＰｖ６アドレスの複数部分を圧縮アレイの入力の同じセットに連続して供給する（ｆｅｅｄ）ことによって、圧縮された識別子が圧縮アレイの対応する出力にて蓄積され、その結果、ＩＰｖ６アドレス全体が圧縮された形式でハッシャ結合に供給されることが可能となる。
【００４３】
図１は、圧縮アレイ１４０における、分配バス１２０を介したデータ１２１のバイトの到着を示す。図のように、バイト１〜４および９〜１２は４バイトを順に受け取るが、バイト５〜８および１３〜１６は、同じ期間にそれぞれ１バイトしか受け取らない。種々の圧縮モジュールに任意の順序で提供され得るが、好適には、一定の期間中、圧縮機能を実行する任意のモジュールが、そのバイトのそれぞれを次々と途切れずに受け取るべきである。
【００４４】
図３は、実施形態による圧縮器アレイのコンポーネントの詳細を示す。特定の実施形態によれば、圧縮器アレイは、新たなビットが受け取られなくなるまで、先行する排他的ＯＲ関数の結果の各ビットに、新たなビットをそれぞれ用いて排他的ＯＲ関数を適用することによって、バイナリ識別子の各部分を連続して受け取ることができる。したがって、圧縮アレイは、排他的ＯＲゲート１４１１、１４２１、１４３１をそれぞれ含むアレイ圧縮器モジュールを包含し、そのそれぞれが、１つの入力において分配バス１２０からの入力、および個別のラッチ１４１３、１４２３、１４３３に格納されている先行する計算の結果を受け取る。新たな入力が受け取られるたびに、前の計算の結果とのＸＯＲがとられるなどである。圧縮アレイにある圧縮モジュールの数は、ハッシャ結合が入力として受け取ることができるビットの数と等しい。なお、示されている構造は、所与の圧縮モジュールに関して一連の入力値の圧縮を可能にするが、１つのみの入力値が受け取られる場合、ラッチからの初期値が０であれば、ラッチに書き込まれる排他的ＯＲ関数の結果は、入力値と等しくなる。この機能は、リセット・ライン１３０を介して制御される。リセット・ライン１３０は、各圧縮モジュール内に位置している個別のＡＮＤゲート１４１２、１４２２、１４３２の１つの入力に接続されており、リセット・ライン１３０上の値と、個別のＸＯＲゲートの出力とのＡＮＤをとって、ラッチへの入力としての結果が提供される。これにより、リセット・ライン１３０の値を０にセットすることによって、各ＡＮＤゲート１４１２、１４２２、１４３２の出力も０となるはずであり、その結果ラッチ値も０にセットされ、その結果、任意の圧縮モジュールの入力で受け取られる次の値は、その出力に、さらにハッシャ・コーンに、変更されずに正しく伝送される。
【００４５】
例として、上記のメカニズムが、次のバイナリ識別子に適用されてもよいであろう。
【００４６】
【表２】
【００４７】
このバイナリ識別子は、１６オクテットを含み、よって標準のＩＰｖ６アドレスに対応するが、実際の値はランダムであり、有効なアドレスには対応しないかもしれない。前述の事項によれば、この１６オクテットは、４つの部分に分割され、表２の第１行に対応する第１の部分が、開始値のゼロとビット単位ＸＯＲをとられる。この第１のサイクルの後にラッチ１４１３、１４２３、１４３３などに格納される結果が、次の表３に示されている。
【００４８】
【表３】
【００４９】
次に、下記の表４に示されているように、表２の第２行に対応する第２の部分が、ラッチ１４１３、１４２３、１４３３などに格納されている先行する（第１の）サイクルの結果とビット単位ＸＯＲをとられる。
【００５０】
【表４】
【００５１】
次に、下記の表５に示されているように、表２の第３行に対応する第３の部分が、ラッチ１４１３、１４２３、１４３３などに格納されている先行する（第２の）サイクルの結果とビット単位ＸＯＲをとられる。
【００５２】
【表５】
【００５３】
最後に、下記の表６に示されているように、表２の第４行に対応する第４の部分が、ラッチ１４１３、１４２３、１４３３などに格納されている先行する（第３の）サイクルの結果とビット単位ＸＯＲをとられる。
【００５４】
【表６】
【００５５】
続いて、最終結果は、上記のように、他の関連情報とともにハッシャ・コーンによって処理される。
【００５６】
図４は、本発明による方法のステップを示す。
【００５７】
図４に示されているように、方法は、ステップ４０５に進む前のステップ４００にて開始し、ステップ４０５にて、ＩＰｖ６アドレスなどのバイナリ識別子が、所定数Ｐの等価な部分に分けられる。図１および２に関して記載された実施形態では、１６バイトのＩＰｖ６アドレスは、それぞれ４バイトの４つの部分に分けられる。方法は、続いてステップ４１０に進み、そこで、第１の部分（ｎ＝１）の各ビットに、個別の開始値（図３の例では、開始値はすべてのビットに関して０であった）を用いて排他的ＯＲ関数が適用される。次に、方法は、ステップ４１５に進み、そこで、次の部分が選択される。すなわち、ｎの値がインクリメントされる。続いて、方法はステップ４２０に進み、そこで、先行する排他的ＯＲ関数の結果の各ビットに、現在の部分の各ビットをそれぞれ用いて排他的ＯＲ関数が適用される。次に、方法はステップ４２５に進み、そこで、任意の部分が残っているか、すなわちｎ＝Ｐであるかが判断される。最後の部分のＸＯＲがとられた場合、方法は、ステップ４３０にて終了し、それによって、最後の排他的ＯＲ関数の結果が、前記圧縮されたバイナリ識別子を形成する。その他の場合は、方法はステップ４１５へ戻る。
【００５８】
各部分は、もとのバイナリ識別子からの、ビットの連続的なシーケンスの順序を保っている、ビットの個別のシーケンスを含むことが好ましい。
【００５９】
図４の圧縮プロセスが完了した後、図１の実施形態によれば、圧縮されたバイナリ識別子は、ハッシャに供給される。より具体的には、図２を参照して説明したように、圧縮されたバイナリ識別子は、他のパケット固有データとともにハッシャに供給される。
【００６０】
そのような場合には、バイナリ識別子は、ソースＩＰアドレスであってもよく、他のパケット固有データは、図４のプロセスによって同じく圧縮された宛先ＩＰアドレスを包含してもよい。
【００６１】
本発明の実施形態は、典型的には、イーサネットを介して、すなわちイーサネット・パケットにカプセル化されて移送されるＩＰｖ６パケットのストリームを処理するのに有用である。
【００６２】
図５は、イーサネット・パケットにカプセル化されたＩＰｖ６パケットの一部を表す。図のように、イーサネット（レイヤ２）パケット５２０は、特に、ＥｔｈｅｒＴｙｐｅフィールド５２１およびペイロード５２２を含む。その一方で、ペイロード５２２は、ＩＰｖ６（レイヤ３）パケット５３０を包含し、これ自体は、ソース・アドレス・フィールド５３１および宛先アドレス・フィールド５３２を含む。ＥｔｈｅｒＴｙｐｅフィールドの８６ＤＤ１６という値は、イーサネット・パケットが、ＩＰｖ６パケットをカプセル化していることを示し、その結果このパケットは、上記のように、適宜処理されることが可能である。
【００６３】
図６は、第１の実施形態による、データの処理のサポートにおいて、パーサ制御モジュールにてとられるとよいステップを表すフロー図である。図のように、方法は、ステップ６１０に進む前のステップ６０５にて開始し、ステップ６１０にてパーサ制御モジュール１１２は、図５に関して説明されたＥｔｈｅｒＴｙｐｅフィールドを探す。ステップ６１５にて、ＥｔｈｅｒＴｙｐｅフィールドの値が、８６ＤＤ１６であるか否かが判断される。ＥｔｈｅｒＴｙｐｅフィールドの値が８６ＤＤ１６でない場合、方法は、ステップ６６５にて終了する。その他の場合、方法は、ステップ６２０に進み、そこで、圧縮アレイのリセット・ライン１３０の値がゼロにセットされ、その結果、図３に関して記載したように、圧縮アレイの各ラッチの値がゼロにセットされる。その後、ステップ６２５にて、値Ｍが９にセットされ、ステップ６３０にて、ＩＰｖ６パケットの第Ｍバイトが、レジスタ１１１のパケットから抽出される。ステップ６３５にて、Ｍの値が８より大きく１３より小さいかどうかが判断され、そうである場合、抽出されたバイトは、ステップ６４０にて、ソース・アドレス用に予約されている圧縮アレイのセクション２１０に送られる。ステップ６３５にて、Ｍの値が８より大きく１３より小さい値ではないと判断されると、ステップ６４５にて、Ｍの値が１２より大きく１７より小さいかどうかが判断され、そうである場合、抽出されたバイトは、ステップ６５０にて、宛先アドレス用に予約されている圧縮アレイのセクション２４０に送られる。ステップ６３５にて、Ｍの値が１２より大きく１７より小さい値ではないと判断されると、方法はステップ６６５にて終了する。ステップ６４０または６５０の後、方法は、ステップ６６０に進み、そこでＭが１インクリメントされてから、ステップ６３０に戻る。
【００６４】
当然のことながら、これらのステップは、ＩＰｖ６パケットの存在を識別し、アドレス・フィールドを抽出し、これらを圧縮アレイの適切な部分へ送る全般的な効果を変更することなく、異なる順序で実行されることが可能である。
【００６５】
本発明は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、またはハードウェアおよびソフトウェア両方の構成要素を含む実施形態の形態をとることができる。好適な実施形態では、本発明はソフトウェアにおいて実装され、これは、限定はされないが、ファームウェア、常駐ソフトウェア、マイクロコードなどを含む。
【００６６】
さらに、本発明は、コンピュータ使用可能またはコンピュータ可読媒体からアクセス可能なコンピュータ・プログラム製品の形態をとり、コンピュータまたは任意の命令実行システムにより、またはそれに関連して使用されるプログラム・コードを提供することができる。本記載では、コンピュータ使用可能またはコンピュータ可読媒体は、命令実行システム、装置もしくはデバイスによって、またはそれに関連して使用されるプログラムを含むこと、格納すること、伝達すること、伝播させること、または移送することができる任意の装置とすることができる。特に、この意味で、上記のパーサ制御モジュールは、命令実行システム、または「コンピュータ」を構成する。
【００６７】
媒体は、電子、磁気、光学、電磁気、赤外線、または半導体システム、（もしくは装置もしくはデバイス）、または伝播媒体とすることができる。コンピュータ可読媒体の例には、半導体または固体メモリ、磁気テープ、リムーバブル・コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）、読み取り専用メモリ（ＲＯＭ：ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ）、剛体磁気ディスク、および光ディスクが含まれる。光ディスクの現在の例には、コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：ｃｏｍｐａｃｔ ｄｉｓｋ−ｒｅａｄ ｏｎｌｙ ｍｅｍｏｒｙ）、コンパクト・ディスク読み取り／書き込み（ＣＤ−Ｒ／Ｗ：ｃｏｍｐａｃｔ ｄｉｓｋ−ｒｅａｄ／ｗｒｉｔｅ）、およびＤＶＤが含まれる。
【００６８】
プログラム・コードの格納もしくは実行またはその両方に適したデータ処理システムは、システム・バスを介してメモリ要素に直接または間接的に連結された少なくとも１つのプロセッサを含み得る。メモリ要素は、プログラム・コードを実際に実行する間に用いられるローカル・メモリ、大容量ストレージ、および、実行中にコードが大容量ストレージから読み出されなければならない回数を減らすために少なくとも一部のプログラム・コードの一時的なストレージとなるキャッシュ・メモリを含むことができる。
【００６９】
入出力、すなわちＩ／Ｏ（ｉｎｐｕｔ／ｏｕｔｐｕｔ）デバイス（限定はされないが、キーボード、ディスプレイ、ポインティング・デバイスなどを含む）は、直接、または介在するＩ／Ｏコントローラを介して、システムに連結されることが可能である。
【００７０】
ネットワーク・アダプタもシステムに連結されて、データ処理システムが、他のデータ処理システムまたはリモート・プリンタまたはストレージ・デバイスに、介在するプライベートまたはパブリック・ネットワークを介して連結された状態となることを可能にしてもよい。モデム、ケーブル・モデム、およびイーサネット・カードが、現在利用可能なタイプのネットワーク・アダプタのごく一部である。
【符号の説明】
【００７１】
１１０ パーサ
１１１ レジスタ
１１２ パーサ制御モジュール
１２０ 分配バス
１２１ データ
１３０ リセット・ライン
１４０ 圧縮アレイ
１５０ ハッシャ組み合わせコーン
【技術分野】
【０００１】
本発明は、バイナリ識別子、特にＩＰｖ６アドレスの圧縮に関する。
【背景技術】
【０００２】
インターネット・プロトコル・バージョン４（ＩＰｖ４：Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ，Ｖｅｒｓｉｏｎ４）は、その原型の３２ビットでインターネットのアドレス指定の機能を定義し、合計２３２、すなわち４３億の可能なアドレスを与えている。ネットワークの爆発的な成長および世界的な増設は、ＩＰｖ４のもとで利用可能なアドレスがすべて、２０１２年までに枯渇することを意味した。
【０００３】
そこで、ＩＰｖ４に代わるＩＰｖ６プロトコルが定義されており、３．４×１０３８のアドレスという理論上の容量の１２８ビット・アドレスを規定することによって、特にＩＰｖ４の特定の欠点に対処する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
それにもかかわらず、実際のところ、既存のハードウェアおよびソフトウェアの大部分は、ＩＰｖ４技術に基づいている。新たなハードウェアおよびソフトウェアがＩＰｖ６と互換性を持つように設計されている場合であっても、できる限り既存のライブラリおよびルーチンを再利用することが望ましい。
【課題を解決するための手段】
【０００５】
本発明によれば、添付の独立請求項１に記載の、圧縮されたバイナリ識別子（ｃｏｍｐａｃｔｅｄ ｂｉｎａｒｙ ｉｄｅｎｔｉｆｉｅｒ）を生成する方法と、添付の請求項１０に記載の圧縮器（ｃｏｍｐａｃｔｏｒ）と、添付の請求項１１に記載のハッシャ（ｈａｓｈｅｒ）と、添付の請求項１２に記載のコンピュータ・プログラムとが提供される。
【０００６】
好適な実施形態が、添付の従属請求項において定義される。
【０００７】
１度に４バイトの累積ＸＯＲベースのプリハッシュ（ｐｒｅｈａｓｈｉｎｇ）に基づき、ハッシュ・キーに必要な特性を保ちながら、大きい（１６バイト）ＩＰｖ６アドレスを通例の（４バイト）アドレス・フィールドに圧縮することについて記載する。
【０００８】
これは、例えば、「５タプル」のようなキーを典型的には受け入れるハッシャにおいてＩＰｖ６アドレスをサポートするために使用されるロジックおよびシリコン面積を最小化することによる利点を提供する。このようなキーは、パケット・ヘッダから抽出される５つのフィールドを用いてアセンブル（ａｓｓｅｍｂｌｅ）され、これらは共に、そのパケットが属するパケット・フローを非常によく表す。ＴＣＰ接続を識別するために使用される５タプルの典型的な例は、次のアセンブリである。
【０００９】
−ＩＰソース・アドレス
−ＩＰ宛先アドレス
−プロトコル・バイト
−ＴＣＰソース・ポート
−ＴＣＰ宛先ポート
【００１０】
パケットが、ＩＰｖ６レイヤ３ヘッダを有する場合、実装問題が生じる。４バイトＩＰアドレスを運ぶＩＰｖ４ヘッダと対照的に、ＩＰｖ６ヘッダは、１６バイトＩＰアドレスを運ぶ。これは、５タプル・キーが、ＩＰｖ４レイヤ３ヘッダよりもＩＰｖ６に関してずっと大きくなるということを意味する。
【００１１】
−ＩＰｖ４＝ＩＰ ＳＡ（４Ｂ）＋ＩＰ ＤＡ（４Ｂ）＋プロトコル（１Ｂ）＋ＴＣＰ ＳＰ（２Ｂ）＋ＴＣＰ ＤＰ（２Ｂ）＝１３バイト
−ＩＰｖ６＝ＩＰ ＳＡ（１６Ｂ）＋ＩＰ ＤＡ（１６Ｂ）＋プロトコル（１Ｂ）＋ＴＣＰ ＳＰ（２Ｂ）＋ＴＣＰ ＤＰ（２Ｂ）＝３７バイト
【００１２】
３７バイトの入力レジスタを備えるハッシャの実装は、シリコン面積の点ではるかに高価である。これは、より大きなＩＰｖ６アドレスを保持するのに必要な、２４×８＝１９２の追加のラッチだけではなく、１３×８＝１０４に対し３７×８＝２９６の入力から始まるはるかに大きな組み合わせロジック・コーン（ｃｏｍｂｉｎａｔｏｒｉａｌ ｃｏｎｅ ｏｆ ｌｏｇｉｃ）が原因でもある。
【００１３】
ハッシャを構成するロジック・コーンのサイズは、その入力の数と線形でないため、２つのソリューション間の面積比は、少なくとも４倍である。
【００１４】
本開示で提案されるソリューションは、もとのキー入力レジスタおよびロジック・コーンを維持するために、ＩＰｖ６アドレスをＩＰｖ４サイズに縮小するようＩＰｖ６アドレスの予備処理を実行することである。
【００１５】
図面および詳細な説明を検討すれば、本発明のさらなる利点が当業者には明白となる。任意のさらなる利点が、本願明細書に包含されるものとする。
【図面の簡単な説明】
【００１６】
【図１】第１の実施形態によるネットワーク・プロセッサのハッシャを示す。
【図２】標準のハッシャ入力構造を示す。
【図３】実施形態による圧縮器アレイのコンポーネントの詳細を示す。
【図４】本発明による方法のステップを示す。
【図５】イーサネット（Ｒ）パケットにカプセル化されたＩＰｖ６パケットの一部を表す。
【図６】第１の実施形態による、データの処理のサポートにおいて、パーサ制御モジュールにてとられるとよいステップを表すフロー図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について、添付の図面を参照して例として記載する。図面では、同じ参照符号は同様の構成要素を示す。
【００１８】
上記に鑑み、圧縮されたバイナリ識別子を使用できるように、ＩＰｖ６アドレスなどの圧縮されたバイナリ識別子を生成することを提案する。
【００１９】
提案される圧縮プロセスは、非決定性であり、すなわち、いくつかの異なるバイナリ識別子が同じ圧縮された識別子をもたらすことがあり得、バイナリ識別子の圧縮された識別子からもとのバイナリ識別子を再構成することは不可能であるということが、この提案される圧縮プロセスの特徴である。この特性により、特定の用途では、本発明による圧縮された識別子の使用が不可能となるかもしれないが、それでも、特許請求される手法が十分である用途は多数ある。特に、特許請求される手法は、アイデンティティ情報に基づくパケットまたは他のデータの特徴付けであって、一意のアイデンティティのレベルまでは粒度が細かくない、該特徴付けが望まれる多数の用途に適する。そのような用途の例には、以下により詳しく説明する、パケット識別子およびＩＰフィルタがある。
【００２０】
上記のように、本発明が有用な例の１つは、ネットワーク・プロセッサにおいてパケット・フローを識別するハッシュ関数などのハッシュ関数においてである。ハッシュ関数の柔軟性は、典型的には、２つのパラメータによって定義される。
【００２１】
−ハッシュ・キーがアセンブルされる方法
−ハッシュ関数自体の特性
【００２２】
これら２つの特性の変化を利用して柔軟性のあるハッシャを実装するには、いくつかのトレード・オフがあることが多い。
【００２３】
従来、ハッシャのソフトウェア実装においてキー・アセンブリ（ｋｅｙ ａｓｓｅｍｂｌｙ）の柔軟性が好まれてきたが、柔軟性のあるハッシュ関数には、通常、ハッシャの何らかの形の構成可能なハードウェア実装が必要である。
【００２４】
ハッシャの柔軟性の各側面には、通常、以下の限界がある。
【００２５】
−ハッシュ・キーの構築に複雑なパターンが必要な場合、特に、キー・アセンブリがビットレベルの粒度で行われる場合、ソフトウェア・キー・アセンブリに性能限界がある。
−典型的には単純なＸＯＲゲートを用いて実装される基本のハッシング構成要素を補完する構成ロジックが原因で、構成可能なハードウェア・ハッシュ関数にはシリコン面積の制約がある。
【００２６】
これらの限界は、非常に高速なインターフェース（１０Ｇｂｐｓ以上）上のパケット・フローを識別するためにハッシャが使用される場合、非常に短いパケット周期性（６７．２ｎｓ以下）が主な理由となって、特に顕著となるようである。
【００２７】
以下、ハッシャの柔軟性の特徴の、中間のトレード・オフに基づき、実施形態を例として記載する。
【００２８】
図１は、第１の実施形態によるネットワーク・プロセッサのハッシャを示す。
【００２９】
ネットワーク・プロセッサのハッシャの役割は、特定の受信または送信キューにパケットを割り当てることを可能にする程度の粒度までパケットの識別が可能な値をもたらし、その結果、類似のパケットが同じキューに割り当てられるようにすることである。
【００３０】
図のように、ハッシャは、パーサ１１０、分配バス（ｄｉｓｔｒｉｂｕｔｉｏｎ ｂｕｓ）１２０、リセット・ライン（ｒｅｓｅｔ ｌｉｎｅ）１３０、圧縮アレイ（ｃｏｍｐａｃｔｉｏｎ ａｒｒａｙ）１４０、およびハッシャ組み合わせコーン（ｈａｓｈｅｒ ｃｏｍｂｉｎａｔｏｒｉａｌ ｃｏｎｅ）１５０を含む。パーサは、パケットを受け取り、パケットは、レジスタ１１１にロードされる。パーサは、レジスタ１１１のコンテンツを調べて、考えられるパケット・フォーマットに関する知識と、パケット内、特にパケットのヘッダ部の特定の位置にある値とに基づき、特定の重要な情報部分の位置を識別して、これらを必要に応じて抽出することができる。現在の例では、この対象となる情報は、そのパケットが属するネットワーク通信を一意的に識別するのに役立つ情報である。
【００３１】
キー・アセンブリに関する柔軟性は、分配バス１２０によって実現される。分配バス１２０は、パケット・パーサからバイト単位で圧縮アレイの任意の入力に入れることができ、パケット・パーサは、ピココードＦＳＭ（ｐｉｃｏ−ｃｏｄｅｄ ＦＳＭ）として実装されることが好ましい。これは、パーサによってパケットから抽出されたバイトの任意の組み合わせを用いてロー・キー（ｒａｗ ｋｅｙ）をアセンブルすることを可能にする。
【００３２】
圧縮アレイ、および同様にハッシャ・コーンの入力段階は、１６バイト幅のレジスタのセットから成り、これらは、パケット・ヘッダもしくはペイロードまたはその両方からバイトを抽出できる任意のパケット・パーサによってロードされるように個々にアドレス指定可能である。様々なバイトがロードされる順序は、特に、フローの識別に貢献できる、抽出された各バイトに含まれる情報量によって決定される。
【００３３】
ハッシャ・コーンによって実装されるハッシュ関数は、ＸＯＲゲートに基づく標準的な組み合わせロジック・コーンであり、ハッシュ・キーの１２８ビットすべてを組み合わせて、結果として生じる３２ビットのハッシュ値をもたらす。
【００３４】
圧縮アレイ１４０が実装する圧縮機能は、長いキー構成要素をより小さなフィールドに縮小することによって、キー・アセンブリ面積のサイズの最小化を可能にし、その結果キーを受け取るハードウェア・ハッシュ関数のシリコン面積のサイズの最小化を可能にする。この機能の典型的な用途は、ＩＰｖ６ヘッダの１６バイト・アドレス・フィールドを４バイトの構成要素に縮小することであり、４バイト構成要素は、ＩＰｖ４ヘッダから抽出される４バイト・アドレスと同じ入力レジスタを使用できる。圧縮アレイの動作については、以下にさらに詳しく記載する。
【００３５】
上記のように、キーの構築に利用可能であり、ハッシャ結合（ｈａｓｈｅｒ ｃｏｍｂ）への入力として使用するのに望ましいと考えられる特定の情報部分は、状況により変化するが、一般的なシナリオには以下が含まれる。
【００３６】
【表１】
【００３７】
状況に応じて、パーサ制御モジュール１１２は、データセットの完成に必要な、レジスタ１１１内のパケットの様々なコンポーネントを抽出し、各コンポーネントを圧縮アレイ１４０の個別の入力に送る。
【００３８】
好適な実施形態によれば、パーサ制御モジュール１１２は、パケットから抽出された情報を、例えば上記で列挙されたシナリオに従って、標準の入力構造へとマップする。
【００３９】
図２は、標準のハッシャ入力構造を示す。図２に示すように、標準のハッシャ入力構造は、１６バイトを含む。４バイトを含む第１のセクション２１０は、ソース・アドレスに使用される。２バイトを含む第２のセクション２２０は、ソース・ポート値に使用される。２バイトを含む第３のセクション２３０は、ＭＰＬＳラベル値に使用される。４バイトを含む第４のセクション２４０は、宛先アドレスに使用される。２バイトを含む第５のセクション２５０は、宛先ポート値に使用される。４ビットを含む第６のセクション２６０は、第３のセクション２３０の続きとしてＭＰＬＳラベル値に使用される。４ビットを含む第７のセクション２７０は、予約される。１バイトを含む第８のセクション２８０は、プロトコル値に使用される。
【００４０】
当然のことながら、他の実施形態では、別の同様の構造が使用されてもよく、または、このような構造は実際には定義されなくてもよい。その場合、パーサ制御モジュールは、データが連続するフィールドのセットに再アセンブルされさえすれば、単にパケットから抽出された順序にデータを保ってもよいであろう。
【００４１】
なお、図２に基づいて、ＩＰｖ６アドレスを扱う必要があるバイトは第１〜第４および第９〜第１２のバイトのみであるため、実際には圧縮アレイがインターセプトする必要があるのは、第１〜第４および第９〜第１２のバイトの値のみである。それでも圧縮アレイは、好適には、種々の入力にデータを割り当てる完全な柔軟性を実現するように、ハッシャ・コーンのあらゆる入力に対して圧縮モジュールを提供するべきである。
【００４２】
圧縮アレイは、ハッシャ組み合わせコーン１５０の入力の数に等しい数のデータ入力、およびさらに出力を有する。図のように、入力は、オクテットにグループ化され、８つの入力の各グループが、分配バス１２０を介してアドレス指定可能である。この方法により、パーサ制御モジュールは、パケットから抽出されるデータのバイトを、圧縮アレイ１４０の入力のオクテット・グループのいずれかに送ることができる。図のように、圧縮アレイは、１６のオクテット入力グループを含み、したがって、１６バイトをパーサ１１０から受け取って同じ数をハッシャ組み合わせコーン１５０に伝えることができる。図２に関して上記で説明したように、一般に、ハッシャ結合の入力において利用可能な合計１６バイトのうち、ソース（第１のセクション、２１０）または宛先（第４のセクション、２４０）の所与のＩＰアドレス用に、４バイトが予約される。上記のように１６バイトを必要とするＩＰｖ６アドレスの場合、これでは明らかに不十分であり、ここで圧縮アレイが重要となる。以下により詳しく記載するように、ＩＰｖ６アドレスの複数部分を圧縮アレイの入力の同じセットに連続して供給する（ｆｅｅｄ）ことによって、圧縮された識別子が圧縮アレイの対応する出力にて蓄積され、その結果、ＩＰｖ６アドレス全体が圧縮された形式でハッシャ結合に供給されることが可能となる。
【００４３】
図１は、圧縮アレイ１４０における、分配バス１２０を介したデータ１２１のバイトの到着を示す。図のように、バイト１〜４および９〜１２は４バイトを順に受け取るが、バイト５〜８および１３〜１６は、同じ期間にそれぞれ１バイトしか受け取らない。種々の圧縮モジュールに任意の順序で提供され得るが、好適には、一定の期間中、圧縮機能を実行する任意のモジュールが、そのバイトのそれぞれを次々と途切れずに受け取るべきである。
【００４４】
図３は、実施形態による圧縮器アレイのコンポーネントの詳細を示す。特定の実施形態によれば、圧縮器アレイは、新たなビットが受け取られなくなるまで、先行する排他的ＯＲ関数の結果の各ビットに、新たなビットをそれぞれ用いて排他的ＯＲ関数を適用することによって、バイナリ識別子の各部分を連続して受け取ることができる。したがって、圧縮アレイは、排他的ＯＲゲート１４１１、１４２１、１４３１をそれぞれ含むアレイ圧縮器モジュールを包含し、そのそれぞれが、１つの入力において分配バス１２０からの入力、および個別のラッチ１４１３、１４２３、１４３３に格納されている先行する計算の結果を受け取る。新たな入力が受け取られるたびに、前の計算の結果とのＸＯＲがとられるなどである。圧縮アレイにある圧縮モジュールの数は、ハッシャ結合が入力として受け取ることができるビットの数と等しい。なお、示されている構造は、所与の圧縮モジュールに関して一連の入力値の圧縮を可能にするが、１つのみの入力値が受け取られる場合、ラッチからの初期値が０であれば、ラッチに書き込まれる排他的ＯＲ関数の結果は、入力値と等しくなる。この機能は、リセット・ライン１３０を介して制御される。リセット・ライン１３０は、各圧縮モジュール内に位置している個別のＡＮＤゲート１４１２、１４２２、１４３２の１つの入力に接続されており、リセット・ライン１３０上の値と、個別のＸＯＲゲートの出力とのＡＮＤをとって、ラッチへの入力としての結果が提供される。これにより、リセット・ライン１３０の値を０にセットすることによって、各ＡＮＤゲート１４１２、１４２２、１４３２の出力も０となるはずであり、その結果ラッチ値も０にセットされ、その結果、任意の圧縮モジュールの入力で受け取られる次の値は、その出力に、さらにハッシャ・コーンに、変更されずに正しく伝送される。
【００４５】
例として、上記のメカニズムが、次のバイナリ識別子に適用されてもよいであろう。
【００４６】
【表２】
【００４７】
このバイナリ識別子は、１６オクテットを含み、よって標準のＩＰｖ６アドレスに対応するが、実際の値はランダムであり、有効なアドレスには対応しないかもしれない。前述の事項によれば、この１６オクテットは、４つの部分に分割され、表２の第１行に対応する第１の部分が、開始値のゼロとビット単位ＸＯＲをとられる。この第１のサイクルの後にラッチ１４１３、１４２３、１４３３などに格納される結果が、次の表３に示されている。
【００４８】
【表３】
【００４９】
次に、下記の表４に示されているように、表２の第２行に対応する第２の部分が、ラッチ１４１３、１４２３、１４３３などに格納されている先行する（第１の）サイクルの結果とビット単位ＸＯＲをとられる。
【００５０】
【表４】
【００５１】
次に、下記の表５に示されているように、表２の第３行に対応する第３の部分が、ラッチ１４１３、１４２３、１４３３などに格納されている先行する（第２の）サイクルの結果とビット単位ＸＯＲをとられる。
【００５２】
【表５】
【００５３】
最後に、下記の表６に示されているように、表２の第４行に対応する第４の部分が、ラッチ１４１３、１４２３、１４３３などに格納されている先行する（第３の）サイクルの結果とビット単位ＸＯＲをとられる。
【００５４】
【表６】
【００５５】
続いて、最終結果は、上記のように、他の関連情報とともにハッシャ・コーンによって処理される。
【００５６】
図４は、本発明による方法のステップを示す。
【００５７】
図４に示されているように、方法は、ステップ４０５に進む前のステップ４００にて開始し、ステップ４０５にて、ＩＰｖ６アドレスなどのバイナリ識別子が、所定数Ｐの等価な部分に分けられる。図１および２に関して記載された実施形態では、１６バイトのＩＰｖ６アドレスは、それぞれ４バイトの４つの部分に分けられる。方法は、続いてステップ４１０に進み、そこで、第１の部分（ｎ＝１）の各ビットに、個別の開始値（図３の例では、開始値はすべてのビットに関して０であった）を用いて排他的ＯＲ関数が適用される。次に、方法は、ステップ４１５に進み、そこで、次の部分が選択される。すなわち、ｎの値がインクリメントされる。続いて、方法はステップ４２０に進み、そこで、先行する排他的ＯＲ関数の結果の各ビットに、現在の部分の各ビットをそれぞれ用いて排他的ＯＲ関数が適用される。次に、方法はステップ４２５に進み、そこで、任意の部分が残っているか、すなわちｎ＝Ｐであるかが判断される。最後の部分のＸＯＲがとられた場合、方法は、ステップ４３０にて終了し、それによって、最後の排他的ＯＲ関数の結果が、前記圧縮されたバイナリ識別子を形成する。その他の場合は、方法はステップ４１５へ戻る。
【００５８】
各部分は、もとのバイナリ識別子からの、ビットの連続的なシーケンスの順序を保っている、ビットの個別のシーケンスを含むことが好ましい。
【００５９】
図４の圧縮プロセスが完了した後、図１の実施形態によれば、圧縮されたバイナリ識別子は、ハッシャに供給される。より具体的には、図２を参照して説明したように、圧縮されたバイナリ識別子は、他のパケット固有データとともにハッシャに供給される。
【００６０】
そのような場合には、バイナリ識別子は、ソースＩＰアドレスであってもよく、他のパケット固有データは、図４のプロセスによって同じく圧縮された宛先ＩＰアドレスを包含してもよい。
【００６１】
本発明の実施形態は、典型的には、イーサネットを介して、すなわちイーサネット・パケットにカプセル化されて移送されるＩＰｖ６パケットのストリームを処理するのに有用である。
【００６２】
図５は、イーサネット・パケットにカプセル化されたＩＰｖ６パケットの一部を表す。図のように、イーサネット（レイヤ２）パケット５２０は、特に、ＥｔｈｅｒＴｙｐｅフィールド５２１およびペイロード５２２を含む。その一方で、ペイロード５２２は、ＩＰｖ６（レイヤ３）パケット５３０を包含し、これ自体は、ソース・アドレス・フィールド５３１および宛先アドレス・フィールド５３２を含む。ＥｔｈｅｒＴｙｐｅフィールドの８６ＤＤ１６という値は、イーサネット・パケットが、ＩＰｖ６パケットをカプセル化していることを示し、その結果このパケットは、上記のように、適宜処理されることが可能である。
【００６３】
図６は、第１の実施形態による、データの処理のサポートにおいて、パーサ制御モジュールにてとられるとよいステップを表すフロー図である。図のように、方法は、ステップ６１０に進む前のステップ６０５にて開始し、ステップ６１０にてパーサ制御モジュール１１２は、図５に関して説明されたＥｔｈｅｒＴｙｐｅフィールドを探す。ステップ６１５にて、ＥｔｈｅｒＴｙｐｅフィールドの値が、８６ＤＤ１６であるか否かが判断される。ＥｔｈｅｒＴｙｐｅフィールドの値が８６ＤＤ１６でない場合、方法は、ステップ６６５にて終了する。その他の場合、方法は、ステップ６２０に進み、そこで、圧縮アレイのリセット・ライン１３０の値がゼロにセットされ、その結果、図３に関して記載したように、圧縮アレイの各ラッチの値がゼロにセットされる。その後、ステップ６２５にて、値Ｍが９にセットされ、ステップ６３０にて、ＩＰｖ６パケットの第Ｍバイトが、レジスタ１１１のパケットから抽出される。ステップ６３５にて、Ｍの値が８より大きく１３より小さいかどうかが判断され、そうである場合、抽出されたバイトは、ステップ６４０にて、ソース・アドレス用に予約されている圧縮アレイのセクション２１０に送られる。ステップ６３５にて、Ｍの値が８より大きく１３より小さい値ではないと判断されると、ステップ６４５にて、Ｍの値が１２より大きく１７より小さいかどうかが判断され、そうである場合、抽出されたバイトは、ステップ６５０にて、宛先アドレス用に予約されている圧縮アレイのセクション２４０に送られる。ステップ６３５にて、Ｍの値が１２より大きく１７より小さい値ではないと判断されると、方法はステップ６６５にて終了する。ステップ６４０または６５０の後、方法は、ステップ６６０に進み、そこでＭが１インクリメントされてから、ステップ６３０に戻る。
【００６４】
当然のことながら、これらのステップは、ＩＰｖ６パケットの存在を識別し、アドレス・フィールドを抽出し、これらを圧縮アレイの適切な部分へ送る全般的な効果を変更することなく、異なる順序で実行されることが可能である。
【００６５】
本発明は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態、またはハードウェアおよびソフトウェア両方の構成要素を含む実施形態の形態をとることができる。好適な実施形態では、本発明はソフトウェアにおいて実装され、これは、限定はされないが、ファームウェア、常駐ソフトウェア、マイクロコードなどを含む。
【００６６】
さらに、本発明は、コンピュータ使用可能またはコンピュータ可読媒体からアクセス可能なコンピュータ・プログラム製品の形態をとり、コンピュータまたは任意の命令実行システムにより、またはそれに関連して使用されるプログラム・コードを提供することができる。本記載では、コンピュータ使用可能またはコンピュータ可読媒体は、命令実行システム、装置もしくはデバイスによって、またはそれに関連して使用されるプログラムを含むこと、格納すること、伝達すること、伝播させること、または移送することができる任意の装置とすることができる。特に、この意味で、上記のパーサ制御モジュールは、命令実行システム、または「コンピュータ」を構成する。
【００６７】
媒体は、電子、磁気、光学、電磁気、赤外線、または半導体システム、（もしくは装置もしくはデバイス）、または伝播媒体とすることができる。コンピュータ可読媒体の例には、半導体または固体メモリ、磁気テープ、リムーバブル・コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）、読み取り専用メモリ（ＲＯＭ：ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ）、剛体磁気ディスク、および光ディスクが含まれる。光ディスクの現在の例には、コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：ｃｏｍｐａｃｔ ｄｉｓｋ−ｒｅａｄ ｏｎｌｙ ｍｅｍｏｒｙ）、コンパクト・ディスク読み取り／書き込み（ＣＤ−Ｒ／Ｗ：ｃｏｍｐａｃｔ ｄｉｓｋ−ｒｅａｄ／ｗｒｉｔｅ）、およびＤＶＤが含まれる。
【００６８】
プログラム・コードの格納もしくは実行またはその両方に適したデータ処理システムは、システム・バスを介してメモリ要素に直接または間接的に連結された少なくとも１つのプロセッサを含み得る。メモリ要素は、プログラム・コードを実際に実行する間に用いられるローカル・メモリ、大容量ストレージ、および、実行中にコードが大容量ストレージから読み出されなければならない回数を減らすために少なくとも一部のプログラム・コードの一時的なストレージとなるキャッシュ・メモリを含むことができる。
【００６９】
入出力、すなわちＩ／Ｏ（ｉｎｐｕｔ／ｏｕｔｐｕｔ）デバイス（限定はされないが、キーボード、ディスプレイ、ポインティング・デバイスなどを含む）は、直接、または介在するＩ／Ｏコントローラを介して、システムに連結されることが可能である。
【００７０】
ネットワーク・アダプタもシステムに連結されて、データ処理システムが、他のデータ処理システムまたはリモート・プリンタまたはストレージ・デバイスに、介在するプライベートまたはパブリック・ネットワークを介して連結された状態となることを可能にしてもよい。モデム、ケーブル・モデム、およびイーサネット・カードが、現在利用可能なタイプのネットワーク・アダプタのごく一部である。
【符号の説明】
【００７１】
１１０ パーサ
１１１ レジスタ
１１２ パーサ制御モジュール
１２０ 分配バス
１２１ データ
１３０ リセット・ライン
１４０ 圧縮アレイ
１５０ ハッシャ組み合わせコーン
【特許請求の範囲】
【請求項１】
圧縮されたバイナリ識別子を生成する方法であって、バイナリ識別子を、所定数の等価な部分に分けるステップと、
前記部分のうちの第１の部分の各ビットに、個別の開始値を用いて排他的ＯＲ関数を適用するステップと、
先行する前記排他的ＯＲ関数の結果の各ビットに、さらなる前記部分の各ビットをそれぞれ用いて排他的ＯＲ関数を適用するステップと、
前記先行する排他的ＯＲ関数の前記結果の各ビットに排他的ＯＲ関数を適用する前記ステップを、残りの各部分に関して繰り返すステップと、
を含む、前記方法であって、
それによって、最後の前記排他的ＯＲ関数の結果が、前記圧縮されたバイナリ識別子を形成する、方法。
【請求項２】
前記バイナリ識別子は、ＩＰアドレスである、請求項１に記載の方法。
【請求項３】
前記バイナリ識別子は、ＩＰパケットから抽出される、請求項２に記載の方法。
【請求項４】
前記バイナリ識別子は、１２８ビットのＩＰｖ６アドレスであり、前記バイナリ識別子は、それぞれ３２ビットの４つの部分に分割され、前記圧縮されたバイナリ識別子は、３２ビットのＩＰｖ４アドレスに対応する、請求項２または３に記載の方法。
【請求項５】
前記部分のうちの第１の部分の各ビットに対する個別の開始値を用いた前記排他的ＯＲ関数が適用される前記ビットそれぞれに関して、前記開始値は０である、請求項１〜４のいずれかに記載の方法。
【請求項６】
ビットの個別のシーケンスを含む前記部分はそれぞれ、もとの前記バイナリ識別子からのビットの連続的なシーケンスの順序を保っている、請求項１〜５のいずれかに記載の方法。
【請求項７】
前記圧縮されたバイナリ識別子をハッシャに供給するさらなるステップを含む、請求項１〜６のいずれかに記載の方法。
【請求項８】
前記圧縮されたバイナリ識別子は、他のパケット固有データとともに前記ハッシャに供給される、請求項７に記載の方法。
【請求項９】
前記バイナリ識別子は、ソースＩＰアドレスであり、前記他のパケット固有データは、請求項１〜６のいずれかに従って圧縮された宛先ＩＰアドレスを包含する、請求項８に記載の方法。
【請求項１０】
請求項１〜９のいずれかに記載の方法を実装するようになっている圧縮器。
【請求項１１】
請求項１０に記載の圧縮器を包含するハッシャ。
【請求項１２】
請求項１〜９のうちのいずれか１項に記載の方法の前記ステップをコンピュータに実行させるコンピュータ・プログラム。
【請求項１】
圧縮されたバイナリ識別子を生成する方法であって、バイナリ識別子を、所定数の等価な部分に分けるステップと、
前記部分のうちの第１の部分の各ビットに、個別の開始値を用いて排他的ＯＲ関数を適用するステップと、
先行する前記排他的ＯＲ関数の結果の各ビットに、さらなる前記部分の各ビットをそれぞれ用いて排他的ＯＲ関数を適用するステップと、
前記先行する排他的ＯＲ関数の前記結果の各ビットに排他的ＯＲ関数を適用する前記ステップを、残りの各部分に関して繰り返すステップと、
を含む、前記方法であって、
それによって、最後の前記排他的ＯＲ関数の結果が、前記圧縮されたバイナリ識別子を形成する、方法。
【請求項２】
前記バイナリ識別子は、ＩＰアドレスである、請求項１に記載の方法。
【請求項３】
前記バイナリ識別子は、ＩＰパケットから抽出される、請求項２に記載の方法。
【請求項４】
前記バイナリ識別子は、１２８ビットのＩＰｖ６アドレスであり、前記バイナリ識別子は、それぞれ３２ビットの４つの部分に分割され、前記圧縮されたバイナリ識別子は、３２ビットのＩＰｖ４アドレスに対応する、請求項２または３に記載の方法。
【請求項５】
前記部分のうちの第１の部分の各ビットに対する個別の開始値を用いた前記排他的ＯＲ関数が適用される前記ビットそれぞれに関して、前記開始値は０である、請求項１〜４のいずれかに記載の方法。
【請求項６】
ビットの個別のシーケンスを含む前記部分はそれぞれ、もとの前記バイナリ識別子からのビットの連続的なシーケンスの順序を保っている、請求項１〜５のいずれかに記載の方法。
【請求項７】
前記圧縮されたバイナリ識別子をハッシャに供給するさらなるステップを含む、請求項１〜６のいずれかに記載の方法。
【請求項８】
前記圧縮されたバイナリ識別子は、他のパケット固有データとともに前記ハッシャに供給される、請求項７に記載の方法。
【請求項９】
前記バイナリ識別子は、ソースＩＰアドレスであり、前記他のパケット固有データは、請求項１〜６のいずれかに従って圧縮された宛先ＩＰアドレスを包含する、請求項８に記載の方法。
【請求項１０】
請求項１〜９のいずれかに記載の方法を実装するようになっている圧縮器。
【請求項１１】
請求項１０に記載の圧縮器を包含するハッシャ。
【請求項１２】
請求項１〜９のうちのいずれか１項に記載の方法の前記ステップをコンピュータに実行させるコンピュータ・プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−１２９９９４（Ｐ２０１２−１２９９９４Ａ）
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願番号】特願２０１１−２６３５７７（Ｐ２０１１−２６３５７７）
【出願日】平成２３年１２月１日（２０１１．１２．１）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願日】平成２３年１２月１日（２０１１．１２．１）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]