(57)【要約】ネットワークにおける脆弱性をマッピングし且つ解析するシステム及び方法。ネットワークがマッピングされる１実施例において、ネットワークラインデータをポイントデータへ変換し、該ポイントデータを該ネットワークの上側に重ねたグリッドのセルと関連付け、且つ該グリッドの該セルに対する該ポイントデータの関係を決定することにより該ネットワークを解析することを包含している。【選択図】      図１
2008509459.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークをマッピングする方法において、
ネットワークラインデータをネットワーク用のポイントデータへ変換し、
該ポイントデータを該ネットワークの上に重なるグリッドのセルと関連付け、
該グリッドの該セルに対する該ポイントデータの関連性を決定することにより該ネットワークを解析する、
ことを包含している方法。
【請求項２】
請求項１において、前記ポイントデータに対して属性データが割当てられる方法。
【請求項３】
請求項１において、該ネットワークが空間的ネットワークである方法。
【請求項４】
請求項１において、該解析を行うことが、該関連性に基づいて臨界的なセルを決定することを包含している方法。
【請求項５】
請求項１において、該解析を行うことが、該セルの各々におけるポイントの数を決定することを包含している方法。
【請求項６】
請求項１において、該解析することが、該ポイントデータの各ポイントに対して重みを割当てることを包含している方法。
【請求項７】
請求項６において、更に、該セルの各々におけるポイントの全体的な重みを決定することを包含している方法。
【請求項８】
請求項７において、更に、各セルにおけるポイントの全体的な重みを各セルにおけるポイントの数により割算した比を計算することを包含している方法。
【請求項９】
請求項１において、更に、
ネットワークラインデータを少なくとも１つの付加的なネットワークに対するポイントデータへ変換し、
該少なくとも１つの付加的なネットワークに対する該ポイントデータに対して属性データを割当て、
該少なくとも１つの付加的なネットワークに対する該ポイントデータを該少なくとも１つの付加的なネットワークの上側に重なるグリッドのセルと関連付け、
該ネットワークにわたって対応するセルにおけるポイントを解析することにより該ネットワーク間の関係を解析する、
ことを包含している方法。
【請求項１０】
請求項１において、更に、
該グリッドから少なくとも１個のセルを除去し、
該少なくとも１個のセルを除去することにより発生される該ネットワークに関する影響を検査する、
ことを包含している方法。
【請求項１１】
請求項１において、該関連付けが、
セルに対するポイントデータの関係に基づいて第二ネットワークを作成する、
ことを包含している方法。
【請求項１２】
請求項１１において、更に、
どのセルが互いに隣接しているかに基づいてセル隣接性リストを作成し、
該セル隣接性リストに基づいてセル間のディスジョイント経路を決定する、
ことを包含している方法。
【請求項１３】
請求項１２において、該経路の共通セルの和を該経路のセルの和により割算した比を利用して経路のディスジョイント性を計算する方法。
【請求項１４】
請求項１において、該ラインデータが、
衛星画像データ、
デジタル化地図データ、又は
上記の任意の結合、
を有している方法。
【請求項１５】
請求項１において、該ネットワークデータが、
静的ネットワークデータ、
動的ネットワークデータ、
衛星ネットワークデータ、
テレコミュニケーションデータ、
マーケティングデータ、
人口統計データ、
ビジネスデータ、
通行権ルーチングデータ、又は
地域位置データ、又は
上記の任意の結合、
を有している方法。
【請求項１６】
請求項１５において、該テレコミュニケーションデータが、
大都市区域ファイバーデータ、
長距離ファイバーデータ、
コロケーション施設データ、
インターネット交換データ、
ワイヤレスタワーデータ、
ワイヤセンターデータ、
海中ケーブルデータ、
海中ケーブルランディングデータ、又は
データセンターデータ、又は
上記の任意の結合、
を有している方法。
【請求項１７】
請求項１５において、該通行権ルーチングデータが、
ガスパイプラインデータ、
オイルパイプラインデータ、
ハイウエイデータ、
鉄道データ、又は
電力輸送線データ、又は
上記の任意の結合、
を有している方法。
【請求項１８】
請求項１５において、該静的ネットワークデータが、
ｉｐネットワークデータ、又は
ネットワークトポロジィデータ、又は
上記の任意の結合、
を有している方法。
【請求項１９】
請求項１５において、該動的ネットワークデータがネットワークトラフィックデータを有している方法。
【請求項２０】
請求項１において、該ネットワークデータが、
データを購入、
データを手作業により構成、
外部ソースからデータをマイニング、
ネットワークをプロービング、
ネットワークをトレーシング、
私有データへのアクセス、又は
ハードコピーデータのデジタル化、又は
上記の任意の結合、
により得られる方法。
【請求項２１】
請求項１５において、該地域位置データが、
大陸情報、
国家情報、
州情報、
郡情報、
郵便番号情報、
国勢調査ブロック情報、
国勢調査トラック情報、
時間情報、
大都市情報、又は
機能的情報、又は
上記の任意の結合、
のうちの少なくとも１つを包含している方法。
【請求項２２】
請求項２１において、該機能的情報が、
方式、
連邦準備銀行領域、
トレードゾーン、
国勢調査領域、又は
通貨領域、又は
上記の任意の結合、
のうちの少なくとも１つを使用して画定される方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークにおける脆弱性をマッピングし且つ解析することに関するものである。
【発明の開示】
【課題を解決するための手段】
【０００２】
【発明を実施するための最良の形態】
【０００３】
図１は本発明の１実施例に基づいてネットワークをマッピングし且つ解析するシステムを例示している。このシステムは、格納データベース１０５を包含しており、それは以下のもの：空間ネットワークからのラインデータを格納するネットワークラインファイル１１０、ポイントへ変換されたネットワークデータを格納するネットワークポイントファイル１１５、ポイントへ割当てられた属性情報を包含するネットワークポイントデータを格納するネットワークポイント／属性ファイル１２０、及びグリッド（格子）情報と関連付けられているポイントデータを格納するネットワークグリッドファイル１２５を包含している。例えば、該グリッドは図２に例示したように、各セルにおけるポイントデータに基づいて各セルに対する属性と共に格納することが可能である。
【０００４】
本システムは、又は地理情報システム（ＧＩＳ）１３０を包含しており、それはライン・ポイント変換器プログラム１３５、ポイント／属性割当てプログラム１４０、グリッド発生器プログラム１４５、重み割当てプログラム１５０を包含している。更に、ＧＩＳ１３０は、密度解析／表面マッピングプログラム１５５、相互依存性解析プログラム１６０、障害シミュレーションプログラム１６５、又はディスジョイント（ｄｉｓｊｏｉｎｔ）経路解析プログラム１７０、又はその任意の結合を包含することが可能である。本システムは、解析的出力に対しアルゴリズム、スクリプト及びプロセスを一意的に結合するオープンソースＤＩＳシステムを含む任意のＪＩＳプラットフォームを使用することが可能である。ライン・ポイント変換器プログラム１３５はオリジナルの空間的ネットワークベクトル（即ち、ライン）データをポイントへ変換する。ポイント／属性割当てプログラム１４０はオリジナルのネットワークベクトルデータから各ポイントに対し属性を割当てる。グリッド発生器プログラム１４５は該データに対しグリッドを適用し且つポイントデータを該グリッドにおけるセルと関連付ける。重み割当てプログラム１５０は各ポイント（点）に対し重みを割当てる。密度解析／表面マッピングプログラム１５５は、該グリッドにおける各セル内のポイントの数を計算する。相互依存性解析プログラム１６０は２つのネットワークのポイントを互いに比較する。障害シミュレーションプログラム１６５及びディスジョイント経路解析プログラム１７０は、ネットワーク効果及び１個のセルにおけるインフラストラクチャがどのようにしてその他のセルにおけるインフラストラクチャと関連しているかを解析する。本実施例はＧＩＳ１３０を使用して空間的ネットワークを解析する。空間的ネットワークはそれに対し地理的参照を有する任意のネットワークを包含し、且つ座標系において提示することが可能である。勿論、該ネットワークを特性付ける任意のシステムを使用してその他のタイプの論理的ネットワークを解析することが可能である。
【０００５】
本システムは、又、ユーザインターフェース１７５を包含しており、それは３−Ｄ脆弱性トポロジィマップ１８０、脆弱性ヒートマップ１８５、統計的及び数値的出力マップ１９０、又はディスジョイント経路視覚化ヒートマップ１９５を発生することが可能である。３−Ｄ脆弱性トポロジィマップ１８０において、ｘ及びｙはそのマップが存在する二次元軸上の位置を表わし、且つｚは高さを表わし且つ解釈に依存してネットワーク密度又は脆弱性のレベルを表示する。脆弱性ヒートマップ１８５はコロプレス（ｃｈｏｒｏｐｌｅｔｈ）マップのように、異なるカラーでセル値における変化を表わす（即ち、高い値は赤色とし値が減少するに従い青色へフェーディングさせることが可能である）。統計的及び数値的出力マップ１９０は非視覚的出力として各セルに対して計算された実際の数学的な値を表わす。ディスジョイント経路視覚化ヒートマップ１９５はネットワークにおける２つ又はそれ以上の離散的なポイントの間のルーチング代替例を表わし、一方脆弱であるネットワークの区域を示す。赤色から青色へフェーディングするヒートマップの上の例を使用して、ディスジョイント経路ヒートマップは赤色（即ち、脆弱な）区域を回避する代替的な経路を例示する。
【０００６】
ラインデータは、これに制限されるものではないが、衛星画像データ、又はデジタル化地図データ、又は任意のその結合を有することが可能である。ネットワークデータはこれに制限されるものではないが、静的ネットワークデータ、動的ネットワークデータ、衛星ネットワークデータ、テレコミュニケーションデータ、マーケティングデータ、人口統計データ、ビジネスデータ、通行権ルーチングデータ、又は地域的位置データ、又は任意のその結合を有することが可能である。テレコミュニケーションデータは、これに制限されるものではないが、大都市区域ファイバーデータ、長距離ファイバーデータ、コロケーション（ｃｏ−ｌｏｃａｔｉｏｎ）施設データ、インターネット交換データ、ワイヤレスパワーデータ、ワイヤセンターデータ、海中ケーブルデータ、海中ケーブルランディングデータ、又はデータセンターデータ、又は任意のその結合を有することが可能である。通行権ルーチングデータは、これに制限されるものではないが、ガスパイプラインデータ、オイルパイプラインデータ、ハイウエイデータ、鉄道データ、又は電力輸送線データ、又は任意のその結合を有することが可能である。静的ネットワークデータは、これに制限されるものではないが、ｉｐネットワークデータ、又はネットワークトポロジィデータ、又は任意のその結合を有することが可能である。動的ネットワークデータは、これに制限されるものではないが、ネットワークトラフィックデータを有することが可能である。地域的位置データは、これに制限されるものではないが、大陸情報、国家情報、州情報、郡情報、郵便番号情報、国勢調整ブロック情報、国勢調査トラック情報、時間情報、大都市情報、又は機能的情報、又は任意のその結合を有することが可能である。機能的情報は、例えば、これらに制限されるものではないが、方式、連邦準備銀行領域、トレードゾーン、国勢調査領域、又は通貨領域又は任意のその結合を使用して画定される。
【０００７】
ネットワークデータは、例えば、これに制限されるものではないが、データの購入、データの手作業による構成、外部ソースからのデータのマイニング、ネットワークのプロービング、ネットワークのトレーシング、私有データへのアクセス、又はハードコピーデータのデジタル化、又は任意のその結合により得ることが可能である。
【０００８】
方法
図３は、本発明の１実施例に基づくネットワークをマッピングし且つ解析する方法を例示している。ステップ３０５において、空間ネットワークライン（即ち、ベクトル）データがネットワークラインファイルからＧＩＳ１３０内へロードされる。ステップ３１０において、ネットワークラインデータはライン・ポイント変換器プログラム１３５を使用してポイント即ち点へ変換され、ネットワークポイントファイル１１５として保存される。ネットワークライン（線）データをポイントデータへ変換させるために、スクリプトがこの機能を実行するためにロードされる。ラインデータはポイントへ変換させる場合に、パラメータをユーザにより設定することが可能である（例えば、ユーザが作成することを所望するポイントの総数、連続するポイントの間の距離等）。ポイントの数が一層高くなるに従い、解析は一層細かなものとなるが、計算的に負担が益々重くなる。
【０００９】
ステップ３１５において、属性データファイルをネットワークポイントファイルと融合させることにより属性を各ポイントに対して割当て、ネットワークポイント／属性ファイルを作成する。属性データはオリジナルのネットワークから派生される。属性データは各ポイントがそれ自身の重み（例えば、容量、直径、トラフィック、電圧、帯域幅等）を有することを可能とする。ステップ３２０において、ネットワークグリッドがネットワークポイント／属性ファイルと統合される。その結果はネットワークグリッドファイルとして保存される。ネットワークグリッドは関心区域を取囲む。グリッドオーバーレイを作成するために多様なスクリプトが使用可能である。グリッドセルの寸法は結果の所望の粒度に従って設定することが可能である。グリッド寸法は数メートルから数キロメートル、又はそれ以上にわたる範囲とすることが可能であり、多様な縮尺を達成することを可能とする。
【００１０】
ステップ３２５において、ポイント及びグリッドが作成されているので、ネットワークグリッドファイル内に保存されているポイント及びグリッドを使用しての計算を使用してネットワークに関して異なるタイプの解析（例えば、脆弱性解析）を実施する。例えば、図４に例示したように、グリッドの各セル内において、各セル内に含まれるポイントに基づいて計算を行うことが可能である。従って、左上角部における第一セルで開始して、且つ左側から右側へ各セルの番号を付けると、各セル内のポイントをカウントする結果的に得られるテーブルは図５に示されるようになる。
【００１１】
ステップ３３０において、セル臨界性のランク付けを含むセル臨界性に関する計算を行うことが可能である。ステップ３３５において、ステップ３３０からの情報をネットワーク障害シミュレーションを実施するために使用することが可能である。ステップ３４０において、セルディスジョイント解析を実施することが可能である。ステップ３４５において、多重基準ディスジョイントルーチング問題を解決するために遺伝的アルゴリズムを使用することが可能である。勿論、ステップ３３０−３４５のうちのいずれか１つ又は任意のその結合を実施することが可能である。
【００１２】
セルの臨界性の測定
セルのクリティカリティ即ち臨界性は、これらに制限されるものではないが、密度解析、重み付け密度解析、相互依存性解析、チョークポイント解析、又はグリッドセルにおける１つ又はそれ以上のネットワークのポイントに対しての乗算、加算、割算、正規化、ロギング（ｌｏｇｇｉｎｇ）、パワーリング（ｐｏｗｅｒｉｎｇ）、又は任意のその他の数学的又は統計的演算の組合わせを含む多数の態様で測定することが可能である。
【００１３】
密度解析。密度解析においては、各セル内のポイントの数が計算され且つ各セルに対して割当てられる。グリッドセルの数値は特定した地形的区域におけるネットワーク資源の相対的な濃度を意味する。このことは、地域的多様性の低レベルであるがネットワークインフラストラクチャの高レベルである区域の識別を可能とし、そのことはボトルネック即ち脆弱性のポイントである場合がある。例えば、図６に例示したように、電力グリッドの密度解析が、最小量の多様性を有する電気的伝送線の最も高い密度が、２００３年８月における北東停電（Ｎｏｒｔｈｅａｓｔ  Ｂｌａｃｋｏｕｔ）の起点として指定されているオハイオにおける区域と一致していることを例示している。
【００１４】
これらの結果は多様な態様で視覚的に提示することが可能である。各グリッドセルの値はその計算された値に従ってｚ値を割当てることが可能である。次いで、全てのグリッドセルのｚ値を三次元マップとしてプロットすることが可能であり、その場合に高さは、解釈に依存して、ネットワーク密度のレベル即ち脆弱性を表わす。更に、これらの三次元マップはアニメーションとすることが可能であり且つ鳥瞰図による景観（ｆｌｙ  ｔｈｒｏｕｇｈ）を与えることが可能である。その結果は、又、コロプレスマップとして提示することが可能であり、その場合に異なるカラーはグリッドセルの計算された値を意味している。その最終結果はネットワーク密度即ち脆弱性のヒートマップとすることが可能である。
【００１５】
重み付け密度解析。従来のマトリクス方法と異なり、重み付け密度アプローチは、非常に大きく且つ複雑なネットワークに対し重みを包含させることを可能とする。各セルにおけるポイントの数を計算すると共に、各ポイントの重みを考慮することも可能である。第一の可能な機能は、１つのセルにおける全てのポイントに対する重みの和を加算することである。第二に、各セルの全体的な重みを各セルにおけるポイントの数で割算することにより比を計算することが可能である。各セル内の値は、ユーザの所望するところに従い、加算、減算、対数化、指数化、正規化、割算又は乗算することが可能である。密度解析の下で上に概説した同一の視覚化技術をここでも使用することが可能である。
【００１６】
例えば、図７−８は北アメリカガスパイプネットワークに対する重み付け密度解析（図８）及び通常の密度解析（図７）を例示している。１個のセル内のポイントの数及びこれらのセルにおけるポイントの容量を見ることに加えて、これら２つの変数が計算において使用されるアルゴリズムを稼動させることが可能である。例えば、セルの容量をセルの密度で割算して密度より一層大きな容量を有する区域を発見することが可能であり（即ち、多様性）、例えば、ネットワークにおけるボトルネックを識別する。このようなアプローチの出力を北アメリカガスパイプラインネットワークに対して図９において例示してある。
【００１７】
相互依存性解析。単一のネットワークインフラストラクチャを解析することに加えて、複数のネットワークを検討してそれらの空間的相互依存性を決定することが可能である。２個又はそれ以上のネットワークがＧＩＳ１３０内にロードされる点を除いて、上述したのと同一の手順が追従される。各ネットワークにおけるラインデータは、別々に、ポイントへ変換され且つそれらの夫々のデータベースから属性が割当てられる。このことが達成されると、グリッドを使用することが可能であり且つ計算を行うことが可能である。特に、２個又はそれ以上のネットワークを同時的に解析することにより、両方に対しての高密度又は脆弱性、空間的相互依存性が存在する特定の地理的位置を識別することが可能である。このことは、全ての可能なネットワーク相互依存性シーケンスに対し、ポイントの数及び多様な重みを積分し、次いで、加算し、減算し、対数化し、指数化し、正規化し、割算し、又は乗算することの多様な組合わせで行うことが可能である。これは、密度解析部分において上に概説した手段を使用して視覚化することが可能である
例えば、図１０はファイバーグリッドとパワーグリッドとを結合してどこにそれら２つのインフラストラクチャの間の共通の地理的相互依存性が存在するかを解析するグリッド密度解析である。
【００１８】
２つ又はそれ以上のネットワークの間の相互依存性を解析すると共に、ネットワークとその他の固定オブジェクトとの間の空間的相互依存性を例示する解析を構成することが可能である。例えば、橋及びテレコミュニケーションファイバ又はダム及び電力伝送線の間の空間的相互依存性を検討することが可能である。これは、ポリゴンにより表わされる固定オブジェクトとポイントとの交点を計算することにより達成される。これは、密度解析部分において上に概説した手段を使用して視覚化することが可能である。
【００１９】
例えば、図１１はファイバオプチックケーブルと交差する臨界的な橋であるポリゴンを例示している。その橋と交差するファイバが多ければ多い程、対応する赤色の棒は一層高い。
【００２０】
空間統計学を使用したチョークポイント解析。ラスターに基づいたアプローチの欠点のうちの１つは、それがネットワーク効果を無視することであり、即ち１つのセルにおけるインフラストラクチャがどのようにして他のセルにおけるものと空間的に関連しているかを無視することである。これはセル又はネットワークの一部のクリチカリティ即ち臨界性を定義する場合に考慮すべき重要な側面である（即ち、ある区域における幾つかのその他のセルへ地理的に良好に接続されている高密度セルにおけるインフラストラクチャを破壊することの暗示は極めて厳しいものである場合があるが、この同じセルが、その密度に拘わらず、地理的に孤立している場合にはその効果はそれ程有害なものではない）。
【００２１】
空間的統計を使用するために、隣接性に対する何等かの規則に基づいてどのようにしてセルが空間内において互いに位置されているかを記述する接近性マトリクスを定義することが必要である。図１２は１０×１０グリッドオーバーレイ及び参照番号を有するプロトタイプネットワークを例示している。ラインはネットワークを表わしており且つセル内の数字は接近性マトリクスに対する参照である。１０×１０グリッドを上に重ねることによりネットワークを３５個のセルに分解し、ネットワークの一部を含むセルのみを抽出する。抽出したセルを使用して、次の規則、即ち、セルが直接上、下、右、左又は４個の対角線位置のうちのいずれかに存在する場合にはそれは別のセルに隣接している点を使用して３５×３５接近性マトリクスを発生させる。いずれか２対のセルに対し、該マトリクスにおける１は隣接性を表わし且つ０は非隣接性を表わす。図１３は該プロトタイプネットワークに対して発生された接近性マトリクスを例示している。各セルは、又、そのセル内に含まれているネットワークの何らかの属性（例えば、容量又は密度）を反映する重み、又は非ゼロ数字を割当てることが可能である。
【００２２】
隣接性関係に基づいてセルの臨界性を識別し且つ測定するために使用可能な統計の幾つかは、程度、中間、近接性、エントロピー、重み付けエントロピーを包含している。セルの程度は、隣接性マトリクスにおいて定義されるように、それに直接隣接しているセルの数として定義される。１個のセルの程度は１個のセル、又はネットワークの一部の局所的連続性の尺度である。中間性及び近接性は社会的ネットワーク理論から派生される２つの指標であり、且つそれらはネットワークの残部に関連してセルの集中性を特性付けるために使用される。１個のセルの近接性集中性は、ネットワークにおける全てのその他のセルに対するそのセルの平均最小距離に基づいている。中間集中性は、１個のセルが全てのその他の対のセルと関連する最小経路に対する中間位置である範囲を測定する。エントロピーはグラフ構造に基づいたネットワークにおける無秩序の尺度であり、その場合に、ある特定のセルに対し、その値は０から１の範囲である。重み付けエントロピー指標もそのエントロピーと容量との積により定義される各セルに対して計算される。
【００２３】
セルディスジョイント経路解析
セルディスジョイント経路解析は、ネットワーク効果及び１つのセルにおけるインフラストラクチャがどのようにしてその他のセルにおけるインフラストラクチャと空間的に関連しているかを解析する。２個又はそれ以上の位置の間でそのセルも経路を共用するものでない場合に、２個又はそれ以上の経路は完全にディスジョイントである。従って、複数の経路により共用されるセルが多ければ多い程、経路のディスジョイントはより少ない。複数の経路がディスジョイントであるものが多ければ多い程、ネットワークは障害に対してより柔軟性がある。何故ならば、障害が複数の経路を故障させる場合のある共用セルがより少ないからである。２つの位置の接続が臨界的である場合には、それらを接続する経路がどのようにディスジョイントであるかを知ることは、それらは接続するネットワークの柔軟性及び信頼性を理解する上で重要である。
【００２４】
図１４はネットワークラインファイル（対角線で示してある）の上に重ねたグリッドを表示している。セルは番号が割当てられている。ネットワークポイントを含むセルはセル内に丸を有している。従って、ネットワークポイントを含むセルは、セル１，５，７，９，１３，１７，１９，２１，２５である。多様な要因に基づいてポイントに対して属性を割当てることも可能である。セル隣接性リスト（即ち、接続性端部リスト）を作成することが可能である。例えば、図１４におけるネットワークに対するセル隣接性リストは以下の通りである。
【００２５】
【表１】
2008509459.tif 000003
【００２６】
セル隣接性リストが作成されると、２つのノードの間のディスジョイント経路の数を計算することが可能である。例えば、図１４において、１つのノードがセル２５及び５の各々の中に位置されている場合には、２５と５との間には１つの経路が存在するに過ぎず、即ち２５，１９，１３，９，５である。従って、その経路内のいずれかのセルが故障すると、セル２５及び５におけるノードは最早互いに通信を行うことができず、ネットワークは故障することとなる。
【００２７】
図１５は同じネットワークに対しての別のリンクの付加を例示している。５，１０，１５，２０，２５をカバーするラインにより表わされる付加的なリンクが該ネットワークに付加されると、計算は異なるものとなる。この新たなネットワークラインの付加により、セル２５と５におけるノードの間には２番目の経路が存在し、即ちその経路は２５，２０，１５，１０，５（垂直線により表わしてある）が存在している。この２番目のリンクはセル２５及び５におけるノードを接続する２番目のルートを付加している。従って、第一経路における１個のセルが故障した場合に、これら２つのノードを接続するための２番目の経路が存在している。このことは、２つのノードを接続するために単に１つの経路ではなく２つの経路が存在しているので、ネットワークの柔軟性は倍化されている。更に、これら２つのリンクは、いずれのセルも共用するものではないという点においてこれら２つのリンクは完全にディスジョイントである。いずれかの１つのセルにおける障害は両方のリンクを故障させることはない。
【００２８】
図１６はリングトポロジィ（セル２，３，４，９，１４，１９，１８，１７，１２，７，そして２へ戻るリングを含む）を例示しており、夫々のクライエントへの２つのラテラル（６及び１５）を有している。リングトポロジィは、クライエントに対し２つの経路を提供するためにしばしばリング状で付設されるテレコミュニケーションネットワークに対して典型的なものである。リングから、クライエントはセル６及び１５により示されるように該リングに対するラテラルにより接続される。セル隣接性リストは以下の通りである。
【００２９】
【表２】
2008509459.tif 000004
【００３０】
論理的ネットワークに対するノードはセル６及び１５であり、何故ならば、これらのノードはラテラルがネットワークに対しクライエントを接続するために設けられているからである。クライエントはラテラルによりネットワークリングにより接続されている位置にノードを有している。これら２つのセルの間のディスジョイント経路はそれ程明らかなものではない。何故ならば、セル７及び１４は２つのノード間の両方の可能な経路のために必要とされるからである。このような場合に、経路のセルディスジョイント性を計算するために以下の式を使用することが可能である。
【００３１】
【数１】
2008509459.tif 000005
【００３２】
尚、ｊは２つの経路の共通セルにわたっての和であり、ｉは２つの経路のセルにわたっての和であり、ＥＤは端部ディスジョイント性であり、ｌjは共用リンク又はセルであり、ｌiは非共用リンク又はセルである。図１６に例示した例の場合には、セル７及び１４は両方の経路に対して必要とされ、従ってｌjは２である。これらの経路におけるセルの総数は１２であり、従ってｌiは１２である。従って、ＥＤ＝１−（２／１２）＝０．８３３である。従って、これらの経路は８３．３％ディスジョイントである。
【００３３】
ノード間の複数の経路がディスジョイントである数が多ければ多い程、そのネットワークは一層柔軟性がある。何故ならば、ネットワーク内の１個を超える経路／ルートを故障させることが可能な共用セルの数がより少ないからである。高レベルのディスジョイント性を有するネットワーク経路は、低レベルのディスジョイント性を有する経路よりも障害の危険度はより低い。このアプローチは、グリッド及びその隣接セルがネットワークへ後戻りすることを可能とし、且つ理論的手段をグラフ化し且つ従来のマトリクスにおける解析のために使用することが可能である。これは次の部分において概説するように障害シミュレーションを実施することを可能とする。
【００３４】
ネットワーク障害シミュレーション
１つのネットワーク又は１組の相互に関連したネットワークの誤差許容範囲及び攻撃許容範囲は、上述したセル臨界性のランク付けを使用し、それらをグリッドから逐次的に除去し、且つそれらが除去されるに従いネットワークの異なる特性を検査することにより解析することが可能である。観察することが可能な幾つかの特性が存在しており、且つこれらのうちの幾つかは、直径、平均測地距離、小国分割（ｂａｌｋａｎｉｚａｔｉｏｎ）の程度、抱き合わせ（ｃｏｈｅｓｉｏｎ）及び距離フラグメンテーションを包含している。直径はルートを構成するリンクの数により測定されるネットワークにおける２つのノード間を移動するのに必要な最大距離であり、且つ平均測地距離はネットワーク内のノードの全ての組合わせの間のリンクにおける平均距離である。小国分割の程度は、シミュレーションにおける任意の点においての、サブネットワーク、即ちネットワークの切断した部分の数である。抱き合わせ及び距離フラグメンテーションは、社会的ネットワーク理論から派生される接続性の尺度である。
【００３５】
セルは、臨界性及び観察されるネットワークの劣化に基づいて逐次的に除去される。このことは、図１２に示したプロトタイプネットワーク及び前のセクションにおいて説明したセル臨界性の尺度を使用して証明される。図１７−２１は、臨界性の各尺度に対し、トップテンの最も臨界的なセルが順番に除去される場合の結果を例示している。図１７は直径を例示している。図１８は平均測地距離を表わしている。図１９はネットワークの小国分割を例示している。図２０は抱き合わせを例示している。ｎ項のネットワーク柔軟性。図２１は距離フラグメンテーションを例示している。このプロトタイプネットワークに対するシミュレーションの結果は、使用した６個の臨界性指標のうちで、程度が、検査したグローバル特性の全てに関して最も直接的な負の影響を有しているものと思われる。エントロピーも強い負の影響を有しているが、その効果は一層遅延されている。
【００３６】
結論
本発明の種々の実施例について上述したが、それらは例示として提示されたものであり制限としてではないことを理解すべきである。当業者に明らかなように、本発明の精神及び範囲から逸脱することなしに形態及び詳細においての種々の変更を行うことが可能である。従って、本発明は上述した例示的実施例のいずれかにより制限されるべきものではない。
【００３７】
更に、理解すべきことであるが、本発明の機能性及び利点をハイライトした上述した図面は単に例示的な目的のために提示したものである。本発明のアーキテクチャは充分に柔軟性及び形態特定可能なものであり、従ってそれは図面に示したもの以外の態様で利用することが可能である。
【００３８】
更に、要約の目的は、一般的に、米国特許庁及び公衆、特に、特許又は法律用語又は専門用語に精通していない科学者、エンジニア及び実務者が、本願の技術的開示の性質及び基本をおおまかな検査から迅速に決定することを可能とすることである。要約は何等本発明の範囲を制限するものとして意図しているものではない。
【図面の簡単な説明】
【００３９】
【図１】本発明の１実施例に基づいてネットワークをマッピングし且つ解析するシステムを例示した概略図。
【図２】本発明の１実施例に基づく属性情報を有するグリッドの１例を例示した概略図。
【図３】本発明の１実施例に基づくネットワークをマッピングし且つ解析する方法を例示した概略図。
【図４】本発明の１実施例に基づいてネットワークをマッピングし且つ解析する方法の１例を例示した概略図。
【図５】本発明の１実施例に基づいてネットワークをマッピングし且つ解析する方法の１例を例示した概略図。
【図６】本発明の１実施例に基づく密度解析の１例を例示した概略図。
【図７】本発明の１実施例に基づく重み付け密度解析を例示した概略図。
【図８】本発明の１実施例に基づく重み付け密度解析を例示した概略図。
【図９】本発明の１実施例に基づく重み付け密度解析を例示した概略図。
【図１０】本発明の１実施例に基づいて相互依存性解析の１例を例示した概略図。
【図１１】本発明の１実施例に基づいて相互依存性解析の１例を例示した概略図。
【図１２】本発明の１実施例に基づくチョークポイント解析の例を例示した概略図。
【図１３】本発明の１実施例に基づくチョークポイント解析の例を例示した概略図。
【図１４】本発明の１実施例に基づくセルディスジョイント経路解析の例を例示した概略図。
【図１５】本発明の１実施例に基づくセルディスジョイント経路解析の例を例示した概略図。
【図１６】本発明の１実施例に基づくセルディスジョイント経路解析の例を例示した概略図。
【図１７】本発明の１実施例に基づくネットワーク障害シミュレーションの特徴を例示した概略図。
【図１８】本発明の１実施例に基づくネットワーク障害シミュレーションの特徴を例示した概略図。
【図１９】本発明の１実施例に基づくネットワーク障害シミュレーションの特徴を例示した概略図。
【図２０】本発明の１実施例に基づくネットワーク障害シミュレーションの特徴を例示した概略図。
【図２１】本発明の１実施例に基づくネットワーク障害シミュレーションの特徴を例示した概略図。
【図１】
2008509459.tif 000006
【図２】
2008509459.tif 000007
【図３】
2008509459.tif 000008
【図４】
2008509459.tif 000009
【図５】
2008509459.tif 000010
【図１２】
2008509459.tif 000011
【図１３】
2008509459.tif 000012
【図１４】
2008509459.tif 000013
【図１５】
2008509459.tif 000014
【図１６】
2008509459.tif 000015
【図６】
2008509459.tif 000016
【図７】
2008509459.tif 000017
【図８】
2008509459.tif 000018
【図９】
2008509459.tif 000019
【図１０】
2008509459.tif 000020
【図１１】
2008509459.tif 000021
【図１７】
2008509459.tif 000022
【図１８】
2008509459.tif 000023
【図１９】
2008509459.tif 000024
【図２０】
2008509459.tif 000025
【図２１】
2008509459.tif 000026
【国際調査報告】
2008509459.tif 000027