JP3216582B2 - データ出力制御方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、入力データをその
属性に基づいて適切な待ち行列に格納後、各待ち行列か
らの出力データの最低速度を保証するように各待ち行列
を選択して、各待ち行列から単一の出力回線にデータを
出力するデータ出力制御方法の改良に関する。

【０００２】

【従来の技術】従来のこの種のデータ出力制御方法とし
ては、Ｗｅｉｇｈｔｅｄ ＲｏｕｎｄＲｏｂｉｎ方式
（Ｍ．Ｋａｔａｖｅｎｉｓ他、Ｗｅｉｇｈｔｅｄ Ｒｏ
ｕｎｄ−Ｒｏｂｉｎ Ｃｅｌｌ Ｍｕｌｔｉｐｌｅｘｉ
ｎｇ ｉｎ ａ Ｇｅｎｅｒａｌ−Ｐｕｒｐｏｓｅ Ａ
ＴＭ Ｓｗｉｔｃｈ Ｃｈｉｐ，ＩＥＥＥ Ｊ．Ｓｅｌ
ｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔ
ｉｏｎ Ｖｏｌ．９，Ｎｏ．８（１５１２）１２６５−
１２７９）がある。

【０００３】Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉ
ｎ方式では、異なる重みをもって、データ出力を行う待
ち行列の選択動作を行い、各待ち行列に対してその重み
の比に従ってデータ出力の最低速度を保証し、余った出
力回線の容量は各待ち行列に対してその重みの比に従っ
て配分される。

【０００４】Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉ
ｎ方式では各待ち行列毎にウエイトとカウンタを持つ。
ウエイトは各待ち行列に与えられている重みであり、カ
ウンタの初期値はウエイトの値である。Ｗｅｉｇｈｔｅ
ｄ Ｒｏｕｎｄ Ｒｏｂｉｎ方式では、各データ出力時
間毎に、前回データ出力を行った待ち行列の次の待ち行
列から巡回順に、データを持ち且つカウンタの値が１以
上である待ち行列を探す。そして、この待ち行列からデ
ータを１つ送出して、この待ち行列のカウンタの値を１
つ減じる。データ出力を行うことのできる待ち行列が無
い場合、すなわちカウンタの値が１以上であり且つ１つ
以上データを持つ待ち行列が無い場合には、全てのカウ
ンタの値をウエイトの値に戻すリセット動作を行った
後、データ出力を行う待ち行列を選択し、データ出力を
行う。

【０００５】Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉ
ｎ方式を適用したデータ出力制御装置の一構成例を図２
９に示す。データ出力制御装置１０１にデータが入力さ
れると、データ識別部１１によって入力データがその属
性に従って適切な待ち行列１３に格納される。そして、
各データ出力時間毎に、出力制御部１２は待ち行列選択
部１２１によって指示された待ち行列からデータを１つ
取り出し、出力回線に出力する。

【０００６】待ち行列選択部１２１では、各待ち行列毎
にウエイトとカウンタの値を保持するカウンタ値格納部
１４０と前回データを送出した待ち行列の番号を保持す
る待ち行列番号保持部２６とを有し、判定部１８は待ち
行列１３内のデータ数とカウンタ値格納部１４０内のカ
ウンタ値とから待ち行列からのデータ送出の可否を判断
し、待ち行列番号加算部２７と判定部１８により、前回
データを送出した待ち行列の次の待ち行列から巡回順
に、データを持ち且つカウンタの値が１以上である待ち
行列を探す。そして、この待ち行列からデータを出力す
るように出力制御部１２に指示し、同時にカウンタ値格
納部１４０では選択された待ち行列のカウンタ値を１つ
減じる。カウンタ値格納部１４０では、データを持ち且
つカウンタの値が１以上である待ち行列が無くなると、
全ての待ち行列のカウンタの値をそれぞれのウエイトの
値に戻すリセット動作を行う。

【０００７】Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉ
ｎ方式を適用したデータ出力制御装置の別の構成例を図
３０に示す。この例のデータ出力制御装置１０２は、待
ち行列選択部１２２の構成が図２９の待ち行列選択部１
２１と異なり、本例においては待ち行列１３内のデータ
数とカウンタ値格納部１４０内のカウンタ値から与えら
れた待ち行列からのデータ送出の可否を判断する判定部
１９を各待ち行列毎に持つ。複数の判定部１９により、
全ての待ち行列について同時にデータの有無とカウンタ
値を調べることができ、選択回路２８ではこの判定結果
と、待ち行列番号保持部２６にある前回データを出力し
た待ち行列番号をもとに、データ出力を行う待ち行列を
選択する。

【０００８】

【発明が解決しようとする課題】Ｗｅｉｇｈｔｅｄ Ｒ
ｏｕｎｄ Ｒｏｂｉｎ方式の第一の問題点は、特に待ち
行列の数が多い場合に、待ち行列選択のための処理量が
大きいことである。図２９の構成では、待ち行列の選択
の際に、データを持ち且つカウンタの値が１以上である
待ち行列が見つかるまで１つ以上の待ち行列を調べなけ
ればならず、待ち行列選択に関して全待ち行列数に応じ
た処理時間が必要である。また、図３０の構成では、待
ち行列の選択を待ち行列数に依存しない時間で行うこと
が可能であるが、待ち行列数に応じた数の判定部が必要
となり、回路数が増大する。

【０００９】第二の問題点は、リセット動作を行うため
の条件判定の処理量が大きいことである。前記条件判定
は全ての待ち行列内のデータ数、及び全ての待ち行列の
カウンタ値を調べる必要があるため、図２９の構成にお
いては待ち行列数に応じた処理時間が必要であり、図３
０の構成においては待ち行列数に応じた回路数が必要で
ある。

【００１０】第三の問題点は、カウンタのリセット動作
時に全ての待ち行列のカウンタを同時にリセットするた
め、リセット動作を行うためには全待ち行列数に応じた
処理時間もしくは処理量が必要になることである。

【００１１】第四の問題点は、Ｗｅｉｇｈｔｅｄ Ｒｏ
ｕｎｄ Ｒｏｂｉｎ方式は、カウンタの値が１以上で且
つ１つ以上データを持つ複数の待ち行列に関しては、各
待ち行列を巡回的に選択するため、遅延要求が厳しく、
優先してデータを出力する必要のある待ち行列も、優先
される必要のない待ち行列も、同等に扱われることであ
る。このため、遅延要求に厳しい待ち行列の遅延要求が
満たされない可能性が生じる。

【００１２】Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉ
ｎ方式では、各待ち行列に対してそれぞれのウエイトの
比に従って最低データ速度を保証し、出力回線の容量が
余っている時には、出力回線の余剰容量を各待ち行列の
ウエイトの比に従って分配する。しかしながら、出力回
線の余剰容量を各待ち行列のウエイトの比とは関係な
く、等分などの別の比率で分配したいという要求も存在
すると考えられる。第五の問題点は、Ｗｅｉｇｈｔｅｄ
Ｒｏｕｎｄ Ｒｏｂｉｎ方式ではこのような要求に対
応できないことである。

【００１３】

【課題を解決するための手段】本発明は、複数の待ち行
列を有し、入力データをその属性（例えばサービスクラ
ス）に基づいて適切な待ち行列に格納し、これらの待ち
行列から単一の出力回線にデータを出力するデータ出力
制御方法において、以下のような構成を採用している。

【００１４】（１）待ち行列の番号を格納する複数のリ
ストを使用し、同一の待ち行列番号は全リスト中に高々
１つのみ存在するようにし、入力データを待ち行列に格
納する際、該待ち行列が入力データ以外のデータを持た
なければ、該待ち行列のデータ出力可否状態および優先
度の内の少なくとも１つの条件に応じて適切なリストに
該待ち行列番号を格納し、データを出力回線に出力する
際には、適切なリストを選択してそのリストの先頭から
待ち行列番号を取り出し、取り出した番号の待ち行列か
らデータを１つ送出し、該待ち行列が、出力したデータ
以外のデータを持てば前記条件により適切なリストに該
待ち行列番号を格納し、一定時間毎に、もしくは特定の
リストが空になる毎に、各待ち行列の前記条件の変更
と、リスト間での待ち行列番号の移動とを行うリセット
動作を行う。

【００１５】（２）データを持ち且つそのデータを出力
可能な待ち行列の番号を保持する送出可能待ち行列番号
リストと、データを持つがそのデータを出力できる状態
にない待ち行列の番号を保持する送出不可能待ち行列番
号リストとを使用し、同一の待ち行列番号は全リスト中
に高々１つのみ存在するようにし、入力データを待ち行
列に格納する際、その待ち行列が入力データ以外のデー
タを持たない場合は該待ち行列からのデータ送出の可否
に従って適切なリストに該待ち行列番号を格納し、デー
タを出力回線に出力する際には、送出可能待ち行列リス
トの先頭から待ち行列番号を取り出し、取り出した番号
の待ち行列からデータを１つ送出し、データ送出後該待
ち行列が出力されたデータ以外のデータを持つ場合は再
び適切なリストに該待ち行列番号を格納し、前回のリセ
ット動作以降に該待ち行列から出力されたデータの個数
が一定数以上となると該待ち行列を送出不可能状態と
し、また、データを出力する際に送出可能待ち行列番号
リストが空であれば、全ての待ち行列をデータ送出可能
状態とし、送出不可能待ち行列番号リストの内容を送出
可能待ち行列番号リストに移動するリセット動作を行
う。

【００１６】（３）データを持ち且つそのデータを優先
して出力可能な待ち行列の番号を保持する送出可能優先
待ち行列番号リストと、データを持ち且つそのデータを
非優先で出力可能な待ち行列の番号を保持する送出可能
非優先待ち行列番号リストとを使用し、同一の待ち行列
番号は全リスト中に高々１つのみ存在するようにし、入
力データを待ち行列に格納する際、その待ち行列が該入
力データ以外のデータを持たない場合は待ち行列の現在
の優先度に従って適切なリストに該待ち行列番号を格納
し、データを出力回線に出力する際には、送出可能優先
待ち行列番号リストの先頭の待ち行列から待ち行列番号
を取り出し、もし送出可能優先待ち行列番号リストが空
であれば送出可能非優先待ち行列番号リストの先頭から
待ち行列番号を取り出し、取り出した番号の待ち行列か
らデータを１つ送出し、データ送出後該待ち行列が出力
されたデータ以外のデータを持つ場合は再び該待ち行列
の優先度に従って適切なリストに該待ち行列番号を格納
し、前回のリセット動作以降に該待ち行列から出力され
たデータの個数が一定数以上となると該待ち行列を非優
先状態とし、一定時間毎に、全ての待ち行列を優先状態
とし、送出可能非優先待ち行列番号リストの内容を送出
可能優先待ち行列番号リストに移動するリセット動作を
行う。

【００１７】（４）データを持ち且つそのデータを優先
して出力可能な待ち行列の番号を保持する送出可能優先
待ち行列番号リストと、データを持ち且つそのデータを
非優先で出力可能な待ち行列の番号を保持する送出可能
非優先待ち行列番号リストと、データを持つがそのデー
タを出力できる状態にない待ち行列の番号を保持する送
出不可能待ち行列番号リストとを使用し、同一の待ち行
列番号は全リスト中に高々１つのみ存在するようにし、
入力データを待ち行列に格納する際、その待ち行列が該
入力データ以外のデータを持たない場合は該待ち行列の
優先度と該待ち行列からのデータ送出の可否とに従って
適切なリストに該待ち行列を格納し、データを出力回線
に出力する際には、送出可能優先待ち行列番号リストの
先頭から待ち行列番号を取り出し、もし送出可能優先待
ち行列番号リストが空であれば送出可能非優先待ち行列
番号リストの先頭から待ち行列番号を取り出したのち該
待ち行列を送出不可能状態とし、取り出した番号の待ち
行列からデータ１つを送出し、データ送出後該待ち行列
が出力されたデータ以外のデータを持つ場合は再び適切
なリストに該待ち行列番号を格納し、また、前回の全待
ち行列に対するリセット動作以降に該待ち行列から出力
されたデータの個数が一定数以上となると該待ち行列を
非優先状態とし、該待ち行列が非優先状態にあり且つ一
度も非優先状態に対するリセット動作を受けていないか
若しくは前回の非優先待ち行列に対するリセット動作以
降に該待ち行列から送出されたデータの個数が別の一定
個数以上であると該待ち行列をデータ送出不可能とし、
一定時間毎に全待ち行列に対するリセット動作、すなわ
ち全ての待ち行列をデータ送出可能で且つ優先状態と
し、送出可能非優先待ち行列番号リストの内容と送出不
可能待ち行列番号リストの内容とを送出可能優先待ち行
列番号リストに移動する動作を行い、また、送出可能非
優先待ち行列番号リストが空となる毎に非優先待ち行列
に対するリスト動作、すなわち送出不可能となっている
待ち行列を全て送出可能状態とし、送出不可能待ち行列
番号リストの内容を送出可能非優先待ち行列番号リスト
に移動する動作を行う。

