--- /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
+
+#include <DIP.h>
+
+configuration DisseminationC {
+ provides interface StdControl;
+}
+
+implementation {
+ components DIPLogicC;
+ StdControl = DIPLogicC;
+}
--- /dev/null
+#include <DIP.h>
+
+/*
+ * Copyright (c) 2006 Arch Rock Corporation
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * - Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the
+ * distribution.
+ * - Neither the name of the Arch Rock Corporation nor the names of
+ * its contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * ARCHED ROCK OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE
+ *
+ */
+
+/**
+ * The DisseminatorC component holds and synchronizes a single value
+ * of a chosen type, and identifies that value by a chosen 16-bit key.
+ * Different nodes should use the same key for the same value.
+ *
+ * See TEP118 - Dissemination for details.
+ *
+ * @param t the type of the object that will be disseminated
+ * @param key the 16-bit identifier of the disseminated object
+ *
+ * @author Gilman Tolle <gtolle@archrock.com>
+ * @version $Revision$ $Date$
+ */
+
+generic configuration DisseminatorC(typedef t, dip_key_t key) {
+ provides interface DisseminationValue<t>;
+ provides interface DisseminationUpdate<t>;
+}
+implementation {
+ enum {
+ JUST_NEED_COUNT = UQ_DIP
+ };
+
+ components new DisseminatorP(t, key);
+ DisseminationValue = DisseminatorP.AppDisseminationValue;
+ DisseminationUpdate = DisseminatorP.AppDisseminationUpdate;
+
+ components LedsC;
+ DisseminatorP.Leds -> LedsC;
+
+ components DIPLogicC;
+ DisseminatorP.DIPDisseminationUpdate -> DIPLogicC.DisseminationUpdate[key];
+
+ components DIPVersionC;
+ DisseminatorP.DIPHelp -> DIPVersionC;
+
+ components MainC;
+ MainC.SoftwareInit -> DisseminatorP;
+
+ components DIPDataC;
+ DIPDataC.DisseminationUpdate[key] -> DisseminatorP.DataDisseminationUpdate;
+ DIPDataC.DisseminationValue[key] -> DisseminatorP.DataDisseminationValue;
+}
--- /dev/null
+/*
+ * Copyright (c) 2006 Arch Rock Corporation
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * - Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the
+ * distribution.
+ * - Neither the name of the Arch Rock Corporation nor the names of
+ * its contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * ARCHED ROCK OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE
+ *
+ */
+
+/**
+ * The DisseminatorP module holds and synchronizes a single value of a
+ * chosen type.
+ *
+ * See TEP118 - Dissemination for details.
+ *
+ * @param t the type of the object that will be disseminated
+ *
+ * @author Gilman Tolle <gtolle@archrock.com>
+ * @version $Revision$ $Date$
+ */
+
+generic module DisseminatorP(typedef t, dip_key_t key) {
+ provides interface DisseminationValue<t> as AppDisseminationValue;
+ provides interface DisseminationUpdate<t> as AppDisseminationUpdate;
+ provides interface DisseminationUpdate<dip_data_t> as DataDisseminationUpdate;
+ provides interface DisseminationValue<dip_data_t> as DataDisseminationValue;
+
+ provides interface Init;
+
+ uses interface DisseminationUpdate<dip_data_t> as DIPDisseminationUpdate;
+ uses interface DIPHelp;
+
+ uses interface Leds;
+}
+implementation {
+ dip_data_t valueCache;
+
+ task void signalNewData() {
+ signal AppDisseminationValue.changed();
+ }
+
+ command error_t Init.init() {
+ call DIPHelp.registerKey(key);
+ return SUCCESS;
+ }
+
+ // A sequence number is 32 bits. The top 16 bits are an incrementing
+ // counter, while the bottom 16 bits are a unique node identifier.
+ // But versions aren't stored here.
+
+ command const t* AppDisseminationValue.get() {
+ return (t*) &valueCache;
+ }
+
+ command void AppDisseminationValue.set( const t* val ) {
+ memcpy( &valueCache, val, sizeof(t) );
+ }
+
+ 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,
+ it just wants the key, so we cast it recklessly */
+ call DIPDisseminationUpdate.change((dip_data_t*)newVal);
+ }
+
+ command const dip_data_t* DataDisseminationValue.get() {
+ return (dip_data_t*) &valueCache;
+ }
+
+ command void DataDisseminationValue.set( const dip_data_t* val ) { }
+
+ command void DataDisseminationUpdate.change( dip_data_t* newVal ) {
+ memcpy( &valueCache, newVal, sizeof(dip_data_t) );
+ //post signalNewData();
+ signal AppDisseminationValue.changed();
+ }
+
+
+ default event void AppDisseminationValue.changed() { }
+
+ default event void DataDisseminationValue.changed() { }
+
+}
--- /dev/null
+
+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.
+
+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
+tiebreakers.
+
+Key 0 is reserved, do not use it.
+
+There is minimal error checking, don't try to intentionally break
+it. (e.g. illegal keys, weird and wacky version numbers)
+
+Usage:
+------
+
+To use include the following in your Makefile:
+
+CFLAGS += -I$(TOSDIR)/lib/net
+CFLAGS += -I$(TOSDIR)/lib/net/dip
+CFLAGS += -I$(TOSDIR)/lib/net/dip/interfaces
--- /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
+/*-
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the University of
+ * California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+//#include <stdlib.h>
+
+typedef int cmp_t(const void *, const void *);
+static char *med3(char *, char *, char *, cmp_t *);
+static void swapfunc(char *, char *, int);
+
+#define min(a, b) ((a) < (b) ? (a) : (b))
+
+/*
+ * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
+ */
+#define swapcode(TYPE, parmi, parmj, n) { \
+ int i = (n) / sizeof (TYPE); \
+ register TYPE *pi = (TYPE *) (parmi); \
+ register TYPE *pj = (TYPE *) (parmj); \
+ do { \
+ register TYPE t = *pi; \
+ *pi++ = *pj; \
+ *pj++ = t; \
+ } while (--i > 0); \
+}
+
+static void
+swapfunc(char *a, char* b, int n)
+{
+ swapcode(char, a, b, n)
+}
+
+#define swap(a, b) swapfunc(a, b, es)
+
+#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n)
+
+static char *
+med3(char* a, char* b, char* c, cmp_t* cmp)
+{
+ return cmp(a, b) < 0 ?
+ (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
+ :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
+}
+
+void
+qsort(void* a, size_t n, size_t es, cmp_t* cmp)
+{
+ char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+ int d, r, swap_cnt;
+
+loop:
+ swap_cnt = 0;
+ if (n < 7) {
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
+ pl -= es)
+ swap(pl, pl - es);
+ return;
+ }
+ pm = (char *)a + (n / 2) * es;
+ if (n > 7) {
+ pl = a;
+ pn = (char *)a + (n - 1) * es;
+ if (n > 40) {
+ d = (n / 8) * es;
+ pl = med3(pl, pl + d, pl + 2 * d, cmp);
+ pm = med3(pm - d, pm, pm + d, cmp);
+ pn = med3(pn - 2 * d, pn - d, pn, cmp);
+ }
+ pm = med3(pl, pm, pn, cmp);
+ }
+ swap(a, pm);
+ pa = pb = (char *)a + es;
+
+ pc = pd = (char *)a + (n - 1) * es;
+ for (;;) {
+ while (pb <= pc && (r = cmp(pb, a)) <= 0) {
+ if (r == 0) {
+ swap_cnt = 1;
+ swap(pa, pb);
+ pa += es;
+ }
+ pb += es;
+ }
+ while (pb <= pc && (r = cmp(pc, a)) >= 0) {
+ if (r == 0) {
+ swap_cnt = 1;
+ swap(pc, pd);
+ pd -= es;
+ }
+ pc -= es;
+ }
+ if (pb > pc)
+ break;
+ swap(pb, pc);
+ swap_cnt = 1;
+ pb += es;
+ pc -= es;
+ }
+ if (swap_cnt == 0) { /* Switch to insertion sort */
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
+ pl -= es)
+ swap(pl, pl - es);
+ return;
+ }
+
+ pn = (char *)a + n * es;
+ r = min(pa - (char *)a, pb - pa);
+ vecswap(a, pb - r, r);
+ r = min(pd - pc, pn - pd - es);
+ vecswap(pb, pn - r, r);
+ if ((r = pb - pa) > es)
+ qsort(a, r / es, es, cmp);
+ if ((r = pd - pc) > es) {
+ /* Iterate rather than recurse to save stack space */
+ a = pn - r;
+ n = r / es;
+ goto loop;
+ }
+/* qsort(pn - r, r / es, es, cmp);*/
+}
projects / tinyos-2.x.git / commitdiff