JPH0983546A - 経路選択方法および経路選択装置および通信網設計方法および通信網設計装置 - Google Patents

Abstract

(57)【要約】 【課題】与えらえたネットワーク上での各種コネクショ
ンの経路選択と、与えられたトラヒック需要を収容する
通信網の設計が効率よく行える。 【解決手段】評価値算出部２で双方向コネクション毎
に、その上りコネクションの帯域と下りコネクションの
帯域とを用いて評価値を求め、この算出された評価値に
基づく順位に従って、経路選択部３で各双方向コネクシ
ョンに対し、最小コスト経路を割り当てる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、複数のノード装置
を接続してなる通信網において、最適な情報の転送経路
を選択する経路選択方法および経路選択装置に関する。
また、本発明は、所望のトラヒック需要を収容できる最
適な通信網を設計する通信網設計方法および通信網設計
装置に関する。

【０００２】

【従来の技術】例えば、複数の端末装置を複数の交換機
を介して接続し、これら端末装置間でセルと呼ばれる固
定長パケットを転送して通信を行うＡＴＭ（Asynchrono
usTransfer Mode：非同期転送モード）通信網において
は、そのセルを転送する経路として、例えば、その物理
網上に複数のＶＰＣ（ Virtual Path Connection）を張
りＶＰ網を設定する必要がある。

【０００３】このＡＴＭ通信網のように、複数のノード
とリンクから構成される通信網においては、複数のコネ
クションの最適な経路を一度に決定する問題( 経路選択
問題) の解法は、従来から種々提案されている。

【０００４】一般に、この問題を最適に解くためにはシ
ンプレックス法等を用いて連立方程式を解かなければな
らず、大規模な問題に対して最適解を求めることは、必
要とする演算量及びメモリ量の観点からあきらめざるを
得ない。

【０００５】そこで、経路選択問題を近似的に解く方法
が必要となる。この近似解法には、例えば、佐々木良
一、中村勤、鈴木三知男、影井隆による「高速ディジタ
ル回線障害時用網再構成最適化技術」( 電子情報通信学
会論文誌 vol. J72 - B-I, No.4 , pp.272-280 , 1989)
がある。

【０００６】この方法は、片方向コネクションに対する
経路選択について述べられており、双方向コネクション
に対する経路選択については述べられていない。そのた
め、上記の方法を用いて双方向コネクションの経路選択
を行なうためには、その上りコネクションと下りコネク
ションを独立な片方向コネクションとみなして経路選択
を行なうことが考えられる。すると、双方向ペアをなす
上りコネクションと下りコネクションが同じ経路を通る
保証がなくなる。

【０００７】また、より計算量の少ない経路選択アルゴ
リズムとして、コネクションをその帯域の大きい順にそ
の最小コスト経路に設定していく方法が考えられる。こ
の方法は、片方向コネクション、あるいは双方向ペアを
なす上りコネクションと下りコネクションの帯域が等し
い双方向コネクション( 対称双方向コネクション) に対
する経路選択を行なう場合には良い結果を与える。

【０００８】しかし、双方向ペアをなす上りコネクショ
ンと下りコネクションの帯域が異なる双方向コネクショ
ン( 非対称双方向コネクション) に対する経路選択を行
なう場合には、1 本の双方向コネクションに対して帯域
が２種類割り当てられているため、このアルゴリズムを
適用することができない。もちろん、双方向コネクショ
ンの上りコネクションと下りコネクションを独立な片方
向コネクションとみなして経路選択を行なうことはでき
るが、その場合は双方向ペアをなす上りコネクションと
下りコネクションが同じ経路を通る保証はなくなる。

【０００９】一方、例えば画像データベースをアクセス
する場合を考えると、端末から画像データベースへのコ
ネクションは低速でよいが、画像データベースから端末
へのコネクションは高速であることが要求される。この
ような非対称双方向コネクションを設定する需要は今後
増すことが予想される。

【００１０】ＡＴＭ通信網では、ある経路に沿ってコネ
クションの設定要求を出すと、その経路上の上りと下り
の両方向に対してＶＣＩ（Virtual Channel Identifie
r）、すなわち、各コネクションの識別子が確保され
る。つまり、片方向コネクションを設定する場合には、
逆方向の要求帯域を「０」に設定することにより実現さ
れ、逆方向のＶＣＩは確保されたままとなる。そのた
め、双方向ペアをなす上りコネクションと下りコネクシ
ョンに異なる経路を設定すると、上りと下りの各々のコ
ネクションの逆方向に割り当てられたＶＣＩを無駄にす
ることになる。

【００１１】また、双方向ペアをなす上りコネクション
と下りのコネクションが異なる経路を通ると、上りと下
りの各々のコネクションに対するＯＡＭ（Oprations ,A
dministration and Maintenance）セルのループバック
用のコネクションが必要となり、合計４本のコネクショ
ンを張ることが必要となる。

【００１２】それに対して、上りコネクションと下りコ
ネクションの経路が同じである場合には、上り( 下り)
コネクションのＯＡＭセルのループバック用のコネクシ
ョンには、下り( 上り) コネクションを用いることがで
きるため、２本のコネクションを張ればよい。それ故、
コネクション管理という点からも、双方向ペアをなす上
りコネクションと下りコネクションの経路は同じである
ことが望ましい。

【００１３】ここでは具体例として、ＡＴＭＴ通信網を
挙げたが、ＡＴＭ通信網に限らず、双方向ペアをなす上
りコネクションと下りコネクションの経路は同じである
ことが望ましい通信網は存在し、また今後も出現するこ
とが予想される。

【００１４】次に、先に挙げた経路選択問題の近似解法
（「高速ディジタル回線障害時用網再構成最適化技
術」）について、簡単に説明する。

【００１５】まず初めに、利得の定義を行なう。コネク
ションを張る経路には、望ましい経路そうでない経路が
存在することが考えられ、また全てのコネクションが張
れない場合には張るべきコネクションに優先度のあるこ
とが考えられる。このような経路の好悪、コネクション
の優先度を表す変数を利得として定義し、コネクション
ｋに経路ｌを割り当てた場合に得られる利得をＣ_klで表
わす。そしてここでは、各リンクを通過するコネクショ
ンの帯域の合計はそのリンクの容量以下であるという条
件の基で、得られる利得を最大とするようにコネクショ
ンの経路を決定する。そのために、リンクｊ（＝１，
２，…，Ｊ）の使用率をＥ_j とし、これを用いてベクト
ルＰ_u をＰ_u ＝｛Ｅ₁ ，Ｅ₂ …，Ｅ_J ｝で定義する。

【００１６】コネクションｋに経路ｌを割り当てた場合
に、リンクｊに新たに加わる負荷Ｆ_klj を用いて、ベク
トルＰ_klをＰ_kl＝｛Ｆ_kl1 ，Ｆ_kl2 ，…，Ｆ_klJ ｝と定
義する。Ｇ_klを式（１）で求め、Ｇ_klを最大とするコネ
クションと経路を探す。

【００１７】

【数１】 但し、Ａ・ＢはベクトルＡとＢの内積を表し、｜Ａ｜は
ベクトルＡの長さを表す。Ｇ_klを最大とするコネクショ
ンをｍ、経路をｉとすると、コネクションｍに経路ｉを
割り当て、Ｐ_u ＝Ｐ_u ＋Ｐ_miとする。以後、同様の操作
を繰り返すことにより、コネクションに経路を割り当て
ていく。

【００１８】概念的に述べると、この方法は、得られる
利得はなるべく大きくなるように、そして現在までに経
路の決定したコネクションが使用している帯域を表すベ
クトルＰ_u をなるべく大きくしないように次に張るべき
コネクションとその経路を決定している。これは、使用
帯域の点からみると、リンクの負荷をなるべく分散し、
各リンクの負荷を均一にしていると言える。

【００１９】具体例として、図１６に示すネットワーク
について、ノードＡからノードＣへの帯域１０Ｍｂｐｓ
のコネクションを１０本張る場合を考える。ただし、図
１６のネットワークのリンクは片方向リンクでその容量
は１５０Ｍｂｐｓであるとする。また、簡単のために、
Ｃ_klの値はコネクションｋの帯域と等しいものとする。
これは、帯域の大きいコネクションは帯域の小さいコネ
クションよりも優先され、各コネクションにおいて経路
に対する好悪はないことを意味する。

【００２０】初めは、Ｐ_u ＝０のためＧ_klを計算するこ
とができないので、

【００２１】

【数２】 を最大とするコネクションと経路を探す。この結果、１
本目を経路Ａ→Ｂ→Ｃに張ったとすると、Ｐ_u ＝｛１０
／１５０，１０／１５０，０，０，０｝となり、２本目
は経路Ａ→Ｄ→Ｃに張られることとなる。以後この繰り
返しにより、経路Ａ→Ｂ→Ｃにコネクションが５本、経
路Ａ→Ｄ→Ｃに５本のコネクションが張られることとな
る。この例では、１０本のコネクションを経路Ａ→Ｂ→
Ｃに設定できるにもかかわらず、２つの経路にコネクシ
ョンが分散される。

【００２２】このように負荷を分散する傾向があるた
め、必要以上にリンクの負荷を分散する場合が生じ、こ
のため、経路選択の性能が劣化する場合がある。例え
ば、図１６のネットワークに、図１７に示すような４本
のコネクションを張る場合について考える。

【００２３】初めは、Ｐ_u ＝０のためＧ_klを計算するこ
とができないため、式（２）を最大とするコネクション
と経路を探す。その結果、コネクション４に経路Ｄ→Ｅ
が割り当てられる。次に、Ｐ_u ＝｛０，０，０，０，５
／１５０｝を用いて、式（１）を最大にするコネクショ
ンと経路を探す。その結果、コネクション１を経路Ａ→
Ｂ→Ｃに割り当てることとなる。次に、Ｐ_u ＝｛１０／
１５０，１０／１５０，０，０，５／１５０｝を用い
て、式（１）を最大にするコネクションと経路を探す。
その結果、コネクション２を経路Ａ→Ｄ→Ｃに割り当て
ることとなる。次に、Ｐ_u ＝｛１０／１５０，１０／１
５０，１０／１５０，１０／１５０，５／１５０｝を用
いて、式（１）を最大にするコネクションと経路を探
す。しかし、リンク３の残余帯域が不足しているため、
コネクション４を設定することのできる経路を存在しな
い。この例では、リンクの負荷を分散させるために、コ
ネクション２の経路をＡ→Ｂ→ＣではなくＡ→Ｄ→Ｃと
してしまうので、コネクション３の経路を失くしてしま
っている。

【００２４】以上説明したような経路選択問題と同様
に、例えば、パケット専用線網の網設計の際にも、送信
ノードと受信ノードの各組合せに対して、送出するであ
ろうパケット量を推定し、ノード間に設定するリンクの
容量とパケットの経路を決定する問題、すなわち、通信
網設計問題を解く必要がある。この通信網設計問題の従
来の解法例としては、例えば、Leonard Kleinrock によ
るQueueing Systems（ vol２，ｐｐ．２７０−４２１，
John Wiley＆Sons，１９７６）に記されている。

【００２５】この方法は、Flow Deviation法（ＦＤ法）
と呼ばれ、効果的な方法である。しかし、この方法に
は、最小化したい目標関数が各ノード間を通過するトラ
ヒック量の関数であり、しかも目標関数が各ノード間を
通過するトラヒック量に対して２回微分可能な凸関数で
なければならない。具体的には、網内でのリンクコスト
の和を最小化する場合には、リンクコストの和が各ノー
ド間を通過するトラヒック量の関数として表せなければ
ならず、しかもリンクコストの和を表す関数は、各ノー
ド間を通過するトラヒック量に対して２回微分可能な凸
関数でなければならない。もし、この条件が満たされて
いない場合には、ＦＤ法は、局所最適解しか得ることが
できない。

【００２６】リンクが任意の容量をとり得るのではな
く、リンクの種類毎に固定の容量をとる場合には、リン
クコストの和が各ノード間を通過するトラヒック量に関
して不連続関数となり、２回微分可能とならない。それ
ゆえ最適解を得ることはできず、また近似解を求める効
果的な方法もなかった。

【００２７】

【発明が解決しようとする課題】このように、複数のノ
ード（交換機、端末装置等）とリンク（伝送路）から構
成される通信網の運用および、そのような通信網の設計
においては、一般に、リンクの容量、各ノード間のトラ
ヒック量、コスト等を考慮しながら、最適な経路を求め
ることが必須となっている。

【００２８】しかし、従来の経路選択問題の近似解法
は、片方向コネクションに対しての経路選択を行なうも
のであり、そのため非対称双方向コネクションの経路選
択を行なう場合には、双方向ペアをなす上りコネクショ
ンと下りコネクションが同じ経路を通るという条件の下
に経路選択問題を解くことができないという第１の問題
点があった。

【００２９】また、従来の経路選択問題の近似解法は、
リンクの負荷を分散するように経路選択を行なうため、
過度に負荷分散を行なうことにより経路選択の結果を劣
化させるという第２の問題点があった。

【００３０】さらに、従来の網設計問題の解法には、評
価関数が各リンクを通るトラヒック量に関して２回微分
可能な凸関数でない場合には、最適解を求めることはで
きず、近似解を求める効果的な方法もいという第３の問
題点があった。

【００３１】そこで、本発明は、第１の問題点に鑑み、
双方向ペアをなす上りコネクションと下りコネクション
の帯域が異なる場合、すなわち、非対称双方向コネクシ
ョンの経路選択を行なう場合にも、双方向ペアをなす上
りコネクションと下りコネクションについて同一の経路
を選択することができる経路選択方法および経路選択装
置を提供することを目的とする。

【００３２】また、本発明は、第２の問題点に鑑み、リ
ンクの負荷分散を過度に行なうことなく、それにより経
路選択問題の精度の良い近似解を得ることができる経路
選択方法およびを経路選択装置を提供することを目的と
する。

【００３３】さらに、本発明は、第３の問題点に鑑み、
通信網設計問題の評価関数が２回微分可能な凸関数でな
い場合でも、網設計問題の精度の良い近似解を与えるこ
とができる通信網設計方法および通信網設計装置を提供
するものである。

【００３４】

【課題を解決するための手段】本発明の経路選択方法
は、複数のノード装置を接続してなる通信網に、複数の
双方向コネクションの経路を、その上りコネクションと
下りコネクションが同じ経路を通るように選択する経路
選択方法であって、前記双方向コネクションの上りコネ
クションの帯域と下りコネクションの帯域をもとに、そ
の双方向コネクションの評価値を算出し、前記複数の双
方向コネクションのそれぞれについて算出された前記評
価値に基づく順位に従って、前記複数の双方向コネクシ
ョンの経路をそれぞれ選択することにより、双方向ペア
をなす上りコネクションと下りコネクションの帯域が異
なる場合、すなわち、非対称双方向コネクションの経路
選択を行なう場合にも、双方向ペアをなす上りコネクシ
ョンと下りコネクションについて同一の経路を選択する
ことが可能となる。

【００３５】また、本発明の経路選択装置は、複数のノ
ード装置を接続してなる通信網に、複数の双方向コネク
ションの経路を、その上りコネクションと下りコネクシ
ョンが同じ経路を通るように選択する経路選択装置であ
って、前記双方向コネクションの上りコネクションの帯
域と下りコネクションの帯域をもとに、前記双方向コネ
クションの評価値を算出する評価値算出手段と、この評
価値算出手段で前記複数の双方向コネクションのそれぞ
れについて算出された評価値に基づく順位に従って、前
記複数の双方向コネクションの経路をそれぞれ選択する
経路選択手段と、を具備することにより、非対称双方向
コネクションの経路選択を行なう場合にも、双方向ペア
をなす上りコネクションと下りコネクションについて同
一の経路を選択することが可能となる。

【００３６】また、本発明の経路選択方法は、複数のノ
ード装置を接続してなる通信網に、複数の双方向コネク
ションの経路を、その上りコネクションと下りコネクシ
ョンが同じ経路を通るように選択する経路選択方法であ
って、必要に応じて出力されたパラメータと、前記双方
向コネクションの上りコネクションの帯域と下りコネク
ションの帯域をもとに、前記双方向コネクションの評価
値を算出し、この算出された評価値に基づく順位に従
い、前記複数の双方向コネクションの経路をそれぞれ選
択し、その選択結果を前記パラメータに対応する経路選
択結果として出力し、この出力された複数の経路選択結
果に基づき、前記複数の双方向コネクションの最適経路
を判断することにより、非対称双方向コネクションの経
路選択を行なう場合にも、双方向ペアをなす上りコネク
ションと下りコネクションについて同一の経路を選択す
ることが可能となる。

【００３７】また、本発明の経路選択装置は、複数のノ
ード装置を接続してなる通信網に、複数の双方向コネク
ションの経路を、その上りコネクションと下りコネクシ
ョンが同じ経路を通るように選択する経路選択装置であ
って、必要に応じて異なるパラメータを出力するパラメ
ータ出力手段と、このパラメータ出力手段で出力された
パラメータと、前記双方向コネクションの上りコネクシ
ョンの帯域と下りコネクションの帯域をもとに、前記双
方向コネクションの評価値を算出する評価値算出手段
と、この評価値算出手段で算出された評価値に基づく順
位に従い、前記複数の双方向コネクションの経路をそれ
ぞれ選択し、その選択結果を前記パラメータに対応する
経路選択結果として出力する出力手段と、この出力手段
で出力された複数の経路選択結果に基づき、前記複数の
双方向コネクションの最適経路を判断する判断手段とを
具備することにより、非対称双方向コネクションの経路
選択を行なう場合にも、双方向ペアをなす上りコネクシ
ョンと下りコネクションについて同一の経路を選択する
ことが可能となる。

【００３８】本発明の経路選択方法は、複数のノード装
置を接続してなる通信網に、複数のコネクションの経路
を選択する経路選択方法であって、前記複数のコネクシ
ョンのとり得る経路を探索し、この探索された経路上の
リンクに前記コネクションの帯域を予約して、その帯域
の予約状態をもとに、前記複数のコネクションのそれぞ
れに対し、前記探索された経路のうちの１つを選択する
ことにより、経路選択問題の精度の良い近似解を得るこ
とができる。

【００３９】また、本発明の経路選択装置は、複数のノ
ード装置を接続してなる通信網に、複数のコネクション
の経路を選択する経路選択装置であって、前記複数のコ
ネクションのとり得る経路を探索する経路探索手段と、
この経路探索手段で探索された経路上のリンクに前記コ
ネクションの帯域を予約する帯域予約手段と、この帯域
予約手段で前記リンクに予約された帯域の予約状態をも
とに、前記複数のコネクションのそれぞれに対し、前記
経路探索手段で探索された経路のうちの１つを選択する
経路選択手段とを具備することにより、経路選択問題の
精度の良い近似解を得ることができる。

