(57)【要約】      （修正有）【課題】他の処理の負荷状況に応じてフロー間の比率を変えずにquantum値を変更することができるパケットスケジューリング方法を提供する。【解決手段】ＥＢＲＲ方式を用いてスケジュールラウンドごとに送信するパケットを決定するパケットスケジューリング方法であり、スケジューリング処理をＣＰＵ等によりソフトウェアで実現する際に、当該ＣＰＵ等が実行する他の処理の負荷状況に合わせて、各フロー間の比率を変えずにquantum値を変更することを可能とする。【選択図】図２
2013236124.tif 000002
【特許請求の範囲】
【請求項１】
パケット送信を行う通信装置において、ＥＢＲＲ方式を用いてスケジュールラウンドごとに送信するパケットを決定するパケットスケジューリング方法であって、
ｉを、フローを識別する識別番号とし、ＥＢＲＲ方式におけるCredit  Counterの１スケジューリングランドあたりの増分値であるquantum値をＱｉとし、ｊを０以上の整数とし、同一時点ではｊの値はフロー間で同一として、Ｑｉをフローｉの最小quantum値に２jを乗じた値として設定するquantum値設定ステップと、
ｊの最大値をＮとし、ＥＢＲＲ方式におけるQueue［ｉ］のリストであるActiveList［］の要素をチェックする際に使用するインデックス値の１スケジューリングランドあたりの増分値であるstrideを２jとし、各フローの最小quantum値のうちの最小値をminQsysとするとき、配列ActiveList［］のサイズｑを、ｑ＝ceil（（ceil（Ｌ／minQsys）＋１）／（２N））＊（２N）とする配列サイズ設定ステップと、
ＥＢＲＲ方式に従って、送信要求のあったパケットをフローｉのパケットに対応するパケットデータ格納用メモリのキューであるQueue［ｉ］に格納するとともに配列ActiveList［］にQueue［ｉ］を追加するデータ格納ステップと、
現在のスケジューリングランドをＲＣとするとき、当該スケジュールラウンドでのQueue［ｉ］の送信後に、Credit  Counterが１より小さくかつQueue［ｉ］が空でない場合、Queue［ｉ］をActiveList［（ＲＣ＋ceil（加算が必要なcredit値／Ｑｉ）＊２j）  mod  ｑ］の最後に追加するリスト追加ステップと、
quantum値を小さくする場合、ｊの値をこれまでのｊの値より小さい新たな値とし、新たなｊの値を用いて、Ｑｉをフローｉの最小quantum値に２jを乗じた値に更新するとともにstride値を２jに更新する更新ステップと、
を含むことを特徴とするパケットスケジューリング方法。
【請求項２】
quantum値を大きくする場合、ｊの値をこれまでのｊの値より大きい新たな値とし、新たなｊの値を用いて、Ｑｉをフローｉの最小quantum値に２jを乗じた値に更新するとともに、新たなｊの値に基づくActiveList［］のインデックス値を記憶するquantum更新ステップと、
quantum値を大きくする場合、現在のスケジューリングラウンドにおいてアクセスするActiveList［］のインデックス値と記憶しているインデックス値とが等しくなるとstride値を新たなｊに基づく２jに更新し、strideの更新までは更新前のstrideを用いてActiveList［］のインデックス値をスケジュールラウンドごとに更新するstride更新ステップと、
をさらに含むことを特徴とする請求項１に記載のパケットスケジューリング方法。
【請求項３】
ＥＢＲＲ方式を用いてスケジュールラウンドごとに送信するパケットを決定する通信装置であって、
ｉを、フローを識別する識別番号とし、送信要求のあったパケットをフローｉのパケットに格納するQueue［ｉ］をフローごとに備えるキュー部と、
ＥＢＲＲ方式におけるCredit  Counterの１スケジューリングランドあたりの増分値であるquantum値をＱｉとし、ｊを０以上の整数とし、同一時点ではｊの値はフロー間で同一として、Ｑｉをフローｉの最小quantum値に２jを乗じた値として設定し、ｊの最大値をＮとし、ＥＢＲＲ方式におけるQueue［ｉ］のリストであるActiveList［］の要素をチェックする際に使用するインデックス値の１スケジューリングランドあたりの増分値であるstrideを２jとし、各フローの最小quantum値のうちの最小値をminQsysとするとき、配列ActiveList［］のサイズｑを、ｑ＝ceil（（ceil（Ｌ／minQsys）＋１）／（２N））＊（２N）として設定し、ＥＢＲＲ方式に従って、送信要求のあったパケットをフローｉのパケットに対応するパケットデータ格納用メモリのキューであるQueue［ｉ］に格納するとともに配列ActiveList［］にQueue［ｉ］を追加し、現在のスケジューリングランドをＲＣとするとき、当該スケジュールラウンドでのQueue［ｉ］の送信後にCredit  Counterが１より小さく、かつQueue［ｉ］が空でない場合、Queue［ｉ］をActiveList［（ＲＣ＋ceil（加算が必要なcredit値／Ｑｉ）＊２j）  mod  ｑ］の最後に追加するスケジューリング処理部と、
を備え、
前記スケジューリング処理部は、quantum値を小さくする場合、ｊの値をこれまでのｊの値より小さい新たな値とし、新たなｊの値を用いて、Ｑｉをフローｉの最小quantum値に２jを乗じた値に更新するとともにstride値を２jに更新することを特徴とする通信装置。
【請求項４】
前記スケジューリング処理部は、quantum値を大きくする場合、ｊの値をこれまでのｊの値より大きい新たな値とし、新たなｊの値を用いて、Ｑｉをフローｉの最小quantum値に２jを乗じた値に更新するとともに、新たなｊの値に基づくActiveList［］のインデックス値を記憶し、現在のスケジューリングラウンドにおいてアクセスするActiveList［］のインデックス値と記憶しているインデックス値とが等しくなるとstride値を新たなｊに基づく２jに更新し、strideの更新までは更新前のstrideを用いてActiveList［］のインデックス値をスケジュールラウンドごとに更新することを特徴とする請求項３に記載の通信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットスケジューリング方法および通信装置に関する。
【背景技術】
【０００２】
パケットスケジューリングアルゴリズムとして、計算量がＯ（１）となるＯ（１）スケジューリング方式が複数提案されている。例えば、Deficit  Round  Robin（ＤＲＲ），Surplus  Round  Robin（ＳＲＲ），Eligibility  Based  Round  Robin（ＥＢＲＲ）（下記非特許文献１参照）等が挙げられる。
【０００３】
これらのうちLenziniらが提案したＥＢＲＲは、ＤＲＲやＳＲＲと異なり、quantum値（スケジューリングラウンド毎に各フローのCredit  Counterに加算する値）が最大パケットサイズ未満の場合でも計算量がＯ（１）であるという特徴を持っている。方式的には、ＥＢＲＲは、quantum値が最大パケットサイズ未満の場合でも計算量がＯ（１）である様に拡張したＳＲＲと見なすことができる。ＥＢＲＲの動作を以下に説明する。
【０００４】
ＥＢＲＲのパケットスケジューリングは、パケットのフローを単位として行う。即ち、パケットスケジューリングは、次に送信するパケットをどのフローの先頭パケットにするかを決定する処理を行う。パケットのフローは、例えばパケットの送信元と送信先のアドレスの値により特定される。
【０００５】
ＥＢＲＲでは、各フローｉ（ｉはフローを識別する識別番号）に対して、フローｉに属するパケットを１つのキューとして格納するためのQueue［ｉ］、フローｉからのパケット送信可否判断に使用するCredit  CounterであるＣｉ、１スケジューリングサイクルでのCredit  Counterの増分値quantum値Ｑｉを管理する。
【０００６】
また、ＥＢＲＲでは、配列ActiveList［］を管理する。ActiveList［］のインデックスはスケジューリングラウンドに対応し、ActiveList［］の要素は、インデックスが表わすスケジューリングラウンドでスケジューリング対象となるフローのQueue［ｉ］のリストである。以下では、最大パケットサイズをＬ、配列ActiveList［］のサイズをｑ、現在のスケジューリングラウンドをＲＣ（ＲＣ＝０，１，２，…）と表わす。このとき、ｑ＝ceil（Ｌ／（Ｑｉの最小値））となる。なお、ceil（ｘ）はｘ以上の最小の整数を返す関数である。
【０００７】
１スケジューリングラウンドでの処理は以下の様になる。
i）ActiveList［ＲＣ  mod  ｑ］（ｘ  mod  ｙ  は、ｘをｙで割った余りを示す）から最初の要素（Queue［ｉ］）を取り出す。Queue［ｉ］の先頭から１パケットをデキューし送信する。Ｃｉをパケット長分減算する。
ii）もし、Ｃｉ＞０かつQueue［ｉ］が空でなければ、Queue［ｉ］をActiveList［ＲＣ  mod  ｑ］の最後に追加する。もし、Ｃｉ≦０ならば、スケジューリングラウンド毎にＱｉをＣｉに加算することで、Ｃｉが０より大きくなるスケジューリングラウンドｒｃを求める。すなわち、ｒｃ＝ＲＣ＋floor（−Ｃｉ／Ｑｉ）＋１としてｒｃを求める。なお、floor（ｘ）はｘ以下の最大の整数を返す関数である。そして、Queue［ｉ］が空でなければ、Queue［ｉ］をActiveList［ｒｃ  mod  ｑ］の最後に追加し、ＣｉをスケジューリングラウンドｒｃでのＣｉ（Ｃｉ（更新前）＋（floor（−Ｃｉ／Ｑｉ）＋１）×Ｑｉ）の値に更新する。Queue［ｉ］が空であり、Queue［ｉ］のパケットがスケジューリングラウンドｒｃ以降ならば送信可能であることを記録し、Ｃｉの値をＱｉに更新する。
iii）フローｉに対してスケジューリングラウンドＲＣでパケットを受信した場合、Queue［ｉ］にパケットをエンキューする。もしQueue［ｉ］がエンキューする前は空であったならば、ｒｃをQueue［ｉ］内のパケットを送信可能なスケジューリングラウンドとすると、Queue［ｉ］をActiveList［max（ｒｃ，ＲＣ）  mod  ｑ］の最後に追加する。なお、max（ｘ，ｙ）はｘとｙのうち大きい方を出力する関数である。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】L．Lenzini，E．Mingozzi  and  G．Stea，“Eligibility−Based  Round  Robin  for  Fair  and  Efficient  Packet  Scheduling  in  Wormhole  Switching  Networks”，Trans．  On  Parallel  and  Distributed  Systems，Vol．15，No．3
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記従来のＥＢＲＲ技術によれば、フローのquantum値の間の比率を変えずにquantum値を小さくすることで、フロー間の公平性改善とフローのバースト性の削減が可能である。一方で、quantum値を小さくするとActiveList［］のサイズ（＝ｑ）が大きくなり、ActiveList［］の各要素に対して空でないかをチェックするための計算量が増える。１スケジューリングラウンドで送信されるデータ量をquantum値が表すことを考慮すると、より小さいquantum値を使用して、一定のデータ送信レートを維持する場合、単位時間当たりに実行するスケジューリングラウンド数が増える。これらのことより、quantum値を小さくすると計算量が増える。
【００１０】
ＥＢＲＲによるスケジューリング処理をＣＰＵ（Central  Processing  Unit）を用いてソフトウェアで実行する場合、ＣＰＵが実行する他の処理の負荷に応じて、公平性およびバースト性の改善と、計算量を増大させないことと、のどちらが優先であるかが変わる。したがって、ＣＰＵが実行する他の処理の負荷に応じて、各フロー間の比率を変えずquantum値を変更することが望ましい。しかし、従来のＥＢＲＲでは、スケジューリング処理実行中にquantum値を変更する場合の送信待ちパケットやデータ構造の扱いが規定されておらず、ＣＰＵが実行する他の処理の負荷に応じてquantum値を変更することの実現性が示されていないという問題があった。
【００１１】
本発明は、上記に鑑みてなされたものであって、スケジューリング処理をＣＰＵ等によりソフトウェアで実現する際に、当該ＣＰＵ等が実行する他の処理の負荷状況に合わせて、各フロー間の比率を変えずにquantum値を変更することが可能なパケットスケジューリング方法および通信装置を得ることを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するために、本発明は、パケット送信を行う通信装置において、ＥＢＲＲ方式を用いてスケジュールラウンドごとに送信するパケットを決定するパケットスケジューリング方法であって、ｉを、フローを識別する識別番号とし、ＥＢＲＲ方式におけるCredit  Counterの１スケジューリングランドあたりの増分値であるquantum値をＱｉとし、ｊを０以上の整数とし、同一時点ではｊの値はフロー間で同一として、Ｑｉをフローｉの最小quantum値に２jを乗じた値として設定するquantum値設定ステップと、ｊの最大値をＮとし、ＥＢＲＲ方式におけるQueue［ｉ］のリストであるActiveList［］の要素をチェックする際に使用するインデックス値の１スケジューリングランドあたりの増分値であるstrideを２jとし、各フローの最小quantum値のうちの最小値をminQsysとするとき、配列ActiveList［］のサイズｑを、ｑ＝ceil（（ceil（Ｌ／minQsys）＋１）／（２N））＊（２N）とする配列サイズ設定ステップと、ＥＢＲＲ方式に従って、送信要求のあったパケットをフローｉのパケットに対応するパケットデータ格納用メモリのキューであるQueue［ｉ］に格納するとともに配列ActiveList［］にQueue［ｉ］を追加するデータ格納ステップと、現在のスケジューリングランドをＲＣとするとき、当該スケジュールラウンドでのQueue［ｉ］の送信後に、Credit  Counterが１より小さくかつQueue［ｉ］が空でない場合、Queue［ｉ］をActiveList［（ＲＣ＋ceil（加算が必要なcredit値／Ｑｉ）＊２j）  mod  ｑ］の最後に追加するリスト追加ステップと、quantum値を小さくする場合、ｊの値をこれまでのｊの値より小さい新たな値とし、新たなｊの値を用いて、Ｑｉをフローｉの最小quantum値に２jを乗じた値に更新するとともにstride値を２jに更新する更新ステップと、を含むことを特徴とする。
【発明の効果】
【００１３】
本発明によれば、スケジューリング処理をＣＰＵ等によりソフトウェアで実現する際に、当該ＣＰＵ等が実行する他の処理の負荷状況に合わせて、各フロー間の比率を変えずにquantum値を変更することが可能となる、という効果を奏する。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明にかかる通信装置の構成例を示す図である。
【図２】図２は、パケット送信処理手順の一例を示す図である。
【図３−１】図３−１は、スケジューリング処理を実行するためのアルゴリズムの一例を示す図である。
【図３−２】図３−２は、スケジューリング処理を実行するためのアルゴリズムの一例を示す図である。
【図３−３】図３−３は、スケジューリング処理を実行するためのアルゴリズムの一例を示す図である。
【図３−４】図３−４は、スケジューリング処理を実行するためのアルゴリズムの一例を示す図である。
【図３−５】図３−５は、スケジューリング処理を実行するためのアルゴリズムの一例を示す図である。
【発明を実施するための形態】
【００１５】
以下に、本発明にかかるパケットスケジューリング方法および通信装置の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００１６】
実施の形態．
図１は、本発明にかかる通信装置の構成例を示す図である。本実施の形態の通信装置１は、ＣＰＵやＭＰＵ（Micro  Processing  Unit）等である制御部２と、タイマー部３と、Credit  Counter格納用メモリ４と、Quantum（quantum）値格納用メモリ５と、ActiveList格納用メモリ６と、パケットデータ格納用メモリ７と、処理待ちパケット情報格納用メモリ８と、キュー情報格納用メモリ９と、パケット入力部１０と、で構成される。
【００１７】
本実施の形態の通信装置は、本発明にかかるパケットスケジューリング方法（ＥＢＲＲを拡張したスケジューリング方法）によりパケットスケジューリング処理を実施してパケットを送信する。以下、本実施の形態では、通常のＥＢＲＲと同様に、各フローｉ（ｉはフローを識別する識別番号）に対して、フローｉに属するパケットを格納するためキューをQueue［ｉ］とし、フローｉからのパケット送信可否判断に使用するCredit  CounterをＣｉとし、１スケジューリングサイクルでのCredit  Counterの増分値quantum値をＱｉとし、配列ActiveList［］を管理する。ActiveList［］のインデックスはスケジューリングラウンドに対応し、ActiveList［］の要素は、インデックスが表わすスケジューリングラウンドでスケジューリング対象となるフローのQueue［ｉ］のリストである。また、以下では、配列ActiveList［］のサイズをｑ、現在のスケジューリングラウンドをＲＣ（ＲＣ＝０，１，２，…）と表わす。
【００１８】
制御部２は、パケット送信要求受付処理部２１と、スケジューリング処理部２２と、パケット送信処理部２３と、を備える。パケット送信要求受付処理部２１、スケジューリング処理部２２およびパケット送信処理部２３は、それぞれソフトウェアのプログラムとして図示しない記憶部に格納され、処理の実行時には、記憶部に格納されたプログラムに従って制御部２によりそれぞれの処理を実行する。
【００１９】
本実施の形態のパケットスケジューラは、パケット送信要求受付処理部２１、スケジューリング処理部２２、パケット送信処理部２３は、タイマー部３と、Credit  Counter格納用メモリ４、Quantum値格納用メモリ５、ActiveList格納用メモリ６、パケットデータ格納用メモリ７、処理待ちパケット情報格納用メモリ８、キュー情報格納用メモリ９およびパケット入力部１０で構成される。
【００２０】
パケット送信要求受付処理部２１は、通信装置１内のパケット入力部１０からパケット送信要求を受け付ける処理を行う。送信要求を受け付けたパケットをパケットデータ格納用メモリ７に保存し、当該パケットに関する情報を処理待ちパケット情報格納用メモリ８に格納する。
【００２１】
パケット入力部１０は、自身が生成したパケット（または他の装置や他の機能部から受信したパケット）とパケットの送信開始を要求する送信要求とをパケットスケジューラのパケット送信要求受付処理部２１へ入力する。
【００２２】
スケジューリング処理部２２は、タイマー部３から一定周期で起動され、起動されたタイミングでパケットスケジューリング処理を行い、送信するパケットを決定して当該パケットの送信要求をパケット送信処理部２３へ出力する。
【００２３】
パケット送信処理部２３は、スケジューリング処理部２２から受け取った送信要求に基づき、送信対象パケットをパケットデータ格納用メモリ７から読み出してネットワークインタフェース等へ送信する処理を行う。
【００２４】
タイマー部３は、パケットスケジューリング処理を起動する周期を管理し、指定された時間（割込み発生周期）毎にスケジューリング処理部２２を起動するためのＣＰＵへの割込みを発生させる。割込み発生周期はスケジューリング処理部２２が指定する。
【００２５】
パケットデータ格納用メモリ７は、パケットデータ本体を格納するメモリである。キュー情報格納用メモリ９は、本実施の形態のパケットスケジューリング処理で使用するQueue［ｉ］の情報を格納するメモリである。処理待ちパケット情報格納用メモリ８は、パケット送信要求受付処理部２１経由でパケットデータ格納用メモリ７に格納された、スケジューリング処理部２２の処理待ち状態のパケットの情報を格納するメモリである。
【００２６】
Credit  Counter格納用メモリ４は、本実施の形態のパケットスケジューリング処理で使用するCredit  CounterであるＣｉの情報を格納するメモリである。Quantum値格納用メモリ５は、本実施の形態のパケットスケジューリング処理で使用するQuantumであるＱｉの情報を格納するメモリである。ActiveList格納用メモリ６は、本実施の形態のパケットスケジューリング処理で使用するActiveList［］の情報を格納するメモリである。
【００２７】
図２は、本実施の形態の通信装置におけるパケット送信処理手順の一例を示す図である。図２を用いて本実施の形態の通信装置におけるパケット送信処理を説明する。図２では、quantum値の変更のない通常のスケジューリング処理を示している。
【００２８】
本実施の形態では、フローｉの最小quantum値をMinＱｉとするとき、フローｉのquantum値であるＱｉをMinＱｉ＊２j（ｊは、０以上の整数）とする。同一時点では、各フローのｊの値は同一とする。また、本実施の形態では、ActiveList［］の要素をチェックする時に使用するインデックスの増分値（スケジュールラウンド毎のＲＣの増分値）をstrideとよび、通常のスケジューリングプロセスでは２jをstrideとして使用する。また、ｊが取り得る最大の値をＮとし、各フロー毎の最小quantum値の中の最小値をminQsysと表し、パケット最大長をＬとするとき、配列ActiveList［］のサイズｑを、
ｑ＝ceil（（ceil（Ｌ／minQsys）＋１）／（２N））＊（２N）
とする。また、現在のスケジューリングラウンドにおけるパケットの送信の後にQueue［ｉ］が空でなく、Ｃｉが０より小さい場合、Queue［ｉ］は、ActiveList［（ＲＣ＋ceil（加算が必要なcredit値／Ｑｉ）＊２j）  mod  ｑ］の最後に追加される。加算が必要なcredit値とは、Ｃｉが０より小さい場合の−Ｃｉである。通常のスケジューリング処理における１スケジューリングラウンドでの処理は、以上述べた点と、後述するquantum値の変更に関連する処理を除き、従来のＥＢＲＲと同様である。
【００２９】
まず、通信装置１内のパケット入力部１０が、パケットスケジューラに対してパケット送信要求を入力する（ステップＳ１）。パケット送信要求受付処理部２１がパケット送信要求を受け付け、パケットデータ格納用メモリにパケットデータ本体を格納すると共に、処理待ちパケット情報格納用メモリ８に当該パケットの情報（例えば、パケット長、パケットが属するフロー決定に必要なヘッダ情報等）を既に格納済みの情報に追加して格納する（ステップＳ２）。
【００３０】
次に、タイマー部３は、一定時間が経過したか否かを管理し（ステップＳ３）、一定時間経過する（ステップＳ３  Ｙｅｓ）と、制御部２に対して割込みを発生させることによりスケジューリング処理部２２の処理が起動され、スケジューリング処理が開始される（ステップＳ４）。スケジューリング処理部２２は、処理待ちパケット情報格納用メモリ８にアクセスし、処理待ちパケット情報に基づいて後述のパケット到着処理によりパケットデータとフローを対応付けてフローごとにパケットをエンキューする（ステップＳ５）。なお、各フローに対応するキュー（Queue［ｉ］）は、パケットデータ格納用メモリ７に設けてもよいし、別途キュー部として設けてもよい。その後、スケジューリング処理部２２は、後述の本実施の形態のＥＢＲＲスケジューリング処理を実施し（ステップＳ６）、ＥＢＲＲスケジューリング処理の結果により、送信対象パケットが決定されるとともにその時点でのstrideの値であるCurStrideが決定される（ステップＳ７）。
【００３１】
スケジューリング処理部２２は、送信対象パケットをパケット送信処理部２３へ通知し、パケット送信処理部２３は、通知された送信対象パケットをパケットデータ格納用メモリ７から読み出して、送信する（ステップＳ８）。次に、スケジューリング処理部２２は、ＲＣにCurStrideを加算してＲＣの値を更新してそのスケジューリングラウンドの処理を終了し、ステップＳ３へ戻る。以上のように、一定時間ごとに、パケットスケジューラはパケットのスケジューリング処理を繰り返す。
【００３２】
図１では、制御部２として本実施の形態のパケットスケジューラの構成部を示しているが、実際には制御部２はパケットスケジューリング以外の他の処理も実施することが多い。ＥＢＲＲでは、フローのquantum値の間の比率を変えずにquantum値を小さくすることで、フロー間の公平性改善とフローのバースト性の削減が可能である。一方で、quantum値を小さくすると計算量が増える。例えば、制御部２において他の処理による負荷が多い場合には、計算量の増加は望ましくないが、制御部２において他の処理による負荷が少ない場合には、計算量が増加してもフロー間の公平性改善とフローのバースト性の削減を優先させる方がよい場合もある。このように、quantum値の最適値は、制御部２における他の処理による負荷に依存して変化する。
【００３３】
本実施の形態では、以下に示す手順により、スケジューリング処理の実行中に、フローのquantum値の間の比率を変えずにquantum値を変更可能とする。上述のように、本実施の形態では、ＱｉをMinＱｉ＊２jとしており、quantum値を変更する際には、ｊの値を変更する。
【００３４】
quantum値を小さくする場合、ｊをそれまでのｊより小さい値として決定し、スケジューリング処理部２２に対して、新たなｊ（または新たなstrideである２j）を指定してquantum値の更新を指示する。quantum値の更新の指示は、図示しない通信装置内の処理部が制御部２の負荷に応じて自動で生成するようにしてもよいし、運用者等からの入力を受け付けてスケジューリング処理部２２に入力されるようにしてもよい。
【００３５】
quantum値を小さくする指示があった場合、スケジューリング処理部２２は、Ｑｉを、新たなｊに対応する値（MinＱｉ＊２j）に更新する。また、stride値を新たなｊに対応する２jの値に更新する。quantum値を小さくし、新しい２jの値が古い（それまでの）２jの値より小さい場合、古いstride値（古い２jの値）は新しい２jの倍数となる。このため、新しい２jをstride値として使ってチェックされるActiveList［］の要素は、古いstride値でアクセスされたActiveList［］の要素を含む。よって、stride値を直ちに（quantum値を小さくする指示があったスケジューリングラウンドで）新しい２jの値に更新可能である。
【００３６】
quantum値を大きくする場合、ｊをそれまでのｊより大きい値として決定し、スケジューリング処理部２２に対して、新たなｊ（または新たなstrideである２j）を指定してquantum値の更新を指示する。
【００３７】
quantum値を大きくする指示があった場合、スケジューリング処理部２２は、Ｑｉを、新たなｊに対応する値（MinＱｉ＊２j）に直ちに（quantum値を小さくする指示があったスケジューリングラウンドで）更新する。そして、スケジューリング処理部２２は、quantum値が変更された場合のActiveList［］のインデックス値を記録し、スケジューリング処理でアクセスするActiveList［］のインデックス値が記録したインデックス値と等しくなるまでの間は、古いstride値を使い続ける。Queue［ｉ］からパケットを送信した後に、Queue［ｉ］からパケット送信可能となるスケジューリングラウンド（ActiveList［］のインデックス値）を計算する時に、以下の式（１）を用いる。
index＝（（floor（（ＲＣ−１）／新しい２j）＋１）＊(新しい２j)＋
ceil（加算が必要なCredit値／Ｑｉ）＊（新しい２j））  mod  q  …（１）
【００３８】
quantum値が増やされ、新しい２jの値が古い２jの値より大きい場合、古いstride値（古い２jの値）でアクセスされていた全てのActiveList［］の要素が１度はアクセスされるまでの間は、古いstride値のままとして上記の様に特別な処理が必要となる。上記式（１）の最初の部分は、インデックス値が新しい２jの倍数となる様に、新しい２jの値で丸めた場合の現在のインデックス値を求めている。この様にすることで、各フローに対して同一長さの異なるスケジューリングインターバルでのCredit  Counterの増加量をほぼ同じにすることができる。
【００３９】
図３−１〜３−５に、本実施の形態のスケジューリング処理を実行するためのアルゴリズムの一例を示す図である。図３−１〜３−５は一例であり、本実施の形態のスケジューリング処理を実行するためのアルゴリズムは、上述のスケジューリング処理を実行できるアルゴリズムであれば図３−１〜３−５の例に限定されない。
【００４０】
図３−１〜３−５におけるSystemInit（）初期化の処理であり、パケット送信処理の開始時に実行される。maxExponentは、上述のＮ（ｊの最大値）に対応し、curExponentは、上述のｊに対応し、minQuantumは上述のminQsysに対応し、macPacketSizeは上述のＬに対応する。FlowInit（）は、新たなフローが生じた場合に実行される。
【００４１】
ChangeQuantum（）は、quantum値を変更指示があった際に実行される。newStrideは、新しい２jに対応する。NeedToStartAdjustは、quantum値が大きくなる変更があった際の上述の特別な処理を実施するか否かを示す変数であり、NeedToStartAdjustは初期値は０であり、NeedToStartAdjustが１の場合（newStrideがCurStrideより大きい場合に１に設定される）、特別な処理を実施することを示す。AdjustInProgressは、quantum値が大きくなる変更があった際の上述の特別な処理を実施中であるか否かを示す変数であり、初期値は０であり、AdjustInProgressが１の場合、特別な処理を実施中であることを示す。
【００４２】
PacketArrival（）は、図２で説明したパケット到着処理に対応する処理であり、従来のＥＣＲＲと同様である。
【００４３】
EBRRScheduler2()は、図２で説明したＥＢＲＲスケジューリング処理に対応する処理であり、従来のＥＢＲＲから拡張した処理に対応する。EBRRScheduler2()のなかで、上述の特別な処理が実施される。NewRound（）は、ＲＣを更新する処理である。
【００４４】
以上のように、本実施の形態では、ＱｉをMinＱｉ＊２jとし、ActiveList［］の要素をチェックする時に使用するインデックスの増分値であるstrideを２jとする。そして、quantum値を小さくする場合はｊの値を小さくし、Ｑｉおよびstrideを新しいｊに対応する値に直ちに更新し、quantum値を大きくする場合はｊの値を大きくし、Ｑｉを新しいｊに対応する値に直ちに更新し、strideについては、すぐには更新せず、quantum値が変更された場合のActiveList［］のインデックス値を記録し、スケジューリング処理でアクセスするActiveList［］のインデックス値が記録したインデックス値となった後にstrideを更新するようにした。このため、スケジューリング処理をＣＰＵ等の制御部によりソフトウェアで実現する際に、制御部が実行する他の処理の負荷状況に合わせて、各フロー間の比率を変えずにquantum値を変更することが可能となる。
【００４５】
また、同一スケジューリングラウンドで、キューが空でかつ送信可能状態（Credit  Counterが正の値）である複数のフローとして受信したパケットについて、パケットサイズが小さいものを先に送信することができる。
【産業上の利用可能性】
【００４６】
以上のように、本発明にかかるパケットスケジューリング方法および通信装置は、ある時点で送信するパケットを決定するパケットスケジューリングを行う通信装置に有用であり、特に、パケットスケジューリングをソフトウェアで実行する通信装置に適している。
【符号の説明】
【００４７】
１  通信装置
２  制御部
３  タイマー部
４  Credit  Counter格納用メモリ
５  Quantum（quantum）値格納用メモリ
６  ActiveList格納用メモリ
７  パケットデータ格納用メモリ
８  処理待ちパケット情報格納用メモリ
９  キュー情報格納用メモリ
１０  パケット入力部
２１  パケット送信要求受付処理部
２２  スケジューリング処理部
２３  パケット送信処理部
【図１】
2013236124.tif 000003
【図２】
2013236124.tif 000004
【図３−１】
2013236124.tif 000005
【図３−２】
2013236124.tif 000006
【図３−３】
2013236124.tif 000007
【図３−４】
2013236124.tif 000008
【図３−５】
2013236124.tif 000009