bac_tex/z1_ot.tex

% Copyright (C) 2014-2017 by Thomas Auzinger <thomas@auzinger.name>

%\documentclass[draft,final]{vutinfth} % Remove option 'final' to obtain debug information.
\documentclass[final]{vutinfth} % Remove option 'final' to obtain debug information.

% Load packages to allow in- and output of non-ASCII characters.
\usepackage{lmodern}        % Use an extension of the original Computer Modern font to minimize the use of bitmapped letters.
\usepackage[T1]{fontenc}    % Determines font encoding of the output. Font packages have to be included before this line.
\usepackage[utf8]{inputenc} % Determines encoding of the input. All input files have to use UTF8 encoding.

% Extended LaTeX functionality is enables by including packages with \usepackage{...}.
\usepackage{amsmath}    % Extended typesetting of mathematical expression.
\usepackage{amssymb}    % Provides a multitude of mathematical symbols.
\usepackage{mathtools}  % Further extensions of mathematical typesetting.
\usepackage{microtype}  % Small-scale typographic enhancements.
\usepackage[inline]{enumitem} % User control over the layout of lists (itemize, enumerate, description).
\usepackage{multirow}   % Allows table elements to span several rows.
\usepackage{booktabs}   % Improves the typesettings of tables.
\usepackage{subcaption} % Allows the use of subfigures and enables their referencing.
\usepackage[ruled,linesnumbered,algochapter]{algorithm2e} % Enables the writing of pseudo code.
\usepackage[usenames,dvipsnames,table]{xcolor} % Allows the definition and use of colors. This package has to be included before tikz.
\usepackage{nag}       % Issues warnings when best practices in writing LaTeX documents are violated.
\usepackage{todonotes} % Provides tooltip-like todo notes.
\usepackage{hyperref}  % Enables cross linking in the electronic document version. This package has to be included second to last.
\usepackage[acronym,toc]{glossaries} % Enables the generation of glossaries and lists fo acronyms. This package has to be included last.
\usepackage{listings}
\usepackage{tabularx}
\usepackage[section]{placeins}

% Define convenience functions to use the author name and the thesis title in the PDF document properties.
\newcommand{\authorname}{Stephan Felber} % The author name without titles.
\newcommand{\thesistitle}{Porting OpenThread to Resource Constrained Devices} % The title of the thesis. The English version should be used, if it exists.

% Set PDF document properties
\hypersetup{
    pdfpagelayout   = TwoPageRight,           % How the document is shown in PDF viewers (optional).
    linkbordercolor = {Melon},                % The color of the borders of boxes around crosslinks (optional).
    pdfauthor       = {\authorname},          % The author's name in the document properties (optional).
    pdftitle        = {\thesistitle},         % The document's title in the document properties (optional).
    pdfsubject      = {Subject},              % The document's subject in the document properties (optional).
    pdfkeywords     = {a, list, of, keywords} % The document's keywords in the document properties (optional).
}

\setpnumwidth{2.5em}        % Avoid overfull hboxes in the table of contents (see memoir manual).
\setsecnumdepth{subsection} % Enumerate subsections.

\nonzeroparskip             % Create space between paragraphs (optional).
\setlength{\parindent}{0pt} % Remove paragraph identation (optional).

\makeindex      % Use an optional index.
\makeglossaries % Use an optional glossary.
%\glstocfalse   % Remove the glossaries from the table of contents.

% Set persons with 4 arguments:
%  {title before name}{name}{title after name}{gender}
%  where both titles are optional (i.e. can be given as empty brackets {}).
\setauthor{}{\authorname}{}{male}
\setadvisor{Ao.Univ.Prof. Dipl.-Ing. Dr.techn.}{Wolfgang Kastner}{}{male}

% For bachelor and master theses:
\setfirstassistant{Dipl.-Ing.}{Stefan Seifried}{BSc}{male}
\setsecondassistant{Univ.Ass. Dipl.-Ing.}{Philipp Raich}{BSc}{male}

% Required data.
\setaddress{Address}
\setregnumber{1426418}
\setdate{01}{04}{2019} % Set date with 3 arguments: {day}{month}{year}.
\settitle{\thesistitle}{OpenThread auf Resource beschränkten Geräten} % Sets English and German version of the title (both can be English or German). If your title contains commas, enclose it with additional curvy brackets (i.e., {{your title}}) or define it as a macro as done with \thesistitle.
%\setsubtitle{Optional Subtitle of the Thesis}{Optionaler Untertitel der Arbeit} % Sets English and German version of the subtitle (both can be English or German).

% Select the thesis type: bachelor / master / doctor / phd-school.
% Bachelor:
\setthesis{bachelor}
%
% Master:
%\setthesis{master}
%\setmasterdegree{dipl.} % dipl. / rer.nat. / rer.soc.oec. / master
%
% Doctor:
%\setthesis{doctor}
%\setdoctordegree{rer.soc.oec.}% rer.nat. / techn. / rer.soc.oec.
%
% Doctor at the PhD School
%\setthesis{phd-school} % Deactivate non-English title pages (see below)

% For bachelor and master:
\setcurriculum{Computer Engineering}{Technische Informatik} % Sets the English and German name of the curriculum.

% For dissertations at the PhD School:
%\setfirstreviewerdata{Affiliation, Country}
%\setsecondreviewerdata{Affiliation, Country}

\lstset{
	basicstyle=\ttfamily,
	columns=fixed,
	fontadjust=true,
	breaklines=true,
	basewidth=0.5em
}

\begin{document}

\newacronym{ot}{OT}{OpenThread}

\newacronym{phy}{PHY}{Physical Layer}

\newacronym{iot}{IoT}{Internet of Things}

\newacronym{ipv6}{IPv6}{Internet Protocol version 6}

\newacronym{ipv4}{IPv4}{Internet Protocol version 4}

%\newacronym{ip}{IPv4}{Internet Protocol}

\newacronym{6lowpan}{6LoWPAN}{IPv6 over Low Powered Personal Area Networks}

\newacronym{hal}{HAL}{Hardware Abstraction Layer}

\newacronym{posix}{POSIX}{Portable Operating Systems Interface}

\newacronym{uart}{UART}{Universal Asynchronous Receiver / Transmitter}

\newacronym{osi}{OSI}{Operating Systems Interconnection}

\newacronym{ffd}{FFD}{Full Function Device}

\newacronym{rfd}{RFD}{Reduced Function Device}

\newacronym{pan}{PAN}{Personal Area Network}

\newacronym{mtu}{MTU}{Maximum Transmission Unit}
 
\newacronym{udp}{UDP}{User Datagram Protocol}
 
\newacronym{tcp}{TCP}{Transmission Control Protocol}
 
\newacronym{reed}{REED}{Router Eligible End Device}
 
\newacronym{sed}{SED}{Sleepy End Device}
 
\newacronym{mle}{MLE}{Mesh Link Establishment}
 
\newacronym{psdu}{PSDU}{Physical Service Data Unit}

\newacronym{ack}{ACK}{Acknowledge}

\newacronym{icmp}{ICMP}{Internet Control Message Protocol}

\newacronym{usb}{USB}{Universal Serial Bus}

\newacronym{mac}{MAC}{Medium Access Control}

\newacronym{mcu}{MCU}{Micro controller Unit}

\newacronym{tls}{TLS}{Transport Layer Security}

\newacronym{cts}{CTL}{Clear To Send}

\newacronym{rtt}{RTT}{Round Trip Time}

\newacronym{spi}{SPI}{Serial Peripheral Interface}

\frontmatter % Switches to roman numbering.
% The structure of the thesis has to conform to
%  http://www.informatik.tuwien.ac.at/dekanat

%\addtitlepage{naustrian} % German title page (not for dissertations at the PhD School).
\addtitlepage{English} % English title page.
\addstatementpage

%\begin{danksagung*}
%\todo{Meine Kaffeemaschine.}
%\end{danksagung*}

\begin{acknowledgements*}

My coffee machine without which I would not even have started university and
my room mates without whom this thesis would have been finished a year earlier.  
	Thanks boys.

\end{acknowledgements*}

