EMPT -- Embedded Message Transport Protocol

Description

EMTP (Embedded Message Transport Protocol) is a protocol targeted towards message exchanges between a small "device" (or embedded system) (e.g. Arduino) and a controlling "computer". The emphasis is on "device", i.e. device with limited computing power (a few MHz) and memory (a few KB) and lacking a networking stack, and "computer", i.e. plug-computer, laptop, desktop, etc., with average or above computing power (at least a few hundred MHz) and memory (at lest a few hundred MB), both linked usually through a serial, RS-232-like, connection.

The main targeted usage of this protocol is control messages, and not data shoveling, where some small latency and small overhead is not an issue, assumptions which are reflected throughout the design.

Thus the terminology for the rest of this proposal is:

• "device" -- an embedded system;
• "controller" -- the computer to which the device is connected;
• "frame", "packet" and "message" are similar as in the OSI terminology;
• "must", "should", etc., are similar as in any RFC terminology;

Data link protocol

The main targeted data link protocol is something resembling a byte stream, for example a serial connection (in the RS-232 sense), which has the following properties:

• point-to-point between the two devices, already configured and ready to be used; thus the proposed solution does not handle connection setup or addressing;
• full-duplex (i.e. the transmit and receive flows are unsynchronized to each other, and can be used concurrently);
• the "atomic" exchange unit is a byte, and any of the 256 values are allowed to appear in the stream;
• ordered (i.e. if two bytes are sent one after another, then if they are received they must arrive in the same order);
• unreliable in the sense that sent bytes could be lost (due to flaky connectivity, etc.), or maybe extra bytes appear interleaved in the data stream (due to signal noise, etc.);

As such each exchanged packet is embedded into a simple HDLC-like frame, with the observation that the prologue and epilogue bytes are not excluded as valid bytes in the packet. This also implies that the frame parsing is strongly tied to the packet parsing. However the two prologue and epilogue bytes could be used to try to re-synchronize the stream in case of decoding errors.

Of course other data link solutions, like Ethernet, can easily fill the role described above, with only trivial adaptations to the proposed framing.

Transport protocol

The exposed services to the "application" (either the embedded code or the control application) are very similar to the ZeroMQ library, and it's ZMTP protocol, that is:

• the application is allowed to send and receive messages, with any desired exchange pattern;
• a message is composed from one or multiple parts, each having an arbitrary binary contents;

Flow control

Because the device has limited capabilities, the controller must be throttled not to overburden the device, thus a flow control mechanism is needed. It must be noted that the memory is considered scarcely limited, but not the processing power, thus it is assumed that the device is always able to process protocol related messages (like ping).

Regarding flow control solutions, there are a number of possibilities each with advantages and disadvantages:

• out-of-band or hardware flow control (like RS-232 RTS/CTS), which, although the best option, is unavailable in most current small embedded devices (or USB serial adapters);
• TCP-like window based flow control, which is non-trivial to implement and assumes larger buffers;
• in-band software flow control (like RS-232 XON/XOFF), which seems to be better suited for the targeted context;

Thus the employed solution is based on special packets being exchanged, mandating that the controller must ask permission to send further messages, and the device explicitly permitting them.

On the other hand, the mechanism is asymmetric, that is the device can send messages at will, because the controller is most likely hundreds of times more powerful than the embedded device.

Also the flow control applies only to packets which imply memory consumption, and not to others (like ping) which can be handled immediately.

Moreover the device can impose limits on what the controller is able to send to it (see the limitations structure):

• max-part-count -- how many parts can a message have;

• max-buffer-size -- how large is the receive buffer on the device, which should translate as:

  • in case of individually sent parts (via the message-push-part or message-push-part-final packet) how large such a part can be;

  • in case of parts sent aggregated (via the message-push-parts packet) how large all the parts concatenated can be;

  • the device actually needs two independent buffers, one for transmitting and one for receiving;
  • the device also needs more memory (but a small constant amount) for other information, like states, part sizes, etc.;

Specification

Notes

