JPH0897844A

JPH0897844A - データ通路の設定方法及び装置

Info

Publication number: JPH0897844A
Application number: JP7213572A
Authority: JP
Inventors: Marco Jose Geraldo Bueno De; ジョセ・ゲラルド・ブエノ・デ・マルコ; Jeffrey Wayne Kidd; ジェフリー・ウエイン・キッド; Edward Hau-Chun Ku; エドワード・ハウ・チュン・ク; Karen Park Heron; カレン・パーク・ヘロン; Simin Hosne Sanaye; シミン・ホスネ・サナイェ; Sousa Silva Luis Filipe De; ルイス・フィリィペ・デ・ソウサ・シルバ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1994-09-15
Filing date: 1995-08-22
Publication date: 1996-04-12
Also published as: US5761440A

Abstract

(57)【要約】【目的】ローカル・エリア・ネットワーク（ＬＡＮ）
のようなネットワーク・システム１００中のデータ通路
を効率よく設定する装置及び方法を与えること。【構成】アドレスをストアするために、ルータ１０２
によって用いられる検索トリーが設けられる。ルータに
よって用いられる検索トリーは、受け取ったデータの１
つまたはそれ以上のフレームがネットワーク・システム
１００の中のどのデータ処理装置１０８、１１０、．．
１２８に伝送されるべきかを、より効率的に、より迅速
に決定するのに用いられる。また、検索トリーを設ける
ことにより、新しいアドレスをサーチ・トリーに付加し
たり、あるいは古いアドレスをサーチ・トリーから削除
することができる。検索トリーは、アドレスをビット・
グループに区画することによって更新される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データ処理システム、
より詳細に言えば、データ処理装置のネットワーク内の
データ通路を設定するためのシステム及び方法に関す
る。

【０００２】

【従来の技術】ネットワークは、通信システムによって
接続されているコンピュータ及び関連機器のグループで
ある。ネットワークは、幾つかのコンピュータ、プリン
タ及びその他の装置で構成されたローカル・エリア・ネ
ットワーク（「ＬＡＮ」）よりも小規模のものであって
もよく、あるいは、広大な地域にまたがって分散された
多くの小型コンピュータ及び大型コンピュータで構成さ
れたネットワークであってもよい。コンピュータが小型
であれ、あるいは大型であれ、コンピュータ・ネットワ
ークは、情報を電気的に通信し伝送する手段をコンピュ
ータ・ユーザに提供するための手段である。

【０００３】ルータ（データ通路設定装置）即ちブリッ
ジは、メッセージの伝送を容易にするため通信ネットワ
ーク中で中間的に媒介する装置である。あり得る接続経
路を介して多くのコンピュータを接続する単一のネット
ワークにおいて、ルータは伝送されたメッセージを受け
取り、そして、最も効率的な利用可能ルートを通して、
受け取ったメッセージを正しい宛先装置に伝送する。同
じ通信プロトコルを用いた相互接続された一組のＬＡＮ
において、ルータは、一方のＬＡＮから他方のＬＡＮへ
メッセージを送信するＬＡＮ間のリンクとして動作する
ような通常のリンクとは若干異なった機能を遂行する。

【０００４】ネットワーク中の多くのそして種々のコン
ピュータ及びその他の装置は、ルータのポート（計算装
置へのデータ及び計算装置からのデータが通過する位
置）を介してルータに結合されている。ネットワーク内
の第１の装置から第２の装置へ送られた通信情報をルー
タが受け取った時、ルータは、その通信情報により与え
られた宛先アドレス（第２の装置のアドレス）と、ルー
タ内のどのポートが第２の装置に関連しているかを表示
しストアされたアドレス・リストとを比較する。次に、
ルータは、第２の装置に結合された該当するポートにそ
の通信情報を転送する。

【０００５】従来のルータは、前以って与えられている
アドレス／ポートのリストが与えられているか、または
このようなアドレス／ポートのリストを動的な態様で作
成する。このようなリストは、ルータの中にストアさ
れ、そしてルータに接続された装置から通信を受け取っ
た時にアクセスされる。従って、ルータは、アドレスの
比較処理においてマッチ（合致）した比較結果が得られ
るまで、このリスト中の各項目と、通信の宛先アドレス
とを比較する。通常、リストを照合する各新しい検索
は、リストの「最も上にある行」で開始し、マッチした
比較結果が得られるまで、リスト中のアドレスを通して
順次に進行する。このような構成によって、リスト中に
Ｎ個のアドレスがある場合、マッチした比較結果が得ら
れるまで、比較動作をＮ回まで行なわなければならない
可能性がある。若しＮが非常に大きな数であれば、ネッ
トワーク内の通信速度はルータによって可成り低下され
ることになる。

【０００６】従って、ネットワーク内のルータを通るメ
ッセージの通路を設定するためのより効率的で、より高
速な処理を行なう技術が必要である。

【０００７】

【発明が解決しようとする課題】本発明の目的は、ネッ
トワーク内のブリッジ、即ちルータを通るデータの通路
を効率良く設定することにある。

【０００８】

【課題を解決するための手段】上述の目的を達成するた
めに、ネットワーク内の装置の宛先アドレス／宛先ポー
トをストアし比較するために使用する新規な検索トリー
技術が用いられる。

【０００９】アドレス・フィールドのデータは、受信し
たデータ・フレームをネットワーク中に転送するか否か
を決定するのに用いられる。高速度でディジタル・パタ
ーンを比較する本発明の良好な実施例の処理技術は、Ｌ
ＡＮ内のブリッジ、即ちルータのサブシステムの環境に
おいて、アドレスを認識するための理想的な検索トリー
の中に編成されストアされたディジタル・パターンと、
ディジタル・パターンのデータベースとを比較する技術
である。本発明のディジタル・パターンの比較技術はテ
スト・インストラクションをストアするためのメモリを
使用する。各テスト・インストラクションは、テスト・
コマンドとメモリ位置を指示するポインタとを持ってい
る。テスト・コマンドは検査されるべきアドレス・ビッ
トに対応している。メモリ位置を指示するポインタは、
次のテスト動作のためのテスト・インストラクションを
ストアしているメモリ・ブロックを指示する。テスト・
インストラクションは、検索トリーを作成するための学
習モードにおいて、リンクされる。学習モードの間で検
索トリーを作成するために、これらのビット・グループ
の間で比較され相異しているビット・パターンのビット
・グループだけが使用される。

【００１０】受け取ったアドレスのテスト・パターンの
ビット構成に従って、テスト・パターンのマッチ処理は
特定のテスト（検索）トリーにおいて開始される。学習
モードにおいて、事前にストアされたテスト・インスト
ラクションは、テスト・トリーの経路を決定する。検索
動作の終点において、テスト・パターンは、参照されず
に検索トリーの終端のノード上にマップされて終了され
るか、または、参照パターン（ストアされたアドレス／
ポートのリスト）に突き当って終了されるかのいずれか
である。メッセージのアドレスと、ストアされたアドレ
スとの間で完全にマッチするか否かのテストが行なわれ
る。メッセージのアドレスと、ストアされたアドレス・
パターンとが完全にマッチしたときにだけ、完全マッチ
が検出される。

【００１１】学習モードにおいて、新しいアドレス・ビ
ット・パターンが、現存するアドレス・ビット・パター
ンに突き当るか、または、参照されずに検索トリーの終
端ノード上にマップされるかの何れかの場合、検索トリ
ーは拡大される。古いアドレス参照パターンと新しいア
ドレス・ビット・パターンとの間を分離するために、検
索インストラクションが検索トリーに加えられる。検索
トリーが拡大を必要とする時、その検索トリーはトリー
・ノードの終端から延長する。

【００１２】アドレスの参照パターンを削除する時、削
除するアドレス・パターンと関連した検索トリーが検査
され、そして、不必要なテスト・エントリ及びテスト・
ブロックはすべて除去される。検索トリーは、不必要な
テスト・ブロックを空にするために再リンクされ、そし
て、メモリ中の除去されたテスト・ブロックは後日使用
できるように保存される。

【００１３】

【実施例】本発明の理解を容易にするために、特別なワ
ードや、バイト長などについての特定の細部について以
下に説明を行なう。然しながら、そのような特定の細部
を持たなくとも本発明を容易に実施できるのは当業者に
は自明である。また、不必要な細部の説明によって本発
明の開示が不明瞭になるのを避けるために、本発明を実
施するために必要な公知の回路はブロック図で示されて
いる。タイミングなどに関する細部は、本発明を理解す
るために詳細に説明する必要はなく、当業者であれば容
易に理解できる。

【００１４】図１に示された各素子の寸法は正確な縮尺
で示していない。図１は、サーバ１０１と、データ処理
装置１０８、１１０、１１２、１１４、１１６、１１
８、１２０、１２２、１２４、１２６及び１２８とがル
ータ１０２を介して相互接続されている代表的なネット
ワーク・システム１００を示す図である。各データ処理
装置、あるいはサーバ１０１はネットワーク・システム
１００内の任意の他のデータ処理装置と通信するように
意図されているので、ルータ１０２は、該当する宛先装
置に対して通信されたデータを、宛先装置のポートに実
質的に結合し、効率的に伝送することによってそのよう
な通信を容易にする。例えば、若しデータ処理装置１１
４がデータ処理装置１２８へのデータ伝送を求めたなら
ば、データ処理装置１１４は、データ処理装置１２８に
関連した「宛先アドレス」と共にそのデータをルータ１
０２に転送し、そしてそのルータ１０２は、データ処理
装置１１４からのデータと共に受け取った「宛先アドレ
ス」と、ルータ１０２のメモリ中のアドレス／ポートの
アドレス・リストとを比較し、次に、受け取った「宛先
アドレス」と、そのメモリ中にリストされたアドレス／
ポートの対の１つとの間のマッチが得られた時に、受け
取ったデータをデータ処理装置１２８に伝送するデータ
通路を設定する。

