そのため、ルーティング エントリから可能な限り一致するインターフェイスを返そうとしています。しかし、それは私が望むように正確に機能しているわけではありません。6 つの値のうち 5 つが本来あるべき方法で返されましたが、アルゴリズムが機能しないルーティング テーブルに 100 万のエントリがあると確信しています。この問題を解決するために二分探索を使用しています。しかし、たとえば、返したいインターフェイスの ipaddress が、引数として渡している ipaddress よりも小さい場合、二分探索アルゴリズムは機能しません。構造は次のようになります。
struct routeEntry_t
{
uint32_t ipAddr;
uint32_t netMask;
int interface;
};
routeEntry_t routing_table[100000];
ルーティング テーブルが次のようになっているとします。
{ 0x00000000, 0x00000000, 1 }, // [0]
{ 0x0A000000, 0xFF000000, 2 }, // [1]
{ 0x0A010000, 0xFFFF0000, 10 }, // [2]
{ 0x0D010100, 0xFFFFFF00, 4 }, // [3]
{ 0x0B100000, 0xFFFF0000, 3 }, // [4]
{ 0x0A010101, 0xFFFFFFFF, 5 }, // [5]
入力/出力の例:
- 通常の検索
入力: 0x0D010101 出力: 4 (エントリ [3])
入力: 0x0B100505 出力: 3 (エントリ [4])
- 任意のアドレスを見つけるには、デフォルト インターフェイスに移動する必要があります。
入力: 0x0F0F0F0F 出力: 1 (エントリ [0])
- 複数のエントリに一致するアドレスを見つけるには、最も一致するものを取得します。
入力: 0x0A010200 出力: 10 (エントリ [2])
入力: 0x0A050001 出力: 2 (エントリ [1])
入力: 0x0A010101 出力: 5 (エントリ [5])
しかし、私の出力は 2, 3, 1, 10, 1, 5 のように見えます。私がどこで間違っているのか説明していただけますか？どんな助けでも素晴らしいでしょう。前もって感謝します。ただし、これは私のアルゴリズムがどのように見えるかです (エントリがソートされていると仮定します):
int interface(uint32_t ipAddr)
{ int 開始 = 0;
int end = SIZE-1;
int mid = 0;
vector<int> matched_entries;
vector<int>::iterator it;
matched_entries.reserve(SIZE);
it = matched_entries.begin();
if (start > end)
return -1;
while (start <= end)
{
mid = start + ((end-start)/2);
if (routing_table[mid].ipAddr == ipAddr)
return routing_table[mid].interface;
else if (routing_table[mid].ipAddr > ipAddr)
{
uint32_t result = routing_table[mid].netMask & ipAddr;
if (result == routing_table[mid].ipAddr)
{
matched_entries.push_back(mid);
}
end = mid-1;
}
else
{
uint32_t result = routing_table[mid].netMask & ipAddr;
if (result == routing_table[mid].ipAddr)
{
matched_entries.insert(it,mid);
}
start = mid+1;
}
}
int matched_ip = matched_entries.back();
if (routing_table[matched_ip].netMask & ipAddr)
return routing_table[matched_ip].interface;
else
return routing_table[0].interface;
}