LLTR Часть 2: Алгоритм определения топологии сети по собранной статистике

Link Layer Topology Reveal logo
В предыдущих частях…

0. Автоматическое определение топологии сети и неуправляемые коммутаторы. Миссия невыполнима? (+ classic Habrahabr UserCSS)

1. Первые шаги в OMNeT++ и INET [tutorial]

Q: Что у нас есть?
A: Статистика, собранная с хостов.

Q: Что мы хотим получить?
A: Топологию сети! Точнее, нужно построить правильную цепочку пиров (хостов) для RingSync.

Нам предстоит придумать алгоритм, который вначале превратит статистику в топологию сети, а затем – в цепочку пиров. Пока алгоритм выглядит так:

статистика –-[*магия*]--> топология сети --[*магия*]--> цепочка пиров
Любая достаточно развитая технология неотличима от магии. — Arthur C. Clarke

Note: далее вместо “–-[*магия*]-->” я буду использовать “–-[???]-->”.

Собранная статистика показывает нам, на каких хостах упала скорость получения broadcast трафика. Например, посмотрим на результат нулевой итерации в сети “N2_2” (“Network” из предыдущей статьи “LLTR Часть 1”):

{300,164,164},

Здесь четко видны 2 состояния хоста:

К чему я клоню? К бинаризации! Если мы закодируем отсутствие реакции как 0, а присутствие реакции как 1, то сможем поместить все реакции хостов, отдельно взятой итерации, в одну переменную (32 – 512 bit [AVX‑512]). Помимо экономии памяти (и места, занимаемого в кэшах), это увеличит скорость обработки – за одну инструкцию будут обрабатываться сразу все реакции хостов конкретной итерации (SIMD).

Note: т.к. использовать LLTR Basic для большого числа хостов весьма накладно (см. начало раздела “LLTR Часть 0::LLTR Advanced”), то все поместится в 64 bit регистры x86‑64.

Note: В текст ссылки на раздел, расположенный в другой статье (другая часть), я буду добавлять номер части в формате: “LLTR Часть #::‹название раздела›”. А в “title” ссылки буду записывать название части, например, для “LLTR Часть 0::” будет всплывать “Автоматическое определение топологии сети и неуправляемые коммутаторы. Миссия невыполнима?”.

Возьмем тот же пример нулевой итерации, и посмотрим, как он будет выглядеть после бинаризации:

{300,164,164} --[бинаризация]--> 011

Весьма компактно, однако я бы хотел, чтобы “1” (присутствие реакции) сразу бросались в глаза при просмотре списка из всех итераций. Сейчас “1” не сильно выделяется на фоне “0” (фейковые данные, для визуального примера):

0101011010110
1100010110010
0101101010111
0100010110100

Чтобы выделить “1”, я введу обозначения:

Посмотрим опять на “фейковые данные”:

.1.1.11.1.11.
11...1.11..1.
.1.11.1.1.111
.1...1.11.1..

Так значительно лучше (IMHO).

Алгоритм, на данный момент, выглядит так:

статистика –-[бинаризация]--> реакции хостов --[???]--> топология сети --[???]--> цепочка пиров

Оставим детали бинаризации для конца статьи, и сконцентрируемся на остальной части алгоритма.

Создавать алгоритм, проще всего, отталкиваясь от конкретных исходных/входных данных (частные случаи, граничные условия; тесты – в терминах TDD). В нашем случае исходные данные зависят от топологии сети, поэтому нужно придумать такую сеть, которая была бы одновременно небольшой, и в то же время содержала разные схемы соединения свитчей (звезда, последовательное соединение). Возможно, в нее удастся включить нечто особенное… В общем, воображение нарисовало такую сеть (обозначения элементов аналогичны обозначениям, используемым в конце раздела “LLTR Часть 0::Топология: “последовательное соединение свитчей””):

Диаграмма: LLTR гибридная сеть

Note: смотря на эту сеть, вспоминается вопрос “а можно ли в данной топологии провести полноценное сканирование, если к одному из свитчей …” (ближе к концу раздела “LLTR Часть 0::Топология: “последовательное соединение свитчей””), и замечаешь, что к одному из свитчей напрямую не подключен ни один хост. Причем в этом нет никаких проблем, т.к. к этому свитчу подключены еще 3 свитча (я считал только свитчи, подключенные “снизу”, без учета того, что он подключен к еще одному свитчу “сверху”), у каждого из которых есть хосты.

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

Диаграмма: LLTR гибридная сеть (clear)

Здесь сразу виден свитч “без хостов”. К тому же все свитчи я расположил таким образом, чтобы хосты в них не перекрывали друг друга по вертикали. Это будет полезно, если я в будущем захочу показать “реакции хостов” не в виде текстовой записи “.....1......”, а в виде диаграммы (на одной вертикали находится только один хост):

Диаграмма: LLTR гибридная сеть (clear), пояснение обозначения “реакций хостов”

А теперь представьте статистику, которую мы получим, по завершению всех итераций сканирования этой сети. В сети 12 хостов (без учета broadcast хоста), следовательно, у нас будут данные по 132 итерациям. Однако не все результаты итераций нам пригодятся, например, будут бесполезны:

После очистки, из всех 132 результатов итераций, останется только 5 (реакции хостов):

1111111111..
11111111....
..111.......
.....111....
11..........

Note: для наглядности я расположил итерации в порядке от большего количества “1” к меньшему.

Алгоритм стал выглядеть так:

статистика –-[бинаризация]--> реакции хостов --[очистка от единичных реакций]--[очистка от дублей]--[???]--> топология сети --[???]--> цепочка пиров
reset point

Я размышлял над включением всего этого в спойлер, но в итоге понял, что это важная часть повествования, которую лучше не пропускать при чтении.

¬( Не пропускать в мозг при чтении :)

[reset point] В оставшихся 5 результатах итераций, внимание привлекают первые две: первая включает в себя вторую, а вторая включает оставшиеся 3 нижние. Здесь вспоминается “тень” из раздела “LLTR Часть 0::Топология: “последовательное соединение свитчей””. В том же разделе, по завершении каждой итерации мы формировали (или не формировали) новые кластеры на основе только что полученных данных. Сейчас нужно сделать то же самое.

Но как мы формировали новые кластеры? По сути все (не единичные) реакции “1” хостов текущей итерации и были “новым кластером”, нам оставалось только найти пересечения (“∩”; не пустые “∅”) с существующими кластерами, чтобы убрать (“∖”) из большего кластера хосты, входящие в меньший кластер.

Однако, в наших действиях присутствовало условие/ветвление (if): нужно определить какой из кластеров больше, и уже затем совершить простую операцию (A∖B) – из большего кластера (A) вычесть меньший (B). Представляя мучения CPU с длинным конвейером, вызванные необходимостью сброса конвейера при неверном предсказании ветвления (если в нем вообще “блок предсказания ветвлений” присутствует), я почти решил использовать тернарный оператор “?:, но в этот момент…

Я стоял на унитазе и вешал часы. Вдруг поскользнулся, ударился головой о раковину, а когда очнулся мне было видение, картинка в моём мозгу, видение вот этого – потоковый накопитель потоковый разделитель (Назад в будущее):

Back to the Future: Flux Divider
// Flux Divider
c=a^b;
aa=a&c;
bb=b&c;
cc=a&b;

И сразу посмотрим его работу на примере перекрывающихся кластеров (точнее, одно множество (кластер) строго включено “” в другое множество):

.....11..... - a
..11111111.. - b

..111..111.. - c=a^b

............ - aa=a&c
..111..111.. - bb=b&c
.....11..... - cc=a&b

Непересекающиеся кластеры:

..111....... - a
.......111.. - b

..111..111.. - c=a^b

..111....... - aa=a&c
.......111.. - bb=b&c
............ - cc=a&b

Получается, что:

Еще один пример с пересекающимися кластерами (“невозможный”, но наглядный пример):

...1111..... - a
.....1111... - b

...11..11... - c=a^b

...11....... - aa=a&c
.......11... - bb=b&c
.....11..... - cc=a&b

Note: такой вариант отклика (реакции хостов) – отсутствует в исходных данных.

Этим же способом можно избавляться от дублей:

.....11..... - a
.....11..... - b

............ - c=a^b

............ - aa=a&c
............ - bb=b&c
.....11..... - cc=a&b

Но, чуть позже…

Голова перестает болеть после удара об раковину, разум проясняется, и всплывают очевидные проблемы…

На входе у нас 2 переменные (результаты итераций / реакции хостов / кластеры / множества / …), но на выходе их уже 3, причем хотя бы один из них будет пуст (“∅”). Если сразу не избавится от “∅”, то их в дальнейшем придется включить в обработку. Поэтому лучше избавится от “∅” сразу. Но как это сделать? Использовать условие/ветвление! … В общем, я вернулся к тому, с чего начал. К тому же если все сделать, как было описано выше, плюс избавится от “∅”, то в итоге мы получим из:

1111111111..
11111111....
..111.......
.....111....
11..........

Это:

