JP2011176445A - 経路決定装置，経路決定方法及び経路決定プログラム - Google Patents

Abstract

【課題】フローに対する経路決定に際して、フローのエンドツーエンド品質を考慮した経路を現実的な計算量で求めることができるようにする。
【解決手段】データリンクにフローを割り当てることによりそのデータリンクにおいて生じる品質変化に基づき、フローのエンドツーエンドの品質要件を満たしていることと、データリンクにフローを割り当てることによりそのデータリンクにおいて既存の他フローに生じる品質変化に基づき、他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定部１０４と、設定された制約条件を満たす範囲内で、複数のデータリンクにより構成される複数の経路の中から、フローに対する経路を決定する経路決定部１０２とをそなえる。
【選択図】図１

Description

本件は、データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する技術に関する。

複数のノードと各ノード間を夫々連結する多数のリンクとをそなえたネットワークにおいては、各ノードに接続されたネットワーク管理システム（ＮＭＳ：Network Management System）が、ネットワーク上における経路の決定やフローの収容（割当）を行なう。
具体的には、ネットワーク管理システムの経路設計機能が、送信元ノードから送信先ノードに対するデータ送信に関するフロー設定要求に応じて、到達性条件やトラフィック容量，経路長（ホップ数）条件等の制約条件に従って、経路の決定及びフローの収容を行なう。なお、フローとはデータの流れであり、セッション又はパスと言い換えることができる。

従来の経路設計手法においては、例えば、複数パターンの経路からノード間のリンクコストを最小化する経路を最適な経路として決定する技術が知られている（下記特許文献１）。

特表２００３−５２７０３９号公報

このような従来の経路決定手法においては、経路が重畳されているリンク毎のトラフィック利用制限等を制約条件として与えることで経路を決定している。このような制約条件では、ネットワークに収容される各フローのエンドツーエンド（End-to-End）品質を保証するために、ネットワーク利用に対してどれぐらいのレベルまで許容できるかが明確ではなく、厳しい制約条件付与のもと経路計算を行なわざるを得ない。

また、従来の経路決定手法においては、新たなフローに対する経路を計算する際に、様々な経路長や品質要件を持つ各フローのエンドツーエンド品質を考慮して経路計算を行なおうとすると、全ての経路候補に対して全パターン検索をして実現するしかない。すなわち、計算量が膨大になり時間がかかる他、ノード数の多いネットワーク構成によっては処理が破綻するという課題がある。

本件の目的の一つは、このような課題に鑑み創案されたもので、フローに対する経路決定に際して、フローのエンドツーエンド品質を考慮した最適経路を現実的な計算量で求めることができるようにすることである。
なお、前記目的に限らず、後述する発明を実施するための形態に示す各構成により導かれる作用効果であって、従来の技術によっては得られない作用効果を奏することも本発明の他の目的の1つとして位置付けることができる。

このため、この経路決定装置は、データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する経路決定装置であって、該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定部と、該制約条件設定部により設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定部とをそなえる。

また、この経路決定方法は、データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する経路決定方法であって、該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定ステップと、該制約条件設定ステップにおいて設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定ステップとをそなえる。

さらに、この経路決定プログラムは、データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する機能をコンピュータに実行させるための経路決定プログラムであって、該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定部と、該制約条件設定部により設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定部として、該コンピュータを機能させる。

開示の技術によれば、以下の少なくともいずれか１つの効果ないし利点が得られる。
（１）フローに対し、既存の他フローを含む各フローに対するエンドツーエンド品質要件を満たす経路を少ない計算量で求めることができる
（２）ノード数が多いネットワークにおいても、多項式時間で最適経路を計算することができる。

実施形態の一例としてのネットワーク管理システムの構成を模式的に示す図である。 実施形態の一例としてのネットワーク管理システムの管理サーバの機能を説明するための図である。 実施形態の一例としてのネットワーク管理システムにおける制約条件設計部による制約条件の設定手法を説明するための図である。 リンクトラフィック負荷とバッファリング遅延との関係を示す図である。 リンクトラフィック負荷とロス率との関係を示す図である。 実施形態の一例としてのネットワーク管理システムにおける要求フローに対する経路計算をするための目的関数と制約条件式とを説明するための図である。 実施形態の一例としてのネットワーク管理システムにおける最適経路の表現方法を説明するための図である。 実施形態の一例としてのネットワーク管理システムにおける経路設定手法を説明するためのフローチャートである。 実施形態の一例としてのネットワーク管理システムにおける各フローの最適経路とその経路履歴情報の使用方法を示す図である。 実施形態の一例としてのネットワーク管理システムにおける、要求フローに対する経路設定処理の流れを説明するためのフローチャートである。 実施形態の一例としてのネットワーク管理システムにおける制約条件の設計手法を説明するためのフローチャートである。 ネットワークのトポロジの構成例を示す図である。 実施形態の一例としてのネットワーク管理システムにおいて生成されるリンク属性情報を例示する図である。 実施形態の一例としてのネットワーク管理システムの制約条件設計部による制約条件の生成手法を説明するための図である。

以下、図面を参照して経路決定に係る実施の形態を説明する。
図１は実施形態の一例としてのネットワーク管理システム１の構成を模式的に示す図、図２はその管理サーバ１０の機能を説明するための図である。
ネットワーク管理システム１は、データリンクを介して接続される複数のノードをそなえるネットワーク２を管理するものであり、図１に示すように、管理サーバ１０をそなえている。

ネットワーク２は、複数のノードをそなえるとともに、これらのノード間を通信可能に接続するデータリンクをそなえている。
ノードは、それぞれデータリンクを介して他のノードとデータを受信及び送信可能なコンピュータシステムである。
また、各ノードは、それぞれ、ネットワーク２に送信されるデータの発信元である送信元ノードとして機能可能であるとともに、送信元ノードから送信されるデータを受信する宛先としての受信ノード（送信先ノード）として機能可能である。又、各ノードは、送信元ノード又は他のノードからデータを受信し、受信されたデータを更に他のノードに送信（転送）する機能もそなえている。なお、本実施形態においては、便宜上、これらのノードの構成や機能についての詳細な説明は省略する。

データリンクは、例えば、ＬＡＮ（Local Area Network）やＦＣ（Fibre Channel）等の通信回線（伝送路）である。このデータリンクは、データを送信するための物理的な回線の他、データネットワークにおいてデータを送受信するためのハードウェア構成要素及びソフトウェア構成要素をそなえている。そして、このデータリンクには既知の種々の規格の通信回線を用いることができる。なお、本実施形態においては、便宜上、これらのデータリンクの構成や機能についての詳細な説明は省略する。又、以下、データリンクを単にリンクという場合がある。

図１に示す例においては、ネットワーク２に６つのノードがそなえられている例を示しており、これらのノードを、それぞれＡ，Ｂ，Ｃ，Ｄ，１および２の符号を付して示している。
なお、以下、これらのノードを特定するための符号をノード番号という。又、以下、ノードを表す場合には、任意のノードを指すときには単にノードと表現するが、複数のノードのうち１つを特定する必要があるときにはノード番号を付して表す。例えば、ノード番号ＡのノードをノードＡと表し、ノード番号１のノードをノード１と表す場合がある。