【００４０】本発明の通信網設計方法は、少なくとも通
信網を構成するノードの数と、その各ノードの識別情
報、各ノード間に設定され得るリンクの種類とコストを
含むネットワーク情報と、少なくとも通信フローの発ノ
ードと着ノードの識別情報、その通信フローの量を含む
トラヒック情報をもとに、前記トラヒック情報にて要求
されるトラヒック需要を収容できる通信網を設計する通
信網設計方法であって、前記ネットワーク情報をもと
に、前記通信網の初期トポロジーを設定し、必要に応じ
て前記初期トポロジーを変更し、その設定された初期ト
ポロジー、あるいは、変更して得られたトポロジーに対
して、前記トラヒック情報をもとに、所望のフローの経
路を設定し、その設定された経路上のリンクのコストを
算出し、その算出されたコストが、あらかじめ定められ
た条件を満たすまで、前記設定された経路を変更しなが
ら、その変更された経路上のリンクのコストを算出し、
前記算出されたコストが、あらかじめ定められた条件を
満たすとき、少なくとも、そのときの前記所望のフロー
の経路、前記ノード間に設定されたリンクの種類を含む
通信網設計情報を出力することにより、網設計問題の精
度の良い近似解を与えることができる。

【００４１】また、本発明の通信網設計方法は、少なく
とも通信網を構成するノードの数と、その各ノードの識
別情報、各ノード間に設定可能なリンクの種類とコスト
を含むネットワーク情報と、少なくとも各コネクション
毎の要求帯域、発ノードと着ノードの識別情報を含むコ
ネクション情報をもとに、前記コネクションを収容でき
る通信網を設計する通信網設計方法であって、前記コネ
クション情報をもとに、発ノードと着ノードを同じくす
るコネクションの要求帯域をまとめることにより通信フ
ローを生成し、この生成された通信フローと前記ネット
ワーク情報をもとに、前記通信フローの経路と前記ノー
ド間のリンクを設定することにより仮想網設を設計し、
この設計された仮想網をもとに、前記コネクションの経
路を決定し、この決定されたコネクションの経路をもと
に前記ノード間に前記コネクションに対応するリンクを
設定することにより、網設計問題の精度の良い近似解を
与えることができる。

【００４２】また、本発明の通信網設計装置は、少なく
とも通信網を構成するノードの数と、その各ノードの識
別情報、各ノード間に設定され得るリンクの種類とコス
トを含むネットワーク情報と、少なくとも通信フローの
発ノードと着ノードの識別情報、その通信フローの量を
含むトラヒック情報をもとに、前記トラヒック情報にて
要求されるトラヒック需要を収容できる通信網を設計す
る通信網設計装置であって、前記ネットワーク情報をも
とに、前記通信網の初期トポロジーを設定する初期トポ
ロジー設定手段と、必要に応じて前記初期トポロジー設
定手段で設定された初期トポロジーを変更するトポロジ
ー変更手段と、前記初期トポロジー設定手段で設定され
た初期トポロジー、あるいは、前記トポロジー変更手段
で変更されたトポロジーに対して、前記トラヒック情報
をもとに、所望のフローの経路を設定する経路設定手段
と、この経路設定手段で設定された経路上のリンクのコ
ストを算出するコスト算出手段と、このコスト算出手段
で算出されたコストが、あらかじめ定められた条件を満
たすまで前記経路設定手段で設定された経路を変更し、
前記コスト算出手段に対し、その変更された経路上のリ
ンクのコストを算出するよう制御する制御手段と、前記
コスト算出手段で算出されたコストが、あらかじめ定め
られた条件を満たすとき、少なくとも、そのときの前記
所望のフローの経路、前記ノード間に設定されたリンク
の種類を含む通信網設計情報を出力する出力手段とを具
備することにより、網設計問題の精度の良い近似解を与
えることができる。

【００４３】また、本発明の通信網設計装置は、少なく
とも通信網を構成するノードの数と、その各ノードの識
別情報、各ノード間に設定可能なリンクの種類とコスト
を含むネットワーク情報と、少なくとも各コネクション
毎の要求帯域、発ノードと着ノードの識別情報を含むコ
ネクション情報をもとに、前記コネクションを収容でき
る通信網を設計する通信網設計装置であって、前記コネ
クション情報をもとに、発ノードと着ノードを同じくす
るコネクションの要求帯域をまとめることにより、通信
フローを生成するフロー生成手段と、このフロー生成手
段で生成された通信フローと前記ネットワーク情報をも
とに、前記通信フローの経路と前記ノード間のリンクを
設定することにより仮想網を設計する仮想通信網設計手
段と、この仮想網設計手段で設計された仮想網をもと
に、前記コネクションの経路を決定するコネクション経
路決定手段と、このコネクション経路決定手段で決定さ
れたコネクションの経路をもとにノード間に前記コネク
ションに対応するリンクを設定するリンク設定手段とを
具備することにより、網設計問題の精度の良い近似解を
与えることができる。

【００４４】

【発明の実施の形態】以下、本発明の実施形態につい
て、図面を参照して説明する。

【００４５】まず、第１の実施形態について説明する。
なお、以下の第１の実施形態の説明において、片方向コ
ネクションとは、その方向が逆方向で帯域が「０」のコ
ネクションと双方向ペアを成しているものと定義する。
これにより、片方向コネクションと双方向コネクション
が混在している場合でも、全て双方向コネクションとし
て扱うことができる。すなわち、片方向コネクションは
その方向が逆方向で帯域が「０」のコネクションと双方
向ペアを成しているものとみなすことにより、片方向コ
ネクションを双方向コネクションとして扱う。また、簡
単のため、双方向コネクションを単にコネクションと記
述し、双方向ペアを成す２本のコネクションを別々に表
す必要がある時は、上りコネクション、下りコネクショ
ンと記述する。

【００４６】図１は、第１の実施形態に係る経路選択装
置１の構成を概略的に示したものである。

【００４７】図１において、経路選択装置１は、評価値
算出部２と経路選択部３とから構成される。

【００４８】評価値算出部２には、所望のコネクション
について、経路を選択するために必要な情報、例えば、
帯域、発着ノードの識別情報等を含むコネクション情報
が入力され、あらかじめ定められた手順にて、そのコネ
クションについての評価値を算出するようになってい
る。

【００４９】経路選択部３には、あらかじめ経路選択対
象のネットワークに関する情報、例えば、そのネットワ
ークのトポロジー、各リンクの容量、コスト等を含むネ
ットワーク情報が入力されていて、この情報をもとに、
モデル化された経路選択対象のネットワークについて、
評価値算出部２で評価値が算出された各コネクションに
対する最適な経路を割り当てる処理を行うものである。

【００５０】図２は、評価値算出部２の構成を概略的に
示したもので、帯域比較部２ａ、重み和算出部２ｂ、第
１の重み記憶部２ｃ、第２の重み記憶部２ｄから構成さ
れる。

【００５１】帯域比較部２ａは、コネクション情報とし
て入力された上りコネクションの帯域Ｗ_up、と下りコネ
クションの帯域Ｗ_downを比較して、その比較結果を重み
和算出部２ｂに出力するようになっている。すなわち、
ｍａｘ（Ｗ_up、Ｗ_down）、ｍｉｎ（Ｗ_up、Ｗ_down）を求
める。ここで、関数ｍａｘ（ｘ、ｙ）は、ｘとｙのうち
小さくない方の値を返す関数であり、関数ｍｉｎ（ｘ、
ｙ）ｘとｙのうち大きくない方の値を返す関数である。

【００５２】重み和算出部２ｂは、コネクション毎に評
価値Ｅを式（３）から求めるようになっている。

【００５３】 Ｅ＝ａ₁ ・ｍａｘ（Ｗ_up、Ｗ_down）＋ａ₂ ・ｍｉｎ（Ｗ_up、Ｗ_down） … （３） ａ₁ 、ａ₂ は、重みと呼ばれ、それぞれ第１の重み記憶
手段２ｃ、第２の重み記憶手段２ｄにあらかじめ記憶さ
れている値である。

【００５４】重み和算出部２ｂで算出された評価値Ｅ
は、経路選択部３に出力される。

【００５５】図３は、経路選択部３の構成を概略的に示
すもので、評価値記憶部３ａ、コネクション選択部３
ｂ、最小コスト経路算出部３ｃから構成される。

【００５６】評価値記憶手段３ａでは、評価値算出部２
から出力された各コネクション毎に算出された評価値Ｅ
を一時記憶するものである。

【００５７】コネクション選択部３ｂは、評価値記憶部
３ａに一時記憶されている評価値をもとに、その値の大
きい順にコネクションを選択するもので、選択されたコ
ネクションは、最小コスト経路算出部３ｃに出力され
る。

【００５８】最小コスト経路算出部３ｃでは、コネクシ
ョン選択手段で選択されたコネクションに対し、そのコ
ネクションを収容できるだけの残余帯域を持つ経路の中
で最もコストの小さい経路を割り当てる処理を行う。そ
の後、再び、コネクション選択手部３ｂは、新たなコネ
クションを選択して、最小コスト経路算出部３ｃが経路
を割り当てる処理を行い、これを繰り返すことにより、
所望の全てのコネクションに対して、経路を割り当て
る。

【００５９】コネクション選択部３ｂにおける、コネク
ションの選択を効率的に行なうために、予め評価値をそ
の大きさによりソートを行ない、コネクションの順序付
けを行なってもよい。

【００６０】次に、図４、図５に示すフローチャートを
参照して、図１の経路選択装置１の動作処理について説
明する。なお、図４は、主に、評価値算出部２の動作を
処理を示し、図５は、経路選択部３の動作処理を示すも
のである。

【００６１】また、ここでは、図６に示したようなメッ
シュ型のトポロジーのネットワークを対象に、図７に示
した各コネクションの経路を選択する場合について説明
する。

【００６２】図６は、経路選択対象であるネットワーク
の構成を概略的に示したもので、このネットワークは、
ノードＡ、Ｂ、Ｃ、Ｄ、Ｅを収容し、各ノード間は論理
的な伝送路、すなわち、リンク（図６の矢印で示したも
の）で接続されている。図６では、ノード間に互いに逆
向きのリンクを記述しているが、物理的に２本の伝送路
である必要はない。例えば、無線伝送路であってもよい
し、時分割により伝送方向を変えるピンポン伝送を行な
う時のように1 本の伝送路であってもよい。

【００６３】ノードＸ（Ｘ＝Ａ〜Ｅ）からノードＹ（Ｙ
＝Ａ〜Ｅ）へのリンクをリンクＸＹと記述し、リンクＸ
Ｙには、容量Ｑ（ＸＹ）とリンクコストＣ（ＸＹ）が定
義されているものとする。

【００６４】また、リンクＸＹを通過するコネクション
の帯域の合計がＱ（ＸＹ）を越えることはできないもの
とする。さらに、発ノードがＸで着ノードがＺ（Ｚ＝Ａ
〜Ｅ）である双方向コネクションｉに例えば、経路Ｘ→
Ｙ→Ｚ（これを経路ＸＹＺと記述する）を割り当てた場
合に必要となるコストはＤ_i （ＸＹＺ）は、式（４）で
定義できる。

【００６５】 Ｄ_i （ＸＹＺ）＝｛Ｃ（ＸＹ）＋Ｃ（ＹＺ）｝Ｗ_down＋ ｛Ｃ（ＺＹ）＋Ｃ（ＹＸ）｝Ｗ_up … （４） 但し、Ｗ_downはノードＸからノードＺへ向かう下りコネ
クションの帯域とし、Ｗ_upはノードＺからノードＸへ向
かう上りコネクションの帯域である。

【００６６】また、コストＤ_i （ＸＹＺ）は、コネクシ
ョンの帯域Ｗ_down、Ｗ_upを用いずに式（５）でも定義で
きる。

【００６７】 Ｄ_i （ＸＹＺ）＝｛Ｃ（ＸＹ）＋Ｃ（ＹＺ）｝＋ ｛Ｃ（ＺＹ）＋Ｃ（ＹＸ）｝ … （５） ここでの説明では、コストＤの計算に式（５）を用いる
ことにする。また、説明を簡単にするために、全てのリ
ンクに対してその容量を１５０［Ｍｂｐｓ］とし，その
リンクコストを「1 」とする。もちろん容量とリンクコ
ストはリンク毎に異なる値をとっても構わない。また、
リンクコストがリンクの残容量によって変化しても構わ
ない。

【００６８】図７では、発ノードから着ノードへのコネ
クションの帯域を下り帯域、着ノードから発ノードへの
コネクションの帯域を上り帯域として記述している。

【００６９】第１の重み記憶部２ｃ、第２の重み記憶部
２ｄのそれぞれに記憶されている重みａ₁ 、ａ₂ の値を
それぞれ「１」「０」として、図７に示したようなコネ
クション（コネクション番号ｉ＝１〜５）の経路選択の
処理過程を、以下、図４、図５を参照して具体的に追っ
ていく。

【００７０】まず、評価値算出部２にコネクション情報
として、例えば、コネクション番号、発ノード、着ノー
ド、下り帯域、上り帯域が入力されると、順次、コネク
ションを選択していき（図４のステップＳ２）、帯域比
較部２ａで上り帯域と下り帯域を比較する（ステップＳ
３）。

【００７１】その比較結果が上り帯域Ｗ_upが下り帯域Ｗ
_down以上のとき、ステップＳ４に進み、そうでないと
き、ステップＳ５に進み、重み和算出部２ｂで評価値Ｅ
を算出する。すなわち、上り帯域Ｗ_upが下り帯域Ｗ_down
以上のとき、式（３）は、 Ｅ＝ａ₁ ・Ｗ_up＋ａ₂ ・Ｗ_down … （６） となり、また、下り帯域の方が大きいとき式（３）は、 Ｅ＝ａ₁ ・Ｗ_down＋ａ₂ ・Ｗ_up … （７） となり、ステップＳ４では、式（６）を用いて評価値Ｅ
を算出し、ステップＳ５では、式（７）を用いて評価値
Ｅを算出する。

【００７２】たとえば、コネクション1 の場合、下り帯
域の方が上り帯域より大きいのでステップＳ５に進み、
式（７）から、その評価値Ｅは１５０と算出され、コネ
クション２の場合もステップＳ５に進み、同じようにし
て評価値Ｅは１５０と算出さ、コネクション３の場合
は、ステップＳ４に進み、その評価値Ｅは１４０と算出
される。コネクション４の場合は、上り帯域の方が下り
帯域より大きいのでステップＳ４に進み、式（６）から
評価値Ｅは１３０と算出される。コネクション５の場合
は、例えばステップＳ４に進み、評価値は１０と算出さ
れる。コネクション３と５に関しては、上り帯域と下り
帯域の大きさが等しいため、上り帯域と下り帯域に重み
の差を設ける必要はなく、従って、ステップＳ４、ステ
ップＳ５のいずれであっても同じ値の評価値を算出す
る。

【００７３】このようにして算出されたコネクションｉ
（ｉ＝１〜５）の評価値をＥｉと表現すると、Ｅ１＝１
５０、Ｅ２＝１５０、Ｅ３＝１４０、Ｅ４＝１３０、Ｅ
５＝１０となる。

【００７４】全てのコネクションについて評価値が算出
されると（ステップＳ１）、経路選択部３の評価値記憶
部３ａには、全てのコネクションの評価値が一時記憶さ
れるている。

【００７５】経路選択手段３では、ｉを「１」から順次
「１」づつインクリメントしながら評価値が最も大きい
ものから順にコネクションｉを選択して、そのコネクシ
ョンを収容できるだけの残余帯域を持つ経路の中で最も
コストの小さい経路を割り当てる処理を行う。ここで
は、各リンクコストは全て「１」であるので、最もコス
トの小さい経路を選択するには、リンク数が最も少ない
経路を選択すればよい。

【００７６】まず、コネクション選択部３ｂにおいて、
評価値記憶手段３ａに記憶された評価値のうち、最も大
きい（ｉ＝１）値の評価値をもつコネクション1 を選び
（ステップＳ５〜ステップＳ７）、ステップＳ８では、
そのコネクション１を収容できるだけの残余帯域を持つ
経路の中で最もコストの小さい経路、すなわち、この場
合、図６の経路ＡＢがコネクション１の経路として割り
当てられる（ステップＳ８〜ステップＳ１０）。

【００７７】次に、ｉが「１」インクリメントされて
（ステップＳ１１）、評価値記憶手段３ａに記憶された
評価値のうち、２番目に大きい（ｉ＝２）値の評価値を
もつコネクション２を選び（ステップＳ５〜ステップＳ
７）、ステップＳ８では、そのコネクション２を収容で
きるだけの残余帯域を持つ経路の中で最もコストの小さ
い経路をサーチする（ステップＳ８）。このとき、リン
クＡＢは、コネクション２の上りコネクションを収容す
るだけの残余帯域を持たないため、コネクション２に
は、経路ＡＣＢなる経路が選択されて、割り当てられる
（ステップＳ９〜ステップＳ１０）。

【００７８】次に、ｉが「１」インクリメントされて
（ステップＳ１１）、評価値記憶手段３ａに記憶された
評価値のうち、３番目に大きい（ｉ＝３）値の評価値を
もつコネクション３を選び（ステップＳ５〜ステップＳ
７）、ステップＳ８では、そのコネクション３を収容で
きるだけの残余帯域を持つ経路の中で最もコストの小さ
い経路をサーチする（ステップＳ８）。このとき、リン
クＡＣは、コネクション３のコネクションを収容するだ
けの残余帯域を持たないため、コネクション３の下りコ
ネクションには、それ以外の経路で最もコストの小さい
経路ＡＥＤＣなる経路が選択されて、割り当てられる
（ステップＳ９〜ステップＳ１０）。

【００７９】次に、ｉが「１」インクリメントされて
（ステップＳ１１）、評価値記憶手段３ａに記憶された
評価値のうち、４番目に大きい（ｉ＝４）値の評価値を
もつコネクション４を選び（ステップＳ５〜ステップＳ
７）、ステップＳ８では、そのコネクション４を収容で
きるだけの残余帯域を持つ経路の中で最もコストの小さ
い経路をサーチする（ステップＳ８）。このとき、リン
クＣＤは、すでに、コネクション３が割り当てられてい
て、コネクション４を収容するだけの残余帯域を持たな
いため、コネクション４には、リンクＣＤを使用してい
ない経路の中で最もコストの小さい経路が選択されるわ
けだが、この場合、コネクション４を収容するための帯
域をもつ経路が存在しいなので、割り当てることができ
ない（ステップＳ９）。

【００８０】次に、ｉが「１」インクリメントされて
（ステップＳ１１）、評価値記憶手段３ａに記憶された
評価値のうち、５番目に大きい（ｉ＝５）値の評価値を
もつコネクション５を選び（ステップＳ５〜ステップＳ
７）、ステップＳ８では、そのコネクション５を収容で
きるだけの残余帯域を持つ経路の中で最もコストの小さ
い経路をサーチする（ステップＳ８）。このとき、経路
ＣＤには、すでに、コネクション３が割り当てられてい
るものの、コネクション５を収容する残余帯域があるた
め、コネクション５には、経路ＣＤが経路として割り当
てられる（ステップＳ９〜ステップＳ１０）。

【００８１】次にｉが「１」インクリメントされると
（ステップＳ１１）、その値は、あらかじめ与えられた
コネクション数（ｉ＝５）より大きいので、ここで処理
が終了し、各コネクション毎に割り当てられた経路を出
力する（ステップＳ６、ステップＳ１２）。

【００８２】ここでは、コネクション選択部３ｂにおい
て、評価値の等しいコネクション１と２に対してはコネ
クション番号の小さい順に選択されて、経路選択を行な
ったが、発ノード番号、着ノード番号、コネクションの
優先度等の情報を用いてコネクションの経路選択のため
の順序を決定しても良い。

【００８３】さて、ここで、重みａ₁ 、ａ₂ の値とし
て、それぞれ「０．５」、「０．５」を用いた場合につ
いて考える。前述のように（図４のフローチャートに従
って）、図７のコネクション１〜５について評価値を算
出すると、Ｅ１＝８０、Ｅ２＝７５、Ｅ３＝１４０、Ｅ
４＝７５、Ｅ５＝１０となる。この場合、図５のフロー
チャートに示したステップＳ７で、コネクション選択部
３ｂで選択される順序は、コネクション３、１、２、
４、５の順となる。

【００８４】そして、図５のフローチャートに従って処
理を行うと、コネクション３には経路ＡＣ、コネクショ
ン１には経路ＡＢを、コネクション２には経路ＡＥＤ
Ｂ、コネクション４には経路ＣＤ、コネクション５には
経路ＣＤが、それぞれのコネクションに対する経路とし
て割り当てられることになる。

【００８５】次に、重みａ₁ 、ａ₂ の値として、それぞ
れ「０」、「１」を用いた場合について考える。前述の
ように（図４のフローチャートに従って）、図７のコネ
クション１〜５について評価値を算出すると、Ｅ１＝１
０、Ｅ２＝０、Ｅ３＝１４０、Ｅ４＝２０、Ｅ５＝１０
となる。この場合、図５のフローチャートに示したステ
ップＳ７で、コネクション選択部３ｂで選択される順序
は、コネクション３、４、１、５、２の順となる。

【００８６】そして、図５のフローチャートに従って処
理を行うと、コネクション３には経路ＡＣ、コネクショ
ン４には経路ＣＤを、コネクション１には経路ＡＢ、コ
ネクション５には経路ＣＤ、コネクション２には経路Ａ
ＥＤＢが、それぞれのコネクションに対する経路として
割り当てられることになる。

【００８７】このように、重みａ₁ 、ａ₂ の値によって
は、与えられた全てのコネクション１〜５に対して、よ
りコストの小さい最適な経路が効率よく割り当てられる
ことがわかる。

【００８８】次に、第２の実施形態について説明する。

【００８９】図８は、第２の実施形態に係る経路選択装
置５の構成を概略的に示したものである。図８におい
て、経路選択装置５は、パラメータ変更部６、評価値算
出部７、経路選択部８、最良結果記憶部９とから構成さ
れる。

【００９０】パラメータ変更部６は、所望のコネクショ
ンに対する最適な経路を選択する処理に必要な各種パラ
メータの値をあらかじめ保持し、あるいは、あらかじめ
定められたアルゴリズムにてその値を変更して、各種パ
ラメータ毎にそのパラメータの複数の値を管理し、必要
に応じて評価値算出部７に出力するものである。パラメ
ータとしては、例えば、重みａ₁ 、ａ₂ がある。

【００９１】評価値算出部７は、所望のコネクションに
ついて、経路を選択するために必要な情報、例えば、帯
域、着ノードの識別情報等を含むコネクション情報が入
力され、あらかじめ定められた手順にて、そのコネクシ
ョンについての評価値を算出するようになっている。

【００９２】経路選択部８は、あらかじめ経路選択対象
のネットワークに関する情報、例えば、そのネットワー
クのトポロジー、各リンクの容量、コスト等を含むネッ
トワーク情報が入力されていて、この情報をもとに、モ
デル化された経路選択対象のネットワークについて、評
価値算出部２で評価値が算出された各コネクションに対
する最適な経路を割り当てる処理を行うものである。経
路選択部８の具体的な構成例は、第１の実施形態におけ
る経路選択部３と同様である（図３参照）。

【００９３】パラメータの値を変更しながら評価値算出
部７、経路選択部９で所定の処理を行って得られる経路
選択結果が、前回までの経路選択処理で得られた経路選
択結果にうち最適な経路選択結果と比較されて、最良結
果記憶部９には、より最適な経路選択結果のみが記憶さ
れるようになっている。

【００９４】図９は、評価値算出部７の構成を概略的に
示したもので、帯域比較部７ａ、重み和算出部７ｂ、第
１の重み算出部７ｃ、第２の重み算出部７ｄから構成さ
れる。

【００９５】帯域比較部７ａの動作は、第１の実施形態
における帯域比較部２ａの動作処理と同様である。

【００９６】重み和算出部２ｂで評価値を算出する際に
必要な各種パラメータは、パラメータ変更部６から必要
に応じて出力されて、それらは、所定の記憶部に記憶さ
れる。例えば、重みａ₁ 、ａ₂ は、それぞれ、第１の重
み算出部７ｃ、第２の重み算出部７ｄに記憶される。

【００９７】これらのパラメータ変更部６から出力され
たパラメータ値をもとに重み和算出部７ｂでは、各コネ
クション毎に評価値を算出する。その詳細は、第１の実
施形態における重み和算出部２ｂの処理動作と同様であ
る。

【００９８】次に、図１０に示すフローチャートを参照
して、図８の経路選択装置５の動作処理について説明す
る。なお、ここでは、第１の実施形態と異なる部分を主
に説明する。

【００９９】まず、パラメータ変更部６は、パラメータ
として、重みａ₁ 、ａ₂ の値の初期値を評価値算出部７
に出力する（ステップＳ２０）。

【０１００】評価値算出部７では、そのパラメータ値か
ら与えられた各コネクションに対して評価値の計算を行
なう。その詳細は、第１の実施形態における評価値算出
部２の動作処理と同様である（ステップＳ２１）。

【０１０１】次に、経路選択部８で、評価値の値が最も
大きいものから順にコネクションを選択しながら、経路
選択の処理を行なう。その詳細は、第１の実施形態にお
ける経路選択部３の動作処理と同様である（ステップＳ
２２）。この最初の経路処理終了の段階では、最良結果
記憶部９には、まだ各コネクションについての他の経路
選択結果は記憶されていないため、ステップＳ２３から
直ちにステップＳ２５に進み、経路選択結果を最良結果
記憶部９に記憶する。

【０１０２】パラメータ変更部６は、次に用いるべきパ
ラメータ値を判断し、それを評価値算出部７に出力する
（ステップＳ２６〜ステップＳ２７）。

【０１０３】評価値算出部７は、新たなパラメータを用
いて、前回と同一のコネクションに対し再度評価値を計
算し直し、経路選択部８で、その評価値の値が最も大き
いものから順にコネクションを選択しながら、経路選択
の処理を行なう（ステップＳ２１〜ステップＳ２２）。

【０１０４】次に、この経路選択結果と最良結果記憶部
９にすでに記憶されている各コネクション毎の経路選択
結果とを比較し、今回の経路選択結果の方が最良結果記
憶部９に記憶されている経路選択結果より望ましい結果
であるときに、最良結果記憶部９の記憶内容を更新する
（ステップＳ２３〜ステップＳ２５）。

【０１０５】これを繰り返すことにより、最終的に最良
結果記憶部９に記憶されている経路選択結果を出力する
ことにより（ステップＳ２８）、パラメータ値、すなわ
ち、重みａ₁ 、ａ₂ の値を一つ用いる場合よりも、良い
結果を得ることができる。

【０１０６】図１０のステップＳ２４で、新たに得られ
た経路選択結果と最良結果記憶部９に記憶されている内
容を比較して、どちらがより望ましいかを判定するため
に、経路評価関数を用いる。

【０１０７】経路評価関数は、（ａ）経路を割り当てる
ことのできなかったコネクションの数、（ｂ）リンクの
使用率の最大値、（ｃ）リンクの使用量とリンクのコス
トの積を全てのリンクについて足し合わせたもの、等を
考慮し、これらの各値が小さい経路選択結果ほど望まし
い結果、すなわち、最適な結果であるとするものであ
る。

【０１０８】また、最良結果記憶部９は、記憶すべき結
果として経路選択結果そのものを記憶しておいてもよい
が、記憶容量に制限がある場合には、最良結果を与える
パラメータ（ここでは、例えば、重みａ₁ 、ａ₂ の値）
を記憶しておき、最終的な経路選択結果を出力する時
に、その最良結果記憶部９が記憶するパラメータを用い
て経路選択処理を行ない、この結果を出力するようにし
てもよい。

【０１０９】具体例として、図６に示したネットワーク
において、図７に示した各コネクションの経路選択を図
１０のフローチャートに従って行ってみる。ここでは、
第１の重みの値ａ₁ をパラメータとし、第２の重みの値
ａ₂ をａ₂ ＝１−ａ₁ とし、コネクションの評価値Ｅを
式（３）から求めることにする。さらに、経路評価関数
として、経路を割り当てることのできなかったコネクシ
ョンの数を基準にするものを用いる。パラメータの値ａ
₁ は「１」、「０．５」、「０」を用いることにする。

【０１１０】まず、パラメータ変更部６は、パラメータ
としての重みａ₁ の値「１」を評価値算出部７に出力す
る（ステップＳ２０）。このとき、第２の重みａ₂ の値
は「０」となり、その場合に経路選択処理を行なうと、
前述同様に、コネクション４に経路を割り当てることが
できなくなり、経路評価関数は「１」となる（ステップ
Ｓ２１〜ステップＳ２２）。

【０１１１】最良結果記憶部９には、まだ何も記憶され
ていないので、この経路選択結果を記憶する（ステップ
Ｓ２３〜ステップＳ２５）。

【０１１２】次に、パラメータ変更部６は、パラメータ
としての重みａ₁ の値「０．５」を評価値算出部７に出
力する（ステップＳ２０）。このとき、第２の重みａ₂
の値は「０．５」となり、その場合に経路選択を行なう
と、前述同様に、全てのコネクションに経路を割り当て
ることができ、経路評価関数は「０」となる（ステップ
Ｓ２１〜ステップＳ２２）。そのとき最良結果記憶部９
に記憶されている経路選択結果よりも新たな経路選択結
果の方が望ましいため、最良結果記憶部９の内容を更新
する（ステップＳ２３〜ステップＳ２５）。

【０１１３】さらに、パラメータ変更部６は、パラメー
タとしての重みａ₁ の値「０」を評価値算出部７に出力
する（ステップＳ２０）。このとき、第２の重みａ₂ の
値は「１」となり、その場合に経路選択を行なうと、前
述同様に、全てのコネクションに経路を割り当てること
ができ、経路評価関数は「０」となる（ステップＳ２１
〜ステップＳ２２）。この場合、最良結果記憶部９に記
憶されている結果と同じ経路選択結果が得られてので、
最良結果記憶部９の更新は行なわない（ステップＳ２３
〜ステップＳ２５）。

【０１１４】以上の処理により最終的に出力される経路
選択結果は、ａ₁ ＝０．５、ａ₂ ＝０．５の場合の経路
選択結果である（ステップＳ２８）。

【０１１５】評価値算出部７は、上記説明では、パラメ
ータとして重みａ₁ 、ａ₂ の値をパラメータ変更部６か
ら受け取って、式（３）から評価値を算出するとした
が、この場合に限らず、パラメータ変更部６から乱数の
種を受け取り、コネクションの評価値として乱数値を用
いることも考えられる。

【０１１６】また、パラメータとして乱数の最大値と乱
数の種を受け取り、コネクションの評価値として乱数値
を用いてもよい。

【０１１７】さらに、パラメータとして第１の重みの値
ａ₁ と第２の重みの値ａ₂ の値と乱数の種を受けとり、
コネクションの評価値Ｅを Ｅ＝ａ₁ ・ｍａｘ（Ｗ_up、Ｗ_down）＋ａ₂ ・ｍｉｎ（Ｗ_up、Ｗ_down）＋ｒ … （８） から求めるようにしてもよい。

【０１１８】ただし、ｒは乱数の種より生成される乱数
の値である。この場合、乱数値ｒは十分小さいことが望
ましい。

【０１１９】このようにコネクションの評価値を計算す
る際にコネクションの帯域だけではなく乱数値を用いる
ことにより、次の２つの効果がある。

【０１２０】第１の効果は、帯域を同じくするコネクシ
ョンに異なる評価値を与えられることである。例えば、
図６に示したようなネットワークに、図１１に示すよう
な各コネクションの経路を選択する場合を例にとり説明
する。

【０１２１】乱数値ｒを用いずに図１１に示したコネク
ションの評価値を式（３）から求めると、全てのコネク
ションに同じ評価値が求められる。そのため、経路選択
部８では、例えば、コネクション番号の小さい順に経路
選択処理を施す。

【０１２２】この場合、図１１のコネクション１〜３に
図６の経路ＢＡＥを経路として割り当て、コネクション
４〜６に経路ＡＣＤＥを経路として割り当てることとな
り、コスト高な経路選択結果となってしまう。

【０１２３】乱数値ｒを用いて式（８）から各コネクシ
ョンの評価値を求めると、コネクション４〜６がコネク
ション１〜３よりも大きな評価値を得る可能性が生じ、
そのためコネクション４〜６をコネクション１〜３より
も先に設定する可能性が生じる。それにより、より良い
経路選択結果が得られる。

【０１２４】乱数値ｒを用いることにより得られる第２
の効果は、複数のパラメータの値を用いて経路選択を行
ない最も良い経路選択結果を最終結果とする時、帯域を
同じくするコネクションが多数存在する場合に乱数値ｒ
を用いないと、各パラメータの値に対して同じ経路選択
結果が得られる可能性が高い。それに対して、乱数値ｒ
を用いると、各パラメータの値に対して異なる経路選択
結果を得ることができ、より良い最終結果が得られる。

【０１２５】このように、乱数値ｒを用いることにより
経路選択性能の向上が期待できる。

【０１２６】また、乱数値ｒは帯域を同じくする経路選
択対象のコネクションが多数存在する場合に効果を表す
が、そうでない場合に帯域を用いた評価値計算に乱数値
ｒが大きな影響を与えないようにするため、乱数値ｒは
小さな値に設定することが望ましい。

【０１２７】以上、説明したように、上記第１〜第２の
実施形態によれば、双方向コネクションに評価値と呼ぶ
数値を求め、この数値を用いて、双方向コネクションの
経路選択を行うことができるので、同じ双方向コネクシ
ョンに属する上りコネクションと下りコネクションが同
じ経路を通るという条件のもとに最適な経路選択を効率
的に行える。

【０１２８】また、上記第１の実施形態によれば、経路
選択装置１の評価値算出部２は、各双方向コネクション
に対してその双方向ペアをなす上りコネクションの帯域
と下りコネクションの帯域を用いて一つの評価値を算出
し、経路選択部３は、この評価値を基に双方向ペアをな
す上りコネクションと下りコネクションがあたかも1本
のコネクションであるかのように経路を決定するため、
双方向ペアをなす上りコネクションと下りコネクション
に同じ経路を割り当てることができる。

【０１２９】また、評価値算出部２は、各双方向コネク
ションに対してその双方向ペアをなす上りコネクション
の帯域と下りコネクションの帯域の大小比較を行ない、
大きいと判断された帯域の値に第１の重みを乗算したも
のと、小さいと判断された帯域の値に第２の重みを乗算
したものとを加算することによりスカラー量の評価値を
求め、経路選択部３では、その評価値の大きい順で双方
向コネクションの経路決定を行なう順序を決定するが、
その際、評価値がスカラー量であるため、簡単に評価値
の大小比較を行なうことができる。

【０１３０】さらに、経路選択部３は評価値の大きい順
に双方向コネクションの経路をその最短経路（すなわ
ち、最小コストの経路）で決定していけばよいため、高
速に処理を行なうことができる。

【０１３１】また、上記第２の実施形態によれば、経路
選択装置５のパラメータ変更部６にパラメータの値を複
数用意しておき、各パラメータの値に対して、評価値算
出部７で各双方向コネクションの評価値を算出し、この
評価値を基に経路選択部８で経路の決定を行ない、複数
のパラメータの値を用いて経路選択を繰り返し行なった
結果、最良のものを見つけて最良結果記憶部９に、その
最良の結果を与えるパラメータの値を記憶しておくこと
により、例えば、第１の実施形態のように、１つのパラ
メータの値を用いる場合よりも、より適した経路の選択
結果が得られる。

【０１３２】もちろん、最良結果記憶部９は、最良結果
を与えるパラメータの値を記憶するのではなく、最良結
果を与えるパラメータの値を用いて経路選択を行なった
場合の各双方向コネクションの経路を記憶するようにし
てもよい。

【０１３３】次に、第３の実施形態について説明する。
ここでは、片方向コネクションに対して経路選択を行う
場合について説明する。

【０１３４】図１２は、第３の実施形態に係る経路選択
装置１００の構成を示したものである。経路選択装置１
００は、経路探索部１０１、帯域予約部１０２、経路決
定部１０３から構成されている。

【０１３５】経路探索部１０１には、ネットワークトポ
ロジー、リンク容量等の経路の選択対象としてのネット
ワークをモデル化するに足りる情報を含むネットワーク
情報と、各コネクションの発着ノード、帯域、許容最大
ホップ数、経路の好悪等の情報を含むコネクション情報
が入力されて、対象となるネットワークに各コネクショ
ンに対して、その要求に適合する経路を全て求め、経路
情報として帯域予約部１０２に出力するようになってい
る。

【０１３６】例えば、経路探索部１０１は、コネクショ
ンの帯域がリンク容量よりも大きい場合には、そのリン
クを通る経路は無視する。また、コネクションが情報伝
送にかかる遅延に要求値を持つ場合には、要求遅延量よ
りも遅延が大きくなるような経路は無視する。このよう
にして、各コネクションに対して割り当てるべきでない
あるいは割り当てる可能性のない経路を、経路探索部１
０１が無視することにより、以後の処理に必要な計算量
を小さくすることができる。

