+++ /dev/null
-#include <DIP.h>
-
-configuration AMDIPC {
- provides interface DIPSend;
- provides interface DIPReceive as DataReceive;
- provides interface DIPReceive as VectorReceive;
- provides interface DIPReceive as SummaryReceive;
-}
-
-implementation {
- components AMDIPP;
- components new AMSenderC(AM_DIP) as SendC;
- components new AMReceiverC(AM_DIP) as ReceiveC;
-
- AMDIPP.NetAMSend -> SendC.AMSend;
- AMDIPP.NetReceive -> ReceiveC.Receive;
-
- components MainC;
- MainC.SoftwareInit -> AMDIPP.Init;
- AMDIPP.Boot -> MainC;
-
- components ActiveMessageC;
- AMDIPP.AMSplitControl -> ActiveMessageC;
-
- DIPSend = AMDIPP.DIPSend;
- DataReceive = AMDIPP.DIPDataReceive;
- VectorReceive = AMDIPP.DIPVectorReceive;
- SummaryReceive = AMDIPP.DIPSummaryReceive;
-}
+++ /dev/null
-
-module AMDIPP {
- provides interface Init;
-
- provides interface DIPSend;
- provides interface DIPReceive as DIPDataReceive;
- provides interface DIPReceive as DIPVectorReceive;
- provides interface DIPReceive as DIPSummaryReceive;
-
- uses interface AMSend as NetAMSend;
- uses interface Receive as NetReceive;
-
- uses interface SplitControl as AMSplitControl;
- uses interface Boot;
-}
-
-implementation {
- message_t am_msg;
- bool busy;
-
- event void Boot.booted() {
- call AMSplitControl.start();
- }
-
- event void AMSplitControl.startDone(error_t err) {
- if(err != SUCCESS) {
- call AMSplitControl.start();
- return;
- }
- dbg("AMDIPP", "ActiveMessageC started!\n");
- }
-
- event void AMSplitControl.stopDone(error_t err) { }
-
- command error_t Init.init() {
- busy = FALSE;
- return SUCCESS;
- }
-
- command error_t DIPSend.send(uint8_t len) {
- error_t err;
- dbg("AMDIPP", "Attempting to send data in the air\n");
- err = call NetAMSend.send(AM_BROADCAST_ADDR, &am_msg, len);
- if(err == SUCCESS) {
- busy = TRUE;
- }
- return err;
- }
-
- command void* DIPSend.getPayloadPtr() {
- // returns NULL if message is busy
- if(busy) {
- return NULL;
- }
- return call NetAMSend.getPayload(&am_msg, 0);
- }
-
- command uint8_t DIPSend.maxPayloadLength() {
- return call NetAMSend.maxPayloadLength();
- }
-
- event void NetAMSend.sendDone(message_t* msg, error_t err) {
- dbg("AMDIPP", "Data send successfully in the air\n");
- if(msg == &am_msg) {
- busy = FALSE;
- }
- }
-
- event message_t* NetReceive.receive(message_t* msg, void* payload,
- uint8_t len) {
- dip_msg_t* dmsg;
- uint8_t type;
-
- dmsg = (dip_msg_t*) payload;
- type = dmsg->type;
- switch(type) {
- case ID_DIP_DATA:
- signal DIPDataReceive.receive(dmsg->content, len);
- break;
- case ID_DIP_VECTOR:
- signal DIPVectorReceive.receive(dmsg->content, len);
- break;
- case ID_DIP_SUMMARY:
- signal DIPSummaryReceive.receive(dmsg->content, len);
- break;
- }
- return msg;
- }
-
-}
--- /dev/null
+#include <Dip.h>
+
+configuration AMDipC {
+ provides interface DipSend;
+ provides interface DipReceive as DataReceive;
+ provides interface DipReceive as VectorReceive;
+ provides interface DipReceive as SummaryReceive;
+}
+
+implementation {
+ components AMDipP;
+ components new AMSenderC(AM_DIP) as SendC;
+ components new AMReceiverC(AM_DIP) as ReceiveC;
+
+ AMDipP.NetAMSend -> SendC.AMSend;
+ AMDipP.NetReceive -> ReceiveC.Receive;
+
+ components MainC;
+ MainC.SoftwareInit -> AMDipP.Init;
+ AMDipP.Boot -> MainC;
+
+ components ActiveMessageC;
+ AMDipP.AMSplitControl -> ActiveMessageC;
+
+ DipSend = AMDipP.DipSend;
+ DataReceive = AMDipP.DipDataReceive;
+ VectorReceive = AMDipP.DipVectorReceive;
+ SummaryReceive = AMDipP.DipSummaryReceive;
+}
--- /dev/null
+
+module AMDipP {
+ provides interface Init;
+
+ provides interface DipSend;
+ provides interface DipReceive as DipDataReceive;
+ provides interface DipReceive as DipVectorReceive;
+ provides interface DipReceive as DipSummaryReceive;
+
+ uses interface AMSend as NetAMSend;
+ uses interface Receive as NetReceive;
+
+ uses interface SplitControl as AMSplitControl;
+ uses interface Boot;
+}
+
+implementation {
+ message_t am_msg;
+ bool busy;
+
+ event void Boot.booted() {
+ call AMSplitControl.start();
+ }
+
+ event void AMSplitControl.startDone(error_t err) {
+ if(err != SUCCESS) {
+ call AMSplitControl.start();
+ return;
+ }
+ dbg("AMDipP", "ActiveMessageC started!\n");
+ }
+
+ event void AMSplitControl.stopDone(error_t err) { }
+
+ command error_t Init.init() {
+ busy = FALSE;
+ return SUCCESS;
+ }
+
+ command error_t DipSend.send(uint8_t len) {
+ error_t err;
+ dbg("AMDipP", "Attempting to send data in the air\n");
+ err = call NetAMSend.send(AM_BROADCAST_ADDR, &am_msg, len);
+ if(err == SUCCESS) {
+ busy = TRUE;
+ }
+ return err;
+ }
+
+ command void* DipSend.getPayloadPtr() {
+ // returns NULL if message is busy
+ if(busy) {
+ return NULL;
+ }
+ return call NetAMSend.getPayload(&am_msg, 0);
+ }
+
+ command uint8_t DipSend.maxPayloadLength() {
+ return call NetAMSend.maxPayloadLength();
+ }
+
+ event void NetAMSend.sendDone(message_t* msg, error_t err) {
+ dbg("AMDipP", "Data send successfully in the air\n");
+ if(msg == &am_msg) {
+ busy = FALSE;
+ }
+ }
+
+ event message_t* NetReceive.receive(message_t* msg, void* payload,
+ uint8_t len) {
+ dip_msg_t* dmsg;
+ uint8_t type;
+
+ dmsg = (dip_msg_t*) payload;
+ type = dmsg->type;
+ switch(type) {
+ case ID_DIP_DATA:
+ signal DipDataReceive.receive(dmsg->content, len);
+ break;
+ case ID_DIP_VECTOR:
+ signal DipVectorReceive.receive(dmsg->content, len);
+ break;
+ case ID_DIP_SUMMARY:
+ signal DipSummaryReceive.receive(dmsg->content, len);
+ break;
+ }
+ return msg;
+ }
+
+}
+++ /dev/null
-
-#ifndef __DIP_H__
-#define __DIP_H__
-
-#define DIP_TAU_LOW (1024L)
-#define DIP_TAU_HIGH (65535L)
-
-#define UQ_DIP unique("DIP")
-#define UQCOUNT_DIP uniqueCount("DIP")
-
-#define DIP_UNKNOWN_VERSION 0xFFFFFFFF
-#define DIP_UNKNOWN_INDEX 0xFFFF
-
-typedef enum {
- ID_DIP_INVALID = 0x0,
- ID_DIP_SUMMARY = 0x1,
- ID_DIP_VECTOR = 0x2,
- ID_DIP_DATA = 0x3
-} dip_msgid_t;
-
-enum {
- AM_DIP = 0x84
-};
-
-typedef uint16_t dip_index_t;
-typedef uint16_t dip_key_t;
-typedef nx_uint16_t nx_dip_key_t;
-typedef uint32_t dip_version_t;
-typedef nx_uint32_t nx_dip_version_t;
-typedef uint8_t dip_estimate_t;
-typedef dip_index_t dip_hashlen_t;
-
-typedef nx_struct dip_msg_t {
- nx_uint8_t type; // dip_msgid_t
- nx_uint8_t content[0];
-} dip_msg_t;
-
-typedef nx_struct dip_data_msg_t {
- nx_dip_key_t key;
- nx_dip_version_t version;
- nx_uint8_t size;
- nx_uint8_t data[0];
-} dip_data_msg_t;
-
-typedef nx_struct dip_vector_msg_t {
- nx_uint8_t unitLen;
- nx_uint32_t vector[0];
-} dip_vector_msg_t;
-
-typedef nx_struct dip_summary_msg_t {
- nx_uint8_t unitLen;
- nx_uint32_t salt;
- nx_uint32_t info[0];
-} dip_summary_msg_t;
-
-dip_estimate_t DIP_DATA_ESTIMATE;
-dip_estimate_t DIP_MAX_ESTIMATE;
-dip_estimate_t DIP_VECTOR_ESTIMATE;
-
-#define DIP_SUMMARY_ENTRIES_PER_PACKET (DIP_SUMMARY_VALUES_PER_PACKET * 3)
-#define DIP_VECTOR_ENTRIES_PER_PACKET (DIP_VECTOR_VALUES_PER_PACKET * 2)
-
-#include "qsort.c"
-
-/* TUNABLE PARAMETERS */
-
-typedef struct dip_data_t {
- uint8_t data[16];
-} dip_data_t;
-
-#define DIP_SUMMARY_VALUES_PER_PACKET 2
-#define DIP_VECTOR_VALUES_PER_PACKET 2
-
-#endif
+++ /dev/null
-
-configuration DIPDataC {
- provides interface DIPDecision;
-
- uses interface DIPSend as DataSend;
- uses interface DIPReceive as DataReceive;
-
- uses interface DisseminationUpdate<dip_data_t>[dip_key_t key];
- uses interface DisseminationValue<dip_data_t>[dip_key_t key];
-
- uses interface DIPHelp;
- uses interface DIPEstimates;
-}
-
-implementation {
- components DIPDataP;
- DIPDecision = DIPDataP;
- DataSend = DIPDataP;
- DataReceive = DIPDataP;
- DisseminationUpdate = DIPDataP;
- DisseminationValue = DIPDataP;
- DIPHelp = DIPDataP;
- DIPEstimates = DIPDataP;
-
- components LedsC;
- DIPDataP.Leds -> LedsC;
-}
+++ /dev/null
-
-#include <DIP.h>
-
-module DIPDataP {
- provides interface DIPDecision;
-
- uses interface DIPSend as DataSend;
- uses interface DIPReceive as DataReceive;
-
- uses interface DisseminationUpdate<dip_data_t>[dip_key_t key];
- uses interface DisseminationValue<dip_data_t>[dip_key_t key];
-
- uses interface DIPHelp;
- uses interface DIPEstimates;
-
- uses interface Leds;
-}
-
-implementation {
- uint8_t commRate = 0;
-
- command uint8_t DIPDecision.getCommRate() {
- return commRate;
- }
-
- command void DIPDecision.resetCommRate() {
- commRate = 0;
- }
-
- command error_t DIPDecision.send() {
- // Scan all estimates and send the highest estimate in deterministic order
- dip_index_t i;
- dip_index_t high_i;
- dip_index_t high_est;
- dip_key_t key;
- dip_version_t ver;
- dip_estimate_t* ests;
- dip_msg_t* dmsg;
- dip_data_msg_t* ddmsg;
- const dip_data_t* data;
-
- ests = call DIPEstimates.getEstimates();
- high_i = 0;
- high_est = 0;
- for(i = 0; i < UQCOUNT_DIP; i++) {
- if(ests[i] > high_est) {
- high_i = i;
- high_est = ests[i];
- }
- }
- key = call DIPHelp.indexToKey(high_i);
- ver = call DIPHelp.keyToVersion(key);
- data = call DisseminationValue.get[key]();
- dmsg = (dip_msg_t*) call DataSend.getPayloadPtr();
- if(dmsg == NULL) {
- return FAIL;
- }
- ddmsg = (dip_data_msg_t*) dmsg->content;
- dmsg->type = ID_DIP_DATA;
-
- ddmsg->key = key;
- ddmsg->version = ver;
- ddmsg->size = sizeof(dip_data_t);
- memcpy(ddmsg->data, data, sizeof(dip_data_t));
-
- call DIPEstimates.decEstimateByKey(key);
- dbg("DIPDataP", "Data sent with key %x and version %08x\n", key, ver);
- return call DataSend.send(sizeof(dip_data_msg_t) + sizeof(dip_msg_t) + sizeof(dip_data_t));
- }
-
- event void DataReceive.receive(void* payload, uint8_t len) {
- dip_key_t key;
- dip_version_t myVer;
- dip_version_t msgVer;
- dip_data_msg_t* ddmsg;
-
- commRate = commRate + 1;
-
- ddmsg = (dip_data_msg_t*) payload;
- key = ddmsg->key;
- msgVer = ddmsg->version;
- myVer = call DIPHelp.keyToVersion(key);
- dbg("DIPDataP", "Data rcved with key %x and version %08x\n", key, msgVer);
-
- // TODO: handle the invalid versions
- if(myVer < msgVer) {
- call DisseminationUpdate.change[key]((dip_data_t*)ddmsg->data);
- call DIPHelp.setVersion(key, msgVer);
- call DIPEstimates.setDataEstimate(key);
- }
- else if (myVer > msgVer) {
- call DIPEstimates.setDataEstimate(key);
- }
- else {
- call DIPEstimates.decEstimateByKey(key);
- }
- }
-
- event void DisseminationValue.changed[dip_key_t key]() { }
-
- default command const dip_data_t* DisseminationValue.get[dip_key_t key]() {
- return NULL;
- }
-
- default command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) { }
-
-}
+++ /dev/null
-
-#include <DIP.h>
-
-configuration DIPLogicC {
- provides interface DisseminationUpdate<dip_data_t>[dip_key_t key];
-
- provides interface StdControl;
-}
-
-implementation {
- components DIPLogicP;
- DisseminationUpdate = DIPLogicP;
- StdControl = DIPLogicP;
-
- components MainC;
- MainC.SoftwareInit -> DIPLogicP;
- DIPLogicP.Boot -> MainC;
-
- components DIPTrickleMilliC;
- DIPLogicP.DIPTrickleTimer -> DIPTrickleMilliC;
-
- components DIPVersionC;
- DIPLogicP.VersionUpdate -> DIPVersionC;
- DIPLogicP.DIPHelp -> DIPVersionC;
-
- components AMDIPC;
-
- components DIPDataC;
- DIPLogicP.DIPDataDecision -> DIPDataC;
- DIPDataC.DataSend -> AMDIPC.DIPSend;
- DIPDataC.DataReceive -> AMDIPC.DataReceive;
- DIPDataC.DIPHelp -> DIPVersionC;
- DIPDataC.DIPEstimates -> DIPLogicP;
-
- components DIPVectorC;
- DIPLogicP.DIPVectorDecision -> DIPVectorC;
- DIPVectorC.VectorSend -> AMDIPC.DIPSend;
- DIPVectorC.VectorReceive -> AMDIPC.VectorReceive;
- DIPVectorC.DIPHelp -> DIPVersionC;
- DIPVectorC.DIPEstimates -> DIPLogicP;
-
- components DIPSummaryC;
- DIPLogicP.DIPSummaryDecision -> DIPSummaryC;
- DIPSummaryC.SummarySend -> AMDIPC.DIPSend;
- DIPSummaryC.SummaryReceive -> AMDIPC.SummaryReceive;
- DIPSummaryC.DIPHelp -> DIPVersionC;
- DIPSummaryC.DIPEstimates -> DIPLogicP;
-}
+++ /dev/null
-
-#include <DIP.h>
-
-module DIPLogicP {
- provides interface DisseminationUpdate<dip_data_t>[dip_key_t key];
- provides interface DIPEstimates;
-
- provides interface Init;
- provides interface StdControl;
-
- uses interface Boot;
- uses interface DIPTrickleTimer;
- uses interface DisseminationUpdate<dip_data_t> as VersionUpdate[dip_key_t key];
- uses interface DIPDecision as DIPDataDecision;
- uses interface DIPDecision as DIPVectorDecision;
- uses interface DIPDecision as DIPSummaryDecision;
- uses interface DIPHelp;
-}
-
-implementation {
- uint32_t windowSize;
- dip_hashlen_t totalPossible;
-
- dip_estimate_t estimates[UQCOUNT_DIP];
-
- uint16_t diplog(uint16_t base, uint16_t num);
- uint16_t dipexp(uint16_t base, uint16_t expt);
- dip_estimate_t getDataEstimate(dip_hashlen_t len);
- dip_estimate_t getMaxEstimate(dip_hashlen_t len);
- uint8_t sendDecision();
-
- command error_t Init.init() {
- windowSize = DIP_TAU_HIGH;
- DIP_DATA_ESTIMATE = getDataEstimate(UQCOUNT_DIP);
- DIP_MAX_ESTIMATE = getMaxEstimate(UQCOUNT_DIP);
- DIP_VECTOR_ESTIMATE = DIP_DATA_ESTIMATE - 1;
- totalPossible = call DIPEstimates.estimateToHashlength(0);
- dbg("DIPLogicP", "Real Total: %u, DIP Total: %u\n", UQCOUNT_DIP, totalPossible);
- if(totalPossible < UQCOUNT_DIP) {
- DIP_DATA_ESTIMATE++;
- DIP_MAX_ESTIMATE++;
- DIP_VECTOR_ESTIMATE++;
- totalPossible = call DIPEstimates.estimateToHashlength(0);
- }
- dbg("DIPLogicP", "Real Total: %u, DIP New Total: %u\n", UQCOUNT_DIP, totalPossible);
- dbg("DIPLogicP","DATA_ESTIMATE initialized to %u\n", DIP_DATA_ESTIMATE);
- dbg("DIPLogicP","MAX_ESTIMATE initialized to %u\n", DIP_MAX_ESTIMATE);
- dbg("DIPLogicP","VECT_ESTIMATE initialized to %u\n", DIP_VECTOR_ESTIMATE);
- dbg("DIPLogicP","DIP ready\n");
-
- return SUCCESS;
- }
-
- event void Boot.booted() {
-
- }
-
- command error_t StdControl.start() {
- return call DIPTrickleTimer.start();
- }
-
- command error_t StdControl.stop() {
- call DIPTrickleTimer.stop();
- return SUCCESS;
- }
-
- command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) {
- dip_index_t i;
-
- dbg("DIPLogicP","App notified key %x is new\n", key);
- i = call DIPHelp.keyToIndex(key);
- estimates[i] = DIP_DATA_ESTIMATE;
- call VersionUpdate.change[key](val);
- call DIPTrickleTimer.reset();
- }
-
- event uint32_t DIPTrickleTimer.requestWindowSize() {
- dip_index_t i;
- dip_estimate_t max = 0;
-
- for(i = 0; i < UQCOUNT_DIP; i++) {
- if(estimates[i] > 0) {
- max = estimates[i];
- windowSize = DIP_TAU_LOW;
- break;
- }
- }
- if(max == 0) {
- windowSize = windowSize << 1;
- if(windowSize > DIP_TAU_HIGH) {
- windowSize = DIP_TAU_HIGH;
- }
- }
-
- dbg("DIPLogicP", "Window size requested, give %u\n", windowSize);
- return windowSize;
- }
-
- event void DIPTrickleTimer.fired() {
- dip_index_t i;
- uint8_t decision;
-
- dbg("DIPLogicP","Trickle Timer fired!\n");
-
- for(i = 0; i < UQCOUNT_DIP; i++) {
- dbg("DIPLogicP","Index-%u Estimate-%u\n", i, estimates[i]);
- }
-
- decision = sendDecision();
-
- switch(decision) {
- case ID_DIP_INVALID:
- dbg("DIPLogicP", "Decision to SUPPRESS\n");
- break;
- case ID_DIP_SUMMARY:
- dbg("DIPLogicP", "Decision to SUMMARY\n");
- call DIPSummaryDecision.send();
- break;
- case ID_DIP_VECTOR:
- dbg("DIPLogicP", "Decision to VECTOR\n");
- call DIPVectorDecision.send();
- break;
- case ID_DIP_DATA:
- dbg("DIPLogicP", "Decision to DATA\n");
- call DIPDataDecision.send();
- break;
- }
- call DIPDataDecision.resetCommRate();
- call DIPVectorDecision.resetCommRate();
- call DIPSummaryDecision.resetCommRate();
- }
-
- command dip_estimate_t* DIPEstimates.getEstimates() {
- return estimates;
- }
-
- command void DIPEstimates.decEstimateByIndex(dip_index_t i) {
- if(estimates[i] != 0) {
- estimates[i] = estimates[i] - 1;
- }
- }
-
- command void DIPEstimates.decEstimateByKey(dip_key_t key) {
- dip_index_t i;
-
- i = call DIPHelp.keyToIndex(key);
- call DIPEstimates.decEstimateByIndex(i);
- }
-
- command dip_estimate_t DIPEstimates.hashlengthToEstimate(dip_hashlen_t len) {
- if(len == UQCOUNT_DIP) {
- len = totalPossible;
- }
- return DIP_MAX_ESTIMATE - diplog(DIP_SUMMARY_VALUES_PER_PACKET, len);
- }
-
- command dip_hashlen_t DIPEstimates.estimateToHashlength(dip_estimate_t est) {
- uint8_t expt, base;
- uint16_t val;
-
- base = DIP_SUMMARY_VALUES_PER_PACKET;
- expt = DIP_MAX_ESTIMATE - est;
- val = dipexp(base, expt);
-
- if(val > UQCOUNT_DIP) { // bring length back down if over UQCOUNT_DIP
- val = UQCOUNT_DIP;
- }
-
- return val;
- }
-
- /* Calculation functions */
- uint16_t diplog(uint16_t base, uint16_t num) {
- uint8_t counter;
-
- counter = 0;
- while(num != 0) {
- num = num / base;
- counter++;
- }
- return counter - 1;
- }
-
- command void DIPEstimates.setDataEstimate(dip_key_t key) {
- dip_index_t i;
-
- i = call DIPHelp.keyToIndex(key);
- estimates[i] = DIP_DATA_ESTIMATE;
- call DIPTrickleTimer.reset();
- }
-
- command void DIPEstimates.setVectorEstimate(dip_key_t key) {
- dip_index_t i;
-
- i = call DIPHelp.keyToIndex(key);
- if(estimates[i] < DIP_VECTOR_ESTIMATE) {
- estimates[i] = DIP_VECTOR_ESTIMATE;
- }
- call DIPTrickleTimer.reset();
- }
-
- command void DIPEstimates.setSummaryEstimateByIndex(dip_index_t ind,
- dip_estimate_t est) {
- if(estimates[ind] < est) {
- estimates[ind] = est;
- }
- call DIPTrickleTimer.reset();
- }
-
- uint16_t dipexp(uint16_t base, uint16_t expt) {
- uint16_t ans;
-
- ans = 1;
- while(expt > 0) {
- if((expt & 1) == 0) {
- base = base * base;
- expt = expt >> 1;
- }
- else {
- ans = ans * base;
- expt = expt - 1;
- }
- }
- return ans;
- }
-
- dip_estimate_t getDataEstimate(dip_hashlen_t len) {
- dip_estimate_t h_total;
- dip_estimate_t v_total;
-
- h_total = diplog(DIP_SUMMARY_VALUES_PER_PACKET, len);
- v_total = diplog(DIP_SUMMARY_VALUES_PER_PACKET,
- DIP_VECTOR_VALUES_PER_PACKET);
-
- return h_total - v_total + 1;
- }
-
- dip_estimate_t getMaxEstimate(dip_hashlen_t len) {
- return diplog(DIP_SUMMARY_VALUES_PER_PACKET, len);
- }
-
- uint8_t sendDecision() {
- dip_estimate_t highEst;
- dip_estimate_t est;
- uint8_t dataCommRate;
- uint8_t vectorCommRate;
- uint8_t summaryCommRate;
- dip_estimate_t* allEsts;
- dip_index_t i;
-
- uint16_t E, D, L, V, C;
-
- allEsts = call DIPEstimates.getEstimates();
- highEst = 0;
- dataCommRate = call DIPDataDecision.getCommRate();
- vectorCommRate = call DIPVectorDecision.getCommRate();
- summaryCommRate = call DIPSummaryDecision.getCommRate();
-
- if(dataCommRate > 1) {
- dbg("DIPLogicP", "Heard data\n");
- return ID_DIP_INVALID;
- }
-
- // if there is an estimate with highest estimate value, send
- for(i = 0; i < UQCOUNT_DIP; i++) {
- est = allEsts[i];
- if(est >= DIP_DATA_ESTIMATE) { return ID_DIP_DATA; }
- if(est > highEst) { highEst = est; };
- }
-
- // didn't send or hear data at this point
- if(vectorCommRate + summaryCommRate > 1) {
- dbg("DIPLogicP", "Heard an advertisement\n");
- return ID_DIP_INVALID;
- }
-
- // corner case, if hash is too short
- if(call DIPEstimates.estimateToHashlength(highEst) <= DIP_VECTOR_VALUES_PER_PACKET) {
- return ID_DIP_VECTOR;
- }
-
- // now we make the DIP decision
- C = dataCommRate + vectorCommRate + summaryCommRate;
- if(C == 0) C = 1; // don't want to divide by zero
- E = highEst;
- D = DIP_DATA_ESTIMATE;
- L = call DIPEstimates.estimateToHashlength(E);
- V = DIP_VECTOR_VALUES_PER_PACKET;
-
- dbg("DIPLogicP", "D=%u, E=%u, L=%u, V=%u, C=%u\n", D, E, L, V, C);
- if((D - E) < (L / (C * V))) {
- return ID_DIP_SUMMARY;
- }
- return ID_DIP_VECTOR;
- }
-
-}
+++ /dev/null
-
-configuration DIPSummaryC {
- provides interface DIPDecision;
-
- uses interface DIPSend as SummarySend;
- uses interface DIPReceive as SummaryReceive;
-
- uses interface DIPHelp;
- uses interface DIPEstimates;
-}
-
-implementation {
- components DIPSummaryP;
- DIPDecision = DIPSummaryP;
- SummarySend = DIPSummaryP;
- SummaryReceive = DIPSummaryP;
- DIPHelp = DIPSummaryP;
- DIPEstimates = DIPSummaryP;
-
- components RandomC;
- DIPSummaryP.Random -> RandomC;
-}
+++ /dev/null
-
-// Need to deal with non powers of base for the length of the hash
-
-#include <DIP.h>
-
-module DIPSummaryP {
- provides interface DIPDecision;
-
- uses interface DIPSend as SummarySend;
- uses interface DIPReceive as SummaryReceive;
-
- uses interface DIPHelp;
- uses interface DIPEstimates;
-
- uses interface Random;
-}
-
-implementation {
- void findRangeShadow(dip_index_t* left, dip_index_t *right);
- uint32_t buildRange(dip_index_t left, dip_index_t right);
- uint32_t computeHash(dip_index_t left, dip_index_t right,
- dip_version_t* basedata, uint32_t salt);
- uint32_t computeBloomHash(dip_index_t left, dip_index_t right,
- dip_version_t* basedata, uint32_t salt);
- void splitRange(uint32_t info, dip_index_t* left, dip_index_t* right);
- void adjustEstimatesSame(dip_index_t left, dip_index_t right);
- void adjustEstimatesDiff(dip_index_t left, dip_index_t rightt,
- dip_version_t* data, uint32_t salt,
- uint32_t bHash);
-
- uint8_t commRate;
- // this can be combined with pairs_t in DIPVectorP maybe?
- dip_estimate_t shadowEstimates[UQCOUNT_DIP];
-
- command uint8_t DIPDecision.getCommRate() {
- return commRate;
- }
-
- command void DIPDecision.resetCommRate() {
- commRate = 0;
- }
-
- command error_t DIPDecision.send() {
- dip_index_t i, j, left, right;
- dip_version_t* allVers;
- dip_estimate_t* allEsts;
- uint32_t salt;
-
- dip_msg_t* dmsg;
- dip_summary_msg_t* dsmsg;
-
- dmsg = (dip_msg_t*) call SummarySend.getPayloadPtr();
- dmsg->type = ID_DIP_SUMMARY;
- dsmsg = (dip_summary_msg_t*) dmsg->content;
-
- allVers = call DIPHelp.getAllVersions();
- allEsts = call DIPEstimates.getEstimates();
- salt = call Random.rand32();
-
- for(i = 0; i < UQCOUNT_DIP; i++) {
- shadowEstimates[i] = allEsts[i];
- }
-
- for(i = 0; i < DIP_SUMMARY_ENTRIES_PER_PACKET; i += 3) {
- findRangeShadow(&left, &right);
- dbg("DIPSummaryP", "Found range %u, %u\n", left, right);
- dsmsg->info[i] = buildRange(left, right);
- dsmsg->info[i+1] = computeHash(left, right, allVers, salt);
- dsmsg->info[i+2] = computeBloomHash(left, right, allVers, salt);
- for(j = left; j < right; j++) {
- shadowEstimates[j] = 0;
- }
- dbg("DIPSummaryP", "Hash Entry: %08x %08x %08x\n",
- dsmsg->info[i], dsmsg->info[i+1], dsmsg->info[i+2]);
- }
-
- dsmsg->unitLen = DIP_SUMMARY_ENTRIES_PER_PACKET;
- dsmsg->salt = salt;
-
- for(i = 0; i < DIP_SUMMARY_ENTRIES_PER_PACKET; i += 3) {
- splitRange(dsmsg->info[i], &left, &right);
- adjustEstimatesSame(left, right);
- }
-
- return call SummarySend.send(sizeof(dip_msg_t) +
- sizeof(dip_summary_msg_t) +
- (sizeof(uint32_t) * DIP_SUMMARY_ENTRIES_PER_PACKET));
- }
-
- event void SummaryReceive.receive(void* payload, uint8_t len) {
- dip_summary_msg_t* dsmsg;
- uint8_t unitlen;
- uint32_t salt, myHash;
- uint8_t i;
- dip_index_t left, right;
- dip_version_t* allVers;
-
- commRate = commRate + 1;
-
- dsmsg = (dip_summary_msg_t*) payload;
- unitlen = dsmsg->unitLen;
- salt = dsmsg->salt;
- allVers = call DIPHelp.getAllVersions();
-
- for(i = 0; i < unitlen; i += 3) {
- splitRange(dsmsg->info[i], &left, &right);
- myHash = computeHash(left, right, allVers, salt);
- if(myHash != dsmsg->info[i+1]) {
- // hashes don't match
- adjustEstimatesDiff(left, right, allVers, salt, dsmsg->info[i+2]);
- }
- else {
- // hashes match
- adjustEstimatesSame(left, right);
- }
- }
-
- }
-
- void findRangeShadow(dip_index_t* left, dip_index_t *right) {
- dip_estimate_t est1;
- dip_estimate_t est2;
- dip_hashlen_t len;
- dip_index_t highIndex;
- dip_index_t i;
- dip_index_t LBound;
- dip_index_t RBound;
- uint16_t runEstSum;
- uint16_t highEstSum;
-
- // find highest estimate
- // initialize test
- highIndex = 0;
- est1 = shadowEstimates[0];
-
- // Get the highest estimate key
- for(i = 0; i < UQCOUNT_DIP; i++) {
- est2 = shadowEstimates[i];
- if(est2 > est1) {
- highIndex = i;
- est1 = est2;
- }
- }
- len = call DIPEstimates.estimateToHashlength(est1);
- dbg("DIPSummaryP","Highest key at %u with estimate %u and thus len %u\n",
- highIndex, est1, len);
-
- // initialize bounds on range
- if(highIndex < len - 1) { LBound = 0; }
- else { LBound = highIndex - len + 1; }
- if(LBound + len > UQCOUNT_DIP) { RBound = UQCOUNT_DIP; }
- else { RBound = highIndex + len; }
-
- // adjust length if necessary
- if(RBound - LBound < len) { len = RBound - LBound; }
-
- // initialize first range
- highEstSum = 0;
- highIndex = LBound;
- for(i = LBound; i < LBound + len; i++) {
- est1 = shadowEstimates[i];
- highEstSum += est1;
- }
- dbg("DIPSummaryP", "First range: %u, %u = %u\n", LBound, LBound + len,
- highEstSum);
-
- // iterate through the range
- runEstSum = highEstSum;
- dbg("DIPSummaryP", "Iterating from %u to %u\n", LBound, RBound);
- for(i = LBound ; i + len <= RBound; i++) {
- est1 = shadowEstimates[i];
- est2 = shadowEstimates[i + len];
- runEstSum = runEstSum - est1 + est2;
- // dbg("Dissemination","Next sum: %u\n", runEstSum);
- if(runEstSum > highEstSum) {
- highEstSum = runEstSum;
- highIndex = i + 1;
- dbg("DIPSummaryP", "Next range: %u, %u = %u\n", highIndex,
- highIndex + len, highEstSum);
- }
- }
-
- // and finish
- *left = highIndex;
- *right = highIndex + len;
- }
-
- uint32_t buildRange(dip_index_t left, dip_index_t right) {
- uint32_t range;
-
- range = ((uint32_t) left << 16) | right;
- return range;
- }
-
- uint32_t computeHash(dip_index_t left, dip_index_t right,
- dip_version_t* basedata, uint32_t salt) {
- dip_index_t i;
- uint32_t hashValue = salt;
- uint8_t *sequence;
-
- if(right <= left) return 0;
- sequence = ((uint8_t*) (basedata + left));
-
- for(i = 0; i <= (right-left-1)*sizeof(dip_version_t); i++) {
- hashValue += sequence[i];
- hashValue += (hashValue << 10);
- hashValue ^= (hashValue >> 6);
- }
- hashValue += (hashValue << 3);
- hashValue ^= (hashValue >> 11);
- hashValue += (hashValue << 15);
- return hashValue;
- }
-
- uint32_t computeBloomHash(dip_index_t left, dip_index_t right,
- dip_version_t* basedata, uint32_t salt) {
- dip_index_t i;
- uint32_t bit;
- uint32_t returnHash;
- uint32_t indexSeqPair[2];
-
- returnHash = 0;
- for(i = left; i < right; i++) {
- indexSeqPair[0] = i;
- indexSeqPair[1] = basedata[i];
- bit = computeHash(0, 2, indexSeqPair, salt) % 32;
- returnHash |= (1 << bit);
- }
- return returnHash;
- }
-
- void splitRange(uint32_t info, dip_index_t* left, dip_index_t* right) {
- *right = info & 0xFFFF;
- *left = (info >> 16) & 0xFFFF;
- }
-
- void adjustEstimatesSame(dip_index_t left, dip_index_t right) {
- dip_index_t i;
-
- for(i = left; i < right; i++) {
- call DIPEstimates.decEstimateByIndex(i);
- }
- }
-
- void adjustEstimatesDiff(dip_index_t left, dip_index_t right,
- dip_version_t* data, uint32_t salt,
- uint32_t bHash) {
- dip_index_t i;
- dip_estimate_t est;
- dip_key_t key;
- uint32_t indexSeqPair[2];
- uint32_t bit;
-
- est = call DIPEstimates.hashlengthToEstimate(right - left) + 1; // + 1 to improve search
- for(i = left; i < right; i++) {
- indexSeqPair[0] = i;
- indexSeqPair[1] = data[i];
- bit = computeHash(0, 2, indexSeqPair, salt) % 32;
- key = call DIPHelp.indexToKey(i);
- if(bHash & (1 << bit)) {
- //set estimate only if better
- call DIPEstimates.setSummaryEstimateByIndex(i, est);
- }
- else {
- dbg("DisseminationDebug", "Key %x definitely different\n", key);
- call DIPEstimates.setVectorEstimate(key);
- }
- }
- }
-
-}
+++ /dev/null
-// $Id$
-/*
- * "Copyright (c) 2006 Stanford University. All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and
- * its documentation for any purpose, without fee, and without written
- * agreement is hereby granted, provided that the above copyright
- * notice, the following two paragraphs and the author appear in all
- * copies of this software.
- *
- * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
- * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
- * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
- * DAMAGE.
- *
- * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
- * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY
- * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
- * ENHANCEMENTS, OR MODIFICATIONS."
- */
-
-/*
- * Configuration that encapsulates the trickle timer implementation to
- * its needed services and initialization. For details on the working
- * of the parameters, please refer to Levis et al., "A Self-Regulating
- * Algorithm for Code Maintenance and Propagation in Wireless Sensor
- * Networks," NSDI 2004.
- *
- * @param l Lower bound of the time period in seconds.
- * @param h Upper bound of the time period in seconds.
- * @param k Redundancy constant.
- * @param count How many timers to provide.
- *
- * @author Philip Levis
- * @author Gilman Tolle
- * @date Jan 7 2006
- */
-
-
-configuration DIPTrickleMilliC {
- provides interface DIPTrickleTimer as TrickleTimer;
-}
-implementation {
- components DIPTrickleMilliP as TrickleP;
- components MainC, RandomC;
- components new TimerMilliC() as PeriodicIntervalTimer;
- components new TimerMilliC() as SingleEventTimer;
- components LedsC;
- TrickleTimer = TrickleP;
-
- TrickleP.PeriodicIntervalTimer -> PeriodicIntervalTimer;
- TrickleP.SingleEventTimer -> SingleEventTimer;
- TrickleP.Random -> RandomC;
-
- TrickleP.Leds -> LedsC;
- MainC.SoftwareInit -> TrickleP;
-}
-
-
+++ /dev/null
-// $Id$
-/*
- * "Copyright (c) 2006 Stanford University. All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and
- * its documentation for any purpose, without fee, and without written
- * agreement is hereby granted, provided that the above copyright
- * notice, the following two paragraphs and the author appear in all
- * copies of this software.
- *
- * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
- * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
- * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
- * DAMAGE.
- *
- * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
- * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY
- * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
- * ENHANCEMENTS, OR MODIFICATIONS."
- */
-
-/*
- * Module that provides a service instance of trickle timers. For
- * details on the working of the parameters, please refer to Levis et
- * al., "A Self-Regulating Algorithm for Code Maintenance and
- * Propagation in Wireless Sensor Networks," NSDI 2004.
- *
- * @param l Lower bound of the time period in seconds.
- * @param h Upper bound of the time period in seconds.
- * @param k Redundancy constant.
- * @param count How many timers to provide.
- *
- * @author Philip Levis
- * @author Gilman Tolle
- * @date Jan 7 2006
- */
-
-#include <Timer.h>
-#include <DIP.h>
-
-module DIPTrickleMilliP {
- provides {
- interface Init;
- interface DIPTrickleTimer as TrickleTimer;
- }
- uses {
- interface Timer<TMilli> as PeriodicIntervalTimer;
- interface Timer<TMilli> as SingleEventTimer;
- interface Random;
- interface Leds;
- }
-}
-implementation {
-
- uint32_t period;
-
- command error_t Init.init() {
- period = DIP_TAU_HIGH;
- return SUCCESS;
- }
-
- /**
- * Start a trickle timer. Reset the counter to 0.
- */
- command error_t TrickleTimer.start() {
- call PeriodicIntervalTimer.startOneShot(period);
- dbg("DIPTrickleMilliP",
- "Starting trickle timer @ %s\n", sim_time_string());
- return SUCCESS;
- }
-
- /**
- * Stop the trickle timer. This call sets the timer period to H.
- */
- command void TrickleTimer.stop() {
- call PeriodicIntervalTimer.stop();
- dbg("DIPTrickleMilliP",
- "Stopping trickle timer @ %s\n", sim_time_string());
- }
-
- /**
- * Reset the timer period to L. If called while the timer is running,
- * then a new interval (of length L) begins immediately.
- */
- command void TrickleTimer.reset() {
- period = DIP_TAU_LOW;
- call PeriodicIntervalTimer.stop();
- call PeriodicIntervalTimer.startOneShot(period);
- dbg("DIPTrickleMilliP",
- "Resetting trickle timer @ %s\n", sim_time_string());
- }
-
- command void TrickleTimer.maxInterval() {
- period = DIP_TAU_HIGH;
- }
-
- /**
- * The trickle timer has fired. Signaled if C > K.
- */
- event void PeriodicIntervalTimer.fired() {
- uint32_t dtfire;
-
- dtfire = (call Random.rand16() % (period / 2)) + (period / 2);
- dbg("DIPTrickleMilliP", "Scheduling Trickle event with %u\n", dtfire);
- call SingleEventTimer.startOneShot(dtfire);
- period = signal TrickleTimer.requestWindowSize();
- call PeriodicIntervalTimer.startOneShot(period);
- //call Leds.led0Toggle();
- }
-
- event void SingleEventTimer.fired() {
- dbg("Trickle", "Firing Trickle Event Timer\n");
- signal TrickleTimer.fired();
- }
-}
-
-
+++ /dev/null
-
-configuration DIPVectorC {
- provides interface DIPDecision;
-
- uses interface DIPSend as VectorSend;
- uses interface DIPReceive as VectorReceive;
-
- uses interface DIPHelp;
- uses interface DIPEstimates;
-}
-
-implementation {
- components DIPVectorP;
- DIPDecision = DIPVectorP;
- VectorSend = DIPVectorP;
- VectorReceive = DIPVectorP;
- DIPHelp = DIPVectorP;
- DIPEstimates = DIPVectorP;
-
- components RandomC;
- DIPVectorP.Random -> RandomC;
-
-}
+++ /dev/null
-
-#include <DIP.h>
-
-module DIPVectorP {
- provides interface DIPDecision;
-
- uses interface DIPSend as VectorSend;
- uses interface DIPReceive as VectorReceive;
-
- uses interface DIPHelp;
- uses interface DIPEstimates;
-
- uses interface Random;
-}
-
-implementation {
- uint8_t commRate = 0;
- typedef struct pairs_t {
- dip_estimate_t estimate;
- dip_key_t key;
- } pairs_t;
- pairs_t pairs[UQCOUNT_DIP]; // This is large memory footprint
-
- int myComparator(const void* a, const void* b);
- void randomizeRun(pairs_t* localPairs, dip_index_t length);
-
- command uint8_t DIPDecision.getCommRate() {
- return commRate;
- }
-
- command void DIPDecision.resetCommRate() {
- commRate = 0;
- }
-
- command error_t DIPDecision.send() {
- dip_index_t i, j, r;
- dip_key_t sendkey;
- dip_estimate_t* ests;
-
- dip_msg_t* dmsg;
- dip_vector_msg_t* dvmsg;
-
- dmsg = call VectorSend.getPayloadPtr();
- if(dmsg == NULL) {
- return FAIL;
- }
-
- ests = call DIPEstimates.getEstimates();
- // get all estimates and sort
- for(i = 0; i < UQCOUNT_DIP; i++) {
- pairs[i].key = call DIPHelp.indexToKey(i);
- pairs[i].estimate = ests[i];
- }
- qsort(pairs, UQCOUNT_DIP, sizeof(pairs_t), myComparator);
- j = pairs[0].estimate;
- r = 0;
- for(i = 0; i < UQCOUNT_DIP; i++) {
- if(pairs[i].estimate < j) {
- randomizeRun(&pairs[r], i - r);
- j = pairs[i].estimate;
- r = i;
- }
- }
- // randomize the last set
- randomizeRun(&pairs[r], UQCOUNT_DIP - r);
-
- // fill up the packet
- dmsg->type = ID_DIP_VECTOR;
- dvmsg = (dip_vector_msg_t*) dmsg->content;
- dvmsg->unitLen = DIP_VECTOR_ENTRIES_PER_PACKET;
- for(i = 0, j = 0;
- i < DIP_VECTOR_ENTRIES_PER_PACKET;
- i += 2, j++) {
- sendkey = pairs[j].key;
- dvmsg->vector[i] = sendkey;
- dvmsg->vector[i+1] = call DIPHelp.keyToVersion(sendkey);
- // adjust estimate
- call DIPEstimates.decEstimateByKey(sendkey);
- }
-
- return call VectorSend.send(sizeof(dip_msg_t) + sizeof(dip_vector_msg_t) +
- (DIP_VECTOR_ENTRIES_PER_PACKET * sizeof(uint32_t)));
- }
-
- event void VectorReceive.receive(void* payload, uint8_t len) {
- dip_vector_msg_t* dvmsg;
- uint8_t unitlen;
-
- uint8_t i;
- dip_key_t vectorkey;
- dip_version_t vectorver;
- dip_version_t myver;
-
- commRate = commRate + 1;
- dvmsg = (dip_vector_msg_t*) payload;
- unitlen = dvmsg->unitLen;
-
- for(i = 0; i < unitlen; i += 2) {
- vectorkey = dvmsg->vector[i];
- vectorver = dvmsg->vector[i+1];
- myver = call DIPHelp.keyToVersion(vectorkey);
-
- // TODO: handle the invalid versions
- if(myver < vectorver) {
- call DIPEstimates.setVectorEstimate(vectorkey);
- }
- else if(myver > vectorver) {
- call DIPEstimates.setDataEstimate(vectorkey);
- }
- else if(myver == vectorver) {
- call DIPEstimates.decEstimateByKey(vectorkey);
- }
- }
-
- }
-
- int myComparator(const void* a, const void* b) {
- const pairs_t *x = (const pairs_t *) a;
- const pairs_t *y = (const pairs_t *) b;
- if( x->estimate < y->estimate ) { return 1; }
- if( x->estimate > y->estimate ) { return -1; }
- return 0;
- }
-
- void randomizeRun(pairs_t* localPairs, dip_index_t length) {
- dip_index_t i,j;
- dip_index_t rLength = length;
- pairs_t temp;
-
- // don't move the last one
- for(i = 0; i < length - 1; i++, rLength--) {
- j = i + (call Random.rand16() % rLength);
- temp.key = localPairs[i].key;
- temp.estimate = localPairs[i].estimate;
- localPairs[i].key = localPairs[j].key;
- localPairs[i].estimate = localPairs[j].estimate;
- localPairs[j].key = temp.key;
- localPairs[j].estimate = temp.estimate;
- }
- }
-
-}
+++ /dev/null
-
-#include <DIP.h>
-
-configuration DIPVersionC {
- provides interface DIPHelp;
-
- provides interface DisseminationUpdate<dip_data_t>[dip_key_t key];
-}
-
-implementation {
- components DIPVersionP;
- DIPHelp = DIPVersionP;
- DisseminationUpdate = DIPVersionP;
-}
+++ /dev/null
-
-module DIPVersionP {
- provides interface DIPHelp;
-
- provides interface DisseminationUpdate<dip_data_t>[dip_key_t key];
-}
-
-implementation {
- int lessThan(const void* a, const void* b);
-
- // keys are ordered from smallest to largest.
- dip_key_t keys[UQCOUNT_DIP];
- dip_version_t versions[UQCOUNT_DIP];
- dip_index_t count = 0;
-
- command void DIPHelp.registerKey(dip_key_t key) {
- dip_index_t i;
-
- keys[count] = key;
- count = count + 1;
- if(count == UQCOUNT_DIP) {
- qsort(keys, UQCOUNT_DIP, sizeof(dip_key_t), lessThan);
- dbg("DIPVersionP","Key registration complete!\n");
- for(i = 0; i < UQCOUNT_DIP; i++) {
- dbg("DIPVersionP","Key %x\n", keys[i]);
- }
- }
- }
-
- command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) {
- dip_index_t i;
- dip_version_t ver;
-
- i = call DIPHelp.keyToIndex(key);
- ver = versions[i];
-
- // the version has node ID embedded in it, so need to do some shifts
- ver = ver >> 16;
- ver++;
- if ( ver == DIP_UNKNOWN_VERSION ) { ver++; }
- ver = ver << 16;
- ver += TOS_NODE_ID;
-
- versions[i] = ver;
- }
-
- command dip_index_t DIPHelp.keyToIndex(dip_key_t key) {
- dip_index_t answer;
- dip_index_t i;
-
- answer = DIP_UNKNOWN_INDEX;
- // linear search for now since it's easier
- for(i = 0; i < UQCOUNT_DIP; i++) {
- if(keys[i] == key) {
- answer = i;
- break;
- }
- }
- dbg("DIPVersionP", "Converting key %x to index %u\n", key, answer);
- return answer;
- }
-
- command dip_key_t DIPHelp.indexToKey(dip_index_t ind) {
- return keys[ind];
- }
-
- command dip_version_t DIPHelp.keyToVersion(dip_key_t key) {
- dip_index_t i;
-
- i = call DIPHelp.keyToIndex(key);
- return versions[i];
- }
-
- command void DIPHelp.setVersion(dip_key_t key, dip_version_t ver) {
- dip_index_t i;
-
- i = call DIPHelp.keyToIndex(key);
- versions[i] = ver;
- dbg("DIPVersionP","Setting key %x at index %u to version %x\n", key, i, ver);
- }
-
- command dip_version_t* DIPHelp.getAllVersions() {
- return versions;
- }
-
- int lessThan(const void* a, const void* b) {
- if ((*(dip_key_t*) a) < (*(dip_key_t*) b)) {
- return -1;
- }
- else if ((*(dip_key_t*) a) > (*(dip_key_t*) b)) {
- return 1;
- }
- return 0;
- }
-
- // binary search code which may be unstable
- /*
- dip_index_t answer;
-
- search_result = (dip_key_t*) bsearch(&key, &keys, UQCOUNT_DIP,
- sizeof(dip_key_t), lessThan);
- if(search_result == NULL) {
- return DIP_UNKNOWN_INDEX;
- }
- answer = search_result - keys;
- */
-}
--- /dev/null
+
+#ifndef __DIP_H__
+#define __DIP_H__
+
+#define DIP_TAU_LOW (1024L)
+#define DIP_TAU_HIGH (65535L)
+
+#define UQ_DIP unique("DIP")
+#define UQCOUNT_DIP uniqueCount("DIP")
+
+#define DIP_UNKNOWN_VERSION 0xFFFFFFFF
+#define DIP_UNKNOWN_INDEX 0xFFFF
+
+typedef enum {
+ ID_DIP_INVALID = 0x0,
+ ID_DIP_SUMMARY = 0x1,
+ ID_DIP_VECTOR = 0x2,
+ ID_DIP_DATA = 0x3
+} dip_msgid_t;
+
+enum {
+ AM_DIP = 0x84
+};
+
+typedef uint16_t dip_index_t;
+typedef uint16_t dip_key_t;
+typedef nx_uint16_t nx_dip_key_t;
+typedef uint32_t dip_version_t;
+typedef nx_uint32_t nx_dip_version_t;
+typedef uint8_t dip_estimate_t;
+typedef dip_index_t dip_hashlen_t;
+
+typedef nx_struct dip_msg_t {
+ nx_uint8_t type; // dip_msgid_t
+ nx_uint8_t content[0];
+} dip_msg_t;
+
+typedef nx_struct dip_data_msg_t {
+ nx_dip_key_t key;
+ nx_dip_version_t version;
+ nx_uint8_t size;
+ nx_uint8_t data[0];
+} dip_data_msg_t;
+
+typedef nx_struct dip_vector_msg_t {
+ nx_uint8_t unitLen;
+ nx_uint32_t vector[0];
+} dip_vector_msg_t;
+
+typedef nx_struct dip_summary_msg_t {
+ nx_uint8_t unitLen;
+ nx_uint32_t salt;
+ nx_uint32_t info[0];
+} dip_summary_msg_t;
+
+dip_estimate_t DIP_DATA_ESTIMATE;
+dip_estimate_t DIP_MAX_ESTIMATE;
+dip_estimate_t DIP_VECTOR_ESTIMATE;
+
+#define DIP_SUMMARY_ENTRIES_PER_PACKET (DIP_SUMMARY_VALUES_PER_PACKET * 3)
+#define DIP_VECTOR_ENTRIES_PER_PACKET (DIP_VECTOR_VALUES_PER_PACKET * 2)
+
+#include "qsort.c"
+
+/* TUNABLE PARAMETERS */
+
+typedef struct dip_data_t {
+ uint8_t data[16];
+} dip_data_t;
+
+#define DIP_SUMMARY_VALUES_PER_PACKET 2
+#define DIP_VECTOR_VALUES_PER_PACKET 2
+
+#endif
--- /dev/null
+
+configuration DipDataC {
+ provides interface DipDecision;
+
+ uses interface DipSend as DataSend;
+ uses interface DipReceive as DataReceive;
+
+ uses interface DisseminationUpdate<dip_data_t>[dip_key_t key];
+ uses interface DisseminationValue<dip_data_t>[dip_key_t key];
+
+ uses interface DipHelp;
+ uses interface DipEstimates;
+}
+
+implementation {
+ components DipDataP;
+ DipDecision = DipDataP;
+ DataSend = DipDataP;
+ DataReceive = DipDataP;
+ DisseminationUpdate = DipDataP;
+ DisseminationValue = DipDataP;
+ DipHelp = DipDataP;
+ DipEstimates = DipDataP;
+
+ components LedsC;
+ DipDataP.Leds -> LedsC;
+}
--- /dev/null
+
+#include <Dip.h>
+
+module DipDataP {
+ provides interface DipDecision;
+
+ uses interface DipSend as DataSend;
+ uses interface DipReceive as DataReceive;
+
+ uses interface DisseminationUpdate<dip_data_t>[dip_key_t key];
+ uses interface DisseminationValue<dip_data_t>[dip_key_t key];
+
+ uses interface DipHelp;
+ uses interface DipEstimates;
+
+ uses interface Leds;
+}
+
+implementation {
+ uint8_t commRate = 0;
+
+ command uint8_t DipDecision.getCommRate() {
+ return commRate;
+ }
+
+ command void DipDecision.resetCommRate() {
+ commRate = 0;
+ }
+
+ command error_t DipDecision.send() {
+ // Scan all estimates and send the highest estimate in deterministic order
+ dip_index_t i;
+ dip_index_t high_i;
+ dip_index_t high_est;
+ dip_key_t key;
+ dip_version_t ver;
+ dip_estimate_t* ests;
+ dip_msg_t* dmsg;
+ dip_data_msg_t* ddmsg;
+ const dip_data_t* data;
+
+ ests = call DipEstimates.getEstimates();
+ high_i = 0;
+ high_est = 0;
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ if(ests[i] > high_est) {
+ high_i = i;
+ high_est = ests[i];
+ }
+ }
+ key = call DipHelp.indexToKey(high_i);
+ ver = call DipHelp.keyToVersion(key);
+ data = call DisseminationValue.get[key]();
+ dmsg = (dip_msg_t*) call DataSend.getPayloadPtr();
+ if(dmsg == NULL) {
+ return FAIL;
+ }
+ ddmsg = (dip_data_msg_t*) dmsg->content;
+ dmsg->type = ID_DIP_DATA;
+
+ ddmsg->key = key;
+ ddmsg->version = ver;
+ ddmsg->size = sizeof(dip_data_t);
+ memcpy(ddmsg->data, data, sizeof(dip_data_t));
+
+ call DipEstimates.decEstimateByKey(key);
+ dbg("DipDataP", "Data sent with key %x and version %08x\n", key, ver);
+ return call DataSend.send(sizeof(dip_data_msg_t) + sizeof(dip_msg_t) + sizeof(dip_data_t));
+ }
+
+ event void DataReceive.receive(void* payload, uint8_t len) {
+ dip_key_t key;
+ dip_version_t myVer;
+ dip_version_t msgVer;
+ dip_data_msg_t* ddmsg;
+
+ commRate = commRate + 1;
+
+ ddmsg = (dip_data_msg_t*) payload;
+ key = ddmsg->key;
+ msgVer = ddmsg->version;
+ myVer = call DipHelp.keyToVersion(key);
+ dbg("DipDataP", "Data rcved with key %x and version %08x\n", key, msgVer);
+
+ // TODO: handle the invalid versions
+ if(myVer < msgVer) {
+ call DisseminationUpdate.change[key]((dip_data_t*)ddmsg->data);
+ call DipHelp.setVersion(key, msgVer);
+ call DipEstimates.setDataEstimate(key);
+ }
+ else if (myVer > msgVer) {
+ call DipEstimates.setDataEstimate(key);
+ }
+ else {
+ call DipEstimates.decEstimateByKey(key);
+ }
+ }
+
+ event void DisseminationValue.changed[dip_key_t key]() { }
+
+ default command const dip_data_t* DisseminationValue.get[dip_key_t key]() {
+ return NULL;
+ }
+
+ default command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) { }
+
+}
--- /dev/null
+
+#include <Dip.h>
+
+configuration DipLogicC {
+ provides interface DisseminationUpdate<dip_data_t>[dip_key_t key];
+
+ provides interface StdControl;
+}
+
+implementation {
+ components DipLogicP;
+ DisseminationUpdate = DipLogicP;
+ StdControl = DipLogicP;
+
+ components MainC;
+ MainC.SoftwareInit -> DipLogicP;
+ DipLogicP.Boot -> MainC;
+
+ components DipTrickleMilliC;
+ DipLogicP.DipTrickleTimer -> DipTrickleMilliC;
+
+ components DipVersionC;
+ DipLogicP.VersionUpdate -> DipVersionC;
+ DipLogicP.DipHelp -> DipVersionC;
+
+ components AMDipC;
+
+ components DipDataC;
+ DipLogicP.DipDataDecision -> DipDataC;
+ DipDataC.DataSend -> AMDipC.DipSend;
+ DipDataC.DataReceive -> AMDipC.DataReceive;
+ DipDataC.DipHelp -> DipVersionC;
+ DipDataC.DipEstimates -> DipLogicP;
+
+ components DipVectorC;
+ DipLogicP.DipVectorDecision -> DipVectorC;
+ DipVectorC.VectorSend -> AMDipC.DipSend;
+ DipVectorC.VectorReceive -> AMDipC.VectorReceive;
+ DipVectorC.DipHelp -> DipVersionC;
+ DipVectorC.DipEstimates -> DipLogicP;
+
+ components DipSummaryC;
+ DipLogicP.DipSummaryDecision -> DipSummaryC;
+ DipSummaryC.SummarySend -> AMDipC.DipSend;
+ DipSummaryC.SummaryReceive -> AMDipC.SummaryReceive;
+ DipSummaryC.DipHelp -> DipVersionC;
+ DipSummaryC.DipEstimates -> DipLogicP;
+}
--- /dev/null
+
+#include <Dip.h>
+
+module DipLogicP {
+ provides interface DisseminationUpdate<dip_data_t>[dip_key_t key];
+ provides interface DipEstimates;
+
+ provides interface Init;
+ provides interface StdControl;
+
+ uses interface Boot;
+ uses interface DipTrickleTimer;
+ uses interface DisseminationUpdate<dip_data_t> as VersionUpdate[dip_key_t key];
+ uses interface DipDecision as DipDataDecision;
+ uses interface DipDecision as DipVectorDecision;
+ uses interface DipDecision as DipSummaryDecision;
+ uses interface DipHelp;
+}
+
+implementation {
+ uint32_t windowSize;
+ dip_hashlen_t totalPossible;
+
+ dip_estimate_t estimates[UQCOUNT_DIP];
+
+ uint16_t diplog(uint16_t base, uint16_t num);
+ uint16_t dipexp(uint16_t base, uint16_t expt);
+ dip_estimate_t getDataEstimate(dip_hashlen_t len);
+ dip_estimate_t getMaxEstimate(dip_hashlen_t len);
+ uint8_t sendDecision();
+
+ command error_t Init.init() {
+ windowSize = DIP_TAU_HIGH;
+ DIP_DATA_ESTIMATE = getDataEstimate(UQCOUNT_DIP);
+ DIP_MAX_ESTIMATE = getMaxEstimate(UQCOUNT_DIP);
+ DIP_VECTOR_ESTIMATE = DIP_DATA_ESTIMATE - 1;
+ totalPossible = call DipEstimates.estimateToHashlength(0);
+ dbg("DipLogicP", "Real Total: %u, Dip Total: %u\n", UQCOUNT_DIP, totalPossible);
+ if(totalPossible < UQCOUNT_DIP) {
+ DIP_DATA_ESTIMATE++;
+ DIP_MAX_ESTIMATE++;
+ DIP_VECTOR_ESTIMATE++;
+ totalPossible = call DipEstimates.estimateToHashlength(0);
+ }
+ dbg("DipLogicP", "Real Total: %u, DIP New Total: %u\n", UQCOUNT_DIP, totalPossible);
+ dbg("DipLogicP","DATA_ESTIMATE initialized to %u\n", DIP_DATA_ESTIMATE);
+ dbg("DipLogicP","MAX_ESTIMATE initialized to %u\n", DIP_MAX_ESTIMATE);
+ dbg("DipLogicP","VECT_ESTIMATE initialized to %u\n", DIP_VECTOR_ESTIMATE);
+ dbg("DipLogicP","DIP ready\n");
+
+ return SUCCESS;
+ }
+
+ event void Boot.booted() {
+
+ }
+
+ command error_t StdControl.start() {
+ return call DipTrickleTimer.start();
+ }
+
+ command error_t StdControl.stop() {
+ call DipTrickleTimer.stop();
+ return SUCCESS;
+ }
+
+ command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) {
+ dip_index_t i;
+
+ dbg("DipLogicP","App notified key %x is new\n", key);
+ i = call DipHelp.keyToIndex(key);
+ estimates[i] = DIP_DATA_ESTIMATE;
+ call VersionUpdate.change[key](val);
+ call DipTrickleTimer.reset();
+ }
+
+ event uint32_t DipTrickleTimer.requestWindowSize() {
+ dip_index_t i;
+ dip_estimate_t max = 0;
+
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ if(estimates[i] > 0) {
+ max = estimates[i];
+ windowSize = DIP_TAU_LOW;
+ break;
+ }
+ }
+ if(max == 0) {
+ windowSize = windowSize << 1;
+ if(windowSize > DIP_TAU_HIGH) {
+ windowSize = DIP_TAU_HIGH;
+ }
+ }
+
+ dbg("DipLogicP", "Window size requested, give %u\n", windowSize);
+ return windowSize;
+ }
+
+ event void DipTrickleTimer.fired() {
+ dip_index_t i;
+ uint8_t decision;
+
+ dbg("DipLogicP","Trickle Timer fired!\n");
+
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ dbg("DipLogicP","Index-%u Estimate-%u\n", i, estimates[i]);
+ }
+
+ decision = sendDecision();
+
+ switch(decision) {
+ case ID_DIP_INVALID:
+ dbg("DipLogicP", "Decision to SUPPRESS\n");
+ break;
+ case ID_DIP_SUMMARY:
+ dbg("DipLogicP", "Decision to SUMMARY\n");
+ call DipSummaryDecision.send();
+ break;
+ case ID_DIP_VECTOR:
+ dbg("DipLogicP", "Decision to VECTOR\n");
+ call DipVectorDecision.send();
+ break;
+ case ID_DIP_DATA:
+ dbg("DipLogicP", "Decision to DATA\n");
+ call DipDataDecision.send();
+ break;
+ }
+ call DipDataDecision.resetCommRate();
+ call DipVectorDecision.resetCommRate();
+ call DipSummaryDecision.resetCommRate();
+ }
+
+ command dip_estimate_t* DipEstimates.getEstimates() {
+ return estimates;
+ }
+
+ command void DipEstimates.decEstimateByIndex(dip_index_t i) {
+ if(estimates[i] != 0) {
+ estimates[i] = estimates[i] - 1;
+ }
+ }
+
+ command void DipEstimates.decEstimateByKey(dip_key_t key) {
+ dip_index_t i;
+
+ i = call DipHelp.keyToIndex(key);
+ call DipEstimates.decEstimateByIndex(i);
+ }
+
+ command dip_estimate_t DipEstimates.hashlengthToEstimate(dip_hashlen_t len) {
+ if(len == UQCOUNT_DIP) {
+ len = totalPossible;
+ }
+ return DIP_MAX_ESTIMATE - diplog(DIP_SUMMARY_VALUES_PER_PACKET, len);
+ }
+
+ command dip_hashlen_t DipEstimates.estimateToHashlength(dip_estimate_t est) {
+ uint8_t expt, base;
+ uint16_t val;
+
+ base = DIP_SUMMARY_VALUES_PER_PACKET;
+ expt = DIP_MAX_ESTIMATE - est;
+ val = dipexp(base, expt);
+
+ if(val > UQCOUNT_DIP) { // bring length back down if over UQCOUNT_DIP
+ val = UQCOUNT_DIP;
+ }
+
+ return val;
+ }
+
+ /* Calculation functions */
+ uint16_t diplog(uint16_t base, uint16_t num) {
+ uint8_t counter;
+
+ counter = 0;
+ while(num != 0) {
+ num = num / base;
+ counter++;
+ }
+ return counter - 1;
+ }
+
+ command void DipEstimates.setDataEstimate(dip_key_t key) {
+ dip_index_t i;
+
+ i = call DipHelp.keyToIndex(key);
+ estimates[i] = DIP_DATA_ESTIMATE;
+ call DipTrickleTimer.reset();
+ }
+
+ command void DipEstimates.setVectorEstimate(dip_key_t key) {
+ dip_index_t i;
+
+ i = call DipHelp.keyToIndex(key);
+ if(estimates[i] < DIP_VECTOR_ESTIMATE) {
+ estimates[i] = DIP_VECTOR_ESTIMATE;
+ }
+ call DipTrickleTimer.reset();
+ }
+
+ command void DipEstimates.setSummaryEstimateByIndex(dip_index_t ind,
+ dip_estimate_t est) {
+ if(estimates[ind] < est) {
+ estimates[ind] = est;
+ }
+ call DipTrickleTimer.reset();
+ }
+
+ uint16_t dipexp(uint16_t base, uint16_t expt) {
+ uint16_t ans;
+
+ ans = 1;
+ while(expt > 0) {
+ if((expt & 1) == 0) {
+ base = base * base;
+ expt = expt >> 1;
+ }
+ else {
+ ans = ans * base;
+ expt = expt - 1;
+ }
+ }
+ return ans;
+ }
+
+ dip_estimate_t getDataEstimate(dip_hashlen_t len) {
+ dip_estimate_t h_total;
+ dip_estimate_t v_total;
+
+ h_total = diplog(DIP_SUMMARY_VALUES_PER_PACKET, len);
+ v_total = diplog(DIP_SUMMARY_VALUES_PER_PACKET,
+ DIP_VECTOR_VALUES_PER_PACKET);
+
+ return h_total - v_total + 1;
+ }
+
+ dip_estimate_t getMaxEstimate(dip_hashlen_t len) {
+ return diplog(DIP_SUMMARY_VALUES_PER_PACKET, len);
+ }
+
+ uint8_t sendDecision() {
+ dip_estimate_t highEst;
+ dip_estimate_t est;
+ uint8_t dataCommRate;
+ uint8_t vectorCommRate;
+ uint8_t summaryCommRate;
+ dip_estimate_t* allEsts;
+ dip_index_t i;
+
+ uint16_t E, D, L, V, C;
+
+ allEsts = call DipEstimates.getEstimates();
+ highEst = 0;
+ dataCommRate = call DipDataDecision.getCommRate();
+ vectorCommRate = call DipVectorDecision.getCommRate();
+ summaryCommRate = call DipSummaryDecision.getCommRate();
+
+ if(dataCommRate > 1) {
+ dbg("DipLogicP", "Heard data\n");
+ return ID_DIP_INVALID;
+ }
+
+ // if there is an estimate with highest estimate value, send
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ est = allEsts[i];
+ if(est >= DIP_DATA_ESTIMATE) { return ID_DIP_DATA; }
+ if(est > highEst) { highEst = est; };
+ }
+
+ // didn't send or hear data at this point
+ if(vectorCommRate + summaryCommRate > 1) {
+ dbg("DipLogicP", "Heard an advertisement\n");
+ return ID_DIP_INVALID;
+ }
+
+ // corner case, if hash is too short
+ if(call DipEstimates.estimateToHashlength(highEst) <= DIP_VECTOR_VALUES_PER_PACKET) {
+ return ID_DIP_VECTOR;
+ }
+
+ // now we make the DIP decision
+ C = dataCommRate + vectorCommRate + summaryCommRate;
+ if(C == 0) C = 1; // don't want to divide by zero
+ E = highEst;
+ D = DIP_DATA_ESTIMATE;
+ L = call DipEstimates.estimateToHashlength(E);
+ V = DIP_VECTOR_VALUES_PER_PACKET;
+
+ dbg("DipLogicP", "D=%u, E=%u, L=%u, V=%u, C=%u\n", D, E, L, V, C);
+ if((D - E) < (L / (C * V))) {
+ return ID_DIP_SUMMARY;
+ }
+ return ID_DIP_VECTOR;
+ }
+
+}
--- /dev/null
+
+configuration DipSummaryC {
+ provides interface DipDecision;
+
+ uses interface DipSend as SummarySend;
+ uses interface DipReceive as SummaryReceive;
+
+ uses interface DipHelp;
+ uses interface DipEstimates;
+}
+
+implementation {
+ components DipSummaryP;
+ DipDecision = DipSummaryP;
+ SummarySend = DipSummaryP;
+ SummaryReceive = DipSummaryP;
+ DipHelp = DipSummaryP;
+ DipEstimates = DipSummaryP;
+
+ components RandomC;
+ DipSummaryP.Random -> RandomC;
+}
--- /dev/null
+
+// Need to deal with non powers of base for the length of the hash
+
+#include <Dip.h>
+
+module DipSummaryP {
+ provides interface DipDecision;
+
+ uses interface DipSend as SummarySend;
+ uses interface DipReceive as SummaryReceive;
+
+ uses interface DipHelp;
+ uses interface DipEstimates;
+
+ uses interface Random;
+}
+
+implementation {
+ void findRangeShadow(dip_index_t* left, dip_index_t *right);
+ uint32_t buildRange(dip_index_t left, dip_index_t right);
+ uint32_t computeHash(dip_index_t left, dip_index_t right,
+ dip_version_t* basedata, uint32_t salt);
+ uint32_t computeBloomHash(dip_index_t left, dip_index_t right,
+ dip_version_t* basedata, uint32_t salt);
+ void splitRange(uint32_t info, dip_index_t* left, dip_index_t* right);
+ void adjustEstimatesSame(dip_index_t left, dip_index_t right);
+ void adjustEstimatesDiff(dip_index_t left, dip_index_t rightt,
+ dip_version_t* data, uint32_t salt,
+ uint32_t bHash);
+
+ uint8_t commRate;
+ // this can be combined with pairs_t in DIPVectorP maybe?
+ dip_estimate_t shadowEstimates[UQCOUNT_DIP];
+
+ command uint8_t DipDecision.getCommRate() {
+ return commRate;
+ }
+
+ command void DipDecision.resetCommRate() {
+ commRate = 0;
+ }
+
+ command error_t DipDecision.send() {
+ dip_index_t i, j, left, right;
+ dip_version_t* allVers;
+ dip_estimate_t* allEsts;
+ uint32_t salt;
+
+ dip_msg_t* dmsg;
+ dip_summary_msg_t* dsmsg;
+
+ dmsg = (dip_msg_t*) call SummarySend.getPayloadPtr();
+ dmsg->type = ID_DIP_SUMMARY;
+ dsmsg = (dip_summary_msg_t*) dmsg->content;
+
+ allVers = call DipHelp.getAllVersions();
+ allEsts = call DipEstimates.getEstimates();
+ salt = call Random.rand32();
+
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ shadowEstimates[i] = allEsts[i];
+ }
+
+ for(i = 0; i < DIP_SUMMARY_ENTRIES_PER_PACKET; i += 3) {
+ findRangeShadow(&left, &right);
+ dbg("DipSummaryP", "Found range %u, %u\n", left, right);
+ dsmsg->info[i] = buildRange(left, right);
+ dsmsg->info[i+1] = computeHash(left, right, allVers, salt);
+ dsmsg->info[i+2] = computeBloomHash(left, right, allVers, salt);
+ for(j = left; j < right; j++) {
+ shadowEstimates[j] = 0;
+ }
+ dbg("DipSummaryP", "Hash Entry: %08x %08x %08x\n",
+ dsmsg->info[i], dsmsg->info[i+1], dsmsg->info[i+2]);
+ }
+
+ dsmsg->unitLen = DIP_SUMMARY_ENTRIES_PER_PACKET;
+ dsmsg->salt = salt;
+
+ for(i = 0; i < DIP_SUMMARY_ENTRIES_PER_PACKET; i += 3) {
+ splitRange(dsmsg->info[i], &left, &right);
+ adjustEstimatesSame(left, right);
+ }
+
+ return call SummarySend.send(sizeof(dip_msg_t) +
+ sizeof(dip_summary_msg_t) +
+ (sizeof(uint32_t) * DIP_SUMMARY_ENTRIES_PER_PACKET));
+ }
+
+ event void SummaryReceive.receive(void* payload, uint8_t len) {
+ dip_summary_msg_t* dsmsg;
+ uint8_t unitlen;
+ uint32_t salt, myHash;
+ uint8_t i;
+ dip_index_t left, right;
+ dip_version_t* allVers;
+
+ commRate = commRate + 1;
+
+ dsmsg = (dip_summary_msg_t*) payload;
+ unitlen = dsmsg->unitLen;
+ salt = dsmsg->salt;
+ allVers = call DipHelp.getAllVersions();
+
+ for(i = 0; i < unitlen; i += 3) {
+ splitRange(dsmsg->info[i], &left, &right);
+ myHash = computeHash(left, right, allVers, salt);
+ if(myHash != dsmsg->info[i+1]) {
+ // hashes don't match
+ adjustEstimatesDiff(left, right, allVers, salt, dsmsg->info[i+2]);
+ }
+ else {
+ // hashes match
+ adjustEstimatesSame(left, right);
+ }
+ }
+
+ }
+
+ void findRangeShadow(dip_index_t* left, dip_index_t *right) {
+ dip_estimate_t est1;
+ dip_estimate_t est2;
+ dip_hashlen_t len;
+ dip_index_t highIndex;
+ dip_index_t i;
+ dip_index_t LBound;
+ dip_index_t RBound;
+ uint16_t runEstSum;
+ uint16_t highEstSum;
+
+ // find highest estimate
+ // initialize test
+ highIndex = 0;
+ est1 = shadowEstimates[0];
+
+ // Get the highest estimate key
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ est2 = shadowEstimates[i];
+ if(est2 > est1) {
+ highIndex = i;
+ est1 = est2;
+ }
+ }
+ len = call DipEstimates.estimateToHashlength(est1);
+ dbg("DipSummaryP","Highest key at %u with estimate %u and thus len %u\n",
+ highIndex, est1, len);
+
+ // initialize bounds on range
+ if(highIndex < len - 1) { LBound = 0; }
+ else { LBound = highIndex - len + 1; }
+ if(LBound + len > UQCOUNT_DIP) { RBound = UQCOUNT_DIP; }
+ else { RBound = highIndex + len; }
+
+ // adjust length if necessary
+ if(RBound - LBound < len) { len = RBound - LBound; }
+
+ // initialize first range
+ highEstSum = 0;
+ highIndex = LBound;
+ for(i = LBound; i < LBound + len; i++) {
+ est1 = shadowEstimates[i];
+ highEstSum += est1;
+ }
+ dbg("DipSummaryP", "First range: %u, %u = %u\n", LBound, LBound + len,
+ highEstSum);
+
+ // iterate through the range
+ runEstSum = highEstSum;
+ dbg("DipSummaryP", "Iterating from %u to %u\n", LBound, RBound);
+ for(i = LBound ; i + len <= RBound; i++) {
+ est1 = shadowEstimates[i];
+ est2 = shadowEstimates[i + len];
+ runEstSum = runEstSum - est1 + est2;
+ // dbg("Dissemination","Next sum: %u\n", runEstSum);
+ if(runEstSum > highEstSum) {
+ highEstSum = runEstSum;
+ highIndex = i + 1;
+ dbg("DipSummaryP", "Next range: %u, %u = %u\n", highIndex,
+ highIndex + len, highEstSum);
+ }
+ }
+
+ // and finish
+ *left = highIndex;
+ *right = highIndex + len;
+ }
+
+ uint32_t buildRange(dip_index_t left, dip_index_t right) {
+ uint32_t range;
+
+ range = ((uint32_t) left << 16) | right;
+ return range;
+ }
+
+ uint32_t computeHash(dip_index_t left, dip_index_t right,
+ dip_version_t* basedata, uint32_t salt) {
+ dip_index_t i;
+ uint32_t hashValue = salt;
+ uint8_t *sequence;
+
+ if(right <= left) return 0;
+ sequence = ((uint8_t*) (basedata + left));
+
+ for(i = 0; i <= (right-left-1)*sizeof(dip_version_t); i++) {
+ hashValue += sequence[i];
+ hashValue += (hashValue << 10);
+ hashValue ^= (hashValue >> 6);
+ }
+ hashValue += (hashValue << 3);
+ hashValue ^= (hashValue >> 11);
+ hashValue += (hashValue << 15);
+ return hashValue;
+ }
+
+ uint32_t computeBloomHash(dip_index_t left, dip_index_t right,
+ dip_version_t* basedata, uint32_t salt) {
+ dip_index_t i;
+ uint32_t bit;
+ uint32_t returnHash;
+ uint32_t indexSeqPair[2];
+
+ returnHash = 0;
+ for(i = left; i < right; i++) {
+ indexSeqPair[0] = i;
+ indexSeqPair[1] = basedata[i];
+ bit = computeHash(0, 2, indexSeqPair, salt) % 32;
+ returnHash |= (1 << bit);
+ }
+ return returnHash;
+ }
+
+ void splitRange(uint32_t info, dip_index_t* left, dip_index_t* right) {
+ *right = info & 0xFFFF;
+ *left = (info >> 16) & 0xFFFF;
+ }
+
+ void adjustEstimatesSame(dip_index_t left, dip_index_t right) {
+ dip_index_t i;
+
+ for(i = left; i < right; i++) {
+ call DipEstimates.decEstimateByIndex(i);
+ }
+ }
+
+ void adjustEstimatesDiff(dip_index_t left, dip_index_t right,
+ dip_version_t* data, uint32_t salt,
+ uint32_t bHash) {
+ dip_index_t i;
+ dip_estimate_t est;
+ dip_key_t key;
+ uint32_t indexSeqPair[2];
+ uint32_t bit;
+
+ est = call DipEstimates.hashlengthToEstimate(right - left) + 1; // + 1 to improve search
+ for(i = left; i < right; i++) {
+ indexSeqPair[0] = i;
+ indexSeqPair[1] = data[i];
+ bit = computeHash(0, 2, indexSeqPair, salt) % 32;
+ key = call DipHelp.indexToKey(i);
+ if(bHash & (1 << bit)) {
+ //set estimate only if better
+ call DipEstimates.setSummaryEstimateByIndex(i, est);
+ }
+ else {
+ dbg("DisseminationDebug", "Key %x definitely different\n", key);
+ call DipEstimates.setVectorEstimate(key);
+ }
+ }
+ }
+
+}
--- /dev/null
+// $Id$
+/*
+ * "Copyright (c) 2006 Stanford University. All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software and
+ * its documentation for any purpose, without fee, and without written
+ * agreement is hereby granted, provided that the above copyright
+ * notice, the following two paragraphs and the author appear in all
+ * copies of this software.
+ *
+ * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
+ * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
+ * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ *
+ * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
+ * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY
+ * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
+ * ENHANCEMENTS, OR MODIFICATIONS."
+ */
+
+/*
+ * Configuration that encapsulates the trickle timer implementation to
+ * its needed services and initialization. For details on the working
+ * of the parameters, please refer to Levis et al., "A Self-Regulating
+ * Algorithm for Code Maintenance and Propagation in Wireless Sensor
+ * Networks," NSDI 2004.
+ *
+ * @param l Lower bound of the time period in seconds.
+ * @param h Upper bound of the time period in seconds.
+ * @param k Redundancy constant.
+ * @param count How many timers to provide.
+ *
+ * @author Philip Levis
+ * @author Gilman Tolle
+ * @date Jan 7 2006
+ */
+
+
+configuration DipTrickleMilliC {
+ provides interface DipTrickleTimer as TrickleTimer;
+}
+implementation {
+ components DipTrickleMilliP as TrickleP;
+ components MainC, RandomC;
+ components new TimerMilliC() as PeriodicIntervalTimer;
+ components new TimerMilliC() as SingleEventTimer;
+ components LedsC;
+ TrickleTimer = TrickleP;
+
+ TrickleP.PeriodicIntervalTimer -> PeriodicIntervalTimer;
+ TrickleP.SingleEventTimer -> SingleEventTimer;
+ TrickleP.Random -> RandomC;
+
+ TrickleP.Leds -> LedsC;
+ MainC.SoftwareInit -> TrickleP;
+}
+
+
--- /dev/null
+// $Id$
+/*
+ * "Copyright (c) 2006 Stanford University. All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software and
+ * its documentation for any purpose, without fee, and without written
+ * agreement is hereby granted, provided that the above copyright
+ * notice, the following two paragraphs and the author appear in all
+ * copies of this software.
+ *
+ * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
+ * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
+ * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ *
+ * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
+ * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY
+ * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
+ * ENHANCEMENTS, OR MODIFICATIONS."
+ */
+
+/*
+ * Module that provides a service instance of trickle timers. For
+ * details on the working of the parameters, please refer to Levis et
+ * al., "A Self-Regulating Algorithm for Code Maintenance and
+ * Propagation in Wireless Sensor Networks," NSDI 2004.
+ *
+ * @param l Lower bound of the time period in seconds.
+ * @param h Upper bound of the time period in seconds.
+ * @param k Redundancy constant.
+ * @param count How many timers to provide.
+ *
+ * @author Philip Levis
+ * @author Gilman Tolle
+ * @date Jan 7 2006
+ */
+
+#include <Timer.h>
+#include <Dip.h>
+
+module DipTrickleMilliP {
+ provides {
+ interface Init;
+ interface DipTrickleTimer as TrickleTimer;
+ }
+ uses {
+ interface Timer<TMilli> as PeriodicIntervalTimer;
+ interface Timer<TMilli> as SingleEventTimer;
+ interface Random;
+ interface Leds;
+ }
+}
+implementation {
+
+ uint32_t period;
+
+ command error_t Init.init() {
+ period = DIP_TAU_HIGH;
+ return SUCCESS;
+ }
+
+ /**
+ * Start a trickle timer. Reset the counter to 0.
+ */
+ command error_t TrickleTimer.start() {
+ call PeriodicIntervalTimer.startOneShot(period);
+ dbg("DipTrickleMilliP",
+ "Starting trickle timer @ %s\n", sim_time_string());
+ return SUCCESS;
+ }
+
+ /**
+ * Stop the trickle timer. This call sets the timer period to H.
+ */
+ command void TrickleTimer.stop() {
+ call PeriodicIntervalTimer.stop();
+ dbg("DipTrickleMilliP",
+ "Stopping trickle timer @ %s\n", sim_time_string());
+ }
+
+ /**
+ * Reset the timer period to L. If called while the timer is running,
+ * then a new interval (of length L) begins immediately.
+ */
+ command void TrickleTimer.reset() {
+ period = DIP_TAU_LOW;
+ call PeriodicIntervalTimer.stop();
+ call PeriodicIntervalTimer.startOneShot(period);
+ dbg("DipTrickleMilliP",
+ "Resetting trickle timer @ %s\n", sim_time_string());
+ }
+
+ command void TrickleTimer.maxInterval() {
+ period = DIP_TAU_HIGH;
+ }
+
+ /**
+ * The trickle timer has fired. Signaled if C > K.
+ */
+ event void PeriodicIntervalTimer.fired() {
+ uint32_t dtfire;
+
+ dtfire = (call Random.rand16() % (period / 2)) + (period / 2);
+ dbg("DipTrickleMilliP", "Scheduling Trickle event with %u\n", dtfire);
+ call SingleEventTimer.startOneShot(dtfire);
+ period = signal TrickleTimer.requestWindowSize();
+ call PeriodicIntervalTimer.startOneShot(period);
+ //call Leds.led0Toggle();
+ }
+
+ event void SingleEventTimer.fired() {
+ dbg("Trickle", "Firing Trickle Event Timer\n");
+ signal TrickleTimer.fired();
+ }
+}
+
+
--- /dev/null
+
+configuration DipVectorC {
+ provides interface DipDecision;
+
+ uses interface DipSend as VectorSend;
+ uses interface DipReceive as VectorReceive;
+
+ uses interface DipHelp;
+ uses interface DipEstimates;
+}
+
+implementation {
+ components DipVectorP;
+ DipDecision = DipVectorP;
+ VectorSend = DipVectorP;
+ VectorReceive = DipVectorP;
+ DipHelp = DipVectorP;
+ DipEstimates = DipVectorP;
+
+ components RandomC;
+ DipVectorP.Random -> RandomC;
+
+}
--- /dev/null
+
+#include <Dip.h>
+
+module DipVectorP {
+ provides interface DipDecision;
+
+ uses interface DipSend as VectorSend;
+ uses interface DipReceive as VectorReceive;
+
+ uses interface DipHelp;
+ uses interface DipEstimates;
+
+ uses interface Random;
+}
+
+implementation {
+ uint8_t commRate = 0;
+ typedef struct pairs_t {
+ dip_estimate_t estimate;
+ dip_key_t key;
+ } pairs_t;
+ pairs_t pairs[UQCOUNT_DIP]; // This is large memory footprint
+
+ int myComparator(const void* a, const void* b);
+ void randomizeRun(pairs_t* localPairs, dip_index_t length);
+
+ command uint8_t DipDecision.getCommRate() {
+ return commRate;
+ }
+
+ command void DipDecision.resetCommRate() {
+ commRate = 0;
+ }
+
+ command error_t DipDecision.send() {
+ dip_index_t i, j, r;
+ dip_key_t sendkey;
+ dip_estimate_t* ests;
+
+ dip_msg_t* dmsg;
+ dip_vector_msg_t* dvmsg;
+
+ dmsg = call VectorSend.getPayloadPtr();
+ if(dmsg == NULL) {
+ return FAIL;
+ }
+
+ ests = call DipEstimates.getEstimates();
+ // get all estimates and sort
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ pairs[i].key = call DipHelp.indexToKey(i);
+ pairs[i].estimate = ests[i];
+ }
+ qsort(pairs, UQCOUNT_DIP, sizeof(pairs_t), myComparator);
+ j = pairs[0].estimate;
+ r = 0;
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ if(pairs[i].estimate < j) {
+ randomizeRun(&pairs[r], i - r);
+ j = pairs[i].estimate;
+ r = i;
+ }
+ }
+ // randomize the last set
+ randomizeRun(&pairs[r], UQCOUNT_DIP - r);
+
+ // fill up the packet
+ dmsg->type = ID_DIP_VECTOR;
+ dvmsg = (dip_vector_msg_t*) dmsg->content;
+ dvmsg->unitLen = DIP_VECTOR_ENTRIES_PER_PACKET;
+ for(i = 0, j = 0;
+ i < DIP_VECTOR_ENTRIES_PER_PACKET;
+ i += 2, j++) {
+ sendkey = pairs[j].key;
+ dvmsg->vector[i] = sendkey;
+ dvmsg->vector[i+1] = call DipHelp.keyToVersion(sendkey);
+ // adjust estimate
+ call DipEstimates.decEstimateByKey(sendkey);
+ }
+
+ return call VectorSend.send(sizeof(dip_msg_t) + sizeof(dip_vector_msg_t) +
+ (DIP_VECTOR_ENTRIES_PER_PACKET * sizeof(uint32_t)));
+ }
+
+ event void VectorReceive.receive(void* payload, uint8_t len) {
+ dip_vector_msg_t* dvmsg;
+ uint8_t unitlen;
+
+ uint8_t i;
+ dip_key_t vectorkey;
+ dip_version_t vectorver;
+ dip_version_t myver;
+
+ commRate = commRate + 1;
+ dvmsg = (dip_vector_msg_t*) payload;
+ unitlen = dvmsg->unitLen;
+
+ for(i = 0; i < unitlen; i += 2) {
+ vectorkey = dvmsg->vector[i];
+ vectorver = dvmsg->vector[i+1];
+ myver = call DipHelp.keyToVersion(vectorkey);
+
+ // TODO: handle the invalid versions
+ if(myver < vectorver) {
+ call DipEstimates.setVectorEstimate(vectorkey);
+ }
+ else if(myver > vectorver) {
+ call DipEstimates.setDataEstimate(vectorkey);
+ }
+ else if(myver == vectorver) {
+ call DipEstimates.decEstimateByKey(vectorkey);
+ }
+ }
+
+ }
+
+ int myComparator(const void* a, const void* b) {
+ const pairs_t *x = (const pairs_t *) a;
+ const pairs_t *y = (const pairs_t *) b;
+ if( x->estimate < y->estimate ) { return 1; }
+ if( x->estimate > y->estimate ) { return -1; }
+ return 0;
+ }
+
+ void randomizeRun(pairs_t* localPairs, dip_index_t length) {
+ dip_index_t i,j;
+ dip_index_t rLength = length;
+ pairs_t temp;
+
+ // don't move the last one
+ for(i = 0; i < length - 1; i++, rLength--) {
+ j = i + (call Random.rand16() % rLength);
+ temp.key = localPairs[i].key;
+ temp.estimate = localPairs[i].estimate;
+ localPairs[i].key = localPairs[j].key;
+ localPairs[i].estimate = localPairs[j].estimate;
+ localPairs[j].key = temp.key;
+ localPairs[j].estimate = temp.estimate;
+ }
+ }
+
+}
--- /dev/null
+
+#include <Dip.h>
+
+configuration DipVersionC {
+ provides interface DipHelp;
+
+ provides interface DisseminationUpdate<dip_data_t>[dip_key_t key];
+}
+
+implementation {
+ components DipVersionP;
+ DipHelp = DipVersionP;
+ DisseminationUpdate = DipVersionP;
+}
--- /dev/null
+
+module DipVersionP {
+ provides interface DipHelp;
+
+ provides interface DisseminationUpdate<dip_data_t>[dip_key_t key];
+}
+
+implementation {
+ int lessThan(const void* a, const void* b);
+
+ // keys are ordered from smallest to largest.
+ dip_key_t keys[UQCOUNT_DIP];
+ dip_version_t versions[UQCOUNT_DIP];
+ dip_index_t count = 0;
+
+ command void DipHelp.registerKey(dip_key_t key) {
+ dip_index_t i;
+
+ keys[count] = key;
+ count = count + 1;
+ if(count == UQCOUNT_DIP) {
+ qsort(keys, UQCOUNT_DIP, sizeof(dip_key_t), lessThan);
+ dbg("DipVersionP","Key registration complete!\n");
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ dbg("DipVersionP","Key %x\n", keys[i]);
+ }
+ }
+ }
+
+ command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) {
+ dip_index_t i;
+ dip_version_t ver;
+
+ i = call DipHelp.keyToIndex(key);
+ ver = versions[i];
+
+ // the version has node ID embedded in it, so need to do some shifts
+ ver = ver >> 16;
+ ver++;
+ if ( ver == DIP_UNKNOWN_VERSION ) { ver++; }
+ ver = ver << 16;
+ ver += TOS_NODE_ID;
+
+ versions[i] = ver;
+ }
+
+ command dip_index_t DipHelp.keyToIndex(dip_key_t key) {
+ dip_index_t answer;
+ dip_index_t i;
+
+ answer = DIP_UNKNOWN_INDEX;
+ // linear search for now since it's easier
+ for(i = 0; i < UQCOUNT_DIP; i++) {
+ if(keys[i] == key) {
+ answer = i;
+ break;
+ }
+ }
+ dbg("DipVersionP", "Converting key %x to index %u\n", key, answer);
+ return answer;
+ }
+
+ command dip_key_t DipHelp.indexToKey(dip_index_t ind) {
+ return keys[ind];
+ }
+
+ command dip_version_t DipHelp.keyToVersion(dip_key_t key) {
+ dip_index_t i;
+
+ i = call DipHelp.keyToIndex(key);
+ return versions[i];
+ }
+
+ command void DipHelp.setVersion(dip_key_t key, dip_version_t ver) {
+ dip_index_t i;
+
+ i = call DipHelp.keyToIndex(key);
+ versions[i] = ver;
+ dbg("DipVersionP","Setting key %x at index %u to version %x\n", key, i, ver);
+ }
+
+ command dip_version_t* DipHelp.getAllVersions() {
+ return versions;
+ }
+
+ int lessThan(const void* a, const void* b) {
+ if ((*(dip_key_t*) a) < (*(dip_key_t*) b)) {
+ return -1;
+ }
+ else if ((*(dip_key_t*) a) > (*(dip_key_t*) b)) {
+ return 1;
+ }
+ return 0;
+ }
+
+ // binary search code which may be unstable
+ /*
+ dip_index_t answer;
+
+ search_result = (dip_key_t*) bsearch(&key, &keys, UQCOUNT_DIP,
+ sizeof(dip_key_t), lessThan);
+ if(search_result == NULL) {
+ return DIP_UNKNOWN_INDEX;
+ }
+ answer = search_result - keys;
+ */
+}
-#include <DIP.h>
+#include <Dip.h>
configuration DisseminationC {
provides interface StdControl;
}
implementation {
- components DIPLogicC;
- StdControl = DIPLogicC;
+ components DipLogicC;
+ StdControl = DipLogicC;
}
-#include <DIP.h>
+#include <Dip.h>
/*
* Copyright (c) 2006 Arch Rock Corporation
components LedsC;
DisseminatorP.Leds -> LedsC;
- components DIPLogicC;
- DisseminatorP.DIPDisseminationUpdate -> DIPLogicC.DisseminationUpdate[key];
+ components DipLogicC;
+ DisseminatorP.DipDisseminationUpdate -> DipLogicC.DisseminationUpdate[key];
- components DIPVersionC;
- DisseminatorP.DIPHelp -> DIPVersionC;
+ components DipVersionC;
+ DisseminatorP.DipHelp -> DipVersionC;
components MainC;
MainC.SoftwareInit -> DisseminatorP;
- components DIPDataC;
- DIPDataC.DisseminationUpdate[key] -> DisseminatorP.DataDisseminationUpdate;
- DIPDataC.DisseminationValue[key] -> DisseminatorP.DataDisseminationValue;
+ components DipDataC;
+ DipDataC.DisseminationUpdate[key] -> DisseminatorP.DataDisseminationUpdate;
+ DipDataC.DisseminationValue[key] -> DisseminatorP.DataDisseminationValue;
}
provides interface Init;
- uses interface DisseminationUpdate<dip_data_t> as DIPDisseminationUpdate;
- uses interface DIPHelp;
+ uses interface DisseminationUpdate<dip_data_t> as DipDisseminationUpdate;
+ uses interface DipHelp;
uses interface Leds;
}
}
command error_t Init.init() {
- call DIPHelp.registerKey(key);
+ call DipHelp.registerKey(key);
return SUCCESS;
}
command void AppDisseminationUpdate.change( t* newVal ) {
memcpy( &valueCache, newVal, sizeof(t) );
/* Increment the counter and append the local node ID later. */
- /* DIPLogicC doesn't care what the data actually is,
+ /* DipLogicC doesn't care what the data actually is,
it just wants the key, so we cast it recklessly */
- call DIPDisseminationUpdate.change((dip_data_t*)newVal);
+ call DipDisseminationUpdate.change((dip_data_t*)newVal);
}
command const dip_data_t* DataDisseminationValue.get() {
-Title: DIP
+Title: Dip
Author: Kaisen Lin
------------------
-DIP is a dissemination protocol for detecting and disseminating new
-items in a network. It uses the same interfaces as Drip.
+Dip is a dissemination protocol for detecting and disseminating new
+items in a network. It uses the same interfaces as Drip. It improves
+node density and item scalability by sending only one packet per
+interval rather than many. If the network is small and with very few
+data items, Drip may be more efficient due to Dip's advertisement
+overhead.
-Data disseminated under DIP cannot be larger than 16 bytes. It was not
+
+
+Notes:
+------
+
+Data disseminated under Dip cannot be larger than 16 bytes. It was not
designed for large data items, but rather for many small data items.
Ties, like Drip, are handled with higher node IDs serving as
+++ /dev/null
-
-interface DIPDecision {
- command uint8_t getCommRate();
- command void resetCommRate();
- command error_t send();
-}
+++ /dev/null
-
-#include <DIP.h>
-
-interface DIPEstimates {
- command dip_estimate_t* getEstimates();
- command void decEstimateByIndex(dip_index_t i);
- command void decEstimateByKey(dip_key_t key);
- command dip_hashlen_t estimateToHashlength(dip_estimate_t est);
- command dip_estimate_t hashlengthToEstimate(dip_hashlen_t len);
- // special event to reset trickle timer too
- command void setDataEstimate(dip_key_t key);
- command void setVectorEstimate(dip_key_t key);
- command void setSummaryEstimateByIndex(dip_index_t ind,
- dip_estimate_t est);
-}
+++ /dev/null
-
-#include <DIP.h>
-
-interface DIPHelp {
- command void registerKey(dip_key_t key);
-
- command dip_index_t keyToIndex(dip_key_t key);
- command dip_key_t indexToKey(dip_index_t ind);
- command dip_version_t keyToVersion(dip_key_t key);
- command void setVersion(dip_key_t key, dip_version_t ver);
- command dip_version_t* getAllVersions();
-}
+++ /dev/null
-
-interface DIPReceive {
- event void receive(void* payload, uint8_t len);
-}
+++ /dev/null
-
-interface DIPSend {
- command error_t send(uint8_t len);
- command void* getPayloadPtr();
- command uint8_t maxPayloadLength();
-}
+++ /dev/null
-// $Id$
-/*
- * "Copyright (c) 2006 Stanford University. All rights reserved.
- *
- * Permission to use, copy, modify, and distribute this software and
- * its documentation for any purpose, without fee, and without written
- * agreement is hereby granted, provided that the above copyright
- * notice, the following two paragraphs and the author appear in all
- * copies of this software.
- *
- * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR
- * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
- * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
- * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
- * DAMAGE.
- *
- * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
- * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
- * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY
- * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
- * ENHANCEMENTS, OR MODIFICATIONS."
- */
-
-/*
- * A network trickle timer. A trickle timer has a period in the range
- * [L, H]. After firing, the period is doubled, up to H. If the period
- * is P, then the timer is scheduled to fire in the interval [0.5P, P]
- * (the second half of a period). The period can be reset to L (the
- * smallest period, and therefore the highest frequency).
- *
- * The timer may be suppressed. If a user of the interface has heard
- * enough packets from other nodes that indicate its transmitting a
- * packet would be unncessarily redundant, then the timer does not
- * fire. The timer has a constant K and a counter C. If C >e; K, then
- * the timer does not fire. When an interval ends, C is reset to 0.
- * Calling <tt>incrementCounter</tt> increments C by one.
- *
- * For details, refer to Levis et al., "A Self-Regulating Algorithm
- * for Code Maintenance and Propagation in Wireless Sensor Networks,"
- * NSDI 2004. The component providing this interface defines the
- * constants L, H, and K.
- *
- * @author Philip Levis
- * @date Jan 7 2006
- */
-
-
-interface DIPTrickleTimer {
-
- /**
- * Start the trickle timer. At boot, the timer period is its maximum
- * value (H). If a protocol requires starting at the minimum value
- * (e.g., fast start), then it should call <tt>reset</tt> before
- * <tt>start</tt>.
- *
- * @return error_t SUCCESS if the timer was started, EBUSY if it is already
- * running, and FAIL otherwise.
- */
- command error_t start();
-
- /**
- * Stop the trickle timer. This call sets the timer period to H and
- * C to 0.
- */
- command void stop();
-
- /**
- * Reset the timer period to L. If called while the timer is
- * running, then a new interval (of length L) begins immediately.
- */
- command void reset();
-
- /**
- * The trickle timer has fired. Signaled if C > K.
- */
- event void fired();
-
- /**
- * Compute the window size based on DIP's estimates
- */
- event uint32_t requestWindowSize();
-
- /**
- * Resets the timer period to H.
- */
- command void maxInterval();
-}
+++ /dev/null
-
-#include <DIP.h>
-
-interface DIPVersion {
- command void setVersion();
- command void incVersion();
-}
\ No newline at end of file
--- /dev/null
+
+interface DipDecision {
+ command uint8_t getCommRate();
+ command void resetCommRate();
+ command error_t send();
+}
--- /dev/null
+
+#include <Dip.h>
+
+interface DipEstimates {
+ command dip_estimate_t* getEstimates();
+ command void decEstimateByIndex(dip_index_t i);
+ command void decEstimateByKey(dip_key_t key);
+ command dip_hashlen_t estimateToHashlength(dip_estimate_t est);
+ command dip_estimate_t hashlengthToEstimate(dip_hashlen_t len);
+ // special event to reset trickle timer too
+ command void setDataEstimate(dip_key_t key);
+ command void setVectorEstimate(dip_key_t key);
+ command void setSummaryEstimateByIndex(dip_index_t ind,
+ dip_estimate_t est);
+}
--- /dev/null
+
+#include <Dip.h>
+
+interface DipHelp {
+ command void registerKey(dip_key_t key);
+
+ command dip_index_t keyToIndex(dip_key_t key);
+ command dip_key_t indexToKey(dip_index_t ind);
+ command dip_version_t keyToVersion(dip_key_t key);
+ command void setVersion(dip_key_t key, dip_version_t ver);
+ command dip_version_t* getAllVersions();
+}
--- /dev/null
+
+interface DipReceive {
+ event void receive(void* payload, uint8_t len);
+}
--- /dev/null
+
+interface DipSend {
+ command error_t send(uint8_t len);
+ command void* getPayloadPtr();
+ command uint8_t maxPayloadLength();
+}
--- /dev/null
+// $Id$
+/*
+ * "Copyright (c) 2006 Stanford University. All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software and
+ * its documentation for any purpose, without fee, and without written
+ * agreement is hereby granted, provided that the above copyright
+ * notice, the following two paragraphs and the author appear in all
+ * copies of this software.
+ *
+ * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
+ * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
+ * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ *
+ * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
+ * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY
+ * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
+ * ENHANCEMENTS, OR MODIFICATIONS."
+ */
+
+/*
+ * A network trickle timer. A trickle timer has a period in the range
+ * [L, H]. After firing, the period is doubled, up to H. If the period
+ * is P, then the timer is scheduled to fire in the interval [0.5P, P]
+ * (the second half of a period). The period can be reset to L (the
+ * smallest period, and therefore the highest frequency).
+ *
+ * The timer may be suppressed. If a user of the interface has heard
+ * enough packets from other nodes that indicate its transmitting a
+ * packet would be unncessarily redundant, then the timer does not
+ * fire. The timer has a constant K and a counter C. If C >e; K, then
+ * the timer does not fire. When an interval ends, C is reset to 0.
+ * Calling <tt>incrementCounter</tt> increments C by one.
+ *
+ * For details, refer to Levis et al., "A Self-Regulating Algorithm
+ * for Code Maintenance and Propagation in Wireless Sensor Networks,"
+ * NSDI 2004. The component providing this interface defines the
+ * constants L, H, and K.
+ *
+ * @author Philip Levis
+ * @date Jan 7 2006
+ */
+
+
+interface DipTrickleTimer {
+
+ /**
+ * Start the trickle timer. At boot, the timer period is its maximum
+ * value (H). If a protocol requires starting at the minimum value
+ * (e.g., fast start), then it should call <tt>reset</tt> before
+ * <tt>start</tt>.
+ *
+ * @return error_t SUCCESS if the timer was started, EBUSY if it is already
+ * running, and FAIL otherwise.
+ */
+ command error_t start();
+
+ /**
+ * Stop the trickle timer. This call sets the timer period to H and
+ * C to 0.
+ */
+ command void stop();
+
+ /**
+ * Reset the timer period to L. If called while the timer is
+ * running, then a new interval (of length L) begins immediately.
+ */
+ command void reset();
+
+ /**
+ * The trickle timer has fired. Signaled if C > K.
+ */
+ event void fired();
+
+ /**
+ * Compute the window size based on Dip's estimates
+ */
+ event uint32_t requestWindowSize();
+
+ /**
+ * Resets the timer period to H.
+ */
+ command void maxInterval();
+}
--- /dev/null
+
+#include <Dip.h>
+
+interface DipVersion {
+ command void setVersion();
+ command void incVersion();
+}
\ No newline at end of file
projects / tinyos-2.x.git / commitdiff