X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=doc%2Ftxt%2Ftep119.txt;h=f8723f317157eafe5cddea349275f5746332a008;hb=6f095cc416fe0a3ca3912e743603531430e1b55f;hp=290de73e3e58eb4e540b08b7d2f94ab2b0d280e9;hpb=ac19889e754777ca5b8e2d697ed6fa9b2c026fb0;p=tinyos-2.x.git diff --git a/doc/txt/tep119.txt b/doc/txt/tep119.txt index 290de73e..f8723f31 100644 --- a/doc/txt/tep119.txt +++ b/doc/txt/tep119.txt @@ -5,7 +5,7 @@ Collection :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 @@ -23,11 +23,15 @@ Abstract ==================================================================== 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 @@ -42,16 +46,16 @@ it. Sometimes, depending on the form of data collection, systems need 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 @@ -63,8 +67,8 @@ algorithmic edge cases that generally occur in wireless routing: 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. @@ -80,15 +84,17 @@ describes a set of components and interfaces for collection services. 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 @@ -100,7 +106,7 @@ snoopers use the Receive interface [1_] to receive a snooped 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 @@ -126,11 +132,11 @@ use the Receive interface [1_] to receive a message delivered by 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:: @@ -141,12 +147,12 @@ 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 ==================================================================== @@ -171,10 +177,10 @@ which has the following signature:: } -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 @@ -185,22 +191,25 @@ collection_id_t. Each collection_id_t corresponds to a different 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.