【０１３７】帯域予約部１０２は、経路探索部１０１に
より得られた経路情報を用いて、各コネクションに対し
て、その通り得る経路上のリンクにそのコネクションの
帯域を予約していく。あるコネクションのとり得る経路
の中で２つ以上の経路が同じリンクを共有する場合、一
度帯域を予約したリンクにはそれ以上の予約を禁止して
も良いが、何度も同じコネクションの帯域の予約を繰り
返しても良い。

【０１３８】図１３を参照して、帯域予約部１０２の帯
域予約方法について説明する。図１３では、ノード装置
Ａ〜Ｅと、そのノード間を伝送路としてのリンク１〜５
により接続して構成されるネットワークを示している。
ノードＡからノードＢにはリンク１が設けられ、ノード
ＢからノードＣにはリンク２が設けられ、ノードＣから
ノードＤにはリンク３が設けられ、ノードＢからノード
Ｅにはリンク４が設けられ、ノードＥからノードＤには
リンク５が設けられている。

【０１３９】例えば、図１３のネットワークに発ノード
Ａで着ノードがＤのコネクションを１本張る場合を考え
る。このコネクションのとり得る経路として、経路Ａ→
Ｂ→Ｃ→Ｄと経路Ａ→Ｂ→Ｅ→Ｄの２つの経路があり、
リンク１は２つの経路に共有されている。このとき、帯
域予約部１０２は、リンク１に、２重にコネクションの
帯域を予約してもよいが、一度帯域を予約すると以後の
予約を禁止してコネクション１本分の帯域を予約しても
よい。

【０１４０】経路決定部１０３は、帯域予約部１０２で
得られた帯域予約情報を用いて、各コネクションの経路
を決定して、その結果（経路選択結果）を出力するよう
になっている。

【０１４１】図１４は、第３の実施形態に係る経路選択
装置１００の経路決定部１０３の構成例を示したもので
ある。経路決定部１０３は、第１の溢れ帯域算出部１１
０、評価値算出部１１１、経路選択部１１２から構成さ
れている。

【０１４２】第一の溢れ帯域算出部１１０は、帯域予約
部１０２から出力された帯域予約情報と、リンク容量等
のネットワーク情報を用いて各リンクから予約帯域が溢
れる量である第１の溢れ帯域を求めるようになってい
る。

【０１４３】評価値算出部１１１は、第１の溢れ帯域算
出部１１０で求められた第１の溢れ帯域と、ネットワー
クトポロジー、リンク容量等のネットワーク情報と、各
コネクションの発着ノード・帯域・許容最大ホップ数・
経路の好悪等のコネクション情報を用いて各コネクショ
ンを設定する経路に対する評価値を求めるようになって
いる。

【０１４４】例えば、評価値算出部１１１は、各リンク
の第１の溢れ帯域の量と各リンク毎に定義された定数を
掛け合わせることにより各リンクのコストを定義し、経
路のコストを経路上のリンクコストの和として計算し、
コネクションが要求する遅延量と経路が保証する遅延量
との差を経路のコストで割ることにより、評価値を求め
る。つまり、コネクションｋを経路ｌに設定する評価値
をＶ_klとすると、Ｖ_klは次のように求める。

【０１４５】

【数３】 経路選択部１１２は、評価値Ｖ_klの大きい順にａ（＞
１）本のコネクションに経路を割り当てる。つまり、経
路選択部１１２は、式（９）を最大にするコネクション
をｍ、経路をｉとすると、コネクションｍに経路ｉを割
り当て、次にコネクションｍを除いて式（９）を最大に
するコネクションｍ′と経路ｉ′を求め、コネクション
ｍ′に経路ｉ′を割り当てる。ａ本のコネクションに経
路を割り当てたら、設定されたコネクションの予約帯域
をその経路上にないリンクから取り除き、第１の溢れ帯
域の値を再計算する。全てのコネクションの経路を、同
様の操作を繰り返すことにより決定する。

【０１４６】また、経路選択部１１２は、帯域の大きい
順にａ（＞１）本のコネクションを選び、各コネクショ
ンに対して最大の評価値を持つ経路を割り当ててもよ
い。また、経路選択部１１２は、予め与えられる優先度
の大きい順にａ（＞１）本のコネクションを選び、各コ
ネクションに対して最大の評価値を持つ経路を選択して
もよい。また、評価値算出部１１１は、第１の溢れ帯域
の値が「０」となったリンクには、第１の溢れ帯域の値
の代わりに予め与えられた定数を用いてコストを計算し
てもよい。

【０１４７】この第３の実施形態では、評価値を求め評
価値の大きい順にコネクションの経路を決定している
が、評価値の代わりにコストを求めコストの小さい順に
コネクションの経路を決定することも可能である。

【０１４８】図１５は、第３の実施形態に係る経路選択
装置１００の動作処理を説明するためのフローチャート
である。

【０１４９】図１５において、まず、経路探索部１０１
は、各コネクションの取り得る経路を全てサーチし（ス
テップＳ５０）、経路情報として帯域予約部１０２に出
力する。帯域予約部１０２は、各コネクションの帯域を
そのとり得る経路上のリンクに予約し（ステップＳ５
１）、第１の溢れ帯域算出部１１０は、帯域予約部１０
２から出力された帯域予約情報と、リンク容量等のネッ
トワーク情報を用いて各リンクから予約帯域が溢れる量
である第１の溢れ帯域を求め（ステップＳ５２）、評価
値算出手段１１１は、第１の溢れ帯域算出部１１０で求
められた第１の溢れ帯域等をもとに、式（９）から評価
値を算出し（ステップＳ５３）、経路選択部１１２は、
評価値Ｖ_klの大きい順にａ（＞１）本のコネクションに
経路を割り当てる（ステップＳ５４）。経路が未決定の
コネクションが存在したら（ステップＳ５５）、設定さ
れたコネクションの予約帯域をその経路上にないリンク
から取り除き、第１の溢れ帯域の値を再計算する（ステ
ップＳ５６）。

【０１５０】図１６に示すようなネットワークついて、
図１７に示す各コネクションの経路を選択する場合を例
にとり、図１５のフローチャートに示した経路選択処理
について具体的に説明する。

【０１５１】図１６には、ノード装置Ａ〜Ｅと、そのノ
ード間を伝送路としてのリンク１〜５により接続して構
成されるネットワークを示している。ノードＡからノー
ドＢにはリンク１が設けられ、ノードＢからノードＣに
はリンク２が設けられ、ノードＡからノードＤにはリン
ク３が設けられ、ノードＤからノードＣにはリンク４が
設けられ、ノードＤからノードＥにはリンク５が設けら
れている。

【０１５２】説明を簡単にするため、リンクのコストを
第１の溢れ帯域の量で定義し、コネクションの遅延に関
する要求を考慮に入れないこととする。また、評価値の
大きい順にコネクションとその経路を選ぶ代わりに、コ
ストの小さい順にコネクションとその経路を選択する。
また、各リンクの容量は全て１５０Ｍｂｐｓとする。

【０１５３】まず、図１７に示した各コネクションｉ
（ｉ＝１〜４）のとり得る経路を求める（ステップＳ５
０）。発ノードがＡで着ノードがＣであるコネクション
１と２がとり得る経路は経路Ａ→Ｂ→Ｃと経路Ａ→Ｄ→
Ｃであり、発ノードがＡで着ノードがＥであるコネクシ
ョン３がとり得る経路は経路Ａ→Ｄ→Ｅであり、発ノー
ドがＤで着ノードがＥのコネクション４がとり得る経路
は経路Ｄ→Ｅである。

【０１５４】次に、コネクションの帯域を各リンクに予
約していく（ステップＳ５１）。その結果としての帯域
の予約状況を図１８に示す。すなわち、図１７のコネク
ション１については、そのとり得る経路は経路ＡＢＣと
経路ＡＤＣであるので、リンク１〜４にそれぞれ１０Ｍ
ｂｐｓが予約される。図１７のコネクション１について
は、そのとり得る経路は経路ＡＢＣと経路ＡＤＣである
ので、リンク１〜４にそれぞれ１０Ｍｂｐｓが予約され
る。図１７のコネクション３については、そのとり得る
経路は経路ＡＤＥであるので、リンク３とリンク５にそ
れぞれ１４５Ｍｂｐｓが予約される。図１７のコネクシ
ョン４については、そのとり得る経路は経路ＤＥである
ので、リンク５に５Ｍｂｐｓが予約される。

【０１５５】次に、各リンクにおける第１の溢れ帯域を
計算する（ステップＳ５２）。図１８に示した各リンク
における予約状況から、リンク１〜５には、それぞれ、
２０Ｍｂｐｓ、２０Ｍｂｐｓ、１６５Ｍｂｐｓ、２０Ｍ
ｂｐｓ、１５０Ｍｂｐｓの帯域が予約されていることが
分かる。さて、ここで、リンクｍ（ｍ＝１〜５）の溢れ
帯域の量をξ_m で示し、第１の溢れベクトルＯ＝
｛ξ₁ ，ξ₂ ，…，ξ₅ ｝を定義すると、各リンクの容
量が１５０Ｍｂｐｓであることから、図１８より明らか
なように、Ｏ＝｛０，０，１５，０，０｝となる。すな
わち、この例では、予約帯域の合計値からリンク容量を
引いた値を溢れ帯域としている。

【０１５６】しかし、実際にリンク３に収容することの
できる予約帯域の組合せは｛コネクション１、コネクシ
ョン２｝または｛コネクション３｝である。そのため、
リンクに収容できない帯域の和という意味において第１
の溢れ帯域を１４５Ｍｂｐｓあるいは２０Ｍｂｐｓ（＝
１０＋１０）として求めてもよい。つまり、リンク容量
と個々の予約帯域とからナップザック問題を解き、リン
クに入らなかった予約帯域の和を求めることにより第１
の溢れ帯域としてもよい。

【０１５７】次に、この第１の溢れ帯域をもとに、各コ
ネクションについての評価値を求める（ステップＳ５
３）。なお、ここでは、リンクのコストを第１の溢れ帯
域の量で定義し、そのコストの小さい順にコネクション
とその経路を選択するものとしている。

【０１５８】すなわち、ステップＳ５４では、コストの
小さい順にａ本のコネクションをその経路に設定する。
ここでは、ａ＝１として１本のコネクションを張る毎に
ステップＳ５６で第１の溢れ帯域を計算し直すものとす
るコネクション１に経路Ａ→Ｂ→Ｃを設定したとすると
その経路のコストは「０」であり、経路Ａ→Ｄ→Ｃを設
定したとするとその経路のコストは「１５」である。コ
ネクション２に経路Ａ→Ｂ→Ｃを設定したとするとその
経路のコストは「０」であり、経路Ａ→Ｄ→Ｃを設定し
たとするとその経路のコストは「１５」である。コネク
ション３に経路Ａ→Ｄ→Ｅを設定したとするとその経路
のコストは「１５」であり、コネクション４に経路Ｄ→
Ｅを設定したとするとその経路のコストは「０」であ
る。

【０１５９】これらの中で最小コストの経路を探す。コ
スト「０」の経路が３つあるのでその中の一つを選び、
エネクション１に経路Ａ→Ｂ→Ｃを設定したものとす
る。すると、ステップＳ５６で、第１の溢れ帯域を計算
し直す。この時、経路Ａ→Ｄ→Ｃに予約したコネクショ
ン１の帯域を取り除き、経路Ａ→Ｂ→Ｃ上のリンク容量
をコネクション１の帯域の分だけ減じる。その結果、第
一の溢れ帯域Ｏは、Ｏ＝｛０，０，５，０，０｝とな
る。同様にして、コネクション２に経路Ａ→Ｂ→Ｃを割
り当てる。そして、第１の溢れ帯域を計算し直し、Ｏ＝
｛０，０，０，０，０｝を得る。同様の繰り返しによ
り、コネクション３に経路Ａ→Ｄ→Ｅを設定し、コネク
ション４に経路Ｄ→Ｅを設定する。

【０１６０】ここでは、全てのコネクションの全ての経
路のコストを一旦計算し、その最小コストの経路を選ん
だが、帯域が最大であるコネクションをまず選び、選ば
れたコネクションをその最小コスト経路に設定するよう
にしてもよい。

【０１６１】次に、第４の実施形態について説明する。

【０１６２】この第４の実施形態における経路選択装置
１では、経路決定部１０３の構成が第３の実施形態と異
なる。

【０１６３】図１９は、図１２の経路決定部１０３の他
の構成例を示したもので、第２の溢れ帯域算出部１２
０、評価値算出部１２１、経路選択部１２２から構成さ
れる。

【０１６４】第２の溢れ帯域算出部１２０は、コネクシ
ョンをある経路に設定したと仮定し、そのコネクション
の予約帯域をその経路上以外のリンクから取り除いた場
合に、リンクから予約帯域が溢れる量である第２の溢れ
帯域を、全てのコネクションの全ての経路に対して求め
る。

【０１６５】評価値算出部１２１は、全てのコネクショ
ンの全ての経路に対して、第２の溢れ帯域とリンク毎に
定義された定数との重み和によりコストを定義する。評
価値算出部１２１は、このコストの逆数により評価値を
求める。

【０１６６】経路選択部１２２は、少なくとも１本のコ
ネクションを評価値の大きい順に経路に決定していく。
経路の決定したコネクションの予約帯域は、その経路上
以外のリンクから取り除く。以後、この操作を全てのコ
ネクションの経路が決定するまで繰り返す。

【０１６７】評価値算出部１２１は、コストの逆数で評
価値を求める代わりに、あるコネクションがある経路を
通過する場合に得られる利得を定義し、この利得をコス
トで割ることにより評価値を求めても良い。評価値算出
部１２１は、全てのリンクに対して第２の溢れ帯域の値
が「０」である場合には、経路のコストとして予め与え
られる定数を用いてもよい。

【０１６８】図２０は、第４の実施形態に係る経路選択
装置１００の動作処理を説明するためのフローチャート
である。

【０１６９】まず、経路探索部１０１は、各コネクショ
ンの取り得る経路を全てサーチし（ステップＳ６０）、
その結果を経路情報として帯域予約部１０２に出力す
る。

【０１７０】帯域予約部１０２は、各コネクションの帯
域をそのとり得る経路上のリンクに予約し（ステップＳ
６１）、第２の溢れ帯域算出部１２０は、コネクション
をある経路に設定したと仮定し、そのコネクションの予
約帯域をその経路上以外のリンクから取り除いた場合
に、リンクから予約帯域が溢れる量である第２の溢れ帯
域を、全てのコネクションの全ての経路に対して求める
（ステップＳ６２）。

【０１７１】評価値算出部１２１は、第２の溢れ帯域を
用いて評価値を算出し（ステップＳ６３）、その算出さ
れた評価値の大きい順に、経路選択部１２２で、コネク
ションの経路を選択し（ステップＳ６４）、全てのコネ
クションの経路が決定するまで（ステップＳ６５）、帯
域予約情報を変更しながら（ステップＳ６６）、ステッ
プＳ６２〜ステップＳ６５の処理を繰り返す。

【０１７２】図１６に示すようなネットワークついて、
図１７に示す各コネクションの経路を選択する場合を例
にとり、図２０のフローチャートに示した経路選択処理
について具体的に説明する。

【０１７３】まず、図１７に示した各コネクションｉ
（ｉ＝１〜４）のとり得る経路を求め（ステップＳ６
０）、コネクションの帯域を各リンクに予約していく
（ステップＳ６１）。その結果としての帯域の予約状況
を図１８に示す。また、このとき、サーチされた、取り
得る経路を図２１に示す。すなわち、図２１において、
経路Ａ→Ｂ→Ｃには経路番号１が付され、経路Ａ→Ｄ→
Ｃには経路番号２が付され、経路Ａ→Ｄ→Ｅには、経路
番号３が付され、経路Ｄ→Ｅには経路番号４が付されて
いる。

【０１７４】次に、第２の溢れ帯域算出部１２１で第２
の溢れ帯域を算出する（ステップＳ６２）。ここで、コ
ネクションｋを経路番号ｌの経路に設定したと仮定した
場合の第２の溢れ帯域をＯ_klと記述することにする。図
１７のコネクション１を図２１の経路番号１の経路に設
定したと仮定し、経路番号２の経路上の帯域からコネク
ション１の予約帯域を取り除き、第２の溢れ帯域を求め
るとＯ₁₁＝｛０，０，５，０，０｝となる。

【０１７５】コネクション１を経路番号２の経路に設定
したと仮定し、経路番号１の経路上の帯域からコネクシ
ョン１の予約帯域を取り除き、第２の溢れ帯域を求める
とＯ₁₂＝｛０，０，１５，０，０｝となる。

【０１７６】コネクション２についても同様にＯ₂₁＝
｛０，０，５，０，０｝、Ｏ₂₂＝｛０，０，１５，０，
０｝となる。

【０１７７】コネクション３に経路番号３の経路を設定
したと仮定すると、コネクション３は他にとり得る経路
がないため取り除くべき予約帯域は存在せず、第２の溢
れ帯域はＯ₃₃＝｛０，０，１５，０，０｝となる。

【０１７８】コネクション４についても同様に第２の溢
れ帯域を求めるとＯ₄₄＝｛０，０，１５，０，０｝とな
る。

【０１７９】次に、第２の溢れ帯域Ｏ_klより評価値Ｖ_kl
を次式で求める（ステップＳ６３）。

【０１８０】

【数４】 但し、Ｃ_klは、コネクションｋを経路ｌに張る時に得ら
れる利得を表す。ここでは、簡単のためＣ_kl＝（コネク
ションｋの帯域）とする。もちろん、Ｃ_klはコネクショ
ン毎、経路毎に異なる値をとってもよい。

【０１８１】式（１０）を用いて算出された評価値を列
挙すると、Ｖ₁₁＝１０／５、Ｖ₁₂＝１０／１５、Ｖ₂₁＝
１０／５、Ｖ₂₂＝１０／１５、Ｖ₃₃＝１４５／１５、Ｖ
₄₄＝５／１５となる。

【０１８２】次に、図２０のフローチャートのステップ
Ｓ６４の処理において、ａ＝２とすると、コネクション
１が経路番号１の経路に、コネクション３が経路番号３
の経路にコネクションが設定されることになる。

【０１８３】次に、帯域予約情報を変更する（ステップ
Ｓ６６）。つまり、コネクション１の予約帯域を経路番
号１の経路以外のリンク（リンク３、リンク４）から取
り除く。

