JP6660283B2 - トラヒック需要予測装置、トラヒック需要予測方法、及びプログラム - Google Patents

Description

本発明は、ネットワークのトラヒック制御技術に関連するものである。

近年、ネットワークサービスの多様化に伴い、突発的なトラヒック変動が増加している。トラヒック変動として、OSアップデート・人気動画ストリーミング配信や人気アプリケーションの配信・企業拠点間やデータセンター間のバックアップ通信等、ネットワーク全体でトラヒックが急増する場合や、オリンピックやコンサート等のライブイベント・通勤混雑等、トラヒック発生箇所が局所的に集中する場合が想定される。これらの「イベント」が原因で発生する突発的なトラヒックの変動は、ネットワークの輻輳の原因となる。通信事業者は、何らかのイベントにより突発的なトラヒック変動が発生したとしても、ネットワークの輻輳を回避する必要がある。

輻輳を回避する方法として、トラヒック量のピーク値に合わせた、ネットワークリソースの増設が考えられる。しかし、リソースの増設には時間を要するため、突発的なイベントトラヒックが原因の輻輳に対して、リソースの増設で対応することは困難である。また、イベント等が原因となって発生する突発的なトラヒックの増加は一時的であることが多く、イベントに対応するためにリソースを増設することは高コストである。

限られたネットワークリソースを動的に割り当てることで、トラヒックを効率的に収容する技術として、トラヒックエンジニアリング(TE)技術がある。TEは、トラヒック需要とネットワークリソースの利用状態に応じて、トラヒックの経路を動的に制御することで、トラヒックの収容効率を向上させている。TEの例として、ネットワーク内の最大リンク利用率の最小化や平均遅延時間の最小化を目的とした経路制御等が考えられる。

TEの中でも、将来のトラヒック需要を予測し、予測結果に基づいたトラヒックの経路制御を実施するTEを、予測型TEと呼ぶ。予測型TEの利点は、将来のトラヒック変動を考慮した経路制御を行うことで、将来発生し得る輻輳を予め回避することが可能であるという点である。予測型TEにより、予めイベントによるトラヒック需要を予測し、動的にトラヒックの経路を変更することで、イベント発生時における突発的なトラヒック変動によるネットワークの輻輳を回避することが可能であると考えられる。

しかし、予測型TEでは、トラヒック需要の予測を外してしまった場合、特定リンクへトラヒックが集中し、リソース利用効率が低下してしまう。そのため、イベント情報の予測が外れてしまった場合、経路制御の効率が大幅に低下してしまう可能性がある。

従って、イベント等で発生する突発的なトラヒック変動に対応したトラヒック制御を実施するためには、イベント情報を活用し、イベント情報の確度 (予測の正確性) に応じ適切な制御を行うことができる、トラヒック制御技術が必要である。

トラヒック需要の予測に関連して、非特許文献１には、ニューラルネットワークとファジー理論を組み合わせたモデルを用いて、短期的な予測に関して、学習期間やデータの粒度と予測の精度の関係について調べることが開示されている。また、非特許文献２には、ウェブレット変換による多重解像度分析を用いて、６ヶ月先までのインターネットバックボーンのトラヒック量の予測することが開示されている。

上記の非特許文献１、２のプローチでは、トラヒックの過去の時系列データから、トラヒック生成パターンをモデル化することで、短期的な標準偏差や長期的なトレンドを予測している。しかし、時系列データによるトラヒック予測では、過去の変動をもとに将来の変動を予測しているため、イベント発生時のような過去に類を見ない突発的なトラヒック変動を予測することは困難である。

上記のアプローチによりイベント情報を活用した経路制御を実施する場合、イベント発生時には、トラヒック需要の予測外れにより、経路制御の効率が大幅に劣化してしまうという課題がある。

また、非特許文献３、及び 特許文献１には、5-tuple (送信元アドレス，宛先アドレス，送信元ポート番号，宛先ポート番号，プロトコル番号) が異なる大量のフローを集約し、同様の特性を示すフロー集合であるマクロフローを生成することが開示されている。ここでは、5-tupleフローのトラヒック量を予測可能マクロフローと予測困難マクロフローに分類し、予測可能マクロフローのみに予測型TEを用いることで、予測型TEの課題である予測外れの課題を解決している。本アプローチでは、過去のトラヒックの変動成分を分析し、トラヒック需要を予測可能な成分と予測困難な成分に分離し、それぞれの成分ごとに異なる経路制御を実施している。なお、特許文献１における安定マクロフローが予測可能マクロフローに相当し、安定マクロフローでないものが予測困難マクロフローに相当する。

しかし、上記のアプローチをイベントトラヒック制御に適応する場合、イベント等で発生する突発的なトラヒックは、予測困難マクロフローとして分類されてしまう。予測困難マクロフローに対しては、最適な経路を割り当てることが困難であるため、イベントトラヒックの割合が増加するほど、ネットワークリソースの利用効率が低下してしまうという課題がある。

また、非特許文献４には、過去のトラヒックの時系列データだけではなく、TVの視聴率や人気番組の配信情報等の外部情報を活用し、Video on Demand (VoD)サービス品質を保証するために必要な追加リソース配備量の推定を行うことが開示されている。

本従来技術では、TVの視聴率とVoD サービスの利用率に負の相関があることや、人気番組が配信される時間帯にトラヒックが増加することを利用し、ピークトラヒック量の予測精度を向上させている。例えば、過去のトラヒック需要から算出したトラヒック需要の予測モデルに対して、「土曜日や祝前日の22:00-23:00」や「人気ドラマが配信される火曜日の22:00-23:00」にトラヒック量が増加するという外部情報に基づき予測モデルを修正することで、予測モデルの予測誤差が減少することを示している。

