JPH10257084A - コンピュータ・ネットワーク内でデータ・フレームを経路指定するフレーム・ヘッダを解析する方法およびシステム - Google Patents
コンピュータ・ネットワーク内でデータ・フレームを経路指定するフレーム・ヘッダを解析する方法およびシステムInfo
- Publication number
- JPH10257084A JPH10257084A JP10001502A JP150298A JPH10257084A JP H10257084 A JPH10257084 A JP H10257084A JP 10001502 A JP10001502 A JP 10001502A JP 150298 A JP150298 A JP 150298A JP H10257084 A JPH10257084 A JP H10257084A
- Authority
- JP
- Japan
- Prior art keywords
- test
- frame
- search
- computer network
- data
- 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
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/74—Address processing for routing
- H04L45/745—Address table lookup; Address filtering
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
- H04L69/22—Parsing or analysis of headers
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Computer Security & Cryptography (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Small-Scale Networks (AREA)
- Computer And Data Communications (AREA)
Abstract
(57)【要約】
【課題】 コンピュータ・ネットワーク内でデータ・フ
レームを経路指定するフレーム・ヘッダを解析する方法
およびシステムを提供すること。 【解決手段】 本発明の方法およびシステムによれば、
まず、コンピュータ・ネットワークからデータ・フレー
ムを受信する。次いで、データ・フレームのフレーム・
ヘッダを同じ長さの複数のテスト・ユニットに分解す
る。その後、各テスト・ユニットにそれぞれリファレン
ス・パターン・フィールドおよびアクション・コード・
ポインタ・フィールドを含む各テスト・ベクトルを割り
当てる。各テスト・ベクトルを様々なテスト・ブロック
の対応するスロットに挿入することによって多数のテス
ト・ブロックを構成する。最後に、これらの様々なテス
ト・ブロックを使用して、探索ツリーを構成する。各テ
スト・ブロックは、その中に含まれるテスト・ベクトル
によって互いに関連づけられる。
レームを経路指定するフレーム・ヘッダを解析する方法
およびシステムを提供すること。 【解決手段】 本発明の方法およびシステムによれば、
まず、コンピュータ・ネットワークからデータ・フレー
ムを受信する。次いで、データ・フレームのフレーム・
ヘッダを同じ長さの複数のテスト・ユニットに分解す
る。その後、各テスト・ユニットにそれぞれリファレン
ス・パターン・フィールドおよびアクション・コード・
ポインタ・フィールドを含む各テスト・ベクトルを割り
当てる。各テスト・ベクトルを様々なテスト・ブロック
の対応するスロットに挿入することによって多数のテス
ト・ブロックを構成する。最後に、これらの様々なテス
ト・ブロックを使用して、探索ツリーを構成する。各テ
スト・ブロックは、その中に含まれるテスト・ベクトル
によって互いに関連づけられる。
Description
【０００１】本発明は、本出願人に譲渡された１９９４
年９月１５日出願の米国特許出願第０８／３０６７８３
号（特開平８−９７８４４号公報）に関連している。
年９月１５日出願の米国特許出願第０８／３０６７８３
号（特開平８−９７８４４号公報）に関連している。
【０００２】
【発明の属する技術分野】本発明は、一般にデータ処理
の方法およびシステムに関し、特にフレーム・ヘッダを
解析する方法およびシステムに関する。さらに詳細に
は、本発明は、コンピュータ・ネットワーク内でデータ
・フレームを経路指定するフレーム・ヘッダを解析する
方法およびシステムに関する。
の方法およびシステムに関し、特にフレーム・ヘッダを
解析する方法およびシステムに関する。さらに詳細に
は、本発明は、コンピュータ・ネットワーク内でデータ
・フレームを経路指定するフレーム・ヘッダを解析する
方法およびシステムに関する。
【０００３】
【従来の技術】コンピュータ・ネットワークは、情報を
電子的に伝送する経路をコンピュータ・ユーザに提供す
るための通信機構によって接続されたコンピュータのグ
ループである。コンピュータ・ネットワークは、狭い領
域内の少数のコンピュータのみから構成されるローカル
エリア・ネットワーク（ＬＡＮ）か、または広大な地理
的領域中に分散された多数のコンピュータから構成され
る広域ネットワーク（ＷＡＮ）である。
電子的に伝送する経路をコンピュータ・ユーザに提供す
るための通信機構によって接続されたコンピュータのグ
ループである。コンピュータ・ネットワークは、狭い領
域内の少数のコンピュータのみから構成されるローカル
エリア・ネットワーク（ＬＡＮ）か、または広大な地理
的領域中に分散された多数のコンピュータから構成され
る広域ネットワーク（ＷＡＮ）である。
【０００４】ルータ（またはブリッジ）は、コンピュー
タ・ネットワーク内のメッセージ配送を容易にする中継
装置である。ＬＡＮ内では、ルータは、メッセージを受
信し、それらを最も効率的に使用できるルートを介して
それらの正しい宛先に転送する。相互接続された複数の
ＬＡＮの組を有するＷＡＮ内では、ルータは、これらの
複数組のＬＡＮの間のリンクとして働き、１組のＬＡＮ
から別の１組のＬＡＮへメッセージを送信できるように
するので幾分異なる役目を果たす。
タ・ネットワーク内のメッセージ配送を容易にする中継
装置である。ＬＡＮ内では、ルータは、メッセージを受
信し、それらを最も効率的に使用できるルートを介して
それらの正しい宛先に転送する。相互接続された複数の
ＬＡＮの組を有するＷＡＮ内では、ルータは、これらの
複数組のＬＡＮの間のリンクとして働き、１組のＬＡＮ
から別の１組のＬＡＮへメッセージを送信できるように
するので幾分異なる役目を果たす。
【０００５】ネットワーク・コンピュータ内の様々なコ
ンピュータは、そのポート（すなわち、データ処理装置
との間でデータを出し入れする場所）を介してルータに
結合される。ルータは、コンピュータ・ネットワーク内
のあるコンピュータから他のコンピュータに向けられた
データ・フレームを受信したとき、データ・フレーム内
に与えられた宛先アドレス（受信側コンピュータのアド
レス）を記憶されたアドレス／ポート・リストと比較す
る。このアドレス／ポート・リストは、ルータ内のどの
ポートが受信側コンピュータに関連するかを示す。次い
で、ルータは、データ・フレームを受信側コンピュータ
に結合された適切なポートに向ける。
ンピュータは、そのポート（すなわち、データ処理装置
との間でデータを出し入れする場所）を介してルータに
結合される。ルータは、コンピュータ・ネットワーク内
のあるコンピュータから他のコンピュータに向けられた
データ・フレームを受信したとき、データ・フレーム内
に与えられた宛先アドレス（受信側コンピュータのアド
レス）を記憶されたアドレス／ポート・リストと比較す
る。このアドレス／ポート・リストは、ルータ内のどの
ポートが受信側コンピュータに関連するかを示す。次い
で、ルータは、データ・フレームを受信側コンピュータ
に結合された適切なポートに向ける。
【０００６】従来技術では、アドレス／ポート・リスト
は予めルータに備えられているか、またはルータがアド
レス／ポート・リストを動的に形成する。そのようなア
ドレス／ポート・リストは、ルータ内に記憶され、デー
タ・フレームを受信したときにアクセスされる。次い
で、ルータは、データ・フレームの宛先アドレスを一致
が得られるまでアドレス／ポート・リスト内の各項目と
比較する。一般に、アドレス／ポート・リストの各新し
い探索は、アドレス／ポート・リストの「上部」から始
まり、一致が見つかるまで宛先アドレスを連続的に探索
する。アドレス／ポート・リスト内に非常に多数の宛先
アドレスがある場合、コンピュータ・ネットワーク内の
通信は、ルータにおけるこのネックのためにかなり速度
が落ちる。
は予めルータに備えられているか、またはルータがアド
レス／ポート・リストを動的に形成する。そのようなア
ドレス／ポート・リストは、ルータ内に記憶され、デー
タ・フレームを受信したときにアクセスされる。次い
で、ルータは、データ・フレームの宛先アドレスを一致
が得られるまでアドレス／ポート・リスト内の各項目と
比較する。一般に、アドレス／ポート・リストの各新し
い探索は、アドレス／ポート・リストの「上部」から始
まり、一致が見つかるまで宛先アドレスを連続的に探索
する。アドレス／ポート・リスト内に非常に多数の宛先
アドレスがある場合、コンピュータ・ネットワーク内の
通信は、ルータにおけるこのネックのためにかなり速度
が落ちる。
【０００７】
【発明が解決しようとする課題】したがって、データ・
フレームがコンピュータ・ネットワーク内でより効率的
な形で経路指定されるようにフレーム・ヘッダを解析す
る改善された方法を提供することが望ましい。
フレームがコンピュータ・ネットワーク内でより効率的
な形で経路指定されるようにフレーム・ヘッダを解析す
る改善された方法を提供することが望ましい。
【０００８】したがって、上記のことから、本発明の目
的は、データ処理の改善された方法およびシステムを提
供することである。
的は、データ処理の改善された方法およびシステムを提
供することである。
【０００９】本発明の他の目的は、データ・パケットを
経路指定する改善された方法およびシステムを提供する
ことである。
経路指定する改善された方法およびシステムを提供する
ことである。
【００１０】本発明の他の目的は、コンピュータ・ネッ
トワーク内でデータ・フレームを経路指定するフレーム
・ヘッダを解析する方法およびシステムを提供すること
である。
トワーク内でデータ・フレームを経路指定するフレーム
・ヘッダを解析する方法およびシステムを提供すること
である。
【００１１】
【課題を解決するための手段】本発明の方法およびシス
テムによれば、まず、コンピュータ・ネットワークから
データ・フレームを受信する。次いで、データ・フレー
ムのフレーム・ヘッダを同じ長さの複数のテスト・ユニ
ットに分解する。その後、各テスト・ユニットにそれぞ
れリファレンス・パターン・フィールドおよびアクショ
ン・コード・ポインタ・フィールドを含むテスト・ベク
トルを割り当てる。各テスト・ベクトルを様々なテスト
・ブロックの対応するスロットに挿入することによって
多数のテスト・ブロックを構成する。最後に、これらの
様々なテスト・ブロックを使用して、探索ツリーを構成
する。各テスト・ブロックは、その中に含まれるテスト
・ベクトルによって互いに関連づけられる。
テムによれば、まず、コンピュータ・ネットワークから
データ・フレームを受信する。次いで、データ・フレー
ムのフレーム・ヘッダを同じ長さの複数のテスト・ユニ
ットに分解する。その後、各テスト・ユニットにそれぞ
れリファレンス・パターン・フィールドおよびアクショ
ン・コード・ポインタ・フィールドを含むテスト・ベク
トルを割り当てる。各テスト・ベクトルを様々なテスト
・ブロックの対応するスロットに挿入することによって
多数のテスト・ブロックを構成する。最後に、これらの
様々なテスト・ブロックを使用して、探索ツリーを構成
する。各テスト・ブロックは、その中に含まれるテスト
・ベクトルによって互いに関連づけられる。
【００１２】本発明のすべての目的、特徴および利点
は、以下の詳細に書かれた説明から明らかになろう。
は、以下の詳細に書かれた説明から明らかになろう。
【００１３】
【発明の実施の形態】本発明は、コンピュータ・ネット
ワーク内で外部通信用のデータ・パケットを使用する様
々なコンピュータ内で実施することができる。そのよう
なコンピュータは、例えばパーソナル・コンピュータ、
ミニコンピュータ、またはメインフレーム・コンピュー
タである。コンピュータ・ネットワークは、例えばロー
カルエリア・ネットワーク（ＬＡＮ）または広域ネット
ワーク（ＷＡＮ）である。
ワーク内で外部通信用のデータ・パケットを使用する様
々なコンピュータ内で実施することができる。そのよう
なコンピュータは、例えばパーソナル・コンピュータ、
ミニコンピュータ、またはメインフレーム・コンピュー
タである。コンピュータ・ネットワークは、例えばロー
カルエリア・ネットワーク（ＬＡＮ）または広域ネット
ワーク（ＷＡＮ）である。
【００１４】以下の説明では、本発明を完全に理解でき
るように、ワード長、バイト長など、多数の特定の詳細
を示してある。しかしながら、本発明は、そのような特
定の詳細なしに実施できることが当業者には明らかであ
ろう。さらに、周知の回路は、本発明が不必要な詳細に
よって曖昧にならないようにブロック図の形で示してあ
る。さらに、タイミング考慮事項などの詳細は、そのよ
うな詳細が当技術分野において通常の技能を有する者の
技量の範囲内に入り、かつ本発明を完全に理解するため
に必要でない限り省略してある。
るように、ワード長、バイト長など、多数の特定の詳細
を示してある。しかしながら、本発明は、そのような特
定の詳細なしに実施できることが当業者には明らかであ
ろう。さらに、周知の回路は、本発明が不必要な詳細に
よって曖昧にならないようにブロック図の形で示してあ
る。さらに、タイミング考慮事項などの詳細は、そのよ
うな詳細が当技術分野において通常の技能を有する者の
技量の範囲内に入り、かつ本発明を完全に理解するため
に必要でない限り省略してある。
【００１５】次に、図１を参照すると、本発明が使用さ
れる代表的なコンピュータ・ネットワーク１００のブロ
ック図が示されている。図示のように、ＬＡＮ１０、Ｌ
ＡＮ１１、およびＬＡＮ１２は、ルータ１０２を介して
サーバ１０１に相互接続される。ＬＡＮ１０はノード１
１１〜１１３を含み、ＬＡＮ１１はノード１１４〜１１
６を含み、ＬＡＮ１２はノード１１７〜１２０を含む。
ＬＡＮ内の各ノードがコンピュータ・ネットワーク１０
０内で互いに通信しようとするとき、ルータ１０２は、
通信データを、パケットの形で、対応するＬＡＮの適切
な宛先ノードに効率的に向けることによってそのような
通信を容易にする。例えば、ＬＡＮ１１のノード１１４
がデータ・フレームをＬＡＮ１２のノード１２０に送る
ことを望む場合、ノード１１４は、そのようなデータ・
フレームをノード１２０に関連する宛先アドレスととも
にルータ１０２に送信し、次いでルータ１０２は、ノー
ド１１４からデータ・フレームとともに受信した宛先ア
ドレスをそのメモリ内のアドレス／ポートのリストと比
較し、その後宛先アドレスとそのメモリ内に記載されて
いるアドレス／ポート対の１つとの一致が得られたとき
にデータ・フレームをノード１２０に送る。
れる代表的なコンピュータ・ネットワーク１００のブロ
ック図が示されている。図示のように、ＬＡＮ１０、Ｌ
ＡＮ１１、およびＬＡＮ１２は、ルータ１０２を介して
サーバ１０１に相互接続される。ＬＡＮ１０はノード１
１１〜１１３を含み、ＬＡＮ１１はノード１１４〜１１
６を含み、ＬＡＮ１２はノード１１７〜１２０を含む。
ＬＡＮ内の各ノードがコンピュータ・ネットワーク１０
０内で互いに通信しようとするとき、ルータ１０２は、
通信データを、パケットの形で、対応するＬＡＮの適切
な宛先ノードに効率的に向けることによってそのような
通信を容易にする。例えば、ＬＡＮ１１のノード１１４
がデータ・フレームをＬＡＮ１２のノード１２０に送る
ことを望む場合、ノード１１４は、そのようなデータ・
フレームをノード１２０に関連する宛先アドレスととも
にルータ１０２に送信し、次いでルータ１０２は、ノー
ド１１４からデータ・フレームとともに受信した宛先ア
ドレスをそのメモリ内のアドレス／ポートのリストと比
較し、その後宛先アドレスとそのメモリ内に記載されて
いるアドレス／ポート対の１つとの一致が得られたとき
にデータ・フレームをノード１２０に送る。
【００１６】次に、図２を参照すると、図１のコンピュ
ータ・ネットワーク内でデータ・フレームを経路指定す
る従来技術の方法のハイレベル論理流れ図が示されてい
る。ステップ２１で、ルータは、コンピュータ・ネット
ワーク内の様々なノードの１つから１つまたは複数のデ
ータ・フレームを受信する。次に、ステップ２２で、ル
ータは、１つまたは複数のデータ・フレームとともに送
信された宛先アドレスを、ルータによって形成され、ル
ータ内に記憶されたアドレス／ポート・リスト内のすべ
てのアドレスと比較する。ステップ２３で、ルータは、
宛先アドレスがアドレス／ポート・リスト内にあるポー
トのうち、当該宛先アドレスを受信したポートと同じポ
ートに関連しているか否かを決定する。関連している場
合、データ・フレームは、データ・フレームを送信した
のと同じノードに向けられるので、それらを経路指定す
る理由はない。したがって、ステップ２４で、ルータ
は、受信したデータ・フレームを廃棄する。
ータ・ネットワーク内でデータ・フレームを経路指定す
る従来技術の方法のハイレベル論理流れ図が示されてい
る。ステップ２１で、ルータは、コンピュータ・ネット
ワーク内の様々なノードの１つから１つまたは複数のデ
ータ・フレームを受信する。次に、ステップ２２で、ル
ータは、１つまたは複数のデータ・フレームとともに送
信された宛先アドレスを、ルータによって形成され、ル
ータ内に記憶されたアドレス／ポート・リスト内のすべ
てのアドレスと比較する。ステップ２３で、ルータは、
宛先アドレスがアドレス／ポート・リスト内にあるポー
トのうち、当該宛先アドレスを受信したポートと同じポ
ートに関連しているか否かを決定する。関連している場
合、データ・フレームは、データ・フレームを送信した
のと同じノードに向けられるので、それらを経路指定す
る理由はない。したがって、ステップ２４で、ルータ
は、受信したデータ・フレームを廃棄する。
【００１７】しかし、宛先アドレスがそれを受信した同
じポートに関連していない場合、ステップ２５で、ルー
タは、宛先アドレスがアドレス／ポート・リスト内の他
のポートに関連しているか否かを決定する。関連してい
る場合、ステップ２６で、ルータは、受信したデータ・
フレームを対応するポートに転送する。宛先アドレスが
他のポートに関連していない場合、ルータは、ステップ
２７に示すように、受信したデータ・フレームをすべて
のポートに同報通信する。
じポートに関連していない場合、ステップ２５で、ルー
タは、宛先アドレスがアドレス／ポート・リスト内の他
のポートに関連しているか否かを決定する。関連してい
る場合、ステップ２６で、ルータは、受信したデータ・
フレームを対応するポートに転送する。宛先アドレスが
他のポートに関連していない場合、ルータは、ステップ
２７に示すように、受信したデータ・フレームをすべて
のポートに同報通信する。
【００１８】上述のように、アドレス／ポート・リスト
は、従来、対応するルータ・ポートに関連するアドレス
の順次リストとして生成されていた。そのような従来の
アドレス／ポート・リストでは、ルータがステップ２３
および２５を実施する場合、一致が見つかるまで受信し
た宛先アドレスをアドレス／ポート・リスト内のすべて
のアドレスと比較していた。コンピュータ・ネットワー
ク内のノードの数が非常に多い場合、そのような探索は
相当な時間を必要とする。アドレス／ポート・リスト内
の最後の項目で初めて一致が見つかった場合、または一
致が見つからない場合、受信したデータ・フレームが同
報通信されるこの探索方法に関連する最悪の場合が生じ
る。
は、従来、対応するルータ・ポートに関連するアドレス
の順次リストとして生成されていた。そのような従来の
アドレス／ポート・リストでは、ルータがステップ２３
および２５を実施する場合、一致が見つかるまで受信し
た宛先アドレスをアドレス／ポート・リスト内のすべて
のアドレスと比較していた。コンピュータ・ネットワー
ク内のノードの数が非常に多い場合、そのような探索は
相当な時間を必要とする。アドレス／ポート・リスト内
の最後の項目で初めて一致が見つかった場合、または一
致が見つからない場合、受信したデータ・フレームが同
報通信されるこの探索方法に関連する最悪の場合が生じ
る。
【００１９】本発明は、アドレス／ポートを１つまたは
複数の探索ツリー内に記憶するより効率的なアドレス探
索技法を提供する。これらの探索ツリーは、受信アドレ
スを分割することから生じた複数のビット・グループを
用いて作成される。したがって、探索は、（着信データ
・フレームのフレーム・ヘッダからの）受信アドレスを
ビット・グループに分割し、これらのビット・グループ
を探索ツリーの様々なノードと連続的に比較することに
よって実施される。探索プロセス中、受信アドレスと探
索ツリーのエントリとの正確な一致を得ることなしに探
索ツリー内のリーフに到達する場合がある。そのような
場合、受信アドレスがソース・アドレスである場合、ソ
ース・アドレスからのビットを使用して、探索ツリーを
延長する。このプロセスは「学習」または「エントリ更
新」と呼ばれる。しかし、受信アドレスが宛先アドレス
である場合、宛先アドレスに対して探索ツリー内に正確
な一致が生じないことが決定され、宛先アドレスに関連
するデータ・フレームの同報通信が実施される。
複数の探索ツリー内に記憶するより効率的なアドレス探
索技法を提供する。これらの探索ツリーは、受信アドレ
スを分割することから生じた複数のビット・グループを
用いて作成される。したがって、探索は、（着信データ
・フレームのフレーム・ヘッダからの）受信アドレスを
ビット・グループに分割し、これらのビット・グループ
を探索ツリーの様々なノードと連続的に比較することに
よって実施される。探索プロセス中、受信アドレスと探
索ツリーのエントリとの正確な一致を得ることなしに探
索ツリー内のリーフに到達する場合がある。そのような
場合、受信アドレスがソース・アドレスである場合、ソ
ース・アドレスからのビットを使用して、探索ツリーを
延長する。このプロセスは「学習」または「エントリ更
新」と呼ばれる。しかし、受信アドレスが宛先アドレス
である場合、宛先アドレスに対して探索ツリー内に正確
な一致が生じないことが決定され、宛先アドレスに関連
するデータ・フレームの同報通信が実施される。
【００２０】本発明の好ましい実施形態として、リファ
レンス・パターン（ＲＰ）は、学習すべきビットのパタ
ーン（ＲＰプールに追加する場合）、または削除すべき
ビットのパターン（ＲＰプールから削除する場合）であ
る。ＲＰビットは、多数のテスト・ユニット（ＴＵ）に
分割される。各ＴＵ内に含まれるビットの数は、探索ツ
リーの好ましい分解能に応じて事前定義される。各ＴＵ
は、ＲＰ内のその関連位置に従って番号付けされる。テ
スト・ブロック（ＴＢ）は、探索パス情報を保持するた
めに使用されるユニットである。各ＴＢは、一組のテス
ト・ベクトル（ＴＶ）を保持し、ＴＢ内に含まれるＴＶ
の数は、使用されるＴＵのサイズによって決定される。
ＴＶは、次のＴＢへのポインタ、次の探索ステップに使
用すべきＴＵ番号、探索の継続のために一致すべきＲ
Ｐ、フラグおよびここまで一致すべきマスクＲＰのアク
ション・コード・ポインタなど、パターン探索に必要な
情報を保持する。パターン探索中、特定のＴＵのＲＰビ
ットは、探索を継続するためにＴＢ内のどのＴＶを使用
するかを決定する。
レンス・パターン（ＲＰ）は、学習すべきビットのパタ
ーン（ＲＰプールに追加する場合）、または削除すべき
ビットのパターン（ＲＰプールから削除する場合）であ
る。ＲＰビットは、多数のテスト・ユニット（ＴＵ）に
分割される。各ＴＵ内に含まれるビットの数は、探索ツ
リーの好ましい分解能に応じて事前定義される。各ＴＵ
は、ＲＰ内のその関連位置に従って番号付けされる。テ
スト・ブロック（ＴＢ）は、探索パス情報を保持するた
めに使用されるユニットである。各ＴＢは、一組のテス
ト・ベクトル（ＴＶ）を保持し、ＴＢ内に含まれるＴＶ
の数は、使用されるＴＵのサイズによって決定される。
ＴＶは、次のＴＢへのポインタ、次の探索ステップに使
用すべきＴＵ番号、探索の継続のために一致すべきＲ
Ｐ、フラグおよびここまで一致すべきマスクＲＰのアク
ション・コード・ポインタなど、パターン探索に必要な
情報を保持する。パターン探索中、特定のＴＵのＲＰビ
ットは、探索を継続するためにＴＢ内のどのＴＶを使用
するかを決定する。
【００２１】マスクＩＰアドレスとして、ＲＰは、宛先
アドレスのサイズまでの任意の長さでよい。例えば、宛
先アドレスが長さ４バイト（３２ビット）である場合、
ＲＰは、長さ３２ビットまでの任意のビット数でよい。
さらに、ＲＰ当たりのＴＵの数は、事前定義したＴＵサ
イズに依存する。したがって、長さ３２ビットのＲＰの
場合、事前定義したＴＵが長さ１ビットである場合、Ｒ
Ｐは、３２個のＴＵに分割される。しかし、事前定義し
たＴＵが長さ２ビットである場合、ＲＰは、１６個のＴ
Ｕに分割されるだけである。この例を続けると、１ビッ
トＴＵを使用した場合、ＴＢ内のＴＶの数はわずか２つ
である。一方、２ビットＴＵを使用した場合、ＴＢ内の
ＴＶの数は４つである。本発明を説明するためには、２
ビットＴＵを選択することが好ましく、したがって開示
の残部ではＴＢ当たりのＴＶの数は４つである。
アドレスのサイズまでの任意の長さでよい。例えば、宛
先アドレスが長さ４バイト（３２ビット）である場合、
ＲＰは、長さ３２ビットまでの任意のビット数でよい。
さらに、ＲＰ当たりのＴＵの数は、事前定義したＴＵサ
イズに依存する。したがって、長さ３２ビットのＲＰの
場合、事前定義したＴＵが長さ１ビットである場合、Ｒ
Ｐは、３２個のＴＵに分割される。しかし、事前定義し
たＴＵが長さ２ビットである場合、ＲＰは、１６個のＴ
Ｕに分割されるだけである。この例を続けると、１ビッ
トＴＵを使用した場合、ＴＢ内のＴＶの数はわずか２つ
である。一方、２ビットＴＵを使用した場合、ＴＢ内の
ＴＶの数は４つである。本発明を説明するためには、２
ビットＴＵを選択することが好ましく、したがって開示
の残部ではＴＢ当たりのＴＶの数は４つである。
【００２２】テスト・ベクトルの説明 次に、図３を参照すると、本発明の好ましい実施形態に
よる２つのテスト・ベクトルのブロック図が示されてい
る。テスト・ベクトル３８は１ビットＴＵとともに使用
され、テスト・ベクトル３９は２ビットＴＵとともに使
用される。図示のように、探索ツリー内で使用される両
方のテスト・ベクトル３８、３９は、同じフィールドを
有する。マスク・リファレンス・パターン・マーカ
（Ｍ）フィールド３１を使用して、このテスト位置のと
ころに一致したＲＰが存在するかどうかを決定する。学
習プロセス中、ＲＰがこのテスト・ユニットのところで
終了するときはいつでもＭフィールド３１がセットされ
る。マークされたフラグごとに、一致したＲＰのアクシ
ョン記述子の位置を示す対応するアクション・コード・
ポインタが「Ｍｘ ＡＣ ＰＴＲ」フィールド内に存在
する。パターン探索（パターン一致プロセス）中、Ｍフ
ラグが検出されたときはいつでも、テスト・ベクトルの
アドレスおよびそのＭフラグが保管される。パターン探
索の終了時に、これらの保管したアドレスおよびフラグ
を使用して、それらの対応するアクション・コード・ポ
インタをフレーム修正プロセスおよび再送信プロセスの
ために後戻りさせる。Ｍフィールド３１内のビットの数
は、選択したＴＵサイズに等しい。上述のように、テス
ト・ベクトルの２つの可能なフォーマット、１ビットＴ
Ｕ構成用のテスト・ベクトル３８内の１ビットＭフィー
ルド、および２ビットＴＵ構成用のテスト・ベクトル３
９内の２ビットＭフィールド（一方のＭビットは奇数ビ
ット境界ＲＰを識別し、他方のＭビットは偶数ビット境
界ＲＰを識別する）が示されている。
よる２つのテスト・ベクトルのブロック図が示されてい
る。テスト・ベクトル３８は１ビットＴＵとともに使用
され、テスト・ベクトル３９は２ビットＴＵとともに使
用される。図示のように、探索ツリー内で使用される両
方のテスト・ベクトル３８、３９は、同じフィールドを
有する。マスク・リファレンス・パターン・マーカ
（Ｍ）フィールド３１を使用して、このテスト位置のと
ころに一致したＲＰが存在するかどうかを決定する。学
習プロセス中、ＲＰがこのテスト・ユニットのところで
終了するときはいつでもＭフィールド３１がセットされ
る。マークされたフラグごとに、一致したＲＰのアクシ
ョン記述子の位置を示す対応するアクション・コード・
ポインタが「Ｍｘ ＡＣ ＰＴＲ」フィールド内に存在
する。パターン探索（パターン一致プロセス）中、Ｍフ
ラグが検出されたときはいつでも、テスト・ベクトルの
アドレスおよびそのＭフラグが保管される。パターン探
索の終了時に、これらの保管したアドレスおよびフラグ
を使用して、それらの対応するアクション・コード・ポ
インタをフレーム修正プロセスおよび再送信プロセスの
ために後戻りさせる。Ｍフィールド３１内のビットの数
は、選択したＴＵサイズに等しい。上述のように、テス
ト・ベクトルの２つの可能なフォーマット、１ビットＴ
Ｕ構成用のテスト・ベクトル３８内の１ビットＭフィー
ルド、および２ビットＴＵ構成用のテスト・ベクトル３
９内の２ビットＭフィールド（一方のＭビットは奇数ビ
ット境界ＲＰを識別し、他方のＭビットは偶数ビット境
界ＲＰを識別する）が示されている。
【００２３】最終テスト・ベクトル（Ｌ）フィールド３
２を使用して、探索ツリーが終了する場所（すなわち、
探索パスの最後のテスト・ベクトル）を識別する。Ｌフ
ィールド３２内のビットの数も選択したＴＵサイズに等
しい。１ビットＴＵ構成では、ただ１つのビットがＬフ
ィールド３２内に必要である。２ビットＴＵ構成では、
２つのビットがＬフィールド３２内に必要である（この
場合も、一方のＬビットは奇数ビット境界ＲＰを識別
し、他方のＬビットは偶数ビット境界ＲＰを識別す
る）。学習プロセス中、ＲＰがこのテスト・ブロックの
ところで終了する場合、Ｍフラグを使用して、ＲＰをマ
ークする（ＲＰの最後のＴＵ＝ＣＴＵ＃、ただし、ＣＴ
Ｕ＃は、ＴＢ内のＴＶを見つけ出すデコードとして使用
される現在のＴＵである）。それ以外の場合、（ＲＰが
ＣＴＵ＃よりも長ければ）ＬフラグおよびＮＴＵ＃を使
用して、ＲＰをマークし、探索ツリーを終了する。実施
を簡単にするために、ただ１つのＬフラグを所与のＴＶ
内にセットすることができる。ＴＢ内で複数のＲＰをＬ
フラグでマークすることができる場合、探索ツリーを延
長し、Ｍフラグを使用して、いくつかのＲＰをマークす
る。パターン探索中にＴＶ内にＬフラグが検出された場
合、以下のイベントが行われる。
２を使用して、探索ツリーが終了する場所（すなわち、
探索パスの最後のテスト・ベクトル）を識別する。Ｌフ
ィールド３２内のビットの数も選択したＴＵサイズに等
しい。１ビットＴＵ構成では、ただ１つのビットがＬフ
ィールド３２内に必要である。２ビットＴＵ構成では、
２つのビットがＬフィールド３２内に必要である（この
場合も、一方のＬビットは奇数ビット境界ＲＰを識別
し、他方のＬビットは偶数ビット境界ＲＰを識別す
る）。学習プロセス中、ＲＰがこのテスト・ブロックの
ところで終了する場合、Ｍフラグを使用して、ＲＰをマ
ークする（ＲＰの最後のＴＵ＝ＣＴＵ＃、ただし、ＣＴ
Ｕ＃は、ＴＢ内のＴＶを見つけ出すデコードとして使用
される現在のＴＵである）。それ以外の場合、（ＲＰが
ＣＴＵ＃よりも長ければ）ＬフラグおよびＮＴＵ＃を使
用して、ＲＰをマークし、探索ツリーを終了する。実施
を簡単にするために、ただ１つのＬフラグを所与のＴＶ
内にセットすることができる。ＴＢ内で複数のＲＰをＬ
フラグでマークすることができる場合、探索ツリーを延
長し、Ｍフラグを使用して、いくつかのＲＰをマークす
る。パターン探索中にＴＶ内にＬフラグが検出された場
合、以下のイベントが行われる。
【００２４】１．テスト・パターン（ＴＰ）（すなわ
ち、受信アドレス）とＴＶ内のリファレンス・パターン
（ＲＰ）とを、正確に一致するように、ＮＴＵ＃フィー
ルド３３内で定義されたテスト・ユニット番号およびＬ
フラグによるビット境界まで比較する。
ち、受信アドレス）とＴＶ内のリファレンス・パターン
（ＲＰ）とを、正確に一致するように、ＮＴＵ＃フィー
ルド３３内で定義されたテスト・ユニット番号およびＬ
フラグによるビット境界まで比較する。
【００２５】２．ＴＰとＲＰが一致した場合、ＮＴＢ
ＰＴＲフィールド３４内のデータをＡＣ ＰＴＲフィー
ルド３６として割り当てる。
ＰＴＲフィールド３４内のデータをＡＣ ＰＴＲフィー
ルド３６として割り当てる。
【００２６】３．次いで、すべてのＡＣ ＰＴＲフィー
ルド３６のアクション・コード・ポインタを分類し、さ
らにフレーム処理を行うためにフレーム処理ユニットに
送る。
ルド３６のアクション・コード・ポインタを分類し、さ
らにフレーム処理を行うためにフレーム処理ユニットに
送る。
【００２７】次テスト・ユニット番号（ＮＴＵ＃）フィ
ールド３３内の値は、ＴＰとＴＶ内のＲＰとの間で一致
する必要があるビット・パターンの長さを保持する。Ｎ
ＴＵ＃フィールド３３内の「０」は、探索パスが終了し
たことを示す。マップされたＴＶ内でＭフラグがセット
されていない場合、ＴＶスロットは空である。ＮＴＵ＃
＝ＣＴＵ＃は、これが探索パス内の最後のＴＶであるこ
とを示す。このマップされたＴＶ内には、Ｍフラグおよ
びＬフラグの少なくとも一方がセットされたＲＰが存在
しなければならない。ＮＴＵ＃＞ＣＴＵ＃かつＬフラグ
がセットされないことは、このマップされたＴＶが、探
索を継続するための潜在的テスト・ノードであることを
示す。ＴＵ（ＮＴＵ＃−１）の長さ内のＴＰとＲＰの間
では（すなわちＴＰがＴＵ（ＮＴＵ＃−１）よりも長い
場合すべてのビットは、探索を継続するために正確に一
致する必要がある。それ以外の場合、探索パスは終了す
る。ＮＴＵ＃＞ＣＴＵ＃かつＬフラグの１つがセットさ
れることは、これが探索における最後のＴＶであること
を示す。Ｌフラグがセットされた場合、ＴＰとＲＰの間
でＴＵ（ＮＴＵ＃）およびＬフラグによって定義された
すべてのビットは、見つかったＲＰとみなすために正確
に一致しなければならない。
ールド３３内の値は、ＴＰとＴＶ内のＲＰとの間で一致
する必要があるビット・パターンの長さを保持する。Ｎ
ＴＵ＃フィールド３３内の「０」は、探索パスが終了し
たことを示す。マップされたＴＶ内でＭフラグがセット
されていない場合、ＴＶスロットは空である。ＮＴＵ＃
＝ＣＴＵ＃は、これが探索パス内の最後のＴＶであるこ
とを示す。このマップされたＴＶ内には、Ｍフラグおよ
びＬフラグの少なくとも一方がセットされたＲＰが存在
しなければならない。ＮＴＵ＃＞ＣＴＵ＃かつＬフラグ
がセットされないことは、このマップされたＴＶが、探
索を継続するための潜在的テスト・ノードであることを
示す。ＴＵ（ＮＴＵ＃−１）の長さ内のＴＰとＲＰの間
では（すなわちＴＰがＴＵ（ＮＴＵ＃−１）よりも長い
場合すべてのビットは、探索を継続するために正確に一
致する必要がある。それ以外の場合、探索パスは終了す
る。ＮＴＵ＃＞ＣＴＵ＃かつＬフラグの１つがセットさ
れることは、これが探索における最後のＴＶであること
を示す。Ｌフラグがセットされた場合、ＴＰとＲＰの間
でＴＵ（ＮＴＵ＃）およびＬフラグによって定義された
すべてのビットは、見つかったＲＰとみなすために正確
に一致しなければならない。
【００２８】ＮＴＢ ＰＴＲフィールド３４内の値は、
次のＴＢ用のベース・アドレスとして使用される。ＴＰ
のＴＵ（ＮＴＵ＃）ビット・パターンは、パターン探索
を継続するために次のＴＶを見つけ出すオフセットとし
て使用される。Ｌフラグがセットされた場合、ＮＴＢ
ＰＴＲフィールド３４は、一致したＲＰのアクション・
コード・ポインタを保持する。Ｌフラグがセットされな
い場合、ＮＴＢ ＰＴＲは、次のＴＢのアドレス・ポイ
ンタを保持する。
次のＴＢ用のベース・アドレスとして使用される。ＴＰ
のＴＵ（ＮＴＵ＃）ビット・パターンは、パターン探索
を継続するために次のＴＶを見つけ出すオフセットとし
て使用される。Ｌフラグがセットされた場合、ＮＴＢ
ＰＴＲフィールド３４は、一致したＲＰのアクション・
コード・ポインタを保持する。Ｌフラグがセットされな
い場合、ＮＴＢ ＰＴＲは、次のＴＢのアドレス・ポイ
ンタを保持する。
【００２９】リファレンス・パターン（ＲＰ）フィール
ド３５は、パターン探索中にビット比較のために使用さ
れるＲＰを保持し、ＴＢ内の各Ｍフラグごとに、一致ア
クション・コード・ポインタ（Ｍｘ ＡＣ ＰＴＲ）フ
ィールド３６内に記憶された対応するアクション・コー
ド・ポインタを有する。
ド３５は、パターン探索中にビット比較のために使用さ
れるＲＰを保持し、ＴＢ内の各Ｍフラグごとに、一致ア
クション・コード・ポインタ（Ｍｘ ＡＣ ＰＴＲ）フ
ィールド３６内に記憶された対応するアクション・コー
ド・ポインタを有する。
【００３０】好ましい実施形態として、着信テスト・パ
ターン（ＴＰ）（すなわち、受信アドレス）が到着した
とき、ＴＰの長さおよびビット・パターンをパターン突
合せエンジンに送る。パターン突合せエンジンは、ＴＰ
ビットおよびテスト・ベクトルを使用して、一致するＲ
Ｐを見つけ出すために探索ツリー中を進む。探索ツリー
から得られたテスト・ベクトル情報および（ＴＵの形
の）ＴＰビットを使用して、ＲＰ探索の継続を決定す
る。すべての一致したＲＰを探索パスおよびそれらの対
応するアクション・コード・ポインタとともに一時的に
記憶する。それらは、フレーム処理のためにパターン探
索の終了時に使用される。
ターン（ＴＰ）（すなわち、受信アドレス）が到着した
とき、ＴＰの長さおよびビット・パターンをパターン突
合せエンジンに送る。パターン突合せエンジンは、ＴＰ
ビットおよびテスト・ベクトルを使用して、一致するＲ
Ｐを見つけ出すために探索ツリー中を進む。探索ツリー
から得られたテスト・ベクトル情報および（ＴＵの形
の）ＴＰビットを使用して、ＲＰ探索の継続を決定す
る。すべての一致したＲＰを探索パスおよびそれらの対
応するアクション・コード・ポインタとともに一時的に
記憶する。それらは、フレーム処理のためにパターン探
索の終了時に使用される。
【００３１】リファレンス・パターン学習プロセス テスト・ブロック（ＴＢ）内のテスト・ベクトル（Ｔ
Ｖ）は、すべてのＴＢを結合して、様々な探索パスを形
成する情報を保持する。ＴＢ内の一致アクション・コー
ド・ポインタ（Ｍｘ ＡＣ ＰＴＲ）フィールドを使用
して、ＴＢ内のすべてのＭフラグ付きＲＰについてアク
ション・コード位置を記憶する。
Ｖ）は、すべてのＴＢを結合して、様々な探索パスを形
成する情報を保持する。ＴＢ内の一致アクション・コー
ド・ポインタ（Ｍｘ ＡＣ ＰＴＲ）フィールドを使用
して、ＴＢ内のすべてのＭフラグ付きＲＰについてアク
ション・コード位置を記憶する。
【００３２】着信テスト・パターン（ＴＰ）がＲＰ探索
のために到着したとき、パターン突合せエンジンは、Ｒ
Ｐビット・パターンおよび探索ツリーの開始点を使用し
て、探索パス中を進む。パターン探索中、（探索パスに
沿ったＴＶ内でＭまたはＬのフラグを付けられた）一致
したＲＰを記録する。パターン探索の終了時に、記録さ
れたＲＰの情報をフレームのフィルタリングまたは修正
および再送信のためにフレーム処理エンジンに送る。
のために到着したとき、パターン突合せエンジンは、Ｒ
Ｐビット・パターンおよび探索ツリーの開始点を使用し
て、探索パス中を進む。パターン探索中、（探索パスに
沿ったＴＶ内でＭまたはＬのフラグを付けられた）一致
したＲＰを記録する。パターン探索の終了時に、記録さ
れたＲＰの情報をフレームのフィルタリングまたは修正
および再送信のためにフレーム処理エンジンに送る。
【００３３】上述のように、ＴＢは、探索ツリーを作成
するために使用される。ＲＰ学習プロセス中、新しいＲ
Ｐが到着したとき、最初のステップは、探索を行い、こ
の「新しい」ＲＰがＲＰプール内にすでに存在するかど
うかを確かめることである。探索が完了した後、一致し
たＲＰが見つかった場合、一致したＲＰのアクション・
コードのみを更新する必要がある。それ以外の場合、新
しいＲＰおよびその中に含まれるアクション・コードを
有するように探索ツリーを延長する。探索を終了する前
に検査すべき最後のＴＢは、新しいＲＰを収容するため
に必要な情報を保持する。
するために使用される。ＲＰ学習プロセス中、新しいＲ
Ｐが到着したとき、最初のステップは、探索を行い、こ
の「新しい」ＲＰがＲＰプール内にすでに存在するかど
うかを確かめることである。探索が完了した後、一致し
たＲＰが見つかった場合、一致したＲＰのアクション・
コードのみを更新する必要がある。それ以外の場合、新
しいＲＰおよびその中に含まれるアクション・コードを
有するように探索ツリーを延長する。探索を終了する前
に検査すべき最後のＴＢは、新しいＲＰを収容するため
に必要な情報を保持する。
【００３４】各ＴＢは、学習したすべてのＲＰの探索ツ
リー・パスおよび（アクション・コード・ポインタ、長
さなど）パラメータを記憶する情報ブロックである。ｎ
個のＲＰを記録するために、ＴＢの最大数、ｍａｘ＿Ｔ
Ｂ ｍａｘ＿ＴＢ＝（ｎ−１）＊ＴＢ＋（ｓｔａｒｔＴＢ） が必要である。
リー・パスおよび（アクション・コード・ポインタ、長
さなど）パラメータを記憶する情報ブロックである。ｎ
個のＲＰを記録するために、ＴＢの最大数、ｍａｘ＿Ｔ
Ｂ ｍａｘ＿ＴＢ＝（ｎ−１）＊ＴＢ＋（ｓｔａｒｔＴＢ） が必要である。
【００３５】探索ツリーを形成するために使用されない
ＴＢは、「自由な」ＴＢである。すべての「自由な」Ｔ
Ｂは、結合されて、自由なＴＢ連鎖を形成する。ＲＰ更
新エンジンは、学習中に、自由なＴＢプールから必要に
応じてＴＢを得ることができる。（自由なＴＢ内の第１
のＴＶのＮＴＵｐｔｒは、自由なＴＢを結合する（次の
自由なＴＢを示す）ポインタとして使用される）。自由
なＴＢ連鎖の「頭部」および「尾部」は、固定の位置に
記録される。自由なＴＢがとられるたびに、「頭部」ポ
インタが更新される。また、（ＲＰ削除プロセスから）
ＴＢが自由になったとき、自由なＴＢは、自由なＴＢ連
鎖の尾部に結合され、「尾部」ポインタが更新される。
ＴＢは、「自由な」ＴＢである。すべての「自由な」Ｔ
Ｂは、結合されて、自由なＴＢ連鎖を形成する。ＲＰ更
新エンジンは、学習中に、自由なＴＢプールから必要に
応じてＴＢを得ることができる。（自由なＴＢ内の第１
のＴＶのＮＴＵｐｔｒは、自由なＴＢを結合する（次の
自由なＴＢを示す）ポインタとして使用される）。自由
なＴＢ連鎖の「頭部」および「尾部」は、固定の位置に
記録される。自由なＴＢがとられるたびに、「頭部」ポ
インタが更新される。また、（ＲＰ削除プロセスから）
ＴＢが自由になったとき、自由なＴＢは、自由なＴＢ連
鎖の尾部に結合され、「尾部」ポインタが更新される。
【００３６】次に、図４を参照すると、本発明の好まし
い実施形態によるリファレンス・パターンを学習する方
法のハイレベル論理流れ図が示されている。最初に、ス
テップ４１に示すように、自由なＴＢ内のすべてのＴＶ
をクリアし、すべての自由なＴＢエントリを連結する。
さらに、ステップ４２に示すように、すべてのＲＰ−Ａ
Ｃバッファをクリアし、またすべての自由なＲＰ−ＡＣ
バッファを連結する。これで初期設定プロセスが完了
し、リファレンス・パターンを学習する方法が開始でき
るようになる。
い実施形態によるリファレンス・パターンを学習する方
法のハイレベル論理流れ図が示されている。最初に、ス
テップ４１に示すように、自由なＴＢ内のすべてのＴＶ
をクリアし、すべての自由なＴＢエントリを連結する。
さらに、ステップ４２に示すように、すべてのＲＰ−Ａ
Ｃバッファをクリアし、またすべての自由なＲＰ−ＡＣ
バッファを連結する。これで初期設定プロセスが完了
し、リファレンス・パターンを学習する方法が開始でき
るようになる。
【００３７】新しい着信ＲＰ（ＮＲＰ）が到着し、かつ
ＲＰプールがいっぱいでない場合、ステップ４３に示す
ように、正確に一致したＲＰを探索する。以下の状態の
１つが発生した場合、探索は終了する。 １．ＲＰが見つかった ２．ＲＰが見つからない、ＮＲＰパターンが検査すべき
最後の（現在の）ＴＢ（ＴＵ（ＮＲＰ＝ＣＴＵ＃）のと
ころで終了した。ただし、ＣＴＵ＃は、探索を終了する
前にテストした最後の（現在の）ＴＢ ＴＵ＃である。 ３．ＲＰが見つからない、ＴＶ（ＮＲＰ）がＴＢ内の
「空の」ＴＶスロット内にマップされた、ＴＵ（ＮＲ
Ｐ）＞ＣＴＵ＃ ４．ＲＰが見つからない、ＲＰがＮＲＰのサブセットで
ある（ＮＲＰがＲＰよりも長い） ５．ＲＰが見つからない、ＮＲＰがＲＰのサブセットで
ある（ＮＲＰがＲＰよりも短い） ６．ＲＰが見つからない、ＮＲＰおよびＲＰ（ＮＴＵ＃
−１）ビット・パターンが一致しない
ＲＰプールがいっぱいでない場合、ステップ４３に示す
ように、正確に一致したＲＰを探索する。以下の状態の
１つが発生した場合、探索は終了する。 １．ＲＰが見つかった ２．ＲＰが見つからない、ＮＲＰパターンが検査すべき
最後の（現在の）ＴＢ（ＴＵ（ＮＲＰ＝ＣＴＵ＃）のと
ころで終了した。ただし、ＣＴＵ＃は、探索を終了する
前にテストした最後の（現在の）ＴＢ ＴＵ＃である。 ３．ＲＰが見つからない、ＴＶ（ＮＲＰ）がＴＢ内の
「空の」ＴＶスロット内にマップされた、ＴＵ（ＮＲ
Ｐ）＞ＣＴＵ＃ ４．ＲＰが見つからない、ＲＰがＮＲＰのサブセットで
ある（ＮＲＰがＲＰよりも長い） ５．ＲＰが見つからない、ＮＲＰがＲＰのサブセットで
ある（ＮＲＰがＲＰよりも短い） ６．ＲＰが見つからない、ＮＲＰおよびＲＰ（ＮＴＵ＃
−１）ビット・パターンが一致しない
【００３８】次いで、ステップ４４に示すように、ＲＰ
が見つかったか否かを決定する。ＲＰが見つかった場
合、ステップ４５に示すように、一致したＲＰのアクシ
ョン・コード記述子をＮＲＰアクション・コード記述子
と交換する。これで学習プロセスが終了する。
が見つかったか否かを決定する。ＲＰが見つかった場
合、ステップ４５に示すように、一致したＲＰのアクシ
ョン・コード記述子をＮＲＰアクション・コード記述子
と交換する。これで学習プロセスが終了する。
【００３９】しかし、ＲＰが見つからない場合、ステッ
プ４６に示すように、（ＲＰ−ＡＣバッファ・プールか
ら）ＲＰ−ＡＣバッファを得、ＮＲＰ ＡＣ記述子をＲ
Ｐ−ＡＣバッファ内に保管し、ＮＲＰ挿入プロセスのた
めにＮＲＰ−ＡＣバッファ・ポインタ（ＮＲＰ−ＡＣ−
ｐｔｒ）を保管することによってＮＲＰのアクション・
コード記述子を保管する。ステップ４７で、ＮＲＰパタ
ーンがこの点（すなわち、ＴＢ（ＴＵ（ＮＲＰ）＝ＴＵ
（Ｃ））のところで終了したか否かを決定する。ＮＲＰ
パターンが終了している場合、ステップ４８に示すよう
に、ＴＶ内でＮＲＰをＭフラグＲＰとしてマークし、Ｎ
ＲＰ−ＡＣ−ｐｔｒを適切なＴＢ位置に記憶することに
よってＴＶ（ＴＵ（ＮＲＰ））に関連するＴＶを修正す
る。ＴＢ内の残りのフィールドは不変である。これで学
習プロセスが終了する。
プ４６に示すように、（ＲＰ−ＡＣバッファ・プールか
ら）ＲＰ−ＡＣバッファを得、ＮＲＰ ＡＣ記述子をＲ
Ｐ−ＡＣバッファ内に保管し、ＮＲＰ挿入プロセスのた
めにＮＲＰ−ＡＣバッファ・ポインタ（ＮＲＰ−ＡＣ−
ｐｔｒ）を保管することによってＮＲＰのアクション・
コード記述子を保管する。ステップ４７で、ＮＲＰパタ
ーンがこの点（すなわち、ＴＢ（ＴＵ（ＮＲＰ）＝ＴＵ
（Ｃ））のところで終了したか否かを決定する。ＮＲＰ
パターンが終了している場合、ステップ４８に示すよう
に、ＴＶ内でＮＲＰをＭフラグＲＰとしてマークし、Ｎ
ＲＰ−ＡＣ−ｐｔｒを適切なＴＢ位置に記憶することに
よってＴＶ（ＴＵ（ＮＲＰ））に関連するＴＶを修正す
る。ＴＢ内の残りのフィールドは不変である。これで学
習プロセスが終了する。
【００４０】しかし、ＮＲＰパターンが終了していない
場合、ステップ４９に示すように、マップしたＴＶスロ
ットが「空の」スロットであるか否かを決定する。マッ
プしたＴＶスロットが「空の」スロットである場合、ス
テップ５０に示すように、ＮＲＰをＬフラグＲＰとして
マークし、ＴＶ（ＴＵ（ＮＲＰ））＝（０、Ｌ（ＮＲ
Ｐ）、ＴＵ（ＮＲＰ）、ＮＲＰ−ＡＣ−ｐｔｒ、ＮＲ
Ｐ）に設定し、次いでＴＶ（ＴＵ（ＮＲＰ））をマップ
した空のＴＶスロットに書き込むことによってこのＴＢ
内のＴＶ（ＮＲＰ）を更新する。これで学習プロセスが
終了する。
場合、ステップ４９に示すように、マップしたＴＶスロ
ットが「空の」スロットであるか否かを決定する。マッ
プしたＴＶスロットが「空の」スロットである場合、ス
テップ５０に示すように、ＮＲＰをＬフラグＲＰとして
マークし、ＴＶ（ＴＵ（ＮＲＰ））＝（０、Ｌ（ＮＲ
Ｐ）、ＴＵ（ＮＲＰ）、ＮＲＰ−ＡＣ−ｐｔｒ、ＮＲ
Ｐ）に設定し、次いでＴＶ（ＴＵ（ＮＲＰ））をマップ
した空のＴＶスロットに書き込むことによってこのＴＢ
内のＴＶ（ＮＲＰ）を更新する。これで学習プロセスが
終了する。
【００４１】それ以外の場合、マップしたＴＶスロット
が「空の」スロットでない場合、ステップ５１に示すよ
うに、自由なＴＢ連鎖から自由なＴＢを得、（「次の」
自由なＴＢを示す）自由なＴＢ「頭部」ポインタを更新
し、新たに得られたＴＢのポインタを後のＮＲＰ挿入プ
ロセスのために保管する。さらに、ステップ５２に示す
ように、ＮＲＰとＲＰ（ＮＴＵ＃）が互いにサブセット
であるか否かを決定する。ＮＲＰとＲＰ（ＮＴＵ＃）が
互いにサブセットである場合、ステップ５３に示すよう
に、ＮＲＰがＲＰ（ＮＴＵ＃）よりも長いか否かをもう
一度決定する。ＮＲＰがＲＰ（ＮＴＵ＃）よりも長い場
合、ステップ５４に示すように、次のようにＲＰをＭフ
ラグ・エントリとしてマークし、ＮＲＰをＬフラグ・エ
ントリとしてマークすることによって新しいＴＢをＮＲ
Ｐ挿入のために準備する。 １．ＴＶ（ＴＵ（ＲＰ））＝（Ｍ（ＲＰ）、Ｌ（ＮＲ
Ｐ）、ＴＵ（ＮＲＰ）、ＮＲＰ−ＡＣ−ｐｔｒ、ＮＲ
Ｐ） （ＲＰパターン・ビットおよびＴＵサイズに応じて、新
しいＴＢ（ＮＴＢ）内でＲＰをＭフラグ・エントリとし
てマークするために複数のＴＶを修正する必要がある） ＲＰ情報は、ＴＢ（ＣＴＵ＃）内のＴＶ（ＴＵ（Ｒ
Ｐ））内で得られる。 ２．Ｍ（ＲＰ）−ＡＣ−ｐｔｒ＝ＴＢ（ＣＴＵ＃）内の
（ＴＶ（ＴＵ（ＲＰ））内で得られる）ＲＰ−ＡＣ−ｐ
ｔｒ ３．ＴＵ（ＲＰ）＝ＴＵ（ｋ）とする。
が「空の」スロットでない場合、ステップ５１に示すよ
うに、自由なＴＢ連鎖から自由なＴＢを得、（「次の」
自由なＴＢを示す）自由なＴＢ「頭部」ポインタを更新
し、新たに得られたＴＢのポインタを後のＮＲＰ挿入プ
ロセスのために保管する。さらに、ステップ５２に示す
ように、ＮＲＰとＲＰ（ＮＴＵ＃）が互いにサブセット
であるか否かを決定する。ＮＲＰとＲＰ（ＮＴＵ＃）が
互いにサブセットである場合、ステップ５３に示すよう
に、ＮＲＰがＲＰ（ＮＴＵ＃）よりも長いか否かをもう
一度決定する。ＮＲＰがＲＰ（ＮＴＵ＃）よりも長い場
合、ステップ５４に示すように、次のようにＲＰをＭフ
ラグ・エントリとしてマークし、ＮＲＰをＬフラグ・エ
ントリとしてマークすることによって新しいＴＢをＮＲ
Ｐ挿入のために準備する。 １．ＴＶ（ＴＵ（ＲＰ））＝（Ｍ（ＲＰ）、Ｌ（ＮＲ
Ｐ）、ＴＵ（ＮＲＰ）、ＮＲＰ−ＡＣ−ｐｔｒ、ＮＲ
Ｐ） （ＲＰパターン・ビットおよびＴＵサイズに応じて、新
しいＴＢ（ＮＴＢ）内でＲＰをＭフラグ・エントリとし
てマークするために複数のＴＶを修正する必要がある） ＲＰ情報は、ＴＢ（ＣＴＵ＃）内のＴＶ（ＴＵ（Ｒ
Ｐ））内で得られる。 ２．Ｍ（ＲＰ）−ＡＣ−ｐｔｒ＝ＴＢ（ＣＴＵ＃）内の
（ＴＶ（ＴＵ（ＲＰ））内で得られる）ＲＰ−ＡＣ−ｐ
ｔｒ ３．ＴＵ（ＲＰ）＝ＴＵ（ｋ）とする。
【００４２】ＮＲＰがＲＰ（ＮＴＵ＃）よりも短い場
合、ステップ５５に示すように、ＮＲＰをＭフラグ・エ
ントリとしてマークし、ＲＰをＬフラグ・エントリとし
てマークすることによってＮＴＢをＮＲＰ挿入のために
準備する。 １．ＴＶ（ＴＵ（ＮＲＰ））＝（Ｍ（ＮＲＰ）、Ｌ（Ｒ
Ｐ）、ＴＵ（ＲＰ）、ＲＰ−ＡＣ−ｐｔｒ、ＲＰ） （ＮＲＰパターン・ビットおよびＴＵサイズに応じて、
ＮＴＢ内でＮＲＰをＭフラグ・エントリとしてマークす
るために複数のＴＶを修正する必要がある） ＲＰ情報は、ＴＢ（ＣＴＵ＃）内のＴＶ（ＴＵ（Ｒ
Ｐ））内で得られる。 ２．（ＴＶ（ＴＵ（ＲＰ））内で得られる）Ｍ（ＮＲ
Ｐ）−ＡＣ−ｐｔｒをＮＴＢ内の適切なＭＲＰ−ｐｔｒ
位置のところで更新する ３．ＴＵ（ＮＲＰ）＝ＴＵ（ｋ）とする。
合、ステップ５５に示すように、ＮＲＰをＭフラグ・エ
ントリとしてマークし、ＲＰをＬフラグ・エントリとし
てマークすることによってＮＴＢをＮＲＰ挿入のために
準備する。 １．ＴＶ（ＴＵ（ＮＲＰ））＝（Ｍ（ＮＲＰ）、Ｌ（Ｒ
Ｐ）、ＴＵ（ＲＰ）、ＲＰ−ＡＣ−ｐｔｒ、ＲＰ） （ＮＲＰパターン・ビットおよびＴＵサイズに応じて、
ＮＴＢ内でＮＲＰをＭフラグ・エントリとしてマークす
るために複数のＴＶを修正する必要がある） ＲＰ情報は、ＴＢ（ＣＴＵ＃）内のＴＶ（ＴＵ（Ｒ
Ｐ））内で得られる。 ２．（ＴＶ（ＴＵ（ＲＰ））内で得られる）Ｍ（ＮＲ
Ｐ）−ＡＣ−ｐｔｒをＮＴＢ内の適切なＭＲＰ−ｐｔｒ
位置のところで更新する ３．ＴＵ（ＮＲＰ）＝ＴＵ（ｋ）とする。
【００４３】ステップ５２から、ＮＲＰとＲＰ（ＮＴＵ
＃）が互いにサブセットでない場合、ステップ５６に示
すように、ＲＰとＮＲＰを比較し、最初のＴＵ、例えば
ＴＵ（ｄ）を見つけ出し、ビット・パターンを異ならせ
ることによって、そのビット・パターンがＲＰとＮＲＰ
の間で異なる最下位ＴＵを見つける。さらに、ステップ
５７に示すように、次のようにＮＲＰをＬフラグ・エン
トリとしてマークし、ＲＰ（ＮＴＵ＃）情報をコピーす
ることによってＮＴＢをＮＲＰ挿入のために準備する。 １．ＴＶ（ＴＵ（ＮＲＰ（ｄ）））＝（０、Ｌ（ＮＲ
Ｐ）、ＴＵ（ＮＲＰ）、ＮＲＰ−ＡＣ−ｐｔｒ、ＮＲ
Ｐ） ２．ＴＶ（ＴＵ（ＲＰ（ｄ）））＝（０、ｘｘ、ｘｘ、
ｘｘ、ｘｘ） ＲＰ情報は、次のようにしてＴＢ（ＣＴＵ＃）内のＴＶ
（ＴＵ（ＲＰ（ＣＴＵ＃）））内で得られる。 ａ．ＴＶ（ＴＵ（ＲＰ（ＣＴＵ＃）））をコピーする ｂ．Ｍフラグ・フィールド（ＭフラグおよびＭＲＰ−Ａ
Ｃ−ｐｔｒフィールド）を遮断する ｃ．ＴＶ（ＴＵ（ＮＲＰ（ｄ）））ＴＶスロットをＮＴ
Ｂ内に書き込む ＴＶ（ＴＵ（ＮＲＰ（ｄ）））は、ＮＲＰの「ｄ」テス
ト・ユニット・ビット・パターンによって識別されるテ
スト・ベクトルである。 ３．ＴＵ（ｄ）＝ＴＵ（ｋ）とする。
＃）が互いにサブセットでない場合、ステップ５６に示
すように、ＲＰとＮＲＰを比較し、最初のＴＵ、例えば
ＴＵ（ｄ）を見つけ出し、ビット・パターンを異ならせ
ることによって、そのビット・パターンがＲＰとＮＲＰ
の間で異なる最下位ＴＵを見つける。さらに、ステップ
５７に示すように、次のようにＮＲＰをＬフラグ・エン
トリとしてマークし、ＲＰ（ＮＴＵ＃）情報をコピーす
ることによってＮＴＢをＮＲＰ挿入のために準備する。 １．ＴＶ（ＴＵ（ＮＲＰ（ｄ）））＝（０、Ｌ（ＮＲ
Ｐ）、ＴＵ（ＮＲＰ）、ＮＲＰ−ＡＣ−ｐｔｒ、ＮＲ
Ｐ） ２．ＴＶ（ＴＵ（ＲＰ（ｄ）））＝（０、ｘｘ、ｘｘ、
ｘｘ、ｘｘ） ＲＰ情報は、次のようにしてＴＢ（ＣＴＵ＃）内のＴＶ
（ＴＵ（ＲＰ（ＣＴＵ＃）））内で得られる。 ａ．ＴＶ（ＴＵ（ＲＰ（ＣＴＵ＃）））をコピーする ｂ．Ｍフラグ・フィールド（ＭフラグおよびＭＲＰ−Ａ
Ｃ−ｐｔｒフィールド）を遮断する ｃ．ＴＶ（ＴＵ（ＮＲＰ（ｄ）））ＴＶスロットをＮＴ
Ｂ内に書き込む ＴＶ（ＴＵ（ＮＲＰ（ｄ）））は、ＮＲＰの「ｄ」テス
ト・ユニット・ビット・パターンによって識別されるテ
スト・ベクトルである。 ３．ＴＵ（ｄ）＝ＴＵ（ｋ）とする。
【００４４】最後に、ステップ５８で、探索を終了する
前に実行された最後のＴＢ（ＴＢ（ＣＴＵ＃））内のＴ
Ｖ（ＴＵ（ＲＰ（ＣＴＵ＃）））のＮＴＵ＃およびＮＴ
Ｕ−ｐｔｒを、ＴＶ（ＴＵ（ＲＰ（ＣＴＵ＃）））＝
（ｘｘ、Ｌ（ＲＰ）＝０、ＮＴＵ＃＝ＴＵ（ｋ）、ＮＴ
Ｕ−ｐｔｒ＝（新しいＴＢｐｔｒ）、ｘｘ）の場合のよ
うに、ＮＴＢを示すように修正することによって新しい
ＴＢ（ＮＴＢ）を探索パス内に挿入する。ただし、「ｘ
ｘ」は、不変のフィールドである。これで学習プロセス
が終了する。
前に実行された最後のＴＢ（ＴＢ（ＣＴＵ＃））内のＴ
Ｖ（ＴＵ（ＲＰ（ＣＴＵ＃）））のＮＴＵ＃およびＮＴ
Ｕ−ｐｔｒを、ＴＶ（ＴＵ（ＲＰ（ＣＴＵ＃）））＝
（ｘｘ、Ｌ（ＲＰ）＝０、ＮＴＵ＃＝ＴＵ（ｋ）、ＮＴ
Ｕ−ｐｔｒ＝（新しいＴＢｐｔｒ）、ｘｘ）の場合のよ
うに、ＮＴＢを示すように修正することによって新しい
ＴＢ（ＮＴＢ）を探索パス内に挿入する。ただし、「ｘ
ｘ」は、不変のフィールドである。これで学習プロセス
が終了する。
【００４５】次に、図５および図６を参照すると、図４
に示される学習プロセスによる複数の例示的なリファレ
ンス・パターン挿入の絵画図が示されている。ＲＰ
（１、ｍ）が到着したとき、それを最初のＴＶをフェッ
チし、次いでＲＰが「空の」ＴＶスロットにマップされ
たことを示す。前のＲＰの探索が終了し、ＲＰのアクシ
ョン・コード記述子を保管し、新しいＴＶ（ＴＶ＝
（０、Ｌ、ＲＰ（１、ｍ）、ＴＵ（ｍ）、ＲＰ−１ Ａ
Ｃ−ｐｔｒ）；ＲＰ−１ ＡＣ−ｐｔｒはＡＣ位置を示
す）を生成し、ＴＵ（１）ＲＰ（１）位置、例えばＲＰ
のＴＵ（１）「０１」に保管する。
に示される学習プロセスによる複数の例示的なリファレ
ンス・パターン挿入の絵画図が示されている。ＲＰ
（１、ｍ）が到着したとき、それを最初のＴＶをフェッ
チし、次いでＲＰが「空の」ＴＶスロットにマップされ
たことを示す。前のＲＰの探索が終了し、ＲＰのアクシ
ョン・コード記述子を保管し、新しいＴＶ（ＴＶ＝
（０、Ｌ、ＲＰ（１、ｍ）、ＴＵ（ｍ）、ＲＰ−１ Ａ
Ｃ−ｐｔｒ）；ＲＰ−１ ＡＣ−ｐｔｒはＡＣ位置を示
す）を生成し、ＴＵ（１）ＲＰ（１）位置、例えばＲＰ
のＴＵ（１）「０１」に保管する。
【００４６】ＲＰ（２、ｈ）が到着したとき、再びそれ
を最初のＴＶフェッチの後でＴＵ（１）内の空のＴＶス
ロットにマップする。この場合も、ＡＣ記述子を保管
し、新しいＴＶを生成し、そのＴＵ（１）ＴＶスロッ
ト、例えば「１１」スロット内に保管する。
を最初のＴＶフェッチの後でＴＵ（１）内の空のＴＶス
ロットにマップする。この場合も、ＡＣ記述子を保管
し、新しいＴＶを生成し、そのＴＵ（１）ＴＶスロッ
ト、例えば「１１」スロット内に保管する。
【００４７】ＲＰ（３、ｎ）が到着したとき、ＲＰ
（３、ｎ）およびＲＰ（１、ｍ）がそれらの最初の６つ
のＴＵ上のビット・パターンを有すると仮定すると、Ｔ
Ｕ（７）は、２つのＲＰ間の異なるビット・パターンを
保持する最初のＴＵである。明らかに、最初のＴＶの後
でＲＰ（１、ｍ）とＲＰ（３、ｎ）を比較したとき、探
索がＲＰ一致なしでＴＵ（１）のところで終了すること
が示される。この場合、探索パス内にＲＰ（３、ｎ）を
追加する以下の複数のステップを行う。 １．ＲＰ（３、ｎ）のＡＣ記述子を保管する ２．新しいＴＵブロックを得る ３．ＲＰ−１とＲＰ−３を区別することができる最初の
ＴＵを見つける。この場合、それはＴＵ（７）である。 ４．ＴＶ（ＲＰ（１））を新しいＴＵ位置ＴＵ（ＲＰ
（１、７））ＲＰ−１ＴＵ（７）ビット・パターンにデ
コードとしてコピーする ５．ＲＰ−３に対して新しいＴＶ、ＴＶ＝（０、Ｌ、Ｒ
Ｐ（３、ｎ）、ＴＵ（ｎ）、ＲＰ−３ ＡＣ−ｐｔｒ）
を生成し、新しいＴＵ位置ＴＵ（ＲＰ（３、７））に保
管する ６．ＴＶ（ＲＰ（１、１））をＴＶ（ＲＰ（１、１））
＝（０、０、ＲＰ（１、ｍ）、ＴＵ（７）、「新しいＴ
Ｕ（７）−ｐｔｒ）に修正することによって新しいＴＵ
を探索パスに結合する。
（３、ｎ）およびＲＰ（１、ｍ）がそれらの最初の６つ
のＴＵ上のビット・パターンを有すると仮定すると、Ｔ
Ｕ（７）は、２つのＲＰ間の異なるビット・パターンを
保持する最初のＴＵである。明らかに、最初のＴＶの後
でＲＰ（１、ｍ）とＲＰ（３、ｎ）を比較したとき、探
索がＲＰ一致なしでＴＵ（１）のところで終了すること
が示される。この場合、探索パス内にＲＰ（３、ｎ）を
追加する以下の複数のステップを行う。 １．ＲＰ（３、ｎ）のＡＣ記述子を保管する ２．新しいＴＵブロックを得る ３．ＲＰ−１とＲＰ−３を区別することができる最初の
ＴＵを見つける。この場合、それはＴＵ（７）である。 ４．ＴＶ（ＲＰ（１））を新しいＴＵ位置ＴＵ（ＲＰ
（１、７））ＲＰ−１ＴＵ（７）ビット・パターンにデ
コードとしてコピーする ５．ＲＰ−３に対して新しいＴＶ、ＴＶ＝（０、Ｌ、Ｒ
Ｐ（３、ｎ）、ＴＵ（ｎ）、ＲＰ−３ ＡＣ−ｐｔｒ）
を生成し、新しいＴＵ位置ＴＵ（ＲＰ（３、７））に保
管する ６．ＴＶ（ＲＰ（１、１））をＴＶ（ＲＰ（１、１））
＝（０、０、ＲＰ（１、ｍ）、ＴＵ（７）、「新しいＴ
Ｕ（７）−ｐｔｒ）に修正することによって新しいＴＵ
を探索パスに結合する。
【００４８】ＲＰ（４、ｐ）が到着したとき、ＲＰ−４
とＲＰ−１はＴＵ（５）のところで異なり、探索はＴＶ
（ＲＰ（１、１））比較の後で終了する。ＲＰ（３、
ｎ）を挿入する場合と同様に、以下のステップを行う。 １．ＲＰ（４、ｎ）のＡＣ記述子を保管する ２．新しいＴＵブロックを得る ３．ＲＰ−１とＲＰ−４を区別することができる最初の
ＴＵを見つける。この場合、それはＴＵ（５）である。 ４．ＴＶ（ＲＰ（１））を新しいＴＵ位置ＴＵ（ＲＰ
（１、５））ＲＰ−１ＴＵ（５）ビット・パターンにデ
コードとしてコピーする ５．ＲＰ−４に対して新しいＴＶ、ＴＶ＝（０、Ｌ、Ｒ
Ｐ（４、ｐ）、ＴＵ（ｎ）、ＲＰ−４ ＡＣ−ｐｔｒ）
を生成し、新しいＴＵ位置ＴＵ（ＲＰ（４、５））に保
管する ６．ＴＶ（ＲＰ（１、１））をＴＶ（ＲＰ（１、１））
＝（０、０、ＲＰ（１、ｍ）、ＴＵ（５）、「新しいＴ
Ｕ（５）−ｐｔｒ）に修正することによって新しいＴＵ
を探索パスに結合する。
とＲＰ−１はＴＵ（５）のところで異なり、探索はＴＶ
（ＲＰ（１、１））比較の後で終了する。ＲＰ（３、
ｎ）を挿入する場合と同様に、以下のステップを行う。 １．ＲＰ（４、ｎ）のＡＣ記述子を保管する ２．新しいＴＵブロックを得る ３．ＲＰ−１とＲＰ−４を区別することができる最初の
ＴＵを見つける。この場合、それはＴＵ（５）である。 ４．ＴＶ（ＲＰ（１））を新しいＴＵ位置ＴＵ（ＲＰ
（１、５））ＲＰ−１ＴＵ（５）ビット・パターンにデ
コードとしてコピーする ５．ＲＰ−４に対して新しいＴＶ、ＴＶ＝（０、Ｌ、Ｒ
Ｐ（４、ｐ）、ＴＵ（ｎ）、ＲＰ−４ ＡＣ−ｐｔｒ）
を生成し、新しいＴＵ位置ＴＵ（ＲＰ（４、５））に保
管する ６．ＴＶ（ＲＰ（１、１））をＴＶ（ＲＰ（１、１））
＝（０、０、ＲＰ（１、ｍ）、ＴＵ（５）、「新しいＴ
Ｕ（５）−ｐｔｒ）に修正することによって新しいＴＵ
を探索パスに結合する。
【００４９】ＲＰ−５は９ビット・パターンであり、９
番目のビットは「１」であり、それはＲＰ−１内の最初
の９ビットと同じである。ＲＰ−５が到着したとき、そ
れはＴＶ（ＲＰ−５、１）テスト（ＴＳ（ＲＰ−１、
４）＝ＴＳ（ＲＰ−４、４））を送る。探索は継続す
る。しかし、ＴＶ（ＲＰ−５、５）を処理したとき、Ｒ
Ｐ−５がそのＴＵを使い尽くすので探索は終了する。Ｔ
Ｖ（ＲＰ−５、５）を検査することによって、ＲＰ−５
に対応するＭフラグがセットされることはない。言い換
えれば、探索中にＲＰ−５が一致することはない。した
がって、ＲＰ−５を探索パス中に挿入する以下のステッ
プを行う必要がある。 １．ＲＰ（５、５．１）のＡＣ記述子を保管する ２．ＲＰ−５は「奇数の」ＴＵ（５）境界で終了するの
で、ＭフラグおよびＲＰ−５ＡＣポインタが含まれるよ
うに、ＲＰ−５に対応する両方のＴＶ（ＲＰ５、５．
１）を修正する。（ＲＰ−５が１０ビットを有する場
合、１つのＴＶ（ＲＰ−５、５）を修正するだけでよ
い）。ＲＰが新しいＲＰと正確に一致する場合、ＲＰ
ＡＣを交換するだけでよい。
番目のビットは「１」であり、それはＲＰ−１内の最初
の９ビットと同じである。ＲＰ−５が到着したとき、そ
れはＴＶ（ＲＰ−５、１）テスト（ＴＳ（ＲＰ−１、
４）＝ＴＳ（ＲＰ−４、４））を送る。探索は継続す
る。しかし、ＴＶ（ＲＰ−５、５）を処理したとき、Ｒ
Ｐ−５がそのＴＵを使い尽くすので探索は終了する。Ｔ
Ｖ（ＲＰ−５、５）を検査することによって、ＲＰ−５
に対応するＭフラグがセットされることはない。言い換
えれば、探索中にＲＰ−５が一致することはない。した
がって、ＲＰ−５を探索パス中に挿入する以下のステッ
プを行う必要がある。 １．ＲＰ（５、５．１）のＡＣ記述子を保管する ２．ＲＰ−５は「奇数の」ＴＵ（５）境界で終了するの
で、ＭフラグおよびＲＰ−５ＡＣポインタが含まれるよ
うに、ＲＰ−５に対応する両方のＴＶ（ＲＰ５、５．
１）を修正する。（ＲＰ−５が１０ビットを有する場
合、１つのＴＶ（ＲＰ−５、５）を修正するだけでよ
い）。ＲＰが新しいＲＰと正確に一致する場合、ＲＰ
ＡＣを交換するだけでよい。
【００５０】リファレンス・パターン削除プロセスリフ
ァレンス・パターン削除プロセスによってリファレンス
・パターン（ＲＰ）をＲＰプールから削除する。削除Ｒ
Ｐ（ＤＲＰ）が到着したとき、削除プロセス・エンジン
は、まず、正確に一致したＤＲＰについてＲＰプールを
探索する。次いで、削除プロセスは、ＤＲＰがＲＰプー
ル内に見つかった場合、ＤＲＰを除去し、探索パスを
「掃除」する。それ以外の場合、リファレンス・パター
ン削除プロセスは、それ以上動作せずに終了する。
ァレンス・パターン削除プロセスによってリファレンス
・パターン（ＲＰ）をＲＰプールから削除する。削除Ｒ
Ｐ（ＤＲＰ）が到着したとき、削除プロセス・エンジン
は、まず、正確に一致したＤＲＰについてＲＰプールを
探索する。次いで、削除プロセスは、ＤＲＰがＲＰプー
ル内に見つかった場合、ＤＲＰを除去し、探索パスを
「掃除」する。それ以外の場合、リファレンス・パター
ン削除プロセスは、それ以上動作せずに終了する。
【００５１】最後の２つのＴＢおよびそれらのＴＶ内容
は、ＤＲＰ探索中に保管され、ＤＲＰ削除を実行する場
合に使用される。削除プロセスを説明するために使用す
る略語を次に示す。 ＴＢ（ＣＴＵ＃）：ＤＲＰ探索を終了する前に実行すべ
き最後の（現在の）ＴＢ ＣＴＵ＃：探索中にＴＢ（ＣＴＵ＃）内のＴＶを選択す
るアドレス・デコードとして使用されるＴＵ番号 ＴＢ（ＰＴＵ＃）：ＴＢ（ＣＴＵ＃）の前に実行される
ＴＢ ＰＴＵ＃：探索中にＴＢ（ＰＴＵ＃）内のＴＶを選択す
るアドレス・デコードとして使用されるＴＵ番号 ＴＶ（ＴＵ（ＤＲＰ（ＣＴＵ＃）））：ＤＲＰ探索中に
テストすべきＴＢ（ＣＴＵ＃）内のＴＶ ＴＶ（ＴＵ（ＤＲＰ（ＰＴＵ＃）））：ＤＲＰ探索中に
テストすべきＴＢ（ＰＴＵ＃）内のＴＶ。
は、ＤＲＰ探索中に保管され、ＤＲＰ削除を実行する場
合に使用される。削除プロセスを説明するために使用す
る略語を次に示す。 ＴＢ（ＣＴＵ＃）：ＤＲＰ探索を終了する前に実行すべ
き最後の（現在の）ＴＢ ＣＴＵ＃：探索中にＴＢ（ＣＴＵ＃）内のＴＶを選択す
るアドレス・デコードとして使用されるＴＵ番号 ＴＢ（ＰＴＵ＃）：ＴＢ（ＣＴＵ＃）の前に実行される
ＴＢ ＰＴＵ＃：探索中にＴＢ（ＰＴＵ＃）内のＴＶを選択す
るアドレス・デコードとして使用されるＴＵ番号 ＴＶ（ＴＵ（ＤＲＰ（ＣＴＵ＃）））：ＤＲＰ探索中に
テストすべきＴＢ（ＣＴＵ＃）内のＴＶ ＴＶ（ＴＵ（ＤＲＰ（ＰＴＵ＃）））：ＤＲＰ探索中に
テストすべきＴＢ（ＰＴＵ＃）内のＴＶ。
【００５２】次に、図７を参照すると、本発明の好まし
い実施形態による探索ツリーからリファレンス・パター
ンを削除する方法のハイレベル論理流れ図が示されてい
る。削除すべきＲＰ（ＤＲＰ）を受け取った後、ステッ
プ６１に示すように、ＲＰプール内の正確に一致したＲ
Ｐを探索する（ＲＰ一致プロセスを使用して、正確に一
致したＤＲＰを捜す）。ステップ６２に示すように、Ｄ
ＲＰが見つかったか否かを決定する。ＤＲＰが見つから
なかった場合、削除プロセスは終了する。
い実施形態による探索ツリーからリファレンス・パター
ンを削除する方法のハイレベル論理流れ図が示されてい
る。削除すべきＲＰ（ＤＲＰ）を受け取った後、ステッ
プ６１に示すように、ＲＰプール内の正確に一致したＲ
Ｐを探索する（ＲＰ一致プロセスを使用して、正確に一
致したＤＲＰを捜す）。ステップ６２に示すように、Ｄ
ＲＰが見つかったか否かを決定する。ＤＲＰが見つから
なかった場合、削除プロセスは終了する。
【００５３】しかし、ＤＲＰが見つかった場合、ステッ
プ６３に示すように、ＴＢ（ＣＴＵ＃）内のＴＶ（ＴＵ
（ＣＴＵ＃））内のＤＲＰエントリ（すなわち、実行さ
れた最後のＴＢ）を遮断する。ＤＲＰがＭフラグ・エン
トリの場合、ＴＶ内のＭフラグを遮断する。しかし、Ｄ
ＲＰがＬフラグ・エントリの場合、ＴＶ内のＭフラグ・
フィールドに触れることなく、ＴＶ内のＬフラグ、ＮＴ
Ｕ＃、ＲＰ−ＡＣ−ｐｔｒ、ＲＰをすべて遮断する。そ
の後、ステップ６４で、ＤＲＰ−ＡＣバッファを自由な
ＲＰ−ＡＣバッファ・プールに戻す。これは、ＤＲＰ−
ＡＣバッファを示すように自由なプール内の最後のＲＰ
−ＡＣバッファを更新し、（ＤＲＰ−ＡＣバッファ位置
に等しい）ＡＣバッファ・プール「尾部」ポインタ・レ
ジスタを更新することによって行う。次に、ステップ６
５に示すように、ＴＢ（ＣＴＵ＃）がＴＢ（１）に等し
いか否かを決定する。ＴＢ（ＣＴＵ＃）がＴＢ（１）に
等しい場合、削除プロセスが終了する。
プ６３に示すように、ＴＢ（ＣＴＵ＃）内のＴＶ（ＴＵ
（ＣＴＵ＃））内のＤＲＰエントリ（すなわち、実行さ
れた最後のＴＢ）を遮断する。ＤＲＰがＭフラグ・エン
トリの場合、ＴＶ内のＭフラグを遮断する。しかし、Ｄ
ＲＰがＬフラグ・エントリの場合、ＴＶ内のＭフラグ・
フィールドに触れることなく、ＴＶ内のＬフラグ、ＮＴ
Ｕ＃、ＲＰ−ＡＣ−ｐｔｒ、ＲＰをすべて遮断する。そ
の後、ステップ６４で、ＤＲＰ−ＡＣバッファを自由な
ＲＰ−ＡＣバッファ・プールに戻す。これは、ＤＲＰ−
ＡＣバッファを示すように自由なプール内の最後のＲＰ
−ＡＣバッファを更新し、（ＤＲＰ−ＡＣバッファ位置
に等しい）ＡＣバッファ・プール「尾部」ポインタ・レ
ジスタを更新することによって行う。次に、ステップ６
５に示すように、ＴＢ（ＣＴＵ＃）がＴＢ（１）に等し
いか否かを決定する。ＴＢ（ＣＴＵ＃）がＴＢ（１）に
等しい場合、削除プロセスが終了する。
【００５４】それ以外の場合、ＴＢ（ＣＴＵ＃）がＴＢ
（１）に等しくない場合、ステップ６６に示すように、
ＴＢ（ＣＴＵ＃）内の有効なエントリの数を検査する。
検査は、ＴＢ（ＣＴＵ＃）内のすべてのＴＶ内の有効な
エントリの読取り、検査および計数を含む。Ｍフラグ・
エントリ、Ｌフラグ・エントリ、および探索ノード（探
索の継続を知らせるために使用されるエントリ）はすべ
ての有効なエントリである。ステップ６７で、ＴＢ（Ｃ
ＴＵ＃）内にただ１つの有効なエントリが存在するか否
かを決定する。複数の有効なエントリが存在する場合、
削除プロセスは終了する。ただ１つの有効なエントリが
存在する場合、ステップ６８に示すように、次のように
してＴＢ（ＣＴＵ＃）を除去するために探索パスを再経
路指定する。 １．ＴＢ（ＣＴＵ＃）からＲＰ情報を取り出す。 ＲＰがＭフラグである場合：ＮＬ（ＰＲ）＝Ｍ（Ｒ
Ｐ）；ＮＮＴＵ＃＝ＴＵ（ｋ）；ＮＮＴＵ−ｐｔｒ＝Ｍ
ＲＰ−ＡＣ−ＰＴＲ；ＮＲＰ＝（ＲＰ（ＴＵ（ＰＴＵ
＃））＋（Ｍ（ＲＰ）））、ただし、（ＲＰ（ＴＵ（Ｐ
ＴＵ＃））＋（Ｍ（ＲＰ））＝ＴＶ（ＴＵ（ＤＲＰ（Ｐ
ＴＵ＃）））内のＲＰ ＴＵ（ｋ）ビットをＭ（ＲＰ）で置き換える。それ以外
の場合、ＮＬ（ＲＰ）＝Ｌ（ＲＰ）；ＮＮＴＵ＃＝ＮＴ
Ｕ＃；ＮＮＴＵ−ｐｔｒ＝ＮＴＵ−ｐｔｒ；ＮＲＰ＝Ｒ
Ｐ。 ２．ＴＶ（ＴＵ（ＤＲＰ（ＰＴＵ＃）））＝（ｘｘ、Ｎ
Ｌ（ＲＰ）、ＮＮＴＵ＃、ＮＮＴＵ−ｐｔｒ、ＮＲＰ）
を修正する （ＴＢ（ＣＴＵ＃）を探索パスから除去するためにＴＢ
（ＰＴＵ＃）を再経路指定する）。
（１）に等しくない場合、ステップ６６に示すように、
ＴＢ（ＣＴＵ＃）内の有効なエントリの数を検査する。
検査は、ＴＢ（ＣＴＵ＃）内のすべてのＴＶ内の有効な
エントリの読取り、検査および計数を含む。Ｍフラグ・
エントリ、Ｌフラグ・エントリ、および探索ノード（探
索の継続を知らせるために使用されるエントリ）はすべ
ての有効なエントリである。ステップ６７で、ＴＢ（Ｃ
ＴＵ＃）内にただ１つの有効なエントリが存在するか否
かを決定する。複数の有効なエントリが存在する場合、
削除プロセスは終了する。ただ１つの有効なエントリが
存在する場合、ステップ６８に示すように、次のように
してＴＢ（ＣＴＵ＃）を除去するために探索パスを再経
路指定する。 １．ＴＢ（ＣＴＵ＃）からＲＰ情報を取り出す。 ＲＰがＭフラグである場合：ＮＬ（ＰＲ）＝Ｍ（Ｒ
Ｐ）；ＮＮＴＵ＃＝ＴＵ（ｋ）；ＮＮＴＵ−ｐｔｒ＝Ｍ
ＲＰ−ＡＣ−ＰＴＲ；ＮＲＰ＝（ＲＰ（ＴＵ（ＰＴＵ
＃））＋（Ｍ（ＲＰ）））、ただし、（ＲＰ（ＴＵ（Ｐ
ＴＵ＃））＋（Ｍ（ＲＰ））＝ＴＶ（ＴＵ（ＤＲＰ（Ｐ
ＴＵ＃）））内のＲＰ ＴＵ（ｋ）ビットをＭ（ＲＰ）で置き換える。それ以外
の場合、ＮＬ（ＲＰ）＝Ｌ（ＲＰ）；ＮＮＴＵ＃＝ＮＴ
Ｕ＃；ＮＮＴＵ−ｐｔｒ＝ＮＴＵ−ｐｔｒ；ＮＲＰ＝Ｒ
Ｐ。 ２．ＴＶ（ＴＵ（ＤＲＰ（ＰＴＵ＃）））＝（ｘｘ、Ｎ
Ｌ（ＲＰ）、ＮＮＴＵ＃、ＮＮＴＵ−ｐｔｒ、ＮＲＰ）
を修正する （ＴＢ（ＣＴＵ＃）を探索パスから除去するためにＴＢ
（ＰＴＵ＃）を再経路指定する）。
【００５５】最後に、ステップ６９で、ＴＢ（ＣＴＵ
＃）を示すように自由なプール内の最後のＴＢを更新
し、（ＴＢ（ＣＴＵ＃）位置に等しい）ＴＢプール「尾
部」ポインタ・レジスタを更新することによって、削除
したＴＢ（ＣＴＵ＃）を自由なＴＢプールに戻す。これ
で削除プロセスが終了する。
＃）を示すように自由なプール内の最後のＴＢを更新
し、（ＴＢ（ＣＴＵ＃）位置に等しい）ＴＢプール「尾
部」ポインタ・レジスタを更新することによって、削除
したＴＢ（ＣＴＵ＃）を自由なＴＢプールに戻す。これ
で削除プロセスが終了する。
【００５６】次に、図８および図９を参照すると、図７
に示される削除プロセスによる２つの例示的なリファレ
ンス・パターン削除の絵画図が示されている。図示のよ
うに、探索ツリー内には４つのリファレンス・パターン
がある。第２のリファレンス・パターン（ＲＰ２）は、
次のようにして探索ツリーから削除される。 １．ＲＰ２を探索する（ＲＰ２はＴＵ（１）内にある） ２．ＴＢ（１）内のＲＰ２のＴＶを遮断する ３．ＲＰ２ＡＣバッファを自由なＴＵプールに戻す ４．削除の終了。 同様に、第４のリファレンス・パターン（ＲＰ４）は、
次のようにして探索ツリーから削除される。 １．ＲＰ４を探索する（ＲＰ４はＴＵ（５）内にある） ２．ＴＢ（５）内のＲＰ４のＴＶを遮断する ３．ＲＰ２ＡＣバッファを自由なＴＵプールに戻す ４．有効なエントリについてＴＵ（５）を検査する（Ｔ
Ｕ（５）内のただ一つの有効なエントリ（ＲＰ１）） ５．（ＴＵ（７）を示す）探索パスを再経路指定するた
めにＴＵ（１）内のＲＰ４のＴＶを修正する ６．ＴＵ（５）を自由なＴＵプールに戻す ７．削除の終了。
に示される削除プロセスによる２つの例示的なリファレ
ンス・パターン削除の絵画図が示されている。図示のよ
うに、探索ツリー内には４つのリファレンス・パターン
がある。第２のリファレンス・パターン（ＲＰ２）は、
次のようにして探索ツリーから削除される。 １．ＲＰ２を探索する（ＲＰ２はＴＵ（１）内にある） ２．ＴＢ（１）内のＲＰ２のＴＶを遮断する ３．ＲＰ２ＡＣバッファを自由なＴＵプールに戻す ４．削除の終了。 同様に、第４のリファレンス・パターン（ＲＰ４）は、
次のようにして探索ツリーから削除される。 １．ＲＰ４を探索する（ＲＰ４はＴＵ（５）内にある） ２．ＴＢ（５）内のＲＰ４のＴＶを遮断する ３．ＲＰ２ＡＣバッファを自由なＴＵプールに戻す ４．有効なエントリについてＴＵ（５）を検査する（Ｔ
Ｕ（５）内のただ一つの有効なエントリ（ＲＰ１）） ５．（ＴＵ（７）を示す）探索パスを再経路指定するた
めにＴＵ（１）内のＲＰ４のＴＶを修正する ６．ＴＵ（５）を自由なＴＵプールに戻す ７．削除の終了。
【００５７】リファレンス・パターン一致プロセス次
に、図１０を参照すると、本発明の好ましい実施形態に
よる探索ツリー内でリファレンス・パターンを一致させ
る方法のハイレベル論理流れ図が示されている。ステッ
プ８１で、ＴＰの最初のＴＵ（すなわち、受信アドレ
ス）をデコードとして使用して、所定の位置のところで
最初のＴＢ内のＴＶを読み取る。異なるプロトコルは異
なる探索ツリーから始まるので、所定の開始位置は、受
信アドレスのプロトコルに依存する。次いで、ステップ
８２に示すように、可能な一致するＲＰについてＴＶを
検査する。一致するＲＰを次に示す。 １．Ｍフラグ ２．Ｌフラグ＋正確に一致するＴＰおよびＲＰのＴＳ
（ＮＴＵ＃）ビット・パターン、ただし、ＴＳ（ＮＴＵ
＃）＝（ＴＵ（１）からＴＵ（ＮＴＵ＃）までのビット
・パターン） 一致するＲＰが存在する場合、ステップ８３に示すよう
に、すべての一致するＲＰ情報およびそれらのアクショ
ン・コード・ポインタ（すなわち、Ｍ、Ｌ、ＭｘＡＣ
ｐｔｒ）を連続的に記録（または保管）する。
に、図１０を参照すると、本発明の好ましい実施形態に
よる探索ツリー内でリファレンス・パターンを一致させ
る方法のハイレベル論理流れ図が示されている。ステッ
プ８１で、ＴＰの最初のＴＵ（すなわち、受信アドレ
ス）をデコードとして使用して、所定の位置のところで
最初のＴＢ内のＴＶを読み取る。異なるプロトコルは異
なる探索ツリーから始まるので、所定の開始位置は、受
信アドレスのプロトコルに依存する。次いで、ステップ
８２に示すように、可能な一致するＲＰについてＴＶを
検査する。一致するＲＰを次に示す。 １．Ｍフラグ ２．Ｌフラグ＋正確に一致するＴＰおよびＲＰのＴＳ
（ＮＴＵ＃）ビット・パターン、ただし、ＴＳ（ＮＴＵ
＃）＝（ＴＵ（１）からＴＵ（ＮＴＵ＃）までのビット
・パターン） 一致するＲＰが存在する場合、ステップ８３に示すよう
に、すべての一致するＲＰ情報およびそれらのアクショ
ン・コード・ポインタ（すなわち、Ｍ、Ｌ、ＭｘＡＣ
ｐｔｒ）を連続的に記録（または保管）する。
【００５８】ステップ８４で、他のＲＰの探索を継続す
べきかどうかを決定する。（ＴＵ（ＴＰ）＞ＮＴＵ＃＞
ＣＴＵ＃）かつ（ＴＰ（ＴＳ（ＮＴＵ＃−１））＝ＲＰ
（ＴＳ（ＮＴＵ＃−１）））かつＬフラグがない場合、
プロセスはステップ８５に進む。（ＴＰ（ＴＳ（ｘ））
＝ＲＰ（ＴＳ（ｘ））：ＴＰとＲＰの間で一致するＴＵ
（１）からＴＵ（ｘ）までのビット・パターン）。ステ
ップ８５で、次のＴＢのＴＶを読み取り、ＴＢポインタ
＝Ｎ−ＴＵ−ｐｔｒ、ＴＶオフセット＝ＴＰの（ＴＵ
（Ｎ−ＴＵ＃）ビット・パターン・デコードとなり、プ
ロセスはステップ８２に戻る。
べきかどうかを決定する。（ＴＵ（ＴＰ）＞ＮＴＵ＃＞
ＣＴＵ＃）かつ（ＴＰ（ＴＳ（ＮＴＵ＃−１））＝ＲＰ
（ＴＳ（ＮＴＵ＃−１）））かつＬフラグがない場合、
プロセスはステップ８５に進む。（ＴＰ（ＴＳ（ｘ））
＝ＲＰ（ＴＳ（ｘ））：ＴＰとＲＰの間で一致するＴＵ
（１）からＴＵ（ｘ）までのビット・パターン）。ステ
ップ８５で、次のＴＢのＴＶを読み取り、ＴＢポインタ
＝Ｎ−ＴＵ−ｐｔｒ、ＴＶオフセット＝ＴＰの（ＴＵ
（Ｎ−ＴＵ＃）ビット・パターン・デコードとなり、プ
ロセスはステップ８２に戻る。
【００５９】それ以外の場合、探索ツリーの終了である
ので、他のＲＰの探索は継続しない。探索ツリーの終了
は次の場合である。 １．（ＴＵ（ＴＰ）またはＮＴＵ＃）がＣＴＵ＃に等し
いかまたはそれよりも小さい場合 ２．ＮＴＵ＃がＴＵ（ＴＰ）よりも大きい場合（ＴＵ
（ＴＰ）＝ＴＰパターンの長さ） ３．Ｌフラグ・エントリに到達した場合 ４．ＴＰとＲＰの間のＴＵ（１）からＴＵ（ＮＴＵ＃−
１）までのビット・パターンが一致しない場合 ５．不法状態の場合。 ステップ８６で、ＲＰアクション・コードをフレーム処
理エンジンにソート／転送する。これでＲＰ一致プロセ
スが完了する。
ので、他のＲＰの探索は継続しない。探索ツリーの終了
は次の場合である。 １．（ＴＵ（ＴＰ）またはＮＴＵ＃）がＣＴＵ＃に等し
いかまたはそれよりも小さい場合 ２．ＮＴＵ＃がＴＵ（ＴＰ）よりも大きい場合（ＴＵ
（ＴＰ）＝ＴＰパターンの長さ） ３．Ｌフラグ・エントリに到達した場合 ４．ＴＰとＲＰの間のＴＵ（１）からＴＵ（ＮＴＵ＃−
１）までのビット・パターンが一致しない場合 ５．不法状態の場合。 ステップ８６で、ＲＰアクション・コードをフレーム処
理エンジンにソート／転送する。これでＲＰ一致プロセ
スが完了する。
【００６０】次に、図１１を参照すると、本発明の好ま
しい実施形態が使用される高性能スイッチ・ルータのブ
ロック図が示されている。図示のように、スイッチ・ル
ータ９０は、中央演算処理装置（ＣＰＵ）９１、適応フ
レーム・ヘッダ分解／処理装置（ＡＦＰＵ）９２、ラン
ダム・アクセス・メモリ（ＲＡＭ）の第１のバンク９
３、ＲＡＭの第２のバンク９４、およびスイッチ装置９
５を含んでいる。
しい実施形態が使用される高性能スイッチ・ルータのブ
ロック図が示されている。図示のように、スイッチ・ル
ータ９０は、中央演算処理装置（ＣＰＵ）９１、適応フ
レーム・ヘッダ分解／処理装置（ＡＦＰＵ）９２、ラン
ダム・アクセス・メモリ（ＲＡＭ）の第１のバンク９
３、ＲＡＭの第２のバンク９４、およびスイッチ装置９
５を含んでいる。
【００６１】ＣＰＵ９１は、スイッチ・ルータ９０内の
すべての標準の動作を制御するだけでなく、プロトコル
関連処理を管理し、フレーム転送テーブルを設定する。
ＡＦＰＵ９２は、ＣＰＵ９１によって与えられた各リフ
ァレンス・パターンを学習し、次いで上述の好ましい方
法に従ってリファレンス・パターンのフレーム・ヘッダ
を分解する。ＡＦＰＵ９２は、分解結果を使用して、フ
レームをフィルタリングし、転送し、再送信の前にフレ
ームを修正する。すべての着信データ・フレームは、Ａ
ＦＰＵ９２内に記憶されたの先入れ先出しバッファかま
たはＲＡＭ９３、９４の一方においてバッファされ、再
送信の前に処理が完了するのを待つ。システム・パフォ
ーマンスおよびパイプライン設計を高めるために、２つ
のＲＡＭ、ＲＡＭ９３および９４がスイッチ・ルータ９
０内で使用される。ＲＡＭ９３、９４は、ＡＦＰＵ９２
によって管理される。フレーム転送アドレス・テーブル
およびポインタは、ＲＡＭ９３、９４の一方に記憶さ
れ、フレーム処理記述子およびバッファされた受信フレ
ームは他方のＲＡＭに記憶される。ＬＡＮ／ＷＡＮ／Ａ
ＴＭコントローラなど、スイッチ装置９５は、フレーム
転送処理のためにＡＦＰＵ９２との間でフレームを供給
するために使用される。
すべての標準の動作を制御するだけでなく、プロトコル
関連処理を管理し、フレーム転送テーブルを設定する。
ＡＦＰＵ９２は、ＣＰＵ９１によって与えられた各リフ
ァレンス・パターンを学習し、次いで上述の好ましい方
法に従ってリファレンス・パターンのフレーム・ヘッダ
を分解する。ＡＦＰＵ９２は、分解結果を使用して、フ
レームをフィルタリングし、転送し、再送信の前にフレ
ームを修正する。すべての着信データ・フレームは、Ａ
ＦＰＵ９２内に記憶されたの先入れ先出しバッファかま
たはＲＡＭ９３、９４の一方においてバッファされ、再
送信の前に処理が完了するのを待つ。システム・パフォ
ーマンスおよびパイプライン設計を高めるために、２つ
のＲＡＭ、ＲＡＭ９３および９４がスイッチ・ルータ９
０内で使用される。ＲＡＭ９３、９４は、ＡＦＰＵ９２
によって管理される。フレーム転送アドレス・テーブル
およびポインタは、ＲＡＭ９３、９４の一方に記憶さ
れ、フレーム処理記述子およびバッファされた受信フレ
ームは他方のＲＡＭに記憶される。ＬＡＮ／ＷＡＮ／Ａ
ＴＭコントローラなど、スイッチ装置９５は、フレーム
転送処理のためにＡＦＰＵ９２との間でフレームを供給
するために使用される。
【００６２】上述のように、本発明は、コンピュータ・
ネットワーク内でデータ・フレームを経路指定するフレ
ーム・ヘッダを分解する改善された方法を開示する。開
示の方法は、探索ツリー構造およびビットパターン一致
技法を使用して、フレーム・ヘッダを分解する。本発明
による分解方法は３つの独自の特性を有する。第１に、
学習した各リファレンス・パターンごとに一意の探索パ
スが存在することが保証される。第２に、探索ツリー
は、可変のビット長さのリファレンス・パターンを記憶
することができる。第３に、長さが変化しかつ同じビッ
ト・パターンを有する複数のリファレンス・パターン
は、探索が終了する前に探索パス内でそれに応じてマー
クされる。
ネットワーク内でデータ・フレームを経路指定するフレ
ーム・ヘッダを分解する改善された方法を開示する。開
示の方法は、探索ツリー構造およびビットパターン一致
技法を使用して、フレーム・ヘッダを分解する。本発明
による分解方法は３つの独自の特性を有する。第１に、
学習した各リファレンス・パターンごとに一意の探索パ
スが存在することが保証される。第２に、探索ツリー
は、可変のビット長さのリファレンス・パターンを記憶
することができる。第３に、長さが変化しかつ同じビッ
ト・パターンを有する複数のリファレンス・パターン
は、探索が終了する前に探索パス内でそれに応じてマー
クされる。
【００６３】以上、本発明について、特に好ましい実施
形態に関して図示し、説明したが、本発明の主旨および
範囲から逸脱することなく形態および詳細の様々な変更
を本発明に加えることができることを当業者なら理解で
きよう。
形態に関して図示し、説明したが、本発明の主旨および
範囲から逸脱することなく形態および詳細の様々な変更
を本発明に加えることができることを当業者なら理解で
きよう。
【００６４】まとめとして、本発明の構成に関して以下
の事項を開示する。
の事項を開示する。
【００６５】（１）コンピュータ・ネットワーク内でデ
ータ・フレームを経路指定するフレーム・ヘッダを解析
する方法であって、前記コンピュータ・ネットワークか
らデータ・フレームを受信するステップと、前記データ
・フレームのフレーム・ヘッダをすべて同じ長さを有す
る複数のテスト・ユニットに分解するステップと、前記
複数のテスト・ユニットの各テスト・ユニットにそれぞ
れリファレンス・パターン・フィールドおよびアクショ
ン・コード・ポインタ・フィールドを含むテスト・ベク
トルを割り当てるステップと、各前記テスト・ベクトル
を複数のテスト・ブロックの対応するスロットに挿入す
ることによって前記複数のテスト・ブロックを構成する
ステップと、前記テスト・ベクトルによって互いに関連
づけられた前記複数のテスト・ブロックを使用して、探
索ツリーを構成するステップとを含む方法。 （２）前記分解ステップが、前記フレーム・ヘッダを複
数の２ビット・テスト・ユニットに分解するステップを
さらに含むことを特徴とする、上記（１）に記載の方
法。 （３）前記割当てステップが、各前記テスト・ユニット
にテスト・ベクトルをビット・パターンに従って割り当
てるステップをさらに含むことを特徴とする、上記
（１）に記載の方法。 （４）前記挿入ステップが、各前記テスト・ユニットの
サイズによって制限されるスロットの数選択からテスト
・ブロックの対応するスロットにテスト・ベクトルを挿
入するステップをさらに含むことを特徴とする、上記
（１）に記載の方法。 （５）前記探索ツリーを構成するステップが、異なる通
信プロトコルを有する受信したデータ・フレーム用の別
個の探索ツリーを構成するステップをさらに含むことを
特徴とする、上記（１）に記載の方法。 （６）前記フレーム・ヘッドに一致する前記リファレン
ス・パターン・フィールド内にリファレンス・パターン
を有する前記複数のテスト・ベクトルの１つのテスト・
ベクトル内の前記アクション・コード・フィールド内の
アクション・コードに従って、前記データ・フレームを
前記コンピュータ・ネットワーク内のノードに経路指定
するステップをさらに含むことを特徴とする、上記
（１）に記載の方法。 （７）コンピュータ・ネットワーク内でデータ・フレー
ムを経路指定するデータ処理システムであって、前記コ
ンピュータ・ネットワークからデータ・フレームを受信
する手段と、前記データ・フレームのフレーム・ヘッダ
をすべて同じ長さを有する複数のテスト・ユニットに分
解する手段と、前記複数のテスト・ユニットの各テスト
・ユニットにそれぞれリファレンス・パターン・フィー
ルドおよびアクション・コード・ポインタ・フィールド
を含むテスト・ベクトルを割り当てる手段と、そのうち
のいくつかが前記テスト・ベクトルの１つを含む複数の
スロットをそれぞれ含む複数のテスト・ブロックと、前
記テスト・ベクトルによって互いに関連づけられた前記
複数のテスト・ブロックによって構成された探索ツリー
とを含むデータ処理システム。 （８）前記複数のテスト・ユニットのうちの各テスト・
ユニットが長さ２ビットであることを特徴とする、上記
（７）に記載のデータ処理システム。 （９）前記割当て手段が、各前記テスト・ユニットにテ
スト・ベクトルをビット・パターンに従って割り当てる
手段をさらに含むことを特徴とする、上記（７）に記載
のデータ処理システム。 （１０）前記テスト・ベクトルが、各前記テスト・ユニ
ットのサイズによって制限されるスロットの数選択から
テスト・ブロックの対応するスロットに挿入されること
を特徴とする、上記（７）に記載のデータ処理システ
ム。 （１１）異なる通信プロトコルを有する受信したデータ
・フレーム用の別個の探索ツリーをさらに含むことを特
徴とする、上記（７）に記載のデータ処理システム。 （１２）前記フレーム・ヘッドに一致する前記リファレ
ンス・パターン・フィールド内に記憶されたリファレン
ス・パターンを有する前記複数のテスト・ベクトルの１
つのテスト・ベクトル内の前記アクション・コード・フ
ィールド内に記憶されたアクション・コードに従って、
前記データ・フレームを前記コンピュータ・ネットワー
ク内のノードに経路指定する手段をさらに含むことを特
徴とする、上記（７）に記載のデータ処理システム。
ータ・フレームを経路指定するフレーム・ヘッダを解析
する方法であって、前記コンピュータ・ネットワークか
らデータ・フレームを受信するステップと、前記データ
・フレームのフレーム・ヘッダをすべて同じ長さを有す
る複数のテスト・ユニットに分解するステップと、前記
複数のテスト・ユニットの各テスト・ユニットにそれぞ
れリファレンス・パターン・フィールドおよびアクショ
ン・コード・ポインタ・フィールドを含むテスト・ベク
トルを割り当てるステップと、各前記テスト・ベクトル
を複数のテスト・ブロックの対応するスロットに挿入す
ることによって前記複数のテスト・ブロックを構成する
ステップと、前記テスト・ベクトルによって互いに関連
づけられた前記複数のテスト・ブロックを使用して、探
索ツリーを構成するステップとを含む方法。 （２）前記分解ステップが、前記フレーム・ヘッダを複
数の２ビット・テスト・ユニットに分解するステップを
さらに含むことを特徴とする、上記（１）に記載の方
法。 （３）前記割当てステップが、各前記テスト・ユニット
にテスト・ベクトルをビット・パターンに従って割り当
てるステップをさらに含むことを特徴とする、上記
（１）に記載の方法。 （４）前記挿入ステップが、各前記テスト・ユニットの
サイズによって制限されるスロットの数選択からテスト
・ブロックの対応するスロットにテスト・ベクトルを挿
入するステップをさらに含むことを特徴とする、上記
（１）に記載の方法。 （５）前記探索ツリーを構成するステップが、異なる通
信プロトコルを有する受信したデータ・フレーム用の別
個の探索ツリーを構成するステップをさらに含むことを
特徴とする、上記（１）に記載の方法。 （６）前記フレーム・ヘッドに一致する前記リファレン
ス・パターン・フィールド内にリファレンス・パターン
を有する前記複数のテスト・ベクトルの１つのテスト・
ベクトル内の前記アクション・コード・フィールド内の
アクション・コードに従って、前記データ・フレームを
前記コンピュータ・ネットワーク内のノードに経路指定
するステップをさらに含むことを特徴とする、上記
（１）に記載の方法。 （７）コンピュータ・ネットワーク内でデータ・フレー
ムを経路指定するデータ処理システムであって、前記コ
ンピュータ・ネットワークからデータ・フレームを受信
する手段と、前記データ・フレームのフレーム・ヘッダ
をすべて同じ長さを有する複数のテスト・ユニットに分
解する手段と、前記複数のテスト・ユニットの各テスト
・ユニットにそれぞれリファレンス・パターン・フィー
ルドおよびアクション・コード・ポインタ・フィールド
を含むテスト・ベクトルを割り当てる手段と、そのうち
のいくつかが前記テスト・ベクトルの１つを含む複数の
スロットをそれぞれ含む複数のテスト・ブロックと、前
記テスト・ベクトルによって互いに関連づけられた前記
複数のテスト・ブロックによって構成された探索ツリー
とを含むデータ処理システム。 （８）前記複数のテスト・ユニットのうちの各テスト・
ユニットが長さ２ビットであることを特徴とする、上記
（７）に記載のデータ処理システム。 （９）前記割当て手段が、各前記テスト・ユニットにテ
スト・ベクトルをビット・パターンに従って割り当てる
手段をさらに含むことを特徴とする、上記（７）に記載
のデータ処理システム。 （１０）前記テスト・ベクトルが、各前記テスト・ユニ
ットのサイズによって制限されるスロットの数選択から
テスト・ブロックの対応するスロットに挿入されること
を特徴とする、上記（７）に記載のデータ処理システ
ム。 （１１）異なる通信プロトコルを有する受信したデータ
・フレーム用の別個の探索ツリーをさらに含むことを特
徴とする、上記（７）に記載のデータ処理システム。 （１２）前記フレーム・ヘッドに一致する前記リファレ
ンス・パターン・フィールド内に記憶されたリファレン
ス・パターンを有する前記複数のテスト・ベクトルの１
つのテスト・ベクトル内の前記アクション・コード・フ
ィールド内に記憶されたアクション・コードに従って、
前記データ・フレームを前記コンピュータ・ネットワー
ク内のノードに経路指定する手段をさらに含むことを特
徴とする、上記（７）に記載のデータ処理システム。
【図１】本発明が使用される代表的なコンピュータ・ネ
ットワークのブロック図である。
ットワークのブロック図である。
【図２】図１のネットワーク内でデータ・フレームを経
路指定する従来技術の方法のハイレベル論理流れ図であ
る。
路指定する従来技術の方法のハイレベル論理流れ図であ
る。
【図３】本発明の好ましい実施形態による２つのテスト
・ベクトルのブロック図である。
・ベクトルのブロック図である。
【図４】本発明の好ましい実施形態によるリファレンス
・パターンを学習する方法のハイレベル論理流れ図であ
る。
・パターンを学習する方法のハイレベル論理流れ図であ
る。
【図５】図４に示される学習プロセスによる複数の例示
的なリファレンス・パターン挿入の絵画図である。
的なリファレンス・パターン挿入の絵画図である。
【図６】図４に示される学習プロセスによる複数の例示
的なリファレンス・パターン挿入の絵画図である。
的なリファレンス・パターン挿入の絵画図である。
【図７】本発明の好ましい実施形態による探索ツリーか
らリファレンス・パターンを削除する方法のハイレベル
論理流れ図である。
らリファレンス・パターンを削除する方法のハイレベル
論理流れ図である。
【図８】図７に示される削除プロセスによる２つの例示
的なリファレンス・パターン削除の絵画図である。
的なリファレンス・パターン削除の絵画図である。
【図９】図７に示される削除プロセスによる２つの例示
的なリファレンス・パターン削除の絵画図である。
的なリファレンス・パターン削除の絵画図である。
【図１０】本発明の好ましい実施形態による探索ツリー
内でリファレンス・パターンを一致させる方法のハイレ
ベル論理流れ図である。
内でリファレンス・パターンを一致させる方法のハイレ
ベル論理流れ図である。
【図１１】本発明の好ましい実施形態が使用される高性
能スイッチ・ルータのブロック図である。
能スイッチ・ルータのブロック図である。
１０ ＬＡＮ １１ ＬＡＮ １２ ＬＡＮ ３１ マスク・リファレンス・パターン・マーカ（Ｍ）
フィールド ３２ 最後のテスト・ベクトル（Ｌ） ３３ ＮＴＵ＃フィールド ３４ ＮＴＢ ＰＴＲフィールド ３５ リファレンス・パターン（ＲＰ）フィールド ３６ ＡＣ ＰＴＲフィールド ３８ テスト・ベクトル ３９ テスト・ベクトル ９０ スイッチ・ルータ ９１ 中央演算処理装置（ＣＰＵ） ９２ 適応フレーム・ヘッダ分解／処理装置（ＡＦＰ
Ｕ） ９３ ランダム・アクセス・メモリ（ＲＡＭ）の第１の
バンク ９４ ＲＡＭの第２のバンク ９５ スイッチ装置 １００ コンピュータ・ネットワーク １０１ サーバ １０２ ルータ １１１ ノード １１２ ノード １１３ ノード １１４ ノード １１５ ノード １１６ ノード １１７ ノード １１８ ノード １１９ ノード １２０ ノード
フィールド ３２ 最後のテスト・ベクトル（Ｌ） ３３ ＮＴＵ＃フィールド ３４ ＮＴＢ ＰＴＲフィールド ３５ リファレンス・パターン（ＲＰ）フィールド ３６ ＡＣ ＰＴＲフィールド ３８ テスト・ベクトル ３９ テスト・ベクトル ９０ スイッチ・ルータ ９１ 中央演算処理装置（ＣＰＵ） ９２ 適応フレーム・ヘッダ分解／処理装置（ＡＦＰ
Ｕ） ９３ ランダム・アクセス・メモリ（ＲＡＭ）の第１の
バンク ９４ ＲＡＭの第２のバンク ９５ スイッチ装置 １００ コンピュータ・ネットワーク １０１ サーバ １０２ ルータ １１１ ノード １１２ ノード １１３ ノード １１４ ノード １１５ ノード １１６ ノード １１７ ノード １１８ ノード １１９ ノード １２０ ノード
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジェームズ・フィリップ・アーヴィン アメリカ合衆国27613 ノースカイライナ 州ローリー カノネーロ・プレース 11804 (72)発明者 ダグラス・レイ・ヘンダーソン アメリカ合衆国27613 ノースカイライナ 州ローリー クィンビー・コート 7300 (72)発明者 リチャード・コルバート・マトラック・ジ ュニア アメリカ合衆国27613 ノースカイライナ 州ローリー ブッシュフェルド・レーン 10005 (72)発明者 ジーン・フェイ・ウィングラー アメリカ合衆国27502 ノースカイライナ 州アペックス ウィックフォード・プレー ス 4205
Claims (12)
- 【請求項１】コンピュータ・ネットワーク内でデータ・
フレームを経路指定するフレーム・ヘッダを解析する方
法であって、 前記コンピュータ・ネットワークからデータ・フレーム
を受信するステップと、 前記データ・フレームのフレーム・ヘッダをすべて同じ
長さを有する複数のテスト・ユニットに分解するステッ
プと、 前記複数のテスト・ユニットの各テスト・ユニットにそ
れぞれリファレンス・パターン・フィールドおよびアク
ション・コード・ポインタ・フィールドを含むテスト・
ベクトルを割り当てるステップと、 各前記テスト・ベクトルを複数のテスト・ブロックの対
応するスロットに挿入することによって前記複数のテス
ト・ブロックを構成するステップと、 前記テスト・ベクトルによって互いに関連づけられた前
記複数のテスト・ブロックを使用して、探索ツリーを構
成するステップとを含む方法。 - 【請求項２】前記分解ステップが、前記フレーム・ヘッ
ダを複数の２ビット・テスト・ユニットに分解するステ
ップをさらに含むことを特徴とする、請求項１に記載の
方法。 - 【請求項３】前記割当てステップが、各前記テスト・ユ
ニットにテスト・ベクトルをビット・パターンに従って
割り当てるステップをさらに含むことを特徴とする、請
求項１に記載の方法。 - 【請求項４】前記挿入ステップが、各前記テスト・ユニ
ットのサイズによって制限されるスロットの数選択から
テスト・ブロックの対応するスロットにテスト・ベクト
ルを挿入するステップをさらに含むことを特徴とする、
請求項１に記載の方法。 - 【請求項５】前記探索ツリーを構成するステップが、異
なる通信プロトコルを有する受信したデータ・フレーム
用の別個の探索ツリーを構成するステップをさらに含む
ことを特徴とする、請求項１に記載の方法。 - 【請求項６】前記フレーム・ヘッドに一致する前記リフ
ァレンス・パターン・フィールド内にリファレンス・パ
ターンを有する前記複数のテスト・ベクトルの１つのテ
スト・ベクトル内の前記アクション・コード・フィール
ド内のアクション・コードに従って、前記データ・フレ
ームを前記コンピュータ・ネットワーク内のノードに経
路指定するステップをさらに含むことを特徴とする、請
求項１に記載の方法。 - 【請求項７】コンピュータ・ネットワーク内でデータ・
フレームを経路指定するデータ処理システムであって、 前記コンピュータ・ネットワークからデータ・フレーム
を受信する手段と、 前記データ・フレームのフレーム・ヘッダをすべて同じ
長さを有する複数のテスト・ユニットに分解する手段
と、 前記複数のテスト・ユニットの各テスト・ユニットにそ
れぞれリファレンス・パターン・フィールドおよびアク
ション・コード・ポインタ・フィールドを含むテスト・
ベクトルを割り当てる手段と、 そのうちのいくつかが前記テスト・ベクトルの１つを含
む複数のスロットをそれぞれ含む複数のテスト・ブロッ
クと、 前記テスト・ベクトルによって互いに関連づけられた前
記複数のテスト・ブロックによって構成された探索ツリ
ーとを含むデータ処理システム。 - 【請求項８】前記複数のテスト・ユニットのうちの各テ
スト・ユニットが長さ２ビットであることを特徴とす
る、請求項７に記載のデータ処理システム。 - 【請求項９】前記割当て手段が、各前記テスト・ユニッ
トにテスト・ベクトルをビット・パターンに従って割り
当てる手段をさらに含むことを特徴とする、請求項７に
記載のデータ処理システム。 - 【請求項１０】前記テスト・ベクトルが、各前記テスト
・ユニットのサイズによって制限されるスロットの数選
択からテスト・ブロックの対応するスロットに挿入され
ることを特徴とする、請求項７に記載のデータ処理シス
テム。 - 【請求項１１】異なる通信プロトコルを有する受信した
データ・フレーム用の別個の探索ツリーをさらに含むこ
とを特徴とする、請求項７に記載のデータ処理システ
ム。 - 【請求項１２】前記フレーム・ヘッドに一致する前記リ
ファレンス・パターン・フィールド内に記憶されたリフ
ァレンス・パターンを有する前記複数のテスト・ベクト
ルの１つのテスト・ベクトル内の前記アクション・コー
ド・フィールド内に記憶されたアクション・コードに従
って、前記データ・フレームを前記コンピュータ・ネッ
トワーク内のノードに経路指定する手段をさらに含むこ
とを特徴とする、請求項７に記載のデータ処理システ
ム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/780803 | 1997-01-09 | ||
| US08/780,803 US5881242A (en) | 1997-01-09 | 1997-01-09 | Method and system of parsing frame headers for routing data frames within a computer network |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH10257084A true JPH10257084A (ja) | 1998-09-25 |
Family
ID=25120745
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10001502A Pending JPH10257084A (ja) | 1997-01-09 | 1998-01-07 | コンピュータ・ネットワーク内でデータ・フレームを経路指定するフレーム・ヘッダを解析する方法およびシステム |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5881242A (ja) |
| JP (1) | JPH10257084A (ja) |
Families Citing this family (26)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6393548B1 (en) * | 1997-02-14 | 2002-05-21 | Advanced Micro Devices, Inc. | Variable 16 or 32 bit PCI interface which supports steering and swapping of data |
| US6401171B1 (en) | 1998-02-27 | 2002-06-04 | Cisco Technology, Inc. | Method and device for storing an IP header in a cache memory of a network node |
| US6098125A (en) * | 1998-05-01 | 2000-08-01 | California Institute Of Technology | Method of mapping fibre channel frames based on control and type header fields |
| US6897073B2 (en) * | 1998-07-14 | 2005-05-24 | Zyomyx, Inc. | Non-specific binding resistant protein arrays and methods for making the same |
| US6611524B2 (en) | 1999-06-30 | 2003-08-26 | Cisco Technology, Inc. | Programmable data packet parser |
| DE19938895C1 (de) * | 1999-08-17 | 2001-03-29 | Siemens Ag | Verfahren zum Aufbau einer Signalisierungsverbindung |
| AU4022301A (en) * | 1999-09-22 | 2001-04-24 | Entridia Corporation | Serial routing bus |
| AUPQ312299A0 (en) * | 1999-09-27 | 1999-10-21 | Canon Kabushiki Kaisha | Method and system for addressing audio-visual content fragments |
| AU2098800A (en) * | 1999-12-17 | 2001-06-25 | Nokia Corporation | A method for contention free traffic detection |
| US6970462B1 (en) | 2000-04-24 | 2005-11-29 | Cisco Technology, Inc. | Method for high speed packet classification |
| US6714985B1 (en) | 2000-04-28 | 2004-03-30 | Cisco Technology, Inc. | Method and apparatus for efficiently reassembling fragments received at an intermediate station in a computer network |
| US20020126673A1 (en) * | 2001-01-12 | 2002-09-12 | Nirav Dagli | Shared memory |
| US6735649B2 (en) * | 2001-05-03 | 2004-05-11 | Advanced Micro Devices, Inc. | Multiple buffers for removing unwanted header information from received data packets |
| US7154888B1 (en) | 2002-02-08 | 2006-12-26 | Cisco Technology, Inc. | Method for classifying packets using multi-class structures |
| US7236493B1 (en) | 2002-06-13 | 2007-06-26 | Cisco Technology, Inc. | Incremental compilation for classification and filtering rules |
| US7894480B1 (en) * | 2002-08-27 | 2011-02-22 | Hewlett-Packard Company | Computer system and network interface with hardware based rule checking for embedded firewall |
| US7724740B1 (en) | 2002-08-27 | 2010-05-25 | 3Com Corporation | Computer system and network interface supporting class of service queues |
| US7328463B2 (en) * | 2003-09-08 | 2008-02-12 | Microtek Medical Holdings, Inc. | Water-soluble articles and methods of making and using the same |
| US20060249716A1 (en) * | 2003-10-30 | 2006-11-09 | Rincoe Richard G | Method of maneuvering a mechanical arm assembly relative to a base support |
| US7317723B1 (en) | 2004-02-03 | 2008-01-08 | Cisco Technology, Inc. | Action based termination of multidimensional lookup |
| US7646771B2 (en) | 2005-08-17 | 2010-01-12 | Cisco Technology, Inc. | Compilation of access control lists |
| US7325074B2 (en) * | 2005-09-28 | 2008-01-29 | Cisco Technology, Inc. | Incremental compilation of packet classifications using fragmented tables |
| US10193788B2 (en) * | 2014-12-19 | 2019-01-29 | Disrupter LLC | Systems and methods implementing an autonomous network architecture and protocol |
| US10148576B2 (en) * | 2016-07-28 | 2018-12-04 | Fortinet, Inc. | Network processing unit (NPU) integrated layer 2 network device for layer 3 offloading |
| US9972360B2 (en) * | 2016-08-30 | 2018-05-15 | Oath Inc. | Computerized system and method for automatically generating high-quality digital content thumbnails from digital video |
| US12339770B2 (en) * | 2023-10-10 | 2025-06-24 | International Business Machines Corporation | Storage of threshold voltage shifts |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3979733A (en) * | 1975-05-09 | 1976-09-07 | Bell Telephone Laboratories, Incorporated | Digital data communications system packet switch |
| US5038345A (en) * | 1989-10-30 | 1991-08-06 | Amp Incorporated | Traffic pattern information for a local area network |
| US5191582A (en) * | 1991-08-14 | 1993-03-02 | Transwitch Corporation | Method and apparatus for the high speed modification of a packet address field of a transmitted packet in a frame relay system |
| US5251215A (en) * | 1992-01-13 | 1993-10-05 | At&T Bell Laboratories | Modifying check codes in data packet transmission |
| US5469150A (en) * | 1992-12-18 | 1995-11-21 | Honeywell Inc. | Sensor actuator bus system |
| US5793954A (en) * | 1995-12-20 | 1998-08-11 | Nb Networks | System and method for general purpose network analysis |
-
1997
- 1997-01-09 US US08/780,803 patent/US5881242A/en not_active Expired - Lifetime
-
1998
- 1998-01-07 JP JP10001502A patent/JPH10257084A/ja active Pending
Also Published As
| Publication number | Publication date |
|---|---|
| US5881242A (en) | 1999-03-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH10257084A (ja) | コンピュータ・ネットワーク内でデータ・フレームを経路指定するフレーム・ヘッダを解析する方法およびシステム | |
| EP1358739B1 (en) | Method and apparatus for routing table management | |
| CN100465947C (zh) | 用于产生和使用改进的树形位图数据结构的方法和装置 | |
| US7415463B2 (en) | Programming tree data structures and handling collisions while performing lookup operations | |
| US7415472B2 (en) | Comparison tree data structures of particular use in performing lookup operations | |
| US7433871B2 (en) | Efficient ipv4/ipv6 best matching prefix method and apparatus | |
| US8538999B2 (en) | String lookup using three-transition tree structure | |
| CA2274962C (en) | High speed variable length best match look-up in a switching device | |
| US20050021752A1 (en) | Reverse path forwarding protection of packets using automated population of access control lists based on a forwarding information base | |
| US20050141519A1 (en) | Apparatus and method using hashing for efficiently implementing an IP lookup solution in hardware | |
| JP2003196295A (ja) | ツリー型知識ベース検索のルックアップ・パフォーマンスを向上させる方法 | |
| US6532516B1 (en) | Technique for updating a content addressable memory | |
| US6590898B1 (en) | Method and apparatus for routing data packets | |
| US20030023581A1 (en) | Method and system for performing a longest prefix match search | |
| US7809008B2 (en) | Methods and apparatus for routing packets | |
| US7154892B2 (en) | Method and apparatus for managing LPM-based CAM look-up table, and recording medium therefor | |
| JP3198547B2 (ja) | 受信装置のバッファ管理方法 | |
| US7171490B2 (en) | Method and apparatus for reducing the number of write operations during route updates in pipelined forwarding engines | |
| JP3660311B2 (ja) | テーブル検索装置および方法およびプログラムおよび記録媒体 | |
| US20030031179A1 (en) | Self-updateable longest prefix matching method and apparatus | |
| US7610440B2 (en) | Content addressable memory with automated learning | |
| CN100531140C (zh) | 一种实现无回溯的最长前缀匹配搜索的方法和装置 | |
| KR20040003258A (ko) | 인터넷 프로토콜 주소 룩-업 방법 | |
| JPH09259136A (ja) | 内容検索型メモリ及び内容検索型メモリを用いたテーブル管理方式 |