• after the initial connection handshake the exchanges are asynchronous (as seen from the two individual FSM for the transmit and receive side);
• although the message part encoding is ambiguous -- for example a 4 byte message part can be encoded either as a fixed-length part, or a variable length part with either a 1 byte or 2 byte size -- the encoding detail must not leak to the application, thus from the application's point of view there is only one encoding scheme;
• it would be easy to add reliability to the protocol by either:
  • using selective acknowledgment and retransmission of past messages or parts, but it would be impractical due to the small memory requirements imposed by the embedded device;
  • or by using immediate part acknowledgment and retransmission which would complicate the protocol; (this could be implemented in future versions;)

Packet exchanges

• # handshake
  1    | D --> C | <connect-request>
  2    | C --> D | <connect-acknowledge>
  
  # controller to device exchanges
  n+1  | C --> D | <message-push-request>
  n+2* | D --> C | <message-push-continue>
  n+3* | C --> D | <message-push-part>
  ...
  n+4  | D --> C | <message-push-continue>
  n+5  | C --> D | <message-push-part-final>
  
  n+1  | C --> D | <message-push-request>
  n+2  | D --> C | <message-push-continue>
  n+3  | C --> D | <message-push-parts>
  
  # device to controller exchanges
  n+1  | D --> C | <message-push-forced>
  n+2* | D --> C | <message-push-part>
  ...
  n+3  | D --> C | <message-push-part-final>
  
  n+1  | D --> C | <message-push-forced>
  n+2  | D --> C | <message-push-parts>
  
  # miscellaneous exchanges
  *    | X --> X | <ping>

• roles:

  • D -- device;

  • C -- controller;

  • X -- either device or controller;

Device states

• [connect-waiting]
      send <connect-request> --> [connect-waiting]
      recv <connect-acknowledge> --> [tx:idle][rx:idle] | [panic]
  
  
  [tx:idle]
      send <ping> --> [tx:idle]
      # not advisable on controller
      send <message-push-request> --> [tx:message-push-waiting]
      send <message-push-forced> --> [tx:message-push-forced]
  
  # not advisable on controller
  [tx:message-push-waiting]
      recv <message-push-continue> --> [tx:message-push-pending]
      recv <message-push-abort> --> [tx:idle] | [panic]
  
  # not advisable on controller
  [tx:message-push-part-waiting]
      recv <message-push-continue> --> [tx:message-push-part-pending]
      recv <message-push-abort> --> [tx:idle] | [panic]
  
  # not advisable on controller
  [tx:message-push-pending]
      send <message-push-part> --> [tx:message-push-part-waiting]
      send <message-push-part-final> --> [tx:idle]
      send <message-push-parts> --> [tx:idle]
  
  # not advisable on controller
  [tx:message-push-part-pending]
      send <message-push-part> --> [tx:message-push-part-waiting]
      send <message-push-part-final> --> [tx:idle]
  
  [tx:message-push-forced]
      send <message-push-part> --> [tx:message-push-part-forced]
      send <message-push-part-final> --> [tx:idle]
      send <message-push-parts> --> [tx:idle]
  
  [tx:message-push-part-forced]
      send <message-push-part> --> [tx:message-push-part-forced]
      send <message-push-part-final> --> [tx:idle]
  
  
  [rx:idle]
      recv <ping> --> [rx:idle]
      recv <message-push-request> --> [rx:message-push-waiting]
      # not advisable on device
      recv <message-push-forced> --> [rx:message-push-forced] | [panic]
  
  [rx:message-push-waiting]
      send <message-push-continue> --> [rx:message-push-pending]
      send <message-push-abort> --> [rx:idle]
  
  [rx:message-push-part-waiting]
      send <message-push-continue> --> [rx:message-push-part-pending]
      send <message-push-abort> ---> [rx:idle]
  
  [rx:message-push-pending]
      recv <message-push-part> --> [rx:message-push-part-waiting]
      recv <message-push-part-final> --> [rx:idle]
      recv <message-push-parts> --> [rx:idle]
  
  [rx:message-push-part-pending]
      recv <message-push-part> --> [rx:message-push-part-waiting]
      recv <message-push-part-final> --> [rx:idle]
  
  # not advisable on device
  [rx:message-push-forced]
      recv <message-push-part> --> [rx:message-push-part-forced]
      recv <message-push-part-final> --> [rx:idle]
      recv <message-push-parts> --> [rx:idle]
  
  # not advisable on device
  [rx:message-push-part-forced]
      recv <message-push-part> --> [rx:message-push-part-forced]
      recv <message-push-part-final> --> [rx:idle]

