% ** General Options ***************************************************

	\documentclass[10pt,a4paper]{article}

	% ** input encoding **
	\usepackage[utf8]{inputenc} % Linux / Windows
	%\usepackage[applemac]{inputenc} % Mac

	% ** language **
	%\usepackage[french]{babel} % french
	%\usepackage[french, english]{babel} % bilingual, french / english
	\usepackage[english]{babel} % english
	
	% ** illustrations **
	\usepackage{graphicx}
	\usepackage{subfigure}

	% ** tables **
	\usepackage{rotating}
	\usepackage{ctable}
	\usepackage{multirow}
	\usepackage{makecell}
	\usepackage{tabularx}
	\usepackage{listings}

	
	% ** equations **
	\usepackage{amsmath,amssymb,amsfonts}
	\newcommand{\be} {\begin{equation}}
	\newcommand{\ee} {\end{equation}}
	\newcommand{\ben} {\begin{equation*}}
	\newcommand{\een} {\end{equation*}}
	\newcommand{\st} {\ensuremath{\sigma}}
	\newcommand{\dfm} {\ensuremath{\varepsilon}}
	\newcommand{\delx} {\ensuremath{\Delta x}}
	\newcommand{\dely} {\ensuremath{\Delta y}}
	\newcommand{\delz} {\ensuremath{\Delta z}}
	\renewcommand{\deg} {\ensuremath{^{\circ}}}
	\providecommand{\abs}[1]{\ensuremath{\left|#1\right|}}
	\providecommand{\re}[1]{\ensuremath{\frac{\Delta #1}{#1}}}
	\providecommand{\norm}[1]{\ensuremath{\lVert#1\rVert}}
	\renewcommand{\vec}[1]{\ensuremath{\boldsymbol{#1}}}
	\providecommand{\unit}[1]{\ensuremath{\mathrm{#1}}}
	\providecommand{\E}[1]{\ensuremath{\cdot 10^{#1}}}
	\providecommand{\tp}[1]{\ensuremath{10^{#1}}}
	\providecommand{\ddif}{\ensuremath{\mathrm{d}}}
	
	% ** links **
	\usepackage[colorlinks,bookmarks=false,linkcolor=blue,urlcolor=blue]{hyperref}
	\newcommand{\mail}[1]{{\href{mailto:#1}{#1}}}
	\newcommand{\ftplink}[1]{{\href{ftp://#1}{#1}}}
	

	% ** comments **
	\newcommand{\comment}[1]{{}} % multi-line comment
	
	% ** layout **
	\setlength{\textheight}{235mm}
	\setlength{\topmargin}{-1.2cm}
	%\setlength{\footskip}{5mm}
	\setlength{\textwidth}{15cm}
	\setlength{\oddsidemargin}{0.56cm}
	\setlength{\evensidemargin}{0.56cm}

\newcommand{\iw}{7.3cm}


% ** Title, author *****************************************************
\title{Arduino Communication protocol, Ensured (ACE)\\Specification}
\date{\today}
\author{Jakob Odersky}
	    
\setcounter{tocdepth}{2}

% ** Document **********************************************************
\begin{document}

\maketitle
\pagestyle{plain}

\section{Introduction \& Purpose}
The purpose of the Arduino Communication protocol, Ensured (ACE) is to provide reliable and reactive communication between a micro controller and a computer (or two micro controllers). The main features of the protocol are reliability, in a sense that the communicating parties know if a sent message was received or not, and reactivity, i.e. the main program loop is not blocked whilst waiting for a message response.

Compared to the OSI model, ACE is a data-link layer protocol.

\section{Functional Overview}
The operation of ACE may be divided into two parts: data framing and automatic repeat request. Data framing is the action of ``packaging'' a sequence of data bytes so that it may be sent as a whole over a physical channel. A checksum sent in the frame ensures that if an error occurred during transmission it is very likely to be detected and the whole frame rejected.

However, if such an error occurs, the sender has no way of knowing it and the sent data will be lost. To remedy this kind of situation, ACE uses a form of automatic repeat request mechanism.

See the following sections on details of these two parts.

\section{Framing}
As to ensure reliability, data is always sent in frames containing a checksum. A frame is composed of: a header consisting of one start byte, followed by an arbitrary amount of data bytes\footnote{limits are implementation specific}, followed by a trailer consisting of one checksum byte and one stop byte. The checksum is calculated by taking the exclusive or of all data bytes. Furthermore, data and checksum bytes are escaped by a preceding escape byte. An overview of a data frame and the definition of special byte values are given in table \ref{tab:frame}.


An invalid frame should be ignored by the receiver and no action taken.

\begin{table}[ht]
 \begin{tabular}{|l||c|c|c|c|} \hline
 Structure & Header & Data & \multicolumn{2}{|c|}{Trailer} \\ \hline \hline
 Detailed structure & start & data & checksum & stop \\ \hline
 Length (bytes) & 1 & any (within limits of implementation) & 1 & 1 \\ \hline
 Hexadecimal values & 0x02 & & XOR  of all data bytes & 0x03 \\ \hline
 \multicolumn{5}{l}{Escape byte value: 0x10.} \\
 \end{tabular}
 
 \caption{A data frame in ACE.}
 \label{tab:frame}
\end{table}


\subsection{Example 1}
As a first example, consider the message ``hello'' encoded in ASCII. Equivalently, this message may be represented as a sequence of bytes (in decimal representation): \begin{verbatim} 104 101 108 108 111 \end{verbatim}
The checksum of this message is 98, therefore the corresponding data frame is:
\begin{verbatim} 002 104 101 108 108 111 098 003 \end{verbatim}

\subsection{Example 2}
As a second example, consider the byte sequence:
\begin{verbatim} 001 108 002 111 016 102 \end{verbatim}
The values 002 and 016 are special bytes and therefore have to be escaped. Considering that the checksum is 118, the resulting frame is given by:
\begin{verbatim} 002 001 108 016 002 111 016 016 102 118 003 \end{verbatim}

\section{Automatic Repeat Request (ARQ)}
To remedy the loss of invalid frames, ACE uses a kind of stop-and-wait ARQ. After sending a frame, the sender waits for an acknowledgement of the receiver before transmitting a next frame. If no acknowledgement is received in a timeout delay, the message is retransmitted. If after retransmitting the message several times no acknowledgement has been received, the message is considered to have been lost and an error is generated at the sender side. Only if the correct acknowledgement is received the message may be considered successfully sent and an action may be taken.

On the receiver side, if a frame is received, an acknowledgement to that frame is sent back and application specific action (to the message) is taken. If the same frame is received following the acknowledgement, it is considered that the sender did not receive the acknowledgement and the acknowledgement is retransmitted, this time without taking application specific action.

To differentiate frames and to enable the distinction between acknowledgements and data frames, each message is preceded with a sequence byte and a command byte (in that order) before being sent as a frame.

The sequence byte is used an identification number and is incremented for every new message (a new message is a message that has not been retransmitted). In case the message is an acknowledgement, the sequence number determines to what message the acknowledgement responds. In case of an overflow, the sequence number restarts at zero.

The command byte determines if the message is data or an acknowledgement. Its value is 0x05 in case of data and 0x06 in case of an acknowledgement.

For an example, see the C pseudo-code in appendix \ref{sec:example}.

\section{Reactivity}
The previous sections specified the ``reliability'' part of ACE. The second important part of the protocol is reactivity. Since the concept of reactivity is very broad and possible implementations vary greatly, the ACE specification does not give any concrete requirements. Implementations must however provide a way to notify applications that a message was successfully transferred or that an error occurred.

\section{Conclusion}
This document specifies the ACE protocol. The reference implementations in C and Scala are authoritative in case of any uncertainties or inconsistencies with this document.

\newpage
\appendix
\section{Stop-and-wait ARQ, example implementation} \label{sec:example}
\lstset{language=c}
\begin{lstlisting}%[frame=single]

#define DATA 0x05
#define ACK 0x06

void send(uint size, uint8_t* message) {
  increment_seq_counter();
  send_frame({seq, DATA, message});
  awaiting_ack = true;
  start_timer();
}

void receive(uint size, uint8_t* data) {
  uint8_t seq = data[0];
  uint8_t cmd = data[1];
  uint8_t* message = &(data[2]);
  int16_t message_size = size - 2;
    
  if (!awaiting_ack) { //ready to receive
    if (cmd == DATA) { //the message is data
      if (last_received_seq != seq) { //the message was not already processed
        last_received_seq = seq;
        application_specific_action(); //process message
      } 
      send_ack(seq); //send acknowledgement to the received frame
    } else {
      //ignore case in which an ack is received even though none is awaited
    }
      
  } else { //awaiting ack
    awaiting_ack = false; //got something so stop waiting for ack
    stop_timer(); //stop timeout
    
    if (cmd == ACK && seq == last_sent_seq) { // the correct ack was returned
      application_specific_action_send_success();
    }
  }
}

void timeout() {
  if (resends > MAX_RESENDS) {
    error_no_ackowledgement();
  } else {
    resends += 1;
    restart_timer();
    resend_message();
  }
}
\end{lstlisting}



% \newpage
% \appendix
% \input{appendix.tex}

%\bibliographystyle{ieeetr}
%\bibliography{bibliography}
\end{document}
