# LLTR Part 2: Algorithm for determining the network topology from the collected statistics

In the previous parts ...

Q: What do we have?
A: Statistics collected from hosts.

Q: What do we want to get?
A: Network topology! More precisely, you need to build the correct chain of peers (hosts) for RingSync .

We have to come up with an algorithm that first turns the statistics into a network topology, and then into a chain of peers. While the algorithm looks like this:

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

If you liked to read “Part 1” on GitHub Pages , then here is the link to this part in GitHub Pages.

Warning : The same artifacts of the Habr-parser will be found below, which I warned about in “Part 1” .

Note :–-[*магия*]--> I will use “–-[???]-->”instead of“”.

The collected statistics show us on which hosts the speed of receiving broadcast traffic fell. For example, look at the result of zero iteration in the “N2_2” network (“ Network” from the previous article “LLTR Part 1”):

{300,164,164},

Here 2 host states are clearly visible:

• normal speed (“value 300”) - no reaction ;
• speed dropped (value " 164") - there is a reaction .

What am I getting at? By binarization! If we encode the absence of a reaction as 0 , and the presence of a reaction as 1 , then we can put all the reactions of the hosts, of a single iteration, into one variable ( 32 - 512 bit [ AVX ‑ 512 ]). In addition to saving memory (and space occupied in the caches), this will increase the processing speed — all instructions from the hosts of a specific iteration ( SIMD ) will be processed at once in a single instruction .

Note : because using LLTR Basic for a large number of hosts is quite expensive ( see the beginning of the section “LLTR Part 0 :: LLTR Advanced” ), then everything fits into 64 bit x86‑64 registers.

Note : In the text of the link to a section located in another article (another part), I will add the part number in the format: “ LLTR Part # :: ‹ section name › ”. And in the “title” link I will write the name of the part, for example, for “LLTR Part 0 ::” will pop up “Automatic detection of network topology and unmanaged switches. Mission Impossible?".

Let's take the same example of zero iteration, and see how it will look after binarization:

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

Very compact, but I would like to see the “ 1” ( presence of reaction ) immediately apparent when viewing a list of all iterations. Now ““ 1”does not stand out much against the background“ 0“(fake data, for visual example ):

0101011010110
1100010110010
0101101010111
0100010110100

To select " 1", I will enter the notation:

• 1” Means 1 - there is a reaction ;
• .” Means 0 - no reaction .

Let's look again at the “fake data”:

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

So much better ( IMHO ).

Algorithm, at the moment, looks like this:

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

Leave the details of the binarization for the end of the article, and concentrate on the rest of the algorithm.

It is easiest to create an algorithm based on specific input / input data (special cases, boundary conditions; tests are in terms of TDD ). In our case, the source data depends on the network topology, so you need to come up with a network that is both small at the same time and at the same time contains different switch connection schemes ( star , serial connection ). It may be possible to include something special in it ... In general, the imagination drew such a network (the element designations are similar to the designations used at the end of the “ LLTR Part 0 :: Topology:“ serial connection of switches ” ”):

Note : looking at this network, I recall the question “is it possible in this topology to conduct a full scan if to one of the switches ...” (closer to the end of the section “ LLTR Part 0 :: Topology:“ serial connection of switches ” ”), and you notice that no host is directly connected to one of the switches. And in this there are no problems, because 3 more switches are connected to this switch (I counted only switches connected “from below”, without taking into account that it is connected to another switch “from above”), each of which has hosts.

However, in this diagram there are a few unnecessary (distracting) details. I'm going to clean it up by removing:

• broadcast host (it is not in the input / statistics);
• ports connecting the switches to each other.

Here you can immediately see the “no hosts” switch. In addition, all the switches I arranged in such a way that the hosts in them do not overlap each other vertically. It will be useful if in the future I want to show the “reaction of hosts” not as a text entry “ .....1......”, but as a diagram (there is only one host on one vertical):

And now imagine the statistics that we will receive on the completion of all iterations of scanning this network. There are 12 hosts in the network (excluding the host broadcast), therefore, we will have data on 132 iterations. However, not all results of the iterations will be useful to us, for example, they will be useless:

• single reactions (as in the example above - “ .....1......”; LLTR Part 0 :: I wonder what are the options for the first iteration?> Option 4: “unicast in sw” );
• duplicates (repetitive results), for example, “ .....111....” will occur approximately 15 times ( 3 × (12 - 3– (2 + 2)) ; “approximately”, since I did not create a model of this network in OMNeT ++ , and did not launch simulation, I conducted only a thought experiment, in which I could not take into account some of the details).

After cleaning, of all 132 results of the iterations, only 5 will remain (host reactions):

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

Note : for clarity, I arranged the iterations in order from a larger “1” to a smaller one.

The algorithm began to look like this:

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

reset point

I reflected on the inclusion of all this in the spoiler, but in the end I realized that this is an important part of the narrative, which it is better not to skip when reading.

[reset point] In the remaining 5 iteration results, the first two attract attention: the first includes the second, and the second includes the remaining 3 bottom. Here we recall the “shadow” from the section “ LLTR Part 0 :: Topology:“ serial connection of switches ” ”. In the same section, at the end of each iteration, we formed (or did not form) new clusters based on the data just received. Now you need to do the same.

But how do we form new clusters? In essence, all (not single) reactions of the 1current iteration hosts were “new cluster”, we only needed to find intersections (“∩”; not empty “∅”) with existing clusters to remove (“∖”) from a larger cluster hosts in a smaller cluster.

However, in our actions there was a condition / branch (if): you need to determine which of the clusters is larger, and only then perform a simple operation (A ∖ B) - from the larger cluster (A) subtract the smaller one (B). Representing the torment of a CPU with a long pipeline, caused by the need to reset the pipeline with incorrect branch prediction (if there is a “branch prediction unit” at all), I almost decided to use it, тернарный оператор “?: but at that moment ...

I stood on the toilet and hung up the clock. Suddenly I slipped, hit my head on the sink, and when I woke up there was a vision, a picture in my brain, a vision of this — a stream drive stream divider ( Back to the Future ) :

// Flux Divider
c=a^b;
aa=a&c;
bb=b&c;
cc=a&b;

And at once let's look at his work on the example of overlapping clusters (more precisely, one set (cluster) is strictly included “ другое ” in another set):

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

Non-intersecting clusters:

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

Turns out that:

• to " aa" get the elements that are unique to ' a';
• in “ bb” - unique to “ b”;
• in " cc" - common to " a" and " b".

Another example with intersecting clusters (“impossible”, but a clear example):

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

Note : this response option (hosts reaction) is absent in the original data.

The same way you can get rid of duplicates :

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

But, a little later ...

The head stops hurting after hitting the sink, the mind clears up, and obvious problems emerge ...

We have 2 variables at the entrance (results of iterations / reactions of the hosts / clusters / sets / ...), but at the output they are already 3, and at least one of them will be empty (“∅”). If you do not immediately get rid of “∅”, then they will have to be included in the processing later. Therefore, it is better to get rid of "∅" immediately. But how to do that? Use condition / branch! ... In general, I went back to where I started. In addition, if we do everything as described above, plus get rid of “∅”, then we will end up with:

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

It:

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

It's time to ask the question: “How can we get a network topology out of this?”. Now this data can “tell” about which cluster a particular host belongs to (i.e., to which switch the host is connected), but this data now completely lacks information on switches topology (i.e., how are the switches between each other) - we lost this information during data conversion. Besides, to which cluster (switch) do the 2 far right hosts belong? If each row is treated as a separate cluster (or as an indication of which hosts are connected to a particular switch), it turns out that these 2 outermost hosts are not connected anywhere! Moreover, we have 6 switches in the network, and there are 4 lines left, where are the other 2 lines? We erased one (as stated above), and the other should have been “2 far to the right of the host”.

[ goto reset point ] Further to develop this idea is useless. Dead-end branch (git branch). We'll have to roll back to the “reset point” label, forgetting everything that happened after it, but leaving this branch for history.

Now, in order not to fall into another “dead branch”, you need to decide on the final structure (representation) of the network topology in memory. That is, with what we want to get by the time “network topology”:

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

First , all hosts must be present:

<strong>..........11</strong>  <--
1111111111..
11111111....
..111.......
.....111....
11..........

Secondly , parents should be indicated (the parent cluster for each cluster; at the moment: the parent child ; on a network diagram, the parents of children I possessed above) (left cluster numbers added):

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

Note : if you notice something strange here comparing the diagram of this network with this data, then you will like it from me.

