JP6895354B2 - 通信中継装置 - Google Patents

Description

本発明は、通信中継装置に関する。

近年、動画や音声といった電子的なコンテンツをネットワーク経由でリアルタイム配信する、いわゆるストリーミング技術が普及している。かかるストリーミングをインターネット経由で実現する場合、多数のユーザ間で同一の回線が共用される。このため、帯域あたりのコストが低く抑えられる。

一方で、通信パケットの廃棄量を抑制することにより、通信品質（ＱｏＳ：Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）が確保される。このようなことから、インターネットに接続する中継装置はシェーパを搭載し、一度に多量に送信されるデータを一定レートに平準化して転送する技術が知られている。

特許文献１には、ユーザやサービスに対応したフロー条件を予め構成定義情報として設定しておき、受信した通信パケットを、フローごとに用意したキューに一旦蓄積して、予め定めたシェーピング条件（送出帯域値や優先度）に基づいて通信パケットの転送を行う技術が開示されている。

特開平１１−３４６２４６号公報

しかしながら、特許文献１の技術は、ユーザやサービスごとにフローを設定する必要があるため、多数のユーザやサービスに対応することが困難である。たとえば、数百万のユーザごとにフローを設定する場合、キューの数をユーザ数と同一数分確保することは困難である。仮に、ユーザ数と同一数分のキューを確保できたとしても、アクティブ率の低いユーザのキューを確保することは非効率である。

本発明は、キュー数以上のフローを収容しつつ、かつ通信品質を守ることを目的とする。

上述の課題を解決するため、本発明に係る代表的な通信装置は、パケットを中継する通信中継装置であって、パケットを受信し、受信したパケットを出力する受信部と、前記受信部が出力したパケットをハッシュ値に変換し、ハッシュ値とキューとの対応関係にしたがい、変換されたハッシュ値に基づいて、前記受信部が出力したパケットを複数のキューに振り分ける振分部と、前記振分部により振り分けられたパケットを複数のキューに格納するバッファと、前記バッファの複数のキューそれぞれに関する状態の情報を蓄積する学習部と、前記学習部が蓄積したキューそれぞれに関する状態の情報に基づいて、キューに複数のハッシュ値が対応する関係の情報を作成し、前記振分部へ送る学習結果処理部と、 前記バッファに格納されたパケットを送信する送信部とを有することを特徴とする。

本発明によれば、キュー数以上のフローを収容しつつ、かつ通信品質を守ることができる。前述した以外の課題、構成および効果は、以下の実施例の説明により明らかにされる。

通信システムの一例を示す図である。 ルータの構成例を示すブロック図である。 振分部の構成例を示す図である。 学習部の構成例を示す図である。 学習結果処理部の構成例を示す図である。 学習結果処理部による作成処理手順の例を示すフローチャートである。 学習結果処理部による更新処理手順の例を示すフローチャートである。

＜システム構成例＞
図１は、通信システムの一例を示す図である。通信システム１００は、たとえば、動画などのコンテンツをストリーミングによってユーザに提供するネットワークシステムである。図示するように、通信システム１００は、サーバ１１１、１１２と、中継装置であるルータ１２０、１４０、１６１〜１６３と、ユーザの端末であるパーソナルコンピュータ１７１〜１７３とを備えている。

サーバ１１１、１１２は、コンテンツを提供するサーバであり、各種コンテンツを記憶する。サーバ１１１、１１２は、ルータ１２０に直接的に接続されている。なお、ルータ１２０に接続されるサーバの数は、説明を簡単にするために２台として示しているが、３台以上であってもよい。

ルータ１２０は、ネットワーク１３０に接続される。ネットワーク１３０は、たとえば、インターネットである。ただし、ネットワーク１３０の種類は、特に限定されるものではなく、専用回線などのＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）であってもよいし、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）であってもよい。

また、ルータ１４０も、ネットワーク１３０に接続される。サーバ１１１、１１２、ルータ１２０、１４０は、たとえば、コンテンツ配信サービスを行うＩＳＰ（Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅ Ｐｒｏｖｉｄｅｒ）により設置される。

ルータ１４０は、家庭１５１〜１５３のそれぞれに設置されたルータ１６１〜１６３を介して、パーソナルコンピュータ１７１〜１７３にそれぞれ接続される。ルータ１４０とルータ１６１〜１６３との間には、他の中継装置や集線装置が介在してもよい。

パーソナルコンピュータ１７１〜１７３は、ユーザの端末であって、汎用のパーソナルコンピュータであるが、これに限定されるものではなく、ルータ１６１〜１６３に接続される端末は、サーバ１１１、１１２の配信するコンテンツを利用可能なコンピュータであればよく、たとえば、ネットワーク対応テレビなどであってもよい。

また、ルータ１６１〜１６３のそれぞれには、図示しない複数の端末が接続されていてもよい。また、ルータ１４０は、説明を簡単にするために、家庭１５１〜１５３のネットワークに接続されるものとしたが、実際には、たとえば、数千や数万の家庭のネットワークに接続される。

