(57)【特許請求の範囲】
【請求項１】
ルックアップ・テーブルを生成する方法で、
入力アドレスを受信し、
入力アドレスから入力アドレスよりビットが少ない圧縮アドレスを生成し、
圧縮アドレスから第１ビットセットを選択し、
アドレス・ルックアップ・テーブルの第１ビットセットが指すメモリ位置が未占有メモリ・スロットを含むか否かを判定し、
入力アドレスがアドレス・ルックアップ・テーブルの第１ビットセットが指すメモリ位置に格納されたアドレスの何れかに一致するか否かを判定し、
第１ビットセットが指すメモリ位置に未占有メモリ・スロットがなく、入力アドレスが第１ビットセットが指すメモリ位置に格納されたアドレスと一致しないことに応じて圧縮アドレスから第２ビットセットを選択する、
各ステップを備えたことを特徴とする方法。
【請求項２】
前記圧縮アドレスから第１ビットセットを選択するステップは、前記圧縮アドレスから所定数の隣接ビットを選択するステップを備える、請求項１に記載の方法。
【請求項３】
前記圧縮アドレスから第２ビットセットを選択するステップは、前記所定数の隣接ビットを１ビットだけシフトするステップを備える、請求項２に記載の方法。
【請求項４】
前記第１ビットセットが指すメモリ位置は、複数のメモリ・スロットを含み、アドレス・ルックアップ・テーブル内の前記第１ビットセットが指すメモリ位置が、未占有メモリ・スロットを含むか否かを判定するステップは、
インデックスポインタが指す第１メモリ・スロットが占有されているか否かを判定し、
占有された前記第１メモリ・スロットに応じて前記インデックスポインタを１だけ増加し、ここで前記入力アドレスは前記第１メモリ・スロットに格納されたアドレスに一致せず、前記インデックスポインタは最大値に等しくなく、
前記増加されたインデックスポインタが指す第２メモリ・スロットが占有されているか否かを判定する、
各ステップを備える請求項１に記載の方法。
【請求項５】
前記入力アドレスが、前記アドレス・ルックアップ・テーブル内の前記第１ビットセットが指すメモリ位置に格納された何れかの入力アドレスに一致するか否かを判定するステップは、前記入力アドレスと占有メモリ・スロットに格納されたアドレスとを比較するステップを備える、請求項４に記載の方法。
【請求項６】
前記第１ビットセットが指すメモリ位置は、１つのメモリ・スロットを含み、
アドレス・ルックアップ・テーブル内の前記第１ビットセットが指すメモリ位置が未占有メモリ・スロットを含むか否かを判定するステップが、１つのメモリ・スロットが占有されているか否かを判定するステップを備え、
前記入力アドレスが前記アドレス・ルックアップ・テーブル内の前記第１ビットセットが指すメモリ位置に格納された何れかの入力アドレスに一致するか否かを判定するステップは、前記入力アドレスと、占有された１つのメモリ・スロットに応じて該１つのメモリ・スロットに格納されたアドレスとを比較するステップを備える、請求項１に記載の方法。
【請求項７】
前記第１ビットセットが指すメモリ位置に未占有のメモリ・スロットがなく、かつ前記入力アドレスが前記第１ビットセットが指す前記メモリ位置に格納された何れの入力アドレスにも一致しないことに応じて、前記アドレス・ルックアップ・テーブル内の全ての内容をクリアする、請求項１に記載の方法。
【請求項８】
ルックアップ・テーブル・ジェネレータを含む装置であって、
前記ルックアップ・テーブル・ジェネレータは、
入力アドレスを受信し、該入力アドレスよりビットの少ない圧縮アドレスを生成するよう構成されたアドレス・コンプレッサと、
前記アドレス・コンプレッサに接続され、前記圧縮アドレスから第１ビットセットを選択するよう構成されるバレル・シフタと、
前記第１ビットセットが指すメモリ位置であって少なくとも１個のメモリ・スロットを含むメモリ位置を含み、前記バレル・シフタに接続されたアドレス・ルックアップ・テーブルと、
前記バレル・シフタとアドレス・ルックアップ・テーブルとに接続され、前記第１ビットセットが指すメモリ位置に未占有メモリ・スロットがなく、かつ前記入力アドレスが前記第１ビットセットが指すメモリ位置に格納されたアドレスに一致しないことに応じて、前記圧縮アドレスから第２ビットセットを選択するように前記バレル・シフタをシフトするよう構成されるコントロール・ステート・マシンと、
を備えたことを特徴とする装置。
【請求項９】
前記バレルシフタは、前記圧縮アドレスから所定数の隣接ビットを選択することにより前記圧縮アドレスから前記第１ビットセットを選択するよう構成される、請求項８に記載の装置。
【請求項１０】
前記コントロール・ステート・マシンは、前記所定数の隣接ビットを１ビットだけシフトすることにより、第２ビットセットが前記圧縮アドレスから選択されるように前記バレルシフタをシフトするよう構成される、請求項９に記載の装置。
【請求項１１】
前記第１ビットセットが指すメモリ位置は、複数のメモリ・スロットを含み、前記ルックアップ・テーブル・ジェネレータは、前記複数のメモリ・スロットのうちの１つを指すように構成されたインデックスポインタを備える、請求項８に記載の装置。
【請求項１２】
前記コントロール・ステート・マシンは、
前記インデックスポインタが指す第１メモリ・スロットが占有されているか否かを判定し、
占有されている前記第１メモリ・スロットに応じて前記インデックスポインタを１だけ増加し、ここで前記入力アドレスは前記第１メモリ・スロットに格納されるアドレスに一致せず、かつ前記インデックスポインタは最大値に等しくなく、
前記増加されたインデックスポインタが指す第２メモリ・スロットが、占有されているか否かを判定する、
各ステップを備えることにより、前記第１ビットセットが指すメモリ位置に未占有メモリ・スロットがあるか否かを判定するよう構成される、請求項１１に記載の装置。
【請求項１３】
前記ルックアップテーブル・ジェネレータは、前記入力アドレスおよび前記アドレス・ルックアップ・テーブルに格納されたアドレスを受信するよう結合された比較器を備え、
前記コントロール・ステート・マシンは、前記比較器に前記入力アドレスと占有メモリ・スロットに格納されたアドレスとを比較可能にすることにより、前記入力アドレスが、前記第１ビットセットが指すメモリ位置に格納された何れかのアドレスに一致するか否かを判定するよう構成される、請求項１２に記載の装置。
【請求項１４】
前記コントロール・ステート・マシンは、前記第１ビットセットが指すメモリ位置の未占有メモリ・スロットがなく、かつ前記入力アドレスが前記第１ビットセットが指すメモリ位置に格納される何れのアドレスにも一致しないことに応じて前記アドレス・ルックアップ・テーブルの全ての内容をクリアするよう構成される、請求項８に記載の装置。
【請求項１５】
複数のポートを備え、ネットワークの複数のノードをインターフェースするよう使用されるネットワークデバイスを備える、請求項８に記載の装置。
【発明の詳細な説明】
【０００１】
〔1.発明の分野〕
本発明は、コンピュータ・ネットワーク装置で用いるアドレス・ルックアップ・テーブルに関し、より詳しくは、そのようなアドレス・ルックアップ・テーブルを生成するための方法および装置に関する。
【０００２】
〔2．関連技術の説明〕
パーソナル・コンピュータ、ワークステーション、サーバ等複数のノードをリンクしてノードが情報やリソースを互いに共有できるようにするためローカル・エリア・ネットワークが定期的に用いられている。小規模ネットワークについては、単純な構成を用いることができ、そこではノードがそれぞれネットワーク・バックボーンに直接接続されている。しかしながら、多数のノードを持つより複雑なネットワークでは、直接接続は非常に非効率となる。より複雑なネットワークの効率を改善するため、「セグメンティング」方法がしばしば利用される。
【０００３】
セグメンティング方法によると、ネットワークの各種ノードは「セグメント」として知られる複数のグループに分けられ、各セグメントは一般に、定期的に互いに通信する複数のノードからなる。セグメントのノードは全て通常は互いにネットワークしてサブ・ネットワークを形成し、そのセグメントは1つのセグメント・ポートを通じてネットワーク・バックボーンに接続される。このようにノードをネットワークと互いに接続することにより、ネットワーク・バックボーンとの接続性を保全しながら、実際にバックボーンに接続されるポート数を最小に抑える。より複雑なネットワークでは、各セグメントはサブ・セグメントに分け、これらサブ・セグメントをさらにスーパー・サブ・セグメントに分けて複雑な階層を作り上げる。セグメンティングの原理は、あらゆる所望レベルに拡張することができる。このようにノードをセグメントすることでネットワーク効率を改善することがわかってきた。
【０００４】
アプリケーションのセグメンティングに広く使われている装置はブリッジである。ブリッジは、2つのエンティティの間にリンクを提供する。接続されたエンティティは、2つの別個のセグメントでもよく、ネットワークとセグメントでもよい。現在、様々なブリッジが利用可能であるが、多くのブリッジが汎用ブリッジとして2面を有し、各面が多数のノードおよび他のブリッジを対処する。典型的なブリッジは、ブリッジの第1面を対処するための第1のコントローラと、ブリッジの第2面を対処するための第2のコントローラを有する。しかしながら、ブリッジは、複数のノードをネットワークにインターフェースするために用いることのできるネットワーク装置のほんの一例である。他にこのようなネットワーク装置の例として、ハブ、スイッチ、ルータ、ゲートウェイ等がある。
【０００５】
複数のノードをネットワークにインターフェースするために用いる各種ネットワーク装置には、一般に、複数のノードに接続するための複数のワーキング・ポート、ワーキング・ポートのアドレスを格納するためのアドレス・ルックアップ・テーブル、ネットワークに接続するためのアタッチメント・ポート、入パケット・コントローラ、出パケット・コントローラを含む。オペレーション中、これら装置はアタッチメント・ポートを介してネットワークから入データ・パケットを受け取る。パケットは入パケット・コントローラに渡される。コントローラはパケットから宛先アドレスを取り出し、これがアドレス・ルックアップ・テーブルに格納されたアドレスの1つと一致するか否か判断する。アドレス・ルックアップ・テーブルは、各アドレスが関連する特定のポートを示す情報を含む。アドレス一致が見つかると、そのパケットはワーキング・ポートの1つ宛てと判断され、対応して、コントローラがそのワーキング・ポートに入パケットを送る。
【０００６】
パケットから取り出した宛先アドレスは一般に、例えば48ビットなどの多数のビットからなる。48ビット宛先アドレス全体と対応するポート情報は通常、データとしてアドレス・ルックアップ・テーブルに格納されているが、48ビットの宛先アドレス全体は通常はアドレス・ルックアップ・テーブルのアドレス指定や中のメモリ位置へのポイントには用いられない。言い換えると、48ビット宛先アドレス全体は通常はアドレス・ルックアップ・テーブル内の特定のメモリ位置やメモリ・スロットのポイントに用いられず、そこには宛先アドレスと対応するポート情報が格納される。48ビット全体は、非常に大きなアドレス・ルックアップ・テーブルを必要とし、オペレーションが不可能になることがあるため、アドレス・ルックアップ・テーブル内のメモリ位置のポイントには用いられない。
【０００７】
その代わり、アドレス・ルックアップ・テーブル内のメモリ位置は、宛先アドレスの全48ビット未満を用いて、アドレス指定またはポイントされる。少ない数のビットを用いることにより、アドレス・ルックアップ・テーブルのサイズをより実用的な大きさに下げることができる。宛先アドレスの全48ビット未満を用いてアドレス・ルックアップ・テーブルをアドレス指定するため用いている方法は、まず48ビット宛先を48ビットより少ない圧縮アドレスに圧縮する。たとえば、48ビット宛先アドレスは、32ビットを有する圧縮アドレスに圧縮することができる。そして、32ビット全てより少ない圧縮アドレスの多数の隣接ビットを使って、アドレス・ルックアップ・テーブルをアドレス指定する。例えば、32ビット圧縮アドレスの5個の最下位ビットを用いてアドレス・ルックアップ・テーブルをアドレス指定することができる。
【０００８】
例えば、一度、アドレス・ルックアップ・テーブルを生成すると、32ビット圧縮アドレスの最下位5ビットを使ったアドレス・ルックアップ・テーブルのアドレス指定はうまく動く。しかし、この方法は、アドレス・ルックアップ・テーブルを生成する時に問題を生じることがある。特に、アドレス・ルックアップ・テーブルは一般に、データ・パケット受信時、使用中に生成する。データ・パケットを受信する時、48ビット宛先アドレスを抽出し、32ビット圧縮アドレスを生成し、32ビット圧縮アドレスの最下位5ビットを選択してから、最下位5ビットでポイントするメモリ位置をチェックして、既に48ビット宛先アドレスと対応するポート情報を保有しているか否か確かめる。メモリ位置が未占有であるなら、48ビット宛先アドレスをその中に格納する。メモリ位置が既に占有されており、その内容が48ビット宛先アドレスと一致する場合、アドレス・ルックアップ・テーブルに既に含まれているため、48ビット宛先アドレスを格納する必要はない。このように、アドレス・ルックアップ・テーブルの生成は遅い。
【０００９】
最下位5ビットによってポイントされたメモリ位置が既に占有されているが、内容が48ビット宛先アドレスと一致しない場合に問題が発生する。2個以上の異なる48ビット宛先アドレスによって32ビット圧縮アドレスの同じ最下位5ビットを生成することができるためこの状況が発生する。言い換えると、宛先アドレスの全48ビット未満を用いてアドレス・ルックアップ・テーブルをアドレス指定するとき、2個以上の異なる48ビット宛先アドレスが、アドレス・ルックアップ・テーブルの同じメモリ位置をポイントしてしまうことがある。これが発生すると、各48ビット宛先アドレスがアドレス・ルックアップ・テーブル内の自身のメモリ位置をポイントしなくなるため、異なるスキームを使ってアドレス・ルックアップ・テーブルをアドレス指定しなければならない。
【００１０】
故に、2個以上の異なる宛先アドレスがアドレス・ルックアップ・テーブルの同じメモリ位置をポイントするシナリオに適合かつ調整できるアドレス・ルックアップ・テーブルの生成のための方法および装置の必要がある。
〔発明の概要〕
本発明は、ルックアップ・テーブル生成の方法を提供する。この方法は、入力アドレスを受信し、入力アドレスから入力アドレスよりビットが少ない圧縮アドレスを生成し、圧縮アドレスから第1ビットセットを選択し、アドレス・ルックアップ・テーブルの第1ビットセットが指すメモリ位置が未占有メモリ・スロットを含むか否かを判定し、入力アドレスが、アドレス・ルックアップ・テーブルの第1ビットセットが指すメモリ位置に格納されたアドレスの何れかに一致するか否かを判定し、第1ビットセットが指すメモリ位置に未占有メモリ・スロットがなく、入力アドレスが第1ビットセットが指すメモリ位置に格納されたアドレスに一致しないことに応じて圧縮アドレスから第2ビットセットを選択する、各ステップを含む。
【００１１】
本発明はまた、ルックアップ・テーブル・ジェネレータを含む装置を提供する。ルックアップ・テーブル・ジェネレータは、入力アドレスを受信し、入力アドレスよりビットの少ない圧縮アドレスを生成するよう構成されたアドレス・コンプレッサを含む。バレル・シフタは、アドレス・コンプレッサに接続され、圧縮アドレスから第１ビットセットを選択するよう構成される。アドレス・ルックアップ・テーブルは、バレル・シフタに接続され、第１ビットセットが指すメモリ位置を含む。メモリ位置は少なくとも１個のメモリ・スロットを含む。コントロール・ステート・マシンは、バレル・シフタとアドレス・ルックアップ・テーブルに接続され、第１ビットセットが指すメモリ位置に未占有メモリ・スロットがなく、入力アドレスが第１ビットセットが指すメモリ位置に格納されたアドレスに一致しないことに応じて、圧縮アドレスから第２ビットセットを選択するようにバレル・シフタをシフトするよう構成される。
【００１２】
本発明の特徴と利点は、本発明の以下の詳細な説明と、本発明の原理を利用した実施例を記載する添付の図面を参照してよりよく理解される。
〔発明の詳細な説明〕
図1を参照すると、本発明による適合アドレス・ルックアップ・テーブル・ジェネレータ20が示される。ルックアップ・テーブル・ジェネレータ20は、複数のノードをネットワーク（例えば、ローカル・エリア・ネットワーク）にインターフェースするために用いる上述の各種ネットワーク装置（例えば、ネットワーク・ブリッジなど）に組み込むと特に便利である。ルックアップ・テーブル・ジェネレータ20をこれらネットワーク装置に用いてアドレス・ルックアップ・テーブルを生成することができる。
【００１３】
上述のように、複数のノードをネットワークにインターフェースするために用いる装置は一般に、アタッチメント・ポートを介してネットワークから入データ・パケットを受け取る。パケットは入パケット・コントローラに渡され、これがパケットから宛先アドレスを抽出する。ルックアップ・テーブル・ジェネレータ20はアドレス入力ノード22で抽出された宛先アドレスを受け取る。例として、アドレス入力ノード22で受け取る抽出された宛先アドレスは48ビット入力アドレスでよい。
【００１４】
ルックアップ・テーブル・ジェネレータ20は、ノード22から入力アドレス（すなわち、抽出された宛先アドレス）を受け取り、そこから入力アドレスよりビットの少ない圧縮アドレスを生成するよう構成されるアドレス・コンプレッサ24を含む。例として、アドレス・コンプレッサ24は、48ビット入力アドレスを本明細書で圧縮アドレスと称する32ビットデータに圧縮すると共に入力アドレスを分散データに変換するCRC32ジェネレータでよい。
【００１５】
バレル・シフタ26は、アドレス・コンプレッサ24の出力に接続される。バレル・シフタ26はアドレス・コンプレッサ24が生成した圧縮アドレスからビットセットを選択するよう構成される。圧縮アドレスから選択されたビットのセットは、所定数の圧縮アドレスの隣接ビットであるのが望ましい。しかしながら、選択されたビットセットは、必ずしも隣接している必要はない。さらに、図1に示す実施例では、バレル・シフタ26は圧縮アドレスから10ビットを選択する。10ビットの利用は単なる例で、あらゆる数のビットを圧縮アドレスから選択できることが理解される。
【００１６】
アドレス・ルックアップ・テーブル28は、バレル・シフタ26に接続される。アドレス・ルックアップ・テーブル28は、バレル・シフタ26が圧縮アドレスから選択したビットセットによりアドレス指定、またはポイントされたメモリ位置を含む。特に、圧縮アドレスから選択したビットセットをアドレス・ルックアップ・テーブル28のアクセス・キー・ポインタとして用いる。以下でさらに詳細に述べるように、本明細書では「バケット」とも称するアドレス・ルックアップ・テーブル28のメモリ位置は、1個以上のメモリ・スロットを含むことができる。
【００１７】
コントロール・ステート・マシン30はバレル・シフタ26とアドレス・ルックアップ・テーブル28に接続される。コントロール・ステート・マシン30は、ルックアップ・テーブル・ジェネレータ20のオペレーションを制御する。例えば、コントロール・ステート・マシン30は、バレル・シフタ26をシフトするシフト・コントロール・インプットを生成し、バレル・シフタ26により異なるビットセットを圧縮アドレスから選択するよう構成される。一般に、このシフトは、バレル・シフタ26が選択した第1ビットセットにポイントされる（アドレス・ルックアップ・テーブルの）メモリ位置に未占有メモリ・スロットがなく、ノード22で受信した入力アドレスが第1ビットセットでポイントされるメモリ位置に格納されたアドレスと一致しないことに対応して行われる。
【００１８】
コントロール・ステート・マシン30は、アドレス・ルックアップ・テーブルの第1ビットセットにポイントされるメモリ位置に未占有メモリ・スロットが含まれるか否か、および入力アドレスがアドレス・ルックアップ・テーブルの第1ビットセットにポイントされるメモリ位置に格納されるアドレスと一致するか否かの判定を調整する。未占有メモリ・スロットの判定は、以下に詳細に述べる。入力アドレスが格納されたアドレスと一致するか否かの判断はアドレス・コンパレータ32によって容易になる。アドレス・コンパレータ32は、ノード22で受信した入力アドレスを現在のメモリ位置の内容とアドレス・ルックアップ・テーブル28のメモリ・スロットと比較する。コントロール・ステート・マシン30は、アドレス・コンパレータ32にイネーブル信号を生成する。入力アドレスがアドレス・ルックアップ・テーブル28の内容の1つと一致する時、アドレス・コンパレータ32はアドレス一致信号34を出力し、入力アドレスが既にアドレス・ルックアップ・テーブル28に登録されていることを示す。
【００１９】
64ビットアドレス入力データ・レジスタ36は、アドレス入力ノード22とアドレス・ルックアップ・テーブル28に接続される。レジスタ36は48ビットアドレス入力と16ビットの制御データを保持する。制御データはコントロール・ステート・マシン30から転送される。レジスタ36の内容は、必要な時と場合にアドレス・ルックアップ・テーブル28に格納される。64ビットアドレス出力データ・レジスタ38はアドレス・ルックアップ・テーブル28とアドレス・ルックアップ・テーブル・コンパレータ32に接続される。レジスタ38は48ビットアドレスと、アドレス・ルックアップ・テーブル28から読み出される16ビットの制御データを保持する。
【００２０】
コントロール・ステート・マシン30は、アドレス・ルックアップ・テーブル28からアドレス出力データ・レジスタ38にデータを読み取るための読み取り信号と、アドレス入力データ・レジスタ36からアドレス・ルックアップ・テーブル28にデータを書き込むための書き込み信号を生成する。コントロール・ステート・マシン30は、アドレス・ルックアップ・テーブル28の内容をクリアするためのクリア・コマンド信号を生成する。コントロール・ステート・マシン30はまた、状態および入力信号に従って各入力アドレスに制御データを生成する。
【００２１】
図1に示すルックアップ・テーブル・ジェネレータ20の実施例はバケットタイプのアドレス・ルックアップ・テーブルを利用しているため、バケット・インデックス・ポインタ40を含む。バケット・タイプ・アドレス・ルックアップ・テーブルとバケット・インデックス・ポインタ40は、本発明のオプション機能である。バケット・タイプ・アドレス・ルックアップ・テーブルとバケット・インデックス・ポインタ40を含まない本発明によるルックアップ・テーブル・ジェネレータについて以下に述べる。
【００２２】
バケット・インデックス・ポインタ40のオペレーションは、アドレス・ルックアップ・テーブル28に用いることのできるフォーマットを示す図2を参照して最もよく説明される。アドレス・ルックアップ・テーブル28を多数のメモリ位置または「バケット」に分ける。図のように、バケットをアドレス・キーによってアドレス指定またはポイントする。アドレス・キーは、バレル・シフタ２６が選択するビットセットに相当する。言い換えると、バレル・シフタ26が（圧縮アドレスの32ビットから）選択した10ビットは、アクセス・キー・ポインタの最上位10ビット（MSB）に対応する。10ビットをアクセス・キー・ポインタに用いることにより、アドレス・ルックアップ・テーブル28は1024個のバケット（またはメモリ位置）を収容できる。
【００２３】
図2に示すバケット（またはメモリ位置）のそれぞれは複数のメモリ・スロットを含む。例えば、バケット#0は、8個の異なる入力アドレスを保持するため8個のメモリ・スロット42を含む。各バケットは通常、同じ数のメモリ・スロットを含む。例えば、図2に示すように、各バケットは8個のメモリ・スロットを含む。各バケットのメモリ・スロットは、バケット・インデックス・ポインタ40にアドレス指定またはポイントされる。バケット・インデックス・ポインタ40は、通常は各バケットのメモリ・スロットの数をサポートするのに十分なビットを含む。例えば、図1に示すバケット・インデックス・ポインタ40は、各バケットが最大8個のメモリ・スロットをサポートできるよう3ビットを生成する。バケット・インデックス・ポインタ40に生成されたこの3ビットはアクセス・キー・ポインタの最下位3ビット（LSB）として作用する。各バケットは8個のメモリ・スロットを含むため、アドレス・ルックアップ・テーブルは最大8,192個のアドレス入力を保持できる。
【００２４】
図3は、図2に示すメモリ・スロットのそれぞれに格納されたデータのフォーマット例である。8個のスロットはそれぞれオリジナルの48ビットのアドレス入力と16ビットの制御データを保持する。特に、48ビットアドレスはビット0-47に格納され、16ビットの制御およびポート情報はビット48-62に格納され、占有ビットはビット63に格納される。占有ビットが1個の場合、メモリ・スロットは既にアドレスを保持しており、占有ビットがゼロの場合、メモリ・スロットはアドレスを保持していない。
【００２５】
上述のように、メモリ・スロットが既に占有されているが、その内容が現在の48ビット入力アドレスと一致しない時、問題が発生する恐れがある。2個以上の異なる48ビット入力アドレスによりアドレス・コンプレッサ24が同じ出力を生成するため、この状況が発生し得る。これが発生すると、バケット・インデックス・ポインタ40がまだ最大値に等しくないと仮定し、バケット・インデックス・ポインタ40が次のメモリ・スロットに1だけインクリメントされる。コントロール・ステート・マシン30はバケット・インデックス・ポインタ40にインクリメント信号を生成する。次のメモリ・スロットも占有され、その内容が現在の48ビット入力アドレスと一致しない場合、バケット・インデックス・ポインタ40は再び次のメモリ・スロットに1だけインクリメントされる。このプロセスが、バケットに未占有メモリ・スロットが見つかるまで続く。未占有メモリ・スロットが見つかると、入力アドレスはその中に格納される。
【００２６】
バケットに未占有メモリ・スロットがなく、バケットに格納されたアドレスがどれも現在の入力アドレスと一致しない場合、本発明によると、コントロール・ステート・マシン30はシフト・コントロール入力を介してバレル・シフタ26をシフトする。図4を参照すると、このシフトにより、バレル・シフタ26はアドレス・コンプレッサ24の出力から異なるビット・セットを選択する。バレル・シフタ26は、ビット44の前のセットを1ビットでシフトし、異なる（新しい）ビット・セット46を形成できるよう、1ビットでシフトできる。しかしながら、バレル・シフタ26は、異なるビット・セットを選択するため1ビット以上でシフトできることが理解される。アドレス・コンプレッサ24の出力から異なるビット・セットを選択することにより、各48ビット入力アドレスが最終的にアドレス・ルックアップ・テーブル28の異なるバケット、あるいはメモリ位置をポイントすることになる。バレル・シフタ26へのシフト・コントロール入力は、コントロール・ステート・マシン30に含まれるシフト・コントロール・レジスタ31をインクリメントするコントロール・ステート・マシン30によって制御する。
【００２７】
バレル・シフタ26のシフトに加えて、コントロール・ステート・マシン30はアドレス・ルックアップ・テーブル28の内容全てをクリアするためクリア・コマンド信号を生成し、ルックアップ・テーブル・ジェネレータ20がルックアップ・テーブルの生成プロセスを再開できるようにする。コントロール・ステート・マシン30も、バケット・インデックス・ポインタ40をリセットするリセット信号を生成する。アドレス・コンプレッサ24から新しいビット・セットを選択し続け、アドレス・ルックアップ・テーブル28の内容をクリアすることで、ルックアップ・テーブル・ジェネレータ20はいずれアドレス・コンプレッサ24の出力にビット・セットを見つけ、それがアドレス・ルックアップ・テーブル28の異なるメモリ・スロットをそれぞれポイントする別の入力アドレスとなる。このように、バレル・シフタ26は、アドレス・キーが異なる全ての入力アドレスに適合されるまで、アドレス・キーに用いるビットを変更する。
【００２８】
図5A、5Bおよび5Cを参照し、コントロール・ステート・マシン30のオペレーションを詳細に説明する。オペレーション50の開始後、コントロール・ステート・マシン30は、クリア.・コマンド信号を起動することによって、アドレス・ルックアップ・テーブル28の全内容をクリアする初期化ステート52に入る。コントロール・ステート・マシン30は、バケット・インデックス・ポインタ40、シフト・コントロール・レジスタ31およびアドレス・コンプレッサ24もリセットする。
【００２９】
初期化ステート52が完了すると、コントロール・ステート・マシンはアイドル・ステート54に移行する。アイドル・ステート54中、コントロール・ステート・マシン30はアドレス入力有効信号23を待つ。ステップ56において、コントロール・ステップ・マシン30は、アドレス入力有効信号23が受け取られたか否かチェックする。アドレス入力有効信号23が高くなると、コントロール・ステート・マシン30はステート58に移る。
【００３０】
ステート58で、48ビット入力アドレスがアドレス入力データ・レジスタ36にロードされ、ステート60では、48ビット入力アドレスがアドレス・コンプレッサ24にロードされる。ステート62では、アドレス・コンプレッサ24は48ビット入力アドレスを圧縮し、32ビット圧縮アドレスを生成する。
圧縮アドレス生成後、コントロール・ステート・マシン30はアドレス・ルックアップ・テーブル28のアクセス・ステート64に移る。ステート64では、コントロール・ステート・マシン30は、アドレス・ルックアップ・テーブル28のメモリ・スロットの内容を読み出させるメモリ読み出し信号を生成する。読み出すメモリ・スロットは、バレル・シフタ26が選択したアドレス・コンプレッサ24の出力の10ビット（MSB10）でポイントするバケット内で、特定のメモリ・スロットは、バケット・インデックス・ポインタ40が生成する3ビット（LSB3）にポイントされるものである。ステート64の読み取りアクセスオペレーションが完了すると、読み取りデータの64ビットがステート66でアドレス出力データ・レジスタ38にロードされる。
【００３１】
アドレス出力データ・レジスタ38に読み取りデータをロードした後、コントロール・ステート・マシン30は占有ビット・ステート68のチェックに進む。ステート68では、コントロール・ステート・マシン30はレジスタ38の占有ビットをチェックする。図3に示すように、占有ビットはレジスタ38のビット数63である。占有ビットが1に等しい場合、コントロール・ステート・マシン30はイネーブル・アドレス・コンパレータ・ステート70に進む。
【００３２】
ステート70では、コントロール・ステート・マシン30はアドレス・コンパレータ32に対してイネーブル信号を起動する。ステート72では、アドレス・コンパレータ32は48ビット入力アドレスを、アドレス・ルックアップ・テーブル28から読み出したアドレス出力データ・レジスタ38（ビット0−47）の48ビットアドレスと比較する。入力アドレスとアドレス出力データ・レジスタ38の内容が一致する場合、アドレス一致出力信号34がステート74で起動され、コントロール・ステート・マシン30はアイドル・ステート54に戻る。入力アドレスとアドレス出力データ・レジスタ38の内容が一致しないと、コントロール・ステート・マシン30はバケット・インデックス・ポインタ・ステート76のチェックに進む。
【００３３】
チェック・バケット・インデックス・ポインタ・ステート76では、コントロール・ステート・マシン30はバケット・インデックス・ポインタ40がその最高値、この例では7に達したか否かを判定する。バケット・インデックス・ポインタ40が7に等しい場合、そのバケット（またはメモリ位置）はフルである。バケットには8個しかメモリ・スロットがないため、バケットはフルである。この条件は、8個以上の異なる入力アドレスが、アドレス・コンプレッサ24の出力において同じ圧縮アドレスを生成させ、バレル・シフタ26が選択した10ビットが同じになることを示す。故に、8個以上の異なる入力アドレスは、アドレス・ルックアップ・テーブル28で同じバケットをポイントすることになり、各バケットは8個のメモリ・スロットしか有しない。この条件が発生すると、コントロール・ステート・マシン30はインクリメント・シフト・コントロール・レジスタ・ステート78に進む。
【００３４】
ステート78に入ると、コントロール・ステート・マシン30がアドレス・ルックアップ・テーブル・アクセス・ステート64に戻るには実行すべきステップが3つある。まず、ステート78で、シフト・コントロール・レジスタ31をインクリメントして、バレル・シフタ26をシフトさせる。バレル・シフタ26をシフトすることで、アドレス・コンプレッサ24の出力から異なる10ビットのセットが選択され、アドレス・ルックアップ・テーブルをアドレス指定するために用いる別の10MSBが生じる。そして、ステート80において、コントロール・ステート・マシン30はバケット・インデックス・ポインタ40をリセットし、クリア・コマンド信号を起動することによってアドレス・ルックアップ・テーブル28の内容をすべてクリアする。これらステップが完了すると、コントロール・ステート・マシン30はアドレス・ルックアップ・テーブル・アクセス・ステート64に戻り、別の10MSBがポイントするバケットの第1メモリ・スロットを読み取る。
【００３５】
一方、ステート76において、バケット・インデックス・ポインタ40が7に等しくない場合、バケット・インデックス・ポインタ40はステート82においてインクリメントされる。すると、コントロール・ステート・マシン30はアドレス・ルックアップ・テーブル・アクセス・ステート64に戻り、そこで（同じバケットの）インクリメントされたバケット・インデックス・ポインタ40のポイントするメモリ・スロットが読み出される。
【００３６】
ステート68に戻り、占有ビットが1に等しくないと、占有ビットはステート84で1にセットされ、コントロール・ステート・マシン30は書き込みアクセス信号を出力する。ステート86では、コントロール・ステート・マシン30が書き込みアクセス信号を出力する。アドレス・ルックアップ・テーブル書き込みアクセスオペレーション中、コントロール・ステート・マシン30はアドレス入力データ・レジスタ36で占有ビットをセットしてから、アドレス入力データ・レジスタ36の内容をアドレス・ルックアップ・テーブル28の現在のメモリ・スロットに格納する。これが完了すると、コントロール・ステート・マシン30はアイドル・ステート54に戻る。
【００３７】
上述のように、本発明はまた、バケット・タイプ・アドレス・ルックアップ・テーブルとバケット・インデックス・ポインタ40を含まないルックアップ・テーブル・ジェネレータを含む。図6を参照すると、本発明による、バケット・タイプ・アドレス・ルックアップ・テーブルとバケット・インデックス・ポインタ40を含まないルックアップ・テーブル・ジェネレータ100が示される。
【００３８】
ルックアップ・テーブル・ジェネレータ100は、バケット方法を用いない。しかしながら、ルックアップ・テーブル・ジェネレータ20と同じ機能を持つ同一コンポーネントを多く含む。例えば、ルックアップ・テーブル・ジェネレータ100は、ノード22で受信した48ビット入力アドレスをアドレス出力データ・レジスタ38の内容と比較するアドレス・コンパレータ32を含む。入力アドレスがアドレス出力データ・レジスタ38の内容と一致する時、アドレス・コンパレータ32はアドレス一致信号34を出力し、アドレス・ルックアップ・テーブル102に既に登録されていることをアドレス入力に知らせる。ルックアップ・テーブル・ジェネレータ100もまた、48ビット入力アドレスを32ビット圧縮アドレスに圧縮するほか、入力アドレスを分散データに変換するアドレス・コンプレッサ24を含む。
【００３９】
64ビット・アドレス入力データ・レジスタ36は、48ビット入力アドレスと16ビットの制御データを保持する。このレジスタの内容は、上述のように必要な時、最終的にはアドレス・ルックアップ・テーブル102に格納される。64ビット・アドレス出力データ・レジスタ38は、48ビットのアドレス出力と16ビットの制御データを保持する。このレジスタの内容はアドレス・ルックアップ・テーブル102から読み出される。
【００４０】
ルックアップ・テーブル・ジェネレータ100は、線形アドレス・ルックアップ・テーブル102を用いる。図7は、アドレス・ルックアップ・テーブル・フォーマットを示す。単一のメモリ・スロットを各アドレス・キーに用いるが、これは各アドレス・キーまたはバケットに1個以上のメモリ・スロットを提供したアドレス・ルックアップ・テーブル28とは異なる。各メモリ・スロットはオリジナルの48ビット入力アドレスと16ビットの制御データを保有する。
【００４１】
各アドレス・キーは1つの関連メモリ・スロットしか持たないため、ルックアップ・テーブル・ジェネレータ100はバケット内のメモリ・スロットをポイントするのにバケット・インデックス・ポインタを必要としない。その代わり、単一メモリ・スロットをアドレス・コンプレッサ24の出力からバレル・シフタ26が選択したビットでのみアドレス指定、またはポイントされる。アドレス・ルックアップ・テーブル28と同じ数のメモリ・スロットに対処するため、ルックアップ・テーブル・ジェネレータ100のバレル・シフタ26はアクセス・キー・ポインタについて10ビットでなく13ビットを選択する。32ビット圧縮アドレスから13ビットを選択することで、8,192個のアドレス・キーが提供される。これは8,192個のメモリ・スロットに相当し、アドレス・ルックアップ・テーブル102が8,192個までアドレス入力を保持できることを意味する。しかしながら、必要なメモリ・スロット数により、バレル・シフタ26によって圧縮アドレスからどのような数のビットでも選択できることが理解される。
【００４２】
コントロール・ステート・マシン104はルックアップ・テーブル・ジェネレータ100のオペレーションを制御する。コントロール・ステート・マシン104は、上述のコントロール・ステート・マシン30と同じ機能の多くを提供する。例えば、コントロール・ステート・マシン104は、状態と入力信号により、アドレス・コンパレータ32にイネーブル信号、バレル・シフタ26にシフト制御信号、アドレス・ルックアップ・テーブル102に読み取り、書き込みおよびクリアのコマンド信号、および各48ビット入力アドレスに制御データを生成する。
【００４３】
しかしながら、コントロール・ステート・マシン104は、コントロール・ステート・マシン104がバケット・インデックス・ポインタを制御する必要がないという意味でコントロール・ステート・マシン30と異なるオペレーションを行う。このため、本発明によると、2個以上の異なる48ビット入力アドレスにより、アドレス・コンプレッサ24によって同じ圧縮アドレスが生成されると、バレル・シフタ26は直ちにシフトされ、バケット・インデックス・ポインタをインクリメントして同じバケット内の異なるメモリ・スロットをポイントするのではなく、別の13ビットセットを選択する。コントロール・ステート・マシン104はまた、この時にアドレス・ルックアップ・テーブル102の全内容をクリアする。言い換えると、バレル・シフタ26はより早くシフトされ、アドレス・ルックアップ・テーブルは、ルックアップ・テーブル・ジェネレータ20より早くクリアされる。このように、バレル・シフタ26は、アドレス・キーが別の入力アドレスに適合されるまでシフトされる。
【００４４】
コントロール・ステート・マシン104の詳細なオペレーションに関し、アドレス・コンパレータ32が使用可能になるポイントまでのオペレーションは主に図5Aに示すものと同じだが、アドレス・ルックアップ・テーブル・アクセス・ステート64が異なる。ステート64では、コントロール・ステート・マシン104はメモリ読み取り信号を生成し、これがアドレス・ルックアップ・テーブル102のメモリ・スロットの内容を読み取らせる。読み取られたメモリ・スロットは、バレル・シフタ26が選択したアドレス・コンプレッサ24の出力の13ビットによりポイントされる単一のメモリ・スロットである。バケット・インデックス・ポインタはルックアップ・テーブル・ジェネレータ20のように用いられない。ステート64の読み取りアクセス・オペレーションが完了すると、読み取りデータの64ビットがステート66でアドレス出力データ・レジスタ38にロードされる。
【００４５】
同様に、図5Cに示すアドレス・ルックアップ・テーブル書き込みアクセス・ステート86は主にルックアップ・テーブル・ジェネレータ100と同じだが、データが、バレル・シフタ26の選択した13ビットのポイントする単一メモリ・スロットに書き込まれるところが異なる。特に、ステート86では、コントロール・ステート・マシン104は書き込みアクセス信号を出力する。アドレス・ルックアップ・テーブル書き込みアクセス・オペレーション中、コントロール・ステート・マシン104はアドレス入力データ・レジスタ36に占有ビットをセットしてから、アドレス入力データ・レジスタ36の内容をバレル・シフタ26の選択する13ビットによりポイントされるアドレス・ルックアップ・テーブル102の単一メモリ・スロットに格納する。
【００４６】
コントロール・ステート・マシン104のオペレーションとコントロール・ステート・マシン30のオペレーションとの1つの違いは、コントロール・ステート・マシン104にバケット・インデックス・ポインタがないことに関する。故に、図5Bに示すオペレーションの部分は、コントロール・ステート・マシン104についてやや修正されており、図8に示す。図8を参照すると、ステート72および74は基本的に同じである。言い換えると、アドレス・コンパレータ32は48ビット入力アドレスを、アドレス・ルックアップ・テーブル102から読み出したアドレス出力データ・レジスタ38の48ビットアドレス（ビット0−47）と比較する。入力アドレスとアドレス出力データ・レジスタ38の内容が一致する場合、アドレス一致出力信号34をステート74で起動し、コントロール・ステート・マシン104はアイドル・ステート54に戻る。
【００４７】
しかしながら、コントロール・ステート・マシン104のオペレーションとの違いは、入力アドレスとアドレス出力データ・レジスタ38の内容が一致しない場合に何が発生するかである。チェック・バケット・インデックス・ポインタ・ステートに進む代わりに、コントロール・ステート・マシン104は直接、インクリメント・シフト・コントロール・レジスタ・ステート108に進む。
【００４８】
ステート108に入ると、コントロール・ステート・マシン30について上述した3ステップに対し、コントロール・ステート・マシン104がアドレス・ルックアップ・テーブル・アクセス・ステート64に戻る前に実行されるのは2ステップである。まず、ステート108で、シフト・コントロール・レジスタ106がインクリメントされ、バレル・シフタ26をシフトさせる。バレル・シフタ26のシフトにより、アドレス・コンプレッサ24の出力から別の13ビットのセットが選択され、アドレス・ルックアップ・テーブル102のアドレス指定に別の13ビットが用いられることになる。そして、ステート110で、コントロール・ステート・マシン104が、クリア・コマンド信号を起動することでアドレス・ルックアップ・テーブル102の全内容をクリアする。これらステップが完了すると、コントロール・ステート・マシン104がアドレス・ルックアップ・テーブル・アクセス・ステート64に戻り、別の13ビットがポイントする単一メモリ・スロットを読み込む。ステート110は、ルックアップ・テーブル・ジェネレータ100がバケット・インデックス・ポインタを含まないため、バケット・インデックス・ポインタのリセットを含まないことに注意する。
【００４９】
図9Aおよび9Bを参照すると、ルックアップ・テーブル・ジェネレータ20と100は、それぞれ複数のポートP1、P2…Pnを有し、複数のノードN1、N2…Nmをネットワークにインターフェースさせるために用いるあらゆるネットワーク装置120および122に組み込むことができる。このようなネットワーク装置120および122の例は、ハブ、スイッチ、ルータ、ゲートウェイ等である。
【００５０】
本発明の実施に際し、本明細書中に説明された本発明の実施例の各種代替を採用できることは理解されよう。以下の特許請求の範囲は、本発明の範囲を規定するものであり、これら特許請求の範囲内の構成および方法とそれらの均等物は、特許請求の範囲により包含されるものである。
【図面の簡単な説明】
【図１】  本発明による適合アドレス・ルックアップ・テーブル・ジェネレータを示す機能的ブロック図である。
【図２】  図1に示すアドレス・ルックアップ・テーブルに用いるアドレス・ルックアップ・テーブル・フォーマットを示すブロック図である。
【図３】  図2に示すルックアップ・テーブル・データ・フォーマットをより詳細に示すブロック図である。
【図４】  図1に示すバレル・シフタによるビット選択を示すブロック図である。
【図５Ａ】  図1に示すコントロール・ステート・マシンのオペレーションを示すフローチャートである。
【図５Ｂ】  図1に示すコントロール・ステート・マシンのオペレーションを示すフローチャートである。
【図５Ｃ】  図1に示すコントロール・ステート・マシンのオペレーションを示すフローチャートである。
【図６】  本発明による他のアドレス・ルックアップ・テーブル・ジェネレータを示す機能的ブロック図である。
【図７】  図6に示すアドレス・ルックアップ・テーブルに用いるアドレス・ルックアップ・テーブル・フォーマットを示すブロック図である。
【図８】  図6に示すコントロール・ステート・マシンのオペレーションの部分を示すフローチャートである。
【図９Ａ】  ネットワーク装置に組み込まれる図1および6の適合アドレス・ルックアップ・テーブル・ジェネレータを示すブロック図である。
【図９Ｂ】  ネットワーク装置に組み込まれる図1および6の適合アドレス・ルックアップ・テーブル・ジェネレータを示すブロック図である。
【図１】
0004021623.tif 000002
【図２】
0004021623.tif 000003
【図３】
0004021623.tif 000004
【図４】
0004021623.tif 000005
【図５Ａ】
0004021623.tif 000006
【図５Ｂ】
0004021623.tif 000007
【図５Ｃ】
0004021623.tif 000008
【図６】
0004021623.tif 000009
【図７】
0004021623.tif 000010
【図８】
0004021623.tif 000011
【図９Ａ】
0004021623.tif 000012
【図９Ｂ】
0004021623.tif 000013