【００１８】（５）前記（１）〜（４）のデータ出力制
御方法において、各種別のリストをそれぞれ優先順位の
クラス数分持ち、各待ち行列がその属する優先順位クラ
スに基づいて固定的な優先順位を持ち、リストに待ち行
列番号を格納する際には、格納する種別のリストのうち
該待ち行列が属する優先順位クラスのリストに待ち行列
番号を格納し、リストから待ち行列番号を取り出す際に
は、取り出す種別のリストのうち、１つ以上待ち行列番
号を持ち且つ最も優先順位の高いリストから待ち行列番
号を取り出す。

【００１９】（６）各待ち行列が優先してデータを送出
できる状態と非優先でデータを送出できる状態の二状態
を持ち、一定時間毎に全ての待ち行列を優先状態とする
リセット動作を行い、その後一定個数のデータを送出し
た待ち行列は非優先状態となり、優先状態にある待ち行
列からは非優先状態にある待ち行列よりも優先してデー
タを送り、優先状態にある待ち行列が無いとき若しくは
全ての優先状態にある待ち行列がデータを持たないとき
には、非優先状態にある待ち行列から、出力回線の余剰
容量を利用して、任意の比でデータを送出する。

【００２０】（７）前記（６）のデータ出力制御方法に
おいて、各待ち行列が、優先してデータを送出できる状
態と非優先でデータを送出できる状態の二状態を持つ上
に、さらに、その属する優先順位クラスに基づいて固定
的な優先順位を持つ。

【００２１】（８）前記（１）〜（７）のデータ出力制
御方法において、各待ち行列に対するリセット動作を、
リセット動作が指示された時に一斉に行うのではなく各
待ち行列で個別に行い、かつ、ある待ち行列に対するリ
セット動作は、リセット動作が指示された後、はじめて
該待ち行列に対してデータが入力された時に行う。

【００２２】（９）前記（８）のデータ出力制御方法に
おいて、最後にリセット動作が指示された時刻を記憶す
ると共に、各待ち行列が最後にリセット動作を行った時
刻を記憶し、各待ち行列にデータを格納する際、データ
を格納する待ち行列が最後にリセット動作を行った時刻
と、最後にリセット動作が指示された時刻とを比較し、
双方の時刻が異なっているときに該待ち行列に対してリ
セット動作を行う。

【００２３】（１０）前記（８）のデータ出力制御方法
において、リセット動作を指示した回数を記憶すると共
に、各待ち行列が実際にリセット動作を行った回数を記
憶し、各待ち行列にデータを格納する際、データを格納
する待ち行列が行ったリセット動作の回数と、リセット
動作が指示された回数とを比較し、双方の回数が異なっ
ているときに該待ち行列に対してリセット動作を行う。

【００２４】（１）〜（５）の構成においては、複数の
リストを用いてデータを出力すべき待ち行列の選択動作
を管理し、いずれかのリストの先頭から待ち行列番号を
取り出し、この番号の待ち行列からデータを出力するこ
とにより、待ち行列の選択動作の処理量の軽減を図り、
また、特定のリスト内の待ち行列番号の有無によって、
もしくは一定時間毎にリセット動作を行うことにより、
リセット動作を行うための条件判定の処理量の軽減を図
っている。

【００２５】（３），（４），（６）の構成において
は、各待ち行列が優先してデータを送出できる状態と非
優先でデータを送出できる状態の二状態を持ち、一定時
間毎にリセット動作を行って全ての待ち行列を優先状態
とし、各リセット周期内で保証される最低データ速度で
決まる個数のデータを送出した待ち行列は非優先状態と
なり、優先状態にある待ち行列は非優先状態にある待ち
行列よりも優先してデータを送ることができ、優先状態
にある待ち行列が無いとき若しくは全ての優先状態にあ
る待ち行列がデータを持たないときには、非優先状態に
ある待ち行列が出力回線の余剰容量を利用して、保証さ
れる最低データ速度の比とは別の比でデータを送出する
ことを図っている。

【００２６】（５），（７）の構成においては、各待ち
行列がその属する優先順位クラスに基づいて固定的な優
先順位を持つことにより、全ての待ち行列に対して最低
データ速度を保証しつつ、優先してデータを送出すべき
待ち行列から優先してデータを出力することを図ってい
る。

【００２７】（８）〜（１０）の構成においては、カウ
ンタのリセット動作を全ての待ち行列で一斉に行うので
はなく、或る待ち行列に対するリセット動作はリセット
動作が指示された後、はじめてその待ち行列に対してデ
ータが入力された時に行うことにより、リセット動作を
行うために同時に必要となる処理の処理量の軽減を図っ
ている。

【００２８】

【発明の実施の形態】次に本発明の実施例について図面
を参照して詳細に説明する。

【００２９】〔第一の実施例〕図１は本実施例のブロッ
ク図である。同図に示すように、データ出力制御装置１
００は、複数の待ち行列１３と、到着したデータの識別
を行いその属性（例えばサービスクラス）に応じた適切
な待ち行列１３にデータを格納するデータ識別部１１
と、データを出力すべき待ち行列１３を選択する待ち行
列選択部１２０と、待ち行列選択部１２０の指示により
待ち行列１３からデータを１つ取り出し出力回線に出力
する出力制御部１２とから構成される。

【００３０】また、待ち行列選択部１２０は、各待ち行
列１３毎にウエイトとカウンタの値を保持するカウンタ
値格納部１４０と、データを１つ以上待ちカウンタの値
が１以上である待ち行列の番号を保持する送出可能待ち
行列番号リスト３０と、データを１つ以上持ちカウンタ
の値が０である待ち行列の番号を保持する送出不可能待
ち行列番号リスト３１と、入力データを格納した待ち行
列１３の番号をデータ識別部１１から受け取り、その番
号を適切なリストに格納し或いは廃棄するリスト選択部
１５０と、リストのリセット動作を行うリセット制御部
４０とから構成される。

【００３１】図２は本実施例における待ち行列選択部１
２０の動作例を示すフローチャートである。

【００３２】次に、図１，図２を参照して本実施例の動
作について説明する。

【００３３】初期状態においては、送出可能待ち行列番
号リスト３０，送出不可能待ち行列番号リスト３１は共
に空であり、各待ち行列１３のカウンタはそれぞれのウ
エイトの値に設定されている。

【００３４】入力データがデータ出力制御装置１００に
到着すると、データ識別部１１によって適切な待ち行列
１３に格納されると同時に、その待ち行列番号が待ち行
列選択部１２０に送られる。

【００３５】待ち行列選択部１２０内のリスト選択部１
５０は、待ち行列番号を取得すると（Ｓ１）、その待ち
行列番号の待ち行列１３が今回の入力データ以外のデー
タを持っていれば（Ｓ２でＮ）、送られてきた待ち行列
番号を廃棄し（Ｓ３）、さもなければ（Ｓ２でＹ）、そ
の待ち行列のカウンタ値を調べ（Ｓ４）、その値が１以
上であれば（Ｓ４でＹ）、送出可能待ち行列番号リスト
３０の最後尾に当該待ち行列１３の番号を格納し（Ｓ
５）、その値が０であれば（Ｓ４でＮ）、送出不可能待
ち行列番号リスト３１の最後尾に当該待ち行列１３の番
号を格納する（Ｓ６）。

【００３６】次に各データ出力時間毎に、待ち行列選択
部１２０は、送出可能待ち行列番号リスト３０の先頭か
ら待ち行列番号を取り出す（Ｓ１４）。ただし、このリ
スト３０が空であれば（Ｓ１１でＹ）、リセット制御部
４０により、カウンタ値格納部１４０内の全ての待ち行
列１３のカウンタをそれぞれのウエイトの値に戻し（Ｓ
１２）、また送出不可能待ち行列番号リスト３１の内容
を全て送出可能待ち行列番号リスト３０に移動する（Ｓ
１３）リセット動作を行ってから、送出可能待ち行列番
号リスト３０の先頭から待ち行列番号を取り出す（Ｓ１
４）。取り出された待ち行列番号は、データ出力の指示
と共に出力制御部１２に送られる（Ｓ１５）。

【００３７】出力制御部１２では、上記取り出された待
ち行列番号に対応する待ち行列１３からデータを１つ取
り出して出力回線に出力する。

【００３８】リスト選択部１５０では、当該待ち行列１
３のカウンタの値を１つ減じ（Ｓ１６）、もしデータ出
力後の当該待ち行列１３内のデータ数が０であれば（Ｓ
１７でＮ）、当該待ち行列１３の待ち行列番号を廃棄し
（Ｓ１８）、さもなければ（Ｓ１７でＹ）、当該待ち行
列１３のカウンタ値を調べ（Ｓ１９）、その値が１以上
であれば（Ｓ１９でＹ）、送出可能待ち行列番号リスト
３０の最後尾に当該待ち行列１３の番号を格納し（Ｓ２
０）、その値が０であれば（Ｓ１９でＮ）、送出不可能
待ち行列番号リスト３１の最後尾に当該待ち行列１３の
番号を格納する（Ｓ２１）。

【００３９】図３に本実施例の動作例を示す。図３で
は、データ入力，データ出力およびリセット動作に伴
い、この直後に各リストの内容や各待ち行列のカウンタ
値，各待ち行列内のデータ数がどのように変化するかを
示している。ここでは、待ち行列数を２とし、待ち行列
１のウエイトを２，待ち行列２のウエイトを１とする。
図３より、待ち行列１と待ち行列２から、２対１の割合
でデータが出力されていることがわかる。

【００４０】このように本実施例は、データを１つ以上
持ちカウンタの値が１以上である待ち行列１３の番号を
保持する送出可能待ち行列番号リスト３０と、データを
１つ以上持ちカウンタの値が０である待ち行列１３の番
号を保持する送出不可能待ち行列番号リスト３１とを用
いて、同一の待ち行列番号が全リスト中に高々１つのみ
存在するように管理し、送出可能待ち行列番号リスト３
０の先頭に番号を持つ待ち行列１３からデータを送出す
ることにより、Ｗｅｉｇｈｔｅｄ ＲｏｕｎｄＲｏｂｉ
ｎ方式の第一の問題点を解決し、送出可能待ち行列番号
リスト３０が空であるか否かによりリセットの判定を行
うことにより、Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂ
ｉｎ方式の第二の問題点を解決している。

【００４１】〔第二の実施例〕図４は本実施例のブロッ
ク図である。同図に示すように、本実施例のデータ出力
制御装置１０３の構成は、第一の実施例の構成とほぼ同
様であるが、送出可能待ち行列番号リスト３０が送出可
能優先待ち行列番号リスト３２となり、送出不可能待ち
行列番号リスト３１が送出可能非優先待ち行列番号リス
ト３３となり、定期的にリスト動作を指示するタイマ２
３が加わっている。

【００４２】図５は本実施例における待ち行列選択部１
２３の動作を示すフローチャートである。

【００４３】次に、図４，図５を用いて本実施例の動作
について説明する。

【００４４】初期状態においては、送出可能優先待ち行
列番号リスト３２，送出可能非優先待ち行列番号リスト
３３は共に空であり、各待ち行列１３のカウンタはそれ
ぞれのウエイトの値に設定されている。

【００４５】入力データがデータ出力制御装置１０３に
到着すると、データ識別部１１によって適切な待ち行列
１３に格納されると同時に、その待ち行列番号が待ち行
列選択部１２３に送られる。