【０１８４】そして、ステップＳ６２に戻り、経路の決
定していないコネクションに対して第２の溢れ帯域を求
める。すると、Ｏ₂₁＝｛０，０，０，０，０｝、Ｏ₂₂＝
｛０，０，５，０，０｝、Ｏ₄₄＝｛０，０，５，０，
０｝となる。Ｏ_kl＝｛０，０，０，０，０｝のとき、式
（１０）を用いて評価値を求めることはできないため、
Ｖ_kl＝Ｃ_klで評価値を求めることにする（ステップＳ６
３）。その結果、Ｖ₂₁＝１０、Ｖ₂₂＝１０／５、Ｖ₄₄＝
５／５となり、コネクション２が経路番号２の経路に、
コネクション４が経路番号４の経路に設定されることと
なる（ステップＳ６４）。

【０１８５】この例では、全てのコネクションの全ての
経路に対して第２の溢れ帯域を求め評価値を求めている
が、計算量を削減するために、利得の大きい順にコネク
ションを少なくとも１本のコネクションを選び、選ばれ
たコネクションに対してのみ評価値を求めてもよい。

【０１８６】次に、第５の実施形態について説明する。

【０１８７】この第５の実施形態における経路選択装置
１では、経路決定部１０３の構成が第３の実施形態と異
なる。

【０１８８】図２２は、図１２の経路決定部１０３のさ
らに他の構成例を示したもので、第１の溢れ帯域算出部
１３０、第２の溢れ帯域算出部１３１、評価値算出部１
３２、経路選択部１３３から構成される。

【０１８９】第１の溢れ帯域算出部１３０は、帯域予約
情報と、リンク容量等のネットワーク情報を用いて各リ
ンクから予約帯域が溢れる量である第１の溢れ帯域を求
めるものである。

【０１９０】第２の溢れ帯域算出部１３１は、全てのコ
ネクションの全ての経路に対して、コネクションがある
経路を通ったものと仮定し、その経路上にないリンクか
らそのコネクションの予約帯域を取り除いた場合に、予
約帯域がリンクから溢れる量である第２の溢れ帯域を求
めるものである。

【０１９１】評価値算出部１３２は、第１の溢れ帯域と
第２の溢れ帯域とネットワーク情報とコネクション情報
から各コネクションとその経路に対して評価値を算出す
るようになっている。

【０１９２】経路選択部１３３は、評価値算出部１３２
で算出された評価値に従いコネクションに経路を設定す
るものである。

【０１９３】図２３は、第５の実施形態に係る経路選択
装置１００の動作処理を説明するためのフローチャート
である。

【０１９４】まず、経路探索部１０１が各コネクション
の取り得る経路を全てサーチし（ステップＳ７０）、そ
の結果を経路情報として帯域予約部１０２に出力する。

【０１９５】帯域予約部１０２は、各コネクションの帯
域をそのとり得る経路上のリンクに予約し（ステップＳ
７１）、第１の溢れ帯域算出部１３０は、帯域予約部１
０２から出力された帯域予約情報と、リンク容量等のネ
ットワーク情報を用いて各リンクから予約帯域が溢れる
量である第１の溢れ帯域を求め（ステップＳ７２）、さ
らに、第２の溢れ帯域算出部１３１は、経路が未決定で
第２の溢れ帯域をまだ求めていないコネクションを１本
選び（ステップＳ７３）、そのコネクションが通り得る
各経路に対して、第２の溢れ帯域を求める（ステップＳ
７４）。

【０１９６】全ての経路未決定のコネクションに対し第
２の溢れ帯域を算出したら（ステップＳ７５）、次に、
評価値算出部１３２は、経路未決定の全てのコネクショ
ンの全ての経路に対する評価値を第１の溢れ帯域と第２
の溢れ帯域とを用いて求める（ステップＳ７６）。

【０１９７】経路選択部１３３は、算出された評価値を
最大とするコネクションと経路を求め、そのコネクショ
ンをその経路に設定する（ステップＳ７７）。経路未決
定のコネクションが存在するときは、再びステップＳ７
２に戻り、全てのコネクションに対し経路が設定される
まで、ステップＳ７２〜ステップＳ７８の処理を繰り返
す。

【０１９８】図１６に示すようなネットワークにおい
て、図１７に示す各コネクションの経路を選択する場合
を例にとり、図２３のフローチャートに示した経路選択
処理について具体的に説明する。

【０１９９】まず、図１７に示した各コネクションｉ
（ｉ＝１〜４）のとり得る経路を求め（ステップＳ７
０）、コネクションの帯域を各リンクに予約していく
（ステップＳ７１）。その結果としての帯域の予約状況
を図１８に示す。

【０２００】このとき、第１の溢れ帯域を求めるとＯ＝
｛０，０，１５，０，０｝となる（ステップＳ７２）。

【０２０１】次に、第２の溢れ帯域を求める（ステップ
Ｓ７３）。記述を簡単にするため、サーチされた、取り
得る経路を図２１に示す。また、コネクションｋを経路
ｌに設定したと仮定した場合の第２の溢れ帯域をＯ_klと
記述することにする。

【０２０２】コネクション１を経路番号１の経路に設定
したと仮定し、経路番号２の経路上のコネクション１の
予約帯域を取り除き、第２の溢れ帯域を求めるとＯ₁₁＝
｛０，０，５，０，０｝となる。

【０２０３】コネクション１を経路番号２の経路に設定
したと仮定し、経路番号１の経路上のコネクション１の
予約帯域を取り除き、第２の溢れ帯域を求めるとＯ₁₂＝
｛０，０，１５，０，０｝となる。

【０２０４】コネクション２についても同様にＯ₂₁＝
｛０，０，５，０，０｝、Ｏ₂₂＝｛０，０，１５，０，
０｝となる。

【０２０５】コネクション３に経路番号３の経路を設定
したと仮定すると、コネクション３は他にとり得る経路
がないため取り除くべき予約帯域は存在せず、第２の溢
れ帯域はＯ₃₃＝｛０，０，１５，０，０｝となる。

【０２０６】コネクション４についても同様に第２の溢
れ帯域を求めるとＯ₄₄＝｛０，０，１５，０，０｝とな
る。

【０２０７】次に、ステップＳ７６に進み、各コネクシ
ョンの全ての経路に対する評価値を求める。コネクショ
ンｋを経路ｌに設定した時の評価値をＶ_klと書くことに
すると、Ｖ_klは、 Ｖ_kl＝Ｃ_kl（Ｏ・（Ｏ−Ｏ_kl）） …（１１） と計算できる。ただし、Ｏ・Ｏ′はベクトルＯとベクト
ルＯ′との内積を表し、Ｃ_klはコネクションｋを経路ｌ
に設定する時に得られる利得である。また、評価値Ｖ_kl
は、コネクションｋを経路ｌに決定するために必要なコ
ストＫ_klを用いて、 Ｖ_kl＝（Ｏ・（Ｏ−Ｏ_kl））／Ｋ_kl …（１２） として求めても良い。

【０２０８】ここでは、コストＫ_klをコネクションｋの
帯域と経路のホップ数との積として定義し、評価値を式
（１２）で計算する。すると、 Ｖ₁₁＝（１５×１０）／（２×１０）＝１５／２ Ｖ₁₂＝０／（２×１０）＝０ となる。

【０２０９】コネクション２、３、４に対しても同様
に、 Ｖ₂₁＝（１５×１０）／（２×１０）＝１５／２ Ｖ₂₂＝０／（２×１０）＝０ Ｖ₃₃＝０／（２×１４５）＝０ Ｖ₄₄＝０／５＝０ となる。

【０２１０】次に、ステップＳ７７に進み、評価値の最
大値を探すとＶ₁₁＝Ｖ₂₁＝１５／２であることがわか
る。そこで、コネクション１に経路番号１の経路を設定
する。

【０２１１】さらに、ステップＳ７２に進み、第１の溢
れ帯域を再計算する。すなわち、経路番号２の経路上の
リンクに予約されたコネクション１の予約帯域を取り除
き、経路１上のリンクの容量をコネクション１の帯域の
分だけ減じる。その後、各リンクから溢れる予約帯域の
量を求めると、Ｏ＝｛０，０，５，０，０｝となる。

【０２１２】第２の溢れ帯域を同様にして求めると、Ｏ
₂₁＝｛０，０，０，０，０｝、Ｏ₂₂＝｛０，０，５，
０，０｝、Ｏ₃₃＝｛０，０，５，０，０｝、Ｏ₄₄＝
｛０，０，５，０，０｝となる（ステップＳ７３〜ステ
ップＳ７４）。

【０２１３】評価値を求めると、Ｖ₂₁＝５／２０、Ｖ₂₂
＝０、Ｖ₄₄＝０となり（ステップＳ７６）、最大の評価
値はＶ₂₁であるため、コネクション２に経路番号１の経
路を設定する。

【０２１４】以後、同様の繰り返しにより、コネクショ
ン３に経路番号３の経路を、コネクション４に経路番号
４の経路を設定する。

【０２１５】なお、ここでは、コネクションを１本張る
毎に第１の溢れ帯域の計算を行なっているが、計算量を
減少させるためにａ（＞１）本コネクションを張るまで
は第１の溢れ帯域の再計算を行なわず、ａ本のコネクシ
ョンを張る毎に第１の溢れ帯域の再計算を行なってもよ
い。また、ここでは、全てのコネクションの全ての経路
に対して評価値の計算を行なっているが、計算量を減少
させるために、コネクショの優先度・帯域等の情報から
評価値を求めるコネクショクを制限してもよい。

【０２１６】例えば、図２４に示すネットワークを考え
る。図２４は、図１６に示したネットワークに、さら
に、ノードＡとノードＤの間にリンク６を張り、ノード
間に２本のリンク（リンク３とリンク６）が張られてい
る場合を示している。このとき、リンク３とリンク６を
論理的に１本のリンクであると考え帯域の予約を行な
う。そして、第１あるいは第２の溢れ帯域を求める時
は、既に経路の決定したコネクションの帯域と予約帯域
の和からリンク容量の和を引くことにより溢れ帯域を求
めることができる。あるいは、既に経路の決定したコネ
クションの帯域は必ずどれかのリンクに収容されるとい
う条件の下にナップザック問題を解くことにより溢れ帯
域を求めてもよい。

【０２１７】以上、説明したように、上記第３〜第５の
実施形態によれば、経路探索部１０１により各コネクシ
ョンのとり得る経路を全て探索し、帯域予約部１０２で
各コネクションの帯域を経路探索部１０１により求めら
れた経路上のリンクに予約して、経路決定部１０３は、
この予約状況を経路選択のための情報として用いてコネ
クションの経路を決定していくことにより、高い近似精
度で経路選択問題を解くことが可能となる。すなわち、
各コネクションに対して、その帯域をそのコネクション
の取り得る全ての経路に予約し、溢れ帯域と呼ぶ各リン
クから溢れる予約帯域の量を求め、この溢れ帯域をなる
べく減らすようにコネクションの経路を決定することが
できるので、過度にリンクの負荷を分散することなく、
経路選択問題の精度のよい近似解を得ることができる。

【０２１８】また、上記第３の実施形態によれば、各リ
ンク毎に予約された帯域の中でリンクに収容することの
できない帯域である第１の溢れ帯域の量を経路決定部１
０３が用いることにより、各リンクから溢れる可能性の
ある帯域の量を知ることができ、この第１の溢れ帯域を
減らすようにコネクションの経路を決定していくことに
より、高い近似精度で経路選択問題を解くことが可能と
なる。

【０２１９】また、上記第４の実施形態によれば、ある
コネクションがある経路を通ったものと仮定し、その経
路上にないリンクからそのコネクションの予約帯域を取
り除いた場合に、各リンクに収容できない可能性のある
帯域の量である第２の溢れ帯域を経路決定部１０３が用
いることにより、あるコネクションがある経路を通った
場合の溢れ帯域の量を知ることができ、従って、最も溢
れ帯域を小さくすることのできるコネクションとその経
路を知ることができる。これにより、高い近似精度で経
路選択問題を解くことが可能となる。

【０２２０】また、上記第５の実施形態によれば、第１
の溢れ帯域と第２の溢れ帯域の量を経路決定部１０３が
用いることにより、あるコネクションがある経路を通っ
た場合に減少する溢れ帯域の量を知ることができ、これ
により、全てのリンクの溢れ帯域の量が「０」となるよ
うにコネクションの経路を決定することができる。従っ
て、高い近似精度で経路選択問題を解くことが可能とな
る。

【０２２１】ここまでは、あらかじめ与えられたのネッ
トワークについて、ノード間に設定されているリンクの
容量、コスト等を考慮してコネクションの最適な経路を
選択する場合について説明した。

【０２２２】次に、例えば、トラヒックの情報とネット
ワークのトポロジーに関する情報があらかじめ与えられ
た場合に、それらをもとに所望のノード間に帯域、コス
ト等を考慮して最適のリンクを張り通信網を設計する通
信網設計方法と、その通信網設計方法を用いた通信網設
計装置について説明する。

【０２２３】まず、第６の実施形態について説明する。

【０２２４】図２５は、第６の実施形態に係る通信網設
計装置２００の構成を示したものである。

【０２２５】図２５において、通信網設計装置２００
は、初期トポロジー設定部２０１、トポロジー変更部２
０２、初期経路設定部２０３、経路変更部２０４、エッ
ジコスト算出部２０５から構成される。

【０２２６】初期トポロジー設定部２０１は、ノード数
・ノード間に設定可能なリンクの種類等のネットワーク
情報と通信フローの発ノード・着ノード・帯域・通信経
路の好悪等のトラヒック情報とを用いて、通信網の初期
トポロジーを求めるようになっている。

【０２２７】トポロジー変更部２０２は、初期トポロジ
ー設定部２０１が求めたトポロジーあるいはトポロジー
変更手段２０２が以前に求めたトポロジーを用いて新た
なトポロジーを求めるようになっている。

【０２２８】初期経路設定部２０３は、初期トポロジー
設定部２０１あるいはトポロジー変更手段２０２によっ
て求められたトポロジー上に要求されたフローの経路を
求めるようになっている。

【０２２９】エッジコスト算出部２０５は、各エッジ毎
にエッジ上を流れるフローの量からエッジのコストを求
めるようになっている。

【０２３０】経路変更部２０４は、エッジコスト算出部
２０５によって求められたエッジコストを用いてフロー
の経路の変更を行なうようになっている。フローの経路
の変更が行なわれると、各エッジを流れるフローの量も
変化するため、エッジコスト算出部２０５は、再びエッ
ジコストの計算を行なう。その後、経路変更部２０４
は、新しく求められたエッジコストを用いてフローの経
路を変更する。この繰り返しによりフローの経路を決定
するようになっている。

【０２３１】フローの経路が決定した後、トポロジー変
更部２０２は現在使用しているトポロジーの変更を行な
い、初期経路設定部２０３に新しいトポロジーを送る。
同様にしてこの新しいトポロジーに対してフローの経路
割当を行なう。このようにトポロジーの変更と経路設定
を繰り返し行なうことにより、通信網の設計を行なうこ
とができる。

【０２３２】次に、図２６に示すフローチャートを参照
して図２５の通信網設計装置２００の動作処理について
説明する。

【０２３３】まず、初期トポロジー設定部２０１は初期
トポロジーを求め（ステップＳ１００）、初期経路設定
部２０３は、その初期トポロジーにおいて、フローの初
期経路を求める（ステップＳ１０１）。

【０２３４】続いて、エッジコスト算出部２０５にて、
エッジコストと網コストを求め（ステップＳ１０２、ス
テップＳ１０３）、ステップＳ１０４で条件判定を行な
う。この段階では、フローの初期経路と網の初期コスト
が求まっただけであるので、無条件にステップＳ１０５
に進む。

【０２３５】ステップＳ１０５では、経路変更手段５０
０でフローの経路を変更し、続いてステップＳ１０２、
ステップＳ１０３に進み、エッジコスト算出部２０５に
てエッジコストと網コストを求める。

【０２３６】そして、ステップＳ１０４に進み、網コス
トが前回よりも低下しているならば、ステップＳ１０５
に進み、フローの経路の変更を繰り返す。網コストが前
回よりも増加しているならば、ステップＳ１０６に進
み、フローの経路を前回の経路に戻す。

【０２３７】次に、ステップＳ１０７の条件判定に進む
が、この段階では、初期トポロジーを用いた網コストの
みが求まっただけであるので、無条件にステップＳ１０
８に進み、トポロジー変更部２０２により与えられる新
しいトポロジーを用いて、ステップＳ１０１〜ステップ
Ｓ１０６の処理、すなわち、フローの経路と網コストを
求める。この新たに求まった網コストが、前回のトポロ
ジーを用いた場合の網コストよりも小さければ（ステッ
プＳ１０７）、ステップＳ１０８に進み、前述のよう
に、トポロジーを変更しフローの経路を求める。そし
て、新たに求まった網コストが前回のトポロジーを用い
た網コストよりも大きくなっていれば（ステップＳ１０
７）、ステップＳ１０９に進み、前回のトポロジーを用
いて得た通信網設計情報を出力する。

【０２３８】通信網設計情報の内容としては、例えば、
あらかじめ与えられたノード間にはられるエッジ（通信
網のトポロジー）、リンクの種類、フローの経路等があ
る。

【０２３９】次に、通信網設計の手順を図２６に示した
フローチャートを参照して具体的に説明する。

【０２４０】初期トポロジー設定部２０１は、図２６の
ステップＳ１００に示すようにネットワーク情報とトラ
ヒック情報とから初期トポロジーを求める。

【０２４１】例えば、設計対象の通信網がノードＡ、
Ｂ、Ｃ、Ｄで構成されるものとすると、ネットワーク情
報には、例えば図２７に示すように、これらノード間に
設定することができるリンクの容量とそのために必要と
なるコスト等も含まれる。すなわち、図２７に示すネッ
トワーク情報には、ノード数「４」、ノード間に設定可
能なリンクの種類はリンクＡＢ、ＡＣ、ＡＤ、ＢＡ、Ｂ
Ｃ、ＢＤ、ＣＡ、ＣＢ、ＣＤ、ＤＡ、ＤＢ、ＤＣである
こと、それら各リンクについての容量およびその容量に
対するコスト等が含まれる。

【０２４２】また、トラヒック情報としては、例えば、
ノードＡからノードＢに５０Ｍｂｐｓのフロー（フロー
１）と、ノードＡからノードＤに５０Ｍｂｐｓのフロー
（フロー２）を流す需要が与えられたものとする。

【０２４３】このようなネットワーク情報およびトラヒ
ック情報をもとに、初期トポロジー設定部２０１で求め
た初期トポロジーの具体例を図２８に示す。

【０２４４】図２８において、各ノードＡ、Ｂ、Ｃ、Ｄ
間に引かれた線をエッジと呼び、ノード間にエッジが設
定されている場合にのみ、そのノード間にリンクを設定
できるものとする。図２８では、初期トポロジーとして
フルメッシュのトポロジーを用いているが、ネットワー
ク情報あるいはトラヒック情報から、設定することが望
まれないエッジが存在する場合には初期トポロジーとし
てフルメッシュトポロジーを用いる必要はない。