【００１５】次に、図２を参照すると、ルータ１０２中
で実行され、ルータ１０２中のメモリ装置において上述
のアドレス・ポートのリストを形成するための処理の流
れ図が示されている。ルータ１０２は、ネットワーク・
システム１００内のデータ処理装置から１つ以上のデー
タ・フレームの通信を受け取った後（ステップ２０）、
データと共に転送され、かつ、送信装置に関連された
「ソース・アドレス」を、そのルータが記録するステッ
プ２１に進む。例えば、若しルータ１０２がデータ処理
装置１１２から１つまたはそれ以上のデータ・フレーム
を受け取ったならば、ルータ１０２はデータ処理装置１
１２に関連付けられた「ソース・アドレス（発信元アド
レス）」を記録する。その後、ステップ２２において、
ルータ１０２は、データ処理装置１１２が接続されるル
ータ１０２中の特定のポートと、データ処理装置１１２
の「ソース・アドレス」とを関連付ける。１台以上のデ
ータ処理装置、または別個の他のネットワーク全体をル
ータ１０２の中の任意の１つのポートに接続することが
できる。更に、ルータ１０２の中のポートは、時分割多
重化技術及び他の公知のソフトウエア技術のような公知
の方法によって区分することができる。

【００１６】ステップ２２の処理結果として、ルータ１
０２は、ルータ中のメモリ中に最終的にアドレス・テー
ブルを作成し、このアドレス・テーブルによって、ネッ
トワーク・システム１００中の複数のデータ処理装置が
ルータ１０２の中のポートに関連付けられる。

【００１７】図３を参照すると、ネットワーク・システ
ム１００において、データ・フレームの通路を設定する
処理の流れ図が示されている。ステップ３０において、
ルータ１０２は、ネットワーク・システム１００内の複
数のデータ処理装置の中の１つの装置から１つ以上のデ
ータ・フレームを受け取る。ステップ２０及びステップ
３０は同じ処理を含むことと、図２及び図３に示された
処理は、ルータ１０２の中で同時に進行することには注
意を向けられたい。

【００１８】次に、ステップ３１において、ルータ１０
２は１つ以上のデータ・フレームと共に伝送された「宛
先アドレス」と、ルータ１０２によって作成されたアド
レス・テーブル（図２を参照）とを比較する。ステップ
３２において、ルータ１０２のアドレス・テーブルの中
の「宛先アドレス」が、「宛先アドレス」及び１つ以上
のデータ・フレームを受け取ったポートに関連付けられ
ているか否かを、ルータ１０２が決定する。若し関連付
けられているならば、それらのデータ・フレームに関す
るデータ通路を設定する必要はない。何故ならば、この
データ通路は、そのデータ・フレームが伝送された装置
と同じ装置に関連しているからである。従って、ステッ
プ３３において、ルータ１０２は受け取られたデータ・
フレームを無視する。例えば、若しルータ１０２がサー
バ１０１からデータ・フレームを受け取り、そして、受
け取られたデータ・フレームと共に伝送された「宛先ア
ドレス」がサーバ１０１に割り当てられたルータのポー
トに関連していると決定されたならば、サーバ１０１は
データ・フレームを既に所有しているから、ルータ１０
２はそのデータ・フレームを無視する。

【００１９】然しながら、若し「宛先アドレス」がその
データ・フレームを受け取ったポートと同じポートに関
連されていなければ、ステップ３４において、ルータ１
０２は、「宛先」アドレスがアドレス・テーブル中の他
のポートに関連されているか否かを決定する。若し関連
されていれば、ステップ３５において、ルータ１０２
は、受け取られたデータ・フレームを他のポートへ差し
向ける。例えば、若しデータ処理装置１０８からのデー
タ・フレームと共に伝送された「宛先アドレス」がデー
タ処理装置１２４に関連したポートに関連されていると
決定されたならば、ルータ１０２は、装置１２４に関連
したポートを通して、受け取られたデータ・フレームを
装置１２４に伝送する。

【００２０】若し「宛先アドレス」が他のポートに関連
されていなければ、ステップ３６に示されているよう
に、ルータ１０２は受け取られたデータ・フレームを、
すべてのポートに対して同報通信する。

【００２１】既に述べたように、アドレス・テーブル
は、通常、ルータのポートに関連され、かつ、順序付け
られたアドレスのリストとして作成されている。そのよ
うな従来のアドレス・リストにおいて、若しルータ１０
２がステップ３２及びステップ３４の処理を遂行したな
らば、受け取られた「宛先アドレス」は、比較検索処理
がアドレスのマッチを検出するまで、アドレス・テーブ
ル中のすべてのアドレスと比較される。若しネットワー
ク・システム１００内のデータ処理装置の数が非常に大
きければ、上述の比較検索処理は可成り長い動作時間を
必要とする。このような検索方法に関連した最悪の事態
として、アドレス・テーブル中の最後の項目のマッチが
検出されるまで、マッチ結果が検出できない場合とか、
あるいは、受け取られたデータ・フレームの同報通信
（ステップ３６）の結果として、所望のマッチが存在し
ないことを検出できない場合がある。

【００２２】本発明の良好な実施例はルータ１０２の中
にストアされたアドレス・テーブルを検索するための、
より効率的で、より高速度の検索技術を与える。

【００２３】本発明は、アドレス・ビットを複数個のビ
ット・グループに区分し、かつ、これらのビット・グル
ープ（区画部分）を含む検索トリーを作成し、そして、
１つまたはそれ以上の検索トリー中にアドレス／ポート
をストアすることによって、より効率的なアドレス検索
技術を与えるものである。従って、本発明の検索処理
は、受け取ったアドレスを複数個のビット・グループに
区分し、そして、これらのビット・グループと検索トリ
ーのノードとを順番に比較することによって遂行され
る。検索処理を通して、若し受け取られたアドレスとト
リー中の入力との間の完全マッチを得ることなく、検索
トリーの終端に到達したならば、受け取られたアドレス
が「ソース・アドレス」である場合に限って検索トリー
は「ソース・アドレス」中のビットを用いて延長され
る。本明細書において、これは、「学習」処理、または
「エントリ更新」処理と言う。若し受け取られたアドレ
スが「宛先アドレス」であり、かつ完全マッチを得るこ
となく検索トリーの終端に到着したならば、アドレス・
テーブルにおいて、「宛先アドレス」のための完全マッ
チが無いことを決定し、そして「宛先アドレス」に関連
したフレーム・データの同報通信（ステップ３６）が行
なわれる。

【００２４】また、後述されるように、検索トリー中の
アドレスの削除が行なわれる。

【００２５】学習モードの間において、ルータ１０２の
中のアドレス・テーブルは、「ソース・アドレス」と、
受け取ったデータ・フレームの記号と、受け取ったポー
ト識別番号とを用いて更新される。ルータ１０２がデー
タ・フレームを受け取った時、ルータ１０２は、アドレ
ス・テーブル中の検索トリーのエントリと、受け取った
データ・フレームの「宛先アドレス」とを比較する。

【００２６】データの送り先を表示する「宛先アドレ
ス」と、データの発信元を表示する「ソース・アドレ
ス」とが、各入力データ・フレームに関連付けられてい
る。すべての入力データ・フレームのために、「宛先ア
ドレス」及び「ソース・アドレス」は、本発明の伝送処
理の間で、アドレス・テーブルのエントリに対して処理
される。以下の説明において、ネットワーク・システム
１００のネットワーク・アドレスは６バイトで構成され
ているものとする。更に、本発明の実施例を説明するだ
けの目的で、ネットワーク・システム１００のアドレス
・テーブルは最大８１９２個の参照アドレスをサポート
するものとする。

【００２７】本明細書において、「宛先アドレス」及び
「ソース・アドレス」のビット・パターンはテスト・パ
ターンと呼ばれる。テスト・パターンと言う用語を用い
ることによって、受け取られたアドレスが検索トリーの
中にストアされたビット・パターン（アドレス）に対し
てテスト（比較）されることが容易に理解できる。テス
ト・パターンは、予め決められたテスト・ビット・グル
ープに区分される。各テスト・ビット・グループは、テ
スト・マスクと関連されている。テスト・マスクは番号
が付されている。テスト・ビット・グループは１ビット
でもよいし、複数ビットでもよい。テスト・マスクは、
テスト処理の間のマッチ動作を行なうために、検査され
るべきテスト・パターンのビットを識別する。図４は本
発明の良好な実施例に従ったテスト・マスクを示す図で
ある。このマスクは、６バイトで構成されたネットワー
ク・アドレスの上述の規定と関係した４８ビットのビッ
ト長を持っている。以下に説明されるように、最初の１
２ビットは遂行される最初のテストのためにマスクされ
るが、残りの３６ビットはマッチ処理において遂行され
る後続テストのためのテスト・グループに分けられる。
本発明の実施例において、後続のテスト・グループは夫
々２ビットで構成されているが、他のビット長のテスト
・グループにすることもできる。

【００２８】次に、図５を参照すると、最初のテスト・
ブロック（「ＦＴＢ」）及び３６ビット／２ビット＝１
８個のテスト・グループ（「ＴＧ」）が識別されるテス
ト・パターン（「ＴＰ」）の実施例が示されている。

【００２９】本発明に従ったルータ１０２の中で用いら
れるメモリは３つの部分に分割される。第１の部分は、
検索トリーを通して検索を開始するためのテスト・イン
ストラクションをストアする幾つかのＦＴＢをストアし
ている。マッチ処理の速度を向上するために、ＦＴＢ
は、各ＴＧよりも大きなテスト・ブロック（テスト・ビ
ットを含むビット・グループ）であるのが好ましい。上
述の実施例において、１２ビットで構成された各ＦＴＢ
には４０９６個のエントリがある。

【００３０】ルータ１０２のメモリの第２の部分は、Ｆ
ＴＢの検索処理が終了した後に開始する検索処理を続行
するテスト・インストラクションをストアする次のテス
ト・ブロック（「ＮＴＢ」）をストアしている。ＮＴＢ
のメモリ要件は下記の通りである。（１）記録される参照パターンの最大数をＭとする。（２）Ｍ個の参照アドレスを区分するために、（Ｍ−
１）個のＮＴＢブロックを必要とする。（３）各テスト・ブロックのビット数をｊとする（Ｔ
Ｇ＝２ビット、あるいは３ビット、等々）。（４）ＮＴＢに必要な最大エントリ数は、２ｘＥＸＰ
（ｊ）である。（５）テスト・インストラクションのデータ長は（Ｉ
ｎｔｅ（ｌｏｇ２（ＴＧの数＋２））＋Ｉｎｔｅ（ｌｏ
ｇ２（Ｍ−１））である。ここで、Ｉｎｔｅ（ｘ）は整
数ｘに等しいか、あるいはｘよりも大きい整数である。

【００３１】図示の実施例においては、合計（８１９２
−１）個のＮＴＢブロックが必要である。各ＮＴＢブロ
ックは、（００、０１、１０、１１）の上述の実施例に
おいて規定されている２ビットのテスト・グループとマ
ッチするために４個のエントリを持っている。本明細書
において、上述のエントリ（００、０１、１０、１１）
は（ｃ１、ｃ２、ｃ３、ｃ４）と記載される。

【００３２】また、各テスト・グループ中のビット数
は、マッチ処理における最悪の場合のタイミングを決定
する。例えば、ＦＴＢが１２ビットであり、他のすべて
のテスト・ブロックが２ビットであると仮定すると、将
来マッチされるであろう参照パターン（つまり、ストア
されたアドレス・ビット）に到達するための最悪のタイ
ミングは、４８ビットのテスト・パターンの場合、１９
テスト・サイクルである。若しシステムが最大８０００
個の参照パターンを参照する必要があるならば、ＮＴＢ
のエントリの合計数は３１９９６（４^*（８０００−
１））個である。然しながら、若しテスト・ブロック中
のビット数が２ビットから４ビットに増加されたなら
ば、参照パターンとマッチする時点に到達するために、
最悪の場合でも、１０テスト・サイクルを取るだけであ
るが、ＮＴＢの合計のエントリ数は、１２７９８４個
（１６^*（８０００−１））に増加される。従って、シ
ステムの設計者は、マッチ処理速度と、それに要するコ
ストとの間の条件を所望のように妥協させることができ
る。

【００３３】必要とされるルータ１０２のメモリの第３
の部分は、アドレス・テーブル・ストレージ（「ＡＴ
Ｓ」）のための領域であり、ＡＴＳは、参照パターン
（アドレス・データ）と、参照パターンに関連されたル
ータのポート及びポート固有の記号情報とをストアして
いる。上述の実施例において、ＡＴＳは、参照パターン
及びポートの記号情報をストアするために、合計で８１
９２個のＡＴＳエントリが必要とされる。

【００３４】使用しないＡＴＳ、つまり「フリー（fre
e）」のＡＴＳのエントリ及び「フリー」のＮＴＢブロ
ックは空に（clear−消去）され、次に、空のエントリ
・ブロック・チェーン（鎖）を形成するために一緒に結
合される。一方のチェーンはＡＴＳのエントリのための
チェーンであり、他方のチェーンはＮＴＢブロックのた
めのチェーンである。ＡＴＳ頭部レジスタは、ＡＴＳの
空のエントリ・ブロック・チェーンの最初のエントリ位
置を保持し、そして、ＡＴＳ尾部レジスタは、ＡＴＳの
空のエントリ・ブロックのチェーンの最後のエントリ位
置を保持する。ＡＴＳの頭部レジスタの内容がＡＴＳの
尾部レジスタの内容と等しい場合、ＡＴＳ１つだけ余分
のエントリを保持することができる。また、ＮＴＢの空
のエントリ・ブロックのチェーンは、同時に形成される
ＮＴＢの頭部レジスタ及び尾部レジスタを持つている。

【００３５】学習モードにおいて、テスト・トリーの経
路中で比較処理を実行するために、新しいＡＴＳのエン
トリ及び／またはＮＴＢのエントリを必要とする時、そ
れらのエントリは頭部レジスタ中にストアされているメ
モリ位置情報から取り出され、そして、頭部レジスタは
次のフリー・ブロックのエントリ位置情報のために更新
される。削除処理の間において、ＡＴＳのメモリ位置、
またはＮＴＢのメモリ位置を最早必要としない時、その
メモリ位置は、空にされ、次に、そのメモリ位置に関連
された空のエントリ・ブロックのチェーンの最後尾に結
合され、そして関連された尾部レジスタが更新される。
頭部レジスタ及び尾部レジスタの内容は連続的に更新さ
れる。

【００３６】記入されるエントリの更新モード、挿入モ
ード及び削除モードにおいて、テスト・トリーは、修正
が行なわれるべき位置を決定するために検索されなけれ
ばならない。テスト・トリーは、参照パターン（ＡＴＳ
エントリ）を削除する時に、少なくとも最後の３つのテ
スト・インストラクションのテスト・ブロック（ＦＴＢ
及び／またはＮＴＢ）の内容が、修正されるように構成
されている。すべてのエントリのために、最後の３つの
テスト・インストラクションを追跡することによって削
除処理の効率を改善することができる。

【００３７】レジスタＤＬ１、ＤＬ２及びＤＬ３は、シ
ステム内で最後の３つのテスト・インストラクションを
記録するためにセットされる。レジスタＤＬ１は、削除
されるべき参照されたエントリの位置情報（ポインタ）
を保持している。この情報は、そのＡＴＳのエントリ位
置を指示することと、そのＡＴＳのエントリを空にする
ことと、削除されたエントリを「フリー」のエントリの
プール（貯蔵位置）中に戻す貯蔵位置情報を設定するこ
ととに用いることができる。

【００３８】レジスタＤＬ２は、ＬＴＢ（最後のテスト
・ブロック）のエントリの位置情報（エントリ位置を指
示するポインタ）を保持している。この情報は、ＡＴＳ
のエントリを削除するために空にする必要のあるテスト
・インストラクションを指示するのに使用される。

【００３９】レジスタＤＬ３は、ＬＴＢを指示するテス
ト・インストラクションの位置情報（テスト・ブロック
を指示するポインタ）を保持している。この情報は、Ａ
ＴＳのエントリが削除された後に不必要なテスト・ブロ
ックを除去するために使用することができる。エントリ
が除去された後に、若しＮＴＢ（ＤＬ２により指示され
た）がただ１つのテスト・インストラクション（残りの
３つの位置はすべて空にされる）を保持しているなら
ば、このＮＴＢは冗長であり、除去可能であることには
注意を払う必要がある。レジスタＤＬ３の内容によって
指示されたテスト・ブロック（ＦＴＢ、またはＮＴＢ）
中の適当なエントリを修正することによって、冗長なＮ
ＴＢは容易に除去することができ、後で使用するために
「フリー」のエントリのプール中に戻すことができる。

【００４０】エントリ更新処理に対して、最大限、最後
の２つのテスト・インストラクションだけが、エントリ
の更新及び検索トリーの拡大処理のために必要とされ
る。各参照アドレス・パターンは特別なパターンなの
で、メモリ中のそれ自身特別のＡＴＳエントリ中にスト
アされる。新しい参照パターン（「ＮＲＰ」）、即ち
「ソース・アドレス」をＡＴＳ（アドレス・テーブル・
ストレージ）のＲＰ（参照パターン）テーブル中に付加
するために、ＮＲＰは、まず検索処理を通らなければな
らない。レジスタＤＬ１及びＤＬ２は、ＮＲＰの検索処
理の間で最後の２つのテスト・インストラクションを記
録する。

【００４１】次に図６を参照して、検索モード、学習モ
ード及びエントリ・モードにおいて使用されるパターン
・マッチ処理を遂行するための論理回路を以下に説明す
る。