上記のアプローチでは、過去のトラヒックの時系列データ以外の外部情報をトラヒック予測に活用することで、高精度なトラヒック予測を可能にしている。しかし、このアプローチでは、リソースの増設により輻輳を回避しているため、対応までに長時間を必要する、高コストである、といった課題がある。

M. F. Zhani, H. Elbiaze, and F. Kamoun, "Analysis and prediction of real network traffic," Journal of Networks, vol. 4, no. 9, pp. 855-865, nov 2009. K. Papagiannaki, N. Taft, Z.-L. Zhang, and C. Diot, "Longterm forecasting of internet backbone traffic: Observations and initial models," in Proceedings of INFOCOM, vol. 2, mar 2003, pp. 1178-1188. Y. Takahashi, K. Ishibashi, M. Tsujino, N. Kamiyama, K. Shiomoto, T. Otoshi, Y. Ohsita, and M. Murata, "Separating predictable and unpredictable flows via dynamic flow mining for effective traffic engineering." 2016 IEEE International Conference on Communications (ICC). IEEE, 2016. H. Hasegawa, S. Kouno, A. Shiozu, M. Sasaki, and S. Shimogawa, "Predictive network traffic engineering for streaming video service." 2013 IFIP/IEEE International Symposium on Integrated Network Management (IM 2013). IEEE, 2013.

高橋洋介，石橋圭介，塩本公平，大下裕一，村田正幸，"フロー集約装置及び方法及びプログラム",特開2015-156529

イベント等による突発的なトラヒック変動が発生するネットワークにおいて、トラヒックの効率的な収容（目標例：最大リンク利用率の最小化、平均遅延時間の最小化）に向けた経路制御を行う場合、従来技術では以下のような課題があった。

すなわち、非特許文献１、２に開示された技術のように、過去の時系列データから、トラヒック需要をモデル化することで、過去のトラヒック需要に基づくトラヒック需要予測により経路制御を行う場合、過去に類を見ない突発的なトラヒック変動には予測できず、予測外れにより経路制御の目標達成度が大幅に劣化する。

また、非特許文献３、特許文献１に開示された技術のように、トラヒック需要を予測可能と予測困難な成分に分離し、それぞれの成分ごとに異なる経路制御を行う場合、予測外れの問題はある程度改善するが、イベントトラヒックが予測困難な成分に分類されるため、経路制御の目標達成度が劣化する。

また、非特許文献４に開示された技術のように、外部情報に基づくトラヒック需要予測によりリソースを予め増設する場合、高精度なトラヒック予測が可能であるが、対応までに長時間を要し、追加コストも大きい。

本発明は上記の点に鑑みてなされたものであり、外部情報としてイベント情報を活用し、トラヒック需要を高精度に予測するとともに、背景トラヒックに基づきイベントトラヒックを高精度に分類することを可能とし、短時間でかつ目標達成度が高い経路制御を実現する技術を提供することを目的とする。

開示の技術によれば、ネットワークにおけるトラヒックの需要を予測するトラヒック需要予測装置であって、
前記ネットワークから収集されたトラヒック情報から、イベント情報に関連しないトラヒックである背景トラヒックを取得する取得手段と、
前記イベント情報におけるイベントトラヒックの予測値の分散と、前記背景トラヒックの平均とを比較し、前記分散が前記背景トラヒックの平均よりも大きい場合、前記イベントトラヒックの特性を予測困難に分類し、前記分散が前記背景トラヒックの平均よりも小さい場合、前記イベントトラヒックの特性を予測可能に分類し、予測困難と予測可能のそれぞれについて、イベントトラヒック需要を集計することによりトラヒックマトリックスを算出する特性別トラヒック需要算出手段と
を備えることを特徴とするトラヒック需要予測装置が提供される。

開示の技術によれば、外部情報としてイベント情報を活用し、トラヒック需要を高精度に予測するとともに、背景トラヒックに基づきイベントトラヒックを高精度に分類することを可能とし、短時間でかつ目標達成度が高い経路制御を実現する技術が提供される。

本発明の実施の形態の概要を説明するための図である。 本発明の実施の形態におけるシステム構成図である。 フロー集約装置１００の構成図である。 フローデータベース１０１を説明するための図である。 フロー集約装置１００のハードウェア構成例を示す図である。 特性別トラヒック需要算出部１０３のアルゴリズムを示す図である。 特性別トラヒック需要算出部１０３の処理フローを示す図である。 イベントトラヒックの分類例を示す図である。 予測可能マクロフローの数理アルゴリズムを示す図である。 予測困難マクロフローの数理アルゴリズムを示す図である。

以下、図面を参照して本発明の実施の形態（本実施の形態）を説明する。以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。

（本実施の形態における制御単位について）
本実施の形態では、トラヒックをフローと呼ばれる単位で制御している。フローにおける単位としては、5-tuple (送信元アドレス，宛先アドレス，送信元ポート番号，宛先ポート番号，プロトコル番号) が異なる固有のフローであるマイクロフローと呼ばれる単位と、マイクロフローを集約したマクロフローと呼ばれる単位を用いることとしている。マクロフローは、フローヘッダ情報 (5-tuple)を任意に組み合わせて識別するフローである。

（技術の概要）
まず、図１を参照して、本実施の形態に係る技術の概要（イメージ）を説明する。図１は、ある発着ノード間のトラヒック需要の総和を示す。ここでは、あるイベントにより突発的なトラヒックが14:00~14:30, 17:00~17:30,20:00~20:30に発生したとする。図１は、全トラヒックが、予測可能な成分と予測困難な成分に分離されていることを示している（このような分離は、特許文献１の技術により可能である）。

