図面 (/)

技術 パケット制御装置

出願人 三菱電機株式会社
発明者 三島拓也
出願日 2015年11月16日 (5年1ヶ月経過) 出願番号 2015-223589
公開日 2017年5月25日 (3年7ヶ月経過) 公開番号 2017-092836
状態 特許登録済
技術分野 広域データ交換
主要キーワード 頻度曲線 算出間隔 通過対象 度数分布図 算出時刻 閾値群 一定期間前 生成間隔
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年5月25日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (15)

課題

バッファを有するパケット制御装置において、バッファが溢れないように到着パケット廃棄するに際し、パケットを送信するユーザ間に不公平が生じ難くする。

解決手段

パケット制御装置1は、到着パケットから廃棄確率に応じた量のパケットを廃棄するパケット廃棄部11と、廃棄されなかったパケットを一時的に蓄積してから出力するバッファ12と、バッファ12に蓄積されているパケットの蓄積量の移動平均値を逐次算出する平均値算出部13と、逐次算出された複数の移動平均値についての頻度分布を生成する統計処理部15と、生成された頻度分布に応じて、移動平均値についての複数の閾値を決定する閾値決定部16と、決定された複数の閾値によって区切られた複数の区間のいずれかに、平均値算出部13で算出された移動平均値を分類する閾値処理を実行し、閾値処理の結果に応じて上記廃棄確率を決定する確率決定部14とを有する。

概要

背景

近年、通信を行うユーザ数の増加及びユーザ当りトラヒック量の増大に伴い、パケット制御装置において効率的な輻輳制御機能実装が重要となってきている。輻輳制御を実現する手法の一つとしてはRED(Random Early Detection)が挙げられる(例えば、非特許文献1参照)。

REDは、パケット制御装置に到着するパケットを、バッファに格納する前に、設定された廃棄確率(パケットが廃棄される確率)に基づいてランダムに廃棄することで、バッファの溢れを回避する輻輳制御を行う。REDは、バッファ内に蓄積されたデータ量であるバッファ蓄積量を定期的に観測し、観測したバッファ蓄積量から上記廃棄確率を算出しており、上記廃棄確率はそのパケットを送信するユーザに依らず決定される。よって、REDでは、各ユーザ間で同一の廃棄確率となり、ユーザ間の公平性が確保される。

REDは、廃棄確率の算出に複雑な演算処理が必要となることから、ハードウェアソフトウェアを組み合わせた手法で元来実現されてきた。しかし、この手法では、処理速度に大幅な時間を要することから、近年増加傾向にあるトラヒック量に対応できないことが予想される。

この問題に対し、特許文献1では、ハードウェアのみでREDを実現する手法が提案されている。特許文献1に記載のパケット処理装置では、REDをハードウェアで実現するにあたり、廃棄確率の算出に用いるバッファ蓄積量の移動平均値を、均等な間隔の閾値閾値処理し、閾値処理した結果に対応する廃棄確率の値を、ルックアップテーブルを参照して得ている。このルックアップテーブルは、各閾値で区切られた区間のそれぞれに廃棄確率の値を関連付けたものである。以上のように、このパケット処理装置では、廃棄確率を求めるために、予め定められた均等な間隔での閾値処理とルックアップテーブルを用いた参照処理を採用することにより、限られたハードウェアリソースで効率的にREDを実現する。

概要

バッファを有するパケット制御装置において、バッファが溢れないように到着パケットを廃棄するに際し、パケットを送信するユーザ間に不公平が生じ難くする。パケット制御装置1は、到着パケットから廃棄確率に応じた量のパケットを廃棄するパケット廃棄部11と、廃棄されなかったパケットを一時的に蓄積してから出力するバッファ12と、バッファ12に蓄積されているパケットの蓄積量の移動平均値を逐次算出する平均値算出部13と、逐次算出された複数の移動平均値についての頻度分布を生成する統計処理部15と、生成された頻度分布に応じて、移動平均値についての複数の閾値を決定する閾値決定部16と、決定された複数の閾値によって区切られた複数の区間のいずれかに、平均値算出部13で算出された移動平均値を分類する閾値処理を実行し、閾値処理の結果に応じて上記廃棄確率を決定する確率決定部14とを有する。

目的

本発明は、上述のような実情に鑑みてなされたものであり、その目的は、バッファを有するパケット制御装置において、バッファが溢れないように到着パケットを廃棄するに際し、パケットを送信するユーザ間に不公平が生じ難いようにすることにある

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

到着したパケットから廃棄確率に応じた量のパケットを廃棄するパケット廃棄部と、前記到着したパケットの内の、前記パケット廃棄部で廃棄されなかったパケットを一時的に蓄積してから出力するバッファと、前記バッファに蓄積されている前記パケットの蓄積量の移動平均値を逐次算出する平均値算出部と、前記平均値算出部で逐次算出された複数の移動平均値についての頻度分布を生成する統計処理部と、前記統計処理部で生成された前記頻度分布に応じて、前記移動平均値についての複数の閾値を決定する閾値決定部と、前記閾値決定部で決定された前記複数の閾値によって区切られた複数の区間のいずれかに、前記平均値算出部で算出された前記移動平均値を分類する閾値処理を実行し、前記閾値処理の結果に応じて前記廃棄確率を決定する確率決定部とを有することを特徴とするパケット制御装置

請求項2

前記閾値決定部は、前記頻度分布によって示される前記移動平均値の頻度が高いほど、前記区間が狭くなるように前記複数の閾値を決定することを特徴とする請求項1に記載のパケット制御装置。

請求項3

前記統計処理部は、前記平均値算出部で算出された前記複数の移動平均値のうちの、現在の移動平均値と同じ値を持つ過去の移動平均値の算出時点を含む算出期間について、前記頻度分布を生成することを特徴とする請求項1又は2に記載のパケット制御装置。

請求項4

前記到着したパケットの種類である到着種類を判別する判別部をさらに有し、前記確率決定部は、予め決められたパケットの種類である基準種類毎に前記廃棄確率を決定し、前記パケット廃棄部は、前記到着種類に属するパケットを、前記到着種類に対応する前記基準種類についての前記廃棄確率に応じた量、廃棄することを特徴とする請求項1から3のいずれか1項に記載のパケット制御装置。

請求項5

前記到着したパケットの種類である到着種類を判別する判別部をさらに有し、前記閾値決定部は、予め決められたパケットの種類である基準種類毎に前記複数の閾値の決定を行い、前記確率決定部は、前記基準種類毎に、前記閾値処理を実行して前記廃棄確率を決定し、前記パケット廃棄部は、前記到着種類に属するパケットを、前記到着種類に対応する前記基準種類についての前記廃棄確率に応じた量、廃棄することを特徴とする請求項1から3のいずれか1項に記載のパケット制御装置。

請求項6

前記確率決定部は、前記複数の区間に対応する複数の廃棄確率候補値を決定し、前記複数の区間のうちの前記閾値処理の結果が示す区間に対応する、前記複数の廃棄確率候補値のうちの廃棄確率候補値を、前記廃棄確率とすることを特徴とする請求項1から5のいずれか1項に記載のパケット制御装置。

請求項7

前記確率決定部は、前記複数の区間と前記複数の廃棄確率候補値を対応付けたテーブルを有し、前記閾値決定部で前記複数の閾値が決定される度に、前記テーブルを更新し、前記テーブルを参照して、前記閾値処理の結果が示す区間に対応する前記廃棄確率候補値を、前記廃棄確率として抽出することを特徴とする請求項6に記載のパケット制御装置。

技術分野

0001

本発明は、バッファを有するパケット制御装置に関し、より詳細には、バッファが溢れないようにパケット廃棄するパケット制御装置に関するものである。

背景技術

0002

近年、通信を行うユーザ数の増加及びユーザ当りトラヒック量の増大に伴い、パケット制御装置において効率的な輻輳制御機能実装が重要となってきている。輻輳制御を実現する手法の一つとしてはRED(Random Early Detection)が挙げられる(例えば、非特許文献1参照)。

0003

REDは、パケット制御装置に到着するパケットを、バッファに格納する前に、設定された廃棄確率(パケットが廃棄される確率)に基づいてランダムに廃棄することで、バッファの溢れを回避する輻輳制御を行う。REDは、バッファ内に蓄積されたデータ量であるバッファ蓄積量を定期的に観測し、観測したバッファ蓄積量から上記廃棄確率を算出しており、上記廃棄確率はそのパケットを送信するユーザに依らず決定される。よって、REDでは、各ユーザ間で同一の廃棄確率となり、ユーザ間の公平性が確保される。

0004

REDは、廃棄確率の算出に複雑な演算処理が必要となることから、ハードウェアソフトウェアを組み合わせた手法で元来実現されてきた。しかし、この手法では、処理速度に大幅な時間を要することから、近年増加傾向にあるトラヒック量に対応できないことが予想される。

0005

この問題に対し、特許文献1では、ハードウェアのみでREDを実現する手法が提案されている。特許文献1に記載のパケット処理装置では、REDをハードウェアで実現するにあたり、廃棄確率の算出に用いるバッファ蓄積量の移動平均値を、均等な間隔の閾値閾値処理し、閾値処理した結果に対応する廃棄確率の値を、ルックアップテーブルを参照して得ている。このルックアップテーブルは、各閾値で区切られた区間のそれぞれに廃棄確率の値を関連付けたものである。以上のように、このパケット処理装置では、廃棄確率を求めるために、予め定められた均等な間隔での閾値処理とルックアップテーブルを用いた参照処理を採用することにより、限られたハードウェアリソースで効率的にREDを実現する。

0006

特開2005−94392号公報

先行技術

0007

S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance”,IEEE/ACMTrans. on Networking, vol.1, pp.397−413, Aug. 1993.

発明が解決しようとする課題

0008

しかしながら、特許文献1に記載のパケット処理装置は、閾値処理で用いる閾値の間隔が均等であり、かつREDとの処理速度の差を大きくするためには間隔をある程度広くする必要がある。これらの要因から、このパケット処理装置では、バッファ蓄積量の移動平均値の分布が特定の範囲に集中する場合に、トラヒック条件によっては、REDの利点の一つであるユーザ間の公平性が十分に確保できない。具体的には、ある閾値の近辺に移動平均値の分布が集中する場合には、バッファ蓄積量の微小増減で廃棄確率に大きな差が発生することになり、特定ユーザのパケットが到着した時のみバッファ蓄積量が僅かに増加するトラヒック条件を想定すると、同ユーザのパケットのみ廃棄確率が高くなり、他のユーザとの間に不公平が生じる。

0009

本発明は、上述のような実情に鑑みてなされたものであり、その目的は、バッファを有するパケット制御装置において、バッファが溢れないように到着パケットを廃棄するに際し、パケットを送信するユーザ間に不公平が生じ難いようにすることにある。

課題を解決するための手段

0010

本発明のパケット制御装置は、到着したパケットから廃棄確率に応じた量のパケットを廃棄するパケット廃棄部と、前記到着したパケットの内の、前記パケット廃棄部で廃棄されなかったパケットを一時的に蓄積してから出力するバッファと、前記バッファに蓄積されている前記パケットの蓄積量の移動平均値を逐次算出する平均値算出部と、前記平均値算出部で逐次算出された複数の移動平均値についての頻度分布を生成する統計処理部と、前記統計処理部で生成された前記頻度分布に応じて、前記移動平均値についての複数の閾値を決定する閾値決定部と、前記閾値決定部で決定された前記複数の閾値によって区切られた複数の区間のいずれかに、前記平均値算出部で算出された前記移動平均値を分類する閾値処理を実行し、前記閾値処理の結果に応じて前記廃棄確率を決定する確率決定部とを有することを特徴とする。

発明の効果

0011

本発明によれば、バッファを有し、バッファが溢れないように到着パケットを廃棄することが可能なパケット制御装置において、バッファ蓄積量の移動平均値の頻度分布に基づき移動平均値についての複数の閾値を決定し、それらの閾値を用いて廃棄確率を決定するため、パケットを送信するユーザ間に不公平が生じ難くなる。

図面の簡単な説明

0012

本発明の実施の形態1に係るパケット制御装置の一構成例を示すブロック図である。
比較例1におけるバッファ蓄積量の移動平均値と廃棄確率の関係を示す図である。
比較例2におけるバッファ蓄積量の移動平均値と廃棄確率の関係を、比較例1の関係と比較して示す図である。
比較例2におけるバッファ蓄積量の移動平均値と廃棄確率との関係を示す近似廃棄確率テーブルを示す図である。
図1のパケット制御装置における統計処理部で生成される頻度分布の一例を示す図である。
図1のパケット制御装置において決定される閾値と廃棄確率候補値の関係の一例を示す図である。
本発明の実施の形態1に係るパケット制御装置の他の構成例を示すブロック図である。
図7のパケット制御装置におけるテーブル更新処理の一例を示すフローチャートである。
図8のテーブル更新処理により更新されたテーブルの一例を示す図である。
本発明の実施の形態2に係るパケット制御装置で時間情報とともに蓄積されたバッファ蓄積量の移動平均値の一例を示す図である。
本発明の実施の形態2に係るパケット制御装置で閾値の決定に用いる頻度分布の一例を示す図である。
本発明の実施の形態3に係るパケット制御装置の一構成例を示すブロック図である。
本発明の実施の形態3に係るパケット制御装置の他の構成例を示すブロック図である。
本発明の実施の形態1〜3に係るパケット制御装置の他の構成例を示す図である。

実施例

0013

以下、本発明の各実施の形態に係るパケット制御装置について、図面を参照しながら説明する。本発明に係るパケット制御装置は、パケットで信号やデータが送信される様々なプロトコルを採用したネットワークにおいて、トラヒック輻輳を回避するために設置することができる。このパケット制御装置は、好適にはルータ又はサーバ装置などのゲートウェイ装置に組み込まれるが、例えばテレビ装置又は音声再生装置等の様々な電子機器におけるパケット入力部に組み込むこともできる。

0014

実施の形態1.
図1は、本発明の実施の形態1に係るパケット制御装置の一構成例を示すブロック図である。図1において、太線の矢印はパケットの流れ、細線の矢印は制御情報の流れを示している。

0015

図1で例示するパケット制御装置1は、パケット廃棄部11、パケット収容部として機能するバッファ12、平均値算出部13、確率決定部14、統計処理部15、及び閾値決定部16を有する。また、パケット制御装置1はその全体を制御する制御部(図示せず)を有するように構成しておいてもよい。パケット制御装置1に到着するパケットは、パケット廃棄部11及びバッファ12を経由して、パケット制御装置1から出力される。

0016

パケット廃棄部11は、確率決定部14にて決定された廃棄確率に応じた量、パケット制御装置1に到着したパケット、つまりパケット制御装置1に入力されたパケットを廃棄する。パケット廃棄部11は、到着したパケットから上記廃棄確率に応じた量のパケットを廃棄すればよく、上記廃棄確率に従ってランダムに廃棄対象とするのか通過対象とするのかを選択してもよいし、上記廃棄確率に合うような一定周期で廃棄対象を選択するなどしてもよい。

0017

バッファ12は、上記到着したパケットの内の、パケット廃棄部11で廃棄されなかったパケットを一時的に蓄積してから出力する。つまり、バッファ12は、パケット廃棄部11にて廃棄されずに通過されたパケットをパケット制御装置1から出力されるまで保持する。なお、バッファ12は、例えばFIFO(First In, First Out)でパケットを出力すればよいが、これに限ったものではない。また、バッファ12の容量、並びにパケット制御装置1におけるパケットの出力タイミングは、例えば、パケット制御装置1の後段に接続する装置での処理がオーバーフローしないように決めておけばよい。

0018

平均値算出部13は、バッファ12に蓄積されているパケットの蓄積量(以下、バッファ蓄積量と称す)の平均値を逐次算出する。ここで算出される平均値は、時系列データに基づき、予め定めた算出間隔で逐次算出される平均値、つまり移動平均値を意味する。ここで、平均値算出部13は、バッファ12の蓄積量、或いは蓄積可能な残量を上記算出間隔で計測監視)しておけばよい。若しくは、バッファ12が上記蓄積量又は上記残量の計測を行い、その計測結果を平均値算出部13に渡すようにしてもよい。また、他の実施の形態も含め、以下ではバッファ蓄積量に基づき、様々な処理を行うが、バッファ12の残量に基づき移動平均値を間接的に取得する処理についても本発明の概念に含まれる。

0019

