(57)【特許請求の範囲】
【請求項１】
Ｎ個の調停ユニットから構成されたリングを具備した帯域幅制限交換ネットワークへのアクセスを調停する方法であり、前記Ｎ個の調停ユニットからなるリングの各調停ユニットは前記帯域幅制限交換ネットワークのＮ個の入力チャネルの中の１チャネルに対して動作するものであり、前記Ｎ個の調停ユニットから構成されるリングは、調停サイクルにおいて、前記帯域幅制限交換ネットワークを構成するＭ個の出力チャネルの内の幾つかへのアクセスを調停する調停方法であって、
前記調停サイクルの開始前に前記Ｎ個の調停ユニットの各ユニットへ制御データを送信するステップであり、該制御データは前記調停サイクルの時に前記帯域幅制限交換ネットワークの前記Ｍ個の出力チャネルの内の幾つかへのアクセスを調停するかどうかを表している制御データ送信ステップと、
第１回目の調停処理において前記帯域幅制限交換ネットワークの帯域幅を最大Ｂの帯域に制限するステップであって、前記第１回目の調停処理は、交換サイクル時に前記帯域幅制限交換ネットワークが最大でＢ個（ＢはＭ未満の整数）のデータパケットを前記Ｎ個の入力チャネルの内から選択されたチャネルから前記Ｍ個の出力チャネルの内の１つへ送信することを確実にする帯域幅制限ステップとから構成されることを特徴とするアクセス調停方法。
【請求項２】
前記帯域幅制限ネットワークのＭ個の出力チャネルの各々が前記交換サイクル中に前記Ｎ個の入力チャネルの内の選択されたものから受信するデータパケットの個数を第２回目の調停処理において最大Ｋ個（Ｋは１以上の整数）に制限するステップをさらに具備していることを特徴とする請求項１に記載のアクセス調停方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般的には通信ネットワークに関するものであり、特に、各交換周期において入力ポートと出力ポートとの間の一対一のマッピングをサポートするための帯域幅が不十分な交換ネットワークを用いて非同期転送モード(ATM) 交換機（スイッチ）を動作させるための予約リング(reservation ring)に関するものである。
【０００２】
【従来の技術】
ATM ネットワークが一般的となりオフィスネットワークとして使用されるようになるにつれ、小型スケーラブル（規模の変更可能な）交換への要望が大きくなってきた。オフィス環境では、こうした小型スケーラブル交換機を「ATM 拡張コード (ATM extension cords)」として使用することにより一つの物理的接続でオフィス機器をより大型の中央側の交換機へ接続することが可能になる。こうした使用では、中央交換機が要求するスループットレベルに必ずしも小型スケーラブル交換機がサポートする必要はない。このため、小型スケーラブル交換機のアーキテクチャは制限された交換帯域幅内で効率よく動作するように構成するのが望ましい。帯域制限交換ネットワーク(limited bandwidth switching networks)で動作する小型スケーラブル交換機には複数の出力ポートがセットとして設けられており、交換ネットワークは、交換周期毎に限られた数のセルを出力ポートに転送できる。一般に、交換帯域幅の制限された交換機は、入力ポートが論理動作どおり動作できる総合最大リンク速度(aggregate maximum link rate) よりも低いスループットで動作する。
【０００３】
制限された帯域幅で動作する交換機は、一回の交換周期中に全ての入力及び出力ポートを可能性のある全ての一対一入出力ポート間マッピングを発生できないため、「閉塞状態(blocking)」になる可能性がある。この閉塞状態を起こす交換機では、セルが失われないようにするため入力をバッファー処理する必要がある。出力バッファー処理が行われている場合でも、入力バッファー処理を行うほうが望ましい。例えば、一交換周期内に特定の出力バッファー向けの最大数のセルを出力バッファーで待機させることができない時は、入力をバッファー処理する必要がある。米国特許第5,305,311 号に述べられているように、入力バッファー処理と出力バッファー処理の組合せは、損失のない交換を行うのに必要な出力バッファーの帯域幅を制限する効果的な方法である。
【０００４】
【発明が解決しようとする課題】
しかしながら、入力を待機させて一交換周期毎に出力ポートへ１個のセルを出力させる交換機では、待機行列の先頭のブロッキングが生じる問題があることが知られている。一般に、待機行列の先頭のブロッキングはスループットの著しい低下を引き起こす。米国特許第5,305,311 号には、交換周期毎に各出力ポートの速度をｋ（例えば、ｋ＝２）倍にして待機行列の先頭のブロッキングを最小化する方法が開示されている。出力ポート毎にその速度をｋ倍に増加させることにより、ｋ＝１（単に入力を待機させた時）ではスループットは約５８％であったものを、ｋ＝２では約８９％、さらにｋ＝４以上では略１００％にまで増加できる。
【０００５】
【課題を解決するための手段】
従って、本発明はＮ個の調停ユニットからなるリングを用いて帯域幅制限交換ネットワークへのアクセスを調停する方法を提供するものである。Ｎ個の調停ユニットで構成されたリングにおいて、各調停ユニットは帯域幅制限交換ネットワークが有するＮ個の入力チャネルの１チャネルとして機能する。Ｎ個の調停ユニットで構成されたリングは、調停周期中に帯域幅制限交換ネットワークのＭ個の出力チャネルの中の或るチャネルへのアクセスを調停するものである。調停サイクルを開始する前にＮ個の調停ユニットの其々に制御データが出力される。この制御データは、調停周期中に帯域幅制限交換ネットワークのＭ個の出力チャネルの中の或るチャネルへのアクセスを調停すべきかどうかを指示する。１回の調停処理(a round of arbitration)の間に、帯域幅制限交換ネットワークの帯域幅は最大Ｂ個に制限される。調停処理の結果、帯域幅制限交換ネットワークにおいては、交換サイクルの間、Ｎ個の入力チャネルの中から選択された入力チャネルからＢ個（ＢはＭ未満の整数）以下のデータパケットがＭ個の出力チャネルの中の１チャネルへと転送されることになる。
【０００６】
本発明の請求項１の態様では、Ｎ個の調停ユニットから構成されたリングを具備した帯域幅制限交換ネットワークへのアクセスを調停する方法であり、前記Ｎ個の調停ユニットからなるリングの各調停ユニットは前記帯域幅制限交換ネットワークのＮ個の入力チャネルの中の１チャネルに対して動作するものであり、前記Ｎ個の調停ユニットから構成されるリングは、調停サイクルにおいて、前記帯域幅制限交換ネットワークを構成するＭ個の出力チャネルの内の幾つかへのアクセスを調停する調停方法であって、前記調停サイクルの開始前に前記Ｎ個の調停ユニットの各ユニットへ制御データを送信するステップであり、該制御データは前記調停サイクルの時に前記帯域幅制限交換ネットワークの前記Ｍ個の出力チャネルの内の幾つかへのアクセスを調停するかどうかを表している制御データ送信ステップと、第１回目の調停処理において前記帯域幅制限交換ネットワークの帯域幅を最大Ｂの帯域に制限するステップであって、前記第１回目の調停処理は、交換サイクル時に前記帯域幅制限交換ネットワークが最大でＢ個（ＢはＭ未満の整数）のデータパケットを前記Ｎ個の入力チャネルの内から選択されたチャネルから前記Ｍ個の出力チャネルの内の１つへ送信することを確実にする帯域幅制限ステップとから構成されることを特徴とする。
【０００７】
本発明の請求項２の態様では、前記帯域幅制限ネットワークのＭ個の出力チャネルの各々が前記交換サイクル中に前記Ｎ個の入力チャネルの内の選択されたものから受信するデータパケットの個数を第２回目の調停処理において最大Ｋ個（Ｋは１以上の整数）に制限するステップをさらに具備していることを特徴とする。
【０００８】
【発明の実施の形態】
以下、本発明の実施の形態を図面を用いて詳細に説明する。
【０００９】
図１はATM(非同期転送モード)交換機５の概略図を示したものである。交換機５は複数のクラスタモジュール８を有しており、このクラスタモジュール８は、ネットワークチャネル１２、１３によりクラスタ間交換ネットワーク１０に接続されている。各クラスタモジュール８には１以上の入出力(I/O）ポート１６が設けられている。交換機５のアーキテクチャはモジュール型でかつ階層構造である。モジュール形式をとっているため、交換機５の規模を変更するのは容易である。一方、階層構造を有しているため、交換帯域幅をポート間で共有させたり、同一クラスタモジュール８のI/O ポート１６へのトラフィックが交換ネットワーク１０上であちこち転送(traverse)されるのを防止できるため交換機５の平均スループットは増加する。クラスタ間交換ネットワーク１０に対するクラスタモジュール８のアクセスは、調停すなわち予約リング１４を使って行われる。予約リング１４は分散型アービタ(distributed arbiter) で、ライン１７で結合された有限状態マシンあるいは調停ユニットの線形シストリックアレイ(systolic array)として構成される。予約リング１４の各調停ユニット１５は直近のユニットに接続されている。予約リング１４のような線形シストリックアレイの利点としては、通信が全て局所的に行われ、アレイが大きくなっても電気的負荷が増えることがない。このため、交換機５の規模を線型的に変更できる。
【００１０】
交換機５はホストプロセッサ２０を備えており、このプロセッサ２０がホストコントロールバス２２を介して通信を行う。各クラスタモジュール８は、クラスタ制御器２４、記憶ユニット２８、ポートインターフェースユニット２７と、少なくとも１個の交換ネットワークインターフェースユニット１９を含む。クラスタ制御器２４はクラスタモジュール８の制御／プライマリーデータパスを提供する。記憶ユニット２８はクラスタ制御器２４の外部に設けられており、セルをバッファー処理のために格納したり、セルのマッピング情報を記憶する。さらに、記憶ユニット２８内のデータ構造には、入力待ち行列、複数の出力待ち行列、ＶＰＩ／ＶＣＩマップ、および空きセル(free cell) のリストなどが含まれる。各クラスタモジュール８のポートインターフェースユニット２７は、複数のポートインターフェース２６を含んでいる。このポートインターフェース２６はいずれもネットワークを介してセルを送受信するためのものである。
【００１１】
各クラスタモジュール８はクラスタ内の通信だけでなく、クラスタ間の通信もサポートしている。クラスタ間通信には、クラスタ間交換ネットワーク１０を用いて異なるクラスタモジュール８に接続されたポート間の交換処理が含まれる。クラスタ間交換ネットワーク１０へのアクセスは、各クラスタモジュール８の交換ネットワークインターフェースユニット１９を介して行われる。交換ネットワークインターフェースユニット１９は、前記調停ユニット１５と交換ネットワークインターフェース１８を含んでいる。各交換ネットワークインターフェース１８は、接続２１を介してクラスタ制御器２４に接続されている。クラスタ間交換ネットワーク１０とこのネットワーク１０の出力チャネル１３の双方に対するアクセスまたは予約(reservation) が調停ユニット１５によって行われるまでは、交換ネットワークインターフェース１８がパケットデータを保持している。
【００１２】
動作中は、交換サイクル中にクラスタ間交換ネットワーク１０を介していずれか１個の出力チャネル１３へ最大Ｋ個（大文字）（ここで、K ≧１）のセルが出力されるよう予約リング１４はスケジュールする。ここで、Ｋ（大文字）はクラスタモジュール８毎の加速係数(speed up factor) であって、（ｐ＊ｋ）に相当する。ここで、ｐはクラスタモジュール８の１個当たりのI/O ポート１６の数を示しており、またｋ（小文字）は交換機内でクラスタ処理を行わない交換機における I/Oポート１６の１個当たりの加速係数である。１個のクラスタモジュール８の中の出力ポート１６では、出力チャネル１３の１個当たりの加速係数Ｋ（大文字）を共有している。
【００１３】
図２は予約リング１４を示している。この予約リング１４は、交換ネットワーク帯域幅や出力チャネル１３と出力ポート１６へのアクセスといったネットワークの共有資源の分散調停(distributed arbitration) を行うものである。予約リング１４は、複数の調停ユニット１５から構成されている。この調停ユニット１５は、調停サイクルにおいて、ネットワーク資源に対するコンテンション（競合）を解消する。例えば、予約リング１４は、クラスタ間交換ネットワーク１０の出力チャネル１３についてのコンテンション（Ｋコンテンションと称す）と、制限された交換ネットワークの帯域幅についてのコンテンション（Ｂコンテンションと称す）を解決する。調停サイクルの開始点では、（複数の）出力チャネル１３へのアクセスに関する調停要求が調停ユニット１５へ出力される。コントローラー５８のような中央クロック機構を利用して、これらの調停要求はライン１７を介して予約リング１４内部をあちこち転送される。集積回路のピン数を減少することが必要とされる実施例では、ライン１７の数を減少させ、予約リング１４の中で調停要求信号を時分割（またはパイプライン処理）する。
【００１４】
調停サイクル中に、調停ユニット１５は、出力ポート１６、出力チャネル１３、交換ネットワーク１０の帯域幅などのネットワーク資源へのアクセスを調停する。調停ユニット１５へ出力された調停要求が調停サイクル中に予約リング１４の内部をシフトされている時に各調停ユニットでは到来する調停要求とそのユニットに常駐している調停要求（resident arbitration request）とを比較する（すなわち、そのユニット自身の調停要求が予約リング内を一巡するようにシフトされる）。調停サイクルの間に、各調停ユニット１５は調停の各段階でこのような比較を行う。もしネットワーク資源に対してコンフリクトが発生していることが判明した場合は、調停ユニット１５ではどちらの調停要求（すなわち、シフトされた要求または常駐要求）がネットワーク資源について高い優先順位を有するかを判断する。多数のネットワーク要求が存在しているため、ネットワーク資源へのアクセスの調停では調停サイクルが終了するまでに調停処理を何回も行う場合がある。調停サイクルが終了するまでに調停処理が１回で済むか、あるいは２回以上必要であるかは、調停中のネットワーク資源間の関係で決まる（すなわち、あるネットワーク資源の調停が相互に依存しているか、あるいは別の資源の調停とは無関係であるかによる）。
【００１５】
ネットワーク資源の各資源に対する調停処理が残りのその他のネットワーク資源とは無関係に実行されるときは、常に１回の調停処理中に複数のネットワーク資源への調停が並行して行ってもよい。例えば、クラスタモジュール８の各出力ポート１６が受信できる最大セル数（つまり、ｋ＿alloc ）の総計が、クラスタモジュール８が受信できるセル数（Ｋ）にすぎない（すなわち、ｋ＿alloc の合計がＫと等しい）場合は、出力ポート１６と出力チャネル１３へのアクセスの調停は個別に実行される。この場合、１回の調停処理（すなわち、予約リング１４を一順する間に）調停を並行して実行できる。上記の例では、調停ユニット１５が調停を要求している（複数の）出力ポート１６と（複数の）出力チャネル１３の両方の調停に成功した時に、交換ネットワークへのアクセスが許可される。
【００１６】
しかしながら、クラスタモジュール８の各出力ポート１６が受信できるセル数の総計がクラスタモジュール８が受信できるセル数以上の（すなわち、ｋ＿allocsの合計がＫよりも大きい）時は、複数のネットワーク資源に対する複数の調停要求は個別には実行されない。これらのネットワーク資源に関する相互依存調停処理を実行することにより、更に多くのネットワーク資源が利用されることになる。例えば、調停ユニット１５が出力チャネル１３へのアクセスだけを調停し、出力ポート１６へのアクセスを得た場合はネットワーク資源の利用が向上する。同様に、交換ネットワーク帯域幅が制限されている場合は、調停ユニット１５が交換ネットワーク帯域幅への調停だけを調停し、出力ポート１６と出力チャネル１３の両方へのアクセスを得たならばネットワーク資源の利用がさらに向上する。
【００１７】
ネットワーク資源に対して相互依存調停を実行する場合は、予約リング１４を複数回巡回するように調停要求をシフトすることにより最大交換スループットを得ることができる。調停要求が予約リング１４を１回巡回する間、調停ユニット１５は調停要求がネットワーク資源に対して高い優先順位を有しているか否かを判定する。調停処理に失敗した調停処理ユニット１５はその後、自ユニットを調停処理から除く（すなわち、調停処理で調停に失敗した調停ユニット１５はその後の調停処理では要求を出力しない）。
【００１８】
ネットワーク資源への相互依存調停の例を説明する。出力ポート１６と出力チャネル１３へのアクセスは並行して行うことができ（すなわち、クラスタモジュール８の各ポート１６に関するk ＿allocsの合計がＫにすぎない）、また交換機５の交換ネットワーク１０の帯域幅が制限されていると仮定する。出力チャネル１３へのアクセスの調停は、１以上の調停サイクルで行われる。各調停サイクルは２回の調停処理から成る。第１回目の調停処理で出力チャネル１３へのコンテンションが解消され、第２回目の調停処理でクラスタ間交換ネットワーク帯域幅コンテンションが解消される。さらに、１以上の交換サイクルで各調停サイクルが実行できる。バスフレームの期間に１以上のバススロットを調停することにより、予約リング１４での調停に利用できる時間が増加する。
【００１９】
米国特許第5,519,698 号（Lyles et. al.,）の教示によれば、予約リング１４は有限状態マシンまたは調停ユニット１５の線形シストリック(systolic)アレイから構成されている。この調停ユニットはそれぞれ直近の調停ユニットとのみに通信する。処理としては、交換サイクルで１個の出力チャネル１３へ最大でＫ個のセルが出力され、また交換サイクルの間に最大でＢ個のセルが交換ネットワークへ入力されるように予約リング１４でクラスタ間交換ネットワーク１０へのアクセスを要求するセルのためにスケジューリングを行う。各調停ユニット１５のＫの値は、出力チャネル１３の全体に対して一定に設定することもできるし、あるいは、出力チャネル１３毎に変えて設定することもできる。同様に、何らかの一対一対のマッピングを転送する交換機の能力(the ability of the switch to route any one-to-one mappings)  を制限する複数の交換資源が存在する場合は、各資源のＫ値は共通の値または異なる値をとる場合がある。クラスタモジュール８はいずれも有限状態マシンまたは調停ユニット１５を含む、このモジュールは記憶ユニット２８内の入力待ち行列先頭のセルが、クラスタ間交換ネットワーク１０の次の交換サイクル中に送信すべきかどうかを判断する。すなわち、予約リング１４の各調停ユニット１５は、送信準備ができているクラスタモジュール８に関連する最も優先順位の高いセルを調べ、より優先順位の高いセルを入力待ち行列の先頭に有するクラスタモジュール８が他に幾つあるかを判断する有限状態マシンである。
【００２０】
各調停ユニット１５の状態情報は内部レジスタ７３に記憶される。各調停ユニット１５へ転送される情報はインターフェースシフトレジスタ７４に格納される。予約リング１４にｍ個の調停ユニット１５が設けられていると仮定すると、予約リング１４内を１回循環する各調停ユニット１５の状態情報は、調停処理中にｍ回シフトされる。一つの調停サイクルは１回以上の調停処理から成る。本願明細書では、１回の調停処理でｍ回シフトされる場合の各シフトを「調停ステージ(arbitration stage) 」と称する。インターフェースシフトレジスタ７４に記憶されている状態情報は、各調停ユニット１５の内部に記憶されている「R(すなわち、常駐）-Destination Vector 」を有しており、また特定のセルの所望の宛先出力ポート１６を示す情報も有している。一つの実施の形態においては、常駐宛先ベクトル内の可能性のある出力ポート１６をビットアレーを用いて示す。１個のセルを１以上の出力ポート１６へ多重出力(multicast) する場合は、その宛先ベクトル内の１以上のビットを設定する。他の実施の形態においては、予め設定したビット列(sequences of bits) を用いて出力チャネル１３の特定のグループを定義することができる。この場合、各宛先ベクトルは、１以上の出力ポート16を示すよう予め設定されたビット列から構成されている。調停サイクルの開始時点では、予約リング１４上の各調停ユニット１５の前記「R-destination vector」がその「S(すなわち、シフト)-Destination Vector」へ複写される。これら「S-Destination Vector」は、調停処理中に調停リング１４の内部でシフトされる。
【００２１】
インターフェースシフトレジスタ７４と内部レジスタ７３にはそれぞれ「有効(valid) 」ビットを含んでいる。この「有効」ビットは、所定の調停サイクル中の調停要求が有効であるかどうかを示すものである。また、各インターフェースレジスタ７４には調停するセルの優先順位を示す情報が格納されている。セルの優先権は、固有(intrinsic) のものであると同時に外的(extrinsic) なものでもある。固有優先順位とはセルに関連する優先順位（例えば、セルが多重出力セルであるかどうか、または予約済みトラフィックであるかそうでないか）である。外的優先順位とは、調停リング１４で生成された順位（例えば、トークンまたは「Ｔ」ビット）である。このセルの優先順位情報の一部は内部レジスタ７３に複写される。これらの優先順位ビットを用いてある調停ユニット１５が別の調停ユニット１５に対して調停処理を行う権利を獲得したか否かを判断する。要するに、「トークン」または「Ｔ」ビットはタイ・ブレーキング・ビット(tie-breaking bit)であって、別の調停ユニット１５がより高い優先順位を持っているかどうかを示すものである。「MCast 」ビットは、セルが多重出力(multicast) されるのか単一出力(unicast) されるかを示している。また、「Rsv 」ビットは、セルが予約済みトラフィックであるかそうでないかを示している。さらに、「in＿session 」ビットは前回の調停サイクルでセルがブロック(blocked) されたかどうかを示す。
【００２２】
図３は、調停ユニット１５の制御状態７６を詳細に示したものである。動作中においては、調停ユニット１５が調停の時に各内部レジスタ７３に格納されている制御状態７６にアクセスする。調停サイクルで各調停ユニット１５が実行するステップは図４〜７に示されており、以下にこれを説明する。一般に、制御ユニット１５は制御状態７６を使用して「調停セッション(arbitrary session) 」中に状態情報を記録する。この調停セッションには幾つかの調停サイクルが含まれる場合がある。調停セッションの長さは、セルが１以上の所望の出力チャネル１３へアクセスを行うのに成功したかどうかで決まる。以下の説明からも分かるように、所定の調停セッション中に同じ出力先へ割り当てられたセルは、前記所定セッションに参加した全てのセルがそれらの共通の宛先へ転送されるまでは、後から到着するセルに対して閉鎖グループ(closed set)を形成する。他の実施の形態においては、この要件は緩和されており、前記閉鎖グループのセルでなくとも前記所定セッションに参加できる。この場合、前回の調停セッションに干渉しなければ、その後の新規の調停セッションの調停要求も参加する。このようにセッション要件が緩和された調停リングの詳細が米国特許第5,305,311 号に開示されている。
【００２３】
図４は調停セッション中に調停ユニット１５が実行する一般的なステップを図示したフローチャートである。クラスタモジュール８は、調停要求をその調停ユニット１５へ送信して調停セッションを開始または調停セッションに参加する。調停要求はデータパケットまたはセルの送信先を特定し、データパケットの優先順位を示す。例えば、多重送信セルの場合は１以上の出力チャネル１３へアクセスする必要が生じる場合もあるため、調停要求を満足させるために調停セッションが１以上の調停「サイクル」を要する場合もある。調停サイクルの終わりに、次の交換サイクルに備えてクラスタ間交換ネットワーク１０の特定の入力チャネル１２から特定の出力チャネル１３へセルを転送するよう定める。すでに説明したように、各調停「サイクル」は２回の調停処理から構成されている。各調停処理では、クラスタモジュール（または入力チャネル１２）からの調停要求は予約リング１４を巡回して伝搬する。第１回目の調停処理では、入力チャネル１２間での出力チャネル１３についてのコンテンションを調停する。第２回目の調停処理では、入力チャネル１２間での交換ファブリック(switching fabric)の帯域幅「Ｂ」についてのコンテンションを調停する。すでに説明したように、各調停処理では、調停要求は予約リング１４の中を各調停ユニット１５へシフトされる。この各シフトを調停処理の「ステージ」と定義する。
【００２４】
調停サイクルでは、予約リング１４を構成している調停ユニット１５がクラスタ間交換ネットワーク１０へのアクセスを調停する。「調停セッション」は宛先と対応付けられており、次の調停サイクルまで調停セッションが延長されるような場合は調停セッションはアクティブのままになっている。関連する宛先のチャネル１３へのアクセスの調停を調停ユニット１５が失敗した時は調停セッションが延長される。調停セッションを延長される場合には、新たな調停要求はセッションに参加できない。また、このセッションで処理されている調停要求は、同セッションに関連する宛先に対して後から出された調停要求よりも優先する。このように、調停セッションがアクティブの時は、調停ユニット１５は前回ブロックされた要求または新たな要求を再送信できる。しかしながら、現在有効なセッションに対応する宛先に関しては何れの調停ユニット１５も関連する宛先についての新たな調停セッションを開始できない。何故なら、新しい要求が調停に勝つ以前に該セッションの一部の要求が満足されているためである。調停セッションを用いてセルが無期限にブロックされるのを防ぐ方法はすでに周知であり、その詳細は米国特許第5,519,698 号に開示されている。
【００２５】
予約リング１４に設けられている調停ユニット１５の状態変数は立上げの時にステップ１０１でリセットされる。すなわち、内部レジスタ７３とインターフェースシフトレジスタ７４の内の全ての変数がクリアされる。例えば、制御状態７６に格納されている「my＿in＿session 」変数は「FALSE 」にリセットされる。次に、ステップ１０２では要求ライン７８を経て調停要求が調停ユニット１５へ入力される。ＴＲＵＥに設定された「有効」ビット付き調停要求は、調停ユニット１５には転送のためネットワークへ出力するセルがあることを示している。ステップ１０４では、調停ユニット１５の制御状態７６に格納されている状態情報が新しい調停「サイクル」の開始時点でリセットされる。制御状態７６に格納されている状態情報の詳細を図３に示す。
【００２６】
調停セッションで１以上の出力チャネル１３へのアクセスを調停するには、調停サイクルの各処理に調停ユニット１５が参加する必要がある。第１回目の調停処理において、交換ネットワーク１０の１以上の出力チャネル１３とクラスタモジュール８の１以上の出力ポート１６へのアクセスをステップ１０６において調停ユニット１５が調停する。引き続く交換サイクルでは、交換ネットワーク１０の各出力チャネル１３へ入力できるセルの最大数はＫ個に制限される。同時に、各出力ポート１６に入力できるセルの最大数も「k ＿alloc 」個に制限される。出力チャネル１３の１チャネル当たりの入力数を「Ｋ」個に制限し、出力ポート１６へのセル入力数を「k＿alloc」に制限する方法は後で詳細に説明する。調停ユニット１５の調停要求はステップ１０８で隣接する調停ユニットにシフトされ、第１回目の調停処理の各ステージ完了するまでステップ１０６の処理が繰り返される。第２回目の調停処理では、クラスタ間交換ネットワーク１０の帯域幅をステップ１１０で各調停ユニット１５が調停する。交換ネットワーク１０で利用できる全帯域幅を「Ｂ」に制限する。ここで、「Ｂ」はポート１６の総リンク速度未満である。第２回目の調停処理の各ステージが完了するまで、ステップ１１２では予約リング１４上の各調停ユニット１５に対してステップ１１０の処理を繰り返し実行する。
【００２７】
ステップ１１４では、処理が要求されている出力チャネル１３に対しての交換帯域幅の調停が成功したかどうかを各調停ユニット１５が判断する。交換ネットワーク１０の次の交換サイクルでセルの交換を行うことが予約できる場合、調停は成功である。ステップ１１６で調停セッションが成功裏に終わったと判断された場合はステップ１０２が繰り返される。そうでない場合は、ステップ１１７を実行する。ステップ１１７では調停要求の全てまたは一部が再発行される。要求されている出力チャネル１３の一部へのアクセスを、交換ネットワーク１０の次の交換サイクルで行うことが許可されると調停要求の一部が再発行される。全てまたは一部が許可された調停要求は、許可ライン７９または８３を経てクラスタチャネル制御ユニット２４または交換ネットワークインターフェース１８に出力される。
【００２８】
図５は図４のフローチャートのステップ１０６と１０８の詳細を示すフローチャートであって、調停ステージにおける交換ネットワーク１０の１以上の出力チャネル１３の調停の様子を示したものである。最初に、ステップ１２０において、各調停ユニット１５はその「S-Destination Vector」を予約リング１４へ転送する。上述のように、この「S-Destination Vector」の各ビットは調停サイクルでどの調停出力チャネルについて調停が行われているかを定義している。また、ステップ１２０では、「カウンタ」変数をゼロにリセットして調停サイクルの第１処理が開始された（すなわち、予約リング１４の第１ステージが開始された）ことを通知する。次のステップ１２２では、予約リング１４からの要求が隣接する調停ユニット１５からインターフェースシフトレジスタ７４（図２）によって受信される。
【００２９】
ステップ１２４では、予約リング１４から入力された調停要求から取り出したタイ・ブレーカー・「トークン」(tie-breaker "token") を調べ、２台の調停ユニットの間に繋がり(tie) がある時は調停要求に優先権を付与できる。各調停ユニット１５は、予約リング１４内を転送されて繋がりを終了させる「トークン」または「Ｔ」ビットを「current ＿ring＿tail」変数と 「nxt＿ring＿tail」変数を用いて更新する。これらの変数は、調停処理の各ステージでの優先順位を定義することにより調停ユニット間でタイ・ブレーキングが公平に行われことを保証する。概念的には、要求されている調停ユニットの順番でリスト状に予約リング１４を分解するものと考える。リストの上位にある調停ユニットには、リストの下位にある調停ユニットよりも高い優先順位が付与される。公正さを高めるため、リストの開始（starting）調停ユニットは定まっているのではなく(not static)、予約リング１４の中を循環しているのである。このため、固定でなく(not static)循環されている優先順位で繋がりを解消することでポート全体での公正さが向上する。例えば、各調停ユニット１５では、予約リング１４に調停要求を出力する前にまずその「トークン」変数を高い優先順位[HIGHER (priority)] に設定する。電源立上げの時こうして指定された調停ユニットをリストの最後尾に割り当てる。リストの最後尾に指定された調停ユニットは、「トークン」変数を予約リング１４へ出力する前に低い優先順位[LOWER (priority)]に設定する。低い優先順位[LOWER (priority)]トークンを受信した調停ユニットは、現在の調停要求よりも低い優先権をシフトされた調停要求に与える。しかしながら、調停ユニットに優先順位の高い[HIGHER (priority)] トークンが入力された時は、常駐調停要求よりも高い優先順位がシフトされた調停要求に割り当てられる。すなわち、調停処理の開始時点で優先順位の低いトークン変数が最初に入力されるリスト中の次位の調停ユニットは、次の調停処理ではリストの次の最後尾となる。
【００３０】
各調停ユニットは、宛先「Ｋ＿counter 」ベクトルをステップ１２６で更新する。このため、各調停ユニット１５では、交換ネットワーク１０の要求出力チャネル１３についてコンテンションが発生しているかどうかを判断しなくてはならない。交換ネットワーク１０の交換サイクルで１つの出力チャネル１３に転送されるセルの数は「dest＿K ＿max 」個に制限されている。調停ステージでは、各調停ユニット１５は「resident(R)-destination vector」と「shifted(S)-destination vector 」を比較して交換ネットワーク１０内の１つの出力チャネル１３に対してコンテンションが発生しているかどうかを判断する。類似した出力チャネル１３に対して２つの調停ユニットの間でコンテンションが発生している場合は、どちらのユニットの優先順位が高いかを判断して優先順位を決める。
【００３１】
すなわち、ステップ１２６では、調停ステージの時に同一出力チャネル１３に対して２台の調停ユニットがコンテンション状態にある時は、優先順位の低い調停ユニットがその宛先K ＿counter ベクトルに含まれている出力チャネルに相当する宛先K ＿counter を増加させる。タイ・ブレーカー・「トークン(T bit) 」、「有効」ビット、「rsv(すなわち、resvered)」トラフィックビット、「mcast（すなわち、multicast)」ビットからなる要素を組み合わせて使用して調停要求の優先順位を決める。この「有効」ビットは、調停要求が現在の調停処理で有効であるかどうかを表している。有効ビットがTRUEに設定されたセルには高い優先順位が付与される。「rsv 」トラフィックビットは、セルが予約済みトラフィックかそうでないかを表している。予約済みトラフィックには高い優先順位が付与される。「mscat 」ビットは、セルが多重出力されるか単一出力されるかを表している。次の交換サイクルで多重出力要求の一部を再送信するよりもセルの出力チャネル１３を全て満足させるほうがより効率的であるため、多重出力に高い優先順位を付与する。
【００３２】
ステップ１２７では、調停ステージにおいて、出力ポート１６について他の調停ユニットとの競合（コンテンション）に失敗した場合は、特定のポートについての宛先「k ＿alloc ＿ct」カウンタを増加させる。各調停ユニット１５の「k ＿alloc ＿ct」ベクトルは、交換機５のポート毎に設けられた「k ＿alloc ＿ct」カウンタを含んでいる。出力チャネルのコンテンションを解消するため用いた優先順位を用いて出力ポート１６についての２台の調停ユニット間のコンテンションも解消される。本発明の実施の形態では、交換機５の出力ポートに転送されるセルの数は、「dest＿k ＿alloc ＿max 」ベクトルに含まれている特定の値に限定されている。従って、「dest＿k ＿alloc ＿max 」個以上のセルが１つの出力ポートで競合する時は、「dest＿k ＿alloc ＿max 」個のセルのみが交換ネットワークについての予約が認められる。各出力ポート１６に対して「k ＿alloc counter 」が定義されておらず、また各出力チャネル１３に対して「K ＿count 」だけが定義されているような実施の形態の場合は、各調停ユニット１５はステップ１２６の処理を行い、ステップ１２７の処理は省略する。
【００３３】
調停ユニット１５についての「session ＿active」変数をステップ１２８で更新する。この「 session＿active」変数は調停ユニットの制御状態７６に格納されていたものであり、交換ネットワーク１０の出力ポート１３について前回の調停セッションがまだアクティブであるかどうかを表している。調停セッションは単一の宛先である出力チャネル１３に関するものであり、該セッションに参加しているセルのそれぞれが単一の宛先である出力チャネル１３に転送されてしまうとそのセッションは終了する。もし出力チャネル１３に対してセッションがまだアクティブである場合は、「in＿session 」ビットがＦＡＬＳＥに設定されている出力チャネル１３について、新規の調停要求が次回の調停セッションまで延期されている。つまり、いずれかの宛先出力チャネル１３への調停セッションが一旦開始されると、そのチャネルに対する別の要求が現在の調停セッションに付加されることはない。このように、調停セッションが完了すると、行列の先頭にあって次の調停セッションに参加する資格のある全ての待ち要求は、次の調停セッションに参加できる。１以上の調停サイクルのセッションで宛先出力チャネル１３について調停を行うことにより、入力チャネルが無期限にブロックされる危険がなくなる。
【００３４】
ステップ１３０では、各調停ユニット１５の制御状態７６に格納されている「カウンタ」変数を調べて、各調停ユニットについての調停要求が予約リング１４を一巡して各調停ユニットへシフトされたかどうかを判断する。各調停要求が予約リング１４を一巡してシフトされると、ステップ１３６の処理が実行される。そうでない場合は、ステップ１３２の処理が実行される。ステップ１３２では、「カウンタ」変数を増加させる。ステップ１３４では、調停ユニットに最後に入力された要求を予約リング１４上へシフトして出力し、ステップ１２２の処理を繰り返す。
【００３５】
各調停ユニット１５の調停要求内容が予約リング１４を一巡してシフトされると、ステップ１３６の処理が実行される。ステップ１３６では、「R-destination vector」に定義されている要求される各宛先出力チャネル１３についての「destination K ＿counter vector」に含まれているK ＿counterが「dest＿K ＿max」を超えているかどうかを予約リング１４の各調停ユニット１５が判断する。この判断は、各調停ユニットの状態制御ロジックに格納されている「destination K ＿counter vector」を用いて行う。他の調停ユニットに対してある調停ユニット１５をステップ１２６において遅延させた回数が「dest＿K＿max」１５を超えず、また他の調停ユニット１５に対してある調停ユニット１５をステップ１２７において遅延させた回数が「dest＿k＿alloc＿max」を超えない場合は、「ok＿to＿send-destinaion vector」 に対応する出力ポート１６を記録する。すなわち、特定の宛先出力チャネル１３に対して「destination K ＿counter vector」の「K＿counter」が超えられることがなく、また特定の宛先ポート１６についての「k ＿alloc ＿ct vector 」の「k ＿alloc ＿ct」が超えられるようなことがない場合にのみ、ビットを「ok＿to＿send-destination vector 」に設定する。第１回目の調停処理後では、「ok＿to＿send-destination vector 」に設定されている各ビットは次の交換サイクルにどの宛先出力チャネル１３がデータパケットを受信するかを表している。「ok＿to＿send-destination vector 」に設定されているこれらのビットは、交換サイクル中の送信セル数の制約、すなわち各宛先出力チャネル１３に最大で「dest＿K ＿max 」個のセルしか送信してはならず、また、宛先出力ポート１６に最大で「k ＿alloc ＿max 」個のセルしか送信してはならないという制約を満足させるためのものである。しかしながら調停サイクルのこの時点では、交換ネットワーク１０の帯域幅制限「Ｂ」を超えているかどうかは「ok＿to＿send-destination vector 」からは分からない。
【００３６】
各クラスタモジュール８について１チャネル当たりの加速係数Ｋ（the speedup of K per channel）と１ポート当たりの加速係数ｋ(the speedup of k per port) を動的に設定する実施の形態では、予約リング１４の各調停ユニット１５は各「dest＿K＿max」または「dest＿k＿alloc＿max max vector」について定義されている値が分からなくてはならない。つまり、ステップ１２６、１２７、１３６の処理を実行する上で、各調停ユニット１５は予約リング１４上の調停ユニット１５の１チャネル当たりの加速係数Ｋと１ポート当たりの加速係数ｋを知る必要がある。上述のように、予約リング１４の各調停ユニットの１チャネル当たりの加速係数Ｋと１ポート当たりの加速係数ｋはいずれもシステムの初期化の時点で動的に設定できる。
【００３７】
図６は図４のフローチャートのステップ１１０と１１２の詳細を示すフローチャートであって、調停ステージにおける交換ネットワーク１０の制限帯域幅「Ｂ」についての調停ユニット１５による調停の様子を示したものである。ステップ１３８では、各調停ユニット１５のカウンタをゼロにリセットして第２回目の調停処理が開始されたことを示す。ステップ１３８では、「non-zero ok ＿to＿send destination vector 」を有した調停ユニット１５がそのバス帯域幅要求を予約リング１４上へシフトして出力する。ステップ１３８で、各調停ユニット１５からその直近の調停ユニット１５へ調停要求を転送する。ステップ１４０では、直近の調停ユニット１５からの調停要求がインターフェースシフトレジスタ７４（図２参照）へ入力される。ステップ１４２では、上記ステップ１２４の場合と同様にタイ・ブレーカー・トークン（the tie-breaker token ）を更新する。
【００３８】
ステップ１４４では、クラスタ間交換ネットワーク１０の帯域幅に対して各調停ユニット１５が競合する。上述のように、クラスタ間交換ネットワーク１０は帯域幅制限交換ネットワークである。従って、交換サイクルでは、交換ネットワーク１０の入力チャネル１２と出力チャネル１３との間に一対一の対応はない。こうした帯域幅の制限は、各調停ユニット１５の制御状態７６に記録されている「B ＿max 」変数を用いて表わされる。また、制御状態７６は、１以上の「B ＿count 」変数と共に「B ＿count vector」を記録する。すなわち、ステップ１４４では、シフトされた調停要求の優先順位が常駐調停要求よりも高い場合には、交換機５の（複数の）交換ネットワークに対応したB ＿count vector」の「B ＿count 」変数の値が増加される。優先順位の決定は、前記ステップ１２６での優先順位の決定と同様に行われる。
【００３９】
ステップ１４６では、「カウンタ」を評価することにより、現在の調停サイクルで行ったバス帯域幅「Ｂ」についての調停要求が予約リングを一巡して予約リング１４上の各調停ユニット１５にシフトされたかどうかを判断する。各インターフェースシフトレジスタ７４が、リングを一巡するシフトに成功した場合は、ステップ１５２の処理を実行する。そうでない場合は、ステップ１４８の処理を実行する。ステップ１４８では、「カウンタ」の値を増加させ、予約リング１４上でさらに調停要求のシフトを行うことを通知する。次に、ステップ１３４では、調停ユニット１５に最も新しく入力された調停要求を予約リング１４へシフトする。ステップ１５２の処理が実行されたことは、バス帯域幅に関する第２番目の調停処理が完了したことを示す。
【００４０】
図７は、図４に示すフローチャートのステップ１１４，１１６，１１７の詳細を示すフローチャートであり、現在の調停サイクルでどの調停ユニット１５が優先順位を獲得したかを判断する。ステップ１５２では、まず最初に、次の交換サイクルの時に交換ネットワーク１０の要求された宛先である少なくとも１個の出力チャネル１３のうち少なくとも１つのチャネルへセルを転送できるかどうかについて第１の判断を下す。各調停ユニットは、ステップ１３６において「ok＿to＿send designation vector 」の中の少なくとも１つのビットが出力ポート１６に対して設定されたかどうかを確認することで前記第１の判断を行う。さらに、「ok＿to＿send designation vector 」に設定されているビットに対応した宛先出力に関連する「B ＿count vector」の「B ＿count 」がB ＿max 未満であるかどうかについて各調停ユニット１５は第２の判断を下す。もし調停ユニット１５のセルが次の交換サイクルの時に送信されるようスケジュールがなされない場合は、ステップ１５８の処理を実行する。そうでない場合は、ステップ１５４の処理を実行する。
【００４１】
ステップ１５４では、第１回目と第２回目のいずれの調停処理においても交換ネットワーク１０についてのアクセスの調停が成功した時は「送信」フラグをTRUEに設定する。調停サイクルの終わりに調停ユニット１５がそのクラスタ制御器２４へ「送信」フラグを送信する。TRUEに設定された送信フラグを受信すると、次の交換サイクルの時にクラスタ制御器２４は４交換ネットワーク１０へセルを送信する準備をする。
【００４２】
ステップ１５６では、調停に成功したセル(successful contender)が共有する交換ネットワーク帯域幅をB ＿count vectorを用いてスケジュールする。調停に成功したセルが共有の交換ネットワーク帯域幅にアクセスする時互いに干渉しなければ、資源は適切に配分される。しかしながら、セルが出力ポートへのアクセスの調停に成功したという表示によって、次の交換サイクルにおいて該出力ポートへそのセルが交換ネットワークを経て転送されるようバススロットがスケジュールされるのではない。
【００４３】
バスを使用した(bus-based) 交換ネットワークでは、競合に勝った調停ユニット１５のそれぞれの「B ＿counter 」を用いてバス帯域幅の時間スロットを割り当てる（上述のように、調停ステージの時に調停ユニット１５が別の調停ユニットに対して遅延される都度「B ＿counter 」を調停サイクルで増加させる）。競合に勝った調停ユニットの「B ＿counter 」の値を調停ユニット１５から出力された時間「スロットベクトル」に記憶させる。すなわち、各カウンタの値は各調停ユニットに固有のものであるため、バスの「B ＿counter 」値を用いて所定セルの時間スロットを特定する。ベクトル内の各B＿count値は各「Bn」について固有であるため、「B ＿counter vector」の値が１以上のカウンタの値を含んでいる時にも上記の原理が当てはまることになる。他の実施の形態では、時分割(time-multiplexed)ではなく空間多重化（space multiplexed ）フレームによる並列ネットワークまたはファブリック形（fabric-based) ネットワークで「B ＿counter 」を用いている。例えば、この実施の形態では、全ての「時間」スロットを使用して独自の転送ネットワーク(unique routing network)を表すことができる。従って、調停サイクルの最後に、「B ＿counter 」を用いて複数の入力ポートに指示を与えて独自の転送ネットワークへセルを出力することが可能である。
【００４４】
ステップ１５８では、各調停ユニット１５は、入力チャネル１２がブロックされて（複数の）出力チャネル１３向けのセルデータを送信できないかどうか判断する。もし何れの宛先入力チャネル１２(destination input channel 12)がブロックされていない場合は、ステップ１０２の処理を行う。一方、ブロックされている場合は、ステップ１６０と１６２の処理を実行する。
【００４５】
ステップ１６０では、調停ユニット１５の「n ＿session 」フラグをTRUEに設定して現在の調停サイクルでは今行っている調停セッションが完了しない旨をクラスタモジュール２４へ通知する。調停ユニット１５は、現在の調停サイクルでは予約が認められなかった（複数の）宛先出力ポートについての調停要求を次の１以上の調停サイクルにおいて再送信しなければならない。調停要求を再送信する際に、セルデータの固有優先権を更新して前回不成功に終わった（複数の）調停サイクルを反映させてもよい。また、「in＿session」 フラグをTRUEに設定して現在の調停セッションを次の調停サイクルまで継続することを通知する。ステップ１６２では、次の調停サイクルの時に再発行しなくてはならない出力ポート要求を用いて宛先ベクトルを更新する。再発行調停要求とは、現在の調停サイクルで調停に成功しなかった要求のことである。これらの要求には、マルチキャストセルの宛先出力チャネル１３のサブセットが含まれている。
【図面の簡単な説明】
【図１】本発明を適用したモジュール式階層ＡＴＭ（非同期転送モード）交換機の概略図である。
【図２】図１のモジュール式階層交換機内で動作する予約リングの概略図である。
【図３】調停ユニットの制御状態を示す概略図である。
【図４】調停セッション中に各調停ユニットが実行する全般的ステップを示したフローチャートである。
【図５】図４の出力チャネルと出力ポートの調停に関するステップ１０６と１０８の詳細を示すフローチャートである。
【図６】図４の交換ファブリック帯域幅の調停に関するステップ１１０と１１２の詳細を示すフローチャートである。
【図７】図４の現在の調停サイクルをどの調停ユニットに割り当てるかを判断する処理に関するステップ１１４、１１６、１１７の詳細を示すフローチャートである。
【図１】
0003936044.tif 000002
【図２】
0003936044.tif 000003
【図３】
0003936044.tif 000004
【図４】
0003936044.tif 000005
【図５】
0003936044.tif 000006
【図６】
0003936044.tif 000007
【図７】
0003936044.tif 000008