........11..
              - здесь должно было быть "............", но мы его стерли :(
..111.......
.....111....
11..........

Пора задаться вопросом: “Как из этого получить топологию сети?”. Сейчас эти данные могут “сказать”, о том, к какому кластеру принадлежит конкретный хост (т.е. к какому свитчу подключен хост), но в этих данных теперь полностью отсутствует информация о топологии свитчей (т.е. о том, как соединены свитчи между собой) – мы потеряли эту информацию в ходе преобразования данных. К тому же, к какому кластеру (свитчу) принадлежат 2 крайних справа хоста? Если рассматривать каждую строку как отдельный кластер (или как указание на то, какие хосты подключены к конкретному свитчу), то окажется, что эти 2 крайних хоста никуда не подключены! Более того, в сети у нас 6 свитчей, а строк осталось 4, где же еще 2 строки? Одну мы стерли (как гласит комментарий выше), а в другой как раз и должны были быть “2 крайних справа хоста”.

[goto reset point] Дальше развивать эту идею бесполезно. Тупиковая ветвь (git branch). Придется откатиться назад к метке “reset point”, забыв все, что было после нее, но оставив эту ветвь для истории.

Теперь же, чтобы не попасть в еще одну “мертвую ветвь”, нужно определиться с итоговой структурой (представлением) топологии сети в памяти. То есть, с тем, что мы хотим получить к моменту “топология сети”:

статистика –-[бинаризация]--> реакции хостов --[очистка от единичных реакций]--[очистка от дублей]--[???]--> топология сети --[???]--> цепочка пиров

Во‑первых, должны присутствовать все хосты:

..........11  <--
1111111111..
11111111....
..111.......
.....111....
11..........

Во‑вторых, должны быть указаны родители (родительский кластер для каждого кластера; на данный момент: родитель ребенок; на диаграмме сети, родителей я располагал выше детей) (слева добавлены номера кластеров):

0) ..........11  parent: ?
1) 1111111111..  parent: ?
2) 11111111....  parent: 1
3) ..111.......  parent: 2
4) .....111....  parent: 2
5) 11..........  parent: 2

Note: если вы заметили здесь что‑то странное, сравнивая диаграмму этой сети с этими данными, то вам like от меня.

Спойлер, лучше не открывать до прочтения всего списка

По сути (по диаграмме), родителем для кластера 1 является кластер 0, но тогда не выполняется условие “родитель ребенок”. Возможно в “Во‑первых” мы ошиблись, и вместо “..........11” стоило добавить “111111111111”?

В‑третьих, должен быть один “корневой” родитель, связывающий отдельные деревья (т.е. лес) в одно дерево:

-1) 111111111111
 0) ..........11  parent:-1
 1) 1111111111..  parent:-1
 2) 11111111....  parent: 1
 3) ..111.......  parent: 2
 4) .....111....  parent: 2
 5) 11..........  parent: 2

В‑четвертых, неплохо было бы иметь списки детей у каждого родителя:

-1) 111111111111             children: 0,1
 0) ..........11  parent:-1
 1) 1111111111..  parent:-1, children: 2
 2) 11111111....  parent: 1, children: 3,4,5
 3) ..111.......  parent: 2
 4) .....111....  parent: 2
 5) 11..........  parent: 2

И наконец, именно теперь можно исключить детей из родителей:

-1) ............             children: 0,1
 0) ..........11  parent:-1
 1) ........11..  parent:-1, children: 2
 2) ............  parent: 1, children: 3,4,5
 3) ..111.......  parent: 2
 4) .....111....  parent: 2
 5) 11..........  parent: 2

Теперь каждая строка описывает один кластер, т.е. указывает на хосты, подключенные к одному и тому же свитчу. Однако, постойте, в нашей сети 6 свитчей, а кластеров получилось 7 ! Пора, наконец, прочитать текст из спойлера выше “Спойлер, лучше не открывать до прочтения всего списка”, и исправить ситуацию:

0) ..........11             children: 1
1) ........11..  parent: 0, children: 2
2) ............  parent: 1, children: 3,4,5
3) ..111.......  parent: 2
4) .....111....  parent: 2
5) 11..........  parent: 2

Эти данные как раз и являются “топологией сети” – они описывают дерево свитчей, и по ним можно определить все хосты, подключенные к конкретному свитчу.

статистика –-[бинаризация]--> реакции хостов --[очистка от единичных реакций]--[очистка от дублей]--[???]--> топология сети --[???]--> цепочка пиров

Осталось понять, как привести данные к такому виду. По сути, все, что мы сделали (во‑первых, во‑вторых, …) можно преобразовать в алгоритм:

  1. “во‑первых” (после внесения исправлений из спойлера становится аналогичен действию “в‑третьих”) – добавить “корневой” кластер111111111111” (универсум), включающий (хосты всех деревьев в лесу  ∪  хосты, находящиеся на одном свитче с broadcast хостом), т.е. он включает в себя все хосты сети;
  2. “во‑вторых” – поиск родителя для каждого кластера;
  3. “в‑четвертых” – построение списка детей для каждого родителя;
  4. “и наконец” – исключение детей из родителей.

Теперь можно внести эти действия в общий алгоритм (немного изменил вид):

                                               ● статистика ●
                                 [бинаризация] ► реакции хостов
                [очистка от единичных реакций]
                           [очистка от дублей] ► кластеры/лес
                 [добавить "корневой" кластер] ► кластеры/дерево
         [поиск родителя для каждого кластера]
[построение списка детей для каждого родителя]
               [исключение детей из родителей] ► топология сети ●
                                         [???] ► цепочка пиров ●
Альтернативный вид
● статистика      ► [бинаризация]
▬ реакции хостов  ► [очистка от единичных реакций]
                    [очистка от дублей]
▬ кластеры/лес    ► [добавить "корневой" кластер]
▬ кластеры/дерево ► [поиск родителя для каждого кластера]
                    [построение списка детей для каждого родителя]
                    [исключение детей из родителей]
● топология сети  ► [???]
● цепочка пиров   ●

Посмотрим, что произойдет, если применить этот алгоритм к другой сети. Я бы хотел взять сеть “Network_serial” и ее результаты симуляции (статистику) из раздела “LLTR Часть 1::Больше сетей с разными топологиями, добавляем новые сети”.

Note: Почему я выбрал именно эту сеть? Она достаточно большая, и в собранных с нее данных присутствуют недочеты (см. конец спойлера “Результаты симуляции” для этой сети).

Поехали!

Бинаризация

Реакции хостов:

.111111..
.111111..
.111111..
.111111..
.111111..
.111111..
.......11
.......11
..1......
...1111..
...1111..
...1111..
...1111..
.......11
.......11
1........
...1111..
...1111..
...1111..
...1111..
.......11
.......11
1........
.1.......
....1....
.....11..
.....11..
.......11
.......11
1........
.1.......
..1......
.....11..
.....11..
.......11
.......11
1........
.1.......
..1......
...1.....
......1..
.........
.........
.........
.1.......
..1......
...1.....
....1....
.........
.........
.........
.1.......
..1......
...1.....
....1....
.....1...
........1
1........
.111111..
.111111..
.111111..
.111111..
.111111..
.111111..
1........
.111111..
.111111..
.111111..
.111111..
.111111..
.111111..
.......1.
Очистка от единичных реакций
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.......11  -->  .......11
.......11  -->  .......11
..1......  --> 
...1111..  -->  ...1111..
...1111..  -->  ...1111..
...1111..  -->  ...1111..
...1111..  -->  ...1111..
.......11  -->  .......11
.......11  -->  .......11
1........  --> 
...1111..  -->  ...1111..
...1111..  -->  ...1111..
...1111..  -->  ...1111..
...1111..  -->  ...1111..
.......11  -->  .......11
.......11  -->  .......11
1........  --> 
.1.......  --> 
....1....  --> 
.....11..  -->  .....11..
.....11..  -->  .....11..
.......11  -->  .......11
.......11  -->  .......11
1........  --> 
.1.......  --> 
..1......  --> 
.....11..  -->  .....11..
.....11..  -->  .....11..
.......11  -->  .......11
.......11  -->  .......11
1........  --> 
.1.......  --> 
..1......  --> 
...1.....  --> 
......1..  --> 
.........  -->  .........
.........  -->  .........
.........  -->  .........
.1.......  --> 
..1......  --> 
...1.....  --> 
....1....  --> 
.........  -->  .........
.........  -->  .........
.........  -->  .........
.1.......  --> 
..1......  --> 
...1.....  --> 
....1....  --> 
.....1...  --> 
........1  --> 
1........  --> 
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
1........  --> 
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.111111..  -->  .111111..
.......1.  -->  

Очистка от дублей (получаем “кластеры/лес”):

.111111..
.......11
...1111..
.....11..
.........

Дополнительно, для удобства, отсортирую по убыванию количества “1”:

.111111..
...1111..
.....11..
.......11
.........

Note: Возможно стоит включить сортировку в алгоритм. Как думаете?

Добавление “корневого” кластера (получаем “кластеры/дерево”):

111111111
.111111..
...1111..
.....11..
.......11
.........

В него вошли хосты 2‑х деревьев (левая “.111111..” и правая “.......11” часть сети) и 1 хост (“1........”, расположенный на одном свитче с broadcast хостом).

Поиск родителя для каждого кластера:

0) 111111111 
1) .111111..  parent: 0
2) ...1111..  parent: 1
3) .....11..  parent: 2
4) .......11  parent: 0
5) .........  parent: 4

