возникли проблемы с возвратом наилучшего интерфейса из набора записей маршрутизации - PullRequest
Новая
       27

возникли проблемы с возвратом наилучшего интерфейса из набора записей маршрутизации

0 голосов
/ 01 апреля 2012

, поэтому я пытаюсь вернуть максимально подходящий интерфейс из записей маршрутизации. Тем не менее, это не совсем так, как я хочу. Я получил 5 из 6 возвращенных значений в порядке, но я почти уверен, что у меня есть миллион записей в таблице маршрутизации, мой алгоритм не будет работать. Я использую бинарный поиск для решения этой проблемы. Но, например, интерфейс, который я хочу вернуть, имеет 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]

Пример ввода / вывода:

  1. Обычный поиск

Вход: 0x0D010101 Выход: 4 (запись [3])

Вход: 0x0B100505 Выход: 3 (запись [4])

  1. Чтобы найти произвольный адрес, он должен перейти на интерфейс по умолчанию.

Вход: 0x0F0F0F0F Выход: 1 (запись [0])

  1. Чтобы найти адрес, который соответствует нескольким записям, возьмите лучшее совпадение.

Вход: 0x0A010200 Выход: 10 (запись [2])

Вход: 0x0A050001 Выход: 2 (запись [1])

Вход: 0x0A010101 Выход: 5 (запись [5])

Но мой вывод выглядит как 2, 3, 1, 10, 1, 5. Я не понимаю, где я все перепутал. Не могли бы вы объяснить, где я делаю неправильно? любая помощь будет отличной. Заранее спасибо. Однако вот как выглядит мой алгоритм (при условии, что записи отсортированы): 

int interface(uint32_t ipAddr)

{ int start = 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;
* *} Тысяча сорок-девять

Ответы [ 2 ]

1 голос
/ 01 апреля 2012

«Правильный» интерфейс - это запись с наиболее определенной маской сети, IP-адрес которой находится в той же подсети, что и ваш ввод.

Давайте посмотрим, что такое маски и как они работают, более подробно.

Обозначение

Хотя сетевые маски обычно пишутся в точечно-десятичном или шестнадцатеричном формате, двоичное представление сетевой маски IPv4 всегда составляет 32 бита; то есть он точно такой же длины, как и IP-адрес. Маска сети всегда начинается с нуля или более 1 битов и дополняется 0 битами для завершения 32-битной длины. Когда сетевая маска применяется к IP-адресу, они «выстраиваются» по крупицам. Биты в IP-адресе, которые соответствуют 1 битам в маске сети, определяют номер сети IP-адреса; те, которые соответствуют 0 битам в маске сети, определяют номер устройства .

Назначение

Маски сети используются для разделения адресного пространства на меньшие подсети . Устройства в одной подсети могут связываться друг с другом напрямую, используя стек протоколов TCP / IP. Устройства в разных подсетях должны использовать один или несколько маршрутизаторов для пересылки данных между ними. Поскольку они изолируют подсети друг от друга, маски сетей являются естественным способом создания логических групп устройств. Например, у каждого местоположения или отдела в компании может быть своя собственная подсеть, или у каждого типа устройства (принтеры, ПК, и т.д. .) Может быть своя собственная подсеть.

Пример сетевых масок:

255.255.255.128 & rarr; FF FF FF 10 & rarr; 1111 1111 1111 1111 1111 1111 1000 0000
Эта маска сети указывает, что первые 25 бит IP-адреса определяют номер сети; последние 7 бит определяют номер устройства. Это означает, что может быть 2 25 различных подсетей, каждая с 2 7 = 128 устройств. *

255.255.255.0 & rarr; FF FF FF 00 & rarr; 1111 1111 1111 1111 1111 1111 0000 0000
Эта маска сети определяет адресное пространство с 2 24 подсетями, каждая с 2 8 = 256 отдельных адресов. Это очень распространенная конфигурация & mdash; настолько распространенная, что ее называют просто "сетью класса".

255.255.192.0 & rarr; FF FF FC 00 & rarr; 1111 1111 1111 1111 1111 1100 0000 0000
Эта маска сети указывает 2 22 * ​​1069 * подсетей, каждая с 2 10 = 1024 адресами. Он может использоваться внутри большой корпорации, где в каждом отделе есть несколько сотен устройств, которые должны быть логически сгруппированы.

An недействительно маска сети (обратите внимание на внутренние нули):
255.128.255.0 & rarr; FF 80 FF 00 & rarr; 1111 1111 1000 0000 1111 1111 0000 0000

