Re: [Roll] multicast & MLD on LLN

"Pascal Thubert (pthubert)" <pthubert@cisco.com> Thu, 16 October 2014 12:54 UTC

Return-Path: <pthubert@cisco.com>
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 030091A1A2F for <roll@ietfa.amsl.com>; Thu, 16 Oct 2014 05:54:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.511
X-Spam-Level:
X-Spam-Status: No, score=-14.511 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01, USER_IN_DEF_DKIM_WL=-7.5] 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 mcN2sBbYYDhO for <roll@ietfa.amsl.com>; Thu, 16 Oct 2014 05:54:35 -0700 (PDT)
Received: from rcdn-iport-7.cisco.com (rcdn-iport-7.cisco.com [173.37.86.78]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0C3A41A1A27 for <roll@ietf.org>; Thu, 16 Oct 2014 05:54:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=5084; q=dns/txt; s=iport; t=1413464067; x=1414673667; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=CdeK5M/YBfVdquu/cBEIV8Uzdg1rBg0Ehe4QmsQ4EcQ=; b=fiUp28uMr6rT2fwOjWtcNFkQ/eVmIFmJtHN3Y4PhEeIksZELojpqtwzx JDXB7GzbNUlnwyRO7QtVd3QI20Az7d9XBgR/CuI5fgqeR7BG5Ge0wNmNz 2iWkAZlm8mL3/pRbMeG/wZot4el8MY+fyZNvil9BPCTNoqe3UEkd/8uOi A=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgoFAEO/P1StJA2K/2dsb2JhbABbgw5TXIMCyRqHTQIbexYBfYQCAQEBBCMRRQwEAgEIDgMBAwEBAQICBh0DAgICMBQBAgYIAgQBDQUIiDYNtQmVIAEBAQEBAQEBAQEBAQEBAQEBAQEBAReBLI5THTEHBoJxNoEeBZF/hEaIfpQwgX4ggVlsgUiBAgEBAQ
X-IronPort-AV: E=Sophos;i="5.04,732,1406592000"; d="scan'208";a="363748399"
Received: from alln-core-5.cisco.com ([173.36.13.138]) by rcdn-iport-7.cisco.com with ESMTP; 16 Oct 2014 12:54:25 +0000
Received: from xhc-rcd-x05.cisco.com (xhc-rcd-x05.cisco.com [173.37.183.79]) by alln-core-5.cisco.com (8.14.5/8.14.5) with ESMTP id s9GCsPRd028240 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Thu, 16 Oct 2014 12:54:25 GMT
Received: from xmb-rcd-x01.cisco.com ([169.254.1.132]) by xhc-rcd-x05.cisco.com ([173.37.183.79]) with mapi id 14.03.0195.001; Thu, 16 Oct 2014 07:54:25 -0500
From: "Pascal Thubert (pthubert)" <pthubert@cisco.com>
To: Don Sturek <d.sturek@att.net>, "Turner, Randy" <Randy.Turner@landisgyr.com>, Kerry Lynn <kerlyn@ieee.org>
Thread-Topic: [Roll] multicast & MLD on LLN
Thread-Index: AQHP5RuvdYkdkHPd5kSqasUTvxD8SJwxu7kcgADwEZA=
Date: Thu, 16 Oct 2014 12:54:24 +0000
Deferred-Delivery: Thu, 16 Oct 2014 12:54:00 +0000
Message-ID: <E045AECD98228444A58C61C200AE1BD8489FAF18@xmb-rcd-x01.cisco.com>
References: <aef2e75903e84afe988ff58d04a0fc56@DB4PR01MB0431.eurprd01.prod.exchangelabs.com> <6B9D200B-58B8-423C-ADEA-A6C61F73748B@cisco.com> <AC402B16-8AD9-4033-A7F3-780725F9BAB8@tzi.org> <CABOxzu0-MLJ9esL55oxj_eQRpzXJrf6XErV+jd6UeZ2vuF0H5w@mail.gmail.com> <29960.1413410219@sandelman.ca>
In-Reply-To: <29960.1413410219@sandelman.ca>
Accept-Language: fr-FR, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.49.80.52]
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/roll/AvfiD3Ua5wFjcG-VbKM4-Uk34X8
Cc: "Greg Shepherd \(shep\)" <shep@cisco.com>, Routing Over Low power and Lossy networks <roll@ietf.org>, "IJsbrand Wijnands \(iwijnand\)" <ice@cisco.com>
Subject: Re: [Roll] multicast & MLD on LLN
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: Thu, 16 Oct 2014 12:54:37 -0000