通信システム１００において、サーバ１１１、１１２は、パーソナルコンピュータ１７１〜１７３から、コンテンツの利用要求を受け付けると、利用要求されたコンテンツを、利用要求元のパーソナルコンピュータ１７１〜１７３に向けて、パケットで配信する。

ルータ１２０、１４０は、サーバ１１１、１１２が配信するパケットを受信すると、それぞれのパケットを一旦バッファに蓄積し、平準化してパーソナルコンピュータ１７１〜１７３に向けて転送する。パーソナルコンピュータ１７１〜１７３は、ルータ１６１〜１６３を介して転送されたパケットを受信し、予めインストールされたアプリケーションで利用する。

サーバ１１１、１１２からパーソナルコンピュータ１７１〜１７３に向けて配信されるパケットは、たとえば宛先となるパーソナルコンピュータ１７１〜１７３の３台それぞれに応じた通信の３つのフローとなる。ただし、フローはこれに限定されるものではなく、他の情報に基づいて識別されるフローであってもよい。

＜ルータの構成例＞
図２は、ルータの構成例を示すブロック図である。なお、図１に示したルータ１２０、１４０は、本実施例においては同一構成であるので、以下では、特に断る場合を除いて、ルータ１２０の構成について説明する。

ルータ１２０は、受信部２０１、振分部２０２、学習部２０３、バッファ２０４、帯域制御部２０５、送信部２０６、および学習結果処理部２０７を備えている。

受信部２０１は、外部からパケット２５０ｒ−１〜２５０ｒ−ｆ（ｆは２以上の任意の整数）を受信するインタフェースである。本実施例では、受信部２０１は、２つの物理ポート（不図示）を備える。この２つの物理ポートには、サーバ１１１、１１２が接続される。

受信部２０１は、サーバ１１１、１１２からパケット２５０ｒ−１〜２５０ｒ−ｆを受信して、振分部２０２に出力する。なお、受信部２０１は、３つ以上の物理ポートを備えていてもよい。この場合、受信部２０１は、３台以上のサーバが接続されてもよい。

パケット２５０ｒ−１〜２５０ｒ−ｆのそれぞれは、フロー２６０ｒ−１〜２６０ｒ−ｆに属するパケットである。このため、ｆはフローの数であって、パケット２５０ｒ−１〜２５０ｒ−ｆが配信される宛先のパーソナルコンピュータの数であってもよい。また、パケット２５０ｒ−１〜２５０ｒ−ｆのそれぞれは、ヘッダ２５１ｒ−１〜２５１ｒ−ｆを含む。

受信部２０１から振分部２０２へ出力されるパケットは、受信済みであり、ルータ１２０の内部の情報であるので、内部の情報であることを示すためにパケット２５０と表記するが、パケット２５０の内容はパケット２５０ｒ−１〜２５０ｒ−ｆの任意の１つと同じである。また、これに対応して、ルータ１２０の内部では、フロー２６０ｒ−１〜２６０ｒ−ｆをフロー２６０と表記し、ヘッダ２５１ｒ−１〜２５１ｒ−ｆをヘッダ２５１と表記する。

振分部２０２は、受信部２０１から入力したパケット２５０を、バッファ２０４に確保されたキュー２１４−１〜２１４−ｎ（ｎは２以上の任意の整数、キュー２１４−１〜２１４−ｎを区別しない場合は、キュー２１４と表記する）のいずれかへ振り分ける。

ここで、キュー２１４−１〜２１４−ｎのそれぞれは、キューポインタであるＱｐ１〜Ｑｐｎで指される。ただし、Ｑｐ１〜Ｑｐｎは、キュー２１４−１〜２１４−ｎへアクセス可能に特定する情報であれば、キュー２１４−１〜２１４−ｎそれぞれの名称や識別子であってもよい。

具体的な振り分けの処理として、たとえば、振分部２０２は、パケット２５０のヘッダ２５１に含まれているヘッダ情報を、所定のハッシュ関数によりハッシュ値へ変換し、パケット２５０をハッシュ値に対応したキュー２１４に振り分ける。

このために、振分部２０２は、変換部２２１とハッシュ値テーブル２２２とを有する。変換部２２１は、パケット２５０のヘッダ２５１に含まれているヘッダ情報をハッシュ関数に与えてハッシュ値Ｈに変換する。

ハッシュ関数に与えられる情報は、パケット２５０のヘッダ２５１に含まれるヘッダ情報であって、たとえば、ＭＡＣヘッダなどのレイヤ２ヘッダ、ＩＰｖ４ヘッダやＩＰｖ６ヘッダなどのレイヤ３ヘッダおよびＴＣＰヘッダやＵＤＰヘッダなどのレイヤ４ヘッダのいずれかまたは複数のフィールドが使用されてもよい。

