% -*- TeX-master: "dp2.tex" -*-
% $Id: communications.tex,v 1.2 2004/05/06 14:10:42 dan Exp $

The most important communications between the devices on Mars are the
distribution of missions and the transmission of mission data. The
network layer is already specified as a ``black box'' with the functions
\proc{sendMsg}(\id{msg}, \id{length}) and
\proc{deliver_message}(\id{packet}, \id{length}), so only packet
segmenting must be dealt with. The link layer is also specified,
because it is just a broadcasting radio receiver, although there is an
issue of how to detect nearby devices which are available to receive
messages. Thus, the majority of the communications design is in the
end-to-end layer.


\subsection{Protocol Design}
\label{sec:protocol}


The first task is to design a standard packet
protocol. The Mars devices follow this protocol for the format of the
packets (in the end-to-end layer; the network and link layers may, of
course, add headers and trailers):

\begin{itemize}
\item Device name
\item Message nonce
\item Message type
\item Message arguments (for message types one, five, six, seven, and ten)
\item Signature
\item Checksum
\end{itemize}

\paragraph{Device name}
The first part of the packet, the device name, is trivial. The rovers
can be given numbers 1-50 as their names, and the command center can
have the name 0, thus providing each device with a unique identifier.

\paragraph{Message nonce}
The nonce is a unique integer chosen by the rover or command center
randomly. Since there are at most fifty-one messages being broadcast
at the same time, a nonce can simply be an integer of several bytes.

\begin{table}[htbp]
  \centering
  \begin{tabular}{|r|l|}
    \hline
    \textbf{ID} & \textbf{Message Type} \\
    \hline
    01 & Acknowledge \\
    02 & ``Who's here?'' \\
    03 & Begin communication \\
    04 & End communication \\
    05 & Mission assignment \\
    06 & Mission data \\
    07 & Data / assignment size \\
    08 & Not enough memory \\
    09 & Already have a mission \\
    10 & Resend message \\
    \hline
  \end{tabular}

  \caption{Message types}
  \label{tab:message-types}
\end{table}


\paragraph{Message type and arguments}
The message type is a single integer specifying the type of message,
such as an acknowledgement or error (see
Table~\ref{tab:message-types}). Message type one, the acknowledgement,
and message type ten, the request to resend, are followed by the
nonces of the messages to which they refer. Message types five and
six, which flag mission assignments and data respectively, will be
followed by the expected sort of message in a standard format
(specified in the section on mission distribution).  Messages type
seven, which flags a data size message, is followed by an integer
specifying the amount data the device wishes to send in bytes. This is
so the device receiving the data or assignment will know how much
memory to allocate, or send a type eight message in reply if there is
not enough memory.  The rest of the message types do not require
additional arguments.

\paragraph{Signature}
The next item, the signature, is to
provide authentication so that the messages from Poodle rovers will
not be mistaken for messages from NASA rovers. Since the Poodle rovers
are not malicious, there is no need for message encryption or
protection against attacks. The most logical solution is to have all
devices sign their messages using a shared secret key. The only
requirement for this key is that it is different from any key the
Poodle rovers might be using; a 54-bit key would be more than enough
protection. Finally, the packet is ended by a SHA1 hash of the
message, used as a checksum. Whenever a rover receives a message, it
checks the signature and recalculates the checksum of the message. If
the signature is not the correct, expected signature of another NASA
device, it disregards the message. If the checksum doesn't match, it
sends the rover a type ten (resend message) message. The checksum is
checked first, because there may be an error in the signature.


\subsection{Message Delivery Procedure}
\label{sec:message-delivery}