また、図１に示す例においては、データリンクによって接続されたノード間のデータ経路（データリンク）を符号ｘを用いて表すとともに、このｘに対して、その経路の両端を形成する各ノードのノード番号を付すことによりデータの送信方向を表す。より詳細には、符号ｘに対して、データの送信元のノード番号、送信先のノード番号の順に並べて下付き符号で付記することにより、そのデータリンクにおけるデータ経路をデータの伝送方向とともに表す。

例えば、符号ｘ_Ａ２は、ノードＡからノード２へデータを伝送する経路を表しており、符号ｘ_２Ｄは、ノード２からノードＤへデータを伝送する経路を表している。
また、以下、データリンクを符号（ｉ，ｊ）を用いて表わす場合がある。ただし、ｉ，ｊはともにデータリンクの両端に位置するノード番号である。
管理サーバ１０は、ネットワーク２におけるデータの送信経路を管理するものであり、ネットワーク２を構成する各ノードに直接もしくは間接に接続されている。この管理サーバ１０は、データリンクを介して接続される複数のノードを有するネットワーク２において、フローに対する経路を決定する経路決定装置として機能する。

また、管理サーバ１０は、サーバ機能をそなえたコンピュータ（情報処理装置）であって、図１に示すように、ＣＰＵ１０１，表示装置１３，ＲＡＭ１１，ＲＯＭ１２，入力装置１４及び記憶装置１５をそなえている。
表示装置１３は、種々の情報を表示することにより、オペレータに対して情報を提示するものであり、例えば、液晶ディスプレイやＣＲＴ（Cathode Ray Tube）ディスプレイである。入力装置１４は、オペレータが種々の指示やデータを入力するための装置であり、例えば、キーワードやマウス等である。

ＲＡＭ（Random Access Memory）１１は、データやプログラム（ネットワーク管理プログラム，経路決定プログラム）を一時的に格納する記憶装置であり、後述するＣＰＵ１０１が各種演算や制御を行なう際に、データやプログラムを展開（格納）するために用いられる。
また、ＲＡＭ１１には、コスト定義テーブル１１１，制約条件情報１１２，経路履歴情報１１３及びリンク属性情報１１４を格納する。

コスト定義テーブル１１１は、ネットワーク２に含まれる各データリンク（ｉ，ｊ）のコスト（リンクコスト）を格納するものであり、各データリンク（ｉ，ｊ）に対して、予め設定されたリンクコストｃ_ｉ，ｊを対応付けて格納する。なお、このリンクコストは、既知の種々の手法を用いて求めることができ、その詳細な説明は省略する。
制約条件情報１１２は、後述する制約条件設計部１０４によって設定された品質制約条件である。なお、この品質制約条件についての詳細な説明は後述する。

経路履歴情報１１３は、後述する最適経路計算部１０２によって決定された最適経路に関する情報であって、例えば、フローを特定する識別情報に対して、最適経路を示す情報や、そのフローに関する、利用帯域，エンドツーエンド遅延（バッファリング遅延）に対する品質要件及びロス率（パケットロス率）に対する品質要件を関連付けられている。すなわち、ＲＡＭ１１は、最適経路計算部１０２によって決定された、フローに対する経路をなすデータリンクに関する情報を経路履歴情報として格納する経路履歴情報格納部として機能する。

リンク属性情報１１４は、制約条件設計部１０４による品質制約条件の設定に際して生成される情報である。このリンク属性情報１１４の詳細は、図１３を参照しながら後述する。
また、ＲＡＭ１１には、送信元ノードから送信された要求フローｆ（詳細は後述）も格納され、この要求フローｆは、後述する最適経路計算部１０２や設計履歴管理部１０３，制約条件設計部１０４等から読み出すことができる。

ＲＯＭ（Read Only Memory）１２はデータやプログラムを格納する記憶装置である。記憶装置１５は、データやプログラムを格納する記憶装置であり、例えばＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid State Drive）等であって、ＯＳ（Operating System）等の種々のプログラムやデータを格納する。
なお、上述したコスト定義テーブル１１１，制約条件情報１１２，経路履歴情報１１３，リンク属性情報１１４および要求フローｆの少なくとも一部を、ＲＡＭ１１に代えて記憶装置１５に格納してもよい。

ＣＰＵ１０１は、ＲＯＭ１２や記憶装置１５に格納されたプログラムを実行することにより種々の演算や制御を実行し、種々の機能を実現する処理装置である。本実施形態においては、このＣＰＵ１０１が、ネットワーク管理プログラムを実行することにより、図１に示すように、フロー経路決定部１１０（最適経路計算部１０２，設計履歴管理部１０３，制約条件設計部１０４，状態計測部１０５）及び経路設計部１０６として機能する。

すなわち、管理サーバ１０において、ＣＰＵ１０１がフロー経路決定部１１０及び経路設計部１０６として機能することにより、図２に示すように、送信元ノード（拠点Ａ）からの要求フロー（設計フロー，接続要求）ｆを受けて、このフローに対する最適な経路（フロー経路）を決定し、経路設定を行なう。
さて、送信元ノードからの要求フローｆには、送信されるデータの他、要求フロー帯域Ｂｆ及び要求フロー品質要件が含まれる。要求フロー帯域Ｂｆは、送信するデータの利用帯域（トラフィック量）であり、例えば、bps（Bits Per Second）等の単位で表される。そして、この要求フロー帯域Ｂｆは、その要求フローｆをデータリンクに流すことにより、そのデータリンクにおいて増加するトラフィック量（トラフィック増量分）を表す。

要求フロー品質要件（品質要件）は、要求フローｆにおいて求められるエンドツーエンド品質を表す情報であって、遅延情報Ｄｆ及びロス率Ｌｆをそなえている。遅延情報Ｄｆは、その要求フローｆに許容される遅延レベルを表す情報であり、例えば、sec（秒）やmsec（ミリ秒）等の単位で表される。ロス率Ｌｆは、その要求フローｆに許容されるデータのロス率（パケットロス率）であり、例えば、０〜１の数値で表される。なお、このロス率はパーセント等の他の単位で表わしてもよい。

なお、これらの要求フロー帯域Ｂｆ及び要求フロー品質要件は、ＲＡＭ１１等の記憶装置における所定の記憶領域に格納される。
経路設計部１０６は、要求フローｆを伝送すべく、フロー経路決定部１１０によって決定された経路（最適経路）をネットワーク上に設定する。なお、この経路設計部１０６としての機能は既知の種々の手法により実現することができ、その詳細な説明については省略する。