使用されるフィールドの選択は、装置固定（ルータ１２０に予め設定されて固定）であってもよいし、装置運用者が指定可能であってもよい。ただし、サーバ１１１、１１２からパーソナルコンピュータ１７１〜１７３へ向けて配信される通信のフロー２６０を識別できる情報を含むフィールドが選択されることが好ましく、パーソナルコンピュータ１７１〜１７３の宛先アドレスを含むフィールドが選択されることが好ましい。

ハッシュ値テーブル２２２は、変換部２２１から得られたハッシュ値Ｈと、バッファ２０４のキュー２１４とを対応付けるためのテーブルである。たとえば、ハッシュ値ＨがＨ１の場合、対応するキュー２１４はＱｐ１といったキューポインタの情報が格納される。

ハッシュ値テーブル２２２のキューポインタの情報は、書き換え可能であり、学習結果処理部２０７からの指示により変更することができる。なお、振分部２０２は、たとえば、集積回路により実現される。この場合のハッシュ値テーブル２２２は、集積回路内のメモリに格納される。

学習部２０３は、振分部２０２によって、ハッシュ値に対応する複数のキュー２１４に振り分けられたパケット２５０を監視して、どのハッシュ値のパケット２５０が、どのキュー２１４にどれだけの流量が振り分けられるかを学習する。

具体的には、たとえば、学習部２０３は、パケット２５０と共にハッシュ値ＨおよびキューポインタＱｐが入力され、ハッシュ値ＨごとにキューポインタＱｐを対象キューとして、現在キュー長およびパケット２５０の流量を監視し、学習情報として保持する。

学習部２０３は、振分部２０２による振り分けにしたがってキュー２１４にパケット２５０の情報を送出し、学習結果を学習結果処理部２０７に出力する。なお、学習部２０３は、たとえば、集積回路により実現される、または、メモリに記憶されたプログラムをプロセッサに実行させることにより実現される。

バッファ２０４は、受信部２０１が受信したパケット２５０を一時的に蓄積する記憶領域であり、複数のキュー２１４−１〜２１４−ｎを有する。本実施例では、キュー２１４−１〜２１４−ｎのそれぞれには、たとえば、同一の記憶容量が割り当てられている。

複数のキュー２１４−１〜２１４−ｎには、既に説明したように、振分部２０２が決定した振り分け結果にしたがって、それぞれのパケット２５０が格納される。なお、輻輳時には、キュー２１４−１〜２１４−ｎのいずれかの容量を超えるパケット２５０は破棄される。

たとえば、キュー２１４−ｉ（ｉは１〜ｎの中の任意の整数）にキュー２１４−ｉの容量分のパケット２５０が既に蓄積されている場合には、新たにバッファ２０４に入力されるパケット２５０は、そのキュー２１４−ｉに格納されずに破棄される。

帯域制御部２０５は、キュー２１４−１〜２１４−ｎごとに帯域を制御して、キュー２１４−１〜２１４−ｎに蓄積されたパケット２５０を送信部２０６に出力する。具体的には、たとえば、帯域制御部２０５は、予め設定された帯域制御ルールに基づいてスケジューリングを行い、キュー２１４−１〜２１４−ｎから順次にパケット２５０を読み出して、送信部２０６に出力する。なお、帯域制御部２０５は、たとえば、集積回路により実現される。

送信部２０６は、パケット２５０をルータ１２０の外部へ送信するインタフェースである。外部へ送信されたパケット２５０ｓ−１〜２５０ｓ−ｆのそれぞれの内容はパケット２５０ｒ−１〜２５０ｒ−ｆの内容と同じであり、フロー２６０ｓ−１〜２６０ｓ−ｆのそれぞれはフロー２６０ｒ−１〜２６０ｒ−ｆに対応する。

ヘッダ２５１ｓ−１〜２５１ｓ−ｆはヘッダ２５１ｒ−１〜２５１ｒ−ｆに対応するものであるが、ルータ１２０のルータとしての動作により、一部の情報が書き換えられていてもよい。

学習結果処理部２０７は、学習部２０３より学習結果を受け取り、各種処理を実行する。たとえば、学習結果処理部２０７は、学習結果を元に特定の閾値以下の流量のフローを束ねるように算出し、算出した結果を振分部２０２のハッシュ値テーブル２２２に反映する。

また、学習結果処理部２０７は、トラップまたはシステムログなどのメッセージを用いて、送信部２０６から学習結果を運用者の端末に送信したり、または、図示しない表示部に表示したりすることで、運用者に学習結果を通知する。

さらに、学習結果処理部２０７は、学習結果が登録または削除した場合、その登録または削除の情報を運用者に通知してもよい。なお、学習結果処理部２０７は、具体的には、たとえば、学習結果処理部２０７の処理を実行するためのプログラムをプロセッサに実行させることで実現される。