本実施の形態に係る技術では、イベント情報（発着ノード、任意の5-tupleマクロフロー、イベント開始時刻、イベント終了時刻、トラヒック量の情報等を有する情報）の確度 (予測の正確性) に応じた適切なトラヒック制御を可能としている。例えば、14:00からのイベント情報におけるイベントトラヒック量の分散が背景トラヒックに比べて大きい場合には、当該イベント情報は確度が低いと判断され、当該イベント情報を予測困難に分類した方が適切と判断される。

また、例えば、20:00からのイベント情報におけるイベントトラヒック量の分散が背景トラヒックに比べて小さいような場合、当該イベント情報は確度が高いと判断され、当該イベント情報を予測可能に分類した方が適切と判断される。

このような判断により、従来のように全てのイベントトラヒックを予測困難な成分に分類するといったことがなくなり、適切な経路制御を実現できる。

なお、イベント情報の確度が高い（イベント情報が正確である、と言い換えてもよい）とは、一例として、「背景トラヒックの量に対して、イベントトラヒックの量の分散が低いこと」、及び、「イベントマクロフローが、背景トラヒックとイベントトラヒックを適切に分離できていること」を満たすイベント情報のことを指す。

イベント情報の確度に関して、例えば，"人気動画配信により、19:00~19:30に200~250Mbpsのイベントトラヒックが発生する"というイベント情報を考えた場合、イベントの確度とは、"200~250Mbps"に相当する。"229~230Mbps"であれば確度の高いイベント情報であり、"100~500Mbps"であれば確度の低いイベント情報であると考えられる。ただし、確度は、背景トラヒックにより相対的に決定される。例えば、過去の背景トラヒック量の平均値が10Mbpsであれば、"200~250Mbps"は背景トラヒックの5倍近くの分散があるため確度が低いと考えられるが、過去の背景トラヒック量の平均値が10Gbpsであれば"200~250Mbps"は確度が高いと考えることができる。これが、上記の、「背景トラヒックの量に対して、イベントトラヒックの量の分散が低いこと」に相当する。

「イベントマクロフローが、背景トラヒックとイベントトラヒックを適切に分離できていること」について、イベントマクロフローとは、イベント情報に含まれるマクロフロー (送信元アドレス，宛先アドレス，送信元ポート番号，宛先ポート番号，プロトコル番号) のことであり、例えば、当該マクロフローは"10.0.0.1,*,*,*,6"と表わされる。「*」は特定の値を指定していないことを示す。

ここでは、例えば、"*,*,*,*,6"を確度の低いイベント情報、"10.0.0.1,20.0.0.1,80,*,6"を確度の高いイベント情報と考えることができる。すなわち、"*,*,*,*,6"は、TCP (プロトコル番号6) による全ての通信を表すことから、「TCPで送られているイベントが発生する」というイベント情報は、背景トラヒックとイベントトラヒックを適切に分離できず、確度が低いイベント情報と考えることができる。また、"10.0.0.1,20.0.0.1,80,*,6"は，10.0.0.1 から 20.0.0.1 に送られる、TCP (プロトコル番号6) 、Http (ポート番号80) による全ての通信を表すことから、背景トラヒックとイベントトラヒックを適切に分離でき、このイベント情報は確度が高いと考えることができる。

なお、イベント情報の確度が高いことの要件として、「背景トラヒックの量に対して、イベントトラヒックの量の分散が低いこと」、及び、「イベントマクロフローが、背景トラヒックとイベントトラヒックを適切に分離できていること」の両方を用いることは一例である。例えば、「背景トラヒックの量に対して、イベントトラヒックの量の分散が低いこと」のみ、あるいは、「背景トラヒックの量に対して、イベントトラヒックの量の分散が低いこと」と、「イベントマクロフローが、背景トラヒックとイベントトラヒックを適切に分離できていること」以外の事項とを要件としてもよい。また、「背景トラヒックの量に対して、イベントトラヒックの量の分散が低いこと」と「イベントマクロフローが、背景トラヒックとイベントトラヒックを適切に分離できていること」のいずれとも異なる事項を要件としてもよい。

（システム構成）
図２に、本実施の形態におけるシステム構成図を示す。図２に示すとおり、本実施の形態におけるシステムは、フロー集約装置１００、経路計算装置２００、制御設定装置３００（コントローラと称してもよい）、転送装置４０１〜４０３（ノードと称してもよい）、端末５０１〜５０４を有し、図示のとおりに装置間で情報の送受信が可能なように通信接続がなされている。なお、以下、転送装置４０１〜４０３を総称する場合、転送装置４００とし、端末５０１〜５０４を総称する場合、端末５００とする。また、フロー集約装置１００をトラヒック需要予測装置と称してもよい。

フロー集約装置１００は、入力されるトラヒック情報、及びイベント情報に従い、トラヒック需要の予測値、イベントトラヒック需要の予測値を算出し、これら予測値を経路計算装置２００に送信する機能を有する。

経路計算装置２００は、入力されるネットワーク構成情報、トラヒック需要予測、及びイベントトラヒック需要予測に従い、最適経路を計算する装置であり、制御設定装置３００に経路情報を送信する機能を有する。

制御設定装置３００は、ネットワーク内の全ての転送装置３００に経路情報を設定する装置であり、転送装置４００から送信されたトラヒック情報を集約する機能、及び、トラヒック情報をフロー集約装置１００に転送する機能を有する。

転送装置４００は、トラヒックを転送する装置であり、経路情報に従ってパケットを処理する。また、転送装置４００は、トラヒック量を計測し、トラヒック情報を収集し、トラヒック情報を制御設定装置３００に送信する機能を有する。端末５００はトラヒックを発生させる装置である。なお、端末５００と転送装置４００とからなる構成を「ネットワーク」と称してもよい。

経路計算装置２００に与えられるネットワーク構成情報は、ノードやリンク等ネットワークのトポロジ情報である。転送装置４００から制御設定装置３００に送信されるトラヒック情報は、マイクロフローの時系列データである。端末５００から送信されたトラヒックが、トラヒック情報として、ノードとコントローラを介して入手される。

＜イベント情報について＞
フロー集約装置１００に与えられるイベント情報は、発着ノード、任意の5-tupleマクロフロー、イベント開始時刻、イベント終了時刻、トラヒック量の情報を有している。これら全ての情報を有しなくてもよいが、少なくとも、発着ノード、イベント開始時刻、イベント終了時刻の情報を必要とする。

ノードには通り番号が割り当てられており、上記の「発着ノード」は、送信ノードの番号と着信ノードの番号である。「任意の5-tupleマクロフロー」は、イベントトラヒックを表現するマクロフローである。トラヒック量の情報は、例えば、イベントトラヒックの予測値、及び、イベントトラヒックの予測値の幅（分散）である。

イベント情報は、企業のプレスリリース、ニュース、ＳＮＳ、ＯＳアップデートの告知、人気アプリの配信の告知、コンサートの開催情報等の公開情報、又は、通信事業者の運用情報等の非公開情報から取得し、通信事業者のオペレータがマクロフロー形式でシステム（具体的にはフロー集約装置１００）に投入する。

イベントに起因するトラヒックは、任意の5-tuple マクロフローにより指定される。また、予測できない箇所は、「任意」を意味する「*」で指定することができる。また、イベントトラヒック量の予測精度があいまいである場合、トラヒック量の標準偏差や予測されるトラヒック量の最大値と最小値等、上記のように、トラヒック量に幅を持たせて指定することができる。

「From: 4, To: 7, "10.0.0.1,*,*,*,6", 14:00~14:30, 50Mbps, ±0Mbps」は、イベント情報の例である。このイベント情報は、ノード4からノード7へ、"10.0.0.1,*,*,*,6"という50Mbpsのイベントトラヒックが14:00~14:30に発生するという予測を示す。なお、"10.0.0.1,*,*,*,6"は、送信元サーバのIPアドレスが"10.0.0.1"であるTCPプロトコルの通信を意味する。

また、例えば、「From: 5, To: 2, "*,*,80,*,6", 14:00~14:30, 110Mbps, ±10Mbps」というイベント情報は、ノード5からノード2へ、"*,*,80,*,6"という100~120Mbpsのイベントトラヒックが14:00~14:30に発生するという予測を示す。なお、"*,*,80,*,6"は、TCPプロトコルを利用したHttpの通信を意味する。

図２に示すシステムを構成する装置のうち、フロー集約装置１００以外の装置は、従来技術を利用して実現することが可能である。以下、フロー集約装置１００の構成を説明する。

（フロー集約装置１００の構成について）
図３は、フロー集約装置１００の構成図である。図３に示すように、フロー集約装置１００は、フローデータベース１０１、マクロフロー生成部１０２、特性別トラヒック需要算出部１０３を有する。

フローデータベース１０１は、例えば特開2015-75896に開示されている多次元フローデータベースの機能を有する。すなわち、フローデータベース１０１は、トラヒック情報、及びイベント情報を入力として、トラヒック情報をイベントに該当するマイクロフローとイベントに該当しないマイクロフローに分離する機能を有する。

図４を参照して、フローデータベース１０１の機能について説明する。図４（ａ）に示すように、上記のイベント情報（具体的には、イベント情報に含まれる任意の5-tupleのマクロフロー）に相当するマクロフロークエリと、上記のトラヒック情報に相当するフローデータが入力され、該当するマイクロフロー情報（イベントに該当するトラヒック情報を指す）が出力される。なお、該当しないマイクロフロー情報（イベントに該当しないトラヒック情報を指す）も出力することができる。

図４（ｂ）にマクロフロークエリの例を示し、図４（ｃ）に該当するマイクロフロー情報例を示す。フローデータベース１０１の機能により、トラヒック情報から、イベントに関するマクロフローを分離することができる。

図３に戻り、マクロフロー生成部１０２は、マイクロフローデータから、特性の異なるマクロフローを出力する機能（例：特許文献１に開示されている機能）を有する。具体的には、マクロフロー生成部１０２は、背景トラヒックの予測可能・予測困難トラヒックマトリックスを算出する。

特性別トラヒック需要算出部１０３は、マクロフロー(イベントに関するマクロフロー・それ以外のマクロフロー)情報を入力とし、特性別のトラヒック需要(全てのノード間のトラヒック量)の予測値を算出する機能、及び、特性別のトラヒック需要予測を経路計算装置２００に送信する機能を有する。

上記のように、本実施の形態では、例として、トラヒックの特性を「予測可能」と「予測困難」としており、特性別トラヒック需要算出部１０３における「特性別」は、「予測可能」と「予測困難」の別を示している。本実施の形態における「予測可能」なフローは、過去からのトラヒック変動が少なく、将来のトラヒック需要が予測可能なフローであり、「予測困難」なフローは、突発的にトラヒック需要が急増し、将来のトラヒック需要が予測困難なフローである。

（ハードウェア構成例）
本実施の形態に係るフロー集約装置１００は、例えば、１つ又は複数のコンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、フロー集約装置１００が有する機能は、当該コンピュータに内蔵されるＣＰＵやメモリ、ハードディスクなどのハードウェア資源を用いて、フロー集約装置１００で実施される処理に対応するプログラムを実行することによって実現することが可能である。また、上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。

図５は、フロー集約装置１００をコンピュータで実現する場合における当該フロー集約装置１００のハードウェア構成例を示す図である。図５のフロー集約装置１００は、それぞれバスＢで相互に接続されているドライブ装置１５０、補助記憶装置１５２、メモリ装置１５３、ＣＰＵ１５４、インタフェース装置１５５、表示装置１５６、及び入力装置１５７等を有する。