フロー経路決定部１１０は、送信元ノードからの要求フローｆに基づいて、経路となるデータリンクを決定するものであり、新たな経路を追加したい送信元ノード（始点ノード）からのフロー要求を受け付けると、その要求フローｆに関して最適経路Ｘの決定を行なう。なお、送信元ノードは、ノードに繋がった端末であってもよい。
このフロー経路決定部１１０は、図１に示すように、最適経路計算部１０２，設計履歴管理部１０３，制約条件設計部１０４及び状態計測部１０５をそなえている。

状態計測部１０５は、ネットワーク２の状態を把握するものであり、ネットワーク２の各データリンク（ｉ，ｊ）における各転送トラフィック量（トラフィック量，リンクトラフィック負荷）Ｒ_ｉ，ｊを計測する。この状態計測部１０５は、データリンクにおけるトラフィック量を実測することにより求めてもよく、又、各データリンクに対する要求フローｆに含まれる情報等に基づいて計算して求めてもよい。すなわち、状態計測部１０５は、既知の種々の手法を用いて、各データリンク（ｉ，ｊ）における各トラフィック量Ｒ_ｉ，ｊの計測を実現することができる。

また、状態計測部１０５は、計測した各転送トラフィック量を例えば、ＲＡＭ１１や記憶装置１５の所定の記憶領域に格納する（図１３参照）。又、ＲＡＭ１１に格納された各転送トラフィック量は、後述する制約条件設計部１０４によって読み出され、制約条件の設定に用いられる。
制約条件設計部（制約条件設定部）１０４は、最適経路計算部１０２による経路決定に用いられる制約条件を設定する。この制約条件設計部１０４は、データリンクにおける現在のトラフィック量と要求フローｆの帯域情報とを用いて、要求フローｆやネットワーク２において既存の他フロー（設定済み他フロー）にそれぞれ与えられた品質要件に基づいて、これらの要求フローｆおよび設定済み他フローに対する制約条件式を設計する。

この制約条件設計部１０４は、要求フローｆによる個々のデータリンクに対するトラフィック影響に基づいて、要求フローｆ及びネットワーク２において既存の他フローに対するエンドツーエンド品質影響をそれぞれ推定する。そして、制約条件設計部１４は、要求フローｆ及び他フローのエンドツーエンド品質に関する線形制約方程式を制約条件として設定する。

すなわち、制約条件設計部１０４は、ネットワーク２の各データリンクにおける「負荷と遅延」および「負荷とパケットロス率」の関係モデルに基づき、要求フロー及び他フローのエンドツーエンドのロス率、遅延を線型方程式として近似定式化する。
図３は実施形態の一例としてのネットワーク管理システム１における制約条件設計部１０４による制約条件の設定手法を説明するための図であり、ネットワーク２のトポロジの構成例を模式的に示している。

この図３に示す例においては、先にフローａ１およびフローａ２の２つのフロー（他フロー，設定済み他フロー）が設定されている環境下で、ノードＡからノードＢへ到達する新たな要求フローｆの設定要求（フロー設定要求）が発生する状況を想定する。
ここで、設定済みの他フローａ１に対しては、エンドツーエンド遅延に対する品質要件として遅延Ｄ１が、又、エンドツーエンドロス率に対する品質要件としてロス率Ｌ１がそれぞれ与えられている。又、設定済みの他フローａ２に対しては、エンドツーエンド遅延に対する品質要件として遅延Ｄ２が、又、エンドツーエンドロス率に対する品質要件としてロス率Ｌ２が、それぞれ与えられている。

さらに、要求フローｆに対しても、フロー設定要求時に利用帯域Ｂｆ，エンドツーエンド遅延品質要件Ｄｆ及びエンドツーエンドロス率品質要件Ｌｆが、それぞれ与えられる。
制約条件設計部１０４は、要求フローｆに対し、後述する最適経路計算部１０２がリンクコスト値の総和が最小となる経路を特定する上で用いる、「要求フローに対する品質」と「他フローに対する品質影響」とを考慮した制約条件を設定する。

「要求フローに対する品質」を考慮した制約条件としては、要求フローに対するエンドツーエンド遅延、エンドツーエンドロス率に対する品質要件を満たすことが要求される。
また、「他フローに対する品質影響」を考慮した制約条件としては、設定済み他フロー対するエンドツーエンド遅延及びエンドツーエンドロス率に対する品質要件を満たすことが要求される。すなわち、フローａ１に対するエンドツーエンド遅延、エンドツーエンドロス率に対する品質要件を満たすことと、フローａ２に対するエンドツーエンド遅延、エンドツーエンドロス率に対する品質要件を満たすこととが要求される。

そして、本手法においては、制約条件設計部１０４は上記制約条件を線形式として設定し、最適経路計算部１０２が線形計画問題の一種として要求フローｆに対する最適経路計算を行なう。
具体的には、制約条件設計部１０４は、個々のノードにおける、「リンクトラフィック負荷とバッファリング遅延」および「リンクトラフィック量とロス率」の特性を推定・管理する。ここで、「リンクトラフィック負荷とバッファリング遅延」および「リンクトラフィック量とロス率」の特性は、例えば、Ｍ／Ｍ／１／Ｋに代表される待ち行列モデル等の品質変化予測関数を用いることで求めることができる。

すなわち、制約条件設計部１０４は、要求フローｆをデータリンクに割り当てることにより生じる品質影響（エンドツーエンド品質影響）を推定する、品質影響推定部としての機能もそなえる。
図４はリンクトラフィック負荷（リンク負荷）とバッファリング遅延との関係を示す図、図５はリンクトラフィック負荷（リンクトラフィック量）とロス率との関係を示す図である。

バッファリング遅延は、図４に示すような、リンクトラフィック負荷とバッファリング遅延との特性関数ｆ_ｄで表わされる。又、ロス率は、図５に示すような、リンクトラフィク負荷とロス率との特性関数f_ｌで表わされる。例えば、
ネットワーク機器のバッファ長：K（単位：packets）
平均パケット長：data（単位：bits）
要求フローｆがデータリンク（ｉ，ｊ）に流入したときの回線容量：Ci,j（単位：bps）
ここでは、各リンクのトラフィック量に応じて該当リンクの回線容量が動的に変化するノードなども本特許の対象として想定している。

リンク（ｉ，ｊ）の負荷：ρi,j［0〜1］＝転送トラフィック量（単位：bps）／Ci,j
とした場合に、バッファリング遅延ｆ_ｄは、例えば以下の式（１）で、又、ロス率f_ｌは、例えば以下の式（２）で、それぞれ表わすことができる。

さらに、これらの特性モデルを用いて、要求フローｆが各リンクを経由したと仮定したときのバッファリング遅延とロス率への品質変化量（エンドツーエンド品質影響）を予測する。すなわち、バッファリング遅延の品質変化量は、以下の式（３）に示すバッファリング遅延予測関数で表わされる。
ｆ_ｄ（Ｒ_ｉ，ｊ＋Ｂ_ｆ）・・・（３）
同様にロス率の品質変化量は、以下の式（４）に示すロス率予測関数で表わされる。

