(57)【特許請求の範囲】
【請求項１】
ネットワークの各リソースについて将来における予測使用推移データを格納する予測使用推移データ格納部から、受信した接続要求に関連する予測使用推移データを読み出す予測使用推移データ特定ステップと、
読み出した前記予測使用推移データに基づき、所定の条件を満たすリソースを選択する選択ステップと、
を含み、
読み出した前記予測使用推移データに基づき、トラフィック占有量が所定の値よりも大きい大量トラフィックの通信要求の到着を検出すると、
前記選択ステップが、
前記大量トラフィック以外の通信要求に対して、前記大量トラフィックの通信要求の到着に係る前記予測使用推移データに基づき、各リソースのコストを定め、当該コストの値が前記所定の条件を満たすリソースを選択するステップと、
前記大量トラフィックの通信要求に対して、ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての現在の使用状況データ又は静的な属性情報を用いて各リソースのコストを定め、当該コストの値が前記所定の条件を満たすリソースを選択するステップと、
を含み、コンピュータにより実行されるルーティング制御方法。
【請求項２】
前記選択ステップに応じて、前記接続要求に対応する条件付きネットワークトポロジ・グラフを生成するステップ又はネットワークトポロジ・グラフの中から前記接続要求に対応する経路を探索するステップをさらに含む請求項１記載のルーティング制御方法。
【請求項３】
前記選択ステップが、
読み出した前記予測使用推移データにおいて、前記接続要求に関連する期間内において最も厳しい予測使用状況を表す値を特定するステップ
をさらに含む請求項１記載のルーティング制御方法。
【請求項４】
ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての過去の使用状況データから、前記ネットワークの各リソースについて将来における予測使用推移データを生成し、前記予測使用推移データ格納部に格納する予測使用推移データ生成ステップ
をさらに含む請求項１記載のルーティング制御方法。
【請求項５】
前記予測使用推移データ格納部において、前記ネットワークの各リソースについて、前記予測使用推移データと当該予測使用推移データに関連するサーバの識別情報又はエッジ・ルータの識別情報とが格納されており、
前記予測使用推移データ特定ステップが、
少なくとも前記接続要求の接続先アドレスに応じて適用される前記予測使用推移データを特定する特定ステップ
を含む請求項１記載のルーティング制御方法。
【請求項６】
条件付きネットワークトポロジ・グラフを生成する場合に、
前記所定の条件が、前記予測使用推移データが使用率であれば前記接続要求に関連する期間内における使用率の最大値が閾値以下、前記予測使用推移データが空き帯域であれば前記接続要求に関連する期間内における空き帯域の最小値が閾値以上であるという条件を含む
請求項１記載のルーティング制御方法。
【請求項７】
条件付きネットワークトポロジ・グラフを生成する場合に、
前記所定の条件が、前記予測使用推移データから特定される現在の値と実際の現在の使用状況データの値との差又は当該差の時間積分値であるリンクコストが閾値内であるという条件を含む
請求項１記載のルーティング制御方法。
【請求項８】
経路探索する場合に、
前記所定の条件が、予測推移を考慮した最小遅延経路探索ならば、前記予測使用推移データにおける使用率から換算される遅延時間をコストとし、最小コスト経路を探索することを含む
請求項１記載のルーティング制御方法。
【請求項９】
経路探索する場合に、
前記所定の条件が、予測推移を考慮した最大安定経路探索ならば、前記予測使用推移データから導かれる現在のトラフィック値と実際の現在のトラフィック値の差、又は当該差の時間積分値をリンクコストとし、最小コスト経路を探索することを含む
請求項１記載のルーティング制御方法。
【請求項１０】
変動パターンデータ格納部に格納された、前記ネットワークの各リソースについて予め生成されている周期的な使用状況の変動パターンデータと、非周期的なイベント変動パターンデータと、長期変動パターンデータとのうち少なくともいずれかを用いて、前記ネットワークの各リソースについて、第１の予測使用推移データを生成するステップ
をさらに含む請求項１記載のルーティング制御方法。
【請求項１１】
変動パターンデータ格納部に格納された、前記ネットワークの各リソースについて予め生成されている周期的な使用状況の変動パターンデータ、あるいは、非周期的なイベント変動パターンデータに、長期変動パターンデータを積算するか、あるいは加算することにより、長期増加分を加味することを特長とする、前記ネットワークの各リソースについて、第１の予測使用推移データを生成するステップ
を含む請求項１記載のルーティング制御方法。
【請求項１２】
生成された前記第１の予測使用推移データを、ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての現在の使用状況データに合致するように修正して、第２の予測使用推移データを生成するステップ
をさらに含む請求項１０記載のルーティング制御方法。
【請求項１３】
生成された前記第１の予測使用推移データを、ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての現在の使用状況データに合致するように修正して第２の予測使用推移データを生成する際に、
ある時点における前記第１の予測使用推移データと現在の使用状況データの差を第１の予測推移データに加算するか、あるいは、ある時点における第１の予測使用推移データと現在の使用状況データの比率を第１の予測推移データに積算するステップ
をさらに含む請求項１２記載のルーティング制御方法。
【請求項１４】
生成された前記第２の予測使用推移データを、前記ネットワークの各リソースの物理的上限値に応じて修正して、第３の予測使用推移データを生成するステップ
をさらに含む請求項１２記載のルーティング制御方法。
【請求項１５】
生成された前記第２の予測使用推移データを、前記ネットワークの各リソースの物理的上限値に応じて修正して、第３の予測使用推移データを生成する際に、
第２の予測使用推移データの最大値がリソースの物理的上限値に一致するように第２の予測使用推移データを正規化する、あるいは、第２の予測使用推移データがリソースの物理的上限値を超えた時間帯だけ物理的上限値で処理する、又は第２の予測使用推移データがリソースの物理的上限値を超えた時間帯と超えたデータ量をその直後の時間帯に物理的上限値で処理する第２の予測使用推移データを正規化するステップ
をさらに含む請求項１４記載のルーティング制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおけるリソース使用推移の予測技術及びリソース使用推移の予測結果を用いたルーティング技術に関する。
【背景技術】
【０００２】
ＤＤｏＳアタック、不正侵入などネットワークを用いた様々な犯罪が増加し、その問題が深刻化する中、情報セキュリティの必要性が高まっている。ＤＤｏＳアタック、不正侵入などが行われている際にトラフィックの性質が変化することに着目し、トラフィックを観測することで異常を検知する方法が多数研究されている。例えば、「高トラフィック観測・分析法に関する技術調査  情報セキュリティ対策研究開発評価等事業」，独立行政法人情報処理推進機構，２００４年４月，15 情経第1632号などを参照のこと。
【０００３】
具体的には、攻撃事例の代表１２ケースを分析した結果では、悪意のあるトラフィックの存在下では、ＤＮＳ要求の遅延が２３０％増大し、Ｗｅｂアクセスへの遅延も３０％増大するとされる。例えば、Kun-chan Lan, Alefiya Hussain and Debojyoti Dutta, “The effect of malicious traffic on the network” in proceeding of PAM 2003, April 6-8, La Jolla 参照のこと。
【０００４】
また、ネットワークベースのAnomaly検知としては、"Review of Anomaly-based Network Intrusion Detection", Jonathan Werrett, 2003/05/26 に以下のようなアプローチが開示されている。すなわち、確率ベースアプローチとして、パケットのフィールドが取りうる値の確率を求め、確率値の低い、あるいは、新しい値を持つフィールドを含むパケットを異常とし、不正アクセスとして検出する。また、多変量アプローチとして、単位時間あたりのパケット数、セッション数など、多数の変数を入力にとり、その変数の確率を求め、不正アクセス検出を行う。さらに、状態ベースアプローチとして、セッションを再構築し、プロトコル、ＩＰ（Internet Protocol）、セッションの状態遷移を確率として求め、不正アクセス検出を行う。通常のセッションはＳＹＮから始まりＦＩＮで終わるが、これとは異なる場合が存在するようなケースを不正とするものである。
【０００５】
さらに、通信キャリアやＩＳＰ（Internet Service Provider）のネットワーク運用管理部門にとって、ネットワークの障害を早期に検知することがノンストップ稼動に不可欠な要素である。このようなネットワークの障害の原因をその障害原因固有の現象から推論する仕組みが検討されている。
【０００６】
また、今までトラフィック・エンジニアリング（ＴＥ）として、ネットワーク又はサーバの負荷に関する現在の状況に応じて、最適な経路を選択することを検討してきた。ネットワーク又はサーバの負荷に関する現在の状況は、ネットワーク・コンテキストの１つである。
【０００７】
あるＴＥの考え方においては、経路を選択するために、ネットワークの面的な広がりを活用して、ネットワークの能力を最大限に引き出すことを基本にしている。このような考え方は、例えば、D. Awduche, et al., “Overview and principles of Internet traffic engineering,” RFC3272, IETF, May 2002，M. Katoh, T. Soumiya, K. Nakamichi, K. Takashima, H. Yamada and A. Chugo, “A study of IP traffic engineering mechanisms,” ITG2002, Duisburg, Germany, Mar. 2002，A. Okamura, K. Nakamichi, H. Yamada and A. Chugo. “A QoS Control Method Cooperating with a Dynamic Balancing Mechanism”, APNOMS2003, Japan, September 2003，Hitoshi Yamada, Akiko Okamura, Akira Chugo and Masafumi Katoh “IP Network Control Architecture for Providing On-Demand QoS Guarantee Service” WTC2004(2004.9.11-16) などを参照のこと。
【０００８】
具体的には、ネットワークのある箇所に輻輳や障害が発生していても、ダイナミックに他の箇所へ迂回させることにより、ネットワークサービスの性能を維持する。また、ＱｏＳ保証用のネットワーク資源を確保する場合に経路やサーバを選択する際には、確保する資源が均等に分散するようにする。これにより、受け付けられる要求数は増え、ネットワークの能力を最大限に引き出せるようになる。このようにすれば、ユーザにとっては呼損にならず要求が受け付けられる確率が上がることになり、ネットワーク事業者にとってはサービス料金収入の増加を意味する。また、ネットワークを隅々まで利用することが２次元ＴＥの根本原理であるから、瞬時的な資源不足に対応して設備を新たに設置するような無駄な投資を回避する技術ともいえる。
【０００９】
また、ネットワークの平面的な拡がりを用いる２次元ＴＥの考え方は、ネットワークの空間的な拡がりを用いる３次元ＴＥへ拡張できる。ＧＭＰＬＳ（Generalized Multi-Protocol Label Switching）は、光波長パス、ＴＤＭ（Time Division Multiplexing）パス、ＭＰＬＳ（Multi-Protocol Label Switching）パスという様々なレイヤのパスを統一的に制御・管理することを狙っている。従って、ＭＰＬＳ網のトラフィック量が長期的に増加し、網全体の容量が不足しているような場合には２次元ＴＥでは限界に達する。このような場合、新たに別の光波長平面を活用すれば、溢れるはずのトラフィックをも吸収することが可能となり、複数の波長平面を考慮した最適経路探索やトラフィック分散により、ネットワークのロバストネスや可用性は更に向上する。このような技術については、Toshio Soumiya, Shinya Kano, Akira Chugo and Masafumi Katoh “Robust and Efficient Control Method for Multilayered GMPLS Networks” WTC2004(2004.9.11-16)，Chung-Fong Su and Hung-Ying Tyan “Multi-layer Traffic Engineering for OPEX Reduction in IP over WDM Networks WTC2004(2004.9.11-16) などを参照のこと。
【００１０】
さらに、ユーザの状況に応じてダイナミックにサービスの提供方法を変えるコンテキストアウェアサービス制御について最近注目が集まっている。例えば、加藤  正文、“ユビキタスネットワークの展開戦略−ネットワークとミドルウェアによる知識の活用−”、［online］、平成１６年６月２４日、ユビキタスネットワーキングフォーラム  ユビキタス戦略シンポジウム、インターネット＜ＵＲＬ：http://www.ubiquitous-forum.jp/documents/sympo20040624/index.html＞などを参照のこと。
【００１１】
更にネットワーク運用を通して得たノウハウや知識（ネットワーク・コンテキスト）を使いネットワーク制御に反映させるという提案も既に行われている。今井  和雄、“第４世代モバイルネットワークとユビキタスへの展開”、［online］、平成１６年７月２０日、電子情報通信学会  実時間指向ユビキタスネットワークワークショップ研究会(URON)、インターネット＜ＵＲＬ：http://www.ieice.org/cs/uron/workshop2004.html＞などを参照のこと。
【００１２】
また、ユーザの状況からユーザの意図を推論し、ユーザプロファイルを参照しながらネットワークへの要求条件を設定し、更に、サービス提供者のポリシー、ネットワーク運用者のポリシーを参照しながら、ネットワーク・コンテキストを用いて最適な経路を探索することを特徴とするネットワーク制御方式が提案されている。
【００１３】
さらに、特開２０００−２５３０５５号公報には、呼損の発生が少なく且つネットワークにおける負荷の少ない経路制御方法が開示されている。具体的には、資源予約要求の発生時、ルーティング・テーブル検索により経路選択を行うとともにアプリケーションに呼の継続時間の情報を生成させ、この情報を資源予約要求パケットの内部に格納して各ノードに転送させ、各ノードでは上記呼の継続時間に関する情報からネットワーク上の帯域 容量の変動の予測を行い、資源予約の際の経路選択にこの情報を反映させる処理を行うものである。しかし、本公報の技術は、ネットワークを利用するアプリケーション自身に呼の継続時間を申告させ、それに基づいてその呼を含めたネットワークの帯域容量の変動を予測するものである。従って、実際に呼が発生してからその呼が消滅するであろう保留時間内の帯域変動だけが考慮でき、その呼が発生する以前から将来のトラフィック推移を予測するものではない。仮にこの予測を基にネットワークリソースの最適化を図るにしても、短期間の推移だけが考慮されることになるので、最適化によるリソース効率の向上を狙うにしても限界がある。更に、予測をネットワークリソースの最適化に用いる方法については触れられていない。
【特許文献１】特開２０００−２５３０５５号公報
【非特許文献１】「高トラフィック観測・分析法に関する技術調査  情報セキュリティ対策研究開発評価等事業」，独立行政法人情報処理推進機構，２００４年４月，15 情経第1632号
【非特許文献２】Kun-chan Lan, Alefiya Hussain and Debojyoti Dutta, “The effect of malicious traffic on the network” in proceeding of PAM 2003, April 6-8, La Jolla
【非特許文献３】"Review of Anomaly-based Network Intrusion Detection", Jonathan Werrett, 2003/05/26
【非特許文献４】D. Awduche, et al., “Overview and principles of Internet traffic engineering,” RFC3272, IETF, May 2002.
【非特許文献５】M. Katoh, T. Soumiya, K. Nakamichi, K. Takashima, H. Yamada and A. Chugo, “A study of IP traffic engineering mechanisms,” ITG2002, Duisburg, Germany, Mar. 2002.
【非特許文献６】A. Okamura, K. Nakamichi, H. Yamada and A. Chugo. “A QoS Control Method Cooperating with a Dynamic Balancing Mechanism”, APNOMS2003, Japan, September 2003.
【非特許文献７】Hitoshi Yamada, Akiko Okamura, Akira Chugo and Masafumi Katoh “IP Network Control Architecture for Providing On-Demand QoS Guarantee Service” WTC2004(2004.9.11-16)
【非特許文献８】Toshio Soumiya, Shinya Kano, Akira Chugo and Masafumi Katoh “Robust and Efficient Control Method for Multilayered GMPLS Networks” WTC2004(2004.9.11-16)
【非特許文献９】Chung-Fong Su and Hung-Ying Tyan “Multi-layer Traffic Engineering for OPEX Reduction in IP over WDM Networks WTC2004(2004.9.11-16)
【非特許文献１０】加藤  正文、“ユビキタスネットワークの展開戦略−ネットワークとミドルウェアによる知識の活用−”、［online］、平成１６年６月２４日、ユビキタスネットワーキングフォーラム  ユビキタス戦略シンポジウム、インターネット＜ＵＲＬ：http://www.ubiquitous-forum.jp/documents/sympo20040624/index.html＞
【非特許文献１１】今井  和雄、“第４世代モバイルネットワークとユビキタスへの展開”、［online］、平成１６年７月２０日、電子情報通信学会  実時間指向ユビキタスネットワークワークショップ研究会(URON)、インターネット＜ＵＲＬ：http://www.ieice.org/cs/uron/workshop2004.html＞
【発明の開示】
【発明が解決しようとする課題】
【００１４】
ネットワークには本来多くの知識が存在する。例えば上位レイヤの情報を見て、メールのタイトルや情報の中身まで見て情報漏えいを発見することも検討されている。しかし、本願では、本来ネットワークが通常知りうる「レイヤ３パケットの量」「トラフィック量」から得られる知識を使うものとする。
【００１５】
これまでにもネットワーク運用を通して得た経験知はよく使われてきた。例えば、長期の需要増傾向から設備増設のタイミングを計るようにしている。また、イベントによる企画型輻輳が予想される場合には、キャッシュ機能をユーザ近辺に配置し、コアネットワークのトラフィックの負担を軽減するようにする。さらに、地震などの異常時には、発信規制をかける場合が多い。このように様々な対策が、人間であるエキスパートの知恵を通して行われている。しかし、定量的に、また動的に経験知を用いたルーティングを行ってはいない。
【００１６】
また、上で述べたように、トラフィックを観測し、障害や悪意のあるトラフィックの混在を検知する研究は色々となされているが、これらはオフラインでの解析を前提としており、単に形式知を得るためのツールとして利用することが想定されていただけである。
【００１７】
また、ＩＤＳ（Intrusion Detection System）／ＩＰＳ（Intrusion Prevention／Protection System）のように、突発的なトラフィックの立ち上がりや過去とのパターンの違いから不正侵入を検知する技術も開発されつつある。更に、不正と判断した場合に、遮断するようなリアクティブ制御の例もある。しかし、リアクティブで、しかもエンドポイントを守る制御に限定されている。すなわち、ネットワークが蓄えてきた知識を用い、あるサービス基準を満足するようにネットワーク全体を予防的に制御するようにはなっていない。
【００１８】
さらに、トラフィック・エンジニアリングはネットワーク資源の効率利用を目指しているが、現時点のトラフィックをベースに最適な資源配分をしている。すなわち、過去の運用を通して得た知識を活用してはいないので、その時瞬間の最適解を得ているにとどまっている。
【００１９】
また、コンテキストアウェアサービス制御について検討されている文献には、ネットワーク・コンテキストを利用するコンセプトや大まかな情報の流れは示されているが、実際にネットワーク・コンテキストをいかに収集し、どのようにネットワーク・コンテキストを活用するかは述べられていない。
【００２０】
従って本発明の目的は、ネットワーク・コンテキストに含まれる、ネットワーク・リソースの使用推移の新規な予測技術を提供することである。
【００２１】
また本発明の他の目的は、ネットワーク・リソースの予測使用推移に基づき適切なルーティングを可能とするための技術を提供することである。
【００２２】
本発明のさらに他の目的は、ネットワーク・リソースの予測使用推移を考慮したリソース割り当てを行い、リソース割り当て時だけではなく、長期にわたるリソースの使用効率を最大化するための技術を提供することである。
【００２３】
本発明のさらに他の目的は、エキスパートの経験知をネットワーク・コンテキストに変換し、ネットワーク運用を体系化・自動化するための技術を提供することである。
【００２４】
本発明のさらに他の目的は、人手に頼っていたネットワーク運用をシステム化することによってコストを削減し、トラフィック変動や異常に迅速に対応するための技術を提供することである。
【課題を解決するための手段】
【００２５】
本発明に係るルーティング制御方法は、ネットワークの各リソース（例えばルータ間のリンク、サーバなど）について将来における予測使用推移データ（トラフィック量、使用率、使用帯域、空き帯域など）を格納する予測使用推移データ格納部から、受信した接続要求に関連する予測使用推移データを読み出す予測使用推移データ特定ステップと、読み出した予測使用推移データに基づき、所定の条件を満たすリソースを選択する選択ステップとを含む。
【００２６】
このように予測使用推移データを用いることによって、例えばリソース使用率の将来的な時間変化に応じて、適切なリソースが特定されるようになり、より適切なルーティングが可能となる。例えば、所定時間後にトラフィック量が増加するリンクが存在する場合には現在空き帯域が多くあっても当該リンクを使用しないというような判断も可能となる。
【００２７】
基本的には、帯域や保留時間が大きい、すなわち大きなトラフィックの到着が予測できるときには、その大きなトラフィックに、最小コストの経路を割り当てる。このようにすれば、リソースの利用効率が向上する。具体的には、例えば、図２６に示すように、Ｎ個のノードが双方向リングで結合されたネットワークを考える。隣接するノード間を結ぶ経路は、１ホップの最短経路と、Ｎ−１ホップの迂回経路が存在する。ここで、図２７のように、まず小トラフィック（帯域Ｂa、保留時間ｈa）用のパス＃ａ設定要求が到着し、その直後に大トラフィック（帯域Ｂb、保留時間ｈb)用のパス＃ｂ設定要求が到着するとする。パス＃ｂの到着を予測しない場合、パス＃ａに最短経路を割り当て、パス＃ａにより最短経路が塞がっている間に要求されるパス＃ｂには迂回経路が割り当てられることになる。この場合のリソースの消費（使われる帯域の使われるリンク分の総和）はＢaｈa＋（Ｎ−１）Ｂｂｈbとなる。大トラフィック用のパス＃ｂの到着が予測できる場合、パス＃ｂに最短経路を割り当てるために、先に要求されたパス＃ａに迂回経路を割り当て、パス＃ｂの要求があった時にパス＃ｂに最短経路を割り当てることができる。この場合のリソースの消費（使われる帯域の使われるリンク分の総和）はＢbｈb＋（Ｎ−１）Ｂaｈaとなる。ここで、パス＃ｂのトラフィック量がパス＃ａのトラフィック量よりも格段に大きい場合、例えば＃ａが保留時間ｈa＝２分の電話で、＃ｂが保留時間ｈb＝２時間の映像配信だったら、長時間にわたり迂回経路を占有する前者の方が圧倒的に効率が悪くなる。極論してＢbｈb＞＞Ｂaｈaとし、Ｂaｈaが無視できるほど相対的に小さいとすると、リソースの消費は、大量トラフィックの到着を予測しない場合は（Ｎ−１）Ｂbｈb、予測する場合はそれに最短経路を割り当てるとＢbｈbとなり、予測する場合のリソース消費は１／（Ｎ−１）になる。このように将来のトラフィック推移を予測し、瞬間でなく長期の期間におけるリソースの利用効率の最適化を図ることができるようになる。
【００２８】
また、ネットワークデータ格納部に格納された、ネットワークの各リソースについての静的属性に関するデータを用いて所定の条件を満たすリソースを選択するステップと、ネットワークコンテキストデータ格納部に格納された、ネットワークの各リソースについての現在の使用状況データを用いて所定の条件を満たすリソースを選択するステップと、上記予測使用推移データ特定ステップ及び上記選択ステップとのうちいずれかを選択する方針選択ステップをさらに含むようにしてもよい。このように、リソース選択の手法を必要に応じて切り替えることによって、状況に応じた適切なリソース選択を行うことができるようになる。
【００２９】
さらに、上で述べた方針選択ステップが、接続要求に対応する条件付きネットワークトポロジ・グラフを生成する場合、又はネットワークトポロジ・グラフの中から接続要求に対応する経路を探索する場合に実行されるようにしてもよい。
【００３０】
また、上で述べたように、将来到着する大きなトラフィックの通信要求用に最短経路を空けておくには、それ以前に発生するそれ以外の通信要求に対して、その最短経路を選択しないようにすれば良い。そのためには、それ以外の通信要求に対して、将来大きなトラフィックが到着することを前提にしたリンクコストを基準に経路を選ぶようにすれば良い。
【００３１】
一般化すれば、本発明では、予測使用推移データに基づき、帯域又は保留時間が所定の値よりも大きい大量トラフィックの通信要求の到着を検出するステップをさらに含むようにし、上で述べた選択ステップが、大量トラフィック以外の通信要求に対して、大量トラフィックの通信要求の到着に係る予測使用推移データに基づき、各リソースのコストを定め、当該コストの値が所定の条件を満たすリソースを選択するステップと、大量トラフィックの通信要求に対して、ネットワークコンテキストデータ格納部に格納された、ネットワークの各リソースについての現在の使用状況データ又は静的な属性情報を用いて各リソースのコストを定め、当該コストの値が所定の条件を満たすリソースを選択するステップとふくむようにしてもよい。このような大量トラフィックの通信要求には、最小コストの経路が割り当てられるようになる。
【００３２】
また、上で述べた選択ステップが、読み出した予測使用推移データにおいて、接続要求に関連する期間内において最も厳しい予測使用状況を表す値を特定するステップを含むようにしてもよい。すなわち、ある瞬間ではなく、ある期間内におけるボトルネックを考慮するものである。
【００３３】
なお、変動パターンデータ格納部に格納された、ネットワークの各リソースについて予め生成されている周期的な使用状況の変動パターン・データと、非周期的なイベント変動パターン・データと、長期変動パターン・データとのうち少なくともいずれかを用いて、ネットワークの各リソースについて、第１の予測使用推移データを生成するステップを実行するようにしてもよい。第１の予測使用推移データを予測使用推移データとして用いることができる。
【００３４】
また、生成された第１の予測使用推移データを、ネットワークコンテキストデータ格納部に格納された、ネットワークの各リソースについての現在の使用状況データに合致するように修正して、第２の予測使用推移データを生成するステップをさらに実行するようにしてもよい。第２の予測使用推移データを予測使用推移データとして用いることができる。
【００３５】
さらに、生成された第２の予測使用推移データを、ネットワークの各リソースの物理的上限値に応じて修正して、第３の予測使用推移データを生成するステップをさらに含むようにしてもよい。第３の予測使用推移データを予測使用推移データとして用いることができる。
【００３６】
また、本発明においては、変動パターンデータ格納部に格納された、ネットワークの各リソースについて予め生成されている周期的な使用状況の変動パターンデータと、非周期的なイベント変動パターンデータと、長期変動パターンデータとのうち少なくともいずれかを用いて、ネットワークの各リソースについて、第１の予測使用推移データを生成するステップをさらに含むようにしてもよい。
【００３７】
なお、本方法をコンピュータに実行させるためのプログラムを作成することができ、このプログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等の記憶媒体又は記憶装置に格納される。また、ネットワークなどを介してデジタル信号として配信される場合もある。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【発明の効果】
【００３８】
本発明によれば、ネットワーク・コンテキストに含まれる、ネットワーク・リソースの使用推移を適切に予測することができるようになる。
【００３９】
また本発明の他の側面によれば、ネットワーク・リソースの予測使用推移に基づき適切なルーティングを可能となる。
【００４０】
本発明のさらに他の側面によれば、ネットワーク・リソースの予測使用推移を考慮したリソース割り当てを行い、リソース割り当て時だけではなく、長期にわたるリソースの使用効率を最大化することができるようになる。
【００４１】
本発明のさらに他の側面によれば、エキスパートの経験知をネットワーク・コンテキストに変換し、ネットワーク運用を体系化・自動化することができるようになる。
【００４２】
本発明のさらに他の側面によれば、人手に頼っていたネットワーク運用をシステム化することによってコストを削減し、トラフィック変動や異常に迅速に対応することができるようになる。
【発明を実施するための最良の形態】
【００４３】
Ａ．システム概要
図１を用いて本発明の一実施の形態に係るシステム概要を説明する。観測対象であり且つ制御対象であるネットワーク１には、多数のルータＲ及びゲートウェイＧＷなどが接続されている。また、ルータＲには、端末７、アプリケーションサーバ９なども接続されている。さらに、ネットワーク１には、ネットワーク制御サーバ５が接続されている。ネットワーク制御サーバ５は、ネットワーク・コンテキストに関連する処理を行うネットワークコンテキスト処理部５１と、端末７からの接続要求などに応答してルータＲ等に対して設定などを行うネットワーク制御部５３と、ネットワーク管理者などによって設定されている運用ポリシー格納部５５とを有する。
【００４４】
ネットワークコンテキスト処理部５１は、ネットワーク１からネットワーク・コンテキストであるトラフィック・データを収集するトラフィックデータ収集部５１１と、トラフィックデータ収集部５１１により収集されたトラフィック・データを格納するネットワークコンテキストＤＢ５１２と、ネットワークコンテキスト処理部５１の管理者をサポートしてトラフィック推移予測に用いるパターン・データを抽出する処理を行うパターン抽出部５１３と、パターン抽出部５１３等によって抽出されたトラフィック変動パターン・データを格納するトラフィック変動パターンデータ格納部５１４と、ネットワーク１におけるトラフィックを変動させるイベントの予定などのデータを格納するイベントデータ格納部５１８と、ネットワーク１のトポロジグラフについてのデータ（リンク接続構成、サーバ能力、リンクの物理的容量、デフォルト・コストなど）を格納するネットワークトポロジデータ格納部５１９と、トラフィック変動パターンデータ格納部５１４とネットワークコンテキストＤＢ５１２とイベントデータ格納部５１８とネットワークトポロジデータ格納部５１９とに格納されたデータを用いてトラフィック推移予測を実施するトラフィック推移予測部５１５と、トラフィック推移予測部５１５の処理結果であるトラフィック推移予測結果を格納するトラフィック推移予測結果格納部５１６と、ネットワーク制御部５３からの要求に応答してトラフィック推移予測結果格納部５１６と運用ポリシー格納部５５とネットワークトポロジデータ格納部５１９とネットワークコンテキストＤＢ５１２とに格納されたデータとを用いて最小コスト経路探索処理を実施し、ネットワーク制御部５３に経路データなどを出力する最小コスト経路探索処理部５１７とを有する。
【００４５】
ネットワーク制御部５３は、端末７からの接続要求などをルータＲなどから受信し、ネットワークコンテキスト処理部５１の最小コスト経路探索処理部５１７に経路探索要求を出力する要求受信部５３１と、最小コスト経路探索処理部５１７から受信した経路データなどに基づきＱｏＳ制御及びリソース割当てなどに必要な設定をルータＲ等に実施する設定処理部５３３とを有する。
【００４６】
ネットワーク制御サーバ５の処理の詳細については後に述べる。
【００４７】
Ｂ．ネットワーク・トラフィックの推移予測
上でも述べたが、トラフィックデータ収集部５１１は、随時ルータＲ及びサーバから受信又は送信若しくは受信及び送信データ量又は同パケット数などのトラフィック・データを収集し、ネットワークコンテキストＤＢ５１２に蓄積する。ネットワークコンテキストＤＢ５１２に蓄積されたトラフィック・データに基づき、パターン抽出部５１３は、長期的な傾向、１日、１週間、１月及び１年など周期的な変動パターンなどを抽出すると共に、ネットワーク制御サーバ５の管理者による、ネットワーク・トラフィックを変動させるイベントに関する入力を受け付けて、各種イベントにおける変動パターンを特定する。ネットワーク制御サーバ５の管理者によりネットワーク・トラフィックの変動パターンのデータが直接入力される場合もある。トラフィック変動パターンデータ格納部５１４には、長期的な傾向を表す変動パターン、周期的な変動パターン、各種イベントにおける変動パターンなど、時系列のトラフィック量のデータを保持する。
【００４８】
図２（ａ）乃至（ｃ）に、変動パターンの一例を示す。例えば、長期的な傾向を表す変動パターンは、例えば図２（ａ）に示すような直線Ｆ(t)又は曲線である。図２（ａ）においては、縦軸はトラフィック増加率（場合によっては増加量）を表し、横軸は時間を表しており、Ｆ(t)＝ｋｔ＋１（ｋは定数）である。
【００４９】
長期的な傾向を表す変動パターンの適用態様については、長期的な傾向を表す変動パターン以外の過去の要素から求められるトラフィック量Ｘに対してａＦ(t)Ｘで表される積算型と、Ｘ＋ｂＦ(t)で表される加算型が存在する。積算型は、全体のトラフィック量がＦ(t)倍になっているならば、ある過去の事象から生じたトラフィック量ＸもＦ(t)倍となるという考え方に基づく。なおａは、Ｆ(t)の調整係数であり、Ｆ(t)以上にトラフィック量を増加すべきならば１以上の値を採用し、Ｆ(t)より抑制されるべきならば１未満の値を採用する。加算型は、ある過去の事象から生じたトラフィック量そのものは全体のトラフィック量が増加してもあまり変らないという考え方に基づく。そして本実施の形態では、係数ｂによって表されるその事象以外のトラフィック量がＦ(t)倍されて加算されるものとする。
【００５０】
また、周期的な変動パターンとしては、図２（ｂ）に示すように、周期Ｔn毎に同じ波形を繰り返す曲線Ｇ(t)＝Ｇn（ｔ＋ｍＴn）＝Ｇn(t)（ｍは整数）である。周期Ｔnは、上で述べたように１日（２４時間）（Ｔ1）、１週間（Ｔ2）、１月（Ｔ3）、１年（Ｔ4）などである。なお、図２（ｂ）では、縦軸はトラフィック量を表し、横軸は時間を表す。また、各種イベントにおける変動パターンは、例えば図２（ｃ）に示すように、任意の波形を有する曲線Ｈ(t)である。なお、図２（ｃ）では、縦軸はトラフィック量を表し、横軸は時間を表す。曲線Ｈ(t)は、例えばあるサーバから人気プログラムが公開された場合、新着着信メロディーの配信が開始された場合、人気チケット予約販売が開始された場合、人気番組の配信が開始された場合などにおけるネットワーク・トラフィックの変動パターンを表している。本実施の形態では、曲線Ｈ(t)としては、ネットワーク・トラフィックの変動とその原因とを対応付けることができるものを取り扱い、トラフィック変動パターンデータ格納部５１４には、イベントの属性と共に変動パターンのデータが登録されている。
【００５１】
このような前提の下、トラフィック推移予測部５１５は、以下のような処理を実施する。まず、トラフィック変動パターンデータ格納部５１４から、参照すべきトラフィック変動パターンのデータを取得する（図３：ステップＳ１）。参照すべきトラフィック変動パターンのデータは、トラフィック推移予測に係るリンク等についての周期的変動パターンのデータ、当該リンク等に関連する長期的な傾向を表す変動パターンのデータ、及び推移予測の期間中に存在し且つ当該リンク等に関連するイベント（イベントデータ格納部５１８に格納されているもの）についての変動パターンのデータを含む。
【００５２】
また、ネットワークコンテキストＤＢ５１２から、トラフィック推移予測に係るリンク等の現在のトラフィック・データを取得する（ステップＳ３）。
【００５３】
そして、長期的な傾向を考慮すべきか判断する（ステップＳ５）。例えば、長期的な傾向を考慮すべきか否かは、例えばステップＳ１で取得されたイベントについての変動パターンの基となるイベントが、予め定められた時期より前に発生している場合など、予め定められた条件を満たすトラフィック推移予測であるか否かで決定される。現在、インターネットのトラフィックは年率２倍以上の増加率で伸び続けている。従って、参照しようとしているイベントが１年前のものならば、インターネットのトラフィックの増加傾向を無視して次回のイベント用のリソースを準備するのでは不十分である。前回のイベントに対するトラフィックＨ(t)の２倍のトラフィックが発生すると考え、リソースを確保する方が自然である。
【００５４】
長期的な傾向を考慮すべきであると判断された場合には、長期的な傾向を表す変動パターンＦ(t)、周期的な変動パターンＧ(t)又はイベントについての変動パターンＨ(t)若しくはその両方を用いて１次予測関数Ｐ(t)を合成する（ステップＳ７）。なお、ステップＳ７の後にはステップＳ１１に移行する。
【００５５】
例えばイベントについての変動パターンＨ(t)に長期的な傾向を適用する場合を、図４（ａ）乃至（ｃ）を用いて説明する。例えば図４（ａ）に示すような長期的な傾向を表す変動パターンＦ(t)及びイベントについての変動パターンＨ(t)を考慮するものとする。（１）積算型の場合には、１次予測関数Ｐ(t)＝ａＦ(t)Ｈ(t)となり、図４（ｂ）に示すような波形（実線）がトラフィック推移予測結果となる。これはＦ(t)で増加するトラフィック全体が、そのイベントに関わるケースを想定している。また、（２）加算型の場合には、１次予測関数Ｐ(t)＝Ｈ(t)＋ｂＦ(t)となり、図４（ｃ）に示すような波形（実線）がトラフィック推移予測結果となる。これは、Ｆ(t)で増加するトラフィック全体とは無関係に、そのイベントに関わるトラフィックはＨ(t)に従うケースを想定している。図４（ｂ）及び（ｃ）において点線は元のＨ(t)である。イベントの発生によるトラフィック増加Ｈ(t)が、長期的な傾向を表す変動パターンＦ(t)の影響をあまり受けないならば、ａ＜１としたり、ｂ＜１として計算してもよい。
【００５６】
また周期的な変動パターンＧ(t)に長期的傾向を適用する場合を、図５（ａ）乃至（ｃ）を用いて説明する。例えば図５（ａ）に示すような長期的な傾向を表す変動パターンＦ(t)及び周期的な変動パターンＧ(t)を考慮するものとする。（１）積算型の場合には、１次予測関数Ｐ(t)＝ａＦ(t)Ｇ(t)となり、図５（ｂ）に示すような波形（実線）がトラフィック推移予測となる。なお、図５（ｂ）において点線はＧ(t)を表す。また、（２）加算型の場合には、１次予測関数Ｐ(t)＝Ｇ(t)＋ｂＦ(t)となり、図５（ｃ）に示すような波形（実線）がトラフィック推移予測となる。なお、図５（ｃ）において点線はＧ(t)を表し、細点線はＦ(t)を表す。例えば１日又は一週間といったように予測期間が短い場合には、長期的な傾向を表す変動パターンＦ(t)については影響を受けないものとして、ａ＝１としたり、ｂ＜＜１といった設定を行うようにしても良い。
【００５７】
なお、長期的な傾向を表す変動パターンＦ(t)、周期的な変動パターンＧ(t)及びイベントについての変動パターンＨ(t)を全て組み合わせる態様については図示していないが、上で述べたものと同様に組み合わせることができる。
【００５８】
一方、長期的な傾向を考慮する必要はないと判断された場合には、周期的な変動パターンＧ(t)、イベントについての変動パターンＨ(t)又はその両方を用いて１次予測関数Ｐ(t)を合成する（ステップＳ９）。なお、ステップＳ９の後にはステップＳ１１に移行する。
【００５９】
具体的には、イベントについての変動パターンＨ(t)については、そのままＨ(t)をトラフィック推移予測として用いるか、又はＨ(t)について通常のトラフィック量ｘに対してｈ倍という定義が行われている場合には、ｈｘをトラフィック推移予測とする。また、周期的な変動パターンＧ(t)については、そのままＧ(t)をトラフィック推移予測として用いる。場合によっては、イベントについての変動パターンＨ(t)と周期的な変動パターンＧ(t)との加算等により組み合わせるようにしても良い。
【００６０】
その後、現在のトラフィック量を考慮するか否かを判断する（ステップＳ１１）。例えば１次予測関数Ｐ(t)を合成する際に積算型を採用した場合には現在のトラフィック量とは無関係に１次予測関数Ｐ(t)は変化するので、この場合には考慮しないと判断する。
【００６１】
現在のトラフィック量を考慮すると判断した場合には、以下の観点にて１次予測関数Ｐ(t)を修正する。すなわち、１次予測関数Ｐ(t)によって以降のトラフィック量を推定することになるが、現時点のトラフィック量Ｕ(0)と、１次予測関数Ｐ(t)における現時点のトラフィック量Ｐ(0)とが一致しているとは限らない。そこでＵ(0)＝２次予測関数値Ｑ(0)となるような２次予測関数Ｑ(t)を生成する。具体的には、現在のトラフィック量Ｕ(0)−１次予測関数値Ｐ(0)又はＵ(0)／Ｐ(0)を算出する（ステップＳ１３）。なお、ステップＳ１３の計算結果を用いた付随的な処理フローについては端子Ａ以降に図８を用いて後に説明する。
【００６２】
そして、現時点のトラフィック量Ｕ(0)と１次予測関数値Ｐ(0)との関係（Ｕ(0)−Ｐ(0)又はＵ(0)／Ｐ(0)）をＰ(t)に反映して２次予測関数Ｑ(t)を生成する（ステップＳ１５）。この処理には、Ｕ(0)−Ｐ(0)をＰ(t)に加える予実差加算型の反映方法と、Ｕ(0)／Ｐ(0)をＰ(t)に乗ずる予実比等倍型の反映方法とがある。予実差加算型の反映方法の場合、２次予測関数Ｑ(t)＝Ｐ(t)＋Ｕ(0)−Ｐ(0)として、Ｑ(0)＝Ｕ(0)を実現する。例えば図６（ａ）に示すように、Ｐ(0)＜Ｕ(0)の場合には、Ｐ(t)が上方に平行移動される。また、予実比等倍型の反映方法の場合、２次予測関数Ｑ(t)＝Ｐ(t)Ｕ(0)／Ｐ(0)として、Ｑ(0)＝Ｕ(0)を実現する。例えば図６（ｂ）に示すように、Ｐ(0)＜Ｕ(0)の場合には、Ｐ(t)が増加するように変形される。その後処理はステップＳ１９に移行する。
【００６３】
一方、現在のトラフィック量を考慮しないと判断した場合には、Ｐ(t)をそのまま２次予測関数Ｑ(t)に採用する（ステップＳ１７）。その後ステップＳ１９に移行する。
【００６４】
そして、２次予測関数Ｑ(t)に対して物理的な制限を考慮して調整する必要があるか判断する（ステップＳ１９）。これまでの処理で過去のトラフィック変動から今後のトラフィック推移を推定且つ調整しているが、Ｑ(t)が実際には取り得ない値となることも考えられる。トラフィック需要そのものの予測であれば取り得ない値というのは存在しないが、２次予測関数Ｑ(t)がリンクの使用帯域幅、サーバの使用能力値といったものの推移予測である場合にはリンクの物理的な帯域幅、サーバの最大能力値といったものに制限される。
【００６５】
ステップＳ１９では、予め物理的な制限を考慮して調整するか否かを設定しておき、当該設定に従って物理的な制限を考慮して調整するか否かを判断する。結果的に調整しないのと同じ結果を得ることもある。これはトラフィック量がＦ(t)という増加率で長期的に増加するならば、ノード（例えばルータ）、リンク（伝送路）、及びサーバなどの装置もＦ(t)という割合で増強されるはずであるという考え方に基づく。すなわち使用率で考える場合には、積算型で長期的な傾向を考慮したならば物理的な上限値Ｂu（分母）についても増加しているためトラフィック量（分子）が増加したとしても使用率が１００％以上にはならないというものである。この場合には、２次予測関数Ｑ(t)を３次予測関数Ｒ(t)に採用する（ステップＳ２３）。そして、３次予測関数Ｒ(t)のデータをトラフィック推移予測結果格納部５１６に格納する。
【００６６】
一方、物理的な制限を考慮して調整が必要であると判断された場合には、２次予測関数Ｑ(t)を物理的な制限を考慮して調整し、３次予測関数Ｒ(t)を生成する（ステップＳ２１）。生成した３次予測関数Ｒ(t)のデータをトラフィック推移予測結果格納部５１６に格納する。調整については以下のような手法がある。すなわち、（１）上限値Ｂuを超える部分を切り捨てるように調整する方法、（２）超過分を時間シフトさせるように調整する方法、（３）全体的に上限値Ｂuを下回るように調整する方法である。
【００６７】
例えば図７（ａ）に示すように、トラフィック量の上限値Ｂuを超える部分を有する２次予測関数Ｑ(t)を用いて説明する。（１）の調整方法を適用した場合には、図７（ｂ）に示すように、上限値Ｂuを超える部分はそのまま呼損となり拒否されるので、上限値Ｂuを超える部分を切り捨てて上限値Ｂuと同値に設定し、それ以外の部分については２次予測関数Ｑ(t)をそのまま用いて３次予測関数Ｒ(t)を生成する。式で表せば、以下のようになる。
Ｒ(t)＝Ｂu      （Ｑ(t)＞Ｂu）
Ｒ(t)＝Ｑ(t)    （Ｑ(t)≦Ｂu）
【００６８】
（２）の調整方法を適用した場合には、上限値Ｂuを超える部分は呼損となり拒否されるが、全てがリトライされて全てが受け付けられるまで上限値Ｂuで処理され続け、その結果上限値Ｂuで処理される時間が長くなる。図７（ｃ）に示すように、上限値Ｂuを超える部分の面積Ａと同じトラフィック量が上限値Ｂu未満の部分を使って処理される。
【００６９】
（３）の調整方法は、Ｑ(t)の最大値が上限値Ｂuに一致するように正規化する方法である。これを適用した場合には、上限値Ｂuと２次予測関数Ｑ(t)の最大値との比Ｂu／max｛Ｑ(t)｝を算出し、３次予測関数Ｒ(t)＝Ｑ(t)Ｂu／max｛Ｑ(t)｝と設定する。Ｂu−max｛Ｑ(t)｝を算出し、３次予測関数Ｒ(t)＝Ｑ(t)＋Ｂu−max｛Ｑ(t)｝とするようにしてもよい。
【００７０】
このような処理を行うことにより、トラフィック推移予測を行うことができるようになる。
【００７１】
なお、以上述べた処理は簡略化した基本的な考え方を述べたものであって、以下で説明するトラフィック推移予測を用いたルーティングを実施するためには、各リンク等につき、時間毎に適用対象のエッジ・ルータ又はサーバにトラフィック推定量等が対応付けられる。
【００７２】
なお、図３の端子Ａ以降の処理を図８を用いて説明しておく。まず、Ｕ(0)−Ｐ(0)又はＵ(0)／Ｐ(0)が予め定められた閾値以上であるか判断する（ステップＳ２５）。閾値未満であれば、特別な処理を行わないで端子Ｂを介して処理を終了する。閾値未満であれば、実際のトラフィックがトラフィック推移予測に従っている、すなわち、状態が安定しており、必要があれば「安定」を表すフラグなどをトラフィック推移予測結果格納部５１６に設定する。一方、閾値以上であれば、実際のトラフィックがトラフィック推移予測に従っていない、すなわちＤｏＳ（Deniel of Service）攻撃を受けていたり、不正侵入されていたり、障害が発生するなど、予測できない状況が発生しており、トラフィックが予測から大きくずれていると解釈する。この時、トラフィック推移予測の対象は不安定化しているものとして、トラフィック推移予測結果格納部５１６において、トラフィック推移予測の対象に不安定フラグをセットする（ステップＳ２７）。このような不安定フラグに応じて、トラフィック推移予測の対象に高いコストを割り当てるようにすれば、最小コストのリソースを選択することが、安定したリソースを選択したことになる。なお、フラグではなく、Ｕ(0)−Ｐ(0)又はＵ(0)／Ｐ(0)に応じた不安定指数を設定するようにしてもよい。
【００７３】
実際のトラフィックとトラフィック推移予測との差を閾値と比較するに当たり、一回の閾値判定に限る必要はない。瞬間で判定するのではなく、長期的に安定性を調べる方法もある。数回の測定で、ある割合以上で閾値を超える場合に不安定であるとし、閾値を超えた割合をコストに設定してもよい。
【００７４】
このようにコストを設定すると、コストのある値以下のリンクやサーバだけを抜き出して条件付きネットワークトポロジ・グラフを作成するならば、安定したリンクとサーバだけが残ることになる。また、コストの和が小さい経路を選択すれば、最も安定したリソースを使った経路で通信することができるようになる。この方法は、安定したリンクやサーバや経路を選択することを可能にする他、次のような狙いもある。このコストが大きい不安定なリンクやサーバや経路が選択されにくくなるということは、安定度を求めているものに限定されるが、新たな要求に対してにそれらが使われなくなる為、既にそれらのリソースを使っているコネクションやパスが終了するにつれ、トラフィックが減少し、実際のトラフィックがトラフィック推移予測と合うようになる。すなわち、不安定なリンクやサーバに加わるトラフィックを間接的に規制したことになる。
【００７５】
上で述べた例では、実際のトラフィックがトラフィック推移予測の差を不安定の程度とみなし、それをリンクコストに反映させて安定な経路を探索するルーティングに用いたが、図３０及び図３１に示すような制御を行うようにしても良い。具体的には、例えば図８の端子Ａの後に、Ｕ(0)−Ｐ(0)が閾値以上に、ある割合以上でなっているか判断する（ステップＳ１０１）。Ｕ(0)−Ｐ(0)が閾値以上に、ある割合以上でなっているわけではない場合には、安定と判断して端子Ｂを介して処理を終了する（ステップＳ１０３）。一方、Ｕ(0)−Ｐ(0)が閾値以上に、ある割合以上でなっている場合には、不安定と判断して（ステップＳ１０５）、Ｕ(0)−Ｐ(0)などを安定度を表すコストに反映する（ステップＳ１０７）。そして、直接的に制御を行わない場合には（ステップＳ１０９：Ｎｏルート）、端子Ｂを介して処理を終了する。一方、直接的に制御を行う場合には（ステップＳ１０９：Ｙｅｓルート）、新たな要求を強制的に規制するか判断する（ステップＳ１１１）。例えば強制的な規制を行うような設定がなされているか否かによって判断する。新たな要求を強制的に規制するという場合には、アドミッション制御として、不安定なリソースを使用する要求を強制的に拒絶する（ステップＳ１１３）。このように、不安定な状態が発生したら、安定状態に戻るまで、そのリソースを使う新たな要求を強制的に受け付けないようにしてもよい。ステップＳ１１１で、新たな要求を強制的に規制しないと判断された場合又はステップＳ１１３の後に、処理は端子Ｃを介して図３１の処理に移行する。
【００７６】
図３１の処理の説明に移行して、不安定なリソース上のトラフィックを排除するか判断する（ステップＳ１１５）。例えば不安定なリソース上のトラフィックを排除するような設定がなされているか否かによって判断する。不安定なリソース上のトラフィックを排除しないと判断された場合には端子Ａを介して図３０のステップＳ１０１に戻る。一方、不安定なリソース上のトラフィックを排除すると判断された場合には、予め定められたルールに従って排除対象（トラフィック量が多い、非重要呼など）を決定する（ステップＳ１１７）。そして、パスレベル（コネクションやパス）での切断が必要であるか否かを所定の基準に基づき判断し（ステップＳ１１９）、必要と判断された場合には安定状態になるまで強制切断するためパス切断指示を行う（ステップＳ１２１）。パスレベルでの切断が不要であると判断された場合又はステップＳ１２１の後に、パスレベルでの切替えが必要か否かを所定の基準に基づき判断する（ステップＳ１２３）。不安定なコネクションやパスからこれらに代わるコネクションやパスにトラフィックを切替える方がよい場合には、パス切替指示を行う（ステップＳ１２５）。さらに、パスレベルでの切替えが不要と判断された場合又はステップＳ１２５の後に、パケット破棄が必要であるか否かを所定の基準で判断する（ステップＳ１２７）。コネクションやパスを切断せずに、それらに流れるパケットをノードで破棄する必要がある場合には、パケット廃棄指示を行う（ステップＳ１２９）。そして端子Ａを介して図３０のステップＳ１０１に戻る。パケット廃棄が不要であれば端子Ａを介して図３０のステップＳ１０１に戻る。
【００７７】
強制的に切断するコネクションやパスの選択方法については、予め設定しておいた優先度、例えば事前登録された発着信者間の通信や重要呼を残し、それ以外の通信で使われるコネクションやパスを強制切断する方法がある。他には、使用している帯域が大きいものから順に、実際のトラフィックとトラフィック推移予測の差が、ある範囲内に収まるように選択する方法もある。
【００７８】
以上述べたような処理を行えば、例えばイベントがある時のトラフィックの集中傾向や周期的なトラフィック変動を知識として持つことが可能になる。すなわち、次に同じようなイベントが行われる際にトラフィックの集中具合が予測でき、これに備えた資源割り当てを行うことで、ネットワークの資源利用効率が上がり、多くの要求に対応でき、機会損失を防ぐことができるようになる。さらに、無駄な設備増設を回避することができる。このような可用性は、間接的に地球環境配慮へつながる。
【００７９】
また、過去の知識から推論したトラフィック量と大きな差が生じた時には、何らかの異常が発生していると考え、この傾向にあるリンクやサーバに高いコスト値を割り当て、このようなコスト値に基づき最小コスト経路を探索すれば、安定性・安全性の高い経路を選択できるようになる。
【００８０】
Ｃ．トラフィック推移予測を利用した経路制御
本実施の形態においては、トラフィック推移予測の結果を用いて経路制御を行う。まず、図９乃至図２１を用いてその概要について説明しておく。
【００８１】
図９（ａ）に示すように、ノードＶとノードＸとを接続するリンクａと、ノードＸとノードＹとを接続するリンクｄと、ノードＸとノードＺとを接続するリンクｂと、ノードＹとノードＺとを接続するリンクｅと、ノードＺとノードＷとを接続するリンクｃとが存在する状態を想定する。この時、最初にノードＶからノードＷへの接続要求を受信すると、従来であれば、その時点における最小コスト経路である、リンクａ、リンクｂ及びリンクｃを使用するようなパス（１）を当該接続要求に割り当てる。その後、ノードＸからノードＺへの接続要求を受信した際には、既にリンクｂが用いられているので、最初の接続要求を受信した時よりもリンクｂについてのコストは上がってしまっており、後の接続要求にはリンクｄ及びリンクｅを使用するようなパス（２）が割り当てられてしまう。しかしながら、後の接続要求で使用するトラフィック量が多い場合、例えば保留時間が長いトラフィックがパス（２）のような迂回経路を占有することは、その間、他のトラフィックがこの経路を構成する２つのリンクを利用できなくなるため、ネットワーク全体の利用効率からして好ましくない。
【００８２】
あるノード間のある時間帯にトラフィック需要が集中することが予測できる場合、その大量のトラフィック需要に最短経路を割り当てるようにすることがネットワーク全体の利用効率からして好ましい。大量のトラフィック需要に最短経路を割り当てるようにするためには、その集中が始まる時刻の前のある時間帯から、そのノード間以外のトラフィックにはその最短経路を割り当てないようにする。すなわち、そのノード間以外のトラフィックに対して、最短経路上のリンクのコストが高く見えるようにすればよい。
【００８３】
具体的には、トラフィック推移予測から、ノードＸからノードＺへ大量のトラフィックが発生することが分かっていれば、図９（ｂ）に示すように、最初の接続要求に対しては、ノードＸからノードＺへのリンクｂを割り当てないようにリンクｂのコストを高くしておき、リンクａ、リンクｄ、リンクｅ及びリンクｃを含むパス（３）を割り当てる。一方、後の接続要求は、トラフィック推移予測で予測した大量トラフィックそのものであるから、当該後の接続要求には、現時点におけるコストに従ってリンクｂからなるパス（４）を割り当てる。このようにすれば、ネットワーク全体の利用効率が向上してリソースの有効利用が図られる。
【００８４】
ネットワーク全体の利用効率については、図１０を用いて説明する。ノードがＸ、Ｙ及びＺしかないとして、図１０において発着ノードの列及び経路の列にはノードの全ての組み合わせ及びそのための経路が示されている。そして、トラフィック推移予測を考慮しなければ、上で述べたように、リンクｄ及びｅを用いて、ノードＹを経由してノードＸからノードＺにパスが構成される。一方、トラフィック推移予測を考慮すれば、上で述べたように、リンクｂを用いて、ノードＸから直接ノードＺにパスが構成される。そして、トラフィック推移予測を考慮しない場合、及びトラフィック推移予測を考慮する場合のそれぞれについて、このように構成されるパスと重なって影響を受ける場合には「×」が、影響を受けない場合には「○」が、発着ノード及び経路毎に示されている。なお、「−」はそのトラフィック自身のパスを示している。トラフィック推移予測を考慮しない場合には「×」は４つであり、トラフィック推移予測を考慮する場合には「×」は２であり、トラフィック推移予測を考慮した方が、影響を受けにくくなっている。すなわち、ネットワーク全体の利用効率が向上してリソースの有効利用が図られていることが分かる。
【００８５】
次に、どのようなコスト設定を行うべきかについて図１１（ａ）及び（ｂ）を用いて説明する。まず、トラフィック推移予測によればノードＸからノードＺにトラフィックが集中することが予測される場合に、ノードＸからノードＺへの接続要求を受信した際のコスト設定を図１１（ａ）を用いて説明する。なお、コストに遅延時間を採用する場合、リンクノ使用率ａとすると、ａ／（１−ａ）と近似することができる。すなわち、リンクｆの使用率が０．５であり、リンクｇの使用率が０．６であり、リンクｈの使用率が０．５であり、リンクｊの使用率が０．６であり、リンクｋの使用率が０．４とする。そうすると、図１１（ａ）に示すように、ノードＸとノードＹとを接続するリンクｆのコストは１．０であり、ノードＸとノードＺとを接続するリンクｇのコストは１．５であり、ノードＹとノードＺとを接続するリンクｈのコストは１．０であり、ノードＹとノードＷとを接続するリンクｊのコストは１．５であり、ノードＺとノードＷとを接続するリンクｋのコストは０．６７となる。
【００８６】
トラフィック推移予測においてノードＸからノードＺにトラフィックが集中することが予測されていてノードＸからノードＺへの接続要求を受信した場合には、上で述べた通常のリンクコストを用いて経路を特定する。具体的には、最小コストのパス（コスト＝０．６）はリンクｇで構成されるパス、次に低いコストのパス（コスト＝０．５＋０．５＝１．０）はリンクｆ及びリンクｈで構成されるパスである。よって、リンクｇで構成されるパスが割り当てられる。
【００８７】
なお、予測したトラフィック量がリンクｇの上限Ｂを超える場合には、リンクｇだけでは足りないので、２番目、３番目の経路が、必要に応じて順番に使われるようになる。
【００８８】
一方、ノードＸからノードＺへの接続要求ではない接続要求を受信した場合には、図１１（ａ）に示した通常のリンクコストではなく、図１１（ｂ）に示すようなトラフィック推移を反映したリンクコストの設定を行う。ここでは、今後到着する大量トラフィックである、ノードＸからノードＺへの接続要求には上で述べた２つのパスが使用されるとして、この２つのパスに関連するリンクのコストを上昇させる。具体的には、リンクｆ、リンクｇ及びリンクｈのコストを、トラフィック推移予測の結果から導き出される使用率ａ'を用いて計算し直す。例えば、リンクｆの使用率が０．５から０．８に増加するとコストは４．０（＝０．８／（１−０．８））となる。また、リンクｇの使用率が０．６から０．９５に増加するとコストは１９．０（＝０．９５／１−０．９５）となる。さらに、リンクｈの使用率が０．５から０．８に増加するとコストは４．０となる。
【００８９】
従って、ノードＸからノードＺへの最小コストのパスは、リンクｆ、リンクｊ及びリンクｋを含むパス（コスト＝４．０＋１．５＋０．６７＝６．１７）となり、２番目に低いコストのパスは、リンクｆ及びリンクｈを含むパス（コスト＝４．０＋４．０＝８．０）となる。従って、リンクｇは選ばれにくくなっている。
【００９０】
本実施の形態をさらに理解しやすくするための図１２に他の例を示す。図１２（ａ）に示すように、ノードＸとノードＺとが接続されたリンクｍと、ノードＸとノードＹとが接続されたリンクｌと、ノードＹとノードＷが接続されたリンクｐとが存在しており、ノードＹにはサーバＶが接続されているものとする。この際、最初にノードＸからノードＷへの接続要求を受信すると、リンクｌ及びリンクｐを含むパス（５）が割り当てられる。その後、ノードＸからサーバＶへの接続要求を受信した場合には、既に最初の接続要求によって割り当てられたパスによってリンクｌのコストが高くなってしまっており、リンクｍ及びリンクｎを含むパス（６）が割り当てられる。またその後、ノードＺからサーバＶへの接続要求を受信した場合には、先に割り当てたパスの影響を受けてリンクｎのコストが高くなってしまっており、リンクｍ及びリンクｌを含むパス（７）が割り当てられる。なお、リンクｌが使用されるのは、リンクｎを使用するよりもコストが低いためである。
【００９１】
例えば、トラフィック推移予測を行ってサーバＶにある時間帯トラフィック需要が集中することが予測できる場合、サーバＶへのトラフィック需要に最短経路を割り当てるようにすると、ネットワーク全体の利用効率が向上する。例えば、人気コンサートのチケット販売がサーバＶで始まる場合、サーバＶへ大量のトラフィックが発生することが予測できるため、以下で述べるようなルーティングが好ましい。
【００９２】
すなわち、図１２（ｂ）に示すように、最初にノードＸからノードＷへの接続要求を受信すると、サーバＶへのトラフィック量が増加するというトラフィック推移予測の結果に基づきリンクｌ及びリンクｎのコストが高く設定されるので、リンクｍ、リンクｎ及びリンクｐを含むパス（８）が割り当てられる。一方、その後にノードＸからサーバＶへの接続要求を受信すると、トラフィック推移予測に該当する接続要求であるからリンクｌ及びリンクｎについて通常どおりのコストを設定して、本接続要求に対してはリンクｌからなるパス（９）を割り当てる。また、ノードＺからサーバＶへの接続要求を受信すると、同様にトラフィック推移予測に該当する接続要求であるからリンクｌ及びリンクｎについては通常どおりのコストを設定して（但しリンクｌについては先の接続要求に割り当てられた分は反映される）、リンクｎからなるパス（１０）を割り当てる。このようにすれば、サーバＶへの大量のトラフィックについては最短経路を割り当てられるようになり、その他の接続要求に対しては迂回路を割り当てるため、ネットワーク全体の利用効率が向上してリソースの有効活用が図られる。
【００９３】
ネットワーク全体の利用効率については、図１３を用いて説明する。ノードがＸ、Ｙ及びＺしかないとして、図１３において発着ノードの列及び経路の列にはノードの全ての組み合わせ及びそのための経路が示されている。そして、トラフィック推移予測を考慮しなければ、上で述べたように、ノードＸからサーバＶへのパスは、リンクｍ及びリンクｎを用いて、ノードＺを経由してノードＸからノードＹにパスが構成される。また、トラフィック推移予測を考慮しなければ、上で述べたように、ノードＺからサーバＶへのパスは、リンクｍ及びリンクｌを用いて、ノードＸを経由してノードＺからノードＹにパスが構成される。一方、トラフィック推移予測を考慮すれば、上で述べたように、ノードＸからサーバＶへのパスは、リンクｌを用いて、ノードＸから直接ノードＹにパスが構成される。同様に、ノードＺからサーバＶへのパスは、リンクｎを用いて、ノードＺから直接ノードＹにパスが構成される。そして、トラフィック推移予測を考慮しない場合、及びトラフィック推移予測を考慮する場合のそれぞれについて、このように構成されるパスと重なって影響を受ける場合には「×」が、影響を受けない場合には「○」が、発着ノード及び経路毎に示されている。なお、「−」は上記パスと完全一致するケースを示している。トラフィック推移予測を考慮しない場合には「×」は８つであり、トラフィック推移予測を考慮する場合には「×」は４であり、トラフィック推移予測を考慮した方が、影響を受けにくくなっている。すなわち、ネットワーク全体の利用効率が向上してリソースの有効利用が図られていることが分かる。
【００９４】
より具体的には、以下のような事項が考えられる。なお、ノードＩ、ノードＪ、ノードＫの順番に経由するトラフィックの量をａ（ＩＪＫ）と記すものとする。また、どのリンクにも帯域の上限Ｂが設定されているものとする。
【００９５】
まず、ノードＹからノードＸへのパスにおいて流れ得るトラフィック量を比較する。図１３からすると、ノードＹから直接ノードＸに至るパスでは、トラフィック推移予測を考慮する場合も考慮しない場合もいずれも影響を受けずに、トラフィック量ａ（ＹＸ）＜Ｂを流すことができる。一方、ノードＹからノードＺを経由してノードＸに至るパスでは、トラフィック推移予測を考慮しないと、パス（７）のトラフィック量ａ（ＺＸＹ）の影響を受け、ａ（ＹＺＸ）＝Ｂ−ａ（ＺＸＹ）となり、ａ（ＺＸＹ）＝Ｂならば、ａ（ＹＺＸ）＝０となってしまう。トラフィック推移予測を考慮すれば影響を受けずに済む。すなわち、ａ（ＹＺＸ）＜Ｂであって、トラフィック需要に従ってデータを送信することができる。
【００９６】
以上のように、パス（７）のトラフィック量ａ（ＺＸＹ）の影響を受けると、ａ（ＹＺ）＋Ｂ−ａ（ＺＸＹ）で、最悪の場合ａ（ＹＺ）＜Ｂとなる。一方、ａ（ＺＸＹ）の影響を受けない場合には、ａ（ＹＺ）＋ａ（ＹＺＸ）＜２Ｂとなる。よって極端な場合は、トラフィック予測推移を考慮して、サーバＶ宛てに最短経路を割り当てると、ノードＹからノードＸへのパスには２倍のトラフィックを流すことが可能になる。
【００９７】
次に、ノードＸからノードＺへのパスにおいて流れ得るトラフィック量を比較する。図１３からすると、ノードＸからノードＹを経由してノードＺに至るパスは、いずれもパス（７）のトラフィック量ａ（ＺＸＹ）又はパス（９）のトラフィック量ａ（ＸＹ）の影響を受ける。トラフィック予測推移を考慮しない場合には、ａ（ＺＸＹ）の影響を受け、ａ（ＸＹＺ）＝Ｂ−ａ（ＺＸＹ）となり、ａ（ＺＸＹ）＝Ｂならばａ（ＸＹＺ）＝０となる。トラフィック予測推移を考慮する場合においても、ａ（ＸＹ）の影響を受け、ａ（ＸＹＺ）＝Ｂ−ａ（ＸＹ）であって、ａ（ＸＹ）＝Ｂであればａ（ＸＹＺ）＝０となる。
【００９８】
一方、ノードＸから直接ノードＺに至るパスは、トラフィック推移予測を考慮しない場合にはパス（６）のトラフィック量ａ（ＸＺＹ）の影響を受け、ａ（ＸＺ）＝Ｂ−ａ（ＸＺＹ）で、ａ（ＸＺＹ）＝Ｂならばａ（ＸＺ）＝０となってしまう。トラフィック推移予測を考慮すると、ａ（ＸＺＹ）の影響を受けず、トラフィック量ａ（ＸＺ）＜Ｂをそのまま流すことが可能となる。
【００９９】
以上のように、トラフィック推移予測を考慮しないならば、Ｂ−ａ（ＺＸＹ）＋Ｂ−ａ（ＸＺＹ）でａ（ＺＸＹ）もａ（ＸＺＹ）もＢになることがありえ、その時ノードＸからノードＺに至るパスに流すことができるトラフィック量は最悪の場合０となる。トラフィック推移予測を考慮するならば、Ｂ−ａ（ＸＹ）＋ａ（ＸＺ）となり、ａ（ＸＹ）はＢになることがありうるので、この時が最悪でノードＸから直接ノードＺに至るパスで流すことができるトラフィック量はａ（ＸＺ）＜Ｂとなる。最悪値の比較ということであれば、０とａ（ＸＺ）＜Ｂとの比較になるので、効果は大といえる。
【０１００】
その他も上記と同様に考察でき、トラフィック推移予測を用い、後から発生する、特定のサーバへの集中トラフィックに最短経路を割り当てることで、相当、全体に流せるトラフィック量を改善することが可能になる。
【０１０１】
なお、粗い考え方であるが、この三角網には３つの双方向リンクがあり、それぞれがＢというトラフィック量を流すことができるので、最大６Ｂのトラフィックを流すことができる。すなわち、ａ（ＸＹ）＝ａ（ＸＺ）＝ａ（ＹＺ）＝ａ（ＺＸ）＝ａ（ＹＸ）=ａ（ＺＹ）＝Ｂが最大効率を満足するトラフィック配置になる。ところが、ノードＹ宛、すなわちサーバＶ宛に２リンクを使ってしまい、ａ（ＸＺＹ）＝ａ（ＺＸＹ）＝Ｂにしてしまうと、ａ（ＸＺ）＝ａ（ＺＹ）＝ａ（ＺＸ）＝ａ（ＸＹ）＝Ｂで使われることになるので、残りはノードＹからノードＸ、ノードＹからノードＺのリンクになる。すなわち、この場合、最大でも４Ｂのトラフィックしか流れないことになる。言い換えると、トラフィック推移予測を用いた工夫により、全体で６／（６−２）＝１．５倍のトラフィックを流すようにできることもある。
【０１０２】
次に、どのようなコスト設定を行うべきかについて図１４（ａ）及び（ｂ）を用いて説明する。まず、トラフィック推移予測によればサーバＶへのトラフィック集中が予測される場合に、サーバＶへの接続要求を受信した際のコスト設定を図１４（ａ）を用いて説明する。図１４（ａ）の例では、ノードＸとノードＹとを接続するリンクｑのコストは１．０であり、ノードＸとノードＺとを接続するリンクｒのコストは２．３であり、ノードＹとノードＺとを接続するリンクｓのコストは１．０であり、ノードＹとノードＷとを接続するリンクｕのコストは１．５であり、ノードＺとノードＷとを接続するリンクｔのコストは０．６７である。なお、コストは遅延時間であり、リンクの使用率をａとすると、ａ／（１−ａ）で近似される。すなわち、上記コスト値は、リンクｑの使用率を０．５、リンクｒのコストを０．７、リンクｓの使用率を０．５、リンクｔの使用率を０．４、リンクｕの使用率を０．６とした場合の値である。
【０１０３】
トラフィック推移予測においてサーバＶ、すなわちノードＹにトラフィックが集中することが予測されていてサーバＶへの接続要求を受信した場合には、上で述べた通常のリンクコストを用いて経路を特定する。具体的には、ノードＸからサーバＶへの最小コストのパスはリンクｑで構成されるパス、ノードＺからサーバＶへの最小コストのパスはリンクｓ、ノードＷからサーバＶへの最小コストのパスはリンクｕとなる。
【０１０４】
一方、サーバＶ以外への接続要求を受信した場合には、（１）サーバＶまでのホップ数が小さいリンクほどコスト値を高くする、（２）サーバＶが接続されるノードＹに直接接続されるリンクの使用率増加分を割り当てるものとする。具体的には、サーバＶの使用率が０．９であれば、ノードＹに直接接続するリンクｕ、リンクｓ及びリンクｑについては、均等に使用率０．３が上乗せされるものとする。そうすると、図１４（ｂ）に示すように、リンクｕの使用率は、０．６＋０．３＝０．９でコストは９．０となり、リンクｓの使用率は、０．５＋０．３＝０．８でコストは４．０となり、リンクｑの使用率は、０．５＋０．３＝０．８でコストは４．０となる。これによれば直接ノードＹに接続しないリンクｒ及びリンクｔのコストは変化無く、ノードＹに向かわないリンクはコストが相対的に低くなり、そのようなリンクを使用するようになる。
【０１０５】
このような具体例を実現するための処理フローを図１５乃至図２１を用いて説明する。端末７は、接続先アドレスなどを含む接続要求をネットワーク制御サーバ５に送信する。ネットワーク制御サーバ５におけるネットワーク制御部５３の要求受信部５３１は端末７から接続要求を受信し、要求受信部５３１は、受信した接続要求から、接続元アドレス又は接続元のエッジ・ルータのアドレス又はＩＤ、接続先アドレス又は接続先のエッジ・ルータのアドレス又はＩＤ、要求帯域幅、予測保留時間などを含む経路探索要求を生成し、ネットワークコンテキスト処理部５１の最小コスト経路探索処理部５１７に出力する。予測保留時間は、接続元と接続先との接続が継続されると予測される時間である。要求帯域幅については、接続要求に含まれる場合もあれば、接続先アドレスなどから推測する場合もある。
【０１０６】
ネットワークコンテキスト処理部５１の最小コスト経路探索処理部５１７は、要求受信部５３１から経路探索要求を受信する（ステップＳ３１）。なお、予測保留時間及び要求帯域幅については最小コスト経路探索処理部５１７が推測するようにしてもよい。また、最小コスト経路探索処理部５１７は、運用ポリシー格納部５５から適用すべき運用ポリシーのデータを読み出す（ステップＳ３３）。本実施の形態では、運用ポリシーには、トラフィック推移予測を用いて処理を行うか、条件付きグラフを作成するか、条件付きグラフにおいてノードやサーバの切り捨て（プルーニング）を行う条件などの設定データを含む。
【０１０７】
そして、最小コスト経路探索処理部５１７は、ネットワークトポロジデータ格納部５１９からネットワークトポロジグラフ・データを読み出す（ステップＳ３５）。また、運用ポリシーにおいて条件付きグラフが必要と設定されているか判断する（ステップＳ３７）。条件付きグラフが不要と設定されている場合にはステップＳ４３に移行する。一方、条件付きグラフが必要と設定されている場合には、条件付きグラフ生成処理を実施する（ステップＳ３９）。この処理については後に図１６を用いて詳細に説明する。そして、必要な全ての条件でノードやサーバなどの切り捨てを行ったか判断する（ステップＳ４１）。例えば、安定度をベースにノードやサーバなどの切り捨てを行い、さらに、使用率等をベースにノードやサーバなどの切り捨てを行う。全ての条件について切り捨てを行っていなければステップＳ３９に戻る。一方全ての条件について切り捨てを行った場合にはステップＳ４３に移行する。
【０１０８】
ステップＳ４３では、最小コスト経路探索処理部５１７は、最小コスト経路選択が必要であるか判断する。もし最小コスト経路選択が不要と判断された場合には、ステップＳ４９に移行する。一方、最小コスト経路選択が必要と判断された場合には、最小コスト経路探索処理を実施する（ステップＳ４５）。この処理については後に図２１を用いて説明する。その後、最小コスト経路探索処理部５１７は、ステップＳ４５で得られた経路探索結果を経路探索結果通知としてネットワーク制御部５３の設定処理部５３３に出力する（ステップＳ４７）。設定処理部５３３は、経路探索結果通知を最小コスト経路探索処理部５１７から受信すると、経路探索結果に従ってネットワーク１における該当ルータに設定を行う。以上のような処理を処理終了イベントが発生するまで繰り返す（ステップＳ４９）。
【０１０９】
次に図１６乃至図２０を用いて、条件付きグラフ生成処理を説明する。まず、最小コスト経路探索処理部５１７は、要求受信部５３１から受信した経路探索要求から経路探索要求の条件を取得する（ステップＳ５１）。この条件とは、接続先アドレス等、予測保留時間及び要求帯域幅である。但し、接続元アドレス等を含む場合もある。また、予測保留時間と、接続先アドレス等又は接続先アドレス等及び接続元アドレス等に基づき、トラフィック推移予測結果格納部５１６から関連するトラフィック推移予測データを取得する（ステップＳ５２）。
【０１１０】
トラフィック推移予測結果格納部５１６には、リンクやサーバ毎且つ単位時間毎に、当該リンクやサーバに係るトラフィック量を増大させる接続要求に関連する接続要求先のエッジ・ルータのＩＤ、又は接続先のエッジ・ルータのＩＤ及び接続元のエッジ・ルータのＩＤ、サーバの場合にはサーバ・アドレス又はＩＤと、当該単位時間におけるトラフィック量又は使用率とが、トラフィック推移予測データとして登録されている。
【０１１１】
次に行うべき処理は、トラフィック推移予測を使って最適経路探索すべき要求とそうでない要求との識別である。上で述べたように、将来大量のトラフィックが発生することが予測できる場合に、接続要求がその大量のトラフィックの基となるものであるならば、この要求に現時点での最小コスト経路を割り当てるので、トラフィック推移予測結果は使わない。反対に接続要求が、その大量のトラフィックの基になるもの以外であるならば、大量のトラフィックに最小コスト経路を割り当てるべく、大量トラフィックが加わることを想定した最小コスト経路を割り当てるために、トラフィック推移予測を用いる。
【０１１２】
このような方針を上で述べた例を用いて説明する。図１１（ａ）及び（ｂ）についての説明において述べたように、図９でＸからＺに大量のトラフィックが発生することが予測できるとき、その要因となる接続要求、すなわち発着エッジ・ルータがＸＺであるならば、これに現時点での最小コスト経路を割り当てるので、トラフィック推移予測結果は使わず、結果的に図１１（ａ）によるリンクコストを基に経路を求める。反対に、接続要求がその大量のトラフィックの基となるもの以外の接続要求、すなわち発着エッジ・ルータがＸＺが以外であるならば、大量トラフィックが加わることを想定した最小コスト経路を割り当てるために、トラフィック推移予測を用い、結果的に図１１（ｂ）によるリンクコストを基に経路を求める。
【０１１３】
同様に、図１４（ａ）及び（ｂ）についての説明において述べたように、図１２でサーバＶに大量トラフィックが発生することが予測できる時、その要因となる接続要求、すなわちアクセス先のサーバがＶであるならば、これに現時点での最小コスト経路を割り当てるので、トラフィック推移予測結果は使わず、結果的に図１４（ａ）によるリンクコストを基に経路を求める。反対に、接続要求がその大量のトラフィックの基になるもの以外の接続要求、すなわちアクセス先のサーバがＶ以外であるならば、大量トラフィックが加わることを想定した最小コスト経路を割り当てるために、トラフィック推移予測を用い、結果的に図１４（ｂ）によるリンクコストを基に経路を求める。
【０１１４】
上記のような接続要求の区別を行うために以下の処理を行う。すなわち、ステップＳ５２では、予測保留時間内において、大量のトラフィックが加わる各リンクやサーバ等につき、接続先アドレスから特定される接続先のエッジ・ルータやサーバのＩＤ又は接続先アドレス、若しくは当該接続先のエッジ・ルータやサーバのＩＤ又は接続先アドレス及び接続元アドレスから特定される接続元のエッジ・ルータのＩＤがトラフィック推移予測結果格納部５１６に登録されているか判断し、接続先のエッジ・ルータ等のＩＤが登録されていないリンクについては、対応するトラフィック量等をトラフィック推移予測データとして読み出し、接続先のエッジ・ルータ等のＩＤが登録されているリンクについては、対応するトラフィック量等ではなくネットワークコンテキストＤＢ５１２に格納されている現在のトラフィック量等をトラフィック推移予測データとして読み出す。上で述べた具体例でも、トラフィック推移予測のとおりトラフィック量を増加させる接続要求については、通常のコストで最小コスト経路探索を実施していたとおり、接続先のエッジ・ルータ等が登録されているリンク等では通常のコストを適用すべく、当該リンク等についてのトラフィック量等を読み出さず、現在のトラフィック量又は静的属性から求められるコスト値を用いる。また、接続先のエッジ・ルータ等が登録されていないリンク等では当該リンク等についてのトラフィック量等を読み出して適用する。
【０１１５】
そして、トラフィック推移予測の反映が必要であるか判断する（ステップＳ５３）。この判断は、運用ポリシーにおいて、トラフィック推移予測を用いて処理を行うと設定されており且つステップＳ５２においてトラフィック推移予測結果格納部５１６からトラフィック推移予測データが読み出されたか否かを判断する。
【０１１６】
もし、運用ポリシーにおいてトラフィック推移予測を用いないと設定されている場合、又はステップＳ５２においてトラフィック推移予測結果格納部５１６からトラフィック推移予測データが読み出されない場合には、ネットワークコンテキストＤＢ５１２に格納されている現トラフィック状況を表すデータ（例えば現在の空き帯域又は現在のＣＰＵ使用率など）又はネットワークトポロジデータ格納部５１９に格納されている静的属性（物理的な距離、障害対策機能の有無、セキュリティ機能の有無など）に基づき各リンクや各サーバなどのコストを設定する（ステップＳ５９）。この処理については、従来と同じなのでこれ以上述べない。その後ステップＳ６１に移行する。
【０１１７】
一方、運用ポリシーにおいてトラフィック推移予測を用いると設定されており且つステップＳ５２においてトラフィック推移予測結果格納部５１６からトラフィック推移予測データが読み出された場合には、トラフィック推移予測に基づき各リンクや各サーバのコストを設定する（ステップＳ５７）。例えば、ステップＳ５２において図１７に示すようなトラフィック推移予測データ（空き帯域又は能力など）Ｓ(t)が読み出されたとする。図１７では横軸は時間を縦軸は空き帯域又は能力を表す。ステップＳ５７で設定されるコストは、予測保留時間において最も少ない空き帯域又は能力Ａに基づき決定される。なお、コストとして空き帯域又は能力をそのまま使用しても良い。
【０１１８】
ステップＳ５９又はステップＳ５７の後に、ネットワークトポロジ・グラフにおける未処理リンクやサーバを１つ選択し（ステップＳ６１）、ステップＳ５９又はステップＳ５７で設定されたコストが条件（例えば要求帯域幅。他の条件を設定しても良い。）を満たすか判断する（ステップＳ６３）。コストが条件を満たしていない場合には、ステップＳ６１で選択したリンク等を削除する（ステップＳ６５）。その後ステップＳ６７に移行する。一方、コストが条件を満たしている場合には、ステップＳ６７に移行する。
【０１１９】
例えば図１８（ａ）に示すようなネットワークトポロジ・グラフが存在する場合を考える。Ｒはルータを表し、□はサーバを表すものとする。例えばステップＳ５９又はステップＳ５７で設定されたコストが条件である要求帯域幅を満たさないと判断されると、リンクやサーバは図１８（ａ）のネットワークトポロジ・グラフから削除され、例えば図１８（ｂ）に示すようなネットワークトポロジ・グラフが生成される。図１８（ｂ）において、点線のリンク及びサーバはコストが条件である要求帯域幅を満たさないと判断されて削除された状態を示している。
【０１２０】
そしてネットワークトポロジ・グラフ内の全てのリンクやサーバを処理したか判断する（ステップＳ６７）。もし、未処理のリンクやサーバが存在している場合にはステップＳ６１に戻る。一方、全て処理した場合には元の処理に戻る。
【０１２１】
このようにすれば、トラフィック推移予測データを用いたコスト設定及びそれに応じたリンク等の切り捨てを行うことができるようになる。
【０１２２】
上ではコストとして帯域についての処理であったが、勿論他のコストを用いた運用ポリシーを実現してもよい。例えば、コストに上で述べた不安定指数を用い、不安定なリンクやサーバの切り捨てを行ってもよいし、コストに使用率や使用率の関数からなる遅延を用い、使用率が高いリソースや遅延が大きいリソースをグラフから切り捨てることも可能である。
【０１２３】
なお、トラフィック推移予測をネットワークトポロジ・グラフにおけるコストに反映する場合には、リンクについてのトラフィック推移予測のデータであればそのままそのリンクに適用するようにすればよい。一方、あるアプリケーションサーバのコスト（負荷など）がイベントによって＋Ｃa(t)増加するという場合には、図１９に示すようにアプリケーションサーバのコストの増加分＋Ｃa(t)を、関連するリンクに分配する場合もある。図１９の例では、アプリケーションサーバＶのコストが＋Ｃa(t)増加する場合には、そのエッジ・ルータ５００に接続されている３本のリンク５０１乃至５０３に、＋Ｃa(t)／３＝Ｃ1(t)を割り当てる。また、リンク５０１は、１本のリンク５０７に接続されており、リンク５０７にも＋Ｃ1(t)を割り当てる。同様に、リンク５０２はアプリケーションサーバＶから遠ざかる方向で１本のリンク５０６に接続されており、リンク５０６にも＋Ｃ1(t)を割り当てる。また、リンク５０３は、リンク５０５とリンク５０４とに接続されており、それぞれについて＋Ｃ1／２＝＋Ｃ2(t)を割当て、リンク５０７は、リンク５０９とリンク５０８とに接続されており、それぞれについてＣ1(t)／２＝Ｃ2(t)を割り当てる。
【０１２４】
さらに詳細に見れば、時間的に反映の方法はいろいろと可能である。例えばイベント時刻の前から徐々にそのイベントについての影響を反映させる場合には、例えば図２０（ａ）に示すように、イベント時刻から影響予測時間前の時刻における０から＋Ｃa(t)まで線形にコストが上昇するように設定し、同様に０から＋Ｃ1(t)まで線形にコストが上昇するように設定し、さらに０から＋Ｃ2(t)まで線形にコストが上昇するように設定する。但し、線形でなく指数関数その他の曲線に従うようにしても良い。
【０１２５】
また、図２０（ｂ）に示すように、イベント時刻で０から＋Ｃa(t)、＋Ｃ1(t)、＋Ｃ2(t)に急にコストが上昇するように設定してもよい。
【０１２６】
次に図２１を用いて最小コスト経路探索処理について説明する。まず、最小コスト経路探索処理部５１７は、要求受信部５３１から受信した経路探索要求から経路探索要求の条件を取得する（ステップＳ７１）。この条件とは、接続先アドレス等、予測保留時間及び要求帯域幅である。但し、接続元アドレス等を含む場合もある。また、接続先アドレス等又は接続先アドレス等及び接続元アドレス等に基づき、トラフィック推移予測結果格納部５１６から関連するトラフィック推移予測データを取得する（ステップＳ７２）。
【０１２７】
ステップＳ７２では、予測保留時間内において、各リンク等につき、接続先アドレスから特定される接続先のエッジ・ルータのＩＤ又は接続先アドレス、若しくは当該接続先のエッジ・ルータのＩＤ又は接続先アドレス及び接続元アドレスから特定される接続元のエッジ・ルータのＩＤがトラフィック推移予測結果格納部５１６に登録されているか判断し、接続先のエッジ・ルータ等のＩＤが登録されていないリンクについては、対応するトラフィック量等をトラフィック推移予測データとして読み出し、接続先のエッジ・ルータ等のＩＤが登録されているリンクについては、対応するトラフィック量等ではなくネットワークコンテキストＤＢ５１２に格納されている現在のトラフィック量等をトラフィック推移予測データとして読み出す。
【０１２８】
そして、トラフィック推移予測の反映が必要であるか判断する（ステップＳ７３）。この判断は、運用ポリシーにおいて、トラフィック推移予測を用いて処理を行うと設定されており且つステップＳ７２においてトラフィック推移予測結果格納部５１６からトラフィック推移予測データが読み出されたか否かを判断する。なお、運用ポリシーにより、条件付きグラフ生成処理においてはトラフィック推移予測データを用いるが、最小コスト探索の場合にはトラフィック推移予測データを用いないようにすることも可能である。逆に、条件付きグラフ生成処理においてはトラフィック推移予測データを用いず、最小コスト探索の場合にトラフィック推移予測データを用いるように、運用ポリシーを設定することも可能である。
【０１２９】
例えば、条件付きグラフ生成では、トラフィック推移予測データを考慮して、予測保留時間中、空き帯域が要求帯域以上のリンクのグラフを生成し、条件付きグラフの中から現トラフィック状況に応じて最も遅延が小さくなる経路を選択するとする。そうすると、一定期間中に今後到来するトラフィックを考慮しても空きがあるリンクとサーバとの中から、現状のトラフィックが最も遅延無く流れる経路を選ぶことが可能となる。
【０１３０】
もし、運用ポリシーにおいてトラフィック推移予測を用いないと設定されている場合、又はステップＳ７２においてトラフィック推移予測結果格納部５１６からトラフィック推移予測データが読み出されない場合には、ネットワークコンテキストＤＢ５１２に格納されている現トラフィック状況を表すデータ（例えば現在の空き帯域又は現在のＣＰＵ使用率など）又はネットワークトポロジデータ格納部５１９に格納されている静的属性（物理的な距離、障害対策機能の有無、セキュリティ機能の有無など）に基づき各リンクや各サーバなどのコストを設定する（ステップＳ７９）。この処理については、従来と同じなのでこれ以上述べない。その後ステップＳ８１に移行する。
【０１３１】
一方、運用ポリシーにおいてトラフィック推移予測を用いると設定されており且つステップＳ７２においてトラフィック推移予測結果格納部５１６からトラフィック推移予測データが読み出された場合には、トラフィック推移予測に基づき各リンクや各サーバのコスト（例えば遅延時間など）を設定する（ステップＳ７７）。
【０１３２】
ステップＳ７９又はステップＳ７７の後に、ステップＳ７９又はステップＳ７７で設定されたコストに基づき、従来技術に従って最小コストのパスを特定する（ステップＳ８１）。すなわち、遅延時間が最小となるようなパスを特定する。なお、例えば、上位５つのパスを特定した後、さらに別の基準で最小コストのパスを特定するようにしても良い。
【０１３３】
なお、最小コスト経路探索については、以下のような点を考慮する。（１）リンクコストにトラフィック推移予測を考慮した使用率ｕ＝Ｒ(t)／Ｂuに対する単調増加関数を用い、リンクコストの和が最小になる経路を求める。（２）上記のリンクコストにｆ(u)＝ｖ＋ｕｈ／（１−ｕ）を用い、遅延時間を近似する。ここでｙｈ／（１−ｕ）はキューによる待ち時間、ｖは伝達遅延を表す。（３）リンクコストにある一定期間の使用率の最大値ｕ−max＝max｛Ｒ(t)／Ｂu｝を用いる場合もある。
【０１３４】
さらに、負荷分散を行う場合には、以下のような点を考慮する。（１）リンクコストにトラフィック推移予測を考慮した空き帯域Ｂu−Ｒ(t)を用い、経路を構成するリンクのコストの最小値が最大になる経路を求める場合もある。（２）上記リンクコストにある一定期間中の空き帯域の最小値ｍｉｎ（Ｂu−Ｒ(t)）を用いる場合もある。（３）リンクコストにトラフィック推移予測を考慮した使用率ｕ＝Ｒ(t)／Ｂuの関数を用い、リンクコストの最大値が最小になる経路を求める場合もある。（４）上記のリンクコストにｆ(u)＝ｕ／（１−ｕ）を用い、待ち時間を近似する場合もある。ここでｕｈ／（１−ｕ）はキューによる待ち時間、ｈは平均パケット処理時間、ｖは伝達遅延を表す。（５）リンクコストにある一定期間の使用率の最大値ｕ−max＝max｛Ｒ(t)／Ｂu｝を用いる場合もある。
【０１３５】
さらに、 最大安定経路探索を行う場合には、以下のような点を考慮する。（１）現在のトラフィック量とトラフィック推移予測における１次予測値との差ｄ(t)＝Ｕ(t)−Ｐ(t)を不安定指数とし、これが大きい場合に、予測不可能な事象が生じているものとし、安全性が低いとする。例えば、ＤＤｏＳを受けていたり、ウィルスが蔓延していたり、不正アクセスされていると解釈する。（２）リンクコストにｄ(t)を用いる場合もある。（３）リンクコストにある期間中のｄ(t)／Ｂuの最大値を用い、リンクコストが最小になる経路を求める場合もある。（４）リンクコストにある期間Ｔ中のｄ(t)／Ｂuの積分値／Ｔを用い、リンクコストが最小になる経路を求める場合もある。（５）Ｐ(t)については、類似のイベントが無い場合、Ｐ(t)＝ａＦ(t)Ｇ(t)、又はＰ(t)＝Ｇ(t)＋ｂＦ(t)を用いる場合もある。（６）類似のイベントがある場合には、Ｐ(t)＝ａＦ(t)Ｈ(t)、又はＰ(t)＝Ｈ(t)＋ｂＦ(t)を用いる場合もある。（７）類似のイベントがあり、且つ周期成分が大きい場合、Ｐ(t)＝ａＦ(t)（Ｇ(t)＋Ｈ(t)）又はＰ(t)＝Ｇ(t)＋Ｈ(t)＋ｂＦ(t)を用いる場合もある。
【０１３６】
また、最小コストのパスを特定する際には、トラフィック量ａを収容できるだけの経路数ａ／Ｂu（一経路の帯域上限）分の経路を予め選択しておく場合もある。
【０１３７】
さらに、トラフィックの大小については、発生頻度、帯域、平均保留時間、帯域と保留時間の積であるデータ量によって評価される。
【０１３８】
また、上の説明でも分かるように、コストは単にリンクのコストだけではなく、サーバもリンクの一種としてそのコストを評価する。
【０１３９】
上でも述べたように、条件付きグラフ生成処理と最小コスト経路探索処理のいずれの処理においても、図１６のステップＳ５３や図２１のステップＳ７３にあるように、評価対象としてトラフィック推移予測、現在のトラフィック状況、静的属性のいずれかを自由に選択することができる。更に、それらを自由に組み合わせ、多様なポリシーに従った運用を可能としている。
【０１４０】
例えば、まず条件付きグラフ生成処理で障害時に迂回能力を有するリンクを選択し、次に条件付きグラフ生成処理を繰り返し、ある期間にわたって一定の空き帯域を有するリンク・サーバだけを残し、その中で最も安定した経路を探索する場合には次のように処理を行う。
【０１４１】
すなわち、条件付きグラフ生成処理（図１６）のステップＳ５９において障害時に迂回能力を有するかという静的属性からコストを定めてリンクの枝葉落とし（プルーニング）を実行し、次に、条件付きグラフ生成処理（図１６）のステップＳ５７においてある期間での空き帯域の最小値というトラフィック推移予測からコストを定めて基準値を満足するリンク・サーバだけを残すようにし、最後に最小コスト経路探索処理（図２１）のステップＳ７７にてトラフィック推移予測から得られる安定度をコストとして定めて最小コストの経路を計算する。
【０１４２】
他の例としては、現時点で一定の安定度を保っているリンクやサーバを対象に、接続要求に係るパスの遅延が保留時間中最も小さい値となる経路を探索する場合には、次のような処理を実施する。
【０１４３】
すなわち、条件付きグラフ生成処理（図１６）のステップＳ５７にて、トラフィック推移予測を用いてリンクとサーバの安定度を求め、一定の安定度を満足するリンクとサーバだけを残した条件付きグラフを作成する。次に、最小コスト経路探索処理（図２１）のステップＳ７７にて保留時間中における要求パスのトラフィック推移予測から最悪の遅延をコストに設定し、最小コストの経路を計算する。
【０１４４】
以上のような処理を行うことによって、トラフィック推移予測データを反映させた最小コストの経路を特定できるようになり、上で述べた具体例のような効果を得ることができるようになる。
【０１４５】
具体的には、ネットワークの運用経験から得た知識（ネットワーク・コンテキスト）の活用範囲が拡大されるようになる。ネットワーク・コンテキストから現状のトラフィックが今後どのように推移するかを見極め、例えば、要求基準に適するアプリケーションサーバ及びリンクを選択する。これにより、可用性や安定性が向上する。
【０１４６】
Ｄ．ネットワーク・モデル
図１に示すように全てのネットワークについて１台のネットワーク制御サーバを設けて、全てのルーティングを制御する集中型ネットワーク制御方式を採用しても良いが、大規模なネットワークへの適用を考えると、そのサーバが性能ボトルネックとなる可能性が大きい。従って、ネットワーク制御・管理単位を複数のサブネットワークに分割し、サブネットワーク単位に制御・管理できるアーキテクチャがスケーラビリティの点で望ましい。すなわち、図２２に示すように、所定のサブネットワーク毎にネットワーク制御サーバを設け、さらにサブネットワーク毎のネットワーク制御サーバを束ねるネットワーク制御サーバを上位に別途設ける階層型ネットワーク制御方式が望ましい。場合によってはネットワーク制御サーバを３層以上の階層構造を有するように設けるようにしても良い。
【０１４７】
この場合、サブネットワーク全体を制御する上位のネットワーク制御サーバでサブネットワークの選択を行うことでサブネットワーク、すなわち基幹経路を選択し、次に各サブネットワークで、サブネットワーク間の接続点におけるルータ間のサブネットワーク内経路を、当該サブネットワークにおけるネットワーク制御サーバで分散して探索する。
【０１４８】
上で述べたように制御・管理単位を分割し、階層構成にすると性能的に優位になることを以下に説明する。サブネットワーク単位に分割することで、一つのサーバで処理しなければならない仕事量も基本的には分割される。上位のネットワーク制御サーバで処理する仕事量も、ネットワーク全体のノードを対象にしたものではなく、サブネットワーク単位で集約された情報を対象にするので、集中型に比較すると格段に小さくなる。ネットワーク制御サーバの性能を支配するプロセスはネットワーク装置からその状態の情報を収集するコンテキスト収集プロセスと、その情報を用いて経路を決定する経路探索プロセスである。ここでは、コンテキスト収集プロセスにおける処理時間が階層構成によって短縮できることを示す。
【０１４９】
なお、全ノード数Ｎ、サブネット数Ｍ（簡単化のためここではＭ＝ｍ2）、ノード数／サブネット数＝Ｎ／Ｍ＝Ｎ／ｍ2とする。コンテキスト収集の到着率、計算量、サーバの計算能力、１つの処理にかかる保留時間（サービス時間）、及びサーバ使用率に関して、集中制御モデルとの関係を、上位ネットワーク制御サーバ、サブネット内のネットワーク制御サーバ毎に示すと、図２３のようになる。ここで、計算量については、コンテキスト情報を発信するエンティティ数に比例すると仮定している。サーバの計算能力の配分については、集中モデルの場合のサーバ能力をＰとし、このうちのｒＰ（ここではｒは０＜ｒ＜１）の能力を上位のネットワーク制御サーバに、残りの（１−ｒ）ＰをＭ個のサブネットワークのネットワーク制御サーバに分散すると仮定している。
【０１５０】
また、図２４には、集中モデル（Ｍ＝１）の場合、Ｍ＝４の階層モデルの場合、Ｍ＝１６の階層モデルの場合のそれぞれにつき、サーバ使用率とコンテキスト収集処理の遅延時間の関係を待ち行列モデルＭ／Ｍ／１で計算した結果を表している。このように、サーバ使用率が上昇すると、集中モデルやサブネット数Ｍが小さいと遅延時間が長くなってしまい、実用に耐えないことが分かる。なお、経路探索の処理時間のモデルについては後に述べるが、結果については同様のことがいえる。
【０１５１】
また、図２８は、集中モデルのサーバ能力をＰとし、これと等価な計算機資源をいかにＭ＝４の階層モデルのサーバに配分するか示すものである。ｒ＝０．９とほとんどの計算能力を上位のネットワーク制御サーバに割り当ててしまうと、ｒ＝０．１の計算能力しかサブネットワークにおける全ネットワーク制御サーバに割り当てることができなくなる。各サブネットワークのサーバにはこれを更にＭで分割した計算機資源しか配分できなくなり、図２３から明らかなように、計算量がＭ（この場合４）分割されたとしても、計算能力が低いため、サーバ使用率は、集中型にも増して高くなってしまう。そのため、図２８のようにコンテキスト収集処理時間は、集中モデル基準のサーバ使用率が低いうちから急激に高くなってしまう。これに比べ、ｒ＝０．５、ｒ＝０．１と低くしてゆき、サブネットワークのネットワーク制御サーバに割り当てる割合を高くしてゆくと、Ｍ（この場合４）分割された計算量に対し、十分な計算能力が割り当てられ、コンテキスト収集処理時間は、集中モデルに比べ格段に小さくすることが可能になる。このとき、反対に上位のネットワーク制御サーバの処理時間が増加するが、その値は相対的に非常に小さいためその影響を受けることはない。基本的には、図２３や後に述べる図２９のサーバ使用率やサービス時間に関し、集中モデルのそれらよりも、階層モデルのそれらの値が小さくなるようにＭやｒを決定することで、階層モデルの性能を優位とすることが可能になる。
【０１５２】
ここでは、ネットワーク制御サーバの性能を支配するプロセスの残りの一つであるコンテキスト情報を用いて経路を決定する経路探索プロセスのモデルを示す。コンテキスト収集プロセスと同様に、全ノード数Ｎ、サブネット数Ｍ（簡単化のためここではＭ＝ｍ2）、ノード数／サブネット数＝Ｎ／Ｍ＝Ｎ／ｍ2とする。経路探索要求の到着率、計算量、サーバの計算能力、１つの処理にかかる保留時間（サービス時間）、及びサーバ使用率に関して、集中制御モデルとの関係を、上位ネットワーク制御サーバ、サブネット内のネットワーク制御サーバ毎に示すと、図２９のようになる。ここで、１つの経路探索要求に関わるサブネット数をｍと仮定したため、サブネット内の経路探索要求の到着率は全体の１／ｍとしている。サーバの計算能力の配分については、集中モデルの場合のサーバ能力をＰとし、この内のｒＰ（ここでｒは０＜ｒ＜１）の能力を上位のネットワーク制御サーバに、残りの（１−ｒ）ＰをＭ個のサブネットワークのネットワーク制御サーバに分散すると仮定している。また、経路探索の必要計算量はダイクストラアルゴリズムの計算量がノード数ｎに対し、ｎｌｏｇ（ｎ）になることが知られているため、図２９のようにしている。
【０１５３】
上で述べたとおり、図２９のサーバ使用率やサービス時間に関し、集中モデルのそれらよりも、階層モデルのそれらの値の方が小さくなるようにＭやｒを決定することで、階層モデルの性能を優位とすることが可能になる。
【０１５４】
以上本発明の実施の形態について説明したが本発明はこれに限定されるものではない。例えば図１に示したネットワーク制御サーバ５の機能ブロックは一例であって、実際のプログラムモジュールの構成とは異なる場合もある。
【０１５５】
ネットワーク制御サーバ５は、図２５のようなコンピュータ装置であって、メモリ２５０１（記憶装置）とＣＰＵ２５０３（処理装置）とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施の形態における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本発明の実施の形態では、上で述べた処理を実施するためのアプリケーション・プログラムはリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１５６】
（付記１）
ネットワークの各リソースについて将来における予測使用推移データを格納する予測使用推移データ格納部から、受信した接続要求に関連する予測使用推移データを読み出す予測使用推移データ特定ステップと、
読み出した前記予測使用推移データに基づき、所定の条件を満たすリソースを選択する選択ステップと、
を含み、コンピュータに実行されるルーティング制御方法。
【０１５７】
（付記２）
ネットワークデータ格納部に格納された、前記ネットワークの各リソースについての静的属性に関するデータを用いて所定の条件を満たすリソースを選択するステップと、
ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての現在の使用状況データを用いて所定の条件を満たすリソースを選択するステップと、
前記予測使用推移データ特定ステップ及び前記選択ステップと、
のうちいずれかを選択する方針選択ステップをさらに含む付記１記載のルーティング制御方法。
【０１５８】
（付記３）
前記方針選択ステップが、前記接続要求に対応する条件付きネットワークトポロジ・グラフを生成する場合、又はネットワークトポロジ・グラフの中から前記接続要求に対応する経路を探索する場合に実行される付記２記載のルーティング制御方法。
【０１５９】
（付記４）
前記予測使用推移データに基づき、帯域又は保留時間が所定の値よりも大きい大量トラフィックの通信要求の到着を検出するステップ
をさらに含み、
前記選択ステップが、
前記大量トラフィック以外の通信要求に対して、前記大量トラフィックの通信要求の到着に係る前記予測使用推移データに基づき、各リソースのコストを定め、当該コストの値が所定の条件を満たすリソースを選択するステップと、
前記大量トラフィックの通信要求に対して、ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての現在の使用状況データ又は静的な属性情報を用いて各リソースのコストを定め、当該コストの値が所定の条件を満たすリソースを選択するステップと、
を含む付記１記載のルーティング制御方法。
【０１６０】
（付記５）
前記選択ステップが、
読み出した前記予測使用推移データにおいて、前記接続要求に関連する期間内において最も厳しい予測使用状況を表す値を特定するステップ
を含む付記１記載のルーティング制御方法。
【０１６１】
（付記６）
前記接続要求に関連する期間が、予測通信保留期間であることを特徴とする付記１のルーティング制御方法。
【０１６２】
（付記７）
ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての過去の使用状況データから、前記ネットワークの各リソースについて将来における予測使用推移データを生成し、前記予測使用推移データ格納部に格納する予測使用推移データ生成ステップ
をさらに含む付記１記載のルーティング制御方法。
【０１６３】
（付記８）
前記予測使用推移データ格納部において、前記ネットワークの各リソースについて、前記予測使用推移データと当該予測使用推移データに関連するサーバの識別情報又はエッジ・ルータの識別情報とが格納されており、
前記予測使用推移データ特定ステップが、
少なくとも前記接続要求の接続先アドレスに応じて適用される前記予測使用推移データを特定する特定ステップ
を含む付記１記載のルーティング制御方法。
【０１６４】
（付記９）
前記特定ステップが、
前記接続要求の接続先アドレスから特定されるサーバの識別情報又はエッジ・ルータの識別情報が、特定のリソースについて、前記予測使用推移データ格納部において前記予測使用推移データと対応付けられて登録されている場合には、当該対応する予測使用推移データを用いることなく別の所定のデータを前記特定のリソースについて予測使用推移データとして特定するステップ
を含む付記８記載のルーティング制御方法。
【０１６５】
（付記１０）
前記特定ステップが、
前記接続要求の接続先アドレスから特定されるサーバの識別情報又はエッジ・ルータの識別情報が、特定のリソースについて、前記予測使用推移データ格納部において前記予測使用推移データと対応付けられて登録されていない場合には、当該特定のリソースについての前記予測使用推移データを特定するステップ
を含む付記８記載のルーティング制御方法。
【０１６６】
（付記１１）
前記別の所定のデータが、現在の使用状況データ、無負荷を表すデータ、又は静的な属性情報である
付記９記載のルーティング制御方法。
【０１６７】
（付記１２）
前記選択ステップが、
前記予測使用推移データに基づきコストを設定するステップ
を含む付記１記載のルーティング制御方法。
【０１６８】
（付記１３）
前記コストが、前記予測使用推移データに対して予め定められたルールに従って変更を実施した後に設定される
付記１２記載のルーティング制御方法。
【０１６９】
（付記１４）
前記方針選択ステップが、条件付きネットワークトポロジ・グラフを生成する場合に実行され、
前記所定の条件が、前記予測使用推移データが使用率であれば前記接続要求に関連する期間内における使用率の最大値が閾値以下、前記予測使用推移データが空き帯域であれば前記接続要求に関連する期間内における空き帯域の最小値が閾値以上であるという条件を含む
付記２記載のルーティング制御方法。
【０１７０】
（付記１５）
前記方針選択ステップが、条件付きネットワークトポロジ・グラフを生成する場合に実行され、
前記所定の条件が、前記予測使用推移データから特定される現在の値と実際の現在の使用状況データの値との差又は当該差の時間積分値であるリンクコストが閾値内であるという条件を含む
付記２記載のルーティング制御方法。
【０１７１】
（付記１６）
前記方針選択ステップが、経路探索する場合に実行され、
前記所定の条件が、予測推移を考慮した最小遅延経路探索ならば、前記予測使用推移データにおける使用率から換算される遅延時間をコストとし、最小コスト経路を探索することを含む
付記２記載のルーティング制御方法。
【０１７２】
（付記１７）
前記方針選択ステップが、経路探索する場合に実行され、
前記所定の条件が、予測推移を考慮した最大安定経路探索ならば、前記予測使用推移データから導かれる現在のトラフィック値と実際の現在のトラフィック値の差、又は当該差の時間積分値をリンクコストとし、最小コスト経路を探索することを含む
付記２記載のルーティング制御方法。
【０１７３】
（付記１８）
変動パターンデータ格納部に格納された、前記ネットワークの各リソースについて予め生成されている周期的な使用状況の変動パターンデータと、非周期的なイベント変動パターンデータと、長期変動パターンデータとのうち少なくともいずれかを用いて、前記ネットワークの各リソースについて、第１の予測使用推移データを生成するステップ
を含む付記１記載のルーティング制御方法。
【０１７４】
（付記１９）
変動パターンデータ格納部に格納された、前記ネットワークの各リソースについて予め生成されている周期的な使用状況の変動パターンデータ、あるいは、非周期的なイベント変動パターンデータに、長期変動パターンデータを積算するか、あるいは加算することにより、長期増加分を加味することを特長とする、前記ネットワークの各リソースについて、第１の予測使用推移データを生成するステップ
を含む付記１８記載のルーティング制御方法。
【０１７５】
（付記２０）
生成された前記第１の予測使用推移データを、ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての現在の使用状況データに合致するように修正して、第２の予測使用推移データを生成するステップ
をさらに含む付記１８記載のルーティング制御方法。
【０１７６】
（付記２１）
生成された前記第１の予測使用推移データを、ネットワークコンテキストデータ格納部に格納された、前記ネットワークの各リソースについての現在の使用状況データに合致するように修正して第２の予測使用推移データを生成する際に、
ある時点における前記第１の予測使用推移データと現在の使用状況データの差を第１の予測推移データに加算するか、あるいは、ある時点における第１の予測使用推移データと現在の使用状況データの比率を第１の予測推移データに積算するステップ
をさらに含む付記２０記載のルーティング制御方法。
【０１７７】
（付記２２）
生成された前記第２の予測使用推移データを、前記ネットワークの各リソースの物理的上限値に応じて修正して、第３の予測使用推移データを生成するステップ
をさらに含む付記２０記載のルーティング制御方法。
【０１７８】
（付記２３）
生成された前記第２の予測使用推移データを、前記ネットワークの各リソースの物理的上限値に応じて修正して、第３の予測使用推移データを生成する際に、
第２の予測使用推移データの最大値がリソースの物理的上限値に一致するように第２の予測使用推移データを正規化する、あるいは、第２の予測使用推移データがリソースの物理的上限値を超えた時間帯だけ物理的上限値で処理する、又は第２の予測使用推移データがリソースの物理的上限値を超えた時間帯と超えたデータ量をその直後の時間帯に物理的上限値で処理する第２の予測使用推移データを正規化するステップ
をさらに含む付記２２記載のルーティング制御方法。
【０１７９】
（付記２４）
付記１乃至２３のいずれか１つ記載のルーティング制御方法をコンピュータに実行させるためのプログラム。
【０１８０】
（付記２５）
ネットワークの各リソースについて将来における予測使用推移データを格納する予測使用推移データ格納部と
前記予測使用推移データ格納部から、受信した接続要求に関連する予測使用推移データを読み出す予測使用推移データ特定手段と、
読み出した前記予測使用推移データに基づき、所定の条件を満たすリソースを選択する選択手段と、
を有するルーティング制御装置。
【０１８１】
（付記２６）
付記２５記載のルーティング制御装置をサブネットワーク毎に設け、
前記ルーティング制御装置を統括してサブネットワーク間のルーティングに関する処理を実施する第２のルーティング制御装置を有する
階層型ルーティング制御システム。
【０１８２】
（付記２７）
サブネットワーク毎に設けた付記２５記載のルーティング制御装置と、前記ルーティング制御装置を統括してサブネットワーク間のルーティングに関する処理を実施する第２のルーティング制御装置とに、
制御管理対象の全ノード数Ｎと分割したサブネットワーク数Ｍから決定される割合に従って計算機資源を配分することを特徴する
階層型ルーティング制御システム。
【０１８３】
（付記２８）
前記予測使用推移データから特定される現在の値と実際の現在の使用状況データの値との差に基づきリソースが不安定と判断されている間、当該リソースを使う新たなパス設定要求を、強制的に拒否するステップ
をさらに含む付記１記載のルーティング制御方法。
【０１８４】
（付記２９）
前記予測使用推移データから特定される現在の値と実際の現在の使用状況データの値との差に基づきリソースが不安定と判断された場合に、当該リソースを既に使用しているパスを強制的に切断すること、他の安定なパスへトラフィックを切り替えること、及び当該リソースを既に使用しているパスを流れるパケットを廃棄することのうち少なくとも１つを実施する実施ステップをさらに含み、
前記実施ステップを、前記リソースが安定と判断されるまで継続的に実行する
ことを特徴とする付記１記載のルーティング制御方法。
【０１８５】
（付記３０）
前記実施ステップが、
前記予測使用推移データから特定される現在の値と実際の現在の使用状況データの値との差に基づき不安定と判断されたリソースを用いるパスが、予め登録された重要通信を行うパスか否かを判断するステップ、
を含む付記２９記載のルーティング制御方法。
【０１８６】
（付記３１）
前記実施ステップが、
前記予測使用推移データから特定される現在の値と実際の現在の使用状況データの値との差に基づき不安定と判断されたリソースを用いるパスを、トラフィック量が大きい順に選択するステップ、
を含む請求項２９記載のルーティング制御方法。
【図面の簡単な説明】
【０１８７】
【図１】本発明の実施の形態に係るシステム概要を説明するための図である。
【図２】（ａ）は長期変動パターンの一例、（ｂ）は周期変動パターンの一例、（ｃ）はイベント変動パターンの一例を示す図である。
【図３】トラフィック推移予測の処理フローを示す図である。
【図４】（ａ）は長期変動パターン及びイベント変動パターンを示し、（ｂ）は（ａ）の積算型の合成、（ｃ）は（ａ）の加算型の合成を示す図である。
【図５】（ａ）は長期変動パターン及び周期的変動パターンを示し、（ｂ）は（ａ）の積算型の合成、（ｃ）は（ａ）の加算型の合成を示す図である。
【図６】（ａ）及び（ｂ）は、２次予測を説明するための図である。
【図７】（ａ）乃至（ｄ）は、３次予測を説明するための図である。
【図８】安定性判定のための処理フローを示す図である。
【図９】（ａ）は第１の具体例の問題点を示すためのルーティングを表すための図であり、（ｂ）は第１の具体例におけるルーティングを表す図である。
【図１０】第１の具体例の効果を示すための図である。
【図１１】（ａ）及び（ｂ）は、コスト設定の一例を示す図である。
【図１２】（ａ）は第２の具体例の問題点を示すためのルーティングを表す図であり、（ｂ）は第２の具体例におけるルーティングを表す図である。
【図１３】第２の具体例の効果を示すための図である。
【図１４】（ａ）及び（ｂ）は、コスト設定の他の例を示す図である。
【図１５】ルーティングのメイン処理フローを示す図である。
【図１６】条件付きグラフ生成処理の処理フローを示す図である。
【図１７】トラフィック推移予測（空き帯域）と予測保留時間と判断に用いられる値Ａとの関係を示す図である。
【図１８】（ａ）は元のネットワークトポロジ・グラフ、（ｂ）は切り捨て後のネットワークトポロジ・グラフを表す図である。
【図１９】サーバのトラフィック量の増加分をリンクに伝播する方法を説明するための図である。
【図２０】（ａ）及び（ｂ）は、サーバのトラフィック量の増加分をリンクに伝播する量を説明するための図である。
【図２１】最小コスト経路探索処理の処理フローを示す図である。
【図２２】階層型ネットワーク制御モデルの概念図である。
【図２３】階層型ネットワーク制御方式の性能評価モデルを示す図である。
【図２４】階層型ネットワーク制御方式の性能評価結果を示す図である。
【図２５】コンピュータの機能ブロック図である。
【図２６】経路選択によるリソース利用効率の違いを説明するためのモデルネットワークを示す図である。
【図２７】経路選択によるリソース利用効率の違いを説明するためのパス要求の例を示す図である。
【図２８】階層型ネットワーク制御方式における計算機資源の配分の評価結果を示す図である。
【図２９】階層型ネットワーク制御方式における性能評価モデルの他の例を示す図である。
【図３０】図８の代わりに実行される処理フロー（第１部分）を示す図である。
【図３１】図８の代わりに実行される処理フロー（第２部分）を示す図である。
【符号の説明】
【０１８８】
１  ネットワーク    ５  ネットワーク制御サーバ    ７  端末
９  アプリケーションサーバ
５１  ネットワークコンテキスト処理部
５３  ネットワーク制御部
５５  運用ポリシー格納部
５１１  トラフィックデータ収集部
５１２  ネットワークコンテキストＤＢ
５１３  パターン抽出部
５１４  トラフィック変動パターンデータ格納部
５１５  トラフィック推移予測部
５１６  トラフィック推移予測結果格納部
５１７  最小コスト経路探索部    ５１８  イベントデータ格納部
５１９  ネットワークトポロジデータ格納部
５３１  要求受信部    ５３３  設定処理部
【図１】
0004606333.tif 000002
【図２】
0004606333.tif 000003
【図３】
0004606333.tif 000004
【図４】
0004606333.tif 000005
【図５】
0004606333.tif 000006
【図６】
0004606333.tif 000007
【図７】
0004606333.tif 000008
【図８】
0004606333.tif 000009
【図９】
0004606333.tif 000010
【図１０】
0004606333.tif 000011
【図１１】
0004606333.tif 000012
【図１２】
0004606333.tif 000013
【図１３】
0004606333.tif 000014
【図１４】
0004606333.tif 000015
【図１５】
0004606333.tif 000016
【図１６】
0004606333.tif 000017
【図１７】
0004606333.tif 000018
【図１８】
0004606333.tif 000019
【図１９】
0004606333.tif 000020
【図２０】
0004606333.tif 000021
【図２１】
0004606333.tif 000022
【図２２】
0004606333.tif 000023
【図２３】
0004606333.tif 000024
【図２４】
0004606333.tif 000025
【図２５】
0004606333.tif 000026
【図２６】
0004606333.tif 000027
【図２７】
0004606333.tif 000028
【図２８】
0004606333.tif 000029
【図２９】
0004606333.tif 000030
【図３０】
0004606333.tif 000031
【図３１】
0004606333.tif 000032