DxRアルゴリズムのアイデアに基づいて設計されたルーティングアイテム配置構造の図

まず、タイトルには、検索構造ではなく、ルーティング項目の配置構造と書かれています。つまり、この構造を使用して IPv4 アドレスを入力として取得すると、次のホップを取得するプロセスで検索操作は行われません。インデックス配置を継続的に使用する必要があるだけです。まず直感的に理解できるように、検索構造図を示します。

1. マルチレベルインデックスから始めましょう

私の失敗した経験では、MMU を完全に模倣してルーティング検索構造を設計しようとしましたが、失敗しました。実は、今考えてみると、ルーティング項目の数が限られているため、失敗ではありません。4G IPv4 アドレス全体と比較すると、その数は無視できるほどです。したがって、マルチレベルインデックスを引き続き使用できます。 16-16の二次セグメンテーションでも効果は良好で、構築と検索構造の理解は難しくありません。しかし、メモリ使用量を計算してみましょう。64k の第 1 レベル インデックス テーブルが必要です。プレフィックス長が 16 を超えるルーティング項目の数 N に応じて、N 個の 64k 第 2 レベル テーブル項目が分割され、終了します。合計 N+1 個の 64k テーブル項目があります。第 1 レベル インデックスは、少なくとも 4 バイトである第 2 レベル テーブルのアドレスを指します。第 2 レベル テーブル項目は、ネクスト ホップ テーブルのインデックスを指すことができます。直接接続されたネクスト ホップの数が 256 を超えないことを考えると、1 バイトで十分です。

多段テーブルを使用する場合でも問題ありません。しかし、より最適化された方法があります。なぜなら、非常に多くのテーブルでは多くのコンテンツが繰り返されていることがわかるからです。必要なのは、重複データを圧縮するためにさらにいくつかのテーブルを導入することです。

2. DxRアルゴリズムについてお話しましょう

この記事では、単なるアイデアではなく、DxR の実際の構造をようやく紹介できるようになりました。次の図に示すように:

私が言いたいのは、「もし」実際にこれが唯一残されたステップだということです。間隔 idx に素早くインデックスを付ける方法を見つけられれば、問題は解決します。 #p#

3. 直感的な概念

二次構造は維持されますが、N 個の二次テーブルを圧縮する方法を見つける必要があります。どのくらいの圧縮がいいのか？だから容赦なく1にしておきましょう！どうやってやるか？それは後で考えましょう！

セカンダリ テーブルは 1 つしかないため、以前の N 個のセカンダリ テーブルの内容を 1 つの場所、つまり別のテーブル セットに圧縮する方法を見つける必要があります。

主要な表の中間点間隔の数と位置を知っているという事実を理解することが重要です。位置は、プライマリインデックスを通じて前処理中に特定でき、数量は前処理中にカウントできます。

この事実は非常に重要なので、プライマリ インデックス テーブル内のすべてのポイント間隔に順番に番号を付け、ポイント間隔に対応するインデックス エントリに番号を保存します。この事実を理解した後、次にそれをどのように使用するかを考えました。このとき、別の事実が徐々に浮かび上がりました。つまり、セカンダリテーブルは1つだけであり、すべてのプライマリテーブルインデックスの各ポイント間隔に対して、対応する下位16ビットのセカンダリテーブルスペースも0〜65535のアドレスサブスペースです。

そこで、問題はそれらをどのように区別するかであり、この時点で、先ほど認識した最初の事実が役に立ちます。はい！つまり、プライマリ テーブル インデックスのポイント間隔番号を使用して、セカンダリ テーブルによってインデックス付けされたテーブルにインデックスを付けます。このテーブルは、明らかに間隔ネクスト ホップ関連付けテーブルです。全体的な概略図は次のとおりです。

配列の添え字アドレス指定を使用する最終的な目標は、スパース データを密なデータに変換することであることがわかります。これが不可能な場合は、共有データを抽出するために追加のテーブルを導入する必要があります。

4. 低域分割法

これからは、ルーティング テーブルを転送テーブルと呼ぶことにします。ルーティング テーブルは前処理後に転送テーブルに完全に変換されているためです。

この時点で、転送テーブルの前処理で最も重要なステップ、つまり低区間の分割方法を提供できれば、転送テーブルはほぼ構築できます。建設プロセスは下の図に示されています

