(57)【要約】【課題】複数のＢＥクラスのフローに関して出力リンク帯域の有効利用と輻輳時におけるフロー間の占有帯域の公平性担保を図ることを可能とする。【解決手段】複数のパケットフローのパケットが到着するトラフィック制御装置であって、複数の時刻に対応する複数のバッファと、前記複数のバッファのうち、現在時刻に対応するバッファに蓄積されたパケットを読み出すセレクタと、到着した各フローのパケットを蓄積すべきバッファを前記複数のバッファの中から決定するスケジューラと、を含み、スケジューラは、前記複数のパケットフローのそれぞれに関して、一定期間中に前記複数のバッファに蓄積されたパケット量が多い程、到着したパケットを蓄積可能なバッファが少なくなる条件下で到着したパケットの蓄積を試行し、蓄積可能なバッファがなければ、当該パケットを廃棄する。【選択図】図１０
2015061126.tif 000002
【特許請求の範囲】
【請求項１】
複数のパケットフローのパケットが到着するトラフィック制御装置であって、
複数の時刻に対応する複数のバッファと、
前記複数のバッファのうち、現在時刻に対応するバッファに蓄積されたパケットを読み出すセレクタと、
到着した各パケットフローのパケットを蓄積すべきバッファを前記複数のバッファの中から決定するスケジューラと、を含み、
前記スケジューラは、前記複数のパケットフローのそれぞれに関して、一定期間中に前記複数のバッファに蓄積されたパケット量が多い程、前記一定期間後にパケットを蓄積可能なバッファが少なくなる条件下で、到着したパケットの蓄積を試行し、蓄積可能なバッファがなければ、当該パケットを廃棄する
トラフィック制御装置。
【請求項２】
前記スケジューラは、記憶装置に記憶された、前記パケット量に応じて決定される、到着したパケットを蓄積可能な、現在時刻に対応するバッファより未来方向のバッファの上限閾値に従って、到着したパケットの蓄積を試行する
請求項１に記載のトラフィック制御装置。
【請求項３】
前記記憶装置は、前記複数のパケットフローのそれぞれに対応する前記パケット量を記憶し、
前記複数のパケットフローのそれぞれに適用すべき前記上限閾値を、前記記憶装置に記憶された各パケットフローの前記パケット量と、予め記憶された、パケット量と上限閾値との対応関係に従って決定し、決定した上限閾値を前記記憶装置に記憶する決定部、
をさらに含む請求項２に記載のトラフィック制御装置。
【請求項４】
前記記憶装置は、前記複数のパケットフローのそれぞれに対応する前記パケット量を記憶し、
前記複数のパケットフローのそれぞれに適用すべき前記上限閾値を、前記記憶装置に記憶された各パケットフローの前記パケット量と、予め記憶された、前記パケット量を入力値として対応する上限閾値を求める関数に従って決定し、決定した上限閾値を前記記憶装置に記憶する決定部、
をさらに含む請求項２に記載のトラフィック制御装置。
【請求項５】
前記記憶装置は、前記複数のパケットフローのそれぞれに対応する前記パケット量と、各パケットフローのパケットを１つのバッファに蓄積可能な許容量とを記憶し、
前記複数のパケットフローのそれぞれに適用すべき前記上限閾値を、前記記憶装置に記憶された各パケットフローの前記パケット量及び前記許容量と、予め記憶された、前記パケット量及び前記許容量と上限閾値との対応関係に従って決定し、決定した上限閾値を前記記憶装置に記憶する決定部、
をさらに含む請求項２に記載のトラフィック制御装置。
【請求項６】
前記記憶装置は、前記複数のパケットフローのそれぞれに対応する前記パケット量と、各パケットフローのパケットを１つのバッファに蓄積可能な許容量とを記憶し、
前記複数のパケットフローのそれぞれに適用すべき前記上限閾値を、前記記憶装置に記憶された各パケットフローの前記パケット量と、予め記憶された、前記パケット量及び前記許容量を入力値として対応する上限閾値を求める関数に従って決定し、決定した上限閾値を前記記憶装置に記憶する決定部、
をさらに含む請求項２に記載のトラフィック制御装置。
【請求項７】
前記記憶装置に記憶される前記パケット量は、前記一定期間毎にリセットされ、前記決定部は、最後にリセットされてから前記一定期間が経過するまでの間に蓄積されたパケット量を用いて前記上限閾値を決定する、
請求項２から６のいずれか１項に記載のトラフィック制御装置。
【請求項８】
前記記憶装置に記憶される前記パケット量は、前記一定期間毎にリセットされ、前記決定部は、前記一定期間毎の前記パケット量の平均値を用いて前記上限閾値を決定する、
請求項２から６のいずれか１項に記載のトラフィック制御装置。
【請求項９】
前記決定部は、前記上限閾値をバッファ単位で決定する
請求項２から８のいずれか１項に記載のトラフィック制御装置。
【請求項１０】
前記決定部は、前記上限閾値を、蓄積可能量単位で決定する
請求項２から８のいずれか１項に記載のトラフィック制御装置。
【請求項１１】
複数のパケットフローのパケットが到着し、複数の時刻に対応する複数のバッファと、前記複数のバッファのうち、現在時刻に対応するバッファに蓄積されたパケットを読み出すセレクタと、到着した各パケットフローのパケットを蓄積すべきバッファを前記複数のバッファの中から決定するスケジューラと、を含むトラフィック制御装置において、
前記スケジューラは、前記複数のパケットフローのそれぞれに関して、一定期間中に前記複数のバッファに蓄積されたパケット量が多い程、前記一定期間後にパケットを蓄積可能なバッファが少なくなる条件下で、到着したパケットの蓄積を試行し、蓄積可能なバッファがなければ、当該パケットを廃棄する
トラフィック制御装置のバッファリング制御方法。
【請求項１２】
複数のパケットフローのパケットが到着するトラフィック制御装置を含むパケット中継装置であって、
前記トラフィック制御装置は、複数の時刻に対応する複数のバッファと、前記複数のバッファのうち、現在時刻に対応するバッファに蓄積されたパケットを読み出すセレクタと、到着した各パケットフローのパケットを蓄積すべきバッファを前記複数のバッファの中から決定するスケジューラと、を含み、
前記スケジューラが、前記複数のパケットフローのそれぞれに関して、一定期間中に前記複数のバッファに蓄積されたパケット量が多い程、前記一定期間後にパケットを蓄積可能なバッファが少なくなる条件下で到着したパケットの蓄積を試行し、蓄積可能なバッファがなければ、当該パケットを廃棄する
ことを特徴とするパケット中継装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、トラフィック制御装置に関する。
【背景技術】
【０００２】
一般に、パケット中継装置は、複数のインタフェースと、インタフェース間を結ぶスイッチと、装置の制御を司る制御装置とを備える。或るインタフェース（入口側のインタフェース）で受信されたパケットは、スイッチにより当該パケットの宛先に対応するインタフェース（出口側のインタフェース）へ転送され、当該出口側のインタフェースから送信される。
【０００３】
インタフェースは、パケットを一時的に蓄積するバッファ（キュー）と、シェーパと、スケジューラを備える。シェーパは、例えば、パケットフロー毎に、バッファから読み出されるパケットの読み出し間隔を調整することによってパケットの送信レートを制御（抑制）する機能を有する。スケジューラは、バッファから読み出されるパケットの順序や読み出し時刻を決定する機能を有する。
【０００４】
バッファに対してシェーパ及びスケジューラが配置される位置によって、シェーパ及びスケジューラは、「出力型」と「入力型」とに大別される。「出力型」では、シェーパ及びスケジューラがバッファの後段に配置される。到着したパケットは、一旦バッファに蓄積され、シェーピング及びスケジューリングアルゴリズムに従って読み出される。
【０００５】
一方、「入力型」では、シェーパ及びスケジューラがバッファの前段に配置される。「入力型」では、到着したパケットについてシェーピング及びスケジューリングアルゴリズムに従ってパケットのバッファからの読み出し時刻が決定された後、読み出し時刻に対応するバッファに蓄積される。パケットの出力は、時間順で並べられたパケット列を読み出し時刻に従って読み出すことによって行われる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−２９９６８６号公報
【特許文献２】特開２００４−３６３９０１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
サービス品質（Quality of Service: QoS）を実現するために、パケット中継装置で中
継されるトラフィックがクラス化される場合がある。クラスの一つとして、ベストエフォート（Best Effort: BE）クラスがある。ＢＥクラスは、非予約型のクラスであり、オー
バーブッキング（過剰収容）が許容されている。ＢＥクラスのフローの送信レートは、リンク帯域のうちの空き帯域の全てを使用するように、上昇させることができる。
【０００８】
このため、或る出力リンクに送出されるＢＥクラスの複数のフローのうち、或る１つのフローのみが発生している場合には、当該フローが出力リンクの帯域全体を占有することができる。これに対し、複数のフローが並列に発生している（輻輳が発生している）場合には、出力リンクの帯域は、複数のフロー間でシェアされる。この結果、各フローの送信レートが抑制される。
【０００９】
本開示は、複数のＢＥクラスのフローに関して、出力リンク帯域の有効利用と輻輳時に
おけるフロー間の占有帯域の公平性担保を図ることのできる技術を提供することを課題とする。
【課題を解決するための手段】
【００１０】
本発明の態様（aspect）の一つは、複数のパケットフローのパケットが到着するトラフィック制御装置であって、
複数の時刻に対応する複数のバッファと、
前記複数のバッファのうち、現在時刻に対応するバッファに蓄積されたパケットを読み出すセレクタと、
到着した各パケットフローのパケットを蓄積すべきバッファを前記複数のバッファの中から決定するスケジューラと、を含み、
前記スケジューラは、前記複数のパケットフローのそれぞれに関して、一定期間中に前記複数のバッファに蓄積されたパケット量が多い程、前記一定期間後にパケットを蓄積可能なバッファが少なくなる条件下で、到着したパケットの蓄積を試行し、蓄積可能なバッファがなければ、当該パケットを廃棄する、トラフィック制御装置である。
【発明の効果】
【００１１】
本発明の態様の一つによれば、複数のＢＥクラスのフローに関して、出力リンク帯域の有効利用と輻輳時におけるフロー間の占有帯域の公平性担保を図ることができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、パケット中継装置の構成例を示す。
【図２】図２は、インタフェースカードのハードウェア構成例を示す。
【図３】図３は、入力型スケジューラ（入力スケジューリング方式）を模式的に示す図である。
【図４】図４は、入力型スケジューラ（入力型スケジューリング方式）の説明図である。
【図５】図５は、入力型スケジューラの他の構成例を示す図である。
【図６】図６は、ベストエフォートの説明図である。
【図７Ａ】図７Ａは、参考例の問題点の説明図であり、シェーピングが行われないケースを示す。
【図７Ｂ】図７Ｂは、参考例の問題点の説明図であり、シェーピングが実行されるケースを示す。
【図８】図８は、実施形態１における入力型スケジューラの考え方の説明図である。
【図９】図９は、実施形態１における入力型スケジューラによる解決方法の説明図である。
【図１０】図１０は、実施形態１に係る入力型スケジューラの構成例を示す。
【図１１】図１１は、フロー情報テーブルのデータ構造例を示す。
【図１２】図１２は、“蓄積バイト量”の平均値が適用される場合における、フロー情報テーブルのデータ構造例を示す。
【図１３】図１３は、ＴＲ上限閾値決定テーブルのデータ構造例を示す。
【図１４】図１４は、ＴＲ上限閾値の導出用関数の例を示す。
【図１５】図１５は、ＴＲ上限閾値決定マトリクステーブルのデータ構造例を示す。
【図１６】図１６は、蓄積バイト量と許容帯域とを用いてＴＲ上限閾値を決定するための関数の例を示す。
【図１７】図１７は、実施形態２に係る入力型スケジューラの構成例を示す。
【図１８】図１８は、実施形態２におけるフロー情報テーブルの記憶内容を示す。
【図１９】図１９は、実施形態２におけるバッファ状態管理部が管理するバッファ状態テーブルの記憶内容を示す。
【図２０】図２０は、実施形態２における蓄積バイト量の算出処理を示すフローチャートである。
【図２１】図２１は、実施形態２におけるＴＲ上限閾値算出の処理例を示すフローチャートである。
【図２２】図２２は、実施形態２における、パケット到着時におけるスケジューラの処理例を示すフローチャートである。
【図２３】図２３は、実施形態２における、パケット到着時におけるスケジューラの処理例を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施形態について説明する。実施形態の構成は例示であり、本発明は実施形態の構成に限定されない。
【００１４】
〔パケット中継装置の構成〕
最初に、以下に説明する実施形態１及び２に適用可能なパケット中継装置の構成例について説明する。図１は、パケット中継装置の構成例を示す。パケット中継装置は、例えば、ルータ（レガシールータ），或いは、レイヤ３スイッチである。図１には、シャーシ型（シェルフ型とも呼ばれる）のパケット中継装置の構成例が示されている。但し、パケット中継装置のタイプは、シャーシ型に限定されない。
【００１５】
また、実施形態１及び２では、レイヤ３のパケット（Ｌ３スイッチ）を例として説明する。但し、実施形態に係るトラフィックの制御方法（スケジューリング及びシェーピング方法）は、ＭＡＣフレームについて複数のバッファ（キュー）を有するレイヤ２スイッチにおいても適用し得る。従って、ＭＡＣフレームは、「パケット」の一例に該当し、レイヤ２スイッチは、「パケット中継装置」の一例に該当する。
【００１６】
図１において、パケット中継装置１０は、内部バスを介して相互に接続された複数のインタフェースカード１１と、１以上（図１では２個を例示）のスイッチカード１２と、制御カード１３とを含む。
【００１７】
インタフェースカード１１は、データ（ユーザデータ，制御データ）の入出力（送受信）を行うインタフェースを有するカード型装置であり、他の装置と接続された物理リンク（例えば、光ファイバ、ケーブル）１５を収容する。図１では、１本の物理リンクが図示されているが、１つのインタフェースカード１１は、複数本の物理リンクを収容することができる。スイッチカード１２は、インタフェースカード１１間におけるデータ転送のためのスイッチングを行うカード型の装置である。
【００１８】
制御カード１３は、Central Processing Unit（ＣＰＵ）１６と、メモリ１７とを含む
カード型の装置である。制御カード１３は、メモリ１７に記憶されたプログラムをＣＰＵ１６が実行することによって、パケット中継装置１０全体の制御を行う。例えば、制御カード１３は、他の装置との制御情報（制御データ）のやりとりや、パケット中継装置１０の状態管理を行う。
【００１９】
パケットは、物理リンク１５を介して入口側のインタフェースカード１１に到着する。インタフェースカード１１に到着したパケットは、スイッチカード１２によって、パケットの宛先に対応する出口側のインタフェースカード１１に転送される。そして、パケットは、出口側のインタフェースカード１１に接続された物理リンク１５へ送出される。
【００２０】
＜インタフェースカードの構成例＞
図２は、インタフェースカード１１のハードウェア構成例を示す。図２には、物理リンクが光ファイバである場合の構成例が示されている。但し、物理リンクは、電気信号を伝
送するケーブル、或いは無線リンクであっても良い。このとき、インタフェースカードは、物理リンクの形態に応じたインタフェース装置又はインタフェース回路を備える。
【００２１】
インタフェースカード１１は、物理リンク１５（光ファイバ）が接続される複数の光モジュール１１１と、ＰＨＹ／ＭＡＣデバイス１１２と、Field Programmable Gate Array
（ＦＰＧＡ）／Application Specific Integrated Circuit（ＡＳＩＣ）１１３と、ＣＰ
Ｕ１１４と、メモリ１１５とを含んでいる。
【００２２】
光モジュール１１１は、信号の光電変換（Ｏ／Ｅ）及び電光変換（Ｅ／Ｏ）を行う。光モジュール１１１には、例えば、Small Form factor Pluggable（ＳＦＰ）モジュールが
適用される。ＰＨＹ／ＭＡＣデバイス１１２は、物理層(レイヤ１)及びMedia Access Control（ＭＡＣ）層の処理を行う半導体デバイス（電子回路チップ）である。
【００２３】
ＦＰＧＡ／ＡＳＩＣ１１３は、ポリシング及びシェーピングのようなトラフィック管理機能が実装される電子デバイス又は半導体デバイス（「トラフィックコントローラ」と称する）の例示である。トラフィック管理機能は、シェーパによるシェーピング機能、すなわち、フロー毎のパケット間隔の調整を行うことによって、出力されるパケットの送信レートを制御する機能を含む。また、トラフィック管理機能は、スケジューラによるスケジューリング機能、すなわち、バッファから読み出されるパケットの順番や時刻を決定する機能を含む。
【００２４】
ＦＰＧＡ／ＡＳＩＣ１１３は、メモリを有し、メモリ上にパケットを一時的に記憶するためのバッファ（キュー）を形成することができる。但し、バッファは、メモリ１１５上に形成することもできる。
【００２５】
トラフィックコントローラを形成する電子デバイス又は半導体の種類は、ＦＰＧＡ及びＡＳＩＣに限定されない。ＦＰＧＡやＡＳＩＣの代わりに、或いは、ＦＰＧＡ及びＡＳＩＣに加えて、ＩＣ，ＬＳＩ，ＦＰＧＡ以外のプログラマブルロジックデバイス（ＰＬＤ）を適用することもできる。以下の説明において、ＦＰＧＡ／ＡＳＩＣ１１３を「トラフィックコントローラ１１３」と表記する。トラフィックコントローラ１１３は、「トラフィック制御装置」の一例であり、後述する入力型スケジューラ２０及び２０Ａとして機能する。
【００２６】
ＣＰＵ１１４は、制御カード１３のＣＰＵ１６からの制御指示に従って、インタフェースカード１１の動作を制御するローカルプロセッサである。メモリ１１５は、ローカルメモリであり、ＣＰＵ１１４によって実行されるプログラム，及びプログラムの実行に際して使用されるデータを記憶する。
【００２７】
インタフェースカード１１は、物理リンク１５からスイッチカード１２へパケットが転送される第１の方向と、スイッチカード１２から物理リンク１５へパケットが転送される第２の方向との双方向にパケットを転送する。
【００２８】
物理リンク１５（光ファイバ）から入力される光信号は、光モジュール１１１によって電気信号に変換され、ＰＨＹ／ＭＡＣデバイス１１２に渡される。ＰＨＹ／ＭＡＣデバイス１１２は、ＰＨＹ及びＭＡＣ処理によってパケットを抽出し、トラフィックコントローラ１１３に渡す。トラフィックコントローラ１１３を経て、パケットは、スイッチカード１２へ転送される。
【００２９】
逆に、スイッチカード１２から受信されるパケットは、トラフィックコントローラ１１３を経てＰＨＹ／ＭＡＣデバイスに入力され、ＭＡＣ及びＰＨＹ処理によって生成された
信号が、光モジュール１１１で光信号に変換され、物理リンク１５（光ファイバ）へ送出される。
【００３０】
上記のように、トラフィックコントローラ１１３内には、第１の方向にパケットが流れる第１の経路と、第２の方向にパケットが流れる第２の経路とが設けられている。シェーパ及びスケジューラ機能は、第１の経路と第２の経路との一方に設けることができる。例えば、シェーパ及びスケジューラ機能は、第２の経路を流れるパケットに対するトラフィック処理（シェーピング及びスケジューリング）を実行するように、トラフィックコントローラ１１３に実装される。
【００３１】
トラフィックコントローラ１１３は、トラフィック処理のためのバッファに対するパケットの読み書きを行う。また、トラフィックコントローラ１１３は、ポリシングやシェーピングのための設定情報が格納されたテーブルを管理する。
【００３２】
テーブルは、トラフィックコントローラ１１３が有するメモリ、又はメモリ１１５に記憶される。さらに、トラフィックコントローラ１１３は、統計情報収集等のソフトウェア処理やユーザ設定インタフェースのために、ＣＰＵ１１４とのインタフェースを有する。
【００３３】
〔参考例〕
以下に説明する各実施形態では、上記したインタフェースカード１１が、「入力型」のシェーパ及びスケジューリング機能（「入力型スケジューラ」と称する）が実装されたトラフィックコントローラ１１３を備える。以下、入力型スケジューラについて説明する。
【００３４】
図３は、入力型スケジューラ（入力型スケジューリング方式）を模式的に示す図である。入力型スケジューラでは、複数のバッファ（キュー）が時刻毎に用意される。各バッファは、時刻バッファと呼ばれる。複数の時刻バッファの前段に、スケジューラ（スケジューラ／シェーパ）が配置される。スケジューラは、パケットフロー毎のシェーパを含む。一方、複数の時刻バッファの後段には、時間経過に従って、複数の時刻バッファの中から１つを選択するセレクタ（キューセレクタ）が配置される。
【００３５】
パケットがスケジューラ／シェーパに到着すると、スケジューラ／シェーパは、シェーピング及びスケジューリング機能によって、パケットの読み出し時刻を決定する。パケットは、決定された読み出し時刻に対応する時刻バッファに格納される。このようにして、スケジューラ／シェーパに到着する複数のフローのパケットがシェーピング及びスケジューリング結果に従って時刻バッファに振り分けられる。
【００３６】
セレクタは、時間経過に応じて、選択される時刻バッファを変更する。これによって、選択された時刻バッファの先頭に格納されたパケットが読み出し時刻で読み出され、セレクタを介して出力リンクへ送出される。
【００３７】
入力型スケジューラの構成によると、出力側（セレクタ）は、読み出し時刻に従って並べられたパケット列を読み出し時刻に従って選択する。これによって、高速化において問題となる出力競合を回避することができる。
【００３８】
図４は、入力型スケジューラ（入力型スケジューリング方式）の説明図である。入力型スケジューラは、図３にも示したように、スケジューラ及びフロー毎のシェーパと、複数の時刻バッファと、セレクタとを含む。“時刻バッファ”は、或るバッファ内のパケットの読み出しが予め定められた読み出し時刻に開始され、当該或るバッファ内にあるパケットの読み出しが次のバッファの読み出し開始時刻までに終了する形式を有する。
【００３９】
よって、各時刻バッファの容量は、次の時刻バッファの読み出し開始時刻までに読み出しが完了するサイズに設定される。例えば、図４において、“５秒”の時刻バッファに格納されたパケットは、５．０秒から６．０秒（次の読み出し開始時刻）の間に読み出される。
【００４０】
換言すれば、現在時刻が０時０分５秒になった瞬間にセレクタが“５秒”の時刻バッファを選択し、当該時刻バッファ内に記憶されたパケットを先頭から順に読み出す。図４に示す例では、１秒間に９個の固定長パケットを時刻バッファから出力可能となっている。従って、各時刻バッファの容量（サイズ）はパケット９個分に設定されている。
【００４１】
セレクタは、現在時刻が０時０分６秒になれば、次の時刻バッファ“６秒”への切り替えを行う。逆に言えば、０時０分５秒から０時０分６秒までの間に、時刻バッファ“５秒”にパケットが存在しなくなっても次の時刻バッファへの切り替えは行われない。
【００４２】
また、時刻バッファ“５秒”用に使用されていたメモリ領域は、時刻バッファ“５秒”に対する読み出しが終了した後に、時刻バッファ“１０秒”として再び利用される。このように、複数の時刻バッファとして使用されるメモリ領域に対し、サイクリックに未来方向の時刻バッファが生成されることによって、現在時刻にかかわらず、常に一定時間先までの複数の時刻バッファが保持される。なお、１つの時刻バッファからの読み出しのために使用可能な時間（図４の例では１秒）は、時間領域(Time Region : ＴＲ)と呼ばれる。
【００４３】
図４に示すような、複数の時刻バッファが存在する環境において、あるユーザのパケットフロー（ｆｌｏｗ１）が１パケット/秒という送信レートでのパケット送出を希望した
場合を仮定する。この場合、図４に示すように、各時刻バッファにｆｌｏｗ１のパケットが１個ずつ配置される。これによって、所望の間隔でパケットを送出することができる。
【００４４】
また、他のユーザのパケットフロー（ｆｌｏｗ２）の要求送信レートが３パケット／秒であれば、１つの時刻バッファにパケットが３個ずつ配置される。また、他のユーザ(ｆ
ｌｏｗ３)の要求送信レートが０．５個／秒であれば、パケットは一つ飛ばしで１個ずつ
時刻パケットに配置される。このようにして、ｆｌｏｗ２及びｆｌｏｗ３の要求を満たすことができる。
【００４５】
このように、時刻バッファ形式（時刻バッファ方式）では、１つのバッファに蓄積（バッファリング）されるパケットの量やパケットの配置間隔を調整することによって、レート制御（シェーピング）を実行できるという特徴がある。
【００４６】
シェーピング及びスケジューリングを適切に行うために、スケジューラは、到着したパケットを一時記憶する時刻バッファを決定する。スケジューラは、フロー毎のシェーパを含み、シェーパは、１つの時刻バッファに配置可能なパケット数を決定する。例えば、図４において、ｆｌｏｗ１の次のパケットが到着した場合、ｆｌｏｗ１の要求送信レートは１個／秒であることから、当該パケットは、時刻バッファ“９秒”に配置することが決定される。
【００４７】
図５は、入力型スケジューラの他の構成例を示す図である。図５に示す例では、入力型スケジューラは、スケジューラ（フローシェーパ含む）に加えて、フロー情報テーブルと、バッファ状態管理部とを含む。また、入力型スケジューラは、複数の時刻にそれぞれ対応する複数の時刻バッファを含む。図５に示す例では、ＴＲ１〜ＴＲｎ（ｎは自然数）に対応する複数の時刻バッファが図示されている。
【００４８】
図５に示す例では、シェーピング粒度向上と可変長パケット対応のため、１つの時刻バ
ッファ(ＴＲｘ)に配置可能な量がバイト（ｂｙｔｅ）量となっている。フロー情報テーブルは、フロー毎に、１つの時刻バッファに配置可能なバイト数(ｂｙｔｅ／ＴＲ，以下、
「許容帯域」と称することもある)，次にパケットを配置すべき時刻バッファの識別子(次時刻バッファ（次ＴＲ）)，次の時刻バッファに配置可能なバイト量(残バイト)を含む情
報（「フロー情報」と称する）を記憶する。バッファ状態管理部は、バッファの空き状況を管理している。
【００４９】
パケットが到着すると、スケジューラは、当該パケットから、少なくともフローＩＤ及びパケット長を含む情報を抽出する。スケジューラは、フローＩＤに対応するフロー情報をフロー情報テーブルから得る。続いて、スケジューラは、次の時刻バッファの識別子（例えば、時刻バッファの番号）とパケット長を元に、バッファ状態管理部に、各時刻バッファの空き状況を問い合わせる。
【００５０】
そして、スケジューラは、バッファ状態管理部から得た空き状況を考慮してパケットを配置する時刻バッファを決定し、当該時刻バッファへの格納（キューイング）を行う。これにより、パケットは、当該時刻バッファに格納されたパケット列の最後尾に配置される。スケジューラは、バッファリング（キューイング）を行ったパケットに係るフロー情報（次ＴＲ，残バイト）の更新を行う（フロー情報を書き換える）。
【００５１】
可変長のパケットが取り扱われる場合、時刻バッファ（ＴＲｘ）に収容（キューイング）可能なデータ量は、キュー上限閾値（Ｑ上限閾値）として、バイト（byte）数で管理される。
【００５２】
基本的に、パケットの収容量がキュー上限閾値を超えた時刻バッファに対するキューイングは実施できない。しかし、可変長パケットを１つの時刻バッファに対するキューイングを実施した結果、収容量がキュー上限閾値を超えてしまうことが起こり得る。図５には、例として、１番目の時刻バッファ（時刻バッファＴＲ１）の収容量がキュー上限値を超えた状態が図示されている。
【００５３】
この場合、次の時刻バッファである時刻バッファＴＲ２のキュー上限閾値が、時刻バッファＴＲ１の収容量がキュー上限閾値を超えた分（収容量とキュー上限閾値との差分）だけ低減される。このように、“ＴＲ１＋ＴＲ２”のような、複数の時間領域（ＴＲ）から形成される時間枠で、送出量の平均値がキュー上限閾値となるように、時間枠におけるパケットの総送出量が調整される。
【００５４】
セレクタは、原則として、時間を計時する時計から供給される現在時刻に基づく時刻バッファの切り替え（選択）を行う。但し、上記したように、１つの時刻バッファにキュー上限閾値を超えるパケットが蓄積された場合には、当該パケットの読み出しを予め決められた時間領域（ＴＲ）内で完了し得ない。このため、セレクタは、時刻バッファについて読み出しを開始した場合には、当該時刻バッファが空になるまで切り替えを猶予する。
【００５５】
パケット中継装置は、ＱｏＳを実現するため、ベストエフォート（ＢＥ）クラスを扱うことがある。図６は、ベストエフォートの説明図である。図６には、説明のため、「出力型」のスケジューラが図示されている。図６では、３つのＢＥクラスのパケットフロー（Ｆｌｏｗ＃１，Ｆｌｏｗ＃２，Ｆｌｏｗ＃３）に対応する３つのバッファが設けられ、これらの３つのフローのパケットが出力リンク（帯域１００Ｍ／ｂｐｓ）へ送出されるケースが仮定されている。３つのバッファからの読み出しを行うセレクタは、例えば、Deficit Round Robin（ＤＲＲ）と呼ばれるアルゴリズムに従って、バイト単位で公平な読み出
しのラウンドロビン（ＲＲ）を実施する。
【００５６】
セレクタ（ＤＲＲ）は、出力リンクの帯域上限値（１００Ｍｂｐｓ）に従って、各バッファから読み出し可能なレートを１００Ｍｂｙｔｅで行う。図６の左上には、３つのフローのうち、Ｆｌｏｗ＃１のパケット（１５０Ｍ）のみが到着した場合の例が示されている。この場合、Ｆｌｏｗ＃２及びＦｌｏｗ＃３のそれぞれの収容量は０であるので、Ｆｌｏｗ＃１のパケットがリンク帯域上限値（１００Ｍｂｐｓ）に等しいレートで送信される。この結果、Ｆｌｏｗ＃１が出力リンクを専有する状態となる。
【００５７】
図６の右上には、Ｆｌｏｗ＃２のパケット（１３０Ｍ）のみが到着した場合の例が示されている。この場合、Ｆｌｏｗ＃２のパケットがリンク帯域上限値（１００Ｍｂｐｓ）に等しいレートで送信され、Ｆｌｏｗ＃２が出力リンクを専有する状態となる。このように、出力リンクが空（未使用）の場合には、１つだけ発生したフローが出力リンクの帯域を専有することができる。
【００５８】
図６の下側には、Ｆｌｏｗ＃１，Ｆｌｏｗ＃２及びＦｌｏｗ＃３のフローがそれぞれ発生し、輻輳が生じた状態を示す。この場合、セレクタは、ＤＲＲアルゴリズムに従って、各フローが出力リンクを占有する帯域が公平（均等）となるように、各バッファからの読み出し（帯域割り当て）を行う。これによって、出力リンクにおける各フローの帯域は、均等（例：３３Ｍｂｐｓ）となる。
【００５９】
上記したように、出力型スケジューラでは、（１）リンク帯域の有効利用と、（２）輻輳時におけるフロー間の帯域占有の公平性担保とを容易に実現可能である。しかし、出力型スケジューラの欠点（出力競合）回避のために、入力型スケジューラの構成が採用される場合には、上記（１）及び（２）の両立が困難であった。
【００６０】
理由を、図７Ａ及び図７Ｂを用いて説明する。図７Ａ及び図７Ｂに示す例では、図６と同様に、３つのパケットフロー（Ｆｌｏｗ＃１，Ｆｌｏｗ＃２及びＦｌｏｗ＃３）が存在し、いずれものフローも、出力リンクが空いている場合には、出力リンクの帯域全てを使い切る（専有する）ことが希望されている。
【００６１】
図７Ａは、スケジューラ（フローシェーパ含む）においてシェーピングが行われないケースを示し、図７Ｂは、スケジューラ（フローシェーパ含む）においてシェーピングが実行されるケースを示す。
【００６２】
図５を用いて説明したように、入力型スケジューラでは、パケットが到着するスケジューラ（フローシェーパ含む）において、各フローの送信レートが調整される。しかし、図７Ａに示すように、シェーピングが行われない場合には、スケジューラに到着するパケットは、バッファあふれが生じるまで無秩序にバッファリングされる。このため、出力帯域は入力レート比となる。すなわち、いわゆる「入力したもの勝ち」の状態となる。従って、シェーピングが実行されないケースでは、上記（２）の公平性を実現できない。
【００６３】
一方、図７Ｂでは、出力リンクのリンク帯域（１００Ｍｂｐｓ）がフロー間で緊張にシェアされるように、各フローの送信レートがリンク帯域の３分の１（３３Ｍｂｐｓ）になるように、シェーピングが実行された様子が示されている。
【００６４】
しかしながら、上記したシェーピングが実行されると、例えば、Ｆｌｏｗ１のパケットのみが到着し、Ｆｌｏｗ２及びＦｌｏｗ３のパケットが到着しない場合、すなわち、Ｆｌｏｗ１がリンク帯域全体を占有可能な状態であっても、Ｆｌｏｗ１の送信レートはシェーピングによって３３Ｍｂｐｓに抑制される。従って、残りのリンク帯域が空き状態であるにも拘わらず、使用されない。このように、シェーピングが実行されると、上記した（１）のリンク帯域の有効利用を図ることができない。
【００６５】
以下に説明する実施形態では、入力型スケジューラにおいて、リンク帯域の有効利用と、フロー間の公平性担保との双方を実現可能なトラフィック制御方法について説明する。
【００６６】
〔実施形態１〕
実施形態１では、図７Ａを用いて説明したような、シェーピングを実施しない構成をベースとしたスケジューリング方式の改良を考える。すなわち、実施形態１では、パケットが到着するスケジューラでシェーピングを実行しない。この場合、図７Ａに示した構成で説明した様に、各フローのパケットが無秩序に（レート調整なく）バッファリングされるという問題がある。
【００６７】
これに対し、実施形態１では、無秩序なバッファリングによって、バッファリングされたデータ量が他のフローのデータ量よりも多くなったフローに関して、将来におけるバッファリングに関してペナルティを科す。これによって、局所的な観点からはフロー間の公平性が担保されていないように見えても、長いスパンにおける観点からは公平性が確保されるように、各フローのパケットのバッファリングを制御する。
【００６８】
図８は、実施形態１の考え方の説明図である。図８には、図４に示した入力型スケジューラと同様の構成を有する入力型スケジューラが図示されている。すなわち、入力型スケジューラには、３つのＢＥクラスのパケットフロー（ｆｌｏｗ１，ｆｌｏｗ２，ｆｌｏｗ３）の固定長パケットが入力される。各フローの固定長パケットは、スケジューリング結果に従って出力リンクへ送出される。
【００６９】
但し、図８に示す例では、スケジューラがシェーピングを行わない。このため、３つのパケットフローのそれぞれに関して、１つの時刻バッファにバッファリング（キューイング）可能なパケット数は、１つの時刻バッファに蓄積可能な固定長パケット数（キュー上限閾値）に等しい９個である。
【００７０】
スケジューラは、フローに関係なく、パケットの到着順で、収容量がキュー上限閾値（９個）になるまで時刻バッファへのバッファリングを行う。図８には、上記したスケジューラの動作の結果、“５秒”の時刻バッファ（時刻バッファＴＲ５）に対し、７個のｆｌｏｗ１のパケットが格納される一方で、ｆｌｏｗ２及びｆｌｏｗ３のパケットが１個ずつ格納されるという、不公平が例示されている。
【００７１】
実施形態１では、時刻バッファＴＲ５の次以降の時刻バッファに該当する“６秒”〜“９秒”の時刻バッファ（時刻バッファＴＲ６〜ＴＲ９）において、時刻バッファＴＲ５で生じた不公平を是正すべく、ｆｌｏｗ１のパケットが、ｆｌｏｗ２及びｆｌｏｗ３のパケットよりもバッファリングされにくくする。
【００７２】
具体的には、各フローに関して、「或る一定期間に時刻バッファに蓄積したパケット数（パケット量（データ量））に応じて、使用可能な未来側の時刻バッファに制限を設ける」という方法を採用する。換言すれば、或るフローに関して一定期間にバッファリングされたパケットの数に応じて、当該フローのパケットをバッファリング可能な現在時刻より未来方向の時刻バッファが決定される。一定期間の長さは適宜設定可能であり、一定期間中にパケットが蓄積されるバッファとして、複数の時刻バッファから１又は２以上の時刻バッファが選択される。
【００７３】
例えば、或るフローに関して、一定期間にバッファリングされたパケット数が２個以下であれば、現在時刻に２を加えた（現在時刻＋２）時刻に該当する時刻バッファまで、当該フローのパケットをバッファリング可能と決定される。バッファリングされたパケット
数が３〜６個であれば、（現在時刻＋１）の時刻に該当する時刻バッファまで、当該フローのパケットをバッファリング可能と決定される。また、パケット数が７個以上であれば、（現在時刻＋０）に該当する時刻バッファまでバッファリング可能であると決定する。
【００７４】
図９は、実施形態１におけるバッファリング制御の説明図である。例えば、一定期間が時刻バッファＴＲ５へのパケットの蓄積時間と等しいと仮定した場合では、図９に示すように、ｆｌｏｗ１のパケットがバッファリング可能な時刻バッファは、時刻バッファＴＲ５までに制限される。このため、時刻バッファＴＲ５に格納されたパケット数がキュー上限閾値（９個）に達した時点でスケジューラに到着しているｆｌｏｗ１のパケット（図９では、“８”〜“１０”のパケット）は、“６秒”以降の時刻バッファにバッファリングされることなく、廃棄される。
【００７５】
ｆｌｏｗ１に対するバッファリングの制限は、バッファリング可能な時刻バッファの上限として決定された時刻バッファ“５秒”のＴＲが満了したとき（現在時刻バッファが時刻バッファ“６秒”となったとき）に解除される。
【００７６】
これに対し、時刻バッファ“５秒”にバッファリングされたｆｌｏｗ２及びｆｌｏｗ３のそれぞれのパケットの個数は１個である。このため、現在時刻＋２，すなわち“７秒”の時刻バッファまで、パケットのバッファリングを行うことができる。なお、図９に示す例では、５つの時刻バッファを生成可能なメモリ領域を用いて、現在時刻より４時刻先の時刻バッファがサイクリックに予め生成される構成が採用されている。
【００７７】
上記したように、ｆｌｏｗ１のパケットは、現在時刻が０時０分６秒となり、“６秒”の時刻バッファが現在時刻バッファになった後に、制限が解除され、再びバッファリング可能となる。このため、時刻バッファ“６秒”にバッファリングされるｆｌｏｗ１のパケットは、時刻バッファ“６秒”のＴＲにてスケジューラに到着したパケットに制限される。この結果、“６秒”の時刻バッファに蓄積されるｆｌｏｗ１のパケット数は、ｆｌｏｗ２やｆｌｏｗ３のパケットより少なくなる可能性が高い。
【００７８】
よって、少なくとも時刻バッファ“６秒”は、ｆｌｏｗ１のパケットよりも多くのｆｌｏｗ２及びｆｌｏｗ３のパケットで占められる。この結果、時刻バッファ“５秒”で生じたｆｌｏｗ１の不公平が是正されることになる。
【００７９】
また、“６秒”の時刻バッファにて、ｆｌｏｗ２又はｆｌｏｗ３のパケット数がｆｌｏｗ１より多くなると、逆に、“６秒”以降の時刻バッファに到着したパケットを蓄積できなくなるペナルティが科せられる。この様に、或る時間において利益を被った（不公平を生じさせた）フローを異なる時間において不利にすることにより、比較的長いスパンで見たときに、各フローの送信レートが公平値近傍に収斂するようなトラフィック制御が行われる。
【００８０】
（態様１）
図１０は、実施形態１に係る入力型スケジューラの構成例を示す。図１０において、入力型スケジューラ２０は、フローシェーパを含むスケジューラ２１と、フロー情報テーブル２２と、バッファ状態管理部２３と、ＴＲ上限閾値決定部２４と、複数の時刻バッファを記憶するメモリ領域２５と、セレクタ２６と、時計２７とを含む。
【００８１】
スケジューラ２１，バッファ状態管理部２３，ＴＲ上限閾値決定部２４，セレクタ２６は、図２に示したトラフィックコントローラ１１３を形成する電子デバイス又は半導体デバイスが有する機能である。メモリ領域２５は、上記したように、トラフィックコントローラ１１３が有するメモリ、或いはメモリ１１５に設けられる。時計２７として、例えば
、インタフェースカード１１に内蔵された時計が用いられる。
【００８２】
入力型スケジューラ２０が第１の方向のパケット経路に配置される場合、スケジューラ２１には、ＰＨＹ／ＭＡＣデバイス１１２から出力されるパケットが到着し、セレクタ２６から出力されるパケットは、スイッチカード１２へ送信される。一方、入力型スケジューラ２０が第２の方向のパケット経路に配置される場合、スケジューラ２１には、スイッチカード１２から送信されたパケットが到着し、セレクタ２６から出力されるパケットは、ＰＨＹ／ＭＡＣデバイス１１２へ送信される。
【００８３】
メモリ領域２５は、複数の時刻（時間領域ＴＲ）に対応する複数の時刻バッファを含む。図１０には、例として、ＴＲ１〜ＴＲｎ（ｎは自然数）に値対応する複数の時刻バッファが図示されている。
【００８４】
但し、メモリ領域２５は、例えば、以下の構成を持つようにしても良い。すなわち、メモリ領域２５には、或る時刻（ＴＲｘ）から所定時間進んだ時刻までの所定数ｘ（ｘは自然数））の時刻バッファが生成され、現在時刻よりも過去の時刻に該当する時刻バッファは、未来の時刻バッファとして再利用される。
【００８５】
例えば、メモリ領域２５には、最初に、所定数の時間領域（例えば、ＴＲ１〜ＴＲ５の５個）に対応する５個の時刻バッファＴＲ１〜ＴＲ５が生成される。現在時刻がＴＲ１からＴＲ２へ進んだとき、過去の時刻バッファに該当する時刻バッファＴＲ１は、現在時刻であるＴＲ２より未来のＴＲ６に対応する時刻バッファＴＲ６として使用される。このように、メモリ領域２５は、現在時刻から所定時間進んだ時刻までの所定数の時刻バッファを保持（記憶）する。
【００８６】
セレクタ２６は、時計２７から得られる現在時刻に該当するＴＲの時刻バッファを選択し、ＴＲに相当する期間、当該時刻バッファからのパケットの読み出しを行う。このため、各時刻バッファは、１ＴＲ分の容量を有する。なお、１ＴＲの長さは、適宜設定可能である。１ＴＲ分の容量は、キュー上限閾値（Ｑ上限閾値）として使用される。セレクタ２６は、基本的に、１ＴＲの期間毎に、時刻バッファの切り替えを、時刻順で行う。
【００８７】
フロー情報テーブル２２は、フロー毎のフロー情報を記憶する。フロー情報は、当該フローに関して１つの時刻バッファに配置（バッファリング）可能なデータ量（バイト数）を示す“許容帯域（Ｂｙｔｅ／ＴＲ）”と、次にパケットを配置すべき時刻バッファの識別子(次ＴＲ)と、次の時刻バッファに配置可能なバイト量(残バイト)とを含む。なお、実施形態１では、時刻バッファはＴＲ番号を用いて識別され、ＴＲ番号は時刻バッファの識別子として使用される。許容帯域はシェーピングレートに相当する。
【００８８】
さらに、フロー情報は、“蓄積バイト（byte）量”と、“ＴＲ上限閾値”とを含む。“蓄積バイト量”は、一定期間が経過するまでの間にバッファリングされたパケット量（データ量）を示す。“ＴＲ上限閾値”は、当該フローが使用可能な時刻バッファの上限に該当する時刻バッファを示す。“ＴＲ上限閾値”によって、フローが使用可能な現在時刻より未来方向の時刻バッファが規定される。
【００８９】
ＴＲ上限閾値決定部２４（以下、「決定部２４」と表記）は、フロー毎のＴＲ上限閾値を決定する。フロー情報テーブルには、決定部２４によって決定された各フローのＴＲ上限閾値が記憶される。
【００９０】
或るフローのパケットが時刻バッファのいずれかに蓄積されたとき、当該パケットのパケット長（バイト数）が、或るフローのフロー情報として記憶されている“蓄積バイト量
”に加算される。決定部２４は、周期的に各フローの“蓄積バイト量”を含むフロー情報を取得する。このとき、決定部２４は、フロー情報テーブル２２の“蓄積バイト量”の値をリセットする（０にする）。決定部２４は、取得したフロー情報を元に、予め決められたルールに従って各フローのＴＲ上限閾値を決定する。決定部２４は、決定した各フローのＴＲ上限閾値をフロー情報テーブル２２に書き込む。
【００９１】
スケジューラ２１は、到着したパケット毎に、以下のような動作を行う。すなわち、スケジューラ２１は、パケットに格納された情報（例えば、ヘッダ情報）に基づき、パケットのフローを識別する。
【００９２】
例えば、パケットがＴＣＰ（ＵＤＰ）／ＩＰパケットであれば、スケジューラ２１は、パケットのＴＣＰ（ＵＤＰ）／ＩＰヘッダに格納された送信元及び宛先ポート番号並びに送信元及び宛先ＩＰアドレスをフローの識別子（フロー識別子）として用い、パケットフローを識別する。また、スケジューラ２１は、パケットのヘッダに格納された情報から、パケット長を得ることができる。
【００９３】
スケジューラ２１は、フロー情報テーブル２２にアクセスし、パケットから得られたフロー識別子に対応するフロー情報を得る。また、スケジューラ２１は、パケット管理部２３から、読み出し中の時刻バッファの識別子（バッファ番号）と、各時刻バッファの空き状況を示す情報を得る。
【００９４】
スケジューラ２１は、フロー情報テーブル２２及びバッファ状態管理部２３から得られた情報に基づいて、スケジューラ２１に到着した（入力された）パケットをバッファリングすべき時刻バッファを決定する。
【００９５】
スケジューラ２１は、一方、フロー情報中の“次ＴＲ”の値がＴＲ上限閾値を超える場合や、ＴＲ上限閾値以下の時刻バッファに空きが無い場合には、スケジューラ２１は、到着パケットを廃棄する。一方、スケジューラ２１は、パケットをバッファリングすべき時刻バッファがあれば、当該パケットを当該時刻バッファに蓄積する。このとき、スケジューラ２１は、当該パケットのパケット長を、フロー情報テーブル２１の“蓄積バイト量”に加算する。
【００９６】
上記した、“態様１”の構成による入力型スケジューラによれば、過剰収容(オーバー
ブッキング)が許容されたＢＥクラスのトラヒックに対し、効率的な収容（リンク帯域の
有効利用）と平均的に公平な帯域割り当ての両立が可能となる。
【００９７】
（態様２）
上記したように、スケジューラ２１は、各フローの“蓄積バイト量”を元に決定部２４が決定したＴＲ上限閾値に従って、パケットを蓄積すべき時刻バッファを決定する。
【００９８】
ＴＲ上限閾値の決定に用いる蓄積バイト量として、常に最新の値を使用することができる。図１１は、フロー情報テーブルのデータ構造例を示す。フロー情報テーブル２２は、フロー毎に用意された複数のエントリからなる。エントリは、これまでに説明した、“許容帯域（Ｂｙｔｅ／ＴＲ）”，“次ＴＲ”，“残バイト（残byte）”を含む。さらに、エントリは、“最新の蓄積バイト（最新蓄積byte）”と、“最新の蓄積バイト”を元に決定されたＴＲ上限閾値とを含む。
【００９９】
“最新蓄積バイト”として、決定部２２によるリセットから現在までにバッファリングされたデータ量が記憶される。態様１で説明したように、スケジューラ２１は、パケットを時刻バッファに蓄積する毎に、蓄積したパケットのパケット長を、“最新の蓄積バイト
”に加算する。このような、“最新蓄積バイト”の値が、決定部２４によるＴＲ上限閾値の参照値として使用される。
【０１００】
“態様２”によれば、“蓄積バイト”として、最後のリセット時点から計測された“最新蓄積バイト”のみがフロー情報テーブル２２に記憶される。このように、過去の一定期間における蓄積バイト量がフロー情報テーブル２２に残存しない構成が採用されることで、フロー情報テーブル２２のメモリ量を削減することができる。また、態様２によれば、リンク帯域の変化に敏感に追従可能なＴＲ上限閾値の算出が可能となる。
【０１０１】
（態様３）
態様２のように、“最新蓄積バイト”量ではなく、蓄積量を平均化した値を用いることも可能である。図１２は、“蓄積バイト量”の平均値が適用される場合における、フロー情報テーブルのデータ構造例を示す。
【０１０２】
フロー情報テーブル２２Ａには、態様２で説明した“最新蓄積バイト（最新蓄積byte）”に加えて、“最新蓄積バイト”を平均化した値である“平均蓄積バイト（平均蓄積byte）”が追加されている。態様３では、“最新の蓄積バイト”の代わりに、“平均蓄積バイト”が、ＴＲ上限閾値を決定するための参照値として使用される。
【０１０３】
“平均蓄積バイト”の算出は、例えば、決定部２４が“最新蓄積バイト”を読み出すときに、“最新蓄積バイト”と“平均蓄積バイト”とを合計して２で割ることで、算出することができる。
【０１０４】
態様３によれば、態様２と同様に、過去の一定期間における蓄積バイト量がフロー情報テーブル２２Ａに残存しない構成が採用されることで、フロー情報テーブル２２Ａの容量削減を図ることができる。また、態様３によれば、“平均蓄積バイト”を元にＴＲ上限閾値が決定される。これによって、瞬時的な帯域変化に追従せず長期的な帯域使用状況を把握することができる。従って、ＴＲ上限閾値の極端な変動を抑制でき、フロー間の公平性を向上させることが可能となる。
【０１０５】
（態様４）
態様１〜態様３に適用可能なＴＲ上限閾値の設定方法として、時刻バッファの境界に閾値を設定する。例えば、「ＴＲ上限閾値＝＋５」のように、ＴＲ上限閾値は、整数で表される。
【０１０６】
例えば、現在時刻バッファが“ＴＲ１０”であり、且つＴＲ上限閾値が“＋５”であると仮定する。この場合、ＴＲ１５の時刻バッファまでは、“許容帯域（ｂｙｔｅ／ＴＲ）”で許容された上限までのバッファリングが可能となる。但し、ＴＲ１６以降の時刻バッファに対するバッファリングが禁止される。
【０１０７】
態様４によれば、時刻バッファ上限閾値の粒度が時刻バッファ（バッファ単位）で規定される。これによって、バッファリングの可不可の線引きが、時刻バッファ間で明確に行われる。また、パケット到着時の廃棄判定も比較的簡易な仕組みとすることが可能になる。
【０１０８】
（態様５）
一方、態様４に変わるＴＲ上限閾値設定方法として、時刻バッファ境界と時刻バッファ内の蓄積byte量に対して閾値を設定する方法がある。例えば、「ＴＲ上限閾値＝＋５．５」のように、ＴＲ上限閾値が小数点以下の値を有することを許容する。すなわち、時刻バッファ上限閾値の粒度が時刻バッファとバッファ内の蓄積可能量により規定される。蓄積
可能量は、当該蓄積可能量を、１ＴＲ分の容量で除した値で表現される。
【０１０９】
「ＴＲ上限閾値＝＋５．５」のとき、現在時刻バッファがＴＲ１０であると仮定する。この場合、ＴＲ１５の時刻バッファまでは、“許容帯域（ｂｙｔｅ／ＴＲ）”で許容された上限までのバッファリングが可能である。一方、ＴＲ１６の時刻バッファには、“許容帯域(ｂｙｔｅ／ＴＲ)×０．５”のバッファリングが可能となる。そして、ＴＲ１７以降の時刻バッファに対するバッファリングが禁止される。
【０１１０】
態様５の構成によれば、時刻バッファの中に閾値が設けられることによって、よりきめの細かなバッファ領域管理が可能となるため、公平性を向上させることが可能となる。
【０１１１】
（態様６）
態様１〜５に適用可能なＴＲ上限閾値の決定方法として、“最新蓄積バイト”や“平均蓄積バイト”のような蓄積バイト量を予め設定された条件と照らし合わせ、ＴＲ上限閾値を導くという方法がある。
【０１１２】
図１３は、ＴＲ上限閾値決定テーブル２４Ａ（テーブル２４Ａ）のデータ構造例を示す。テーブル２４Ａは、例えばメモリ１１５に記憶され、決定部２４によって管理される。テーブル２４Ａは、蓄積バイト量の範囲に対応するＴＲ上限閾値を記憶する。
【０１１３】
決定部２４は、ＴＲ上限閾値の決定イベントにおいて、テーブル２４Ａを参照する。このとき、蓄積バイト量が１０００バイト未満であれば、決定部２４は、ＴＲ上限閾値として“＋１０”を決定する。蓄積バイト量が１０００バイト以上５０００バイト未満であれば、決定部２４は、ＴＲ上限閾値として“＋５”を決定する。蓄積バイト量が５０００バイト以上であれば、決定部２４は、ＴＲ上限閾値として“＋２”を決定する。
【０１１４】
態様６では、蓄積バイト量とＴＲ上限閾値との対応関係が予め記憶され、決定部２４が対応関係の参照によってＴＲ上限閾値を決定する。このように、構成が簡易であるので、トラフィックコントローラ１１３の回路規模を小さくすることができる。
【０１１５】
（態様７）
態様６に変わるＴＲ上限閾値の決定方法として、蓄積バイト量を入力値とした関数を用いてＴＲ上限閾値を導く方法を適用可能である。図１４は、ＴＲ上限閾値の導出用関数の例を示す。例えば、図１４に示すような、[TR上限閾値= Max(3, 10 - (蓄積byte量)/1000)]の関数を用いて、決定部２４がＴＲ上限閾値を決定することができる。
【０１１６】
態様７によれば、関数を用いてＴＲ上限閾値が決定されることで、態様６に比べてきめの細かなTR上限閾値を算出できる。このため、公平性を向上させることが可能となる。
【０１１７】
（態様８）
態様６及び態様７に代わるＴＲ上限閾値の決定方法として、フロー毎の許容帯域（ｂｙｔｅ／ＴＲ）を加味する方法がある。図１５は、テーブル２４の代わりに決定部２４が管理するＴＲ上限閾値決定マトリクステーブル２４Ｂ（テーブル２４Ｂ）のデータ構造例を示す。テーブル２４Ｂは、例えばメモリ１１５に記憶される。
【０１１８】
図１５に示すように、テーブル２４Ｂは、蓄積バイト量の範囲と許容帯域の範囲との対応関係（２次元情報）でＴＲ上限閾値を決定するマトリクスを記憶している。決定部２４は、フロー情報から得られる蓄積バイト量及び許容帯域に対応するＴＲ上限閾値をテーブル２４Ｂから読み出し、読み出したＴＲ上限閾値を該当フローに適用するＴＲ上限閾値として決定することができる。
【０１１９】
図１６は、蓄積バイト量と許容帯域とを用いてＴＲ上限閾値を決定するための関数の例を示す。この場合、図１６に示すような、[TR上限閾値= Max(3, 10 - (蓄積byte量)*7/(byte/TR))]といった関数に従って、決定部２４はＴＲ上限閾値を決定する。
【０１２０】
態様８の構成によれば、同一のフローにおいて、許容帯域(ｂｙｔｅ／ＴＲ)を加味した上での公平性を実現することが可能となる。
【０１２１】
〔実施形態２〕
次に、実施形態２について説明する。実施形態２は、実施形態１と共通点を有するので、共通点については説明を省略し、主として相違点について説明する。実施形態２は、実施形態１で説明した態様１，態様３，態様５，態様７及び態様８を用いた具体的な形態である。
【０１２２】
図１７は、実施形態２に係る入力型スケジューラの構成を示す。図１７の入力型スケジューラ２０Ａの構成自体は、実施形態１における入力型スケジューラ２０（図１０）とほぼ同じであるため、説明を省略する。但し、以下の点で、実施形態１の入力型スケジューラ２０と異なっている。
【０１２３】
実施形態２での出力リンク帯域は、１００Ｍｂｐｓである。また、時刻バッファの個数は５０個である。また、セレクタは、基本的に１ｍｓで時刻バッファの切り替えを行う。よって、各時刻バッファの容量は、１２５００バイト(100Mbit / 1ms = 100kbit = 12500byte)である。また、図１７において、現在時刻バッファは時刻バッファＴＲ２であると
仮定する。
【０１２４】
図１８は、実施形態２におけるフロー情報テーブル２２の記憶内容を示す。図１９は、実施形態２におけるバッファ状態管理部２３が管理するバッファ状態テーブルの記憶内容を示す。スケジューラ２１を通過するＢＥクラスのパケットフローとして、図１９に示す例では、ｍ個のパケットフローがあると仮定する。
【０１２５】
なお、実施形態２におけるフロー情報テーブル２２及びバッファ状態管理テーブルのデータ構造自体は、実施形態１で説明したフロー情報テーブル２２及びバッファ状態管理テーブルと同じである。
【０１２６】
実施形態２では、実施形態１で説明した態様３が適用される。このため、蓄積バイト量として、平均的な値が算出される。図２０は、実施形態２における蓄積バイト量の算出処理を示すフローチャートである。スケジューラ２１は、図２０に示す平均値の計算を周期的に行う。スケジューラ２１は、１回の平均値の計算イベントにおいて、全ての（ｍ個）のフローの平均値を算出する。
【０１２７】
すなわち、スケジューラ２１は、アイドル（Idle）状態（０７）において、例えば、タイマの満了に伴う平均蓄積バイト量の計算イベントが発生すると、フローを示す引数ｉの値を、１番目のフロー（フロー＃１）を示す“１”に設定する（０１）。
【０１２８】
次に、スケジューラ２１は、フロー情報テーブル２２からフローｉの最新蓄積バイトと平均蓄積バイト(“以前の平均値”として利用)を取得する（０２）。次に、スケジューラ２１は、最新蓄積バイトと平均蓄積バイトとを用いて新たな平均値を算出する（０３）。適用可能な平均値の導出方法として、様々な方法が存在するが、例えば、図２０の０３にて示す移動平均法による平均値導出方法を適用することができる。
【０１２９】
フロー＃１の場合、最新蓄積バイトは３９００であり、平均蓄積バイトは２８５２である。このため、移動平均法による計算（(1/8)*3900+(7/8)*2852）によって、２９８３と
いう値が新たな平均値として導き出される。
【０１３０】
新たな平均値を算出すると、スケジューラ２１は、新たな平均値をフローｉの平均蓄積バイトに上書きし、最新蓄積バイトはリセットする（０にする）（０４）。その後、スケジューラ２１は、引数ｉの値がフロー数ｍに達しているか否かを判定する（０５）。ｉの値がｍに達していなければ（０５，Ｙ）、スケジューラ２１は、ｉの値をインクリメントし（０６）、処理を０２に戻す。このようにして、残りのフロー＃２からフロー＃ｍまでの平均値計算を行う。そして、ｉの値がｍに達し（０５，Ｎ）、全フローに対する処理が完了すると、アイドル状態に戻る（０７）。
【０１３１】
図２１は、実施形態２におけるＴＲ上限閾値算出の処理例を示すフローチャートである。ＴＲ上限閾値算出も周期的に実行され、一度の算出イベントにおいて、全てのフロー（ｍ個）の平均計算が行われる。
【０１３２】
ＴＲ上限閾値更新イベントが発生すると、決定部２４は、引数ｉを１に設定し（１１）、フロー＃１から処理を開始する。決定部２４は、フロー情報テーブル２２からフローｉの平均蓄積バイトを取得する（１２）。
【０１３３】
続いて、決定部２４は、平均蓄積バイトを計算式に代入する事により、ＴＲ上限閾値を導く（１３）。実施形態２では、図１６に示した関数が用いられる。例えば、フロー＃１のＴＲ上限閾値は、ＴＲ上限閾値＝ Max(3, 10 - (2852*7/2500))＝３となる。現在時刻
バッファが時刻バッファＴＲ２であるとき、フロー＃１については、時刻バッファＴＲ５まで、ｂｙｔｅ／ＴＲ分のパケットをバッファリング可能となる。
【０１３４】
次に、決定部２４は、フロー情報テーブル２２にフローｉのＴＲ上限閾値を上書きする（１４）。その後、決定部２４は、引数ｉの値がフロー数ｍに達しているか否かを判定する（１５）。ｉの値がｍに達していなければ（１５，Ｙ）、スケジューラ２１は、ｉの値をインクリメントし（１６）、処理を１２に戻す。このようにして、残りのフロー＃２からフロー＃ｍまでの平均値計算を行う。そして、ｉの値がｍに達し（１５，Ｎ）、全フローに対する処理が完了すると、アイドル状態に戻る（１７）。
【０１３５】
上記処理において、フロー＃２に関しては、ＴＲ上限閾値 ＝ Max(3, 10 - (2908*7/7500)) ≒ ７．３となる。現在時刻バッファが時刻バッファＴＲ２であるとき、時刻バッファＴＲ９までは無条件にｂｙｔｅ／ＴＲ分(７５００[byte])を蓄積することができる。さらに、時刻バッファには、７０００[byte]＊０．３＝２２５０[byte]を蓄積することができる。
【０１３６】
図１６の関数（態様８）が適用される場合では、byte/TR比となることが公平と位置付
けられる。このため、上記したフロー＃１及びフロー＃２の例のように、平均蓄積バイトが多いフロー＃２が優遇されるケースも起こりうる。
【０１３７】
＜パケット到着時の処理＞
図２２及び図２３は、実施形態２における、パケット到着時におけるスケジューラ２１の処理例を示すフローチャートである。最初の１０１では、スケジューラ２１は、到着したパケットから当該パケットのフロー番号（フロー識別子：ＦＩＤ）及びパケット長（ＰＬＥＮ）を得る。
【０１３８】
１０２において、スケジューラ２１は、フロー情報テーブルにアクセスし、ＦＩＤに対
応するフロー情報を得る。フロー情報は、次ＴＲを示す値“ＴＲｘ”と、ＴＲ上限閾値を示す値“Ｎ”と、時刻バッファ容量“ｂｙｔｅ／ＴＲ”を示す値“Ｂ１”と、残バイトを示す値“Ｂ２”とを含む。
【０１３９】
また、スケジューラ２１は、１０３において、バッファ状態管理部からバッファ情報を得る。バッファ情報は、現在読み出し中の時刻バッファ（現在時刻バッファ）の識別子（時刻バッファ番号）を示す値“ＴＲｙ”と、各時刻バッファの空き状態を示す情報を含む。各時刻バッファの空き状態を示す情報は、少なくとも、時刻バッファに蓄積されたデータ量がキュー上限閾値に達しているか否かを示す。
【０１４０】
次に、スケジューラ２１は、パケットを格納すべき事項バッファを決定するため、“ＴＲｘ”の値が有効か否かを判定する（１０４）。ここで、当該バッファのフローの過去の到着パケットに関して“ＴＲｘ”が指定されていた場合には、当該“ＴＲｘ”の値は有効である。これに対し、当該パケットが最初のパケットに該当する場合（過去の到着パケットがない場合）、及び“ＴＲｘ”の値が現バッファの時刻より過去の時刻を指す場合には、“ＴＲｘ”の値は無効である。
【０１４１】
ＴＲｘの値が有効であるときには（１０４，Ｙ）、スケジューラ２１は、ＴＲｘの値で特定される時刻バッファをバッファリング候補に決定する（１０５）。これに対し、ＴＲｘの値が無効であるときには（１０４，Ｎ）、スケジューラ２１は、“ＴＲｙ”の値で特定される現在時刻バッファをバッファリング候補に決定する（１０６）。
【０１４２】
次に、スケジューラ２１は、パケットをバッファリング候補の時刻バッファにバッファリング可能か否かを調べる。すなわち、スケジューラ２１は、ＴＲｚの時刻バッファに空きがあるか否かを、各バッファの空き状況を示す情報を用いて判定する（１０７）。
【０１４３】
ＴＲｚの時刻バッファに空きがないときには（１０７，Ｎ）、ＴＲｚの値をインクリメントし（１０８）、次の時刻バッファ（ＴＲｚ＋１）の空き状態を調べる（１０７）。１０７及び１０８のループは、空き状態の時刻バッファが見つかるまで繰り返される。空き状態の時刻バッファが見つかったとき、スケジューラ２１は、当該時刻バッファを新たなバッファリング候補（ＴＲｚ）として決定する。
【０１４４】
ＴＲｚの時刻バッファに空きがあるときには（１０７，Ｙ）、１０９へ処理が進む。１０９では、スケジューラ２１は、バッファリング候補ＴＲｚと現在時刻バッファＴＲｙとの差が、当該フローのＴＲ上限閾値Ｎ内に収まっているか否かを判定する（ＴＲｚ−ＴＲｙ＞Ｎ＋１）。
【０１４５】
すなわち、（ＴＲｚ−ＴＲｙ）の値が（Ｎ＋１）の値より大きいとき（１０９，Ｙ）、スケジューラ２１はパケットを廃棄する（１１０）。ＴＲｚで特定される時刻バッファがバッファリング許容外の時刻バッファであるからである。
【０１４６】
これに対し、（ＴＲｚ−ＴＲｙ）の値が、Ｎより大きく（Ｎ＋１）以下である場合（Ｎ＋１ ≧ ＴＲｚ−ＴＲｙ＞Ｎ）（１０９，Ｎ）には、処理が１１１に進む。すなわち、Ｎが小数点以下の値を持ち、且つＴＲｚが当該小数点以下の値の判定対象となる時刻バッファであるときには（１０９，Ｎ）、スケジューラ２１は、さらに残バイト（Ｂ２）を用いた判定を行う（１１０）。
【０１４７】
１１０において、スケジューラ２１は、Ｂ２の値が許容蓄積バイト（Ｂ１＊（ＴＲｚ−ＴＲｙ−Ｎ））より大きい場合（１１１，Ｎ）には、処理を１１３に進め、そうでない場合（１１１，Ｙ）には、パケットを廃棄する（１１２）。また、（ＴＲｚ−ＴＲｙ≦Ｎ）
が満たされる場合にも、処理が１１３に進む。
【０１４８】
１１３では、スケジューラ２１は、パケットをＴＲｚの値で特定される時刻バッファへ格納する。このとき、スケジューラ２１は、バッファ状態管理テーブル（図１９）を更新するため、ＴＲｚの値で特定される時刻バッファのキュー長（データ蓄積量）にパケット長“ＰＬＥＮ”を加算する。
【０１４９】
次に、スケジューラ２１は、加算後のキュー長がキュー上限閾値を超えているか否かを判定する（１１４）。このとき、キュー長がキュー上限閾値を超えていれば（１１４，Ｙ）、スケジューラ２１は、超過したバイト数を次の時刻バッファ以降の空き領域から減算し（１１５）、１１１へ処理を進める。これに対し、キュー長がキュー上限閾値を超えていなければ（１１４，Ｎ）、処理が１１６に進む。
【０１５０】
以上の１１５までの処理が、パケットのバッファリングに係る処理である。当該処理が終了すると、１１６以降の処理でフロー情報テーブルの更新が行われる。
【０１５１】
１１６では、スケジューラ２１は、残バイト“Ｂ２”の値からパケット長“ＰＬＥＮ”を減じた値が０より大きいか否かを判定する。Ｂ２の値は、次の時刻バッファＴＲｘの残りの空きバイト数である。このため、今回到着したパケットのパケット長(ＰＬＥＮ)がＢ２の値より小さければ(Ｂ２−ＰＬＥＮ＞０：１１６，Ｙ)、Ｂ２の値からＰＬＥＮを減じた値が新たなＢ２の値として決定される（１１７）。このとき、ＴＲｘの値は変更されない。
【０１５２】
しかし、パケット長が残バイトより大きい場合(Ｂ２-ＰＬＥＮ≦０：１１６，Ｎ)には
、スケジューラ２１は、ＰＬＥＮの値からＢ２を減算して新たなＰＬＥＮの値を得る（１１８）。さらに、スケジューラ２１は、ＴＲｘをインクリメントする（ＴＲｘの値に１を加える（１１９）。
【０１５３】
次に、スケジューラ２１は、次の時刻バッファに蓄積可能なバイト数を示すＢ１の値からＰＬＥＮの値を減じた値が０より大きい（正の値）か否かを判定する（１２０）。このとき、正の値が得られない場合（１２０，Ｎ）には、スケジューラ２１は、ＰＬＥＮの値からＢ１の値を減じた値を新たなＰＬＥＮの値に決定し（１２１）、さらに、ＴＲｘの値をインクリメントして（１１９）、処理を１２０に戻す。スケジューラ２１は、（Ｂ１−ＰＬＥＮ）の値が正になるまで、１２１及び１９１のループを繰り返す。
【０１５４】
（Ｂ１−ＰＬＥＮ）の値が正になると、スケジューラ２１は、そのときの（Ｂ１−ＰＬＥＮ）の値を新たなＢ２の値として決定する（１２２）。そして、スケジューラ２１は、ＴＲｘの値とＢ２の値をフロー情報テーブルに書き戻す。これによって、到着パケットのフローに係るフロー情報が更新される。
【０１５５】
実施形態２の作用効果に関しては、実施形態１で説明した対応する態様によって得られる効果と同様の効果を得ることができる。なお、実施形態１及び実施形態２で説明した構成は、適宜組み合わせることが可能である。
【符号の説明】
【０１５６】
１０・・・パケット中継装置
１１・・・インタフェースカード
１２・・・スイッチカード
１３・・・制御カード
１５・・・物理リンク
１１１・・・光モジュール
１１２・・・ＰＨＹ／ＭＡＣデバイス
１１３・・・トラフィックコントローラ
１１４・・・ＣＰＵ
１１５・・・メモリ
２０，２０Ａ・・・入力型スケジューラ
２１・・・スケジューラ（フローシェーパ含む）
２２・・・フロー情報テーブル
２３・・・バッファ状態管理部
２４・・・ＴＲ上限閾値決定部
２６・・・セレクタ
【図１】
2015061126.tif 000003
【図２】
2015061126.tif 000004
【図３】
2015061126.tif 000005
【図４】
2015061126.tif 000006
【図５】
2015061126.tif 000007
【図６】
2015061126.tif 000008
【図７Ａ】
2015061126.tif 000009
【図７Ｂ】
2015061126.tif 000010
【図８】
2015061126.tif 000011
【図９】
2015061126.tif 000012
【図１０】
2015061126.tif 000013
【図１１】
2015061126.tif 000014
【図１２】
2015061126.tif 000015
【図１３】
2015061126.tif 000016
【図１４】
2015061126.tif 000017
【図１５】
2015061126.tif 000018
【図１６】
2015061126.tif 000019
【図１７】
2015061126.tif 000020
【図１８】
2015061126.tif 000021
【図１９】
2015061126.tif 000022
【図２０】
2015061126.tif 000023
【図２１】
2015061126.tif 000024
【図２２】
2015061126.tif 000025
【図２３】
2015061126.tif 000026