【００４６】待ち行列選択部１２３内のリスト選択部１
５１は、待ち行列番号を取得すると（Ｓ３１）、その待
ち行列番号の待ち行列１３が今回の入力データ以外のデ
ータを持っていれば（Ｓ３２でＮ）、送られてきた待ち
行列番号を廃棄し（Ｓ３３）、さもなければ（Ｓ３２で
Ｙ）、その待ち行列のカウンタ値を調べ（Ｓ３４）、そ
の値が１以上であれば（Ｓ３４でＹ）、送出可能優先待
ち行列番号リスト３２の最後尾に当該待ち行列１３の番
号を格納し（Ｓ３５）、その値が０であれば（Ｓ３４で
Ｎ）、送出可能非優先待ち行列番号リスト３３の最後尾
に当該待ち行列１３の番号を格納する（Ｓ３６）。

【００４７】次に各データ出力時間毎に、待ち行列選択
部１２３は、送出可能優先待ち行列番号リスト３２の先
頭から待ち行列番号を取り出し（Ｓ４２）、もしこのリ
スト３２が空であれば（Ｓ４１でＹ）、代わりに送出可
能非優先待ち行列番号リスト３３の先頭から待ち行列番
号を取り出す（Ｓ４３）。取り出された待ち行列番号
は、データ出力の指示と共に出力制御部１２に送られる
（Ｓ４４）。

【００４８】出力制御部１２では、上記取り出された待
ち行列番号に対応する待ち行列１３からデータを１つ取
り出して出力回線に出力する。

【００４９】リスト選択部１５１では、当該待ち行列１
３のカウンタの値を１つ減じ（Ｓ４５）、データ出力後
の当該待ち行列１３内のデータ数が０であれば（Ｓ４６
でＮ）、当該待ち行列１３の待ち行列番号を廃棄し（Ｓ
４７）、さもなければ（Ｓ４６でＹ）、当該待ち行列１
３のカウンタ値を調べ（Ｓ４８）、その値が１以上であ
れば（Ｓ４８でＹ）、送出可能優先待ち行列番号リスト
３２の最後尾に当該待ち行列１３の番号を格納し（Ｓ４
９）、その値が０であれば（Ｓ４８でＮ）、送出可能非
優先待ち行列番号リスト３３の最後尾に当該待ち行列１
３の番号を格納する（Ｓ５０）。

【００５０】リセット動作は、タイマ２３により定期的
に行われる。リセット時、リセット制御部４０により、
カウンタ値格納部１４０内の全ての待ち行列１３のカウ
ンタをそれぞれのウエイトの値に戻し（Ｓ５１）、また
送出可能非優先待ち行列番号リスト３３の内容を全て送
出可能優先待ち行列番号リスト３２に移動する（Ｓ５
２）。

【００５１】図６に本実施例の動作例を示す。図６で
は、データ入力，データ出力およびリセット動作に伴
い、この直後に各リストの内容や各待ち行列のカウンタ
値，各待ち行列内のデータ数がどのように変化するかを
示している。ここでは、待ち行列数を２とし、待ち行列
１のウエイトを２，待ち行列２のウエイトを１とし、リ
セット間隔を７データ出力時間とする。図６より、待ち
行列１と待ち行列２から、最低データ速度保証分として
それぞれ２及び１個のデータを出力した後は、次のリセ
ットまで等しい割合でデータを送出していることがわか
る。

【００５２】このように本実施例は、データを１つ以上
持ちカウンタの値が１以上である待ち行列の番号を保持
する送出可能優先待ち行列番号リスト３２を用いて、カ
ウンタの値が１以上である待ち行列を優先状態としてカ
ウンタの値が０である待ち行列１３より優先してデータ
送出を行い、データを１つ以上持ちカウンタの値が０で
ある待ち行列の番号を保持する送出可能非優先待ち行列
番号リスト３３を用いて、カウンタの値が０である待ち
行列１３から各待ち行列１３で等しくデータ送出を行
い、定期的にリセット動作を行うことにより、各待ち行
列１３に対して最低データ速度を保証し且つ出力回線の
余剰容量を各待ち行列に等しく分配し、Ｗｅｉｇｈｔｅ
ｄ Ｒｏｕｎｄ Ｒｏｂｉｎ方式の第五の問題点を解決
している。

【００５３】また本実施例では、優先状態にある待ち行
列が存在してもこの待ち行列がデータを持たなければ、
優先状態にない待ち行列からデータを出力することがで
きるため、出力回線の容量を効率的に用いることができ
る。

【００５４】さらに本実施例は、送出可能優先待ち行列
番号リスト３２の先頭に番号を持つ待ち行列１３からデ
ータを送出することによりＷｅｉｇｈｔｅｄ Ｒｏｕｎ
ｄＲｏｂｉｎ方式の第一の問題点を解決し、定期的にリ
セット動作を行うことによりＷｅｉｇｈｔｅｄ Ｒｏｕ
ｎｄ Ｒｏｂｉｎ方式の第二の問題点を解決している。

【００５５】〔第三の実施例〕図７は本実施例のブロッ
ク図である。同図に示すように、本実施例のデータ出力
制御装置１０３の構成は、第二の実施例の構成とほぼ同
様であるが、送出不可能待ち行列番号リスト３１が加わ
っている。また、カウンタ値格納部１４１において各待
ち行列に対する余剰容量の使用可否の情報が更に加えら
れている。

【００５６】図８は本実施例における待ち行列選択部１
２３の動作を示すフローチャートであり、図５のフロー
チャートに対し、ステップＳ３７，Ｓ３８，Ｓ５３，Ｓ
５４が加わっている。また、ステップＳ５２の内容が変
更されている。

【００５７】次に、図７，図８を用いて本実施例の動作
について説明する。

【００５８】初期状態においては、送出不可能待ち行列
番号リスト３１，送出可能優先待ち行列番号リスト３
２，送出可能非優先待ち行列番号リスト３３は共に空で
あり、各待ち行列１３のカウンタはそれぞれのウエイト
の値に設定されている。

【００５９】入力データがデータ出力制御装置１０３に
到着すると、データ識別部１１によって適切な待ち行列
１３に格納されると同時に、その待ち行列番号が待ち行
列選択部１２３に送られる。

【００６０】待ち行列選択部１２３内のリスト選択部１
５１は、待ち行列番号を取得すると（Ｓ３１）、その待
ち行列番号の待ち行列１３が今回の入力データ以外のデ
ータを持っていれば（Ｓ３２でＮ）、送られてきた待ち
行列番号を廃棄し（Ｓ３３）、さもなければ（Ｓ３２で
Ｙ）、その待ち行列の余剰容量の使用可否の情報を調べ
（Ｓ３７）、使用不可であれば（Ｓ３７でＮ）、その待
ち行列の番号を送出不可能待ち行列番号リスト３１の最
後尾に格納する（Ｓ３８）。その待ち行列が余剰容量を
使用可であれば（Ｓ３７でＹ）、その待ち行列のカウン
タ値を調べ（Ｓ３４）、その値が１以上であれば（Ｓ３
４でＹ）、送出可能優先待ち行列番号リスト３２の最後
尾に当該待ち行列１３の番号を格納し（Ｓ３５）、その
値が０であれば（Ｓ３４でＮ）、送出可能非優先待ち行
列番号リスト３３の最後尾に当該待ち行列１３の番号を
格納する（Ｓ３６）。

【００６１】次に各データ出力時間毎に、待ち行列選択
部１２３は、送出可能優先待ち行列番号リスト３２の先
頭から待ち行列番号を取り出し（Ｓ４２）、もしこのリ
スト３２が空であれば（Ｓ４１でＹ）、代わりに送出可
能非優先待ち行列番号リスト３３の先頭から待ち行列番
号を取り出す（Ｓ４３）。取り出された待ち行列番号
は、データ出力の指示と共に出力制御部１２に送られる
（Ｓ４４）。

【００６２】出力制御部１２では、上記取り出された待
ち行列番号に対応する待ち行列１３からデータを１つ取
り出して出力回線に出力する。

【００６３】リスト選択部１５１では、当該待ち行列１
３のカウンタの値を１つ減じ（Ｓ４５）、データ出力後
の当該待ち行列１３内のデータ数が０であれば（Ｓ４６
でＮ）、当該待ち行列１３の待ち行列番号を廃棄し（Ｓ
４７）、さもなければ（Ｓ４６でＹ）、その待ち行列の
余剰容量の使用可否の情報を調べ（Ｓ５３）、使用不可
であれば（Ｓ５３でＮ）、その待ち行列の番号を送出不
可能待ち行列番号リスト３１の最後尾に格納する（Ｓ５
４）。その待ち行列が余剰容量を使用可であれば（Ｓ５
３でＹ）、当該待ち行列１３のカウンタ値を調べ（Ｓ４
８）、その値が１以上であれば（Ｓ４８でＹ）、送出可
能優先待ち行列番号リスト３２の最後尾に当該待ち行列
１３の番号を格納し（Ｓ４９）、その値が０であれば
（Ｓ４８でＮ）、送出可能非優先待ち行列番号リスト３
３の最後尾に当該待ち行列１３の番号を格納する（Ｓ５
０）。

【００６４】リセット動作は、タイマ２３により定期的
に行われる。リセット時、リセット制御部４０により、
カウンタ値格納部１４１内の全ての待ち行列１３のカウ
ンタをそれぞれのウエイトの値に戻し（Ｓ５１）、また
送出可能非優先待ち行列番号リスト３３および送出不可
能待ち行列番号リスト３１の内容を全て送出可能優先待
ち行列番号リスト３２に移動する（Ｓ５２）。

【００６５】図９に本実施例の動作例を示す。図９で
は、データ入力，データ出力およびリセット動作に伴
い、この直後に各リストの内容や各待ち行列のカウンタ
値，各待ち行列内のデータ数がどのように変化するかを
示している。ここでは、待ち行列数を２とし、待ち行列
１のウエイトを２，待ち行列２のウエイトを１とし、リ
セット間隔を７データ出力時間とする。また、待ち行列
１は余剰容量使用可、待ち行列２は余剰容量使用不可と
する。図９より、待ち行列１と待ち行列２から、最低デ
ータ速度保証分としてそれぞれ２及び１個のデータを出
力した後は、次のリセットまで、余剰容量使用可の待ち
行列１からのみデータを送出していることがわかる。

【００６６】このように本実施例は、第二の実施例と同
様にＷｅｉｇｈｔｅｄ ＲｏｕｎｄＲｏｂｉｎ方式の第
一、第二の問題点を解決し、さらに、特定の待ち行列へ
は出力回線の余剰容量を与えず、その他の待ち行列に対
しては、出力回線の余剰容量を等しく分配することによ
り第五の問題点を解決している。

【００６７】〔第四の実施例〕図１０は本実施例のブロ
ック図である。同図に示すように、本実施例のデータ出
力制御装置１０５の構成は、第二の実施例の構成とほぼ
同様であるが、動作切替部２４が加わっている。

【００６８】図１１は本実施例における待ち行列選択部
２０の動作を示すフローチャートであり、図５のフロー
チャートに対し、ステップＳ５５〜Ｓ５８が加わってい
る。

【００６９】次に、図１０，図１１を用いて本実施例の
動作について説明する。

【００７０】初期状態においては、送出可能優先待ち行
列番号リスト３２，送出可能非優先待ち行列番号リスト
３３は共に空であり、各待ち行列１３のカウンタはそれ
ぞれのウエイトの値に設定されている。

【００７１】入力データがデータ出力制御装置１０５に
到着すると、データ識別部１１によって適切な待ち行列
１３に格納されると同時に、その待ち行列番号が待ち行
列選択部２０に送られる。

