(57)【特許請求の範囲】
【請求項１】
複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計回路であって、前記多地点間通信サービスを求めるための数理計画問題を設定する設定手段と、前記設定手段で設定された数理計画問題を解いて前記多地点間通信サービスのためのパスを得る最適化手段とを有することを特徴とする通信ネットワーク設計回路。
【請求項２】
前記多地点間通信サービスのためのパスを予め設定される最適化基準に基づいて求めるようにしたことを特徴とする請求項１記載の通信ネットワーク設計回路。
【請求項３】
前記設定手段は、前記対象ネットワークにおけるリンク負荷を最小化しかつ前記最適化基準となる目的関数を設定しかつ前記リンク負荷を求める制約式を設定する最適化基準作成手段と、他のネットワークから流入するデータのトラフィックを収容する経路を選ぶための制約式を作成する経路選択条件条件作成手段と、前記入口ノード各々から流入するデータのトラフィック毎に各リンクに必要なリンク帯域を計算するための制約式を作成するユーザ別必要リンク容量計算条件作成手段と、各リンクにおいてリンク容量制限を越えないための制約式を作成するリンク収容条件作成手段とを含むことを特徴とする請求項１または請求項２記載の通信ネットワーク設計回路。
【請求項４】
前記設定手段の各手段は、各々並列的に処理するようにしたことを特徴とする請求項３記載の通信ネットワーク設計回路。
【請求項５】
複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計方法であって、前記多地点間通信サービスを求めるための数理計画問題を設定するステップと、その設定された数理計画問題を解いて前記多地点間通信サービスのためのパスを得るステップとを有することを特徴とする通信ネットワーク設計方法。
【請求項６】
前記多地点間通信サービスのためのパスを予め設定される最適化基準に基づいて求めるようにしたことを特徴とする請求項５記載の通信ネットワーク設計方法。
【請求項７】
前記数理計画問題を設定するステップは、前記対象ネットワークにおけるリンク負荷を最小化しかつ前記最適化基準となる目的関数を設定しかつ前記リンク負荷を求める制約式を設定するステップと、他のネットワークから流入するデータのトラフィックを収容する経路を選ぶための制約式を作成するステップと、前記入口ノード各々から流入するデータのトラフィック毎に各リンクに必要なリンク帯域を計算するための制約式を作成するステップと、各リンクにおいてリンク容量制限を越えないための制約式を作成するステップとを含むことを特徴とする請求項５または請求項６記載の通信ネットワーク設計方法。
【請求項８】
前記数理計画問題を設定するステップの各ステップは、各々並列的に処理するようにしたことを特徴とする請求項７記載の通信ネットワーク設計方法。
【請求項９】
複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計制御プログラムを記憶する記憶媒体であって、前記通信ネットワーク設計制御プログラムは前記対象ネットワークを設計するためのコンピュータに、前記多地点間通信サービスを求めるための数理計画問題を設定させ、その設定された数理計画問題を解いて前記多地点間通信サービスのためのパスを得させるようにしたことを特徴とする通信ネットワーク設計制御プログラムを記憶する記憶媒体。
【請求項１０】
前記通信ネットワーク設計制御プログラムは前記コンピュータに、前記多地点間通信サービスのためのパスを予め設定される最適化基準に基づいて求めさせるようにしたことを特徴とする請求項９記載の通信ネットワーク設計制御プログラムを記憶する記憶媒体。
【請求項１１】
前記通信ネットワーク設計制御プログラムは前記コンピュータに、前記数理計画問題を設定させる際に、前記対象ネットワークにおけるリンク負荷を最小化しかつ前記最適化基準となる目的関数を設定しかつ前記リンク負荷を求める制約式を設定させ、他のネットワークから流入するデータのトラフィックを収容する経路を選ぶための制約式を作成させ、前記入口ノード各々から流入するデータのトラフィック毎に各リンクに必要なリンク帯域を計算するための制約式を作成させ、各リンクにおいてリンク容量制限を越えないための制約式を作成させるようにしたことを特徴とする請求項９または請求項１０記載の通信ネットワーク設計制御プログラムを記憶する記憶媒体。
【請求項１２】
前記通信ネットワーク設計制御プログラムは前記コンピュータに、前記数理計画問題を設定させる際の各処理を各々並列的に処理させるようにしたことを特徴とする請求項１１記載の通信ネットワーク設計制御プログラムを記憶する記憶媒体。
【請求項１３】
複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計制御プログラムをネットワークで伝送する伝送媒体であって、前記通信ネットワーク設計制御プログラムは前記対象ネットワークを設計するためのコンピュータに、前記多地点間通信サービスを求めるための数理計画問題を設定させ、その設定された数理計画問題を解いて前記多地点間通信サービスのためのパスを得させるようにしたことを特徴とする通信ネットワーク設計制御プログラムをネットワークで伝送する伝送媒体。
【請求項１４】
前記通信ネットワーク設計制御プログラムは前記コンピュータに、前記多地点間通信サービスのためのパスを予め設定される最適化基準に基づいて求めさせるようにしたことを特徴とする請求項１３記載の通信ネットワーク設計制御プログラムをネットワークで伝送する伝送媒体。
【請求項１５】
前記通信ネットワーク設計制御プログラムは前記コンピュータに、前記数理計画問題を設定させる際に、前記対象ネットワークにおけるリンク負荷を最小化しかつ前記最適化基準となる目的関数を設定しかつ前記リンク負荷を求める制約式を設定させ、他のネットワークから流入するデータのトラフィックを収容する経路を選ぶための制約式を作成させ、前記入口ノード各々から流入するデータのトラフィック毎に各リンクに必要なリンク帯域を計算するための制約式を作成させ、各リンクにおいてリンク容量制限を越えないための制約式を作成させるようにしたことを特徴とする請求項１３または請求項１４記載の通信ネットワーク設計制御プログラムをネットワークで伝送する伝送媒体。
【請求項１６】
前記通信ネットワーク設計制御プログラムは前記コンピュータに、前記数理計画問題を設定させる際の各処理を各々並列的に処理させるようにしたことを特徴とする請求項１５記載の通信ネットワーク設計制御プログラムをネットワークで伝送する伝送媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信ネットワーク設計回路及びその設計方法並びにその制御プログラムを記録した記録媒体及び伝送媒体に関し、特に複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスの設計方法に関する。
【０００２】
【従来の技術】
従来、通信ネットワーク設計法、例えば、”Ｒｅｓｔｏｒａｔｉｏｎ  ｓｔｒａｔｅｇｉｅｓ  ａｎｄ  ｓｐａｒｅ  ｃａｐａｃｉｔｙ  ｒｅｑｕｉｒｅｍｅｎｔｓ  ｉｎ  ｓｅｌｆ−ｈｅａｌｉｎｇ  ＡＴＭ  ｎｅｔｗｏｒｋｓ”（Ｙｉｊｕｎ  Ｘｉｏｎｇ  ａｎｄ  Ｌｏｒｎｅ  Ｍａｓｏｎ，ＩＮＦＯＣＯＭ’９７，Ａｐｒｉｌ  １９９７）に記載の方法では、単一ノード間の通信のためのパスを設計している。そこでは通信を行うノードペア毎に通信量を定め、それらのノードペア間に固定的な帯域のパスを設定している。
【０００３】
従来の設計法に基づいて設計された結果の一例を図４に示す。まず、図４を参照して従来の設計法について説明する。図４において、ｄ１は設計法で対象となるネットワーク範囲を示し、以下、これを対象ネットワークとする。ｎ１〜ｎ７はノードを表す。ｕ１〜ｕ４は設計対象外のネットワークを表し、これらのネットワーク間の通信トラフィックが対象ネットワークに流入出する。以下、この対象外のネットワークをユーザネットワークとする。
【０００４】
例えば、ｕ１〜ｕ４はあるユーザのネットワークの異なる拠点を表している。ノードのうち、対象ネットワークとユーザネットワークとの境界上にあるノードをエッジノード、対象ネットワーク内のノードをコアノードとする。
【０００５】
ユーザネットワークからデータが入ってくる場合にはエッジノードを入口ノードとし、ユーザネットワークにデータが出ている場合にはエッジノードを出口ノードとする。普通、エッジノードは入口ノード及び出口ノードのどちらの役割も果たす。但し、ノードといった場合にはエッジノード及びコアノードの両方が含まれる。また、ノード間及びノード・対象外ネットワーク間の線分はリンクを意味し、これを（ｎ１，ｎ２）や（ｕ１，ｎ２）等と表現する。
【０００６】
図４おいてはリンクを一本しか記述していないが、両方向のリンクがあることを示す。例えば、リンク（ｎ１，ｎ２）はｎ１→ｎ２のリンクとｎ２→ｎ１のリンクとがあることを意味する。尚、同じノード組にいくつものリンクがあってもよい。リンクはその属性に帯域を持つ。図４では説明に必要な部分の帯域しか記述していない。
【０００７】
いま、ある多地点間サービスにおいて、入口ノードｎ３からデータが２Ｍｂ／ｓ流入し、入口ノードｎ１からデータが１Ｍｂ／ｓ流入し、出口ノードｎ６からデータが２Ｍｂ／ｓ流出し、出口ノードｎ５からデータが１Ｍｂ／ｓ流出するものとする。
【０００８】
従来の設計法では各入口ノードと出口ノードとの間に固定的にパスを設定する必要がある。例えば、＜ｎ２，ｎ７＞を１Ｍｂ／ｓ、＜ｎ２，ｎ６＞を２Ｍｂ／ｓ、＜ｎ１，ｎ７＞を１Ｍｂ／ｓ、＜ｎ１，ｎ６＞を１Ｍｂ／ｓとそれぞれのトラフィック量を決めてパスを設計する。ここで、パスをｐ１〜ｐ４で表し、従来の設計法によって図４に示すようなパスが設計された例を示している。
【０００９】
【発明が解決しようとする課題】
しかしながら、従来の設計法では、入口／出口ペア毎に通信量を与えてパスを設計するため、各始端ノードにユーザネットワークから入る通信量及び各終端ノードからユーザネットワークへ出る通信量を与え、その範囲内で任意に通信することができるという形態サービスを設計することができない。
【００１０】
そこで、本発明の目的は上記の問題点を解消し、入口ノードから流入するデータのトラフィック量及び出口ノードから流出するデータのトラフィック量のみを与え、その範囲内で任意に通信することができる多地点間通信サービスのためのパス、必要なリンク容量を求めることができる通信ネットワーク設計回路及びその設計方法並びにその制御プログラムを記録した記録媒体及び伝送媒体を提供することにある。
【００１１】
【課題を解決するための手段】
本発明による通信ネットワーク設計回路は、複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計回路であって、前記多地点間通信サービスを求めるための数理計画問題を設定する設定手段と、前記設定手段で設定された数理計画問題を解いて前記多地点間通信サービスのためのパスを得る最適化手段とを備えている。
【００１２】
本発明による通信ネットワーク設計方法は、複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計方法であって、前記多地点間通信サービスを求めるための数理計画問題を設定するステップと、その設定された数理計画問題を解いて前記多地点間通信サービスのためのパスを得るステップとを備えている。
【００１３】
本発明による通信ネットワーク設計制御プログラムを記録した記録媒体は、複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計制御プログラムを記憶する記憶媒体であって、前記通信ネットワーク設計制御プログラムは前記対象ネットワークを設計するためのコンピュータに、前記多地点間通信サービスを求めるための数理計画問題を設定させ、その設定された数理計画問題を解いて前記多地点間通信サービスのためのパスを得させるようにしている。
【００１４】
本発明による通信ネットワーク設計制御プログラムを記録した伝送媒体は、複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計制御プログラムをネットワークで伝送する伝送媒体であって、前記通信ネットワーク設計制御プログラムは前記対象ネットワークを設計するためのコンピュータに、前記多地点間通信サービスを求めるための数理計画問題を設定させ、その設定された数理計画問題を解いて前記多地点間通信サービスのためのパスを得させるようにしている。
【００１５】
すなわち、本発明の通信ネットワーク設計回路は、多地点間通信サービスを求めるための数理計画問題を設定する最適化基準作成手段、経路選択条件条件作成手段、ユーザ別必要リンク容量計算条件作成手段、リンク収容条件作成手段と、これらの手段によって作成された数理計画問題を解く最適化手段とを有することを特徴とする。
【００１６】
最適化基準作成手段はリンク負荷を最小化する目的関数を設定し、さらにリンク負荷を求める制約式を設定する。経路選択条件条件作成手段は対象ネットワークにおいて流入するデータのトラフィック量を収容する経路を選ぶための制約式を作成する。
【００１７】
ユーザ別必要リンク容量計算条件作成手段は各ユーザの入口ノードから入ってきたデータ毎に各リンクにおいて必要なリンク帯域を計算するための制約式を作成する。リンク収容条件作成手段は各リンクにおいてリンク容量制限を越えないための制約式を作成する。最適化手段はこれらの手段によって作成された数理計画問題を解く。
【００１８】
これによって、入口ノードから流入するトラフィック量と出口ノードから流出するトラフィック量とをのみ与えてその範囲内で任意に通信することができる多地点間通信サービスのためのパスを最適化基準に基づいて求めることが可能となる。
【００１９】
【発明の実施の形態】
次に、本発明の一実施例について図面を参照して説明する。図１は本発明の一実施例による多地点間通信サービスのための設計回路（以下、設計回路とする）の構成を示すブロック図である。図１において、本発明の一実施例による設計回路はコンピュータ１と、キーボード等の入力部２と、ディスプレイ装置等の出力部３と、記録媒体（または伝送媒体）４とから構成されている。
【００２０】
コンピュータ１は最適化基準作成手段１１と、経路選択条件条件作成手段１２と、ユーザ別必要リンク容量計算条件作成手段１３と、リンク収容条件作成手段１４と、最適化手段１５とを備えている。
【００２１】
記録媒体４はフロッピディスクやＲＯＭ（リードオンリメモリ）、その他の記録媒体もしくはネットワークで伝送される媒体であり、コンピュータ１を多地点間通信サービスのための設計回路として機能させるためのプログラムが記録されている。
【００２２】
このプログラムはコンピュータ１によって記録媒体４から読取られ、コンピュータ１の動作を制御することで、コンピュータ１上に最適化基準作成手段１１、経路選択条件条件作成手段１２、ユーザ別必要リンク容量計算条件作成手段１３、リンク収容条件作成手段１４、最適化手段１５各々の機能を実現する。
【００２３】
最適化基準作成手段１１は対象ネットワークにおけるリンク負荷を最小化しかつ最適化基準となる目的関数を設定し、さらにリンク負荷を求める制約式を設定する。経路選択条件条件作成手段１２は他のネットワークから流入するデータのトラフィックを収容する経路を選ぶための制約式を作成する。
【００２４】
ユーザ別必要リンク容量計算条件作成手段１３は入口ノード各々から流入するデータのトラフィック毎に各リンクに必要なリンク帯域を計算するための制約式を作成する。
【００２５】
リンク収容条件作成手段１４は各リンクにおいてリンク容量制限を越えないための制約式を作成する。最適化手段１５は上記の最適化基準作成手段１１、経路選択条件条件作成手段１２、ユーザ別必要リンク容量計算条件作成手段１３、リンク収容条件作成手段１４各々によって作成された数理計画問題を解き、多地点間通信サービスのためのパスを得る。
【００２６】
続いて、本実施例の動作について詳細に説明する。まず、本実施例で使う記号について説明する。この記号は集合、変数、定数に区分される。集合としてはＬがリンク集合を、Ｄがユーザ集合を、Ｎｄ  がユーザｄの入口エッジノード集合を、Ｐｄ  がユーザｄの入口ノードと出口ノードとのペア集合を、Ｉ（ａ，ｚ）  が入口エッジノードａと出口エッジノードｚとの間のパス候補集合をそれぞれ示している。
【００２７】
リンク集合Ｌにおいて、各要素は（ｌ，ｍ，ｋ）で表わされる。ここで、ｌは発ノード、ｍは着ノード、ｋは同じノード間で複数のリンクがある場合の識別子である。この最後の識別子をサブリンク識別子と呼ぶ。ユーザ集合Ｄにおいては各ユーザ毎に一つの多地点間サービスがある。パス候補集合Ｉ（ａ，ｚ）  においては各要素をｉ（ａ，ｚ）  と表している。
【００２８】
変数としてはｆｉ  が０−１変数を、φが対象ネットワークにおけるリンク負荷を、ｗ（ｌ，ｍ，ｋ）ａｄ  が出口エッジノードに流れるデータフローの合計をそれぞれ示している。
【００２９】
０−１変数ｆｉ  はユーザｄが入口エッジノードａと出口エッジノードｚとの間のパス候補ｉ（ａ，ｚ）  をパスとして採用する時に１を、そうでない時に０をとる。出口エッジノードに流れるデータフローの合計ｗ（ｌ，ｍ，ｋ）ａｄ  はユーザｄの入口エッジノードａから流入するデータのトラフィックに関して、リンク（ｌ，ｍ，ｋ）より下流にある出口エッジノードに流れるデータフローの合計を表す。
【００３０】
定数としてはｖａｄが入口エッジノードａから流入してくるデータのトラフィック量を、ｖｚｄが出口エッジノードｚから流出して行くデータのトラフィック量を、ｇｉ  がインディケータ定数を、ｃ（ｌ，ｍ，ｋ）  がリンク（ｌ，ｍ，ｋ）における容量制限をそれぞれ示している。
【００３１】
トラフィック量ｖａｄはユーザｄに関して入口エッジノードａから流入してくるデータのトラフィック量を示し、トラフィック量ｖｚｄはユーザｄに関して出口エッジノードｚから流出して行くデータのトラフィック量を示している。インディケータ定数ｇｉ  はパス候補ｉ（ａ，ｚ）  がリンク（ｌ，ｍ，ｋ）を通る時に１をとり、そうでない時に０をとる。
【００３２】
上記の記号を用いて本発明の一実施例による設計回路について説明する。まず、最適化基準作成手段１１は対象ネットワークにおけるリンク負荷を最小化しかつ最適化基準となる目的関数、
Ｍｉｎφ                                              ……（１）
を設定し、リンク負荷φを求める制約式、
【数１】
0003578062.tif 000002
0003578062.tif 000003
を設定する。
【００３３】
続いて、経路選択条件作成手段１２は他のネットワークから流入するデータのトラフィックを収容する経路を選ぶための制約式、
【数２】
0003578062.tif 000004
0003578062.tif 000005
【数３】
0003578062.tif 000006
0003578062.tif 000007
を作成する。
【００３４】
ユーザ別必要リンク容量計算方法作成手段１３は各ユーザの入口ノードから流入するデータのトラフィック毎に各リンクにおいて必要なリンク帯域を計算するための制約式、
【数４】
0003578062.tif 000008
0003578062.tif 000009
を作成する。
【００３５】
リンク収容条件作成手段作成手段１４は各リンクにおいてリンク容量制限を越えないための制約式、
【数５】
0003578062.tif 000010
0003578062.tif 000011
を作成する。
【００３６】
最後に、最適化手段１５は上記の最適化基準作成手段１１、経路選択条件条件作成手段１２、ユーザ別必要リンク容量計算条件作成手段１３、リンク収容条件作成手段１４各々によって作成された数理計画問題、つまり（１）式〜（５）式を解き、多地点間通信サービスのためのパスを得る。
【００３７】
図２は本発明の一実施例による設計回路の処理動作を示すフローチャートである。これら図１及び図２を参照して本発明の一実施例による設計回路の処理動作について説明する。尚、図２に示す処理動作はコンピュータ１が上記の記憶媒体４に記憶されたプログラムを実行することで実現される。
【００３８】
入力部２から上記の集合、変数、定数が入力されると（図２ステップＳ１）、最適化基準作成手段１１は対象ネットワークにおけるリンク負荷φを最小化しかつ最適化基準となる目的関数［（１）式］を設定し（図２ステップＳ２）、リンク負荷φを求める制約式［（２）式］を設定する（図２ステップＳ３）。
【００３９】
同様に、上記の集合、変数、定数が入力されると（図２ステップＳ１）、経路選択条件条件作成手段１２はユーザネットワークから流入するデータのトラフィックを収容する経路を選ぶための制約式［（３）式］を作成し（図２ステップＳ４）、ユーザ別必要リンク容量計算条件作成手段１３は入口ノード各々から流入するデータのトラフィック毎に各リンクにおいて必要なリンク帯域を計算するための制約式［（４）式］を作成する（図２ステップＳ５）。
【００４０】
また、上記の集合、変数、定数が入力されると（図２ステップＳ１）、リンク収容条件作成手段１４は各リンクにおいてリンク容量制限を越えないための制約式［（５）式］を作成する（図２ステップＳ６）。
【００４１】
上述したように、最適化基準作成手段１１、経路選択条件条件作成手段１２、ユーザ別必要リンク容量計算条件作成手段１３、リンク収容条件作成手段１４によってそれぞれ並列的に多地点間通信サービスを求めるための数理計画問題が設定されるので、最適化手段１５は数理計画問題を解き、多地点間通信サービスのためのパスを得る（図２ステップＳ７）。
【００４２】
図３は本発明の一実施例による多地点間通信サービスの設計結果の一例を示す図である。この図３を参照して本発明の一実施例による多地点間通信サービスの設計結果の一例について説明をする。
【００４３】
図３において、ｄ１は設計法で対象となるネットワーク範囲を示し、これを対象ネットワークと呼ぶ。ｎ１〜ｎ７はノードを表す。ｕ１〜ｕ４は設計対象外のネットワークを表し、これらのネットワーク間の通信トラフィックが対象ネットワークに流入出する。この対象外のネットワークをユーザネットワークと呼ぶことにする。例えば、ｕ１〜ｕ４はあるユーザのネットワークの異なる拠点を表している。
【００４４】
ノードのうち、対象ネットワークとユーザネットワークの境界上にあるノードをエッジノード、対象ネットワーク内のノードをコアノードとそれぞれ呼ぶ。ユーザネットワークからトラフィックが入ってくる場合にはエッジノードを入口ノードと呼び、ユーザネットワークにトラフィックが出ている場合にはエッジノードを出口ノードと呼ぶ。
【００４５】
普通、エッジノードは入口ノード／出口ノードどちらの役割も果たす。但し、ノードといった場合にはエッジノード及びコアノードの両方が含まれる。また、ノード間及びノード・対象外ネットワーク間の線分はリンクを意味し、これを（ｎ１，ｎ２）や（ｕ１，ｎ２）等と表現する。
【００４６】
図３ではリンクを一本しか記述していないが、両方向のリンクがあることを示す。例えば、リンク（ｎ１，ｎ２）はｎ１→ｎ２のリンクと、ｎ２→ｎ１のリンクとがあることを意味する。尚、同じノード組にいくつものリンクがあってもよい。リンクはその属性に帯域を持つ。図３では説明に必要な部分の帯域しか記述していない。
【００４７】
いま、ある多地点間通信サービスにおいて、入口ノードｎ３からデータが２Ｍｂ／ｓ流入し、入口ノードｎ１からデータが１Ｍｂ／ｓ流入し、出口ノードｎ６からデータが２Ｍｂ／ｓ流出し、出口ノードｎ５からデータが１Ｍｂ／ｓ流出するものとする。
【００４８】
すると、任意の入口／出口ノードペア間＜ｎ３，ｎ６＞、＜ｎ３，ｎ５＞、＜ｎ１，ｎ６＞、＜ｎ１，ｎ５＞で、上記の流入量・流出量の範囲内で自由に通信することができるようにするために、パスｐ１〜ｐ４のパスを求める。
【００４９】
また、この多地点間通信サービスのために必要な帯域は、図３に示すように、リンク（ｎ３，ｎ４）は２Ｍｂ／ｓ、リンク（ｎ４，ｎ６）は２Ｍｂ／ｓ、リンク（ｎ１，ｎ４）は１Ｍｂ／ｓ、リンク（ｎ４，ｎ５）は１Ｍｂ／ｓとなる。
【００５０】
ここで、例えば、リンク（ｎ４，ｎ５）はノードｎ３からデータが２Ｍｂ／ｓ流入し、ノードｎ１からデータが１Ｍｂ／ｓ流入しているので、最大３Ｍｂ／ｓのデータが流れる可能性があるが、ノードｎ５から流出するデータのトラフィック量が１Ｍｂ／ｓなので、１Ｍｂ／ｓとなる。
【００５１】
このように、多地点間通信サービスのための設計方法を数理計画問題として、最適化基準作成手段１１と経路選択条件条件作成手段１２とユーザ別必要リンク容量計算条件作成手段１３とリンク収容条件作成手段１４とによって設定し、それを最適化手段１５で解いているので、入口ノードから流入するデータのトラフィック量及び出口ノードから流出するデータのトラフィック量のみを与えて、その範囲内で任意に通信することができる多地点間通信サービスのためのパス、必要なリンク容量を求めることができる。
【００５２】
上記の定数において、最小のリンク空き容量としてηを追加すると、最適化手段１１は対象ネットワークにおけるリンクの空き容量を最大化する目的関数として、
Ｍａｘｉｍｉｚｅ  η                        ……（７）
を設定し、さらに空き容量を求める制約式として、
【数６】
0003578062.tif 000012
0003578062.tif 000013
を設定する。これらの設定を行うことによっても、最適化基準作成手段１１は最適化のための数理計画問題を作成することができる。
【００５３】
また、上記の変数において、リンク（ｌ，ｍ，ｋ）の単位容量あたりのリンクコストとしてω（ｌ，ｍ，ｋ）  を追加すると、最適化基準作成手段１１は対象ネットワークに流入するデータトラフィックを最小のリンクコストで収容する目的関数として、
【数７】
0003578062.tif 000014
0003578062.tif 000015
を設定する。この設定を行うことによっても、最適化基準作成手段１１は最適化のための数理計画問題を作成することができる。
【００５４】
続いて、ユーザ別必要リンク容量計算方法作成手段１３が各ユーザの入口ノードから入ってきたトラフィック毎に各リンクにおいて必要なリンク帯域を計算するための制約式を整数計画問題の制約式として設定する場合について説明する。整数計画問題は数理計画問題の一種であり、最適化手段１５において各種の整数計画問題の解法（伊里他、「最適化ハンドブック」朝倉書店）を利用することができる。
【００５５】
いま、ｘ（ｌ，ｍ，ｋ）ａｄ  をユーザｄの入口エッジノードａから流入するトラフィックに関して、リンク（ｌ，ｍ，ｋ）より下流にある出口エッジノードに流れるフローの合計が入口エッジノードａに流入してくるトラフィック量ｖａｄより大きければ１をとり、そうでなければ０をとる０−１変数とし、Ｍを任意の大きな数とする。ここで、Ｍは、
【数８】
0003578062.tif 000016
0003578062.tif 000017
という式からあたえられる。
【００５６】
ユーザ別必要リンク容量計算方法作成手段１３はこれらを用いて次の３つの制約式、
【数９】
0003578062.tif 000018
0003578062.tif 000019
【数１０】
0003578062.tif 000020
0003578062.tif 000021
【数１１】
0003578062.tif 000022
0003578062.tif 000023
を設定する。
【００５７】
これによって、ユーザ別必要リンク容量計算方法作成手段１３は各ユーザの入口エッジノードａから入ってきたトラフィック毎に各リンクにおいて必要なリンク帯域を計算するための制約式を整数計画問題の制約式として設定することができる。
【００５８】
【発明の効果】
以上説明したように本発明によれば、複数のノードからなりかつ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量及び他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えてその範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワーク設計回路において、多地点間通信サービスを求めるための数理計画問題を設定し、その設定された数理計画問題を解いて多地点間通信サービスのためのパスを得ることによって、入口ノードから流入するデータのトラフィック量及び出口ノードから流出するデータのトラフィック量のみを与え、その範囲内で任意に通信することができる多地点間通信サービスのためのパス、必要なリンク容量を求めることができるという効果がある。
【図面の簡単な説明】
【図１】本発明の一実施例による多地点間通信サービスのための設計回路の構成を示すブロック図である。
【図２】本発明の一実施例による多地点間通信サービスのための設計回路の処理動作を示すフローチャートである。
【図３】本発明の一実施例による多地点間通信サービスの設計結果の一例を示す図である。
【図４】従来例による多地点間通信サービスの設計結果の一例を示す図である。
【符号の説明】
１  コンピュータ
２  入力部
３  出力部
４  記録媒体（または伝送媒体）
１１  最適化基準作成手段
１２  経路選択条件条件作成手段
１３  ユーザ別必要リンク容量計算条件作成手段
１４  リンク収容条件作成手段
１５  最適化手段
【図１】
0003578062.tif 000024
【図２】
0003578062.tif 000025
【図３】
0003578062.tif 000026
【図４】
0003578062.tif 000027