(57)【特許請求の範囲】
【請求項１】
複数のソースから受け取ったセルを選択的に転送するキュー管理システムであって、
前記複数のソースから受け取ったセルを一つの出力チャネルに多重化する多重化器と、
前記多重化器から供給されるセルを受け取って格納するセル格納部と、
前記多重化器、前記セル格納部及びシーケンサを起動させる制御信号を発生する制御部と、
前記セル格納部における空きセクタのアドレスを格納するアイドルアドレス先入れ先出し(FIFO)と、
各々が縦続接続されており、転送際のセルのシーケンスを決定し、セルの優先順位フィールドと該当アドレスよりなる情報を前記セル格納部に格納し、格納された情報と新たに入力されるセルの情報とを比較し、該当情報を前記優先順位フィールド単位にキューイングする複数のモジュールからなる前記シーケンサであって、前記優先順位フィールドは、セルが一つのノードから伝播される際の最大許容可能な遅延限界を表すデッドラインの時間と、ジッターを考慮して一つのセルが一つのノードから伝播される際の遅延限界を表す適格の時間とよりなる、前記シーケンサ
とを含み、
ETｉ , ｊ ｋ がノードｉにおけるチャネルｊに対するｋ番目のセルに割当てられる前記適格の時間を表し、ETｉ−１,ｊ ｋ がノードｉ−１における前記チャネルｊに対する前記ｋ番目のセルに割当てられる前記適格の時間を表し、 dｉ−１,ｊ が前記ノード (ｉ−１) における前記チャネルｊに対する前記デッドラインの時間を表し、 tｉ が前記ノードｉ−１と前記ノードｉとの間の伝播遅延を表す時、前記適格の時間が次の式、
【数１】
0003859864.tif 000004
のように表現されることを特徴とするキュー管理システム。
【請求項２】
前記シーケンサが、
該当モジュールの優先順位フィールドと左側のモジュールから新たに入力されるセルの優先順位フィールドとを比較し、その比較の結果によって優先順位及びアドレスよりなる対を選択し、レジスタが該当対を格納するようにする制御部と、
前記優先順位及び該当アドレスよりなる前記対の情報を格納する前記レジスタと、
前記実時間と前記適格の時間とを比較する比較部と、
前記左側のモジュール内の選択部からの出力、または前記比較部からの出力による前記レジスタのアドレスのうちのいずれか一つを選択的に出力する選択部
とを備えることを特徴とする請求項１に記載のキュー管理システム。
【請求項３】
前記制御部が、新たに入力されるセルのデッドラインの時間と前記シーケンサに既に格納されているセルのデッドラインの時間とを順次的に比較して、より小さいデッドライン時間を有するセルがより大きいデッドライン時間を有するセルの右側に配列されるようにし、前記デッドラインの時間が互いに同一である場合は、それらの前記適格の時間を互いに比較して、より小さい適格の時間を有するセルがより大きい適格の時間を有するセルの右側に配列されるようにすることを特徴とする請求項２に記載のキュー管理システム。
【請求項４】
前記シーケンサに組み込まれる前記モジュールの数が、前記セル格納部に格納可能なセルの数と同じであることを特徴とする請求項２に記載のキュー管理システム。
【請求項５】
前記シーケンサが、非作業保存方式(non-working-conserving)のキュー管理システムに用いられることを特徴とする請求項２に記載のキュー管理システム。
【請求項６】
前記キュー管理システムが、広帯域サービス総合ディジタル網(B−ISDN) で具現されることを特徴とする請求項５に記載のキュー管理システム。
【請求項７】
前記ノードが、ATM(非同期転送モード) 交換機であることを特徴とする請求項６に記載のキュー管理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、キュー管理システムに関し、特に、セルの優先順位及びジッターを同時に制御し得るキュー管理システムに関する。
【０００２】
【従来の技術】
B-ISDN（広帯域サービス総合ディジタル網）は、 ATM（非同期転送モード）方式を用いて多様な帯域のサービスのための端末相互間転送を柔軟且つ効果的に提供する。 ATM方式において、情報はパケット化されて一定な長さのセルに伝送される。各セルは53オクテットから構成され、これらのうち５オクテットはヘッダーに関し、48オクテットは情報フィールドに関する。
【０００３】
B-ISDNにおいて、多様な帯域のサービスのうち実時間（リアルタイム）通信サービスが段々重要になっている。そのような実時間通信サービスにおいては受信率、セル損失率、遅延及びジッターなどにより決まれる多様な品質基準(QoS: Quality of Services)がクライアントの要求に合わせて定義されているので、広帯域サービス総合ディジタル網はそのようなQoS を保証しなければならない。とりわけ、実時間通信サービスにおいては、特定の限界を超過する遅延及びジッターがセル損失と同様に扱われるので、遅延やジッターを抑止して適切にキュー（queue ）を管理する方法が肝要に提案されている。ここで、セル遅延変動分といわれるジッター接続は、該当接続において二つのセルの間で測定される遅延の最大絶対差分によって定義され得る。
【０００４】
通常のキュー管理システムは、作業保存方式(work-conserving scheme)と非作業保存方式(non-work-conserving scheme)とに大別し得る。
作業保存方式において、キューにセルが存在する間、サーバーは常に動作する反面、非作業保存方式においては、キューにセルが存在していてもサーバーは動作しない。従来のデータ通信網においては、平均遅延及び平均受信率がQoS の重要な要因として見なしているので、そのような要因を充足させるために作業保存方式が主に研究されてきたが、今後には、セル遅延やジッターが段々重要な要因として考慮されることに伴い、非作業保存方式が注目されている。
非作業保存方式は作業保存方式に比べて、キューの効率性面で多少低下されるが、セルシーケンスのバースト（burstiness）、即ち、ジッターを相当に減らし得る特長を有する。
【０００５】
作業保存方式を用いるキュー管理システムは、チャオ(Chao)氏によって提案されている（「A novel architecture for queue management in the ATM network」, IEEE Journal on Selected Areas in Communications. Vol.9, No.7,Septemper, 1991 参照）。以下、チャオ氏によって提案されたキュー管理システムに対して図１〜図７を参照して説明する。
【０００６】
図１は、バーストを抑止するために、セルの再配列の際に用いられる出発順番をどう決定するかを説明するための模式図である。入力X の場合、平均到着率ARがタイムスロット当り0.1 セルであり、平均バースト長さB が2 であり、また、入力Y の場合は、平均到着率ARがタイムスロット当り0.2 セルであり、平均バースト長さB が4 であると仮定する。初期時間は0 に設定される。図１に示すように、入力Y から連続する４個のセルが入力され、その後、入力X から連続する２個のセルが入力される。ｉ番目の到来セルに対する出発順番DSi は次のように各セルに割り当てられる。詳述すると、 DＳi 、例えば、入力Ｙの第１セルの出発順番DSは実時間0 として割り当てられ、以降のセル即ち、第２、第３、・・・は公式  DSi ＝ maximum〔実時間、DSi-1 +1／ARi 〕によって決定される。即ち、入力Y の平均到着率ARi が0.2 であるため、第２セル、第３セル及び第４セルの出発順番は各々５、１０及び１５として割当てられる。こうして、入力X の第１セルには実時間４がその出発順番として割当てられ、第２セルには公式maximum 〔5 、4 ＋10〕によって１４がその出発順番として割当てられる。その結果、図２に示すように、各セルが配列されてキュー11が生成される。これらの出発順番DSに基づいて、サーバー12は図３に示したように、より低い値のセルから順次に出力する。
【０００７】
ATM交換機でのキュー管理においては、出力ポートアドレス及び優先順位フィールドを有する付加データがセルに含まれる。
優先順位フィールドを有するパケットはB-ISDNで転送されるもので、図４に示したように、配列され得る。この優先順位フィールドはサービスクラス及び出発順番よりなる。パケットにおける出力ポートアドレス及び優先順位フィールドは ATM交換機の入力ポート制御器によって割り当てられる。
【０００８】
図５は、チャオ氏によって提案された従来のキュー管理システムのブロック図であって、時分割マルチプレクサ(TDM)31 、セルプール32、シーケンサ33、アイドルアドレスFIFO34、書込み制御部35及び読出し制御部36から構成される。
【０００９】
TDM31 は、１２個の入力を１個の高速チャネルに多重化して出力する。セルプール32はTDM31 からの出力を受け取って格納する働きを果たす。シーケンサ33はソーティングメモリとして、パケットの優先順位フィールドP と該当アドレスA とよりなる対P-A を形成する働きを果たす。ここで、アドレスとはセルプール32における空き空間をいい、そのアドレス情報はアイドルアドレスFIFO34から求められる。このアイドルアドレスFIFO34はセルプール32における全ての空セルのアドレスを格納する。書込み制御部35及び読出し制御部36は、各要部の制御のための制御信号を発生する。
【００１０】
詳述すると、TDM31 は12個の入力パケットを１個のチャネルに時分割多重化してセルプール32に供給する。シーケンサ33は、より高い優先順位の対P-A が常により低い優先順位の対P-A の右側に配置されるように格納して、より高い優先順位の対P-Aが最初読出し制御部36によってアクセスされるようにする。各対がアクセスされると、セルのアドレスはセルプール32内の該当空間を読み出すのに用いられる。
【００１１】
以下、シーケンサ33の動作原理に対して図6を参照して説明する。
図６において、N 番目の優先順位 Pn がn+1 番目の優先順位 Pn+1 より高い優先順位を有すると仮定する。優先順位 Pn を有する新たなセルが入力された時、 Ak それ自体を含んで Ak の右側ある全ての対P-A はそれ自体の位置を維持する反面、この以外のものは左側にシフトする。この際発生する空いている空間には図６（Ｂ）に示すように、新たなセルの優先順位フィールドPn及びアドレスAnよりなる対P-A が格納される。
【００１２】
セルプール32が一杯になった時、即ち、アイドルアドレスFIFO34が空いている時、シーケンサ33において最も左側にある優先順位フィールド（例えば、Pz）は新たに入力されたセルの優先順位フィールドPnと比較される。PnがPzより小さい場合、新たな対Pn-An がシーケンサ33に入力されると共に、対Pz-Az はシーケンサ33から取捨てられる。一方、セルプール32においてアドレスAzを有するセルは新たなセルとして上書きされる。しかし、PnがPz以上である場合は、新たなセルは取捨てられるようになる。
【００１３】
図７は、対P-A を処理するシーケンサ33の詳細なブロック図であって、このシーケンサ33は各々が複数の回路よりなる複数のモジュールから構成され、ここでは、１個のモジュール（例えば、ブロック50）を例として説明する。
新たな優先順位及びアドレスの対Pn-An は各モジュールに供給される。決定回路51は優先順位Ｘ (即ち、 Pi-1)、Ｙ (即ち、 Pi ) 及びＺ (即ち、 Pn ) に基づいて、新たな対Pn-An をレジスタ55にシフトさせ、対 Pi-1 -Ai-1 を右側からレジスタ55の方にシフトさせ、または元の対 Pi -Ai を得るために、格納信号sn及び左シフト信号slを発生する。下記〔表１〕は、信号sn及びslを発生する真理表を表す。
【００１４】
【表１】
0003859864.tif 000002
【００１５】
上記〔表１〕において、ケース(a) の場合は、両信号sn及びslを発生して新たな対 Pn -An がレジスタ55にラッチされて対 Pn -A nがレジスタ55の入力として選択されるようし、左シフトクロック信号slckをレジスタのクロック入力として伝達する。ケース(b) の場合は、sl信号のみを発生して Pi-1 -Ai-1 がクロック信号slckと共にレジスタ55にラッチされるようする。ケース(c) の場合には、sn信号が“do not care"の条件である間sl信号を無視することによって、レジスタ55は元の Pi -Ai を保持することになる。
【００１６】
以下、シーケンサ33の動作の詳細を〔表２〕を参照して説明する。
【表２】
0003859864.tif 000003
【００１７】
上記〔表２〕において、決定回路51は入力X 、Y 及びZ を同時に比較する。もし、決定回路51が値１の左シフト信号slと、値１の新たな格納信号snとを発生する場合、マルチプレクサ54は新たに受け取ったセルの対P-A を出力し、ラッチ55は左シフトクロック信号sclkに応じて該当対P-A を格納する。この場合、右シフト信号sr及び右シフトクロック信号srckは遮断される。
【００１８】
また、決定回路51が入力X 、Y 及びZ を比較して値0の信号slを出力する場合は、現在の対P-A をそのまま保持する。この場合、右シフト信号sr及び右シフトクロック信号srckは遮断される。
【００１９】
このように決定回路51の判断によって、新たに受け取ったセルに対するソーティングプロセスが完了されると、読出し制御部36は右シフト信号srを1 に設定した後右シフトクロック信号srckを用いて、シーケンサ33における各対P-A を右側にシフトさせて最右側の対P-A をサーバー12に出力する。
アイドルアドレスFIFO34はサーバー12に伝送されたセルのアドレスを格納しており、新たなセルを受け取ると共に、格納していたアドレスを出力する。このアイドルアドレスFIFO34が空いていると、セルプール32が一杯な状態を意味し、アイドルアドレスFIFO34が一杯な状態であると、セルプール32が空いている状態を意味する。
【００２０】
書込み制御部35は選択信号によってTDM31 としてセル出力するようし、読出し信号rdを発生してアイドルアドレスFIFO34としてアドレスを出力するようする。シーケンサ33が対P-A を受け取ると、書込み制御部35はセルプール32が該当アドレスにセルを格納するよう書込み制御信号waddr を発生する。また書込み制御部35は、対P-A をシーケンサ33に格納ための左シフト信号sl及び左シフトクロック信号slckをも出力する。
【００２１】
読出し制御部36は最高の優先順位を有するセルのアドレスが出力されるようにする信号シフトアウト信号shiftoutを出力し、該当アドレスがアイドルアドレスFIFO34に格納されるようする書込み信号wrを発生し、またセルプール32に読出し制御信号raddr を発生して該当アドレスのセルを出力されるようする。この読出し制御部36は、対P-A を読み出すための右シフト信号sr及び右シフトクロック信号srckをも出力する。
【００２２】
以下、従来のキュー管理システムの全体的な動作に対して説明する。
最初、各接続から入力される複数のセルはTDM31 によって時分割多重化された後、セルプール32に入力される。セルプール32に格納されているセルのアドレスは、書込み制御部35からの書込み信号rdに応じて起動されるアイドルアドレスFIFO34から出力される。セルの優先順位情報及びアドレスよりなる対P-A はシフトイン信号shiftin の入力によって、シーケンサ33に格納される。
シーケンサ33に格納される対P-A の位置関係は、より高い優先順位の対P-A がより低い優先順位の対P-A の右側に配置されるよう決定される。最右側にあるセルが読出し制御部36からのシフトアウト信号shiftoutに応じて、サーバー12に出力される。
【００２３】
シーケンサ33のモジュールの個数はセルプール32の格納可能なセルの個数と一致する。従って、セルプール32が一杯な状態 (即ち、アイドルアドレスFIFO34が空いている状態) になって、セルプール32に新たなセルを格納するための空間がもう以上存在しないと、テーブルの空間もなくなる。このようなテーブルの充満状態にて、新たなセルが入力される場合、最初シーケンサ33にて新たに入力されたセルの優先順位と最左側セルの優先順位との間の比較が行われる。比較結果、最左側セルの優先順位が新たなセルの優先順位より小さいと、最左側セルは取捨てられ、その結果生じたアイドルアドレス及び新たなセルの優先順位よりなる対P-Aがシーケンサ33に挿入される。もし、新たなセルの優先順位が最左側セルの優先順位より小さいと、受け取った新たなセルが取捨てられる。
【００２４】
前述したように、シーケンサ33は受け取ったセルをセルヘッダに含まれた優先順位情報によってサーバー12に転送し得る、スケジューリング機能を有している。しかしながら、そのようなシーケンサ33にはキューにおいて遅延提供機能即ち、ジッター制御機能が組み込まれていないという不都合がある。
【００２５】
さらに、非作業保存方式においては、キュー管理のためのジッター制御機能は有しているが、この方式は通常的にソフトウェアのみで具現されることによって、計算時間が相当に増加するという不都合がある。
【００２６】
【発明が解決しようとする課題】
従って、本発明の主な目的は、セルの優先順位及びジッターを同時に制御し得るキュー管理システムを提供することにある。
【００２７】
【課題を解決するための手段】
上記の目的を達成するために、本発明によれば、複数のソースから受け取ったセルを選択的に転送するキュー管理システムであって、前記複数のソースから受け取ったセルを一つの出力チャネルに多重化する多重化器と、前記多重化器から供給されるセルを受け取って格納するセル格納部と、前記多重化器、前記セル格納部及びシーケンサを起動させる制御信号を発生する制御部と、前記セル格納部における空きセクタのアドレスを格納するアイドルアドレス先入れ先出し(FIFO)と、各々が縦続接続されており、転送際のセルのシーケンスを決定し、セルの優先順位フィールドと該当アドレスよりなる情報を前記セル格納部に格納し、格納された情報と新たに入力されるセルの情報とを比較し、該当情報を前記優先順位フィールド単位にキューイングする複数のモジュールからなる前記シーケンサであって、前記優先順位フィールドは、セルが一つのノードから伝播される際の最大許容可能な遅延限界を表すデッドラインの時間と、ジッターを考慮して一つのセルが一つのノードから伝播される際の遅延限界を表す適格の時間とよりなる、前記シーケンサとを含み、
ETｉ , ｊ ｋ がノードｉにおけるチャネルｊに対するｋ番目のセルに割当てられる前記適格の時間を表し、ETｉ−１,ｊ ｋ がノードｉ−１における前記チャネルｊに対する前記ｋ番目のセルに割当てられる前記適格の時間を表し、 dｉ−１,ｊ が前記ノード (ｉ−１) における前記チャネルｊに対する前記デッドラインの時間を表し、 tｉ が前記ノードｉ−１と前記ノードｉとの間の伝播遅延を表す時、前記適格の時間が次の式、
【数２】
ETｉ , ｊ ｋ ＝  ETｉ−１,ｊ ｋ ＋ dｉ−１,ｊ ＋ tｉ
のように表現されることを特徴とするキュー管理システムが提供される。
【００２８】
【発明の実施の形態】
以下、本発明の好適実施例について図面を参照しながらより詳しく説明する。図８には、本発明による優先順位及びアドレスよりなる対の模式図が示されている。優先順位はデッドラインの時間DT及び適格の（eligible）時間ETによって決定される。デッドラインの時間DTは、B-ISDNにおいてセルが一つのノードから伝播される際の最大許容可能な遅延限界であって、各デッドライン時間の和がソースより宛先ノードまでの遅延限界を超えない条件下で決定される。一つのノードにおいてデッドラインの時間を超過する遅延が発生する場合、終端間の遅延限界を超過し、セルが無用になる。適格の時間ETは、ジッターを考慮して一つのセルが一つのノードから伝播される際の遅延限界を表し、次の式(1) の通り定義される。
【００２９】
【数３】
ETｉ , ｊ ｋ ＝  ETｉ−１,ｊ ｋ ＋ dｉ−１,ｊ ＋ tｉ         式(1)
ここで、ETｉ , ｊ ｋ はノードｉにおけるチャネルｊに対するｋ番目のセルに割当てられる適格の時間を表し、ETｉ−１,ｊ ｋ はノードｉ−１におけるチャネルｊに対するｋ番目のセルに割当てられる適格の時間を表し、 dｉ−１,ｊ はノード (ｉ−１) におけるチャネルｊに対するデッドラインの時間を表し、 tｉ はノードｉ−１とノードｉとの間の伝播遅延を表す。式(1) を通じて、ノードｉにおけるｋ番目の適格の時間は前ノード (ｉ−１) における適格時間及びデッドライン時間によって決定されることを分かる。
【００３０】
本発明によるキュー管理システムは、従来のシステムとほぼ類似な構造をもって具現することができる。従って、本発明の構造及び動作はシーケンサ33を除いては、図５に示した従来のTDM31 、セルプール32、アイドルアドレスFIFO34、書込み制御部35、及び読出し制御部36のものと同一である。
【００３１】
図９は、本発明による、ジッター制御機能付きシーケンサの詳細なブロック図である。
本発明のシーケンサにおいて、複数のモジュール (例えば、70) が並んで接続されている。このシーケンサに組み込まれるモジュールの数はセルプール32に格納し得るセルの数と同じである。モジュール70はコントローラ71、レジスタ72、コンパレータcomp73、及びセレクタ74より構成される。
【００３２】
適格の時間及びデッドラインの時間よりなる優先順位フィールドはレジスタ72に格納される。該当セルが存在するセルプール32におけるアドレスもレジスタ72に格納される。各アドレスは優先順位フィールドに関連するセルが格納されているセルプール32における空間を表す。実時間及び適格の時間はコンパレータ73に入力され比較される。セレクタ74は、左側のセレクタからの出力またはレジスタ72からのアドレスのうちのいずれか一つを選択して出力する。コントローラ71は、該当モジュール70の優先順位フィールドと左側に位置する (ｉ−１) 番目のモジュールの優先順位フィールド、また新たな入力とを比較する。そのようなコントローラ71は優先順位及びアドレスよりなる一つの対を選択し、レジスタ72に出力して格納する。
【００３３】
本発明によるシーケンサは、最初入力されるセルのデッドラインの時間とシーケンサに既に格納されているセルのデッドラインの時間とを順次的に比較する。より小さいデッドライン時間を有するセルが、より大きいデッドライン時間を有するセルの右側に配列されるようにする。デッドラインの時間が互いに同一である場合、それらの適格の時間を互いに比較して、より小さい適格の時間を有するセルがより大きい適格の時間を有するセルの右側に配列されるようにする。
【００３４】
従来のキュー管理システムに比べて、本発明のキュー管理システムはデッドラインの時間のみならず適格の時間をも考慮して優先順位を割り当てる。即ち、各モジュールにて実時間と適格の時間とを比較した後、実時間より小さい適格の時間を有するセルをまずサービスする。実時間より小さい適格の時間を有するセルが複数個ある場合は、より小さい適格の時間を有するセルがまずサービスされるようにする。
【００３５】
このために、コンパレータcomp73は実時間と適格時間とを比較して比較結果をセレクタ74に供給する。セルの適格時間が実時間より大きい場合、即ち、該当セルが適格時間より先に到着する場合、セレクタ74は左側のセレクタからの出力を選択して出力し、またセルの適格時間が実時間より小さい場合は、セレクタ74はレジスタ72に格納されたアドレスAiを選択して出力する。
【００３６】
本発明によるキュー管理システムは、デッドラインの時間が小さくて優先順位の高いセルであっても、適格の時間が過ぎない限り、セルのサービスが行わないように遅延させることによってジッタを調節できるよう構成されている。即ち、全てのセルは適格の時間が過ぎてから始めてサービス可能である。
【００３７】
上記において、本発明の好適な実施の形態について説明したが、本発明の請求範囲を逸脱することなく、当業者は種々の改変をなし得るであろう。
【００３８】
【発明の効果】
従って、本発明によれば、デッドラインの時間が小さくて優先順位の高いセルであっても、適格の時間が過ぎない限り、セルのサービスが行わないように遅延させることによって、セルの優先順位及びジッタを効果的に調節することができる。
【図面の簡単な説明】
【図１】セルの出発順番をどう決定するかを説明する模式図である。
【図２】優先順位によって再配列されたセルの模式図である。
【図３】再配列されたセルの出力手続を説明する模式図である。
【図４】優先順位フィールドを含むパケットの模式図である。
【図５】従来のキュー管理システムのブロック図である。
【図６】  (A) 及び(B) よりなり、各々図３中のシーケンサの動作原理を説明する模式図である。
【図７】図3中のシーケンサの詳細なブロック図である。
【図８】本発明によって優先順位フィールド及びアドレスよりなる対の模式図である。
【図９】本発明によるシーケンサの詳細なブロック図である。
【符号の説明】
31  時分割マルチプレクサ(TDM)
32  セルプール
33  シーケンサ
34  アイドルアドレスFIFO
35  書込み制御部
36  読出し制御部
70  モジュール
71  コントローラ
72  レジスタ
73  コンパレータ(comp)
74  セレクタ
【図１】
0003859864.tif 000005
【図２】
0003859864.tif 000006
【図３】
0003859864.tif 000007
【図４】
0003859864.tif 000008
【図５】
0003859864.tif 000009
【図６】
0003859864.tif 000010
【図７】
0003859864.tif 000011
【図８】
0003859864.tif 000012
【図９】
0003859864.tif 000013