Note: Вот здесь как раз и проявилось негативное влияние недочетов в данных – 4‑й кластер стал родителем для 5‑го! Вообще, родителем 5‑го кластера может стать любой кластер, т.к. он пуст (∅).

Построение списка детей для каждого родителя:

0) 111111111             children: 1,4
1) .111111..  parent: 0, children: 2
2) ...1111..  parent: 1, children: 3
3) .....11..  parent: 2
4) .......11  parent: 0, children: 5
5) .........  parent: 4

Исключение детей из родителей:

0) 1........             children: 1,4
1) .11......  parent: 0, children: 2
2) ...11....  parent: 1, children: 3
3) .....11..  parent: 2
4) .......11  parent: 0, children: 5
5) .........  parent: 4

На этом шаге мы должны были получить “топологию сети”. И мы ее получили. Если нам интересно только местоположение хостов, то такая “топологию сети” нас вполне устраивает. Однако, в нашей сети появился еще один свитч, в котором 0 хостов!

Чтобы все исправить, достаточно будет после одного из первых шагов исключить эти “недочеты в данных”. Это можно сделать сразу же после “бинаризации”:

                                               ● статистика ●
                                 [бинаризация] ► реакции хостов
[очистка от пустоты (∅), и от универсумов (⦱)]
                [очистка от единичных реакций]
                           [очистка от дублей] ► кластеры/лес
                 [добавить "корневой" кластер] ► кластеры/дерево
         [поиск родителя для каждого кластера]
[построение списка детей для каждого родителя]
               [исключение детей из родителей] ► топология сети ●
                                         [???] ► цепочка пиров ●

Мы удаляем пустые множества (∅; “.........”), но зачем удалять универсумы (⦱; “111111111”)? Ответ станет очевидным, когда мы начнем реализовывать этап “бинаризации”. Разные варианты реализации “бинаризации” могут на одних и тех же данных (данных с описанным недочетом) выдать как “.........”, так и “111111111”. И, т.к. получить в корректных входных данных “111111111” на столько же невозможно, как и получить “.........”, то мы можем удалить все “111111111” (к тому же они не несут никакой информации, кроме той, что в данных присутствуют “недочеты”).

Если применить этот (дополненный, исправленный) алгоритм к этой же сети (“Network_serial”), то “топология сети” станет выглядеть так:

0) 1........             children: 1,4
1) .11......  parent: 0, children: 2
2) ...11....  parent: 1, children: 3
3) .....11..  parent: 2
4) .......11  parent: 0

Note: Красиво, получилась диагональ. Напоминает единичную матрицу, но ее в чистом виде получить не удастся. Можно сделать, чтобы в каждом кластере было по 2 хоста (для этого нужно добавить один хост в “switch0”), но мы не сможем получить в каждых кластерах только 1 хост (в крайних кластерах всегда будут как минимум 2 хоста):

Примеры не “единичной матрицы”
0) 11........             children: 1,4
1) ..11......  parent: 0, children: 2
2) ....11....  parent: 1, children: 3
3) ......11..  parent: 2
4) ........11  parent: 0
0) 1......             children: 1,4
1) .1.....  parent: 0, children: 2
2) ..1....  parent: 1, children: 3
3) ...11..  parent: 2
4) .....11  parent: 0

Мы смогли дописать алгоритм до получения корректной “топологии сети”. Осталось построить “цепочку пиров” из “топологии сети”. В статье про RingSync я уже описывал, как это сделать (обход дерева в глубину: Pre‑order). В итоге “цепочка пиров” должна получиться такой:

1 1........  hostS/seed -> host0 ->
. .11......  host1 -> host2 ->
. ...11....  host3 -> host4 ->
. .....11..  host5 -> host6 ->
. .......11  host7 -> host8/leech

Note: в первую строчку (левый, отделенный столбец) добавлен сид, он же broadcast хост.

Кажется, что ничего не изменилось по сравнению с порядком кластеров в “топологии сети” (все та же диагональ), и это действительно так для этой сети (“Network_serial”). Чуть ниже я проделаю то же самое с нашей предыдущей сетью (которой я так и не дал название), возможно на ней будут видны изменения. А пока я покажу путь движения трафика для построенной цепочки:

Диаграмма: последовательное соединение свитчей; путь движения трафика для цепочки, построенной без приоритетов

Как и обещал, делаю то же самое для “предыдущей сети” (“цепочка пиров”):

..........11 1  hS/seed -> h10 -> h11 ->
........11.. .  h8 -> h9 ->
..111....... .  h2 -> h3 -> h4 ->
.....111.... .  h5 -> h6 -> h7 ->
11.......... .  h0 -> h1/leech

Изменений (по сравнению с расположением кластеров в “топологии сети”) практически нет. Единственное, что изменилось – это исчез кластер 2, т.к. он был пуст (∅). Означает ли это, что “обход дерева в глубину” не нужен, и достаточно взять кластеры из “топологии сети” (в том же порядке, в котором они будут на этот момент), и удалить все пустые (∅) кластеры? Однако, это не так: во‑первых, чтобы кластеры выстроились в таком “удобном” порядке я использовал сортировку, но она до сих пор не была включена в алгоритм ( надо бы включить, но пока еще рано ;) ; во‑вторых, не для всех сетей этот трюк сработает (попробуйте придумать такую сеть без заглядывания в спойлер).

Простым трансформированием, сеть “предыдущая сеть” превращается в сеть, для которой нужен “обход дерева в глубину” Диаграмма: LLTR гибридная сеть (clear), зеркально скопирована, нужно использовать “depth first traversal”

Я попробовал применить алгоритм (вместе с сортировкой) к этой сети, и, на момент получения “топологии сети”, расположение кластеров стало сильно что‑то напоминать

Ладно, вернемся к построенной “цепочке пиров”, и посмотрим на путь движения трафика…

Note: Здесь должна была быть картинка, но изображение пути движения трафика на такой маленькой диаграмме, стало напоминать спагетти. Не рекомендую смотреть на это.

Одна из попыток изобразить путь

Я даже изменил последовательность соединения пиров, подключенных к одному свитчу (их все равно можно соединять в любой последовательности), но и это не помогло.

Диаграмма: LLTR гибридная сеть (clear); путь движения трафика

Цепочка пиров:

..........11 1  hS/seed -> h11 -> h10 ->
........11.. .  h9 -> h8 ->
..111....... .  h2 -> h3 -> h4 ->
.....111.... .  h5 -> h6 -> h7 ->
11.......... .  h0 -> h1/leech

В этот момент мне захотелось опять взглянуть на путь движения трафика в “Network_serial”…

Теперь я обратил внимание, на то в какой последовательности трафик проходит через свитчи:

           switch0 -> switch1 -> switch2 -> switch3 -┐
switch4 <- switch0 <- switch1 <- switch2 <-----------┘

… и мне очень не понравился “крюк” через “switch0 <- switch1 <- switch2”. Хотелось получить на выходе алгоритма такую последовательность:

                                 switch0 -> switch4 -┐
switch3 <- switch2 <- switch1 <- switch0 <-----------┘

Путь движения трафика для нее:

Диаграмма: последовательное соединение свитчей; путь движения трафика для цепочки, построенной с учетом приоритетов

Путь стал короче, и, главное, нагрузка на сеть уменьшилась!

Note: но меня все же больше привлекает уменьшение количества промежуточных сетевых узлов, т.е. “путь стал короче”.

Note: имеется ввиду именно “количество промежуточных сетевых узлов”, а не “суммарная длина канала” (длина сетевого кабеля; длина пути прохождения сигнала на физическом уровне – L0) – она вполне могла и увеличится.

Чтобы этого добиться, достаточно добавить в “обход дерева в глубину” небольшую эвристику.

Note: эту эвристику я изначально создавал для другой цели, но у нее оказался очень полезный побочный эффект – уменьшение количества промежуточных сетевых узлов.

Эвристика (правило): при “входе в поддерево” (LLTR Часть 0::Топология: “звезда из свитчей”) отдавать приоритет узлам с меньшей вложенностью:

  1. узел – хост;
  2. узел – один свитч;
  3. узел – два свитча (соединенных последовательно);
  4. узел – много свитчей (соединенных как угодно) – чем больше, тем ниже приоритет.

Note: если в тексте этого списка заменить “узел –” на “порт свитча, к которому подключен”, то, возможно, он станет понятнее.

Note: Изначальная цель этих правил – вначале пустить трафик через ближайшие хосты (хосты до которых меньше всего промежуточных устройств). Меньше промежуточных устройств – меньше вероятность возникновения ошибки (при передаче данных) в самом начале пути. Сравните две дорожные ситуации, приводящие к временной пробке (одна полоса): затор случился в начале дороги (буферная зона практически отсутствует); затор случился ближе к концу дороги (размер буферной зоны достаточен для смягчения последствий затора).

Обновим алгоритм:

                                                    ● статистика ●
                                      [бинаризация] ► реакции хостов
     [очистка от пустоты (∅), и от универсумов (⦱)]
                     [очистка от единичных реакций]
                                [очистка от дублей] ► кластеры/лес
                      [добавить "корневой" кластер] ► кластеры/дерево
              [поиск родителя для каждого кластера]
     [построение списка детей для каждого родителя]
                    [исключение детей из родителей] ► топология сети ●
