RF12 driver and ACKs « Jee Labs Talk

RF12 driver and ACKs

(15 posts) (5 voices)

Tags:

No tags yet.

kellerza

Hi, I'm trying to figure out how the ACK mechanism was intended to be used.

From digging around in the driver...

A frame sent to a specific node, requesting an ACK, contains the following in rf12hdr
- RF12HDRACK
- RF12HDRDST
- destinationID & RF12HDRMASK

When the destination receives the frame it has no way of knowing who the source was....

The only time the source is written into the rf12hdr is when RF12HDRDST is NOT set, but this is a broadcast to all nodes, and ACKing a broadcast is a bit of an overkill.

One option would be to hardcode the relationships (limiting), or inserting the sourceId in rf12data0].

Any suggestions would be appreciated.

Posted 29/12/2009 10:22:18
jcw

The ack mechanism is an experiment to find out with how little info one can get away with. It may need to be expanded.

As you point out, for broadcasts (sent to node 0), acks can't really be used (multiple acks would trip over each other). That's how I run my sensor networks here.

For packets sent to a single destination, it is up to the two nodes involved whether they need more information. In one-on-one exchanges, the receiver might not care what the ID of its peer is (or know it without being told). So yes, you can put the source id inside the data payload when needed. It's an application decision.

The ack part is the tricky bit. My initial thought was that acks always come right after a packet has been received, so broadcasting the ack back to everyone could work because only the node which just sent a packet would act on it. That requires all nodes to keep track of how long ago they ended transmission - something which isn't being done right now. It also puts a time limit on how quickly an ack must be sent.

There is another problem with acks right now. When they get lost, the originator may decide to re-send the packet. This means the same packet is received more than once. What the receiver should do is: ignore the packet, yet still send back an ack. But detecting duplicates can only be done if packets have a sequence number (well, at least 0 and 1). I haven't quite worked out the details, but my plan was to simplify the 3 header bits a bit (several combinations are not used) in an attempt to fit that extra sequence bit in.

For a receiver wich communicates with more than one node, sequence numbers are a bit more involved, because it has to track them for each originator. In the case of sequence bits, the receiver needs to remember 31 of them. It all looks very doable, but it isn't in there now. These bits are essentially used to decide whether a packet should be reported as new incoming data - either way, an ack needs to be sent if requested.

As you can see, this is really an attempt to make things as minimal as possible. I'm trying to keep the overhead down to a single byte, while still supporting robust packet communication. I think it can be done, but I have yet to work out the final details.

Again - maybe I'm trying to push this too far. Will look into this in the near future. It's an important step towards reliable communication.

Posted 29/12/2009 11:32:38

gotcha

Hi people. I am also interested in reliable data transfer. I got to this thread trying to send packets requesting acknowledge with the RF12demo sketch. Packets are arriving correctly but no ack is sent back by the receiver.

These are lines 665-670 of the mentioned sketch:

if ((rf12hdr & ~RF12HDRMASK) == RF12HDRACK &&

                    (config.nodeId & 0x20) == 0) {

                Serial.println(" -> ack");

                byte addr = rf12hdr & RF12HDRMASK;

                rf12sendStart(RF12HDRCTL | RF12HDRDST | addr, 0, 0);

            }
What I am observing is that the "-> ack" string is never printed. So the condition seems not to evaluate to true :
     (config.nodeId & 0x20) == 0)-> true, "collect mode" bit not set (BTW,any hint on what this mode is will be welcome, and #define NIDCOLLECTMODE 0x20 too ;-) )
     (rf12hdr & ~RF12HDRMASK) == RF12HDRACK -> always false: (rf12hdr & ~RF12HDRMASK) corresponds to the three upper bits CTL, DST, ACK. But both DST and ACK are set, so this evaluates to 0x60 instead of Ox20 (RF12HDRACK).
Am I missing something?
Then comes the ACK packet itself: it has the CTL bit set. This stands for "Control", I guess. What is the idea behind it? Is it specific to the easyPoll routines? Or is it intended to indicate that it is an ACK packet response in a more general aspect? Is it OK to have 0 length?
Anyway, I changed the "never true" expression to check if the ACK request bit was set:
(rf12hdr & RF12HDRACK) && (config.nodeId & 0x20) == 0)
Now I have the "-> ack" printed, but the Rf12SendStart seems not be working... rf12canSend seems not to be tested, so I added it. And when I did, it was it was false, even with a "while(!rf12canSend()) delay(1);" (This crashed the app, BTW)
I'll continue looking... but a little hint would be appreciated!
Thanks and happy New Year!

