Changeset 2766

Show
Ignore:
Timestamp:
10/30/09 08:16:28 (4 weeks ago)
Author:
prabal
Message:

Checkpoint

Location:
docs/Lowthane/ipsn10
Files:
1 added
3 modified

Legend:

Unmodified
Added
Removed

  • docs/Lowthane/ipsn10/design.tex

    r2751 r2766  
    1 \section{\LOWTHANE~Overview}\label{sec:overview} 
    2  
    3 Before diving into the details, we begin by providing an overview of 
    4 {\lowthane}'s basic operation and design philosophy. 
    5 {\lowthane} develops organically from prior work, and extends it to 
    6 provide robust point-to-point routing.  At its core is a reliable channel from 
    7 the low-power, deeply embedded nodes to higher function {\controller}s situated 
    8 through the network.  For this purpose, {\lowthane} draws on many ideas from 
    9 existing collection protocols, such as data-driven link estimation, density 
    10 sensitive (trickelized) neighbor discovery messages, and careful ranking of 
    11 multiple potential next hops.  As has been amply demonstrated, these 
    12 techniques enable simple yet robust multipoint-to-point routing.  {\lowthane} 
    13 uses this functionality to route packets from within the network to the egress 
    14 points at the edge. 
    15  
    16 {\lowthane} 
    17 transmits a portion of the topology discovered by the collection protocol 
    18  down the tree to the 
    19 higher-function {\controller}s.  A major advantage of using this topology is 
    20 that collection traffic, which is often present as a background workload in 
    21 this class of network, is used to maintain the freshness of link estimates. 
    22 Furthermore, {\lowthane} is careful not to introduce an excess amount of 
    23 control traffic into the system by attempting to piggyback this topology information 
    24 on data packets wherever possible. 
    25  
    26 The {\controller}s build up a global based on topology reports.  They use this 
    27 database for two main purposes.  First, communication from a {\controller} or  
    28 external networks is source-routed into the network, based on routes computed 
    29 from the database.  Secondly, the {\controller} uses the database to compute 
    30 and install paths between nodes in the network.  By adding installed routes in 
    31 the network, {\lowthane} is able to reduce stretch for point-to-point routes 
    32 and well as mitigate contention around the controller, which is otherwise a 
    33 bottleneck for the performance of ``triangle'' routing, where all 
    34 point-to-point traffic is routed through an {\controller}. 
    35  
    36 % Because updates to {\controllers} may be delayed or lost, and links exhibit 
    37 % significant temporal variation\cite{}, {\lowthane} contains multiple 
    38 % mechanisms to detect and repair local inconsistencies.  These include local 
    39 % repair  
     1%% \section{\LOWTHANE~Overview}\label{sec:overview} 
     2 
     3%% Before diving into the details, we begin by providing an overview of 
     4%% {\lowthane}'s basic operation and design philosophy. 
     5%% {\lowthane} develops organically from prior work, and extends it to 
     6%% provide robust point-to-point routing.  At its core is a reliable channel from 
     7%% the low-power, deeply embedded nodes to higher function {\controller}s situated 
     8%% through the network.  For this purpose, {\lowthane} draws on many ideas from 
     9%% existing collection protocols, such as data-driven link estimation, density 
     10%% sensitive (trickelized) neighbor discovery messages, and careful ranking of 
     11%% multiple potential next hops.  As has been amply demonstrated, these 
     12%% techniques enable simple yet robust multipoint-to-point routing.  {\lowthane} 
     13%% uses this functionality to route packets from within the network to the egress 
     14%% points at the edge. 
     15 
     16%% {\lowthane} 
     17%% transmits a portion of the topology discovered by the collection protocol 
     18%% down the tree to the 
     19%% higher-function {\controller}s.  A major advantage of using this topology is 
     20%% that collection traffic, which is often present as a background workload in 
     21%% this class of network, is used to maintain the freshness of link estimates. 
     22%% Furthermore, {\lowthane} is careful not to introduce an excess amount of 
     23%% control traffic into the system by attempting to piggyback this topology information 
     24%% on data packets wherever possible. 
     25 
     26%% The {\controller}s build up a global based on topology reports.  They use this 
     27%% database for two main purposes.  First, communication from a {\controller} or  
     28%% external networks is source-routed into the network, based on routes computed 
     29%% from the database.  Secondly, the {\controller} uses the database to compute 
     30%% and install paths between nodes in the network.  By adding installed routes in 
     31%% the network, {\lowthane} is able to reduce stretch for point-to-point routes 
     32%% and well as mitigate contention around the controller, which is otherwise a 
     33%% bottleneck for the performance of ``triangle'' routing, where all 
     34%% point-to-point traffic is routed through an {\controller}. 
     35 
     36%% % Because updates to {\controllers} may be delayed or lost, and links exhibit 
     37%% % significant temporal variation\cite{}, {\lowthane} contains multiple 
     38%% % mechanisms to detect and repair local inconsistencies.  These include local 
     39%% % repair  
    4040 
    4141\section{Design and Implementation}\label{sec:design} 

  • docs/Lowthane/ipsn10/intro.tex

    r2752 r2766  
    4949requested data.  Lacking a suitably lightweight point-to-point 
    5050protocol, Fetch and Flush resorted to flooding the whole network with 
    51 transfer request commands and end-to-end acknowledgements, relying on 
     51transfer requests and end-to-end acknowledgements, relying on 
    5252application-layer filtering to drop messages from all but the intended 
    5353recipients.  Although far from an elegant solution to the problem of 
    … …  
    5555forward for domain scientists to collect their data. 
    5656 
    57 We now find ourselves facing a fork in the road.  One path -- 
    58 representing current practice -- continues to abuse flooding in the 
    59 service of unicast.  Acceptable as quick-and-dirty hack, the approach 
    60 is not tenable for general purpose -- and increasingly more common -- 
    61 applications of point-to-point routing including interactive 
    62 communications, sensor/actuator pairings, or TCP 
    63 acknowledgements.\footnote{Which must occur with much higher frequency 
    64   than bulk transport acknowledgements.}  A second path -- embracing 
    65 recent developments in point-to-point wireless mesh routing -- leads 
    66 to an architecturally elegant solution, but not one without its share 
    67 of practical challenges.  Some protocols suffer from poor 
    68 stretch~\cite{?}.  Some require a location service~\cite{bls} to 
    69 decouple a node's name from its dynamic virtual coordinates~\cite{?}. 
    70 Some require nodes to be aware of their coordinates in physical 
    71 space~\cite{?}.  Some require non-trivial state or frequent 
    72 messaging~\cite{?}.  Some require stable landmarks~\cite{?}.  And all 
    73 have non-trivial code overhead in excess of collection. 
     57We now face a fork in the road.  One path -- representing current 
     58practice -- continues to abuse flooding in the service of unicast. 
     59Acceptable as quick-and-dirty hack, the approach is not tenable for 
     60general purpose -- and increasingly more common -- applications of 
     61point-to-point routing including interactive communications, 
     62sensor/actuator pairings, or TCP acknowledgements.\footnote{Which 
     63  occur more frequently than bulk transport acks.}  A second path -- 
     64embracing recent developments in point-to-point wireless mesh routing 
     65-- leads to an architecturally elegant solution, but one with its 
     66share of practical challenges.  Some protocols suffer from poor 
     67stretch~\cite{ref:bvr}.  Some require a location service~\cite{bls} to 
     68decouple a node's names from dynamic 
     69addresses~\cite{ref:bvr,s4-nsdi}. Some require non-trivial state or 
     70frequent messaging~\cite{aodv}.  Some require stable 
     71landmarks~\cite{ref:bvr}.  And all have non-trivial overhead. 
    7472 
    7573This paper embraces a third path that preserves collection routing, 
    … …  
    7876pragmatic, evolutionary, and architecturally-principled way forward. 
    7977Our design begins where collection ends: by creating a collection tree 
    80 link state database at the root, itself populated using a collection 
    81 protocol.  With knowledge of the collection topology, point-to-point 
    82 routing is simple: a node sends data to the root and the root source 
    83 routes the data to the destination~\cite{hui08}.  Although this design 
    84 is simple, its use of triangle routing leads to a worst-case stretch 
    85 of twice the network diameter. 
     78link state database at the root, itself populated using collection. 
     79With knowledge of the collection topology, point-to-point is simple: a 
     80node sends data to the root and it source routes the data to the 
     81destination~\cite{hui}.  Although simple, triangle routing leads to a 
     82worst-case stretch of twice the diameter. 
    8683 
    87 Our design departs from the literature at this point.  In our scheme, 
    88 nodes periodically report to the root a subset of their neighbors and 
    89 quality of the connecting links.  Over time, as these data-, timer-, 
    90 or change-driven reports are sent, a more complete picture of the 
    91 network's link state emerges at the root.  Since the cross edges in 
    92 the collection spanning tree are critical for reducing stretch between 
    93 many node pairs, these cross edges must be discovered, evaluated, and 
    94 reported, raising the question of how to balance exploration and 
    95 exploitation. 
     84Our design departs from the sensornet literature at this point and 
     85adopts mechanisms from enterprise networking~\cite{ethane}, with 
     86changes to adapt to the unique characteristics of low-power, lossy 
     87wireless links.  In our scheme, nodes periodically report a subset of 
     88good neighbor links to the root.  Over time, as these data-, timer-, 
     89or change-driven reports are sent, a picture of the network's link 
     90state emerges at the root.  Since the cross edges in the collection 
     91spanning tree are useful for reducing stretch between many node pairs, 
     92they must be discovered, tested, and reported, raising the question of 
     93how to balance exploration and exploitation.  We find that such a 
     94simple design provides high reliability, allows low stretch, and 
     95offers low overheard, while adhering to system architecture already in 
     96place. 
     97 
    9698 
    9799%PKD: STILL A FEW MORE PARAGRPAHS NEEDED. 
     100 
     101%% Although architecturally similar, low-power wireless links exhibit 
     102%% such loss and transients that they void and loss behaviors that pose 
     103%% many challenges assumptions underlying Ethane's operation, which must 
     104%% be addressed in our context.  Among the (invalid) assumptions are (i) 
     105%% a reliable path exists to the central controller; (ii) a consistent 
     106%% global view of the topology is available; and (iii) links are 
     107%% generally stable.  None of these assumptions hold in a wireless 
     108%% sensornet. 

  • docs/Lowthane/ipsn10/lowthane.tex

    r2751 r2766  
    111111 
    112112\input{intro}  
     113\input{overview} 
    113114\input{design}  
    114115\input{evaluation}