【００４２】図６に示した論理回路が動作される時、こ
の論理回路を動作するために用いられる重複しない２つ
のクロック・パルスが使用される。例えば、回路６０、
６１及び６２は、クロックＡが付勢信号を与えた時にデ
ータをサンプルし、そして、クロックＢが付勢信号を与
えた時にデータを送り出す。回路６５、６６及び６７
は、クロックＢが付勢信号を与えた時にデータをサンプ
ルし、クロックＡが付勢信号を与えた時にデータを送り
出す。

【００４３】更新モード及び削除モードに関して、図６
に示した論理回路は、ビット・パターンのマッチ処理に
関する上述のモードの一部だけしか示されていないこと
には注意を向けられたい。

【００４４】次に、図６及び図７を参照して、検索トリ
ー中のエントリ（ソース・アドレス）を更新する処理を
説明する。ステップ７０１において、この更新処理はテ
スト・パターン（ＴＰ）の受け取りを待機しているアイ
ドル状態にある。新しい参照パターン（ＮＲＰ）、即ち
新しいテスト・パターンを受け取った時、ＮＲＰはレジ
スタ６０（ＴＰレジスタ）の中にロードされる。ＴＰレ
ジスタ６０は６バイトのビット幅を持っている。ＦＴＢ
（最初のテスト・ブロック）と呼ばれる最初の１２ビッ
トは、マルチプレクサ６５（ＦＴＢのアドレス選択はク
ロックされている）中に転送され、他方、残りの３６ビ
ットはセレクタ（ＳＬ）６４に転送される。

【００４５】比較器（ＣＰ）６３、セレクタ（ＳＬ）６
４、マルチプレクサ（ＭＸ）６５、６６、６７及びレジ
スタ６０、６１、６２は、以下に説明される機能を遂行
するための従来の論理回路であることには注意を向けら
れたい。

【００４６】マルチプレクサ６５の中にロードされた最
初のテスト・ブロックの１２ビットはルータ１０２のメ
モリをアドレスするためのＦＴＢのポインタになる。レ
ジスタＤＬ１及びＤＬ２はこの第１ポインタと等しい値
になるように初期化される。

【００４７】次に、ステップ７０２において、ＦＴＢは
メモリからアドレスを読み取るために使用され、そのア
ドレスは、ＮＴＢレジスタ６２の中にロードされる。

【００４８】ＮＴＢレジスタ６２は１８ビットのビット
幅を持っている。このビット幅は、メモリ中にストアさ
れているテスト・ブロックのビット幅に適合している。
各テスト・ブロックのエントリは、５ビットのテスト・
コマンドと、１３ビットのテスト・ブロックのアドレス
・ポインタとを含むテスト・インストラクションをスト
アしている。テスト・ブロックのアドレス・ポインタ
は、次の検索動作のためのテスト・インストラクション
を保持するエントリを持っているテスト・ブロックの位
置（メモリの位置）を指示する。テスト・コマンドは、
既に説明したテスト・マスクに関するテスト番号であ
る。テスト・コマンドは、どのテスト・パターン（Ｔ
Ｐ）のビット・グループがこの検索処理により検査され
るかを識別する（セレクタ６４を使用して）。検査され
るＴＰのビット・パターンは、次の検索ステップのため
のテスト・インストラクションを保持しているテスト・
ブロックのエントリを決定する。若しテスト・コマンド
が「０」をストアしていれば、このことは、検索が終了
されており、参照パターンのマッチが生じなかったこと
を定義する。１乃至１８のテスト・コマンド値は、他の
テスト・ブロックがテストされるべきであることを決定
する。テスト・コマンド値２４は、将来マッチされるで
あろう参照パターンがあることを定義する。

【００４９】１３ビットのアドレス・ポインタはメモリ
中の次のテスト・ブロック（「ＮＴＢ」）の位置を指示
する。

【００５０】学習モードにおいて、ＲＰ（参照パター
ン）がＮＲＰ（新しい参照パターン）とは異なっている
場合において、ＮＲＰ（ソース・アドレス）が「行き止
まり」ノード（「０」のテスト・コマンドを持つエント
リ）で終了するか、または、現存するＲＰに突き当たっ
て終了するかを決定した時にのみ、テスト・トリーが延
長される。「行き止まり」のノードで終了した時、ＮＲ
ＰはＲＰデータベース中に付加される。数値Ｅのテスト
・コマンドを含むテスト・インストラクション（将来マ
ッチされるであろうＲＰで終了する検索を定義してい
る）は、ＮＲＰの位置情報（ポインタ）が「行き止ま
り」エントリの中に保持されていることを決定する。若
しテスト・パターンがＲＰに突き当たり、そしてＲＰ及
びＮＲＰが同一値であるならば、ＲＰの記号情報だけが
更新される。然しながら、若しＲＰ及びＮＲＰが異なっ
た値を持っていれば、ＮＲＰはＲＰデータベースの中に
付加される。次に、ＲＰ及びＮＲＰの間でビット値の差
異を持つテスト・グループが識別され、そして、この新
しいテスト・ブロックは、アドレス・テーブル・ストレ
ージ（ＡＴＳ）中に現在ストアされている元のＲＰ及び
ＮＲＰを指示するためのテスト・インストラクションを
保存するために、トリーの中に導入される。ＡＴＳ中に
ストアされているＲＰを以前に指示したテスト・ブロッ
クのエントリ中のテスト・インストラクションは、作成
された新しいテスト・ブロックを現在指示するテスト・
インストラクションによって置き換えられる。

【００５１】ステップ７０３において、受け取ったビッ
ト値を決定するために、受け取ったテスト・コマンド、
即ちＮＴＢレジスタ６２の中にストアされた５ビットの
テスト・コマンド値についてテストが行なわれる。若し
テスト・コマンドが数値０に等しければ、処理はステッ
プ７０６に進む。若しテスト・コマンドが数値２４に等
しければ、処理はステップ７１０に進む。若しテスト・
コマンドが数値０でも、数値２４でもないが、数値２４
よりも小さければ、処理はステップ７０４に進む。レジ
スタＤＬ１の内容はレジスタＤＬ２中にストアされ、そ
してＮＴＢレジスタ中の内容はＤＬ１の中にストアされ
る。

【００５２】若しテスト・コマンドが数値０に等しけれ
ば、このことは、新しい参照パターン（ＮＲＰ）にマッ
チするテスト・トリー中のエントリは存在しないことを
表わしている。従って、ステップ７０６において、新し
い参照パターンのアドレスがＡＴＳ（アドレス・テーブ
ル・ストレージ）の中に加えられる。ステップ７０７に
おいて、ＦＴＢ（最初のテスト・ブロック）は、ＡＴＳ
中にストアされている現在のＮＲＰであるマッチされた
参照パターンを指示するＬＴＢ（最後のテスト・ブロッ
ク）であるように更新される。従って、このＦＴＢ／Ｌ
ＴＢは、ＮＲＰをストアしているＡＴＳ中のメモリ位置
を指示するポインタを持つことになる。次に、ステップ
７０８において、この更新は完了され、処理は、受け取
られるべき新しいアドレスを待機するステップ７０１に
戻る。

【００５３】若しテスト・コマンドが数値２４を持って
いれば、このことは、将来マッチされるであろう参照パ
ターンが検出されることを意味する。この場合、セレク
タ６４は、１３ビットのアドレス・ポインタとの組み合
せを行なうマルチプレクサ（ＭＸ）６７に転送するため
のテスト・グループ（この実施例では２ビット）を選択
するための５ビットのテスト・コマンドを使用し、マル
チプレクサ６７（ＡＴＳの読み取りはクロックされる）
は、レジスタ６１に転送されるＡＴＳ中にストアされた
参照パターンを読み取るためにメモリからＡＴＳアドレ
スを選択する。その後、ステップ７１１において、比較
器（ＣＰ）６３は、ＮＲＰがＲＰに等しいか否かを決定
する。若しＮＲＰがＲＰと等しければ、処理は、参照パ
ターン（ＲＰ）の記号情報を更新するためにステップ７
１３に進む。参照パターンはＡＴＳのメモリ位置中に既
に存在しているので、上述のことは、学習モードに必要
なすべての処理である。参照パターンの記号情報には、
ＮＲＰがルータ１０２によって受け取られたことを示す
タイム・スタンプを含ませることができる。次に、処理
は前述したステップ７０８に進んだ後ステップ７０１に
進む。

【００５４】ステップ７１１において、若しＮＲＰがＲ
Ｐと等しくなければ、処理は、ステップ７０６に関して
説明したように、ＮＲＰ（新しい参照パターン）をＡＴ
Ｓのメモリ位置の中にストアするように転送するステッ
プ７１２に進む。次に、ステップ７１４において、テス
ト・グループ（ＦＴＢ）がＮＲＰに差し向けられ、かつ
ＲＰに差し向けられるように、テスト・グループが更新
される。つまり、ＮＲＰ及びＲＰの間で異なっているテ
スト・グループのビット・パターンは、それらのビット
・パターンの関連ＡＴＳエントリに別々に差し向けられ
て利用される。ステップ７１２及びステップ７１４が新
しいＲＰを与えている間で、ステップ７１５は検索トリ
ーの中にＮＲＰを挿入する。その後、処理はステップ７
０８に進む。