＜振分部２０２の構成例＞
図３は、振分部２０２の構成例を示す図である。図２でも示したように、振分部２０２は、変換部２２１とハッシュ値テーブル２２２とを有する。

変換部２２１は、パケット２５０をハッシュ関数に基づいてハッシュ値Ｈに変換する。変換部２２１が変換するハッシュ値Ｈの範囲は、装置が有するキュー２１４の数以上の範囲で変換可能とする。この例ではキュー２１４の数の２倍程度の範囲で変換可能とする。

ハッシュ値テーブル２２２は、ハッシュ値３０１とキューポインタ３０２とを有する。ハッシュ値３０１は、ハッシュ値Ｈ１〜Ｈｍ（ｍは２以上の任意の整数、ハッシュ値Ｈ１〜Ｈｍを区別しない場合は、ハッシュ値Ｈと表記する）を記憶する記憶領域である。

キューポインタ３０２は、キューポインタＱｐ１〜Ｑｐｎ（ｎはキュー２１４の数、キューポインタＱｐ１〜Ｑｐｎを区別しない場合は、キューポインタＱｐと表記する）を記憶する記憶領域である。キューポインタＱｐは、ハッシュ値Ｈとキュー２１４を結びつけるポインタの役割を行う。

具体的に、図３の例では、ハッシュ値３０１のハッシュ値Ｈ１にキュー２１４−１が対応する場合、キュー２１４−１を指すキューポインタＱｐ１がキューポインタ３０２に記憶される。

また、図３の例では、キュー２１４の数に対してハッシュ値３０１の数が２倍程度であるため、ｍはｎの２倍程度の値であり、キューポインタ３０２のたとえばキューポインタＱｐ１は、ハッシュ値３０１の２つのハッシュ値Ｈに対応している。すなわち、ハッシュ値Ｈにキュー２１４−１を結びつけるキューポインタ３０２のキューポインタＱｐ１は２つ存在することになる。

また、ハッシュ値テーブル２２２において、ハッシュ値３０１のハッシュ値Ｈにキュー２１４が結び付けられていなくてもよい。このように、いずれのキュー２１４もハッシュ値Ｈに結び付けない情報であるＮＵＬＬがキューポインタ３０２に記憶されてもよい。そして、ハッシュ値Ｈが使用される時点で、ハッシュ値Ｈにキュー２１４を結び付けるためのキューポインタＱｐが、ＮＵＬＬの代わりに記憶されてもよい。

なお、実際に通信されるフロー２６０ｒ−１〜２６０ｒ−ｆの数に対して、ハッシュ値Ｈ１〜Ｈｍの数が十分な状態であり、その状態においてハッシュ関数がコリジョンの発生しない関数である場合、１つのハッシュ値Ｈには、１つのフロー２６０のパケット２５０が変換されるため、以下で説明する１つのハッシュ値Ｈは１つのフロー２６０であるとみなされてもよい。

＜学習部２０３の詳細構成例＞
図４は、学習部２０３の構成例を示す図である。学習部２０３は、振分部２０２によって各キュー２１４に振り分けられたパケット２５０のフロー２６０に対して、ハッシュ値Ｈごとに、対象キューＱｐ、現在キュー長ＱＬ、および流量Ｒを監視および学習する。このために、学習部２０３は、パケット２５０と共にハッシュ値ＨとキューポインタＱｐを振分部２０２から入力する。

学習情報４００において、ハッシュ値４０１と対象キュー４０２のそれぞれは、振分部２０２から入力されたハッシュ値ＨとキューポインタＱｐを、その入力された対応関係のまま記憶し、その対応関係を学習部２０３が学習する。

現在キュー長４０３は、対象キュー４０２のキューポインタＱｐが指すキュー２１４内のパケット２５０であって、ハッシュ値４０１のハッシュ値Ｈに変換されたパケット２５０の数を記憶する。パケット２５０の数の代わりに、１または複数のパケット２５０のバイト数などであってもよい。

流量４０４は、対象キュー４０２のキューポインタＱｐが指すキュー２１４へ出力されるパケット２５０であって、ハッシュ値４０１のハッシュ値Ｈに変換されたパケット２５０の１秒当たりの数を記憶する。パケット２５０の数の代わりに、１または複数のパケット２５０のバイト数であってもよいし、１秒当たりの代わりに、他の期間当たりであってもよい。

また、流量４０４は、対象キュー４０２のキューポインタＱｐが指すキュー２１４から出力されるパケット２５０であって、ハッシュ値４０１のハッシュ値Ｈに変換されたパケット２５０の１秒当たりの数を記憶してもよい。このために、学習部２０３はバッファ２０４あるいは帯域制御部２０５から流量Ｒのための情報を取得してもよい。

図４の例は、対象キューＱｐ１が指すキュー２１４−１の中におけるハッシュ値Ｈ１に変換されたパケット２５０の数は現在キュー長ＱＬ１という値であり、キュー２１４−１へ出力されるハッシュ値Ｈ１に変換されたパケット２５０の１秒当たりの数は流量Ｒ１という値であることを表している。

