--- /dev/null
+=====================================================
+IEEE EUI-64 Unique Node Identifier
+=====================================================
+
+:TEP: 122
+:Group: Core Working Group
+:Type: Documentary
+:Status: Draft
+:TinyOS-Version: 2.x
+:Author: Gilman Tolle, Jonathan Hui
+
+:Draft-Created: 26-Apr-2006
+:Draft-Version:
+:Draft-Modified:
+:Draft-Discuss: TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>
+
+.. Note::
+
+ This memo documents a part of TinyOS for the TinyOS Community, and
+ requests discussion and suggestions for improvements. Distribution
+ of this memo is unlimited. This memo is in full compliance with
+ TEP 1.
+
+Abstract
+====================================================================
+
+A TinyOS application developer may desire a globally-unique node
+identifier within the IEEE EUI-64 namespace. This document describes
+the TinyOS components used to access such an identifier.
+
+1. Interfaces
+====================================================================
+
+A platform that can provide a valid IEEE EUI-64 globally-unique node
+identifier SHOULD provide it through a component with the signature
+defined here, enabling platform-independent access to the identifier::
+
+ configuration LocalIeeeEui64C {
+ provides interface LocalIeeeEui64;
+ }
+
+The identifier is accessed through the following interface::
+
+ interface LocalIeeeEui64 {
+ command ieee_eui64_t getId();
+ }
+
+The ieee_eui64_t type is defined in ``tos/types/IeeeEui64.h`` as::
+
+ enum { IEEE_EUI64_LENGTH = 8; }
+
+ typedef struct ieee_eui64 {
+ uint8_t data[IEEE_EUI64_LENGTH];
+ } ieee_eui64_t;
+
+If the platform can provide a valid IEEE EUI-64, the value returned
+from this call MUST follow the IEEE EUI-64 standard.
+
+If a platform can provide a unique identifier that is not a valid IEEE
+EUI-64 identifier, it SHOULD provide its unique identifier through a
+component with a different name and a different interface. The
+definition of such an interface is outside the scope of this TEP.
+
+2. IEEE EUI-64
+====================================================================
+
+The IEEE EUI-64 structure is copied here::
+
+ | company_id | extension identifier |
+ |addr+0 | addr+1 | addr+2 | addr+3 | addr+4 | addr+5 | addr+6 | addr+7|
+ | AC | DE | 48 | 23 | 45 | 67 | AB | CD |
+ 10101100 11011110 01001000 00100011 01000101 01100111 10101011 11001101
+ | | | |
+ | most significant byte least significant byte |
+ most-significant bit least-significant bit
+
+ If provided in byte-addressable media, the original byte-address order
+ of the manufacturer is specified: the most through least significant
+ bytes of the EUI-64 value are contained within the lowest through
+ highest byte addresses, as illustrated above.
+
+See: http://standards.ieee.org/regauth/oui/tutorials/EUI64.html
+
+The author of the LocalIeeeEui64C component MUST ensure that the
+getId() call returns a valid EUI-64 identifier that follows the
+standard, with the bytes in the order described above.
+
+3. Implementation Notes
+====================================================================
+
+Some TinyOS node platforms contain a unique hardware identifier that
+can be used to build the EUI-64 node identifier. That hardware
+identifier may be obtained from several places, e.g. a dedicated
+serial ID chip or a flash storage device. Users of the interface
+described in this document MUST NOT require knowledge of how the
+unique identifier is generated.
+
+The EUI-64 node identifier MUST be available before the Boot.booted()
+event is signalled. If the EUI-64 is derived from a hardware device,
+the hardware device should be accessed during the Init portion of the
+boot sequence.
+
+4. Author's Address
+====================================================================
+
+| Gilman Tolle
+| Arch Rock Corporation
+| 657 Mission St. Suite 600
+| San Francisco, CA 94105
+|
+| phone - +1 415 692 0828
+| email - gtolle@archrock.com
+
+| Jonathan Hui
+| Arch Rock Corporation
+| 657 Mission St. Suite 600
+| San Francisco, CA 94105
+|
+| phone - +1 415 692 0828
+| email - jhui@archrock.com
+
+
--- /dev/null
+==============================================================================
+The Collection Tree Protocol (CTP)
+==============================================================================
+
+:TEP: 123
+:Group: Network Working Group
+:Type: Documentary
+:Status: Draft
+:TinyOS-Version: 2.x
+:Author: Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, Sukun Kim, Philip Levis, and Alec Woo
+
+:Draft-Created: 3-Aug-2006
+:Draft-Version: $Revision$
+:Draft-Modified: $Date$
+:Draft-Discuss: TinyOS Developer List <tinyos-devel at mail.millennium.berkeley.edu>
+
+.. Note::
+
+ This memo documents a part of TinyOS for the TinyOS Community, and
+ requests discussion and suggestions for improvements. Distribution
+ of this memo is unlimited. This memo is in full compliance with
+ TEP 1.
+
+Abstract
+==============================================================================
+
+This memo documents the Collection Tree Protocol (CTP), which
+provides best-effort anycast datagram communication to one of the
+collection roots in a network.
+
+1. Introduction
+==============================================================================
+
+2. Assumptions and Limitations
+==============================================================================
+
+CTP is a tree-based collection protocol. Some number of nodes in a
+network advertise themselves as tree roots. Nodes form a set of routing
+trees to these roots. CTP is **address-free** in that a node does not
+send a packet to a particular root; instead, it implicitly chooses a
+root by choosing a next hop. Nodes generate routes to roots using
+a routing gradient.
+
+The CTP protocol assumes that the data link layer provides four things:
+
+ 1) Provides an efficient local broadcast address.
+ 2) Provides synchronous acknowledgments for unicast packets.
+ 3) Provides a protocol dispatch field to support multiple higher-level
+ protocols.
+ 4) Has single-hop source and destination fields.
+
+CTP assumes that it has link quality estimates of some number of nearby
+neighbors. These provide an estimate of the number of transmissions it
+takes for the node to send a unicast packet whose acknowledgment is
+successfully received.
+
+CTP has several mechanisms in order to improve delivery reliability,
+but it does not promise 100\% reliable delivery. It is best effort, but
+a best effort that *tries very hard.*
+
+CTP is designed for relatively low traffic rates. Bandwidth-limited systems
+might benefit from a different protocol, which can, for example, pack
+multiple small frames into a single data-link packet.
+
+
+3. Collection and CTP
+==============================================================================
+
+CTP uses expected transmissions (ETX) as its routing gradient. A root has an
+ETX of 0. The ETX of a node is the ETX of its parent plus the ETX of its
+link to its parent. This additive measure assumes that nodes use link-level
+retransmissions. Given a choice of valid routes, CTP SHOULD choose the one with the
+lowest ETX value. CTP represents ETX values as 16-bit fixed-point real numbers
+with a precision of hundredths. An ETX value of 451, for example, represents
+an ETX of 4.51, while an ETX value of 109 represents an ETX of 1.09.
+
+Routing loops are a problem that can emerge in a CTP network. Routing loops
+generally occur when a node choose a new route that has a significantly higher
+ETX than its old one, perhaps in response to losing connectivity with a candidate
+parent. If the new route includes a node which was a descendant, then a loop
+occurs.
+
+CTP addresses loops through two mechanisms. First, every CTP packet
+contains a node's current gradient value. If CTP receives a data frame with
+a gradient value lower than its own, then this indicates that there
+is an inconsistency in the tree. CTP tries to resolve the inconsistency
+by broadcasting a beacon frame, with the hope that the node which sent
+the data frame will hear it and adjust its routes accordingly. If a
+collection of nodes is separated from the rest of the network, then they
+will form a loop whose ETX increases forever. CTP's second mechanism
+is to not consider routes with an ETX higher than a reasonable constant.
+The value of this constant is implementation dependent.
+
+Packet duplication is an additional problem that can occur in CTP.
+Packet duplication occurs when a node receives a data frame successfully
+and transmits an ACK, but the ACK is not received. The sender retransmits
+the packet, and the receiver receives it a second time. This can have
+disasterous effects over multiple hops, as the duplication is exponential.
+For example, if each hop on average produces one duplicate, then on the
+first hop there will be two packets, on the second there will be four,
+on the third there will be eight, etc.
+
+Routing loops complicate duplicate suppression, as a routing loop may
+cause a node to legitimately receive a packet more than once. Therefore,
+if a node suppresses duplicates based solely on originating address and
+sequence number, packets in routing loops may be dropped. CTP data frames
+therefore have an additional time has lived (THL) field, which the
+routing layer increments on each hop. A link-level retransmission has
+the same THL value, while a looped version of the packet is unlikely
+to do so.
+
+4. CTP Data Frame
+==============================================================================
+
+The CTP data frame format is as follows::
+
+ 1
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ |C|P| reserved | THL |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | ETX |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | origin |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | seqno | collect_id |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | data ...
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+Field definitions are as follows:
+
+ * C: Congestion notification. If a node is receiving packets faster than it can forward them, it MAY set the C field to notify other nodes. If a node hears a packet from node N with the C bit set, it MUST NOT transmit CTP data frames to N until it hears a packet from N with the C bit cleared.
+ * P: Routing pull. The P bit allows nodes to request routing information from other nodes. If a node hears a packet with the P bit set, it SHOULD transmit a routing frame in the near future if it has a valid route.
+ * THL: Time Has Lived. When a node generates a CTP data frame, it MUST set THL to 0. When a node receives a CTP data frame, it MUST increment the THL. If a node receives a THL of 255, it increments it to 0.
+ * ETX: The ETX routing metric of the single-hop sender. When a node transmits a CTP data frame, it MUST put the ETX value of its route through the single-hop destination in the ETX field. If a node receives a packet with a lower gradient than its own, then it MUST schedule a routing frame in the near future.
+ * origin: The originating address of the packet. A node forwarding a data frame MUST NOT modify the origin field.
+ * seqno: Origin sequence number. The originating node sets this field, and a node forwarding a data frame MUST NOT modify it.
+ * collect_id: Higher-level protocol identifier. The origin sets this field, and a node forwarding a data frame MUST NOT modify it.
+ * data: the data payload, of zero or more bytes.
+
+Together, the origin, seqno and collect_id fields denote a unique
+***origin packet.*** Together, the origin, seqno, collect_id, and
+THL denote a unique ***packet instance*** within the network. The
+distinction is important for duplicate suppression in the presence
+of routing loops. If a node suppresses origin packets, then if
+asked to forward the same packet twice due to a routing loop, it will
+drop the packet. However, if it suppresses packet instances, then
+unless the THL has wrapped around to the identical value it had
+on previous times around.
+
+A node MUST send CTP data frames as unicast messages with link-layer
+acknowledgments enabled.
+
+5. CTP Routing Frame
+==============================================================================
+
+The CTP routing frame format is as follows::
+
+ 1
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ |C|P| reserved | parent |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | parent | ETX |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | ETX |
+ +-+-+-+-+-+-+-+-+
+
+The fields are as follows:
+
+ * C: Same as data frame.
+ * P: Same as data frame.
+ * parent: The node's current parent.
+ * metric: The node's current routing metric value.
+
+When a node hears a routing frame, it MUST update its routing table to
+reflect the address' new metric. If a node's ETX value changes
+significantly, then CTP SHOULD transmit a broadcast frame soon thereafter
+to notify other nodes, which might change their routes. The parent
+field acts as a surrogate for the single-hop destination field of
+a data packet: a parent can detect when a child's ETX is significantly
+below its own. When a parent hears a child advertise an ETX below its
+own, it MUST schedule a routing frame for transmission in the near
+future.
+
+
projects / tinyos-2.x.git / commitdiff