:TEP: 119
:Group: Net2 Working Group
:Type: Documentary
-:Status: Draft
+:Status: Final
:TinyOS-Version: > 2.1
:Author: Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, and Philip Levis
====================================================================
The memo documents the interfaces, components, and semantics used by
-collection protocol in TinyOS 2.x. Collection provides a best-effort,
-multihop delivery of packets to the root of a tree. There may be
-multiple tree roots in a network, and in this case the semantics
-are *anycast* delivery to at least one of the roots. A node sending
-a packet does not specify which root the packet is destined to.
+the collection protocols in TinyOS 2.x. Collection provides
+best-effort, multihop delivery of packets to one of a set of
+collection points. There may be multiple collection points in a
+network, and in this case the semantics are *anycast* delivery to at
+least one of the collection points. A node sending a packet does not
+specify which of the collection points the packet is destined to. The
+union of the paths from each node to one or more of the collection
+points forms a set of trees, and in this document we assume that
+collection points are the roots of these trees.
1. Introduction
to be able to inspect packets as they go by, either to gather
statistics, compute aggregates, or suppress redundant transmissions.
-Collection provides a best-effort, multihop delivery of packets to one
-of a network's tree roots: it is an *anycast* protocol. The semantics
-is that the protocol will make a reasonable effort to deliver the
-message to at least one of the roots in the network. By picking a
-parent node, a collection protocol inductively joins the tree its
-parent has joined. Delivery is best effort, and there can be
-duplicates delivered to one or more roots. Collection provides no
-ordering guarantees. Collection does not provide real-time guarantees,
-although specific implementations may extend the basic functionality
-to do so.
+Collection provides best-effort, multihop delivery of packets to one
+of a network's tree roots: it is an *anycast* protocol. The
+semantics are that the protocol will make a reasonable effort to
+deliver the message to at least one of the roots in the network. By
+picking a parent node, a node implementing the collection protocol
+inductively joins the tree its parent has joined. Delivery is best
+effort, and there can be duplicates delivered to one or more roots.
+Collection provides no ordering or real-time guarantees, although
+specific implementations may extend the basic functionality to do
+so.
Given the limited state that nodes can store and a general need for
distributed tree building algorithms, collection protocols encounter
a next hop.
* Duplicate suppression, detecting and dealing with lost
- acknowledgments causing packets to replicate in the network,
- wasting capacity.
+ acknowledgments that can cause packets to replicate in the
+ network, wasting capacity.
* Link estimation, evaluating the link quality to single-hop
neighbors.
2. Collection interfaces
====================================================================
-A node can perform four different roles in collection: sender,
-snooper, in-network processor, and receiver/root. Depending on their
-role, the nodes use different interfaces to interact with the
-collection component.
+A node can perform four different roles in collection: sender (or
+source), snooper, in-network processor, and receiver (or
+root). Depending on their role, the nodes use different interfaces to
+interact with the collection component.
The collection infrastructure can be multiplexed among independent
-applications, by means of a collection identifier. While data traffic
-in the protocol is multiplexed through these identifiers, control
-traffic is not: all data traffic uses the same routing topology.
+applications, by means of a collection identifier. The collection
+identifier is used to identify different data traffic at the sender,
+intermediate-nodes, or the receiver, much like port number in TCP. All
+data traffic, regardless of the collection identifier, use the same
+routing topology.
The nodes that generate data to be sent to the root are *senders*.
Senders use the Send interface [1_] to send data to the root of
message. The collection identifier is specified as a parameter
to Receive during instantiation.
-The nodes can process a packet that are in transit. These in-network
+The nodes can process a packet that is in transit. These in-network
*processors* use the Intercept interface to receive and update a
packet. The collection identifier is specified as a parameter to
Intercept during instantiation. The Intercept interface has this
collection. The collection identifier is specified as a parameter to
Receive during instantiation.
-The set of all roots and the paths that
-lead to them form the collection routing infrastructure in the network.
-For any connected set of nodes implementing the collection protocol
-there is only one collection infrastructure, *i.e.*, all roots in this
-set active at the same time are part of the same infrastructure.
+The set of all roots and the paths that lead to them form the
+collection routing infrastructure in the network. For any connected
+set of nodes implementing the collection protocol there is only one
+collection infrastructure, *i.e.*, all roots in this set active at the
+same time are part of the same infrastructure.
The RootControl interface configures whether a node is a
root::
command bool isRoot();
}
-Both commands MUST return SUCCESS if the node is now in the specified
-state, and FAIL otherwise. For example, if a node is already a root
-and an application calls RootControl.setRoot(), the call will
+The first two commands MUST return SUCCESS if the node is now in the
+specified state, and FAIL otherwise. For example, if a node is already
+a root and an application calls RootControl.setRoot(), the call will
return SUCCESS. If setRoot() returns SUCCESS, then a subsequent call
-to isRoot() MUST return TRUE. If unsetRoot() returns SUCCESS, then
-a subsequent call to isRoot() MUST return FALSE.
+to isRoot() MUST return TRUE. If unsetRoot() returns SUCCESS, then a
+subsequent call to isRoot() MUST return FALSE.
3 Collection Services
====================================================================
}
-CollectionC MAY have additional interfaces. These additional
-interfaces MUST have default functions on all outgoing invocations
-(commands for uses, events for provides) of those interfaces so that
-it can operate properly if they are not wired.
+CollectionC MAY have additional interfaces. All outgoing invocations
+(commands for uses, events for provides) of those interfaces MUST have
+default functions. Those default functions enable CollectionC to
+operate properly even when the additional interfaces are not wired.
Components SHOULD NOT wire to CollectionC.Send. The generic
component CollectionSenderC (described in section 3.1) provides
protocol operating on top of collection, in the same way that
different am_id_t values represent different protocols operating on
top of active messages. All packets sent with a particular
-collection_id_t generally have the same payload format, so that
+collection_id_t generally SHOULD have the same payload format, so that
snoopers, intercepters, and receivers can parse them properly.
ColletionC MUST NOT signal Receive.receive on non-root
-nodes. CollectionC MAY signal Receive.receive on a root node when a
-data packet successfully arrives at that node. If a root node calls
-Send, CollectionC MUST treat it as it if were a received packet. Note
-that the buffer swapping semantics of Receive.receive, when combined
-with the pass semantics of Send, require that CollectionC make a copy
-of the buffer if it signals Receive.receive.
+nodes. CollectionC MUST signal Receive.receive on a root node when a
+unique (non-duplicate) data packet successfully arrives at that
+node. It MAY signal Receive.receive when a duplicate data packet
+successfully arrives. If a root node calls Send, CollectionC MUST
+treat it as it if were a received packet. Note that the buffer
+swapping semantics of Receive.receive, when combined with the pass
+semantics of Send, require that CollectionC make a copy of the buffer
+if it signals Receive.receive.
If CollectionC receives a data packet to forward and it is not a root
-node, it MAY signal Intercept.forward.
-
-If CollectionC receives a data packet that a different node
-is supposed to forward, it MAY signal Snoop.receive.
+node, it MAY signal Intercept.forward. CollectionC MAY signal
+Snoop.receive when it hears a packet which a different node is
+supposed to forward. For any given packet it receives, CollectionC
+MUST NOT signal more than one of the Snoop.receive, Receive.receive,
+and Intercept.forward events.
RootControl allows a node to be made a collection tree root.
CollectionC SHOULD NOT configure a node as a root by default.
projects / tinyos-2.x.git / blobdiff