JP6569374B2 - スイッチ装置及びスイッチ装置の制御方法 - Google Patents

Description

本発明は、スイッチ装置及びスイッチ装置の制御方法に関する。

近年、コストの削減やシステムの柔軟性の向上などを目的として、クラウドコンピューティングが広く普及してきている。その、クラウドコンピューティングプラットフォームを構築するための技術として、ＩａａＳ（Infrastructure as a Service）が提案されている。ＩａａＳは、ネットワーク環境などの外部化情報システムの稼動に必要な仮想サーバをはじめとした機材やネットワークなどのインフラを、インターネット上のサービスとして提供する技術である。

ＩａａＳでは、インターネット経由で情報インフラを利用者に提供する。また、ＩａａＳでは、ネットワーク資源が複数の利用者で供給される場合が多い。このようなことから、ＩａａＳなどを実現するデータセンタでは、通信品質の向上が求められる。具体的には、高バンド幅や低レイテンシといった高い通信性能、及びフェアな帯域分配や低いジッタ、すなわちレイテンシの揺らぎの抑制といったネットワーク資源のフェアな共有などがＩａａＳでは求められる。

このような要望に応えるため、通信品質の向上に向けて、現在ＶＭ（Virtual Machine：仮想マシン）の配分による制御や、仮想スイッチでの帯域制御が行われている。ただし、計算上ではＶＭを適切に配置したとしても、実際の動作状況によって輻輳などが発生する場合がある。その結果、バッファ資源の枯渇やスイッチング性能の容量限界により、通信性能の低下及びネットワーク資源のアンフェアな共有状態が発生するおそれがある。このような状況に対応するため、例えば帯域に余裕を持たせてＶＭを配備することが考えられるが、資源の利用効率が低下してしまい、コストの増大を招くおそれがある。

そこで、輻輳発生時などに、フェアな状態を実現するためのポリシーに応じてスケジューリングを行うことが望ましい。ここで、フェアとは、どのフローも公平に扱うことを指す。ここで、フローとは、送信元及び送信先のアドレス及びポート番号やプロトコル番号を含む条件によって分類される一連のパケットを指す。

そこで、従来、輻輳を回避するために経路を切り替える技術が提案されている。また、複数の送信キューを用いて、それらのスケジューリングにより帯域を制御する技術が提案されている。

米国特許第８８６７５６０号明細書

しかしながら、フローの途中で経路を切り替えた場合、パケットの到着順序が変化するおそれがある。また、複数の送信キューのスケジューリングにより帯域を制御する技術では、以下のような問題がある。例えば、キューの数が限られているため全てのフローに専用キューを割り当てることが困難である。加えて、スケジューリングやキューの割り当てが固定となり、フローごとの帯域制御を行うことが困難である。また、ＷＲＲ（Weighted Round Robin）方式やＤＲＲ（Deficit Round Robin）方式によるスケジューリングを行った場合、１つのキューから連続してパケットが送信されることが多く、パケットの受信側に負荷を与えやすく、通信性能が低下するおそれがある。

開示の技術は、上記に鑑みてなされたものであって、通信性能を向上させたスイッチ装置及びスイッチ装置の制御方法を提供することを目的とする。

本願の開示するスイッチ装置及びスイッチ装置の制御方法は、一つの態様において、パケットを受信して格納し、格納したパケットをそれぞれ出力する複数のキューを有する。そして、情報取得部は、各前記キューにおけるパケットの送受信情報を取得する。グルーピング部は、前記情報取得部により取得された前記送受信情報を基に、１つまたは複数のフローが属するフローグループを作成し、前記フローグループ毎に前記キューを割り当て、特定のフローグループに属するフロー毎のパケットの送信量と予め決められたバンド幅との差が大きくなった場合、前記特定のフローグループを分割し、分割後のフローグループに前記キューを割り当てる。第１スケジューリング部は、前記情報取得部により取得された前記送受信情報及び予め決められた前記キューの優先度を基に、各前記キューの出力順を決定する。

本願の開示するスイッチ装置及びスイッチ装置の制御方法の一つの態様によれば、通信性能を向上させることができるという効果を奏する。

図１は、実施例１に係るスイッチのブロック図である。 図２は、フロー識別情報の一例の図である。 図３は、フローグループ定義情報の一例の図である。 図４は、ポリシー情報の一例を示す図である。 図５は、スケジューリングパラメータの一例を示す図である。 図６は、フローグループの分割を説明するための図である。 図７は、フローグループの結合を説明するための図である。 図８は、重み計算における重みの変更の規則の一例を表す図である。 図９は、実施例１に係るスイッチにおけるパケット転送処理のフローチャートである。 図１０は、フローグループの再構成の処理のフローチャートである。 図１１は、関数「ＮＥＸＴ」を説明するための図である。 図１２は、実施例２に係るスイッチのフローグループ分割時のパケットの出力を説明するための図である。 図１３は、実施例２に係るスイッチのフローグループ結合時のパケットの出力を説明するための図である。 図１４は、実施例２に係るスケジューラによる送信要求を取得する内部キューの決定のフローチャートである。 図１５は、実施例２に係るスケジューラによるパケットを出力させる内部キューの決定のフローチャートである。

以下に、本願の開示するスイッチ装置及びスイッチ装置の制御方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例により本願の開示するスイッチ装置及びスイッチ装置の制御方法が限定されるものではない。

図１は、実施例１に係るスイッチのブロック図である。スイッチ１は、サーバや他のスイッチなどの外部の情報処理装置からパケットの入力を受け、入力されたパケットを指定されたアドレスに向けて転送する通信装置である。スイッチ１は、管理用サーバ２に接続される。

管理用サーバ２は、スイッチ１に接続された仮想サーバのパケットの送受信を制御する。例えば、管理用サーバ２は、ある仮想サーバから他の仮想サーバへのパケットの送受信をそれぞれの仮想サーバに行わせる。すなわち、管理用サーバ２は、スイッチ１が転送する各パケットの送信先アドレス、送信元アドレス、送信元ポート、送信先ポート及び使用するプロトコルの情報を保持する。また、管理用サーバ２は、後述する内部キュー２３２のそれぞれの優先度を予め有する。例えば、優先度として、０〜７の優先度があり、３が基準の優先度であり、７〜４が、基準の優先度を有する内部キュー２３２よりも優先する優先度であり、２〜０が基準の優先度を有する内部キュー２３２の後に選択される優先度である。

さらに、管理用サーバ２は、各フローに割り当てられた、そのフローが使用できるバンド幅の上限である設定バンド幅を予め有する。また、管理用サーバ２は、各フローの初期のグルーピングの情報を予め有する。また、管理用サーバ２は、後述する各送信キュー２３の１ラウンドでの送出可能量を予め有する。

スイッチ１は、図１に示すように、制御情報送受信部１１、記憶部１２、スケジューラ１３、制御部１４、送信側メータカウンタ１５、キュー選択部１６、受信側メータカウンタ１７及びフロー識別部１８を有する。さらに、スイッチ１は、受信ポート２１、スイッチング部２２、送信キュー２３及び送信ポート２４を有する。

以下では、スイッチ１を介して送受信されるデータの単位をパケットという。パケットには、例えば、本実施例では、送信元ＩＰ（Internet Protocol）アドレス、送信先ＩＰアドレス、送信元ポート番号、送信先ポート番号及びプロトコル番号が付加される。そして、条件によって分類された一連のパケットの集まりをフローという。例えば、送信元ＩＰアドレス、送信先ＩＰアドレス、送信元ポート番号、送信先ポート番号及びプロトコル番号によって分類されたパケットの集まりがフローにあたる。さらに、入力されたパケットを格納し順次出力するパケットの一時格納部のことをキューという。

スイッチ１は、受信ポート２１を複数有する。各受信ポート２１は、それぞれ外部の情報処理装置へ繋がるネットワークに接続される。受信ポート２１は、外部の情報処理装置からパケットの入力を受ける。そして、受信ポート２１は、受信したパケットをスイッチング部２２へ出力する。

スイッチング部２２は、パケットの入力を各受信ポート２１から受ける。ここで、スイッチング部２２が取得したパケットの内の１つのパケットに対するスイッチング部２２の処理について説明する。ただし、以下の処理は、各パケット全てに同様に行われる。

スイッチング部２２は、フロー識別部１８からパケットが属するフローの識別情報であるフローＩＤ（Identifier）の入力を受ける。また、スイッチング部２２は、フロー識別部１８から入力されたフローＩＤに対応するフローグループの情報、すなわちそのパケットを含むフローが属するフローグループの情報をフロー管理情報１２１に含まれるフローグループ定義情報から取得する。以下では、例えば第１パケットというパケットがあったとして、その第１パケットが含まれるフローが属するフローグループのことを、単に「第１パケットのフローグループ」という。

また、スイッチング部２２は、パケットの送信先ＩＰアドレスを取得する。そして、スイッチング部２２は、取得した送信先ＩＰアドレスによって、そのパケットの出力に使用可能な送信ポート２４を抽出する。この他にも、スイッチング部２２は、ＭＡＣアドレスを用いてスイッチを行ってもよい。次に、スイッチング部２２は、抽出した使用可能な送信ポート２４に接続される送信キュー２３を特定する。そして、スイッチング部２２は、特定した送信キュー２３にパケットを出力する。

送信キュー２３は、デマルチプレクサ２３１、内部キュー２３２及びマルチプレクサ２３３を有する。送信キュー２３は、スイッチング部２２から出力されたパケットを後述するスケジューラ１３からの指示にしたがい送信ポート２４へ出力する。以下に、送信キュー２３の詳細を説明する。

内部キュー２３２は、対応付けられたフローグループに属するフローに含まれるパケットを格納し出力するキューである。内部キュー２３２は、格納されたタイミングが早い順にパケットを出力する。

内部キュー２３２は、１つの送信キュー２３の中での上限の数が予め決められる。例えば、送信キュー２３は、内部キュー２３２を４つまで有することができる。そして、送信キュー２３の中で使用される内部キュー２３２は、制御部１４からの制御を受けて決定される。具体的には、後述するように、内部キュー２３２は、制御部１４によって分割及び結合が行われ、使用される本数が変化する。さらに、内部キュー２３２に対するフローグループの対応付けも制御部１４によって行われる。

デマルチプレクサ２３１は、パケットの入力をスイッチング部２２から受ける。さらに、デマルチプレクサ２３１は、受信した各パケットをいずれの内部キュー２３２へ格納するかの指示を後述するキュー選択部１６から受ける。そして、デマルチプレクサ２３１は、指示にしたがい各パケットを内部キュー２３２へ格納する。

マルチプレクサ２３３は、後述するスケジューラ１３からパケットを取得する内部キュー２３２の情報の入力を受ける。そして、マルチプレクサ２３３は、指定された内部キュー２３２からパケットを取得する。そして、マルチプレクサ２３３は、取得したパケットを送信ポート２４へ出力する。

ここで、後述するようにマルチプレクサ２３３は、スケジューラ１３によって各内部キュー２３２の重み及び優先度を用いて決められた取得先とする内部キュー２３２の指定を受ける。これにより、マルチプレクサ２３３は、各フローグループに対して重みや優先度に応じたフェアなパケットの出力を行うことができる。

また、スイッチ１は、送信ポート２４を複数有する。各送信ポート２４は、それぞれ外部の情報処理装置へ繋がるネットワークに接続される。送信ポート２４は、送信キュー２３からパケットの入力を受ける。そして、送信ポート２４は、取得したパケットの送信先ＩＰアドレスを有する情報処理装置へ送信されるようにパケットをネットワークへ出力する。

記憶部１２は、フロー管理情報１２１、フロー情報１２２、フローグループ情報１２３、ポリシー情報１２４及びスケジューリングパラメータ１２５を記憶する。

フロー管理情報１２１は、フロー識別情報２１１及びフローグループ定義情報２１２を含む。図２は、フロー識別情報の一例の図である。また、図３は、フローグループ定義情報の一例の図である。

図２に示すように、フロー識別情報２１１は、パケットの送信元ＩＰアドレス（ＳＩＰ：Source IP Address）、送信先ＩＰアドレス（ＤＩＰ：Destination IP Address）、送信先ポート番号（ＳＰ：Source Port）、送信元ポート番号（ＤＰ：Destination Port）及びプロトコル番号（Ｐｒｏ：Protocol）に応じたフロー毎に、フローＩＤが登録される。フロー識別情報２１１は、後述する制御情報送受信部１１により登録される。

また、図３に示すように、フローグループ定義情報２１２は、フローＩＤに対応するフローグループが登録される。すなわち、フローグループ定義情報２１２は、各フローがどのフローグループに含まれるかという情報を保持する。フローグループ定義情報２１２は、後述する制御部１４が後述する内部キュー２３２の設定バンド幅及び統計情報を用いて決定したグルーピングにしたがって、制御部１４により登録される。

フロー情報１２２は、スイッチ１のパケット転送におけるフロー毎の統計情報である。フロー情報１２２は、受信側のフロー毎の統計情報及び送信側のフロー毎の統計情報を含む。

フロー情報１２２の受信側の統計情報には、スイッチ１に入力された各フローの単位時間当たりの受信量であるフロー受信量が含まれる。フロー情報１２２の受信側の統計情報は、後述する受信側メータカウンタ１７により登録される。

フロー情報１２２の送信側の統計情報には、フロー送信量、フローキュー長及びフロー廃棄数が含まれる。フロー送信量は、フロー毎の単位時間あたりの送信量である。フローキュー長は、各内部キュー２３２に格納されたフロー毎のパケットサイズの合計である。フロー廃棄数は、内部キュー２３２に格納されずに破棄されたフロー毎のパケットの数である。フロー情報１２２の送信側の統計情報は、後述する、送信側メータカウンタ１５により登録される。

フローグループ情報１２３は、スイッチ１のパケット送信におけるフローグループ毎の送信側の統計情報である。ここで、受信時にはフローはフローグループ毎に分類されていないので、フローグループ毎の受信側の統計情報は存在しない。

フローグループ情報１２３は、フローグループ送信量、フローグループキュー長及びフローグループ廃棄数を含む。フローグループ送信量は、フローグループ毎の単位時間あたりの送信量である。フローグループキュー長は、各内部キュー２３２に格納されたフローグループ毎のパケットサイズの合計である。フローグループ廃棄数は、フローグループ毎の内部キュー２３２に格納されずに破棄されたパケットの数である。フローグループ情報１２３は、後述する送信側メータカウンタ１５により登録される。

ポリシー情報１２４は、図４に示すように、各フローＩＤに対応させて制約情報である設定バンド幅が登録される。図４は、ポリシー情報の一例を示す図である。設定バンド幅は、各フローに割り当てられた、そのフローが使用できるバンド幅である。ポリシー情報１２４は、後述する制御情報送受信部１１により登録される。

スケジューリングパラメータ１２５は、送信キュー２３が有する内部キュー２３２からパケットを出力する場合に、どのような順番で出力を行うかをスケジューラ１３が決定するために用いるパラメータを含む。スケジューリングパラメータ１２５は、送信キュー２３毎に、例えば図５に示すように、キュー番号、優先度、重み、平均パケット長及びカウンタの領域を有する。図５は、スケジューリングパラメータの一例を示す図である。キュー番号は、各内部キュー２３２を表す番号である。そして、スケジューリングパラメータ１２５は、各キュー番号が振られた内部キュー２３２の優先度、重み及び平均パケット長が、制御部１４により登録される。図５において、優先度は各キュー番号に対応させてＰ１〜ＰＮと表したが、例えば、優先度が０〜７で表される場合、Ｐ１〜ＰＮは、０〜７の何れかの値となる。また、スケジューリングパラメータ１２５のカウンタの領域は、スケジューラ１３が使用する作業領域であり、スケジューラ１３が、パケット出力のスケジュールを行うに当たり値を格納して使用する。

フロー識別部１８は、各受信ポート２１からスイッチング部２２へ出力されたパケットの送信元ＩＰアドレス、送信先ＩＰアドレス、送信先ポート番号、送信元ポート番号及びプロトコル番号を取得する。そして、フロー識別部１８は、取得した情報に対応するフローＩＤをフロー管理情報１２１に含まれるフロー識別情報２１１から取得する。

その後、フロー識別部１８は、取得したフローＩＤをキュー選択部１６、受信側メータカウンタ１７及びスイッチング部２２へ出力する。この時、フロー識別部１８は、出力したフローＩＤがどのパケットが属するフローの識別情報か判別できるように各部へ出力する。

受信側メータカウンタ１７は、各受信ポート２１からスイッチング部２２へ出力されたパケットの情報を取得する。さらに、受信側メータカウンタ１７は、各パケットが属するフローのフローＩＤをフロー識別部１８から取得する。そして、受信側メータカウンタ１７は、フロー毎のパケットの数をカウントし、単位時間当たりの各フローの受信量であるフロー受信量を算出する。その後、受信側メータカウンタ１７は、各フロー受信量をフローＩＤに対応させてフロー情報１２２として記憶部１２に格納する。

キュー選択部１６は、スイッチング部２２から出力された各パケットが属するフローのフローＩＤの入力をフロー識別部１８から受ける。また、キュー選択部１６は、各フローＩＤに対応するフローグループの情報をフロー管理情報１２１のフローグループ定義情報２１２から取得する。

そして、キュー選択部１６は、送信キュー２３に入力された各パケットをどの内部キュー２３２に格納するかをデマルチプレクサ２３１に指示する。この時、キュー選択部１６は、同じフローグループに属するパケットであれば同じ内部キュー２３２に格納するように指示する。また、キュー選択部１６は、異なるフローグループに属するパケットであれば、それぞれ異なる内部キュー２３２に格納するように指示する。

例えば、送信キュー２３が、内部キュー２３２として、内部キュー＃１〜＃４を有するとする。そして、図３に示すように、フローＩＤがＦ１及びＦ２であるフローが、ＦＧ１のフローグループに属し、フローＩＤがＦ３であるフローがＦＧ２のフローグループに属する場合とする。この場合、キュー選択部１６は、内部キュー＃１〜＃４の内、何れか一つ、例えば、内部キュー＃１にＦＧ１のフローグループのパケットを格納するとした場合、Ｆ１及びＦ２のフローに属するパケットは内部キュー＃１に格納するようにデマルチプレクサ２３１に指示する。また、キュー選択部１６は、ＦＧ２のフローグループのパケットを格納する内部キュー２３２として内部キュー＃２〜＃４のいずれか一つ、例えば、内部キュー＃２を選択する。この場合、キュー選択部１６は、Ｆ３のフローに属するパケットは内部キュー＃２に格納するようにデマルチプレクサ２３１に指示する。

その後、ＦＧ１のフローグループが、制御部１４により、ＦＧ３及びＦＧ４に分割され、Ｆ１のフローはＦＧ３のフローグループに属し、Ｆ２のフローはＦＧ４のフローグループに属するように変更されたとする。この場合、キュー選択部１６は、今までＦ１及びＦ２が属していたＦＧ１のフローグループと、これからＦ１が属するＦＧ３のフローグループ及びＦ２が属するＦＧ４のフローグループとは異なるフローグループとして認識する。そこで、キュー選択部１６は、ＦＧ３及びＦＧ４のフローグループのそれぞれに内部キュー＃３又は＃４のいずれかをそれぞれ割り当てる。ここでは、キュー選択部１６は、ＦＧ３のフローグループに内部キュー＃３を割り当て、ＦＧ４のフローグループに内部キュー＃４を割り当てる。そこで、キュー選択部１６は、Ｆ１及びＦ２に属するパケットを内部キュー＃１に格納させることは止め、Ｆ１に属するパケットを内部キュー＃３に格納し、Ｆ２に属するパケットを内部キュー＃４に格納するようにデマルチプレクサ２３１に指示する。これにより、内部キュー＃１が使われないようになる。このように、キュー選択部１６は、フローグループの情報を取得し、各フローグループにいずれかの内部キュー２３２を割り当てる。すなわち、内部キュー２３２とフローグループとは必ず１対１で対応する。

送信側メータカウンタ１５は、各送信キュー２３の各内部キュー２３２から出力されたパケットの情報を取得する。内部キュー２３２は、フローグループ毎に割り当てられるので、この情報は、フローグループ毎の出力されたパケットの情報にあたる。そして、送信側メータカウンタ１５は、内部キュー２３２毎の単位当たりのパケットの送信量、すなわちフローグループ毎の単位時間あたりのパケットの送信量であるフローグループ送信量を算出する。

また、送信側メータカウンタ１５は、内部キュー２３２毎に格納されているパケットサイズの合計を算出する。内部キュー２３２は、１つのフローグループに対応するので、この算出した値は、各フローグループの内部キュー２３２に格納されているサイズであるフローグループキュー長にあたる。すなわち、送信側メータカウンタ１５は、フローグループキュー長を算出する。

また、送信側メータカウンタ１５は、内部キュー２３２毎に廃棄されたパケットの数をカウントする。内部キュー２３２は、１つのフローグループに対応するので、このパケットの数は、フローグループ毎の破棄されたパケット数であるフローグループ廃棄数にあたる。すなわち、送信側メータカウンタ１５は、フローグループ廃棄数を算出する。

そして、送信側メータカウンタ１５は、算出したフローグループ送信量、フローグループキュー長及びフローグループ廃棄数をフローグループ統計情報としてフローグループ情報１２３に登録する。

また、送信側メータカウンタ１５は、各内部キュー２３２の出力を監視し、フロー毎の送信量であるフロー送信量を算出する。また、送信側メータカウンタ１５は、内部キュー２３２に格納されているフロー毎のサイズの合計であるフローキュー長を算出する。さらに、送信側メータカウンタ１５は、フロー毎のパケットの廃棄数であるフロー廃棄数を算出する。そして、送信側メータカウンタ１５は、算出したフロー送信量、フローキュー長及びフロー廃棄数をフロー統計情報としてフロー情報１２２に登録する。この、送信側メータカウンタ１５及び上述した受信側メータカウンタ１７が、「情報取得部」の一例にあたる。

制御情報送受信部１１は、管理用サーバ２から構成定義を取得する。構成定義には、フロー識別情報２１１及びポリシー情報１２４が含まれる。また、構成定義には、キューの優先度及び平均パケット長が含まれる。

制御情報送受信部１１は、フロー識別情報２１１及びポリシー情報１２４を記憶部１２に格納する。また、制御情報送受信部１１は、キューの優先度及び平均パケット長を制御部１４へ出力する。

さらに、制御情報送受信部１１は、フローの初期のグルーピングの情報及び送信キュー２３の１ラウンドでの送出可能量を管理用サーバ２から取得する。そして、制御情報送受信部１１は、フローの初期のフローグループの情報及び送信キュー２３の１ラウンドでの送出可能量を制御部１４へ出力する。

また、制御情報送受信部１１は、フロー情報１２２及びフローグループ情報１２３を記憶部１２から取得する。そして、制御情報送受信部１１は、フロー情報１２２及びフローグループ情報１２３を管理用サーバ２へ送信する。

制御部１４は、重み計算部１１４を有する。制御部１４は、フローグループの作成による内部キュー２３２の使用状態の制御及びスケジューリングパラメータの調整による内部キュー２３２からの出力調整の制御を行う。

制御部１４によるフローグループの作成について説明する。簡単に説明すると、制御部１４は、フロー情報１２２、フローグループ情報１２３及びポリシー情報１２４を用いてフローのグルーピングを行い、フローグループを作成する。そして、制御部１４は、作成したフローグループの情報をフロー管理情報１２１のフローグループ定義情報２１２に登録する。これにより、制御部１４は、フローグループ毎の内部キュー２３２の割り当て、内部キュー２３２の分割及び結合などの再構成を制御する。以下に、制御部１４によるフローグループの作成の詳細について説明する。

制御部１４は、フローの初期のグルーピングの情報を制御情報送受信部１１から取得する。そして、制御部１４は、取得した初期のグルーピングの情報にしたがい、フロー管理情報１２１のフローグループ定義情報２１２に各フローに対応するフローグループを登録する。

次に、ある１つのフローグループについて分割を行う場合、すなわち内部キュー２３２を分割するための判定について説明する。制御部１４は、分割の実行を決定するための、フローグループにおけるスループットと設定バンド幅との乖離率の分割閾値を予め記憶する。また、制御部１４は、フローグループに属する各フローのスループット、すなわちフロー送信量をフロー情報１２２から取得する。さらに、制御部１４は、フローグループに含まれる各フローの設定バンド幅をポリシー情報１２４から取得する。

そして、制御部１４は、フローグループに属するフロー毎に、フローのスループットからフローの設定バンド幅を減算し、減算結果をフローの設定バンド幅で除算した値を求め、乖離率とする。乖離率は、フローのスループットが設定バンド幅からどのくらい離れているかを表す。ここで、乖離率をＤ_ｆｌｏｗとすると、Ｄ_ｆｌｏｗ＝（フローのスループット−フローの設定バンド幅）／フローの設定バンド幅と表される。

次に、制御部１４は、算出した乖離率の中で正の値を有するものの合計を求め、フローグループの乖離率とする。例えば、フローグループの乖離率をＤ_ＦＧとすると、Ｄ_ＦＧ＝Σ_{ｆｌｏｗ∈ＦＧ}ｍａｘ（Ｄ_ｆｌｏｗ，０）と表される。

そして、制御部１４は、フローグループの乖離率が分割閾値を超えたか否かを判定する。制御部１４は、フローグループの乖離率が分割閾値を超えた場合、すなわち、「Ｄ_ＦＧ＞分割閾値」をみたす場合、そのフローグループの分割を決定する。

制御部１４は、分割を決定したフローグループに属するフローの中で、乖離率が正の値を有するフローをまとめて１つのフローグループとする。さらに、制御部１４は、分割を決定したフローグループに属するフローの中で残ったフローをまとめて他の１つのフローグループとする。例えば、フローグループＦＧ１をＦＧ３及びＦＧ４に分割する場合、ＦＧ３＝｛［Ｄ_ｆｌｏｗ＞０］となるフロー｝，ＦＧ４＝ＦＧ１−ＦＧ３と表される。ただし、このグルーピング方法は一例であり、フローグループに属するフローを複数のグループに分けることができれば他の方法でもよい。

例えば、図６を参照して、制御部１４によるフローグループの分割について説明する。図６は、フローグループの分割を説明するための図である。図６における状態３０１は、分割前の状態を表す。また、状態３０２は、分割後の状態を表す。ここで、図６では、使用しない内部キュー２３２は図示していない。また、図６におけるＡ〜Ｄは、それぞれがフローＡ〜Ｄに含まれるパケットを表す。

状態３０１では、フローグループＦＧ１にフローＡ〜Ｃが含まれる。ここでは、このようなフローグループとフローの状態をＦＧ１＝｛Ａ，Ｂ，Ｃ｝と表す。また、フローグループＦＧ２にフローＤが含まれる。これは、ＦＧ２＝｛Ｄ｝と表される。

ここで、フローグループＦＧ１の分割を例に、制御部１４による分割を説明する。制御部１４は、フローＡ〜Ｃの乖離率（Ｄ_ｆｌｏｗ）を計算する。ここで、フローＡ〜Ｃの乖離率を、それぞれＤ_Ａ〜Ｄ_Ｃとする。さらに、制御部１４は、フローグループＦＧ１の乖離率Ｄ_ＦＧ１を求める。そして、制御部１４は、フローグループＦＧ１の乖離率Ｄ_ＦＧ１が分割閾値を超えた場合、フローグループＦＧ１を分離する。このとき、Ｄ_Ａ＞０，Ｄ_Ｂ≦０，Ｄ_Ｃ≦０だとすると、制御部１４は、状態３０２のように、分割後のフローグループＦＧ３にフローＡを属させ、フローグループＦＧ４にフローＢ及びＣを属させる。すなわち、分割後のフローグループは、ＦＧ３＝｛Ａ｝及びＦＧ４＝｛Ｂ，Ｃ｝となる。

次に、ある複数のフローグループについて結合を行う場合、すなわち内部キュー２３２を結合するための判定について説明する。制御部１４は、分割を行うにあたり使用可能な内部キュー２３２の数の上限を超えてしまう場合、キューの結合の実行を決定する。

ここでは、制御部１４は、結合するフローグループに属するフローを新たなフローグループに属させる。これにより、結合前のフローグループに属していたフローは全て新しいフローグループに属することになる。この後、結合前のフローグループに割り当てられた内部キュー２３２に格納されていたパケットが全て出力されると、その内部キュー２３２は空になり、未使用の状態となる。これに対して、結合前のフローグループに属していたフローに含まれるパケットは、新しく作成されたフローグループに割り当てられた内部キュー２３２に格納されていく。このようにして、制御部１４は、複数のフローグループを１つのフローグループにまとめる。

例えば、図７を参照して、制御部１４によるフローグループの結合について説明する。図７は、フローグループの結合を説明するための図である。図７における状態３０３は、結合前の状態を表す。また、状態３０４は、結合後の状態を表す。ここで、図７では、使用しない内部キュー２３２は図示していない。また、図７におけるＡ〜Ｄは、それぞれがフローＡ〜Ｄに含まれるパケットを表す。

例えば、フローグループＦＧ１及びＦＧ２を結合してフローグループＦＧ４とする場合について説明する。状態３０３では、フローグループＦＧ１にフローＡが属し、フローグループＦＧ２にフローＢ及びＣが属し、フローグループＦＧ３にフローＤが属するものとする。すなわち、ＦＧ１＝｛Ａ｝、ＦＧ２＝｛Ｂ，Ｃ｝及びＦＧ３＝｛Ｄ｝と表される。

制御部１４は、フローグループＦＧ４を作成する。そして、制御部１４は、フローグループＦＧ４にフローＡ〜Ｃを属させる。すなわち、ＦＧ４＝｛Ａ，Ｂ，Ｃ｝となる。このとき、送信キュー２３は状態３０４の状態となる。これにより、フローグループＦＧ１及びＦＧ２に割り当てられていた２つの内部キュー２３２が未使用となり、代わりにフローグループＦＧ３に割り当てられた内部キュー２３２が使用中になる。すなわち、この結合により未使用の内部キュー２３２が１つ増える。

次に、制御部１４によるスケジューリングパラメータ１２５の登録について説明する。制御部１４は、予め送信キュー２３毎に、その送信キュー２３に含まれる内部キュー２３２のキュー番号を有する。例えば、送信キュー２３にＮ個の内部キュー２３２が存在する場合、送信キュー２３は、内部キュー２３２のキュー番号として＃１〜＃Ｎを有する。

また、制御部１４は、送信キュー２３に含まれる各内部キュー２３２の優先度及び平均パケット長の入力を制御情報送受信部１１から受ける。

最初のスケジューリングパラメータ１２５の設定の場合、制御部１４は、内部キュー２３２に割り当てられたキュー番号に対応させて優先度、重み及び平均パケット長をスケジューリングパラメータ１２５に登録する。ここで、最初の登録では、各内部キュー２３２の重みは全て同じでもよい。

その後、制御部１４は、重み計算部１１４により内部キュー２３２の重みを算出する。以下に、１つの内部キュー２３２を例に、重み計算部１１４による重みの算出について説明する。ここでは、フローグループＦＧ１に割り当てられた内部キュー２３２のバンド幅の設定を求める場合について説明する。重み計算部１１４は、廃棄閾値及びキュー長閾値を予め記憶する。

重み計算部１１４は、初期状態として、例えば、各内部キュー２３２をそれぞれ等しい重みとする。その後、重み計算部１１４は、フローグループＦＧ１の各フローの設定バンド幅をポリシー情報１２４から取得する。そして、重み計算部１１４は、フローグループに属するフローの設定バンド幅の合計を算出し、内部キュー２３２のバンド幅とする。ここで、内部キュー２３２のバンド幅をＢｑとし、フローグループＦＧ１に属するフローをｆｌｏｗとし、さらにｆｌｏｗのバンド幅をＢＷ_ｆｌｏｗとする。このとき、重み計算部１１４は、Ｂｑ＝Σ_{ｆｌｏｗ∈ＦＧ１}ＢＷ_ｆｌｏｗという式を用いて内部キュー２３２のバンド幅を算出する。

