Subject: [6tisch] draft-papadopoulos-6tisch-pre-reqs review

From: Xavi Vilajosana Guillen <[email-masked]>
Date: Tue, 6 Feb 2018 12:48:07 +0100

Dear George and all

as agreed during the last call meeting I did a review to
the draft-papadopoulos-6tisch-pre-reqs. Find inline my comments tagged with
[XV].

regards
X
-------------------------

6TiSCH                                              G. Papadopoulos, Ed.
Internet-Draft                                              N. Montavont
Intended status: Informational                            IMT Atlantique
Expires: January 3, 2018                                      P. Thubert
                                                                   Cisco
                                                            July 2, 2017

   Exploiting Packet Replication and Elimination in Complex Tracks in
                              6TiSCH LLNs
                 draft-papadopoulos-6tisch-pre-reqs-00

Abstract

   6TiSCH Packet Replication and Elimination mechanism consists in
   duplicating data packets into several paths in the network to
   increase reliability and provide low jitter.  Over a wireless medium,
   this technique can take advantage of communication overhearing, when
   parallel transmissions over two adjacent paths are scheduled.  This
   document presents the concept and details the required changes to the
   current specifications that will be necessary to enable this.

Status of This Memo

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

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   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."

   This Internet-Draft will expire on January 3, 2018.

Copyright Notice

   Copyright (c) 2017 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

Papadopoulos, et al.     Expires January 3, 2018                [Page 1]
Internet-Draft        Address Protection ND for LLN            July 2017

   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 Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   3
   3.  Tracks  . . . . . . . . . . . . . . . . . . . . . . . . . . .   3
     3.1.  Tracks Overview . . . . . . . . . . . . . . . . . . . . .   3
     3.2.  Complex Tracks  . . . . . . . . . . . . . . . . . . . . .   3
   4.  Packet Replication and Elimination principles . . . . . . . .   3
     4.1.  Packet Replication  . . . . . . . . . . . . . . . . . . .   4
     4.2.  Packet Elimination  . . . . . . . . . . . . . . . . . . .   5
     4.3.  Promiscuous Overhearing . . . . . . . . . . . . . . . . .   5
   5.  Requirements  . . . . . . . . . . . . . . . . . . . . . . . .   6
     5.1.  Requirements Related to Alternative Parent Selection  . .   6
     5.2.  Requirements Related to Promiscuous Overhearing . . . . .   6
     5.3.  Requirements Related to Cells without ACKs  . . . . . . .   7
     5.4.  Requirements Related to Packet Elimination  . . . . . . .   7
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .   7
   7.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   7
   8.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   7
     8.1.  Informative references  . . . . . . . . . . . . . . . . .   8
     8.2.  Other Informative References  . . . . . . . . . . . . . .   8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   8

1.  Introduction

   Some applications (such as Wireless Industrial IoT) require robust
   communications framework that guarantees data packet delivery in a
   given delay.  For example, a periodic process may need to be repeated
   identically every time.  To reach this ambition, the network must not
   only be reliable but also deterministic.

   A deterministic network ensures that the transported data packet will
   be carried out in a pre-defined and in a tight window of time,
   whatever the quality of the wireless links and the network
   congestion.  The goal of such network is to exhibit ultra-low jitter
   performance, i.e., close to 0.  IEEE std. 802.15.4 [IEEE802154-2015]
   has provision to provide guarantees for deterministic networks.
   Time-Slotted Channel Hopping (TSCH) provides transmission schedule to
   avoid random access to the medium and channel diversity to fight
   interferences.  However, TSCH is prone to retransmissions when the
   actual transmission was unsuccessful, due to external interference or