Posted 01/01/2010 18:45:04

gotcha

Of course! The answer was in the first post: the source address is NOT available at destination, except for broadcasts (the rf12sendStart function implemented in the RF12 library does it when the destination is 0!)

So in the acknowledge response statement at the receiving peer (line 669 of RF12demo), after my supermod attempt trying to force the ACK reply :

rf12sendStart(RF12HDRCTL | RF12HDRDST | addr, 0, 0); (as in version $Id: RF12demo.pde 4736 2009-12-14 11:37:43Z)

addr would be the receiving node address (it's own address!), except for broadcasts (Thanks, kellerza)

But why then make appear the "a" command in the help printout?

" ...,<nn> a - send data packet to node <nn>, with ack"

I think I got the anwser: it does set the ACK bit in the header, but, indeed, the receiving peer does not (and cannot) reply to the sending peer since it does not have his address.

I'll try to give a look to the problem... source address + simple sequence numbers (a mini sliding window protocol)

Thanks!

Posted 01/01/2010 22:36:13
kellerza

Suggested packet format:

first three bytes of rf12buf: packet in brackets with 'bits' inside

[CTL DST ACK DESTID5] [SEQ2 LEN6] [SEQ3 SRCID5]

- max length of packet data 62
- acks on same seq#, with ctrl bit set

The only bit I dont like is the two SEQ bits in the rf12len byte, which breaks compatibility with some other aspects of the driver.

For now I've adapted the driver to handle collision detection by buffering the last send.
Buffering is the first step for resends on no ACKs etc. I only added a one packet buffer for now, which seems to work well enough and simplify the sketches significantly.

I've added the calls to a class (more Arduino like). The new class uses Flash & Streaming libs from Mikal Hart

So using RF is as easy as:

[strong]Setup[/strong]

RF.begin(sourceId);

[strong]Loop[/strong]

RF.trysend();
if (RF.check()) {
RF.printPacket();
if (RF.isCmd(F("MyCMD"))) {
} else if (RF.isBroadcast()) {
} else {
}
RF.sendAck();
}

RF.sendBroadcast(msg, len);
RF.sendTo(msg, len);
RF.sendAck(destId, msg, len);

The seq numbers are not implemented yet, but first thing is to install two more JeeNodes today...
Will try to implement some more and share it on the wiki this week

Posted 02/01/2010 07:04:58
gotcha

Are you seeing this as another version of the current RF12 protocol or another layer on top of RF12? As an extension of the existing protocol, I would say that it should be agreed with Jean-Claude for future compatibility, but if you think it as another layer using the RF12 as a lower level protocol, it would be an independent protocol. What we should also consider are the services provided by this new protocol:

1. Connection oriented or unconnected
2. Reliable communications (retries, time to live (timeouts), acknowledges...)
3. Order preserving
4. Packet assembly and disassembly into the lower layers (LEN not limited by the RF12 protocol)(How? Good question!)
5. More???

This would be like an hybrid approach, complements the RF12 protocol and provides new services keeping a certain independence (of course this can be implemented gradually). Take a look:

[CTL DST ACK DESTID5][OPCODE3 SRCID5][SEQ][LEN][DATA]

Still more overhead! (1 byte for RF12, 3 bytes for your version and 4 in mine!!!)

Since RF12 protocol does not include the SRCID, we are obliged to put it here. It has the same format as the original hdr, but leaving behind the bitmapped functions of the first three bits. These bits are now an OPCODE (just like Jean-Claude suggested as a change for the RF12 hdr).

As you can see, LEN is a byte, so packets of upto 255 bytes payload could be passed, if the SEQ numbers are specially tailored:

SEQ
Bits 7-3: packet sequence
Bits 2-0: frame (sub packet sequence)

Some ideas for the OPCODE

OPCODE
000 Unsequenced packet - Not acknowledged (No SEQ byte at all)
001 Sequenced packet - Acknowledge needed
010 ACK packet #SEQ - LEN=0, no DATA
011 SYNC ?? (Connection)
100 CONTINUE ?? (Connection)
101 SYNC ACK ?? (Connection)
110 RESET ?? (Connection)
111

What do you think? Myself, I think it is a big work, specially for an Arduino with no timed interrupts (timers are all assigned), 30KB flash, 2KB RAM (the high end, not even think of an ATmega8!)... and specially because I have 8 hours programing experience in Arduinos!!!

BTW, nice libs you mentioned. IMHO, the Arduino libs is the way to go... Just one more comment: error handling + FIFOs. Application should be aware of what has happened with the communications... and for retry/pending TX/RX, FIFOs are a good solution, I'll write a little lib (I didn't find anything in the Arduino Playgroud)