フロー集約装置１００での処理を実現するプログラムは、例えば、ＣＤ−ＲＯＭ又はメモリカード等の記録媒体１５１によって提供される。プログラムを記憶した記録媒体１５１がドライブ装置１５０にセットされると、プログラムが記録媒体１５１からドライブ装置１５０を介して補助記憶装置１５２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１５１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１５２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。

メモリ装置１５３は、プログラムの起動指示があった場合に、補助記憶装置１５２からプログラムを読み出して格納する。ＣＰＵ１５４は、メモリ装置１５３に格納されたプログラムに従ってフロー集約装置１００に係る機能を実現する。インタフェース装置１５５は、ネットワークに接続するためのインタフェースとして用いられる。表示装置１５６はプログラムによるＧＵＩ（Graphical User Interface）等を表示する。入力装置１５７はキーボード及びマウス、ボタン、又はタッチパネル等で構成され、様々な操作指示を入力させるために用いられる。

（システムの全体動作例）
次に、システムの全体動作例として、イベント情報を活用したトラヒック制御の例を説明する。本実施の形態に係るシステムでは、以下のステップＳ１〜Ｓ６の手順がタイムステップ (単位時間) ごとに繰り返される。例えば、タイムステップが10分であれば、ある時刻（例えば12:00）で1回目の制御を行い、次の時刻（例えば12:10）で2回目の制御を行う、といったように以下の手順が繰り返される。

ステップＳ１）フロー集約装置１００におけるフローデータベース１０１（例：前述した特開2015-75896等に開示されている多次元フローデータベース）が、制御設定装置３００から入力されたトラヒック情報を、イベント情報に関連するイベントトラヒックと、イベント情報に関連しないそれ以外のトラヒック (以下、背景トラヒックと呼ぶ) に分離する。フローデータベース１０１は、イベント情報を特性別トラヒック需要算出部１０３に送信し、背景トラヒックのマイクロフローデータをマクロフロー生成部１０２に送信する。

ステップＳ２）マクロフロー生成部１０２は、例えば特許文献１に開示されているフロー集約手法を用いて、背景トラヒックのマイクロフローを、特性ごと（例：予測可能、予測困難）のマクロフローに集約し、特性ごとのマクロフローとマクロフローサイズを、特性別トラヒック需要計算部１０３に送る。

ステップＳ３）特性別トラヒック需要算出部１０３は、フローデータベース１０１から入力されたイベント情報と、マクロフロー生成部１０２から入力された背景トラヒックのマクロフロー情報とから、特性別のトラヒック需要を算出し、経路計算装置２００に送信する。本実施の形態における特性別トラヒック需要は、特性(予測可能又は予測困難)、時刻、発着ノード、発着ノード別トラヒック量の情報を有する。

ステップＳ４）経路計算装置２００により、経路計算を行う。経路計算装置２００は、経路計算の解 (送信ノードから受信ノードへの各リンクを経由するトラヒック分割比)、マクロフロー情報を制御設定装置３００に送信する。本実施の形態では、経路計算装置２００は、予測可能マクロフローの経路を計算し、その後、残余帯域に対して、予測困難マクロフローの経路を計算している。

ステップＳ５）制御設定装置３００は、全ての転送装置４００に対して、フローテーブルの更新を行う。

ステップＳ６）各転送装置４００は、フローテーブルに基づき、端末５００が発生させたトラヒックを転送する。

（特性別トラヒック需要の算出方法）
次に、特性別トラヒック需要算出部１０３により実行される特性別トラヒック需要の算出方法について詳細に説明する。

＜特性別トラヒック需要算出のための全体の処理手順＞
特性別トラヒック需要算出部１０３は、以下の手順を実行することで特性別トラヒック需要を算出する。

ステップＳ１１）フローデータベース１０１から、イベント情報を受け取る。

ステップＳ１２）マクロフロー生成部１０２から、背景トラヒックの特性別・発着ノード別マクロフロー情報を受け取る。

ステップＳ１３）イベントを予測可能に分類すべきか、予測困難に分類すべきかを判断し、イベントトラヒックの予測可能・予測困難トラヒックマトリックスを算出する。この算出方法の詳細については後述する。

特性別トラヒック需要算出部１０３は、イベント情報の予測が正確だと判断した場合、イベントマクロフローを予測可能マクロフローとして処理し、イベント情報の予測が不正確だと判断した場合、イベントマクロフローを予測困難マクロフローとして処理する。

ステップＳ１４）マクロフロー生成部１０２で算出した背景トラヒックの予測可能・予測困難トラヒックマトリックスと、イベントトラヒックの予測可能・予測困難トラヒックマトリックスの和をとり、全トラヒックの予測可能・予測困難トラヒックマトリックスを算出する。

ステップＳ１５）全トラヒックの予測可能・予測困難トラヒックマトリックスを経路計算装置２００に送信する。

以下、特性別トラヒック需要算出部１０３により実行される、イベントトラヒックの予測可能・予測困難トラヒックマトリックスの算出方法の例について説明する。まず、算出において使用される記号の定義を以下に示す。

＜記号の定義＞
−時刻:t∈T
−発着ノード:p,q
−イベント情報に関する定式化:

−時刻tにおける全トラヒック需要:

−背景トラヒック需要:

−背景トラヒック需要の平均:

−時刻t における予測可能マクロフローのトラヒックマトリックス:

−時刻tにおける予測困難マクロフローのトラヒックマトリックス:

なお、「イベント情報に関する定式化」に関して、「実際のイベントトラヒック需要」は、観測（トラヒック情報）から得られた情報であり、それ以外は、「イベント情報」として与えられる情報である。

また、「イベント情報に関する定式化」における「時刻tにおけるイベントトラヒック需要の予測値」、及びその「幅」に関して、tがイベント期間でなくても、当該予測値が入る。例えば、あるイベントeに対して、100±10Mbpsという予測がある場合、tに依らず、イベント開始前であっても、「イベントトラヒック需要の予測値」は100、その「幅」は10である。また、「実際のイベントトラヒック需要」については、観測値なので、tがイベント開始前であれば空欄（0と考えても良い）、tがイベント開始後であれば実測値（例えば、95Mbpsなど）が入力される。

