Improving design of a point-to-point layer on top of a byte-oriented protocol [closed]

Question

I want to design a very simple, efficient protocol layer, point-to-point, that uses a UART on a low-end 8-bit microprocessor. It has extremely limited RAM, and only the most simple arithmetic operations. The UART handles framing of bytes, and it can be assumed that this layer can rely on this fact. (error detection will be done on a higher level).

The protocol would work as follows:

• Server and client are indistinguishable
• Receiving and transmission are done completely independently (so only one-way need be considered)
• Connectionless and unreliable (a frame/packet will be sent-and-forgotten)
• A frame/packet will be delimited with a start, so requiring as little RAM as possible (in the order of a few bytes) while detecting the start of a frame.
• A frame/packet will be delimited with an end, to distinguish between 1. a delay in reception of the next byte and 2. the end of the frame/packet.

My first idea was as follows:

• The start of a frame consists of a byte: 00xxxxxx (where x can be used for specifying the type of frame for the higher level)
• The end of a frame consists of a byte: 11xxxxxx (where x is discarded)
• The frame contains any number of content bytes: 01xxxxxx (where x is content)

This would mean the microprocessor literally doesn't need any RAM whatsoever while waiting for the start of a frame; it only has to check each byte as it's received to see if it matches 00xxxxxx.

The problem with this idea is obviously it's wasteful of bandwidth: 2 of every 8 bits (plus the whole of the end-delimiting byte).

My second, flawed idea was to do something similar with, say, two bytes instead of one. For example:

• The start of a frame consists of one byte as above: 00xxxxxx
• The end of a frame would also be one byte also as above: 11xxxxxx
• The content would be in pairs of bytes: 01xxxxxx, xxxxxxxx

But this is flawed because the second byte of a content byte-pair could be confused with either a start or an end delimiter. The UARTs could be disconnected and reconnected at any time without warning, so there needs to be a way for this layer to find the beginning of a packet through the values of bytes.

My logic is failing - I can't see a way of improving on my first version. I've been reading up on loads of different protocols and I can't find any that I could adapt, let alone use as-is. Is my second idea fatally flawed? Or have I just not realised how a start delimiter could be distinguished from that of the second content byte, without storing too much in RAM?

Any ideas welcome, including protocols that I could adapt or adopt, or changes to the above ideas.

---

Response to comments

UDP seems very much like overkill, and is too high level. I certainly don't need addressing (ports or otherwise). I don't think the OSI model can be applied to my requirements, but I need something more at the data link layer rather than transport later (UDP). It will be (a part of a re-usable stack) for communication between a host (usually a PC) and a microprocessor (PIC, Atmel) via a virtual COM (serial) port (Using bluetooth-UART or USB-UART hardware bridges). It will by no means be a one-size-fits-all protocol, but just something which suits very limited hardware capabilities for tasks such as sending key+value pairs, or command+parameters etc, where the values/parameters will be of variable length, anywhere from 0 to over 2^16 (but could be split up). Some protocols that come close but are also overkill:

• High-Level Data Link Control
• AMP - Asynchronous Messaging Protocol

The greatest priority is low computational requirements and resources, followed by bandwidth efficiency.

The microprocessors will invariably either use data as it's being received, or send data as it's acquired, which is why they won't have much RAM. They might also do real-time processing so the less they need to manipulate data for transmission/reception, the better. The reason low end microprocessors are being used is because there will be a lot of them, and costs will need to be kept down.

Answer 1

Idea 1: ASCII

See this question on SE for using ASCII control characters

Idea 2

That article on HLDC gave me this simple idea which uses one byte for start delimiting, one for end delimiting, and one for escaping data within the packet:

• Start byte: 0x00 (8-bit hex notation)
• Escape byte: 0x01
• End byte: 0x02

So a packet will always start with 0x00 and end with 0x02. Bytes within that will only be escaped if they match 0x00, 0x02 or 0x03. Escaping is done by preceding that byte with 0x01. For randomly distributed values of data, this means the protocol's overhead in bytes, per frame, is this:

1 + 3n/256 + 1 

Where n is the number of data bytes. (This is more attractive than the first example in my question which had waste of 1/4 + n/4 + 1)

If processed in the same way as the first idea in my question, the amount of RAM bytes required would be just 1.

I also considered doing something similar but with two bytes:

Start: 0x0000 Escape: 0x0101 End: 0x0202

The RAM required would be 3 bytes, and the protocol overhead would be:

2 + 6n/2^16 + 2

One last idea was to deal with sequences of nibbles (4 bits) but it was barely more bandwidth-efficient than the first example in my question, and quite a bit higher in computations, so not worth mentioning.)

So between those two options I now have a lot of versatility (I will be choosing the one-byte version if anyone cares!). I've ordered some books on Data-Link layers so will add any further ideas.

I'd still appreciate any other ideas anyone comes up with

Answer 2

You may use the following protocol (inspired by PPP over Asynchronous Links RFC), with two special characters IDLE and ESC. You will need about 2 bytes of RAM at the Transmitter and 2 bytes at the Receiver to maintain state information (plus two more bytes for CRC computation). Payload data are arbitrary, from 0x00 to 0xFF.

Say IDLE is 0x7E, ESC (for Escape) is 0x7D.
IDLEs MAY be sent by Transmitter at any time when it has no payload data to Transmit.
When Transmitter wants to send a frame/packet, it MUST send IDLE, then the escaped (see below) payload data, then IDLE.

As IDLE should not appear in frame data, we define a second special character ESC that will be used by Transmitter when it wants to escape data. IDLE and ESC itself will be escaped, at a minimum.

When the Transmitter wants to send payload byte:
- 0x7E (IDLE), it transmits two bytes: ESC followed by (IDLE ^ 0x40) [IDLE XOR 0x40]
- 0x7D (ESC), it transmits two bytes: ESC followed by (ESC ^ 0x40)
- other byte, it transmits the byte unchanged. Alternatively this byte MAY be escaped by ESC followed by (byte ^ 0x40), provided that (byte ^ 0x40) does not result in IDLE or ESC.

The escaping formula (byte ^ 0x40) is not magic, it can be replaced by another. The important thing if that the result of the escaping formula is never ESC or IDLE.

From the Receiver point of view, any data received between two IDLE makes a frame/packet. Receiver has to unESCape these data in order to get the initial payload data.

It is of course strongly advised to add a (2-byte) CRC at the end of the frame/packet, just before the closing IDLE. This CRC has also to be ESCaped. CRC can be computed on-the fly, on a byte-by-byte basis.

I have implemented this kind of protocol (precisely: encapsulation) numerous times, it's very simple, reliable and efficient.