Packet framing

• <frame> = <prologue> <packet> <crc> <epilogue>
  
  <prologue> = 0x55
  <epilogue> = 0xaa
  
  <crc> = <uint-16>

• binary patterns:

  • 0x55 -- 01010101;

  • 0xaa -- 10101010;

• re-synchronization can be achieved by looking after the pattern 0x55 0xaa and then trying to parse a valid package;

Packet encoding

• bytes (or nibbles) identifying various items start at 0x04 (or 0x4) as it leave smaller values for future extensions;

• the identifier field is used by the device and controller to designate their roles, and not their identities; (that is they are hard-coded in either the program or a configuration file;)

• the one that initiates the "conversation" is the device, because:
  • it is assumed that the controller powers the device explicitly (as in the case of Arduino);
  • it allows the controller to be backward compatible by implementing multiple behaviours based how the device presents itself, thus replying with an appropriate identifier;
• sequences:

  • they start at 1;

  • in the connect messages the sequence represents the last sent message (or 0);

  • in the ping messages the sequences represent the ones fully sent and received;

  <connect-request> = 0x04 0x04 <version> <identity:uuid> <initial-sequence:sequence> <limits>
  <connect-acknowledge> = 0x04 0x05 <version> <identity:uuid> <initial-sequence:sequence>
  
  <version> = 0x04 0x04
  <limits> = <max-part-count:size> <max-buffer-size:size>

  <message-push-request> = 0x14 0x04 <sequence>
  <message-push-forced> = 0x14 0x05 <sequence>
  <message-push-continue> = 0x14 0x06 <sequence>
  <message-push-abort> = 0x14 0x07 <sequence>
  
  <message-push-part> = 0x14 0x08 <sequence> <part-sequence:sequence> <message-part>
  <message-push-part-final> = 0x14 0x09 <sequence> <part-sequence:sequence> <message-part>
  
  <message-push-parts> = 0x14 0x0a <sequence> <part-count:uint-8> <message-part>{*}
  
  <message-part> =
      0x00
      0x01 <byte>
      0x02 <byte>{2}
      0x03 <byte>{4}
      0x04 <byte>{8}
      0x05 <byte>{16}
      0x06 <byte>{32}
      0x07 <byte>{64}
      0x08 <byte>{128}
      0x09 <byte>{256}
      0x0a <size:uint-8> <byte>{*}
      0x0b <size:uint-16> <byte>{*}

  <ping> = 0x04 <last-received-sequence:sequence> <last-sent-sequence:sequence>

  <size> = <uint-16>
  <sequence> = <uint-16>
  <uuid> = <byte>{16}

Extensions

• it is possible to use almost the same protocol to communicate between two devices, by just:
  • adding a new symmetric connection handshake;
  • implementing the flow-control on both sides;
• the message encoding allows to interleave parts of multiple messages, thus "multiplexing" the connexion in a way similar to AMQP;
• as discussed in a previous section, reliability could be achieved by adding acknowledgments after each individual part;

References

• protocol related:

  • 15/ZMTP -- ZeroMQ Message Transport Protocol;

• framing related:

  • High-Level Data Link Control;

  • RFC 1662 -- PPP in HDLC-like Framing;

  • Serial Communication Protocols for Embedded Systems;

  • Framing in serial communications;

• hardware related:

  • Software flow control;

  • RS-232 RTS/CTS handshake;

  • Serial HOWTO;

• Arduino related:

  • Arduino Serial Port Communication;

• just for future reading:

  • Firmata v2.2 Protocol Details;

  • MQ Telemetry Transport;

  • Modbus;