さらに、重み計算部１１４は、送信キュー２３に含まれる全ての内部キュー２３２のバンド幅の合計を送信キュー２３の全体のバンド幅とする。すなわち、送信キュー２３の全体のバンド幅をＳとし、対象とする送信キュー２３に含まれる内部キュー２３２をｑとし、その集合をＱとすると、重み計算部１１４は、Ｓ＝Σ_ｑ∈ＱＢｑという式を用いて送信キュー２３の全体のバンド幅を算出する。

次に、重み計算部１１４は、対象とする送信キュー２３が繋がる送信ポート２４のバンド幅が、算出した送信キュー２３の全体のバンド幅（Ｓ）よりも大きい場合、各内部キュー２３２のバンド幅の正規化を行う。具体的には、重み計算部１１４は、各内部キュー２３２のバンド幅（Ｂｑ）を算出した送信キュー２３の全体のバンド幅（Ｓ）で除算する。そして、送信ポート２４のバンド幅をＢＷ_Ｌとすると、重み計算部１１４は、除算結果に送信ポート２４のバンド幅（ＢＷ_Ｌ）を乗算した値を正規化後の内部キュー２３２のバンド幅とする。すなわち、正規化された内部キュー２３２のバンド幅をＢＷｑとすると、重み計算部１１４は、ＢＷｑ＝（Ｂｑ／Ｓ）×ＢＷ_Ｌという式を用いて、正規化された内部キュー２３２のバンド幅を求める。

これに対して、対象とする送信キュー２３が繋がる送信ポート２４のバンド幅が、算出した送信キュー２３の全体のバンド幅（Ｓ）以下の場合、重み計算部１１４は、算出した内部キュー２３２のバンド幅（Ｂｑ）を正規化後のバンド幅とする。

重み計算部１１４は、各内部キュー２３２に割り当てられたフローグループのフローグループ送信量、フローグループキュー長及びフローグループ廃棄数をフローグループ情報１２３から取得する。そして、重み計算部１１４は、フローグループ送信量と算出した内部キュー２３２の設定バンド幅とを比較する。フローグループ送信量が内部キュー２３２の設定バンド幅よりも小さい場合、重み計算部１１４は、その内部キュー２３２の重みを増加させる。また、フローグループ送信量が内部キュー２３２の設定バンド幅と同じ場合、重み計算部１１４は、その内部キュー２３２の重みを維持する。また、フローグループ送信量が内部キュー２３２の設定バンド幅よりも大きい場合、重み計算部１１４は、その内部キュー２３２の重みを減少させる。

また、重み計算部１１４は、フローグループ廃棄数と廃棄閾値とを比較する。フローグループ廃棄数が廃棄閾値よりも大きい場合、重み計算部１１４は、その内部キュー２３２の重みを増加させる。また、フローグループ廃棄数が廃棄閾値と同じ場合、重み計算部１１４は、その内部キュー２３２の重みを維持する。また、フローグループ廃棄数が廃棄閾値よりも小さい場合、重み計算部１１４は、その内部キュー２３２の重みを減少させる。

また、重み計算部１１４は、フローグループキュー長とキュー長閾値とを比較する。フローグループキュー長がキュー長閾値よりも大きい場合、重み計算部１１４は、その内部キュー２３２の重みを増加させる。また、フローグループキュー長がキュー長閾値と同じ場合、重み計算部１１４は、その内部キュー２３２の重みを維持する。また、フローグループキュー長がキュー長閾値よりも小さい場合、重み計算部１１４は、その内部キュー２３２の重みを減少させる。

ここで、重み計算部１１４による内部キュー２３２の重みの算出の一例についてさらに具体的に説明する。ここでは、現在の内部キュー２３２の重みをＷ_{ＣＵＲＲＥＮＴ}とし、新しく算出する重みをＷ_ＮＥＷとする。この場合、重み計算部１１４は、内部キュー２３２の重みの算出に用いるための、スループットの重み（Ｋｔ）、破棄パケット数の重み（Ｋｄ）及びキュー長の重み（Ｋｑ）の入力を制御情報送受信部１１から受ける。そして、重み計算部１１４は、フローグループ送信量（ＴＰ：Throughput）から設定バンド幅（設定ＢＷ：Band Width）を減算した値にスループットの重みを乗算した値を算出する。また、重み計算部１１４は、フローグループの廃棄数（Ｄｒｏｐ）から廃棄閾値を減算した値に破棄パケット数の重みを乗算した値を算出する。また、重み計算部１１４は、フローグループキュー長（Ｑｌｅｎ：Q Length）からキュー長閾値を減算した値にキュー長の重みを乗算した値を算出する。そして、重み計算部１１４は、算出した３つの値を現在の重みに加算することで、新しい重みを算出する。すなわち、重み計算部１１４は、Ｗ_ＮＥＷ＝Ｗ_{ＣＵＲＲＥＮＴ}＋Ｋｔ（ＴＰ−設定ＢＷ）＋Ｋｄ（Ｄｒｏｐ−Ｄｒｏｐ閾値）＋Ｋｑ（Ｑｌｅｎ−Ｑｌｅｎ閾値）を計算することで、内部キュー２３２の新しい重みを算出する。

また、重み計算部１１４による内部キュー２３２の重みの算出の他の例ついては以下のような方法でもよい。重み計算部１１４は、フローグループ送信量から設定バンド幅を減算した値、フローグループの廃棄数から廃棄閾値を減算した値、フローグループキュー長からキュー長閾値を減算した値をキーとして、重みの変更値を決定するための３次元テーブルを有する。そして、重み計算部１１４は、算出した値をキーとして、３次元テーブルから重みの変更値を求める。そして、重み計算部１１４は、現在の重みに重みの変更値を加算して新しい重みを算出する。

図８は、重み計算における重みの変更の規則の一例を表す図である。以上に説明したように、図８に示す規則にしたがい、重み計算部１１４は、各内部キュー２３２におけるフローグループ送信量、フローグループ廃棄数及びフローグループキュー長を用いて、内部キュー２３２の重みを決定する。そして、重み計算部１１４は、求めた内部キュー２３２の重みを送信キュー２３内で正規化して各内部キュー２３２の重みとする。例えば、内部キュー２３２として＃１〜＃４まである場合、正規化前の重みをＷ＃１〜＃４とすると、キュー番号が＃１の内部キュー２３２の正規化後の重みは、Ｗ＃１／（Ｗ＃１＋Ｗ＃２＋Ｗ＃３＋Ｗ＃４）と表される。

そして、制御部１４は、重み計算部１１４が算出した各内部キュー２３２の重みをスケジューリングパラメータ１２５に登録する。このように、制御部１４は、フローグループの統計情報を用いて、各内部キュー２３２の状態に合わせて内部キュー２３２の重みを変更していく。この制御部１４が、「グルーピング部」の一例にあたる。

スケジューラ１３は、スケジューリングパラメータ１２５を用いてパケットを出力させる内部キュー２３２の順番を決定する。そして、スケジューラ１３は、決定した順番にしたがいマルチプレクサ２３３に内部キュー２３２からパケットを取得させる。これにより、スケジューラ１３は、公平性を維持しつつフローの出力を調整する。

具体的には、スケジューラ１３は、スケジューリングパラメータ１２５における各内部キュー２３２の優先度を参照する。ここでは、上述したように、３を基準の優先度、７〜４を基準の優先度に優先する優先度、２〜０を基準の優先度より低い優先度とする。スケジューラ１３は、まず、優先度が７〜４の内部キュー２３２の中で優先度が高いものからパケットの出力を行う。

次に、スケジューラ１３は、優先度が３の内部キュー２３２の中で、ＷＲＲ（Weight Round Robin）又はＤＤＲ（Deficit Round Robin）を用いてパケットを出力させる内部キュー２３２の順番を決定する。

例えば、ＷＲＲを用いる場合、スケジューラ１３は、スケジューリングパラメータ１２５から内部キュー２３２の重み及び平均パケット長を取得する。そして、スケジューラ１３は、内部キュー２３２の重みを内部キュー２３２の平均パケット長で除算して、内部キュー２３２の正規化された重みを算出する。

次に、スケジューラ１３は、算出した正規化された重みの中から最小値を特定する。さらに、スケジューラ１３は、各内部キュー２３２の正規化された重みを重みの最小値で除算して、内部キュー２３２毎の送信パケット数を求める。そして、スケジューラ１３は、求めた送信パケット数分のパケットがそれぞれの内部キュー２３２から出力されるように、内部キュー２３２の出力順を決定する。そして、スケジューラ１３は、決定した出力順で内部キュー２３２からパケットを取得するようにマルチプレクサ２３３を制御する。また、スケジューラ１３は、内部キュー２３２が空になった場合、その内部キュー２３２からのパケットの取得の停止をマルチプレクサ２３３に指示する。

また、例えば、ＤＲＲを用いる場合、スケジューラ１３は、１ラウンドでの送出可能量を制御情報送受信部１１から取得する。そして、スケジューラ１３は、内部キュー２３２の重みに送出可能量を乗算して各内部キュー２３２の１ラウンドあたりの通信量を算出する。

次に、スケジューラ１３は、各内部キュー２３２の算出した１ラウンドあたりの通信量をスケジューリングパラメータ１２５のカウンタの領域に設定する。そして、スケジューラ１３は、ある内部キュー２３２に出力可能なパケットが存在し、且つカウンタ数が負でなければ、その内部キュー２３２からパケットを取得するようにマルチプレクサ２３３を制御する。そして、スケジューラ１３は、カウンタから出力した分のパケットの大きさを減算する。そして、ラウンドの最後に、スケジューラ１３は、内部キュー２３２の重みに送出可能量を乗算した値をカウンタに登録する。スケジューラ１３は、１ラウンドあたりの通信量の算出、カウンタの登録及びカウンタを減らしながらのパケットの出力の指示を出力するパケットがなくなるまで繰り返す。

そして、スケジューラ１３は、優先度が３の内部キュー２３２のパケットの出力が終わると、次に、優先度が０〜２の内部キュー２３２の優先度にしたがって、パケットを出力させる。このスケジューラ１３が、「スケジューリング部」の一例にあたる。

次に、図９を参照して、本実施例に係るスイッチ１におけるパケット転送の全体的な流れについて説明する。図９は、実施例１に係るスイッチにおけるパケット転送処理のフローチャートである。

受信ポート２１は、外部の情報処理装置からパケットを受信する（ステップＳ１）。そして、受信ポート２１は、受信したパケットをスイッチング部２２へ出力する。

