(57)【特許請求の範囲】
【請求項１】
データ交換装置であって、
入力ポートであって、そこへの複数の入力接続を有する入力ポートと、
複数の出力ポートへの接続のための手段と、
データの送信に対して与えられるべき優先順位を表すパラメータ値を入来データに割り当てる手段であって、入来データに割り当てられた前記パラメータ値が、そのデータを受ける入力接続に割り当てられた優先順位のレベルと送信をまだ待機しているその入力接続からのデータ・セルの数とによって決定される、手段と、
既知のポインタによって指示されるアドレスで前記入来データを記憶する入力バッファ・メモリと、
前記入来データに割り当てられたポインタを既知の位置に記憶する第１のメモリと、
割り当てられたパラメータ値によってアドレス可能なアレイに前記既知の位置を記憶する第２のメモリと、を含み、
データを送信すべきときに、前記第２のメモリが、それらの優先順位から次に送信されるべきデータに関連したポインタを前記第１のメモリから引き出すのに用いられ得、
まだ送信を待機している入力接続からのセルの数がスレッショルドを越えると、その接続でのさらなる入来データに関連したポインタが前記第１のメモリにフラグを付けた位置で記憶され、かつ、全てのこのようなさらなるデータが先入れ先出しプロセスに従って送信される、データ交換機。
【請求項２】
前記ポインタが、同じ割り当てられたパラメータ値を有する他のデータと関連するポインタの位置にリンクされた位置で前記第１のメモリに記憶され、前記第２のメモリが、その後の割り当てられたパラメータ値を有するデータと関連したポインタの位置へのアクセスを可能とする指示子を記憶する、請求項１記載のデータ交換装置。
【請求項３】
どのセルが次の送信のためのものであるかを決定する出力ブロックが、前記第２のメモリにわたって循環し、入来データと関連するポインタの位置に対する指示子が、割り当てられたパラメータ値と前記入来データを受けたときに前記出力ブロックによって到達する前記第２のメモリの位置とによって決定される前記第２のメモリ内の位置に記憶される、請求項１記載のデータ交換装置。
【請求項４】
前記第１および第２のメモリが、種々の出力ポートに関連した個別のそれぞれのリストからなる、請求項１記載のデータ交換装置。
【請求項５】
入力接続からＡＴＭ交換装置の出力ポートへデータを交換する方法であって、
各データセルを到着後および送信前にバッファ・メモリに、ポインタによって指示されるアドレスで記憶し、
入力接続に到着した各データ・セルに、そのデータの送信に対して与えられるべき優先順位を指示するパラメータ値を割り当て、ここで、前記パラメータ値が、データを受ける前記入力接続に割り当てられた優先順位のレベルと送信を待機しているその接続からのデータ・セルの数とに基づいて割り当てられ、
前記ポインタを第１のメモリに既知の位置で記憶し、
前記割り当てられたパラメータ値によりアドレス可能となるように第２のメモリに前記既知の位置を記憶し、
それらの優先順位から次に送信されるべきデータに関連したポインタを前記第１のメモリから引き出すように前記第２のメモリを使用することによってデータを送信し、
送信を待機している接続からのデータ・セルの数がスレッショルドを越えると、その接続でのさらなる入来データに関連したポインタをフラグを付けた前記第１のメモリ内の位置に記憶して、前記さらなるデータが先入れ先出し基準で送信される、方法。
【請求項６】
同じ割り当てられたパラメータ値を有する他のデータと関連するポインタの位置にリンクされた位置で前記第１のメモリに前記ポインタを記憶し、その後の割り当てられたパラメータ値を有するデータと関連したポインタの位置へのアクセスを可能とする指示子を前記第２のメモリに記憶する、請求項５記載の方法。
【請求項７】
どのセルが次の送信のためのものであるかを前記第２のメモリにわたって循環することによって決定し、入来データと関連するポインタの位置に対する指示子を、前記割り当てられたパラメータ値と前記入来データを受けたときに送信サイクルによって到達された前記第２のメモリ内の位置とによって決定される前記第２のメモリ内の位置に記憶する、請求項５記載の方法。
【請求項８】
前記第１および第２のメモリを前記種々の出力ポートに関連した個別のそれぞれのリストに分割する、請求項５記載の方法。
【発明の詳細な説明】
技術分野
本発明は、交換装置に関し、より詳細には、入来トラフィックを種々の入力で取り扱わせる態様で公平性を与えるようにするＡＴＭ交換装置に関する。
関連技術の説明
パケットベースのトラフィック用の統合サービス網のユーザにネットワーク・リソースを割り当てる問題に対する１つの提案された解決法は、重み付け公平待ち行列化として知られており、到着データ・パケットは、それらがプロセッサ・シェアリング・システムである程度の公平性をもって再送信されるように、再順序決めされる。例えば、ＰａｒｅｋｈおよびＧａｌｌａｇｈｅｒ著，「統合サービス網における流れ制御に対するプロセッサ・シェアリング・アプローチ：単ノードの場合」，ネットワーキングに関するＩＥＥＥ／ＡＣＭ会報，第１巻，第３号，１９９３年６月を参照されたい。しかしながら、このようなシステムは、構成化するには極めて複雑となってしまう。
米国特許第５，４５５，８２５号は、待ち行列化システムを含むデジタル通信網用の交換機を開示している。入来セルまたはパケットが到着すると、それらには所望のスケジュール化アルゴリズムに従って計算された数値タグが与えられ、待ち行列に配置される。ＶＬＳＩ構成化のために設計された待ち行列化および検索モジュールは、それらタグに基づいて送信用のセルまたはパケットを選択する。このようにして、その待ち行列が検索され、各着信先に対して、最も小さなタグ値を有するセルが送信のために選択される。しかしながら、このような検索は時間が掛かるものとなってしまう。
発明の概要
本発明は、種々の入力接続の間で公平な待ち行列化を与える交換装置を提供しようとする。一態様において、これは受信入力データを関連ポインタと共にメモリに記憶することによって達成され、このポインタはデータの送信に対して与えられるべき優先順位を指示する。同一の送信をなす呼出と共にグループ化するアレイを通してポインタがアクセスされ、長い検索の必要性が回避される。他の態様においては、送信を機している単一の入力接続からのセルの数がスレッショルド数を越えるまで、公平な待ち行列化が与えられる。その入力接続からのさらなるセルは、公平性なしの態様で取り扱われる。
【図面の簡単な説明】
図１は、入力バッファリングを行う交換装置の回路図である。
図２は、本発明に従って交換装置の回路図である。
図３は、受信セルをバッファリングするプロセスを示すフローチャートである。
図４は、１つの時間点での送信のために利用可能なセルの概略図である。
図５は、本発明の他の態様による交換装置の一部の回路図である。
図６は、図５の装置の制御を時分割多重化する方法の図である。
図７は、本発明による他の交換装置の回路図である。
好適実施例の詳細な説明
図１は、本発明が関連する形式の交換装置を示す。交換装置２は、Ｎ個の入力ポート４．１，４．２，・・・，４．Ｎを有し、それぞれは関連した入力バッファを備えている。同様に、交換装置２は、Ｎ個の出力ポート６．１，６．２，・・・，６．Ｎを有し、それぞれは関連した出力バッファを備えている。各入力バッファは、それぞれが出力ポートのそれぞれの１つに関連したＮ個の論理バッファに分割されているものと考えることができる。そのため、ある特定の入力ポートで受けた入力セルは、このセルを意図する出力ポートに関連したその入力ポートの入力バッファに記憶される。しかしながら、実際には、各入力ポートでの種種の論理バッファは、バッファの使用度を上げるために、その入力ポートに関連した単一の入力バッファを共有する。
本発明は、各出力ポートの出力能力が種々の入力ポートの間で共有されるような態様の公平性を向上することに関する。したがって、ある特定の出力ポートに対する多量のトラフィックを発生する単一の接続がかなりの時間の間その出力ポートの能力の全体を占めてしまう状況を回避することが望まれる。このような状況において、１つの接続に到着するセルが話中の接続からより早く到着したセルの前に送信されることができるようにすることが望まれる。
図１に示される交換装置に関連して、この公平性を達成する１つの態様は、１つの接続当り１つの論理バッファを規定し、かつ、各スケジューリング・サイクルの間に１つのセルを各非空きバッファから取るようにすることとなろう。このようなシステムは、「ラウンド・ロビン」スケジューリングとして知られている。しかしながら、これは、交換装置が入力ポートで出力ポート当り保持される現存の論理待ち行列内に多数の論理待ち行列を維持しなければならないことを意味する。例えば、確立される接続の数は、数千のオーダーとなることがある。
本発明によれば、別態様の手法は、入力バッファに記憶されている各接続からのセルの数のトラック状態を保持することによってセルが入力バッファから送られる順序を再配列することである。これは、各セルを受ける際にある処理を必要とするにせよ、より大きな公平性が達成され得るようにする。本明細書には、所望の程度の公平性を達成するために、実行される幾つかのセル取扱処理手順が記載されるであろうことに留意すべきである。しかしながら、当業者に周知の他のセル取扱処理手順も同様行われることにも留意すべきである。また、記載されているような発明はＡＢＲ（利用可能ビット伝送速度）およびＶＢＲ（可変ビット伝送速度）トラフィックと共に使用するのにふさわしいということにも留意すべきである。連続ビット伝送速度（ＣＢＲ）トラフィックは遅延なしで取り扱われなければならず、そのため、それは独立したストリームとして装置を通るようにさせるようにすることができる。別態様として、このようなトラフィックは、それが遅延を何ら受けずに送信されるようにするために、最も高い可能な優先順位が与えられるようにされてもよい。
図２は、本発明による入力交換装置のブロック図である。この装置は、受信セルに与えられるべき優先順位を表す「グループ・シーケンス番号」を計算する、ブロック２４に接続された入力接続２２を有する。ルックアップ・テーブル２６がブロック２４に接続されており、グループ・シーケンス番号の計算のために必要な情報を記憶しており、順番にカウンタ・ブロック２８から情報を受ける。入力セルはバッファ・メモリ３０に記憶される。バッファ・メモリ３０は、１つの特定の入力ポートへの接続の全ての間で共有される。また、ブロック２４はメモリ３２に接続されている。メモリ３２は、多数のリスト３２．１，３２．２，・・・，３２．Ｎを含んでおり、各リストは装置の１つの特定の出力ポートに関連している。このメモリ３２は第２のメモリ３４に接続されている。第２のメモリ３４もまた、同様に、出力ポートと関連するリスト３４．１，３４．２，・・・，３４．Ｎを含んでいる。第２のメモリ３４およびバッファ・メモリ３０は出力装置３６に接続されている。出力装置３６は交換装置を介してセルを送信するように接続されている。また、出力装置３６はカウンタ装置２８にも接続されている。図２の回路図において、種々のメモリはそれらの機能に従って別々に示されている。しかしながら、それらが物理的に個別であってもよく、便宜的に同じ物理的装置の一部であってもよいことを理解されたい。
図３は、本発明に従って入力交換装置によって受信セルが記憶されるプロセスを示すフローチャートである。第１のステップＳ１は、入力ポートの１つの特定の接続ｉでのセルの受信である。セルの受信に引続いて、ステップＳ２において、その特定の接続に関連する重みファクタｗiがブロック２６から取り出される。同様に、ステップＳ３において、その接続に到着したバッファ・メモリに記憶されているセルの現在数ｎiもブロック２６から受信される。
重みファクタは各入力接続に対してユーザによって定義されてもよいパラメータであり、ユーザが特定の接続に到着するセルに対してより高い優先順位を与えることができるようにする。
本発明の目的の１つは、入来セルをそれが可能な程度まで「公平な」態様で取り扱わせることである。すなわち、大きなバーストのセルがある接続は、交換装置の能力を独占するようには許可されない。しかし、その代わりに、それらのセルは、稼働率が小さい接続からの他の後の到着セルが送信された後に取り扱われるようにすることができる。しかしながら、実際上、完全な公平性を達成することは、交換装置の選別機構がこの際に無制限能力を必要とすることになるため、不可能である。その代わりに、１つの特定の接続から到着したセルの数があるレベルを越えると、「公平性なし」態様でさらなるセルが取り扱われるように、あるパラメータがセットされる。
また、その限定的に、装置が取り扱う能力を越える場合には、幾つかのセルを放棄する必要があるかもしれないことを言及しなければならない。その能力をどの程度大きくすべきか、およびセルが公平性なしの態様で取り扱われなければならない前にどの程度多くのセルが到着している必要があるかは、設計的選択事項である。
実際上、好適実施例において、これは、あるセルが公平性なしの態様で取り扱われなければならないときにはフラグｎｆを“１”の値にセットし、そうでなければフラグｎｆを“０”にセットすることによって達成される。一旦フラグが“１”にセットされたならば、その特定の接続からのセルの全てが送信されてしまった状態に交換装置が達成したときに、その接続からのセルが公平な態度で再度取り扱われるようにする“０”にフラグが単にリセットされることになる。したがって、ステップＳ４において、ｎｆフラグの値がブロック２６から取り出される。次いで、ステップＳ５で、ｎi＝０かどうかが決定される。そうであれば、ｎｆフラグはステップＳ６で“０”にリセットされる。
いずれの場合でも、次いで、その接続からのバッファリングされたセルの数ｎiがプリセット・スレッショルド値Ｎmaxを越えているかどうかが、ステップＳ７において試験される。そうであれば、ｎｆフラグはステップＳ８でセットされる。
いずれの場合でも、ｎiの現在値はステップＳ９で“１”だけインクリメントされ、次いで、セルはステップＳ１０でバッファ・メモリ３０のアドレスＡikに記憶される。次いで、アドレスＡikに対するポインタＰikがステップＳ１１において取り出される。
ステップＳ１２において、セルが公平な態様または公平性なしの態様で処理されるべきかどうかが決定される。これは、ｎｆフラグがその接続に対してセットされているかどうかを決定することによって行われる。フラグがセットされていなければ、グループ・シーケンス数ｇがステップＳ１３においてｎiおよびｗiの積として計算される。グループ・シーケンス数は、特定のセルに対して与えられるべき優先順位の指示として働く。
他方、ｎｆフラグがセットされていた場合には、ステップＳ１４で、グループ・シーケンス数ｇがその最大値ｇmaxにセットされる。
セルが公平に取り扱われるべきかどうかにより、グループ・シーケンス数ｇと呼出ポインタｐikと（それがセットされていた場合は）ｎｆフラグとは、ステップＳ１５において、メモリ・アレイに、すなわち最後にはさらなるポインタを記憶するグループ・ポインタ・ブロック３２に移される。
図２に概略的に示されるように、ブロック３２はＮ個のリストＬＧＰj（ｊ＝１，２，・・・，Ｎ）からなり、各リストは交換装置の各出力ポート用である。各リスト内に、検索パラメータｋのあらゆる可能な値と関連する３つのポインタが記憶されている。送信のためのセルを取り出すときに、送りブロックは送信されるべきセルの指示としてパラメータｋを用いてアレイ３２を通して循環を行う。したがって、バッファ・メモリ内のセルに対するポインタｐikは、ＬＯＰメモリ３４のＬＧＰアレイ３２からアクセス可能なアドレスに記憶される。セルの公平な取扱いを可能にするために、各ＬＯＰメモリ・アドレスは、各場合において、セルを受けたときに検索パラメータｋの値（これはこのときに送信されているセルと関連した位置の指示である。）とそのセルに与えられるべき優先順位の指示であるｇの値とに依存する位置で、アレイ３２に記憶される。これら位置は、（（ｇ＋ｋ）  ｍｏｄ  Ｍ）、すなわち（ｇ＋ｋ）または（ｇ＋ｋ）がＭ（アレイのサイズ）を越えるときには（ｇ＋ｋ−Ｍ）として計算される。これは、本明細書で簡略化のため、（ｇ＋ｋ）として一般的に言及される。
したがって、検索パラメータｋの各値に対して、ブロック３２の各リストには、３つのポインタが記憶されている。第１のものは、ｋの特定の値と関連した第１の受信セル・ポインタのＬＯＰメモリ３４内の位置を指示する。第２のものは、公平な態様で処理されるべきｋの値と関連した最近の受信セル・ポインタのＬＯＰメモリ３４内の位置を指示する。第３のものは、公平性なしの態様で処理されるべきｋのその値と関連した最近の受信セル・ポインタのＬＯＰメモリ３４内の位置を指示する。
パラメータｋの最大値Ｍ、したがってアレイ３２のサイズは、グループ・シーケンス値ｇの最大値ｇmaxに等しい。
各場合におけるセル・ポインタｐikは、第２のメモリ・ブロックすなわちポインタのリストのブロック３４に記憶されており、このブロックはセル・ポインタのリストを記憶している。記憶装置３２での場合のように、記憶装置３４はＮ個の個別のリストＬＯＰj（ｊ＝１，２，・・・，Ｎ）からなり、各リストは交換装置の出力ポートの１つと関連している。
ブロック３４のセル・ポインタをアレイ３２のさらなるポインタにわたってアクセスすることは、ポインタが記憶されるべきブロック３４内の正しい位置を見い出すために時間が掛かる検索を行う必要性を回避することができる。
ステップＳ１６において、ｎｆフラグがセットされていたかどうかが決定される。フラグが設定されていなければ、プロセスはステップＳ１７に進み、そこで、受信セルがｇ＋ｋのその特定の値を備えた最初のセルであるかどうかが決定される。それが最初のそのようなセルであるならば、処理はステップＳ２０に進む。そこで、バッファ・メモリ３０内のアドレスを指示するポインタｐikが、ポインタ・メモリ３４のリスト、すなわち関連した出力ポートにとって適切なリストＬＯＰjにアドレスＬＯＰjkで記憶される。
次いで、ステップＳ２１において、リストＬＯＰjのそのアドレスＬＯＰjkがグループ・パラメータ・メモリ３２の最後に記憶される。アドレスは、特定の出力ポートと関連したリストのメモリ位置にアドレスＬＧＰ（ｇ＋ｋ）で記憶される。グループ・ポインタ・メモリ３２の最後でのアドレスは、特定の所望の出力ポートと関連したリストに、その受信セルに割り当てられたグループ・シーケンス数とそのセルを受信した時間でのパラメータｋの値とによって決定された位置にある。
メモリ３２のその位置には、その特定の出力ポートと関連しかつ同じ（ｇ＋ｋ）の値を有する最初の受信セルおよび最近の受信セルの両方を指示するポインタが、記憶されている。その場合に、ここでのように、セルが値（ｇ＋ｋ）を持った最初のものである場合には、ステップＳ２２で示されるように、ポインタ・メモリ３４のリスト内のメモリ位置ＬＯＰjkは、グループ・ポインタ・メモリ３２の最後の中の最初および最後のポインタの両者によって指示される。最後に、ステップＳ２３において、ＬＧＰメモリ３２の次の非空のエントリーを見い出すためにセルを送るときに使用されるパラメータ「次」が、次いで更新される。それは記憶プロセスを完成させる。
到着セルが（ｇ＋ｋ）の値を持つように特定の所望の出力ポートと関連した最初のセルではない場合には、すなわちステップＳ１５での質問に対する回答が否（ＮＯ）である場合には、プロセスはステップＳ３０に移る。ステップＳ２０での場合と同様に、バッファ・メモリ３０内の位置に対するポインタは、ポインタ・メモリ３４のリストの適切なリスト、すなわち所望の出力ポートに関連したリストＬＯＰj内でアドレスＬＯＰjkに記憶される。この場合に、そのアドレスは、（ｇ＋ｋ）の値を有するセルのためのポインタを記憶するアドレスにリンクされる。ステップＳ３１において示されるように、アドレスＬＯＰjは、グループ・ポインタ・メモリ３２の最後に、すなわち再び所望の出力ポートに関連したリストＬＧＰjにアドレスＬＧＰ（ｇ＋ｋ）で記憶される。この場合において、「最後の」ポインタは、その所望の出力ポートと（ｇ＋ｋ）の計算値とを有する最近の受信セルのためのポインタのアドレスである。
前のように、ステップＳ２３で、ＬＧＰメモリ３２の次の非空エントリーを見い出すためにセルを送るのに使用されるパラメータ「次」が、次いで更新される。それは記憶プロセスを完成させる。
ステップＳ１６において、ｎｆフラグがセットされたことが決定される場合には、すなわちセルが公平性なしの態様で処理されるべきことが決定される場合には、プロセスはステップＳ４０に移る。ステップＳ３０と同様に、バッファ・メモリ３０内のアドレスに対するセル・ポインタｐikが、ｎｆフラグと共に、ポインタ・メモリ３４のリスト、すなわち所望の出力ポートと関連するリストＬＯＰj内でアドレスＬＯＰjkで記憶される。このアドレスは、公平性なしの態様でも処理されるべきでありかつステップＳ１４においてセットされたような最大の許可され得るグループ・シーケンス数ｇmaxを有するセルのための他のポインタのアドレスに、リンクされている。したがって、実際上、公平な態様で処理されるべき全てのセルのセル・ポインタは、公平性なしの態様で処理されるべきセルのためのセル・ポインタの正面に効果的に記憶される。
したがって、公平な態様で処理されるべきセルの処理に類似した態様で再度、ステップＳ４１において、関連した出力ポートに関連するリストＬＯＰjのアドレスＬＯＰjkが、グループ・ポインタ・メモリ３２内の最後に、所望の出力ポートと関連したリストＬＧＰjにアドレスＬＧＰ（ｇ）で記憶される。このようにして、公平性なしの態様で取り扱われるべきｇの同じ値を有する接続からのセルに対するポインタのアドレスの全てが、アレイ３２の同じ位置にわたってアクセスされる。これは、公平性なしの態様で処理されるべき任意の特定の接続からのセルが先入れ先出し基準で効果的に取り扱われることを意味する。
次いで、ステップ４２において、セル・ポインタのアドレスＬＯＰjkは、そのセルがグループ・シーケンス数ｇmaxを有する最近に受信した公平性なしのセルであることを指示する「最後の公平性なし」ポインタによって、グループ・ポインタ・メモリ３２の最後に指示される。最後に、公平なセルでの場合と同様に、ステップＳ２３において、ＬＧＰメモリ３２の次の非空のエントリーを見い出すためにセルを送るときに使用されるパラメータ「次」が、次いで更新される。これは記憶プロセスを完成させる。
交換装置からセルを送るプロセスをここで説明する。図４は、ＬＧＰアレイと関連する各グループ・シーケンス内のセルの概略図である。この場合において、次に送信するためのものであるセルのグループはｋ＝０に見い出され、斜線の箱は各グループの「公平」セルの後にリンクされる「公平性なし」セルを表す。
送りブロック３６は、グループ・ポインタ・メモリ３２の最後に、（検索パラメータｋの特定の値を有する）グループのシーケンスで最初のものを抜き取ることによって、セルを送る。このようにして、１つの特定のグループに対して、グループ・ポインタ・メモリ３２内の最後のものは、ポインタ・メモリ３４のリスト内での、関連ポインタを記憶しているアドレスを指示する。次いで、これらポインタは、送りブロック３６による送信用のバッファ・メモリ３０からセルを取り出す。あるグループ・シーケンス内で公平に取り扱われるべき接続からのセルの全てと共に、ある数、例えば最大値ｎnfまでの「公平性なしの」セルも送信される。引き続いて、次のグループすなわちＬＧＰアレイ３２内の（ｇ＋ｋ）の次の占有値にわたってアクセルされるセルが、送信のために発せられる。このように、メモリ３２は循環的な態様で使われる。
１つのセルの送信後に、入力接続の識別が更新ブロック２８に送られ、ルックアップ・テーブル２６のその接続と関連したｎiの値を“１”だけ減少させる。
上記したようなシステムは、入力ポート能力の共有が比較的に公平となるようにする。しかしながら、公平性とシステムの複雑さとの間にはかね合いがあることに留意すべきである。このようにして、ｇの許可値の範囲に応じて、システムはより一層公平かより一層複雑かのいずれかに作られることができる。ｇの極めて高い最大許可値では、高度の公平性が達成され得るが、システムは幾分複雑となる。他方、ｇの最大許可値が“１”にセットされていた場合には、システムはより単純となるであろうが、それは通常のＦＩＦＯシステムとして働くことであろう。したがって、実際上は、システムは公平な待ち行列化およびＦＩＦＯ待ち行列化の混成したものとして働く。
更に、今までに記載されたシステムは入力ポートの能力の公平な共有を可能にするが、最も重要な目的は出力ポートの能力の公平な共有を達成することである。これはグループ・シーケンスの送信の調整を必要とする。そうでなければ、少ない有効な接続を有する入力ポートは、多くの有効な接続を有する入力ポートよりも交換装置を通るセルを得ることに一層成功する。この公平性を達成するために、１つの特定の出力ポートに送信すべきグループ・シーケンスは有利に全て結合される。そのため、他の入力ポートの全てが現在のグループ・シーケンスを送ることを終える前に、新たなグループ・シーケンスを送ることを開始するように許可される入力ポートはない。
図５は、必要な公平性を達成するシステムを概略形で示す。図５は、入力調整バス５６により相互接続された第１の入力ポート５２および第２の入力ポート５４を示す（実際は、２つの入力ポートよりも多くのものがあってもよいことを理解するであろう）。入力ポート５２，５４は処理ユニット５８，６０をそれぞれ有し、これらは、上記したような局部公平性関数を計算し、また、各ライン６２，６４によってバス５６に接続されている。バス５６の第１のチャンネル６６は、同じ出力ポートへの送信下にある現在のグループが全ての論理入力ポートで済ませられるかどうかを信号化するために使用される。バス５６の第２のチャンネル６８は、出力から入力への流れ制御信号として使用される。出力ポート・バッファがオーバーフローしようとしている場合には、入力ポートがその出力ポートの方向にセルを送ることを停止するように、信号がチャンネル６８に送られることができる。出力ポートが入力ポートと同じアクセス・ボードに物理的に配置されている場合にこの構成を実行することができるに過ぎないことに留意すべきである。バス５６の他のチャンネル７０は、各論理入力ポートで有効なパラメータ「次」の現在値を信号化するために使用される。例えば、パラメータの各有効値に関連したチャンネル７０の１つがあってもよい。次いで、例えば、「低」信号がチャンネル７０の関連した１つでその入力ポートにより送られてもよい。次いで、次のグループ・シーケンスを送ることを許可されるようにするために、入力ポートは、チャンネル７０の現在の１つによって指示されるものと同じパラメータ値を持たなければならない。これは、全ての入力ポートが任意の一時点で同じグループ・シーケンス数を備えたセル送信することを確実にする。パラメータ「次」の値に対する最大の可能な値は、重み付けパラメータｗの最も大きな値に等しく、そのため、上記したように、ｗのあらゆる可能な値に対してチャンネル７０の１つがなければならない。別態様として、パラメータ「次」の値がチャンネル７０での信号の値の特定の組合せによって表されるように、コード化システムが使用されてもよい。これは、ある余分の複雑性の負担で、必要とされるチャンネル数を減少させることになろう。
図６に示されるように、バス５６はＮ個の出力ポート間で時分割多重される。時間周期Ｔは、調整が効果的になりかつ能力が未使用となることを避けるようにするために、１つのセル送信間隔よりも短くなるように設計されるが、各個々の調整間隔ｔiは、入力ポートの全てがバス５６に対して信号を出しかつバス５６の信号を検出することができるようにするために、充分長くなければならない。
上記したように、当該機構は、比較的に小さな出力バッファに結合された比較的に大きな入力バッファを有するシステムに関連して動作する。しかしながら、純粋に出力バッファリングを行う交換装置を考慮する場合には、同じ局部公平性アルゴリズムは、種々の接続間で公平性を与えるために、出力バッファに直接に等しく適用されてもよい。このような構成において、図７に示されるように、ただ１つのＬＧＰアレイおよび１つのＬＯＰメモリが各出力ポートに対して必要とされる。そうでなければ、図２に示されかつそれに関連して記載されたような構成となる。
以上のように開示された構成は、余分な処理またはストレージ・リソースを必要とせずに、公平な待ち行列化アルゴリズムの使用を可能にする。
【図１】
0003820272.tif 000002
【図６】
0003820272.tif 000003
【図２】
0003820272.tif 000004
【図３−１】
0003820272.tif 000005
【図３−２】
0003820272.tif 000006
【図４】
0003820272.tif 000007
【図５】
0003820272.tif 000008
【図７】
0003820272.tif 000009