Papadopoulos, et al.     Expires January 3, 2018                [Page 2]
Internet-Draft        Address Protection ND for LLN            July 2017

   potential collision and, consequently, it increases the end-to-end
   delay performance.

   This document is mainly motivated by the ongoing work in the 6TiSCH
   working group.  The architecture of a 6TiSCH network is detailed in
   6TiSCH Architecture [I-D.ietf-6tisch-architecture] draft, which is
   used for the remainder of this document.  In this specification, we
   focus on Complex Track with Replication and Elimination.

2.  Terminology

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

3.  Tracks

3.1.  Tracks Overview

   The 6TiSCH architecture introduces the concept of Tracks in 6TiSCH
   Architecture [I-D.ietf-6tisch-architecture].  A simple track is
   composed of a sequence of cells (a combination of a transmitter, a
   receiver and a given channel offset) to ensure the transmission of a
   single packet from a source 6TiSCH node to a destination 6TiSCH node
   across a 6TiSCH multihop path.

3.2.  Complex Tracks

   A Complex Track is designed as a directed acyclic graph from a source
   6TiSCH node towards a destination 6TiSCH node to support multi-path
   forwarding, as introduced in 6TiSCH Architecture
   [I-D.ietf-6tisch-architecture].  By employing DetNet Packet
   Replication and Elimination (PRE) techniques, several paths may be
   computed, and these paths may be more or less independent.  For
   example, a complex Track may branch off and rejoin over non-congruent
   paths (branches).

 [XV] this is not clear. What are the requirements to compute that paths?
 are they feasible given the restrictions of a 6TiSCH network. Could you
detail more how this paths may be computed? what is the information that is
required and how this information is made available to the nodes in the
network? Is this a L4 task?  or is handled at the L2.5?

   In the following Section, we will detail Deterministic Networks PRE
   techniques.

4.  Packet Replication and Elimination principles

   In a nutshell, PRE consists in establishing several paths in a
   network to provide redundancy and parallel transmissions to bound the
   delay to traverse the network.  Optionnally, promiscuous listening
   between paths is possible, such that the nodes on one path may
   overhear transmissions along the other path.  Considering the
   scenario depicted in Figure 1, many different paths are possible for

Papadopoulos, et al.     Expires January 3, 2018                [Page 3]
Internet-Draft        Address Protection ND for LLN            July 2017

   S to reach R.  A simple way to take benefit from this topology could
   be to use the two independent paths via nodes A, C, E and via B, D,
   F.  But more complex paths are possible by interleaving transmissions
   from one level of the path to the upper level in a ship-in-the-night
   fashion.

[xv] Not clear what in a ship-in-the-night fashion means here

   The 6TiSCH PRE may also take advantage to the shared
   properties of the medium to compensate for the potential loss that is
   incurred with radio transmissions.  For instance, when the source
   sends to A, B may listen and get a second chance to receive the frame
   without an additional transmission.  Note that B would not have to
   listen if it already received that particular frame at an earlier
   time slot.
[xv] This is assuming some sort of implicit knowledge in B. Not sure if
this is
possible without specific signaling.

                               (A)   (C)   (E)

                 source (S)                       (R) (root)

                               (B)   (D)   (F)

    Figure 1: A Typical Ladder Shape with Two Parallel Paths Toward the
                                Destination

   PRE model can be implemented in both centralized and distributed
   scheduling approach.  In the centralized approach, a scheduler
   calculates the routes and schedules the communication among the nodes
   along a circuit such as a Label switched path.  In the distributed
   approach, each node selects its route to the destination.  In both
   cases, a default parent and alternate parent(s) should be selected to
   set up complex tracks.

   In the following Subsections, detailed description of all required
   operations defined by PRE, namely, Alternative Path Selection, Packet
   Replication, Packet Elimination and Promiscuous Overhearing, will be
   described.