また、ハッシュ値Ｈ７に関しては、キュー２１４が結び付けられておらず、現在キュー長４０３と流量４０４は定数Ｃである。ここで、定数Ｃは、図５を用いて説明するルールに該当しない数であることが好ましい。

学習部２０３は、振分部２０２から入力されたパケット２５０（ハッシュ値ＨとキューポインタＱｐ）ごとに監視して学習情報４００を更新することにより学習を行ってもよいし、予め設定された一定の周期ごとに振分部２０２から入力されたパケット２５０を監視して学習情報４００を更新することにより学習を行ってもよい。

＜学習結果処理部２０７の構成例＞
図５は、学習結果処理部２０７の構成例を示す図である。学習結果処理部２０７が学習部２０３から学習結果２７１を受け取り、再振分情報２７２に反映させ、振分部２０２へ送る。学習結果２７１は、図４に示した学習情報４００の学習した結果である。

学習結果処理部２０７は、学習部２０３から学習結果２７１を受け取ると、予め設定された一定のルールに基づき、ハッシュ値Ｈと対象キューのキューポインタＱｐとの対応すなわちハッシュ値Ｈとキュー２１４の結び付けを分配しなおす。

たとえば、一定のルールとして、１つのキュー２１４において現在キュー長が０で流量が３０以下となるように、ハッシュ値単位でパケットを集約すなわちフローを集約するというルールの場合、流量が既に３０を超えているハッシュ値Ｈ２と現在キューが既に１以上のハッシュ値Ｈ３は対象外となり、学習結果処理部２０７は学習結果２７１１、学習結果２７１３、および学習結果２７１４が集約可能と判定する。

その判定の結果として、学習結果２７１３と学習結果２７１４のハッシュ値Ｈ４およびハッシュ値Ｈ５を、ハッシュ値Ｈ１の対象キューであるキューポインタＱｐ１が指すキュー２１４−１と結び付けるため、学習結果処理部２０７は、再振分情報２７２にハッシュ値Ｈ４に対応する再振分情報２７２１としてキューポインタＱｐ１を対象キューに設定し、ハッシュ値Ｈ５に対応する再振分情報２７２２としてキューポインタＱｐ１を対象キューに設定する。

再振分情報２７２において、結び付けしなおさないハッシュ値Ｈ１〜Ｈ３については、学習部２０３から受け取った時点の学習結果２７１と同じであり、キューポインタＱｐ１〜Ｑｐ３のままである。これらは、学習情報４００およびハッシュ値テーブル２２２におけるハッシュ値Ｈ１〜Ｈ３とキューポインタＱｐ１〜Ｑｐ３の関係とも同じであり、初期情報のままであるとも言える。

学習結果処理部２０７が、一定のルールに基づき再振分を行う際、装置運用者の指示、たとえばコンフィグレーションにより、再振分の対象外となるハッシュ値が指定され、指定されたハッシュ値は一定のルールから除外されてもよい。

振分部２０２は、学習結果処理部２０７から再振分情報２７２を受け取り、再振分情報２７２をハッシュ値テーブル２２２のキューポインタ３０２へ反映する。特に、再振分情報２７２１、２７２２が、ハッシュ値テーブル２２２のキューポインタ３０２に設定される。

＜学習結果処理部２０７による再振分情報２７２の作成処理手順例＞
図６は、学習結果処理部２０７による処理手順の例を示すフローチャートである。図５を用いて説明したように、学習結果処理部２０７は学習結果２７１から再振分情報２７２を作成するため、この作成の処理手順の例を示すフローチャートとなる。ここで、一定のルールは既に説明したとおりである。

学習結果処理部２０７は、学習部２０３から学習結果２７１を受信し（ステップ６０１）、受信した学習結果２７１のハッシュ値Ｈの若番から、現在キュー長と流量を判定するため、変数ｉに０を設定し（ステップ６０２）、変数ｉに１を加算する（ステップ６０３）。

ステップ６０３からステップ６１２まではループとなっており、変数ｉが１からハッシュ値Ｈの数であるｍまでを処理して終了するため、学習結果処理部２０７は、変数ｉがｍ＋１未満であるかを判定し（ステップ６０４）、変数ｉがｍ＋１未満でないと判定した場合、ハッシュ値Ｈ１からハッシュ値Ｈｍまでが既に処理済みであるので、ステップ６１３へ進んでループを終了する。

なお、ステップ６０２〜６０４はループのための処理の例であり、ハッシュ値Ｈ１からハッシュ値Ｈｍまでを処理できれば、これらの例に処理が限定されるものではない。

