Pages: [1]   Go Down
Author Topic: Choosing a packet terminator, what do you use?  (Read 947 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 18
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I am currently making a reliable network protocol for communication between an Arduino Uno and a controlling computer. The protocol works by appending a 6 byte header to every packet. The header contains the total length of the packet, a CRC checksum for the actual data and a sequence number for the packet. To be able to distinguish packets from each other I was thinking about adding some kind of packet terminator symbol to each packet.

My first though was just to use some character, eg. '#', which does not appear in the data very often or at all. The problem with this approach is that I want to send arbitrary data across the connection. The '#' sign equals to the decimal 35. If I send a packet whose length is 35, then I'm screwed, since the protocol will think that the package ends immediately.

Another approach would be to use a pattern, eg. four bytes with value zero or something like that, and append this to each packet. It is highly unlikely that something like this would ever appear in the data. However, this hardly seems efficient. What other options are there?

Thanks!
Logged

nr Bundaberg, Australia
Offline Offline
Tesla Member
***
Karma: 129
Posts: 8583
Scattered showers my arse -- Noah, 2348BC.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
'#', which does not appear in the data very often
"very often" doesn't cut it I'm afraid.

If you have a length, CRC (16 bit?) and a sequence number frankly I think you've pretty much got the makings of a reliable protocol. That's almost exactly what I'm using in my current design and FWIW I'm well satisfied it will be robust.

Maybe we should collaborate.

______
Rob
Logged

Rob Gray aka the GRAYnomad www.robgray.com

Offline Offline
Newbie
*
Karma: 0
Posts: 18
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

My CRC is 8-bit atm. Yeah, I should be allright with the length and CRC, but I would really like to add a terminator anyway. Then I could read bytes into a buffer until I encounter the terminator, and only then start treating the data as a package, doing CRC checks etc. The sequence number is mainly used for sending acks back to the sender, and I don't see how it helps me here. How do you use it?

If I end up not using a terminator I am worried the following might happen:

1. Read a packet into memory. The first byte (length) could be used to determine how many bytes to read.
2. Do CRC checks on the data.
3. Determine that the package was not okay and discard it.
4. Start again.

What happens at point 4 now? Since the previous packet was erronous, I guess the next one could be as well. Then, reading the number of bytes that is contained in the serial buffer next and using that as the length for the next packet could be a very bad idea. The value might be something else completely, and sooner or later I am completely out of sync with where the packets start and end. The terminator would be used to sync the reading back to the start of a packet after a failure. Something like:

1. Read the until we encounter a terminator
2. Check that the amount of bytes read equal the value of the first byte (first change to bail out if not correct)
3. Do CRC checks (second chance to bail out)
4. Start again.

In this manner we can be quite (but not completely of course) sure that we start reading at the beginning of a packet and stop at the end.

Thoughts?
« Last Edit: September 21, 2011, 05:01:33 am by unvestigate » Logged

nr Bundaberg, Australia
Offline Offline
Tesla Member
***
Karma: 129
Posts: 8583
Scattered showers my arse -- Noah, 2348BC.
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
What happens at point 4 now?
You have to resynch...somehow.

If your data is binary I see no really valid method of resynching with the data stream using any combination of terminator values. This is one good thing (the only good thing IMO) of using ASCII-only data.

In my case the sequence number is just another check. I recently dropped it BTW but it's still on the cards.

The fundamental problem is resynching with the data stream. I do this (caveat, untested just designed) by waiting for an idle line of 16 bit times that indicates an inter-frame break. The timing is very important though and in fact I have a dedicated processor to handle the low level interface.

I assume that you are doing a multi-drop protocol otherwise you wouldn't be having these issues.

I have spent a lot of time designing such a protocol to be used as a robust "commercial grade" protocol and just recently dropped it for a point-to-point ring topology because of perceived (by me that is) reliability issues.

What's you application and how robust does it have to be?

______
Rob

 
Logged

Rob Gray aka the GRAYnomad www.robgray.com

Seattle, WA USA
Offline Offline
Brattain Member
*****
Karma: 630
Posts: 49998
Seattle, WA USA
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Typically, one uses start and end of packet markers, with some delimiter between the length and the data. If you receive

"<xx:SomeDataGoesHere:Checksum><xx:MoreData:Checksum><xx:AnotherPacket:Checksum>"

you can determine where a packet starts ("<"), how many bytes (xx) are to be in the packet, then you should see a known value (":"), then xx bytes, then another known value (":"), followed by a checksum, followed by another known value (">").

If the :Checksum> part (known value, unknown value, known value) appears before xx bytes have been read, then you know data was lost. If the checksum is what is lost, you know that, too, because the known values are not in the correct location relative to the start of packet marker. Determining if it is the length byte that got lost is a bit tougher. If the valid packet length is always less than the ascii code for the delimiter, life is easier.

Having a maximum packet length, and known start and end markers, one can locate the start and end of a packet in an otherwise unknown stream of data, with a relatively high degree of certainty.
Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 18
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

As I said in my earlier post ( http://arduino.cc/forum/index.php/topic,72785.0.html ) I'm writing a communications protocol for a submarine ROV. We are planning to run three on-board arduinos, each with their own serial connections to the controlling computer, and a webcam on a single USB connection which is running on an RJ45 cable. The USB extender I am using claims to be able to handle up to 60 metre cables, but we'll see.

I don't know what a multi-drop protocol is smiley I am in fact not very expecienced when it comes to network programming. My system basically sends a packet and waits for an ack to be sent back for that packet. This is what the sequence number is for. The packet is buffered on the sending side until an ack is sent back. The packet is resent a number of times and eventually dropped if no ack is every received. Also, on the receiving side, the sequence numbers for the most recent packets are buffered, so that no packets are processed twice if the ack is dropped or garbled.

I'm sticking to binary data right now. I might try using a multi byte packet terminator, I just have to be smart about selecting a byte pattern that never occurs within the actual packet. Since the protocol is only designed for the ROV project right now, finding such a pattern should not be that big of a problem.

EDIT: PaulS, that is all fine but it does not work with binary data.
« Last Edit: September 21, 2011, 05:36:31 am by unvestigate » Logged

Leighton Buzzard, UK
Offline Offline
Edison Member
*
Karma: 21
Posts: 1339
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

typically if you want to use a byte as a terminator, you have to "escape" that byte if it appears in data
so, for example, if you wanted to use # as a terminator, wherever # appears you have to fix it
if it's in the data you might use "/h" to mean #
(cost penalty here is one extra byte)

but then you have to escape "/" as well
so you use "//"
(cost penalty here is one extra byte)

if it's in the packet length, easiest fix is simply disallow a packet of 35 (as i recall), pad it with a null to make it 36!
(cost penalty here is one extra byte)

or use a terminator that is always well beyond the maximum packet size
0xAA is tempting
(no real cost penalty as you decided you wanted a terminator!)

but if your protocol already has a packet size and checksum
you'll not gain much by adding a terminator
remember - the terminator may go AWOL as well!

it's worth getting the remote end to ACK (acknowledge) each packet, with the last good packet ID received
you then then use that with a timeout
so if you send packet 25, get ACK 25 - good stuff
if you send packet 25 get ACK 24, you know 25 fell off the carrier pigeon, so resend it

HTH
Logged

there are only 10 types of people
them that understands binary
and them that doesn't

Offline Offline
Newbie
*
Karma: 0
Posts: 18
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks mmcp42, I actually misread your post at first, and thought you suggested always sending packets of a fixed size. This is something that I had not thought of, and I might try it.

For example, my header is 6 bytes long. Currently I allow 16 bytes of data. After that I could have a two byte terminator. If the data is not 16 bytes long, I just pad it with zeroes. That would make 6 + 16 + 2 = 24 byte packets. This should make it easier to look for the terminator, and I can use any two bytes for it. The length byte in the header gets kind of redundant in this scenario. Maybe I'll get rid of it...

I know that the terminator might get lost, and as I said I am using ACKs. That escaping technique is pretty much what I had in mind when I said "terminator byte pattern", but yeah, the principal is the same.
Logged

UK, Southwest
Offline Offline
Full Member
***
Karma: 5
Posts: 138
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

PaulS said:
Quote
Typically, one uses start and end of packet markers, with some delimiter between the length and the data. If you receive

"<xx:SomeDataGoesHere:Checksum><xx:MoreData:Checksum><xx:AnotherPacket:Checksum>"

you can determine where a packet starts ("<"), how many bytes (xx) are to be in the packet, then you should see a known value (":"), then xx bytes, then another known value (":"), followed by a checksum, followed by another known value (">").

If the :Checksum> part (known value, unknown value, known value) appears before xx bytes have been read, then you know data was lost. If the checksum is what is lost, you know that, too, because the known values are not in the correct location relative to the start of packet marker. Determining if it is the length byte that got lost is a bit tougher. If the valid packet length is always less than the ascii code for the delimiter, life is easier.

Having a maximum packet length, and known start and end markers, one can locate the start and end of a packet in an otherwise unknown stream of data, with a relatively high degree of certainty.

I'm doing nearly the same thing, but I don't see what the : gives you.  In my case the protocol is mostly for integrity, i.e. did the correct device send the packet of data, so the protocol includes an extra identifier. In the event of a detected error all I want to do is discard the data.

If the (correct) CRC has not appeared by the time the length has been read, the packet is corrupted.
If the final delimiter has not appeared within a specific time, the packet is corrupted (allows for line breaks, allows a restart)
If the start delimiter has not appeared, discard data until it does.
If a start has been missed, and the data contains with another start, then the length and checksum are still not going to be right.

I'm using a CCITT CRC32,  modified to calculate the CRC one byte at a time.
Logged

Pages: [1]   Go Up
Jump to: