(57)【特許請求の範囲】
【請求項１】
全伝送帯域を等比的に区切って定義された複数の帯域の各々に対応付けられた、各々が複数のステップに区分された複数の連鎖待ち行列を有し、
コネクションを、当該コネクションの帯域に応じて、その帯域に対応付けられた前記複数の連鎖待ち行列のいずれかに登録して管理するセル送出管理装置であって、
前記複数の連鎖待ち行列の各々のステップに対応して、各々のステップに蓄積されているセル数、各々のステップに蓄積されている先頭セルおよび最後尾セルを指示するポインタを格納する記憶部とを有し、
前記記憶部は、前記複数の連鎖待ち行列の各々の先頭ステップに対応して、それらの先頭ステップに蓄積されているセル数、各々のステップに蓄積されている先頭セルおよび最後尾セルを指示するポインタを格納する複数のレジスタと、
前記複数の連鎖待ち行列の各々の先頭ステップ以外のステップに対応して、それらの先頭ステップに蓄積されているセル数、各々のステップに蓄積されている先頭セルおよび最後尾セルを指示するポインタを格納する記憶装置とを有し、
前記記憶装置は、前記複数の連鎖待ち行列の各々の先頭ステップ以外のステップに対応して、マトリクス状に区分された複数の記憶領域を有することを特徴とするセル送出管理装置。
【請求項２】
請求項１に記載のセル送出管理装置であって、
前記複数の連鎖待ち行列の各々の先頭ステップ以外のステップと、前記記憶装置内の複数の記憶領域とは、前記複数の連鎖待ち行列の更新タイミングをカウントすることによって得られる値から求まる関係に従い、１対１に対応することを特徴とするセル送出管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、たとえばＡＴＭ（Asynchronous Transfer Mode）通信網に適用される、セル送出管理装置に関する。より詳細には、セル送出管理に際して、重み付け制御方法である等級別連鎖待ち行列を用いる上で、複数の等級別連鎖待ち行列に蓄積されているセルを効率的に管理する方法に関する。また、そのような管理方法を適用した装置に関する。
【０００２】
【従来の技術】
ＡＴＭネットワークでは、音声や映像、データ通信など、様々のトラフィック特性を持つセルを、個々の通信品質（サービス品質）を保証しつつ多重化する必要がある。現在のＡＴＭネットワークでは、通信品質クラスとしてＣＢＲ、ＶＢＲなど、いくつかのカテゴリーが定義されている。ＡＴＭスイッチでは、これらのクラスに応じて、フロー毎にセルスケジューリングが必要になる。
【０００３】
たとえば、代表的なセルスケジューリング方式として、重み付けラウンドロビン（Weighted Round Robin）、ＤＲＲ（Deficit Round Robin）、さらに、ＶＣ毎にスケジューリングを行う方法など、多数提案されている。
【０００４】
一方で、ＡＴＭネットワークでの通信速度（通信帯域）は高速化の一途をたどっており、ＡＴＭスイッチも高速化／大規模化する傾向にある。このような状況に対して、従来行われていたようなセルスケジューリング方式では、スイッチの高速化／大規模化に対応することが困難になりつつある。そこで近年では、セルフローが大規模化したとしても対応可能なアルゴリズムとして、ＣＣＱ（Chained and Classfied Queue：等級別連鎖待ち行列）が注目されるようになっている。
【０００５】
【発明が解決しようとする課題】
一般的なＣＣＱセルスケジューリング方式は、セルを帯域値毎にクラス分けし、それぞれのクラス毎に、セル送出時刻を算出したタイムテーブルを作成しする。個々のクラスは、このタイムテーブルをもとにセルスケジューリングを行ない、最後に、各クラス間で競合制御を行なって、どのクラスのセルを送出するかを決定する方式である。
【０００６】
ここで一般的なＣＣＱセルスケジューリング方式では、帯域値毎に分けられた各々のクラスは、複数のステップから構成されているものである。このステップは、一般的にはＦＩＦＯメモリとして動作する。したがってＣＣＱセルスケジューリング方式では、マトリクス状に配置されたＦＩＦＯについて、それぞれのＦＩＦＯ動作に加えて、指数的にずらしたタイミングで並列的に連鎖動作させなければならない。
【０００７】
しかし、実用的なＡＴＭスイッチを実現するためには、セルをクラス分けする等級、そして各々の等級が有するステップとも、数十〜数百という規模になる。すなわち、膨大な数のＦＩＦＯが、マトリクス状に配置されることになる。これらのＦＩＦＯを並列的に連鎖動作させるのであるから、並列的な処理量が膨大なものとなる。
【０００８】
よって、このような膨大な数のＦＩＦＯを単に並列動作させるのでは、回路規模の問題で実現性が低い。したがってこの発明は、問題となる処理を疑似化する多重化メカニズムを適用し、実用に適するセル送出管理方法およびセル送出管理装置を提供する。
【０００９】
【課題を解決するための手段】
すなわち、この発明は、全伝送帯域を等比的に区切って定義された複数の帯域の各々に対応付けられた、各々が複数のステップに区分された複数の連鎖待ち行列を有し、コネクションを、当該コネクションの帯域に応じて、その帯域に対応付けられた複数の連鎖待ち行列のいずれかに登録して管理するセル送出管理装置であって、複数の連鎖待ち行列の各々のステップに対応して、各々のステップに蓄積されているセル数、各々のステップに蓄積されている先頭セルおよび最後尾セルを指示するポインタを格納する記憶部とを有し、記憶部は、複数の連鎖待ち行列の各々の先頭ステップに対応して、それらの先頭ステップに蓄積されているセル数、各々のステップに蓄積されている先頭セルおよび最後尾セルを指示するポインタを格納する複数のレジスタと、複数の連鎖待ち行列の各々の先頭ステップ以外のステップに対応して、それらの先頭ステップに蓄積されているセル数、各々のステップに蓄積されている先頭セルおよび最後尾セルを指示するポインタを格納する記憶装置とを有し、記憶装置は、複数の連鎖待ち行列の各々の先頭ステップ以外のステップに対応して、マトリクス状に区分された複数の記憶領域を有することを特徴とする。
【００１４】
そして、少なくとも複数の連鎖待ち行列の各々の先頭ステップ以外のステップと、記憶部内の複数の記憶領域とは、各連鎖待ち行列の更新タイミングをカウントすることによって得られる値から求まる関係に従い、１対１に対応する。
【００１５】
【発明の実施の形態】
以下、図面を参照しながら、この発明の実施形態について説明する。まず図２に、この発明の第１の実施形態によるセル送出管理装置のブロック図を示す。セル送出管理装置１００には、複数のコネクションが接続されている。図２では、コネクションＡからコネクションＣまで、３本のコネクションが接続されている状態を示す。
【００１６】
セル送出管理装置１００は、セル振分部１０、等級別連鎖待ち行列２０、競合制御部３０、および制御部４０を有する。前述したコネクションＡからコネクションＣまでの複数のコネクションは、セル送出管理装置１００内のセル振分部１０に接続されている。等級別連鎖待ち行列２０は、セル振分部１０の出力側に接続されている。競合制御部３０は、等級別連鎖待ち行列２０の出力側に接続されている。また、等級別連鎖待ち行列２０内には、複数の等級別連鎖待ち行列が配置されている。図２では、等級別連鎖待ち行列２１から２３まで、３の等級別連鎖待ち行列が配置されている例を示す。
【００１７】
各コネクションからセル送出管理装置１００に入力されるセルには、指数的な重み付けがされている。各セルは、この指数的な重み付けごとに、複数の等級のいずれかにクラス分けされる。それぞれの等級について、１以上の連鎖待ち行列が割り当てられる。図２に示すセル送出管理装置１００では、セルが３つの等級にクラス分けされ、各クラスに１つの、すなわち等級別連鎖待ち行列２１ないし２３が対応して割り当てられている。
【００１８】
セル振分部１０は、各コネクションから入力されてくるセルを、そのセルの重み付けに応じて、対応する等級別連鎖待ち行列２１ないし２３のいずれかに振り分ける。実際には、セル送出管理装置１００が受信したセル自体が等級別連鎖待ち行列２１ないし２３に一時蓄積されるのではなく、各セルの送出権（トークン）が、等級別連鎖待ち行列２１ないし２３に一時蓄積される。
【００１９】
制御部４０は、等級別連鎖待ち行列２０に接続されており、等級別連鎖待ち行列２０内の各待ち行列へのトークンの登録、更新などを制御する。各トークンは、等級別連鎖待ち行列の更新毎にステップをシフトされ、最終的にセル送出への競合に参加することとなる。すなわち、等級別連鎖待ち行列２１ないし２３の先頭までシフトされたトークンは競合制御部３０における競合制御に参加し、競合に勝ったトークンに対応するセルが、最終的にセル送出管理装置１００から出力される。
【００２０】
以下、各等級別連鎖待ち行列２１ないし２３へのトークンの登録、更新動作について、図を用いて詳しく説明する。まず図１には、等級別連鎖待ち行列２１の詳細な構造が示されている。等級別連鎖待ち行列２１、そして等級別連鎖待ち行列２２も、同様の構造を有する。よって以下では、セル送出管理装置１００に入力されたセルが等級別連鎖待ち行列２１に割り振られた場合の、等級別連鎖待ち行列２１でのトークンの登録、更新などの制御について説明する。なお、入力されたセルをいずれの等級別連鎖待ち行列に割り振るかを決定するアルゴリズムについては、この発明の主要なポイントではないので詳細は省略する。
【００２１】
等級別連鎖待ち行列２１は、先頭ステップとしてのステップ＃０、ステップ＃１、ステップ＃２、ステップ＃３、および最後尾ステップとしてのステップ＃４を有する。これらのステップは、各々がＦＩＦＯメモリとして動作する。
【００２２】
各ステップにはそれぞれ複数のトークンが蓄積されるが、各ステップには、トークンを収容している数を保持する収容トークン数パラメータが設けられている。各等級別連鎖待ち行列のすべてのステップは、さらに、それぞれが蓄積しているトークンの最初のもの、および最後尾のものを特定するためのパラメーター（ポインタ値）を保持している。これらのパラメーターは、各ステップ対応で設置されるレジスタに保持される。
【００２３】
さらに、各等級別連鎖待ち行列に登録されているすべてのトークンは、自トークンの次のトークンを指示するポインタを有している。
【００２４】
図１では、各ステップが収容トークン数パラメーターを格納するレジスタ、先頭トークンを示すパラメーターを格納するレジスタ、ステップに蓄積されている複数のトークン、そして最後尾トークンを示すパラメーターを格納するレジスタから構成されている様子が、模式的に示されている。
【００２５】
１．登録（レジスト）動作
新たなセルがセル送出管理装置１００に入力された場合、そのセルに対応するトークンが、等級別連鎖待ち行列２１内のいずれかのステップに登録される。なお、セル(トークン)をいずれのステップに登録するかを決定するアルゴリズムについても、この発明の主要なポイントではないので、詳細は省略する。
【００２６】
新たにトークンを登録する等級別連鎖待ち行列、およびステップが決定した場合、制御部４０は、以下のような制御を行なう。たとえば、新しいトークンがステップ＃２に登録される場合の制御について説明する。
【００２７】
制御部４０はまず、ステップ＃２に対して、新たに登録すべきトークンを与える。前述したように各ステップはＦＩＦＯメモリとして動作するので、このトークンはステップ＃２内では最後に蓄積される。
【００２８】
したがって、ステップ＃２に新たなトークンを登録する場合、ステップ＃２の最後尾のトークンの位置を示すパラメーターの値を修正しなければならない。さらに、新たに登録されるトークンの前後においてトークンの順序が狂わないように、新たに登録されるトークンの前に蓄積されているトークン、新たに登録されるトークン、そして新たに登録されるトークンの後に蓄積されているトークンについて、自トークンの次のトークンを指示するポインタを変更しなければならない。
【００２９】
具体的には、以下の手順でパラメーター、およびポインタの値が修正される。すなわち制御部４０は、まず、ステップ＃２に保持されている、ステップ＃２の最後尾のトークンを指示するポインタ値を、新たに登録するトークンを指示するポインタ値に書き換える（ａ）。同時に、それまでステップ＃２に保持されている最後尾であったトークンが有するポインタを、新たに登録するトークンを指示するように変更する（ｂ）。
【００３０】
そして、新たに登録するトークンが有するポインタを、ステップ＃３以降のステップであって、トークンを１以上蓄積しているステップの、最初のトークンを指示するように変更する（ｃ）。図１に示した例では、ステップ＃３がトークンを蓄積しているので、新たに登録するトークンが有するポインタは、ステップ＃３が蓄積する最初のトークンを指示するように変更される。
【００３１】
制御部４０は最後に、新たなトークンを登録したステップ＃２について、収容トークン数パラメータの値を１インクリメントする（ｄ）。以上の処理を行なうことにより、ステップ＃２に新たなトークンが蓄積され、各トークンの順序が新たに定義される。
【００３２】
２．送出（プッシュ）動作
それぞれの等級別連鎖待ち行列の先頭ステップであるステップ＃０の先頭に位置するトークンは、競合制御部３０での競合制御に参加する。競合制御部３０での競合に勝ったトークンは、等級別連鎖待ち行列から送出（プッシュ）される。このプッシュされたトークンに対応するセルが、セル送出管理装置１００から送出される。
【００３３】
以下、等級別連鎖待ち行列２１内のステップ＃０の先頭に蓄積されているトークンが競合に勝ち、等級別連鎖待ち行列２１からプッシュされる場合の制御について、図３を用いて説明する。
【００３４】
制御部４０は、まず、先頭ステップであるステップ＃０に保持されている、ステップ＃０の最初のトークンを指示するポインタ値を、その最初のトークンの次のトークンを指示するポインタ値に書き換える（ａ）。次いで制御部４０は、ステップ＃０について、収容トークン数パラメータの値を１デクリメントする（ｂ）。以上の処理により、ステップ＃０からトークンが１プッシュされる。
【００３５】
３．更新（シフト）動作
それぞれの等級別連鎖待ち行列は、所定の頻度で更新される。この更新の頻度は、その等級別連鎖待ち行列が扱う重み、待ち行列内に連鎖されているステップの数などに依存する。等級別連鎖待ち行列２１について更新時刻となった場合、制御部４０が行なう制御について、図４を用いて説明する。
【００３６】
制御部４０はまず、先頭ステップであるステップ＃０と、次のステップであるステップ＃１とのマージを行なう。
【００３７】
（ａ）ステップ＃０の最初のトークンの指示
ステップ＃０にトークンが蓄積されていた場合、ステップ＃０に保持されている、ステップ＃０の最初のトークンを指示するポインタ値はそのまま（その最初のトークンを指示するように）維持しておく。一方、ステップ＃０になんらのトークンも蓄積されていなかった場合、ステップ＃０に保持されている、ステップ＃０の最初のトークンを指示するポインタ値を、ステップ＃１以降のステップであって、トークンを１以上蓄積しているステップの最初のトークンを指示するように変更する。
【００３８】
図４に示す例では、ステップ＃０にトークンが蓄積されている。よって制御部４０は、ステップ＃０の最初のトークンを指示するポインタ値を特に書き換えることなく、ステップ＃０に保持されている最初のトークンを指示するようにそのまま維持する。
【００３９】
（ｂ）ステップ＃０の最後尾のトークンの指示
次に、ステップ＃０に保持されている、ステップ＃０の最後尾のトークンを指示するポインタ値を、ステップ＃１以降のステップであって、トークンを１以上蓄積しているステップの最後尾のトークンを指示するように変更する。
【００４０】
図４に示す例では、ステップ＃１にトークンが蓄積されている。よって制御部４０は、ステップ＃０の最後尾のトークンを指示するポインタ値を、ステップ＃１に保持されている最後尾のトークンを指示するように変更する。
【００４１】
（ｃ）先頭ステップの収容トークン数パラメーターの更新
制御部４０は最後に、ステップ＃０について、収容トークン数パラメータの値を更新する。すなわち、ステップ＃０の収容トークン数パラメーターの値に、ステップ＃１の収容トークン数パラメーターの値を加算し、これを新たにステップ＃０の収容トークン数パラメーターの値とする。以上の処理によって、ステップ＃１に蓄積されていたトークンが、以後はステップ＃０に蓄積されているものとして扱われるようになる。
【００４２】
制御部４０はさらに、ステップ＃２以降の各ステップについて、一つ前のステップに移す処理を行なう。すなわち、ステップ＃２が保持する、ステップ＃２の先頭トークンへのポインタおよび最後尾トークンへのポインタ、そして収容トークン数パラメーターを、それぞれステップ＃１の各パラメーターに上書きする（ｄ）。同様にして、ステップ＃３の保持する各パラメーターを、それぞれステップ＃２の各パラメーターに上書きする（ｅ）。さらに同様にして、ステップ＃４の保持する各パラメーターを、それぞれステップ＃３の各パラメーターに上書きする（ｆ）。最後に、最後尾ステップであるステップ＃４が保持する収容トークン数パラメーターを０にリセットする（ｇ）。
【００４３】
以上の処理により、ステップ＃０とステップ＃１とがマージされ、ステップ＃２、ステップ＃３およびステップ＃４がそれぞれ一つ前のステップに移動し、最後尾ステップであるステップ＃４が空になる。
【００４４】
次に図５を用いて、複数の等級別連鎖待ち行列の更新処理について説明する。たとえば、等級別連鎖待ち行列２０として、図５（ａ）に示したように７等級に区分された等級別連鎖待ち行列５１ないし５７が設けられているとする。この場合、図５に示すように、各等級の扱う重みは、指数的に区分されている。等級別連鎖待ち行列５１ないし５７の具体的な構成は、図１に示した等級別連鎖待ち行列２１と同様であるので、詳細については説明を省略する。
【００４５】
また、各連鎖待ち行列の更新頻度は、等級０の待ち行列については毎回更新されるものとし、等級１の待ち行列については２回に１回、等級２の待ち行列については４回に１回・・・と、等級が１下がるにつれて、更新頻度が半分になる。すなわち、ある待ち行列の更新頻度は、その待ち行列が扱う重みの指数値に比例する。
【００４６】
各待ち行列の更新頻度をこのように設定すると、各待ち行列の更新処理を多重化することができる。ここで図５（ｂ）を参照しながら説明すれば、等級０の待ち行列の更新処理は、毎更新処理時に行なう。一方で、等級１〜等級６までの待ち行列の更新処理は、時分割的に多重化することができる。したがって、等級０の待ち行列の更新処理と、それ以外の待ち行列の更新処理と、２つの更新処理を並列に行なえば足り、設定されている等級の数だけ並列処理を行なう必要はない。
【００４７】
以上説明したように、この第１の実施形態では、等級別連鎖待ち行列を実現する上で、トークンの登録、プッシュ、シフトなど、シリアルに発生する処理の負担が従来の方法と殆ど変わらず、現実的な制御方法を提供することができる。
【００４８】
この実施形態によるシフト動作は、従来のＦＩＦＯやタイムテーブル方式に比べて、見かけの並列処理量は大きいが、更新頻度を指数的に設定しているため、実際の並列処理数は２程度と、現実的なレベルの処理量に抑えられる。
【００４９】
次に、この発明の第２の実施形態について説明する。第１の実施形態では、等級別連鎖待ち行列の各ステップが保持する各種パラメーターを、各ステップ対応で設けられたレジスタに格納していた。しかし第２の実施形態では、各待ち行列の先頭ステップに関するパラメーターはレジスタに格納し、以降の各ステップが保持する各種パラメーターについて、半導体メモリなどの記憶装置に格納する。
【００５０】
すなわち、第２の実施形態では、図２に示すセル送出管理装置１００の等級別連鎖待ち行列２０、および制御部４０の構成が異なる。以下、その相違について説明する。
【００５１】
第２の実施形態でも、第１の実施形態と同様、等級別連鎖待ち行列２０は複数の等級別連鎖待ち行列を有し、これらは、それぞれが複数のステップに区分されている。ただし第２の実施形態では、各々の等級別連鎖待ち行列の先頭ステップのみに、パラメーターを保持するレジスタを設ける。そして、先頭ステップ以外のステップは、パラメーター保持用のレジスタを設けない、単にトークンを蓄積するＦＩＦＯメモリとして構成する。
【００５２】
以下に、各ステップのパラメーターを蓄積するための構成を、図６を用いて説明する。すなわち図６は、各ステップについてのパラメーターを蓄積する構成を記憶部６０として表わした模式図である。この記憶部６０は、記憶装置６１と、レジスタ６２とから構成される。
【００５３】
記憶装置６１は、たとえば半導体メモリで構成される。記憶装置６１は、セルがクラス分けされる等級数、また各々の等級を構成するステップ数に応じて、マトリクス状に多数のステップ記憶領域が配置されている。
【００５４】
ただし、記憶装置６１内に形成されるステップ記憶領域は、セルがクラス分けされる等級数と、各々の等級を構成するステップ数より１小さい数とで定義される。たとえば、セルがクラス分けされる等級数が７、各々の等級を構成するステップが９である場合、記憶装置６１内には、７＊（９−１）＝５６のステップ記憶領域が形成される。このように記憶装置６１に形成された各ステップ記憶領域＃１ないし＃８は、それぞれ、各等級別連鎖待ち行列の先頭ステップ以外のステップについて、収容トークン数パラメーター、それぞれが蓄積しているトークンの最初のもの、および最後尾のものを特定するためのパラメーター（ポインタ値）を格納する。
【００５５】
一方、レジスタ６２は、等級別連鎖待ち行列の数と同数のレジスタを有する。これらのレジスタは、各等級別連鎖待ち行列の先頭ステップに関するパラメーターを格納する。
【００５６】
この状態を図示したのが図６である。まず記憶装置６１には、等級＃０から等級＃６までの７等級、かつ、ステップ記憶領域＃１からステップ記憶領域＃８までの８ステップ分のステップ記憶領域が形成されているのが理解されるであろう。そしてレジスタ６２には、等級別連鎖待ち行列の数と同数の、レジスタ６２０からレジスタ６２６が配置されているのが理解されるであろう。
【００５７】
この第２の実施形態では、制御部４０は、各ステップのパラメーターを更新する処理をシリアルに行なう。以下、具体的な処理について説明する。
【００５８】
制御部４０は、内部時計としてタイムスロットカウンタ（ＴＳＣ：図示せず）を有する。ＴＳＣは、システムが管理する現在時刻をカウントし、そのカウント値を制御部４０に与える。制御部４０は、このＴＳＣから取得したカウント値から、ステップスライド係数を算出する。ステップスライド係数は、時間の関数であり、制御部４０は、ステップスライド係数に基づいて、先頭ステップ以外のステップについてのパラメーターを格納するステップ記憶領域を決定する。
【００５９】
すなわち第２の実施形態では、先頭以外の各ステップと、ステップに関するパラメーターを格納するステップ記憶領域とは、固定的に対応しているのではなく、時間の関数によって定められる動的な対応関係にある。換言すれば、先頭以外の各ステップと、記憶装置６１内のステップ記憶領域とは、時間の関数によって動的に、しかし１対１に対応付けられる。ここで、あるステップ記憶領域と、記憶部６０上のアドレスとが１対１に対応していれば、両者間の具体的な対応関係は問わない。
【００６０】
この結果、制御部４０は、（たとえば）ステップ＃３についてのパラメーターを参照しようとする場合、ある時点ではステップ記憶領域＃４を参照するが、次の時点では同じステップ＃３についてのパラメーターを参照するためにステップ記憶領域＃５を参照するということになる。あるいは、同じステップ記憶領域＃４を、ある時点ではステップ＃３についてのパラメーターとして参照し、次の時点ではステップ＃２についてのパラメーターとして参照するということになる。以下、第２の実施形態でのトークンの登録、プッシュ、および更新処理について、等級０を例にとって説明する。
【００６１】
１．登録（レジスト）動作
新たなトークンを、ある等級のあるステップに登録する要求は、基本的にはシリアルに発生する。セル送出管理装置１００がセルを受信した場合、制御部４０は、このセル（に対応するトークン）を、いずれのステップに登録すべきかを決定する。ここで、新たなトークンを先頭ステップに登録すべきと判断した場合、制御部４０は、レジスタ６２０に、各種パラメーターを書き込む。
【００６２】
一方、新たなトークンを先頭ステップ以外に登録すべきと判断した場合、制御部４０は、ＴＳＣを参照してカウント値を取得し、ステップスライド係数を算出する。次いで制御部４０は、ステップスライド係数に基づいて、その時点における当該ステップのパラメーターを格納すべきステップ記憶領域を選定する。
【００６３】
ここで、トークンを登録する際の処理は、第１の実施形態について述べたと同様であるので、詳細は省略する。制御部４０は、こうして当該ステップ（トークンを登録するステップ）に対応するレジスタ６２０あるいはステップ記憶領域にアクセスし、各種パラメーターを書き込む。
【００６４】
２．送出（プッシュ）動作
競合制御に勝ったトークンをプッシュする要求も、基本的にはシリアルな事象として発生する。ただしトークンのプッシュは、必ず先頭ステップから行われる。したがってトークンのプッシュ動作については、第１の実施形態と同様にして、レジスタ６２０に保持されているパラメーターを書き換える。
【００６５】
３．更新（シフト）動作
この動作も、基本的な処理は第１の実施形態で説明したと同様である。すなわち、各等級別連鎖待ち行列の更新動作は、大別して、（１）先頭ステップと次ステップとのマージ、（２）それ以降のステップを、各々一つ前に移す、（３）最後尾ステップを空にするという３段階の処理から構成される。
【００６６】
このうち、（１）先頭ステップと次ステップとのマージは、次のように行なう。すなわち制御部４０は、ＴＳＣの値を取得してステップスライド係数を算出し、このステップスライド係数から、その時点での次ステップのパラメーターを保持しているステップ記憶領域を選定する。
【００６７】
ステップ＃０にトークンが蓄積されていた場合、制御部４０は、レジスタ６２０に保持されている、ステップ＃０の最初のトークンを指示するポインタ値はそのまま（その最初のトークンを指示するように）維持しておく。
【００６８】
一方、ステップ＃０になんらのトークンも蓄積されていなかった場合、制御部４０は、ステップスライド係数から選定された、ステップ＃１のパラメーターを保持しているステップ記憶領域にアクセスする。このステップ記憶領域に格納されている収容トークン数パラメーターから、ステップ＃１にトークンが格納されていると判断された場合、制御部４０は先頭ステップとステップ＃１とのマージを行なう。すなわち制御部４０は、レジスタ６２０に保持されている、ステップ＃０の最初のトークンを指示するポインタ値を、このステップ記憶領域に格納されている最初のトークンを指示するポインタ値で更新する。
【００６９】
もし、ステップ＃１内にトークンが蓄積されていないと判断された場合、制御部４０は、ステップスライド係数からさらに次のステップ（この場合、ステップ＃２）のパラメーターを格納しているステップ記憶領域を選定し、上記の動作を繰り返す。
【００７０】
以下、同様にして、レジスタ６２０に保持されている、ステップ＃０の最後尾のトークンを指示するポインタ値を、次ステップに対応するステップ記憶領域から読み出した、そのステップの最後尾のトークンを指示するパラメーターに更新する。これで、等級０待ち行列の先頭ステップの、最後尾のトークンが指示されたことになる。
【００７１】
制御部４０はさらに、レジスタ６２０の収容トークン数パラメーターの値を修正する。これで、先頭ステップと次ステップとのマージが行われたことになる。
【００７２】
制御部４０はさらに、（２）以降の各ステップについて、一つ前のステップに移す処理を行なう。この処理は、第１の実施形態のように各ステップ対応でレジスタが設けられている構成では、個々のレジスタの内容を読み出し、前のステップに対応するレジスタの値を更新していく処理が必要であった。しかし第２の実施形態では、実際には何らの処理も行なわない。
【００７３】
制御部４０は最後に、（３）最後尾ステップを空にする処理を行なう。すなわち制御部４０は、ステップスライド係数から最後尾のステップのパラメーターを格納しているステップ記憶領域を選定し、この記憶領域に保持されている収容トークン数パラメーターを０にリセットする。
【００７４】
以上の処理により、先頭ステップと次ステップとがマージされ、それ以降のステップがそれぞれ一つ前のステップに移動し、最後尾ステップが空になる。
【００７５】
ここで、上記（２）の”それ以降のステップを、各々一つ前に移す”処理については、実際には何らの処理も行なわなかった。しかし、一つの等級別連鎖待ち行列についての更新動作が終了し、次の更新動作を行なう場合、制御部４０は、再度ステップスライド係数を算出し、該当するステップ記憶領域を選定する。この時、時間の関数であるステップスライド係数により、前回の更新動作時と今回の更新動作時とでは、参照するステップ記憶領域が変化している。
【００７６】
この結果、たとえば前回の更新動作時に、ステップ＃３についてのパラメーターをステップ＃２に移す動作をしたとすれば、実際にパラメーターが格納されているステップ記憶領域は同一でも、制御部４０からみた場合、前回にはステップ＃３のパラメーターを参照するためにアクセスしていたステップ記憶領域＃４を、今回はステップ＃２のパラメーターを参照するためにアクセスする。したがって、記憶装置６１内の書き換えを行なわなくとも、ステップのパラメーターが更新されたと同様の結果が得られる。
【００７７】
以上説明したように、この第２の実施形態では、特にステップの更新動作の際、現実にメモリアクセスを行なう処理を低減することができる。この結果、処理量を増やすことなく、それぞれの連鎖待ち行列のステップ数を大きくすることができる。ステップ数を大きくすることは、セル重み付けの精度をより細かくすることになる。
【００７８】
なお、上記の説明では、各等級別連鎖待ち行列の先頭ステップに関する情報を記憶するための構成としてレジスタを用いた例について説明した。しかし、先頭ステップについても、他の（それ以降の）ステップと同様に、記憶装置６１内に形成されたステップ記憶領域に情報を格納しても良い。
【００７９】
さらに、記憶装置６１に形成されているステップ記憶領域の数は、各々の等級を構成するステップ数よりも多く設けても良い。たとえば各々の連鎖待ち行列が９ステップに区分されている場合、記憶装置６１には９よりも多い１０ステップ分のステップ記憶領域を設けても良い。このような場合でも、待ち行列の各ステップとステップ記憶領域とが、ステップスライド係数によって１対１に対応されるようになっていればよい。
【００８０】
【発明の効果】
以上説明したように、この発明のセル送出管理装置により、並列に行なう処理量をほとんど増大させずに、より実際的なセル送出管理装置が実現される。また、処理量を増やすことなく、セル重み付けの精度をより細かくすることになる。
【図面の簡単な説明】
【図１】第１の実施形態による等級別連鎖待ち行列へのトークンの登録処理を示す図である。
【図２】この発明のセル送出管理装置のブロック図である。
【図３】第１の実施形態による、等級別連鎖待ち行列へのトークンのプッシュ処理を示す図である。
【図４】第１の実施形態による、等級別連鎖待ち行列の更新処理を示す図である。
【図５】第１の実施形態による、複数の等級別連鎖待ち行列の更新処理について説明する図である。
【図６】第２の実施形態による記憶部の構成を示す図である。
【符号の説明】
１０・・・・セル振分部
２０、２１、２２、２３・・・・等級別連鎖待ち行列
３０・・・・競合制御部
４０・・・・制御部
５１〜５７・・・・等級別連鎖待ち行列
６０・・・・記憶部
１００・・・セル送出管理装置
【図１】
0003673114.tif 000002
【図２】
0003673114.tif 000003
【図３】
0003673114.tif 000004
【図４】
0003673114.tif 000005
【図５】
0003673114.tif 000006
【図６】
0003673114.tif 000007