Posted 02/01/2010 14:40:24

kellerza

gotcha, The main focus would be reliable packets: Couple of retries (up to 5, exponential backoff between sends), ack's, drop packets and resend ack's. Non-blocking sends for different nodes

> 1. Connection oriented or unconnected

    No connection orientation

> 2. Reliable communications (retries, time to live (timeouts), acknowledges...)

    The main focus, mentioned above

> 3. Order preserving

    Order is not important, but it is implied, sending..waiting,sending etc.

> 4. Packet assembly and disassembly into the lower layers

    At the moment I cant see the use for Long packets (resources, resources)

> 5. More???

    Simple routing (one hop retransmissions)
If we redesign the whole RF12 lib, the first three bits [CTL DST ACK] should be replaced with the an OPCODE concept, for now lets just build something on top of the rf12 library...
Current RF12 packet (2byte overhead):

    [CTL DST ACK DESTID5] [len] [data]

Reliable packet (3byte overhead):

    [CTL DST ACK DESTID5] [len] [seq3 sourceId] [data]
A good FIFO buffer would be a nice start. It would probably have to be instantiated for each destination node.
Some thoughts on the data structures and what needs to be stored to accomplish reliability
Packet Tx data that need to be stored: [dst, seq# &data]

Possible data structures:

  (1) Pure FIFO per dest node

  (2) Single FIFO with "look ahead functions" for other nodes (we don’t want one dead node delaying everything unnecessary)
Packet Rx data that need to be stored: [Seq# from sources]

  (1) Circular buffer per source, where you push Rx SEQs if ACKed, qiuck search to drop packets on driver level if seq exists and simply resend ack

  (2) Circular buffer storing SEQn&Source pair.

  (3) If we have 2^3=8 SEQ's we ould store each SEQ as a bit in a uint8t/char/byte, but how do you clear these?

  (4) Only store last SEQ from each node, if you receive a higher SEQ from same source, this must be a new packet and it means source received my ack
Leaning toward the last option in each case.
A unique SEQ number per dest node would simplify wrapping issues.. or a bigger (8bit) seq#
Thoughts?

Posted 04/01/2010 10:17:04

jcw

@gotcha - you can send an ack back even if you don't know who sent it: send the ack as broadcast, i.e. to node 0. The receiver of the ack (i.e. the originator of the original packet) will see who sent the ack, and can then decide to act on it or not. The trick here is that sending to node id 0 is treated as broadcast, and causes the driver to flip the header info to contain the origin id instead. So an packet sent to node X, will arrive with no origin info, but the broadcast of the ack will include "I'm an ack from X".

My hunch is that there is just enough info in this exchange to build a reliable mechanism on top. As I said before I may be pushing it a bit on the minimalism side - but I kinda like those kinds of challenges, because even if it fails I tend to learn a lot about core design issues.

@kellerza - great to see some new ideas on how to take this further. If we can advance this in such a way that a minimalistic bottom layer can support the new features you're describing as layer on top, then that would be great. There is still room to adjust things in the RF12 driver, since right now it only needs to remain compatible with itself at the other end(s).

I'll need more time (and brain cycles) to respond to the finer points of your proposals. Please don't let that keep you from moving forward.

Posted 04/01/2010 11:27:55
kellerza

@jcw - One problem with an "I'm an ack from X" is when Y and Z sends packets to X, X only receives packets from Y, but Z is happy with the broadcast ACK

What would make source & dest would be basic routing If I'm in the middle, say Z, and I see
X -> Y msg, but no ACK's, Z can do simple one hop routing
so,
X -> Y (msg, received by Z)
Z -> Y (payload from X's msg, masquerading as X)
Y -> X (ack, but maybe only received by Z)
Z -> X (ack, masquerading as Y just to be sure)

Posted 04/01/2010 12:13:21
jcw

I'm hoping that a rule such as "acks have to be sent within 1 ms after reception" can disambiguate this - but it needs some extra logic which isn't in there right now. This is what I alluded to in my first reply on this thread.

I know little about mesh logic, but the repeater-style approach you describe might be more complicated than that. What if Z doesn't see the ack from X to Y, but Y got it just fine? The extra ack would be ok, but unnecessary. There can be a lot of random dropout/interference with very local effects, I suspect. The other complication is that with repeaters, you need to allow more time for packets and acks to reach their destinations (and perhaps also larger sequence number ranges).

For very simple cases of trying to get a slightly larger range, I'd be inclined to build a simple real repeater: taking packets from one net group and re-sending them on another net-group (along with the acks). Might be easier to implement (though more limited). I've got one case like that in the house in fact - I'm not able to get through two reinforced concrete floors right now.

For more advanced long-range networks, meshing and TDMA might be better choices. Lots of trade-offs, as always... there's a reason why ZigBee stacks are so large: they need to incorporate a lot more logic.

Posted 04/01/2010 12:42:57
jcw

@gotcha - "collect mode" tells a node to respond to broadcast packets requesting an ack. There can be at most one. It's currently disabled by setting bit 5 to 1.

The RF12 driver is short on comments, and not yet well explained. Now that it has had a bit more real-world use, I'd like to revisit this code and come up with an improved version. Will probably coincide with fleshing out the header byte details, and getting enough machinery in place to support a reliable comms layer. Another factor will be the choice of I/O primitives this gets based on - I'm not sure the Arduino's digitalWrite() is the way to go, or at least not exclusively.

It will probably be necessary to re-examine every single bit used in each packet, to keep their overhead to an absolute minimum. Keep in mind that on the 868 ISM band, "normal" use is severely limited to 1% of the available bandwidth on average, which at 57600 baud translates to just a few dozen characters per second.

Posted 04/01/2010 17:02:59
phord

I'm very new to embedded RF networks in practice, but I've thought about them in theory for quite a while. I also have a lot of experience in the wired protocol world. So I could be wrong here for practical purposes, but...

1. I think the layered approach is nice. Keep the RF12 driver protocol as an independent layer from stream or reliability. In fact, you may want to split it into two layers already since ACK (and retrans) don't really belong to layer 2, traditionally.

2. Melding layers is ok, especially on an embedded platform where code and RAM are tiny. For example, the PHY layer is intrinsically part of the RF12 library (frequency, modulation, etc.) But don't overdo it. If something can be isolated to a specific layer without increasing code size or memory requirements, it's probably a good idea.

3. An application should be able to pick how lightweight his support code should be and not be penalized (in code size, for example) for capabilities he chooses not to use. Therefore, I think layers need more separation than they have now. The "Easy" functions deserve their own library, for example. For that matter, RX and TX could be isolated entirely since not all nodes will be receiving nodes.

4. I think your recent forays into templating could really help out here. If done carefully, the library could be tuned so that code specific to one operation mode might never appear in apps that don't use that mode (low-bandwidth 868MHz mode, for example).

I like your simple packet headers. Certainly more complex app requirements will necessitate larger headers. But let those headers be imposed only on those apps that will use them. Yet lower-layer levels need to supply (just) enough data to discriminate higher layer formats.

But maybe this is just me turning this thing into another Zigbee stack behemoth... I'll go back to thinking about it some more.

Posted 18/01/2010 03:24:30
jcw

Thanks for your comments, Phil. I try not to over-engineer things ;) - which in this case means: extend and reorg into more distinct pieces only as the need arises. Right now, the code size is in the range of 3 kb, and having everything included seems workable. As this gets used for more and more things, I agree that pulling it apart will become more effective.

Apart from templates, the other avenue I'd like to explore is to pull all the code needed for a specific app into a single file and then compile it. Static functions will then automatically get inlined where possible and dropped when unused. I.e. presenting the entire app as one source file gives the compiler the best shot at optimizing the whole kaboodle.

Posted 18/01/2010 09:49:34
phord

Yeah, I agree. As I was writing that, I was realizing just how complex it was going to get to support distinct layers. And 3k isn't bad. I'll see about building from there as needed.

I'm not sure how aggressively gcc implements the "inline" keyword, but it's possible to do that with an rf12 class (header) full of inlined code and see how it goes. I expect gcc does a good job with, actually.

Posted 18/01/2010 18:09:19
rubi

I found a quick and dirty solution, which works for me.
I send a counter byte with the data and on the receiver side I compare against an internal counter.
So I can analyse packet loss and could send an Nack if the missing data was important.

Posted 19/01/2010 18:33:12