Хабрахабр

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

Link Layer Topology Reveal logo

В предыдущих частях…

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

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

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

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

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

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 крайних справа хоста? Одну мы стерли (как гласит комментарий выше), а в другой как раз и должны были быть “2 крайних справа хоста”. Более того, в сети у нас 6 свитчей, а строк осталось 4, где же еще 2 строки?

Тупиковая ветвь (git branch).
[goto reset point] Дальше развивать эту идею бесполезно. Придется откатиться назад к метке “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
.........

111111..” и правая “.......
В него вошли хосты 2‑х деревьев (левая “. 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

Вообще, родителем 5‑го кластера может стать любой кластер, т.к.
Note: Вот здесь как раз и проявилось негативное влияние недочетов в данных – 4‑й кластер стал родителем для 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) большинство функций “заинлайнил” – это очень упрощает чтение.

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

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

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

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

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

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

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

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

(если знаете способ лучше, то прошу написать в ЛС или в комментарии; возможно, есть какой‑нибудь <oembed>?)
Note: Не во всех браузерах GIF начнет проигрываться с начала (в начале есть надпись “Scroll Down”) – в этом случае лучше всего просто обновить страницу (Ctrl+R), либо открыть GIF в новой вкладке.

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

#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

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

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

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

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

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

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

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

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

спойлер

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

Нет

Любопытно?

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

Да

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

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

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

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

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

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

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

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

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

Избавится от структур (массивов структур), и адаптировать реализацию используемых 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++ продолжение

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

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

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

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

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

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

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

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

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

Ссылки:

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

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

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

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

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

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

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

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

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

Что позволяет представить двоичную запись числа в виде звездочек и ящичков (границ/перегородок ящичков): “1” – Star, а “0” – Bar.
Пора переключится на 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 ).

Вот так, через “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#Перестановки_с_повторением

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

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

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

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

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

Ссылки:

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

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

Ссылки:

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

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

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

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

Для этого просто использовался файловый сервер {один из ПК; 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 трафика.

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

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

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

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

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

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

0b1 и INET v3.
TODO[x]: при вставке ссылок на исходники представить их в виде веток (дерева) + добавить комментарии, что в них было сделано + комментарий, про то, что это создавалось на старой версии OMNeT++ v5. 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?), сбор статистики в процессе,
и прикрутить отсечение лишних (симметричных) зондирований, если зондирование в одном направлении уже дало результат

9 – на client собирать статистику в текущей итерации не до прихода следующего синхросигнала, а до истечения времени (и прихода синхросигнала)
LLTD 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
либо сделать тестовую реализацию v0.

S.
P. нормально‑ступенчатое распределение. при рандомизации таймеров (в модели) использовать “нормальное распределение”.
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‑прозрачность
      • [если есть Adobe Fireworks] (Ctrl+Shift+X) → PNG‑8 + 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

        1 уже запущен.
        Note: если он выводит “Image Catalyst 2. 1” в “Image-Catalyst-2. Для выхода из приложения нажмите на Enter.”, хотя это не так, то переименуйте папку, в которой он находится (я переименовал “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

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

      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” всегда был меньше.

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

Image Catalyst.bat

1 diff: v2.

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

5 diff:
V2.

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; “🔗”) после заголовка, но не все браузеры его отобразят (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 (для этой части).

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть