(57)【特許請求の範囲】
【請求項１】
複数のポートを有するデータ通信スイッチにおいてパケット優先順位をリマップする方法であって、
第１のポート上で第１の優先順位値を含んでいるパケットを受信するステップと、
複数の値に基づいて仮想トランク値を決定するステップと、
前記第１の優先順位値および前記仮想トランク値に基づいて第２の優先順位値を決定するステップと、
第２のポート上で前記第２の優先順位値を含んでいるパケットを送信するステップとを備え、
前記複数の値が、前記第１のポートの識別子とＶＬＡＮ識別子を含んでいる方法。
【請求項２】
前記ＶＬＡＮ識別子が、受信時にパケット内に含まれる、請求項１に記載の方法。
【請求項３】
前記第１の優先順位値が、受信時にパケット内に含まれる、請求項１に記載の方法。
【請求項４】
前記第２の優先順位値が、送信時にパケット内に含まれる、請求項１に記載の方法。
【請求項５】
前記仮想トランク値を決定するステップが、前記複数の値をより小さいビットの値に縮小するステップと、前記より小さいビットの値をテーブルルックアップにおいて使用するステップを含んでいる、請求項１に記載の方法。
【請求項６】
複数のポートを有するデータ通信スイッチにおいてパケット優先順位をリマップする方法であって、
第１のポート上で第１の優先順位値を含んでいるパケットを受信するステップと、
前記第１の優先順位値、および第１のポートの識別子を含んでいる複数の他の値に基づいて、第２の優先順位値を決定するステップと、
第２のポート上で前記第２の優先順位値を含んでいるパケットを送信するステップを備え、
前記複数の他の値がさらに、ＶＬＡＮ識別子を含んでいる方法。
【請求項７】
前記ＶＬＡＮ識別子が、受信時にパケット内に含まれる、請求項６に記載の方法。
【請求項８】
前記第１の優先順位値が、受信時にパケット内に含まれる、請求項６に記載の方法。
【請求項９】
前記第２の優先順位値が、送信時にパケット内に含まれる、請求項６に記載の方法。
【請求項１０】
第１の優先順位値を含んでいるパケットを受信するポートを有するアクセスコントローラと、
前記アクセスコントローラからパケットを受信し、前記パケットに応答して複数の値を第１のエレメントに送信し、前記複数の値に応答して第１のエレメントから仮想トランク識別子を受信し、前記仮想トランク識別子および前記第１の優先順位値を第２のエレメントに送信し、前記仮想トランク識別子および前記第１の優先順位値に応答して第２のエレメントから第２の優先順位値を受信し、前記第２の優先順位値を含んでいるパケットを送信する、前記アクセスコントローラに結合された交換エンジンとを備え、
前記複数の値が、ポートの識別子を含み、
アクセスコントローラにおいて受信されたパケットが、ＶＬＡＮ識別子を含んでいる、データ通信スイッチ用のネットワークインタフェース。
【請求項１１】
前記複数の値が、前記ＶＬＡＮ識別子を含んでいる、請求項１０に記載のネットワークインタフェース。
【請求項１２】
第１の優先順位値およびＶＬＡＮ識別子を含んでいるパケットを受信するポートを有するアクセスコントローラと、
前記アクセスコントローラからパケットを受信し、複数のデータベースを調べて、前記ポートの識別子、前記ＶＬＡＮ識別子、前記第１の優先順位値を含んでいる複数の値から第２の優先順位値を解決し、前記第２の優先順位値を含んでいるパケットを送信する、前記アクセスコントローラに結合された交換エンジンとを備えている、データ通信スイッチ用のネットワークインタフェース。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
【従来の技術】
ＩＥＥＥ（米国電気電子学会）が公布した「Ｖｉｒｔｕａｌ  ＢｒｉｄｇｅｄＬｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ」と称する標準８０２．１Ｑ（Ｓｔｄ．８０２．１Ｑ）は特に、ブリッジされたＬＡＮ（ローカルエリアネットワーク）における、トラフィックの優先順位付けに対応する規約を定義する。この標準は、標準８０２．１Ｑ準拠のパケットを生成する際に、パケット内でタグをインスタンス化するための規約を含んでいる。タグは特に、仮想ＬＡＮ（ＶＬＡＮ）識別子および優先順位を含んでいることがある。一般的にＶＬＡＮ識別子は、パケットがどこで送信されるのかを決定するように適用され、優先順位はパケットが他のパケットと比較してどれほど速く処理されるのかを決定するよう適用される。
【０００２】
【発明が解決しようとする課題】
標準８０２．１Ｑ準拠のパケットがネットワーク内の各ブリッジを通過する際について、規約は、受信される際のパケット内のタグ優先順位（すなわちインバウンドタグの優先順位）を「再生成」すること、および送信される際のパケット内の再生成優先順位（すなわちアウトバウンドタグの優先順位）をインスタンス化することについて規定する。標準によると、アウトバウンドタグの優先順位はインバウンドタグの優先順位と異なることがあり、順位は、ブリッジがパケットを受信する物理ポート、およびインバウンドタグの優先順位に基づいて、各ブリッジ上で独自に決定されることがある。ただしこの標準には、アウトバウンドタグの優先順位を決定する際にその他の値を使用するための規約はない。インバウンドタグの優先順位および受信する物理ポート以外の値に基づいてアウトバウンドタグの優先順位を決定することが望ましい。
【０００３】
【課題を解決するための手段】
本発明は、パケット内でのインスタンス化の優先順位がパケットからの優先順位および複数の他の値に基づいて決定される、ソース学習ブリッジングをサポートするＬＡＮスイッチなどのデータ通信スイッチのための優先順位処理法を提供する。複数の他の値は、受信ポートの識別子およびパケットからのＶＬＡＮ識別子を含んでいることもある。パケットは、標準８０２．１Ｑに準拠してフォーマットされた「タグ付き」のパケットでもよい。複数の他の値は初めに解決して仮想トランク識別子としてもよく、この仮想トランク識別子を、パケットからの優先順位とともに適用して、パケット内でのインスタンス化について優先順位を決定してよい。複数の他の値をより小さいビットの値に還元し、そのより小さいビット値をテーブルルックアップにおいて使用することにより、仮想トランク識別子を解決することもできる。
【０００４】
本発明のこれらの態様、および他の態様は、添付の図面と合わせて下記の詳細な説明を参照することにより、より効果的に理解されよう。
【０００５】
【発明の実施の形態】
図１に、本発明が効果的に機能するＬＡＮスイッチ１００を示す。スイッチ１００は、インタフェース１０１〜１０９によりそれぞれ駆動されるパケットバス１１１〜１１９のマトリックスを含んでいる。インタフェース１０１〜１０９は、それぞれ１つまたは複数のＬＡＮ１２１〜１２８に関連付けられたネットワークインタフェース１０１〜１０８、および管理インタフェース１０９を含んでいる。各バスは、パケットデータをバス上で送信する独占権を有するインタフェース１０１〜１０９のうち１つとのインタフェースをなすルート（すなわちルートインタフェース）、およびパケットデータをバスから受信する複数のインタフェース１０１〜１０９とのインタフェースをとるリーフ（すなわちリーフインタフェース）を有する。各インタフェースは、バス１１１〜１１９のうち１つの上でルートインタフェースであり、かつバス１１１〜１１９の、バスについてルートインタフェースであるバスを含むすべてのバス上でリーフインタフェースであることが好ましい。パケットは、バス１１１〜１１９上をクロックサイクル当たり１バーストの速度で一連の定ビットデータバーストとして送信されることが好ましい。バス１１１〜１１９は、ブロードキャスト指向であり、バス上を伝搬されるすべてのデータバーストは、インタフェース１０１〜１０９すべてに到達する。パケットデータを送信および受信することに加え、管理インタフェース１０９はスイッチ１００の「中枢センター」として機能し、ネットワークインタフェース１０１〜１０８がそれらと関連付けられたＬＡＮ１２１〜１２８上でネットワーク装置のアドレスを学習することを、管理バス（図示していない）上に情報を送信することにより補助する。無論、上記で説明したルート−リーフ構造は、本発明に従って動作するスイッチの多くの可能な構造の１つである。可能な他の構造は、インタフェース間、あるいはインタフェース間の単一の共通バス、あるいは二地点間接続の「フルメッシュ」のマトリックスを有することもある。
【０００６】
基本的な一操作において、スイッチ１００は、ソース学習ブリッジング機能に対応する。例として、パケットが、ネットワークインタフェース１０１と関連付けられたＬＡＮ１２１の１つにあるネットワーク装置（図示していない）上を発する。そのパケットは、発信元のネットワーク装置のソースアドレス、およびパケットがユニキャストパケットである場合は、通信が意図されるネットワーク装置の宛先アドレスを含んでいる。メディアアクセス制御（ＭＡＣ）アドレスなどのレイヤ２（データリンク）アドレスが企図される。ＬＡＮのブロードキャスト性により、パケットはインタフェース１０１に到達する。パケットのソースアドレスがインタフェース１０１で認識されない場合、パケットは管理コントローラ１０９に提出され学習操作を受け、その結果アドレスがインタフェース１０１上で「学習」される。すなわち、アドレスがインタフェース１０１上でアクティブなアドレスのリストに加えられる。その後インタフェース１０１は、パケットバス１０１〜１０９から受信される、学習されたアドレスを宛先アドレスとして有するいずれのパケットも、ＬＡＮ１２１の１つにあるネットワーク装置を宛先とするものであると認識し、転送するためにそのようなパケットを取り込む。
【０００７】
パケットバス１０１〜１０９から受信されたパケットについて実行される宛先アドレスのチェックは、「フィルタリング」チェックと呼ばれることが多い。これは、インタフェース１０１によって学習されたアドレスを宛先アドレスとして持たないパケットが、一定の除外を受け、インタフェース１０１により落とされる、すなわち「フィルタにかけられる」からである。フィルタリングチェックは、インタフェース１０１〜１０９により、バス１１１〜１１９から受信される各パケットに対して個々に行われる。パケットを転送するかあるいはフィルタするかについての決定は一般に、上記で説明したように、そのパケットが、以前にインタフェースによって学習された宛先アドレスを含んでいるかどうかに基づいて行われる。ただしインタフェース１０１〜１０９はこのような決定の結果を共有し、どのインタフェースによっても宛先アドレスが学習されていないパケットをフィルタすることを防止している。このような「宛先が知られていない」パケットは、すべてのインタフェースにより取り込まれる。より詳細には、例示的フィルタリングチェックにおいて、インタフェースは以下のフィルタ規則を適用する。
【０００８】
１．以前にインタフェースによって学習された宛先アドレスをパケットが有する場合、フィルタリングチェックをパスする。パケットは取り込まれる。
【０００９】
２．以前にインタフェースによって学習されていない宛先アドレスをパケットが有し、かつ宛先アドレスが以前に別のインタフェースによって学習されている場合、フィルタリングチェックをパスしない。パケットは取り込まれない。
【００１０】
３．以前にインタフェースによって学習されていない宛先アドレスをパケットが有し、その宛先アドレスが以前に別のインタフェースによって学習されていない場合、フィルタリングチェックをパスする。パケットは取り込まれる。
インタフェース１０１〜１０９は、パケットを取り込む決定に関して相互に通知するために、クレームライン（図示していない）にアサートすることが好ましい。
【００１１】
上記で説明したようにソース学習ブリッジング機能に対応する以外に、スイッチ１００は本発明が主な意図とする優先順位処理に対応する。優先順位処理は、標準８０２．１Ｑ準拠のイーサネットパケットなど、それと関連付けられたタグ優先順位を有するパケットに関連して使用するよう企図されるものである。
【００１２】
図２では、ネットワークインタフェース１０１〜１０８の典型例であるネットワークインタフェース２００を参照して、好適な優先順位処理を説明する。インタフェース２００は、ＬＡＮおよび交換エンジン２１１に結合されたアクセスコントローラ２０１を含んでいる。コントローラ２０１はパケットをＬＡＮから受信し、それをフォーマットしエンジン２１１に送信する。コントローラ２０１は、エンジン２１１からもパケットを受信し、それをフォーマットしＬＡＮ上に送信する。エンジン２１１は、優先順位処理を容易にするためのエレメントに結合され、そのエレメントには仮想トランクファインダ２２１、優先順位リマップデータベース２３１、ＣＡＭ（連想記憶装置）２４１、転送データベース２５１、待ち行列リマップデータベース２６１が含まれる。詳細には、エンジン２１１はコントローラ２０１からパケットを受信し、それを進入優先順位処理に加え、インタフェース２００がルートであるバス１１１〜１１９のうち１つを介して送信する。エンジン２１１は、バス１１１〜１１９からもパケットを受信し、そのうち選択したパケットを退出優先順位処理に加え、コントローラ２０１に送信する。進入優先順位処理は、仮想トランクファインダ２２１、優先順位リマップデータベース２３１、ＣＡＭ２４１、転送データベース２５１の補助により行われ、一方退出優先順位処理は、ＣＡＭ２４１、転送データベース２５１、待ち行列リマップデータベース２６１の補助により行われる。
【００１３】
図３から図１６では、ＬＡＮの１つからインタフェース２００で受信されるフォーマットの、標準８０２．１Ｑ準拠のイーサネットパケット（以降「タグ付き」パケット）を参照して、スイッチ１００における優先順位処理をより詳細に説明する。まず図３を参照すると、インバウンドパケット３００は、宛先ＭＡＣアドレス（ＤＡ０〜ＤＡ５）、続いてソースＭＡＣアドレス（ＳＡ０〜ＳＡ５）、タグ（ＴＡＧ０〜ＴＡＧ３）、タイプ−長さの情報（ＴＬ０およびＴＬ１）をそれぞれ含んでいる。タイプ−長さの情報の後には追加の情報が続き、それは通常ＩＰ（インターネットプロトコル）のヘッダを含んでおり、それについて最初の４つのバイトをＤ０〜Ｄ３と示す。
【００１４】
アクセスコントローラ２０１において、インバウンドパケット３００はタグ付きパケットとして識別され、進入処理準備完了フォーマットに置かれ、交換エンジン２１１に送信される。タグ付きパケットであるとの識別は、タグの部分（ＴＡＧ０およびＴＡＧ１）を参照することにより行われ、パケットがタグ付きパケットである場合、ＩＥＥＥ８０２．１Ｑ標準で定義されるように、その部分はｘ８１００の値を有する。図４には進入準備完了パケット４００が２バイトの幅で示されているが、これは、図示する実施形態でパケット４００がコントローラ２０１からエンジン２１１に２バイトのバーストで送信されることを反映している。ただし他の実施形態では、送信は異なる幅で送信されることがあることは理解されよう。パケット４００は、インバウンドパケット３００が受信される物理ポートを識別する物理ポート識別子（ＰＯＲＴ）、それに続き、パケット４００をタグ付きパケットであると識別する制御情報（ＣＴＲＬ）を含んでいる。ＣＴＲＬの次にはタグの部分（ＴＡＧ２およびＴＡＧ３）が続き、それは標準８０２．１Ｑで定義されるタグ制御情報（ＴＣＩ）を有する。より詳細には、ＴＣＩは、３ビットのインバウンドタグの優先順位、１ビットの基準フォーマット標識、１２ビットのＶＬＡＮ識別子を含んでいる。パケット４００の残りの部分は、インバウンドパケット３００内で行われるのと同様にフォーマットされる。インバウンドパケットがタグ付きでない場合、ＣＴＲＬは、対応する進入準備完了パケットにこの条件を指示し、そのようなパケットにはＴＣＩが付加されないことに留意されたい。
【００１５】
交換エンジン２１１において、パケット４００は進入優先順位処理を受け、パケット４００を、インタフェース２００がルートであるバス上で送信するのに備える。ＣＴＲＬを参照することにより、エンジン２１１はパケット４００をタグ付きパケットとして識別する。パケット４００が識別されると、エンジン２１１はパケット４００から、ＰＯＲＴ、ＣＴＲＬ、ＴＡＧ２、ＴＡＧ３（その中の１２ビットのＶＬＡＮ識別子も含んでいる）を除去する。ＰＯＲＴは、スイッチ１００上で固有の８ビットの仮想ポート識別子（ＶＰＩ）にリマップされる。これに関して、ネットワークインタフェース１０１〜１０８の２つ以上が、同一の物理ポート識別子で表される物理ポートを有すること、およびパケット４００内のＰＯＲＴをＶＰＩにリマップすることにより、生じうるあいまいさを有利に解決することが理解されよう。ＶＰＩおよび１２ビットのＶＬＡＮ識別子はペアとして、それぞれ入力ライン５１１および５１２上を通じて、仮想トランクファインダ２２１に提出される。
【００１６】
仮想トランクファインダ２２１で、２０ビットのＶＰＩ／ＶＬＡＮ識別子ペアは、仮想トランク識別子（ＶＴＩ）を解決するために使用される、１０ビットのハッシュキーに還元される。この還元により、ここで説明したＶＴＩを解決するためのような、識別子を解決するためのインデックスベースのルックアップ体系を実施するのに必要なＲＡＭのサイズが縮小されることが理解されよう。次に図５および図６を参照すると、エンジン２１１により送信されたＶＰＩ／ＶＬＡＮのペアは、マルチプレクサアレイ５１０で受信される。アレイ５１０は互い違いに配列されたマルチプレクサ６１１〜６２０のアレイであり、これはＶＰＩ／ＶＬＡＮのペアを、異なるＶＰＩ／ＶＬＡＮペアを互いに区別する際に最も効果的であるとハッシングアルゴリズムが判断した、ＶＰＩ／ＶＬＡＮペア中のビット位置からのビットを含んでいるハッシュキーに還元する。ＶＰＩ／ＶＬＡＮのペアは異なる部分集合にパースされ、それぞれ入力ライン６０１〜６１０上でマルチプレクサ６１１〜６２０により受信される。入力ライン６０１〜６１０の異なるラインにより送信された部分集合は互い違いに配列され、集合体中のマルチプレクサ６１１〜６２０が、ＶＰＩ／ＶＬＡＮペア中のいずれの１０ビットの組合せから、アレイ５１０に適用されたビット選択コマンドに従って、ハッシュキーを選択できるようにする。従って例えば、入力ライン６０１はビットゼロを１２ビットのＶＰＩ／ＶＬＡＮペアを通じて送信し、入力ライン６０２はビット１を１３ビットのペアを通じて送信し、入力ライン６０３はビット２を１４ビットのペアを通じて送信することができる、などである。マルチプレクサ制御５２０の補助により、各マルチプレクサ６１１〜６２０は、入力ライン６０１〜６１０のうちそれと関連する１つから単一のビットを選択し、選択したビットだけを送信する。任意選択で、マルチプレクサ制御５２０は、マルチプレクサ６１１〜６２０のうち１つまたは複数に、入力ライン６０１〜６１０のうちそれと関連するライン上のすべてのビットを無視し、自動的に０の値を選択させることもある。ＶＰＩ／ＶＬＡＮペアの選択されたビットおよびゼロの値は、出力ライン６３１〜６４０を通じて送信され、ともにハッシュキーを形成する。
【００１７】
マルチプレクサのビット選択は、マルチプレクサ制御５２０により指示を受ける。制御５２０は、ハッシュマスクを記憶するためのメモリエレメントおよび関連する論理を含んでいる。ハッシュマスクは、入力ライン５２１上でプログラムおよび更新されると有利である。ハッシュマスクについての値はハッシングアルゴリズムにより計算され、アレイ５１０が受信したいずれのＶＰＩ／ＶＬＡＮペアをも、ＶＰＩ／ＶＬＡＮペアを互いに区別する際に最も効果的であるとハッシングアルゴリズムが判断した、ビット位置からのビットを含んでいるハッシュキーに変換できるようにする。選択を容易にするために、制御５２０は、マスクライン６３１〜６４０を介してマルチプレクサ６１１〜６２０に結合される。制御５２０は、各マルチプレクサ６１１〜６２０について、ハッシュマスクからビット選択コマンドを決定し、ビット選択コマンドをマスクライン６３１〜６４０上に送信する。各ビット選択コマンドは、もしある場合はＶＰＩ／ＶＬＡＮペアの単一のビットを識別すれば十分であり、マルチプレクサ６１１〜６２０のそれぞれをハッシュキー内に含んでいるために選択する。したがって、例えばマルチプレクサ６１１によりライン６３１上で受信されたビット選択コマンドは、マルチプレクサ６１１に対して、ハッシュキー内に含んでいるために、もしある場合は１２ビットのＶＰＩ／ＶＬＡＮペアを通じてビット０のうち１つを選択するよう命令し、またマルチプレクサ６１２によりライン６３２上で受信されたビット選択コマンドは、マルチプレクサ６１２に対して、もしある場合は１３ビットのＶＰＩ／ＶＬＡＮペアを通じてビットの１つを選択するよう命令する、などである。ハッシュキーは、入力ライン５３１を送信されるオフセットとともに、仮想トランクマッチ制御５３０に送信され、ともに仮想トランクハッシュＲＡＭ（ランダムアクセスメモリ）５４０に対するポインタを形成する。これに関して、ハッシュＲＡＭ５４０は２つのテーブルを含んでおり（テーブル１およびテーブル２）、そのうち１つはオフセットに従って任意の所与の時間に選択される。
【００１８】
ハッシュＲＡＭ５４０から戻された１つまたは複数のＶＰＩ／ＶＬＡＮペアと連想比較をする際の被比較数として使用するために、２０ビットのＶＰＩ／ＶＬＡＮペアも、ここでより詳細に説明する方法で仮想トランクマッチ制御５３０で受信される。図７を参照すると、マッチ制御５３０はハッシュＲＡＭ５４０とのインタフェースをなし、ハッシュキーおよびオフセットから形成されたポインタを使用して連想比較を実行する。ポインタは、ハッシュＲＡＭ５４０に対する最初のポインタとして使用され、その値がポインタと一致するインデックスと関連付けられたエントリの内容を検索する。ポインタは、テーブル内のリンクされたエントリのリストのウォークスルーを開始させることができ、それはＶＰＩ／ＶＬＡＮペアについて一致するものが見つかるか、あるいはリンクされたリストの最後に到達するまで続行する。より詳細には、テーブル７００は対応するインデックスにおけるエントリ内容を含んでいる。エントリ内容は各エントリについて、ＶＰＩ／ＶＬＡＮペア、ＶＴＩ、およびある場合は「次のエントリ」キーを含んでいる。図示する例でテーブル７００は、Ｎ個のリンクされたリストすなわち「バケット」を形成する、Ｎ個のエントリ部分集合を含んでいる。第１のバケットは、インデックス７０１および７０９を含んでいる。第２のバケットは、インデックス７０２、７０５、７０７、７１０を含んでいる。第３のバケットは、インデックス７０３および７０８を含んでいる。Ｎ番目のバケットは、インデックス７０４および７０６を含んでいる。ポインタが例えばインデックス７０２をポイントし、対応するエントリからのＶＰＩ／ＶＬＡＮペアがマッチ制御５３０内のＶＰＩ／ＶＬＡＮペアと一致しない場合、エントリからの「次のエントリ」キー（インデックス７０５を識別する）がインデックス７０５に対するポインタとして使用される。インデックス７０５に対応するエントリから戻されたペアが一致しない場合、エントリからの「次のエントリ」キー（インデックス９０７を識別する）がインデックスセット７０７に対するポインタとして使用される。マッチ制御５３０は、一致するものが見つかるまでこのハッシュＲＡＭ１２０のウォークスルーを続行する。マッチ制御５３０は、一致するエントリに関連付けられたＶＴＩをマッチ制御５３０に戻し、出力ライン５３１を通じて交換エンジン２１１に転送する。
【００１９】
仮想トランクマッチ制御５３０は、ハッシングアルゴリズムの効率も追跡し、効率が十分に低下した場合はいつでも、出力ライン５３２を通じて外部プロセッサ（図示していない）に通知する。詳細には、制御５３０は、失敗した試みごとにメモリ内の値を増分し、ハッシュＲＡＭ５４０から戻されたＶＰＩ／ＶＬＡＮペアを被比較数と照合させる。効率が最低限の効率基準を下回った場合、制御５３０は、出力ライン５３２を通じてプロセッサに不履行通知を送信し、プロセッサにハッシングアルゴリズムを再計算させ、入力ライン５２１上のハッシュマスクを更新させる。失敗した試みの集合体数、特定のウォークスルーについて失敗した試みの最高回数、各ウォークスルーについて失敗した試みの平均回数、失敗した試みの回数を上回った頻度などの検討に基づいて、さまざまな最低限の効率基準を実施することができる。最低限の効率基準は、マッチ制御５３０上で設定することができる。ハッシュマスクが変更される場合は、ハッシュＲＡＭ５４０内のエントリを、新しくインデックスされた位置に必ず書き換えなければならないことは理解されよう。エントリの書き換えは、もう一方を書き換えながらルックアップ用の１つのテーブルを使用し、またハッシュＲＡＭ５４０にアクセスする目的のために、書き換えについてのルックアップの優先順位を容認することにより、効率に与えるインパクトを最低限に抑えて実行される。
【００２０】
次に図８では、優先順位リマップデータベース２３１をより詳細に図示する。データベース２３１は、インバウンドタグの優先順位および解決されたＶＴＩに基づいて、進入準備完了パケット４００に関してアウトバウンドタグの優先順位を決定する。詳細には、交換エンジン２１１は、パケット４００のインバウンドタグの優先順位、および仮想トランクファインダ２２１から受信したＶＴＩを、データベース２３１に提出する。インバウンドタグの優先順位およびＶＴＩは、データベース２３１内の対応するインデックスに対するポインタとして使用され、データベースはアウトバウンドタグの優先順位を返す。
【００２１】
優先順位リマップデータベース２３１内で実行されるアウトバウンドタグの優先順位決定とは無関係に、交換エンジン２１１はＣＡＭ２４１および転送データベース２５１を調べ、パケット４００について優先順位選択をする。図２に戻り、ＣＡＭ２４１は、インタフェース２００と関連付けられたＬＡＮ上にあるネットワーク装置の学習されたアドレスを、種々のＣＡＭインデックスで保持するエントリを有する。転送データベース２５１は、ＣＡＭ２４１内で共通のインデックスによりこれらのエントリにリンクされたエントリを保持する。パケット４００中のソースアドレスはＣＡＭ２４１に提出され、ＣＡＭ２４１はソースアドレスがあるＣＡＭインデックス（以降、ソースＣＡＭインデックス、すなわちＳＣＩ）を返す。図９を参照すると、ＳＣＩは、転送データを検索するために、データベース２５１中のリンクされたエントリに対するポインタとして使用され、またパケット４００の優先順位選択標識を含んでおり、それはエンジン２１１に戻される。下記でより詳細に説明するように、優先順位選択標識は、そのタグ優先順位に関して、パケット４００にスイッチ１００におけるサービスの質を与えるか与えないかを決定する。データベース２５１は図示するように、特定のインデックスに、優先順位選択標識およびローカル優先順位待ち行列識別子を含んでいる。ローカル優先順位待ち行列識別子は、この説明においては進入優先順位処理に関係しないが、下記で説明する退出優先順位ベースの処理において実施されると有利である。パケット４００中のソースアドレスがまだ学習されていない場合、ＣＡＭ２４１からは有効なＳＣＩは戻されず、代わりに仮想トランクファインダ２２１から戻されたＶＴＩを使用して別のデータベース（図示していない）をインデックスし、パケット４００について優先順位選択を行うことに留意されたい。
【００２２】
交換エンジン２１１は、ローカルパケットヘッダを進入準備完了パケット４００（以前に除去されたＰＯＲＴ、ＣＴＲＬ、ＴＡＧ２、ＴＡＧ３は少ない）に付加し、パケットを退出準備完了フォーマットにする。図１０には、退出準備完了パケットのローカルパケットヘッダ１０００を図示する。ヘッダ１０００は、ＳＣＩ、または有効なＳＣＩがＣＡＭ２４１から戻されない場合は、ＶＴＩおよびＶＴＩがインタフェース２００から発したものであると識別するのに十分なインタフェース識別子を含んでいる。これに関して、ネットワークインタフェース１０１〜１０８の２つ以上が、同一のＶＴＩによって表されるＶＰＩ／ＶＬＡＮペアを有し、また生じうるあいまいさを追加のビットが有利に解決することが理解されよう。ヘッダ１０００はさらに、有効なＳＣＩが戻されたか戻されていないかを識別する「無効ＳＣＩ」標識を含んでいる。詳細には、「無効ＳＣＩ」標識がセットされる場合、退出準備完了パケットが管理インタフェース１０９により取り込まれて「ソース学習」を受け、その結果ソースアドレスがＣＡＭ２４１に追加される。ヘッダ１０００は、優先順位リマップデータベース２３１から戻された、アウトバウンドタグの優先順位、および転送データベース２５１から戻された優先順位選択標識（あるいはＣＡＭ２４１が有効なＳＣＩを戻さなかった場合は、ＶＴＩルックアップから戻された標識）、ならびにヘッダ長情報、宛先アドレス、パケット制御情報も含んでいる。退出準備完了パケットは、インタフェース２００がルートであるバスを通じて送信され、進入優先順位ベースの処理を完了する。
【００２３】
ここまで説明してきた進入優先順位処理では、インバウンドタグの優先順位および他の複数の値に基づいて、パケットについてアウトバウンドタグの優先順位が決定されてパケットに適用され、パケットの優先順位選択標識が決定されてパケットに適用され、そのタグ優先順位に基づいてスイッチにおいてパケットに優先順位付けをするかどうかをその標識が決定する。ここで説明した従来の方式の優先順位処理に関する方法については、他のさらなる改良があろう。それでもなお、ここまで説明した進入優先順位処理法は、従来技術に対して意義深い前進であると信ずる。
【００２４】
ここで退出準備完了パケットの退出優先順位処理を説明するために、典型的なネットワークインタフェース２００を参照する。不必要に複雑になるのを避けるために、インタフェース２００は、退出準備完了パケットが宛先を定められたネットワーク装置があるＬＡＮと関連付けられたネットワークインタフェース１０１〜１０８の１つであり、パケットの発信元のネットワーク装置は、パケットの宛先であるネットワーク装置と通信することを許可されているものと想定する。したがって、ヘッダ１０００のＳＣＩ構成要素を利用する許可チェックなど、これらの想定を試す退出処理の態様は詳細には説明しない。交換エンジン２１１は、パケットからヘッダ１０００を除去し、ＣＡＭ２４１および転送データベース２５１を調べて、ヘッダ１０００中の行先アドレスが認識されているかどうかを判断し、それについてローカル優先順位待ち行列識別子（ＬＰＱＩＤ）を決定する。先に引用したように、ＣＡＭ２４１は、インタフェース２００に関連付けられたＬＡＮ上にあるネットワーク装置の学習されたアドレスを、異なるＣＡＭインデックスで保持するエントリを有する。検討中の例においては宛先アドレスが認識されるので、ＣＡＭ２４１は、宛先アドレスがあるＣＡＭインデックス（以降、宛先ＣＡＭインデックス、すなわちＤＣＩ）を返す。図９に戻り、ＤＣＩは、転送データを検索するために、リンクされたエントリに対するポインタとして転送データベース２５１内で使用され、またそのパケットについてのＬＰＱＩＤを含んでおり、それはエンジン２１１に戻される。ＬＰＱＩＤは、いずれのタグ優先順位も参照せずにスイッチ１００により決定されるという意味で「ローカル」である。したがってＬＰＱＩＤは、特にインタフェース２００からのパケットの放出を他のパケットとの関連でスケジューリングすることに関して、退出準備完了パケットを優先順位付けする機能を提供し、そのスケジューリングはタグ優先順位とは無関係である。優先順位付けをタグ優先順位に従って実施するか、あるいはタグの優先順位とは無関係に実施するかについての決定は、優先順位選択標識を参照することにより行われるが、ここでそれについてより詳細に説明する。
【００２５】
交換エンジン２１１はヘッダ１０００からの優先順位選択標識を調べ、退出準備完了パケットにタグベースの優先順位付けを提供するべきかしないべきかを決定する。優先順位選択標識が、パケットにタグベースの優先順位付けを提供するべきではないことを示す場合、パケット（再フォーマットされたもの）は、ＬＰＱＩＤが指定する優先順位待ち行列に入れられ、優先順位ベースのスケジューリングアルゴリズムに従って、アクセスコントローラ２０１に放出される。ただし優先順位選択標識が、パケットにタグベースの優先順位付けを行うべきであることを示す場合は、エンジン２１１は、待ち行列リマップデータベース２６１を使用してタグ優先順位待ち行列識別子（ＴＰＱＩＤ）を決定する。次に図１１で、データベース２６１をより詳細に図示する。データベース２６１は、アウトバウンドタグの優先順位およびＬＰＱＩＤに基づいて、パケットについてＴＰＱＩＤを決定する。詳細には、エンジン２１１は待ち行列リマップデータベース２６１に、ヘッダ１０００からのアウトバウンドタグの優先順位、および転送データベース２５１から解決されたＬＰＱＩＤを提出する。アウトバウンドタグの優先順位およびＬＰＱＩＤは、データベース２６１内の対応するインデックスに対するポインタとして使用され、データベース２６１はＴＰＱＩＤを戻す。ＴＰＱＩＤはエンジン２１１に戻され、パケット（再フォーマットされたもの）は、ＴＰＱＩＤが指定する優先順位待ち行列内に入れられ、優先順位ベースのスケジューリングアルゴリズムに従ってアクセスコントローラ２０１に放出される。
【００２６】
図１２には、パケットがエンジン２１１によりアクセスコントローラ２０１に送信されるフォーマットを図示する。パケット１２００は、アウトバウンドパケットが送信される物理ポートを識別する物理ポート識別子（ＰＯＲＴ）、それに続き、パケット１２００をタグ付きパケットとして識別する制御情報（ＣＴＲＬ）を含んでいる。ＣＴＲＬの後には、アウトバウンドタグの優先順位を含んでいるＴＣＩを有するタグの部分（ＴＡＧ２およびＴＡＧ３）が続く。パケット１２００は、宛先アドレス（ＤＡ０〜ＤＡ５）、ソースアドレス（ＳＡ０〜ＳＡ５）、タイプ−長さ情報（ＴＬ０〜ＴＬ１）、他の情報も含んでいる。アクセスコントローラ２０１で、パケット１２００は、ＣＴＲＬを参照することによりタグ付きパケットとして識別される。パケット１２００がタグ付きパケットであると識別されると、コントローラ２０１は、ＰＯＲＴ、ＣＴＲＬ、ＴＡＧ２、ＴＡＧ３をパケット１２００から除去し、完全なタグ（ＴＡＧ０〜ＴＡＧ３）をＩＥＥＥ８０２．１Ｑ標準が指示する位置に適用し、アウトバウンドパケット１３００を生成する。パケット１３００は、ＰＯＲＴと表される物理ポート上で、コントローラ２０１によりＬＡＮ１２１の１つに送信される。
【００２７】
図１４では、流れ図を参照して進入優先順位処理を説明する。タグ付きパケットはスイッチ１００の物理ポート上で受信され（１４１０）、物理ポートに関連する識別子に基づいて仮想ポート識別子が決定される（１４２０）。仮想ポート識別子およびインバウンドタグのＶＬＡＮ識別子構成要素に基づいて、仮想トランク識別子が決定される（１４３０）。仮想トランク識別子およびインバウンドタグの優先順位構成要素を使用して、アウトバウンドタグの優先順位を決定し（１４４０）、それとは別に、インバウンドパケットのソースアドレスを使用して優先順位選択を行う（１４５０）。優先順位選択標識およびアウトバウンドタグの優先順位は、パケットのローカルヘッダに適用され（１４６０）、パケットは送信される（１４７０）。
【００２８】
図１５では、流れ図を参照して退出優先順位処理を説明する。進入処理されたパケットが受信され（１５１０）、そのパケットの宛先アドレスに基づいてローカル優先順位待ち行列識別子を決定する（１５２０）。パケットの優先順位選択標識を精査し、そのタグ付きの優先順位に基づいてパケットに優先順位付けを行うか行わないかを決定する（１５３０）。否定の応答である場合、パケットは、ローカル優先順位待ち行列識別子に基づいて優先順位待ち行列に適用される（１５５０）。だが肯定の応答である場合、タグ優先順位待ち行列識別子は、ローカル優先順位待ち行列識別子およびアウトバウンドタグの優先順位に基づいて決定され（１５４０）、パケットは、タグ優先順位待ち行列識別子に基づいて優先順位待ち行列に付される（１５５０）。いずれの場合も、アウトバウンドタグはパケットに適用され（１５６０）、アウトバウンドタグの優先順位を含んでおり、パケットはスイッチ１００から送信される（１５７０）。
【００２９】
したがって説明してきた優先順位処理では、スイッチ上でタグ付きパケットに、（ｉ）タグ優先順位とは無関係なローカル優先順位付け、または（ｉｉ）タグ優先順位によるタグ付きの優先順位付け、のいずれかが提供される。さらに、優先順位付けを実施するために、アウトバウンドタグの優先順位がスイッチ上で適用されるかどうかということとは無関係に、アウトバウンドタグ付きパケット内にアウトバウンドタグの優先順位が送信のために保存される、優先順位ベースの処理を説明した。これらの特性は、従来技術に対するさらに意義深い前進であると信ずる。
【００３０】
当分野の通常の技術を有する者は、本発明は、ここに述べる精神または基本的な性質から離れることなく、他の特定の形で実施することができることを理解されよう。したがって、この説明はあらゆる点で例示的なものであり、制限的なものではない。本発明の範囲は、添付の請求項により示され、これの同等物の意味および範囲内のすべての変更はその中に含まれる。
【図面の簡単な説明】
【図１】ＬＡＮスイッチを示す図である。
【図２】図１のＬＡＮスイッチにおける典型的なネットワークインタフェースを示す図である。
【図３】図２のネットワークインタフェースにおけるアクセスコントローラでＬＡＮから受信されるパケットを示す図である。
【図４】図２のネットワークインタフェースにおける交換エンジンで、図２のアクセスコントローラから受信されるパケットを示す図である。
【図５】図２のネットワークインタフェースにおける仮想トランクファインダを示す図である。
【図６】図５の仮想トランクファインダ内のマルチプレクサアレイを示す図である。
【図７】図５の仮想トランクファインダ内の仮想トランクハッシュＲＡＭを示す図である。
【図８】図２のネットワークインタフェースにおける優先順位リマップデータベースを示す図である。
【図９】図２のネットワークインタフェースにおける転送データベースを示す図である。
【図１０】図２のネットワークインタフェースにおいて動作可能な交換エンジンで、バックプレーンバスから受信されるパケットのローカルヘッダを示す図である。
【図１１】図２のネットワークインタフェースにおける待ち行列リマップデータベースを示す図である。
【図１２】図２のネットワークインタフェースにおけるアクセスコントローラで、図２の交換エンジンから受信されるパケットを示す図である。
【図１３】図２のネットワークインタフェースにおけるアクセスコントローラにより、ＬＡＮに送信されるパケットを示す図である。
【図１４】本発明の好ましい実施形態による進入優先順位処理を説明する流れ図である。
【図１５】本発明の好ましい実施形態による退出優先順位処理を説明する流れ図である。
【符号の説明】
１００  スイッチ
１０１、１０２、１０３、１０４、１０５、１０６、１０７、１０８  ネットワークインタフェース
１０９  管理インタフェース
２００  ネットワークインタフェース
２２１  仮想トランクファインダ
２３１  優先順位リマップデータベース
２５１  転送データベース
２６１  待ち行列リマップデータベース
３００  インバウンドパケット
４００、１２００  パケット
５１０  マルチプレクサアレイ
５１１、５１２、５１３、５２１、６０１、６０２、６０３、６０４、６０５、６０６、６０７、６０９、６０９、６１０  入力ライン
５３１、５３２、６３１、６３２、６３３、６３４、６３５、６３６、６３７、６３８、６３９、６４０  出力ライン
５４０  仮想トランクハッシュＲＡＭ
６１１、６１２、６１３、６１４、６１５、６１６、６１７、６１８、６１９、６２０  マルチプレクサ
７０１、７０２、７０３、７０４、７０５、７０６、７０７、７０８、７０９、７１０  インデックス
１０００  ローカルパケットヘッダ
１３００  アウトバウンドパケット
【図１】
0004685254.tif 000002
【図２】
0004685254.tif 000003
【図３】
0004685254.tif 000004
【図４】
0004685254.tif 000005
【図５】
0004685254.tif 000006
【図６】
0004685254.tif 000007
【図７】
0004685254.tif 000008
【図８】
0004685254.tif 000009
【図９】
0004685254.tif 000010
【図１０】
0004685254.tif 000011
【図１１】
0004685254.tif 000012
【図１２】
0004685254.tif 000013
【図１３】
0004685254.tif 000014
【図１４】
0004685254.tif 000015
【図１５】
0004685254.tif 000016