X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=tos%2Flib%2Fnet%2Fctp%2FCtpRoutingEngineP.nc;h=4657a00f20ccffc96657bcd4079e827f207a80b0;hb=e9bfab607e051bae6afb47b44892ce37541d1b44;hp=5c6faeb01ef3a4e360d0f4563f847cbd7abb882a;hpb=74b463fafc2f4183803664e767abac06e0a1bf85;p=tinyos-2.x.git diff --git a/tos/lib/net/ctp/CtpRoutingEngineP.nc b/tos/lib/net/ctp/CtpRoutingEngineP.nc index 5c6faeb0..4657a00f 100644 --- a/tos/lib/net/ctp/CtpRoutingEngineP.nc +++ b/tos/lib/net/ctp/CtpRoutingEngineP.nc @@ -93,7 +93,7 @@ * @see Net2-WG */ -generic module CtpRoutingEngineP(uint8_t routingTableSize, uint16_t minInterval, uint16_t maxInterval) { +generic module CtpRoutingEngineP(uint8_t routingTableSize, uint32_t minInterval, uint32_t maxInterval) { provides { interface UnicastNameFreeRouting as Routing; interface RootControl; @@ -113,6 +113,9 @@ generic module CtpRoutingEngineP(uint8_t routingTableSize, uint16_t minInterval, interface Random; interface CollectionDebug; interface CtpCongestion; + + interface CompareBit; + } } @@ -148,26 +151,19 @@ implementation { uint32_t parentChanges; /* end statistics */ - uint32_t routeUpdateTimerCount; - - // Maximimum it takes to hear four beacons - enum { - DEATH_TEST_INTERVAL = (maxInterval * 4) / (BEACON_INTERVAL / 1024), - }; - // forward declarations void routingTableInit(); uint8_t routingTableFind(am_addr_t); error_t routingTableUpdateEntry(am_addr_t, am_addr_t , uint16_t); error_t routingTableEvict(am_addr_t neighbor); - uint16_t currentInterval = minInterval; + uint32_t currentInterval = minInterval; uint32_t t; bool tHasPassed; void chooseAdvertiseTime() { t = currentInterval; - t *= 512; // * 1024 / 2 + t /= 2; t += call Random.rand32() % t; tHasPassed = FALSE; call BeaconTimer.stop(); @@ -180,26 +176,22 @@ implementation { } void decayInterval() { - if (!state_is_root) { currentInterval *= 2; if (currentInterval > maxInterval) { currentInterval = maxInterval; } - } chooseAdvertiseTime(); } void remainingInterval() { uint32_t remaining = currentInterval; - remaining *= 1024; remaining -= t; tHasPassed = TRUE; - call BeaconTimer.startPeriodic(t); + call BeaconTimer.startOneShot(remaining); } command error_t Init.init() { uint8_t maxLength; - routeUpdateTimerCount = 0; radioOn = FALSE; running = FALSE; parentChanges = 0; @@ -207,7 +199,7 @@ implementation { routeInfoInit(&routeInfo); routingTableInit(); my_ll_addr = call AMPacket.address(); - beaconMsg = call BeaconSend.getPayload(&beaconMsgBuffer); + beaconMsg = call BeaconSend.getPayload(&beaconMsgBuffer, call BeaconSend.maxPayloadLength()); maxLength = call BeaconSend.maxPayloadLength(); dbg("TreeRoutingCtl","TreeRouting initialized. (used payload:%d max payload:%d!\n", sizeof(beaconMsg), maxLength); @@ -250,16 +242,9 @@ implementation { /* Is this quality measure better than the minimum threshold? */ // Implemented assuming quality is EETX bool passLinkEtxThreshold(uint16_t etx) { - return TRUE; return (etx < ETX_THRESHOLD); } - /* Converts the output of the link estimator to path metric - * units, that can be *added* to form path metric measures */ - uint16_t evaluateEtx(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: @@ -294,11 +279,11 @@ implementation { i, entry->neighbor, entry->info.parent); continue; } - /* Compute this neighbor's path metric */ - linkEtx = evaluateEtx(call LinkEstimator.getLinkQuality(entry->neighbor)); + + linkEtx = call LinkEstimator.getLinkQuality(entry->neighbor); dbg("TreeRouting", - "routingTable[%d]: neighbor: [id: %d parent: %d etx: %d]\n", - i, entry->neighbor, entry->info.parent, linkEtx); + "routingTable[%d]: neighbor: [id: %d parent: %d etx: %d retx: %d]\n", + i, entry->neighbor, entry->info.parent, linkEtx, entry->info.etx); pathEtx = linkEtx + entry->info.etx; /* Operations specific to the current parent */ if (entry->neighbor == routeInfo.parent) { @@ -321,6 +306,7 @@ implementation { } if (pathEtx < minEtx) { + dbg("TreeRouting", " best is %d, setting to %d\n", pathEtx, entry->neighbor); minEtx = pathEtx; best = entry; } @@ -348,17 +334,21 @@ implementation { // we need it: i. when choosing a parent (here); // ii. when choosing a next hop parentChanges++; - resetInterval(); + dbg("TreeRouting","Changed parent. from %d to %d\n", routeInfo.parent, best->neighbor); - call CollectionDebug.logEventRoute(NET_C_TREE_NEW_PARENT, best->neighbor, 0, best->info.etx); + call CollectionDebug.logEventDbg(NET_C_TREE_NEW_PARENT, best->neighbor, best->info.etx, minEtx); call LinkEstimator.unpinNeighbor(routeInfo.parent); call LinkEstimator.pinNeighbor(best->neighbor); call LinkEstimator.clearDLQ(best->neighbor); - atomic { + + atomic { routeInfo.parent = best->neighbor; routeInfo.etx = best->info.etx; routeInfo.congested = best->info.congested; } + if (currentEtx - minEtx > 20) { + call CtpInfo.triggerRouteUpdate(); + } } } @@ -403,8 +393,7 @@ implementation { beaconMsg->etx = routeInfo.etx; beaconMsg->options |= CTP_OPT_PULL; } else { - beaconMsg->etx = routeInfo.etx + - evaluateEtx(call LinkEstimator.getLinkQuality(routeInfo.parent)); + beaconMsg->etx = routeInfo.etx + call LinkEstimator.getLinkQuality(routeInfo.parent); } dbg("TreeRouting", "%s parent: %d etx: %d\n", @@ -434,7 +423,7 @@ implementation { event void RouteTimer.fired() { if (radioOn && running) { - post updateRouteTask(); + post updateRouteTask(); } } @@ -453,8 +442,8 @@ implementation { } - ctp_routing_header_t* getHeader(message_t* m) { - return (ctp_routing_header_t*)call BeaconReceive.getPayload(m, NULL); + ctp_routing_header_t* getHeader(message_t* ONE m) { + return (ctp_routing_header_t*)call BeaconSend.getPayload(m, call BeaconSend.maxPayloadLength()); } @@ -484,7 +473,6 @@ implementation { dbg("TreeRouting","%s from: %d [ parent: %d etx: %d]\n", __FUNCTION__, from, rcvBeacon->parent, rcvBeacon->etx); - //call CollectionDebug.logEventRoute(NET_C_TREE_RCV_BEACON, rcvBeacon->parent, 0, rcvBeacon->etx); //update neighbor table if (rcvBeacon->parent != INVALID_ADDR) { @@ -505,10 +493,10 @@ implementation { if (call CtpRoutingPacket.getOption(msg, CTP_OPT_PULL)) { resetInterval(); } - //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) { @@ -545,7 +533,11 @@ implementation { return FAIL; if (routeInfo.parent == INVALID_ADDR) return FAIL; - *etx = routeInfo.etx; + if (state_is_root == 1) { + *etx = 0; + } else { + *etx = routeInfo.etx + call LinkEstimator.getLinkQuality(routeInfo.parent); + } return SUCCESS; } @@ -554,24 +546,11 @@ implementation { } command void CtpInfo.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); - } + resetInterval(); } command void CtpInfo.triggerImmediateRouteUpdate() { - // Random time in interval 4-11ms - uint16_t time = call Random.rand16(); - time &= 0x7; - time += 4; - call BeaconTimer.stop(); - call BeaconTimer.startOneShot(time); + resetInterval(); } command void CtpInfo.setNeighborCongested(am_addr_t n, bool congested) { @@ -640,6 +619,54 @@ implementation { } + /* The link will be recommended for insertion if it is better* than some + * link in the routing table that is not our parent. + * We are comparing the path quality up to the node, and ignoring the link + * quality from us to the node. This is because of a couple of things: + * 1. we expect this call only for links with white bit set + * 2. we are being optimistic to the nodes in the table, by ignoring the + * 1-hop quality to them (which means we are assuming it's 1 as well) + * This actually sets the bar a little higher for replacement + * 3. this is faster + */ + event bool CompareBit.shouldInsert(message_t *msg, void* payload, uint8_t len) { + + bool found = FALSE; + uint16_t pathEtx; + uint16_t neighEtx; + int i; + routing_table_entry* entry; + ctp_routing_header_t* rcvBeacon; + + if ((call AMPacket.type(msg) != AM_CTP_ROUTING) || + (len != sizeof(ctp_routing_header_t))) + return FALSE; + + /* 1.determine this packet's path quality */ + rcvBeacon = (ctp_routing_header_t*)payload; + + if (rcvBeacon->parent == INVALID_ADDR) + return FALSE; + /* the node is a root, recommend insertion! */ + if (rcvBeacon->etx == 0) { + return TRUE; + } + + pathEtx = rcvBeacon->etx; // + linkEtx; + + /* 2. see if we find some neighbor that is worse */ + for (i = 0; i < routingTableActive && !found; i++) { + entry = &routingTable[i]; + //ignore parent, since we can't replace it + if (entry->neighbor == routeInfo.parent) + continue; + neighEtx = entry->info.etx; + found |= (pathEtx < neighEtx); + } + return found; + } + + /************************************************************/ /* Routing Table Functions */ @@ -672,7 +699,7 @@ implementation { error_t routingTableUpdateEntry(am_addr_t from, am_addr_t parent, uint16_t etx) { uint8_t idx; uint16_t linkEtx; - linkEtx = evaluateEtx(call LinkEstimator.getLinkQuality(from)); + linkEtx = call LinkEstimator.getLinkQuality(from); idx = routingTableFind(from); if (idx == routingTableSize) { @@ -772,7 +799,7 @@ implementation { command uint16_t CtpRoutingPacket.getEtx(message_t* msg) { return getHeader(msg)->etx; } - command void CtpRoutingPacket.setEtx(message_t* msg, uint8_t etx) { + command void CtpRoutingPacket.setEtx(message_t* msg, uint16_t etx) { getHeader(msg)->etx = etx; }