In delivering a message from one device to another, the first step
must be ensuring that another device is in range of the radio. This is
accomplished by sending a type two (``who's here'') message.  Any device
which receives this message will broadcast an acknowledgement (ack;
signified by type one). If the device doesn't receive an answer and
expects that it should (for instance, if a rover knows it is in range
of the command center), it can re-broadcast the query after a
reasonable period of time until it receives an ack. Repeated queries
and acks cause little overhead, and a rover need not keep any state
except for the knowledge that it is expecting a query reply. Note that
a rover
%% will only send an ``ack'' if it is not moving, and
% not anymore! -drkp
will not move while communicating with another device. This will
prevent rovers from moving out of radio range while another device is
attempting to communicate with them. When a suitable device has been
located in radio range, mission data can be transmitted.


\subsubsection{Rover -- Control Center Communications}

The command center will wait for queries. When a
query is received, the command center acknowledges the query, and the
rover will send a message of type three (begin communication). The
rover will not move until the communication is finished. The rover
will then send a type seven message along with the size of the data it
plans to transmit, which the command center will acknowledge.

After receiving an acknowledgement, the rover will begin transmitting
the data in 1500-byte packets, each flagged type six. The data will
simply be segmented into pieces sized 1500 bytes - (size of packet
headers and trailers). The rover will only transmit one packet at a
time and wait for an acknowledgement or a request to resend a packet
before sending a new one. If it does not receive an acknowledgement or
resend request containing the nonce of the message it just sent after
a timeout period (for instance, two or three times the average amount
of time necessary to send, receive, and acknowledge a 1500-byte
packet), it discards that nonce and resends the packet with a new
nonce. Thus the devices only keep one piece of state (the current
nonce) per communication.

The fact that devices only transmit one packet at a time, and wait for
an acknowledgement before transmitting a new packet means that each
device receives packets in order, and so no order information need be
included with a packet of data. Since message transmission time is
trivial compared to traveling and experimentation time, using more
complicated protocols to transmit multiple packets would add
complexity without much performance benefit.

A rover will continue transmitting its mission data until it has
received an acknowledgement for the last packet. It will then send a
type four (end communication) message. The command center can either
acknowledge this, in which case the rover will sit idle until the
command center contacts it (using the same query/begin system
described above), or send a type seven (data / assignment size)
message, containing the size of the mission assignment it wishes to
send to the rover. This is also how the command center contacts rovers
when they first reach Mars. The rover will acknowledge the assignment
and allocate memory space, unless it already has a mission (an error
condition which should not happen), in which case it will send a type
nine message. It should have enough space free, since it just uploaded
all of its data to the command center, so it can delete data starting
with the oldest.  The command center will transmit its mission
assignment using the same protocol that the rover used to transmit its
data. After it has finished transmitting the mission assignment, the
command center will send a type four (end communication) message, and
the rover will respond with an ack. This frees the rover to begin its
travel to the mission site.


\subsubsection{Rover -- Rover Communications}

Two rovers can share mission results with each other (described in
Section~\ref{sec:data-exchange}). This is accomplished using exactly
the same protocol as a rover sharing data with the command center,
except that a rover can, after receiving the ``data size'' message,
send a message stating it does not have enough memory for the data, at
which point the other rover can decide to send only part of its data
and try again, or terminate communication


\subsubsection{Control Center -- Earth Communcations}
.
The other special case is communication between the command center and
Earth. This also follows the same protocol as described above, except
that the command center does not wait for acknowledgements before
sending the packets. Earth will know how many packets to expect upon
receiving the ``data size'' packet, so the command center can simply
number each packet it sends. It can even send packets multiple times,
defending against packet loss, if it runs out of new data to send
during a transmission time. The command center will not delete data it
holds until it receives acknowledgements for every non-duplicate
packet, thus the command center must keep extra state for
communications with Earth. It will resend packets to Earth as
necessary.


\subsubsection{Failures}

If a rover fails in the middle of a communication, then the device at
the other end will notice after a suitably long period of time that it
has not received any messages. It will then attempt several queries.
If it times out again, then the device will assume that the rover has
died. If the rover was communicating with the command center, it will
be marked dead; if the rover was communicating with another rover,
then that rover will simply move on to other tasks.



