TOP > 国内特許検索 > 断片的自己相似過程を用いる通信トラヒックの評価方法及び評価装置 > 明細書

明細書 :断片的自己相似過程を用いる通信トラヒックの評価方法及び評価装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4081552号 (P4081552)
公開番号 特開2007-060440 (P2007-060440A)
登録日 平成20年2月22日(2008.2.22)
発行日 平成20年4月30日(2008.4.30)
公開日 平成19年3月8日(2007.3.8)
発明の名称または考案の名称 断片的自己相似過程を用いる通信トラヒックの評価方法及び評価装置
国際特許分類 H04L  12/56        (2006.01)
H04L  29/14        (2006.01)
FI H04L 12/56 400B
H04L 13/00 313
請求項の数または発明の数 6
全頁数 18
出願番号 特願2005-245021 (P2005-245021)
出願日 平成17年8月25日(2005.8.25)
審査請求日 平成17年9月2日(2005.9.2)
特許権者または実用新案権者 【識別番号】504202472
【氏名又は名称】大学共同利用機関法人情報・システム研究機構
発明者または考案者 【氏名】計 宇 生
個別代理人の代理人 【識別番号】100097320、【弁理士】、【氏名又は名称】宮川 貞二
【識別番号】100100398、【弁理士】、【氏名又は名称】柴田 茂夫
【識別番号】100096611、【弁理士】、【氏名又は名称】宮川 清
【識別番号】100098040、【弁理士】、【氏名又は名称】松村 博之
【識別番号】100123892、【弁理士】、【氏名又は名称】内藤 忠雄
【識別番号】100131820、【弁理士】、【氏名又は名称】金井 俊幸
【識別番号】100134278、【弁理士】、【氏名又は名称】吉村 裕子
審査官 【審査官】清水 稔
参考文献・文献 時間スケールを考慮した長期依存性トラヒックの性能解析 Performance Analysis of Long-range Dependent Internet Traffic According to Relevant Time Scales,情報処理学会論文誌 第45巻 第5号 IPSJ Journal,2004年 5月15日
調査した分野 H04L 12/56
H04L 29/14
特許請求の範囲 【請求項1】
通信網における通信トラヒックの各時間スケールにおける到着トラヒック量を採取するデータ採取工程と;
採取された到着トラヒック量データに基づき、時間スケール区間毎に異なる自己相似過程を採用する断片的自己相似過程を適用することにより、各時間スケール区間における前記通信トラヒックの自己相似指数を含む特徴量を導出する特徴量導出工程と;
前記時間スケールと前記通信網に生成される待ち行列の待ち行列長との関係を用いて、導出された自己相似指数を含む特徴量に基づき、前記通信網の負荷が与えられたときの、待ち行列長が所定値より大きくなる確率を求める確率導出工程と;
前記確率を用いて、前記通信トラヒックの待ち時間に係る品質を評価する品質評価工程とを備える;
断片的自己相似過程を用いる通信トラヒックの評価方法。
【請求項2】
前記特徴量導出工程は、単位時間をΔtとし、k番目の、連続するm個の単位時間mΔt内に到着した通信トラヒックの単位時間Δt当たりのビット数の平均値をX(m)(k)とし(この場合mは時間スケールとみなすことができる)、その分散Var[X(m)(k)]の前記時間スケールmに対する分散-時間特性を求める分散-時間特性導出工程と、
前記分散-時間特性導出工程で求められた分散-時間特性に基づいて、前記各時間スケール区間における前記通信トラヒックの自己相似指数を含む特徴量を導出する自己相似指数等導出工程とを有する;
請求項1に記載の断片的自己相似過程を用いる通信トラヒックの評価方法。
【請求項3】
前記特徴量導出工程において、隣り合う時間スケールの比が一定になるよう前記品質を評価するための各評価点時間スケールを定め;
前記評価点時間スケールが前記時間スケール区間の中間点となるように、前記評価点時間スケール毎に前記時間スケール区間を対応させ、前記時間スケール区間の長さを前記隣り合う時間スケールの比の倍数に定める;
請求項1又は請求項2に記載の断片的自己相似過程を用いる通信トラヒックの評価方法。
【請求項4】
前記通信トラヒックに正規性が近似的に成り立つ場合、前記断片的自己相似過程として、マルチスケールフラクショナルブラウン運動(MFBM:Multiscale Fractional Brownian Motion)確率過程を用いて、前記特徴量を導出する;
請求項2又は請求項3に記載の断片的自己相似過程を用いる通信トラヒックの評価方法。
【請求項5】
通信網における通信トラヒックの各時間スケールにおける到着トラヒック量を採取するデータ採取手段と;
採取された到着トラヒック量データに基づき、時間スケール区間毎に異なる自己相似過程を採用する断片的自己相似過程を適用することにより、各時間スケール区間における前記通信トラヒックの自己相似指数を含む特徴量を導出する特徴量導出手段と、
前記時間スケールと前記通信網に生成される待ち行列の待ち行列長との関係を用いて、前記導出された自己相似指数を含む特徴量に基づき、前記通信網の負荷が与えられたときの、前記の待ち行列長が所定値より大きくなる確率を求める補分布演算手段と、
前記確率を用いて、前記通信トラヒックの待ち時間に係る品質を評価する品質評価手段とを備える;
断片的自己相似過程を用いる通信トラヒック評価装置。
【請求項6】
請求項1乃至請求項4のいずれか1項に記載の断片的自己相似過程を用いる通信トラヒックの評価方法をコンピュータに実行させるためのプログラム。

