Subject: Re: [Roll] WG Last Call on draft-ietf-roll-trickle-02

From: JP Vasseur <[email-masked]>
Date: Tue, 3 Aug 2010 15:35:41 +0200

Please find below comments on draft-ietf-roll-trickle-02 (search for  
JP>).
Co-chair hat on (shepherding the document)

Networking Working Group                                        P. Levis
Internet-Draft                                       Stanford University
Intended status: Informational                                T. Clausen
JP> So far good consensus to move to Std track. Let's wait until
end of LC.

Expires: January 7, 2011                        LIX, Ecole Polytechnique
                                                                   J.  
Hui
                                                    Arch Rock  
Corporation
                                                               O.  
Gnawali
                                                      Stanford  
University
                                                                    J.  
Ko
                                                 Johns Hopkins  
University
                                                             July 6,  
2010

                          The Trickle Algorithm
                        draft-ietf-roll-trickle-02

Abstract

    The Trickle algorithm allows wireless nodes to exchange information

JP> Not restricted to wireless. Even if we do not use some features,  
dynamic
timer adjustments are still useful in PLC/wired environments.
    in a highly robust, energy efficient, simple, and scalable manner.
    Dynamically adjusting transmission windows allows Trickle to spread
    new information on the scale of link-layer transmission times while
    sending only a few messages per hour
JP> I would suggest to be more generic (not specify "hour", "mn", since
that all depends on the parameter settings)
when information does not
    change.  A simple suppression mechanism and transmission point
    selection allows Trickle's communication rate to scale
    logarithmically with density.  This document describes Trickle
JP> s/trickle/the trickle algorithm
and
    considerations in its use.

Status of this Memo

    This Internet-Draft is submitted to IETF in full conformance with  
the
    provisions of BCP 78 and BCP 79.

    Internet-Drafts are working documents of the Internet Engineering
    Task Force (IETF), its areas, and its working groups.  Note that
    other groups may also distribute working documents as Internet-
    Drafts.

    Internet-Drafts are draft documents valid for a maximum of six  
months
    and may be updated, replaced, or obsoleted by other documents at any
    time.  It is inappropriate to use Internet-Drafts as reference
    material or to cite them other than as "work in progress."

    The list of current Internet-Drafts can be accessed at
    http://www.ietf.org/ietf/1id-abstracts.txt.

    The list of Internet-Draft Shadow Directories can be accessed at
    http://www.ietf.org/shadow.html.

Levis, et al.            Expires January 7, 2011                [Page 1]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

    This Internet-Draft will expire on January 7, 2011.

Copyright Notice

    Copyright (c) 2010 IETF Trust and the persons identified as the
    document authors.  All rights reserved.

    This document is subject to BCP 78 and the IETF Trust's Legal
    Provisions Relating to IETF Documents
    (http://trustee.ietf.org/license-info) in effect on the date of
    publication of this document.  Please review these documents
    carefully, as they describe your rights and restrictions with  
respect
    to this document.  Code Components extracted from this document must
    include Simplified BSD License text as described in Section 4.e of
    the Trust Legal Provisions and are provided without warranty as
    described in the BSD License.

Levis, et al.            Expires January 7, 2011                [Page 2]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

Table of Contents

    1.   
Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 3
    2.   
Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3
    3.  Trickle Algorithm  
Overview  . . . . . . . . . . . . . . . . . . 3
    4.  Trickle  
Algorithm . . . . . . . . . . . . . . . . . . . . . . . 4
      4.1.  Parameters and  
Variables  . . . . . . . . . . . . . . . . . 4
      4.2.  Algorithm  
Description . . . . . . . . . . . . . . . . . . . 5
    5.  Using  
Trickle . . . . . . . . . . . . . . . . . . . . . . . . . 5
    6.  Operational  
Considerations  . . . . . . . . . . . . . . . . . . 6
      6.1.  Mismatched redundancy  
constants . . . . . . . . . . . . . . 6
      6.2.  Mismatched  
Imin . . . . . . . . . . . . . . . . . . . . . . 6
      6.3.  Mismatched  
Imax . . . . . . . . . . . . . . . . . . . . . . 7
      6.4.  Mismatched  
definitions  . . . . . . . . . . . . . . . . . . 7
      6.5.  Specifying the constant  
k . . . . . . . . . . . . . . . . . 7
      6.6.  Relationship between k and  
Imin . . . . . . . . . . . . . . 7
      6.7.  Tweaks and improvements to  
Trickle  . . . . . . . . . . . . 8
    7.   
Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . 8
    8.  IANA  
Considerations . . . . . . . . . . . . . . . . . . . . . . 8
    9.  Security  
Considerations . . . . . . . . . . . . . . . . . . . . 8
    10.  
References  . . . . . . . . . . . . . . . . . . . . . . . . . . 8
      10.1. Normative  
References  . . . . . . . . . . . . . . . . . . . 8
      10.2. Informative  
References  . . . . . . . . . . . . . . . . . . 9
    Authors'  
Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 9

Levis, et al.            Expires January 7, 2011                [Page 3]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

1.  Introduction

    The Trickle algorithm is designed for wireless networks.
JP> please use the LLN terminology and point to [I-D-ietf.roll- 
terminology] ID.
It
    establishes a density-aware local broadcast with an underlying
    consistency model that guides when a node communicates.  When a
    node's data does not agree
JP> you may want to clarify the term "agree"
with its neighbors, it communicates
    quickly to resolve the inconsistency.
JP> Please define "inconsistency" (an example should suffice)
When nodes agree, they slow
    their communication rate exponentially, such that nodes send at most
    a few packets per hour.
JP> See comments on "hour"
Instead of flooding a network with packets,
    the algorithm controls the send rate so each node hears a small
JP> avoid "small", "large", ... it is all relative.

    trickle of packets, just enough to stay consistent.  Furthermore, by
    relying only on local broadcasts,
JP> broadcast or multicast
Trickle handles network re-
    population,
JP> Define "re-population"
is robust to network transience, loss, and disconnection,
    and requires very little state (implementations use 4-11 bytes).

JP> Mention that current implementations typically requires ....

    While Trickle was originally designed for reprogramming protocols
    (where the data is the code of the program being updated),  
experience
    has shown it to be a powerful mechanism that can be applied to wide
    range of protocol design problems, including control traffic timing,
    multicast propagation, and route discovery.

    This document describes the Trickle algorithm and provides  
guidelines
    for its use.  It also states requirements for protocol  
specifications
    that use Trickle.  This document does not provide results on
    Trickle's performance or behavior, nor does it explain the
    algorithm's design in detail: interested readers should refer to
    [Levis04] and [Levis08].

2.  Terminology

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
    "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
    "OPTIONAL" in this document are to be interpreted as described in  
RFC
    2119 [RFC2119].

3.  Trickle Algorithm Overview

    Trickle's basic primitive is simple: every so often, a node  
transmits
    code metadata
JP> s/code metadata/information (e.g. routing protocol, software  
updates, ...)

if it has not heard a few other nodes transmit the same
    thing.
JP> s/thing/information
This allows Trickle to scale to thousand-fold variations in
    network density, quickly propagate updates, distribute transmission
    load evenly, be robust to transient disconnections, handle network
    repopulations, and impose a maintenance overhead on the order of a
    few packets per hour.
JP> same comment about "hour"

    Trickle sends all messages to the local broadcast address.
JP> or multicast (to be updated throughout the document)

There are

Levis, et al.            Expires January 7, 2011                [Page 4]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

    two possible results to a Trickle broadcast: either every node that
    hears the message is up to date, or a recipient detects the need for
    an update.  Detection can be the result of either an out-of-date  
node
    hearing someone has new code, or an updated node hearing someone has
    old code.
JP> this comes from one application of trickle (code update), could  
you make it
more general (e.g. fresher information)
As long as every node communicates somehow - either
    receives or transmits - the need for an update will be detected.

    For example, consider a simple case where "up to date" is defined by
    version numbers (e.g., network configuration).  If node A broadcasts
    that it has version V, but B has version V+1, then B knows that A
    needs an update.  Similarly, if B broadcasts that it has V+1
JP> s/V+1/version V+1
, A knows
    that it needs an update.  If B broadcasts updates, then all of its
    neighbors can receive them without having to advertise their need.
    Some of these recipients might not even have heard A's transmission.

    In this example, it does not matter who first transmits, A or B;
    either case will detect the inconsistency.  All that matters is that
    some nodes communicate with one another at some nonzero rate.  As
    long as the network is connected and there is some minimum
    communication rate for each node, the network will reach eventual
    consistency.

    The fact that communication can be either transmission or reception
    enables Trickle
JP> s/Trickle/the Trickle algorithm
to operate in sparse as well as dense networks.  A
    single, disconnected node must transmit at the communication rate.
    In a lossless, single-hop network of size n, the sum of  
transmissions
    over the network is the communication rate, so for each node it is
    1/n.  Sparser networks require more transmissions per node, but
    utilization of the radio channel over space will not increase.  This
    is an important property in wireless networks,
JP> and other shared media
where the channel is a
    valuable shared resource.  Additionally, reducing transmissions in
    dense networks conserves system energy.

4.  Trickle Algorithm

    This section describes the Trickle algorithm.

4.1.  Parameters and Variables

    A Trickle timer has three configuration parameters: the minimum
    interval size Imin, the maximum interval size Imax, and a redundancy
    constant k:

    o  The minimum interval size is defined in units of time (e.g.,
       milliseconds, seconds).  For example, a protocol might define the
       minimum interval as 100 milliseconds.

Levis, et al.            Expires January 7, 2011                [Page 5]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

    o  The maximum interval size is described as a number of doublings  
of
       the minimum interval size (the base-2 log(max/min)).  For  
example,
       a protocol might define the maximum interval as 16.  If the
       minimum interval is 100ms, then the maximum interval is 100ms *
       65536, 6,553.6 seconds, or approximately 109 minutes.

    o  The redundancy constant is a natural number (an integer greater
       than zero).
JP> Could be equal to infinity (and encoded as 0) => no suppression.

    In addition to these three parameters, Trickle maintains three
    variables:

    o  I, the current interval size

    o  t, a time within the current interval, and

    o  c, a counter.

4.2.  Algorithm Description

    The Trickle algorithm has five rules:

    1.  When an interval begins, Trickle resets c to 0 and sets t to a
        random point in the interval, taken from the range [I/2, I).
JP> s/I)/I]

    2.  Whenever Trickle hears a transmission that is "consistent," it
        increments counter c.

    3.  At time t, Trickle transmits if and only if counter c is less
        than the redundancy constant k.

    4.  When an interval expires,
