First Message Priority

[AgeManning]

Description

There is discussion and simulations around improving the overall message transmission via scheduling "first" messages being sent out on a mesh. See here: https://ethresear.ch/t/improving-das-performance-with-gossipsub-batch-publishing/21713

Motivation

When gossipsub publishes a message, it duplicates it to all mesh peers (and all peers if flood publish is enabled). If there are multiple messages to be sent, on the same topic, the second message will be added to each peer's queue and won't be sent until the peer has sent the first message. Just changing the ordering of messages in the queue, will enable at least one instance of each message to reach the network before sending the duplicates, allowing for faster overall message transmission.

An implementation of this is here: libp2p#5924

Sending across multiple topics is harder to reason about, because each topic has its own mesh. Sending multiple messages to each topic, may not have overlapping peer sets and so ordering messages is not easily done (at least in our implementation).

One general way, that I think could be beneficial, is to use the ordering ability in this proposed async-channel implementation: #570.

For every message we publish, when duplicating the message for each mesh peer, we randomly select one peer and tag the message to that peer as a "first" message or priority message. This message takes a priority precedence in that peers queue (not above control messages however).

I'm thinking if we do this for each published message regardless of topic and mesh, then we have sense of priority for one message being published above all the other duplicates.

Each peer could have multiple priority messages, but it will try to send those before it sends "duplicates".

I have no idea if this helps with propagation but I suspect it aligns a little with what is mentioned in the blog post referenced at the start of this issue.

cc @jxs @elenaf9 @cskiraly @jimmygchen

Current Implementation

--

Are you planning to do it yourself in a pull request?

Maybe

[jxs]

Hi Age, and thanks for opening this,

When gossipsub publishes a message, it duplicates it to all mesh peers (and all peers if flood publish is enabled)

I think this only happens to FloodSub peers, flood publish still respects the mesh:

With flood publishing enabled, the mesh is used when propagating messages from other peers, but a peer's own messages will always be published to all known peers in the topic.

Reading the conversation from the original post I cannot understand if the second message to be sent is after some time has elapsed or after the confirmation of the successful delivery, but in both cases on a first opinion on the matter and after a conversation with @pawanjay176 I think this should be done outside of gossipsub as it is not part of the spec.

If the second message is to be sent is to be sent after successful sending of the first as you suggest the only modification we need from gossipsub is a ToSwarm::GenerateEvent of a successful publish of a given message. I.e add a flag to the publish function to notify the swarm on a successful publish of that message.
That would allow lighthouse or any other use of gossipsub to implement the desired ordering of the batch to be sent, wdyt?

[AgeManning]

I think I may not have explained the issue well enough.

When we publish a message to a topic, we find peers on our mesh, lets say there's 8 of them.

We then send this message to each peer, thus making 8 copies of this message.

We do this process for every message on a range of topics.

To highlight this, lets say we publish 3 messages (A,B,C) on the same topic, which has 3 mesh peers (1,2,3) on it. In the current case, we would add these messages to the three peers queues, like this:
1: [A,B,C]
2: [A,B,C]
3: [A,B,C]

So each peer, 1, 2 and 3 are all trying to send A at the same time. The observation that it would be better to propagate messages on the network if the queues looked like:
1: [A,B,C]
2: [B,C,A]
3: [C,B,A]

In this scenario, peers 1,2,3 are all trying to send different messages at the same time and once they have done that, then they try to send the "duplicates" or copies.

I wrote an implementation for the second scenario here: libp2p#5924

This logic is harder to generalise across multiple topics, but I think we could just "tag" one message as a priority on a random peer.

So, using the same example, we publish messages A, B, C.

When publishing A, we randomly select peer 2 and set A as a priority.
When publishing B, we randomly select peer 1 and set B as a priority.
When publishing C, we randomly select peer 3 and set C as a priority.
(We got lucky with this randomization, but to demonstrate the point).

The queues should look like: (I'm using * to denote the message as a "priority" message making it be in front of the queue):
1: [B*, A, C]
2: [A*, B. C]
3: [C*. A. B]

Assuming the randomization helps us, we get a similar result with each peer working on a unique message.

[ackintosh]

Thanks, Age! I will try to do simulation with the PR using the Shadow simulator to see how much the change improves message delivery.

[AgeManning]

Oh nice. The PR that I wrote is pretty much useless for what we need.

I think the thing that would have more value is what I've explained in this issue. Essentially we want @jxs PR:#570
But then when publishing a message we prioritize one message to one peer in the queue.