JP3673025B2 - パケット転送装置 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、例えば、ＡＴＭ通信網におけるセル多重化装置およびセルバッファ装置に関する。
【０００２】
また、セルスイッチはセル多重化装置が複数個重ね合わされていることから、本発明のセル多重化装置の構成をセルスイッチのひとつの出力ポートに対応する構成としてセルスイッチに適用することが可能である。
【０００３】
本発明のセルバッファ装置は、セルに限らず一般的なバッファ装置にも適用可能である。
【０００４】
さらに、本発明はＡＴＭ通信網のみならず、パケット交換網にも適用可能である。
【０００５】
【従来の技術】
現在、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ）通信方式に関する研究が、世界中の通信技術の研究者らによって精力的に行なわれている。ＡＴＭ通信方式は情報をセルという固定長のパケットにより伝送交換する。ＡＴＭ通信方式ではスイッチノード内のハードウェアによるセルスイッチにより、高速なセルの交換が可能で単位時間当たりの情報転送能力は既存の通信網を越えるものを実現可能である。
【０００６】
ＡＴＭ通信方式は、セルのヘッダのＶＰＩ（Ｖｉｒｔｕａｌ Ｐａｔｈ Ｉｄｅｎｔｉｆｉｅｒ）とＶＣＩ（Ｖｉｒｔｕａｌ Ｃｈａｎｎｅｌ Ｉｄｅｎｔｉｆｉｅｒ）と呼ばれる識別情報により、ひとつの物理伝送路に論理的に複数のコネクション（Ｖｉｒｔｕａｌ Ｃｏｎｎｅｃｔｉｏｎ：ＶＣ）を設定することができる。網内の各スイッチノードにおいては、各ＶＣに対して予めルートが定められており、スイッチノードはセルのコネクション識別子ＶＰＩとＶＣＩからセルを出力すべき出方路を求める。ＶＰＩとＶＣＩは、スイッチノード間の物理伝送路で一意に割り当てられるため、スイッチノードは、通過するセルのＶＰＩとＶＣＩの値を書き換える能力を持つ。
【０００７】
これまで、ＡＴＭ網において品質を保証されたＶＣは、ＣＢＲ（Ｃｏｎ− ｓｔａｎｔ Ｂｉｔ Ｒａｔｅ：固定ビットレート）コネクションかＶＢＲ （Ｖａｒｉａｂｌｅ Ｂｉｔ Ｒａｔｅ：可変ビットレート）コネクションが中心であった。ＣＢＲコネクションは、セルの伝送速度（セルレートまたは帯域ともいう。単位時間当たりの伝送セル数）が一定で予めわかっているトラヒックを伝送するＶＣであり、ＶＢＲコネクションはセルの伝送速度が一定ではないが、その最大値（ピークレート）と平均値（平均レート）などのトラヒックの性質が予めわかっているＶＣである。
【０００８】
基本的には、１本の物理伝送路に複数のＶＣを十分な品質を保ちつつ多重化する場合には、全てのＶＣのピークレートの和が物理伝送路の帯域以下になっていればよい。この手法をピークレート割り当てと呼ぶ。ＣＢＲコネクションのみをピークレート割り当てした場合には、物理伝送路の十分に高い利用効率が達成可能である。ＶＢＲコネクションの場合には、ピークレート割り当てでは、物理伝送路の利用効率を高くできない。そこで予め分かっているトラヒックの性質より、統計的多重化効果を用いて品質を保ちつつ利用効率を上げる技術がさかんに検討されている。
【０００９】
ところが、計算機間のＡＴＭ通信を考えると、平均レートを始めとしたトラヒックの性質が予め予測できないという性質や、瞬間的に大量のセルを送信するが、送信しないときには全くセルを送信しないというバースト性と呼ばれる性質がある。そのため、ＣＢＲやＶＢＲの様に品質を保証しつつ網の利用効率を上げることは難しい。つまり計算機間で転送されるデータは、ピークレート割り当てなどで品質を保証しようとすると網の利用効率が著しく低下し、ＶＢＲの様に統計的多重化効果を用いるとトラヒックのバースト性のためにセルスイッチのある出力ポートに同時に大量のセルが到着し、セルスイッチのバッファ量が十分でないと、バッファ溢れによるセル廃棄が発生してしまう。また、セル廃棄が発生すると複数のセルで構成されているパケット単位で再送が発生し、これにより、実効的なスループットが低下する。
【００１０】
そこで近年、端末とスイッチノード間でフロー制御をかけて、セルの転送品質（特にセル廃棄に関する品質）を保証し、かつ、網の利用効率を上げるＡＢＲ （Ａｖａｉｌａｂｌｅ Ｂｉｔ Ｒａｔｅ）というサービスクラスが提案され、検討が進んでいる。ＡＢＲコネクションは、経由するスイッチノードがセル輻輳におちいりそうになった場合には、スイッチノードがセル輻輳の発生前に、送信端末にセルの送出を迎えるように要求する。端末へのトラヒック制御情報は、主にＲＭセル（リソース管理セル）と呼ばれるセルを用いて行なう。ＡＢＲにおけるスイッチノードから送信端末へのトラヒック制御には無視できない遅延時間が存在する。そのため、トラヒック制御が有効に作用するまでセルを廃棄しないようにセルスイッチは大容量のバッファを実装する必要がある。
【００１１】
ＣＢＲ、ＶＢＲ、ＡＢＲの他のサービスクラスとして、ＵＢＲ （Ｕｎｓｐｅｃｉｆｉｅｄ Ｂｉｔ Ｒａｔｅ）というサービスクラスが存在する。このクラスは、端末が出力するトラヒック特性を詳細に網に申告することを必要としない。そのかわり、網はその転送品質について一切の保証をしない、いわゆるベストエフォート（Ｂｅｓｔ Ｅｆｆｏｒｔ）サービスのクラスである。
【００１２】
前述したように、計算機間のデータはバースト性を持っているため、ＵＢＲコネクションのセル廃棄率を満足できるものとするためにはセルスイッチに大容量のセルバッファを実装する必要があると考えられている。
【００１３】
幸いなことに計算機間のトラヒックは転送の遅延時間、遅延揺らぎに関しての要求がＣＢＲやＶＢＲと比較して厳しくはない場合が多い。容量の大きなバッファをセルスイッチに実装することによりセルの伝送遅延時間、遅延揺らぎが増大するが、それを許容できるアプリケーションは決して少なくないと考えられる。
【００１４】
特にＡＢＲ、ＵＢＲサービスの場合、網の輻輳を回避する手段が必要となると考えられる。輻輳回避手段のひとつとして、ＥＦＣＩ（Ｅｘｐｌｉｃｉｔ Ｆｏｒｗａｒｄ Ｃｏｎｇｅｓｔｉｏｎ Ｉｎｄｉｃａｔｉｏｎ）と呼ばれる方法がある。セルのヘッダ内に、そのセルの輻輳経験を書き込むＥＦＣＩビットがあり、網内のセルスイッチは、その輻輳状況に応じてＥＦＣＩをマークする。端末はその情報を利用することにより輻輳を回避することが可能となる。
【００１５】
次に、ＶＣ間公平キューイングについて説明する。
【００１６】
まず、ＡＢＲサービスにおける耐故障性から要求されるＶＣ間公平キューイングについて述べる。
【００１７】
ＡＢＲサービスは、網からのトラヒック制御情報に従って送信端末がセルの送出を制御することによって成立する。もし、ある端末が故障し（もしくは故意に）、網からのトラヒック制御情報を無視すれば、網の輻輳からの脱出が困難になるおそれがある。
【００１８】
このような問題は、セル多重化装置またはセルスイッチにおいてＶＣ間で公平なキューイングを行ない、ＶＣ間の公平なセル多重化スケジューリングとＶＣ間の公平なバッファ割り当てを実現することにより解決できる。ＶＣ間公平キューイングを行なえばＶＣ間の相互作用は最小限に抑えられ、もしトラヒック制御情報を無視するＶＣがあっても、そのＶＣのみが輻輳におちいり、その他のＶＣにおよぼす影響を低減できるからである。
【００１９】
また、ＵＢＲサービスにおける公平性からもＶＣ間公平キューイングが要求される。
【００２０】
図４８に、ＵＢＲサービスにおける不公平な帯域割り当ての例を示す。この例では網に端末Ａ、Ｂ、Ｃ、Ｄの４つの端末と、ひとつのファイルサーバが存在し、それぞれがセルスイッチ（またはセル多重化装置）Ｘ、Ｙ、Ｚとリンク１、２、３、４、５、６、７により接続されている。
【００２１】
ここで、各セルスイッチが入力リンクに設定されているＶＣ数に関わらずセルを多重化したとすると、各セルスイッチは入力ポートを平等に扱う。例えば、セルスイッチＸは、リンク２とリンク３からのセルをリンク１へ多重化する場合に、両方のリンクを平等に扱うため、リンク１の帯域を１．０とすると、リンク２とリンク３にそれぞれ０．５の帯域を与える。
【００２２】
同様に考えていくと最終的に各端末に与えられる帯域は、端末Ａが最も大きく０．５、端末Ｃ、Ｄは最も少なく０．１２５である。全ての端末が平等にファイルサーバにアクセスすることが理想だとすれば、これは理想とはほど遠い。
【００２３】
またさらに、網が輻輳に陥った場合、網は端末に帯域を小さくするようにＥＦＣＩ情報を送信する。このとき、網内にＥＦＣＩ情報に忠実に従う端末と、無視する端末が存在する場合、ＥＦＣＩに忠実な端末のみがセルの送出を抑制するため、ＥＦＣＩを無視する端末は不当に多くの帯域資源を確保することになってしまうという問題点もある。
【００２４】
これらの問題は、セルスイッチが入力リンクに多重されているＶＣ数を無視して各入力リンクを平等に扱っていることによる。セルスイッチがＶＣ間公平キューイングを行ない、ＶＣ数に応じた帯域の分配を行なうことにより、各端末は公平にファイルサーバーにアクセスすることが可能となる。
【００２５】
次に、クラス間の優先制御を行なうセル多重化装置について説明する。
【００２６】
図４９に従来のクラス間の優先制御を行なうセル多重化装置の構成を示す。
【００２７】
図４９は、Ｎ本の入力ポートから入力したセルを１本の出力ポートに多重化するセル多重化装置である。
【００２８】
出力バッファは、内部のクラス毎のセル蓄積部にクラス毎にセルを蓄積し、出力ポートへはクラスの優先度に応じてセルをセル選択部が選択し出力する。
【００２９】
出力バッファの各蓄積部に蓄積しているセル数としきい値とを比較してバックプレッシャ信号を生成する。入力バッファもまたクラス毎のセル蓄積部が設けられており、バックプレッシャ信号により出力が許可されているクラスの中からクラスの優先度に応じてセルを出力バッファへ転送する。
【００３０】
この構成では出力バッファに複数のクラス毎セル蓄積部を設ける必要があるため、クラス数が多くなると出力バッファの実現が困難になるという欠点があった。特に、出力バッファの入力速度は入力ポートの速度のＮ倍（Ｎは入力ポート数）である必要があり、クラス数、入力ポート数が大きな場合は、この様な複雑な機能を実現することは困難であった。
【００３１】
図４９を、セルスイッチの各出力ポートに関する部分と考えると、入力ポートにバッファを持つセルスイッチについても同じ問題点が存在する。
【００３２】
次に、セル多重化装置について説明する。
【００３３】
図５０に示すような入力バッファを持つセル多重化装置の問題点を説明する。
【００３４】
図５０は、Ｎ本の入力ポートから入力されたセルを１本の出力ポートに多重化するセル多重化装置である。
【００３５】
出力バッファは、入力ポートからのセルを一時的に蓄積し、出力ポートの速度に応じてセルを出力する。
【００３６】
出力バッファに蓄積しているセル数としきい値とを比較してバックプレッシャ信号を生成する。入力バッファは出力ポートに対応してひとつのキューを持ち、バックプレッシャ信号により出力が許可されているときのみセルを出力バッファへ転送する。
【００３７】
この様なセル多重化装置は設定されているＶＣ数に関わらず各入力バッファを公平に扱ってしまうため、ＡＢＲサービスにおける耐故障性や、ＵＢＲサービスにおける公平性に問題があった。
【００３８】
図５０を、セルスイッチの各出力ポートに関する部分と考えると、入力ポートにバッファを持つセルスイッチについても同じ問題点が存在する。
【００３９】
次に、ＶＣ間公平キューイングについて説明する。
【００４０】
図５１にＶＣ間公平キューイングの実現方法であるＶＣ毎のＦＩＦＯの構成を示す。
【００４１】
図５１は、入力リンクより入力したセルのコネクション識別情報をバッファポインタ管理部に通知し、バッファポインタ管理部よりセルの書き込み位置を示す書き込みポインタを得てセルを一時的にセルバッファに蓄積し、バッファポインタ管理部からの、読みだしセルを示す読みだしポインタに基づいてセルをセルバッファから読みだし出力リンクへ出力するセルバッファ装置である。バッファポインタ管理部は、蓄積しているセルのセルバッファ上の位置を示すバッファポインタを管理する。
【００４２】
バッファポインタ管理部はＶＣテーブルによりバッファポインタをＶＣ毎に管理する。図５１は広く知られているポインタチェーンによる管理方法を示している。
【００４３】
セルが入力すると空きチェーンの先頭からバッファポインタを書き込みポインタとして一つ取りだし、入力セルに対応するＶＣのチェーンの末尾につける。セルを出力する時は、セルを蓄積しているＶＣを公平に選択し、その先頭のバッファポインタを読みだしポインタとして取りだす。セル出力時にＶＣを公平に選択する方法として、ラウンドロビンが知られている。
【００４４】
ＶＣをラウンドロビンで選択するためには、ＶＣテーブル上で、前回出力したＶＣの次から、バッファに蓄積しているセルがあるかどうかを順に検索しなければならない。検索は、多い場合にはほぼ全てのＶＣを１セル周期で行なう必要があるが、設定すべきＶＣ数は数千以上に及ぶ場合があり、実現は困難であった。
次に、キュー長監視について説明する。
【００４５】
図５２に、例えば図５０の様な、入力バッファを持つセル多重化装置における、入力バッファのキュー長の変化の一例を示す。
【００４６】
横軸は時間、縦軸は上が入力バッファのキュー長、下がバックプレッシャ信号である。バックプレッシャ信号が出力禁止を指示しているとき（Ｔup）、入力バッファからの出力スループットはゼロであるためキュー長はバッファの入力レート（Ｒi ）で増加する。バックプレッシャ信号が出力可能を指示しているとき、入力バッファからの出力スループットは最大であり、通常キュー長は減少する。
【００４７】
この様にキュー長はバックプレッシャ信号に同期して振動する。従来、バッファにセルが到着したとき、キュー長がしきい値を越えていれば入力したセルを受け付けず廃棄し、越えていなければ受け付けることが広く行なわれている。この方法は通常のバッファでは問題ないが、この様にバッファの出力がバックプレッシャ信号に制御されている場合に問題となる。キュー長の最大値は入力レート （Ｒi ）とバックプレッシャ信号が出力禁止を指示している時間（Ｔup）によって決定され、特にバックプレッシャ信号の出力禁止時間（Ｔup）は、他の入力バッファへの入力トラヒックなどに大きく影響されるからである。
【００４８】
バックプレッシャ信号により制御されるバッファ装置の場合は、単純にキュー長としきい値と比較してセルの廃棄を決定する方法では外部条件によりセルの廃棄が過敏に影響され安定したセルの廃棄が困難であった。キュー長から輻輳を判断する場合にも同じ問題点があった。
【００４９】
次に、優先制御を行うセルバッファ装置について説明する。
【００５０】
図５３に、優先制御を行なうセルバッファ装置の構成を示す。
【００５１】
遅延に関して低優先のセルを一時的に蓄積する、クラス１セル蓄積部と、高優先のセルを一時的に蓄積するクラス２セル蓄積部とあって、それぞれの出力はクラス多重化ＦＩＦＯにより多重化される。クラス管理部は、クラス２セル蓄積部セル数Ｎa およびクラス多重化ＦＩＦＯセル数Ｎb を入力し、どちらかのクラスへ転送指示を与える。転送指示を受けたクラスのセル蓄積部は１セルだけクラス多重化ＦＩＦＯへ転送する。
【００５２】
このセルバッファ装置の優先制御の性能を高めるためにはクラス多重化ＦＩＦＯの蓄積セル数を少なくすることが必要であるが、スループットを低下させないためには、クラス多重化ＦＩＦＯを努めて空にしない（＝アンダフローしない）ように転送を指示する必要がある。さらに、どちらか一方のセル蓄積部が空になっている時に、空のセル蓄積部に対して転送を指示してしまった場合（空指示と呼ぶ）にはアンダフローしてしまう可能性があるため、転送指示は蓄積セルが存在するセル蓄積部に対して行なう必要がある。
【００５３】
以上の方針から、クラス管理部がクラス２セル蓄積部へ転送指示を行なう条件は、
（Ｎb ≦１）ａｎｄ（Ｎa ＞１）
で与えられる。クラス１セル蓄積部への転送指示は、
（Ｎb ≦１）ａｎｄ（Ｎa ＝＝０）
である。
【００５４】
ここで、クラス毎のセル蓄積部やクラス多重化ＦＩＦＯからクラス管理部へのセル数情報の伝送や、クラス管理部からクラス毎セル蓄積部への転送指示情報の伝送、さらにはクラス毎セル蓄積部からセル多重化ＦＩＦＯへのセル転送に遅延時間が存在する場合を考える。このとき従来は次のような問題点が存在していた。
【００５５】
これらの遅延時間により、クラス多重化ＦＩＦＯがアンダフローするかどうかがクラス管理部で正確に判定できなかった。そこでクラス多重化ＦＩＦＯ内セル数をこの遅延時間に応じた大きめのしきい値と比較してアンダフローしないための条件としていた。この結果、クラス多重化ＦＩＦＯの平均キュー長が大きくなり優先制御の性能が低下した。
【００５６】
また、高優先であるクラス２セル蓄積部情報の伝送が遅れることにより、クラス２セル蓄積部が空になったことを正確に判断できない。したがって空になっているのに空でないと誤り、空指示をしてしまうか、空でないのに空であると誤り、高優先であるクラス２のセルよりも低優先のクラス１のセルが優先して出力してしまうような指示を行なってしまっていた。結果としてセルバッファ装置のスループットが低下したり優先制御機能の性能が低下する問題点があった。
【００５７】
以上、図５３の優先制御を行なうセルバッファ装置に関して問題点を述べた。この問題はこの様な優先制御を行なうセルバッファ装置のみならず、さまざまなセルバッファ装置において発生し得る。
【００５８】
つまり、複数のバッファ間のセルの転送を管理部が指示するセルバッファ装置において、管理部へのバッファ情報の伝送、管理部からバッファへの転送指示情報の伝送、バッファ間のセルの伝送に遅延時間が存在する場合、セルバッファ装置の性能やスループットが低下してしまうという問題点があった。
【００５９】
【発明が解決しようとする課題】
以上述べたように、従来のセル多重化装置には次のような第１、第２の２つの問題点があった。
【００６０】
まず、出力バッファに複数のクラス毎セル蓄積部を設ける必要があるため、クラス数が多くなると出力バッファの実現が困難になるという欠点があった。特に、出力バッファの入力速度は入力ポートの速度のＮ倍（Ｎは入力ポート数）である必要があり、クラス数、入力ポート数が大きな場合は、この様な複雑な機能を実現することは困難であった。
【００６１】
次に、設定されているＶＣ数に関わらず各入力バッファを公平に扱ってしまうため、ＡＢＲサービスにおける耐故障性や、ＵＢＲサービスにおける公平性に問題があった。
【００６２】
また、従来のセルバッファ装置には次のような第３、第４の２つの問題点があった。
【００６３】
まず、ＶＣをラウンドロビンで選択するためには、ＶＣテーブル上で、前回出力したＶＣの次から、バッファに蓄積しているセルがあるかどうかを順に検索しなければならない。検索は、多い場合にはほぼ全てのＶＣを１セル周期で行なう必要があるが、設定すべきＶＣ数は数千以上に及ぶ場合があり、実現は困難であった。
【００６４】
これに対し近年、”Ｅｆｆｉｃｉｅｎｔ Ｆａｉｒ Ｑｕｅｕｅｉｎｇ Ｄｅｆｉｃｉｔ Ｒｏｕｎｄ Ｒｏｂｉｎ”（ｐｐ．２３１−２４２、ＡＣＭ ＳＩＧＣＯＭＭ ’９５、１９９５年８月）に記載されているようなアルゴリズムが提案されている。この文献で提案されているＤＲＲというアルゴリズムはアクティブリストという概念を用いてセルを蓄積しているＶＣを管理するため、セル出力時のＶＣテーブルの検索が不要である。従って、設定すべきＶＣ数が増えても高速にＶＣ間公平キューイングの為の出力すべきセルの選択が実現できる。しかしながら、このＤＲＲアルゴリズムでは、パケットを各ＶＣ毎に分類して蓄積するため各ＶＣに設定された重みの値に応じた量のパケットが一度に出力されてしまい、その出力トラヒックのバースト性が非常に高くなってしまうという欠点があった。
【００６５】
次に、バックプレッシャ信号により制御されるバッファ装置の場合は、単純にキュー長としきい値と比較してセルの廃棄を決定する方法では外部条件によりセルの廃棄が過敏に影響され安定したセルの廃棄が困難であった。キュー長から輻輳を判断する場合にも同じ問題点があった。
【００６６】
さらに、複数のバッファ間のセルの転送を管理部が指示するセルバッファ装置においては、次にような第５の問題点があった。すなわち、管理部へのバッファ情報の伝送、管理部からバッファへの転送指示情報の伝送、バッファ間のセルの伝送に遅延時間が存在する場合、セルバッファ装置の性能やスループットが低下してしまうという問題点があった。
【００６７】
本発明は、上述の点に鑑みてなされたもので、その目的とするところは、入力ポート数が大きな場合においても実現が容易なクラス間の優先制御を行なうセル多重化装置を提供することにある。
【００６８】
本発明の他の目的は、ＡＢＲサービスにおける耐故障性や、ＵＢＲサービスにおける公平性を実現するＶＣ毎公平キューイングを行なうことができるセル多重化装置を提供することにある。
【００６９】
本発明の別の目的は、設定可能なＶＣ数の上限に依存することなく容易に実現することのできるＶＣ間公平キューイングを行なうセル多重化装置を提供することにある。
【００７０】
本発明のさらに別の目的は、キュー長の監視結果が外部条件の影響を受け難く、安定したキュー長の監視が容易であるセル多重化装置を提供することにある。
【００７１】
本発明のもう一つの目的は、複数のバッファ間のセルの転送を管理部が指示する際に、管理部へのバッファ情報の伝送、管理部からバッファへの転送指示情報の伝送、バッファ間のセルの伝送に遅延時間が存在する場合においても、従来のように性能やスループットが低下しないセル多重化装置を提供することにある。
【００７２】
【課題を解決するための手段】
本発明のパケット転送装置（請求項１〜４）は、入力されたパケットを一時的に蓄積する複数の入力バッファと、これら入力バッファを制御する制御手段と、前記各入力バッファから出力されるパケットを転送する少なくとも１つの出力ポートを具備したパケット転送装置であって、
前記各入力バッファは、
入力したパケットを一時的にクラス毎に蓄積するクラス毎の蓄積手段と、
前記制御手段から指示されたクラスのパケットを前記蓄積手段から前記出力ポートへ向けて出力する出力手段とを具備し、
前記制御手段は、
前記蓄積手段の複数の入力バッファ全体における蓄積状況をクラス毎に把握し、この蓄積状況に基づいてパケットを出力すべきクラスを決定し、この決定したクラスの指定を含む指示を前記複数の入力バッファに送信することにより、
制御部が複数の入力バッファ全体の状況を把握して（少なくとも全体の状況を把握していればよいが、個々の入力バッファ毎に把握していても構わない）指示を出すため、各入力バッファのクラス毎の蓄積状況の違いによりクラス間の優先関係が崩れてしまうことが生じず、また、入力ポートの数すなわち入力バッファの数が増えても容易にクラス間の優先制御を実現できる。
【００７３】
また、本発明のパケット転送装置（請求項５、６）は、複数の入力バッファと、これら入力バッファを制御する制御手段と、前記各入力バッファから出力されるパケットを転送する少なくとも１つの出力ポートを具備したパケット転送装置であって、
前記各入力バッファは、
入力したパケットを一時的に蓄積する蓄積手段と、
前記制御手段からの指示を受けて、次のフェーズで前記蓄積手段から前記出力ポートへ向けて出力すべきパケットを選択する選択手段と、
この選択手段で選択されたパケットを前記出力ポートに向けて出力する出力手段とを具備し、
前記制御手段は、
前記複数の入力バッファ全体における前記選択手段で選択されたパケットの出力状況を把握し、この出力状況に基づいて新たなパケットを選択するよう前記複数の入力バッファに指示することにより、
あるフェーズ（その時間的長さは不定）内で出力されるべきパケット集合（カゴ）という概念を導入し、このパケット集合に入れるパケットの選択と、このパケット集合に入っているパケットのみを出力する（その他のパケットは出力が許可されない）という処理を各入力バッファが分担し、パケット集合に新たなパケットを入れるタイミングを指示する処理を制御部（カゴ管理部）が分担することにより、例えば、入力バッファ方式のセルスイッチにおいて、ＶＣ間公平キューイングを容易に実現できる。
【００７４】
また、本発明のパケット転送装置（請求項７、８）は、入力したパケットを一時的に蓄積するバッファと、このバッファを制御する制御手段と、前記バッファから出力されたパケットを転送するパケット転送装置であって、
前記制御手段は、
前記バッファ内に蓄積されたパケットを複数の集合に分けて管理する管理手段と、
前記バッファに入力したパケットを各パケットの属するフロー間で公平になるように前記複数の集合のいずれか１つに振り分ける振り分け手段と、
前記管理手段で管理されている前記複数の集合のうちの１つの集合に属するパケットを出力するよう前記バッファに対し指示する指示手段と、
を具備することにより、制御手段（バッファポインタ管理部）でパケットが入力されたときに複数の集合への振り分けが行われており、パケットを出力するときには１つの集合に属するポインタを出すだけで済むので、設定すべきＶＣ数が増えても高速にＶＣ間公平キューイングのための出力すべきパケットの選択が実現できる。また、本発明の前記指示手段により、請求項５の選択手段の動作を実現することができる。さらに、本発明は、出力バッファ方式のセルスイッチでＶＣ間公平キューイングをする際の出力バッファとして用いることができる。
【００７７】
【発明の実施の形態】
以下、本発明の実施形態について図面を参照して説明する。
【００７８】
０． 用語の定義
以下、本発明の実施の形態を説明する上で用いられる用語の定義を行う。
【００７９】
（１） パケットとは、固定長のセルを含む概念で、セルの上位概念と解することができる。また、以下の説明でパケットというときは、可変長、固定長を問わない。また、セルに限定して説明している場合でも、それは単に説明を簡単にするためのもので、特に、これに限るものではない。
【００８０】
（２） パケット（セル）多重化装置とパケット（セル）バッファ装置の違い：
パケットバッファ装置：一つの以上の入力ポートと一つ以上の出力ポート及び一つ以上のバッファを具備し、入力ポートから入力されたパケットを必要に応じて一時的にバッファに蓄積し、出力ポートへ出力する装置。特にパケットを宛先に応じた出力ポートへ出力するパケットバッファ装置は、パケットスイッチと呼ばれる。
【００８１】
パケット多重化装置：パケットバッファ装置の中でも特にパケットの出力ポートが一つのものをパケット多重化装置と呼ぶ（パケットバッファ装置を出力ポート毎に分けて考えると、入力ポートが共通な複数のパケット多重化装置の重ね合わせてとして見ることができる）。以下の説明において、パケット多重化装置について述べていることは、パケットバッファ装置にも容易に適用できる。
【００８２】
（３）パケット転送装置：パケットバッファ装置と、その一種であるパケット多重化装置の双方を含む。また、以下の説明において、多重化装置あるいはバッファ装置を例にとり説明している場合も、特にこれに限るものではなく、広くパケット転送装置として適用できる。
【００８３】
１． クラス間優先制御（第１の実施形態、第２の実施形態）
まず、本発明に係るクラス間の優先制御を行なうセル多重化装置の実施形態について説明する。
【００８４】
１．１ 第１の実施形態
図１に、第１の実施形態に係るクラス間の優先制御を行なうセル多重化装置の構成例を示す。
【００８５】
図１のセル多重化装置は、入力ポート＃１〜＃Ｎのそれぞれに対応して設けられ、各入力ポート＃１〜＃Ｎから入力したセルを一時的に蓄積する複数の入力バッファ１０と、入力バッファ１０の出力したセルを多重化し出力ポートへ出力する出力バッファ１１と、全ての入力バッファを管理するクラス管理部１２とを備える。
【００８６】
入力バッファ１０は、入力したセルをクラス（クラス１〜クラス３）毎に蓄積するクラスのセル蓄積部１３（クラス１セル蓄積部１３ａ、クラス２セル蓄積部１３ｂ、クラス３セル蓄積部１３ｃ）と、セル蓄積部１３から出力したセルを多重化し出力バッファ１１へ出力するクラス多重化ＦＩＦＯ１４を備えている。
【００８７】
クラス管理部１２は、セル蓄積部１３のクラス毎セル蓄積部セル数と、クラス多重化ＦＩＦＯ１４のクラス多重化ＦＩＦＯセル数を得て、予め定められたアルゴリズムより転送クラス指示を決定して全ての入力バッファ１０へ同報する。
【００８８】
入力バッファ１０に同報された転送クラス指示で指示されたクラスのセル蓄積部１３は、セルをクラス多重化ＦＩＦＯ１４へ転送し、クラス多重化ＦＩＦＯ１４は、出力バッファ１１内の輻輳状態に応じたバックプレッシャ信号の制御に従って出力バッファ１１へセルを出力する。
【００８９】
クラス毎セル蓄積部１３は通常はＦＩＦＯ（First In First Out）メモリで構成される。
【００９０】
図１は３クラス（クラス１〜クラス３）の場合を示したが、第１の実施形態はクラス数に関わらず有効に作用する。
【００９１】
また、図１を、セルスイッチの、各出力ポートに関する部分と考えるとセルスイッチについても第１の実施形態を適用できる。
【００９２】
図１の出力バッファ１１は、単段のＦＩＦＯ１５から構成されているが、どんな状況においてもクラス多重化ＦＩＦＯ１４のセルをある有限の時間内で出力ポートに出力できることを保証できれば、どんな形態でもよい。
【００９３】
例えば、バッファを全く持たずにクラス多重化ＦＩＦＯ１４のセルを調停して出力ポートに出力する構成でもよい。また例えば、後述の図３または図４に示す構成でもかまわない。
【００９４】
図３に示した出力バッファ１６は、ＦＩＦＯが複数段（図３では２段）に構成されており、それぞれ前段のＦＩＦＯにバックプレッシャ信号が接続される。
【００９５】
すなわち、図３の出力バッファ１６は、入力側（前段）の複数のＦＩＦＯ１８に、入力バッファ１０の各出力に対応して設けられる入力リンク＃１〜＃Ｎが接続され、それらＦＩＦＯ１８の各出力が出力側（後段）のＦＩＦＯ１９に接続されて構成され、後段のＦＩＦＯ１９から、その輻輳状態に応じて出力されるバックプレッシャ信号は、前段の複数のＦＩＦＯ１８のそれぞれに接続され、前段の複数のＦＩＦＯ１８のそれぞれから、その輻輳状態に応じて出力されるバックプレッシャ信号は、複数のクラス多重化ＦＩＦＯ１４のそれぞれに接続される。
【００９６】
図４に示した出力バッファ１７は、図３と同様にＦＩＦＯが複数段（図４では２段）に構成されている。図３と異なるのは、入力側の複数のＦＩＦＯ１８のキュー長情報（または全てのＦＩＦＯのキュー長情報でもよい）をバックプレッシャ生成部２０へ転送し、バックプレッシャ生成部２０はキュー長情報からバックプレッシャ信号を生成し、全ての入力リンクへ同報することである。
【００９７】
例えば、キュー長を全て合計してしきい値と比較し、しきい値を越えていればバックプレッシャ信号により出力バッファへの入力を禁止する。バックプレッシャ生成部２０はクラス管理部１２に存在しても良い。
【００９８】
第１の実施形態のクラス間の優先制御を行うセル多重化装置によれば、高いスループットが必要な出力バッファにてクラスを識別する必要がないため、容易に実現することが可能となる。入力バッファはクラス毎にセルを管理する必要があるが、入力バッファに必要なスループットは低いため実現が容易となる。
【００９９】
図１のセル多重化装置の構成をさらに詳細に説明する。
【０１００】
クラス管理部１２に入力されるクラス毎セル蓄積部セル数は、クラス毎に、全ての入力バッファ１０のクラス毎セル蓄積部セル数の合計でよい。また、クラス多重化ＦＩＦＯセル数も、全ての入力バッファ１０の合計でよい。
【０１０１】
合計の演算はクラス管理部１２の内部で行なっても良いし、クラス管理部１２の外部で行なっても良い。
【０１０２】
セル数情報はクラス管理部１２において比較的小さなしきい値と大小を判定する。しきい値が固定値であるか動的に変化する値であるかはクラス管理部１２のアルゴリズムに依存するが、もししきい値がある固定値の場合はセル数の代わりにその比較結果をクラス管理部に入力してもよい。または、ある値以上はどのような値でもクラス管理部１２の処理に影響を与えないのなら、それを利用してその値以上は一つの符号に符号化して入力しても良い。例えば４ビットで、セル数を（００００）＝０、（０００１）＝１、（００１０）＝２、（００１１）＝３、…、（１１０１）＝１３、（１１１０）＝１４、（１１１１）＝１５以上、という１６段階に符号化するなどとしてもよい。これによりクラス管理部１２への入力情報を圧縮することができ、実装が容易になるという利点がある。
【０１０３】
セル数の合計を扱うことにより、クラス管理部１２の実装を簡単化することができる。転送クラス指示も全ての入力バッファに同じ情報を同報することから、クラス管理部は入力バッファを個々に認識する必要がない。よって入力ポート数が多くなっても本質的な実装の困難度は変化しないという利点がある。
【０１０４】
クラス管理部１２が転送指示を決定するアルゴリズムは例えば次のようなものである。
【０１０５】
１．クラス多重化ＦＩＦＯセル数より、クラス多重化ＦＩＦＯがアンダフローしないかどうかを判断し、アンダフローする可能性があると判断した場合のみアンダフローしないように転送指示を行なう。アンダフローとは、クラス多重化ＦＩＦＯセル数がゼロになり、本来出力できるはずのクラス毎セル蓄積部のセルが有効に出力できない状態をいう。
【０１０６】
２．クラス毎セル蓄積部セル数より、入力バッファ１０にセルが蓄積されているクラスを転送指示の候補とする。
【０１０７】
３．転送指示を行なうことができる場合に、転送指示の候補となっているクラスの中で最も優先度の高いクラスを求め、そのクラスの転送を指示する。
【０１０８】
クラス管理部１２は出力バッファの状態とバックプレッシャ信号を直接考慮せずに転送クラス指示を行なう。そのため、転送クラス指示によるセルの転送スループットが、入力バッファ１０からのセル出力スループットを、上回ることがあり、その差を一時的に吸収するためにクラス多重化ＦＩＦＯ１４が用意されている。クラス管理部１２はクラス多重化ＦＩＦＯセル数を知ることで、転送クラス指示によるセル転送のスループットが、入力バッファ１０からのセル出力スループットを、長時間連続して越えないように制御する。
【０１０９】
クラス毎セル蓄積部１３からクラス多重化ＦＩＦＯ１４へ実際に転送したセルを全ての入力バッファ１０で合計したセル数（クラス毎転送セル数）をクラス管理部１２が知ることにより、より詳細なクラス間の優先制御を行なうことができる。
【０１１０】
この場合、クラス管理部１２が転送指示を決定するアルゴリズムは例えば次のようなものである。
【０１１１】
１．クラス多重化ＦＩＦＯ内セル数より、クラス多重化ＦＩＦＯがアンダフローしないかどうかを判断し、アンダフローする可能性があると判断した場合のみアンダフローしないように転送指示を行なう。アンダフローとは、クラス多重化ＦＩＦＯセル数がゼロになり、本来出力できるはずのクラス毎セル蓄積部１３のセルが有効に出力できない状態をいう。
【０１１２】
２．クラス毎セル蓄積部セル数より、入力バッファにセルが蓄積されているクラスを転送指示の候補とする。
【０１１３】
３．クラス毎転送セル数より、クラス毎に予め定められたスループット以上のスループットを得ているクラスは、その程度に応じて転送指示する優先度を下げる。または転送指示の候補としない。
【０１１４】
４．クラス毎転送セル数より、クラス毎に予め定められたスループット以下のスループットしか得ていないクラスは、その程度に応じて転送指示する優先度を上げる。
【０１１５】
５．転送指示を行なうことができる場合に、転送指示の候補となっているクラスの中で最も優先度の高いクラスを求め、そのクラスの転送を指示する。
【０１１６】
１．２ 第２の実施形態
次に、第２の実施形態について説明する。
【０１１７】
図２に、第２の実施形態に係るクラス間の優先制御を行なうセル多重化装置の他の構成例を示す。
【０１１８】
図２のセル多重化装置は、入力ポート＃１〜＃Ｎのそれぞれに対応して設けられ、各入力ポート＃１〜＃Ｎから入力したセルを一時的に蓄積する複数の入力バッファ１００と、入力バッファ１００の出力したセルを多重化し出力ポートへ出力する出力バッファ１１１と、全ての入力バッファ１００を管理するクラス管理部１１２とを備える。
【０１１９】
入力バッファ１００は、入力したセルをクラス（クラス１〜クラス３）毎に蓄積するクラス毎のセル蓄積部１１３（クラス１セル蓄積部１１３ａ、クラス２セル蓄積部１１３ｂ、クラス３セル蓄積部１１３ｃ）と、セル蓄積部１１３から出力したセルを多重化し出力バッファ１１１へ出力するクラス多重化ＦＩＦＯ１１４を備えている。
【０１２０】
クラス管理部１１２は、セル蓄積部１１３のクラス毎セル蓄積部セル数と、出力バッファ内セル数を得て、予め定められたアルゴリズムより転送クラス指示を決定して全ての入力バッファ１００へ同報する。
【０１２１】
入力バッファ１００に同報された転送クラス指示で指示されたクラスのセル蓄積部１１３は、セルをクラス多重化ＦＩＦＯ１１４へ転送し、クラス多重化ＦＩＦＯ１１４は、出力バッファ１１１内の輻輳状態に応じたバックプレッシャ信号の制御に従って出力バッファ１１１へセルを出力する。
【０１２２】
クラス毎セル蓄積部１１３は通常はＦＩＦＯで構成される。
【０１２３】
図２は３クラス（クラス１〜クラス３）の場合を示したが、第２の実施形態はクラス数に関わらず有効に作用する。
【０１２４】
図２を、セルスイッチの、各出力ポートに関する部分と考えるとセルスイッチについても第２の実施形態を適用できる。
【０１２５】
図２の出力バッファ１１１は、どんな状況においてもクラス多重化ＦＩＦＯのセルをある有限の時間内で出力ポートに出力できることを保証できれば、どんな形態でもよい。
【０１２６】
例えば、図４に示す構成でもかまわない。
【０１２７】
なお、この場合、バックプレッシャ生成部２０はクラス管理部１１２に存在してもよい。出力バッファ内セル数Ｎｍは、バックプレッシャ生成部２０にて加算し、図２のクラス管理部１１２へ出力する。
【０１２８】
第２の実施形態のクラス間の優先制御を行うセル多重化装置によれば、高いスループットが必要な出力バッファにてクラスを識別する必要がないため、容易に実現することが可能である。入力バッファ１００はクラス毎にセルを管理する必要があるが、入力バッファ１００に必要なスループットは低いため実現が容易である。
【０１２９】
図２のセル多重化装置の構成をさらに詳細に説明する。
【０１３０】
クラス管理部１１２に入力されるクラス毎セル蓄積部セル数は、クラス毎に、全ての入力バッファ１００のクラス毎セル蓄積セル数の合計でよい。
【０１３１】
合計の演算はクラス管理部１１２の内部で行なっても良いし、クラス管理部１１２の外部で行なっても良い。
【０１３２】
セル数情報はクラス管理部１１２において比較的小さなしきい値と大小を判定する。しきい値が固定値であるか動的に変化する値であるかはクラス管理部１１２のアルゴリズムに依存するが、もししきい値がある固定値の場合はセル数の代わりにその比較結果をクラス管理部１１２に入力してもよい。または、ある値以上はどのような値でもクラス管理部１１２の処理に影響を与えないのなら、それを利用してその値以上は一つの符号に符号化して入力しても良い。例えば４ビットで、セル数を（００００）＝０、（０００１）＝１、（００１０）＝２、（００１１）＝３、…、（１１０１）＝１３、（１１１０）＝１４、（１１１１）＝１５以上、という１６段階に符号化するなどとしてもよい。これによりクラス管理部への入力情報を圧縮することができ、実装が容易になるという利点がある。
【０１３３】
セル数の合計を扱うことにより、クラス管理部１１２の実装を簡単化することができる。転送クラス指示も全ての入力バッファ１００に同じ情報を同報することから、クラス管理部１１２は入力バッファ１００を個々に認識する必要がない。よって入力ポート数が多くなっても本質的な実装の困難度は変化しないという利点がある。
【０１３４】
クラス管理部１１２が転送指示を決定するアルゴリズムは例えば次のようなものである。
【０１３５】
１．出力バッファ１１１内セル数より、出力バッファ１１１がアンダフローしないかどうかを判断し、アンダフローする可能性があると判断した場合のみアンダフローしないように転送指示を行なう。アンダフローとは、出力バッファセル数がゼロになり、本来出力できるはずのクラス毎セル蓄積部１１３のセルが有効に出力できない状態をいう。
【０１３６】
２．クラス毎セル蓄積部セル数より、入力バッファ１００にセルが蓄積されているクラスを転送指示の候補とする。
【０１３７】
３．転送指示を行なうことができる場合に、転送指示の候補となっているクラスの中で最も優先度の高いクラスを求め、そのクラスの転送を指示する。
【０１３８】
クラス管理部１１２は出力バッファ１１１の状態を直接考慮して転送クラス指示を行なう。そのため出力バッファ１１１のバッファ量を十分用意すれば、バックプレッシャ信号が入力バッファからのセル出力を抑制することがなく、クラス多重化ＦＩＦＯ１１４は基本的に不要である。クラス管理部１１２は出力バッファ内セル数を知ることで、転送クラス指示によるセル転送のスループットが、出力バッファ１１１からのセル出力スループットを、長時間連続して越えないように制御する。
【０１３９】
このように入力バッファ１００へのバックプレッシャ信号およびクラス多重化ＦＩＦＯ１１４は基本的に不要であるが、出力バッファ１１１のバッファ量が十分でない場合には有効に作用する。これらを備えていれば無い場合に比べ出力バッファ１１１のバッファ量を少なくできる。
【０１４０】
クラス毎セル蓄積部１１３からクラス多重化ＦＩＦＯ１１４へ実際に転送したセルを全ての入力バッファで合計したセル数（クラス毎転送セル数）をクラス管理部１１２が知ることにより、より詳細なクラス間の優先制御を行なうことができる。
【０１４１】
この場合、クラス管理部１１２が転送指示を決定するアルゴリズムは例えば次のようなものである。
【０１４２】
１．出力バッファ１１１内セル数より、出力バッファ１１１がアンダフローしないかどうかを判断し、アンダフローする可能性があると判断した場合のみアンダフローしないように転送指示を行なう。アンダフローとは、出力バッファセル数がゼロになり、本来出力できるはずのクラス毎セル蓄積部１１３のセルが有効に出力できない状態をいう。
【０１４３】
２．クラス毎セル蓄積部セル数より、入力バッファ１００にセルが蓄積されているクラスを転送指示の候補とする。
【０１４４】
３．クラス毎転送セル数より、クラス毎に予め定められたスループット以上のスループットを得ているクラスは、その程度に応じて転送指示する優先度を下げる。または転送指示の候補としない。
【０１４５】
４．クラス毎転送セル数より、クラス毎に予め定められたスループット以下のスループットしか得ていないクラスは、その程度に応じて転送指示する優先度を上げる。
【０１４６】
５．転送指示を行なうことができる場合に、転送指示の候補となっているクラスの中で最も優先度の高いクラスを求め、そのクラスの転送を指示する。
【０１４７】
１．３ 第１、第２の実施形態に係るセル多重化装置の利点
以上、説明したように、上記第１、第２の実施形態のクラス間の優先制御を行なうセル多重化装置によれば、高いスループットが必要な出力バッファにてクラスを識別する必要がないため、入力ポート数が大きな場合においても実現が容易であるという利点がある。
【０１４８】
２． 公平キューイング（第３〜第７の実施形態）
次に、本発明に係るＶＣ間公平キューイングを行なうセル多重化装置の実施形態について説明する。
【０１４９】
２．１ 第３の実施形態（出力バッファ型のセル多重化装置）
図５に、第３の実施形態に係るＶＣ間公平キューイングを行なうセル多重化装置の構成例を示す。
【０１５０】
図５のセル多重化装置は、出力バッファ型と呼ばれ、入力ポート＃１〜＃Ｎのそれぞれに対応して設けられ、入力ポート＃１〜＃Ｎから入力したセルを、入力ポート数Ｎ倍の速度に速度変換する複数の速度変換回路２００と、速度変換回路２００の出力したセルを一時的に蓄積し出力ポートへ出力する出力バッファ２０１とを備える。
【０１５１】
出力バッファ２０１は、入力したセルをＶＣ毎に分離するＶＣ分離部２０１ａと、各ＶＣ毎に設けられる複数のＶＣ毎ＦＩＦＯ２０１ｂと、複数のＶＣ毎ＦＩＦＯ２０１ｂのそれぞれから出力されるセルを選択して出力ポートへ出力するセル選択部２０１ｃを備えている。
【０１５２】
ＶＣ毎ＦＩＦＯ２０１ｂは十分良好なセル廃棄率を得るためには大容量でなければならない。またノンブロッキング条件より、ＶＣ毎ＦＩＦＯ２０１ｂの入力速度は入力ポートのＮ倍でなければならない。入力ポートの速度が大きい場合や、入力ポート数が多い場合は、この様なスループットを満足する高速大容量のメモリは安価ではなく、かつ、この様なスループットを満足しつつ複雑なＶＣ毎のキュー管理を行なうことも困難である。
【０１５３】
２．２ 第４の実施形態（「カゴ」という概念を用いたセル多重化装置）
次に、第４の実施形態について説明する。
【０１５４】
図６に、第４の実施形態に係るカゴと呼ぶ概念を用いたセル多重化装置の構成例を示す。
【０１５５】
図６に示したセル多重化装置は、入力ポート＃１〜＃Ｎのそれぞれに対応して設けられ、入力ポート＃１〜＃Ｎから入力したセルを一時的に蓄積する複数の入力バッファ２１０と、各入力バッファ２１０の出力したセルを多重化し出力ポートへ出力する出力バッファ２１１とを備え、出力バッファ２１１内の輻輳状態に応じてバックプレッシャ信号により各入力バッファ２１０のセル出力を制御する。
【０１５６】
このセル多重化装置は、出力許可済セル集合を管理するカゴ管理部２１２を備える。
【０１５７】
入力バッファ２１０に蓄積されているセルのうち、出力を許可されたセルの集合（出力許可済セル集合）をカゴと呼ぶ。入力バッファ２１０から出力するセルはカゴ２１３から選択する。
【０１５８】
カゴ管理部２１２は、カゴ２１３に含まれるセル数を入力し、予め定められたアルゴリズムよりカゴ２１３へのセル転送指示を決定して全ての入力バッファ２１０へ同報する。
【０１５９】
入力バッファ２１０は、セル転送指示により、カゴ２１３として確定されたセル以外の入力バッファ２１０に蓄積されているセルで、同一の時刻までに出力すべきセルの集合２１４をカゴ２１３に加える。
【０１６０】
図６を、セルスイッチの、各出力ポートに関する部分と考えるとセルスイッチについても第４の実施形態を適用できる。
【０１６１】
図６の出力バッファ２１１は、どんな状況においてもカゴのセルをある有限の時間内で出力ポートに出力できることを保証できれば、どんな形態でもよい。
【０１６２】
例えば、バッファを全く持たずにカゴ２１３のセルを調停して出力ポートに出力する構成でもよい。また例えば図３または図４に示す構成でもかまわない。
【０１６３】
なお、図４において、バックプレッシャ生成部２０はカゴ管理部２１２に存在しても良い。
【０１６４】
第４の実施形態のＶＣ間公平キューイングを行なうセル多重化装置によれば、高いスループットが必要な出力バッファは簡単な構成になっているため、容易に実現することが可能である。入力バッファはカゴによりセルを管理する必要があるが、入力バッファに必要なスループットは低いため、実現の容易性は高い。
【０１６５】
図６のセル多重化装置の構成をさらに詳細に説明する。
【０１６６】
カゴ管理部２１２に入力されるカゴ内セル数は、全ての入力バッファ２１０のカゴ内セル数の合計でよい。
【０１６７】
合計の演算はカゴ管理部２１２の内部で行なっても良いし、カゴ管理部２１２の外部で行なっても良い。
【０１６８】
セル数情報はカゴ管理部２１２において比較的小さなしきい値と大小を判定する。しきい値が固定値であるか動的に変化する値であるかはカゴ管理部２１２のアルゴリズムに依存するが、もししきい値がある固定値の場合はセル数の代わりにその比較結果をカゴ管理部２１２に入力してもよい。または、ある値以上はどのような値でもカゴ管理部２１２の処理に影響を与えないのなら、それを利用してその値以上は一つの符号に符号化して入力しても良い。例えば４ビットで、セル数を（００００）＝０、（０００１）＝１、（００１０）＝２、（００１１）＝３、…、（１１０１）＝１３、（１１１０）＝１４、（１１１１）＝１５以上、という１６段階に符号化するなどとしてもよい。これによりカゴ管理部２１２への入力情報を圧縮することができ、実装が容易になるという利点がある。
【０１６９】
セル数の合計を扱うことにより、カゴ管理部２１２の実装を簡単化することができる。カゴへのセル転送指示も全ての入力バッファ２１０に同じ情報を同報することから、カゴ管理部２１２は入力バッファ２１０を個々に認識する必要がない。よって入力ポート数が多くなっても本質的な実装の困難度は変化しないという利点がある。
【０１７０】
カゴ管理部２１２がカゴ２１３へのセル転送指示を決定するアルゴリズムは例えば次のようなものである。
【０１７１】
すなわち、カゴ内セル数Ｎｋより、カゴ２１３内のセル数がアンダフローしないかどうかを判断し、アンダフローする可能性があると判断した場合のみアンダフローしないように転送指示を行なう。アンダフローとは、カゴ内セル数Ｎｋがゼロになり、本来出力できるはずの入力バッファ２１０のセルが有効に出力できない状態をいう。
【０１７２】
入力バッファ２１０は、カゴ２１３へのセル転送指示に応じて、同一の時刻までに出力すべきセルの集合２１４をカゴ２１３に加える。例えばＶＣ毎に設定する値Ｎx で重み付けされたＶＣ間公平キューイングを行なう場合において、同一の時刻までに出力すべきセルとは、各入力バッファ２１０内のカゴ２１３に入っていないセルでＶＣ毎に最も古いＮx 個のセルを集めたものである。
【０１７３】
転送指示は全ての入力バッファ２１０に同報されるため、カゴ２１３には複数の入力バッファ２１０を通してＶＣ間で公平にセルが入る。カゴ２１３のセルをカゴ２１３の外のセルよりも優先して出力バッファ２１１に転送することにより、複数の入力バッファ２１０を通してＶＣ間で公平にセルを出力バッファ２１１へ転送することが可能である。
【０１７４】
出力バッファ２１１が、カゴ２１３から入力したセルをどんな場合でもある時間内に出力できる構成になっていれば、ＶＣ間で公平にカゴ２１３へ転送されたセルはその時間の遅延揺らぎを持って、出力ポートから出力される。
【０１７５】
図６は、例として、入力ポート＃１、＃２、＃Ｎの入力バッファ２１０にそれぞれ２本、１本、３本のＶＣがキューイングされている状態を示している。全てのＶＣの重みが同じ時、ＶＣ間公平キューイングを行なえば、各入力バッファ２１０からの出力は２対１対３の割合になる必要がある。本実施形態のセル多重化装置は、カゴ管理部２１２から全ての入力バッファ２１０へ同報されるカゴ２１３へのセル転送指示によって、カゴ２１３内のセル数は各入力バッファで２対１対３の割合になり、結果的に出力バッファからの出力も２対１対３の割合になる。
【０１７６】
カゴ２１３へのセルの入力方法には２通りの方法がある。ここでは、転送を指示されたとき、各ＶＣ毎に最も古いＮx 個（ＶＣ毎に設定する値）のセルをカゴに入れる場合を例にとって説明する。
【０１７７】
ひとつの方法は、入力バッファ２１０に入力したセルがカゴ２１３に入れる条件を満たしていても最初はカゴ２１３の中へ入れない方法である。セルはカゴ管理部２１２からセル転送が指示された場合にのみカゴ２１３に転送される。これにより、カゴ内セル数はカゴ管理部２１２がセル転送を指示した場合以外は減少する。
【０１７８】
別の方法は、入力バッファ２１０に入力したセルがカゴ２１３に入れる条件を満たしている時には最初からカゴ２１３の中へ入れてしまう方法である。つまり転送指示の時点でＮx 個のセルをカゴ２１３に転送したＶＣは次の転送指示があるまでセルをカゴ２１３に入れることができないが、転送指示の時点でセルをカゴ２１３に全く転送しなかったＶＣ、または転送セル数がＮx 個に満たないＶＣは、Ｎx 個になるまで入力セルを転送指示がなくてもカゴに２１３入れることができる。これにより、カゴ内セル数は転送指示と転送指示の間においても増加することがあるが、ほぼ全てのアクティブなＶＣがＮx 個のセルを転送した段階で減少する。なお、本実施形態はどちらの方法においても有効に作用する。
【０１７９】
第４の実施形態のセル多重化装置の輻輳状態の判断は、ＶＣ毎に、トラヒックにより変動する情報を予め定められた方法により監視すれば良い。そして、この輻輳判断を元にＶＣ毎に端末にトラヒック制御情報を通知すればよい。
【０１８０】
監視すべき変動する情報は、例えば蓄積セル数、一定時間あたりの入力セル数とその目標値との関係、一定個数のセルが入力する時間とその目標値との関係である。蓄積セル数が多いＶＣ、一定時間あたりの入力セル数が目標値からかけ離れて多いＶＣ、一定個数のセルが入力する時間がその目標値からかけ離れて短いＶＣを輻輳しているＶＣと判断する。
【０１８１】
輻輳しているＶＣのセルのヘッダにあるＥＦＣＩをマークすることや、通過するＲＭセルを書き換えることにより、端末にトラヒック制御情報を通知することができる。
【０１８２】
２．３ 第５の実施形態（「カゴ」という概念を用いたセル多重化装置の他の実施形態）
次に、第５の実施形態について説明する。
【０１８３】
図７に、第５の実施形態に係るカゴと呼ぶ概念を用いたセル多重化装置の他の構成例を示す。
【０１８４】
図７に示したセル多重化装置は、入力ポート＃１〜＃Ｎのそれぞれに対応して設けられ、各入力ポート＃１〜＃Ｎから入力したセルを一時的に蓄積する複数の入力バッファ２２０と、入力バッファ２２０の出力したセルを多重化し出力ポートへ出力する出力バッファ２２１とを備え、出力バッファ２２１内の輻輳状態に応じてバックプレッシャ信号により入力バッファ２２０のセル出力を制御する。
【０１８５】
このセル多重化装置は、出力許可済セル集合を管理するカゴ管理部２２２を備える。
【０１８６】
入力バッファ２２０に蓄積されているセルのうち、出力を許可されたセルの集合（出力許可済セル集合）をカゴと呼ぶ。入力バッファから出力するセルはカゴ２２３から選択する。
【０１８７】
カゴ管理部２２２は、出力バッファ内セル数を入力し、予め定められたアルゴリズムよりカゴ２２３へのセル転送指示を決定して全ての入力バッファ２２０へ同報する。
【０１８８】
入力バッファ２２０は、セル転送指示により、カゴ２２３以外の入力バッファ２２０に蓄積されているセルで同一の時刻までに出力すべきセルの集合２２４をカゴ２２３に加える。
【０１８９】
図７を、セルスイッチの、各出力ポートに関する部分と考えるとセルスイッチについても本実施形態を適用できる。
【０１９０】
図７の出力バッファ２２１は、どんな状況においてもカゴ２２３のセルをある有限の時間内で出力ポートに出力できることを保証できれば、どんな形態でもよい。
【０１９１】
例えば、図４に示す構成でもかまわない。この場合、バックプレッシャ生成部２０はカゴ管理部２２２に存在しても良い。出力バッファ内セル数はバックプレッシャ生成部２０にて加算し、カゴ管理部２２２へ出力する。
【０１９２】
第５の実施形態に係るＶＣ間公平キューイングを行なうセル多重化装置によれば、高いスループットが必要な出力バッファは簡単な構成になっているため、容易に実現することが可能である。入力バッファはカゴによりセルを管理する必要があるが、入力バッファに必要なスループットは低いため、実現の容易性は高い。
【０１９３】
図７のセル多重化装置の構成をさらに詳細に説明する。
【０１９４】
セル数情報はカゴ管理部２２２において比較的小さなしきい値と大小を判定する。しきい値が固定値であるか動的に変化する値であるかはカゴ管理部２２２のアルゴリズムに依存するが、もししきい値がある固定値の場合はセル数の代わりにその比較結果をカゴ管理部２２２に入力してもよい。または、ある値以上はどのような値でもカゴ管理部２２２の処理に影響を与えないのなら、それを利用してその値以上は一つの符号に符号化して入力しても良い。例えば４ビットで、セル数を（００００）＝０、（０００１）＝１、（００１０）＝２、（００１１）＝３、…、（１１０１）＝１３、（１１１０）＝１４、（１１１１）＝１５以上、という１６段階に符号化するなどとしてもよい。これによりカゴ管理部２２２への入力情報を圧縮することができ、実装が容易になるという利点がある。
【０１９５】
カゴ管理部２２２がカゴ２２３へのセル転送指示を決定するアルゴリズムは例えば次のようなものである。
【０１９６】
すなわち、出力バッファ内セル数より、出力バッファ２２１内のセル数がアンダフローしないかどうかを判断し、アンダフローする可能性があると判断した場合のみアンダフローしないように転送指示を行なう。アンダフローとは、出力バッファ内セル数がゼロになり、本来出力できるはずの入力バッファ２２０のセルが有効に出力できない状態をいう。
【０１９７】
入力バッファ２２０は、カゴ２２３へのセル転送指示に応じて、同一の時刻までに出力すべきセルの集合２２４をカゴ２２３に加える。例えばＶＣ毎に設定する値Ｎx で重み付けされたＶＣ間公平キューイングを行なう場合において、同一の時刻までに出力すべきセルの集合とは、各入力バッファ内のカゴ２２３に入っていないセルでＶＣ毎に最も古いＮx 個のセルを集めたものである。
【０１９８】
転送指示は全ての入力バッファに同報されるため、カゴ２２３には複数の入力バッファを通してＶＣ間で公平にセルが入る。カゴ２２３のセルをカゴの外のセルよりも優先して出力バッファ２２１に転送することにより、複数の入力バッファ２２０を通してＶＣ間で公平にセルを出力バッファ２２１へ転送することが可能である。出力バッファ２２１が、カゴ２２３から入力したセルをどんな場合でもある時間内に出力できる構成になっていれば、ＶＣ間で公平にカゴ２２３へ転送されたセルはその時間の遅延揺らぎを持って、出力ポートから出力される。
【０１９９】
図７は、例として、入力ポート＃１、＃２、＃Ｎの入力バッファ２２０にそれぞれ２本、１本、３本のＶＣがキューイングされている状態を示している。全てのＶＣの重みが同じ時、ＶＣ間公平キューイングを行なえば、各入力バッファ２２０からの出力は２対１対３の割合になる必要がある。
【０２００】
図７のセル多重化装置は、カゴ管理部２２２から全ての入力バッファ２２０へ同報されるカゴ２２３へのセル転送指示によって、カゴ内のセル数は各入力バッファで２対１対３の割合になり、結果的に出力バッファ２２１からの出力も２対１対３の割合になる。
【０２０１】
カゴ２２３へのセルの入力方法には２通りの方法がある。ここでは、転送を指示されたとき、各ＶＣ毎に最も古いＮx 個（ＶＣ毎に設定する値）のセルをカゴに入れる場合を例にとって説明する。
【０２０２】
ひとつの方法は、入力バッファ２２０に入力したセルがカゴ２２３に入れる条件を満たしていても最初はカゴの中へ入れない方法である。セルはカゴ管理部２２２からセル転送が指示された場合にのみカゴ２２３に転送される。これにより、カゴ内セル数はカゴ管理部２２２がセル転送を指示した場合以外は減少する。
【０２０３】
別の方法は、入力バッファ２２０に入力したセルがカゴ２２３に入れる条件を満たしている時には最初からカゴ２２３の中へ入れてしまう方法がある。つまり転送指示の時点でＮx 個のセルをカゴ２２３に転送したＶＣは次の転送指示があるまでセルをカゴ２２３に入れることができないが、転送指示の時点でセルをカゴ２２３に全く転送しなかったＶＣ、または転送セル数がＮx 個に満たないＶＣは、Ｎx 個になるまで入力セルを転送指示がなくてもカゴ２２３に入れることができる。これにより、カゴ内セル数は転送指示と転送指示の間においても増加することがあるが、ほぼ全てのアクティブなＶＣがＮx 個のセルを転送した段階で減少する。なお、本実施形態はどちらの方法においても有効に作用する。
【０２０４】
第５の実施形態のセル多重化装置の輻輳状態の判断は、ＶＣ毎に、トラヒックにより変動する情報を予め定められた方法により監視すれば良い。そして、セル多重化装置は、この輻輳判断を元にＶＣ毎に端末にトラヒック制御情報を通知すればよい。
【０２０５】
監視すべき変動する情報は、例えば蓄積セル数、一定時間あたりの入力セル数とその目標値との関係、一定個数のセルが入力する時間とその目標値との関係である。蓄積セル数が多いＶＣ、一定時間あたりの入力セル数が目標値からかけ離れて多いＶＣ、一定個数のセルが入力する時間がその目標値からかけ離れて短いＶＣを輻輳しているＶＣと判断する。
【０２０６】
輻輳しているＶＣのセルのヘッダにあるＥＦＣＩをマークすることや、通過するＲＭセルを書き換えることにより、端末にトラヒック制御情報を通知することができる。
【０２０７】
２．４ 第４、第５の実施形態に係るセル多重化装置の利点
以上説明したように、上記第４〜第５の実施形態に係る出力許可済セル集合 （カゴ）の概念を用いたセル多重化装置によれば、出力許可済セル集合に入れるセルを制御することにより各入力バッファの出力スループットを調整するため、ＶＣ間公平キューイングを行なうことができ、ＡＢＲサービスにおける耐故障性や、ＵＢＲサービスにおける公平性を実現することが可能である。
【０２０８】
２．５ 第６の実施形態（セルグループＦＩＦＯを用いたセルバッファ装置）次に、本発明に係るＶＣ間公平キューイングを行なうセルバッファ装置の実施形態について説明する。
【０２０９】
図８に、第６の実施形態に係るセルグループＦＩＦＯを用いたセルバッファ装置の構成例を示す。
【０２１０】
図８は、入力リンクより入力したセルのコネクション識別情報をバッファポインタ管理部２３０に通知し、バッファポインタ管理部２３０よりセルの書き込み位置を示す書き込みポインタを得てセルを一時的にセルバッファ２３１に蓄積し、バッファポインタ管理部２３０からの、読みだしセルを示す読みだしポインタに基づいてセルをセルバッファ２３１から読みだし出力リンクへ出力するセルバッファ装置である。
【０２１１】
バッファポインタ管理部２３０は、蓄積しているセルのセルバッファ２３１上の位置を示すバッファポインタを管理する。
【０２１２】
バッファポインタ管理部２３０は、バッファポインタの集合である複数のセルグループをＦＩＦＯ管理するセルグループＦＩＦＯ２３２ａと、出力待ちセルグループＦＩＦＯ２３２ｂと、セルグループ選択部２３３と、空きバッファポインタ管理部２３４からなる。
【０２１３】
バッファポインタ管理部２３０は、セル入力時には、空きバッファポインタ管理部２３４より空きのバッファポインタを得て前記書き込みポインタとするとともに、セルグループ選択部２３３がコネクション識別情報より書き込みポインタをセルグループＦＩＦＯ２３２ａの先頭のセルグループより順にＶＣ毎に予め定められた重みに従って決定される数だけ入るようにセルグループ指示を行ない、セルグループＦＩＦＯ２３２ａはセルグループ指示に従って書き込みポインタを指示されたセルグループに入力する。
【０２１４】
セル出力時には、セルグループＦＩＦＯ２３２ａの先頭よりセルグループを出力し、さらにそのセルグループよりバッファポインタを出力して前記読みだしポインタとするとともに、その読みだしポインタを空きバッファポインタ管理部２３４に戻す。
【０２１５】
図８では、セルグループＦＩＦＯ２３２ａから出力され、出力を待っているセルグループが複数になる可能性がある場合の構成を示している。これらのセルグループＦＩＦＯ２３２ａから出力されたセルグループは出力待ちセルグループＦＩＦＯ２３２ｂに入力される。
【０２１６】
出力待ちセルグループＦＩＦＯ２３２ｂのセルグループは、セルバッファ２３１の外部の何らかの管理部により出力を許可されたセルグループである。例えば、図６のカゴ２３１に相当する。
【０２１７】
読みだしポインタは、出力待ちセルグループＦＩＦＯ２３２ｂの先頭のセルグループから出力されたバッファポインタである。
【０２１８】
例えば全てのＶＣの重みを同じとする。セルグループＦＩＦＯ２３２ａの先頭のセルグループのセルは、各ＶＣのキューを考えるとキューの先頭（ただし出力待ちセルグループＦＩＦＯ２３２ｂ内のセルは除く）のセルである。セルグループＦＩＦＯ２３２ａの先頭から２番目のセルグループのセルは、各ＶＣのキューの２番目のセルである。３番目以降のセルグループのセルも同様である。これらのセルを出力する場合はセルグループＦＩＦＯ２３２ａの先頭のセルグループから順に出力するためＶＣ間で公平に出力することになる。
【０２１９】
今まで全く到着していなかったＶＣのセルが新たにこのバッファ装置に到着した場合は、セルグループＦＩＦＯ２３２ａの先頭のセルグループに入力され、他のＶＣのキューの２番目以降のセルよりも優先して出力される。
【０２２０】
この様に、第６の実施形態に係るセルバッファ装置によれば、ＶＣ間で公平にキューイングを行なうことが可能でありながらセルの入力、出力時に図５０に示した従来例のように検索動作が不要であるという利点がある。
【０２２１】
第６の実施形態に係るセルバッファ装置のセルグループＦＩＦＯ２３２ａの実現方法は、例えばポインタチェーンによる方式やリングバッファによる方式が考えられる。
【０２２２】
２．６ 第７の実施形態（セルグループＦＩＦＯを用いたセルバッファ装置の他の実施形態）
次に、第７の実施形態について説明する。
【０２２３】
図９に、第７の実施形態に係るセルグループＦＩＦＯを用いたセルバッファ装置の他の構成例を示す。
【０２２４】
図９は、入力リンクより入力したセルのコネクション識別情報をバッファポインタ管理部２４０に通知し、バッファポインタ管理部２４０よりセルの書き込み位置を示す書き込みボインタを得てセルを一時的にセルバッファ２４１に蓄積し、バッファポインタ管理部２４０からの、読みだしセルを示す読みだしポインタに基づいてセルをセルバッファ２４１から読みだし出力リンクへ出力するセルバッファ装置である。
【０２２５】
バッファポインタ管理部２４０は、蓄積しているセルのセルバッファ２４１上の位置を示すバッファポインタを管理する。
【０２２６】
バッファポインタ管理部２４０は、バッファポインタの集合であるセルグループをＦＩＦＯ管理するセルグループＦＩＦＯ２４２と、セルグループ選択部２４３と、空きバッファポインタ管理部２４４からなる。
【０２２７】
バッファポインタ管理部２４０は、セル入力時には、空きバッファポインタ管理部２４４より空きのバッファポインタを得て前記書き込みポインタとするとともに、セルグループ選択部２４３がコネクション識別情報より書き込みポインタをセルグループＦＩＦＯ２４２の先頭のセルグループより順にＶＣ毎に予め定められた重みに従って決定される数だけ入るようにセルグループ指示を行ない、セルグループＦＩＦＯ２４２はセルグループ指示に従って書き込みボインタを指示されたセルグループに入力する。
【０２２８】
セル出力時には、セルグループＦＩＦＯ２４２の先頭のセルグループよりバッファポインタを出力して前記読みだしポインタとするとともに、その読みだしポインタを空きバッファポインタ管理部２４４に戻す。
【０２２９】
図９では、セルグループＦＩＦＯ２４２内で出力を待っているセルグループを出力待ちセルグループＦＩＦＯ２４２ｂとして記してある。
【０２３０】
出力待ちセルグループＦＩＦＯ２４２ｂのセルグループは、セルバッファ２４１の外部の何らかの管理部により出力を許可されたセルグループである。例えば、図６のカゴに相当する。
【０２３１】
読みだしポインタは、出力待ちセルグループＦＩＦＯ２４２ｂの先頭のセルグループから出力されたバッファポインタである。
【０２３２】
例えば全てのＶＣの重みを同じとする。セルグループＦＩＦＯ２４２の先頭のセルグループ（すなわち、出力待ちセルグループＦＩＦＯ２４２ｂ内のセルグループ）のセルは、各ＶＣのキューを考えるとキューの先頭のセルである。セルグループＦＩＦＯ２４２の先頭から２番目のセルグループのセルは、各ＶＣのキューの２番目のセルである。３番目以降のセルグループのセルも同様である。これらのセルを出力する場合はセルグループＦＩＦＯ２４２の先頭のセルグループから順に出力するためＶＣ間で公平に出力することになる。
【０２３３】
今まで全く到着していなかったＶＣのセルが新たにこのバッファ装置に到着した場合は、セルグループＦＩＦＯ２４２の先頭のセルグループに入力され、他のＶＣのキューの２番目以降のセルよりも優先して出力される。
【０２３４】
この様に、第７の実施形態に係るセルバッファ装置によれば、ＶＣ間で公平にキューイングを行なうことが可能でありながらセルの入力、出力時に図５１に示した従来例のように検索動作が不要であるという利点がある。
【０２３５】
第７の実施形態に係るセルバッファ装置のセルグループＦＩＦＯ２４２の実現方法は、例えばポインタチェーンによる方式やリングバッファによる方式が考えられる。
【０２３６】
２．７ 第６の実施形態に係るセルバッファ装置で用いられるデータ構造
次に、第６の実施形態に係るセルバッファ装置（図８参照）で用いられるデータの構造について説明する。
【０２３７】
図１０、図１１に、図８で説明したバッファ装置をポインタチェーン方式で実現した場合のデータ構造の一例を示す。
【０２３８】
大きく分けて、図１０に示すように、ＶＣテーブル２５０、セルグループＦＩＦＯ２３２ａ、出力待ちセルグループＦＩＦＯ２３２ｂ、空きバッファポインタチェーン２５１、また、図１１に示すように、空きセルグループチェーン２５２で構成される。
【０２３９】
セルグループＦＩＦＯ２３２ａには、それを管理するセルグループＦＩＦＯ管理データ２５３、出力待ちセルグループＦＩＦＯ２３２ｂには、それを管理する出力待ちセルグループＦＩＦＯ管理データ２５４がある。
【０２４０】
セルグループと空きバッファポインタチェーン２５１は、バッファポインタのチェーンであり、セルグループＦＩＦＯ２３２ａと空きセルグループチェーン２５２はセルグループ管理データ２５５のチェーンである。
【０２４１】
出力待ちセルグループＦＩＦＯ２３２ｂは、出力待ちセルグループＦＩＦＯ管理データ２５４にセルグループを指すポインタのリスト（Ｐtr１、Ｐtr２、Ｐtr３、…）がある。
【０２４２】
セルグループＦＩＦＯ２３２ａ、出力待ちセルグループＦＩＦＯ２３２ｂはリングバッファ方式でもかまわない。
【０２４３】
セルが入力した場合、空きバッファポインタチェーン２５１から取り出した書き込みポインタをどのセルグループに入力するかを決定しなければならない。そのため、まずＶＣテーブル２５０の該当する領域を読み出す。ＶＣテーブル２５０のＮx はそのＶＣの重み、Ｎc は作業変数、Ｑlen はそのＶＣの蓄積セル数、ＰtrはそのＶＣのセルが蓄積されているセルグループの末尾へのポインタである。
【０２４４】
はじめに、Ｑlen をチェックして、そのＶＣのセルが現在バッファ装置に蓄積されているかどうかを調べる。もし、Ｑlen がゼロの場合は、セルグループＦＩＦＯ２３２ａの先頭のセルグループに入れる。Ｑlen が１以上の場合でも、Ｐtrが出力待ちセルグループＦＩＦＯ２３２ｂ内のセルグループを指している場合は、セルグループＦＩＦＯ２３２ａの先頭のセルグループに入れる。
【０２４５】
その他の場合はＮc に１．０を加えＮx と比較し、Ｎx の方が大きければＰtrで指しているセルグループに入れ、そうでない場合は、Ｐtrで指しているセルグループの次のセルグループに入れる。
【０２４６】
ここで、セルが入力した時のＮc の更新手順について説明する。前述のように、そのＶＣに関してセルグループＦＩＦＯ２３２ａの先頭のセルグループに初めてバッファポインタを入力する場合は、Ｎc ：＝１．０とする。その他の場合は、Ｎc をＮc ：＝Ｎc ＋１．０と更新する。その結果、もしＮx ＞Ｎc ならば、そのセルグループにバッファポインタを入れる。逆に、もしＮx ＜Ｎc ならば、セルグループＦＩＦＯ２３２ａの次のセルグループにバッファポインタを入れると同時に、Ｎc ：＝Ｎc −Ｎx と書き変える（つまり、０＜Ｎc ＜Ｎx である）。
【０２４７】
もし、セルグループＦＩＦＯ２３２ａの最後のセルグループの次のセルグループにバッファポインタを入れる必要があれば、空きセルグループチェーン２５２の先頭よりセルグループ管理データ２５５をとりだし、セルグループＦＩＦＯ２３２ａの末尾に入れ、そのセルグループにバッファポインタを入れれば良い。 出力待ちセルグループＦＩＦＯ管理データ２５４は、セルグループを指すポインタＰtr１、Ｐtr２、Ｐtr３、…がシフトレジスタになっている。Ｐtr１の示すセルグループがＦＩＦＯの先頭であり、このセルグループから出力したバッファボインタが読みだしポインタとなる。読みだしポインタは空きバッファポインタチェーン２５１の末尾に入力する。Ｐtr１の示すセルグループのバッファポインタが空になったら、そのセルグループは空きセルグループチェーン２５２の末尾に入力する。そしてｎ＞２の全てのｎについてポインタＰtr（ｎ）をＰtr（ｎ−１）にシフトし、新しいＰtr１の指すセルグループからバッファポインタを出力する。
【０２４８】
前述したように、セルの入力時にＶＣテーブル２５０のＰtrが出力待ちのセルグループを指しているかどうか判定しなければならない。したがって出力待ちセルグループＦＩＦＯ管理データ２５４は、検索が容易に可能な構成であることが必要である。
【０２４９】
セルグループＦＩＦＯ２３２ａから出力待ちセルグループＦＩＦＯ２３２ｂに新たにセルグループを転送する場合には、出力待ちセルグループＦＩＦＯ管理データ２５４のセルグループ数をインクリメントして（ｍとする）、Ｐtr（ｍ）がセルグループＦＩＦＯ２３２ａから出力したセルグループを指すようにする。
【０２５０】
なお、第６の実施形態に係るセルバッファ装置は、図６や図７に示すようなカゴの概念を用いた入力バッファに容易に適用することができる。その場合、出力待ちセルグループＦＩＦＯ２３２ｂがカゴに相当する。また、図５の出力バッファにも適用することができる。
【０２５１】
２．８ 第７の実施形態に係るセルバッファ装置で用いれるデータ構造
次に、第７の実施形態に係るセルバッファ装置（図９参照）で用いられるデータの構造について説明する。
【０２５２】
図１２、図１３に、図９で説明したバッファ装置をポインタチェーン方式で実現した場合のデータ構造の一例を示す。
【０２５３】
大きく分けて、図１２に示すように、ＶＣテーブル２６０、セルグループＦＩＦＯ２４２、空きバッファポインタチェーン２６１、また、図１３に示すように、空きセルグループチェーン２６２で構成される。
【０２５４】
セルグループＦＩＦＯ２４２の内部には、出力待ちセルグループＦＩＦＯ２４２ｂが存在し、セルグループＦＩＦＯ２４２を管理するセルグループＦＩＦＯ管理データ２６３、出力待ちセルグループＦＩＦＯ２４２ｂを管理する出力待ちセルグループＦＩＦＯ管理データ２６４がある。
【０２５５】
セルグループと空きバッファポインタチェーン２６１は、バッファポインタのチェーンであり、セルグループＦＩＦＯ２４２と空きセルグループチェーン２６２はセルグループ管理データ２６５のチェーンである。
【０２５６】
出力待ちセルグループＦＩＦＯ２４２ｂは、セルグループＦＩＦＯ２４２の先頭のいくつかのセルグループである。つまり図１２において、セルグループＦＩＦＯ管理データ２６３の先頭ポインタが指すセルグループから出力待ちセルグループＦＩＦＯ管理データ２６４の末尾ポインタが指すセルグループまでが出力待ちセルグループＦＩＦＯ２４２である。
【０２５７】
セルグループＦＩＦＯ２４２、出力待ちセルグループＦＩＦＯ２４２ｂはリングバッファ方式でもかまわない。
【０２５８】
セルが入力した場合、空きバッファポインタチェーン２６１から取り出した書き込みポインタをどのセルグループに入力するかを決定しなければならない。そのため、まずＶＣテーブル２６０の該当する領域を読み出す。ＶＣテーブル２６０のＮx はそのＶＣの重み、Ｎc は作業変数、Ｑlen はそのＶＣの蓄積セル数、ＰtrはそのＶＣのセルが蓄積されているセルグループの末尾へのポインタである。
【０２５９】
はじめに、Ｑlen をチェックして、そのＶＣのセルが現在バッファ装置に蓄積されているかどうかを調べる。もし、Ｑlen がゼロの場合は、セルグループＦＩＦＯ２４２の先頭のセルグループに入れる。
【０２６０】
その他の場合はＮc に１．０を加えＮx と比較し、Ｎx の方が大きければＰtrで指しているセルグループに入れ、そうでない場合は、Ｐtrで指しているセルグループの次のセルグループに入れる。
【０２６１】
ここで、セルが入力した時のＮc の更新手順について説明する。前述のように、そのＶＣに関してセルグループＦＩＦＯ２４２の先頭のセルグループに初めてバッファポインタを入力する場合は、Ｎc ：＝１．０とする。その他の場合は、Ｎc をＮc ：＝Ｎc ＋１．０と更新する。その結果、もしＮx ＞Ｎc ならば、そのセルグループにバッファポインタを入れる。逆に、もしＮx ＜Ｎc ならば、セルグループＦＩＦＯ２４２の次のセルグループにバッファポインタを入れると同時に、Ｎc ：＝Ｎc −Ｎx と書き変える（つまり、０＜Ｎc ＜Ｎx である）。
【０２６２】
セルが入力した時、セルグループがセルグループＦＩＦＯ２４２になかった場合、もし、セルグループＦＩＦＯ２４２の最後のセルグループの次のセルグループにバッファポインタを入れる必要があれば、空きセルグループチェーン２６２の先頭よりセルグループ管理データ２６５をとりだし、セルグループＦＩＦＯ２４２の末尾に入れ、そのセルグループにバッファポインタを入れれば良い。
【０２６３】
出力待ちセルグループＦＩＦＯ管理データ２６４は、出力待ちセルグループＦＩＦＯ２４２ｂの末尾を示すポインタを持っている。先頭はセルグループＦＩＦＯ管理データ２６３の先頭のセルグループと同じである。
【０２６４】
出力待ちセルグループＦＩＦＯ２４２ｂの先頭のセルグループ（セルグループＦＩＦＯの先頭と同じセルグループ）からバッファポインタを出力し、このバッファポインタが読みだしポインタとなる。読みだしポインタは空きバッファポインタチェーン２６１の末尾に入力する。
【０２６５】
セルグループＦＩＦＯ２４２の先頭のセルグループのバッファポインタが空になったら、セルグループＦＩＦＯ２４２からセルグループ管理データ２６５を出力し、空きセルグループチェーン２６２の末尾に入力する。
【０２６６】
出力待ちセルグループＦＩＦＯ２４２ｂに新たにセルグループを転送する場合には、出力待ちセルグループＦＩＦＯ管理データ２６４の末尾を示すポインタをセルグループＦＩＦＯ２４２上の次のセルグループを指すように変更する。
【０２６７】
なお、第７の実施形態に係るセルバッファ装置は、図６や図７に示すようなカゴの概念を用いた入力バッファに容易に適用することができる。その場合、出力待ちセルグループＦＩＦＯ２４２ｂがカゴに相当する。また、図５の出力バッファにも適用することができる。
【０２６８】
２．９ 第６、第７の実施形態に係るセルバッファ装置の利点
以上説明したように、上記第６〜第７の実施形態に係るＶＣ間公平キューイングを行なうセルバッファ装置によれば、ＶＣテーブルを検索する処理が必要なく、したがって設定可能なＶＣ数の上限に依存することなく容易に実現することができる。
【０２６９】
２．１０ フロー間重み付き公平キューイング
以上のＶＣ間公平キューイングを行なうセルバッファ装置は、固定長のパケットであるセルを扱う場合を例にあげて説明した。異なる長さのパケットを同時に扱うことが可能なパケットバッファ装置にも以下に説明するように入力したパケットをフロー毎に定めた重みに基づいて公平に出力することができる。
【０２７０】
ここでのフローとは、以下の例に示すようにある基準によって識別されるパケットの集合である。
【０２７１】
・ＩＰ網のいわゆるフロー（送信元アドレス、送信元レポート、宛先アドレス、宛先ポートの組で識別）、もしくはＡＴＭ網のＶＣＣまたはＶＰＣ。
【０２７２】
・ＩＰ網のサービスクラス（ｇｕａｒａｎｔｅｅｄ、ｃｏｎｔｒｏｌｌｅｄ−ｌｏａｄ、ｂｅｓｔ−ｅｆｆｏｒｔなど）、もしくはＡＴＭ網のサービスカテゴリ（ＣＢＲ、ＶＢＲ、ＡＢＲなど）の違い。
【０２７３】
・プロトコルの違い（ＴＣＰ／ＩＰ、ＤＥＣｎｅｔ、ＳＮＡ、ＡｐｐｌｅＴａｌｋなど）
・アプリケーションの違い（ｆｔｐ、ｔｅｌｎｅｔなど）
・同じバケットバッファ装置を共用する異なった組織（企業別など）
これらを本発明のパケットバッファ装置で異なったフローとして扱うことによりトラヒックを互いに分離することができる。
【０２７４】
はじめに、図１４を用いて、一般的なフロー間重み付き公平キューイングを説明する。このパケットバッファ装置の目的は、装置に蓄積しているパケットをそのフローの重みに従って公平に出力することである。その動作は図１４のようなフロー毎のＦＩＦＯを考えるとわかりやすい。図には、フロー１、フロー２、フロー３の３つのフローのキュー（ＦＩＦＯ）があり、それぞれのキューにはいろいろな長さのパケットが蓄積されている。図中のパケットに添えられている数字は、バイト数で表したそのパケットの長さである。
【０２７５】
このパケットバッファ装置にパケットが入力した場合の処理は、入力したパケットが属するフローを判定しフロー毎のキューに蓄積することである。
【０２７６】
一方パケットの出力については、フロー間で公平に行なうことが必要であり、どのキューのパケットをどの順で出力するかが重要である。ひとつの方法を図１４の状況に合わせて説明する。説明を簡単にするためここでは各フローの重みを同じとしている。また公平の単位をここでは仮に５００バイトと定めた。
【０２７７】
まずフロー１のキューの先頭から３００バイトの長さのパケットと２００バイトの長さのパケットの合わせて５００バイト分のパケットを出力する。次にフロー２のキューの先頭から２５０バイトの長さのパケットを２個続けて出力する。そしてフロー３のキューの先頭から５００バイトの長さのパケットをひとつ出力する。このように出力すると、この時点では各フローバイトの長さのパケットをひとつ出力する。このような出力にすると、この時点では各フローから等しく５００バイトずつのパケットを出力しているので公平に出力したといってよい。続いて再びフロー１から順に各フローから５００バイトずつパケットを出力することを繰り返せばよい。この様にすればパケットはフロー間で公平に出力される。
【０２７８】
以上の方法では５００バイトを単位として公平になっているが、それより小さな単位では必ずしも公平になっていない。しかし厳密な公平性の実現はパケットバッファ装置に非常に大きな処理能力を要求することが知られており、現実問題として上述の程度の公平性で十分と判断される場合が多い。
【０２７９】
さて、上述の説明ではフローの数が３つであったが、パケットバッファ装置が莫大な数のフローを扱う場合、キューにパケットを蓄積しているフローをどの様に探索し、公平にパケットを出力するのかが課題になる。本発明は、パケットグループという概念を用いてこの課題を解決する。
【０２８０】
本発明は、前述の図１４のＺ、Ａ、Ｂ、Ｃ、Ｄの様に全てのフローのキューを一定の長さに区切る。このとき、各区切りを単位としてパケットを出力することで公平なパケット出力を実現できることに着目する。本発明はこれらの区切り毎にパケットをグループ化して管理する。この各グループをパケットグループと呼ぶ。ひとつのパケットグループには複数のフローのパケットが混在する。パケットの出力はまず出力側に最も近いパケットグループＺのパケットを出力し、次にパケットグループＡのパケットを出力する。さらにＢ、Ｃ、Ｄというように順にパケットグループのパケットを出力することにより、本発明のパケットバッファ装置はフロー間で公平にパケットを出力できる。
【０２８１】
ところで図１４において区切りＢのフロー３を見ると、４００バイトのパケットの次に３５０バイトのパケットが蓄積されている。図では同じ区切りに属するパケットは合計５００バイトを上限としているため、パケットをパケットバッファ装置内部で分割しないとする４００バイトのパケットと３５０バイトのパケットの両方を区切り、Ｂに入れることはできない。そうかといって、後からパケットバッファ装置に到着した３５０バイトのパケットを区切りＢに入れなければ区切りＢには１００バイトのすき間が発生してしまう。この様な場合の扱いは後で述べる。
【０２８２】
以上本発明のパケットグループという概念について説明した。
【０２８３】
続いて本発明のパケットバッファ装置の一例を図１５を用いてより具体的に説明する。
【０２８４】
本発明の構成要素として、パケットグループ、パケットグループＦＩＦＯ、フローテーブル、出力待ちパケットグループがある。
【０２８５】
パケットグループは前述した様に蓄積しているパケットをグループ化したものである。図１５ではＡ、Ｂ、Ｃ、Ｄがパケットグループである。各パケットグループに属するパケットには順序がついており、パケットグループはいわばＦＩＦＯ構造になっている。
【０２８６】
本発明は図１５のように、パケットのＦＩＦＯであるパケットグループをさらにＦＩＦＯで管理する。このパケットグループのＦＩＦＯをパケットグループＦＩＦＯと呼ぶ。
【０２８７】
フローテーブルはフロー毎の情報を記憶する。フローテーブルのＮx はそのフローの重みの設定値、Ｎc は作業変数、蓄積量はそのフローの蓄積パケットの合計量、Ｐtrはそのフローの最後に到着したパケットが属するパケットグループへのポインタである。蓄積量はパケットバッファ装置がそのフローのパケットを蓄積しているかどうかを示す目的を持ち、例えばパケット入力時に入力パケット長を加え、パケット出力時に出力パケット長を引く変数とすることによりフロー毎に蓄積パケットの合計バイト数を保持する。
【０２８８】
出力待ちパケットグループは、パケットグループＦＩＦＯから出力されたパケットグループである（図ではパケットグループＺ）。パケットバッファ装置からパケットを出力する場合、出力待ちパケットグループに属するパケットを出力する。
【０２８９】
パケットが入力した場合、そのパケットをどのパケットグループに入れるかを決定しなけらばならない。
【０２９０】
まずはじめに、そのフローのパケットが現在バッファ装置に蓄積されているかどうかを調べる。フロー識別情報よりフローテーブルのそのフローの蓄積量を参照し、それがゼロかどうかで判断できる。現在蓄積されていなければ、パケットグループＦＩＦＯの先頭のパケットグループ（図１５のパケットグループＡ）に入力パケットを入れる。
【０２９１】
蓄積量がゼロより大きな場合でも、Ｐtrが出力待ちパケットグループ（図１５のパケットグループＺ）を指している場合は、やはりパケットグループＦＩＦＯの先頭のパケットグループＡに入力パケットを入れる。
【０２９２】
その他の場合は、入力パケット長と、Ｎx 、Ｎc 、Ｐtrによって決定する。
【０２９３】
各フローのＮx は、そのフローについて、ひとつのパケットグループが管理する平均的なパケットの量を示している。Ｎx はそのフローの最大パケット長よりも大きな値に設定する。
【０２９４】
Ｎc は、Ｎx −Ｎc を計算することにより、Ｐtrで示しているパケットグループに、そのフローが今後入れることのできる残りの量を示す。もしＮx −Ｎc ≧（入力パケット長）ならば、Ｐtrで指しているパケットグループに入力パケットを入れ、逆にＮx −Ｎc ＜（入力パケット長）ならば、パケットグループＦＩＦＯ上で、Ｐtrが目指すパケットグループの次のパケットグループに入力パケットを入れる。
【０２９５】
パケットグループが決定すると、次にＮc とＰtrの値を更新する。パケットグループＦＩＦＯの先頭のパケットグループに、そのフローに関して１つめのパケットを入れた場合は、Ｎc ：＝（入力パケット長）とする。その他の場合は、まず、Ｎc ：＝Ｎc ＋（入力パケット長）とし、その結果もしＮx ＜Ｎc ならさらにＮc ：＝Ｎc −Ｎx と書き変える（つまり、０＜Ｎc ≦Ｎx である）。Ｐtrはその入力パケットを入れたパケットグループへのポインタを書き込む。
【０２９６】
本発明では、ひとつのパケットをふたつのパケットグループが管理することはない。そのため入力パケットの長さがＮx −Ｎc を越えている場合には、入力パケットをＰtrの指すパケットグループに入れず次のパケットグループに入れる。しかしＮc の計算上ではひとつのパケットをふたつのパケットグループに分割して入れる。つまり、Ｎc ：＝Ｎc ＋（入力パケット長）とし、Ｎx を越えた部分があれば、そのＮc −Ｎx を次のパケットグループのＮc とする。このアルゴリズムにより平均的に、ひとつのパケットグループあたりＮx のパケットが属することになる。
【０２９７】
図１５を用いてパケット入力動作を具体的に説明する。図１５はフロー１で長さ２５０バイトのパケットがパケットバッファ装置に到着した場面である。このときフロー１のＰtrはパケットグループＢを指している。フローテーブルの更新は、上述の手続にしたがってＮc をＮc ：＝Ｎc ＋（入力パケット長）＝２００＋２５０＝４５０とする。この値はＮx 以下のなので、この入力パケットはＰtrが指しているパケットグループＢに入れる。
【０２９８】
もし、仮にフロー１の入力パケット長が２５０ではなく３５０であった場合はＮc ：＝２００＋３５０＝５５０となりＮx を越える。したがってさらに、Ｎc ：＝Ｎc −Ｎx ＝５５０−５００＝５０と更新し、この入力パケットをパケットグループＢの次のパケットグループＣに入れる。ＰtrはパケットグループＣに変更する。
【０２９９】
パケットグループＦＩＦＯは先入れ先だしのキューであり、キューイングしているパケットグループ数を必要なだけ増やすことができる。例えば、図１５においてフロー２でパケット長が４００のパケットが到着したと仮定すると、空きのパケットグループ（パケットグループＥ）がパケットグループＤの次に追加され、入力パケットはそのパケットグループＥに入れることになる。
【０３００】
以上のようにパケット入力時の処理は、フローテーブルの該当箇所を変更することと、パケットグループにパケットを入れることと、必要があればパケットグループＦＩＦＯに空きのパケットグループを追加することでよい。フローテーブルを複数のフローに渡って検索することなく入力時の処理を行なうことが可能であり、フロー数が大きくなっても処理の複雑さは変化しない。
【０３０１】
一方、パケットの出力時に必要な処理はさらに簡単である。つまり出力待ちパケットグループからパケットを出力すればよい。必要に応じてパケットグループＦＩＦＯからパケットグループを出力することをその前に行なう。これらの処理もフローテーブルを複数のフローに渡って検索することなく可能であり、フロー数が大きくなっても処理の複雑さは変化しない。
【０３０２】
前述したように各フローの重みＮx は、そのフローに関してひとつのパケットグループあたりの平均的なパケットの量を示している。そして本発明のパケットバッファ装置はパケットグループを単位としてパケットを出力するため、各フローの出力スリープットはＮx に比例する。
【０３０３】
このパケットバッファ装置によれば、フローテーブルを検索する処理が必要なく、したがって設定可能なフロー数の上限に依存することなく容易に可変長パケットを扱い重み付き公平なパケットバッファ装置を実現することができる。
【０３０４】
本発明の各パケットグループはパケットを到着順に管理する。つまり同じパケットグループに属するパケットの出力順位は全てのフローを通して到着順になるということである。この性質はパケットの遅延揺らぎを低減する効果がある。
【０３０５】
また、本発明のパケットバッファ装置は、従来の技術で説明したＤＲＲというアルゴリズムと比較すると、ＶＣ数が増えても高速にＶＣ間公平キューイングの為の出力セルの選択が実現できるうえ、重みの値が大きくなっても出力トラヒックのバースト性が増加することがない。本発明でバースト性が増加しないのは、入力したパケットを複数の集合（パケットグループ）に振り分け管理する際に、ひとつの集合内ではパケットをフロー（ＶＣ）とは無関係に管理し、パケットをその集合（パケットグループ）から出力する際はフロー（ＶＣ）とは無関係に出力するからである。
【０３０６】
３． バックプレッシャを考慮したキュー監視（第８の実施形態）
次に、本発明の第８の実施形態に係るバックプレッシャを考慮したキュー監視を行うセルバッファ装置について説明する。
【０３０７】
図１６に、例えば、前述の第１、第２、第４、第５の実施形態で説明したような入力バッファにおけるキュー長の変化の一例を示す。
【０３０８】
第８の実施形態に係るセルバッファ装置は、バックプレッシャ信号により出力が出力可能と出力禁止の２状態に制御されているセルバッファ装置であって、バックプレッシャ信号が出力可能から出力禁止に変化した時から次に出力可能から出力禁止に変化するまでの間で、最初のセル入力時の蓄積セル数のみを監視することを特徴とする。
【０３０９】
監視の目的は、輻輳の判定や、ひとつのバッファ領域を複数のキューが共用する場合においてバッファ領域の独占を防ぐための入力セル廃棄の判定などである。
【０３１０】
図１７にバックプレッシャ考慮のキュー監視部を持つセルバッファ装置の構成例を示す。図１７において、セルバッファ装置は、複数のキューＱｉ（ｉ＝１〜Ｎ）、キューテーブル記憶部２８０、バックプレッシャ識別子（ＢＰＩＤ）記憶部２８１、キュー監視部２８２から構成される。
【０３１１】
キューテーブル記憶部２８０に記憶されるキューテーブルのＱlen i はそのキューの蓄積セル数、Ｃnti は輻輳判定変数（初期値ゼロ）、ＢＰＩＤt i は最後のセル入力時のバックプレッシャ識別子（ＢＰＩＤ）である。
【０３１２】
セルがキューに入力すると入力セル情報がキュー監視部２８２に転送される。また、ＢＰＩＤはバックプレッシャ信号が出力可能から出力禁止に変化した時に図１６の様にインクリメントされる。キュー監視部２８２はキュー長の監視を図１８に示すアルゴリズムに基づいて行なう。
【０３１３】
図１８にバックプレッシャを考慮したバッファのキュー長監視アルゴリズムの一例を示す。これはキュー長を監視して輻輳の有無を判断する例を示している。
【０３１４】
キューＱｉにセルが入力されて、セル入力処理が開始されると、まず、Ｑlen i をインクリメントする（ステップＳ１）。
【０３１５】
次に、ＢＰＩＤとＢＰＩＤt i を比較することにより、キュー長を監視すべきかそうでないかを判断する（ステップＳ２）。すなわち、バックプレッシャ信号により変動するキュー長が短くなった時に監視する。
【０３１６】
ＢＰＩＤ≠ＢＰＩＤt i の場合、キュー長を監視すべきであり、まず、Ｃnti ＞１であるか否かを判断する（ステップＳ３）。このとき、Ｃnti ＞１場合は直前まで輻輳状態だと判断し、輻輳状態か否かを判断するためのしきい値Ｑthにヒステリシスを持たせた値（Ｑth−Ｈ）とＱlen i 比較する（ステップＳ４）。
【０３１７】
一方、Ｃnti ＞１でない場合は、Ｑlen i ＞Ｑthを判定する（ステップＳ５）。 ステップＳ４、ステップＳ５でキュー長Ｑlen i をＱth−ＨあるいはＱthと比較した結果、これらのしきい値を越えているとき（すなわち、Ｑlen i ＞Ｑth−Ｈ、あるいは、Ｑlen i ＞Ｑthであるとき）、Ｃnti ：＝Ｑlen i −Ｑth＋Ｈを行ない（ステップＳ６、ステップＳ７）、そうでなければＣnti ：＝０とする（ステップＳ８、ステップＳ９）。さらに、ステップＳ１０に進む。
【０３１８】
ステップＳ２で、ＢＰＩＤ＝＝ＢＰＩＤt i の場合、キュー長を監視すべきではなく、そのままステップＳ１０に進む。
【０３１９】
ステップＳ１０では、Ｃnti ＞１を判定する。もし、そうであれば輻輳状態であり、ステップＳ１１に進み、Ｃnti から「１」を減算し（Ｃnti ：＝Ｃnti −１）、入力セルを廃棄するなら（ステップＳ１２）Ｑlen i から「１」を減算する（Ｑlen i ：＝ Ｑlen i −１）。Ｃnti ＞１でないなら（ステップＳ１０）輻輳状態ではない。
【０３２０】
最後に、ＢＰＩＤt i にＢＰＩＤの値を代入し、ＢＰＩＤt i を更新する（ステップＳ１３）。
【０３２１】
このように、図１８に示したフローチャートによれば、バックプレッシャー信号が出力可能から出力禁止に変化した時から、次に、出力可能から出力禁止に変化する時までの最初のセル入力時の蓄積数のみを監視していることになる。
【０３２２】
なお、Ｈは、ヒステリシスに関するパラメタを示す。ヒステリシスはキュー長を監視して行なわれるセル廃棄や輻輳状態などの判定結果の振動を低減する作用がある。０＜Ｈ＜Ｑthであり、ヒステリシスが不要である場合はゼロに設定する。
【０３２３】
図１８では、しきい値ＱthとヒステリシスパラメタＨは全てのキューで同じ値を用いる場合を示しているが、キュー毎に異なる値を設定してもかまわない。
【０３２４】
ここで、しきい値Ｑthの決定方法を述べる。まず、バックプレッシャ信号によって制御されていないバッファを考える。このバッファは一定レートＲi で入力し、一定レートＲ0 で出力するとする。Ｒi ＞Ｒ0 のとき、この負荷（Ｒi −ＲO ）が加わってもｔT 時間廃棄を起こさないために必要なバッファ量Ｑthは、Ｑth＝（Ｒi −ＲO ）×ｔT により求められる。
【０３２５】
これに対し、この第８の実施形態では、図１６に示すように、入力レートはＲi で一定であるが、入力バッファからの出力レートはＴup時間（入力バッファからの出力禁止時間）についてはゼロ、Ｔdn時間（入力バッファからの出力可能時間）についてはＲe である。Ｔup、Ｔdnの変化が少ないと仮定すると、先ほどと同じく、この負荷が加わってもｔT 時間廃棄を起こさないために必要なバッファ量Ｑthは、
【数１】

