Changeset 2778

Timestamp:

10/30/09 14:17:45 (4 weeks ago)

Author:

stevedh

Message:

edits

Location:

docs/Lowthane/ipsn10

Files:

• design.tex (modified) (1 diff)
• evaluation.tex (modified) (8 diffs)
• intro.tex (modified) (1 diff)
• overview.tex (modified) (1 diff)

docs/Lowthane/ipsn10/design.tex

@@ -262 +262 @@
 forward packets, in-network nodes take the following actions:
 
-\begin{enumerate}
+\begin{enumerate}\addtolength{\itemsep}{-0.5\baselineskip}
 \item{{\bf{Source Route:}} If a packet contains a valid source route, the node forwards the packet to the next router in the sequence.}
 \item{{\bf{Flow Table Entry:}} If a matching entry exists in the Flow Table, then it is used to forward the packet on to the destination.}

docs/Lowthane/ipsn10/evaluation.tex

@@ -1 @@
-\section{Evaluation}\label{sec:evaluation}
-
-This section evaluates the performance of {\lowthane} on several key
+\section{Analysis}\label{sec:evaluation}
+
+Hui has presented a complete IPv6 architecture for L2Ns which included a
+routing layer \ref{hui}, but there has been no systematic evalutation of the routing
+performance in the literature.  Since we embrace the IP architecture proposed
+by Hui and extend his routing mechanisms, this work is the first in-depth
+analysis the performance of a protocol which embraces a layered IPv6
+architecture in this class of networks.
+
+This section examines the performance of {\lowthane} on several key
 metrics across multiple networks.  In one application, we
 evaluate the performance of 57 nodes running {\lowthane} for over six
@@ -186 +193 @@
 Saturday, and 98.4\% on a Monday, reinforcing the key assertion that the
 distributed DAG effectively provides a reliable backchannel to the
-{\controller}.  % The same experiment on Testbed A and in TOSSIM yielded slightly better results, which were omitted here for brevity.
+{\controller}.  
+
+We use CTP, the leading open-source collection
+protocol as a point of comparison \cite{ctp}.  CTP provides only a subset of {\lowthane}'s
+functionality, routing packets from in-network nodes to a set of data sinks.
+In our comparison in Figure \ref{fig:collection-ctp-blip}, our implementation
+performs nearly as well as this specialized protocol in a test lasting one
+work day.  Much of the reliability in both cases comes from carefully engineered
+implementations, rather then any particular mechanism.
+% The same experiment on Testbed A and in TOSSIM yielded slightly better results, which were omitted here for brevity.
 
 %The distributed DAG is designed to provide a reliable mechanism for nodes to communicate with the {\controller}.  Figure~\ref{fig:collection-acme} provides a histogram of the packet delivery ratio (PDR) observed across three days on our real-world deployment.  The workload consisted of nodes transmitting data every 5 minutes to the {\controller}.  The nodes are using channel 19 (due to a poor deployment decision), and deployed in a very wi-fi intensive environment, leading to a slight degradation in performance during the work-week.  Regardless, we still see that the median PDR is 99.4\% on a Saturday, and 98.4\% on a Monday.  The same evaluation on Testbed A, and in TOSSIM yielded slightly better results, but are omitted here for brevity.
@@ -323 +339 @@
 
 
-\subsection{Centralized Route Installation}
+\subsection{Point-to-Point Routing}
+
+Building on source routing and the collection engine, {\lowthane} provides
+point-to-point routing.  Our point of comparison is AODV; while far from
+perfect, it provides a representative design point in the space of
+fully-distributed ad-hoc protocols.  
 
 %\begin{figure*}[htbp]
@@ -344 +365 @@
 %% mechanisms of {\lowthane} interact with the load and dynamic nature of
 %% L2Ns.  
+
+\subsubsection{Basic Operation}
+
 To see {\lowthane}'s basic mechanisms in action, we first focus on a trace of
 50 packets from a single flow running on testbed A.  The measure of
@@ -391 +415 @@
 %% common issue with centralized architectures is the latency necessary to
 %% communicate with a control point, this is a critical issue. 
+
+\subsubsection{Concurrent Flows}
+
 Expanding our test from a single flow, we test {\lowthane}'s ability
 to support a relatively large number of concurrent low bandwidth flows.  Concurrency stresses
@@ -428 +455 @@
   paths.  Floods from different flows also interfere with each other during
   route discovery, delaying discovery and incurring significant overhead.}
+\label{fig:aodv-compr}
 \end{figure}
 
@@ -469 +497 @@
 has a diameter of only 3 or 4, and so the consistent reduction in stretch by
 one hop is quite significant in relation to the network diameter.
+
+\subsubsection{AODV Comparison}
+
+AODV is an reactive distance-vector protocol which builds routes using flooded
+Route Request messages.  Nodes along the path forward traffic, generating
+Route Error messages back to the source when a link along the path fails.  A
+comparison AODV's results in Figure \ref{fig:aodv-compr} show that it
+achieves reasonable overall reliability, although far lower then {\lowthane}.
+Since AODV forms routes based on a flood, it does not have the well-developed
+link estimates {\lowthane} draws on when choosing routes.
+
+More striking is the huge difference in control traffic between
+the protocols during the route discover state.  Although additional
+optimizations to AODV may be possible to reduce this, {\lowthane} makes spare
+use of all control messages and never floods.  
+This is important because of the character of the AODV traffic-- like most
+ad-hoc protocols, it uses link-layer broadcast frames to exchange routing state.
+{\lowthane} also uses broadcasts, but in a much
+more limited fashion to build the DAG; all other control traffic is unicast.
+This is notable because when using asynchronous MAC protocols, sending a
+broadcast frame can cost an order of magnitude or more then a unicast frame.  
 
 %%  shows the