この構成の理由は、第 2 レベルの低間隔テーブルが 1 つしかないためです。異なる第 1 レベルのポイント間隔の低間隔は、数量と分布の点で異なるため、つまり、各第 1 レベルのポイント間隔には独自の独立した低間隔があります。このように、単一の低間隔テーブルを使用して、複数の第 1 レベルのポイント間隔から派生した低間隔をインデックスする方法はありません。したがって、これらすべての独立した低間隔セットを同じ 16 ビット ドメインにマッピングする必要があり、マッピング プロセスは上の図に示すプロセスです。このプロセスを言葉で説明すると、次のようになります。

1) M個の第1レベル点間隔に対応するすべての低間隔分割点要素を集合Sに入れる。

2). 集合 S をソートし、重複する要素を削除します。S の要素数は N です。

3) N 個の関連テーブルを構築し、各関連テーブル n の要素を第 1 レベルのポイント間隔インデックスの順序で配置します。ここで、次のホップ インデックスは、下位の間隔がマージされる前に保存されるか (分割ポイントは下位の間隔に固有)、または関連テーブル n-1 の対応する添字で次のホップを継承します (分割ポイントは、統一されたマッピングのためにハード配置されます)。

この時点で、DxR のアイデアと私の低範囲マージのアイデアを比較することができます。

DxR の考え方: 第 1 レベルのポイント間隔に対応する第 2 レベルの低間隔はすべて別々に配置されます。すべての低間隔が同じ 16 ビット ドメインにあるため、それらの間には DxR アルゴリズムが検出できない重大なデータ冗長性が存在する可能性があります。

低区間をマージするアイデア：第1レベルのポイント区間に対応する第2レベルの低区間はすべて均一に配置されているため、冗長なデータを削除できます。たとえば、1.2.3.0/24と2.2.3.0/24の低区間分割ポイントはどちらも3.0/8です。これらは明らかにマージできますが、大きな区間を複数の小さな区間に分割することもできます...

例を挙げると、低間隔セグメンテーションポイントシーケンスに対応する第 1 レベルのポイント間隔は次の 4 つあります。

ポイント間隔1: 0,1,3,4,7,8,16,32

ポイント間隔2: 0,3,7,8,20,25,32

ポイント間隔3: 0,2,4,24,32

ポイント間隔4: 0,7,16,32

DxRアルゴリズムの場合、上記の分割ポイントはすべて区間表に書き込まれることは明らかです: 0,1,3,4,7,8,16,32|0,3,7,8,20,25,32|0,2,4,24,32|0,7,16,32

低間隔マージ法では、マージされる間隔は0、1、2、3、4、7、8、16、20、24、25、32です。

多くの冗長な区間分割ポイントが排除されていることがわかりますが、すべてのポイント区間で、いくつかの低い区間がまったく同じ 2 つに分割されています。 もちろん、次のホップもまったく同じです... これは代償であり、小さな代償ですが、支払わなければならない代償です。 #p#

5. 次のホップのロケーション構造

書くインクもあまり残っていないし、電車の中では長々と書くこともできない。問題は、データ通信が不安定なので、オフラインでしか書けないということ。実際、現在のモバイル IP はひどいです。高速鉄道が高速で移動する場合、アプリケーション層が中断されないことを保証できません。だから、あまり言わないほうがいいです。一人でいるときは用心深くなる？ああ、いやだ！

私のこの技術はどれほど優れているでしょうか。少なくとも、すべての検索操作を拒否し、純粋な位置決めだけを行うと言えます。しかし、膨大な貴重なスペースを、恥ずべき時間と引き換えにしているのでしょうか。いいえ、違います。では、DxR アルゴリズムのメモリ使用量を見てみましょう。この数値は http://www.nxlab.fer.hr/dxr/ から取得しました。

16-16セグメンテーションを例にとると、その間隔テーブルの占有率は64kのほぼ3〜4倍です。私のデータ構造内のセカンダリテーブルと関連テーブルの合計メモリ使用量もこの桁であることを証明できれば、私は勝ちです（以前、Huaweiの人が、転送テーブルを設計するためにマルチレベルインデックスアルゴリズムを使用して提唱する論文を書きましたが、私はこのソリューションを軽蔑しています。 DxRまたは私のソリューションの空間計算量を計算するだけで、Huaweiの人々でさえ手の届かないところではないことがわかります...多くの国内論文は常に世界を欺き、評判を盗んでいると疑われています。回転式リフティングシートは間違いなく爆発します、待ってください）。私の勝利の前提は、私​​が「アルゴリズム」を一切使用せず、インデックスに基づいて位置を特定したことです。ただし、メモリは余分に使用しませんでした。

