多重接続ネットワーク合成アルゴリズム

エントリー

個人的には、インターネット上または工科大学での学習過程で、多重接続されたネットワークを合成するための「公式」アルゴリズムには遭遇していません。 登録された特許取得済みのアルゴリズムよりも、複数接続されたネットワークを構築する方法があります。 このようなタスクに出会ったことがない人のために、それは主にさまざまな規模の通信ネットワークのモデリングと設計のプロセスで発生することに注意したいです。 実際にそのようなモデリングのプロセスで得られたプロジェクトを実現するかどうかは、主にその目標に依存します。 これが電気通信を専門とする学生の学期論文である場合、以下で説明する推奨事項は非常に当てはまります。 全国規模または少なくとも都市規模のネットワークの設計に関与する組織は、複数の接続ネットワークを構築するための実用的な方法を使用しますが、記事に記載されている情報が役立つ可能性があります。



アルゴリズム

ドネツク国立工科大学では、TCS（電気通信システムおよびネットワーク）の専門分野で、「ネットワーク理論」コースの一環として、多重接続ネットワークを構築する次のシーケンス（アルゴリズム）が教えられています。



0）ソースデータは、ネットワークのエンドオブジェクト間の距離（L）の行列です（実際には、たとえば、ルーターはそれらの役割を果たすことができます）。 マトリックスは正方形で、各要素（Lij = Lji）はi番目とj番目のノード間の距離（メートル、キロメートル）に等しくなります。 Lii = Ljj = 0-現在のノードからそれ自体までの距離。 このマトリックスに基づいて、情報転送媒体（ケーブル通信回線とする）を選択し、距離にケーブルのメートル単位またはキロメートル単位のコストの条件付き単位または実単位を掛けることにより、コストマトリックス（C）を構築できます。



1）基本トポロジー（Cb）のマトリックスを作成します。 これらのオプションのいずれかを基本トポロジーとして使用することをお勧めします-最適なリング、最小スパニングツリー、およびスター。 これらの各オプションの基本的なトポロジのマトリックスを構築するために、この記事で説明されていないアルゴリズムがあります。 これらのトポロジを構築する原理は同じである、つまり、特定のトポロジ内のノード間の最小距離であり、それぞれの基本的な特性が異なるというだけです。 最適なリングの場合、このようなプロパティはノード間の2つの異なるパスの存在であり、これにより重複が保証されます。スターの場合は、すべての情報フローが通過する中央ノードの存在を意味します。最小限のスパニングツリーの場合、トポロジには閉じたパス（ループ）がありません



2）制限基準に従って、基本トポロジのマトリックスに追加の分岐を導入することによる多重接続ネットワークの実際の構築。これに達すると、多重接続ネットワークが構築されると見なされます。 そのような基準として、中間ノード（Kij）の数は、選択された2つのノードiとjの間のパスで選択され（言い換えると、基準は「再試行回数」）、ブランチをネットワークに導入するコストです。 したがって、パラメーターKに特定の制限を設定し、このアルゴリズムの各ステップでマトリックス（C）から最小要素を選択することにより、中間ではあるが最適ではない（！）場所を占める多重接続ネットワークを徐々に取得します。コストと2つのノード間の情報の再試行回数。 ネットワークのすべてのノードで基準（K）によって指定された制限に達すると、多重接続されたネットワークは準備完了と見なされます。



上記のアルゴリズムの提案された拡張

改善は一見簡単です。 -上記の方法の2番目の段落では、アルゴリズムの各ステップで行列（C）から最小値（inputable=ijmin）ではなく、基準最小（（ij/ Cmin）+（Wmax / Wij）に対応するノードを多重接続ネットワークに入力することを提案します。ここで、ijは基準の順守をチェックする行列の要素（C）、Cminはアルゴリズムのこのステップでのコスト行列の最小要素（C）、Wijは分岐ij、Wmaxに入る前のネットワークの状態と比較した再試行回数（パラメーターK）の変化を示す値です現在のパラメータWの可能な最大変化 そのネットワークの状態。

この改善を実装するために、アルゴリズムの各ステップでネットワークの現在の状態が再計算され、マトリックスWが構築されます。これは、Cij要素が導入されたときにネットワークのすべての要素のパラメーターKの変化を反映し、そこからWijおよびWmax要素が取得されます。 アルゴリズムのステップはサブステップに分割され、その数はネットワークのサイズに依存します。



これは提案された方法の単なる一般的な説明です。 ソフトウェアの実装には、他の多くの中間行列の構築、および記事で指定されていないアルゴリズム（フロイドのアルゴリズムなど）の適用が含まれます。

多重接続ネットワークを構築するこの方法により、コストと中間ノードの数に応じた最適なネットワークではないにしても、比較的優れたネットワークを取得できます-それは確かです。 この方法の欠点は、最初のオプションと比較して計算が複雑なことです。ソフトウェアを実装しないと、比較的ノード数の少ないネットワークにも適用することは非常に困難です。



Creative Commons Attribution-Share Alikeでライセンスされたテキスト