【００７２】待ち行列選択部２０内のリスト選択部１５
２は、待ち行列番号を取得すると（Ｓ３１）、その待ち
行列番号の待ち行列１３が今回の入力データ以外のデー
タを持っていれば（Ｓ３２でＮ）、送られてきた待ち行
列番号を廃棄し（Ｓ３３）、さもなければ（Ｓ３２で
Ｙ）、その待ち行列のカウンタ値を調べ（Ｓ３４）、そ
の値が１以上であれば（Ｓ３４でＹ）、送出可能優先待
ち行列番号リスト３２の最後尾に当該待ち行列１３の番
号を格納し（Ｓ３５）、その値が０であれば（Ｓ３４で
Ｎ）、送出可能非優先待ち行列番号リスト３３の最後尾
に当該待ち行列１３の番号を格納する（Ｓ３６）。

【００７３】次に各データ出力時間毎に、待ち行列選択
部２０は、送出可能優先待ち行列番号リスト３２の先頭
から待ち行列番号を取り出し（Ｓ４２）、もしこのリス
ト３２が空であれば（Ｓ４１でＹ）、動作切替部２４に
よってタイマ２３により一定時間毎にリセット動作を行
うように設定されているか否かを調べ（Ｓ５５）、タイ
マによるリセット動作に設定されていれば（Ｓ５５で
Ｙ）、この時点ではリセット動作を行わず、送出可能非
優先待ち行列番号リスト３３の先頭から待ち行列番号を
取り出す（Ｓ４３）。他方、タイマによるリセット動作
でなく、送出可能優先待ち行列番号リスト３２内にデー
タが無い場合にリセット動作を行うよう動作切替部２４
で設定されている場合は（Ｓ５５でＮ）、リセット制御
部４０により、カウンタ値格納部１４０内の全ての待ち
行列１３のカウンタをそれぞれのウエイトの値に戻し
（Ｓ５６）、また送出可能非優先待ち行列番号リスト３
３の内容を全て送出可能優先待ち行列番号リスト３２に
移動する（Ｓ５７）リセット動作を行ってから、送出可
能優先待ち行列番号リスト３２の先頭から待ち行列番号
を取り出す（Ｓ４２）。取り出された待ち行列番号は、
データ出力の指示と共に出力制御部１２に送られる（Ｓ
４４）。

【００７４】出力制御部１２では、上記取り出された待
ち行列番号に対応する待ち行列１３からデータを１つ取
り出して出力回線に出力する。

【００７５】リスト選択部１５２では、当該待ち行列１
３のカウンタの値を１つ減じ（Ｓ４５）、データ出力後
の当該待ち行列１３内のデータ数が０であれば（Ｓ４６
でＮ）、当該待ち行列１３の待ち行列番号を廃棄し（Ｓ
４７）、さもなければ（Ｓ４６でＹ）、当該待ち行列１
３のカウンタ値を調べ（Ｓ４８）、その値が１以上であ
れば（Ｓ４８でＹ）、送出可能優先待ち行列番号リスト
３２の最後尾に当該待ち行列１３の番号を格納し（Ｓ４
９）、その値が０であれば（Ｓ４８でＮ）、送出可能非
優先待ち行列番号リスト３３の最後尾に当該待ち行列１
３の番号を格納する（Ｓ５０）。

【００７６】タイマ２３が一定時間を計時する毎に、待
ち行列選択部２０は、動作切替部２４によってタイマ２
３により一定時間毎にリセット動作を行うように設定さ
れているか否かを調べ（Ｓ５８）、そうであれば（Ｓ５
８でＹ）、リセット動作を行う。このリセット時、リセ
ット制御部４０により、カウンタ値格納部１４０内の全
ての待ち行列１３のカウンタをそれぞれのウエイトの値
に戻し（Ｓ５１）、また送出可能非優先待ち行列番号リ
スト３３の内容を全て送出可能優先待ち行列番号リスト
３２に移動する（Ｓ５２）。

【００７７】本実施例は、動作切替部２４により、送出
可能優先待ち行列番号リスト３２内にデータが無い場合
にリセット動作を行うように設定されている場合、送出
可能非優先待ち行列番号リスト３３によってデータが送
出される前に、前記事象によってリセット動作が行われ
るため、第一の実施例と等しい動作を行う。また、動作
切替部２４により、タイマにより一定時間毎にリセット
動作を行うように設定されている場合は、本実施例は第
二の実施例と等しい動作を行う。

【００７８】このように本実施例は、動作切替部２４に
よってリセット動作を切り替えることで、第一の実施例
の動作と第二の実施例の動作とを一つの装置で実現する
ことができる。

【００７９】なお、本実施例の考え方を第三の実施例に
適用することにより、動作切替部によるリセット動作の
切り替えによって、第一の実施例の動作と第三の実施例
の動作とを一つの装置で実現することも可能である。

【００８０】〔第五の実施例〕図１２は本実施例のブロ
ック図である。同図に示すように、データ出力制御装置
１０６は、複数の待ち行列１３と、到着したデータの識
別を行い適切な待ち行列１３に格納するデータ識別部１
１と、データを出力すべき待ち行列１３を選択する待ち
行列選択部１２６と、待ち行列選択部１２６の指示によ
り待ち行列１３からデータを１つ取り出し出力回線に出
力する出力制御部１２とから構成される。

【００８１】また、待ち行列選択部１２６は、各待ち行
列１３毎に最低データ保証用のウエイトと余剰容量用の
ウエイトとカウンタの値と待ち行列の優先度とを保持す
るカウンタ値格納部１４１と、データを１つ以上待ちカ
ウンタの値が１以上であり且つ優先状態にある待ち行列
の番号を保持する送出可能優先待ち行列番号リスト３２
と、データを１つ以上持ちカウンタの値が１以上であり
且つ優先状態にない待ち行列の番号を保持する送出可能
非優先待ち行列番号リスト３３と、データを１つ以上持
ちカウンタの値が０である待ち行列の番号を保持する送
出不可能待ち行列番号リスト３１と、データを格納した
待ち行列１３の番号をデータ識別部１１から受け取り、
その番号を適切なリストに格納或いは廃棄するリスト選
択部１５３と、リストのリセット動作を行う全待ち行列
用リセット制御部４１及び非優先状態待ち行列用リセッ
ト制御部４２とから構成される。

【００８２】図１３は本実施例における待ち行列選択部
１２６の動作例を示すフローチャートである。

【００８３】次に、図１２，図１３を参照して本実施例
の動作について説明する。

【００８４】初期状態においては、各リスト３１，３
２，３３は全て空であり、各待ち行列１３は優先状態に
あり、そのカウンタ値はそれぞれの最低データ速度保証
用ウエイトの値に設定されている。

【００８５】入力データがデータ出力制御装置１０６に
到着すると、データ識別部１１によって適切な待ち行列
１３に格納されると同時に、その待ち行列番号が待ち行
列選択部１２６に送られる。

【００８６】待ち行列選択部１２６内のリスト選択部１
５３は、待ち行列番号を取得すると（Ｓ６１）、その待
ち行列番号の待ち行列１３が今回の入力データ以外のデ
ータを持っているか（Ｓ６２でＮ）、持っていなくても
（Ｓ６２でＹ）、その待ち行列のカウンタ値と余剰容量
用ウエイトが共に０であれば（Ｓ６４でＮ，Ｓ６５で
Ｙ）、送られてきた待ち行列番号を廃棄し（Ｓ６３）、
その待ち行列のカウンタ値が０で余剰容量用ウエイトが
０でなければ（Ｓ６４でＮ，Ｓ６５でＮ）、送られてき
た待ち行列番号を送出不可能待ち行列番号リスト３１の
最後尾に格納する（Ｓ６９）。

【００８７】他方、待ち行列番号の待ち行列１３が今回
の入力データ以外のデータを持っていなくて（Ｓ６２で
Ｙ）、カウンタ値が１以上であれば（Ｓ６４でＹ）、そ
の待ち行列が優先状態か否かを調べ（Ｓ６６）、優先状
態であれば（Ｓ６６でＹ）、送出可能優先待ち行列番号
リスト３２の最後尾に当該待ち行列１３の番号を格納し
（Ｓ６７）、優先状態でなければ（Ｓ６６でＮ）、送出
可能非優先待ち行列番号リスト３３の最後尾に当該待ち
行列１３の番号を格納する（Ｓ６８）。

【００８８】次に各データ出力時間毎に、待ち行列選択
部１２６は、送出可能優先待ち行列番号リスト３２の先
頭から待ち行列番号を取り出す（Ｓ７２）。ただし、こ
のリスト３２が空であれば（Ｓ７１でＹ）、送出可能非
優先待ち行列番号リスト３３の先頭から待ち行列番号を
取り出す（Ｓ７６）。更に、このリスト３２も空であれ
ば（Ｓ７３でＹ）、非優先待ち行列に対するリセット動
作（Ｓ７４，Ｓ７５）を行った後、送出可能非優先待ち
行列番号リスト３３の先頭から待ち行列番号を取り出す
（Ｓ７６）。非優先状態待ち行列に対するリセット動作
では、リセット制御部４２により送出不可能待ち行列番
号リスト３１の内容を送出可能非優先待ち行列番号リス
ト３３に移動すると共に、カウンタ値格納部１４１内の
送出不可能となっていた待ち行列のカウンタの値を余剰
容量用ウエイトに設定する（Ｓ７４，Ｓ７５）。上記の
取り出された待ち行列番号は、データ出力の指示と共に
出力制御部１２に送られる（Ｓ７８）。

【００８９】出力制御部１２では、上記取り出された待
ち行列番号に対応する待ち行列１３からデータを１つ取
り出して出力回線に出力する。

【００９０】リスト選択部１５３では、当該待ち行列１
３のカウンタの値を１つ減じ（Ｓ７９）、データ出力後
の当該待ち行列１３内のデータ数が０であるか（Ｓ８０
でＮ）、０でなくても（Ｓ８０でＹ）、その待ち行列の
カウンタ値と余剰容量用ウエイトが共に０であれば（Ｓ
８２でＮ，Ｓ８７でＹ）、送られてきた待ち行列番号を
廃棄し（Ｓ８１）、その待ち行列のカウンタ値が０で余
剰容量用ウエイトが０でなければ（Ｓ８２でＮ，Ｓ８７
でＮ）、送られてきた待ち行列番号を送出不可能待ち行
列番号リスト３１の最後尾に格納する（Ｓ８８）。この
とき（カウンタ値が０のとき）、当該待ち行列を非優先
状態に変更する（Ｓ８６）。また、その待ち行列のカウ
ンタ値が１以上であれば（Ｓ８２でＹ）、その待ち行列
が優先状態か否かを調べ（Ｓ８３）、優先状態であれば
（Ｓ８３でＹ）、送出可能優先待ち行列番号リスト３２
の最後尾に当該待ち行列１３の番号を格納し（Ｓ８
４）、優先状態でなければ（Ｓ８３でＮ）、送出可能非
優先待ち行列番号リスト３３の最後尾に当該待ち行列１
３の番号を格納する（Ｓ８５）。

【００９１】全待ち行列に対するリセット動作は、タイ
マ２３により定期的に行われる。このリセット時には、
リセット制御部４１により、全ての待ち行列を優先状態
とし（Ｓ９１）、全ての待ち行列１３のカウンタ値をそ
れぞれの最低データ速度保証用ウエイトの値に戻し（Ｓ
９２）、送出不可能待ち行列番号リスト３１と送出可能
非優先待ち行列番号リスト３３の内容を全て送出可能優
先待ち行列番号リスト３２に移動する（Ｓ９３）。

【００９２】図１４に本実施例の動作例を示す。図１４
では、データ入力，データ出力およびリセット動作に伴
い、この直後に各リストの内容や各待ち行列のカウンタ
値，各待ち行列内のデータ数がどのように変化するかを
示している。ここでは、待ち行列数を２とし、待ち行列
１の最低データ速度保証用ウエイトを２，余剰容量用ウ
エイトを１とし、待ち行列２の最低データ速度保証用ウ
エイトを１，余剰容量用ウエイトを２とする。また最低
データ速度保証用のリセット周期を７データ出力時間と
する。図１４より、待ち行列１と待ち行列２がそれぞれ
の最低データ速度保証分として２及び１個のデータを出
力した後は、次のリセットまで１対２の割合でデータを
送出していることがわかる。