確率決定部14は、上記廃棄確率を算出するか、或いは後述のテーブルを用いるなどして抽出することで上記廃棄確率を決定する。上記廃棄確率は、トラヒックの輻輳回避を図るために、バッファ12を溢れさせずバッファ12の容量に応じた適切な割合で、到着パケットを廃棄するように決定される。この決定方法の詳細については後述する。

0020

統計処理部15は、平均値算出部13で逐次算出された複数の移動平均値についての頻度分布(度数分布)を生成する。頻度分布の生成間隔は、平均値算出部13における移動平均値の算出間隔と同じであってもよいが、それより大きくしておくことが処理負荷低減の点から好ましい。また、統計処理部15は、頻度分布の生成のために、内部に記憶部15aを有し、その記憶部15aに、平均値算出部13で逐次算出された複数の移動平均値を入力して蓄積(保持)しておく。記憶部15aは統計処理部15の外部に設けられていてもよい。

0021

閾値決定部16は、統計処理部15で生成された頻度分布の情報(統計情報と称す)を入力し、その頻度分布に応じて、バッファ蓄積量の移動平均値についての複数の閾値を決定する。そして、確率決定部14は、閾値決定部16で決定された複数の閾値によって区切られた複数の区間のいずれかに、平均値算出部13で算出された移動平均値を分類する閾値処理を実行し、その閾値処理の結果(つまり分類結果)に応じてパケット廃棄部11で使用する上記廃棄確率を決定する。確率決定部14は、基本的に平均値算出部13での移動平均値の算出間隔と同じ間隔で閾値処理を行って上記廃棄確率を決定すればよいが、その算出間隔より長い確率決定間隔でそれらの処理を実行してもよい。

0022

本実施の形態における上記廃棄確率の決定について具体的に説明する前に、図2図4を参照しながら、REDに関する比較例1及び2について説明する。図2は、比較例1におけるバッファ蓄積量の移動平均値と廃棄確率の関係を示す図である。図3は、比較例2におけるバッファ蓄積量の移動平均値と廃棄確率の関係を、比較例1の関係と比較して示す図、図4は、比較例2におけるバッファ蓄積量の移動平均値と廃棄確率との関係を示す近似廃棄確率テーブルを示す図である。

0023

比較例1のパケット制御装置は、バッファ蓄積量の移動平均値を基に、パケットの廃棄確率を決定する。なお、ここでのバッファ蓄積量の移動平均値は、バッファ蓄積量の移動平均値をQav、現在のバッファ蓄積量をQ、重み係数をwとして、以下の式(1)にて定義される。
Qav←(1−w)×Qav+w×Q (1)

0024

また、図2に示すように比較例1では、バッファ蓄積量が最小閾値minTHを下回る場合、パケットが全く廃棄されず(廃棄確率が0%となり)、バッファ蓄積量が最大閾値maxTHを上回る場合、パケットが全て廃棄される(廃棄確率が100%となる)。バッファ蓄積量がminTH以上、maxTH以下の場合には、図2の廃棄確率直線Krで示したようなバッファ蓄積量の値に応じた廃棄確率に基づき、パケットが廃棄される。なお、図2において、maxPは最大閾値maxTHにおける廃棄確率であり、廃棄確率直線Krの傾きを決定するパラメータである。

0025

一方で、比較例2のパケット制御装置は、近似廃棄確率テーブルと呼ばれる、バッファ蓄積量の移動平均値と廃棄確率を関連付けたテーブルを用いて、比較例1における廃棄確率を算出している。この近似廃棄確率テーブルは、比較例1の3つのパラメータminTH,maxTH,maxPを基に予め生成されている。具体的には、この近似廃棄確率テーブルは、基本的に比較例1の最小閾値minTHと最大閾値maxTHの間のバッファ蓄積量をN等分して得られる、図3の廃棄確率線Kpで示したようなバッファ蓄積量の移動平均値と廃棄確率の関係を予めテーブル化したものであり、図4で示すような近似廃棄確率テーブルである。例えば、比較例2のパケット制御装置は、予め定められた図4の近似廃棄確率テーブルを参照し、現在のバッファ蓄積量の移動平均値が70.00%の場合、廃棄確率候補値の中から37.5%を選択して廃棄確率に設定し、その廃棄確率に従い到着パケットを廃棄する。なお、図4では簡略化して記述しているが、バッファ蓄積量の移動平均値は、例えば2行目で56.25(%)以上、62.50(%)未満を指しており、他の行も同様である。但し、図4最下行については移動平均値が100.00(%)を指す。

0026

ここで、図3において、例えば図中の領域Raのような閾値近辺の特定の領域にバッファ蓄積量の移動平均値の分布が集中する場合について、廃棄確率線Kpを比較例1の廃棄確率直線Krと比較する。領域Raにおいて、比較例1における廃棄確率の差Drは小さいが、比較例2における廃棄確率の差Dpは大きくなっており、これは比較例2のパケット制御装置が等間隔でN段階に閾値処理しているため、並びに分布とは無関係に予め定められた固定の閾値群で閾値処理を実行しているためである。よって、比較例1においては、上記の分布が領域Raに集中する場合でも、到着するパケット間で廃棄確率に大きな差が発生しないため、どのようなトラヒック条件でもユーザ間に不公平は生じない。一方で、比較例2においては、上記の分布が領域Raに集中する場合、バッファ蓄積量の微小な増減で廃棄確率に量子化に起因する大きな差が生じることから、到着するパケット間で廃棄確率に大きな差が発生するため、特定ユーザのパケットが比較例2のパケット制御装置に到着した時のみバッファ蓄積量が僅かに増加するトラヒック条件を想定すると、同ユーザのパケットのみ廃棄確率が高くなり、パケットを送信するユーザ間で不公平が生じる。

0027

このような不公平性を低減させるために、本実施の形態では、上述したようにバッファ蓄積量の移動平均値の頻度分布に応じて複数の閾値を決定してそれらの閾値を用いて廃棄確率を決定する。以下、図5及び図6を併せて参照しながら、このような処理について具体例を挙げて説明する。図5は、パケット制御装置1における統計処理部15で生成される頻度分布の一例を示す図、図6は、パケット制御装置1において決定される閾値と廃棄確率候補値の関係の一例を示す図である。

0028

まず、平均値算出部13は、上述したようにバッファ蓄積量の移動平均値を算出するが、その移動平均値の算出式としては式(1)が利用できる。本実施の形態では、この算出式の代わりに他の種類の重み付け手法を適用した算出式を採用することもできる。但し、式(1)の演算は、平均値算出部13をハードウェアで構成できる点、及び過去の移動平均値と現在のバッファ蓄積量のみから実行できるため処理速度が速い点から望ましい。

0029

式(1)を利用する場合、平均値算出部13は、その内部又は外部に、過去の移動平均量を格納しておき、移動平均値を算出する度に上書きするような移動平均値記憶部(図示せず)を設けておけばよい。また、式(1)では過去のバッファ蓄積量が算出結果に影響を与える式となっているが、遠い過去のバッファ蓄積量の影響はその値に重み付け係数(1−w)が累積されるため少ない。他の種類の重み付け手法を適用する場合にも、平均値算出部13の内部又は外部に、現在までの過去のバッファ蓄積量を記憶する蓄積量記憶部(図示せず)を設けておけばよく、これにより、現在のバッファ蓄積量の移動平均値を算出時には平均値算出部13がその蓄積量記憶部に記憶されたバッファ蓄積量を読み出すことができる。

0030

式(1)を利用する場合には現在までのバッファ蓄積量を全て反映させることを前提とし、また、上記蓄積量記憶部が現在までの全てのバッファ蓄積量を記憶することを前提として説明した。しかし、平均値算出部13は、現在の移動平均値の算出に際し、過去の全てのバッファ蓄積量を用いなくてもよい。式(1)を採用する場合には、例えばパケット制御装置1に別途設けたリセットタンの押下により、或いは電源オフ後電源オンにより、平均値算出部13等が、上記移動平均値記憶部に記憶された過去の移動平均値のデータも消去するようにすればよい。式(1)のような過去の移動平均値をそのまま利用するのではなく、過去のバッファ蓄積量のデータを利用する方式で現在の移動平均値を算出する場合、上記リセットボタン或いは電源オフ後の電源オンにより、平均値算出部13等が、蓄積量記憶部に記憶された過去のバッファ蓄積量のデータを消去するようにすればよい。この代替処理として、平均値算出部13が、上記蓄積量記憶部に現在から一定期間前までの過去のバッファ蓄積量を記憶するように、つまりそれ以前のバッファ蓄積量を消去していくようにしておいてもよい。なお、パケット制御装置1において、記憶部15aと上記移動平均値記憶部又は上記蓄積量記憶部は共通の記憶装置を利用することができる。