[обход дерева в глубину с учетом приоритетов/весов] ► цепочка пиров ●

И обновленная “цепочка пиров” для “Network_serial” сети станет выглядеть так:

1 1........  hostS/seed -> host0 ->
. .......11  host7 -> host8 ->
. .11......  host1 -> host2 ->
. ...11....  host3 -> host4 ->
. .....11..  host5 -> host6/leech

Что полностью соответствует измененному “пути движения трафика”, который изображен выше.

А вот на “прежнюю сеть” обновление алгоритма никак не повлияло. “Цепочка пиров” осталась прежней:

s0) ..........11 1  hS/seed -> h10 -> h11 ->
s1) ........11.. .  h8 -> h9 ->
s3) ..111....... .  h2 -> h3 -> h4 ->
s4) .....111.... .  h5 -> h6 -> h7 ->
s5) 11.......... .  h0 -> h1/leech

Почему не изменилось? Обновление алгоритма влияет на последовательность свитчей, однако, в этой сети, последовательность уже была оптимальной (обновление алгоритма не смогло ни улучшить и ни ухудшить ее):

s0 -> s1 -> s2 -> s3 -┐
   ┌- s4 <- s2 <------┘
   └------> s2 -> s5

Note: номер свитча “s#” соответствует номеру кластера в “топологии сети” для этой сети (см. выше).

# TL;DR


Алгоритм определения топологии сети и построения цепочки пиров по собранной статистике:

  1. Бинаризация (~~ k‑medoids ~~) + очистка от пустоты (∅), и от универсумов (⦱) + очистка от единичных реакций:
    1. середина между amin и amax
    2. разделить на 2 части посередине
      1. + очистка от пустоты (∅), и от универсумов (⦱)
    3. найти медиану массива левой и правой части:
      1. (Мой любимый алгоритм: нахождение медианы за линейное время)
      2. (Сортировка на односвязном списке за O(nlogn) времени в худшем случае с O(1) дополнительной памяти)
      3. (nth_element implementations complexities)
    4. найти середину между amedL (medLow) и amedR (medHi)
    5. разделить на 2 части по новой середине, и сразу представить в двоичном виде
    6. + очистка от единичных реакций
  2. Дедупликация + добавление “корневого” кластера:
    1. + добавить “корневой” кластер
    2. + отсортировать по bitCount (от max к min)
    3. убрать дубликаты
  3. Поиск родителя для каждого кластера:
    1. начиная с min элемента искать снизу (min) вверх (max) тот (первый попавшийся) элемент, куда входит текущий;
      искать при помощи проверки bitCount(ai)==bitCount(ai|amin), либо более простая проверка: ai==ai|amin
    2. предыдущий шаг выполнять рекурсивно, попутно фиксировать цепочку элементов (путь рекурсии) – к текущему элементу добавлять идентификатор следующего элемента
    3. найти следующий min элемент (не участвующий в цепочке) и повторить рекурсию
  4. Построение списка (карты) детей для каждого родителя:
    1. создать обратную цепочку (от “родителей” к “потомкам”)
  5. Исключение детей из родителей:
    1. когда все элементы будут в “цепочке”, то начиная с max элемента, сделать or|=ai над его потомками, и применить amax&=~or
      (либо “amax^=or” – при корректных данных результат совпадет)
    2. рекурсивно повторить с потомками потомков
      (либо просто двигаемся от amax до amin, т.к. это дерево, и его вершины отсортированы в массиве)
  6. Обход дерева в глубину с учетом приоритетов/весов:
    1. построить маршрут для трафика (RingSync)

Note: примерно в таком виде я записал алгоритм git, перед его реализации в коде.

Немного про структуру кода
Гипотеза. Чем умнее программист (чем более объёмной рабочей памятью он располагает), тем более длинные методы и функции он пишет.

Из “Горе от ума, или Почему отличники пишут непонятный код

Я не настолько умный, чтобы создавать такие большие функции с таким большим количеством переменных, поэтому я использую области видимости (“{…}”) для структурирования (упрощения) кода. Получается аналог вложенных анонимных функций (пример):

// вначале перечислены переменные "возвращаемые из функции"
int ...;{
    // а здесь тело "функции"
}

Если надо дать название “функции”, то оно записывается в комментарии перед блоком (пример):

//==[Name]==//
int ...;{
    ...
}

Если такой код визуализировать, то получится подобная диаграмма:

Tensors Flowing

TensorsFlowing

т.е. каждая область видимости – это отдельный блок на диаграмме, а “переменные, возвращаемые из функции” – связи между блоками.

Что дает такой подход к структурированию?
Это дает:

Note: Мой ответ на тему статьи из которой была взята цитата: т.к. еще до создания своих программ они успели поработать с множеством ресурсоемких приложений (2D/3D графические редакторы, рендеры, другие приложения для моделирования *, …). И им со временем начали надоедать лаги (задержки), возникающие при редактировании проекта, а также тот факт, что финальный просчет может занимать несколько жарких летних дней (в течение которых компьютер, расположенный в спальне, работает 24 часа, и мешает заснуть; это происходило во времена, когда ACPI только появился), в процессе одного из которых взрываются (выстреливают оболочкой) конденсаторы на материнской плате, что явно не добавляет им дофамина :( . Дальше они знакомятся с тонкостями разгона (тайминги, системы фазового перехода, …) и тюнинга операционной системы, чтобы хоть как‑нибудь подправить ситуацию подручными средствами. И наконец, они встречают первое в своей жизни демо, и узнают про демо‑сцену. Уровень их дофамина повышается (они словно видят лучик “нитро” в мире “тормозов”), и просят родителей купить первую в их жизни книгу “по программированию на *”. В общем, они – это те люди, которые сами используют то, что создают, и хотят максимально утилизировать доступные ресурсы. А также у них есть нечеткое разделение (правило) – реализовывать алгоритм для того, кто будет его выполнять. Если это – компьютер (не человек), то пишется код для него. Если это – человек, то ничего нагляднее диаграммы/схемы/инфо‑графики/анимации пока еще никто не придумал/реализовал. А отладочная (debug) реализация находится где‑то посередине.

Note: Это всего лишь Debug версия кода, по которой еще надо несколько раз пройтись профилировщиком (ведь, иногда повторив одно и то же в коде два раза – можно увеличить производительность программы в несколько раз {вроде простое дублирование кода ускорило его в 9 раз, записей про этот вариант не осталось; по ссылке – окончательный вариант с ×16 ускорением (раздел 1.2 и 1.5); скриншоты из профилировщика допосле}), и устранить warning'и компилятора.

Note: Некоторые комментарии в коде могут показаться странными, особенно учитывая тот факт, что после дедупликации размер обрабатываемых данных значительно сократится, и поместится в одну кеш‑линию. В эти моменты я думал, как обрабатывать значительно больший объем данных, и забывал (вытеснял из “рабочей памяти” мозга) этап дедупликации.

# Tooo Long; Didn't Read; Visualize, plz.


Note: Ниже вы увидите анимацию работы каждого из блоков, и анимацию передачи данных между блоками (как в GIF “TensorsFlowing” из спойлера “Немного про структуру кода”). При создании этих GIF меня вдохновляли уже упомянутый “TensorsFlowing” и GIF “Loop over python list animation”. Также, в эти GIF я пытался перенести образы, которые “всплывают в мозге” при чтении/создании этих строк кода. Естественно, из‑за определенных ограничений перенос не может быть осуществлен 1:1, тем не менее “добро пожаловать в мой мозг”.

# Блок бинаризации

Note: При создании GIF я пробовал разными способами разместить код рядом с анимацией (как в “Loop over python list animation”), но не один из вариантов не выглядел хорошо. Поэтому, связанный с анимацией код, я поместил в спойлеры под анимацией. Номер спойлера соответствует номеру этапа в анимации ( номера появляются справа ;)

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

Note: Не во всех браузерах GIF начнет проигрываться с начала (в начале есть надпись “Scroll Down”), для того, чтобы вернуться на начало, я сделал эту кнопку:

Анимация: бинаризация
#1
int average;{
       int max,min;
       max=min=countFill[i][0];
       for(int j=1;j<numHosts;j++){
             max=countFill[i][j]>max?countFill[i][j]:max;
             min=countFill[i][j]<min?countFill[i][j]:min;
       }
       average=(max+min)/2;
}
Кадр: бинаризация – этап 1

Note: на самом деле в GIF нету этого кадра…

#2
int lo=0;
struct CnN{
       int Count;
}iFill[numHosts];
for(int j=0,hi=numHosts-1;j<numHosts;j++){
       if(countFill[i][j]<average) iFill[lo++].Count=countFill[i][j];
       else                        iFill[hi--].Count=countFill[i][j];
}

bitCluster[i]=0;
if(lo==0||lo==numHosts) continue;  //псевдо-очистка от пустоты и от универсумов

Note: эти фрагменты кода (в спойлерах) немного отличаются от кода в репозитории.

Кадр: бинаризация – этап 2
#3
int averageMed;{
       CnN *iFillLo=&iFill[0];
       CnN *iFillHi=&iFill[lo];
       const int hi=numHosts-lo;

       if(lo>1) std::nth_element(iFillLo,&iFillLo[lo/2],&iFillLo[lo],[](const CnN a,const CnN b){return a.Count<b.Count;});
       if(hi>1) std::nth_element(iFillHi,&iFillHi[hi/2],&iFillHi[hi],[](const CnN a,const CnN b){return a.Count<b.Count;});

       averageMed=(iFillLo[lo/2].Count+iFillHi[hi/2].Count)/2;
}
Кадр: бинаризация – этап 3

Note: std::nth_element() работает оптимальнее, чем вариант, показанный на анимации (сортировка + выбор среднего элемента = медиана).

#4
for(unsigned int j=0;j<numHosts;j++) bitCluster[i]|=( (countFill[i][j]<averageMed)?1:0 )<<j;
Кадр: бинаризация – этап 4
#5
bitCluster[i] = bitCluster[i]^(1<<((i/(numHosts-1))+(i%(numHosts-1)+1))%numHosts) ? bitCluster[i]:0;
Кадр: бинаризация – этап 5

Note: Исходники GIF находятся в репозитории git. Перед их просмотром рекомендую прочесть ReadMe (это может сберечь ваши нервные клетки; и если кто‑нибудь знает более подходящий инструмент для визуального создания подобной анимации, то прошу написать про него в комментариях).

Входные данные

Я все‑таки создал в OMNeT++ модель “прежней сети”, а полученную статистику сохранил в “DAT_EX.h”.

# Протокол прощения с жизнью


Написание первых 3‑х частей растянулось на 1.92 года, и я не уверен, что за 1.6 - 2 месяца успею дописать оставшиеся части. При том, что описанные в первых 3‑х частях события длились (в реальной жизни) чуть меньше месяца (за который я также успел написать первую реализацию на Go – это заняло 2 дня, и провести эксперимент на реальной сети – 2 - 4 дня). Затем был перерыв (4 месяца), и еще 2.5 месяца работы над LLTR.

В спойлере находятся наброски оставшихся частей + TODO’шки + ссылки на исходники.

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

Note: в конце понимаешь, сколько знаний/идей ты не описал, и они просто умрут вместе с тобой…

спойлер

Прошло ли 2 месяца с момента публикации этой статьи?

Нет

Любопытно?

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

Да
Продолжение данной части

# Tooo Long; Didn't Read; Visualize, plz.


TODO[old]: сделать анимацию каждого этапа алгоритма (1 этап – gif_1, стрелка вниз, 2 этап – gif_2, стрелка вниз, …)

TODO: сделать анимацию каждого этапа алгоритма, разместить каждую анимацию в своем подразделе

Стикер: демонстрация побитового & – он ипользуется где‑то в алгоритме

(набросок элементов и анимации одного из этапов)

TODO: сделать общую анимацию передачи данных между блоками (как в GIF “TensorsFlowing”, только направить поток данных сверху‑вниз – как в коде программы), разместить ее в последнем подразделе

(объяснить в Note, почему я выбрал именно GIF для анимации, а, например, не загрузил видео на YouTube. Ответ простой: субдискретизация 4:2:0 и TV‑диапазон яркостей (динамический диапазон 16 - 235). Первое создаст цветные ореолы на границе цветных однопиксельных линий и белого фона, а второе – сделает белый фон тусклым (серым). Другие форматы: SVG – были бы проблемы с рендером текста, и при рендере “желтой обводки‑подсветки”; SWF – R.I.P.)

# Что еще можно ускорить?


Избавится от структур (массивов структур), и адаптировать реализацию используемых std функций (например, сортировки) для работы с отдельными массивами (которые получились после избавления от структур);

Можно ускорить нахождение родителей (пропуская кластеры с количеством “1” == количеству “1” текущего кластера). Пример:

0) 111111111111
1) 1111111111..
2) 11111111....
3) ..111.......
4) .....111.... <- текущий кластер, можно сразу прыгнуть ко 2‑му, пропустив 3‑й
5) 11..........