ｆ_ｌ（Ｒ_ｉ，ｊ＋Ｂ_ｆ）・・・（４）
ただし、Ｒ_ｉ，ｊは、データリンク（ｉ，ｊ）の転送トラフィック量（単位：bps）、すなわち、データリンク（ｉ，ｊ）における現在の負荷を表わす。従って、要求フローｆがデータリンク（ｉ，ｊ）を用いる場合には、
遅延増大＝ｆ_ｄ（Ｒ_ｉ，ｊ＋Ｂ_ｆ）
ロス率増大＝ｆ_ｌ（Ｒ_ｉ，ｊ＋Ｂ_ｆ）
となる。

すなわち、制約条件設定部１０４は、フローによるデータリンクにおけるトラフィック影響を品質変化予測関数に適用することにより、要求フロー及び他フローに対するエンドツーエンド品質影響を推定する。
なお、本実施形態においては、最適経路計算部１０２は、要求フローｆが各ノードiからノードjを繋ぐリンクを経由するか（Xij＝１）、しないか（Xij＝０）を数理演算で計算し、設計変数であるｘｉ，ｊを求めることにより最適経路を求める。

したがって、設計変数（Xiｊ）を導出するための制約条件は、設計変数（Xij）を用いた式として与えられる必要がある。なお，エンドツーエンド遅延やエンドツーエンドロス率は、個々のノードに対して予測した品質変化量と設計変数（Xij）とを用いて定式化することができる。
図６は実施形態の一例としてのネットワーク管理システムにおける要求フローに対する経路計算をするための目的関数と制約条件式とを説明するための図である。

目的関数は、各ノードｉからノードｊを繋ぐリンクに与えられたリンクコスト値Ｃ_ｉ，ｊと、設計変数（Xij）を用いて、以下の式（５）のように表わされる。

この式（５）に示す目的関数は、リンクコスト和を最小とする設計変数（Xij）を導出することを表す。
制約条件設計部１０４は、この目的関数に対して、以下の制約条件を設定する。
［要求フローに対する品質制約］

ただし、ｘｉ，ｊは要求フローｆについて、リンク（ｉ，ｊ）の利用有無∈｛０，１｝を表わす。
また、上記品質制約において、ｆ_ｄ（Ｒ_ｉ，ｊ＋Ｂ_ｆ）は、要求フローｆ自身の遅延増分を表わし、ｆ_ｌ（Ｒ_ｉ，ｊ＋Ｂ_ｆ）は、要求フローｆ自身のロス増分を表わす。
［フローａ１に対する品質制約］

上記品質制約において、ｆ_ｄ（Ｒ_ｉ，ｊ＋Ｂ_ｆ）−ｆ_ｄ（Ｒ_ｉ，ｊ）は、要求フローｆに影響されるフローａ１の遅延増分を表わし、ｆ_ｄ（Ｒ_ｉ，ｊ）は、フローａ１が現在経験しているリンク遅延を表わす。又、ｆ_ｌ（Ｒ_ｉ，ｊ＋Ｂ_ｆ）−ｆ_ｌ（Ｒ_ｉ，ｊ）は、要求フローｆに影響されるフローａ１のロス増分を表わし、ｆ_ｌ（Ｒ_ｉ，ｊ）は、フローａ１が現在経験しているリンクロスを表わす。

［フローａ２に対する品質制約］

そして、上述の如きフローａ１，ａ２に対する品質制約は、要求フローｆ以外の他フローに対する品質制約として、以下の式（６），（７）に示すように一般化して示すことができる。
［他フローに対する品質制約］
ｋはフローを識別するための情報（ｋは１以上の自然数）とする。

上記経路計算問題はすべて線形式で扱われ、最適な設計変数（Xij）を導出する０−１整数計画問題として解を導出することを可能にする。
また、上述の如く制約条件設計部１０４によって作成された品質制約条件は、ＲＡＭ１１に制約条件情報１１２として格納される。
最適経路計算部（経路決定部）１０２は、制約条件設計部１０４によって設定された品質制約条件を満たす範囲で、経路上の全リンクについてコスト定義テーブルに定義されているコスト総和が最小となる経路を、最適経路Ｘ∈｛０，１｝として決定する。すなわち、最適経路計算部１０２は、制約条件設計部１０４によって設定された制約条件を満たす範囲内で、複数のデータリンクの中から、要求フローに対する経路をなすデータリンクを決定する。

具体的には、最適経路計算部１０２は、上述した式（５）の目的関数により、リンクコスト和を最小とする設計変数（Xij）を導出する。
図７は実施形態の一例としてのネットワーク管理システム１における最適経路の表現方法を説明するための図であり、ネットワーク２のトポロジ例を示す図である。
最適経路Ｘは、例えば、以下に示すように、ネットワーク２中の全てのデータ経路を羅列した状態で、選択されたデータ経路に“１”を設定するとともに、被選択のデータ経路に“０”を設定することにより表す。

例えば、図７に示すネットワークトポロジにおいて、それぞれのノード間を接続するリンク情報は、
リンク変数Ｘ＝｛ｘ_Ａ，１，ｘ_１，Ａ，ｘ_Ａ，２，ｘ_２，Ａ，ｘ_Ｂ，１，ｘ_１，Ｂ，ｘ_Ｂ，２，ｘ_２，Ｂ，ｘ_Ｃ，１，ｘ_１，Ｃ，ｘ_Ｃ，２，ｘ_２，Ｃ｝
Ｘ∈｛０，１｝
と表される。

フロー経路決定部１１０は、要求フローｆが与えられる毎に、このリンク変数（０：要求フローは経由しない／１：要求フローは経由する）を決定する。
例えば、図７に示すネットワークトポロジにおいて、図中、矢印Ａで表される、ノードＡからノード１を経由してノードＣに至る経路、すなわち、リンクｘ_Ａ，１，ｘ_１，Ｃを経由する経路は、Ｘ＝｛１，０，０，０，０，０，０，０，０，１，０，０｝と表される。

最適経路計算部１０２は、上述の如く線形式として形成された経路計算問題を、０−１整数計画問題として解を導出することにより最適な設計変数（Xij）を導出し、最適経路Ｘを計算する
なお、この最適経路計算部１０２によるコスト総和に基づく最適経路の決定手法は、既知の種々の手法を用いて実現することができ、その詳細な説明については省略する。

経路設計部１０６は、最適経路計算部１０２による経路計算結果に基づき、その要求フローをネットワーク２に収容する。
設計履歴管理部１０３は、ネットワーク２に既に設定されているフローの経路情報や利用帯域、エンドツーエンド遅延、ロス率に対する品質要件を管理する。
この設計履歴管理部１０３は、最適経路計算部１０２によって決定された最適経路に関する情報を、経路履歴情報１１３としてＲＡＭ１１に格納する。具体的には、設計履歴管理部１０３は、要求フローｆを特定する識別情報と、その要求フローｆについて最適経路計算部１０２によって求められた最適経路Ｘとを対応付けて経路履歴情報１１３として格納する。

