Какой алгоритм разбиения сети на подсети указанного размера?

Question

[ITF]

Собственно получилось написать свой "велосипед" разбиения сети на заданное количество сегментов.
Но уперся в стену, когда нужно ещё учитывать размер подсети.
Например исходная сеть:
192.168.0.0/24 (256 адресов)
Нужно например разбить её на:
5 сегментов: 30, 30, 30, 2, 2

Натыкался на алгоритм разбиения "квадратами".
Это когда делишь сеть на 2 части и пока не найдется подсеть для самого маленького сегмента.
Но этим методом я например не смогу разбить по примеру на 4 подсети, где 4-ую разбиваю на более мелкие.
Там получиться что 30 уйдет в сеть с /25 маской, вторые 30 уйдет с /26 маской, третьи 30 уйдут с /27 маской, 2 с /28 и ещё 2 с /29.
Что собственно не "экономично", тем более если указывать большую исходную сеть (например /16), имеет свой предел по количеству сегментов. И запас неиспользуемых адресов слишком большой.

Кто подскажет как подобное можно реализовать?

Comments

[Максим Корнеев]

у всех сетей на 30 хостов маска одинаковая. у всех сетей на 2 хоста маска одинаковая. меняются только адреса сетей, а не маска. или Вы имели в виду что-то другое?

[ITF]

Имел ввиду что если при разбиении сети 192.168.0.0 / 24
Алгоритм квадратов показывает, что я разбиваю её на 2 подсети по 128, в первую уходит 100 адресов моих, оставшаяся часть разбивается на 2 по 64 адреса, в первую уходит 30 адресов, оставшаяся делится на 2 по 32 в первую уходит 30... оставшуюся делить нет смысла, поэтому выходит сообщение что они не влазят.

Но хотелось бы что:
Разбивается на 2 подсети по 128, в первую уходит 100, оставшаяся делиться на 4 по 64 и в них раскидываются по 30 адресов.
Или
С необходимыми подсетями 100, 30, 30, 30, 30
Что бы сеть разбивалась сначала на 2 посдети по 128 адресов, оставшаяся часть на 4 по 64 адреса, где первые из них разбивались на 2 подсети по 32 адреса. 3-4 подсеть на 64 адреса остаются не тронутыми.

Answer 1

[Rsa97]

Несколько обобщив задачу получаем следующее:
- на входе есть список имеющихся подсетей (возможно из одного элемента) и список размеров подсетей, которые надо выделить;
- на выходе надо получить выделенные подсети и список оставшихся нераспределёнными подсетей.
1. Находим маску необходимой подсети mask := 32 - ⌈log₂(size + 2)⌉. 2. Ищем в списке свободных подсеть subNet с максимальной маской меньшей либо равной mask.
3. Если не нашли, то выделить подсеть невозможно, возвращаем ошибку.
4. Пока маска subNet меньше mask, удаляем subNet из списка свободных, разбиваем её на две подсети, добавляем полученные подсети в список свободных, в качестве subNet берём одну из них.
5. Если маска subNet равна mask, то выделяем подсеть, удаляем её из списка свободных, возвращаем результат.

Пример:

Вход: список подсетей = [192.168.0.0/24], размер = 30
mask = 32-ceil(log2(32)) = 27
после поиска subNet = 192.168.0.0/24
24 < 27 => список подсетей = [192.168.0.0/25, 192.168.0.128/25], subNet = 192.168.0.0/25
25 < 27 => список подсетей = [192.168.0.0/26, 192.168.0.64/26, 192.168.0.128/25], subNet = 192.168.0.0/26
26 < 27 => список подсетей = [192.168.0.0/27, 192.168.0.32/27, 192.168.0.64/26, 192.168.0.128/25], subNet = 192.168.0.0/27
27 == 27 => список подсетей = [192.168.0.32/27, 192.168.0.64/26, 192.168.0.128/25], выделенная подсеть = 192.168.0.0/27