Changeset 2775

Show
Ignore:
Timestamp:
10/30/09 13:36:15 (4 weeks ago)
Author:
arsalan
Message:

Another stab at the intro

Files:
1 modified

Legend:

Unmodified
Added
Removed

  • docs/Lowthane/ipsn10/intro.tex

    r2770 r2775  
    11\section{Introduction}\label{sec:intro} 
    22 
     3This paper aims to address one of the main shortcomings of sensornet research: the lack of a routing protocol that efficiently supports all components of an application workload.  To expand further: 
    34 
    4 This paper is about the future of routing in stationary sensor 
    5 networks but we begin with a brief history of its past.  A decade ago, 
    6 Estrin and others proposed directed diffusion as a robust and scalable 
    7 coordination architecture for {\em localized} communications in sensor 
    8 networks~\cite{estrin99challeges, intanagowiwat00diffusion}. In the 
    9 directed diffusion model, some nodes publish data, some nodes 
    10 subscribe to data, and intermediate nodes disseminate subscriber 
    11 interests, establish an interest gradient, and (optionally) transform 
    12 the data as they flow from sources to sinks.  Although directed 
    13 diffusion left an indelible intellectual mark on the field, the use of 
    14 localized algorithms never became common.  This was due in part to 
    15 early application workloads which did not demand in-network processing 
    16 of concurrent flows among arbitrary endpoints. 
     5\begin{itemize} 
     6\item{{\bf{Workload:}} Traffic patterns are predominantly many-to-one collection, with a smaller but significant mix of point-to-point traffic.} 
     7\item{{\bf{Efficiently:}} Any solution must adhere to sensornet resource-constraints, and state and control overhead must be proportional to the data traffic.} 
     8\end{itemize} 
    179 
    18 Rather, early sensornet application workloads were {\em collection} 
    19 (all-to-one) and {\em dissemination} (one-to-all) oriented, and 
    20 applications ranging from environmental monitoring~\cite{gdi,redwoods} 
    21 to target tracking~\cite{vigilnet,lites,exscal} were implemented using 
    22 essentially these communications primitives.  The early applications 
    23 established the importance of collection and dissemination, spawned a 
    24 period of active research that produced many pioneering 
    25 contributions~\cite{trickle,mintroute}, and influence collection and 
    26 dissemination research to this day~\cite{flashflood,ctp,dip}. 
     10Many solutions do exist, but they have either only addressed one component of the problem, or solved the problem in another domain with limited applicability to sensornets.  Collection protocols~\cite{mintroute,ctp} provide reliable collection to a sink, but use grossly inefficient schemes for unicast communication.  Point-to-point protocols~\cite{s4-nsdi, tinyaodv, bvr} allow for communication between arbitrary pairs of nodes, yet make no provisions to support common-case collection.  Outside of sensornets, general networking platforms such as Ethane~\cite{ethane} provide compelling solutions, yet are based on assumptions that make porting anything beyond the high-level design to sensornets untenable. 
    2711 
    28 Over time and with experience, the community began to conclude that 
    29 reasoning about (and implementing) localized algorithms proved to be 
    30 more challenging and less important than originally anticipated. 
    31 Perhaps equally important, through many application deployments, the 
    32 community converged on a canonical system architecture for stationary 
    33 sensor networks: a bevy of resource-poor sensor nodes streaming data 
    34 to a resource-rich root node.  Eventually, centralized implementations 
    35 would leverage this architecture and exhibit competitive performance 
    36 without the complexity overhead common to localized algorithms.  And, 
    37 the early proponents of directed diffusion would argue for centralized 
    38 routing~\cite{centroute} and application logic~\cite{tenet}, and 
    39 others would converge on this architecture approach~\cite{koala}. 
     12We don't claim to present a highly-novel new routing protocol; rather our main contribution is a seemingly intuitive routing architecture designed from scratch that simply works.  We leverage the asymmetrical resource allocation typical of sensornets to push complexity to {\controller}s at the edge and minimize state and functionality in the network.  Our design revolves around controlling the tradeoff between state and stretch, and minimizing control traffic through a focus on data-driven design.  We embrace the open-standards approach to system design, and our solution, {\lowthane}, is in fact the default routing protocol for blip, a widely-used IPv6 adaptation network layer for sensornets. 
    4013 
    41 Today, collection routing continues to play an important role, but its 
    42 best effort reliability semantics -- due to its lack of end-to-end 
    43 acknowledgements -- proved insufficient for many scientific 
    44 applications that require full data reliability~\cite{volcano,shm}. 
    45 To redress collection's shortcomings, researchers developed reliable 
    46 transport protocols like Fetch~\cite{fetch} and Flush~\cite{flush} 
    47 that allowed the root node to request a bulk data transfer from a 
    48 particular node and also acknowledge, end-to-end, receipt of the 
    49 requested data.  Lacking a suitably lightweight point-to-point 
    50 protocol, Fetch and Flush resorted to flooding the whole network with 
    51 transfer requests and end-to-end acknowledgements, relying on 
    52 application-layer filtering to drop messages from all but the intended 
    53 recipients.  Although far from an elegant solution to the problem of 
    54 point-to-point routing, the approach represented a pragmatic path 
    55 forward for domain scientists to collect their data. 
     14Beyond presenting {\lowthane}, we provide an analysis from real-world experiments that seeks to answer the questions, how well does this general architecture compare to specialized point solutions, and how robust is it?  In this vein, we compare it to CTP for collection traffic, and TinyAODV for point-to-point traffic, focusing on reliability and overhead.  For robustness, we examine the functionality of {\lowthane} in the face of high traffic concurrency and significant network failures. 
    5615 
    57 We now face a fork in the road.  One path -- representing current 
    58 practice -- continues to abuse flooding in the service of unicast. 
    59 Acceptable as quick-and-dirty hack, the approach is not tenable for 
    60 general purpose -- and increasingly more common -- applications of 
    61 point-to-point routing including interactive communications, 
    62 sensor/actuator pairings, or TCP acknowledgements.\footnote{Which 
    63   occur more frequently than bulk transport acks.}  A second path -- 
    64 embracing recent developments in point-to-point wireless mesh routing 
    65 -- leads to an architecturally elegant solution, but one with its 
    66 share of practical challenges.  Some protocols suffer from poor 
    67 stretch~\cite{ref:bvr}.  Some require a location service~\cite{bls} to 
    68 decouple a node's names from dynamic 
    69 addresses~\cite{ref:bvr,s4-nsdi}. Some require non-trivial state or 
    70 frequent messaging~\cite{aodv}.  Some require stable 
    71 landmarks~\cite{ref:bvr}.  And all have non-trivial overhead. 
    72  
    73 This paper embraces a third path that preserves collection routing, 
    74 leverages the contemporary architecture of resource-poor sensor nodes 
    75 reporting to one (or more) resource-rich root node(s), and provides a 
    76 pragmatic, evolutionary, and architecturally-principled way forward. 
    77 Our design begins where collection ends: by creating a collection tree 
    78 link state database at the root, itself populated using collection. 
    79 With knowledge of the collection topology, point-to-point is simple: a 
    80 node sends data to the root and it source routes the data to the 
    81 destination~\cite{hui}.  Although simple, triangle routing leads to a 
    82 worst-case stretch of twice the diameter. 
    83  
    84 Our design departs from the sensornet literature at this point and 
    85 adopts mechanisms from enterprise networking~\cite{ethane}, with 
    86 changes to adapt to the unique characteristics of low-power, lossy 
    87 wireless links.  In our scheme, nodes periodically report a subset of 
    88 good neighbor links to the root.  Over time, as these data-, timer-, 
    89 or change-driven reports are sent, a picture of the network's link 
    90 state emerges at the root.  Since the cross edges in the collection 
    91 spanning tree are useful for reducing stretch between many node pairs, 
    92 they must be discovered, tested, and reported, raising the question of 
    93 how to balance exploration and exploitation.  We find that such a 
    94 simple design provides high reliability, allows low stretch, and 
    95 offers low overheard, while adhering to a system architecture already 
    96 in place for today's stationary networks. 
     16%This paper is about the future of routing in stationary sensor 
     17%networks but we begin with a brief history of its past.  A decade ago, 
     18%Estrin and others proposed directed diffusion as a robust and scalable 
     19%coordination architecture for {\em localized} communications in sensor 
     20%networks~\cite{estrin99challeges, intanagowiwat00diffusion}. In the 
     21%directed diffusion model, some nodes publish data, some nodes 
     22%subscribe to data, and intermediate nodes disseminate subscriber 
     23%interests, establish an interest gradient, and (optionally) transform 
     24%the data as they flow from sources to sinks.  Although directed 
     25%diffusion left an indelible intellectual mark on the field, the use of 
     26%localized algorithms never became common.  This was due in part to 
     27%early application workloads which did not demand in-network processing 
     28%of concurrent flows among arbitrary endpoints. 
     29% 
     30%Rather, early sensornet application workloads were {\em collection} 
     31%(all-to-one) and {\em dissemination} (one-to-all) oriented, and 
     32%applications ranging from environmental monitoring~\cite{gdi,redwoods} 
     33%to target tracking~\cite{vigilnet,lites,exscal} were implemented using 
     34%essentially these communications primitives.  The early applications 
     35%established the importance of collection and dissemination, spawned a 
     36%period of active research that produced many pioneering 
     37%contributions~\cite{trickle,mintroute}, and influence collection and 
     38%dissemination research to this day~\cite{flashflood,ctp,dip}. 
     39% 
     40%Over time and with experience, the community began to conclude that 
     41%reasoning about (and implementing) localized algorithms proved to be 
     42%more challenging and less important than originally anticipated. 
     43%Perhaps equally important, through many application deployments, the 
     44%community converged on a canonical system architecture for stationary 
     45%sensor networks: a bevy of resource-poor sensor nodes streaming data 
     46%to a resource-rich root node.  Eventually, centralized implementations 
     47%would leverage this architecture and exhibit competitive performance 
     48%without the complexity overhead common to localized algorithms.  And, 
     49%the early proponents of directed diffusion would argue for centralized 
     50%routing~\cite{centroute} and application logic~\cite{tenet}, and 
     51%others would converge on this architecture approach~\cite{koala}. 
     52% 
     53%Today, collection routing continues to play an important role, but its 
     54%best effort reliability semantics -- due to its lack of end-to-end 
     55%acknowledgements -- proved insufficient for many scientific 
     56%applications that require full data reliability~\cite{volcano,shm}. 
     57%To redress collection's shortcomings, researchers developed reliable 
     58%transport protocols like Fetch~\cite{fetch} and Flush~\cite{flush} 
     59%that allowed the root node to request a bulk data transfer from a 
     60%particular node and also acknowledge, end-to-end, receipt of the 
     61%requested data.  Lacking a suitably lightweight point-to-point 
     62%protocol, Fetch and Flush resorted to flooding the whole network with 
     63%transfer requests and end-to-end acknowledgements, relying on 
     64%application-layer filtering to drop messages from all but the intended 
     65%recipients.  Although far from an elegant solution to the problem of 
     66%point-to-point routing, the approach represented a pragmatic path 
     67%forward for domain scientists to collect their data. 
     68% 
     69%We now face a fork in the road.  One path -- representing current 
     70%practice -- continues to abuse flooding in the service of unicast. 
     71%Acceptable as quick-and-dirty hack, the approach is not tenable for 
     72%general purpose -- and increasingly more common -- applications of 
     73%point-to-point routing including interactive communications, 
     74%sensor/actuator pairings, or TCP acknowledgements.\footnote{Which 
     75%  occur more frequently than bulk transport acks.}  A second path -- 
     76%embracing recent developments in point-to-point wireless mesh routing 
     77%-- leads to an architecturally elegant solution, but one with its 
     78%share of practical challenges.  Some protocols suffer from poor 
     79%stretch~\cite{ref:bvr}.  Some require a location service~\cite{bls} to 
     80%decouple a node's names from dynamic 
     81%addresses~\cite{ref:bvr,s4-nsdi}. Some require non-trivial state or 
     82%frequent messaging~\cite{aodv}.  Some require stable 
     83%landmarks~\cite{ref:bvr}.  And all have non-trivial overhead. 
     84% 
     85%This paper embraces a third path that preserves collection routing, 
     86%leverages the contemporary architecture of resource-poor sensor nodes 
     87%reporting to one (or more) resource-rich root node(s), and provides a 
     88%pragmatic, evolutionary, and architecturally-principled way forward. 
     89%Our design begins where collection ends: by creating a collection tree 
     90%link state database at the root, itself populated using collection. 
     91%With knowledge of the collection topology, point-to-point is simple: a 
     92%node sends data to the root and it source routes the data to the 
     93%destination~\cite{hui}.  Although simple, triangle routing leads to a 
     94%worst-case stretch of twice the diameter. 
     95% 
     96%Our design departs from the sensornet literature at this point and 
     97%adopts mechanisms from enterprise networking~\cite{ethane}, with 
     98%changes to adapt to the unique characteristics of low-power, lossy 
     99%wireless links.  In our scheme, nodes periodically report a subset of 
     100%good neighbor links to the root.  Over time, as these data-, timer-, 
     101%or change-driven reports are sent, a picture of the network's link 
     102%state emerges at the root.  Since the cross edges in the collection 
     103%spanning tree are useful for reducing stretch between many node pairs, 
     104%they must be discovered, tested, and reported, raising the question of 
     105%how to balance exploration and exploitation.  We find that such a 
     106%simple design provides high reliability, allows low stretch, and 
     107%offers low overheard, while adhering to a system architecture already 
     108%in place for today's stationary networks. 
    97109 
    98110