checking in Rodrigos changes

diff --git a/tos/lib/net/ctp/CtpDebugMsg.h b/tos/lib/net/ctp/CtpDebugMsg.h
index 7f42826f5b51045b7c4bd1cfbd6890abf8e071fd..59e1f73b5694538179406a5a716c835d9cd66581 100644 (file)
--- a/tos/lib/net/ctp/CtpDebugMsg.h
+++ b/tos/lib/net/ctp/CtpDebugMsg.h
@@ -23,6 +23,7 @@ enum {
     NET_C_FE_PUT_QEPOOL_ERR = 0x52,
     NET_C_FE_GET_MSGPOOL_ERR = 0x53,
     NET_C_FE_GET_QEPOOL_ERR = 0x54,
+    NET_C_FE_QUEUE_SIZE=0x55,
 
     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
@@ -41,6 +42,8 @@ enum {
                                     //  arg=1 => overheard parent's
                                     //           ECN cleared.
                                     //  arg=0 => timeout.
+    NET_C_FE_CONGESTED = 0x2E,
+
     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

diff --git a/tos/lib/net/ctp/CtpForwardingEngineP.nc b/tos/lib/net/ctp/CtpForwardingEngineP.nc
index 09eef878c0b20ea22e32e211f14dab357720951e..b436c668d87b45df449e95ef94f92c5cb1c6c5e6 100644 (file)
--- a/tos/lib/net/ctp/CtpForwardingEngineP.nc
+++ b/tos/lib/net/ctp/CtpForwardingEngineP.nc
@@ -181,6 +181,9 @@ implementation {
   /* Tracks our parent's congestion state. */
   bool parentCongested = FALSE;
 
+  /* Threshold for congestion */
+  uint8_t congestionThreshold;
+
   /* Keeps track of whether the routing layer is running; if not,
    * it will not send packets. */
   bool running = FALSE;
@@ -234,6 +237,7 @@ implementation {
       clientPtrs[i] = clientEntries + i;
       dbg("Forwarder", "clientPtrs[%hhu] = %p\n", i, clientPtrs[i]);
     }
+    congestionThreshold = (call SendQueue.maxSize()) >> 1;
     loopbackMsgPtr = &loopbackMsg;
     lastParent = call AMPacket.address();
     seqno = 0;
@@ -835,7 +839,7 @@ implementation {
   command bool CtpCongestion.isCongested() {
     // A simple predicate for now to determine congestion state of
     // this node.
-    bool congested = (call SendQueue.size() + 2 >= call SendQueue.maxSize()) ? 
+    bool congested = (call SendQueue.size() > congestionThreshold) ? 
       TRUE : FALSE;
     return ((congested || clientCongested)?TRUE:FALSE);
   }

diff --git a/tos/lib/net/ctp/CtpP.nc b/tos/lib/net/ctp/CtpP.nc
index 7f73f4471d9d052b82103ff674d8b6654145b97f..43254bb6a524372e71a32e91cd20d6f6cd442366 100644 (file)
--- a/tos/lib/net/ctp/CtpP.nc
+++ b/tos/lib/net/ctp/CtpP.nc
@@ -90,7 +90,7 @@ configuration CtpP {
 implementation {
   enum {
     CLIENT_COUNT = uniqueCount(UQ_CTP_CLIENT),
-    FORWARD_COUNT = 5,
+    FORWARD_COUNT = 12,
     TREE_ROUTING_TABLE_SIZE = 10,
     QUEUE_SIZE = CLIENT_COUNT + FORWARD_COUNT,
     CACHE_SIZE = 4,

diff --git a/tos/lib/net/ctp/CtpRoutingEngineP.nc b/tos/lib/net/ctp/CtpRoutingEngineP.nc
index 0044233b4d9008d97d5d6f0760a9d5fd2cf5fc28..9ffbf6c6681b877c419c787c29abbab54daf176c 100644 (file)
--- a/tos/lib/net/ctp/CtpRoutingEngineP.nc
+++ b/tos/lib/net/ctp/CtpRoutingEngineP.nc
@@ -200,7 +200,7 @@ implementation {
 
     command error_t Init.init() {
         uint8_t maxLength;
-       routeUpdateTimerCount = 0;
+        routeUpdateTimerCount = 0;
         radioOn = FALSE;
         running = FALSE;
         parentChanges = 0;
@@ -265,7 +265,6 @@ implementation {
     /* 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 */
-    /* TODO: take into account congested state to select parents */ 
     task void updateRouteTask() {
         uint8_t i;
         routing_table_entry* entry;
@@ -313,6 +312,9 @@ implementation {
                 }
                 continue;
             }
+            /* Ignore links that are congested */
+            if (entry->info.congested)
+                continue;
             /* Ignore links that are bad */
             if (!passLinkEtxThreshold(linkEtx)) {
               dbg("TreeRouting", "   did not pass threshold.\n");
@@ -328,8 +330,19 @@ implementation {
         //call CollectionDebug.logEventDbg(NET_C_DBG_3, routeInfo.parent, currentEtx, minEtx);  
 
         /* Now choose between the current parent and the best neighbor */
+        /* Requires that: 
+            1. at least another neighbor was found with ok quality and not congested
+            2. the current parent is congested and the other best route is at least as good
+            3. or the current parent is not congested and the neighbor quality is better by 
+               the PARENT_SWITCH_THRESHOLD.
+          Note: if our parent is congested, in order to avoid forming loops, we try to select
+                a node which is not a descendent of our parent. routeInfo.ext is our parent's
+                etx. Any descendent will be at least that + 10 (1 hop), so we restrict the 
+                selection to be less than that.
+        */
         if (minEtx != MAX_METRIC) {
             if (currentEtx == MAX_METRIC ||
+                (routeInfo.congested && (minEtx < (routeInfo.etx + 10))) ||
                 minEtx + PARENT_SWITCH_THRESHOLD < currentEtx) {
                 // routeInfo.metric will not store the composed metric.
                 // since the linkMetric may change, we will compose whenever
@@ -466,6 +479,7 @@ implementation {
         //need to get the am_addr_t of the source
         from = call LinkSrcPacket.getSrc(msg);
         rcvBeacon = (ctp_routing_header_t*)payload;
+
         congested = call CtpRoutingPacket.getOption(msg, CTP_OPT_ECN);
 
         dbg("TreeRouting","%s from: %d  [ parent: %d etx: %d]\n",
@@ -563,18 +577,16 @@ implementation {
 
     command void CtpInfo.setNeighborCongested(am_addr_t n, bool congested) {
         uint8_t idx;    
+        if (ECNOff)
+            return;
         idx = routingTableFind(n);
         if (idx < routingTableActive) {
             routingTable[idx].info.congested = congested;
         }
-        /* TODO:  (this only makes sense if routeUpdateTask takes congestion into
-         *         account for selecting routes.)
-         *   if (routeInfo.congested && !congested) 
-         *       post routeUpdateTask() 
-         *   else if (routeInfo.parent == n && congested) {
-         *       post routeUpdateTask()
-         *
-         */
+        if (routeInfo.congested && !congested) 
+            post updateRouteTask();
+        else if (routeInfo.parent == n && congested) 
+            post updateRouteTask();
     }
 
     command bool CtpInfo.isNeighborCongested(am_addr_t n) {
@@ -679,7 +691,8 @@ implementation {
                     routingTable[idx].neighbor = from;
                     routingTable[idx].info.parent = parent;
                     routingTable[idx].info.etx = etx;
-                   routingTable[idx].info.haveHeard = 1;
+                    routingTable[idx].info.haveHeard = 1;
+                    routingTable[idx].info.congested = FALSE;
                     routingTableActive++;
                 }
                 dbg("TreeRouting", "%s OK, new entry\n", __FUNCTION__);
@@ -692,7 +705,7 @@ implementation {
                 routingTable[idx].neighbor = from;
                 routingTable[idx].info.parent = parent;
                 routingTable[idx].info.etx = etx;
-               routingTable[idx].info.haveHeard = 1;
+                       routingTable[idx].info.haveHeard = 1;
             }
             dbg("TreeRouting", "%s OK, updated entry\n", __FUNCTION__);
         }