JP> this may not be obvious first time you read it. interval=t or I  
(question
was asked on the mailing list in the past).
Trickle doubles the interval length.
        If this new interval length would be longer than Imax, Trickle
        sets the interval length I to be Imax.

    5.  If Trickle hears a transmission that is "inconsistent," the
        Trickle timer resets.  If I is greater than Imin,
JP> how could that happen that I <  Imin?
resetting a
        Trickle timer sets I to Imin and begins a new interval.  If I is
        equal to Imin, resetting a Trickle timer does nothing.  Trickle
        may also reset the timer in response to external "events."

    The terms consistent, inconsistent and event are in quotes because
    their meaning depends on the use of Trickle.

5.  Using Trickle

    A protocol specification that uses Trickle MUST specify:

Levis, et al.            Expires January 7, 2011                [Page 6]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

    o  Default values for Imin, Imax, and k.
JP> s/Default values/Value
Because link layers can
       vary widely in their properties, the default
JP> remove "default"
value of Imin should
       be specified in terms of the worst-case latency of a link layer
       transmission.  For example, a specification should say "the
       default value of Imin is 4 times the worst case link layer
       latency"
JP> may be worth how you define "latency"
and should not say "the default value of Imin is 500
       milliseconds."  Worst case latency is the time until the first
       link-layer transmission of the frame assuming an idle channel
       (does not include backoff, virtual carrier sense, etc.).

    o  What constitutes a "consistent" transmission.

    o  What constitutes an "inconsistent" transmission.

    o  What "events," if any, besides inconsistent transmissions that
       reset the Trickle timer.

6.  Operational Considerations

    It is RECOMMENDED that a protocol which uses Trickle include
    mechanisms to inform nodes of configuration parameters at runtime.
    However, it is not always possible to do so.  In the cases where
    different nodes have different configuration parameters, Trickle may
    have unintended behaviors.  This section outlines some of those
    behaviors and operational considerations as educational exercises.

6.1.  Mismatched redundancy constants

    If nodes do not agree on the redundancy constant k, then nodes with
    higher values of k will transmit more often than nodes with lower
    values of k.  In some cases, this increased load can be independent
    of the density.  For example, consider a network where all nodes but
    one have k=1, and this one node has k=2.  The different node can end
    up transmitting on every interval: it is maintaining a communication
    rate of 2 with only itself.  Hence, the danger of mismatched k  
values
    is uneven transmission load that can deplete the energy of some
    nodes.
JP> Still this does not lead to interoperability issues.
Don't we want to recommend consistent configuration ? If you agree, then
these comments should go at the end of this section (or beginning) but  
they
apply to several kind of mismatches

6.2.  Mismatched Imin

    If nodes do not agree on Imin, then some nodes, on hearing
    inconsistent messages, will transmit sooner than others.  These
    faster nodes will have their intervals grow to similar size as the
    slower nodes within a single slow interval time, but in that period
    may suppress the slower nodes.  However, such suppression will end
    after the first slow interval, when the nodes generally agree on the
    interval size.  Hence, mismatched Imin values are usually not a

Levis, et al.            Expires January 7, 2011                [Page 7]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

    significant concern.

6.3.  Mismatched Imax

    If nodes do not agree on Imax, then this can cause long-term  
problems
    with transmission load.  Nodes with small Imax values will transmit
    faster, suppressing those with larger Imax values.  The nodes with
    larger Imax values, always suppressed, will never transmit.  In the
    base case, when the network is consistent, this can cause long-term
    inequities in energy cost.

6.4.  Mismatched definitions

    If nodes do not agree on what constitutes a consistent or
    inconsistent transmission, then Trickle may fail to operate  
properly.
    For example, if a receiver thinks a transmission is consistent, but
    the transmitter (if in the receivers situation) would have thought  
it
    inconsistent, then the receiver will not respond properly and inform
    the transmitter.  This can lead the network to not reach a  
consistent
    state.  For this reason, unlike the configuration constants k, Imin,
    and Imax, consistency definitions should be clearly stated in the
    protocol and should not be configured at runtime.

JP> I would suggest a MUST instead of a should in the sentence above.

6.5.  Specifying the constant k

    There are some edge cases where a protocol may wish to use Trickle
    with its suppression disabled (k is set to infinity).  In general,
    this approach is highly dangerous and it is NOT RECOMMENDED.
JP> I would strongly suggest to soften this statement. Just explain the
consequences.

    Disabling suppression means that every node will always send on  
every
    interval, and can lead to congestion in dense networks.  This
    approach is especially dangerous
JP> same comment
if many nodes reset their intervals
    at the same time.  In general, it is much more desirable to set k to
    a high value (e.g., 5 or 10) than infinity.  Typical values for k  
are
    1-5: these achieve a good balance between redundancy and low cost.

JP> I would suggest to add refs here.
    Nevertheless, there are situations where a protocol may wish to turn
    off Trickle suppression.  Because k is a natural number
    (Section 4.1), c=0 has no useful meaning.  If a protocol allows k to
    be dynamically configured, a value of 0 remains unused.  For ease of
    debugging and packet inspection, having the parameter describe (c-1)
JP> c-1 ?

    can be counter-productive.  Instead, it is RECOMMENDED that  
protocols
    which require turning off suppression reserve c=0 to mean  
c=infinity.

6.6.  Relationship between k and Imin

    Finally, a protocol SHOULD set k and Imin such that Imin is at least
    two to three as long as it takes to transmit k packets.  Otherwise,
    if more than k nodes reset their intervals to Imin, the resulting

Levis, et al.            Expires January 7, 2011                [Page 8]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

    communication will lead to congestion and significant packet loss.
    Experimental results have shown that packet losses from congestion
    reduce Trickle's efficiency [Levis04].
JP> Well ... it is true in most networks, but may not be completely  
applicable to
non wireless networks though. You may want to mention it.

6.7.  Tweaks and improvements to Trickle

    Trickle is based on a small number of simple, tightly integrated
    mechanisms that are highly robust to challenging network
    environments.

    >>In our experiences using Trickle, attempts to tweak
    its behavior are typically not worth the cost.  As written, the
    algorithm is already highly efficient: further reductions in
    transmissions or response time come at the cost of failures in edge
    cases.  Based on our experiences, we urge protocol designers to
    suppress the instinct to tweak or improve Trickle without a great
    deal of experimental evidence that the change does not violate its
    assumptions and break the algorithm in edge cases.<<
JP> You may want to soften this statement.

    This warning in mind, Trickle is far from perfect.
JP> nobody's perfect. Not needed in the document.
For example,
    Trickle suppression typically leads sparser nodes to transmit more
    than denser ones; it is far from the optimal computation of a  
minimum
    cover.  However, in dynamic network environments such as wireless,
    the coordination needed to compute the optimal set of transmissions
    is typically much greater than the benefits it provides.  One of the
    benefits of Trickle
JP> s/Trickle/the Trickle algorithm
is that it is so simple to implement and requires
    so little state yet operates so efficiently.  Efforts to improve it
    should be weighed against the cost of increased complexity.

7.  Acknowledgements

JP> to be done

8.  IANA Considerations

    This document has no IANA considerations.

9.  Security Considerations

    This document has no security considerations.

10.  References