4.1.  Packet Replication

   The objective of PRE is to offer deterministic networking properties,
   with high reliability and bounded latency.  To achieve this goal,
   determinism in every level of the forwarding path should be
   guaranteed.  By employing Packet Replication procedure, each node
   transmits (i.e., replicates) each data packet to both its Default
   Parent (DP) and Alternative Parent (AP).  To do so, each node (i.e.,
   source and intermediate 6TiSCH nodes) transmits the data packet twice
   in unicast to each parent.  For instance, in Figure 2, the source
   6TiSCH node S is transmitting the packet to both parents, nodes A and

Papadopoulos, et al.     Expires January 3, 2018                [Page 4]
Internet-Draft        Address Protection ND for LLN            July 2017

   B, in two different timeslots within the same TSCH slotframe.  Thus,
   the packet eventually obtains parallel paths to the destination.

                      ===> (A) ====> (C) ====> (E) ====
                    //                                 \\
          source (S)                                     (R) (root)
                    \\                                 //
                      ===> (B) ====> (D) ====> (F) ====

   Figure 2: Packet Replication: S transmits twice the same data packet,
                     to its DP (A) and to its AP (B).

[XV] here you are only considering duplication at the source. While would
be better IMHO to duplicate before those links that show lower performance.
Would you also consider duplication at inner hops?

4.2.  Packet Elimination

   The replication operation increases the traffic load in the network,
   due to packet duplications.  Thus, Packet Elimination operation
   should be applied at each RPL DAG level to reduce the unnecessary
   traffic.
   To this aim, once a node receives the first copy of a data
   packet, it discards the following copies.  Because the first copy
   that reaches a node is the one that counts, and thus will be the only
   copy that will be forwarded upward.

[xv] Will this node duplicate it again?

4.3.  Promiscuous Overhearing

   Considering that the wireless medium is broadcast by nature, any
   neighbor of a transmitter may overhear a transmission.  By employing
   the Promiscuous Overhearing operation, DP and AP eventually have more
   chances to receive the data packets.  In Figure 3, when node A is
   transmitting to its DP (node C), the AP (node D) and its Sibling
   (node B) may decode this data packet as well.  As a result, by
   employing correlated paths, a node may have multiple opportunities to
   receive a given data packet.  This feature not only enhances the end-
   to-end reliability but also it reduces the end-to-end delay.

                      ===> (A) ====> (C) ====> (E) ====
                    //     ^ | \\                      \\
          source (S)       | |   \\                      (R) (root)
                    \\     | v     \\                  //
                      ===> (B) ====> (D) ====> (F) ====

    Figure 3: Unicast to DP with Overhearing: by employing Promiscuous
   Overhearing, DP, AP and the Sibling nodes have more opportunities to
                       receive the same data packet.

Papadopoulos, et al.     Expires January 3, 2018                [Page 5]
Internet-Draft        Address Protection ND for LLN            July 2017

5.  Requirements

5.1.  Requirements Related to Alternative Parent Selection

   To perform the Replication procedure, it is necessary to define the
   Alternative Parent(s) and, consequently, the path to the destination
   6TiSCH node, for each node in the 6TiSCH network.  An AP can be
   selected in many different ways, and is dependent on the
   implementation.  However, control packets should give some metrics to
   discriminate between different neighbors.

   Related requirements are:

   Req1.1: To design such algorithm, RPL DODAG Information Object (DIO)
   message format SHOULD be extended with an option to allow for a
   6TiSCH node to learn additional information for its potential parent
   and its list of parents.

[XV] What information? a node receives DIOs from different neighbors. Could
that information be used without modyfing the DIO?

   Req1.2: The routing protocol SHOULD be extended to allow for each
   6TiSCH node to select AP(s) and duplicate a packet to several next
   hops.

[XV] This is implementation no? In their neighbor set nodes can be select
possible parents by rank given a destination (upstream).
Usually querying RPL returns the preferred parent given a destination
address.  Extending this to return the N best connected parents
seems implementaiton specific no?
[XV] what is specific in duplicating a packet that needs to be known at L3?
Does L3 need to know this is a duplicate packet? or this is something that
is handled at L4-7?