【０２４５】次に、図２６のステップＳ１０１に進み、
初期経路設定部２０３は、図２８に示す初期トポロジー
について、フローの初期経路を求める。そして、エッジ
を流れるフローの量を用いてエッジコスト算出部２０５
がエッジコストと網コストを求め（ステップＳ１０２、
ステップＳ１０３）、これらを用いて経路変更部２０４
がフローの経路を変更する（ステップＳ１０５）。

【０２４６】新たなフローの経路に基づいてエッジコス
ト算出部２０５がエッジコストを再計算し（ステップＳ
１０２〜ステップＳ１０３）、この再計算されたエッジ
コストを用いて経路変更部２０４がフローの経路を変更
する（ステップＳ１０４〜ステップＳ１０５）。

【０２４７】この経路の変更を繰り返すことにより、フ
ローの経路を決定する。この経路の決定過程の具体例を
図２９に示す。なお、図２９において、括弧内の数字は
エッジコストを示す。

【０２４８】まず、図２９（ａ）のように、初期トポロ
ジーの各エッジにコストを割り当てる。ここでは、各エ
ッジに設定できるリンクの中で最小容量のリンクを選
び、そのリンクの単位容量当りのコストをエッジのコス
トとしている。そして、そのエッジのコストを用いて最
小コスト経路を求め、初期経路としている。その結果、
フロー初期経路は、フロー１に対しては経路Ａ→Ｂ、フ
ロー２に対しては経路Ａ→Ｄが与えられる。

【０２４９】次に、ステップＳ１０２に進み、エッジコ
スト算出部２０５がエッジの新たなコストを求める。図
２９（ｂ）では、通過しているフローの量の合計が
「０」よりも大きいエッジには、リンク容量がフローの
量の合計よりも大きくかつ最小のコストを持つリンクを
選びそのコストを与え、フローの量の合計が「０」のエ
ッジには、初期経路を決める際と同様に、最小容量のリ
ンクの単位容量当りのコストを与えている。すなわち、
図２９（ｂ）では、エッジＡＢ（フロー１）には容量６
０Ｍｂｐｓでコストが「１２（万円）」のリンクを与
え、エッジＡＤ（フロー２）には容量６０Ｍｂｐｓでコ
ストが「１２（万円）」のリンクを与えている。

【０２５０】次に、ステップＳ１０３に進み、経路変更
部２０４で網コストを求める。図２９（ｂ）では、フロ
ーが通過しているエッジのコストの和を求め、その結
果、網コストは「２４」となる。

【０２５１】次に、ステップＳ１０４に進み、前回の経
路を用いた場合と新たな経路を用いた場合とで網コスト
の比較を行なうのだが、今回は前回の経路が存在しない
ため、無条件でステップＳ１０５に進み、経路変更部２
０４は、フローの経路を変更する。

【０２５２】例えば、図２９（ｃ）では、エッジコスト
を用いて最小コスト経路をフローに割り当てている。具
体的には、図２９（ｂ）のエッジコストを用いて最小コ
スト経路を求めることにより、フロー１の変更後の経路
として経路Ａ→Ｃ→Ｂが求められ、フロー２の変更後の
経路として経路Ａ→Ｃ→Ｄが求められる。フロー１とフ
ロー２の経路を変更した様子を図２９（ｃ）に示す。

【０２５３】図２９（ｃ）では、フロー１とフロー２を
新たな経路に全て変更しているが、Leonard Kleinrock
によるQueueing Systems（ vol２，ｐｐ．２７０−４２
１，John Wiley＆Sons，１９７６）に記載されたＦＤ法
のようにフローの一部を新たな経路に変更しても良い。
また、Kleinrock によるのFIXED ROUTING のようにフロ
ー１を新たな経路に変更し、網コストが減少しない場合
にはフロー１の経路をもとに戻し、次にフロー２の経路
を新たな経路に変更し、網コストが減少しない場合には
フロー２の経路をもとに戻すといったように、逐次フロ
ーの経路を変更していってもよい。

【０２５４】次に、ステップＳ１０２に進み、エッジコ
ストを再び求める。図２９（ｃ）では、フロー１、フロ
ー２の経路に共通な経路Ａ→Ｃに、容量１００Ｍｂｐ
ｓ、コスト「１６」のリンクを与え、フロー１の経路Ｃ
→Ｂに容量６０Ｍｂｐｓ、コスト「３」のリンクを与
え、フロー２の経路Ｃ→Ｄに容量６０Ｍｂｐｓ、コスト
「３」のリンクを与えている。

【０２５５】ステップＳ１０３に進み、網コストを求め
ると「２２」となり、前回と比べ網コストが減少してい
るため（ステップＳ１０４）、もう一度。ステップＳ１
０５に進みフローの経路を変更する。

【０２５６】すると、フローの経路は図２９（ｂ）のよ
うになるため、網コストが増加し、今回はステップＳ１
０４からステップＳ１０６に進み、フローの経路を変更
前に戻す。つまり、フローの経路は図２９（ｃ）の状態
に戻される。

【０２５７】次に、ステップＳ１０７の条件判定を行な
うのだが、初期トポロジーを用いているので、無条件に
ステップＳ１０８に進む。ステップＳ１０８では、トポ
ロジー変更部２０２でトポロジーの変更を行ない、この
新たなトポロジーを用いて、初期経路設定部２０３とエ
ッジコスト算出部２０５と経路変更部２０４により前述
のステップＳ１０１〜ステップＳ１０６の処理を行い、
フローの経路を決定する。

【０２５８】ステップＳ１０７では、経路変更部２０４
は、前回のトポロジーを用いた場合の網コストと比べ、
現在のトポロジーを用いた網コストが減少していればス
テップＳ１０８に進み、そうでなければ、ステップＳ１
０９に進み、前回のトポロジーを用いた場合のフローの
経路ノード間に設定されたリンクの種類等の通信網設計
情報を出力する。

【０２５９】図２９の経路決定過程の説明では、各エッ
ジを流れるフローからエッジコストを計算し、フローの
経路を最小コスト経路へ変更することを試みている。そ
うではなく、エッジコスト算出部２０５は、各エッジを
流れるフローから求められるエッジコストであるエッジ
コスト１と、あるフローを選択し、各リンクにその選択
したフローが加わったと仮定した時のエッジコストであ
るエッジコスト２を求める。経路変更部２０４は、エッ
ジコスト２とエッジコスト１の差である増加コストをリ
ンク毎に求め、経路上の各リンクの増加コストの和が最
小である経路へ、選択されたフローの経路の変更を試み
る。この操作を全てのフローに対して行なうことにより
フローの経路変更を行なってもよい。

【０２６０】以後に説明する通信網設計装置の他の実施
形態においても、フローの経路の変更先は、現在のフロ
ーの量よりエッジコストを求めエッジコストの和が最小
の経路を選択してもよいし、経路変更を試みるフローが
各リンクに新たに加わったとして増加するエッジコスト
を求め増加コストの和が最小となる経路を選択してもよ
い。

【０２６１】次に、第７の実施形態について説明する。

【０２６２】図３０は、第７の実施形態に係る通信網設
計装置３００の構成を示したものである。

【０２６３】図３０において、通信網設計装置３００
は、初期トポロジー設定部３０１、トポロジー変更部３
０２、初期経路設定部３０３、経路変更部３０４、エッ
ジコスト算出部３０５、最良結果記憶部３０６から構成
されている。

【０２６４】初期トポロジー設定部３０１は、ノード数
・ノード間に設定可能なリンクの種類等のネットワーク
情報と通信フローの発ノード・着ノード・帯域・通信経
路の好悪等のトラヒック情報とを用いて、通信網の初期
トポロジーを求めるようになっている。

【０２６５】トポロジー変更部３０２は、初期トポロジ
ー設定部３０１が求めたトポロジーあるいはトポロジー
変更手段２０２が以前に求めたトポロジーを用いて新た
なトポロジーを求めるようになっている。

【０２６６】初期経路設定部３０３は、初期トポロジー
設定部３０１あるいはトポロジー変更手段３０２によっ
て求められたトポロジー上に要求されたフローの経路を
求めるようになっている。

【０２６７】エッジコスト算出部３０５は、各エッジ毎
にエッジ上を流れるフローの量からエッジのコストを求
めるようになっている。

【０２６８】次に、図３１に示すフローチャートを参照
して、図３０の通信網設計装置３００の動作処理につい
て説明する。

【０２６９】まず、ステップＳ１２０に進み、例えば、
トポロジー変更部３０２のトポロジー記憶部３１０にあ
らかじめ記憶されているトポロジーを変更した回数ｈに
初期値「０」を記憶する。そして、ステップＳ１２１に
進み、初期トポロジー設定部３０１において、初期トポ
ロジーを求め、次にステップＳ１２２に進み、初期経路
設定部３０３が、その初期トポロジーを対象にフローの
初期経路を求める。

【０２７０】そして、ステップＳ１２３〜ステップＳ１
２４で、エッジコスト算出部３０５により各エッジを流
れるフローからエッジコストと網コストを算出する。

【０２７１】次に、ステップＳ１２５に進み、今回の網
コストが前回の網コストより低下したか否かの条件判定
を行なうのであるが、今回はフローの初期経路と網の初
期コストが求まった段階であるので、無条件にステップ
Ｓ１２６に進む。

【０２７２】ステップＳ１２６では、経路変更部３０４
がフローの経路を変更し、再びステップＳ１２３、ステ
ップＳ１２４に進み、エッジコスト算出部３０５がエッ
ジコストと網コストを求める。そして、ステップＳ１２
５で、網コストが前回の網コストよりも低下しているの
であればステップＳ１２６に進み、コストが増加してい
るのであればステップＳ１２７に進む。

【０２７３】ステップＳ１２７では、フローの経路を変
更前に戻し、ステップＳ１２８に進み、条件判定を行な
う。すなわち、トポロジーを変更した回数ｈが規定回数
Ｋよりも小さい場合、ステップＳ１２９に進み、トポロ
ジーを変更した回数に１を加え、ステップＳ１３０に進
む。このとき、ステップＳ１３０では、過去に最良結果
記憶部３０６に網情報を記憶したことがないため、無条
件にステップＳ１３１に進み、最良結果記憶部３０６に
今回の通信網設計情報を記憶し、ステップＳ１３２に進
み、トポロジー変更部３０２がトポロジーを変更し、更
にステップＳ１２２に戻る。以後同様のことを繰り返
す。

【０２７４】なお、ステップＳ１２８で、トポロジーを
変更した回数ｈが規定回数Ｋ以上のときは、ステップＳ
１３３に進み、最良結果記憶部３０６に記憶されている
通信網設計情報を出力し、処理が終了する。

【０２７５】この第７の実施形態にかかる通信網設計装
置３００が、第６の実施形態と異なる点は、トポロジー
変更を繰り返し、網コストが前回のトポロジーを用いた
場合の網コストよりも増加した場合でもトポロジーの変
更を続け、ある規定回数（Ｋ）のトポロジー変更を行な
った後に最良結果記憶部３０６に記憶してある通信網設
計情報を出力することである。

【０２７６】図３２は、トポロジー変更部３０２の構成
例を示したもので、トポロジー記憶部３１０、エッジ削
除部３１１、トポロジー選択部３１２から構成される。

【０２７７】初期トポロジー設定部３０１で求められた
初期トポロジー情報が出力されて、トポロジー記憶部３
１０に記憶されるようになっている。

【０２７８】エッジ削除部３１１は、通信フローの発ノ
ード・着ノード・帯域・経路の好悪等のトラヒック情報
と過去のフローの経路割り当て結果とを用いて、トポロ
ジー記憶部３１０に記憶されているトポロジーのエッジ
からｋ（＞０）本のエッジを取り除くことにより、複数
の新たなトポロジーを求めるようになっている。その結
果もとめられたトポロジー情報は初期経路設定部３０３
に出力される。

【０２７９】トポロジー選択部３１２は、エッジ削除部
３１１の求めた複数のトポロジーに対して、経路変更部
３０４で決定された経路の結果を用い、その中で最良の
結果を得ることのできたトポロジーを選択するようにな
っている。そして、この選ばれたトポロジーはトポロジ
ー記憶部３１２に再度記憶されるようになっている。

【０２８０】エッジ削除部３１１は、トポロジー記憶部
３１０に新たに記憶されたトポロジーからエッジをｋ本
削除することにより、新たなトポロジーを求める。以
後、この繰り返しにより、通信網の設計を行なう。

【０２８１】次に、図３２に示したような構成のトポロ
ジー変更部３０２の動作処理について、図３３に示すフ
ローチャートを参照して詳細に説明する。

【０２８２】まず、ステップＳ１４０に進み、トポロジ
ー記憶部３１０には、初期トポロジー設定部３０１で求
められた初期トポロジーの情報が記憶されているとす
る。すなわち、この初期トポロジーを対象にすでに図３
１のステップＳ１２２〜ステップＳ１２５の処理が行わ
れたものとする。

【０２８３】次に、ステップＳ１４１に進み、エッジ削
除部３１１は、トポロジー記憶部３１０に記憶されてい
るトポロジーのエッジをｂ本取り除くことにより新たな
トポロジーを作り、これを出力する。出力したトポロジ
ーを用いて図３１のステップＳ１２２〜ステップＳ１２
５の処理が行われ、その結果、経路変更部３０４から通
信網設計情報を受けとると、再びエッジ削除部３１１
は、トポロジー記憶部３１０に記憶されているトポロジ
ーからｂ本のエッジを取り除くことにより新たなトポロ
ジーを生成し、これを出力する（ステップＳ１４２）。
このとき、エッジ削除部３１１は、過去に生成したトポ
ロジーとは異なったトポロジーを生成することはいうま
でもない。このようにして、エッジ削除部３１１は、新
たなトポロジーを生成していく。すなわち、トポロジー
記憶部３１０に図２８に示したような初期トポロジーが
記憶されているとすると、エッジ削除部３１１で、この
初期トポロジーから、例えば、ｂ＝２本のエッジを取り
除くことにより生成される新たなトポロジーの具体例を
図３４に示す。

【０２８４】図３４に示す（ａ）図〜（ｏ）図は、初期
トポロジーとして、ノードＡ、Ｂ、Ｃ、Ｄ間に引かれた
６本のエッジのうち、２本のエッジを削除した場合に考
え得る全ての新たなトポロジーを示している。

【０２８５】ここでは、ｂ本のエッジを削除することに
より得られる全てのトポロジーをエッジ削除部３１１は
生成しているが、例えば、任意のノード間の経路は２つ
以上必要であり、この制限を破壊するエッジの削除パタ
ーンを禁止してもよい。また、計算量を削減するため、
フローの経路に対する好悪等のトラヒック情報や通信網
設計情報を用いて、網コストを減少させる可能性の低い
トポロジーの生成を禁止してもよい。

【０２８６】エッジ削除部３１１が許される全てのトポ
ロジーを生成したならば（ステップＳ１４３）、ステッ
プＳ１４４に進み、トポロジー選択部３１２は、トポロ
ジー記憶部３１０に現在記憶されているトポロジーを用
いてエッジ削除部３１１が生成したトポロジーの中から
最小の網コストを与えるトポロジーを選択する。

【０２８７】ステップＳ１４４で選択されたトポロジー
を用いた場合の網コストが、トポロジー記憶部３１０に
記憶されているトポロジーを用いた場合の網コストより
も減少している場合は（ステップＳ１４５）、ステップ
Ｓ１４４で選択されたトポロジーをトポロジー記憶部３
１０に記憶し（ステップＳ１４６）、ステップＳ１４１
に進み、新たなトポロジーの生成を続ける。

【０２８８】一方、ステップＳ１４５で選択されたトポ
ロジーを用いた場合の網コストが、トポロジー記憶部３
１０に記憶されているトポロジーを用いた場合の網コス
トよりも減少していない場合には（ステップＳ１４
５）、新しいトポロジーの生成を終了する。あるいは、
図３１のステップＳ１２８のように、網コストが減少し
なくとも、あらかじめ与えられた回数だけトポロジーの
生成を続けてもよい。

【０２８９】このとき、ｂは固定した値であってもよい
が、トポロジー記憶部３１０に記憶されているトポロジ
ーのエッジの数の非減少関数で決定してもよい。

【０２９０】なお、図３２の示したトポロジー変更部３
０２の構成例は、前述の第６の実施形態におけるトポロ
ジー変更部２０２の構成例としても有効である。この場
合、図２６のステップＳ１０７において、経路変更部２
０４がトポロジーの変更を行なうか否かの判断を行う
際、トポロジー記憶部３１０に記憶されているトポロジ
ーを用いた場合の網コストと、エッジ削除部３１１で、
そのトポロジーからｂ（＞０）本のエッジを取り除くこ
とにより得られる複数のトポロジーの中で最も良い結果
を与えるトポロジーを用いた場合の網コストを比較する
ことはいうまでもない。

【０２９１】次に、第８の実施形態について説明する。
ここでは、ノード間に２本以上のリンクを設定すること
が許されている場合の通信網設計方法および通信網設計
装置について説明する。

【０２９２】ノード間に２本以上のリンクを設定するこ
とが許されている場合のエッジのコストの計算方法とし
ては、例えば、次のようなものがある。すなわち、エッ
ジｅを通過するフローの合計量をｙと書くことにする
と、リンク容量の和がｙ以上でかつリンクのコストの合
計が最小となるリンクの組合せを選び、選ばれたリンク
のコストの和をエッジｅのコストとしてエッジコスト算
出部３０５が求めることにより、通信網設計装置３００
をノード間に２本以上のリンクを設定することが許され
ている場合における通信網設計装置として用いることが
できる。

【０２９３】次に、ノード間に２本以上のリンクを設定
することが許されている場合の設定するリンクの選び方
について説明する。以下の説明において、エッジｅを通
過するフローの合計量がｙであり、そのエッジに設定す
ることのできるリンクはｎ種類あり、ｉ番目のリンクの
容量をａ_i 、コストをｃ_i と書くことにし、エッジ上に
設定すべきｉ番目のリンクの本数をｘ_i で表すことにす
る。すると、最小コストのリンクを選ぶには、次の問題
（Ｐ（ｙ））を解けばよいことが分かる。

【０２９４】問題（Ｐ（ｙ））とは、式（１２）の制約
条件のもと、式（１１）で表されるｚを最小化する解を
求めることである。

【０２９５】

【数５】

【０２９６】

【数６】 なお、ｙ，ｃ_j ，ａ_j は非負の整数であるものとする。
このような仮定をおいてもｙ，ｃ_j ，ａ_j が有限桁の実
数である場合には、適当な整数をかけることにより整数
とすることができるので、実用上の問題はない。