10.1.  Normative References

    [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
               Requirement Levels", BCP 14, RFC 2119, March 1997.

Levis, et al.            Expires January 7, 2011                [Page 9]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

10.2.  Informative References

    [Levis04]  Levis, P., Patel, N., Culler, D., and S. Shenker,
               "Trickle: A Self-Regulating Algorithm for Code  
Propagation
               and Maintenance in Wireless Sensor Networks"",  
Proceedings
               of the First USENIX/ACM Symposium on Networked Systems
               Design and Implementation NSDI 2004, March 2004,
               <http://portal.acm.org/citation.cfm?id=1251177>.

    [Levis08]  Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S.,
               Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and  
A.
               Woo, "The Emergence of a Networking Primitive in Wireless
               Sensor Networks", Communications of the ACM, v.51 n.7,
               July 2008,
               <http://portal.acm.org/citation.cfm?id=1364804>.

Authors' Addresses

    Philip Levis
    Stanford University
    358 Gates Hall, Stanford University
    Stanford, CA  94305
    USA

    Phone: +1 650 725 9064
    Email: [email-masked]

    Thomas Heide Clausen
    LIX, Ecole Polytechnique

    Phone: +33 6 6058 9349
    Email: [email-masked]

    Jonathan Hui
    Arch Rock Corporation
    501 Snd St., Suite 410
    San Francisco, CA  94107
    USA

    Email: [email-masked]

Levis, et al.            Expires January 7, 2011               [Page 10]

Internet-Draft         draft-ietf-roll-trickle-02              July 2010

    Omprakash Gnawali
    Stanford University
    S255 Clark Center, 318 Campus Drive
    Stanford, CA  94305
    USA

    Phone: +1 650 725 6086
    Email: [email-masked]

    JeongGil Ko
    Johns Hopkins University
    3400 N. Charles St., 224 New Engineering Building
    Baltimore, MD  21218
    USA

    Phone: +1 410 516 4312
    Email: [email-masked]

Levis, et al.            Expires January 7, 2011               [Page 11]


Thanks.

JP.

On Jul 28, 2010, at 10:05 AM, JP Vasseur wrote:

> Dear WG,
>
> draft-ietf-roll-trickle-02 is stable and now ready for WG Last Call.
>
> This starts a 2-week Working Group last call ending on August 11 at  
> 9:00am ET.
>
> Please send your comments to the authors and the list.
>
> Thanks.
>
> JP.
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: JP Vasseur <[email-masked]>
Date: Tue, 3 Aug 2010 15:36:04 +0200

Begin forwarded message:

> From: JP Vasseur <[email-masked]>
> Date: August 3, 2010 3:35:41 PM CEDT
> To: JP Vasseur <[email-masked]>
> Cc: ROLL WG <[email-masked]>
> Subject: Re: [Roll] WG Last Call on draft-ietf-roll-trickle-02
>
> J. Ko
>    o  The maximum interval size is described as a number of  
> doublings of
> variables:    o  I, the current interval size    o  t, a time within  
> the current interval, and    o  c, a counter.
>
> these comments should go at the end of this section (or beginning)  
> but they
>  6.2.  Mismatched Imin    If nodes do not agree on Imin, then some  
> nodes, on hearing   inconsistent messages, will transmit sooner than  
> others.  These   faster nodes will have their intervals grow to  
> similar size as the   slower nodes within a single slow interval  
> time, but in that period   may suppress the slower nodes.  However,  
> such suppression will end   after the first slow interval, when the  
> nodes generally agree on the   interval size.  Hence, mismatched  
> Imin values are usually not a Levis, et al.            Expires  
> January 7, 2011                [Page 7]  Internet-Draft         draft 
> -ietf-roll-trickle-02              July 2010    significant concern.  
> 6.3.  Mismatched Imax    If nodes do not agree on Imax, then this  
> can cause long-term problems   with transmission load.  Nodes with  
> small Imax values will transmit   faster, suppressing those with  
> larger Imax values.  The nodes with   larger Imax values, always  
> suppressed, will never transmit.  In the   base case, when the  
> network is consistent, this can cause long-term   inequities in  
> energy cost. 6.4.  Mismatched definitions    If nodes do not agree  
> on what constitutes a consistent or   inconsistent transmission,  
> then Trickle may fail to operate properly.   For example, if a  
> receiver thinks a transmission is consistent, but   the transmitter  
> (if in the receivers situation) would have thought it    
> inconsistent, then the receiver will not respond properly and  
> inform   the transmitter.  This can lead the network to not reach a  
> consistent   state.  For this reason, unlike the configuration  
> constants k, Imin,   and Imax, consistency definitions should be  
> clearly stated in the   protocol and should not be configured at  
> runtime.
> protocols   which require turning off suppression reserve c=0 to  
> mean c=infinity. 6.6.  Relationship between k and Imin    Finally, a  
> protocol SHOULD set k and Imin such that Imin is at least   two to  
> three as long as it takes to transmit k packets.  Otherwise,   if  
> more than k nodes reset their intervals to Imin, the resulting  
> Levis, et al.            Expires January 7, 2011                 
> [Page 8]  Internet-Draft         draft-ietf-roll-trickle-02           
>     July 2010    communication will lead to congestion and  
> significant packet loss.   Experimental results have shown that  
> packet losses from congestion   reduce Trickle's efficiency [Levis04].
>  6.7.  Tweaks and improvements to Trickle    Trickle is based on a  
> small number of simple, tightly integrated   mechanisms that are  
> highly robust to challenging network   environments.
>
>  8.  IANA Considerations    This document has no IANA  
> considerations. 9.  Security Considerations    This document has no  
> security considerations. 10.  References 10.1.  Normative  
> References    [RFC2119]  Bradner, S., "Key words for use in RFCs to  
> Indicate              Requirement Levels", BCP 14, RFC 2119, March  
> 1997. Levis, et al.            Expires January 7,  
> 2011                [Page 9]  Internet-Draft         draft-ietf-roll- 
> trickle-02              July 2010 10.2.  Informative References     
> [Levis04]  Levis, P., Patel, N., Culler, D., and S.  
> Shenker,              "Trickle: A Self-Regulating Algorithm for Code  
> Propagation              and Maintenance in Wireless Sensor  
> Networks"", Proceedings              of the First USENIX/ACM  
> Symposium on Networked Systems              Design and  
> Implementation NSDI 2004, March 2004,              <http://portal.acm.org/citation.cfm?id=1251177 
> >.    [Levis08]  Levis, P., Brewer, E., Culler, D., Gay, D., Madden,  
> S.,              Patel, N., Polastre, J., Shenker, S., Szewczyk, R.,  
> and A.              Woo, "The Emergence of a Networking Primitive in  
> Wireless              Sensor Networks", Communications of the ACM, v. 
> 51 n.7,              July 2008,              <http://portal.acm.org/citation.cfm?id=1364804 
> >. Authors' Addresses    Philip Levis   Stanford University   358  
> Gates Hall, Stanford University   Stanford, CA  94305   USA     
> Phone: +1 650 725 9064   Email: [email-masked]    Thomas Heide  
> Clausen   LIX, Ecole Polytechnique    Phone: +33 6 6058 9349    
> Email: [email-masked]    Jonathan Hui   Arch Rock  
> Corporation   501 Snd St., Suite 410   San Francisco, CA  94107    
> USA    Email: [email-masked] Levis, et al.            Expires  
> January 7, 2011               [Page 10]  Internet-Draft         draft 
> -ietf-roll-trickle-02              July 2010    Omprakash Gnawali    
> Stanford University   S255 Clark Center, 318 Campus Drive    
> Stanford, CA  94305   USA    Phone: +1 650 725 6086   Email: [email-masked] 
>     JeongGil Ko   Johns Hopkins University   3400 N. Charles St.,  
> 224 New Engineering Building   Baltimore, MD  21218   USA    Phone:  
> +1 410 516 4312   Email: [email-masked] Levis, et al.             
> Expires January 7, 2011               [Page 11] 
>
> Thanks.
>
> JP.
>

---

From: "Cedric Chauvenet" <[email-masked]>
Date: Tue, 3 Aug 2010 18:06:13 +0200

I vote for moving trickle to Std track.
  ----- Original Message ----- 
  From: JP Vasseur 
  To: ROLL WG 
  Sent: Tuesday, August 03, 2010 3:36 PM
  Subject: [Roll] Fwd: WG Last Call on draft-ietf-roll-trickle-02

  Begin forwarded message:

    Please find below comments on draft-ietf-roll-trickle-02 (search for JP>).
    Co-chair hat on (shepherding the document)

Networking Working Group                                        P. Levis
Internet-Draft                                       Stanford University
Intended status: Informational                                T. ClausenJP> So far good consensus to move to Std track. Let's wait untilend of LC.Expires: January 7, 2011                        LIX, Ecole Polytechnique
                                                                  J. Hui
                                                   Arch Rock Corporation
                                                              O. Gnawali
                                                     Stanford University
                                                                   J. Ko
                                                Johns Hopkins University
                                                            July 6, 2010

                         The Trickle Algorithm

Abstract

   The Trickle algorithm allows wireless nodes to exchange information
JP> Not restricted to wireless. Even if we do not use some features, dynamictimer adjustments are still useful in PLC/wired environments.   in a highly robust, energy efficient, simple, and scalable manner.
   Dynamically adjusting transmission windows allows Trickle to spread
   new information on the scale of link-layer transmission times while
   sending only a few messages per hour JP> I would suggest to be more generic (not specify "hour", "mn", since that all depends on the parameter settings)when information does not
   change.  A simple suppression mechanism and transmission point
   selection allows Trickle's communication rate to scale
   logarithmically with density.  This document describes Trickle JP> s/trickle/the trickle algorithmand
   considerations in its use.

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."



Copyright Notice

   carefully, as they describe your rights and restrictions with respect



Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 3
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3
   3.  Trickle Algorithm Overview  . . . . . . . . . . . . . . . . . . 3
   4.  Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . . 4
     4.1.  Parameters and Variables  . . . . . . . . . . . . . . . . . 4
     4.2.  Algorithm Description . . . . . . . . . . . . . . . . . . . 5
   5.  Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . . 5
   6.  Operational Considerations  . . . . . . . . . . . . . . . . . . 6
     6.1.  Mismatched redundancy constants . . . . . . . . . . . . . . 6
     6.2.  Mismatched Imin . . . . . . . . . . . . . . . . . . . . . . 6
     6.3.  Mismatched Imax . . . . . . . . . . . . . . . . . . . . . . 7
     6.4.  Mismatched definitions  . . . . . . . . . . . . . . . . . . 7
     6.5.  Specifying the constant k . . . . . . . . . . . . . . . . . 7
     6.6.  Relationship between k and Imin . . . . . . . . . . . . . . 7
     6.7.  Tweaks and improvements to Trickle  . . . . . . . . . . . . 8
   7.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . 8
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8
   9.  Security Considerations . . . . . . . . . . . . . . . . . . . . 8
   10. References  . . . . . . . . . . . . . . . . . . . . . . . . . . 8
     10.1. Normative References  . . . . . . . . . . . . . . . . . . . 8
     10.2. Informative References  . . . . . . . . . . . . . . . . . . 9
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 9



1.  Introduction

   The Trickle algorithm is designed for wireless networks.  JP> please use the LLN terminology and point to [I-D-ietf.roll-terminology] ID.It
   establishes a density-aware local broadcast with an underlying
   consistency model that guides when a node communicates.  When a
   node's data does not agree JP> you may want to clarify the term "agree"with its neighbors, it communicates
   quickly to resolve the inconsistency.  JP> Please define "inconsistency" (an example should suffice)When nodes agree, they slow
   their communication rate exponentially, such that nodes send at most
   a few packets per hour.  JP> See comments on "hour"Instead of flooding a network with packets,
   the algorithm controls the send rate so each node hears a smallJP> avoid "small", "large", ... it is all relative.   trickle of packets, just enough to stay consistent.  Furthermore, by
   relying only on local broadcasts, JP> broadcast or multicastTrickle handles network re-
   population, JP> Define "re-population"is robust to network transience, loss, and disconnection,
   and requires very little state (implementations use 4-11 bytes).
JP> Mention that current implementations typically requires ....    While Trickle was originally designed for reprogramming protocols
   (where the data is the code of the program being updated), experience
   has shown it to be a powerful mechanism that can be applied to wide
   range of protocol design problems, including control traffic timing,
   multicast propagation, and route discovery.

   This document describes the Trickle algorithm and provides guidelines
   for its use.  It also states requirements for protocol specifications
   that use Trickle.  This document does not provide results on
   Trickle's performance or behavior, nor does it explain the
   algorithm's design in detail: interested readers should refer to
   [Levis04] and [Levis08].

2.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in RFC
   2119 [RFC2119].

   Trickle's basic primitive is simple: every so often, a node transmits
   code metadata JP> s/code metadata/information (e.g. routing protocol, software updates, ...)if it has not heard a few other nodes transmit the same
   thing.  JP> s/thing/informationThis allows Trickle to scale to thousand-fold variations in
   network density, quickly propagate updates, distribute transmission
   load evenly, be robust to transient disconnections, handle network
   repopulations, and impose a maintenance overhead on the order of a
   few packets per hour.JP> same comment about "hour"   Trickle sends all messages to the local broadcast address.  JP> or multicast (to be updated throughout the document)There are



   two possible results to a Trickle broadcast: either every node that
   hears the message is up to date, or a recipient detects the need for
   an update.  Detection can be the result of either an out-of-date node
   hearing someone has new code, or an updated node hearing someone has
   old code.  JP> this comes from one application of trickle (code update), could you make itmore general (e.g. fresher information)As long as every node communicates somehow - either
   receives or transmits - the need for an update will be detected.

   needs an update.  Similarly, if B broadcasts that it has V+1JP> s/V+1/version V+1, A knows

   The fact that communication can be either transmission or reception
   enables Trickle JP> s/Trickle/the Trickle algorithmto operate in sparse as well as dense networks.  A
   single, disconnected node must transmit at the communication rate.
   In a lossless, single-hop network of size n, the sum of transmissions
   over the network is the communication rate, so for each node it is
   1/n.  Sparser networks require more transmissions per node, but
   utilization of the radio channel over space will not increase.  This
   is an important property in wireless networks, JP> and other shared mediawhere the channel is a
   valuable shared resource.  Additionally, reducing transmissions in
   dense networks conserves system energy.

4.  Trickle Algorithm



   o  The maximum interval size is described as a number of doublings of
      the minimum interval size (the base-2 log(max/min)).  For example,
      a protocol might define the maximum interval as 16.  If the
      minimum interval is 100ms, then the maximum interval is 100ms *
      65536, 6,553.6 seconds, or approximately 109 minutes.

   o  The redundancy constant is a natural number (an integer greater
      than zero).JP> Could be equal to infinity (and encoded as 0) => no suppression.   In addition to these three parameters, Trickle maintains three   variables:    o  I, the current interval size    o  t, a time within the current interval, and    o  c, a counter.4.2.  Algorithm Description

   1.  When an interval begins, Trickle resets c to 0 and sets t to a
       random point in the interval, taken from the range [I/2, I).
JP> s/I)/I]   2.  Whenever Trickle hears a transmission that is "consistent," it
       increments counter c.

   4.  When an interval expires, JP> this may not be obvious first time you read it. interval=t or I (questionwas asked on the mailing list in the past).Trickle doubles the interval length.
       If this new interval length would be longer than Imax, Trickle
       sets the interval length I to be Imax.

       Trickle timer resets.  If I is greater than Imin, JP> how could that happen that I <  Imin?resetting a

