リンク収容率上限値算出装置、リンク収容率上限値算出方法、及びプログラム
【課題】既定のパケット損失率を満たすリンク収容率の上限を算出し、探索に要する計算量を削減する。
【解決手段】リンク収容率上限値算出装置であり、対象のフローを(m+1)個のサブフローに分割する手段と、サブフローi群(i=1,.,(m+1))を構成する手段と、リソース配分手段と、を備え、バケット1,.,ｍのバッファ長をb1,.,bm、バケット(m+1)の最大トークン停留量をb(m+1)、バケット1,.,(m+1)のトークンレートをr1,.,r(m+1)とした場合に、前記リソース配分状態において所与のリンク損失率閾値のもとでb(m+1)および収容率を(b1,.,bm,r1,.,rm,r(m+1))により決定する機能であって、かつその内r(m+1)を(b1,.,bm,r1,.,rm)の関数として算出し、収容率上限値を(b1,.,bm,r1,.,rm)領域上の最適値探索問題に帰着し算出する機能を有す。
【解決手段】リンク収容率上限値算出装置であり、対象のフローを(m+1)個のサブフローに分割する手段と、サブフローi群(i=1,.,(m+1))を構成する手段と、リソース配分手段と、を備え、バケット1,.,ｍのバッファ長をb1,.,bm、バケット(m+1)の最大トークン停留量をb(m+1)、バケット1,.,(m+1)のトークンレートをr1,.,r(m+1)とした場合に、前記リソース配分状態において所与のリンク損失率閾値のもとでb(m+1)および収容率を(b1,.,bm,r1,.,rm,r(m+1))により決定する機能であって、かつその内r(m+1)を(b1,.,bm,r1,.,rm)の関数として算出し、収容率上限値を(b1,.,bm,r1,.,rm)領域上の最適値探索問題に帰着し算出する機能を有す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット交換網において、パケット損失や転送遅延を防止して、転送品質を確保（低パケット損失，低遅延等）するために、NW流入フローによる帯域利用に上限を設ける方式に関連し、特に、複数のフローを転送する固定長バッファを有するルーター等の通信装置において、パケット損失率が既定のパケット損失率上限以下となるリンク収容率（リンク帯域使用率とも呼ぶ）上限値を算出する技術に関するものである。
【背景技術】
【０００２】
複数のフローを転送する固定長バッファを有する通信装置における、パケット損失率が既定のパケット損失率上限以下となるリンク収容率上限値を算出するための従来技術として、下記の従来技術１と従来技術２がある。従来技術１、２において、リンク収容率上限を算出する装置における入力、及び出力は、下記のとおりとする。
【０００３】
入力：リンク帯域bw、バッファサイズbf、パケット損失率上限値L、対象フローのデータ（パケットのタイムスタンプとサイズのリスト）
出力：リンク収容率上限値a_max
＜従来技術１＞
対象とするフローのパケットサイズsは一定で、パケット到着がポアソン過程に従い、重畳する複数本のフローのパケット到着は互いに独立であるとしてモデル化を行う。このとき、重畳したフロー群のパケット到着もポアソン過程に従うことから、任意のリンク収容率aに対して、収容率a（サービス時間a/bw）、
【０００４】
【数１】
の待ち行列モデルM/D/1/Kを用いてパケット損失率lを求めることができる。
【０００５】
そこで、従来技術１では、sを対象フローの平均パケットサイズとして、l≦Lとなるようなaの最大値を二分法（0≦a≦1の範囲）によって求め、リンク収容率上限値a_maxとして出力する。
【０００６】
＜従来技術２＞
従来技術２は、Elwalidらのフローモデル化手法（非特許文献１）（以下、これを従来手法と呼ぶ）を応用した技術である。
【０００７】
従来技術２では、リーキーバケット・アルゴリズム（非特許文献２）を実行する単一の仮想的なリーキーバケット（サイズ無限、流出レートr）を用いて対象フローのパケット到着特性を定量化する。そして、パケットが常に一定量（サイズb）バースト到着するモデルを作り、重畳した全体トラヒックのバースト到着がポアソン過程に従うとみなす。このとき、
【０００８】
【数２】
使用率r*a/r0の待ち行列モデルM/D/1/Kを用いてフロー群のパケット損失率lを求めることができる。
【０００９】
つまり、任意のリンク収容率a、リーキーバケットの流出レートr（r≧対象フローの平均レートr0）に対してパケット損失率lを求めることができる。
【００１０】
そこで、従来技術２では、rをr0 と初期設定して、l≦Lとなるようなaの最大値を二分探索法（0≦a≦1の範囲）によって求めて結果をa_maxとする。そして、rを一定量ずつ増やして上記処理を繰り返してaを出力し、もしa>a_maxならばa_maxにaを代入してa_maxを更新する。そして、上記手順を繰り返して実行し、一定回数a_maxが更新されないときに繰り返し実行を終了して、a_maxを、目的のリンク収容率上限値a_maxとして出力する。
【００１１】
なお、上記従来技術２で用いられるリーキーバケット・アルゴリズムは、仮想的なバケットにビット量を補充し、一定レートでバケットのビット量を流出させるモデルのアルゴリズムである。バケットが空いている場合にはビット量が流出されず、満杯の場合にはビット量が補充されない。対象フローのパケット到着時にパケットサイズ相当のビット量を補充する状況で、パケットがバースト的に到着する場合、瞬間的に消費レートに対して補充量が過多となり、バケット内にトークンが滞留することになる。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】A. Elwalid, et al.,"A new approach for allocating buffers and bandwidth to heterogeneous, regulated traffic in an ATM node,"IEEE J. Select. Areas Commun., vol.13, pp.1115-1127, Aug. 1995.
【非特許文献２】ITU-T Recommendation I.371,"Traffic control and congestion control in B-ISDN,"Mar. 2004.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
対象フローの実際のトラヒックは、バースト性を伴っている部分と、定期的なパケット送出を行っている部分の合成からなると考えられる。しかし、従来技術１ではパケットのバースト到着を想定しておらず、パケットがバースト到着する場合に比べて、算出されるパケット損失率lを実態より低く推定してしまい、NW設計上のリンク収容率上限値を適切に出力することができない。
【００１４】
一方、従来技術２では、全てのトラヒックがバースト到着するという、実態より過度にバースト性の高い単一ソースのON/OFFモデルを作ることになるため、パケット損失率を実態より高く推定してしまいNW設計上のリンク収容率上限値を低く推定することから、NWの利用効率が上がらないという問題がある。
【００１５】
上記の問題を解決するために、対象フローの特性をより適切にモデル化して、より実態に近いパケット損失率を推定することにより、予め定められたパケット損失率以下を満たせるリンク収容率の適切な上限値を算出するための技術が先願である特願２０１０−１８８８７８に記載されている。特願２０１０−１８８８７８に記載された技術は、本発明の前提となる技術であるので、これを「前提技術」とよぶことにする。
【００１６】
しかし、後に詳述するように、前提技術では、収容率上限値算出に際して、3 個のパラメータを独立に動かし決定することとしており、探索に要する計算量が非常に大きいという課題がある。更に、前提技術では、各パラメータの探索範囲を特定していないため、本来探索対象である領域以外を探索する懸念、逆に探索対象の領域を探索対象としない懸念も存在する。
【００１７】
本発明は、従来技術１、２における課題を解決するとともに、前提技術における上記の課題を解決するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記の課題を解決するために、本発明は、パケット交換網における複数のフローを転送する固定長バッファを有する通信装置における、既定のパケット損失率上限以下を満たすリンク収容率上限値を算出するリンク収容率上限値算出装置であり、実トラヒックのキャプチャデータの入力を受け、当該キャプチャデータから対象情報を抽出する情報抽出手段と、前記情報抽出手段により抽出された情報に対して複数個のリーキーバケット（バケット1,2,...,(m+1)とする）を適用し、対象のフローを(m+1)個のサブフローに分割するサブフロー分割手段と、前記サブフロー分割手段で得られた各サブフロー毎に、それを重畳してサブフローi群 (i=1, 2,...,(m+1) )を構成するサブフロー群構成手段と、前記通信装置の帯域およびバッファリソースを各サブフロー群毎に固定的に配分するリソース配分手段と、を備えるリンク収容率上限値算出装置であって、前記リーキーバケット1,2,...,ｍのバッファ長をb1, b2, ...,bm、前記リーキーバケット(m+1) の最大トークン停留量をb(m+1)、バケット1, 2,...,(m+1)のトークンレートをr1, r2, .....,r(m+1)とした場合に、前記リソース配分手段により配分されたリソース配分状態において所与のリンク損失率閾値のもとでb(m+1) および収容率を(b1,...,bm,r1, ..., rm,r(m+1)) により決定する機能であって、かつその内r(m+1)を(b1,...,bm,r1,...,rm) の関数として算出し、収容率上限値を(b1,..., bm, r1,...,rm) 領域上の最適値探索問題に帰着して算出する機能を有する収容率上限値算出手段を備えることを特徴とするリンク収容率上限値算出装置として構成される。
【００１９】
前記収容率上限値算出手段は、所与のリンク損失率閾値のもとでパラメータ(b1,...,bm, r1,...,rm,r(m+1))のうちいずれか１個を他のパラメータの関数として表すことにより、処理を実行するように構成してもよい。
【００２０】
また、前記収容率上限値算出手段は、前記最適値探索における探索対象の関数の特徴を勘案した探索法を適用して、前記最適値探索の処理を実行するように構成することもできる。
【００２１】
また、本発明は、上記リンク収容率上限値算出装置が実行するリンク収容率上限値算出方法として構成することもできる。
【００２２】
更に、本発明は、コンピュータを、上記リンク収容率上限値算出装置の各手段として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【００２３】
本発明によれば、対象フローの特性をより適切にモデル化して、より実態に近いパケット損失率を推定することにより、予め定められたパケット損失率以下を満たせるリンク収容率の適切な上限値を算出することができる。
【００２４】
更に、本発明によれば、前提技術における課題が解決される。すなわち、探索に要する計算量が削減される。また、各パラメータの探索範囲を特定できるため、本来探索対象である領域以外を探索する懸念や、逆に探索対象の領域を探索対象としない懸念が解消される。
【図面の簡単な説明】
【００２５】
【図１】対象フローを仮想的にサブフロー１とサブフロー２に分割することを説明するための図である。
【図２】前提技術におけるリンク収容率上限値算出装置１０の機能構成例である。
【図３】サブフロー分割機能部１１における処理の概念を説明するための図である。
【図４】サブフロー分割機能部１１が実行する処理手順を示すフローチャートである。
【図５】パケット損失率算出機能部１２が実行する処理手順を示すフローチャートである。
【図６】リンク収容率上限値算出機能部１３が実行する処理手順を示すフローチャートである。
【図７】リンク収容率上限値最大値探索機能部１４が実行する処理手順を示すフローチャートである。
【図８】前提技術でのリンク収容率上限値の算出方式の処理概念を説明するための図である。
【図９】本発明の実施の形態に係るリンク収容率上限値算出装置の構成例である。
【図１０】本発明の実施の形態に係るリンク収容率上限値算出装置が実行する処理の概念を説明するための図である。
【図１１】収容率上限値算出部の処理手順例を示す図である。
【図１２】SA(Simulated Annealing)法を適用する場合において、高コスト解の採択率が座標に依存していることを示す図である。
【図１３】SA(Simulated Annealing)法を適用して、収容率上限値算出部が探索を行う場合の手順の一例を示す図である。
【発明を実施するための形態】
【００２６】
＜前提技術＞
以下、本発明の実施の形態を説明するにあたり、まず、その前提となった前提技術について説明する。
【００２７】
（概要）
図１を参照して、前提技術の概要を説明する。図１の上段に示すように、従来技術２では、リンク収容率上限値を算出する対象となる対象フローが常にバースト到着するものとしてモデル化していたところ、前提技術においては、図１の下段に示すように、リンク収容率上限値を算出する対象となる対象フローを仮想的にサブフロー１とサブフロー２に分割してモデル化を行うことにより対象フローの特性をより適切にモデル化する。これにより、より実態に近いパケット損失率を推定することができる。このように実態に近いパケット損失率を推定することにより、予め定められたパケット損失率以下を満たせるリンク収容率の適切な上限を算出することが可能である。
【００２８】
（装置構成）
図２に、前提技術におけるリンク収容率上限値算出装置１０の機能構成例を示す。図２に示すように、リンク収容率上限値算出装置１０は、対象フローを仮想的なサブフローに分割するサブフロー分割機能部１１と、サブフロー群ごとにリンク帯域及びバッファのリソースを固定的に割り当てて、待ち行列モデルを用いてパケット損失率を算出するパケット損失率算出機能部１２と、入力条件に対応したリンク収容率上限値を算出するリンク収容率上限値算出機能部１３と、対象フローに対応したリンク収容率上限値を算出するリンク収容率上限値最大値探索機能部１４と、各種データを格納するデータ記憶部１５とを備えている。
【００２９】
ここで、データ記憶部１５は、各機能部からアクセスされるメモリ等の記憶部であり、各機能部は、データ記憶部１５から処理に用いるデータ（例えば変数の値）を読み出し、処理後のデータをデータ記憶部１５に格納することにより、処理を進める。また、各機能部からの出力は、データ記憶部１５に格納され、他の機能部や他の装置への入力のために読み出される。ただし、リンク収容率上限値最大値探索機能部１４からの出力は、リンク収容率上限値算出装置１０の出力として、そのまま外部に出力することとしてもよい。
【００３０】
リンク収容率上限値算出装置１０には、リンク帯域bw、ルータのバッファサイズbf、パケット損失率上限L、及び、対象フローのデータ（本実施の形態では、パケットのタイムスタンプとサイズのリスト）が入力され、対象フローに対応したリンク収容率上限値a_maxが出力される。例えば、入力データのうちのリンク帯域bw、バッファサイズbf、パケット損失率上限Lは、NW設計者等により、入力手段を用いてリンク収容率上限値算出装置１０に入力され、対象フローのデータは、例えば、外部のデータベース装置に蓄積されたデータを通信ネットワークを介して受信することができる。
【００３１】
（各機能部の詳細）
以下、図２に示すリンク収容率上限値算出装置１０の各機能部の処理を詳細に説明する。後述するように、本実施の形態に係るリンク収容率上限値算出装置１０においては、リンク収容率上限値最大値探索機能部１４が、各機能部を動作させる制御を行って、結果として対象フローに対応したリンク収容率上限値a_maxを算出するが、以下では、各機能部毎に処理内容を説明する。
【００３２】
[サブフロー分割機能部１１]
サブフロー分割機能部１１は、リーキーバケット・アルゴリズムを実行する2 個の仮想的なリーキーバケットを用いてフローのパケット到着特性を定量化し、対象フローを仮想的なサブフローに分割するサブフロー分割処理を行う。
【００３３】
より具体的には、サブフロー分割機能部１１は、対象フローのデータ、バケット1の流出レートr1、バケット1のサイズb1、及びバケット2の流出レートr2を入力し、バケット2があふれないようにする上で必要なバケットサイズb2を出力する機能を有する。サブフロー分割機能部１１における処理の概念を図３を参照して説明する。
【００３４】
図３に示すとおり、リーキーバケット・アルゴリズムを実行する2 個の仮想的なリーキーバケットを用いてフローのパケット到着特性を定量化するにあたり、バケット1 のサイズはb1、流出レートはr1 とする。また、バケット2 のサイズは無限として、流出レートはr2 とする。
【００３５】
そして、対象フローのデータから対象フローを再現して到着パケットを観測し、パケット到着毎に観測パケットサイズ相当のビット量（トークン）をバケット1 に補充する。バケット1 が満杯の場合には、バケット1 に補充しきれない分のビット量をバケット2 へ補充する。このとき、観測中におけるバケット2 の最大ビット滞留量b2 を求める。そして、対象フローは以下の2 つのサブフローで構成されるとみなす。
【００３６】
サブフロー1：平均レートr1 で常にサイズb1 のバースト到着となるフロー
サブフロー2：平均レートr2 で常にサイズb2 のバースト到着となるフロー
なお、r1 = 0，b1 = 0 の場合，従来手法と同等となる。
【００３７】
図４は、対象フローのデータを与えて、r1、b1、r2を入力パラメータとし、b2を出力するための処理手順を示すフローチャートである。図４の処理は、図３に示す処理に対応するものである。また、図４の処理における一時変数等の意味は、図４内に示すとおりである。
【００３８】
図４を参照して、サブフロー分割機能部１１が実行するb2を出力するための処理手順を説明する。なお、以下の処理で、変数に数値を代入するとは、データ記憶部１５の所定領域に、数値を格納することに相当する。
【００３９】
まず、ステップ１０１において、パケット１個目のタイムスタンプをltimeに代入する。次に、ステップ１０２において、パケット１個目のパケットサイズをql1maxに代入し、ql1maxの値をql1に代入する。
【００４０】
次に、ql1>b1であるか否かの判定が行われ（ステップ１０３）、判定結果がYesであればステップ１０４に進み、Noであればステップ１０５に進む。ステップ１０４では、(ql1-b1)がql2に代入され、ql2の値がql2maxに代入される。
【００４１】
上記のステップ１０１〜１０４の処理はパケット１個目の処理に該当する。
【００４２】
ステップ１０５において、次のパケットデータの有無が判定され、Noであればステップ１１７に進み、Yesであれば次のパケットデータの処理を行うためにステップ１０６に進む。
【００４３】
ステップ１０６において、(ql1-(タイムスタンプ-ltime)*r1)がql1に代入され、(ql2-(タイムスタンプ-ltime)*r2)がql2に代入される。次に、ステップ１０７において、ql1<0であるか否かの判定が行われ、判定結果がYes（バケット１が空）であればステップ１０８に進み、Noであればステップ１０９に進む。
ステップ１０８において、ql1に０が代入される。ステップ１０９では、ql2<0であるか否かの判定が行われ、判定結果がYes（バケット２が空）であればステップ１１０に進み、Noであればステップ１１１に進む。ステップ１１０において、ql2に０が代入される。
【００４４】
上記のステップ１０５〜１１０の処理はバケットからのビット量流出処理に該当する。
【００４５】
ステップ１１１では、(ql1＋パケットサイズ)がql1に代入される。続いて、ステップ１１２において、ql1>b1であるか否かの判定が行われ、判定結果がYes（バケット１が満杯）であればステップ１１３に進み、Noであればステップ１１４に進む。
【００４６】
ステップ１１３において、(ql1-b1)がql2に代入され、ql2の値がql2maxに代入される。ステップ１１４において、ql2>ql2maxであるか否かの判定が行われ、判定結果がYesであればステップ１１５に進み、Noであればステップ１１６に進む。ステップ１１５において、ql2がql2maxに代入される。
【００４７】
上記のステップ１１１〜１１５の処理はバケットへのビット量補充処理に該当する。
【００４８】
ステップ１１６において、パケットのタイムスタンプがltimeに代入される。これは、直近パケットタイムスタンプltimeの更新処理である。
【００４９】
そして、ステップ１０５に判定において、次のパケットデータがなくなった場合に、ql2maxをb2（バケット２があふれないようにする上で必要なバケットサイズ）として出力する。
【００５０】
[パケット損失率算出機能部１２]
パケット損失率算出機能部１２は、パケット損失率算出処理を行う。パケット損失率算出処理におけるパケット損失率算出機能部１２への入力と、パケット損失率算出機能部１２からの出力は下記のとおりである。
【００５１】
入力：リンク帯域bw、ルータバッファサイズbf、対象フロー平均レートr0、バケット1の流出レートr1、バケット1のサイズb1、バケット2の流出レートr2、バケット2があふれないようにする上で必要なバケットサイズb2、リンク収容率a
出力：パケット損失率l
パケット損失率算出機能部１２は、サブフローを重畳したトラヒック（サブフロー群）ごとにリンク帯域及びバッファのリソースを固定的に割り当てて、それぞれのサブフロー群において仮想的な待ち行列モデルを従来手法に準じた方法で評価してサブフロー群毎のパケット損失率を算出して、リンク全体でのパケット損失率lを算出する機能を有する。
【００５２】
ここで、リーキーバケットでモデル化されたサブフロー1に対して帯域リソースr1，バッファリソースb1を用意するとき、b1はサブフロー1の最大キュー長に等しいことからパケット損失は生じない。
【００５３】
よって、上述した固定的に割り当てるリソースとして、サブフロー1 群に対してパケット損失が生じないようリンク収容率に応じたリンク帯域リソースr1 *(bw*a/r0)を割り当て、バッファリソースb1*(bw*a/r0)を割り当てる。また、残余リンク帯域リソース(bw-r1*(bw*a/r0))、残余バッファリソース(bf-b1*(bw*a/r0) )をサブフロー2 群に対して割り当てる。
【００５４】
そして、サブフロー2 群においてはサイズb2 のバーストパケットがランダムに到着するモデルを考えて、
【００５５】
【数３】
使用率(r2*(bw*a/r0))/(bw-(bw*a/r0)*r1)の待ち行列モデルM/D/1/K（非特許文献１）を用いてサブフロー2 群のパケット損失率l2 を求める。
【００５６】
上記の算出結果から、リンク全体のパケット損失率l=l2*r2/(r1+r2) を求める。なお、r1=0、k=0とする場合、サブフロー1群は無いものとしてサブフロー2のみを重畳することになるので、従来技術２と同等となる。
【００５７】
パケット損失率算出機能部１２が実行する処理手順は、図５に示すとおりである。すなわち、ステップ２０１において、
【００５８】
【数４】
使用率(r2*(bw*a/r0))/(bw-(bw*a/r0)*r1)の待ち行列モデルM/D/1/K（非特許文献１）を用いてサブフロー2群のパケット損失率l2を求め、ステップ２０２において、パケット損失率l=l2*r2/(r1+r2)を算出し、出力する。
[リンク収容率上限値算出機能部１３]
リンク収容率上限値算出機能部１３は、リンク収容率上限値算出処理を行う。リンク収容率上限値算出機能部１３への入力と、リンク収容率上限値算出機能部１３からの出力は、下記のとおりである。
【００５９】
入力：リンク帯域bw、ルータバッファサイズbf、パケット損失率上限L、対象フロー平均レートr0、バケット1の流出レートr1、バケット1のサイズb1、バケット2の流出レートr2、バケット2があふれないようにする上で必要なバケットサイズb2
出力：入力条件r1、r2、b1、b2に対応したリンク収容率上限値a_m
より具体的には、リンク収容率上限値算出機能部１３は、入力条件r1、r2、b1、b2の下で、損失率l≦損失率上限Lとなるようなリンク収容率aの最大値a_mを出力する。例えば、二分法（0≦a≦1の範囲）を用いて、リンク収容率aを変えながらパケット損失率算出機能部１２を用いてパケット損失率の算出処理を繰り返すことにより、リンク収容率aの最大値a_mを算出する。
【００６０】
リンク収容率上限値算出機能部１３が実行する処理手順を図６のフローチャートを参照して説明する。
【００６１】
リンク収容率aを設定し（ステップ３０１）、パケット損失率算出機能部１２を用いてステップ３０１で設定したリンク収容率aに対応するパケット損失率lを算出する（ステップ３０２）。
【００６２】
そして、リンク収容率上限値算出機能部１３は、算出した損失率lと、与えられた損失率上限Lを比較し、損失率lが損失率上限L以下ならば、a_mにaを代入する（ステップ３０３）。損失率lが損失率上限L以下でなければa_mは更新されない。リンク収容率上限値算出機能部１３は、ステップ３０１〜３０３の処理を十分な回数繰り返した後（ステップ３０４）、a_mを、入力条件r1、r2、b1、b2に対応したリンク収容率上限値として出力する（ステップ３０５）。上記の十分な回数の判定は、例えば、予め定めた回数の繰り返しを行ったかどうか、処理を繰り返す中でのa_mの変化が、予め定めた値よりも小さくなったかどうか、などにより行うことができる。
【００６３】
以下、ここでの処理をより具体的に説明する。
【００６４】
リンク収容率上限値算出機能部１３は、まず、リンク収容率をa=(0+1)/2=0.5と設定し（ステップ３０１）、パケット損失率算出機能部１２を用いてリンク収容率a=0.5のときのパケット損失率lを算出する（ステップ３０２）。
【００６５】
続いて、リンク収容率上限値算出機能部１３は、損失率lと損失率上限Lを比較し、損失率lが損失率上限L以下であれば、a_mにaを代入し（ステップ３０３）、a=(0.5+1)/2=0.75と設定して（ステップ３０４、ステップ３０１）、再度ステップ３０２の計算を行う。ステップ３０３において、損失率lが損失率上限Lを上回っていれば、a_mは更新されずa=(0+0.5)/2=0.25として再計算を行う。
【００６６】
[リンク収容率上限値最大値探索機能部１４]
リンク収容率上限値最大値探索機能部１４は、対象フローのデータ、リンク帯域bw、ルータバッファサイズbf、及び損失率上限Lを入力し、リンク収容率上限値の最大値探索処理を行って、対象フローに対応したリンク収容率上限値a_maxを出力する。
【００６７】
より具体的には、リンク収容率上限値最大値探索機能部１４は、r1、r2、b1を変化させてサブフロー分割機能部１１によりb２を求め、リンク収容率上限値算出機能部１３によりリンク収容率上限値a_mを求める。そして、各r1、r2、b1の組に対するa_mの中から最大値を探索し、a_maxとして出力する。
【００６８】
以下、リンク収容率上限値最大値探索機能部１４が実行する処理の手順を図７のフローチャートを参照して説明する。
【００６９】
まず、対象フローの平均レートr0を取得する（ステップ４０１）。この平均レートは、対象フローのデータから算出してもよいし、予めデータ記憶部１５に格納したものを読み出してもよい。続いて、r1、r2、b1をそれぞれ0、r0、0と初期設定する（ステップ４０２）。その後、十分な粒度で網羅的にr1、r2、b1を変更（ただし、r1+r2≧r0）させていきa_mを算出、出力し、もしa_m>a_maxならばa_maxにa_mを代入してa_maxを更新していき、a_mの最大値a_maxを出力する。
【００７０】
すなわち、ステップ４０３において、ステップ４０２での設定値をサブフロー分割機能部１２への入力として使用して、サブフロー分割機能部１２により、バケット２があふれないようにする上で必要なバケットサイズb2を算出する。
【００７１】
続いてステップ４０４において、リンク収容率上限値算出機能部１３により、入力条件r1、r2、b1、及びb2に対応したリンク収容率上限値a_mを算出する。そして、ステップ４０５で、a_m>a_maxであるか否かを判定し、判定結果がNoであればステップ４０７に進み、Yesであればステップ４０６に進む。
【００７２】
ステップ４０６では、a_mをa_maxに代入する。そして、r1、r2、b1を変更して、ステップ４０２からの処理を繰り返す。ステップ４０７では、r1、r2、b1のそれぞれを変更してもa_maxが一定回数以上更新されていないか否かを判定する。判定結果がNo（a_maxの更新がされている場合）であれば、r1、r2、b1を変更して、ステップ４０２からの処理を繰り返す。判定結果がYesであれば、そのときのa_maxをリンク収容率上限値として出力する（ステップ４０８）。
【００７３】
＜前提技術における課題について＞
上述したように、前提技術では、2 個のリーキーバケットを用いて、対象フローのパケット到着特性からモデルトラヒックを構成し、待ち行列モデルを用いてサブフロー(m + 1) 群（前提技術ではm=1）の損失率およびリンク全体の損失率を求める処理を、パラメータを動かしながら行い、リンク収容率上限値を探索する。
【００７４】
前提技術でのリンク収容率上限値の算出方式は、図８のように表すことができる。すなわち、前提技術ではまず、パラメータ(b1, r1, r2) を独立に動かし、対応するa(b1, r1, r2) の値を求める。続いてリンク全体の損失率l(b1, r1, r2, a(b1, r1, r2)) の値を算出する。この値が閾値L 以下であれば、当該a(b1, r1, r2) ,(b1, r1, r2)をそれぞれ最適解およびそれを実現するパラメータの候補として採択する。
【００７５】
そして、上記操作を各(b1, r1, r2)について実施し、a(b1, r1, r2)としてより大きい値が算出された場合には、上記の最適解候補を更新していく。
【００７６】
上記のように、前提技術では、収容率上限値算出に際して、3 個のパラメータを独立に動かし決定することとしているので、探索に要する計算量が非常に大きい。また各パラメータの探索範囲を特定していないため、本来探索対象である領域以外を探索する可能性や、逆に探索対象の領域を探索対象としない可能性がある。
【００７７】
＜前提技術における課題を解決するための構成＞
（装置構成）
上記の課題を解決するための本実施の形態に係るリンク収容率上限値算出装置１００の構成例を図９に示す。本実施の形態に係るリンク収容率上限値算出装置１００は、ネットワークのルータ収容設計等への使用に適した装置であり、図９に示すように、情報抽出部１０１、サブフロー分割部１０２、サブフロー群構成部１０３、リソース配分部１０４、収容率上限値算出部１０５、及びデータ記憶部１０６を備える。
【００７８】
情報抽出部１０１は、実トラヒック（平均レートr0とする）のキャプチャデータの入力を受け、当該キャプチャデータから必要情報を抽出する機能部である。
【００７９】
サブフロー分割部１０２は、情報抽出部１０１により抽出された情報に対して複数個のリーキーバケット（バケット1,2,...,(m+1)とする）を適用し、対象のフローを(m+1)個のサブフローに分割する機能部である。以下、(m+1)個のサブフローは、それぞれサブフロー1、サブフロー2,..., サブフロー(m+1)とする。また、バケット1,2,...,ｍのバッファ長をb1, b2, ...,bm、バケット(m+1) の最大トークン停留量をb(m+1)（m+1は添字）、バケット1, 2,...,(m+1)のトークンレートをr1, r2, .....,r(m+1)とする。
【００８０】
サブフロー群構成部１０３は、サブフロー分割部１０２で得られた各サブフロー毎に、それを重畳して仮想的トラヒックモデルを構成する機能部である。以下、サブフローi を重畳して構成したモデルをサブフローi群 (i=1, 2,...,(m+1) )と記する。
【００８１】
リソース配分部１０４は、ルータの帯域およびバッファリソースを各サブフロー群毎に固定的に配分する機能部である。
【００８２】
また、収容率上限値算出部１０５は、前記リソース配分状態において所与のリンク損失率閾値のもとでb(m+1) および収容率を(b1,...,bm,r1,...,rm,r(m+1)) により決定する機能であって、かつその内r(m+1)を(b1,...,bm,r1,...,rm) の関数として算出し、収容率上限値を(b1,...,bm,r1,...,rm) 領域上の最適値探索問題に帰着して算出する機能を有する機能部である。
【００８３】
収容率上限値算出部１０５は、所与のリンク損失率閾値のもとでパラメータ(b1,...,bm,r1,...,rm,r(m+1))のうちいずれか１個を他のパラメータの関数として表すことにより、処理を実行することが可能である。更に、収容率上限値算出部１０５は、探索対象の関数の特徴を勘案した探索法（例：SA(Simulated Annealing)における重み付け等)を適用して、前記最適値探索の処理を実行することができる。
【００８４】
ここで、データ記憶部１０６は、各機能部からアクセスされるメモリ等の記憶部であり、各機能部は、データ記憶部１０６から処理に用いるデータ（例えば変数の値）を読み出し、処理後のデータをデータ記憶部１０６に格納することにより、処理を進める。また、各機能部からの出力は、データ記憶部１０６に格納され、他の機能部や他の装置への入力のために読み出される。
【００８５】
リンク収容率上限値算出装置１００は、コンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、リンク収容率上限値算出装置１００の各部で行われる処理や機能は、リンク収容率上限値算出装置１００を構成するコンピュータに内蔵されるＣＰＵやメモリなどのハードウェア資源を用いて、各部で実施される処理に対応するプログラムを実行することによって実現することが可能である。また、当該プログラムは、当該プログラムを記録したＦＤ、ＣＤ−ＲＯＭ、ＤＶＤなどの記録媒体や、インターネットなどのネットワークを介して市場に流通させることができる。
【００８６】
また、リンク収容率上限値算出装置１００は、単独の装置として実現してもよいし、ネットワーク運用監視装置やネットワーク設計支援装置の機能の一部、あるいは、ルータ等の通信装置の機能の一部として構成することもできる。
（リンク収容率上限値算出装置１００における処理概要）
次に、リンク収容率上限値算出装置１００が実行する処理の概念を図１０に示す。図１０は、説明を分かりやすくするために、m=1の場合を示している。また、前提技術との相違についても説明する。
【００８７】
図１０に示すように、損失率が一定においては、aおよび r2 はそれぞれb1,r1の関数として表すことができる。すなわち、損失率が閾値を与える領域においては、(b1,...,bm, r1,...,rm) のうちの(m-1)個を用いて、他の１個およびa を所定の領域上で表すことができる。そして、前記所定の領域において最大となるa を探索し、それを、求める最適解とする。以下、m =1の 場合において前提技術との比較を行う。
【００８８】
前提技術ではパラメータ(b1,r1,r2) を独立に動かしてa(b1,r1,r2) の上限値を求めたため、例えば各パラメータの探索範囲をそれぞれ
【００８９】
【数５】
とすると探索領域のボリュームは
【００９０】
【数６】
で与えられたのに対し、本発明に係る方式では例えば(b1,r1) のパラメータ空間上の領域（当該領域は明示的に算出可能である）上で探索を行えばよく探索領域のボリュームは
【００９１】
【数７】
で与えられる（図８、１０に示したとおり）。
【００９２】
また、実施の一形態として後述するように、当該パラメータ空間をさらに有界領域に分割し、個々の有界領域上での最適解を比較して全体としての最適解を求める構成とすることが可能である。
【００９３】
（リンク収容率上限値算出装置１００における処理の詳細：ｍ＝１の場合の例）
以下、まず、リンク収容率上限値算出装置１００における処理内容をm=1の場合を例にして説明する。説明にあたって使用する記号の凡例を以下に示す。
【００９４】
【数８】
まず、情報抽出部１０１が、実トラヒック（平均レートr0とする）のキャプチャデータの入力を受け、当該キャプチャデータから対象フローのデータ（パケットのタイムスタンプとサイズのリスト）を抽出し、サブフロー分割部１０２に与える。サブフロー分割部１０２は、情報抽出部１０１により抽出された情報に対して２個のリーキーバケットを適用し、対象のフローを２個のサブフローに分割する。また、サブフロー群構成部１０３は、サブフロー分割部１０２で得られた各サブフロー毎に、それを重畳してサブフロー１群、２群を構成する。ここまでの処理は前提技術と同様である。
【００９５】
リソース配分部１０４は、各サブフロー群に対して、以下に示すようにルータの帯域リソースを固定配分する。本実施の形態では、一例として、サブフロー１群での損失率が０となるように配分を行う場合を示している。
【００９６】
【数９】
この場合、サブフロー２群のパケット損失率に「Β＾（サブフロー２に流入するビット数）／Β（データ中の全パケットのビット数）」を乗じることにより、リンク全体の損失率を算出することができる。
【００９７】
［問題設定］
次に、収容率上限値算出部１０５が収容率上限値を算出するにあたっての問題設定について説明する。
【００９８】
サブフロー２群のパケット損失率は、サブフロー２群に待ち行列モデルM/D/1/Kを適用し算出する。上記リソース配分より、
【００９９】
【数１０】
のM/D/1/K待ち行列モデルを適用すると、収容率上限値を決定することは、以下のような問題として記述できる。なお、以下での［x］は実数xの整数部分を示す。
【０１００】
問題：「
【０１０１】
【数１１】
のもとでリンク収容率（の定数倍）a^(=a/r0)の上限値を与えるパラメータの組を求めよ。ここで
【０１０２】
【数１２】
である。」
［処理手順］
本実施の形態に係るリンク収容率上限値算出装置１００の収容率上限値算出部１０５は、上記の問題を解くための処理を、図１１に示すパラメータ最適化手順に従って実行する。この手順では、探索領域を明確にするために、リーキーバケット２に流入するビット数（Β＾）をパラメータとしてとり、(b1,r1)領域を有界領域に分割する。なお、図１１に示すパラメータ最適化手順は一例である。以下、収容率上限値算出部１０５が実行する処理手順を図１１に沿って説明する。
【０１０３】
ステップ１）リーキーバケット２に流入するビット数Β＾を所与とし、
【０１０４】
【数１３】
をとる。
【０１０５】
ステップ２）
【０１０６】
【数１４】
よりサブフロー２群の待ち行列モデルにおける損失率ρ(k, u)を求める。
【０１０７】
ステップ３）上記損失率を与える(k, u)の組
【０１０８】
【数１５】
を求める。
【０１０９】
ステップ４）上記の各(ki, ui)について
【０１１０】
【数１６】
を求める。これを各(b1,r1)について行い、最大のa^(=a/r0)を与えるものを探索する。
【０１１１】
ステップ５）上記のステップ１~４を、任意の増分幅で
【０１１２】
【数１７】
について実施し、最大のa^×r0を求め、これをリンク収容率最大値として出力する。
【０１１３】
（リンク収容率上限値算出装置１００における処理の詳細：一般のｍについて）
次に、mが一般の場合におけるリンク収容率上限値算出装置１００の処理内容を説明する。新規に必要な記号の凡例を以下に示す。
【０１１４】
【数１８】
まず、情報抽出部１０１が、実トラヒック（平均レートr0とする）のキャプチャデータの入力を受け、当該キャプチャデータから対象フローのデータ（パケットのタイムスタンプとサイズのリスト）を抽出し、サブフロー分割部１０２に与える。サブフロー分割部１０３は、情報抽出部１０２により抽出された情報に対して(m+1)個のリーキーバケットを適用し、対象のフローを(m+1)個のサブフローに分割する。また、サブフロー群構成部１０３は、サブフロー分割部１０２で得られた各サブフロー毎に、それを重畳してサブフローi群 (i=1, 2,...,(m+1) )を構成する。前述したように、(m+1)個のサブフローは、それぞれサブフロー1、サブフロー2,..., サブフロー(m+1)であり、バケット1,2,...,ｍのバッファ長はb1, b2, ...,bm、バケット(m+1) の最大トークン停留量はb(m+1)、バケット1, 2,...,(m+1)のトークンレートはr1, r2, r(m+1)である。
【０１１５】
次に、リソース配分部１０４は、各サブフロー群に対して、以下に示すようにルータの帯域リソースを固定配分する。本実施の形態では、一例として、サブフロー１群での損失率が０となるように配分を行う場合を示している。
【０１１６】
【数１９】
ここでは、サブフロー(m+1)群におけるM/D/1/Kモデルは以下のとおりである。
【０１１７】
【数２０】
［収容率上限値算出部１０５の処理手順］
収容率上限値算出部１０５は、図１１に示すパラメータ最適化手順と同様の手順で収容率上限値を求める処理を実行している。ただし、本例ではmは一般であり、１に限られない。以下、収容率上限値算出部１０５が実行する処理手順（ステップ１１〜１５）を説明する。
【０１１８】
ステップ１１）リーキーバケット(m+1)に流入するビット数Β＾を所与とし、
【０１１９】
【数２１】
をとる。
【０１２０】
ステップ１２）
【０１２１】
【数２２】
よりサブフロー(m+1)群の待ち行列モデルにおける損失率ρ(k, u)を求める。
【０１２２】
ステップ１３）上記損失率を与える(k, u)の組
【０１２３】
【数２３】
を求める。
【０１２４】
ステップ１４）上記の各(ki, ui)について
【０１２５】
【数２４】
を求める。これを
【０１２６】
【数２５】
について行い、最大のa^(=a/r0)を与えるものを探索する。
【０１２７】
ステップ１５）上記のステップ１１~１４を、任意の増分幅で
【０１２８】
【数２６】
について実施し、最大のa^×r0を求め、これをリンク収容率最大値として出力する。
【０１２９】
[探索処理について]
上記のステップ１４（m=1のときのステップ４も同様）において、収容率上限値算出部１０５が実行する探索処理としては種々の手法を用いることが可能である。本実施の形態では、一例として、SA(Simulated Annealing)法を適用する場合を説明する。
【０１３０】
本例においては、
【０１３１】
【数２７】
但し、b(m+1)はその各引数の値が大きい場合の方が、小さい値をとる可能性が高いため、高コスト解採択率は、これら引数の値に応じて重み付けをすることとする。図１２は、この性質をm=1の場合で示した図である。図１２には、高コスト解の採択率が座標に依存していることが示されている。
【０１３２】
【数２８】
パラメータの値に依らず既存のSA法を適用する。
【０１３３】
図１３は、SA(Simulated Annealing)法を適用して、収容率上限値算出部１０５が探索を行う場合の手順の一例を示す図である。本例は、
【０１３４】
【数２９】
探索を行う場合（上記の一番目）における手順を示すものである。
【０１３５】
ステップ２１）
【０１３６】
【数３０】
ステップ２２）解の近傍N(sol)から
【０１３７】
【数３１】
ステップ２３）
【０１３８】
【数３２】
δ>0であるか否かを判定し、δ>0であればステップ２４に進み、そうでなければステップ２５に進む。
【０１３９】
ステップ２４）
【０１４０】
【数３３】
更新後、ステップ２６に進む。
【０１４１】
ステップ２５）
【０１４２】
【数３４】
ステップ２５での判定結果がYesであれば、
【０１４３】
【数３５】
そして、ステップ２４に進む。また、ステップ２５での判定結果がNoである場合、solを更新せずにステップ２６に進む。
【０１４４】
ステップ２６）温度をα×θで更新し、ステップ２２に戻る。収容率上限値算出部１０５は、上記のステップ２２〜２６を所定の回数反復することにより探索を行う。
【０１４５】
以上、説明したように、本実施の形態に係る技術によれば、対象フローの特性をより適切にモデル化して、より実態に近いパケット損失率を推定することにより、予め定められたパケット損失率以下を満たせるリンク収容率の適切な上限値を算出することができるという前提技術と同様の効果が得られるとともに、前提技術における課題が解決される。すなわち、探索に要する計算量が削減される。また、各パラメータの探索範囲を特定できるため、本来探索対象である領域以外を探索する懸念や、逆に探索対象の領域を探索対象としない懸念が解消される。
【０１４６】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１４７】
１０ リンク収容率上限値算出装置
１１ サブフロー分割機能部
１２ パケット損失率算出機能部
１３ リンク収容率上限値算出機能部
１４ リンク収容率上限値最大値探索機能部
１５ データ記憶部
１００ リンク収容率上限値算出装置
１０１ 情報抽出部
１０２ サブフロー分割部
１０３ サブフロー群構成部
１０４ リソース配分部
１０５ 収容率上限値算出部
１０６ データ記憶部
【技術分野】
【０００１】
本発明は、パケット交換網において、パケット損失や転送遅延を防止して、転送品質を確保（低パケット損失，低遅延等）するために、NW流入フローによる帯域利用に上限を設ける方式に関連し、特に、複数のフローを転送する固定長バッファを有するルーター等の通信装置において、パケット損失率が既定のパケット損失率上限以下となるリンク収容率（リンク帯域使用率とも呼ぶ）上限値を算出する技術に関するものである。
【背景技術】
【０００２】
複数のフローを転送する固定長バッファを有する通信装置における、パケット損失率が既定のパケット損失率上限以下となるリンク収容率上限値を算出するための従来技術として、下記の従来技術１と従来技術２がある。従来技術１、２において、リンク収容率上限を算出する装置における入力、及び出力は、下記のとおりとする。
【０００３】
入力：リンク帯域bw、バッファサイズbf、パケット損失率上限値L、対象フローのデータ（パケットのタイムスタンプとサイズのリスト）
出力：リンク収容率上限値a_max
＜従来技術１＞
対象とするフローのパケットサイズsは一定で、パケット到着がポアソン過程に従い、重畳する複数本のフローのパケット到着は互いに独立であるとしてモデル化を行う。このとき、重畳したフロー群のパケット到着もポアソン過程に従うことから、任意のリンク収容率aに対して、収容率a（サービス時間a/bw）、
【０００４】
【数１】
の待ち行列モデルM/D/1/Kを用いてパケット損失率lを求めることができる。
【０００５】
そこで、従来技術１では、sを対象フローの平均パケットサイズとして、l≦Lとなるようなaの最大値を二分法（0≦a≦1の範囲）によって求め、リンク収容率上限値a_maxとして出力する。
【０００６】
＜従来技術２＞
従来技術２は、Elwalidらのフローモデル化手法（非特許文献１）（以下、これを従来手法と呼ぶ）を応用した技術である。
【０００７】
従来技術２では、リーキーバケット・アルゴリズム（非特許文献２）を実行する単一の仮想的なリーキーバケット（サイズ無限、流出レートr）を用いて対象フローのパケット到着特性を定量化する。そして、パケットが常に一定量（サイズb）バースト到着するモデルを作り、重畳した全体トラヒックのバースト到着がポアソン過程に従うとみなす。このとき、
【０００８】
【数２】
使用率r*a/r0の待ち行列モデルM/D/1/Kを用いてフロー群のパケット損失率lを求めることができる。
【０００９】
つまり、任意のリンク収容率a、リーキーバケットの流出レートr（r≧対象フローの平均レートr0）に対してパケット損失率lを求めることができる。
【００１０】
そこで、従来技術２では、rをr0 と初期設定して、l≦Lとなるようなaの最大値を二分探索法（0≦a≦1の範囲）によって求めて結果をa_maxとする。そして、rを一定量ずつ増やして上記処理を繰り返してaを出力し、もしa>a_maxならばa_maxにaを代入してa_maxを更新する。そして、上記手順を繰り返して実行し、一定回数a_maxが更新されないときに繰り返し実行を終了して、a_maxを、目的のリンク収容率上限値a_maxとして出力する。
【００１１】
なお、上記従来技術２で用いられるリーキーバケット・アルゴリズムは、仮想的なバケットにビット量を補充し、一定レートでバケットのビット量を流出させるモデルのアルゴリズムである。バケットが空いている場合にはビット量が流出されず、満杯の場合にはビット量が補充されない。対象フローのパケット到着時にパケットサイズ相当のビット量を補充する状況で、パケットがバースト的に到着する場合、瞬間的に消費レートに対して補充量が過多となり、バケット内にトークンが滞留することになる。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】A. Elwalid, et al.,"A new approach for allocating buffers and bandwidth to heterogeneous, regulated traffic in an ATM node,"IEEE J. Select. Areas Commun., vol.13, pp.1115-1127, Aug. 1995.
【非特許文献２】ITU-T Recommendation I.371,"Traffic control and congestion control in B-ISDN,"Mar. 2004.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
対象フローの実際のトラヒックは、バースト性を伴っている部分と、定期的なパケット送出を行っている部分の合成からなると考えられる。しかし、従来技術１ではパケットのバースト到着を想定しておらず、パケットがバースト到着する場合に比べて、算出されるパケット損失率lを実態より低く推定してしまい、NW設計上のリンク収容率上限値を適切に出力することができない。
【００１４】
一方、従来技術２では、全てのトラヒックがバースト到着するという、実態より過度にバースト性の高い単一ソースのON/OFFモデルを作ることになるため、パケット損失率を実態より高く推定してしまいNW設計上のリンク収容率上限値を低く推定することから、NWの利用効率が上がらないという問題がある。
【００１５】
上記の問題を解決するために、対象フローの特性をより適切にモデル化して、より実態に近いパケット損失率を推定することにより、予め定められたパケット損失率以下を満たせるリンク収容率の適切な上限値を算出するための技術が先願である特願２０１０−１８８８７８に記載されている。特願２０１０−１８８８７８に記載された技術は、本発明の前提となる技術であるので、これを「前提技術」とよぶことにする。
【００１６】
しかし、後に詳述するように、前提技術では、収容率上限値算出に際して、3 個のパラメータを独立に動かし決定することとしており、探索に要する計算量が非常に大きいという課題がある。更に、前提技術では、各パラメータの探索範囲を特定していないため、本来探索対象である領域以外を探索する懸念、逆に探索対象の領域を探索対象としない懸念も存在する。
【００１７】
本発明は、従来技術１、２における課題を解決するとともに、前提技術における上記の課題を解決するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記の課題を解決するために、本発明は、パケット交換網における複数のフローを転送する固定長バッファを有する通信装置における、既定のパケット損失率上限以下を満たすリンク収容率上限値を算出するリンク収容率上限値算出装置であり、実トラヒックのキャプチャデータの入力を受け、当該キャプチャデータから対象情報を抽出する情報抽出手段と、前記情報抽出手段により抽出された情報に対して複数個のリーキーバケット（バケット1,2,...,(m+1)とする）を適用し、対象のフローを(m+1)個のサブフローに分割するサブフロー分割手段と、前記サブフロー分割手段で得られた各サブフロー毎に、それを重畳してサブフローi群 (i=1, 2,...,(m+1) )を構成するサブフロー群構成手段と、前記通信装置の帯域およびバッファリソースを各サブフロー群毎に固定的に配分するリソース配分手段と、を備えるリンク収容率上限値算出装置であって、前記リーキーバケット1,2,...,ｍのバッファ長をb1, b2, ...,bm、前記リーキーバケット(m+1) の最大トークン停留量をb(m+1)、バケット1, 2,...,(m+1)のトークンレートをr1, r2, .....,r(m+1)とした場合に、前記リソース配分手段により配分されたリソース配分状態において所与のリンク損失率閾値のもとでb(m+1) および収容率を(b1,...,bm,r1, ..., rm,r(m+1)) により決定する機能であって、かつその内r(m+1)を(b1,...,bm,r1,...,rm) の関数として算出し、収容率上限値を(b1,..., bm, r1,...,rm) 領域上の最適値探索問題に帰着して算出する機能を有する収容率上限値算出手段を備えることを特徴とするリンク収容率上限値算出装置として構成される。
【００１９】
前記収容率上限値算出手段は、所与のリンク損失率閾値のもとでパラメータ(b1,...,bm, r1,...,rm,r(m+1))のうちいずれか１個を他のパラメータの関数として表すことにより、処理を実行するように構成してもよい。
【００２０】
また、前記収容率上限値算出手段は、前記最適値探索における探索対象の関数の特徴を勘案した探索法を適用して、前記最適値探索の処理を実行するように構成することもできる。
【００２１】
また、本発明は、上記リンク収容率上限値算出装置が実行するリンク収容率上限値算出方法として構成することもできる。
【００２２】
更に、本発明は、コンピュータを、上記リンク収容率上限値算出装置の各手段として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【００２３】
本発明によれば、対象フローの特性をより適切にモデル化して、より実態に近いパケット損失率を推定することにより、予め定められたパケット損失率以下を満たせるリンク収容率の適切な上限値を算出することができる。
【００２４】
更に、本発明によれば、前提技術における課題が解決される。すなわち、探索に要する計算量が削減される。また、各パラメータの探索範囲を特定できるため、本来探索対象である領域以外を探索する懸念や、逆に探索対象の領域を探索対象としない懸念が解消される。
【図面の簡単な説明】
【００２５】
【図１】対象フローを仮想的にサブフロー１とサブフロー２に分割することを説明するための図である。
【図２】前提技術におけるリンク収容率上限値算出装置１０の機能構成例である。
【図３】サブフロー分割機能部１１における処理の概念を説明するための図である。
【図４】サブフロー分割機能部１１が実行する処理手順を示すフローチャートである。
【図５】パケット損失率算出機能部１２が実行する処理手順を示すフローチャートである。
【図６】リンク収容率上限値算出機能部１３が実行する処理手順を示すフローチャートである。
【図７】リンク収容率上限値最大値探索機能部１４が実行する処理手順を示すフローチャートである。
【図８】前提技術でのリンク収容率上限値の算出方式の処理概念を説明するための図である。
【図９】本発明の実施の形態に係るリンク収容率上限値算出装置の構成例である。
【図１０】本発明の実施の形態に係るリンク収容率上限値算出装置が実行する処理の概念を説明するための図である。
【図１１】収容率上限値算出部の処理手順例を示す図である。
【図１２】SA(Simulated Annealing)法を適用する場合において、高コスト解の採択率が座標に依存していることを示す図である。
【図１３】SA(Simulated Annealing)法を適用して、収容率上限値算出部が探索を行う場合の手順の一例を示す図である。
【発明を実施するための形態】
【００２６】
＜前提技術＞
以下、本発明の実施の形態を説明するにあたり、まず、その前提となった前提技術について説明する。
【００２７】
（概要）
図１を参照して、前提技術の概要を説明する。図１の上段に示すように、従来技術２では、リンク収容率上限値を算出する対象となる対象フローが常にバースト到着するものとしてモデル化していたところ、前提技術においては、図１の下段に示すように、リンク収容率上限値を算出する対象となる対象フローを仮想的にサブフロー１とサブフロー２に分割してモデル化を行うことにより対象フローの特性をより適切にモデル化する。これにより、より実態に近いパケット損失率を推定することができる。このように実態に近いパケット損失率を推定することにより、予め定められたパケット損失率以下を満たせるリンク収容率の適切な上限を算出することが可能である。
【００２８】
（装置構成）
図２に、前提技術におけるリンク収容率上限値算出装置１０の機能構成例を示す。図２に示すように、リンク収容率上限値算出装置１０は、対象フローを仮想的なサブフローに分割するサブフロー分割機能部１１と、サブフロー群ごとにリンク帯域及びバッファのリソースを固定的に割り当てて、待ち行列モデルを用いてパケット損失率を算出するパケット損失率算出機能部１２と、入力条件に対応したリンク収容率上限値を算出するリンク収容率上限値算出機能部１３と、対象フローに対応したリンク収容率上限値を算出するリンク収容率上限値最大値探索機能部１４と、各種データを格納するデータ記憶部１５とを備えている。
【００２９】
ここで、データ記憶部１５は、各機能部からアクセスされるメモリ等の記憶部であり、各機能部は、データ記憶部１５から処理に用いるデータ（例えば変数の値）を読み出し、処理後のデータをデータ記憶部１５に格納することにより、処理を進める。また、各機能部からの出力は、データ記憶部１５に格納され、他の機能部や他の装置への入力のために読み出される。ただし、リンク収容率上限値最大値探索機能部１４からの出力は、リンク収容率上限値算出装置１０の出力として、そのまま外部に出力することとしてもよい。
【００３０】
リンク収容率上限値算出装置１０には、リンク帯域bw、ルータのバッファサイズbf、パケット損失率上限L、及び、対象フローのデータ（本実施の形態では、パケットのタイムスタンプとサイズのリスト）が入力され、対象フローに対応したリンク収容率上限値a_maxが出力される。例えば、入力データのうちのリンク帯域bw、バッファサイズbf、パケット損失率上限Lは、NW設計者等により、入力手段を用いてリンク収容率上限値算出装置１０に入力され、対象フローのデータは、例えば、外部のデータベース装置に蓄積されたデータを通信ネットワークを介して受信することができる。
【００３１】
（各機能部の詳細）
以下、図２に示すリンク収容率上限値算出装置１０の各機能部の処理を詳細に説明する。後述するように、本実施の形態に係るリンク収容率上限値算出装置１０においては、リンク収容率上限値最大値探索機能部１４が、各機能部を動作させる制御を行って、結果として対象フローに対応したリンク収容率上限値a_maxを算出するが、以下では、各機能部毎に処理内容を説明する。
【００３２】
[サブフロー分割機能部１１]
サブフロー分割機能部１１は、リーキーバケット・アルゴリズムを実行する2 個の仮想的なリーキーバケットを用いてフローのパケット到着特性を定量化し、対象フローを仮想的なサブフローに分割するサブフロー分割処理を行う。
【００３３】
より具体的には、サブフロー分割機能部１１は、対象フローのデータ、バケット1の流出レートr1、バケット1のサイズb1、及びバケット2の流出レートr2を入力し、バケット2があふれないようにする上で必要なバケットサイズb2を出力する機能を有する。サブフロー分割機能部１１における処理の概念を図３を参照して説明する。
【００３４】
図３に示すとおり、リーキーバケット・アルゴリズムを実行する2 個の仮想的なリーキーバケットを用いてフローのパケット到着特性を定量化するにあたり、バケット1 のサイズはb1、流出レートはr1 とする。また、バケット2 のサイズは無限として、流出レートはr2 とする。
【００３５】
そして、対象フローのデータから対象フローを再現して到着パケットを観測し、パケット到着毎に観測パケットサイズ相当のビット量（トークン）をバケット1 に補充する。バケット1 が満杯の場合には、バケット1 に補充しきれない分のビット量をバケット2 へ補充する。このとき、観測中におけるバケット2 の最大ビット滞留量b2 を求める。そして、対象フローは以下の2 つのサブフローで構成されるとみなす。
【００３６】
サブフロー1：平均レートr1 で常にサイズb1 のバースト到着となるフロー
サブフロー2：平均レートr2 で常にサイズb2 のバースト到着となるフロー
なお、r1 = 0，b1 = 0 の場合，従来手法と同等となる。
【００３７】
図４は、対象フローのデータを与えて、r1、b1、r2を入力パラメータとし、b2を出力するための処理手順を示すフローチャートである。図４の処理は、図３に示す処理に対応するものである。また、図４の処理における一時変数等の意味は、図４内に示すとおりである。
【００３８】
図４を参照して、サブフロー分割機能部１１が実行するb2を出力するための処理手順を説明する。なお、以下の処理で、変数に数値を代入するとは、データ記憶部１５の所定領域に、数値を格納することに相当する。
【００３９】
まず、ステップ１０１において、パケット１個目のタイムスタンプをltimeに代入する。次に、ステップ１０２において、パケット１個目のパケットサイズをql1maxに代入し、ql1maxの値をql1に代入する。
【００４０】
次に、ql1>b1であるか否かの判定が行われ（ステップ１０３）、判定結果がYesであればステップ１０４に進み、Noであればステップ１０５に進む。ステップ１０４では、(ql1-b1)がql2に代入され、ql2の値がql2maxに代入される。
【００４１】
上記のステップ１０１〜１０４の処理はパケット１個目の処理に該当する。
【００４２】
ステップ１０５において、次のパケットデータの有無が判定され、Noであればステップ１１７に進み、Yesであれば次のパケットデータの処理を行うためにステップ１０６に進む。
【００４３】
ステップ１０６において、(ql1-(タイムスタンプ-ltime)*r1)がql1に代入され、(ql2-(タイムスタンプ-ltime)*r2)がql2に代入される。次に、ステップ１０７において、ql1<0であるか否かの判定が行われ、判定結果がYes（バケット１が空）であればステップ１０８に進み、Noであればステップ１０９に進む。
ステップ１０８において、ql1に０が代入される。ステップ１０９では、ql2<0であるか否かの判定が行われ、判定結果がYes（バケット２が空）であればステップ１１０に進み、Noであればステップ１１１に進む。ステップ１１０において、ql2に０が代入される。
【００４４】
上記のステップ１０５〜１１０の処理はバケットからのビット量流出処理に該当する。
【００４５】
ステップ１１１では、(ql1＋パケットサイズ)がql1に代入される。続いて、ステップ１１２において、ql1>b1であるか否かの判定が行われ、判定結果がYes（バケット１が満杯）であればステップ１１３に進み、Noであればステップ１１４に進む。
【００４６】
ステップ１１３において、(ql1-b1)がql2に代入され、ql2の値がql2maxに代入される。ステップ１１４において、ql2>ql2maxであるか否かの判定が行われ、判定結果がYesであればステップ１１５に進み、Noであればステップ１１６に進む。ステップ１１５において、ql2がql2maxに代入される。
【００４７】
上記のステップ１１１〜１１５の処理はバケットへのビット量補充処理に該当する。
【００４８】
ステップ１１６において、パケットのタイムスタンプがltimeに代入される。これは、直近パケットタイムスタンプltimeの更新処理である。
【００４９】
そして、ステップ１０５に判定において、次のパケットデータがなくなった場合に、ql2maxをb2（バケット２があふれないようにする上で必要なバケットサイズ）として出力する。
【００５０】
[パケット損失率算出機能部１２]
パケット損失率算出機能部１２は、パケット損失率算出処理を行う。パケット損失率算出処理におけるパケット損失率算出機能部１２への入力と、パケット損失率算出機能部１２からの出力は下記のとおりである。
【００５１】
入力：リンク帯域bw、ルータバッファサイズbf、対象フロー平均レートr0、バケット1の流出レートr1、バケット1のサイズb1、バケット2の流出レートr2、バケット2があふれないようにする上で必要なバケットサイズb2、リンク収容率a
出力：パケット損失率l
パケット損失率算出機能部１２は、サブフローを重畳したトラヒック（サブフロー群）ごとにリンク帯域及びバッファのリソースを固定的に割り当てて、それぞれのサブフロー群において仮想的な待ち行列モデルを従来手法に準じた方法で評価してサブフロー群毎のパケット損失率を算出して、リンク全体でのパケット損失率lを算出する機能を有する。
【００５２】
ここで、リーキーバケットでモデル化されたサブフロー1に対して帯域リソースr1，バッファリソースb1を用意するとき、b1はサブフロー1の最大キュー長に等しいことからパケット損失は生じない。
【００５３】
よって、上述した固定的に割り当てるリソースとして、サブフロー1 群に対してパケット損失が生じないようリンク収容率に応じたリンク帯域リソースr1 *(bw*a/r0)を割り当て、バッファリソースb1*(bw*a/r0)を割り当てる。また、残余リンク帯域リソース(bw-r1*(bw*a/r0))、残余バッファリソース(bf-b1*(bw*a/r0) )をサブフロー2 群に対して割り当てる。
【００５４】
そして、サブフロー2 群においてはサイズb2 のバーストパケットがランダムに到着するモデルを考えて、
【００５５】
【数３】
使用率(r2*(bw*a/r0))/(bw-(bw*a/r0)*r1)の待ち行列モデルM/D/1/K（非特許文献１）を用いてサブフロー2 群のパケット損失率l2 を求める。
【００５６】
上記の算出結果から、リンク全体のパケット損失率l=l2*r2/(r1+r2) を求める。なお、r1=0、k=0とする場合、サブフロー1群は無いものとしてサブフロー2のみを重畳することになるので、従来技術２と同等となる。
【００５７】
パケット損失率算出機能部１２が実行する処理手順は、図５に示すとおりである。すなわち、ステップ２０１において、
【００５８】
【数４】
使用率(r2*(bw*a/r0))/(bw-(bw*a/r0)*r1)の待ち行列モデルM/D/1/K（非特許文献１）を用いてサブフロー2群のパケット損失率l2を求め、ステップ２０２において、パケット損失率l=l2*r2/(r1+r2)を算出し、出力する。
[リンク収容率上限値算出機能部１３]
リンク収容率上限値算出機能部１３は、リンク収容率上限値算出処理を行う。リンク収容率上限値算出機能部１３への入力と、リンク収容率上限値算出機能部１３からの出力は、下記のとおりである。
【００５９】
入力：リンク帯域bw、ルータバッファサイズbf、パケット損失率上限L、対象フロー平均レートr0、バケット1の流出レートr1、バケット1のサイズb1、バケット2の流出レートr2、バケット2があふれないようにする上で必要なバケットサイズb2
出力：入力条件r1、r2、b1、b2に対応したリンク収容率上限値a_m
より具体的には、リンク収容率上限値算出機能部１３は、入力条件r1、r2、b1、b2の下で、損失率l≦損失率上限Lとなるようなリンク収容率aの最大値a_mを出力する。例えば、二分法（0≦a≦1の範囲）を用いて、リンク収容率aを変えながらパケット損失率算出機能部１２を用いてパケット損失率の算出処理を繰り返すことにより、リンク収容率aの最大値a_mを算出する。
【００６０】
リンク収容率上限値算出機能部１３が実行する処理手順を図６のフローチャートを参照して説明する。
【００６１】
リンク収容率aを設定し（ステップ３０１）、パケット損失率算出機能部１２を用いてステップ３０１で設定したリンク収容率aに対応するパケット損失率lを算出する（ステップ３０２）。
【００６２】
そして、リンク収容率上限値算出機能部１３は、算出した損失率lと、与えられた損失率上限Lを比較し、損失率lが損失率上限L以下ならば、a_mにaを代入する（ステップ３０３）。損失率lが損失率上限L以下でなければa_mは更新されない。リンク収容率上限値算出機能部１３は、ステップ３０１〜３０３の処理を十分な回数繰り返した後（ステップ３０４）、a_mを、入力条件r1、r2、b1、b2に対応したリンク収容率上限値として出力する（ステップ３０５）。上記の十分な回数の判定は、例えば、予め定めた回数の繰り返しを行ったかどうか、処理を繰り返す中でのa_mの変化が、予め定めた値よりも小さくなったかどうか、などにより行うことができる。
【００６３】
以下、ここでの処理をより具体的に説明する。
【００６４】
リンク収容率上限値算出機能部１３は、まず、リンク収容率をa=(0+1)/2=0.5と設定し（ステップ３０１）、パケット損失率算出機能部１２を用いてリンク収容率a=0.5のときのパケット損失率lを算出する（ステップ３０２）。
【００６５】
続いて、リンク収容率上限値算出機能部１３は、損失率lと損失率上限Lを比較し、損失率lが損失率上限L以下であれば、a_mにaを代入し（ステップ３０３）、a=(0.5+1)/2=0.75と設定して（ステップ３０４、ステップ３０１）、再度ステップ３０２の計算を行う。ステップ３０３において、損失率lが損失率上限Lを上回っていれば、a_mは更新されずa=(0+0.5)/2=0.25として再計算を行う。
【００６６】
[リンク収容率上限値最大値探索機能部１４]
リンク収容率上限値最大値探索機能部１４は、対象フローのデータ、リンク帯域bw、ルータバッファサイズbf、及び損失率上限Lを入力し、リンク収容率上限値の最大値探索処理を行って、対象フローに対応したリンク収容率上限値a_maxを出力する。
【００６７】
より具体的には、リンク収容率上限値最大値探索機能部１４は、r1、r2、b1を変化させてサブフロー分割機能部１１によりb２を求め、リンク収容率上限値算出機能部１３によりリンク収容率上限値a_mを求める。そして、各r1、r2、b1の組に対するa_mの中から最大値を探索し、a_maxとして出力する。
【００６８】
以下、リンク収容率上限値最大値探索機能部１４が実行する処理の手順を図７のフローチャートを参照して説明する。
【００６９】
まず、対象フローの平均レートr0を取得する（ステップ４０１）。この平均レートは、対象フローのデータから算出してもよいし、予めデータ記憶部１５に格納したものを読み出してもよい。続いて、r1、r2、b1をそれぞれ0、r0、0と初期設定する（ステップ４０２）。その後、十分な粒度で網羅的にr1、r2、b1を変更（ただし、r1+r2≧r0）させていきa_mを算出、出力し、もしa_m>a_maxならばa_maxにa_mを代入してa_maxを更新していき、a_mの最大値a_maxを出力する。
【００７０】
すなわち、ステップ４０３において、ステップ４０２での設定値をサブフロー分割機能部１２への入力として使用して、サブフロー分割機能部１２により、バケット２があふれないようにする上で必要なバケットサイズb2を算出する。
【００７１】
続いてステップ４０４において、リンク収容率上限値算出機能部１３により、入力条件r1、r2、b1、及びb2に対応したリンク収容率上限値a_mを算出する。そして、ステップ４０５で、a_m>a_maxであるか否かを判定し、判定結果がNoであればステップ４０７に進み、Yesであればステップ４０６に進む。
【００７２】
ステップ４０６では、a_mをa_maxに代入する。そして、r1、r2、b1を変更して、ステップ４０２からの処理を繰り返す。ステップ４０７では、r1、r2、b1のそれぞれを変更してもa_maxが一定回数以上更新されていないか否かを判定する。判定結果がNo（a_maxの更新がされている場合）であれば、r1、r2、b1を変更して、ステップ４０２からの処理を繰り返す。判定結果がYesであれば、そのときのa_maxをリンク収容率上限値として出力する（ステップ４０８）。
【００７３】
＜前提技術における課題について＞
上述したように、前提技術では、2 個のリーキーバケットを用いて、対象フローのパケット到着特性からモデルトラヒックを構成し、待ち行列モデルを用いてサブフロー(m + 1) 群（前提技術ではm=1）の損失率およびリンク全体の損失率を求める処理を、パラメータを動かしながら行い、リンク収容率上限値を探索する。
【００７４】
前提技術でのリンク収容率上限値の算出方式は、図８のように表すことができる。すなわち、前提技術ではまず、パラメータ(b1, r1, r2) を独立に動かし、対応するa(b1, r1, r2) の値を求める。続いてリンク全体の損失率l(b1, r1, r2, a(b1, r1, r2)) の値を算出する。この値が閾値L 以下であれば、当該a(b1, r1, r2) ,(b1, r1, r2)をそれぞれ最適解およびそれを実現するパラメータの候補として採択する。
【００７５】
そして、上記操作を各(b1, r1, r2)について実施し、a(b1, r1, r2)としてより大きい値が算出された場合には、上記の最適解候補を更新していく。
【００７６】
上記のように、前提技術では、収容率上限値算出に際して、3 個のパラメータを独立に動かし決定することとしているので、探索に要する計算量が非常に大きい。また各パラメータの探索範囲を特定していないため、本来探索対象である領域以外を探索する可能性や、逆に探索対象の領域を探索対象としない可能性がある。
【００７７】
＜前提技術における課題を解決するための構成＞
（装置構成）
上記の課題を解決するための本実施の形態に係るリンク収容率上限値算出装置１００の構成例を図９に示す。本実施の形態に係るリンク収容率上限値算出装置１００は、ネットワークのルータ収容設計等への使用に適した装置であり、図９に示すように、情報抽出部１０１、サブフロー分割部１０２、サブフロー群構成部１０３、リソース配分部１０４、収容率上限値算出部１０５、及びデータ記憶部１０６を備える。
【００７８】
情報抽出部１０１は、実トラヒック（平均レートr0とする）のキャプチャデータの入力を受け、当該キャプチャデータから必要情報を抽出する機能部である。
【００７９】
サブフロー分割部１０２は、情報抽出部１０１により抽出された情報に対して複数個のリーキーバケット（バケット1,2,...,(m+1)とする）を適用し、対象のフローを(m+1)個のサブフローに分割する機能部である。以下、(m+1)個のサブフローは、それぞれサブフロー1、サブフロー2,..., サブフロー(m+1)とする。また、バケット1,2,...,ｍのバッファ長をb1, b2, ...,bm、バケット(m+1) の最大トークン停留量をb(m+1)（m+1は添字）、バケット1, 2,...,(m+1)のトークンレートをr1, r2, .....,r(m+1)とする。
【００８０】
サブフロー群構成部１０３は、サブフロー分割部１０２で得られた各サブフロー毎に、それを重畳して仮想的トラヒックモデルを構成する機能部である。以下、サブフローi を重畳して構成したモデルをサブフローi群 (i=1, 2,...,(m+1) )と記する。
【００８１】
リソース配分部１０４は、ルータの帯域およびバッファリソースを各サブフロー群毎に固定的に配分する機能部である。
【００８２】
また、収容率上限値算出部１０５は、前記リソース配分状態において所与のリンク損失率閾値のもとでb(m+1) および収容率を(b1,...,bm,r1,...,rm,r(m+1)) により決定する機能であって、かつその内r(m+1)を(b1,...,bm,r1,...,rm) の関数として算出し、収容率上限値を(b1,...,bm,r1,...,rm) 領域上の最適値探索問題に帰着して算出する機能を有する機能部である。
【００８３】
収容率上限値算出部１０５は、所与のリンク損失率閾値のもとでパラメータ(b1,...,bm,r1,...,rm,r(m+1))のうちいずれか１個を他のパラメータの関数として表すことにより、処理を実行することが可能である。更に、収容率上限値算出部１０５は、探索対象の関数の特徴を勘案した探索法（例：SA(Simulated Annealing)における重み付け等)を適用して、前記最適値探索の処理を実行することができる。
【００８４】
ここで、データ記憶部１０６は、各機能部からアクセスされるメモリ等の記憶部であり、各機能部は、データ記憶部１０６から処理に用いるデータ（例えば変数の値）を読み出し、処理後のデータをデータ記憶部１０６に格納することにより、処理を進める。また、各機能部からの出力は、データ記憶部１０６に格納され、他の機能部や他の装置への入力のために読み出される。
【００８５】
リンク収容率上限値算出装置１００は、コンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、リンク収容率上限値算出装置１００の各部で行われる処理や機能は、リンク収容率上限値算出装置１００を構成するコンピュータに内蔵されるＣＰＵやメモリなどのハードウェア資源を用いて、各部で実施される処理に対応するプログラムを実行することによって実現することが可能である。また、当該プログラムは、当該プログラムを記録したＦＤ、ＣＤ−ＲＯＭ、ＤＶＤなどの記録媒体や、インターネットなどのネットワークを介して市場に流通させることができる。
【００８６】
また、リンク収容率上限値算出装置１００は、単独の装置として実現してもよいし、ネットワーク運用監視装置やネットワーク設計支援装置の機能の一部、あるいは、ルータ等の通信装置の機能の一部として構成することもできる。
（リンク収容率上限値算出装置１００における処理概要）
次に、リンク収容率上限値算出装置１００が実行する処理の概念を図１０に示す。図１０は、説明を分かりやすくするために、m=1の場合を示している。また、前提技術との相違についても説明する。
【００８７】
図１０に示すように、損失率が一定においては、aおよび r2 はそれぞれb1,r1の関数として表すことができる。すなわち、損失率が閾値を与える領域においては、(b1,...,bm, r1,...,rm) のうちの(m-1)個を用いて、他の１個およびa を所定の領域上で表すことができる。そして、前記所定の領域において最大となるa を探索し、それを、求める最適解とする。以下、m =1の 場合において前提技術との比較を行う。
【００８８】
前提技術ではパラメータ(b1,r1,r2) を独立に動かしてa(b1,r1,r2) の上限値を求めたため、例えば各パラメータの探索範囲をそれぞれ
【００８９】
【数５】
とすると探索領域のボリュームは
【００９０】
【数６】
で与えられたのに対し、本発明に係る方式では例えば(b1,r1) のパラメータ空間上の領域（当該領域は明示的に算出可能である）上で探索を行えばよく探索領域のボリュームは
【００９１】
【数７】
で与えられる（図８、１０に示したとおり）。
【００９２】
また、実施の一形態として後述するように、当該パラメータ空間をさらに有界領域に分割し、個々の有界領域上での最適解を比較して全体としての最適解を求める構成とすることが可能である。
【００９３】
（リンク収容率上限値算出装置１００における処理の詳細：ｍ＝１の場合の例）
以下、まず、リンク収容率上限値算出装置１００における処理内容をm=1の場合を例にして説明する。説明にあたって使用する記号の凡例を以下に示す。
【００９４】
【数８】
まず、情報抽出部１０１が、実トラヒック（平均レートr0とする）のキャプチャデータの入力を受け、当該キャプチャデータから対象フローのデータ（パケットのタイムスタンプとサイズのリスト）を抽出し、サブフロー分割部１０２に与える。サブフロー分割部１０２は、情報抽出部１０１により抽出された情報に対して２個のリーキーバケットを適用し、対象のフローを２個のサブフローに分割する。また、サブフロー群構成部１０３は、サブフロー分割部１０２で得られた各サブフロー毎に、それを重畳してサブフロー１群、２群を構成する。ここまでの処理は前提技術と同様である。
【００９５】
リソース配分部１０４は、各サブフロー群に対して、以下に示すようにルータの帯域リソースを固定配分する。本実施の形態では、一例として、サブフロー１群での損失率が０となるように配分を行う場合を示している。
【００９６】
【数９】
この場合、サブフロー２群のパケット損失率に「Β＾（サブフロー２に流入するビット数）／Β（データ中の全パケットのビット数）」を乗じることにより、リンク全体の損失率を算出することができる。
【００９７】
［問題設定］
次に、収容率上限値算出部１０５が収容率上限値を算出するにあたっての問題設定について説明する。
【００９８】
サブフロー２群のパケット損失率は、サブフロー２群に待ち行列モデルM/D/1/Kを適用し算出する。上記リソース配分より、
【００９９】
【数１０】
のM/D/1/K待ち行列モデルを適用すると、収容率上限値を決定することは、以下のような問題として記述できる。なお、以下での［x］は実数xの整数部分を示す。
【０１００】
問題：「
【０１０１】
【数１１】
のもとでリンク収容率（の定数倍）a^(=a/r0)の上限値を与えるパラメータの組を求めよ。ここで
【０１０２】
【数１２】
である。」
［処理手順］
本実施の形態に係るリンク収容率上限値算出装置１００の収容率上限値算出部１０５は、上記の問題を解くための処理を、図１１に示すパラメータ最適化手順に従って実行する。この手順では、探索領域を明確にするために、リーキーバケット２に流入するビット数（Β＾）をパラメータとしてとり、(b1,r1)領域を有界領域に分割する。なお、図１１に示すパラメータ最適化手順は一例である。以下、収容率上限値算出部１０５が実行する処理手順を図１１に沿って説明する。
【０１０３】
ステップ１）リーキーバケット２に流入するビット数Β＾を所与とし、
【０１０４】
【数１３】
をとる。
【０１０５】
ステップ２）
【０１０６】
【数１４】
よりサブフロー２群の待ち行列モデルにおける損失率ρ(k, u)を求める。
【０１０７】
ステップ３）上記損失率を与える(k, u)の組
【０１０８】
【数１５】
を求める。
【０１０９】
ステップ４）上記の各(ki, ui)について
【０１１０】
【数１６】
を求める。これを各(b1,r1)について行い、最大のa^(=a/r0)を与えるものを探索する。
【０１１１】
ステップ５）上記のステップ１~４を、任意の増分幅で
【０１１２】
【数１７】
について実施し、最大のa^×r0を求め、これをリンク収容率最大値として出力する。
【０１１３】
（リンク収容率上限値算出装置１００における処理の詳細：一般のｍについて）
次に、mが一般の場合におけるリンク収容率上限値算出装置１００の処理内容を説明する。新規に必要な記号の凡例を以下に示す。
【０１１４】
【数１８】
まず、情報抽出部１０１が、実トラヒック（平均レートr0とする）のキャプチャデータの入力を受け、当該キャプチャデータから対象フローのデータ（パケットのタイムスタンプとサイズのリスト）を抽出し、サブフロー分割部１０２に与える。サブフロー分割部１０３は、情報抽出部１０２により抽出された情報に対して(m+1)個のリーキーバケットを適用し、対象のフローを(m+1)個のサブフローに分割する。また、サブフロー群構成部１０３は、サブフロー分割部１０２で得られた各サブフロー毎に、それを重畳してサブフローi群 (i=1, 2,...,(m+1) )を構成する。前述したように、(m+1)個のサブフローは、それぞれサブフロー1、サブフロー2,..., サブフロー(m+1)であり、バケット1,2,...,ｍのバッファ長はb1, b2, ...,bm、バケット(m+1) の最大トークン停留量はb(m+1)、バケット1, 2,...,(m+1)のトークンレートはr1, r2, r(m+1)である。
【０１１５】
次に、リソース配分部１０４は、各サブフロー群に対して、以下に示すようにルータの帯域リソースを固定配分する。本実施の形態では、一例として、サブフロー１群での損失率が０となるように配分を行う場合を示している。
【０１１６】
【数１９】
ここでは、サブフロー(m+1)群におけるM/D/1/Kモデルは以下のとおりである。
【０１１７】
【数２０】
［収容率上限値算出部１０５の処理手順］
収容率上限値算出部１０５は、図１１に示すパラメータ最適化手順と同様の手順で収容率上限値を求める処理を実行している。ただし、本例ではmは一般であり、１に限られない。以下、収容率上限値算出部１０５が実行する処理手順（ステップ１１〜１５）を説明する。
【０１１８】
ステップ１１）リーキーバケット(m+1)に流入するビット数Β＾を所与とし、
【０１１９】
【数２１】
をとる。
【０１２０】
ステップ１２）
【０１２１】
【数２２】
よりサブフロー(m+1)群の待ち行列モデルにおける損失率ρ(k, u)を求める。
【０１２２】
ステップ１３）上記損失率を与える(k, u)の組
【０１２３】
【数２３】
を求める。
【０１２４】
ステップ１４）上記の各(ki, ui)について
【０１２５】
【数２４】
を求める。これを
【０１２６】
【数２５】
について行い、最大のa^(=a/r0)を与えるものを探索する。
【０１２７】
ステップ１５）上記のステップ１１~１４を、任意の増分幅で
【０１２８】
【数２６】
について実施し、最大のa^×r0を求め、これをリンク収容率最大値として出力する。
【０１２９】
[探索処理について]
上記のステップ１４（m=1のときのステップ４も同様）において、収容率上限値算出部１０５が実行する探索処理としては種々の手法を用いることが可能である。本実施の形態では、一例として、SA(Simulated Annealing)法を適用する場合を説明する。
【０１３０】
本例においては、
【０１３１】
【数２７】
但し、b(m+1)はその各引数の値が大きい場合の方が、小さい値をとる可能性が高いため、高コスト解採択率は、これら引数の値に応じて重み付けをすることとする。図１２は、この性質をm=1の場合で示した図である。図１２には、高コスト解の採択率が座標に依存していることが示されている。
【０１３２】
【数２８】
パラメータの値に依らず既存のSA法を適用する。
【０１３３】
図１３は、SA(Simulated Annealing)法を適用して、収容率上限値算出部１０５が探索を行う場合の手順の一例を示す図である。本例は、
【０１３４】
【数２９】
探索を行う場合（上記の一番目）における手順を示すものである。
【０１３５】
ステップ２１）
【０１３６】
【数３０】
ステップ２２）解の近傍N(sol)から
【０１３７】
【数３１】
ステップ２３）
【０１３８】
【数３２】
δ>0であるか否かを判定し、δ>0であればステップ２４に進み、そうでなければステップ２５に進む。
【０１３９】
ステップ２４）
【０１４０】
【数３３】
更新後、ステップ２６に進む。
【０１４１】
ステップ２５）
【０１４２】
【数３４】
ステップ２５での判定結果がYesであれば、
【０１４３】
【数３５】
そして、ステップ２４に進む。また、ステップ２５での判定結果がNoである場合、solを更新せずにステップ２６に進む。
【０１４４】
ステップ２６）温度をα×θで更新し、ステップ２２に戻る。収容率上限値算出部１０５は、上記のステップ２２〜２６を所定の回数反復することにより探索を行う。
【０１４５】
以上、説明したように、本実施の形態に係る技術によれば、対象フローの特性をより適切にモデル化して、より実態に近いパケット損失率を推定することにより、予め定められたパケット損失率以下を満たせるリンク収容率の適切な上限値を算出することができるという前提技術と同様の効果が得られるとともに、前提技術における課題が解決される。すなわち、探索に要する計算量が削減される。また、各パラメータの探索範囲を特定できるため、本来探索対象である領域以外を探索する懸念や、逆に探索対象の領域を探索対象としない懸念が解消される。
【０１４６】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１４７】
１０ リンク収容率上限値算出装置
１１ サブフロー分割機能部
１２ パケット損失率算出機能部
１３ リンク収容率上限値算出機能部
１４ リンク収容率上限値最大値探索機能部
１５ データ記憶部
１００ リンク収容率上限値算出装置
１０１ 情報抽出部
１０２ サブフロー分割部
１０３ サブフロー群構成部
１０４ リソース配分部
１０５ 収容率上限値算出部
１０６ データ記憶部
【特許請求の範囲】
【請求項１】
パケット交換網における複数のフローを転送する固定長バッファを有する通信装置における、既定のパケット損失率上限以下を満たすリンク収容率上限値を算出するリンク収容率上限値算出装置であり、
実トラヒックのキャプチャデータの入力を受け、当該キャプチャデータから対象情報を抽出する情報抽出手段と、
前記情報抽出手段により抽出された情報に対して複数個のリーキーバケット（バケット1,2,...,(m+1)とする）を適用し、対象のフローを(m+1)個のサブフローに分割するサブフロー分割手段と、
前記サブフロー分割手段で得られた各サブフロー毎に、それを重畳してサブフローi群 (i=1, 2,...,(m+1) )を構成するサブフロー群構成手段と、
前記通信装置の帯域およびバッファリソースを各サブフロー群毎に固定的に配分するリソース配分手段と、を備えるリンク収容率上限値算出装置であって、
前記リーキーバケット1,2,...,ｍのバッファ長をb1, b2, ...,bm、前記リーキーバケット(m+1) の最大トークン停留量をb(m+1)、バケット1, 2,...,(m+1)のトークンレートをr1, r2, .....,r(m+1)とした場合に、前記リソース配分手段により配分されたリソース配分状態において所与のリンク損失率閾値のもとでb(m+1) および収容率を(b1,...,bm,r1, ..., rm,r(m+1)) により決定する機能であって、かつその内r(m+1)を(b1,...,bm,r1,...,rm) の関数として算出し、収容率上限値を(b1,...,bm,r1,...,rm) 領域上の最適値探索問題に帰着して算出する機能を有する収容率上限値算出手段
を備えることを特徴とするリンク収容率上限値算出装置。
【請求項２】
前記収容率上限値算出手段は、所与のリンク損失率閾値のもとでパラメータ(b1,...,bm, r1,...,rm,r(m+1))のうちいずれか１個を他のパラメータの関数として表すことにより、処理を実行する
ことを特徴とする請求項１に記載のリンク収容率上限値算出装置。
【請求項３】
前記収容率上限値算出手段は、前記最適値探索における探索対象の関数の特徴を勘案した探索法を適用して、前記最適値探索の処理を実行する
ことを特徴とする請求項１又は２に記載のリンク収容率上限値算出装置。
【請求項４】
パケット交換網における複数のフローを転送する固定長バッファを有する通信装置における、既定のパケット損失率上限以下を満たすリンク収容率上限値を算出するリンク収容率上限値算出装置が実行するリンク収容率上限値算出方法であって、
実トラヒックのキャプチャデータの入力を受け、当該キャプチャデータから対象情報を抽出する情報抽出ステップと、
前記情報抽出ステップにより抽出された情報に対して複数個のリーキーバケット（バケット1,2,...,(m+1)とする）を適用し、対象のフローを(m+1)個のサブフローに分割するサブフロー分割ステップと、
前記サブフロー分割ステップで得られた各サブフロー毎に、それを重畳してサブフローi群 (i=1, 2,...,(m+1) )を構成するサブフロー群構成ステップと、
前記通信装置の帯域およびバッファリソースを各サブフロー群毎に固定的に配分するリソース配分ステップと、を含むリンク収容率上限値算出方法であって、
前記リーキーバケット1,2,...,ｍのバッファ長をb1, b2, ...,bm、前記リーキーバケット(m+1) の最大トークン停留量をb(m+1)、バケット1, 2,...,(m+1)のトークンレートをr1, r2, .....,r(m+1)とした場合に、前記リソース配分ステップにより配分されたリソース配分状態において所与のリンク損失率閾値のもとでb(m+1) および収容率を(b1,...,bm,r1, ..., rm,r(m+1)) により決定するステップを有し、かつその内r(m+1)を(b1,...,bm,r1,...,rm) の関数として算出し、収容率上限値を(b1,...,bm,r1,...,rm) 領域上の最適値探索問題に帰着して算出するステップを有する収容率上限値算出ステップ
を備えることを特徴とするリンク収容率上限値算出方法。
【請求項５】
前記収容率上限値算出ステップは、所与のリンク損失率閾値のもとでパラメータ(b1,...,bm, r1,...,rm,r(m+1))のうちいずれか１個を他のパラメータの関数として表すことにより、処理を実行するステップを含む
ことを特徴とする請求項４に記載のリンク収容率上限値算出方法。
【請求項６】
前記収容率上限値算出ステップは、前記最適値探索における探索対象の関数の特徴を勘案した探索法を適用して、前記最適値探索の処理を実行するステップを含む
ことを特徴とする請求項４又は５に記載のリンク収容率上限値算出方法。
【請求項７】
コンピュータを、請求項１ないし３のうちいずれか１項に記載のリンク収容率上限値算出装置の各手段として機能させるためのプログラム。
【請求項１】
パケット交換網における複数のフローを転送する固定長バッファを有する通信装置における、既定のパケット損失率上限以下を満たすリンク収容率上限値を算出するリンク収容率上限値算出装置であり、
実トラヒックのキャプチャデータの入力を受け、当該キャプチャデータから対象情報を抽出する情報抽出手段と、
前記情報抽出手段により抽出された情報に対して複数個のリーキーバケット（バケット1,2,...,(m+1)とする）を適用し、対象のフローを(m+1)個のサブフローに分割するサブフロー分割手段と、
前記サブフロー分割手段で得られた各サブフロー毎に、それを重畳してサブフローi群 (i=1, 2,...,(m+1) )を構成するサブフロー群構成手段と、
前記通信装置の帯域およびバッファリソースを各サブフロー群毎に固定的に配分するリソース配分手段と、を備えるリンク収容率上限値算出装置であって、
前記リーキーバケット1,2,...,ｍのバッファ長をb1, b2, ...,bm、前記リーキーバケット(m+1) の最大トークン停留量をb(m+1)、バケット1, 2,...,(m+1)のトークンレートをr1, r2, .....,r(m+1)とした場合に、前記リソース配分手段により配分されたリソース配分状態において所与のリンク損失率閾値のもとでb(m+1) および収容率を(b1,...,bm,r1, ..., rm,r(m+1)) により決定する機能であって、かつその内r(m+1)を(b1,...,bm,r1,...,rm) の関数として算出し、収容率上限値を(b1,...,bm,r1,...,rm) 領域上の最適値探索問題に帰着して算出する機能を有する収容率上限値算出手段
を備えることを特徴とするリンク収容率上限値算出装置。
【請求項２】
前記収容率上限値算出手段は、所与のリンク損失率閾値のもとでパラメータ(b1,...,bm, r1,...,rm,r(m+1))のうちいずれか１個を他のパラメータの関数として表すことにより、処理を実行する
ことを特徴とする請求項１に記載のリンク収容率上限値算出装置。
【請求項３】
前記収容率上限値算出手段は、前記最適値探索における探索対象の関数の特徴を勘案した探索法を適用して、前記最適値探索の処理を実行する
ことを特徴とする請求項１又は２に記載のリンク収容率上限値算出装置。
【請求項４】
パケット交換網における複数のフローを転送する固定長バッファを有する通信装置における、既定のパケット損失率上限以下を満たすリンク収容率上限値を算出するリンク収容率上限値算出装置が実行するリンク収容率上限値算出方法であって、
実トラヒックのキャプチャデータの入力を受け、当該キャプチャデータから対象情報を抽出する情報抽出ステップと、
前記情報抽出ステップにより抽出された情報に対して複数個のリーキーバケット（バケット1,2,...,(m+1)とする）を適用し、対象のフローを(m+1)個のサブフローに分割するサブフロー分割ステップと、
前記サブフロー分割ステップで得られた各サブフロー毎に、それを重畳してサブフローi群 (i=1, 2,...,(m+1) )を構成するサブフロー群構成ステップと、
前記通信装置の帯域およびバッファリソースを各サブフロー群毎に固定的に配分するリソース配分ステップと、を含むリンク収容率上限値算出方法であって、
前記リーキーバケット1,2,...,ｍのバッファ長をb1, b2, ...,bm、前記リーキーバケット(m+1) の最大トークン停留量をb(m+1)、バケット1, 2,...,(m+1)のトークンレートをr1, r2, .....,r(m+1)とした場合に、前記リソース配分ステップにより配分されたリソース配分状態において所与のリンク損失率閾値のもとでb(m+1) および収容率を(b1,...,bm,r1, ..., rm,r(m+1)) により決定するステップを有し、かつその内r(m+1)を(b1,...,bm,r1,...,rm) の関数として算出し、収容率上限値を(b1,...,bm,r1,...,rm) 領域上の最適値探索問題に帰着して算出するステップを有する収容率上限値算出ステップ
を備えることを特徴とするリンク収容率上限値算出方法。
【請求項５】
前記収容率上限値算出ステップは、所与のリンク損失率閾値のもとでパラメータ(b1,...,bm, r1,...,rm,r(m+1))のうちいずれか１個を他のパラメータの関数として表すことにより、処理を実行するステップを含む
ことを特徴とする請求項４に記載のリンク収容率上限値算出方法。
【請求項６】
前記収容率上限値算出ステップは、前記最適値探索における探索対象の関数の特徴を勘案した探索法を適用して、前記最適値探索の処理を実行するステップを含む
ことを特徴とする請求項４又は５に記載のリンク収容率上限値算出方法。
【請求項７】
コンピュータを、請求項１ないし３のうちいずれか１項に記載のリンク収容率上限値算出装置の各手段として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−１０５０８６（Ｐ２０１２−１０５０８６Ａ）
【公開日】平成２４年５月３１日（２０１２．５．３１）
【国際特許分類】
【出願番号】特願２０１０−２５２１４１（Ｐ２０１０−２５２１４１）
【出願日】平成２２年１１月１０日（２０１０．１１．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年５月３１日（２０１２．５．３１）
【国際特許分類】
【出願日】平成２２年１１月１０日（２０１０．１１．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]