【０３２６】
となる。ここで、出力ポートからの平均の出力レートＲ′0 は、
【数２】

【０３２７】
であるから、Ｑth＝( Ｒi −Ｒ′O ）×ｔT となり、この第８の実施形態のセルバッファ装置は、バックプレッシャのない単純なバッファ装置の場合のしきい値と同じしきい値を設定することにより、ほぼ同様の効果を得られると考えられる。
【０３２８】
なお、輻輳状態を判定する代わりに、セルの廃棄判定を行なう場合でも全く同じアルゴリズムが適用できる。
【０３２９】
以上説明したように、上記第８の実施形態に係るバックプレッシャ信号を考慮するセルバッファ装置によれば、キュー長の監視結果が外部条件の影響を受け難く、安定したキュー長の監視が容易である。
【０３３０】
４． 遅延を考慮したセル数情報の修正（第９の実施形態）
次に、本発明に係るセル数情報を修正するセルバッファ装置の実施形態について説明する。
【０３３１】
４．１ 第９の実施形態（遅延を考慮したセルバッファ装置）
図１９に、第９の実施形態に係る遅延を考慮したセルバッファ装置の構成を示す。
【０３３２】
図１９に示したセルバッファ装置は、大きく分けて、ひとつ以上のセルバッファＢ（Ｂａ、Ｂｂ、…）を複数段（図１９では２段）接続してなるセルバッファ網３００と、各セルバッファＢのセル数を入力してセルバッファＢへ転送指示を行なう管理部３０１とから構成される。
【０３３３】
管理部３０１は、転送指示の履歴３０２を保持し、新たな転送指示を決定する際にこの転送指示履歴３０２を使用することを特徴とする。
【０３３４】
前記管理部３０１は、セルバッファＢがセル数を管理部３０１へ送信した時刻から、管理部が決定する転送指示がそのセルバッファＢに作用する時刻までに、そのセルバッファＢに作用する転送指示の回数を前記転送指示履歴３０２より求め、その転送指示の回数とセル数から転送指示を決定する。
【０３３５】
図２０は、本発明の遅延を考慮したセルバッファ装置におけるセル数情報の修正原理を説明する図である。
【０３３６】
入力リンク＃１、＃２から入力したセルは、それぞれ前段のセルバッファＢa1、Ｂa2に一時的に蓄積される。管理部３０１の転送指示に従いセルはセルバッファＢb に転送され、セルバッファＢb はセルを出力リンクへ出力する。
【０３３７】
管理部３０１には、Ｂa2のセル数Ｎa2と、Ｂb のセル数Ｎb が伝送され、Ｂa1、Ｂa2に対して転送指示を出力する。
【０３３８】
今、Ｂa2からセル数情報が管理部３０１に到着し、その情報から転送指示を決定してＢa2に転送を指示して、この転送指示によりＢa2のセル数が変化するまでの遅延時間をＤセル周期とする。また、Ｂb からセル数情報が管理部に到着し、その情報から転送指示を決定してＢa1、Ｂa2に転送を指示して、この転送指示によりＢa1またはＢa2からＢb へセルが転送されＢb のセル数が変化するまでの遅延時間も、説明を簡単にするため同じＤセル周期であるとする。
【０３３９】
ここで、図２０を、セルバッファＢa1、Ｂa2が図５３のクラス１セル蓄積部、クラス２セル蓄積部に相当し、セルバッファＢb がセル多重化ＦＩＦＯに相当する優先制御を行なうセルバッファ装置と考える。Ｂa1、Ｂa2、Ｂb のセルバッファ間のセル転送の方針は図５３と同じである。つまりＢb の蓄積セル数を少なくすることが必要であるが、Ｂb を努めて空にしない（＝アンダフローしない）ように転送指示をする。さらに、転送指示は空指示をしないように行なう（Ｂa2に蓄積セルが存在する場合にのみＢa2に対して転送指示を行なう）。
【０３４０】
さて、時刻ｔ2 でＢa2から出力されたセル数情報Ｎa2が管理部３０１へ到着し、時刻ｔ3 に管理部３０１が転送指示を行なって時刻ｔ4 にその転送指示によりＢa2からセルが出力したとする。管理部３０１が知りたい情報は、転送指示が実際にＢa2に作用する時刻ｔ4 におけるＢa2のセル数である。この時点を図２０に白丸で示した。
【０３４１】
Ｂa2が時刻ｔ2 からｔ4 の時間（＝Ｄセル周期）でＭa2回の転送指示を受け付けたとすると、この間にＢa2はＭa2セル出力したことになり、時刻ｔ4 におけるＢa2のセル数はＮa2−Ｍa2である（Ｂa2へセルが入力しなかった場合）。
【０３４２】
通常、管理部３０１からＢa2までの転送指示の伝送遅延は一定だから、Ｂa2が受信する転送指示回数Ｍa2は、ｔ4 −ｔ2 ＝Ｄ＝ｔ3 −ｔ1 となるようなｔ1 とｔ3 間で管理部３０１が出力した転送指示の回数と等しい。従って、転送指示履歴３０２より転送指示回数Ｍa2を知ることにより、時刻ｔ2 からｔ4 におけるＢa2の減少セル数を正確に求めることができる。
【０３４３】
Ｂb に関しても同様に考えることができ、時刻ｔ2 からｔ4 におけるＢb のセル数の増加量（Ｂa2からの転送セルによる増加量）を正確に求めることができる。
【０３４４】
時刻ｔ2 からｔ4 でのＢa2への入力セル数は、管理部３０１は知ることができない。Ｂa2に対して空指示しないようにするためには、Ｂa2のセル数を少なめに見積もればよい。従って、入力リンクからＢa2へのセル入力は、時刻ｔ2 からｔ4 においてなかったと仮定する。
【０３４５】
また時刻ｔ2 からｔ4 でのＢb からのセル出力は、管理部３０１は知ることができない。Ｂb がアンダフローしないようにするためには、Ｂb のセル数を少なめに見積もる必要がある。従って、Ｂb からのセル出力は、時刻ｔ2 からｔ4 において常に出力し続けたと仮定する（Ｄセル周期であるので、Ｄセルと仮定する）。さらに、Ｂa1からの入力セルもゼロと仮定する。
【０３４６】
まとめると、修正されたＮa2、Ｎb をそれぞれＮ′a2、Ｎ′b とすると、
Ｎ′a2＝Ｎa2＋０−Ｍa2
Ｎ′b ＝Ｎb ＋Ｍa2−Ｄ
である。よって管理部３０１がＢa2へ転送指示を行なう条件は、
（Ｎ′b ≦Ｔｈ）ａｎｄ（Ｎ′a ＞０）
で与えられる。Ｂa1への転送指示は、
（Ｎ′b ≦Ｔｈ）ａｎｄ（Ｎ′a ≦０）
の条件で行なう。Ｔｈは通常は「１」である。以上のようにセル数を修正することにより、アンダフローや空指示を努めて少なくしつつ転送を指示することができる。
【０３４７】
４．２ 一般的なバッファ網におけるセル数の修正方法
次に、一般的なバッファ網におけるセル数の修正方法について説明する。
【０３４８】
基本原理の説明には図２１を用いる。図２１には、すでに述べたようにセルバッファ網３００と管理部３０１がある。セルバッファ網３００は、着目しているセルバッファＢx を含む。セルバッファＢｘは物理的には複数のバッファであっても良い。管理部はこのセルバッファＢｘからセル数情報を得て転送指示を与える。まず本発明を説明する際に使用する用語の定義を行う。
【０３４９】
４．２．１． 用語の定義
時刻は、特に断らない限り現在時刻をゼロとする相対時刻とし、セル周期経過毎に１ずつ増加するものとする。このような時刻の定義は他の表現方法に変換可能であり一般性がある。また、ある時刻ｔ１からある時刻ｔ２までの期間をｐなどと表すことがあり、これをｐ＝［ｔ１、ｔ２）と表す。この期間ｐは時刻ｔ１を含み、ｔ２は含まない。
【０３５０】
セルバッファＢｘの蓄積セル数をＮｘで表す。Ｎｘは現在時刻（ｔ＝０）に管理部３０１に到着した蓄積セル数である。
【０３５１】
セルバッファＢｘに対し管理部３０１が時刻ｔ（ｔ＜０）に出力した転送指示をＩｘ（ｔ）で表す。転送を指示した場合はＩｘ（ｔ）＝１であり、転送を指示しない場合はＩｘ（ｔ）＝０である。
【０３５２】
時刻ｔ（ｔ＜０）に管理部３０１に到着したセルバッファＢｘのＨＯＬセル数をＨｘ（ｔ）で表す。
【０３５３】
ＨＯＬセル数とは、１回の転送指示でセルバッファから一度に転送される可能性のあるセル数である。特に、現在時刻に管理部３０１に到着したＨＯＬセル数情報ＨｘをＨｘ（０）と表す。
【０３５４】
本発明の管理部３０１は、時刻ｔ（ｔ＜０）において得たセルバッファＢｘのＨＯＬセル数Ｈｘ（ｔ）および自らがセルバッファＢｘへ出力した転送指示Ｉｘ（ｔ）を履歴として記憶する。
【０３５５】
ある期間ｐに管理部がセルバッファＢｘに転送を指示した回数をＳｍｘ（ｐ）と表す。ｐ＝［ｔ１、ｔ２）のとき、Ｍｘ［ｔ１、ｔ２）とも表す。つまり、
【数３】

【０３５６】
図２３に、セルバッファＢｘから管理部３０１へのセル数情報の流れと、管理部３０１からセルバッファＢｘへの転送指示の流れを表したタイムチャートを示す。
【０３５７】
この図の様に、時刻ｔｆ、ｔｔ、ｔｈを定める。時刻ｔｆにおけるセルバッファＢｘの蓄積セル数Ｎｘおよび時刻ｔｈにおけるセルバッファＢｘのＨＯＬセル数Ｈｘは、管理部３０１が現在時刻においてセルバッファＢｘに関し直接知り得る最新の情報であるとする。このとき管理部３０１は、時刻ｔｔにおけるセルバッファＢｘの蓄積セル数を予測したいものとする。
【０３５８】
時刻ｔｆ、ｔｔ、ｔｈに対して、時刻ｔ１、ｔ３、ｔ２を定める。時刻ｔ１に管理部３０１が出力した転送指示がセルバッファＢｘに届く時刻をｔｆとし、時刻ｔ２に管理部３０１が出力した転送指示がセルバッファＢｘに届く時刻をｔｔとする。同様に時刻ｔ３に管理部３０１が出力した転送指示がセルバッファＢｘに届く時刻をｔｈとする。
【０３５９】
時刻ｔ１、ｔ２、ｔ３は現在時刻より過去の時刻であるとする。つまり、ｔ１＜ｔ２＜０、ｔ３＜０とする。
【０３６０】
４．２．２． 基本原理
ここで本発明の基本原理を説明する。本発明の管理部３０１は転送指示の履歴から蓄積セル数の変化を予測する。前述のセルバッファＢｘについて、時刻ｔｔの蓄積セル数を求めたい場合、それより過去にの時刻ｔｆにおける蓄積セル数Ｎｘに対して、転送指示の履歴を用いてこの期間に転送指示により転送されたセル数を予測して修正する。修正は、１回の転送指示により転送されるセル数が１以上であることに基づく。特に時刻ｔｈ以降の最初の転送指示により転送されるセル数についてはＨＯＬセル数Ｈｘ以上であることに基づく。
【０３６１】
４．２．３． ３つの関数
以上の基本原理より修正に使用する３つの関数、ｆ（ ）、ｇ（ ）、Ｓｃ（）を定める。これらの関数は、時刻ｔｆから時刻ｔｔにおいてセルバッファＢｘが転送指示によるセルの転送でどのくらい変化するかを求めるものである。ｔｆ、ｔｔと比較してｔｈがどのような値であるかにより３通りの場合に分類でき、適用する関数が異なる。
【０３６２】
（１） 関数ｆ（ ）
関数ｆ（ ）は、ｔｈ＝ｔｆ＜ｔｔの場合に使用する。この時のタイムチャートを図２２に示す。ｐ１［ｔ１、ｔ２）とする。Ｈｘ≠０かつＳｍｘ（ｐ１）≠０のときは、期間ｐ１の最初の転送指示ではＨｘセル転送され、それ以降の転送指示では１セルずつ転送されると考える。時刻ｔｆから時刻ｔｔにおいて変化するセルバッファＢｘのセル数を計算する関数ｆ（ ）は、Ｈｘと期間ｐ１の転送指示回数Ｓｍｘ（ｐ１）を引数として、次のように求めることができる。
【０３６３】
【数４】

【０３６４】
（２） 関数ｇ（ ）
関数ｇ（ ）は、ｔｈ＜ｔｆ＜ｔｔの場合に使用する。この時のタイムチャートを図２３に示す。ｐ１＝［ｔ１、ｔ２）とし、ｐ２＝［ｔ３、ｔ１）とする。
【０３６５】
この場合、時刻ｔｈ以降に到着した初めての転送指示が期間ｐ２に管理部３０１から出力されたか否かで場合分けが必要である。期間ｐ２に管理部３０１から転送指示が出力されていないから、期間ｐ１においてＨｘの値を用いることができる。時刻ｔｆから時刻ｔｔにおいて変化するセルバッファＢｘのセル数を計算する関数ｇ（ ）は、Ｈｘと期間ｐ１、ｐ２の転送指示回数Ｓｍｘ（ｐ１）、Ｓｍｘ（ｐ２）を引数として、次のように求めることができる。
【０３６６】
【数５】

【０３６７】
（３） 関数Ｓｃ（ ）
関数Ｓｃ（ ）は、ｔｆ＜ｔｔ＝ｔｈの場合に使用する。この時のタイムチャートを図２４に示す。ｐ１＝［ｔ１、ｔ２）とする。管理部３０１が知り得る最新の蓄積セル数は時刻ｔｆのときの値であるが、この場合はＨＯＬセル数に関しては時刻ｔｆから時刻ｔｔまでの全ての期間における情報が管理部３０１にすでに到着している。
【０３６８】
転送指示がセルバッファＢｘへ到着した時点のＨＯＬセル数がわかれば、転送されるセル数もわかることから、時刻ｔｆから時刻ｔｔにおいて変化するセルバッファのセル数を計算する関数Ｓｃ（ ）は、Ｉｘ（ｔ）、Ｈｘ（ｔ）を用い、期間ｐ１を引数として、次のように求めることができる。
【０３６９】
【数６】

【０３７０】
以上説明してきたようなセル数の修正方法を、例えば、図１に示したようなクラス間の優先制御を行なうセル多重化装置に適用することは容易である。
【０３７１】
さらに、例えば、図６に示したようなＶＣ間公平キューイングを行なうセル多重化装置に、セル数の修正方法を適用することも容易である。
【０３７２】
４．３ 第９の実施形態に係るセルバッファ装置の利点
以上説明したように、上記第９の実施形態によれば、セルバッファとセルバッファを管理する管理部との間に遅延のあるセルバッファ装置は、転送指示を決定する際に転送指示の履歴を用いて、セルバッファから伝送されてきたセル数を、転送指示がセルバッファに作用する時刻のセル数に修正するため、遅延時間を原因とした性能の劣化が少ない。
【０３７３】
５．セルスイッチ（第１０の実施形態）
５．１ 第１０の実施形態（セルスイッチ）
次に、第１０の実施形態として、ここまで説明してきた本発明に係るセル多重化装置、セルバッファ装置を組み合わせたセルスイッチについて説明する。
【０３７４】
図２５は、複数の入力ポート＃ｉ（ｉ＝１〜Ｎ）から入力したセルを一時的に蓄積し、バックプレッシャに応じて出力する複数の入力バッファＩＢと、内部の輻輳状態に応じてバックプレッシャ信号を出力するバックプレッシャ付きセルスイッチ４００と、入力バッファＩＢとの間で情報を転送するカゴ管理部ＫＭとからなる。
【０３７５】
この構成例において扱うセルは、大きくは高優先セル、低優先セルの２つの優先度を持ち、さらに低優先クラスは複数のクラスにわかれている。通常はＣＢＲ、ＶＢＲなどのリアルタイム情報を伝送するセルを高優先セルとし、ＡＢＲ、ＵＢＲなどのノンリアルタイム情報を伝送するセルを低優先セルとする。
【０３７６】
まず、バックプレッシャ付きセルスイッチについて説明する。
【０３７７】
カゴスイッチの特徴は入力バッファＩＢとカゴ管理部ＫＭにある。バックプレッシャ付きセルスイッチ４００は入力したセルをある定められた時間内に出力できればよく、そのアーキテクチャは以下に示すものだけではない。例えば、電子情報通信学会技術報告ＳＳＥ９３−６“バッファ容量拡張可能なＡＴＭスイッチ：ＸＡＴＯＭ”にて示されているＡＴＭスイッチでもよい。
【０３７８】
図２５に示すバックプレッシャ付きセルスイッチ４００を一例として説明する。１段目単位スイッチＳＥ１、２段目単位スイッチＳＥ２、出力バッファＯＢからなり、ＳＥ１とＳＥ２を並列リンクにて２段デルタ網接続し、ＳＥ２の出力したセルをＯＢへ転送して出力ポートへ出力する。ＳＥ１からＯＢの間はｋ倍速で動作する。ｋの値はセルスイッチがノンブロッキングになるように定める。例えばＳＥ１、ＳＥ２が８入力８出力の時、全体で１６入力１６出力とする場合にはｋ＝２とすればよい。
【０３７９】
図２５のバックプレッシャ付きセルスイッチ４００は、高優先セルと低優先セルの２段階の優先度を扱う構成である。
【０３８０】
低優先セルの交換にのみ着目すると基本構成は１９９５年電子情報通信学会総合大会Ｂ−５８９“ＡＴＭ２段スイッチ網のバッファ容量拡張法”にて示されているものとほぼ等しい。低優先セルは、ＳＥ１、ＳＥ２で交換、コピーされる。
【０３８１】
低優先セルがＯＢで輻輳した場合には低優先セル用バックプレッシャ信号を用いてＩＢのその出力ポート行きのセル出力を抑制する。このバックプレッシャ信号により基本的にはＯＢおよびＳＥ２のバッファを溢れさせないようにすることが可能である。しかし、マルチキャストセルの影響のためこれらのバッファが溢れそうになる場合があり、それに備えて低優先セル用オーバーフローバックプレッシャ信号がＯＢからＳＥ２へ出力し、低優先セル非常用バックプレッシャ信号がＳＥ２からＩＢへ出力する。ＩＢが低優先セルを蓄積するのでＳＥ２、ＯＢでは廃棄されない。
【０３８２】
ＯＢは、低優先セル用オーバーフローバックプレッシャ信号をＳＥ２へ出力する代わりに、これを低優先セル非常用バックプレッシャ信号としてＩＢへ出力する構成でもよい。この場合は、ＳＥ２が低優先セル非常用バックプレッシャ信号を出力する必要はない。しかし、先に説明したように、低優先セル非常用バックプレッシャ信号をＳＥ２から出力した方がＳＥ２内でのバッファ共用化効果を有効に活用できるという利点がある。
【０３８３】
高優先セルは、低優先セルと同様、ＳＥ１、ＳＥ２で交換、コピーされる。高優先セルに関してはバックプレッシャ付きセルスイッチからＩＢへのバックプレッシャ信号はない。ＯＢはその高優先セルの輻輳を反映した高優先セル用バックプレッシャ信号によりＳＥ２のセル出力を制御する。ＩＢは高優先セルを蓄積しない。ＳＥ２内に空きバッファが無ければ廃棄されることがある。
【０３８４】
次に、出力バッファについて説明する。
【０３８５】
図２６に、カゴスイッチの出力バッファＯＢの構成例を示す。
【０３８６】
ＳＥ２からＯＢへ転送されたセルは識別部４１０にて優先度を識別され各優先度に対応したキューに入れられる。各キューのセルは選択部４１１により優先度に従って選択され出力ポートへ出力される。ＯＢは、低優先セルのキュー長があるしきい値を越えた場合に低優先セル用バックプレッシャ信号を用いてＩＢの低優先セルの、そのＯＢ行きの出力を止める。高優先セルのキュー長があるしきい値を越えた場合に高優先セル用バックプレッシャ信号を用いてＳＥ２の高優先セルの、そのＯＢ行きの出力を止める。低優先セルのマルチキャストセルの影響により低優先セルのキュー長が伸び続けた場合に備えて低優先セル用オーバーフローバックプレッシャ信号を用いてＳＥ２の低優先セルの、そのＯＢ行きの出力を止める。
【０３８７】
次に、単位スイッチについて説明する。
【０３８８】
図２７に、カゴスイッチに用いる１段目単位スイッチＳＥ１の構成例を示す。ＳＥ１は一般的によく知られているスイッチＬＳＩである。入力リンクより入力したセルに対し、そのセルヘッダを識別部４１５で識別して所定の交換処理を行い出力リンクへ出力する。スイッチ全体がｋ倍速で動作していることから内部のセルバッファの蓄積セル数は多くならない。これについては１９９４年電子情報通信学会秋季大会Ｂ−４３９“並列リンクのあるスイッチ網の検討”にて知られている。
【０３８９】
図２８に、カゴスイッチに用いる２段目単位スイッチＳＥ２の構成例を示す。ＳＥ２は内部のキューが出力リンク毎に優先度毎のキューになっている。各優先度毎のキューの出力は選択部４２１により選択される。高優先セルが存在するときには、低優先セルの有無に関わらずその出力リンクに高優先セルを出力する。ただし、選択部４２１に入力している高優先セル用バックプレッシャ信号が、高優先セルの出力の禁止を指示している場合は高優先セルを出力せず、低優先セルを出力しても良い。低優先セルは低優先セル用オーバーフローバックプレッシャ信号により出力が禁止される場合がある。
【０３９０】
ＳＥ２は、複数の優先度、複数の出力リンク間で物理的なバッファ領域を共有することにより、ＳＥ２内部のバッファを効率的に使用することが可能である。バッファ状態管理部４２２は各キュー毎のキュー長、および優先度毎に全ての出力リンク行きのキュー長を合計した結果などをモニタする。
【０３９１】
例えば、高優先セル用キューは各キュー毎にしきい値を持ち、そのしきい値を越えた場合にそのキューの入力セルを廃棄する。低優先セル用キューは全てのキュー長の合計をモニタし、しきい値を越えた場合は低優先セル非常用バックプレッシャ信号により低優先セルの入力を禁止するようにＩＢに伝える。
【０３９２】
ＳＥ１はＳＥ２と同じ単位スイッチを使用してもかまわない。
【０３９３】
図２５のバックブレッシャ付きセルスイッチ４００は２段の単位スイッチＳＥ１とＳＥ２によりセルを交換するが、内部の経路は各入力ポートと出力ポートのペアにひとつずつしか定めない。そのため各単位スイッチはセルヘッダを見てセルをコピーしつつ交換する際に複雑な経路の選択アルゴリズムは必要ない。出力ポート数が３２ポート程度以下であるなら、セルのヘッダに出力ポートのビットマップ情報を付加することが容易に可能である。ＳＥ１、ＳＥ２はそのビットマップ情報に基づいてセルを交換する。
【０３９４】
次に、入力バッファＩＢについて説明する。
【０３９５】
図２９に、カゴスイッチの入力バッファＩＢの構成例を示す。
【０３９６】
ＩＢに入力した高優先セルは、ユニキャスト、マルチキャストとも優先的にＳＥ１へ出力する。そのため高優先セルのセル遅延揺らぎは非常に小さい。またＩＢに高優先セル用のバッファは存在しない。
【０３９７】
本発明の特徴は低優先セルの処理方法にある。以降、低優先セルについてのみ説明する。
【０３９８】
図２９において、入力バッファＩＢは、主に、入力したユニキャストセルを一時的にそのセルの出力ポート毎に蓄積する複数の出力ポート毎ユニキャストセル管理部４３０と、入力したマルチキャストセルを一時的に蓄積するマルチキャストセル管理部４３１、およびこれらの管理部のセルを選択して入力バッファから出力する出力ポート選択スケジューラ４３２を持つ。
【０３９９】
出力ポート毎ユニキャストセル管理部４３０は、入力したセルを一時的にそのセルのクラス毎に蓄積する複数のクラス毎ユニキャストセル管理部４３３と、そのクラス毎ユニキャストセル管理部４３３から出力したセルを多重化するクラス多重化ＦＩＦＯ４３４を持つ。
【０４００】
マルチキャストセル管理部４３１は、入力したセルを一時的にそのセルのクラス毎に蓄積する複数のクラス毎マルチキャストセル管理部４３５と、そのクラス毎マルチキャストセル管理部４３５から出力したセルを多重化するクラス多重化ＦＩＦＯ４３６を持つ。
【０４０１】
出力ポート毎ユニキャストセル管理部４３０、マルチキャストセル管理部４３１のそれぞれのクラス多重化ＦＩＦＯ４３４、４３６より出力するセルは出力ポート選択スケジューラ４３２により選択され、入力バッファＩＢから出力される。
【０４０２】
出力ポート選択スケジューラ４３２は外部からの低優先セル用バックプレッシャ信号、低優先セル非常用バックプレッシャ信号を考慮してセルを選択する。
【０４０３】
クラス毎ユニキャストセル管理部４３３は、蓄積されているセルのうち、カゴ管理部ＫＭから出力を許可されたセルの集合を管理するカゴと呼ばれるキュー （カゴ４４０）と、それ以外のセルを管理する前カゴと呼ばれるキュー（前カゴ４４１）を持つ。
【０４０４】
前カゴ４４１に入ったセルは単位カゴという単位で管理される。図２９において前カゴ４４１、カゴ４４０内の縦一列が単位カゴを示す。入力したセルは単位カゴ毎にＶＣ（ＣＧ）間で公平に管理される。前カゴ４４１のセルはカゴ管理部ＫＭの指示により、単位カゴを単位としてカゴ４４０に転送される。
【０４０５】
カゴ４４０のセルはカゴ管理部ＫＭの指示により、セルを単位として転送されクラス多重化ＦＩＦＯ４３４で多重化される。
【０４０６】
クラス毎マルチキャストセル管理部４３５の動作は後述する。
【０４０７】
ＩＢの全ての出力ポート、全てのクラスのキューでセルバッファを共有することにより、有限のバッファ量を有効に活用することが可能である。
【０４０８】
ＩＢに到着したセルがＩＢから出力されるためには、セルが到着したことをＩＢからＫＭへ通知し、ＫＭがＩＢからの出力を指示することが必要である。従ってＩＢとＫＭの間の情報伝送に遅延がある場合はその遅延時間だけＩＢからのセルの出力が遅延する。しかし遅延時間の大きさは数セル周期程度と考えられるため、トラヒック特性に及ぼす影響は少ないと考えられる。
【０４０９】
ユニキャストセルを出力ポート毎に優先制御するために、ＩＢには出力ポート毎に、クラス毎ユニキャストセル管理部４３３とクラス多重化ＦＩＦＯ４３４がある。図１のセル多重化装置で説明した優先制御と基本的に同じ方法を使用する。
【０４１０】
図１はセル多重化装置であるが、カゴスイッチはセルスイッチでありＩＢはセルスイッチの入力バッファである。そのためクラス多重化ＦＩＦＯはひとつのＩＢに全ての出力ポートに対応して複数存在し、そのセルは出力ポート選択スケジューラ４３４により選択されＳＥ１へ出力される。
【０４１１】
図１のセル多重化装置のクラス毎セル蓄積部１３は、図２９のＩＢのクラス毎ユニキャストセル管理部４３３に相当し、図１のセル多重化装置のクラス多重化ＦＩＦＯ１４は、図２９のＩＢのクラス多重化ＦＩＦＯ４３４に相当する。
【０４１２】
図１のセル多重化装置のクラス管理部１２は、図２５のＫＭに対応する。クラス毎ユニキャストセル管理部４３３からクラス多重化ＦＩＦＯ４３４へのセルの転送をカゴ管理部ＫＭが指示することにより優先制御を行なうことができる。
【０４１３】
マルチキャストセルの優先制御は後述する。
【０４１４】
ユニキャストセルをクラス毎にＶＣ間公平キューイングするために、クラス毎ユニキャストセル管理部４３３に前カゴ４４１とカゴ４４０がある。図６のセル多重化装置で説明したＶＣ間公平キューイングと基本的に同じ方法を使用する。
【０４１５】
図６はセル多重化装置であり、かつクラスも存在しないが、ＩＢはセルスイッチの入力バッファでありクラスも存在する。前カゴ４４１、カゴ４４０は各ＩＢについて、全ての出力ポート、全てのクラスに対応して存在し、そのセルはクラス多重化ＦＩＦＯ４３４により多重化された後、出力ポート選択スケジューラ４３２により選択されＳＥ１へ出力される。
【０４１６】
図６のセル多重化装置のカゴ２１３は、図２９のＩＢのカゴ４４０に相当し、図６のセル多重化装置の同一の時刻までに出力すべきセル集合２１４が、図２９のＩＢの単位カゴに相当する。図６のセル多重化装置のカゴ管理部１２は、図２５のカゴ管理部ＫＭに相当する。図２９の前カゴ４４１からカゴ４４０への単位カゴの転送をカゴ管理部ＫＭが指示することによりＶＣ間公平キューイングを行なうことができる。
【０４１７】
マルチキャストセルのＶＣ間公平キューイングは後述する。
【０４１８】
ユニキャストセルをＩＢ内でＶＣ間公平キューイングするために、クラス毎ユニキャストセル管理部４３３に前カゴ４４１とカゴ４４０がある。図１０のセルグループＦＩＦＯ２３２ａのポインタチェーンによるデータ構造例で説明した方法と基本的に同じ方法を使用する。
【０４１９】
図１０のセルグループＦＩＦＯ２３２ａが、図２９のＩＢの前カゴ４４１に相当し、図１０の出力待ちセルグループＦＩＦＯ２３２ｂが、図２９のＩＢのカゴ４４０に相当する。また、図１０のセルグループは図２９のＩＢの単位カゴに相当する。
【０４２０】
次に、図３０を参照して、入力バッファＩＢのキューイング処理について説明する。
【０４２１】
セルは、まず前カゴ４４１に蓄積され、その後単位カゴを単位としてカゴ４４０に転送される。カゴ４４０のセルはセルを単位としてカゴ４４０から出力される。それぞれのきっかけについてはカゴ管理部ＫＭが指示を行なう。
【０４２２】
この構成例では、全てのＶＣは、あるコネクショングループ（ＣＧ）に所属する。コネクショングループの概念を持つことにより複数のＶＣにひとつのリソース（帯域やセルバッファ）を共有させることが可能となる。例えば、離れたふたりのユーザ間の通信に対して１本のＶＣ分の課金しか行なわないときに、そのふたりのユーザ間に複数のＶＣを設定する自由度を与えることが可能となる。もしくは、ＶＣ数に応じて公平な帯域の割当を行なう網において、あるふたりのユーザが多数のＶＣを設定して不当に大きな帯域を得ようとすることを防止することが可能となる。
【０４２３】
前カゴ４４１においてセルをどの単位カゴにいれるかを決定するためにＶＣテーブルとＣＧテーブルを使用する。
【０４２４】
ＶＣテーブルを用いて入力したセルのコネクション識別子（例えばＶＣ４）からコネクショングループ識別子（例えばＣＧ５）を知ることができる。ＣＧテーブルを用いてコネクションクループ識別子からＣＧ毎に定められた値を知ることができる。この構成例におけるＣＧ毎の値はＮx 、Ｎc 、Ｐtr、Ｑlen 、Ｃnt１、Ｃnt２、Ｃnt３、ＢＰＩＤt である。
【０４２５】
Ｎx 、Ｎc 、Ｐtr、Ｑlen は、図１０のセルグループＦＩＦＯのポインタチェーンによるデータ構造例で説明した。Ｎx はそのＣＧの重み、Ｎc は作業変数、Ｑlen はそのＣＧの蓄積セル数、ＰtrはそのＣＧのセルが蓄積されている単位カゴの末尾へのポインタである。
【０４２６】
一方、Ｑlen 、Ｃnt１、Ｃnt２、Ｃnt３、ＢＰＩＤt は、図１５および図１６のバックプレッシャ考慮キュー監視部を持つセルバッファ装置で説明した。
【０４２７】
Ｑlen はそのＣＧの蓄積セル数、Ｃnt１は廃棄すべきセル数、ＢＰＩＤt は最後のセル入力時のバックプレッシャ識別子である。よりきめの細かいキュー監視を行なうためＣnt１と同じ機能を持つ変数Ｃnt２、Ｃnt３が存在する。それぞれキュー長監視のしきい値が異なる。Ｃnt２はセルヘッダ内にあるＣＬＰ（Ｃｅｌｌ Ｌｏｓｓ Ｐｒｉｏｒｉｔｙ：セル廃棄優先）ビットが低優先（ＣＬＰ＝１）であるセル用の廃棄すべきセル数、Ｃnt３はこのキュー長監視において輻輳かどうかを判定するために使用する値である。輻輳かどうかの情報は、例えばセルヘッダ内にあるＥＦＣＩをマークするかどうかや、ＲＭセルの輻輳表示ビットをマークするかどうかを決定するために用いる。
【０４２８】
あるクラスでＶＣ間公平キューイングを行なわない設定をすることも可能である。その場合は、そのＶＣが所属するＣＧのＮx を十分大きな値に設定すればよい。
【０４２９】
さて、図２５に示すバックプレッシャ付きセルスイッチは、ＩＢからＯＢまでのセル伝送の遅延時間が大きいことなどの影響により、低優先セル用バックプレッシャ信号が出力可能と出力禁止を繰り返す周期が比較的大きい。従ってＩＢのＣＧ毎のキュー長Ｑlen を観測すると、主に低優先セルバックプレッシャ信号に同期して図１４の様に振動を繰り返す。この様に、バックプレッシャ信号により振動するキュー長の監視には、図１５、図１６で説明したバックプレッシャ考慮キュー長監視アルゴリズムが適している。
【０４３０】
前カゴ４４１のとカゴ４４０に蓄積されているセルのクラス全体の合計セル数についてもバックプレッシャ考慮キュー長監視により入力セルの廃棄やＥＦＣＩのマークなどを行なって、一部のクラスがＩＢのバッファ領域の大半を独占することを防ぐことが可能である。
【０４３１】
図３１に、カゴスイッチに用いる入力バッファＩＢのカゴ管理部ＫＭとのインタフェースの一例を示す。
【０４３２】
ＫＭから各出力ポートのそれぞれに対し、以下に示すような各出力ポート毎の情報が入力される。
【０４３３】
−ＡＢＲ入力セル数
−指示クラス
−前カゴからカゴへ単位カゴの転送指示（図３１の転送指示Ｔ１）
−カゴからクラス多重化ＦＩＦＯへセルの転送指示（図３１の転送指示Ｔ２）ＡＢＲ入力セル数はＡＢＲ処理部４５０へ転送される。ＡＢＲ処理部４５０は、ＡＢＲ入力セル数を知ることによりそのＩＢとペアの出力ポートに流入するトラヒックをモニタすることができる。その情報を用いてＩＢを通過するＲＭセルのペイロードの書き換えなどを行なう。
【０４３４】
カゴ４４０からクラス多重化ＦＩＦＯ４３４へセルの転送をＫＭから指示されると、ＩＢは指示クラスのユニキャストのカゴ４４０からセルをひとつ取りだしクラス多重化ＦＩＦＯ４３４に転送する。また前カゴ４４１からカゴ４４０へ単位カゴの転送指示があると、ＩＢは指示クラスのユニキャストの前カゴ４４１から単位カゴをひとつ取りだしカゴ４４０に転送するとともに、カゴ４４０からセルをひとつ取りだしクラス多重化ＦＩＦＯ４３４に転送する。
【０４３５】
単位カゴの転送指示をそのクラスのセルの転送指示を行なう時のみに限定することにより、転送指示の情報量を減らし、より容易に実装することができる。
【０４３６】
ＩＢ内で前カゴ４４１、カゴ４４０、クラス多重化ＦＩＦＯ４３４のセル数が変化するのは、ＩＢへセルが入力した時、ＫＭが転送指示を行なった時、ＩＢからセルが出力した時である。従って、それに応じてセル数情報をＫＭへ出力する。ひとつのＩＢがＫＭへ出力する情報は、以下のものである。
【０４３７】
各出力ポート毎に、入力したセルについて（ユニキャストの場合はひとつの出力ポートについてのみ出力）、
−入力セルの有無とクラス
各出力ポート毎に、転送の指示クラスについて、
−（転送後の）前カゴセル数（図３１のＣＥ１）
−（転送後の）カゴセル数（図３１のＣＥ２）
−クラス多重化ＦＩＦＯへの転送セル数（図３１のＣＥ３）
各出力ポート毎に、ユニキャストのみの、
−クラス多重化ＦＩＦＯセル数（図３１のＣＥ４）
図３１を用いて説明する。入力したセルの情報はＩＢからＫＭへ入力セルの有無とクラスとして伝送される。また、ユニキャストとマルチキャストの前カゴセル数が加算され、クラス選択部Ｌ５により転送の指示クラスで選択されたものが前カゴセル数として伝送される。さらに、ユニキャストとマルチキャストのカゴセル数が加算され、クラス選択部Ｌ６において指示クラスで選択されたものがカゴセル数となり伝送される。そして転送指示によりカゴからクラス多重化ＦＩＦＯ４３４へ移動したセル数はユニキャストとマルチキャストとが加算され、クラス選択部Ｌ７において指示クラスで選択されて伝送される。クラス多重化ＦＩＦＯセル数はユニキャストについてのみＫＭへ伝送される。マルチキャストのクラス多重化ＦＩＦＯセル数は、クラス毎マルチキャストセル管理部４３５からのセルの出力を制御するためのバックプレッシャ信号として使用する。
【０４３８】
マルチキャストのクラス多重化ＦＩＦＯ４３６は複数の出力バッファＯＢからのバックプレッシャ信号により出力が制御されていることなどから、クラス多重化ＦＩＦＯセル数がゼロでなくともセルスイッチの出力ポートがアンダフローする可能性がある。ユニキャストセルがその影響を受けてアンダフローしないように、この構成例ではユニキャストのクラス多重化ＦＩＦＯセル数とは加算していない。
【０４３９】
ここで、マルチキャストセルの優先制御およびＶＣ間公平キューイングについて説明する。
【０４４０】
マルチキャストＶＣをスループットの視点で考える。一般的に、ある時点のセルスイッチの状態を考えると、その複数の出力ポートには、輻輳している出力ポートもあれば、負荷が低い出力ポートもある。つまり、ＶＣが使用できるスループットは出力ポートによって異なることになる。マルチキャストＶＣは、ひとつの入力ポートから複数の出力ポートへ同じスループットが同時に出力されるから、そのマルチキャストＶＣが得ることのできるスループットは出力先の中で最も輻輳している出力ポートのスループットになるのがよい。従って、ＩＢからマルチキャストセルを出力する場合は、最も輻輳している出力ポートのスループットで出力することが望ましい。
【０４４１】
ある出力ポートのあるクラスに与えられるＶＣ（ＣＧ）あたりのスループットを、ＩＢは前カゴ４４１からカゴ４４０への単位カゴの転送指示の頻度より知ることができる。また、ある出力ポートのあるクラスに与えられるスループットを、ＩＢはカゴ４４０からクラス多重化ＦＩＦＯ４３４へのセルの転送指示の頻度より知ることができる。さらにある出力ポートに与えられるスループットを、ＩＢは低優先セル用バックプレッシャ信号の頻度より知ることができる。これらの転送指示やバックプレッシャ信号は出力ポート毎に与えられる。
【０４４２】
最も輻輳している出力ポートのスループットで出力するためには、マルチキャストセルを、そのセルの出力ポートの全てに関してこれらの信号が指示または許可した時点で転送すればよい。複数の出力ポートへの指示または許可は同時である必要はない。
【０４４３】
ＩＢにおいて、低優先マルチキャストＶＣを管理する場合、本来そのクラス毎かつ出力ポートパターン毎に管理することが望ましいのであるが、一般的にはその組合せの数は大きく、また通信中にその出力ポート数が増減する可能性があるため、その様な実装は現実的ではない。図２５に示すようなカゴスイッチでは全てのマルチキャストコネクションをクラス毎にのみ管理し、出力ポートパターン毎での管理はしない。ある程度のＨＯＬ（Ｈｅａｄ Ｏｆ Ｌｉｎｅ）ブロッキングが発生することになる。
【０４４４】
図３２は、クラス毎マルチキャストセル管理部４３５を説明するための図である。この管理部は、出力ポート表、ＶＣ間公平キュー、単位カゴセル数、カゴセル数、出力許可済みセル数を保持し、管理するものである。
【０４４５】
クラス毎ユニキャストセル管理部４３３が前カゴとカゴでセルを管理していたのに対して、クラス毎マルチキャストセル管理部４３５は前カゴに相当するＶＣ間公平キュー４６０のみによりセルを管理する。ただ本発明のクラス毎マルチキャストセル管理部４３５は、管理の計算上では前カゴ、カゴの概念を用いてユニキャストと同様のセル管理を行なう。
【０４４６】
クラス毎マルチキャストセル管理部４３５は、出力ポート毎に次の情報を入力する。
【０４４７】
・前カゴからカゴへの単位カゴ転送指示
・カゴからクラス多重化ＦＩＦＯへのセル転送指示
また出力ポート毎に次の情報を出力する。
【０４４８】
・前カゴセル数
・カゴセル数
・転送セル数
ＶＣ間公平キュー４６０は単位カゴのＦＩＦＯである。ＶＣ間公平キュー４６０に入力したセルは、各ＶＣ（ＣＧ）についてひとつの単位カゴに予め定められた数までしか入力できない。この構成は図３０で説明したユニキャストの前カゴの構成と同様である。クラス多重化ＦＩＦＯ４３６からバックプレッシャ信号が入力しており、状況によってＶＣ間公平キュー４６０からのセル出力を禁止する。
【０４４９】
出力ポート表は、出力ポート別に、前カゴセル数と先頭単位カゴへのポインタを記憶する。前カゴセル数は単位カゴセル数の合計、先頭単位カゴは計算上の前カゴの先頭の単位カゴへのポインタである。
【０４５０】
単位カゴセル数はＶＣ間公平キュー４６０の単位カゴに対応して出力ポート毎のデータを記憶する。基本的には対応する単位カゴに蓄積しているマルチキャストセルの出力ポート毎のセル数を記憶する。例えば、図３２のＶＣ間公平キュー４６０の先頭の単位カゴには５セル蓄積されている。そのうち、ポート＃１とポート＃Ｎに出力するセルが３セル、ポート＃１とポート＃２に出力するセルが２セルあるので、単位カゴセル数のポート＃１には５、ポート＃２には２、ポート＃Ｎには３が記憶される。
【０４５１】
カゴセル数は計算上のカゴのセル数である。また、出力許可済みセル数は計算上の出力を許可されたセル数である。
【０４５２】
ある出力ポートに対して単位カゴ転送を指示された場合、その出力ポートの先頭単位カゴの単位カゴセル数をカゴセル数に加算し、単位カゴセル数をゼロにする。さらにその出力ポートのカゴセル数から１を減算して出力許可済みセル数に１を加算する。そして出力ポート表の先頭単位カゴのポインタをＶＣ間公平キュー４６０の次の単位カゴへひとつ進める。このときの転送セル数は１セルである。
【０４５３】
先頭単位カゴのポインタを進めることにより、ポインタはＶＣ間公平キュー４６０の先頭の単位カゴから離れていく。この距離に上限を設け、ある距離になったら単位カゴ転送指示を無視してポインタを進めないように制御する。これは、単位カゴの転送が指示された時刻と実際にセルを出力する時刻との差を大きくしないようにする効果がある。
【０４５４】
ある出力ポートに対してＫＭからセル転送が指示された場合、その出力ポートのカゴセル数から１を減算して出力許可済みセル数に１を加算する。このときの転送セル数は１セルである。
【０４５５】
クラス多重化ＦＩＦＯ４３６からのバックプレッシャ信号が出力を許可している時、セルをＶＣ間公平キュー４６０から出力することができる。その際、そのセルの全ての出力ポートについて出力許可済みセル数を１ずつ減算する。出力許可済みセル数がゼロの出力ポートが存在する場合は減算できないので、そのセルはまだ出力できない。
【０４５６】
出力許可済みセル数は単位カゴ転送指示およびセル転送指示により増加する。ある出力ポートの出力許可済みセル数がある値以上になった場合には、その出力ポートについて、クラス毎マルチキャストセル管理部４３５から出力する前カゴセル数とカゴセル数をゼロとし、単位カゴ転送指示とセル転送指示を無視する。これは実際のセルの転送スループット以上の転送指示を無視する効果がある。
【０４５７】
次に、図３３〜図３９を参照して、クラス毎マルチキャストセル管理部の動作について説明する。
【０４５８】
図３２の状態から、出力ポート＃１に対して単位カゴの転送をＫＭから指示された場合の動作を図３３に示す。ポート＃１の先頭単位カゴの単位カゴセル数をカゴセル数に加算し、単位カゴセル数ゼロにする。さらにポート＃１のカゴセル数から１を減算して出力許可済みセル数に１を加算する。ＫＭへの転送セル数は出力ポート＃１に関して１セルである。
【０４５９】
出力ポート表の先頭単位カゴのポインタをＶＣ間公平キュー４６０の次の単位カゴへひとつ進める。
【０４６０】
さらに、出力ポート＃１に対してセルの転送をＫＭから指示された場合の動作を図３４に示す。ポート＃１のカゴセル数から１を減算して出力許可済みセル数に１を加算する。ＫＭへの転送セル数は出力ポート＃１に関して１セルである。
【０４６１】
図３４のＶＣ間公平キュー４６０の先頭のセルの出力ポートは＃１と＃Ｎである。出力許可済みセル数は出力ポート＃１に関してはゼロでない（＝２）が、出力ポート＃Ｎに関してはゼロであるのでまだセルを出力することはできない。
【０４６２】
セルが到着した時の動作を図３５に示す。到着したセルの出力ポートは＃１と＃Ｎである。またこのセルは今までにＶＣ間公平キュー４６０に蓄積していなかったＶＣのセルであるとする。この場合セルはＶＣ間公平キュー４６０の先頭の単位カゴに入力される。
【０４６３】
セルを入力したとき、そのセルの全ての出力ポートの単位カゴセル数を１ずつ加算する。加算する単位カゴは出力ポート毎に決定する。基本的にはセルを入力した単位カゴに１を加えるが、出力ポート表の先頭単位カゴがセルを入力した単位カゴよりも後ろにある場合は出力ポート表の先頭単位カゴが指している単位カゴセル数に１を加える。従って、図３５では出力ポート＃１については先頭単位カゴが指している２番目の単位カゴの単位カゴセル数に１を加算する。出力ポート＃Ｎについてはセルを入力した単位カゴである１番目の単位カゴの単位カゴセル数に１を加算する。
【０４６４】
さらに、またセルが到着した時の動作を図３６に示す。新たに到着したセルの出力ポートは＃１と＃２である。またこのセルは現在ＶＣ間公平キュー４６０にセルが蓄積しているＶＣのセルであるとする。図３６の場合このセルはＶＣ間公平キュー４６０の末尾に新たに単位カゴを設け、その単位カゴに入力した。
【０４６５】
さらに、図３７に出力ポート＃Ｎに対して単位カゴの転送をＫＭから指示された場合の動作を示す。ポート＃Ｎの先頭単位カゴの単位カゴセル数をカゴセル数に加算し、単位カゴセル数ゼロにする。さらにポート＃Ｎのカゴセル数から１を減算して出力許可済みセル数に１を加算する。ＫＭへの転送セル数は出力ポート＃Ｎに関して１である。出力ポート表の先頭単位カゴのポインタをＶＣ間公平キュー４６０の次の単位カゴへひとつ進める。
【０４６６】
ＶＣ間公平キュー４６０の先頭のセルの出力ポートが＃１と＃Ｎであり、その＃１と＃Ｎの出力許可済みセル数がそれぞれ１以上（具体的には２と１）になったため、クラス多重化ＦＩＦＯ４３６が許可すればそのセルを出力できる。
【０４６７】
図３８にセルを出力した場合の状態を示す。出力セルの出力ポートに対応する出力許可済みセル数を１ずつ減算する。
【０４６８】
図３９に、以上のようにして連続して単位カゴ、カゴの転送が指示され、合計６セル出力したときの状態を示す。ＶＣ間公平キュー４６０の先頭の単位カゴはこの時点で空になり、その単位カゴおよび単位カゴセル数は消滅する。必然的に出力ポート表の先頭単位カゴがこの消失した単位カゴを指していることはない。次に、図４０を参照して、出力ポート選択スケジューラ４３２について説明する。
【０４６９】
出力ポート選択スケジューラ４３２に入力する、出力ポート毎のユニキャスト出力待ちセルとマルチキャスト出力待ちセルをセル選択部４７０が選択して出力ポート選択スケジューラ４３２から出力する。セル選択部４７０の選択の候補となるセルは、出力待ちセルのうち許可されたセルである。
【０４７０】
ユニキャストセルは、ユニキャストセル出力許可信号生成部４７１が出力するユニキャストセル出力許可信号により出力が許可される。
【０４７１】
ユニキャストセル出力許可信号生成部４７１には、バックプレッシャ信号と非常用バックプレッシャ信号が入力する。
【０４７２】
バックプレッシャ信号は出力ポート毎である。また非常用バックプレッシャ信号は対応するバックプレッシャ信号が予め定まっている。図２５の場合は、非常用バックプレッシャ信号はＳＥ２から出力しており、そのＳＥ２の出力リンクに接続する出力バッファＯＢからのバックプレッシャ信号に対応している。
【０４７３】
バックプレッシャ信号が出力禁止を示している時、ユニキャストセル出力許可信号はその出力ポートのセルの出力を許可しない。非常用バックプレッシャ信号が出力禁止を示している場合は、その非常用バックプレッシャ信号に対応するバックプレッシャ信号が全て出力禁止を示しているものと見なして出力を許可しない。
【０４７４】
マルチキャストセルは、マルチキャストセル出力許可信号生成部４７２が出力するマルチキャストセル出力許可信号により出力が許可される。
【０４７５】
マルチキャストセル出力許可信号生成部４７２には、ユニキャストセル出力許可信号とマルチキャストセル用クラス多重化ＦＩＦＯ４３６の先頭のセルの出力ポート情報が入力する。
【０４７６】
マルチキャストセル出力許可信号生成部４７２は、マルチキャストセルの出力ポートが全て（同時にでなくてもよい）許可されたかどうかを監視する。どれかの出力ポートが許可されていない場合はマルチキャストセル出力許可信号を出力禁止とする。マルチキャストセルの全ての出力ポートが許可された時、最後に許可された出力ポートのユニキャストセル出力許可信号が出力可能を示している時間はマルチキャストセルの出力を許可する。その時間内にそのマルチキャストセルがセル選択部４７０により選択されなかった場合、およびマルチキャストセルがセル選択部４７０により選択され出力して新しいマルチキャストセルの出力ポート情報が到着した場合は、再び最初から出力ポートが全て許可されたかどうかを監視する。
【０４７７】
セル選択部４７０は、こうして出力が許可された出力待ちセルを公平に選択する。
【０４７８】
上述したように、マルチキャストセルはその出力ポートの全てのバックプレッシャ信号が同時に出力を許可していなくても出力される。すなわち、そのマルチキャストセルの出力時には、そのセルの出力ポートのバックプレッシャ信号のいくつかが出力禁止を示している可能性がある。この様な状況においてもＳＥ２のバッファが溢れないように低優先セル非常用バックプレッシャ信号が有効に作用する。
【０４７９】
上述の構成においては、低優先セル非常用バックプレッシャ信号は出力禁止を示した場合、対応する出力ポート行きのユニキャストセルおよびマルチキャストセルの両方の出力を禁止する。他の構成としては、マルチキャストセル出力許可信号生成部４７２において、ある出力ポートが一度許可されても低優先セル非常用バックプレッシャ信号が出力禁止を指示した時に許可を取り消す処理を行うなどとしてもよい。また、簡単には、低優先非常用バックプレッシャ信号が出力禁止と指示した場合は、全ての低優先マルチキャストセルの出力を禁止する構成でもよい。
【０４８０】
本発明の入力バッファＩＢは、図１５で説明したバックプレッシャ考慮キュー監視を行なう。この監視は、バックプレッシャ信号によりバックプレッシャ識別子を更新し、その値に基づいて動作する。ユニキャストセルの出力ポート毎のバックプレッシャ識別子は出力ポート選択スケジューラ４３２のユニキャストセル出力許可信号により更新し、マルチキャストセルのバックプレッシャ識別子は出力ポート選択スケジューラ４３２のマルチキャストセル出力許可信号により更新する。
【０４８１】
次に、図４１を参照して、図２５に示したカゴスイッチに用いるカゴ管理部ＫＭについて説明する。
【０４８２】
図４１は、カゴ管理部ＫＭの構成例を示したものである。
【０４８３】
ＫＭは出力ポート毎に、
・ＡＢＲ入力セル数合計。
【０４８４】
・クラス毎に、前カゴセル数合計、カゴセル数合計、転送セル数。
【０４８５】
・クラス多重化ＦＩＦＯセル数合計。
【０４８６】
といった情報を保持し、さらに、出力ポート毎に、転送指示履歴管理部４８０、クラス選択スケジューラ４８１を具備している。
【０４８７】
ＡＢＲ入力セル数合計は、ＡＢＲクラスについて各出力ポート行きの全ＩＢの合計入力セル数である。一定時間内で積算し、その周期毎にその出力ポートとペアとなるＩＢへ伝送する。所定の一定時間に達する前にＡＢＲ入力セル数合計があるしきい値以上になった場合は割り込み的にＩＢへその旨を通知する構成でもかまわない。
【０４８８】
前カゴセル数合計は、ＩＢへ入力したセルの有無とクラスの情報より、前カゴに入力したセルの合計を加算する。またＫＭが転送を指示したクラスの前カゴセル数を全てのＩＢについて合計したもので更新する。そのクラスはＫＭの転送指示履歴管理部４８０が記憶している。
【０４８９】
カゴセル数合計は、ＫＭが転送を指示したクラスのカゴセル数を全てのＩＢについて合計したもので更新する。転送を指示したクラスはＫＭの転送指示履歴管理部４８０が記憶している。
【０４９０】
転送セル数は、ＫＭが転送を指示したクラスのクラス多重化ＦＩＦＯへの転送セル数を全てのＩＢについて合計したもので更新する。転送を指示したクラスはＫＭの転送指示履歴管理部４８０が記憶している。
【０４９１】
クラス多重化ＦＩＦＯセル数合計は、クラス多重化ＦＩＦＯセル数を全てのＩＢについて合計したもので更新する。
【０４９２】
クラス選択スケジューラ３８１は、前カゴセル数合計、カゴセル数合計、転送セル数合計、クラス多重化ＦＩＦＯセル数合計などの情報よりＩＢに転送指示を行なう。過去の転送指示の履歴は転送指示履歴管理部４８０が記憶し、またクラス選択スケジューラ４８１はその履歴を利用して上記のセル数情報を修正する。
【０４９３】
図４２、図４３、図４４に、カゴ管理部ＫＭのクラス選択スケジューラ４８１で実行するスケジューリングアルゴリズムの一例を示す。このアルゴリズムは、クラスの最大帯域を制限し最小帯域を保証しつつ優先度による優先制御を行なうものである。
【０４９４】
グローバルな変数として、現在時刻を示す変数ｎｏｗがある。各クラスｉについて、最小帯域１／Ｄi 、出力義務時刻Ｔｄi 、Ｔｄi の上限を与えるパラメタＤｘi 、および最大帯域１／Ｕi 、出力禁止時刻Ｔｕi 、Ｔｕi の下限を与えるパラメタＵｘi を設定する（図４２のステップＳ１００）。
【０４９５】
各クラスｉについて、出力すべき場合は現在時刻ｎｏｗがＴｄi ＜ｎｏｗである時であり、出力が禁止される場合は現在時刻ｎｏｗがｎｏｗ＜Ｔｕi である時である。また優先順位に従って出力すべき場合は現在時刻ｎｏｗがＴｕi ＜ｎｏｗ＜Ｔｄi である時である。Ｔｄi はその上限値を定められており、Ｔｄi ＜ｎｏｗ＋Ｄｘi である。またＴｕi はその下限値を定められており、ｎｏｗ−Ｕｘi ＜Ｔｕi である。ただしＵｘi ＞０、Ｄｘi ＞Ｄi である。
【０４９６】
初期設定は、ｎｏｗをゼロに設定し、各クラスｉに対してＴｄi をＤi −Ｕi とし、Ｔｕi をｎｏｗつまりゼロにする（図４２のステップＳ１０１）。
【０４９７】
このアルゴリズムはセル周期毎に次の処理を行なう。
【０４９８】
まず、クラスがアクティブになった時の処理を行なう。具体的にはセルが無かったクラスｉにセルが到着したとき、Ｔｄi をｎｏｗとＴｄi の大きい方に更新し、Ｔｕi をｎｏｗとＴｕi の大きい方に更新する（図４３のステップＳ１０２）。
【０４９９】
次にセルを転送してもよいかどうかを判定して（図４３のステップＳ１０３）、もしそうであれば転送クラス選択および転送クラス指示を行なう（図４３のステップＳ１０４）。
【０５００】
転送クラス選択は次のような処理である。
【０５０１】
転送すべきセルがある各クラスｉの中で、
１．Ｔｄi ＜ｎｏｗとなっているクラスがあれば、その中で最もｎｏｗ−Ｔｄi の大きいクラスを選択する（同じ値の場合は優先度で判断）。
【０５０２】
２．Ｔｄi ＜ｎｏｗとなっているクラスがなければ、Ｔｕi ＜ｎｏｗ＜Ｔｄi を満足するクラスの中から優先度の最も高いクラスを選択する。
【０５０３】
選択されたクラスをｊとすると、図４４のステップＳ１０５に進み、次のような転送クラス指示の処理を行なう。
【０５０４】
１．クラスｊの転送指示を行なう。
【０５０５】
２．Ｔｕj をｍａｘ（Ｔｕj 、ｎｏｗ−Ｕｘj ）と更新。
【０５０６】
３．Ｔｄj をＴｄj ＋Ｄj と更新。
【０５０７】
４．Ｔｕj をＴｕj ＋Ｕj と更新。
【０５０８】
５．Ｔｄj をｍｉｎ（Ｔｄj 、ｎｏｗ＋Ｄｘj ）と更新。
【０５０９】
最後に、転送セル流量モニタの処理を行なった後（図４４のステップＳ１０６）、ｎｏｗをインクリメントして（図４４のステップＳ１０７）、セル周期毎の処理を終了する。
【０５１０】
図４４のステップＳ１０６の転送セル流量モニタの処理は、クラスｊの転送セル数がｘj の時、クラスｊに関して次の処理を行なう。
【０５１１】
１．Ｔｕj をｍａｘ（Ｔｕj 、ｎｏｗ−Ｕｘj ）と更新。
【０５１２】
２．Ｔｄj をＴｄj ＋（ｘj −１）Ｄj と更新。
【０５１３】
３．Ｔｕj をＴｕj ＋（ｘj −１）Ｕj と更新。
【０５１４】
４．Ｔｄj をｍｉｎ（Ｔｄj 、ｎｏｗ＋Ｄｘj ）と更新。
【０５１５】
図４３のステップＳ１０３のセルを転送指示してもよいかどうかの判定は、クラス多重化ＦＩＦＯセル数合計が、あるしきい値以下かどうかで行なう。あるしきい値とは通常は「１」である。このクラス多重化ＦＩＦＯセル数合計は転送指示履歴管理部４８０の転送指示履歴により修正された値である。
【０５１６】
図４３のステップＳ１０４における、クラスに転送すべきセルがあるかどうかの判定は、前カゴセル数合計またはカゴセル数合計のどちらか一方がゼロでないことを判定して行なう。この前カゴセル数合計とカゴセル数合計は転送指示履歴管理部４８０の転送指示履歴により修正された値である。
【０５１７】
転送指示はカゴ４４０からクラス多重化ＦＩＦＯ４３４へのセルの転送指示 （図３１の転送指示Ｔ２）である。その際に前カゴからカゴへの単位カゴの転送指示を同時に行なうかどうかの判定は、前カゴセル数合計がゼロでなく、かつ、カゴセル数合計があるしきい値以下かどうかを判定して行なう。あるしきい値とは通常は１である。この前カゴセル数合計とカゴセル数合計は転送指示履歴管理部４８０の転送指示履歴により修正された値である。
【０５１８】
本アルゴリズムは、Ｄi を大きな数に設定することにより、最小保証帯域をゼロに近付けることができる。例えば全てのクラスのＤi を大きな数に設定すれば全てのクラスを完全優先で優先制御することができる。
【０５１９】
また、クラスのひとつを、優先度は最も低いが最小保証帯域を持つＩＣ （Ｉｄｌｅ Ｃｅｌｌ）クラスとすることにより、出力ポートの使用率を制御することができる。ＩＢはＩＣクラスの転送指示があった場合にアイドルセルをクラス多重化ＦＩＦＯへ挿入する（このＩＢはひとつだけでよい）。
【０５２０】
アイドルセルは他のセルと同様にセルスイッチの出力ポートに向けて交換され、そこでＵｎａｓｓｉｇｎｅｄ Ｃｅｌｌに置き換えられる。ＫＭは、ＩＣクラスはいつも転送すべきセルがある状態と考えスケジューリングを行なえば良い。
【０５２１】
ところで、図４２〜図４４に示したアルゴリズムでは説明を簡単にするために、変数ｎｏｗ、Ｔｄi 、Ｔｕi といった時刻を示す変数は、表現できる値が上限を持たないとしている。実装時にはこれらの変数は有限のビット長を持つレジスタなどで表現するため長時間経過すると同じ時刻が循環して現われる。アルゴリズムを正常に動作させるためには次のようなことを行なえば良い。これらの周期をＭaxとする。Ｍaxは十分大きい必要がある。
【０５２２】
このとき、ｘ：＝ｆ（ｘ）などの計算は、
ｘ：＝ｆ（ｘ ） ｍｏｄ Ｍax
と置き換える。つまりＭaxでモジュロをとる。また、ｙ＜ｚの比較演算は、
（ｚ＜ｙ−Ｍax／２）ｏｒ（（ｙ＜ｚ）ａｎｄ（ｚ＜ｙ＋Ｍax／２））
に置き換え比較する。
【０５２３】
例えば、ｎｏｗ：＝ｎｏｗ＋１という計算は、
ｎｏｗ：＝（ｎｏｗ＋１） ｍｏｄ Ｍax
と置き換える。Ｔｄi ＜ｎｏｗという比較演算は、
（now ＜Tdi −Max/2) or ((Tdi ＜now) and (now ＜Tdi ＋Max/2)) に置き換え比較すれば良い。
【０５２４】
時刻の変数は周期的に監視し、必要に応じてｎｏｗからＭax／２以上離れ過ぎないように調整を行なうことが必要であるが、Ｍaxを大きくとることによって監視の周期を長くとることができ、実装が容易となる。
【０５２５】
さらに、他のクラス選択スケジューリングとしては次のようなものを有効である。
【０５２６】
すでに説明したように、ＣＧ毎（ＶＣ毎）に設定された重みに従ってＶＣ間公平キューイングを行ったセルバッファ装置は、入力バッファＩＢのＣＧテーブル（図３０）またはＶＣテーブルのＮx に重みを書き込む。
【０５２７】
ここでは、クラス選択スケジューリングを併用することによって、そのクラスに設定されているＶＣ毎の重みを係数倍できることを説明する。
【０５２８】
クラスＡ、クラスＢがあり、クラスＡに設定されているあるＶＣの重みＮxaとし、クラスＢに設定されているあるＶＣの重みをＮxbとする。このとき双方のクラスに出力待ちセルが存在するときにクラス選択スケジューリングにより単位カゴの転送指示回数をクラスＸとクラスＹでＲa 対Ｒb の比になるようにスケジューリングすることにより、それぞれの重みを Ｎxa×Ｒa 、Ｎxb×Ｒb と係数倍することが可能である。３クラス以上の場合も同様である。所望の比になるように、スケジューリングを行うアルゴリズムとして例えば、ＳＣＦＱ（Ｓｅｌｆ−Ｃｌｏｃｋｅｄ Ｆａｉｒ Ｑｕｅｕｅｉｎｇ）などが知られている。
【０５２９】
具体的な例で説明する。例えば、ＶＣ１からＶＣ７の７本のＶＣに重みをそれぞれ１．２４、３．７２、２．１８、９３４、５６２、１３７０、４３６０に設定したいとする。クラスＡにＶＣ１、２を設定し、Ｎx をそれぞれ１．２４、３．７２とする。クラスＢにＶＣ３を設定し、Ｎx を２．１８とする。クラスＣにＶＣ４、５を設定し、Ｎx をそれぞれ９．３４、５．６２とする。クラスＤにＶＣ６、７を設定し、Ｎx をそれぞれ１．３７、４．３６とする。単位カゴの転送指示回数を出力待ちセルが存在するクラス間でクラスＡ：クラスＢ：クラスＣ：クラスＤ＝１：１：１００：１０００の比になるようにクラス選択スケジューリングを行えば、目的の重み１．２４：３．７２：２．１８：９３４：５６２：１３７０：４３６０でセルが出力ポートに多重化される。この方法はＮx の値として大きな数値を設定するとＶＣ間公平キューイングのセル遅延揺らぎが増大してしまうという現象を回避する効果がある。
【０５３０】
図４２〜図４４に示したようなクラス選択スケジューリングのアルゴリズムでは、各クラスの転送セル流量をモニタしていた。これを利用して階層的なクラス選択スケジューリングを行うことが可能である。
【０５３１】
クラスＡ１、Ａ２、Ａ３、…からなるクラス群Ｇa と、別のクラスＢ１、Ｂ２、Ｂ３、…からなるクラス群Ｇb とがあるとき、出力待ちセルが存在するクラス群間で転送セル流量の比をＲa 対Ｒb と設定してクラス選択スケジューリングを行う。クラス群が３以上の場合も同様である。各クラス群内のクラス選択スケジューリングと、クラス群間の選択スケジューリングとは独立である。
【０５３２】
これにより、あるクラス群間の剰余帯域は、そのクラス群内のクラスのみが使用することになり、別のクラス群が使用できることを防止できる。別のクラス群がこの剰余帯域を使用できるのは、あるクラス群の出力待ちセルが一つも存在しない場合だけである。この様な階層的なクラス選択スケジューリングは。例えば、企業毎にクラス群を割り当てるなどの応用が考えられる。
【０５３３】
５．２ 優先制御およびＶＣ間公平キューイングを行うセルスイッチのセル数修正方法
次に、優先制御およびＶＣ間公平キューイングを行うセルスイッチ（カゴスイッチ）（図２５、図２９、図３１）のカゴ管理部ＫＭにおけるセル数の修正方法を図４５を参照して説明する。
【０５３４】
修正の原理は、図１９、図２０などを用いて説明したカゴスイッチの場合も同じ方法でセル数を修正することにより優先制御の性能や出力ポートのスループットの向上などを実現することができる。
【０５３５】
本発明のセル数修正方法の一応用例として、図４５に示すカゴスイッチに適用する。カゴスイッチでは、管理部３０１がクラスｉの前カゴ（Ｂpi）へ転送を指示すると、そのクラスの前カゴのセルがカゴ（Ｂki）へ転送されるとともに、その一部がクラス多重化ＦＩＦＯ（Ｂm ）へ転送される。管理部３０１がクラスｉのカゴからクラス多重化ＦＩＦＯへ転送を指示すると、そのクラスのカゴのセルがクラス多重化ＦＩＦＯへ転送される。
【０５３６】
図４５の様に各セルバッファのセル数情報および遅延時間を定める。
【０５３７】
Ｈpiは転送指示Ｉpiにより前カゴからカゴへ転送されるＨＯＬ数、Ｈpmi は同じく転送指示Ｉpiにより前カゴからクラス多重化ＦＩＦＯへ転送されるＨＯＬセル数である。
【０５３８】
ここで一例として、各遅延時間の値が等しい場合について考える。つまり、ＤＯp ＝ＤＩk ＝ＤＯk ＝ＤＩm ＝Ｄｉpm＝Ｄ、および、ＤＴpm＝ＤＴkmとする。またｐ＝［−Ｄ、０）とする。このとき、クラスｉの前カゴとカゴの修正されたセル数（Ｎ′pi、Ｎ′ki）、およびクラス多重化ＦＩＦＯの修正されたセル数 （Ｎ′m ）は次のように計算できる。
【０５３９】
【数７】

