nse.rst (6426B)
1 .. index:: 2 single: subsystem; Network size estimation 3 see: NSE; Network size estimation 4 5 .. _NSE-Subsystem-Dev: 6 7 NSE 8 === 9 10 The NSE subsystem has the simplest API of all services, with only two 11 calls: ``GNUNET_NSE_connect`` and ``GNUNET_NSE_disconnect``. 12 13 The connect call gets a callback function as a parameter and this 14 function is called each time the network agrees on an estimate. This 15 usually is once per round, with some exceptions: if the closest peer has 16 a late local clock and starts spreading its ID after everyone else 17 agreed on a value, the callback might be activated twice in a round, the 18 second value being always bigger than the first. The default round time 19 is set to 1 hour. 20 21 The disconnect call disconnects from the NSE subsystem and the callback 22 is no longer called with new estimates. 23 24 .. _Results: 25 26 Results 27 ^^^^^^^ 28 29 The callback provides two values: the average and the `standard 30 deviation <http://en.wikipedia.org/wiki/Standard_deviation>`__ of the 31 last 64 rounds. The values provided by the callback function are 32 logarithmic, this means that the real estimate numbers can be obtained 33 by calculating 2 to the power of the given value (2average). From a 34 statistics point of view this means that: 35 36 - 68% of the time the real size is included in the interval 37 [(2average-stddev), 2] 38 39 - 95% of the time the real size is included in the interval 40 [(2average-2*stddev, 2^average+2*stddev] 41 42 - 99.7% of the time the real size is included in the interval 43 [(2average-3*stddev, 2average+3*stddev] 44 45 The expected standard variation for 64 rounds in a network of stable 46 size is 0.2. Thus, we can say that normally: 47 48 - 68% of the time the real size is in the range [-13%, +15%] 49 50 - 95% of the time the real size is in the range [-24%, +32%] 51 52 - 99.7% of the time the real size is in the range [-34%, +52%] 53 54 As said in the introduction, we can be quite sure that usually the real 55 size is between one third and three times the estimate. This can of 56 course vary with network conditions. Thus, applications may want to also 57 consider the provided standard deviation value, not only the average (in 58 particular, if the standard variation is very high, the average maybe 59 meaningless: the network size is changing rapidly). 60 61 .. _libgnunetnse-_002d-Examples: 62 63 Examples 64 ^^^^^^^^ 65 66 Let's close with a couple examples. 67 68 Average: 10, std dev: 1 Here the estimate would be 69 2^10 = 1024 peers. (The range in which we can be 95% sure is: [2^8, 70 2^12] = [256, 4096]. We can be very (>99.7%) sure that the network is 71 not a hundred peers and absolutely sure that it is not a million 72 peers, but somewhere around a thousand.) 73 74 Average 22, std dev: 0.2 Here the estimate would be 75 2^22 = 4 Million peers. (The range in which we can be 99.7% sure is: 76 [2^21.4, 2^22.6] = [2.8M, 6.3M]. We can be sure that the network size 77 is around four million, with absolutely way of it being 1 million.) 78 79 To put this in perspective, if someone remembers the LHC Higgs boson 80 results, were announced with \"5 sigma\" and \"6 sigma\" certainties. In 81 this case a 5 sigma minimum would be 2 million and a 6 sigma minimum, 82 1.8 million. 83 84 .. _The-NSE-Client_002dService-Protocol: 85 86 The NSE Client-Service Protocol 87 ------------------------------- 88 89 As with the API, the client-service protocol is very simple, only has 2 90 different messages, defined in ``src/nse/nse.h``: 91 92 - ``GNUNET_MESSAGE_TYPE_NSE_START`` This message has no parameters and 93 is sent from the client to the service upon connection. 94 95 - ``GNUNET_MESSAGE_TYPE_NSE_ESTIMATE`` This message is sent from the 96 service to the client for every new estimate and upon connection. 97 Contains a timestamp for the estimate, the average and the standard 98 deviation for the respective round. 99 100 When the ``GNUNET_NSE_disconnect`` API call is executed, the client 101 simply disconnects from the service, with no message involved. 102 103 NSE Peer-to-Peer Protocol 104 .. _The-NSE-Peer_002dto_002dPeer-Protocol: 105 106 The NSE Peer-to-Peer Protocol 107 ----------------------------- 108 109 GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD 110 The NSE subsystem only has one message in the P2P protocol, the 111 ``GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD`` message. 112 113 This message key contents are the timestamp to identify the round 114 (differences in system clocks may cause some peers to send messages way 115 too early or way too late, so the timestamp allows other peers to 116 identify such messages easily), the `proof of 117 work <http://en.wikipedia.org/wiki/Proof-of-work_system>`__ used to make 118 it difficult to mount a `Sybil 119 attack <http://en.wikipedia.org/wiki/Sybil_attack>`__, and the public 120 key, which is used to verify the signature on the message. 121 122 Every peer stores a message for the previous, current and next round. 123 The messages for the previous and current round are given to peers that 124 connect to us. The message for the next round is simply stored until our 125 system clock advances to the next round. The message for the current 126 round is what we are flooding the network with right now. At the 127 beginning of each round the peer does the following: 128 129 - calculates its own distance to the target value 130 131 - creates, signs and stores the message for the current round (unless 132 it has a better message in the \"next round\" slot which came early 133 in the previous round) 134 135 - calculates, based on the stored round message (own or received) when 136 to start flooding it to its neighbors 137 138 Upon receiving a message the peer checks the validity of the message 139 (round, proof of work, signature). The next action depends on the 140 contents of the incoming message: 141 142 - if the message is worse than the current stored message, the peer 143 sends the current message back immediately, to stop the other peer 144 from spreading suboptimal results 145 146 - if the message is better than the current stored message, the peer 147 stores the new message and calculates the new target time to start 148 spreading it to its neighbors (excluding the one the message came 149 from) 150 151 - if the message is for the previous round, it is compared to the 152 message stored in the \"previous round slot\", which may then be 153 updated 154 155 - if the message is for the next round, it is compared to the message 156 stored in the \"next round slot\", which again may then be updated 157 158 Finally, when it comes to send the stored message for the current round 159 to the neighbors there is a random delay added for each neighbor, to 160 avoid traffic spikes and minimize cross-messages. 161 162