フロー識別部１８は、受信ポート２１からスイッチング部２２へ出力されたパケットの送信元ＩＰアドレス、送信先ＩＰアドレス、送信先ポート番号、送信元ポート番号及びプロトコル番号を取得する。そして、フロー識別部１８は、取得した情報に対応するフローＩＤをフロー管理情報１２１に含まれるフロー識別情報２１１から取得し、各パケットが属するフローを特定する（ステップＳ２）。フロー識別部１８は、各パケットが属するフローのフローＩＤをスイッチング部２２へ出力する。

スイッチング部２２は、パケットの入力を受信ポート２１から受ける。また、スイッチン部２２は、受信したパケットが属するフローのフローＩＤをフロー識別部１８から取得する。そして、スイッチング部２２は、フロー管理情報１２１のフローグループ定義情報２１２から各パケットのフローグループを特定する。そして、スイッチング部２２は、特定したフローグループにしたがい各パケットを出力する送信キュー２３を決定し、決定した送信キュー２３へ各パケットを送信する（ステップＳ３）。

キュー選択部１６は、フロー管理情報１２１のフローグループ定義情報２１２から各パケットのフローグループを特定する。そして、キュー選択部１６は、特定したフローグループに内部キュー２３２が割り当てられていない場合、未使用の内部キュー２３２の中から１つ選択しフローグループに割り当てる。そして、キュー選択部１６は、フローグループ毎に、割り当てられた内部キュー２３２へパケットを格納する（ステップＳ４）。

制御部１４の重み計算部１１４は、フローグループ送信量、フローグループキュー長及びフローグループ廃棄数を用いて各内部キュー２３２それぞれの重みを算出する。そして、制御部１４は、重み計算部１１４により算出された内部キュー２３２の重みをスケジューリングパラメータ１２５へ登録し、スケジューリングパラメータ１２５を変更する（ステップＳ５）。

スケジューラ１３は、スケジューリングパラメータ１２５から優先度を取得し、優先度が基準の優先度より高い内部キュー２３２のパケットを基準の優先度の内部キュー２３２より先に出力することを決定する。次に、スケジューラ１３は、基準の優先度を有する内部キュー２３２において、内部キュー２３２の重みや内部キュー２３２の平均パケット長を取得し、カウンタを用いて、ＷＲＲ又はＤＲＲなどによりパケット送信のスケジュールを決定する。さらに、スケジューラ１３は、優先度が基準の優先度より低い内部キュー２３２のパケットを基準の優先度の内部キュー２３２の後に出力することを決定する（ステップＳ６）。そして、スケジューラ１３は、決定したスケジュールにしたがい内部キュー２３２からパケットを取得するようにマルチプレクサ２３３に指示する。

マルチプレクサ２３３は、スケジューラ１３からの指示にしたがいパケットを取得する内部キュー２３２からパケットを取得し、送信ポート２４を介して宛先の外部装置へパケットを送信する（ステップＳ７）。

その後、スケジューラ１３及び制御部１４は、スイッチ１の動作を終了するか否かを判定する（ステップＳ８）。スイッチ１の動作を終了しない場合（ステップＳ８：否定）、処理はステップＳ１へ戻る。

これに対して、スイッチ１の動作を終了する場合（ステップＳ８：肯定）、スケジューラ１３及び制御部１４は、パケットの転送処理を終了する。

次に、図１０を参照して、制御部１４によるフローグループの再構成の処理の流れについて説明する。図１０は、フローグループの再構成の処理のフローチャートである。

制御部１４は、フロー識別情報２１１を基にフローを識別し、各フローを含む初期のフローグループを作成する。そして、制御部１４は、フローグループ定義情報２１２に各フローに対応するフローグループを登録する（ステップＳ１１）。

その後、制御部１４は、フローの送信量をフロー情報１２２から取得する。また、制御部１４は、フローの設定バンド幅をポリシー情報１２４から取得する。そして、制御部１４は、フローの送信量及びフローの設定バンド幅から乖離率を求める。さらに、制御部１４は、求めた乖離率からフローグループ乖離率を算出する。そして、制御部１４は、フローグループ乖離率が分割閾値を超えているか否かを判定する（ステップＳ１２）。

フローグループ乖離率が分割閾値を超えていない場合（ステップＳ１２：否定）、制御部１４は、ステップＳ１７へ進む。

これに対して、フローグループ乖離率が分割閾値を超えた場合（ステップＳ１２：肯定）、制御部１４は、フローグループを分割することを決定する（ステップＳ１３）。

次に、制御部１４は、分割により使用する内部キュー２３２の数が使用できる内部キュー２３２の数の上限を超えるか否かを判定する（ステップＳ１４）。使用する内部キュー２３２の数が上限を超えない場合（ステップＳ１４：否定）、制御部１４は、ステップＳ１６へ進む。

これに対して、使用する内部キュー２３２の数が上限を超える場合（ステップＳ１４：肯定）、制御部１４は、異なるフローグループに属する複数のフローが１つのフローグループに属するようにフローグループ定義情報２１２を変更してフローグループの結合を実行する（ステップＳ１５）。具体的には、キュー選択部１６が、変更されたフローグループ定義情報２１２にしたがってパケットの格納先をデマルチプレクサ２３１に指示することで、フローグループの結合が実現される。

次に、制御部１４は、１つのフローグループに属する複数のフローが異なる複数のフローグループに属するようにフローグループ定義情報２１２を変更してフローグループの分割を実行する（ステップＳ１６）。具体的には、キュー選択部１６が、変更されたフローグループ定義情報２１２にしたがってパケットの格納先をデマルチプレクサ２３１に指示することで、フローグループの分割が実現される。

その後、制御部１４は、スイッチ１の動作を終了するか否かを判定する（ステップＳ１７）。スイッチ１の動作を終了しない場合（ステップＳ１７：否定）、制御部１４は、ステップＳ１２に戻る。これに対して、スイッチ１の動作を終了する場合（ステップＳ１７：肯定）、制御部１４は、フローの再構成処理を終了する。

ここで、図９のステップＳ３及びＳ４における処理は、例えば、図１０のフローにより定期的に更新されるフローグループ定義情報２１２が用いられる。

以上に説明したように、本実施例に係るスイッチは、フローグループに属する各フローのスループットが低下した場合に、そのフローグループを分割し、ＷＲＲやＤＲＲなどにより各内部キューからパケットを出力する。これにより、スループットが低下したフローが複数の内部キューに格納されることになり、出力される確率が上昇する。したがって、スループットが低下したフローのスループットを向上させることができ、スイッチとしての全体的な通信性能の向上及びネットワーク資源のフェアな共有を実現することができる。

また、本実施例に係るスイッチは、優先度に応じてパケットを出力させる内部キューを選択するため、優先度に適合した通信品質を実現することができる。

（変形例）
次に、実施例１の変形例について説明する。実施例１では、送信側メータカウンタ１５がフローの統計情報を取得してフロー情報１２１に格納した。しかし、フローグループとして同じ内部キュー２３２に格納されたフロー毎の統計情報を取得することは困難な場合が多い。そこで、本変形例に係る制御部１４は、フローグループの統計情報から送信側のフローの統計情報を算出することが実施例１と異なる。本実施例に係るスイッチ１も図１のブロック図で表される。以下の説明では、実施例１と同じ各部の機能については説明を省略する。

送信側メータカウンタ１５は、各送信キュー２３の各内部キュー２３２から出力されたパケットに関する情報を取得する。そして、送信側メータカウンタ１５は、フローグループ送信量、フローグループキュー長及びフローグループ廃棄数を算出する。

そして、送信側メータカウンタ１５は、算出したフローグループ送信量、フローグループキュー長及びフローグループ廃棄数をフローグループ統計情報としてフローグループ情報１２３に登録する。

これに対して、本実施例では、送信側メータカウンタ１５は、フロー毎の統計情報は取得しない。すなわち、フロー情報１２２には、送信側のフローの統計情報は格納されない。

制御部１４は、フローグループ送信量、フローグループキュー長及びフローグループ廃棄数をフローグループ情報１２３から取得する。さらに、制御部１４は、フロー情報１２２からフローの受信量を取得する。さらに、制御部１４は、フローグループ定義情報２１２から各フローグループを構成するフローを特定する。

次に、制御部１４は、フローの受信量をそのフローが属するフローグループに属するフローの受信量の総和で除算し、フローの重みを算出する。このフローの重みは、そのフローが属するフローグループの中で、そのフローがどの程度の割合を占めるかを表す。そして、制御部１４は、フローグループ送信量に算出したフローの重みを乗算して、フロー送信量を算出する。また、制御部１４は、フローグループキュー長に算出したフローの重みを乗算して、フローキュー長を算出する。また、制御部１４は、フローグループ廃棄数にフローの重みを乗算して、フロー廃棄数を算出する。そして、制御部１４は、算出したフロー送信量、フローキュー長及びフロー廃棄数をフロー情報１２２に登録する。

さらに、制御部１４は、算出したフロー送信量を用いてフローグループの再構成を行う。

以上に説明したように、本実施例に係るスイッチは、フローグループの統計情報からフロー毎の統計情報を算出する。すなわち、本実施例に係るスイッチは、送信キューからのフロー毎の統計情報が取得困難な場合でも、フロー送信量が算出でき実施例１と同様にグルーピングを行うことができ、通信性能の向上及びネットワーク資源のフェアな共有を実現することができる。

次に、実施例２について説明する。本実施例に係るスイッチ１は、基準の優先度を有する内部キュー２３２に対して、スケジューラ１３が、ＤＲＲに改良を加えたアルゴリズムを用いて送信要求を取得する内部キュー２３２を決定する。次に、スケジューラ１３は、送信要求を取得する内部キュー２３２の中からパケットを出力する内部キュー２３２を選択する。そして、スケジューラ１３は、送信要求の取得及びパケットを出力する内部キュー２３２の選択を繰り返す。本実施例に係るスイッチ１も図１のブロック図で表される。また、以下の説明では、実施例１と同様の各部の機能については説明を省略する。

まず、送信要求を取得する内部キュー２３２の決定について説明する。スケジューラ１３は、各内部キュー２３２の１ラウンドの送出可能量を制御情報送受信部１１から取得する。また、スケジューラ１３は、制御部１４によって変更される内部キュー２３２の重みをスケジューリングパラメータ１２５から取得する。

次に、スケジューラ１３は、内部キュー２３２の１ラウンドの送出可能量に内部キュー２３２の重みを乗算する。そして、スケジューラ１３は、算出した値をカウンタ値としてスケジューラ１３のカウンタの領域に設定する。これにより、スケジューラ１３は、内部キュー２３２の重みに応じたカウンタ値の設定が行える。

次に、スケジューラ１３は、パケットの出力を指示する送信キュー２３が有する内部キュー２３２を全て抽出する。

次に、スケジューラ１３は、抽出した内部キュー２３２に格納されたパケットの情報を取得し、抽出した内部キュー２３２の中でパケットが有る内部キュー２３２を特定する。

さらに、スケジューラ１３は、特定した内部キュー２３２のそれぞれのカウンタ値が０より大きいか否かを判定する。カウンタ値が０より大きい内部キュー２３２があれば、スケジューラ１３は、その内部キュー２３２から送信要求を取得する。その後、スケジューラ１３は、送信要求を取得した内部キュー２３２の中からパケットを出力する内部キュー２３２を選択する。

そして、スケジューラ１３は、選択した内部キュー２３２からのパケットの出力をマルチプレクサ２３３に指示する。マルチプレクサ２３３は、スケジューラ１３から指示された内部キュー２３２からパケットを取得し、送信ポート２４へ出力する。

また、スケジューラ１３は、送信パケット長を取得する。そして、スケジューラ１３は、スケジューリングパラメータ１２５におけるパケットを出力させた内部キュー２３２のカウンタから送信パケット長を減算する。

その後、スケジューラ１３は、送信キュー２３に含まれる内部キュー２３２の内、選択されていない内部キュー２３２があるか否かを判定する。洗濯されてない内部キュー２３２がある場合、スケジューラ１３は、選択されていない内部キュー２３２を抽出、送信要求の取得、内部キュー２３２の選択、パケットの出力及びカウンタからの平均パケット長の減算の処理を繰り返す。

また、送信キュー２３に含まれる全ての内部キュー２３２を選択した場合、スケジューラ１３は、パケットの残る内部キュー２３２のカウンタが全て０以下か否かを判定する。パケットの残る内部キュー２３２の中でカウンタが０より大きいものが存在する場合、スケジューラ１３は、内部キュー２３２の選択履歴を消去し、内部キュー２３２の未選択の状態に戻る。その後、スケジューラ１３は、選択されていない内部キュー２３２を抽出、送信要求の取得、内部キュー２３２の選択、パケットの出力及びカウンタからの平均パケット長の減算の処理を繰り返す。

これに対して、パケットの残る内部キュー２３２のカウンタ値が全て０以下の場合、スケジューラ１３は、パケットの出力処理を終了する。その後、スケジューラ１３は、カウンタの設定から上記処理を繰り返す。

次に、本実施例に係るスケジューラ１３による送信要求を取得した内部キュー２３２からのパケットを出力させる内部キュー２３２の選択について説明する。ここで、スイッチ１では、制御部１４によりフローグループの分割及び結合といった再構成が行われる。その場合、スケジューラ１３は、再構成中の内部キュー２３２の集合からパケットを出力する内部キュー２３２を選択する１段目の選択を行う。さらに、スケジューラ１３は、１段目で選択された内部キュー２３２と１段目に含まれない内部キュー２３２との中からパケットを出力する内部キュー２３２を選択する２段目の選択を行う。このように、スケジューラ１３は、２段階の選択を含むスケジューリングを行う。そこで、この２段階の選択を含むスケジューリングについて詳細に説明する。以下では、１段目の選択は内部キュー２３２の優先度に応じて選択を行うので、１段目の選択を「優先度選択」という。また、２段目の選択はラウンドロビンを基にした選択なので「ラウンドロビン選択」という。

まず、スケジューラ１３は、パケットが格納されており、カウンタが０より大きい値を有する内部キュー２３２を送信可能なパケットがある内部キュー２３２と判定する。そして、スケジューラ１３は、送信可能な内部キュー２３２から送信要求を取得する。

例えば、送信キュー２３に内部キュー２３２が４本ある場合で説明する。以下では、各内部キュー２３２にそれぞれ０〜３番の番号を振り、それぞれを内部キュー＃０〜＃３とする。そして、内部キュー＃０の送信要求はＸ［０］とし、内部キュー＃１の送信要求はＸ［１］とし、内部キュー＃２の送信要求はＸ［２］とし、内部キュー＃３の送信要求はＸ［３］とする。さらに、送信要求の値が１の場合、送信要求があるとし、送信要求の値が０の場合、送信要求が無いとする。また、以下の説明で、単に「Ｘ」と記した場合、Ｘ［０］〜Ｘ［３］の値を並べた４ビットの信号を表すものとする。このＸが、上述したＤＲＲに改良を加えたアルゴリズムを用いてスケジューラ１３により取得される送信要求にあたる。

スケジューラ１３は、このＸを入力として次にサービスする内部キュー２３２、すなわち次にパケットを出力させる内部キュー２３２を選択する。

送信要求Ｘに対するスケジューラ１３からのパケットを出力させる内部キュー２３２を示す応答をＹとする。また、１段目の優先度選択の対象となりうる内部キュー２３２を４ビットの２進数表記で表すパラメータをＳとする。例えば、Ｓ＝４’ｂ０１１１と表される。ここで、Ｗ’ｂｎｎｎｎは、ｎが２進数であり、Ｗビットの２進数表記を表すものとする。すなわち、Ｓは、ｎｎｎｎの部分で後ろから順に内部キュー＃０，１，２，３を表し、優先度選択の対象となりうる内部キュー２３２に対応する値が１となる。例えば、Ｓ＝４’ｂ０１１１であれば、内部キュー＃１〜＃３が１段目の選択の対象となる内部キュー２３２である。以下では、優先度選択の対象となりうる内部キュー２３２を、「１段目内部キュー２３２」という。また、優先度選択候補の内部キュー２３２以外の内部キュー２３２を、「２段目内部キュー２３２」という。

スケジューラ１３は、１段目内部キュー２３２を表す情報Ｓを制御部１４から取得する。スケジューラ１３は、送信要求Ｘに対するパケットを出力させる内部キュー２３２を示す応答Ｙとして、Ｙ＝（Ｋ＆Ｓ）？ＳＰ（Ｘ１）：Ｋという応答を返す。ここで、Ｘ１＝Ｘ＆Ｓである。「＆」は、論理積を表す。すなわち、Ｘ１は、１段目内部キュー２３２で、且つ送信可能なパケットがある内部キュー２３２を示す。例えば、Ｘ１＝０は、１段目内部キュー２３２が無いことを示す。また、Ｘ２＝Ｘ＆ＮＯＴ（Ｓ）である。「ＮＯＴ（Ｓ）」は、Ｓを反転したものを表し、例えば、ＮＯＴ（４’ｂ０１１１）＝４’ｂ１０００である。すなわち、Ｘ２は、２段目内部キュー２３２を表す。Ｘ２＝０であれば、１段目内部キュー２３２しかないことになる。また、Ｃ＝（Ｘ１）？ＳＰ（Ｓ）：０である。（Ｘ１）？ＳＰ（Ｓ）：０は、三項演算子を表し、Ｘ１≠０のときは、Ｃ＝ＳＰ（Ｓ）であり、Ｘ１＝０のときは、Ｃ＝０となる。また「｜」は、論理和を表す。さらに、Ｋ＝ＲＲ（Ｃ｜Ｘ２）である。「ＳＰ」及び「ＲＲ」については後で説明する。スケジューラ１３は、ＫとＳの論理積が０でなければ、Ｙ＝ＳＰ（Ｘ１）を応答として返し、ＫとＳの論理積が０であれば、Ｙ＝ＲＲ（Ｃ｜Ｘ２）を返す。

ここで、ＳＰ（Ｘ）はＸの中から最も優先度の高い内部キュー２３２を選択する関数である。例えば、Ｙ＝ＳＰ（Ｘ）とした場合、Ｙ［０］＝Ｘ［０］，Ｙ［１］＝ＮＯＴ（Ｘ［０］）＆Ｘ［１］，Ｙ［２］＝ＮＯＴ（Ｘ［０］）＆ＮＯＴ（Ｘ［１］）＆Ｘ［２］，Ｙ［３］＝ＮＯＴ（Ｘ［０］）＆ＮＯＴ（Ｘ［１］）＆ＮＯＴ（Ｘ［２］）＆Ｘ［３］となる。ここで、Ｙ［０］〜［３］は、スケジューラ１３からの応答であれば、それぞれ内部キュー＃０〜＃３への応答である。すなわち、スケジューラ１３は、値が１の内部キュー２３２にパケットを出力させ、値が０の内部キュー２３２にはパケットを出力させない。この場合、ＳＰ（Ｘ１）は、内部キュー＃０の優先度を最も高くし、内部キュー＃１，＃２，＃３の順に優先度を低くして、スケジューラ１３は、優先度の高い順に内部キュー２３２を選択する。

さらに、ＳＰ（Ｓ）は、１段目内部キュー２３２全てを対象として優先度の最も高い内部キュー２３２を選択することを表す。

また、Ｙ＝ＲＲ（Ｘ）は、以下に示す関数である。Ｙ＝Ｃ１｜Ｃ２であり、Ｃ１＝ＳＰ（Ｘ１１），Ｃ２＝（ＳＰ（Ｘ１１）＝＝０）？ＳＰ（Ｘ２２）：０である。ここで、「＝＝」は、左辺と右辺を比較し、等しいときは１となり等しくないときは０となる。そして、Ｘ１１＝Ｘ＆Ｒ１，Ｒ１＝ＮＥＸＴ（Ｒ）である。ここで、Ｒは、前回の結果を４’ｂｎｎｎｎで表した値であり、「ＮＥＸＴ」は、図１１で表される関数である。図１１は、関数「ＮＥＸＴ」を説明するための図である。さらに、Ｘ２２＝Ｘ＆Ｒ２，Ｒ２＝ＮＯＴ（Ｒ１）である。すなわち、Ｘ１１は、Ｒ１の中で送信要求のあるものを表す。また、Ｘ２２は、Ｒ２の中で送信要求のあるものを表す。

すなわち、スケジューラ１３は、内部キュー２３２の内前回パケットを出力させたものより番号が大きい内部キュー２３２のグループと、前回パケットを出力させたもの以下の番号の内部キュー２３２のグループに分け、それぞれで優先度が高いものを選択する。そして、前回パケットを出力させた内部キュー２３２を含まないグループの内部キュー２３２を優先して選択する。その後、スケジューラ１３は、前回のＹ＝ＲＲ（Ｘ）で得られた結果をＲとして保持し、次の選択時に使用する。

まとめると、スケジューラ１３は、ＳＰ（Ｘ１）を優先度選択として、１段目内部キュー２３２の中から優先度の高い内部キュー２３２を選択する。さらに、スケジューラ１３は、関数ＲＲで、優先度選択で選ばれた内部キュー２３２と２段目内部キュー２３２との間でラウンドロビン選択を行う。そして、スケジューラ１３は、ラウンドロビン選択までを行った場合の選択結果が、１段目内部キュー２３２であれば、優先度選択で選ばれた内部キュー２３２をパケットを出力する内部キュー２３２として選択させる。これに対して、ラウンドロビン選択を行った場合の選択結果が、１段目内部キュー２３２でなければ、ラウンドロビン選択で選ばれた内部キュー２３２をパケットを出力する内部キュー２３２として選択させる。これにより、スケジューラ１３は、優先度の高い内部キュー２３２を優先度選択で選択し、その選択された内部キュー２３２と２段目内部キュー２３２との間でラウンドロビンを用いてパケットを出力する内部キュー２３２を選択する。

ここで、以上の説明は、内部キュー＃０が最優先であり、＃１〜＃３の順で優先度が低い場合のスケジューリングである。しかし、実際には、優先度がキュー番号の順番になるとは限らない。そこで、スケジューラ１３は、優先度に応じて以下の論理で組み替えを行う。

例えば、送信キュー２３が内部キュー２３２を４つ有する場合、スケジューラ１３は、Ｙ＝ＸＣＨＧ（Ｘ，Ｐ０，Ｐ１，Ｐ２，Ｐ３）として優先度に応じた組み換えを行う。ここで、Ｘは、送信要求である。また、Ｐ０〜３は、それぞれ各内部キュー＃０〜＃３の優先度を４ビットの２進数表記で表した値である。４ビットの内の右側のビットほど優先度が高いことを表す。例えば、Ｐ０＝４‘ｂ００１０，Ｐ１＝４‘ｂ０１００，Ｐ２＝４‘ｂ１０００，Ｐ３＝４‘ｂ０００１であれば、内部キュー＃３の優先度が最も高いことを表す。また、以下では、Ｐｎ［ｋ］は、Ｐｎの右からｋ番目のビットを表す。

そして、Ｙ［０］＝Ｘ［０］＆Ｐ０［０］｜Ｘ［１］＆Ｐ０［１］｜Ｘ［２］＆Ｐ０［２］｜Ｘ［３］＆Ｐ０［３］となる。また、Ｙ［１］＝Ｘ［０］＆Ｐ１［０］｜Ｘ［１］＆Ｐ１［１］｜Ｘ［２］＆Ｐ１［２］｜Ｘ［３］＆Ｐ１［３］となる。また、Ｙ［２］＝Ｘ［０］＆Ｐ２［０］｜Ｘ［１］＆Ｐ２［１］｜Ｘ［２］＆Ｐ２［２］｜Ｘ［３］＆Ｐ２［３］となる。また、Ｙ［３］＝Ｘ［０］＆Ｐ３［０］｜Ｘ［１］＆Ｐ３［１］｜Ｘ［２］＆Ｐ３［２］｜Ｘ［３］＆Ｐ３［３］となる。

すなわち、スケジューラ１３は、上記関数で優先度に合わせてビットの順番を入れ替え、優先度が高い内部キュー２３２の順に４ビットの左側から送信要求が並ぶように変更する。そして、スケジューラ１３は、順番を入れ替えた送信要求を用いてパケットを出力させる内部キュー２３２を選択する。その後、スケジューラ１３は、上記関数を用いて元の状態にビットの順番を入れ替える。そして、スケジューラ１３は、元の状態に入れ替えたビットの状態を用いてマルチプレクサ２３３に内部キュー２３２を選択させる。

次に、図１２を参照して、本実施例に係るスイッチのフローグループの分割時のパケットの出力について説明する。図１２は、実施例２に係るスイッチのフローグループ分割時のパケットの出力を説明するための図である。図１２の状態３１１は、分割前の状態を表す。状態３１２は、分割中の状態を表す。状態３１３は、分割後の状態を表す。

状態３１１では、分割前であるので、スケジューラ１３は、優先度選択は行わず、ラウンドロビン選択のみを行う。状態３１１では、フローグループＦＧ１にフローＡ及びフローＢが属する。そして、フローグループＦＧ１に割り当てられた内部キュー２３２が、フローＡのパケットＡ１及びフローＢのパケットＢ１を格納する。また、フローグループＦＧ２にフローＣが属する。そして、フローグループＦＧ２に割り当てられた内部キュー２３２は、フローＣのパケットＣ１及びＣ２を格納する。

状態３１１の状態で、制御部１４がフローグループＦＧ１の分割を開始する。この場合、制御部１４は、新たにフローＡが属するフローグループＦＧ３及びフローＢが属するフローグループＦＧ４を作成する。そして、送信キュー２３は、状態３１２に遷移する。状態３１２では、マルチプレクサ２３３Ａが、優先度選択を行い、マルチプレクサ２３３Ｂが、ラウンドロビン選択を行う。フローグループＦＧ３は、新たに入力されたフローＡのパケットＡ２を格納する。また、フローグループＦＧ４は、新たに入力されたフローＢのパケットＢ２を格納する。制御部１４は、分割前のフローグループＦＧ１の優先度を、分割後のフローグループＦＧ３及びＦＧ４より高くする。

スケジューラ１３は、フローグループＦＧ１、ＦＧ３及びＦＧ４の中で、最も優先度の高いフローグループに割り当てられた内部キュー２３２をマルチプレクサ２３３Ａに選択させる。この場合、フローグループＦＧ１に割り当てられた内部キュー２３２の優先度が高いので、マルチプレクサ２３３Ａは、フローグループＦＧ１の中のパケットがなくなるまでフローグループＦＧ１に割り当てられた内部キュー２３２を選択する。これにより、送信キュー２３から出力されるパケットの順番が入力された順番に維持される。さらに、スケジューラ１３は、マルチプレクサ２３３Ａが選択した内部キュー２３２及びフローグループＦＧ２に割り当てられた内部キュー２３２の中からラウンドロビン選択によりマルチプレクサ２３３Ｂに内部キュー２３２を選択させる。そして、マルチプレクサ２３３Ｂは、選択した内部キュー２３２からパケットを取得し送信ポート２４へ出力する。例えば、マルチプレクサ２３３Ａが選択した内部キュー２３２の選択からラウンドロビンが始まる場合、マルチプレクサ２３３Ｂは、パケットＡ１、Ｃ１、Ｂ１の順でパケットを出力する。

パケットＡ１及びＢ１が出力されフローグループＦＧ１のパケットが無くなると、制御部１４は、フローグループＦＧ１を削除し、フローグループＦＧ１に割り当てられていた内部キュー２３２を未使用の状態にする。これにより、送信キュー２３は、状態３１３に遷移する。フローグループの分割が終了したので、スケジューラ１３は、フローグループＦＧ２〜ＦＧ４の中でのラウンドロビン選択のみをマルチプレクサ２３３に行わせる。

このように、スケジューラ１３は、優先度選択及びラウンドロビン選択を組み合わせたスケジューリングを行うことで、パケットの順序を反転させることなくフローグループの分割を実現することができ、パケット送信の公平性を維持することができる。

次に、図１３を参照して、本実施例に係るスイッチ１のフローグループの結合時のパケットの出力について説明する。図１３は、実施例２に係るスイッチのフローグループ結合時のパケットの出力を説明するための図である。図１３の状態３２１は、結合前の状態を表す。状態３２２は、結合中の状態を表す。状態３２３は、結合後の状態を表す。

状態３２１では、結合前であるので、スケジューラ１３は、優先度選択は行わず、ラウンドロビン選択のみを行う。状態３２１では、フローグループＦＧ１にフローＡが属し、フローグループＦＧ２にフローＢが属し、フローグループＦＧ３にフローＣが属する。そして、フローグループＦＧ１に割り当てられた内部キュー２３２が、フローＡのパケットＡ１を格納する。フローグループＦＧ２に割り当てられた内部キュー２３２が、フローＢのパケットＢ１を格納する。また、フローグループＦＧ３に割り当てられた内部キュー２３２は、フローＣのパケットＣ１及びＣ２を格納する。

状態３２１の状態で、制御部１４がフローグループＦＧ１及びＦＧ２の結合を開始する。この場合、制御部１４は、新たにフローＡ及びＢが属するフローグループＦＧ４を作成する。そして、送信キュー２３は、状態３２２に遷移する。状態３２２では、マルチプレクサ２３３Ａが、優先度選択を行い、マルチプレクサ２２３Ｂが、ラウンドロビン選択を行う。フローグループＦＧ４は、新たに入力されたフローＡのパケットＡ２及びフローＢのパケットＢ２を格納する。制御部１４は、結合前のフローグループＦＧ１及びＦＧ２の優先度を、結合後のフローグループＦＧ４より高くする。

スケジューラ１３は、フローグループＦＧ１、ＦＧ２及びＦＧ４の中で、最も優先度の高いフローグループに割り当てられた内部キュー２３２をマルチプレクサ２３３Ａに選択させる。この場合、フローグループＦＧ１及びＦＧ２に割り当てられた内部キュー２３２の優先度が高いので、マルチプレクサ２３３Ａは、フローグループＦＧ１及びＦＧ２の中のパケットがなくなるまでフローグループＦＧ１及びＦＧ２に割り当てられた内部キュー２３２を順次選択する。これにより、送信キュー２３から出力されるパケットの順番が入力された順番に維持される。さらに、スケジューラ１３は、マルチプレクサ２３３Ａが選択した内部キュー２３２及びフローグループＦＧ３に割り当てられた内部キュー２３２の中からラウンドロビン選択によりマルチプレクサ２３３Ｂに内部キュー２３２を選択させる。そして、マルチプレクサ２３３Ｂは、選択した内部キュー２３２からパケットを取得し送信ポート２４へ出力する。例えば、マルチプレクサ２３３Ａが選択した内部キュー２３２の選択からラウンドロビンの選択が始まる場合、マルチプレクサ２３３Ｂは、パケットＡ１、Ｃ１、Ｂ１の順でパケットを出力する。

パケットＡ１及びＢ１が出力されフローグループＦＧ１及びＦＧ２のパケットが無くなると、制御部１４は、フローグループＦＧ１及びＦＧ２を削除し、フローグループＦＧ１及びＦＧ２に割り当てられていた内部キュー２３２を未使用の状態にする。これにより、送信キュー２３は、状態３２３に遷移する。フローグループの結合が終了したので、スケジューラ１３は、フローグループＦＧ３及びＦＧ４の中でのラウンドロビン選択のみをマルチプレクサ２３３に行わせる。

このように、スケジューラ１３は、優先度選択及びラウンドロビン選択を組み合わせたスケジューリングを行うことで、パケットの順序を反転させることなくフローグループの結合を実現することができ、パケット送信の公平性を維持することができる。

次に、図１４を参照して、本実施例に係るスケジューラ１３による送信要求を取得する内部キュー２３２の決定の流れについて説明する。図１４は、実施例２に係るスケジューラによる送信要求を取得する内部キューの決定のフローチャートである。

