Recently I've been attempting to view world around from p2p node's perspective
i.e. how can a p2p node learn about
global topology of network it's part of. Nodes are aware of neighbourhood
but not how neighbours are themselves stuctured. Node has no idea of
edges existing between a pair of vertices, when it's not one of those. Nodes follow one cooperative
protocol by forwarding messages to peers who hasn't yet seen certain message.
Each peer authors its own message & helps in forwarding peer-authored messages
while playing role of hop. By inspecting message body, node learns
of which hops has helped in forwarding certain message & pictures path in network. A few
of these messages, traversed through different paths, helps in forming substantial portion of network graph.
Last week I wrote about it here.
In previous setting of simulation, network topologies were statically synthesized & small number
of participants collaborated. This week I explore more dynamically generated network
topologies. I also bring in libp2p based nodes into picture. Main goal is to understand
how to tweak the algorithm so that it can adaptively catch changes happening throughout
network, while keeping network wide peer specific topology probings at minimum.
I classify messages passed around by respective purpose. Broadly speaking, there're
three kinds of messages which can be sent across network.
- Probe Message
- Edge Add Message
- Edge Remove Message
I consider each participant of p2p network as vertex
& each TCP connection between a pair of them as an edge, while picturing
p2p overlay network as graph. P2P networks keep changing
their structure frequently, due to some node going down or network partition
occuring, which is why node's world view should be adapting to those changes.
I name, TCP connection being established between two peers as edge added event,
whereas disconnection of two peers triggers edge removed event. When either
of these two events happen, news is gossiped throughout network. And this allows
existing participants to either add or remove an edge from graph, which it's maintaining locally
as world view.
But some peer who has just joined network may be interested in exploring world
around, so it authors one probe message, which is passed throughout network collecting
trace of hops who cooperated in gossiping, helping every participant to refresh
their world view. And this is what I call, probing.
Probing helps any network participant to learn network topology
while it's not really necessary that everyone probes, rather single peer
probes & everyone learns.
When announcing edge added event, both of peers upon which edge
is incident, authors their own message with kind set to add.
Each incident node sends message to other one, at very first step of
connection establishment, making other side of edge aware of self-identity.
After that each of them shares message with their neighbours,
so that it can be propagated throughout network. Before announcing, peer sets self-id
as other side of edge, denoting edge has been established between two peers; also
appends self as hop of message so that network doesn't send this message back to
this peer again --- reducing cost to some extent.
// send self authored message to peer
// and forward peer authored one to
// local neughbourhood, so that nodes
// on which edge is incident upon
// learns of each others identifiers
def add_edge_gossip_init():
// kind = "add"
msg_s = author_message(:self)
send(msg_s, :peer)
// wait for peer to send
recv(&msg_r, :peer)
// designates edge by adding self_id
// where peer_id is already present
update_edge_description(msg_r, :self)
append_hop(msg_r, :self)
// except from whom received
propagate(msg_r, :peers)
enddef
Similarly when disconnection between two peers occur, edge removed event is propagated. But this time each of those affected nodes, author their own message with kind set to del and puts edge description in terms of ( previously ) incident node identifiers, so that when other participants receive message they can delete this edge from their locally maintained view of network.
// announce it to all neighbours
def del_edge_gossip_init():
// kind = "del"
msg = author_message(:self)
add_edge_description(msg, :self, :peer)
propagate(msg, :all)
enddef
Probing specific crafted message carries authorship details, kind set to probe & identifier of hops i.e. trace of path through which message has traversed. That's why inspection of probe message body, helps peer in deciding whom to forward message & picturing a path in network. Over time a peer receives multiple copies of same message traversed via different paths, from its neighbours --- learning of existence of multiple paths in network. Peers follow collaborative gossip protocol & message path is determined by trace in message body, which is updated before forwarding it to next hop.
// announce it to all neighbours
def probe_gossip_init():
// kind = "probe"
msg = author_message(:self)
propagate(msg, :all)
enddef
// run for each TCP connection peer
// manages with its direct neighbours
def handle_message():
while(true):
recv(&msg, :peer)
if author(msg) == :self:
continue
endif
// updates network view
// by inspecting message
refresh_network_view(msg)
forward? = inspect(msg)
if forward?:
// so that network structure can be pictured
msg = append_hop(msg, :self)
propagate(msg, forward_to(msg))
endif
endwhile
enddef
For running simulation, I set up N-many libp2p nodes, each listening for
incoming connections while each also attempting to establish
connection with M-many randomly chosen peers, essentially
forming a dynamically synthesized nework topology.
During network forming step, each peer follows protocol i.e. announces
edge added message to its local neighbours, which is eventually propagated
throughout network, helping current network participants to learn of existence of
edge between a pair of nodes.
After network forming, one peer attempts to gauge network i.e. broadcasts
probe message to its neighbours, resulting into whole network learning
of message along with path trace, helping them to picture network structure.
In this step all current participants get a full picture of network.
To simulate link failure scenario, one randomly chosen connection
is dropped, which triggers edge removed message being broadcasted
to other neighbours still connected, from both of peers which just got disconnected.
By inspecting this message participants remove edge from graph which they
locally maintain as world view.
At the very end, randomly one connection is established, triggering propagation of
edge added message, letting peers update their world view, by adding new edge
in graph.
Randomly generated simulation setup has 7 nodes & 15 edges, where peer_1
probes, as a result of it everyone pictures whole world. This is how peer_1 sees
world around itself after running probing step.
Now I take a look at how peer_2 sees world around itself, after end of probing round.
And both of peer_1 & peer_2 find similar world view.
When I check remaining nodes world views, I find exact similarity.
I plot collected metrics i.e. data transferred over each edge ( read TCP connection ) for collaborative probing. I see some edges carrying more data compared to others due to presence of important vertices i.e. vertices having >= 3 edges, where they can have at max 6.
I trigger edge disconnection & let disconnection message get propagated throughout network. I find Peer 1 looses connection with Peer 4, so both of them must remove that edge from their local view of network --- which they do.
But interesting part is, does others also capture this change ? For checking that, I snapshot Peer 2's network view at this moment & it also captures change as expected.
During edge disconnection, some messages are passed around network, each edge's contribution
towards its network wide propagation is captured in following cost graph.
After a careful inspection, I see connection Peer 1 <-> Peer 4 & Peer 1 <-> Peer 3
doesn't anyhow contribute to forwarding of edge removed message, which is desired
behaviour because none of these edges exist in graph as of now.
Link between Peer 1 & Peer 4 just got failed, while Peer 1 & Peer 3 is going to
get connected in next step of simulation.
Finally it's time to simulate random connection establishment between a pair of peers. After edge added message passing has stabilised, I take a look at world view of Peer 1, finding existence of new edge between Peer 1 & Peer 3.
For understanding whether Peer 7 has learned of this change in topology, I snapshot its world view at this point of time. As expected all other peers who were not involved in connection establishment ( i.e. none of incident vertices ) has correctly learned change.
Cost analysis shows newly created edge i.e. Peer 1 <-> Peer 3 carrying edge addition message, while Peer 1 <-> Peer 4 doing nothing, because it doesn't exist anymore.
Results of simulation seem promising for dynamically adapting world view to network
state changes. Peers can even colloborate on when to probe, avoiding chances of
simultaneous probing, because if one peer starts probing, all will be benefitting from it.
I keep code used for simulating & generating these findings here.
I note few points for further exploration,
- Each process remembers whether certain {addition, deletion} message has been forwarded instead of using message itself for keeping track of it --- saves some bandwidth.
- Peers signing messages to cryptographically assert probe message indeed hopped through them.
- Using edge addition message to propagate peer address throughout network, allowing anyone interested to attempt connection with it.
- Using world view to take better routing decision.
- Dynamically graft edges forming faster path to distant vertex.
- Pruning edges to reduce duplicate paths --- reducing data transfer cost.