ステップ６０４で変数ｉがｍ＋１未満であると判定した場合、学習結果処理部２０７は、学習結果２７１においてハッシュ値Ｈｉの列の現在キュー長が０であるかを判定し（ステップ６０５）、現在キュー長が０であると判定した場合、学習結果２７１においてハッシュ値Ｈｉの列の流量が、一定のルールに設定された閾値以下であるかを判定する（ステップ６０６）。

ステップ６０５で現在キューが０でないと判定した場合と、ステップ６０６で流量が閾値以下ではないと判定した場合は、ステップ６０３へ戻り、変数ｉに１が加算されて次のハッシュ値Ｈｉが処理の対象となる。

ここで、閾値は既に説明したようにたとえば３０である。なお、ステップ６０６は無くてもステップ６１１により同じ処理結果が得られるが、図５に示した学習結果２７１におけるハッシュ値Ｈ２の場合などで、以下で説明するステップ６０８からステップ６１１までのループの実行を予め省略できる。

ステップ６０６で流量が閾値以下であると判定した場合、ハッシュ値Ｈｉよりも若番のハッシュ値Ｈｊ（ｊはｉ未満の整数）の列の対象キューであるキューポインタＱｐに、ハッシュ値Ｈｉを集約するため、学習結果処理部２０７は、変数ｊに０を設定し（ステップ６０８）、変数ｊに１を加算する（ステップ６０８）。

ステップ６０８からステップ６１１まではループとなっており、変数ｊが１から変数ｉ―１までを処理して終了するため、学習結果処理部２０７は、変数ｊが変数ｉ未満であるかを判定し（ステップ６０９）、変数ｊが変数ｉ未満でないと判定した場合、ハッシュ値Ｈ１からハッシュ値Ｈｉ−１までは既に処理済みであり、集約する対象のハッシュ値Ｈｊが見つからないため、ステップ６０３へ戻る。

なお、ステップ６０７〜６０９はループのための処理の例であり、ハッシュ値Ｈ１からハッシュ値Ｈｉ−１までを処理できれば、これらの例に処理が限定されるものではない。

ステップ６０９で変数ｊが変数ｉ未満であると判定した場合、学習結果処理部２０７は、学習結果２７１においてハッシュ値Ｈｊの列の現在キュー長が０であるかを判定し（ステップ６１０）、現在キュー長が０であると判定した場合、学習結果２７１においてハッシュ値Ｈｊの列の流量とハッシュ値Ｈｉの列の流量との合計値が、一定のルールに設定された閾値以下であるかを判定する（ステップ６１１）。

ステップ６１０で現在キューが０でないと判定した場合と、ステップ６１１で流量の合計値が閾値以下ではないと判定した場合は、ステップ６０８へ戻り、変数ｊに１が加算されて次のハッシュ値Ｈｊが処理の対象となる。

ステップ６１１で流量の合計値が閾値以下であると判定した場合、ハッシュ値Ｈｉをハッシュ値Ｈｊの列の対象キューであるキューポインタＱｐに集約できるので、学習結果処理部２０７は、学習結果２７１におけるハッシュ値Ｈｊの列をハッシュ値Ｈｉの列へコピーする（ステップ６１２）。

このコピーには、対象キューのキューポインタＱｐが含まれるため、ハッシュ値Ｈｊに対応するキューポインタＱｐがハッシュ値Ｈｉにも対応することになる。また、学習結果処理部２０７は、ステップ６１２で流量の合計値を、学習結果２７１におけるハッシュ値Ｈｊの列の流量に設定し、この合計値もコピーに含める。

これにより、ステップ６１１でのハッシュ値Ｈｊの列の流量は、既に合計値（図５に示したハッシュ値Ｈ１とハッシュ値Ｈ４の５＋２＝７）である場合、ハッシュ値Ｈｉの列の流量をさらに加えた合計値（図５に示したハッシュ値Ｈ５を加えた７＋３＝１０）とすることができる。

また、合計値もコピーしているので、ハッシュ値Ｈｉをハッシュ値Ｈｊの列の対象キューであるキューポインタＱｐに集約しているにもかかわらず、ハッシュ値Ｈｊの列の流量よりハッシュ値Ｈｉの列の流量が小さくなるという現象が発生し、ハッシュ値Ｈｊに集約できずにハッシュ値Ｈｉに集約してしまうということもない。

なお、ステップ６１１〜６１２では、学習結果２７１を変更する例を示したが、これらに限定されるものではなく、集約の対象となるキューポインタＱｐと流量の合計値を学習結果２７１とは別に記憶し、それに応じた処理手順としてもよい。

学習結果処理部２０７は、ステップ６１２を実行すると、ハッシュ値Ｈｉに関する集約が終了したので、ステップ６０２へ戻り、変数ｉに１が加算して次のハッシュ値Ｈｉを処理の対象とする。

ステップ６０４で変数ｉがｍ＋１未満でないと判定した場合、学習結果処理部２０７は、変更された対象キューを含む学習結果２７１のハッシュ値と対象キューを、再振分情報２７２のハッシュ値と対象キューへコピーし、処理を終了する。

