Changeset 2785

Timestamp:

10/30/09 15:33:38 (4 weeks ago)

Author:

stevedh

Message:

@ 12

Location:

docs/Lowthane/ipsn10

Files:

• design.tex (modified) (8 diffs)
• discussion.tex (modified) (2 diffs)
• evaluation.tex (modified) (12 diffs)

docs/Lowthane/ipsn10/design.tex

@@ -96 +96 @@
 %% packets is volatile and potentially inaccurate.  Instead, w
 
-When presented with a new link, {\lowthane} initially use a {\emph{spot}} link quality metric, {\it e.g.} a hardware LQI estimate, to evaluate the quality of the link.  For each link, {\lowthane} maintains a Confidence value, currently the number of transmissions that have used that link.  Once this value crosses a certain threshold, the link is considered {\emph{mature}}, and is then evaluated using the overall link cost metric, ETX or expected transmissions.We use link-layer acknowledgement frames on all unicast traffic, and base our link quality estimate on the ack reception rate: consequently, our link estimator strongly prefers bidirectional links.  To account for the temporal variability of links, {\lowthane} maintains both long-term and short-term link estimates.  Both estimators use the same metric (ETX) but with different time horizons so as to manage the agility/stability tradeoff.
+When presented with a new link, {\lowthane} initially use a {\emph{spot}} link quality metric, {\it e.g.} a hardware LQI estimate, to evaluate the quality of the link.  For each link, {\lowthane} maintains a Confidence value, currently the number of transmissions that have used that link.  Once this value crosses a certain threshold, the link is considered {\emph{mature}}, and is then evaluated using the overall link cost metric, ETX or expected transmissions.We use link-layer acknowledgement frames on all unicast traffic, and base our link quality estimate on the ack reception rate: consequently, our link estimator strongly prefers bidirectional links.  To account for the temporal variability of links, {\lowthane} maintains both long-term and short-term link estimates.  % Both estimators use the same metric (ETX) but with different time horizons to manage the agility/stability tradeoff.
 %When presented with
 %a new link, {\lowthane} initially uses a {\emph{spot}} link quality metric,
@@ -127 +127 @@
 {\emph{Willingness}} value, which indicates the degree to which the
 advertising node is willing to forward traffic for other nodes.  Such a metric
-accounts for a heterogeneous network, in which battery-powered and mobile
-nodes would rather shift forwarding responsibilities to mains-powered or stationary nodes.
+accounts for a heterogeneous network, and allow battery-powered and mobile
+nodes to shift forwarding responsibilities to mains-powered or stationary nodes.
 
 \subsubsection{Default Route Formation}\label{sssec:default-route}
@@ -173 +173 @@
 
 Topology reports are sent to the {\controller} periodically using the default
-route; they are opportunistically piggybacked on data traffic whenever an
-application generates sufficiently frequent traffic.  The unpacked datagram in
+route; they are opportunistically piggybacked on data traffic whenever
+application traffic is sufficiently frequent.  The unpacked datagram in
 Figure \ref{fig:arch} shows how topology information is added to data traffic
 using an optional extension header; using this mechanism, the overhead is only
@@ -201 +201 @@
 allows state to be installed in the network to optimize active flows.  A
 {\controller} uses Route Install messages to update a node's Flow Table.  When a node
-receives a Route Install, it inserts or updates an entry in the Flow Table.  Each Route
+receives a Route Install, it creates or updates an entry in the Flow Table.  Each Route
 Install has two parts:
 
