5

ipv6ルーターnは、アドレスの最初のビットとしていくつかのルートを格納します。2000年に、研究者は1500ipv6ルートでわずか14の異なるプレフィックス長を発見しました。着信パケットは最長プレフィックス一致に基づいて異なる発信ポートにルーティングされるため、パケットxの最初の8ビットが8ビットルートと一致するが、同じパケットの最初の48ビットが48ビットルートと一致する場合、ルータは48ビットルート。

私のルーターは非常に多くのパケットを処理しているため、ルーティングテーブルへのメモリルックアップの速度が制限要因になっています。ルーティングテーブルで最長一致のプレフィックスを見つけるための優れたアルゴリズムは何ですか？

4

4 に答える 4

5

トライまたは基数ツリーのいずれかを使用して、「標準」プレフィックスを格納します。サフィックス ツリー/配列は不要なオーバーキルです。これらは、プレフィックス間だけでなく、インフィックス間の一致を見つけるために使用されます(インフィックスはサフィックスのプレフィックスであり、複数の文字列間で一致を見つけたい場合は、それらを互いに連結するという事実を使用します)。

于 2009-02-04T19:00:13.303 に答える
2

ブルームフィルターを使用した最長プレフィックスマッチングと呼ばれる、このテーマに関するクールな論文を見つけました。

要約：最長プレフィックス一致（LPM）にブルームフィルターを使用することを認識している最初のアルゴリズムを紹介します。アルゴリズムは、プレフィックス長でソートされたプレフィックスのセットでアドレスプレフィックスメンバーシップを決定するために、メンバーシップクエリの効率的なデータ構造であるブルームフィルターに対して並列クエリを実行します。インターネットプロトコル（IP）ルーティングルックアップにこのアルゴリズムを使用すると、検索エンジンがTCAMベースのアプローチよりも優れたパフォーマンスとスケーラビリティを提供することを示します。

彼らの基本的な考え方は、プロセッサの組み込みSRAM（高速）に格納されているブルームフィルタを使用して、低速ではあるがより豊富なメモリでプレフィックスハッシュテーブルのルックアップをガイドすることです。IPv4の場合、ルーティングテーブルプレフィックスのほとんどが24ビットであるという事実を考慮して、アルゴリズムを調整します。IPv6の場合、1550のBGPエントリで14の一意のプレフィックス長しか見つかりませんでした。

于 2009-02-10T20:56:12.847 に答える
0

一般に、最も長い共通プレフィックスを計算する最も効率的な方法は、サフィックス ツリーまたはサフィックス配列です (ランタイムは、前処理後のプレフィックスの長さに比例します)。

于 2009-02-04T16:06:09.863 に答える
0

予備のメモリはありますか？

次のような構造を作成します。

typedef struct node {
  struct node* table[256];
  Port_type port;
} Node;
Node* root[256];

これで、次のようにルックアップを実行できます。

Node* table = root;
for (i=0; table != NULL; i++)
{
   node = table[address_byte[i]];
   table = node->table;
}
destination = node->port;
于 2009-02-04T21:38:20.990 に答える