(57)【特許請求の範囲】
【請求項１】
フローキー{srcIP，dstIP，srcPort，dstPort，Protocol}の５つ組みを同じくするパケット群をフローと定義し、フロー毎の状態を管理するネットワーク装置において必要となるフローエントリ数を見積もるための同時フロー数変動量推定方法であって、
フロー管理手段が、ネットワーク内を通過する、フローキーi={srcIP，dstIP，srcPort，dstPort，Protocol}，フローiの開始時刻Tfirst_iと終了時刻Tlast_i、及び、それらから計算されるフロー持続時間d_i=Tlast_i-Tfirst_iを含むフローiの情報を、予め定めた測定期間Tの間、N本収集し、記憶手段に格納するフロー収集ステップと、
フロー統計情報収集手段が、前記フロー収集ステップで収集されたN本のd_i>0となるフローについて、フロー持続時間の平均をavg_d=Σd_i/Nにより求め、前記記憶手段に格納されている前記フローの中から、ランダムに２つのフローiとjを選択し、Hmin=min(d_i,d_j)とする処理を、これを予め定めた回数M回実施し、m番目の試行におけるHminの値をHmin(k)とし、その平均を、
avg_Hmin=ΣHmin(m)/M
により計算する平均算出ステップと、
前記フロー統計情報収集手段が、前記記憶手段に格納されている前記フロー情報を用いて、srcIP#x毎の発生フロー数に関する統計情報を求め、単位時間当たりの到着srcIP数Aを、A=N/T/Eにより求める統計情報算出ステップと、
同時フロー数分散推定手段が、
同時フロー数の分散VarLを、
VarL=A×(V+E2-E)×avg_Hmin+A×E×avg_d
により、算出する同時フロー数分散推定ステップと、
を行い、
前記統計情報算出ステップにおいて、
前記測定期間Tを、該Tより小さい測定周期τで分割し（区間がT/τ=L個生成される）、k番目の測定区間における、srcIP#xからの発生フロー数をF(x,k)とし、該発生フロー数F(x,k)を用いて、あるsrcIPから生成されるフロー数の平均Eと分散Vを計算する
ことを特徴とする同時フロー数変動量推定方法。
【請求項２】
前記統計情報算出ステップにおいて、
前記フロー数の平均Eと分散Ｖを計算する際に、
出現srcIPの集合をw_sとしたとき、x∈w_sかつk∈[1,L]に対し収集された発生フロー数F(x,k)のうち、F(k,x)>0を満たすものだけを抽出し、
抽出されたF(k,x)の数をLWとし、前記平均Eを、
E=ΣF(k,x)/LW，V=ΣF(k,x)2/LW-E2
により計算することを特徴とする請求項１記載の同時フロー数変動量推定方法。
【請求項３】
前記統計情報算出ステップにおいて、
将来の単位時間当たりの到着srcIP数Aが、予め定めたA*になると仮定したときの、同時フロー数の分散を
VarL=A*×(V+E2-E)×avg_Hmin+A*×E×avg_d
により求める
ことを特徴とする請求項１記載の同時フロー数変動量推定方法。
【請求項４】
前記同時フロー数分散推定ステップにおいて、
前記同時フロー数の分散を推定する際に、推定に用いるフロー情報のうち、宛先ポート番号が特定の番号（スキャンなどの異常トラヒックに多く見られるポート番号）であるフローを除外してから、分散の推定を行う
ことを特徴とする請求項１または３記載の同時フロー数変動量推定方法。
【請求項５】
前記同時フロー数分散推定ステップにおいて、
前記フロー情報の収集対象となるユーザ数をZとして、仮に収容ユーザ数をZ'としたときの同時フロー数の分散を、
VarL=A/Z×Z'×(V+E2-E)×avg_Hmin+ A/Z×Z'×E×avg_d
により求める
ことを特徴とする請求項１記載の同時フロー数変動量推定方法。
【請求項６】
前記フロー情報収集ステップにおいて、
前記測定期間Tよりも短い測定期間T'においてフロー情報を収集し、
前記平均算出ステップにおいて、
前記平均avg_dとavg_Hminを用いてα=avg_Hmin/avg_dを計算し、
前記統計情報算出ステップにおいて、
前記フロー情報を用いて、srcIP#x毎の発生フロー数に関する統計情報を求め、
前記測定期間T'における同時フロー数の平均avgL'を収集フロー情報より算出し、
前記同時フロー数分散推定ステップにおいて、
前記同時フロー数の分散Var_Lを
VarL=A×(V+E2-E)×avgL'/(A×E)×α+avgL'
により推定し、
前記統計情報算出ステップにおいて、
前記測定期間T'を、T'より小さい測定周期τで分割し（区間がT'/τ=L'個生成される）、k番目の測定区間における、srcIP#xからの発生フロー数をF(x,k)し、該発生フロー数F(x,k)を用いて、あるsrcIPから生成されるフロー数の平均Eと分散Vを計算し、
単位時間当たりの到着srcIP数Aを、A＝N/T'/Eにより計算する
請求項１記載の同時フロー数変動量推定方法。
【請求項７】
フローキー{srcIP，dstIP，srcPort，dstPort，Protocol}の５つ組みを同じくするパケット群をフローと定義し、フロー毎の状態を管理するネットワーク装置において必要となるフローエントリ数を見積もるための同時フロー数変動量推定装置であって、
ネットワーク内を通過する、フローキーi={srcIP，dstIP，srcPort，dstPort，Protocol}，フローiの開始時刻Tfirst_iと終了時刻Tlast_i、及び、それらから計算されるフロー持続時間d_i=Tlast_i-Tfirst_iを含むフローiの情報を、予め定めた測定期間Tの間、N本収集し、記憶手段に格納するフロー管理手段と、
前記フロー管理手段で収集されたN本のd_i>0となるフローについて、フロー持続時間の平均をavg_d=Σd_i/Nにより求め、前記記憶手段に格納されている前記フローの中から、ランダムに２つのフローiとjを選択し、Hmin=min(d_i,d_j)とする処理を、これを予め定めた回数M回実施し、m番目の試行におけるHminの値をHmin(k)とし、その平均を、
avg_Hmin=ΣHmin(m)/M
により計算する平均算出手段と、
前記記憶手段に格納されている前記フロー情報を用いて、srcIP#x毎の発生フロー数に関する統計情報を求め、単位時間当たりの到着srcIP数Aを、A=N/T/Eにより求めるフロー統計情報収集手段と、
同時フロー数の分散VarLを、
VarL=A×(V+E2-E)×avg_Hmin+A×E×avg_d
により、算出する同時フロー数分散推定手段と、
を有し、
前記統計情報算出手段は、
前記測定期間Tを、該Tより小さい測定周期τで分割し（区間がT/τ=L個生成される）、k番目の測定区間における、srcIP#xからの発生フロー数をF(x,k)とし、該発生フロー数F(x,k)を用いて、あるsrcIPから生成されるフロー数の平均Eと分散Vを計算する手段を含むことを特徴とする同時フロー数変動量推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同時フロー数変動量推定方法及び装置に係り、特に、フロー毎に状態を管理するネットワークシステム、例えばフロールータ（http://anagran.com/を参照）や、IPv4アドレス枯渇問題への対策として、ISP（Internet Service Provider）がNAT(Network Address Translation)を用いて通信ネットワークを構成する際に設置するlarge scale NAT(LSN)(T. Nishitani et al., "Common functions of large scale NAT(LSN)," draftnishitani-cgn-02, IETF, May 2009.参照)などにおいて必要なフローテーブルのサイズを見積もる際に必要となる同時フロー数の変動量を推定するための同時フロー数変動量推定方法及び装置に関するものである。
【背景技術】
【０００２】
IPネットワークが広く利用されてくるに伴ってIPネットワークの利用形態やアプリケーションも多様化し、それに伴ってネットワークへ加わるトラヒックも多様化している。一方で、トラヒックは年々増加しており、トラヒックがネットワークへどのようなインパクトを与えるかを見積もることが非常に重要となってきている。例えば、動画共有トラヒックや、ビデオやTVなどのリッチコンテンツ配信によるトラヒックなどの増加が指摘されている（例えば、非特許文献1参照）。
【０００３】
一方、上記のように、１通信当りのトラヒック量が多いことに加えて、例えば、近年のアプリケーションでは、一つのホストが多数のフローを同時に発生することが指摘されている（例えば、非特許文献2参照）。
【０００４】
また、SYN floodingやネットワークスキャンなどの異常トラヒックによって大量のフローが生成されることもある。このようなフロー数の多いトラヒックがネットワークに加わると、large scale NAT(LSN)へのインパクトが大きくなると予想される。ここで、LSNとは、IPv4アドレス枯渇問題への対策として考えられている方式である。図１(a)に示すように、ISPは、LSNを内部ネットワークと外部ネットワークの境界に設置し、内部ネットワークでは独自のアドレスを用い、それを内部ホストに割り当て、インターネットへアクセスする際にはLSNにおいて内部ホストの独自アドレスをグローバルIPv4アドレスへ変換することで、インターネット上のホストとの通信を可能にしている。
【０００５】
例えば、NAT444, dual stack (DS)-lite呼ばれる方式が提案されている（例えば、非特許文献３参照）。図１(a)のNAT444では、宅内のエンドホストは、宅内で用いるプライベートIPv4アドレスXを用いて、customer premise equipment (CPE)-NATへパケットを送信する。CPE-NATで、アドレスXは、ISP内で用いる独自アドレスYに変換される。この独自アドレスは例えば「ISPシェアドアドレス」（例えば、非特許文献４参照）と呼ばれるものを利用する。これは、Internet assigned numbers authority(IANA)によって未割当のIPv4アドレスを、ISP間でシェア可能なアドレスとして規定するという案である。独自アドレスYを付与されたパケットはLSNまで転送され、そこで、グローバルIPv4アドレスに変換後、インターネットへと転送される。
【０００６】
図１(b)のDS-liteでは、ISPはIPv6を内部で利用する。図１(a)と同様に、エンドホストからのパケットはプライベートアドレスXでDS-lite home gateway (HGW)まで転送され、そのパケットはLSNまでIPv4 over an IPv6トンネルを用いてLSNまで転送される。そして、LSNで、そのパケットのアドレスを、グローバルIPv4アドレスに変換する。
【０００７】
以上のいずれの方式も、LSNの内部で、フローの状態を管理する必要がある。ここで、フローとは{srcIP，dstIP，srcPort，dstPort，Protocol}の5つ組を同じくするパケット群を指す。
【０００８】
フローの状態の管理の例を図２に示す。この例では、ネットワーク外部ホストX1（インターネット上のホスト）129.1.1.1とネットワーク内部ホストY1（プライベートアドレス：ポート番号＝192.168.0.1:1024）と通信し、ネットワーク外部ホストX2 129.2.2.2とネットワーク内部ホストY2（192.168.0.1:1025）と通信しているとする。通常のNAPTだと、２つの内部ホストに対して、それぞれ別の{グローバルIPv4アドレス，ポート番号}を割り当てる。例えば、192.168.0.1:1024⇔129.0.0.1:1000，192.168.0.1:1025⇔129.0.0.1:1001、というように、２つのプライベートアドレス：ポートに対して、129.0.0.1:1000, 129.0.0.1:1001という２つのグローバルIPv4：ポートを割り当てる。
以上，図２に示すように，フロー状態を管理する必要のあるシステムにおいては、フロー管理テーブルのサイズを適切に設計する必要がある。LSNへのトラヒックのインパクト評価として、非特許文献５〜７の報告がある。これらは、ホスト当りの生成フロー数の平均やその分布がどうなっているかを、実測データから算出している。例えば、非特許文献５では、一部のホストが多数のフローを生成していることを示している。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Cisco Visual Networking Index: Forecast and Methodology, 2008-2013, http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white paper c11-481360.pdf
【非特許文献２】S. Miyakawa, "From IPv4 only To v4/v6 Dual Stack," IETF72 IABTechnical Plenary, Aug. 2008. http://www.nttv6.jp/ miyakawa/IETF72/IETF-IAB-TECH-PLENARY-NTT-miyakawa.pdf
【非特許文献３】T. Nishitani et al., "Common functions of large scale NAT (LSN)," draftnishitani-cgn-02, IETF, May 2009.
【非特許文献４】Y. Shirasaki et al., "NAT444 with ISP shared address," draft-shirasakinat444-isp-shared-addr-01 (work in progress), March 2009.
【非特許文献５】G. Maier et al., "On dominant characteristics of residential broadband Internet traffic," ACM IMC 2009.
【非特許文献６】http://www.janog.gr.jp/meeting/janog24/program/d2p5.html
【非特許文献７】屏, "ISPへのNAT導入によるユーザ影響評価,"電子情報通信学会誌, Vol. 93, No. 6, pp. 473-478, 2010年6月.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記の非特許文献５〜７においては、１ホスト当りの生成フロー数分布に関する報告、あるいは、その結果、全ホストを多重したときに平均して１ホスト当り何フロー生成しているかといった分析を行っているだけである。一方、フロー管理テーブルのサイズを設計するには、複数のホストを多重していったときに、フローテーブルにおけるエントリ数（同時フロー数）の変動量、つまり分散がどのようになるかを把握する必要がある。例えば、ホストを多重したときの同時フロー数の平均が100本であったとしても、その分散が100なのか10000なのかで必要となるフローテーブルサイズは大きく異なるからである。分散が100の場合、標準偏差はその平方根である10となり、例えば、同時フロー数の変動を考慮して、平均＋３×標準偏差＝130エントリ分のテーブルを用意すれば、同時フロー数が正規分布に従う場合にはエントリ成功率は99.87%とできる。一方、分散が10000の場合には、同じ成功率を達成するためには、平均＋３×標準偏差＝400エントリ用意する必要がある。以上のように、同時フロー数の変動量（分散）を正しく見積もる必要があるという課題があった。
【００１１】
本発明の目的は、上述の問題点に鑑み、ネットワーク内で測定可能な統計量を用いて、フロー状態を管理するネットワーク装置内にて必要となるフローテーブルのサイズを決定するための、同時フロー数の変動量（分散）を推定するための同時フロー数変動量推定方法及び装置を提供することにある。
【課題を解決するための手段】
【００１２】
本発明の第1の方法においては、
{srcIP，dstIP，srcPort，dstPort，Protocol}の５つ組みを同じくするパケット群をフローと定義し、フロー毎の状態を管理するネットワーク装置において必要となるフローエントリ数を見積もるために、
ネットワーク内を通過するフローiの情報を、予め定めた測定期間Tの間、収集して記憶手段に格納する。ここで、フローiの情報とは、フローキーi={srcIP，dstIP，srcPort，dstPort，Protocol}、フローiの開始時刻Tfirst_iと終了時刻Tlast_i、およびそれらから計算されるフロー持続時間d_i=Tlast_i-Tfirst_iとなる。ここでd_i>0となるフローがN本収集されたとし、フロー持続時間の平均をavg_d=Σd_i/Nとする。これら収集されたフローの中から、ランダムに２つのフローiとjを選択し、Hmin=min(d_i,d_j)とし、これを予め定めた回数M回実施する。m番目の試行におけるHminの値をHmin(k)とし、その平均avg_Hmin=ΣHmin(m)/Mにより計算する。
【００１３】
次に、フロー情報を用いて、srcIP#x毎の発生フロー数に関する統計情報を求める。具体的には、まず、測定期間Tを、Tより小さい測定周期τで分割し（区間がT/τ=L個生成される）、k番目の測定区間における、srcIP#xからの発生フロー数をF(x,k)とする。F(x,k)を用いて、あるsrcIPから生成されるフロー数の平均Eと分散Vを計算する。
【００１４】
そして、単位時間当たりの到着srcIP数Aを、A＝N/T/Eにより計算する。
【００１５】
以上の準備の下、同時フロー数の分散VarLを以下の式で算出することを特徴とする。
【００１６】
VarL=A×(V+E2-E)×avg_Hmin+A×E×avg_d                  （１）
本発明の第２の方法においては、第１の方法におけるEとVを計算する方法として、出現srcIPの集合をw_sとしたとき、x∈w_sかつk∈[1,L]に対し収集されたF(x,k)のうち、F(k,x)>0を満たすものだけを抽出する。そして抽出されたF(k,x)の数をLWとし、
E=ΣF(k,x)/LW，V=ΣF(k,x)2/LW-E2
により計算することを特徴とする。
【００１７】
本発明の第３の方法においては、
第１の方法では、収集フロー情報からAを計算していたのに対して、将来時点でのAが予め定めたA*になると仮定したときの、同時フロー数の分散を
VarL=A*×(V+E2-E)×avg_Hmin+A*×E×avg_d
により見積もることを特徴とする。
【００１８】
本発明の第４の方法においては、
第１または３の方法で、同時フロー数の分散を推定する際に、推定に用いるフロー情報のうち、宛先ポート番号が特定の番号（スキャンなどの異常トラヒックに多く見られるポート番号）であるフローを除外してから、分散の推定を行うことを特徴とする。
【００１９】
本発明の第５の方法においては、
第１の方法では、収集フロー情報からAを計算していたのに対して、フロー情報の収集対象となるユーザ数をZとして、仮に収容ユーザ数をZ'としたときの同時フロー数の分散を 
VarL=A/Z×Z'×(V+E2-E)×avg_Hmin+ A/Z×Z'×E×avg_d
により見積もることを特徴とする。
【００２０】
本発明の第６の方法においては、
第１の方法におけるavg_dとavg_Hminを用いて
α=avg_Hmin/avg_d
を計算しておき、別途、第１の方法における測定期間Tよりも短い測定期間T'において収集されたフロー情報があったとする。このとき、該フロー情報を用いて、srcIP#x毎の発生フロー数に関する統計情報を求める。具体的には、まず、測定期間T'を、T'より小さい測定周期τで分割し（区間がT'/τ=L'個生成される）、k番目の測定区間における、srcIP#xからの発生フロー数をF(x,k)とする。F(x,k)を用いて、あるsrcIPから生成されるフロー数の平均Eと分散Vを計算する。また、単位時間当たりの到着srcIP数Aを、
A＝N/T'/E
により計算する。
【００２１】
また、測定期間T'における同時フロー数の平均avgL'を収集フロー情報より算出しておく。
【００２２】
以上の準備の元、同時フロー数の分散Var_Lを以下の式で推定することを特徴とする。
【００２３】
VarL=A×(V+E2-E)×avgL'/(A×E)×α+avgL'
【発明の効果】
【００２４】
以上説明したように、本発明によれば、ネットワーク内で測定可能な統計量を用いて、フロー状態を管理するネットワーク装置内にて必要となるフローテーブルのサイズを決定するための、同時フロー数の変動量（分散）を推定することが可能になる。
【図面の簡単な説明】
【００２５】
【図１】本発明において対象となるlarge scale NAT(LSN)の説明図である。
【図２】本発明において対象となるLSN内でのフロー管理テーブルの例である。
【図３】本発明が適用されるIPネットワークの基本構成図である。
【図４】本発明の第１の実施の形態における推定装置の構成図である。
【図５】本発明の第１の実施の形態におけるフロー管理テーブル管理のフローチャートである。
【図６】ポアソン到着を仮定したときの標準偏差の推定結果と実測値の結果を比較したグラフである。
【図７】本発明の第２の実施の形態に適用されるシステム構成図である。
【図８】本発明を適用した実データ分析結果である。
【発明を実施するための形態】
【００２６】
以下図面と共に、本発明の実施の形態を説明する。
【００２７】
[第1の実施の形態]
図３は本発明が適用されるIPネットワークの基本構成図であり、その一例を示す。
【００２８】
図３に示すように本推定装置１０はノード１，２間のリンクに挿入される形態で利用される。あるいは、ノード（スイッチやルータ）において、パケットをポートへミラーして、そのポートの先に本推定装置を設置してもよい。あるいは、パケットを図３の構成で一旦キャプチャしておき、後処理でパケットを先頭から読み出して本実施の形態に記載の手順（以下に記載）を実施してもよい。
【００２９】
図４は、本発明の第１の実施の形態における推定装置の構成を示す。
【００３０】
同図に示す推定装置１０は、前述の第１の方法で同時フロー数の分散を推定し、さらに第２の方法でその推定に必要となるホスト当りの発生フロー数の平均と分散を計算する装置であり、パケット解析部１１、フロー管理部１２、フロー統計情報収集部１３、同時フロー数分散推定部１４から構成される。
【００３１】
また、当該推定装置のフロー管理テーブル管理の動作のフローを図５に示す。
【００３２】
図４において、前段ノード１からパケットが到着したら、パケット解析部１１において、そのパケットのフローキー＝{srcIP#i，dstIP#i，srcPort#i，dstPort#i，Protocol#i}を読み出し、フロー管理部１２にフローキーを通知する。その後、パケットを後段ノード２に転送する（図５のステップ１０１）。
【００３３】
フロー管理部１２では、フロー管理テーブル（図示せず）を内部または外部に用意し、そのテーブルでは、フローキーi＝{srcIP#i，dstIP#i，srcPort#i，dstPort#i，Protocol#i}、および最初ならびに最後にパケットが到着した時刻Tfirst_i，Tlast_i，の２つを記憶しておく。該パケットのフローキーi＝{srcIP#i，dstIP#i，srcPort#i，dstPort#i，Protocol#i}が、フロー管理テーブルに既にエントリされているかチェックする（図５のステップ１０２）。新規であれば、パケットがTCPかつFINまたはRSTにフラグが立っていたら（図５のステップ１０３）何もしない。FINかつRSTでなければ、フロー管理テーブルに新規にエントリして、Tfirst_i←Tnow(現在の時刻)、Tlast_i←Tnowに設定する（図５のステップ１０４）。
【００３４】
既出と判定されたら（図５のステップ１０２、Yes）、パケットがTCPかつFINまたはRSTにフラグが立っているかチェックする（図５のステップ１０５）。もしフラグが立っていれば（図５のステップ１０５、Yes）、Tlast_i←Tnowと更新してから、該フローの情報（つまり、フローキーiと、Tfirst_i，Tlast_i）をフロー統計情報収集部に出力し、フロー管理テーブルから該情報を削除する（図５のステップ１０６）。もし、フラグが立っていなければ（図５のステップ１０５、No）、現在の時刻Tnowと、Tlast_iに予め定めたタイマー値Toutを足したものTlast_i+Toutを比較する（図５のステップ１０７）。もしTnowの方が大きければ（図５のステップ１０７、Yeｓ）、フロー管理テーブルのTlast_iをTlast_i+Toutに更新してから、該フローの情報（つまり、フローキーiと、Tfirst_i，Tlast_i）をフロー統計情報収集部１３に出力し、フロー管理テーブルから該情報を削除する（図５のステップ１０８）。
【００３５】
フロー管理部１２は、以上を測定期間Tの間実施する。測定期間終了時点でフロー管理テーブルに残っているフロー情報はフロー統計情報収集部１３に出力する。ただし、このときのTlast_iは，Tlast_i+Tout<TnowであればTlast_iをTlast_i+Tout に更新し，そうでなければTlast_i をnullと設定してから出力する。
【００３６】
フロー統計情報収集部１３では、フロー管理部１２から出力されたフロー情報をメモリ（図示せず）に格納し、そのフロー情報のうち、Tlast_iがnullでない、かつ、Tfirst_iが測定開始からTout以上経過しているフローのみ抽出し、同時フロー数分散推定部１４に出力する。その理由は、Tout経過していないフローは、測定開始以前から通信を継続している可能性があるため、Tfirst_iが本当のフロー開始時刻とは限らないためである。
【００３７】
同時フロー数分散推定部１４では、フローiの開始時刻Tfirst_iと終了時刻Tlast_iからフロー持続時間d_i=Tlast_i-Tfirst_iを計算する。ここでd_i>0となるフローがN本収集されたとし、フロー持続時間の平均をavg_d=Σd_i/Nとする。これら収集されたフローの中から、ランダムに２つのフローiとjを選択し、Hmin=min(d_i,d_j)とし、これを予め定めた回数M回実施する。m番目の試行におけるHminの値をHmin(k)とし、その平均を、
avg_Hmin=ΣHmin(m)/M
により計算し、メモリ（図示せず）に格納する。
【００３８】
次に、フロー統計情報収集部１３は、フロー情報を用いて、srcIP#x毎の発生フロー数に関する統計情報を求める。具体的には、まず、測定期間Tを、Tより小さい測定周期τで分割し（区間がT/τ=L個生成される）、k番目の測定区間における、srcIP#xからの発生フロー数をF(x,k)とする。同時フロー数分散推定部１４は、当該フロー数F(x,k)を用いて、あるsrcIPから生成されるフロー数の平均Eと分散Vを計算する。そして、単位時間当たりの到着srcIP数Aを、A＝N/T/Eにより計算する。
【００３９】
以上の準備の下、同時フロー数分散推定部１４は、同時フロー数の分散VarLを以下の式で算出する。
【００４０】
VarL=A×(V+E2-E)×avg_Hmin+A×E×avg_d          (1)
ここで上記数式(1)について説明する。そのために、図６の実験結果についてまず説明する。これは本発明者らによる先行研究（文献１：R. Kawahara, T. Mori, T. Yada, "Analysis of impact of traffic on large-scale NAT, " IEICE Technical Report, vol. 110, no. 224, IN2010-78, pp. 75-80, Oct. 2010. ）における結果である。
【００４１】
図６のグラフのうち、"Poisson"'というラインは、フローの発生が、ポアソン過程と呼ばれるトラヒック理論でよく用いられる確率過程に従うと仮定して、同時フロー数の標準偏差（＝分散の平方根）を見積もった結果である。
【００４２】
それに対して、図中の"data set A"、"data set B"は、あるインターネットトラヒックの実測データを用いて、同時フロー数の平均と標準偏差をプロットした値である。これより、ポアソンを仮定したラインと、実測値の結果は大きくずれていることが分かる。
【００４３】
単位時間当たりの到着フロー数をλ、フローの持続時間Hの平均をE[H]と置くと、同時フロー数Lの平均E[L]は、E[L]=λ×E[H]で与えられる。これはフローの発生がポアソンかどうかに依らず成立し、リトルの公式と呼ばれる（文献２：「滝根，伊藤，西尾，ネットワーク設計理論，岩波講座」参照）。一方、フローの発生がポアソンに従う場合、待ち行列モデルにおけるM/G/∞を適用すると系内滞在客数（つまり同時フロー数）の分散Var[L]は、Var[L]=E[L]となる。つまり、標準偏差はsqrt(E[L])となる。従って、図６のPoissonのラインは、y=sqrt(x)のラインということになる。
【００４４】
図６のように、実測値が理論値と大きく乖離する理由の一つとして、フローがポアソン過程に従わず、同時に複数のフローが発生することが考えられる。実際、前述の非特許文献２では、最近のアプリケーションが同時に何十本ものフローを生成することを指摘している。
【００４５】
そこで本発明では、フローの集団到着モデルを考える。具体的には、M[x]/G/∞という集団到着モデルの適用を考える。この場合、各ホスト(=srcIP)がポアソンで到着し、ホスト到着時に同時に複数のフローが発生するモデルとなる。このとき、同時フロー数の分散Var[L]は、次式で計算される（文献３：J. Keilson and A. Seidmann, "M/G/∞ with batch arrivals," Operations Research Letters, Oct. 1988. 参照）。
【００４６】
Var[L] =λE[K(K-1)]E[min(H1,H2)]+E[L]                    （２）
ここで、Kはあるホストが到着した際に生成するフロー数、H1，H2はフローの持続時間、を表す確率変数である。
【００４７】
本発明においては、この式(2)の、E[K(K-1)]，E[min(H1,H2)]をネットワークで測定可能な統計量から決定している。
【００４８】
具体的には、収集されたフロー情報から、フローiの持続時間d_iを計算し、これらフローの中から、ランダムに２つのフローiとjを選択し、Hmin=min(d_i,d_j)とし、これを予め定めた回数M回実施する。m番目の試行におけるHminの値をHmin(k)とし、その平均を
avg_Hmin=ΣHmin(m)/M
により計算する。そして上記の数式(２)におけるE[min(H1,H2)]を、avg_Hminにより推定する。 
次に、測定期間Tを、Tより小さい測定周期τで分割し（区間がT/τ=L個生成される）、k番目の測定区間における、srcIP#xからの発生フロー数をF(x,k)とし、F(x,k)を用いて、あるsrcIPから生成されるフロー数の平均Eと分散Vを計算する。そして数式(２)におけるE[K(K-1)]をEとVを用いて、V+E2-Eにより推定する。これは、
E[K(K-1)]=E[K2]-E[K]=Var[K]+E[K]2-E[K]
となるからである。
【００４９】
数式(２)におけるE[L]は、リトルの公式E[L]=λ×E[H]より、到着ホスト数の平均Aにホスト到着当りの発生フロー数の平均EをかけたものA×Eを到着フロー数λの推定値とし、それと持続時間の平均d_avgを用いて、A×E×d_avgによりE[L]を推定している。
【００５０】
[第２の実施の形態]
第１の実施の形態では、図３のように、ノード１，２間に挿入する形で本推定装置を構成したが、図７に示すように、ネットワーク内の各ルータ３からフロー情報を出力させて、それを収集する形態でもよい。なお、推定装置の構成自体は、図４と同様であり、推定装置の処理も第１の実施の形態と略同様であるが、一般的なルータのフロー出力機能においてはフロー持続時間d_i=0となるフロー（例えば、１パケットだけからなるフローで、そのパケットがTCPのFINまたはRSTが付与されている）も存在するため、d_i>0となるフローのみを対象とする必要がある。
【００５１】
［第３の実施の形態］
本実施の形態における推定装置の構成は図４と同様である。
【００５２】
第１の実施の形態における平均Eと分散Vを計算する方法として、本実施の形態では、同時フロー数分散推定部１４において、出現srcIPの集合をw_sとしたとき、x∈w_sかつk∈[1,L]に対し収集されたF(x,k)のうち、F(k,x)>0を満たすものだけを抽出する。そして抽出されたF(k,x)の数をLWとし、平均Eと分散Vを、
E=ΣF(k,x)/LW，V=ΣF(k,x)2/LW-E2
により計算する。
【００５３】
［第４の実施の形態］
本実施の形態における推定装置の構成は図４と同様であるが、同時フロー数分散推定部１４の動作が異なる。
【００５４】
第１の実施の形態において、収集フロー情報からAを計算していたのに対して、本実施の形態では、同時フロー数分散推定部１４において、将来時点でのAが予め定めたA*になると仮定したときの、同時フロー数の分散を
VarL=A*×(V+E2-E)×avg_Hmin+A*×E×avg_d
により見積もる。
【００５５】
こうすることで、将来時点での需要A*に対して、同時フロー数の変動量を見積もることが可能となる。なお、需要がA*に変化したときの同時フロー数の平均は、
A*×E×d_avg
により算出される。
【００５６】
［第５の実施の形態］
本実施の形態における推定装置の構成は図４と同様であるが、同時フロー分散推定部１４の動作が第１、第４の実施の形態と異なる。
【００５７】
第１の実施の形態及び第４の実施の形態に記載の方法で、同時フロー数分散推定部１４において、本実施の形態では、同時フロー数の分散を推定する際に、推定に用いるフロー情報のうち、宛先ポート番号が特定の番号（スキャンなどの異常トラヒックに多く見られるポート番号）であるフローを除外してから、分散の推定を行う。
【００５８】
文献１に記載のように、フローを大量に生成するホストからのトラヒックの中には、スキャンなどの異常トラヒックが含まれていることがある。そこで、そのようなトラヒックを除去する機能をLSNに設けることで、そのようなトラヒックを除いた後のトラヒックに対して適切なフロー管理テーブルのサイズを設計する必要がある。そこで、ポート番号１３５，４４５といったスキャントラヒックを除去した後に、同時フロー数の変動量を推定することを提案している。
【００５９】
[第６の実施の形態]
本実施の形態における推定装置の構成は図４と同様であるが、同時フロー分散推定部１４の動作が第１の実施の形態と異なる。
【００６０】
第１の実施の形態では、収集フロー情報から単位時間当たりの到着srcIP数A を計算していたのに対して、本実施の形態では、同時フロー数分散推定部１４において、フロー情報の収集対象となるユーザ数をZとして、仮に収容ユーザ数をZ'としたときの同時フロー数の分散を 
VarL=A/Z×Z'×(V+E2-E)×avg_Hmin+ A/Z×Z'×E×avg_d
により見積もる。
【００６１】
なお、ユーザ数Zについては、監視対象としているネットワークにおける収容ユーザ数を用いるか、あるいは、収集されたフロー情報から、出現するsrcIP数をカウントし、それをZとして用いてもよい。
【００６２】
[第７の実施の形態]
本実施の形態における推定装置の構成は図４と同様であるが、フロー情報収集部１３、同時フロー数分散推定部１４の動作が異なる。
【００６３】
第１の実施の形態におけるフロー持続時間の平均avg_dとavg_Hminを用いて
α=avg_Hmin/avg_d
を計算しておき、別途、第１の実施の形態における測定期間Tよりも短い測定期間T'において収集されたフロー情報があったとする。本実施の形態では、このとき、フロー統計情報収集部１３は、該フロー情報を用いて、srcIP#x毎の発生フロー数に関する統計情報を求める。
【００６４】
具体的には、まず、測定期間T'を、T'より小さい測定周期τで分割し（区間がT'/τ=L'個生成される）、k番目の測定区間における、srcIP#xからの発生フロー数をF(x,k)とする。同時フロー数分散推定部１４は、F(x,k)を用いて、あるsrcIPから生成されるフロー数の平均Eと分散Vを計算する。また、単位時間当たりの到着srcIP数Aを、
A＝N / T' / E
により計算する。
【００６５】
また、測定期間T'における同時フロー数の平均avgL'を、図４のフロー統計情報収集部１３において収集されたフロー情報を用いて算出しておく。その手順について述べる。
【００６６】
測定期間T'のデータについて、便宜上、時刻0から時刻T'までのデータとして説明する。T'を測定周期τで分割したとし、時点kτ(k=1からL')に対して、
Tfirst_i<kτ<Tlast_i
を満たすフローiの数をカウントし、それを時点kτでの同時フロー数L(k)とし、
avgL'=ΣL(k)/L'
と計算する。 
以上の準備の元、同時フロー数分散推定部１４は、同時フロー数の分散Var_Lを以下の式で推定する。
【００６７】
VarL=A×(V+E2-E)×avgL'/(A×E)×α+avgL'
上記の方法について補足説明する。ここでは、測定期間T'におけるデータを用いて同時フロー数の平均avgL'は直接算出している。一方、期間T'が分散を出すのには測定期間長が不十分である場合を想定し、上記の式で分散は推定している。その際に、上記の式の右辺第一項において、第1の実施の形態ではavg_Hminの値を用いていたが、avg_Hminはそのときのavg_d（フロー持続時間の平均）に依存して決まるため、現在の（つまり期間T'における）フロー持続時間の平均が、別途測定されているそれ（つまりavg_d）と異なる可能性がある。そこで、本実施の形態では、現在の同時フロー数の平均avgL'から、現在のフロー持続時間の平均を、リトルの公式を用いて、avgL'/(A×E)により推定し、その値にαをかけることで、現在のavg_Hminの値を推定している。
【００６８】
また、上記の第１〜７の実施の形態における推定装置の構成要素の動作をプログラムとして構築し、推定装置として利用されるコンピュータにインストールして実行させることが可能である。
【００６９】
なお、本発明は上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更、応用が可能である。
【符号の説明】
【００７０】
１  前段のノード
２  後段のノード
１０  推定装置
１１  パケット解析部
１２  フロー管理部
１３  フロー統計情報収集部
１４  同時フロー数分散推定部
【図１】
0005545674.tif 000002
【図２】
0005545674.tif 000003
【図３】
0005545674.tif 000004
【図４】
0005545674.tif 000005
【図５】
0005545674.tif 000006
【図６】
0005545674.tif 000007
【図７】
0005545674.tif 000008
【図８】
0005545674.tif 000009