X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=tos%2Flib%2Fnet%2Fctp%2FCtpRoutingEngineP.nc;h=bd213db9fe1dba01fe2aef27b81e5a1e65ec23c9;hb=21f38881e2b39579501fc8f979cd0fa929ca7120;hp=fb8aad78ff98ca9fba238a9c897b96cbd710185f;hpb=618c63a3bd6752cdd94d8511ffecaac79499283a;p=tinyos-2.x.git diff --git a/tos/lib/net/ctp/CtpRoutingEngineP.nc b/tos/lib/net/ctp/CtpRoutingEngineP.nc index fb8aad78..bd213db9 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; + } } @@ -161,13 +164,13 @@ implementation { 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,21 +183,18 @@ 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() { @@ -207,7 +207,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); @@ -256,7 +256,7 @@ implementation { /* 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) { + uint16_t evaluateEtx(uint16_t quality) { //dbg("TreeRouting","%s %d -> %d\n",__FUNCTION__,quality, quality+10); return (quality + 10); } @@ -297,8 +297,8 @@ implementation { /* Compute this neighbor's path metric */ linkEtx = evaluateEtx(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 +321,7 @@ implementation { } if (pathEtx < minEtx) { + dbg("TreeRouting", " best is %d, setting to %d\n", pathEtx, entry->neighbor); minEtx = pathEtx; best = entry; } @@ -348,17 +349,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(); + } } } @@ -434,7 +439,7 @@ implementation { event void RouteTimer.fired() { if (radioOn && running) { - post updateRouteTask(); + post updateRouteTask(); } } @@ -453,8 +458,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 +489,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 +509,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 +549,12 @@ implementation { return FAIL; if (routeInfo.parent == INVALID_ADDR) return FAIL; - *etx = routeInfo.etx; + if (state_is_root == 1) { + *etx = 0; + } else { + // path etx = etx(parent) + etx(link to the parent) + *etx = routeInfo.etx + evaluateEtx(call LinkEstimator.getLinkQuality(routeInfo.parent)); + } return SUCCESS; } @@ -554,24 +563,11 @@ implementation { } command void CtpInfo.triggerRouteUpdate() { - // Random time in interval 64-127ms - uint16_t beaconDelay = call Random.rand16(); - beaconDelay &= 0x3f; - beaconDelay += 64; - if (call BeaconTimer.gett0() + call BeaconTimer.getdt() - - call BeaconTimer.getNow() >= beaconDelay) { - call BeaconTimer.stop(); - call BeaconTimer.startOneShot(beaconDelay); - } + resetInterval(); } command void CtpInfo.triggerImmediateRouteUpdate() { - // Random time in interval 4-11ms - uint16_t beaconDelay = call Random.rand16(); - beaconDelay &= 0x7; - beaconDelay += 4; - call BeaconTimer.stop(); - call BeaconTimer.startOneShot(beaconDelay); + resetInterval(); } command void CtpInfo.setNeighborCongested(am_addr_t n, bool congested) { @@ -640,6 +636,55 @@ 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; + //neighEtx = evaluateEtx(call LinkEstimator.getLinkQuality(entry->neighbor)); + found |= (pathEtx < neighEtx); + } + return found; + } + + /************************************************************/ /* Routing Table Functions */