【０２９７】問題（Ｐ（ｙ））の最適値をＧ（ｙ）と書
く。すなわち、

【０２９８】

【数７】 と定義する。

【０２９９】次に、問題（Ｐ（ｙ））の最適解Ｘ＝（ｘ
₁ 、ｘ₂ 、…、ｘ_n ）に対して、

【０３００】

【数８】 を定義する。すると、ｘ_j ＞０ならば、Ｘ´＝（ｘ₁ 、
…、ｘ_j-1 、ｘ_j 、ｘ_j+1 、…、ｘ_n ）は、問題（Ｐ
（ｙ−ａ_j ））の最適解であるから。ｘ_j ＞０なる全て
のｊに対して式（１５）が成り立つ。

【０３０１】

【数９】 従って、

【０３０２】

【数１０】 とおくと、Ｔ（ｙ）＝φのとき、

【０３０３】

【数１１】 となる。定義よりＧ（０）＝０であるから式（１７）を
用いてＧ（ｙ）を再帰的に求めることができる。また、
Ｔ（ｙ）≠φのとき、

【０３０４】

【数１２】 で求めることができる。

【０３０５】さらに、Ｇ（ｙ）は次の性質を持つ。すな
わち、ａ_max ＝max _j ｛ａ_j ｝とするとき、

【０３０６】

【数１３】 を満たすならばｙ＞ｙ^* なるｙに対して次式が成り立
つ。

【０３０７】

【数１４】 このＧ（ｙ）の周期性を用いると、問題（Ｐ（ｙ））を
さらに容易に解くことができる。

【０３０８】以上をまとめ、問題Ｐ（ｙ）を解くアルゴ
リズム（手順）を説明する。 （手順１） もし、ｙ＝０ならＧ（ｙ）＝０、ｘ＝０と
し、処理を終了する。 （手順２） ａ_max ＝max _j ａ_j 、ｙ^* ＝１、Ｇ（ｉ）
＝∞（ｉ＝１，２，…，ｙ）、ｄ（ｉ）＝ｎ（ｉ＝１，
２，…，ｙ）、ｘ_j ＝０（ｊ＝１，２，…，ｎ） （手順３） ｉ＝１ （手順４） もしｉ＝ｙ^* ＋ａ_max ならば手順９へ、も
しｉ＞ｙならば手順１１へ （手順５） Ｓ（ｉ）、Ｔ（ｉ）を求め、式（１８）を
用いてＧ（ｉ）を求める。この時、式（１８）を満足す
るｊをｊ^* で表す。 （手順６） ｄ（ｉ）＝ｊ^* （手順７） もしｊ^* ≠ならば、ｙ^* ＝ｉ＋１ （手順８） ｉ＝ｉ＋１として手順４へ （手順９） ｋ＝「（ｙ−ｙ^* ）／ａ₁ 」，ｙ′＝ｙ−
ｋａ₁ （手順１０） Ｇ（ｙ）＝ｋｃ₁ ＋Ｇ（ｙ′），ｉ＝
ｙ′ （手順１１） もしｉ＝０なら終了 （手順１２） ｊ＝ｄ_i ，ｘ_j ＝ｘ_j ＋１ （手順１３） ｉ＝ｉ−ａ_j （手順１４） 手順１１へ なお、「ｘ」は、ｘ以下の最大整数を表すものとする。

【０３０９】上記の方法により、エッジを通過するフロ
ーの合計量から、そのエッジ上に張るべきリンクが決定
できる。例えば、ノードＡ、Ｂ、Ｃ、Ｄで構成されるネ
ットワークについて、これらノード間に、図３５で示す
ような容量、コストの２種類づつのリンクを設定できる
場合、各ノード間に複数のリンクを設定できるとすれ
ば、各エッジにおける流れるフローの量とエッジコスト
の関係は、図３６に示すようになる。

【０３１０】図３５は、ノードＡ、Ｂ、Ｃ、Ｄで構成さ
れるネットワークの各リンク毎に、設定され得る容量と
そのコストを示したテーブル群を示したもので、図３６
は、そのネットワークの各エッジ毎に、そのエッジに流
れるフローの量に対するコストの関係の一具体例を示し
たテーブル群を示したものである。

【０３１１】例えば、図３５に示すノードＡ、Ｂ間に設
定できるリンクが、容量２０Ｍｂｐｓでコスト４万円の
リンクと、容量１００Ｍｂｐｓでコスト１６万円のリン
クであるとすると、そのエッジＡＢに流れるフローの量
とエッジコストの関係は、図３６より、フローの量が０
〜２０Ｍｂｐｓのときは、容量２０Ｍｂｐｓのリンクを
１本はり、従ってコストは４万円であることがわかる。
また、フローの量が２０〜４０Ｍｂｐｓのときは、容量
２０Ｍｂｐｓのリンクを２本はり、従ってコストは８万
円であることがわかる。また、フローの量が４０〜６０
Ｍｂｐｓのときは、容量２０Ｍｂｐｓのリンクを３本は
り、従ってコストは１２万円であることがわかる。さら
に、フローの量が６０〜１００Ｍｂｐｓのときは、容量
１００Ｍｂｐｓのリンクを１本はり、従ってコストは１
６万円であることがわかる。

【０３１２】なお、エッジコスト算出部３０５では、前
述の手順１から手順１４を行う代わりに、例えば、図３
６のような各エッジにおける流れるフローの量とエッジ
コストの関係を示したテーブル群をあらかじめ記憶する
ようにしてもよい。

【０３１３】次に、第９の実施形態について説明する。

【０３１４】図３７は、第９の実施形態に係る通信網設
計装置４００の構成を示したもので、フロー算出部４０
１、仮想網設計部４０２、コネクション経路決定部４０
３、リンク設定部４０４から構成されている。

【０３１５】フロー算出部４０１は、コネクション情報
として、設定したいコネクションの需要を受けとり、発
ノードと着ノードを同じくするコネクションの帯域の合
計を求め、仮想的にフローを生成するものである。

【０３１６】仮想網設計部４０２は、フロー算出部４０
１が求めたフローを設定する網を設計するものである。

【０３１７】コネクション経路決定部４０３は、仮想網
設計部４０２が設計したフローの経路からコネクション
の経路を決定するものである。この決定されたコネクシ
ョンの経路を基に、リンク設定部４０４がノード間に設
定すべきリンクを決定するようになっている。

【０３１８】例えば、Ａ、Ｂ、Ｃという３つのノードが
与えられ、ノードＡからノードＢへ帯域が７０Ｍｂｐｓ
のコネクションを２本、ノードＣからノードＡへ帯域が
５０Ｍｂｐｓと７０Ｍｂｐｓのコネクションを各々１本
ずつ、ノードＣからノードＢへ帯域が８０Ｍｂｐｓと７
０Ｍｂｐｓと１０Ｍｂｐｓのコネクションを各々１本ず
つ設定する需要がある場合を考える。コネクションの経
路は、２つ以上に分岐してはいけないものとする。

【０３１９】フロー算出部４０１は、このようなコネク
ションの情報を基にフローを生成する。その結果、ノー
ドＡからノードＢへ設定することを要求する帯域が１４
０Ｍｂｐｓのフローと、ノードＣからノードＡへ設定す
ることを要求する帯域が１２０Ｍｂｐｓのフローと、ノ
ードＣからノードＢへ設定することを要求する帯域が１
６０Ｍｂｐｓのフローが生成される。

【０３２０】このとき、各ノード間に設定可能なリンク
の種類が図３８で示すように与えられているとする。す
なわち、ノードＡとノードＢの間、ノードＢとノードＣ
の間、ノードＣとノードＡの間には、それぞれ１５０Ｍ
ｂｐｓのリンクが設定可能であるとする。また、そのコ
ストは各ノード間で等しいものとする。

【０３２１】このとき、このリンクの容量とコスト等に
関する情報（ネットワーク情報）とフロー算出部４０１
が生成したフローの情報とを用いて、仮想網設計部４０
２は、フローの経路とノード間に設定すべきリンクを決
定する。その結果得られたフローの経路を図３９に示
す。

【０３２２】このフローの経路を用いて、コネクション
経路決定部４０３は、コネクションの経路を決定する。
図３９では、ノードＣからノードＢへ設定を要求するフ
ローの一部がノードＡを経由している。このようにフロ
ーの経路が分岐している場合には、各経路のフローの帯
域に応じて、その経路に設定されるコネクションを決め
る。図３９では、ノードＣからノードＢへ設定されたフ
ローの経路が１５０Ｍｂｐｓと１０Ｍｂｐｓの２つの経
路に分岐している。このフローの元になっているコネク
ションの帯域は、８０Ｍｂｐｓ、７０Ｍｂｐｓ、１０Ｍ
ｂｐｓであるので、このコネクションの帯域を用いてフ
ローの帯域となるべく近くなるようにコネクションの経
路を決める。その結果、図４０のように１０Ｍｂｐｓの
コネクションが経路Ｃ→Ａ→Ｂに設定される。

【０３２３】以上の結果、コネクションの経路は、図４
０のように決定される。すなわち、ノードＡからノード
Ｂへ帯域が７０Ｍｂｐｓの２本のコネクションの経路、
ノードＣからノードＡへ帯域が５０Ｍｂｐｓと７０Ｍｂ
ｐｓの２本のコネクションの経路、ノードＣからノード
Ｂへ帯域が８０Ｍｂｐｓと７０Ｍｂｐｓの２本のコネク
ションの経路、ノードＣからノードＡを経由してノード
Ｂに向かう１０Ｍｂｐｓのコネクションの経路が決定さ
れる。

【０３２４】すると、ノード間を通過するコネクション
が既に決定されているため、各ノード間で通過するコネ
クションを収容するリンクを決定することができる。

【０３２５】この例では、コネクションを収容する最終
的な網と仮想網は同じリンクを設定しているが、必要な
らば、仮想網と最終的に設計される網とで設計されるリ
ンクが異なっていてもよい。

【０３２６】図３７に示した通信網設計装置４００の構
成の説明では、設定すべきコネクション群がコネクショ
ン情報として予め与えられるという前提で説明を行なっ
たが、コネクション設定要求が確率的に生起する場合に
は、コネクション設定拒絶確率が予め与えられる閾値以
下になるように設定すべきコネクション群を求めてもよ
い。

【０３２７】また、図３７に示した通信網設計装置４０
０の仮想網設計部４０２は、図２５、図３０に示したよ
うな通信網設計装置２００、３００を用いても有効であ
る。この場合、図３７の通信網設計装置４００のフロー
算出部４０１で求められた通信フローの情報をトラヒッ
ク情報とすればよい。

【０３２８】以上説明したように、上記第６〜第９の実
施形態によれば、トポロジーの変更とフローの経路の変
更を繰り返すことにより、通信網設計問題の精度のよい
近似解を得ることができ、また、設定すべきコネクショ
ンが与えられている場合には、コネクションをフローに
変換して、その仮想的なフローに対する通信網設計問題
を解き、その解をもとに、コネクションの経路を決定す
ることにより、少ない計算量で網設計を行うことができ
る。

【０３２９】また、上記第６の実施形態に係る通信網設
計方法およびその方法を用いた通信網設計装置によれ
ば、初期トポロジー設定部２０１が与えた初期トポロジ
ーに、初期経路設定部２０３はフローの設定を行ない、
次に、各エッジ上を流れるフローの量からエッジコスト
算出部２０５は、エッジのコストを求め、その結果をも
とに経路変更部２０４でフローの新しい経路を求め、フ
ローの一部または全部を新しい経路に移すことにより変
化する各エッジ上を流れるフローの量に伴い変化するエ
ッジのコストを再計算し、以下、同様の操作を網コスト
が低下しなくなるまで繰り返し、さらに、トポロジー変
更部２０２により初期トポロジーを変更し、この変更さ
れたトポロジーを用いてフローの経路を決定して、さら
に、トポロジーの変更とその新しいトポロジーに対して
フローの経路の決定を繰り返し、トポロジーの変更によ
り網コストが低下しなくなるまで繰り返すことにより、
網設計問題の精度の良い近似解を得ることが可能とな
る。

【０３３０】また、上記第７の実施形態に係る通信網設
計方法およびその方法を用いた通信網設計装置によれ
ば、初期トポロジー設定部３０１が与えた初期トポロジ
ーに、初期経路設定部３０３はフローの設定を行ない、
次に、各エッジ上を流れるフローの量からエッジコスト
算出部３０５は、エッジのコストを求め、その結果をも
とに経路変更部３０４でフローの新しい経路を求め、フ
ローの一部または全部を新しい経路に移すことにより変
化する各エッジ上を流れるフローの量に伴い変化するエ
ッジのコストを再計算し、以下、同様の操作をフローの
経路が変更されなくなるまで繰り返し、さらに、トポロ
ジー変更部３０２により初期トポロジーを変更し、この
変更されたトポロジーを用いてフローの経路を決定し
て、さらに、トポロジーの変更とその新しいトポロジー
に対してフローの経路の決定を繰り返し、この繰り返し
の中で最良の結果を最良結果記憶部３０６に記憶してお
くことにより、網設計問題の精度の良い近似解を得るこ
とが可能となる。

【０３３１】また、トポロジー記憶部３１０に記憶され
ているトポロジーからエッジ削除手段が与えられた数だ
けエッジを取り除く際に取り除くエッジの組合せを変更
することにより複数のトポロジーを得て、この複数のト
ポロジーに対してフローの経路の決定を行ない、最も良
い結果を与えるトポロジーをトポロジー選択部３１２が
選び、トポロジー記憶部３１０に再記憶し、この操作を
繰り返すことにより、網設計問題の精度の良い近似解を
得ることが可能となる。

【０３３２】また、上記第８の実施形態に係る通信網設
計方法およびその方法を用いた通信網設計装置によれ
ば、エッジコスト算出部３０５は、エッジコストをフロ
ーを収容することのできるリンクの組合せの中で最小コ
ストのリンクの組合せを選ぶことにより、網設計問題の
精度の良い近似解を得ることが可能となる。

【０３３３】また、上記第９の実施形態によれば、設定
すべき複数のコネクションが与えられ、１本のコネクシ
ョンの経路が２つ以上に分岐することが許されていない
場合の網設計問題は組合せ問題となるため、解くことが
非常に困難となるが、発ノードと着ノードを同じくする
コネクションをまとめて、フロー算出部４０１が、フロ
ーを求め、フローの経路は２つ以上に分岐してもよいも
のとすることにより、仮想網設計部４０２は網設計問題
を解くことが容易になる。このようにして求めたフロー
の経路を基にコネクションの経路をコネクション経路決
定部４０３を用いて求める。その後、コネクションの経
路を基に、各ノード間に設定すべきリンクをリンク設定
部４０４が求める。この操作により、コネクションを設
定する網設計問題を少ない計算量で解くことが可能とな
る。

【０３３４】

【発明の効果】以上説明したように、本発明によれば、
同じ双方向コネクションに属する上りコネクションと下
りコネクションが同じ経路を通るという条件のもとに最
適な経路の選択を効率的に行える経路選択方法および経
路選択装置を提供できる。

【０３３５】また、本発明によれば、あらかじめ与えら
れたネットワーク上に複数のコネクションの経路を選択
するという経路選択問題の精度のよい近似解を与えるこ
とが可能な経路選択方法および経路選択装置を提供でき
る。

【０３３６】また、本発明によれば、ノード間に設定可
能なリンクの容量とコストとトラヒック需要から通信網
を設計するという通信網設計問題の精度のよい近似解を
少ない計算量で得ることができる通信網設計方法および
通信網設計装置を提供できる。

【図面の簡単な説明】

【図１】本発明の第１の実施形態に係る経路選択装置の
構成を概略的に示したブロック図。

【図２】図１の評価値算出部の構成を概略的に示すブロ
ック図。

【図３】図１の経路選択部の構成を概略的に示すブロッ
ク図。

【図４】評価値算出部の処理動作を説明するためのフロ
ーチャート。

【図５】経路選択部の処理動作を説明するためのフロー
チャート。

【図６】経路選択対象のネットワークの構成例を示した
図。

【図７】経路選択を行うために必要なコネクション情報
の内容の具体例を示した図。

【図８】本発明の第２の実施形態に係る経路選択装置の
構成を概略的に示したブロック図。

【図９】図１の評価値算出部の構成を概略的に示したブ
ロック図。

【図１０】図１の経路選択装置の処理動作を説明するた
めのフローチャート。

【図１１】図１の経路選択装置の処理動作を具体的に説
明するために用いたコネクション情報の内容の具体例を
示した図。

【図１２】本発明の第３の実施形態に係る経路選択装置
の構成を概略的に示したブロック図。

【図１３】経路選択対象のネットワークの構成例を示し
た図。

【図１４】図１２の経路決定部の構成を概略的に示した
ブロック図。

【図１５】図１２の経路選択装置の処理動作を説明する
ためのフローチャート。

【図１６】経路選択対象のネットワークの他の構成例を
示した図。

【図１７】経路選択を行うために必要なコネクション情
報の内容の他の具体例を示した図。

【図１８】各コネクションの帯域の予約状況の具体例を
示した図。

【図１９】本発明の第４の実施形態に係る経路決定部の
構成を概略的に示したブロック

【図２０】第４の実施形態に係る経路選択装置の動作処
理を説明するためのフローチャート。

【図２１】経路探索部で探索された経路と経路番号の対
応の一例を示した図。

【図２２】本発明の第５の実施形態に係る経路決定部の
構成を概略的に示したブロック図。

【図２３】第５の実施形態に係る経路選択装置の動作処
理を説明するためのフローチャート。

【図２４】ノード間に複数のリンクが張られている場合
の経路選択方法について説明するための図。

【図２５】本発明の第６の実施形態に係る通信網設計装
置の構成を概略的に示したブロック図。

【図２６】第６の実施形態に係る通信網設計装置の動作
処理を説明するためのフローチャート。

【図２７】通信網の設計に必要なネットワーク情報の内
容の具体例を示した図で、ノード間に設定可能なリンク
の種類と、そのリンクの容量、コストの情報が含まれて
いる。

【図２８】初期トポロジー設定部で求めた初期トポロジ
ーの具体例を示した図。

【図２９】フローの経路の決定過程を説明するための
図。

【図３０】本発明の第７の実施形態に係る通信網設計装
置の構成を概略的に示したブロック図。

【図３１】第７の実施形態に係る通信網設計装置の動作
処理を説明するためのフローチャート。

【図３２】トポロジー変更部の構成を概略的に示したブ
ロック図。

【図３３】図３２のトポロジー変更部の動作処理を説明
するためのフローチャート。

【図３４】エッジ削除部で所定数のエッジを削除して作
成される新たなトポロジーの具体例を示した図。