発明の詳細な説明 【技術分野】
【0001】
本発明は通信トラヒックの評価方法及び評価装置に関する。詳しくは、断片的自己相似過程を用いる通信トラヒックの待ち時間に係る品質を評価する評価方法及びその評価方法を実施するための評価装置に関する。
【背景技術】
【0002】
一般に、定常増分を有する確率過程X(t)(t:時間)の自己相関関数がr(k)であり、(式1)のような条件を満足する場合、X(t)が2次の自己相似性を有するという。
【数1】
JP0004081552B2_000002t.gif
ここに、Hは自己相関関数のkに対する減衰の速さを特徴付ける量(0.5≦H<1)で自己相似指数という(ハーストパラメータともいう)。
【0003】
また、tが離散値の場合、連続したm個のX(t)の平均
【数2】
JP0004081552B2_000003t.gif

を考えると、2次の自己相似性は(式3)のようにも表される。
【数3】
JP0004081552B2_000004t.gif
ここにσはX(t)の分散である。2次の自己相似性や長期依存性は、mに対するX(m)(k)の分散値の変化(分散-時間特性)などで確認することができる。X(t)が厳密な2次の自己相似性を有する場合、(式3)により、対数座標上ではX(m)(k)の分散の値がmに対して勾配が-2(1-H)の直線になる。
【0004】
確率過程X(t)がFractional Brownian Motion(FBM)確率過程であるとき、3つの特徴量{平均到着率λ,分散係数a、自己相似指数H}で記述できる。X(t)をサービス率(通信網では回線帯域または回線容量に相当する)Cの待ち行列への入力であるとしたとき、待ち行列長の補分布(すなわち、待ち行列長Qが一定の長さxを超える確率)は(式4)によって与えられる。
【数4】
JP0004081552B2_000005t.gif

ただしここでは、
【数5】
JP0004081552B2_000006t.gif

であり、~はxが非常に長くなるときの漸近的な値であることを表す。
【数6】
JP0004081552B2_000007t.gif
(式4)を用いて、待ち行列長Qがxを超える確率を導出でき、トラヒックの性能を評価できる。
【0005】
図1に観測トラヒックサンプルデータの分散-時間特性の例を示す。縦軸はX(m)(k)の分散、横軸は時間スケールmである。ここで、X(m)(k)は、(式2)に示すように、k番目の、連続したm個の単位時間m×Δt内に到着した通信トラヒックのビット数の単位時間Δt当たりの平均値である。したがって、mの値はミリ秒を単位とする時間スケールとして見ることができる。図中、AはSINETデータ、BはAbileneデータである。Δtは、SINETデータでは1ミリ秒、Abileneデータでは0.1ミリ秒とした。これらについてはそれぞれ第1、第2の実施の形態で説明する。
【0006】
図1によれば、データの分散特性の時間スケールに対する減衰の速さは一定でなく、mの小さい領域においては減衰が比較的速く、ポアソン特性(長期依存性がなく、指数分布データの自己相似指数が0.5である)に近い。これに対して、比較的長い時間スケール(mの大きい領域)においては、分散の減衰が緩やかになり(自己相似指数が1に近づく)、変動が長く持続されることを示している。このことから、インターネットのトラヒックは長期依存性を有していることが分かる。また、インターネットのトラヒックは多くの場合、分散や自己相関関数のような2次特性が時間スケールにより異なる挙動を示しており、このような特性を従来の有力な解析手段である、Fractional Brownian Motion(FBM)確率過程の3つの特徴量{平均到着率λ,分散係数a、自己相似指数H}で記述することは不可能である。
【0007】
発明者達は、待ち行列システムにおけるトラヒックの挙動と深くかかわりのある時間スケールに注目し、より一般的な自己相関特性を持つ長期依存性トラヒックの性能を近似的に解析するための方法を提案した(非特許文献1参照)。
すなわち、実際のシステムにおいて待ち行列長が有限(バッファ長が有限)の場合、それに最も関係する時間スケールにおけるトラヒックの相関特性がバッファあふれ率を左右する。このような性能に最も関係する時間スケールを適正時間スケールといい、待ち行列長がxのときのFBM過程の適正時間スケールmは(式6)で表される。
【数7】
JP0004081552B2_000008t.gif
ここにρは平均負荷である。この適正時間スケールmは(式5)の等号右辺の最大値が得られるtの値である。
【0008】
この適正時間スケールmを分散-時間特性の横軸とする。発明者らが提案した方法では、適正時間スケールを用いて表した分散-時間特性を複数の直線により近似する。
【0009】
図8に、分散-時間特性を2本の直線で近似したときのグラフを示す。また、図9に、分散-時間特性を3本の直線で近似したときのグラフを示す。図8の分散-時間特性の例では、mが小さく減衰が比較的速い領域の第1の直線(Line1、ハーストパラメータH1=0.69)とmが大きく減衰が比較的遅い領域の第2の直線(Line2、ハーストパラメータH2=0.932)の2本の直線で、2つの直線の交点の近くを除けばその大部分を近似できる。図9では、その交点の近くを第3の直線(Line3)で近似することにより、より滑らかな性能曲線を得ている。この第3の直線(Line3)は、評価値が安全側になるように、Line1とLine2の交点(時間スケールTm)の両側のLine1、Line2上の点(それぞれ時間スケールT1,T2)を結ぶように引かれる。
【0010】