【００９３】このように本実施例は、データを１つ以上
持ちカウンタの値が１以上あり、かつ優先状態にある待
ち行列の番号を保持する送出可能優先待ち行列番号リス
ト３２を用いて、優先状態にある待ち行列から優先して
データ送出を行い、データを１つ以上持ちカウンタの値
が１以上であり、かつ優先状態にない待ち行列の番号を
保持する送出可能非優先待ち行列番号リスト３３と、デ
ータを１つ以上持ちカウンタの値が０である待ち行列の
番号を保持する送出不可能待ち行列番号リスト３１とを
用いて、非優先状態にある待ち行列から任意の比でデー
タ送出を行い、最低データ速度を保証するために定期的
に全待ち行列に対するリセット動作を行い、出力回線の
余剰容量を任意の比で各待ち行列に分配するため送出可
能非優先待ち行列番号リスト３３が空になる毎に非優先
状態にある待ち行列に対してリセット動作を行うことに
より、Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉｎ方式
の第五の問題点を解決し、また、第二の実施例と同様に
第一，第二の問題点を解決する。

【００９４】なお、本実施例は、全待ち行列に対するリ
セット動作の周期を無限大とし、余剰容量用のウエイト
に最低データ速度保証用のウエイトを設定することによ
り、第一の実施例と同様の動作を行う。また、本実施例
は、全待ち行列に対するリセット動作の周期を適当な時
間間隔に設定し、余剰容量用ウエイトを全て１とするこ
とにより、第二の実施例と同様の動作を行い、余剰容量
用のウエイトを余剰容量使用可の待ち行列に対しては
１、余剰容量使用不可の待ち行列に対しては０とするこ
とにより、第三の実施例と同様の動作を行う。

【００９５】〔第六の実施例〕図１５は本実施例のブロ
ック図である。同図に示すように、データ出力制御装置
１０７は、複数の待ち行列１３と、到着したデータの識
別を行い適切な待ち行列１３に格納するデータ識別部１
１と、データを出力すべき待ち行列１３を選択する最低
データ速度保証用待ち行列選択部１２８及び余剰容量用
待ち行列選択部１２７と、タイマ２３と、待ち行列選択
部１２７及び１２８の指示により待ち行列１３からデー
タを１つ取り出し出力回線に出力する出力制御部１２と
から構成される。

【００９６】また、最低データ速度保証用待ち行列選択
部１２８は、各待ち行列１３毎に最低データ保証用のウ
エイトと余剰容量用のウエイトとカウンタの値と優先状
態とを保持するカウンタ値格納部１４１と、前回データ
を送出した待ち行列の番号を保持する待ち行列番号保持
部２６と、判定部２０と、待ち行列番号加算部２７とか
ら構成される。さらに、余剰容量用待ち行列選択部１２
７は、前回データを送出した待ち行列の番号を保持する
待ち行列番号保持部２６と、判定部２１と、待ち行列番
号加算部２７とから構成される。カウンタ値格納部１４
１は、最低データ速度保証用待ち行列選択部１２８と余
剰容量用待ち行列選択部１２７とで共用される。

【００９７】図１６は本実施例における最低データ速度
保証用待ち行列選択部１２８及び余剰容量用待ち行列選
択部１２７の動作例を示すフローチャートである。

【００９８】次に、図１５，図１６を参照して本実施例
の動作について説明する。

【００９９】初期状態においては、各待ち行列１３は優
先状態となっており、各待ち行列のカウンタはそれぞれ
の最低データ速度保証用のウエイトの値となっている。

【０１００】最低データ速度保証用待ち行列選択部１２
８では、優先状態にありデータを有しカウンタ値が１以
上である待ち行列からデータ出力を行う待ち行列を巡回
的に選択し（Ｓ１０１〜Ｓ１０７，Ｓ１０９）、余剰容
量用待ち行列選択部１２７では非優先状態にありデータ
を有しカウンタ値が１以上である待ち行列からデータ出
力を行う待ち行列を巡回的に選択する（Ｓ１２１〜Ｓ１
２７，Ｓ１３１）。通常は、最低データ速度保証用待ち
行列選択部１２８で選ばれた待ち行列からデータ出力を
行い、ここで待ち行列が選択されなかったときのみ（Ｓ
１０８でＹ，Ｓ１３０でＹ）、余剰容量用待ち行列選択
部１２７で選択された待ち行列からデータ出力を行う。

【０１０１】また、最低データ速度保証用待ち行列選択
部１２８では、データを出力した待ち行列のカウンタ値
を１減じる（Ｓ１１０）。カウンタの値が０になった待
ち行列は非優先状態となる（Ｓ１１１，Ｓ１１２）。更
に、最低データ速度保証用待ち行列選択部１２８では、
タイマ２３による一定時間毎に、全ての待ち行列のカウ
ンタ値をそれぞれの最低データ速度保証用のウエイトの
値にするリセット動作を行い（Ｓ１４１）、かつ、全て
の待ち行列を優先状態とする（Ｓ１４２）。

【０１０２】他方、余剰容量用待ち行列選択部１２７で
は、データを出力した待ち行列のカウンタ値を１減じる
（Ｓ１３２）。また、選択される待ち行列が無くなる毎
に（Ｓ１２８でＹ）、非優先状態にある待ち行列のカウ
ンタ値をそれぞれの余剰容量用ウエイトの値にするリセ
ット動作を行う（Ｓ１２９）。

【０１０３】図１７に本実施例の動作例を示す。図１７
では、データ入力，データ出力およびリセット動作に伴
い、この直後に各待ち行列のカウンタ値，各待ち行列内
のデータ数がどのように変化するかを示している。ここ
では、図１２と同様の設定を行っている。図１７より、
待ち行列１と待ち行列２がそれぞれの最低データ速度保
証分として２及び１個のデータを出力した後は、次のリ
セットまで１対２の割合でデータを出力しているが、第
五の実施例とは若干、送出されるデータの順序が異なっ
ていることがわかる。

【０１０４】このように本実施例は、最低データ速度保
証用待ち行列選択部１２８と余剰容量用待ち行列選択部
１２７とを用いて、各待ち行列に対して最低データ速度
を保証し、余った出力回線の容量を各待ち行列において
任意の比で分配することにより、Ｗｅｉｇｈｔｅｄ Ｒ
ｏｕｎｄ Ｒｏｂｉｎ方式の第五の問題点を解決する。

【０１０５】なお、本実施例では、最低データ速度保証
用待ち行列選択部１２８と余剰容量用待ち行列選択部１
２７として、図２９に示されるＷｅｉｇｈｔｅｄ Ｒｏ
ｕｎｄ Ｒｏｂｉｎ方式を応用したが、図３０に示され
る、判定部を並列に持った構成を採用することも可能で
ある。

【０１０６】〔第七の実施例〕図１８は本実施例のブロ
ック図である。同図に示すように、本実施例のデータ出
力制御装置１０７は、第六の実施例のデータ出力制御装
置１０７とほぼ同様な構成を有する。但し、カウンタ値
格納部１４０には余剰容量用のウエイトは存在しない。
従って、余剰容量用待ち行列選択部１２７では待ち行列
内のデータ数のみでデータ送出の可否を判断し、リセッ
ト動作は行わない。即ち、本実施例において余剰容量用
待ち行列選択部１２７はポーリング動作を行う。

【０１０７】図１９は本実施例における最低データ速度
保証用待ち行列選択部１２８及び余剰容量用待ち行列選
択部１２７の動作例を示すフローチャートである。図１
６に存在するステップＳ１２６，Ｓ１２８，Ｓ１２９は
無い。

【０１０８】次に、図１８，図１９を参照して本実施例
の動作について説明する。

【０１０９】初期状態においては、各待ち行列１３は優
先状態となっており、各待ち行列のカウンタはそれぞれ
の最低データ速度保証用のウエイトの値となっている。

【０１１０】最低データ速度保証用待ち行列選択部１２
８では、優先状態にありデータを有しカウンタ値が１以
上である待ち行列からデータ出力を行う待ち行列を巡回
的に選択し（Ｓ１０１〜Ｓ１０７，Ｓ１０９）、余剰容
量用待ち行列選択部１２７では非優先状態にありデータ
を有する待ち行列からデータ出力を行う待ち行列を巡回
的に選択する（Ｓ１２１〜Ｓ１２７，Ｓ１３１）。通常
は、最低データ速度保証用待ち行列選択部１２８で選ば
れた待ち行列からデータ出力を行い、ここで待ち行列が
選択されなかったときのみ（Ｓ１０８でＹ，Ｓ１３０で
Ｙ）、余剰容量用待ち行列選択部１２７で選択された待
ち行列からデータ出力を行う。

【０１１１】また、最低データ速度保証用待ち行列選択
部１２８では、データを出力した待ち行列のカウンタ値
を１減じる（Ｓ１１０）。カウンタの値が０になった待
ち行列は非優先状態となる（Ｓ１１１，Ｓ１１２）。更
に、最低データ速度保証用待ち行列選択部１２８では、
タイマ２３による一定時間の計測毎に、全ての待ち行列
のカウンタ値をそれぞれの最低データ保証用のウエイト
の値にするリセット動作を行い（Ｓ１４１）、かつ、全
ての待ち行列を優先状態とする（Ｓ１４２）。

【０１１２】図２０に本実施例の動作例を示す。図２０
では、データ入力，データ出力およびリセット動作に伴
い、この直後に各待ち行列のカウンタ値，各待ち行列内
のデータ数がどのように変化するかを示している。ここ
では、図１２と同様の設定を行っている。図２０より、
待ち行列１と待ち行列２がそれぞれの最低データ速度保
証分として２及び１個のデータを出力した後は、次のリ
セットまで等しい割合でデータを出力していることがわ
かる。

【０１１３】このように本実施例は、最低データ速度保
証用待ち行列選択部１２８と余剰容量用待ち行列選択部
１２７とを用いて、各待ち行列に対して最低データ速度
を保証し、余った出力回線の容量を各待ち行列において
等分で分配することにより、Ｗｅｉｇｈｔｅｄ Ｒｏｕ
ｎｄ Ｒｏｂｉｎ方式の第五の問題点を解決する。

【０１１４】なお、本実施例では、最低データ速度保証
用待ち行列選択部１２８と余剰容量用待ち行列選択部１
２７として、図２９に示されるＷｅｉｇｈｔｅｄ Ｒｏ
ｕｎｄ Ｒｏｂｉｎ方式を応用したが、図３０に示され
る、判定部を並列に持った構成を採用することも可能で
ある。

【０１１５】〔第八の実施例〕本実施例は、第一の実施
例を拡張し、各待ち行列を２つの優先順位クラス、即ち
クラス１とクラス２に分けたものである。

【０１１６】図２１は本実施例のブロック図である。同
図に示すように、データ出力制御装置１０９は、複数の
待ち行列１３と、到着したデータの識別を行い適切な待
ち行列１３に格納するデータ識別部１１と、データを出
力すべき待ち行列１３を選択する待ち行列選択部１３１
と、待ち行列選択部１３１の指示により待ち行列１３か
らデータを１つ取り出し出力回線に出力する出力制御部
１２とから構成される。

【０１１７】また、待ち行列選択部１３１は、各待ち行
列１３毎にウエイトとカウンタの値を保持するカウンタ
値格納部１４０と、データを１つ以上待ちカウンタの値
が１以上である待ち行列の番号を保持するクラス１用の
送出可能待ち行列番号リスト３４と、データを１つ以上
持ちカウンタの値が０である待ち行列の番号を保持する
クラス１用の送出不可能待ち行列番号リスト３５と、デ
ータを１つ以上待ちカウンタの値が１以上である待ち行
列の番号を保持するクラス２用の送出可能待ち行列番号
リスト３６と、データを１つ以上持ちカウンタの値が０
である待ち行列の番号を保持するクラス２用の送出不可
能待ち行列番号リスト３７と、入力データを格納した待
ち行列１３の番号をデータ識別部１１から受け取り、そ
の番号を適切なリストに格納或いは廃棄するリスト選択
部１５４と、リストのリセット動作を行う各クラス毎の
リセット制御部４０とから構成される。

【０１１８】図２２は本実施例における待ち行列選択部
１３１の動作例を示すフローチャートである。

【０１１９】次に、図２１，図２２を参照して本実施例
の動作について説明する。

【０１２０】初期状態においては、全てのリスト３４〜
３７は共に空であり、各待ち行列１３のカウンタはそれ
ぞれのウエイトの値に設定されている。

【０１２１】入力データがデータ出力制御装置１０９に
到着すると、データ識別部１１によって適切な待ち行列
１３に格納されると同時に、その待ち行列番号が待ち行
列選択部１３１に送られる。

【０１２２】待ち行列選択部１３１内のリスト選択部１
５４は、待ち行列番号を取得すると（Ｓ１５１）、その
待ち行列番号の待ち行列１３が今回の入力データ以外の
データを持っていれば（Ｓ１５２でＮ）、送られてきた
待ち行列番号を廃棄し（Ｓ１５３）、さもなければ（Ｓ
１５２でＹ）、その待ち行列のカウンタ値を調べ（Ｓ１
５４）、その値が１以上であれば（Ｓ１５４でＹ）、当
該待ち行列が属する優先順位クラスの送出可能待ち行列
番号リスト３４または３６の最後尾に当該待ち行列１３
の番号を格納し（Ｓ１５５）、その値が０であれば（Ｓ
１５４でＮ）、当該待ち行列が属する優先順位クラスの
送出不可能待ち行列番号リスト３５または３７の最後尾
に当該待ち行列１３の番号を格納する（Ｓ１５６）。

【０１２３】次に各データ出力時間毎に、待ち行列選択
部１３１は、データを持つ送出可能待ち行列番号リスト
のうち最も優先順位の高いクラスのリスト（３４または
３６）の先頭から待ち行列番号を取り出す（Ｓ１６４，
Ｓ１６５，Ｓ１６６）。もし、全てのクラスの送出可能
待ち行列番号リスト３４，３６が空であれば（Ｓ１６１
でＹ）、リセット制御部４０により、全ての待ち行列１
３のカウンタをそれぞれのウエイトの値に戻し（Ｓ１６
２）、各クラスの送出不可能待ち行列番号リスト３５，
３７の内容全てを、対応するクラスの送出可能待ち行列
番号リスト３４，３６に移動する（Ｓ１６３）リセット
動作を行ってから、データを持つ送出可能待ち行列番号
リストのうち最も優先順位の高いクラスのリスト（３４
または３６）の先頭から待ち行列番号を取り出す（Ｓ１
６４，Ｓ１６５，Ｓ１６６）。取り出された待ち行列番
号は、データ出力の指示と共に出力制御部１２に送られ
る（Ｓ１６７）。

【０１２４】出力制御部１２では、上記取り出された待
ち行列番号に対応する待ち行列１３からデータを１つ取
り出して出力回線に出力する。

【０１２５】リスト選択部１５４では、当該待ち行列１
３のカウンタの値を１つ減じ（Ｓ１６８）、もしデータ
出力後の当該待ち行列１３内のデータ数が０であれば
（Ｓ１６９でＮ）、当該待ち行列１３の待ち行列番号を
廃棄し（Ｓ１７０）、さもなければ（Ｓ１６９でＹ）、
当該待ち行列１３のカウンタ値を調べ（Ｓ１７１）、そ
の値が１以上であれば（Ｓ１７１でＹ）、当該待ち行列
が属する優先順位クラスの送出可能待ち行列番号リスト
３４または３６の最後尾に当該待ち行列１３の番号を格
納し（Ｓ１７２）、その値が０であれば（Ｓ１７１で
Ｎ）、当該待ち行列が属する優先順位クラスの送出不可
能待ち行列番号リスト３５または３７の最後尾に当該待
ち行列１３の番号を格納する（Ｓ１７３）。

【０１２６】図２３に本実施例の動作例を示す。図２３
では、データ入力，データ出力およびリセット動作に伴
い、この直後に各リストの内容や各待ち行列のカウンタ
値，各待ち行列内のデータ数がどのように変化するかを
示している。ここでは、待ち行列数を２とし、待ち行列
１のウエイトを２，待ち行列２のウエイトを１とする。
優先順位クラスは２クラス設け、待ち行列１をクラス
１、待ち行列２をクラス２とする。図２３より、待ち行
列１と待ち行列２から、２対１の割合でデータが出力さ
れ、両待ち行列共にデータ出力可能な場合は待ち行列１
から優先してデータが出力されていることがわかる。

【０１２７】このように本実施例は、送出可能待ち行列
番号リストと送出不可能待ち行列番号リストとを優先順
位クラス１，２毎に持ち、データ送出時にクラス１に属
する待ち行列を優先的に選択することにより、全ての待
ち行列に対して最低データ速度を保証しつつ、クラス１
のデータを優先して送出し、Ｗｅｉｇｈｔｅｄ Ｒｏｕ
ｎｄ Ｒｏｂｉｎ方式の第四の問題点を解決する。ま
た、第一の実施例と同様の動作により、Ｗｅｉｇｈｔｅ
ｄ Ｒｏｕｎｄ Ｒｏｂｉｎ方式の第一，第二の問題点
を解決する。

【０１２８】なお、本実施例では、優先順位クラスを２
クラスとしたが、３クラス以上の優先順位クラスを設け
ることも可能である。

【０１２９】〔第９の実施例〕本実施例は、第２の実施
例を拡張し、各待ち行列を２つの優先順位クラス、即ち
クラス１とクラス２に分けたものである。

【０１３０】本実施例の構成は、第２の実施例の構成に
おいて、送出可能優先待ち行列番号リストと送出可能非
優先待ち行列番号リストとを優先順位クラス毎に持たせ
たものである。本実施例の動作は、第二の実施例の動作
とほぼ同様であり、相違点は、リストに待ち行列番号を
格納する際、その待ち行列が属する優先順位クラス別に
格納することと、データを送出する際、データを持つ送
出可能優先待ち行列番号リストの中で最も優先順位が高
いものから待ち行列番号を取り出し、もし全ての送出可
能優先待ち行列番号リストが空であれば、データを持つ
送出可能非優先待ち行列番号リストの中で最も優先順位
が高いものから待ち行列番号を取り出すことと、リセッ
ト動作を行う際、各送出可能非待ち行列番号リスト内の
待ち行列番号を同じ優先順位クラスの送出可能優先待ち
行列番号リストへ移すことである。

【０１３１】本実施例は、各リストを優先順位クラス毎
に２つずつ持ち、データ送出時にクラス１に属する待ち
行列を優先的に選択することにより優先順位の高いクラ
スの待ち行列のデータを優先して送出しつつ、全ての優
先順位クラスに対して最低データ速度を保証し、出力回
線の余剰容量は最も優先順位に高いクラス内の待ち行列
によって等分し、以下、上位の優先順位クラスが出力回
線の容量を余らせた時のみ、次に上位の優先順位クラス
がその余った容量をクラス内の待ち行列で等分し、Ｗｅ
ｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉｎ方式の第四，第
五の問題点を解決する。また第二の実施例と同様の動作
により、Ｗｅｉｇｈｔｅｄ ＲｏｕｎｄＲｏｂｉｎ方式
の第一，第二の問題点を解決する。

【０１３２】なお、本実施例では、優先順位クラスを２
クラスとしたが、３クラス以上の優先順位クラスを設け
ることも可能である。

【０１３３】〔第十の実施例〕本実施例は、第五の実施
例を拡張し、各待ち行列を２つの優先順位クラス、即ち
クラス１とクラス２に分けたものである。

【０１３４】本実施例の構成は、第五の実施例の構成に
おいて、各リストを優先順位クラス毎に持たせたもので
ある。本実施例の動作は、第五の実施例の動作とほぼ同
様であり、相違点は、リストに待ち行列番号を格納する
際、その待ち行列が属する優先順位クラス別に格納する
ことと、データを送出する際、データを持つ送出可能優
先待ち行列番号リストの中で最も優先順位が高いものか
ら待ち行列番号を取り出し、もし全ての優先順位クラス
の送出可能優先待ち行列番号リストが空であれば、デー
タを持つ送出可能非優先待ち行列番号リストの中で最も
優先順位が高いものから待ち行列番号を取り出すこと
と、非優先待ち行列に対するリセット動作は、全ての優
先順位クラスの非優先待ち行列が空である時に行われる
ことと、全待ち行列に対するリセット動作および非優先
待ち行列に対するリセット動作を行う際、同優先順位ク
ラス内でリスト内の待ち行列番号の移動を行うことであ
る。

【０１３５】本実施例は、各リストを優先順位クラス毎
に２つずつ持ち、データ送出時にクラス１に属する待ち
行列を優先的に選択することにより、全ての待ち行列に
対して最低データ速度を保証し、余った出力回線の容量
も全ての待ち行列で任意の比で分配し、さらに、優先順
位の高いクラスの待ち行列のデータを優先して送出しつ
つも、最低保証分で送られているデータは余剰容量で送
られているデータよりも優先順位クラスに関係なく常に
優先して送出し、Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏ
ｂｉｎ方式の第一，第二，第四および第五の問題点を解
決する。

【０１３６】なお、本実施例では、優先順位クラスを２
クラスとしたが、３クラス以上の優先順位クラスを設け
ることも可能である。

【０１３７】〔第十一の実施例〕本実施例は、第十の実
施例の変形例である。第十の実施例と同様に全ての待ち
行列に対して最低データ速度を保証し、余った出力回線
の容量も全ての待ち行列で任意の比で分配するが、最低
データ速度保証分で送られているデータは余剰容量で送
られているデータより優先しつつも、これに関係なく優
先順位の高いクラスのデータを常に優先して送出し、Ｗ
ｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉｎ方式の第一，
第二，第四および第五の問題点を解決する。

【０１３８】本実施例の構成は第十の実施例の構成と同
様である。本実施例の動作と第十の実施例の動作との相
違点は、データを送出する際、送出可能優先待ち行列番
号リストもしくは送出可能非優先待ち行列番号リストの
どちらかにデータを持っている優先順位クラスの中で最
も優先順位が高いクラスを選択し、この優先順位クラス
の送出可能優先待ち行列番号リスト、もしくは送出可能
非優先待ち行列番号リストから待ち行列番号を取り出す
ことである。

【０１３９】なお、本実施例も第十の実施例と同様に、
３クラス以上の優先順位クラスを設けることも可能であ
る。

【０１４０】〔第十二の実施例〕本実施例のブロック図
を図２４に示す。本実施例は、第六もしくは第七の実施
例を拡張し、各待ち行列を２つの優先順位クラス、即ち
クラス１とクラス２とに分けたものである。本実施例の
構成は、第六もしくは第七の実施例において、最低デー
タ速度保証用待ち行列選択部１２８と余剰容量用待ち行
列選択部１２７をクラス毎に設けたものであり、データ
を送出する待ち行列を選択する際には、優先順位の高い
クラスの待ち行列選択部を優先しつつも、最低データ速
度保証用待ち行列選択部１２８は、余剰容量用待ち行列
選択部１２７よりもクラスに関係なく常に優先する。本
実施例は、送出されるデータの順序が若干異なることを
除いて、第十の実施例と同様の効果を持つ。

【０１４１】なお、本実施例では、優先順位クラスを２
クラスとしたが、３クラス以上の優先順位クラスを設け
ることも可能である。

【０１４２】〔第十三の実施例〕本実施例は、第六もし
くは第七の実施例を拡張し、各待ち行列を２つの優先順
位クラス、即ちクラス１とクラス２とに分けたものであ
る。本実施例の構成は、第十二の実施例と同様である
が、データを送出する待ち行列を選択する際には、最低
データ速度保証用待ち行列選択部を余剰容量待ち行列選
択部より優先しつつも、これに関係なく優先順位の高い
クラスの待ち行列選択部を優先する。本実施例は、送出
されるデータの順序が若干異なることを除いて、第十一
の実施例と同様の効果を持つ。

【０１４３】なお、３クラス以上の優先順位クラスを設
けることも可能である。

【０１４４】以上の各実施例においては、各待ち行列に
対するリセット動作を、リセット動作が指示された時に
一斉に行ったが、各待ち行列で個別に行い、ある待ち行
列に対するリセット動作は、リセット動作が指示された
後、はじめてその待ち行列にデータが到着した時に行う
ようにすれば、リセット動作時に同時に行う必要のある
処理の処理量が軽減され、Ｗｅｉｇｈｔｅｄ Ｒｏｕｎ
ｄ Ｒｏｂｉｎ方式の第三の問題点が解決される。以
下、このような分散型のリセット動作にかかる実施例に
ついて説明する。