【図３５】通信網の設計に必要なネットワーク情報の内
容の他の具体例を示した図で、ノード間に設定可能なリ
ンクの種類と、そのリンクの容量、コストの情報が含ま
れている。

【図３６】ノード間に２本以上のリンクを設定できる場
合のエッジを通過するフローの量とエッジコストの対応
の具体例を示した図。

【図３７】本発明の第９の実施形態に係る通信網設計装
置の構成を概略的に示したブロック図。

【図３８】図３７の通信網設計装置の処理動作を説明す
るための図で、各ノード間に設定可能なリンクの一例を
示した図。

【図３９】図３７の通信網設計装置の処理動作を説明す
るための図で、仮想網設計部で仮想網を設計した結果得
られたフローの経路の具体例を示した図。

【図４０】図３７の通信網設計装置の処理動作を説明す
るための図で、コネクション経路決定部で決定された各
コネクションの経路の具体例を示した図。

【符号の説明】

１…経路選択装置、２…評価値算出部、３…経路選択
部、５…経路選択装置、６…パラメータ変更部、７…評
価値算出部、８…経路選択部、９…最良結果記憶部、１
００…経路選択装置、１０１…経路探索部、１０２…帯
域予約部、１０３…経路決定部、２００…通信網設計装
置、２０１…初期トポロジー設定部、２０２…トポロジ
ー変更部、２０３…初期経路設定部、２０４…経路変更
部、２０５…エッジコスト算出部、３００…通信網設計
装置、３０１…初期トポロジー設定部、３０２…トポロ
ジー変更部、３０３…初期経路設定部、３０４…経路変
更部、３０５…エッジコスト算出部、３０６…最良結果
記憶部。

Claims (20)

【特許請求の範囲】
1. 【請求項１】 複数のノード装置を接続してなる通信網
   に、複数の双方向コネクションの経路を、その上りコネ
   クションと下りコネクションが同じ経路を通るように選
   択する経路選択方法であって、 前記双方向コネクションの上りコネクションの帯域と下
   りコネクションの帯域をもとに、その双方向コネクショ
   ンの評価値を算出し、前記複数の双方向コネクションの
   それぞれについて算出された前記評価値に基づく順位に
   従って、前記複数の双方向コネクションの経路をそれぞ
   れ選択することを特徴とする経路選択方法。
2. 【請求項２】 前記双方向コネクションの上りコネクシ
   ョンの帯域がその下りコネクションの帯域よりも大きい
   かまたは等しいとき、前記上りコネクションの帯域の値
   に第１の重みの値を乗算したものと、前記下りコネクシ
   ョンの帯域の値に第２の重みの値を乗算したものとを加
   算することにより、前記双方向コネクションの評価値を
   算出し、前記上りコネクションの帯域が前記下りコネク
   ションの帯域よりも小さいとき、前記上りコネクション
   の帯域の値に前記第２の重みの値を乗算したものと、前
   記下りコネクションの帯域の値に前記第１の重みの値を
   乗算したものとを加算することにより前記双方向コネク
   ションの評価値を算出することを特徴とする請求項１記
   載の経路選択方法。
3. 【請求項３】 複数のノード装置を接続してなる通信網
   に、複数の双方向コネクションの経路を、その上りコネ
   クションと下りコネクションが同じ経路を通るように選
   択する経路選択装置であって、 前記双方向コネクションの上りコネクションの帯域と下
   りコネクションの帯域をもとに、前記双方向コネクショ
   ンの評価値を算出する評価値算出手段と、 この評価値算出手段で前記複数の双方向コネクションの
   それぞれについて算出された評価値に基づく順位に従っ
   て、前記複数の双方向コネクションの経路をそれぞれ選
   択する経路選択手段と、 を具備したことを特徴とする経路選択装置。
4. 【請求項４】 前記評価値算出手段は、前記双方向コネ
   クションの上りコネクションの帯域がその下りコネクシ
   ョンの帯域よりも大きいかまたは等しいとき、前記上り
   コネクションの帯域の値に第１の重みの値を乗算したも
   のと、前記下りコネクションの帯域の値に第２の重みの
   値を乗算したものとを加算することにより前記双方向コ
   ネクションの評価値を算出し、前記上りコネクションの
   帯域が前記下りコネクションの帯域よりも小さいとき、
   前記上りコネクションの帯域の値に前記第２の重みの値
   を乗算したものと、前記下りコネクションの帯域の値に
   前記第１の重みの値を乗算したものとを加算することに
   より前記双方向コネクションの評価値を算出することを
   特徴とする請求項３記載の経路選択装置。
5. 【請求項５】 複数のノード装置を接続してなる通信網
   に、複数の双方向コネクションの経路を、その上りコネ
   クションと下りコネクションが同じ経路を通るように選
   択する経路選択方法であって、 必要に応じて出力された異なるパラメータのそれぞれ
   と、前記双方向コネクションの上りコネクションの帯域
   と下りコネクションの帯域をもとに、前記双方向コネク
   ションの評価値を算出し、この算出された評価値に基づ
   く順位に従い、前記複数の双方向コネクションの経路を
   それぞれ選択し、その選択結果を前記パラメータに対応
   する経路選択結果として出力し、この出力された複数の
   経路選択結果に基づき、前記複数の双方向コネクション
   の最適経路を判断することを特徴とする経路選択方法。
6. 【請求項６】 複数のノード装置を接続してなる通信網
   に、複数の双方向コネクションの経路を、その上りコネ
   クションと下りコネクションが同じ経路を通るように選
   択する経路選択装置であって、 必要に応じて異なるパラメータを出力するパラメータ出
   力手段と、 このパラメータ出力手段で出力されたパラメータと、前
   記双方向コネクションの上りコネクションの帯域と下り
   コネクションの帯域をもとに、前記双方向コネクション
   の評価値を算出する評価値算出手段と、 この評価値算出手段で算出された評価値に基づく順位に
   従い、前記複数の双方向コネクションの経路をそれぞれ
   選択し、その選択結果を前記パラメータに対応する経路
   選択結果として出力する出力手段と、 この出力手段で出力された複数の経路選択結果に基づ
   き、前記複数の双方向コネクションの最適経路を判断す
   る判断手段と、 を具備したことを特徴とする経路選択装置。
7. 【請求項７】 複数のノード装置を接続してなる通信網
   に、複数のコネクションの経路を選択する経路選択方法
   であって、 前記複数のコネクションのとり得る経路を探索し、この
   探索された経路上のリンクに前記コネクションの帯域を
   予約して、その帯域の予約状態をもとに、前記複数のコ
   ネクションのそれぞれに対し、前記探索された経路のう
   ちの１つを選択することを特徴とする経路選択方法。
8. 【請求項８】 前記リンクに予約された帯域の中で前記
   リンクに収容できない溢れ帯域を算出し、この算出され
   た溢れ帯域をもとに、前記コネクションの取り得る経路
   に対して評価値を算出し、この算出された評価値に基づ
   く順位に従って、前記複数のコネクションのうち少なく
   とも１本のコネクションに対し、前記探索された経路の
   うちの１つを選択することを、全てのコネクションに対
   し経路が選択されるまで繰り返すことを特徴とする請求
   項７記載の経路選択方法。
9. 【請求項９】 前記コネクションに前記探索された経路
   のうちの１つを割り当てたと仮定し、その経路上にない
   リンクから前記コネクションの予約帯域を取り除いた場
   合に、予約された帯域の中でリンクに収容できない溢れ
   帯域を算出し、この算出された溢れ帯域をもとに、前記
   複数のコネクションの取り得る経路に対して評価値を算
   出し、この算出された評価値に基づく順位に従って、前
   記複数のコネクションのうち少なくとも１本のコネクシ
   ョンに対し、前記探索された経路のうちの１つを選択す
   ることを、全てのコネクションに対し経路が選択される
   まで繰り返すことを特徴とする請求項７記載の経路選択
   方法。
10. 【請求項１０】 前記リンクに予約された帯域の中で前
    記リンクに収容できない第１の溢れ帯域を算出し、前記
    コネクションに前記探索された経路のうちの１つを割り
    当てたと仮定し、その経路上にないリンクから前記コネ
    クションの予約帯域を取り除いた場合に、予約された帯
    域の中でリンクに収容できない第２の溢れ帯域を算出
    し、前記第１の溢れ帯域と前記第２の溢れ帯域をもと
    に、前記複数のコネクションの取り得る経路に対して評
    価値を算出し、この算出された評価値に基づく順位に従
    って、前記複数のコネクションのうち少なくとも１本の
    コネクションに対し、前記探索された経路のうちの１つ
    を選択することを、全てのコネクションに対し経路が選
    択されるまで繰り返すことを特徴とする請求項７記載の
    経路選択方法。
11. 【請求項１１】 複数のノード装置を接続してなる通信
    網に、複数のコネクションの経路を選択する経路選択装
    置であって、 前記複数のコネクションのとり得る経路を探索する経路
    探索手段と、 この経路探索手段で探索された経路上のリンクに前記コ
    ネクションの帯域を予約する帯域予約手段と、 この帯域予約手段で前記リンクに予約された帯域の予約
    状態をもとに、前記複数のコネクションのそれぞれに対
    し、前記経路探索手段で探索された経路のうちの１つを
    選択する経路選択手段と、 を具備したことを特徴とする経路選択装置。
12. 【請求項１２】 前記経路選択手段は、 前記帯域予約手段で前記リンクに予約された帯域の中で
    前記リンクに収容できない溢れ帯域を算出する溢れ帯域
    算出手段と、 この溢れ帯域算出手段で算出された溢れ帯域をもとに、
    前記経路探索手段で探索された前記コネクションの取り
    得る経路に対して評価値を算出する評価値算出手段と、 この評価値算出手段で算出された評価値に基づく順位に
    従って、前記複数のコネクションのうち少なくとも１本
    のコネクションに対し、前記経路探索手段で探索された
    経路のうちの１つを選択する選択手段と、 全てのコネクションに対し経路が選択されるまで、前記
    帯域の予約状態を更新して、その更新された帯域の予約
    状態のもと、前記溢れ帯域算出手段に対し溢れ帯域を算
    出するよう制御する制御手段と、 を具備したことを特徴とする請求項１１記載の経路選択
    装置。
13. 【請求項１３】 前記経路選択手段は、 前記コネクションに前記経路探索手段で探索された経路
    のうちの１つを割り当てたと仮定し、その経路上にない
    リンクから前記コネクションの予約帯域を取り除いた場
    合に、予約された帯域の中でリンクに収容できない溢れ
    帯域を算出する溢れ帯域算出手段と、 この溢れ帯域算出手段で算出され溢れ帯域をもとに、前
    記経路探索手段で探索された前記コネクションの取り得
    る経路に対して評価値を算出する評価値算出手段と、 この評価値算出手段で算出された評価値に基づく順位に
    従って、前記複数のコネクションのうち少なくとも１本
    のコネクションに対し、前記経路探索手段で探索された
    経路のうちの１つを選択する選択手段と、 全てのコネクションに対し経路が選択されるまで、前記
    帯域の予約状態を更新して、その更新された帯域の予約
    状態のもと、前記溢れ帯域算出手段に対し溢れ帯域を算
    出するよう制御する制御手段と、 を具備したことを特徴とする請求項１１記載の経路選択
    装置。
14. 【請求項１４】 前記経路選択手段は、 前記帯域予約手段で前記リンクに予約された帯域の中で
    前記リンクに収容できない第１の溢れ帯域を算出する第
    １の算出手段と、 前記コネクションに前記経路探索手段で探索された経路
    のうちの１つを割り当てたと仮定し、その経路上にない
    リンクから前記コネクションの予約帯域を取り除いた場
    合に、予約された帯域の中でリンクに収容できない第２
    の溢れ帯域を算出する第２の算出手段と、 前記第１の算出手段で算出された第１の溢れ帯域と、前
    記第２の算出手段で算出された第２の溢れ帯域をもと
    に、前記経路探索手段で探索された前記コネクションの
    取り得る経路に対して評価値を算出する評価値算出手段
    と、 この評価値算出手段で算出された評価値に基づく順位に
    従って、前記複数のコネクションのうち少なくとも１本
    のコネクションに対し、前記経路探索手段で探索された
    経路のうちの１つを選択する選択手段と、 全てのコネクションに対し経路が選択されるまで、前記
    帯域の予約状態を更新して、その更新された帯域の予約
    状態のもと、前記第１の算出手段、前記第２の算出手段
    に対し、それぞれ前記第１の溢れ帯域、前記第２の溢れ
    帯域を算出するよう制御する制御手段と、 を具備したことを特徴とする請求項１１記載の経路選択
    装置。
15. 【請求項１５】 少なくとも通信網を構成するノードの
    数と、その各ノードの識別情報、各ノード間に設定され
    得るリンクの種類とコストを含むネットワーク情報と、
    少なくとも通信フローの発ノードと着ノードの識別情
    報、その通信フローの量を含むトラヒック情報をもと
    に、前記トラヒック情報にて要求されるトラヒック需要
    を収容できる通信網を設計する通信網設計方法であっ
    て、 前記ネットワーク情報をもとに、前記通信網の初期トポ
    ロジーを設定し、必要に応じて前記初期トポロジーを変
    更し、その設定された初期トポロジー、あるいは、変更
    して得られたトポロジーに対して、前記トラヒック情報
    をもとに、所望のフローの経路を設定し、その設定され
    た経路上のリンクのコストを算出し、その算出されたコ
    ストが、あらかじめ定められた条件を満たすまで、前記
    設定された経路を変更しながら、その変更された経路上
    のリンクのコストを算出し、前記算出されたコストが、
    あらかじめ定められた条件を満たすとき、少なくとも、
    そのときの前記所望のフローの経路、前記ノード間に設
    定されたリンクの種類を含む通信網設計情報を出力する
    ことを特徴とする通信網設計方法。
16. 【請求項１６】 前記設定された初期トポロジーから、
    そのトポロジーを構成するためのノード間を接続する複
    数のエッジのうち、少なくとも１本のエッジを取り除
    き、その取り除かれるエッジの組合せを変えることによ
    り生成される複数のトポロジーのうち、そのトポロジー
    に対して設定された前記所望のフローの経路上のリンク
    のコストが、あらかじめ定められた条件を満たすものを
    記憶し、その記憶されたトポロジーに対して設定された
    前記所望のフローの経路、前記ノード間に設定されたリ
    ンクの種類を含む通信網設計情報を出力することを特徴
    とする請求項１５記載の通信網設計方法。
17. 【請求項１７】 少なくとも通信網を構成するノードの
    数と、その各ノードの識別情報、各ノード間に設定可能
    なリンクの種類とコストを含むネットワーク情報と、少
    なくとも各コネクション毎の要求帯域、発ノードと着ノ
    ードの識別情報を含むコネクション情報をもとに、前記
    コネクションを収容できる通信網を設計する通信網設計
    方法であって、 前記コネクション情報をもとに、発ノードと着ノードを
    同じくするコネクションの要求帯域をまとめることによ
    り通信フローを生成し、この生成された通信フローと前
    記ネットワーク情報をもとに、前記通信フローの経路と
    前記ノード間のリンクを設定することにより仮想網を設
    計し、この設計された仮想網をもとに、前記コネクショ
    ンの経路を決定し、この決定されたコネクションの経路
    をもとに前記ノード間に前記コネクションに対応するリ
    ンクを設定することを特徴とする通信網設計方法。
18. 【請求項１８】 少なくとも通信網を構成するノードの
    数と、その各ノードの識別情報、各ノード間に設定され
    得るリンクの種類とコストを含むネットワーク情報と、
    少なくとも通信フローの発ノードと着ノードの識別情
    報、その通信フローの量を含むトラヒック情報をもと
    に、前記トラヒック情報にて要求されるトラヒック需要
    を収容できる通信網を設計する通信網設計装置であっ
    て、 前記ネットワーク情報をもとに、前記通信網の初期トポ
    ロジーを設定する初期トポロジー設定手段と、 必要に応じて前記初期トポロジー設定手段で設定された
    初期トポロジーを変更するトポロジー変更手段と、 前記初期トポロジー設定手段で設定された初期トポロジ
    ー、あるいは、前記トポロジー変更手段で変更されたト
    ポロジーに対して、前記トラヒック情報をもとに、所望
    のフローの経路を設定する経路設定手段と、 この経路設定手段で設定された経路上のリンクのコスト
    を算出するコスト算出手段と、 このコスト算出手段で算出されたコストが、あらかじめ
    定められた条件を満たすまで前記経路設定手段で設定さ
    れた経路を変更し、前記コスト算出手段に対し、その変
    更された経路上のリンクのコストを算出するよう制御す
    る制御手段と、 前記コスト算出手段で算出されたコストが、あらかじめ
    定められた条件を満たすとき、少なくとも、そのときの
    前記所望のフローの経路、前記ノード間に設定されたリ
    ンクの種類を含む通信網設計情報を出力する出力手段
    と、 を具備したことを特徴とする通信網設計装置。
19. 【請求項１９】 前記トポロジー変更手段は、 前記初期トポロジー設定手段で設定されたトポロジーを
    記憶する記憶手段と、 この記憶手段に記憶されたトポロジーから、そのトポロ
    ジーを構成するためのノード間を接続する複数のエッジ
    のうち、少なくとも１本のエッジを取り除くエッジ削除
    手段と、 このエッジ削除手段で取り除かれるエッジの組合せを変
    えることにより生成される複数のトポロジーのうち、そ
    のトポロジーに対して前記経路設定手段で設定された前
    記所望のフローの経路が、あらかじめ定められた条件を
    満たすトポロジーを前記記憶手段に記憶するよう制御す
    る制御手段と、 を具備したことを特徴とする請求項１８記載の通信網設
    計装置。
20. 【請求項２０】 少なくとも通信網を構成するノードの
    数と、その各ノードの識別情報、各ノード間に設定可能
    なリンクの種類とコストを含むネットワーク情報と、少
    なくとも各コネクション毎の要求帯域、発ノードと着ノ
    ードの識別情報を含むコネクション情報をもとに、前記
    コネクションを収容できる通信網を設計する通信網設計
    装置であって、 前記コネクション情報をもとに、発ノードと着ノードを
    同じくするコネクションの要求帯域をまとめることによ
    り、通信フローを生成するフロー生成手段と、 このフロー生成手段で生成された通信フローと前記ネッ
    トワーク情報をもとに、前記通信フローの経路と前記ノ
    ード間のリンクを設定することにより仮想網を設計する
    仮想通信網設計手段と、 この仮想網設計手段で設計された仮想網をもとに、前記
    コネクションの経路を決定するコネクション経路決定手
    段と、 このコネクション経路決定手段で決定されたコネクショ
    ンの経路をもとにノード間に前記コネクションに対応す
    るリンクを設定するリンク設定手段と、 を具備することを特徴とする通信網設計装置。