(57)【特許請求の範囲】
【請求項１】
セル（１０）のヘッダ（１２）内に与えられる仮想接続情報に少なくとも部分的に基づいて通信網（２０）内の入力ポートから出力ポートへのセル（１０）の経路を選択する仮想経路／仮想チャンネル・ルックアップ方法であって、前記方法は前記仮想接続情報の少なくとも一部をハッシュ・コード化することを含み、前記ハッシュ・コード化は短縮された長さのハッシュ・コードを生成し、前記短縮された長さのハッシュ・コードを用いてルックアップ・テーブル（２０８ａ）内に記憶されている仮想接続情報にアクセスし、前記テーブル（２０８ａ）から得られた仮想接続情報に少なくとも部分的に基づいて前記ディジタル通信網（２０）内でセル（１０）の経路を選択し、
前記方法は更に、前記短縮された長さのハッシュ・コードにより指標を付けられた仮想接続情報を含むレコードを求めて前記ルックアップ・テーブル（２０８ａ）を探索し、前記探索の結果、同じ短縮された長さのハッシュ・コードにより指標を付けられた仮想接続情報を含む複数のレコードを返すことがあり、前記目的のセルの経路選択と一致する仮想接続情報を含む、前記探索の結果返されたレコードの中の１つだけを選択することを更に特徴とする、
仮想経路／仮想チャンネル・ルックアップ方法。
【請求項２】
前記ハッシュ・コード化は少なくとも仮想経路識別子と物理リンク識別子をハッシュ・コード化することを含むことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項３】
前記探索は前記短縮された長さのハッシュ・コードにに基づいて前記テーブル（２０８ａ）の２進探索を行うことを含むことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項４】
ハッシュ・コード化は前記仮想接続情報が活動状態の仮想経路に対応するかどうか試験して、前記試験の結果に基づいて前記仮想接続情報の少なくとも一部を選択的にマスクすることを含むことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項５】
前記選択的にマスクするステップは仮想チャンネル識別子を選択的にマスクすることを含むことを更に特徴とする、請求項４に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項６】
前記方法は前記短縮された長さのハッシュ・コードに基づいて探索テーブル・ポインタをルックアップすることを更に含み、また前記アクセスするステップは前記探索ポインタに少なくとも部分的に基づいて前記探索テーブル（２０８ａ）にアクセスすることを含むことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項７】
前記ハッシュ・コード化はＣＲＣ多項式割り算を行うことを含むことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項８】
前記ハッシュ・コード化はフィードバック・レジスタ（２０４ａ）とＸＯＲゲートの網（２０４ｂ）で少なくとも部分的に前記仮想接続情報を処理することを含むことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項９】
前記ハッシュ・コード化はハッシュ・コード化の副産物を生成することを含み、前記探索により前記ハッシュ・コードに対応する複数のレコード（２０９）を得、前記選択は前記ハッシュ・コード化の副産物に基づいて複数のレコード（２０９）の中の１つを選択することを含む、ことを更に特徴とする請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項１０】
前記探索は多重レベルの２進探索を行って、所定数の２進探索レベルの後で対応する接続レコードが見つからない場合は誤りを生成することを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項１１】
前記方法は２進探索トリーをバランスさせることを更に含み、また前記探索は前記バランスされた２進探索トリーを探索することにより行う、ことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項１２】
前記方法は、
物理層ＰＨＹおよび仮想経路識別子ＶＰＩの仮想接続情報に少なくとも部分的に基づいて活動状態の仮想経路接続ＶＰＣがあるかどうか判定することを更に含み、
前記探索は前記ハッシュ・コードにより指標を付けられた探索テーブル（２０８ａ）に基づいて活動状態の仮想チャンネル接続ＶＣＣがあるかどうか判定することを含む、
ことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項１３】
前記方法は物理層ＰＨＹと仮想経路識別子ＶＰＩの仮想接続情報に組合せに基づいて第１のテーブル内のレコード（２０２ａ）をルックアップして、前記第１のテーブルのルックアップに基づいて前記セルが活動状態の仮想経路接続を有するかどうかを判定することを更に含み、
前記探索は前記物理層ＰＨＹおよび仮想経路識別子ＶＰＩの仮想接続情報と仮想チャンネル識別子ＶＣＩの仮想接続情報の組合せに基づいて第２のテーブル（２０８ａ）内のレコードをルックアップして、前記第２のテーブルのルックアップに基づいて前記セルが活動状態の仮想チャンネル接続を有するかどうかを判定することを含む、
ことを更に特徴とする、請求項１に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項１４】
前記選択は物理層ＰＨＹおよび仮想経路識別子ＶＰＩと、ハッシュ・コード化され選択的にマスクされた仮想チャンネル識別子ＶＣＩに基づいて、第２のテーブル（２０８ａ）にアクセスすることを含むことを更に特徴とする、請求項１３に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項１５】
第２のテーブル（２０８ａ）内でルックアップされたレコードから得られた情報に基づいてセル（１０）の経路を選択するステップを更に特徴とする、請求項１３に記載の仮想経路／仮想チャンネル・ルックアップ方法。
【請求項１６】
仮想経路／仮想チャンネル・ルックアップ装置であって、ルータであって、セル（１０）のヘッダ（１２）内に与えられる仮想接続情報に少なくとも部分的に基づいて通信網（２０）内の入力ポートから出力ポートへのセル（１０）の経路を選択し、前記ルータは前記仮想接続情報の少なくとも一部をハッシュ・コード化するハッシュ・コーダ（２０４）を含み、前記ハッシュ・コーダ（２０４）は短縮された長さのハッシュ・コードを生成する、ルータと、前記短縮された長さのハッシュ・コードに基づいてテーブル（２０８ａ）内に記憶されている仮想接続情報にアクセスする手段と、テーブル（２０８ａ）から得られた仮想接続情報に少なくとも部分的に基づいてディジタル通信網（２０）内のセル（１０）の経路を選択する手段とを含み、
前記短縮された長さのハッシュ・コードを用いてテーブル（２０８ａ）内に記憶されている仮想接続情報にアクセスする手段は、前記短縮された長さのハッシュ・コードにより指標を付けられた仮想接続情報を含むレコードを求めて前記ルックアップ・テーブル（２０８ａ）を探索する探索および選択装置（２０８ｂ、２０８ｃ）を含み、前記探索の結果、同じ短縮された長さのハッシュ・コードにより指標を付けられた仮想接続情報を含む複数のレコードを返すことがあり、前記目的のセルの経路選択と一致する仮想接続情報を含む、前記探索の結果返されたレコードの中の１つだけを選択する、ことを特徴とする、
仮想経路／仮想チャンネル・ルックアップ装置。
【請求項１７】
前記ハッシュ・コーダ（２０４）は少なくとも仮想経路識別子と物理リンク識別子をハッシュ・コード化する手段を含むことを更に特徴とする、請求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項１８】
前記探索および選択装置（２０８ｂ、２０８ｃ）は前記ハッシュ・コードに少なくとも部分的に基づいて前記テーブル（２０８ａ）の２進探索を行う探索論理（２０８ｃ）含むことを更に特徴とする、請求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項１９】
前記装置は前記仮想接続情報が活動状態の仮想経路に対応するかどうか試験する装置（２０２ａ）と、前記試験の結果に基づいて前記仮想接続情報の少なくとも一部を選択的にマスクする手段（２０２ｂ）とを更に含むことを更に特徴とする、請求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２０】
マスクする手段（２０２ｂ）は仮想チャンネル識別子を選択的にマスクする手段を含むことを更に特徴とする、請求項１９に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２１】
前記ハッシュ・コーダはＣＲＣ多項式割り算を行う手段を含むことを更に特徴とする、請求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２２】
ハッシュ・コーダは前記仮想接続情報を処理するフィードバック・レジスタ（２０４ａ）とＸＯＲゲートの網（２０４ｂ）を含むことを更に特徴とする、請求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２３】
ハッシュ・コーダ（２０４）はハッシュ・コード化の副産物を生成する手段を含み、また探索および選択手段（２０８）は前記ハッシュ・コードに対応する複数のレコード（２０９）を選択する手段（２０８ｃ）と、前記ハッシュ・コード化の副産物に基づいて複数のレコード（２０９）の中の１つを選択する手段（２０８ｂ）を含む、ことを更に特徴とする請求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２４】
探索および選択装置（２０８）は、多重レベルの２進探索を行って、所定数の２進探索レベルの後で対応する接続レコードが見つからない場合は誤りを生成する手段（２０８ｃ）を含むことを更に特徴とする、請求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２５】
前記装置は２進探索トリーをバランスさせる手段を更に含み、また前記探索および選択装置（２０８）は前記バランスされた２進探索トリーを探索する手段（２０８ｃ）を含む、ことを更に特徴とする、詰求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２６】
前記装置は、
物理層ＰＨＹおよび仮想経路識別子ＶＰＩの仮想接続情報に少なくとも部分的に基づいて活動状態の仮想経路接続ＶＰＣがあるかどうかを判定する手段（２００）を更に含み、
前記探索および選択装置（２０８）は前記ハッシュ・コードにより指標を付けられた探索テーブルに基づいて活動状態の仮想チャンネル接続ＶＣＣがあるかどうかを判定する手段（２０８）を含む、
ことを更に特徴とする、請求項１６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２７】
前記ハッシュ・コーダ（２０４）はフィードバック・レジスタ（２０４ａ）とゲート・アレイ（２０４ｂ）を含むことを更に特徴とする請求項２６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２８】
前記装置は前記仮想接続情報が活動状態の仮想経路に対応するかどうかに基づいて前記仮想接続情報の一部を選択的にマスクする手段（２０２ｂ）を更に含むことを更に特徴とする、請求項２６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項２９】
探索および選択装置（２０８）は、前記仮想接続情報と、前記ハッシュ・コードにより指標を付けられた探索レコードの少なくとも一部とを比較する比較論理（２０８ｂ）を含むことを更に特徴とする、請求項２６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項３０】
テーブル（２０８ａ）は２進探索トリーを記憶する手段を含むことを更に特徴とする、請求項２６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項３１】
テーブル（２０８ａ）は、それぞれが仮想接続情報フィールドと、接続識別子フィールドと、低フィールドと、高フィールドを含む複数の探索レコード（２０９）を記憶するメモリを含むことを更に特徴とする、請求項２６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項３２】
ハッシュ・コーダ（２０４）は仮想経路識別子と、仮想チャンネル識別子と、物理リンク情報をハッシュ・コード化することを更に特徴とする、請求項２６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【請求項３３】
前記装置は、前記仮想接続情報が活動状態の仮想経路接続に対応するかどうかを判定する回路（２００）を更に含み、またテーブル（２０８ａ）は前記仮想接続情報が活動状態の仮想チャンネル接続に対応するかどうかを判定することを更に特徴とする、請求項２６に記載の仮想経路／仮想チャンネル・ルックアップ装置。
【発明の詳細な説明】
【０００１】
（関連出願の相互参照）
本発明は次のＰＣＴ文書に関連する。すなわち、ＷＯ−Ａ−９９０３２３５「ＡＴＭスイッチのためのＶＣマージング（ＶＣ  ＭＥＲＧＩＮＧ  ＦＯＲ  ＡＴＭ  ＳＷＩＴＣＨ）」、ＷＯ−Ａ−９９０３２３４「ＡＢＲサーバ（ＡＢＲ  ＳＥＲＶＥＲ）」、ＷＯ−Ａ−９９０３２９９「ＡＴＭマルチキャスト・セルの処理（ＨＡＮＤＬＩＮＧ  ＡＴＭ  ＭＵＬＴＩＣＡＳＴ  ＣＥＬＬＳ）」、ＷＯ−Ａ−９９０３２３６である。
【０００２】
（発明の分野）
本発明は通信網内のデータの転送に関するもので、より詳しくは、非同期転送モード（ＡＴＭ）網およびスイッチに用いられる効率的な接続ルックアップ技術に関する。更に特定すると、本発明はハッシング（ｈａｓｈｉｎｇ）および２進探索に基づいてＡＴＭスイッチの仮想経路／仮想チャンネル接続テーブル内の接続情報を効率的にルックアップする方法に関する。
【０００３】
（発明の背景）
非同期転送モード（ＡＴＭ）は次世代のディジタル通信用の主要なネットワーク化技術である。ＡＴＭは接続を用いる高速パケット交換技術であって、オーディオ、ビデオ、データなどの多くの異なる種類の情報を実時間で伝送するのに用いられる。
【０００４】
ＡＴＭは、各ＡＴＭデータ・パケット（ＡＴＭ用語で「セル」と呼ぶ）と、物理リンクで支援される所定の「仮想チャンネル」とを関連させる接続向けプロトコルを有する。各接続を２つのサブ・フィールド、すなわち仮想チャンネル識別子（ＶＣＩ）と仮想経路識別子（ＶＰＩ）、により識別する。これらのフィールドを用いて、網内のセルの多重化、多重分離、交換を行う。ＶＣＩとＶＰＩはアドレスではなく、接続を確立するときに接続の各セグメント（ＡＴＭスイッチ間のリンク）で明示的に割り当てられるもので、接続されている間そのまま継続する。
【０００５】
ＡＴＭスイッチが入力ポートに到着セルを受信すると、到着セルのＶＰＩとＶＣＩと入力ポートの物理的識別子に基づいてどの出力ポートにセルの経路を選択するか決定しなければならない。また次のＡＴＭ網セグメントによりセルの経路を正しく選択するために、ＡＴＭスイッチはセル・ヘッダで置き換える新しいＶＰＩとＶＣＩの値を決定しなければならない。一般にＡＴＭスイッチは、セル・ヘッダのＶＰＩおよびＶＣＩ情報と、入力ポートを識別する別の「物理層」（ＰＨＹ）情報に基づいて、ＶＰ／ＶＣ接続テーブル内のこの接続情報をルックアップする。ＡＴＭスイッチ内でのセルの処理量を最大にするには、接続テーブルの正しい接続情報にアクセスするための高速で効率的な方法と装置を提供することが重要である。
【０００６】
国際ＡＴＭ標準では、仮想経路識別子（ＶＰＩ）フィールドと仮想チャンネル識別子（ＶＣＩ）フィールドの大きさは次の通りである。
・  ＶＰＩフィールドは１２ビット長
・  ＶＣＩフィールドは１６ビット長
物理リンク識別子（ＰＨＹ）の代表的な大きさは５ビットである。したがって、これらの３フィールドの全長は３３ビット程度であって、約８９億（２３３）の組合せに対応する。しかし特定のＡＴＭスイッチが設定することのできる接続の最大数は一般にはるかに低い値（例えば１６Ｋ）に限られる。最も一般的には、ＡＴＭスイッチが設定するチャンネル用の識別子として、総数８９億のＰＨＹ、ＶＰＩ、ＶＣＩの組合せのどの任意の部分集合を用いることも可能である。問題は、ＰＨＹ、ＶＰＩ、ＶＣＩフィールド（例えば３３ビット長）を取り、それがビットの有効な組合せであることを確認し、ＡＴＭスイッチが保持することのできる接続数に適応する大きさの仮想経路／仮想チャンネル接続テーブル内の少数の（例えば１６Ｋの）接続の中の１つを指すポインタを出力することのできる、効率的な方法を見つけることである。
【０００７】
Ｓｈｔａｙｅｒ他の米国特許番号第５，４１４，７０１号はこの問題を解決する１つの方法を提供している。Ｓｈｔａｙｅｒ他の特許は、別個のリンク、仮想経路、仮想チャンネル・テーブルを階層的に配置したアドレス圧縮法について述べている。Ｓｈｔａｙｅｒ他では、ＰＨＹ情報は仮想経路ポインタを与える「リンク」テーブルに指標を付ける。仮想経路ポインタとセル・ヘッダのＶＰＩを用いて、多くの仮想経路テーブルの中の１つに指標を付ける。仮想経路テーブルは仮想チャンネル・オフセットを与え、仮想チャンネル・オフセットをセル・ヘッダのＶＣＩと共に用いて、多くの仮想チャンネル・テーブルの中の１つに指標を付ける。仮想チャンネル・テーブルは、ＡＴＭシステム内を通るデータの物理的な経路を選択するのに用いられる進入（ｉｎｇｒｅｓｓ）接続識別子を与える。
【０００８】
Ｓｈｔａｙｅｒ他の方法では、大きな、ほとんど用いない接続テーブルを使うことは避けられるが、リンク情報を用いてリンク・テーブルに指標を付け、リンク・テーブル内でルックアップした情報を用いて仮想経路テーブルに指標を付ける、などを行うので非常に時間がかかり、効率的でない。更に、Ｓｈｔａｙｅｒ他の複雑な階層構造を持つ別個のリンク、仮想経路、仮想チャンネル・テーブルを維持することは困難である。
【０００９】
Ｃｈａｎｄｒａｎｍｅｎｏｎ他の「パケット処理のためのパケット・ヘッダの交換（Ｔｒａｄｉｎｇ  Ｐａｃｋｅｔ  Ｈｅａｄｅｒｓ  ｆｏｒ  Ｐａｃｋｅｔ  Ｐｒｏｃｅｓｓｉｎｇ）」、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  Ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ  ｖｏｌ．４，ｎｏ．２，１４１−１５２（Ａｐｒｉｌ  １９９６）は、仮想回路識別子の代わりにフローＩＤとソース・ハッシュを用いて、データ・リンク、経路選択、トランスポート層のルックアップ・コストを下げる方法を教示している。
ＷＯ  ９７／１３３７７はハッシュ関数を用いて経路選択テーブルに指標を付けることにより、各仮想回路ＶＣＩ値は一意的なハッシュ値と、対応する一意的な指標を生成する。この文献によると、特定の得られたハッシュ・コードに対応するテーブル位置が現在占有されている場合は、ＶＣＩ値は、ハッシュ関数に入力したときに空いた場所を指す指標を生成する値に変えられる。変えられたＶＣＩ値は、出力するセル・ヘッダ内に置くようにとの命令と共に仮想回路上の前のノードに送られる。したがってこの文献では、仮想接続と、経路選択テーブルに指標を付けるのに用いられる一意的なハッシュ・コードとが１対１に対応する必要がある。このように確定すると、前のノードは、すでに用いられているハッシュ・コード指標を生成し得るＶＣＩ値を用いることができない、という欠点がある。
したがって、用いるＰＨＹ、ＶＰＩ、ＶＣＩの仮想接続の組合せの集合を制限することなく、ハッシュ化に基づいて仮想経路／仮想チャンネル・テーブルを効率的にルックアップすることが必要になる。
【００１０】
（発明の概要）
本発明はＡＴＭ接続テーブルをルックアップする新しい効率的な方法を提供するもので、ハッシュ・コード化および２進テーブル探索法を用いてテーブルおよびテーブル・ルックアップの数を最小にする。
【００１１】
仮想経路／仮想チャンネル・ルックアップ法は、前記セル（１０）のヘッダ（１２）内に与えられる仮想接続情報に少なくとも部分的に基づいて入力ポートから出力ポートへのセル（１０）の経路を選択する。仮想接続情報の少なくとも一部をハッシュ・コード化して、短縮された長さのハッシュ・コードを生成する。この短縮された長さのハッシュ・コードは、ルックアップ・テーブル（２０８ａ）内に記憶されている仮想接続情報に次のようにしてアクセスする。すなわち、（ａ）短縮された長さのハッシュ・コードにより指標を付けられた仮想接続情報を含むレコードを求めてルックアップ・テーブル（２０８ａ）を探索し、（活動状態にある特定の接続によっては、この探索の結果、同じ短縮された長さのハッシュ・コードにより指標を付けられた仮想接続情報を更に含む複数のレコードを返すことがある）、（ｂ）目的のセルの経路選択と一致する仮想接続情報を含む、探索の結果返された複数のレコードの中の１つだけを選択する。次にテーブル（２０８ａ）からアクセスした仮想接続情報に少なくとも部分的に基づいて、ディジタル通信網（２０）内のセル（１０）の経路を選択する。
【００１２】
上に述べた方法の利点は、短縮された長さのハッシュ・コードがＰＨＹ、ＶＰＩ、ＶＣＩの情報を圧縮して表現したものなので、用いることのできるＰＨＹ、ＶＰＩ、ＶＣＩの組合せの集合を制限することなく、テーブルのアドレス空間をＰＨＹ、ＶＰＩ、ＶＣＩの組合せの最大数よりはるかに小さくすることができる、ということである。しかしハッシュ・コード化を行うと情報が消失するので、ハッシュ・コード化により複数のＰＨＹ、ＶＰＩ、ＶＣＩの値が必然的に同じハッシュ・コードに変換される。探索テーブルは、各ハッシュ・コードに対応する複数の異なる探索レコードを保持して、ハッシュ・コードと、セルに関連するＰＨＹ、ＶＰＩ、ＶＣＩの情報とに基づいて、特定のレコードを選択して検索することができる。
【００１３】
この好ましい例では２進探索を用いて、探索テーブル内の特定の探索レコードの位置を効率的に見つける。この好ましい例では、探索テーブルは２進トリー構造で探索レコードを保持する。２進探索法により、ＡＴＭセルのＶＰＩ／ＶＣＩおよびＰＨＹ物理リンク識別子に対応する特定の探索レコードの位置を効率的に見つけることができる。
【００１４】
本発明により、用いるＰＨＹ、ＶＰＩ、ＶＣＩの組合せの集合を制限することなく、ハッシングと２進探索に基づいて仮想経路／仮想チャンネル・テーブル・ルックアップを効率的に行い、メモリ・アクセスの数を最小にすることができる。
【００１５】
（好ましい実施の形態の例の詳細な説明）
図１は、例えばＡＴＭスイッチが行うＶＰ／ＶＣルックアップの全過程の例を示す。この例では、ＡＴＭ網２０の或るセグメントから到着するＡＴＭセル１０は、標準ヘッダ１２とデータ・ペイロード１４を含む。ヘッダ１２は仮想接続情報、すなわち１２ビットの仮想経路識別子（ＶＰＩ）１６と１６ビットの仮想チャンネル識別子（ＶＣＩ）１８、を含む。更にこの例では、ＡＴＭセル１０に関連する物理的インターフェース情報（例えば、ＡＴＭスイッチ入力ポート識別子）を５ビットのＰＨＹフィールド２２が示す。
【００１６】
この例では、ＶＰＩ１６とＶＣＩ１８とＰＨＹ２２を用いて、仮想経路／仮想チャンネル接続（すなわち経路選択）テーブル１００内に記憶されている接続情報にアクセスする。ＡＴＭスイッチは経路選択テーブル１００の接続情報を用いてＡＴＭセル１０の経路を或るスイッチ出力ポートに選択し、また経路選択テーブルから新しいＶＰＩおよびＶＣＩフィールドを得て、ＡＴＭ網２０の次のセグメントが用いるようセル・ヘッダ１０を置き換える。
【００１７】
この例では、任意の時刻にＡＴＭスイッチが維持することのできる接続の最大数は１６Ｋである。したがって、接続テーブル１００は最大１６Ｋ（２１４）の項目（ＡＴＭスイッチが保持することのできる異なる接続ごとに１つ）を記憶する。異なるＡＴＭスイッチでは保持する接続の数が異なって良い。一般に接続テーブル１００の大きさは、用いる特定のＡＴＭスイッチの能力と一致するように決める。この例では接続テーブル１００は１６Ｋの項目を記憶するので、接続テーブル内の特定の接続レコードを一意的に識別子するには１４ビット長のチャンネル識別子が必要である。
【００１８】
（簡単なルックアップ過程）
この例では、ルックアップ機能５０は接続テーブル１００内の項目をルックアップするため、ＰＨＹ２２、ＶＰＩ１６、ＶＣＩ１８の組合せに基づく１４ビット長のチャンネル識別子を備える。この例のルックアップ機能５０は、図２の例示の簡単なルックアップ過程に示す次の３つの別個のステップから成る。
１．  ＰＨＹ、ＶＰの直接ルックアップ（ステップ５２）、
２．  ハッシュ・コード化および探索ポインタのルックアップ（ステップ５４）、
３．  テーブルの探索（ステップ５６）。
テーブルを探索すると（ステップ５６）１４ビットの接続すなわちチャンネルＩＤが得られるので、これを用いてＶＰ／ＶＣ接続テーブル１００内の接続情報をルックアップする（ステップ５８）。
【００１９】
簡単なレベルでは、直接ルックアップ・ステップ５２はＰＨＹ２２とＶＰＩ１６の組合せが活動状態の仮想経路接続（ＶＰＣ）に対応するかどうか決定する。対応する場合は、到着したＡＴＭセル１０内のＶＣＩフィールド１８はルックアップに関係ない。すなわち、これは任意の値で良いので修正なしで交換される。したがって、直接ルックアップ・ステップ５２でＰＨＹ２２、ＶＰＩ１６の情報が活動状態の仮想経路接続に対応することが分かった場合は、次のハッシュ・コード化および探索ポインタのルックアップ・ステップ５４を行う前に直接ルックアップ・ステップでＶＣＩフィールド１８をマスクする。
【００２０】
簡単に述べると、ハッシュ・コード化および探索ポインタのルックアップ・ステップ５４の目的は、ＰＨＹ、ＶＰＩ、（マスクされた）ＶＣＩの組合せから短縮された長さのハッシュ・コードを生成することである。好ましい例では、得られたハッシュ・コードを探索ステップ５６で直接または間接に用いて、探索テーブル内に記憶されているチャンネル識別子をルックアップする。この好ましい例では、ステップ５４で作られたハッシュ・コードを、位置ごとに探索テーブルへのポインタを含む第２のルックアップ・テーブルへのアドレスとして用いる。ステップ５６ではこの探索ポインタ（およびセルの仮想接続情報）を用いて、探索テーブル内の対応する接続情報をルックアップする。
【００２１】
ステップ５４でハッシュ・コード化を行うと情報が消失するので、多くの活動状態の接続がハッシュ・コード化されて同じ値になることがある。この場合は、探索ステップ５６で同じハッシュ・コードを持つ全ての接続について探索しなければならない。好ましい例では、ステップ５６で２進探索を用いて探索テーブルへのアクセスの数を最小にする。図３は、探索テーブル内に保持され、ステップ５６で行う２進探索に用いられるＶＰ／ＶＣ２進探索トリーの例を示す。
【００２２】
（更に詳細なＶＰ／ＶＣルックアップ・システムの例）
図４は、図２に示すルックアップ過程５０を行う仮想経路／仮想チャンネル・ルックアップ・システム２００の例を示す。この例では、
・  ＶＰＣルックアップ／ＶＣＩマスク・ブロック２０２は図２の直接ルックアップ・ステップ５２を行う。
・  ハッシュ・コード化ブロック２０４とポインタ・ルックアップ・ブロック２０６は図２のステップ５４を行う。
・  探索ブロック２０８は図２の探索ステップ５６を行う。
【００２３】
この例では、ＶＰＩ１６とＰＨＹ２２がＶＰＣルックアップ／ＶＣＩマスク・ブロック２０２に入力される。ブロック２０２はＰＨＹ、ＶＰＩの組合せ（１７ビット）を取り、この組合せが活動状態の仮想経路接続（ＶＰＣ）であるかどうかを示す１ビットのデータ情報を読み出す。この単一テーブル２０２ａはリンク情報を与えるのではなく、ＶＰＩとＰＨＹに基づいて活動状態の仮想経路接続情報を出力する。更に詳細に述べると、この例のブロック２０２は１２８Ｋ×１ビットＲＡＭで構成する直接ルックアップ・メモリ２０２ａを含む。直接ルックアップ・メモリ２０２ａは、例えば可能なＰＨＹ、ＶＰＩの組合せ毎に、その組合せが活動状態の仮想経路接続（ＶＰＣ）であるか、そうでない（ＮＯ）かを示す単一ビットの出力を出す。
【００２４】
良く知られているように、活動状態の接続は２種類ある。すなわち、活動状態の仮想経路接続（ＶＰＣ）と活動状態の仮想チャンネル接続（ＶＣＣ）である。ＶＰＣはＶＰＩフィールド（およびＰＨＹ）により識別される。ＶＣＩフィールドはこの場合はスイッチには関係ない。或る活動状態のＶＰＣに属する全てのセルは同じ方法で交換されるので、チャンネル・テーブル内の正しい項目を見つけるにはＶＣＩフィールドをマスクしなければならない。この例では、ＰＨＹ、ＶＰＩテーブル２０２ａをチェックした後でこれを行う。
【００２５】
ＶＣＣはＰＨＹとＶＰＩとＶＣＩにより識別される。この場合は、異なるＶＣＩ（ただしＰＨＹとＶＰＩは同じ）を持つセル１０は異なる接続に属する。スイッチはＶＰＣとＶＣＣを同時に支援して良い。
【００２６】
上に述べたように、この例の第１のテーブル２０２ａ（ＰＨＹ、ＶＰＩ）は、セルが活動状態のＶＰＣに属するかどうかを示す。活動状態のＶＰＣの場合はＶＣＩフィールドをマスクする。活動状態のＶＰＣでない場合は、活動状態のＶＣＣであるか、または不正なＶＰＩ、ＶＣＩの組合せである。この例では、この後者の決定は探索テーブル２０８ａを用いて行う。
【００２７】
したがってこの例では、セル１０のＰＨＹ、ＶＰＩの情報が活動状態の仮想経路接続に対応する場合は、セル内のＶＣＩフィールド１８は無関係である（すなわち、任意の値で良く、修正なしで交換される）。仮想経路接続が活動状態の場合は、マルチプレクサ２０２ｂ（または他のハードウエアまたはソフトウエアのマスク機能）がＶＰＩフィールド１６を（次の段階でこのビット・フィールドを用いる前に）マスクして全て０にする。すなわち、ＰＨＹ、ＶＰＩ、０である。この例でＶＰ接続が活動状態でない場合は、ＶＣＩフィールド１８をマスクしない。マルチプレクサ２０２ｂから出力された、この選択的にマスクされたＶＣＩフィールド１８を、図４ではＶＣＩ’で示す。
【００２８】
またこの例では、上に述べたマスク機能は全てのＶＣＩ≦３１（または１５）をマスクして０にする。その理由は、これらのＶＣＩ値は仮想経路に関する操作および保全を行うために保留されているからである。すなわち、これらのＶＣＩ値を仮想チャンネルに用いることはできない。このようなセル１０が到着すると、或る仮想経路に属するものとして処理される（たとえＶＰＣ／ＶＣＩルックアップ・テーブル２０２ａが、この仮想経路は活動状態でないとに示す場合でも）。
【００２９】
この例のハッシュ・コード化ブロック２０４は、３３ビットのＰＨＹ、ＶＰＩ、（マスクされた）ＶＣＩ’の組合せから１４ビットのハッシュ・コードを生成する。この例では、ハッシュ・コード化ブロック２０４は、短縮された（圧縮された）長さの書式のＰＨＹ、ＶＰＩ、ＶＣＩ’の組合せを表す１４ビット長のハッシュ・コードを生成する。これを行う１つの方法は、３３ビット値からＣＲＣ１４の値を生成することである。形式的にこれを行うには、３３ビットの値の後に１４個のゼロを付加して４７ビットの値を生成して次数４７の多項式として扱い、これを次数１４の生成多項式で割る。生成多項式は、例えばｘ１４＋ｘ１３＋ｘ１１＋ｘ９＋１である。他の多くの多項式も使える。ＣＲＣは割り算が終わったときに残る余りである。この特定のＣＲＣ１４ハッシュ・コード化を効率的に行う１つの方法は、１４ビットのフィードバック・レジスタ２０４ａと多数のＸＯＲゲート２０４ｂの複合網を用いることである。当業者が理解するように、他のハッシュ・コード化装置および／または実現法を用いても良い。
【００３０】
この例では、ハッシュ・コード化ブロック２０４が生成するハッシュ・コードを用いて第２のルックアップ・テーブル２０６にアドレスする。テーブル２０６は、位置ごとに探索テーブル２０８を指す１４ビットのポインタを含む。この例では、ポインタ・ルックアップ・テーブル２０６はそれぞれ１４ビット長の１６Ｋの項目（全体の大きさは２２４Ｋビット）を有する。必要な場合は、テーブル２０６は接続の最大数より大きくて良い（例えば１６ｋ接続の場合に３２ｋ）。この利点は、より多くのハッシュ・コード（より多くのトリー）があるので、完全な２進トリーへの確率が減ることである。
【００３１】
探索ブロック２０８は、活動状態のＡＴＭスイッチ接続に対応する探索レコード２０９を記憶する探索テーブル２０８ａを含む。ハッシュ・コード化ブロック２０４がハッシュ・コード化を行うと情報が消失するので、ハッシュ・コード化された多くの活動状態の接続が、ポインタ・ルックアップ２０６により生成される同じポインタになる。この場合は、探索ブロック２０８は、セル１０の接続に対応する１つの探索レコード２０９を見つけるために同じハッシュ・コードを持つメモリ２０８ａ内の全ての接続を探索しなければならない。この例では、探索テーブル２０８は２進探索を用いて、探索のステップ数（例えば、探索テーブル２０８ａへのアクセスの数）を最小にする。
【００３２】
理論的には、１６Ｋの接続がハッシュ・コード化されて全て同じ値になり得る。これは２進探索の深さが１４レベルでなければならないことを意味する。しかしこの確率は無視できる程度であって、実際にＡＴＭスイッチを実現する場合には更に省略された探索を用いて良い。例えば、４レベルの探索の場合は１５のＰＨＹ、ＶＰＩ、ＶＣＩ’の組合せがハッシュされて同じコードになることがある。その結果、接続を確立中に１６番目の（空いた）ＰＨＹ、ＶＰＩ、ＶＣＩ’の値をハッシュした値が１５個の他の活動状態の接続がすでにハッシュされている値と同じであると、これを用いることができない。これが起こる確率は非常に小さく、約  Ｎ／｛ｅ（ｎ＋１）！｝である。ただし、ｎはもしトリーの場合の大きさ、Ｎは探索テーブルの大きさ（ｅ＝２．７１８．．）である。ｎ＝１５かつＮ＝１６Ｋのとき、この確率は１０−９より小さい（シミュレーションによりこれを確認することができる）。したがって障害となる場合もあり得るが（すなわち、完全な２進探索トリーのため、空いたＰＨＹ、ＶＰＩ、ＶＣＩの組合せを用いることができないが）、ＰＨＹ、ＶＰＩ、ＶＣＩを「通常」使用する場合はこれを全く無視してよい。
【００３３】
例示の実施の形態では、探索テーブル２０８内の各探索レコード２０９は次のフィールドを含む。
・  ＰＨＹ／ＶＰＩ／ＶＣＩの組合せフィールド２１０ａ（３２ビット）、
・  チャンネル識別子フィールド２１０ｂ（１４ビット）、
・  低ポインタ・フィールド２１０ｃ（１４ビット）、
・  高ポインタ・フィールド２１０ｄ（１４ビット）。
したがってこの例の探索テーブル２０８ａの大きさは、１６Ｋに７５ビットを掛けた値、すなわち１．２メガビットである。
【００３４】
２進探索にＶＰＩ、ＶＣＩを用いると、見つかる場合と見つからない場合がある。見つかる場合はＶＣＣは活動状態にある。見つからない場合はＶＣＣは活動状態にない。テーブル２０２ａと２０８ａを接続した全体の効果は次のように要約することができる。
活動状態のＶＰＣ：  ＰＨＹ、ＶＰＩの組合せが第１のテーブル２０２ａ内に見つかる。ＶＣＩはマスクされる。ハッシュおよび２進探索により接続番号（接続テーブル２０８ａ内の項目）が得られる。
活動状態のＶＣＣ：  ＰＨＹ、ＶＰＩの組合せが第１のテーブル２０２ａ内に見つからない（＝ＶＰＣなし）。ハッシュおよび２進探索の後にＰＨＹ、ＶＰＩ、ＶＣＩの組合せが見つかり、接続番号が探索テーブル２０８ａから読み出される。
不正なＶＰＩ、ＶＣＩ：  ＰＨＹ、ＶＰＩが第１のテーブル２０２ａ内に見つからない（＝ＶＰＣなし）。ハッシュおよび２進探索の後にＰＨＹ、ＶＰＩ、ＶＣＩの組合せが探索テーブル２０８ａ内に見つからない。
【００３５】
したがってこの例では、或る意味では、ＶＰＣが活動状態であることは第１のテーブル２０２ａ内で直ぐ分かるが、活動状態のＶＣＣが活動状態であることはハッシュおよび２進探索（探索が「ヒット」）の後に間接的に探索テーブル２０８ａ内で分かる。
【００３６】
図３および図４において、探索ブロック２０８が探索を行うとき、１乃至１５のレコード２０９（１）−２０９（１５）を含む２進探索トリーの「根」探索レコード２０９（１）にアクセスするには、ポインタ・ルックアップ２０６が生成する１４ビットのポインタを用いる。比較ブロック２０８ｂで、ＡＴＭセル１０に関連するＰＨＹ２２、ＶＰＩ１６、（マスクされた）ＶＣＩ’の情報と、アクセスされた探索レコード２０９内のＰＨＹ／ＶＰＩ／ＶＣＩ’の組合せフィールド２１０ａとを比較する。セル１０に関連するＰＨＹ、ＶＰＩ、（マスクされた）ＶＣＩ’の組合せがアクセスされた探索レコード２０９内に記憶されている値に等しい場合は、探索論理２０８ｃは探索を止めてこのレコードからチャンネル識別子２１０ｂを読み出す。セル１０に関連するＰＨＹ、ＶＰＩ、ＶＣＩ’の値が、アクセスされた探索レコード２０９内に記憶されている値より小さいと比較ブロック２０８ｂが判定した場合は、低ポインタ２１０ｃを読み出し、これを用いて２進探索トリーの他の（特定の整理された）探索レコード２０９（２）にアクセスする。セル１０に関連するＰＨＹ、ＶＰＩ、ＶＣＩ’の値が、アクセスされた探索レコードのフィールド２１０ａの値より大きいと比較ブロック２０８ｂが判定した場合は、探索論理２０８ｃは高ポインタ２１０ｄを読み出し、これを用いて２進探索トリーの他の（特定の整理された）探索レコード２０９（９）にアクセスする。４回探索してもヒットがない場合は、探索論理２０８ｃは「不正なセル」（誤り）信号を生成してセル１０を捨てる。
【００３７】
一致するＰＨＹ、ＶＰＩ、ＶＣＩ’の値を含む該当レコード２０９が見つかると、そのレコードのチャンネル識別子２１０ｂを、接続に関する全ての情報が記憶されているＶＰ／ＶＣ接続テーブル１００の項目として用いる。
【００３８】
ハッシュ・コード化ブロック２０４によりハッシュされて同じハッシュ・コードになった２つのＰＨＹ、ＶＣＩ、ＶＰＩの組合せは、上に述べたＣＲＣ多項式割り算により異なる１９ビットの商を与える。探索テーブル２０８ａの大きさを縮小するため、探索レコード２０９内の全部で３３ビットのＰＨＹ／ＶＣＩ／ＶＰＩの組合せの代わりにＣＲＣ多項式割り算の商（１９ビット）を記憶してメモリ空間を節約することができる。この代わりの方法では、商を出力するためにハッシュ・コード化ブロック２０４内に更に追加の（多数の）ＸＯＲゲートが必要である。
【００３９】
（ソフトウエア・ドライバ機能の例）
新しい接続を設定するときは、正しい情報を各テーブル２０２ａ、２０６、２０８ａ内に記憶しておかなければならない。図５はソフトウエア・ドライバ接続設定の接続の例を示す。図５に示すステップは、任意の望ましい順序で行っても同じ結果が得られる。
【００４０】
図５に示すように、ドライバ（または他のＡＴＭスイッチの呼の経路選択過程）は該当する接続情報をＶＰ／ＶＣ接続テーブル１００に記憶しなければならない（図５、ブロック３０２）。ドライバ・ソフトウエアは、ＰＨＹ、ＶＰＩ、ＶＣＩ’の組合せに基づいてハッシュ・コード化ブロック２０４が計算する（ドライバはこの計算をソフトウエアで、および／またはハードウエア支援を用いて行う）同じ１４ビットのハッシュ・コードを計算しなければならない（図５、ブロック３０４）。次にドライバは、同じハッシュ・コードを持つチャンネルが探索テーブル２０８ａ内にすでに存在するかどうか判定する（図５、決定ブロック３０６）。同じハッシュ・コードを持つチャンネルがすでに存在する（決定ブロック３０６の「はい」出口）場合は、ドライバは探索テーブル２０８ａ内にすでに記憶されている既存の２進探索トリーに新しい「葉」を追加しなければならない。同じハッシュ・コードを持つチャンネルが探索テーブル２０８ａ内に存在しない場合は、ドライバは探索テーブルに新しい探索トリーの「根」を追加して（図５、ブロック３１０）、新しいハッシュ・コード・ポインタをポインタ・ルックアップ・テーブル２０６に記憶しなければならない（図５、ブロック３１２）。またドライバは、新しい接続が確立されたことを示すためにＶＰＣテーブル２０２ａを更新しなければならない（図５、ブロック３１４）。
【００４１】
この例では、ドライバは２進探索トリーを整理された状態に保持して、２進探索が機能するようにする役目を持つ。したがって新しい探索トリーの葉を追加するには（ブロック３０８）、この例のドライバは新しいＰＨＹ、ＶＰＩ、ＶＣＩの組合せを持つ探索テーブル２０８ａを探索して、既存の探索トリー内の正しい（整理された）位置に新しい葉を挿入する。接続の設定と解除の履歴によっては探索トリーがアンバランスになることがある。例えば、特定の探索トリー用の「根」レコード２０９に関連するＰＨＹ、ＶＰＩ、ＶＣＩの組合せが比較的高いまたは比較的低い値を持つことがある。これは、２進探索トリーが完全でない（すなわち、枝や葉が１５より少ない）のに新しい組合せのための場所を見つけることができないことを意味する。この場合は、ドライバはまず項目を線形に整理し、次に中央の項目を根として取り、続いて上部および下部のサブトリーに進むというようにしてトリーを構築することにより、トリーをバランスさせなければならない。項目数が１５以下なので、この手続きには余り時間がかからない。新しい探索トリーができると、ドライバは新しいトリーを、正しいチャンネル識別子２１０ｂと共に探索テーブル２０８ａ内の別の（空いた）位置に置く。これが済むと、ドライバはルックアップ・テーブル２０６内のポインタを更新して新しい根を指す。この後で、古いトリーを除去（すなわち上書き）して良い。
【００４２】
図６は、ソフトウエア・ドライバの接続解除過程の例を示す。接続を解除するときドライバは探索トリーを再構成するが、これは余り複雑ではない。解除される接続が葉にある場合は（決定ブロック３２４の「はい」出口）、単に葉を除去する（ブロック３２６）。除去される接続が枝にある場合は枝を除去して、代わりに上位のトリー内の最低の接続、または下位のトリー内の最高の接続で置き換える。例えば図３において葉２０９（２）を除去することは、この葉を葉２０９（５）または２０９（７）で置き換えることである。残りのサブトリーを再構成する必要はない。根を除去し且つ葉がある場合は、葉で根を置き換える。他の葉がなくて根を除去する必要がある場合は（決定ブロック３２４の「はい」出口）、この過程は探索トリーの根レコード２０９（１）を削除し（図６、ブロック３２８）、ポインタ・ルックアップ２０６内の関連するポインタを削除する（図６、ブロック３３０）。またドライバ（または他の呼の経路選択過程）はＶＰＣテーブル２０２ａを更新して、接続がすでに活動状態でないことを示して良い（図６、ブロック３３２）。
【００４３】
このように本発明はＡＴＭ接続テーブル・ルックアップに新しい効率的な方法を提供するものであって、ハッシュ・コード化および２進テーブル探索方法を用いることによりテーブルおよびメモリのルックアップの数を最小にする。到着するＡＴＭセルに関連する仮想接続情報をハッシュ・コード化する。ハッシュ・コードは仮想接続情報を圧縮して表現したものであって、これによりハッシュ・コードがアクセスするテーブルのアドレス空間を、用いられる仮想接続組合せの集合を制限することなく、ＡＴＭセル・ヘッダ内でコード化される可能な仮想接続組合せの最大数よりはるかに小さくすることができる。２進探索を用いて、セルの接続に対応する特定の探索レコードの位置を効率的に、すなわち比較的少ないメモリ・アクセス（例えば、１＋１＋４＊２＝１０）で見つけることができる。
【００４４】
本発明について現在最も実際的で好ましいと考えられる実施の形態に関して説明したが、理解されるように、本発明はここに開示された実施の形態に限定されるものではなく、特許請求の範囲に含まれる種々の修正や同等の装置を含むものである。
【図面の簡単な説明】
本発明が提供する特徴と利点は、ここに説明した好ましい例示の実施の形態を以下の図面に関連して参照すれば良く理解することができる。
【図１】  図１は、仮想経路／仮想チャンネル・ルックアップの全過程にＶＰＩ、ＶＣＩ、ＰＨＹ仮想接続情報を用いる方法の例を示す。
【図２】  図２は、ハッシュ・コード化および２進探索に基づく、ＶＰ／ＶＣ情報の効率的なルックアップの簡単な過程の例を示す。
【図３】  図３は、ＶＰ／ＶＣ２進探索トリーの例を示す。
【図４】  図４は、ＶＰ／ＶＣルックアップ装置の例を示す。
【図５】  図５は、接続設定過程の例を示す。
【図６】  図６は、接続解除過程の例を示す。
【図１】
0003901942.tif 000002
【図２】
0003901942.tif 000003
【図３】
0003901942.tif 000004
【図４】
0003901942.tif 000005
【図５】
0003901942.tif 000006
【図６】
0003901942.tif 000007