JPH0851439A - パケット処理装置 - Google Patents

Abstract

(57)【要約】 【目的】 入力ポートを通して受け取られたパケットに
ついて、短いインデックスを用いてチャネル識別子（"
マスタＶＣＮ"）を得る。 【構成】 パケット（ＡＴＭセル）に含まれる仮想チャ
ネルを識別するチャネル・ラベル、および、このパケッ
トを受け取った入力ポートを識別するポート・ラベルを
結合して長いチャネル識別子を生成する。これを分割し
てＫ個のキーを生成し、このキーをより短いインデック
スに変換する。このインデックスを用いてマスタＶＣＮ
テーブルを探索してマスタＶＣＮを得る。こうして、Ａ
ＴＭ装置内で短いインデックスを用いてマスタＶＣＮを
アクセスすることができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、パケットに基づくシス
テム（固定長パケットまたは"セル"を扱うシステムを含
む）のチャネル識別子の生成に関し、具体的には、複数
の入力ポートを持つＡＴＭスイッチでセルが受け取られ
る仮想チャネルの識別に関する。

【０００２】

【従来の技術】ＡＴＭ（Asynchronous Transfer Mode非
同期伝送モードの略称で、以下ＡＴＭと呼称する）は、
厳密に一定間隔で物理媒体上に出現するという意味にお
いて同期的である固定サイズ・セルを使用して、ある１
つのネットワークにわたってデータを転送するためのマ
ルチプレクシング（多重化）およびスイッチングの技術
である。各セルは、ペイロード部分とヘッダからなり、
後者のヘッダには、ネットワーク終端の送信システムと
受信システムとの間における通信インスタンスにセルを
関連づけるラベルが含まれる。この通信インスタンスに
は、１つの送信終端システムからおそらく複数の受信終
端システムへ多数のセルを転送することが含まれる場合
がある。同一の通信インスタンスに属する複数セルが必
ずしも一定間隔で出現しないという意味において、ＡＴ
Ｍは非同期的である。

【０００３】ＡＴＭにおいては、セルに付けられるラベ
ルは、固定サイズの文脈依存ラベルである。すなわち、
それらラベルは、解読ネットワーク・ノードにおいて予
め定められた文脈情報に照らしてのみ解釈可能であり、
ラベルは、一般的に、あるノードにおいて次のノードに
必要とされるラベルによって置き換えられる。言い換え
ると、ＡＴＭは、通信の各インスタンスが各ノードにお
ける適切なラベル情報を確立するための設定フェーズを
必要とする仮想回線技術である。

【０００４】ＡＴＭ技術は、普及の増加を見せている
が、その理由は、ＡＴＭ技術によって、（回線交換技術
に通常関連する）適時特性と（パケット交換技術に関連
する）統計的利点を結合する上で許容可能な妥協を図れ
る点にある。ＡＴＭは、音声、エンターテイメント（娯
楽）サービスまたはコンピュータ・トラフィックを含む
すべてのタイプのトラフィックを搬送するための単一の
伝送モードを提供する。

【０００５】本発明は、セル・サイズのような特定の実
施上の詳細事項にとらわれることなく一般的にＡＴＭシ
ステム（および他のシステム）に適用できるものであ
る。しかし、以下の説明において、ＣＣＩＴＴおよびＡ
ＴＭフォーラム（前者は主としてパブリック・ネットワ
ークに関するもので、後者はコンピュータ関連ユーザ・
ネットワークに関するものである）によって推進されて
いる現在進展中のＢ−ＩＳＤＮ ＡＴＭ規格を特に参照
する。