例えば、最適経路計算部１０２によって求められた、フローの最適経路Ｘ＝｛１，０，０，０，０，０，０，０，０，１，０，０｝は、ｙ^（ｋ）＝｛１，０，０，０，０，０，０，０，０，１，０，０｝として経路履歴情報１１３として格納される。
また、設計履歴管理部１０３は、要求フローｆについての利用帯域Ｂｆ、エンドツーエンド遅延に対する品質要件Ｄｆ及びロス率に対する品質要件Ｌｆを、フローｋについての、利用帯域Ｂｋ、エンドツーエンド遅延に対する品質要件Ｄｋ及びロス率に対する品質要件Ｌｋとして経路履歴情報１１３に格納し管理する。

そして、この設計履歴管理部１０３によって管理される情報は、新たな要求フローｆが与えられ、この要求フローｆの最適経路を決定する際に、設定済み他フローの情報として用いられる。
すなわち、新たなフローに対する経路を決定するに際して、制約条件設定部１０４が、ＲＡＭ１１に格納された経路履歴情報１１３を、既存の他フローに対するエンドツーエンド品質影響の推定に用いる。

なお、そのフローが処理された際には、経路履歴情報１１３から当該フローについての情報が削除されることが望ましい。
制約条件設計部１０４は、経路離脱が発生する度に、エンドツーエンド品質影響を経路計算に対する制約条件として削除する。
ここで、本実施形態の一例としてのネットワーク管理システムにおける経路設定手法を、図９を参照しながら図８に示すフローチャート（ステップＡ１０〜Ａ３０）に従って説明する。なお、図９は各フローの最適経路とその経路履歴情報１１３の使用方法を示す図である。又、この図８に示す例においては、図７に示すネットワークトポロジに対してフロー１〜３の３つの要求フローｆを順番に経路設定する例について説明する。

図７に示すような、トラフィックの入口・出口となるノードＡ、Ｂ、Ｃと、トラフィックを中継するノード１、２から構成されるトポロジとにおいて、それぞれのノード間を接続するリンク情報は、上述の如く、
リンク変数Ｘ＝｛ｘ_Ａ，１，ｘ_１，Ａ，ｘ_Ａ，２，ｘ_２，Ａ，ｘ_Ｂ，１，ｘ_１，Ｂ，ｘ_Ｂ，２，ｘ_２，Ｂ，ｘ_Ｃ，１，ｘ_１，Ｃ，ｘ_Ｃ，２，ｘ_２，Ｃ｝
で表される。

（１）１つ目のフロー（ステップＡ１０）
まず、ネットワーク２上にフローが何も収容されていない環境下で、1つ目のフローが設定される過程を示す。
利用帯域Ｂ１、エンドツーエンド遅延品質要件Ｄ１、エンドツーエンドロス率品要件Ｌ１を持つ、ノードＡからノードＣまで到達するフロー１が要求されたものとする。

制約条件設計部１０４は、このフロー１の品質制約条件を生成する。

また、最適経路計算部１０２は、その制約条件を満たす範囲で、

により、リンクコスト値ｃ_ｉ，ｊの和を最小とするフロー１の経路を導出する。
図９に示す例においては、最適経路Ｘ＝｛１，０，０，０，０，０，０，０，０，１，０，０｝が導出されている。この結果は、データリンクｘ_Ａ,１，ｘ_１，Ｃをフロー１が経由することを意味する。
管理サーバ１０においては、経路設計部１０６が、この経路計算結果に従い、フロー１をネットワークに収容する。又、設計履歴管理部１０３が、経路情報を、Ｙ^(１)＝｛１，０，０，０，０，０，０，０，０，１，０，０｝として履歴管理する。

（２）２つ目のフロー（ステップＡ２０）
フロー１が設定済み他フローとなり、更に、利用帯域Ｂ２、エンドツーエンド遅延品質要件Ｄ２、エンドツーエンドロス率品要件Ｌ２を持つ、ノードＡからノードＢまで到達するフロー２が要求されたものとする。

制約条件設計部１０４は、このフロー２の品質制約条件を生成する。

さらに制約条件設計部１０４は、フロー１に対する品質制約条件を生成する。

また、最適経路計算部１０２は、既に設定済みのフロー１と要求フロー２の制約条件を満たす範囲で、

により、リンクコスト値ｃ_ｉ，ｊの和を最小とするフロー２の経路を導出する。
図９に示す例においては、最適経路Ｘ＝｛１，０，０，０，０，１，０，０，０，０，０，０｝が導出されている。この結果は、データリンクｘ_Ａ,１，ｘ_１，Ｂをフロー２が経由することを意味する。
管理サーバ１０においては、経路設計部１０６が、この経路計算結果に従い、フロー２をネットワークに収容する。又、設計履歴管理部１０３が、経路情報を、Ｙ^（２）＝｛１，０，０，０，０，１，０，０，０，０，０，０｝として履歴管理する。

（３）３つ目のフロー（ステップＡ３０）
フロー１，２が設定済み他フローとなり、更に、利用帯域Ｂ３、エンドツーエンド遅延品質要件Ｄ３、エンドツーエンドロス率品要件Ｌ３を持つ、ノードＢからノードＣまで到達するフロー３が要求されたものとする。

制約条件設計部１０４は、このフロー３の品質制約条件を生成する。

さらに制約条件設計部１０４は、フローｋ（ｋ＝１，２）に対する品質制約条件を生成する。

また、最適経路計算部１０２は、要求フロー３の制約条件と、既に設定済みのフロー１，２の制約条件を満たす範囲で、

により、リンクコスト値ｃ_ｉ，ｊの和を最小とするフロー３の経路を導出する。
図９に示す例においては、最適経路Ｘ＝｛０，０，０，０，０，０，０，１，０，０，１，０｝が導出されている。この結果は、データリンクｘ_Ｂ,２，ｘ_２，Ｃをフロー３が経由することを意味する。
管理サーバ１０においては、経路設計部１０６が、この経路計算結果に従い、フロー３をネットワークに収容する。又、設計履歴管理部１０３が、経路情報を、Ｙ^（３）＝｛０，０，０，０，０，０，０，１，０，０，１，０｝として履歴管理する。

上述の如く構成された実施形態の一例としてのネットワーク管理システム１における、要求フローｆに対する経路設定処理の流れを、図１０に示すフローチャート（ステップＢ１０〜Ｂ５０）に従って説明する。
管理サーバ１０は、ネットワーク２における送信元ノードから要求フローを受け付けると（ステップＢ１０）、制約条件設計部１０４が、各データリンクにおけるバッファリング遅延やパケットロス率を推定する（ステップＢ２０）。すなわち、制約条件設計部１０４は、要求フローfに対する経路がリンク（i，ｊ）に収容されたと仮定したときの、リンク（i，ｊ）で発生するバッファリング遅延とパケットロス率とを見積る。

