(57)【要約】電気通信網におけるルーティングを実行するために、ネットワークを仕切り、前処理段階において、装置の特性で決定される接続を使用することにより、簡易グラフをパーティションに作成し、ネットワークの双対グラフを構成する方法を提案する。そして変換されたグラフでルーティングが実行される。また、その整合性を保つグラフ更新技術が説明される。ルーティングがまだ考慮されていなかったトラフィックを要求されるごとに、そのトラフィックのための簡易グラフが作成されると同時に、そのトラフィックをサポートしないオリジナルのグラフのアークは削除される。上述のグラフ分割により展開される縮小グラフのみがメモリに記憶されることにより、著しい省資源化が達成される。
2004535140.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの双対グラフを構成し、装置の特性によって制約された接続を使用することによって該グラフを簡易化する前処理段階において、ネットワークのグラフＧを仕切り、パーティションＰiに簡易グラフＧRを作成し、ルーティングが変換されたグラフで実行される、電気通信網におけるルーティング方法。
【請求項２】
簡易グラフのみがメモリに記憶されることを特徴とする請求項１記載の方法。
【請求項３】
簡易グラフＧRを構築するために、
簡易グラフＧRのノードnfをオリジナルのグラフの各インターリンクに割り当てる；
各パーティションＰiに対し、ポートセットを入力ポートと出力ポートに分割し、Ｐiレベルではパラグラフ１に従い作成された、パーティションＰiのポート（インターリンク）を表す、関連ポートの方向に依存して入力ノードnfiあるいは出力ノードnfuとなるそれぞれの仮想ノードnfが関連する；
オリジナルのグラフで問題のポートに接続されるノードに、仮想nfiノードあるいは仮想nfuノードを接続し；二度同じコストを数えるのを避けるために、始点にノードnfuを持つアーチにコスト0を割り当て、ノードnfiの終点のアーチのコストはｃinの値を保つ；
各仮想ノードnfiから各仮想出力ノードnfuまでの最短経路を計算し；各経路は＜入力ポート、出力ポート＞のノードセットに接するオリジナルのグラフのアーチのセットによって特徴付けられる；
前ポイントに従い計算される空ではないアーチの1セットから成る経路があり、２つのポートを表すノードnfを接続する、簡易グラフｍrの中にあるアーチはこれらの経路それぞれに関連し；２個の仮想ノードの間の経路が存在していない場合、この経路に関連しているアーチのセットは空集合であり、この場合簡易グラフにアーチが挿入されることはない；
というステップから成る請求項１記載の方法。
【請求項４】
簡易グラフのそれぞれのアーチｍrに対し、
オリジナルのグラフで仮想ノードnfiおよびnfuに関連しているポートを接続する経路により横断されるオリジナルのグラフのアーチのリスト「L」と；
経路を介してオリジナルのグラフで横断されるアーチのコストの合計と等しいコストと；
経路が計算されたパーティションの名前；
が関連する請求項３記載の方法。
【請求項５】
座標＜ソースノードns、ソースパーティションＰS＞、＜宛先ノードnd 宛先パーティションＰd＞で特定される一組のノードに対する接続要求Ｒが到達したとき、オリジナルのグラフのソースノードと宛先ノードを簡易グラフに追加する；
組＜nS，ＰS＞に対し、データベースからソースパーティションだけのデータをすべて取り；ソースノードからソースパーティションのすべての出力ポートまでの最短経路を計算し；各経路は、上記パラグラフで説明されるように計算され、簡易グラフのほかのアーチと同じデータ（ソースパーティションで横断されたアーチのリスト、総コスト、及びソースパーティションの名前）を含むアーチに関連する；
組＜ｎd，Ｐd＞に対して、データベースから宛先パーティションのデータを取り；宛先パーティションのすべての入力ポートから宛先ノードまでの最短経路を計算し；各経路は、上記パラグラフで説明されるように計算され、簡易グラフの他のアーチと同じデータを含むアーチに関連する；
というステップが実行される請求項１記載の方法。
【請求項６】
ネットワークあるいはサブネットワークの装置が少なくとも以下の3つのクラス；
装置A：いかなる入力ポートもいかなる出力ポートに接続することができる；
装置B：いかなる入力ポートもいかなる出力ポートに接続することができる、入出力ポートで構成されたセットが少なくとも1セット存在する；
装置C：各入力ポートに、考慮されるべきすべての接続制約がある；
に分割されている、双対グラフの作成のための請求項１記載の方法。
【請求項７】
変換されたグラフの仮想ノードＮｆがタイプA及びBの装置に関連し、変換されたグラフの別の仮想ノードLｆが、終点あるいは始点に接続制約付ポートを持つ各リンクに関連する請求項６記載の方法。
【請求項８】
オリジナルのタイプAノードに対する変換されたグラフのそれぞれの仮想ノードＮｆに関し；
パラグラフ3に従いLｆが作成したそれぞれの仮想ノードに関して、ＬｆのオリジナルのアーチがＮｆのオリジナルのノードに入力された場合、ＮｆをＬｆに接続するリンクを挿入する；
パラグラフ3に従いＬｆが作成したそれぞれの仮想ノードに関して、ＬｆのオリジナルのアーチがＮｆのオリジナルのノードに出力された場合、ＮｆをＬｆに接続するコストのないリンクを挿入する；
オリジナルのグラフで、始点あるいは終点としてのＮｆのノードを持つ、既述の変換を受けていないアーチを考慮し、各アーチに関してＮｆはもう片方の仮想ノードに接続され、このノードはオリジナルのグラフの終点あるいは始点ノードに関連し、オリジナルのグラフのアーチと同じコストを保つ；
請求項７記載の方法。
【請求項９】
タイプBのオリジナルノードに対する変換されたグラフのそれぞれの仮想ノードＮｆに対し、
制約付のポートの入力または出力でオリジナルのグラフのアーチに対して作成された仮想ノードＬｆinまたはＬｆoutを検討し、仮想ノードＮｆのノード及び前記仮想ノードＬｆinに対するノードへのあるいはそのノードから、仮想ノードＬｆinを結合するリンクを他の仮想ノードＬｆoutに挿入し；この場合、この結合は、仮想ノードの組Ｌｆin、Ｌｆoutに対してだけに行い、またこれらの組はオリジナルのグラフのアーチの結合可能な組に対応しなければならず；
制約なしのポートの入力または出力におけるオリジナルのグラフのアーチに対して作成されたすべての仮想ノードの組ＬｆinまたはＬｆoutを検討し、仮想ノードＮｆに対する及び前記仮想ノードＬｆinに対するノードへあるいはそのノードから、Ｌｆinで表示されるオリジナルアーチのコストを維持しつつ、仮想ノードＬｆinを結合するリンクを他の仮想ノードＬｆoutに挿入し、これらの仮想ノードＬｆoutの各々に対して、仮想ノードＮｆをゼロコストで結合するリンクを前記仮想ノードＬｆoutに挿入し:
前記変換を受けていないオリジナルのグラフの始点あるいは終点ノードＮｆを持つアーチを検討し；各アーチに対して、オリジナルのグラフのアーチと同じコストを維持しながら前記仮想ノードＮｆをオリジナルのグラフの終点あるいは始点ノードに関連する他方の仮想ノードに接続する；
ことを特徴とする請求項７記載の方法。
【請求項１０】
オリジナルのタイプCノードに関連した変換されたグラフの各仮想ノードＮｆに関し；
Ｎｆで表されるノードへのあるいはそのノードからの制約があり、入力ポートあるいは出力ポートに制約付で存在する、作成されたすべての仮想ノードＬｆinあるいはＬｆoutがオリジナルのグラフのアーチに関連している場合、オリジナルのグラフで結合可能な２つのアーチを表すすべての組Ｌｆin、Ｌｆoutにアーチを挿入する請求項７記載の方法。
【請求項１１】
簡易グラフの動的補完のために、
ソースノードあるいは宛先ノードがタイプCである場合、仮想ノードを加える；
ソースノードがタイプAあるいはタイプBである場合、変換されたネットワークのノードは直接作成される；
というステップが、ソースパーティションあるいは宛先パーティションに対するグラフの作成中に実行される請求項６記載の方法。
【請求項１２】
簡易グラフの動的補完のために、ソースノードｎSに関し、
ｎSがタイプAである場合、処理は実行されない；
ｎSがタイプBである場合、変換されたグラフのｎSを表す仮想ノードと各出力ポートのリンクを表す仮想ノードの間に接続制約付でアーチを加える；
ｎSがタイプCである場合、変換されたグラフのｎSを表す仮想ノードと、各出力ポートのリンクを表す仮想ノードの間にアーチを加える；
というステップが実行される請求項６記載の方法。
【請求項１３】
簡易グラフの動的補完のために、宛先ノードｎdに関し、
ｎdがタイプAである場合、処理は実行されない；
ｎdがタイプBである場合、変換されたグラフのｎdを表す仮想ノードと各入力ポートのリンクを表す仮想ノードの間に、接続制約付でアーチを加える；
ｎdがタイプCである場合、変換されたグラフのｎdを表す仮想ノードと各出力ポートのリンクを表す仮想ノードの間に、アーチを加える；
というステップが実行される請求項６記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信網において、特に同期デジタルハイアラーキ（ＳＤＨ）か波長分割多重方式（ＷＤＭ）の電気通信網において最適経路(ルーティング)を素早く効率的に見つける方法に関するものである。
【背景技術】
【０００２】
急速に広がっている電気通信サービスと装置が複雑なために、効率的で優れた性能をもつルーティングアルゴリズムの設計と実装において、重大な問題が残されている。
【０００３】
ネットワーク構築において、現在ある同期デジタルハイアラーキか波長分割多重方式装置では、必ずしも最短経路を計算をすることに重点をおいていないので、ネットワークに関するすべてのデータをネットワークの完全な視野を持つ唯一のデータベースに記憶させている。したがって、この集中型アーキテクチャにおいて、最短経路の計算とデータルーティングのために、データアルゴリズムを使う時には、データベースからネットワークの現況を説明するルーティングをロードする必要がある。
【０００４】
特に、電気通信網の現在のサイズやますます増大していく傾向を考えると、これは大きな問題である。実際に、現代のネットワークは何千もの装置が、同数のリンクに接続されており、現在の成長率から考えても、短期間に何万にも増加しさほど遠くない将来には、何十万の数に達するであろう。最短経路の計算をする度に、このように大量のデータを取り出すには、大掛かりな取り組みが必要で、応答時間が長くかかる事は既に明らかである。データベースへのアーチセスは、時間の観点からすると実に費用のかかる操作である。アーチセスする時間は実際に計算にかかる時間よりもはるかに長い。
【０００５】
データベースのすべてのデータをロードするために、大量のメモリが必要であることを忘れてはならない。
【０００６】
さらに、ネットワークメンバのルーティングの制約により、結果の帰納的検証が出来ない場合もあるので、探索アルゴリズムを繰り返し行う必要がある。
より少ないメモリ(より小さいグラフ)を使い、より速いルーティング・アルゴリズムを確保するために、ネットワークを仕切る策が提案された。しかし仕切るだけでは問題の一部の解決にしかならない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は上記の短所を克服して、ネットワークの装置とリンクの増加にあわせて、ネットワークを形成する装置の接続の制限を考慮した最適経路をたどる効率的な通信ネットワークの方法を確立することである。
【課題を解決するための手段】
【０００８】
この目的にあわせて通信ネットワークのルーティング方法をかいた発明は、ネットワークのグラフGを仕切りパーティションPi上に簡易化したグラフGRを作成しネットワークの2つのグラフを作成する前処理段階と、装置の特徴のため制限される接続方法で、グラフを簡易化して変換されたグラフ上でルーティングを行う方法である。
【発明を実施するための最良の形態】
【０００９】
従来の技術と比べて、本発明の革新的な原則と利点を明確にするために、付加の図面を使い例を限定しないで、発明で体現できることを示した。
【００１０】
図1はネットワークの包括的な例を示す。これは一定のパーティションまたは管理しやすいサブネットワークを確保するために仕分けした最初のネットワークである。以下の申し合わせ事項がある。
【００１１】
１．ネットワークの各装置は複数の装置を含む一つのパーティションに属す。これは、１つのパーティションに属す装置のセットと無作為に選ばれた別のパーティションに属すそれらのセットの間の交差点が空集合であることを含む。
２．１つのパーティションは他のパーティションを含んでいない。そのためネットワークの仕切りはただ一つの分離レベルで行われる。
３．ネットワークのオリジナルのリンクは以下として分類される。
インターリンク；これらのリンクは２つのパーティションに属す2台の装置を連結する。＜ソースノード、ソースパーティション＞と＜宛先ノード、宛先パーティション＞の特徴を有する連結である。
イントラリンクこれらのリンクは同じパーティションに属す2台の装置を連結する。イントラリンクは＜ソースノード、宛先ノードとパーティション＞の３つのデータの特色をもつ。
４．インターリンクとイントラリンクを同時に分類することはできない。
５．接続するパーティションのために、それぞれのインターリンクはトラフィックがながれるポートを構成する。ポートの中を実際に流れるトラフィックはソースパーティションと宛先パーティションと同じ方向に流れる。
【００１２】
上記の理由で、同じリンクがソースパーティションの出力ポートと宛先ポートの入力ポートの役割をはたす。
【００１３】
Nノード(装置)のグラフとMアーチ(arches)(リンク(links))と費用関数C(M)で示したネットワークの仕切りを確保するために、パーティションPのセットを定義し、オリジナルのグラフにパーティションＰi，ｎiノードとｍiアーチを割り当てる。その時にはアーチ、終点、始点ノードがＰi(イントラリンク)に属している方法でなければならない。２つの異なるパーティションに属する(i,j)ノードをもつ残りのｍkアーチはインターリンクである。
【００１４】
パーティションＰはオリジナルのグラフのｍkアーチ(インターリンク)を通して接続している。
【００１５】
規則(1)と(2)を適用すると、次のようになる。
2004535140.tif 000003
【００１６】
図１は、私たちがオリジナルのネットワークと呼ぶ可能なネットワークの例を示す。
図２はこのネットワークをA、B、Ｃ、３つのサブネットワークに仕切る方法を示す。（可能なパーティションと呼ぶ可能なネットワークに関する例で、）仕切りのネットワークのサイズが増加する場合、サブネットワークのサイズが過度になることがデータ管理の問題となる。一方で、ネットワークの仕切りは過度の断片化を避ける必要があるため結果として分割のパーティション数が過度になるという限界がある。
【００１７】
サブネットワークとネットワークのオリジナルのグラフの完全なコピーを記憶させないで、ネットワークの現況をまとめる基礎データのアセンブリッジを記憶する方法をさがし、ネットワークを表す全てのデータをロードするのを避ける事が望まれる。
【００１８】
したがって、本発明によると、簡易グラフGはオリジナルのネットワークのグラフGRから抜粋したものである。
【００１９】
この簡易グラフを作図するために、以下の方法を取る。
１．簡易グラフＧRにおけるノードｎfをオリジナルのグラフの各インターリンクに割り当てる。
２．パーティションＰiに関してはポートを２つの入出力のポートのセットに分割する。
パーティションＰiレベルでポート(インターリンク)を表すパラグラフの下で作成した仮想ノードｎfと、ポートの方向によって仮想入力ノードｎfiか出力ノードｎfuになる仮想ノードを結合させる。
オリジナルのグラフで仮想ノードのｎfiかｎfuを問題のポートに接続されるノードに接続する。同じコストを2度数えないために、コスト０を始点としてノードｎfuを持っているアーチに割り当てる。
終点としてノードｎfiを持っているアーチのコストはｃinであり変更しない。
それぞれの仮想入力ノードｎfiからそれぞれの仮想出力ノードｎfuまで最短経路を計算する。各経路は<入力ポート、出力ポート>のノードを接続するオリジナルのグラフのアーチのセットによって特徴付けられる。
３．パラグラフ２でアーチセットは、簡易グラフｍrでアーチを計算し、２つのポートを表すノードｎfをこのアーチで接続している。２個の仮想ノードの経路が存在せず、その結果、前述の経路に関連しているアーチのセットが空集合の場合、アーチを簡易グラフに挿入してはならない。
４．次のデータは簡易グラフのｍrのアーチと関わりがある。
オリジナルのグラフでｎfiとｎfuという仮想ノードのためのポートを接続する。
経路を書いたリストＬコスト。
オリジナルグラフに経路がかかれたアーチの総コスト
経路を計算したパーティションの名前
（ＧR（Ｐi））はＧRアーチのセットとして定義され、ＬアーチのリストはパーティシンＰiの中で計算された。同様に（ＧR（Ｐi））はパーティション分野がＰiであるＧRのアーチのセットを表す。
【００２０】
図３は図１のパーティションＡのための架空のノードの追加を表す。図４は、上記の方法で作成されるオリジナルのパーティションＡを表す縮小簡易グラフである。
【００２１】
簡易グラフの構造を理解するためと、イラストを複雑にしないために、アーチのコストは数字に挿入されなかった。
【００２２】
例えばポート７，６からポート５，１４までの最短経路は{7,6;6,3;4,5;5,14}と推測する。縮小したGR(７,６,５,４)のアーチと関連したデータは、次のようになる。
１．リストＬ：L=｛＜7,6;6＞,＜6;3＞,＜3;4＞,＜4;5＞,＜5;5,14＞｝
２．この経路の総コスト
３．パーティションの名前Ａ
再び明確にするために、アーチを関連終点と始点ノードの識別子として割り当て、一連のアーチの経路を指定する。
【００２３】
もちろん、同じ方向で同じノードのペアと接続する１つ以上のアーチがあれば、この方法は適用されない。この例を理解するために、異なるパーティションのノードに違う名前をつける方法もある。実際は、装置は名前、パーティションや価値で区別するので、２つの異なるパーティションに属する装置が同じ名前をもつことは可能である。
【００２４】
接続要求Rが座標＜ソースノードｎS、ソースパーティションＰS＞や＜宛先ノードｎd、宛先パーティションＰd＞に達する時、下記の方法で簡易グラフを作成する必要がある。
１．簡易グラフにオリジナルのソースと宛先ノードを加える。
２．＜ｎS，ＰS＞のためにソースパーティションのためにデータベースから必要なデータだけを取りだす。
ソースノードからソースパーティションのすべての出力ポートまでの最短経路を計算する。
上のパラグラフで計算された経路と同じデータをもつアーチと(ソースパーティションに横断するアーチのリスト、総コスト、ソースパーティションの名前が入った)簡易グラフの他のアーチを関連させる。
3．＜ｎd，Ｐd＞について宛先パーティションのために、必要なデータだけを取り出す。
宛先パーティションのすべての入力ポートから宛先ノードまで最短経路を計算する。
先行のパラグラフの下で計算された経路と簡易グラフのアーチと同じデータを持つアーチを関連させる。(宛先パーティションを横断するアーチのリスト、総コスト、宛先パーティションの名前を含む)簡易グラフ
【００２５】
図５は簡易グラフの動的補完に関する例を示す。この動的補完は図４のＧRに適用され、パーティションA(＜1、A＞)のノード1からパーティションC(＜8、C＞)のノード8までの経路の計算のため必要となる。
簡易グラフが完成した時に、グラフ上で操作して直接最短経路を計算できる。
簡易グラフＧRのアーチ(＜ｎfi，ｎfu)の順序付きリストを発見できる。
簡易グラフリストの各メンバのアーチｍrはオリジナルグラフのアーチリストと関連があり、仮想ノードのｎfiとｎfuで関連する２つのポートの間を最短経路によって横断する。
簡易グラフのアーチの順序によるリストの線形化と、インターリンクのアーチの反復を避けることが最後の解決策である。
【００２６】
以下を仮定した例をあげてみる。図５の簡易グラフで計算されたパーティションA(＜1、A＞)のノード1からパーティションC(＜8、C＞)のノード8までの最短経路は、図６で見られるものと同じである。
【００２７】
図６に、簡易グラフの３つのアーチ、すなわち簡易グラフで動的補完する間、簡易グラフに追加されたアーチ＜1,A;5,14＞とアーチ＜12,11;8,C＞、そして簡易グラフの構築の間導入されたアーチ＜5,14,12,11＞の３つのーケンスから成る最短経路を示す。
以下のデータが3つのアーチと関連すると仮定する。
【００２８】
2004535140.tif 000004
オリジナルのグラフのノード1からノード8までの最短経路のコストは、３つのアーチの総コストと等しく、この合計はｃtot=ｃ1+ｃ2+ｃ3=23の数式で表される。
【００２９】
この最短経路はアーチの以下の分類順序で作られる:
経路={＜1;2＞＜2;5＞＜5;14＞＜14;15＞,＜15;16＞,＜16;12＞,＜12;11＞,＜11;10＞、＜10;7＞,＜7、8＞}
オリジナルグラフのノード1からノード8まで経路が見つけて図7で示した。
【００３０】
最適経路を計算するためのルーティング方法が提案され、図８に示したように、同じパーティションを最適経路が数回通る特別な場合にも活用できる。
【００３１】
ソースと宛先ノードが同じパーティションに属する状況で最短経路を計算する能力が大変重要になってくる。この場合、２個のノードを含んでいるパーティションに関連するすべてのデータをロードして、最初に簡易グラフを使用せずに２つのノード間の最短経路を計算する時に効果があるかもしれない。
【００３２】
このように計算された経路は他のパーティションを通り、２つのノードを含む他のパーティションに戻る最適経路ではないかもしれないが、一般に経路を作るリンクの数が制限されているので、接続を作成する問題における有効な解決策となる。パーティションの中の経路が存在していないのでこの最初の試みが失敗しても、オリジナルのネットワークに存在しないということではない。
ここから経路が見つけられなかったなら、全体の簡易グラフにおいて計算し、一般的な事例にある本発明に従うだけで十分である。
【００３３】
簡易グラフにおける最短経路の計算に関して、以下の接続の計算をする前であればいつでも、簡易グラフのソースノード、宛先ノード、および関連ノードをキャンセルできる。新しい接続要求がある場合のみキャンセルする利点があるかもしれない。新しいソースノードまたは宛先ノードが前のソースノードまたは宛先ノードと一致する場合に前のデータを再利用できる。
もちろん、前に接続した後の計算での後で一貫性がないリンクになった場合は、更新する必要がある。
【００３４】
解決策を用いた時にオリジナルのグラフと簡易グラフが一致していることが一般的に必要である。簡易グラフはいつもネットワークの現状をまとめたものでなければならない。
【００３５】
一貫性問題を生み出す他の状況がある。主なものは、既に割り当てられたソースを使い、接続をリリースし、パーティションの中に新しいノードやリンクを挿入したり、パーティションの中のノードやリンクをキャンセルしたり、インターリンクを挿入したり、キャンセルする状況である。
上記の状況は以下の調査をした。例えば、計算されたものの資源を使用して、後に接続することを避けるために、解決策を使った資源を割り当てるべきである。資源を割り当てることによって、リリースされるまで、その後の接続要求はこれらの資源を使用できない。
【００３６】
発見された経路にある簡易グラフＧRのリンクであるｍrリンクすべてにおいて、「リソース占有問題」と定義される一貫性の問題が起こる。同様に、Lリストに解決策に属するGリンクを含む簡易グラフＧRリンクのすべてのリンクにも一貫性の問題はある。
【００３７】
これに反して、セットアップされた接続で横断されなかったGパーティションで計算されたすべてのＧRリンクや、解決策に属しながらリストにリンクを含まないすべてのＧRリンクでは、一貫性問題は起こらず、資源が割り当てられていない場合と同様に最短経路は変更することはない。
【００３８】
パーティションのノードかリンクが取り消されるときも一貫性問題は起こる。
しかし、接続がリリースされるとき、似た状況は起こり接続のため占領されていた資源が新しい接続を計算するために、利用可能になるために一貫性問題がおきる。
【００３９】
上記の状況が起こったときは、リリースした接続に横断するGのパーティションで計算したすべての経路を更新する必要がある。同じ一貫性問題はパーティションの新しいノードまたはリンクをインストールする場合にもおこり、そこでのパーティションで計算したすべての経路を更新する必要がある。
【００４０】
しかし、インターリンクを挿入した場合に、ＧＲに属す新しいノードはGの新しいアーチに関連する。この新しいノードを挿入することは、入力ポートから終点ノードを含むパーティションの中にある問題のインターリンクまですべての経路を計算することや、インターリンクからすべての始点ノードを含むパーティションのなかの出力ポートまでの計算を要する。
【００４１】
上記とは逆に、インターリンクをキャンセルした時に、すべての入力と出力アーチが影響するこのポートに代表されるＧＲノードもキャンセルしなければならない。簡易グラフを常に一貫したものに保つことを心がける必要がある。
【００４２】
一貫した簡易グラフを維持する努力のほうが、利点を上回っているのではないかという疑問をもつかもしれない。また、新しい接続要求がくる度に、データベースからデータを引き出すため応答時間は必ずしも短縮されるのかという疑問をもつかもしれない。現実には、経路をみつけて使用可能になった時に、２つの要求の間の不動作時間にゆっくりと簡易グラフを更新できることがわかっている。
【００４３】
簡易グラフにルーティング・アルゴリズムを使う場合、簡易グラフを更新する時間は顧客の負担にならないため、顧客の立場からすると即座の応答を受け取るという疑う余地のない利点がある。
【００４４】
接続要求の到着から応答を見るまでにかかる間に、２つのソースと宛先パーティションだけが、関係するデータベースへの唯一のアーチセスである。簡易グラフの動的補完のためにこれらのデータが必要である。このようにデータベースに出来るだけ少ない情報を送るという目的は上記の方法で達成される。
加えてネットワークサイズと比べて、接続を作るリンクの数は非常に少ないことが実験で観察された。
接続に要するアーチの数が少ないので、接続がパーティションをわずかしか横切らない可能性は高く大量のデータをロードする必要はないということである。
簡易グラフではネットワークに関するすべてのデータを取り込むために、データベースにアーチセスする前処理段階が終了すれば、応答時間には影響しない。
【００４５】
同時に、接続で横断されたパーティションＰiは設定された直後であることを考慮すると、全ての（ＧR（Ｐi））のアーチを再び計算しなければならないということは考えにくい。この理由は、パーティションＰiに属する接続のアーチの数は多くないので、（ＧR（Ｐi））のアーチがリストLに接続のアーチを含むことは考えにくいからである。
実際は、これに関しては様々なパーティションのコストのトポロジーと配分に大きく左右される。
【００４６】
コスト面で有利なＰiの中に不可欠な経路かアーチがあれば、簡易グラフを作成するにあたって、ＧR（Ｐi）ののアーチが同じリンクを持つ可能性がある。
アルゴリズムを並列化する可能性を過小評価するべきでない。
管理された装置が最短経路の計算における有効な役割を果たさないため流通アルゴリズムを実現するのは現時点では不可能である。
この目的を達成する唯一の方法は有効にネットワーク管理のために設計された計算機を最大利用することである。
これは共用メモリをもち高出力で非常に強力であるマルチプロセッサである。
【００４７】
ネットワークの区分化に加えて簡易グラフを使用すれば、資源の地理的分布に基づいて様々なプロセッサの上でワークロードの分布を容認し、そして、それぞれのパーティションの連続と繋がり、構築のオペレーションを実行し、並行して、簡易グラフを更新することが考えられる。
【００４８】
テレコミュニケーションでは、ネットワーク上にある同期デジタルハイアラーキか波長分割多重方式がルーティング・アルゴリズムをかなり複雑にするために接続の制約を生じる。
確立した入力ポートがあるとすれば、接続的制約があるため出力ポートのどれにでも接続することは必ずしも可能ではない。
【００４９】
装置のポートは接続の制約によって、例として３つのセットに配置することが出来る。下記の特徴がある。
制約のないポートこのセットのポートの１つから信号が入力装置に届き、このセットのどの出力ポートからも通過できるポート。
総制約または固定交差接続ポートこのセットに属しながらポートの１つを通して入力装置に達する信号が決められた出力ポートを通過しなければならない。
部分的な制約か保護があるポート。これらのポートは、他のセットのポートを使用して配置された接続を保護するのに使用される。
このポートの制約はどの接続を保護するかに左右される。
【００５０】
接続の制限に加えてある波長を持つ特定のチャンネルが他の波長をもつチャンネルに光信号を接続できないという切り替えの制限がある。
【００５１】
例えば、適切なカードとマルチプレクサ(多重化装置)を使って、同期デジタルハイアラーキドメインから波長分割多重方式ドメインまで信号を多重送信する時にこの問題が起こる。
【００５２】
これらのカードの信号は、他のカードを使って多重化装置に送信された信号とは異なるユニークな波長を使ってそれ自体の波長を使用しマルチプレクサに送信しなければならない。多重化装置には、同じファイバの中でただ一つの波長分割多重方式信号でこれらの異なった信号を異なった波長で多重送信する機能がある。
上記の信号をカードから多重化装置に送る特定の波長は、ハードウェアを通して確立される。
【００５３】
ソフトウェアで適切なeの設定を許可するのを目的とする様々な研究があり、より高度な自由はルーティングプロセスにおいて導入するだろう。
これらすべての制限はペナルティは及び禁則を伴う最短経路の問題の解決策をもたらし、そこにはアーチ(i, j)(j, k)に関連したアーチ(i, j)からアーチ(j, k)までノードjで入力切替コストがかかる。
【００５４】
切り替えが容認されない場合は、ペナルティは無限のものになる。
デュアルネットワークがオリジナルのグラフの各アーチにある状態で、結合グラフのノードに関連する。アーチは各ペナルティと関連する。
禁じられた切り替えは、協定しているグラフに単にアーチが不在として示される。
【００５５】
様々な変換があり、その中でも驚いたことに双対グラフ変換か双対グラフが最も満足できるものであることがわかった。
【００５６】
接続よりもはるかに少ない数のノードがある電気通信網では、双対変換の特徴から、双対グラフ変換は容認できないほど複雑になるはずである。
双対グラフでは、ノード数はオリジナルのグラフのアーチの数と等しく、変換されたネットワークのアーチはネットワーク装置に許容交差接続を表す。
【００５７】
同期デジタルハイアラーキか波長分割多重方式のテレコミュニケーションに、適用した場合の明白な問題は、いくつかの装置によって導入された制約を表すために、すべての装置のために同じ変換を実行しなければならない。
【００５８】
接続制約がない装置にも変換を実行しなければならないことを意味し、準備のために物理的にノードを拡張する高いコストがかかることである。
接続制約のない装置は双対グラフでノード数O = (Ｏin+Ｏout)に激増し、Ｏinはオリジナルのグラフに装置への入力リンク数を表し、Ｏoutはオリジナルのグラフの装置から出力リンクの数を表す。また、アーチの数もＭr= (Ｏin×Ｏout)と等しい。
【００５９】
双対変換と簡易グラフと本発明のパーティションを用いることにより、「クレバー双対グラフ変換」とよばれるものをもたらし、双対グラフの不利をなくし、高いルーティング効率を達成する。
この方法は、様々なパーティションをもつグラフを作図するのに双対変換を使用する。
構築のためや、簡易グラフを更新するために必要な経路を計算したあとで、グラフは取り消される。
したがって、唯一永久的に保存され定期的に更新するデータ構造で簡易グラフを作成することになる。
【００６０】
各パーティションの入力ポートから出力ポートへの経路を計算することで、確実に装置の接続制約を順守する。
簡易グラフＧRから直接操作して接続するために、許容されている様々な経路をリンクして接続の制約を順守する。
【００６１】
簡易グラフ上では、変換する必要が無く上記の方法で、制限のない場合に直接最短経路を探す。ネットワークの区分化により、ネットワークの更新ごとのパーティションにおいてだけノードとアーチの数が増加する。
この利点を強調するには、データベースからネットワークに関する全てのデータをロードして、接続要求がある度にこの大量のデータを変換する意味を考える必要がある。
【００６２】
|V|=Nと|A|=MでW指定のネットワークG (V,A)は、各装置への入力リンクの平均数を仮定する。装置への入力リンクは別の装置からの出力リンクなので、Wは各装置から出力リンクの平均数を表す。
誤解をさけるために、Wはネットワークに実際インストールした装置から平均の入出力リンクを定義した。
この数と装置が入力か出力で管理できる数を混同してはいけない。各装置がインストールできる最大リンク数の入出力がある場合、変換したネットワークのサイズの観点からみて最悪の場合にこの２つの値が一致する。
最悪の場合、すべての可能な交さ結線が認められ、W2アーチを持つ装置ではアーチがノードとなるため、双対グラフ変換がMノードとNxW2アーチから成るネットワークを作り出す。
それぞれの入力リンクを各出力リンクに接続でき、入出力リンクの平均数Wである。
上記から、簡易グラフの作成と更新には何度か最短経路探索アルゴリズムを実行する必要がある。最短経路アルゴリズムの選択方法が重要な鍵を握る。
効率に重点をおいてフィボナッチヒープの特定のデータ構造をもつダイクストラアルゴリズムを使用することを薦める。
【００６３】
ダイクストラアルゴリズムを導入してNノードとMアーチがあるネットワークの計算の複雑性は、O (M + Nxlog (N))と等しく、NxW2値はMを代入し、M値はNを代入する。
変換されたネットワークの複雑性は以下のようになる。
O(NxW2 + Mxlog(M))
W値が装置が管理できるリンクの最大数に制限されていることがわかる。そのため前述の複雑性は以下に示される。
O (N + Mxlog(M) )
【００６４】
実際には、W値はわずかなノードとアーチから成るネットワークで特に重要となる。ここに、以下のことを考慮しなければならない。同期デジタルハイアラーキトラフィックが整い、各接続要求はソースと宛先ノードに加えて、望みのトラフィックのタイプを指定しなければならない。つまりそれぞれのタイプのトラフィックの簡易ＧRをメモリに保存することになる。
【００６５】
理論的には、ネットワーク(簡易グラフの使用に関係なく)を表すグラフの作成段階で要求されたトラフィックの種類と関連して、そのリンクに利用可能なコンテナの数と同数のアーチ数をもつようにリンクを拡大することを意味する。
【００６６】
基本的には接続制約は、入力か出力リンクの組に関係があり、2つのリンクの中で選ばれた特定のコンテナには関係がない。データを取る段階で、要求されたタイプのトラフィックのサポートのためのコンテナを選べる。
【００６７】
正しいトラフィック分配をするために、１次結合に基づいたアーチのコストは確立され、クライアントによってそのリンクに割り当てられたコストとトラフィックのリンクでの入手可能性に基づいて確立する。
【００６８】
光学機器が完全な波長変換できる波長分割多重方式トラフィックが、同期デジタルハイアラーキトラフィックのために適用されるのと同じ論理である。この場合に有効なチャネル数にリンクを増大させ、同期デジタルハイアラーキトラフィックの評価基準にコストをあてる代わりに、光リンクで利用可能なチャネルを選べる。そのうえ、他の波長割当て処理を適用できる。
【００６９】
光ドメイン信号が電子ドメイン信号に変換しない場合やその反対の場合（OEO変換）、波長変換をしない交さ結線のコストを割り当てるために、装置からの入力と出力リンクが増加することは明らかである。
【００７０】
一方では、波長分割多重方式単一経路ネットワークにおいて、各リンクを入手可能のチャネル数まで激増させる必要がある。
単一経路ネットワークはそれぞれのリンクで同じ波長を使用する波長継続制約を導入する。容認される解決策を得るために、２つの同じ波長の間の交差結線を表すアーチを変換されたネットワークに挿入する必要がある。
導入した制約の観点から、波長継続制約とフィールド交差接続を比較できる。
双対グラフの使用が明らかに複雑性を増すことを上述した。実際には本発明の仕分け方法で、接続制約を持つ装置と接続制約をもたない装置にわけることができる。この様に、パーティションに接続制約がない装置があり、その装置には、双対グラフではなく直接単一最短路アルゴリズムが適用されている。
制約のある装置とない装置が同じパーティションにある場合、「クレバー・デュアルネットワーク」と呼ばれる方法が適用されるかもしれない。言い換えれば、デュアルネットワークは制約のないネットワークメンバには効率的でない。
【００７１】
この場合、方法を変更したり、ペナルティなしに入力から出力に達するノードを使ったアルゴリズム(クリアデュアルネットワーク)を使う方法がある。したがって、アーチそれぞれは、ペナルティゼロとなるアルゴリズムは以下の事実を使用する。この様に、P^2〜2Pまでのアーチが可能である。
これは、以下のステップから成る。
【００７２】
１．装置を3つのクラス(図9で3つのクラスの装置を示す)に分割する。
- A.接続制約のない装置;入力はどこの出力ポートにも接続できる。
- B.部分的な接続制約がある装置;少なくとも１つの入出力セットが自由に入力ポートと出力ポートを接続できる。
- C.絶対的な接続制約がある装置;全ての入力ポートに制約がある。
2．AとBの装置と簡易グラフで仮想ノードNfを関連させる。
3．接続制約があるポートを終点か始点ともつ各リンクと簡易グラフの仮想Lf ノードを関連させ、オリジナルグラフがタイプCまたはDで制約のあるポートの場合である。
4．オリジナルのタイプAノードに関連する簡易グラフの仮想ノードNfについて
- パラグラフ3で作成した仮想ノードLfについて、LfのオリジナルアーチがNfのオリジナルノードに入力された場合、LfとNfをつなぐリンクを挿入し、このアーチのコストはLfによって表されるオリジナルアーチのコストと同じでなければならない。
- パラグラフ３で作成した仮想ノードLfについて、LfのオリジナルアーチがNfと関連したオリジナルのノードの出力であった場合NfとLfを接する費用が掛からないリンクを挿入する。
- オリジナルグラフのアーチがパラグラフ3の変換をしない場合、そこでNfを始点か終点にもつノード、それぞれのアーチにNfをオリジナルのグラフの始点か終点に関連するノードを接続する場合、オリジナルグラフのアーチのコストと同じでなければならない。
5．オリジナルタイプBノードと協働する変換グラフの各仮想ノードNfに対して、
- パラグラフ3で作成されたすべての仮想LfinかLfoutを検討し、これらの仮想ノードはオリジナルのグラフの入力か出力アーチのためのもので、仮想Nfノード間にある制約のあるポートでおこる。仮想ノードLfinにリンクを挿入し、これは仮想LfinとLfoutに限定した接続をする。これはオリジナルグラフ上の接続可能なアーチにあたり、アーチのコストはオリジナルのアーチのコストと等しくなければならない。
オリジナルのアーチはLfinによって表され、アーチのコストはペナルティのコストと等しくなければならない。
2つのアーチがオリジナルのグラフで接続されため、ペナルティコストを支払わなければならない。
−制約付のポートの入力または出力でオリジナルのグラフのアーチに対してパラグラフ３のもとで作成された仮想ノードＬｆinまたはＬｆoutを検討し、仮想ノードＮｆのノード及び前記仮想ノードＬｆinに対するノードへのあるいはそのノードから、仮想ノードＬｆinを結合するリンクを他の仮想ノードＬｆoutに挿入する；この場合、この結合は、仮想ノードの組Ｌｆin、Ｌｆoutに対してだけに行い、またこれらの組はオリジナルのグラフのアーチの結合可能な組に対応しなければならない；上記アーチのコストはＬｆinで表示されるオリジナルアーチのコスト及びオリジナルグラフにおける２つのアーチを接続するための支払われるべきペナルティのコストとの総計に等しい；
−制約なしのポートの入力または出力におけるオリジナルのグラフのアーチに対してパラグラフ３のもとで作成されたすべての仮想ノードの組ＬｆinまたはＬｆoutを検討し、仮想ノードＮｆに対する及び前記仮想ノードＬｆinに対するノードへあるいはそのノードから、Ｌｆinで表示されるオリジナルアーチのコストを維持しつつ、仮想ノードＬｆinを結合するリンクを他の仮想ノードＬｆoutに挿入し、これらの仮想ノードＬｆoutの各々に対して、仮想ノードＮｆをゼロコストで結合するリンクを前記仮想ノードＬｆoutに挿入し:
パラグラフ３で記載された、前記変換を受けていないオリジナルのグラフの始点あるいは終点ノードＮｆを持つアーチを検討し；各アーチに対して、オリジナルのグラフのアーチと同じコストを維持しながら前記仮想ノードＮｆをオリジナルのグラフの終点あるいは始点ノードに関連する他方の仮想ノードに接続する；
6．オリジナルのタイプCノードに関連した変換グラフの仮想ノードNfについて、
パラグラフ３で作成されたすべての仮想ノードのLfinかLfoutは、オリジナルのグラフの入力か出力アーチと関連があり制約があるポートでおこり、その制約はNfと示したノードの間にある。特定のLfinまたはLfoutにアーチを挿入しオリジナルグラフに接続できる２つのアーチを象徴している。
【００７３】
図10にオリジナルネットワークで上記の方法を示している。特に、11a から11eに変換ステージ2,3,4,5, 6を示す。
【００７４】
本発明に述べたネットワークの区分化により、双対グラフのサイズを制限し、ネットワーク変換が個別に各パーティションで、簡易グラフの構築、操作、動的補完と更新ができる。
そのため各パーティションのノードやリンクの数は、全体のネットワークより少ない。それぞれの操作の完了後、関連したパーティションの双対グラフであるデータ構造は取り消される。
クレバー・デュアルネットワークを考慮した場合でも双対グラフと取り替えるだけで、上記の内容に変更はない。
しかし、接続要求が到着する時には簡易グラフの動的補完に関わるソースと宛先パーティションをもつクレバー・デュアルネットワークも構成しなければならない。さらに、変換されたネットワークで要求のノードを特定できなければならない。
【００７５】
以上の観察結果から、簡易グラフを動的に完成するための方法は以下のようにまとめることができる。
1．ソースまたは宛先パーティションのためのクレバー・デュアルネットワークは、ソースか宛先ノードがタイプCである場合、仮想ノードが加わる。ソースノードがタイプAかBであるなら、変換したネットワークのノードがクレバー・デュアルネットワークの構造に必要な正常動作の間に直接作成される。
２．ソースノードｎSを検討し、ｎSがタイプAの場合に何の行動も起こさない。タイプBであるなら接続制約がある各出力ポートに、変換グラフのｎSと表す仮想ノードとポートのリンクを表す仮想ノードと間にアーチを加える。ｎSがタイプCなら各出力ポートに、変換グラフのｎSと表す仮想ノードとポートのリンクを表す仮想ノードの間にアーチを加える。
３．宛先ノードｎdを検討し、ｎdがタイプAの場合に何の行動も起こさない。タイプBであるなら接続制約がある各入力ポートに、変換グラフのｎdと表す仮想ノードとポートのリンクを表す仮想ノードと間にアーチを加える。ｎdがタイプCなら各出力ポートに、変換グラフのｎdと表す仮想ノードとポートのリンクを表す仮想ノードの間にアーチを加える。
【００７６】
言い換えれば、提案方法の概要は次の３段階になる。
前処理
簡易グラフのルーティング
グラフの更新
前処理は２ステップからなる。
デュアルネットワークの構築
固定接続を使用するグラフの減少
この操作は、オプションであるかもしれない。
【００７７】
トラフィックタイプについてはまだ検討されていないが、トラフィックのルーティングが要求される度に、トラフィックをサポートしないオリジナルグラフのアーチを削除して、そのトラフィックのための簡易グラフを作成する。
上記のグラフを区分してトラフィックごとに作成した簡易グラフは、メモリに保存される。
簡易グラフのルーティングは、パーティションAのノードsからパーティションBのノードdまで要求があるたびに、トラフィックtrとトラフィックtrに関連したグラフとパーティションAとBは２つのサブグラフでおきかえらる。ノードsからパーティションAの端のノードと、パーティションBの端のノードからノードdまでは最小のコストとなる。
【００７８】
最短経路探索アルゴリズムはこの最終的なグラフに適用され、最短経路が発見されるとき、関連リソースが用意される。
【００７９】
次のルーティングの前にグラフの更新をする必要があるが、ルーティングで使用されるパーティションだけに適用される。オリジナルグラフと計算したルーティングに共通のアーチがある簡易グラフの経路だけを更新する必要がある。
ノードを挿入、変更、または取り消すときに更新する必要がある。
【００８０】
図12はネットワークに関する例を示す。図13は図12のサブネットワー2のためのデュアルネットワークを示す。この例では、各ijとjk全てのペナルティが1: oij, jk =1となる。対応する簡易グラフは図14に示した。Min(p)×Mout(p)がパーティションとパーティションへのI/Oアーチの数を示す。これから簡易グラフのパーティションｐではMin(p) x Mout(p)は表示されない。
【００８１】
図15にネットワークを構成する接続制限のある装置の例を示した。これらの装置には、下記の接続制限がある。
【００８２】
接続制限の例を下記に示した。
ネットワークAとDのメンバには絶対的な接続制約がある。
ネットワークBのメンバが部分的な接続制約がある。
ネットワークCのメンバには、接続制約が全くない。
【００８３】
ネットワークを変換するために、3つの異なった規則が適用される。アプリケーションはネットワークメンバの特性による。下記に2つの規則を述べる。
接続の完全な制約。その結果、すべてのI/O接続がノードになる。
接続の制約がないネットワークメンバとの接続は単一接続となる。単一接続とは、制約のないノードと新しい仮想ノードの接続のことを示す。新しい仮想ノードとは連結に制約のないネットワークと関係がある。
【００８４】
図16のグラフは最初の2つの規則が図15のオリジナルのネットワークに適用された例である。
【００８５】
3番目の規則は部分的な接続制約の場合に関連する。絶対的に接続可能なポートは単一ノードによって示される。
接続制約があるポートは同じように絶対的な接続制約の規則に従って扱われる。
このアプリケーションから作成された最終的なネットワークは図17の概要で示した。
上記のまとめとして、要約した例を下記に示した。そこでくわしく接続制約のある装置をもつネットワークの、最短経路の識別について要約した例を述べている。
【００８６】
本発明の方法では、第1ステップは1つのレベルでオリジナルのネットワークを仕切り、パーティションの中の様々な装置を分類することである。装置は接続制約によって分類されている。この第1ステップは図18に示される。
【００８７】
次に、各パーティションにオリジナルグラフのインターリンクを示す仮想ノードを挿入する必要がある。さらにこれらの仮想ノードは上記の操作をするクレバー・デュアルネットワーク変換をおこなう。このステップは図19に示した。
【００８８】
各パーティションに関しては、入力ポートと出力ポートを接続するための最短経路を計算する。その経路が無ければ、アーチは挿入されない簡易グラフGRが構築される状況になる。図18のネットワークに関連した簡易グラフを図20に示した。
【００８９】
接続要求(＜S,Pa＞, ＜D,Pc＞)が届くとき、クレバー・デュアルネットワーク変換をしながら動的補完をする必要がある。クレバー・デュアルネットワークで簡易グラフの動的補完に関するパーティションのステップは図21に示した。図22で完成した簡易グラフの(＜S,Pa＞, ＜D,Pc＞)接続の計算の最終結果を図22に示した。
【００９０】
ノードSはタイプAノードカテゴリに属し、これは仮想ノードSfがPaのクレバー・デュアルネットワークの構造の間、自動的に作成されるため、ノードが全く加えられなかったと強調しておく。
【００９１】
タイプCノードカテゴリに属すノードDは、仮想宛先ノードであるDfを挿入する必要がありDfはDfをDの入力ポートに現れるリンクのノードを接続するアーチの始点ノードとなる。
【００９２】
最後に、必要な経路は図22の簡易グラフで計算され、計算の結果は図23に示され、その必要経路は図24に示したオリジナルグラフの経路に対応している。
このように前もって予定していた目的が達成されたことは明らかになった。
【００９３】
本発明の双対変換法には、光ファイバ通信システムによって供給された莫大な帯域のために基本となるネットワークの保護技術の開発が容易になるという利点がある。双対変換は変換ネットワークを作り出し、そこで正常な回線交換のために最短路ダイクストラのアルゴリズムを使用する。
さらに、変換されたネットワークのサイズは装置の接続制約の数が増加すると縮小する。例えば、固定交差接続はデュアルネットワークのアーチの数をかなり減少させる。
【００９４】
最後に、デュアルネットワークのオリジナルのネットワークの変換の作業はネットワーク分割をつかうので、かなり限定される。
確かに簡易グラフＧRを作成した後には、接続要求に応答し、更新フェーズにおける経路によって横断されたパーティションに応答するために、ソースと宛先パーティションで作業をするだけなので、クライアントに負担をかけない。
【００９５】
本発明の具体例は革新的な原則に制限されず、ここで請求している占有権に関連している。
【図面の簡単な説明】
【００９６】
【図１】ネットワークを例に挙げたグラフである。
【図２】図1のネットワークを3つのサブネットワークA,B,Cに仕切る方法を示している。
【図３】図1のパーティションAを仕切るための仮想ノードの追加を示している。
【図４】本発明の方法に沿ったオリジナルのパーティションAの簡易グラフを示している。
【図５】簡易グラフの動的補完の例を示している。
【図６】簡易グラフで見つけた最短経路に関する例を示している。
【図７】図6の最短経路をオリジナルのグラフに移した例を示している。
【図８】最適経路が何度か同じパーティションを通り抜けるネットワークグラフの例を示している。
【図９】接続制限に基づいて装置の概要の下位区分を示している。
【図１０】本発明に従って「精妙な二元的なネットワーク」方法を適用したオリジナルネットワークの概要を示している。
【図１１ａ】図10のネットワークに適用されたものをグラフ化したものを示している。
【図１１ｂ】図10のネットワークに適用されたものをグラフ化したものを示している。
【図１１ｃ】図10のネットワークに適用されたものをグラフ化したものを示している。
【図１１ｄ】図10のネットワークに適用されたものをグラフ化したものを示している。
【図１１ｅ】図10のネットワークに適用されたものをグラフ化したものを示している。
【図１２】本発明に沿った方法を適用したアプリケーションを示している。
【図１３】本発明に沿った方法を適用したアプリケーションを示している。
【図１４】本発明に沿った方法を適用したアプリケーションを示している。
【図１５】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図１６】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図１７】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図１８】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図１９】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図２０】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図２１】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図２２】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図２３】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図２４】本発明に沿った方法の拡張したアプリケーションの適用に関する例を示している。
【図２】
2004535140.tif 000005
【図４】
2004535140.tif 000006
【図５】
2004535140.tif 000007
【図６】
2004535140.tif 000008
【図１６】
2004535140.tif 000009
【図１８】
2004535140.tif 000010
【国際公開パンフレット】
2004535140.tif 000011
2004535140.tif 000012
2004535140.tif 000013
2004535140.tif 000014
2004535140.tif 000015
2004535140.tif 000016
2004535140.tif 000017
2004535140.tif 000018
2004535140.tif 000019
2004535140.tif 000020
2004535140.tif 000021
2004535140.tif 000022
2004535140.tif 000023
2004535140.tif 000024
2004535140.tif 000025
2004535140.tif 000026
2004535140.tif 000027
2004535140.tif 000028
2004535140.tif 000029
2004535140.tif 000030
2004535140.tif 000031
2004535140.tif 000032
2004535140.tif 000033
2004535140.tif 000034
2004535140.tif 000035
2004535140.tif 000036
2004535140.tif 000037
2004535140.tif 000038
2004535140.tif 000039
2004535140.tif 000040
2004535140.tif 000041
2004535140.tif 000042
2004535140.tif 000043
2004535140.tif 000044
2004535140.tif 000045
2004535140.tif 000046
2004535140.tif 000047
2004535140.tif 000048
2004535140.tif 000049
2004535140.tif 000050
2004535140.tif 000051
2004535140.tif 000052
2004535140.tif 000053
2004535140.tif 000054
2004535140.tif 000055
2004535140.tif 000056
2004535140.tif 000057
2004535140.tif 000058
2004535140.tif 000059
2004535140.tif 000060
2004535140.tif 000061
2004535140.tif 000062
【国際調査報告】
2004535140.tif 000063
2004535140.tif 000064