Serial Framing Protocol
SFP (Serial Framing Protocol) is a reliable link-layer protocol which operates on octets (bytes), styled after the Point-to-Point Protocol. Since it is a link-layer protocol, it supports only two endpoints; thus, there is no concept of addressing. It is intended for use on links with a low bandwidth-delay product, such as USB cables. To reduce complexity, it uses no ACK packets, and no timers. Additionally, to allow easy inclusion in embedded firmware, it requires no dynamic memory allocation, relying instead on a context data structure which contains all SFP state and buffers. The user is responsible for allocating this context.
The most basic responsibility of SFP is to encapsulate a user's packet into a link-layer frame, and to ensure that this packet is delivered to the user on the other end of the link. (In this document, the term "user" shall refer to the code which uses the SFP interface, or the programmer who writes this code.) SFP accomplishes its task with the following actions.
- Packets are assigned a sequence number.
- Packets are recorded in a fixed-size history buffer.
- Packets are framed using flag octets and a 16-bit CRC (HDLC-like framing).
- A three-way connection handshake is provided to enforce synchronization of history buffers.
HDLC-like framing is composed of two parts: flagging/escaping, and a CRC. Before explaining this in detail, it is useful to motivate the need for HDLC-like framing with an example.
A common method for transmitting user packets over a link is simply to transmit the length, in bytes, of the entire frame (including the length of the header), followed by the data itself. For example, given the ASCII user packet "abcd", the data's length is four. Assuming an 8-bit header field, the entire length of the frame would be five, and the following would be transmitted:
Header | Data
-------+-------
5 | "abcd"
Or, in hexadecimal:
Header | Data
-------+------------
05 | 61 62 63 64
This suffers from a major problem: if the transmitted length value is corrupted en route to the remote host, the remote host will become unsynchronized, and will likely stay that way. For example, consider the two packets, "abcd", and "efgh". Over the wire, they would look like:
(with Hd meaning Header)
Frame 0 | Frame 1
-----------------+-----------------
Hd | Data | Hd | Data
---+-------------+----+------------
05 | 61 62 63 64 | 05 | 65 66 67 68
Assume Frame 0's length is corrupted to 0x07, a difference of a single bit. The octet 0x66 would then be interpreted as the length of Frame 1. This is clearly an error, and it will have major ramifications down the line. If this is the end of the transmission, the receiver will wait indefinitely for the rest of Frame 1, potentially not giving an appropriate reply. If the transmission continues, the receiver will in all likelihood erroneously interpret another data value as a frame length, and the cycle repeats.
A more robust system is not to transmit the length, but rather frame the packet with flag octets, most commonly 0x7e (binary: 0111 1110).
(with Fl meaning Flag)
Fl | Frame 0 | Fl | Frame 1 | Fl
---+-------------+----+-------------+---
7e | 61 62 63 64 | 7e | 65 66 67 68 | 7e
While a corrupt flag octet could still cause two frames to be interpreted as one, the cascading errors observed with the previous system is impossible, unless every single flag octet in a transmission is corrupted. Otherwise, the receiver will eventually observe a good 0x7e octet, and recognize it as the end of one frame and the start of another. The flag octet is a delimiter, and it is useful to think of it as such.
This leaves two questions: how do we deal with 0x7e octets in the user's data, and how do we detect when a frame has been corrupted?
The answer to the first question is simple, and is analogous to the problem of including a quotation mark in a quoted string literal in a programming language (i.e., "\""): we use an escape octet. The standard value for such an escape octet is 0x7d (binary: 0111 1101). In addition, we flip bit 5 of the octet being escaped (bits in an octet being numbered, most-significant-bit first, 7654 3210). This gives us two rules to follow:
- When transmitting, prefix any
0x7eor0x7doctets in the user's data with0x7d, and XOR the user's octet with0x20before sending. - When receiving, discard any
0x7doctet and XOR the following octet with0x20before putting it in the receiver's buffer.
Any octet may be escaped, but SFP only requires that flag and escape octets be escaped. In other words, a 0x7e in the user's data becomes 7d 5e, and a 0x7d becomes 7d 5d.
The reason for flipping the fifth bit is largely historic: terminal hardware sometimes injects ASCII control characters (the unprintable ASCII characters, values less than 32) into data streams. By escaping these control characters and flipping their fifth bit on transmission, the receiver can detect whether a control character came from the remote host, or from the local host's hardware. It has the added benefit that it guarantees no 0x7e flag octets will occur anywhere in the data stream on the wire except in their intended locations.
We also need a facility to detect when a frame has been corrupted. A standard, easy way of doing this is to include a cyclic redundancy check, or CRC. This is typically encoded at the end of the frame, just before the flag octet, for reasons which will become clear.
SFP uses the 16-bit CRC-CCITT function. This was chosen because it is conveniently included in avr-libc, and is the same function used in the PPP protocol, for which there exists abundant documentation.
The CRC calculation begins with an initial state, typically 0xffff. In libsfp, this is the value of SFP_CRC_PRESET in serial_framing_protocol.h. On transmission, each data octet in the frame (including the header, but before flag or escape octets are added) is fed to the function one at a time. At the end of this computation, the bits of the resulting CRC are flipped (i.e., we take its bitwise complement), and this value is transmitted over the wire, least significant byte first.
On receipt, we again begin with the initial value of SFP_CRC_PRESET, and feed the octets we receive into the CRC function. This is done after flag and escape octets are removed from the data stream. We compute the CRC eagerly; that is, we feed the incoming CRC value to the CRC function itself without worrying about it. This is by design, because the CRC function has the following property:
- Given an arbitrarily-long string of octets, x, and a 16-bit, complemented, LSB-first CRC of that message, y, the CRC of xy will be
0xf0b8. This magic value isSFP_CRC_GOODin serial_framing_protocol.h.
(TODO: an example would be good here.)
It is to exploit this property that we include the CRC at the end of the frame, instead of sticking it in a header. All the receiver has to do is compute the rolling CRC as it receives octets. When it encounters an unescaped flag octet, it knows it has reached the end of the frame. At this point, if the current value of the rolling CRC is SFP_CRC_GOOD, then the message is verified as having no errors.
While HDLC-like framing provides us a robust method of delivering data to the remote host, and verifying its correctness, we still need a way of recovering from any errors that the cyclic redundancy check reveals. To this end, SFP maintains a history buffer of sent frames, implemented as a ring buffer, and numbers every outgoing frame with a sequence number. A small header contains this sequence number, plus control bits which SFP uses to manage retransmissions.
The header is a single byte laid out like so: ccss ssss, where c is a control bit, and s is a sequence number bit.
The sequence number bits comprise an integer with a 6-bit range, [0, 64). Sequence numbers overflow back to 0 when incremented past their maximum. Sequence numbers are used primarily to identify the order in which a host transmits its user frames. Both hosts have two separate sequence counters: one for their transmitter, and one for their receiver. The transmitter sequence counter contains the number that will be assigned to the next outgoing frame. The receiver sequence counter contains the number that the receiver next expects from the remote host. Upon the establishment of the connection, all four of these counters are set to zero.
The control bits indicate which of the four frame types this frame is: USR, RTX, NAK, or SYN.
SFP_FRAME_USR == 0 /* User frames */
SFP_FRAME_RTX == 1 /* Retransmitted user frames */
SFP_FRAME_NAK == 2 /* Negative acknowledgement frames */
SFP_FRAME_SYN == 3 /* Synchronization frames */
-
User frames (USR) are the frames which encapsulate the initial transmission of a user's packet. They are generated and sent when the user calls
sfpWritePacket(). They are the only frames which are ever added to the history buffer. -
Retransmitted user frames (RTX) also contain the user's data, but they are generated in response to a negative acknowledgement received from the remote host. They are not added to the history buffer, because they come from the history buffer.
-
Negative acknowledgement frames (NAK) are generated in response to out-of-order USR frames and any frame which fails its CRC test. For a NAK frame, the header's sequence number indicates the sequence number which the receiver was expecting. It is worth stressing that NAKs are not generated in response to out-of-order RTX frames, because doing so causes a feedback-like effect.
-
Synchronization frames (SYN) are used exclusively in the connection handshake. The sequence number bits have a special meaning for these frames, and can take one of only four values.
SFP_SEQ_SYN0 == 0 /* Synchronization request frame */ SFP_SEQ_SYN1 == 1 /* Synchronization response frame */ SFP_SEQ_SYN2 == 2 /* Synchronization complete frame */ SFP_SEQ_SYN_DIS == 3 /* Disconnect frame */
SFP maintains a history buffer with a capacity of SFP_CONFIG_HISTORY_CAPACITY (default: 16) frames. This capacity may differ between hosts. Every time a user calls sfpWritePacket(), SFP pushes the transmitted frame onto the history buffer and increments the transmitter's sequence counter to the next sequence number.
From there, the frame travels across the wire, where it is received by the remote host. This host checks the frame's CRC value first, generating a NAK if it fails. Otherwise, the frame is processed according to the following.
-
If the incoming frame is a USR or RTX frame, check its sequence number. If the frame was received in-order (i.e., its sequence number matches the receiver's expected sequence number) then its data is extracted and delivered to the user. Out-of-order USR frames cause this host to generate a NAK for the expected sequence number, while out-of-order RTX frames are silently discarded.
-
If the incoming frame is a NAK frame, the NAKed sequence number is checked. If it does not match the transmitter's sequence counter, then this host's entire history is retransmitted, from the NAKed sequence number to the sequence counter's current value. If the NAKed sequence number is equal to the transmitter's sequence counter, then this means that the remote host is simply reporting that it is all caught up, and the NAK is silently discarded.
-
If the incoming frame is a SYN frame, the receiving host's connection state machine is affected. This is the subject of the next section.
(TODO: make a few graphics for simple examples)
