(57)【要約】【課題】  故障端で代用経路への切り替えを行う際に、故障復旧制御を行う範囲を最小限に抑える。【解決手段】  本発明は、故障復旧のための予備経路の計算の際に、計算対象現用区間[m,m+1]の計算のために、当該通信網のリンクを除いた通信網に存在する全てのリンクの重みの総和より大きな値を与えて迂回経路を計算し、計算結果が現用パスと他の区間を共有する場合には、その重なった部分を除去して計算対象区間[m,m+1]を含む区間の予備経路とする。【選択図】  図１
2005175593.tif 000002
【特許請求の範囲】
【請求項１】
ノード１〜k（k：正数）を通過する現用パスと該現用パスのノード間の区間［m,m+1］（１≦m＜k，m：整数）の故障に対しての予備リソースをそれぞれの区間毎に用意し、故障発生時に故障箇所に応じて故障復旧動作を行う通信網上のノード装置、または、該通信網を制御する装置が行う通信網における故障復旧経路探索方法において、
前記ノード装置の計算手段が、
故障復旧のための予備経路の計算の際に、計算対象現用区間[m，m+1]の計算のために、該計算対象現用区間のリンクを除いた通信網に存在する全てのリンクの重みの総和より大きな値を与えて迂回経路を計算する迂回経路計算過程と、
前記迂回経路の計算結果が前記現用パスと他の区間を共有する場合には、その重なった部分を除去して計算対象区間[m，m+1]を含む区間の予備経路とする予備経路決定過程と、からなることを特徴とする通信網における故障復旧経路探索方法。
【請求項２】
前記予備経路決定過程において、重なった部分を除去して得られた計算対象区間を含む区間について、再度前記迂回経路計算過程及び前記予備経路決定過程を行う請求項１記載の故障復旧経路探索方法。
【請求項３】
前記迂回経路計算過程において、
重み付き有向グラフの最短経路を求める手法を用いる請求項１記載の通信網における故障復旧経路探索方法。
【請求項４】
前記重み付き有向グラフの最短経路を求める手法として、ダイクストラ法を用いる請求項３記載の通信網における故障復旧経路探索方法。
【請求項５】
ノード１〜k(k:正数)を通過する現用パスと該現用パスのノード間の区間［m,m+1］（１≦m＜k,m：整数）の故障に対しての予備リソースをそれぞれの区間毎に用意し、故障発生時に故障箇所に応じて故障復旧動作を行う通信網上のノード装置、または、該通信網を制御する装置に実行させる故障復旧経路探索プログラムであって、
計算対象現用区間[m,m+1]の計算のために、該計算対象現用区間のリンクを除いた通信網に存在する全てのリンクの重みの総和より大きな値を入力する入力ステップと、
故障復旧のための予備経路の計算として、入力された値を用いて迂回経路を計算する計算ステップと、
前記計算ステップにおける迂回経路の計算結果が前記現用パスと他の区間を共有する場合には、その重なった部分を除去して計算対象区間[m,m+1]を含む区間の予備経路として出力する予備経路決定ステップと、をコンピュータに実行させることを特徴とする故障復旧経路探索プログラム。
【請求項６】
前記予備経路決定ステップにおいて、重なった部分を除去して得られた計算対象区間を含む区間について、再度前記迂回経路計算ステップ及び前記予備経路決定ステップを行う請求項５記載の故障復旧経路探索プログラム。
【請求項７】
前記迂回経路計算ステップにおいて、
重み付き有向グラフの最短経路を求める手法を用いる請求項５記載の故障復旧経路探索プログラム。
【請求項８】
前記迂回経路計算ステップにおいて、
前記重み付き有向グラフの最短経路を求める手法として、ダイクストラ法を用いる請求項７記載の故障復旧経路探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信網における故障復旧経路探索方法及び故障復旧経路探索プログラムに係り、特に、ノード１〜ｋ（ｋ：正数)を通過する現用パスと現用パスのノード間の区間[m,m+1](１≦m＜k、m：整数)の故障に対しての予備リソースをそれぞれの区間毎に用意し、故障発生時に故障箇所に応じて故障復旧動作を行う通信網における故障復旧経路を計算する、通信網における故障復旧経路探索方法及び故障復旧経路探索プログラムに関する。
【背景技術】
【０００２】
従来の故障復旧方法の形態は、主に次の２つに大別することができる。一つは、“パス端切り替え”と呼ばれるものであり、もうひとつは、“故障端切り替え”と呼ばれるものである。
【０００３】
パス端切り替え方法では、利用していた経路に故障が生じた場合、その経路の始点ノードから終点ノードまで、今まで利用していた経路と重ならない新しい経路に経路の切り替えを行う方法である(例えば、非特許文献１，２参照)。ここで、故障後に利用する新しい経路は、故障発生の前に、予備経路として予め決定される。
【０００４】
一方、故障端切り替えは、故障した部分だけ代用経路で復旧させ、その他の部分は元々利用していた経路をそのまま利用する方法である。これを実現する方法として、IPリルーティングがある。IPリルーティングを実現するプロトコルは、RIP Versｉon2, OSPFなどが考案されている(例えば、非特許文献３，４参照)。しかし、IPリルーティングは、故障が発生し、ネットワークトポロジが変化してから新しい経路を決定するもので、事前予約型のリストレーションは実現できず、それに適応する予備パス経路の計算方法も無い。
【０００５】
このように、従来の技術の中には、予備経路を事前予約でき、かつ、故障端で切り替えのリストレーションに対応できる技術はない。
【０００６】
ここでは、あるネットワーク上にパスを想定し、その一部分を代用できる経路を決定する方法を考える。
【０００７】
以下で想定するネットワーク及び、ネットワーク上のパスの持つ条件を次に示す。
【０００８】
（１）  ネットワークトポロジは、IDを持ったノードと、それらの間の辺(リンク)、さらに、リンクに付けられた重みを用いた有向ラベルグラフGで表す。
【０００９】
（２）  リンクに与えられる重みの値は必ず正の値である。
【００１０】
（３）  あるノードから他のあるノードへ向かうリンクが存在すれば、必ずその逆方向のリンクも存在する。また、そのような互いに逆向きで両端に持つノードが同じ出る２つのリンクに与えられる重みの値は等しいものとする。
【００１１】
（４）  グラフG上で、N個のノードとＮ−１本のリンクからなるパスPが与えられている(但し、N≧２)。
【００１２】
（５）  Pは始点(Ingressノード)と終点(Egressノード)を持つ枝分かれのない経路。
【００１３】
（６）  Pを構成するノードは、自分以外のPを構成する全てのノードのアドレスと全ての隣接関係を知っている。
【００１４】
（７）  Pは最適経路とは限らない。
【００１５】
（８）  PをIngressノードからEgressノードまで辿る時、k番目に現れるPの構成ノードをNODE[k]、k番目に現れるリンクをLINK[k]とする。
【００１６】
（９）  リンクの重みには通過する際のコストを与え、LINK[k]のコストをLINK_WEIGHT[k]とする。
【００１７】
（１０）  NODE[a]とNODE[b]間の最適経路をh[a,b]とし、そのコストをCOST[a,b]で表す。
【００１８】
（１１）  NODE[ｉ]は、次の情報を持つ。
【００１９】
・NODE[ｉ]に隣接しているノードの数DEG[ｉ]。
【００２０】
・NODE[ｉ]から隣接ノードADJ[ｉ,j]までのコスト。
【００２１】
ADJ_WEIGHT_OUT[ｉ,j](j=1〜DEG[ｉ])。
【００２２】
・隣接ノードADJ[ｉ,j]からNODE[ｉ]までのコストADJ_WEIGHT_IN[j,ｉ](j=1〜DEG[ｉ])。
【００２３】
このような条件を持つネットワークとパスの一例を図１６に、パスの表現方法を図１７に示す。ここで、LINK[1]〜LINK[N-1]のN-1本のリンクの代用経路ｓ[1]〜s[N-1]を決定したい。LINK[k]とs[ｋ]の関係を図１８に示す。
【発明の開示】
【発明が解決しようとする課題】
【００２４】
しかしながら、上記の従来の方法には次のような解決すべき課題がある。
【００２５】
パス端切り替えでは、予備経路の選択には、予備経路は元の経路と重なってはならないという制約、また、予備経路と元の経路は終点と始点を同じくしなければならないという制約が課せられる。このため、故障復旧の際に、故障と関係のない部分まで制御しなければならず、故障のない部分まで故障復旧の影響を受けるという問題点である。
【００２６】
また、故障端切り替えであるIPリルーティングでは、故障を検出してから代用経路を計算するため、故障から復旧までに長い時間を要するという問題点がある。
【００２７】
これらの問題は、故障端で代用経路への切り替えができ、かつ、代用経路を事前予約する方法により解決することができるが、このような方法はこれまでに実現されていない。その理由の一つとして、効率的な代用経路の計算方法が存在しなかったことが挙げられる。
【００２８】
本発明は、上記の点に鑑みなされたもので、故障端で代用経路への切り替えを行う際に、故障復旧制御を行う範囲を最小限に抑える代用経路の計算法を用いた通信網における故障復旧経路探索方法及び故障復旧経路探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２９】
図１は、本発明の原理を説明するための図である。
【００３０】
本発明は、ノード１〜k（k：正数）を通過する現用パスと該現用パスのノード間の区間［m，m+1］（１≦m＜k，m：整数）の故障に対しての予備リソースをそれぞれの区間毎に用意し、故障発生時に故障箇所に応じて故障復旧動作を行う通信網上のノード装置、または、該通信網を制御する装置が行う通信網における故障復旧経路探索方法において、
ノード装置の計算手段が、
故障復旧のための予備経路の計算の際に、計算対象現用区間[m，m+1]の計算のために、該計算対象現用区間のリンクを除いた通信網に存在する全てのリンクの重みの総和より大きな値を与えて迂回経路を計算する迂回経路計算過程（ステップ１）と、
迂回経路の計算結果が現用パスと他の区間を共有する場合には（ステップ２）、その重なった部分を除去して計算対象区間[m，m+1]を含む区間の予備経路とする予備経路決定過程（ステップ３）と、からなる。
【００３１】
また、本発明は、予備経路決定過程において、重なった部分を除去して得られた計算対象区間を含む区間について、再度迂回経路計算過程及び予備経路決定過程を行う。
【００３２】
また、本発明の迂回経路計算過程において、重み付き有向グラフの最短経路を求める手法を用いる。
【００３３】
また、本発明の重み付き有向グラフの最短経路を求める手法として、ダイクストラ法を用いる。
【００３４】
本発明は、ノード１〜k(k:正数)を通過する現用パスと該現用パスのノード間の区間［m，m+1］（１≦m＜k，m：整数）の故障に対しての予備リソースをそれぞれの区間毎に用意し、故障発生時に故障箇所に応じて故障復旧動作を行う通信網上のノード装置、または、該通信網を制御する装置に実行させる故障復旧経路探索プログラムであって、
計算対象現用区間[m，m+1]の計算のために、該計算対象現用区間のリンクを除いた通信網に存在する全てのリンクの重みの総和より大きな値を入力する入力ステップと、
故障復旧のための予備経路の計算として、入力された値を用いて迂回経路を計算する計算ステップと、
計算ステップにおける迂回経路の計算結果が現用パスと他の区間を共有する場合には、その重なった部分を除去して計算対象区間[m，m+1]を含む区間の予備経路として出力する予備経路決定ステップと、をコンピュータに実行させる。
【００３５】
また、本発明は、予備経路決定ステップにおいて、重なった部分を除去して得られた計算対象区間を含む区間について、再度迂回経路計算ステップ及び予備経路決定ステップを行わせる。
【００３６】
また、本発明の迂回経路計算ステップにおいて、重み付き有向グラフの最短経路を求める手法を用いる。
【００３７】
また、本発明の迂回経路計算ステップにおいて、重み付き有向グラフの最短経路を求める手法として、ダイクストラ法を用いる。
【発明の効果】
【００３８】
上記のように、本発明は、予備経路の計算結果に基づいて現用回線を除外して最短の迂回経路を求めることにより、故障復旧制御を行う範囲を少なくすることができる。
【発明を実施するための最良の形態】
【００３９】
以下、図面と共に、本発明の実施の形態を説明する。
【００４０】
最初に、本発明で利用するダイクストラ法の性質の中で必要となる条件は、２つのノード間で、リンクに与えられた重み(この場合はコスト)が最小となるような最適経路を求めることができ、最適経路を求めるためには、全てのノード、または、それらと結びつくリンクとその重み（正の値）を表した有向ラベルグラフが必要となる。
【００４１】
なお、以下の説明において、Ａ←Ｂは、Ａの値にＢの値を代入することを示す。また、MIN_DOWNの「DOWN」は、downstreamから、MIN_UPの「UP」は、upstreamからを意味する。
【００４２】
また、以下に示す動作は、通信網に接続されるノード装置（コンピュータ）上、または、当該通信網を管理する（または、監視する）システム上の装置（コンピュータ）で行われる。
【００４３】
［第１の実施の形態］
本実施の形態では、ＮＯＤＥ[k]とNODE[K+1]の間のLINK[k]を使わない場合に、そのリンクの代用として利用できる経路s[ｋ]を決定する。このような経路を見つける手順を以下に示す。
【００４４】
以下の（１）〜（３）の手順をｋ＝１〜Ｎ−１まで繰り返す。
【００４５】
手順（１）  LINK[k]のコストを∞にする。
【００４６】
手順（２）  LINK[k]の両端ノード、NODE[k],NODE[k+1]の間でのダイクストラ法などを用いて最短経路h[k,k+1]を求める。
【００４７】
手順（３）  最短経路が存在する場合はそれをs[k]←h[k,k+1]とし、ない場合には、s[k]の決定をスキップする。
【００４８】
以下に、上記の手順をフローチャートを用いて説明する。
【００４９】
図２は、本発明の第１の実施の形態における動作のフローチャートである。
【００５０】
ステップ１０１）  初期値として、ｋに１を代入する。
【００５１】
ステップ１０２）  LINK[k]のコストを∞にする。
【００５２】
ステップ１０３）  LINK[k]の両端ノード、NODE[k]、NODE[k+1]の間でのダイクストラ法などを用いて最短経路h[k,k+1]を求める。
【００５３】
ステップ１０４）  最短経路が存在する場合には、ステップ１０５に移行し、無い場合には、ステップ１０６に移行する。
【００５４】
ステップ１０５）  s[k]にh[k,k+1]を代入し、ステップ１０６に移行する。
【００５５】
ステップ１０６）  ｋがN-1になった場合には、処理を終了し、ならない場合には、ステップ１０７に移行する。
【００５６】
ステップ１０７）  ｋをインクリメントし、ステップ１０２に移行する。
【００５７】
上記により、その両端のノード間に、LINK[k]を通らない経路が存在する場合には代用経路を求めることができる。
【００５８】
［第２の実施の形態］
本実施の形態は、前述の第１の実施の形態を更に改善したものである。例えば、図３に示した例を考える。ここでは、簡単のため、双方向のリンクと重みを一本の線と一つの重みで表した。このネットワークで、NODE[k]からNODE[k+1]までのLINK[ｋ]の代用経路を第１の実施の形態の方法で求めると、図３に点線で示したように、NODE[k-1]を通過する経路が求まる。パスPのLINK[k]部分を、ここで求めたh’[k]で代用すると、代用してできた新しいパスP’には冗長部分ができてしまう。パスP’にとってNODE[k]→NODE[k−１]の部分は必要なく、取り除いても差し支えない。第１の実施の形態では、この冗長部分が生じることが避けられないが、本実施の形態では、このような冗長部分ができないように経路s[k]を選択することができる。
【００５９】
この方法で求まる経路s[k]の条件を以下に示す。
【００６０】
（条件１）  LINK[k]を使わない。
【００６１】
（条件２）  経路の始点と終端点は共に、P上のノードであり、s[k]の始点はNODE[k]または、NODE[k]よりIngress側のP上のノードで、終端点はNODE[k+1]または、NODE[k+1]より、Egress側のP上のノード。
【００６２】
（条件３）  始点と終端点以外に、P上のノードを通らない。
【００６３】
（条件４）  NODE[k]からNODE[k+1]の最短経路か、または、その一部分。
【００６４】
つまり、ここで求める経路s[k]は、NODE[k]から、NODE[k+１]からの最短経路h[k,k+1]を求め、h[k,k+1]をPに挿入したときにできる冗長な経路を取り除いたものになる。第１の実施の形態で求めたh’[k]の例を図４に、また、同様のネットワークにおいてこの方法で求めたs[k]の一例を図５に示す。
【００６５】
図５では、第１の実施の形態において選択された図４に示した経路からNODE[k]→Node-a→NODE[k+1]の部分が取り除かれている。
【００６６】
ｋ＝１，２…N-1について、LINK[k]の代用経路s[k]を求める手順を以下に示す。
【００６７】
以下の手順（１）〜（６）をｋ=１〜Ｎ−１について行うことでs[1],s[2],…,s[N-1]が求まる。
【００６８】
手順（１）  LINK[k]のコストLINK_WEIGHT[k]←∞とする。
【００６９】
手順（２）  NODE[k]からNODE[k+1]〜NODE「N」までの最短経路h[k,m](m＝k＋１〜N)と、h[ｋ,ｍ]のコストCOST[k,m](m=k+1〜N)をダイクストラ法により計算する。
【００７０】
ｉ．COST[k,k+1]=∞であるなら、s[k]の決定をスキップする。
【００７１】
ｉｉ．COST[k,k+1]≠∞ならば、手順（３）に移行する。
【００７２】
手順（３）  ｍ＝ｋ＋１〜ＮについてのCOST[k,m]の中の最小値MIN_DOWN[k]とMIN_DOWN[k]を与えるｍを求める。また、そのときのｍを、ｍMIN_DOWN[k]とする。
【００７３】
手順（４）  NODE[ｍMIN_DOWN[k]]からNODE[1]〜NODE[k-1]までの最短経路h[ｍMIN_DOWN[k],m]（ｍ＝１〜ｋ）と、その最短経路のコストCOST[mMIN_DOWN,[k],m](m=1〜k)をダイクストラ法により計算する。
【００７４】
手順（５）ｍ＝１〜kについてのCOST[m, MIN_DOWN[k]]を与えるmを求める。また、そのときのmをmMIN_UP[k]とする。
【００７５】
手順（６）  NODE[ｍMIN_UP[k]]を求め、s[k]←h[mMIN_UP[k],mMIN_DOWN[k]]とする。
【００７６】
上記の手順を以下にフローチャートを用いて説明する。
【００７７】
図６、図７は、本発明の第２の実施の形態における動作のフローチャートである。
【００７８】
ステップ２０１）  初期値としてkに１を代入する。
【００７９】
ステップ２０２）  LINK[k]のコストLINK_WEIGHT[k]←∞とする。
【００８０】
ステップ２０３）  MIN_UP←∞、mMIN_UP←k＋１、MIN_DOWN←∞、mMIN_DOWN←ｋとする。
【００８１】
ステップ２０４）  m←Nとする。
【００８２】
ステップ２０５）  ダイクストラ法により、最短経路h[ｋ,ｍ](ｍ=ｋ+1〜N)と、ｈ［ｋ，ｍ］のコストCOST[k，m](m＝k＋１〜N)を計算する。
【００８３】
ステップ２０６）  MIN＿UP記号COST[k，m]であるかを判定し、そうであるならステップ２０７に移行し、そうでない場合にはステップ２０８に移行する。
【００８４】
ステップ２０７）  MIN＿UP←COST[k，m]、ｍMIN_DOWN←ｍとする。
【００８５】
ステップ２０８）  ｍ←ｍ−１とする。
【００８６】
ステップ２０９）  ｍ＝ｋであれば、ステップ２１０に移行し、そうでなければステップ２０５に戻る。
【００８７】
ステップ２１０）  ダイクストラ法により、ｈ[mMIN_DOWN,m]と、COST[ｍMIN_DOWN,m]を求める。
【００８８】
ステップ２１１）  MIN_DOWN≧COST[mMIN_DOWN,m]であるかを判定し、そうである場合には、ステップ２１２に移行し、そうでない場合にはステップ２１３に移行する。
【００８９】
ステップ２１２）  MIN_DOWN←COST[mMIN_DOWN,m]、mMIN_UP←mとする。
【００９０】
ステップ２１３）  ｍ＝１である場合にはステップ２１５に移行し、そうでない場合には、ステップ２１４に移行する。
【００９１】
ステップ２１４）  ｍ←ｍ−１とし、ステップ２１０に移行する。
【００９２】
ステップ２１５）  COST[k,k+1]≠∞である場合にはステップ２１６に移行し、そうでない場合にはステップ２１９に移行する。
【００９３】
ステップ２１６）  ダイクストラ法により、h[mMIN_UP,mMIN_DOWN]を求める。
【００９４】
ステップ２１７）  s[k]←ｈ[mMIN_UP,mMIN_DOWN]とする。
【００９５】
ステップ２１８）  k＝N-1となったかを判定し、なった場合には、処理を終了し、ならない場合には、ステップ２１９に移行する。
【００９６】
ステップ２１９）  kをインクリメントし、ステップ２０２に移行する。
【００９７】
上記の手順（１）〜（６）までを詳細に説明する。
【００９８】
手順（１）  ダイクストラ法LINK_WEIGHT[k]←∞とすることは、h[k,m]を選択する際に、LINK[k]を用いないことを意図している。LINK[k]以外にNODE[k]で始まり、NODE[k+1]で終端する有限のコストの経路が一つでも存在するならば、ダイクストラ法でLINK[k]を含むh[k,m]が決定されることはない。
【００９９】
手順（２）  COST[k,k+1]＝∞であるなら、NODE[k]からNODE[k+1]への経路はLINK[k]ただ一つのみであることを現す。つまり、LINK[k]を通らないh[k,m]は存在しない。このような場合のネットワークの例を図８に示す。このような場合、s[k]となり得る経路は存在しないので、s[k]の決定をスキップする。なお、ここでは、リンクのコストは双方向で等しいので、COST[k,k+1]≠∞ならば、COST[k+1,k]≠∞が保証される。
【０１００】
手順（３）  h[k，k+1]がNODE［k］よりEgress側のNODE[p](ｉ+1≦p≦N)を通る場合、必ずCOST[k,k+1]≧COST[k,p]となる。ゆえに、h[k,k+1]をNODE[k]からNODE[k+1]まで辿るとき、NODE[k]よりEgress側のP上のノードの中で、一番初めに到達するものはNODE[mMIN_DOWN[k]]である。従って、mMIN_DOWN[k]＞ｋ＋１であれば、h[k,k+1]のNODE[mＭＩＮ_ＤＯＷＮ[ｋ]]からNODE[k+1]までの間にPと重複ノードが存在することがわかる。NODE[mＭＩＮ_ＤＯＷＮ[ｋ]]を代用経路の終点にすることによって、図４のような経路が選択されることを排除している。
【０１０１】
手順（４）  上記の（３）の説明と同様に、h[mMIN_DOWN[k],k]をNODE[mMIN_DOWN[k]]からNODE[k]まで辿るとき、一番初めに到達するNODE[k+1]よりIngress側のP上のノードはNODE[mMIN_UP[k]]である、従って、h[k,k+1]のNODE[k]から、NODE[mMIN_UP[k]]までの間にPと重複するノードが存在することがわかる。
【０１０２】
手順（５）  s[k]を決定する。
【０１０３】
本実施の形態の方法では、Pが最短経路に設定されていなかった場合、必要に応じて次のようなPの一部分を最短経路に再設定することができる。
【０１０４】
・NODE[ｍMIN_UP[k]]からNODE[k]まで。
【０１０５】
・NODE[k+1]からNODE[mMIN_DOWN[k]]まで。
【０１０６】
図５のネットワークのPをこのような方法で再設定した例を図９に示す。経路QがPを再設定することで得られたパスである。
【０１０７】
［第３の実施の形態］
本実施の形態は、代用経路の通過する範囲を限定できる点において、前述の第２の実施の形態と異なる。
【０１０８】
例えば、代用経路の始点をP上のNODE[a]に、代用経路の終端点をP上のNODE[b]に指定し、かつ、代用経路がその2つのノード以外には、P上のノードを通らないという制約を代用経路の選択時に課したとする。このとき、第１の実施の形態及び第２の実施の形態では、それぞれの過程でダイクストラ法を用いて求められるNODE[a]からNODE[b]までの最短経路が、このような制約を満たす経路の集合にたまたま含まれない限り、この制約を満たす経路が見つからない。このように、第１の実施の形態、第２の実施の形態でうまくいかない場合の具体例を図３に示す。要求を満たす経路はNODE[k]→NODE-a→NODE[k+1]であるが、この経路は、単純にダイクストラ法を用いる方法では求めることができない。単純にダイクストラ法を用いる方法では、コストが最小である経路はただ一つ見つかるが、その最短経路以外の経路の情報は、その経路が存在するかどうかということさえ分からないからである。
【０１０９】
本実施の形態では、この場合に、NODE[k]→Node-a→NODE[k+1]を代用経路として、選択することができる。図３の場合と同様な問題がEgress側で発生するネットワークの例を図４に示す。
【０１１０】
本実施の形態で求めるs[k]の条件は以下の通りである。
【０１１１】
（条件１）  経路の始点をNODE[ｉ]、終点をNODE[j]とした時、第２の実施の形態のs[k]の条件（１）〜（３）を満たす経路の中で、ｊ−ｉが最小の経路。
【０１１２】
（条件２）  第２の実施の形態のs[k]の条件（１）〜（４）を全て満たす経路の始点をNODE[ｉ]、終点をNODE[j]とする。経路P上のNODE[ｉ]からNODE[j]の部分を、第２の実施の形態のs[k]の条件（１）〜（４）を全て満たす経路で置き換え、新しいパスP’を作るとする。このとき、第２の実施の形態のs[k]の条件（１）〜（４）を満たす経路の中からダイクストラ法で選んだ経路P’のコストを最小にする経路。
【０１１３】
LINK[k]のｋ＝１，２，…N-1について代用経路s[k]を決定する手順を以下に示す。
【０１１４】
次の（１）〜（６）手順を、ｋ＝１〜Ｎ−１について行うことで、s[1],s[2],…s[N-1]が求まる。
【０１１５】
手順（１）  LINK[k]のコストLINK_WEIGHT[k]←∞とする。
【０１１６】
手順（２）  NODE[k]からNODE[k+1]まで最短経路ｈ[k,k+1]と、ｈ[k,k+1]のコストCOST[k,k+1]をダイクストラ法により計算する。
【０１１７】
ｉ．COST[k,k+1]=∞となり、ｈ[k,k+1]が存在しない場合はs[k]の決定をスキップし、手順（１０）に移行する。
【０１１８】
ｉｉ．COST[k,k+1]≠∞である場合は、手順（3）へ移行する。
【０１１９】
手順（３）  NODE[k]または、NODE[k]より、Ingress側のノードNODE[k-p](0≦ｐ≦k-1)と、NODE[k+1]または、NODE[k+1]より、Egress側のノードNODE[k+1+q](0≦ｑ≦N-k-1)を考え、Δ≡1+ｐ+ｑ（Δ＝１〜Ｎ−１）という変数Δを定義する。
【０１２０】
手順（４）  Δ=1から始め、Δ＝１からＮ−１まで、Δの小さい順に次の手順（５）〜（８）を行う。
【０１２１】
手順（５）  グラフＧにおいて、Ｐ上のノードNODE[1]〜NODE[N]へ向かうリンクの重みを全て無限大にしたグラフＧ’を考える。（これと反対向きにNODE[1]〜NODE[N]から、それらの隣接ノードへ向かうリンクは、重みを変化させない）。
【０１２２】
手順（６）  NODE[k-p]、NODE[k+1+q]へ向かうリンクの重みを、∞から最初のグラフＧと同じ値に戻す。
【０１２３】
手順（７）  手順（６）までのようにしてきたネットワーク上で、Δ=1+ｐ+ｑ（0≦ｐ≦ｋ−１，０≦ｑ≦Ｎ−ｋ−１）を満たす全てのｐ、ｑについて、
COST[k+1-Δ，k-p]+COST[k-p,k+1+q]+COST[k+1+q,Δ+1]
を求め、それをP’_COST[p,q]とする。
【０１２４】
手順（８）  Δ＝１＋ｐ＋ｑ（０≦ｐ≦ｋ−１，０≦ｑ≦Ｎ−ｋ−１）を満たすｐ、ｑについて、P’_COST[p,q]の最小値MIN[Δ]と、それを与えるｐ、ｑの値、p_MIN[Δ],q_MIN[Δ]を求める。
【０１２５】
ｉ．MIN[Δ]=∞であったら、Δ←Δ＋１として手順（４）へ戻る。
【０１２６】
ｉｉ．MIN[Δ]≠∞であったら、手順（９）へ移行する。
【０１２７】
手順（９）  s[k]←h[p,mｉn[Δ],q_mｉn[Δ]]として、手順（１０）へ移行する。
【０１２８】
手順（１０）  現在のｋについての計算を終了する。
【０１２９】
上記の手順を表すフローチャートを図１０、図１１に示す。
【０１３０】
ステップ３０１）  初期値としてｋに１を代入する。
【０１３１】
ステップ３０２）  LINK_COST[k]←∞とする。
【０１３２】
ステップ３０３）  ダイクストラ法により、h[k,m]とCOST[k,m]を求める。
【０１３３】
ステップ３０４）  COST[k,k+1]≠∞であればステップ３０５に移行し、そうでなければステップ３２７に移行する。
【０１３４】
ステップ３０５）  ｉ←１とする。
【０１３５】
ステップ３０６）  Δ←１とする。
【０１３６】
ステップ３０７）  ｐ←０、ｑ←Δ−ｐ−１とする。
【０１３７】
ステップ３０８）  ｊ=１，２…DEG[j]について、ADJ_WEIGHT_IN[j,ｉ]←∞とする。
【０１３８】
ステップ３０９）  ｉ＝Ｎであればステップ３１１に移行し、そうでなければステップ３１０に移行する。
【０１３９】
ステップ３１０）  ｉをインクリメントして、ステップ３０８に移行する。
【０１４０】
ステップ３１１）  ｊ=１，２，…DEG[k+p]について、ADJ_WEIGHT_IN[j,k+p]←ADJ_WEIGHT_OUT[k+p,j]とする。
【０１４１】
ステップ３１２）  ｊ=１，２，…DEG[k+1+q]について、ADJ_WEIGHT_IN[j,k+1+q
]←ADJ_WEIGHT_OUT[k+1+q,j]とする。
【０１４２】
ステップ３１３）  MIN[Δ]←∞とする。
【０１４３】
ステップ３１４）  h[k-p,k+1+q]，COST[k-p,k+1+q]を求める。
【０１４４】
ステップ３１５）  COST[k+1-Δ,k-p]+COST[k-p,k+1+q]+COST[k+1+q,Δ+1]を求め、これをP’_COST[p,q]とする。
【０１４５】
ステップ３１６）  MIN_[Δ]≧Ｐ’_COST[p,q]であれば、ステップ３１７に移行し、そうでなければステップ３１８に移行する。
【０１４６】
ステップ３１７）  MIN[Δ]≧P’_COST[p,q]とし、p_mｉn[Δ]←ｐ、q_mｉn[Δ]←ｑとする。
【０１４７】
ステップ３１８）  ｐ＝ｋ−１であれば、ステップ３２０に移行し、そうでなければステップ３１９に移行する。
【０１４８】
ステップ３１９）  ｑ←ｐ＋１、ｑ←ｑ−１とし、ステップ３０８に移行する。
【０１４９】
ステップ３２０）  MIN[Δ]≠∞であれば、ステップ３２２に移行し、そうでなければステップ３２１に移行する。
【０１５０】
ステップ３２１）  Δ←Δ＋１とし、ステップ３０７に移行する。
【０１５１】
ステップ３２２）  s[k]←h[p_mｉn[Δ],q_mｉn[Δ]]とする。
【０１５２】
ステップ３２３）  ｉ←１とする。
【０１５３】
ステップ３２４）  ｊ=１，２，…DEG[ｉ]について、ADJ_WEIGHT_IN[j,ｉ]←ADJ_WEIGHT[ｉ,j]とする。
【０１５４】
ステップ３２５）  ｉ＝Ｎとなれば、ステップ３２７に移行し、そうでなければ、ステップ３２６に移行する。
【０１５５】
ステップ３２６）  ｉ←ｉ＋１とし、ステップ３２４に移行する。
【０１５６】
ステップ３２７）  ｋ＝Ｎ−１となれば、処理を終了し、そうでなければ、ステップ３２８に移行する。
【０１５７】
ステップ３２８）  ｋ←ｋ＋１とし、ステップ３０２に移行する。
【０１５８】
上記のような各手順を詳細に説明する。
【０１５９】
手順（１）  前述の第２の実施の形態と同様に、LINK_WEIGHT[k]←∞とすることは、h[k,m]を選択する際に、LINK[k]を用いないことを意図している。LINK[k]以外にNODE[k]で始まり、NODE[k+1]で終端する有限のコストの経路が一つでも存在するならば、ダイクストラ法でLINK[k]を含むh[k,m]が決定されることはない。
【０１６０】
手順（２）  COST[k,k+1]＝−∞であるなら、NODE[k]からNODE[k+1]への経路は、LINK[k]ただ一つのみであることを表す。つまり、LINK[k]を通らないh[k,m]は存在しない。前述の第２の実施の形態の時と同様に、図８のような例がこの場合に当てはまる。
【０１６１】
手順（３）  経路の始点をNODE[ｉ]、終点をNODE[j]とした時、ｊ−ｉ=ΔとなるようにΔを定義する。
【０１６２】
手順（４）  Δの小さいものを優先的に求める。
【０１６３】
手順（５）  s[k]の始点と終端点とのあるノード以外は、Ｐ上のノードを通らないようにしたい。そのために、まず、全てのＰ上のノードへ向かうリンクの重みを∞にする。上記の手順（６）でs[k]の始点と終端点へ向かうリンクの重みを∞から元に戻す。
【０１６４】
手順（６）  隣接ノードからs[k]の始点と終端点までのコストを無限大の値から元の値に戻し、利用できるようにする。
【０１６５】
具体的には、始点ノードNODE[k+p]、終端点ノードNODE[k+1+q]から、隣接ノードまでの重み
ADJ_WEIGHT_OUT[k+p,j]（ｊ＝１〜DEG[ｉ]）、ADJ_WEIGHT_OUT[k+1+q,j]
を、隣接ノードからNODE[k+p]、NODE[k+1+q]までの重み、
ADJ_WEIGHT_IN[j,k+p]、ADJ_WEITHT_IN[j,k+1+q]
に代入する。重みは、双方向で等しいとしたので、
ADJ_WEITHT_OUT[k+p,j]（j=1〜DEG[ｉ]）、ADJ_WEIGHT_OUT[k+1+q,j]
の値から、元の重みを得ることができる。
【０１６６】
手順（７）  h[k-p,k+1+q]を、パスＰのNODE[k-p]〜NODE[k+1+q]の部分に挿入し、新しいパスＰ’を作ったとき、Ｐ’のコストが最小になるようにする。このように、COST[k+1-Δ,k-p]と、COST[k+1+q,Δ+1]を加えてコストを評価するのは、図１２のような、Δの等しい代用経路が存在するネットワークトポロジに対応するためである。図１２の場合、LINK[k]の代用経路として、ともにΔ＝２であるａとｂが存在する。代用経路のみで比較すれば、ａの方がｂより小さいコストを持つが、NODE[k-1]からNODE[k+2]までの経路で比較すると、ｂを通る経路の方が小さいコストを持つ。このような場合、最適な代用経路はｂである。
【０１６７】
手順（８）  現在のΔでは、求める経路が見つからない場合、Δを１大きくする。
【０１６８】
手順（９）  s[k]を決定する。
【０１６９】
第２の実施の形態と同様に、第３の実施の形態でも、Ｐが最短経路に設定されていなかった場合、必要に応じて次のようなＰの一部分を最短経路に再設定することができる。
【０１７０】
・NODE[k+1−Δ]からNODE[k-p]まで；
・NODE[k+1+q]からNODE[Δ＋１]まで；
図１２のネットワークでは、
・NODE[k-1]からNODE[k]；
・NODE[kp1]からNODE[k+2]；
までが、これに該当する。
【０１７１】
［第４の実施の形態］
本実施の形態は、s[k]をLINK[k]の代用としてＰに挿入して作られる経路に冗長部分がなく、かつ、代用経路を選択する際に、ホップ数が最小となる経路を選択するものである（第３の実施の形態が選択するのはコストが最小の経路）。ホップ数が最小となる経路の選択は、全てのリンクのコストを１としてダイクストラ法を用いることで実現する。
【０１７２】
本実施の形態における条件を以下に示す。
【０１７３】
（条件１）  前述の第２の実施の形態の条件（１）〜（４）を満たすもののうち、経路の始点をNODE[ｉ]、終点をNODE[j]としたとき、NODE[ｉ]からNODE[j]までの経路h[ｉ,j]のホップ数が最小となる経路：
次に、LINK[k]のｋ=１，２…Ｎ−１について代用経路s[k]を決定する手順を以下に示す。
【０１７４】
次の手順（１）〜（６）をｋ＝１〜Ｎ−１について行うことで、s[1],s[2],…s[N-1]が求まる。
【０１７５】
手順（１）  グラフＧの全てのリンクの重みを１とし、そのようにしてＧを変化させたグラフをＧ’とする。
【０１７６】
手順（２）  LINK[k]のコストLINK_WEIGHT[k]←∞とする。
【０１７７】
手順（３）  NODE[k]からNODE[k+1]まで最短経路h[k,k+1]と、h[k,k+1]のコストCOST[k,k+1]をダイクストラ法により計算する。
【０１７８】
ｉ．COSt[k,k+1]=∞となり、h[k,k+1]が存在しない場合はs[k]の決定をスキップし、手順（１２）へ移行する。
【０１７９】
ｉｉ．COST[k,k+1]≠∞である場合は手順（４）へ移行する。
【０１８０】
手順（４）  NODE[k]または、NODE[k]よりIngress側のノードNODE[k-p]（０≦ｐ≦ｋ−１）とし、NODE[k+1]または、NODE[k+1]よりEgress側のノードNODE[k+1+q]（０≦ｑ≦Ｎ−ｋ−１）を考え、Δ≡１＋ｐ＋ｑ（Δ＝１〜Ｎ−１）という変数Δを定義する。
【０１８１】
手順（５）  Δ＝１から始め、Δ＝１からＮ−１まで、Δの小さい順に次の手順（６）〜（９）を行う。
【０１８２】
手順（６）  グラフＧにおいて、Ｐ上のノードNODE[1]〜NODE[N]へ向かうリンクの重みを全て無限大にしたグラフＧ’を考える（これと反対向きにNODE[1]〜NODE[N]から、それらの隣接ノードへ向かうリンクは、重みを変化させない）。
【０１８３】
手順（７）  NODE[k-p]、NODE[k+1+q]へ向かうリンクの重みを、∞から最初のグラフＧと同じ値に戻す。
【０１８４】
手順（８）  手順（７）までのようにしてできたネットワーク上で、Δ＝１＋ｐ＋ｑ（０≦ｐ≦ｋ−１，０≦ｑ≦Ｎ−ｋ−１）を満たす全てのｐ、ｑについて、
COST[k+1-Δ,k-p]+COST[k-p,k+1+q]+COST[k+1+q,Δ+1]
を求め、それをP’_COST[p,q]とする。
【０１８５】
手順（９）  Δ＝１＋ｐ＋ｑ（０≦ｐ≦ｋ−１，０≦ｑ≦Ｎ−ｋ−１）を満たすｐ、ｑについて、P’_COST[p,q]の最小値MIN[Δ]と、それを与えるｐ、ｑの値、p_MIN[Δ],q_MIN[Δ]を求める。
【０１８６】
手順（１０）  Δ＝１からΔ＝Ｎ−１についてMIN[Δ]の最小値MIN’と、それを与えるΔ、p_MIN[Δ],q_MIN[Δ]の組、Δ’、ｐ’、ｑ’を求める。
【０１８７】
手順（１１）  s[k]←h[p’,q’]として手順（１０）へ戻る。
【０１８８】
手順（１２）  現在のｋについて計算を終了する。
【０１８９】
このような手順を表すフローチャートを図１３〜図１５に示す。
【０１９０】
ステップ４０１）  初期値として、ｋ←１とする。
【０１９１】
ステップ４０２）  初期値として、ｉ←１とする。
【０１９２】
ステップ４０３）  ｊ＝1，2…DEG[j]についてADJ_WEIGHT_IN[j,ｉ]←１とする。
【０１９３】
ステップ４０４）  ｉ＝Ｎであれば、ステップ４０６に移行し、そうでなければ、ステップ４０５に移行する。
【０１９４】
ステップ４０５）  ｉをインクリメントし、ステップ４０３に戻る。
【０１９５】
ステップ４０６）  LINK_COST[k]←∞とする。
【０１９６】
ステップ４０７）  ダイクストラ法により、h[k,m]とCOST[k,m]を求める。
【０１９７】
ステップ４０８）  COST[k,k+1]≠∞である場合には、ステップ４０９に移行し、そうでない場合には処理を終了する。
【０１９８】
ステップ４０９）  ｉ←１とする。
【０１９９】
ステップ４１０）  Δ←１とする。
【０２００】
ステップ４１１）  MIN’←∞とする。
【０２０１】
ステップ４１２）  ｐ←０、ｑ←Δ−ｐ−1とする。
【０２０２】
ステップ４１３）  ｊ＝１，２…DEG[ｉ]についてADJ_WEIGHT_IN[j,ｉ]←∞とする。
【０２０３】
ステップ４１４）  ｉ＝Ｎであれば、ステップ４１６に移行し、そうでなければ、ステップ４１５に移行する。
【０２０４】
ステップ４１５）  ｉをインクリメントし、ステップ４１３に戻る。
【０２０５】
ステップ４１６）  ｊ＝１，２…DEG[k+p]について、ADJ_WEIGHT_IN[j,k+p]←ADJ_WEIGHT_OUT[k+p,j]とする。
【０２０６】
ステップ４１７）  ｊ＝１，２…DEG[k+1+q]について、ADJ_WEIGHT_IN[j,k+1+q]←ADJ_WEIGHT_OUT[k+1+q,j]とする。
【０２０７】
ステップ４１８）  MIN[Δ]←∞とする。
【０２０８】
ステップ４１９）  h[k-p,k+1+q],COST[k-p,k+1+q]を求める。
【０２０９】
ステップ４２０）  COST[k+1-Δ,k-p]+COST[k-p,k+1+q]+COST[k+1+q,Δ+1]を求め、これをP’_COST[p,q]とする。
【０２１０】
ステップ４２１）  MIN[Δ]≧P’_COST[p,q]であるかを判定し、そうである場合にはステップ４２２に移行し、そうでない場合にはステップ４２３に移行する。
【０２１１】
ステップ４２２）  MIN[Δ]←P’_COST[p,q]、p_mｉn[Δ]←ｐ、q_mｉn[Δ]←ｑとする。
【０２１２】
ステップ４２３）  ｐ＝ｋ−１であるかを判定し、そうである場合にはステップ４２５に移行し、そうでない場合にはステップ４２４に移行する。
【０２１３】
ステップ４２４）  ｐ←ｐ＋１、ｑ←ｑ−１とし、ステップ４１３に戻る。
【０２１４】
ステップ４２５）  MIN’≧MIN[Δ]である場合には、ステップ４２６に移行し、そうでない場合には、ステップ４２７に移行する。
【０２１５】
ステップ４２６）  MIN’←MIN[Δ]、p’←p_mｉn[Δ]、q’←q_mｉn[Δ]とする。
【０２１６】
ステップ４２７）  Δ＝Ｎ−１であれば、ステップ４２９に移行し、そうでない場合にはステップ４２８に移行する。
【０２１７】
ステップ４２８）  Δ←Δ＋１とし、ステップ４１１に戻る。
【０２１８】
ステップ４２９）  s[k]←h[p’,q’]とする。
【０２１９】
ステップ４３０）  ｉ←１とする。
【０２２０】
ステップ４３１）  ｊ＝１，２…DEG[ｉ]についてADJ_WEIGHT_IN[j,ｉ]←１とする。
【０２２１】
ステップ４３２）  ｉ＝Ｎであれば、ステップ４３４に移行し、そうでない場合にはステップ４３３に移行する。
【０２２２】
ステップ４３３）  ｉをインクリメントし、ステップ４３１に戻る。
【０２２３】
ステップ４３４）  ｋ＝Ｎ−１であれば処理を終了し、そうでない場合には、ステップ４３５に移行する。
【０２２４】
ステップ４３５）  ｋをインクリメントし、ステップ４０２に戻る。
【０２２５】
上記の手順を詳細に説明する。
【０２２６】
手順（１）  全てのリンクの重みに１を与え、コストを計算することでホップ数を計算する。
【０２２７】
手順（２）  前述の第２、第３の実施の形態と同様に、COST[k,k+1]＝−∞であるなら、NODE[k]からNODE[k+1]への経路は、LINK[k]ただ一つのみであることを表す。つまり、LINK[k]を通らないh[k,m]は存在しない。前述の第２の実施の形態の時と同様に、図８のような例がこの場合に当てはまる。
【０２２８】
手順（３）  COST[k,k+1]=∞であるなら、NODE[k]からNODE[k+1]への経路はLINK[k]唯一つのみであることを表す。つまり、LINK[k]を通らないh[k,m]は存在しない。第２の実施の形態と同様に、図８のような例がこの場合に当てはまる。
【０２２９】
手順（４）  経路の始点をNODE[ｉ]、終点をNODE[j]としたとき、ｊ−ｉ＝ΔとなるようにΔを定義する。
【０２３０】
手順（５）  全てのΔについて、ホップ数が最小となるような代用経路を求める。
【０２３１】
手順（６）〜（９）前述の第３の実施の形態の（６）〜（９）の記載と同様である。
【０２３２】
手順（１０）  同じΔである代用経路の内、ホップ数が最小になるように定めたものから、さらに、全てのΔについてホップ数が最小になるものを求める。
【０２３３】
なお、上記において、はじめに与えられるパスは、最適経路とは限らないとしたが、最適経路が与えられている場合でも、同様の手順で同様の経路を決定することができる。
【０２３４】
また、上記で用いているダイクストラ法で求められる最適経路は、同じ道を２回以上通らず、また、ループを持たないものとする。
【０２３５】
また、上記の各実施の形態において、迂回経路を計算する手法として、ダイクストラ法を用いているが、この例に限定されることなく、重み付き有向グラフの最短経路を求められる方法であれば他の方法であってもよい。
【０２３６】
また、上記の各実施の形態における図２、図６〜図７、図１０〜図１１、図１３〜図１５に示すフローチャートの動作を、プログラムとして構築し、通信網上のノード装置、または、当該通信網を管理する装置として利用されるコンピュータにインストールし、ＣＰＵ等の制御手段により実行する、または、ネットワークを介して流通させることが可能である。
【０２３７】
また、構築されたプログラムを、通信網上のノード装置、または、当該通信網を管理する装置として利用されるコンピュータに接続される、ハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、本発明を実施する際にコンピュータにインストールすることも可能である。
【０２３８】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【産業上の利用可能性】
【０２３９】
本発明は、ネットワーク上のノードを通過する現用パスと、現用パスのノード間の区間の故障に対して予備リソースを用意し、故障箇所に応じて故障復旧処理を行うシステムに適用可能である。
【図面の簡単な説明】
【０２４０】
【図１】本発明の原理を説明するための図である。
【図２】本発明の第１の実施の形態における動作のフローチャートである。
【図３】本発明の第１の実施の形態でIngress側のノードでＰと重複する場合に選択する経路である。
【図４】本発明の第１の実施の形態でEgress側のノードでＰと重複する場合に選択する経路である。
【図５】本発明の第２の実施の形態で求めた経路s[k]の一例である。
【図６】本発明の第２の実施の形態における動作のフローチャート（その１）である。
【図７】本発明の第２の実施の形態における動作のフローチャート（その２）である。
【図８】本発明の第２の実施の形態における条件を満たす経路が存在しないネットワークの一例である。
【図９】本発明の第２の実施の形態におけるパスＰを再設定して得られたパスＱである。
【図１０】本発明の第３の実施の形態における動作のフローチャート（その１）である。
【図１１】本発明の第３の実施の形態における動作のフローチャート（その２）である。
【図１２】本発明の第３の実施の形態におけるΔの等しい代用経路が複数あるネットワークである。
【図１３】本発明の第４の実施の形態における動作のフローチャート（その１）である。
【図１４】本発明の第４の実施の形態における動作のフローチャート（その２）である。
【図１５】本発明の第４の実施の形態における動作のフローチャート（その３）である。
【図１６】ネットワークとパスの一例である。
【図１７】パスの表現法である。
【図１８】LINK[k]と経路s[k]の関係である。
【図１】
2005175593.tif 000003
【図２】
2005175593.tif 000004
【図３】
2005175593.tif 000005
【図４】
2005175593.tif 000006
【図５】
2005175593.tif 000007
【図６】
2005175593.tif 000008
【図７】
2005175593.tif 000009
【図８】
2005175593.tif 000010
【図９】
2005175593.tif 000011
【図１０】
2005175593.tif 000012
【図１１】
2005175593.tif 000013
【図１２】
2005175593.tif 000014
【図１３】
2005175593.tif 000015
【図１４】
2005175593.tif 000016
【図１５】
2005175593.tif 000017
【図１６】
2005175593.tif 000018
【図１７】
2005175593.tif 000019
【図１８】
2005175593.tif 000020