＜学習結果処理部２０７による再振分情報２７２の更新処理手順例＞
図７は、学習結果処理部２０７による処理手順の例を示すフローチャートである。図５、６を用いて説明した学習結果処理部２０７が作成した再振分情報２７２は、集約されたハッシュ値ＨのキューポインタＱｐすなわちキュー２１４が使用されなくなる。

このため、使用されなくなったキュー２１４へ他のハッシュ値Ｈを対応させ、その他のハッシュ値Ｈに変換されるパケット２５０のフロー２６０のバッファに割り当てる処理手順を示すフローチャートとなる。なお、ここでは、学習結果処理部２０７の処理として説明するが、学習結果処理部２０７の代わりに振分部２０２が処理してもよい。

使用されなくなったキュー２１４へ他のハッシュ値Ｈを対応させる場合、学習結果処理部２０７は、図６に示したフローチャートの処理手順を実行した後、振分部２０２へ再振分情報２７２を送る前に、以下で説明する処理手順を実行する。使用されなくなったキュー２１４へ他のハッシュ値Ｈを対応させない場合は、以下で説明する処理手順を実行せず、図６を用いて説明したように再振分情報２７２を送る。

学習結果処理部２０７は、新たに割り当てるハッシュ値Ｈｋ（ｋは１〜ｍの任意の整数）を取得する（ステップ７０１）。ハッシュ値Ｈｋは、たとえば、新たに追加されたフロー２６０のパケット２５０から変換されたハッシュ値Ｈであり、通信が無くキュー２１４が結び付けられていないため、図３、４に示したキューポインタ（対象キュー）がＮＵＬＬであるハッシュ値Ｈ７である。

なお、図５の例では、ハッシュ値Ｈ７の図示を省略したが、学習結果２７１は図４に示した学習情報４００と同じ情報であり、再振分情報２７２は学習結果２７１のコピーであるので、再振分情報２７２のハッシュ値Ｈ７に対応する対象キューはＮＵＬＬである。

学習結果処理部２０７は、キューポインタＱｐの数すなわちキュー２１４の数に相当するｎビットのビットマップの各ビットに０を設定する（ステップ７０２）。このｎビットのビットマップの各ビットは、使用されていないキュー２１４を０で表し、ステップ７０２はこの初期化である。

なお、図５に示した再振分情報２７２のようにキューポインタＱｐ１の指すキュー２１４−１にハッシュ値Ｈ１、Ｈ４、Ｈ５が結び付けられる場合もあり、これはハッシュ値テーブル２２２、学習情報４００、および学習結果２７１にも反映し、反映した後の学習に基づいて、たとえば一部のハッシュ値Ｈ４が他のキュー２１４に集約されても、ハッシュ値Ｈ１、Ｈ５は残る。

このため、図６に示したステップ６１２では、ハッシュ値Ｈｉの対象キューが他のハッシュ値Ｈが結び付けられている可能性もあり、使用されなくなったキュー２１４を特定しきれないので、再振分情報２７２をスキャンして、ｎビットのビットマップにキュー２１４の使用状況を反映させる。

学習結果処理部２０７は、変数ｉに０を設定し（ステップ７０３）、変数ｉに１を加算し（ステップ７０４）、変数ｉがｍ＋１未満であるかを判定する（ステップ７０５）。これらのステップ７０３〜７０５は、図６に示したステップ６０２〜６０４と同じである。

学習結果処理部２０７は、ステップ７０５で変数ｉがｍ＋１未満であると判定した場合、再振分情報２７２におけるハッシュ値Ｈｉの列の対象キューのキューポインタＱｐｊを取得し、ｎビットのビットマップのｊ番目のビットに１を設定して（ステップ７０６）、ステップ７０４へ戻る。

ステップ７０５で変数ｉがｍ＋１未満でないと判定すると、ハッシュ関数Ｈｍまでの列の対象キューのキューポインタＱｐの情報をｎビットのビットマップに反映させたので、学習結果処理部２０７は、ｎビットのビットマップの情報を調べるために、変数ｉに０を設定し（ステップ７０７）、変数ｉに１を加算し（ステップ７０８）、変数ｉがｎ＋１未満であるかを判定する（ステップ７０９）。

学習結果処理部２０７は、ステップ７０９で変数ｉがｎ＋１未満であると判定した場合、ｎビットのビットマップのｉ番目のビットが０であるかを判定し（ステップ７１０）し、ｎビットのビットマップのｉ番目のビットが０であると判定した場合、再振分情報２７２においてハッシュ値Ｈｋの列の対象キューにキューポインタＱｐｉを設定し、再振分情報２７２を更新する（ステップ７１１）。