5.  Using Trickle



   o  Default values for Imin, Imax, and k.  JP> s/Default values/ValueBecause link layers can
      vary widely in their properties, the default JP> remove "default"value of Imin should
      be specified in terms of the worst-case latency of a link layer
      transmission.  For example, a specification should say "the
      default value of Imin is 4 times the worst case link layer
      latency" JP> may be worth how you define "latency"and should not say "the default value of Imin is 500
      milliseconds."  Worst case latency is the time until the first
      link-layer transmission of the frame assuming an idle channel
      (does not include backoff, virtual carrier sense, etc.).

   If nodes do not agree on the redundancy constant k, then nodes with
   higher values of k will transmit more often than nodes with lower
   values of k.  In some cases, this increased load can be independent
   of the density.  For example, consider a network where all nodes but
   one have k=1, and this one node has k=2.  The different node can end
   up transmitting on every interval: it is maintaining a communication
   rate of 2 with only itself.  Hence, the danger of mismatched k values
   is uneven transmission load that can deplete the energy of some
   nodes.JP> Still this does not lead to interoperability issues.Don't we want to recommend consistent configuration ? If you agree, thenthese comments should go at the end of this section (or beginning) but theyapply to several kind of mismatches 6.2.  Mismatched Imin    If nodes do not agree on Imin, then some nodes, on hearing   inconsistent messages, will transmit sooner than others.  These   faster nodes will have their intervals grow to similar size as the   slower nodes within a single slow interval time, but in that period   may suppress the slower nodes.  However, such suppression will end   after the first slow interval, when the nodes generally agree on the   interval size.  Hence, mismatched Imin values are usually not a Levis, et al.            Expires January 7, 2011                [Page 7]  Internet-Draft         draft-ietf-roll-trickle-02              July 2010    significant concern. 6.3.  Mismatched Imax    If nodes do not agree on Imax, then this can cause long-term problems   with transmission load.  Nodes with small Imax values will transmit   faster, suppressing those with larger Imax values.  The nodes with   larger Imax values, always suppressed, will never transmit.  In the   base case, when the network is consistent, this can cause long-term   inequities in energy cost. 6.4.  Mismatched definitions    If nodes do not agree on what constitutes a consistent or   inconsistent transmission, then Trickle may fail to operate properly.   For example, if a receiver thinks a transmission is consistent, but   the transmitter (if in the receivers situation) would have thought it   inconsistent, then the receiver will not respond properly and inform   the transmitter.  This can lead the network to not reach a consistent   state.  For this reason, unlike the configuration constants k, Imin,   and Imax, consistency definitions should be clearly stated in the   protocol and should not be configured at runtime. JP> I would suggest a MUST instead of a should in the sentence above.6.5.  Specifying the constant k

   There are some edge cases where a protocol may wish to use Trickle
   with its suppression disabled (k is set to infinity).  In general,
   this approach is highly dangerous and it is NOT RECOMMENDED.JP> I would strongly suggest to soften this statement. Just explain theconsequences.   Disabling suppression means that every node will always send on every
   interval, and can lead to congestion in dense networks.  This
   approach is especially dangerous JP> same commentif many nodes reset their intervals
   at the same time.  In general, it is much more desirable to set k to
   a high value (e.g., 5 or 10) than infinity.  Typical values for k are
   1-5: these achieve a good balance between redundancy and low cost.
JP> I would suggest to add refs here.   Nevertheless, there are situations where a protocol may wish to turn
   off Trickle suppression.  Because k is a natural number
   (Section 4.1), c=0 has no useful meaning.  If a protocol allows k to
   be dynamically configured, a value of 0 remains unused.  For ease of
   debugging and packet inspection, having the parameter describe (c-1)JP> c-1 ?   can be counter-productive.  Instead, it is RECOMMENDED that protocols   which require turning off suppression reserve c=0 to mean c=infinity. 6.6.  Relationship between k and Imin    Finally, a protocol SHOULD set k and Imin such that Imin is at least   two to three as long as it takes to transmit k packets.  Otherwise,   if more than k nodes reset their intervals to Imin, the resulting Levis, et al.            Expires January 7, 2011                [Page 8]  Internet-Draft         draft-ietf-roll-trickle-02              July 2010    communication will lead to congestion and significant packet loss.   Experimental results have shown that packet losses from congestion   reduce Trickle's efficiency [Levis04].JP> Well ... it is true in most networks, but may not be completely applicable tonon wireless networks though. You may want to mention it. 6.7.  Tweaks and improvements to Trickle    Trickle is based on a small number of simple, tightly integrated   mechanisms that are highly robust to challenging network   environments.     >>In our experiences using Trickle, attempts to tweak
   its behavior are typically not worth the cost.  As written, the
   algorithm is already highly efficient: further reductions in
   transmissions or response time come at the cost of failures in edge
   cases.  Based on our experiences, we urge protocol designers to
   suppress the instinct to tweak or improve Trickle without a great
   deal of experimental evidence that the change does not violate its
   assumptions and break the algorithm in edge cases.<<JP> You may want to soften this statement.   This warning in mind, Trickle is far from perfect.  JP> nobody's perfect. Not needed in the document.For example,
   Trickle suppression typically leads sparser nodes to transmit more
   than denser ones; it is far from the optimal computation of a minimum
   cover.  However, in dynamic network environments such as wireless,
   the coordination needed to compute the optimal set of transmissions
   is typically much greater than the benefits it provides.  One of the
   benefits of Trickle JP> s/Trickle/the Trickle algorithmis that it is so simple to implement and requires
   so little state yet operates so efficiently.  Efforts to improve it
   should be weighed against the cost of increased complexity.

