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

    Link Layer Topology Reveal logo


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


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


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


    статистика –-[*магия*]--> топология сети --[*магия*]--> цепочка пиров


    Если понравилось читать “Часть 1” на GitHub Pages, то вот ссылка на эту часть в GitHub Pages.


    Warning: Ниже будут встречаться те же самые артефакты Хабра‑парсера, о которых я предупреждал в “Части 1”.


    Любая достаточно развитая технология неотличима от магии. — Arthur C. Clarke


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


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


    {300,164,164},


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


    • нормальная скорость (значение “300”) – отсутствие реакции;
    • скорость упала (значение “164”) – есть реакция.


    К чему я клоню? К бинаризации! Если мы закодируем отсутствие реакции как 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 – есть реакция;
    • .” означает 0 – отсутствие реакции.


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


    .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 свитча (я считал только свитчи, подключенные “снизу”, без учета того, что он подключен к еще одному свитчу “сверху”), у каждого из которых есть хосты.


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


    • broadcast хост (он отсутствует во входных данных/статистике);
    • порты, соединяющие свитчи между собой.

    Диаграмма: 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


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


    • в “aa” попадают элементы, уникальные для “a”;
    • в “bb” – уникальные для “b”;
    • в “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”, забыв все, что было после нее, но оставив эту ветвь для истории.


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


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


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


    <strong>..........11</strong>  <--
    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


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


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


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


    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 хостов!


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


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


    Мы удаляем пустые множества (∅; “.........”), но зачем удалять универсумы (⦱; “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 -> <strong>h11</strong> -> <strong>h10</strong> ->
    ........11.. .  <strong>h9</strong> -> <strong>h8</strong> ->
    ..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


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


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


    • Свободу перемещения частей кода – я могу (если это потребуется) быстро перенести часть кода из одного блока в другой блок, реорганизуя тем самым последовательность действий. Мне не нужно заботиться о передаваемых в “функцию” параметрах, т.к. любая “функция” уже “видит” все переменные из внешних областей видимости. Также, если для оптимального выполнения кода нужно будет сделать “нечто странное”, то это можно будет сделать.
    • Все в одном месте – не нужно “прыгать” по множеству функций / файлов в проекте, чтобы понять, что конкретно делает этот код. Достаточно прочесть его последовательно от начала до конца. Это похоже на чтение дизассемблированной программы, при сборке которой линкер (Interprocedural optimization, Whole program optimization; Link‑time optimization) большинство функций “заинлайнил” – это очень упрощает чтение.


    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”) – в этом случае лучше всего просто обновить страницу (Ctrl+R), либо открыть GIF в новой вкладке. (если знаете способ лучше, то прошу написать в ЛС или в комментарии; возможно, есть какой‑нибудь <oembed>?)


    Анимация: бинаризация

    #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 + сказать про то, что для статей я переписывал исходники (менял название переменных), и чтобы легче было ориентироваться – указать какие старые исходники соответствуют каким коммитам/тегам в репозитории


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


    • OMNetProjectLLTD lltdapp + sim – в то время LLTR не имел своего названия, и я его называл просто “LLTD” (“R” – это “D”, у которой выросли ножки/ветки/корни) [примерно соответствует последнему коммиту из “Часть 1”, т.е. ветке article_1 и тегу a1_v0.30.0 git] {по датам в архиве можно посмотреть, когда что делал}
    • OMNetProject (before v0.9) lltdapp – небольшие правки (“LLTDClient.cc”: исправил опечатку, и перешел на использование DISCARD‑порта для “разогрева” ARP) [также примерно соответствует ветке article_1] {добавил в архив директорию “for diff (LLTR)” – сравнив (diff) ее содержимое с содержимым родительской директории, можно увидеть, как были переименованы переменные}
    • OMNetProject (v0.9) lltdapp – изменена логика остановки подсчета количества принятых пакетов (“LLTDClient.cc”: “trafCount[stepN]++”): добавлено ограничение по времени (см. “timeCalcEnd” и “timeoutCalc”), что хорошо отразилось на статистике (“stat.txt”: увеличился контраст) [Часть 3] {за кадром остается “как я понял, что нужно сделать именно это”, т.е. что нужно увидеть, чтобы прийти к такому решению}
    • Timers (QPC) – самое полезное в нем – это ссылки (в “Timers.cpp”; в частности на “The Windows Timestamp Project: Adjustment of System Time (NTP)”) [Часть 6] {по хронологии это должно быть здесь, после первой реализацией на Golang, но я решил все это перенести в “Часть 6”}
    • OMNetProject (v0.9.1) lltdapp – несколько изменений, основное из них: добавлена синхронизация времени (“LLTDClient.cc”: “sntpTimeOffset” и “sntpLatency” – эти значения пока не используются, но пригодятся в будущем) [Часть 3]
    • “fixed event time” ответвление – предрассчитал время наступления каждого события:
    • OMNetProject (v0.9.3) lltdapp – v0.9.1 + доделка синхронизации времени, и использование ее + улучшения из v0.9.2ft [Часть 3]
    • Get sequence (math induction) – получение формул для новой последовательности сканирования сети: unicast_src_hosti+1 = unicast_dst_hosti, т.е. хост, который сейчас принимает трафик (unicast dst), станет хостом, испускающим трафик (unicast src) [Часть 4] {одно из преимуществ этой последовательности можно увидеть, сравнив места возникновения “заторов” (наполнение буфера в свитчах) в двух рядом стоящих итерациях – теперь “затор” не будет возникать два раза подряд в одном и том же месте, что благоприятно скажется на: “самочувствии сети” (средней задержке прохождения пакета), и, соответственно, на качество собираемой статистики}
    • OMNetProject (v0.9.4) lltdapp – в основном: использование новой последовательности сканирования сети, и несколько “хаков для ООП” [Часть 5]
    • OMNetProject (vFinal) lltdapp – рефакторинг [Часть 5]
    • LLTD-Process (vFinal) – адаптация под новую последовательность сканирования сети [Часть 5]
    • GoLLTD – старая реализация на Go (“LLTD/old/main.old.go”) + новая реализация + описание подготовки окружения для эксперимента (“LLTD/Prepare test environment.txt”) + промежуточные инструменты, последовательность просмотра: “Timers/”, “SNTP/”, “LLTD/flood/broadcast.txt”, “LLTD/Prepare test environment.txt”, “LLTD/flood/old/main.go”, “LLTD/flood/main.go”, “LLTD/” [Часть 6,7]


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


    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, перед использованием, нужно сохранить в ней же.



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


    • 778px – максимальная ширина (780px – максимальное разрешение по горизонтали − 2px запасных)
      • 756px – при использовании изображения в спойлере первого уровня (758px – максимальное разрешение по горизонтали в спойлере − 2px запасных)
      • 738px – при использовании изображения в цитате первого уровня (740px – максимальное разрешение по горизонтали в цитате − 2px запасных)
    • Оптимизировать изображения в Image Catalyst v2.1 и v2.5, затем выбрать файлы наименьшего размера (используя “merge_min.bat”).
    • При вставке изображений в пост – сохранить имена картинок: habrastorage превращает все имена в “dwbmwbyvlzes80cep1hvcdb5iy.png” (пример) и не возвращает оригинальное имя в HTTP‑заголовке “Content-Disposition: inline;...”, поэтому, чтобы сохранить оригинальное имя, можно использовать хеш (якорь): “dwbmwbyvlzes80cep1hvcdb5iy.png#real-name.png”. Все изображения будут загружаться так же, как и прежде – браузер не отправляет хеш на сервер (сервер не заметит разницы). Единственная проблема может возникнуть с SVG – для них хеш может указывать на символ (спрайт), либо на кадр в анимации, либо …
    • Пометить изображения якорем (id, name). В качестве названия якоря использовать имя файла. (якоря на изображениях в спойлерах бесполезны – они не будут работать пока содержимое спойлера скрыто, но все же сделать якоря и для них, в частности – текст спойлера может иметь ссылку на изображение)
    • Если ширина изображения оказалась все же больше максимальной ширины, то сделать изображение ссылкой на него же (чтобы при клике открылось не масштабированное изображение).
    • Для всех изображений‑архивов (un[7z]me), после заливки на habrastorage – проверить, что с ними сделал CloudFlare Polish.


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


    Текст и git:


    • Пометить все ссылки на git tag значком git  и добавить якорь “git-tag-‹версия›” к значку.
    • Для каждой части создавать в git свою ветку, указывающую на последний коммит/тэг части, и давать названия “article_#”. (в основном это нужно для репозитория LLTR Simulation Model)
    • Проверить (поиск по “http”), что все ссылки (в статье и в исходниках) есть в web.archive.org, и на sohabr.net:
      var res=str.match(/http[^#)\s]*/gm);
      var res_l=res.length;
      for(var i=0;i<res_l;i++) console.log(res[i]);
      var archive = res.filter(function(a){return a.search(/(omnetpp.org\/doc\/omnetpp\/manual\/#|wikipedia|\/github.com\/)/)==-1;});
      • Перед публикацией опять проверить все ссылки, и неработающие заменить на web.archive.org или на sohabr.net .
      • Не заменять ссылки на habrahabr.ru ссылками на habr.com, т.к. их нет в web.archive.org (либо они уже есть, но не получится посмотреть всю историю изменений целиком).
    • Проверить, что у всех ссылок на Wikipedia есть “?stable=1”.
    • Заменить старые якоря (хеши) в ссылках MediaWiki (“#.D0.AD.D0.B2.D1.80.D0.B8.D1.81…”; поиск по “wikipedia”, и по “#.D0”) на новые (“#Эврис…”).
    • Cделать бекап статьи (со всеми версиями и внешними ресурсами) + бекап Git.
    • [начиная с “Части 2”] Для каждой ссылки на радел в другой части (“LLTR Часть #::”), добавить “title” (с названием части).
    • Добавить к каждому заголовку якорь (id, name), и добавить перед заголовком значок (например, серый “#”) с ссылкой на этот якорь (дополнительно можно добавить title “Ссылка на раздел”).
      • sohabr.net заменяет `id` у заголовков (пример), использовать `<a name=""></a>`?
      • Можно было добавить “Unicode Link Symbol” (U+1F517; “&#128279;”) после заголовка, но не все браузеры его отобразят (Chrome отобразит, если в системе присутствует хотя бы один шрифт из заданного семейства, включающий этот символ), т.к. он будет отсутствовать в основном шрифте.
    • Начинать и заканчивать спойлер горизонтальными линиями (<hr />) – для тех, кто не применил UserCSS (а в UserCSS убирать эти линии).
    • Для абзацев использовать верстку `<p><br />текст</p>`, чтобы в UserCSS можно было легко убрать `<br />`, и установить `margin` для `<p>` (легко не получилось).
      • Похоже `<p>` будет использоваться, только если включить Markdown… (жалко, что `<p>` используется только в info разделе сайта, но не в основном его содержимом, я бы хотел изменить интервал между абзацами в UserCSS, очень хотел бы).
    • При вставке картинок указать height картинки (чтобы при загрузке страницы и картинок текст не прыгал верх‑вниз), если изображение обтекается текстом, то указать также и width.
    • В смайликах использовать “Full width brackets” (чтобы можно было их быстро найти; хотел использовать декоративные скобки, но они слишком смещены по вертикали относительно двоеточия).
    • Добавить к статье тег “какие еще добавить теги?”
      • Добавить названия хабов к тегам (на случай, если хабы удалят, связанность сохранится по тегам). Например, однажды мне нужно было найти (чтобы поделится ссылками) группу статей, они все были в корпоративном блоге одной компании. Компания, которая завела корпоративный блог – не стала продлять его. Все статьи сохранились, но потерялась связанность (мне пришлось долго искать нужные статьи). Если бы один из тегов был названием блога/компании, то связанность сохранилась бы. Хаб могут переименовать/объединить/удалить, а теги – вечны.
      • Добавить тег “Хакерская ценность”.
    • Прочесть habrahabr.ru/info/help/posts/ (теги, old теги)
      если ваша публикация является обучающей, уроком или how‑to – отметьте чекбокс «Обучающий материал» (tutorial), это поможет визуально выделить ее среди прочих;
    • Прочесть памятку по базовой верстке статьи.


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


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




    DOI: 10.5281/zenodo.1407060
    Поделиться публикацией

    Комментарии 15

      +5
      Ваша серия из 3 статей — сокровище для инженеров. Честно скажу — многие вещи я услышал вообще впервые в жизни и вообще как будто читаю про будущее. Отдельное спасибо — за вёрстку, это просто космос. Разослал бывшим и нынешним коллегам ссылку, будем кое-что тащить в практику.
        +1
        Рад, что статьи пригодятся.
        Значит не зря в свое время пошел именно по этому пути:
        В 2015 году (когда я впервые рассказал основную идею LLTR) мне предложили сделать свою Ph.D-диссертацию именно на эту тему. Но видя, что получается в итоге у других, защитивших свою диссертацию (все 1в1 как описано в этой заметке), решил сделать что-то лучшее (более полезное для других), чем диссертация.
        Жалко, что не получилось описать больше (создание одной только анимации бинаризации) заняло больше месяца...).

        В оставшееся время я хочу еще:

        • добавить DOI — для тех, кто захочет сослаться на статьи, используя DOI;
        • загрузить на GitHub Pages «Часть 0» — для тех, кому понравилось оформление остальных частей на GitHub Pages.

        И поделится некоторыми другими вещами, например, из области "Анализ сигналов"+"Учебный процесс в IT": я как-то сделал квест (рассказ/история, совмещенная с задачей — для того, чтобы «открыть» следующую главу истории — нужно выполнить некоторые действия главного героя) для студентов (заочников). История происходит во «вселенной бондианы» (кстати, многие преподаватели не знают про такую возможность, возможно это даже к лучшему — некоторые могут испортить изначальный образ, созданный автором).
        Вот начало истории, вот info о квесте/курсе, а вот файл, который понадобится для прохождения квеста (он будет генерировать ссылки на «следующие главы») — перед использованием его нужно скопировать в свой Google Drive.

        Либо из области "настрой под себя": некоторым людям нравится вид папок/файлов как в Explorer в Windows XP (и старше):

        • размер иконок 32x32;
        • имена расположены под иконками
        • работает автоматическое выравнивание (тот режим, в котором можно вручную менять местами файлы/папки).

        На форумах есть хаки, которые это делают, но они нестабильны, и увеличивают нагрузку на CPU. Поэтому я поступил проще — сделал патчи (x64dbg помог мне в этот раз).

        Есть и другие патчи, например, один патч восстанавливает в системе четкий «однопиксельный» рендер шрифтов (небольшого размера), для тех программ, которые используют DirectWrite (когда из Chromium удалили рендеринг шрифтов через GDI, оставив только DirectWrite — было много недовольных «размытым текстом»), а т.к. в Windows 10 многие системные утилиты используют именно DirectWrite, то система становится «четкой» :-)
        (на самом деле, т.к. в основном в Win10 используется отнюдь не маленький размер шрифта, то эффект мало заметен).

        Либо "ADSL (14 Mbps) vs GPON (75 Mbps)" (часть 1), но в них было сделано много предположений, а я так и не смог установить точную причину падения скорости (дропов и ретрансмитов).

        Note: мне очень нравился ADSL — со свежими конденсаторами и «подобранными/вычисленными параметрами» я получал 21-23 Mbps (предел скорости входящего потока 24 Mbps) ADSL2+ Annex M (восходящий был 2.1-2.4-2.7 Mbps).

        Либо из области фотоники: «всегда хотел сделать для себя процессор».

        Либо (см. пасхалки).
          +1
          В оставшееся время я хочу еще:

          • добавить DOI — для тех, кто захочет сослаться на статьи, используя DOI;
          • загрузить на GitHub Pages «Часть 0» — для тех, кому понравилось оформление остальных частей на GitHub Pages.
          Сделано.
        +2

        Скажите пожалуйста, а нельзя ли для этих целей (передача данных) использовать multicast? Кажется, что для минимизации трафика самое оно.
        Извиняюсь, если в статьях был ответ на это предложение.

          +2
          Ответ кроется в названии[и первом абзаце] части 0: "LLTR Часть 0: Автоматическое определение топологии сети и неуправляемые коммутаторы. Миссия невыполнима?".
          А неуправляемые комутаторы «превратят» multicast в broadcast.

          К тому же RingSync использует TCP (в том числе и для контроля скорости отправки данных).
          А если использовать multicast (в сети с управляемыми коммутаторами или маршрутизаторами), то придется «вручную» подстраиваться под скорость самого медленного пира.

          P.S. а в остальном — да, если получится использовать в сети multicast, и он будет хорошо работать, то лучше использовать именно multicast.
            0

            Спасибо за развернутый ответ

              0
              На самом деле multicast не такой простой, как кажется на первый взгляд. Чтобы осознать все «нюансы» нужно хоть раз его настроить. Либо прочитать про «проблемы», с которыми сталкиваются при настройке IPTV или радио (в мире основной процент multicast трафика — это IPTV или радио).

              Причем, для IPTV/радио, в плане передачи данных, все просто — используется UDP, т.к. потеря пакетов для этих данных не так страшна.
              И здесь возникает еще один вопрос: если мы передаем клиентам файл (нужно, чтобы каждый клиент получил полный файл), но в процессе передачи некоторые клиенты не получили часть файла (пакеты отбросились — не дошли до клиентов), то что делать в этом случае?
              Решение не так просто, как «клиенты подключаются к серверу, и скачивают (unicast, TCP) недостающие части». А если потерялась (не дошла до клиентов) большая часть файла? Запускать еще одно multicast вещание именно для этих клиентов, но с пониженной скоростью передачи данных? Либо…

              Как-то (давно) я писал работу "решение проблемы 'первого часа' в p2p (bittorrent)".

              Слайды из нее
              (два черных овала с белой обводкой — это сети двух разных «провайдеров»)







              (на примере распространения большого обновления для операционной системы)



              Часть презентации (с анимацией, которую нормально можно увидеть только в просмотрщике от MS :(

              Ссылки «в тему»

                +1

                Вопрос передачи через multucast udp частично решен в uftp, кроме ручного указания скости.
                А так все верно, нюансов масса. Но и простора для творчества.


                Например, первичная передача через multicast, затем передача потерянных данных по принципу ringsync, или, например, частичная синхронизация в рамках одного свитча, затем запрос остальных частей в источнике.

                  +1
                  Хорошо начинать знакомство с передачей файлов через мультикаст по ссылке на этот RFC:
                  tools.ietf.org/html/rfc6968
                    0
                    И заодно (в дополнении к References):




                    Но, как я уже писал, в сети, в которой multicast «превращается» в broadcast — это все перестает иметь смысл :(
                      0
                      КМК, сеть на неуправляемых коммутаторах — это не индустриальное решение.
                      Решать индустриальные проблемы с помощью неиндустриальных решений никто никому запретить, конечно же, не может.

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

                        (все это напоминает фрагмент из первого "Железного человека" — заперли в «катакомбы», под рукой только металлолом, и нужно сделать...)

                        Намек на место, где это происходило
                        Порой решать индустриальные проблемы в некоторых государственных университетах весьма затруднительно.

                        Спасибо за комментарии.
                        +1
                        Нашел свою старую заметку "интересных протоколов, в которых используется multicast":
                        • Nack-Oriented Reliable Multicast (NORM) Protocol (RFC 5740; включен в RFC 6968)
                        • Multicast Dissemination Protocol (MDP)
                        • Optimized Link State Routing (NRL-OLSR)
                        • Neighborhood Discovery Protocol (NRL-NHDP)
                        • Simplified Multicast Forwarding (NRL-SMF) for MANETs
                        • OSPF MANET Designated Routers
                      +1
                      Как раз для рассылки файла мультикастом с защитой от потерь выгодно применить фонтанное кодирование. Существует ряд RFC (RFC3453, RFC5053), предлагающих стандарты для подобных применений фонтанных кодов.

                      Суть самого фонтанного кодирования состоит в том, что из исходного набора данных порождается неограниченное количество блоков. Принимающая сторона, получив достаточное количество полезных блоков, может с высокой степенью вероятности восстановить полное сообщение. У современных алгоритмов крайне низкая избыточность передачи — порядка нескольких лишних блоков (по сравнению с линейным разбиением на блоки) дают вероятность получения данных >99.99%.

                      Пользуясь такими алгоритмами, передачу можно просто не прекращать никогда — у неё нет начала и конца.

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

            Самое читаемое