@@ -590 +639 @@
 Overall, the protocol is both
     {\it agile} and {\it reliable} in the face of significant network
-    disruption.
+    disruption; futhermore, it generates very little traffic {\it even when
+      responding to failure}.
 
 %% Thus, {\lowthane} appears to react correctly to node and

docs/Lowthane/ipsn10/intro.tex

@@ -1 +1 @@
 \section{Introduction}\label{sec:intro}
 
-This paper aims to address one of the main shortcomings of sensornet research: the lack of a routing protocol that efficiently supports all components of an application workload.  To expand further:
+% This paper aims to address one of the main shortcomings of sensornet research: the lack of a routing protocol that efficiently supports all components of an application workload.  To expand further:
 
-\begin{itemize}
-\item{{\bf{Workload:}} Traffic patterns are predominantly many-to-one collection, with a smaller but significant mix of point-to-point traffic.}
-\item{{\bf{Efficiently:}} Any solution must adhere to sensornet resource-constraints, and state and control overhead must be proportional to the data traffic.}
-\end{itemize}
+% \begin{itemize}
+% \item{{\bf{Workload:}} Traffic patterns are predominantly many-to-one collection, with a smaller but significant mix of point-to-point traffic.}
+% \item{{\bf{Efficiently:}} Any solution must adhere to sensornet resource-constraints, and state and control overhead must be proportional to the data traffic.}
+% \end{itemize}
 
-Many solutions do exist, but they have either only addressed one component of the problem, or solved the problem in another domain with limited applicability to sensornets.  Collection protocols~\cite{mintroute,ctp} provide reliable collection to a sink, but use grossly inefficient schemes for unicast communication.  Point-to-point protocols~\cite{s4-nsdi, tinyaodv, bvr} allow for communication between arbitrary pairs of nodes, yet make no provisions to support common-case collection.  Outside of sensornets, general networking platforms such as Ethane~\cite{ethane} provide compelling solutions, yet are based on assumptions that make porting anything beyond the high-level design to sensornets untenable.
+This work presents an analysis of {\lowthane}, the routing protocol at the
+core of {\tt blip}, the open IPv6 stack in TinyOS.  {\lowthane} is
+characterized by extreme attention to reducing control traffic and optimizing the
+common case of collection, while providing efficent point-to-point
+communication.
 
-We don't claim to present a highly-novel new routing protocol; rather our main contribution is a seemingly intuitive routing architecture designed from scratch that simply works.  We leverage the asymmetrical resource allocation typical of sensornets to push complexity to {\controller}s at the edge and minimize state and functionality in the network.  Our design revolves around controlling the tradeoff between state and stretch, and minimizing control traffic through a focus on data-driven design.  We embrace the open-standards approach to system design, and our solution, {\lowthane}, is in fact the default routing protocol for blip, a widely-used IPv6 adaptation network layer for sensornets.
+% Many solutions do exist, but they have either only addressed one component of
+% the problem, or solved the problem in another domain with limited
+% applicability to sensornets.  
+Among existing work, collection protocols~\cite{mintroute,ctp}
+provide reliable collection to a sink, but don't provide for
+unicast communication.  Point-to-point protocols~\cite{s4-nsdi, tinyaodv, bvr}
+allow for communication between arbitrary pairs of nodes, yet make no
+provisions to optimize common-case collection.  Outside of sensornets, general
+networking platforms such as Ethane~\cite{ethane} provide compelling
+solutions, yet are based on assumptions that make porting anything beyond the
+high-level design to sensornets impractical.
 
-Beyond presenting {\lowthane}, we provide an analysis from real-world experiments that seeks to answer the questions, how well does this general architecture compare to specialized point solutions, and how robust is it?  In this vein, we compare it to CTP for collection traffic, and TinyAODV for point-to-point traffic, focusing on reliability and overhead.  For robustness, we examine the functionality of {\lowthane} in the face of high traffic concurrency and significant network failures.
+{\lowthane} is not a highly novel new routing protocol; rather our main
+contribution is a seemingly intuitive routing architecture designed from
+scratch that simply works.  We leverage the asymmetrical resource allocation
+typical of sensornets to push complexity to {\controller}s at the edge and
+minimize state and functionality in the network.  Our design revolves around
+controlling the tradeoff between state and stretch, and minimizing control
+traffic through a focus on data-driven design.  We embrace the open-standards
+approach to system design, and our solution, {\lowthane}, is in fact the
+default routing protocol for blip, a widely-used IPv6 network layer for
+sensornets.
+
+Beyond presenting {\lowthane}, we provide an analysis from real-world
+experiments that seeks to answer the questions, how well does this general
+architecture compare to specialized point solutions, and how robust is it?  
+We compare to other protocols which solve a piece of the problem,
+CTP for collection traffic, and TinyAODV for
+point-to-point traffic.  For robustness,
+we examine the functionality of {\lowthane} in the face of high traffic
+concurrency and significant network failures.
 
 %This paper is about the future of routing in stationary sensor

docs/Lowthane/ipsn10/overview.tex

@@ -14 +14 @@
 \label{sec:overview}
 
-Before diving into the details, we begin with the {\lowthane}'s basic
-operation and design philosophy for point-to-point routing built atop
-collection routing.
+{\lowthane}'s basic
+operation and design philosophy builds 
+point-to-point routing built atop
+collection routing, tree reversal, and source routing.
 %{\lowthane} develops organically from prior work, and extends it to provide robust point-to-point routing.  
 At its core is a reliable channel from the low-power nodes to higher