\begin{abstract}

    Small embedded systems featuring radio capabilities are getting cheaper and 
    cheaper to produce. These devices are characterised by a comparably low 
    processing power, a reduced periphery and low power consumption. To  allow 
    wireless communication between such devices, while respecting the 
    restrictions, a new specially crafted communication protocol had to be 
    designed. Demanding that it be power efficient, allowing devices to run on 
    battery, error resistant and easy to use may seem like too much to ask, but 
    Thread building on 802.15.4 and IPv6 fullfills all of the above.

    This thesis presents an implementation of OpenThread, an implementation of 
    the Thread specification for the Zolertia Z1 mote. The Z1 is a cheap and power 
    efficient 16-bit micro controller.

    By outlining the integral protocols of the Thread stack, the challenges of the 
    thesis are presented. In the end, an implementation for OpenThread using 
    the Zolertia Z1 is given. This implementation may be used to develop 
    applications for OpenThread on a PC while taking part in an actual Thread 
    network.

\end{abstract}

% Select the language of the thesis, e.g., english or naustrian.
\selectlanguage{english}

% Add a table of contents (toc).
\tableofcontents % Starred version, i.e., \tableofcontents*, removes the self-entry.

% Switch to arabic numbering and start the enumeration of chapters in the table of content.
\mainmatter

\chapter{Introduction}

\section{Motivation}

As small computers, or so called embedded systems, got cheaper over the last 
few years, the need for specially tailored communication protocols arose.  These 
embedded systems are restricted to a small power consumption and have to to be 
fairly cheap to produce, as they are expected to be used in large numbers.  
Designing a way of communication for such devices has to take these factors 
into account. It can neither be too complex to be run on a \gls{mcu} nor too 
energy consuming to use.

The low cost per unit and the resulting volumes of units produced allow 
for local networks with a larger amount of participants. Connecting this local 
domain of communication to the Internet results in the so called \gls{iot}.  
The \gls{iot} mainly consists of tiny computers which primarily do one or 
both of two things: firstly most of them serve as an actuator or a sensor. Like a light bulb 
that can be controlled via an app on your mobile phone, or a door lock that can 
be remotely released. Secondly they collect data. A humidity sensor might record 
the air quality, a smart dog feeder may remember when you feed your dog, and the 
light bulb might record when it is switched on and off. This data is then sent 
via the Internet to the user or the manufacturer.

An interesting sector for \gls{iot} is health care. As the median of the 
population age keeps getting older, new solutions for health care services have 
to be found. Because pretty much every bed is already connected to the 
Internet, it is expected that gathering all data available from a patient can 
be beneficial to both their recovery and further medical research.

As \gls{iot} devices are expected to get even cheaper and more numerous, 
more data sources will be monitoring the patients recovery story. The industry 
expects to develop more efficiently using such databases and keywords like Big 
Data, data mining and distributed intelligence are often associated with Health 
\gls{iot} \cite{doi:10.1080/17517575.2013.776118}.

\subsection{Technical Motivation}

Both the actuator and the sensor part of the connected device need a channel of
communication to receive commands and deliver information \cite{5523336}.
Taking into account that the participants of the network should be allowed to 
spread about in the range of the network, a wireless communication is heavily 
favored because it eliminates the need of a cable tree to every node. Although 
wireless clears some difficulties, it also presents new challenges, like 
increased power consumption or interference on the shared medium.

There are nevertheless solutions to the challenges presented. One of them is
\gls{ot} which builds on the 802.15.4 \gls{phy} standard. The 802.15.4 
standard was crafted specifically with such low power devices in mind. In order 
to provide direct connectivity to the Internet, the \gls{6lowpan} layer 
translates \gls{ipv6} to 802.15.4 friendly packets. This promotes every 
participant in the network to a fully qualified member of the \gls{ipv6} 
Internet and grants all the benefits of a direct Internet access. \gls{ot} 
is easing network setup and maintenance by providing self healing mechanisms 
and fully encrypted communication.

%This thesis provides an implementation of the \gls{ot} stack utilizing the
%Zolertia Z1 mote.

The Z1 features a 802.15.4 capable radio chip and multiple connection 
possibilities to connect sensors or actuators. It can run on battery or on the 
power provided by a \gls{usb} cable. Altough there are already multiple smaller 
devices providing the same functionality, the Z1 is still a candidate for the 
\gls{ot} stack.

%Glossary oder acronyms?

\section{Problem Statement}
%This chapter states the problem which this work aims to solve. The initial
%problem proved not to be solvable in the alloted amount of time but a different
%approach allowed similar results.

The task of this thesis is to port the \gls{ot} implementation to the Zolertia 
Z1 mote.

Up to now, \gls{ot} is already running on multiple embedded platforms from
different manufacturers, such as RIOT OS, Zephyr and provides two border
router implementations. The porting process of the \gls{ot} stack in
general consists of writing a new \gls{hal}. This means implementing an
\gls{hal} between the program logic and the hardware it runs on.

\gls{ot} is already a Thread certified implementation, which means that the 
Thread Group assures its compliance with the Thread standard. It was released 
under an open source license allowing developers easier development of 
applications for Thread. 

The Z1 is in general not as powerful as the other hardware \gls{ot} is already 
running on because it was released much earlier. This presents new challenges 
for the development of a \gls{hal} and problems like memory size or \gls{mcu} 
capabilities may arise.

\section{Aim of the Thesis}
%TODO measureable. Aim at the last result from the beginning. The thing in
%between is just a failure.
This thesis provides an implementation of the \gls{ot} stack utilizing the 
Zolertia Z1 mote. As the Z1 provides a 802.15.4 compatible radio interface it 
allows the \gls{ot} Stack to operate either directly on the device or with some 
transport layer in between. This model is already similarly described on the 
official \gls{ot} website as a network co-processor model, but no actual 
implementation was found at this time \cite{OTsite:platform}.

The result should allow developers writing applications for the \gls{ot} stack 
to actively develop on a normal computer while still having access to actual 
radio hardware. Applications may be tested in an existing \gls{ot} network and 
concurrently inspected by, for example, the GNU Debugger (GDB).

%This implementation allows developers to write their applications for
%\gls{ot} on a normal computer, with all standard debugging tools, like the
%GNU Debugger available. But it also provides an actual link to a running Thread
%network. This may prove especially valuable when debugging network related
%errors.


\chapter{State of the Art}

This chapter provides a more exhaustive description of the standards and
protocols that Thread relies on and are relevant for this thesis. Starting with 
the fundamentals, 802.15.4 will be explained, continuing with 6LoWPAN and its 
features. Thread, building on top of the previous two, is explained at the
end. The corresponding \gls{osi} model is visualized in figure 
\ref{fig:osi}.

Thread itself fullfills some aspects in the transport layer and some 
responsibilities of a network infrastructure manager. Considering this, it is 
both part of the transport layer and exceeds it. According to the \gls{osi} 
model, Thread corresponds to the transport layer, but Threads network 
management capabilities are simply not reflected in the \gls{osi} model.
This correctly classifies Thread but neglects the efforts for the mesh network 
establishment and maintenance.

%\input{images/802_15_4_topologies.tex}

\begin{figure}
\centering
\includegraphics[width=0.5\linewidth]{images/sota_osi.png}
\caption{The first three layers of the \gls{osi} model on the left, and their 
    respective specifications on the right.}
\label{fig:osi}
\end{figure}

\section{802.15.4}

In 2003, the Institute of Electrical and Electronics Engineers introduced the
802.15.4 standard to enable "very low-cost, low-power communication" for
devices while ensuring consistent transmission and keeping the protocol simple
but flexible. \cite[13, 45]{802_15_4_std}

This standard proved to be the foundation for many communication stacks 
operating on power constrained devices. Since efficient energy saving 
communication requires fine-grained control over the hardware used, it was 
necessary to start such a communication stack at the very lowest \gls{osi} 
level, the \gls{phy} layer. This may be observed in figure \ref{fig:osi}.

The lowest layer in the \gls{osi} model states how the bits are delivered 
from one point to another. It takes care of the physical and mechanical aspects 
and ensures the actual delivery of the information.

\subsection{Topology}

Two different network arrangements are allowed, called the star topology and 
the peer-to-peer topology. As the name suggests, the star topology forms a 
'star' because every node connects to the same router, also called the 
\gls{pan} coordinator. The single \gls{pan} coordinator handles all the message 
routing and every node participating in the network requires a connection to 
it, as visualized in figure \ref{fig:topstar}. This brings simplicity because 
it eliminates the need for routing algorithms, but also looses the ability to 
cover wider areas.

The peer-to-peer topology forms a mesh, which basically means that all routers
connect to all other routers in range. A mesh is visualized in figure 
\ref{fig:topmesh}. This implies that a router has to handle not only its 
children, but also maintains a table of its neighbouring routers. This topology 
grants more redundancy to the network infrastructure but also brings more 
complexity. Message routing algorithms for finding the best path between two 
routers are required, but the network can span over a bigger area compared to 
the star topology. Thread uses the distance-vector routing protocol to find the 
ideal path between non adjacent routers \cite[112]{thread_spec}.