DxR アルゴリズムでは、間隔テーブルの数は、すべてのプライマリ インデックス テーブル内の中間間隔で割ったセカンダリ間隔の合計です。実際には、シグマ記号を使用して数式を書くこともできますが、スクリーンショットを撮る必要があるため、忘れてください。そこで、言葉で表現します。第 1 レベルのポイント間隔 1 の a 要素低間隔配列 + ポイント間隔 2 の b 要素低間隔配列 + ポイント間隔 3 の c 要素低間隔配列... + ポイント間隔 M の x 要素低間隔配列

私のアルゴリズムでは、64k の固定サイズの一意のセカンダリ インデックス テーブルが使用されていますが、関連付けられているテーブルの数は固定されていません。関連付けられているテーブルの数は、マージ後の低間隔の数であり、各関連付けられているテーブルのサイズは、プライマリ インデックス テーブル内のポイント間隔の数です。計算式は次のとおりです。

M 個の低間隔 a、b、c、... x を結合した後の新しい間隔 1 の M 要素配列 + M 個の低間隔 a、b、c、... x を結合した後の新しい間隔 2 の M 要素配列.... + M 個の低間隔 a、b、c、... x を結合した後の新しい間隔 N の M 要素配列

Python スクリプトを書いて結果を計算してみました。ほとんどのルーティング項目が均等に配置されている場合、私のソリューションは DxR よりもスペースをあまり取らないことがわかりました... すごいですね! この実践的な作業は Python の学習を促進しました。

6. 転送テーブルとルーティングテーブル

本来はこのセクションを完全な記事として書きたかったのですが、今は高速列車に乗っており、隣に座っている人に笑われるのが怖くて（実際、確率的には80％の人は私が何を書いているのか分かりませんが…）、プロジェクトレポートという形でしか書けません。爆発！

Linux では、ルーティング テーブルは転送テーブルです。すべてのデータ パケットはこのテーブルを照会する必要があります (ルーティング キャッシュについては触れないでください。これは削除されました。なぜでしょうか。特に P2P 環境では、アプリケーションの多様性を考慮すると、データ パケットの時間的局所性はもはや前提条件ではないため、...)。これにより問題が発生します... ルーティング テーブルにはプレフィックスとネクスト ホップのマッピングが格納されており、データ パケットはそのようなルーティング項目を見つける必要があるため、一連の検索プロセスが必要になります...

ルーティング項目に対して一連の前処理を実行しないのはなぜでしょうか。その結果、IP アドレスが直接次のホップを見つけられるようになります。IP アドレスを「最速」で次のホップにマップできるテーブルを作成できれば、住宅ローンを返済し、娘を何のプレッシャーもなく育てられるだろうと考えました... しかし、これは馬鹿でも思いつくアイデアなので、私は間違っていました。今書きましたが、もし30年早く生まれていたら、私は今頃おじいさんになっていたでしょう…

次ホップを「最速」で直接見つける方法は 2 つあります。1 つ目は、厳しいスペース要件のある厳しい環境で、より効率的なアルゴリズムを使用することです。2 つ目は、貴重な時間を節約するために多くのスペースを使用することです。しかし、私の解決策は、わずかなスペースを使用してルーティング場所を完全にインデックス化することです。

