<titledata-rh="true">Message Propagation Times With Waku-RLN | Waku Documentation</title><metadata-rh="true"name="viewport"content="width=device-width,initial-scale=1"><metadata-rh="true"name="twitter:card"content="summary_large_image"><metadata-rh="true"property="og:url"content="https://docs.waku.org/learn/research/research-and-studies/message-propagation"><metadata-rh="true"property="og:locale"content="en_GB"><metadata-rh="true"name="docusaurus_locale"content="en-GB"><metadata-rh="true"name="docsearch:language"content="en-GB"><metadata-rh="true"name="keywords"content="waku, web3"><metadata-rh="true"name="image"content="https://docs.waku.org/_og/e093238147e25245716028178897434ad9585a62.png"><metadata-rh="true"name="docusaurus_version"content="current"><metadata-rh="true"name="docusaurus_tag"content="docs-default-current"><metadata-rh="true"name="docsearch:version"content="current"><metadata-rh="true"name="docsearch:docusaurus_tag"content="docs-default-current"><metadata-rh="true"property="og:title"content="Message Propagation Times With Waku-RLN | Waku Documentation"><metadata-rh="true"name="description"content="TLDR: We present the results of 1000 nwaku nodes running rln using different message sizes, in a real network with bandwidth limitations and network delays. The goal is to study the message propagation delay distribution, and how it's affected by i) rln and ii) message size in a real environment. We observe that for messages of 10kB the average end-to-end propagation delay is 508 ms. We can also observe that the message propagation delays are severely affected when increasing the message size, which indicates that it is not a good idea to use waku for messages of eg. 500kB. See simulation parameters."><metadata-rh="true"property="og:description"content="TLDR: We present the results of 1000 nwaku nodes running rln using different message sizes, in a real network with bandwidth limitations and network delays. The goal is to study the message propagation delay distribution, and how it's affected by i) rln and ii) message size in a real environment. We observe that for messages of 10kB the average end-to-end propagation delay is 508 ms. We can also observe that the message propagation delays are severely affected when increasing the message size, which indicates that it is not a good idea to use waku for messages of eg. 500kB. See simulation parameters."><linkdata-rh="true"rel="icon"href="/theme/image/favicon.ico"><linkdata-rh="true"rel="canonical"href="https://docs.waku.org/learn/research/research-and-studies/message-propagation"><linkdata-rh="true"rel="alternate"href="https://docs.waku.org/learn/research/research-and-studies/message-propagation"hreflang="en-GB"><linkdata-rh="true"rel="alternate"href="https://docs.waku.org/learn/research/research-and-studies/message-propagation"hreflang="x-default"><linkrel="alternate icon"type="image/png"href="/theme/image/favicon.png">
<h2class="anchor anchorWithHideOnScrollNavbar_WYt5"id="introduction">Introduction<ahref="#introduction"class="hash-link"aria-label="Direct link to Introduction"title="Direct link to Introduction"></a></h2>
<p>Waku uses <ahref="https://rfc.vac.dev/spec/11/"target="_blank"rel="noopener noreferrer">relay</a> as a routing protocol, which is an adaptation of <ahref="https://arxiv.org/pdf/2007.02754.pdf"target="_blank"rel="noopener noreferrer">gossipsub</a>. It routes messages following a publisher/subscriber architecture, where nodes can publish messages or subscribe to topics. If message <code>m</code> is published to topic <code>t</code>, all <code>i</code> nodes <code>n_1...n_i</code> subscribed to <code>t</code> will get <code>m</code>. The <code>relay</code> protocol ensures that every node gets the messages of the topics it is subscribed to.</p>
<p>However, since <code>relay</code> works in a decentralized manner, all nodes contribute to the gossiping of a message, until it has successfully reached all the interested nodes (subscribed to it). This means that a message can travel multiple hops until it reaches all nodes. The amount of hops determines the <strong>message propagation time</strong>, which is measured as the <strong>time difference of when the node published the message and when another node received</strong>.</p>
<p><strong>This issue aims to go from theory to practice, by i) understanding message propagation times in theory and ii) presenting nwaku simulation results in an end-to-end setup with rln, with real message propagation times</strong>.</p>
<h2class="anchor anchorWithHideOnScrollNavbar_WYt5"id="theory">Theory<ahref="#theory"class="hash-link"aria-label="Direct link to Theory"title="Direct link to Theory"></a></h2>
<p>Let's start with <strong>message propagation times in theory</strong>. On a high level, it depends on:</p>
<ul>
<li>The gossipsub <ahref="https://github.com/libp2p/specs/blob/master/pubsub/gossipsub/gossipsub-v1.0.md#parameters"target="_blank"rel="noopener noreferrer">configuration</a>, being <code>D</code> one of the most important parameters. This sets the hops that a message will travel to reach all nodes. Higher <code>D</code>, less hops, less delay. Note that a higher <code>D</code> implies more bandwidth consumption.</li>
<li>The node. Different nodes will see different propagation times, because a message can travel different paths. A node connected directly to the publisher (1 hop) will see lower propagation times than other nodes further away.</li>
<li>Individual propagation times. Since a message can travel multiple hops to reach its destination, each hop adds a contribution to the overall message propagation time. This individual propagation time depends on the characteristics on the nodes involved in the connections.</li>
</ul>
<p>In a D-regular graph, like the one formed by waku nodes around a topic, the maximum amount of hops that a message can travel to reach all nodes can be calculated as <code>ceil(log(total_nodes)/log(D))</code>. For example, with log(1000)/log(6) = 3.85 = 4. So in a network with 1000 nodes and <code>D=6</code>, no matter which node publishes the message, in 4 hops it will reach all the nodes.</p>
<p>Notice the <strong>"worst case"</strong> since some nodes might be directly connected to the publisher, so they will get the message in just 1 hop.</p>
<p>But how long does it take to jump each hop? It depends on:</p>
<ul>
<li>The latency between nodes. Can be measured as the time to respond to a ping.</li>
<li>The size of the messages. The bigger the message, the more time it takes to transmit.</li>
<li>Nodes bandwidth. Sender upload bandwidth and receiver download bandwidth. More important when using big message sizes.</li>
<li>Message validation time. When each node receives a message, it applies some validation to decide if the message is further gossiped or not. In the case of waku, this is RLN (<ahref="https://arxiv.org/pdf/2207.00116.pdf"target="_blank"rel="noopener noreferrer">paper</a>, <ahref="https://rfc.vac.dev/spec/32/"target="_blank"rel="noopener noreferrer">rfc</a>)</li>
</ul>
<p>Assuming a message <code>m</code> that travels 4 hops from node <code>n1</code> (publisher) to <code>n5</code> (subscriber) we can calculate the message propagation time <code>mpt=ipt_1+ipt_2+ipt_3+ipt_4</code> where <code>ipt</code> is the individual propagation time between each node in the chain.</p>
<p>However, specific message propagation times are useless, we need average times under specific conditions. And <strong>for this, we need simulations</strong>.</p>
<h2class="anchor anchorWithHideOnScrollNavbar_WYt5"id="simulations">Simulations<ahref="#simulations"class="hash-link"aria-label="Direct link to Simulations"title="Direct link to Simulations"></a></h2>
<p>Using <ahref="https://shadow.github.io/docs/guide/shadow.html"target="_blank"rel="noopener noreferrer">shadow</a> simulator, we have developed a <ahref="https://github.com/waku-org/research/tree/master/rln-delay-simulations"target="_blank"rel="noopener noreferrer">tool</a> that allows to simulate message propagation delays of <code>nwaku</code> (using a slightly modified <ahref="https://github.com/waku-org/nwaku/compare/master...simulations"target="_blank"rel="noopener noreferrer">branch</a>, mainly to instrument it with tools to measure the times + starting from an already connected mesh. Thanks <ahref="https://github.com/menduist"target="_blank"rel="noopener noreferrer">@Menduist</a> for the help. Note that running this simulation requires a significant amount of resources, done with 256 GB of RAM.</p>
<p>The configuration of the simulation is (see <ahref="https://github.com/waku-org/research/blob/master/rln-delay-simulations/shadow.yaml"target="_blank"rel="noopener noreferrer">config</a>):</p>
<ul>
<li><code>latency=100ms</code>. Average latency in our current waku network. Thanks <ahref="https://github.com/vpavlin"target="_blank"rel="noopener noreferrer">@vpavlin</a> for the measurements. See <ahref="https://grafana.infra.status.im/d/b819dbfe-acb6-4086-8736-578ca148d7cd/waku-networkmonitor-v2?orgId=1&refresh=30s&viewPanel=12"target="_blank"rel="noopener noreferrer">this</a> for live data.</li>
<li><code>down_bandwidth=83Mbps</code>, <code>up_bandwidth=38Mbps</code>. As shown in <ahref="https://github.com/waku-org/research/issues/31"target="_blank"rel="noopener noreferrer">Table 2</a> that's the worldwide median speed.</li>
<li><code>D=6</code>, which is the current <code>nwaku</code><ahref="https://github.com/waku-org/nwaku/blob/v0.21.0/waku/waku_relay/protocol.nim#L73-L78"target="_blank"rel="noopener noreferrer">configuration</a>.</li>
<li><code>nodes=1000</code>. Amount of nodes used in the simulation</li>
<li><code>nwaku</code> was used with a minor <ahref="https://github.com/waku-org/nwaku/compare/master...simulations"target="_blank"rel="noopener noreferrer">modification</a></li>
<li>A total of <code>10</code> messages were published, that led to <code>9990</code> received messages.</li>
<li>Since <code>shadow</code><strong>doesn't take into account CPU times</strong> (<ahref="https://github.com/shadow/shadow/discussions/1675#discussioncomment-7342812"target="_blank"rel="noopener noreferrer">by now</a>), we simulate it with <code>sleepAsync</code> as per <ahref="https://github.com/waku-org/research/issues/23"target="_blank"rel="noopener noreferrer">https://github.com/waku-org/research/issues/23</a> findings. <code>0.012 seconds</code> for proof verification and <code>0.15 seconds</code> for proof generation.</li>
</ul>
<h2class="anchor anchorWithHideOnScrollNavbar_WYt5"id="results">Results<ahref="#results"class="hash-link"aria-label="Direct link to Results"title="Direct link to Results"></a></h2>
<p>The following figure shows the <strong>message propagation time with real simulations</strong>, showing the distribution in a network with the above configuration with three different message sizes: <code>10kB</code>, <code>100kB</code>, <code>500kB</code>. Note that the whiskers indicate the best/worst values and the box contains P25 to P75 values. Average <code>mu</code> and P95 are also shown. Raw data <ahref="https://github.com/waku-org/research/tree/master/rln-delay-simulations/raw"target="_blank"rel="noopener noreferrer">here</a>.</p>
<p><strong>Important note</strong>. The first messages sent in the simulations are omitted, since they show an abnormal propagation delay that doesn't reflect reality. This is due to how flow control works in TCP, where right after connection, the sender node has no idea of the "bandwidth" of the receiver node, so it will start sending packages at a lower rate. This translates into high transmission times, and it's more pronounced when dealing with big message sizes.</p>
<p>In other words, in a 100Mpbs link, 100Mbits won't be sent in 1 second, or at least not a the beginning, when the node is slowly increasing the rate until based on ACK/NACK ratio. For more information about this, this is explained in <ahref="https://www.youtube.com/watch?v=vb_wjh_nAmo"target="_blank"rel="noopener noreferrer">here</a>.</p>
<p><strong>Conclusions:</strong></p>
<ul>
<li>Using small messages <code>10kB</code> the <strong>average propagation delay is <code>508 ms</code></strong>, quite reasonable for applications using waku. The variance is acceptable, with 95% of the messages arriving in <code><627 ms</code>.</li>
<li>When using a size of <code>10kB</code> we can see that the best case propagation delay is <code>263 ms</code>. This corresponds to the nodes that are just 1 hop from the publisher. The proof generation time <code>0.15 seconds</code> affects the most, where the rest is the inter-node latency and the transmission of the message itself.</li>
<li>We can see that the <strong>message propagation delay increases with big messages</strong>, <code>100kB</code> and <code>500kB</code>. So its <strong>probably not a good idea to use waku for such big messages</strong>. Note that these simulations had 1000 nodes, so if we scale it to 10000 or beyond, propagation times would be worse.</li>
<li>Best case propagation time (lower part of the whisker) is quite similar in all cases. This is because it corresponds to the node that is just 1 hop away from the publisher.</li>
</ul>
<p><strong>Future work</strong>:</p>
<ul>
<li>Current waku <code>D</code><ahref="https://github.com/waku-org/nwaku/blob/v0.21.0/waku/waku_relay/protocol.nim#L73-L78"target="_blank"rel="noopener noreferrer">values</a> (average of 6 ranging from 4 to 12) have a huge impact on the bandwidth that a node consumes. Are we willing to lower D in order to reduce bandwidth but increase message propagation times?</li>
<li>Since <code>shadow</code> doesn't take CPU time into account, it's currently simulated for rln, which should be the biggest bottleneck. Once <code>shadow</code> has <ahref="https://github.com/shadow/shadow/discussions/1675#discussioncomment-7342812"target="_blank"rel="noopener noreferrer">this feature</a> times would be more accurate.</li>