【非特許文献1】時間スケールを考慮した長期依存性トラヒックの性能解析、計宇生他、情報処理学会論文誌、第45巻第5号、平成16年5月発行
【発明の開示】
【発明が解決しようとする課題】
【0011】
しかしながら、上記発明者らが提案した方法では、分散-時間特性を近似するのには限度があり、比較的単純な、下方に凸な分散-時間特性の形に対応できるように考えられていた。さらに手動により直線の選択を行うので処理時間や精度上の問題があった。
【0012】
本発明は、通信トラヒックの自己相似指数やその他の特徴量と時間スケールとの関係を動的に定めることによって、時間スケールによって変化する長期依存性通信トラヒックの待ち行列に係る特性を適正に評価できる評価方法及び評価装置を提供することを目的とする。
【課題を解決するための手段】
【0013】
上記課題を解決するために、請求項1に記載の断片的自己相似過程を用いる通信トラヒックの評価方法は、例えば図6に示すように、通信網における通信トラヒックの各時間スケールm(時間間隔mΔt)における到着トラヒック量mX(m)(k)を採取するデータ採取工程(S001)と、採取された到着トラヒック量データmX(m)(k)に基づき、時間スケール区間毎に異なる自己相似過程を採用する断片的自己相似過程を適用することにより、各時間スケール区間における通信トラヒックの自己相似指数Hを含む特徴量を導出する特徴量導出工程(S003~S004)と、時間スケールmと通信網に生成される待ち行列の待ち行列長xとの関係(式6参照)を用いて、導出された自己相似指数Hを含む特徴量に基づき、通信網の負荷が与えられたときの、トラヒックの待ち行列長Qが所定値xより大きくなる確率Pr(Q>x)を求める確率導出工程(S005)と、確率Pr(Q>x)を用いて、通信トラヒックの待ち時間に係る品質を評価する品質評価工程(S006)とを備える。
【0014】
ここにおいて、時間スケールmにおける到着トラヒック量mX(m)(k)は時間間隔mΔt内の到着トラヒック量である。到着トラヒック量は単位時間Δtのデータx(t)をm個採取しても良く、時間間隔mΔtのデータを採取しても良い。また、特徴量には自己相似指数Hの他に、多様な特徴量が含まれる。すなわち、トラヒックデータX(t)が正規分布であれば、平均到着率λ、自己相似指数H及び2次の特徴量である分散係数aで表せ、高い精度で特徴量を導出できるが、正規分布以外ではさらに3次特徴量など多様な特徴量が使用される。また、特徴量の導出には、正規分布以外では正確に特徴量を求められない場合もあり、推定による導出も含まれる。また、時間スケール区間は、例えば、品質を評価するための時間スケール(評価点時間スケールm)毎に定められても良く、対数座標で均等になるように時間スケールを分割しても良く、特徴量の変化の様相に応じて臨機応変に定めても良い。また、隣り合う時間スケール区間が重複しあっても良い。典型的には、時間スケール区間は、各評価点時間スケールm毎に定められ、また、評価点時間スケールmが時間スケール区間の中間点(対数座標で)にくるように定められ、また、時間スケール区間の長さl/sは、隣り合う時間スケールの比(すなわち隣り合う評価点時間スケールの比)mi+1/mの倍数に定められる。また、隣り合う時間スケールの比mi+1/mは一定に選ばれる。また、通信トラヒック網の負荷は典型的には、通信トラヒックの平均到着率λおよび回線帯域Cで与えられる。
【0015】
このように構成すると、自己相似指数Hやその他の特徴量が時間スケールmによって変化する長期依存性通信トラヒックにおいても、適正な評価ができる評価方法を提供できる。また、通信トラヒックの性能を広い範囲で予測することが可能であり、予測の精度を向上させ、ネットワーク帯域の設計、品質の予測に役立てられる。
【0016】
また、請求項2に記載の発明は、請求項1に記載の断片的自己相似過程を用いる通信トラヒックの評価方法において、例えば図2に示すように、特徴量導出工程は、単位時間をΔtとし、k番目の、連続するm個(mは時間スケールである)の単位時間mΔt内に到着した通信トラヒックの単位時間Δt当たりのビット数の平均値をX(m)(k)とし、その分散Var[X(m)(k)]の時間スケールmに対する分散-時間特性を求める分散-時間特性導出工程(S003)と、分散-時間特性導出工程で求められた分散-時間特性に基づいて、各時間スケール区間における通信トラヒックの自己相似指数Hを含む特徴量を導出する自己相似指数等導出工程(S004)とを有する。
このように構成すると、分散-時間特性を使用して、各時間スケール区間における自己相似指数Hを含む特徴量を精度良く導出(推定を含む)できる。
【0017】
また、請求項3に記載の発明は、請求項1又は請求項2に記載の断片的自己相似過程を用いる通信トラヒックの評価方法において、特徴量導出工程において、隣り合う時間スケールの比mi+1/mが一定になるように品質を評価するための評価点時間スケールmを定め、評価点時間スケールmが時間スケール区間の中間点(対数座標で)となるように、評価点時間スケールm毎に時間スケール区間を対応させ、時間スケール区間の長さl/sを隣り合う時間スケールの比mi+1/mの倍数に定める。
ここにおいて、隣り合う時間スケールとは、品質を評価するための評価点時間スケールにおいて隣り合うものをいう。したがって、隣り合う時間スケールの比とは隣り合う評価点時間スケールの比をいう。このように構成すると、各時間スケール区間が自動的に定まり、自己相似指数やその他の特徴量を求めるのに便宜であり、さらに、実測されたトラヒックの分散-時間特性に応じて、適正な範囲で時間スケール比を変更でき、適正に性能を評価することができる。また、データを採取する時間スケールと評価点時間スケールとを同じにすることも可能であり、この場合は各採取データをそのまま利用して各時間スケール区間における特徴量が導出される。
【0018】
また、請求項4に記載の発明は、請求項2又は請求項3に記載の断片的自己相似過程を用いる通信トラヒックの評価方法において、通信トラヒックに正規性が近似的に成り立つ場合、マルチスケールフラクショナルブラウン運動(MFBM:Multiscale Fractional Brownian Motion)確率過程を用いて特徴量を導出する。
ここにおいて、MFBM過程とは、時間スケールmの範囲毎に異なるFBM(Fractional Brownian Motion)過程の特徴量を採用する確率過程をいう。
このように構成すると、正規性が近似的に成り立つ通信トラヒックを正確に記述でき、性能の評価が精度良くかつ短時間に求まる。
【0019】
また、請求項5に記載の断片的自己相似過程を用いる通信トラヒック評価装置は、例えば図5に示すように、通信網における通信トラヒックの各時間スケールm(時間間隔mΔt)における到着量mX(m)(k)を採取するデータ採取手段9と、採取された到着トラヒック量データに基づき、時間スケール区間毎に異なる自己相似過程を採用する断片的自己相似過程を適用することにより、各時間スケール区間における通信トラヒックの自己相似指数Hを含む特徴量を導出する特徴量導出手段3と、時間スケールmと通信網に生成される待ち行列の待ち行列長xとの関係(式6参照)を用いて、導出された自己相似指数Hを含む特徴量に基づき、通信網の負荷が与えられたときの、待ち行列長Qが所定値xより大きくなる確率Pr(Q>x)を求める補分布演算手段6と、確率Pr(Q>x)を用いて、通信トラヒックの待ち時間に係る品質を評価する品質評価手段7とを備える。
本請求項1に記載の断片的自己相似過程を用いる通信トラヒックの評価方法を実施するための断片的自己相似過程を用いる通信トラヒック評価装置の発明である。
【0020】
また、請求項6に記載のプログラムは、請求項1乃至請求項4のいずれか1項に記載の断片的自己相似過程を用いる通信トラヒックの評価方法をコンピュータに実行させるためのプログラムの発明である。なお、コンピュータには通信トラヒック評価装置を構成するコンピュータの他に、パーソナルコンピュータ等の汎用コンピュータも含まれる。
【発明の効果】
【0021】
本発明によれば、自己相似指数やその他の特徴量が時間スケールによって変化する長期依存性通信トラヒックにおいても、通信トラヒックの待ち行列に係る特性を適正に評価できる。また、データの取得から評価にいたる演算を自動化でき、評価を迅速にできる。
【発明を実施するための最良の形態】
【0022】
[第1の実施の形態]
以下に図面に基づき本発明の実施の形態について説明する。本実施の形態では、時間スケール区間の最大、最小の2点から各々のFBM確率過程のパラメータを導出する(ここでは2点法ということとする)例を説明する。トラヒックデータはSINETから採取したデータの中で最も正規分布に近いデータを用いた。
【0023】
図1に観測トラヒックサンプルデータの分散-時間特性を示す。
縦軸は分散Var[X(m)(k)]、横軸は時間スケールmである。X(m)(k)は連続したm個の単位時間m×Δt内に到着した通信トラヒックのビット数の単位時間Δt当たりの平均値である。ここでは単位時間Δtを1ミリ秒とした。
【0024】
図中、AはSINETデータ、BはAbileneデータである。ここでは、Aについて取り扱い、Bについては第2の実施の形態で取り扱う。
SINETデータは広域ネットワークのデータとして、国立情報学研究所で運用されている学術情報ネットワーク(SINET)のバックボーンノードから得られたデータである。観測データの中で最も正規分布に近いものである。SINETデータは、定常性が得られる午後の通信ピーク時間帯の持続時間10,000秒(約2.8時間)のデータである。
【0025】
表1に使用したトラヒックサンプルデータ(SINETデータ、Abileneデータ)に関する統計量を示す。正規分布の場合、3次の特徴量である歪度と4次の特徴量である尖度はともに0になるので、SINETデータはAbileneデータよりも正規分布に近いことがわかる。
【表1】
JP0004081552B2_000009t.gif