Это можно сделать (т.е. это безопасно), т.к. пересекающихся кластеров с одинаковым количеством “1” быть не может (дублей мы удалили ранее) (см. “невозможный пример” из примеров “потокового разделителя”). Для этой оптимизации необходима дополнительная информация об индексе конца предыдущего диапазона с большим числом “1”, т.е.:

0) 111111111111 
1) 1111111111..  0
2) 11111111....  1
3) ..111.......  2
4) .....111....  2
5) 11..........  4

(вставить более наглядный пример с сетью, похожей на бинарное дерево – нарисовать диаграмму сети + представить в текстовом виде (кластеры+индексы), как сделано выше)

Информацию об индексе можно получить на этапе сортировки (ее все равно уже собрались “препарировать”). Главное в конце оценить суммарное время CPU, затраченное на сортировку + поиски родителей. Оно вполне может стать больше, чем прежде, если дополнения, внесенные в сортировку, сильно замедлят ее.

3: OMNeT++ продолжение

LLTR Часть 3: OMNeT++ продолжение

Неудача с первой реализацией на Golang. (просто упомянуть факт, что она была)

(вначале сделать бекап, и обновится до последней версии OMNeT++ c исправленным Qtenv)

(перейти на фон “background/fresh” для “.ned” {“grey99” → “-,-,0;bgi=background/fresh”}, и “blueprint/print-26.png” для фона Qtenv из “LLTR Часть 1::Набор узоров для фона”)

(улучшение результатов, из “OMNetProject (v0.9) lltdapp”)

(при объяснении, почему на хостах с разным удалением от “hostS” доходит разное количество пакетов – сразу запустить симуляцию (с большим количеством промежуточных свитчей) и открыть одну из очередей свитча в инспекторе. Показать, что, при свободном месте в очереди – доходит broadcast пакет, а за ним приходит unicast пакет, но т.к. очередь заполнена – он отбрасывается, и так происходит всегда. Вот что бывает в идеальном мире, в неидеальном мире – есть “спонтанные задержки”. “идеальный мир – мертвый мир”, из Лангольеров: “здесь нет эхо” – вспомнить про результаты сети “Serial” из “Части 1” (проблема с концами – “затухание воздействия”). Попробовать добавить еще несколько промежуточных свитчей – ситуация должна улучшится (задержка, создаваемая свитчами, поменяла порядок broadcast и unicast пакетов)[показать как добавить rand либо сейчас, либо сказать, что добавим в будущем – в зависимости от того, как я делал ранее – в исходниках])

(ссылка Precision Time Protocol (PTP) дата сохранения 2016-04-12)

(для версии с предварительно рассчитанным временем – создать отдельную ветку, и именовать теги иначе, например “a3_v0.3_ft0.1.0”, где “a3_v0.3.0” – коммит, с которого началось разветвление; “ft” – fixed time)

Развитие модели.

TODO[x]: добавить ссылки на архивы, при этом упомянуть про различия в коде, подробнее про различия см. “TODO[x]” перед “ссылки на исходники” после списка спойлеров (с содержимым частей)

Ссылки:

4: Математика

LLTR Часть 4: Математика

Wolfram Mathematica – Numbers (last episode 1 season) – см. на книжку на столе

Поиск закономерностей и написание формул

∀ habrauser ∈ {user ∈ Habrahabr | user пришедший с хаба “Математика”},

Существует ненулевая вероятность того, что и в этот раз комментарии к статье окажутся “интереснее” самой статьи.

(написать, что эта статья посвящена мат. индукции)

Ссылки:

Лучше всего, когда число хостов (hostsCount) – степень двойки. В этом случае получится использовать специальную формулу. Чем эта формула так хороша? (подсказка: одинаковые расстояния)

(написать, что я не использую слово “доказательство”, но его смысл включаю в такие слова как {“вывод”,“получение”,“написание”})

(в спойлере рассказать про вывод еще одной полезной формулы для быстрого разложения числа (в двоичном виде) на комбинацию [количество единичных бит в числе; номер “битовой перестановки”], и обратной формулы – для быстрого получения n‑й “битовой перестановки”; упомянуть, что они не используются в LLTR, они могут помочь при сжатии данных)

Permutation of bitsets (“lexicographic” order) derivation (mathematical induction)

(привести пример того, что это _штука_ делает [можно взять пример из таблицы, сказать, что она работает как в прямом направлении, так и в обратном]):

n=4; k=2
bitset  i
0011 <- 0
0101 <- 1
1001 <- 2
0110 <- 3
1010 <- 4
1100 <- 5

Note: используется лексикографический порядок, т.е. bitsetki < bitsetki+1, где i – номер “битовой перестановки”; k – количество единичных бит; n – количество бит в числе.

Где “мясо” (получение формул; функции/код; и программа, которую можно собрать и “распотрошить”/отладить), и с чего лучше начать?

  • открыть таблицу (обратить внимание на ячейку “B9”) (оказывается “электронные таблицы” бывают полезными O_o; люблю их использовать для визуального наблюдения за числами, и визуального поиска закономерностей)
  • скачать исходники
  • изучить “_tmain()” (не обращая внимания за закомментированные куски кода)
  • собрать программу, запустить ее, и на основе ее вывода – проверить свои догадки насчет предназначения функций “med()” и “demed()

Жалко, что это прошло мимо меня:

Но есть и отличия:
Здесь используется “битовая перестановка” (“перестановка с повторением”; либо корректнее “Permutations of multisets”).
В чем отличие? В обычной перестановке повторяющихся элементов нет (пример [abcdef]), но в нашем случае они есть (пример [000011]).
Если же взять алгоритм генерации перестановок, и ограничится сопоставлением (сделать замену):

a => 0
b => 0
c => 0
d => 0
e => 1
f => 1

, то ничего не получится, т.к. одним из вариантов перестановки, генерируемых алгоритмом, будет [abcdfe] ⇒ [000011], однако вариант [000011] уже есть в нашем наборе. (следовательно, алгоритм не подходит)

Попробуем определить количество вариантов для нашего случая {{000011}}.
Число всех перестановок {abcdef} равно 6! ( nuclphys.sinp.msu.ru/mathan/p1/m0204.html ).
Исключим из него лишние перестановки.
Так, например, на каждую уникальную перестановку (например [000011]) будут сгенерированы дубли, (переставляющие единицы (“1”) 2! раз  ×  переставляющие нули (“0”) 4! раз) = 2! × 4! = 2! × (6−2)! .
В итоге получим количество вариантов для нашего случая = 6! ∕ (2! × (6−2)!) .

Эта запись очень напоминает формулу для расчёта числа сочетаний ( nuclphys.sinp.msu.ru/mathan/p1/m0204.html ), но по определению ( ru.wikipedia.org/wiki/Сочетание?stable=1 ) наш случай – это не сочетание. Для нас порядок следования элементов важен. Тогда может это “размещение с повторениями” ( ru.wikipedia.org/wiki/Размещение?stable=1 ), однако в нем нельзя “зафиксировать” конкретное число повторений “1” и “0” – в нем перебираются все возможные варианты повторений ( ru.wikipedia.org/wiki/Размещение?stable=1#Количество_размещений_с_повторениями ).

Пора переключится на EN: сочетания → комбинации → combination: ( k‑combination with repetitions / k‑multicombination / multisubset ), и увидеть пример ( en.wikipedia.org/wiki/Combination?stable=1#Example_of_counting_multisubsets ), использующий “Stars and Bars” ( en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)?stable=1#Proofs_via_the_method_of_stars_and_bars ). Что позволяет представить двоичную запись числа в виде звездочек и ящичков (границ/перегородок ящичков): “1” – Star, а “0” – Bar.

Вот так, через “Stars and Bars” были связаны “сочетания” (и “сочетания с повторением” – k‑combination with repetitions) с “перестановками с повторением” (permutations of multisets): en.wikipedia.org/wiki/Permutation?stable=1#Permutations_of_multisets .
Возвращаясь на RU: ru.wikipedia.org/wiki/Перестановка?stable=1#Перестановки_с_повторением

P.S. код из ответа stackoverflow.com/a/24257996 генерирует не варианты Перестановок, а варианты Размещений ( Перестановка – частный случай Размещения: n!∕((n−k)!); n⩵k; (n−k)!⇒1; n! ).

P.P.S. [скорее обращение к @alisey и @Trif] если раньше где‑нибудь в сети встречали похожий алгоритм/код (для “Permutations of multisets”), то можете оставить ссылки в комментариях?

5: OMNeT++ продолжение 2

LLTR Часть 5: OMNeT++ продолжение 2

Почти все готово

(нужно еще адаптировать LLTR-Process под новую sequence, вначале сделать простой вариант – просто переупорядочим новые данные под старую последовательность {именно этот вариант находится в “LLTD-Process (vFinal)”}, а затем сделать вариант получше – без переупорядочивания данных, просто заменить в нужном месте формулу расчета i → dstId, а предыдущий вариант можно использовать в качестве теста для улучшенного варианта)

Ссылки:

6+7: Реализация + Эксперимент

LLTR Часть 6: Реализация

Таймеры и счетчики систем, программа на Golang.

Ссылки:

LLTR Часть 7: Эксперимент (название: “в конце Джон умрет” – фильм)

(Что делать если для эксперимента нужно минимум 4 сетевых устройства {без учета свитчей/роутеров/Wi‑Fi}, а у вас их только 3 и больше ничего нет? Сделать из одного из устройств – 2 устройства! Один из устройств – MacBook, у которого есть Wi‑Fi и Ethernet через Thunderbolt)

(Если собрать стенд из того, что “лежит под рукой”, то можно узнать много нового о том, что “лежит под рукой”)

(Проблема с Wi‑Fi и UDP broadcast пакетами – ограничение скорости на уровне WNIC/прошивки/драйвера. Подробнее: How to override wifi broadcast speed limit?, Why does my UDP Broadcast wireless communication is capped at 1MBs?. В моем случае ограничение было либо 3 Mbps, либо 5 Mbps {точно уже не помню}. В итоге MacBook {Wi‑Fi интерфейс} стал Super‑хостом, только теперь он отправляет не broadcast‑пакеты, а unicast, а промежуточное сетевое устройство {Wi‑Fi-роутер или свитч‑роутер} преобразует unicast‑пакеты в broadcast {не передавая его назад – на Wi‑Fi}. В общем, с Wi‑Fi-роутером не получилось – CPU был слишком слаб для такой скорости. Поэтому пришлось делать это на свитч‑роутере.)

(Почему используется такой большой размер UDP‑пакета, он же будет фрагментироваться!? Ответ: для Windows используется “блокирующая” запись в сокет {Windows ждет пока драйвер NIC не сообщит об успешной отправке?..}, к этому добавляются накладные расходы на частый вызов API, “съедающие CPU” {в Win8 был добавлен новый API, который в том числе минимизирует операции копирования данных… (см. ссылки в “LLTD/flood/main.go”)}. К тому же придется использовать таймер с “высоким разрешением”. Поэтому самое простое решение – одним вызовом API сразу отправляем большую порцию данных, которой должно хватить до следующего “тика” таймера. А в *nix запись асинхронная {моментальный возврат после вызова API}, можно использовать обычный размер пакета, и в каждом “тике” таймера делать несколько отправок данных {см. комментарии в “LLTD/flood/main.go”}. В тему: “iperf3 and microbursts”)

(В ходе эксперимента исходники постоянно менялись → нужно синхронизовать изменения между ПК. Для этого просто использовался файловый сервер {один из ПК; SMB}: менялись исходники → собирались под все платформы → копировались на файловый сервер → MacBook создавал локальную копию. Все ПК запускали локальную копию, чтобы минимизировать влияние на сеть во время эксперимента.)

(описание подготовки окружения для эксперимента находится в файле “LLTD/Prepare test environment.txt”)

Ссылки:

(часть собранной статистики находится в файле “LLTD/Client.go”, а статистики “по‑отдельности” – внизу “LLTD/flood/main.go”)

(также на одном из ПК {Client1} NIC и раньше не любил, когда его закидывают большим числом пакетов – мог спонтанно отключиться, и помогало только полное обесточивание, то теперь я научился “по желанию” выводить его из строя: строчка в статистике “ interface always dead”)

Note: Джон – Wi‑Fi роутер (точнее ADSL‑модем/роутер, в котором отпала необходимость в ADSL и роутер части – используется как точка доступа)

Note: Со свитчом‑роутером тоже не получилось: он спокойно “переваривает” 100 Mbps входящего unicast трафика; он может спокойно сам генерировать 100 Mbps broadcast трафика. Но у него не получается делать это одновременно (по крайне мере, если использовать те правила/настройки, которые я задал)

TODO: Эксперимент с форматом статьи: одну из статьей опубликовать в виде комментариев к статье (каждый абзац – отдельный комментарий; можно оставлять комментарий сразу же к конкретному абзацу; можно будет даже голосовать +1/−1 за конкретный абзац). Это будет похоже на Google Wave, или на комментарии в Google Docs, или на контекстные комментарии Discus. Формат:

Также нужно будет создать UserJS/UserCSS, скрывающий все, кроме первого уровня комментариев, т.е. комментариев, содержащих саму статью.

Также такой формат повлияет и на содержимое статьи – на размер ее абзацев – они должны быть крупными, чтобы UI комментариев (ник, аватарка, дата) встречались как можно реже (если будут встречаться часто, то взгляд будет постоянно о них “спотыкаться”). Либо уменьшить “шум” от этих элементов при помощи UserCSS. И все же я думаю, что не стоит их полностью убирать, чтобы оставалось ощущение, что находишься в комментариях (в иерархии комментариев), и можешь задать вопрос (оставить комментарий) прямо здесь (на месте).

Через некоторое время продублировать содержимое статьи (из комментариев) в спойлере (в тексте после ката). В основном это нужно для мобильной версии хабра (основные мобильные браузеры вроде бы не поддерживают UserJS и UserCSS; Opera Presto поддерживала, Firefox тоже вроде поддерживает)

Оптимальный кандидат для эксперимента – статья “OMNeT++ продолжение 2”.

TODO[x]: при вставке ссылок на исходники представить их в виде веток (дерева) + добавить комментарии, что в них было сделано + комментарий, про то, что это создавалось на старой версии OMNeT++ v5.0b1 и INET v3.0.0 + сказать про то, что для статей я переписывал исходники (менял название переменных), и чтобы легче было ориентироваться – указать какие старые исходники соответствуют каким коммитам/тегам в репозитории

Ссылки на исходники:

В предыдущих статьях (частях) были фотографии стикеров (листочков), на которых я делал заметки. Я называю их “заметки перед сном” – записи идей, родившихся во время засыпания.

Note: пока я не запишу идею – я не могу заснуть, а самый быстрый (в это время) способ сохранить идею – нарисовать на листочке.

К каждой части я хотел добавлять соответствующие “заметки перед сном”, либо сфотографировав, либо нарисовав “в векторе”.

Все “заметки перед сном”, за исключением тех, фотографии которых уже были в предыдущих частях:

Стикеры: просто стикеры и TOP SECRET

В каждой строке – скан одного и того же листочка с двух сторон. В тех случаях, когда на обратной стороне не было полезной информации – заполнял пробел “случайной заметкой”.

Note: “кулер” – хотел рассчитать соотношение теплоотвода (теплового сопротивления−1) к шуму (звуковому давлению) для такой конструкции и ее вариаций (например: тепловые трубки смещены к центру; основная крыльчатка находится снаружи; поток воздуха от центра – наружу); “хабра‑карма‑кластеры‑сообщества” – (представляя гиперповерхность) локальных экстремумов много, и было бы удобно видеть только то, что позволит тебе достигнуть ближайший экстремум как можно быстрее (чтобы начать путь к следующему экстремуму), и скрывать все, что будет перетягивать в другой локальный экстремум {а чтобы была возможность выбраться из “пузыря” (локального экстремума) – сделать карту кластеров, при клике в которой, можно посмотреть “а что там у других?”; + ситуация “хочу посмотреть статьи 'для меня', но не хочу логинется а чужом устройстве”, решение: отдельный идентификатор пользователя (cookie) для режима view‑only}

Note: заметки расположены в хронологическом порядке (сверху‑вниз)

А также текстовые заметки

LLTD v1 – с синхронизацией по TCP (нужен map?), сбор статистики в процессе,
и прикрутить отсечение лишних (симметричных) зондирований, если зондирование в одном направлении уже дало результат

LLTD v0.9 – на client собирать статистику в текущей итерации не до прихода следующего синхросигнала, а до истечения времени (и прихода синхросигнала)

либо сделать тестовую реализацию v0.5 на Go
для определения IP, в будущем переписать github.com/hashicorp/mdns
github.com/davecheney/mdns
grokbase.com/t/gg/golang-nuts/132tcpawde/go-nuts-udp-multicast-who-is-on-my-network

P.S. при рандомизации таймеров (в модели) использовать “нормальное распределение”.
r=rand();
Взять количество единичных бит у r, и функцию расчета номера перестановки бит при заданном числе бит.
Сделать два варианта:
1. нормально‑ступенчатое распределение. Количество единичных бит дает нормальное распределение, а номер перестановки – равномерное. Берем количество единичных бит за основу случайного числа + уточняем его при помощи +/- номера перестановки (с масштабированием в пределах текущей “ступеньки” нормального распределения).
2. “мешанина”. Берем номер перестановки за основу (при этом учитываем, что диапазон его значений всегда разный и зависит количества единичных бит; поэтому его надо масштабировать на весь диапазон случайного числа) + уточняем его количеством единичных бит (отмасштабированным в пределах текущей “ступеньки” равномерного распределения)

iperf3 and microbursts burntchrome.blogspot.ru/2016/09/iperf3-and-microbursts.html

# Check‑list (TODO's)

Мои TODO, которые я использовал при подготовке статей.

Подготовка PNG{SVG} (SVG с thumbnail в виде PNG) изображений:

  1. PNG:
    1. [если ширина изображения превышает 778px, 756px] придется где‑нибудь подрезать (подробнее см. в этапах подготовки любых изображений)
    2. добавить метку‑иконку 7z (un[7z]me), расположить в наиболее не отвлекающем месте (главное – чтобы не “висело в воздухе”, а было продолжением какой‑либо группы объектов, но при этом было визуально‑логически отделено от нее)
      • [если иконка добавлялась в Photoshop] для сохранения использовать “Save for Web” → PNG 24+alpha
      • [если иконка добавлялась в GIMP] экспортировать в “8bpc RGBA” (все остальные опции можно отключить), либо аналогичный режим в “Save for Web
    3. уменьшить количество цветов до 256 + alpha‑прозрачность
    4. “дожать” изображения, используя Image Catalyst (я “параллельно” использовал 2 версии: 2.1 и 2.5, а затем оставлял файл минимального размера):
      1. “закинуть” копию изображений в Image Catalyst 2.1 ([5] Xtreme profile)
        Tools\config.ini
        [options]
        ;Если Вы не хотите оптимизировать изображения в подпапках указанной папки, то замените значение "true" на "false".
        fs = true
        
        ;Количество одновременных потоков обработки PNG. Если указано значение 0, то выбирается значение равное системной переменной %NUMBER_OF_PROCESSORS%.
        threatpng = 0
        
        ;Обновление проекта. Если Вы не хотите автоматически проверять доступность новой версии проекта, то замените значение "true" на "false".
        up = false
        
        [JPEG]
        ;Удаление Metadata. Если Вы не хотите удалять определенные Metadata в JPEG, то замените значение "true" на "false" там, где это необходимо.
        dc = true    ;Delete comment field (as left by progs like Photoshop & Compupic).
        de = true    ;Strip Exif section (smaller JPEG file, but lose digicam info).
        di = true    ;Delete IPTC section (from Photoshop, or Picasa).
        dx = true    ;Deletex XMP section.
        du = true    ;Delete non image sections except for Exif and comment sections.
        
        [PNG]
        ;Оптимизация ColorType и BitDepth. Если Вы не хотите изменять ColorType и BitDepth в PNG, то замените значение "true" на "false".
        nc = true
        
        ;Оптимизация альфа-канала. Если Вы не хотите применять систему "Dirty Transparency" для PNG c альфа-каналом, то замените значение "true" на "false".
        na = true
        
        ;Удаление Chunks.
        ;Если Вы хотите удалить определенные Chunks или группы Chunks, то пропишите "remove" без кавычек и через запятую те Chunks или группы Chunks, которые хотите удалить.
        ;Если Вы хотите оставить определенные Chunks или группы Chunks, то пропишите "keep" без кавычек и через запятую те Chunks или группы Chunks, которые хотите оставить.
        ;Группы Chunks:
        ;text  = iTXt,tEXt,zTXt
        ;color = cHRM,sRGB,iCCP,gAMA
        ;misc  = bKGD,pHYs,sBIT,sPLT,hIST,tIME
        ;all   = all of noncritical chunks
        сhunks = remove all

        Note: если он выводит “Image Catalyst 2.1 уже запущен. Для выхода из приложения нажмите на Enter.”, хотя это не так, то переименуйте папку, в которой он находится (я переименовал “Image Catalyst 2.1” в “Image-Catalyst-2.1”)

      2. “закинуть” копию изображений в Image Catalyst 2.5 ([1] Xtreme profile)
        Tools\config.ini
        [options]
        ;Number of streams. If value early 0, is used value of parameter %NUMBER_OF_PROCESSORS%.
        thread=0
        
        ;Automatic replacement of original images by the optimized.
        outdir=true
        
        ;Check update
        update=false
        
        [PNG]
        ;Parameters of optimization of PNG:
        ;/a# - PNG dirty transparency 0=Clean, 1=Optimize;
        ;/g# - PNG gamma 0=Remove, 1=Apply & Remove, 2=Keep;
        ;/na - PNG don't change RGB values for fully transparent pixels;
        ;/nc - PNG don't change ColorType and BitDepth;
        ;/np - PNG don't change Palette.
        xtreme=/a1 /g0
        advanced=/a0 /g0
        
        ;Remove PNG Metadata (Chunks).
        chunks=true
        
        [JPEG]
        ;Remove JPEG Metadata.
        metadata=true
        
        [GIF]
        ;Remove GIF Metadata.
        giftags=true

        Note: если он выводит “Attention: running 2 of Image Catalyst.”, хотя это не так, то переименуйте папку, в которой он находится (я переименовал в “iCatalyst-2.5”)

      3. оставить файлы наименьшего размера
        merge_min.bat
        @echo off
        setlocal enabledelayedexpansion
        
        :: Copy file from source to destination directory only if
        :: source file is smaller in size than in destination directory
        
        echo Src dir: %~f1
        echo Dst dir: %~f2
        
        echo ---
        
        for /r "%~1" %%A in (*) do (
          set FileA=%%~fA
          set FileB=!FileA:%~f1=%~f2!
        
          set FileASize=%%~zA
          for %%Z in ("!FileB!") do set FileBSize=%%~zZ
        
          if !FileASize! LSS !FileBSize! copy "!FileA!" "!FileB!"
        )
    5. добавить “.svg” после имени файлов (перед расширением) – будет влиять на расширение файла (SVG) после его распаковки (un[7z]me)
  2. SVG:
    1. экспортировать с настройками {SVG 1.1; UTF-8; стили внутри файла; единица измерения: пиксели; точность: “1:100”; текст преобразовать в кривые} (если до этого была выбрана другая единица измерения, то придется экспортировать 2 раза – в 1‑й раз будут установлены неверные размеры)
    2. избавится от всех transform в созданном SVG (в основном они создаются после поворота прямоугольника на 90 градусов) (для ускорения поиска можно экспортировать в SVG содержимое всей страницы):
      1. в браузере в DevTools найти все объекты с transform (используя селектор “[transform]”)
      2. убрать поворот в исходнике при помощи макроса “Rotate90AndSwapWH()” (я поместил его в “глобальные макросы”)
        Rotate90AndSwapWH()
        Sub Rotate90AndSwapWH()
            Dim sr As ShapeRange, s As Shape, w#, h#
            Set sr = ActiveSelectionRange
        
            On Error Resume Next
        
            boostStart2 "Rotate 90 and Swap W-H"
            For Each s In sr
                s.GetSize w, h
                s.Rotate -90
                s.SetSizeEx s.CenterX, s.CenterY, w, h
            Next s
            boostFinish2
        End Sub

        + boostStart2/boostFinish2:

        Я их немного изменил:

        Private Sub boostStart2(ByVal unDo$)
            On Error Resume Next
            ActiveDocument.BeginCommandGroup unDo
            Optimization = True
            EventsEnabled = False
        End Sub
        Private Sub boostFinish2()
            On Error Resume Next
            EventsEnabled = True
            Optimization = False
            ActiveWindow.Refresh
            ActiveDocument.EndCommandGroup
            'Refresh
        End Sub
    3. перед финальным экспортом добавить корректирующий положение и размер прямоугольник:
      • залить его белым
      • без абриса
      • он должен:
        • покрывать все пиксели изображения (причем его размеры [ширина, высота] должны быть четными числами)
        • быть привязан к пиксельной сетке (к краю пикселя)
      • перенести на задний план
    4. экспортировать (с описанными выше настройками)
    5. подправить XML (добиться соответствия по структуре с уже экспортированными файлами)
      1. скопом (во всех файлах):
        • заменить “DOCTYPE” и комментарий “Creator” на комментарий “96ppi” (именно таким должен быть ppi у документа в CorelDRAW перед импортом в него этого SVG)
        • стереть “metadata”, “id” (у внешней группы)
        • в атрибутах тега svg:
          1. стереть “xmlns” и “xml:space
          2. стереть “xmlns:xlink
          3. [проверить, что в “style” во всех файлах есть “fill-rule:evenodd; clip-rule:evenodd”] заменить “version” и “style” на `style="margin:16px auto" shape-rendering="geometricPrecision" fill-rule="evenodd" clip-rule="evenodd" xmlns="http://www.w3.org/2000/svg" version="1.1" baseProfile="full"`
        • заменить (убрать пробел) ` "` на `"`
      2. удалить корректирующий прямоугольник (он будет первым <rect> в <g>), проверив, что его размеры соответствуют размерам “viewBox” (в <svg>)
        • проверить, как SVG выглядит в браузере, и как выглядит после импорта в CorelDRAW – все должно быть четким, если края объектов получились размытыми, то это означает, что корректирующий прямоугольник не был корректно расположен (придется исправить его положение в исходнике, и повторить предыдущие пункты заново)
      3. оптимизировать в SVG optimiser:
        • настройки:
          • Whitespace: pretty
          • Style type: optimal
          • Truncate * numbers: unchanged
          • включить все опции (если нужно сохранить группы, то отключить “Remove clean group”, и затем вручную убрать одноэлементные группы)
        • не заменять оригинальные атрибуты тега <svg>
        • не заменять содержимое тега <style> – в нем SVG optimiser только убирает CDATA (не изменяя сами стили)
      4. отформатировать XML
  3. Объединить PNG со сжатым SVG:
    1. воспользоваться “PNG_SVG.bat” (лучшие параметры 7-Zip для сжатия SVG: “-txz -m0=LZMA2:lc1:pb0 -mx”)
      PNG_SVG.bat
      @echo off
      setlocal enabledelayedexpansion
      
      :: PNG+7Zip{SVG}
      
      echo PNG dir: %~f1
      echo SVG dir: %~f2
      
      echo ---
      
      for /r "%~2" %%A in (*.svg) do (
        set SVG=%%~fA
        set PNG=!SVG:%~f2=%~f1!.png
      
        "%ProgramFiles%\7-Zip\7z.exe" a dummy -txz -m0=LZMA2:d96m:fb74:lc1:pb0 -mx -so -- "!SVG!" >> "!PNG!"
      )

      Как была получена “LZMA2:d96m:fb74:lc1:pb0”?

      Параметры подбирались слева‑направо (для “RingSync_no_problem.svg”):

      - "LZMA2:d96m:fb64"         6804 byte
      - "LZMA2:d96m:fb74"         6800 byte
      - "LZMA2:d96m:fb74:lc2"     6812 byte
      - "LZMA2:d96m:fb57:lc2"     6780 byte
      - "LZMA2:d96m:fb57:lc1"     6768 byte
      - "LZMA2:d96m:fb56:lc1"     6760 byte
      - "LZMA2:d96m:fb49:lc1"     6760 byte
      - "LZMA2:d96m:fb56:lc1:pb0" 6696 byte
      - "LZMA2:d96m:fb46:lc1:pb0" 6688 byte (fb44-fb47)
      - "LZMA2:d96m:fb63:lc1:pb0" 6688 byte
      - "LZMA2:d96m:fb66:lc1:pb0" 6684 byte
      - "LZMA2:d96m:fb74:lc1:pb0" 6692 byte

      Для всех остальных svg размер сравнивался с “LZMA2:d96m” (fb64), и “LZMA2:d96m:fb74:lc1:pb0” всегда был меньше.

Note: я использую немного измененный Image Catalyst: заменил ping на timeout, и сделал (для версии 2.5) вывод размера в байтах (как было в версии 2.1 – для возможности сравнения размеров между этими двумя версиями)

Image Catalyst.bat

v2.1 diff:

182c182
< if defined thrt >nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:waithreat
---
> if defined thrt >nul 2>&1 timeout /t 1 /nobreak & goto:waithreat
203c203
< 1>nul 2>&1 ping -n 1 -w 500 127.255.255.255
---
> 1>nul 2>&1 timeout /t 1 /nobreak
237c237
< if exist "%~1" (1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:waitflag)
---
> if exist "%~1" (1>nul 2>&1 timeout /t 1 /nobreak & goto:waitflag)
513c513
<      if exist "%tmppath%\typelog.lck" (1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:savelog)
---
>      if exist "%tmppath%\typelog.lck" (1>nul 2>&1 timeout /t 1 /nobreak & goto:savelog)
534c534
< if "%jpeg%" equ "0" if "%png%" equ "0" 1>nul ping -n 1 -w 500 127.255.255.255 2>nul & goto:finmessage
---
> if "%jpeg%" equ "0" if "%png%" equ "0" 1>nul timeout /t 1 /nobreak 2>nul & goto:finmessage
572c572
<      1>nul ping -n 1 -w 500 127.255.255.255 2>nul
---
>      1>nul timeout /t 1 /nobreak 2>nul

V2.5 diff:

319,320c319
<      call:division float 1024 100
<      call:echostd " In    - !float! КБ"
---
>      call:echostd " In    - !float! байт"
322d320
<      call:division change 1024 100
324,325c322
<      call:division float 1024 100
<      call:echostd " Out   - !float! КБ (!change! КБ, %5%%%%%%)"
---
>      call:echostd " Out   - !float! байт (!change! байт, %5%%%%%%)"
362,363c359,360
< set /a "ww=%random%%%%1"
< 1>nul 2>&1 ping -n 1 -w %ww% 127.255.255.255
---
> set /a "ww=%random%%%%1/1000"
> 1>nul 2>&1 timeout /t %ww% /nobreak
707c704
< if %jpeg% equ 0 if %png% equ 0 if %gif% equ 0 1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:finmessage
---
> if %jpeg% equ 0 if %png% equ 0 if %gif% equ 0 1>nul 2>&1 timeout /t 1 /nobreak & goto:finmessage
741d737
< call:division changePNG 1024 100
747d742
< call:division changeJPG 1024 100
753d747
< call:division changeGIF 1024 100
800c794
<      call:echostd " Total %1:          %%change%1%% КБ, %%perc%1%%%%%%"
---
>      call:echostd " Total %1:          %%change%1%% байт, %%perc%1%%%%%%"

Note: батники Image Catalyst сохранены в кодировке (кодовой странице) CP866, поэтому эти diff, перед использованием, нужно сохранить в ней же.

Подготовка любых изображений:

Note: оказывается теперь habrastorage поддерживает SVG (раньше не поддерживал): пример (картинка), но я все равно оставил PNG{SVG} (в разных браузерах используется разный рендр SVG, даже в разных версиях одного браузера, и в разных режимах одной версии браузера – изображение может отличаться) (в растровом изображении максимум, что может исказится при рендере, кроме пропорций/размера – это гамма‑кривые / цветовой профиль, а в векторном к этому добавляется искажение геометрии)

Текст и git:

Note: habrahabr поддерживает тег <oembed>, можно вставлять исходники прямо с GitHub, пример использования.

Note: так TODO‑список выглядел только в самом начале, затем он разросся до 43 KiB (для “Части 0”), до 69 KiB (для “Части 1”), и до 45 KiB (для этой части).

Комментарии на Хабре →

DOI: 10.5281/zenodo.1407060