ECHO Protocol possible improvement?

#1

Reading the whitepaper on the ECHO protocol was thoroughly informative and was a nice read, thank you so much. I have thought of something that might be an improvement to the ECHO Protocol and would like your thoughts. Forget exactly how I came across the whitepaper.

Each broadcast packet is initial marked as Pruned Flood (PF), and if a timer has expired it is converted to a Full Flood (FF) packet to reach the largest amount of nodes possible. These FF packets helps to determine critical nodes (CN), based on a node receiving an echo of which they were the previous-sender. After, that for a set period of time all broadcast packets transmitted are only transmitted by CN. As for the improvement, if these CN are connected to power and are also operating in relay mode, would it possible for them to periodically send PF broadcast of which only the CN echo to determine their status to remain classified as a CN. Believe this would help in at least two ways;

  1. In scenarios, such as Mammoth mountain where there are powered stationary nodes, there would less of a need for initial FF packets, because you could assume that if CN nodes continue to talk with each other, that area is covered.
  2. Even thought there is the occasional transmission from the CNs, the amount of transmitted packet would go down because there is less need for FF in said area.

Thoughts?

1 Like
#2

Thanks @toadico for your interest in the paper and the insightful question. Before I answer I would like to restate your question to make sure I got it right.

“Instead of having a Full Flood, can we use Pruned Floods themselves to determine whether a Critical Node should remain critical or not, either using CN-originated PFs or by forcing CNs to originate such PFs if they are pure relays”

Also, in your question you said “send PF broadcast of which only the CN echo”. By “echo” here I am assuming you mean the CNs retransmit and also execute the ECHO protocol of “become a CN if I hear a packet with myself as previous sender else not”.

Assuming I got it right, let me proceed. In general, the answer is no, this won’t work because a CN may not get an “echo” (prevSender == me) if only CNs retransmit, and hence a CN may “resign” when it shouldn’t. Take for example the network in Figure 2 of the paper (I’m assuming you’re reading the 6-7 page paper entitled “ECHO: Efficient Zero Control….”). Refer to the rightmost picture where A and C are CNs. Now suppose A generates such a special “maintenance” PF, or uses its naturally originated PF message. C gets it and retransmits, A gets that packet and sees itself in prevSender and remains critical. Working so far! But then C retransmits and doesn’t get an “echo” from A (because A is done transmitting), or from B, C or F (they are not critical). So then C marks itself non-critical, which means F would never get any of packets originated by A, B, E or D.

In general, a node cannot mark itself non-critical unless it is certain nobody depends on that node to relay others’ packets. That certainty requires all nodes to retransmit, implying Full Flood.

At a higher level, the question of whether we can reduce overhead in some specific situations like Mammoth mountain is valid. ECHO was designed for mobile networks, but if we have a stationary relay backbone like in Mammoth mountain, one could perhaps increase the FF period by an order of magnitude or more to cut down on FF overhead (since it is very likely the topology won’t change). We have also considered ideas where a node would, between two FF periods – detect if there was a topology change and take appropriate action, but so far we have preferred to keep things simple.

Thanks again for your question, and do let us know if you have any other questions.

Ram

3 Likes
#3

Thank you for the great explanation, understand exactly what you are talking about and why it would not work. And you understood my thought perfectly.

Kelly

1 Like