【0026】
データの分散特性の時間スケールmに対する減衰の速さは一定でなく、時間スケールmの短い領域においては減衰が比較的速く、ポアソン特性に近い。それに対して、比較的長い時間スケールmにおいては、分散の減衰が緩やかになり、変動が長く持続されることを示している。
【0027】
図1で示したように、SINETのトラヒックは長期依存性を有していることが分かる。さらに、これらのトラヒックは一般的に、より複雑な自己相関特性を有している。このような特性をFBM過程の3つの特徴量{平均到着率λ,分散係数a、自己相似指数H}だけで記述することが不可能である。
【0028】
本実施の形態では、SINETトラヒックの正規性を利用して、断片的自己相似過程の一例であるMultiscale Fractional Brownian Motion(MFBM)過程を適用して解析するものである。MFBM過程は時間スケールの範囲毎に異なる特徴量を持つFBM過程を採用するものである。また、断片的自己相似過程(ピースワイズ自己相似過程ともいう)とは、時間スケール範囲毎に異なる自己相似過程を採用する確率過程をいう。
【0029】
時間スケールmに関して、I個(0≦i≦I)(Iは正整数)の時間スケール区間があるものとする。i番目の時間スケール区間における自己相似指数をH、分散係数をa、平均到着率λを使用すると、MFBM過程の正規性により、3つの特徴量{λ,a,H}を用いてMFBM過程を記述できる。
時間スケール依存の自己相似指数Hは、(式7)のように、時間スケールmとその時間スケールmにおける分散値v(m)(前記のVar[X(m)(k)]と同じ)で表される。
【数8】
JP0004081552B2_000010t.gif
ここに、sとlはそれぞれ、i番目の時間スケール区間内の最小、最大時間スケールである。SINETの分散-時間特性が比較的滑らかであるため、(式8)に示す方法(2点法)で自己相似指数を求める。
【数9】
JP0004081552B2_000011t.gif
ここに、v(s)とv(l)はそれぞれ、時間スケールsとlにおける分散値である。
【0030】
また、分散係数はa=v(m)/λm2Hで表すことができる。ここに、mは単位時間を表す。そこで、(式8)で使った図1の分散-時間特性図上の2つの点(s,v(s))と(l,v(l))を通る直線上の任意の点の座標を(m、v(m))とすると、i番目の時間スケール区間における分散係数aは、(式9)のように表される。
【数10】
JP0004081552B2_000012t.gif

