From 2727e48315f17814ea11b1ccff9f324dc12b0b1d Mon Sep 17 00:00:00 2001 From: scipio Date: Fri, 8 Sep 2006 22:53:17 +0000 Subject: [PATCH] Add TEP 122 and 123. --- doc/txt/tep122.txt | 122 +++++++++++++++++++++++++++++ doc/txt/tep123.txt | 187 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 309 insertions(+) create mode 100644 doc/txt/tep122.txt create mode 100644 doc/txt/tep123.txt diff --git a/doc/txt/tep122.txt b/doc/txt/tep122.txt new file mode 100644 index 00000000..87670103 --- /dev/null +++ b/doc/txt/tep122.txt @@ -0,0 +1,122 @@ +===================================================== +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 + +.. 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 + + diff --git a/doc/txt/tep123.txt b/doc/txt/tep123.txt new file mode 100644 index 00000000..93e6b820 --- /dev/null +++ b/doc/txt/tep123.txt @@ -0,0 +1,187 @@ +============================================================================== +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 + +.. 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. + + -- 2.39.2