学習結果処理部２０７は、ステップ７１０でｎビットのビットマップのｉ番目のビットが０でないと判定した場合、キューポインタＱｐｉは使用されているので、ステップ７０８へ戻り、ステップ７０９で変数ｉがｎ＋１未満でないと判定した場合、キューポインタＱｐ１〜Ｑｐｎには使用されていないものはないので、処理を終了する。

図７に示したフローチャートの処理が終了すると、既に説明したように、学習結果処理部２０７は、更新された再振分情報２７２を振分部２０２へ送る。ここで、ステップ７０９で変数ｉがｎ＋１未満でないと判定した場合、さらに、ハッシュ値Ｈｋに現在キュー長および／あるいは流量の少ないキュー２１４を結び付けたり、運用者へ通知したりしてもよい。

以上で説明したように、キュー２１４の数以上のハッシュ値Ｈすなわちフロー２６０を収容しても、現在キュー長と流量の小さな複数のハッシュ値Ｈを集約できるので、キュー２１４の容量を超える可能性は低く、パケット２５０が破棄されないので、通信品質を守ることができる。

また、集約により使用されなくなったキュー２１４へ新たなハッシュ値Ｈすなわち新たなフロー２６０を収容できるので、通信品質を守りながら、収容できるフロー２６０の数を増やすことも可能になる。

なお、本発明は以上で説明した実施例に限定されるものではなく、特許請求の範囲の趣旨内における様々な変形例および同等の構成が含まれる。たとえば、以上の実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに本発明は限定されない。

また、以上で説明した各構成、機能、処理部、処理手段などは、それらの一部又は全部を、たとえば集積回路で設計するなどにより、ハードウェアで実現してもよく、プロセッサがそれぞれの機能を実現するプログラムを解釈し実行することにより、ソフトウェアで実現してもよい。

各機能を実現するプログラム、テーブル、ファイルなどの情報は、メモリ、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｒｉｖｅ）などの記憶装置、又は、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）カード、ＳＤカード、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）の記録媒体に格納されてもよい。

また、制御線や情報線は説明上必要と考えられるものを示しており、実装上必要な全ての制御線や情報線を示しているとは限らない。実際には、ほとんど全ての構成が相互に接続されていると考えてよい。

１２０ ルータ
２０１ 受信部
２０２ 振分部
２０３ 学習部
２０４ バッファ
２０５ 帯域制御部
２０６ 送信部
２０７ 学習結果処理部
２１４ キュー
２２１ 変換部
２２２ ハッシュ値テーブル

Claims (5)

1. パケットを中継する通信中継装置であって、
   パケットを受信し、受信したパケットを出力する受信部と、
   前記受信部が出力したパケットをハッシュ値に変換し、ハッシュ値とキューとの対応関係にしたがい、変換されたハッシュ値に基づいて、前記受信部が出力したパケットを複数のキューに振り分ける振分部と、
   前記振分部により振り分けられたパケットを複数のキューに格納するバッファと、
   前記バッファの複数のキューそれぞれに関する状態の情報を蓄積する学習部と、
   前記学習部が蓄積したキューそれぞれに関する状態の情報に基づいて、キューに複数のハッシュ値が対応する関係の情報を作成し、前記振分部へ送る学習結果処理部と、
   前記バッファに格納されたパケットを送信する送信部と
   を有し、
   前記学習部は、
   前記バッファのキューのキュー長と、前記振分部により振り分けられたパケットの流量とを、ハッシュ値ごとに、前記バッファの複数のキューそれぞれに関する状態の情報として蓄積すること
   を特徴とする通信中継装置。
2. 請求項１に記載の通信中継装置であって、
   前記振分部は、
   ハッシュ値とキューとの対応関係を記憶するハッシュ値テーブルを有し、
   前記受信部が出力したパケットのヘッダをハッシュ値に変換し、
   変換されたハッシュ値に対応するキューの情報を、前記ハッシュ値テーブルから取得し、
   前記ハッシュ値テーブルから取得したキューの情報に基づいて、前記受信部が出力したパケットを複数のキューに振り分けること
   を特徴とする通信中継装置。
3. 請求項２に記載の通信中継装置であって、
   前記受信部が受信したパケットは、宛先アドレスをヘッダに含み、
   前記振分部は、
   前記宛先アドレスを含めてハッシュ値に変換すること
   を特徴とする通信中継装置。
4. 請求項１に記載の通信中継装置であって、
   前記学習結果処理部は、
   予め設定された値よりキュー長が小さく、予め設定された値よりパケットの流量が小さい状態となるパケットのヘッダから変換されたハッシュ値を、キューへ集約させることにより、キューに複数のハッシュ値が対応する関係の情報を作成し、前記振分部へ送ること
   を特徴とする通信中継装置。
5. 請求項４に記載の通信中継装置であって、
   前記学習結果処理部は、
   前記集約によって使用されなくなったキューに、新たなハッシュ値を対応させる関係の情報を作成し、前記振分部へ送ること
   を特徴とする通信中継装置。

Images