これらのバッファリング遅延やパケットロス率は、例えば、Ｍ／Ｍ／１／Ｋに代表される待ち行列モデルや、予め実測データに基づいて構築したテーブルを用いることにより求めることができる。
次に、制約条件設計部１０４は、そのネットワーク２において、その時点までに設計されている全ての経路に対する、エンドツーエンド経路毎の遅延及びパケットロス率にかかる制約条件を生成する（ステップＢ３０：制約条件設定ステップ）。なお、このステップＢ３０の詳細な処理については後述する（図１１参照）。

そして、最適経路計算部１０２が、制約条件設計部１０４によって設定された品質制約条件を満たす範囲で、経路上の全リンクについてコスト定義テーブルに定義されているコスト総和が最小となる経路を、最適経路として決定する（ステップＢ４０：経路決定ステップ）。
経路設計部１０６は、この最適経路計算部１０２によって決定された最適経路をネットワーク２に設定する（ステップＢ５０）。又、決定された最適経路に関する情報はＲＡＭ１１の経路履歴情報１１３として格納される（経路履歴情報格納ステップ）。その後、処理は終了される。

次に、本実施形態の一例としてのネットワーク管理システム１における制約条件の設計手法を、図１１に示すフローチャート（ステップＣ１０〜Ｃ７０）に従って説明する。
制約条件設計部１０４は、状態計測部１０５から、ネットワーク２を構成する全てのデータリンクについて、その時点におけるリンク利用量（転送トラフィック量）をそれぞれ読み込む（ステップＣ１０）。又、制約条件設計部１０４は、送信元ノードからの要求フローｆから、利用帯域情報Ｂｆを読み込む（ステップＣ２０）。

制約条件設計部１０４は、要求フローｆがそのデータリンクを利用した場合のバッファリング遅延及びロス率の変化量を推定する（ステップＣ３０）。又、制約条件設計部１０４は、ネットワーク２において既に設定済みのフロー（設定済み他フロー）に関する経路履歴情報１１３を、ＲＡＭ１１から読み込む（ステップＣ４０）。
そして、制約条件設計部１０４は、要求フローｆに対する、エンドツーエンド遅延の制約条件及びエンドツーエンドロス率の制約条件を生成する（ステップＣ５０）。又、制約条件設計部１０４は、ネットワーク２における設定済み他フローに対する、エンドツーエンド遅延の制約条件及びエンドツーエンドロス率の制約条件を生成する（ステップＣ６０）。

制約条件設計部１０４は、ステップＣ５０及びステップＣ６０においてそれぞれ生成した制約条件を、制約条件として最適経路計算部１０２に受け渡す（ステップＣ７０）。
図１２はネットワーク２のトポロジの構成例を示す図、図１３は図１２に示すトポロジに関して、本管理システム１において生成されるデータをテーブル状に例示する図である。

図１２に例示するトポロジは、ノードＡとノードＢとの間にノード１及びノード２が並列に配置されている。又、この図１２に示す例においては、データリンクｘ_Ａ,１をＬｉｎｋ１、データｘ_１，ＢをＬｉｎｋ２，データリンクｘ_Ａ,２をＬｉｎｋ３、データｘ_２，ＢをＬｉｎｋ４と、それぞれ表わしている。
また、この図１２に示す例においては、各Ｌｉｎｋ１〜４の最大容量は１００Ｍｂｐｓであるものとする。又、Ｌｉｎｋ１に３０Mbpsのトラフィック量が流れており、同様に、Ｌｉｎｋ２に６０Mbps、Ｌｉｎｋ３に５０Mbps、Ｌｉｎｋ４に７５Mbpsのトラフィック量が流れている。

そして、この図１２に示すネットワーク２に、送信元ノードＡから送信先ノードＢに対して、利用帯域１０Mbpsの要求フローｆの設定要求が行なわれたものとする。
図１３は実施形態の一例としてのネットワーク管理システム１において生成されるリンク属性情報１１４を例示する図である。このリンク属性情報１１４は、上述した制約条件設計部１０４が品質制約条件の設定を行なうに際して生成される種々の情報であり、図１３に示す例においては、これらの情報をテーブル状に示している。制約条件設計部１０４は、これらの情報を、逐次、ＲＡＭ１１の所定の領域に格納する。

この図１３に示す例においては、リンク属性情報１１４は、リンク属性として、「リンク容量」，「現在の転送トラフィック量」，「現在の遅延量」，「現在のロス率」，「フロー要求時 トラフィック量増分」，「フロー要求時 予測トラフィック量」，「フロー要求時 予測遅延量」，「フロー要求時 予測遅延量 増分」，「フロー要求時 予測ロス率」及び「フロー要求時 予測ロス率増分」をそなえている。

ここで、「現在の遅延量」及び「現在のロス率」は、制約条件設計部１０４が、例えば、Ｍ／Ｍ／１／Ｋに代表される待ち行列モデルの遅延量に関する関数ｆ_ｄ（ρ_ｉ）に対して、「現在の転送トラフィック量」を適用することにより求める。
「フロー要求時 予測遅延量」は、制約条件設計部１０４が、「現在の転送トラフィック量」に「フロー要求時 トラフィック量増分」を加算することにより求められる。

「フロー要求時 予測遅延量」は、制約条件設計部１０４が、例えば、Ｍ／Ｍ／１／Ｋに代表される待ち行列モデルの遅延量に関する関数ｆ_ｄ（ρ_ｉ）に対して、「フロー要求時 予測トラフィック量」を適用することにより求める。
「フロー要求時 予測遅延量 増分」は、制約条件設計部１０４が、「フロー要求時 予測遅延量」から「現在の遅延量」を減算することにより求める。

「フロー要求時 予測ロス率」は、制約条件設計部１０４が、例えば、Ｍ／Ｍ／１／Ｋに代表される待ち行列モデルの遅延量に関する関数ｆ_ｌ（ρ_ｉ）に対して、「フロー要求時 予測トラフィック量」を適用することにより求める。
「フロー要求時 予測ロス率増分」は、制約条件設計部１０４が、「フロー要求時 予測ロス率」から「現在のロス率」を減算することにより求める。

そして、経路履歴情報１１３は、これらの情報（リンク特性）を、ネットワーク２を構成するデータリンク毎にそなえる。
実施形態の一例としてのネットワーク管理システム１の制約条件設計部１０４による制約条件の生成手法を、図１４に定式化して表わす。なお、ネットワーク２のノード集合をＶ，ネットワーク２のリンク集合をＥとする。

制約条件設計部１０４は、フローｆの受付と、フローｆに対する品質要件、さらには各リンクのバッファ遅延特性／ロス特性を設定する。すなわち、
Ｂｆ：フローｆのトラフィックデマンド
Ｄｆ：フローｆに対するエンドツーエンド遅延上限
Ｌｆ：フローｆに対するエンドツーエンドロス上限
ｆ_ｄ（ρ_ｉ，ｊ）／ｆ_ｌ（ρ_ｉ，ｊ）：リンク（ｉ，ｊ）間の負荷ρ_ｉ，ｊに対するバッファ遅延関数／ロス関数である。

