SDNアプリケーションルーティングアルゴリズムを実装するためのツールであるNetworkx

SDN (ソフトウェア定義ネットワーク) は、集中制御プレーンを通じてデータ層転送やその他の操作を管理する新しいタイプのネットワーク アーキテクチャです。ネットワーク接続は最も基本的な要件です。ネットワーク接続を確保するには、コントローラーは対応するグラフ理論アルゴリズムを適用して転送パスを計算し、データ転送を完了する必要があります。 SDN アプリケーションを開発する場合、開発者は基本的なパス計算を完了するためにネットワーク アルゴリズムを独自に記述する必要があることがよくあります。これは面倒なだけでなく、パフォーマンスとコードの再利用性は開発者の個人的なプログラミング レベルにも影響されます。そこで、この記事では、パスアルゴリズムの開発を完了するために使用されるネットワークアルゴリズムツール networkx を紹介します。

Networkx は、複雑なネットワークのダイナミクス、構造、機能性を作成、操作、研究するための Python 言語パッケージです。 Networkx は、単純な無向グラフ、有向グラフ、マルチグラフの作成をサポートします。多くの標準的なグラフ理論アルゴリズムが組み込まれており、ノードは画像ファイルなどの任意のデータにすることができます。任意のエッジ値の次元をサポートし、機能が豊富で使いやすいです。

Networkx コードは何度もテストされ、パフォーマンスに関して多くの作業が行われているため、Networkx に組み込まれているさまざまなグラフ理論アルゴリズムを使用すると、SDN アプリケーションの開発に多くの利便性がもたらされ、開発時間が節約され、コード障害率が低減されます。読者は公式ウェブサイトのドキュメントから networkx のインストールと使用方法を簡単に理解できるので、ここでは詳細には触れません。以下のコンテンツでは、最短経路、KSP (K 最短経路) アルゴリズム、トラバーサル アルゴリズム BFS (幅優先探索)/DFS (深さ優先探索) など、Networkx の古典的なグラフ理論アルゴリズムについて簡単に紹介します。

最短経路アルゴリズム ダイクストラとフロイド

単一のソースから他のすべてのノードまでの最短パスを計算する Dijkstra アルゴリズムと、すべてのノード間の最短パスを計算する Floyd アルゴリズムは、最も古典的なネットワーク アルゴリズムの 1 つです。 networkx における両方の実装を以下に紹介します。

ダイクストラ

Dijkstra アルゴリズムは有向グラフと無向グラフの両方に使用できます。ここで、G は networkx によって生成されたグラフ データ構造です。ソースは開始点であり、ターゲットは終了点です。開始点、終了点、重みはオプションのパラメータです。

networkx.shortest_path(G、ソース=なし、ターゲット=なし、重み=なし)

重み付けなしグラフ

networkx.single_source_shortest_path(G, ソース[, カットオフ])

地図の権利

networkx.dijkstra_path(G、ソース、ターゲット、重み='重み')

フロイド

フロイドのアルゴリズムには、重みなしグラフと重み付きグラフの 2 つの実装があります。

重み付けなしグラフ

ネットワークx.all_pairs_shortest_path(G[, カットオフ])

地図の権利

networkx.all_pairs_dijkstra_path(G[, カットオフ, 重み])

パスの長さを計算するには、network.XXX_length 関数を呼び出します。ここで、XXX は対応するパス計算アルゴリズムの名前です。上記のアルゴリズムに加えて、networkx では、同じ長さの複数の *** パスを返すアルゴリズムなど、多くのニーズを満たすためのさまざまな関数も設計されています。読者は、ニーズに応じて学習コンテンツをカスタマイズできます。

K最短経路

ネットワークルーティングアルゴリズム/転送アルゴリズムを研究する場合、ホップ数を最適パスの計算基準として使用するほか、帯域幅、レイテンシなど、他の多くの指標も使用されます。複数の指標に基づいて多次元評価システムを構築し、重み付け値を計算して最適パスを計算することもできます。たとえば、帯域幅が基準となる場合、計算量は多くなります。まず、ネットワーク リンクの残りの帯域幅データを取得し、ソースから開始して、パスの中で最も帯域幅が高いパスを選択します。リンクの最大残存帯域幅は、残存帯域幅が最も小さいリンクに依存するため、貪欲アルゴリズムを使用してホップを 1 つずつ削除すると、計算エラーが発生する可能性があります。したがって、分岐が発生するたびにパスを選択し、選択されていない他のパスのデータを保存する必要があります。すべてのリンクが比較的完了するまで、各ノードはすべてのデータを比較し、その時点で最適なパスを選択する必要があります。このようなアルゴリズムは、ダイクストラ アルゴリズムを変更することで実装できます。ロジックは難しくありませんが、効率は高くありません。具体的な実装については詳しく説明しません。読者は、インターネットで見つけた入門記事「SDN ベースの最短経路アルゴリズム (ダイクストラ) ダイクストラ」を参照してください。

