Распили мне сеть!

Не так давно предомной встала задача — распилить сеть на несколько подсетей. Вроде вещь не сложная, ещё на первом курсе этому учили, но увы, из-за постоянного неиспользования как-то подзабылась. И дабы больше не освежать память путем просмотра бесчисленных веб страниц с кучей cетевой теории, я и написал это.

Задача: получить из сети 192.168.1.0/24 несколько, а если быть точным, то на восемь подсетей. Количество машин в сетях:

сеть 1 - 7  хостов
сеть 2 - 20 хостов
сеть 3 - 30 хостов 
сеть 4 - 37 хостов
сеть 5 - 20 хостов
сеть 6 - 14 хостов 
сеть 7 - 24 хоста
сеть 8 - 28 хостов 

Ну что ж, представим для наглядности наши исходные адрес и маску в бинарном виде.

адрес: 192.168.1.0  ->    11000000.10101000.00000001.00000000
маска: 255.255.255.0  ->  11111111.11111111.11111111.00000000

Первые три октета ip адреса отвечают за сеть в которой он находится, последний же октет за определённый адрес в этой сети. Первый и последний адреса сети зарезервированы для адреса самой сети и адреса бродкаста и об этом не стоит забывать когда пилишь сеть. Префикс /24 показывает сколько задействовано бит в нашей маске. В данном случае задействовано 24 бита, вследствии чего последний октет маски получется состоит из нулей. /25 - префикс "откусит" из последнего октета 1 бит, теперь маска примет форму

255.255.255.128 ->  11111111.11111111.11111111.10000000

для /26 уже будет:

255.255.255.192 ->  11111111.11111111.11111111.11000000

и так далее.
Что нам это даёт? Хех, да это ключь к решению всего "зла" с разбиениями сетей на подсети:). Первые, занятые биты октета скажут нам на сколько ровных подсетей мы сможем разбить нашу сеть, а последние, свободные биты из нулей — скажут нам сколько хостов может быть в каждой подсети.
Используем формулы вычисления количества подсетей (1) и количества хостов в подсети (2):

(1) 2^n, где n - кол-во занятых бит в последнем октете маски

(2) 2^m-2, где m - кол-во свободных бит в последнем октете 

Вернёмся к изначальной задаче. Нам надо получить 8 подсетей. Что ж, 8 = 2 ^ 3, следовательно забиваем еденицами первые три бита последнего октета маски и получаем сеть с префиксом /27 и маской 255.255.255.224:

11111111.11111111.11111111.11100000 -> 255.255.255.224 -> /27

Всё бы ничего, да только нам этот вариант не подходит. Сети у нас равные, что значит что количество хостов в них одно и то же: 2^5-2 = 32. Но для нашей задачи это не подходит, слишком уж расточительно, да и в некоторых сетях количество хостов должно быть больше 32-х. Придётся подбирать оптимальный вариант.
Мы можем разбивать сеть так, что у нас будет 128, 64, 32, 16, 8 или 4 адресов в подсети. Глядя на исходные данные о количестве хостов в подсетях, можно сказать что нам понадобятся: 5 подсетей с 32 адресами, 2 подсети с 16 адресами и 1 сеть с 64 адресами для сети 4, в которой 37 хостов (эх, было бы их на 7 меньше...). Как будем разбивать:

Итак, имеем сеть 192.168.1.0/24, разбиваем её на 2 сети с префиксом /25, для нас обе получившиеся сети слишком большие, бьём их ещё на несколько. Первую часть разбивавем ещё на четыре с префиксом /27 по 32 адреса. Уже лучше, можно назначить адреса трём сетям, в частности:

сеть 3  ->  192.168.1.0  - 192.168.1.31
сеть 7  -> 192.168.1.32 - 192.168.1.63
сеть 5 -> 192.168.1.64 - 192.168.1.95

Всего 3, осталась ещё одна, вот её то мы и используем для сетей 6 и 1, эти сети содержать самое маленькое количество хостов, следовательно для них хватит /28, содержащее по 16 адресов:

сеть 6 -> 192.168.1.96  - 192.168.1.111
сеть 1 -> 192.168.1.112 - 192.168.1.127

Вернёмся ко второй, пока не тронутой половинке сети с префиксом /25. Её мы тоже так просто оставлять не будем а разобьём на 2 части, одну из которых мы оставим не тронутой для сети 4, так как чило хостов, которые надо подключить 37, то придётся использовать диапазон в 64 адреса (в 32 не влезли :( ).

сеть 4 -> 192.168.1.128 - 192.168.1.191

Вторую половинку половинки:) снова разбиваем на 2. И у нас как раз ещё 2 не определённых сети - 2 и 8. Вот им то и назначаем адреса с префиксом /27:

сеть 2 -> 192.168.1.192 - 192.168.1.233
сеть 8 -> 192.168.1.224 - 192.168.1.255

Вот и всё. С задачей справились, сети запилены разбиты, все всюду влезли (даже в некоторых сетях осталась почва для расширения). Не знаю на сколько удобен такой способ, но для меня он вполне приемлем, если найду (пойму) более простые (удачные) способы разбиения сети на подсети  — обязательно выложу.


P.S.  Небольшая табличка в помощь:

Кол-во адресов: 256    128    64    32    16      8     4     2
Маска подсети:    0    128   192   224    240   248   252   254
Кол-во подсетей:  1      2     4     8     16    32    64
Кол-во хостов:  254    126    62    30     14     6     2
Маска:          /24    /25   /26   /27    /28   /29   /30   /32

Нашёл на этом сайтике, кстати там много полезной инфы по этой теме:)

Алгоритм Брезенхема для... параболы

Алгоритм Брезенхэ́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Е. Брезенхэмом (Jack E. Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка.

из википедии

  Суть алгоритма Брезенхема для окружности: считаем один раз точку и отражаем её ещё 7 раз, для параболы же получаем то же самое, только рисуем не часть четверти, как у окружности, а одну ветвь параболы, отражая её потом зеркально от оси. Ну обовсём по порядку.
  Имеем каноническое уравнение параболы:

Определися с направлениями движения. Их как и в случае с коружностью три (гм.. странные совпадения:): вертикаль, горизонталь и диагональ, соответствено движение из начальной точки (x,y) будут следующими: (x,y+1), (x+1, y) или (x+1,y+1). Теперь, было бы не плохо понять, как мы двигаемся при отрисовке параболы, имея три направления. Для начала, находим расстояния от трёх возможных точек до параболы по следующим формулам:

—  для диагонали


      
          —   для горизонтали

     
          —   для вертикали

  Затем высчитываем направление нашего движения следующим образом, находим разности между расстояниями:

  Если дельта меньше нуля, то следующее направление движения горизонталь либо диагональ, в противном случае вертикаль либо диагональ. Предположим что меньше, тогда смотрим разницу расстояний  И снова сравнения, если разность меньше нуля, то двигаемся по диагонали, если не - по горизонтали.   Вернёмся к   дельта, мы рассмотрели случай с меньше, но что же будет если всё не так? А будет следующее - очередное сравнение и обьектом его будет разности растояний .  Если разность больше нуля, то движение по диагонали, если меньше - по вертикали.Вот собственно и весь принцип определения направлений движения.

  Увеличив нужные координаты на еденицу, отрисовываем пиксель (и зеркальный ему по другую сторону оси) и проделываем всё заново, пока не достроим нашу параболу до конца.

  Вот собственно и всё, принцип почти тот же что и для окружности. Такой вариант достаточно медленный из-за пересчета расстояний до параболы на каждой итерации, поэтому его лучше оптимизировать, но... об этом позже.

З.Ы. Небольшой кусок кода на С#, иллюстрирующий вышесказанное:

//---------------------------------------------------------

            int p = 2;
            int x0 = 0; //  центр
            int y0 = 0; //
            int Sh, Sv, Sd;
            Sd = ((y + 1) * (y + 1) )- 2 * p * (x + 1);
            Sv = ((y + 1)*(y + 1)) - 2 * p * x;
            Sh = (y*y) - 2 * p * (x + 1);
            this.drawPix(x0, y0);    
            while (x + x0 < maxX) //пока полотно не кончится
            {
                if (Math.Abs(Sh) - Math.Abs(Sv)<=0)
                {
                    if (Math.Abs(Sd) - Math.Abs(Sh) < 0)
                           y++;
                    x++;

                }
                else
                {
                    if (Math.Abs(Sv) - Math.Abs(Sd) > 0)
                           x++;
                    y++;
                    
                }

                this.drawPix(x + x0, y + y0);

                Sd = ((y + 1) * (y + 1)) - 2 * p * (x + 1);
                Sv = ((y + 1) * (y + 1)) - 2 * p * x;
                Sh = (y * y) - 2 * p * (x + 1);
            }
//---------------------------------------------------------