(57)【特許請求の範囲】
【請求項１】
多数の入力ポート、多数の出力ポート、およびいずれかの入力ポートで受信したプロトコルデータユニットをいずれかの出力ポートに交換する交換ファブリックを有するディジタル交換機内で使用するための、プロトコルデータユニットのバッファリングを制御する方法であって、
各入力ポートが、１つまたは複数の送信待ち行列を有する入力バッファに関連付けられ、
各出力ポートが、１つまたは複数の受信待ち行列を有する出力バッファに関連付けられ、
（ａ）それぞれ特定の出力ポートに向けられたプロトコルデータユニットを入力ポートで受信するステップと、
（ｂ）それぞれ特定の出力ポートに向けられたプロトコルデータユニットを記憶するように構成された送信待ち行列にプロトコルデータユニットを割り当てるステップと、
（ｃ）それぞれ特定の出力ポートに向けられたプロトコルデータユニットを記憶するように構成された受信待ち行列を所定の順序でポーリングするステップと、
（ｄ）ポーリングされた受信待ち行列の負荷が十分に軽い場合、該ポーリングされた受信待ち行列と同じ出力ポートに関連付けられた各送信待ち行列にクレジットを割り当てるステップと、
（ｅ）送信待ち行列を所定の順序でポーリングするステップと、
（ｆ）ポーリングされた送信待ち行列が十分なクレジット量を有する場合、該ポーリングされた送信待ち行列から該ポーリングされた送信待ち行列と同じ出力ポートに関連付けられた受信待ち行列にプロトコルデータユニットを送信するステップと、
（ｇ）送信されたプロトコルデータユニットを受信待ち行列から宛先出力ポートにさらに送信するステップとを含む方法。
【請求項２】
ステップ（ｆ）が、送信されたプロトコルデータユニットの長さに関連して、ポーリングされた送信待ち行列に割り当てられたクレジットの量を減らすステップをさらに含む請求項１に記載の方法。
【請求項３】
ステップ（ｄ）で、割り当てられるクレジットの量が送信待ち行列ごとに異なる請求項１に記載の方法。
【請求項４】
ステップ（ｂ）で、各送信待ち行列が、特定のサービス品質を享受する資格があるプロトコルデータユニットを記憶するように構成されている請求項１に記載の方法。
【請求項５】
ステップ（ｄ）で、送信待ち行列に記憶されたプロトコルデータユニットが享受する資格があるサービス品質に関連して、割り当てられるクレジットの量が送信待ち行列ごとに異なる請求項４に記載の方法。
【請求項６】
ステップ（ｄ）で、相対的に高いサービス品質を享受する資格があるプロトコルデータユニットを記憶する送信待ち行列に、相対的に低いサービス品質を享受する資格があるプロトコルデータユニットを記憶する送信待ち行列よりも多くのクレジットが割り当てられる請求項４に記載の方法。
【請求項７】
ステップ（ｄ）で、各送信待ち行列にクレジットのしきい値量が割り当てられる請求項１に記載の方法。
【請求項８】
ステップ（ｄ）で、割り当てられるクレジットの量が調整可能である請求項１に記載の方法。
【請求項９】
ステップ（ｄ）で、出力ポートへの送信待ちのデータの量を所定のしきい値と比較することで負荷が測定される請求項１に記載の方法。
【請求項１０】
ステップ（ｃ）で、受信待ち行列がラウンドロビン方式でポーリングされる請求項１に記載の方法。
【請求項１１】
ステップ（ｅ）で、送信待ち行列がラウンドロビン方式でポーリングされる請求項１に記載の方法。
【請求項１２】
多数の入力ポート、多数の出力ポート、およびいずれかの入力ポートで受信したプロトコルデータユニットをいずれかの出力ポートに交換する交換ファブリックを有するディジタル交換機内で使用するための、プロトコルデータユニットのバッファリングを制御する方法であって、
各入力ポートが、１つまたは複数の送信待ち行列を有する入力バッファに関連付けられ、
各出力ポートが、１つまたは複数の受信待ち行列を有する出力バッファに関連付けられ、
（ａ）プロトコルデータユニットを入力ポートで受信するステップと、
（ｂ）送信待ち行列にプロトコルデータユニットを割り当てるステップと、
（ｃ）特定の送信待ち行列からのプロトコルデータユニットを受信し、プロトコルデータユニットを特定の宛先出力ポートに送信するように構成された共用出力バッファ内に、リンクされたエントリリストをそれぞれ含む受信待ち行列を所定の順序でポーリングするステップと、
（ｄ）ポーリングされた受信待ち行列内のエントリ数が十分に小さい場合、該ポーリングされた受信待ち行列にプロトコルデータユニットを送信するように構成された特定の送信待ち行列の各々にクレジットを割り当てるステップと、
（ｅ）送信待ち行列を所定の順序でポーリングするステップと、
（ｆ）ポーリングされた送信待ち行列が十分なクレジット量を有する場合、該ポーリングされた送信待ち行列から、該ポーリングされた送信待ち行列からのプロトコルデータユニットを受信するように構成された受信待ち行列にプロトコルデータユニットを送信するステップと、
（ｇ）送信されたプロトコルデータユニットを受信待ち行列から宛先出力ポートにさらに送信するステップとを含む方法。
【請求項１３】
ステップ（ｆ）が、送信されたプロトコルデータユニットの長さに関連して、ポーリングされた送信待ち行列に割り当てられたクレジットの量を減らすステップをさらに含む請求項１２に記載の方法。
【請求項１４】
ステップ（ｄ）で、割り当てられるクレジットの量が送信待ち行列ごとに異なる請求項１２に記載の方法。
【請求項１５】
ステップ（ｂ）で、各送信待ち行列が特定のサービス品質を享受する資格があるプロトコルデータユニットを記憶するように構成されている請求項１２に記載の方法。
【請求項１６】
ステップ（ｄ）で、送信待ち行列に記憶されたプロトコルデータユニットが享受する資格があるサービス品質に関連して、割り当てられるクレジットの量が送信待ち行列ごとに異なる請求項１５に記載の方法。
【請求項１７】
ステップ（ｄ）で、相対的に高いサービス品質を享受する資格があるプロトコルデータユニットを記憶する送信待ち行列に相対的に低いサービス品質を享受する資格があるプロトコルデータユニットを記憶する送信待ち行列よりも多くのクレジットが割り当てられる請求項１５に記載の方法。
【請求項１８】
ステップ（ｄ）で、各送信待ち行列にクレジットのしきい値量が割り当てられる請求項１２に記載の方法。
【請求項１９】
ステップ（ｄ）で、割り当てられるクレジットの量が調整可能である請求項１２に記載の方法。
【請求項２０】
ステップ（ｃ）で、受信待ち行列がラウンドロビン方式でポーリングされる請求項１２に記載の方法。
【請求項２１】
ステップ（ｅ）で、送信待ち行列がラウンドロビン方式でポーリングされる請求項１２に記載の方法。
【請求項２２】
多数の入力ポート、多数の出力ポート、およびいずれかの入力ポートで受信したプロトコルデータユニットをいずれかの出力ポートに交換する交換ファブリックを有するタイプのディジタル交換機であって、
各入力ポートに関連付けられた、１つまたは複数の送信待ち行列を有する入力バッファと、
１つまたは複数の受信待ち行列を有する出力バッファと、
それぞれ特定の出力ポートに向けられたプロトコルデータユニットを入力ポートで受信する手段と、
それぞれ特定の出力ポートに向けられたプロトコルデータユニットを記憶するように構成された送信待ち行列にプロトコルデータユニットを割り当てる手段と、
それぞれ特定の出力ポートに向けられたプロトコルデータユニットを記憶するように構成された受信待ち行列を所定の順序でポーリングする手段と、
十分に軽い負荷を有するポーリングされた受信待ち行列と同じ出力ポートに関連付けられた各送信待ち行列にクレジットを割り当てる手段と、
送信待ち行列を所定の順序でポーリングする手段と、
十分な量のクレジットを有するポーリングされた送信待ち行列から、該ポーリングされた送信待ち行列と同じ出力ポートに関連付けられた受信待ち行列にプロトコルデータユニットを送信し、送信されたプロトコルデータユニットの長さに関連して、ポーリングされた送信待ち行列に割り当てられたクレジットの量を減らす手段と、
送信されたプロトコルデータユニットを受信待ち行列から宛先出力ポートにさらに送信する手段とを含むディジタル交換機。
【発明の詳細な説明】
【０００１】
（発明の背景）
本発明は、ディジタルトラフィック交換機、特に入力バッファ／出力制御ディジタルトラフィック交換機に関する。
【０００２】
ディジタルトラフィック交換機は、多数のソースからプロトコルデータユニット（ＰＤＵ）を取り込み、それらを多数の宛先にルーティングする。そのような交換機は、ハードウェアベース、またはハードウェアおよびソフトウェアベースである。アーキテクチャは、図１に示すように一般的に表すことができる。プロトコルデータユニットは、入力ポート１〜Ｎｉｎに到着し、交換機１００を介して出力ポート１〜Ｎｏｕｔの様々なポートに交換される。
【０００３】
時折、プロトコルデータユニット間で衝突が発生する。すなわち、同じ出力ポートに向けられたプロトコルデータユニットが、複数の入力ポートに入ってくる。同じ出力ポートに向けられた複数のプロトコルデータユニットが衝突する状態を記述する２つのシナリオ、すなわち、（１）一時的な競合または衝突、および（２）持続的な競合または衝突の２つのシナリオがある。衝突を最小限にするために、バッファリングが使用される。他のプロトコルデータユニットが、バッファリングされたプロトコルデータユニットの出力ポートへの送達に必要なリソースを消費している間に、バッファは、一時的にプロトコルデータユニットを記憶する。
【０００４】
バッファリングは、「ブロッキング」として知られる別のトラフィックフローの問題を引き起こすことがある。他のプロトコルデータユニットの送達が、ブロックされたプロトコルデータユニットの出力ポートへの送達に必要なリソースを消費しているために、プロトコルデータユニットの送達が無期限に遅延している時に、ブロッキングは発生する。これを「ヘッドオブライン」（Ｈｅａｄ  ｏｆ  Ｌｉｎｅ）ブロッキングと呼ぶ。ブロッキングによって、ブロックされたプロトコルデータユニットの送達は遅延し、「ドロップ」と呼ばれるバッファでの放出待ちの間に、これらのデータユニットが書き替えられることがあるので、ブロッキングは望ましくない。
【０００５】
ブロッキングは、いくつかの異なる形式をとることができる。非同期転送モード（ＡＴＭ）交換機では、ブロッキングによって、「優先順位ブロッキング」として知られている状態、すなわち相対的に低い優先順位を有するすべてのプロトコルデータユニットが出力側に送達されなくなることがある。ＬＡＮおよびＷＡＮパケット交換機の場合、ブロッキングによって、「フローブロッキング」と呼ばれる状態、すなわち特定のパケット識別子の組を有するすべてのプロトコルデータユニットが出力側に送達されなくなることがある。ＡＴＭ、ＬＡＮまたはＷＡＮの場合、ブロッキングによって、「ポートブロッキング」と呼ばれる状態、すなわち特定の入力ポートに到着するすべてのプロトコルデータユニットが出力側に送達されなくなることがある。
【０００６】
ブロッキングを防止するために、交換機は、プロトコルデータユニットを入力ポートから出力ポートに送信するために、利用可能な制限された帯域幅を割り振るストラテジーを実施しなければならない。帯域幅割り振りの１つの重要な局面が、バッファ制御である。バッファ制御は、入力ポートと出力ポート間の経路上の他のバッファへの送達のために、プロトコルデータユニットをバッファから放出するタイミングを計る。
【０００７】
１つのバッファ制御ストラテジーは、入力側でプロトコルデータユニットをバッファリングし、出力ポートの帯域幅の利用可能性に基づいて入力バッファフローを調整する。これは「入力バッファ／出力制御交換」として知られている。入力側で受信され、出力側に向けられるプロトコルデータユニットは、入力側でバッファリングされる。出力ポートのトラフィック負荷は監視され、負荷が十分に軽くなった時にプロトコルデータユニットが出力側に放出される。出力の負荷状況に基づいて、入力でバッファリングされたプロトコルデータユニットを放出する方式は、複数の利点を有する。第１に、入力バッファリングは、プロトコルデータユニットが交換ファブリック上で送信される前に必要に応じてドロップされ、輻輳時の交換ファブリックのトラフィック負荷が軽減されることを意味する。第２に、出力で制御された放出は、出力ポートの帯域幅限度付近に交換機が設計でき、スケーラビリティが改善されることを意味する。第３に、出力で制御された放出を使用してトラフィックパターンを正常化できる、すなわち、交換機のトラフィックフローを、低トラフィック時に加速でき、高トラフィック時に減速できる。
【０００８】
入力バッファ／出力制御ＡＴＭ交換機が知られている。そのような交換機では、プロトコルデータユニットは、交換ファブリック上の放出が、通常「要求」および「許可」が「セルごとの」ベースで交換されるハンドシェーク手順によってトリガされる、固定長の「セル」である。より詳細に言えば、入力側は、着信セルをバッファリングし、入力にバッファリングされたセルの各々を放出するための要求を出力側に送信する。その要求は、通常、セルのタイプ情報、例えば、ソース入力、セルの優先順位、宛先出力などを指定する。出力側は、最終的に、宛先出力ポートへ交換ファブリック上でセルを放出する許可を発行する。許可の命令は、通常、帯域幅が利用可能になるといつでも指定タイプに基づいてペンディングの要求間で決定するアルゴリズムを実行することでなされる。そのような交換機は、入力ポート間でラウンドロビン方式で許可を発行するアルゴリズムを実行することで、ポートのブロッキングを解消してきた。例えば、米国特許第５７６８２５７号、Ｋｈａｃｈｅｒｉａｎを参照にされたい。
【０００９】
ただし、これまで優先順位ブロッキングは、持続することが許されていた。相対的に高い優先順位のセルを放出する許可は、相対的に低い優先順位のセルを放出する許可よりも前に発行されていた。したがって、交換機が相対的に高い優先順位のトラフィックで満杯になるときはいつでも、相対的に低い優先順位のトラフィックは全く送達されなかった。
【００１０】
明らかに、異なる優先順位の間における、放出する「順番」（例えば許可）のラウンドロビン方式の割り振りは意味がないであろう。優先順位付けは、本質的に平等主義の逆である。あるプロトコルデータユニットに他のプロトコルデータユニットより有利な扱いを提供する「サービス品質」ハイアラーキを構築することが考えられる。ただし、優先順位ブロッキングの持続が可能な知られている入力バッファ／出力制御ＡＴＭ交換機で使用される放出する順番を割り振る「オールオアナッシング」式の手法は、完全に満足できるものではない。異なる優先順位の間で放出する順番を割り振るためのより洗練された方式が正当化される。そのような方式は、フローブロッキングの類似の問題を防止するために、入力バッファ／出力制御ＬＡＮおよびＷＡＮパケット交換機においても正当化される。問題を一般化して述べると、異なるサービス品質を享受する資格があるプロトコルデータユニットの間で順番を割り振る、よりよい方式が入力バッファ／出力制御交換機に必要である。
【００１１】
（発明の概要）
本発明は、最も基本的な特徴において、入力バッファ／出力制御交換機において、異なるサービス品質を享受する資格があるプロトコルデータユニットのグループの間で放出する順番を確定的に割り振るクレジットベースの方式を提供する。
【００１２】
一態様では、入力バッファ／出力制御交換機は、各々が１つまたは複数の送信待ち行列に関連付けられた１つまたは複数の入力ユニットと、各々が１つまたは複数の受信待ち行列に関連付けられた１つまたは複数の出力ポートとを有する。入力ユニットは、共用交換ファブリックを介して、出力ポートにデータを送信する。異なる出力ポートに向けられた、または異なるサービス品質を享受する資格がある着信プロトコルデータユニットは、異なる送信待ち行列に割り当てられる。受信待ち行列のトラフィック負荷は監視される。受信待ち行列のトラフィック負荷が十分に軽くなるといつでも、受信待ち行列は、入力ユニットにステータスメッセージを送信することで「支払い日（ｐａｙ  ｄａｙ）」を宣言する。「支払い日」宣言に応答して、入力ユニットは、プロトコルデータユニットを、その宣言している受信待ち行列に送信する送信待ち行列に「支払い小切手（ｐａｙｃｈｅｃｋｓ）」を配布する。異なる送信待ち行列に配布された「支払い小切手」は、送信待ち行列に割り当てられたプロトコルデータユニットのサービス品質の資格によって異なるクレジット量を含む。送信待ち行列は、プロトコルデータユニットを受信待ち行列に放出するために、所定の順序でポーリングされる。ポーリング時に送信待ち行列が十分なクレジット量を有する場合、送信待ち行列は、受信待ち行列にプロトコルデータユニットを放出し、送信待ち行列によって蓄積されたクレジット量は、放出されたプロトコルデータユニットの長さに関係して低減される。ポーリング時に送信待ち行列が十分なクレジット量を有しない場合、送信待ち行列は、受信待ち行列にプロトコルデータユニットを放出せず、その蓄積されたクレジットを保持する。「支払い小切手」の形で送信待ち行列に配布されるクレジット量は、相対的に高いサービス品質を享受する資格があるプロトコルデータユニットを記憶する送信待ち行列が、相対的に大きな量のクレジットを配布され、相対的に低いサービス品質を享受する資格があるプロトコルデータユニットを記憶する送信待ち行列が、相対的に小さいクレジットしきい値の量を配布されるように、構成されることができる。このようにクレジットを割り振ることで、サービス品質のハイアラーキは守られ、ブロッキングは防止される。
【００１３】
別の態様では、ＬＡＮまたはＷＡＮパケット交換機における実施の場合、すべての送信待ち行列について標準の「バースト」カウントが、選択され、送信待ち行列に割り当てられる。該「バースト」カウントは、所定の順序で、送信待ち行列の「順番」を送出する。
送信待ち行列は、「バースト」カウントが次に放出されるパケットの長さが残りの「バースト」カウントを超えるレベルまで下がるまで、プロトコルデータユニットを放出する。割り当てられた「バースト」カウントの残りの部分は、もしあれば、記憶され、送信待ち行列の次の放出する「順番」において、付加的な「バースト」として割り当てられる。それにより、持続動作期間の送信待ち行列のデータ放出レートを、放出のために提示されるプロトコルデータユニットの長さから独立させることができる。
【００１４】
さらに別の態様では、受信待ち行列は、共用出力バッファ内で動的に構成されて不均一のトラフィックパターンに対応する。
【００１５】
本発明の上記の、およびその他の目的は、以下に概説する添付図面に関連する以下の簡単な説明を参照することでよりよく理解できよう。本発明の実際の範囲が首記の特許請求の範囲に記載されていることは当然である。
【００１６】
（好ましい実施形態の詳細な説明）
図２を参照すると、本発明を組み込むディジタルトラフィック交換機の一般的なアーキテクチャが示されている。多数の入力ユニット２１０（１−Ｎ）および多数の出力ユニット２２０（１−Ｎ）が交換ファブリック２３０を介して結合される。あらゆる入力ポートがあらゆる出力ポートと通信できるように、各入力ユニットは１つまたは複数の関連する入力ポートを有することができ、各出力ユニットは１つまたは複数の関連する出力ポートを有することができる。所要の瞬間に、入力ユニット２１０（１−Ｎ）のサブセット（またはすべて）が、出力ユニット２２０（１−Ｎ）のサブセット（またはすべて）に向けられたディジタルトラフィックを受信する。したがって、ディジタルデータトラフィックは、左から右、すなわち、入力ユニット２１０（１−Ｎ）から出力ユニット２２０（１−Ｎ）に流れるように想像できる。データトラフィックは、離散的なプロトコルデータユニットで送信される。交換機で動作するプロトコルによって、プロトコルデータユニットは、可変長のパケットまたは固定長のセルのどちらかになり得る。
【００１７】
図３は、代表的な入力ユニット３１０と代表的な出力ユニット３４０の間の交換ファブリック３３０を介した接続を分離する。入力ユニット３１０内に、異なる出力ポートに向けられた、または異なるサービス品質を享受する資格がある、着信プロトコルデータユニットを記憶する異なる送信待ち行列を有する入力バッファ３１２がある。Ｌ個の異なるサービス品質をサポートし、それぞれがＰ個の出力ポートをサポートするＵ個の出力ユニットを有する交換機の場合、入力バッファは、Ｕ×Ｐ×Ｌ個の送信待ち行列（物理的には入力バッファ内に常駐する）を有する。また、着信プロトコルデータユニットを出力ポートおよびサービス品質資格ごとに異なる送信待ち行列に割り当て、異なる送信待ち行列について利用可能なクレジットを監視し、プロトコルデータユニットを入力バッファ３１２から出力バッファ３３２に放出する、入力バッファ制御装置３１４もある。サービス品質は、交換特性の所定の組を参照することで、着信プロトコルデータユニットについて決定できる。ＬＡＮまたはＷＡＮパケット交換機の場合、確定的なサービス品質特性は、プロトコルデータユニットのレイヤ２（メディアアクセス）、レイヤ３（ネットワーク）およびレイヤ４（トランスポート）のヘッダにある制御情報およびルーティング情報を、単独でまたは組み合わせて無制限に含むことができる。ＡＴＭセル交換機の場合、確定的なサービス品質特性は、入力ポートおよびセルの優先順位を無制限に含むことができる。入力バッファ制御装置３１４内で、利用可能なクレジット記憶装置３１６は、異なる送信待ち行列の現在のクレジット値を保持する。Ｕ×Ｐ×Ｌ個の送信待ち行列をサポートする入力ユニットの場合、それぞれがＵ×Ｐ×Ｌ個の送信待ち行列の異なる１つのクレジット値を記憶するＵ×Ｐ×Ｌ個の利用可能なクレジット記憶装置がある。
【００１８】
交換ファブリック３３０内には、異なる出力ポートに向けられたプロトコルデータユニットを記憶する異なる受信待ち行列を有する出力バッファ３３２がある。それぞれがＰ個の出力ポートをサポートするＵ個の出力ユニットを有する交換機の場合、出力バッファは、Ｕ×Ｐ個の論理受信待ち行列（物理的には出力バッファ内に常駐する）を有する。交換ファブリック３３０内には、異なる受信待ち行列のトラフィック負荷を監視し、それに応じて発行される「支払い日」宣言を生じさせる、出力フロー制御装置３３４もある。出力フロー制御装置３３４は、異なる受信待ち行列の現在のトラフィック負荷を監視するために、クレジット調整記憶装置３３６を有する。Ｕ×Ｐ個の受信待ち行列をサポートする交換ファブリックの場合、それぞれが受信待ち行列の異なる１つの負荷値を保持するＵ×Ｐ個のクレジット調整記憶装置がある。
【００１９】
出力ユニット３４０内には、異なる出力ポートに向けられたプロトコルデータユニットを記憶する異なる出力ＦＩＦＯ３４２がある。
【００２０】
好ましい実施形態では、出力バッファ３３２のリソースは、出力フロー制御装置３３４における空きバッファポインタリスト手段によって、動的に割り振られる。出力バッファ３３２内の利用可能なアドレス空間へのポインタは、プロトコルデータユニットが出力バッファ３３２に書き込まれる時に空きリストの先頭から引き出れ、プロトコルデータユニットが出力バッファ３３２から読み出される時に空きリストの末尾に戻される。同じ出力ポートに向けられたプロトコルデータユニット（またはその一部）を保持するアドレス空間は、リンクされて論理受信待ち行列を形成する。受信待ち行列が動的に構成される共用出力バッファを使用することで、出力ポートが出力バッファ３３２のその持分以上を利用できるようにすることで、有利には不均一のトラフィックパターンに対応することができる。各出力ユニットが専用の出力バッファと出力フロー制御装置を有する専用の出力バッファリング環境も可能であることは当然である。その場合、各出力バッファは、Ｐ個の出力ポートに対応するＰ個の受信待ち行列とＰ個のクレジット調整記憶装置を有するであろう。そのような専用の出力バッファリング環境は、共用出力バッファリング方式と比べて一定のスケーラビリティの利点を有することができる。
【００２１】
入力ユニット３１０と交換ファブリック３３０は、ステータスライン３１８およびデータバス３２０上で通信する。ステータスライン３１８は、出力フロー制御装置３３４から入力バッファ制御装置３１４に「支払い日」宣言を送信するために使用される。各「支払い日」宣言は、その「支払い日」宣言が関連する受信待ち行列を識別するのに十分な情報を含む。「支払い日」宣言は、受信待ち行列のトラフィック負荷が所定のしきい値以下であることが検出された場合に送信される。好ましい実施形態では、トラフィック負荷は、その受信待ち行列に対応する出力ポートへの送達を待っている受信待ち行列内のデータ量によって測定される。「支払い日」宣言は、様々な方法で送信できる。好ましい実施形態では、ステータスライン３１８は、各クロック周期で、最大１つのマルチビットの「支払い日」宣言を送信するマルチビットバスである。別の実施形態では、各受信待ち行列に、ラインをハイ状態にするまたはしないことで「支払い日」宣言を搬送するための専用の１ビットラインを割り当てることができる。さらに別の実施形態では、受信待ち行列を「支払い日」宣言を搬送するための複数の共用１ビットラインの１つに割り当てることができ、ラインを共用するその受信待ち行列に、割り当てられたタイムスロットでラインをハイ状態にするまたはしないことで「支払い日」宣言を搬送するための、反復タイミング周期内の異なるタイムスロットを割り当てることができる。受信待ち行列の数が「支払い日」宣言を搬送するための様々な利用可能な技法の相対的な適合性を決定できることは当然である。データバス３２０は、送信待ち行列から受信待ち行列にプロトコルデータユニットを送信するのに使用される。
【００２２】
出力フロー制御装置３３４は、プロトコルデータユニットが、入力バッファ３１２から出力バッファ３３２に、また出力バッファ３３２から出力ＦＩＦＯ３４２に送信される時に、適当な負荷値を更新する。より詳細に言えば、プロトコルデータユニットが出力バッファ３３２内の受信待ち行列で受信されると、出力フロー制御装置３３４は、受信されたプロトコルデータユニットの長さに関連して、対応する受信待ち行列の保持されている負荷値を増やす。プロトコルデータユニットが出力バッファ３３２内の受信待ち行列から送信されると、出力フロー制御装置３３４は、送信されたプロトコルデータユニットの長さに関連して、対応する受信待ち行列の保持されている負荷値を減らす。このようにして、出力フロー制御装置３３４は、出力バッファ３３２内の様々な受信待ち行列上のトラフィック負荷の正確な監視を動的に維持する。プロトコルデータユニットの長さと負荷値の関係は正比例でよく、したがって、受信待ち行列に書き込まれた各Ｎビットデータブロックは負荷値を１だけ増やすことができ、受信待ち行列から読み出された各Ｎビットデータブロックは負荷値を１だけ減らすことができる。
【００２３】
同様に、入力バッファ制御装置３１４は、出力フロー制御装置３３４から「支払い日」宣言が受信される場合、及びプロトコルデータユニットが入力バッファ３１２から出力バッファ３３２に送信される場合、適当なクレジット値を更新する。より詳細に言えば、「支払い日」宣言が受信されると、入力バッファ制御装置３１４は、プロトコルデータユニットを「支払い日」宣言を送信した受信待ち行列に送信する送信待ち行列のクレジット値を増やす。クレジット値は、その送信待ち行列に割り当てられたプロトコルデータユニットの所定のサービス品質資格に関連して増やされる。配布されるクレジットの量は、相対的に高いサービス品質を享受する資格があるプロトコルデータユニットを割り当てられる送信待ち行列が相対的に多数のクレジットを配布され、相対的に低いサービス品質を享受する資格があるプロトコルデータユニットを割り当てられる送信待ち行列が相対的に小さいしきい値のクレジット数を配布されるように構成される。プロトコルデータユニットが送信待ち行列から出力バッファ３３２内の受信待ち行列に送信されると、入力バッファ制御装置３１４は、送信されたプロトコルデータユニットの長さに関連して、対応する送信待ち行列のクレジット値を減らす。このようにして、入力バッファ制御装置３１４は、入力バッファ３１２内の様々な送信待ち行列によって保持されるクレジットを正確に監視することができる。プロトコルデータユニットの長さとクレジット値の関係は正比例でよく、したがって、送信待ち行列から読み出された各Ｎビットデータブロックは、クレジット値を１だけ減らすことができる。
【００２４】
交換機で動作する一般バッファ制御ストラテジーについて代表的な入力ユニット３１０と交換ファブリック３３０の対話を参照しながら以下に説明する。出力フロー制御装置３３４は、受信待ち行列をラウンドロビン方式でポーリングする。「支払い日」宣言は、現在の受信待ち行列の負荷が十分に軽くなると、入力バッファ制御装置３１４に送信される。受信待ち行列の負荷値は、クレジット調整記憶装置３３６における受信待ち行列の１つに保持される。好ましい実施形態では、受信待ち行列の負荷は、所定数のクロック周期にわたる平均負荷値が所定のしきい値以下になった時に、十分に軽いと見なされる。「支払い日」宣言に応答して、入力バッファ制御装置３１４は、適当な送信待ち行列に「支払い小切手」を配布する。プロトコルデータユニットをその宣言をしている受信待ち行列に向けて送る各送信待ち行列は、「支払い小切手」を配布される。ただし、すべての「支払い小切手」が、同じクレジット量を有するわけではない。「支払い小切手」内のクレジット量は、その送信待ち行列に割り当てられたプロトコルデータユニットのサービス品質資格と相関する。入力バッファ制御装置３１４は、適当な送信待ち行列に対して保持されたクレジット値を「支払い小切手」内に示されたクレジット量だけ上方に改訂することで、利用可能なクレジット記憶装置３１６内に「支払い小切手」を預ける。一方、入力バッファ制御装置３１０は、着信プロトコルデータユニットに対して、出力ポートとサービス品質資格を決定し、それに応じて、着信プロトコルデータユニットは、送信待ち行列に割り当てられる。入力バッファ制御装置３１０は、送信待ち行列をラウンドロビン方式でポーリングする。プロトコルデータユニットは、現在の送信待ち行列が十分に大きいクレジット量を有する場合、現在の送信待ち行列から適当な受信待ち行列に放出される。プロトコルデータユニットの受信に応答して、出力バッファ制御装置３２２は、適当な受信待ち行列に対して保持された負荷値を、受信されたプロトコルデータユニットの長さだけ上方に改訂する。一方、プロトコルデータユニットは、出力ポートの帯域幅が利用可能になると、受信待ち行列から出力ＦＩＦＯ３４２を介して出力ポートに所定の順序で送信される。
【００２５】
基本バッファ制御ストラテジーの様々な発展形態が可能である。ただし、基礎的なレベルでは、この基本バッファストラテジーは、送信待ち行列間におけるプロトコルデータユニットを放出する「順番」が、完全に確定的な形で割り当てることができると言う点で従来技術に対して大幅な進歩を示していると考えられている。したがって、好ましい実施形態では、クレジットは、サービス品質の差が十分に尊重されることを保証しながらブロッキングを防止する形で配布できる。この利点は、相対的に高いサービス品質を享受する資格があるプロトコルデータユニットを割り当てられた送信待ち行列に、相対的に低いサービス品質を享受する資格があるプロトコルデータユニットを割り当てられた送信待ち行列よりも多数のクレジットを転送する一方で、最も低いサービス品質を享受する資格があるプロトコルデータユニットを割り当てられた送信待ち行列にクレジットのしきい値の数を割り当てることで達成できる。
【００２６】
この基本バッファ制御ストラテジーの好ましい一発展形態は、「支払い小切手」の配布の間に満了する所定数のクロック周期を必要とし、任意の１つの送信待ち行列に対して「支払い小切手」ごとに配布されるクレジット数を賢明に制限することで、最大転送レートを最大限に課す。
【００２７】
基本バッファ制御ストラテジーの別の好ましい発展形態は、「バースト」実施の放出を介して、ＬＡＮまたはＷＡＮパケット交換機における公平さを改善する。すべての送信待ち行列について標準の「バースト」カウントが、選択され、送信待ち行列に割り当てられる。この「バースト」カウントが、ラウンドロビン順で送信待ち行列の「順番」を放出する。送信待ち行列は、次に放出されるパケットの長さが残りの「バースト」カウントを超えるレベルまで「バースト」カウントが下がるまで、プロトコルデータユニット（この場合パケット）を放出する。割り当てられた「バースト」カウントの残りの部分は、もしあれば、その送信待ち行列に対する保持された残りの「バースト」記憶装置に記憶され、送信待ち行列の次に放出する「順番」において、付加的な「バースト」として再度割り当てられる。以降の「順番」において、送信待ち行列は、「バースト」カウントと以前の「順番」からの残りの「バースト」の合計が下がるまで、パケットを放出する。好ましくは、選択された「バースト」カウントは、各「順番」ごとに、少なくとも１つのパケットが放出されることが保証できる程度の大きさである。上述のストラテジーを実施することで、持続動作期間の送信待ち行列のデータ放出レートを、放出のために提示されるパケットの長さから独立させることができる。
【００２８】
図４を参照すると、「支払い日」を宣言する出力フロー制御装置によって実施される負荷制御アルゴリズムが示されている。ラウンドロビン順に現在の受信待ち行列が選択され（４１０）、その受信待ち行列の現在のトラフィック負荷が検討される（４２０）。現在のトラフィック負荷が十分に軽い場合、「支払い日」が宣言される（４３０）。現在のトラフィック負荷が十分に軽いか否かにかかわらず、現在の受信待ち行列が最後の受信待ち行列であるか否かを決定するために検査がされる（４４０）。そうである場合、アルゴリズムは終了する（４５０）。そうでない場合、ラウンドロビン順に次の受信待ち行列が選択され（４１０）、ステップ４２０が繰り返される。
【００２９】
図５を参照すると、プロトコルデータユニットを放出する入力バッファ制御装置によって実施される放出制御アルゴリズムが示されている。ラウンドロビン順に現在の送信待ち行列が選択され（５１０）、その送信待ち行列の現在のクレジット値が検討される（５２０）。現在のクレジット値が十分に高い場合、プロトコルデータユニットは放出され（５３０）、クレジット値は放出されたプロトコルデータユニットの長さに関連して低減される（５４０）。現在のクレジット値が十分に高いか否かにかかわらず、現在の送信待ち行列が最後の送信待ち行列であるか否かを決定するために検査がされる（５５０）。そうである場合、アルゴリズムは終了する（４５０）。そうでない場合、ラウンドロビン順に次の送信待ち行列が選択され（５１０）、ステップ５２０が繰り返される。
【００３０】
このアルゴリズムは汎用マイクロプロセッサを使用してソフトウェア内で実施できる。より好ましくは、このアルゴリズムは、特定用途向け集積回路（ＡＳＩＣ）の一部としてハードウェア内で実施できる。後者の場合、図４および５の流れ図は、プログラム命令の実行ではなく、ＡＳＩＣの論理演算を記述する。
【００３１】
送信待ち行列の間のラウンドロビンポーリング順以外のポーリング順も可能である。例えば、送信待ち行列は、それに割り当てられるプロトコルデータユニットの相対的な優先順位に従ってポーリングされることができ、その結果、相対的に高い優先順位のプロトコルデータユニットを割り当てられた送信待ち行列が、もはや十分なクレジットを有しなくなるまで、相対的に高い優先順位のプロトコルデータユニットが相対的に低い優先順位のプロトコルデータユニットより前に放出される。そのような構成では、相対的に高い優先順位のプロトコルデータユニットを割り当てられた送信待ち行列に、上述の形で最大転送レート限界値を課すことによって、優先順位ブロッキングを防止することができる。
【００３２】
また、「支払い日」を宣言する、より先進的な方式も実施できる。例えば、複数の優先順位に特有の複数のしきい値が、各受信待ち行列に割り当てられることができる。その際、より高い優先順位により高いしきい値が割り当てられる。負荷値が少なくとも１つのしきい値を超えているがすべてのしきい値を超えてはいない時、選択的な「支払い日」が、その結果、そのしきい値が超えられていない優先順位のプロトコルデータユニットが割り当てられた受信待ち行列に関連付けられた送信待ち行列にだけ「支払い小切手」を配布されるように、宣言されることができる。
【００３３】
以上から、本発明はその精神または基本的な特徴から逸脱することなく本発明を他の特定の形式で具体化できることを当業者は理解するであろう。したがって、本発明はすべての面で例示的であって限定的ではないと考えられる。本発明の範囲は、首記の特許請求の範囲に記載され、それと同等物の意味と範囲内に入るすべての変更はそれに含まれるものと意図される。
【図面の簡単な説明】
【図１】  ディジタルトラフィック交換機の一般的なブロック図である。
【図２】  本発明が使用されるディジタルトラフィック交換機のブロック図である。
【図３】  出力フロー制御装置と入力バッファ制御装置間の制御フロー、ならびに入力バッファと出力バッファ間のデータフローを詳細に示すブロック図である。
【図４】  「支払い日」を宣言する好ましい実施形態で使用される負荷制御アルゴリズムの流れ図である。
【図５】  放出プロトコルデータユニットを送信待ち行列から受信待ち行列に順序付ける好ましい実施形態で使用される放出制御アルゴリズムの流れ図である。
【図１】
0004159253.tif 000002
【図２】
0004159253.tif 000003
【図３】
0004159253.tif 000004
【図４】
0004159253.tif 000005
【図５】
0004159253.tif 000006