【００５５】ステップ７０３において、若しテスト・コ
マンドが数値２４よりも小さな値を持っていれば、図７
の処理はステップ７０４に進み、このステップにおいて
セレクタ６４は、ＡＴＳ中の次のテスト・グループをア
クセスするためのアドレスとして用いられるレジスタ６
２中にストアされている１３ビットのアドレス・ポイン
タと、テスト・グループの２ビットとを組み合わせるマ
ルチプレクサ６６（ＮＴＢの読み取りはクロックされ
る）に、ＮＲＰ中の次のテスト・グループを転送する。
次に、この、次のテスト・ブロックはレジスタ６２の中
に転送される。ステップ７０５において、レジスタＤＬ
１の内容がレジスタＤＬ２に更新され、このテスト・ブ
ロックの内容がレジスタＤＬ１に更新される。また、ス
テップ７０５において、５ビットのテスト・コマンドが
決定される。ステップ７０３に関して説明したように、
若しテスト・コマンド値が数値０であれば、処理はステ
ップ７０６に進む。若しテスト・コマンド値が数値２４
を持っていれば、処理はステップ７１０に進む。若しエ
ラー状態が発生すれば、処理はステップ７０９に進む。
このようなエラーは、パリティ・エラーの発生か、無効
なテスト・コマンド、即ちこの実施例において「コード
化」されていない２０、２１、．．．等のテスト・コマ
ンドの発生か、あるいはマッチ処理において反復して現
われるテスト・コマンドなどである。特定の検索通路に
おいてテスト・グループが２度以上含まれたならば、エ
ラー状態が発生されなければならない。

【００５６】然しながら、若しテスト・コマンドの値が
数値２４よりも小さければ、処理はステップ７０４に戻
り、このステップにおいて、セレクタ６４は、ＡＴＳ中
の次のテスト・ブロックをアドレスし、かつ検索するた
めに、前に受け取った次のテスト・ブロックからの１３
ビットのアドレス・ポインタと、テスト・グループ（Ｔ
Ｇ）の２ビットとを組み合わせるマルチプレクサ６６へ
２ビットの次のテスト・グループを転送し、次に、これ
はレジスタ６２中にストアされる。テスト・コマンドの
値が有効で、かつ数値２４以下である限り、ステップ７
０４及びステップ７０５は繰り返えされる。

【００５７】上述の処理は図８乃至図１０に示されてい
る検索トリーの実施例を参照してより良く理解すること
ができる。図８乃至図１０において、最右端に示された
縦列（Ｘを正の整数としてＭＸで示されている）は、Ａ
ＴＳのエントリを示している。

【００５８】新しい参照パターン（ＮＲＰ）がＲＰ（Ａ
ＴＳ）のエントリに最終的にマップされ、そしてＮＲＰ
及びＲＰが同じではない時には（ステップ７１１）、検
索トリーは拡大される。このような場合が図８乃至図１
０に示されており、図８乃至図１０において、ＮＲＰ４
は、ＡＴＳ（アドレス・テーブル・ストレージ）のエン
トリＲＰ３上にマップされているけれども（ステップ７
０４及びステップ７０５を通して組み合わされた後の状
態）、しかし、ＮＲＰ４及びＲＰ３はまだ同じではない
（図８）。この例において、新しいＡＴＳのエントリＭ
７がＮＲＰ４のために作成される（図７のステップ７１
２）（図９）。次に、ＲＰ３に対して前に指示されたテ
スト・グループ、この場合Ｂ２＿ｃ４中の（２４、Ｍ
５）を検出するために、ＮＲＰ及びＲＰ間のビットの相
異が決定され利用される。次に、新しいＮＴＢ、Ｂ３が
作成される（ステップ７１４）（図９）。次に、ＲＰ３
及びＮＲＰ４に差し向けるために、新しいテスト・イン
ストラクションがＢ３の中にストアされる（図９及び図
１０）。これらのテスト・インストラクションの各々
は、それらがＡＴＳのエントリに差し向けられているの
で、数値２４を持つテスト・コマンドを含んでいる。Ｒ
Ｐ３に差し向けるポインタは、Ｂ３＿ｃ１位置にある値
（２４、Ｍ５）としてストアされ、他方、ＮＲＰ４に差
し向けるポインタは、Ｂ３＿ｃ４位置にある値（２４、
Ｍ７）によって表わされている（ステップ７１４）。

【００５９】Ｂ２＿ｃ４の位置にあり、ＲＰ３に差し向
ける前のポインタは、（ＴＧ７、Ｂ３）に差し向けるポ
インタに置き換えられる（ステップ７１５）（図９及び
図１０）。

【００６０】若しＮＲＰが、数値０に等しいテスト・コ
マンド値を有するＦＴＢ、またはＮＴＢエントリ中にマ
ップされたならば、検索トリーは下記のように拡大され
る。テスト・コマンドの数値０を有するＦＴＢに関して
は、新しいＡＴＳエントリが得られる（ステップ７０
６）。これは、図９及び図１０において、ＮＲＰ３で示
されている。これは、ＦＴＢｎが「行き止まり」ノード
だったからである。従って、ＦＴＢｎは、数値２４を持
つテスト・コマンドと、ＡＴＳのエントリＭ４に差し向
ける１３ビットのアドレス・ポインタとを有するテスト
・インストラクションを持たせるように更新される（ス
テップ７０７）。

【００６１】図８において、若しＮＲＰが、数値０のテ
スト・コマンドを有する「行き止まり」ノードである次
のテスト・ブロックＢ４＿ｃ４の中にマップされたなら
ば、新しいＡＴＳのエントリＭ３が形成され（ステップ
７０４及びステップ７０５後のステップ７０６）、そし
てＢ４＿ｃ４中のポインタ（２４、Ｍ３）はＡＴＳエン
トリのＭ３に差し向けるポインタに更新される（ステッ
プ７０７）（図９及び図１０）。

【００６２】既に説明したように、若しＮＲＰ及びＲＰ
が完全にマッチされたならば、ＲＰの記号だけが更新さ
れる。これは、ＲＰ２を含むＡＴＳエントリのＭ２の経
路を通してマッチされるＮＲＰ１によって示されている
（ステップ７１０、７１１及び７１３）（図８）。

【００６３】次に、図１１を参照すると、検索トリーか
らエントリを削除する処理を説明する流れ図が示されて
いる。エントリを削除する状態は、ネットワーク・シス
テム１００中の特定の装置が取り除かれて、存在しない
装置に対する情報伝送通路を、ルータ１０２が最早設定
する必要がない時に生じる。各ＡＴＳのエントリは、ル
ータ１０２のメモリ中に、関連されたポートのアドレス
を含んでいることを想起されたい。

【００６４】図６の論理回路は、図１１のエントリ削除
処理の流れ図のパターン・マッチ部分に対しても適用さ
れる。

【００６５】ステップ９０１において、処理は、レジス
タ６０の中に、削除される参照パターン（「ＤＲＰ」）
をロードする。レジスタＤＬ１、ＤＬ２及びＤＬ３はす
べてＦＴＢのポインタの数値と同じ値にセットされる。
次に、マルチプレクサ６５は、レジスタ６２の中に保持
するためのテスト・コマンド及びポインタ情報を検索す
るために、ＦＴＢ（最初のテスト・ブロック）のメモリ
に１２ビット・ポインタのアドレスを転送する（ステッ
プ９０２）。ステップ９０３において、ＦＴＢ中にスト
アされているテスト・コマンドの数値がアクセスされ
る。レジスタＤＬ２の内容はレジスタＤＬ３の中に置か
れ、レジスタＤＬ１の内容はレジスタＤＬ２の中に置か
れ、そしてＮＴＢのポインタはレジスタＤＬ１の中に置
かれる。若しテスト・コマンドの数値が０であれば、こ
の状態は、「行き止まり」ノードに到達したことと、削
除すべき参照パターンがメモリ中に存在しないので削除
処理を必要としないこととを意味する（ステップ９０
５）。次に、処理はステップ９０１に戻る。

【００６６】若しエラー状態（既に説明した）が発生し
たならば、処理はステップ９０４に進む。

【００６７】若しテスト・コマンド値が２４よりも小さ
ければ、処理はステップ９０２に戻り、ステップ９０２
において、レジスタ６０の中にストアされた３６ビット
中の次のテスト・グループは、セレクタ６４によって選
択され、そして、レジスタ６２中にストアされている１
３ビット・ポインタのアドレスと組み合せるために、マ
ルチプレクサ６６に転送される。次に、多重化されたこ
のビット・グループは、次のテスト・ブロックのための
ルータ１０２中のメモリをアドレスするために用いら
れ、次に、このテスト・ブロックはレジスタ６２の中に
読み取られる。次に、ステップ９０３において、このテ
スト・コマンドは前述したと同じように決定される。

