00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #include "Dictionary.h"
00018 #include "Table.h"
00019
00020 namespace prophet
00021 {
00022
00023 #define MIN_LENGTH (strlen("dtn://"))
00024
00025 #define LOG_LT_MIN_LENGTH core_->print_log(name_.c_str(),BundleCore::LOG_ERR, \
00026 "destination id is shorter than required minimum @ %s:%d", \
00027 __FILE__, __LINE__)
00028
00029 Table::Table(BundleCore* core,
00030 const std::string& name,
00031 bool persistent)
00032 : core_(core), persistent_(persistent), name_(name), max_route_(0)
00033 {
00034 }
00035
00036 Table::Table(const Table& t)
00037 : core_(t.core_), persistent_(t.persistent_),
00038 name_(t.name_), max_route_(0)
00039 {
00040 iterator i = table_.begin();
00041 for (const_iterator c = t.table_.begin();
00042 c != t.table_.end();
00043 c++)
00044 {
00045 Node *n = new Node(*(c->second));
00046 i = table_.insert(i,rib_table::value_type(c->first,n));
00047
00048 heap_add(n);
00049 }
00050 }
00051
00052 Table::~Table()
00053 {
00054 free();
00055 table_.clear();
00056 }
00057
00058 void Table::heap_add(Node* n) {
00059 heap_.add(n);
00060 }
00061
00062 void
00063 Table::heap_del(Node* n) {
00064
00065 size_t pos = n->heap_pos_;
00066 const Node* old_n;
00067 if (pos < heap_.size())
00068 {
00069 old_n = heap_.sequence()[pos];
00070 if (old_n->dest_id_ == n->dest_id_)
00071 heap_.remove(pos);
00072 }
00073 }
00074
00075 const Node*
00076 Table::find(const std::string& dest_id) const
00077 {
00078 if (dest_id.length() > MIN_LENGTH)
00079 {
00080 const_iterator it = (const_iterator) table_.find(dest_id);
00081 if (it != table_.end())
00082 return (*it).second;
00083 }
00084 else
00085 LOG_LT_MIN_LENGTH;
00086 return NULL;
00087 }
00088
00089 double
00090 Table::p_value(const std::string& dest_id) const
00091 {
00092 const Node* n = find(dest_id);
00093 if (n == NULL)
00094 return 0.0;
00095
00096 return n->p_value();
00097 }
00098
00099 double
00100 Table::p_value(const Bundle* b) const
00101 {
00102 std::string dest = b->destination_id();
00103 std::string route = core_->get_route(dest);
00104 const Node* n = find(route);
00105 if (n == NULL)
00106 return 0.0;
00107
00108 return n->p_value();
00109 }
00110
00111 void
00112 Table::update(Node* n)
00113 {
00114 if (n == NULL ||
00115 strlen(n->dest_id()) < MIN_LENGTH)
00116 {
00117 LOG_LT_MIN_LENGTH;
00118 return;
00119 }
00120
00121
00122
00123 iterator i;
00124
00125 double p_old = 0.0;
00126
00127
00128 if (find(n->dest_id(),&i))
00129 {
00130 Node* old = i->second;
00131 p_old = i->second->p_value();
00132 i->second = n;
00133 if (n != old)
00134 {
00135 heap_del(old);
00136 delete old;
00137 }
00138 else
00139 heap_del(n);
00140 }
00141
00142 else
00143 table_.insert(i,rib_table::value_type(n->dest_id(),n));
00144
00145 heap_add(n);
00146 enforce_quota();
00147
00148
00149 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00150 "updating route %s (%.2f -> %.2f) direct\n",
00151 n->dest_id(), p_old, n->p_value());
00152
00153
00154 if (persistent_) core_->update_node(n);
00155 }
00156
00157 void
00158 Table::update_route(const std::string& dest_id,
00159 bool relay, bool custody, bool internet)
00160 {
00161 if (dest_id.length() < MIN_LENGTH)
00162 {
00163 LOG_LT_MIN_LENGTH;
00164 return;
00165 }
00166
00167 double p_old = 0.0;
00168
00169 iterator i;
00170 Node* n = NULL;
00171 if (find(dest_id,&i))
00172 {
00173 n = i->second;
00174 p_old = n->p_value();
00175 n->update_pvalue();
00176 n->set_relay(relay);
00177 n->set_custody(custody);
00178 n->set_internet_gw(internet);
00179 heap_del(n);
00180 }
00181 else
00182 {
00183 n = new Node(dest_id,relay,custody,internet);
00184 n->update_pvalue();
00185 table_.insert(i,rib_table::value_type(dest_id,n));
00186 }
00187 heap_add(n);
00188 enforce_quota();
00189
00190
00191 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00192 "updating route %s (%.2f -> %.2f) direct\n",
00193 n->dest_id(), p_old, n->p_value());
00194
00195
00196 if (persistent_) core_->update_node(n);
00197 }
00198
00199 void
00200 Table::update_transitive(const std::string& dest_id,
00201 const std::string& peer_id, double peer_pvalue,
00202 bool relay, bool custody, bool internet)
00203 {
00204 if (dest_id.length() < MIN_LENGTH ||
00205 peer_id.length() < MIN_LENGTH)
00206 {
00207 LOG_LT_MIN_LENGTH;
00208 return;
00209 }
00210
00211 double ab = p_value(peer_id);
00212 double p_old = 0.0;
00213 iterator i;
00214 Node* n = NULL;
00215 if (find(dest_id,&i))
00216 {
00217 n = i->second;
00218 p_old = n->p_value();
00219 n->update_transitive(ab,peer_pvalue);
00220 n->set_relay(relay);
00221 n->set_custody(custody);
00222 n->set_internet_gw(internet);
00223 heap_del(n);
00224 }
00225 else
00226 {
00227 n = new Node(dest_id,relay,custody,internet);
00228 n->update_transitive(ab,peer_pvalue);
00229 table_.insert(i,rib_table::value_type(dest_id,n));
00230 }
00231 heap_add(n);
00232 enforce_quota();
00233
00234
00235 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00236 "updating route %s (%.2f -> %.2f) transitive\n",
00237 n->dest_id(), p_old, n->p_value());
00238
00239
00240 if (persistent_) core_->update_node(n);
00241 }
00242
00243 void
00244 Table::update_transitive(const std::string& peer_id,
00245 const RIBNodeList& rib,
00246 const Dictionary& ribd)
00247 {
00248 if (peer_id.length() < MIN_LENGTH)
00249 {
00250 LOG_LT_MIN_LENGTH;
00251 return;
00252 }
00253
00254 double ab = p_value(peer_id);
00255 for (RIBNodeList::const_iterator i = rib.begin(); i != rib.end(); i++)
00256 {
00257 double p_old = 0.0;
00258
00259 if ((*i)->sid_ == Dictionary::INVALID_SID)
00260 continue;
00261
00262 std::string eid = ribd.find((*i)->sid_);
00263
00264 if (eid == "")
00265 continue;
00266
00267 iterator t;
00268 Node* n = NULL;
00269 if (find(eid,&t))
00270 {
00271 n = t->second;
00272 p_old = n->p_value();
00273 n->update_transitive(ab,(*i)->p_value());
00274 n->set_relay((*i)->relay());
00275 n->set_custody((*i)->custody());
00276 n->set_internet_gw((*i)->internet_gw());
00277 heap_del(n);
00278 }
00279 else
00280 {
00281 n = new Node(eid,
00282 (*i)->relay(),
00283 (*i)->custody(),
00284 (*i)->internet_gw());
00285 n->update_transitive(ab,(*i)->p_value());
00286 table_.insert(t,rib_table::value_type(eid,n));
00287 }
00288 heap_add(n);
00289 enforce_quota();
00290
00291
00292 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00293 "updating route %s (%.2f -> %.2f) transitive\n",
00294 eid.c_str(), p_old, n->p_value());
00295
00296
00297 if (persistent_) core_->update_node(n);
00298 }
00299 }
00300
00301 size_t
00302 Table::clone(NodeList& list) const
00303 {
00304
00305 list.clear();
00306
00307 size_t num = 0;
00308 for (const_iterator i = table_.begin(); i != table_.end(); i++)
00309 {
00310
00311
00312 list.push_back(new Node(*((*i).second)));
00313
00314 num++;
00315 }
00316 return num;
00317 }
00318
00319 size_t
00320 Table::truncate(double epsilon)
00321 {
00322 size_t num = 0;
00323
00324
00325 if (epsilon >= 1.0)
00326 {
00327
00328
00329 num = table_.size();
00330 free();
00331 table_.clear();
00332
00333
00334 size_t pos = heap_.size();
00335 while (pos-- > 0)
00336 heap_.remove(pos);
00337
00338 return num;
00339 }
00340
00341 Node* n;
00342 iterator i;
00343 if (heap_.empty()) {
00344 for (i = table_.begin(); i != table_.end(); i++) {
00345 n = (*i).second;
00346 if (n->p_value() < epsilon) {
00347 iterator j = i++;
00348
00349 remove(&j);
00350
00351 num++;
00352 } else
00353 i++;
00354 }
00355 } else {
00356 n = heap_.top();
00357 while (n->p_value() < epsilon)
00358 {
00359 if (find(n->dest_id(),&i))
00360 {
00361
00362 remove(&i);
00363
00364 n = heap_.top();
00365
00366 num++;
00367 }
00368 else
00369 break;
00370 }
00371 }
00372
00373
00374 if (num > 0)
00375 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00376 "removed %zu routes with p_value < (epsilon %.4f)\n",
00377 num, epsilon);
00378
00379 return num;
00380 }
00381
00382 void
00383 Table::assign(const RIBNodeList& list,
00384 const Dictionary& ribd)
00385 {
00386 for (RIBNodeList::const_iterator i = list.begin(); i != list.end(); i++)
00387 {
00388 std::string eid = ribd.find((*i)->sid_);
00389 Node* n = new Node(*(*i));
00390 n->set_dest_id(eid);
00391 update(n);
00392 }
00393
00394
00395 if (list.size() > 0)
00396 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00397 "assigned %zu routes from RIB\n",
00398 list.size());
00399 }
00400
00401 void Table::assign(const std::list<const Node*>& list,
00402 const NodeParams* params)
00403 {
00404
00405 bool old = persistent_;
00406 persistent_ = false;
00407 for (std::list<const Node*>::const_iterator i = list.begin();
00408 i != list.end(); i++)
00409 {
00410 Node* n = new Node(*(*i));
00411 n->set_params(params);
00412 update(n);
00413 }
00414 persistent_ = old;
00415
00416
00417 if (list.size() > 0)
00418 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00419 "assigned %zu routes from permanent storage\n",
00420 list.size());
00421 }
00422
00423 size_t
00424 Table::age_nodes()
00425 {
00426 size_t num = 0;
00427 for (iterator i = table_.begin(); i != table_.end(); i++)
00428 {
00429 Node *n = (*i).second;
00430 n->update_age();
00431 heap_del(n);
00432 heap_add(n);
00433 num++;
00434
00435
00436 if (persistent_) core_->update_node(n);
00437 }
00438
00439
00440 if (num > 0)
00441 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00442 "applied age algorithm to %zu nodes\n", num);
00443
00444 return num;
00445 }
00446
00447 void
00448 Table::remove(iterator* i)
00449 {
00450
00451 if (persistent_) core_->delete_node((*i)->second);
00452
00453 Node* n = (**i).second;
00454 table_.erase(*i);
00455 heap_del(n);
00456 delete n;
00457 }
00458
00459 void
00460 Table::enforce_quota()
00461 {
00462 if (max_route_ == 0)
00463
00464 return;
00465
00466 iterator i;
00467 core_->print_log(name_.c_str(),BundleCore::LOG_INFO,
00468 "enforce_quota table_size=[%zu] max_route=[%u]",
00469 table_.size(), max_route_);
00470 while(table_.size() > max_route_)
00471 {
00472 if (heap_.empty())
00473 break;
00474
00475
00476 Node* n = heap_.top();
00477 if (find(n->dest_id(),&i))
00478 remove(&i);
00479 else
00480
00481 heap_del(n);
00482 }
00483 }
00484
00485 void
00486 Table::free()
00487 {
00488 for (iterator i = table_.begin(); i != table_.end(); i++)
00489 {
00490 heap_del((*i).second);
00491 delete ((*i).second);
00492 }
00493 }
00494
00495 bool
00496 Table::find(const std::string& dest_id, iterator* i)
00497 {
00498 if (dest_id.length() < MIN_LENGTH)
00499 {
00500 LOG_LT_MIN_LENGTH;
00501 return false;
00502 }
00503 if (i == NULL) return false;
00504
00505 *i = table_.lower_bound(dest_id);
00506 return (*i != table_.end() && !(table_.key_comp()(dest_id,(*i)->first)));
00507 }
00508
00509 };