-\begin{itemize}
+\begin{itemize}\addtolength{\itemsep}{-0.5\baselineskip}
 \item{{\bf{Flow Match:}} The criteria used to determine whether a
   given packet matches a flow table entry.  By default {\lowthane} uses
@@ -306 +306 @@
 data, combined with their policy configuration.  Policy rules must currently
 be hard-coded into the route computation engine which runs Dijkstra's
-shortest-path over the link state.  We envision in the future adding a policy
-specification language similar to the packet classification languages used by
-{\tt packetfilter} or {\tt iptables}.
+shortest-path over the link state.  % We envision in the future adding a policy
+% specification language similar to the packet classification languages used by
+% {\tt packetfilter} or {\tt iptables}.
 
 \subsection{Multiple {\Controller}s}
@@ -363 +363 @@
 their contents have been discussed in previous sections.  First, The Default
 Route Table is used to maintain a stable back-channel to a {\controller}; its
-consistency is maintained by using a standard tree-formation protocol.%   When
+consistency is maintained by using the default route formation algorithm.%   When
 % inconsistencies are detected, broadcasts are started to resolve them.
 
@@ -371 +371 @@
 by listening to updates for same amount of time as the slowest topology
 update.  Due to link and node failures, the LSDB may contain false information.
-If allowed to persist, this can be extremely damaging since nodes may be
-instructed to continuously attempt to send messages across a non-existent
-link, wasting energy and increasing latency.  If a link fails on the default
+% If allowed to persist, this can be extremely damaging since nodes may be
+% instructed to continuously attempt to send messages across a non-existent
+% link, wasting energy and increasing latency.  
+If a link fails on the default
 route, local repair mechanisms reroute the packet around the failure, and
 update the Default Route Table.  If a link fails otherwise, the packet must
@@ -379 +380 @@
 route.  In this case, the packet will be re-routed to a {\controller} using the
 default route DAG.  The {\controller} notes the broken link in the source
-header, and after a small number of failures, it deletes the link from the
-LSDB so it will route around the failure.  The link may reappear in
-subsequent topology reports, if the failure was temporary.
+header, and after a small number of failures, deletes the link from the
+LSDB so it will route around the failure.%   The link may reappear in
+% subsequent topology reports, if the failure was temporary.
 
 The final table is the Route Install Table: it contains routes installed
 based on the Link State Database of a {\controller} at some point in time.  It
-is also not proactively maintained: when a link which is part of
-an installed route fails, the packet is forwarded to a \controller.  In
+is also not proactively maintained: when an installed route fails, 
+the packet is forwarded to a \controller.  In
 addition to removing the link from the LSDB after a small number of failures,
 the {\controller} will generate a ``Route Uninstall'' message so that the node
-router does not continue to use the same erroneous route.
+router does not continue to use the broken route.
 
 

docs/Lowthane/ipsn10/discussion.tex

@@ -36 +36 @@
 corresponding to the multicast group.  It would then unicast the message to a
 small number of nodes within each connected component (for reliability); these
-nodes would then run a dissemination algorithm like Trickle, where only group
-members participate.  This is essentially an implementation of of Levis's
+nodes would then run a dissemination algorithm like Trickle.  
+This is essentially an implementation of of Levis's
 Firecracker protocol \cite{firecracker}.
 
@@ -66 +66 @@
 \subsection{Limitations}\label{sec:limitations}
 
-\lowthane~has some important limitations which impact its suitability for some
-applications.
+% \lowthane~has some important limitations which impact its suitability for some
+% applications.
 
 \subsubsection{Stretch}

docs/Lowthane/ipsn10/evaluation.tex

@@ -13 +13 @@
 months in a real deployment.  On two experimental testbeds, we
 evaluate {\lowthane}'s scalability, performance, and resilience across a
-range of workloads and failure conditions.
+range of workloads and failures.
 
 \subsection{Questions}
@@ -366 +366 @@
 %% 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
-interest is ``transmissions per success,'' which counts the total number of link
-layer transmissions necessary to deliver a packet from a source to a destination.
-%  This flow was taken from an experiement on
-% Testbed A, with 4 other concurrent flows, and with the Flow Table being empty
-% at the beginning of the experiment.  %% This allows us to verify the basic
-%% functionality of {\lowthane}'s centralized route install.
-
-\begin{figure} [htb]
-\centering
-\includegraphics[width=0.7\columnwidth]{figs/BlowByBlow.pdf}
-\caption{Number of transmissions for each packet of a single flow.  The first
-  packet triggers a Route Install message, which reduces the path length from
-  6 to 2.}
-\label{fig:blowbyblow}
-\end{figure}
-
-Figure~\ref{fig:blowbyblow} shows {\lowthane}'s installation mechanism
-in action.  The first packet is forced to traverse the Default Route
-through a \controller, a four-hop path (plus two retransmissions, for
-a total of six transmissions).  However, this first packet prompts the
-installation of a shorter and more direct two-hop path which is used
-for all subsequent packets, reducing the stretch by a factor of two.
-We also see the effect of link failures: delivering the first packet
-to the {\controller} required two retransmissions for a total of six
-transmissions, and subsequent link failures occasionally require a
-retransmission.
+% \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
+% interest is ``transmissions per success,'' which counts the total number of link
+% layer transmissions necessary to deliver a packet from a source to a destination.
+% %  This flow was taken from an experiement on
+% % Testbed A, with 4 other concurrent flows, and with the Flow Table being empty
+% % at the beginning of the experiment.  %% This allows us to verify the basic
+% %% functionality of {\lowthane}'s centralized route install.
+
+% \begin{figure} [htb]
+% \centering
+% \includegraphics[width=0.65\columnwidth]{figs/BlowByBlow.pdf}
+% \caption{Number of transmissions for each packet of a single flow.  The first
+%   packet triggers a Route Install message, which reduces the path length from
+%   6 to 2.}
+% \label{fig:blowbyblow}
+% \end{figure}
+
+% Figure~\ref{fig:blowbyblow} shows {\lowthane}'s installation mechanism
+% in action.  The first packet is forced to traverse the Default Route
+% through a \controller, a four-hop path (plus two retransmissions, for
+% a total of six transmissions).  However, this first packet prompts the
+% installation of a shorter and more direct two-hop path which is used
+% for all subsequent packets, reducing the stretch by a factor of two.
+% We also see the effect of link failures: delivering the first packet
+% to the {\controller} required two retransmissions for a total of six
+% transmissions, and subsequent link failures occasionally require a
+% retransmission.
 
 %% shows the number of transmissions needed to
@@ -418 +418 @@
 \subsubsection{Concurrent Flows}
 
-Expanding our test from a single flow, we test {\lowthane}'s ability
+First, we test {\lowthane}'s ability
 to support a relatively large number of concurrent low bandwidth flows.  Concurrency stresses
 many aspects of a routing protocol, especially {\it reliability} and {\it
@@ -440 +440 @@
 \subfigure[\lowthane, with (centralized) and without (triangle) the
 route-installation optimization] {
-  \includegraphics[width=0.7\columnwidth]{figs/Control-double.pdf}
+  \includegraphics[width=0.65\columnwidth]{figs/Control-double.pdf}
   \label{fig:concurrent-smote-pdr}
 }
 \subfigure[AODV performance] {
-  \includegraphics[width=0.7\columnwidth]{figs/TinyAODV.pdf}
+  \includegraphics[width=0.65\columnwidth]{figs/TinyAODV.pdf}
   \label{fig:concurrent-aodv}
 }
@@ -494 +494 @@
   variability without the centralized optimization}.  We also note that {\it
   installing routes reduces
-  stretch}, as Figure \ref{fig:concurrency-smote-trans} illustrates.  Testbed A
-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.
+  stretch}, as Figure \ref{fig:concurrency-smote-trans} illustrates.  % Testbed A
+% 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}
@@ -549 +549 @@
 \begin{figure*}[htbp]
 \centering
