Получить набор подсетей / адресов из диапазона IP

Question

Я ищу хороший алгоритм (или код, если вы говорите лучше английского), чтобы сделать следующее:

Для данного диапазона IP (например, 1.1.1.1 - 1.1.2.247) найдите наименьшую комбинацию подсетей / адресов, которая включает все IP в указанном диапазоне. Игнорировать широковещательную рассылку, ограничения подсети 0 и класс сети.

Примеры:

• Для 1.1.1.1 - 1.1.2.1 вы получите {1.1.1.1/24, 1.1.2.1}, который лучше / меньше, чем {1.1.1.1, 1.1.1.2, ..., 1.1.1.255, 1.1.2.1}
• Для 1.1.1.12 - 1.1.1.31 вы получите {1.1.1.12/30, 1.1.1.16/28}, которое лучше / меньше, чем {1.1.1.12, 1.1.1.13, 1.1.1.14, 1.1.1.15, 1.1.1.16/28}

Для любопытных, вариант использования сопоставляет сетевой трафик на произвольном диапазоне IP-адресов источника / назначения с наименьшим числом потоков, используя протокол Openflow. Необходимость такой оптимизации обусловлена ​​тем фактом, что аппаратные коммутаторы / маршрутизаторы имеют ограниченное пространство для этих конфигураций потока, и для программирования / изменения требуется относительно много времени.

Answer 1

Если вы рассматриваете IP-адреса как 32-разрядные числа, это проблема поиска набора интервалов, объединение которых представляет собой диапазон IP-адресов, который необходимо заполнить. Глядя на ваш первый пример, я собираюсь предположить, что когда вы говорите.1, вы разрешаете интервалу включать.0, потому что 1.1.1.1/24 - это набор адресов как 1.1.1.0/24.

Рассматривая IP-адреса как числа, я бы начал с наименьшего числа и искал наибольшую подсеть, начинающуюся с этого номера, которая не идет дальше конечного IP-адреса. Примите это как свою первую подсеть и определите IP-адрес в конце диапазона, который вы только что охватили. Затем начните снова, чтобы найти самую большую подсеть, начинающуюся с того IP-адреса, которая не заходит слишком далеко - и так далее.

Это оптимально, потому что все доступные подсети выстроены в степени двух. Чтобы использовать большую подсеть, охватывающую 2^n адресов, вы должны перейти к начальному адресу, в котором очищены младшие n битов. Если у вас меньше чем n битов, очистите способ сделать это, выбрав самый большой шаг, возможный на каждом этапе, и каждый шаг очищает самый младший установленный бит в текущем адресе.