「時刻tにおける全トラヒック需要」は、時刻ｔのトラヒック情報から得られる値である。

＜イベントトラヒックの予測可能・予測困難トラヒックマトリックスの算出手順＞
図６は、イベントトラヒックの予測可能・予測困難トラヒックマトリックスの算出のために、特性別トラヒック需要算出部１０３が実行する手順のアルゴリズムの例を示す。各行の意味は図示のとおりである。なお、イベントトラヒックの予測可能・予測困難トラヒックマトリックスの算出に用いられる背景トラヒックは、特性ごとに得られた背景トラヒックの合計（図３の１０２から１０３への線で渡される情報（特性ごとのマクロフロー情報）の合計）である。

なお、図６において、α、βは予め定めたパラメータである。また、第５行における例外マクロフローリスト(MacroFlow_List_of_Exeption)は、「*」が多すぎて、イベント情報からイベントトラヒックを背景トラヒックから適切に分離できないマクロフローを集めたリストである。例えば、ポート番号でイベントの対象を絞ることができない場合、送信先アドレスと宛先アドレスが両方「*」の場合、等を指す(例："*,*,*,*,*", "*,*,*,*,6", "*,*,80,*,*", …)。

なお、意味のない5-tupleの除外は、イベント情報を活用したトラヒック量の予測精度を向上させることに寄与する。例えば、イベントマクロフローを"*,*,*,*,*"と指定すると、背景トラヒック量が0になるため、特性別にイベントトラヒックを適切に分離することが困難になる。そこで、意味のない5-tupleを除外することで、あいまい過ぎるイベント情報を無視することができ、イベントにより発生するトラヒック需要の予測外れを防ぐことができ、経路制御の効率の劣化を防ぐことが可能となる。

図６に示すアルゴリズムに基づき特性別トラヒック需要算出部１０３が実行する処理手順を、図７のフローチャートを参照して説明する。以下の説明では、各ステップが、図６のどの行に対応するかを、ステップ番号の後に記載している。

まず、時刻ごと、発着ノードごと、イベントごとに処理を分割する（ステップＳ１０１、第２〜第４行）。

なお、「時刻ごと」に関して、例えば、タイムステップが10分で、現在時刻が12:00であれば、12:10~12:20の「イベント情報」に対して処理（イベントの分類）を実行する。また、現在時刻が12:10になったら、12:00に行った処理に従って制御を実行する。それと同時に12:20~12:30の「イベント情報」に対して処理を実行する。

また、タイムステップが10分の例で、時刻ごとに分割するとは、全てのイベント情報をT=0 (12:00-12:10のイベント情報)、T=1 (12:10-12:20のイベント情報)、…のように分割することを指す。

また、図６の第２行のfor each tのtは現在時刻（例：10分きざみ）を表し、例えば、t=12:00の場合、12:10-12:20の（各）イベント情報に対して、第５行以降の処理が実行される。

また、例えば、システムに入力されるイベント情報が、「13:00-14:00に100Mのトラヒックが発生」というものであった場合、「12:10-12:20のイベント情報」は、空(0)であり、「13:10-13:20のイベント情報」は、予測値（100M）になる。t（例：12:00）がイベント期間内かどうかの判断について、例えば、（分類対象の）「12:10-12:20のイベント情報」の（分割前の）イベントの期間が11:30-12:30であれば、tはイベント期間内であると判断される。

次に、イベントマクロフローが例外マクロフローリストに入っているか否かを判定し（ステップＳ１０２、第５行）、Ｙｅｓであればイベント情報を無視する（ステップＳ１１０、第６行）。

ステップＳ１０２の判定結果がＮｏの場合、tにおいてイベントが開始しているか否かを判定する（ステップＳ１０３、第８行、第１３行）。イベント開始前の場合、過去の背景トラヒックの平均と比して、イベントトラヒックの分散が大きいかどうか判定する（ステップＳ１０４、第９行）。

ステップＳ１０４の判定結果がＹｅｓの場合、イベントを予測困難に分類する（ステップＳ１０５、第１０行）。ステップＳ１０４の判定結果がＮｏの場合、イベントを予測可能に分類する（ステップＳ１０６、第１２行）。

ステップＳ１０３の判定により、イベント期間内である場合、イベントトラヒックの予測値と比して、実際のイベントトラヒックが大きいかどうかを判定する（ステップＳ１０７、第１４行）。

ステップＳ１０７の判定結果がＹｅｓの場合、イベントを予測困難に分類する（ステップＳ１０８、第１５行）。ステップＳ１０７の判定結果がＮｏの場合、イベントを予測可能に分類する（ステップＳ１０９、第１７行）。

そして、特性別トラヒック需要算出部１０３は、特性ごとに・発着ノードごとに、トラヒック需要を集計し、トラヒックマトリックスを算出する（ステップＳ１１１）。

図８に、上述した手法によるイベントトラヒックの分類例（イメージ）を示す。図８（ａ）は、背景トラヒックの平均と比して、イベントトラヒックの分散が小さいため、予測可能に分類される例を示す。図８（ｂ）は、背景トラヒックの平均と比して、イベントトラヒックの分散が大きいため、予測困難に分類される例を示す。

図８（ｃ）は、イベントトラヒックの予測値と比して、実際のイベントトラヒックが大きくなったため、ある時刻から、予測可能から予測困難に分類される例を示す。このように、イベントトラヒックの制御結果をフィードバックすることで、イベント情報の正しさを検証でき、イベント情報の予測外れによる輻輳を回避できる。

