Changeset 2749

Timestamp:

10/30/09 00:23:38 (4 weeks ago)

Author:

prabal

Message:

Checkpoint

Files:

• docs/Lowthane/ipsn10/related.tex (modified) (1 diff)

docs/Lowthane/ipsn10/related.tex

@@ -1 @@
-\section{Background}\label{sec:related}
-
-In this section, we examine existing solutions in the space, highlighting
-elements which serve as building blocks for our
-design and their shortcomings.  Creating a distinct control plane
-for routing is not a novel idea, and so we examine related works in 
-internetworking.  Such work served as inspiration for our design, yet we also
-discuss barriers that prevent such works from being naturally portable to L2Ns.
-
-\subsection{Existing Low-Power Protocols}
-
-Routing has been an integral part of L2Ns since their emergence, as
-data and commands had to be relayed between nodes.  Initially, as many of the
-deployments focused on various types of monitoring, the
-predominant communication paradigm was {\emph{collection-Oriented}}, or
-{\emph{many-to-one}} routing.  By association
-{\emph{dissemination-Oriented}}, or {\emph{one-to-many}}, routing also
-emerged because of the need to send commands to the nodes ({\it e.g.} for
-configuration).
-%   We examine the progression and state-of-the art for these
-% constrained L2N routing protocols.
-
-% In addition, as the set of potential application domains expanded, the need
-% for richer and fuller routing protocols became clear, {\it i.e.} those that
-% support unicast and multicast communication paradigms;  we
-% examine these in this section as well.
-
-\subsubsection{Collection-Oriented Protocols}
-
-Most collection protocols are tree- or DAG-based.
-MintRoute~\cite{mintroute} was one of the initial routing protocols for L2Ns.
-Starting with the gateway, or base station node, beacon messages 
- announce the cost to reach the gateway in terms of hops, as
-well as ETX, or expected transmissions. %%  ETX is calculated using the inverse
-%% of packet reception ratio (PRR) over a link, which was roughly approximated
-%% using an exponentially weighted moving average of received signal strength
-%% indicators (RSSI) for each packet. 
-%% In subsequent versions for a popularal
-%% platform, link cost estimation was done by using a chip link quality indicator
-%% (LQI), which is provided for every received packet.
-While MintRoute was
-successful, it's main shortcomings stemmed from the limited sophistication of
-its link estimation and loss response techniques, which reduced efficiency in
-difficult RF environments.
-
-The successor to MintRoute was CTP~\cite{ctp}.  CTP developed a more accurate
-link estimator, in which control and data traffic were used to inform link
-estimates, although two different link estimators were kept.  %% Furthermore,
-%% CTP allowed multiple destinations to serve as data sinks, in which case
-%% multiple trees were formed with each destination serving as a tree root.
-Multiple potential next-hop parents are maintained, although only
-one was used at any given time.  In one test, CTP displayed 97\%
-overall reliability in a difficult RF environment, as opposed to the 70\%
-reliability obtained by MintRoute.  
-
-CentRoute~\cite{centroute} provides centralized tree routing, allowing for
-dissemination of tasklets and collection of information in the
-Tenet~\cite{tenet} architecture.  A single node serves as the sink, and other
-nodes in the network send join request messages which are forwarded to the
-sink.
-%%   If the node is a direct
-%% neighbor of the sink, the sink replies with an accept message, and the node
-%% joins the tree by selecting the sink as its next hop.  Otherwise, if a node
-%% that is part of the tree overhears a join message, it forwards this message to
-%% the sink.  
-%% When the sink receives a join message (originating from a
-%% non-neighbor node), it waits for the same join message to arrive along
-%% multiple paths and selects the best path.  The sink then source routes the
-%% accept message to the originating node along this path, and the node
-%% appropriately sets its next hop. 
-Once created, the tree is frozen unless
-some threshold of failures occur, after which a node disengages and begins the
-join process anew.  This approach is limited to single destination routing,
-and also affords no flexibility for dynamic topology conditions unless links
-completely break.
-
-Koala~\cite{koala} is designed to provide mechanisms to enable efficient data
-retrieval from in-network nodes.  It presents centralized mechanisms similar
-to those used by {\lowthane}, in which nodes explore their neighborhood, and
-provide this information to a central controller, which subsequently installs
-an appropriate route in the network.  However, similar to CentRoute, these
-mechanisms are only targeted towards collecting data to a root.  Further, it
-does not position these mechanisms within a broader architecture or
-investigate their performance under different conditions; the focus of the
-work is a MAC-layer technique called Low Power Probing. %% , which enables more
-%% effective duty-cycling.
-
-TSMP~\cite{tsmp}, incorporated into the WirelessHART standard\cite{whart}, is a
-well-established industry approach that includes centralize scheduling of
-channel resources to achieve predictable latencies.  It operates at the link-layer, using channel
-hopping, and does not provide any routing capabilities specified in publicly
-available documentation.  Its tight scheduling of media accesses differs
-significantly from the functionality of our {\controller}s, which contain only
-soft state and are relatively asynchronous.
-
-
-%Koala \cite{koala} presents a design which contains mechanisms
-%similar to those used by {\lowthane} such as collecting topology and installing
-%routes within the network.  However, it does not position these mechanisms
-%within a broader architecture or investigate their performance under different
-%conditions; the focus of the work is a MAC-layer technique called Low Power
-%Probing.
-
-%% One of the shifts in ROLL has been toward an IPv6 based architecture, centered
-%% around 6LoWPAN~\cite{6lowpan}, the low-powered adaptation designed for L2Ns.
-Hui presented a complete IPv6 network architecture for L2Ns, which includes a
-low power link along with network and transport layers adapted to the unique
-characteristics of these networks \cite{hui}.  This work adapted collection to
-the IP architecture by conceptualizing it as choosing an IP default route.  It
-also provided unicast capabilities by allowing a controller to communicate
-with individual nodes by source routing the packet, forming the basis for
-triangle routing of intra-network traffic.  
-% However, such an approach also incurs unnecessarily high stretch, and
-% naturally forms bottleneck links around the controller.
-
-% However, the implementation presented relies on routing intra-network
-% traffic through a collection point to implement unicast traffic, leading to
-% unnecessarily high stretch.
-%%   Of particular interest to our work was
-%% Hui's contribution to reliable multi-parent tree-based routing, and confidence
-%% driven link estimation.  
-% This basic design represents the leading edge of collection research, and formed
-% {\lowthane}'s basic template; we extend it with optimizations for
-% point-to-point traffic.
-
-From these myriad examples of collection protocols, we drew the elements of a
-reliable control plane.  Dynamic and accurate link estimation is important to
-deal with the lossy nature of the medium, and data-path validation is helpful
-to prevent harmful routing loops.  Finally, nodes should exploit spatial
-redundancy by keeping a set of potential next hops rather than a single choice.
-
-%% the  foundation and inspiration
-%% for many of our algorithms and has been invaluable in helping us to frame our
-%% architecture.
-
-%% A final approach worth considering are receiver-oriented protocols such as
-%% ExOR.  This family of protocol forwards data by broadcasting packets and
-%% relying on receivers closer to a sink forwarding it.  They must contain a
-%% resolution protcol to suppress duplicates.  The inherent difficult is 
-
-\subsubsection{Other Routing Protocols}
-\label{ssec:existing-other}
-
-BVR~\cite{ref:bvr} is a geographical location-based routing protocol for
-L2Ns.  A set of landmark beacons are selected whose identity is known by all
-nodes in the network.  Every node is given a virtual coordinate, which is the
-vector of distances to all beacons in the network.  When a node wants
-to send a packet to a destination node, it greedily forwards the packet along
-routes that move it closer to the destination.  
-%% If it is unable to do this (i.e. gets stuck at some point), it forwards the packet to the beacon closest to the destination.  In the case that this beacon is not able to use greedy routing to forward to the destination, scoped flooding is used to find the destination.  As demonstrated in other papers~\cite{s4-nsdi}, 
-BVR suffers from poor transmission and routing stretch, particularly as the
-network grows in size \cite{s4-nsdi}.  %% Variations to improve performance trade
-%% off resources by maintaining the entire 2-hop neighbor table in memory.
-Another difficulty is that in such a network, the identity of the beacons must
-be known {\it a priori}, and can not be modified dynamically without a location
-service \cite{bvr-location}.
-%% .  A BVR location
-%% service~\cite{bvr-location} was designed, but struggled because it still
-%% necessitated significant network overhead and state.
-
-S4~\cite{s4-nsdi}, is designed to provide small stretch and state in order to
-enable scalable routing.  It utilizes a modified compact routing algorithm
-tailored for L2Ns. %%  A subset of nodes in the network are designated as beacons,
-%% with $\sqrt{N}$ being the optimal number.  A node $n$'s local neighborhood
-%% cluster is defined as the set of nodes whose distance to $n$ is less than or
-%% equal to the distance to their closest beacon.  Each node maintains routes to
-%% all other nodes in their cluster, and all beacons in the network.  A node can
-%% route to nodes outside its cluster by routing to the destination node's
-%% closest beacon.  
-%% However, this feature requires a directory service that the
-%% node can contact to obtain this information, and furthermore a beacon
-%% selection mechanism is needed, both for initial beacon selection, as well as
-%% under failure conditions, and the number of beacons can not be easily modified
-%% during runtime.  
-S4 has a theoretical worst case routing stretch of $3$,
-although published results indicate an average routing stretch of $1.2$ while maintaining
-$\mathit{O}(\sqrt{N})$ state.  Like BVR, deploying S4 would require also
-designing a distributed directory service.  Neither of these protocols
-optimize for the common workload where most traffic is destined towards an
-egress point; unlike S4 and BVR's homogeneous network, {\lowthane} starts with
-optimizing collection and emphasizing heterogeneity.
-
-  %% In section~\ref{sec:tossim}, we compare {\lowthane} to S4,
-%% demonstrating that we achieve greater reliability, with smaller stretch,
-%% state, and control traffic.
-
-%Finally Hui's work explores extending the
-%Internet architecture to L2Ns, and develops the algorithms necessary for
-%default route formation in \cite{hui}.  This work has been invaluable in
-%helping us to frame our architecture.
-
-\subsection{Ad-Hoc Networking Protocols}
-
-Finally, there is also an extensive literature on fully distributed routing
-protocols for ad-hoc wireless networks. % and L2Ns in particular. %% The
-%MANET~\cite{MANET} working group focuses
-%% on such protocols and issues.
-AODV~\cite{aodv} uses flooded RREQ messages to discover paths to destinations
-on demand, with intermediate nodes creating hop-by-hop entries for
-bidirectional flows.  DSR~\cite{dsr} is also an on-demand routing protocol,
-but uses source routing to route packets.  OLSR~\cite{olsr} is a link state
-algorithm that uses multipoint relays to reduce the flood of link-state
-advertisements.  802.11s, a draft mesh routing standard uses a variant of AODV
-called AODV-RM for intra-subnet point-to-point communication, but optimizes
-for an access network's workload by proactively building a routing tree towards
-egress points \cite{80211s}.
-
-These and other protocols provide point-to-point routing capabilities in
-wireless networks.  Both on-demand and link-state based solutions exist, but
-the focus is on providing reliable any-to-any delivery in networks with mobile
-nodes that are resource rich.  Consequently, most of these protocols have
-large control traffic and/or state requirements.  A protocol
-survey~\cite{ietf-protocol-survey} recently evaluated the specifications of
-the most widely used ad-hoc protocols against five criteria, and
-noted that in their current form no ad-hoc protocol meets more than
-three of the five criteria.%%   L2N-specific implementations of some of these
-%% protocols exists, such as TinyAODV and TYMO, but have received limited
-%% exposure and acceptance due to their poor (or non-existent) evaluations and
-%% limited feature-sets.
-
-
-\subsection{Internet Solutions}
+\section{Related Work}
+\label{sec:related}
+
+In this section, we review the prior work in three distinct areas:
+resource-constrained routing (e.g. low-power, memory-limited), ad hoc
+routing, and Internet routing.  This work synthesizes contributions
+from these distinct areas to create a new design point that no prior
+work occupies.
+
+\subsection{Resource-Constrained Routing}
+
+A number of collection protocols have been proposed over the years for
+data collection in sensor networks.  Most collection protocols create
+a collection tree, or DAG, along which data are sent to a root node.
+
+MintRoute~\cite{mintroute} was one of the first such routing protocols
+and it explored several techniques for selecting neighbors from a set
+of candidates that were larger than a node could fit into memory.  The
+Collection Tree Protocol (CTP)~\cite{ctp} succeeded MintRoute and used
+a more accurate, data-driven link estimator and incorporated next-hop
+diversity, achieving better data reliability than MintRoute.  In one
+experiment, for example, CTP delivered 97\% of data traffic in a
+difficult RF environment while MintRoute delivered only 70\%.
+
+MintRoute and CTP both use {\em distributed} topology formation but
+several protocols have explored {\em centralized} topology formation
+as well.  CentRoute~\cite{centroute}, a part of Tenet~\cite{tenet},
+uses a root node to control topology centrally (and disseminate
+tasklets to individual nodes).  Once created, the routing topology is
+frozen unless dramatic topology changes dictate rebuilding routes.
+CentRoute is limited to single-destination routing and does not adapt
+to limited topology dynamics.
+
+Koala~\cite{koala}, another centralized routing protocol, enables data
+retrieval from in-network nodes using mechanisms similar to those used
+by {\lowthane}.  Both protocols employ a technique in which nodes
+explore their neighborhood and forward this information to a central
+controller.  The controller installs routes directly onto network
+nodes.  However, similar to CentRoute, these mechanisms target
+collection routing and do not support general point-to-point routing.
+
+TSMP~\cite{tsmp} is an established industry approach that includes
+centralized scheduling of channel resources to achieve predictable
+latencies but it operates at the link-layer, using channel hopping,
+and does not provide routing capabilities.
+
+Hui and Culler presented an IPv6 network architecture that adapted IP
+routing to the unique characteristics of sensornet.  This work
+conceptualized collection within an IP framework as selecting a
+default route~\cite{hui}.  It also provided unicast capabilities by
+source routing along the collection reverse path, forming the basis
+for triangle routing of intra-network traffic.
+
+%% From these myriad examples of collection protocols, we drew the
+%% elements of a reliable control plane.  Dynamic and accurate link
+%% estimation is important to deal with the lossy nature of the medium,
+%% and data-path validation is helpful to prevent harmful routing loops.
+%% Finally, nodes should exploit spatial redundancy by keeping a set of
+%% potential next hops rather than a single choice.
+
+BVR~\cite{ref:bvr} is a geographical, location-based routing protocol.
+A set of landmarks are selected whose identities are known to all
+nodes in the network.  Every node is given a virtual coordinate, which
+is the vector of distances to the landmarks.  Packets are greedily
+forwarded along a gradient.  BVR suffers from poor transmission and
+routing stretch, particularly with network size size~\cite{s4-nsdi},
+and it requires a location service to map between node names and their
+dynamic addresses~\cite{bvr-location}.
+%
+S4~\cite{s4-nsdi} is designed to provide small stretch and state in
+order to enable scalable routing.  It utilizes a modified compact
+routing algorithm tailored for resource-constrained networks.  S4 has
+a theoretical worst case routing stretch of $3$, although published
+results indicate an average routing stretch of $1.2$ while maintaining
+$\mathit{O}(\sqrt{N})$ state.  Like BVR, S4 requires a location
+service.  More importantly, neither of these protocols optimize for
+the common collection workload where most traffic is destined towards
+an egress point.  In constrast, {\lowthane} starts with optimizing
+collection and build point-to-point on top of collection.
+
+\subsection{Ad-hoc Routing}
+\label{sec:related-manet}
+
+Mobile ad hoc networking (MANET) has explored many distributed routing
+protocols.  AODV~\cite{aodv} floods route-request messages to discover
+paths to destinations on demand, with intermediate nodes creating
+hop-by-hop entries for bidirectional flows.  DSR~\cite{dsr} offers
+on-demand routes, but employs source routing.  OLSR~\cite{olsr} is a
+link state algorithm that uses multipoint relays to reduce the flood
+of link-state advertisements.  802.11s, a draft mesh routing standard
+uses a variant of AODV called AODV-RM for intra-subnet point-to-point
+communication, but optimizes for an access network workload by
+proactively building a routing tree towards egress
+points~\cite{80211s}.  These and other protocols provide
+point-to-point routing capabilities in wireless networks.  Both
+on-demand and link-state based solutions exist, but the focus is on
+providing reliable any-to-any routing between mobile, resource-rich
+nodes.  As a result, these protocols exhibit greater control traffic
+or require greater state than is appropriate for our constrained
+setting~\cite{ietf-protocol-survey}.
+
+\subsection{Internet Routing}
 \label{sec:related-centralize}
 
