(57)【要約】【課題】許容待機時間を考慮して経路毎の集約パケットの収容効率を高めることができる通信装置、プログラム及び方法を提供する。【解決手段】通信装置は、入力されたパケットを異なる経路に転送するために、経路毎に異なるキューバッファを有する。入力されたパケットには、許容待機時間ｄpが付与されている。キューバッファi毎に、当該キューバッファiから出力する経路における経路帯域ｗiとが設定されている。キューバッファは、蓄積されたパケットについて許容待機時間ｄpに達した際、複数のパケットを１つの集約パケットに収容して出力する。そして、通信装置は、複数のキューバッファの中で、経路帯域ｗiが狭いキューバッファほど、許容帯域時間ｄpが大きいパケットを入力する経路選択手段を有する。【選択図】図２
2015039152.tif 000002
【特許請求の範囲】
【請求項１】
入力されたパケットを異なる経路に転送するために、経路毎に異なるキューバッファを有する通信装置において、
入力されたパケットには、許容待機時間ｄpが付与されており、
前記キューバッファi毎に、当該キューバッファiから出力する経路における経路帯域ｗiとが設定されており、
前記キューバッファは、蓄積されたパケットについて許容待機時間ｄpに達した際、複数のパケットを１つの集約パケットに収容して出力するものであり、
複数のキューバッファの中で、前記経路帯域ｗiが狭いキューバッファほど、前記許容帯域時間ｄpが大きいパケットを入力する経路選択手段を有する
ことを特徴とする通信装置。
【請求項２】
前記キューバッファi毎に、過去に入力された複数のパケットに対する平均許容待機時間ｄaveiが更に記録されており、
前記経路選択手段は、
前記キューバッファi毎に、当該キューバッファiの平均許容待機時間ｄaveiと、入力された当該パケットの許容待機時間ｄpとの乖離度ｇiを算出し、
前記キューバッファi毎に、前記乖離度ｇiに対する前記経路帯域ｗiの割合となる適合度ｒiを算出し、
全てのキューバッファの適合度Σｒiに対する当該キューバッファiの適合度ｒiの割合となる経路選択確率ｐiを算出し、
全てのキューバッファを順に並べて前記経路選択確率ｐiを累積することによって、前記キューバッファi毎の経路選択確率範囲を決定し、
パケットが入力された際に、乱数を発生させ、その乱数値が含まれる経路選択確率範囲と一致するキューバッファを選択し、当該キューバッファへ当該パケットを出力する
ことを特徴とする請求項１に記載の通信装置。
【請求項３】
前記経路選択手段について、
前記乖離度ｇiは、平均許容待機時間ｄaveiに集約係数ｋiを乗算した目標許容待機時間ｋi・ｄaveiを用いて、以下のように算出される
ｇi＝ｋi・ｄavei−ｄp
ことを特徴とする請求項２に記載の通信装置。
【請求項４】
前記集約係数ｋiは、過去の集約係数ｋi'に、当該キューバッファから出力される前記集約パケットの実測送信サイズＬiに対する目標送信サイズＬの割合を乗算した、集約パケットサイズの移動平均値であって、以下のように算出される
ｋi＝max(１，ｋi'・Ｌ／Ｌi)
max(x,y)：x又はyのいずれか大きい方の値を出力
ことを特徴とする請求項３に記載の通信装置。
【請求項５】
前記適合度ｒiは、前記乖離度ｇiを用いて以下のように算出される
ｒi＝ｗi／log(１＋ｇi2)
＝ｗi／log(１＋(ｋi・ｄavei−ｄp) 2)
ことを特徴とする請求項３又は４に記載の通信装置。
【請求項６】
入力されたパケット毎に、タイムスタンプを付与するタイムスタンプ付与手段と、
前記パケット毎に、前記タイムスタンプと現在時刻との時間差となる許容待機時間を付与する許容待機時間算出手段と
を更に有し、
前記経路選択手段には、前記タイムスタンプ及び前記許容帯域時間を付加したパケットが入力される
ことを特徴とする請求項１から５のいずれか１項に記載の通信装置。
【請求項７】
前記経路選択手段は、
パケットのヘッダ情報に、当該パケットを入力すべきキューバッファの識別子を対応付けて登録したフローテーブルを有し、
入力されたパケットのヘッダ情報が、前記フローテーブルに登録されたヘッダ情報と一致するか否かを判定し、
真と判定した場合、当該パケットを、登録された当該キューバッファへ出力し、
偽と判定した場合、当該パケットの許容帯域時間ｄpに応じて複数のキューバッファの中から選択し、選択されたキューバッファの識別子と、入力されたパケットのヘッダ情報とを対応付けて前記フローテーブルに登録する
ことを特徴とする請求項１から６のいずれか１項に記載の通信装置。
【請求項８】
当該通信装置は、コアネットワークとアクセスネットワークとの境界に設置されるエッジ装置であって、
前記ヘッダ情報は、レイヤ１からレイヤ４までのプロトコルヘッダに基づく情報である
ことを特徴とする請求項７に記載の通信装置。
【請求項９】
請求項１から８のいずれか１項に記載の複数の通信装置と、ネットワーク内の経路毎の経路帯域を管理する管理装置とを有するシステムであって、
前記管理装置は、各通信装置へ、経路i毎の新規経路帯域ｎiを送信し、
前記通信装置は、各キューバッファiの実測経路帯域ｓiを計測し、キューバッファi毎に設定すべき経路帯域ｗiを、以下の式によって算出する
ｗi＝ｎi×（ｎi／ｓi）
ことを特徴とするシステム。
【請求項１０】
入力されたパケットを異なる経路に転送するために、経路毎に異なるキューバッファを有する通信装置に搭載されたコンピュータを機能させるプログラムにおいて、
入力されたパケットには、許容待機時間ｄpが付与されており、
前記キューバッファi毎に、当該キューバッファiから出力する経路における経路帯域ｗiとが設定されており、
前記キューバッファは、蓄積されたパケットについて許容待機時間ｄpに達した際、複数のパケットを１つの集約パケットに収容して出力するものであり、
複数のキューバッファの中で、前記経路帯域ｗiが狭いキューバッファほど、前記許容帯域時間ｄpが大きいパケットを入力する経路選択手段としてコンピュータを機能させることを特徴とするプログラム。
【請求項１１】
入力されたパケットを異なる経路に転送するために、経路毎に異なるキューバッファを有する装置におけるパケット入出力方法において、
入力されたパケットには、許容待機時間ｄpが付与されており、
前記キューバッファi毎に、当該キューバッファiから出力する経路における経路帯域ｗiとが設定されており、
前記キューバッファは、蓄積されたパケットについて許容待機時間ｄpに達した際、複数のパケットを１つの集約パケットに収容して出力するものであり、
複数のキューバッファの中で、前記経路帯域ｗiが狭いキューバッファほど、前記許容帯域時間ｄpが大きいパケットを入力する
ことを特徴とするパケット入出力方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力されたパケットを異なる経路に転送するべく、経路毎に異なるキューバッファを有する通信装置の技術に関する。特に、コアネットワークを介して通信するエッジ装置の技術に関する。
【背景技術】
【０００２】
コアネットワークは、パケット転送処理に特化したコア装置と、パケット経路を選択するエッジ装置とから構成されている。コア装置は、コアネットワークの中核に配置され、エッジ装置は、コアネットワークとアクセスネットワークとの境界に配置される。特にエッジ装置は、コアネットワークにおける局所的な空き状況を把握して、パケット毎に要求される通信品質に応じて、パケットの転送経路を選択する。エッジ装置は、コア装置と比較して処理負荷が大きいために、１つの拠点に複数配備され、負荷分散されることも多い。
【０００３】
例えばエッジ装置のような通信装置には、コアネットワークの収容回線全体を最大限に利用するために、以下のような関係を成立させる必要がある。
許容平均パケット長  ≧  Ｍｌ／Ｍｐ
Ｍｌ：通信装置における１秒当たりの収容回線のビット数
Ｍｐ：通信装置における１秒当たりの処理可能なパケット数
【０００４】
図１は、エッジ装置間でコアネットワークを介して通信するシステム構成図である。
【０００５】
図１によれば、送信側エッジ装置は、コアネットワークを介した同一の宛先エッジ装置に対して、異なる複数の経路を確立する。そして、送信側エッジ装置は、アクセスネットワークから入力されたパケットについて、できる限り通信帯域に空きのある経路へ、そのパケットを送出する。これによって、余剰通信経路を有効に利用し、コアネットワーク全体の利用効率を高めようとする。
【０００６】
また、エッジ装置は、経路毎に個別のキューバッファを備えているために、入力されたパケットに対するキューバッファの通信遅延も重要となる。エッジ装置は、受信した各パケットの優先度（通信品質）に応じて中継転送するために、キューバッファを最適に構成する必要がある。具体的には、パケット毎に計測されたバッファ内の待機時間と、その優先度に基づく許容待機時間とを考慮して、パケットが中継転送される。異なるサービスのパケットを転送するコアネットワークによれば、サービス毎に、異なる通信遅延が要求される。この通信遅延は、そのパケットがエッジ装置内に滞留できる時間、即ちキューバッファに滞留できる許容待機時間として与えられる。エッジ装置は、その通信遅延の制約を満たしつつ、それらパケットをコアネットワークへ転送する。
【０００７】
更に、エッジ装置は、宛先エッジ装置のアドレス群とその経路とを対応付けて記憶したフローテーブルを有する。そのフローテーブルに応じて、パケット毎の経路、即ち、そのパケットを入力すべきキューバッファが選択される。具体的には、ＲＩＰ(Routing Information Protocol)、ＯＳＰＦ(Open Shortest Path First)、ＢＧＰ(Border Gateway Protocol)のような経路制御プロトコルによっても、異なるキューバッファが選択される。尚、エッジ装置間の経路は、異なる物理回線であってもよいし、単一の物理回線に設定された複数の論理回線であってもよい。
【０００８】
他の従来技術として、無線基地局について、無線回線から入力された複数のパケットを集約し、その集約パケットを固定ネットワークへ出力する技術がある（例えば特許文献１及び２参照）。この技術によれば、キューバッファに複数のパケットが格納されるまで待機し、所定条件のタイミングで、そのキューバッファ内のパケットを集約し、その集約パケットを出力する。転送すべきパケットの平均パケット長が許容平均パケット長よりも小さい場合であっても、それらパケットの平均パケット長を大きくすることができる。平均パケット長が大きいパケット単位で転送することによって、ネットワークの利用効率を高めることができる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０１２−２３９２４３号公報
【特許文献２】特開２０１３−１０２４３３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
前述した従来技術によれば、以下の両方を追求することは難しい場合がある。
（１）各パケットの経路選択に基づくネットワークの利用率の最大化
（２）複数のパケットの集約に基づく許容平均パケット長の最大化
【００１１】
（１）各パケットの経路選択に基づくネットワークの利用率の最大化
通常、パケットを複数の経路へ振り分ける場合、経路毎に、パケットの振り分ける割合（振り分け率）が与えられる。エッジ装置は、この振り分け率に応じて、各パケットを異なる経路へ振り分ける。振り分け率が大きい経路のキューバッファには、振り分け率が小さい経路のキューバッファと比較して、高いレートでパケットが入力される。
【００１２】
尚、この振り分け率は、時々刻々と変化する高速ネットワークの利用率と、高速ネットワークを取り囲むエッジ装置へ入力されるトラヒック量の変化とに対応するために、定期的に更新される。図１によれば、コアネットワークに管理装置２が備えられており、エッジ装置に対して、定期的に、キューバッファ毎の振り分け率が送信される。
【００１３】
（２）複数のパケットの集約に基づく許容平均パケット長の最大化
所定の通信品質（通信遅延）が要求されたパケットを集約する場合には、許容待機時間が短いパケットは、キューバッファに滞在できる時間も短い。そのようなパケットが、振り分け率が低い経路へ振り分けられた場合、そのキューバッファは、集約のために後続のパケットを待つ待機時間が短くなり、十分なパケットの集約をすることなく、キューバッファに格納されたパケットを出力することとなる。尚、図１によれば、管理装置２が、宛先ＩＰアドレスや、フロータプル（送信元・宛先のＩＰアドレスとポート番号の組など）に対応する許容待機時間を、エッジ装置１へ送信するものであってもよい。
【００１４】
そこで、本発明は、許容待機時間を考慮して経路毎の集約パケットの収容効率を高めることができる通信装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明によれば、入力されたパケットを異なる経路に転送するために、経路毎に異なるキューバッファを有する通信装置において、
入力されたパケットには、許容待機時間ｄpが付与されており、
キューバッファi毎に、当該キューバッファiから出力する経路における経路帯域ｗiとが設定されており、
キューバッファは、蓄積されたパケットについて許容待機時間ｄpに達した際、複数のパケットを１つの集約パケットに収容して出力するものであり、
複数のキューバッファの中で、経路帯域ｗiが狭いキューバッファほど、許容帯域時間ｄpが大きいパケットを入力する経路選択手段を有する
ことを特徴とする。
【００１６】
本発明の通信装置における他の実施形態によれば、
キューバッファi毎に、過去に入力された複数のパケットに対する平均許容待機時間ｄaveiが更に記録されており、
経路選択手段は、
キューバッファi毎に、当該キューバッファiの平均許容待機時間ｄaveiと、入力された当該パケットの許容待機時間ｄpとの乖離度ｇiを算出し、
キューバッファi毎に、乖離度ｇiに対する経路帯域ｗiの割合となる適合度ｒiを算出し、
全てのキューバッファの適合度Σｒiに対する当該キューバッファiの適合度ｒiの割合となる経路選択確率ｐiを算出し、
全てのキューバッファを順に並べて経路選択確率ｐiを累積することによって、キューバッファi毎の経路選択確率範囲を決定し、
パケットが入力された際に、乱数を発生させ、その乱数値が含まれる経路選択確率範囲と一致するキューバッファを選択し、当該キューバッファへ当該パケットを出力する
ことも好ましい。
【００１７】
本発明の通信装置における他の実施形態によれば、
経路選択手段について、
乖離度ｇiは、平均許容待機時間ｄaveiに集約係数ｋiを乗算した目標許容待機時間ｋi・ｄaveiを用いて、以下のように算出される
ｇi＝ｋi・ｄavei−ｄp
ことも好ましい。
【００１８】
本発明の通信装置における他の実施形態によれば、
集約係数ｋiは、過去の集約係数ｋi'に、当該キューバッファから出力される集約パケットの実測送信サイズＬiに対する目標送信サイズＬの割合を乗算した、集約パケットサイズの移動平均値であって、以下のように算出される
ｋi＝max(１，ｋi'・Ｌ／Ｌi)
max(x,y)：x又はyのいずれか大きい方の値を出力
ことも好ましい。
【００１９】
本発明の通信装置における他の実施形態によれば、
適合度ｒiは、乖離度ｇiを用いて以下のように算出される
ｒi＝ｗi／log(１＋ｇi2)
＝ｗi／log(１＋(ｋi・ｄavei−ｄp) 2)
ことも好ましい。
【００２０】
本発明の通信装置における他の実施形態によれば、
入力されたパケット毎に、タイムスタンプを付与するタイムスタンプ付与手段と、
パケット毎に、タイムスタンプと現在時刻との時間差となる許容待機時間を付与する許容待機時間算出手段と
を更に有し、
経路選択手段には、タイムスタンプ及び許容帯域時間を付加したパケットが入力される
ことも好ましい。
【００２１】
本発明の通信装置における他の実施形態によれば、
経路選択手段は、
パケットのヘッダ情報に、当該パケットを入力すべきキューバッファの識別子を対応付けて登録したフローテーブルを有し、
入力されたパケットのヘッダ情報が、フローテーブルに登録されたヘッダ情報と一致するか否かを判定し、
真と判定した場合、当該パケットを、登録された当該キューバッファへ出力し、
偽と判定した場合、当該パケットの許容帯域時間ｄpに応じて複数のキューバッファの中から選択し、選択されたキューバッファの識別子と、入力されたパケットのヘッダ情報とを対応付けてフローテーブルに登録する
ことも好ましい。
【００２２】
本発明の通信装置における他の実施形態によれば、
当該通信装置は、コアネットワークとアクセスネットワークとの境界に設置されるエッジ装置であって、
ヘッダ情報は、レイヤ１からレイヤ４までのプロトコルヘッダに基づく情報である
ことも好ましい。
【００２３】
本発明によれば、前述した複数の通信装置と、ネットワーク内の経路毎の経路帯域を管理する管理装置とを有するシステムであって、
管理装置は、各通信装置へ、経路i毎の新規経路帯域ｎiを送信し、
通信装置は、各キューバッファiの実測経路帯域ｓiを計測し、キューバッファi毎に設定すべき経路帯域ｗiを、以下の式によって算出する
ｗi＝ｎi×（ｎi／ｓi）
ことを特徴とする。
【００２４】
本発明によれば、入力されたパケットを異なる経路に転送するために、経路毎に異なるキューバッファを有する通信装置に搭載されたコンピュータを機能させるプログラムにおいて、
入力されたパケットには、許容待機時間ｄpが付与されており、
キューバッファi毎に、当該キューバッファiから出力する経路における経路帯域ｗiとが設定されており、
キューバッファは、蓄積されたパケットについて許容待機時間ｄpに達した際、複数のパケットを１つの集約パケットに収容して出力するものであり、
複数のキューバッファの中で、経路帯域ｗiが狭いキューバッファほど、許容帯域時間ｄpが大きいパケットを入力する経路選択手段としてコンピュータを機能させることを特徴とする。
【００２５】
本発明によれば、入力されたパケットを異なる経路に転送するために、経路毎に異なるキューバッファを有する装置におけるパケット入出力方法において、
入力されたパケットには、許容待機時間ｄpが付与されており、
キューバッファi毎に、当該キューバッファiから出力する経路における経路帯域ｗiとが設定されており、
キューバッファは、蓄積されたパケットについて許容待機時間ｄpに達した際、複数のパケットを１つの集約パケットに収容して出力するものであり、
複数のキューバッファの中で、経路帯域ｗiが狭いキューバッファほど、許容帯域時間ｄpが大きいパケットを入力する
ことを特徴とする。
【発明の効果】
【００２６】
本発明の装置、方法及びプログラムによれば、許容待機時間を考慮して経路毎の集約パケットの収容効率を高めることができる。即ち、本発明の装置等によれば、（１）各パケットの経路選択に基づくネットワークの利用率の最大化と、（２）複数のパケットの集約に基づく許容平均パケット長の最大化との両方の効果を得ることができる。
【図面の簡単な説明】
【００２７】
【図１】エッジ装置間でコアネットワークを介して通信するシステム構成図である。
【図２】本発明におけるエッジ装置の機能構成図である。
【図３】本発明における経路選択部の基本的な機能を表す説明図である。。
【図４】本発明における経路選択部の具体的な処理を表す説明図である。
【図５】管理装置からのキューバッファの経路帯域の制御を表す説明図である。
【発明を実施するための形態】
【００２８】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２９】
図２は、本発明におけるエッジ装置の機能構成図である。
【００３０】
図２によれば、入力された複数のパケットを収容した集約パケットを出力する通信装置１が表されている。当該通信装置１は、コアネットワークとアクセスネットワークとの境界に設置されるエッジ装置であって、コアネットワークを介して相手方エッジ装置との間で、集約パケットを送受信する。図２のエッジ装置１によれば、入力インタフェース１０と、タイムスタンプ付与部１１と、許容待機時間算出部１２と、経路選択部１３と、複数のキューバッファ１４と、出力インタフェース１５とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行させることによって実現できる。また、これら機能構成部の処理の流れは、装置における入出力方法としても理解できる。
【００３１】
入力インタフェース１０は、アクセスネットワークに接続しており、アクセスネットワークからパケットを入力する。それらパケットは、タイムスタンプ付与部１１へ出力される。
【００３２】
［タイムスタンプ付与部１１］
タイムスタンプ付与部１１は、入力されたパケット毎に、入力直後の時刻を付与する（タイムスタンプ）。パケット毎のタイムスタンプによって、後段の処理について、そのパケットにおける許容待機時間を算出することができる。そのパケットは、許容待機時間算出部１２へ出力される。
【００３３】
［許容待機時間算出部１２］
許容待機時間算出部１２は、パケット毎に、タイムスタンプと現在時刻との時間差となる「許容待機時間」（許容遅延時間）を付与する。許容待機時間は、当該エッジ装置内のキューバッファに滞在することが許容される時間を意味する。
許容待機時間ｄp＝現在時刻−タイムスタンプ
許容待機時間ｄpが付与されたパケットは、経路選択部１３へ出力される。
【００３４】
［経路選択部１３］
エッジ装置１は、例えばＯＳＰＦのような経路制御プロトコルを用いて、同一の宛先エッジ装置１に対して、複数の経路を確立している。経路選択部１３には、タイムスタンプ及び許容帯域時間を付加したパケットが入力され、そのパケットを、いずれかのキューバッファ１４へ振り分ける。尚、後段のキューバッファ１４は、経路毎に備えられたものである。
【００３５】
図３は、本発明における経路選択部の基本的な機能を表す説明図である。
【００３６】
経路選択部１３は、パケットのヘッダ情報に、経路（経路識別子、即ちキューバッファ識別子）を対応付けて記憶したフローテーブルを有する。フローテーブルは、パケットに対して、宛先となる１つの相手方エッジ装置を特定すると共に、その相手方エッジ装置に対して確立された複数の経路の中から当該パケットを転送すべき経路を登録している。ここで、ヘッダ情報は、「フロータプル」であってもよい。フロータプルとは、レイヤ１（例えばスイッチの物理ポート）から、レイヤ４（例えばＴＣＰ／ＩＰのポート番号）までのプロトコルヘッダに基づく情報である。例えばOpenFlowスイッチに本発明を適用する場合、フロータプルは１４種類程度あり、フローテーブルには、特定のレイヤに基づくことなく設定することができる。
【００３７】
経路選択部１３は、最初に、フローテーブルを参照し、入力されたパケットのヘッダ情報が登録されているか否かを判定する。既に登録されている場合（ＹＥＳ）、そのパケットを、フローテーブルに登録された経路へ、即ち登録された当該キューバッファ１４へ出力する。パケットのフローについて、一度確立された経路は、継続して使用される。
【００３８】
一方で、入力されたパケットのヘッダ情報が、フローテーブルに登録されていない場合（ＮＯ）、経路選択部１３は、宛先となる相手方エッジ装置に対して確立された複数の経路の中から、当該パケットを転送すべき経路を選択する。このとき、当該パケットの許容帯域時間ｄpに応じて、キューバッファが選択される。
【００３９】
図３によれば、キューバッファ１４は、キューバッファi毎に、少なくとも、当該キューバッファiから出力する経路における「経路帯域ｗi」が設定されている。ここで、経路帯域ｗiが狭いキューバッファiほど、パケット集約のために、長いバッファ待機時間が必要となる。そのようなキューバッファiへ、許容待機時間が短いパケットが格納されると、十分な数のパケットが当該キューバッファに溜まる前に、パケットを集約して送出しなければならない。この場合、パケットの収容効率が低下することとなる。そのために、本発明のエッジ装置１における経路選択部１３は、複数のキューバッファの中で、経路帯域ｗiが狭いキューバッファiほど、許容帯域時間ｄpが大きいパケットを入力するように制御する。
【００４０】
図４は、本発明における経路選択部の具体的な処理を表す説明図である。
【００４１】
図４によれば、経路選択部１３が、経路帯域ｗiが狭いキューバッファiほど、許容帯域時間ｄpが大きいパケットを入力するための具体的な処理が表されている。まず、キューバッファ１４は、キューバッファi毎に、過去に入力された複数のパケットに対する「平均許容待機時間ｄavei」を記憶している。そして、経路選択部１３は、以下のステップを実行する。
【００４２】
（Ｓ１）キューバッファi毎に、当該キューバッファiの平均許容待機時間ｄaveiと、入力された当該パケットの許容待機時間ｄpとの乖離度ｇiを算出する。乖離度ｇiは、集約係数ｋiを用いて以下のように算出される。
ｇi＝ｋi・ｄavei−ｄp
ｇi：キューバッファiの乖離度
ｋi：キューバッファiの集約係数
ｄavei：キューバッファiの平均許容待機時間
ｄp：当該パケットの許容待機時間
【００４３】
集約係数ｋiは、パケット集約効率をより高くすることによって、キューバッファ内で待機する当該パケットの目標許容待機時間ｋi・ｄaveiを導くためのものである。集約係数ｋiは、静的な設定値としてもよいし、以下のように集約パケットサイズの移動平均値に連動させた値であってもよい。集約係数ｋiは、過去の集約係数ｋi'に、当該キューバッファから出力される集約パケットの実測送信サイズＬiに対する目標送信サイズＬの割合を乗算した、集約パケットサイズの移動平均値であって、以下のように算出される。
ｋi＝max(１，ｋi'・Ｌ／Ｌi)    （ｋi≧１）
max(x,y)：x又はyのいずれか大きい方の値を出力
ｋi'：キューバッファiの過去の集約係数
Ｌ：目標送信サイズ
Ｌi：キューバッファiの実測送信サイズ
ここでは、経路iの平均許容待機時間ｄaveiに対して、より大きい目標許容待機時間ｋi・ｄaveiを持つパケットを振り分けやすくするために、集約係数ｋiを乗算している。
【００４４】
前述の式によれば、集約パケットサイズが目標送信サイズＬであれば、集約効率が最大であることを前提とする。実測送信サイズＬiが目標送信サイズＬよりも小さい場合には、目標送信サイズＬに近づくように、集約係数を大きくする性質がある。また、実測送信サイズＬiが目標送信サイズＬよりも小さいということは、少ないパケットが集約されて送出されていることを意味し、即ち、当該経路の許容待機時間が十分に大きくないことを意味する。そこで、集約係数ｋiを大きくすることによって、より許容待機時間の大きいパケットを当該経路iへ振り分けることができ、集約効率を回復することができる。
【００４５】
（Ｓ２）次に、キューバッファi毎に、乖離度ｇiに対する経路帯域ｗiの割合となる適合度ｒiを算出する。適合度ｒiは、乖離度ｇiを用いて以下のように算出される
ｒi＝ｗi／log(１＋ｇi2)
＝ｗi／log(１＋(ｋi・ｄavei−ｄp) 2)
ｒi：適合度
ｇi：乖離度
ｗi：経路帯域
当該パケットの許容待機時間ｄpが、平均許容待機時間ｄaveiよりも大きい目標許容待機時間ｋi・ｄaveiに近くなるほど、適合度ｒiは大きくなる。また、適合度ｒiの算出に用いるlogは、当該パケットの許容待機時間が目標許容待機時間ｋi・ｄaveiに近くなるほど、より高い感度で経路選択確率ｐiを大きくするためのものである。
【００４６】
（Ｓ３）次に、全てのキューバッファの適合度Σｒiに対する当該キューバッファiの適合度ｒiの割合となる経路選択確率ｐiを算出する。
ｐi＝ｒi／Σｒi
適合度ｒiが大きいほど、経路iの選択確率ｐiも大きくなる。その結果、当該パケットは、経路iに選択されやすくなる。
【００４７】
（Ｓ４）そして、全てのキューバッファを順に並べて経路選択確率ｐiを累積することによって、キューバッファi毎の経路選択確率範囲を決定する。経路選択確率ｐiは、累積和は１となる。図４によれば、キューバッファには、例えば以下のように割り当てられている。
Σk=0k=i-1ｐk≦ キューバッファi毎の経路選択確率範囲 ＜Σj=0j=iｐj
キューバッファ１は、経路選択確率ｐi＝０．２であって、経路選択確率範囲０（以上）〜０．２が割り当てられている。
キューバッファ２は、経路選択確率ｐi＝０．３であって、経路選択確率範囲０．２（以上）〜０．５が割り当てられている。
最終的に、キューバッファｎは、経路選択確率ｐi＝０．０５であれば、経路選択確率範囲０．９５（以上）〜１が割り当てられている。
【００４８】
（Ｓ５）パケットが入力された際に、０〜１の範囲の一様乱数ａを発生させる。そして、その乱数値ａが、以下の経路選択確立範囲に割り当てられたキューバッファを選択する。
Σk=0k=i-1ｐk≦ａ＜Σj=0j=iｐj
図４によれば、例えば乱数値０．１５が発生したとする。このとき、その乱数値が含まれる経路選択確率範囲０〜０．２と一致するキューバッファ１が選択される。また、図示されていないが、例えばランスうち０．４が発生した場合、その乱数値が含まれる経路選択確率範囲０．２〜０．５と一致するキューバッファ２が選択される。
【００４９】
（Ｓ６）経路選択部１３は、当該パケットを選択されたキューバッファiへ出力する。
【００５０】
（Ｓ７）当該パケットについてキューバッファが選択された後、当該パケットのヘッダ情報と当該キューバッファ識別子とを対応付けて、フローテーブルへ登録する。その後は、当該パケットのフローは全て、フローテーブルに従って、同一のキューバッファへ出力される。
【００５１】
［キューバッファ１４］
キューバッファ１４は、ＦＩＦＯ(First-In First-Out)形式のバッファであって、経路毎に備えられている。キューバッファ１４は、蓄積されたパケットのいずれかについて、許容待機時間ｄpに達した際、出力側から順に、複数のパケットを１つの集約パケットに収容して出力する。
【００５２】
ここで、経路毎のキューバッファiは、平均許容待機時間ｄi、実測送信サイズＬi及び実測経路帯域ｓiを、逐次に再計算することが好ましい。具体的な計算方法としては、以下のような移動平均であってもよい。
【００５３】
平均許容待機時間ｄiの算出方法
ｄi＝α・ｄp＋（１−α）ｄi'
ｄi'：既存の平均許容待機時間
α：係数
ｄp：当該パケットの許容待機時間
この計算方法によれば、キューバッファ毎に、平均許容待機時間ｄiが逐次に算出されることとなる。
【００５４】
集約パケットの実測送信サイズＬiの算出方法
Ｌi＝β・Ｌi＋（１−β）Ｌi'
Ｌi'：既存の集約パケットの実測送信サイズ
β：係数
この計算方法によれば、キューバッファ毎に、集約パケットの実測送信サイズＬiが逐次に算出されることとなる。
【００５５】
尚、実測経路帯域ｓiは、集約パケットのサイズを、送信時間（送信終了時刻−送信開始時刻）で除算することによって算出される。
【００５６】
前述した図２〜図４の実施形態によれば、エッジ装置は、許容待機時間が大きいパケットは比較的低速の帯域を持つ経路へ、逆に、許容待機時間が小さいパケットは比較的高速の帯域を持つ経路へ送り出す。また、各経路へ転送されるパケットの許容平均パケット長を、最大化することができる。これによって、高速の帯域を持つ経路は、低速の帯域を持つ経路よりも、より多くのパケットを転送することができる。更に、フローテーブルに登録された後は、フローを構成するパケットは全て、同一の経路へ転送される。これによって、フローを基準としたパケットの順序逆転を生じることがない。
【００５７】
図５は、管理装置からのキューバッファの経路帯域の制御を表す説明図である。
【００５８】
図５によれば、各エッジ装置１は、経路毎の実測経路帯域ｓiを、管理装置２へ送信する。管理装置２は、コアネットワークに接続された多数のエッジ装置１から、経路毎の実測経路帯域ｓiを受信する。コアネットワークのトポロジ（経路）の検出には、例えばＯＳＰＦのプロトコルを用いることができる。また、実測経路帯域の最適化計算には、コアネットワークにおける全回線の利用状況から、例えば線形計画法を用いることができる。
【００５９】
その上で、一定周期Ｉcで、管理装置２は、経路i毎の新規経路帯域ｎiを各エッジ装置１へ送信すると共に、各エッジ装置１は、経路毎の実測経路帯域ｓiを管理装置２へ送信する。尚、一定周期Ｉcは、エッジ装置１内における平均許容待機時間ｄi及び実測送信サイズＬiの更新周期Ｉｒよりも、十分に長くする。
【００６０】
これに対し、各エッジ装置１は、各キューバッファiの実測経路帯域ｓiを計測し、キューバッファi毎に設定すべき経路帯域ｗiを、以下の式によって算出する。
ｗi＝ｎi×（ｎi／ｓi）
【００６１】
以上、詳細に説明したように、本発明の装置、方法及びプログラムによれば、許容待機時間を考慮して経路毎の集約パケットの収容効率を高めることができる。即ち、本発明の装置等によれば、（１）各パケットの経路選択に基づくネットワークの利用率の最大化と、（２）複数のパケットの集約に基づく許容平均パケット長の最大化とが得られる。
【００６２】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６３】
１  エッジ装置、通信装置
１０  入力インタフェース
１１  タイムスタンプ付与部
１２  許容待機時間算出部
１３  経路選択部
１４  キューバッファ群
１５  出力インタフェース
２  管理装置
【図１】
2015039152.tif 000003
【図２】
2015039152.tif 000004
【図３】
2015039152.tif 000005
【図４】
2015039152.tif 000006
【図５】
2015039152.tif 000007