【００６８】若し数値２４と等しい値のテスト・コマン
ドが得られたならば、ステップ９０６において、１３ビ
ット・ポインタはセレクタ６４からのテスト・グループ
のデータと多重化されるマルチプレクサ６７に転送さ
れ、次に、この内容はレジスタ６１に読み取られる。ス
テップ９０７において、比較器（ＣＰ）６３は、ＤＲＰ
（削除参照パターン）が獲得した参照パターン（ＤＰ）
と等しいか否かを決定する。若し等しくなければ、処理
はステップ９０５に進み、ステップ９０５において、削
除されるべき参照パターンとマッチする参照パターンが
ＡＴＳの中には存在しないので、削除処理は終了され
る。然しながら、ステップ９０７において、若しＤＲＰ
がＤＰと同じならば、処理はステップ９０８に進み、削
除されるべきＡＴＳのエントリを指示する最後のテスト
・ブロック中のポインタ・エントリは空にされ（レジス
タＤＬ２はこのＬＴＢのポインタを保持している）、そ
して、このＬＴＢ（ＦＴＢかＮＴＢかのいずれかに保持
されている）を空にする。若し空にされるべきこのエン
トリがＦＴＢ中にあるならば、このＦＴＢは空にされ、
そしてＡＴＳのエントリはフリーのエントリ・ブロック
のプールに解放される。

【００６９】然しながら、若し空にされるＬＴＢがＦＴ
Ｂ中にないが、その代わりに中間的なノードにあるなら
ば、ステップ９０９中の処理は、このＮＴＢが１つのエ
ントリを含んでいるか否かを決定する。若しこのような
エントリを含んでいなければ、ＮＴＢ中でこれに対応す
るエントリは空にされ、そして、このＡＴＳのエントリ
はフリーのエントリ・ブロックのプールに与えられる。
然しながら、若しＮＴＢの中にストアされた唯１つのテ
スト・インストラクションがあれば、この最後のテスト
・ブロックは、ステップ９１０において削除され、ステ
ップ９１１の中に進む。

【００７０】エントリが削除される検索トリーが示され
ている図１２乃至図１４を参照して、エントリを削除す
る処理を更に説明する。

【００７１】ＤＲＰ１（削除参照パターン１）は、行き
止まりノードＢ２＿ｃ１中にマップされていることには
注意を払われたい（図１２）。この例において、Ｂ２＿
ｃ１は数値０のテスト・コマンドを持っており、他の動
作は必要とされない（ステップ９０５）。

【００７２】ＤＲＰ２はＡＴＳの記録位置Ｍ３の中にス
トアされているＲＰ６中にマップされている（図１
２）。この場合、Ｂ４＿ｃ４中のテスト・コマンドは数
値２４を持っている。Ｂ４＿ｃ４の内容は空にされる
（ステップ９０８）（図１３）。ＡＴＳの記録位置Ｍ３
は空にされ、フリーのエントリ・ブロックのプールに解
放される（ステップ９１２）（図１４）。そして、Ｂ２
が２つ以上のエントリを持っているので、削除処理は完
了される（ステップ９０５）。

【００７３】ＤＲＰ３はＲＰ９の中にマップされている
（ステップ９０７）（図１２）。ＦＴＢｋの内容は空に
される（ステップ９０８）（図１３）。ＡＴＳのエント
リＭ４は空にされ、ＡＴＳのフリーのエントリ・ブロッ
クのプールに戻される（ステップ９１２）（図１４）。
ＡＴＳエントリを処理する最後のテスト・ブロックは最
初のテスト・ブロック（ＦＴＢｋ）なので、その上の処
理は必要としない。

【００７４】ＤＲＰ４はＡＴＳエントリＭ７においてＲ
Ｐ４の中にマップされている（ステップ９０７）（図１
２）。この場合、Ｂ３＿ｃ４は空にされる（ステップ９
０８）（図１３）。Ｂ３はただ１つのエントリを持って
いるだけなので（ステップ９１０）、処理は、Ｂ３を削
除するためにステップ９１０に進み、Ｂ３のブロックを
空にし、そして、Ｂ３のために必要とするメモリ位置を
ＮＴＢのフリーのエントリ・ブロックのプールに解放す
る（ステップ９１１）（図１３）。Ｂ２＿ｃ４中の新し
いポインタが、残りのＡＴＳエントリのＲＰ３に向けて
指示するよう付勢される（図１４）。

【００７５】次に図１５を参照すると、検索トリーの中
でマッチを検出するための処理を説明するための流れ図
が示されている。図１５の処理によって、ルータ１０２
は、受け取ったデータ・フレームを、所定の宛先装置へ
伝送するデータ通路を設定することができる。ステップ
１１００において、テスト・グループの検出処理は、レ
ジスタ６０の中に、受け取った「宛先アドレス」をロー
ドする。ステップ１１０１において、１２ビットのＦＴ
Ｂのデータ・ブロックは、レジスタ６２中にストアされ
た次のテスト・ブロックのためのルータのメモリを検索
するために、マルチプレクサ６５によって使用される。
ステップ１１０２において、テスト・グループのデータ
のテスト・コマンド部分の値を決定するテストが行なわ
れる。若しテスト・コマンドが数値０を持っているなら
ば、ステップ１１０３において、処理は、マッチがない
ことを決定した後、ステップ１１００に戻る。この場
合、ルータ１０２は受け取ったデータの同報通報を行な
う（図２のステップ３６）。

【００７６】若しテスト・コマンドが数値２４よりも小
さい値を持っているならば、このことは、検索トリー内
の他のノードが検索されることを表わしている。ステッ
プ１１０７において、マルチプレクサ６６は、ＮＴＢメ
モリ位置の中にアドレスを与えるために、セレクタ６４
から受け取ったテスト・グループのデータと、レジスタ
６２から受け取った１３ビットのアドレス・ポインタと
を組み合わせる。再言すると、ステップ１１０８におけ
るテストは、レジスタ６２の中にストアされたテスト・
コマンドに対して行なわれる。若しテスト・コマンドが
数値２４よりも小さい値を持っているならば、処理は、
ステップ１１０７に戻り、次に、上述と同じ処理経路を
通過して進行する。

【００７７】ステップ１１０２、またはステップ１１０
８のいずれかのステップにおいて、若しテスト・コマン
ドが数値２４と同じ値ならば、これは、新しい参照パタ
ーンにマッチする参照パターンがあることを意味し、こ
の場合、マルチプレクサ６７は、セレクタ６４からのテ
スト・グループと、レジスタ６２からのポインタ・ビッ
トとを用い、次に、レジスタ６１の中に読み取られる参
照パターンにマッチするためのＡＴＳの記録位置をアド
レスする。ステップ１１０５において、比較器６３は、
テスト・パターンが検索された参照パターンと同じであ
るか否かを決定する。若しテスト・パターンが参照パタ
ーンと同じでなければ、処理はステップ１１０３に進
む。然しながら、若しテスト・パターンがＡＴＳ中にス
トアされた参照パターンと同じならば、処理は、ステッ
プ１１０６に進み、そこでマッチが存在することが決定
される。従って、これは、マッチされた参照パターンに
関連したルータのポートを通過する所定の宛先装置への
データ・フレームの通路設定動作を、このルータによっ
て行なわせる（図３のステップ３５）。

【００７８】次に、図１６を参照すると、本発明に従っ
たルータ１０２中の処理動作を説明するための論理回路
のブロック図が示されている。ランダム・アクセス・メ
モリ（ＲＡＭ）１２１２はＦＴＢ、ＮＴＢ及びＡＴＳの
メモリ位置を含んでいることには注意を向けられたい。
ＤＡ（宛先アドレス）マッチ・エンジン１２０６はＴＰ
（テスト・パターン）データ・バスからの「宛先アドレ
ス」データを受け取り、そして「宛先アドレス」のマッ
チ処理を行なう（図１５）。ＳＡ（ソース・アドレス）
マッチ・エンジン１２０７は、ＴＰデータ・バスから
「ソース・アドレス」を受け取り、そして「ソース・ア
ドレス」のマッチ処理を行なう（図７）。若し参照パタ
ーンのマッチが検出されたならば、タイム・スタンプが
与えられる。マイクロプロセッサの比較エンジン１２０
８はマイクロプロセッサ・バスからのデータを受け取
り、そしてパターンのマッチ処理を行なう（図６の比較
器）。エントリ更新エンジン１２０９はマイクロプロセ
ッサ・バスからのＮＲＰのデータを受け取り、そして、
上述したようにＡＴＳエントリの更新を遂行する（図
７）。エントリ削除エンジン１２１０はマイクロプロセ
ツサ・バスからＤＲＰ（削除参照パターン）を受け取
り、そしてＡＴＳエントリの削除を遂行する（図１
１）。マイクロプロセッサ・インターフェース・ロジッ
ク１２０２を設けることによって、必要に応じて任意の
エンジンとの間で通信することと、コマンドを発生する
ことと、ＲＡＭ１２１２に対する読み取り及び書き込み
動作を行なうこととを、ルータ１０２の中のマイクロプ
ロセッサが遂行可能となる。ＴＰバス仲裁装置１２０１
はＴＰ（テスト・パターン）処理を共有する装置を仲裁
し、そしてＴＰ処理要求のための適当な装置へのバスを
与える。

【００７９】まとめとして、本発明の構成に関して以下
の事項を開示する。

