00001
00002
00003 #ifndef landmark_h_
00004 #define landmark_h_
00005
00006 #include <agent.h>
00007 #include <ip.h>
00008 #include <delay.h>
00009 #include <scheduler.h>
00010 #include <queue.h>
00011 #include <trace.h>
00012 #include <arp.h>
00013 #include <ll.h>
00014 #include <mac.h>
00015 #include <priqueue.h>
00016 #include <mobilenode.h>
00017 #include "tags.h"
00018 #include "agent-list.h"
00019
00020 typedef double Time;
00021
00022 #define ROUTER_PORT 255
00023 #define QUERY_PORT 0
00024
00025 #define NOT_CHILD 0
00026 #define IS_CHILD 1
00027 #define NOT_POTL_CHILD 2 // Not within appropriate vicinity
00028
00029 #define NO_PARENT 60000
00030
00031 #define OLD_ENTRY 0 // Object already exists in list
00032 #define NEW_ENTRY 1 // New object created in list
00033 #define OLD_MESSAGE 2 // Old information; Object not added to list
00034 #define ENTRY_NOT_FOUND 3 // Object not found
00035 #define NEW_CHILD 4 // New child added
00036 #define OLD_CHILD_TAGS_CHANGED 5
00037
00038 #define TRUE 1
00039 #define FALSE 0
00040
00041 #define MAX_ENERGY 100000
00042 #define MAX_LEVELS 8
00043 #define MAX_CHILDREN 30
00044 #define MAX_DEMOTION_RECORDS 20
00045
00046 #define INITIAL_WAIT_TIME 10.0
00047 #define PERIODIC_WAIT_TIME 60.0
00048 #define LM_STARTUP_JITTER 10.0 // secs to jitter LM's periodic adverts
00049 #define IP_HDR_SIZE 20 // 20 byte IP header as in the Internet
00050 #define WAIT_TIME 2 // 1s for each hop; round-trip is 2
00051 #define MAX_TIMEOUT 200 // Value divided by local population density and
00052
00053 #define CONST_TIMEOUT 10 // Constant portion of timeout across levels
00054
00055 #define LOW_FREQ_UPDATE 300
00056 #define PROMO_TIMEOUT_MULTIPLES 1 // Used in promotion timer
00057
00058 #define DEMOTION 0 // update pkt should advertise demotion
00059 #define PERIODIC_ADVERTS 1 // periodic update for each level node is at
00060 #define UNICAST_ADVERT_CHILD 2
00061 #define UNICAST_ADVERT_PARENT 3
00062 #define GLOBAL_ADVERT 4 // global advertisement from root LM
00063 #define QUERY_PKT 5 // query/response pkt
00064 #define DIR_QUERY_PKT 6
00065 #define DIR_RESPONSE_PKT 7
00066 #define OBJECT_QUERY_PKT 8
00067 #define OBJECT_RESPONSE_PKT 9
00068 #define HASH_PKT 10
00069 #define HASH_ACK_PKT 11
00070 #define REHASH_PKT 12
00071
00072 #define FLOOD 0
00073 #define UNICAST 1
00074 #define SUPPRESS 2
00075
00076 #define DEMOTION_RATIO 1.3
00077 #define DEMOTION_DIFF 5000
00078
00079 #define NO_NEXT_HOP 50000
00080 #define MAX_CACHE_ITEMS 200
00081
00082 #define NO_GLOBAL_LM 60000
00083
00084
00085 class TagMobilityHandler;
00086 class TagAdvtHandler;
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098 class aggreg_taglist {
00099 public:
00100 aggreg_taglist() { marked_ = 0; next_ = NULL;}
00101 int obj_name_;
00102 int marked_;
00103 aggreg_taglist *next_;
00104 };
00105
00106
00107
00108
00109
00110 class LMAddrs {
00111 public:
00112 LMAddrs() {
00113 lmaddr_ = 0;
00114 num_lm_addrs_ = 0;
00115 }
00116
00117 ~LMAddrs() {
00118 delete_lm_addrs();
00119 }
00120
00121 void add_lm_addr(int64_t lmaddr) {
00122 int i = 0;
00123 assert(num_lm_addrs_ >= 0);
00124
00125 if(num_lm_addrs_) {
00126 int64_t *tmp_addrs = new int64_t[num_lm_addrs_];
00127 for(i = 0; i < num_lm_addrs_; ++i) {
00128 tmp_addrs[i] = lmaddr_[i];
00129 }
00130 delete[] lmaddr_;
00131
00132 lmaddr_ = new int64_t[num_lm_addrs_+1];
00133 for(i = 0; i < num_lm_addrs_; ++i) {
00134 lmaddr_[i] = tmp_addrs[i];
00135 }
00136 delete[] tmp_addrs;
00137 }
00138 else
00139 lmaddr_ = new int64_t[num_lm_addrs_+1];
00140
00141 lmaddr_[num_lm_addrs_] = lmaddr;
00142 ++num_lm_addrs_;
00143 }
00144
00145 void delete_lm_addrs() {
00146 if(!num_lm_addrs_) return;
00147 num_lm_addrs_ = 0;
00148 delete[] lmaddr_;
00149 lmaddr_ = NULL;
00150 }
00151
00152 void get_lm_addrs(int *num_lm_addrs, int64_t **lmaddr) {
00153 *num_lm_addrs = num_lm_addrs_;
00154 *lmaddr = NULL;
00155 if(num_lm_addrs_) {
00156 *lmaddr = new int64_t[num_lm_addrs_];
00157 for(int i = 0; i < num_lm_addrs_; ++i) {
00158 (*lmaddr)[i] = lmaddr_[i];
00159 }
00160 }
00161 }
00162
00163 int match_lm_addr(int *addr, int level) {
00164 int i[8];
00165 int num_addrs = 0;
00166 int match = FALSE;
00167
00168 assert(level < 8);
00169
00170 for(num_addrs = 0; num_addrs < num_lm_addrs_; ++num_addrs) {
00171 i[7] = (lmaddr_[num_addrs] >> 56) & 0xFF;
00172 i[6] = (lmaddr_[num_addrs] >> 48) & 0xFF;
00173 i[5] = (lmaddr_[num_addrs] >> 40) & 0xFF;
00174 i[4] = (lmaddr_[num_addrs] >> 32) & 0xFF;
00175 i[3] = (lmaddr_[num_addrs] >> 24) & 0xFF;
00176 i[2] = (lmaddr_[num_addrs] >> 16) & 0xFF;
00177 i[1] = (lmaddr_[num_addrs] >> 8) & 0xFF;
00178 i[0] = (lmaddr_[num_addrs]) & 0xFF;
00179
00180 match = TRUE;
00181 for(int j = 7; j >= level; --j) {
00182 if(addr[j] != i[j]) {
00183 match = FALSE;
00184 break;
00185 }
00186 }
00187 if(match == TRUE)
00188 return(match);
00189 }
00190 return(match);
00191 }
00192
00193 private:
00194 int64_t *lmaddr_;
00195 int num_lm_addrs_;
00196 };
00197
00198
00199
00200
00201 class RecentMsgRecord {
00202 public:
00203 RecentMsgRecord() {
00204 id_ = 60000;
00205 level_ = -1;
00206 origin_time_ = 0;
00207 }
00208 nsaddr_t id_;
00209 int level_;
00210 int origin_time_;
00211 };
00212
00213
00214
00215 class NodeIDList {
00216 public:
00217 NodeIDList() {
00218 next_ = NULL;
00219 }
00220 nsaddr_t dst_node_;
00221 nsaddr_t dst_next_hop_;
00222 int next_hop_level_;
00223 NodeIDList *next_;
00224 };
00225
00226
00227 class LMNode {
00228 friend class ParentChildrenList;
00229 friend class LandmarkAgent;
00230 friend class PromotionTimer;
00231 public:
00232 LMNode(nsaddr_t id, nsaddr_t next_hop, int num_hops, int level, int num_children, int energy, int origin_time, double update_time) {
00233 id_ = id;
00234 lmaddr_ = new LMAddrs;
00235 next_hop_ = next_hop;
00236 child_flag_ = NOT_CHILD;
00237 num_hops_ = num_hops;
00238 level_ = level;
00239 num_children_ = num_children;
00240 energy_ = energy;
00241 last_upd_origin_time_ = origin_time;
00242 last_upd_seqnum_ = -1;
00243 last_update_rcvd_ = update_time;
00244 tag_list_ = NULL;
00245 next_ = NULL;
00246 }
00247
00248 ~LMNode() {
00249 compr_taglist *tag_ptr1, *tag_ptr2;
00250 tag_ptr1 = tag_list_;
00251 while(tag_ptr1) {
00252 tag_ptr2 = tag_ptr1;
00253 tag_ptr1 = tag_ptr1->next_;
00254 delete tag_ptr2;
00255 }
00256 delete lmaddr_;
00257 }
00258
00259 nsaddr_t id_;
00260 LMAddrs *lmaddr_;
00261 nsaddr_t next_hop_;
00262 int child_flag_;
00263 int num_hops_;
00264 int level_;
00265 int num_children_;
00266 int energy_;
00267 int last_upd_origin_time_;
00268 int last_upd_seqnum_;
00269
00270 double last_update_rcvd_;
00271 compr_taglist *tag_list_;
00272 LMNode *next_;
00273
00274 void copy_tag_list(compr_taglist *taglist);
00275 };
00276
00277
00278
00279 class LMEvent : public Event {
00280 public:
00281 int level_;
00282 LMEvent(int level) : Event() {level_ = level;}
00283 };
00284
00285
00286 class ParentChildrenList {
00287 friend class LandmarkAgent;
00288 friend class LMNode;
00289 friend class PromotionTimer;
00290 friend class LMPeriodicAdvtHandler;
00291 public:
00292 ParentChildrenList(int level, LandmarkAgent *a);
00293 ~ParentChildrenList() {
00294 LMNode *node1, *node2;
00295
00296 node1 = pchildren_;
00297 while(node1) {
00298 node2 = node1;
00299 node1 = node1->next_;
00300 delete node2;
00301 }
00302
00303 node1 = pparent_;
00304 while(node1) {
00305 node2 = node1;
00306 node1 = node1->next_;
00307 delete node2;
00308 }
00309
00310
00311 if(periodic_update_event_->uid_) {
00312 Scheduler &s = Scheduler::instance();
00313 s.cancel(periodic_update_event_);
00314 }
00315 delete mylmaddrs_;
00316 }
00317
00318
00319
00320
00321
00322
00323
00324
00325 int level_;
00326 LMNode *parent_;
00327 int num_heard_;
00328
00329
00330 int num_children_;
00331 int num_potl_children_;
00332 int num_pparent_;
00333 LMNode *pchildren_;
00334 LMNode *pparent_;
00335
00336
00337 int seqnum_;
00338 double last_update_sent_;
00339 double update_period_;
00340 double update_timeout_;
00341 Event *periodic_update_event_;
00342
00343 LMPeriodicAdvtHandler *periodic_handler_;
00344
00345 ParentChildrenList *next_;
00346 int update_round_;
00347
00348
00349
00350
00351
00352
00353
00354
00355 int UpdatePotlParent(nsaddr_t id, nsaddr_t next_hop, int num_hops, int level,int num_children, int energy, int origin_time, int delete_flag);
00356 int UpdatePotlChild(nsaddr_t id, nsaddr_t next_hop, int num_hops, int level, int num_children, int energy, int origin_time, int child_flag, int delete_flag, compr_taglist *taglist);
00357 void UpdateChildLMAddr(nsaddr_t id, int num_lm_addrs, int64_t *lm_addrs);
00358
00359 LandmarkAgent *a_;
00360 compr_taglist *tag_list_;
00361 int num_tags_;
00362
00363 int adverts_type_;
00364
00365 LMAddrs *mylmaddrs_;
00366
00367
00368 };
00369
00370
00371 #define HIER_ADVS 0
00372 #define OBJECT_ADVS 1
00373 #define HIER_AND_OBJECT_ADVS 2
00374
00375 class LandmarkAgent : public Agent {
00376 friend class LMPeriodicAdvtHandler;
00377 friend class PromotionTimer;
00378 friend class ParentChildrenList;
00379 public:
00380 LandmarkAgent();
00381 virtual int command(int argc, const char * const * argv);
00382
00383
00384
00385
00386 PromotionTimer *promo_timer_;
00387 double promo_start_time_;
00388 double promo_timeout_;
00389 double promo_timeout_decr_;
00390
00391 int promo_timer_running_;
00392
00393 void startUp();
00394 virtual void stop();
00395 int seqno_;
00396 int myaddr_;
00397
00398
00399
00400 virtual void periodic_callback(Event *e, int level);
00401
00402 int highest_level_;
00403
00404
00405
00406 ParentChildrenList *parent_children_list_;
00407 void Addparent(const nsaddr_t parent, int level);
00408
00409 void Addpotentialchild(const nsaddr_t child, int level);
00410
00411
00412
00413
00414 virtual Packet *makeUpdate(ParentChildrenList *pcl, int pkt_type, int action);
00415
00416 int radius(int level);
00417
00418 PriQueue *ll_queue;
00419
00420 void recv(Packet *p, Handler *);
00421 virtual void ProcessHierUpdate(Packet *p);
00422 virtual void ForwardPacket(Packet *p);
00423
00424
00425 void get_nbrinfo();
00426
00427
00428 RecentMsgRecord *recent_demotion_msgs_;
00429 int num_demotion_msgs_;
00430 int CheckDemotionMsg(nsaddr_t id, int level, int origin_time);
00431
00432
00433 void trace(char* fmt,...);
00434 Trace *tracetarget_;
00435
00436
00437 void assign_lmaddress(int64_t *lmaddr, int num_lm_addrs, int root_level);
00438
00439
00440 tags_database *tag_dbase_;
00441 compr_taglist *aggregate_taginfo(compr_taglist *unagg_tags, int agg_level, int *num_tags);
00442 compr_taglist *aggregate_tags(compr_taglist *unagg_tags, int agg_level, int *num_tags);
00443 NodeIDList *search_tag(int obj_name, int prev_hop_level, int next_hop_level, nsaddr_t last_hop_id, int *num_dst);
00444 virtual nsaddr_t get_next_hop(nsaddr_t dst, int next_hop_level);
00445
00446
00447 MobileNode *node_;
00448
00449
00450 int be_random_;
00451
00452 int num_resched_;
00453 int wait_state_;
00454
00455 double total_wait_time_;
00456
00457
00458 int debug_;
00459 int qry_debug_;
00460
00461
00462 int cache_;
00463 TagCache *tag_cache_;
00464 int num_cached_items_;
00465
00466
00467 double update_period_;
00468 double update_timeout_;
00469
00470
00471
00472 int adverts_type_;
00473
00474
00475
00476 int global_lm_;
00477
00478
00479 nsaddr_t global_lm_id_;
00480 int global_lm_level_;
00481
00482
00483 int node_dead_;
00484
00485
00486 RNG *rn_;
00487 inline double jitter(double max, int be_random_);
00488 inline double random_timer(double max, int be_random_);
00489
00490 virtual void GenerateReHashMsg(int64_t lm_addr, double net_change_time) { }
00491
00492 int num_nbrs_;
00493 int *nbrs_;
00494
00495
00496 TagMobilityHandler *tag_mobility_;
00497 Event *tag_mobility_event_;
00498 double mobility_period_;
00499
00500 virtual void MoveTags();
00501 virtual void AddMobileTag(void *mobile_tag);
00502
00503
00504 compr_taglist *mobile_tags_;
00505
00506 TagAdvtHandler *tag_advt_handler_;
00507 Event *tag_advt_event_;
00508 RNG *tag_rng_;
00509
00510 void SendChangedTagListUpdate(int our_tag_changed, int level);
00511 int compare_tag_lists(compr_taglist *tag_list1, int num_tags1, compr_taglist *tag_list2, int num_tags2);
00512 };
00513
00514
00515
00516 class LMPeriodicAdvtHandler : public Handler {
00517 public:
00518 LMPeriodicAdvtHandler(ParentChildrenList *p) { p_ = p; }
00519 virtual void handle(Event *e) { (p_->a_)->periodic_callback(e,p_->level_); }
00520 private:
00521 ParentChildrenList *p_;
00522 };
00523
00524
00525 class PromotionTimer : public TimerHandler {
00526 public:
00527 PromotionTimer(LandmarkAgent *a) : TimerHandler() { a_ = a;}
00528 protected:
00529 virtual void expire(Event *e);
00530 LandmarkAgent *a_;
00531 };
00532
00533
00534 class TagMobilityHandler : public Handler {
00535 public:
00536 TagMobilityHandler(LandmarkAgent *a) { a_ = a; }
00537 virtual void handle(Event *) { a_->MoveTags(); }
00538 private:
00539 LandmarkAgent *a_;
00540 };
00541
00542
00543
00544
00545 class TagAdvtHandler : public Handler {
00546 public:
00547 TagAdvtHandler(LandmarkAgent *a) { a_ = a; our_tags_changed_ = 1; }
00548 virtual void handle(Event *) { a_->SendChangedTagListUpdate(our_tags_changed_,0); }
00549 private:
00550 LandmarkAgent *a_;
00551 int our_tags_changed_;
00552 };
00553
00554
00555 #endif