Spoiler, it is better not to open to read the entire list

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

Thirdly , there should be one “root” parent linking separate trees (i.e. forest ) into one tree:

-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

Fourth , it would be nice to have lists of children for each parent:

-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

And finally , it is now possible to exclude children from parents:

-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

Now each line describes one cluster, i.e. points to hosts connected to the same switch. However, wait, there are 6 switches in our network, and there are 7 clusters! It’s time, finally, to read the text from the spoiler above “ Spoiler, it’s better not to open it before reading the entire list, ” and correct the situation:

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

These data are just the “network topology” - they describe the switch tree, and using it you can identify all the hosts connected to a particular switch.

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

It remains to understand how to bring the data to this form. In fact, everything that we did (firstly, secondly, ...) can be converted into an algorithm:

1. “First” (after making corrections from the spoiler becomes similar to the action “third”) - add the “root” cluster111111111111” ( universe ), including (hosts of all trees in the forest ∪ hosts that are on the same switch with the broadcast host) i.e. it includes all the hosts on the network;
2. “Secondly” - search for a parent for each cluster ;
3. “Fourth” - building a list of children for each parent ;
4. “And finally” - exclusion of children from their parents .

Now you can add these actions to the general algorithm (slightly changed the view):

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

Alternative view

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

Let's see what happens if we apply this algorithm to another network. I would like to take the network “ ” and its simulation results (statistics) from the section “ LLTR Part 1 :: More networks with different topologies, add new networks ”.Network_serial

Note : Why did I choose this network? It is quite large, and there are flaws in the data collected from it (see the end of the “Results of the simulation” spoiler for this network).

Go!

Binarization

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

.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.

Purification of single reactions

.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.  -->

Clearing duplicates (we get “clusters / forest”):

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

Additionally, for convenience , sort by decreasing the number of " 1":

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

Note : It may be worthwhile to include sorting in the algorithm. What do you think?

Adding a “root” cluster (we get “clusters / tree”):

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

It includes hosts of 2 trees (left “ .111111..” and right “ .......11” part of the network) and 1 host (“ 1........” located on the same switch with the broadcast host).

Parent search for each cluster:

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

Note : This is exactly where the negative impact of data deficiencies manifested itself - the 4th cluster became the parent for the 5th! In general, any cluster can become the parent of the 5th cluster, since it is empty (∅).

Building a list of children for each parent:

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

Exclusion of children from parents:

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

In this step, we had to get a “network topology”. And we got it. If we are only interested in the location of the hosts, then this “network topology” suits us perfectly. However, one more switch appeared in our network, in which there are 0 hosts!

To fix everything, it will be enough after one of the first steps to eliminate these “data flaws”. This can be done immediately after “binarization”:

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

We delete empty sets (∅; " ........."), but why remove universes (⦱; " 111111111")? The answer will become obvious when we begin to implement the “binarization” phase. Different versions of the implementation of "binarization" can on the same data (data with the described defect) issue both " ........." and " 111111111". And, because to get in the correct input data “ 111111111” is as impossible as it is to get “ .........”, then we can delete all the “ 111111111” (besides, they do not carry any information, except for the fact that there are “flaws” in the data).

If we apply this (amended, corrected) algorithm to the same network (“ ”), then the “network topology” will look like this: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 : Beautiful, it turned out the diagonal. It resembles a unit matrix , but it cannot be obtained in its pure form. It can be done to have 2 hosts in each cluster (to do this, add one host to “switch0”), but we cannot get only 1 host in each cluster ( there will always be at least 2 hosts in the outermost clusters):

Examples of not “single matrix”

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

We were able to finish the algorithm to obtain the correct “network topology”. It remains to build a “chain of peers” from the “network topology”. In the article about RingSync, I already described how to do this (deep tree traversal: Pre ‑ order ). As a result, the “chain of peers” should turn out like this:

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

Note : in the first line (left, separated column) added seed, also broadcast host.

It seems that nothing has changed compared to the order of clusters in the “network topology” (all the same diagonal), and this is true for this network (“ ”). Below, I will do the same with our previous network (which I never gave the name), maybe it will be visible changes. In the meantime, I will show the traffic path for the constructed chain:Network_serial

As promised, I do the same for the “previous network” (“chain of peers”):

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