7.  Acknowledgements
JP> to be done 8.  IANA Considerations    This document has no IANA considerations. 9.  Security Considerations    This document has no security considerations. 10.  References 10.1.  Normative References    [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate              Requirement Levels", BCP 14, RFC 2119, March 1997. Levis, et al.            Expires January 7, 2011                [Page 9]  Internet-Draft         draft-ietf-roll-trickle-02              July 2010 10.2.  Informative References    [Levis04]  Levis, P., Patel, N., Culler, D., and S. Shenker,              "Trickle: A Self-Regulating Algorithm for Code Propagation              and Maintenance in Wireless Sensor Networks"", Proceedings              of the First USENIX/ACM Symposium on Networked Systems              Design and Implementation NSDI 2004, March 2004,              <http://portal.acm.org/citation.cfm?id=1251177>.    [Levis08]  Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S.,              Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A.              Woo, "The Emergence of a Networking Primitive in Wireless              Sensor Networks", Communications of the ACM, v.51 n.7,              July 2008,              <http://portal.acm.org/citation.cfm?id=1364804>. Authors' Addresses    Philip Levis   Stanford University   358 Gates Hall, Stanford University   Stanford, CA  94305   USA    Phone: +1 650 725 9064   Email: [email-masked]    Thomas Heide Clausen   LIX, Ecole Polytechnique    Phone: +33 6 6058 9349   Email: [email-masked]    Jonathan Hui   Arch Rock Corporation   501 Snd St., Suite 410   San Francisco, CA  94107   USA    Email: [email-masked] Levis, et al.            Expires January 7, 2011               [Page 10]  Internet-Draft         draft-ietf-roll-trickle-02              July 2010    Omprakash Gnawali   Stanford University   S255 Clark Center, 318 Campus Drive   Stanford, CA  94305   USA    Phone: +1 650 725 6086   Email: [email-masked]    JeongGil Ko   Johns Hopkins University   3400 N. Charles St., 224 New Engineering Building   Baltimore, MD  21218   USA    Phone: +1 410 516 4312   Email: [email-masked] Levis, et al.            Expires January 7, 2011               [Page 11] 

    Thanks.

    JP.

      Dear WG,

      This starts a 2-week Working Group last call ending on August 11 at 9:00am ET.

      Thanks.

      JP.

------------------------------------------------------------------------------

---

From: "Don Sturek" <[email-masked]>
Date: Tue, 3 Aug 2010 10:03:11 -0700

+1 on making the Trickle draft standards track...

Don

From: [email-masked] [mailto:[email-masked]] On Behalf Of JP
Vasseur
Sent: Tuesday, August 03, 2010 6:36 AM
To: ROLL WG
Subject: [Roll] Fwd: WG Last Call on draft-ietf-roll-trickle-02

Begin forwarded message:

                         The Trickle Algorithm
 
Abstract

JP> Not restricted to wireless. Even if we do not use some features, dynamic
 
Status of this Memo

 

 

 
Copyright Notice

 

 

 

 

 

 

Table of Contents

 

 

 

 

 

1.  Introduction
 
JP> please use the LLN terminology and point to [I-D-ietf.roll-terminology]
ID.

2.  Terminology

 
   Trickle's basic primitive is simple: every so often, a node transmits
   code metadata 
JP> s/code metadata/information (e.g. routing protocol, software updates,
...)

There are

 

JP> this comes from one application of trickle (code update), could you make

 

4.  Trickle Algorithm

 

 

 
   o  The redundancy constant is a natural number (an integer greater
      than zero).
JP> Could be equal to infinity (and encoded as 0) => no suppression.
   In addition to these three parameters, Trickle maintains three
variables:    o  I, the current interval size    o  t, a time within the
current interval, and    o  c, a counter.

 

 

5.  Using Trickle

 

 

 

   If nodes do not agree on the redundancy constant k, then nodes with
   higher values of k will transmit more often than nodes with lower
   values of k.  In some cases, this increased load can be independent
   of the density.  For example, consider a network where all nodes but
   one have k=1, and this one node has k=2.  The different node can end
   up transmitting on every interval: it is maintaining a communication
   rate of 2 with only itself.  Hence, the danger of mismatched k values
   is uneven transmission load that can deplete the energy of some
   nodes.
JP> Still this does not lead to interoperability issues.
Don't we want to recommend consistent configuration ? If you agree, then
these comments should go at the end of this section (or beginning) but they
apply to several kind of mismatches
 6.2.  Mismatched Imin    If nodes do not agree on Imin, then some nodes, on
hearing   inconsistent messages, will transmit sooner than others.  These
faster nodes will have their intervals grow to similar size as the   slower
nodes within a single slow interval time, but in that period   may suppress
the slower nodes.  However, such suppression will end   after the first slow
interval, when the nodes generally agree on the   interval size.  Hence,
mismatched Imin values are usually not a Levis, et al.            Expires
January 7, 2011                [Page 7] 

 Internet-Draft         draft-ietf-roll-trickle-02              July 2010
significant concern. 6.3.  Mismatched Imax    If nodes do not agree on Imax,
then this can cause long-term problems   with transmission load.  Nodes with
small Imax values will transmit   faster, suppressing those with larger Imax
values.  The nodes with   larger Imax values, always suppressed, will never
transmit.  In the   base case, when the network is consistent, this can
cause long-term   inequities in energy cost. 6.4.  Mismatched definitions
If nodes do not agree on what constitutes a consistent or   inconsistent
transmission, then Trickle may fail to operate properly.   For example, if a
receiver thinks a transmission is consistent, but   the transmitter (if in
the receivers situation) would have thought it   inconsistent, then the
receiver will not respond properly and inform   the transmitter.  This can
lead the network to not reach a consistent   state.  For this reason, unlike
the configuration constants k, Imin,   and Imax, consistency definitions
should be clearly stated in the   protocol and should not be configured at
runtime. 
JP> I would suggest a MUST instead of a should in the sentence above.
6.5.  Specifying the constant k
 
   Disabling suppression means that every node will always send on every
 
JP> I would suggest to add refs here.
   Nevertheless, there are situations where a protocol may wish to turn
   off Trickle suppression.  Because k is a natural number
   (Section 4.1), c=0 has no useful meaning.  If a protocol allows k to
   be dynamically configured, a value of 0 remains unused.  For ease of
   debugging and packet inspection, having the parameter describe (c-1)
JP> c-1 ?
   can be counter-productive.  Instead, it is RECOMMENDED that protocols
which require turning off suppression reserve c=0 to mean c=infinity. 6.6.
Relationship between k and Imin    Finally, a protocol SHOULD set k and Imin
such that Imin is at least   two to three as long as it takes to transmit k
packets.  Otherwise,   if more than k nodes reset their intervals to Imin,
the resulting Levis, et al.            Expires January 7, 2011
[Page 8] 

 Internet-Draft         draft-ietf-roll-trickle-02              July 2010
communication will lead to congestion and significant packet loss.
Experimental results have shown that packet losses from congestion   reduce
Trickle's efficiency [Levis04].
JP> Well ... it is true in most networks, but may not be completely
applicable to
non wireless networks though. You may want to mention it.
 6.7.  Tweaks and improvements to Trickle    Trickle is based on a small
number of simple, tightly integrated   mechanisms that are highly robust to
challenging network   environments.  

7.  Acknowledgements
 
JP> to be done
 8.  IANA Considerations    This document has no IANA considerations. 9.
Security Considerations    This document has no security considerations. 10.
References 10.1.  Normative References    [RFC2119]  Bradner, S., "Key words
for use in RFCs to Indicate              Requirement Levels", BCP 14, RFC
2119, March 1997. Levis, et al.            Expires January 7, 2011
[Page 9] 

 Internet-Draft         draft-ietf-roll-trickle-02              July 2010
10.2.  Informative References    [Levis04]  Levis, P., Patel, N., Culler,
D., and S. Shenker,              "Trickle: A Self-Regulating Algorithm for
Code Propagation              and Maintenance in Wireless Sensor Networks"",
Proceedings              of the First USENIX/ACM Symposium on Networked
Systems              Design and Implementation NSDI 2004, March 2004,
<http://portal.acm.org/citation.cfm?id=1251177>.    [Levis08]  Levis, P.,
Brewer, E., Culler, D., Gay, D., Madden, S.,              Patel, N.,
Polastre, J., Shenker, S., Szewczyk, R., and A.              Woo, "The
Emergence of a Networking Primitive in Wireless              Sensor
Networks", Communications of the ACM, v.51 n.7,              July 2008,
<http://portal.acm.org/citation.cfm?id=1364804>. Authors' Addresses
Philip Levis   Stanford University   358 Gates Hall, Stanford University
Stanford, CA  94305   USA    Phone: +1 650 725 9064   Email:
[email-masked]    Thomas Heide Clausen   LIX, Ecole Polytechnique
Phone: +33 6 6058 9349   Email: [email-masked]    Jonathan Hui
Arch Rock Corporation   501 Snd St., Suite 410   San Francisco, CA  94107
USA    Email: [email-masked] Levis, et al.            Expires January 7,
2011               [Page 10] 

 Internet-Draft         draft-ietf-roll-trickle-02              July 2010
Omprakash Gnawali   Stanford University   S255 Clark Center, 318 Campus
Drive   Stanford, CA  94305   USA    Phone: +1 650 725 6086   Email:
[email-masked]    JeongGil Ko   Johns Hopkins University   3400 N.
Charles St., 224 New Engineering Building   Baltimore, MD  21218   USA
Phone: +1 410 516 4312   Email: [email-masked] Levis, et al.
Expires January 7, 2011               [Page 11] 

Thanks.

JP.

Dear WG,

This starts a 2-week Working Group last call ending on August 11 at 9:00am
ET.

Thanks.

JP.

---

From: Philip Levis <[email-masked]>
Date: Wed, 4 Aug 2010 19:20:30 -0700

Comments inline.

>> JP> how could that happen that I <  Imin?

It can't, but it can be equal to Imin. The inequality is to prevent starvation if a node keeps on resetting its interval.

>> JP> s/Default values/Value

Why this change?

>> apply to several kind of mismatches

I'm not sure I want to go as far as recommending consistent configuration. E.g., if I have some nodes with more energy, they might be willing to shoulder a greater energy burden and so have a smaller Imax.

>>  6.2.  Mismatched Imin    If nodes do not agree on Imin, then some nodes, on hearing   inconsistent messages, will transmit sooner than others.  These   faster nodes will have their intervals grow to similar size as the   slower nodes within a single slow interval time, but in that period   may suppress the slower nodes.  However, such suppression will end   after the first slow interval, when the nodes generally agree on the   interval size.  Hence, mismatched Imin values are usually not a Levis, et al.            Expires January 7, 2011                [Page 7]  Internet-Draft         draft-ietf-roll-trickle-02              July 2010    significant concern. 6.3.  Mismatched Imax    If nodes do not agree on Imax, then this can cause long-term problems   with transmission load.  Nodes with small Imax values will transmit   faster, suppressing those with larger Imax values.  The nodes with   larger Imax values, always suppressed, will never transmit.  In the   base case, when the network is consistent, this can cause long-term   inequities in energy cost. 6.4.  Mismatched definitions    If nodes do not agree on what constitutes a consistent or   inconsistent transmission, then Trickle may fail to operate properly.   For example, if a receiver thinks a transmission is consistent, but   the transmitter (if in the receivers situation) would have thought it   inconsistent, then the receiver will not respond properly and inform   the transmitter.  This can lead the network to not reach a consistent   state.  For this reason, unlike the configuration constants k, Imin,   and Imax, consistency definitions should be clearly stated in the   protocol and should not be configured at runtime. 

I'm wary of saying MUST; it would mean that an implementation is not compliant with this document even if, for good reason, it has different consistency definitions.

>>    approach is especially dangerous 

OK -- I will give an explanation.

>>    debugging and packet inspection, having the parameter describe (c-1)

Disagree -- it's easier for debugging when the value equals the value. There's later text about k=0 and using it to represent k=inf.

Phil

---

From: Philip Levis <[email-masked]>
Date: Thu, 5 Aug 2010 11:04:17 -0700

On Aug 4, 2010, at 7:20 PM, Philip Levis wrote:

> This can lead the network to not reach a consistent   state.  For this reason, unlike the configuration constants k, Imin,   and Imax, consistency definitions should be clearly stated in the   protocol and should not be configured at runtime. 

Sorry, I miswrote. I agree that the sentence should say MUST, and SHOULD NOT. So,

> For this reason, unlike the configuration constants k, Imin,   and Imax, consistency definitions MUST be clearly stated in the   protocol and SHOULD NOT be configured at runtime. 

Sound good? Although the MUST is redundant with prior text...

Phil

---

From: Philip Levis <[email-masked]>
Date: Tue, 10 Aug 2010 11:46:00 -0700

>>        random point in the interval, taken from the range [I/2, I).

Just as a note -- this is an example of why there's the strong language about not tweaking Trickle. If you use [I/2, I] rather than [I/2, I), then there's an ambiguity when intervals are synchronized: a packet transmitted in interval X can suppress in interval X+1. This could prevent Trickle from maintaining its minimum communication rate, as an entire interval could pass with no transmissions.

Phil

---

From: JP Vasseur <[email-masked]>
Date: Thu, 12 Aug 2010 21:19:05 +0200

Dear all,

WG Last Call on draft-ietf-roll-trickle-02 has now ended.
Authors, please address the comments raised during the WG Last Call  
and submit a new revision, before publication request.

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Thu, 12 Aug 2010 21:26:34 +0200

Dear all,

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 16 Aug 2010 11:20:44 +0200

Hi Phil,

Look for JP> (I suppose that you incorporated other comments and only  
focussed on the ones that require further discussion).

On Aug 5, 2010, at 4:20 AM, Philip Levis wrote:

> It can't, but it can be equal to Imin. The inequality is to prevent  
> starvation if a node keeps on resetting its interval.

JP> Understood, but the sentence is a bit misleading. Why not:
>        Trickle timer resets.  Resetting a
>        Trickle timer sets I to Imin and begins a new interval.  When  
> I is
>        may also reset the timer in response to external "events.

>>> [Page 6]
JP>
Please ignore ...

> I'm not sure I want to go as far as recommending consistent  
> configuration. E.g., if I have some nodes with more energy, they  
> might be willing to shoulder a greater energy burden and so have a  
> smaller Imax.
>

JP>This is fine. At least the text explains the drawbacks of using  
inconsistent values.

>>> nodes, on hearing   inconsistent messages, will transmit sooner  
>>> than others.  These   faster nodes will have their intervals grow  
>>> to similar size as the   slower nodes within a single slow  
>>> interval time, but in that period   may suppress the slower  
>>> nodes.  However, such suppression will end   after the first slow  
>>> interval, when the nodes generally agree on the   interval size.   
>>> Hence, mismatched Imin values are usually not a Levis, et  
>>> al.            Expires January 7, 2011                [Page 7]  Int 
>>> ernet-Draft         draft-ietf-roll-trickle-02              July  
>>> 2010    significant concern. 6.3.  Mismatched Imax    If nodes do  
>>> not agree on Imax, then this can cause long-term problems   with  
>>> transmission load.  Nodes with small Imax values will transmit    
>>> faster, suppressing those with larger Imax values.  The nodes  
>>> with   larger Imax values, always suppressed, will never  
>>> transmit.  In the   base case, when the network is consistent,  
>>> this can cause long-term   inequities in energy cost. 6.4.   
>>> Mismatched definitions    If nodes do not agree on what  
>>> constitutes a consistent or   inconsistent transmission, then  
>>> Trickle may fail to operate properly.   For example, if a receiver  
>>> thinks a transmission is consistent, but   the transmitter (if in  
>>> the receivers situation) would have thought it   inconsistent,  
>>> then the receiver will not respond properly and inform   the  
>>> transmitter.  This can lead the network to not reach a  
> I'm wary of saying MUST; it would mean that an implementation is not  
> compliant with this document even if, for good reason, it has  
> different consistency definitions.

JP>OK so let's at least make it a normative SHOULD.

> OK -- I will give an explanation.

JP>OK

> Disagree -- it's easier for debugging when the value equals the  
> value. There's later text about k=0 and using it to represent k=inf.

JP>I do not see which comment you disagree on ?

JP.

---

From: JP Vasseur <[email-masked]>
Date: Mon, 16 Aug 2010 11:22:35 +0200

On Aug 10, 2010, at 8:46 PM, Philip Levis wrote:

> Just as a note -- this is an example of why there's the strong  
> language about not tweaking Trickle. If you use [I/2, I] rather than  
> [I/2, I), then there's an ambiguity when intervals are synchronized:  
> a packet transmitted in interval X can suppress in interval X+1.  
> This could prevent Trickle from maintaining its minimum  
> communication rate, as an entire interval could pass with no  
> transmissions.

For the WG, the misunderstanding was coming from the the use of  
different notation. In some countries we use [a,b[ instead:

But that's OK let's use the [a,b) notation.

For the record:

(http://en.wikipedia.org/wiki/Interval_(mathematics)):
The ISO notation
International standard ISO 31-11 also defines another notation for  
intervals, which seems to be more commonly taught in Europe[citation  
needed] and South America. It uses an inwards pointing bracket to  
indicate inclusion of the endpoint, and outwards-pointing bracket for  
exclusion:

Both notations may overlap with other uses of parentheses and brackets  
in mathematics. For instance, the notation (a,b) is often used to  
denote an ordered pair in set theory, the coordinates of a point or  
vector in analytic geometry and linear algebra, or (sometimes) a  
complex number in algebra. The notation [a,b] too is occasionally used  
for ordered pairs, especially in computer science.
Some authors use ]a,b[ to denote the complement of the interval (a,b);  
namely, the set of all real numbers that are either less than or equal  
to a, or greater than or equal to b.
In countries where numbers are written with a decimal comma, a  
semicolon may be used as a separator, to avoid ambiguity.

Cheers.

JP.

---

From: Philip Levis <[email-masked]>
Date: Mon, 16 Aug 2010 09:02:47 -0700

> JP>I do not see which comment you disagree on ?

Having the parameter describe c-1. I think it's easier if you have the parameter describe c, and define c=0 as a special case.

Phil

---

From: JP Vasseur <[email-masked]>
Date: Tue, 17 Aug 2010 10:01:28 +0200

On Aug 16, 2010, at 6:02 PM, Philip Levis wrote:

> Having the parameter describe c-1. I think it's easier if you have  
> the parameter describe c, and define c=0 as a special case.

What I am suggesting is to clarify the sentence ... (hard to  
parse) ... why "counter-productive" ?
Just a question of wording, we agree on the content.

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Tue, 17 Aug 2010 10:04:56 +0200

On Aug 5, 2010, at 8:04 PM, Philip Levis wrote:

>> This can lead the network to not reach a consistent   state.  For  
>> this reason, unlike the configuration constants k, Imin,   and  
>> Imax, consistency definitions should be clearly stated in the    
>> I'm wary of saying MUST; it would mean that an implementation is  
>> not compliant with this document even if, for good reason, it has  
>> For this reason, unlike the configuration constants k, Imin,   and  
>> Imax, consistency definitions MUST be clearly stated in the    
>> protocol and SHOULD NOT be configured at runtime.
>

Yes, better, thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Tue, 17 Aug 2010 10:10:36 +0200

On Jul 29, 2010, at 11:49 AM, Philip Levis wrote:

> Yoav, my comments are inline.
> On Jul 29, 2010, at 8:58 AM, Yoav Ben-Yehezkel wrote:
>
>> Authors/ROLL WG,
>>
>> Find below some minor comments/clarifications I have on the Trickle  
>> draft.
>>
>> Suggest to replace the term “wireless” with “LLN” (trickle is  
>> potentially not used solely by wireless – though it was developed  
>> on a wireless platform I understand).
>>
>> It appears in the abstract, in the intro, at the last para of  
>> section 3., at section 6.7.
>> “Abstract
>>
>>   in a highly robust,...”
>> “1.  Introduction
>>   The Trickle algorithm is designed for wireless networks.”
>>
>> “3. Trickle Algorithm Overview
>>   … Sparser networks require more transmissions per node, but
>>   is an important property in wireless networks, where the channel  
>> is a
>>   valuable shared resource.”
>>
>> “6.7.  Tweaks and improvements to Trickle
>>   … However, in dynamic network environments such as wireless,
>>   the coordination needed to compute the…
>
> This is a good point. What this text is trying to get at is that  
> Trickle is designed for, and well-suited to, lossy broadcast media.  
> We've never really examined its use in low-loss switched networks  
> (e.g., Ethernet). When the algorithm was designed, lossy broadcast  
> media basically meant wireless, and not just low-power wireless.  
> E.g., Trickle is well suited to 802.11. We didn't really consider  
> PLC -- in the context of ROLL, however, it should definitely be  
> considered.
>
> Correspondingly, I don't think LLN is the right term either. How  
> about "lossy broadcast-based networks," with a few examples (e.g.,  
> wireless, PLC)?

I would much prefer LLN:
	* This is the term used across all documents in ROLL
	* PLC are also low power and lossy

>
>>
>>
>> Last paragraph of section 3 is a little unclear to me.
>> “  A single, disconnected node must transmit at the communication  
>> rate.”
>> Can you clarify this sentence? What do you mean by “must transmit  
>> at the communication rate”? The communication rate is the output of  
>> the number of transmissions a disconnected node makes, not the  
>> other way around.
>
> Ah -- I see. This sentence is referring to the prior paragraph,  
> which reads:
>
> "As long as the network is connected and there is some minimum  
> consistency."
> The point is that communication is either transmission or reception  
> and that the edge case of a solitary node, its communication will be  
> all transmissions. In networks of multiple nodes, a node's  
> communication can be some mix of receptions and transmissions.
>
> Would it make more sense if the text read "Trickle communication  
> rate" rather than "communication rate?"

I think so.

>
>
>
>>
>> “  In a lossless, single-hop network of size n, the sum of  
>> transmissions
>>   1/n.”
>> I think “the sum of transmissions” should be “the sum of  
>> transmission rates”, right? This property is true only if all nodes  
>> have the same arrival rates. Is this always the case, or just the  
>> case when using trickle? You probably mean that this is a long term  
>> average, not always, right?
>
> I don't understand -- the same arrival rates? It's a lossless,  
> single-hop network: when a node transmits, every other node hears  
> the transmission. So the communication (reception+transmission)  
> rates across the network are uniform.
>
>
>>
>>   Sparser networks require more transmissions per node, but
>>   is an important property in wireless networks, where the channel  
>> is a
>>   dense networks conserves system energy.”
>> I think the word Trickle is missing in the above to emphasize the  
>> fact that what you describe is true for the trickle mechanism, not  
>> in a network consisting of both trickle control data together with  
>> application data.
>
> Which sentence do you think is unclear? Is it that application data  
> does not necessarily follow this property of scaling? I'd like to  
> think there is some context, and that it doesn't have to be that  
> every sentence says Trickle in it.
>
>
>>
>>
>> I have some questions/clarifications for section 4.2:
>> Generally, what I think required is a more precise description of  
>> the term “interval”.
>> When does an interval start? When did the previous ended? After the  
>> previous I expires or when t is reached (and transmission or  
>> suppression of transmission is decided on)? It is not so clear in  
>> the text. If it is  when I expires, then after the transmission a  
>> node must wait from the randomized time t till I expires and then  
>> re-randomize the next t, and that leads to the question of what  
>> happens with all the (in)consistencies it hears till the next  
>> interval starts? Should they be counted as well (in step 2 it says  
>> to count all consistencies and in step 1 it says to set c to 0,  
>> i.e. disregard counts from t till I expires)? Some clarification  
>> would be helpful.
>
> From -02:
>
> I'm not sure how this can be more precise... would changing the text  
> to
>
>       random point in the interval, taken from the range [I/2, I). The
>       interval ends at I.
>
> be helpful?
>
>>
>> One comment on operational considerations (section 6):
>> Do you see value in describing some typical “events” that can be  
>> used to reset the timer? What are the guidelines/limitations for  
>> doing these resets, what could be considered good events and what  
>> could be considered bad events?
>>
>
> I'm really a bit wary of doing this -- almost any recommendations we  
> could come up with would be wrong in some cases. E.g., the  
> recommendations for multicast are very different than protocol  
> acknowledgment timing. Perhaps the document can point to references  
> of a few examples of its use, from which a reader might benefit?
>
> Phil
>
>

---

From: JP Vasseur <[email-masked]>
Date: Tue, 17 Aug 2010 10:14:00 +0200

On Jul 29, 2010, at 12:47 PM, Yoav Ben-Yehezkel wrote:

> Thanks Phil,
>
> I think now I understand better some of the points. With these  
> understandings, I’d like to bring up some more the topics for  
> further discussion. I’m OK with all your explanations excluding the  
> ones that are in the below list.
>
> ----
> potentially not used solely by wireless – though it was developed on  
> a wireless platform I understand).
> …
> Phil: "Correspondingly, I don't think LLN is the right term either.  
> How about "lossy broadcast-based networks," with a few examples  
> (e.g., wireless, PLC)?"
>
> Yoav: I definitely support the examples.
> I'm not familiar with the term "lossy broadcast-based networks", is  
> this a commonly used term?

Nope

> To me, something like "lossy and partially connected networks" would  
> make more sense. But if people understand what that means, I  
> wouldn't object.
> ----
> …
> Phil: Would it make more sense if the text read "Trickle  
> communication rate" rather than "communication rate?"
>
> Yoav: It would make sense to explain some terminology.

This is a good suggestion since the question was asked for several  
terms: Phil, would you mind adding a short terminology section ?

> For example, communication rate, maybe also: (in)consistency, event,  
> maybe also “lossy broadcast-based networks” that you spoke of  
> earlier. Specifically, to me the term “communication rate” was not  
> self-explanatory and I would appreciate it if you described it  
> somewhere.
>
> Yoav: Something like: ”communication rate – the communication rate  
> of a node is the sum of transmission and reception rates of this  
> node.”
> Yoav: maybe also: “Trickle communication rate – the trickle  
> communication rate equals the communication rate of trickle messages  
> only.”
>
> With this understanding in mind, I still think that the sentence:
> Yoav: Is somewhat misleading, and mixes the outcome with the given  
> scenario.
>
> Yoav: Would you consider a re-write in the form of:
> Yoav: "In the case of a single, disconnected node, the communication  
> rate is equal to the transmission rate."
>
> Yoav: Is this what you were trying to say?
> ----
> >
> …
> Yoav: How does one sum up transmissions? It is not a numeric value.  
> One can count them, or sum their rates.
>
> Yoav: I agree that the transmission rates will be uniformly  
> distributed when using the trickle and the same communication rates  
> will be the sum of the transmission rates.
>
> Yoav: Trying to follow this logic, I would like to propose the  
> following re-write here:
> Yoav: " In a lossless, single-hop network of size n, the sum of  
> transmission rates of trickle messages (summed over all nodes)  
> equals the trickle communication rate of each node separately. The  
> trickle mechanism balances the load in such a scenario, such that  
> for each node, the transmission rate of trickle messages is 1/n  
> times the trickle communication rate."
>
> Yoav: Is the above correct? Does it clarify my point better?
> ----
> …
> Phil: I'm not sure how this can be more precise... would changing  
> the text to
>
> Phil:   1.  When an interval begins, Trickle resets c to 0 and sets  
> t to a
> The
> Phil: be helpful?
> Yoav: Yes! So is my understanding that between t and I, there's no  
> meaning to counting consistencies correct? Would it promote this  
> understanding (not so much implementation or correctness) if you  
> change rule 2. to:
>
> Yoav: " 2.  Whenever Trickle hears a transmission that is  
> "consistent," it
>        increments counter c." to:
>
> Yoav: " 2. Whenever Trickle hears a transmission that is  
> "consistent," until t expires, it
>        increments counter c."
> ----
> …
> Phil: Perhaps the document can point to references of a few examples  
> of its use, from which a reader might benefit?
>
> Yoav: that would be good enough for me.
> ----
>
> Thanks for the productive response.
>
> Best Regards,
> Yoav
>
>
> -----Original Message-----
> From: Philip Levis [mailto:[email-masked]]
> Sent: Thursday, July 29, 2010 12:50 PM
> To: Yoav Ben-Yehezkel
> Cc: [email-masked]; [email-masked];  
> [email-masked];[email-masked]; [email-masked]
> > Find below some minor comments/clarifications I have on the  
> Trickle draft.
> >
> potentially not used solely by wireless – though it was developed on  
> a wireless platform I understand).
> >
> >    is an important property in wireless networks, where the  
> channel is a
> the number of transmissions a disconnected node makes, not the other  
> way around.
>
> >    is an important property in wireless networks, where the  
> channel is a
> > When does an interval start? When did the previous ended? After  
> the previous I expires or when t is reached (and transmission or  
> node must wait from the randomized time t till I expires and then re- 
> randomize the next t, and that leads to the question of what happens  
> with all the (in)consistencies it hears till the next interval  
> starts? Should they be counted as well (in step 2 it says to count  
> all consistencies and in step 1 it says to set c to 0, i.e.  
> disregard counts from t till I expires)? Some clarification would be  
> helpful.
>
> From -02:
>
> The

---

From: Philip Levis <[email-masked]>
Date: Tue, 17 Aug 2010 11:00:01 -0700

On Aug 16, 2010, at 2:22 AM, JP Vasseur wrote:

> 
> On Aug 10,
> For the WG, the misunderstanding was coming from the the use of different notation. In some countries we use [a,b[ instead:
> 
> International standard ISO 31-11 also defines another notation for intervals, which seems to be more commonly taught in Europe[citation needed] and South America. It uses an inwards pointing bracket to indicate inclusion of the endpoint, and outwards-pointing bracket for exclusion:
> Both notations may overlap with other uses of parentheses and brackets in mathematics. For instance, the notation (a,b) is often used to denote an ordered pair in set theory, the coordinates of a point or vector in analytic geometry and linear algebra, or (sometimes) a complex number in algebra. The notation [a,b] too is occasionally used for ordered pairs, especially in computer science.
> Some authors use ]a,b[ to denote the complement of the interval (a,b); namely, the set of all real numbers that are either less than or equal to a, or greater than or equal to b.
> In countries where numbers are written with a decimal comma, a semicolon may be used as a separator, to avoid ambiguity.

Fascinating! Sorry for the confusion -- I had thought that at least mathematics was an international language. :) I will add a sentence of natural language to explain it.

Phil

---

From: Philip Levis <[email-masked]>
Date: Tue, 17 Aug 2010 11:14:35 -0700

On Aug 17, 2010, at 1:01 AM, JP Vasseur wrote:

> What I am suggesting is to clarify the sentence ... (hard to parse) ... why "counter-productive" ?

How about "confusing" rather than "counter-productive?"

I.e.:

<t>Nevertheless, there are situations where a protocol may wish to
turn off Trickle suppression. Because k is a natural number (<xref
target="Parameters"/>), k=0 has no useful meaning. If a protocol
allows k to be dynamically configured, a value of 0 remains
unused. For ease of debugging and packet inspection, having the
parameter describe (k-1) can be confusing.  Instead, it is RECOMMENDED
that protocols which require turning off suppression reserve k=0 to
mean k=infinity.</t>

How does that sound?

Phil

---

From: Philip Levis <[email-masked]>
Date: Tue, 17 Aug 2010 11:36:44 -0700

On Aug 17, 2010, at 1:10 AM, JP Vasseur wrote:

>>> Find below some minor comments/clarifications I have on the Trickle draft.
>>> 
>>> Suggest to replace the term “wireless” with “LLN” (trickle is potentially not used solely by wireless – though it was developed on a wireless platform I understand).
>>> 
>>> It appears in the abstract, in the intro, at the last para of section 3., at section 6.7.
>>> “Abstract
>>> 
>>>  is an important property in wireless networks, where the channel is a
>> This is a good point. What this text is trying to get at is that Trickle is designed for, and well-suited to, lossy broadcast media. We've never really examined its use in low-loss switched networks (e.g., Ethernet). When the algorithm was designed, lossy broadcast media basically meant wireless, and not just low-power wireless. E.g., Trickle is well suited to 802.11. We didn't really consider PLC -- in the context of ROLL, however, it should definitely be considered.
>> 
>> Correspondingly, I don't think LLN is the right term either. How about "lossy broadcast-based networks," with a few examples (e.g., wireless, PLC)?
> 
> I would much prefer LLN:

I currently have the text as:

   The Trickle algorithm allows nodes in a lossy shared medium to
   exchange information in a highly robust, energy efficient, simple,
   and scalable manner.

How about:

   The Trickle algorithm allows nodes in a lossy shared medium (e.g., low power
   and lossy networks) to exchange information in a highly robust, energy efficient, simple,
   and scalable manner.

I'd say "LLNs" but don't want to put a reference in the abstract.

Phil

---

From: JP Vasseur <[email-masked]>
Date: Wed, 18 Aug 2010 00:20:12 +0200

Great, thanks.

JP.

On Aug 17, 2010, at 8:00 PM, Philip Levis wrote:

>> intervals, which seems to be more commonly taught in  
>> Europe[citation needed] and South America. It uses an inwards  
>> pointing bracket to indicate inclusion of the endpoint, and  
>> outwards-pointing bracket for exclusion:
>> Both notations may overlap with other uses of parentheses and  
>> brackets in mathematics. For instance, the notation (a,b) is often  
>> used to denote an ordered pair in set theory, the coordinates of a  
>> point or vector in analytic geometry and linear algebra, or  
>> (sometimes) a complex number in algebra. The notation [a,b] too is  
>> occasionally used for ordered pairs, especially in computer science.
>> Some authors use ]a,b[ to denote the complement of the interval  
>> (a,b); namely, the set of all real numbers that are either less  
>> than or equal to a, or greater than or equal to b.
> Fascinating! Sorry for the confusion -- I had thought that at least  
> mathematics was an international language. :) I will add a sentence  
> of natural language to explain it.
>
> Phil

---

From: JP Vasseur <[email-masked]>
Date: Wed, 18 Aug 2010 00:21:04 +0200

> that protocols which require turning off suppression reserve k=0 to

Crystal clear.

Thanks.

JP.

---

From: JP Vasseur <[email-masked]>
Date: Wed, 18 Aug 2010 00:22:09 +0200

That works.

JP.

On Aug 17, 2010, at 8:36 PM, Philip Levis wrote:

>>> Trickle is designed for, and well-suited to, lossy broadcast  
>>> media. We've never really examined its use in low-loss switched  
>>> networks (e.g., Ethernet). When the algorithm was designed, lossy  
>>> broadcast media basically meant wireless, and not just low-power  
>>> wireless. E.g., Trickle is well suited to 802.11. We didn't really  
>>> consider PLC -- in the context of ROLL, however, it should  
>>> definitely be considered.
>>>

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Aug 2010 12:09:53 +0200

Thanks Phil for the changes agreed on the mailing and incorporated in  
Trickle -03.

There just a few things still to update before I can send the  
publication request the IESG:
1) Can you add a terminology section (define Trickle communication  
rate, ...) => See Yoav/JP comments on the list
2) When listing a reference, add parenthesis.

Example

OLD: include RPL[I-D.ietf-roll-rpl]

NEW: include RPL ([I-D.ietf-roll-rpl])

3) Several comments below have not been incorporated (see JP>)