0031

平均値算出部13で逐次算出された移動平均値は、確率決定部14及び統計処理部15に逐次出力される。統計処理部15は、これらの移動平均値を記憶部15aに記憶し、記憶された移動平均値について、頻度分布を生成する。この頻度分布としては、図5で例示するようなヒストグラム度数分布図)であってもよいし、例示したヒストグラムを図示できるような、ビンBの値(移動平均値)とその頻度値とを関連付けたルックアップテーブル(以下、頻度テーブルと称す)であってもよい。但し、後述する閾値決定処理は少なくとも頻度テーブルがあれば実行できるため、頻度テーブルを生成するだけで十分である。なお、図5縦軸は、バッファ12におけるバッファ蓄積量の移動平均値の頻度発生頻度)であり、全ユーザ(具体的には全ユーザの端末)から送信されたパケットについての合計の頻度を表している。

0032

この頻度分布におけるビンBの幅及び数は、比較例1で使用したような最小閾値minTH及び最大閾値maxTHに基づき、予め決めておいたものを用いてもよいし、単純に平均値算出部13において算出できる単位をビンの幅とし、算出された移動平均値をそのまま各ビンBに割り当てるようにして、ビンBの数だけ最小閾値minTH及び最大閾値maxTHに基づき決定してもよい。ビンBの数は、最大閾値maxTHと最小閾値minTHの差をビンの幅で除算することで算出することができる。なお、除算に際しては、実際には天井関数を用いるなどして整数化も併せて施すようにしておけばよく、その場合、頻度分布における両端の幅を増減させるなどの処理が必要となる場合がある。

0033

ここでは、比較例1における最小閾値minTH及び最大閾値maxTHを使用した例を挙げたが、本実施の形態における最小閾値及び最大閾値は、それぞれ0%及び100%としてもよいし、いずれも変動値であってもよい。最小閾値及び最大閾値を変動値とする例では、統計処理部15は、記憶部15aに記憶された移動平均値を参照し、実際の移動平均値の最小値及び最大値をそれぞれ最小閾値及び最大閾値として使用するようにすればよい。この場合、ビンの幅又は数を予め決めておけばよい。ビンの幅が決まっていれば、上述したようにビンの数を算出することができ、この場合にも整数化を行うに際しては、頻度分布における両端の幅を増減させるなどの処理が必要となることもある。逆にビンの数が決まっていれば、最大閾値と最小閾値との差をビンの数で除算することで、ビンの幅を算出することができる。

0034

また、記憶部15aには、生成された頻度分布の情報(統計情報)も記憶しておくことで、その統計情報を利用して次回の統計情報の生成を実行することができる。例えば、統計処理部15は、現在の移動平均値を平均値算出部13から受けた場合、その時点での統計情報に対しその移動平均値に対応する頻度値を1だけ増加させる処理のみで、統計情報の更新が可能となる。

0035

また、記憶部15aに蓄積した移動平均値は、一定期間の経過により、若しくは上述したリセットボタンの押下や電源オフ後の電源オンにより、削除されるようにすることもできる。これにより、統計処理部15は、最近の傾向をより反映した頻度分布を得、閾値決定部16においても閾値等の決定にそれを利用することができる。一定期間の経過により記憶部15aに蓄積した移動平均値を削除する場合、統計処理部15は、移動平均値を時間情報とともに記憶部15aに記憶させておけばよい。また、統計処理部15は、記憶部15aに生成された統計情報も併せて記憶させておくことで、削除対象の移動平均値に対応する頻度値を1だけ減少させる処理のみで、統計情報の更新が可能となる。

0036

閾値決定部16は、統計処理部15で生成された統計情報を入力し、その統計情報によって示された頻度分布に応じて、バッファ蓄積量の移動平均値についての複数の閾値(上記廃棄確率の決定に使用する複数の閾値)を決定する。なお、閾値決定部16では、基本的に統計処理部15で使用した最小閾値及び最大閾値をそのまま利用し、それらが示す範囲内の閾値を決定すればよく、以下ではそのような例を挙げる。但し、閾値決定部16は、統計処理部15で使用した最小閾値及び最大閾値が示す範囲を絞る又は拡げるように、別途、最小閾値及び最大閾値を決定してもよい。

0037

閾値決定部16における閾値決定処理の一例について説明する。図5では、生成されたヒストグラムに基づき、各ビンBの頻度値を結んだ頻度曲線Fdを描いた結果も示している。閾値決定部16は、統計処理部15からヒストグラムを入力し、このような頻度曲線Fdを導出する。この頻度曲線Fdは上記頻度テーブルのみから導出することもできる。頻度曲線Fdの導出処理は統計処理部15側が担ってもよい。

0038

次いで、閾値決定部16(又は統計処理部15)は、頻度曲線Fdとバッファ蓄積量の移動平均値の軸とで囲まれる面積Sを算出する。閾値決定部16(又は統計処理部15)は、頻度曲線Fdを得ずとも上記頻度テーブルのみから、[ビンBの幅]×[その頻度値]を全てのビンBについて足し合わせることで、面積Sを算出するように構成することもできる。

0039

そして、閾値決定部16は、取得したヒストグラムを面積SがN等分(S1=S2=…=SN=S/N)となるように分割し、その分割した境界である分割点X0,X1,…,XNを算出する。ここで、Nは予め定めておいた閾値の数であり、X0は最小閾値minTH、XNは最大閾値maxTHにそれぞれ予め定めておく。なお、S=S1+S2+…+SNである。また、この分割も上記頻度テーブルのみから実行することができる。各ビンBについて別途、累積頻度値を算出しておけば、面積SのN等分の値に該当する累積頻度値を示すビンBを得ることができ、同様に面積Sのk/Nの値に該当する累積頻度値を示すビンBを得ることもできる。このように、閾値決定部16は上記頻度テーブルを有するように構成することができる。

0040

図5からも分かるように、面積SをN等分することから、頻度値が小さい範囲では頻度値が大きい範囲に比べて、隣り合う分割点同士の差が広くなる。例えば、X0からX1の間では頻度値がXk−1からXkの間のような他の範囲に比べて小さく、分割点の差ΔX1が差ΔXkのような他の範囲に比べて広くなる。

0041

そして、閾値決定部16は、分割点X0,X1,…,XNをバッファ蓄積量の移動平均値の代表値(以下、移動平均代表値と称す)とする。また、閾値決定部16は、図6で例示したように、決定した移動平均代表値と隣接する移動平均代表値の平均値を閾値Y1,Y2,…,YNに決定する。具体的には、例えば、閾値決定部16は、式、Yk=(Xk−1+Xk)/2により閾値Ykを決定する。図6で示すように、隣り合う閾値Yk−1,Ykによって区切られた区間Δk(k=1,2,…,N)は、移動平均値の頻度が大きい区間では狭く(例えば区間Δ5,Δ6)、頻度が小さい区間では広く(例えば区間Δ2,Δ3)なっている。閾値決定部16は、決定した閾値を確率決定部14に出力(通知)する。なお、ここで説明している例では、閾値決定部16は移動平均代表値を確率決定部14に出力しない。

0042

また、ここでは、分割点Xkを移動平均代表値とし、隣り合う分割点の平均値Ykを閾値とした例を挙げて説明しているが、閾値決定部16は、分割点Xkを閾値に決定し、隣り合う分割点の平均値Yk(=(Xk−1+Xk)/2)を移動平均代表値に決定してもよい。

0043

図5を参照し、面積SをN等分することにより閾値を決定した例を挙げているが、この例のように、閾値決定部16は、頻度分布によって示される移動平均値の頻度が高いほど、区間が狭くなるように複数の閾値を決定することが好ましい。このように、閾値決定部16において、頻度値が大きい範囲(移動平均値の範囲)では区間(隣り合う閾値の間隔)を狭く、頻度値が小さい範囲では区間を広くすることで、バッファ蓄積量の移動平均値の分布が集中する部分に閾値を多く配置することができる。

0044

他の方法でもこのような傾向での閾値の決定を実現することは可能である。例えば、閾値決定部16は、最も頻度値の高い移動平均値を抽出し、その移動平均値を中心とする一定範囲(例えば中心から一定数のビンだけ離れた範囲)を求め、それ以外の範囲を上記一定範囲より広い他の一定範囲とする。そして、閾値決定部16は、これらの範囲の境界を閾値として決定する。

0045

次に確率決定部14における確率決定処理の一例について説明する。確率決定部14は、閾値決定部16で決定された複数の閾値によって区切られた複数の区間に対応する複数の廃棄確率候補値を決定することが好ましい。パケット制御装置1は、確率決定部14の内部又は外部に、閾値決定部16で決定された閾値を記憶する閾値記憶部及び廃棄確率候補値を記憶する廃棄確率候補値記憶部を備えるとともに、いずれかの記憶部において廃棄確率候補値と区間(又はその両端の閾値)との関連付けに関する情報も記憶させる。この閾値記憶部は、区間のそれぞれに対応するような電圧値を出力するような可変抵抗器等の電気素子代用することもできる。廃棄確率候補値記憶部は、廃棄確率候補値のそれぞれに対応するような電圧値を出力するような可変抵抗器等の電気素子で代用することもできる。

0046

具体的には、確率決定部14は、閾値決定部16から複数の閾値が入力された場合、過去の複数の閾値を入力された値で更新するとともに、例えば図6に示す廃棄確率線Kiのように複数の区間に一対一に対応する複数の廃棄確率候補値を算出する。廃棄確率線Kiの例では、隣り合う閾値Yk−1,Ykによって区切られた区間Δk(k=1,2,…,N)のそれぞれに対し、最小値0%から最大値maxPまで隣り合う廃棄確率候補値Pk−1,Pkの間隔と区間Δkとが比例するように、廃棄確率候補値P1,P2,…,Pk−1,…PN−1を算出している。この比例係数は、比較例1の廃棄確率直線Krの傾きと同じにしているが、これに限ったものではない。

0047

また、確率決定部14は、予め用意された比較例1の廃棄確率直線Krにおける、各区間Δkの中央値(移動平均代表値Xk−1に相当)に対応する廃棄確率の値を算出することで、若しくは予め記憶された対応関係を参照して抽出することで、その区間における廃棄確率候補値Pk−1を決定してもよい。

0048

そして、確率決定部14は、平均値算出部13で算出された移動平均値に閾値処理を施し、上記複数の区間のうちのその閾値処理の結果が示す区間に対応する、上記複数の廃棄確率候補値のうちの廃棄確率候補値を、廃棄確率とし、パケット廃棄部11に出力する。図6の例で簡略化して説明すると、確率決定部14は、廃棄確率線Ki(又はその関係を記した情報)を参照して、入力された移動平均値から廃棄確率を決定する。

0049

これにより、パケット廃棄部11では、現在の移動平均値と移動平均値の分布とに応じた廃棄確率で、到着パケットの廃棄を実行することができる。例えば図6においてd2で示した部分において、廃棄確率候補値がP1からP2へと大きく変化しているが、この部分を含む区間ΔX2においてはパケット蓄積量の移動平均値の頻度が少ない(つまり平均値算出部13からこの近辺に該当する移動平均値が入力されることは少ない)。一方で、例えば図6においてd5で示した部分においては、この部分を含む区間ΔX5においてはパケット蓄積量の移動平均値の頻度が大きい(つまり平均値算出部13からこの近辺に該当する移動平均値の入力が集中する)が、廃棄確率候補値の変化が小さい。従って、本実施の形態では、全体的に見ると、ユーザ間での不公平さが残る頻度が少なく、公平性を高めることができる。

0050

なお、上述した例では、閾値決定部16が移動平均代表値を決定しているが、決定しない例も採用できる。例えば分割点Xkを閾値に決定し、隣り合う分割点の平均値Ykの算出を行わなければよい。このような例においても、確率決定部14は、複数の閾値によって区切られた複数の区間に対応する複数の廃棄確率候補値を決定でき、かつ平均値算出部13から入力された移動平均値に閾値処理を施すこともできるため、パケット廃棄部11に出力する廃棄確率を決定することができる。

0051

図7には、図1のパケット制御装置1とは異なる構成例のパケット制御装置1aを示している。パケット制御装置1aで示すように、確率決定部14の代わりに設ける確率決定部24は、複数の区間と複数の廃棄確率候補値を対応付けたテーブル(ルックアップテーブル)24tを有する。なお、テーブル24tは確率決定部24の内部の記憶部に格納しておけばよいが、テーブル24tを確率決定部24と別のハードウェアとして構成してもよい。また、上述の閾値記憶部及び廃棄確率候補値記憶部は、テーブル24tを記憶する記憶部であってもよい。

0052

また、確率決定部24は、閾値決定部16で複数の閾値が決定される度に、それらの閾値を入力し、それらの閾値に応じて廃棄確率候補値を決定し、その結果でテーブル24tを更新すればよい。テーブル24tは、形式的には図4の近似廃棄確率テーブルと同じとなる。しかし、上述のように、閾値決定部16では区間の幅が異なることを許容して閾値を決め、閾値に応じて廃棄確率候補値を決めているため、テーブル24tはこれらの値が図4の近似廃棄確率テーブルと異なる。

0053

そして、確率決定部24は、テーブル24tを参照して、平均値算出部13から入力された現在の移動平均値に閾値処理を施して、その閾値処理の結果が示す区間に対応する廃棄確率候補値を、パケット廃棄部11に出力する廃棄確率として抽出する。このように、確率決定部24は、テーブル24tを有するように構成することで、そのテーブル24tを更新、参照するだけの処理で済む。

0054

以上のように、本実施の形態では、バッファ蓄積量の移動平均値についての頻度分布を活用して、バッファ蓄積量の移動平均値についての複数の閾値を決定し、それらの閾値に基づき廃棄確率を決定し、バッファ蓄積量の移動平均値の分布が集中する部分(となる部分)に多くの閾値を配置しかつ分布が疎となる部分に少ない閾値を配置している。よって、本実施の形態では、移動平均値の分布が集中する部分においてパケット間の廃棄確率に大きな差が発生するのを防ぎ、パケットを送信するユーザ間に不公平が生じ難くなり、ユーザ間の公平性を図ることができる。また、本実施の形態では、ハードウェアによる構成が可能であり、比較例1より処理速度が速い。また、閾値及び廃棄確率候補値の更新処理の間隔を、それらの値を用いた現在の廃棄確率の決定処理の間隔より長くすることで、特に処理の負荷を減らすことができる。

0055

以上の例では、平均値算出部13から出力された移動平均値に閾値処理を施すことにより廃棄確率を決定したが、廃棄確率の決定に際し、一旦、移動平均値を閾値処理して移動平均代表値に変換してから(換言すれば量子化してから)、廃棄確率の決定を行うようにしてもよい。この場合の量子化は、閾値の間隔に対応する量子化ステップ幅が一定ではないため、非線形量子化に該当する。また、この場合、閾値は量子化閾値を意味し、移動平均代表値は量子化代表値を意味する。

0056

このような非線形量子化を用いた廃棄確率の決定方法の一例について説明する。但し、ここでは、図5及び図6を参照して説明した廃棄確率の決定方法の流れの一例を、非線形量子化といった観点から再度、簡略化して説明するとともに、現在の移動平均値を移動平均代表値(量子化代表値)に変換してから廃棄確率を決定するような応用例を採用する場合の変更箇所の説明を行う。

0057

本例において、閾値決定部16は、量子化閾値だけでなく量子化代表値も決定し、確率決定部24に出力するようにしておく。確率決定部24は、量子化代表値のそれぞれに廃棄確率候補値を関連付けて記憶する。本例においてもテーブル24tのようなルックアップテーブルを用いることができる。上記応用例においては、テーブル24tには、量子化閾値の代わりに量子化代表値が記述されることになる。以下、テーブル24tを用いる例を挙げて説明するが、用いない例でも同様に非線形量子化を利用することができる。

0058

まず、テーブル24tにおける量子化代表値の初期値としては、例えばバッファ蓄積量を均等にN等分した場合の値としておく。なお、この例においても、量子化代表値、量子化閾値、及び廃棄確率候補値の更新処理(この例ではテーブル24tの更新処理)とそれらの値を用いた現在の廃棄確率の決定処理とを、同じ時間間隔で定期的に行えばよい。この例においては、上記同じ時間間隔が量子化周期を指すこととなる。