Both topologies deploy a single \gls{pan} coordinator which acts as
the leader in infrastructure questions. It decides on new addresses, allows
or denies new routers in a mesh network or sets the \gls{pan} prefix, to 
name only a few tasks.

%\todo{verify this}

\begin{figure}

\begin{subfigure}{0.4\textwidth}
\includegraphics[width=\textwidth]{images/802_15_4_topologie_star.png}
\caption{The star topology as set in the 802.15.4 standard.}
\label{fig:topstar}
\end{subfigure}
\qquad
\begin{subfigure}{0.4\textwidth}
\includegraphics[width=\textwidth]{images/802_15_4_topologie_mesh.png}
\caption{The mesh, or peer-to-peer topology allows networks to cover a bigger
    area compared to the star topology. In the top right, there is a \gls{ffd} 
    that is not yet a router, because there is no need for it.}
\label{fig:topmesh}
\end{subfigure}

\end{figure}

\subsection{Network Structure}

Two different device types are specified, a \gls{ffd} and a \gls{rfd}.

\glspl{ffd} build the network. In the case of a star topology, one \gls{ffd} 
assumes the role of the sole router and the \gls{pan} coordinator. It handles 
message routing, coordinates new nodes wanting to join the network and is also 
responsible for the connection to the Internet if available. If the sole router 
breaks, any other \gls{ffd} that already joined the network can compete for the 
role as the new router and \gls{pan} coordinator.

The peer-to-peer topology, also called mesh, utilizes more than just one router 
\cite[47]{802_15_4_std}.  Redundancy is achieved by simply deploying more than 
one device for the same task. If a router breaks, all of its connected children 
will try to reconnect to the network using another router in reach. If there 
was a \gls{ffd} amongst the orphaned children, it will attempt to promote 
itself to a router, replacing the failed node.

If the network does not require another router, the \gls{ffd} may simply
work as an end node. It then waits until, for example, it receives a join 
request from a \gls{rfd}, in that case it asks for a promotion to router status 
from the \gls{pan} coordinator and subsequently adds the new node as its child.

A \gls{rfd}, as already mentioned, fully depends on \glspl{ffd} for a working 
network infrastructure. In order to join a network a router or a \gls{ffd} that 
is not yet a router needs to be in range.  Since \glspl{rfd} are not important 
to the network structure they can operate on much less power.

\section{Messages} \label{802_15_4_messages}

In an effort to ensure delivery over the generally unreliable nature of a 
wireless \gls{phy} layer, 802.15.4 specifies special acknowledge frames 
\cite[105]{802_15_4_std}. If the transmitting device requests a frame to be 
acknowledged by the receiving side, the receiver shall indicate through the so 
called \gls{ack} frame that the frame was correctly received. The standard sets 
a timeout within which the \gls{ack} has to be received, otherwise the frame is 
re-transmitted for a set amount of retries. If no \gls{ack} is received and all 
retries have been exhausted, the transmission of the frame fails.

%TODO kinda weird here, if not needed leave it
%A message for a Reduced-function Device has to be polled by the device itself
%which allows it to sleep, as the router will buffer all communication. As a
%consequence, every router has to be capable of storing messages long enough for
%its children to wake up again.

Regarding security, messages may be encrypted using symmetric keys and can be
authenticated using a cryptographic block cipher. \cite[360]{802_15_4_std} The 
standard does not set how the keys may be exchanged, but defines how messages 
are to be encrypted on the \gls{mac} layer.


\section{6LoWPAN}

%Providing internet access to the network of sensors is achieved by extending
%IPv6 to work with 802.15.4. This adaption problem concentrates on the fact that
%the Maximum Transmission Unit (MTU) of IPv6 is required to be 1280 bytes and
%the MTU of 802.15.4 is only 128 bytes. This means, that some sort of adaption
%layer between the Network layer (IP) and the Mac layer is needed to handle 
%fragmentation and reassembly, which is where 6LoWPAN comes in.
%6LoWPAN, or "IPv6 over Low-Power Wireless Personal Area
%Networks" \cite{rfc4919} specifies how the bigger IPv6 packets are delivered
%over the 802.15.4 network.

So far a structure for point-to-point communication was defined. Messages can 
be delivered to neighboring nodes, but up to now there is no concept of message
routing to nodes with no direct line of communication. Considering that a 
connection to the Internet is a requirement, \gls{ipv6} seems like a good 
candidate for the network layer. Since \gls{ipv6} is expected to take a 
significant portion of all Internet traffic by 2019,
\cite{Czyz:2014:MIA:2740070.2626295} and distributed low power networks 
typically exhibit a large amount of devices, \gls{ipv6} proved to be the 
better choice over \gls{ipv4}. Its large address space allows for an individual 
address assigned to every node and eliminates the need for subnets.

% TODO HC is more important than fragmentation
The main problem \gls{6lowpan} solves, is that the \gls{mtu} of 
\gls{ipv6} is 1280 bytes while the 802.15.4 can only send 127 bytes at once.  
Using a conventional link, a full \gls{ipv6} packet could be sent on the 
\gls{phy} layer in one go, but on 802.15.4 it needs to be split up. This 
imposes longer latency for larger packets, which is justified by the assumption 
that \gls{6lowpan} networks are expected to rather send small packets 
periodically anyway \cite[5]{rfc4944}. This nevertheless calls for an adaption 
layer between 802.15.4 and \gls{ipv6}, \gls{6lowpan} to take care of efficient 
packet fragmentation, packet routing and compression. Since 802.15.4 reaches up 
to the \gls{osi} model layer 2 and \gls{ipv6} operates on layer 3, 
\gls{6lowpan} bridges the gap in the middle of those two.

\subsection{Fragmentation and Reassembly}

If an \gls{ipv6} packet is too big to be sent in one go, it will be split into 
multiple fragments that are sent independently. On the receiver side, the 
fragments are reassembled and presented as one packet to the next layer.  This 
is achieved by preceding the packet with a fragmentation header which contains 
the index of the fragment and the total size of the packet. Allowing the 
receiver to efficiently assemble the whole packet even if the fragments arrive 
out of order \cite[p.~11]{rfc4944}. In contrast to \gls{ipv4}, the \gls{mtu} in
802.15.4 networks is guaranteed to be 127 bytes on every link which allows
every router to forward a fragment without fully assembling it. Figure
\ref{fig:6lowpan_frag} shows a fragmented \gls{6lowpan} packet with a \gls{udp}
payload.

\begin{figure}
\centering
\includegraphics[width=0.8\linewidth]{images/6lowpan_frag.png}
\caption{Boxes sharing the same border color also share the same information.  
    The first bar shows the \gls{ipv6} frame, the second and the last bar model 
    the first and the last fragment of the fragmented \gls{ipv6} packet.}
\label{fig:6lowpan_frag}
\end{figure}

\subsection{Header compression}

Some assumptions about the \gls{pan} allow \gls{6lowpan} to strip the 
\gls{ipv6} header down to just the necessary information.  In the best case, 
assuming a link local communication, the 40 bytes \gls{ipv6} header can be 
compressed to just 2 bytes. If the packet has to pass multiple routers on its 
way to the destination, a special mesh header is required. In this case, the 
total \gls{6lowpan} header can be as small as 7 bytes. Providing further 
compression, the following \gls{udp}, \gls{tcp} or \gls{icmp} headers may also 
be reduced in size. \cite[p.~19]{rfc4944}

If the message is larger than the \gls{mtu} of 802.15.4, the \gls{6lowpan} 
fragmentation header introduces only 3 bytes resulting in a 5 byte overhead. A 
small packet travelling just in the mesh network consists of a mesh header and 
the compressed \gls{ipv6} header, adding up to only 6 bytes.  
\cite{Mulligan:2007:ARC:1278972.1278992} 

\subsection{Link Layer Packet forwarding}

As the mesh header of a packet is transmitted first, intermediate routers may 
need to forward the packet to the next stop at the link layer. This saves time 
as the upper layers do not have to be consulted. In figure 
\ref{fig:6lowpan_frag}, it can be seen that the mesh header also precedes
fragmented packets and thus allows link layer forwarding.

\section{Thread}

With \gls{6lowpan} providing means of addressing nodes in and outside of a 
network, only a protocol for building and maintaining the network is missing. 
Thread fills this gap and provides features like self healing, nearly automated
network joining, full data encryption and \gls{udp} plus optionally
\gls{tcp} as a transport layer.

\subsection{Devices}

In addition to the \gls{ffd} and the \gls{rfd}, Thread utilizes three
more devices types. A Network Leader, a \gls{reed} and a Border Router.
The \gls{rfd} is simply renamed to a \gls{sed}. Before a network
becomes usable, all the routers participating will elect a Network Leader among
them. The leader takes decisions for the whole network, such as which address a 
new node receives or if a \gls{reed} gets promoted to a router.  A typical
Thread network imposes a limit of 32 routers. A \gls{reed} can ask the
Network Leader to be promoted if another node tries to join the network using
that \gls{reed} as a parent.  In the same manner, if all children of a
router have disconnected, it will be downgraded to a \gls{reed} again.

The Border Router typically utilizes different hardware compared to the other 
Thread devices, as it is also connected to some other network. In most cases, 
this works over Wi-Fi or Ethernet. A Border Router also routes messages within 
the mesh network as it still is a complete router. Thread allows for more than 
one Border Router.

\subsection{Network Structure}

Children of a router can be either \glspl{reed} or \glspl{sed} The latter 
received their name because they are allowed to sleep for short time frames to 
save energy and typically run on battery.

Thread networks form a mesh, as illustrated in figure \ref{fig:topmesh}, which 
grants redundancy for certain nodes.  A network consisting of just one router 
and multiple \gls{sed}s simply turns into a star topology. If the router 
representing the parent of a \gls{sed} breaks, the \gls{sed} can and will 
connect to another router or \gls{reed} in its range.  This happens 
automatically without the need for user interaction.  Even if the acting 
Network Leader breaks, the other routers will elect a new one among them.

To form the network in the first place, Thread employs special messages called
\gls{mle} messages. These are used to discover neighbors, test link quality
and distribute route configuration. The link quality in Thread is not
necessarily reflexive. This means that in a 802.15.4 network the link quality
from device A to B may differ from the link quality from B to A. As a result,
Thread can choose to route messages from B to A over an intermediate router and
ensure safe delivery. \gls{mle} messages are not just used during the
setup, but periodically utilized allowing the network to adjust dynamically.

\subsection{Transport Layer}

To actually deliver messages, every Thread device has to provide a
\gls{udp} implementation, the \gls{tcp} implementation is optional.

Starting with the authentication process, all communication in the network is
encrypted. Every device "must be specifically authenticated and authorized" to
join the network and complete a \gls{tls} handshake to agree on a common key 
\cite{thread_spec}. All further communication is then secured with a network 
key.

\section{Zolertia Z1}
The Zolertia Z1 mote data sheet was released in March 2010 and predates the 
initial release of Thread by 5 years. The equipped hardware on the board also 
dates back to the earlier stages of embedded systems with a wireless 
connection. Its most important feature is the CC2420 chip from Texas 
Instruments which brings full 802.15.4-compliant radio communication. The Z1 
allows up to 92 KB of program logic to be stored in flash memory, and provides 
8 kB of RAM. The data sheet states that the chip brings 16 MB of flash, but the 
linker script provided by the manufacturer only provided 92 KB.  As no further 
time was spent in investigating this discrepancy, the 92 KB of memory are
assumed. The Z1 features a TI MSP430 16 bit \gls{mcu} with up to 16 MHz clock
speed.

In comparison, the TI CC2538 32 bit \gls{mcu}, a device \gls{ot} already 
supports, features 32 kB of RAM, 512 kB of flash memory and a Cortex M3. All 
further already ported platforms also feature a 32 bit \gls{mcu} which hints
the first complications concerning the 16 bit Z1 platform.

\begin{figure}
\includegraphics[width=0.65\linewidth]{images/Z1.jpg}
\caption{Zolertia Z1 mote, the silver plate on the right covers the radio 
    chip. Image taken from \cite{Z1}}
\label{fig:Z1}
\end{figure}


\chapter{Methodology}

Projects such as the \gls{ot} stack utilize a \gls{hal}, which allows a 
developer to assume a reasonable hardware interface and write the application 
against it.  To actually build the executable, a specific \gls{hal} is chosen 
that maps the abstract interface to an actual hardware.

Obvious advantages are less code duplication and the core logic of the 
application is less exposed to errors as it may be tested independently. It is 
also easier to distribute the same application to a variety of hardware without 
any modifications. For example, Google utilizes a \gls{hal} to distribute 
Android to different cellphones.

The \gls{hal} of the \gls{ot} stack includes access to a 802.15.4  capable 
radio chip, non-volatile memory, hardware timers and various communication 
interfaces.

\section{Tools}

This section lists all the tools used and developed over the course of this 
thesis.

\subsection{Linker Map Analyzer}

