JP2000244577A - Ｔｒｉｅメモリによって転送基準値をデータパケットと関連づける方法およびこの方法を用いたパケット処理装置 - Google Patents
Ｔｒｉｅメモリによって転送基準値をデータパケットと関連づける方法およびこの方法を用いたパケット処理装置Info
- Publication number
- JP2000244577A JP2000244577A JP2000034023A JP2000034023A JP2000244577A JP 2000244577 A JP2000244577 A JP 2000244577A JP 2000034023 A JP2000034023 A JP 2000034023A JP 2000034023 A JP2000034023 A JP 2000034023A JP 2000244577 A JP2000244577 A JP 2000244577A
- Authority
- JP
- Japan
- Prior art keywords
- memory
- header
- packet
- reference value
- trie
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 230000015654 memory Effects 0.000 title claims abstract description 95
- 238000012546 transfer Methods 0.000 title claims abstract description 25
- 238000012545 processing Methods 0.000 title claims abstract description 9
- 238000000034 method Methods 0.000 title claims description 27
- 238000004458 analytical method Methods 0.000 claims description 45
- 238000012986 modification Methods 0.000 claims 1
- 230000004048 modification Effects 0.000 claims 1
- 230000008569 process Effects 0.000 description 9
- 238000010586 diagram Methods 0.000 description 8
- 239000013256 coordination polymer Substances 0.000 description 6
- 230000007704 transition Effects 0.000 description 6
- 238000012360 testing method Methods 0.000 description 4
- 230000009471 action Effects 0.000 description 3
- 230000000875 corresponding effect Effects 0.000 description 3
- 230000008859 change Effects 0.000 description 2
- 238000004891 communication Methods 0.000 description 2
- 238000001514 detection method Methods 0.000 description 2
- 230000006870 function Effects 0.000 description 2
- 230000006978 adaptation Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000001276 controlling effect Effects 0.000 description 1
- 238000005538 encapsulation Methods 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 230000008520 organization Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04Q—SELECTING
- H04Q11/00—Selecting arrangements for multiplex systems
- H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
- H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
- H04Q11/0478—Provisions for broadband connections
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/30—Peripheral units, e.g. input or output ports
- H04L49/3081—ATM peripheral units, e.g. policing, insertion or extraction
- H04L49/309—Header conversion, routing tables or routing tags
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/90—Buffering arrangements
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/40—Network security protocols
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Computer Security & Cryptography (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Computer And Data Communications (AREA)
Abstract
(57)【要約】
【課題】 ルーティング・アプリケーションにおいて、
ＴＲＩＥメモリにより提供される処理の柔軟性をさらに
向上させる。 【解決手段】 プロトコルデータを備える各々のパケッ
トのヘッダの異なる部分は、ＴＲＩＥメモリの異なるゲ
ートレジスタから連続して解析される。パケットが到着
すると、そのヘッダはバッファメモリ（１５）に記憶さ
れ、前記記憶されたヘッダの第１部分が解析される。ヘ
ッダ部分の各々の解析は、前記パケットと関連した転送
基準値、または、次の解析すべき部分とこの部分が解析
されるべき起点であるゲートレジスタとを捜し当てるこ
とを可能にする２つのコードを有する中間基準値のいず
れかを生成する。記憶されたヘッダの前記第１部分の解
析後に、該第１部分の後続部分は、前記転送基準値が生
成されるまで連続して生成された前記中間基準値に備え
られる前記第１，第２コードによって解析される。
ＴＲＩＥメモリにより提供される処理の柔軟性をさらに
向上させる。 【解決手段】 プロトコルデータを備える各々のパケッ
トのヘッダの異なる部分は、ＴＲＩＥメモリの異なるゲ
ートレジスタから連続して解析される。パケットが到着
すると、そのヘッダはバッファメモリ（１５）に記憶さ
れ、前記記憶されたヘッダの第１部分が解析される。ヘ
ッダ部分の各々の解析は、前記パケットと関連した転送
基準値、または、次の解析すべき部分とこの部分が解析
されるべき起点であるゲートレジスタとを捜し当てるこ
とを可能にする２つのコードを有する中間基準値のいず
れかを生成する。記憶されたヘッダの前記第１部分の解
析後に、該第１部分の後続部分は、前記転送基準値が生
成されるまで連続して生成された前記中間基準値に備え
られる前記第１，第２コードによって解析される。
Description
【０００１】
【発明の属する技術分野】本発明は、連想メモリに関
し、より詳細には、《ＴＲＩＥ》形式のメモリに関する
（これは、英語の動詞《reTRIEve》に由来している）。
し、より詳細には、《ＴＲＩＥ》形式のメモリに関する
（これは、英語の動詞《reTRIEve》に由来している）。
【０００２】
【従来の技術】《ＴＲＩＥ》メモリの原理は、R. de la
BriandaisおよびE. Fredkin等によって１９５０年代の
終わり頃に提案された（E. Fredkin等の《Trie Memor
y》, Communications of the ACM, Vol.3, No.9, Septe
mber 1960, 490-499頁を参照）。この原理は、認識すべ
きビットストリングを、固定長の（Ｋビットの）連続的
スライスに切り分け、かつ、これらを２次元テーブルＴ
に組み込むことにある。このテーブルの各々の行は、２
K個の基本「セル」（elementary cell）からなる「レジ
スタ」を構成する。レジスタ（Ｒ）はストリングの各々
のスライスに割り当てられ、かつ、このレジスタ内のセ
ルは、このスライスの０〜２K−１の範囲の値（Ｖ）と
関連づけられる。このように決定されたセルの内容（Ｃ
＝Ｔ［Ｒ，Ｖ］）は、後続のスライス（または「ポイン
タ」）に割り当てられたレジスタ、または、ストリング
の解析がこのスライスにおいて終了する必要がある場合
には解析基準値（analysis reference）（または《ステ
ータス》）の終わり、のいずれかを表す。
BriandaisおよびE. Fredkin等によって１９５０年代の
終わり頃に提案された（E. Fredkin等の《Trie Memor
y》, Communications of the ACM, Vol.3, No.9, Septe
mber 1960, 490-499頁を参照）。この原理は、認識すべ
きビットストリングを、固定長の（Ｋビットの）連続的
スライスに切り分け、かつ、これらを２次元テーブルＴ
に組み込むことにある。このテーブルの各々の行は、２
K個の基本「セル」（elementary cell）からなる「レジ
スタ」を構成する。レジスタ（Ｒ）はストリングの各々
のスライスに割り当てられ、かつ、このレジスタ内のセ
ルは、このスライスの０〜２K−１の範囲の値（Ｖ）と
関連づけられる。このように決定されたセルの内容（Ｃ
＝Ｔ［Ｒ，Ｖ］）は、後続のスライス（または「ポイン
タ」）に割り当てられたレジスタ、または、ストリング
の解析がこのスライスにおいて終了する必要がある場合
には解析基準値（analysis reference）（または《ステ
ータス》）の終わり、のいずれかを表す。
【０００３】前記テーブルへの入口ポイントでもある、
ストリングの第１スライスに割り当てられたレジスタ
は、「ゲート」とも称される。ビットストリングの形で
解析すべき、すなわちＴＲＩＥメモリの内容と比較すべ
きデータは、以後、「ルート（routes）」とも称され
る。「パス」という用語は、ルートと関連づけられたテ
ーブル内の連鎖状セルの連続を示すために用いられる。
テーブルの各々のレジスタは、該レジスタが１つ以上の
記憶されたルートの（ｉ＋１）番目のスライスに起因す
る場合には、オーダーｉ≧０であると称される。したが
って、ゲートレジスタはオーダーゼロである。ＴＲＩＥ
メモリは、オーダーｉ≧０のレジスタの各々と、各々の
ルートの最初のｉＫビットに対応するｉＫビットの独自
のシーケンスとを結びつける。テーブル内における前記
各々のルートのパスは、当該のレジスタのセルを経由し
て進む。
ストリングの第１スライスに割り当てられたレジスタ
は、「ゲート」とも称される。ビットストリングの形で
解析すべき、すなわちＴＲＩＥメモリの内容と比較すべ
きデータは、以後、「ルート（routes）」とも称され
る。「パス」という用語は、ルートと関連づけられたテ
ーブル内の連鎖状セルの連続を示すために用いられる。
テーブルの各々のレジスタは、該レジスタが１つ以上の
記憶されたルートの（ｉ＋１）番目のスライスに起因す
る場合には、オーダーｉ≧０であると称される。したが
って、ゲートレジスタはオーダーゼロである。ＴＲＩＥ
メモリは、オーダーｉ≧０のレジスタの各々と、各々の
ルートの最初のｉＫビットに対応するｉＫビットの独自
のシーケンスとを結びつける。テーブル内における前記
各々のルートのパスは、当該のレジスタのセルを経由し
て進む。
【０００４】以下の例は、Ｋ＝４という特定の場合にお
いて、データがＴＲＩＥメモリ内に記憶される方法に関
する例示を提供する。各々のスライスの値は、１６進数
のディジット（０，１，...Ｅ，Ｆ）で表され、かつ、
各々のレジスタは、２4＝１６個のセルを有している。
いて、データがＴＲＩＥメモリ内に記憶される方法に関
する例示を提供する。各々のスライスの値は、１６進数
のディジット（０，１，...Ｅ，Ｆ）で表され、かつ、
各々のレジスタは、２4＝１６個のセルを有している。
【０００５】認識すべきルートが４５Ａ４，４５ＡＢ，
６７ＡＢ，７８８Ａ，および７８８ＢＤのコードで始ま
るルートであり、これらのコードに対してステータスＳ
０，Ｓ１，Ｓ２，Ｓ３，およびＳ０がそれぞれ割り当て
られたと仮定する（同じステータスを幾つかのルートが
共有してもよい）。レジスタＲに関して行インデクス
を、スライスの値Ｖに関して列インデクスを用いること
と、レジスタＲ0＝０をゲートとして用いることとによ
り、ＴＲＩＥメモリのテーブルは、図１に示されるよう
に表される。下線を施されたデータがステータスであ
る。コード４５Ａ４，４５ＡＢ，６７ＡＢ，７８８Ａ，
７８８ＢＤは、以下のパスにより、図１のテーブルにお
いてそれぞれ表される。 Ｔ［０，４］→Ｔ［１，５］→Ｔ［２，Ａ］→Ｔ［３，
４］； Ｔ［０，４］→Ｔ［１，５］→Ｔ［２，Ａ］→Ｔ［３，
Ｂ］； Ｔ［０，６］→Ｔ［４，７］→Ｔ［５，Ａ］→Ｔ［６，
Ｂ］； Ｔ［０，７］→Ｔ［７，８］→Ｔ［８，８］→Ｔ［９，
Ａ］； Ｔ［０，７］→Ｔ［７，８］→Ｔ［８，８］→Ｔ［９，
Ｂ］→Ｔ［10，Ｄ］；
６７ＡＢ，７８８Ａ，および７８８ＢＤのコードで始ま
るルートであり、これらのコードに対してステータスＳ
０，Ｓ１，Ｓ２，Ｓ３，およびＳ０がそれぞれ割り当て
られたと仮定する（同じステータスを幾つかのルートが
共有してもよい）。レジスタＲに関して行インデクス
を、スライスの値Ｖに関して列インデクスを用いること
と、レジスタＲ0＝０をゲートとして用いることとによ
り、ＴＲＩＥメモリのテーブルは、図１に示されるよう
に表される。下線を施されたデータがステータスであ
る。コード４５Ａ４，４５ＡＢ，６７ＡＢ，７８８Ａ，
７８８ＢＤは、以下のパスにより、図１のテーブルにお
いてそれぞれ表される。 Ｔ［０，４］→Ｔ［１，５］→Ｔ［２，Ａ］→Ｔ［３，
４］； Ｔ［０，４］→Ｔ［１，５］→Ｔ［２，Ａ］→Ｔ［３，
Ｂ］； Ｔ［０，６］→Ｔ［４，７］→Ｔ［５，Ａ］→Ｔ［６，
Ｂ］； Ｔ［０，７］→Ｔ［７，８］→Ｔ［８，８］→Ｔ［９，
Ａ］； Ｔ［０，７］→Ｔ［７，８］→Ｔ［８，８］→Ｔ［９，
Ｂ］→Ｔ［10，Ｄ］；
【０００６】この例から、ｉＫビットの共通部分から始
まっている全てのコードが、これらのｉＫビットにより
形成されたシーケンスが関連しているオーダーｉのレジ
スタに通じているメモリ内における共通のイニシャルパ
スにより表されていることが分かる。
まっている全てのコードが、これらのｉＫビットにより
形成されたシーケンスが関連しているオーダーｉのレジ
スタに通じているメモリ内における共通のイニシャルパ
スにより表されていることが分かる。
【０００７】解析すべきルートを、値Ｖiの２進スライ
スの級数に切り分けけられたと考慮する場合に（ここ
で、０≦ｉ≦Ｎ、｛Ｒi｝は値Ｖiと関連づけられたレジ
スタの級数、さらに、Ｒ0はゲートレジスタを表す）、
実行される解析アルゴリズムは、図２に示されるもので
あってもよい。
スの級数に切り分けけられたと考慮する場合に（ここ
で、０≦ｉ≦Ｎ、｛Ｒi｝は値Ｖiと関連づけられたレジ
スタの級数、さらに、Ｒ0はゲートレジスタを表す）、
実行される解析アルゴリズムは、図２に示されるもので
あってもよい。
【０００８】このアルゴリズムの初期化段階１におい
て、解析ランクｉはゼロに設定され、かつ、ゲートレジ
スタＲ0がレジスタＲとして選択される。ランクｉの各
々の反復（iteraton）において、選択されたオーダーｉ
のレジスタ内のルートの（ｉ＋１）番目のスライスＶi
により示されるセルＴ［Ｒ，Ｖi］の内容Ｃが、段階２
において読み取られる。このセルが、テスト３におい
て、該セルに記憶されたビットＦＰ（Ｃ）に対する値１
によって示される連続解析ポインタ（continue analysi
s pointer）を有していれば、このポインタＰtr（Ｃ）
により表されるオーダーｉ＋１のレジスタが、段階４に
おいて、次の反復に対するレジスタＲとして選択され、
かつ、ランクｉがインクリメントされる。テスト３が、
ポインタを有していないセルを示せば（ＦＰ（Ｃ）＝
０）、関連したセル内に読み取られたステータスＲｅｆ
（Ｃ）が、段階５において、テーブルを調べた結果とし
て返される。
て、解析ランクｉはゼロに設定され、かつ、ゲートレジ
スタＲ0がレジスタＲとして選択される。ランクｉの各
々の反復（iteraton）において、選択されたオーダーｉ
のレジスタ内のルートの（ｉ＋１）番目のスライスＶi
により示されるセルＴ［Ｒ，Ｖi］の内容Ｃが、段階２
において読み取られる。このセルが、テスト３におい
て、該セルに記憶されたビットＦＰ（Ｃ）に対する値１
によって示される連続解析ポインタ（continue analysi
s pointer）を有していれば、このポインタＰtr（Ｃ）
により表されるオーダーｉ＋１のレジスタが、段階４に
おいて、次の反復に対するレジスタＲとして選択され、
かつ、ランクｉがインクリメントされる。テスト３が、
ポインタを有していないセルを示せば（ＦＰ（Ｃ）＝
０）、関連したセル内に読み取られたステータスＲｅｆ
（Ｃ）が、段階５において、テーブルを調べた結果とし
て返される。
【０００９】このアルゴリズムは、任意の数のスライス
を有するルートが解析されることを可能にする。異なる
ゲートに基づいてデータを管理して、同じテーブルを幾
つかのタイプの解析のために用いることもできる。さら
に、このアルゴリズムは、データの解析時間が制御され
ることを可能にし、Ｎ個のＫビットスライスの解析に
は、せいぜい、１度の反復の継続時間のＮ倍が必要とさ
れる。
を有するルートが解析されることを可能にする。異なる
ゲートに基づいてデータを管理して、同じテーブルを幾
つかのタイプの解析のために用いることもできる。さら
に、このアルゴリズムは、データの解析時間が制御され
ることを可能にし、Ｎ個のＫビットスライスの解析に
は、せいぜい、１度の反復の継続時間のＮ倍が必要とさ
れる。
【００１０】図２のアルゴリズムについては、テーブル
メモリへのアクセスを管理するハードウェア構成要素に
より非常に迅速に実行することができる。詳細には、高
性能のルータを、パケット交換遠距離通信ネットワーク
用に設定することが可能となる。パケットのヘッダは、
構成要素により急速に解析され、かつ、ルートと関連づ
けられたステータスは、例えば、このルートに従う終点
アドレスを生じさせているパケットがルーティングされ
る必要があるルータの出力ポートを指定する。
メモリへのアクセスを管理するハードウェア構成要素に
より非常に迅速に実行することができる。詳細には、高
性能のルータを、パケット交換遠距離通信ネットワーク
用に設定することが可能となる。パケットのヘッダは、
構成要素により急速に解析され、かつ、ルートと関連づ
けられたステータスは、例えば、このルートに従う終点
アドレスを生じさせているパケットがルーティングされ
る必要があるルータの出力ポートを指定する。
【００１１】このようなルータは、マルチプロトコル・
ルータであってもよい。この場合には、ヘッダの異なる
部分は、異なるゲートから解析される。例えば、用いら
れているプロトコルおよび／またはこのプロトコルのバ
ージョンを示す１つの（または幾つかの）ヘッダフィー
ルドの最初の解析については、最初のゲートから解析し
てもよい。この最初の解析は、ある基準値を供給し、こ
の基準値は、前記解析の論理的結果に対応しているが、
ヘッダの残りを解析するために用いるべき他のゲートレ
ジスタを示す連続解析ポインタにより、ＴＲＩＥメモリ
に組み込まれ得る。さらに、当該の基準値は、解析され
ているヘッダ内の所定数のビットによる時間遅延または
スキップを引き起こすこともでき、これにより、ヘッダ
のどの部分を次に解析すべきかを選択することができ
る。実際には、一定数の解析が、一般に連続して実行さ
れ、これにより、ヘッダの内容に応じて、サポートされ
たプロトコルにより必要とされる動作が引き起こされ
る。これらの解析のうち１つは、厳密に言えばルーティ
ング機能を完了するために必要とされる終点アドレスに
関連する。
ルータであってもよい。この場合には、ヘッダの異なる
部分は、異なるゲートから解析される。例えば、用いら
れているプロトコルおよび／またはこのプロトコルのバ
ージョンを示す１つの（または幾つかの）ヘッダフィー
ルドの最初の解析については、最初のゲートから解析し
てもよい。この最初の解析は、ある基準値を供給し、こ
の基準値は、前記解析の論理的結果に対応しているが、
ヘッダの残りを解析するために用いるべき他のゲートレ
ジスタを示す連続解析ポインタにより、ＴＲＩＥメモリ
に組み込まれ得る。さらに、当該の基準値は、解析され
ているヘッダ内の所定数のビットによる時間遅延または
スキップを引き起こすこともでき、これにより、ヘッダ
のどの部分を次に解析すべきかを選択することができ
る。実際には、一定数の解析が、一般に連続して実行さ
れ、これにより、ヘッダの内容に応じて、サポートされ
たプロトコルにより必要とされる動作が引き起こされ
る。これらの解析のうち１つは、厳密に言えばルーティ
ング機能を完了するために必要とされる終点アドレスに
関連する。
【００１２】上記に略述した形式のルータは、仏国特許
出願第２，７０７，７７５号明細書に記載されている。
ルータにおいてＴＲＩＥメモリを用いることに関して
は、T.B. Pei等による≪Putting Routing Tables in Si
licon≫（IEEE Network Magazine, January 1992, page
s 42-50）という論文を参照のこと。
出願第２，７０７，７７５号明細書に記載されている。
ルータにおいてＴＲＩＥメモリを用いることに関して
は、T.B. Pei等による≪Putting Routing Tables in Si
licon≫（IEEE Network Magazine, January 1992, page
s 42-50）という論文を参照のこと。
【００１３】幾つかの基本解析（elementary analysi
s）をともにつなぎ合わせ、かつ、これらの間にプログ
ラム可能なスキップを挿入することができるという事実
は、特に幾つかの層におけるＩＳＯモデルのカプセル化
されたプロトコルを処理する場合に、前記方法に高度の
柔軟性を与える。さらに、ヘッダのスライスを、これら
のスライスが到着した際に急速に解析することによって
速度が高められる。
s）をともにつなぎ合わせ、かつ、これらの間にプログ
ラム可能なスキップを挿入することができるという事実
は、特に幾つかの層におけるＩＳＯモデルのカプセル化
されたプロトコルを処理する場合に、前記方法に高度の
柔軟性を与える。さらに、ヘッダのスライスを、これら
のスライスが到着した際に急速に解析することによって
速度が高められる。
【００１４】しかしながら、ある状況においては、ある
種のフィールドを、これらのフィールドが到着した順序
以外の順序で検査するために、ヘッダ内において後方へ
移動できることが有用である。このことは、しばしば、
必要とされるメモリサイズの一層優れた最適化を可能に
する。さらに、このことは、ＲＳＶＰ予約（reservatio
n）プロトコルやマルチキャスト・プロトコルのよう
な、ある種のプロトコルにより必要とされる特徴であ
る。
種のフィールドを、これらのフィールドが到着した順序
以外の順序で検査するために、ヘッダ内において後方へ
移動できることが有用である。このことは、しばしば、
必要とされるメモリサイズの一層優れた最適化を可能に
する。さらに、このことは、ＲＳＶＰ予約（reservatio
n）プロトコルやマルチキャスト・プロトコルのよう
な、ある種のプロトコルにより必要とされる特徴であ
る。
【００１５】
【発明が解決しようとする課題】本発明の目的は、特に
ルーティング・アプリケーションにおいて、ＴＲＩＥメ
モリにより提供される処理の柔軟性をさらに向上させる
ことである。
ルーティング・アプリケーションにおいて、ＴＲＩＥメ
モリにより提供される処理の柔軟性をさらに向上させる
ことである。
【００１６】
【課題を解決するための手段】したがって、本発明は、
ＴＲＩＥメモリによって転送基準値（forwarding refer
ence）をデータパケットと関連づける方法を提案し、こ
れにより、前記ＴＲＩＥメモリの異なるゲートレジスタ
が、プロトコルデータを有する各々のパケットのヘッダ
の異なる部分を連続して解析する。パケットが到着する
と、そのヘッダは、バッファメモリに記憶され、かつ、
前記記憶されたヘッダの第１部分が解析される。パケッ
トのヘッダ部分の各々の解析は、前記パケットに関連づ
けられた前記転送基準値、または、前記バッファメモリ
の任意のロケーションにおいて後続の解析すべき部分を
捜し当てることを可能にする第１コードと、前記ＴＲＩ
Ｅメモリの任意のロケーションにおいて、ゲートレジス
タ（このゲートレジスタから、前記後続部分が解析され
ることになる）を捜し当てることを可能にする第２コー
ドとを有する中間基準値（intermediate reference）の
いずれかを生成する。記憶されたヘッダの前記第１部分
を解析した後に、前記第１部分の後続部分は、前記転送
基準値が得られるまで、連続して生成された前記中間基
準値に備えられた前記第１および第２コードにしたがっ
て解析される。
ＴＲＩＥメモリによって転送基準値（forwarding refer
ence）をデータパケットと関連づける方法を提案し、こ
れにより、前記ＴＲＩＥメモリの異なるゲートレジスタ
が、プロトコルデータを有する各々のパケットのヘッダ
の異なる部分を連続して解析する。パケットが到着する
と、そのヘッダは、バッファメモリに記憶され、かつ、
前記記憶されたヘッダの第１部分が解析される。パケッ
トのヘッダ部分の各々の解析は、前記パケットに関連づ
けられた前記転送基準値、または、前記バッファメモリ
の任意のロケーションにおいて後続の解析すべき部分を
捜し当てることを可能にする第１コードと、前記ＴＲＩ
Ｅメモリの任意のロケーションにおいて、ゲートレジス
タ（このゲートレジスタから、前記後続部分が解析され
ることになる）を捜し当てることを可能にする第２コー
ドとを有する中間基準値（intermediate reference）の
いずれかを生成する。記憶されたヘッダの前記第１部分
を解析した後に、前記第１部分の後続部分は、前記転送
基準値が得られるまで、連続して生成された前記中間基
準値に備えられた前記第１および第２コードにしたがっ
て解析される。
【００１７】その結果、前記ＴＲＩＥメモリの内容は、
もはや、前記パケットヘッダ自体と関連づけられた前記
基準値のみを示さない。さらに、これらの内容は、前記
メモリにより考慮された異なるコンフィギュレーション
に応じて、実行すべき基本解析のストリングからなるプ
ログラムをも備える。これらのストリングは、前記ヘッ
ダのどの部分を、さらに、前記ＴＲＩＥメモリのどのレ
ジスタから検査する必要があるのかを、ユーザーが任意
にかつ前述の処理の各々の段階において規定できる限り
は、完全にプログラム可能である。
もはや、前記パケットヘッダ自体と関連づけられた前記
基準値のみを示さない。さらに、これらの内容は、前記
メモリにより考慮された異なるコンフィギュレーション
に応じて、実行すべき基本解析のストリングからなるプ
ログラムをも備える。これらのストリングは、前記ヘッ
ダのどの部分を、さらに、前記ＴＲＩＥメモリのどのレ
ジスタから検査する必要があるのかを、ユーザーが任意
にかつ前述の処理の各々の段階において規定できる限り
は、完全にプログラム可能である。
【００１８】本発明の他の特徴は、上記に略述された方
法にしたがって動作する前記ＴＲＩＥ形式の連想記憶を
用いて受け取られた前記パケットの前記ヘッダを解析す
るための回路を有するパケット処理装置に関連する。こ
のような装置は、ヘッダ解析を必要とする任意の形式の
処理を実行することができる。詳細には、前記装置は、
ＩＰルータ、ファイヤウェルのような安全装置、測定装
置などであってもよい。
法にしたがって動作する前記ＴＲＩＥ形式の連想記憶を
用いて受け取られた前記パケットの前記ヘッダを解析す
るための回路を有するパケット処理装置に関連する。こ
のような装置は、ヘッダ解析を必要とする任意の形式の
処理を実行することができる。詳細には、前記装置は、
ＩＰルータ、ファイヤウェルのような安全装置、測定装
置などであってもよい。
【００１９】
【発明の実施の形態】本発明の他の方法および利点は、
以下に与えられる例についての説明から、さらに、添付
図面を参照して明確になる。前記説明は、あらゆる点に
おいて制限的なものではない。上述した図１は、ＴＲＩ
Ｅメモリの内容の例を示す。上述した図２は、ＴＲＩＥ
メモリを調べる手段として実行される従来の解析方法を
示すフローチャートである。図３は、本発明により提案
されたパケットルータのブロック図である。図４は、パ
ケットヘッダの一例の構成を示す図である。図５および
図６は、ルータのＴＲＩＥメモリ内のセルの構成を示す
図である。図７は、ＴＲＩＥメモリを調べるために本発
明により提案された解析手順を示すフローチャートであ
る。
以下に与えられる例についての説明から、さらに、添付
図面を参照して明確になる。前記説明は、あらゆる点に
おいて制限的なものではない。上述した図１は、ＴＲＩ
Ｅメモリの内容の例を示す。上述した図２は、ＴＲＩＥ
メモリを調べる手段として実行される従来の解析方法を
示すフローチャートである。図３は、本発明により提案
されたパケットルータのブロック図である。図４は、パ
ケットヘッダの一例の構成を示す図である。図５および
図６は、ルータのＴＲＩＥメモリ内のセルの構成を示す
図である。図７は、ＴＲＩＥメモリを調べるために本発
明により提案された解析手順を示すフローチャートであ
る。
【００２０】以下の説明を例示する手段として、本発明
により提案されたルータによりルーティングされたパケ
ットが非同期転送モード（ＡＴＭ）ネットワーク上にお
いて伝送される場合を検証する。さらに、各々のパケッ
トのヘッダが常に１つのＡＴＭセル内に備えられている
と仮定する。
により提案されたルータによりルーティングされたパケ
ットが非同期転送モード（ＡＴＭ）ネットワーク上にお
いて伝送される場合を検証する。さらに、各々のパケッ
トのヘッダが常に１つのＡＴＭセル内に備えられている
と仮定する。
【００２１】図３に示されたルータ１０は、ホストコン
ピュータ１１と関連して動作する。ホストコンピュータ
１１は、特に、ルーティング処理を管理するために、パ
ケットを送信かつ受信することができる。この目的に対
し、ルータ１０の入力と出力とにおいて仮想チャンネル
（ＶＣ）を有する。
ピュータ１１と関連して動作する。ホストコンピュータ
１１は、特に、ルーティング処理を管理するために、パ
ケットを送信かつ受信することができる。この目的に対
し、ルータ１０の入力と出力とにおいて仮想チャンネル
（ＶＣ）を有する。
【００２２】前記ルータ１０は、解析モジュール１３に
より生じた、これ以後《転送基準値（forwarding refer
ence）》または《最終ステータス》と称される命令にし
たがって受け取られたパケットを、ＴＲＩＥメモリテー
ブルとして構成されたメモリ１４から転送する転送モジ
ュール１２を有している。ＡＴＭネットワーク装備の場
合において、転送モジュール１２は、本質的に、仮想パ
ス識別子および仮想チャンネル識別子ＶＰＩ／ＶＣＩ
（《Virtual Path Identifier / Virtual Channel Iden
tifier》）と、仮想パス内の仮想チャンネルマージャ
（merger）と、装置の出力ポートへのパケットの供給と
の変換を実行することができる。この目的に対し、ＴＲ
ＩＥメモリ１４内に記憶された転送基準値を構成し得
る、出ていくパケットのＶＰＩ／ＶＣＩの組を知る必要
がある。
より生じた、これ以後《転送基準値（forwarding refer
ence）》または《最終ステータス》と称される命令にし
たがって受け取られたパケットを、ＴＲＩＥメモリテー
ブルとして構成されたメモリ１４から転送する転送モジ
ュール１２を有している。ＡＴＭネットワーク装備の場
合において、転送モジュール１２は、本質的に、仮想パ
ス識別子および仮想チャンネル識別子ＶＰＩ／ＶＣＩ
（《Virtual Path Identifier / Virtual Channel Iden
tifier》）と、仮想パス内の仮想チャンネルマージャ
（merger）と、装置の出力ポートへのパケットの供給と
の変換を実行することができる。この目的に対し、ＴＲ
ＩＥメモリ１４内に記憶された転送基準値を構成し得
る、出ていくパケットのＶＰＩ／ＶＣＩの組を知る必要
がある。
【００２３】ルーティングすべきパケットのヘッダを有
する各々のＡＴＭセルは、バッファメモリ１５を介して
通過し、解析モジュール１３は、これらのヘッダの一部
をＴＲＩＥメモリ１４によって解析するために、前記バ
ッファメモリ１５にアクセスする。この解析は、例え
ば、カルテット（Ｋ＝４）により実行される。
する各々のＡＴＭセルは、バッファメモリ１５を介して
通過し、解析モジュール１３は、これらのヘッダの一部
をＴＲＩＥメモリ１４によって解析するために、前記バ
ッファメモリ１５にアクセスする。この解析は、例え
ば、カルテット（Ｋ＝４）により実行される。
【００２４】前記ルータ１０を機器構成（configurin
g）することは、関連データをＴＲＩＥメモリ１４に記
憶することにある。この動作は、ホストコンピュータ１
１の制御の下でＴＲＩＥメモリを管理するモジュール
（図示せず）により実行される。この機器構成命令につ
いては、ネットワークを介して伝送されかつルータ１０
にアドレス指定されたパケットの形で受け取ってもよ
い。ＴＲＩＥメモリ１４の内容がどのように動的に管理
され得るのかの詳細については、仏国特許明細書９８１
１８５６を参照のこと。
g）することは、関連データをＴＲＩＥメモリ１４に記
憶することにある。この動作は、ホストコンピュータ１
１の制御の下でＴＲＩＥメモリを管理するモジュール
（図示せず）により実行される。この機器構成命令につ
いては、ネットワークを介して伝送されかつルータ１０
にアドレス指定されたパケットの形で受け取ってもよ
い。ＴＲＩＥメモリ１４の内容がどのように動的に管理
され得るのかの詳細については、仏国特許明細書９８１
１８５６を参照のこと。
【００２５】図３に示されたルータの場合に、解析モジ
ュール１３は、ルータによりサポートされた通信プロト
コルに応じて、ある検査を実行しかつパケットヘッダに
作用を適用するようにプログラムされた制御装置１６と
共働する。この制御装置１６の外側において、ルータ１
０の動作は、パケット伝送プロトコルから独立してい
る。
ュール１３は、ルータによりサポートされた通信プロト
コルに応じて、ある検査を実行しかつパケットヘッダに
作用を適用するようにプログラムされた制御装置１６と
共働する。この制御装置１６の外側において、ルータ１
０の動作は、パケット伝送プロトコルから独立してい
る。
【００２６】図４は、本発明のルータにより処理するこ
とができるパケットに関するヘッダ構成の特定の例を示
す。この例においては、前記パケットは、ＵＤＰ（《Us
er Datagram Protocol》）アプリケーションプロトコル
を保持するＩＰＶ４（《Internet Protocol-Version
4》）パケットであり、ＬＬＣ−ＳＮＡＰ（《Logical L
ink Control - Sub Network Access Protocol》）レイ
ヤ２プロトコルによってＡＴＭセル形式にカプセル化さ
れている。図面に示されたフィールドネームは、これら
のプロトコルに付随した関連仕様において用いられてい
るものである。解析すべき全体的なヘッダは、ＡＴＭセ
ルの５オクテットヘッダと、ＬＬＣ−ＳＮＡＰヘッダ
と、ＩＰＶ４プロトコルとそのＵＤＰ拡張子のヘッダと
のインタリーブされた配置からなっている。
とができるパケットに関するヘッダ構成の特定の例を示
す。この例においては、前記パケットは、ＵＤＰ（《Us
er Datagram Protocol》）アプリケーションプロトコル
を保持するＩＰＶ４（《Internet Protocol-Version
4》）パケットであり、ＬＬＣ−ＳＮＡＰ（《Logical L
ink Control - Sub Network Access Protocol》）レイ
ヤ２プロトコルによってＡＴＭセル形式にカプセル化さ
れている。図面に示されたフィールドネームは、これら
のプロトコルに付随した関連仕様において用いられてい
るものである。解析すべき全体的なヘッダは、ＡＴＭセ
ルの５オクテットヘッダと、ＬＬＣ−ＳＮＡＰヘッダ
と、ＩＰＶ４プロトコルとそのＵＤＰ拡張子のヘッダと
のインタリーブされた配置からなっている。
【００２７】他の形式のプロトコルおよびカプセル化
を、ルータ１０によりサポートすることもできる。例え
ば、レイヤ２においてＳＮＡＰプロトコルの代わりに、
ＰＰＰ（《Point-to-Point Protocol》）プロトコルを
扱うことや、あるいはまた、レイヤ２および／またはレ
イヤ３においてＭＰＬＳ（《Multi-Protocol Label Swi
tching》）体系を扱うことも可能である。これらの条件
下において、以下の一続きのヘッダ形式が、ＡＴＭセル
のヘッダに続くＡＡＬ５（《ATM Adaptation Layer No
5》）フレームにおいて遭遇される可能性がある。 ＩＰ ＩＰ，ＩＰ ＬＬＣ−ＳＮＡＰ，ＩＰ ＬＬＣ−ＰＰＰ，ＩＰ ＭＰＬＳ ＭＰＬＳ,...ＭＰＬＳ ＬＬＣ−ＳＮＡＰ，ＭＰＬＳ ＭＰＬＳ，ＩＰ ＭＰＬＳ,...ＭＰＬＳ，ＩＰ ＭＰＬＳ，ＬＬＣ−ＳＮＡＰ，ＩＰ ＭＰＬＳ,...ＭＰＬＳ，ＬＬＣ−ＳＮＡＰ，ＩＰ ここで、ＩＰは、インターネットプロトコルのバージョ
ン４またはバージョン６のいずれかと、ネットワークレ
イヤ（ＴＣＰ，ＵＤＰ...）以上のレイヤのヘッダとを
示す。
を、ルータ１０によりサポートすることもできる。例え
ば、レイヤ２においてＳＮＡＰプロトコルの代わりに、
ＰＰＰ（《Point-to-Point Protocol》）プロトコルを
扱うことや、あるいはまた、レイヤ２および／またはレ
イヤ３においてＭＰＬＳ（《Multi-Protocol Label Swi
tching》）体系を扱うことも可能である。これらの条件
下において、以下の一続きのヘッダ形式が、ＡＴＭセル
のヘッダに続くＡＡＬ５（《ATM Adaptation Layer No
5》）フレームにおいて遭遇される可能性がある。 ＩＰ ＩＰ，ＩＰ ＬＬＣ−ＳＮＡＰ，ＩＰ ＬＬＣ−ＰＰＰ，ＩＰ ＭＰＬＳ ＭＰＬＳ,...ＭＰＬＳ ＬＬＣ−ＳＮＡＰ，ＭＰＬＳ ＭＰＬＳ，ＩＰ ＭＰＬＳ,...ＭＰＬＳ，ＩＰ ＭＰＬＳ，ＬＬＣ−ＳＮＡＰ，ＩＰ ＭＰＬＳ,...ＭＰＬＳ，ＬＬＣ−ＳＮＡＰ，ＩＰ ここで、ＩＰは、インターネットプロトコルのバージョ
ン４またはバージョン６のいずれかと、ネットワークレ
イヤ（ＴＣＰ，ＵＤＰ...）以上のレイヤのヘッダとを
示す。
【００２８】ＬＬＣ−ＳＮＡＰ／ＩＰＶ４／ＵＤＰの特
定の場合において、図４のハッシュ領域は、ルーティン
グ工程に関連し得るヘッダフィールドを示す。適用され
るルーティングの形式に応じて、これらのフィールドの
うち幾つかについては、図面に示された非ハッシュフィ
ールドとともに無視してもよい。ＴＲＩＥメモリのサイ
ズを不必要に増大させることを回避するために、これら
のフィールドの内容は、解析処理の間は、単に無視され
る。
定の場合において、図４のハッシュ領域は、ルーティン
グ工程に関連し得るヘッダフィールドを示す。適用され
るルーティングの形式に応じて、これらのフィールドの
うち幾つかについては、図面に示された非ハッシュフィ
ールドとともに無視してもよい。ＴＲＩＥメモリのサイ
ズを不必要に増大させることを回避するために、これら
のフィールドの内容は、解析処理の間は、単に無視され
る。
【００２９】したがって、前記解析は、部分的解析を連
続的に受けることになるヘッダの異なる部分に集中し、
これにより、最終部分（この最終部分に対し、ＴＲＩＥ
メモリ１４が、モジュール１２に向けられた転送基準値
を供給する）が到達されるまで中間基準値（intermedia
te reference）が供給される。
続的に受けることになるヘッダの異なる部分に集中し、
これにより、最終部分（この最終部分に対し、ＴＲＩＥ
メモリ１４が、モジュール１２に向けられた転送基準値
を供給する）が到達されるまで中間基準値（intermedia
te reference）が供給される。
【００３０】本発明により提案された方法は、ヘッダフ
ィールドが任意の順序で解析されることを可能にする。
このことは、フィールドをこれらが現れる順に解析する
ことでは十分ではない一定数の状況において有用であ
る。例えば、以下のことが指摘される。 − 必要とされるメモリサイズを制限するために、ＩＰ
ヘッダのＴＯＳ（Typeof Service）フィールドを（これ
らのフィールドは逆の順序で現れるが）、終点アドレス
の後に解析することは重要である。 − ＲＳＶＰ形式の予約プロトコルに関して、レイヤ４
ヘッダを解析した後にＩＰヘッダの《プロトコル》フィ
ールドと、《終点アドレス》フィールドとへ戻ることが
できることが必要である。 − マルチキャスト・アプリケーションにおいて、幾つ
かのノード間におけるルーピングの発生を防ぐべく、Ｉ
ＰヘッダのＴＴＬ（Time to Live）フィールドと、ＡＴ
Ｍヘッダに入力されたルータのＶＰＩ／ＶＣＩ識別子と
へ戻ることができることは重要である。
ィールドが任意の順序で解析されることを可能にする。
このことは、フィールドをこれらが現れる順に解析する
ことでは十分ではない一定数の状況において有用であ
る。例えば、以下のことが指摘される。 − 必要とされるメモリサイズを制限するために、ＩＰ
ヘッダのＴＯＳ（Typeof Service）フィールドを（これ
らのフィールドは逆の順序で現れるが）、終点アドレス
の後に解析することは重要である。 − ＲＳＶＰ形式の予約プロトコルに関して、レイヤ４
ヘッダを解析した後にＩＰヘッダの《プロトコル》フィ
ールドと、《終点アドレス》フィールドとへ戻ることが
できることが必要である。 − マルチキャスト・アプリケーションにおいて、幾つ
かのノード間におけるルーピングの発生を防ぐべく、Ｉ
ＰヘッダのＴＴＬ（Time to Live）フィールドと、ＡＴ
Ｍヘッダに入力されたルータのＶＰＩ／ＶＣＩ識別子と
へ戻ることができることは重要である。
【００３１】ＴＲＩＥメモリ１４におけるデータの構
成、および、これらのデータが調べられる方法は、解析
されているヘッダフィールド間とＴＲＩＥメモリのゲー
トレジスタ間とにおいて必要とされ得る任意のスキップ
をプログラムすることを可能にするために適合される。
成、および、これらのデータが調べられる方法は、解析
されているヘッダフィールド間とＴＲＩＥメモリのゲー
トレジスタ間とにおいて必要とされ得る任意のスキップ
をプログラムすることを可能にするために適合される。
【００３２】特定の実施形態において、図５および図６
は、ＴＲＩＥメモリ１４の空ではない基本セル内に備え
られるデータ構造を示す。この例においては、各々の基
本セルは、３２ビットのメモリ領域を示す。ＴＲＩＥメ
モリ内のセルの最初の３ビットは、制御装置１６の状態
を制御するためのコマンドフィールドＣＴを形成する。
は、ＴＲＩＥメモリ１４の空ではない基本セル内に備え
られるデータ構造を示す。この例においては、各々の基
本セルは、３２ビットのメモリ領域を示す。ＴＲＩＥメ
モリ内のセルの最初の３ビットは、制御装置１６の状態
を制御するためのコマンドフィールドＣＴを形成する。
【００３３】例によれば、前記制御装置１６は、５つの
状態を有する。 − 《非活動》 バッファメモリ１５内にヘッダが存在
しない場合； − 《ＡＴＭ》 モジュール１３が、ＡＴＭヘッダのＶ
ＰＩ／ＶＣＩ識別子の解析を進行中の場合； − 《ＭＰＬＳ》 モジュール１３が、ＭＰＬＳヘッダ
の解析を進行中の場合； − 《ＩＰ》 モジュール１３が、ＩＰヘッダまたはそ
の拡張子の解析を進行中の場合； − 《other》 モジュール１３が、他の形式のヘッダ
（ＬＬＣ，ＳＮＡＰ，ＰＰＰ，...）の解析を進行中の
場合。
状態を有する。 − 《非活動》 バッファメモリ１５内にヘッダが存在
しない場合； − 《ＡＴＭ》 モジュール１３が、ＡＴＭヘッダのＶ
ＰＩ／ＶＣＩ識別子の解析を進行中の場合； − 《ＭＰＬＳ》 モジュール１３が、ＭＰＬＳヘッダ
の解析を進行中の場合； − 《ＩＰ》 モジュール１３が、ＩＰヘッダまたはそ
の拡張子の解析を進行中の場合； − 《other》 モジュール１３が、他の形式のヘッダ
（ＬＬＣ，ＳＮＡＰ，ＰＰＰ，...）の解析を進行中の
場合。
【００３４】前記ＴＲＩＥメモリの基本セルのコマンド
フィールドＣＴは、例えば、以下のように符号化され
る。 − ＣＴ＝０００： 制御装置の状態が変更されていな
い − ＣＴ＝００１： 解析の終了 − ＣＴ＝０１ａ： 《other》状態への移行 − ＣＴ＝１０ａ： 《ＩＰ》状態への移行 − ＣＴ＝１１ａ： 《ＭＰＬＳ》状態への移行
フィールドＣＴは、例えば、以下のように符号化され
る。 − ＣＴ＝０００： 制御装置の状態が変更されていな
い − ＣＴ＝００１： 解析の終了 − ＣＴ＝０１ａ： 《other》状態への移行 − ＣＴ＝１０ａ： 《ＩＰ》状態への移行 − ＣＴ＝１１ａ： 《ＭＰＬＳ》状態への移行
【００３５】上記のビットａは、フレームがホストコン
ピュータ１１から来たのかどうかを示し、これにより、
制御装置１６は、必要に応じて、ＩＰＶ４ヘッダのＴＴ
Ｌフィールドおよび《チェックサム》フィールドの処理
を抑制することができる。
ピュータ１１から来たのかどうかを示し、これにより、
制御装置１６は、必要に応じて、ＩＰＶ４ヘッダのＴＴ
Ｌフィールドおよび《チェックサム》フィールドの処理
を抑制することができる。
【００３６】図５および図６に示された例において、Ｔ
ＲＩＥメモリの基本セルのうち１８個の最下位ビット
は、図５の場合には（ゲートレジスタであろうとなかろ
うと）ＴＲＩＥメモリの次レジスタへのポインタ（この
ポインタから解析が継続されるべきである）、または、
図６に示された例においてはモジュール１２に向けられ
た転送基準値のいずれかを有するフィールドＰtrを形成
する。
ＲＩＥメモリの基本セルのうち１８個の最下位ビット
は、図５の場合には（ゲートレジスタであろうとなかろ
うと）ＴＲＩＥメモリの次レジスタへのポインタ（この
ポインタから解析が継続されるべきである）、または、
図６に示された例においてはモジュール１２に向けられ
た転送基準値のいずれかを有するフィールドＰtrを形成
する。
【００３７】後者の場合には、転送基準値の発行がＴＲ
ＩＥメモリを用いて解析処理を終了させるので、コマン
ドフィールドＣＴは００１を有する。
ＩＥメモリを用いて解析処理を終了させるので、コマン
ドフィールドＣＴは００１を有する。
【００３８】図５に示された場合において、フィールド
Ｐtrに備えられるポインタは、何が２ビットのカウンテ
ィング・フィールドＣＰに備えられているのかに応じ
て、直接的または間接的に、連続解析レジスタを示し得
る。カウンタについては、ＴＲＩＥメモリの全てのセル
に割り当ててもよい。次に、このカウンタは、このセル
が、解析中に後続されるパスにおいて遭遇される毎にイ
ンクリメントされる。各々のカウンタＶ（Ａ）は、ＴＲ
ＩＥメモリ内の連続解析ポインタへのポインタＰＴ
（Ａ）を備える他のロケーションと連結されたメモリロ
ケーションに配置される。
Ｐtrに備えられるポインタは、何が２ビットのカウンテ
ィング・フィールドＣＰに備えられているのかに応じ
て、直接的または間接的に、連続解析レジスタを示し得
る。カウンタについては、ＴＲＩＥメモリの全てのセル
に割り当ててもよい。次に、このカウンタは、このセル
が、解析中に後続されるパスにおいて遭遇される毎にイ
ンクリメントされる。各々のカウンタＶ（Ａ）は、ＴＲ
ＩＥメモリ内の連続解析ポインタへのポインタＰＴ
（Ａ）を備える他のロケーションと連結されたメモリロ
ケーションに配置される。
【００３９】前記カウンティング・フィールドＣＰが０
０以外に何らかの値を有していれば、ＴＲＩＥメモリセ
ルのフィールドＰtrは、関連するカウンタＶ（Ａ）が記
憶されているメモリロケーションのアドレスを有してお
り、かつ、この関連カウンタＶ（Ａ）と連結されたロケ
ーションＰＴ（Ａ）は、解析を継続するために用いる必
要があるＴＲＩＥメモリ内のレジスタへのポインタを有
している。フィールドＣＰの２ビットが００であれば、
基本セルのフィールドＰtrは、ＴＲＩＥメモリ内の連続
解析レジスタを直接的に指す。
０以外に何らかの値を有していれば、ＴＲＩＥメモリセ
ルのフィールドＰtrは、関連するカウンタＶ（Ａ）が記
憶されているメモリロケーションのアドレスを有してお
り、かつ、この関連カウンタＶ（Ａ）と連結されたロケ
ーションＰＴ（Ａ）は、解析を継続するために用いる必
要があるＴＲＩＥメモリ内のレジスタへのポインタを有
している。フィールドＣＰの２ビットが００であれば、
基本セルのフィールドＰtrは、ＴＲＩＥメモリ内の連続
解析レジスタを直接的に指す。
【００４０】次にパケットヘッダのどの部分を解析すべ
きかを示すために、転送基準値（図５）を有していない
基本セルは、２ビットのフォーマットフィールドＦＭ
と、７ビットのシフトフィールドＤＰとを有する。フィ
ールドＦＭは、バッファメモリ１５内における関連ロケ
ーションの数値表示のフォーマットを示す。
きかを示すために、転送基準値（図５）を有していない
基本セルは、２ビットのフォーマットフィールドＦＭ
と、７ビットのシフトフィールドＤＰとを有する。フィ
ールドＦＭは、バッファメモリ１５内における関連ロケ
ーションの数値表示のフォーマットを示す。
【００４１】この表示は、以下のものであり得る。 − 連続的（ＦＭ＝００）／解析すべきカルテットが、
メモリ１５に記憶されたヘッダ内において直接に順々に
続く場合 − 絶対的（ＦＭ＝１１）／カルテットの絶対的な位置
を、解析されているサブヘッダから独立して示す（この
ことは、例えば、マルチキャストアプリケーションにお
いてＩＰヘッダを処理するときに、ＡＴＭヘッダのＶＣ
フィールドに戻ることが必要である場合に有用である） − 差分的（ＦＭ＝１０）／現在のカルテットに対して
次のカルテットの位置を表すためのものであり、このこ
とは、（例えば、《other》状態において）あるヘッダ
の長さが先験的に既知ではない場合に有用である − 相対的（ＦＭ＝０１）／制御装置１６により管理さ
れたオフセット値により捜し当てられた、バッファメモ
リ１５の所定のロケーションに対して次のカルテットの
位置を表すためのものである。この値ＯＦＦＳＥＴは、
通常は、現在解析されているサブヘッダの開始を示す。
制御装置１６は、状態の移行中に、以前の状態に対応す
るヘッダ長さを加えることにより、この値を管理する。
メモリ１５に記憶されたヘッダ内において直接に順々に
続く場合 − 絶対的（ＦＭ＝１１）／カルテットの絶対的な位置
を、解析されているサブヘッダから独立して示す（この
ことは、例えば、マルチキャストアプリケーションにお
いてＩＰヘッダを処理するときに、ＡＴＭヘッダのＶＣ
フィールドに戻ることが必要である場合に有用である） − 差分的（ＦＭ＝１０）／現在のカルテットに対して
次のカルテットの位置を表すためのものであり、このこ
とは、（例えば、《other》状態において）あるヘッダ
の長さが先験的に既知ではない場合に有用である − 相対的（ＦＭ＝０１）／制御装置１６により管理さ
れたオフセット値により捜し当てられた、バッファメモ
リ１５の所定のロケーションに対して次のカルテットの
位置を表すためのものである。この値ＯＦＦＳＥＴは、
通常は、現在解析されているサブヘッダの開始を示す。
制御装置１６は、状態の移行中に、以前の状態に対応す
るヘッダ長さを加えることにより、この値を管理する。
【００４２】前記制御装置１６により実行される他のタ
スクは、ＩＰＶ４ヘッダの《チャックサム》フィールド
に基づくエラーチェックと、このＩＰヘッダのＴＯＳ，
ＴＴＬフィールドにおける任意の操作とを備えている。
このような変更は、いずれも、転送基準値を備えたＴＲ
ＩＥメモリにより供給されるパラメータに基づいて、解
析処理の終わりに実行される。これらのパラメータは、
転送基準値を有する各々の基本セルの２ビットフィール
ドＴＴと８ビットフィールドＰＡとに備えられる（図
６）。コーディングは、例えば、以下の通りである。 − ＴＴ＝００： ＴＯＳ，ＴＴＬフィールドに何の変
更もない（ホストコンピュータ１１に対して向けられた
パケット用に用いることができる） − ＴＴ＝０１： ＴＴＬを１だけデクリメントする − ＴＴ＝１０： ＴＴＬをＰＡフィールドの内容だけ
デクリメントする − ＴＴ＝１１： ＴＴＬを１だけデクリメントし、か
つ、ＴＯＳをＰＡフィールドの内容に置き換える
スクは、ＩＰＶ４ヘッダの《チャックサム》フィールド
に基づくエラーチェックと、このＩＰヘッダのＴＯＳ，
ＴＴＬフィールドにおける任意の操作とを備えている。
このような変更は、いずれも、転送基準値を備えたＴＲ
ＩＥメモリにより供給されるパラメータに基づいて、解
析処理の終わりに実行される。これらのパラメータは、
転送基準値を有する各々の基本セルの２ビットフィール
ドＴＴと８ビットフィールドＰＡとに備えられる（図
６）。コーディングは、例えば、以下の通りである。 − ＴＴ＝００： ＴＯＳ，ＴＴＬフィールドに何の変
更もない（ホストコンピュータ１１に対して向けられた
パケット用に用いることができる） − ＴＴ＝０１： ＴＴＬを１だけデクリメントする − ＴＴ＝１０： ＴＴＬをＰＡフィールドの内容だけ
デクリメントする − ＴＴ＝１１： ＴＴＬを１だけデクリメントし、か
つ、ＴＯＳをＰＡフィールドの内容に置き換える
【００４３】バージョン４における《ＡＴＭ》または
《ＭＰＬＳ》または《other》から《ＩＰ》への移行に
基づいて、制御装置１６は、ＩＰＶ４ヘッダの《チェッ
クサム》フィールドの内容がヘッダの残りと一致するこ
とを確実にするために、仕様に従ってこれらのヘッダに
おいて適用されたエラー検出コーディングに応じて検査
する。《ＩＰ》から《不活動》状態への移行（ＣＴ＝０
０１）に基づいて、制御装置１６は、ＩＰＶ４ヘッダの
《チェックサム》フィールドを、入力ヘッダに備えられ
る《チェックサム》フィールドを合計することにより更
新し、かつ、ＴＴＬおよび／またはＴＯＳフィールドに
適用された変更に基づいて計算されたエラー検出コード
を更新する。
《ＭＰＬＳ》または《other》から《ＩＰ》への移行に
基づいて、制御装置１６は、ＩＰＶ４ヘッダの《チェッ
クサム》フィールドの内容がヘッダの残りと一致するこ
とを確実にするために、仕様に従ってこれらのヘッダに
おいて適用されたエラー検出コーディングに応じて検査
する。《ＩＰ》から《不活動》状態への移行（ＣＴ＝０
０１）に基づいて、制御装置１６は、ＩＰＶ４ヘッダの
《チェックサム》フィールドを、入力ヘッダに備えられ
る《チェックサム》フィールドを合計することにより更
新し、かつ、ＴＴＬおよび／またはＴＯＳフィールドに
適用された変更に基づいて計算されたエラー検出コード
を更新する。
【００４４】図７は、上述した例においてモジュール１
３により実行することができる解析手順を示すフローチ
ャートを与えている。初期化２０に基づき、解析された
カルテットのうちｉ番目は、バッファメモリ１５におけ
るＡＴＭヘッダの開始を示すためにゼロに設定され、基
本ゲートレジスタＲ0が、レジスタＲとして選択され、
かつ、制御装置１６は、アクティブ命令（《非活動》状
態から《ＡＴＭ》状態への切り替え）を受け取る。
３により実行することができる解析手順を示すフローチ
ャートを与えている。初期化２０に基づき、解析された
カルテットのうちｉ番目は、バッファメモリ１５におけ
るＡＴＭヘッダの開始を示すためにゼロに設定され、基
本ゲートレジスタＲ0が、レジスタＲとして選択され、
かつ、制御装置１６は、アクティブ命令（《非活動》状
態から《ＡＴＭ》状態への切り替え）を受け取る。
【００４５】各々の反復ｉにおいて、バッファメモリ１
５に記憶されたヘッダの（ｉ＋１）番目のカルテットＶ
iにより示された、選択されたレジスタＲの基本セルＴ
［Ｒ，Ｖi］の内容Ｃが、段階２１において読み取られ
る。このセルのコマンドフィールドＣＴ（Ｃ）が００１
でなければ（テスト２２）、このコマンドフィールドの
内容は、段階２３において、制御装置１６へ適用され、
これにより、制御装置１６は、必要であれば、対応する
作用を続行するために必要とされる状態変化を採用す
る。この作用の後に、モジュール１３は、解析がどのよ
うに継続されるべきかを、段階２４において、解析すべ
き次カルテットのバッファメモリ１５内の位置を識別す
ることと、段階２５〜２８において、この解析を継続す
るために用いるべきＴＲＩＥメモリの次レジスタを識別
することとにより判断する。
５に記憶されたヘッダの（ｉ＋１）番目のカルテットＶ
iにより示された、選択されたレジスタＲの基本セルＴ
［Ｒ，Ｖi］の内容Ｃが、段階２１において読み取られ
る。このセルのコマンドフィールドＣＴ（Ｃ）が００１
でなければ（テスト２２）、このコマンドフィールドの
内容は、段階２３において、制御装置１６へ適用され、
これにより、制御装置１６は、必要であれば、対応する
作用を続行するために必要とされる状態変化を採用す
る。この作用の後に、モジュール１３は、解析がどのよ
うに継続されるべきかを、段階２４において、解析すべ
き次カルテットのバッファメモリ１５内の位置を識別す
ることと、段階２５〜２８において、この解析を継続す
るために用いるべきＴＲＩＥメモリの次レジスタを識別
することとにより判断する。
【００４６】段階２４において、解析すべき次カルテッ
トのコードは、現在のカルテットｉのコードと、ＴＲＩ
Ｅメモリ内のセルのフィールドＦＭ，ＤＰにより、さら
に選択的に、制御装置１６により管理されるパラメータ
ＯＦＦＳＥＴにより表された位置コードとの関数として
計算される。上記に略述した従来技術によれば、ｆにつ
いては、以下のものとして表すことができる。 ｆ（ｉ，００，ＤＰ，ＯＦＦＳＥＴ）＝ｉ＋１； ｆ（ｉ，１１，ＤＰ，ＯＦＦＳＥＴ）＝ＤＰ； ｆ（ｉ，１０，ＤＰ，ＯＦＦＳＥＴ）＝ｉ＋ＤＰ（ＤＰ
は正または負）； ｆ（ｉ，０１，ＤＰ，ＯＦＦＳＥＴ）＝ＯＦＦＳＥＴ＋
ＤＰ（ＤＰは正または負）。
トのコードは、現在のカルテットｉのコードと、ＴＲＩ
Ｅメモリ内のセルのフィールドＦＭ，ＤＰにより、さら
に選択的に、制御装置１６により管理されるパラメータ
ＯＦＦＳＥＴにより表された位置コードとの関数として
計算される。上記に略述した従来技術によれば、ｆにつ
いては、以下のものとして表すことができる。 ｆ（ｉ，００，ＤＰ，ＯＦＦＳＥＴ）＝ｉ＋１； ｆ（ｉ，１１，ＤＰ，ＯＦＦＳＥＴ）＝ＤＰ； ｆ（ｉ，１０，ＤＰ，ＯＦＦＳＥＴ）＝ｉ＋ＤＰ（ＤＰ
は正または負）； ｆ（ｉ，０１，ＤＰ，ＯＦＦＳＥＴ）＝ＯＦＦＳＥＴ＋
ＤＰ（ＤＰは正または負）。
【００４７】段階２５において、前記モジュール１３
は、カウントが必要かどうかを判断するために、ＴＲＩ
Ｅメモリの現在セルのフィールドＣＰを検査する。カウ
ントが必要でなければ（ＣＰ＝００）、セルのフィール
ドＰtrから読み取られたポインタにより指定されたレジ
スタは、段階２６において、後続の反復のためのレジス
タＲであるとして選択される。段階２５において、ＣＰ
（Ｃ）≠００であれば、段階２７において、インクリメ
ントすべきカウンタのアドレスＡが、ＴＲＩＥメモリの
現在セルのフィールドＰtrの内容であるとして得られ
る。段階２８において、モジュール１３は、次に、この
カウンタＶ（Ａ）をインクリメントする命令を発行し、
かつ、後に続く反復のためのレジスタＲを選択するため
にポインタＰＴ（Ａ）を検索する。
は、カウントが必要かどうかを判断するために、ＴＲＩ
Ｅメモリの現在セルのフィールドＣＰを検査する。カウ
ントが必要でなければ（ＣＰ＝００）、セルのフィール
ドＰtrから読み取られたポインタにより指定されたレジ
スタは、段階２６において、後続の反復のためのレジス
タＲであるとして選択される。段階２５において、ＣＰ
（Ｃ）≠００であれば、段階２７において、インクリメ
ントすべきカウンタのアドレスＡが、ＴＲＩＥメモリの
現在セルのフィールドＰtrの内容であるとして得られ
る。段階２８において、モジュール１３は、次に、この
カウンタＶ（Ａ）をインクリメントする命令を発行し、
かつ、後に続く反復のためのレジスタＲを選択するため
にポインタＰＴ（Ａ）を検索する。
【００４８】この解析処理は、中間ステータスを供給し
ている幾つかの論理解析を結びつけることにより継続さ
れる。この解析処理は、現在のセルのコマンドフィール
ドＣＴ（Ｃ）において値００１が現れたときに終了する
（テスト２２）。この地点において、モジュール１３
は、段階２９において、セルのフィールドＴＴ，ＰＡに
備えられるパラメータを制御装置１６に供給し、さら
に、段階３０において、最終ステータスＰtr（Ｃ）を転
送モジュール１２へ供給する。
ている幾つかの論理解析を結びつけることにより継続さ
れる。この解析処理は、現在のセルのコマンドフィール
ドＣＴ（Ｃ）において値００１が現れたときに終了する
（テスト２２）。この地点において、モジュール１３
は、段階２９において、セルのフィールドＴＴ，ＰＡに
備えられるパラメータを制御装置１６に供給し、さら
に、段階３０において、最終ステータスＰtr（Ｃ）を転
送モジュール１２へ供給する。
【図１】 ＴＲＩＥメモリの内容の例を示す図である。
【図２】 ＴＲＩＥメモリを調べる手段として実行され
る従来の解析方法を示すフローチャートである。
る従来の解析方法を示すフローチャートである。
【図３】 本発明により提案されたパケットルータのブ
ロック図である。
ロック図である。
【図４】 パケットヘッダの一例の構成を示す図であ
る。
る。
【図５】 ルータのＴＲＩＥメモリ内のセルの構成を示
す図である。
す図である。
【図６】 ルータのＴＲＩＥメモリ内のセルの構成を示
す図である。
す図である。
【図７】 ＴＲＩＥメモリを調べるために本発明により
提案された解析手順を示すフローチャートである。
提案された解析手順を示すフローチャートである。
１０ ルータ １１ ホストコンピュータ １２ 転送モジュール １３ 解析モジュール １４ ＴＲＩＥメモリ １５ バッファメモリ １６ 制御装置
───────────────────────────────────────────────────── フロントページの続き (72)発明者 セルヴァン・ボンジュール フランス・92100・ブローニュ・ビランク ール・リュ・ドゥ・スィリー・56 (72)発明者 エルベ・ギュスドン フランス・92240・マラコフ・アヴニュ・ オーギュスタン・デュモン・１
Claims (8)
- 【請求項１】 ＴＲＩＥメモリ（１４）の異なるゲート
レジスタと、プロトコルデータを備える各々のパケット
のヘッダの異なる部分とから連続して解析することによ
り、前記ＴＲＩＥメモリ（１４）によって転送基準値を
データパケットに関連づける方法であって、 パケットが到着した際に、そのヘッダはバッファメモリ
（１５）に記憶され、かつ、前記記憶されたヘッダの第
１部分が解析され、 パケットのヘッダ部分の各々の解析は、前記パケットと
関連づけられた前記転送基準値、または、次の解析すべ
き部分を、前記バッファメモリの任意のロケーションに
おいて捜し当てることを可能にする第１コード（ＦＭ，
ＤＰ）と、前記次の部分が解析されるべき起点であるゲ
ートレジスタを、前記ＴＲＩＥメモリの任意のロケーシ
ョンにおいて捜し当てることを可能にする第２コード
（Ｐtr）とを有する中間基準値のいずれかを生成し、 記憶されたヘッダの前記第１部分を解析した後に、前記
後続の部分は、前記転送基準値が生成されるまで連続し
て生成された前記中間基準値に備えられる前記第１およ
び第２コードにしたがって解析されることを特徴とする
方法。 - 【請求項２】 前記ＴＲＩＥメモリ（１４）は基本セル
からなり、各々の基本セルは、該セルが転送基準値を備
えているかどうかを示すフィールド（ＣＴ）を有し、 転送基準値を備えていない各々の基本セルは、少なくと
も、前記解析が継続されるべき前記バッファメモリ（１
５）のロケーションを指定する情報の一片を備えるため
の第１フィールド（ＦＭ，ＤＰ）と、前記ＴＲＩＥメモ
リの連続解析レジスタを指定する情報の一片を備えるた
めの第２フィールド（Ｐtr）とを有することを特徴とす
る請求項１に記載の方法。 - 【請求項３】 前記解析が継続されるべき前記バッファ
メモリ（１５）のロケーションを指定する前記情報が、
前記バッファメモリの前記ロケーションの数値表示を示
すフォーマットコード（ＦＭ）と、前記表示にしたがっ
て、前記バッファメモリの前記ロケーションを指定する
アドレスコード（ＤＰ）とを有することを特徴とする請
求項２に記載の方法。 - 【請求項４】 前記フォーマットコード（ＦＭ）が、
（ｉ）前記記憶されたヘッダの前記データ要素が、これ
らのデータ要素が現れた順序で解析される順次的表示
と、（ii）解析すべき次のデータ要素が、記憶されたヘ
ッダのその絶対的地点により指定される絶対的表示と、
（iii）解析すべき次のデータ要素が、現在解析されて
いるデータ要素に対するその位置により指定される差分
的表示と、または、（iv）解析すべき次のデータ要素
が、前記記憶されたヘッダの所定の部分に対するその位
置により指定される相対的表示とを示すことを特徴とす
る請求項３に記載の方法。 - 【請求項５】 転送基準値を備えていない各々の基本セ
ルが、カウント工程が必要かどうかを示す情報の一片を
有する追加フィールド（ＣＣ）を有し、 転送基準値を備えておらずかつカウント工程が必要であ
る示す追加フィールド（ＣＣ）を有する各々の基本セル
が、その第２フィールド（Ｐtr）において、前記工程が
実行されかつ前記ＴＲＩＥメモリ（１４）の連続解析レ
ジスタへのポインタ（Ｒ）を有する他のメモリロケーシ
ョン（ＰＴ（Ａ））と関連づけられるときにインクリメ
ントすべきカウンタを有するメモリロケーション（Ｖ
（Ａ））へのポインタ（Ａ）を有することを特徴とする
請求項２から請求項４のいずれかに記載の方法。 - 【請求項６】 前記ＴＲＩＥメモリ（１４）の各々の基
本セルが、補助制御装置（１６）に向けられた命令を有
するコマンドフィールド（ＣＴ）を有していることを特
徴とする請求項１から請求項５のいずれかに記載の方
法。 - 【請求項７】 転送基準値が、前記バッファメモリ（１
５）に記憶された前記パケットの前記ヘッダの部分に適
用すべきあらゆる修正を特定するために、前記制御装置
（１６）に適用されるパラメータとともに前記ＴＲＩＥ
メモリ（１４）から発行されることを特徴とする請求項
６に記載の方法。 - 【請求項８】 請求項１から請求項７のいずれかに記載
の方法にしたがって動作する前記ＴＲＩＥメモリ（１
４）の連想メモリを用いて、受け取られたパケットのヘ
ッダを解析するための回路（１３）を有することを特徴
とするパケット処理装置（１０）。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR9901714A FR2789778B1 (fr) | 1999-02-12 | 1999-02-12 | Procede pour associer des references d'acheminement a des paquets de donnees au moyen d'une memoire trie, et routeur de paquets appliquant ce procede |
| FR9901714 | 1999-02-12 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2000244577A true JP2000244577A (ja) | 2000-09-08 |
Family
ID=9541953
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000034023A Pending JP2000244577A (ja) | 1999-02-12 | 2000-02-10 | Ｔｒｉｅメモリによって転送基準値をデータパケットと関連づける方法およびこの方法を用いたパケット処理装置 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US6704313B1 (ja) |
| EP (1) | EP1030493B1 (ja) |
| JP (1) | JP2000244577A (ja) |
| DE (1) | DE60040358D1 (ja) |
| FR (1) | FR2789778B1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005253077A (ja) * | 2004-03-02 | 2005-09-15 | Agilent Technol Inc | Ａｔｍデータをリアルタイムで再組立するシステム、方法、およびプログラム |
Families Citing this family (24)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE69830598T2 (de) * | 1997-01-31 | 2006-05-18 | The Horticulture And Food Research Institute Of New Zealand Limited | Optische vorrichtung und methode |
| US6071689A (en) | 1997-12-31 | 2000-06-06 | Xy, Inc. | System for improving yield of sexed embryos in mammals |
| US6149867A (en) | 1997-12-31 | 2000-11-21 | Xy, Inc. | Sheath fluids and collection systems for sex-specific cytometer sorting of sperm |
| US7208265B1 (en) | 1999-11-24 | 2007-04-24 | Xy, Inc. | Method of cryopreserving selected sperm cells |
| NZ545311A (en) * | 2000-05-09 | 2008-03-28 | Xy Inc | Flow cytometer for high purity X-chromosome bearing and Y-chromosome bearing populations of spermatozoa |
| EP1162789A1 (de) * | 2000-06-08 | 2001-12-12 | Siemens Aktiengesellschaft | Verfahren zur Verwaltung von Pfadinformationen und deren Änderungen in einem MPLS-Netzwerk |
| UY26761A1 (es) * | 2000-06-12 | 2001-07-31 | Univ Colorado State Res Found | Integración de destete precoz y uso de semen de sexo seleccionado en un sistema de vaquillona- ternero único para incrementar el valor de vaquillonas de no reemplazo. |
| US7149216B1 (en) * | 2000-09-05 | 2006-12-12 | Cisco Technology, Inc. | M-trie based packet processing |
| WO2002043486A1 (en) | 2000-11-29 | 2002-06-06 | Xy, Inc. | System for in-vitro fertilization with spermatozoa separated into x-chromosome and y-chromosome bearing populations |
| US7713687B2 (en) | 2000-11-29 | 2010-05-11 | Xy, Inc. | System to separate frozen-thawed spermatozoa into x-chromosome bearing and y-chromosome bearing populations |
| CN1175633C (zh) * | 2001-12-26 | 2004-11-10 | Lg电子株式会社 | 基于atm的mpls-ler系统和建立该系统的连接的方法 |
| FR2835991B1 (fr) | 2002-02-12 | 2004-04-23 | France Telecom | Procede de configuration d'une memoire trie pour le traitement de paquets de donnees, et dispositif de traitement de paquets mettant en oeuvre un tel procede |
| MX337304B (es) | 2002-08-01 | 2016-02-24 | Xy Llc | Sistema de separacion de baja presion para celulas de esperma. |
| US8486618B2 (en) | 2002-08-01 | 2013-07-16 | Xy, Llc | Heterogeneous inseminate system |
| WO2004017041A2 (en) | 2002-08-15 | 2004-02-26 | Xy, Inc. | High resolution flow cytometer |
| US7169548B2 (en) | 2002-09-13 | 2007-01-30 | Xy, Inc. | Sperm cell processing and preservation systems |
| CA3074799C (en) | 2003-03-28 | 2022-12-06 | Inguran, Llc | Apparatus, methods and processes for sorting particles and for providing sex-sorted animal sperm |
| DK1625203T3 (en) | 2003-05-15 | 2015-07-06 | Xy Llc | EFFECTIVE SEPARATION OF haploid cells FOR FLOWCYTOMETRISYSTEMER |
| EP1678632A1 (fr) * | 2003-10-28 | 2006-07-12 | France Telecom | Dispositif de memoire de type trie avec mecanisme de compression |
| PT2151243E (pt) | 2004-03-29 | 2013-01-25 | Inguran Llc | Suspensões de esperma para separação em populações enriquecidas carregando o cromossoma x ou y |
| JP2008507287A (ja) | 2004-07-22 | 2008-03-13 | モンサント テクノロジー エルエルシー | 精子細胞の集団を富化する方法 |
| US7618770B2 (en) * | 2005-07-29 | 2009-11-17 | Xy, Inc. | Methods and apparatus for reducing protein content in sperm cell extenders |
| EP2074767A2 (en) * | 2006-08-02 | 2009-07-01 | University Of Florida Research Foundation, Inc. | Succinct representation of static packet classifiers |
| CN101212414A (zh) * | 2006-12-29 | 2008-07-02 | 朗迅科技公司 | 在通信系统中路由数据分组的方法 |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1996000945A1 (en) * | 1994-06-30 | 1996-01-11 | International Business Machines Corp. | Variable length data sequence matching method and apparatus |
| JPH10222535A (ja) * | 1997-02-12 | 1998-08-21 | Nippon Telegr & Teleph Corp <Ntt> | データ検索回路 |
| JP2000502872A (ja) * | 1996-09-18 | 2000-03-07 | シーメンス アクチエンゲゼルシヤフト | 種々のパラメータを表す値のレコードに対するアドレス割り当て方法 |
| JP2002530011A (ja) * | 1998-11-06 | 2002-09-10 | マイクロソフト コーポレイション | 最適ルーティング・テーブル圧縮のためのルータ及び方法 |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| AU624205B2 (en) * | 1989-01-23 | 1992-06-04 | General Electric Capital Corporation | Variable length string matcher |
| FR2707775B1 (fr) * | 1993-07-12 | 1996-04-12 | Duret Chrsitian | Procédé et dispositif d'analyse d'informations contenues dans des structures de données. |
| US5509006A (en) * | 1994-04-18 | 1996-04-16 | Cisco Systems Incorporated | Apparatus and method for switching packets using tree memory |
| US6243667B1 (en) * | 1996-05-28 | 2001-06-05 | Cisco Systems, Inc. | Network flow switching and flow data export |
| US6493347B2 (en) * | 1996-12-16 | 2002-12-10 | Juniper Networks, Inc. | Memory organization in a switching device |
| US5938736A (en) * | 1997-06-30 | 1999-08-17 | Sun Microsystems, Inc. | Search engine architecture for a high performance multi-layer switch element |
| US6157641A (en) * | 1997-08-22 | 2000-12-05 | Cisco Technology, Inc. | Multiprotocol packet recognition and switching |
| US6041053A (en) * | 1997-09-18 | 2000-03-21 | Microsfot Corporation | Technique for efficiently classifying packets using a trie-indexed hierarchy forest that accommodates wildcards |
-
1999
- 1999-02-12 FR FR9901714A patent/FR2789778B1/fr not_active Expired - Fee Related
-
2000
- 2000-01-28 US US09/493,583 patent/US6704313B1/en not_active Expired - Lifetime
- 2000-02-09 EP EP00400366A patent/EP1030493B1/fr not_active Expired - Lifetime
- 2000-02-09 DE DE60040358T patent/DE60040358D1/de not_active Expired - Lifetime
- 2000-02-10 JP JP2000034023A patent/JP2000244577A/ja active Pending
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1996000945A1 (en) * | 1994-06-30 | 1996-01-11 | International Business Machines Corp. | Variable length data sequence matching method and apparatus |
| JP2000502872A (ja) * | 1996-09-18 | 2000-03-07 | シーメンス アクチエンゲゼルシヤフト | 種々のパラメータを表す値のレコードに対するアドレス割り当て方法 |
| JPH10222535A (ja) * | 1997-02-12 | 1998-08-21 | Nippon Telegr & Teleph Corp <Ntt> | データ検索回路 |
| JP2002530011A (ja) * | 1998-11-06 | 2002-09-10 | マイクロソフト コーポレイション | 最適ルーティング・テーブル圧縮のためのルータ及び方法 |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005253077A (ja) * | 2004-03-02 | 2005-09-15 | Agilent Technol Inc | Ａｔｍデータをリアルタイムで再組立するシステム、方法、およびプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| DE60040358D1 (de) | 2008-11-13 |
| US6704313B1 (en) | 2004-03-09 |
| EP1030493A1 (fr) | 2000-08-23 |
| FR2789778A1 (fr) | 2000-08-18 |
| EP1030493B1 (fr) | 2008-10-01 |
| FR2789778B1 (fr) | 2001-09-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2000244577A (ja) | Ｔｒｉｅメモリによって転送基準値をデータパケットと関連づける方法およびこの方法を用いたパケット処理装置 | |
| US7835375B2 (en) | Method and apparatus for providing multi-protocol, multi-stage, real-time frame classification | |
| US6658458B1 (en) | Cascading associative memory arrangement | |
| EP1224773B1 (en) | Apparatus and method for identifying data packet types in real time on a network switch port | |
| US6798788B1 (en) | Arrangement determining policies for layer 3 frame fragments in a network switch | |
| US7289517B1 (en) | Node device | |
| US6661791B1 (en) | Method and apparatus for generating forward overrides in a packet switch | |
| US6044079A (en) | Statistical packet discard | |
| US12058231B2 (en) | Hybrid fixed/programmable header parser for network devices | |
| US6976154B1 (en) | Pipelined processor for examining packet header information | |
| US20010012295A1 (en) | Enhanced internet packet routing lookup | |
| US6480468B1 (en) | Repeater | |
| US6801545B2 (en) | Container transport for packets in connection oriented protocols | |
| US6658003B1 (en) | Network relaying apparatus and network relaying method capable of high-speed flow detection | |
| US6807183B1 (en) | Arrangement for reading a prescribed location of a FIFO buffer in a network switch port | |
| HUP0203823A2 (en) | Method and system for frame and protocol classification | |
| WO2007133316A2 (en) | Packet firewalls of particular use in packet switching devices | |
| US7403526B1 (en) | Partitioning and filtering a search space of particular use for determining a longest prefix match thereon | |
| KR100755979B1 (ko) | 네트워크 스위치 포트상에서 와이어 속도로 데이터 패킷을식별하는 장치 및 방법 | |
| CN100512205C (zh) | 虚拟输出队列(VoQ)管理方法和装置 | |
| US20020073222A1 (en) | Packet transfer control method | |
| US20020181463A1 (en) | System and method for handling asynchronous transfer mode cells | |
| KR100310303B1 (ko) | 멀티프로토콜 레이블 스위칭 망의 에지 라우터에서의 고속인터넷프로토콜 헤더의 룩업 제어장치 | |
| US6728255B1 (en) | Apparatus and method for storing min terms in a network switch port memory for identifying data packet types in a real time | |
| US7042886B2 (en) | Apparatus, method, and computer program for wire-speed classification and pre-processing of data packets in an ATM network |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20070131 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20090930 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20091013 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20100907 |