* @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;
interface Random;
interface CollectionDebug;
interface CtpCongestion;
+
+ interface CompareBit;
+
}
}
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();
}
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;
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);
/* 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:
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) {
}
if (pathEtx < minEtx) {
+ dbg("TreeRouting", " best is %d, setting to %d\n", pathEtx, entry->neighbor);
minEtx = pathEtx;
best = entry;
}
// 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();
+ }
}
}
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",
event void RouteTimer.fired() {
if (radioOn && running) {
- post updateRouteTask();
+ post updateRouteTask();
}
}
}
- 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());
}
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) {
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) {
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;
}
}
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) {
}
+ /* 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 */
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) {
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;
}
projects / tinyos-2.x.git / blobdiff