最適経路計算部１０２は、要求フローｆに対する最適経路設として以下の式を生成する。すなわち、
ｘ_ｉ，ｊ∈｛０，１｝ｆｏｒ（ｉ，ｊ）∈Ｅ：フローｆに対するリンク（ｉ，ｊ）間の転送有無
ｃ_ｉ，ｊ ｆｏｒ（ｉ，ｊ）∈Ｅ：リンク（ｉ，ｊ）間のリンクコスト
Ｒ_ｉ，ｊ （ｉ，ｊ）∈Ｅ：リンクｉ，ｊ間の現在の利用トラフィック量
とし、更に

とする。
ここで、現状のネットワーク２の状態を基準としたフローｆに対する品質制約に基づく制約条件（s.t.）は以下のようにすることができる。
先ず、要求フローｆ（トラフィック量Ｂｆ）の始点ノードｓと終点ノードｄとにおいて流量の総量が保存されることに基づき（流量保存条件）、
フロー収容制約を、
ｆｏｒ ｓ：source ｄ：destination

とし、又、フロー保存制約を、

とする。
また、遅延制約を、

とし、ロス制約を、

とする。更に、設定済みフローgk（k＝1，・・・，M）に対するリンク（ｉ，ｊ）間の転送有無を

とする。又、
設定済みフローgkのトラフィックデマンドを、Ｂ_ｇｋ
設定済みフローgkに対するエンドツーエンド遅延上限を、Ｄ_ｇｋ
設定済みフローgkに対するエンドツーエンドロス上限を、Ｌ_ｇｋ
エンドツーエンド遅延制約を、

とし、エンドツーエンドロス制約を、

とする。
なお、上述した最適経路計算部１０２，設計履歴管理部１０３，制約条件設計部１０４，状態計測部１０５及び経路設計部１０６としての機能を実現するためのプログラム（ネットワーク管理プログラム）は、例えばフレキシブルディスク，ＣＤ（ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ等），ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−ＲＡＭ，ＤＶＤ−Ｒ，ＤＶＤ＋Ｒ，ＤＶＤ−ＲＷ，ＤＶＤ＋ＲＷ，ＨＤ ＤＶＤ等），ブルーレイディスク，磁気ディスク，光ディスク，光磁気ディスク等の、コンピュータ読取可能な記録媒体に記録された形態で提供される。そして、コンピュータはその記録媒体からプログラムを読み取って内部記憶装置または外部記憶装置に転送し格納して用いる。又、そのプログラムを、例えば磁気ディスク，光ディスク，光磁気ディスク等の記憶装置（記録媒体）に記録しておき、その記憶装置から通信経路を介してコンピュータに提供するようにしてもよい。

最適経路計算部１０２，設計履歴管理部１０３，制約条件設計部１０４，状態計測部１０５及び経路設計部１０６としての機能を実現する際には、内部記憶装置（本実施形態ではＲＡＭ１１やＲＯＭ１２）に格納されたプログラムがコンピュータのマイクロプロセッサ（本実施形態ではＣＰＵ１０１）によって実行される。このとき、記録媒体に記録されたプログラムをコンピュータが読み取って実行するようにしてもよい。

なお、本実施形態において、コンピュータとは、ハードウェアとオペレーティングシステムとを含む概念であり、オペレーティングシステムの制御の下で動作するハードウェアを意味している。又、オペレーティングシステムが不要でアプリケーションプログラム単独でハードウェアを動作させるような場合には、そのハードウェア自体がコンピュータに相当する。ハードウェアは、少なくとも、ＣＰＵ等のマイクロプロセッサと、記録媒体に記録されたコンピュータプログラムを読み取るための手段とをそなえており、本実施形態においては、管理サーバ１０がコンピュータとしての機能を有しているのである。

このように、実施形態の一例としてのネットワーク管理システム１によれば、新たに追加要求されたフローに対し、既に設定済のフローを含む各フローに対するエンドツーエンド品質要件を満たし、且つ、リンクコスト和が最小となる最適な経路を決定することができる。
また、制約条件設計部１０４が、ネットワーク２の各データリンクにおける「負荷と遅延」および「負荷とパケットロス」の関係モデルに基づき、要求フロー及び他フローのエンドツーエンドのロス率、遅延を線型方程式として定式化する。

これにより、最適経路計算部１０２は、リンクコストの総和が最小となる経路を特定する線形目的関数と線形制約式とを用いて、０−１整数計画問題に帰着して経路計算を行なう。これにより計算量を軽減し短時間で最適経路を計算することができる。特に、ノード数が多いネットワークにおいても、短時間で最適経路を計算することができる。
そして、開示の技術は上述した実施形態に限定されるものではなく、本実施形態の趣旨を逸脱しない範囲で種々変形して実施することができる。

以上の実施形態に関し、更に以下の付記を開示する。
（付記１）
データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する経路決定装置であって、
該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定部と、
該制約条件設定部により設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定部とをそなえることを特徴とする、経路決定装置。

（付記２）
該制約条件設定部が、該フローによる個々の該データリンクに対するトラフィック影響に基づいて、該フロー及び該ネットワークにおいて既存の他フローに対するエンドツーエンド品質影響をそれぞれ推定し、該フロー及び該他フローのエンドツーエンド品質に関する線形制約方程式を制約条件として設定し、
該経路決定部が、該制約条件を満たす範囲内で、複数の該データリンクの中から、該フローに対する該経路をなすデータリンクを決定することを特徴とする、付記１記載の経路決定装置。
（付記３）
該制約条件設定部が、該フローによる該データリンクにおけるトラフィック影響を品質変化予測関数に適用することにより、該フロー及び該他フローに対するエンドツーエンド品質影響を推定することを特徴とする、付記１又は付記２記載の経路決定装置。

（付記４）
該制約条件設定部が、該フローに対する経路を決定する度に、該フロー及び該他フローに対するエンドツーエンド品質影響に基づく該制約条件を設定することを特徴とする、付記１〜付記３のいずれか１項に記載の経路決定装置。
（付記５）
該経路決定部によって決定された、該フローに対する該経路をなすデータリンクに関する情報を経路履歴情報として格納する経路履歴情報格納部をそなえ、
新たなフローに対する経路を決定するに際して、該制約条件設定部が、該経路履歴情報格納部に格納された該経路履歴情報を、該既存の他フローに対するエンドツーエンド品質影響の推定に用いることを特徴とする、付記１〜付記４のいずれか１項に記載の経路決定装置。

（付記６）
該制約条件設定部が、経路離脱が発生する度に、エンドツーエンド品質影響を経路計算に対する制約条件として削除することを特徴とする、付記１〜付記５のいずれか１項に記載の経路決定装置。
（付記７）
該品質要件がエンドツーエンド遅延時間であることを特徴とする、付記１〜付記６のいずれか１項に記載の経路決定装置。