-The concept of centralized routing, or separating the control and data planes,
-is not a novel one; we explore several existing protocols later in this
-section that embrace a centralized paradigm.  However, these solutions
-were designed primarily for the Internet, characterized by
-low churn and high bandwidth.  This is in stark contrast to the
-high-churn, low-bandwidth nature of typical L2N environments. %% Consequently,
-%% we discuss three factors that are critical to the success of centralized
-%% solutions, and while trivial to achieve in general networking environments,
-%% present the main obstacles to a centralized solution.
-
-% \subsection{Internet Routing Protocols}
-
-%% We discuss two separate bodies of work in this section: Centralized Internet
-%% Routing Architectures / Protocols, and IP-Based Ad-Hoc Networking
-%% Protocols(i.e. MANET~\cite{MANET}).
-
-% \subsubsection{Centralized Routing Architectures}
-
-The most conceptually similar work is Ethane~\cite{ethane}, %% , the successor to SANE~\cite{sane} and the predecessor to
-%% NOX~\cite{nox}, 
-a centralized architecture for implementing high-level
-security policies.  Designed for large enterprise networks, the network is
-divided into four tiers: controllers, %  (or multiple ones for fault tolerance),
-switches, end hosts or servers, and users.  %% Whenever a switch is connected to
-%% the network, it registers with the controller, and establishes a secure
-%% backchannel to it.  When an end host joins the network, the switch also
-%% reports this registration, reporting the class of device and attachment port.
-%% Finally, users are able to associate with one or more end host machines.
-%% Consequently, the controller maintains a complete and accurate view of the
-%% topology. 
-Network administrators specify high-level access policies, such as
-restricting which servers a certain user may communicate with.  Each switch
-maintains a flow table against which it can classify incoming packets using
-a packet header's 10-tuple.  If no applicable entry exists, the packet is
-forwarded to the controller.  The controller consults its policy
-specification, and installs flow entries along the path.
-%% {\lowthane} utilizes this concept of installing flow entries and forwarding
-%% packets belonging to unclassifiable flows to the controller.
-%Ethane~\cite{ethane} is the work that is the most similar to ours.  Designed
-%for large enterprise networks, the network is divided into three tiers: a
-%controller (or multiple ones for fault tolerance), switches, and end hosts or
-%servers.  
-% Whenever a switch is connected to the network, it registers with the
-% controller, and establishes a secure channel to it.  When a server or
-% middlebox joins the network, it also registers with the controller, reporting
-% the connecting switch and port.  Consequently, the controller maintains a
-% complete and accurate view of the topology.  Each switch maintains a flow
-% table in which it can match packet 5-tuples.  If no applicable entry exists,
-% the packet is forwarded to the controller.  The controller consults its policy
-% specification, and installs hop-by-hop
-% flow entries along the path.
-
-Key elements visible in this design include forming a channel and ``default
-routing'' to a controller, and maintaining global topology.  At a high level,
-{\lowthane} can be considered an adaptation or instantiation of the Ethane
-architecture.  Bringing Ethane together with low-power wireless
-brings out many of the assumptions underlying Ethane's operation, which must
-be addressed for the system to be practical; we explictly note three of the
-most important assumptions in the next section.
-
-% {\lowthane} also
-% addresses these issues, but the details differ significantly when no wired
-% infrastructure is available.
-
-%%  are present in the {\lowthane} design.  However,
-%% elements which Ethane takes for granted like {\controller} reachability and
-%% topology inference must be carefully addressed in the more dynamic L2N setting.
-
-%% Ethane assumes the availability of a secure and reliable channel to the
-%% controller, and also lends itself to trivial construction of a global topology
-%% view.  Network switches all have ample bandwidth and memory, allowing Ethane
-%% to support 70,000 flows / second at line speeds.  Finally, Ethane operates on
-%% top of layer 2 switching, which performs automatic failure rerouting to direct
-%% a packet to the addressed next hop.  While we discuss Ethane's successor,
-%% NOX~\cite{nox}, further in chapter~\ref{ch:player-centralized}, we note that
-%% architecturally it is the same as Ethane and hence suffers from the same
-%% limitations in the context of ROLL.
-
-A number of other centralized internet routing designs exist, which we mention
-briefly for completeness.  Feamster's Routing Control Platform, implemented by
-Caesar, made the case for separating the control aspect of routing from
-routers \cite{feamster-separating, caesar-rcp}.  Greenberg {\it et al.}
-present 4D~\cite{4d,tesseract}, a general framework for separating routing from routers.
-The framework consists of four components: a decision plane, a dissemination
-plane, a discovery plane, and a data plane.
-
-
-  %% Designed for both intra-AS (autonomous
-%% system) and inter-AS routing, 
-%% The motivation was that by distributing all
-%% aspects of routing, interactions became increasingly complex, heavy bandwidth
-%% usage resulted from topology changes, and forwarding loops and routing
-%% failures that were incredibly difficult to diagnose continually presented
-%% themselves.  To alleviate such difficulties, RCP serves as the primary
-%% interaction point for all routers within an AS.  %% By participating in the
-%% network, RCP was able to obtain a complete view of the topology. 
-%% A network
-%% operator could specify the routing policy at a single place (which typically
-%% was to simply mimic that of a fully-meshed iBGP AS), and then the RCP node
-%% would advertise the correct route to each router in the network.
-%% RCP would
-%% then serve the role of an egress router in communicating routing information
-%% with other AS's using eBGP (allowing for a smooth incremental deployment). 
-%%  As
-%% an ideal end-state, all AS's would have an RCP, and these RCP's would
-%% communicate with each other to exchange routing information.
-%% Caesar {\it et al.} presented an actual design and implementation of an
-%% RCP~\cite{caesar-rcp}.  %% Leveraging the existing OSPF and BGP protocols in
-%% place in most existing networks, the implementation had three distinct
-%% components: an IGP Viewer, a BGP Engine, and a Route Control Server (RCS).
-%% The IGP Viewer obtains IGP topology information by building adjacencies with
-%% routers in the network.  The BGP Engine learns BGP routes from the routers,
-%% and also communicates routing assignments to each router.  Finally, the RCS
-%% uses the information obtained by the other two components to compute routing
-%% assignments according to some specified policy, which currently defaults to
-%% full-mesh iBGP configurations. 
-%% A key decision was distributing RCS nodes to avoid creating a single point of
-%% failure, but they are not precise replicas and there are only loose
-%% consistency requirements. %, which are detailed in the paper.
-%% While the creation of a distinct control hierarchy certainly permeates our
-%% design, the practicality of RCP for L2Ns is limited.  
-%% However, the design focuses on only
-%% the intra-AS aspect, leveraging full underlying IP and TCP connectivity, as
-%% well as OSPF and BGP for information dissemination, which neither exist nor
-%% are practical in L2Ns.  A key part of our design involves designing
-%% mechanisms that provide this underlying connectivity and accurately
-%% constructing and maintaining global topology views. %%  Furthermore, full
-%% consistent connectivity is maintained by all nodes in the network at all times
-%% (often through flooding of Link State Advertisements), resulting in
-%% significant memory and network overhead, as opposed to on-demand schemes that
-%% are often a better fit for ROLL traffic patterns.  The lossy and dynamic
-%% nature of low-power wireless would only exacerbate network congestion in such
-%% an architecture.  Finally, their attempts at reducing overhead relies on
-%% prefix-based IP addressing, conflating node address and geographical location,
-%% while ROLL networks primarily embrace flat-label based addressing schemes.
-
-%% decision plane, composed of a single logical decision element (which is
-%% replicated for fault tolerance), serves as the {\emph{network brain}}, serving
-%% as the interface for network-wide policy specification, which is subsequently
-%% communicated to individual routers and switches.  The dissemination plane is
-%% tasked with creating the logical channels between the decision element and
-%% each router and switch, providing a medium for control information flow,
-%% independent of the state of the data plane.  The discovery plane refers to the
-%% process in which each router/switch discovers its own capabilities, its
-%% neighboring routers/switches (including those in other ASes), and communicates
-%% this information across the dissemination plane to the decision element,
-%% allowing for the creation of a global view of the network.  Finally, the data
-%% plane is greatly simplified, responsible only for forwarding packets according
-%% to the forwarding table entries installed by the decision element.
-%% As a framework paper, 4D does not provide any specific instantiations of any
-%% of the components.  
-%% Although targeted towards the general Internet,
-%% the same modularization applies in the context of ROLL as well; our routing
-%% architecture for L2Ns can roughly be
-%% decomposed into the same four components.  This componentization is
-%% particularly effective in highlighting the characteristics that differentiate
-%% L2Ns from the general Internet.  The dissemination plane must be built over
-%% a series of lossy unreliable links, in which the {\emph{optimal}} paths are
-%% potentially shifting.  %% Low power wireless also complicates the
-%% discovery plane, as there is a degree of dynamicity, even if the nodes
-%% are physically stationary, and also power duty cycles that reach 0.1\% and
-%% below.
-%% Furthermore, energy constraints prohibit excessive control traffic, which
-%% complicates communication of this discovery information to the decision plane.
-%% Finally, the data plane must provide certain reliability and delivery
-%% guarantees in the face of lossy and moving paths.  Yan {\it et al.} present
-%% Tesseract~\cite{tesseract}, a faithful instantiation of the 4D framework and
-%% concept.  %% Switches use periodic beaconing to determine their
-%% neighboring nodes, as well as their own capabilities, and then transmit this
-%% information to a {\emph{decision element}}, which forms the basis of the
-%% decision plane.  Path explorer messages are flooded through the network to
-%% enable the building of the dissemination plane.  Subsequently, the decision
-%% element sends all control messages to switches using source routes, and in
-%% turn, these switches reverse these source routes for sending information to
-%% the decision element.  The decision plane is implemented as an abstract model,
-%% in which specific algorithms are separated from the underlying link
-%% technologies, to provide an element of portability.  To provide robustness at
-%% the decision plane level, multiple decision elements are maintained at any
-%% given time, with all information being fully replicated across all of them.
-%% However, only one of them is a master (i.e. active) at any given time, while
-%% the rest are only used in the case of a hot standby.  The master is chosen
-%% through a leader-election process and arbitrarily assigned priorities.
-%% Security also plays a large role in Tesseract, with numerous mechanisms to
-%% enable encryption, certification, and authentication.
-%% Tesseract also provides the fully connected best path routing, which
-%% necessitates large amounts of control traffic, and state at the nodes that
-%% scales with the size of the network. %% The
-%% dissemination plane relies on source routing in both directions, stripping the
-%% switches of any local flexibility to deal with unreliable links, and dynamic
-%% topology shifts, as is common in L2N networks.  This results in additional
-%% control traffic for every instance of packet delivery failure, as does the
-%% need for full information at decision elements.
-
-
-%\begin{itemize}
-%\item{Tempest}
-%\item{FIRE}
-%\end{itemize}
-
-% \subsubsection{Stable Backchannel To Centralized Controller}
-
-\subsection{Towards a Hybrid Solution}
-
-From this disparate related Internet work, we distill a three requirements for
-successful centralized control. 
-\begin {description}
-\item[Reliable Path to Centralized controller] 
-
-A logical controller serves as the brain of the network, gathering
-information from all the routers in the network, and disseminating
-control commands.  One of the key implications of this role hierarchy is the
-need for a stable channel between the controller and all routers in the
-network at all times.  %% In many cases, this channel uses logically different
-%% links than the data plane, as its reliability and stability must be ensured.
-In large wired networks, creation of this channel is simplified by underlying
-data link layers: in Ethernets, the
-underlying layer-2 spanning tree algorithm provides reachability between all
-switches and end-hosts in a subnet.%% , and lookups can be accomplished using ARP.
-%% This is feasible because of the local broadcast nature of communications on a
-%% subnet.  Extending this reachability across multiple subnets can be done by
-%% introducing layer-3 routing elements as well.  Furthermore, once this channel
-%% has been established, it remains relatively stable, except in cases of severe
-%% congestion or physical partitioning, which are outside of the scope of our
-%% problem.
-% In contrast, no such natural mechanisms exist in L2N environments, and so the
-% network layer must build a robust path to the controller.  
-% Much
-Collection protocols may be used to provide just this functionality.
-%% The
-%% link-layer provides only single-radio-hop communications, with no inherent
-%% mechanisms for building neighbor tables.  
-%% Networks can be relatively deep,
-%% with diameters of 20 or more hops possible~\cite{ietf-industrial}.
-%% Furthermore, the quality of links vary widely, both spatially and temporally,
-%% creating a lossy path that is highly dynamic even without mobility.
-%% Finally, this channel must be maintained with minimal control traffic and
-%% network overhead, per the requirements outlined previously.
-\item[Consistent Global View of Topology] 
-One benefit of centralized routing is the ability to make routing decisions at
-a central location that has complete information about the state of the entire
-network. %%  In to order to create such a global view, all the elements of the
-%% network must register upon joining, and then provide updates of new neighbors
-%% and changes in the state.
-%%   In many existing solutions, there are periodic
-%% heartbeats that are sent in the form of link state advertisements, which
-%% allows the controller to maintain this global view.
-Three main factors complicate this task in L2Ns: control traffic restrictions,
-memory constraints, and dynamic topology.  
-Only a trickle of bandwidth is generally available to propagate network state towards
-a control element.
-%% Control traffic must not exceed
-%% the data rate, and so consistent periodic link state advertisements with
-%% updates sent to the controller are not practical.  %% Furthermore, the
-%% loss-response ROLL criteria dictates that control traffic in response to a
-%% loss must be limited to active paths or the single-hop broadcast domain,
-%% preventing triggered global updates. 
-Links exhibit temporal
-and spatial variability, which complicates %: links are not binary, so 
-maintaining a consistent
-view of network links. % qualities is difficult. %% would require significant amounts of control
-%% traffic. 
-Finally, memory constraints prevent individual nodes from
-maintaining state for all nodes in the network, or even the single-hop
-broadcast neighborhood.  Therefore, forming the complete topology may
-not be possible.%; we investigate the extent to which this is necessary.
-
-%% , leading to the unavailability of needed information,
-%% even if control traffic was not problematic.
-
-\item [Providing Reliability Over Lossy Links]
-The target environment for the majority of existing routing protocols is often
-highly-reliable, in the form of either wired links, or single-hop wireless
-links that provide relatively high reliability, through both link-layer and
-typically transport layer retransmissions.
-In L2Ns, the low-power nature of the ratio leads to a small
-Signal-to-Interference-and-Noise Ratio (SINR) on many links.  As demonstrated
-by Srinivasan {\it et al.} \cite{underlying}, the SINR of these links is often on
-the cusp of the necessary threshold to receive a packet, which results in
-bimodal links due to variations in signal strength and interference levels.
-Consequently, accurate link estimation and local repair techniques are critical.%% , both in accurately
-%% calculating a links quality/cost, and also in identifying and accounting for
-%% temporal shifts in these link qualities in order to minimize transmission
-%% stretch while maintaining reliability.
-\end{description}
-
-Although it is not obvious that any element of centralized control is a
-natural fit for L2N routing since existing centralized solutions rely on
-assumptions which do not automatically hold in this setting, research in the
-sensor network literature can be re-cast to help achieve the necessary
-prerequisites.
-
-%% policy
-% Futhermore, none of the related wireless work we have considered has addressed
-% the need for policy routing in wireless networks.  The ability to optimize for
-% metrics other then ETX or hop-count, and to do so ``on the fly'' becomes
-% increasingly important as networks begin to be composed of devices with
-% different power levels, processing rates, and security capabilities, it
-% becomes desirable to have a framework with which to tie together all these
-% metrics and optimize over the joint metrics and policy space.
-
-
-%% Finally, one way of providing effective routing is to utilize meaningful, or
-%% routable, addressing schemes.  One of the reasons that IP prefix-based routing
-%% is effective is that IP-addresses often tie together a name and geographical
-%% location.  %% In other words, except in very rare cases (such as Mobile IP
-%% %% solutions), all IP addresses with a shared prefix (of varying length depending
-%% %% on the size of subnet) are geographically co-located, allowing remote routers
-%% %% to maintain a single routing entry for that block of addresses.
-%% This reduces
-%% both memory state at routers, and the size of control traffic.
-%% This conflation of address and location is difficult in L2Ns.%%   We discussed
-%% %% examples of this in section~\ref{ssec:existing-other} in the form of
-%% %% geographic routing and compact routing schemes. 
-%% The challenge in implementing
-%% such a design is the dynamic nature of the network \cite{shenkergeo}.  Varying link qualities
-%% cause optimal routing paths to change, which would imply that the router's
-%% address would have to adjust accordingly.%%   This would require a lookup service
-%% %% for nodes to report updates to, and request lookups from.  This is in fact one
-%% %% of the main shortcomings of proposed geographic and compact routing schemes in
-%% %% the L2N space.  Despite the shortcomings of existing solutions, this may be a
-%% %% potential avenue that warrants additional research.
-
-
-
-
-
-%Multiprotocol Label Switching~\cite{mpls}, or MPLS, is a commonly used example of centralized routing in large networks.  Network operators setup explicit paths, often either to provide QoS or VPN services, by installing label entries at Label Switch Routers in the network.  Packets then carry a label, or even potentially a stack, which are attached at Label Edge Routers, allowing for fast lookups at each Label Switch Router.  This setup assumes a relatively static network, and paths are manually set-up, with no clear correlation with data traffic.
-
+Centralized routing is hardly a novel concept and we explore several
+existing protocols in this section that embrace a centralized design.
+The critical distinction is that these earlier solutions were designed
+for wired networks characterized by low churn, high bandwidth, and
+significant memory.  These assumptions do not hold in sensornets which
+exhibit high-churn, low-bandwidth, and high resource-constraints.
+
+Ethane~\cite{ethane} is the work that is architecturally most similar
+to ours.  Designed for large enterprise networks, Ethane divides the
+network into four tiers: controllers, switches, hosts, and users.
+Network administrators specify high-level access policies.  Each
+switch maintains a flow table against which it can classify incoming
+packets based on header fields.  If no applicable entry exists, the
+packet is forwarded to the controller where the controller consults
+its policy specification, and installs flow entries along the path.
+
+We adopt several aspects of Ethane's design including ``default
+routes'' to a controller and maintaining global network topology
+centrally.  Although architecturally similary, low-power wireless
+links expose many assumptions underlying Ethane's operation, which
+must be addressed in our context.  Among the (invalid) assumptions are
+(i) a reliable path exists to the central controller; (ii) a
+consistent global view of the topology is available; and (iii) links
+are generally stable.  None of these assumptions hold in a wireless
+sensornet.
+
+Other centralized Internet routing designs exist, which we review
+briefly for completeness.  The Routing Control Platform architecture
+makes the case for separating the control aspect of routing from
+routers~\cite{feamster-separating, caesar-rcp}.  Greenberg {\it et
+  al.}  present 4D~\cite{4d,tesseract}, a general framework for
+separating routing from routers.  The framework consists of four
+components: a decision plane, a dissemination plane, a discovery
+plane, and a data plane.
+
+
+
+%% {\bf OLD STUFF BELOW}
+
+
+%% highlighting aspects that
+%% influenced our thinking and highlight aspects of the prior work that
+%% we adopt, and draw a dis directly, and contrast our
+
+%% examine some of the existing solutions in
+%% the space, highlighting elements which serve as building blocks for
+%% our design and their shortcomings.  Creating a distinct control plane
+%% for routing is not a novel idea, and so we examine related works in
+%% internetworking.  Such work served as inspiration for our design, yet
+%% we also discuss barriers that prevent such works from being naturally
+%% portable to L2Ns.
+
+
+
+%% \subsection{Existing Low-Power Protocols}
+
+%% Routing has been an integral part of L2Ns since their emergence, as
+%% data and commands had to be relayed between nodes.  Initially, as many of the
+%% deployments focused on various types of monitoring, the
+%% predominant communication paradigm was {\emph{collection-Oriented}}, or
+%% {\emph{many-to-one}} routing.  By association
+%% {\emph{dissemination-Oriented}}, or {\emph{one-to-many}}, routing also
+%% emerged because of the need to send commands to the nodes ({\it e.g.} for
+%% configuration).
+%% %   We examine the progression and state-of-the art for these
+%% % constrained L2N routing protocols.
+
+%% % In addition, as the set of potential application domains expanded, the need
+%% % for richer and fuller routing protocols became clear, {\it i.e.} those that
+%% % support unicast and multicast communication paradigms;  we
+%% % examine these in this section as well.
+
+%% \subsubsection{Collection-Oriented Protocols}
+
+%% Most collection protocols are tree- or DAG-based.
+%% MintRoute~\cite{mintroute} was one of the initial routing protocols for L2Ns.
+%% Starting with the gateway, or base station node, beacon messages 
+%%  announce the cost to reach the gateway in terms of hops, as
+%% well as ETX, or expected transmissions. %%  ETX is calculated using the inverse
+%% %% of packet reception ratio (PRR) over a link, which was roughly approximated
+%% %% using an exponentially weighted moving average of received signal strength
+%% %% indicators (RSSI) for each packet. 
+%% %% In subsequent versions for a popularal
+%% %% platform, link cost estimation was done by using a chip link quality indicator
+%% %% (LQI), which is provided for every received packet.
+%% While MintRoute was
+%% successful, it's main shortcomings stemmed from the limited sophistication of
+%% its link estimation and loss response techniques, which reduced efficiency in
+%% difficult RF environments.
+
+%% The successor to MintRoute was CTP~\cite{ctp}.  CTP developed a more accurate
+%% link estimator, in which control and data traffic were used to inform link
+%% estimates, although two different link estimators were kept.  %% Furthermore,
+%% %% CTP allowed multiple destinations to serve as data sinks, in which case
+%% %% multiple trees were formed with each destination serving as a tree root.
+%% Multiple potential next-hop parents are maintained, although only
+%% one was used at any given time.  In one test, CTP displayed 97\%
+%% overall reliability in a difficult RF environment, as opposed to the 70\%
+%% reliability obtained by MintRoute.  
+
+%% CentRoute~\cite{centroute} provides centralized tree routing, allowing for
+%% dissemination of tasklets and collection of information in the
+%% Tenet~\cite{tenet} architecture.  A single node serves as the sink, and other
+%% nodes in the network send join request messages which are forwarded to the
+%% sink.
+%% %%   If the node is a direct
+%% %% neighbor of the sink, the sink replies with an accept message, and the node
+%% %% joins the tree by selecting the sink as its next hop.  Otherwise, if a node
+%% %% that is part of the tree overhears a join message, it forwards this message to
+%% %% the sink.  
+%% %% When the sink receives a join message (originating from a
+%% %% non-neighbor node), it waits for the same join message to arrive along
+%% %% multiple paths and selects the best path.  The sink then source routes the
+%% %% accept message to the originating node along this path, and the node
+%% %% appropriately sets its next hop. 
+%% Once created, the tree is frozen unless
+%% some threshold of failures occur, after which a node disengages and begins the
+%% join process anew.  This approach is limited to single destination routing,
+%% and also affords no flexibility for dynamic topology conditions unless links
+%% completely break.
+
+%% Koala~\cite{koala} is designed to provide mechanisms to enable efficient data
+%% retrieval from in-network nodes.  It presents centralized mechanisms similar
+%% to those used by {\lowthane}, in which nodes explore their neighborhood, and
+%% provide this information to a central controller, which subsequently installs
+%% an appropriate route in the network.  However, similar to CentRoute, these
+%% mechanisms are only targeted towards collecting data to a root.  Further, it
+%% does not position these mechanisms within a broader architecture or
+%% investigate their performance under different conditions; the focus of the
+%% work is a MAC-layer technique called Low Power Probing. %% , which enables more
+%% %% effective duty-cycling.
+
+%% TSMP~\cite{tsmp}, incorporated into the WirelessHART standard\cite{whart}, is a
+%% well-established industry approach that includes centralize scheduling of
+%% channel resources to achieve predictable latencies.  It operates at the link-layer, using channel
+%% hopping, and does not provide any routing capabilities specified in publicly
+%% available documentation.  Its tight scheduling of media accesses differs
+%% significantly from the functionality of our {\controller}s, which contain only
+%% soft state and are relatively asynchronous.
+
+
+%% %Koala \cite{koala} presents a design which contains mechanisms
+%% %similar to those used by {\lowthane} such as collecting topology and installing
+%% %routes within the network.  However, it does not position these mechanisms
+%% %within a broader architecture or investigate their performance under different
+%% %conditions; the focus of the work is a MAC-layer technique called Low Power
+%% %Probing.
+
+%% %% One of the shifts in ROLL has been toward an IPv6 based architecture, centered
+%% %% around 6LoWPAN~\cite{6lowpan}, the low-powered adaptation designed for L2Ns.
+%% Hui presented a complete IPv6 network architecture for L2Ns, which includes a
+%% low power link along with network and transport layers adapted to the unique
+%% characteristics of these networks \cite{hui}.  This work adapted collection to
+%% the IP architecture by conceptualizing it as choosing an IP default route.  It
+%% also provided unicast capabilities by allowing a controller to communicate
+%% with individual nodes by source routing the packet, forming the basis for
+%% triangle routing of intra-network traffic.  
+%% % However, such an approach also incurs unnecessarily high stretch, and
+%% % naturally forms bottleneck links around the controller.
+
+%% % However, the implementation presented relies on routing intra-network
+%% % traffic through a collection point to implement unicast traffic, leading to
+%% % unnecessarily high stretch.
+%% %%   Of particular interest to our work was
+%% %% Hui's contribution to reliable multi-parent tree-based routing, and confidence
+%% %% driven link estimation.  
+%% % This basic design represents the leading edge of collection research, and formed
+%% % {\lowthane}'s basic template; we extend it with optimizations for
+%% % point-to-point traffic.
+
+%% From these myriad examples of collection protocols, we drew the elements of a
+%% reliable control plane.  Dynamic and accurate link estimation is important to
+%% deal with the lossy nature of the medium, and data-path validation is helpful
+%% to prevent harmful routing loops.  Finally, nodes should exploit spatial
+%% redundancy by keeping a set of potential next hops rather than a single choice.
+
+%% %% the  foundation and inspiration
+%% %% for many of our algorithms and has been invaluable in helping us to frame our
+%% %% architecture.
+
+%% %% A final approach worth considering are receiver-oriented protocols such as
+%% %% ExOR.  This family of protocol forwards data by broadcasting packets and
+%% %% relying on receivers closer to a sink forwarding it.  They must contain a
+%% %% resolution protcol to suppress duplicates.  The inherent difficult is 
+
+%% \subsubsection{Other Routing Protocols}
+%% \label{ssec:existing-other}
+
+%% BVR~\cite{ref:bvr} is a geographical location-based routing protocol for
+%% L2Ns.  A set of landmark beacons are selected whose identity is known by all
+%% nodes in the network.  Every node is given a virtual coordinate, which is the
+%% vector of distances to all beacons in the network.  When a node wants
+%% to send a packet to a destination node, it greedily forwards the packet along
+%% routes that move it closer to the destination.  
+%% %% If it is unable to do this (i.e. gets stuck at some point), it forwards the packet to the beacon closest to the destination.  In the case that this beacon is not able to use greedy routing to forward to the destination, scoped flooding is used to find the destination.  As demonstrated in other papers~\cite{s4-nsdi}, 
+%% BVR suffers from poor transmission and routing stretch, particularly as the
+%% network grows in size \cite{s4-nsdi}.  %% Variations to improve performance trade
+%% %% off resources by maintaining the entire 2-hop neighbor table in memory.
+%% Another difficulty is that in such a network, the identity of the beacons must
+%% be known {\it a priori}, and can not be modified dynamically without a location
+%% service \cite{bvr-location}.
+%% %% .  A BVR location
+%% %% service~\cite{bvr-location} was designed, but struggled because it still
+%% %% necessitated significant network overhead and state.
+
+%% S4~\cite{s4-nsdi}, is designed to provide small stretch and state in order to
+%% enable scalable routing.  It utilizes a modified compact routing algorithm
+%% tailored for L2Ns. %%  A subset of nodes in the network are designated as beacons,
+%% %% with $\sqrt{N}$ being the optimal number.  A node $n$'s local neighborhood
+%% %% cluster is defined as the set of nodes whose distance to $n$ is less than or
+%% %% equal to the distance to their closest beacon.  Each node maintains routes to
+%% %% all other nodes in their cluster, and all beacons in the network.  A node can
+%% %% route to nodes outside its cluster by routing to the destination node's
+%% %% closest beacon.  
+%% %% However, this feature requires a directory service that the
+%% %% node can contact to obtain this information, and furthermore a beacon
+%% %% selection mechanism is needed, both for initial beacon selection, as well as
+%% %% under failure conditions, and the number of beacons can not be easily modified
+%% %% during runtime.  
+%% S4 has a theoretical worst case routing stretch of $3$,
+%% although published results indicate an average routing stretch of $1.2$ while maintaining
+%% $\mathit{O}(\sqrt{N})$ state.  Like BVR, deploying S4 would require also
+%% designing a distributed directory service.  Neither of these protocols
+%% optimize for the common workload where most traffic is destined towards an
+%% egress point; unlike S4 and BVR's homogeneous network, {\lowthane} starts with
+%% optimizing collection and emphasizing heterogeneity.
+
+%%   %% In section~\ref{sec:tossim}, we compare {\lowthane} to S4,
+%% %% demonstrating that we achieve greater reliability, with smaller stretch,
+%% %% state, and control traffic.
+
+%% %Finally Hui's work explores extending the
+%% %Internet architecture to L2Ns, and develops the algorithms necessary for
+%% %default route formation in \cite{hui}.  This work has been invaluable in
+%% %helping us to frame our architecture.
+
+%% \subsection{Ad-Hoc Networking Protocols}
+
+%% Finally, there is also an extensive literature on fully distributed routing
+%% protocols for ad-hoc wireless networks. % and L2Ns in particular. %% The
+%% %MANET~\cite{MANET} working group focuses
+%% %% on such protocols and issues.
+%% AODV~\cite{aodv} uses flooded RREQ messages to discover paths to destinations
+%% on demand, with intermediate nodes creating hop-by-hop entries for
+%% bidirectional flows.  DSR~\cite{dsr} is also an on-demand routing protocol,
+%% but uses source routing to route packets.  OLSR~\cite{olsr} is a link state
+%% algorithm that uses multipoint relays to reduce the flood of link-state
+%% advertisements.  802.11s, a draft mesh routing standard uses a variant of AODV
+%% called AODV-RM for intra-subnet point-to-point communication, but optimizes
+%% for an access network's workload by proactively building a routing tree towards
+%% egress points \cite{80211s}.
+
+%% These and other protocols provide point-to-point routing capabilities in
+%% wireless networks.  Both on-demand and link-state based solutions exist, but
+%% the focus is on providing reliable any-to-any delivery in networks with mobile
+%% nodes that are resource rich.  Consequently, most of these protocols have
+%% large control traffic and/or state requirements.  A protocol
+%% survey~\cite{ietf-protocol-survey} recently evaluated the specifications of
+%% the most widely used ad-hoc protocols against five criteria, and
+%% noted that in their current form no ad-hoc protocol meets more than
+%% three of the five criteria.%%   L2N-specific implementations of some of these
+%% %% protocols exists, such as TinyAODV and TYMO, but have received limited
+%% %% exposure and acceptance due to their poor (or non-existent) evaluations and
+%% %% limited feature-sets.
+
+
+%% \subsection{Internet Solutions}
+%% \label{sec:related-centralize}
+
+%% The concept of centralized routing, or separating the control and data planes,
+%% is not a novel one; we explore several existing protocols later in this
+%% section that embrace a centralized paradigm.  However, these solutions
+%% were designed primarily for the Internet, characterized by
+%% low churn and high bandwidth.  This is in stark contrast to the
+%% high-churn, low-bandwidth nature of typical L2N environments. %% Consequently,
+%% %% we discuss three factors that are critical to the success of centralized
+%% %% solutions, and while trivial to achieve in general networking environments,
+%% %% present the main obstacles to a centralized solution.
+
+%% % \subsection{Internet Routing Protocols}
+
+%% %% We discuss two separate bodies of work in this section: Centralized Internet
+%% %% Routing Architectures / Protocols, and IP-Based Ad-Hoc Networking
+%% %% Protocols(i.e. MANET~\cite{MANET}).
+
+%% % \subsubsection{Centralized Routing Architectures}
+
+%% The most conceptually similar work is Ethane~\cite{ethane}, %% , the successor to SANE~\cite{sane} and the predecessor to
+%% %% NOX~\cite{nox}, 
+%% a centralized architecture for implementing high-level
+%% security policies.  Designed for large enterprise networks, the network is
+%% divided into four tiers: controllers, %  (or multiple ones for fault tolerance),
+%% switches, end hosts or servers, and users.  %% Whenever a switch is connected to
+%% %% the network, it registers with the controller, and establishes a secure
+%% %% backchannel to it.  When an end host joins the network, the switch also
+%% %% reports this registration, reporting the class of device and attachment port.
+%% %% Finally, users are able to associate with one or more end host machines.
+%% %% Consequently, the controller maintains a complete and accurate view of the
+%% %% topology. 
+%% Network administrators specify high-level access policies, such as
+%% restricting which servers a certain user may communicate with.  Each switch
+%% maintains a flow table against which it can classify incoming packets using
+%% a packet header's 10-tuple.  If no applicable entry exists, the packet is
+%% forwarded to the controller.  The controller consults its policy
+%% specification, and installs flow entries along the path.
+%% %% {\lowthane} utilizes this concept of installing flow entries and forwarding
+%% %% packets belonging to unclassifiable flows to the controller.
+%% %Ethane~\cite{ethane} is the work that is the most similar to ours.  Designed
+%% %for large enterprise networks, the network is divided into three tiers: a
+%% %controller (or multiple ones for fault tolerance), switches, and end hosts or
+%% %servers.  
+%% % Whenever a switch is connected to the network, it registers with the
+%% % controller, and establishes a secure channel to it.  When a server or
+%% % middlebox joins the network, it also registers with the controller, reporting
+%% % the connecting switch and port.  Consequently, the controller maintains a
+%% % complete and accurate view of the topology.  Each switch maintains a flow
+%% % table in which it can match packet 5-tuples.  If no applicable entry exists,
+%% % the packet is forwarded to the controller.  The controller consults its policy
+%% % specification, and installs hop-by-hop
+%% % flow entries along the path.
+
+%% Key elements visible in this design include forming a channel and ``default
+%% routing'' to a controller, and maintaining global topology.  At a high level,
+%% {\lowthane} can be considered an adaptation or instantiation of the Ethane
+%% architecture.  Bringing Ethane together with low-power wireless
+%% brings out many of the assumptions underlying Ethane's operation, which must
+%% be addressed for the system to be practical; we explictly note three of the
+%% most important assumptions in the next section.
+
+%% % {\lowthane} also
+%% % addresses these issues, but the details differ significantly when no wired
+%% % infrastructure is available.
+
+%% %%  are present in the {\lowthane} design.  However,
+%% %% elements which Ethane takes for granted like {\controller} reachability and
+%% %% topology inference must be carefully addressed in the more dynamic L2N setting.
+
+%% %% Ethane assumes the availability of a secure and reliable channel to the
+%% %% controller, and also lends itself to trivial construction of a global topology
+%% %% view.  Network switches all have ample bandwidth and memory, allowing Ethane
+%% %% to support 70,000 flows / second at line speeds.  Finally, Ethane operates on
+%% %% top of layer 2 switching, which performs automatic failure rerouting to direct
+%% %% a packet to the addressed next hop.  While we discuss Ethane's successor,
+%% %% NOX~\cite{nox}, further in chapter~\ref{ch:player-centralized}, we note that
+%% %% architecturally it is the same as Ethane and hence suffers from the same
+%% %% limitations in the context of ROLL.
+
+%% A number of other centralized internet routing designs exist, which we mention
+%% briefly for completeness.  Feamster's Routing Control Platform, implemented by
+%% Caesar, made the case for separating the control aspect of routing from
+%% routers \cite{feamster-separating, caesar-rcp}.  Greenberg {\it et al.}
+%% present 4D~\cite{4d,tesseract}, a general framework for separating routing from routers.
+%% The framework consists of four components: a decision plane, a dissemination
+%% plane, a discovery plane, and a data plane.
+
+
+%%   %% Designed for both intra-AS (autonomous
+%% %% system) and inter-AS routing, 
+%% %% The motivation was that by distributing all
+%% %% aspects of routing, interactions became increasingly complex, heavy bandwidth
+%% %% usage resulted from topology changes, and forwarding loops and routing
+%% %% failures that were incredibly difficult to diagnose continually presented
+%% %% themselves.  To alleviate such difficulties, RCP serves as the primary
+%% %% interaction point for all routers within an AS.  %% By participating in the
+%% %% network, RCP was able to obtain a complete view of the topology. 
+%% %% A network
+%% %% operator could specify the routing policy at a single place (which typically
+%% %% was to simply mimic that of a fully-meshed iBGP AS), and then the RCP node
+%% %% would advertise the correct route to each router in the network.
+%% %% RCP would
+%% %% then serve the role of an egress router in communicating routing information
+%% %% with other AS's using eBGP (allowing for a smooth incremental deployment). 
+%% %%  As
+%% %% an ideal end-state, all AS's would have an RCP, and these RCP's would
+%% %% communicate with each other to exchange routing information.
+%% %% Caesar {\it et al.} presented an actual design and implementation of an
+%% %% RCP~\cite{caesar-rcp}.  %% Leveraging the existing OSPF and BGP protocols in
+%% %% place in most existing networks, the implementation had three distinct
+%% %% components: an IGP Viewer, a BGP Engine, and a Route Control Server (RCS).
+%% %% The IGP Viewer obtains IGP topology information by building adjacencies with
+%% %% routers in the network.  The BGP Engine learns BGP routes from the routers,
+%% %% and also communicates routing assignments to each router.  Finally, the RCS
+%% %% uses the information obtained by the other two components to compute routing
+%% %% assignments according to some specified policy, which currently defaults to
+%% %% full-mesh iBGP configurations. 
+%% %% A key decision was distributing RCS nodes to avoid creating a single point of
+%% %% failure, but they are not precise replicas and there are only loose
+%% %% consistency requirements. %, which are detailed in the paper.
+%% %% While the creation of a distinct control hierarchy certainly permeates our
+%% %% design, the practicality of RCP for L2Ns is limited.  
+%% %% However, the design focuses on only
+%% %% the intra-AS aspect, leveraging full underlying IP and TCP connectivity, as
+%% %% well as OSPF and BGP for information dissemination, which neither exist nor
+%% %% are practical in L2Ns.  A key part of our design involves designing
+%% %% mechanisms that provide this underlying connectivity and accurately
+%% %% constructing and maintaining global topology views. %%  Furthermore, full
+%% %% consistent connectivity is maintained by all nodes in the network at all times
+%% %% (often through flooding of Link State Advertisements), resulting in
+%% %% significant memory and network overhead, as opposed to on-demand schemes that
+%% %% are often a better fit for ROLL traffic patterns.  The lossy and dynamic
+%% %% nature of low-power wireless would only exacerbate network congestion in such
+%% %% an architecture.  Finally, their attempts at reducing overhead relies on
+%% %% prefix-based IP addressing, conflating node address and geographical location,
+%% %% while ROLL networks primarily embrace flat-label based addressing schemes.
+
+%% %% decision plane, composed of a single logical decision element (which is
+%% %% replicated for fault tolerance), serves as the {\emph{network brain}}, serving
+%% %% as the interface for network-wide policy specification, which is subsequently
+%% %% communicated to individual routers and switches.  The dissemination plane is
+%% %% tasked with creating the logical channels between the decision element and
+%% %% each router and switch, providing a medium for control information flow,
+%% %% independent of the state of the data plane.  The discovery plane refers to the
+%% %% process in which each router/switch discovers its own capabilities, its
+%% %% neighboring routers/switches (including those in other ASes), and communicates
+%% %% this information across the dissemination plane to the decision element,
+%% %% allowing for the creation of a global view of the network.  Finally, the data
+%% %% plane is greatly simplified, responsible only for forwarding packets according
+%% %% to the forwarding table entries installed by the decision element.
+%% %% As a framework paper, 4D does not provide any specific instantiations of any
+%% %% of the components.  
+%% %% Although targeted towards the general Internet,
+%% %% the same modularization applies in the context of ROLL as well; our routing
+%% %% architecture for L2Ns can roughly be
+%% %% decomposed into the same four components.  This componentization is
+%% %% particularly effective in highlighting the characteristics that differentiate
+%% %% L2Ns from the general Internet.  The dissemination plane must be built over
+%% %% a series of lossy unreliable links, in which the {\emph{optimal}} paths are
+%% %% potentially shifting.  %% Low power wireless also complicates the
+%% %% discovery plane, as there is a degree of dynamicity, even if the nodes
+%% %% are physically stationary, and also power duty cycles that reach 0.1\% and
+%% %% below.
+%% %% Furthermore, energy constraints prohibit excessive control traffic, which
+%% %% complicates communication of this discovery information to the decision plane.
+%% %% Finally, the data plane must provide certain reliability and delivery
+%% %% guarantees in the face of lossy and moving paths.  Yan {\it et al.} present
+%% %% Tesseract~\cite{tesseract}, a faithful instantiation of the 4D framework and
+%% %% concept.  %% Switches use periodic beaconing to determine their
+%% %% neighboring nodes, as well as their own capabilities, and then transmit this
+%% %% information to a {\emph{decision element}}, which forms the basis of the
+%% %% decision plane.  Path explorer messages are flooded through the network to
+%% %% enable the building of the dissemination plane.  Subsequently, the decision
+%% %% element sends all control messages to switches using source routes, and in
+%% %% turn, these switches reverse these source routes for sending information to
+%% %% the decision element.  The decision plane is implemented as an abstract model,
+%% %% in which specific algorithms are separated from the underlying link
+%% %% technologies, to provide an element of portability.  To provide robustness at
+%% %% the decision plane level, multiple decision elements are maintained at any
+%% %% given time, with all information being fully replicated across all of them.
+%% %% However, only one of them is a master (i.e. active) at any given time, while
+%% %% the rest are only used in the case of a hot standby.  The master is chosen
+%% %% through a leader-election process and arbitrarily assigned priorities.
+%% %% Security also plays a large role in Tesseract, with numerous mechanisms to
+%% %% enable encryption, certification, and authentication.
+%% %% Tesseract also provides the fully connected best path routing, which
+%% %% necessitates large amounts of control traffic, and state at the nodes that
+%% %% scales with the size of the network. %% The
+%% %% dissemination plane relies on source routing in both directions, stripping the
+%% %% switches of any local flexibility to deal with unreliable links, and dynamic
+%% %% topology shifts, as is common in L2N networks.  This results in additional
+%% %% control traffic for every instance of packet delivery failure, as does the
+%% %% need for full information at decision elements.
+
+
+%% %\begin{itemize}
+%% %\item{Tempest}
+%% %\item{FIRE}
+%% %\end{itemize}
+
+%% % \subsubsection{Stable Backchannel To Centralized Controller}
+
+%% \subsection{Towards a Hybrid Solution}
+
+%% From this disparate related Internet work, we distill a three requirements for
+%% successful centralized control. 
+%% \begin {description}
+%% \item[Reliable Path to Centralized controller] 
+
+%% A logical controller serves as the brain of the network, gathering
+%% information from all the routers in the network, and disseminating
+%% control commands.  One of the key implications of this role hierarchy is the
+%% need for a stable channel between the controller and all routers in the
+%% network at all times.  %% In many cases, this channel uses logically different
+%% %% links than the data plane, as its reliability and stability must be ensured.
+%% In large wired networks, creation of this channel is simplified by underlying
+%% data link layers: in Ethernets, the
+%% underlying layer-2 spanning tree algorithm provides reachability between all
+%% switches and end-hosts in a subnet.%% , and lookups can be accomplished using ARP.
+%% %% This is feasible because of the local broadcast nature of communications on a
+%% %% subnet.  Extending this reachability across multiple subnets can be done by
+%% %% introducing layer-3 routing elements as well.  Furthermore, once this channel
+%% %% has been established, it remains relatively stable, except in cases of severe
+%% %% congestion or physical partitioning, which are outside of the scope of our
+%% %% problem.
+%% % In contrast, no such natural mechanisms exist in L2N environments, and so the
+%% % network layer must build a robust path to the controller.  
+%% % Much
+%% Collection protocols may be used to provide just this functionality.
+%% %% The
+%% %% link-layer provides only single-radio-hop communications, with no inherent
+%% %% mechanisms for building neighbor tables.  
+%% %% Networks can be relatively deep,
+%% %% with diameters of 20 or more hops possible~\cite{ietf-industrial}.
+%% %% Furthermore, the quality of links vary widely, both spatially and temporally,
+%% %% creating a lossy path that is highly dynamic even without mobility.
+%% %% Finally, this channel must be maintained with minimal control traffic and
+%% %% network overhead, per the requirements outlined previously.
+%% \item[Consistent Global View of Topology] 
+%% One benefit of centralized routing is the ability to make routing decisions at
+%% a central location that has complete information about the state of the entire
+%% network. %%  In to order to create such a global view, all the elements of the
+%% %% network must register upon joining, and then provide updates of new neighbors
+%% %% and changes in the state.
+%% %%   In many existing solutions, there are periodic
+%% %% heartbeats that are sent in the form of link state advertisements, which
+%% %% allows the controller to maintain this global view.
+%% Three main factors complicate this task in L2Ns: control traffic restrictions,
+%% memory constraints, and dynamic topology.  
+%% Only a trickle of bandwidth is generally available to propagate network state towards
+%% a control element.
+%% %% Control traffic must not exceed
+%% %% the data rate, and so consistent periodic link state advertisements with
+%% %% updates sent to the controller are not practical.  %% Furthermore, the
+%% %% loss-response ROLL criteria dictates that control traffic in response to a
+%% %% loss must be limited to active paths or the single-hop broadcast domain,
+%% %% preventing triggered global updates. 
+%% Links exhibit temporal
+%% and spatial variability, which complicates %: links are not binary, so 
+%% maintaining a consistent
+%% view of network links. % qualities is difficult. %% would require significant amounts of control
+%% %% traffic. 
+%% Finally, memory constraints prevent individual nodes from
+%% maintaining state for all nodes in the network, or even the single-hop
+%% broadcast neighborhood.  Therefore, forming the complete topology may
+%% not be possible.%; we investigate the extent to which this is necessary.
+
+%% %% , leading to the unavailability of needed information,
+%% %% even if control traffic was not problematic.
+
+%% \item [Providing Reliability Over Lossy Links]
+%% The target environment for the majority of existing routing protocols is often
+%% highly-reliable, in the form of either wired links, or single-hop wireless
+%% links that provide relatively high reliability, through both link-layer and
+%% typically transport layer retransmissions.
+%% In L2Ns, the low-power nature of the ratio leads to a small
+%% Signal-to-Interference-and-Noise Ratio (SINR) on many links.  As demonstrated
+%% by Srinivasan {\it et al.} \cite{underlying}, the SINR of these links is often on
+%% the cusp of the necessary threshold to receive a packet, which results in
+%% bimodal links due to variations in signal strength and interference levels.
+%% Consequently, accurate link estimation and local repair techniques are critical.%% , both in accurately
+%% %% calculating a links quality/cost, and also in identifying and accounting for
+%% %% temporal shifts in these link qualities in order to minimize transmission
+%% %% stretch while maintaining reliability.
+%% \end{description}
+
+%% Although it is not obvious that any element of centralized control is a
+%% natural fit for L2N routing since existing centralized solutions rely on
+%% assumptions which do not automatically hold in this setting, research in the
+%% sensor network literature can be re-cast to help achieve the necessary
+%% prerequisites.
+
+%% %% policy
+%% % Futhermore, none of the related wireless work we have considered has addressed
+%% % the need for policy routing in wireless networks.  The ability to optimize for
+%% % metrics other then ETX or hop-count, and to do so ``on the fly'' becomes
+%% % increasingly important as networks begin to be composed of devices with
+%% % different power levels, processing rates, and security capabilities, it
+%% % becomes desirable to have a framework with which to tie together all these
+%% % metrics and optimize over the joint metrics and policy space.
+
+
+%% %% Finally, one way of providing effective routing is to utilize meaningful, or
+%% %% routable, addressing schemes.  One of the reasons that IP prefix-based routing
+%% %% is effective is that IP-addresses often tie together a name and geographical
+%% %% location.  %% In other words, except in very rare cases (such as Mobile IP
+%% %% %% solutions), all IP addresses with a shared prefix (of varying length depending
+%% %% %% on the size of subnet) are geographically co-located, allowing remote routers
+%% %% %% to maintain a single routing entry for that block of addresses.
+%% %% This reduces
+%% %% both memory state at routers, and the size of control traffic.
+%% %% This conflation of address and location is difficult in L2Ns.%%   We discussed
+%% %% %% examples of this in section~\ref{ssec:existing-other} in the form of
+%% %% %% geographic routing and compact routing schemes. 
+%% %% The challenge in implementing
+%% %% such a design is the dynamic nature of the network \cite{shenkergeo}.  Varying link qualities
+%% %% cause optimal routing paths to change, which would imply that the router's
+%% %% address would have to adjust accordingly.%%   This would require a lookup service
+%% %% %% for nodes to report updates to, and request lookups from.  This is in fact one
+%% %% %% of the main shortcomings of proposed geographic and compact routing schemes in
+%% %% %% the L2N space.  Despite the shortcomings of existing solutions, this may be a
+%% %% %% potential avenue that warrants additional research.
+
+
+
+
+
+%% %Multiprotocol Label Switching~\cite{mpls}, or MPLS, is a commonly used example of centralized routing in large networks.  Network operators setup explicit paths, often either to provide QoS or VPN services, by installing label entries at Label Switch Routers in the network.  Packets then carry a label, or even potentially a stack, which are attached at Label Edge Routers, allowing for fast lookups at each Label Switch Router.  This setup assumes a relatively static network, and paths are manually set-up, with no clear correlation with data traffic.
+