-\setlength\SUBSIZE{0.55\columnwidth}
+\setlength\SUBSIZE{0.45\columnwidth}
 % good noise
 \subfigure[Concurrent load]{
@@ -584 +584 @@
 
 \subsubsection{Failure Reliability}
-Centralized systems are often criticized for being too slow to detect and
-react to remote events.  It is important that the optimization we introduced
+% Centralized systems are often criticized for being too slow to detect and
+% react to remote events.  
+It is important that the optimization we introduced
 does not break in the case of node and link failures.  Therefore, we next
 turn our attention to {\lowthane}'s robustness to 
@@ -602 +603 @@
 \begin{figure} [h]
 \centering
-\includegraphics[width=0.85\columnwidth]{figs/Single_Failure_Control-6.pdf}
+\includegraphics[width=0.65\columnwidth]{figs/Single_Failure_Control-6.pdf}
 \caption{Packet delivery ratio and control traffic statistics for a single
   flow amidst node failures: each vertical line indicates that four nodes
@@ -649 +650 @@
 \begin{figure} [h]
 \centering
-\includegraphics[width=0.85\columnwidth]{figs/Failure_Control-6.pdf}
+\includegraphics[width=0.65\columnwidth]{figs/Failure_Control-6.pdf}
 \caption{Packet delivery ratio and control traffic statistics for multiple
   flows amidst node failures.  Approximately half the nodes are involved in a
@@ -664 +665 @@
 \ref{fig:mfailure-smote-pdr} shows the same view of the data: at a high
 level, it appears that {\lowthane} still responds well to the network
-failures.  We see an interesting spike in control traffic around 1000 seconds
-into the experiment: at this point we have removed approximately $1/3$ of the
-network, and the DAG forms a brief loop, which persists for several minutes
-before the DAG re-forms and success rates return to near
-100\%.  We can also note that the transmission stretch necessary to deliver a
+failures.  
+At around 1000 seconds into the experiment and we have removed $1/3$ of the
+network, traffic spikes as a loop is formed and then resolved by the DAG
+maintenance protocol.
+% We see an interesting spike in control traffic around 1000 seconds
+% into the experiment: at this point we have removed approximately $1/3$ of the
+% network, and the DAG forms a brief loop, which persists for several minutes
+% before the DAG re-forms and success rates return to near
+% 100\%.  
+The transmission stretch necessary to deliver a
 packet oscillates throughout the experiment (Figure
 \ref{fig:mfailure-smote-trans}) as packets must be re-routed across longer paths.
@@ -674 +680 @@
 is in the process of recovering when the final nodes are killed, partitioning
 the network and making recovery impossible.
-
 Furthermore, Figures \ref{fig:sfailure-smote-pdr} and
 \ref{fig:mfailure-smote-pdr} demonstrate that the DAG control traffic remains
@@ -686 +691 @@
 in the face of substantial failure.  One design feature that we did
 not originally anticipate but which proved critical was {\it
-  explicitly uninstalling Flow Table state}.  While many protocols use
-timeouts to expire soft state, there is no ``natural period'' at which
-one can say this table state is stale; instead, it makes sense to
-allow it to persist until it is needed.  If we discover it is
-inaccurate, the packet will still generally be delivered using the
+  explicitly uninstalling Flow Table state}.  % While many protocols use
+% timeouts to expire soft state, there is no ``natural period'' at which
+% one can say this table state is stale; instead, it makes sense to
+% allow it to persist until it is needed.  
+If we discover (through a re-routed packet) that an installed path is broken, 
+the packet will still generally be delivered using the
 default route, but failing to uninstall or replace the route leads to high
 transmission counts as the source repeatedly tries to use a broken