5.2.  Requirements Related to Promiscuous Overhearing

   As stated previously, to further increase the 6TiSCH network
   reliability and to achieve deterministic packet deliveries at the
   destination 6TiSCH node, promiscuous overhearing can be considered.

   As it is described in BCP 210 [RFC8180], in TSCH mode, the data
   frames are transmitted in unicast mode and are acknowledged by the
   receiving neighbor.  To perform the promiscuous overhearing
   procedure, there SHOULD be an option for the transmitted frames,
   i.e., in unicast, to be overheard by the potential neighborhood
   6TiSCH node.

   Related requirements are:

   Req2.1: The 6top Protocol [I-D.ietf-6tisch-6top-protocol] SHOULD be
   extended to allow optionally a cell reservation with two receivers,
   i.e., DP and AP.  Considering that each frame may be transmitted
   twice in unicast to each parent, then depending the transmission,
   either DP will acknowledge the frame or AP will.

[XV] this is an interesting requirement. The destination address filtering
is performed by the MAC layer,  usually a node receiving a packet with a
destination address different than its own and different to 0xFF  discards
the packet immediatelly. Note that this functionality can even be
automatically performed by hardware in some MCUs.

If we assume that a 15.4 implementation can baypass this filtering, either
by using an anycast/multicast address as  destination or by
programmatically forcing to accept such a frame, then we can talk about
what 6P should provide to support it.

Given that consideration and assuming that the MAC Layer is the responsible
of handling the reception of a non-matching destination address, 6P  can
simply support that traffic pattern through the use of a TX cell at the
transmitter side and a RX cell at the reception side (in both DP and AP)
right ?

   Req2.2: Next, to request the overhearing cells, the 6P ADD Request
   Format SHOULD be transmitted either twice to each parent, i.e., DP
   and AP, or once in multicast to both parents.

[XV] Sending it twice is fine. Not need to complicate 6P with multicast.

Papadopoulos, et al.     Expires January 3, 2018                [Page 6]
Internet-Draft        Address Protection ND for LLN            July 2017

5.3.  Requirements Related to Cells without ACKs

   As stated in BCP 210 [RFC8180], each date frame is acknowledged by
   the receiving 6TiSCH node.  However, by employing promiscuous
   overhearing operation, particular attention should be given to who
   will acknowledge a transmission, i.e., the DP, and / or one of the
   AP(s)

   Related requirements are:

   Req4.1: To avoid the ACK collision, the TSCH Schedule as per BCP 210
   [RFC8180], only the DP MUST acknowledge the data packet.

   [XV] which may happen as the AP will detect that the destination address
does not match its address and hence does not ACK.
   this is an implementation decision in my opinion.

   Req4.2: Alternatively, to achieve further consistency the overheard
   transmission need be acknowledged by both parents, i.e., DP and AP.
   To do so, BCP 210 [RFC8180] SHOULD be extended accordingly.

   [XV] This will require major changes in the MAC layer operation. I see
it unfeasible

5.4.  Requirements Related to Packet Elimination

   By employing packet replication operation, the 6TiSCH network expects
   to perform the packet elimination operation along a complex Track to
   bound the number of the duplicated packets, i.e., the unnecessary
   traffic.

   Related requirements are:

   Req5.1: As per 6TiSCH Architecture [I-D.ietf-6tisch-architecture],
   6TiSCH has no position about how the sequence numbers would be tagged
   in the packet.  However, it comes with Tagging Packets for Flow
   Identification.  More specifically, a 6TiSCH network expects that
   timeslots corresponding to copies of a same frame along a complex
   Track are correlated by configuration and, thus, does not need to
   process the sequence numbers.

Papadopoulos, et al.     Expires January 3, 2018                [Page 9]

-- 
Dr. Xavier Vilajosana
Wireless Networks Lab