【０００６】事実、これら現在進展しつつある規格の範
囲においてさえ、各セルのヘッダ部分に含まれる情報の
意味論は、ネットワーク上でセルが（その末端か内部か
に）出現する場所とネットワーク終端システムにおいて
ＡＴＭセルを処理するために配置されるＡＴＭ適合層の
特性に依存して変わる。特記しない限り本発明の以下の
説明において記述するセルの形式は、ＡＡＬ５サービス
のためのＢ−ＩＳＤＮＵＮＩ(ユーザ・ネットワーク・
サービスUser Network Interface）である（ここで"Ａ
ＡＬ"は、ＡＴＭ適合層（ATM Adaption Layer）を指
し、"ＡＡＬ５"は、コンピュータ通信に適した接続指向
の可変ビット伝送速度非同期通信サービスを意味す
る）。

【０００７】図１は、上記のようなセルの形式をバイト
幅形式で示している。図に見られる通り、セルは、５バ
イト長のヘッダとユーザ・データの４８バイト長ペイロ
ードで構成されている。ヘッダ・フィールドは、次の通
りである。 −ＧＦＣ ４ビット 一般フロー制御(General Flow C
ontrol)フィールド −ＶＰＩ ８ビット 仮想経路識別子(Virtual Path I
ndicator)フィールド −ＶＣＩ １６ビット 仮想チャネル識別子(Virtual Ch
annel Indicator)フィールド −ＰＴ ３ビット ペイロード・タイプ(Payload Ty
pe)フィールド −ＥＯＰ １ビット パケット終了(End of Packet)フ
ィールド −ＨＥＣ ８ビット ヘッダ・エラー・チェック(Head
er Error Check)フィールド ＶＰＩとＶＣＩはともに、特定リンク上のセルのための
仮想回線ラベルを形成し、このラベルは、セルが遭遇す
る次のネットワーク・ノードでセルの行先経路が定めら
れる基礎情報となる。一般的に、ＡＴＭ用語において、
仮想回線は、"仮想チャネル"と呼ばれ、ＶＰＩは、ある
リンク上の１つの仮想チャネル・グループを識別するも
のとみなされ、一方、ＶＣＩは該グループ内の特定の仮
想チャネルを識別するものである。

【０００８】ＥＯＰビットは、当該セルが、上位レベル
の適用業務データ・ユニット（パケット）を構成する一
連のセルの最後のセルであることを識別するために使わ
れる。このようにパケットの最後を明示する情報をセル
・ヘッダに保有することの利点は、１つの構成セルが消
失した場合、パケットを構成しているすべてのセルを破
棄することを可能にすることである。

【０００９】ある特定の入力ポートを経由してあるネッ
トワーク・ノードに到着するＡＴＭセルは、セル・ヘッ
ダに記憶されるＶＰＩとＶＣＩ情報および設定時に設定
される文脈情報に従って、経路を再指定（すなわちスイ
ッチ）される。ＶＰＩとＶＣＩ情報は、変更され、セル
は出力される。そのようなノードは、一般に、ＡＴＭス
イッチと呼ばれ、図２に示すように、概念的にスイッチ
・コア２００を含む。このスイッチ・コア２００は、取
り扱うセルに関し以下の動作を実行する役目を有する。 −各セルに記憶されたＶＰＩとＶＣＩ情報が、与えられ
たリンクに唯一の特異な情報であることを考慮して、ど
のセルがどのチャネルに属するかを決定すること、 −セルの行先チャネルを決定しそこへ配送すること、お
よび、 −適切な出力ポートに対する複数のアクセス要求を仲裁
すること。 スイッチは、また、チャネル設定と管理機能を分担する
ある種のプロセッサ装置２０１と、該スイッチのそれぞ
れの外部ポートに接続されるリンク２０３にスイッチ・
コアをインターフェースさせるためのインターフェース
回路２０２とを含むこともあろう。

【００１０】スイッチ・コアは一般に高帯域を持つよう
に設計され、そのため、該スイッチは、本来的かまたは
統計的かいずれにしても低域幅である複数のリンクをサ
ービスすることが可能である。この場合、複数のリンク
は、スイッチ・コアに供給される前にマルチプレクスさ
れ、反対に、スイッチ・コアの出力は、適切なリンクに
渡すためデマルチプレクスされる。

【００１１】セル・ヘッダのＶＰＩとＶＣＩフィールド
を合計した大きさは２４ビットで、これにリンク識別子
を加えて、全リンクにわたって特異なチャネル・ラベル
を作成すると、その結果できるラベルは長すぎて、ＡＴ
Ｍスイッチ内で処理する（たとえば、スケジューリング
を実行する）ために実際使うタグとしては使用できなく
なる。したがって、従来のＡＴＭスイッチの具体化で
は、ＶＰＩ＋ＶＣＩ全フィールドの使用を避けることが
多かった。全フィールドが必要とされることはめったに
ないので、これは正当化できた。

【００１２】

【発明が解決しようとする課題】本発明の目的は、パケ
ットに関連する仮想チャネルを特異に識別するチャネル
・ラベル（ＶＰＩ＋ＶＣＩ）を利用し、ＡＴＭスイッチ
（または、受け取られたセルまたはパケットに関して予
定の機能を実行するその他の装置）内で使用できる扱い
易い大きさのチャネル識別タグを提供することである。

【００１３】

【課題を解決するための手段】本発明の１つの側面とし
て、少なくとも１つの入力ポートを通して受け取られた
パケットに関してあらかじめ定められた機能を実行する
ための装置を提供する。各パケットは、パケットを受け
取った該装置の入力ポートに対して、該パケットに関連
する仮想チャネルを特異に識別するチャネル・ラベルを
持ち、上記装置は、該装置によって受け取られた各パケ
ットに、該パケットに関連する仮想チャネルと入力ポー
トとを結合したものを特異に識別する識別子（ここでは
マスタＶＣＮ（Virtual Channel Number 仮想チャネル
番号））を提供するＶＣＮ提供手段と、上記ＶＣＮ提供
手段によって提供されたマスタＶＣＮに基づいて各パケ
ットに関して上記のあらかじめ定められた機能を実行す
る処理手段と、を含み、上記ＶＣＮ提供手段は、 −各パケットに対し、パケットを受け取った入力ポート
を識別するそれぞれのポート・ラベルを生成するポート
識別手段と、 −パケットに関連するチャネル・ラベルとポート・ラベ
ルを結合し、出力される長いチャネル識別子を作成する
結合手段と、 −上記結合手段の出力をあらかじめ定められた方法で分
割し、Ｋが２以上の整数であるＫ個のキーを提供するキ
ー提供手段と、 −Ｋ個のキーが適用されるテーブル探索手段と、を有
し、さらに、上記テーブル探索手段が、 −パケットに関連するＫ個のキーの各々を、それぞれ対
応するより短いインデックスに変換する変換手段と、 −それぞれのマスタＶＣＮを保持する位置を持つＫ次元
のマスタ・テーブルであって、対象とするパケットのマ
スタＶＣＮを提供するために、同一パケットから得られ
たＫ個のインデックスが、対応するマスタ・テーブルの
位置をアクセスする役割をするようにした、Ｋ次元マス
タ・テーブルと、を有する。この形のＶＣＮ提供手段に
より、マスタＶＣＮが得られた長いチャネル識別子より
も、実質的に短いマスタＶＣＮの提供が可能になる。

【００１４】ＡＴＭスイッチに関する本発明の１つの実
施例では、パラメータＫは２の値を持つ。

【００１５】上記結合手段は、長いチャネル識別子が出
力される前に、それをスクランブルするように動作する
ことが望ましい。

【００１６】一般的に、キー提供手段は、結合手段の出
力をＫ個の等しいセグメントに分割することによって、
Ｋ個のキーを提供する。しかし、出力を他の方法で分割
し、出力の要素（たとえばディジット）をＫ個の群に分
け、１つの群内の要素を混ぜることも可能である。

【００１７】ＶＣＮ提供手段がさらに、テーブル探索手
段によって提供されたマスタＶＣＮの正確さを確認する
確認手段を持つことにより、さらに利点が増す。上記確
認手段は、 −マスタＶＣＮを提供するときに使われた長いチャネル
識別子の少なくともあらかじめ定められた部分に各マス
タＶＣＮを関連させ、マスタＶＣＮが供給されたときに
上記の少なくともあらかじめ定められた部分を出力す
る、チェック・テーブル手段と、 −チェック・テーブル手段の出力と、チェック・テーブ
ル手段に供給されたマスタＶＣＮを提供する際に実際に
使われた長いチャネル識別子の対応する部分とを比較
し、比較の結果の標示を出力するように動作する比較手
段と、を有する。

【００１８】望ましい形として、装置はＶＣＮ提供手段
を含むコアと、複数の入力ポートを提供し、入力ポート
で受け取られたパケットをマルチプレクス（多重化）
し、あらかじめ定められたタイミングに従ってパケット
をコアに渡すマルチプレクサ手段を含む外部インタフェ
ース手段と、を有することが望ましい。この場合、ポー
ト識別手段は、パケットがコアに到着する時間に依存し
て、パケットに対してポート・ラベルを生成するように
構成することができる。

【００１９】各変換手段は、関連するキーを対応するイ
ンデックスに関連させるリスト手段を含むことが有利で
ある。この文脈において、用語"リスト手段"は、リスト
のように働き、それにより、対応するインデックスを探
索するためにキーが使えるいかなる構造も広くカバーす
るものと理解されたい。

【００２０】もちろん、一般的に、装置は、新しい仮想
チャネルのパケットにマスタＶＣＮを提供するためにテ
ーブル探索手段を設定する新エントリ手段を備えること
が必要であって、これらのパケットに関連するチャネル
・ラベルとポート・ラベルは、Ｋ個の特性キー（以下新
キー）をテーブル探索手段に適用させることができるも
のである。新エントリ手段は、 −新しい仮想チャネルのマスタＶＣＮをマスタ・テーブ
ルの指定された位置に挿入するための挿入手段と、 −Ｋ個の新キーがリスト手段の既存のインデックスを参
照しているかを判断する判断手段と、 −上記の判断手段が上記インデックスがないと判断する
と上記の適切なインデックスを対応するリスト手段に挿
入し、新キーによって参照される１対のインデックス
が、マスタ・テーブルの、既存の塞がったテーブル位置
に関してよく分配された空きの位置を識別できるよう
に、上記の適切なインデックスを選択し、さらに、イン
デックスによって指示された空きのテーブル位置を挿入
手段に知らせ、該挿入手段に空きのテーブル位置にマス
タＶＣＮを挿入させるようにする、リスト設定手段と、
を有することが望ましい。

【００２１】さらに、新エントリ手段が、 −判断手段が全てのキーに対してインデックスが既に存
在すると判断したときに、インデックスによって指され
たテーブル位置を検査し、テーブル位置が空いているこ
とがわかると、挿入手段に、その空いているテーブル位
置に新しい仮想チャネルのマスタＶＣＮを挿入させる検
査手段と、 −上記検査手段により、インデックスによって指された
テーブル位置に、エントリが存在して塞いでいることが
判明したことに反応し、塞いでいるエントリに関連する
上記インデックスを調整することによってテーブル位置
を空けることができるかを判断し、空けられれば、この
調整を行い、挿入手段に、新しい仮想チャネルのマスタ
ＶＣＮを空いた位置に挿入させる、調整手段と、を有す
ると利点が多い。

【００２２】新エントリ手段が、上記の調整手段がテー
ブル位置を空けることができないときに動作する付加的
調整手段をさらに持ち、塞いでいるエントリを外して新
しい仮想回線のマスタＶＣＮで置き換え、その後、マス
タＶＣＮに関連する上記インデックスを調整することに
よりテーブル位置を空けることができるかを判断し、空
けられるならば、この調整を行って、塞いでいるエント
リを置き換えることが望ましい。

【００２３】本発明のもう１つの側面として、装置の少
なくとも１つの入力ポートを通して受け取られたパケッ
トに対し、パケットに関してあらかじめ定められた機能
を実行する意図でパケット・ストリーム識別子（ここで
は"マスタＶＣＮ"）を生成する方法を提供する。この場
合、各パケットは、そのパケットが受け取られた入力ポ
ートに対し、そのパケットに関連する仮想チャネルを特
異に識別するチャネル・ラベルを含む。この方法は、 −Ｋが２以上の整数の、マスタＶＣＮを記憶するＫ次元
の探索テーブルを提供するステップと、 −特定の上記のパケットに関連するマスタＶＣＮを提供
するために、(i)上記パケットに対して、そのパケット
を受け取った入力ポートを識別するポート・ラベルを生
成し、(ii)長いチャネル識別子を作成するために、上記
のパケットに関連するチャネル・ラベルおよびポート・
ラベルを結合し、(iii)Ｋ個のキーを提供するために、
あらかじめ定められた方法で長いチャネル識別子を分割
し、(iv)各キーを、対応する、それぞれの、より短いイ
ンデックスに変換し、(v)Ｋ次元探索テーブルに、Ｋ個
のインデックスを使って、対象としているパケットのマ
スタＶＣＮを探索する、ことからなるサブステップを実
行するステップと、を有することが望ましい。望ましく
は、上記方法は長いチャネル識別子をスクランブルする
サブステップをさらに含み、この場合、上記サブステッ
プ(iii)は、スクランブルされた長いチャネル識別子に
対してはたらく。

【００２４】本発明のさらにもう１つの側面として、少
なくとも１つの入力ポートを通して受け取られたパケッ
トに関して、あらかじめ定められた機能を実行する装置
を提供する。各パケットは、パケットが受け取られた入
力ポートに対して、各パケットが関連する仮想チャネル
を識別するチャネル・ラベルを持ち、上記装置は、受け
取られた各パケットに、パケットに関連する仮想チャネ
ルと入力ポートとを結合したものを識別する識別子（こ
こでは"マスタＶＣＮ"）を提供するＶＣＮ提供手段と、
上記ＶＣＮ提供手段によってパケットに提供されたマス
タＶＣＮに依存して、各パケットに対し上記のあらかじ
め定められた機能を実行する処理手段と、を備える。Ｖ
ＣＮ提供手段は、 −各パケットに対して、パケットが受け取られた入力ポ
ートを識別するポート・ラベルを生成するポート識別手
段と、 −パケットに関連するチャネル・ラベルとポート・ラベ
ルを結合する結合手段であって、該結合手段によってス
クランブルされる長いチャネル識別子を作成する結合手
段と、 −パケットのスクランブルされた長いチャネル識別子
を、あらかじめ定められた方法で分割して少くとも２個
のキーを提供するキー提供手段と、 −マスタＶＣＮを保持するマスタ・テーブルを含むテー
ブル探索手段であって、特定のパケットに関連する上記
少なくとも２個のキーが該テーブル探索手段に適用され
るのに応答して、そのパケットに対するマスタＶＣＮを
出力する、テーブル探索手段と、を有する。

【００２５】

【実施例】

アーキテクチャの概要 以下に記述するＡＴＭスイッチは、高帯域、Ｎポートの
スイッチ・コアを備え、このＮポートのスイッチ・コア
は、スイッチ・コア・ポートそれぞれに関連付けられる
マルチプレクサ／デマルチプレクサ機構を介して低速リ
ンクとインターフェースされる。スイッチ・コアは、１
度に１つのポートを処理するため周期的にポートをサー
ビスして新しいセルを持ち込む。従って当アーキテクチ
ャで実施されるマルチプレクサ／デマルチプレクサに２
つのレベル（当然Ｎ＝１の場合を除いて）が存在する。

【００２６】更に具体的に図３を参照して述べれば、本
発明を実現するスイッチは、大きく見て３タイプの主要
ブロックから構成されている。中央には、Ｎポートのス
イッチ・コア２０があり、各スイッチ・コア・ポート２
１は、例えば６２２Ｍビット／秒という予め定められた
速度で動作する。アダプタ・カード２２が、各ポート２
１に接続している。アダプタ・カード２２の各々は、多
数の比較的低速の外部スイッチ・ポート２３をスイッチ
・コア・ポートへインターフェースする（図でＩ／Ｆと
表示）。最後に、プロセッサ装置２４があって、これ
は、信号生成と仮想チャネル設定機能を実行する。

【００２７】本発明のスイッチの説明の目的のため、ス
イッチ・コア・ポートは、６２２Ｍビット／秒で動作す
るものとするが、上記特定のポート速度は本発明にとっ
て必須のものではなく、それより低いまたは高い速度も
可能である点は認識されるべきであろう。

【００２８】本スイッチのアーキテクチャは、「すべて
共有」のアーキテクチャである。これは、いかなる資源
も特定ポートやバッファに占有されず、論理部分は中心
に集められていることを意味する。従って、アダプタ・
カードは、殆どバッファ機能と知能を備えていない。

【００２９】共通のマスタ・クロック２５がすべての３
つの主要ブロック（スイッチ・コア２０、アダプタ・カ
ード２２、プロセッサ２４）へクロック信号を送り、局
所スレーブ・クロック２６が適切な局所クロック信号を
生成する。この配置は、クロック速度が予め定められた
一定の関係を有することを保証する。ライン２７は、プ
ロセッサからのグロ―バル同期化信号をプロセッサ・ブ
ロック２４からスイッチ・コア２０とアダプタ・カード
２２へ送り、動作開始時点における各ブロックの動作を
同期化させる。

【００３０】以下の３つの節において、３つの主要ブロ
ックについて詳細な説明を行う。

【００３１】Ｎポート・コア２０ 図４には、Ｎポートのスイッチ・コア２０のブロック図
が示されていて、図に見られるように、スイッチ・コア
は、一般に対となってスイッチ・コア・ポートを構成す
る入力／出力ポート３７、３８、セル本体共有メモリ３
１、空きアドレス・リスト・メモリ３２、コントローラ
３３、および、コントローラとの間で送受信されるセル
のＡＴＭ適合層およびその他高位通信層処理を実行する
ための通信ブロック３４（これにより当該スイッチが一
部をなすネットワーク上でコントローラがセルを通信す
ることが可能となる）を含む。

【００３２】スイッチ・コアの動作は、非常に単純であ
る。Ｎ入力ポート３７は厳密な順序で一度に１つのセル
をサービスされる。１つのセルが入力ポートの１つに到
着すると、ファブリック（fabric、送受信機構、以下フ
ァブリックという）３０が、空きアドレス・リスト・メ
モリ３２から取り出したアドレスを用いて、セル本体を
セル本体共有メモリ３１に書き込む。このアドレスは、
また、当該セルのヘッダとともに、コントローラ３３に
渡される。入力ポート３７が固定的順序でサービスされ
るため、コントローラ３３は、ヘッダの到着時間からセ
ルの発信ソース（入力ポート）を特定することができ
る。

【００３３】コントローラ３３は、到着セルのヘッダと
セル本体アドレスとを記憶し処理する。コントローラは
また、（後述する）待ち行列モデルとスケジュール規則
を基に各出力ポート３８上にどのセルを次に送信すべき
かを決定する。セルを送信するため、コントローラは、
当該セルの本体が記憶されているアドレスと当該セルの
ヘッダとを出力する。ファブリック３０は、セル本体共
有メモリ３１からセル本体を読み取り、それをヘッダと
組み合わせてセルを作成し、このセルを出力ポートに送
出する。出力ポートもまた固定順序でサービスされるの
で、コントローラがヘッダとアドレスを送出する時間に
よって、セルの宛先は決定される。アダプタ・カード２
２が接続するスイッチ・コアの主ポート（入力／出力ポ
ート対３７，３８）の他に、ファブリック３０は、２つ
の低速ポートをサポートする。その１つは、セルを送受
信するためプロセッサ２４によって使用されるプロセッ
サ・ポートであり、もう１つは、通信ブロック３４を通
してフロー制御セルを送受信するためにコントローラに
よって使用されるコントローラ・ポートである。

【００３４】セル本体共有メモリ３１とコントローラ３
３の帯域幅は、ポートの最大速度ですべての入力ポート
３７からセルを受け取り、すべての出力ポート３８にセ
ルを送り出すことを実施するのに十分なものである。ス
イッチ・コア２０の構成エレメントのクロック動作は、
局所クロック機構２６によって制御される。

【００３５】スイッチ・コア動作のタイミングをより詳
細に考察すると、所与のスイッチ・コアの主ポートの速
度（６２２Ｍビット／秒）での連続的セル到着の間隔を
Ｔとすれば、Ｎポートのスイッチ・コアに関して、ファ
ブリック３０は、時間Ｔ毎に、Ｎ個のセルを、すなわ
ち、スイッチ・コア入力ポート３７の各々から１つのセ
ルを受け取る能力を持たなければならない。同様に、該
ファブリックは、時間Ｔ内にＮ個のセルを、すなわち、
出力ポート３８の各々毎に１つのセルを送信する能力を
持たなければならない。ファブリック３０はまた、プロ
セッサ・ポートとコントローラ・ポートを経由するセル
の伝送を処理する能力を有していなければならない。

【００３６】ファブリックは、複数のシフト・レジスタ
を基本的に含み、このシフト・レジスタでのシフトによ
って、セルの転送が、主スイッチ・ポートを経由して、
すべてのポートに対して同時に実行される。ファブリッ
ク３０のシフト・レジスタと共有メモリ３１との間のセ
ル本体データの転送とコントローラ３３とのセル・ヘッ
ダの転送は、各ポートを順番に取り扱う所定周期の転送
に従ってシフト・レジスタとの並列転送によって実行さ
れる。

【００３７】スイッチ・コア・ポートを通して各セルを
転送するために必要となる一般的プロセスは、先ず、セ
ル・ヘッダがファブリックにシフトされ、セル本体が続
くというものである。セル本体がシフトされている間、
セル・ヘッダは、コントローラへ送出され、引き続くセ
ル本体のメモリ３１への転送の間に、当該ポートに関す
る次のセルのヘッダが、ファブリックにシフトされる。
セルの出力に関して、同様であるが反対のプロセスが行
われる。

【００３８】セル本体メモリ３１への転送に関する限り
は、転送サイクルは、単純に各主スイッチ・ポートを順
番に進む（例えば入力ポート３７が４個、出力ポート３
９が４個ある場合、転送サイクルは、先ず各入力ポート
をサービスしてセル本体データをメモリ３１へ転送し、
次に各出力ポートをサービスしてデータをメモリ３１か
らファブリックへ転送する）。メモリ３１とコントロー
ラ／プロセッサ・ポートに関連付けられたシフト・レジ
スタとの間のセル本体データの転送は、スイッチ・コア
の主ポートに関するセル転送サイクルのうちの予め定め
られた冗長部分においてファブリックによって取り扱わ
れる。

【００３９】ファブリック３０とコントローラ３３との
間のセル・ヘッダの転送は、コントローラ３３が逐次ヘ
ッダを受け取り出力することができる（コントローラが
その処理を逐次遂行する）ことを前提に、セル本体の転
送と同様の転送サイクルをとることができる。したがっ
て、コントローラ／プロセッサ・ポートは、コントロー
ラによって実行される全般ポート・サービス・サイクル
において、それ自身のスロット（時間間隔）を割り当て
られなければならない。もちろん、コントローラ／プロ
セッサ・ポートは、スイッチ・コアの主ポートのように
頻繁にサービスされることはなく、一般に、プロセッサ
／コントローラ・ポートが主ポートの１／ｎの速度で動
作するとすれば、プロセッサ／コントローラ・ポート
は、主ポートのｎ回のサービス毎に一度だけサービスさ
れる。結果として、全般ポート・サービス・サイクル
は、Ｐ１からＰ４の４つの主ポートを持つスイッチ・コ
アに関して図５で示されるようになり、コントローラ３
３へのヘッダの入力とコントローラからのヘッダの出力
との両方に適合する（実際には、サイクルは、入出力に
関して同じである必要はないが、一般的にはそのように
なる）。

【００４０】コントローラ３３に渡されるセル・ヘッダ
は、セル本体をメモリ３１に記憶するために使われるア
ドレスによって、その対応するセル本体と関連づけら
れ、これらのアドレスは、ヘッダ・データとともにコン
トローラ３３に記憶される。セル本体が記憶されるアド
レスは、正しいヘッダとともに記憶されることを保証す
るため適切なタイミングでコントローラ３３に供給され
なければならないことが認識される必要がある。

【００４１】以下に説明されるように、スイッチ・コア
の主ポートを通して供給される特定のセルが空のセル
（さらに正確にいえば無視されるべきセル）である可能
性があり、この条件は、セル・ヘッダのＶＰＩとＶＣＩ
の値がゼロにセットされることによって標示される。こ
のようなセルの存在は、セル本体のメモリ３１への転送
またはセル・ヘッダのコントローラ３３への転送の処理
を変えることはなく、コントローラ３３は、セル・ヘッ
ダのＶＰＩとＶＣＩがゼロであることを発見次第、セル
本体が記憶される関連アドレスを空きアドレス・リスト
・メモリ３２へ単に戻すだけであり、メモリ３１それ自
体においてなにかの措置を講ずる必要はない。

【００４２】アダプタ・カード２２ 各アダプタ・カードは、対となっている多数の外部入力
／出力ポートをスイッチ・コアの１つのポートに結合す
る。１つのアダプタ・カード上の外部入力／出力ポート
（複数）は、複数リンクの帯域幅の総和がスイッチ・コ
アのポートの速度より小さいことを前提に、それらリン
クの任意の組合せで構成することができる。例えば、ス
イッチ・コアのポートの速度が６２２Ｍビット／秒であ
れば、アダプタ・カードは、１２個の５１Ｍビット／秒
ポート、または４個の１５５Ｍビット／秒ポート、また
は、３個の１５５Ｍビット／秒ポートと１個の１００Ｍ
ビット／秒ポートと１個の５ｌＭビット／秒ポートの混
合のいずれかを含むことができる。

【００４３】アダプタ・カードの動作は、非常に単純で
ある。ほとんどの場合、アダプタ・カードはそれが扱う
セルの内容を見ることはない。その１つの例外は、各セ
ルのヘッダ・エラー・チェック（ＨＥＣ）フィールドで
あり、それは、送信されるセルに関してはアダプタ・カ
ードによって生成され、受信されるセルに関してはアダ
プタ・カードによってチェックされる。もしもＨＥＣが
到来するセルに関しエラーを示していれば、アダプタ・
カードは該セルのＶＰＩとＶＣＩフィールドをゼロにセ
ットすることによって該セルを空セルに変える。

【００４４】図６に示されているアダプタ・カード３２
の例では、５つの外部低速ポートＡからＥがスイッチ・
コアの１つのポートにインターフェースするように設計
されている。明示の目的のため、ポートＡのコンポネン
トのみが図示されている。アダプタ・カード２２は以下
のエレメントを含む。 −ポートＡからＥの各々に対するそれぞれの物理層／フ
レーム機構（ＰＨＹＳ）４０。機構４０は、上述のヘッ
ダ・エラー・チェック機能を実行する。 −ポートＡからＥの各々の入力側に対する小規模の（セ
ル２つ分の）入力先入先出機構（ＦＩＦＯ）４１。この
ＦＩＦＯは、入力ポートの転送速度をスイッチ・コアの
ポートに合致させる。 −対応する入力ＦＩＦＯ４１の内容が１個のセルに等し
い分量以下であることを検出するための入力検出機構４
２。 −ポートＡからＥの各々の出力側に対する小規模の出力
先入先出機構（ＦＩＦＯ）４３。このＦＩＦＯは、スイ
ッチ・コアのポートの転送速度を出力ポートのそれに合
致させる。 −対応する出力ＦＩＦＯ４３の内容が１つのセルに相当
する分量を越えることを検出するための出力検出機構４
４。 −入力ポートの各々からのセルをスイッチ・コアの入力
ポート３７へマルチプレクスする時分割マルチプレクサ
４５。セルは、入力ポート・ロータ機構４６に保持され
る所定のポート順で周期的に送られる。ポート・ロータ
周期の開始は、グロ―バル同期化信号によって指示され
る。 −対応するスイッチ・コアの出力ポート３８からセルを
取り出し、それらを適切な出力ポートＡからＥへ送るデ
マルチプレクサ４７。セルは、グロ―バル同期化信号に
同期化されるプログラム可能出力ポート・ロータ機構４
８に保持される所定の順序で到着する。 −局所クロック２６。

【００４５】一方でのマルチプレクサ４５とデマルチプ
レクサ４７との間の、他方ではそれらとスイッチ・コア
のポートとの密接な機能的関連性のために、マルチプレ
クサ４５とデマルチプレクサ４７は、スイッチ・コアの
ファブリック３０との間のセルの転送を同期化させるた
め、スイッチ・コアのポートから供給されるクロック信
号を使用する。

【００４６】スイッチ・コアのポートは、それに関連付
けられる外部ポートの累積速度より若干速い速度で転送
動作を行う（上記外部ポートの外側はそのようにセット
されたクロック信号を局所クロック２６から受け取
る）。このようにすることの１つの理由は、外部ポート
に接続するリンクの実際の速度をその公称値から変動す
ることができるようにするためである。スイッチ・コア
のポートのこのような速度超過は、入力ＦＩＦＯが、満
たされるより速く空にされることを意味する。具体的に
は、あるＦＩＦＯ４１の内容量が、１つのセルに相当す
る量以下の場合、入力検出機構４２はマルチプレクサ４
５に信号を送り、空セル挿入機構４９をして空セルを生
成し適当な時間にコントローラへ送るようにさせ、入力
ＦＩＦＯは再び収納を始める。反対に、出力ＦＩＦＯ４
３は空にされるより速く満たされる。これは、関連出力
検出機構４４が関連するＦＩＦＯ４３の内容量が１つの
セルより多くなることを検出し、コントローラ３３へ相
応の標識を送信することによって取り扱われる。この標
識を対応する外部ポートへセルを送信する準備をしてい
るコントローラ３３が検知すると、コントローラは、外
部ポートへ空セルを送る。デマルチプレクサ４７の機構
５０はこの空セルを検出し削除するため配置され、ＦＩ
ＦＯ４３は空にされる。

【００４７】機構４６と４８に記憶されるポート・ロー
タによって確立される外部ポートのサービス順序を次に
考察すると、明らかに、より高速のポートは、より低速
のポートよりも一層頻繁にサービスを必要とする。一般
的意味において、最低速度のセル間隔が、ポート・ロー
タの全般的サイクル・タイムをセットするため用いら
れ、この最低速度のポートは、上記サイクル中一度だけ
サービスされることを必要とし、一方、より高速のポー
トは、２回以上のサービスを必要とする。図７は、図６
のアダプタ・カードに関する可能なポート・ロータを図
示している。関連するスイッチ・コアのポートの各セル
期間Ｔ毎に、ポート・ロータに従って、１つのセルが、
外部ポート（ＡからＤ）からスイッチ・コアのポート
へ、また、スイッチ・コアのポートから外部ポート（Ａ
からＤ）へ、転送される。

【００４８】プロセッサ プロセッサ装置２４は、接続要求を受け取り、コントロ
ーラ３３中のデータ構造を処理することによって、仮想
チャネル接続設定と管理を実行する。プロセッサはま
た、電源投入時にコントローラ・データ構造を初期化す
る。

【００４９】これらの機能を達成するため、プロセッサ
装置２４は、スイッチ・コアに対するインターフェース
を２つ有する。第１は、スイッチ・ファブリックのプロ
セッサ入力／出力ポートを通してのセル・インターフェ
ースであり、これにより、プロセッサがあたかもアダプ
タ・カード上の入力／出力ポートの１つに接続している
かのように、セルを送受信することが可能となる。

【００５０】第２のインターフェースは、コントローラ
自体に直接かかわるもので（図４参照）、プロセッサが
コントローラの内部データ構造にアクセスすることを可
能とし、そのため、仮想チャネル・データを設定し修正
することができる。空のセルを受け取ったためコントロ
ーラがアイドル状態の間、プロセッサはコントローラに
アクセスする。十分な空セル（複数）が受け取られるこ
とを保証するため、スイッチ・コアは、入力／出力ポー
トに対処するため必要となる速度より若干（約１０％）
速く動作し、この結果、アダプタ・カードＦＩＦＯ４１
は周期的にそのしきい値（１つのセル相当量）以下に内
容を減らし、空セル挿入機構４９を動作させる。

【００５１】プロセッサはコントローラのすべてのデー
タ構造に対し全面的なアクセスを行うが、セル本体共有
メモリへのアクセスは行わない。

【００５２】初期化と接続を実行する際のプロセッサ装
置２４の一般的動作は従来技術の既知の方法に従うもの
であるから、これ以上の説明は行わない。

【００５３】コントローラの概念と概要外部ポート・ロータ どの外部（アダプタ・カード）ポートからセル・ヘッダ
が受け取られたかを知ることは、各ヘッダ中の（ＶＰＩ
＋ＶＣＩ）情報がリンク単位でのみ特異であるため、コ
ントローラ３３にとって不可欠である。従って、外部ポ
ート識別は、当該スイッチを経由の特定の通信に適切な
ものとしてセルを特異に識別するために必要である。コ
ントローラに適切な外部ポート識別を通知する１つの方
法は、アダプタ・カードが各セル・ヘッダにタグを付け
ることである。しかし、各アダプタ・カードがその関連
する外部ポートをサービスする順番とこれらのアダプタ
・カードが対応するスイッチ・コアのポートを通してサ
ービスされる順番の両方が、あらかじめ定められている
ので、本発明のコントローラでは別の方法を使うことが
可能である。従って、本コントローラにおいては、セル
・ヘッダに関連付けられる外部ポート識別は、ヘッダが
受け取られる時間を基にコントローラによって決定され
る。更に云えば、セル・ヘッダがスイッチ・コアに接続
するすべてのアダプタ・カードの外部ポートから受け取
られる順番を標示する外部ポート・ロータが取り出さ
れ、その後、コントローラ３３とマルチプレクサ４５
は、前述のグロ―バル初期化信号によって初期的に同期
化されているので、コントローラ３３が、アダプタ・カ
ード・マルチプレクサ４５の動作との調整を図りながら
このロータにアクセスする。外部ポート・ロータそれ自
体は、図５で示される（セル・ヘッダがスイッチ・コア
・ポートからコントローラに渡される順番を示す）スイ
ッチ・コア・ポート・サイクルと各アダプタ・カードに
関する外部ポート・サービス（図７参照）との組合せで
ある。この組合せは、対応するスイッチ・コア・ポート
がスイッチ・コア・ポート・サイクルに出現する度毎
に、アダプタ・カードに関し次のエントリを外部ポート
・サービス・サイクル上にとることによって実効を生じ
る。かくして、アダプタ・カードに接続するスイッチ・
コア・ポートＰ１を持つ図５のポート・サイクルを有す
るスイッチ・コアに関して、図５のサイクルでのポート
Ｐ１の連続的サービスは、図７のサイクルに従った外部
ポートＡからＥの連続的サービスと関連づけられる。

【００５４】外部ポート・ロータは、当然、スイッチ・
コアに接続しているアダプタ・カードのポート構成に依
存する。このため、外部ポート・ロータは、スイッチの
動作開始時にプロセッサが各アダプタ・カードを調べて
その外部ポート・サービス・サイクルを見い出すことに
よって決定される。次いでプロセッサ装置２４は、コン
トローラ３３の適切なデータ構造６０Ａに上記ロータを
記憶し、コントローラが必要に応じてロータにアクセス
することができるようにする。

【００５５】外部ポート・ロータは、それが受け取る新
しいセル・ヘッダ各々のソースをコントローラが判定す
るために必要とされるのみならず、外部ポートがスイッ
チ・コア出力を行うことができる所定の順序でヘッダの
出力を調整する（これは、ファブリック３０およびアダ
プタ・カード上のデマルチプレクサ４７の結合動作によ
って決定される）ためにも必要とされる。既に注記のと
おり、ポートが入力と出力に関しサービスされる順番は
必ずしも同じである必要はないが一般的には同じであ
る。本発明の場合においては、外部ポート・ロータの同
じ一般的形式が、入力と出力とに使用される。図８にお
いて外部ポート・ロータは６０Ａおよび６０Ｂとして示
されている。

【００５６】マスタＶＣＮと出力ＶＣＮ 本発明のスイッチにおける関連セルのフローを特異に識
別するため、仮想チャネル番号（ＶＣＮ）がコントロー
ラによって使われる。どの入力仮想チャネルも"マスタ
ＶＣＮ"と呼ばれるそれ自身のＶＣＮを持ち、どの出力
仮想チャネルも、それ自身の"出力ＶＣＮ"を持つ。従っ
て、本スイッチによる各ユニキャスト（単一キャスト）
接続に関しては、１つのマスタＶＣＮと１つの出力ＶＣ
Ｎが存在し、一方、各マルチキャスト接続グループ毎
に、１つのマスタＶＣＮと複数の出力ＶＣＮが存在す
る。ユニキャストについては、マスタＶＣＮを出力ＶＣ
Ｎとしても使用する便法があり、マルチキャストの場合
でも、便法として、マスタＶＣＮを出力ＶＣＮの最初の
１つとして使用することができる。

【００５７】以下に詳しく述べるように、マスタＶＣＮ
は、セルを送り込む外部ポートの識別と組み合わせてセ
ル・ヘッダの（ＶＰＩ＋ＶＣＩ）から取り出される。最
初に、コントローラ３３に渡される各セル・ヘッダがそ
のマスタＶＣＮを決定し（図８のブロック６１参照）、
次に、このマスタＶＣＮが、コントローラにおけるヘッ
ダの待ち行列を制御するために使われる。出力ＶＣＮ
は、接続を設定する際にプロセッサ装置によって割り当
てられ、出力の待ち行列化とスケジュールを実行するた
めに使用される。出力ＶＣＮは、コントローラの適切な
データ構造においてその対応するマスタＶＣＮと関連づ
けられ、そのため、両方向、すなわち、マスタＶＣＮか
ら対応する出力ＶＣＮへと出力ＶＣＮを対応するマスタ
ＶＣＮへと、変換することが可能となる。

【００５８】２つのコントローラ経路 図８に示されようにコントローラ３３に２つの経路があ
る。１つは、セルの詳細（すなわち、各セルに関し、一
定のセル・ヘッダ・データと対応するセル本体アドレ
ス）を待ち行列に入れるための経路であり、他方は、コ
ントローラからのセル・ヘッダの出力を制御するため出
力ＶＣＮを待ち行列に入れ、スケジュールするための経
路である。

【００５９】セル詳細経路−この経路は、セル・ヘッダ
のマスタＶＣＮの探索の後、当該セルのセル詳細を記憶
できるかあるいは破棄すべきかをチェックするための監
視ブロック６２と、セル詳細待ち行列ブロック６３と、
出力されるべき次のヘッダに関するセル詳細をブロック
６３から受け取り、（新しいＶＰＩ＋ＶＣＩを探索する
ことを含み）新しいヘッダを生成し、その新しいヘッダ
と対応するセル本体のアドレスとを出力する出力ヘッダ
生成ブロック６４とを含む。同じマスタＶＣＮを持つセ
ル（すなわち同じＶＣソースからのセル）のセル詳細
は、ブロック６３において記憶される同じリスト６５の
待ち行列にすべて入れられる（各セルのセル詳細はそれ
ぞれのリスト・エントリとしてリスト６５に記憶され
る）。リスト６５は接続の設定の際プロセッサ装置によ
って空のリストとして作成される。各リスト毎に、セル
詳細入力制御６６は、リストの最後部（エントリが追加
される場所）をポイントする作成者ポインタ６７と、リ
スト６５が空であるか否かを示す空きフラグとを維持す
る。

【００６０】各リスト６５の先頭には、当該マスタＶＣ
Ｎに関する到来セル・ストリームに関してなお送出され
るべき最古のセル詳細についてのセル詳細エントリがあ
る。ユニキャストＶＣの場合は、先頭リスト・エントリ
は、唯一の出力ＶＣのため出力されるべき次のセルを識
別する。この先頭エントリは、セル詳細出力制御６９に
よって当該出力ＶＣＮのため記憶される使用者ポインタ
６８によってポイントされる。マルチキャストの場合
は、当然各入力ストリーム毎に複数の出力ＶＣがあり、
セルを出力する際に対応するリスト６５に応じて、各出
力ＶＣ毎にその進行を追跡することが必要である。これ
は、各出力ＶＣＮに関連付けられるそれぞれの使用者ポ
インタ６８を供給することによって達成される。実際
に、それぞれのセル詳細待ち行列７０が、各出力ＶＣＮ
に対して保持され、この待ち行列７０は、対応する使用
者ポインタ６８によってポイントされている待ち行列の
先頭と、当該マスタＶＣＮに関する作成者ポインタによ
ってポイントされている待ち行列の最後部とを持つリス
ト６５へマップされる。各マスタＶＣＮに関連付けられ
るそれぞれのセル詳細リスト６５と、出力ＶＣＮに関し
リスト６５上へマップされるそれぞれの待ち行列７０を
持つというこの概念は、セル詳細待ち行列ブロック６３
の動作において重要なものである。

【００６１】待ち行列７０の先頭エントリが出力制御６
９によって出力され、その結果対応する出力ＶＣＮのセ
ルが出力されると、待ち行列７０に関する使用者ポイン
タ６８は、待ち行列からそのエントリを除外するように
更新される。リスト６５の先頭エントリが、リストにマ
ップされるすべての待ち行列７０から除外されると、こ
のエントリは解放され、対応するセル本体アドレスが出
力制御６９によって空きアドレス・リスト３２上に戻さ
れる。

【００６２】出力ＶＣＮ送出制御経路−適切な外部スイ
ッチ・ポートを通して本発明のスイッチからセルを出力
する順序は、出力仮想チャネルに関して設定された出力
ＶＣＮを基に動作する送出制御経路によって決定され
る。以下にさらに詳細に説明するが、リスト６５が空き
から空きでない状態へ変化するときにかならず待ち行列
ブロック６３の入力制御６６によってそれ自身始動され
る出力ＶＣＮ送出始動ブロック８２によって、出力ＶＣ
Ｎはこの経路へ導入される。ブロック８２を始動するこ
とには、当該リストのマスタＶＣＮを当ブロックに渡す
ことが含まれる。始動ブロック８２は、このマスタＶＣ
Ｎを該マスタＶＣＮに関連する出力ＶＣＮに変換する。
これらの出力ＶＣＮは、直前に空でなくなったリスト６
５にマップされる待ち行列７０を有するＶＣＮである。
従って、これら出力ＶＣＮは、セルが送出可能な状態と
なった仮想チャネルを表す。始動ブロック８２は、送出
制御経路へ（特に資格制御ブロック７７へ）これら出力
ＶＣＮを導入する。一旦出力ＶＣＮがこの経路に導入さ
れたならば、その出力ＶＣＮは、対応するセル詳細待ち
行列７０が当該出力ＶＣＮに関して送出すべきセルがな
くなったことを示すまで、周期的にセルの送信を促進し
ながら経路の中を循環する。

【００６３】送出制御経路の主要部分は、資格制御ブロ
ック７７とスケジュール・ブロック７５である。セル出
力の実際のスケジュール決めは、各外部ポートに関する
それぞれの待ち行列構造（ブロック７６参照）を維持す
るケジュール・ブロック７５によって実行される。これ
ら待ち行列構造の各々は、対応する外部ポートに関連づ
けられ、少くとも１つのセルが送出できる状態にあるす
べての出力仮想チャネルの出力ＶＣＮを待ち行列に入れ
るために使用される。仮想チャネルは、（後述の"停止
ビット"により一時的に送出が禁止されていない限り）
対応する待ち行列７０中に少なくとも１つのエントリが
あり、また、該仮想チャネルが（下記に説明されるよう
に）送出のためのクレジットを、そのようなクレジット
が必要な場合、有しているならば、送出資格のある１つ
または複数のセルを持つ。

【００６４】出力仮想回路が1つ以上の送出有資格セル
を持つ時点を判定し、そのように判定したとき、該当す
る待ち行列構造に入れるためスケジュール・ブロック７
５へ対応する出力ＶＣＮを渡すのは、資格制御ブロック
７７の仕事である。従って、これら待ち行列構造は、"
有資格の"出力ＶＣＮを待ち行列に入れる構造とみなす
ことができる。有資格の出力ＶＣＮを適切な待ち行列構
造上に入れることは、各出力ＶＣＮに関し適切な待ち行
列構造の識別情報をブロック７７のテーブル８１に記憶
することによって行われ、この情報は、各出力ＶＣＮと
ともにブロック７５へ渡される。

【００６５】資格制御ブロック７７と関連ブロック８
０、８２の動作は、更に後述されるが、ここで、スケジ
ュール・ブロック７５の待ち行列構造に有資格出力ＶＣ
Ｎが格納されたと仮定する。

【００６６】スケジュール・ブロック７５には、外部ポ
ート・ロータ６０への同期アクセスを通してファブリッ
ク３０およびアダプタ・カードのデマルチプレクサの動
作でその動作が調整されるスケジュール機構７８が含ま
れる。スケジュール機構７８は、ロータ６０の適切なス
ロットにおける各外部ポートに関する出力ＶＣＮ構造を
検査し、該構造に関しもっとも高い優先度を持つ（もし
あれば）ＶＣＮを、セル詳細待ち行列ブロックの出力制
御６９へ出力する。次いで出力制御６９は、当該ＶＣＮ
に関する使用者ポインタ６８を使用して、対応するセル
詳細待ち行列７０の先頭にあるセル詳細エントリにアク
セスし、それら詳細を新しいヘッダが生成される出力ヘ
ッダ生成ブロック６４へ渡す。同時に、出力制御６９
は、当該ＶＣＮに関する使用者ポインタ６８を対応する
リスト６５における次のエントリをポイントするように
更新する。

【００６７】ある１つの出力ＶＣＮは、対応するＶＣに
関し出力有資格セルがいくつあるかにかかわらず、当該
外部ポートにとって適切な待ち行列構造７６においてた
だ一度だけ出現する。スケジュール機構７８がＶＣＮを
出力する度毎に、それは、対応する待ち行列構造から取
り除かれる。出力制御６９は、セル詳細を出力ＶＣＮに
出力すると、この出力ＶＣＮを資格制御ブロック７７に
渡す。これにより、この資格制御ブロック７７は、その
出力ＶＣＮに関するクレジット（credit）を減分するこ
とができ、同時に、出力制御６９は、対応するセル詳細
待ち行列に送出する準備のできているセルが更に１つま
たは複数あると判断すれば、"送信セルあり"標識の送信
によって資格制御ブロック７７にそれを通知する。資格
制御ブロック７７が、更新（減分）後なおこの出力ＶＣ
Ｎに関し記録された送出クレジットを有する場合（また
はクレジットが不要の場合）、出力ＶＣＮは、スケジュ
ール・ブロック７５へ戻され、そこで、対応する待ち行
列に再度入れられる。しかし、もし送信クレジットが
（必要ではあるが）直ちに使用可能でない場合、資格制
御７７ブロックは、スケジュール・ブロック７５へ出力
ＶＣＮを渡す前に、クレジット付与ブロック８０からそ
のようなクレジットが渡されるのを待つ。各出力ＶＣＮ
のクレジット状態は、資格制御ブロック７７によって維
持されるテーブル８１に保持される。

【００６８】もしも出力制御６９が、特定の出力ＶＣＮ
に関するセル詳細を出力した後に、対応する待ち行列７
０が空であると判断すれば、資格制御ブロック７７へ"
送信セルあり"標識を渡さない。しかし、もしも、同時
に、対応するリスト６５に残存エントリがない（該リス
トに関係するすべの待ち行列７０が空にされた）と出力
制御６９が判断するならば、該リストに関し空きフラッ
グがセットされるように、信号を入力制御６６に送る。

【００６９】新しいセルが特定の出力ＶＣＮの待ち行列
７０に到着したことを始動ブロック８２によって資格制
御ブロック７７が通知されると、これらの出力ＶＣＮの
各々は、出力制御６９が該出力ＶＣＮに関しいかなる有
資格セルも存在しないと判断するまで、ブロック７７と
スケジュール・ブロック７５と出力制御６９を巡回する
という点がこれまでの説明から明らかである（出力ＶＣ
Ｎ（複数）が各エントリに関するスケジュール決めを待
っている間に新しいエントリ（複数）が関連待ち行列７
０に追加される点が認められるであろう）。使用可能な
送出クレジットが存在しないことによってこのプロセス
は一時的に停止されるかもしれないが、新しいクレジッ
トが使用可能になり次第、プロセスは再開される。

【００７０】出力ＶＣＮが（使用可能エントリがその待
ち行列７０にないため）巡回を停止すると、送出のため
の再スケジュールが行われるまで、該出力ＶＣＮは、始
動ブロック８２による送出制御経路への再導入を待たな
ければならない。

【００７１】サービス特性 本発明のスイッチは、以下の３つの異なるサービス特性
の接続を提供する。 −最大待ち時間が小さい保証された帯域幅（ＧＢ０） −最大待ち時間がより大きい保証された帯域幅（ＧＢ
１） −最善努力（ＢＥ） スケジュール・ブロック７５における各外部ポート待ち
行列構造（７６ブロック）は、実際に（各サービス品質
について１つの）３つの待ち行列を含み、各有資格出力
ＶＣＮが、該当する待ち行列に加えられる（この待ち行
列の識別情報は資格制御ブロックのテーブル８１に保持
され、出力ＶＣＮとともにブロック７５に渡される）。
この結果、各サービス・クラスの範囲内で公平な待ち行
列方法が使用されることとなる。図９は、スケジュール
・ブロックによって維持される外部ポートの出力ＶＣＮ
待ち行列を図示し、ポート０と記号が付けられた外部ポ
ートの場合外部ポート毎に３つの待ち行列が付与されて
いることを示している。ロータ６０の対応するスロット
における外部ポート待ち行列を検査する度毎に、スケジ
ュール機能７８は、もっとも高い優先度の空でない待ち
行列の先頭の出力ＶＣＮを取り出す。ここで、待ち行列
の優先順序は、ＧＢＯ、ＧＢ１、ＢＥである。

【００７２】保証された帯域幅サービスに関しては、適
切な量の共有メモリ３１が、そのサービスに応じて各入
力ＶＣのために予約され、さらに、クレジット制御方式
がトークン・バケット（複数）に基づいて操作される。
保証された帯域幅ソースがその保証を越えると（すなわ
ち、スイッチが処理を保証した以上に単位時間あたりの
セルを帯域幅ソースが作成すると）、資格制御ブロック
は、一時的にそのＶＣＮに関するセルの送出（定形出
力）を停止させるか、または、最善努力接続（非定形出
力）として一時的に接続を処理する。

【００７３】最善努力型トラフィックは、フロー制御が
行われることも行われないこともある。フローが制御さ
れるトラフィックの場合、メモリの固定量が各入力ＶＣ
に割り当てられ、このメモリの空き量に基づいて、クレ
ジットが上流ノードに発行される。各出力ＶＣＮに関し
て、下流ノードが発行したクレジットの計数が維持され
る。この上流／下流クレジット制御は、フロー制御ブロ
ック８５によって管理され、フローが制御された出力Ｖ
ＣＮに関するクレジット計数が、資格制御ブロック７７
によって現行ノードに保持される。このクレジット計数
がゼロになると、資格制御ブロックはＶＣＮが対応する
スケジューラ待ち行列に渡されるのを止め、それによっ
て伝送を停止させる。

【００７４】フローが制御されない最善努力型接続は、
それら接続に任意の量のメモリを割り当てるとができ
る。もしも出力に関し競合があってこのメモリが費消し
てしまう場合、セルは破棄される。

【００７５】マルチキャスト、空きフラグおよび停止ビ
ット 上述の通り、マルチキャスト（１つの入力ＶＣに対する
複数の出力ＶＣ）の場合、対応するセル詳細リスト６５
は、そこへマップされるいくつかの（各々が特定の出力
ＶＣＮに対応する）待ち行列７０を有する。やはり上述
の通り、待ち行列ブロック６３に対する出力制御６９
は、リスト６５に関連するすべての待ち行列７０が空に
なるまで、リスト６５の空きフラグをセットさせない。
この理由は、そのセル詳細がリスト６５上で待ち行列に
入れられるべき新しいヘッダの到着に応じて空きフラッ
グをセットから非セット状態へ変化させることにより、
入力制御６６が送出始動ブロック８２を始動させ、その
結果、リストに関連したすべての出力ＶＣＮが送出制御
経路に導入されることとなるためである。もしもあるリ
ストの空きフラグがただ１つ空きとなる関連待ち行列に
セットされたとすれば、いくつかの出力ＶＣＮがまだ経
路にある時点で、送出始動ブロック８２が始動され、出
力ＶＣＮを送出制御経路に導入することとなり、この結
果、不公平な出力スケジュールが行われる。

【００７６】スイッチ動作の間に、新しいリスト・エン
トリが以下の時間の間に追加されることが起こり得る。 (i)リスト６５の先頭エントリが関連する出力ＶＣに関
するセル・ヘッダを出力するため使用された後、この先
頭エントリを待ち行列７０から取り除くための使用者ポ
インタ調整に続いて待ち行列の１つが空となる時、およ
び、(ii)エントリがその待ち行列に関連した出力ＶＣに
関するヘッダを出力するために使われた後、使用者ポイ
ンタ調整によって取り除かれたものと同じリスト・エン
トリを別の待ち行列が持つ時。このような状況におい
て、上記の待ち行列の２番目は、第１の待ち行列を空に
させたエントリを取り除くとき空ではなく、すべての他
の待ち行列が空であっても、空きフラグは、出力制御６
９によってセットされない。このような状況では、空に
なった待ち行列がスケジュール決めプロセスに再び入る
機会を持つことができないことは明白である。なぜな
ら、上記の空でないリストを常に空でないままにしなが
ら、新しいセル詳細エントリを該リストに追加し続ける
ことができるからである。ある特定の入力ＶＣへ割り当
てられるメモリの量には限りがあるので、当然セルは失
われるであろう。

【００７７】この問題を回避するため、リスト６５の各
セル詳細エントリは関連する"停止ビット"を持つ。マル
チキャストの場合において、もし、待ち行列７０が空に
なると、出力制御６９は、先頭エントリ（すなわち空き
待ち行列から直前に取り除かれたエントリ）の停止ビッ
トをセットする。このエントリを取り除く同じリスト上
の他の待ち行列に関して（そのエントリに基づくセル・
ヘッダが関連出力ＶＣＮに関し送出されたため）、対応
する出力ＶＣＮは、資格制御ブロック７７へ戻されな
い。すなわち、待ち行列は、効果的に"停止"される。し
かし、すべての待ち行列が、停止ビットのセットされて
いるエントリを使用したとき、そのエントリは取り除か
れ、ＶＣＮ送出始動ブロックが、出力制御６９によって
始動され（図８の「停止解除」始動参照）、対応するマ
スタＶＣＮがすべての関連するＶＣＮを送出制御経路に
再導入する。

【００７８】出力ＶＣＮ送出始動ブロック 始動ブロック８２の一般的機能性は既に記述したが、こ
の時点でいくつかの点を追加することは意味があろう。
ブロック８２は、マルチキャスト拡張機構８３と出力回
路８４を含む。マルチキャスト拡張機構８３は、特定の
マスタＶＣＮについて始動される時該特定マスタＶＣＮ
に対応するすべての出力ＶＣＮを使用可能にするように
設計される。マルチキャスト拡張機構８３は、ある接続
が設定または終了される度毎にプロセッサ装置からの適
切なデータを用いてプログラムし直され、そのため、そ
れは継続的に最新に更新され、すべての現時点マスタＶ
ＣＮを対応する出力ＶＣＮに関連付けることができる。
拡張機構８３によって使用可能とされる出力ＶＣＮは、
出力回路８４によって資格制御ブロック７７へ１つずつ
渡される。

【００７９】始動ブロック８２は、他のものを受け取る
前に処理を完了する必要はないが、受け取るすべての始
動要求を受容できるような方法で実施される。これは、
例えば、始動信号のための入力ＦＩＦＯを含めることに
よって、または、おそらく出力ＶＣＮ ＦＩＦＯを備え
持つことによって実施できる。一般的には、必要とされ
ることは、資格制御ブロックへの転送のような出力ＶＣ
Ｎ動作にブロック８２が影響を与える必要がある場所の
上流地点にＦＩＦＯバッファ機能を具備することであ
る。

【００８０】ブロック８３が始動されるこのような構成
および環境の重要性は、マルチキャスチング固有の拡張
機能が、コントローラにかかわる処理ひずみの発生を最
小にとどめるような方法で取り扱われることである。か
くして、各マスタＶＣＮと出力ＶＣＮはブロック８３に
おいてただ一度だけ出現し、これにより、とくに効率的
なメモリの活用が可能となる。さらに、いかなる特定の
始動に関連した出力ＶＣＮ毎の処理も、次の始動を受け
取る前に完了する必要はない。

【００８１】マスタＶＣＮ探索ブロック 本発明は、扱いやすいマスタＶＣＮの生成に関し、した
がって、マスタＶＣＮ探索（ルックアップ）ブロックに
ついて、以下に詳しく述べる。

【００８２】既に説明のとおり、セルがスイッチ・コア
に到着すると、そのヘッダは、コントローラ３３に渡さ
れ、そこで、先ずマスタＶＣＮ探索ブロック６１によっ
て取り扱われる。ブロック６１における受領時点で、ヘ
ッダは、以下のフィールドから構成される。 −一般フロー制御（ＧＦＣ）、４ビット −仮想経路識別子（ＶＰＩ）、８ビット −仮想チャネル識別子（ＶＣＩ）、１６ビット −ペイロード・タイプ（ＰＴ）、３ビット −ＡＡＬ５接続がパケットの終了（ＥＯＰ）を形成する
ためのビット、１ビット。 注：ヘッダの５番目のバイトのヘッダ・エラー・チェッ
ク（ＨＥＣ）が該当するアダプタ・カードにおいて既に
検査されたので除去されている。ＨＥＣがエラーのと
き、当該セルは、空（ＶＰＩ＝ＶＣＩ＝０）としてマー
ク付けされることとなる。

【００８３】セル本体アドレスは、また、対応するセル
・ヘッダとともに、ＶＣＮ探索ブロック６１に渡され
る。以下の動作が、ヘッダに関してブロック６１によっ
て実行される： −セルのＶＰＩとＶＣＩがゼロにセットされているなら
ば、そのセルは破棄される。この破棄は、セル本体アド
レスを空きアドレス・リスト３２に戻すことによって実
行される。 −ＧＦＣが破棄される。 −ＰＴとＥＯＰが、セル本体アドレスとともに記憶され
るために取り出され、出力ヘッダが正しく生成される。
これらの項目を以下"セル詳細"と呼ぶ。 −ＶＰＩおよびＶＣＩをセルが受け取られた外部ポート
を識別する番号（ポート番号）と連結し、セルが関連す
る接続のための特異な識別子（本明細書では長いチャネ
ル識別子と呼ぶ）を作成する。次に、この長いチャネル
識別子を用いて、セルに関連するマスタＶＣＮを探索す
る。

【００８４】上記４番目の機能はブロック６１の主要な
機能であり、以下で更に詳細に説明する。あるセルに関
し長いチャネル識別子を取り出すために使われるＶＰＩ
とＶＣＩ情報は、セル・ヘッダから直接用いられる。セ
ルが受け取られた外部入力ポートを識別するポート番号
は、本実施例においては、外部入力ポート・ロータ６０
Ａから取り出される（各外部ポートは、関連する特異な
番号を持って上記ロータに記録されている）。

【００８５】一旦入力ポート番号が得られたならば、そ
の入力ポート番号は、ＶＰＩとＶＣＩに連結され、約３
０ビットの長さの長いチャネル識別子となる（その正確
な長さは、スイッチが持つことができるポートの数に依
存する）。次いで、この番号は、セルが関連する接続の
マスタＶＣＮを見出すために使われる。

【００８６】この長さの識別子を用いて単純な探索を行
うことは非実用的であるので、多段式探索プロセスが使
われる。探索プロセスは、以下のステップを含む： １．長いチャネル識別子（ＶＰＩ＋ＶＣＩ＋ポート番
号）は、スクランブラ９０においてスクランブルされる
（図１０参照）。スクランブラは、線形フィードバック
・シフト・レジスタに基づくもののような標準形式のも
のでよく、そこでは、スクランブル結果の出力ワードを
与えるためワード長だけシフトされる線形フィードバッ
ク・シフト・レジスタに関するシード（種）ワードとし
てチャネル識別子が使われる。 ２．スクランブルされた長いチャネル識別子が、スプリ
ッタ９１によって２つの部分に分割される。一つの部分
（上方部分）は、"高位テーブル"９２において"行イン
デックス"を探索するために使われ、他方の部分（下方
部分）は、"低位テーブル"９３において"列インデック
ス"を探索するために使われる。 ３．次に、"行インデックス"と"列インデックス"は、マ
スタＶＣＮ（複数）を含む２次元テーブル９４にアクセ
スするために使われる。 ４．最後に、チェック・テーブル９５において長いチャ
ネル識別子を探索するためにマスタＶＣＮが使われ、こ
の識別子は、すべてが順当に動作するならば、ステップ
１で使われたであろうものに相当する。探索された識別
子は、比較器９５において実際のオリジナルの長いチャ
ネル識別子と比較され、ステップ１から３のプロセスが
間違った結果を与えなかったかがチェックされる（もし
も誤りがあれば、セル本体アドレスを空きアドレス・リ
ストに加えることによってセルは破棄される）。

【００８７】上記探索プロセスのステップの各々を実行
する理由は、次に述べる通りである。 ステップ１. 同一のリンクからのセルに関する最も長い
チャネル識別子（複数）が同等の上位部分（たぶんゼ
ロ）を有することがあり得るため、長いチャネル識別子
をスクランブルする必要が起きる。従って、長いチャネ
ル識別子がスクランブルされなければ、それらはすべ
て、高位テーブル９２における同一のインデックスにイ
ンデックス付けし、これにより、マスタＶＣＮテーブル
９４のただ１行だけが使われることとなる。スクランブ
ルによってすべての識別子間で差がつけられ、そのた
め、行および列のテーブルの利用度が向上し、マスタＶ
ＣＮテーブルがいっそう効率的に使用されることとな
る。

【００８８】ステップ２. ３０ビット長の番号を調べる
ことは非実用的であるが、１５ビット長い番号を調べる
ことは実用的であるので（３２Ｋビット長のエントリ・
テーブルが必要とされる）、スクランブルされた長いチ
ャネル識別子は、半分に分割される。番号をさらに小さ
く分割すると、３つの１Ｋビット長のテーブルになり、
これは一見魅力的ではあるが、作成されるテーブルが多
数のＶＣをサポートするには小さすぎるので、この選択
は、特殊な状況の場合にのみ適切である。

【００８９】ステップ３. 高位と低位テーブルの２つの
探索結果は、接続を特異に識別するけれども、テーブル
上に散在しているので、それらテーブルはマスタＶＣＮ
テーブルにインデックスを付けるために使われる。これ
は、マスタＶＣＮテーブルが約４分の１以上使われる
と、プロセスが充分に動作しないことによる。従って、
高位と低位テーブルの結果を使用することは、ＶＣＮ空
間をそうあるべきよりも４倍広くするものであり、コン
トローラの残りのＶＣＮ当たりデータ構造のすべてのメ
モリ要求を増加させることを可能ならしめる。

【００９０】ステップ４. 設定されなかったＶＣ（複
数）にもセルが到着することがあり得るので、長いチャ
ネル識別子チェックが実行される。チェックが実行され
ず、そのようなＶＣが偶然有効なマスタＶＣＮにインデ
ックス付けした場合、それらセルは、あたかもそれらが
そのマスタＶＣＮに対応するＶＣ上に到着したかのよう
に取り扱われるであろう。

【００９１】前述の探索プロセスは、大量のＶＣＮの迅
速な探索を低コストのハードウェアで実行することを可
能にする。例えば、最高６４個の外部ポートに関連付け
られる８０００個のマスタＶＣＮは、３２Ｋｘ８の高位
テーブル、３２Ｋｘ８の低位テーブル、６４Ｋｘｌ３の
マスタＶＣＮテーブルおよび８Ｋｘ３０のチェック・テ
ーブルを必要とする。

【００９２】あるＶＣ接続が設定されると、プロセッサ
装置２４は、マスタＶＣＮ探索ブロック６１の各種テー
ブルに収納するエントリの数を計算する。以下の例から
分かるように、プロセッサ装置２４は、高位テーブルと
低位テーブル９２、９３に入れるエントリを選ぶ自由度
は一般的に限られている。一方、テーブル９４に挿入さ
れたマスタＶＣＮの値は、既存の値と衝突しない限り、
プロセッサ装置によって自由に選ぶことができる。テー
ブル９２および９３を設定する際、プロセッサ装置は、
特定のＶＣが、以前に設定されたＶＣと衝突せずに、最
初に、既存のテーブルに入ることができないことを見い
出す場合がある（特に、新しいＶＣのスクランブルされ
た長いチャネル識別子と前のＶＣが両方とも同じマスタ
ＶＣＮテーブル・エントリにマップされる場合）。この
場合、プロセッサ装置は、衝突をなくすために、マスタ
ＶＣＮテーブル９４を変更することを試みる（以下に詳
しく述べる）。これができない場合は、衝突がこれ以上
ないように新しいテーブルを生成するために、スクラン
ブラ９０によって使用されるスクランブル機能を変更す
るようにプロセッサ装置２４が準備される。この動作を
支持するために、高位テーブル、低位テーブル、および
マスタＶＣＮテーブルは二重バッファになっていて、プ
ロセッサ装置が１つのテーブルを書きかえている間、別
のテーブルで探索が続けられる。

【００９３】図１１ないし図２０を参照して、新しいＶ
Ｃを加えるために、テーブル９２ないし９４を設定する
ためにプロセッサ装置２４が用いる一般的処理について
述べる。この処理は、スクランブルされた長いチャネル
識別子が２つのヘキサデシマル・ディジットとして表さ
れた８ビット長の単純な例を用いて述べる。これらのデ
ィジットは、それぞれが１６のエントリを持つ高位テー
ブル９２および低位テーブル９３をアクセスするために
使われる（図１１を参照）。マスタＶＣＮテーブルの大
きさは、それぞれ１から４まで番号をつけた４行４列に
なるように選択されている。理解を容易にするために、
マスタＶＣＮテーブル９４の塞がったエントリに挿入さ
れたマスタＶＣＮは、高位及び低位両テーブルをアクセ
スするのに使われるスクランブルされた長いチャネル識
別子と同じものとしてある。これから説明する例は相対
的に単純なものであるが、この例が示す動作は、より大
きな高位、低位、およびマスタＶＣＮテーブルによって
サポートされるより大きなマスタＶＣＮに使うことがで
きる。

【００９４】記述を簡潔にするために、以下の例では、
高位テーブル、低位テーブルをアクセスするために分割
された、スクランブルされた長いチャネル識別子は"Ｖ
ＣＩＤ"と呼ぶ。さらに、マスタＶＣＮおよびマスタＶ
ＣＮテーブル９４を参照する際は、あたまの"マスタ"は
省略する。

【００９５】図１１に示した例は、１つのＶＣＩＤ、Ｂ
６のために構成されたテーブルを示す。ＶＣＩＤが与え
られると、ＶＣＩＤは半分に分割され、Ｂは行の２を与
えて高位テーブルをインデックスするのに使われ、６は
列３を与えて低位テーブルをインデックスするのに使わ
れる。高位テーブルから行の値２、および低位テーブル
から列の値３（エントリ位置の値が２、３になる）を使
ってＶＣＮテーブル９４においてＶＣＮが探索（ルック
アップ）され、このＶＣＮについてＢ６という値が見つ
かる。

【００９６】新しいＶＣＩＤを加えるとき、可能性とし
て以下の４つのケースがる。 １. ＶＣＩＤによって参照される高位テーブルおよび
低位テーブル両方のエントリが空である場合。 ２. 高位テーブルのエントリは塞がっていて、低位テ
ーブルのエントリに空がある場合。 ３. 高位テーブルのエントリに空があり、低位テーブ
ルのエントリが塞がっている場合。 ４. 高位テーブルも低位テーブルもエントリがいっぱ
いである場合。 これらのケースの各々について順番に説明する。

【００９７】１. ＶＣＩＤによって参照される高位テ
ーブルおよび低位テーブル両方のエントリが空である場
合。この場合、プロセッサ装置２４は、ＶＣＩＤのそれ
ぞれの半分によってアクセスされた高位テーブルおよび
低位テーブルのエントリに挿入した行の値および列の値
を選ぶことができる。この選択をする際に、プロセッサ
装置は、先ず、ＶＣＮテーブルの中の最も満ちていない
行を見つけ、この行番号を高位テーブルに挿入する。こ
の行の中で、行に空きのエントリを持つ最も満ちていな
い列が選ばれ、その列番号が低位テーブルに挿入され
る。ケース１の状況の例は、図１２に示すように、８Ｄ
というＶＣＩＤが図１１の例に加えられる。この結果、
位置（１、１）が選ばれる。このケースでは、ＶＣＮテ
ーブルがいっぱいでない限り、この処理はしくじること
はない。

【００９８】２。高位テーブルのエントリが塞がってい
て、低位テーブルのエントリに空がある場合。この場
合、使える行は、高位テーブルに既にあるエントリによ
って固定されている。プロセッサ装置は、低位テーブル
に入れるべき列の値を、テーブル９４の行に空きのエン
トリがあり使われ方が最も少ない列を探すことによっ
て、選択する。このケース２は、図１２の例に８Ｃとい
うＶＣＩＤが加えられたときに起こる。この結果、図１
３に示すように、位置（１、２）が選択される。この処
理は、行がいっぱいのときには実行できない。しかし、
実際には、常にエントリは最も満ちていない行に加えら
れるので、行がいっぱいになることはなく、通常、この
ようなことは起こらない。それにもかかわらず、そのよ
うなことが起こる場合は、対象としている行のエントリ
を空けるためにテーブルを再整理することによって対処
できる。

【００９９】３。高位テーブルのエントリに空があり、
低位テーブルのエントリが塞がっている場合。このケー
スはケース２と同じように処理されるが、相違点は、列
が固定され行が選択される。このケースは、ＶＣＩＤ
Ｄ６が図１３の例に加えられるときに起こる。この結
果、図１４に示すように、位置（３、３）が選択され
る。

【０１００】４。高位テーブルも低位テーブルもエント
リがいっぱいである場合。このケースは、図１４の例に
ＶＣＩＤ ＢＤが加えられたときに起こる。行および列
が、高位及び低位両テーブルに既にあるエントリによっ
て固定されている。これは、図１５に示すように、位置
（１、２）を使わなければならないことを意味する。

【０１０１】しかし、この動作は、位置（１、２）が空
いていたので可能であった。これは、図１６の新しい例
にＶＣＩＤ ２Ａを加えようとする例からわかるよう
に、必ずしも可能というわけではない。このエントリ
は、高位テーブルと低位テーブルのエントリが位置
（１、３）を指すが、この位置は既に塞がっているの
で、加えることができない。このケースの解決方法は、
エントリ２４（占領エントリと呼ぶ）を動かすことであ
る。しかし、占領エントリの行を変えることではこの問
題は解決できない。というのは、占領エントリのＶＣＩ
Ｄの上位半分は、挿入しようとするＶＣＩＤの上位半分
と同じであるからである。したがって、低位テーブルの
エントリ４に記憶されている値を変えることによって、
占領エントリの列を変えなければならない。この値は、
全てのＶＣＮのためのスペースを持つ、このエントリ
（この場合２４と８４）が指す最も満ちていない列を指
すように変えられる。再整理して２Ａを加えた後の結果
を図１７に示す。

【０１０２】行だけを動かすことができる場合にも同様
の状況が起きる。また、占領エレメントのある行または
列のどちらかを変える状況を得ることも可能である。そ
のようなケースが図１８に示されており、ＶＣＩＤ ２
Ａを加えるとき、テーブル９４の既存のエントリＶＣＩ
Ｄ ３４と衝突が起こる。この場合、衝突するＶＣＩＤ
の高位テーブルあるいは低位テーブルの部分が同じでな
いことに留意されたい。

【０１０３】これらの４つのケースのいずれにおいて
も、占領エレメントを動かす先に空いた正しい位置を持
つ行あるいは列がないために、再整理をしてもうまくい
かない可能性がある。そのような例を、ＶＣＩＤ ２Ａ
を加えようとするケースとして、図１９に示す。この例
では、位置（１、３）で、新しいＶＣＩＤが既存のＶＣ
ＩＤ ２４と衝突を起こす。衝突しあうＶＣＩＤが高位
テーブルの同じ参照（２）を持つので、占領エントリ２
４の低位テーブルのエントリ（すなわち低位テーブルの
エントリ４の値）を変更しなければならない。しかし、
この例では、行１および４（これらの行は、低位テーブ
ルのエントリ４を通して参照しなければならない列の、
既存の塞がった行である）に空きの列がないので、低位
テーブルのエントリ４のポインタを変更できない。この
状況は、占領エレメント（２４）を外し、加えるべきエ
レメント（２Ａ）で置き換え、占領エレメントがもとに
戻れるようにテーブルを再整理することによって処理で
きる。この動作の結果として、その列の別のエレメント
を動かすので、うまくいく可能性がある。この例では、
エントリ２４を外し２Ａを加えた後、低位テーブルのＡ
にあるエントリを（３）から（２）に変更する。これが
できるのは、テーブル９４の列２の第１および第２の行
が空で、低位テーブルのエントリＡの値を変更すること
によって動かされたエントリ２Ａおよび４Ａを受け取る
ことができるからである。この変更が行われた後、図２
０に示すように、エレメント２４は、もとの場所に再び
挿入される。

【０１０４】図２１に、新しいＶＣＩＤのためにテーブ
ル９２ないし９４を更新しようとするときに、プロセッ
サ装置２４によって実行される上述の処理を流れ図で示
す。流れ図で、"Ｈ−Ｔ"、"Ｌ−Ｔ"、および"ＶＣＮ−
Ｔ"は、それぞれ、高位テーブル、低位テーブルおよび
マスタＶＣＮテーブルを表す。

【０１０５】図２１の流れ図で、最初のステップ１００
で、高位テーブルおよび低位テーブルをチェックして、
新しいＶＣＩＤによって参照されるこれらのテーブルの
位置が既に塞がっているかどうかを調べる。ステップ１
０１、１０２、および１０３は、上述したケース１、
２、および３の処理に対応するものである。残りのステ
ップ１０４ないし１１０は、上述のケース４の処理に対
応するものである。とくに、ステップ１０４でＶＣＮテ
ーブルに衝突があるかが調べられ、衝突がある場合には
ステップ１０５が実行され、新しい占領ＶＣＩＤが、同
じ高位テーブル参照あるいは低位テーブル参照を持って
いるかが判断される。ステップ１０６、１０７、および
１０８は、占領エントリの行／列を再整理しようとする
ための処理である。この手法が実行できない場合（ステ
ップ１０９）、ステップ１１０が実行され、占領エント
リは除かれ、新しいエントリが挿入され、再整理が行わ
れ、除かれた占領エントリはもとに戻される。

【０１０６】プロセッサ装置２４は、ソフトウェア制御
の下に、図２１の処理を遂行することが出来るが、速い
実行を確実にするためには、これらの処理の全部あるい
は部分を、適切なハードウェア手段を用いて具体化する
こともできることを理解されたい。

【０１０７】また、上記の説明では、ただ２個の探索キ
ーがスクランブルされた長いチャネル識別子から得られ
たが、そのようなキーをＫ個（Ｋは２以上）提供できる
ことも理解されたい。この場合、マスタＶＣＮテーブル
はＫ次元のテーブルになり、Ｋ個のキーを使ってＫ個の
インデックスを求め、これらのＫ個のインデックスを使
ってテーブルがアクセスされる。

【０１０８】さらに、上述したコントローラの概念の多
くは、セル（固定長パケット）を扱うシステムはもちろ
んのこと、可変長パケットを持つ、パケットに基づくシ
ステムにも適用できることを理解されたい。

【０１０９】本発明には、例として次のような実施態様
が含まれる。 （１）少なくとも１つの入力ポートを通して受け取られ
たパケットに関して予定の機能を実行するパケット処理
装置であって、各パケットは、パケットを受け取った該
装置の入力ポートに対して、該パケットに関連する仮想
チャネルを特異に識別するチャネル・ラベルを持ち、前
記装置は、受け取った各パケットについて、該パケット
に関連する仮想チャネルおよび入力ポートの組合せを特
異に識別するマスタＶＣＮと称する識別子を提供するＶ
ＣＮ提供手段と、前記ＶＣＮ提供手段によって提供され
たマスタＶＣＮに依存して各パケットに関して前記の予
定の機能を実行する処理手段と、を備え、前記ＶＣＮ提
供手段は、各パケットに対し、パケットを受け取った入
力ポートを識別するそれぞれのポート・ラベルを生成す
るポート識別手段と、パケットに関連するチャネル・ラ
ベルおよびポート・ラベルを結合して出力される長いチ
ャネル識別子を生成する結合手段と、前記結合手段の出
力を予定の方法で分割し、Ｋが２以上の整数であるＫ個
のキーを提供するキー提供手段と、前記のＫ個のキーが
適用されるテーブル探索手段と、を有し、前記テーブル
探索手段は、パケットに関連するＫ個のキーの各々を、
それぞれ対応するより短いインデックスに変換するそれ
ぞれの変換手段と、それぞれのマスタＶＣＮを保持する
位置を持つＫ次元のマスタ・テーブルであって、対象と
するパケットのマスタＶＣＮを提供するために、同一パ
ケットから得られたＫ個のインデックスが、対応するマ
スタ・テーブルの位置をアクセスする役割をするように
した、Ｋ次元マスタ・テーブルと、を有する、パケット
処理装置。

【０１１０】（２）前記結合手段が、前記長いチャネル
識別子が出力される前に、該長いチャネル識別子をスク
ランブルするように動作する、上記（１）に記載の装
置。 （３）前記パケットの各々がＡＴＭセルで、該ＡＴＭセ
ルに含まれた前記チャネル・ラベルが仮想経路標示およ
び仮想チャネル標示を有する、上記（１）に記載の装
置。

【０１１１】（４）ＶＣＮ提供手段がさらに、前記テー
ブル探索手段によって提供されたマスタＶＣＮの正確さ
を確認する確認手段を有し、前記確認手段が、各マスタ
ＶＣＮを、前記マスタＶＣＮを提供するときに使われる
はずであった前記長いチャネル識別子の少なくともあら
かじめ定められた部分に関連させ、マスタＶＣＮが供給
されたときに前記の少なくともあらかじめ定められた部
分を出力する、チェック・テーブル手段と、前記チェッ
ク・テーブル手段の出力を、チェック・テーブル手段に
供給されたマスタＶＣＮを提供する際に実際に使われた
長いチャネル識別子の対応する部分と比較し、比較の結
果の標示を出力するように動作する比較手段と、を有す
る、上記（１）に記載の装置。

【０１１２】（５）前記装置が、前記ＶＣＮ提供手段を
含むコアと、複数の前記入力ポートを提供し、前記入力
ポートで受け取られたパケットをマルチプレクスし、あ
らかじめ定められたタイミングに従ってパケットを前記
コアに渡すマルチプレクサ手段を含む外部インタフェー
ス手段と、を備え、前記ポート識別手段が、パケットが
前記コアに到着する時間に依存して、パケットに対し前
記ポート・ラベルを生成する、上記（１）に記載の装
置。

【０１１３】（６）前記変換手段の各々が、関連する前
記のキーを対応する前記のインデックスに関連させるリ
スト手段を有する、上記（１）に記載の装置。

【０１１４】（７）前記装置がさらに、新しい仮想チャ
ネルのパケットにマスタＶＣＮを提供するために前記テ
ーブル探索手段を設定する新エントリ手段を有し、これ
らのパケットに関連するチャネル・ラベルおよびポート
・ラベルが、新キーと称するＫ個の特性キーをテーブル
探索手段に適用させることができ、前記新エントリ手段
が、新しい仮想チャネルのマスタＶＣＮを前記マスタ・
テーブルの指定された位置に挿入する挿入手段と、前記
のＫ個の新キーが前記リスト手段に既にあるインデック
スを参照しているかを判断する判断手段と、前記判断手
段が前記インデックスがないと判断すると、適切な前記
のインデックスを対応するリスト手段に挿入し、前記の
新キーによって参照されるＫ個のインデックスが前記マ
スタ・テーブルの既存の塞がったテーブル位置に関して
よく分配された空きの位置を識別できるように、前記の
適切なインデックスを選択し、前記インデックスによっ
て指示された空きのテーブル位置を挿入手段に知らせ該
挿入手段に空きのテーブル位置に前記マスタＶＣＮを挿
入させるようにする、リスト設定手段と、を有する、上
記（６）に記載の装置。

【０１１５】（８）前記新エントリ手段がさらに、前記
判断手段が前記全ての新キーに対してインデックスが既
に存在すると判断したときに、前記インデックスによっ
て指されたテーブル位置を検査し、前記テーブル位置が
空いていることがわかると、前記挿入手段に、その空い
ているテーブル位置に新しい仮想チャネルのマスタＶＣ
Ｎを挿入させる検査手段と、前記検査手段により、前記
インデックスによって指されたテーブル位置にエントリ
が存在して塞いでいることが判明したことに反応し、塞
いでいるエントリに関連する前記インデックスを調整す
ることによって前記テーブル位置を空けることができる
かを判断し、空けられれば、この調整を行い、前記挿入
手段に新しい仮想チャネルのマスタＶＣＮを前記の空い
た位置に挿入させる、調整手段と、を有する、上記
（７）に記載の装置。

【０１１６】（９）前記新エントリ手段がさらに、前記
の調整手段が前記テーブル位置を空けることができない
ときに動作する付加的調整手段を持ち、前記の塞いでい
るエントリを外して新しい仮想回線の前記マスタＶＣＮ
で置き換え、その後、前記マスタＶＣＮに関連する前記
インデックスを調整することにより前記テーブル位置を
空けることができるかを判断し、空けられるならば、こ
の調整を行って、前記の塞いでいるエントリを置き換え
る、上記（８）に記載の装置。

【０１１７】（１０）装置の少なくとも１つの入力ポー
トを通して受け取られたパケットに対し、前記パケット
に関して予定の機能を実行する意図でマスタＶＣＮと称
するパケット・ストリーム識別子を生成する方法であっ
て、各パケットは、パケットを受け取った入力ポートに
対して、そのパケットに関連する仮想チャネルを特異に
識別するチャネル・ラベルを持ち、前記方法が、Ｋが２
以上の整数の、マスタＶＣＮを記憶するＫ次元の探索テ
ーブルを提供するステップと、特定の前記パケットに関
連するマスタＶＣＮを提供するために、(i)前記パケッ
トに対し、そのパケットを受け取った入力ポートを識別
するポート・ラベルを生成し、(ii)長いチャネル識別子
を作成するために、前記パケットに関連するチャネル・
ラベルおよびポート・ラベルを結合し、(iii)Ｋ個のキ
ーを提供するために、あらかじめ定められた方法で前記
長いチャネル識別子を分割し、(iv)前記各キーを、対応
する、それぞれの、より短いインデックスに変換し、
(v)前記Ｋ次元探索テーブルに、前記インデックスを使
って、対象としているパケットのマスタＶＣＮを探索す
る、ことからなるサブステップを実行するステップと、
を有する、前記方法。

【０１１８】（１１）前記方法が長いチャネル識別子を
スクランブルするサブステップをさらに含み、前記サブ
ステップ(iii)は、前記スクランブルされた長いチャネ
ル識別子に対してはたらく、上記（１０）に記載の方
法。

【０１１９】（１２）少なくとも１つの入力ポートを通
して受け取られたパケットに関して予定の機能を実行す
るパケット処理装置であって、各パケットは、パケット
を受け取った入力ポートに対して、該パケットに関連す
る仮想チャネルを識別するチャネル・ラベルを持ち、前
記装置は、受け取った各パケットについて、該パケット
に関連する仮想チャネルおよび入力ポートの組合せを識
別するマスタＶＣＮと称する識別子を提供するＶＣＮ提
供手段と、前記ＶＣＮ提供手段によって提供されたマス
タＶＣＮに依存して各パケットに関して前記の予定の機
能を実行する処理手段と、を備え、前記ＶＣＮ提供手段
は、各パケットに対し、パケットを受け取った入力ポー
トを識別するそれぞれのポート・ラベルを生成するポー
ト識別手段と、パケットに関連するチャネル・ラベルお
よびポート・ラベルを結合する結合手段であって、該結
合手段によってスクランブルされる長いチャネル識別子
を作成する結合手段と、少なくとも２個のキーを提供す
るために、パケットのスクランブルされた長いチャネル
識別子をあらかじめ定められた方法で分割するキー提供
手段と、マスタＶＣＮを保持するマスタ・テーブルを含
むテーブル探索手段であって、特定のパケットに関連す
る前記少なくとも２個のキーが該テーブル探索手段に適
用されるのに応答して、そのパケットに対するマスタＶ
ＣＮを出力する、テーブル探索手段と、を有する、前記
装置。

【０１２０】

【発明の効果】パケットに含まれる、パケットに関連す
る仮想チャネルを特異に識別するチャネル・ラベルを利
用して、ＡＴＭスイッチ内で使用することのできる扱い
易い大きさのチャネル識別タグが得られる。

【図面の簡単な説明】

【図１】ＡＡＬ５結合のための標準ＡＴＭ ＵＮＩセル
の形式を示すブロック図。

【図２】一般的なＡＴＭスイッチのアーキテクチャを示
すブロック図。

【図３】本発明を実施するＡＴＭスイッチの概略を示す
ブロック図。

【図４】図３のスイッチのスイッチ・コア・ブロックを
示すブロック図。

【図５】スイッチ・コア・ポートに関するサービス・ロ
ータのテーブルを示すブロック図。

【図６】図３のスイッチのアダプタ・カードのブロック
図。

【図７】図６のアダプタ・カードの外部スイッチ・ポー
トに関するサービス・ロータのテーブルを示すブロック
図。

【図８】図４のスイッチ・コア・ブロックのコントロー
ラの機能ブロック図。

【図９】図８のコントローラのスケジュール機構によっ
て保持されるポート待ち行列を示すブロック図。

【図１０】図８のコントローラのマスタＶＣＮ探索ブロ
ックのブロック図。

【図１１】図１１ないし２０で全体を構成し、新しい仮
想チャネルを設定するときに、図１０のＶＣＮ探索ブロ
ックによって維持される高位テーブル、低位テーブル、
マスタＶＣＮテーブルの更新を示すブロック図。

【図１２】高位及び低位テーブルのエントリが空である
場合の更新を示すブロック図。

【図１３】高位テーブルのエントリが塞がっていて、低
位テーブルのエントリに空きがある場合の更新を示すブ
ロック図。

【図１４】高位のエントリに空きがあり、低位テーブル
のエントリが塞がっている場合の更新を示すブロック
図。

【図１５】高位／低位テーブルともエントリが塞がって
いる場合の更新を示すブロック図。

【図１６】図１５の例に新しいＶＣＩＤを加えることが
できない例を示すブロック図。

【図１７】テーブルを再整理した後の結果を示すブロッ
ク図。

【図１８】占領エレメントがある行または列のどちらか
を変える例を示すブロック図。

【図１９】占領エレメントを外す必要がある状況を示す
ブロック図。

【図２０】外された占領エレメントがもとに戻った状況
を示すブロック図。

【図２１】図１１ないし２０に示したテーブル更新処理
を示す流れ図。

【符号の説明】

２００ スイッチ・コア ２０１ プロセッサ装置 ２０２ インターフェース回路 ２０３ リンク ２０ Ｎポートのスイッチ・コア ２１ スイッチ・コア・ポート ２２ アダプタ・カード ２３ 外部スイッチ・ポート ２４ プロセッサ装置 ２５ マスタ・クロック ２６ 局所スレーブ・クロック ３０ ファブリック ３１ セル本体共有メモリ ３２ 空きアドレス・リスト・メモリ ３３ コントローラ ３４ 通信ブロック ３７ 入力ポート ３８ 出力ポート ４０ 物理層／フレーム機構（ＰＨＹＳ） ４１ 入力先入先出機構（ＦＩＦＯ） ４２ 入力検出機構 ４３ 出力先入先出機構（ＦＩＦＯ） ４４ 出力検出機構 ４５ 時分割マルチプレクサ ４６ 入力ポート・ロータ機構 ４８ 出力ポート・ロータ機構 ４９ 空セル挿入機構 ５０ 空セル検出・破棄機構 ９２ 高位テーブル ９３ 低位テーブル ９４ マスタＶＣＮテーブル（２次元テーブル）

Claims (1)

【特許請求の範囲】
1. 【請求項１】 少なくとも１つの入力ポートを通して受
   け取られたパケットに関して予定の機能を実行するパケ
   ット処理装置であって、各パケットは、パケットを受け
   取った該装置の入力ポートに対して、該パケットに関連
   する仮想チャネルを特異に識別するチャネル・ラベルを
   持ち、前記装置は、受け取った各パケットについて、該
   パケットに関連する仮想チャネルおよび入力ポートの組
   合せを特異に識別するマスタＶＣＮと称する識別子を提
   供するＶＣＮ提供手段と、前記ＶＣＮ提供手段によって
   提供されたマスタＶＣＮに依存して各パケットに関して
   前記の予定の機能を実行する処理手段と、を備え、前記
   ＶＣＮ提供手段は、 各パケットに対し、パケットを受け取った入力ポートを
   識別するそれぞれのポート・ラベルを生成するポート識
   別手段と、 パケットに関連するチャネル・ラベルおよびポート・ラ
   ベルを結合して出力される長いチャネル識別子を生成す
   る結合手段と、 前記結合手段の出力を予定の方法で分割し、Ｋが２以上
   の整数であるＫ個のキーを提供するキー提供手段と、 前記のＫ個のキーが適用されるテーブル探索手段と、 を有し、前記テーブル探索手段は、 パケットに関連するＫ個のキーの各々を、それぞれ対応
   するより短いインデックスに変換するそれぞれの変換手
   段と、 それぞれのマスタＶＣＮを保持する位置を持つＫ次元の
   マスタ・テーブルであって、対象とするパケットのマス
   タＶＣＮを提供するために、同一パケットから得られた
   Ｋ個のインデックスが、対応するマスタ・テーブルの位
   置をアクセスする役割をするようにした、Ｋ次元マスタ
   ・テーブルと、 を有する、パケット処理装置。