【０５４０】
５．３ 第１０の実施形態に係るセルスイッチの説明の続き
図４６に、カゴスイッチの入力バッファＩＢとカゴ管理部ＫＭとの接続例を示す。
【０５４１】
ここでは、例えば、クラス数を６２クラス、セルスイッチサイズを１６入力１６出力とする。
【０５４２】
クラス番号は、｛０、１、２、…、６０、６１、ＵＣ、ＩＣ｝と６ビットにコーディングする。
【０５４３】
クラスＵＣは非割り当てセル（Ｕｎａｓｓｉｇｎｅｄ Ｃｅｌｌ）、ＩＣはアイドルセル（Ｉｄｌｅ Ｃｅｌｌ）を示し、これらの使い方は以下に記述する。
【０５４４】
前カゴセル数、カゴセル数、クラス多重化ＦＩＦＯセル数は、｛０、１、２、…、１３、１４、１５以上｝と４ビットにコーディングする。
【０５４５】
入力バッファＩＢからカゴ管理部ＫＭへの転送情報を以下に示す。
【０５４６】
（１）入力セル 出力ポート毎に、入力したセルについて（ユニキャストの場合はひとつの出力ポートについてのみ出力する）、
・入力セルの有無とクラス…６ビット
（入力セルがない場合はクラスＵＣを送信する）
（３）転送指示クラス 出力ポート毎に転送の指示クラスについて、
・転送後の前カゴセル数…４ビット
・転送後のカゴセル数…４ビット
・クラス多重化ＦＩＦＯへの転送セル数…２ビット
（最大でユニキャストとマルチキャストの２セルが転送される）
（４）クラス多重化ＦＩＦＯ 出力ポート毎にユニキャストのみの、
・クラス多重化ＦＩＦＯセル数…４ビット
合計すると、ひとつの出力ポートに関する情報は２０ビットである。
【０５４７】
カゴ管理部ＫＭから全ての入力バッファＩＢへ同報する転送情報を以下に示す。
【０５４８】
（２）出力ポート毎に、
・前カゴからカゴへ単位カゴの転送指示（下記のクラスについて）…１ビット
・カゴからクラス多重化ＦＩＦＯへセルの転送指示と、指示クラス…６ビット
（転送指示をしない場合はＵＣクラスを指定。ＩＣクラスが指定された場合はＩＢはアイドルセルを転送（挿入）する。アイドルセルは他のクラスのセルと同様に出力ポートへ交換転送され、セルスイッチからの出力時にＵｎａｓｓｉｇｎｅｄ Ｃｅｌｌに置き換えられるスループット調整用のセルである。）
合計すると、ひとつの出力ポートに関する情報は７ビットである。
【０５４９】
ＫＭは、ＡＢＲトラヒック制御のため出力ポート毎に、対応するＩＢへ次の信号を送信する。
【０５５０】
（５）全ＩＢの入力セルのうち、各出力ポート行きのＡＢＲ入力セル数…５ビット
（１６入力１６出力のセルスイッチの場合）
ひとつの出力ポートに関する情報は５ビットである。
【０５５１】
図４６は、カゴ管理部ＫＭをふたつのＬＳＩにて実現する構成例を示したものである。ふたつのＬＳＩのうち一方は出力ポート＃１から＃８を管理し、もう一方は出力ポート＃９から＃１６を管理する。
【０５５２】
ＩＢからＫＭへの転送情報（前述の（１）（３）（４））は、１出力ポートあたり２０ビットであるから、８ポート分で１６０ビットである。高速差動伝送を２ペア用いてパラレル伝送を行なえば１セル周期に８０ビットの伝送速度でよい。
【０５５３】
ＫＭからＩＢへの同報情報（前述の（２））は、１出力ポートあたり７ビットであるから、８ポート分で５６ビットである。通常の伝送ドライバを用いて、８本のパラレル伝送を行なえば１セル周期に７ビットの伝送速度でよい。
【０５５４】
ＫＭからＩＢへのＡＢＲトラヒック制御のための情報（前述の（５））は、１出力ポートあたり５ビットである。
【０５５５】
セル伝送速度が６２２Ｍｂｐｓであるセルスイッチを考えても、これらの伝送速度は現在の技術において十分実現可能である。
【０５５６】
ＩＢはＫＭへセル数情報をＬＳＢ（最下位桁）から伝送することにより、セル数の加算の回路規模を少なくすることができる。加算回路は全てのＩＢから伝送されてくるセル数情報を（出力ポート毎クラス毎に）下位桁から順に加算することができるためである。より具体的には、加算回路は入力した桁の数字とそれまでに計算した下位桁からの桁上がりの和を計算して、加算結果のその桁の値を得ることができる。加えて次の桁の計算のための桁上がりを保持する。
【０５５７】
ＩＢからＫＭへの信号の中にクラス多重化ＦＩＦＯセル数がある。バックプレッシャ付きセルスイッチが出力ポート毎の蓄積セル数（図２５の出力バッファＯＢのセル数）を出力できる場合には、ＫＭは、クラス多重化ＦＩＦＯセル数の代わりにこの出力ポート毎蓄積セル数を用いても良い。
【０５５８】
これは、図２のクラス間の優先制御を行なうセル多重化装置や、図７のＶＣ間公平キューイングを行なうセル多重化装置と同じ効果を持つ。
【０５５９】
図４７に、ＡＢＲサービスを実現するための情報の経路を示す。
【０５６０】
図４７は、ポート＃１からポート＃Ｎに入力するＡＢＲクラスのセルが、バックプレッシャ付きセルスイッチ４００によりポート＃ｉに交換多重化される部分について特に抜き出して示してある。実際は全ての出力ポートに関して、この図の＃ｉと同じ構成になっている。
【０５６１】
ＡＢＲサービスは、セルスイッチの出力ポートに使用可能な帯域があれば、その帯域をＡＢＲクラスのＶＣで公平に分配して使用するサービスクラスである。トラヒック制御には受信端末から送信端末へ伝送されるＲＭセルを用いる。
【０５６２】
セルスイッチ４００は、出力ポート＃ｉにおいてＡＢＲが使用可能な帯域を知っており、それと現在のＡＢＲの入力トラヒックとの比（または差）を知ることにより、送信端末に対してトラヒック制御を行なうことができる。現在のＡＢＲトラヒックは図４７に示したポート＃ｉ行きの入力セル数の一定周期毎の合計から知ることができる。入力セル数から入力帯域を求め、これが出力ポートにおいてＡＢＲが使用可能な帯域を越えていれば過負荷であるから、ポート＃ｉに入力するＲＭセルにＶＣの帯域を減らす指示を書き込めばよい。逆に、ポート＃ｉ行きの入力セル数から求めた入力帯域が、出力ポートにおいてＡＢＲが使用可能な帯域を下回っていれば、低負荷であるから、ポート＃ｉに入力するＲＭセルにＶＣの帯域を増やす指示を書き込めばよい。入力帯域と出力帯域の比または差を知ることにより、過負荷、低負荷の程度を知ることができ、細やかな制御を行なうことが可能である。
【０５６３】
この処理により輻輳に陥る確率は少なくなるが、さらにＩＢにおいてキュー長を監視して輻輳を検出した場合はＥＦＣＩをマークしたり、ＲＭセルを書き換えたりすることにより、より安全にトラヒックを制御することが可能である。特にマルチキャストの場合は、入力帯域が出力帯域より小さくとも過負荷となる可能性があり、その場合はキュー長監視によるトラヒック制御が重要になる。
【０５６４】
このように、第１０の実施形態に係るカゴスイッチは、ＶＣ間公平キューイングを行なうため、キュー長監視によるトラヒック制御においてもＶＣ間で公平な帯域分配を実現することが可能である。
【０５６５】
【発明の効果】
以上説明したように、本発明のクラス間の優先制御を行なうパケット転送装置（第１、第２の実施形態（請求項１、２、３、４、））によれば、制御部（クラス管理部）が複数の入力バッファ全体の状況を把握して（少なくとも全体の状況を把握していればよいが、個々の入力バッファ毎に把握していても構わない）指示を出すため、各入力バッファのクラス毎の蓄積状況の違いによりクラス間の優先関係が崩れてしまうことが生じず、また、入力ポートの数すなわち入力バッファの数が増えても容易にクラス間の優先制御を実現できる。
【０５６６】
また、複数の入力バッファにまたがってＶＣ（フロー）間公平キューイングをするために、例えば、制御手段が全ての入力バッファの全てのＶＣ（フロー）について、その入力ポート番号とＶＣ番号、パケットの到着状況、出力状況等を把握してパケットの出力順序を制御するのでは、装置構成が複雑になり、スループットの向上が難しい。そこで、本発明のパケット転送装置（第３、第４、第５の実施形態（請求項５、６））によれば、あるフェーズ（その時間的長さは不定）内で出力されるべきパケット集合（カゴ）という概念を導入し、このパケット集合に入れるパケットの選択と、このパケット集合に入っているパケットのみを出力する（その他のパケットは出力が許可されない）という処理を各入力バッファが分担し、パケット集合に新たなパケットを入れるタイミングを指示する処理をカゴ管理部が分担することにより、例えば、入力バッファ方式のセルスイッチにおいて、ＶＣ（フロー）間公平キューイングを容易に実現できる。
【０５６７】
また、本発明のパケット転送装置（第６、第７の実施形態（請求項７、８））によれば、制御手段（バッファポインタ管理部）がパケットが入力されたときに複数の集合への振り分けが行われており、パケットを出力するときには１つの集合に属するポインタを出すだけで済むので、例えば設定すべきＶＣ数が増えても高速にＶＣ（フロー）間公平キューイングのための出力すべきパケットの選択が実現できる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係るクラス間の優先制御を行なうセル多重化装置の構成例を示した図。
【図２】本発明の第２の実施形態に係るクラス間の優先制御を行なうセル多重化装置の他の構成例を示した図。
【図３】出力バッファの他の構成例を示した図。
【図４】出力バッファのさらに他の構成例を示した図。
【図５】本発明の第３の実施形態に係るＶＣ毎ＦＩＦＯを備えた出力バッファ型セル多重化装置の構成例を示した図。
【図６】本発明の第４の実施形態に係る：ＶＣ間公平キューイングを行なうセル多重化装置の構成例を示した図。
【図７】本発明の第５の実施形態に係るＶＣ間公平キューイングを行なうセル多重化装置の構成例を示した図。
【図８】本発明の第６の実施形態に係るセルグループＦＩＦＯを用いるセルバッファ装置の構成例を示した図。
【図９】本発明の第７の実施形態に係るセルグループＦＩＦＯを用いるセルバッファ装置の構成例を示した図。
【図１０】第６の実施形態に係るセルグループＦＩＦＯのポインタチェーンによるデータ構造例を説明するための図。
【図１１】第６の実施形態に係るセルグループＦＩＦＯのポインタチェーンによるデータ構造例を説明するための図で、空きセルグループチェーンの構成を示している。
【図１２】第７の実施形態に係るセルグループＦＩＦＯのポインタチェーンによるデータ構造例を説明するための図。
【図１３】第７の実施形態に係るセルグループＦＩＦＯのポインタチェーンによるデータ構造例を説明するための図で、空きセルグループチェーンの構成を示している。
【図１４】パケットグループを用いたフロー間公平キューイングを説明するための図。
【図１５】パケットグループを用いたフロー間公平キューイングを用いたパケットバッファ装置の動作を説明するための図。
【図１６】本発明の第８の実施形態にかかるバックプレッシャ考慮キュー監視を説明する図である。
【図１７】第８の実施形態に係るバックプレッシャ考慮キュー監視部を持つセルバッファ装置の構成例を示した図。
【図１８】第８の実施形態に係るバックプレッシャ考慮キュー監視アルゴリズムを示したフローチャート。
【図１９】本発明の第９の実施形態に係る遅延を考慮したセルバッファ装置の構成例を示した図。
【図２０】遅延を考慮したセル数情報の修正方法の基本原理を説明するための図。
【図２１】セル数修正方法の他の基本原理を説明するための図。
【図２２】図２１のセル数修正方法に用いる基本的な関数ｆ（）を説明するための図。
【図２３】図２１のセル数修正方法に用いる基本的な関数ｇ（）を説明するための図。
【図２４】図２１のセル数修正方法に用いる基本的な関数Ｓｃ（）を説明するための図。
【図２５】本発明の第１０の実施形態に係るカゴスイッチの全体の構成例を示した図。
【図２６】図２５の出力バッファの構成例を示した図。
【図２７】図２５の１段目単位スイッチの構成例を示した図。
【図２８】図２５の２段目単位スイッチの構成例を示した図。
【図２９】図２５の入力バッファの構成例を示した図。
【図３０】入力バッファのキューイング処理を説明するための図。
【図３１】図２５の入力バッファのカゴ管理部とのインタフェースを示した図。
【図３２】図２９のクラス毎マルチキャストセル管理部の動作を説明するための図。
【図３３】図２９のクラス毎マルチキャストセル管理部の動作を説明するための図。
【図３４】図２９のクラス毎マルチキャストセル管理部の動作を説明するための図。
【図３５】図２９のクラス毎マルチキャストセル管理部の動作を説明するための図。
【図３６】図２９のクラス毎マルチキャストセル管理部の動作を説明するための図。
【図３７】図２９のクラス毎マルチキャストセル管理部の動作を説明するための図。
【図３８】図２９のクラス毎マルチキャストセル管理部の動作を説明するための図。
【図３９】図２９のクラス毎マルチキャストセル管理部の動作を説明するための図。
【図４０】図２９の出力ポート選択スケジューラの構成例を示した図。
【図４１】図２５のカゴ管理部の構成例を示した図。
【図４２】図４１のカゴ管理部のクラス選択スケジューラで実行する、最大帯域を制限し最小帯域を保証するスケジューリングアルゴリズムの具体例を示したフローチャート。
【図４３】図４１のカゴ管理部のクラス選択スケジューラで実行する、最大帯域を制限し最小帯域を保証するスケジューリングアルゴリズムの具体例を示したフローチャート。
【図４４】図４１のカゴ管理部のクラス選択スケジューラで実行する、最大帯域を制限し最小帯域を保証するスケジューリングアルゴリズムの具体例を示したフローチャート。
【図４５】セル数情報の修正方法の応用例であるカゴスイッチの動作を説明するための図。
【図４６】図２５の入力バッファとカゴ管理部との接続の具体例を示した図。
【図４７】ＡＢＲサービスのための情報の経路の具体例を示した図。
【図４８】従来のＵＢＲサービスにおける不公平な帯域割り当てについて説明するための図。
【図４９】従来のクラス間の優先制御を行うセル多重化装置の構成を説明するための図。
【図５０】従来の入力バッファを持つセル多重化装置の構成を説明するための図。
【図５１】従来のＶＣテーブルの検索が必要なセルバッファ装置の構成を説明するための図。
【図５２】図５０に示すような従来の入力バッファを持つセル多重化装置における入力バッファのキュー長の変化について説明するための図。
【図５３】従来の優先制御を行うセル多重化装置の構成を説明するための図。
【符号の説明】
１０…入力バッファ、１１…出力バッファ、１２…クラス管理部、２１２、２２２…カゴ管理部、２３０、２４０…バッファポインタ管理部、２８２…キュー監視部、３０２…転送指示履歴、ＫＭ…カゴ管理部、４００…バックプレッシャ付きセルスイッチ。