＜分類のための基準例＞
上述した特性別トラヒック需要算出部１０３が実行する手順における「背景トラヒックの平均」は、イベントトラヒックを予測可能な成分・予測困難な成分に分類するための基準の一例である。イベントトラヒックを予測可能な成分・予測困難な成分に分類するための基準はこれに限定されない。例えば、「背景トラヒックの分散」、「背景トラヒックの平均及び分散」、「予測可能トラヒックの平均及び分散」、「背景トラヒックの変動係数(C.V.)」、「予測可能トラヒックの変動係数(C.V.)」のいずれも基準として使用することができる。ここでの「予測可能トラヒック」とは、マクロフロー生成部１０２で生成される特性ごとのマクロフローのうちの、予測可能トラヒックに相当する。

上記のC.V.は以下のとおりである。

v_t:時刻t におけるトラヒック量
上記の基準を用いた場合でも、「背景トラヒックの平均」を用いた場合と同様にイベントトラヒックを分類することが可能である。

なお、「予測可能・予測困難」は、トラヒック分類の一例であり、これに限定されるわけではない。例えば、「通話・テキスト・動画」等、ユーザのアプリケーションによる分類、「固定・モバイル」等、ユーザの端末による分類も可能である。これらの場合で、DPI(Deep Packet Inspection)装置等を利用し、パケット情報を取得することで、「予測可能・予測困難」での分類と同様に分類することが可能である。

（経路計算装置２００が実行する数理最適化計算について）
以下、経路計算装置２００における経路計算の一例としての数理最適化計算について説明する。なお、ここでの計算は一例であり、これに限られるわけではない。

＜予測可能マクロフローに対する数理最適化モデル＞
予測可能マクロフローに対する数理最適化モデルは、多品種フロー問題により定式化される。多品種フロー問題による数理最適化モデルは以下のとおりである。

ネットワークは有効グラフG(V,E)で表現する。ここで、Vはノードの集合、Eはリンクの集合を表している。また、ノードi∈Vからノードj∈Vまでのリンクはlink(i,j)∈Eと表す。link(i,j)∈Eの使用可能な帯域の容量はc_ijと表す。

ノードpからノードqまでのトラヒック需要t_pqを表すトラヒック行列は、Q={t_pq}と表す。x_ij ^pqはリンク(i,j)を通過するトラヒック需要t_pqの通過割合を示し、ルーティング変数と呼ばれる。U_linkはネットワークの混雑割合を示しており、後述する式ではU_linkを最小化するようなルーティング変数の値を求めている。

本実施の形態で使用される多品種フロー問題と呼ばれる数理計画問題の例を図９の式(1.1)〜式(1.6)に示す。

式(1.1) はネットワークの混雑割合を最小化する目的関数を示しており、(1.2)〜(1.6) は制約条件である。式(1.2)及び式(1.3)はフロー保存則を示している。式(1.4)はリンク(i,j)を通過するトラヒックの総和がリンク容量×混雑割合を超えないことを示している。式(1.5)及び(1.6) はルーティング変数x_ij ^pqとネットワークの混雑割合U_linkは値域を示している。

経路計算装置２００は、上記の数理最適化計算を行うことで、予測可能マクロフローに対する経路を算出する。

＜予測困難マクロフローに対する数理最適化モデル＞
予測困難マクロフローに対する数理最適化モデルは、負荷分散フロー問題により定式化される。負荷分散フロー問題による数理最適化モデルは以下のとおりである。

ネットワークは有効グラフG(V,E)で表現する。ここで、Vはノードの集合、Eはリンクの集合を表している。また、ノードi∈Vからノードj∈Vまでのリンクはlink(i,j)∈Eと表す。link(i,j)∈Eの使用可能な帯域の容量はc_ijと表す。

h_equarityはノードpからノードqへのトラヒックの公平性を示す。x_ij ^pqはノードpからノードqへのリンク(i,j)を通過するトラヒック需要の通過割合を示し,
ルーティング変数と呼ばれる。ノードpからノードqへのトラヒックの通過割合は、トラヒックの公平性から決定する。後述する式(2.1)ではh_equarityの和を最小化するようなルーティング変数の値を求めている。すなわち、各ノードのペア(p, q)ごとにトラヒックの公平性を最大化している。

本実施の形態で使用される負荷分散フロー問題の数理計画問題の例を図１０の式(2.1)〜式(2.6)に示す。

式(2.1)は通過するトラヒックの公平性を最大化する(不公平性を最小化する)目的関数を示しており，(2.2)〜(2.6)は制約条件である。

式(2.2)及び式(2.3) はフロー保存則を示している。式(2.4)はリンク(i,j)を通過するトラヒックがリンク容量×トラヒックの公平性の割合を超えないことを示している。式(2.5)及び(2.6) はルーティング変数x_ij ^pqとネットワークの公平性h_equarityの値域を示している。

経路計算装置２００は、上記の数理最適化計算を行うことで、予測困難マクロフローに対する経路を算出する。

（実施の形態の効果）
イベント情報をトラヒック制御に活用することで、イベント等による突発的なトラヒック変動が発生した際にも、輻輳を回避しつつ高効率な経路制御を実現することができる。

また、イベント情報のヘッダをマクロフロー(任意の5-tupleの組合せ)で柔軟に指定することができるため、あいまいなイベント情報であっても経路制御に活用することができる。例えば、動画配信の情報から、どのユーザが(宛先アドレス)が動画を視聴するかを予測することは困難であるが、本技術では、宛先アドレスを任意という意味の「*」で指定することができるため、このようなあいまいなイベント情報であっても経路制御に活用することができる。

すなわち、従来技術では、トラヒック量の予測が常に正しく行われる前提で経路制御を行っているため、イベント情報を活用するべきかどうかをオペレータが判断する必要があり、そのため、従来技術では、あいまいなイベント情報は全て予測困難に分類され、経路制御の精度を上げることが困難であった。