0059

このようなテーブル24tの更新処理の一例について、図8及び図9を併せて参照しながら説明する。図8図7のパケット制御装置1aにおけるテーブル更新処理の一例を示すフローチャート、図9は、図8のテーブル更新処理により更新されたテーブルの一例を示す図である。

0060

まず、統計処理部15が平均値算出部13から入力されたバッファ蓄積量の移動平均値についての頻度分布(図5で示したようなヒストグラムで例示)を生成し、閾値決定部16がその頻度分布を示す統計情報を取得する(ステップS1)。次いで、閾値決定部16が、その統計情報によって示されるヒストグラムを面積が均等になるようにN分割し(ステップS2)、N分割した時の境界となる値を量子化代表値に決定し(ステップS3)、隣り合う量子化代表値の平均値を量子化閾値に決定する(ステップS4)。次に、閾値決定部16は、確率決定部24に量子化代表値と量子化閾値を通知する(ステップS5)。これらの処理の詳細については図5及び図6を用いて説明した通りである。

0061

次いで、確率決定部24は、閾値決定部16から量子化代表値及び量子化閾値が入力される度に、量子化代表値(又は量子化閾値)に基づき廃棄確率候補値(例えば図6の廃棄確率候補値P1,P2,…,PN−1)を算出する(ステップS6)。この算出処理の詳細についても図6を用いて説明した通りである。

0062

次いで、確率決定部24は、量子化閾値及び廃棄確率候補値に基づき、近似廃棄確率のテーブル24tを更新する(ステップS7)。このテーブル24tは、図9で例示できる。なお、図9においてY1,Y2,…,YNは量子化閾値を指す。また、図9では簡略化して記述しているが、バッファ蓄積量の移動平均値は、例えば2行目でminTH(%)以上、Y1(%)未満を指しており、他の行も同様である。また、図9の最下行については移動平均値がmaxTH(%)以上を指している。上記応用例では、ステップS7において、量子化閾値の代わりに量子化代表値を用い、複数の量子化代表値と複数の廃棄確率候補値とを一対一に対応付けるようにテーブル24tを更新する。

0063

以上のようにしてテーブル24tが更新される。その後の確率決定部24における現在の移動平均値に対応する廃棄確率の決定については上述した通りである。但し、上記応用例ではテーブル24tにおいて量子化閾値の代わりに量子化代表値が記述されているため、現在の移動平均値の単なる閾値処理ではそのテーブル24tを参照できない。

0064

よって、上記応用例では、確率決定部24は、平均値算出部13から入力された現在の移動平均値に対し、閾値決定部16で決定された複数の量子化閾値及び複数の量子化代表値に基づき量子化(非線形量子化)を施し、量子化代表値に変換する。つまり、確率決定部24は、入力された現在の移動平均値を、量子化閾値によって区切られた複数の区間のいずれかに分類し、分類した結果が示す区間に対応付けられた量子化代表値に変換する。その後、確率決定部24が、テーブル24tを参照して、量子化した結果の量子化代表値に対応付けられた廃棄確率候補値を抽出し、抽出した廃棄確率候補値を廃棄確率としてパケット廃棄部11に出力する。

0065

上記応用例においてテーブル24tを用いる場合、複数の量子化閾値と複数の量子化代表値とを一対一に対応付けたテーブルと、複数の量子化代表値と複数の廃棄確率候補値とを一対一に対応付けたテーブルの、2つのテーブルで構成しておく。また、上記応用例においては、量子化代表値は量子化インデックスなどのより情報量の少ない値としてもよい。

0066

また、以上では、閾値及び廃棄確率候補値の更新処理(例えばテーブル24tの更新処理)とそれらの値を用いた現在の廃棄確率の決定処理とを、上記同じ時間間隔で定期的に行うこと、或いは特に閾値及び廃棄確率候補値の更新処理の間隔を、それらの値を用いた現在の廃棄確率の決定処理の間隔より長くすることを前提として、本実施の形態の説明を行った。

0067

しかし、上述の更新処理は、一定の時間間隔で実行しないようにしてもよい。例えば、統計処理部15で一定量の統計情報を取得する度に、閾値決定部16が閾値を更新し、確率決定部14又は確率決定部24がそれに合わせて廃棄確率候補値等の更新処理(例えばテーブル24tの更新処理)を実行するようにしてもよい。

0068

このような処理の一例について説明する。まず、平均値算出部13は、移動平均値を算出した結果、一定値(例えば図5及び図6のminTH等)より小さい場合、その結果を統計処理部15に出力しないように構成しておく。なお、この場合にも平均値算出部13は確率決定部14又は確率決定部24にはその結果を出力するように構成しておいてもよい。平均値算出部13は結果に関係なく統計処理部15に移動平均値を出力するようにしておき、統計処理部15は、その結果が上記一定値より小さい場合にその結果を無視し、上記一定値以上の場合にのみ有効な移動平均値として取り扱うようにしてもよい。

0069

そして、統計処理部15は、一定量の有効な移動平均値を取得する度に、つまり一定量の統計情報を取得する度に、閾値決定部16に閾値の更新タイミングであることを通知する。若しくは、閾値決定部16が統計処理部15での統計情報の蓄積量を監視し、一定の蓄積量だけ増えたタイミングを更新タイミングとして決定する。いずれの場合でも、閾値決定部16は、更新タイミングで閾値の更新処理を実行し、その結果を受けた確率決定部14又は確率決定部24は、廃棄確率候補値等の更新処理を実行する。また、このようにして更新タイミングを決定する場合には、統計処理部15は、上記一定の蓄積量を超える古い統計情報は廃棄するようにしておくか、若しくは閾値決定部16での参照対象としないようにしておくことが好ましい。

0070

このような処理により、パケット制御装置1,1aへの入力レートが高い場合には多くの統計情報が取得できるため更新間隔が短くなり、入力レートが低い場合には少ししか統計情報が取得できないため更新間隔が長くなる。つまり、このような処理により、入力レートに依らず同量の統計情報(サンプル数)が蓄積されたタイミングで、更新処理が実行でき、以下のような効果を奏する。

0071

すなわち、入力レートが高い場合には、一定量の統計情報を取得する度に更新処理を実行すると、定期的な更新処理に比べ、十分な統計情報が獲得できた段階で即座に閾値を更新できる(最新の統計情報に最適化できる)ことから、常に高い公平性を確保しておくことができる。また、入力レートが低い場合には、一定量の統計情報を取得する度に更新処理を実行すると、定期的な更新処理に比べ、更新に意味のあるタイミングで閾値を更新するため、不必要な演算処理が実施されず、処理時間を抑制できる。

0072

実施の形態2.
本発明の実施の形態2に係るパケット制御装置について、図10及び図11を併せて参照しながら説明する。本実施の形態に係るパケット制御装置の構成は基本的に図1又は図7と同様である。その他、本実施の形態においても実施の形態1で説明した様々な例が適用できる。図10は、本実施の形態に係るパケット制御装置で時間情報とともに蓄積されたバッファ蓄積量の移動平均値の一例を示す図、図11は、このパケット制御装置で閾値の決定に用いる統計情報の一例を示す図である。

0073

実施の形態1では、バッファ蓄積量の移動平均値についての頻度分布に応じて複数の閾値を決定してそれらの閾値に基づき廃棄確率を決定しているが、本実施の形態では、その頻度分布を現在のバッファ蓄積量の移動平均値に近い情報から生成する。具体的には、本実施形態における統計処理部15は、平均値算出部13で算出された複数の移動平均値のうちの、現在の移動平均値と同じ値を持つ過去の移動平均値の算出時点を含む算出期間について、頻度分布を生成する。

0074

より詳細に説明すると、統計処理部15は、まず図10で例示するようなバッファ蓄積量の移動平均値の時系列データX(t)を使用し、図中のNOWで示す現在時刻のバッファ蓄積量の移動平均値XPと同じ値を持つ過去の移動平均値及びその算出時刻(算出日も含めた算出日時が好ましい)を抽出する。そして、統計処理部15は、その算出日時を始点として算出期間Tが経過するまでに算出された移動平均値のみを、統計処理の対象として抽出し、頻度分布を生成する。上記算出期間Tは予め定めた期間としておけばよい。また、現在のバッファ蓄積量の移動平均値も統計処理の対象としてカウントしてもよい。統計処理部15は、図10で例示した時系列データX(t)のように対象となる始点が複数存在する場合にはその全てについて抽出する。

