(57)【要約】【課題】コネクションレス型通信ネットワークにおいて、任意の端末装置間の経路のうち、経路上のリンクのコストの最小値が最大となる経路または最大値が最小となる経路を、切断点を持つトポロジの場合においても計算を可能にする。【解決手段】あらかじめ、切断点となる中継装置を検出し、切断点以降の経路計算には、それまで保持していたリンクのコストの最小値あるいは最大値ではなく、切断点以降のリンクのコストの最小値あるいは最大値を用いて経路計算を行うようにＭＩＮ−ＭＡＸアルゴリズムを動作させる。【選択図】図１５
2005057658.tif 000002
【特許請求の範囲】
【請求項１】
端末装置と、中継装置と、これらの装置を相互に接続する複数の物理的あるいは論理的リンクとから構成されるコネクションレス型通信ネットワークにおいて、各リンクに経路選択のためのコストが付与されている場合に、前記ネットワーク内の任意の端末装置間の複数の経路のうち、経路上のコストの最小値が最大となる経路もしくは最大値が最小となる経路を計算する経路計算方法であって、前記ネットワークが、それを取り除くと複数のネットワークに切断されてしまう中継装置（切断点）を含む場合には、前記経路上のコストの最小値が最大となる経路もしくは最大値が最小となる経路の計算中に、切断点となる中継装置に達すると、それまで保持していたリンクのコストの最小値あるいは最大値を破棄し、切断点以降のリンクのコストの最小値あるいは最大値を基に経路の計算を行うことを特徴とする経路計算方法。
【請求項２】
前記ネットワーク内の中継装置のうち、それを取り除くと複数のネットワークに切断されてしまう中継装置（切断点）を深さ優先探索であらかじめ検出することを特徴とする請求項１記載の経路計算方法。
【請求項３】
前記経路の計算はＭＩＮ−ＭＡＸアルゴリズムを用い、該ＭＩＮ−ＭＡＸアルゴリズムを、切断点に達すると、それまで保持していたリンクのコストの最小値あるいは最大値を破棄し、切断点以降のリンクのコストの最小値あるいは最大値を用いて経路計算を行うように動作させることを特徴とする請求項１または２記載の経路計算方法。
【請求項４】
請求項１記載の方法を実施する装置であって、ネットワーク内の任意の端末装置間の経路のうち、経路上のコストの最小値が最大となる経路もしくは最大値が最小となる経路を計算し、該計算中にネットワーク内の切断点となる中継装置に達すると、それまで保持していたリンクのコストの最小値あるいは最大値を破棄し、切断点以降のリンクのコストの最小値あるいは最大値を基に経路の計算を行う手段を備えることを特徴とする経路計算装置。
【請求項５】
ネットワーク内の中継装置のうち、それを取り除くと複数のネットワークに切断されてしまう中継装置（切断点）を深さ優先探索であらかじめ検出する手段を更に備えることを特徴とする請求項１記載の経路計算装置。
【請求項６】
前記経路計算手段はＭＩＮ−ＭＡＸアルゴリズムを実行し、該ＭＩＮＩ−ＭＡＸアルゴリズムを、切断点に達すると、それまで保持していたリンクのコストの最小値あるいは最大値を破棄し、切断点以降のリンクのコストの最小値あるいは最大値を用いて経路計算を行うように動作することを特徴とする請求項４または５記載の経路計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コネクションレス型通信ネットワークにおいて、任意の端末装置間の経路のうち、経路上のリンクのコストの最小値が最大となる経路または最大値が最小となる経路を、切断点を持つトポロジの場合においても計算を可能にする経路計算方法に関するものであり、例えば各リンクのトラヒックなどに代表される、流量を最大にする必要のあるコストを最適化する経路を計算する場合に適用される。
【背景技術】
【０００２】
コネクションレス型通信網においては、２つの端末装置間の経路を計算し設定する必要があるが、この場合、経路は複数存在するため、経路上のリンクのコストを何らかの方法で評価し、最適な経路を計算する必要がある。
従来の最適な経路計算方法として、ダイクストラ（Dijkstra）アルゴリズムを基本とし、該アルゴリズムで計算された複数の経路のうち、経路上のリンクのコストの最小値を保持し、その値が最も大きい経路を選択するＭＩＮ−ＭＡＸアルゴリズムがある。このＭＩＮ−ＭＡＸアルゴリズムでは、リンクの物理的帯域に代表される、経路上のリンクのコストの最小値が最大となる経路を選択することにより、多くのパケット通信のトラヒックを収容することの可能な経路を計算していた（例えば、特許文献１参照）。
【０００３】
しかし、ＭＩＮ−ＭＡＸアルゴリズムでは、コストの最小値を保持したまま次の経路を探索するため、連結グラフにおける切断点のように、複数の経路候補が特定の中継（転送）装置を必ず通らなければならないようなトポロジで、かつ、始点から切断点（中継装置）までのコストの最小値が切断点以降の最小値より小さい場合、切断点以降はどの経路候補を選択してもリンクのコストの最小値が変わらなくなってしまうため、切断点以降は特定リンクにトラヒックが集中してしまうという問題点があった。
【０００４】
【特許文献１】特開２００１−２４４９７４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述したように、コネクションレス型通信網におけるトラヒック分散を目的とした従来の経路計算方法として、経路上の各リンクのコストの最小値を比較し、最小値が最大である経路を選択する経路計算方法があるが、このような経路計算方法では、経路候補の全てが切断点となる中継装置を通過しなければならないようなトポロジで、かつ、始点から切断点までのリンクのコストの最小値が切断点以降のリンクの最小値より小さい場合、切断点以降はどの経路候補を選択してもリンクのコストの最小値が変わらないため、特定経路にトラヒックが集中することがある。
【０００６】
本発明の目的は、上記のトラヒックの集中を回避することにあり、具体的には、切断点以降の経路計算においても、流量を最大化する経路の計算を行い得る経路計算方法および装置を提供することにある。
【課題を解決するための手段】
【０００７】
本発明の経路計算方法は、端末装置と、中継装置と、これらの装置を相互に接続する複数の物理的あるいは論理的リンクとから構成されるコネクションレス型通信ネットワークにおいて、各リンクに経路選択のためのコストが付与されている場合に、前記ネットワーク内の任意の端末装置間の複数の経路のうち、経路上のコストの最小値が最大となる経路もしくは最大値が最小となる経路を計算する経路計算方法であって、前記ネットワークが、それを取り除くと複数のネットワークに切断されてしまう中継装置（切断点）を含む場合には、前記経路上のコストの最小値が最大となる経路もしくは最大値が最小となる経路の計算中に、切断点となる中継装置に達すると、それまで保持していたリンクのコストの最小値あるいは最大値を破棄し、切断点以降のリンクのコストの最小値あるいは最大値を基に経路の計算を行うことを特徴とする。
【０００８】
また、本発明の経路計算方法を実施する装置は、ネットワーク内の任意の端末装置間の複数の経路のうち、経路上のコストの最小値が最大となる経路もしくは最大値が最小となる経路を計算し、該計算中に切断点となる中継装置に達すると、それまで保持していたリンクのコストの最小値あるいは最大値を破棄し、切断点以降のリンクのコストの最小値あるいは最大値を用いて経路の計算を行う手段とを備えることを特徴とする。
【０００９】
要するに、従来のＭＩＮ−ＭＡＸアルゴリズムでは、経路上のリンクのコストの最小値が最大となる経路あるいは最大値が最小となる経路を計算するだけであったが、本発明では、ネットワークが切断点を持つトポロジの場合に、切断点以降の経路計算には、それまで保持していたリンクのコストの最小値あるいは最大値ではなく、切断点以降のリンクのコストの最小値あるいは最大値を用いて経路計算を行うようにＭＩＮ−ＭＡＸアルゴリズムを動作させる。
【００１０】
このようにＭＩＮ−ＭＡＸアルゴリズムを拡張しても、経路上のリンクのコストの最小値が最大となる経路あるいは経路上のリンクのコストの最大値が最小となる経路が正しく計算される。なぜなら、このような拡張アルゴリズムでは、切断点によって分断される複数のネットワークにおいて、個々にＭＩＮ−ＭＡＸアルゴリズムを動作させていることになるため、個々のネットワーク内ではＭＩＮ−ＭＡＸアルゴリズムにより、流量を最大化する経路の計算を行えることが保証されるからである。
【００１１】
本発明の経路計算方法および装置では、ネットワーク内の中継装置のうち、それを取り除くと複数のネットワークに切断されてしまう中継装置（切断点）をあらかじめ検出するのが好ましい。この切断点の検出は深さ優先探索でネットワークワーク内のどの中継装置が切断点であるか探索することにより行うことができる、この切断点の検出はトポロジを構成したとき、あるいは、ネットワーク構成が変化したときにのみ行えばよい。
【００１２】
本発明の経路計算方法および装置では、経路計算自体はＭＩＮ−ＭＡＸアルゴリズムで行う。本発明ではＭＩＮ−ＭＡＸアルゴリズムを、切断点に達すると、それまで保持していたリンクのコストの最小値あるいは最大値を破棄し、切断点以降のリンクのコストの最小値あるいは最大値を用いて経路計算を行うように動作させる。従って、従来のＭＩＮ−ＭＡＸアルゴリズムと同等の計算量で経路計算を行うことができる。
【発明の効果】
【００１３】
本発明によれば、コネクションレス型通信ネットワークにおいて、切断点を持つようなトポロジにおいても、任意の端末装置間の経路のうち、経路上のリンクのコストの最小値が最大となる経路または最大値が最小となる経路を、少ない計算量で計算することが可能であるから、例えば各リンクのトラヒックなどに代表される、流量を最大にする必要のあるコストを最適化する経路を短時間で計算することなどが可能となる。
例えば、各リンクの経路選択のために付与されるコストが帯域である場合には、経路上のリンクの帯域の最小値が最大となる経路を選択することができる。
また、各リンクの経路選択のために付与されるコストが料金である場合には、経路上のリンクの料金の最大値が最小となる経路を選択することができる。
【発明を実施するための最良の形態】
【００１４】
本発明の実施形態をアルゴリズム表記により説明し、アルゴリズムの一実施例を図面により説明する。
本実施の形態では、あらかじめネットワークの切断点を深さ優先探索で検出し、その後、ＭＩＮ−ＭＡＸアルゴリズムを用いて経路計算を行う。
まず、ネットワーク中の切断点を深さ優先探索で検出する方法（切断点検出アルゴリズム）のアルゴリズム表記を示す。
【００１５】
＜定義＞
label(v):点vにおけるラベル値;
lowpt(v):点Vにおける以下の3つの値のうちの最小の値;
・label(v);
・点vから直接後退辺で到達できる頂点のラベル;
・点vからの木片のみの有効パスで到達できる頂点からさらに後退辺を
1本通って、到達できる頂点のラベル
bicmp(v):点vが切断点であるかの判定;
探索木:深さ優先探索において、始点を頂点とし、探索したリンクを枝とする木;
親:ある点に隣接し、探索木上である点より始点に近い点;
子:ある点に隣接し、探索木上である点より始点から遠い点;
【００１６】
＜アルゴリズム＞
begin
グラフ上のすべての点について  label(v):=0;
グラフ上の任意の点を始点sとする;
k:=1;
label(s):=k;
lowpt(s):=k;
k:=k+1;
sの子をvとする;
それぞれのvについて以下を行う;
while v≠s do
begin
label(v):=k;
lowpt(v):=k;
vの子をwとする;
if label(w)=0 であるwがある場合 then
begin
label(w):=k;
lowpt(w):=k;
k:=k+1;
wをvとする;
end
else if label(w)=0であるwが一つもない場合 then
begin
if label(w)>label(v) then
begin
lowpt(v):=min{lowpt(w), lowpt(v)};
if lowpt(w)≧label(v) then
begin
bicmp(v):=1;
end
else if lowpt(w)<label(v) and bicmp(v)≠1 then
begin
bicmp(v):=0;
end
end
else if label(w)<label(v) then
begin
lowpt(v):=min{label(w), lowpt(v)};
if lowpt(w)≧label(v) then
begin
bicmp(v):=1;
end
else if lowpt(w)<label(v) and bicmp(v)≠1 then
begin
bicmp(v):=0;
end
end
v自身をwとする;
vの親をvとする;
end
end
end
【００１７】
次に、切断点検出アルゴリズムで得られた切断点情報を基に、流量を最大化する経路を計算する方法（拡張ＭＩＮ−ＭＡＸアルゴリズム）のアルゴリズム表記を示す。
＜定義＞
U：始点からの最適経路が求まった点の集合；
V：すべての点の集合；
c(v)：始点vlから点ｖまでの経路上の辺のコストの最大値；
W(v1,v2)：辺(v1,v2)のコスト；
c(v){A}：経路Ａを経由した場合の始点vlから点ｖまでの経路上の辺のコストの
最大値；
bicmp(v)：点ｖが切断点であるかの判定；
【００１８】
＜アルゴリズム＞
begin
U：＝φ；
V：＝全ての点；
C(v1):＝0；
vl以外の各点ｖについてc(v):＝∞；
while U≠V do
begin
V−Uな点の中から，c(v)が最小の点vを選ぶ；
U：＝U∪{v}；
Bicmp(v)が１であれば切断点なので，V−Uに含まれる点のc(v)を全て∞に
変更する；
V−Uに含まれる点のうち，ｖに隣接している点uについて，
c(u):＝max{c(u), min{c(v),w{u,v}}；
end
end
【００１９】
次に、上記の切断点検出アルゴリズムおよび経路計算アルゴリズムの一実施例を図面により説明する。
図１に、本発明の実施形態におけるネットワーク構成を示す。ここで、３０，３６はリンクおよび中継装置を介してパケットを送受信する端末装置、３１，３２，３３，３４，３５は、リンクを介して端末装置と接続し、パケットの転送を行う中継装置、１０２，１０３，１０４，１０５，１０６，１０７，１０８，１０９はリンクを示す。端末装置３０より端末装置３６に宛てて送出されたパケットは、途中の中継装置およびリンクを経由して転送される。
【００２０】
最初に、図１のネットワーク構成における、切断点検出アルゴリズムの実施例を説明する。
図１のネットワーク構成において、端末装置３０をsとして切断点の探索を開始し、まず、端末装置３０にlabel(30)=1，lowpt(30)=1を割り当てる。次に端末装置３０に隣接する子である中継装置を探索対象とし、端末装置３０に隣接する２台の中継装置である中継装置３１と中継装置３２の中から、どちらか一方を検索対象とする。どちらを探索対象としても、最終的には、全ての中継装置が探索対象となり、切断点の検出に影響が無いので、以降では、複数の中継装置が探索対象となるときは番号の若い中継装置を探索対象とする。ここでは中継装置３１をvとして探索対象とする。中継装置３１はlabel(31)=0であるためまだ未探索であり、ゆえに、中継装置３１にlabel(31)=2，lowpt(31)=2を割り当て、中継装置３１に隣接する子である中継装置を探索する。同様にして中継装置３３，３４，３５の順にlabel値、lowpt値を割り当て、vおよびwを移動させていく（図２）。図２以降では、探索済みの中継装置のみを示している。
【００２１】
中継装置３５をvとしたとき、中継装置３５に隣接する子であるwとなる中継装置３３は、label(33)≠0でありすでに探索済みであるため、wが探索済みの場合の条件文を実行することになる。図２の値に基づき、次の計算を行う。label(33) < label(35)であるため、label(33)とlowpt(35)のうち小さい値をlowpt(35)とするが、label(33)=3でありlowpt(35)=6であるため、lowpt(35)=3となる。また、lowpt(33)とlabel(35)の値を比較すると、lowpt(33)=3，label(35)=6であり、lowpt(33)<label(35)であるため、bicmp(35)=0となる。計算後の値を図３に示す。変更した値に下線を付す。端末装置３６は中継装置３５の親であるため、vを端末装置３６とし、再び探索を行う。
【００２２】
端末装置３６においてwとなる中継装置３５は、label(35)≠0でありすでに探索済みであるため、wが探索済みの場合の条件文を実行することになる。図３の値に基づき、次の計算を行う。label(35) > label(36)であるため、lowpt(35)とlowpt(36)のうち小さい値をlowpt(36)とするが、lowpt(35)=3でありlowpt(36)=5であるため、lowpt(36)=3となる。また、lowpt(35)とlabel(36)の値を比較すると、lowpt(35)=3，label(36)=5であり、lowpt(35)<label(36)であるため、bicmp(36)=0となる。計算後の値を図４に示す。変更した値に下線を付す。端末装置３４は中継装置３６の親であるため、vを端末装置３４とし、再び探索を行う。
【００２３】
端末装置３４においてwとなる中継装置３６は、label(36)≠0でありすでに探索済みであるため、wが探索済みの場合の条件文を実行することになる。図４の値に基づき、次の計算を行う。label(36) > label(35)であるため、lowpt(36)とlowpt(34)のうち小さい値をlowpt(34)とするが、lowpt(36)=3でありlowpt(34)=4であるため、lowpt(34)=3となる。また、lowpt(36)とlabel(34)の値を比較すると、lowpt(36)=3，label(34)=4であり、lowpt(36)<label(34)であるため、bicmp(34)=0となる。計算後の値を図５に示す。変更した値に下線を付す。端末装置３３は中継装置３４の親であるため、vを端末装置３３とし、再び探索を行う。
【００２４】
端末装置３３においてwとなる中継装置３４は、label(34)≠0でありすでに探索済みであるため、wが探索済みの場合の条件文を実行することになる。図５の値に基づき、次の計算を行う。label(34) > label(33)であるため、lowpt(34)とlowpt(33)のうち小さい値をlowpt(33)とするが、lowpt(34)=3でありlowpt(33)=3であるため、lowpt(33)=3のままとなる。また、lowpt(34)とlabel(33)の値を比較すると、lowpt(34)=3，label(33)=3でありlowpt(34)≧label(33)であるため、bicmp(34)=1となる。計算後の値を図６に示す。変更した値に下線を付す。端末装置３２は中継装置３３の未探索である子であるため、wを中継装置３２とし、再び探索を行う。
【００２５】
中継装置３２はlabel(32)=0であるためまだ未探索であり、ゆえに、中継装置３２にlabel(32)=7，lowpt(32)=7を割り当て、中継装置３２に隣接する子である中継装置３０を探索する。計算後の値を図７に示す。
端末装置３２においてwとなる中継装置３０は、label(30)≠0でありすでに探索済みであるため、wが探索済みの場合の条件文を実行することになる。図７の値に基づき、次の計算を行う。label(32) > label(30)であるため、lowpt(32)とlowpt(30)のうち小さい値をlowpt(32)とするが、lowpt(32)=7でありlowpt(30)=1であるため、lowpt(32)=1となる。また、lowpt(30)とlabel(32)の値を比較すると、lowpt(30)=1，label(32)=7であり、lowpt(30)<label(32)であるため、bicmp(32)=0となる。計算後の値を図８に示す。変更した値に下線を付す。端末装置３３は中継装置３２の親であるため、vを端末装置３３とし、再び探索を行う。
【００２６】
端末装置３３においてwとなる中継装置３２は、label(32)≠0でありすでに探索済みであるため、wが探索済みの場合の条件文を実行することになる。図８の値に基づき、次の計算を行う。label(33) < label(32)であるため、lowpt(32)とlowpt(33)のうち小さい値をlowpt(33)とするが、lowpt(32)=1でありlowpt(33)=3であるため、lowpt(33)=1となる。また、lowpt(32)とlabel(33)の値を比較すると、lowpt(32)=1，label(33)=1であり、lowpt(32)≧label(33)であるが、bicmp(33)=1であるため、bicmp(33)は変更されない。計算後の値を図９に示す。変更した値に下線を付す。端末装置３１は中継装置３３の親であるため、vを端末装置３１とし、再び探索を行う。
【００２７】
端末装置３１においてwとなる中継装置３３は、label(33)≠0でありすでに探索済みであるため、wが探索済みの場合の条件文を実行することになる。図９の値に基づき、次の計算を行う。label(33) > label(31)であるため、lowpt(33)とlowpt(31)のうち小さい値をlowpt(31)とするが、lowpt(33)=1でありlowpt(31)=2であるため、lowpt(31)=1となる。また、lowpt(33)とlabel(31)の値を比較すると、lowpt(33)=1，label(31)=2であり、lowpt(33)<label(31)であるため、bicmp(31)=0となる。計算後の値を図10に示す。変更した値に下線を付す。端末装置３０は中継装置３１の親であるため、vを端末装置３０とし、再び探索を行う。
【００２８】
端末装置３０はsであり、v≠sの条件を満たさないため、計算は終了する。
以上により、中継装置３３に対するbicmp(v)値が１となり、中継装置３３が切断点であることが確定する。
【００２９】
次に、拡張ＭＩＮ−ＭＡＸアルゴリズムの実施例を示す。本実施例では、リンク帯域情報として表１を用いる。
【表１】
2005057658.tif 000003
【００３０】
ここでは、端末装置３０を発端未装置とし、端末装置３６を着端末装置とする経路を計算する。まず、ｖを端末装置３０とし、端末装置３０に隣接している中継装置を探索対象とする。
端末装置３０に隣接している中継装置３１と中継装置３２のどちらを先に探索しても結果が変わることはないが、ここでは、番号の若い中継装置３１を先に探索対象とする。
端末装置３０から中継装置３１へのリンクはリンク１０２であり、リンク１０２のコスト値は表1より３であるため、中継装置３１のc(v)は、c(31)＝３となる。中継装置３１のc(v)は全てのc(v)の中で最小であるため、端末装置３０から中継装置３１までの経路が確定する（図１２）。
【００３１】
次に中継装置３２を探索対象とする。端末装置３０から中継装置３２へのリンクはリンク１０３であり、リンク１０３のコスト値は表１より４であるため、中継装置３２のc(v)はc(32)＝４となる。中継装置３２のc(v)は、まだ経路が確定していない装置全てのc(v)の中で最小であるため、端末装置３０から中継装置３２までの経路が確定する（図１３）。
【００３２】
そして、次に中継装置３３を探索対象とする。端末装置３０から中継装置３３への経路の中で、中継装置３３に隣接している中継装置は、中継装置３１と中継装置３２である。中継装置３１のc(v)はc(31)＝3であり、中継装置３１と中継装置３３の間のリンクはリンク１０４で、コスト値は表１より７であるため、端末装置３０−中継装置３１−中継装置３３の経路の場合における最小のc(v)は３となる。一方、中継装置３２のc(v)はc(32)＝４であり、中継装置３２と中継装置３４との間のリンクはリンク１０５で、コスト値は表１より５であるため、端末装置３０−中継装置３２−中継装置３３の経路の場合における最小のc(v)は４となり、中継装置３２を経由した経路の方がc(v)が大きいため、中継装置３３のc(v)がc(33)＝４となり、端末装置３０から中継装置３３までの経路が、端末装置３０−中継装置３２−中継装置３３の経路のように確定する（図１４）。
【００３３】
そして、次に中継装置３３を起点として探索を開始する。
中継装置３３に隣接している中継装置は中継装置３４と中継装置３５であり、２つの中継装置のどちらを先に探索しても結果が変わることはないが、ここでは番号の若い中継装置３４を先に探索対象とする。
中継装置３３のc(v)はc(33)＝４であるが、bicmp(33)＝１であり、切断点であるため、中継装置３３のc(v)をc(33)＝∞とする。中継装置３３と中継装置３４との間のリンクはリンク１０６で、コスト値は表１より７であり、c(33)＝∞であるため、中継装置３４のc(v)はc(34)＝７となり、まだ経路が確定していない装置のc(v)の中で、中継装置３４のc(v)の値が最小であるため、端末装置３０から中継装置３４までの経路が確定する（図１５）。
【００３４】
次に中継装置３５を探索対象とする。中継装置３３と中継装置３５との間のリンクはリンク１０７で、コスト値は表１より６であり、c(33)＝∞であるため、中継装置３５のc(v)はc(35)＝６となり、まだ経路が確定していない装置のc(v)の中で、中継装置３５のc(v)の値が最小であるため、装置３０から中継装置３５までの経路が確定する（図１６）。
【００３５】
そして、次に端末装置３６を探索対象とする。
端末装置３６に隣接している中継装置は中継装置３４と中継装置３５であり、中継装置３４のc(v)はc(34)＝７であり、中継装置３４と端末装置３６との間のリンクはリンク１０８で、リンク１０８のコスト値は表１より８であるため、中継装置３４を経由した場合の端末装置３６のc(v)は７となる。
一方、中継装置３５のc(v)はc(35)＝６であり、中継装置３５と端末装置３６との間のリンクはリンク１０９で、リンク１０９のコスト値は表１より１０であるため、中継装置３５を経由した場合の端末装置３６のc(v)は６となる。そのため、中継装置３４を経由する経路のほうが端末装置３６のc(v)が大きくなるため、中継装置３４を経由する経路が選択され、端末装置３６のc(v)がc(36)＝７となり(図１７)、まだ経路が確定していない装置のc(v)の中で、端末装置３６のc(v)の値が最小であるため、端末装置３０から端末装置３６までの経路が、端末装置３０−中継装置３２−中継装置３３−中継装置３４−端末装置３６と確定する。そして、全ての装置が探索済みとなったため、探索を終了する。
【００３６】
拡張ＯＳＰＦを用いて、端末装置３０から端末装置３６までの経路を探索した場合、経路上のコストの合計値が大きい方の経路を選択するため、端末装置３０−中継装置３１−中継装置３３−中継装置３５−端末装置３６となる。その経路上での最小コストを持つリンクは、リンク１０２の３である。
一方、拡張ＭＩＮ−ＭＡＸアルゴリズムにより導出された経路は、端末装置３０−中継装置３３−中継装置３２−中継装置３４−端末装置３６となり、その経路上で最小コストを持つリンクはリンク１０３の４であるため、拡張ＭＩＮ−ＭＡＸアルゴリズムはリンク１０２でのボトルネックを回避することができる。
【００３７】
尚、実施の形態では、経路上のリンクのコストの最小値が最大となる経路を計算する方法について説明したが、経路上のリンクのコストの最大値が最小となる経路を計算することもでき、この場合には、前記ＭＩＮＩ−ＭＡＸアルゴリズムの「c(u):＝max{c(u), min{c(v),w{u,v}}」を「c(u):＝min{c(u), max{c(v),w{u,v}}」と置き換えればよい。
【００３８】
また、本発明の切断点検出方法および経路計算方法を実施する装置は、上記のアルゴリズムを実行するコンピュータにより実現することができ、本発明は上記のアルゴリズムをコンピュータに実行させるためのプログラムおよび該プログラムを記録した記録媒体も本発明の範囲に含むものである。
【図面の簡単な説明】
【００３９】
【図１】本発明の実施形態におけるネットワーク構成を示す図である。
【図２】本発明による切断点検出アルゴリズムの実施における探索の状態と各値を示す図である。
【図３】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図４】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図５】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図６】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図７】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図８】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図９】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図１０】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図１１】切断点を検出するアルゴリズムの実施における探索の状態と各値を示す図である。
【図１２】本発明による拡張ＭＩＮ−ＭＡＸアルゴリズムの実施における探索の状態と各値を示す図である。
【図１３】本発明による拡張ＭＩＮ−ＭＡＸアルゴリズムの実施における探索の状態と各値を示す図である。
【図１４】本発明による拡張ＭＩＮ−ＭＡＸアルゴリズムの実施における探索の状態と各値を示す図である。
【図１５】本発明による拡張ＭＩＮ−ＭＡＸアルゴリズムの実施における探索の状態と各値を示す図である。
【図１６】本発明による拡張ＭＩＮ−ＭＡＸアルゴリズムの実施における探索の状態と各値を示す図である。
【図１７】本発明による拡張ＭＩＮ−ＭＡＸアルゴリズムの実施における探索の状態と各値を示す図である。
【符号の説明】
【００４０】
３０，３６  端末装置
３１，３２，３３，３４，３５  中継装置
１０１，１０２，１０３，１０４，１０５，１０６，１０７，１０８，１０９  リンク
【図１】
2005057658.tif 000004
【図２】
2005057658.tif 000005
【図３】
2005057658.tif 000006
【図４】
2005057658.tif 000007
【図５】
2005057658.tif 000008
【図６】
2005057658.tif 000009
【図７】
2005057658.tif 000010
【図８】
2005057658.tif 000011
【図９】
2005057658.tif 000012
【図１０】
2005057658.tif 000013
【図１１】
2005057658.tif 000014
【図１２】
2005057658.tif 000015
【図１３】
2005057658.tif 000016
【図１４】
2005057658.tif 000017
【図１５】
2005057658.tif 000018
【図１６】
2005057658.tif 000019
【図１７】
2005057658.tif 000020