(57)【特許請求の範囲】
【請求項１】
通信システムであって、
情報を供給する複数の源と、
上記源からの上記情報を受信する複数の行先と、
上記源を上記行先に接続するネットワークを形成している１つまたはそれ以上のノードと、
を備え、
上記ネットワークは上記情報を輸送するための複数のチャンネルを有し、各チャンネル毎に、
１つまたはそれ以上のノードから順方向経路をリンクすることによって上記複数の源の１つが上記ネットワークを通して上記複数の行先の１つにリンクされ、
上記１つまたはそれ以上のノードから戻し経路をリンクすることによって上記複数の行先の上記１つが上記ネットワークを通して上記複数の源の上記１つにリンクされ、そして
上記１つまたはそれ以上の各ノードは、上記複数の源からの上記情報を待ち行列に入れるためのキューイング手段を含み、上記キューイング手段は、
フルバッファ容量、及び上記フルバッファ容量より小さいか、または等しい使用されているバッファ容量を有するバッファメモリを含み、上記各源は上記バッファメモリの使用されている容量の一部分である割振り済みの源バッファ容量を有し、
上記各源の上記源バッファの利用率、及び上記バッファメモリの使用されているバッファ容量の合計を指示する指示器手段と、
各特定の源毎に、上記フル容量に対する上記バッファメモリの上記使用されているバッファ容量の関数として、及び上記特定の源のための上記使用されている源バッファ容量の関数として、上記各源毎の上記バッファメモリ内の上記使用されている源バッファ容量のために割振り済みの源バッファ容量を割振る動的割振り手段と、
を更に含む、
ことを特徴とする通信システム。
【請求項２】
上記各ノードは、上記使用されている源バッファ容量が上記特定の源のための上記割振り済みの源バッファ容量を超えると、上記特定の源から情報を破棄する破棄手段を含むことを特徴とする請求項１に記載の通信システム。
【請求項３】
上記各源は源サービス分類を有し、上記動的割振り手段は上記サービス分類に応答して機能することを特徴とする請求項１に記載の通信システム。
【請求項４】
上記各ノードは、上記使用されている源バッファ容量が上記特定の源のための上記割振り済みの源バッファ容量を超えると、上記特定の源から情報を破棄する破棄手段を含むことを特徴とする請求項１に記載の通信システム。
【請求項５】
上記各源及び上記各ノードは、上記源と上記行先を接続する仮想チャンネルを用いてＡＴＭネットワークを形成しており、上記情報はパケット化されたセルで伝送されることを特徴とする請求項１に記載の通信システム。
【請求項６】
反応的な輻輳制御を有する通信システムであって、
複数の源を備え、上記源は輻輳信号に応答して順方向情報信号を異なる伝送レートで伝送する変更可能な送出レートユニットを含み、上記送出レートユニットは輻輳信号に応答して伝送レートを減少させ、
複数の行先と、
上記源と上記行先とを接続する非同期転送モード（ＡＴＭ）ネットワークを形成する１つまたはそれ以上のノードと、
を更に備え、上記各ノードは、
上記ネットワークを通して情報を順方向に行先に向けて転送する順方向経路と、
上記ネットワークを通して輻輳信号を逆方向に源に向けて戻す戻し経路と、
上記複数の源からの上記情報を待ち行列に入れるキューイング手段と、
を含み、上記キューイング手段は、
フルバッファ容量、及び上記フルバッファ容量より小さいか、または等しい使用されているメモリ容量を有するバッファメモリを含み、上記各源は上記バッファメモリの使用されている容量の一部分である使用されている源バッファ容量を有し、
上記各源の上記源バッファの利用率、及び上記バッファメモリ使用されている容量の合計を指示する指示器手段と、
各特定の源毎に、上記メモリ容量に対する上記バッファメモリの上記使用されている源バッファ容量の関数として、及び上記特定の源のための上記使用されている源バッファ容量の関数として、上記各源のための上記バッファメモリ内の上記使用されている源バッファ容量のために割振り済みの源バッファ容量を割振る動的割振り手段と、
上記ノードにおける輻輳に応答し、上記フルメモリ容量に対する上記バッファメモリの上記使用されているメモリ容量の関数として、及び上記特定の源のための上記使用されている源バッファ容量の関数として、上記特定の源のための輻輳信号を生成する輻輳信号生成手段と、
を更に含み、
上記ネットワークは、複数の仮想チャンネルを有し、各仮想チャンネル毎に、
１つまたはそれ以上のローカルノードから順方向経路をリンクすることによって上記複数のローカル源の１つが上記ネットワークを通して上記複数のローカル行先の１つにリンクされ、上記送出レートユニットは上記仮想チャンネルからの輻輳信号に応答して順方向情報信号を異なる伝送レートで伝送し、
上記１つまたはそれ以上のノードから戻し経路をリンクすることによって上記複数の行先の上記１つが上記ネットワークを通して上記複数の源の上記１つにリンクされ、
上記ノードの１つ内の上記輻輳信号生成手段は、上記ノードの上記１つにおける輻輳に応答して上記仮想チャンネルのための上記輻輳信号を生成する
ことを特徴とする通信システム。
【請求項７】
上記送出レートは、上記輻輳信号の欠如に応答して上記伝送レートを増加させることを特徴とする請求項６に記載の通信システム。
【請求項８】
輻輳したノードから上記源へ戻される輻輳信号のための伝送間隔は、上記仮想チャンネルを介して伝送される情報信号間の間隔より小さく、それによって上記送出レートユニットは反応的に応答して上記伝送レートを変更し、輻輳を減少させることを特徴とする請求項６に記載の通信システム。
【請求項９】
ローカル反応及び予測輻輳制御の両成分を有する広域通信システムであって、
複数のローカル通信システムを備え、上記各ローカル通信システムは、
複数のローカル源を含み、上記各ローカル源は順方向情報信号を異なる伝送レートで伝送する変更可能な送出レートユニットを含み、上記送出レートユニットは輻輳信号の存在に応答して上記伝送レートを減少させ、輻輳信号の欠如に応答して上記伝送レートを増加させ、
複数のローカル行先と、
上記源を上記行先に接続する非同期転送モード（ＡＴＭ）ローカルネットワークを形成する１つまたはそれ以上のノードと、
を更に含み、上記各ローカルノードは、
上記ネットワークを通して情報を順方向に行先に向けて異なる選択可能な伝送レートで転送する順方向経路と、
上記ネットワークを通して輻輳信号を逆方向に源に向けて戻す戻し経路と、
上記ローカルノードにおける輻輳に応答して輻輳信号に関する要求を生成する輻輳信号生成手段と、
上記要求を濾波し、上記輻輳信号を応答的に供給するフィルタ手段と、
を含み、
上記ネットワークは、複数の仮想チャンネルを有し、各仮想チャンネル毎に、
１つまたはそれ以上のローカルノードから順方向経路をリンクすることによって上記複数のローカル源の１つが上記ローカルネットワークを通して上記複数のローカル行先の１つにリンクされ、上記送出レートユニットは上記仮想チャンネルを介する輻輳信号に応答して順方向情報信号を異なる伝送レートで伝送し、
上記１つまたはそれ以上のノードから戻し経路をリンクすることによって上記複数のローカル行先の上記１つが上記ネットワークを通して上記複数のローカル源の上記１つにリンクされ、
上記ローカルノードの１つ内の上記輻輳信号生成手段は、上記ローカルノードの上記１つにおける輻輳に応答して上記仮想チャンネルのための上記輻輳信号に関する上記要求を生成し、
１つまたはそれ以上の広域源が上記ローカルネットワークの１つに接続され、
１つまたはそれ以上の広域行先が上記ローカルネットワークの別の１つに接続され、
複数の仮想チャンネルは、各仮想チャンネル毎に、上記複数の広域源の１つが上記ローカルネットワーク及び上記ローカルネットワークリンクを通して上記複数の広域行先の１つにリンクされている、
ことを特徴とする広域通信システム。
【請求項１０】
ローカル反応及び予測輻輳制御の両成分を有する広域通信システムであって、
複数のローカル通信システムを備え、上記各ローカル通信システムは、
複数のローカル源を含み、上記各ローカル源は順方向情報信号を異なる伝送レートで伝送する変更可能な送出レートユニットを含み、上記送出レートユニットは輻輳信号の存在に応答して上記伝送レートを減少させ、輻輳信号の欠如に応答して上記伝送レートを増加させ、
複数のローカル行先と、
上記源を上記行先に接続する非同期転送モード（ＡＴＭ）ローカルネットワークを形成する１つまたはそれ以上のノードと、
を更に含み、上記各ローカルノードは、
上記ネットワークを通して情報を順方向に行先に向けて異なる選択可能な伝送レートで転送する順方向経路と、
上記ネットワークを通して輻輳信号を逆方向に源に向けて戻す戻し経路と、
上記複数の源からの上記情報を待ち行列に入れるキューイング手段と、
を含み、上記キューイング手段は、
フルメモリ容量、及び上記フルメモリ容量より小さいか、または等しい使用されているメモリ容量を有するバッファメモリを含み、上記各源は上記バッファメモリの使用されている容量の一部分である使用されている源容量を有し、
上記各源の上記源のために使用されている源容量、及び上記バッファメモリの使用されているメモリ容量を指示する指示器手段と、
各特定の源毎に、上記フルメモリ容量に対する上記バッファメモリの上記使用されている源バッファ容量の関数として、及び上記特定の源のための上記使用されている源容量の関数として、上記各源のための上記バッファメモリ内の上記使用されている源容量のために割振り済みの源容量を割振る動的割振り手段と、
上記ノードにおける輻輳に応答し、上記フルメモリ容量に対する上記バッファメモリの上記使用されているメモリ容量の関数として、及び上記特定の源のための上記使用されている源容量の関数として、上記特定の源のための輻輳信号に関する要求を生成する輻輳信号生成手段と、
上記要求を濾波し、上記輻輳信号を応答的に供給するフィルタ手段と、
を含み、
上記ネットワークは、複数の仮想チャンネルを有し、各仮想チャンネル毎に、
１つまたはそれ以上のローカルノードから順方向経路をリンクすることによって上記複数のローカル源の１つが上記ローカルネットワークを通して上記複数のローカル行先の１つにリンクされ、上記送出レートユニットは上記仮想チャンネルを介する輻輳信号に応答して情報信号を順方向に異なる伝送レートで伝送し、
上記１つまたはそれ以上のノードから戻し経路をリンクすることによって上記複数のローカル行先の上記１つが上記ネットワークを通して上記複数のローカル源の上記１つにリンクされ、
上記ローカルノードの１つ内の上記輻輳信号生成手段は、上記ローカルノードの上記１つにおける輻輳に応答して上記仮想チャンネルのための上記輻輳信号に関する上記要求を生成し、
１つまたはそれ以上の広域源が上記ローカルネットワークの１つに接続され、
１つまたはそれ以上の広域行先が上記ローカルネットワークの別の１つに接続され、
複数のローカルネットワークリンクが２つまたはそれ以上のローカルネットワークを相互接続して広域ネットワークを形成し、上記広域ネットワークは複数の仮想チャンネルを有し、各仮想チャンネル毎に、上記複数の広域源の１つが上記ローカルネットワーク及び上記ローカルネットワークリンクを介して上記複数のローカルネットワークを通して上記複数の広域行先の１つにリンクされている
ことを特徴とする広域通信システム。
【請求項１１】
輻輳したローカルノードから上記ローカル源へ戻される輻輳信号のための伝送間隔は短く、それによって上記送出レートユニットは上記伝送レートを反応的に変更することができ、それによって上記広域通信システム内の輻輳を減少させることを特徴とする請求項１０に記載の広域通信システム。
【請求項１２】
輻輳したローカルノードから上記ローカル源へ戻される輻輳信号のための伝送間隔は、上記仮想チャンネルを介して伝送される情報信号間の間隔より小さく、それによって上記送出レートユニットは反応的に応答して上記伝送レートを変更し、上記広域通信システム内の輻輳を減少させることを特徴とする請求項１０に記載の広域通信システム。
【請求項１３】
輻輳したローカルノードから上記ローカル源へ戻される輻輳信号のための伝送間隔は、上記仮想チャンネルを介して伝送される情報信号間の10間隔より小さく、それによって上記送出レートユニットは反応的に応答して上記伝送レートを変更し、上記広域通信システム内の輻輳を減少させることを特徴とする請求項１０に記載の広域通信システム。
【請求項１４】
各ノードにおいて輻輳信号を生成するために要する処理時間は、輻輳信号のための上記伝送間隔よりも遙かに小さいことを特徴とする請求項１０に記載の広域通信システム。
【請求項１５】
上記送出レートユニットは、上記伝送レートを減少させた後に、輻輳信号の欠如に応答して上記伝送レートを増加させる手段を有し、上記増加は上記伝送レートと共に変化し、低めの伝送レートにおいては高めの伝送レートにおけるより速く増加することを特徴とする請求項１０に記載の広域通信システム。
【請求項１６】
上記順方向への情報はセルに断片化され、各セルは仮想チャンネル識別子を含み、各ノードはスイッチング要素を含み、各スイッチング要素は、
スイッチファブリックと、
上記スイッチファブリックによって相互接続されている複数のポートコントローラと、
を含み、上記各ポートコントローラは、
入力コントローラと、
出力コントローラと、
上記ノードにおける輻輳を検出する輻輳検出手段と、
仮想チャンネル識別子を有するセルを上記順方向経路から上記戻し経路へコピーし、それによって輻輳信号を生成する反転手段と、
を含む、
ことを特徴とする請求項１４に記載の広域通信システム。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、一般的には複数の源（出所、またはソース）からの情報をバッファする情報転送システムに関し、特定的には共用バッファプールにおいて、そのバッファプールの利用率及び各個々の源の推定される賦課ロードの両方に依存して各源にバッファサイズを動的に割振る共用バッファアーキテクチャに関する。
【０００２】
（従来の技術）
一般的に、ネットワーク通信システムは、ネットワーク内の多くのユーザを相互接続する。各ユーザは、ポートにおいてネットワークに接続される。ネットワークは多くのノードの相互接続によって形成され、源の１ユーザからの入力ポートへの情報入力はネットワークを通してノードからノードへ、出力ポートへ、そして行先（デスティネーション）の別のユーザへ渡される。源から行先へ転送される情報はパケット化され、各ノードは入力ポートにおける入力パケットを出力ポートにおける出力パケットにスイッチする。ＡＴＭ（非同期転送モード）ネットワークの場合には、パケットは更にセルに分割される。
【０００３】
現在の技術では、高速パケットスイッチは、各スイッチポートにおいて毎秒数十万パケットを転送する。各スイッチポートは、広帯域統合サービスデジタル回路網（ＩＳＤＮ）の場合、典型的には50Ｍビット／秒から2.4Ｇビット／秒のレートで情報を転送するように設計されている。スイッチサイズは、数ポートから数千ポートまでの範囲である。
【０００４】
“高速パケットスイッチ”なる用語は、可変長パケット及び固定長パケットの両方を取扱うことができるスイッチを含む。固定長パケットの使用は、スイッチ設計を簡易化することができる。短い固定長パケット（セル）を使用する高速パケットスイッチを、ＡＴＭスイッチと呼ぶ。高速パケットスイッチは、単一の統合回路網内で異なる型の通信サービスを取扱う。これらのサービスは、音声、ビデオ、及びデータ通信を含むことができる。ネットワークを通して伝送される音声及びビデオサービスが許容できる遅延及び遅延変動は制限されるから、ＡＴＭスイッチはこれらのサービスに適している。広帯域ＩＳＤＮのためのＡＴＭ標準は、５バイトのヘッダー及び48バイトのデータの53バイトの長さを有するセルを定義している。ＡＴＭフォーラムトラフィック管理仕様は、以下のような多くのサービスクラス定義を指定している。
ＣＢＲ：連続ビットレート。音声及びビデオのような厳密に制約された遅延及び遅延変動を要求する実時間応用のために。ＣＢＲサービスクラスは、一貫して使用可能な固定された量の帯域幅を要求する。
ＲＴ−ＶＢＲ：実時間可変ビットレート。源が、時間に伴って変化するレートで伝送し（当分野においては“バースティ”という）、しかも厳密に制約された遅延及び遅延変動で受信しなければならないような応用用。
ＮＲＴ−ＶＢＲ：非実時間可変ビットレート。遅延またはその変動に関してのサービスは要求しないが、損失に対して感応性を有するバースティ応用用。
ＵＢＲ：無指定ビットレート。ファイル転送及びｅメールのような非実時間応用用。これは、関連するサービスを保証せず、従って割振られた帯域幅資源を用いず、セル損失比またはセル転送遅延に関して保証せず、そして現在のネットワーク輻輳レベルに関する明示フィードバックを用いずに、セルの非連続バーストを伝送する
ＧＦＲ：保証（された）フレームレート。これも非実時間応用用。このサービスカテゴリは、契約した最小レートで、またはそれ以下でトラフィックを伝送する源のために損失保証を与える。源が契約した最小レートを超えれば、そのレートより上のトラフィックはどのような損失保証も受けられない。
ＡＢＲ：使用可能ビットレート。ネットワーク内で使用可能な帯域幅の量に依存して、情報転送レートを変化させることができる非実時間応用用。
【０００５】
典型的なＡＴＭスイッチにおいては、セル処理機能はネットワークのノード内で遂行される。各ノードはＡＴＭスイッチであり、入力コントローラ（ＩＣ）、スイッチファブリック（ＳＦ）、出力コントローラ（ＯＣ）、及びノード制御（Ｃ）を含む。ノード制御は、接続の確立及び解放、帯域幅予約、バッファリング制御、輻輳制御、保守、及びネットワーク管理を含む機能のために使用される。
【０００６】
各スイッチにおいては、入力コントローラは典型的に同期しているので、入力コントローラからの全てのセルは同時にスイッチファブリックに到着し、セルはそれらの優先順位に従って受入れられたり、または拒絶されたりすることができる。スイッチファブリックを通るトラフィックはスロットされ、スイッチファブリック遅延は、タイムスロット持続時間、パイプライン遅延、及びキューイング遅延の合計に等しい。
【０００７】
ノード制御は、スイッチファブリックをバイパスする直接通信経路によって、またはスイッチファブリックを通して伝送される制御セルを介しての何れかによって、入力コントローラ及び出力コントローラと通信する。
【０００８】
スイッチへの外部接続は、一般的に双方向である。双方向接続は、入力コントローラ（Ｃ）及び出力コントローラ（ＯＣ）を互いにグループにしてポートコントローラ（ＰＣ）を形成させることによって形成する。
【０００９】
仮想チャンネル内のセルの入力シーケンスはスイッチファブリックにまたがって保存されるので、各仮想チャンネル内のセルの出力シーケンスは入力シーケンスと同一である。セルは、セルヘッダー内にそのセルが属している接続を識別する仮想チャンネル識別子（ＶＣＩ）を含んでいる。各セルのヘッダー内の各入力ＶＣＩは入力コントローラにおいて変換され、出力識別子を指定する。この変換は入力コントローラにおいて、典型的には、入力ＶＣＩを使用してテーブルを表引きし、接続テーブルをアドレスすることによって遂行される。この接続テーブルは、その接続がルートされているスイッチファブリックの出力ポートを指定するルート指定フィールドをも含んでいる。接続の優先順位、サービスのクラス、及びトラフィックの型のような他の情報も、接続毎に接続テーブル内に含ませることができる。
【００１０】
ＡＴＭスイッチにおいては、セルの到着はスケジュールされていない。典型的な動作では、同一の出力ポートを各々が要求している複数のセルが異なる入力ポートに同時に到着するかも知れない。これらの要求が出力ポートの出力容量を超えるような動作を、出力競合（回線争奪）と称する。出力ポートは一時に固定された数（例えば、１つ）のセルしか伝送できないから、伝送のためには固定された数のセルだけしか受入れることができず、従ってそのポートへルートされた他のセルは破棄するか、または待ち行列内にバッファしなければならない。スイッチモジュールを通るセルをルート指定するために、例えば自己ルート指定及びラベルルート指定のような、異なる方法が使用される。
【００１１】
自己ルート指定ネットワークは、各セルにルート指定タグをプレフィックスする入力コントローラと共に動作する。典型的には、入力コントローラはルート指定テーブルからルート指定タグを入手する表引きを使用する。ルート指定タグはセルが送給される出力ポートを指定する。各スイッチング要素は、ルート指定タグを検査することによって迅速にルート指定決定を行うことができる。自己ルート指定ネットワークは、セルが入るスイッチポートには無関係に、要求された行先へ各セルが到着することを保証する。
【００１２】
ラベルルート指定ネットワークは、各スイッチング要素内の変換テーブルを参照する各セル内のラベルと共に動作する。ラベルは各スイッチング要素内で変換され、従ってスイッチング要素の任意のネットワークを使用することができる。
【００１３】
スイッチは２つの主要設計、即ち時分割、及び空間分割を有している。時分割スイッチングファブリックでは、全てのセルは、全ての入力及び出力ポートによって共通に共用される単一の通信チャンネルを通って流れる。空間分割スイッチングでは、入力ポートと出力ポートとの間に複数の経路が設けられている。これらの経路は同時に動作するので、スイッチファブリックを横切って同時に多くのセルを伝送することができる。従って、スイッチファブリックの合計容量は、各経路の帯域幅と、セルを同時に伝送できる経路の平均数との積である。
【００１４】
トラフィックロードがネットワーク内の使用可能なシステム資源を越えると、輻輳が発生して性能が劣化する。セルの数がネットワークの輸送容量内にある時には、送給されるセルの数が、輻輳を生じさせずに送られるセルの数に等しいように、全てのセルを送給することができる。しかしながら、もしノードがトラフィックを処理できないレベルまでトラフィックが増加すれば、輻輳が発生する。
【００１５】
輻輳は、幾つかの要因によって惹起される。もしネットワーク内のノードがそれらに要求される種々のタスク（キューイングバッファ、更新テーブル等）を遂行するのに遅過ぎれば、たとえ余分なライン容量が存在しているとしても、待ち行列が累積する。一方、たとえノードが無限に速いとしても、入力トラフィックレートが何等かの出力の特定グループのための出力トラフィックレートの容量を超えれば、待ち行列が累積する。
【００１６】
もしノードがキューイングセルのための自由バッファを有していなければ、ノードは新たに到着するセルを破棄しなければならない。パケットデータトラフィックの場合、あるセルが破棄されると、破棄されたセルを含んでいたパケットが多分多数回伝送され、輻輳エポックを更に拡張させる。
【００１７】
ＡＴＭスイッチにおいては、入力セルを受信し、格納するためにバッファが使用される。若干（固定）量のバッファ空間がＣＢＲ、ＲＴ-ＶＢＲ、及びＮＲＴ-ＶＢＲトラフィックのために予約されている。これらのサービスカテゴリからのトラフィックは受信側において管理されているので、空間の所要量は予め知られている。しかしながら、ＡＢＲ及びＵＢＲトラフィックは十分に調節されておらず、残余のバッファ空間から溢れてセルの損失、及び他の接続の品質の劣化がもたらされ得る。
【００１８】
従来の技術では、一般的に１つまたは２つのバッファアーキテクチャを使用する。１つのバッファアーキテクチャでは共用バッファ空間を使用するが、１つの高ボリューム接続が全バッファを溢れさせると、他の接続のためのバッファ空間が残されなくなり得る。別のバッファアーキテクチャでは、ある量のバッファ空間が各接続毎に割振られているので、溢れを保護するためにバッファ空間が必ずしも十分に活用されないことが多い。割振られた空間が殆どの時間使用されず、結局はトラフィックを輸送しない接続のために留保されて使用されることがないので、この不十分な活用はコスト高である。
【００１９】
（発明の概要）
本発明は、バッファプール利用率、及び各個々の源の推定される賦課ロードの両方に依存して、各源にバッファサイズを動的に割振る共用バッファアーキテクチャからなる。バッファプールが殆ど空である時には、各源に大きいバッファ空間が割振られる。バッファプールが満たされてくると、各源には個々の接続の重みに関係付けられた減少したバッファ空間が割振られる。
【００２０】
本発明は、源毎の受信されたセルの数を追跡し、その源のためのバッファメモリ内に比例する量のバッファ空間を動的に割振る。動的割振りは、トラフィックの量及び各源が取るバッファ空間の量に依存してバッファ空間を公平に割振るように、一方明白な損失目的を要求する接続のためにある保証されたバッファ空間を設けるように、全ての源に対するバッファメモリ割振りの十分さの関数としてなされる。従って、本発明の長所は、所与の接続が受ける相対的な公平さ（同一クラス内の他の接続に対する）を制御する能力を提供することである。動作中のメモリ割振りはバッファメモリ内のセルの合計数に依存して再調整される。
【００２１】
従って、本発明の方法及びシステムは、バッファが一杯でない場合に、より効率的な割振りを達成する。バッファサイズ（全体として、フルバッファ）の上限は固定バッファと同一であるが、それ以外は本発明は静的バッファ割振りよりも効率的である。それは、各源が可能な限り多くのバッファ空間を使用することができるように、使用可能なバッファ空間が最適化されるからである。各源にとっては、バッファは、組合わされた全ての源のために実際に使用可能であるよりも大きく見える。本発明は、コンプライアントな源をコンプライアントではない源の誤挙動の効果から確実に隔離することによって、要求を強く主張してネットワークの使用をより効率的にする。
【００２２】
複数のホップよりも効率的な、重み付き公平破棄動作が提供される。固定されたバッファでは、その後のノードにおける破棄の危険性がホップの数と共に指数的に増加する。本発明の動的割振りでは、システムは、非静止ローディングパターンに動的に適合させる能力を保持しながら、安定状態条件に調整する傾向があるので、損失の可能性の低下が達成される。
【００２３】
本発明は特にＡＴＭネットワークに有用であるが、複数の源からの共用バッファリングが動的制御を要求すれば、本発明の他の応用が存在する。
【００２４】
破棄しきい値は、望まれるサービスの品質、所与のクラスのサービスの相対的な重み、または所与のサービスクラス内に確立されている接続の数のような要因に依存して、異なる量のメモリをバッファに割振るように変化させることができる。
【００２５】
バッファの溢れの問題は、源が調節されていないＵＢＲ及びＧＦＲトラフィックにおいて最大である。数年以内にトラフィックの主流になることが予測されるこれらのトラフィックの型では、本発明の効果は帯域幅を制御（システムのトラフィック管理部分によって）することである。源レートを制御するために、明示順方向輻輳指示（ＥＦＣＩ）を使用することが好ましい。
【００２６】
当分野に精通していれば、以下の添付図面に基づく詳細な説明から本発明は容易に理解されよう。本発明は種々の変更及び代替形状が可能であるが、以下にその特定の実施の形態を例として説明する。しかしながら、この説明が本発明を以下の特定の形状に限定する意図はないことを理解されたい。そうではなく、本発明は特許請求の範囲に記載されている本発明の思想及び範囲内に入る全ての変更、等価、及び代替をカバーするものである。
【００２７】
（実施の形態）
総合ネットワーク−図１
先ず図１を参照する。複数のネットワークユーザが、源／行先（Ｓ／Ｄ）４で表されている。各ユーザは、典型的に、源（Ｓ）として情報を送り、行先（Ｄ）として情報を受信する。Ｓ／Ｄユニット４の源（Ｓ）は、他のＳ／Ｄユニット４の行先（Ｄ）へ情報を送る。情報を源から行先へ転送するために、各Ｓ／Ｄユニット４はマルチノード（Ｎ）ネットワーク１を通して接続されている。ネットワーク１は、多くのノード（Ｎ）５を含んでいる。ノードは、ノードからノードへ接続されているから、一般的に、ネットワーク１内にノード５のチェーンを形成することによって、Ｓ／Ｄユニット４のどの特定の１つをも、他のＳ／Ｄユニット４のどの１つへも接続することができる。一般的に、Ｓ／Ｄユニット４とノード５との間の接続、及びノード５間の接続は、情報を両方向に転送することを可能にする双方向リンク８によっている。
【００２８】
明瞭化のために、図１に図示したノード（Ｎ）５の数は比較的少数であるが、ネットワークは数百またはそれ以上のノードを含むことができる。またＳ／Ｄユニット４は、Ｓユーザ、即ち４-０、４-１、４-２、４-３、４-４、…、４-（Ｓ−２）、４-（Ｓ−１）を含む。Ｓの値はどのような整数であることもできるが、典型的にはＳは数百またはそれ以上である。
【００２９】
典型的な実施の形態では、図１の通信システムはＡＴＭネットワークであり、情報転送の単位はセルである。複数のセルが、情報のパケットを形成する。ネットワーク１は、画像、音声、及びデータを含む異なる型の情報を支援するようにセル及びパケットと通信する。
【００３０】
仮想チャンネル−図２
図２において、Ｓ／Ｄユニット４-ｘは、複数Ｃのノード（Ｎ）５-０、５-１、…、５-（Ｃ−１）を通してＳ／Ｄユニット４-ｙに接続されている。
【００３１】
図２に示すＳ／Ｄユニット４-ｘは、図１のＳ／Ｄユニット４の何れかの典型である。例えば、Ｓ／Ｄユニット４-ｘは、図１のＳ／Ｄユニット４-２を表すことができる。同様に、図２のＳ／Ｄユニット４-ｙは、図１のＳ／Ｄユニット４の何れかを表すことができる。例えば、図２のＳ／Ｄユニット４-ｙは、図１のＳ／Ｄユニット４-４を表すことができる。この例では、ノード５-０、５-１、…、５-（Ｃ−１）は、図１のＳ／Ｄユニット４-２をＳ／Ｄユニット４-４に接続するために使用されているネットワーク１内のＣノードを表している。
【００３２】
図２において、双方向リンク８-０、８-１、…、８-（Ｃ−１）、８-（Ｃ）は、複数Ｃのノード（Ｎ）５-０、５-１、…、５-（Ｃ−１）を通してＳ／Ｄユニット４-ｘからＳ／Ｄユニット４-ｙに接続されている。図２において、情報は、Ｓ／Ｄユニット４-ｘ内の源（Ｓ）からＳ／Ｄユニット４-ｙ内の行先（Ｄ）へ転送することができる。同様に、情報をＳ／Ｄユニット４-ｙ内の源（Ｓ）からＳ／Ｄユニット４-ｘ内の行先（Ｄ）へ転送することができる。情報は、図２の何れの方向へも転送することはできるが、説明の目的から、源（Ｓ）と行先（Ｄ）との間の転送が、Ｓ／Ｄユニット４-ｘからＳ／Ｄユニット４-ｙへであるのか、またはＳ／Ｄユニット４-ｙからＳ／Ｄユニット４-ｘへであるのかを考えると便利である。方向には関係なく、各転送は源（Ｓ）から行先（Ｄ）へである。
【００３３】
ＳからＤへの転送−図３
図３に、図２の仮想チャンネル内での源（Ｓ）から行先（Ｄ）への転送に使用される回路を示す。図３において、図２のＳ／Ｄユニット４-ｘ内の源ユニット４-（Ｓ）は、図２のＳ／Ｄユニット４-ｙ内の源ユニット４-（Ｄ）に接続されている。
【００３４】
図３において、各リンク８-０、８-１、…、８-（Ｃ−１）、８-（Ｃ）は、情報を順方向に転送するための順方向（Ｆ）チャンネルと、情報を逆方向に転送するための逆方向（Ｒ）チャンネルとを含んでいる。図３の逆方向チャンネルは、源ユニット４-（Ｄ）から行先ユニット４-（Ｓ）への情報の転送に関している。図３の逆方向チャンネルは、図１のネットワークに関連して使用される制御情報を送る目的のためのものである。逆方向チャンネル（Ｒ）は、図２に関連して説明したＳ／Ｄユニット４-ｘからＳ／Ｄユニット４-ｙへの情報の順方向の転送に使用される順方向チャンネル（Ｆ）とは区別される。順方向（Ｆ）及び逆方向（Ｒ）の両チャンネルは、源ユニット４-（Ｓ）から行先ユニット４-（Ｄ）への転送に関している。図３の各ノードは、順方向（Ｆ）回路６及び逆方向（Ｒ）回路７を含んでいる。図３において、順方向チャンネル８-０Ｆ、８-１Ｆ、…、８-（Ｃ−１）Ｆは、入力としてそれぞれ順方向回路６-０、６-１、…、６-（Ｃ−１）に接続されている。順方向チャンネル８-（Ｃ）Ｆは、ノード６-（Ｃ−１）からユニット４-（Ｄ）まで接続されている。同様に、逆方向チャンネル８-０Ｒ、８-１Ｒ、…、８-（Ｃ−１）Ｒは、逆方向回路７-０、７-１、…、７-（Ｃ−１）から接続されている。逆方向チャンネル８-（Ｃ）Ｒは、Ｄユニット-（Ｄ）から逆方向回路７-（Ｃ−１）まで接続されている。
【００３５】
図３において、各ノード５は、順方向（Ｆ）回路６から逆方向（Ｒ）回路７まで接続されているフィードバック接続９を有している。詳述すれば、フィードバックチャンネル９-０、９-１、…、９-（Ｃ−１）は、それぞれノード５-０、５-１、…、５-（Ｃ−１）内の順方向（Ｆ）回路６から逆方向（Ｒ）回路７まで接続されている。図３の回路においては、仮想チャンネル接続は、順方向チャンネルセッティングアップに沿って、Ｓユニット４-（Ｓ）とＤユニット４-（Ｄ）との間に順方向の通信経路を作っている。図１のネットワーク１内には他の仮想チャンネルも確立されているので、各ノード、及び図３のノードを含む行先においてバッファリングが必要である。
【００３６】
簡単なノードの実施の形態−図４
図４に、図３の信号経路を有するノードの１つの典型的な実施の形態を示す。図４において、ノード５は、Ｎリンク１８-０、１８-１、…、１８-ｎ、…、１８-（Ｎ−１）を含む。図４の各リンク１８は、図２の双方向リンク８に類似している。図４では、リンク１８-０、１８-１、…、１８-ｎ、…、１８-（Ｎ−１）は、ポートコントローラ１１-０、１１-１、…、１１-ｎ、…、１１-（Ｎ−１）に接続されている。
【００３７】
図４のノードは、例えば、リンク１８の１つ（例えば、図４の入力リンク１８-０）を、スイッチファブリック１０を通して別のリンク１８の１つ（例えば、リンク１８-ｎ）に接続することによって、図３の情報転送に関連して使用される。この例では、スイッチファブリック１０は、リンク１８-０をリンク１８-ｎに接続するように機能する。
【００３８】
図４のノードが図２のノード５-１を表すような例では、図２のリンク８-１は図４のリンク１８-０であり、図２のリンク８-２は図４のリンク１８-ｎである。
【００３９】
このような接続では、図４のノードは、情報を例えばリンク１８-０からリンク１８-ｎへ接続し、また情報を逆方向にリンク１８-ｎからリンク１８-０へ接続する。リンク１８-０及び１８-ｎは、説明のために任意に選択したものである。Ｎリンク１８の何れかを、他の何れかのリンク１８へ接続するために、図２の回路内で選択することができる。
【００４０】
図４のノードを図３の仮想チャンネル接続（源（Ｓ）が左側、行先（Ｄ）が右側）に使用する場合、説明の目的からリンク１８-０がノード５への順方向入力であり、リンク１８-ｎがノードからの順方向出力であるものとする。
【００４１】
図４において、ポートコントローラ（ＰＣ）１１-０、１１-１、…、１１-ｎ、…、１１-（Ｎ−１）は、それぞれ入力コントローラ１４-０、１４-１、…、１４-ｎ、…、１４-（Ｎ−１）を有し、またそれぞれ出力コントローラ１５-０、１５-１、…、１５-ｎ、…、１５-（Ｎ−１）を有している。図４において、順方向情報セルは、図３の源４-Ｓからバス１８-０１、入力コントローラ１４-０、バス２０-ｎ０、スイッチファブリック１０、バス２０-ｎ１、コントローラ１５-ｎ、及びバス１８-ｎ０を通して図３の行先４-（Ｄ）へ送られる。ポートコントローラは、共用キューイングユニット５１内に配置されている共通バッファ記憶装置を共用し、バス４１-０、４１-１、４１-ｎ、…、４１-（Ｎ−１）を通してユニット５１に双方向に接続されている。
【００４２】
キューイングユニット−図５
図５に、図４のキューイングユニット５１の詳細を示す。キューイングユニット５１は、データ待ち行列ユニット５２及び待ち行列制御ユニット５３を含む。データ待ち行列ユニット５２及び待ち行列制御ユニット５３は、各々双方向バス４１-０、４１-１、…、４１-ｎ、…、４１-（Ｎ−１）に接続されている。バス４１上の制御情報は待ち行列ユニット５３へ接続され、バス４１上のデータはデータ待ち行列ユニット５２へ接続される。
【００４３】
図５に示す待ち行列制御ユニット５３は、データ待ち行列ユニット５２及びキューイングユニット５１の総合動作を制御する待ち行列管理部５４を含んでいる。待ち行列管理部は、典型的に、ソフトウェアを実行することができる処理ユニットを含む。バス４１上の入力情報がデータ待ち行列ユニット５２内への格納を要求すると、待ち行列管理部５４は自由バッファリストユニット５９から使用可能なバッファ位置を検出し、その使用可能なデータ位置をデータ待ち行列ユニット５２に割当てる。待ち行列管理部の一般的機能及び動作は公知である。キューイングに加えて、及び本発明の方法で動作させるために、総合通信ネットワークの効率的な動作を促進するように若干のセルを時折破棄する必要があり得る。待ち行列管理部５４の制御の下にある破棄ユニット５５は、先に割振られた待ち行列割当てを破棄する時点を決定する。キューイング動作の結果は、ポート毎の待ち行列ユニット５６内に格納され、ユニット５６自体はデキューユニット５７を活動させ、ユニット５７自体はマルチキャストサーバーを通して動作して先に割振られたバッファ位置を除去する。除去されると、デキューされたバッファ位置はユニット５９内の自由バッファリストへ戻されて追加され、再割当てのために使用可能になる。
【００４４】
破棄ユニット５５。破棄ユニット５５は、３つのユニット、即ちＦＩＦＯユニット６１（サブユニット６１-１及び６１-２を含む）、破棄ユニット６２、及びポインタ完全性ユニット６３からなる。破棄ユニット５５は、
１．全ての接続の契約されたサービス品質（QｏＳ）を保証（損なう接続を破棄することによって）
２．バッファ輻輳の監視及び制御
３．バッファが輻輳し始めるとＡＴＭヘッダー内に明示順方向輻輳指示（ＥＦＣＩ）のタグ付けを遂行
４．輻輳が過大になると接続毎にセル及びフレームの破棄を遂行
５．非保証接続（ＡＢＲ、ＧＦＲ、及びＵＢＲ）間の公平さの保証
６．種々のＥＦＣＩ及び破棄しきい値を支援することによって、ＡＢＲ、ＧＦＲ、及びＵＢＲの異なる品質の提供
７．ポインタ完全性検証（ポインタの重複が発生していないことを確認する）に責を負う。
【００４５】
図４の共用バッファアーキテクチャでは、それらの使用が制限されない仮想チャンネル（ＶＣ）が全ての使用可能なバッファリングを使用することができ、それのため他のＶＣ源に対しては不公平になる。この動作は、２つの型のトラフィックを受信側において管理するＣＢＲ、ＲＴ-ＶＢＲ、及びＲＴ-ＶＢＲトラフィックにとっては問題にならない。しかしながら、ＡＢＲ及びＧＦＲトラフィックはピークセルレートに関してのみ管理され、平均及びＵＢＲに関しては結局管理されない。セルプールが、全てのポートについて全てのサービスクラス（ＣｏＳ）源によって共用されるので、非行（トラフィック契約違反）ＡＢＲ、ＧＦＲ、またはＵＢＲ源がバッファプールを満たして最終的に他の良好に挙動している接続の品質を劣化させないようにする、種々のメカニズムが使用される。
【００４６】
一方法では、保証されたトラフィックのためにある量のバッファリングを予約し、非保証トラフィックが使用できないようにする。予約される正確な量は、全ＣＢＲ及びＶＢＲ接続源によって必要とされるバッファリングを加算することによって見出される。この予約方法は、共用バッファ内に存在するＡＢＲ、ＧＦＲ、及びＵＢＲセルの数を斟酌し、全ての使用可能なバッファ空間が使用されている場合には何れかの付加的なＡＢＲ、ＧＦＲ、またはＵＢＲセルをドロップさせることを暗示している。
【００４７】
以下に詳細に説明する公平破棄方法では、非保証トラフィックが保証トラフィックの損失をもたらすことはない。この公平破棄方法は、図５のＦＩＦＯユニット８１における所与の最大エンキューイングレートについて、セル毎の特定の最大レートのトラフィックを破棄する。もし指定されたサイズのセルマージンが保証トラフィックのために予約されていれば、それは、全てのポートからラインレートで到来する非保証トラフィックの比例的バーストを必要とし、保証トラフィックに影響し始める。非保証トラフィックのこのようなバーストはありそうもないので、実際的的には、公平破棄メカニズムは単独で十分である。更に、殆ど枯渇した自由バッファリストが、主要輻輳が発生した時に非保証トラフィックに対する“ハード”な限界として好ましい実施の形態内で使用される時点を指示するために、殆ど空フラグが使用されるようになる。
【００４８】
源毎の動的破棄しきい値
共通バッファプール（図４のキューイングユニット５１）内に使用されている公平破棄方法は、使用可能なバッファリング空間の効率的使用を提供し、全ての源間の保護を保証する。動的しきい値は、待ち行列に入れられたセルの合計数、源の推定される賦課ロード、及び所与のサービスクラス内に確立された接続の数の関数として変化する。各ＶＰ／ＶＣ接続源は、それ自体のセルカウンタを有している。セルを受信した時に、共用バッファプール内に存在するその接続のセルの数と、接続源毎に許容されるセルの最大数（この数は、その時点における合計バッファプール利用率の関数である）とを比較することによって、そのセルを保持するか否かの決定がなされる。
【００４９】
本発明の動的方法の原理を図８に示す。図８において、水平軸はバッファされたセルの合計数を表し、垂直軸は接続源毎にバッファできるセルの数を表し、斜線を施した領域はセルが保持される領域を表している。破棄関数データはランダムアクセスメモリ内に維持されているので、トラフィック分布に従って変更することは容易である。例えば、ＣＯＳ、ＱｏＳ、ＣＬＲ、ＣＬＰビットのような全ての型のビットのために異なる破棄関数を使用することができる。
【００５０】
接続源を互いに他方から保護するのに加えて、この動的破棄方法はＵＢＲ接続源の間の公平さをも確立する。多くのＵＢＲ接続源が存在する場合、各源は可能な限り大きい帯域幅を得ようと試みる。この試みの正味効果は、バッファをゆっくりと満たすことである。バッファが満たされるにつれて、接続源毎のバッファリングの最大量が減少して行く。個々の公平重みに最も近いレベルでセルをバッファする接続源は最初にドロップされる源であり、最終的に所与の重み内で各ＵＢＲまたはＧＦＲ接続源毎にバッファされるセルの数は均一になる傾向がある。同じことが、遷移中のＡＢＲトラフィックの場合にも言える。通常の場合には、ＡＢＲ制御ループは、全ての接続源の平均帯域幅が使用可能な帯域幅より小さいことを保証する。しかしながら、もし使用可能な帯域幅を一時的に越えれば、バッファされるセルの合計数が増加し、接続源毎のバッファの最大量が減少し始める。これが発生すると、殆どのバッファリングを使用している接続源（最尤違反者でもある）は、それらのトラフィックが破棄されることが予見される第１の源である。この動作も、使用可能なバッファリングを、全ての接続源の間で公平に共用させることになる。
【００５１】
公平破棄方法は、ユニット６１内の２つのＦＩＦＯ６１-１及び６１-２の一方内にセルが存在するのを待機する。両ＦＩＦＯ６１-１及び６１-２はデータを含んでおり、最高優先順位のＦＩＦＯ６１-１が常に最初にデキューされる。１実施の形態では、100ｎＳの期間中に、セル破棄メカニズムはセルポインタ及び記述子を読み、そのセルをドロップさせるのか、または待ち行列へ渡すのかを決定する。
【００５２】
１つのセルが受入れられると、その接続源のためのセルカウンタ、及び全ての源のための合計セルカウンタがインクリメントされる。１つのセルが拒絶されても、対応するセルカウンタ及び合計セルカウンタは不変のままである。１つのセルがバッファプールからデキューされると、その接続源のための対応するセルカウンタ、及び全ての源のための合計セルカウンタが共にデクレメントされる。
【００５３】
サブクラス毎の破棄しきい値
異なる破棄しきい値関数を動的破棄方法によって使用して、セル損失比（ＣＬＲ）の制御を与えることができる。破棄しきい値は、（全ての型の）バッファされた合計セルの関数であるから、バッファされたセルの合計量、破棄しきい値、及びＣＬＲの間の正確な統計的関係は、一般に決定的ではない（各クラス毎のトラフィックの量が既知の値に制限されていない限り）。その結果、一般的に破棄しきい値関数は特定のＣＬＲを保証しない。しかしながら、特定クラス内の異なるサブクラスの間のＣＬＲの相対的挙動を制御する。異なる破棄しきい値を有することは、特定クラス内の異なるサブクラスの間のＣＬＲの相対的挙動を制御するのにそれを使用できることから、ＡＢＲ、ＧＦＲ、及びＵＢＲのような非保証トラフィックには特に有用である。
【００５４】
ＮＲＴ-ＶＢＲの場合には、ＣＡＣビットはセル損失レート（ＣＬＲ）を０に近づけることを保証するために、許容されているＶＢＲトラフィックの量を制御する。適合するＣＢＲ接続源の場合には、予測されるバッファリング量は常に低く予測されるから、複数のＣＢＲ破棄しきい値は有用ではない。同じことがＲＴ-ＶＢＲにも言える。しかしながら、セル損失優先順位（ＣＬＰ）-透過型サービス、及びＣＬＰ-非透過型サービスの両方を支援するために、ＲＴ-ＶＢＲ接続の場合に複数の破棄しきい値が使用されている。
【００５５】
輻輳指示（ＥＦＣＩ）−図７
輻輳指示は、公平破棄動作に類似する動作により得られる。１つの接続源が輻輳レベルに到達したか否かを、１組の曲線が記述する。セルがデキューされると、デキューメカニズムは公平破棄サブシステムから対応する接続源の輻輳状態を入手し、ＥＦＣＩ出力ビットを相応にセットする。図７は、図６の公平破棄値に類似する輻輳指示値を表している。
【００５６】
ＡＡＬ５パケット破棄
可能な場合には、フレームからのランダムなセルの代わりに、完全フレームをドロップさせる方がより効率的である。このパケット破棄関数は、本発明の動的破棄方法に実現されている。ＡＴＭ適合層型５（ＡＡＬ５）セルを受信した場合に、もし接続源が、輻輳指示しきい値は通過しているが、未だに破棄しきい値には到達していなければ、完全フレームだけが破棄される。破棄しきい値を通過すると、フレーム内の位置には無関係に全てのセルがドロップされる。フレームが破棄され始めるとフラグがセットされ、輻輳レベルには無関係に、そのフレームの残余のセルがフレームの最後のセルまで破棄されることを指示する。
【００５７】
公平破棄及び輻輳指示ブロック図−図８
図８は、図５の公平破棄ユニット５５の１実施の形態を、接続毎の輻輳検出構造及び流れと共に示している。図８において、３つのアップ／ダウンカウンタ８１は、各クラスのサービスの全ての源のために待ち行列に入れられるセルの数をカウントする（エンキューされる場合はアップカウント、デキューされる場合はダウンカウント）。アップ／ダウンカウンタ８１からの値は、バッファ内のサービスのクラス毎の合計セルカウントであり、公平破棄値を得るためにＲＡＭ８５への入力として、及び輻輳指示値を得るためにＲＡＭ８６への入力として使用される。ＲＡＭ８７は、各セル源毎のセルカウントをそのセル源の接続数の関数として格納し、各セルがエンキューまたはデキューされる度に更新される出力Nを供給する。ＲＡＭ８５は、図６に関連して説明したように、アップ／ダウンカウンタ８１の１つからのＸ軸入力に基づいて、Ｙ軸の出力値表現を供給する。次いで、この出力値は、コンパレータ８３において、ＲＡＭ８７から得られた特定のセル源の接続のセルバッファの数Nと比較される。Nの源毎の値は、コンパレータ８３において、ＲＡＭ８５からのＹ軸出力と比較され、公平破棄方法のための保持信号、または破棄信号を供給する。また出力Nは、コンパレータ８４において、ＲＡＭメモリ８６からのｙ軸の値と比較され、もしＮがメモリ８６からのＹより小さければ、輻輳指示を形成する。
【００５８】
特定のセル源のためにセルがエンキュー、またはデキューされる度に、その源のためのセルカウントがＲＡＭ８７内に格納され、加算器／減算器８２はカウンタ８１を１だけインクリメント、またはデクレメントさせる。
【００５９】
破棄しきい値の作成及び調整−図９
図９に示す曲線は、本発明の方法及びシステムによって破棄決定を行うための４つの関連パラメータを示しており、これらは、任意のセル時点における接続のためにバッファ内に許容されるセルの最大数、所与のＣｏＳのために確立された接続の数、ロードの下で動作している時にある接続に保証されるセルバッファの数、及び対応するＣｏＳのためにバッファ内に許容されるセルの最大数を含む。
【００６０】
図９の４つのマークされた各点９-１、９-２、９-３、及び９-４は、上述した４つの基準の１つに対応している。点９-１は、ｙ軸の最大値、好ましくはトラフィック到着強度の関数を表している。現在では好ましい点９-１のセッティング方法は、以下の式１に従って、セルレート、外出（gress）レート、及び共用バッファサイズを斟酌する最悪例シナリオアプローチからなる。
inputLoadmax＝［（ cellRate * SHBUFSIZE ） / egressRate ］
このアプローチは、所与の接続が要求するセルバッファの最大数の合理的な、早期推定を与える。この式において、項cellRateは、ピークセルレートまたは維持されたレートとピークレートとの間のある値（例えば、ＶＢＲ接続のための計算された等価容量）の何れかからなる。項egressRateは、ＭＳＵ−最悪例ローディングシナリオ上に見出される最も遅い物理的ポートレートを表している。
【００６１】
曲線勾配が負になり始める点９-２は、輻輳のためにセルの破棄が受入れ可能であるような曲線に適用できる。ＣＢＲセルの場合、及びＶＢＲ接続のＣＬＰ（Ｏ）（またはＶＢＲ-１接続のＣＬＰ（Ｏ＋１））セルの流れの場合、輻輳による破棄は望ましくない（ＣＬＲ目的のために）。従って、これらの接続型のための曲線は、勾配が負になり始める点を含まない（しかしながら、ｘ＝１からｘ＝最大まで０勾配を有している）。他の全てのセル型の場合には、負勾配（点２）が適切であるが、勾配の程度は変化する。
【００６２】
曲線上の点９-２の位置は、導入された接続の数に関連して輻輳の可能性が増加するから、合計バッファロード（ＣｏＳ毎の）を生成する接続の数によって最良に推定される。一般に、使用可能なハードウェアは活動接続の数を追跡することはできないから、１つの実施の形態は、近似として単に確立された接続の数を注視するだけである。適応曲線管理実施の形態では、接続が確立されるにつれて、ＭＳＵ接続毎の実際の数を追跡する。
【００６３】
点９-３は特にＡＢＲ接続に関連し、それは最小セルレートに関連している。勿論、最小セルレートにおける、またはそれ以下のセルには、若干の所定の損失保証を与えるべきである。従って、図９の破棄曲線の点９-３における“屈曲点”は、所与の接続のロードの下で保証バッファ空間を許容する何等かのサービス（例えば、保証されたフレームレートＧＦＲ）に特に関連している。点９-２は、式（１）の項cellRateをＭＣＲに置換することによって定義することもできる。
【００６４】
最後に、ＣｏＳ内の曲線の任意の集まりの場合、点９-４の最大ｘ軸値は、ＣＬＲ目的を有するトラフィックのための保証バッファ空間を提供するそのＣｏＳのための共用バッファ仕切り（パーティション）を表している。曲線生成の静的モード方法は、ＭＳＵ上に見出される（各ポートのユーザが定義した）構成値に基づいて共用バッファの仕切りを推定する。曲線管理の適応モードは、これらの仕切りを動的に調整し、変化するセルレベルロードに適合させる。
【００６５】
ポインタ完全性検証−図１０
図１０に、図５のポインタ検証ユニット６３の詳細を示す。セル記述子の完全性を検証するために使用されるパリティ検出器は、ポインタの重複（待ち行列を併合させ得る）のような問題を検出するのには役立たないから、検証ユニット６３が有用である。検証ユニット６３は、ポインタがキューイングシステムへ入るか、またはそれから去る度に１組の“ポインタ使用中”フラグを監視し、更新することによって、重複ポインタを検出する。ポインタがエンキューされると、検証システムは先ずポインタテーブル９１内のそのポインタのための“使用中”フラグがクリアされていることをチェックし、次いでそれをセットする。セルがデキューされると、検証システムはテーブル９１内のそのデキューされたポインタの“使用中”フラグがセットされていることを確認し、次いでそれをりセットする。何等かのエラーが検出されれば、ＣＰＩ割込み要求（ＩＲＱ）を用いて主ＣＰＵ（待ち行列管理部５４）へ直ちに信号する。
【００６６】
ＣＰＵは、始めに各ＲＡＭメモリユニット、即ち、破棄しきい値メモリ、接続毎のセルカウントメモリ、接続毎のセルドロップドメモリ上でメモリ初期化を遂行する。次いで、ＣＰＵは全てのカウントメモリをクリアし、種々の破棄及び輻輳しきい値をプログラムし、破棄サブシステム内に使用されている３つのＣＯＳセルカウンタをクリアする。第１のカウンタを読んでバッファされたＣＢＲ及びＶＢＲセルの組合わされた数を戻し、第２のカウンタはＡＢＲセルの数を戻し、そして第３はＵＢＲセルの数を戻す。待ち行列に入れられるセルの合計数は、これら３つのカウンタの合計に等しい。
【００６７】
以上に、本発明の１つの特定の実施の形態を説明したが、当分野に精通していれば、本発明の範囲及び思想から逸脱することなく本発明に種々の変更をなしえることが理解されよう。本発明の実施の形態において説明した精密な成分はその動作が臨界的ではないことを理解されたい。詳述すれば、所望の結果を達成するために、種々のデジタル信号プロセッサとハードウェアとの他の組合わせ、及び信号処理アルゴリズムを組み入れたコンピュータプログラムを使用することができる。本発明及びその長所は以上の説明から理解されたであろう。本発明の思想及び範囲から逸脱することなく以上の説明に種々の変化を与え得ることは明白である。
【図面の簡単な説明】
【図１】  マルチノードネットワークを通して接続されている複数の源／行先（Ｓ／Ｄ）ユーザの概要ブロック図である。
【図２】  図１のネットワーク内のノードのシーケンスを通して１つのＳ／Ｄユーザを別のＳ／Ｄユーザに接続する回路の概要図である。
【図３】  情報を源（Ｓ）から順方向（Ｆ）に行先（Ｄ）へ送り、制御信号を逆方向（Ｒ）へ源（Ｓ）に伝送する仮想チャンネルを有する図２の回路の概要図である。
【図４】  図１のネットワーク内のノード（Ｎ）の典型的な１つの概要図である。
【図５】  図４のノード内のキューイングユニットの概要図である。
【図６】  動的セル破棄しきい値を表す図である。
【図７】  輻輳指示及びフレーム破棄しきい値の概要図である。
【図８】  公平破棄及び輻輳指示のブロック図である。
【図９】  破棄決定を行うための関連パラメータを示す図である。
【図１０】  ポインタ完全性検証の概要図である。
【図１１】  構成要素８９のブロック図である。
【図１２】  構成要素８７のブロック図である。
【図１】
0004395280.tif 000002
【図２】
0004395280.tif 000003
【図３】
0004395280.tif 000004
【図４】
0004395280.tif 000005
【図５】
0004395280.tif 000006
【図６】
0004395280.tif 000007
【図７】
0004395280.tif 000008
【図８】
0004395280.tif 000009
【図９】
0004395280.tif 000010
【図１０】
0004395280.tif 000011
【図１１】
0004395280.tif 000012
【図１２】
0004395280.tif 000013