Begin forwarded message:

> Date: August 3, 2010 3:36:04 PM CEDT
> To: ROLL WG <[email-masked]>

JP> Comment above
>> JP> s/trickle/the trickle algorithm
JP> Comment above
>> [Page 1]
>> [Page 2]
>> [Page 3]

JP> Comment above (need to define the term "agree")
>> JP> Please define "inconsistency" (an example should suffice)

JP> The first you use the term "inconsistency" can you point to  
Section 6.8

>> JP> See comments on "hour"
JP> Same here

    This primitive allows Trickle to scale to thousand-fold variations  
in
    network density, quickly propagate updates, distribute transmission
    load evenly, be robust to transient disconnections, handle network
    repopulations, and impose a very low maintenance overhead: common
    uses require on the order of a few packets per hour yet can respond
    in milliseconds.
Avoid using a unit value (hour) unless it is clear that this is given  
as an example.
4) Checking references for intended status: Proposed Standard
    
----------------------------------------------------------------------------

      (See RFCs 3967 and 4897 for information about using normative  
references
      to lower-maturity documents in RFCs)

   == Outdated reference: A later version (-11) exists of
      draft-ietf-roll-rpl-10
Thanks.

JP.

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 19 Aug 2010 13:19:50 +0300

Also, see typo at bottom of page 4 – blaances should be balances

