From 2bb921603dd4304083b1921817198f85631f4232 Mon Sep 17 00:00:00 2001 From: gnawali Date: Tue, 16 Jan 2007 04:39:20 +0000 Subject: [PATCH] checking in Rodrigos changes --- tos/lib/net/ctp/CtpDebugMsg.h | 3 ++ tos/lib/net/ctp/CtpForwardingEngineP.nc | 6 +++- tos/lib/net/ctp/CtpP.nc | 2 +- tos/lib/net/ctp/CtpRoutingEngineP.nc | 37 +++++++++++++++++-------- 4 files changed, 34 insertions(+), 14 deletions(-) diff --git a/tos/lib/net/ctp/CtpDebugMsg.h b/tos/lib/net/ctp/CtpDebugMsg.h index 7f42826f..59e1f73b 100644 --- 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 09eef878..b436c668 100644 --- 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 7f73f447..43254bb6 100644 --- 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 0044233b..9ffbf6c6 100644 --- 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__); } -- 2.39.2