それに対し、本実施の形態に係る技術では、イベントで発生するトラヒック量の予測値が幅を持たせて与えられた場合であっても、予測可能として分類するべきか、予測困難として分類するべきかを適切に判断することが可能である。あいまいなイベント情報を予測可能に分類することで、経路制御の精度を上げることが可能となる。なお、本実施の形態では、背景トラヒックの平均と比して、イベントトラヒックの分散が大きいかどうかを判断することで、あいまいさを許容している。図６で示したMacroFlow_List_Exceptionは、あいまい過ぎるイベント情報を除外することで、予測外れによる経路制御の精度の劣化を回避することに寄与している。

以上、説明したように、本実施の形態に係る技術により、外部情報としてイベント情報を活用し、トラヒック需要を高精度に予測するとともに、背景トラヒックに基づきイベントトラヒックを高精度に分類することを可能とし、短時間でかつ目標達成度が高い経路制御が実現される。

また、イベントトラヒックを基準値（例：背景トラヒックの分散）に基づいて分類することで、あいまいなイベント情報も外部情報として幅広く適用可能となる。更に、極端にあいまいなイベント情報の除外や、イベント発生後のイベントトラヒックと予測値の乖離に応じたイベント情報の再分類により、さらに高精度な予測が可能となる。

（実施の形態のまとめ）
以上、説明したように、本実施の形態により、ネットワークにおけるトラヒックの需要を予測するトラヒック需要予測装置であって、前記ネットワークから収集されたトラヒック情報から、イベント情報に関連しないトラヒックである背景トラヒックを取得する取得手段と、前記イベント情報におけるイベントトラヒックの予測値の分散と、前記背景トラヒックとを比較することにより、当該イベントトラヒックの特性を判定し、特性別のトラヒック需要を算出する特性別トラヒック需要算出手段とを備えることを特徴とするトラヒック需要予測装置が提供される。

前記特性別トラヒック需要算出手段は、前記イベント情報におけるイベントトラヒックの予測値と、実際のイベントトラヒックとを比較することにより、前記イベントトラヒックの特性を変更することとしてもよい。

前記特性は、予測可能又は予測困難であり、前記特性別トラヒック需要算出手段は、前記イベントトラヒックの予測値の分散と前記背景トラヒックとの比較に基づき、前記イベント情報におけるイベントトラヒックの予測が正確であると推定される場合に前記特性を予測可能とし、前記イベント情報におけるイベントトラヒックの予測が正確でないと推定される場合に前記特性を予測困難とすることとしてもよい。

なお、フロー集約装置１００は、トラヒック需要予測装置の例である。また、フローデータベース１０１及びマクロフロー生成部１０２は、取得手段の例である。また、特性別トラヒック需要算出部１０３は、特性別トラヒック需要算出手段の例である。

以上、本実施の形態について説明したが、本発明はかかる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。

１００ フロー集約装置
２００ 経路計算装置
３００ 制御設定装置
４０１〜４０３ 転送装置
５０１〜５０４ 端末
１０１ フローデータベース
１０２ マクロフロー生成部
１０３ 特性別トラヒック需要算出部
１５０ ドライブ装置
１５２ 補助記憶装置
１５３ メモリ装置
１５４ ＣＰＵ
１５５ インタフェース装置
１５６ 表示装置
１５７ 入力装置

Claims (5)

1. ネットワークにおけるトラヒックの需要を予測するトラヒック需要予測装置であって、
   前記ネットワークから収集されたトラヒック情報から、イベント情報に関連しないトラヒックである背景トラヒックを取得する取得手段と、
   前記イベント情報におけるイベントトラヒックの予測値の分散と、前記背景トラヒックの平均とを比較し、前記分散が前記背景トラヒックの平均よりも大きい場合、前記イベントトラヒックの特性を予測困難に分類し、前記分散が前記背景トラヒックの平均よりも小さい場合、前記イベントトラヒックの特性を予測可能に分類し、予測困難と予測可能のそれぞれについて、イベントトラヒック需要を集計することによりトラヒックマトリックスを算出する特性別トラヒック需要算出手段と
   を備えることを特徴とするトラヒック需要予測装置。
2. 前記特性別トラヒック需要算出手段は、前記イベント情報におけるイベントトラヒックの予測値と、実際のイベントトラヒックとを比較することにより、前記イベントトラヒックの特性を変更する
   ことを特徴とする請求項１に記載のトラヒック需要予測装置。
3. ネットワークにおけるトラヒックの需要を予測するトラヒック需要予測装置が実行するトラヒック需要予測方法であって、
   前記ネットワークから収集されたトラヒック情報から、イベント情報に関連しないトラヒックである背景トラヒックを取得する取得ステップと、
   前記イベント情報におけるイベントトラヒックの予測値の分散と、前記背景トラヒックの平均とを比較し、前記分散が前記背景トラヒックの平均よりも大きい場合、前記イベントトラヒックの特性を予測困難に分類し、前記分散が前記背景トラヒックの平均よりも小さい場合、前記イベントトラヒックの特性を予測可能に分類し、予測困難と予測可能のそれぞれについて、イベントトラヒック需要を集計することによりトラヒックマトリックスを算出する特性別トラヒック需要算出ステップと
   を備えることを特徴とするトラヒック需要予測方法。
4. 前記特性別トラヒック需要算出ステップにおいて、前記トラヒック需要予測装置は、前記イベント情報におけるイベントトラヒックの予測値と、実際のイベントトラヒックとを比較することにより、前記イベントトラヒックの特性を変更する
   ことを特徴とする請求項３に記載のトラヒック需要予測方法。
5. コンピュータを、請求項１又は２に記載のトラヒック需要予測装置における各手段として機能させるためのプログラム。

Images