Расчеты

Вот несколько примеров, которые показывают, как маска сети определяет номер сети и номер устройства IP-адреса.

IP-адрес: 192.168.0.1 & rarr; C0 A8 00 01
Маска сети: 255.255.255.0 & rarr; FF FF FF 00
Это устройство находится в подсети 192.168.0.0. Он может напрямую связываться с другими устройствами, чьи IP-адреса имеют вид 192.168.0. x

IP-адрес: 192.168.0.1 & rarr; C0 A8 00 01
IP-адрес: 192.168.0.130 & rarr; C0 A8 00 82
Маска сети: 255.255.255.128 & rarr; FF FF FF 80
Эти два устройства находятся в разных подсетях и не могут связываться друг с другом без маршрутизатора.

IP-адрес: 10.10.195.27 & rarr; 0A 0A C3 1B
Маска сети: 255.255.0.0 & rarr; FF FF 00 00
Это адрес в сети «класса B», который может связываться с адресами 2 16 в сети 10.10.0.0.

Вы можете видеть, что чем больше 1 битов в начале маски сети, тем более она конкретна. То есть больше 1 битов создают «меньшую» подсеть, состоящую из меньшего количества устройств.

Собираем все вместе

Таблица маршрутизации, как и ваша, содержит три маски сетей, IP-адреса и интерфейсы.(Он также может содержать метрику «стоимости», которая указывает, какой из нескольких интерфейсов является «самым дешевым» для использования, если они оба способны маршрутизировать данные в конкретное место назначения. Например, можно использовать дорогую выделенную линию.)

Для маршрутизации пакета маршрутизатор находит интерфейс с наиболее точным соответствием адресату пакета. Запись с адресом addr и маской сети mask соответствует IP-адресу назначения destесли (addr & netmask) == (dest & netmask), где & обозначает побитовую операцию AND. На английском языке нам нужна наименьшая подсеть , которая является общей для обоих адресов .

Почему? Предположим, что вы и коллега находитесь в отеле, который является частью огромной цепочки с корпоративной проводной и беспроводной сетью. Вы также подключились к VPN вашей компании. Ваша таблица маршрутизации может выглядеть примерно так: 

 Destination    Netmask    Interface   Notes
 -----------    --------   ---------   -----
 Company email  FFFFFF00   VPN         Route ALL company traffic thru VPN
 Wired network  FFFF0000   Wired       Traffic to other hotel addresses worldwide
 Default        00000000   Wireless    All other traffic

Самое конкретное правило будет направлять электронную почту вашей компании через VPN, даже если адрес совпадает ссеть также.Весь трафик на другие адреса в сети отелей будет направляться через проводную сеть.И все остальное будет отправлено через беспроводную сеть.



* Фактически, в каждой подсети 2 адреса - самый высокий исамые низкие - зарезервированы.Адрес «все единицы» - это адрес широковещательный : этот адрес отправляет данные на каждое устройство в подсети.А адрес «все нули» используется устройством для обращения к себе, когда у него еще нет собственного IP-адреса.Я проигнорировал их для простоты.

Так что алгоритм будет выглядеть примерно так: 

initialize:
  Sort routing table by netmask from most-specific to least specific.
  Within each netmask, sort by IP address.

search:
  foreach netmask {
    Search IP addresses for (input & netmask) == (IP address & netmask)
    Return corresponding interface if found
  }
  Return default interface
0 голосов
/ 02 апреля 2012

Ладно, вот как сейчас выглядит моя структура и алгоритм. Это работает и дает мне результаты, которые я хочу, однако я все еще не знаю, как сортировать IP-адреса внутри сетевых масок. Я использовал сортировку STL для сортировки сетевых масок. 

struct routeEntry_t

{
uint32_t ipAddr;
uint32_t netMask;
int interface;

bool operator<(const routeEntry_t& lhs) const
{
    return lhs.netMask < netMask;
}
};

const int SIZE = 6;

routeEntry_t routing_table[SIZE];

void sorting()
{
//using STL sort from lib: algorithm
sort(routing_table, routing_table+SIZE);
}

int interface(uint32_t ipAddr)
{
for (int i = 0; i < SIZE; ++i)
{
    if ((routing_table[i].ipAddr & routing_table[i].netMask) == (ipAddr &   routing_table[i].netMask))
        return routing_table[i].interface;
}
return routing_table[SIZE-1].interface;
}
...