[Roll] Fwd: Revisiting the Trickle Algorithm

Omprakash Gnawali <gnawali@cs.uh.edu> Mon, 02 February 2015 16:37 UTC

Return-Path: <gnawali@cs.uh.edu>
X-Original-To: roll@ietfa.amsl.com
Delivered-To: roll@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6B6AE1A870E for <roll@ietfa.amsl.com>; Mon, 2 Feb 2015 08:37:51 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.588
X-Spam-Level:
X-Spam-Status: No, score=-3.588 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_MED=-2.3, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xpyefq3kn9of for <roll@ietfa.amsl.com>; Mon, 2 Feb 2015 08:37:44 -0800 (PST)
Received: from dijkstra.cs.uh.edu (dijkstra.cs.uh.edu [129.7.240.12]) by ietfa.amsl.com (Postfix) with ESMTP id EBB741A802E for <roll@ietf.org>; Mon, 2 Feb 2015 08:37:30 -0800 (PST)
Received: from localhost (dijkstra.cs.uh.edu [127.0.0.1]) by dijkstra.cs.uh.edu (Postfix) with ESMTP id A4A1123CA79 for <roll@ietf.org>; Mon, 2 Feb 2015 10:37:30 -0600 (CST)
X-Virus-Scanned: amavisd-new at cs.uh.edu
Received: from dijkstra.cs.uh.edu ([127.0.0.1]) by localhost (dijkstra.cs.uh.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id oXB2SoV7QRs6 for <roll@ietf.org>; Mon, 2 Feb 2015 10:37:27 -0600 (CST)
Received: from it.cs.uh.edu (unknown [129.7.240.6]) by dijkstra.cs.uh.edu (Postfix) with ESMTP id 794AE23CA77 for <roll@ietf.org>; Mon, 2 Feb 2015 10:37:27 -0600 (CST)
Received: from mail-pa0-f41.google.com (mail-pa0-f41.google.com [209.85.220.41]) by it.cs.uh.edu (Postfix) with ESMTP id 66EDA2A280BD for <roll@ietf.org>; Mon, 2 Feb 2015 10:48:01 -0600 (CST)
Received: by mail-pa0-f41.google.com with SMTP id kq14so84362462pab.0 for <roll@ietf.org>; Mon, 02 Feb 2015 08:37:26 -0800 (PST)
X-Received: by 10.66.234.2 with SMTP id ua2mr31644504pac.4.1422895046788; Mon, 02 Feb 2015 08:37:26 -0800 (PST)
MIME-Version: 1.0
Received: by 10.70.49.73 with HTTP; Mon, 2 Feb 2015 08:37:06 -0800 (PST)
In-Reply-To: <CAErDfURsY8EhGnvN8SLcpDb9MK6c7mM0h+XwfP0xquR3nVXFpg@mail.gmail.com>
References: <CAPm4LDTj3-ZTZGi86ttgqNuTSRnEBUY59rAnxmr_DMvuhNWGGA@mail.gmail.com> <CAErDfUSewgX8i-qrZUTAv6S-7XQ5Vu2O5Z1qj0pUT=akwg3MiA@mail.gmail.com> <CAPm4LDRY4dUYgshFN96eJbOT4Fv18N9yOQBXeO23akRmdQ_KVg@mail.gmail.com> <CAErDfURsY8EhGnvN8SLcpDb9MK6c7mM0h+XwfP0xquR3nVXFpg@mail.gmail.com>
From: Omprakash Gnawali <gnawali@cs.uh.edu>
Date: Mon, 2 Feb 2015 10:37:06 -0600
Message-ID: <CAErDfUT+3tVujTNTP5djeaE1OeT5sD18Pe1uJRUAPxQuwD9wcg@mail.gmail.com>
To: ROLL WG <roll@ietf.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/roll/IgrmHT5CbzhV6ORrCwvYTNzPw04>
Subject: [Roll] Fwd: Revisiting the Trickle Algorithm
X-BeenThere: roll@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: Routing Over Low power and Lossy networks <roll@ietf.org>
List-Id: Routing Over Low power and Lossy networks <roll.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/roll>, <mailto:roll-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/roll/>
List-Post: <mailto:roll@ietf.org>
List-Help: <mailto:roll-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/roll>, <mailto:roll-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 02 Feb 2015 16:37:52 -0000

---------- Forwarded message ----------
From: Omprakash Gnawali <gnawali@cs.uh.edu>
Date: Mon, Feb 2, 2015 at 10:12 AM
Subject: Re: Revisiting the Trickle Algorithm
To: Badis Djamaa <badis.djamaa@gmail.com>
Cc: badis DJAMAA <badis.djamaa@ieee.org>rg>, ROLL WG <roll@ietf.org>rg>,
"Thomas Heide Clausen (work)" <T.Clausen@computer.org>rg>, Philip Levis
<pal@cs.stanford.edu>du>, JeongGil Ko <jgko@cs.jhu.edu>du>, JeongGil Ko
<jeonggil.ko@gmail.com>om>, Jonathan Hui <jonhui@cisco.com>om>, Ines Robles
<maria.ines.robles@ericsson.com>om>, Michael Richardson
<mcr+ietf@sandelman.ca>


On Mon, Jan 19, 2015 at 5:35 PM, Badis Djamaa <badis.djamaa@gmail.com> wrote:
> Thank you Gnawali for your comments,
>
>
>
>>Could you discuss the tradeoffs due to the proposed modification? Are
>>there some scenarios that will be worse off due to the changes?
>
>
>
> Figure1, page 2 of the document, shows the scheme in its best-case (lossless
> networks). From that Figure, we can see a side-effect of the proposed scheme
> which can add an extra cost in lossy-networks.
>
>
>
> Figure 4 in page 4, clearly shows this side-effect in lossy networks. But
> results in Figure 5 ( network with 90% physical loss rate) shows that the
> extra cost only affects a few following intervals and disappears later. Also
> Figure 5 shows that this additional cost does not affect trickle
> scalability.
>
>
>
> When generating heavy inconsistencies (periodically injecting new packets),
> testbed results depicted in third row of graphs in Figure 6, page 4, shows a
> bigger additional cost because of heavy inconsistent traffic being
> generated.
>
>
>
>>Did you consider minor variations to your scheme - e.g., rather than
>>just the first interval starting at 0, how about the first n intervals
>>starting at 0 rather than I/2?
>
>
>
> Because of the side-effect depicted in Figure 4, the additional cost
> increases if we go for n intervals. Generally speaking, Trickle's
> scalability might remain logarithmic, because the extra cost only depends on
> losses. However, the extra cost is noticeable under heavy inconsistent
> traffic and wastes energy.
>
>
>
> Note however, that we made a small variation to the scheme by letting a node
> that transmitted in an Imin interval to start listening immediately (put
> c=0). Preliminary results look promising and show that the side-effect can
> be addressed.
>
>
>
> More results are being analysed to see whether other side-effects can
> emerge.


Look forward to this. Could you also post your code so others can do
experiments on different testbeds to verify the results once you have
converged on a design that addresses the side effects. For example, I
can try to have a student do this as a short project in TinyOS.

If the side effects remain, this will be a question of tradeoff in
which case it is better to have this as a commentary in the RFC rather
than replace it.

It will also be helpful to do a survey of what type of intervals are
being used by the community so we know how big a problem this is.

- om_p