< draft-vanderstok-roll-mcreq-01.txt   draft-vanderstok-roll-mcreq-02.txt >
ROLL P. van der Stok, Ed. ROLL P. van der Stok, Ed.
Internet-Draft Philips Research Internet-Draft vanderstok consultancy
Intended status: Informational March 12, 2012 Intended status: Informational E. Dijk
Expires: September 13, 2012 Expires: January 12, 2013 A. Lelkens
Philips Research
July 11, 2012
Multicast requirements for control over LLN Multicast requirements for control over LLN
draft-vanderstok-roll-mcreq-01 draft-vanderstok-roll-mcreq-02
Abstract Abstract
This is a working document intended to focus discussion on This is a working document intended to focus discussion on
requirements for multicast in Low-power and Lossy Networks in the requirements for multicast in Low-power and Lossy Networks in the
area of M2M communication for control purposes. The Trickle area of M2M communication for control applications. The Trickle
algorithm, which uses re-broadcasting to assure that messages arrive algorithm, which uses random re-broadcasting to assure that messages
at all destinations, is proposed as the ROLL multicast protocol. In arrive at all destinations, has been proposed in the Trickle
this draft additional requirements on Trickle, such as timeliness and Multicast Forwarding ROLL WG draft as the basis for a multicast
ordering, are motivated by building control. Re-broadcasting and routing protocol. In this draft additional requirements on multicast
timeliness can be mutually exclusive properties. To alleviate that routing are presented, such as timeliness, motivated by building
problem, this draft considers minimizing re-broadcast by limiting the control. Random re-broadcasting and timeliness can be difficult to
number of re-broadcasting devices in the wireless network. reconcile. This draft presents some simulation results in typical
control settings which show that achieving latencies below 400 ms is
feasible with Trickle. Recommendations are proposed for the current
Trickle Multicast Forwarding draft to achieve optimal performance and
meet the stated requirements.
Status of this Memo Status of this Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 13, 2012. This Internet-Draft will expire on January 12, 2013.
Copyright Notice Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 16 skipping to change at page 2, line 22
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Application characteristics . . . . . . . . . . . . . . . . . 4 2. Application characteristics . . . . . . . . . . . . . . . . . 4
3. Multicast requirements . . . . . . . . . . . . . . . . . . . . 5 3. Multicast requirements . . . . . . . . . . . . . . . . . . . . 6
4. Wireless link characteristics . . . . . . . . . . . . . . . . 7 4. Performance of Trickle-based multicast . . . . . . . . . . . . 7
5. Recommendation . . . . . . . . . . . . . . . . . . . . . . . . 9 4.1. Reasons for using Trickle . . . . . . . . . . . . . . . . 7
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 4.2. Simulation setup . . . . . . . . . . . . . . . . . . . . . 7
7. Security Considerations . . . . . . . . . . . . . . . . . . . 9 4.3. Simulation results . . . . . . . . . . . . . . . . . . . . 8
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9 4.4. Simulation conclusions . . . . . . . . . . . . . . . . . . 9
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5. Performance issues of Trickle Multicast Forwarding . . . . . . 9
9.1. Normative References . . . . . . . . . . . . . . . . . . . 9 5.1. Redundancy of Trickle ICMP message . . . . . . . . . . . . 10
9.2. Informative References . . . . . . . . . . . . . . . . . . 10 5.2. Ability to configure forwarders as data sinks . . . . . . 11
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.3. Issues in the 'consistency' definition . . . . . . . . . . 11
5.4. Window handling without ICMP . . . . . . . . . . . . . . . 12
6. Summary of Recommendations for Trickle Multicast Forwarding . 12
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12
8. Security Considerations . . . . . . . . . . . . . . . . . . . 13
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 13
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13
10.1. Normative References . . . . . . . . . . . . . . . . . . . 13
10.2. Informative References . . . . . . . . . . . . . . . . . . 14
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14
1. Introduction 1. Introduction
The ROLL working group is chartered to design and standardize a The ROLL working group is chartered to design and standardize a
routing protocol for resource constrained devices in Low-power and routing protocol for resource constrained devices in Low-power and
Lossy Networks (LLN) [I-D.ietf-roll-rpl]. The requirements for ROLL Lossy Networks (LLN) [RFC6550]. The requirements for ROLL are
are documented in [RFC5548] [RFC5673] [RFC5826] [RFC5867]. For documented in [RFC5548] [RFC5673] [RFC5826] [RFC5867]. For building
building control it is recognized that most communication is local to control it is recognized that most communication is local to the
the wireless mesh network, and does not necessarily pass through the wireless mesh network, and does not necessarily pass through the edge
edge router. The point-to-point RPL routing algorithm is developed router. The point-to-point RPL routing algorithm is developed to
to efficiently support such applications [I-D.ietf-roll-p2p-rpl]. efficiently support unicast routing in such applications
The Trickle algorithm was developed to support the RPL routing [I-D.ietf-roll-p2p-rpl]. The Trickle algorithm was initially
algorithm [RFC6206], and later proposed to support general multicast developed to support the RPL routing algorithm [RFC6206], and later
delivery in LLN [I-D.ietf-roll-trickle-mcast]. proposed to support general multicast delivery in LLNs in Trickle
Multicast Forwarding (TMF) [I-D.ietf-roll-trickle-mcast].
This draft discusses the multicast requirements for constrained This draft discusses the multicast requirements for constrained
devices participating in M2M building control networks. An important devices participating in M2M building control networks. An important
requirement is the delivery of control commands to a subset (group) requirement is the delivery of control commands to a subset (group)
of neighbouring devices in the LLN within some latency bound. of neighbouring devices in the LLN within some latency bound. Also,
analyses are provided of how well Trickle algorithm and TMF can meet
these requirements and suggestions for improvement are made.
1.1. Terminology 1.1. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
Addtional privileged words are described below. Addtional privileged words are described below.
"TMF" is used as an abbreviation for Trickle Multicast Forwarding as
described in [I-D.ietf-roll-trickle-mcast].
A "device" is a physical processor connected to at least one link A "device" is a physical processor connected to at least one link
through a network interface. Each interface has at least one IP through a network interface. Each interface has at least one IP
unicast address. The IP address is optionally bound to a host name, unicast address. The IP address is optionally bound to a host name,
which may be a Fully Qualified Domain Name (FQDN). which may be a Fully Qualified Domain Name (FQDN).
One device communicates directly with another device by wirelessly One device communicates directly with another device by wirelessly
transmitting packets to it over a link. The link quality is divided transmitting packets to it over a link. The link quality is divided
in three regions: in three regions [Zhao]:
1. good: where a transmitted packet will be correctly received by a 1. good: where a transmitted packet will be correctly received by a
destination with a probability higher than 99%. destination with a probability of say 95% or more.
2. transitional: where the probability of correct reception 2. transitional: where the probability of correct reception
fluctuates. fluctuates.
3. bad: where almost no transmission is successfully received. 3. bad: where almost no transmission is successfully received.
It is empirically known that good links can become bad occasionally It is empirically known that good links can become bad occasionally
(e.g. once a week for a few minutes)due to dynamic effects such as (e.g. once a week for a few minutes)due to dynamic effects such as
multipath interference. multipath interference.
A distinction is made between reception and delivery of a message. A A distinction is made between reception and delivery of a message. A
message is received when it is stored in the reception buffer of the message is received when it is stored in the reception buffer of the
skipping to change at page 4, line 15 skipping to change at page 4, line 21
passed from the reception buffer to the destination application. We passed from the reception buffer to the destination application. We
also say the application accepts the message. also say the application accepts the message.
Broadcasting is used for the link-local sending of one packet to all Broadcasting is used for the link-local sending of one packet to all
reachable 1-hop neigbours. This is equivalent to the term link-local reachable 1-hop neigbours. This is equivalent to the term link-local
multicast. multicast.
1.2. Motivation 1.2. Motivation
In this draft, we focus and develop discussions on requirements In this draft, we focus and develop discussions on requirements
pertaining to multicasting, in the context of building control pertaining to IP multicasting requirements and IP multicast routing,
applications. in the context of building control applications on LLNs. This draft
aims to show potential (latency) improvements for current proposed
multicast routing approaches, that can be easily attained.
2. Application characteristics 2. Application characteristics
Multicast is important for building control applications. Two types Multicast is important for building control applications. Two types
of applications are considered: of applications are considered:
1. Discovery messages to (a subset of) the members of the mesh 1. Discovery messages to (a subset of) the members of the mesh
(multicast GET) (multicast GET)
2. Control messages to a subset of the mesh (multicast PUT) 2. Control messages to a subset of the mesh (multicast PUT)
The first type requires the message to be sent to a (sub)set which The first type requires the message to be sent to a (sub)set which
may be randomly distributed over the building area. Some of the may be randomly distributed over the building area. Some of the
destinations return unicast messages to the source. destinations return unicast response messages to the source.
The second type requires the message to be sent to a closely spaced The second type requires a Non-Confirmable message mostly to be sent
subset. No return messages are generated. This second type is the to a closely spaced subset. No return messages are generated. This
subject of this draft, although most of the requirements equally second type is the subject of this draft, although most of the
apply to case 1. requirements equally apply to case 1.
PUT and GET are the message types defined for CoAP GET and PUT and Confirmable/Non-Confirmable are message types defined
[I-D.ietf-core-coap]. They are thought representative for the two for CoAP [I-D.ietf-core-coap]. They are thought representative for
applications types, as one returns a result and the other does not. the two applications types, as the multicast GET SHOULD return a
unicast response and the multicast PUT typically does not return a
response in control applications.
An office building typically consist of multiple floors, divided in An office building typically consist of multiple floors, divided in
working areas. The working areas can be open or enclosed by walls. working areas. The working areas can be open or enclosed by walls.
Within a working area sensors measure temperature, presence, humidity Within a working area sensors measure temperature, presence, humidity
and other parameters. On the basis of these measurements, equipment and other parameters. On the basis of these measurements, equipment
within the working area can receive commands to change settings. A within the working area can receive commands to change settings. A
well-known example is presence detection to switch on or dim lights. well-known example is presence detection to switch on or dim lights.
The equipment configuration is quite stable, because devices are The equipment configuration is quite stable, because devices are
installed in the ceiling, and modifying (or servicing) the installed in the ceiling, and modifying (or servicing) the
installation can be costly. installation can be costly.
skipping to change at page 5, line 13 skipping to change at page 5, line 23
The equipment is interconnected in a wireless network. The RF The equipment is interconnected in a wireless network. The RF
transmissions pass through the walls and generate interference to the transmissions pass through the walls and generate interference to the
wireless equipment in other working areas. wireless equipment in other working areas.
The lay-out of a network may be different from installation to The lay-out of a network may be different from installation to
installation. However, it is expected that many wireless networks installation. However, it is expected that many wireless networks
extend over one floor and include several working areas. Another extend over one floor and include several working areas. Another
working hypothesis is that most of the time sensors will multicast working hypothesis is that most of the time sensors will multicast
their values to a group of devices within the working area. their values to a group of devices within the working area.
Consequently, multicast messages are often meant for a subset of Consequently, multicast messages are often meant for a subset of
neigbouring devices. neigbouring (not necessarily 1-hop) devices.
A LoWPAN is a mesh of wireless devices that share the same IPv6 A LoWPAN is a mesh of wireless devices that share the same IPv6
address prefix. A typical LowPAN in a building may cover the area of address prefix. A typical LowPAN in a building may cover the area of
an entire floor. A commercial installation may cover 1000 m2 per an entire floor. A commercial installation may cover 1000 m2 per
floor. A length of 50 m can easily mean a hop count >5 for a message floor. A length of 50 m can easily mean a hop count >5 for a message
to pass from end to end. For example, devices may be installed in to pass from end to end. For example, devices may be installed in
the ceiling in a grid with a grid pattern distance of 40 cm between the ceiling in a grid with a grid pattern distance of 2 m between
devices. devices.
Messages may consist of sensor measurements performed or commands Messages may consist of sensor measurements performed or commands
issued in a given working area, which then must be acted upon by issued in a given working area, which then must be acted upon by
neigbouring devices in the same working area. Under this control neigbouring devices in the same working area. Under this control
pattern, source and sink are located in one working area, and pattern, source and sink are located in one working area, and
accordingly sink and source of a multicast message are often between accordingly sink and source of a multicast message are often between
3 - 6 m from each other. Consequently, it is required to send a 3 - 6 m from each other. Consequently, it is required to send a
multicast to a subset of the devices in the LoWPAN. multicast to a subset of the devices in the LoWPAN.
In case of commands to luminaries, messages must be delivered within In case of commands to luminaries, a command message must be
a clear deadline of about 200ms. In [RFC5867] a deadline of 120 ms delivered to all LoWPAN-local multicast group members within a clear
is suggested for other building applications. deadline of about 200ms. In [RFC5867] a deadline of 120 ms is
suggested for other building applications.
Although control messages are frequently exchanged between closely Although control messages are frequently exchanged between closely
spaced (less than 6 m) devices, it is sometimes necessary, say every spaced (less than 6 m) devices, it is sometimes necessary to send a
hour or less frequently, to send a message to a subset of devices message to a subset of devices covering the whole building. In that
covering the whole building. In that case the multicast message will case the multicast message will need to pass the edge router of the
need to pass the edge router of the lowpan and to propagate to other LoWPAN and to propagate to other subnets. This case is discussed in
subnets. more detail in [I-D.ietf-core-groupcomm].
3. Multicast requirements 3. Multicast requirements
The Multicast requirements are derived from the characteristics of The multicast requirements are derived from the characteristics of
the applications. A device is said to be correct it it follows the the aforementioned applications. A device is said to be correct it
selected multicast algorithm. The application characteristics and it follows the selected multicast routing algorithm. The application
the network installation make it possible to add an additional set of characteristics and the network installation make it possible to add
network properties to make the multicast algorithm more efficient. an additional set of network properties to make the multicast
algorithm more efficient.
The basic traditional multicast requirements (applying to PUT and The basic traditional multicast requirements (applicable to both PUT
GET)are: and GET) are [Mullender]:
o Validity: If sender S sends message, m, to a group, g, of o Validity: If sender S sends message, m, to a group, g, of
destinations, a path exists between S and a destination D, and S destinations, a path exists between S and any destination D, and
and D are correct, D eventually accepts m. if S and D are correct, D eventually accepts m.
o Integrity: A destination accepts m at most once from sender and o Integrity: A destination D accepts m at most once from sender S
only if sender sent m to a group including destination. and only if S sent m to a group including D.
o Agreement: If a correct destination of g accepts m, then all o Agreement: If a correct destination of g accepts m, then all
correct destinations of g accept m. correct destinations of g accept m.
The set of intended destination devices is identified by the The set of intended destination devices is identified by the
multicast (group) IP address. Every device in the associated multicast (group) IP address. Every device in the associated
multicast group is a destination of the multicast. Each destination multicast group is a destination of the multicast. Each destination
accepts messages with as destination the specified IP multicast accepts messages with as destination the specified IP multicast
address. Additional multicast requirements are: address. Additional multicast requirements are:
o Timeliness: There is a known constant C such that if m is sent at o Timeliness: There is a known constant C such that if m is sent at
time t, no correct destination accepts m after t+C. time t, no correct destination accepts m after t+C.
For lighting control applications the value of C is taken as 200 ms. For lighting control applications the value of C is taken as 200 ms.
This requirement considers the PUT case and not the return of a This requirement only holds for the PUT case without response from a
response in the GET case. destination, but not for the GET case where a response is returned.
o Ordering: When m1 and m2 sent to the same group g, and a receiver o Ordering: When m1 and m2 sent to the same group g, and a receiver
in g accepts message m1 before m2, every receiver in g accepts m1 in g accepts message m1 before m2, every receiver in g accepts m1
before accepting m2 before accepting m2
Ordering applies to PUT and GET cases. Ordering can be partial or Ordering applies to both the PUT and GET cases. Ordering can be
total. Partial ordering means that for specified message pairs, one partial or total. Partial ordering means that for specified message
message of the pair precedes the other. In case of total ordering, pairs, one message of the pair precedes the other. In case of total
every message pair is ordered. Partial ordering is obtained by ordering, every message pair is ordered. Partial ordering is
adding message counters in the message such that destinations can obtained by adding message counters in the message such that
order the messages of a given sender. Messages from different destinations can order the messages of a given sender. Messages from
sources are not ordered. Total ordering can be obtained with vector different sources are not ordered. Total ordering can be obtained
clocks or using synchronized clocks. Vector clocks require a large with vector clocks or using synchronized clocks. Vector clocks
overhead that increases linearly with the number of devices in the require a large overhead that increases linearly with the number of
network. As long as no synchronized clocks are available, partial devices in the network. As long as no synchronized clocks are
ordering seems the most realistic. Total Ordering is interesting for available, partial ordering seems the most realistic. Total Ordering
the discovery application. When two devices announce themselves is interesting for the discovery application. When two devices
simultaneously with conflicting properties, all participants can come announce themselves simultaneously with conflicting properties, all
to the same decision by favoring the first arrival. Partial ordering participants can come to the same decision by favoring the first
is necessary when a multicast message needs multiple packets (for arrival. Partial ordering is necessary when a multicast message
example discovery messages) or when multicast messages are sent with needs multiple packets (for example discovery messages) or when
intervals shorter than the throughput delay. multicast messages are sent with intervals shorter than the maximum
throughput delay.
4. Wireless link characteristics 4. Performance of Trickle-based multicast
It is possible to broadcast from a source to a set of devices In this section we investigate the behavior of the Trickle algorithm
reachable over good links in one hop. This is not sufficient because [RFC6206] when used for multicast routing. Rebroadcasting as defined
the set of reachable devices is often a subset of the set of in Trickle makes meeting tight deadlines a challenge. Simulation
destination devices. Consequently, additional measures are needed to results in this section show for particlar configurations and
make sure that the Agreement requirement is met. A standard parameter settings which end-to-end communication delays can be
technique, to reach all devices instead of a subset, stipulates that expected.
every receiver of a broadcast message rebroadcasts this message
(flooding). When the multicast address corresponds with a specified 4.1. Reasons for using Trickle
multicast address in the receiver device, the message is delivered.
Thanks to this technique it is assured that when a path exists The simplest approach to IP multicast is to broadcast from a source
between the source and the destination device, the destination device to a set of devices reachable over good links in one hop. This is
will eventually receive the message from the sender. not sufficient however, because the set of reachable devices is often
a subset of the set of destination devices. Consequently, additional
measures are needed to make sure that the Agreement requirement is
met. A standard technique, to reach all devices instead of a subset,
stipulates that every receiver of a broadcast message rebroadcasts
this message (flooding). When the multicast destination address of
the message corresponds with a specified multicast address in the
receiver device, the message is delivered. Thanks to this technique
it is assured that when a path exists between the source and the
destination device, the destination device will eventually receive
the message from the sender.
Given the network density described in section 2, the multicast can Given the network density described in section 2, the multicast can
generate a broadcast storm with lots of interfering senders. The generate a broadcast storm with lots of interfering senders. The
technique to prevent the storm, also used in Trickle, is to randomly technique to prevent the storm, also used in Trickle, is to randomly
delay the message rebroadcast. However, the long delays can delay a message rebroadcast. However, long delays can seriously
seriously jeopardize the timeliness requirement. This draft proposes jeopardize the Timeliness requirement. The following sections give
three ways suggested by the application characteristics, to reduce insight under which conditions the Timeliness requirement can be met.
the interference between re-broadcasting devices:
1. Restrict the scope of the multicast. 4.2. Simulation setup
2. Restrict number of rebroadcasting devices.
3. Weaken the Timeliness requirement.
In the application characteristics it is mentioned that most control The simulations were done on a general rectangular network topology
messages have a set of destinations which are closely spaced to the and on an approximation of known building installations. The IEEE
source. The interference between multicast sources can be reduced by 802.15.4 protocol is simulated with CSMA and the standard back-off
limiting the scope of the broadcast message. The ensuing proximity intervals specified by IEEE 802.15.4. Packets between A and B arrive
condition can be formulated for both PUT and GET as: with a probability dependent on the distance but independent of the
direction. A distance of 70m is at the limit of the transmission
range. Two rectangular meshes were tried: (1) 5 x 5 nodes and (2) 10
x 10 nodes. The distance between two adjoining neigbors was varied
between 5 and 70 m. The total surface for the 10 x 10 mesh varied
accordingly between 45 x 45 m^2 and 630 x 630 m^2. The building
installation approximation consist of a rectangular grid of 14 x 7
nodes over a surface of 35 x 15 m^2. Parameters Imin, Imax and k and
variables I, t and c are defined as in [RFC6206].
o Proximity condition: A multicast message is accepted by a subset 4.3. Simulation results
of devices closely spaced to the sender.
In practice, this condition means that most multicast messages can be The table below presents some of the results on the 5 x 5 mesh.
constrained to 1-2 hops. Therefore, it is recommended to put the
multicast range under control of the multicast source.
Given the stability of the network configuration, the configuration Imax k Parameter Distance
of good links is also stable over long periods (say several days). 10m 40m 70m
When all good links are available, the number of possible paths 250ms 1 hopcount 1 2-4 5-9
between a source and each of its destinations is probably larger than 250ms 1 avg delay 5 ms 40 ms 110 ms
required given the sporadic failure of a good link. Under the 250ms 1 max delay 18 ms 90 ms 1050 ms
assumption that the qualities of the good links of a given device are 250ms 1 msgs sent 0-5 0-11 1-12
unrelated, the failure of good link has no consequence for 250ms 1 msgs received 18-36 3-20 0-20
alternative good links. The number of paths can be reduced by 250ms 3 hopcount 1 2-4 5-9
specifying a subset of devices, called relay devices (possibly 250ms 3 avg delay 5 ms 40 ms 130 ms
equivalent with Trickle multicast forwarders mentioned in 250ms 3 max delay 25 90 ms 260 ms
[I-D.ietf-roll-trickle-mcast]), to rebroadcast messages. A path can 250ms 3 msgs sent 1-7 3-12 7-13
pass from a source via relay devices to the multicast destinations. 250ms 3 msgs received 40-60 14-32 9-23
A relay device can also be a destination device. In [RFC5867] it is 500ms 1 hopcount 1 3-5 5-10
mentioned that 1 out of 2 devices is a relay device. Given the 500ms 1 avg delay 5 ms 40 ms 110 ms
network densities foreseen for lighting, a much lower relay density 500ms 1 max delay 19 ms 100 ms 1500 ms
is possible. The reduction of the relay devices reduces the risk of 500ms 1 msgs sent 0-4 0-8 0-10
interference in the dense networks described in section 2. An 500ms 1 msgs received 12-26 0-16 0-16
appropriate condition to assure the presence of a path between source 500ms 3 hopcount 1 3-5 5-10
and destination can be formulated as: 500ms 3 avg delay 5 ms 40 ms 120 ms
500ms 3 max delay 22 80 ms 240 ms
500ms 3 msgs sent 1-8 2-9 5-10
500ms 3 msgs received 28-44 8-27 5-18
o Multiple relay links: any device has good links to at least q The observed behavior is close to what is observed on the 10 x 10
relay devices mesh and on the installation configuration. Behavior on, for
example, a single row of nodes tends to be quite different and
requires quite different parameter settings. The results in the
table concern node (4,4) which had the longest end-to-end delays of
all nodes. Node (0,0) sent a message every 2 seconds. Individual
packets were lost but all messages arrived at all nodes eventually.
The Imin was taken to 10 ms and Imax was taken to 250 ms and 500 ms
with quite similar results. Changing the Imax has measurable
influence on the maximum end-to-end delay. The table shows how many
copies of a given message were received by node (4,4) and how many
times a given message was rebroadcast. For k=3 more messages were
received and sent. Receiving more messages leads to lower maximum
delays because the probability of receiving the message early
increases with increasing rebroadcast frequency.
The value of q is determined by the quality of the links in a given The causes for the large maximum delays (>400ms), occurring at d=70m,
installation. have been investigated in more detail. It is shown that a new packet
does not always arrive after the first transmission. This is
probably due to the synchronization of nodes when a new message
arrives, resulting in hidden terminal effects at the destination node
by overlapping sending intervals of its neighbors. For d=70 m,
packets are only received by the direct neighbor along the x-axis or
the y-axis. Consequently, when node (x, y) receives a new message,
it originates probably from (x-1, y) or (x, y-1). When node (x, y)
sends, packets are received in nodes (x+1, y) and (x,y+1). Given a
Imin value of 10ms there is a large probability that the sending by
nodes (x+1, y) and (x, y+1) overlap, leading to collision of the
messages at node (x+1, y+1). In the following intervals, nodes (x+1,
y) and nodes (x, y+1) receive the last message from their neighbors
and do not repeat the message because c is larger than k, thus
leading to long delays. The receiving node (x+1, y+1) sends at
regular intervals, determined by the Imax value, its last received
'old' message. Often the reception of the old message by a neighbor
leads to resending the new message. For that reason the maximum
delay is linked to the maximum interval Imax. Increasing the value
of k increases the probability of reciveing rebroadcast messages.
However, the probability that a path was temporarily unavailable 4.4. Simulation conclusions
cannot be excluded. The timeliness requirement is too strong for
wireless sensor networks, where packets get lost for multiple reasons
like hidden terminal, multipath fading, and others. The timeliness
requirement can be reformulated for the PUT case as:
o Majority Timeliness: with high probability, p, the timeliness The results indicate that for the network configurations we foresee,
requirent is met; with probability (1-p) a subset s in g accepts m with Trickle it is quite possible to reach average message delivery
after t+C. latency within the 200 ms range, meeting the Timeliness requirement
for most nodes, and to limit the maximum latency by tuning parameter
k.
The agreement requirement specifies that all destinations in g accept 5. Performance issues of Trickle Multicast Forwarding
the message eventually. Consequently, there is a (low) probability
(1-p) that members of g accept the message after t+C. Probability p
and subset s are specified as function of the installation and linked
with the value of q. For a lighting application this means that in
general all lights switch on/off within 200 ms and quite
infrequently, (say once a month) one out of all lights swictches on/
off a bit later (say a few seconds).
Using rebroadcast with a frequency that decreases with increasing The Trickle Multicast Forwarding (TMF) draft
density to reduce the probability of interference (as in Trickle) [I-D.ietf-roll-trickle-mcast] differs from direct application of
assures that missed messages are eventually repeated. It should be [RFC6206] in the introduction of multi-source, sliding windows, and
noted that the relay nodes can be consistent while a receiver node is use of ICMP messages. For Trickle parameter k finite, a transmission
not. Relay nodes cannot detect the inconsistency, and are thus event consists of sending a Trickle ICMP advertizement (that
required to rebroadcast the latest message continuously, or receiver summarizes a forwarder's state i.e. buffered IP multicast packets)
nodes rebroadcast their status with a low frequency. and in addition any multicast messages that need rebroadcasting.
This section analyzes some issues of TMF, in particular its ability
to meet the Timeliness requirement for building control scenarios,
and proposes improvements to address the issues.
5. Recommendation 5.1. Redundancy of Trickle ICMP message
From the text above emerges a number of recommendations to make it Summarizing state in an ICMP message is clearly useful to reduce
possible to put propagation characteristics of the multicast network traffic, if many IP multicast packets are being buffered in
algorithm under application control. Trickle multicast forwarders. However, if only one or a few
1. Take into account timeliness and partial ordering requirements in multicast packets are active in the network at a time, a forwarder
multicast algorithm. sending ICMP messages generates unnecessary overhead. As an example,
2. Exploit the small range of most multicasts used for control consider a forwarder that stores and needs to rebroadcast a single
purposes and put multicast range under application control. multicast message m1. According to TMF, it would need to send an
3. Introduce a subset of devices as relay devices to reduce the ICMP message containing information about m1 (SeedID, sequence
number of rebroadcasting devices. number, M bit) and additionally send a Trickle Multicast message with
4. Introduce meachanisms to remove inconsistencies in receiver nodes a Trickle Multicast header option which contains exactly the same
in spite of consistent relay nodes. information (SeedID, sequence number, M bit) plus the useful
5. Use majority timeliness requirement to choose the number of relay application data.
devices with respect to the probability that a device misses its
multicast reception deadline.
6. Multicast messages transit through an edge router.
6. IANA Considerations In such cases were low latency is required, the extra overhead of
sending the ICMP message leads to additional delays, for example in
dense network topologies due to increased congestion. In a
simulation of a building control installation the operation with and
without extra ICMP message was compared for the case that a single
multicast message was active. Without ICMP messages an average
latency of message delivery to the entire group of 131 ms was
observed. The extra overhead generated by ICMP messages led to an
average delay of 197 ms, quite close to the Timeliness bound of 200
ms.
The simulation modeled a single IP multicast message active in a
6LoWPAN network, delivery targeted to a group which is a subset of 13
nodes out of 95 nodes total, with a 40-byte data payload, each node
acting as a forwarder, with Trickle parameters k=1, Imin=32 ms,
Imax=128 ms.
To addresss the latency issue without increasing k (which would lead
to increased traffic), we propose that:
o sending the Trickle ICMP message is made OPTIONAL as part of a
transmission event, if a Trickle forwarder has any Trickle
Multicast Messages to send in that transmission event. A Trickle
Multicast forwarder may decide per transmission event (depending
on internal state e.g. number of buffered messages) whether the
ICMP message is sent or not.
o as part of a transmission event, sending the Trickle ICMP message
MAY be done after retransmitting Trickle Multicast Messages. Note
that the TMF draft does not clearly express a preferred order for
Trickle ICMP messages.
These proposed changes are still fully compatible with existing
implementations of TMF.
5.2. Ability to configure forwarders as data sinks
The current TMF makes a separation between (IP) hosts and Trickle
Multicast forwarders. Nodes that only need to receive IP multicast
packets (not wanting to participate in rebroadcasting) therefore can
be configured as hosts unaware of the multicast routing protocol.
However, this bears the risk that such hosts receive a specific
multicast packet very late or never, because they don't have a way to
signal missing packets to Trickle forwarders. Implementing a node as
a host has the clear advantages that the node does not need to buffer
any Trickle Multicast Messages which can considerably reduce memory
usage.
A solution that enables the best of both worlds is to allow Trickle
Multicast forwarders to act as 'data sinks' only i.e. not acting as a
repeater. We propose that:
o a Trickle Multicast forwarder MAY act as a data sink, which means
that it does keep sliding window state for messages it accepts,
and sends Trickle ICMP messages, but does not buffer any Trickle
Multicast Messages for retransmission.
5.3. Issues in the 'consistency' definition
In the TMF draft the notion of 'consistency' (as we read it) is based
on information received in Trickle ICMP messages only, not on
information received from incoming Trickle Multicast Messages. This
operation can lead to unnecessary delays in certain use cases.
Consider the following scenario:
o Nodes A, B, C are Trickle Multicast forwarders; where A cannot
hear C and C cannot hear A
o A stores messages m1,m2,m3, B stores m1,m2,m3, C stores m2,m3
o C sends ICMP(m2,m3)
o B sees an inconsistency based on this and schedules the missing m1
for transmission
o A sends ICMP (m1,m2,m3) but not any multicast message m_i
o B sees a consistency and increments c
o When the Trickle timer at B expires assuming k=1, the scheduled
transmission of m1 is cancelled
o C does not get m1 from B, at least not during this round.
Eventually C will get m2, after more rounds (when B transmits before
A does), but later than necessary.
A first approach to improve latency in this scenario is to apply the
suppression only to ICMP messages, not to scheduled multicast
messages (such as m1 by B in the example above). A refinement of
this approach is to maintain a counter c for each SeedID/
Sequence-number combination, in addition to a global Trickle counter
c. Then, retransmission of Trickle Multicast Messages is only
suppressed for those messages that have been received at least k
times. ICMP suppression is still based on the global Trickle counter
c as in the current TMF draft.
5.4. Window handling without ICMP
A forwarder that does not support sending ICMP advertizements could
advertize its state by retransmitting the multicasat message with the
largest number in its window that has no missing messages relative to
the lower bound of the window. So if a forwarder has a window
containing m1,m2,m4,m5 it retransmits m2, triggering others to send
m3 (and maybe higher numbers). If it encounters an inconsistency,
i.e. seeing a multicast with a number lower than its own upperbound,
it itself would send out the messages that have a higher number than
the received multicast message (excluding the ones that it has
received at least k tines during the current Trickle interval).
6. Summary of Recommendations for Trickle Multicast Forwarding
From the analyses above emerge a number of recommendations that aim
to reduce transmission latency of multicast messages and to reduce
the probability of missing a multicast message. In summary, the
following adaptations to TMF [I-D.ietf-roll-trickle-mcast] are
proposed which can be applied independently of each other:
1. Efficient retransmission: sending the Trickle ICMP message is
made OPTIONAL as part of a transmission event if a Trickle
forwarder already has any Trickle Multicast Messages to send.
2. Allow data sinks: a Trickle Multicast forwarder MAY refrain from
buffering any Trickle Multicast Messages for retransmission.
3. Consistency improvement: When a transmission is suppressed, a
forwarder MAY only suppress ICMP but not suppress transmission of
a multicast message that was scheduled due to a detected
inconsistency. This approach could be refined by keeping in
addition to a global Trickle consistency counter c, separate
counters c per SeedID/sequence-number combination suppressing
only messages seen at least k times.
4. Window handling without ICMP: forwarders without ICMP sending
capability can ask for retransmissions by rebroadcasting
multicast messages
7. IANA Considerations
This document makes no request of IANA. This document makes no request of IANA.
Note to RFC Editor: this section may be removed on publication as an Note to RFC Editor: this section may be removed on publication as an
RFC. RFC.
7. Security Considerations 8. Security Considerations
TBD TBD
8. Acknowledgments 9. Acknowledgments
This I-D has benefited from conversations with and comments from This I-D has benefited from conversations with and comments from
Anders Brandt, Kerry Lynn, Zach Shelby, Emmanuel Frimout, Michael Anders Brandt, Kerry Lynn, Zach Shelby, Emmanuel Frimout, Michael
Verschoor, Jamie Mc Cormack, Dee Denteneer, Esko van Dijk, Jerald Verschoor, Jamie Mc Cormack, Dee Denteneer, Jerald Martocci, Matthieu
Martocci, Matthieu Vial, and Nicolas Riou. Vial, and Nicolas Riou.
9. References 10. References
9.1. Normative References 10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel, [RFC5548] Dohler, M., Watteyne, T., Winter, T., and D. Barthel,
"Routing Requirements for Urban Low-Power and Lossy "Routing Requirements for Urban Low-Power and Lossy
Networks", RFC 5548, May 2009. Networks", RFC 5548, May 2009.
[RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney, [RFC5673] Pister, K., Thubert, P., Dwars, S., and T. Phinney,
"Industrial Routing Requirements in Low-Power and Lossy "Industrial Routing Requirements in Low-Power and Lossy
skipping to change at page 10, line 22 skipping to change at page 13, line 45
Routing Requirements in Low-Power and Lossy Networks", Routing Requirements in Low-Power and Lossy Networks",
RFC 5826, April 2010. RFC 5826, April 2010.
[RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen, [RFC5867] Martocci, J., De Mil, P., Riou, N., and W. Vermeylen,
"Building Automation Routing Requirements in Low-Power and "Building Automation Routing Requirements in Low-Power and
Lossy Networks", RFC 5867, June 2010. Lossy Networks", RFC 5867, June 2010.
[RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko, [RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko,
"The Trickle Algorithm", RFC 6206, March 2011. "The Trickle Algorithm", RFC 6206, March 2011.
9.2. Informative References [RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R.,
Levis, P., Pister, K., Struik, R., Vasseur, JP., and R.
Alexander, "RPL: IPv6 Routing Protocol for Low-Power and
Lossy Networks", RFC 6550, March 2012.
[I-D.ietf-roll-rpl] 10.2. Informative References
Brandt, A., Vasseur, J., Hui, J., Pister, K., Thubert, P.,
Levis, P., Struik, R., Kelsey, R., Clausen, T., and T.
Winter, "RPL: IPv6 Routing Protocol for Low power and
Lossy Networks", draft-ietf-roll-rpl-19 (work in
progress), March 2011.
[I-D.ietf-roll-p2p-rpl] [I-D.ietf-roll-p2p-rpl]
Goyal, M., Baccelli, E., Philipp, M., Brandt, A., and J. Goyal, M., Baccelli, E., Philipp, M., Brandt, A., and J.
Martocci, "Reactive Discovery of Point-to-Point Routes in Martocci, "Reactive Discovery of Point-to-Point Routes in
Low Power and Lossy Networks", draft-ietf-roll-p2p-rpl-09 Low Power and Lossy Networks", draft-ietf-roll-p2p-rpl-13
(work in progress), March 2012. (work in progress), June 2012.
[I-D.ietf-roll-trickle-mcast] [I-D.ietf-roll-trickle-mcast]
Hui, J. and R. Kelsey, "Multicast Forwarding Using Hui, J. and R. Kelsey, "Multicast Forwarding Using
Trickle", draft-ietf-roll-trickle-mcast-00 (work in Trickle", draft-ietf-roll-trickle-mcast-00 (work in
progress), April 2011. progress), April 2011.
[I-D.ietf-core-coap] [I-D.ietf-core-coap]
Frank, B., Bormann, C., Hartke, K., and Z. Shelby, Shelby, Z., Hartke, K., Bormann, C., and B. Frank,
"Constrained Application Protocol (CoAP)", "Constrained Application Protocol (CoAP)",
draft-ietf-core-coap-08 (work in progress), October 2011. draft-ietf-core-coap-10 (work in progress), June 2012.
Author's Address [I-D.ietf-core-groupcomm]
Rahman, A. and E. Dijk, "Group Communication for CoAP",
draft-ietf-core-groupcomm-02 (work in progress),
July 2012.
[Zhao] Zhao, J. and R. Govindan, "Understanding Packet Delivery
Performance in Dense Wireless Sensor Networks", senSys ,
2003.
[Mullender]
Mullender, S., "Distributed Systems, Second Edition",
Section 5 , Addison-Wesley Publishing Company, Inc. ,
ISBN 0-201-62427-3, 1995.
Authors' Addresses
Peter van der Stok (editor) Peter van der Stok (editor)
vanderstok consultancy
Kamperfoelie 8
Helmond, 5708 DM
The Netherlands
Email: consultancy@vanderstok.org
Esko Dijk
Philips Research Philips Research
High Tech Campus 34-1 High Tech Campus 34-1
Eindhoven, 5656 AA Eindhoven, 5656 AA
The Netherlands The Netherlands
Email: peter.van.der.stok@philips.com Email: esko.dijk@philips.com
Armand Lelkens
Philips Research
High Tech Campus 34-1
Eindhoven, 5656 AA
The Netherlands
Email: armand.lelkens@philips.com
 End of changes. 53 change blocks. 
196 lines changed or deleted 403 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/