0075

なお、統計処理部15は、上記算出日時を始点とするのではなく、上記算出日時を含む算出期間T以内で算出された移動平均値のみを統計処理の対象としてもよいが、基本的には現時点から未来で発生する可能性があるバッファ12の溢れに対処する必要があるため、算出期間Tは上記算出日時より新しい移動平均値を多く含めるように決めておくことが好ましい。

0076

図11で例示するように、上記算出日時を始点等として含む算出期間Tにおける移動平均値から生成されたヒストグラムHTは、実施の形態1でのように全期間の移動平均値から生成されたヒストグラムHAに比べると、基本的に現在のバッファ蓄積量の移動平均値XP付近で他の範囲に比べて頻度が高くなるようになる。

0077

上述のように生成されたヒストグラムは、実施の形態1と同様に、閾値決定部16において閾値等を決定する処理に用いられ、それ以降の処理も実施の形態1と同様になる。その結果、ヒストグラムHTから決定された閾値は、ヒストグラムHAから決定された閾値に比べて、現在のバッファ蓄積量の移動平均値XP近辺に多く配置できる。よって、本実施の形態では実施の形態1と比較すると、パケット間の廃棄確率に大きな差が発生し難くなり、さらなるユーザ間の公平性の確保が可能になる。

0078

また、以上の例では、統計処理部15が上記算出日時を含む算出期間Tについての移動平均値から頻度分布を生成したが、現在のバッファ蓄積量の移動平均値に近い過去の移動平均値の抽出方法抽出条件)はこれに限ったものではない。例えば、統計処理部15は、現在のバッファ蓄積量の移動平均値XPとの差が一定値に収まる値を持つ過去の移動平均値及びその算出日時を抽出し、その算出日時を含む算出期間T以内に算出された移動平均値のみを、頻度分布の生成に用いる。この場合、重複するデータが存在するが、重複分は1つのみ用いるものとする。

0079

その他の例を挙げると、統計処理部15は、現在の移動平均値XPから算出期間T(又は長さが異なる算出期間)遡った移動平均値を参照して現在が増加傾向であるのか減少傾向であるのかを判定する。そして、統計処理部15は、移動平均値XPと同じ(又は差が一定値に収まる)過去の移動平均値の算出日時を含む算出期間T内で算出された移動平均値のうち、現在の傾向と同じ傾向をもつもののみから頻度分布の生成を行う。図10の例では現在が減少傾向であるため、時系列データX(t)において4箇所存在する算出期間Tのうち、3番目の算出期間Tについての移動平均値のみから頻度分布を生成することになる。このような抽出条件を採用することで、結果として移動平均値XP近辺に多くの閾値が配置されることになるだけでなく、時系列データX(t)に基づく予測も反映できるようになる。

0080

実施の形態3.
本発明の実施の形態3について、図12及び図13を参照しながら説明する。図12は、本実施の形態に係るパケット制御装置の一構成例を示すブロック図、図13は、その他の構成例を示すブロック図である。本実施の形態について実施の形態1における図1のパケット制御装置1との相違点を中心に説明するが、本実施の形態においても実施の形態1及び2で説明した様々な例が適用できる。

0081

実施の形態1では、輻輳制御方式としてREDを利用した例を挙げ、パケット制御装置1に到着するパケットが1種類であること、或いは複数種類存在したとしてもその種類毎に処理を異ならせないことを前提としている。本実施の形態に係るパケット制御装置は、到着するパケットが複数種類存在する場合に、種類毎に処理を異ならせるようにしたものである。

0082

図12で例示するように、本実施の形態の一構成例に係るパケット制御装置1bは、図1のパケット制御装置1の構成に加え、到着したパケットの種類である到着種類を判別する判別部17を有する。パケット制御装置1bはさらに確率決定部を有する。この確率決定部は、予め決められたパケットの種類である基準種類毎に廃棄確率を決定するものであり、例えば図1の確率決定部14を基準種類の数だけ設けることで構成することができる。

0083

ここではパケットの種類として、高優先度、中優先度、及び低優先度のいずれかを示す優先度情報が付加された優先度付きのパケットを考慮し、3つの確率決定部14を設けた例を挙げており、それらを第1の確率決定部14a、第2の確率決定部14b、及び第3の確率決定部14cと称する。但し、確率決定部14a〜14cをハードウェアで構成するに際しても、1つのハードウェアとして構成することもできる。

0084

本実施の形態における判別部17は、パケット廃棄部11に対し、到着したパケットだけでなく到着種類を示す情報を送信する。パケット廃棄部11は、この到着種類を示す情報を入力し、この到着種類に属するパケットを、その到着種類に対応する基準種類についての廃棄確率に応じた量、廃棄する。そのため、パケット廃棄部11には基準種類のそれぞれに対応する廃棄確率が設定される。この例では、到着種類を示す情報は、優先度を判別した結果(優先度情報)に該当し、パケット廃棄部11には基準種類の例としての優先度の種類に対応する3つの廃棄確率が設定される。

0085

つまり、第1の確率決定部14aが基準種類の1つとしての高優先度に対する廃棄確率Paを決定し、第2の確率決定部14bが基準種類の1つとしての中優先度に対する廃棄確率Pbを決定し、第3の確率決定部14cが基準種類の1つとしての低優先度に対する廃棄確率Pcを決定し、それぞれパケット廃棄部11に出力する。

0086

具体的に廃棄確率Pa〜Pcの決定方法について説明する。まず、閾値決定部16は実施の形態1と同様に複数の閾値(以下、閾値群と称す)を決定し、第1〜第3の確率決定部14a〜14cに出力する。第1〜第3の確率決定部14a〜14cはいずれも共通の閾値群を受け取ることになる。なお、閾値決定部16で閾値群の決定の際に用いる頻度分布も共通であり、統計処理部15は、基準種類毎に統計処理を行うわけではない。つまり、統計処理部15は、高優先度、中優先度、及び低優先度のそれぞれについて別個に統計処理を行うわけではない。

0087

第1の確率決定部14aは、閾値群によって区切られた複数の区間のそれぞれについて、高優先度用の廃棄確率候補値を決定し、対応する隣り合う閾値(閾値群の中の隣り合う閾値)又は対応する区間に関連付けておく。また、第2の確率決定部14bは、閾値群によって区切られた複数の区間のそれぞれについて、高優先度用に比べて大きな値となるように中優先度用の廃棄確率候補値を決定し、対応する隣り合う閾値又は対応する区間に関連付けておく。補足すると、このような決定により、ある1つの区間Δkに対応する中優先度用の廃棄確率候補値はその区間Δkに対応する高優先度用の廃棄確率候補値に比べて大きな値になり、このことが全ての区間について当てはまる。同様に、第3の確率決定部14cは、閾値群によって区切られた区間のそれぞれについて、中優先度用に比べて大きな値となるように低優先度用の廃棄確率候補値を決定し、対応する隣り合う閾値又は対応する区間に関連付けておく。この例では、廃棄確率候補値の最大値(maxP)は、高優先度用の方が中優先度用より小さくなり、中優先度用の方が低優先度用より小さくなる。

0088

また、このようにして決定された廃棄確率候補値等は、図7で示したテーブル24tのようなルックアップテーブルに記述しておいてもよく、その場合、各確率決定部14a〜14cのそれぞれで異なるテーブルを有するように構成することもできる。

0089

そして、第1の確率決定部14aは、平均値算出部13で算出された移動平均値を、上記共通の閾値群によって区切られた複数の区間のいずれかに分類する閾値処理を施し、その閾値処理の結果が示す区間に対応する高優先度用の廃棄確率候補値を、廃棄確率Paとしてパケット廃棄部11に出力する。

0090

パケット廃棄部11は、判別部17での判別結果が基準種類の1つである高優先度であることを示している場合には、高優先度用の廃棄確率Paに従って高優先度のパケットの廃棄を実行する。つまりパケット廃棄部11は、高優先度のパケットが到着した場合、この廃棄確率Paに従ってその到着した高優先度のパケットを廃棄するのか、或いは通過させるのかを判定し、判定結果に従って廃棄又は通過を実行する。

0091