Claims (8)

1. 入力されたパケットを一時的に蓄積する複数の入力バッファと、これら入力バッファを制御する制御手段と、前記各入力バッファから出力されるパケットを転送する少なくとも１つの出力ポートを具備したパケット転送装置であって、
   前記各入力バッファは、入力したパケットを一時的にクラス毎に蓄積するクラス毎の蓄積手段と、
   前記制御手段から指示されたクラスのパケットを前記蓄積手段から前記出力ポートへ向けて出力する出力手段とを具備し、
   前記制御手段は、
   前記蓄積手段の複数の入力バッファ全体における蓄積状況をクラス毎に把握し、この蓄積状況に基づいてパケットを出力すべきクラスを決定し、この決定したクラスの指定を含む指示を前記複数の入力バッファに送信することを特徴とするパケット転送装置。
2. 前記出力ポートは、前記入力バッファから出力されたパケットを一時的に蓄積する出力バッファを具備し、
   前記出力手段は、前記出力バッファ内部のパケットの蓄積状況に応じてパケットを前記出力ポートへ向けて出力することを特徴とすることを特徴とする請求項１記載のパケット転送装置。
3. 前記出力手段は、前記蓄積手段から出力されたパケットを多重化し、この多重化されたパケットを前記出力ポートに出力する多重化手段を具備し、
   前記制御手段は、前記蓄積状況に加えて、前記多重化手段の複数の入力バッファ全体における多重化状況を把握し、前記蓄積状況および前記多重化状況に基づいてパケットを出力すべきクラスを決定することを特徴とする請求項１記載のパケット転送装置。