（付記８）
該品質要件がエンドツーエンドデータロス率であることを特徴とする、付記１〜付記７のいずれか１項に記載の経路決定装置。
（付記９）
データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する経路決定方法であって、
該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定ステップと、
該制約条件設定ステップにおいて設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定ステップとをそなえることを特徴とする、経路決定方法。

（付記１０）
該制約条件設定ステップにおいて、該フローによる個々の該データリンクに対するトラフィック影響に基づいて、該フロー及び該ネットワークにおいて既存の他フローに対するエンドツーエンド品質影響をそれぞれ推定し、該フロー及び該他フローのエンドツーエンド品質に関する線形制約方程式を制約条件として設定し、
該経路決定ステップにおいて、該制約条件を満たす範囲内で、複数の該データリンクの中から、該フローに対する該経路をなすデータリンクを決定することを特徴とする、付記９記載の経路決定方法。

（付記１１）
該制約条件設定ステップにおいて、該フローによる該データリンクにおけるトラフィック影響を品質変化予測関数に適用することにより、該フロー及び該他フローに対するエンドツーエンド品質影響を推定することを特徴とする、付記９又は付記１０記載の経路決定方法。

（付記１２）
該制約条件設定ステップにおいて、該フローに対する経路を決定する度に、該フロー及び該他フローに対するエンドツーエンド品質影響に基づく該制約条件を設定することを特徴とする、付記９〜付記１１のいずれか１項に記載の経路決定方法。
（付記１３）
該経路決定ステップにおいて決定された、該フローに対する該経路をなすデータリンクに関する情報を、経路履歴情報格納部に経路履歴情報として格納する経路履歴情報格納ステップをそなえ、
新たなフローに対する経路を決定するに際して、該制約条件設定ステップにおいて、該経路履歴情報格納部に格納された該経路履歴情報を、該既存の他フローに対するエンドツーエンド品質影響の推定に用いることを特徴とする、付記９〜付記１２のいずれか１項に記載の経路決定方法。

（付記１４）
該制約条件設定ステップにおいて、経路離脱が発生する度に、エンドツーエンド品質影響を経路計算に対する制約条件として削除することを特徴とする、付記９〜付記１３のいずれか１項に記載の経路決定方法。
（付記１５）
該品質要件がエンドツーエンド遅延時間であることを特徴とする、付記９〜付記１４のいずれか１項に記載の経路決定方法。

（付記１６）
該品質要件がエンドツーエンドデータロス率であることを特徴とする、付記９〜付記１５のいずれか１項に記載の経路決定方法。
（付記１７）
データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する機能をコンピュータに実行させるための経路決定プログラムであって、
該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定部と、
該制約条件設定部により設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定部として、該コンピュータを機能させることを特徴とする、経路決定プログラム。

（付記１８）
該制約条件設定部が、該フローによる個々の該データリンクに対するトラフィック影響に基づいて、該フロー及び該ネットワークにおいて既存の他フローに対するエンドツーエンド品質影響をそれぞれ推定し、該フロー及び該他フローのエンドツーエンド品質に関する線形制約方程式を制約条件として設定し、
該経路決定部が、該制約条件を満たす範囲内で、複数の該データリンクの中から、該フローに対する該経路をなすデータリンクを決定するように、該コンピュータを機能させることを特徴とする、付記１７記載の経路決定プログラム。

１ ネットワーク管理システム
２ ネットワーク
１０ 管理サーバ（経路決定装置）
１１ ＲＡＭ
１２ ＲＯＭ
１３ 表示装置
１４ 入力装置
１５ 記憶装置
１０１ ＣＰＵ
１０２ 最適経路計算部（経路決定部）
１０３ 設計履歴管理部
１０４ 制約条件設計部（制約条件設定部）
１０５ 状態計測部
１０６ 経路設計部
１１０ フロー経路決定部
１１１ コスト定義テーブル
１１２ 制約条件情報
１１３ 経路履歴情報
１１４ リンク属性情報

Claims (10)

1. データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する経路決定装置であって、
   該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定部と、
   該制約条件設定部により設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定部とをそなえることを特徴とする、経路決定装置。
2. 該制約条件設定部が、該フローによる個々の該データリンクに対するトラフィック影響に基づいて、該フロー及び該ネットワークにおいて既存の他フローに対するエンドツーエンド品質影響をそれぞれ推定し、該フロー及び該他フローのエンドツーエンド品質に関する線形制約方程式を制約条件として設定し、
   該経路決定部が、該制約条件を満たす範囲内で、複数の該データリンクの中から、該フローに対する該経路をなすデータリンクを決定することを特徴とする、請求項１記載の経路決定装置。
3. 該制約条件設定部が、該フローによる該データリンクにおけるトラフィック影響を品質変化予測関数に適用することにより、該フロー及び該他フローに対するエンドツーエンド品質影響を推定することを特徴とする、請求項１又は請求項２記載の経路決定装置。
4. 該制約条件設定部が、該フローに対する経路を決定する度に、該フロー及び該他フローに対するエンドツーエンド品質影響に基づく該制約条件を設定することを特徴とする、請求項１〜請求項３のいずれか１項に記載の経路決定装置。
5. 該経路決定部によって決定された、該フローに対する該経路をなすデータリンクに関する情報を経路履歴情報として格納する経路履歴情報格納部をそなえ、
   新たなフローに対する経路を決定するに際して、該制約条件設定部が、該経路履歴情報格納部に格納された該経路履歴情報を、該既存の他フローに対するエンドツーエンド品質影響の推定に用いることを特徴とする、請求項１〜請求項４のいずれか１項に記載の経路決定装置。
6. 該制約条件設定部が、経路離脱が発生する度に、エンドツーエンド品質影響を経路計算に対する制約条件として削除することを特徴とする、請求項１〜請求項５のいずれか１項に記載の経路決定装置。
7. 該品質要件がエンドツーエンド遅延時間であることを特徴とする、請求項１〜請求項６のいずれか１項に記載の経路決定装置。
8. 該品質要件がエンドツーエンドデータロス率であることを特徴とする、請求項１〜請求項７のいずれか１項に記載の経路決定装置。
9. データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する経路決定方法であって、
   該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定ステップと、
   該制約条件設定ステップにおいて設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定ステップとをそなえることを特徴とする、経路決定方法。
10. データリンクを介して接続される複数のノードを有するネットワークにおいて、フローに対する経路を決定する機能をコンピュータに実行させるための経路決定プログラムであって、
    該データリンクに該フローを割り当てることにより当該データリンクにおいて生じる品質変化に基づき、該フローのエンドツーエンドの品質要件を満たしていることと、該データリンクに該フローを割り当てることにより当該データリンクにおいて既存の他フローに生じる品質変化に基づき、該他フローのエンドツーエンドの品質要件を満たしていることとを要件とする制約条件を生成する制約条件設定部と、
    該制約条件設定部により設定された該制約条件を満たす範囲内で、複数の該データリンクにより構成される複数の経路の中から、該フローに対する該経路を決定する経路決定部として、該コンピュータを機能させることを特徴とする、経路決定プログラム。

Images