【0031】
このようにして、時間スケールに依存する自己相似指数H、分散係数aをすべてのi(0≦i≦I)について求めることができる。
一方、FBM過程のもうひとつの特徴量である平均到着率λは、確率過程が定常であれば一定である。それはMFBM過程についても同じであり、時間スケールによって変わらない。
以上により、MFBM過程のすべての時間スケール区間における3つの特徴量{λ,a,H}は既知となる。これらを使って表す一つの確率過程をMFBM過程といい、それは断片的自己相似過程と呼ばれる確率過程の一例である。
【0032】
i番目の時間スケール区間はs≦m≦lである。すなわち、sとlはそれぞれ、i番目の時間スケール区間内の最小、最大時間スケールである。自己相似指数H、および剰余帯域C-λ(または回線帯域Cと平均負荷ρ)より、待ち行列長がxのときにおけるFBM過程の適正時間スケールmは(式6)で表される。
その結果、mとxの関係によって、さらに断片的自己相似過程のすべての時間スケール区間における既知の3つの特徴量{λ,a,H}により、待ち行列長Qがxを超える確率Pr(Q<x)を(式4)で求めることができる。
【0033】
図2に2点法を用いた断片的自己相似過程に基づく解析アルゴリズム(ここではマルチスケール解析アルゴリズムともいう)のフローチャートの例を示す。
各評価点時間スケールに対応して時間スケール区間が定められ、特徴量が導出される。次いで、その特徴量を使用して、待ち行列長が各評価点時間スケールに対応する所定値xを超える確率が求められ、評価可能となる。ここでは、隣り合う時間スケールの比nn及び時間スケール区間の長さplenを初めに付与する方法を示す。隣り合う時間スケールとは、品質を評価するための時間スケール、すなわち評価点時間スケールmにおいて隣り合うものをいい、隣り合う時間スケールの比nnは隣り合う評価点時間スケールの比mi+1/mで表すものとする。また、時間スケール区間は特徴量の計算のために使う時間スケールの範囲であり、各評価点時間スケールmに対応して定められる。時間スケール区間の長さplenは区間内の最大と最小の時間スケールの比l/sで表すものとし、隣り合う時間スケールの比mi+1/mの倍数に定められる。また、隣り合う時間スケールの比mi+1/mは一定に選ばれる。
【0034】
まず、時間スケールm[i](i=0, …,I)、時間スケールm[i]における分散値v[i]、nn=m[i+1]/m[i]のデータを確保する(S101)。次に、平均到着率λ、回線帯域C、単位時間mk(前記Δt)、時間スケール区間の長さplenを入力する(S102)。次に、時間スケール区間の長さplenにより定まり、時間スケール区間内にある時間スケールmの数を決める変数nを定義し、初期値としてi=nとする(S103)。次に、iがI-nを超える否かを判断し(S104)、超えない場合は、時間スケール毎に、変数β、自己相似指数h、分散係数a、待ち行列長x、係数γ、確率p(Pr(Q>x)に相当)を演算して求める(S105)。次に、待ち行列長xと確率pを出力する(S106)。次にiを1ずつ増加し(S107)、iがI-nを超えない場合はS104~S107のループを繰り返す。iがI-nを超えた場合は、得られたすべてのxとpの値を使って補分布のグラフを作成し(S108)、処理を終了する。なお、隣り合う時間スケールの比nn及び時間スケール区間の長さplenを変更可能であり、例えば滑らかな補分布のグラフが得られないなどの場合には、隣り合う時間スケールの比nn又は/及び時間スケール区間の長さplenを変更して再度フローに添って処理する。このように、いくつかのパラメータを決めれば、各時間スケール区間における特徴量が自動的に導出され、待ち行列長の補分布が自動的に求められ、通信トラヒックの待ち時間に係る品質を評価可能となる。
【0035】
自己相似指数は分散-時間特性の湾曲部の近傍で大きく変化する。HとHi+1を2つの隣り合う時間スケールmとmi+1に対応する自己相似指数とすると、mi+1とmの比率は次の(式10)を満足しなければならない。
【数11】
JP0004081552B2_000013t.gif
もしHとHi+1との差が大きく、mi+1とmの比率が(式10)を満足しないとき、この2つの隣り合う時間スケールm,mi+1と自己相似指数H,Hi+1の組を使って(式6)で計算した待ち行列長xi+1とx(それぞれmi+1とmに対応)はもとの時間スケールと逆の順序となり、滑らかな性能曲線を得ることができない。例えば、もしmi+1/m=1.1で、H=0.60であるとき、Hi+1 は0.62以下でなければならない。このため後述の時間スケール区間の長さを適当に選ぶことによって、HとHi+1との差があまり大きくならないようにする必要がある。ここでは、mi+1/m=1.1とした。
【0036】
分散-時間特性の湾曲の度合いによって、時間スケール区間の長さ(すなわち、lとsの比率)を適宜決めることによって、(式10)を満足させることができる。一般的に、湾曲の度合いが大きいと、時間スケール区間の長さも大きくとる必要がある。またあまり大きくすると近似の精度が粗くなるので、適当な範囲に選ぶ必要がある。本実施の形態では、時間スケール区間の長さl/sを約約10(1.124~9.85)とした。
【0037】
図3に、分散-時間特性における時間スケール区間の例を模式的に示す。図において、横軸は時間スケールm、縦軸は分散Var[X(m)(k)]である。分散—時間特性グラフにおいてプロット点×は特徴量を導出するためのサンプリング点である。本実施の形態では、品質を評価するための評価点時間スケールとしても使用される。詳しくは、時間スケール区間内の2点(本実施の形態)又は全てのサンプリング点(第2の実施の形態)を使用して評価点時間スケールに対応する特徴量を導出する。さらに、この特徴量を用いて待ち行列長が各評価点時間スケールに対応する所定値xを超える確率が求められ、品質を評価するために使用される。そして、評価点時間スケールm毎に時間スケール区間が対応する。mとmi+1はi番目とi+1番目の時間スケールで、i番目とi+1番目の時間スケール区間の中間点(対数座標で)に相当し、lとsはi番目の時間スケール区間の最大と最小時間スケール、li+1とsi+1はi+1番目の時間スケール区間の最大と最小時間スケールである。図において、各時間スケール区間は直線の断片で表され、その中間点である評価点時間スケールの座標((m=(l0.5,v(m))が品質評価の解析に使用される。また、(式3)で説明されているように、直線の傾きは-2(1-H)である。このように、本近似解析法は、時間スケールを領域に分け、それぞれの領域を直線の断片で表し、それぞれの領域に異なる自己相似性を適用するため、断片的自己相似過程(またはピースワイズ自己相似過程)と呼んでいる。
本実施の形態では、時間スケール区間の長さl/sを約10とし、lとsの中間点(l0.5であるi番目の時間スケール区間の評価点時間スケールmをプロット点とし、プロット点をmi+1/m=1.1倍間隔とした。
【0038】
図4にSINETデータに関する待ち行列長の補分布を示す。図4(a)は負荷70%、図4(b)は負荷80%のデータである。
横軸は待ち行列長の所定値x、縦軸は待ち行列長Qがxを超える確率Pr(Q>x)である。負荷は、回線容量(または回線帯域)Cに対する平均到着率λの割合を示す。
プロット点の帯(Line A)は本実施の形態における解析結果であり、それぞれの点が一つの時間スケール区間の中間点(評価点時間スケール)に係るプロット点である。実線(Line B)はシミュレーションデータである。
【0039】
SINETのトラヒックはバックボーンノードから得られており、正規性に比較的良く適合するので、近似解析結果と良く一致している。したがって、トラヒックデータが正規性に適合する場合には、MFBM正規過程特徴量の導出による近似解析データは有効であると言える。
シミュレーションで使用できるデータトレースの長さが限られているため、イベントの発生が希少である場合に得られる確率の値には誤差が生じ易い。そのため、待ち行列長の大きい区間では結果の揺れと確率値の急な減少が起きている。
シミュレーションのためには個々のパケットの到着時間と長さが必要であり、計算時間がかかるのみならず、高速回線の場合、そのようなデータを得ることが困難または不可能な場合もある。これに対して、断片的自己相似過程に基づく解析(マルチスケール解析)を用いる計算は時間間隔mΔt内のトラヒック量を知ることができれば、可能であり、評価の時間を大いに短縮できる。
【0040】
次にトラヒックの評価について説明する。
待ち行列長が予め定められた特定の値を超える確率を設計値と比較し、トラヒック性能を評価する。例えば、図4(a)では、待ち行列長Qが10ビットを超える確率が約10-5であるが、これで充分であれば、トラヒック性能を良好と評価し、もっと待ち時間を少なくすべきであれば、トラヒック性能を改善すべきと評価する。改善すべきときは、負荷が70%以下になるように、回線容量を増加するように設計に反映できる。または、回線容量の増加が不可能な場合、負荷を減少するようにトラヒックコントロールに反映することも可能である。
このように、トラヒックが正規性に適合する場合には、MFBMを利用して、時間スケール区間毎に異なる自己相似指数と分散係数を採用する断片的自己相似過程に基づく解析(マルチスケール解析)を行うことにより、トラヒック性能を良く評価できる。
【0041】
図5に本実施の形態における通信トラヒックの評価方法を実施するための通信トラヒック評価装置1の構成例を示す。
図において、2は中央処理装置(CPU)であり、パーソナルコンピュータ等で構成される。CPU2は、特徴量導出手段3、補分布演算手段6、品質評価手段7、制御手段8を有する。また、特徴量導出手段3は分散-時間特性形成手段4と時間スケール区間形成手段5を含む。制御手段8は通信トラヒック評価装置1を構成する各手段を制御して、通信トラヒックの評価の各工程を実行させる。CPU2には、データ採取手段9、データ記憶手段10、表示手段11が付随されており、CPU2及びこれらの付随手段等により、通信トラヒック評価装置1が構成される。これらの機能については、次の通信トラヒックの評価方法の処理フローの説明で併せて説明する。
【0042】
図6に、本実施の形態における通信トラヒックの評価方法の処理フロー例を示す。
まず、通信トラヒックの各時間スケールmにおける到着トラヒックデータX(t)を採取する(データ採取工程:S001)。採取はデータ採取手段9により行われ、採取したデータは記憶手段10に記憶される(データ記憶工程:S002)。
【0043】
次に、採取されたデータX(t)に基づき、分散-時間特性を求める(分散-時間特性導出工程:S003)。分散-時間特性は分散-時間特性形成手段4で統計処理により求められる。詳しくは単位時間をΔtとし、k番目の、連続するm個の単位時間m×Δt内に到着した通信トラヒックの単位時間Δt当たりのビット数の平均値をX(m)(k)とし、その分散Var[X(m)(k)]の時間スケールmに対する分散-時間特性を求める。
【0044】
次に、分散-時間特性からマルチスケールフラクショナルブラウン運動(MFBM:Multiscale Fractional Brownian Motion)過程を利用して自己相似指数等の特徴量を導出する(自己相似指数等特徴量導出工程:S004)。特徴量の導出は特徴量導出手段3で行われる。分散Var[X(m)(k)]の時間スケールmに対する関係に基づいて、それぞれの時間スケール区間におけるトラヒックの自己相似指数Hを含む特徴量(特徴量は自己相似指数H及び分散係数aである)を導出するが、この工程で、時間スケール区間形成手段5は、例えば、隣り合う時間スケールmi、i+1の比mi+1/、mが一定になるように定め、隣り合う時間スケール区間の中間値(対数座標で)である評価点時間スケールm、mi+1に対して、自己相似指数H、Hi+1の差があまり大きくならないように時間スケール区間の長さ(l/s、li+1/si+1)を一定値(mi+1/mの倍数)に定める。これらの時間スケール区間内の分散-時間特性を用いて、特徴量導出手段4により自己相似指数H及び分散係数aが導出される。なお、平均到着率λ、回線帯域Cは入力される。ここに、分散-時間特性導出工程S003と自己相似指数等特徴量導出工程S004とが特徴量導出工程に含まれる。
【0045】
次に、時間スケールmと待ち行列長xの関係(式6参照)を用いて、導出された自己相似指数を含む特徴量(自己相似指数H及び分散係数a)に基づき、通信網の負荷が与えられたときの、通信網に生成される待ち行列の待ち行列長Qが所定値xより大きくなる確率Pr(Q>x)を求める(確率導出工程:S005)。この確率導出は補分布演算手段6により行われる。ここにおいて、時間スケールmと待ち行列長xの関係は適正時間スケールmと待ち行列長xとの関係を示す(式6)が用いられる。待ち行列長Qが所定値xより大きくなる確率Pr(Q>x)は(式4)で導出される。通信網の負荷は平均到着率λと回線帯域Cで与えられる。
【0046】
次に、確率Pr(Q>x)を用いて、通信トラヒックの待ち時間に係る品質を評価する(品質評価工程:S006)。品質評価は品質評価手段7で行われる。次に、評価結果が補分布と共に表示装置11に表示される(表示工程:S007)。これにより、通信トラヒックの品質が精度よく評価でき、また、通信トラヒックの設計や管理に還元され得る。
【0047】
[第2の実施の形態]
第2の実施の形態では、時間スケール区間内の多数の点から最小二乗法を用いて、FBM確率過程のパラメータを導出する。また、SlNET以外のトラヒックデータの例としてAbileneネットワークのデータについて解析を行った。
図1のBはAbileneデータである。Abileneネットワークは、米国Internet2プロジェクトで運営されているインターネットバックボーンである。本実施の形態で使用したのは、現地時間午前9時から採取された2時間のデータトレースの中から、午前10時10分から始まる、長さ30分のデータである。理由は、その間平均到着率λがほぼ一定に保たれているからである。到着率が高いので、単位時間Δtを0.1msと短くした。なお、各種統計量については表1を参照されたい。
【0048】
図1で示したように、トラヒックデータは長期依存性を有していることが分かる。SINETのデータに比して、湾曲の近傍における自己相似指数の変化が大である。このため、時間スケール区間の形成にあたり、時間スケール区間の長さを約40(1.139~41.14)とした。
さらに、SINETのデータに比べ、持続時間が短いため、時間スケールmが大きくなる領域では、分散値のばらつきが顕著である。
【0049】
このため、時間スケール依存の自己相似指数Hを決めるとき、もし実施形態1のように、(式8)で表す2点法を使うと、負荷の大きい領域では、得られる確率のばらつきが大きくなる。そこで、(式8)の2点法の代わりに、(式11)に示す最小二乗法を用いて、自己相似指数を求める。
【数12】
JP0004081552B2_000014t.gif
ここに、m,m,…,m(N≧2)はi番目の時間スケール区間内にある、最小と最大時間スケール(sとl)を含むすべての時間スケール値が用いられる。すなわち、s≦m≦lである。
【0050】
図7にAbileneデータに関する待ち行列長の補分布を示す。図7(a)は負荷70%、図7(b)は負荷80%のデータである。
横軸は待ち行列長の所定値x、縦軸は待ち行列長Qがxを超える確率Pr(Q>x)である。負荷は、回線容量(または回線帯域)Cに対する平均到着率λの割合を示す。
プロット点の帯(Line A:最小二乗法、Line A’:2点法)は本実施の形態における断片的自己相似過程に基づく解析(マルチスケール解析)の結果であり、それぞれの点が一つの時間スケール区間の中間点である評価点時間スケールに係るプロット点である。実線(Line B)はシミュレーションデータである。
【0051】
Abileneデータでは負荷が小さい場合(70%)は、近似解析結果はシミュレーション結果とは良く一致しているが、負荷が大きい場合(80%)、2点法(Line A’)により求めた自己相似指数を使った場合の確率のばらつきが大きくなっている。例えば、図1の分散-時間特性の横軸値100,000の(10秒に相当する)時間スケールは図7(b)待ち行列長x=10の適正時間スケールであるため、図1の横軸座標100,000以降の分散値のばらつきが図7(b)の横軸座標x=10以降のばらつきの起因である。
それに対して、(式11)に示す最小二乗法を使った解析結果(Line A)では確率のばらつきがなくなり、シミュレーション結果と良く一致している。
【0052】
また、本発明は第1、第2の実施の形態における通信トラヒックの評価方法を、コンピュータに実行させるためのプログラムとして、また当該プログラムを記録したコンピュータ読み取り可能な記録媒体としても実現可能である。プログラムは、コンピュータに内蔵のROMに記録して用いても良く、FD、CD-ROM、内蔵又は外付けの磁気ディスク等の記録媒体に記録し、コンピュータに読み取って用いても良く、インターネットを介してコンピュータにダウンロードして用いても良い。
【0053】
以上、本発明の実施の形態について説明したが、本発明は上記の実施の形態に限定されるものではなく、実施の形態に種々変更を加えられることは明白である。
上記実施の形態では、時間スケール区間に関し、その長さl/sを一定とする例を説明したが、例えば、l/sを湾曲の近傍で大きく、他で小さくするなど、時間スケール区間の長さ(l/s)を分散-時間特性の湾曲の度合いに応じて変えても良い。また、時間スケール区間を互いに重ならないように定め、時間スケール区間の複数の点を評価点時間スケールとしても良い。また、隣り合う時間スケールの比mi+1/mを一定にしなくても良く、時間スケール区間の長さl/sをmi+1/mの倍数にしなくても良い。
また、分散-時間特性の代わりに、アイデーシー(IDC:Index of Dispersion for Counts)など、他の特徴量と時間スケールの関係を利用して、自己相似指数を導出することもできる。
また、正規性が成立しない場合でも断片的自己相似性を使った本発明を適用可能である。その場合には、各時間スケール区間は3次以上の特徴量も含むような、例えばアルファステ-ブル(α-stable)な自己相似性過程などで構成される断片的自己相似過程を用いて解析を行なう。
【産業上の利用可能性】
【0054】
本発明は通信トラヒックの評価に利用できる。
【図面の簡単な説明】
【0055】
【図1】通信トラヒックサンプルデータの分散—時間特性を示す図である。
【図2】本発明を使った解析アルゴリズムのフローチャートである。
【図3】分散-時間特性における時間スケール区間の例を模式的に示す図である。
【図4】SINETデータに関する待ち行列長の補分布を示す図である。
【図5】第1の実施の形態における通信トラヒック評価装置の構成例を示す図である。
【図6】第1の実施の形態における通信トラヒックの評価方法の処理フロー例を示す図である。
【図7】Abileneデータに関する待ち行列長の補分布を示す図である。
【図8】分散-時間特性を2本の直線で近似したときの図である。
【図9】分散-時間特性を3本の直線で近似したときの図である。
【符号の説明】
【0056】
1 通信トラヒック評価装置
2 中央処理装置(CPU)
3 特徴量導出手段
4 分散-時間特性形成手段
5 時間スケール区間形成手段
6 補分布演算手段
7 品質評価手段
8 制御手段
9 データ採取手段
10 データ記憶手段
11 表示手段
a、a 分散係数
C 回線帯域
H、H、Hi+1 自己相似指数(ハーストパラメータ)
i番目時間スケール区間の最大時間スケール
適正時間スケール
m、m、mi+1 時間スケール
i番目時間スケール区間の最小時間スケール
/s時間スケール区間の長さ
Pr(Q>x) 待ち行列長Qがxより大きくなる確率
v(x)、Var[X(m)(k)] 分散
x 待ち行列長(所定の待ち行列長を含む)
X(t) 確率過程
Δt 単位時間
λ 平均到着率
ρ 平均負荷


図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8