同様に、第2の確率決定部14bは、平均値算出部13で算出された移動平均値に対し、上記共通の閾値群を用いて閾値処理を施し、その閾値処理の結果が示す区間に対応する中優先度用の廃棄確率候補値を、廃棄確率Pbとしてパケット廃棄部11に出力する。パケット廃棄部11は、判別部17での判別結果が中優先度であることを示している場合には、中優先度用の廃棄確率Pbに従って中優先度のパケットの廃棄を実行する。

0092

同様に、第3の確率決定部14cは、平均値算出部13で算出された移動平均値に対し、上記共通の閾値群を用いて閾値処理を施し、その閾値処理の結果が示す区間に対応する低優先度用の廃棄確率候補値を、廃棄確率Pcとしてパケット廃棄部11に出力する。パケット廃棄部11は、判別部17での判別結果が低優先度であることを示している場合には、低優先度用の廃棄確率Pcに従って、低優先度のパケットの廃棄を実行する。

0093

なお、優先度毎に処理を異ならせる手法は、上述のような優先度情報がパケットに付されて到着することを想定したWRED(Weighted RED)で実現されているが、本実施の形態では、上述したように各優先度についての廃棄確率を統計情報に応じて異ならせるようにしたものである。本実施の形態においても、WREDに適用可能な様々な応用が適用できる。

0094

次に、本実施の形態の他の構成例について、図13を参照しながら説明する。本構成例におけるパケット制御装置は、予め決められたパケットの種類である基準種類毎に複数の閾値の決定を行う閾値決定部を有する。この閾値決定部は、例えば図1の閾値決定部16を基準種類の数だけ設けることで構成することができる。

0095

本構成例においてもパケットの種類として3種類の優先度を適用した例を挙げて説明する。図13で例示するように、本構成例のパケット制御装置1cは、パケット制御装置1bにおいて閾値決定部16を3つ設けたものであり、それらを第1の閾値決定部16a、第2の閾値決定部16b、及び第3の閾値決定部16cと称する。但し、閾値決定部16a〜16cをハードウェアで構成するに際しても、1つのハードウェアとして構成することもできる。

0096

本構成例において、第1の閾値決定部16aは基準種類の1つとしての高優先度用の閾値群を決定する。同様に、第2の閾値決定部16bは基準種類の1つとしての中優先度用の閾値群を決定し、第3の閾値決定部16cは基準種類の1つとしての低優先度用の閾値群を決定する。第1〜第3の閾値決定部16a〜16cではいずれも共通の統計情報を用いて、異なる閾値群に決定することになる。第1〜第3の閾値決定部16a〜16cは、例えば、優先度が高いほど、閾値群によって区切られる区間が小さいように設定しておけばよい。これは、後述するように、この例においても低い優先度ほど廃棄確率候補値の最大値(maxP)が大きくなり、高い優先度ほど隣り合う区間での廃棄確率候補値の差が小さく設定できるためである。

0097

本構成例における確率決定部は、基準種類毎に、閾値処理を実行して廃棄確率を決定する。具体的には、まず第1の確率決定部14aは、第1の閾値決定部16aで決定された高優先度用の閾値群Thaを用い、閾値群Thaによって区切られた複数の区間のそれぞれについて、高優先度用の廃棄確率候補値を決定し、対応する隣り合う閾値(閾値群Thaの中の隣り合う閾値)又は対応する区間に関連付けておく。第2の確率決定部14bは、第2の閾値決定部16bで決定された中優先度用の閾値群Thbを用い、閾値群Thbによって区切られた複数の区間のそれぞれについて、中優先度用の廃棄確率候補値を決定し、対応する隣り合う閾値(閾値群Thbの中の隣り合う閾値)又は対応する区間に関連付けておく。第3の確率決定部14cは、第3の閾値決定部16cで決定された低優先度用の閾値群Thcを用い、閾値群Thcによって区切られた複数の区間のそれぞれについて、低優先度用の廃棄確率候補値を決定し、対応する隣り合う閾値(閾値群Thcの中の隣り合う閾値)又は対応する区間に関連付けておく。

0098

第1〜第3の確率決定部14a〜14cは、それぞれ閾値群が異なることとなるが、いずれの移動平均値に対しても、高優先度用に比べて中優先度用の廃棄確率候補値が大きくなり、かつ中優先度用に比べて低優先度用の廃棄確率候補値が大きくなるように決定しておけばよい。この例でも、廃棄確率候補値の最大値(maxP)は、高優先度用の方が中優先度用より小さくなり、中優先度用の方が低優先度用より小さくなる。

0099

そして、第1の確率決定部14aは、平均値算出部13で算出された移動平均値を、閾値群Thaによって区切られた複数の区間のいずれかに分類する閾値処理を施し、その閾値処理の結果が示す区間に対応する高優先度用の廃棄確率候補値を、廃棄確率Paとしてパケット廃棄部11に出力する。同様に、第2の確率決定部14bは、平均値算出部13で算出された移動平均値に対し、閾値群Thbを用いて閾値処理を施し、その閾値処理の結果が示す区間に対応する中優先度用の廃棄確率候補値を、廃棄確率Pbとしてパケット廃棄部11に出力する。同様に、第3の確率決定部14cは、平均値算出部13で算出された移動平均値に対し、閾値群Thcを用いて閾値処理を施し、その閾値処理の結果が示す区間に対応する低優先度用の廃棄確率候補値を、廃棄確率Pcとしてパケット廃棄部11に出力する。

0100

本構成例においても、パケット廃棄部11は図12の構成例と同様の処理を行う。つまり、パケット廃棄部11は、到着種類に属するパケットを、その到着種類に対応する基準種類についての廃棄確率に応じた量、廃棄することになる。

0101

以上、本実施の形態によれば、多大なハードウェアリソースを追加せずに、複数種類のパケットが到着するWREDのような輻輳制御技術にも対応させることができる。また、パケットの種類として優先度の違いによってパケットを分類する例を挙げたが、例えば映像音声、他の情報(受信側機器での出力制御に必要な制御情報など)といった種類でパケットを分類するなど、他の種類で分類することもできる。なお、映像、音声、他の情報のそれぞれのパケットはパケットのヘッダ種別を示す情報を記述しておき、パケット制御装置1b,1cでは、例えば映像パケットより音声パケットの方が廃棄確率を低く、かつ音声パケットより他の情報パケットの方が廃棄確率を低くするように処理を実行すればよい。

0102

変形例.
図14は、上記実施の形態1〜3に係るパケット制御装置の他の構成例を示す図である。図1図7図12図13で例示したパケット制御装置1,1a,1b,1cはいずれも、ソフトウェアとしてのプログラムと各種データを格納する記憶装置としてのメモリ31と、メモリ31に格納されたプログラムを実行する情報処理部(パケット制御装置の処理タイミングなどの全体の制御を行う上述した制御部を含む)としてのプロセッサ32とを用いて(例えば、コンピュータにより)実現することができる。

0103

この場合には、図1等におけるバッファ12をはじめ記憶部15a、上述した移動平均値記憶部、蓄積量記憶部、閾値記憶部、及び廃棄確率候補値記憶部はメモリ31に相当する。また、プロセッサ32は、図1等におけるパケット廃棄部11、平均値算出部13、確率決定部14(第1〜第3の確率決定部14a〜14c)、統計処理部15、閾値決定部16(第1〜第3の閾値決定部16a〜16c)、及び判別部17の機能や、上記制御部の機能を実現するためのプログラムを実行する。このプログラムはメモリ31の代わりにプロセッサ32の内部のメモリに格納しておいてもよい。これらの各部11〜17の一部を、図14に示されるメモリ31と、プログラムを実行するプロセッサ32とによって実現してもよい。また、上述したソフトウェアとしてのプログラムは非一時的な記録媒体に記憶させて頒布することで流通させること、或いはサーバ装置に格納しておきインターネットを介して流通させることができる。

0104

1,1a,1b,1cパケット制御装置、 11パケット廃棄部、 12バッファ(パケット収容部)、 13平均値算出部、 14 確率決定部、 14a 第1の確率決定部、 14b 第2の確率決定部、 14c 第3の確率決定部、 15統計処理部、 15a 記憶部、 16閾値決定部、 16a 第1の閾値決定部、 16b 第2の閾値決定部、 16c 第3の閾値決定部、 17判別部、 24 確率決定部、 24t テーブル、 31メモリ、 32プロセッサ。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