Thanks,

Yoav

*From:* [email-masked] [mailto:[email-masked]] *On Behalf Of *JP
Vasseur
*Sent:* Thursday, August 19, 2010 1:10 PM
*To:* Philip Levis
*Cc:* ROLL WG
*Subject:* [Roll] Fwd: Fwd: WG Last Call on draft-ietf-roll-trickle-02

There just a few things still to update before I can send the publication
request the IESG:

1) Can you add a terminology section (define Trickle communication rate,
...) => See Yoav/JP comments on the list

Example

Begin forwarded message:

  *From: *JP Vasseur <[email-masked]>

*Date: *August 3, 2010 3:36:04 PM CEDT

*To: *ROLL WG <[email-masked]>

*Subject: **[Roll] Fwd:  WG Last Call on draft-ietf-roll-trickle-02*

Begin forwarded message:

  *From: *JP Vasseur <[email-masked]>

*Date: *August 3, 2010 3:35:41 PM CEDT

*To: *JP Vasseur <[email-masked]>

*Cc: *ROLL WG <[email-masked]>

*Subject: **Re: [Roll] WG Last Call on draft-ietf-roll-trickle-02*

Please find below comments on draft-ietf-roll-trickle-02 (search for *JP>*).

end of LC.

                                                                  J. Hui

                                                   Arch Rock Corporation

                                                              O. Gnawali

                                                     Stanford University

                                                                   J. Ko

                                                Johns Hopkins University

                                                            July 6, 2010

                         The Trickle Algorithm