4. 前記入力バッファは、複数の入力バッファにまたがる同一クラス内で、各パケットの属する各仮想コネクション間でパケットの転送が公平になるように前記蓄積手段から出力するパケットを選択することを特徴とする請求項１記載のパケット転送装置。
5. 入力されたパケットを一時的に蓄積する複数の入力バッファと、これら入力バッファを制御する制御手段と、前記各入力バッファから出力されるパケットを転送する少なくとも１つの出力ポートを具備したパケット転送装置であって、
   前記各入力バッファは、
   入力したパケットを一時的に蓄積する蓄積手段と、
   前記制御手段からの指示を受けて、次のフェーズで前記蓄積手段から前記出力ポートへ向けて出力すべきパケットを選択する選択手段と、
   この選択手段で選択されたパケットを前記出力ポートに向けて出力する出力手段とを具備し、
   前記制御手段は、
   前記複数の入力バッファ全体における前記選択手段で選択されたパケットの出力状況を把握し、この出力状況に基づいて新たなパケットを選択するよう前記複数の入力バッファに指示することを特徴とするパケット転送装置。
6. 前記各入力バッファの選択手段は、それぞれ、
   各パケットの属する各仮想コネクション間でパケットの転送が公平になるように前記蓄積手段から出力するパケットを選択することを特徴とする請求項５記載のパケット転送装置。
7. 入力したパケットを一時的に蓄積するバッファと、このバッファを制御する制御手段と、前記バッファから出力されたパケットを転送する少なくとも１つの出力ポートを具備したパケット転送装置であって、
   前記制御手段は、
   前記バッファ内に蓄積されたパケットを複数の集合に分けて管理する管理手段と、
   前記バッファに入力したパケットを各パケットの属するフロー間で公平になるように前記複数の集合のいずれか１つに振り分ける振り分け手段と、
   前記管理手段で管理されている前記複数の集合のうちの１つの集合に属するパケットを前記出力ポートに向けて出力するよう前記バッファに対し指示する指示手段と、
   を具備したことを特徴とするパケット転送装置。
8. 前記振り分け手段は、前記バッファに入力したパケットを、そのパケットの属するフローの識別情報と、各フローに対して定められた重み及び入力したパケットの長さの少なくとも一方とに基づいて前記複数の集合のいずれか１つに振り分けることを特徴とする請求項７記載のパケット転送装置。

Images