LLTR Part 2: Algorithm for determining the network topology from the collected statistics
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
Warning : The same artifacts of the Habr-parser will be found below, which I warned about in
Note : further, instead of “ –-[**]--> ” I will use “ –-[???]--> ”.
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 , we can put all the reactions of the hosts, of a single iteration, into one variable (
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
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 record the name of the part, for example, for “LLTR Part 0 ::”, the “Automatic detection of network topology and unmanaged switches will pop up. 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, however, I would like the “ 1 ” ( presence of reaction ) to immediately catch my eye when viewing a list of all iterations. Now “ 1 ” does not stand out much against “ 0 ” (fake data, for visual example ):
0101011010110 1100010110010 0101101010111 0100010110100
To select " 1 ", I will enter the following 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. This 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 do not created a model of this network inOMNeT ++ , and did not run the simulation, I conducted only a mental 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 number “ 1 ” to a smaller one.
The algorithm began to look like this:
–-[]--> --[ ]--[ ]--[???]--> --[???]--> 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.
¬ ( Do not skip to the brain 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 “ 1 ” hosts of the current iteration were “new cluster”, we only needed to find intersections (“∩”; not empty “∅”) with existing clusters to remove (“∖”) from the larger Cluster hosts included 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 block” at all), I almost decided to use the “?: ” “?: , but at this 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 drivestream 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:
- elements unique to “
a” fall into “aa”; - 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 in the future. 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 , the parents must be indicated (parent cluster for each cluster; at the moment: parent child ; on the network diagram, I placed parents above children) (cluster numbers are added on the left):
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.
In essence (according to the diagram), the parent for cluster 1 is cluster 0, but then the condition “ parent ⊋ child ” is not fulfilled. Perhaps in “ First, ” we made a mistake, and instead of “ ..........11 ” it was worth adding “ 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 it is possible to 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:
- “First” (after making corrections from the spoiler becomes similar to the action “third”) - add the “root” cluster “
111111111111” ( 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; - “Secondly” - search for a parent for each cluster ;
- “Fourth” - building a list of children for each parent ;
- “And finally” - exclusion of children from their parents .
Now you can add these actions to the general algorithm (slightly changed the view):
● ● [] ► [ ] [ ] ► / [ "" ] ► / [ ] [ ] [ ] ► ● [???] ► ● ● ► [] ▬ ► [ ] [ ] ▬ / ► [ "" ] ▬ / ► [ ] [ ] [ ] ● ► [???] ● ●
Let's see what happens if we apply this algorithm to another network. I would like to take the network “ Network_ serial ” and its simulation results (statistics) from the section “ LLTR Part 1 :: More networks with different topologies, add new networks ”.
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!
Host Reactions:
.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. -->
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 one switch with 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 it is impossible to get in the correct input data “ 111111111 ” as it is impossible to get “ ......... ”, then we can delete all “ 111111111 ” (besides, they do not carry any information, except for that there are “flaws” in the data).
If we apply this (amended, corrected) algorithm to the same network (“ Network_ serial ”), then the “network topology” will look like this:
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, .. (∅). , “ ” , “ ” ( , ), (∅) ? , : ‑, “” , ( , ；）; ‑, ( ).
, “ ”, …
Note : , , . .
“ 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:: : “ ” ) :
- – ;
- – ;
- – ( );
- – ( ) – , .
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
:
- (~~ k‑medoids ~~) + (∅), (⦱) + :
a mina max- 2
- + (∅), (⦱)
- :
a medL(medLow)a medR(medHi)- 2 ,
- +
- + “” :
- + “”
- +
bitCount( max min)
- :
- min (min) (max) ( ) , ;
bitCount(a i )==bitCount(a i |a min )a i ==a i |a min - , ( ) –
- min ( )
- min (min) (max) ( ) , ;
- () :
- ( “” “”)
- :
- “”, max ,
or|=a i ,a max &=~or
( “a max ^=or
(a maxa min, .. , )
- “”, max ,
- /:
- (RingSync)
. ( ), .
“ , ”
, , (“ {…} ”) () . ():
// " " int ...;{ // "" }
“”, ():
//==[Name]==// int ...;{ ... }
, :
those. – , “, ” – .
?
:
- – ( ) , . “” , .. “” “” . , “ ”, .
- – “” / , , . . , (Interprocedural optimization, Whole program optimization; Link‑time optimization) “” – .
Note : : .. (2D/3D , , *, …). (), , , ( , , 24 , ; , ACPI ), ( ) , ：（. (, , …) , ‑ . , , ‑. ( “” “”), “ *”. , – , , , . () – , . – ( ), . – , //‑/ /. (debug) ‑ .
Note : Debug , (, – { 9 , ; – ×16 ( 1.2 1.5); → }), warning' .
Note : , , , ‑. , , ( “ ” ) .
# Tooo Long; Didn't Read; Visualize, plz.
Note : , ( GIF “TensorsFlowing” “ ”). GIF “TensorsFlowing” GIF “ Loop over python list animation ”. , GIF , “ ” / . , ‑ 1:1, “ ”.
#
Note : GIF ( “Loop over python list animation”), . , , . ( ；）
Note : ( ) ( ). , .
Note : GIF ( “Scroll Down”) – (Ctrl+R), GIF . ( , ; , ‑ <oembed> ? )
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; } 
Note : std::nth_element() , , ( + = ).
Note : GIF 
. ReadMe ( ; ‑ , ).
...
#
3‑ 1.92 , ,
+ TODO' + .
, ‑ , , , 2 .
Note : , / , …
2 ?
?
, , . , , 2 . .
# Tooo Long; Didn't Read; Visualize, plz.
TODO[old]: (1 – gif_1, , 2 – gif_2, , …)
TODO: ,
? ( )
TODO: ( GIF “TensorsFlowing”, ‑ – ),
( Note, GIF , , , YouTube. : 4:2:0 TV‑ (
# ?
( ), std (, ) ( );
( “ 1 ” == “ 1 ” ). Example:
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, + . , , , , .
...
LLTR 3: OMNeT++
Golang. ( , )
( ,
( “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]” “ ” ( )
References:
- OMNetProject (v0.9) lltdapp
- OMNetProject (v0.9.1) lltdapp
- OMNetProject (fixed event time — v0.9.2) lltdapp
- OMNetProject (v0.9.3) lltdapp
LLTR 4:
.jpg)
, “” .
(, . )
References:
- Get sequence (math induction) , online (Google Spreadsheets):
, (hostsCount) – . . ? (: )
(, “”, {“”,“”,“”})
( ( ) [ ; “ ”], – n‑ “ ”; , LLTR, )
( , __ [ , , , ]):
n=4; k=2 bitset i 0011 <- 0 0101 <- 1 1001 <- 2 0110 <- 3 1010 <- 4 1100 <- 5
Note: , .. bitset k i < bitset k i+1 , i – “ ”; k – ; n – .
“” ( ; /; , “”/), ?
, :
- habrahabr.ru/post/276937/#comment_8768131 ( alisey Trif )
- stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others/24257996#24257996
:
“ ” (“ ”; “Permutations of multisets”).
What's the Difference? ( [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#__
PS stackoverflow.com/a/24257996 , ( – : n!∕((n−k)!); n⩵k; (n−k)!⇒1; n! ).
PPS [ alisey Trif ] ‑ / ( “Permutations of multisets”), ?
LLTR 5: OMNeT++ 2
( LLTR-Process sequence, – { “LLTD-Process (vFinal)”}, – , i → dstId, )
References:
LLTR 6:
, Golang.
References:
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”)
References:
( “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 )
– “
TODO [x]: () + , + , ,
:
- 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 (fixed event time — v0.9.2) lltdapp – , “stat.txt” [ 3]
- OMNetProject (v0.9.3) lltdapp – v0.9.1 + , + v0.9.2ft [ 3]
- Get sequence (math induction) – : unicast_src_host i+1 = unicast_dst_host i , .. , (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
PS ( ) “ ”.
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) :
- PNG:
- [ 778px, 756px] ‑ ( . )
- ‑ 7z (un[7z]me), ( – “ ”, ‑ , ‑ )
- [ Photoshop] “Save for Web” → PNG 24+alpha
- [ GIMP] “8bpc RGBA” ( ), “ Save for Web ”
- 256 + alpha‑
- [ Adobe Fireworks] (Ctrl+Shift+X) → PNG‑8 + alpha
- []
- “” , Image Catalyst ( “” 2 : 2.1 2.5 , ):
- “” Image Catalyst 2.1 ([5] Xtreme profile)Tools\config.ini
[options] ; , "true" "false". fs = true ; PNG. 0, %NUMBER_OF_PROCESSORS%. threatpng = 0 ; . , "true" "false". up = false [JPEG] ; Metadata. Metadata JPEG, "true" "false" , . dc = true ;Delete comment field (as left by progs like Photoshop & Compupic). de = true ;Strip Exif section (smaller JPEG file, but lose digicam info). di = true ;Delete IPTC section (from Photoshop, or Picasa). dx = true ;Deletex XMP section. du = true ;Delete non image sections except for Exif and comment sections. [PNG] ; ColorType BitDepth. ColorType BitDepth PNG, "true" "false". nc = true ; -. "Dirty Transparency" PNG c -, "true" "false". na = true ; Chunks. ; Chunks Chunks, "remove" Chunks Chunks, . ; Chunks Chunks, "keep" Chunks Chunks, . ; Chunks: ;text = iTXt,tEXt,zTXt ;color = cHRM,sRGB,iCCP,gAMA ;misc = bKGD,pHYs,sBIT,sPLT,hIST,tIME ;all = all of noncritical chunks hunks = remove all
Note : “ Image Catalyst 2.1 . Enter. ”, , , ( “Image Catalyst 2.1” “Image-Catalyst-2.1”) - “” Image Catalyst 2.5 ([1] Xtreme profile)Tools\config.ini
[options] ;Number of streams. If value early 0, is used value of parameter %NUMBER_OF_PROCESSORS%. thread=0 ;Automatic replacement of original images by the optimized. outdir=true ;Check update update=false [PNG] ;Parameters of optimization of PNG: ;/a# - PNG dirty transparency 0=Clean, 1=Optimize; ;/g# - PNG gamma 0=Remove, 1=Apply & Remove, 2=Keep; ;/na - PNG don't change RGB values for fully transparent pixels; ;/nc - PNG don't change ColorType and BitDepth; ;/np - PNG don't change Palette. xtreme=/a1 /g0 advanced=/a0 /g0 ;Remove PNG Metadata (Chunks). chunks=true [JPEG] ;Remove JPEG Metadata. metadata=true [GIF] ;Remove GIF Metadata. giftags=true
Note : “ Attention: running 2 of Image Catalyst. ”, , , ( “iCatalyst-2.5”) - 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!" )
- “” Image Catalyst 2.1 ([5] Xtreme profile)
- “.svg” ( ) – (SVG) (un[7z]me)
- SVG:
- {SVG 1.1; UTF-8; ; : ; : “1:100”; } ( , 2 – 1‑ )
- transform SVG ( 90 ) ( SVG ):
- DevTools transform ( “
[transform]”) - “
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 WH" 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
- DevTools transform ( “
- :
- :
- ( [, ] )
- ( )
- :
- ( )
- XML ( )
- ( ):
- “
DOCTYPE” “Creator” “96ppi” ( ppi CorelDRAW SVG) - “
metadata”, “id” ( ) - svg:
- “
xmlns” “xml:space” - “
xmlns:xlink” - [, “
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"`
- “
- ( ) `
"` `"`
- “
- ( <rect> <g>), , “
viewBox” ( <svg>)- , SVG , CorelDRAW – , , , ( , )
- SVG optimiser :
- :
- Whitespace: pretty
- Style type: optimal
- Truncate * numbers: unchanged
- ( , “Remove clean group”, )
- <svg>
- <style> – SVG optimiser CDATA ( )
- :
- XML
- ( ):
- PNG SVG:
- “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” .
- “PNG_SVG.bat” ( 7-Zip SVG: “
Note : Image Catalyst: ping timeout, ( 2.5) ( 2.1 – )
v2.1 diff:
182c182 < if defined thrt >nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:waithreat --- > if defined thrt >nul 2>&1 timeout /t 1 /nobreak & goto:waithreat 203c203 < 1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 --- > 1>nul 2>&1 timeout /t 1 /nobreak 237c237 < if exist "%~1" (1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:waitflag) --- > if exist "%~1" (1>nul 2>&1 timeout /t 1 /nobreak & goto:waitflag) 513c513 < if exist "%tmppath%\typelog.lck" (1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:savelog) --- > if exist "%tmppath%\typelog.lck" (1>nul 2>&1 timeout /t 1 /nobreak & goto:savelog) 534c534 < if "%jpeg%" equ "0" if "%png%" equ "0" 1>nul ping -n 1 -w 500 127.255.255.255 2>nul & goto:finmessage --- > if "%jpeg%" equ "0" if "%png%" equ "0" 1>nul timeout /t 1 /nobreak 2>nul & goto:finmessage 572c572 < 1>nul ping -n 1 -w 500 127.255.255.255 2>nul --- > 1>nul timeout /t 1 /nobreak 2>nul
V2.5 diff:
319,320c319 < call:division float 1024 100 < call:echostd " In - !float! " --- > call:echostd " In - !float! " 322d320 < call:division change 1024 100 324,325c322 < call:division float 1024 100 < call:echostd " Out - !float! (!change! , %5%%%%%%)" --- > call:echostd " Out - !float! (!change! , %5%%%%%%)" 362,363c359,360 < set /a "ww=%random%%%%1" < 1>nul 2>&1 ping -n 1 -w %ww% 127.255.255.255 --- > set /a "ww=%random%%%%1/1000" > 1>nul 2>&1 timeout /t %ww% /nobreak 707c704 < if %jpeg% equ 0 if %png% equ 0 if %gif% equ 0 1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:finmessage --- > if %jpeg% equ 0 if %png% equ 0 if %gif% equ 0 1>nul 2>&1 timeout /t 1 /nobreak & goto:finmessage 741d737 < call:division changePNG 1024 100 747d742 < call:division changeJPG 1024 100 753d747 < call:division changeGIF 1024 100 800c794 < call:echostd " Total %1: %%change%1%% , %%perc%1%%%%%%" --- > call:echostd " Total %1: %%change%1%% , %%perc%1%%%%%%"
Note : Image Catalyst ( ) CP866, diff, , .
- 778px – (780px – − 2px )
- 756px – (758px – − 2px )
- 738px – (740px – − 2px )
- Image Catalyst v2.1 v2.5, ( “ merge_min.bat ”).
- – : habrastorage “dwbmwbyvlzes80cep1hvcdb5iy.png” () HTTP‑ “
Content-Disposition : inline ;...”, , , (): “dwbmwbyvlzes80cep1hvcdb5iy.png#real-name.png”. , – ( ). SVG – (), , … - (id, name). . ( – , , – )
- , ( ).
- ‑ (un[7z]me), habrastorage – , CloudFlare Polish .
Note : habrastorage SVG ( ): ( ), PNG{SVG} ( SVG, , – ) ( , , / – ‑ / , )
git:
- git tag git “git-tag-‹›” .
- git , / , “article_#”. ( LLTR Simulation Model )
- ( “http”), ( ) web.archive.org, sohabr.net:
var res=str.match(/http[^#)\s]*/gm); var res_l=res.length; for(var i=0;i<res_l;i++) console.log(res[i]); var archive = res.filter(function(a){return a.search(/(omnetpp.org\/doc\/omnetpp\/manual\/#|wikipedia|\/github.com\/)/)==-1;});- , web.archive.org sohabr.net .
- habrahabr.ru habr.com, .. web.archive.org ( , ).
- , Wikipedia “?stable=1”.
- () MediaWiki (“#.D0.AD.D0.B2.D1.80.D0.B8.D1.81…”; “wikipedia”, “#.D0”) (“#…”).
- C ( ) + Git.
- [ “ 2”] (“LLTR #::”), “title” ( ).
- (id, name), (, “#”) ( title “ ”).
- (<hr />) – , UserCSS ( UserCSS ).
- `
<p><br /></p>`, UserCSS `<br />`, `margin` `<p>` ( ). - 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 ( ).
')
Source: https://habr.com/ru/post/421243/
All Articles