【０１４５】〔第十四の実施例〕図２５は本実施例にお
けるカウンタ値格納部のブロック図である。同図に示す
ように、カウンタ値格納部１２４は、各待ち行列毎に、
カウンタ５０，ウエイト５１，最後にカウンタのリセッ
トを行った時刻を保持するカウンタリセット時刻５２を
持つ待ち行列テーブル６０と、現在時刻を計時する時計
５７と、最後にリセットが指示された時刻を記憶するリ
セット時刻５８と、カウンタ値更新演算部５４と、カウ
ンタリセット時刻５２とリセット時刻５８との比較結果
に応じてリセット演算部５５に対してカウンタのリセッ
ト動作を指示する比較部５６とで構成される。

【０１４６】本実施例のカウンタ値格納部１４２は、従
来のＷｅｉｇｈｔｅｄ ＲｏｕｎｄＲｏｂｉｎ方式のデ
ータ出力制御装置の他、第一から第七までの実施例にお
けるカウンタ値格納部として適用可能である。以下で
は、本実施例のカウンタ値格納部１４２を、第一の実施
例で採用した場合、つまり図１のカウンタ値格納部１４
０を本実施例のカウンタ値格納部１４２とした場合の待
ち行列選択部１２０の動作を説明する。

【０１４７】図２６は本実施例のカウンタ値格納部１４
２を第一の実施例で採用した場合の待ち行列選択部１２
０の動作例を示すフローチャートである。図２のフロー
チャートと相違するのは、ステップＳ１８１〜Ｓ１８４
である。以下、図２５，図２６および図１を参照して動
作を説明する。

【０１４８】データ出力時、待ち行列選択部１２０のリ
セット制御部４０は、送出可能待ち行列番号リスト３０
が空であれば（Ｓ１１でＹ）、カウンタ値格納部１４２
にリセット信号を送ってリセット動作を指示し、カウン
タ値格納部１４２では、このときリセット時刻５８を時
計５７が計時する現在時刻に更新する（Ｓ１８４）。各
待ち行列１３に対応するカウンタ５０はこの時点ではリ
セットされない。

【０１４９】データ出力制御装置１００にデータが入力
されると、データ識別部１１からデータを格納した待ち
行列１３の番号がリスト選択部１５０を通じてカウンタ
値格納部１４２に送られ、カウンタ値格納部１４２の比
較部５６は、この送られてきた待ち行列番号の待ち行列
に対応するカウンタリセット時刻５２とリセット時刻５
８とを比較し（Ｓ１８１）、もし異なっていれば（Ｓ１
８１でＮ）、リセット演算部５５によりその待ち行列の
カウンタ５０を、その待ち行列のウエイト５１にリセッ
トする（Ｓ１８２）。このとき、カウンタリセット時刻
５２の内容がリセット時刻５８に等しくなるように更新
される（Ｓ１８３）。また、各待ち行列からデータを出
力する際には、カウンタ値更新演算部５４により、対応
するカウンタ５０の値が１つ減じられる。

【０１５０】〔第十五の実施例〕図２７は本実施例にお
けるカウンタ値格納部のブロック図である。この実施例
のカウンタ値格納部１４３は、時刻の代わりにリセット
回数を用いて、第十四の実施例と同様の動作を可能とし
たものである。本実施例のカウンタ値格納部１４３は、
各待ち行列毎に、カウンタ５０，ウエイト５１，現在ま
でにカウンタのリセットを行った回数を保持するカウン
タリセットカウンタ５３を持つ待ち行列テーブル６１
と、現在までにリセット動作が指示された回数を示すリ
セットカウンタ５９と、カウンタ値更新演算部５４と、
カウンタリセットカウンタ５３とリセットカウンタ５９
との比較結果に応じてリセット演算部５５に対してカウ
ンタのリセット動作を指示する比較部５６とで構成され
る。

【０１５１】次に、図２７を参照して本実施例のカウン
タ値格納部１４３の動作を説明する。外部からのリセッ
ト信号でリセット動作が指示されたとき、リセットカウ
ンタ５９の値を１つ増す。そして、データ出力制御装置
にデータが入力され、データを格納した待ち行列の番号
が送られてくると、カウンタ値格納部１４３の比較部５
６は、この送られてきた待ち行列番号の待ち行列に対応
するカウンタリセットカウンタ５３とリセットカウンタ
５９とを比較し、もし異なっていればリセット演算部５
５によりその待ち行列のカウンタ５０を、その待ち行列
のウエイト５１にリセットする。このとき、カウンタリ
セットカウンタ５３の内容がリセットカウンタ５９に一
致するように更新される。また、各待ち行列からデータ
を出力する際には、カウンタ値更新演算部５４により、
対応するカウンタ５０の値が１つ減じられる。

【０１５２】本実施例のカウンタ値格納部１４３は、従
来のＷｅｉｇｈｔｅｄ ＲｏｕｎｄＲｏｂｉｎ方式のデ
ータ出力制御装置の他、第一から第七までの実施例にお
けるカウンタ値格納部として適用可能である。

【０１５３】〔第十六の実施例〕図２８は本実施例にお
けるカウンタ値格納部のブロック図である。本実施例の
カウンタ値格納部１４４は、同図に示すように、各待ち
行列毎に、カウンタ５０，複数種のウエイト５１，最後
にカウンタのリセットを行った時刻を保持するカウンタ
リセット時刻５２，待ち行列の状態６３を持つ待ち行列
テーブル６２と、現在時刻を計時する時計５７と、各状
態毎にその状態の待ち行列に対して最後にリセットが指
示された時刻を記憶するリセット時刻５８と、カウンタ
値更新演算部５４と、カウンタリセット時刻５２と該当
するリセット時刻５８との比較結果に応じてリセット演
算部５５に対してカウンタのリセット動作を指示する比
較部５６とで構成される。

【０１５４】次に、図２８を用いて本実施例の動作を説
明する。リセット動作が指示された時には対応するリセ
ット時刻５８を現在の時刻に更新する。そして、データ
出力制御装置にデータが入力されると、カウンタ値格納
部１４４の比較部５６は、データが格納された待ち行列
の待ち行列状態６３に対応するリセット時刻５８と該待
ち行列のカウンタリセット時刻５２を比較し、もし異な
っていればその待ち行列のカウンタ５０の値をその待ち
行列の状態に対応するウエイト５１にリセットする。各
待ち行列からデータを出力する際には、カウンタ値更新
部５４によりカウンタ５０の値を１つ減じる。また、待
ち行列の状態が変化した時には、この待ち行列のカウン
タリセット時刻５２を、該待ち行列の新たな状態に対応
するリセット時刻５８に設定する。

【０１５５】本実施例のカウンタ値格納部１４４は、待
ち行列の状態が動的に変化し、各々の状態毎に異なった
値にカウンタをリセットする必要がある場合に、Ｗｅｉ
ｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉｎ方式の第三の問題
点を解決する。待ち行列の状態を優先状態と非優先状態
の二状態とし、リセット信号１を優先状態にある待ち行
列に対するリセット信号、リセット信号２を非優先状態
にある待ち行列に対するリセット信号とすることによ
り、第八から第十三の実施例におけるカウンタ値格納部
として採用することができる。

【０１５６】なお、第十七の実施例として、第十四と第
十五との関係と同様に、第十六実施例において時刻の代
わりにリセット回数を用いたカウンタ値格納部も考えら
れる。この第十七の実施例は、第十六の実施例と同様に
第八から第十三の実施例におけるカウンタ値格納部とし
て採用することができる。

【０１５７】

【発明の効果】以上説明したように本発明によれば、各
待ち行列に対して最低のデータ送信速度を保証しつつ、
以下のような効果を得ることができる。

【０１５８】請求項１乃至５の発明においては、待ち行
列の選択動作の処理量の軽減とリセット動作を行うため
の条件判定の処理量の軽減とが可能となる。

【０１５９】請求項４，６の発明においては、出力回線
の余剰容量を任意の割合で各待ち行列に分配することが
できる。

【０１６０】請求項５，７の発明においては、各待ち行
列がその属する優先順位クラスに基づいて固定的な優先
順位を持つことにより、全ての待ち行列に対して最低デ
ータ速度を保証しつつ、優先してデータを送出すべき待
ち行列から優先してデータを出力することが可能とな
る。

【０１６１】請求項８〜１０の発明においては、リセッ
ト動作を行うために同時に必要になる処理の処理量の軽
減が可能となる。

【図面の簡単な説明】

【図１】本発明の第一の実施例にかかるデータ出力制御
装置のブロック図である。

【図２】本発明の第一の実施例にかかるデータ出力制御
装置における待ち行列選択部の動作例を示すフローチャ
ートである。

【図３】本発明の第一の実施例にかかるデータ出力制御
装置の動作例を示すタイミングチャートである。

【図４】本発明の第二の実施例にかかるデータ出力制御
装置のブロック図である。

【図５】本発明の第二の実施例にかかるデータ出力制御
装置における待ち行列選択部の動作例を示すフローチャ
ートである。

【図６】本発明の第二の実施例にかかるデータ出力制御
装置の動作例を示すタイミングチャートである。

【図７】本発明の第三の実施例にかかるデータ出力制御
装置のブロック図である。

【図８】本発明の第三の実施例にかかるデータ出力制御
装置における待ち行列選択部の動作例を示すフローチャ
ートである。

【図９】本発明の第三の実施例にかかるデータ出力制御
装置の動作例を示すタイミングチャートである。

【図１０】本発明の第四の実施例にかかるデータ出力制
御装置のブロック図である。

【図１１】本発明の第四の実施例にかかるデータ出力制
御装置における待ち行列選択部の動作例を示すフローチ
ャートである。

【図１２】本発明の第五の実施例にかかるデータ出力制
御装置のブロック図である。

【図１３】本発明の第五の実施例にかかるデータ出力制
御装置における待ち行列選択部の動作例を示すフローチ
ャートである。

【図１４】本発明の第五の実施例にかかるデータ出力制
御装置の動作例を示すタイミングチャートである。

【図１５】本発明の第六の実施例にかかるデータ出力制
御装置のブロック図である。

【図１６】本発明の第六の実施例にかかるデータ出力制
御装置における待ち行列選択部の動作例を示すフローチ
ャートである。

【図１７】本発明の第六の実施例にかかるデータ出力制
御装置の動作例を示すタイミングチャートである。

【図１８】本発明の第七の実施例にかかるデータ出力制
御装置のブロック図である。

【図１９】本発明の第七の実施例にかかるデータ出力制
御装置における待ち行列選択部の動作例を示すフローチ
ャートである。

【図２０】本発明の第七の実施例にかかるデータ出力制
御装置の動作例を示すタイミングチャートである。

【図２１】本発明の第八の実施例にかかるデータ出力制
御装置のブロック図である。

【図２２】本発明の第八の実施例にかかるデータ出力制
御装置における待ち行列選択部の動作例を示すフローチ
ャートである。

【図２３】本発明の第八の実施例にかかるデータ出力制
御装置の動作例を示すタイミングチャートである。

【図２４】本発明の第十二の実施例にかかるデータ出力
制御装置のブロック図である。

【図２５】本発明の第十四の実施例にかかるデータ出力
制御装置におけるカウンタ値格納部のブロック図であ
る。

【図２６】本発明の第十四の実施例にかかるデータ出力
制御装置における待ち行列選択部の動作例を示すフロー
チャートである。

【図２７】本発明の第十五の実施例にかかるデータ出力
制御装置におけるカウンタ値格納部のブロック図であ
る。

【図２８】本発明の第十六の実施例にかかるデータ出力
制御装置におけるカウンタ値格納部のブロック図であ
る。

【図２９】Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉｎ
方式を適用した従来のデータ出力制御装置のブロック図
である。

【図３０】Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉｎ
方式を適用した従来のデータ出力制御装置のブロック図
である。

【符号の説明】

