(57)【特許請求の範囲】
【請求項１】
データリンクを介して接続される複数のノードを有し現存のルーティングプロトコルを利用するネットワーク中のデータトラフィックを制御する方法であって、
−データパスを選択し、
−選択されたデータパスの上限リンク利用率、平均リンク利用率、または上限リンク利用率と平均リンク利用率との組み合わせを示す値のうち１つ以上に基づいて、選択されたデータパスの利用率を決定し、
−最適データパスを特定するための線形最適化問題のための方程式系を定め、
−方程式系を解くことにより、選択されたデータパスの最小上限リンク利用率、最小平均リンク利用率、または上限リンク利用率と平均リンク利用率との組み合わせを示す最小値のうち１つ以上を有する選択されたデータパスの１つを、最適データパスと定め、
−送信ノードから最適データパスを経て受信ノードへデータを通信することを含み、
−データパスの選択に先立って送信ノードから受信ノードへの各データリンクおよびノードを経由するすべてのループなしデータパスを決定し、
−２つのノード間で通信されるべきすべてのデータが同一のデータパスを経て通信されることを保証する線形最適化問題のルーティング制約を定め、
−ネットワークの現存のルーティングプロトコルに従い２つのノード間で同一のデータパスを経てすべてのデータを通信することを特徴とする方法。
【請求項２】
データパスの選択が、
−データパスのデータ通信容量の決定と、前記送信ノードから前記受信ノードに通信されるべきデータの量以上の上限データ通信容量を有するデータパスの選択とを含む、請求項１に記載の方法。
【請求項３】
データパスの選択が、
−データパスの物理的遅延の決定と、所定の上限物理的遅延以下の物理的遅延を有するデータパスの選択とを含む、請求項１または２に記載の方法。
【請求項４】
前記方程式系の定義が、
−選択されたデータパスの利用率を表わす項を含む目的関数の定義を含む請求項１〜３の１つに記載の方法。
【請求項５】
前記方程式系の定義が、
−選択されたデータパスの各々の利用率についてのコスト制約を定めることを含む請求項１〜４の１つに記載の方法。
【請求項６】
前記方程式系の定義が、
−フローの維持及び／又はループなしデータパスの決定のための目的関数の平均リンク利用率部分と共にトランスポート制約を定めることを含む請求項１〜５の１つに記載の方法。
【請求項７】
前記方程式系の定義が、
−前記送信ノードから前記受信ノードに通信されるべきデータの量以上の上限データ通信容量を有するデータパスを決定する容量制約を定めることを含む、請求項１〜６の１つに記載の方法。
【請求項８】
前記方程式系の定義が、
−各データリンクについて、所定の上限物理的遅延以下の物理的遅延を有するデータパスを決定する物理的遅延制約を定めることを含む、請求項１〜７の１つに記載の方法。
【請求項９】
−平均リンク利用率及び／又は上限リンク利用率の組み合わせが互いに重み付けされた平均リンク利用率及び／又は上限リンク利用率を含む関数によって表わされる請求項１〜８の１つに記載の方法。
【請求項１０】
−選択されたデータパスのうち予め定められた範囲の利用率を有するものが最適データパスの選択のために考慮されるものとして特定される請求項１〜９の１つに記載の方法。
【請求項１１】
−−現在の前記方程式系を解くことができない場合、
−−目的関数について最小値が決定されない場合、または
−−目的関数が収束しない場合、
−所定の時間内に決定される前記方程式系の最後の解が最適データパスを特定する請求項１〜１０の１つに記載の方法。
【請求項１２】
−−前記送信ノードから前記受信ノードへの全てのループなしデータパスについてデータ通信のための時間を決定し、
−−最小データ通信時間及び／または所定の上限データ通信時間より小さいデータ通信時間を決定する前記方程式系を解くために考慮されるべきデータパスを識別することと、
−によって前記方程式系の変数の数が低減されかつ／または前記方程式系を解くために考慮されるべきデータリンクが決定される、請求項１〜１１の１つに記載の方法。
【請求項１３】
−全ての可能なデータパスに含まれるデータリンクが前記方程式系を解くために考慮され、かつ／または
−前記可能なデータリンクのどれにも含まれないデータリンクが前記方程式系を解くために考慮されない、請求項１２に記載の方法。
【請求項１４】
−前記物理的遅延制約が、前記ネットワークの前記ノード間の前記データリンクについての所定のデータ通信時間によって定められ、かつ／または
−前記物理的遅延制約が、データの帯域幅を各物理的遅延に変換することによって定められる、請求項１〜１３の１つに記載の方法。
【請求項１５】
データリンクを介して接続される複数のノードを有し現存のＩＰルーティングプロトコルを利用するネットワーク中のデータトラフィックを制御する方法であって、
−データパスを選択し、
−選択されたデータパスの上限リンク利用率、平均リンク利用率、または上限リンク利用率と平均リンク利用率との組み合わせを示す値のうち１つ以上に基づいて、線形最適化問題に基づく選択されたデータパスの利用率を決定し、
−選択されたデータパスの最小上限リンク利用率、最小平均リンク利用率、または上限リンク利用率と平均リンク利用率との組み合わせを示す最小値のうち１つ以上を有する選択されたデータパスの１つを、最適データパスとして定め、
−最適データパスを介して送信ノードから受信ノードへデータを通信することを含み、
−データパスの選択に先立って各データリンクおよびノードを経由する送信ノードから受信ノードへのすべてのループなしデータパスを決定し、
−２つのノード間で通信されるべきすべてのデータが同一のデータパスを経て通信されることを保証する線形最適化問題のルーティング制約を定め、
−ネットワークの現存のＩＰルーティングプロトコルに従い２つのノード間で同一のデータパスを経てすべてのデータを通信することを特徴とする方法。
【請求項１６】
−選択されたデータパスのうち他のデータパスの利用率の値の合計よりも大きい利用率の値の合計を有するものが最適データパスとして選択される請求項１５記載の方法。
【請求項１７】
−コスト制約は、最適データパスの利用率が最適データパス以外の選択されたデータパスのすべてについての利用率よりも小さくなるように最適データパス以外の選択されたデータパスのすべてについて定められる請求項１５または１６記載の方法。
【請求項１８】
−コスト制約は、最適データパス以外の選択されたデータパスであって最適データパスの送信ノードに隣接するノードから始まり最適データパスの受信ノードで終わり、最適データパスのノードをさらに含まないものについて定められ、
−最適データパス以外の選択されたデータパスの残りについてはコスト制約が定められない請求項１５〜１７の１つに記載の方法。
【請求項１９】
−前記最適データパスの決定が、連続的に、または所定の回数で、または所定の時間間隔で行われる一方、通信されるべきデータの量が連続的に、または所定の回数で、または所定の時間間隔で決定される、請求項１〜１８の１つに記載の方法。
【請求項２０】
−前記最適データパスの決定が、通信されるべき所定または上限量のデータについて行われる、請求項１〜１９の１つに記載の方法。
【請求項２１】
−利用率の値が、前記ネットワークの異なったノードを含むデータリンクについてのみ決定され、かつ／または
−前記最適データパスの識別が、前記ネットワークの少なくとも２つの部分について個別に行われ、かつ／または
−前記ネットワークの少なくとも一部が仮想ノードにグループ化され、前記ネットワークの前記グループ化された部分の最適データパスと、前記仮想ノードを含む前記ネットワークの残りの部分の最適データパスとが個別に識別される、請求項１〜２０の１つに記載の方法。
【請求項２２】
最適データパスを介してネットワーク中でデータを通信するシステムであって、前記システムが、
−データリンクによって接続されるノードを有するネットワークであって、前記ノードの少なくとも１つが送信ノードであり前記ノードの少なくとも１つが受信ノードであるネットワークと、
−前記ネットワーク中のデータ通信を制御するため前記ネットワークに接続される制御手段とを含み、
−前記制御手段が請求項１〜２１の１つに記載の方法を実行するよう構成されるシステム。
【発明の詳細な説明】
【０００１】
発明の分野
本発明はネットワーク中でデータの通信を制御する方法とシステムに関する。特に、本発明は、データリンクを介して接続される複数のノードを有するネットワーク中の送信ノードから受信ノードへの最適データパスを介してデータを通信する方法とシステムであって、ネットワーク中のデータ通信のために使用される最適データパスが、最小のリンクコストを与えるデータパスとして定められる方法とシステムに関する。
【０００２】
発明の背景
ネットワーク中のデータ通信では、通信されるべきデータはネットワークを通じてルーティングされる、すなわち、データまたはそのデータパケットは、データ送信ノードからデータ受信ノードにネットワークのデータリンクを介して導かれる。ネットワークのデータリンクを介しデータリンクによって接続されるネットワークのノード間でデータを正しくルーティングするため、ルーティング戦略またはルーティング戦略を表すいわゆるルーティングプロトコルが利用される。最も普及したルーティングプロトコルは、ルーティング情報プロトコル（ＲＩＰ）、拡張インターネットゲートウェイルーティングプロトコル（ＥＩＧＲＰ）及びオープンショーテストパスファースト（ＯＳＰＦ）プロトコルである。これらのプロトコルは、共通ネットワーク管理下にあるネットワーク中でデータをルーティングするいわゆる内部ゲートウェイプロトコルとして使用される。データネットワーク（例えば、インターネット）は、固定通信接続を有するネットワーク（例えば、電話ネットワーク）と対照的に、送信ノードと受信ノードとの間に予め定められたデータパス／コネクションを有さない。内部ルーティングプロトコルは一般に、送信ノードから受信ノードへのデータ通信が予め定められたデータリンク及びネットワークのノードを介して行われないというアプローチに基づいている。その代わり、データまたはデータパッケージが１つのノードから別のノードに通信される際に、次のノードへのどのデータリンクを選択すべきかというルーティングの各決定は、各ノードによって別々に「作り上げ」られる。従って、データを他のノード／ルータに伝送するルータとも呼ばれるノードには、送信ノードから受信ノードへデータを通信するデータパスを形成する全体のデータパスまたはデータリンクが「わからない」。各ノード／ルータは、データまたはデータパッケージが伝送可能な次のノード／ルータはどれかというルーティング情報に応じて自分でルーティング決定を行う。その結果、ルーティング決定、すなわちデータが伝送される次のノード／ルータの決定は、それぞれのデータを通信するノード／ルータによってローカルでなされる。
【０００３】
ネットワーク内の各ノード／ルータの動作条件がわかれば、データまたはデータパッケージがネットワークを通じて通信されるデータパス及びデータパスを形成するデータリンクを決定することが可能である。各ノード／ルータの動作条件、特に各ノード／ルータのルーティング決定は、リンクのコストを決定するコスト関数を介して決定される。コスト関数はプロトコルにより異なり、リンクの容量、通信されるデータの種類及び／または量、データの送り先となるノードへのデータリンクの利用率、（物理的な）遅延及びネットワーク全体のデータ通信状況に依存しうる。実際には、コスト関数は、リンクデータベース中で前もって定められるリンクの容量及びリンクの遅延値といった静的及び／または予め定められた変数だけに依存する。従って、ネットワーク中で誤りが発生しない場合、ネットワークのノード／ルータの動作条件はデータ通信の間変化しないので、データが送信ノードから受信ノードに通信されるデータパスを決定することが可能になる。
【０００４】
上記で言及された内部ルーティングプロトコルのさらなる基本的な原理は、送信ノードと受信ノードとの間の最短データリンクを常に選択するということである。ルーティングプロトコルがデータパスの長さを決定する基準となるメトリックを定め最短データパスの決定に関する情報がネットワーク上で分配される。例えば、オープンショーテストパスファースト（ＯＳＰＦ）プロトコルは一般に、データリンク（例えば、ＣＩＳＣＯルータ）のデータ通信容量または／及びデータリンク上のデータ通信に関する遅延といった時間に独立なパラメータに基づく加算的メトリックを使用する。ＯＳＰＦメトリックでは、あるノード／ルータからそれに接続される他のノード／ルータへの各データリンクについてのコストが入力される。あるノード／ルータから次のノード／ルータへの間のデータリンクのデータ通信パラメータはデータリンク上のデータ通信の方向に依存しうる。すなわち、データリンクのコストはデータ通信方向に関連して変化することがある。データパスの総コストは、データパスに含まれるデータリンクの全てのコストの加算によって得られる。
【０００５】
拡張インターネットゲートウェイルーティングプロトコル（ＥＩＧＲＰ）のメトリックはＯＳＰＦプロトコルのメトリックより複雑であるが、ほとんどの場合加算的メトリックに簡約化された形態で使用される。
【０００６】
常に最短データパスを選択するこのアプローチは、単一パスルーティング、すなわち２つのノード／ルータ間のルーティングが全てのデータフローについて同一であることを含意している。多重パスルーティングを定めることは可能であるが、安定性（例えば、ループ保護）とプロトコルに依存する理由のため使用されることはほとんどない。固定コストメトリックと単一パスルーティングの結果、データパスまたはデータパスに含まれる単一データ／リンクの輻輳が発生することがある。これは例えばデータの量が単一データ／リンクのデータ通信容量より大きい場合発生する。同様の問題は、ノード／ルータのデータ通信容量が望ましい量のデータを通信するのに十分でない場合、例えば、ノード／ルータが異なった送信ノード及び／または異なった受信ノードのデータパスに含まれる場合発生しうる。
【０００７】
その上、特定のデータパス及び／またはデータリンクが非常に頻繁に利用され、他のものは時々しか使用されないということもある。データリンク上のデータ通信のこの不均等な分配の結果、ネットワークデータリンクの不均等なリンク利用が生じる。この不均等なリンク利用は別のデータリンクの輻輳につながることもある。高度に利用されたリンクの場合でさえ、負荷と待ち時間との間の非線形依存性のためネットワークはＩＰ電話のような実時間適用業務に利用できない。その上、高価なハードウェア及びソフトウェア手段を必要とするネットワーク内で提供されるデータリンクが使用されないため、ネットワーク中のデータのこうしたルーティングはネットワークの不経済な運用につながる。
【０００８】
ネットワーク中のデータのルーティングを最適化する従来のアプローチは既存のルーティングプロトコルを改善／拡張するか、または新しいルーティングプロトコルを開発するものであった。変更されたかまたは新しいルーティングプロトコルは普通ネットワーク全体を通じて確立されなければならないので、変更されたかまたは新しいハードウェア及びソフトウェアが必要である。従って、この最適化は主として組織上の問題によって制限される。
【０００９】
発明の目的
本発明の目的は、現時点の技術水準の上記で説明された問題を解決することである。すなわち、本発明は、既存のルーティングプロトコルを使用して、すなわちネットワーク中ですでに使用されているルーティングプロトコルとネットワークのそれぞれのハードウェア及びソフトウェア構成要素とを修正または再配置せずにネットワーク中のデータのルーティングを最適化する方向に向けられている。その上、本発明は、ネットワークを通じてそれぞれ通信／ルーティングされるデータまたはデータトラフィックの均質な分配を達成するため、ネットワーク中でデータをルーティングする方法とシステムを提供する。本方法はまた、ＭＰＬＳ及び今後の（例えば光／デジタルラッパを伴う）光ネットワークでのルーティングで発生するトラフィックにも適用される。
【００１０】
発明の簡単な記述
上記の問題を解決するため、請求項１に記載のネットワーク中でデータを通信する最適なデータパスを決定する方法を提供する。
【００１１】
本発明による方法は線形最適化問題に基づいてネットワーク中のデータのルーティングを最適化するアプローチに基づいている。本発明による線形最適化問題は、データトラフィックとも呼ばれるネットワーク中でルーティング／通信されるデータがネットワーク上で均一／均質に分配されるように定義されなければならない。本発明の観点では、データトラフィックの「均一／均質な分配」という表現は、データトラフィックの「均等な分配」として理解されるべきではない。ネットワークを通じたデータトラフィックの均等な分配とはネットワークのノードを接続する各データリンクについての同一／均等なデータトラフィックに帰結するものであろう。
【００１２】
データトラフィックの「均等な分配」が本発明による線形最適化問題の最適解であることもあるが、本発明による方法は特にデータトラフィックの「均等な分配」を得ることに適用されるのではなく、ネットワーク中のデータリンクのリンク利用率が異なっていることもあるネットワーク中でのデータのルーティングの最適化に向けられる。
【００１３】
本発明による方法は、データリンクによって接続される複数のノードを有するネットワーク中で送信ノードから受信ノードに最適なデータパスを介してデータを通信するために使用される。以下、「データパス」という用語は、送信ノードと受信ノードとの間のデータパスについて使用され、その際データパスは対応するデータリンクによって形成される。
【００１４】
送信ノードから受信ノードへの最適なデータパスを決定するため、それぞれのデータリンク及びノードを通じた送信ノードから受信ノードへの全てのループなしデータパスが決定され、２つのノード間の全てのデータ通信が同じデータパスを介して通信されるようにデータパスが選択される。続いて、選択されたデータパスのリンクコストが決定され、最小リンクコストを有するデータパスが最適データパスとして定められる。次に、データが送信ノードから受信ノードに最適データパスを介して通信される。
【００１５】
さらに、データパスの選択は、データパスのデータ通信容量を決定し送信ノードから受信ノードにデータを通信するのに十分な通信容量を有するデータパスを選択すること、及び／または、データパスの物理的遅延を決定し所定の上限物理的遅延に等しいかまたはそれより小さい物理的遅延を有するデータパスを選択することを含んでもよい。
【００１６】
送信ノードから受信ノードへの最適データパスの決定は線形最適化問題に関する方程式系の定義と、最適データパスを定義する方程式系の解とに基づくものでもよい。
【００１７】
方程式系に対し、リンクコストを示す項を含む目的関数が定義される。
また、上限リンク利用率、または平均リンク利用率、または上限リンク利用率及び／又は平均リンク利用率及び／又はリンクコストの組み合わせを示す値を表わす項を含む目的関数を定義することも可能である。
【００１８】
目的関数の他に、線形最適化問題は制約の定義を必要とする。本発明によれば、選択されたデータパスのリンクコストに対するコスト制約が定義される。
さらに、フローの維持及び／又はループなしデータパスの決定のための目的関数の平均リンク利用率部分と共にトランスポート制約が定められる。
【００１９】
さらに、送信ノードから受信ノードに通信されるべき全てのデータが同じデータパスを介して通信されるように、ルーティング制約が定義される。このルーティング制約の定義によって、ノード／ルータ間の最短データパスを選択し単一パスルーティングを利用する既存のプロトコルが利用できるようになる。
【００２０】
さらに、十分なデータ通信容量、通信されるべきデータの量に等しいかまたはそれより大きい好適な上限データ通信容量、及び／または所定の上限リンク利用率に等しいかまたはそれより小さいデータ通信容量を有するデータパスを決定するため容量制約が定義される。
【００２１】
さらに物理的遅延制約を定義することによって、所定の上限物理的遅延に等しいかまたはそれよりも小さい物理的遅延を有するデータパスが決定できる。本発明の観点では、物理的遅延とは、それぞれのデータリンクによって接続されるネットワークのノード間でデータを通信するために必要な時間である。最適データパスを得るため、線形最適化問題についての方程式系が制約に関する目的関数の最小化によって解かれる。
この方程式系を解くと、送信ノードから受信ノードへの全ての可能なデータパスが決定され、最小リンクコストを有するデータパスが最適データパスとして定められる。特に、多くのノードと接続データリンクとを含む複雑なネットワークの場合、反復的に目的関数の最小化を行うことが有利なことがある。
【００２２】
平均リンク利用率と上限リンク利用率との組み合わせを示す値に関連して、互いに重み付けされた平均リンク利用率と上限リンク利用率とを表す関数を使用してもよい。
【００２３】
さらに詳しく言うと、最適データパスの決定についてより大きな影響／重要度を有する目的関数の成分は、目的関数の他の成分についての重み付け値と比較してより大きな値によって重み付けされる。
【００２４】
最適データパスの決定において考慮すべき選択されたデータパスの数を最小化するため、予め定められたリンクコスト範囲を超えるリンクコストを有するデータパスを除外することも可能である。例えば、リンクコスト範囲は１と予め定められた上限閾値、例えば送信ノードおよび受信ノードを含むネットワークのルータの数の４倍以上の値の間に定め得る。
非常に時間がかかることもある、方程式を解く際の複雑さに関連して、所定の時間内に決定された方程式系の最新の解を使用することが可能である。例えば、このアプローチは、所定の時間内で、目的関数が実行可能でない場合、目的関数について最小値が決定できない場合、または目的関数が収束しない場合好適である。
【００２５】
本発明による方法が使用される対象となるネットワークに応じて、方程式系を定義するための変数の数は非常に多いことがある。すなわち、Ｎがノード／ルータの数を表しＭがデータリンクの数を表す時、目的関数についての変数の数はＮ2Ｍ2という大きさになる。ルーティング制約によって決定される、本発明による制約についての変数の数はＮ3Ｍ2という大きさになる。好適には、大規模ネットワークの場合、変数の数を低減するため、かつ／または方程式系を解くために考慮すべきデータリンクの数を低減するため、本方法は、全てのループなしデータパスについて送信ノードから受信ノードへのデータ通信のための時間を決定することを含む。さらに、データパスは、方程式系を解くために考慮すべきデータパスのうち、最小データ通信時間及び／または所定の上限データ通信時間が決定されたところのものとして識別される。好適には、上限データ通信時間は最小決定済データ通信時間に関連して予め定められる。
【００２６】
方程式系について考慮されるデータパスの識別に関連して、可能なデータパスに含まれるデータリンクだけが使用される。さらに、方程式系を解くため全ての可能なデータパスに含まれるデータリンクを考慮しないことも可能である。
【００２７】
ネットワークによっては、ノード間のデータ通信についての上限時間を表す所定のデータ通信時間制限が利用されることがある。こうした所定の通信時間制限を考慮するため、所定の通信時間制限に基づいて物理的遅延制約を定義することが可能である。ここでは、物理的遅延制約は、ノード間のデータの通信のために必要な実際の時間によって決定されるのではなく、それぞれのデータリンクについての所定の通信時間制限によって決定される。
【００２８】
同様に、データリンクの帯域幅の結果として得られるネットワークの特性は、データリンクの帯域幅に基づいて物理的遅延制約を定義することによって考慮される。ある特定のデータリンク上でのデータの通信のための実際の時間を使用する代わりに、データリンクの帯域幅が対応する物理的遅延に変換される。
【００２９】
上記の方程式系の代わりとして、線形最適化問題を基礎としてリンクコストを決定することも可能である。ここで、線形最適化問題に対する不等式系を計算することによりリンクコストを得ることが好ましい。他のデータパスのリンクコストの合計と比べてより大きいリンクコストの合計を有する選択されたデータパスの中の１つのデータパスを最適データパスとして選択することが可能である。
最適データパス以外の選択されたデータパスのすべてに対するコスト制約を、最適データパスのリンクコストが最適データパス以外の選択されたデータパスのすべてに対するリンクコストよりも小さくなるように定めることが好ましい。
不等式システムの複雑さを軽減するため、最適データパス以外の選択されたデータパスであって最適データパスの送信ノードに隣接するノードから始まり最適データパスの受信ノードで終わり最適データパスのノードをそれ以上含まないものに対してコスト制約を定め、最適データパス以外の選択されたデータパスの残りのものについてはコスト制約を定めないようにすることも可能である。
【００３０】
送信ノードと受信ノードとの間で通信されるべきデータの量は時間と共に変化しうるという事実により、かついくつかの送信及び／または受信ノードがネットワーク上で通信するという事実によれば、本発明による最適データパスの決定を、所定の時間、または所定の時間間隔中、連続して行うことが好適である。ここで、所定の時間、または所定の時間間隔中、通信されるべきデータの量を連続して決定することが可能であり、その際最適データパスの決定及び通信すべきデータの量の決定のため、異なった所定の時間及び／または異なった所定の時間間隔を使用してもよい。
【００３１】
代替案として、所定の（例えば上限）量の通信されるべきデータについて最適データパスを決定することが可能である。好適には、所定の量の通信されるべきデータは感知または近似される。
【００３２】
特に非常に大規模／複雑なネットワークの場合、ネットワークが少なくとも２つの部分または部分ネットワークに分割され、その各々について最適データパスの決定が個別に行われる可能性が大いにある。最短パス原理によれば、小規模なネットワークの連結解は１つの大規模ネットワークの最適化によって得られる値に等しい。
【００３３】
その上、ネットワークの少なくとも一部を仮想ノードにグループ化することも可能である。ここで、仮想ノードを含むネットワークの残りの部分の最適データパスの決定と、仮想ノードであるネットワークのグループ化された部分の最適データパスの決定とは個別に行われる。
【００３４】
また、本発明は、請求項２６の発明により、最適データパスを介してネットワーク中でデータを通信するシステムを提供する。このシステムは少なくとも１つのノードが送信ノードであり少なくとも１つのノードが受信ノードであるデータリンクによって接続されるノード／ルータを有するネットワークと、ネットワーク中のデータ通信を制御するネットワークに接続される制御手段とを備えている。すなわち、制御手段は、最適データパスを介してデータを通信する本発明による方法の１つを実行するよう適用される。
【００３５】
制御手段は、少なくとも１つのノード／ルータ、好適には全てのノード／ルータのデータ通信を制御する中央制御システムまたは中央制御システム（例えば、インターネットサーバ）の構成要素でよい。
【００３６】
さらに、制御手段は、データ通信を制御するため、１つまたはいくつかのノード／ルータに関連する少なくとも１つの制御ユニットを備えてもよい。最適な方法でデータ通信を制御し、かつ／またはさらに別のノード／ルータのデータ通信を制御するため、こうした制御ユニットは、ネットワーク内のデータ通信の情報を得るため、さらに別のノード／ルータ、好適には全てのノード／ルータと通信すべきである。
【００３７】
特に大規模ネットワーク及び／または大量のデータ通信を示すネットワークの場合、中央制御システムと少なくとも１つの制御ユニットの組み合わせによって最適データパスの識別を改善できるが、これは、単一ノードについてのデータ通信制御機能と、ネットワーク全体に関連するデータ通信制御機能が制御手段の異なった構成要素にしかるべく分配されるからである。
【００３８】
発明の詳細な実施形態の記述
一般に、ネットワークのノードは、それぞれのノードに接続されたデータリンクを介してデータを受信及び送信できるコンピュータベースのシステム／ユニット（サーバ）である。ノードはネットワークに送信されるデータの発信元である送信ノードとして動作し得る。さらに、ノードは、対応する送信ノードから通信されるデータを受信する宛先の役目を果たす受信ノードとして動作し得る。その上、ノードは、送信ノードまたは別のノード／ルータからデータを受信し受信されたデータをさらに別のノード／ルータまたは受信ノードに送信するいわゆるルータとして動作し得る。
【００３９】
ネットワークのノード間のデータリンクはインタフェースと呼ばれることが多いが、これは、データリンクは送信されるべきデータを表す電気／光信号の物理的送信のための回線だけでなく、データネットワーク中でデータを送信するために必要なハードウェア及びソフトウェア構成要素をも含んでいるからである。こうしたハードウェア及びソフトウェア構成要素には、従来の電気回線、データバス、バッファ／メモリユニット、プロセッサベースユニット、データ変換及びデータ通信プロトコル（すなわち、ルーティングプロトコル）の実現のためのソフトウェアプログラム、等が含まれる。
【００４０】
本発明の目的を達成するため、すなわち、全てのリンク利用率（平均リンク利用率）を最小化し、上限リンク利用率を最小化し、ネットワークのノード間のデータリンクの物理的遅延をある範囲内に維持するためには、ネットワークとそのデータトラフィック、すなわち、ネットワーク中で通信されるデータの量と流れを定式化する必要がある。この定式化のため、３つの行列が使用される。
【００４１】
第１に、ＮノードのネットワークはサイズＮ×Ｎを有する容量行列Ｃによって定義され、その際容量行列Ｃの各エントリはノードｉ及びｊの各対についてリンク容量Ｃijを表す。２つのノードの間にデータリンクが存在しない場合、容量行列Ｃの対応するエントリは０に設定される。
【００４２】
第２の行列はトラフィック行列Ｆであり、ノードｉ及びｊの各対についてエントリｆijを備える。各エントリｆijは２つのノードｉ及びｊの間のデータトラフィック／データフローを表す。２つのノード間でデータが交換されない場合、トラフィック行列Ｆ中の対応するエントリは０に設定される。本発明による方法の実現に応じて、トラフィック行列のエントリｆijは静的データフローを表すこともあり、また、例えば本発明による方法がネットワークの運用中連続して実行される場合、エントリｆijはネットワークのノード間の実際のデータフローを表すこともある。
【００４３】
第３に、データリンクの物理的遅延を記述する行列Ｄが導入される。データリンクの物理的遅延は、対応するデータリンク上の２つのノード間でデータを通信するために必要な時間を特定する。行列Ｄのエントリｄijは２つのノードｉ及びｊを接続するデータリンクの物理的または近似的遅延を表す。
【００４４】
これらの行列に基づいて、本発明によるルーティング最適化が線形最適化問題として定義できる。周知のように、線形最適化問題は、目的関数と制約という２つの部分からなる方程式系によって記述される。制約は、目的関数の最適解が決定されなければならない多次元解空間を定める。目的関数の最適解は、本発明の場合、目的関数の最小値を生じる解空間内の解である。ネットワーク中のデータルーティングの最適化を達成するため、目的関数の可能な解を制限する異なった制約を満たさなければならない。
【００４５】
第１に、送信ノードから受信ノードに通信されるデータの場合、データが伝送／ルーティングされるデータパスを決定しなければならない。送信ノードと受信ノードとがデータリンクによって直接接続されていない場合、可能なデータパスには送信及び受信ノードだけでなく、さらに別のノードとそれを接続するデータリンクとが含まれる。送信ノードから受信ノードに伝送される異なったデータが異なったデータパスまたはデータリンク上でそれぞれルーティング伝送されるのを避けるため、可能なルーティングデータパスはいわゆる単一パスルーティングに制限されていた。単一パスルーティング制約によれば、目的関数の可能な解について２つのノード／ルータ間で正確に１つのデータパスが定められる。こうした単一パスルーティングの結果が図１に例示されている。使用されるルーティングプロトコルメトリックが何であっても、ノード／ルータＣ及びＦの間の最短データパスはノード／ルータＤ上またはノード／ルータＥ上の何れかである。単一パスルーティングの結果、２つのデータフローＡ−Ｆ及びＢ−Ｆはまずノード／ルータＣ上、次にノード／ルータＤまたはノード／ルータＥ上の何れかでルーティングされるが一方がノード／ルータＤ上を通り、もう一方がノード／ルータＥ上でルーティングされるということはない。
【００４６】
第２に、容量制約が満たされなければならず、それによれば特定のデータリンク上で通信されるデータの量は対応するデータリンクの容量、すなわち対応するデータリンク上で通信できるデータの上限量を越えない。ネットワーク中のデータリンクの容量はデータリンクの様々な伝送構成要素（すなわち、電気ワイヤ、バス、プロセッサ）の物理的伝送容量に制限されないが、それは、伝送されるべきデータまたはそのデータパッケージは、伝送前に例えばデータリンク及び／またはノード／ルータの中間メモリに格納できるからである。線形最適化問題の観点から容量制約を定義するために２つのアプローチが使用できる。１つのアプローチはパス指向型であり、もう１つはデータリンクに関連するフロー指向型である。ここで、フロー指向型を選択して詳細を示すが、パス指向型アプローチと比較して含んでいる変数の数が少ないためである。フロー指向型アプローチの説明の後、パス指向型アプローチの場合の方法の表記の変更が説明される。
【００４７】
既存のルーティングプロトコルと組み合わせて本発明によるルーティング最適化の方法を適用するため、使用されているルーティングプロトコルによって指定されるルーティングアルゴリズムを考慮しなければならない。上記で言及されたように、現在使用されているルーティングプロトコル、すなわちＯＳＰＦプロトコルとＥＩＧＲＰは、送信ノードから受信ノードにルーティングされるべきデータの最短データパスを決定するルーティングアルゴリズムに基づいている。最短データパスを求めるこうしたアルゴリズムは、２つのノード／ルータ間で通信される全てのデータが同じデータリンク上でルーティングされることを含意している。
【００４８】
目的関数
目的は、ネットワーク全体を通じてできる限り均質／均一な伝送データの分配またはデータトラフィック分配を達成することである。別言すれば、ネットワークの全てのデータリンクはできる限り低いデータ通信レベルでできる限り均等に利用されるべきである。データトラフィック行列Ｆ中でデータトラフィックエントリＪij≧０を有するノード／ルータｉ及びｊの間の各データフローと、容量行列Ｃ中で容量エントリＣij＞０を有する各データリンクとについて、フロー指向型アプローチを利用するため、ブール変数ｘuvijを導入する。この変数は、送信ノードｕから受信ノードｖへのデータフローｕｖがノードｉ及びｊの間のデータリンクｉｊ上でルーティングされる場合１に設定され、そうでない場合この変数は０に設定される。さらに、全てのデータリンクのリンク利用率について上しきい値を定義する変数ｔが導入される。
【００４９】
上限リンク利用率と平均リンク利用率の両方を最小化しなければならない。従って、目的関数には２つの加法要素が含まれ、その両方を最小化しなければならない。
【００５０】
【数１】
0004768192.tif 000002
【００５１】
目的関数（１）の左側の加法要素は上限リンク利用率を表し、目的関数（１）の右側の加法要素は平均リンク利用率を表す。目的関数（１）の上限リンク利用率部分のパラメータａtは目的関数（１）の平均リンク利用率部分に対して上限リンク利用率部分に重み付けする重み係数として使用される。パラメータａtは、最適データを選択するための小さい／最小化された上限リンク利用率の影響／重要度対小さい／最小化された平均リンク利用率の影響／重要度という観点から選択される。例えば、上限リンク利用率の最小化が平均リンク利用率の最小化と比較して高い優先度を有する場合、パラメータａtは大きな値を有するべきであり、その結果データトラフィックを利用率の少ないデータリンクに誘導することによって上限リンク利用率が低下する。それと比較して、最適データパスの選択に対する平均リンク利用率の最小化の影響が上限リンク利用率の最小化の影響より大きい場合、パラメータａtは小さな値を有するように選択されるべきである。
【００５２】
トランスポート制約
トランスポート制約は、各データフローについて、例えば送信ノードｕから受信ノードｖへのデータフローについて、目的関数（１）の解から得られる変数ｘuvijの値が送信ノードｕから受信ノードｖへの１つのループなしデータパスを確実に指定することを保証する。ここで、トランスポート制約は各データフローに対する次の４つの副制約を備えている。
【００５３】
１．ノード／ルータｉ上で伝送される送信ノードｕから受信ノードｖへのデータフローはノード／ルータｉから出る１つのデータリンク上でだけルーティングされる。すなわち、
【００５４】
【数２】
0004768192.tif 000003
【００５５】
２．送信ノードｕから受信ノードｖへのデータフローｕｖは送信ノードｕから別のノード／ルータｉへの正確に１つのリンクｕｉを介してルーティングされる。すなわち、
【００５６】
【数３】
0004768192.tif 000004
【００５７】
３．送信ノードｕから受信ノードｖへの全てのデータフローについて、および送信及び受信ノードｕ及びｖ以外の各ルータｉについて、データフローｕｖによって使用されるルータｉに至るデータリンクの数とルータｉから出るデータリンクの数とは等しい。すなわち、
【００５８】
【数４】
0004768192.tif 000005
【００５９】
４．送信ノードｕから受信ノードへのデータフローｕｖは受信ノードｖに至る正確に１つのデータリンク上でルーティングされる。すなわち、
【００６０】
【数５】
0004768192.tif 000006
【００６１】
送信ノードｕから受信ノードｖへの正確に１つのループなしデータパスを定義するトランスポート制約の結果は図２に例示されている。式（３）によれば、ノードｕとノードａを接続するデータリンクｕａだけがデータフローｕｖを伝える。１つのデータリンクが各ノード／ルータａ、ｂ及びｃに至るものとする。式（４）によれば、データフローｕｖについて１つのデータリンクが各ノード／ルータａ、ｂ及びｃから出る。式（５）の条件では、データフローｕｖについてのデータパスはノード／ルータｃと受信ノードｖとの間のデータリンクｃｖに向けられ、受信ノードｖで終了する。
【００６２】
それにもかかわらず、データフローｕｖについて選択されたデータパス以外にループ付きデータパスが存在することはありうるが、それは、こうしたループはトランスポート制約によっては回避できないからである（図１２参照）。しかし、こうしたループは目的関数（１）中の平均リンク利用率の最小化によって回避される。
【００６３】
容量制約
容量制約によって、データリンク上のデータの量またはデータトラフィックは対応するデータリンクの容量を越えないようになる。容量制約はノードｉ及びｊ間の各データリンクｉｊについて２つの副制約を備えている。
【００６４】
第１の副制約は、リンク利用率がパラメータａcによって定義される一定のレベル以下になるようにする。すなわち、
【００６５】
【数６】
0004768192.tif 000007
【００６６】
前述したように、データネットワーク内のデータリンクは、短期間であれば対応するデータリンクの物理的伝送容量より大きなデータトラフィックを処理できる。従って、パラメータａcは０と１との間の値に制限されない。１より大きいパラメータを設定することは、輻輳の場合最初のボトルネックになるリンクを識別するためにも有用である。本発明による方法の場合、パラメータａcはデフォルト値として１に設定される。
【００６７】
式（７）によって与えられる第２の副制約はリンク利用率について上しきい値を定める。目的関数（１）で使用される変数ｔは全てのリンクの利用率について上限を定める。パラメータａcが固定値であるのに対して、変数ｔは最小化される。第２の副制約は全てのリンク利用率がパラメータｔの値より低い値を有するようにする。すなわち、
【００６８】
【数７】
0004768192.tif 000008
【００６９】
ルーティング制約
ルーティング制約は最も重要な制約であるが、それは、ルーティング制約が、線形最適化問題について方程式系を解くことによって得られるデータ通信／ルーティングのコストをそれぞれ計算するのに十分なデータリンクまたはデータパスの組み合わせだけを定めるからである。上記で言及されたルーティングプロトコルを使用すると、データは常に、各データリンクについてのあるルーティングプロトコルメトリックによって定められる最短データパス上で通信／ルーティングされる。その結果、ノード／ルータｉからノード／ルータｊへの全てのデータフローは、ノード／ルータｉ及びｊ間の同一のデータリンク上で通信／ルーティングされなければならない。
【００７０】
こうした制約は次のような副制約の再帰的システムによって達成される。
【００７１】
【数８】
0004768192.tif 000009
【００７２】
【数９】
0004768192.tif 000010
【００７３】
式（８）及び（９）の反復的または再帰的適用を考えると、ノード／ルータｉ及びｊの間のルーティングはこれらのノード／ルータを通る全てのデータフローについて同一である。従って、ルーティング制約に基づいて発見される解はルーティングプロトコルの実現に対応する。
【００７４】
図３は、ルーティング制約の結果を例示する。データフローｕｂがノードｕ、ａ及びｂ上でルーティングされるとすると、データフローａｃはノードａ、ｂ及びｃ上でルーティングされ、データフローｃｖはノードｃ、ｄ及びｖ上でルーティングされ、式（８）及び（９）によれば、送信ノードｕから受信ノードｖへのデータフローｕｖはノードｕ、ａ、ｂ、ｃ、ｄ及びｖ上でルーティングされなければならない。
【００７５】
データフローｕｃについて、ノードａ’またはノードｂ’の何れかを通る２つのさらに別のデータパスが存在する。ノードａ’を含むデータパスは、ノードａを含んでおらず、これは式（９）と矛盾するので、データフローｕｃのために使用することはできない。さらに、ノードｂ’を含むデータパスはノードｂを含んでおらず、これは式（８）と矛盾するので、データフローｕｃのために使用することはできない。別言すれば、ノードａ’を含むデータパスと、ノードｂ’を含むデータパスとは、全てのデータフローｕｃ、ａｃ及びｂｖを同じデータリンク上でルーティングするルーティング制約を満たしていないので、データフローｕｃのために使用することはできない。
【００７６】
物理的遅延制約
トランスポート制約、容量制約及びルーティング制約と組み合わされた目的関数（１）に基づいて、データトラフィックが均質、均等に分配された最短パスルーティングを有するデータルーティングが達成される。ネットワーク中のデータ通信の物理的遅延をある範囲内に維持するという目標を得るため、以下説明される物理的遅延制約を適用しなければならない。
【００７７】
可能な物理的遅延の範囲はパラメータａrによって定義され、データフローの最低物理的遅延は変数ｄminuvによって表される。Ｐがノードｕからノードｖへの全てのループなしデータパスの集合であり、ｄpがパスｐのデータリンクの全ての物理的遅延の合計である場合、最小物理的遅延ｄminuvは物理的遅延ｄｐが最小であるノードｕからノードｖへのパスｐの遅延である。すなわち、
【００７８】
【数１０】
0004768192.tif 000011
【００７９】
最小物理的遅延の値は、ノードｕからノードｖへの全ての可能なループなしデータパスの全ての物理的遅延を計算することによって得られる。パラメータａrを導入すると、各データフローについて上限物理的遅延を表す上しきい値ａrｄminuvが下記のように定義できる。
【００８０】
【数１１】
0004768192.tif 000012
【００８１】
線形最適化問題についての方程式系の複雑さの低減
目的関数（１）を解くため、考慮されるべき変数の数は、Ｎがノード／ルータの数を表しＭがデータリンクの数を表す時、Ｎ2Ｍ2という大きさになる。ルーティング制約によって決定される、制約の数はＮ3Ｍ2の大きさになる。特に多くのノード／ルータとデータリンクを含む大規模ネットワークの場合、本発明による線形最適化問題の方程式系を解くのは非常に時間がかかり、複雑で、不可能なことさえある。従って、方程式系を解くために重要なデータパスだけを考慮することで変数と制約の数を低減するいわゆるプリソルバーが使用される。
【００８２】
重要なデータパスはそれぞれの物理的遅延に基づいて識別される。２つのノード／ルータ間の各データフローについて、ループなしパスである全てのデータパスが決定される。こうしたループなしデータパス各々についての物理的遅延、すなわちそれぞれのデータパスを形成するデータリンクの物理的遅延の合計が計算される。最小物理的遅延を有し、かつ上物理的遅延しきい値ａrｄminuvより低い遅延を有するデータパスが重要なデータパスとして識別される。さらに、重要なデータパスの全てのデータリンクが全ての重要なデータパスに含まれるかまたは重要なデータパスのどれにも含まれないかが検査される。全ての重要なデータパスに含まれるデータリンクがそのデータリンク上でそれぞれのデータフローをルーティングするために使用される。重要なデータパスのどれにも含まれないデータリンクは、線形最適化問題の方程式系を解く際考慮されないので、対応するデータリンクはそのデータリンクを介してルーティングされることはない。重要なデータパスの一部にだけ含まれるデータリンクは方程式系を解くために考慮され、そのデータリンクの利用率は方程式系を解くことで決定される。
【００８３】
次善のルーティング
場合によっては、例えば非常に複雑なネットワークの場合など、方程式系全体を使用してルーティングを計算するのではなく、以下説明されるアプローチを利用して結果として次善の（次善：実際的な時間内に最適に近い解を得ること）ルーティングを得るのが有利なこともある。上記で説明された手順と対照的に、上限リンク利用率を直接最小化するのではない。ここでは、上限リンク利用率の最小化は、異なった、簡約化された目的関数と、異なった、簡約化された容量制約とを有する線形最適化問題の反復解によって達成される。
【００８４】
上限リンク利用率を最小化する目的関数（１）の成分ａt*ｔは省略される。その結果、様々なデータリンクの利用率をリンク利用率の上しきい値以下にする式（７）によって表される容量制約についての副制約はもはや必要ない。他方、式（６）によって表される容量制約についてのもう一方の副制約はより厳密に定義される。パラメータａcについてデフォルト値１を使用する代わりに、パラメータａcは反復的に最小化される。
【００８５】
パラメータａcの値が１であるところから始めて、簡約化された目的関数を含む方程式系が解かれる。単一データリンクのリンク利用率は簡約化された方程式系の発見された解に基づいて決定される。次のステップでは、パラメータａcは最小決定済リンク利用率よりわずかに小さい値に設定される。この手順は、簡約化された方程式系の解が収束するまで繰り返される。方程式系が所定の時間間隔内に収束しないか方程式系の解が存在しない場合、方程式系の最後の解によって決定されるルーティングが線形最適化問題の次善の解と考えられる。
【００８６】
パス指向型アプローチ
前に言及したように、問題をパス指向型アプローチとして定式化することが可能である。この方法はフロー指向型アプローチに等しいが、以下の変更を伴っている。
【００８７】
変数
ブール変数ｐkuvが導入される。この変数は、送信ノードｕから受信ノードｖへのデータフローｕｖがデータパスｋ上でルーティングされる場合１に設定され、そうでない場合変数は０に設定される。ｋは、ｕ、ｂ、…、ｖがパスを構築する符号である場合、ｕ、ｂ、…、ｖに等しい指標である。
【００８８】
目的関数
フロー指向型アプローチと同様、パス指向型アプローチの目的関数には２つの加法要素が含まれ、その両方を最小化すべきである。
【００８９】
【数１２】
0004768192.tif 000013
【００９０】
トランスポート制約
トランスポート制約によって、送信ノードｕから受信ノードｖへの１つのループなしデータパスが確実に存在するようになる。
【００９１】
【数１３】
0004768192.tif 000014
【００９２】
容量制約
各リンク上のフローの合計はリンクの容量より小さくなければならず、
【００９３】
【数１４】
0004768192.tif 000015
【００９４】
ルーティング制約
ｐuvがｕからｖへのパスを定め、ｐkvがｋからｖへのパスを定め、両方のパスがｉ上でルーティングされる時、両方のパスはパスｉからｖについて同一であるので、次式が成り立つ。
【００９５】
ｐuv−ｐiv＜１
このルーティング制約は指標パラメータｋの再帰的反復として書くことができる。例えば、ｕからｖへのパスはａ、ｂ及びｃ上でルーティングされる。すなわち、ｋはｋ＝ｕ、ａ、ｂ、ｃ、ｖとして定義されるのでａからｖへのフローはパスａ、ｂ、ｃ、ｖを使用しなければならず、またｂからｖへのフローはパスｂ、ｃ、ｖを使用しなければならない、等である。この再帰的反復は指標パラメータｋの反対方向でも真であり、例えばｋ＝ｕ、ａ、ｂ、ｃ、ｖであればｕからｃへのフローはパスｕ、ａ、ｂ、ｃを使用しなければならない、等々。
【００９６】
リンクコストの特定
方程式系または簡略化された方程式系により決定されたルーティングに対するデータリンクコストを特定するため、データリンクコストは見い出されたルーティングと最適化データパスがいずれもショーテストパスルーティングと対応するように決定されなければならない。例示として、この事は次のようにして達成される：
１．付加的制約
第１の線形プログラムの解の一部としてリンクコストを得るため、次の付加的な制約が線形ブログラムに追加される。
【数１５】
0004768192.tif 000016
付加的変数Ｉijはリンクｉとｊの間のインターフェースまたはリンクコスト値を特定し、Ｌkuvはｕからｖへのｋ番目のパスのコスト全体を定める。
Ｌkuv−Ｌsuv＞（ｐsuv−１）*ｉmax
この不等式は、パスｓが最短パスとして選ばれたならばパスｓはｕからｖへの最小全体コスト値を有することを保証する。パスｓが最短パスとして選ばれたならば、ｐsuv＝１であり、不等式Ｌkuv−Ｌsuv＞０は満たされる。言い換えれば、差分Ｌkuv−Ｌsuvは−ｉmaxよりも大である。
１＜Ｉij＜ｉmax
リンクまたはインターフェースのコスト値は１と値ｉmaxの値でなければならない。ｉmaxはリンクまたはインターフェースの最大コスト値を定める。例えばｉmaxはルーティングプロトコルにおいてリンクまたはインターフェースコスト値に対して特定される最大値に設定される（例えばＯＳＰＦについてはｉmaxは６５５３５）。計算時間を節約するため、例えば次の経験則：
ｎ個のルータを有するネットワークに対してｉmax＝４ｎ
に基いてより小さい値を選ぶことも可能である。
【数１６】
0004768192.tif 000017
２．線形最適化問題に対する方程式
線形最適化問題に対する方程式によりリンクコストを特定することも可能である。この場合、データリンクコストの所望の解は線形システムを計算することにより得られるから、目的関数はむしろ重要でない。線形最適化問題は、目的関数と組み合わせられた不等式系で表わされる。従って、インターフェースコストの決定は線形最適化問題の方程式系を用いて計算することができる。結果として、線形最適化問題の標準的なソルバをデータリンクコストの決定に使用することができる。
変数ｍijはインターフェースｉｊのコストを表わす。ｕからｖへの最短パスは最小コストを有するパスである。パスのコストは単一のインターフェースのコスト値の総計である、ｕからｖへのフローについてコストｍuvは次の様に与えられる。
【数１７】
0004768192.tif 000018
ここでｘijuvは以前のルーティング最適化のパスを表わす。ｍuvはｕからｖへのすべての可能なパスの最小コストでなければならない。従って、最適パスｐoptuv以外の各ループなしパスｐについて、コストｐoptuvをより小さいものにする制約が特定されなければならない。
【数１８】
0004768192.tif 000019
すべてのパスに対するすべてのこのような制約を含めると大規模なネットワークに対しては非常に複雑な問題となる。しかしながら、これらのすべての制約が適切な解を得るために要求される。ｕからｖへのフローについて次のアルゴリズムにより必須の制約が特定される：
ｕの各隣接ルータｉを考慮して：
ｐoptuvとｐoptivがｕ以外の共通ノードを持たなければ次の制約を追加し
【数１９】
0004768192.tif 000020
そうでなければ制約を追加しない。
このアルゴリズムを図１３の例を用いて説明する。ｕからｖへの各パスはｕの隣接ルータを経る。例では、ｕの３つの隣接ルータはｊ、ｊおよびｐoptuvの第１のルータである。３つのタイプのパスがｕに隣接するルータｎとｖとの間に存在する：
−ｐoptuvと共通のノードを持たない最適パスｐoptnv（図１３の例ではｉとｖの間の実線）
−ｐoptuvと共通のノードを有する最適パスｐoptnv（図１３の例ではｊとｖの間の実線）
−ｎからｖへの最適でないパス（例では破線）
上記のアルゴリズムに従えば、ｐoptivを含むパスについてのみ制約が必要である。
ｉとｖの間の破線で示されるパスｐgの場合、ｉからｕへのフローが考慮されるとき次の制約がすでに存在する。
【数２０】
0004768192.tif 000021
この制約は式１２と共に、ｐgを使うパスのコストはｐoptuvのコストよりも大きいことを暗示している。
ｊとｖの間のパスを考えると、ｋとｖの間の部分ｐoptuvと共通である。ルーティングの原理によれば、ｕからｋへの最短パスは太線に沿ってルーティングされることが知られている。ｕからｋへのこのフローについては、太線に沿ったパスｐoptukはｊを通る細線のパスより短かくなければならない。しかしこの制約はｐoptuvがｊを通る細線のパスよりも短かいということを暗示している。
このような不等式系の解が所望の／最適なデータパスを除くすべてのデータパスについてデータパスのデータリンクコストの合計が所望の／最適なデータパスのリンクコストの合計よりも大であることを示すならば、所望の／最適なデータパスは最短データパスに対応する。
例
本発明による方法の効果を実証するため、例示的なネットワークの最適化されたルーティングの結果を以下説明する。使用されるネットワークを図４に示す。図４の右側の６ノード／ルータだけのネットワークが選択されたのは、このサイズならば結果として得られるパスを例示することができるからである。８及び１４のノード／ルータを有するネットワークが選択されたのはそれらの複雑な構造のため多くの異なったデータパスが可能だからである。一例として、６ノード／ルータを有するネットワークについてリンク容量行列Ｃとデータフロー行列Ｆが表１及び表２に示される。
【００９７】
【表１】
0004768192.tif 000022
【００９８】
【表２】
0004768192.tif 000023
【００９９】
データリンクの物理的遅延ｈはすべて１に設定され、パラメータａrはすべての最適化において３に設定された。例えば、上記で説明されたプリソルバーを使用すると、１４ノード／ルータを有するネットワークについての変数の数は８８００という値から４７１４という値に減少した。さらに、制約の数も半分未満に減らすことができた。
【０１００】
全てのネットワークについて、いくつかのパラメータ設定による最適化が行われた。まず、上限リンク利用率について有効な上しきい値がない状態で最適化が行われた。これは、（「次善の最適化」の節で説明されたように）上限リンク利用率をパラメータｔ以下に維持する制約を省略し、パラメータａcを１０という値に設定することによって達成された。６ノード／ルータを有するネットワークについて結果として得られるルーティングを図５に例示する。４２．９％という最高利用率を有するデータリンクはデータリンク４−３である。最小平均リンク利用率の値は２２．４％と計算された。
【０１０１】
次に、パラメータａcを、４２．９％という計算された上限リンク利用率よりわずかに小さい０．４（＝４０％）という値に設定した。パラメータａcを反復的に、すなわち０．３７５（＝３７．５％）及び０．３６（＝３６％）という値に減らすことで、パラメータａcについての最適なルーティングが発見されたが、これはデフォルト最適化の結果に対応する０．３６という値を有した。
【０１０２】
目的関数（１）を使用するデフォルト最適化では、パラメータａtを１０００という値に設定した。６ノード／ルータを有するネットワークについてのこの最適化の結果を図６に例示する。ここでも最も利用されたデータリンクは再び４−３であったが、その利用率は３５．７％という値に低下した。その代わり、平均リンク利用率は２２．７％という値まで増大した。
【０１０３】
図５及び図６に示されるように、データフロー５−０はデータリンク４−３から外され、ノード／ルータ２及び１上でルーティングされた。従って、データフロー２−０についてのデータパスもノード／ルータ１上でルーティングされた。さらに、データリンク３−４のリンク利用率を４０％という値から３５．７％という値に下げるため、データフロー２−４はノード／ルータ３の代わりにノード／ルータ５上でルーティングされた。
【０１０４】
上記で説明されたデータリンクコストの決定に基づいて、最短パスルーティングが上記の最適化によって定められるルーティングと同等になるように、できる限り小さいデータリンクコストが指定された。図７及び図８は計算されたデータリンクコストを例示するが、ここでは対応するデータリンクコストと対応する物理的遅延が灰色の四角形の中に書かれている。図７に示されるように、データフロー５−０全体のデータリンクコストは３である。データフロー５−０についての他の可能なデータパスにはノード／ルータ２と１またはノード／ルータ２と３が含まれる。これらのパス全体の物理的遅延はそれぞれ５及び４である。最短パスは、最小化された平均リンク利用率を有する望ましいパスと同じである。
【０１０５】
図８では、上限リンク利用率の最小化に関する最適化に基づいて、データフロー５−０のデータパスについての物理的遅延はやはり３である。ノード／ルータ４と３またはノード／ルータ２と３上の他の可能なデータパスの物理的遅延はそれぞれ４及び６である。ここでも、最短データパスは望ましい／最適なデータパスに対応する。
【０１０６】
８及び１４ノード／ルータを有するネットワークについてのデータルーティングの最適化も同様に行われた。第１に、上限リンク利用率の制限なしで平均リンク利用率が最小化された。次に、上限リンク利用率を反復的に減らした。最後に、最適化が行われ可能な最小の上限リンク利用率が得られた。しかし、１４ノード／ルータを有するネットワークは最適解を得るには複雑すぎることが判明している。上限リンク利用率は３８．８％まで減少したが、上限リンク利用率の最小値は未知である。しかし、最小リンク利用率は３２％という値より大きいはずであるが、それはこの値については線形最適化問題の方程式系が実行不可能だからである。
【０１０７】
図９及び図１０では、８及び１４ノード／ルータを有するネットワークについて上限リンク利用率の上しきい値が選択されたルーティング最適化の結果が示される。上限リンク利用率は低下することがあるが、平均リンク利用率はほとんど変化しない。最大及び最小利用データリンクのリンク利用率の差を示す棒グラフによって表されるように、データトラフィック分配はより均質になり、上限リンク利用率の上しきい値はより厳密になっている。すなわち、差は８ノード／ルータを有するネットワークについてほぼ４分の１に減らすことができた（図９参照）。１４ノード／ルータを有するネットワークの場合、最適化効果はあまり明瞭でないが、それは、このネットワークでは、上限リンク利用率についての上しきい値の選択と無関係に約１％しか利用率のないリンクが存在しているからである（図１０参照）。
【０１０８】
最適化は上限リンク利用率の最高値の低減に帰結するので、個々のリンクのリンク利用率はその代わりに増大するはずである。図１１に例示されるように、選択されたデータリンクのリンク利用率が上限リンク利用率の様々な上しきい値について示される。当初利用率の高かったデータリンクのリンク利用率は上限リンク利用率の上しきい値を下げると低下する。これは例えばデータリンク９−４、４−９及び４−２に当てはまる。その結果、データリンク８−５、５−８及び３−１のデータリンクのリンク利用率が増大する。
【０１０９】
0004768192.tif 000024
【０１１０】
より小規模なネットワークの場合、必要な情報を収集し、ルーティングプロトコルによって（例えば、ルーティングプロトコルを変更または追加プロトコルを使用するなどして）行列を形成しルータ毎に最適ルーティングパラメータを計算することも可能である。この場合、中央ユニットは必要ない。
【図面の簡単な説明】
【図１】  ネットワーク中のデータパスに対する単一パスルーティングの結果を例示する。
【図２】  ネットワーク中のデータパスに対するトランスポート制約の結果を例示する。
【図３】  ネットワーク中のデータパスに対する本発明によるルーティング制約の結果を例示する。
【図４】  ６、８及び１４ノード／ルータのネットワークの例を示す。
【図５】  ６ノードネットワークについて、平均リンク利用率を最小にする本発明によるデータルーティングを例示する。
【図６】  ６ノードネットワークについて、上限リンク利用率を最小にする本発明によるデータルーティングを例示する。
【図７】  本発明による平均リンク利用率が最小化された６ノードネットワークのリンクコストを例示する。
【図８】  本発明による上限リンク利用率が最小化された６ノードネットワークのリンクコストを例示する。
【図９】  ８ノードネットワークについて本発明によるリンク利用率の変化に関する図である。
【図１０】  １４ノードネットワークについて本発明によるリンク利用率の変化に関する図である。
【図１１】  １４ノードネットワークの選択されたデータリンクについて本発明によるリンク利用率に関する図である。
【図１２】  目的関数によってのみ回避されトランスポート制約によっては回避されないループを示す図である。
【図１３】  本発明によるリンクコストアルゴリズムの一例を示す図である。
【図１】
0004768192.tif 000025
【図２】
0004768192.tif 000026
【図３】
0004768192.tif 000027
【図４】
0004768192.tif 000028
【図５】
0004768192.tif 000029
【図６】
0004768192.tif 000030
【図７】
0004768192.tif 000031
【図８】
0004768192.tif 000032
【図９】
0004768192.tif 000033
【図１０】
0004768192.tif 000034
【図１１】
0004768192.tif 000035
【図１２】
0004768192.tif 000036
【図１３】
0004768192.tif 000037