ルーティング テーブルとは何ですか? プロトコル スタックの IP 層のコントロール プレーンの内容です。転送テーブルとは何ですか? プロトコル スタックの IP 層のデータ プレーンの内容です。この違いを理解することで、ルーティング テーブルのデータ構造が固定されている場合でも、転送テーブルを可能な限り最適化できます。つまり、ルーティング テーブルでは追加、削除、更新操作に対して高い効率が求められ、転送テーブルではクエリ操作に対して高い効率が求められます。ルーティング テーブルが安定している場合は、それを「ゆっくり」転送テーブルに変換できます。 Linux はルーティング テーブルと転送テーブルを区別しません (Linux のルーティング キャッシュを転送テーブルと考えないでください)。これは、一般的なオペレーティング システム カーネル プロトコル スタックの一般的な方法であり、プロフェッショナル ルーター オペレーティング システムの方法ではありません。プロフェッショナル ルーター オペレーティング システムのカーネル プロトコル スタックは、多くの場合、コントロール プレーンと管理プレーンにのみ焦点を当てていますが、データ プレーンの操作はオペレーティング システム プロトコル スタックではまったく完了せず、専用のハードウェアまたはソフトウェア サブシステムによって完了するためです。コントロール プレーンと管理プレーンは何を制御および管理するのでしょうか。それはデータ プレーンです。#p#

7. 16対16で分割する必要がありますか？

上記のプライマリ インデックス テーブルとセカンダリ インデックス テーブルでは、常に 16 ビット - 16 ビットのセグメンテーションを使用してきましたが、これが唯一の方法であるように思われますが、実際にはそうではありません。結局のところ、私のアイデアの一部は DxR から来ており、別の部分は間隔ビットマップ マッチングから来ており、別の部分は MMU から来ています。これらのどれであっても、第 1 レベルのインデックスの長さは固定されておらず、間隔ビットマップ インデックスは必ずしも固定長のインデックスである必要はありません。

第 1 レベル インデックスの長さは、ルーティング項目の分布と CPU キャッシュ ラインの状況に基づいて分析できます。たとえば、プレフィックス長が 16 ～ 20 のルーティング項目が多数ある場合は、マージされた第 2 レベルの低間隔の数を減らすことができるため、20 ビットの第 1 レベル インデックスを使用できます。さらに柔軟性を高めるには、第 1 レベルのインデックス テーブルで 2 ビットのデータを追加します。00 は、第 1 レベルのインデックスが次のホップを直接インデックスすることを示し、01 は、第 1 レベルのインデックスが低間隔のインデックスに使用されることを示し、10 は、第 1 レベルのインデックスが DxR 間隔テーブルの開始と終了を見つけるために使用されることを示します。つまり、DxR アルゴリズムを使用して、最初のアイデアは、次のシーケンスを使用して、第 1 レベルのインデックス テーブル項目の 2 ビットのデータを動的に変換することです。

1) 2ビットデータ設定の基礎となるオフライン統計

一定期間のオフライン統計に基づいて、最も頻繁にヒットしない (セカンダリ ロー インターバルでの分割数を増やすだけ)、絶対値が最も低い (つまり、これらのルーティング アイテムには時間的局所性がなく、遅延は許容範囲内である)、ハッシュされたプレフィックス分布が最も高い (分散しすぎる分布は、これらのルーティング アイテムが原因でセカンダリ ロー インターバルが多数の小さなブロックに分割されることを意味する) 上位 K 個のルーティング アイテム (KD ツリー アルゴリズムを含む) を取得します。これら 3 つの指標は重み付けして平均化することができ、重みはカスタマイズできます。同時に、上記 3 つの指標の他の極値をカウントし、D 個のルーティング項目を取得し、D 個のルーティング項目のうちプレフィックス長が昇順で並べられた m 個のルーティング項目をカウントします。

2). DxR間隔テーブルを設定する

K ルーティング項目のプライマリ インデックスの 2 ビット インジケータ ビットが 10 に設定され、DxR 間隔テーブルが設定されます。これらの K ルーティング項目は、使用頻度が最も低く、断片化されており、高い確率で遅延を許容できるため、ゆっくりとバイナリ検索を実行します。これにより、二次低間隔の過剰なカットによるメモリ使用量の増加が防止されます。

3). 第1レベルのインデックスビット長を設定する

m 個のルーティング項目の最長プレフィックスの長さが第 1 レベル インデックスの長さとして使用され、これらのルーティング項目の次のホップが最小 CPU サイクル内で第 1 レベル インデックス テーブル項目によって直接特定されることが保証されます。

4). セカンダリローレンジを設定する

残りのすべてのルーティング項目では、二次配置に私の方法を使用します。

8. 終わり