１１…データ識別部 １２…出力制御部 １３…待ち行列 １８〜２２…判定部 ２３…タイマ ２４…動作切替部 ２６…待ち行列番号保持部 ２７…待ち行列番号加算部 ２８…選択回路 ３０…送出可能待ち行列番号リスト ３１…送出不可能待ち行列番号リスト ３２…送出可能優先待ち行列番号リスト ３３…送出可能非優先待ち行列番号リスト ３４…優先クラス１用の送出可能待ち行列番号リスト ３５…優先クラス１用の送出不可能待ち行列番号リスト ３６…優先クラス２用の送出可能待ち行列番号リスト ３７…優先クラス２用の送出不可能待ち行列番号リスト ４０…リセット制御部 ４１…全待ち行列用リセット制御部 ４２…非優先待ち行列用リセット制御部 ５０…カウンタ ５１…ウエイト ５２…カウンタリセット時刻 ５３…カウンタリセットカウンタ ５４…カウンタ値更新演算部 ５５…リセット演算部 ５６…比較部 ５７…時計 ５８…リセット時刻 ５９…リセットカウンタ ６０〜６２…待ち行列テーブル ６３…待ち行列状態 １００〜１０９…データ出力制御装置 １２０〜１２６…待ち行列選択部 １２７…余剰容量用待ち行列選択部 １２８…最低データ速度保証用待ち行列選択部 １４０〜１４４…カウンタ値格納部 １５０〜１５４…リスト選択部

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平４−176236（ＪＰ，Ａ) 特開 平２−113751（ＪＰ，Ａ) 特開 平９−186721（ＪＰ，Ａ) 特開 平９−231161（ＪＰ，Ａ) 特開 平10−190700（ＪＰ，Ａ) 特許2725475（ＪＰ，Ｂ２) 特許2967767（ＪＰ，Ｂ２) (58)調査した分野(Int.Cl.⁷，ＤＢ名) H04L 29/06 H04L 12/56 200

Claims (10)

(57)【特許請求の範囲】
1. 【請求項１】 複数の待ち行列を有し、入力データをそ
   の属性に基づいて適切な待ち行列に格納し、これらの待
   ち行列から単一の出力回線にデータを出力するデータ出
   力制御方法において、 待ち行列の番号を格納する複数のリストを使用し、同一
   の待ち行列番号は全リスト中に高々１つのみ存在するよ
   うにし、 入力データを待ち行列に格納する際、該待ち行列が入力
   データ以外のデータを持たなければ、該待ち行列のデー
   タ出力可否状態および優先度の内の少なくとも１つの条
   件に応じて適切なリストに該待ち行列番号を格納し、 データを出力回線に出力する際には、適切なリストを選
   択してそのリストの先頭から待ち行列番号を取り出し、
   取り出した番号の待ち行列からデータを１つ送出し、該
   待ち行列が、出力したデータ以外のデータを持てば前記
   条件により適切なリストに該待ち行列番号を格納し、 一定時間毎に、もしくは特定のリストが空になる毎に、
   各待ち行列の前記条件の変更と、リスト間での待ち行列
   番号の移動とを行うリセット動作を行うことを特徴とす
   るデータ出力制御方法。
2. 【請求項２】 複数の待ち行列を有し、入力データをそ
   の属性に基づいて適切な待ち行列に格納し、これらの待
   ち行列から単一の出力回線にデータを出力するデータ出
   力制御方法において、 データを持ち且つそのデータを出力可能な待ち行列の番
   号を保持する送出可能待ち行列番号リストと、データを
   持つがそのデータを出力できる状態にない待ち行列の番
   号を保持する送出不可能待ち行列番号リストとを使用
   し、同一の待ち行列番号は全リスト中に高々１つのみ存
   在するようにし、 入力データを待ち行列に格納する際、その待ち行列が入
   力データ以外のデータを持たない場合は該待ち行列から
   のデータ送出の可否に従って適切なリストに該待ち行列
   番号を格納し、 データを出力回線に出力する際には、送出可能待ち行列
   リストの先頭から待ち行列番号を取り出し、取り出した
   番号の待ち行列からデータを１つ送出し、データ送出後
   該待ち行列が出力されたデータ以外のデータを持つ場合
   は再び適切なリストに該待ち行列番号を格納し、前回の
   リセット動作以降に該待ち行列から出力されたデータの
   個数が一定数以上となると該待ち行列を送出不可能状態
   とし、また、データを出力する際に送出可能待ち行列番
   号リストが空であれば、全ての待ち行列をデータ送出可
   能状態とし、送出不可能待ち行列番号リストの内容を送
   出可能待ち行列番号リストに移動するリセット動作を行
   うことを特徴とするデータ出力制御方法。
3. 【請求項３】 複数の待ち行列を有し、入力データをそ
   の属性に基づいて適切な待ち行列に格納し、これらの待
   ち行列から単一の出力回線にデータを出力するデータ出
   力制御方法において、 データを持ち且つそのデータを優先して出力可能な待ち
   行列の番号を保持する送出可能優先待ち行列番号リスト
   と、データを持ち且つそのデータを非優先で出力可能な
   待ち行列の番号を保持する送出可能非優先待ち行列番号
   リストとを使用し、同一の待ち行列番号は全リスト中に
   高々１つのみ存在するようにし、 入力データを待ち行列に格納する際、その待ち行列が該
   入力データ以外のデータを持たない場合は待ち行列の現
   在の優先度に従って適切なリストに該待ち行列番号を格
   納し、 データを出力回線に出力する際には、送出可能優先待ち
   行列番号リストの先頭の待ち行列から待ち行列番号を取
   り出し、もし送出可能優先待ち行列番号リストが空であ
   れば送出可能非優先待ち行列番号リストの先頭から待ち
   行列番号を取り出し、取り出した番号の待ち行列からデ
   ータを１つ送出し、データ送出後該待ち行列が出力され
   たデータ以外のデータを持つ場合は再び該待ち行列の優
   先度に従って適切なリストに該待ち行列番号を格納し、
   前回のリセット動作以降に該待ち行列から出力されたデ
   ータの個数が一定数以上となると該待ち行列を非優先状
   態とし、 一定時間毎に、全ての待ち行列を優先状態とし、送出可
   能非優先待ち行列番号リストの内容を送出可能優先待ち
   行列番号リストに移動するリセット動作を行うことを特
   徴とするデータ出力制御方法。
4. 【請求項４】 複数の待ち行列を有し、入力データをそ
   の属性に基づいて適切な待ち行列に格納し、これらの待
   ち行列から単一の出力回線にデータを出力するデータ出
   力制御方法において、 データを持ち且つそのデータを優先して出力可能な待ち
   行列の番号を保持する送出可能優先待ち行列番号リスト
   と、データを持ち且つそのデータを非優先で出力可能な
   待ち行列の番号を保持する送出可能非優先待ち行列番号
   リストと、データを持つがそのデータを出力できる状態
   にない待ち行列の番号を保持する送出不可能待ち行列番
   号リストとを使用し、同一の待ち行列番号は全リスト中
   に高々１つのみ存在するようにし、 入力データを待ち行列に格納する際、その待ち行列が該
   入力データ以外のデータを持たない場合は該待ち行列の
   優先度と該待ち行列からのデータ送出の可否とに従って
   適切なリストに該待ち行列を格納し、 データを出力回線に出力する際には、送出可能優先待ち
   行列番号リストの先頭から待ち行列番号を取り出し、も
   し送出可能優先待ち行列番号リストが空であれば送出可
   能非優先待ち行列番号リストの先頭から待ち行列番号を
   取り出したのち該待ち行列を送出不可能状態とし、取り
   出した番号の待ち行列からデータ１つを送出し、データ
   送出後該待ち行列が出力されたデータ以外のデータを持
   つ場合は再び適切なリストに該待ち行列番号を格納し、
   また、前回の全待ち行列に対するリセット動作以降に該
   待ち行列から出力されたデータの個数が一定数以上とな
   ると該待ち行列を非優先状態とし、該待ち行列が非優先
   状態にあり且つ一度も非優先状態に対するリセット動作
   を受けていないか若しくは前回の非優先待ち行列に対す
   るリセット動作以降に該待ち行列から送出されたデータ
   の個数が別の一定個数以上であると該待ち行列をデータ
   送出不可能とし、 一定時間毎に全待ち行列に対するリセット動作、すなわ
   ち全ての待ち行列をデータ送出可能で且つ優先状態と
   し、送出可能非優先待ち行列番号リストの内容と送出不
   可能待ち行列番号リストの内容とを送出可能優先待ち行
   列番号リストに移動する動作を行い、また、送出可能非
   優先待ち行列番号リストが空となる毎に非優先待ち行列
   に対するリスト動作、すなわち送出不可能となっている
   待ち行列を全て送出可能状態とし、送出不可能待ち行列
   番号リストの内容を送出可能非優先待ち行列番号リスト
   に移動する動作を行うことを特徴とするデータ出力制御
   方法。
5. 【請求項５】 請求項１，２，３または４記載のデータ
   出力制御方法において、 各種別のリストをそれぞれ優先順位のクラス数分持ち、 各待ち行列がその属する優先順位クラスに基づいて固定
   的な優先順位を持ち、 リストに待ち行列番号を格納する際には、格納する種別
   のリストのうち該待ち行列が属する優先順位クラスのリ
   ストに待ち行列番号を格納し、リストから待ち行列番号
   を取り出す際には、取り出す種別のリストのうち、１つ
   以上待ち行列番号を持ち且つ最も優先順位の高いリスト
   から待ち行列番号を取り出すことを特徴とするデータ出
   力制御方法。
6. 【請求項６】 複数の待ち行列を有し、入力データをそ
   の属性に基づいて適切な待ち行列に格納し、これらの待
   ち行列から単一の出力回線にデータを出力するデータ出
   力制御方法において、 各待ち行列が優先してデータを送出できる状態と非優先
   でデータを送出できる状態の二状態を持ち、一定時間毎
   に全ての待ち行列を優先状態とするリセット動作を行
   い、その後一定個数のデータを送出した待ち行列は非優
   先状態となり、優先状態にある待ち行列からは非優先状
   態にある待ち行列よりも優先してデータを送り、優先状
   態にある待ち行列が無いとき若しくは全ての優先状態に
   ある待ち行列がデータを持たないときには、非優先状態
   にある待ち行列から、出力回線の余剰容量を利用して、
   任意の比でデータを送出することを特徴とするデータ出
   力制御方法。
7. 【請求項７】 請求項６記載のデータ出力制御方法にお
   いて、 各待ち行列が、優先してデータを送出できる状態と非優
   先でデータを送出できる状態の二状態を持つ上に、さら
   に、その属する優先順位クラスに基づいて固定的な優先
   順位を持つことを特徴とするデータ出力制御方法。
8. 【請求項８】 請求項１，２，３，４，５，６または７
   記載のデータ出力制御方法において、 各待ち行列に対するリセット動作を、リセット動作が指
   示された時に一斉に行うのではなく各待ち行列で個別に
   行い、かつ、ある待ち行列に対するリセット動作は、リ
   セット動作が指示された後、はじめて該待ち行列に対し
   てデータが入力された時に行うことを特徴とするデータ
   出力制御方法。
9. 【請求項９】 請求項８記載のデータ出力制御方法にお
   いて、 最後にリセット動作が指示された時刻を記憶すると共
   に、各待ち行列が最後にリセット動作を行った時刻を記
   憶し、 各待ち行列にデータを格納する際、データを格納する待
   ち行列が最後にリセット動作を行った時刻と、最後にリ
   セット動作が指示された時刻とを比較し、双方の時刻が
   異なっているときに該待ち行列に対してリセット動作を
   行うことを特徴とするデータ出力制御方法。
10. 【請求項１０】 請求項８記載のデータ出力制御方法に
    おいて、 リセット動作を指示した回数を記憶すると共に、各待ち
    行列が実際にリセット動作を行った回数を記憶し、 各待ち行列にデータを格納する際、データを格納する待
    ち行列が行ったリセット動作の回数と、リセット動作が
    指示された回数とを比較し、双方の回数が異なっている
    ときに該待ち行列に対してリセット動作を行うことを特
    徴とするデータ出力制御方法。