*Internet Interdisciplinary Institute (IN3)Professor*
(+34) 646 633 681
[email-masked] <[email-masked]>
http://xvilajosana.org
http://wine.rdi.uoc.edu
Parc Mediterrani de la Tecnologia
Av Carl Friedrich Gauss 5, B3 Building
08860 Castelldefels (Barcelona). Catalonia. Spain

---

From: "Georgios Z. Papadopoulos" <[email-masked]>
Date: Tue, 6 Feb 2018 15:03:05 +0100

Hello Xavier,

Thank you so much for your inputs. 
I will come back with an updated version, and feedbacks to all your comments.

Thanks again,
Georgios

————————————————————
Georgios Z. Papadopoulos, Ph.D.
Associate Professor, IMT Atlantique

web: 	 www.georgiospapadopoulos.com <http://www.georgiospapadopoulos.com/>
twitter: 	@gzpapadopoulos <https://twitter.com/gzpapadopoulos?ref_src=twsrc%5Etfw&ref_url=http://georgiospapadopoulos.com/>
——
Consider to submit @AdHoc-Now 2018 <http://conferences.imt-atlantique.fr/adhocnow2018/>
————————————————————

> On Feb 6, 2018, at 12:48, Xavi Vilajosana Guillen <[email-masked]> wrote:
> 
> Dear George and all
> 
> as agreed during the last call meeting I did a review to the draft-papadopoulos-6tisch-pre-reqs. Find inline my comments tagged with [XV].
> 
> regards
> X
>    Drafts is at http://datatracker.ietf.org/drafts/current/ <http://datatracker.ietf.org/drafts/current/>.
> 
>    (http://trustee.ietf.org/license-info <http://trustee.ietf.org/license-info>) in effect on the date of
>  are they feasible given the restrictions of a 6TiSCH network. Could you detail more how this paths may be computed? what is the information that is required and how this information is made available to the nodes in the network? Is this a L4 task?  or is handled at the L2.5? 
> 
> [xv] This is assuming some sort of implicit knowledge in B. Not sure if this is 
> [XV] here you are only considering duplication at the source. While would be better IMHO to duplicate before those links that show lower performance. Would you also consider duplication at inner hops? 					 
> 					 
> 4.2.  Packet Elimination
> 
> [XV] What information? a node receives DIOs from different neighbors. Could that information be used without modyfing the DIO?   
> 
> [XV] This is implementation no? In their neighbor set nodes can be select possible parents by rank given a destination (upstream). 
> Usually querying RPL returns the preferred parent given a destination address.  Extending this to return the N best connected parents
> [XV] what is specific in duplicating a packet that needs to be known at L3? Does L3 need to know this is a duplicate packet? or this is something that 
> is handled at L4-7? 
>    
> [XV] this is an interesting requirement. The destination address filtering is performed by the MAC layer,  usually a node receiving a packet with a destination address different than its own and different to 0xFF  discards the packet immediatelly. Note that this functionality can even be automatically performed by hardware in some MCUs.
> 
> If we assume that a 15.4 implementation can baypass this filtering, either by using an anycast/multicast address as  destination or by programmatically forcing to accept such a frame, then we can talk about what 6P should provide to support it.  
> 
> Given that consideration and assuming that the MAC Layer is the responsible of handling the reception of a non-matching destination address, 6P  can simply support that traffic pattern through the use of a TX cell at the transmitter side and a RX cell at the reception side (in both DP and AP) right ?  
>    
>    
>    [XV] which may happen as the AP will detect that the destination address does not match its address and hence does not ACK. 
>    [XV] This will require major changes in the MAC layer operation. I see it unfeasible
> 
> Internet Interdisciplinary Institute (IN3)
> Professor
> (+34) 646 633 681
> [email-masked] <mailto:[email-masked]>
> http://xvilajosana.org <http://xvilajosana.org/>
> http://wine.rdi.uoc.edu <http://wine.rdi.uoc.edu/>
> _______________________________________________
> 6tisch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6tisch