Abstract

JP> Comment above

   JP> Comment above

   and

Status of this Memo

   Drafts.

Copyright Notice

Table of Contents

1.  Introduction

JP> please use the LLN terminology and point to [I-D-ietf.roll-terminology] ID.

It

JP> The first you use the term "inconsistency" can you point to Section 6.8

   a few packets per hour.

   JP> Same here

   This primitive allows Trickle to scale to thousand-fold variations in

   in milliseconds.

     (See RFCs 3967 and 4897 for information about using normative references

     draft-ietf-roll-rpl-10

 Thanks.

JP.

---

From: Philip Levis <[email-masked]>
Date: Thu, 19 Aug 2010 12:04:10 -0700

On Aug 19, 2010, at 3:09 AM, JP Vasseur wrote:

> Thanks Phil for the changes agreed on the mailing and incorporated in Trickle -03.
> 
> There just a few things still to update before I can send the publication request the IESG:
> 1) Can you add a terminology section (define Trickle communication rate, ...) => See Yoav/JP comments on the list

OK

> NEW: include RPL ([I-D.ietf-roll-rpl])

Is this the standard RFC style? I see RFCs where this isn't done. Just typing 3 random recent numbers, none of them use this style:

http://tools.ietf.org/rfc/rfc4311.txt

   In the conceptual sending algorithm in [ND] and in the optional
   extension in [ROUTERSEL]

http://tools.ietf.org/rfc/rfc4759.txt

   The following syntax specification uses the Augmented Backus-Naur
   Form (ABNF) as described in RFC 4234 [2] to extend the syntax of the
   "par" production defined in the ABNF of RFC 3966 [5].

http://tools.ietf.org/rfc/rfc5050.txt

   Additional bundle protocol blocks of other types may follow the
   primary block to support extensions to the bundle protocol, such as
   the Bundle Security Protocol [BSP].

The reason I ask is that I'm used to [] indicating a citation; you'd put the citation in parentheses only the act of citation was, well, parenthetical.

>>> that all depends on the parameter settings)

Is this a comment, or a required edit? I say that because I think some kind of mention of scale is useful here. The actual technical section states things more generally, but if you have a strong concrete statement, better to say it. A general statement, for example, might be interpreted as seconds/minutes.

>>> JP> s/trickle/the trickle algorithm

OK.

>>>    (
>>> http://trustee.ietf.org/license-info
>>> ) in effect on the date of

This is a simple conceptual description (the introduction): later text that actually presents the algorithm gives the technical definition.

> JP> The first you use the term "inconsistency" can you point to Section 6.8

Would it be more helpful to put this reference at the end of the second paragraph? That's where it makes the point about what an inconsistency is.

> 
> Avoid using a unit value (hour) unless it is clear that this is given as an example.

OK, I will cite CTP.

> 4) Checking references for intended status: Proposed Standard

Roger.

Phil