In order to analyze the memory issues encountered during the development of
the solution, a Linker Map Analyzer was developed 
\footnote{\url{https://notabug.org/agentcoffee/stats}}. Using Python, it parses 
all information present in the map file and stores it in a two dimensional 
linked list. It is then possible to run queries over the sections of the 
resulting hex file.

For example, just a specific section may be printed, all sections in 
\texttt{.text} sorted by size, or just one function. This example is visualised 
in listing \ref{fig:link_analyzer}. The output of the linker map analyzer 
allowed for a estimate of how many functions need to be removed in order to fit 
the implementation into the provided flash.

%0x380   text       ot::Lowpan::Lowpan::Compress(ot::Message&, ot::Mac::Address const&, ot::Mac::Address const&, unsigned char*)
%0x402   text       _printf_i
%0x406   text       ot::Mle::Mle::HandleParentResponse(ot::Message const&, ot::Ip6::MessageInfo const&, unsigned long)
%0x428   text       addSetting.isra.1
%0x43a   text       ot::Cli::Interpreter::ProcessCounters(int, char**)
%0x48c   text       ot::Mle::Mle::HandleUdpReceive(ot::Message&, ot::Ip6::MessageInfo const&)
%0x4a2   text       ot::Lowpan::Lowpan::DecompressBaseHeader(ot::Ip6::Header&, ot::Mac::Address const&, ot::Mac::Address const&, unsigned char const*, unsigned short)
%0x4e0   text       mbedtls_sha256_process
%text: 0x18356(99158), listed: 0x18356(99158)
%
%Section table:
%...
%0x1602  bss
%0x161b  rodata
%0x18356 text

\begin{lstlisting}[
    caption={A sample output of the script with the arguments \texttt{-f 
    ot-cli-mtd.map -p -o -t -s text}. The number behind \texttt{text:} states 
    the current size of the \texttt{.text} section which itself is bigger than 
    the available flash memory in the Z1. The \texttt{\_printf\_i} corresponds 
    to the newlib implementation of the c library that is more memory 
    efficient. It is also interesting that two \gls{6lowpan} functions are 
    under the top eight biggest functions. The arguments taken by the functions 
    have been removed in order to maintain readability.},
    label={fig:link_analyzer},
    captionpos=b
    ]
...
0x380   text       ot::Lowpan::Lowpan::Compress(...)
0x402   text       _printf_i
0x406   text       ot::Mle::Mle::HandleParentResponse(...)
0x428   text       addSetting.isra.1
0x43a   text       ot::Cli::Interpreter::ProcessCounters(...)
0x48c   text       ot::Mle::Mle::HandleUdpReceive(...)
0x4a2   text       ot::Lowpan::Lowpan::DecompressBaseHeader(...)
0x4e0   text       mbedtls_sha256_process
text: 0x18356(99158), listed: 0x18356(99158)

Section table:
...
0x1602  bss
0x161b  rodata
0x18356 text
\end{lstlisting}

Running on Python 3.7, the script reads one linker map file and analyzes it
according to the arguments given. Obtaining the linker map file may be achieved
by invoking the linker with the argument \texttt{-Map=linker\_map\_file}. Usage
of the script is provided in table \ref{fig:link_analyzer_usage}.

\begin{table}
	\begin{tabularx}{\textwidth}{l | X}
		\multicolumn{2}{l}{\texttt{stats.py -f out.map [-p [-s text] [-i
		otMle] [-o]] [-t]}} \\ \hline
		\texttt{-p} & Prints all the entries in the linker map matching the selection
		criteria. \\
		\texttt{-s <section>} & Selects just entries in the specified section. \\
        \texttt{-i <object>} & Selects just entries that, in a C++ manner, are
		instantiated from object. This allows for example, listing all functions
		in the object Mle (Mesh Link Establishment). \\
		\texttt{-o} & Orders (sorts) all selected entries by size. \\
		\texttt{-t} & Prints a table of all sections with their size at the very end. \\
	\end{tabularx}
	\caption{The usage of the linker map analyzer explained in more detail.}
	\label{fig:link_analyzer_usage}
\end{table}

\subsection{Flashing}

The Z1 flash is written using a python script written by Chris Liechti and 
taken from the contiki project
\footnote{\url{https://github.com/contiki-os/contiki/tree/master/tools/zolertia}}.
The script is also hosted at the implementation mirror.

\section{Settings} \label{settings}

This section lists all the settings necessary for the implementation.

\subsection{Compiler Flags}

To compile the project, the MSPGCC-TI version 5.01.02.00 was used.

The \gls{ot} project used the following arguments to invoke the compiler.

\begin{tabularx}{\textwidth}{r X}
	\texttt{COMMONCFLAGS} & \texttt{-DNDEBUG -minrt -mlare -mmcu=msp430f2617
	-mhwmult=16bit -I/usr/msp430-elf/include -L/usr/msp430-elf/lib/large -g
	-fdata-sections -ffunction-sections -Os} \\

	\texttt{CFLAGS} & \texttt{-Wall -Wextra -Wshadow -std=c99 \$COMMONCFLAGS} \\

	\texttt{CXXFLAGS} & \texttt{-Wall -Wextra -Wshadow -std=gnu++11 -Wno-c++14-compat
	\$COMMONCFLAGS} \\

	\texttt{LDFLAGS} & \texttt{-Wl,--gc-sections -nostartfiles \$COMMONCFLAGS} \\
\end{tabularx}

The Server/Client implementation then used the following arguments to run the
compiler.

\begin{tabularx}{\textwidth}{r X}
	\texttt{CFLAGS} & \texttt{-Os -g -mmcu=msp430f2617 -Wall -Wpedantic
	-fpack-struct -std=c99 -Iinclude/ -I/opt/ti/mspgcc/include
	-Wl,-Map=out.map"} 
\end{tabularx}

\subsection{\gls{uart} settings}

A Linux system was used to develop the software for the Z1 and control the 
device. The necessary configuration is set using \texttt{stty}, short for set 
teletype, as can be seen in listing \ref{fig:stty}. The \texttt{stty} program 
is part of the GNU Coreutils package
\footnote{\url{https://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=tree;f=src;h=938a6f26722ec723c52a9b88b490761b8f42c281;hb=HEAD}}.

\begin{lstlisting}[
	caption={The options to configure the serial device for usage on the host.  
    The \texttt{/dev/ttyS0} corresponds to the actual serial device. The baud 
    rate is set to 115200. The option \texttt{min 1} tells the serial driver to 
    wait for at least one character before returning. Specifying 
    \texttt{-parenb} disables the generation of a parity bit. The 
    \texttt{crtscts} option enables flow control.},
	label={fig:stty},
	captionpos=b]
stty -F /dev/ttyS0 115200 min 1 -parenb crtscts
\end{lstlisting}

\subsection{\gls{ot} version} \label{ot_version}

The \gls{ot} source code was initially cloned from the original git repository
\footnote{\url{https://github.com/openthread/openthread/tree/6805cfa81e181cf35770d0f24cb42cbb86a88594}}.  
As changes had to be incorporated into the \gls{ot} core itself, the whole
repository is also hosted in a git repository
\footnote{\url{git@notabug.org:agentcoffee/openthread.git}} at the last commit
for this thesis.

\begin{figure} \includegraphics[width=\linewidth]{images/test_setup.jpg}
    \caption{The test setup. The two devices are connected and powered via 
    common micro \gls{usb} cables.}
\label{fig:test_setup}
\end{figure}

\section{Evaluation} \label{evaluation}

In accordance to the procedure given by \gls{ot} in \cite{ot:cert} to validate 
a new \gls{hal} port, the implementation is evaluated through the following 4 
steps. 

\begin{enumerate}
    
    \item Interaction with the command line interface. This point is fulfilled
        by executing a few commands, which is done during the next few points
        anyway.

    \item Building a Thread network and joining it with another device. By 
        powering one device alone, it detects that no other Thread network is 
        already present and shall start a new one. Powering the second device, 
        it should detect the already present Thread network and attempt to 
        join.  After successfully becoming a child node, the second device 
        shall be promoted to a router.
	
    \item Transmission speed. By sending seven \gls{icmp} echo requests from 
        one device to the other, the transmission speed is measured. The 
        \gls{rtt} is chosen as the method of evaluation.  \gls{rtt} measures 
        the time a packet is traveling from point A to B and the time it takes 
        for B to acknowledge the reception of the packet. In case of layer 3 in 
        the \gls{osi} model, the acknowledge does not happen with an \gls{ack} 
        frame, but with the same \gls{icmp} message.
	
    \item Re-attaching after a reset. After joining the Thread network, the 
        second device saves information about the currently joined Thread 
        network in its non-volatile storage. After resetting the device, it 
        shall automatically rejoin the same Thread network without user 
        intervention.

\end{enumerate}


\chapter{Implementation}

In this chapter, two different approaches to achieve the goal stated are 
presented.

The direct port tries to run the \gls{ot} stack directly on the Z1 by simply 
implementing a suitable \gls{hal}. This is the intended way of porting \gls{ot} 
to another hardware. After encountering various obstacles as described in 
\ref{first_approach}, a second approach to achieve is taken.

The host / client oriented approach involves rewriting the \gls{hal} of the 
\gls{posix} implementation already provided by Nest to work with the CC2420 
chip on the Z1.  This means developing a protocol over a \gls{uart} connection 
and a receiving logic on the Z1 that handles the communication with the CC2420, 
which is described in detail under section \ref{second_approach}.

\section{Direct Port} \label{first_approach}

This section details the challenges and possible solutions encountered while 
trying to port the \gls{ot} stack directly on to the Z1.

\begin{enumerate}

    \item The first problem that appears are predefined enums. Since a lot of 
        static values are hard coded in such enums, and not in 
        \texttt{\#defines}, the compiler tries to place them into 
        \texttt{int}s that correspond to 16 bits on the Z1. Unfortunately, a 
        lot of bit masks and values are bigger than $2^{16}$ which requires 
        them to either be rewritten, or compiled with a C++ compiler, as C++ 
        allows sized enums in its standard. This turns out to be a solvable 
        challenge, although multiple files that are not part of the \gls{hal} 
        have to be rewritten.

    \item Furthermore, the flash memory of the Z1 is divided into two parts.  
        This is due to the fact that the original instruction set architecture 
        on the 16 bit processor was only able to address $2^{16} = 65536$ bytes 
        of flash memory but the Z1 provides $93884$ bytes. This led to the 
        modification of the instruction set architecture to allow 20 bit 
        pointers, which are able to span the whole flash memory. The interrupt 
        routine could not follow the update, and so the interrupt vector has to 
        sit at the top of the $2^{16}$ byte flash and thus divides the whole 
        flash into two parts.

        The relevant parts of the linker file may be seen in figure 
        \ref{fig:z1mem}.  This rather unusual setup is not fully supported by 
        the compiler, and no real bin packing for sections is implemented. It 
        is possible to place whole sections in either region, but this does not 
        utilize the flash to its fullest potential. This implies that either 
        the project is small enough to fit in either region, or it is 
        sufficient that just the \texttt{.data} section goes in the upper flash 
        region, which is supported by the compiler. It is definitely possible 
        to assign each function section into either flash region, but this 
        requires a hard coded linker file and is not really optimal for ongoing 
        development.

    \item The 8 KB of RAM are mostly consumed by two 5352 bytes large state 
        objects, that hold the complete state of the \gls{ot} stack. This 
        leaves about 2840 bytes for the whole stack and heap. Further, all 
        already supported devices feature at least 28 KB of RAM. To ensure 
        correct functionality, memory checks to avoid stack and heap corruption 
        would  have been required. 

    \item To provide encryption, Thread includes the size-optimised 
        \texttt{mbedtls}\footnote{\url{https://tls.mbed.org/}} library. As the 
        CC2420 network chip on the Z1 provides a hardware implementation for 
        the used Counter with CBC-MAC algorithm, this library was replaced by 
        an interface to the CC2420 encryption capabilities.

    \item As the \gls{ot} stack uses the standard \texttt{printf} 
        implementation to format strings, the much smaller newlib
        \footnote{\url{https://sourceware.org/newlib/}} was included which 
        provides the size-optimised \texttt{iprintf} function which was used 
        instead of the standard \texttt{printf}.

\end{enumerate}

Over the course of developing the \gls{hal} for the direct port, it turns out 
that just the default example application already exceeds the available flash 
memory on the Z1, even with all the size optimistions mentioned above.

To visualize the issue of memory limitation, the linker map analyzer already 
introduced in section \ref{fig:link_analyzer_usage} comes in handy. As the 
biggest sections all correspond to functions that are essential to the correct 
operation of \gls{ot}, which can be seen in listing \ref{fig:link_analyzer}, a 
greater amount of smaller functions would have to be removed. This is possible, 
but stripping the \gls{ot} project in size while also keeping some core 
functionality alive, requires deeper knowledge of the \gls{ot} implementation.

This led to the conclusion that porting the \gls{ot} stack directly onto the Z1 
presents challenges that exceed the workload assigned for this thesis. As a 
result to this conclusion, another approach to reaching the goal stated is 
taken.

\begin{figure}
\begin{lstlisting}

MEMORY {
  ...
  RAM        : ORIGIN=0x1100,  LENGTH=0x2000 /* END=0x30FF, size 8192 */
  ...
  ROM (rx)   : ORIGIN=0x3100,  LENGTH=0xCEBE /* END=0xFFBD, size 52926 */
  HIROM (rx) : ORIGIN=0x10000, LENGTH=0x9FFF /* END=0x19FFF, size 40958 */
  ...
  VECT1      : ORIGIN=0xFFC0,  LENGTH=0x0002
  ...
  VECT31     : ORIGIN=0xFFFC,  LENGTH=0x0002
  RESETVEC   : ORIGIN=0xFFFE,  LENGTH=0x0002
}

\end{lstlisting}
\caption{The memory segment of the linker file for the TI MSP430. Non relevant 
    parts have been replaced by dots. It can be observed that the Read only 
    Memory (\texttt{ROM}), or Flash Memory, is cut by the interrupt vectors 
    from 1 to 31 and \texttt{RESETVEC} and ultimately continues in section 
    \texttt{HIROM}. The total size of the \texttt{ROM} and \texttt{HIROM} 
    section is 93884 bytes.}
\label{fig:z1mem}
\end{figure}

\section{Host / Client oriented Port} \label{second_approach}

The result for this thesis consists of a small protocol on top of the 
\gls{uart} connection that, in combination with the Z1, allows the 802.15.4 
compatible radio to be controlled.  The device runs a small server controlling 
the radio chip and providing access to received data. This setup is compareable 
to an external 802.15.4 compatible \gls{usb} antenna. An existing \gls{ot} 
\gls{hal} implementation was convinced to talk with the new antenna and is thus 
theoretically able to participate in an actual \gls{ot} network.

The so called host runs all the \gls{ot} logic and sends data to the
device, in this case the Z1. In the concept of splitting the radio controller 
and the \gls{ot} logic onto two different devices the radio controller, or 
device, is also called network co-processor. Thread mentions this concept but 
uses a different protocol to control the device. As no documentation or actual 
implementation can be found, the protocol described in the following section is 
developed \cite{ot:hostcontr}.
 
\begin{figure}
\includegraphics[width=\linewidth]{images/implementation_structure.png}
\caption{Implementation overview. All the parts in red have been implemented 
	over the course of this thesis.}
\label{fig:impl_ovw}
\end{figure}

\subsection{Protocol}

Sending one command and a variable-size payload, the protocol can be seen as a 
memory interface. The command corresponds to the memory location, the data
represents the data to be written there. As no extra information is 
transmitted, no additional features such as error correction or automatic 
retransmission are provided. Such extension may easily be added, but is out of 
the scope of this thesis.

The underlying \gls{uart} transmits with a baudrate of 115200 baud, no
parity, one stop and one start bit. A frame of the protocol contains the size
of the data, the command and at most 255 bytes of data. The size information
being sent first allows for easier assembly on the receiving part. As just one
byte is reserved for commands or memory addresses, up to 256 commands could be
implemented, although only a few are currently available. For a list of
commands, see table \ref{tab:prot_cmds}.

%TODO write data length taken
\begin{table}
\begin{center}
\begin{tabular}{l|l|l|l|}
\cline{2-4}
Bytes: & $1$ & $1$ & $0 \leq n \leq 255$\\ \cline{2-4}
& Size (n) & Command & Data \\
\cline{2-4}
\end{tabular}
\caption{The frame structure of the UART protocol}
\label{tab:prot_frame}
\end{center}
\end{table}

\begin{table} \begin{tabularx}{\textwidth}{l X} Command & Description \\ \hline
		%OTPLATRADIOGETIEEEEUI64 & \\
		%\hline

		OTPLATRADIOSETPANID & Sets the PANID on the CC2420, to enter the specified
		802.15.4 network.\\
		\hline
		OTPLATRADIOSETEXTENDEDADDRESS & Sets a 802.15.4 extended address for
		the source address match feature. See OTPLATRADIOENABLESRCMATCH and
		\cite[103]{802_15_4_std}.\\
		\hline
		OTPLATRADIOSETSHORTADDRESS & Sets the 802.15.4 short address. See
		OTPLATRADIOENABLESRCMATCH and \cite[103]{802_15_4_std}\\
		\hline
		OTPLATRADIOGETSTATE & Returns the debug state of the CC2420 as described in
				\cite[43]{cc2420_ds}.\\
		\hline
		OTPLATRADIOENABLE & Starts the CC2420 from its idle state.\\
		\hline
		OTPLATRADIODISABLE & Sets the CC2420 into its idle state.\\
		\hline
		OTPLATRADIOISENABLED & Returns true if the radio is enabled.\\
		\hline
		OTPLATRADIOSLEEP & Allows the CC2420 to sleep and save power.\\
		\hline
		OTPLATRADIORECEIVE & Sets the CC2420 explicitly into receive mode.\\
		\hline
		%OTPLATRADIOENABLESRCMATCH & Controls the Frame Pending bit in
		%Acknowledge frames sent to children as described here
		%\cite[103]{802_15_4_std}.\\
		%\hline

		%OTPLATRADIOADDSRCMATCHSHORTENTRY & \\
		%\hline
		%OTPLATRADIOADDSRCMATCHEXTENTRY & \\
		%\hline
		%OTPLATRADIOCLEARSRCMATCHSHORTENTRY & \\
		%\hline
		%OTPLATRADIOCLEARSRCMATCHEXTENTRY & \\
		%\hline
		%OTPLATRADIOCLEARSRCMATCHSHORTENTRIES & \\
		%\hline
		%OTPLATRADIOCLEARSRCMATCHEXTENTRIES & \\
		%\hline
		%OTPLATRADIOGETTRANSMITBUFFER & Not used\\
		%\hline
		%OTPLATRADIOTRANSMIT & Starts a transmission. This requires the PSDU to be
		%already present on the device.\\
		%\hline

		%OTPLATRADIOGETRSSI & Returns the last measured Received Signal 
		%Strength
		%Indicator (RSSI).\\
		%\hline

		%OTPLATRADIOGETCAPS & \\
		%\hline
		%OTPLATRADIOGETTRANSMITPOWER & \\
		%\hline
		%OTPLATRADIOSETTRANSMITPOWER & \\
		%\hline

		%OTPLATRADIOGETPROMISCUOUS & Fetches the promiscuous value
		%\cite[109]{802_15_4_std}.\\
		%\hline
		%OTPLATRADIOSETPROMISCUOUS & Sets the promiscuous value
		%\cite[109]{802_15_4_std}. A value equal to true instructs the radio to
		%pass all frames received to the next layer without any filtering.\\
		%\hline
		%OTPLATRADIOENERGYSCAN & \\
		%\hline
		%OTPLATRADIOGETRECEIVESENSITIVITY & Returns the current receive
		%sensitivity.\\
		%\hline
		%RADIOPOLLFRAME & Polls the device if a new frame has been received.\\
		%\hline
		RADIOSETCHANNEL & \\
		\hline
		RADIOSETPSDULEN & Sets the length of the \gls{psdu} to
		be sent.\\
		\hline
		RADIOSETPSDU & Sets the actual \gls{psdu}.\\
		\hline

		%OTPLATRADIORECEIVEDONE & \\
		%\hline
		%OTPLATRADIOTXSTARTED & \\
		%\hline
		%OTPLATRADIOTXDONE & \\
		%\hline
		%OTPLATDIAGRADIOTRANSMITDONE & \\
		%\hline
		%OTPLATDIAGRADIORECEIVEDONE & \\
		%\hline
		%OTPLATRADIOENERGYSCANDONE & \\
		%\hline
\end{tabularx}
\caption{The commands implemented by the protocol.}
\label{tab:prot_cmds}
\end{table}

\subsection{Host} \label{impl_16ms}

The host runs the logic of the \gls{ot} stack. As the \gls{hal}
implementation for \gls{posix}-compliant platforms already exists, it can be 
simply adapted to forward the relevant data to the client. The reference
implementation utilizes sockets to send data between different \gls{ot}
processes on the same system. This implementation enables the data to be sent 
over the air using the Z1 mote and allows the host to take part in an actual 
\gls{ot} network.

% TODO elaborate?
This is achieved by cutting the \gls{ot} stack in the radio implementation and 
rewriting the necessary functions to send information via the \gls{uart} bridge 
to the device. Communication with the device is only done where necessary, if 
information that is already available on the host side allows the function to 
finish, then no communication is taking place.

The existing socket design already requires the whole \gls{psdu} to be 
constructed on the host which is then simply sent to the device. The payload of 
the \gls{psdu} is encrypted on the host using the \texttt{mbedtls} library.

As the \gls{ot} stack requires an \gls{ack} (see section 
\ref{802_15_4_messages}) to be received within the following 16 milliseconds
after sending a frame, the \gls{ack} timeout has been raised to 40
milliseconds. In an attempt to minimise the overhead, the device already sends
\gls{ack} frames itself and instantly transfers the message to the host. In
theory, 16 milliseconds are enough for the acknowledge to reach the
transmitter, but altering it to 40 milliseconds allows for a much stabler
usage.

%TODO say something about usage and ref results
The host implementation with the corresponding \gls{hal} may be found at 
section \ref{ot_version}.

\subsection{Device}

The device starts by initialising all the necessary components on the Z1 board.
As the Z1 board features an adjustable oscillator, an iterative algorithm
anneals the desired 8 MHz CPU frequency. Once the \gls{spi}  and the \gls{uart} 
are running, the CC2420 is initialised.

With the periphery set up, the device waits for a command to be received over
the \gls{uart} bridge. As soon as a full command is available, it is
executed. In the regular case, this involves sending data to the CC2420. If  
the CC2420 receives a frame, it will alert the chip through an interrupt which 
schedules a read from the CC2420. The chip then copies the frame into an 
internal ring buffer and immediately transmits it to the host. The computer 
running the \gls{ot} logic will buffer the data sent in the serial pipe and 
serve it once needed. This immediately clears the internal buffer of the 
CC2420, as it only has enough space for 127 bytes.

The receiving module on the device is structured into 3 different buffers as 
visualised in figure \ref{fig:buffer_system}.

\begin{enumerate}

\item The first buffer is a standard ring buffer. The \gls{uart} receive 
	interrupt fills it with incoming bytes. If it detects that the next byte 
		will overflow the ring buffer, the \gls{cts} line is asserted, 
		indicating to the host that no more bytes may be sent. As soon as space 
		is available again in the ring buffer, the \gls{cts} line is released 
		again.  This guarantees that no data is lost and the execution is not 
		stalled for longer than necessary. 

\item The second buffer slowly assembles a full command. The main loop 
    periodically dispatches a routine that empties all available bytes from the 
        ring buffer into the second buffer. As soon as the command is completed 
        in the second buffer, it is copied into the third buffer and executed.  
        This allows the next command to be assembled while executing. As the 
        first byte in every telegram contains the length of the variable data 
        section \ref{tab:prot_frame}, it is used to detect when the whole 
        command is received.

\item From the third buffer, the received instruction is executed. If said 
    command requires data to be sent back, the information in question is 
        handed to an asynchronous sending routine. This second interrupt driven 
        routine transmits the data back to the host, where it is buffered in 
        the serial file descriptor.

%This function handles all communication with the CC2420 chip.

\end{enumerate}

%The protocol employs two buffers, a ringbuffer and a command buffer. While a
%\gls{uart} interrupt routine fills the ringbuffer with incoming bytes, a
%periodically called receive function assembles the full command in the second
%buffer by copying all the available bytes from the ringbuffer into a command
%oriented buffer. This command buffer can hold at least $1+1+255$ bytes.  As
%soon as the command in the command buffer is fully assembled, which is checked 
%with the \texttt{size} argument given in \ref{tab:prot_frame}, the line is 
%copied into a second buffer and executed. This allows a command to be sent 
%while the previous is still running.

In theory, the device may stack up to $2$ full commands plus the size of the 
ring buffer before the \gls{cts} line is set to logical $1$. As most commands 
do not require the maximum data length available, more commands may be stacked 
in practice.

In an effort to reduce the overhead of the serial communication, a received 
message from the CC2420 is instantly transmitted to the host.  The operating 
system will then buffer the message and deliver it to the \gls{ot} stack once 
needed.  This also reduces the overhead of reading the message on the host 
side, as the host does not have to wait for the serial communication and is 
just limited by the reading speed on the serial file descriptor.

If the message received by the CC2420 requires an \gls{ack}, the Z1 will 
instantly acknowledge the reception. The special acknowledge with data pending, 
required for routers with \gls{sed} as children, is not implemented, yet. 

\begin{figure}
    \includegraphics[width=\linewidth]{images/buffer_system.png}
	\caption{The 3 buffer system illustrated in detail. The ring buffer is
	filled by a \gls{uart} interrupt routine and periodically copied into
	the command buffer. If the command is fully assembled in the command buffer,
	it is moved to the executing buffer and executed. In this example, the
	\texttt{RADIOSETPSDULEN (0x1D)} command is currently executed while the
	command \texttt{RADIOSETPSDU (0x1E)} is still being built up in the
	command buffer. As the name says, \texttt{RADIOSETPSDULEN (0x1D)} sets the
	length of the \gls{psdu}, which is also the length of the payload of
	\texttt{RADIOSETPSDU (0x1E)}. The actual \gls{psdu} was set to
	\texttt{0x0A} for illustration purposes.}
\label{fig:buffer_system}
\end{figure}

The complete device implementation is available in a separate repository at
\footnote{\url{https://notabug.org/agentcoffee/z1_board}}, together with a 
flash script mentioned in section \ref{settings}. It also contains a Makefile 
with targets to compile, flash and reset the Z1.

\section{Usage}

The original executable has been extended with a low level debug framework that 
simply prints everything received and sent through the \gls{uart} bridge to a 
file provided through the \texttt{-d} argument. Passing it a pipe, previously 
created with \texttt{mkfifo}, allows observation of the log in real time as can 
be seen in figure \ref{fig:work_setup}. As the original \gls{ot} framework 
sends all logs directly to the system log, the logging framework has been 
modified to write all logs to the file descriptor 3 that has to be piped to a 
file or just \texttt{/dev/null} if it is of no interest. \gls{ot} will not work 
correctly if no pipe is passed.

After connecting and flashing the Z1, the corresponding character device has to 
be passed to the executable via the \texttt{-f} argument. Additionally, a node 
ID is required, using the \texttt{-n} parameter. The usage is specified in 
table \ref{fig:ot_usage}

\begin{table}
	\begin{tabularx}{\textwidth}{l | X}
		\multicolumn{2}{l}{\texttt{./ot-cli-ftd -f /dev/ttyUSB0 -n 2 -d 
		dbg.fifo}} \\ \hline
		\texttt{-f <device>} & The USB character device of the z1. \\
		\texttt{-n <node id>} & The node ID of this specific node in the 
		network.\\
        \texttt{-d <debug pipe>} & A file object the protocol log should be 
        written to. If it is not needed /dev/null has to be passed.\\
	\end{tabularx}
	\caption{The usage of the \gls{ot} logic.}
	\label{fig:ot_usage}
\end{table}

\begin{figure} \includegraphics[width=\linewidth]{images/work_setup.png}
	\caption{The typical developing setup. The two terminals at the top run the 
	\gls{ot} logic. The two terminals at the bottom show the debug output 
	of the protocol implementation. Currently, two frames can be seen being 
    sent from the left process to the right process via two Zolertia Z1 motes.  
    The top two terminals also show the results of four pings.}
\label{fig:work_setup}
\end{figure}

% Evaluation or Discussion if no measurements
\chapter{Results}

This thesis presents a functional implementation for the specified protocol 
together with a working \gls{hal} for \gls{ot}. As the implementation is just 
expected to underline the feasibility of such an external network co-processor 
it may still miss features for a full \gls{ot} compliance. For example, 
currently the special acknowledge frame with data pending flag is not 
implemented \cite[152]{802_15_4_std} as this feature is not needed for the 
proof of concept. Adding it is rather straight forward and no further pitfalls 
are expected.

\section{Evaluation}

The implementation was evaluated against the tutorial given in 
\cite{ot:tutorial} and defined in subsection \ref{evaluation}. The test setup 
can be seen in figure \ref{fig:test_setup}

\subsection{Interaction with the command line interface}

As can be seen in figure \ref{fig:cli_interaction}, the command line works 
fine. The \texttt{help} command lists all available commands. Some of them may 
require additional arguments, a full reference may be found in the official 
\gls{ot} repository
\footnote{\url{https://github.com/openthread/openthread/blob/master/src/cli/README.md}}.

\begin{figure}[h!]
    \includegraphics[width=\linewidth]{images/evaluation/help.png}
    \caption{The tail of the \texttt{help} command can be seen. As the command 
    line logic of \gls{ot} was not modified, it is expected to work the same as 
    before.}
\label{fig:cli_interaction}
\end{figure}

\subsection{Building a Thread network and joining it with another device}

After powering the first device and letting it establish a Thread network, the 
second device is started. Follwing some negotiation, which usually takes abut 5 
to 10 seconds, one device joins the other. The delay happens because the 
\gls{ack} may miss its time frame and thus invalidates the message, which 
crashes the current joining process. The reason was explained in further detail 
in section \ref{impl_16ms}.

This may result in device A joining the Thread network of device B, even though 
A was started earlier. This happens because after a failed attempt to join a 
network the joining device assumes that the network has failed and starts its 
own. As soon as the other device notices the presence of the second network, it 
attempts to join. Figure \ref{fig:build_thread_a} shows the joining process 
from the parents view. At first the \texttt{router table} contains only itself, 
because the child is not yet promoted to a router. After some time, the child 
is also promoted and shows up in the \texttt{router table}. One \gls{icmp} echo 
request has been sent and answered and the \texttt{router table} command shows 
that two devices are taking part in this Thread network.

In figure \ref{fig:build_thread_b}, the same process may be seen from the child 
side. After joining, the device automatically becomes a child and after some 
time it is promoted to a router. One \gls{icmp} echo request has been sent and 
answered. The \texttt{state} command tells us that the device has changed its 
state from child to a router and once the device has been promoted to a router, 
it also maintains a router table.

\begin{figure}[h!]
    \includegraphics[width=\linewidth]{images/evaluation/ping_a_r.png}
    \caption{This figure shows the leader of the established Thread network as 
    can be seen by the output of the \texttt{state} command while another 
    device joins the Thread network.}
\label{fig:build_thread_a}
\end{figure}

\begin{figure}[h!]
    \includegraphics[width=\linewidth]{images/evaluation/ping_b_r.png}
    \caption{This figure shows the child joining an existing Thread network.}
\label{fig:build_thread_b}
\end{figure}

\subsection{Transmission speed, \gls{rtt}}

The seven \gls{icmp} echo requests have been sent within 2 minutes and the 
devices were about 30 centimeters apart. Tables \ref{tab:ping_r_l} and 
\ref{tab:ping_l_r} list the results of the 14 pings.

The \gls{rtt} from the parent to the child is on average faster here. That 
could imply that in general a router takes less time to answer than the network 
leader.  This assumption requires more thorough testing but the fact that a 
network leader has more responsibilities than a router could explain the 
delayed \gls{icmp} response.

\begin{table}
\begin{center}
\begin{tabular}{l|l}
	Sequence & round trip time $(ms)$ \\
    1        & 1308 \\
    2        & 1272 \\
    3        & 1313 \\
    4        & 1298 \\
    5        & 1056 \\
    6        & 1216 \\
    7        & 1606 \\
    \hline
    Mean     & 1295 \\
\end{tabular}
    \caption{Seven \gls{icmp} echo requests from the child to the parent.}
\label{tab:ping_r_l}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{l|l}
	Sequence & round trip time $(ms)$ \\
    1        & 1115 \\
    2        & 871 \\
    3        & 1010 \\
    4        & 912 \\
    5        & 716 \\
    6        & 1204 \\
    7        & 1146 \\
    \hline
    Mean     & 996 \\
\end{tabular}
    \caption{Seven \gls{icmp} echo requests from the parent to the child as can 
    be seen in figure \ref{fig:rtt_a}.}
\label{tab:ping_l_r}
\end{center}
\end{table}

\begin{figure}[h!]
    \includegraphics[width=\linewidth]{images/evaluation/rtt_a.png}
    \caption{The seven \gls{icmp} echo requests and responses from the network 
    leader to its child.}
\label{fig:rtt_a}
\end{figure}

\subsection{Resetting a router and validate reattachment}

Figure \ref{fig:reset_3} shows the reset and re-attach procedure. After 
successfully joining the Thread network, the device is reset using the command 
\texttt{reset}. As the whole Thread stack is now in its original state, the 
whole interface has to be brought up again using \texttt{ifconfig up}. After 
restarting the Thread stack, the device immediately re-joins the network and 
assumes its previous role as a router. The \texttt{ping} at the very end 
confirms connectivity to the network. 

One \gls{icmp} echo request is sent to the network leader to confirm actual 
connectivity with the network.

\begin{figure}[h!]
    \includegraphics[width=\linewidth]{images/evaluation/reset_3.png}
    \includegraphics[width=\linewidth]{images/evaluation/reset_4.png}
    \caption{The reset and re attach procedure. Immediately after the reset, 
    the debug message informing about the physical state of the radio is seen. 
    There are two images as the total output had to be split over two pages of 
    terminal output.}
\label{fig:reset_3}
\end{figure}

\section{Conclusion}

The results show a possible implementation of the so called network
co-processor where the logic of the application runs on a different hardware
than the network related logic.

This thesis also acknowledges that the timing constraints introduced by the 
\gls{uart} connection may not be fixed at this stage of the \gls{ot} stack.  
While certain optimisations may allow for a faster \gls{rtt} or faster 
acknowledging of frames, the minimum time to transmit a full 802.15.4 frame to 
the device cannot be lower than 11 $(ms)$ on a baud rate of 115200.  Taking 
into account that it also takes another 11 $(ms)$ for the receivig device to 
deliver the frame to the host, this introduces a delay of at least 22 $(ms)$ 
simply due to transportation.

This may seem reasonable for a protocol as a whole, but as the delay is 
introduced at the \gls{hal} for a protocol stack that already has timing 
windows of 16 $(ms)$ \ref{impl_16ms}, it is not certain that the 22 $(ms)$ do
not violate other timing constraints. Through testing, this thesis assumes that
other timing windows are met, but cannot guarantee it.

The new \gls{hal} works most of the time, but seeing that already one timing 
window in the stack had to be altered for stable operation, this is probably
not the most efficient way to write a fully Thread certified \gls{hal} for
\gls{ot}.

Despite the solution still leaving room for improvement it presents an already 
working state of \gls{ot} utilizing the Z1. Of course it also allows 
applications to be developed against the \gls{ot} stack and tested over a real 
wireless connection.

Testing it in an actual Thread network requires the special \gls{ack} with 
data pending to be implemented \cite[152]{802_15_4_std}. The mechanism the 
\gls{ot} \gls{posix} implementation uses to determine which devices receive a 
data pending flag can be mirrored to the device.  All necessary commands may be 
added to the \gls{uart} bridge.

\section{Further Research}

% TODO Rephrase this
Implementing the missing \gls{ack} with data pending feature and testing the Z1 
together with other Thread devices would be the next step building on top of 
this thesis.  This would be the final step towards actual Thread certification 
for new \gls{hal} implementations \cite{ot:cert}.

Assuming the timing restrictions imposed by the serial communication line are 
too high to deal with, moving more of the \gls{ot} stack on to the device can
speed things up. This is already proposed by the \gls{ot} developers in form of 
a network co-processor, but no actual implementation was found at the time of writing 
\cite{ot:hostcontr}.

The Z1 is definitely a good candidate for a network co-processor implementation 
because of its power efficient operation, the 802.15.4 compatible radio chip 
and the rather fast \gls{uart} connection to the host. It also features a 
rather large memory and flash, compared to devices from its time.

As the protocol developed through this thesis is not Thread specific, it can be 
adapted for any project taking part in 802.15.4 networks as required.

\backmatter

% Use an optional list of figures.
%\listoffigures % Starred version, i.e., \listoffigures*, removes the toc entry.

% Use an optional list of tables.
%\cleardoublepage % Start list of tables on the next empty right hand page.
%\listoftables % Starred version, i.e., \listoftables*, removes the toc entry.

% Use an optional list of alogrithms.
%\listofalgorithms
%\addcontentsline{toc}{chapter}{List of Algorithms}

% Add an index.
\printindex

% Add a glossary.
\printglossaries

% Add a bibliography.
\bibliographystyle{alpha}
\bibliography{z1_ot}

\end{document}