【手続補正書】
【提出日】平成18年8月15日(2006.8.15)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  それぞれ予約した帯域が保証されている複数の帯域保証キューと、それぞれ予め優先順序が設定されていて優先制御の対象となる複数の優先キューを有する優先キュークラスの各キューにそれぞれ格納されているパケットのうち最先に出力すべきパケットを選定するパケットスケジューリング方法であって、
各前記帯域保証キューに付与された重みと、前記優先キュークラス全体に付与された重みとを記憶し、
記憶した前記重みを参照し、前記帯域保証キューについてはバックログ状態のキューがあるときはそのキューの重みを、前記優先キュークラスについてはバックログ状態の前記優先キューがあるときは該優先キュークラスの重みを合計して合計値を計算し、
少なくとも、前記重みと、前記合計値と、前記優先順序の高いパケットであって前記優先キュークラスに最初に到着したパケットの最小到着時刻と、をパラメータとして、バックログ状態の各前記キューについてサービス時刻を計算し、
各前記サービス時刻相互間の大小比較により最小のサービス時刻を有する１のパケットを、前記の最先に出力すべきパケットとして、選定する、
ことを特徴とするパケットスケジューリング方法。
【請求項２】  前記サービス時刻の計算を、実時刻に代えて、仮想時刻を用いて行う請求項１に記載の方法。
【請求項３】  前記優先順序に従い選択されなかった前記優先キューについては、前記サービス時刻の計算の対象から除外する請求項１に記載の方法。
【請求項４】  それぞれ予約した帯域が保証されている複数の帯域保証キューと、それぞれ予め優先順序が設定されていて優先制御の対象となる優先キュークラスをなす複数の優先キューと、にそれぞれ格納されているパケットのうち最先に出力すべきパケットを選定するパケットスケジューリング装置であって、
入力された複数の所定のパラメータに基づき、バックログ状態の各前記帯域保証キューと、バックログ状態にあり、かつ、最も高い前記優先順序を有する前記優先キューとについて、それぞれのサービス時刻を計算するサービス時刻計算部と、
計算された各前記サービス時刻相互の大小比較をして、最小のサービス時刻を有するパケットを、前記の最先に出力すべきパケットとして、選定するサービス時刻比較部と、
前記帯域保証と、前記優先制御とを両立させるように計算された前記パラメータを生成するパラメータ生成部と、からなることを特徴とするパケットスケジューリング装置。
【請求項５】  前記パラメータ生成部は、
各前記帯域保証キューに付与された重みと、前記優先キュークラス全体に付与された重みとを、前記所定のパラメータとして、記憶する重み記憶手段を有する請求項４に記載の装置。
【請求項６】  前記パラメータ生成部は、
バックログ状態にある前記帯域保証キューおよび前記優先キューと、前記優先順序と、に関する各情報をもとに、１の優先キューを選択する優先キュー選択手段を有する請求項５に記載の装置。
【請求項７】  前記パラメータ生成部は、
前記優先キュー選択手段により選択された前記１の優先キューおよびバックログ状態にある前記帯域保証キューと、前記重み記憶手段から提供される当該バックログ状態にある前記キューについての各前記重みと、に関する各情報を入力として、各該キューの重みを合計してその合計値を計算する重み合計値計算手段を有する請求項６に記載の装置。
【請求項８】  前記パラメータ生成部は、
前記優先キュークラスに最初に到着したパケットの最小到着時刻を記憶する最小到着時刻記憶手段を有する請求項７に記載の装置。
【請求項９】  前記パラメータ生成部は、
前記サービス時刻計算部にて計算された前記サービス時刻に関連する計算時刻を、各前記パケット毎のサービス状況に応じて記憶し、かつ、該計算時刻を、次のパケットに対する計算のために該サービス時刻計算部にフィードバックするサービス時刻記憶手段を有する請求項８に記載の装置。
【請求項１０】  前記重み合計値計算手段は、
前記帯域保証キューについては、バックログ状態にある前記キューの前記重みを加算し、
前記複数の優先キューについては、いずれか１つがバックログ状態にあれば、前記優先キュークラスの前記重みを加算して前記合計値を計算する請求項７に記載の装置。
【請求項１１】  サービス時刻記憶手段は、
同一の前記キューから直前に出力されたパケットのサービス終了時刻を記憶し、
前記優先キュークラスの中で、最後に出力したパケットのサービス終了時刻を記憶する請求項９に記載の装置。
【請求項１２】  前記サービス時刻計算部は、
前記優先キュー選択手段により選択された前記優先キューについては、前記最小到着時刻と、サービス終了時刻と、前記優先キュークラスの重みによって、前記サービス時刻を計算する請求項８に記載の装置。
【請求項１３】  前記サービス時刻比較部は、前記優先キュー選択手段によって選択されなかった前記優先キューについては、前記の大小比較の対象から除外するために、前記サービス時刻として、該サービス時刻が通常取りうる最大値よりも大きい値を設定する請求項６に記載の装置。
【請求項１４】  前記優先キュー選択手段は、
各前記キューに前記パケットが格納されているか否かの情報を記憶するキュー状態記憶手段と、
各前記キューが前記優先キューか否かの情報を記憶する優先制御対象キュー記憶手段と、
前記優先順序に関する情報を記憶する優先順序記憶手段と、
前記の各情報をもとに、バックログ状態にある高優先のパケットを選択し、その選択情報を出力する請求項６に記載の装置。
【請求項１５】  各前記帯域保証キューに付与される前記重みの合計と、前記の最先に出力すべきパケットを送出する出力リンクの速度との差分により、前記優先キュークラス全体に付与される前記重みを設定する請求項５に記載の装置。
【請求項１６】  前記重み合計値計算手段からの出力をもとに仮想時刻を計算する仮想時刻計算手段をさらに設け、
前記最小到着時刻記憶手段は、計算された前記仮想時刻をもとに、前記優先キュークラスに最初に到着したパケットの到着時刻における該仮想時刻を記憶し、
前記サービス時刻計算部は、記憶した前記仮想時刻に基づいて、各前記帯域保証キューに対しおよび前記優先キュー選択手段により選択された前記優先キューに対し、それぞれ、前記サービス時刻を計算する請求項８に記載の装置。
【請求項１７】  入力された複数の所定のパラメータに基づき、各帯域保証キューと、高い優先順序を有する優先キューとについて、それぞれのサービス時刻を計算するサービス時刻計算部と、
計算された各サービス時刻相互の大小比較をして、最先に出力すべきパケットを選定するサービス時刻比較部と、
帯域保証と、優先制御とを両立させるように計算されたパラメータを生成するパラメータ生成部と、から構成される
ことを特徴とするパケットスケジューリング装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
まず、帯域保証を要求するトラヒックに対しては、各トラヒック毎に予約した帯域の相互の比に基づいて、各々の重みφｉを設定する。
一方、優先制御を要求するトラヒックに対しては、低優先トラヒックの重みφｉを、高優先トラヒックの重みφｉより小さく設定する。このように重みを設定することにより、帯域保証を要求するトラヒックに対しては予約帯域を保証することができる。一方、高優先トラヒックは、低優先トラヒックよりも大きい帯域（φｉ）が割当てられて、優先的に出力される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
重み記憶手段２２は、帯域保証キュー１３の各々の重みφｉ（上記の式（４））と、優先キュークラス１４の重みφｐ（上記の式（５））とを記憶する。
重み合計値計算手段２３は、キューセット１２内の各キューのバックログ状態に基づいて、パケットを格納している各キュー（１３，１４）が有する重みの合計値を計算する。優先キュー選択手段２１により優先キュー１４が選択されており、かつ、いずれかの帯域保証キュー１３がバックログ状態であれば、重み記憶手段２２を参照して、各φｉとφｐとを合計する。その合計値はφｂである。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
なお、各帯域保証キューｉの重みφｉと、優先キュークラスの重みφｐは、既述の式（４）および（５）に従い、
φｐ＝（Ｒ−ｗ ａｌｌ）／Ｒおよび
φｉ＝ｗ ｉ／Ｒ
によってそれぞれ求まる。前述のとおり、Ｒは出力リンク速度、ｗ ｉは各帯域保証キューｉの予約帯域、ｗ ａｌｌは帯域保証するトラヒックの予約帯域の合計である。
３）図４の重み合計値計算手段２３では、パケットを格納するキューすなわちアクティブなキューの全ての重みの合計値φｂを、下記ａ）およびｂ）のように計算し、サービス時刻計算手段２５に通知する（図２の〔３〕）。
ａ）優先キュークラス１４の中の少なくとも１つの優先キューがバックログ状態の場合
φｂ＝（バックログ状態の帯域保証キューφｉの重みの合計値Σφｉ）＋φｐｂ）優先キュークラス１４の優先キューの全てが空の場合
φｂ＝（バックログ状態の帯域保証キューφｉの重みの合計値Σφｉ）
なお、上記φｂの計算手順の具体例については、後に図６を参照して説明する。
４）図４の最小到着時刻記憶手段２４は、優先キュークラス１４の優先キューに格納されているパケットの中で、その到着時刻が最小のパケットの時刻、すなわち最先に到着した最小到着時刻をｔ ｍｉｎとして、サービス時刻計算手段２５に通知する（図４の〔４〕）。
５）図４のサービス時刻記憶手段２６は、サービス時刻計算手段２５で計算されたサービス時刻を、パケットと関連付けて記憶する。ここに記憶したサービス時刻は、サービス時刻計算手段２５に通知される（図４の〔５〕）。
６）図４のサービス時刻計算手段２５はキューｉのサービス時刻Ｆｉを計算し、この計算後のＦｉを再び記憶手段２６に格納すると共に（図４の〔６〕）、サービス時刻比較手段２７に通知する（図４の〔６〕′）。