Это не использует основание, но это просто реализовать.
Ваши ключи поиска не будут абсолютными. Возможны частичные совпадения, которые означают, что вы нашли правило соответствия сети, а не правило соответствия хоста.
Я предлагаю вам использовать список контейнеров (вложенные таблицы). Первый список будет упорядочен по маске подсети от наиболее ограничивающего (правила маршрута узла с маской 255.255.255.255) до наименее ограничивающего (шлюз по умолчанию с маской 0.0.0.0).
Под каждой записью в списке будет легко доступная для поиска структура (дерево, хеш-таблица или просто список), которая указана в замаскированной части адреса, который вы пытаетесь найти.
Для каждого адреса, который вы пытаетесь найти, вы должны искать его в подстолях каждой сетевой маски по очереди и выбирать первое совпадение, которое вы встретите, в качестве маршрута для использования. Он будет иметь максимально ограничивающую маску сети, поскольку они упорядочены от наиболее ограничивающей до минимальной, и если совпадение не будет найдено к тому времени, как вы достигнете конца списка сетевых масок, вы найдете запись сетевой маски шлюза по умолчанию в список, если у вас есть. Эта запись будет немного отличаться от других, потому что, если у вас есть более одной записи в ее под-таблице, все они будут иметь один и тот же сетевой адрес. Если вы хотите иметь только один шлюз по умолчанию, вы можете отказаться от записи 0.0.0.0 и рассматривать это как особый случай.
Вы также можете иметь метрику (стоимость, скорость и т. Д.) В качестве подключа для каждой записи (или чтобы каждое сетевое совпадение представляло собой список записей с одинаковым адресом сети / назначения, упорядоченных по их метрике ). Это позволит вам иметь более одного маршрута 192.168.1.0 (один по WiFi и один по проводному Этеренту), не усложняя ситуацию.
Когда запись с сетевой маской станет пустой, вы, вероятно, захотите удалить ее.
struct route4_table_subnet {
uint32_t mask;
struct route_table_network_container sub_table;
struct route_table_subnet * next;
};
struct route4_table_network_container_entry {
// The route_table_network_container contains nodes of this type, but
// however you want to implement this container is up to you
uint32_t network; // this is the key
uint32_t metric;
// route info
struct route4_table_network_container_entry * next;
};
Информация о маршруте хитрая. Вы можете просто перечислить здесь IP-адрес и распознать, когда вы получили IP-адрес, который находится в локальной сети, и прекратить поиск. Это потребует, чтобы вы узнали, когда собирались искать адрес, который был в локальной сети. Это затруднило бы настройку правил маршрутизации для отправки пакетов по адресу, который выглядел локально для маршрутизатора, что часто бывает полезно.
Вместо этого вы можете делать то, что делает Linux, и разрешать использование интерфейсных маршрутов в дополнение к адресным маршрутам.
Вероятно, вы реализуете это, имея флаг, указывающий тип маршрута, и тип объединения, содержащий данные для этого типа маршрута. Это делает интерфейсы, такие как PPP, где действительно не имеет значения, что вы знаете, что IP-адрес машины на другой стороне модема работает очень чисто. Это также позволяет вам не иметь странного случая для локальной сети. Вы просто смотрите их как любой другой адрес в таблице, и они говорят «использовать интерфейс Ethernet 0».
В этом случае, когда у вас был пакет для маршрутизации, вы передавали бы IP-адрес назначения в функцию поиска маршрута, которая возвращала бы лучшее совпадение. Если наилучшим соответствием была запись IP-адреса, вы бы развернулись и посмотрели этот IP-адрес в таблице маршрутизации, и он вернул бы наилучшее совпадение этого адреса. Вы продолжите это, пока не достигнете совпадения интерфейса (поэтому потребуются маршруты сопоставления интерфейса).
Возможно, вы захотите сохранить IP-адрес, поиск которого привел к записи маршрута интерфейса. В случае маршрута Ethernet вам нужно будет указать этот адрес для поиска ARP. Этот последний сопоставленный IP-адрес может совпадать с адресом назначения или маршрутизатором, который находится в той же сети, что и один из ваших сетевых интерфейсов.
Каждый раз, когда вы находите совпадение интерфейса, вы можете проверить, что интерфейс все еще присутствует, прежде чем вернуться из процедуры route_lookup. В случае, если интерфейс больше не присутствует, вы можете удалить его, а затем продолжить поиск лучшего соответствия. Вам не нужно было бы перезапускать поиск в списке сетевых масок, но нужно было бы убедиться, что вы не пропустили запись в текущем сетевом списке, которая имела более дорогостоящий показатель, чем интерфейс, который вы только что заметили, был удален. Скажем, у вас есть WiFi и проводной Ethernet в локальной сети, но вы просто отключили свой Ethernet, который стоит дешевле, чем WiFi (Ethernet быстрее и потребляет меньше энергии, поэтому вы дали ему более выгодный показатель) - теперь вы бы это сделали хотите, чтобы для этого пакета вы пытались перенаправить его на WiFi.
Я не знаю, как это можно сравнить с реализацией радикального дерева. Я подозреваю, что это будет сопряжено с этим на 32-битной машине для IPv4 (в зависимости от того, как вы выбрали route_table_network_container), но, возможно, будет менее выгодно в IPv6, где размеры адресов больше и маски подсети не используются (не так ли? I я не слишком знаком с IPv6, к сожалению)
Я полностью проигнорировал нити в этом. Я предполагаю, что только один поток будет иметь доступ к таблице маршрутизации одновременно. Если это не так, то добавление и удаление узлов потребует включения некоторых типов блокировок, которые будут зависеть от того, на какой платформе вы планируете реализовать это.