研究の過程で、論文で言及されている多くの方法が、トポロジカル情報アルゴリズム K 最短パスに基づいて、帯域幅に基づいて最適なパスを計算することがわかりました。アルゴリズムに従って、これらの K パスの中から最適なパスを直接選択することも、重みを設定し、ホップ数と帯域幅の加重値を計算して、最適なパスを選択することもできます。ホップ数と帯域幅の値が大きく異なるため、両方を正規化/正則化する必要があります。

ホップ数を考慮する理由は、パケットがスイッチを通過するたびに消費されるリソースが増えるため、考慮する必要があるためです。たとえば、パス A の帯域幅は 100M、ホップ数は 2 です。パス B の帯域幅は 110M、ホップ数は 5 です。帯域幅に基づいて選択する場合は、パス B を選択します。ただし、パス B が通過するパスはパス A の数倍であり、より多くのリソースを消費し、より多くの伝送遅延と伝播遅延が発生します (5 ホップのリンク長が 2 より大きいと仮定します。そうでない場合は当てはまりません)。したがって、すべての要素を考慮すると、パス A の方が適している可能性があります。

伝統的な KSP アルゴリズムは数多くあります。1971 年に Yen, Jin Y が発表した論文「ネットワーク内の k 最短ループレス パスの検索」で提案された Yen のアルゴリズムは、古典的なアルゴリズムの 1 つです。読者は、Yen のアルゴリズムの wiki を直接クリックして、それを表示できます。アルゴリズムは複雑ではありません。基本的な考え方は次のとおりです。

ダイクストラ法は最初の最適な経路を選択し、それをA[0]として保存する。

外側のループ、k は 1 から k まで。 内側のループでは、k-1番目（前）のルートパスがパスとして使用され、パスの最初のポイントが分岐ノードとして使用されます。分岐ノードの前の部分は、前のルートパスと現在のパスと一致する部分であり、ルートパスと呼ばれます。分岐点で選択されたルートパスの分岐は削除され（重みは正の無限大に設定され）、次にダイクストラ法が計算され、パスの計算結果が一時データ構造Bに配置されます。ループが進むにつれて、分岐点は終了点の前のジャンプまで前進し続けます。内側のループが比較され、複数の潜在的なルートパスが選択されています。

一時データ構造 B 内のパスをソートし、最適なパスを見つけてそれを A データ構造に追加し、A[k] として保存すると、外側のループが終了します。

外側のループは、K 個の最適なパスが見つかるまで続きます。

Networkx は KSP アルゴリズムを実装しました。アルゴリズム パッチは 2015 年 4 月頃に networkx プロジェクトに追加されました。networkx では all_shrtest_paths という名前が使用されているため、networkx に新しく追加されたアルゴリズムの対応する関数の名前は all_simple_pay です。具体的なパラメータは次のとおりです。

all_simple_paths(G、ソース、ターゲット、カットオフ=なし)

ここで、G は networkx のグラフ データ構造、source は開始点、target は終了点、cutoff は検索の深さであり、cutoff よりも短い長さのパスのみが返されます。パフォーマンスを最適化するために、関数の戻り値はジェネレータです。読者は for ループを使用して、対応する K 最短パスを生成できます。ジェネレータを使用すると、すべての結果を一度にメモリに書き込むのではなく、結果を 1 つずつ計算できるため、メモリの使用量を大幅に削減できます。

トラバーサル

一部のネットワーク アプリケーション シナリオでは、BFS (幅優先探索)/DFS (深さ優先探索) アルゴリズムなどのトラバーサル アルゴリズムが使用されます。Networkx は対応する関数を定義しています。スペースの制限により、具体的な内容はここでは紹介しません。読者は学習のために、公式の networkx ドキュメントにあるトラバーサルに関するドキュメントを参照できます。

要約する

SDN アプリケーションを開発する場合、ネットワーク接続は最も基本的な要件です。ネットワークアプリケーションを開発する場合、networkx を使用するとネットワークデータの保存やパスの計算などが可能になり、開発効率が大幅に向上します。学習の過程で、私は常に車輪の再発明を繰り返すことから、徐々に成熟したオープンソース ソフトウェアを使用するようになりました。多くのツールに触れ、多くの有用な知識を学びました。独自のホイールを構築する場合、パフォーマンス、適用性、インターフェースの安定性が大きなテストになることがよくあります。優れたオープンソースツールを徐々に試していくことが、今後のプログラミング学習の方向性になるでしょう。