Discussion: Reliable delivery


  • Mod

    @hek agreed. My change hard-codes the next hop to be 0 so in this particular case that's not a problem, but for a generic MySensor solution we need a better way. That's why we have no reliable way to send messages in a MySensors network. And it will likely stay that way for the foreseeable future, unfortunately 😞

    I'll do some reading and see if I can come up with something useful to discuss, to get the community started towards a mechanism for reliable delivery.

    EDIT: The original thread diverged into two discussions: one generic about reliable delivery and one about the specific case I was trying to solve. I have forked the topic and I think I managed to pull all relevant posts to this thread. Sorry for the inconvenience.


  • Mod

    @mfalkvidd I recently did some sniffing on a 1.5 network and experienced some ack-storms from the gateway. E.g. a client would send a single message, and the gateway would send all 15 ack's. The client did not get the ack (for whatever reason), and sends the message again. Gateway responds with 15 acks etc. etc. I experienced delays of many seconds because the node and gateway were chattering all the time. This tends to get funky with many nodes...

    Anyway, I thought it had to do with my setup (resend automatically when a message does not get ack'ed), but it would be interesting to see if others experience the same behavior.

    To get 'reliable' message delivery, we would need to buffer messages. At the nodes, repeaters and the gateway.
    I've been thinking about this for quite some time, because it's been at the top of my wish-list for ages.
    Still have to find the time to implement it...


  • Mod

    @Yveaux thanks for your input. Acks getting lost is something we'll have to handle. Exponential backoff is a method used in many protocols, so that might be a remedy. Some sort of book-keeping to determine which packet was ack'ed might be required as well.

    I don't think we necessarily need to buffer in all places though. It would be possible to only buffer at the sender node (which is what TCP does with a window size of 1 packet). We would then need an ack from the gateway (as opposed to an ack from the next hop), which means we can't use the hardware ack in the nrf radios.

    But as usual there are lots of compromises when selecting a design.

    There are lots of existing implementations of message control protocols. Some have had the benefit of large-scale deployment over a long time (like TCP). Some have been developed by research teams. Some have been designed especially for low-power nodes. I don't think we should invent something ourselves. Adopting an existing protocol (or a slight variant of it) should be possible.

    I would like to discuss the following:

    • Use cases. Real-world use cases are very helpful, both when discussing and explaining the design. I will try to collect use-cases that have already been discussed in the forum, but it would be great if everyone can post their use cases below.
    • Scope
      • What does reliable delivery mean? Does it mean at-most-once or at-least-once delivery?
      • To where is the delivery guaranteed (next hop, the destination node, the gateway, a controller, at least n controllers, etc)?
    • Who decides if reliable or best-effort message delivery is to be used? The internet protocol suite leaves the decision to the application (developer), which in our case might correspond to the sketch (developer).
    • Technical information
      • How much buffer space can we realistically assume will be available? Looking at how much ram the example sketches use might give a good clue to a reasonable default value for buffer size.
    • Do we develop something that is agnostic to the underlying communication protocol or do we utilize (or even require) features in the underlying protocol?
    • Which existing protocols would be useful to implement or adapt? - Anyone who knows of a protocol that be useful, please post below.

    imho, this is best discussed over a glass of beer/wine or two but I guess the forum will have to do 🙂


  • Mod

    @mfalkvidd said:

    It would be possible to only buffer at the sender node

    When communicating between sensor & gateway there are, IMHO, at least two sending nodes, as the messages from the gateway towards the sensor also have to be delivered reliably.

    which means we can't use the hardware ack in the nrf radios.

    No problem. I have the feeling it sometimes introduces more problems than it actually solves. Better have a good, portable (e.g. RFM69) implementation in MySensors, then something half-baked in hardware.

    Adopting an existing protocol (or a slight variant of it) should be possible.

    Totally agree!

    • Use cases

    Simple one in my case: assured delivery of a message from source to destination (whether it be gateway -> sensor or the other way around).

    • What does reliable delivery mean? Does it mean at-most-once or at-least-once delivery?

    I'd say exactly once. At most once is what we got now, at least once can hopefully be turned into exactly once quite easily.

    • To where is the delivery guaranteed (next hop, the destination node, the gateway, a controller, at least n controllers, etc)?

    Tricky one, but I'd say between the MySensors' network (excluding the controller as we don't have grip on it).

    • Who decides if reliable or best-effort message delivery is to be used? The internet protocol suite leaves the decision to the application (developer), which in our case might correspond to the sketch (developer).

    Currently, when sending messages, an ack is optional. This mechanism we can keep, or use e.g. compile-time selection.

    • How much buffer space can we realistically assume will be available? Looking at how much ram the example sketches use might give a good clue to a reasonable default value for buffer size.

    That seems like a good start. The size of the buffer could also be selected at compile time. For a simple sensor the amount of messages buffered can be limited, for a repeater or gateway in a large network the amount should be a lot bigger. This need not be a problem as these nodes can be based one of the supported platforms with more ram.

    • Do we develop something that is agnostic to the underlying communication protocol or do we utilize (or even require) features in the underlying protocol?

    No need to implemeng the complete OSI layering. I think we can implement reliable delivery with only a few fields added to the mysensors protocol.

    Which existing protocols would be useful to implement or adapt? - Anyone who knows of a protocol that be useful, please post below.

    And again, the RadioHead library pops into my mind 😉

    imho, this is best discussed over a glass of beer/wine or two but I guess the forum will have to do 🙂

    You're most welcome to come over -- beer's in the fridge, winecellar is open 👍


  • Mod

    It would be possible to only buffer at the sender node

    When communicating between sensor & gateway there are, IMHO, at least two sending nodes, as the messages from the gateway towards the sensor also have to be delivered reliably.

    Are there really two sending nodes? Or are there two messages, that each need to be delivered reliably, independent of each other? The latter case is tremendously easier to solve. TCP, for example, has independent acks for each direction (even though the acks can be piggybacked for higher efficiency but that's not the same thing).

    which means we can't use the hardware ack in the nrf radios.

    No problem. I have the feeling it sometimes introduces more problems than it actually solves. Better have a good, portable (e.g. RFM69) implementation in MySensors, then something half-baked in hardware.

    I agree. We will need to get this working over several different radio (or even wired) protocols anyway. And nothing would prevent adding protocol-dependent sub-layers later, if someone wants to.

    Simple one in my case: assured delivery of a message from source to destination (whether it be gateway -> sensor or the other way around).

    I would prefer something less generic. Generic is hard to discuss. What is a source? What is a destination? It is a good start though.

    • What does reliable delivery mean? Does it mean at-most-once or at-least-once delivery?

    I'd say exactly once. At most once is what we got now, at least once can hopefully be turned into exactly once quite easily.

    I'd be very happy if that is the case. More that half of the first page of search results on my google profile for the phrase "exactly once delivery" link to articles saying that it is not possible. But it would be awesome if it can be done.

    • To where is the delivery guaranteed (next hop, the destination node, the gateway, a controller, at least n controllers, etc)?

    Tricky one, but I'd say between the MySensors' network (excluding the controller as we don't have grip on it).

    I agree. MySensors takes responsibility up to and including the gateway. No less and no more. That's the way signing is handled (we don't require/support signing by the controller) and I think the same should apply to reliable delivery.

    • Who decides if reliable or best-effort message delivery is to be used? The internet protocol suite leaves the decision to the application (developer), which in our case might correspond to the sketch (developer).

    Currently, when sending messages, an ack is optional. This mechanism we can keep, or use e.g. compile-time selection.

    I agree. That means everyone can decide what they want when they write their sketch. Reliable delivery will have some consequences, and sometimes the sketch developer might prefer best-effort delivery so they don't need to deal with those consequences.

    • How much buffer space can we realistically assume will be available? Looking at how much ram the example sketches use might give a good clue to a reasonable default value for buffer size.

    That seems like a good start. The size of the buffer could also be selected at compile time. For a simple sensor the amount of messages buffered can be limited, for a repeater or gateway in a large network the amount should be a lot bigger. This need not be a problem as these nodes can be based one of the supported platforms with more ram.

    Compile-time (or even run-time?) could be great. I like the idea of recommending hardware with more memory for busy nodes/networks.

    Which existing protocols would be useful to implement or adapt? - Anyone who knows of a protocol that be useful, please post below.

    And again, the RadioHead library pops into my mind 😉

    Great. I'll check that out!

    imho, this is best discussed over a glass of beer/wine or two but I guess the forum will have to do 🙂

    You're most welcome to come over -- beer's in the fridge, winecellar is open 👍

    Very nice! I might take you up on that 🙂


  • Mod

    Alright. I have done some reading 🙂

    First, anyone interested in this discussion should probably read this thread where the protocol specification was discussed. Awesome work by @Yveaux @Zeph @ToSa @Damme and @hek !

    If there are any other references on the design decisions for the protocol, please let me know.

    Note: I use the term originating node in the text below. By that I mean a single MySensor node, a leaf node in the routing tree. (or the gateway if reliable messages are sent from the gateway to a MySensor node)

    After reading up on the radiohead rf library and a blog post about the protocol used for ulpnode, combined with my experience from the "internet" world, I realized one thing: There are two philosophies to reliable delivery, and we need to decide which one suits MySensors best.

    hop-to-hop acknowledgment
    As identified in the protocol thread, Radiohead uses a "hop-to-hop acknowledgment" philosophy. The way I see it (everyone is welcome to offer a different view on this) is that the world we live in when we want the "hop-to-hop acknowledgment" looks like this:

    • End nodes are considered extremely low power. They have little memory and/or need to conserve power
    • End nodes want to get rid of the responsibility of a message as soon as possible. Either because they want to go back to sleep, or because they don't have enough memory to buffer messages.

    This puts very high reliability requirements on all relay nodes. If the originating node has gotten an ack, the node that sent the ack is 100% responsible for making sure the message is delivered. Since the originating node might have gone back to sleep, there is no way to let the originating node know if something bad happens. So all relay nodes MUST be able to buffer a lot of messages, maybe not indefinitely but at least for a reasonable long time. The originating node wanted reliable delivery after all, so the relay node(s) really need to make sure the message is delivered. If the message wasn't important, the originating node would not have chosen the reliable delivery mechanism.

    end-to-end acknowledgment
    The most widely used protocol on Internet, TCP, uses a "end-to-end acknowledgment" philosophy. Routers (Internet's equivalent of MySensors' repeat nodes) can (and do) drop packets at any time. They are not responsible for buffering. In fact, buffering leads to worse performance in the network. The philosophy is that the originating node is the node that is most interested in getting the message delivered, and that node is also best equipped to make decisions on timeouts and re-transmission.

    This philosophy also assumes that originating nodes are likely to be less busy than repeat nodes. My come computer does a lot less packet sending than the central routers on the Internet. The originating node might only be having a single conversation, and keeping a single message in memory is no problem: the node needs to have that message in memory anyway to call the send function.

    .

    Does this make sense? If so, which of the philosophies are more suitable when implementing reliable delivery in MySensors?

    The current implementation is sort of "hop-to-hop acknowledgment". But MySensors does not offer high reliability on repeat nodes. As far as I understand, repeat nodes will not buffer and re-transmit messages, even though they have said "Don't worry little guy, I'll take care of this message and deliver it reliably" to the originating node. If the message fails later, the failure will not be detected.

    I don't mean to complain about the current implementation. There were probably lots of design choices that I am not aware of, and what we have is awesome. I just think that we can do better when it comes to reliable delivery.

    Sorry about the long post.


  • Admin

    Good summary @mfalkvidd.

    There is actually another looong thread that should give you more perspective/history here:
    http://forum.mysensors.org/topic/304/2-0-discussion-units-sensor-types-and-protocol
    It's not been realised.

    Just a note. The bool you're getting from send() was never meant to be used for detecting if a message was delivered to its final destination. It's merely exposes the "hardware" acking result from the NRF-module. So, it's an indication if the node is totally off the grid.


  • Mod

    Thanks @hek! Now I have something to read before I go to sleep tonight 🙂


  • Mod

    I have collected some real-world use cases and read the protocol design discussions in the forum. There is something I don't understand though:

    What is the difference between hardware and software ack, and difference between the ack in present/sendSketchInfo/send/sendBatteryLevel/, mSetRequestAck and isAck() in incoming messages.
    I have read these posts but I'm unable to figure out how the library is designed.
    http://forum.mysensors.org/topic/1163/can-anyone-shed-some-clarity-in-this-ack-business-hek/4
    http://forum.mysensors.org/topic/649/rc-from-send-and-how-to-identify-an-ack-message/7

    From @hek's response in the first thread, it looks like the library is designed to support BOTH end-to-end acknowledgment and hop-to-hop acknowledgment, but how to use that isn't very clear, at least not to me. Could anyone care to explain?


  • Admin

    Low-level: When a node wants end-to-end ack, it sets a bit in the message header "req ack". The node that receives this type of message, sends an ack-message with the "req ack" bit off and "is ack" bit on. Otherwise messages would create a endless loop.

    The "hardware ack" functionality is only used to detect if a node loses connection with it's closest neighbor.. and should start looking for a new parent.


  • Mod

    I think I'm most confused by this statement:

    @hek said

    It will first send the hardware ack and then the end-to-end software ack provided by the MySensors library.

    What is the end-to-end software ack? Was it never implemented?


  • Mod

    ok, let's see if I understand now. How much of this is correct?

    Hardware ack is what I get when using send(msg, true) and some other functions like present, sendSketchInfo and sendBatteryLevel

    • Hardware ack is hop-to-hop acknowledgment
    • Sending is a blocking function which returns true if an ack was received and false if ~70ms passed without receiving an hardware ack.
    • Sending ack is handled automatically by the library(/radio)
    • Receiving an ack is handled automatically by the library
    • Re-send needs to be handled manually in each sketch (a while-loop with a counter counting up to maxRetries and using wait() between each resend seems to be the most common solution)

    Software ack is what I get when setting msg.mSetRequestAck before sending the message (is this true? I'm unable to find any documentation on mSetRequestAck on http://www.mysensors.org/download/sensor_api_15)

    • Software ack is end-to-end acknowledgment
    • Sending is a non-blocking function (from the software ack perspective, using hardware ack together with software ack is allowed and in that case the rules for hardware ack applies to hardware ack but the call is not blocked until the software ack comes through)
    • Sending an ack needs to be handled manually in each sketch (by checking msg.mGetRequestAck in incomingMessage? I'm unable to find any documentation on mSetRequestAck on http://www.mysensors.org/download/sensor_api_15 )
    • Re-send needs to be handled manually in each sketch (setting up a timer might be a good solution)
    • Receiving an ack needs to be handled manually in each sketch (by checking msg.isAck() in incomingMessage and clearing the timer mentioned above)

  • Admin

    Nope,

    Hardware ack is always enabled in the MySensors library (except for broadcast messages).

    End-to-end ack is enabled with the true flag.


  • Mod

    But then end-to-end ack is horribly broken? Since the next hop node will respond with an ack even if it is a repeater?


  • Admin

    No, only the findal destination node will answer with a soft ack message.

    Note, the (soft) ack message has to be picked up by yourself in your incomingMessage function.


  • Admin

    You can look at the RelayWithButton example on how to use it.
    https://github.com/mysensors/Arduino/blob/development/libraries/MySensors/examples/RelayWithButtonActuator/RelayWithButtonActuator.ino

    Here the node sends a message with soft ack enabled when someone presses the button. It doesn't change the local (light) state until ack message is received.


  • Mod

    @hek said:

    No, only the findal destination node will answer with a soft ack message.

    Note, the (soft) ack message has to be picked up by yourself in your incomingMessage function.

    Thanks for explaining. Just checking if my understanding is correct:

    bool send(MyMessage &msg, bool ack);
    

    will return the result of the hardware ack, regardless if the second parameter is true or false?

    So my post above should have been like this:

    Hardware ack is always on

    • Hardware ack is hop-to-hop acknowledgment
    • Sending is a blocking function which returns true if an hardware ack was received, and false if ~70ms passed without receiving an hardware ack.
    • Sending hardware ack (when the message has reached the next-hop node) is handled automatically by the library(/radio)
    • Receiving an hardware ack is handled automatically by the library, by setting the return value from the send call mentioned above
    • Up to 15 tries are made automatically by the library. Further re-send needs to be handled manually in each sketch (a while-loop with a counter counting up to maxRetries and using wait() between each resend seems to be the most common solution)

    Software ack is what I get when using send(msg, true) (and is also supported by some other functions like present(), sendSketchInfo() and sendBatteryLevel()

    • Software ack is end-to-end acknowledgment
    • Sending is a non-blocking function
    • Sending ack (when the message has reached its final destination) is handled automatically by the library
    • Re-send needs to be handled manually in each sketch (setting up a timer when sending the original message might be a good solution)
    • Receiving an ack needs to be handled manually in each sketch (by checking msg.isAck() in incomingMessage and clearing the timer mentioned above)

  • Admin

    Yes! Looks correct!

    If you want to dig even deeper you can tune the hardware ack/message burst handled by the radio here:
    https://github.com/mysensors/Arduino/blob/development/libraries/MySensors/core/MyTransportNRF24.cpp#L59

    The radio sends a burst of maximum 15 messages (with a 5us interval) by itself unless it picks up a respond by the other node.


  • Mod

    Very cool! Thanks a lot @hek! Can't believe I have read several hundred forum posts about the protocol design and ack problems the last two weeks without realizing that what I needed was already included in the library.

    From the discussions I've read it looks like almost no-one else has understood either.

    Some ideas to help people understand how to use the built-in features for reliable delivery:

    1. Add an example that has a complete implementation of end-to-end ack usage. This includes
    • setting up timer(s) for re-sending
    • storing sent messages so they can be re-sent
    • determining which message was acked when an ack message is received (there might be several messages that haven't been acked yet)
    • removing acked message from the sent message store and clearing the timer(s)
    • re-sending when the timers expire
    1. Update the documentation for bool send(MyMessage &msg, bool ack); (and similar functions) to explain that the bool returned is the result of the next-hop ack.
    2. Rename the bool ack parameter to bool end-to-end-ack or something similar to make it clear(er) that there are two types of acks
    3. In the documentation for send() (and similar functions), refer to the example in (1) for information on how to use end-to-end ack.
    4. When the example in (1) is good enough, add some of the required code to the MySensors library so people don't need to copy-paste a lot of code into their sketches. Surround the code with ifdefs to make it optional.

    (2) and (3) should be quite easy to do. Can it be done with a pull request or how are documentation improvements handled?

    I'm willing to do 1 (will post the sketch in the forum for public scrutiny/feedback of course).

    4 can be done when the community think the example is "good enough"

    5 can wait until the example has been thoroughly vetted.


  • Admin

    Sounds like a plan.

    The code documentation could be solved with a PR as you say. But the main site isn't available on github (a messy thing) so I have to update that part when PR arrives/has been merged.


Log in to reply
 

394
Online

6.7k
Users

7.6k
Topics

80.3k
Posts

Looks like your connection to MySensors Forum was lost, please wait while we try to reconnect.