スケジューラ１３は、各内部キュー２３２の１ラウンドの送出可能量を制御情報送受信部１１から取得する。また、スケジューラ１３は、制御部１４によって変更される内部キュー２３２の重みをスケジューリングパラメータ１２５から取得する。次に、スケジューラ１３は、内部キュー２３２の１ラウンドの送出可能量に内部キュー２３２の重みを乗算する。そして、スケジューラ１３は、算出した値をカウンタ値としてスケジューラ１３のカウンタの領域に設定することで、キューの重みに応じたカウンタ値を内部キュー２３２のそれぞれに対して設定する（ステップＳ１０１）。以下では、スケジューリングの対象とする送信キュー２３が有する内部キュー２３２に連続する番号を振り、その番号をｑとして表す。また、番号ｑの内部キュー２３２に設定したカウンタ値をＣｑとする。

次に、スケジューラ１３は、パケットの出力を指示する送信キュー２３が有する内部キュー２３２の中から未選択の内部キュー２３２を抽出する（ステップＳ１０２）。

次に、スケジューラ１３は、抽出した内部キュー２３２において番号ｑの内部キュー２３２にパケットが格納されており、且つ、カウンタ値Ｃｑが０より大きいかを判定する（ステップＳ１０３）。番号ｑの内部キュー２３２の全てにパケットが格納されていない、又は、全てのカウンタ値Ｃｑ≦０の場合（ステップＳ１０３：否定）、スケジューラ１３は、ステップＳ１０７へ進む。

これに対して、番号ｑの内部キュー２３２にパケットが格納されており、且つ、カウンタ値Ｃｑが０より大きい場合（ステップＳ１０３：肯定）、スケジューラ１３は、パケットを格納し、且つカウンタ値Ｃｑが０より大きい内部キュー２３２から送信要求を取得する（ステップＳ１０４）。

次に、スケジューラ１３は、送信要求を取得した内部キュー２３２の中からパケットを出力する内部キュー２３２を選択する（ステップＳ１０５）。

そして、スケジューラ１３は、選択した内部キュー２３２からのパケットの出力をマルチプレクサ２３３に指示する。マルチプレクサ２３３は、スケジューラ１３から指示された内部キュー２３２からパケットを取得し、送信ポート２４へ出力する。また、スケジューラ１３は、平均パケット長をスケジューリングパラメータ１２５から取得する。そして、スケジューラ１３は、スケジューリングパラメータ１２５におけるパケットを出力させた内部キュー２３２のカウンタ値から平均パケット長を減算する（ステップＳ１０６）。

その後、スケジューラ１３は、送信キュー２３に含まれる内部キュー２３２の内、選択されていない内部キュー２３２があるか否かを判定する（ステップＳ１０７）。選択されていない内部キュー２３２がある場合（ステップＳ１０７：肯定）、スケジューラ１３は、ステップＳ１０２へ戻る。

これに対して、送信キュー２３に含まれる全ての内部キュー２３２の選択が終わった場合（ステップＳ１０７：否定）、スケジューラ１３は、パケットが存在する内部キュー２３２のカウンタ値が全て０以下か否かを判定する（ステップＳ１０８）。パケットが存在する内部キュー２３２の中でカウンタ値が０より大きいものが存在する場合（ステップＳ１０８：否定）、スケジューラ１３は、内部キュー２３２の未選択の状態に戻る（ステップＳ１０９）。その後、スケジューラ１３は、ステップＳ１０２へ戻る。

これに対して、パケットが存在する内部キュー２３２のカウンタ値が全て０以下の場合（ステップＳ１０８：肯定）、スケジューラ１３は、パケットの出力処理を終了する。

次に、図１５を参照して、本実施例に係るスケジューラ１３によるパケットを出力させる内部キュー２３２の決定手順について説明する。図１５は、実施例２に係るスケジューラによるパケットを出力させる内部キューの決定のフローチャートである。ここで、図１５に記載したフローは、図１４におけるステップＳ１０５で実施される処理の一例にあたる。

スケジューラ１３は、１段目内部キュー２３２であることを示す情報Ｓの入力を制御部１４から受ける（ステップＳ２０１）。

次に、スケジューラ１３は、上述したＸＣＨＧ関数を用いて、優先度に合わせて送信要求の順番を組み換える（ステップＳ２０２）。

次に、スケジューラ１３は、１段目内部キュー２３２が有るか否かを判定する（ステップＳ２０３）。１段目内部キュー２３２が無い場合（ステップＳ２０３：否定）、スケジューラ１３は、２段目内部キュー２３２に対してラウンドロビン選択を行う（ステップＳ２０５）。その後、スケジューラ１３は、ステップＳ２０９へ進む。

これに対して、１段目内部キュー２３２がある場合（ステップＳ２０３：肯定）、スケジューラ１３は、１段目内部キュー２３２に対して優先度選択を行う（ステップＳ２０４）。

次に、スケジューラ１３は、２段目内部キュー２３２があるか否かを判定する（ステップＳ２０６）。２段目内部キュー２３２が無い場合（ステップＳ２０６：否定）、スケジューラ１３は、優先度選択で選択された内部キュー２３２を選択する（ステップＳ２０７）。その後、スケジューラ１３は、ステップＳ２０９へ進む。

これに対して、２段目内部キュー２３２がある場合（ステップＳ２０６：肯定）、スケジューラ１３は、優先度選択で選択された内部キュー２３２と２段目内部キュー２３２とでラウンドロビン選択を行う（ステップＳ２０８）。

その後、スケジューラ１３は、上述したＸＣＨＧ関数を用いて優先度により組み換えた送信要求の順序を元に戻す（ステップＳ２０９）。

そして、スケジューラ１３は、マルチプレクサ２３３に対して、選択した内部キュー２３２からパケットを送信させる（ステップＳ２１０）。

以上に説明したように、本実施例に係るスケジューラは、ＤＲＲを改良したアルゴリズムを用いて送信要求を取得する内部キューを決定する。その後、スケジューラは、送信要求を出力した内部キューの中から優先度選択及びラウンドロビン選択を用いてパケットを出力させる内部キューを決定する。これにより、パケットを出力する内部キューが順次変更されるため、１つの内部キューから連続してパケットが出力される状態を抑制でき、スイッチからのパケットの入力先となる受信機側の負荷を低減することができる。

そして、受信機側の負荷を低減することで、受信機側のバッファ資源の枯渇の防止や、受信機におけるスイッチングや受信性能不足の問題の低減に寄与することができる。

また、以上では、送信要求を取得する内部キューの決定に、ＤＲＲに改良を加えたアルゴリズムを用いたが、この送信要求の取得は、ある程度受信側の負荷が高くなるのを許容できるのであれば、例えば、従来のＷＲＲやＤＲＲなどを用いてもよい。その場合、スケジューラは、ＷＲＲやＤＲＲなどのアルゴリズムを用いて決定した送信要求を取得する内部キューに対して、本実施例で説明した優先度選択及びラウンドロビン選択を用いることで、受信機側の負荷をある程度低減することができる。

１ スイッチ
２ 管理用サーバ
１１ 制御情報送受信部
１２ 記憶部
１３ スケジューラ
１４ 制御部
１５ 送信側メータカウンタ
１６ キュー選択部
１７ 受信側メータカウンタ
１８ フロー識別部
２１ 受信ポート
２２ スイッチング部
２３ 送信キュー
２４ 送信ポート
１２１ フロー管理情報
１２２ フロー情報
１２３ フローグループ情報
１２４ ポリシー情報
１２５ スケジューリングパラメータ
２３１ デマルチプレクサ
２３２ 内部キュー
２３３ マルチプレクサ

Claims (6)

1. パケットを受信して格納し、格納したパケットをそれぞれ出力する複数のキューと、
   各前記キューにおけるパケットの送受信情報を取得する情報取得部と、
   前記情報取得部により取得された前記送受信情報を基に、１つまたは複数のフローが属するフローグループを作成し、前記フローグループ毎に前記キューを割り当て、特定のフローグループに属するフロー毎のパケットの送信量と予め決められたバンド幅との差が大きくなった場合、前記特定のフローグループを分割し、分割後のフローグループに前記キューを割り当てるグルーピング部と、
   前記情報取得部により取得された前記送受信情報及び予め決められた前記キューの優先度を基に、各前記キューの出力順を決定する第１スケジューリング部と
   を備えたことを特徴とするスイッチ装置。
2. 前記グルーピング部は、前記特定のフローグループに対して分割後のフローグループを複数生成し、生成した分割後のフローグループに前記キューを割り当て、
   前記第１スケジューリング部は、前記特定のフローグループに割り当てられた第１キューに格納されたパケットを全て出力した後に、前記分割後のフローグループのそれぞれに割り当てられた第２キューからパケットを出力するように出力順を決定することを特徴とする請求項１に記載のスイッチ装置。
3. 前記第１スケジューリング部及び指定されたキューの中からラウンドロビンでパケットを出力させるキューを選択する第２スケジューリング部を備えたスケジューラを有し、
   前記スケジューラは、前記分割前には前記第２スケジューリング部にキューの選択を行わせ、前記分割後には前記第１キュー及び前記第２キューの中から予め決められた優先順位にしたがってキューの選択を前記第１スケジューリング部に行わせ、且つ、前記第１キュー及び前記第２キュー以外のキューと前記第１スケジューリング部により選択されたキューとの中からラウンドロビンによるキューの選択を前記第２スケジューリング部に行わせて、選択されたキューからパケットを出力させると決定する
   ことを特徴とする請求項２に記載のスイッチ装置。
4. 前記送受信情報を基に、キュー毎の重みを計算する重み計算部をさらに備え、
   前記第１スケジューリング部は、キュー毎に残量カウンタを有し、前記重み計算部により算出されたキューの重みにしたがって残量カウンタの値を設定し、前記キュー毎にパケットをそれぞれ送信させ、パケットを送信したキューに対応する前記残量カウンタから送信済みのパケットのパケットサイズをそれぞれ減算し、残量カウンタが０以下になったキューからのパケットの送信を停止させ、全てのキューの残量カウンタが０になるまで出力が停止されていないキューからのパケットの出力を行うことを特徴とする請求項１〜３のいずれか一つに記載のスイッチ装置。
5. 前記グルーピング部は、前記分割を行った場合に、各前記フローグループに割り当てるキューの数が所定数を超えてしまう場合、パケットの送信量が小さいフローグループを選択し結合することを特徴とする請求項１〜４のいずれか一つに記載のスイッチ装置。
6. パケットを受信して格納し、格納したパケットをそれぞれ出力する複数のキューにおけるパケットの送受信情報を取得し、
   取得した前記送受信情報を基に、１つまたは複数のフローが属するフローグループを作成し、
   生成した前記フローグループ毎に前記キューを割り当て、
   特定のフローグループに属するフロー毎のパケットの送信量と予め決められたバンド幅との差が大きくなった場合、前記特定のフローグループを分割し、分割後のフローグループに前記キューを割り当て、
   前記送受信情報及び予め決められた前記キューの優先度を基に、各前記キューの出力順を決定する
   ことを特徴とするスイッチ装置の制御方法。

Images