この記事には技術的な内容や技術的な限界はあまりありませんが、多くの時間を費やしました。この考えは長い間私の心の中にありました。すべては、一銭も稼げない、純粋に手助けするための個人的な仕事から始まりました... モノのインターネットの時代では、すべてが 20 年前に戻って最初からやり直したかのようです。メモリは要求が厳しく、遅延は許容できません... 当然、ルーティング サブシステムは、ハイエンドのコア ネットワーク管理者だけが触れることができる聖なる遺物ではなくなりました。HASH であれ LC-Trie であれ、Linux カーネルのアルゴリズムを理解したり、説明したり、移植したり、記述したりできることに限定されることはもうありません... 私が探しているのは、時間の複雑さを無視する位置決め構造であり、検索構造ではありません。これは、設計ではなく、見つけることであることに注意してください。しかし、これは必然的に空間の複雑さの問題に遭遇します... 私の考えを整理するのに役立ったのは Huawei の人々でしたが、どうしても彼の方法を賞賛することはできません...

ずっと考えていたのですが、今週北京に出張すると聞いて初めて書き始めました。今回は少し時間を作れるはずだと思いました。北京行きの高速列車に乗って出発し、仕事が終わったらホテルに行って絵を描き、考えを整理し始めました。ようやく少しロジックができて、それから前処理済みのテスト構造プログラムを手作業で書きました。難しいのは前処理にあることに注意してください。この前処理プログラムを書くのにあまりエネルギーを費やしたくありません。なぜなら、ソート、バイナリツリー、パス圧縮ツリー、統計、KDツリー、重複の排除、近いポイントの検索などの問題に必然的に遭遇するからです。これらのプロセスは非常に単純で、プログラムのアルゴリズムはさまざまなインタビューハンドブックに記載されています。デバッグするときは間違いなくまた百度に行くと思いますし、Googleに行く必要もありません。そのため、これらの前処理はすべて完了していると想定しています。インデックスを作成するだけで、このプログラムのコードは200行未満で、おそらく印刷#を削除します。その数はわずか150行ほどです...データはDxRのテストデータを使用し、約10万から50万のルーティング項目を追加しますが、これはすでにコアルーターの桁数です。テスト後、DxRは本当に素晴らしいです。ルーティングテーブルと転送テーブルを区別しないLinuxプロトコルスタックIPルーティングアルゴリズムについては、その悲惨な状況については説明しません。大丈夫としか言えません。本当に大丈夫です、少し関連があります。

この記事はこれで終わりです。今日の北京の天気は良く、雲ひとつない青空です。明日はまた新しい日で、新しい仕事と新しい旅が始まります。また別の2012/2013年がやってくるような気がします。地獄に落ちて山腹を登った初期のプロジェクトでは、自分を鍛えて多くのことを学びましたが、まだ360度回転して雑草を見下ろす山頂には到達していません（実際、雑草は見えず、雲しか見えません...）。だから、新しいものを設計するにしても、SPを続けるにしても、私は再び希望を持っています。プログラマーの中のネットワーク管理者、ネットワーク管理者の中のプログラマー、歴史の話が得意で、控えめで恐れ知らず、養女がいてローンを返済中のIT技術者にとって、次にどれだけのチャンスがあるでしょうか？私は普通の人ですが、かつては夢見がちなナルシストな技術オタクのように、自分が偉大で自信がないと感じていました。普通の人々が歴史を作るのではなく、歴史は英雄によって作られるが、普通の人々は幸せである。私にとってみんなは、そして私にとってみんなは、私たちはみんな普通の人間です。最後に、現実のありふれた出来事に対する私の評価を述べてこの記事を締めくくりたいと思います。

今日、私はタクシーの起源について同僚とチャットしていました。それで、ホテルに到着した後、私はその男に関連する時代と背景をすぐにレビューしました...今、私は彼の名前がエラトステネスであることを知っています（この名前は私にとって本当に長くはありません）席の爆発など、見返りに彼に1つのことを教えること...これはキリスト教の真の意味であり、すべて私にとって、そして私にとってはすべてです。私の母は宗教を信じているのですが、いつの間にか私もそれを信じていました.... 爆発 座席爆発を推進する精神と能力で、会社の製品と技術を宣伝し、他の会社との補完的な協力を促進し、製品の改善を推進することができれば、どんなに美しい絵になるでしょう... 爆発！

元の URL: http://dog250.blog..com/2466061/1623638