There are practically no changes (compared to the location of clusters in the “network topology”). The only thing that has changed is cluster 2, since it was empty (∅). Does this mean that there is no need to “crawl the tree to the depth”, and it suffices to take the clusters from the “network topology” (in the same order in which they will be at that moment) and delete all empty () clusters? However, this is not the case: firstly, so that the clusters are arranged in such a “convenient” order, I used sorting, but it has not yet been included in the algorithm (it would be necessary to enable, but it is still early）; secondly, not For all networks, this trick will work (try to come up with such a network without looking at the spoiler).

With a simple transformation, the “previous network” network turns into a network, which requires a “tree-by-depth walkthrough”

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

Okay, back to the built “chain of peers”, and look at the traffic flow ...

Note : There should have been a picture here, but the image of the traffic flow on such a small diagram began to resemble spaghetti. I do not recommend looking at this.

One attempt to portray the path

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

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

..........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

At that moment, I wanted to look again at the traffic path in “ ” ...Network_serial

Now I noticed that in what sequence the traffic passes through the switches:

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

... and I really did not like the "hook" through " switch0 <- switch1 <- switch2". I wanted to get the following sequence at the output of the algorithm:

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

Traffic path for her:

The path has become shorter, and, most importantly, the load on the network has decreased!

Note : but I'm still more attracted by the decrease in the number of intermediate network nodes, i.e. “The path has become shorter”.

Note : it is precisely “the number of intermediate network nodes” that is meant, and not “the total channel length” (the length of the network cable; the length of the signal path at the physical level - L0 ) - it could and would increase.

To achieve this, it is enough to add a small heuristic to the “walk into the depths of the tree”.

Note : I initially created this heuristic for another purpose, but it turned out to be a very useful side effect - reducing the number of intermediate network nodes.

Heuristics (rule) : when “entering the subtree” ( LLTR Part 0 :: Topology: “switch star” ), give priority to nodes with less nesting:

1. host - host;
2. node - one switch;
3. node - two switches (connected in series);
4. node - many switches (connected as you like) - the more, the lower the priority.

Note : if in the text of this list we replace “ node - ” with “ switch port to which it is connected ”, then perhaps it will become clearer.

Note : The initial purpose of these rules is to first send traffic through the nearest hosts (the hosts to which there are the least intermediate devices). Less intermediate devices - less likelihood of an error (during data transfer) at the very beginning of the path. Compare the two traffic situations leading to a temporary traffic jam (one lane): a traffic jam occurred at the beginning of the road (the buffer zone is practically absent); the congestion occurred near the end of the road (the size of the buffer zone is sufficient to mitigate the effects of the congestion).

Update the algorithm:

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

And the updated “chain of peers” for the “network” will look like this:Network_serial

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

That fully corresponds to the modified “traffic path”, which is shown above.

But the update of the algorithm had no effect on the “old network”. The “chain of feasts” remained the same:

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

Why hasn't changed? Updating the algorithm affects the sequence of switches, however, in this network, the sequence was already optimal (updating the algorithm could neither improve nor degrade it):

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

Note : the switch number “s#” corresponds to the cluster number in the “network topology” for this network (see above).

## # TL; DR

The algorithm for determining the network topology and building a chain of peers according to the collected statistics:

1. Binarization (~~ k ‑ medoids ~~) + purification from emptiness (∅), and from universums (⦱) + purification from single reactions:
1. middle between andaminamax
2. divided into 2 parts in the middle
1. + emptying void (∅), and universes (()
3. find the median of the left and right side of the array:
4. find the middle between (medLow) and (medHi)amedLamedR
5. divided into 2 parts by the new middle, and immediately presented in binary form
6. + purification from single reactions
2. Deduplication + adding a “root” cluster:
2. + sort by bitCount(from max to min)
3. remove duplicates
3. Parent search for each cluster:
1. starting with the min element, search from below (min) up (max) that (first available) element, which includes the current one;
search with a check or a simpler check:bitCount(ai)==bitCount(ai|amin)ai==ai|amin
2. perform the previous step recursively, fix a chain of elements along the way (recursion path) - add the identifier of the next element to the current element
3. find the next min element (not participating in the chain) and repeat the recursion
4. Building a list (card) of children for each parent:
1. create a reverse chain (from “parents” to “descendants”)
5. Exclusion of children from parents:
1. when all elements are in the “chain”, then starting with the max element, make or | = a i over its descendants, and apply (or “ ” - with correct data, the result will match)amax&=~or
amax^=or
2. repeat recursively with descendants of descendants
(or just move from to , because it is a tree, and its vertices are sorted in an array)amaxamin
6. Traversing a tree in depth, taking into account priorities / weights:
1. build route for traffic (ringsync)

Note : approximately in this form, I wrote down the algorithm , before its implementation in the code.

It is a little about code structure

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

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

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

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

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

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

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

НЛОприлетелоиоставилоэтотпробелздесь? 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; Didnt read; Visualize, plz.

Note : Below you will see an animation of the operation of each of the blocks, and an animation of data transfer between the blocks (as in the GIF “TensorsFlowing” from the spoiler “A little about the code structure”). When creating these GIFs, I was inspired by the already mentioned “TensorsFlowing” and GIF “ Loop over python list animation ”. Also, in these GIFs I tried to transfer images that “float in the brain” while reading / creating these lines of code. Naturally, due to certain restrictions the transfer cannot be carried out 1: 1, nevertheless “welcome to my brain”.

### # Block binarization

Note : When creating a GIF, I tried to place the code next to the animation in different ways (as in “Loop over python list animation”), but not one of the options looked good. Therefore, associated with the animation code, I put in the spoilers under the animation. The spoiler number corresponds to the stage number in the animation (numbers appear on the right ；）

Note : It is better to look at the first (and second) iteration without looking at the spoilers (simultaneous monitoring of the animation and reading of the source can be confusing). In particular, for this reason I put a frame from the animation of a specific stage in the spoilers.

Note : Not all browsers will start playing GIF from the beginning (at the beginning there is an inscription “Scroll Down”) - in this case it is best to simply refresh the page (Ctrl + R), or open GIF in a new tab. ( if you know a better way, then please write in the LAN or in the comments ; perhaps there is some <oembed>? )

#one

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;
}

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

# 2

int lo=0;
structCnN{
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: эти фрагменты кода (в спойлерах) немного отличаются от кода в репозитории.

# 3

int averageMed;{
CnN *iFillLo=&iFill[0];
CnN *iFillHi=&iFill[lo];
constint 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;
}

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

#four

for(unsignedint j=0;j<numHosts;j++) bitCluster[i]|=( (countFill[i][j]<averageMed)?1:0 )<<j;

#five

bitCluster[i] = bitCluster[i]^(1<<((i/(numHosts-1))+(i%(numHosts-1)+1))%numHosts) ? bitCluster[i]:0;

Note : GIF sources are in the repository . Before viewing them, I recommend reading ReadMe (this may save your nerve cells; and if anyone knows a more suitable tool for visual creation of such an animation, please write about it in the comments ).

Input data

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

## # Protocol forgiveness with life

The writing of the first 3 parts went on for 1.92 years, and I am not sure that in 1.6 - 2 months I will have time to finish the remaining parts. Given that the events described in the first 3 ‑ parts, they lasted (in real life) a little less than a month (for which I also managed to write the first implementation on Go - it took 2 days, and an experiment on a real network took 2 - 4 days) . Then there was a break (4 months), and another 2.5 months of work on the LLTR.

In the spoiler are sketches of the remaining parts + TODO's + links to the sources.

Perhaps I can add something from this, so I ask you not to look under the spoiler for at least 2 months.

Note : at the end you understand how much knowledge / ideas you have not described, and they will simply die with you ...

Spoiler

Прошло ли 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: Математика

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

∀ 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 ] {по датам в архиве можно посмотреть, когда что делал}
• 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: пока я не запишу идею – я не могу заснуть, а самый быстрый (в это время) способ сохранить идею – нарисовать на листочке.

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

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

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

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‑прозрачность
• [если есть Adobe Fireworks] (Ctrl+Shift+X) → PNG‑8 + alpha
• [иначе]
4. “дожать” изображения, используя Image Catalyst (я “параллельно” использовал 2 версии: 2.1 и 2.5, а затем оставлял файл минимального размера):
1. “закинуть” копию изображений в ImageCatalyst2.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 Catalyst2.5 ([1] Xtreme profile)
Tools\config.ini

[options]
;Number of streams. If value early 0, is used value ofparameter %NUMBER_OF_PROCESSORS%.
;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
chunks=true
[JPEG]
[GIF]

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" %%Ain (*) do (
set FileA=%%~fA
set FileB=!FileA:%~f1=%~f2!
set FileASize=%%~zA
for%%Zin ("!FileB!") doset 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
OnErrorResumeNext
boostStart2 "Rotate 90 and Swap W-H"
ForEach s In sr
s.GetSize w, h
s.Rotate -90
s.SetSizeEx s.CenterX, s.CenterY, w, h
Next s
boostFinish2
EndSub

+ boostStart2/boostFinish2:

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

PrivateSub boostStart2(ByVal unDo\$)
OnErrorResumeNext
ActiveDocument.BeginCommandGroup unDo
Optimization = True
EventsEnabled = FalseEndSubPrivateSub boostFinish2()
OnErrorResumeNext
EventsEnabled = True
Optimization = False
ActiveWindow.Refresh
ActiveDocument.EndCommandGroup
'RefreshEndSub

3. перед финальным экспортом добавить корректирующий положение и размер прямоугольник:
• залить его белым
• без абриса
• он должен:
• покрывать все пиксели изображения (причем его размеры [ширина, высота] должны быть четными числами)
• быть привязан к пиксельной сетке (к краю пикселя)
• перенести на задний план
4. экспортировать (с описанными выше настройками)
5. подправить XML (добиться соответствия по структуре с уже экспортированными файлами)
1. скопом (во всех файлах):
• заменить “DOCTYPE” и комментарий “Creator” на комментарий “96ppi” (именно таким должен быть ppi у документа в CorelDRAW перед импортом в него этого SVG)
• стереть “metadata”, “id” (у внешней группы)
• в атрибутах тега svg:
1. стереть “xmlns” и “xml:space
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" %%Ain (*.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
< ifdefined thrt >nul2>&1ping -n 1 -w 500127.255.255.255 & goto:waithreat
---
> ifdefined thrt >nul2>&1 timeout /t 1 /nobreak & goto:waithreat
203c203
< 1>nul2>&1ping -n 1 -w 500127.255.255.255
---
> 1>nul2>&1 timeout /t 1 /nobreak
237c237
< ifexist "%~1" (1>nul2>&1ping -n 1 -w 500127.255.255.255 & goto:waitflag)
---
> ifexist "%~1" (1>nul2>&1 timeout /t 1 /nobreak & goto:waitflag)
513c513
<      ifexist "%tmppath%\typelog.lck" (1>nul2>&1ping -n 1 -w 500127.255.255.255 & goto:savelog)
---
>      ifexist "%tmppath%\typelog.lck" (1>nul2>&1 timeout /t 1 /nobreak & goto:savelog)
534c534
< if "%jpeg%" equ "0" if "%png%" equ "0" 1>nulping -n 1 -w 500127.255.255.2552>nul & goto:finmessage
---
> if "%jpeg%" equ "0" if "%png%" equ "0" 1>nul timeout /t 1 /nobreak 2>nul & goto:finmessage
572c572
<      1>nulping -n 1 -w 500127.255.255.2552>nul
---
>      1>nul timeout /t 1 /nobreak 2>nul

V2.5 diff:

319,320c319
<      call:division float 1024100
<      call:echostd " In    - !float! КБ"
---
>      call:echostd " In    - !float! байт"
322d320
<      call:division change 1024100324,325c322
<      call:division float 1024100
<      call:echostd " Out   - !float! КБ (!change! КБ, %5%%%%%%)"
---
>      call:echostd " Out   - !float! байт (!change! байт, %5%%%%%%)"
362,363c359,360
< set /a "ww=%random%%%%1"
< 1>nul2>&1ping -n 1 -w %ww%127.255.255.255
---
> set /a "ww=%random%%%%1/1000"
> 1>nul2>&1 timeout /t %ww% /nobreak
707c704
< if%jpeg%equ0if%png%equ0if%gif%equ01>nul2>&1ping -n 1 -w 500127.255.255.255 & goto:finmessage
---
> if%jpeg%equ0if%png%equ0if%gif%equ01>nul2>&1 timeout /t 1 /nobreak & goto:finmessage
741d737
< call:division changePNG 1024100747d742
< call:division changeJPG 1024100753d747
< call:division changeGIF 1024100800c794
<      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 (для этой части).