+++ /dev/null
-/* $Id$ */
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/** BasicRouting is to be implemented by all routing engines.
- * @author Rodrigo Fonseca
- * @date $Date$
- */
-interface BasicRouting {
- /** Get a set of neighbors that make progress towards the destination.
- * @param nextHops: pointer to an array where to store the next hops found.
- * This array is allocated at the caller. If the message
- * is to be received by the local node, nextHops will
- * contain exactly one entry, TOS_LOCAL_ADDRESS.
- * @param n : the maximum number of entries to return. Upon return, n
- * has the number of entries actually returned. If the message
- * is to be received locally, n will be set to 1.
- * @return : if the result is FAIL, n cannot be used.
- */
- command error_t getNextHops(am_addr_t* nextHops, uint8_t* n);
-}
-
+++ /dev/null
-/* $Id$ */
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/*
- * @author Rodrigo Fonseca
- * @date $Date$
- */
-#ifndef COLLECTION_H
-#define COLLECTION_H
-
-enum {
- AM_COLLECTION_DATA = 20,
- AM_COLLECTION_CONTROL = 21,
- AM_COLLECTION_DEBUG = 22,
-};
-
-typedef uint8_t collection_id_t;
-
-#define UQ_COLLECTION_ID "CollectionSenderC.CollectId"
-
-#endif
+++ /dev/null
-/* $Id$ */
-#include "Collection.h"
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/*
- * @author Rodrigo Fonseca
- * @date $Date$
- */
-configuration CollectionC {
- provides {
- interface SplitControl;
- interface Send;
- interface Receive;
- interface Receive as Snoop;
- interface Intercept;
- interface Packet;
- interface RootControl;
- }
-}
-
-implementation {
- components new ForwardingEngineP(), new TreeRoutingEngineP(8), LinkEstimatorC;
-
- Send = ForwardingEngineP;
- Receive = ForwardingEngineP;
- Snoop = ForwardingEngineP;
- Intercept = ForwardingEngineP;
- Packet = ForwardingEngineP;
- RootControl = TreeRoutingEngineP;
-
- ForwardingEngineP.BasicRouting -> TreeRoutingEngineP;
- TreeRoutingEngineP.LinkEstimator -> LinkEstimatorC;
- ForwardingEngineP.LinkEstimator -> LinkEstimatorC;
-
- components new LinkEstimatorAMSenderC(AM_COLLECTION_DATA)
- as DataAMSender;
- ForwardingEngineP.AMSend -> DataAMSender;
-
- components new LinkEstimatorAMReceiverC(AM_COLLECTION_DATA)
- as DataAMReceiver;
- ForwardingEngineP.AMReceive -> DataAMReceiver;
-
- components new LinkEstimatorAMSenderC(AM_COLLECTION_CONTROL)
- as ControlAMSender;
- TreeRoutingEngineP.AMSend -> ControlAMSender;
-
- components new LinkEstimatorAMReceiverC(AM_COLLECTION_CONTROL)
- as ControlAMReceiver;
- TreeRoutingEngineP.AMReceive -> ControlAMReceiver;
-}
+++ /dev/null
-/* $Id$*/
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/**
- * The CollectionDebug is an interface for sending debugging events to
- * a logging infrastructure. An implementer can choose to send the event
- * information to different destinations. Primary examples can include:
- * <ul>
- * <li> logging to the UART, in case of a testbed of network-connected
- * nodes;
- * <li> logging to flash, if the logs are to be retrieved later
- * <li> logging to the standard output, in the case of TOSSIM.
- * </ul>
- *
- * The interface does not specify in what format the log is to be produced,
- * or if other information, like timestamps, should be added, and this is
- * up to the implementer.
- *
- * Some commands are generic, like Event, EventSimple, and EventDbg, while others
- * are for more specific events related to collection, like EventRoute and EventMsg.
- *
-
- * @author Rodrigo Fonseca
- * @author Kyle Jamieson
- * @date $Date$
- */
-
-interface CollectionDebug {
- /* Log the occurrence of an event of type type */
- command error_t logEvent(uint8_t type);
-
- /* Log the occurrence of an event and a single parameter */
- command error_t logEventSimple(uint8_t type, uint16_t arg);
-
- /* Log the occurrence of an event and 3 16bit parameters */
- command error_t logEventDbg(uint8_t type, uint16_t arg1, uint16_t arg2, uint16_t arg3);
-
- /* Log the occurrence of an event related to forwarding a message.
- * This is intended to allow following the same message as it goes from one
- * hop to the next
- */
- command error_t logEventMsg(uint8_t type, uint16_t msg, am_addr_t origin, am_addr_t node);
-
- /* Log the occurrence of an event related to a route update message,
- * such as a node receiving a route, updating its own route information,
- * or looking at a particular entry in its routing table.
- */
- command error_t logEventRoute(uint8_t type, am_addr_t parent, uint8_t hopcount, uint16_t metric);
-}
+++ /dev/null
-#ifndef _COLLECTION_UART_MSG
-#define _COLLECTION_UART_MSG
-
-#include "AM.h"
-
-//Comment format -> :meaning:args
-enum {
- NET_C_DEBUG_STARTED = 0xDE,
-
- NET_C_FE_MSG_POOL_EMPTY = 0x10, //::no args
- NET_C_FE_SEND_QUEUE_FULL = 0x11, //::no args
- NET_C_FE_NO_ROUTE = 0x12, //::no args
- NET_C_FE_SUBSEND_OFF = 0x13,
- NET_C_FE_SUBSEND_BUSY = 0x14,
- NET_C_FE_BAD_SENDDONE = 0x15,
- NET_C_FE_QENTRY_POOL_EMPTY = 0x16,
- NET_C_FE_SUBSEND_SIZE = 0x17,
- NET_C_FE_LOOP_DETECTED = 0x18,
- NET_C_FE_SEND_BUSY = 0x19,
-
- NET_C_FE_SENDQUEUE_EMPTY = 0x50,
- NET_C_FE_PUT_MSGPOOL_ERR = 0x51,
- NET_C_FE_PUT_QEPOOL_ERR = 0x52,
- NET_C_FE_GET_MSGPOOL_ERR = 0x53,
- NET_C_FE_GET_QEPOOL_ERR = 0x54,
-
- NET_C_FE_SENT_MSG = 0x20, //:app. send :msg uid, origin, next_hop
- NET_C_FE_RCV_MSG = 0x21, //:next hop receive:msg uid, origin, last_hop
- NET_C_FE_FWD_MSG = 0x22, //:fwd msg :msg uid, origin, next_hop
- NET_C_FE_DST_MSG = 0x23, //:base app. recv :msg_uid, origin, last_hop
- NET_C_FE_SENDDONE_FAIL = 0x24,
- NET_C_FE_SENDDONE_WAITACK = 0x25,
- NET_C_FE_SENDDONE_FAIL_ACK_SEND = 0x26,
- NET_C_FE_SENDDONE_FAIL_ACK_FWD = 0x27,
- NET_C_FE_DUPLICATE_CACHE = 0x28, //dropped duplicate packet seen in cache
- NET_C_FE_DUPLICATE_QUEUE = 0x29, //dropped duplicate packet seen in queue
- NET_C_FE_DUPLICATE_CACHE_AT_SEND = 0x2A, //dropped duplicate packet seen in cache
-
-
- NET_C_TREE_NO_ROUTE = 0x30, //: :no args
- NET_C_TREE_NEW_PARENT = 0x31, //: :parent_id, hopcount, metric
- NET_C_TREE_ROUTE_INFO = 0x32, //:periodic:parent_id, hopcount, metric
- NET_C_TREE_SENT_BEACON = 0x33,
- NET_C_TREE_RCV_BEACON = 0x34,
-
- NET_C_DBG_1 = 0x40, //:any :uint16_t a
- NET_C_DBG_2 = 0x41, //:any :uint16_t a, b, c
- NET_C_DBG_3 = 0x42, //:any :uint16_t a, b, c
-};
-
-typedef nx_struct CollectionDebugMsg {
- nx_uint8_t type;
- nx_union {
- nx_uint16_t arg;
- nx_struct {
- nx_uint16_t msg_uid;
- nx_am_addr_t origin;
- nx_am_addr_t other_node;
- } msg;
- nx_struct {
- nx_am_addr_t parent;
- nx_uint8_t hopcount;
- nx_uint16_t metric;
- } route_info;
- nx_struct {
- nx_uint16_t a;
- nx_uint16_t b;
- nx_uint16_t c;
- } dbg;
- } data;
- nx_uint16_t seqno;
-} CollectionDebugMsg;
-
-#endif
+++ /dev/null
-#include "Collection.h"
-
-interface CollectionId {
- command collection_id_t fetch();
-}
+++ /dev/null
-#include "Collection.h"
-
-generic module CollectionIdP(collection_id_t collectid) {
- provides interface CollectionId;
-}
-
-implementation {
- command collection_id_t CollectionId.fetch() {
- return collectid;
- }
-}
+++ /dev/null
-/* $Id$ */
-/*
- * Copyright (c) 2006 Stanford University.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * - Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * - Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the
- * distribution.
- * - Neither the name of the Stanford University nor the names of
- * its contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD
- * UNIVERSITY OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
- * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
- * OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-/*
- * @author Philip Levis
- * @author Kyle Jamieson
- * @date $Date$
- */
-
-#include <AM.h>
-
-interface CollectionPacket {
- command am_addr_t getOrigin(message_t* msg);
- command void setOrigin(message_t* msg, am_addr_t addr);
-
- command uint8_t getCollectionID(message_t* msg);
- command void setCollectionID(message_t* msg, uint8_t id);
-
- command uint8_t getControl(message_t* msg);
- command void setControl(message_t* msg, uint8_t control);
-
- command uint8_t getSequenceNumber(message_t* msg);
- command void setSequenceNumber(message_t* msg, uint8_t seqno);
-
- command uint16_t getGradient(message_t* msg);
- command void setGradient(message_t* msg, uint16_t gradient);
-
- /**
- * Returns a 32bit number which is a concatenation of
- * the origin and the sequence number */
- command uint32_t getPacketID(message_t* msg);
-}
+++ /dev/null
-/**
- * The virtualized collection sender abstraction.
- *
- * @author Kyle Jamieson
- * @author Philip Levis
- * @date April 25 2006
- * @see TinyOS Net2-WG
- */
-
-#include "Collection.h"
-#include "TreeCollection.h"
-
-generic configuration CollectionSenderC(collection_id_t collectid) {
- provides {
- interface Send;
- interface Packet;
- }
-}
-
-implementation {
- components new CollectionSenderP(collectid, unique(UQ_COLLECTION_CLIENT));
- Send = CollectionSenderP;
- Packet = CollectionSenderP;
-}
+++ /dev/null
-#include "Collection.h"
-
-generic configuration
-CollectionSenderP(collection_id_t collectid, uint8_t clientid) {
- provides {
- interface Send;
- interface Packet;
- }
-}
-
-implementation {
- components TreeCollectionC as Collector;
- components new CollectionIdP(collectid);
-
- Send = Collector.Send[clientid];
- Packet = Collector.Packet;
- Collector.CollectionId[clientid] -> CollectionIdP;
-}
+++ /dev/null
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-interface CostBasedRouting {
- command uint16_t getMyCost(uint8_t tree_id);
- command uint16_t getNeighborCost(uint8_t tree_id, uint16_t neighbor);
-}
-
+++ /dev/null
-#ifndef FORWARDING_ENGINE_H
-#define FORWARDING_ENGINE_H
-
-/*
- * Copyright (c) 2006 Stanford University.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * - Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * - Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the
- * distribution.
- * - Neither the name of the Stanford University nor the names of
- * its contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD
- * UNIVERSITY OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
- * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
- * OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include <AM.h>
-#include <message.h>
-
-/**
- * Author: Philip Levis
- * Author: Kyle Jamieson
- * Author: Omprakash Gnawali
- * Author: Rodrigo Fonseca
- */
-
-/*
- * These timings are in milliseconds, and are used by
- * ForwardingEngineP. Each pair of values represents a range of
- * [OFFSET - (OFFSET + WINDOW)]. The ForwardingEngine uses these
- * values to determine when to send the next packet after an
- * event. FAIL refers to a send fail (an error from the radio below),
- * NOACK refers to the previous packet not being acknowledged,
- * OK refers to an acknowledged packet, and LOOPY refers to when
- * a loop is detected.
- *
- * These timings are defined in terms of packet times. Currently,
- * two values are defined: for CC2420-based platforms (4ms) and
- * all other platfoms (32ms).
- */
-
-enum {
-#if PLATFORM_MICAZ || PLATFORM_TELOSA || PLATFORM_TELOSB || PLATFORM_TMOTE
- FORWARD_PACKET_TIME = 4,
-#else
- FORWARD_PACKET_TIME = 32,
-#endif
-};
-
-enum {
- SENDDONE_FAIL_OFFSET = 512,
- SENDDONE_NOACK_OFFSET = FORWARD_PACKET_TIME << 2,
- SENDDONE_OK_OFFSET = FORWARD_PACKET_TIME << 2,
- LOOPY_OFFSET = FORWARD_PACKET_TIME << 4,
- SENDDONE_FAIL_WINDOW = SENDDONE_FAIL_OFFSET - 1,
- LOOPY_WINDOW = LOOPY_OFFSET - 1,
- SENDDONE_NOACK_WINDOW = SENDDONE_NOACK_OFFSET - 1,
- SENDDONE_OK_WINDOW = SENDDONE_OK_OFFSET - 1,
-};
-
-
-/*
- * The number of times the ForwardingEngine will try to
- * transmit a packet before giving up if the link layer
- * supports acknowledgments. If the link layer does
- * not support acknowledgments it sends the packet once.
- */
-enum {
- MAX_RETRIES = 4
-};
-
-/*
- * The network header that the ForwardingEngine introduces.
- * This header will change for the TinyOS 2.0 full release
- * (it needs several optimizations).
- */
-typedef nx_struct {
- nx_uint8_t control;
- nx_am_addr_t origin;
- nx_uint8_t seqno;
- nx_uint8_t collectid;
- nx_uint16_t gradient;
-} network_header_t;
-
-/*
- * An element in the ForwardingEngine send queue.
- * The client field keeps track of which send client
- * submitted the packet or if the packet is being forwarded
- * from another node (client == 255). Retries keeps track
- * of how many times the packet has been transmitted.
- */
-typedef struct {
- message_t *msg;
- uint8_t client;
- uint8_t retries;
-} fe_queue_entry_t;
-
-#endif
+++ /dev/null
-/* $Id$ */
-/*
- * Copyright (c) 2006 Stanford University.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * - Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * - Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the
- * distribution.
- * - Neither the name of the Stanford University nor the names of
- * its contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD
- * UNIVERSITY OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
- * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
- * OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-/**
- * The ForwardingEngine is responsible for queueing and scheduling outgoing
- * packets in a collection protocol. It maintains a pool of forwarding messages
- * and a packet send
- * queue. A ForwardingEngine with a forwarding message pool of size <i>F</i>
- * and <i>C</i> CollectionSenderC clients has a send queue of size
- * <i>F + C</i>. This implementation has a large number of configuration
- * constants, which can be found in <code>ForwardingEngine.h</code>.
- *
- * <p>Packets in the send queue are sent in FIFO order, with head-of-line
- * blocking. Because this is a tree collection protocol, all packets are going
- * to the same destination, and so the ForwardingEngine does not distinguish
- * packets from one another: packets from CollectionSenderC clients are
- * treated identically to forwarded packets.</p>
- *
- * <p>If ForwardingEngine is on top of a link layer that supports
- * synchronous acknowledgments, it enables them and retransmits packets
- * when they are not acked. It transmits a packet up to MAX_RETRIES times
- * before giving up and dropping the packet.</p>
- *
- * <p>The ForwardingEngine detects routing loops and tries to correct
- * them. It assumes that the collection tree is based on a gradient,
- * such as hop count or estimated transmissions. When the ForwardingEngine
- * sends a packet to the next hop, it puts the local gradient value in
- * the packet header. If a node receives a packet to forward whose
- * gradient value is less than its own, then the gradient is not monotonically
- * decreasing and there may be a routing loop. When the ForwardingEngine
- * receives such a packet, it tells the RoutingEngine to advertise its
- * gradient value soon, with the hope that the advertisement will update
- * the node who just sent a packet and break the loop.
- *
- * <p>ForwardingEngine times its packet transmissions. It differentiates
- * between four transmission cases: forwarding, success, ack failure,
- * and loop detection. In each case, the
- * ForwardingEngine waits a randomized period of time before sending the next
- * packet. This approach assumes that the network is operating at low
- * utilization; its goal is to prevent correlated traffic -- such as
- * nodes along a route forwarding packets -- from interfering with itself.
- *
- * <table>
- * <tr>
- * <td><b>Case</b></td>
- * <td><b>CC2420 Wait (ms)</b></td>
- * <td><b>Other Wait (ms)</b></td>
- * <td><b>Description</b></td>
- * </tr>
- * <tr>
- * <td>Forwarding</td>
- * <td>Immediate</td>
- * <td>Immediate</td>
- * <td>When the ForwardingEngine receives a packet to forward and it is not
- * already sending a packet (queue is empty). In this case, it immediately
- * forwards the packet.</td>
- * </tr>
- * <tr>
- * <td>Success</td>
- * <td>16-31</td>
- * <td>128-255</td>
- * <td>When the ForwardingEngine successfully sends a packet to the next
- * hop, it waits this long before sending the next packet in the queue.
- * </td>
- * </tr>
- * <tr>
- * <td>Ack Failure</td>
- * <td>8-15</td>
- * <td>128-255</td>
- * <td>If the link layer supports acks and the ForwardingEngine did not
- * receive an acknowledgment from the next hop, it waits this long before
- * trying a retransmission. If the packet has exceeded the retransmission
- * count, ForwardingEngine drops the packet and uses the Success timer instead. </td>
- * </tr>
- * <tr>
- * <td>Loop Detection</td>
- * <td>32-63</td>
- * <td>512-1023</td>
- * <td>If the ForwardingEngine is asked to forward a packet from a node that
- * believes it is closer to the root, the ForwardingEngine pauses its
- * transmissions for this interval and triggers the RoutingEngine to
- * send an update. The goal is to let the gradient become consistent before
- * sending packets, in order to prevent routing loops from consuming
- * bandwidth and energy.</td>
- * </tr>
- * </table>
- *
- * <p>The times above are all for CC2420-based platforms. The timings for
- * other platforms depend on their bit rates, as they are based on packet
- * transmission times.</p>
-
- * @author Philip Levis
- * @author Kyle Jamieson
- * @date $Date$
- */
-
-#include <ForwardingEngine.h>
-#include "CollectionDebugMsg.h"
-
-generic module ForwardingEngineP() {
- provides {
- interface Init;
- interface StdControl;
- interface Send[uint8_t client];
- interface Receive[collection_id_t id];
- interface Receive as Snoop[collection_id_t id];
- interface Intercept[collection_id_t id];
- interface Packet;
- interface CollectionPacket;
- }
- uses {
- interface AMSend as SubSend;
- interface Receive as SubReceive;
- interface Receive as SubSnoop;
- interface Packet as SubPacket;
- interface UnicastNameFreeRouting;
- interface SplitControl as RadioControl;
- interface Queue<fe_queue_entry_t*> as SendQueue;
- interface Pool<fe_queue_entry_t> as QEntryPool;
- interface Pool<message_t> as MessagePool;
- interface Timer<TMilli> as RetxmitTimer;
- interface Cache<uint32_t> as SentCache;
- interface TreeRoutingInspect;
- interface PacketAcknowledgements;
- interface Random;
- interface RootControl;
- interface CollectionId[uint8_t client];
- interface AMPacket;
- interface CollectionDebug;
- interface LinkEstimator;
- interface Leds;
- }
-}
-implementation {
- /* Starts the retxmit timer with a random number masked by the given
- * mask and added to the given offset.
- */
- static void startRetxmitTimer(uint16_t mask, uint16_t offset);
-
- /* Keeps track of whether the routing layer is running; if not,
- * it will not send packets. */
- bool running = FALSE;
-
- /* Keeps track of whether the radio is on; no sense sending packets
- * if the radio is off. */
- bool radioOn = FALSE;
-
- /* Keeps track of whether an ack is pending on an outgoing packet,
- * so that the engine can work unreliably when the data-link layer
- * does not support acks. */
- bool ackPending = FALSE;
-
- /* Keeps track of whether the packet on the head of the queue
- * is being used, and control access to the data-link layer.*/
- bool sending = FALSE;
-
- /* Keep track of the last parent address we sent to, so that
- unacked packets to an old parent are not incorrectly attributed
- to a new parent. */
- am_addr_t lastParent;
-
- /* Network-level sequence number, so that receivers
- * can distinguish retransmissions from different packets. */
- uint8_t seqno;
-
- enum {
- CLIENT_COUNT = uniqueCount(UQ_COLLECTION_CLIENT)
- };
-
- /* Each sending client has its own reserved queue entry.
- If the client has a packet pending, its queue entry is in the
- queue, and its clientPtr is NULL. If the client is idle,
- its queue entry is pointed to by clientPtrs. */
-
- fe_queue_entry_t clientEntries[CLIENT_COUNT];
- fe_queue_entry_t* clientPtrs[CLIENT_COUNT];
-
- /* The loopback message is for when a collection roots calls
- Send.send. Since Send passes a pointer but Receive allows
- buffer swaps, the forwarder copies the sent packet into
- the loopbackMsgPtr and performs a buffer swap with it.
- See sendTask(). */
-
- message_t loopbackMsg;
- message_t* loopbackMsgPtr;
-
- command error_t Init.init() {
- int i;
- for (i = 0; i < CLIENT_COUNT; i++) {
- clientPtrs[i] = clientEntries + i;
- dbg("Forwarder", "clientPtrs[%hhu] = %p\n", i, clientPtrs[i]);
- }
- loopbackMsgPtr = &loopbackMsg;
- lastParent = call AMPacket.address();
- seqno = 0;
- return SUCCESS;
- }
-
- command error_t StdControl.start() {
- running = TRUE;
- return SUCCESS;
- }
-
- command error_t StdControl.stop() {
- running = FALSE;
- return SUCCESS;
- }
-
- /* sendTask is where the first phase of all send logic
- * exists (the second phase is in SubSend.sendDone()). */
- task void sendTask();
-
- /* ForwardingEngine keeps track of whether the underlying
- radio is powered on. If not, it enqueues packets;
- when it turns on, it then starts sending packets. */
- event void RadioControl.startDone(error_t err) {
- if (err == SUCCESS) {
- radioOn = TRUE;
- if (!call SendQueue.empty()) {
- post sendTask();
- }
- }
- }
-
- /*
- * If the ForwardingEngine has stopped sending packets because
- * these has been no route, then as soon as one is found, start
- * sending packets.
- */
- event void UnicastNameFreeRouting.routeFound() {
- post sendTask();
- }
-
- event void UnicastNameFreeRouting.noRoute() {
- // Depend on the sendTask to take care of this case;
- // if there is no route the component will just resume
- // operation on the routeFound event
- }
-
- event void RadioControl.stopDone(error_t err) {
- if (err == SUCCESS) {
- radioOn = FALSE;
- }
- }
-
- network_header_t* getHeader(message_t* m) {
- return (network_header_t*)call SubPacket.getPayload(m, NULL);
- }
-
- /*
- * The send call from a client. Return EBUSY if the client is busy
- * (clientPtrs is NULL), otherwise configure its queue entry
- * and put it in the send queue. If the ForwardingEngine is not
- * already sending packets (the RetxmitTimer isn't running), post
- * sendTask. It could be that the engine is running and sendTask
- * has already been posted, but the post-once semantics make this
- * not matter.
- */
- command error_t Send.send[uint8_t client](message_t* msg, uint8_t len) {
- network_header_t* hdr;
- fe_queue_entry_t *qe;
- dbg("Forwarder", "%s: sending packet from client %hhu: %x, len %hhu\n", __FUNCTION__, client, msg, len);
- if (!running) {return EOFF;}
- if (len > call Send.maxPayloadLength[client]()) {return ESIZE;}
-
- call Packet.setPayloadLength(msg, len);
- hdr = getHeader(msg);
- hdr->origin = TOS_NODE_ID;
- hdr->seqno = seqno++;
- hdr->collectid = call CollectionId.fetch[client]();
-
- if (clientPtrs[client] == NULL) {
- dbg("Forwarder", "%s: send failed as client is busy.\n", __FUNCTION__);
- return EBUSY;
- }
-
- qe = clientPtrs[client];
- qe->msg = msg;
- qe->client = client;
- qe->retries = MAX_RETRIES;
- dbg("Forwarder", "%s: queue entry for %hhu is %hhu deep\n", __FUNCTION__, client, call SendQueue.size());
- if (call SendQueue.enqueue(qe) == SUCCESS) {
- if (radioOn && !call RetxmitTimer.isRunning()) {
- post sendTask();
- }
- clientPtrs[client] = NULL;
- return SUCCESS;
- }
- else {
- dbg("Forwarder",
- "%s: send failed as packet could not be enqueued.\n",
- __FUNCTION__);
-
- // send a debug message to the uart
- call CollectionDebug.logEvent(NET_C_FE_SEND_QUEUE_FULL);
-
- // Return the pool entry, as it's not for me...
- return FAIL;
- }
- }
-
- command error_t Send.cancel[uint8_t client](message_t* msg) {
- // cancel not implemented. will require being able
- // to pull entries out of the queue.
- return FAIL;
- }
-
- command uint8_t Send.maxPayloadLength[uint8_t client]() {
- return call Packet.maxPayloadLength();
- }
-
- command void* Send.getPayload[uint8_t client](message_t* msg) {
- return call Packet.getPayload(msg, NULL);
- }
-
- /*
- * These is where all of the send logic is. When the ForwardingEngine
- * wants to send a packet, it posts this task. The send logic is
- * independent of whether it is a forwarded packet or a packet from
- * a send client.
- *
- * The task first checks that there is a packet to send and that
- * there is a valid route. It then marshals the relevant arguments
- * and prepares the packet for sending. If the node is a collection
- * root, it signals Receive with the loopback message. Otherwise,
- * it sets the packet to be acknowledged and sends it. It does not
- * remove the packet from the send queue: while sending, the
- * packet being sent is at the head of the queue; a packet is dequeued
- * in the sendDone handler, either due to retransmission failure
- * or to a successful send.
- */
-
- task void sendTask() {
- dbg("Forwarder", "%s: Trying to send a packet. Queue size is %hhu.\n", __FUNCTION__, call SendQueue.size());
- if (sending) {
- dbg("Forwarder", "%s: busy, don't send\n", __FUNCTION__);
- call CollectionDebug.logEvent(NET_C_FE_SEND_BUSY);
- return;
- }
- else if (call SendQueue.empty()) {
- dbg("Forwarder", "%s: queue empty, don't send\n", __FUNCTION__);
- call CollectionDebug.logEvent(NET_C_FE_SENDQUEUE_EMPTY);
- return;
- }
- else if (!call RootControl.isRoot() &&
- !call UnicastNameFreeRouting.hasRoute()) {
- dbg("Forwarder", "%s: no route, don't send, start retry timer\n", __FUNCTION__);
- call RetxmitTimer.startOneShot(10000);
-
- // send a debug message to the uart
- call CollectionDebug.logEvent(NET_C_FE_NO_ROUTE);
-
- return;
- }
- else {
- error_t subsendResult;
- fe_queue_entry_t* qe = call SendQueue.head();
- uint8_t payloadLen = call SubPacket.payloadLength(qe->msg);
- am_addr_t dest = call UnicastNameFreeRouting.nextHop();
- uint32_t msg_uid = call CollectionPacket.getPacketID(qe->msg);
- uint16_t gradient;
-
- if (call SentCache.lookup(msg_uid)) {
- call CollectionDebug.logEvent(NET_C_FE_DUPLICATE_CACHE_AT_SEND);
- call SendQueue.dequeue();
- post sendTask();
- return;
- }
- /* If our current parent is not the same as the last parent
- we sent do, then reset the count of unacked packets: don't
- penalize a new parent for the failures of a prior one.*/
- if (dest != lastParent) {
- qe->retries = MAX_RETRIES;
- lastParent = dest;
- }
-
- dbg("Forwarder", "Sending queue entry %p\n", qe);
- if (call RootControl.isRoot()) {
- collection_id_t collectid = getHeader(qe->msg)->collectid;
- memcpy(loopbackMsgPtr, qe->msg, sizeof(message_t));
- ackPending = FALSE;
-
- dbg("Forwarder", "%s: I'm a root, so loopback and signal receive.\n", __FUNCTION__);
- loopbackMsgPtr = signal Receive.receive[collectid](loopbackMsgPtr,
- call Packet.getPayload(loopbackMsgPtr, NULL),
- call Packet.payloadLength(loopbackMsgPtr));
- signal SubSend.sendDone(qe->msg, SUCCESS);
- return;
- }
-
- // Loop-detection functionality:
- if (call TreeRoutingInspect.getMetric(&gradient) != SUCCESS) {
- // If we have no metric, set our gradient conservatively so
- // that other nodes don't automatically drop our packets.
- gradient = 0;
- }
- call CollectionPacket.setGradient(qe->msg, gradient);
-
- ackPending = (call PacketAcknowledgements.requestAck(qe->msg) == SUCCESS);
-
- subsendResult = call SubSend.send(dest, qe->msg, payloadLen);
- if (subsendResult == SUCCESS) {
- // Successfully submitted to the data-link layer.
- sending = TRUE;
- dbg("Forwarder", "%s: subsend succeeded with %p.\n", __FUNCTION__, qe->msg);
- if (qe->client < CLIENT_COUNT) {
- dbg("Forwarder", "%s: client packet.\n", __FUNCTION__);
- }
- else {
- dbg("Forwarder", "%s: forwarded packet.\n", __FUNCTION__);
- }
- return;
- }
- else if (subsendResult == EOFF) {
- // The radio has been turned off underneath us. Assume that
- // this is for the best. When the radio is turned back on, we'll
- // handle a startDone event and resume sending.
- radioOn = FALSE;
- dbg("Forwarder", "%s: subsend failed from EOFF.\n", __FUNCTION__);
- // send a debug message to the uart
- call CollectionDebug.logEvent(NET_C_FE_SUBSEND_OFF);
- }
- else if (subsendResult == EBUSY) {
- // This shouldn't happen, as we sit on top of a client and
- // control our own output; it means we're trying to
- // double-send (bug). This means we expect a sendDone, so just
- // wait for that: when the sendDone comes in, // we'll try
- // sending this packet again.
- dbg("Forwarder", "%s: subsend failed from EBUSY.\n", __FUNCTION__);
- // send a debug message to the uart
- call CollectionDebug.logEvent(NET_C_FE_SUBSEND_BUSY);
- }
- else if (subsendResult == ESIZE) {
- dbg("Forwarder", "%s: subsend failed from ESIZE: truncate packet.\n", __FUNCTION__);
- call Packet.setPayloadLength(qe->msg, call Packet.maxPayloadLength());
- post sendTask();
- call CollectionDebug.logEvent(NET_C_FE_SUBSEND_SIZE);
- }
- }
- }
-
- void sendDoneBug() {
- // send a debug message to the uart
- call CollectionDebug.logEvent(NET_C_FE_BAD_SENDDONE);
- }
-
- /*
- * The second phase of a send operation; based on whether the transmission was
- * successful, the ForwardingEngine either stops sending or starts the
- * RetxmitTimer with an interval based on what has occured. If the send was
- * successful or the maximum number of retransmissions has been reached, then
- * the ForwardingEngine dequeues the current packet. If the packet is from a
- * client it signals Send.sendDone(); if it is a forwarded packet it returns
- * the packet and queue entry to their respective pools.
- *
- */
-
- event void SubSend.sendDone(message_t* msg, error_t error) {
- fe_queue_entry_t *qe = call SendQueue.head();
- dbg("Forwarder", "%s to %hu and %hhu\n", __FUNCTION__, call AMPacket.destination(msg), error);
- if (qe == NULL || qe->msg != msg) {
- dbg("Forwarder", "%s: BUG: not our packet (%p != %p)!\n", __FUNCTION__, msg, qe->msg);
- sendDoneBug(); // Not our packet, something is very wrong...
- return;
- }
- else if (error != SUCCESS) {
- // Immediate retransmission is the worst thing to do.
- dbg("Forwarder", "%s: send failed\n", __FUNCTION__);
- call CollectionDebug.logEventMsg(NET_C_FE_SENDDONE_FAIL,
- call CollectionPacket.getSequenceNumber(msg),
- call CollectionPacket.getOrigin(msg),
- call AMPacket.destination(msg));
- startRetxmitTimer(SENDDONE_FAIL_WINDOW, SENDDONE_FAIL_OFFSET);
- }
- else if (ackPending && !call PacketAcknowledgements.wasAcked(msg)) {
-
- call LinkEstimator.txNoAck(AMPacket.destination(msg));
-
- // AckPending is for case when DL cannot support acks.
- if (--qe->retries) {
- dbg("Forwarder", "%s: not acked\n", __FUNCTION__);
- call CollectionDebug.logEventMsg(NET_C_FE_SENDDONE_WAITACK,
- call CollectionPacket.getSequenceNumber(msg),
- call CollectionPacket.getOrigin(msg),
- call AMPacket.destination(msg));
- startRetxmitTimer(SENDDONE_NOACK_WINDOW, SENDDONE_NOACK_OFFSET);
- } else {
- //max retries, dropping packet
- if (qe->client < CLIENT_COUNT) {
- clientPtrs[qe->client] = qe;
- signal Send.sendDone[qe->client](msg, FAIL);
- call CollectionDebug.logEventMsg(NET_C_FE_SENDDONE_FAIL_ACK_SEND,
- call CollectionPacket.getSequenceNumber(msg),
- call CollectionPacket.getOrigin(msg),
- call AMPacket.destination(msg));
- } else {
- if (call MessagePool.put(qe->msg) != SUCCESS)
- call CollectionDebug.logEvent(NET_C_FE_PUT_MSGPOOL_ERR);
- if (call QEntryPool.put(qe) != SUCCESS)
- call CollectionDebug.logEvent(NET_C_FE_PUT_QEPOOL_ERR);
- call CollectionDebug.logEventMsg(NET_C_FE_SENDDONE_FAIL_ACK_FWD,
- call CollectionPacket.getSequenceNumber(msg),
- call CollectionPacket.getOrigin(msg),
- call AMPacket.destination(msg));
- }
- call SendQueue.dequeue();
- sending = FALSE;
- startRetxmitTimer(SENDDONE_OK_WINDOW, SENDDONE_OK_OFFSET);
- }
- }
- else if (qe->client < CLIENT_COUNT) {
- network_header_t* hdr;
- uint8_t client = qe->client;
- dbg("Forwarder", "%s: our packet for client %hhu, remove %p from queue\n",
- __FUNCTION__, client, qe);
- call CollectionDebug.logEventMsg(NET_C_FE_SENT_MSG,
- call CollectionPacket.getSequenceNumber(msg),
- call CollectionPacket.getOrigin(msg),
- call AMPacket.destination(msg));
- call LinkEstimator.txAck(AMPacket.destination(msg));
- clientPtrs[client] = qe;
- hdr = getHeader(qe->msg);
- call SendQueue.dequeue();
- signal Send.sendDone[client](msg, SUCCESS);
- sending = FALSE;
- startRetxmitTimer(SENDDONE_OK_WINDOW, SENDDONE_OK_OFFSET);
- }
- else if (call MessagePool.size() < call MessagePool.maxSize()) {
- // A successfully forwarded packet.
- dbg("Forwarder,Route", "%s: successfully forwarded packet (client: %hhu), message pool is %hhu/%hhu.\n", __FUNCTION__, qe->client, call MessagePool.size(), call MessagePool.maxSize());
-
- call LinkEstimator.txAck(AMPacket.destination(msg));
-
- call CollectionDebug.logEventMsg(NET_C_FE_FWD_MSG,
- call CollectionPacket.getSequenceNumber(msg),
- call CollectionPacket.getOrigin(msg),
- call AMPacket.destination(msg));
- call SentCache.insert(call CollectionPacket.getPacketID(qe->msg));
- call SendQueue.dequeue();
- if (call MessagePool.put(qe->msg) != SUCCESS)
- call CollectionDebug.logEvent(NET_C_FE_PUT_MSGPOOL_ERR);
- if (call QEntryPool.put(qe) != SUCCESS)
- call CollectionDebug.logEvent(NET_C_FE_PUT_QEPOOL_ERR);
- sending = FALSE;
- startRetxmitTimer(SENDDONE_OK_WINDOW, SENDDONE_OK_OFFSET);
- call Leds.led2Toggle();
- }
- else {
- dbg("Forwarder", "%s: BUG: we have a pool entry, but the pool is full, client is %hhu.\n", __FUNCTION__, qe->client);
- sendDoneBug(); // It's a forwarded packet, but there's no room the pool;
- // someone has double-stored a pointer somewhere and we have nowhere
- // to put this, so we have to leak it...
- }
- }
-
- /*
- * Function for preparing a packet for forwarding. Performs
- * a buffer swap from the message pool. If there are no free
- * message in the pool, it returns the passed message and does not
- * put it on the send queue.
- */
- message_t* forward(message_t* m) {
- if (call MessagePool.empty()) {
- dbg("Route", "%s cannot forward, message pool empty.\n", __FUNCTION__);
- // send a debug message to the uart
- call CollectionDebug.logEvent(NET_C_FE_MSG_POOL_EMPTY);
- }
- else if (call QEntryPool.empty()) {
- dbg("Route", "%s cannot forward, queue entry pool empty.\n",
- __FUNCTION__);
- // send a debug message to the uart
- call CollectionDebug.logEvent(NET_C_FE_QENTRY_POOL_EMPTY);
- }
- else {
- message_t* newMsg;
- fe_queue_entry_t *qe;
- uint16_t gradient;
-
- qe = call QEntryPool.get();
- if (qe == NULL) {
- call CollectionDebug.logEvent(NET_C_FE_GET_MSGPOOL_ERR);
- return m;
- }
-
- newMsg = call MessagePool.get();
- if (newMsg == NULL) {
- call CollectionDebug.logEvent(NET_C_FE_GET_QEPOOL_ERR);
- return m;
- }
-
- memset(newMsg, 0, sizeof(message_t));
- memset(m->metadata, 0, sizeof(message_metadata_t));
-
- qe->msg = m;
- qe->client = 0xff;
- qe->retries = MAX_RETRIES;
-
-
- if (call SendQueue.enqueue(qe) == SUCCESS) {
- dbg("Forwarder,Route", "%s forwarding packet %p with queue size %hhu\n", __FUNCTION__, m, call SendQueue.size());
- // Loop-detection code:
- if (call TreeRoutingInspect.getMetric(&gradient) == SUCCESS) {
- // We only check for loops if we know our own metric
- if (call CollectionPacket.getGradient(m) < gradient) {
- // The incoming packet's metric (gradient) is less than our
- // own gradient. Trigger a route update and backoff.
- call TreeRoutingInspect.triggerRouteUpdate();
- startRetxmitTimer(LOOPY_WINDOW, LOOPY_OFFSET);
- call CollectionDebug.logEventMsg(NET_C_FE_LOOP_DETECTED,
- call CollectionPacket.getSequenceNumber(m),
- call CollectionPacket.getOrigin(m),
- call AMPacket.destination(m));
- }
- }
-
- if (!call RetxmitTimer.isRunning()) {
- // sendTask is only immediately posted if we don't detect a
- // loop.
- post sendTask();
- }
-
- // Successful function exit point:
- return newMsg;
- } else {
- // There was a problem enqueuing to the send queue.
- if (call MessagePool.put(newMsg) != SUCCESS)
- call CollectionDebug.logEvent(NET_C_FE_PUT_MSGPOOL_ERR);
- if (call QEntryPool.put(qe) != SUCCESS)
- call CollectionDebug.logEvent(NET_C_FE_PUT_QEPOOL_ERR);
- }
- }
-
- // Resource acquisition problem. Send a debug message to the
- // uart.
- call CollectionDebug.logEvent(NET_C_FE_SEND_QUEUE_FULL);
-
- // We'll have to drop the packet on the floor: not enough
- // resources available to forward.
- return m;
- }
-
- /*
- * Received a message to forward. Check whether it is a duplicate by
- * checking the packets currently in the queue as well as the
- * send history cache (in case we recently forwarded this packet).
- * The cache is important as nodes immediately forward packets
- * but wait a period before retransmitting after an ack failure.
- * If this node is a root, signal receive.
- */
- event message_t*
- SubReceive.receive(message_t* msg, void* payload, uint8_t len) {
- network_header_t* hdr = getHeader(msg);
- uint8_t netlen;
- collection_id_t collectid;
-
- uint32_t msg_uid;
- bool duplicate = FALSE;
- fe_queue_entry_t* qe;
- uint8_t i;
-
-
- msg_uid = call CollectionPacket.getPacketID(msg);
- collectid = hdr->collectid;
-
- call CollectionDebug.logEventMsg(NET_C_FE_RCV_MSG,
- call CollectionPacket.getSequenceNumber(msg),
- call CollectionPacket.getOrigin(msg),
- call AMPacket.destination(msg));
- if (len > call SubSend.maxPayloadLength()) {
- return msg;
- }
-
- //See if we remember having seen this packet
- //We look in the sent cache ...
- if (call SentCache.lookup(msg_uid)) {
- call CollectionDebug.logEvent(NET_C_FE_DUPLICATE_CACHE);
- return msg;
- }
- //... and in the queue for duplicates
- if (call SendQueue.size() > 0) {
- for (i = call SendQueue.size(); --i;) {
- qe = call SendQueue.element(i);
- if (call CollectionPacket.getPacketID(qe->msg) == msg_uid) {
- duplicate = TRUE;
- break;
- }
- }
- }
-
- if (duplicate) {
- call CollectionDebug.logEvent(NET_C_FE_DUPLICATE_QUEUE);
- return msg;
- }
-
- // If I'm the root, signal receive.
- else if (call RootControl.isRoot())
- return signal Receive.receive[collectid](msg,
- call Packet.getPayload(msg, &netlen),
- call Packet.payloadLength(msg));
- // I'm on the routing path and Intercept indicates that I
- // should not forward the packet.
- else if (!signal Intercept.forward[collectid](msg,
- call Packet.getPayload(msg, &netlen),
- call Packet.payloadLength(msg)))
- return msg;
- else {
- dbg("Route", "Forwarding packet from %hu.\n", hdr->origin);
- return forward(msg);
- }
- }
-
- command void*
- Receive.getPayload[collection_id_t id](message_t* msg, uint8_t* len) {
- return call Packet.getPayload(msg, NULL);
- }
-
- command uint8_t
- Receive.payloadLength[collection_id_t id](message_t *msg) {
- return call Packet.payloadLength(msg);
- }
-
- command void *
- Snoop.getPayload[collection_id_t id](message_t *msg, uint8_t *len) {
- return call Packet.getPayload(msg, NULL);
- }
-
- command uint8_t Snoop.payloadLength[collection_id_t id](message_t *msg) {
- return call Packet.payloadLength(msg);
- }
-
- event message_t*
- SubSnoop.receive(message_t* msg, void *payload, uint8_t len) {
- network_header_t* hdr = getHeader(msg);
- return signal Snoop.receive[hdr->collectid] (msg, (void *)(hdr + 1),
- len - sizeof(network_header_t));
- }
-
- event void RetxmitTimer.fired() {
- sending = FALSE;
- post sendTask();
- }
-
- command void Packet.clear(message_t* msg) {
- call SubPacket.clear(msg);
- }
-
- command uint8_t Packet.payloadLength(message_t* msg) {
- return call SubPacket.payloadLength(msg) - sizeof(network_header_t);
- }
-
- command void Packet.setPayloadLength(message_t* msg, uint8_t len) {
- call SubPacket.setPayloadLength(msg, len + sizeof(network_header_t));
- }
-
- command uint8_t Packet.maxPayloadLength() {
- return call SubPacket.maxPayloadLength() - sizeof(network_header_t);
- }
-
- command void* Packet.getPayload(message_t* msg, uint8_t* len) {
- uint8_t* payload = call SubPacket.getPayload(msg, len);
- if (len != NULL) {
- *len -= sizeof(network_header_t);
- }
- return payload + sizeof(network_header_t);
- }
-
- command am_addr_t CollectionPacket.getOrigin(message_t* msg) {
- return getHeader(msg)->origin;
- }
-
- command void CollectionPacket.setOrigin(message_t* msg, am_addr_t addr) {
- getHeader(msg)->origin = addr;
- }
-
- command uint8_t CollectionPacket.getCollectionID(message_t* msg) {
- return getHeader(msg)->collectid;
- }
-
- command void CollectionPacket.setCollectionID(message_t* msg, uint8_t id) {
- getHeader(msg)->collectid = id;
- }
-
- command uint8_t CollectionPacket.getControl(message_t* msg) {
- return getHeader(msg)->control;
- }
-
- command void CollectionPacket.setControl(message_t* msg, uint8_t control) {
- getHeader(msg)->control = control;
- }
-
- command uint16_t CollectionPacket.getGradient(message_t* msg) {
- return getHeader(msg)->gradient;
- }
-
- command void CollectionPacket.setGradient(message_t* msg, uint16_t gradient) {
- getHeader(msg)->gradient = gradient;
- }
-
- command uint8_t CollectionPacket.getSequenceNumber(message_t* msg) {
- return getHeader(msg)->seqno;
- }
-
- command void CollectionPacket.setSequenceNumber(message_t* msg, uint8_t _seqno) {
- getHeader(msg)->seqno = _seqno;
- }
-
- command uint32_t CollectionPacket.getPacketID(message_t* msg) {
- return ((uint32_t)(getHeader(msg)->origin) << 16) | (uint32_t)(getHeader(msg)->seqno);
- }
-
-
- default event void
- Send.sendDone[uint8_t client](message_t *msg, error_t error) {
- }
-
- default event bool
- Intercept.forward[collection_id_t collectid](message_t* msg, void* payload,
- uint16_t len) {
- return TRUE;
- }
-
- default event message_t *
- Receive.receive[collection_id_t collectid](message_t *msg, void *payload,
- uint8_t len) {
- return msg;
- }
-
- default event message_t *
- Snoop.receive[collection_id_t collectid](message_t *msg, void *payload,
- uint8_t len) {
- return msg;
- }
-
- default command collection_id_t CollectionId.fetch[uint8_t client]() {
- return 0;
- }
-
- static void startRetxmitTimer(uint16_t mask, uint16_t offset) {
- uint16_t r = call Random.rand16();
- r &= mask;
- r += offset;
- call RetxmitTimer.startOneShot(r);
- dbg("Forwarder", "started rexmit timer in %hu ms\n", r);
- }
-
- event void LinkEstimator.evicted(am_addr_t neighbor) {
- }
-
- /* Default implementations for CollectionDebug calls.
- * These allow CollectionDebug not to be wired to anything if debugging
- * is not desired. */
-
- default command error_t CollectionDebug.logEvent(uint8_t type) {
- return SUCCESS;
- }
- default command error_t CollectionDebug.logEventSimple(uint8_t type, uint16_t arg) {
- return SUCCESS;
- }
- default command error_t CollectionDebug.logEventDbg(uint8_t type, uint16_t arg1, uint16_t arg2, uint16_t arg3) {
- return SUCCESS;
- }
- default command error_t CollectionDebug.logEventMsg(uint8_t type, uint16_t msg, am_addr_t origin, am_addr_t node) {
- return SUCCESS;
- }
- default command error_t CollectionDebug.logEventRoute(uint8_t type, am_addr_t parent, uint8_t hopcount, uint16_t metric) {
- return SUCCESS;
- }
-
-}
+++ /dev/null
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-interface NeighborTable {
- /* Signals to users that the neighbor has been evicted from the table */
- event void evicted(uint16_t neighbor)
-}
-
+++ /dev/null
-$Id$
-This is pre-alpha stage, only intended for discussion of the structure.
-The current state is that the configurations and module skeletons are in place,
-but with no actual executing code in the modules.
-
-The basic structure is the following:
-
-
-CollectionC is the visible interface to external users.
-The data plane (the send and receive paths exported) are through the ForwardingEngine, the only external interface to the routing engine is currently RootControl.
-
-The link estimation is done through a third module, the LinkEstimator.
-It provides the latest link estimate for a given neighbor.
-
-TreeRoutingEngine sends and receives control messages to form the tree. These are independent of the data plane messages.
-
-Both TreeRoutingEngine and ForwardingEngine have their send and receive paths wired through the LinkEstimator. The initial idea is to have almost pass-through components LinkEstimatorAMSenderC and LinkEstimatorAMReceiverC such that the link estimator can intercept all packets to and from both components.
-
-
+++ /dev/null
-/* $Id$ */
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/** Controls whether the current node is a root of the tree
- * @author Rodrigo Fonseca
- * @date $Date$
- */
-
-interface RootControl {
- command error_t setRoot();
- command error_t unsetRoot();
- command bool isRoot();
-}
+++ /dev/null
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/** Controls for the routing engine.
- * @author Rodrigo Fonseca
- * @date $Date$
- */
-
-
-interface RoutingEngineControl {
- /** Initialize the routing header of the given message. This will write
- * to the routing header assuming the message is originating at the
- * local node. This includes setting the destination address. */
- command error_t initializeRH(message_t *msg, uint8_t tree_id);
- /** Get the size in bytes of the routing engine header */
- command uint8_t getHeaderSize();
-}
-
+++ /dev/null
-#ifndef TREE_COLLECTION_H
-#define TREE_COLLECTION_H
-
-/*
- * "Copyright (c) 2006 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-
-#define UQ_COLLECTION_CLIENT "CollectionSenderC.Send"
-
-
-#endif
+++ /dev/null
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-/*
- * Copyright (c) 2006 Stanford University.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * - Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * - Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the
- * distribution.
- * - Neither the name of the Stanford University nor the names of
- * its contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD
- * UNIVERSITY OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
- * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
- * OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include "Collection.h"
-#include "TreeCollection.h"
-#include "ForwardingEngine.h"
-
-/**
- * A data collection service that uses a tree routing protocol
- * to deliver data to collection roots, following TEP 119.
- *
- * @author Rodrigo Fonseca
- * @author Omprakash Gnawali
- * @author Kyle Jamieson
- * @author Philip Levis
- */
-
-
-configuration TreeCollectionC {
- provides {
- interface StdControl;
- interface Send[uint8_t client];
- interface Receive[collection_id_t id];
- interface Receive as Snoop[collection_id_t];
- interface Intercept[collection_id_t id];
- interface RootControl;
- interface Packet;
- interface CollectionPacket;
- interface TreeRoutingInspect;
- }
-
- uses {
- interface CollectionId[uint8_t client];
- interface CollectionDebug;
- }
-}
-
-implementation {
- enum {
- CLIENT_COUNT = uniqueCount(UQ_COLLECTION_CLIENT),
- FORWARD_COUNT = 5,
- TREE_ROUTING_TABLE_SIZE = 10,
- QUEUE_SIZE = CLIENT_COUNT + FORWARD_COUNT,
- CACHE_SIZE = 4,
- };
-
- components ActiveMessageC;
- components new ForwardingEngineP() as Forwarder;
- components MainC, LedsC;
-
- Send = Forwarder;
- StdControl = Forwarder;
- Receive = Forwarder.Receive;
- Snoop = Forwarder.Snoop;
- Intercept = Forwarder;
- Packet = Forwarder;
- CollectionId = Forwarder;
- CollectionPacket = Forwarder;
-
- components new PoolC(message_t, FORWARD_COUNT) as MessagePoolP;
- components new PoolC(fe_queue_entry_t, FORWARD_COUNT) as QEntryPoolP;
- Forwarder.QEntryPool -> QEntryPoolP;
- Forwarder.MessagePool -> MessagePoolP;
-
- components new QueueC(fe_queue_entry_t*, QUEUE_SIZE) as SendQueueP;
- Forwarder.SendQueue -> SendQueueP;
-
- components new LruIntCacheC(uint32_t, CACHE_SIZE) as SentCacheP;
- Forwarder.SentCache -> SentCacheP;
-
- components new TimerMilliC() as RoutingBeaconTimer;
- components LinkEstimatorP as Estimator;
-
- components new AMSenderC(AM_COLLECTION_DATA);
- components new AMReceiverC(AM_COLLECTION_DATA);
- components new AMSnooperC(AM_COLLECTION_DATA);
-
- components new TreeRoutingEngineP(TREE_ROUTING_TABLE_SIZE) as Router;
- StdControl = Router;
- StdControl = Estimator;
- RootControl = Router;
- MainC.SoftwareInit -> Router;
- Router.BeaconSend -> Estimator.Send;
- Router.BeaconReceive -> Estimator.Receive;
- Router.LinkEstimator -> Estimator.LinkEstimator;
- Router.LinkSrcPacket -> Estimator.LinkSrcPacket;
- Router.AMPacket -> ActiveMessageC;
- Router.RadioControl -> ActiveMessageC;
- Router.BeaconTimer -> RoutingBeaconTimer;
- Router.CollectionDebug = CollectionDebug;
- Forwarder.CollectionDebug = CollectionDebug;
- Forwarder.TreeRoutingInspect -> Router;
- TreeRoutingInspect = Router;
-
- components new TimerMilliC() as RetxmitTimer;
- Forwarder.RetxmitTimer -> RetxmitTimer;
-
- components RandomC;
- Router.Random -> RandomC;
- Forwarder.Random -> RandomC;
-
- MainC.SoftwareInit -> Forwarder;
- Forwarder.SubSend -> AMSenderC;
- Forwarder.SubReceive -> AMReceiverC;
- Forwarder.SubSnoop -> AMSnooperC;
- Forwarder.SubPacket -> AMSenderC;
- Forwarder.RootControl -> Router;
- Forwarder.UnicastNameFreeRouting -> Router.Routing;
- Forwarder.RadioControl -> ActiveMessageC;
- Forwarder.PacketAcknowledgements -> AMSenderC.Acks;
- Forwarder.AMPacket -> AMSenderC;
- Forwarder.Leds -> LedsC;
-
- components new AMSenderC(AM_COLLECTION_CONTROL) as SendControl;
- components new AMReceiverC(AM_COLLECTION_CONTROL) as ReceiveControl;
- components new AMSenderC(AM_LINKEST) as SendLinkEst;
- components new AMReceiverC(AM_LINKEST) as ReceiveLinkEst;
- components new TimerMilliC() as EstimatorTimer;
-
- Estimator.AMSend -> SendControl;
- Estimator.SubReceive -> ReceiveControl;
- Estimator.AMSendLinkEst -> SendLinkEst;
- Estimator.ReceiveLinkEst -> ReceiveLinkEst;
- Estimator.SubPacket -> SendControl;
- Estimator.SubAMPacket -> SendControl;
- Estimator.Timer -> EstimatorTimer;
- MainC.SoftwareInit -> Estimator;
-}
+++ /dev/null
-#ifndef _TREE_ROUTING_H
-#define _TREE_ROUTING_H
-
-enum {
- AM_TREE_ROUTING_CONTROL = 0xCE,
- BEACON_INTERVAL = 8192,
- INVALID_ADDR = TOS_BCAST_ADDR,
- ETX_THRESHOLD = 50, // link quality=20% -> ETX=5 -> Metric=50
- PARENT_SWITCH_THRESHOLD = 15,
- MAX_METRIC = 0xFFFF,
-};
-
-
-typedef struct {
- am_addr_t parent;
- uint8_t hopcount;
- uint16_t metric;
-} route_info_t;
-
-typedef struct {
- am_addr_t neighbor;
- route_info_t info;
-} routing_table_entry;
-
-inline void routeInfoInit(route_info_t *ri) {
- ri->parent = INVALID_ADDR;
- ri->hopcount = 0;
- ri->metric = 0;
-}
-
-typedef nx_struct beacon_msg_t {
- nx_am_addr_t parent;
- nx_uint8_t hopcount;
- nx_uint16_t metric;
-} beacon_msg_t;
-
-#endif
+++ /dev/null
-Miscelaneous notes on the TreeRoutingP module details.
-Rodrigo Fonseca
-
-The RoutingTable is a table with information about *routing* information of neighbors: their hopcount, quality, etc. It is used to periodically choose the best route, and to find backup routes.
-
-It is strictly a subset of the LinkEstimator table, meaning that no node that is not in the link estimator table is in the routing table. However, not all neighbors will be here. The policy for managing this table is a generalization of the regular tree routing: we keep the K best paths to *a* root.
-
-
-Timer has period P jittered with +- P/2
-
-RouteInfo:
- metric is a 16 bit number that measures quality to the root. See below.
- hopcount
- parent: a link neighbor address (next hop)
-
-Root:
- rootControl interface.
- if isRoot()
- parent = self
- hopcount = 0
- metric = 0
- has_route = true
-
-
-Update task updates the parent before sending out beacon.
-This is not done right when you receive a beacon, because the qualities may change right before you send. This is a policy question, anyway, and can be changed easily.
-
-Quality is converted to a 'path metric' by evaluateMetric().
-Path metric is ADDITIVE along a path, and smaller metric is always better.
-Currently, it is 10*ETX along the path.
+++ /dev/null
-#include <Timer.h>
-#include <TreeRouting.h>
-#include <CollectionDebugMsg.h>
-/* $Id$ */
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/**
- * The TreeRoutingEngine is responsible for computing the routes for
- * collection. It builds a set of trees rooted at specific nodes (roots) and
- * maintains these trees using information provided by the link estimator on
- * the quality of one hop links.
- *
- * <p>Each node is part of only one tree at any given time, but there is no
- * difference from the node's point of view of which tree it is part. In other
- * words, a message is sent towards <i>a</i> root, but which one is not
- * specified. It is assumed that the roots will work together to have all data
- * aggregated later if need be. The tree routing engine's responsibility is
- * for each node to find the path with the least number of transmissions to
- * any one root.
- *
- * <p>The tree is proactively maintained by periodic beacons sent by each
- * node. These beacons are jittered in time to prevent synchronizations in the
- * network. All nodes maintain the same <i>average</i> beacon sending rate
- * (defined by BEACON_INTERVAL +- 50%). The beacon contains the node's parent,
- * the current hopcount, and the cumulative path quality metric. The metric is
- * defined as the parent's metric plus the bidirectional quality of the link
- * between the current node and its parent. The metric represents the
- * expected number of transmissions along the path to the root, and is 0 by
- * definition at the root.
- *
- * <p>Every time a node receives an update from a neighbor it records the
- * information if the node is part of the neighbor table. The neighbor table
- * keeps the best candidates for being parents i.e., the nodes with the best
- * path metric. The neighbor table does not store the full path metric,
- * though. It stores the parent's path metric, and the link quality to the
- * parent is only added when the information is needed: (i) when choosing a
- * parent and (ii) when choosing a route. The nodes in the neighbor table are
- * a subset of the nodes in the link estimator table, as a node is not
- * admitted in the neighbor table with an estimate of infinity.
- *
- * <p>There are two uses for the neighbor table, as mentioned above. The first
- * one is to select a parent. The parent is just the neighbor with the best
- * path metric. It serves to define the node's own path metric and hopcount,
- * and the set of child-parent links is what defines the tree. In a sense the
- * tree is defined to form a coherent propagation substrate for the path
- * metrics. The parent is (re)-selected periodically, immediately before a
- * node sends its own beacon, in the updateRouteTask.
- *
- * <p>The second use is to actually choose a next hop towards any root at
- * message forwarding time. This need not be the current parent, even though
- * it is currently implemented as such.
- *
- * <p>The operation of the routing engine has two main tasks and one main
- * event: updateRouteTask is called periodically and chooses a new parent;
- * sendBeaconTask broadcasts the current route information to the neighbors.
- * The main event is the receiving of a neighbor's beacon, which updates the
- * neighbor table.
- *
- * <p> The interface with the ForwardingEngine occurs through the nextHop()
- * call.
- *
- * <p> Any node can become a root, and routed messages from a subset of the
- * network will be routed towards it. The RootControl interface allows
- * setting, unsetting, and querying the root state of a node. By convention,
- * when a node is root its hopcount and metric are 0, and the parent is
- * itself. A root always has a valid route, to itself.
- */
-
- /*
- * @author Rodrigo Fonseca
- * Acknowledgment: based on MintRoute, MultiHopLQI, BVR tree construction, Berkeley's MTree
- *
- * @date $Date$
- * @see Net2-WG
- */
-
-generic module TreeRoutingEngineP(uint8_t routingTableSize) {
- provides {
- interface UnicastNameFreeRouting as Routing;
- interface RootControl;
- interface TreeRoutingInspect;
- interface StdControl;
- interface Init;
- }
- uses {
- interface AMSend as BeaconSend;
- interface Receive as BeaconReceive;
- interface LinkEstimator;
- interface AMPacket;
- interface LinkSrcPacket;
- interface SplitControl as RadioControl;
- interface Timer<TMilli> as BeaconTimer;
- interface Random;
- interface CollectionDebug;
- }
-}
-
-
-implementation {
-
-
- /* Keeps track of whether the radio is on. No sense updating or sending
- * beacons if radio is off */
- bool radioOn = FALSE;
- /* Controls whether the node's periodic timer will fire. The node will not
- * send any beacon, and will not update the route. Start and stop control this. */
- bool running = FALSE;
- /* Guards the beacon buffer: only one beacon being sent at a time */
- bool sending = FALSE;
-
- /* Tells updateNeighbor that the parent was just evicted.*/
- bool justEvicted = FALSE;
-
- route_info_t routeInfo;
- bool state_is_root;
- am_addr_t my_ll_addr;
-
- message_t beaconMsgBuffer;
- beacon_msg_t* beaconMsg;
-
- /* routing table -- routing info about neighbors */
- routing_table_entry routingTable[routingTableSize];
- uint8_t routingTableActive;
-
- /* statistics */
- uint32_t parentChanges;
- /* end statistics */
-
- // forward declarations
- void routingTableInit();
- uint8_t routingTableFind(am_addr_t);
- error_t routingTableUpdateEntry(am_addr_t, am_addr_t , uint8_t, uint16_t);
- error_t routingTableEvict(am_addr_t neighbor);
-
-
- command error_t Init.init() {
- uint8_t maxLength;
- radioOn = FALSE;
- running = FALSE;
- parentChanges = 0;
- state_is_root = 0;
- routeInfoInit(&routeInfo);
- routingTableInit();
- my_ll_addr = call AMPacket.address();
- beaconMsg = call BeaconSend.getPayload(&beaconMsgBuffer);
- maxLength = call BeaconSend.maxPayloadLength();
- dbg("TreeRoutingCtl","TreeRouting initialized. (used payload:%d max payload:%d!\n",
- sizeof(beaconMsg), maxLength);
- return SUCCESS;
- }
-
- command error_t StdControl.start() {
- //start will (re)start the sending of messages
- uint16_t nextInt;
- if (!running) {
- running = TRUE;
- nextInt = call Random.rand16() % BEACON_INTERVAL;
- nextInt += BEACON_INTERVAL >> 1;
- call BeaconTimer.startOneShot(nextInt);
- dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
- }
- return SUCCESS;
- }
-
- command error_t StdControl.stop() {
- running = FALSE;
- dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
- return SUCCESS;
- }
-
- event void RadioControl.startDone(error_t error) {
- radioOn = TRUE;
- dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
- if (running) {
- uint16_t nextInt;
- nextInt = call Random.rand16() % BEACON_INTERVAL;
- nextInt += BEACON_INTERVAL >> 1;
- call BeaconTimer.startOneShot(nextInt);
- }
- }
-
- event void RadioControl.stopDone(error_t error) {
- radioOn = FALSE;
- dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
- }
-
- /* Is this quality measure better than the minimum threshold? */
- // Implemented assuming quality is EETX
- bool passLinkMetricThreshold(uint16_t metric) {
- return (metric < ETX_THRESHOLD);
- }
-
- /* Converts the output of the link estimator to path metric
- * units, that can be *added* to form path metric measures */
- uint16_t evaluateMetric(uint8_t quality) {
- //dbg("TreeRouting","%s %d -> %d\n",__FUNCTION__,quality, quality+10);
- return (quality + 10);
- }
-
- /* updates the routing information, using the info that has been received
- * from neighbor beacons. Two things can cause this info to change:
- * neighbor beacons, changes in link estimates, including neighbor eviction */
- task void updateRouteTask() {
- uint8_t i;
- routing_table_entry* entry;
- routing_table_entry* best;
- uint16_t minMetric;
- uint16_t currentMetric;
- uint16_t linkMetric, pathMetric;
-
- if (state_is_root)
- return;
-
- best = NULL;
- /* Minimum metric found among neighbors, initially infinity */
- minMetric = MAX_METRIC;
- /* Metric through current parent, initially infinity */
- currentMetric = MAX_METRIC;
-
- dbg("TreeRouting","%s\n",__FUNCTION__);
-
- /* Find best path in table, other than our current */
- for (i = 0; i < routingTableActive; i++) {
- entry = &routingTable[i];
-
- // Avoid bad entries and 1-hop loops
- if (entry->info.parent == INVALID_ADDR || entry->info.parent == my_ll_addr) {
- dbg("TreeRouting",
- "routingTable[%d]: neighbor: [id: %d parent: %d hopcount: %d metric: NO ROUTE]\n",
- i, entry->neighbor, entry->info.parent, entry->info.hopcount);
- continue;
- }
- if (TOS_NODE_ID > 10 && entry->neighbor == 0) {
- continue;
- }
- /* Compute this neighbor's path metric */
- linkMetric = evaluateMetric(call LinkEstimator.getLinkQuality(entry->neighbor));
- dbg("TreeRouting",
- "routingTable[%d]: neighbor: [id: %d parent: %d hopcount: %d metric: %d]\n",
- i, entry->neighbor, entry->info.parent, entry->info.hopcount, linkMetric);
- pathMetric = linkMetric + entry->info.metric;
- /* Operations specific to the current parent */
- if (entry->neighbor == routeInfo.parent) {
- dbg("TreeRouting", " already parent.\n");
- currentMetric = pathMetric;
- /* update routeInfo with parent's current info */
- atomic {
- routeInfo.metric = entry->info.metric;
- routeInfo.hopcount = entry->info.hopcount + 1;
- }
- continue;
- }
- /* Ignore links that are bad */
- if (!passLinkMetricThreshold(linkMetric)) {
- dbg("TreeRouting", " did not pass threshold.\n");
- continue;
- }
-
- if (pathMetric < minMetric) {
- minMetric = pathMetric;
- best = entry;
- }
- }
-
- /* Now choose between the current parent and the best neighbor */
- if (minMetric != MAX_METRIC) {
- if (currentMetric == MAX_METRIC ||
- minMetric + PARENT_SWITCH_THRESHOLD < currentMetric) {
- // routeInfo.metric will not store the composed metric.
- // since the linkMetric may change, we will compose whenever
- // we need it: i. when choosing a parent (here);
- // ii. when choosing a next hop
- parentChanges++;
- dbg("TreeRouting","Changed parent. from %d to %d\n", routeInfo.parent, best->neighbor);
- call CollectionDebug.logEventRoute(NET_C_TREE_NEW_PARENT, best->neighbor, best->info.hopcount + 1, best->info.metric);
- call LinkEstimator.unpinNeighbor(routeInfo.parent);
- call LinkEstimator.pinNeighbor(best->neighbor);
- call LinkEstimator.clearDLQ(best->neighbor);
- atomic {
- routeInfo.parent = best->neighbor;
- routeInfo.metric = best->info.metric;
- routeInfo.hopcount = best->info.hopcount + 1;
- }
- }
- }
-
- /* Finally, tell people what happened: */
- /* We can only loose a route to a parent if it has been evicted. If it hasn't
- * been just evicted then we already did not have a route */
- if (justEvicted && routeInfo.parent == INVALID_ADDR)
- signal Routing.noRoute();
- /* On the other hand, if we didn't have a parent (no currentMetric) and now we
- * do, then we signal route found. The exception is if we just evicted the
- * parent and immediately found a replacement route: we don't signal in this
- * case */
- else if (!justEvicted &&
- currentMetric == MAX_METRIC &&
- minMetric != MAX_METRIC)
- signal Routing.routeFound();
- justEvicted = FALSE;
- }
-
-
-
- /* send a beacon advertising this node's routeInfo */
- // only posted if running and radioOn
- task void sendBeaconTask() {
- error_t eval;
- if (sending) {
- return;
- }
- beaconMsg->parent = routeInfo.parent;
- beaconMsg->hopcount = routeInfo.hopcount;
-
- if (state_is_root || routeInfo.parent == INVALID_ADDR) {
- beaconMsg->metric = routeInfo.metric;
- } else {
- beaconMsg->metric = routeInfo.metric +
- evaluateMetric(call LinkEstimator.getLinkQuality(routeInfo.parent));
- }
-
- dbg("TreeRouting", "%s parent: %d hopcount: %d metric: %d\n",
- __FUNCTION__,
- beaconMsg->parent,
- beaconMsg->hopcount,
- beaconMsg->metric);
- call CollectionDebug.logEventRoute(NET_C_TREE_SENT_BEACON, beaconMsg->parent, beaconMsg->hopcount, beaconMsg->metric);
-
- eval = call BeaconSend.send(AM_BROADCAST_ADDR,
- &beaconMsgBuffer,
- sizeof(beacon_msg_t));
- if (eval == SUCCESS) {
- sending = TRUE;
- } else if (eval == EOFF) {
- radioOn = FALSE;
- dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
- }
- }
-
- event void BeaconSend.sendDone(message_t* msg, error_t error) {
- if ((msg != &beaconMsgBuffer) || !sending) {
- //something smells bad around here
- return;
- }
- sending = FALSE;
- }
-
-
- event void BeaconTimer.fired() {
- if (radioOn && running) {
- // determine next interval
- uint16_t nextInt;
- nextInt = call Random.rand16() % BEACON_INTERVAL;
- nextInt += BEACON_INTERVAL >> 1;
- call BeaconTimer.startOneShot(nextInt);
- post updateRouteTask();
- post sendBeaconTask();
- }
- }
-
- /* Handle the receiving of beacon messages from the neighbors. We update the
- * table, but wait for the next route update to choose a new parent */
- event message_t* BeaconReceive.receive(message_t* msg, void* payload, uint8_t len) {
- am_addr_t from;
- beacon_msg_t* rcvBeacon;
-
- // Received a beacon, but it's not from us.
- if (len != sizeof(beacon_msg_t)) {
- dbg("LITest", "%s, received beacon of size %hhu, expected %i\n", __FUNCTION__, len, (int)sizeof(beacon_msg_t));
-
- return msg;
- }
-
- //need to get the am_addr_t of the source
- from = call LinkSrcPacket.getSrc(msg);
- rcvBeacon = (beacon_msg_t*)payload;
-
- dbg("TreeRouting","%s from: %d [ parent: %d hopcount: %d metric: %d]\n",
- __FUNCTION__, from,
- rcvBeacon->parent, rcvBeacon->hopcount, rcvBeacon->metric);
- //call CollectionDebug.logEventRoute(NET_C_TREE_RCV_BEACON, rcvBeacon->parent, rcvBeacon->hopcount, rcvBeacon->metric);
-
- //update neighbor table
- if (rcvBeacon->parent != INVALID_ADDR) {
-
- /* If this node is a root, request a forced insert in the link
- * estimator table and pin the node. */
- if (rcvBeacon->hopcount == 0) {
- dbg("TreeRouting","from a root, inserting if not in table\n");
- call LinkEstimator.insertNeighbor(from);
- call LinkEstimator.pinNeighbor(from);
- }
- //TODO: also, if better than my current parent's path metric, insert
-
- routingTableUpdateEntry(from, rcvBeacon->parent, rcvBeacon->hopcount, rcvBeacon->metric);
- }
-
- //post updateRouteTask();
- return msg;
- }
-
- /* Signals that a neighbor is no longer reachable. need special care if
- * that neighbor is our parent */
- event void LinkEstimator.evicted(am_addr_t neighbor) {
- routingTableEvict(neighbor);
- dbg("TreeRouting","%s\n",__FUNCTION__);
- if (routeInfo.parent == neighbor) {
- routeInfoInit(&routeInfo);
- justEvicted = TRUE;
- post updateRouteTask();
- }
- }
-
- /* Interface UnicastNameFreeRouting */
- /* Simple implementation: return the current routeInfo */
- command am_addr_t Routing.nextHop() {
- return routeInfo.parent;
- }
- command bool Routing.hasRoute() {
- return (routeInfo.parent != INVALID_ADDR);
- }
-
- /* TreeRoutingInspect interface */
- command error_t TreeRoutingInspect.getParent(am_addr_t* parent) {
- if (parent == NULL)
- return FAIL;
- if (routeInfo.parent == INVALID_ADDR)
- return FAIL;
- *parent = routeInfo.parent;
- return SUCCESS;
- }
- command error_t TreeRoutingInspect.getHopcount(uint8_t* hopcount) {
- if (hopcount == NULL)
- return FAIL;
- if (routeInfo.parent == INVALID_ADDR)
- return FAIL;
- *hopcount= routeInfo.hopcount;
- return SUCCESS;
- }
- command error_t TreeRoutingInspect.getMetric(uint16_t* metric) {
- if (metric == NULL)
- return FAIL;
- if (routeInfo.parent == INVALID_ADDR)
- return FAIL;
- *metric = routeInfo.metric;
- return SUCCESS;
- }
-
- command void TreeRoutingInspect.triggerRouteUpdate() {
- // Random time in interval 64-127ms
- uint16_t time = call Random.rand16();
- time &= 0x3f;
- time += 64;
- if (call BeaconTimer.gett0() + call BeaconTimer.getdt() -
- call BeaconTimer.getNow() >= time) {
- call BeaconTimer.stop();
- call BeaconTimer.startOneShot(time);
- }
- }
-
- /* RootControl interface */
- /** sets the current node as a root, if not already a root */
- /* returns FAIL if it's not possible for some reason */
- command error_t RootControl.setRoot() {
- bool route_found = FALSE;
- route_found = (routeInfo.parent == INVALID_ADDR);
- atomic {
- state_is_root = 1;
- routeInfo.parent = my_ll_addr; //myself
- routeInfo.hopcount = 0;
- routeInfo.metric = 0;
- }
- if (route_found)
- signal Routing.routeFound();
- dbg("TreeRouting","%s I'm a root now!\n",__FUNCTION__);
- call CollectionDebug.logEventRoute(NET_C_TREE_NEW_PARENT, routeInfo.parent, routeInfo.hopcount, routeInfo.metric);
- return SUCCESS;
- }
-
- command error_t RootControl.unsetRoot() {
- atomic {
- state_is_root = 0;
- routeInfoInit(&routeInfo);
- }
- dbg("TreeRouting","%s I'm not a root now!\n",__FUNCTION__);
- post updateRouteTask();
- return SUCCESS;
- }
-
- command bool RootControl.isRoot() {
- return state_is_root;
- }
-
- default event void Routing.noRoute() {
- }
-
- default event void Routing.routeFound() {
- }
-
-
- /************************************************************/
- /* Routing Table Functions */
-
- /* The routing table keeps info about neighbor's route_info,
- * and is used when choosing a parent.
- * The table is simple:
- * - not fragmented (all entries in 0..routingTableActive)
- * - not ordered
- * - no replacement: eviction follows the LinkEstimator table
- */
-
- void routingTableInit() {
- routingTableActive = 0;
- }
-
- /* Returns the index of parent in the table or
- * routingTableActive if not found */
- uint8_t routingTableFind(am_addr_t neighbor) {
- uint8_t i;
- if (neighbor == INVALID_ADDR)
- return routingTableActive;
- for (i = 0; i < routingTableActive; i++) {
- if (routingTable[i].neighbor == neighbor)
- break;
- }
- return i;
- }
-
-
- error_t routingTableUpdateEntry(am_addr_t from, am_addr_t parent,
- uint8_t hopcount, uint16_t metric)
- {
- uint8_t idx;
- uint16_t linkMetric;
- linkMetric = evaluateMetric(call LinkEstimator.getLinkQuality(from));
-
- idx = routingTableFind(from);
- if (idx == routingTableSize) {
- //not found and table is full
- //if (passLinkMetricThreshold(linkMetric))
- //TODO: add replacement here, replace the worst
- //}
- dbg("TreeRouting", "%s FAIL, table full\n", __FUNCTION__);
- return FAIL;
- }
- else if (idx == routingTableActive) {
- //not found and there is space
- if (passLinkMetricThreshold(linkMetric)) {
- atomic {
- routingTable[idx].neighbor = from;
- routingTable[idx].info.parent = parent;
- routingTable[idx].info.hopcount = hopcount;
- routingTable[idx].info.metric = metric;
- routingTableActive++;
- }
- dbg("TreeRouting", "%s OK, new entry\n", __FUNCTION__);
- } else {
- dbg("TreeRouting", "%s Fail, link quality (%hu) below threshold\n", __FUNCTION__, linkMetric);
- }
- } else {
- //found, just update
- atomic {
- routingTable[idx].neighbor = from;
- routingTable[idx].info.parent = parent;
- routingTable[idx].info.hopcount = hopcount;
- routingTable[idx].info.metric = metric;
- }
- dbg("TreeRouting", "%s OK, updated entry\n", __FUNCTION__);
- }
- return SUCCESS;
- }
-
- /* if this gets expensive, introduce indirection through an array of pointers */
- error_t routingTableEvict(am_addr_t neighbor) {
- uint8_t idx,i;
- idx = routingTableFind(neighbor);
- if (idx == routingTableActive)
- return FAIL;
- routingTableActive--;
- for (i = idx; i < routingTableActive; i++) {
- routingTable[i] = routingTable[i+1];
- }
- return SUCCESS;
- }
- /*********** end routing table functions ***************/
-
- /* Default implementations for CollectionDebug calls.
- * These allow CollectionDebug not to be wired to anything if debugging
- * is not desired. */
-
- default command error_t CollectionDebug.logEvent(uint8_t type) {
- return SUCCESS;
- }
- default command error_t CollectionDebug.logEventSimple(uint8_t type, uint16_t arg) {
- return SUCCESS;
- }
- default command error_t CollectionDebug.logEventDbg(uint8_t type, uint16_t arg1, uint16_t arg2, uint16_t arg3) {
- return SUCCESS;
- }
- default command error_t CollectionDebug.logEventMsg(uint8_t type, uint16_t msg, am_addr_t origin, am_addr_t node) {
- return SUCCESS;
- }
- default command error_t CollectionDebug.logEventRoute(uint8_t type, am_addr_t parent, uint8_t hopcount, uint16_t metric) {
- return SUCCESS;
- }
-
-}
+++ /dev/null
-/* $Id$ */
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/*
- * @author Rodrigo Fonseca
- * @date $Date$
- * @see Net2-WG
- */
-
-
-interface TreeRoutingInspect {
- /* Get the parent of the node in the tree. The pointer is allocated
- * by the caller. If the parent is invalid, return FAIL. The
- * caller MUST NOT use the value in parent if the return is not
- * SUCCESS
- */
- command error_t getParent(am_addr_t* parent);
-
- /* Get the depth (hopcount) of the node in the tree. The pointer is
- * allocated by the caller. If the parent is invalid, return FAIL
- * (no info). The caller MUST NOT use the value in parent if the
- * return is not SUCCESS
- */
- command error_t getHopcount(uint8_t* hopcount);
-
- /* Get the path quality metric for the current path to the root
- * through the current parent. The pointer is allocated by the
- * caller. If the parent is invalid, return FAIL (no info). The
- * caller MUST NOT use the value in parent if the return is not
- * SUCCESS
- */
- command error_t getMetric(uint16_t* metric);
-
- /* This informs the routing engine to update its routing
- * information, possibly by sending a beacon */
- command void triggerRouteUpdate();
-}
+++ /dev/null
-#include <CollectionDebugMsg.h>
-module UARTDebugSenderP {
- provides {
- interface CollectionDebug;
- }
- uses {
- interface Boot;
- interface Pool<message_t> as MessagePool;
- interface Queue<message_t*> as SendQueue;
- interface AMSend as UARTSend;
- }
-}
-implementation {
- message_t uartPacket;
- bool sending;
- uint8_t len;
- uint16_t statLogReceived = 0;
- uint16_t statEnqueueFail = 0;
- uint16_t statSendFail = 0;
- uint16_t statSendDoneFail = 0;
- uint16_t statSendDoneOk = 0;
- uint16_t statSendDoneBug = 0;
-
-
- event void Boot.booted() {
- sending = FALSE;
- len = sizeof(CollectionDebugMsg);
- statSendFail = 0;
- statLogReceived = 0;
- statEnqueueFail = 0;
- statSendDoneOk = 0;
- statSendDoneFail = 0;
- statSendDoneBug = 0;
- }
-
- task void sendTask() {
- if (sending) {
- return;
- } else if (call SendQueue.empty()) {
- return;
- } else {
- message_t* smsg = call SendQueue.head();
- error_t eval = call UARTSend.send(AM_BROADCAST_ADDR, smsg, len);
- if (eval == SUCCESS) {
- sending = TRUE;
- return;
- } else {
- //Drop packet. Don't retry.
- statSendFail++;
- call SendQueue.dequeue();
- call MessagePool.put(smsg);
- if (! call SendQueue.empty())
- post sendTask();
- }
- }
- }
-
- event void UARTSend.sendDone(message_t *msg, error_t error) {
- message_t* qh = call SendQueue.head();
- if (qh == NULL || qh != msg) {
- //bad mojo
- statSendDoneBug++;
- } else {
- call SendQueue.dequeue();
- call MessagePool.put(msg);
- if (error == SUCCESS)
- statSendDoneOk++;
- else
- statSendDoneFail++;
- }
- sending = FALSE;
- if (!call SendQueue.empty())
- post sendTask();
- }
-
- command error_t CollectionDebug.logEvent(uint8_t type) {
- statLogReceived++;
- if (call MessagePool.empty()) {
- return FAIL;
- } else {
- message_t* msg = call MessagePool.get();
- CollectionDebugMsg* dbg_msg = call UARTSend.getPayload(msg);
- memset(dbg_msg, 0, len);
-
- dbg_msg->type = type;
- dbg_msg->seqno = statLogReceived;
-
- if (call SendQueue.enqueue(msg) == SUCCESS) {
- post sendTask();
- return SUCCESS;
- } else {
- statEnqueueFail++;
- call MessagePool.put(msg);
- return FAIL;
- }
- }
- }
- /* Used for FE_SENT_MSG, FE_RCV_MSG, FE_FWD_MSG, FE_DST_MSG */
- command error_t CollectionDebug.logEventMsg(uint8_t type, uint16_t msg_id, am_addr_t origin, am_addr_t node) {
- statLogReceived++;
- if (call MessagePool.empty()) {
- return FAIL;
- } else {
- message_t* msg = call MessagePool.get();
- CollectionDebugMsg* dbg_msg = call UARTSend.getPayload(msg);
- memset(dbg_msg, 0, len);
-
- dbg_msg->type = type;
- dbg_msg->data.msg.msg_uid = msg_id;
- dbg_msg->data.msg.origin = origin;
- dbg_msg->data.msg.other_node = node;
- dbg_msg->seqno = statLogReceived;
-
- if (call SendQueue.enqueue(msg) == SUCCESS) {
- post sendTask();
- return SUCCESS;
- } else {
- statEnqueueFail++;
- call MessagePool.put(msg);
- return FAIL;
- }
- }
- }
- /* Used for TREE_NEW_PARENT, TREE_ROUTE_INFO */
- command error_t CollectionDebug.logEventRoute(uint8_t type, am_addr_t parent, uint8_t hopcount, uint16_t metric) {
- statLogReceived++;
- if (call MessagePool.empty()) {
- return FAIL;
- } else {
- message_t* msg = call MessagePool.get();
- CollectionDebugMsg* dbg_msg = call UARTSend.getPayload(msg);
- memset(dbg_msg, 0, len);
-
- dbg_msg->type = type;
- dbg_msg->data.route_info.parent = parent;
- dbg_msg->data.route_info.hopcount = hopcount;
- dbg_msg->data.route_info.metric = metric;
- dbg_msg->seqno = statLogReceived;
-
- if (call SendQueue.enqueue(msg) == SUCCESS) {
- post sendTask();
- return SUCCESS;
- } else {
- statEnqueueFail++;
- call MessagePool.put(msg);
- return FAIL;
- }
- }
- }
- /* Used for DBG_1 */
- command error_t CollectionDebug.logEventSimple(uint8_t type, uint16_t arg) {
- statLogReceived++;
- if (call MessagePool.empty()) {
- return FAIL;
- } else {
- message_t* msg = call MessagePool.get();
- CollectionDebugMsg* dbg_msg = call UARTSend.getPayload(msg);
- memset(dbg_msg, 0, len);
-
- dbg_msg->type = type;
- dbg_msg->data.arg = arg;
- dbg_msg->seqno = statLogReceived;
-
- if (call SendQueue.enqueue(msg) == SUCCESS) {
- post sendTask();
- return SUCCESS;
- } else {
- statEnqueueFail++;
- call MessagePool.put(msg);
- return FAIL;
- }
- }
- }
- /* Used for DBG_2, DBG_3 */
- command error_t CollectionDebug.logEventDbg(uint8_t type, uint16_t arg1, uint16_t arg2, uint16_t arg3) {
- statLogReceived++;
- if (call MessagePool.empty()) {
- return FAIL;
- } else {
- message_t* msg = call MessagePool.get();
- CollectionDebugMsg* dbg_msg = call UARTSend.getPayload(msg);
- memset(dbg_msg, 0, len);
-
- dbg_msg->type = type;
- dbg_msg->data.dbg.a = arg1;
- dbg_msg->data.dbg.b = arg2;
- dbg_msg->data.dbg.c = arg3;
- dbg_msg->seqno = statLogReceived;
-
- if (call SendQueue.enqueue(msg) == SUCCESS) {
- post sendTask();
- return SUCCESS;
- } else {
- statEnqueueFail++;
- call MessagePool.put(msg);
- return FAIL;
- }
- }
- }
-
-}
-
+++ /dev/null
-/* $Id$ */
-/*
- * "Copyright (c) 2005 The Regents of the University of California.
- * All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and its
- * documentation for any purpose, without fee, and without written agreement is
- * hereby granted, provided that the above copyright notice, the following
- * two paragraphs and the author appear in all copies of this software.
- *
- * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
- * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
- * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
- * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
- * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
- * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
- *
- */
-
-/**
- * Provides a single next hop on a name-free protocol.
- *
- * @author Philip Levis
- * @date $Date$
- */
-interface UnicastNameFreeRouting {
- /**
- * Get the address of the best next hop set to the destination.
- * If there is not best next hop, the address is the local address.
- * @return : The next best hop, or the local address if there is no route.
- */
- command am_addr_t nextHop();
- command bool hasRoute();
- event void routeFound();
- event void noRoute();
-
-}
-
+++ /dev/null
-Collection Service
-
-$Id$
-
-Rodrigo Fonseca, UCB
-Omprakash Gnawali, USC
-Kyle Jamieson, MIT
-
-
-This document describes inital thoughts on the collection protocol to be
-produced by the net2-wg. The main improvements over the defacto standard
-collection from TinyOS 1.x are as follows:
-
- 1. decoupling of neighbor management and link estimation from the routing
- establising element
- 2. more general modularization, in the direction of allowing very different
- multihop protocols to be implemented along the same lines. This structure can
- evolve to a more general network layer architecture.
- 3. decoupling of tree identifier from node address
-
-
-Service:
-
-The service provided by the collection network service is best-effort, multihop
-delivery of packets to the root of a specified tree. The interfaces provided
-are for sending, receiving, intercepting, and snooping packets. Packets in
-transit can be intercepted for in-network processing, and traffic can be
-snooped by forwarding nodes.
-
-[Rodrigo: This needs discussion, as we are parameterizing the send interface
- per tree id, and then want to further demultiplex by N_ID.
- These interfaces are
- parameterized by a network-layer id (in contrast to an AM id). AM ids are used
- for multiplexing at the link layer, and NID is used for demultiplexing among
- different users of the network layer.
-]
-
-Best-effort means that absolute reliability should be obtained by higher layer
-mechanisms, such as end-to-end retransmissions or forward error correcting
-coding. However, it does not preclude network level retransmissions and
-link-level retransmissions.
-
-There can be multiple trees in a network, and there can be multiple roots in a
-tree. A network with a single root is a special case of the former. A tree
-with multiple roots will provide the semantics of anycast: the message will be
-delivered to one of the roots. The specific tree is identified by a tree
-identifier (tree_id). Tree_id is explicitly decoupled from the node id that is
-the root of the tree, and is considered a network-level name.
-
-This decoupling has some advantages.
- 1. allows transparent substitution of one root by another, in case of
- failures for example.
- 2. allows any node to become the root of a tree
- 3. allows trees with multiple roots
-
-The specific tree(s) an application sends messages to can be configured at
-compile time. A shim module can be interposed between the network layer and
-the application and provide an address-free sending interface to a specified
-tree_id.
-
-Service decomposition:
-
-There are two main functionalities in the collection network protocol,
-corresponding to data and control planes. The data plane is responsible for
-forwarding of messages, and the control plane is responsible for the
-establishment of the routes in the network. In other words, the control plane
-tells *where* to send messages to, while the data plane is responsible for
-*how* and *when* to send messages. Correspondingly, there are two main modules
-in the implementation: a forwarding engine and a routing engine. The basic
-interface between the two is a lookup call that obtains a set of next hops to
-forward the message to.
-
-The forwarding engine is responsible for the forwarding discipline: queueing,
-scheduling, network-level retransmission. The routing engine is responsible for
-building and maintaining the information necessary to get the next hops for a
-given message. For example, it should maintain the tree structure. It should
-use the services of a link estimator to provide link quality estimates for
-different neighbors.
-
-Control-plane protocol:
-
-The tree formation protocol is based on a variation of the distance vector
-protocol.
-
-Control packet format: (in bits)
-
-[sizeof(bits) neighbor_t]:source 4:count 4:total | [ 8:tree_id | 8:root_id | 8:root_seqno | 8:hopcount | 16:cost ]+
-
-source is the neighbor id
-total is how many control packets in this message (if there are many roots that
- don't fit into a packet)
-count is which one of the total packets in this message this belongs to
-
-Then there is a sequence of cost-to-root messages, specifying the tree_id, the
-root_id in that tree, the
-hopcount of the sending node, the cost to that root through the sender, and the
-sequence number of the root message.
-
-A tree formation message is simply one initiated by the root, in which the
-hopcount and the cost are 0, and the sequence number is incremented with each
-broadcast. The root is the only node which increments the cost-to-root entry
-sequence numbers.
-
-The tree_id allows multiple trees, hopcount allows the tree formation and
-establishment of hopcounts. Cost allows parent selection. Cost MUST be a
-cumulative (additive or multiplicative) measure that represents the cost or
-quality to get a message to the root starting from sending node. The root_id
-and root_seqno are needed for the prevention of count to infinity problems.
-
-Each node actively maintains a parent towards the root of a tree. This is the
-neighbor with the lowest composed cost (my cost to the neighbor + the
-neighbor's cost). This parent is not necessarily used for routing: it is used
-to establish the hopcount, and thus the tree structure. A packet can be routed
-to any node that decreases the cost to the root. Should a parent die, it will
-be readily replaced by another neighbor with a lower cost. This can be done
-proactively by looking at the neighbor table, or can wait for the next distance
-vector update from a neighbor.
-
-Data-plane protocol:
-
-There are two header fields in the data-plane packets that allow successful
-routing:
-typedef struct {
- uint8_t tree_id;
- uint16_t min_cost;
-} nc_header; //network collection header
-
-The forwarding engine can elect to perform network-level retransmissions to
-alternate next hops should the trasmission to a given next hop fail. This
-allows recoveries in routing on time scales shorter than those required for
-route convergence, and leverages routing engines that can provide multiple next
-hops towards a given destination. This technique can reduce the buffer
-requirements at forwarding nodes, and spread the load in face of congestion.
-However it is still an open question whether this is the best response: it
-might also spread congestion.
-
-Link Estimation:
-
-Link estimation can be done in a variety of ways, and we do not impose one
-here. It is decoupled from the establishment of routes. There is a narrow
-interface between the link estimator and the routing engine, see interface
-LinkEstimator below. The one requirement is that the quality returned be
-standardized. Two candidates are the probability of success of a packet, and
-the ETX, or expected number of transmissions to get the message across to the
-other node. Some protocols might also be interested in one of the reverse or
-forward qualities. It is the job of the link estimator to convert other
-metrics to the standardized one, and to possibly have its own control traffic
-to exchange reverse link qualities.
-
-There are currently three ways of doing this: using LQI, using RSSI, or using
-an average history of packet losses on a link. In the case of the former, it is
-possible that the link estimator be interposed in the network stack and inserts
-a header with the source address in each outgoing packet.
-
-Some Issues:
-
-Any node can become the root of a tree. Nodes can keep state about a limited
-number of trees. An issue arises when there are more trees active than space in
-the nodes, and there has to be a decision on which tree to keep information
-about.
-
-One solution is to have it be first-come first-serve. Another is to have a
-deterministic priority between tree ids, such that a new tree message will
-displace a lower priority one. Eventually a new tree with higher priority id
-will reach the root of a lower priority one, and the root will silence.
-
-Maybe the simpler solution for now is to have a first come-first serve policy,
-such that a new root will fail to propagate its messages on a network with more
-than one tree.
-
-Interfaces:
-
-
-(The send interface is to be used, parameterized by tree_id)
-interface BasicRouting
- //To be parameterized by tree_id
- command result_t getNextHops(neighbor_t* nextHops, uint8_t* n);
-interface CostBasedRouting
- //To be parameterized by tree_id
- command uint16_t getMyCost();
- command uint16_t getNeighborCost(neighbor_t neighbor);
-interface REControl
- command result_t initializeRH(message_t *msg, uint8_t tree_id);
- command uint8_t getHeaderSize();
- command result_t startRoot(uint8_t tree_id);
- command result_t stopRoot(uint8_t tree_id);
-
-interface LinkEstimator:
- command uint8_t getLinkQuality(neighbot_t neighbor);
- command uint8_t getReverseQuality(neighbot_t neighbor);
- command uint8_t getForwardQuality(neighbot_t neighbor);
-
-interface NeighborTable:
- event void evicted(neighbot_t neighbor)
-
-(Initially, typedef uint16_t neighbor_t)
-
-Components:
-
-LinkEstimator {
- provides {
- interface LinkEstimator;
- interface NeighborTable;
- }
-}
-
-MTreeRoutingEngine
- provides {
- REControl;
- BasicRouting[uint8_t tree_id];
- CostBasedRouting[uint8_t tree_id];
- }
- uses {
- LinkEstimator;
- NeighborTable;
- SendMsg[CONTROL_AM_ID];
- ReceiveMsg[CONTROL_AM_ID];
- }
-}
-
-ForwardingEngine {
- provides {
- interface Send[uint8_t tree_id]
- interface Receive[uint8_t tree_id];
- interface Intercept;
- interface Snoop;
- interface Packet;
- }
- uses {
- interface REControl;
- interface BasicRouting[uint8_t tree_id];
- interface CostBasedRouting[uint8_t tree_id];
- interface SendMsg[COLLECTION_AM_ID];
- interface ReceiveMsg[COLLECTION_AM_ID];
- }
-}
-
-Observation: while some of these interfaces are similar to the ones specified
-for multihop routing in TinyOS 1.x, there were several required changes. The
-TinyOS framework assumed address-free protocols, and only one next hop per
-message. There was also a coupling assumed between parent selection and
-neighbor/link quality estimation, which resulted in the exposure of some
-parameters not necessary for the forwarding part. There is parallel between
-RouteSelect and BasicRouting, CostBasedRouting and REControl, while calls such
-as getQuality shouldn't be exposed to the ForwardingEngine.
-
-
-
-
-
-
projects / tinyos-2.x.git / commitdiff