Hello Michael

I think that saying that MPL is the default is quite exaggerated. 

RPL has a classical multicast built in, which is a simple extension to storing mode ( https://tools.ietf.org/html/rfc6550#section-12). 
The trouble is that this hardly fits with non-storing.

BIER (draft-wijnands-bier-architecture-00.txt) seems an appropriate approach for non-storing devices, considering that it makes the same tradeoff of bytes in packets vs. state in the nodes. BIER could be used for both unicast and multicast, unicast being seen as an extreme form of multicast. Each address, or group, or (source, group),  the node registers unicast to the root in pretty much the same way as we do today in non-storing. There is a bit offset associated to each node. When a packet comes in, the root looks up the list of interested nodes, sets a bit map at all the relevant bit offsets, and encapsulates the packet adding that bitmap, e.g. in an address or an option header. Each node maintains a bitmap per child down the RPL preferred tree, which has the bits set for the end nodes that are reachable via this child. These bitmaps could be built and re-advertised over classical storing-mode DAO messages whereby a node just advertises the AND of all its bitmaps to its preferred parent.

It would seem to be the right approach for Don's problem if it were not for the sheer size of " Around 5000 devices in the network total ".

BIER needs one bit per device in the routing bitmap. We cannot have a 5K bitmap in every packet. If we steal one bit in the ff1 (RFC 7371) to indicate a BIER routing, we could fit up to 112 hosts in a multicast IPv6 address.  To reach 5K, we'll need to subnet. For instance, by using 8 bits as a prefix, we could carve out 256 sets of 104 devices. For 5000 nodes, this means roughly 50 groups, and could multiply the state in every node by 50, though the numbers are probably a lot less if the sets are formed based on geography. But then, the root may have to send multiple copies of a packet, as many as there are groups with at least one listener for that packet.

Don: are these nodes all in a same DODAG? Or are they partitioned in smaller groups through multiple roots, or multiple instances?

Pascal


> -----Original Message-----
> From: Roll [mailto:roll-bounces@ietf.org] On Behalf Of Michael Richardson
> Sent: mercredi 15 octobre 2014 23:57
> To: Routing Over Low power and Lossy networks
> Cc: IJsbrand Wijnands (iwijnand)
> Subject: Re: [Roll] multicast & MLD on LLN
> 
> 
> Kerry Lynn <kerlyn@ieee.org> wrote:
>     > On Sat, Oct 11, 2014 at 2:39 AM, Carsten Bormann <cabo@tzi.org>
> wrote:
> 
>     >> Right, MLD is a host-router protocol.  Routers among them speak a
>     >> routing protocol, so they wouldn’t exchange MLD.  (A RPL “leaf” is a
>     >> router.)
>     >>
>     >> > Finally I'm looking at BIER see how their ideas could apply to LLNs…
>     >>
>     >> Yep.  We (TZI) have done (specified, implemented, analyzed) an
>     >> efficient BIER-like multicast forwarding protocol for non-storing mode
>     >> a while ago.
>     >>
> 
>     > I admit to some confusion here.  Is (topology-free) MPL no longer the
>     > default multicast forwarding protocol for LLN?
> 
> I don't know anything about BIER really... MPL is still the default at this
> point.
> (proceedural delays getting trickle-mcast out, not-with-standing) My take on
> the conversation is that BIER has some kind of helper node that unicasts
> everything out as appropriate.
> 
> --
> Michael Richardson <mcr+IETF@sandelman.ca>ca>, Sandelman Software Works
> IETF ROLL WG co-chair.    http://datatracker.ietf.org/wg/roll/charter/