【００８０】（１）データ処理装置の宛先アドレスと関
連されているデータを処理するネットワーク・システム
中のデータ通路を設定する方法において、上記宛先アド
レスと宛先アドレスのデータベースとを比較する比較ス
テップを含み、該比較ステップは、更に、上記宛先アド
レスの一部分と上記データベースの区画部分とを順番に
比較する比較ステップを含み、該比較ステップにおい
て、前に比較された一部分／区画部分の対がマッチした
時に、一部分／区画部分の対の後続の比較動作が発生さ
れることと、上記宛先アドレスの上記一部分のすべてが
上記データベースの区画部分とマッチした時に上記宛先
アドレスへの上記データ通路を設定するステップとを含
むことを特徴とするデータ通路の設定方法。（２）宛先アドレスの上記データベースの上記区画部分
は検索トリー中に配置されている（１）に記載のデータ
通路の設定方法。（３）上記データベースの区画部分は後続する区画部分
に差し向けるポインタを含み、前に比較された一部分／
区画部分の対がマッチした時に上記ポインタの動作が開
始されることを特徴とする（１）に記載のデータ通路の
設定方法。（４）一部分／区画部分の対がマッチしない時に、上記
宛先アドレスのマッチされない部分を上記検索トリーに
加えるステップを含む（２）に記載のデータ通路の設定
方法。（５）上記システムはデータ処理装置のネットワークを
含む（１）に記載のデータ通路の設定方法。（６）ネットワーク中のデータ処理装置の間でデータ通
路を設定する装置において、上記データ処理装置へデー
タを転送し、かつ上記データ処理装置からデータを受け
取ることを可能にするインターフェース手段を含み、上
記データは上記データ処理装置の１つに関連された宛先
アドレスを含むことと、１つまたはそれ以上の検索トリ
ー中にストアされた複数個のアドレスと上記宛先アドレ
スとを比較する比較手段を含み、上記複数個のアドレス
は上記データ処理装置に関連されていることと、上記宛
先アドレスと、上記複数個のアドレスの１つとがマッチ
したことを上記比較手段が検出した時に、上記インター
フェース手段を通して上記データを上記データ処理装置
の１つに転送する手段とを含むデータ通路設定装置。（７）上記データは上記データを発信した上記データ処
理装置の１つに関連されたソース・アドレスを含んでい
るデータ通路設定装置であって、上記１つまたはそれ以
上の検索トリー中にストアされた上記複数個のアドレス
と上記ソース・アドレスとを比較する比較手段と、上記
１つまたはそれ以上の検索トリー中にストアされた上記
複数個のアドレスの１つと上記ソース・アドレスとがマ
ッチしなかったことを上記比較手段が検出した時に、上
記１つまたはそれ以上の検索トリーの１つに上記ソース
・アドレスを付加する手段とを含む（６）に記載のデー
タ通路設定装置。（８）上記データが発信された上記データ処理装置の１
つに関連されたアドレスと上記宛先アドレスとがマッチ
したことを上記比較手段が検出した時に、上記データを
無視する手段を含む（６）に記載のデータ通路設定装
置。（９）上記１つまたはそれ以上の検索トリーの中にスト
アされた上記複数個のアドレスの１つと上記宛先アドレ
スとがマッチしなかったことを上記比較手段が検出した
時に、上記インターフェース手段を通して上記データ処
理装置のすべてに上記データを同報通信する手段を含む
（６）に記載のデータ通路設定装置。（１０）上記１つまたはそれ以上の検索トリー中にスト
アされた上記複数個のアドレスの１つを削除する手段を
含む（６）に記載のデータ通路設定装置。（１１）データ処理ネットワークに接続する複数個のポ
ートと、上記ネットワーク中のデータ処理装置に対応す
るアドレスをストアする手段と、上記１つまたはそれ以
上の検索トリー中の上記アドレスと、上記データに関連
付けられたアドレスとを比較することによって、上記複
数個のポートの内の一方のポートを通して上記複数個の
ポートの内の他方のポートへ、受信したデータの通路を
設定する手段とを含むルータ。（１２）上記１つまたはそれ以上の検索トリーは上記ア
ドレスの区画部分を含み、上記アドレスの１つまたはそ
れ以上のアドレスがポインタによって組み合されること
を特徴とする（１１）に記載のルータ。（１３）上記１つまたはそれ以上の検索トリーの１つの
中にストアされた上記アドレスの１つと、上記データに
関連された上記アドレスとの間で将来のマッチがあるこ
とを、上記ポート内の１つまたはそれ以上のポートが表
示することを特徴とする（１２）に記載のルータ。（１４）１つまたはそれ以上の上記ポインタは、上記デ
ータに関連された上記アドレスと、上記１つまたはそれ
以上の検索トリーの１つのトリーにストアされた上記ア
ドレスの１つのアドレスとの間でマッチがないことの表
示を含むことを特徴とする（１２）に記載のルータ。（１５）データ処理ネットワークに接続されたルータ中
のメモリ中にアドレスをストアする方法において、上記
ネットワーク中のデータ処理装置に関連したアドレスを
受け取るステップと、上記アドレスの１つまたはそれ以
上の区画部分と、上記メモリ中の検索トリー中に配置さ
れる前にストアされた区画部分とを比較するステップ
と、上記アドレスの上記区画部分の１つが上記前にスト
アされた区画部分の１つとマッチしない時に、上記検索
トリーに上記アドレスを加えるステップとを含むアドレ
スのストア方法。（１６）上記前にストアされた区画部分は上記検索トリ
ー中の次の区画部分を指示するポインタを含んでいる
（１５）に記載のアドレスのストア方法。（１７）上記前にストアされた区画部分は、（ａ）上
記検索トリーはその区画部分において終端しているか、
または、（ｂ）上記検索トリーは他の区画部分に連続
しているか、または、（ｃ）上記検索トリーはマッチ
したアドレスを指示しているかのいずれかを表示するコ
ードを含むことを特徴とする（１６）に記載のアドレス
のストア方法。（１８）ルータによってリンクされている複数個のデー
タ処理装置を含むデータ処理ネットワークにおいて、上
記ルータは、上記複数個のデータ処理装置の第１の装置
からデータを受け取る手段を含み、上記データは上記複
数個のデータ処理装置の第２の装置に送られるメッセー
ジを含んでおり、そして、ソース・アドレスは上記複数
個のデータ処理装置の第１の装置に関連されており、か
つ宛先アドレスは上記複数個のデータ処理装置の第２の
装置に関連されていることと、１つまたはそれ以上の検
索トリー中に配置された複数個のアドレスをストアする
メモリ手段と、上記ソース・アドレスと、１つまたはそ
れ以上の検索トリー中に配置された上記複数個のアドレ
スとを比較する第１比較手段と、該第１比較手段が１つ
またはそれ以上の検索トリー中に配置された上記複数個
のアドレスの内の任意の１つと上記ソース・アドレスと
がマッチしないことを検出した時に、１つまたはそれ以
上の検索トリー中に配置された上記複数個のアドレスを
更新する手段と、上記宛先アドレスと、１つまたはそれ
以上の検索トリー中に配置された上記複数個のアドレス
とを比較する第２比較手段と、該第２比較手段が上記宛
先アドレスと、１つまたはそれ以上の検索トリー中に配
置された上記複数個のアドレスの任意の１つとがマッチ
したことを検出した時に、上記複数個のデータ処理装置
の中の第２の装置に上記データを転送する手段とを含む
データ処理ネットワーク。（１９）１つまたはそれ以上の検索トリー中に配置され
た上記複数個のアドレスの１つを削除する手段を含む
（１８）に記載のデータ処理ネットワーク。

【００８１】

【発明の効果】データ通信ネットワーク内のルータを通
るメッセージのデータ通路を効率よく、しかも従来より
も遥かに迅速に設定することができる。

【図面の簡単な説明】

【図１】ルータを使用したネットワーク構成を示す図で
ある。

【図２】ルータの中にアドレス／ポートをストアする処
理を説明するための流れ図である。

【図３】ルータを通ってデータ通路を設定する処理を説
明するための流れ図である。

【図４】本発明に従ってアドレスの区分を定義するため
のテスト・グループのマスクを示す図である。

【図５】本発明の動作を行なうために区分されたアドレ
スの例を説明する図である。

【図６】本発明に従った論理回路を示すブロック図であ
る。

【図７】本発明に従ってアドレス情報を更新する処理を
説明するための流れ図である。

【図８】更新されるアドレスを有する検索トリーの実施
例を説明する図である。

【図９】更新されるアドレスを有する検索トリーの実施
例を説明する図である。

【図１０】更新されるアドレスを有する検索トリーの実
施例を説明する図である。

【図１１】本発明に従ってアドレスを削除するための処
理を説明するための流れ図である。

【図１２】削除されるアドレスを有する検索トリーの実
施例を説明する図である。

【図１３】削除されるアドレスを有する検索トリーの実
施例を説明する図である。

【図１４】削除されるアドレスを有する検索トリーの実
施例を説明する図である。

【図１５】本発明のアドレス・マッチ処理の実行を説明
するための流れ図である。

【図１６】ルータ装置の中で本発明を遂行するための装
置のブロック図である。

【符号の説明】

６０ＴＰ（テスト・パターン）レジスタ６１ＲＰ（参照パターン）レジスタ６２ＮＴＢ（次のテスト・ブロック）レジスタ６３比較器６４セレクタ６５、６６、６７、１２１１マルチプレクサ（ＭＸ）１００ネットワーク・システム１０１サーバ１０２ルータ１０８、１１０、１１２１２４、１２８データ処理
装置１２０１ＴＰバス仲裁装置１２０２マイクロプロセッサのインターフェース１２０３出力レジスタ１２０４タスク・スケジューラ１２０５バッフア管理エンジン１２０６宛先（ＤＡ）マッチ・エンジン１２０７ソース・アドレス（ＳＡ）マッチ・エンジン１２０８比較エンジン１２０９エントリ更新エンジン１２１０エントリ削除エンジン１２１２ランダム・アクセス・メモリ（ＲＡＭ）ＡＴＳアドレス・テーブル・ストレージＤＲＰ削除パターンＤＡ宛先アドレスＦＴＢ最初のテスト・ブロックＮＴＢ次のテスト・ブロックＬＴＢ最後のテスト・ブロックＮＲＰ新しい参照パターンＳＡソース・アドレスＴＧテスト・グループ

───────────────────────────────────────────────────── フロントページの続き (72)発明者ジェフリー・ウエイン・キッドアメリカ合衆国ノースカロライナ州、ケアリー、ケアリー・パインス・ドライブ 413 (72)発明者エドワード・ハウ・チュン・クアメリカ合衆国ノースカロライナ州、ケアリー、ロックウッド・ドライブ・ウエスト 115 (72)発明者カレン・パーク・ヘロンアメリカ合衆国ノースカロライナ州、ラーレイ、ペニイ・ロード 9208 (72)発明者シミン・ホスネ・サナイェアメリカ合衆国ノースカロライナ州、ラーレイ、ロードステッド・ウエイ・ウエスト 10301 (72)発明者ルイス・フィリィペ・デ・ソウサ・シルバブラジル国リオ・デ・ジャネーロ、ジャカレパクゥア、フレゲシア、ルア・ティロル 876、エィ・ピー 202

Claims

【特許請求の範囲】

【請求項１】データ処理装置の宛先アドレスと関連さ
れているデータを処理するネットワーク・システム中の
データ通路を設定する方法において、上記宛先アドレスと宛先アドレスのデータベースとを比
較する比較ステップを含み、該比較ステップは、更に、上記宛先アドレスの一部分と上記データベースの区画部
分とを順番に比較する比較ステップを含み、該比較ステ
ップにおいて、前に比較された一部分／区画部分の対が
マッチした時に、一部分／区画部分の対の後続の比較動
作が発生されることと、上記宛先アドレスの上記一部分のすべてが上記データベ
ースの区画部分とマッチした時に上記宛先アドレスへの
上記データ通路を設定するステップとを含むことを特徴
とするデータ通路の設定方法。
【請求項２】宛先アドレスの上記データベースの上記
区画部分は検索トリー中に配置されている請求項１に記
載のデータ通路の設定方法。
【請求項３】上記データベースの区画部分は後続する
区画部分に差し向けるポインタを含み、前に比較された
一部分／区画部分の対がマッチした時に上記ポインタの
動作が開始されることを特徴とする請求項１に記載のデ
ータ通路の設定方法。
【請求項４】一部分／区画部分の対がマッチしない時
に、上記宛先アドレスのマッチされない部分を上記検索
トリーに加えるステップを含む請求項２に記載のデータ
通路の設定方法。
【請求項５】上記システムはデータ処理装置のネット
ワークを含む請求項１に記載のデータ通路の設定方法。
【請求項６】ネットワーク中のデータ処理装置の間で
データ通路を設定する装置において、上記データ処理装置へデータを転送し、かつ上記データ
処理装置からデータを受け取ることを可能にするインタ
ーフェース手段を含み、上記データは上記データ処理装
置の１つに関連された宛先アドレスを含むことと、１つまたはそれ以上の検索トリー中にストアされた複数
個のアドレスと上記宛先アドレスとを比較する比較手段
を含み、上記複数個のアドレスは上記データ処理装置に
関連されていることと、上記宛先アドレスと、上記複数個のアドレスの１つとが
マッチしたことを上記比較手段が検出した時に、上記イ
ンターフェース手段を通して上記データを上記データ処
理装置の１つに転送する手段とを含むデータ通路設定装
置。
【請求項７】上記データは上記データを発信した上記
データ処理装置の１つに関連されたソース・アドレスを
含んでいるデータ通路設定装置であって、上記１つまたはそれ以上の検索トリー中にストアされた
上記複数個のアドレスと上記ソース・アドレスとを比較
する比較手段と、上記１つまたはそれ以上の検索トリー中にストアされた
上記複数個のアドレスの１つと上記ソース・アドレスと
がマッチしなかったことを上記比較手段が検出した時
に、上記１つまたはそれ以上の検索トリーの１つに上記
ソース・アドレスを付加する手段とを含む請求項６に記
載のデータ通路設定装置。
【請求項８】上記データが発信された上記データ処理
装置の１つに関連されたアドレスと上記宛先アドレスと
がマッチしたことを上記比較手段が検出した時に、上記
データを無視する手段を含む請求項６に記載のデータ通
路設定装置。
【請求項９】上記１つまたはそれ以上の検索トリーの
中にストアされた上記複数個のアドレスの１つと上記宛
先アドレスとがマッチしなかったことを上記比較手段が
検出した時に、上記インターフェース手段を通して上記
データ処理装置のすべてに上記データを同報通信する手
段を含む請求項６に記載のデータ通路設定装置。
【請求項１０】上記１つまたはそれ以上の検索トリー
中にストアされた上記複数個のアドレスの１つを削除す
る手段を含む請求項６に記載のデータ通路設定装置。
【請求項１１】データ処理ネットワークに接続する複
数個のポートと、上記ネットワーク中のデータ処理装置に対応するアドレ
スをストアする手段と、上記１つまたはそれ以上の検索トリー中の上記アドレス
と、上記データに関連付けられたアドレスとを比較する
ことによって、上記複数個のポートの内の一方のポート
を通して上記複数個のポートの内の他方のポートへ、受
信したデータの通路を設定する手段とを含むルータ。
【請求項１２】上記１つまたはそれ以上の検索トリー
は上記アドレスの区画部分を含み、上記アドレスの１つ
またはそれ以上のアドレスがポインタによって組み合さ
れることを特徴とする請求項１１に記載のルータ。
【請求項１３】上記１つまたはそれ以上の検索トリー
の１つの中にストアされた上記アドレスの１つと、上記
データに関連された上記アドレスとの間で将来のマッチ
があることを、上記ポート内の１つまたはそれ以上のポ
ートが表示することを特徴とする請求項１２に記載のル
ータ。
【請求項１４】１つまたはそれ以上の上記ポインタ
は、上記データに関連された上記アドレスと、上記１つ
またはそれ以上の検索トリーの１つのトリーにストアさ
れた上記アドレスの１つのアドレスとの間でマッチがな
いことの表示を含むことを特徴とする請求項１２に記載
のルータ。
【請求項１５】データ処理ネットワークに接続された
ルータ中のメモリ中にアドレスをストアする方法におい
て、上記ネットワーク中のデータ処理装置に関連したアドレ
スを受け取るステップと、上記アドレスの１つまたはそれ以上の区画部分と、上記
メモリ中の検索トリー中に配置される前にストアされた
区画部分とを比較するステップと、上記アドレスの上記区画部分の１つが上記前にストアさ
れた区画部分の１つとマッチしない時に、上記検索トリ
ーに上記アドレスを加えるステップとを含むアドレスの
ストア方法。
【請求項１６】上記前にストアされた区画部分は上記
検索トリー中の次の区画部分を指示するポインタを含ん
でいる請求項１５に記載のアドレスのストア方法。
【請求項１７】上記前にストアされた区画部分は、（ａ）上記検索トリーはその区画部分において終端し
ているか、または、（ｂ）上記検索トリーは他の区画部分に連続している
か、または、（ｃ）上記検索トリーはマッチしたアドレスを指示し
ているかのいずれかを表示するコードを含むことを特徴
とする請求項１６に記載のアドレスのストア方法。
【請求項１８】ルータによってリンクされている複数
個のデータ処理装置を含むデータ処理ネットワークにお
いて、上記ルータは、上記複数個のデータ処理装置の第１の装置からデータを
受け取る手段を含み、上記データは上記複数個のデータ
処理装置の第２の装置に送られるメッセージを含んでお
り、そして、ソース・アドレスは上記複数個のデータ処
理装置の第１の装置に関連されており、かつ宛先アドレ
スは上記複数個のデータ処理装置の第２の装置に関連さ
れていることと、１つまたはそれ以上の検索トリー中に配置された複数個
のアドレスをストアするメモリ手段と、上記ソース・アドレスと、１つまたはそれ以上の検索ト
リー中に配置された上記複数個のアドレスとを比較する
第１比較手段と、該第１比較手段が１つまたはそれ以上の検索トリー中に
配置された上記複数個のアドレスの内の任意の１つと上
記ソース・アドレスとがマッチしないことを検出した時
に、１つまたはそれ以上の検索トリー中に配置された上
記複数個のアドレスを更新する手段と、上記宛先アドレスと、１つまたはそれ以上の検索トリー
中に配置された上記複数個のアドレスとを比較する第２
比較手段と、該第２比較手段が上記宛先アドレスと、１つまたはそれ
以上の検索トリー中に配置された上記複数個のアドレス
の任意の１つとがマッチしたことを検出した時に、上記
複数個のデータ処理装置の中の第２の装置に上記データ
を転送する手段とを含むデータ処理ネットワーク。
【請求項１９】１つまたはそれ以上の検索トリー中に
配置された上記複数個のアドレスの１つを削除する手段
を含む請求項１８に記載のデータ処理ネットワーク。