00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #include <oasys/util/Time.h>
00018 #include "ProphetTLV.h"
00019
00020 #include "ProphetLists.h"
00021
00022 namespace dtn {
00023
00024 ProphetTable::ProphetTable()
00025 : lock_(new oasys::SpinLock())
00026 {
00027 table_.clear();
00028 }
00029
00030 ProphetTable::~ProphetTable()
00031 {
00032 oasys::ScopeLock l(lock_,"destructor");
00033 clear();
00034 l.unlock();
00035 delete lock_;
00036 }
00037
00038 ProphetNode*
00039 ProphetTable::find(const EndpointID& eid) const
00040 {
00041 ASSERT( eid.equals(EndpointID::NULL_EID()) == false );
00042 EndpointID routeid = Prophet::eid_to_routeid(eid);
00043
00044 oasys::ScopeLock l(lock_,"ProphetTable::find");
00045 rib_table::const_iterator it =
00046 (rib_table::const_iterator) table_.find(routeid);
00047 if(it != table_.end()) {
00048 return (ProphetNode*) (*it).second;
00049 }
00050 return NULL;
00051 }
00052
00053 double
00054 ProphetTable::p_value(const EndpointID& eid) const
00055 {
00056 ProphetNode *n = find(eid);
00057 if( n == NULL )
00058 return 0.0;
00059
00060 return n->p_value();
00061 }
00062
00063 void
00064 ProphetTable::update(ProphetNode* node)
00065 {
00066 EndpointID eid(node->remote_eid());
00067 ASSERT( eid.equals(EndpointID::NULL_EID()) == false );
00068
00069 oasys::ScopeLock l(lock_,"ProphetTable::update");
00070
00071
00072 rib_table::iterator lb = table_.lower_bound(eid);
00073
00074
00075 if ( lb != table_.end() &&
00076 !(table_.key_comp()(eid,lb->first)) &&
00077 !(table_.key_comp()(lb->first,eid)) )
00078 {
00079 ProphetNode* old = lb->second;
00080 lb->second = node;
00081 if (node != old) delete old;
00082 }
00083
00084 else {
00085 table_.insert(lb,rib_table::value_type(eid,node));
00086 }
00087 }
00088
00089 size_t
00090 ProphetTable::dump_table(ProphetNodeList& list) const
00091 {
00092 oasys::ScopeLock l(lock_,"ProphetTable::dump_table");
00093 size_t num = 0;
00094 for(rib_table::const_iterator rti = table_.begin();
00095 rti != table_.end();
00096 rti++) {
00097 ProphetNode* node = new ProphetNode(*((*rti).second));
00098 list.push_back(node);
00099 num++;
00100 }
00101 return num;
00102 }
00103
00104 ProphetTable::iterator
00105 ProphetTable::begin()
00106 {
00107 ASSERT( lock_->is_locked_by_me() );
00108 return table_.begin();
00109 }
00110
00111 ProphetTable::iterator
00112 ProphetTable::end()
00113 {
00114 ASSERT( lock_->is_locked_by_me() );
00115 return table_.end();
00116 }
00117
00118 void
00119 ProphetTable::truncate(double epsilon)
00120 {
00121 oasys::ScopeLock l(lock_,"ProphetTable::truncate");
00122 for(iterator i = table_.begin();
00123 i != table_.end();
00124 i++)
00125 {
00126 ProphetNode* node = (*i).second;
00127 if (node->p_value() < epsilon)
00128 {
00129 table_.erase(i);
00130 delete node;
00131 }
00132 }
00133 }
00134
00135 void
00136 ProphetTable::free()
00137 {
00138 oasys::ScopeLock l(lock_,"ProphetTable::free");
00139 for(iterator i = table_.begin();
00140 i != table_.end();
00141 i++)
00142 {
00143 delete((*i).second);
00144 }
00145 }
00146
00147 void
00148 ProphetTableAgeTimer::reschedule()
00149 {
00150 struct timeval when;
00151 ::gettimeofday(&when,0);
00152 when.tv_sec += period_;
00153 schedule_at(&when);
00154 }
00155
00156 void
00157 ProphetTableAgeTimer::timeout(const struct timeval& now)
00158 {
00159 (void)now;
00160 int c = 0;
00161 oasys::ScopeLock l(table_->lock(),"ProphetTableAgeTimer");
00162 ProphetTable::iterator i = table_->begin();
00163 while(i != table_->end()) {
00164 (*i).second->update_age();
00165 i++; c++;
00166 }
00167 table_->truncate(epsilon_);
00168 reschedule();
00169 log_debug("aged %d prophet nodes",c);
00170 }
00171
00172 void
00173 ProphetAckAgeTimer::reschedule()
00174 {
00175 struct timeval when;
00176 ::gettimeofday(&when,0);
00177 when.tv_sec += period_;
00178 schedule_at(&when);
00179 }
00180
00181 void
00182 ProphetAckAgeTimer::timeout(const struct timeval& now)
00183 {
00184 (void)now;
00185
00186 log_debug("aged %zu prophet ACKs",list_->expire());
00187 reschedule();
00188 }
00189
00190 void
00191 ProphetDictionary::dump(oasys::StringBuffer* buf)
00192 {
00193 for(const_iterator i = rribd_.begin(); i != rribd_.end(); i++)
00194 {
00195
00196 buf->appendf("%d %s\n",(*i).first,(*i).second.c_str());
00197 }
00198 }
00199
00200 void
00201 BundleOfferList::dump(oasys::StringBuffer* buf)
00202 {
00203 for(const_iterator i = list_.begin(); i != list_.end(); i++)
00204 {
00205 (*i)->dump(buf);
00206 }
00207 }
00208
00209 ProphetDictionary::ProphetDictionary(const EndpointID& sender,
00210 const EndpointID& receiver)
00211 : guess_(0)
00212 {
00213 clear();
00214
00215 if (sender.equals(EndpointID::NULL_EID()) == false)
00216 {
00217 ribd_[sender] = 0;
00218 rribd_[0] = sender;
00219 }
00220 if (receiver.equals(EndpointID::NULL_EID()) == false)
00221 {
00222 ribd_[receiver] = 1;
00223 rribd_[1] = receiver;
00224 }
00225
00226
00227 }
00228
00229 ProphetDictionary::ProphetDictionary(const ProphetDictionary& pd)
00230 : ribd_(pd.ribd_), rribd_(pd.rribd_), guess_(pd.guess_)
00231 {
00232 }
00233
00234 bool
00235 ProphetDictionary::is_assigned(const EndpointID& eid) const
00236 {
00237 ASSERT(eid.equals(EndpointID::NULL_EID()) == false);
00238 ribd::const_iterator it =
00239 (ribd::const_iterator) ribd_.find(eid);
00240 if (it != ribd_.end()) {
00241 return true;
00242 }
00243 return false;
00244 }
00245
00246 u_int16_t
00247 ProphetDictionary::find(const EndpointID& eid) const
00248 {
00249 ASSERT(eid.equals(EndpointID::NULL_EID()) == false);
00250 ribd::const_iterator it =
00251 (ribd::const_iterator) ribd_.find(eid);
00252 if (it != ribd_.end()) {
00253 return (*it).second;
00254 }
00255 return 0;
00256 }
00257
00258 EndpointID
00259 ProphetDictionary::find(u_int16_t id) const
00260 {
00261 rribd::const_iterator it = (rribd::const_iterator) rribd_.find(id);
00262 if (it != rribd_.end()) {
00263 return (*it).second;
00264 }
00265 return EndpointID::NULL_EID();
00266 }
00267
00268 u_int16_t
00269 ProphetDictionary::insert(const EndpointID& eid)
00270 {
00271 ASSERT(eid.equals(EndpointID::NULL_EID()) == false);
00272 u_int16_t sid = ribd_.size();
00273 bool res = assign(eid,sid);
00274 return res ? sid : 0;
00275 }
00276
00277 bool
00278 ProphetDictionary::assign(const EndpointID& eid, u_int16_t sid)
00279 {
00280 ASSERT(eid.equals(EndpointID::NULL_EID()) == false);
00281
00282 ASSERT(ribd_.size() == rribd_.size());
00283 if (ribd_.size() >= 2)
00284 {
00285 EndpointID sender = rribd_[0];
00286 EndpointID receiver = rribd_[1];
00287 if (eid.equals(sender) && sid != 0)
00288 return false;
00289 if (eid.equals(receiver) && sid != 1)
00290 return false;
00291 }
00292
00293
00294 bool res = ribd_.insert(
00295 std::pair<EndpointID,u_int16_t>(eid,sid)
00296 ).second;
00297 if ( ! res )
00298 return false;
00299
00300 res = rribd_.insert(std::pair<u_int16_t,EndpointID>(sid,eid)).second;
00301 if ( ! res ) {
00302 ribd_.erase(eid);
00303 } else {
00304
00305
00306 if ( ! (sid == 0 || sid == 1))
00307 {
00308 update_guess(eid.str().size());
00309 }
00310 }
00311 ASSERT(ribd_.size() == rribd_.size());
00312 return res;
00313 }
00314
00315 void
00316 ProphetDictionary::clear() {
00317
00318 ribd_.clear();
00319 rribd_.clear();
00320 guess_ = 0;
00321 }
00322
00323 void
00324 BundleOfferList::sort(ProphetDictionary* ribd,
00325 ProphetTable* nodes,
00326 u_int16_t sid)
00327 {
00328 oasys::ScopeLock l(lock_,"BundleOfferList::sort");
00329 std::sort(list_.begin(),list_.end(),BundleOfferSIDComp(ribd,nodes,sid));
00330 }
00331
00332 bool
00333 BundleOfferList::remove_bundle(u_int32_t cts, u_int16_t sid)
00334 {
00335 oasys::ScopeLock l(lock_,"BundleOfferList::remove_bundle");
00336 for (iterator i = list_.begin();
00337 i != list_.end();
00338 i++)
00339 {
00340 if ((*i)->creation_ts() == cts && (*i)->sid() == sid) {
00341 list_.erase(i);
00342 return true;
00343 }
00344 }
00345 return false;
00346 }
00347
00348 size_t
00349 BundleOfferList::size() const
00350 {
00351 return list_.size();
00352 }
00353
00354 bool
00355 BundleOfferList::empty() const
00356 {
00357 return list_.empty();
00358 }
00359
00360 void
00361 BundleOfferList::clear()
00362 {
00363 oasys::ScopeLock l(lock_,"BundleOfferList::clear");
00364 list_.clear();
00365 }
00366
00367 void
00368 BundleOfferList::push_back(BundleOffer* bo)
00369 {
00370 oasys::ScopeLock l(lock_,"BundleOfferList::push_back");
00371 list_.push_back(bo);
00372 }
00373
00374 void
00375 BundleOfferList::add_offer(BundleOffer* offer)
00376 {
00377 oasys::ScopeLock l(lock_,"BundleOfferList::add_offer");
00378 ASSERT(type_ != BundleOffer::UNDEFINED);
00379 ASSERT(offer->type() == type_);
00380 list_.push_back(new BundleOffer(*offer));
00381 }
00382
00383 void
00384 BundleOfferList::add_offer(u_int32_t cts, u_int16_t sid,
00385 bool custody, bool accept, bool ack)
00386 {
00387 oasys::ScopeLock l(lock_,"BundleOfferList::add_offer");
00388 ASSERT(type_ != BundleOffer::UNDEFINED);
00389 list_.push_back(new BundleOffer(cts, sid, custody, accept, ack, type_));
00390 }
00391
00392 void
00393 BundleOfferList::add_offer(Bundle* bundle,u_int16_t sid)
00394 {
00395 oasys::ScopeLock l(lock_,"BundleOfferList::add_offer");
00396 BundleRef b("BundleOfferList::add_offer");
00397 b = bundle;
00398 if (b.object() == NULL) return;
00399 ASSERT(type_ != BundleOffer::UNDEFINED);
00400 list_.push_back(new BundleOffer(b->creation_ts_.seconds_, sid,
00401 b->custody_requested_, false, false, type_));
00402 }
00403
00404 BundleOffer*
00405 BundleOfferList::find(u_int32_t cts, u_int16_t sid) const
00406 {
00407 oasys::ScopeLock l(lock_,"BundleOfferList::find");
00408 BundleOffer* retval = NULL;
00409 for (const_iterator i = list_.begin();
00410 i != list_.end();
00411 i++)
00412 {
00413 if ((*i)->creation_ts() == cts && (*i)->sid() == sid) {
00414 retval = *i;
00415 break;
00416 }
00417 }
00418 return retval;
00419 }
00420
00421 BundleOfferList::const_iterator
00422 BundleOfferList::begin() const
00423 {
00424 ASSERT(lock_->is_locked_by_me());
00425 return (const_iterator) list_.begin();
00426 }
00427
00428 BundleOfferList::const_iterator
00429 BundleOfferList::end() const
00430 {
00431 ASSERT(lock_->is_locked_by_me());
00432 return (const_iterator) list_.end();
00433 }
00434
00435 BundleOfferList::iterator
00436 BundleOfferList::begin()
00437 {
00438 ASSERT(lock_->is_locked_by_me());
00439 return list_.begin();
00440 }
00441
00442 BundleOfferList::iterator
00443 BundleOfferList::end()
00444 {
00445 ASSERT(lock_->is_locked_by_me());
00446 return list_.end();
00447 }
00448
00449 ProphetAckList::ProphetAckList()
00450 : lock_(new oasys::SpinLock())
00451 {
00452 acks_.clear();
00453 }
00454
00455 ProphetAckList::~ProphetAckList()
00456 {
00457 {
00458 oasys::ScopeLock l(lock_,"ProphetAckList::destructor");
00459 palist::iterator iter;
00460 while(!acks_.empty()) {
00461 ProphetAck* a;
00462 iter = acks_.begin();
00463 a = *iter;
00464 acks_.erase(a);
00465 delete a;
00466 }
00467 }
00468 acks_.clear();
00469 delete lock_;
00470 }
00471
00472 size_t
00473 ProphetAckList::count(const EndpointID& eid) const
00474 {
00475 oasys::ScopeLock l(lock_,"ProphetAckList::count");
00476 size_t retval = 0;
00477 ProphetAck p(eid);
00478
00479
00480 palist::iterator iter = acks_.lower_bound(&p);
00481 while( iter != acks_.end() ) {
00482 if ( !(*iter)->dest_id_.equals(eid) )
00483 break;
00484 retval++;
00485 iter++;
00486 }
00487 return retval;
00488 }
00489
00490 bool
00491 ProphetAckList::insert(const EndpointID& eid, u_int32_t cts, u_int32_t ets)
00492 {
00493 oasys::ScopeLock l(lock_,"ProphetAckList::insert");
00494 if (ets == 0)
00495 ets = cts + 86400;
00496 ProphetAck* p = new ProphetAck(eid,cts,ets);
00497 if (acks_.insert(p).second)
00498 return true;
00499 delete p;
00500 return false;
00501 }
00502
00503 bool
00504 ProphetAckList::insert(ProphetAck* p)
00505 {
00506 oasys::ScopeLock l(lock_,"ProphetAckList::insert");
00507 return acks_.insert(p).second;
00508 }
00509
00510 size_t
00511 ProphetAckList::expire(u_int32_t older_than)
00512 {
00513 oasys::ScopeLock l(lock_,"ProphetAckList::expire");
00514 oasys::Time now(older_than);
00515 size_t how_many = 0;
00516 if(older_than == 0)
00517 now.get_time();
00518 palist::iterator iter = acks_.begin();
00519 while(iter != acks_.end()) {
00520 ProphetAck* p = *iter;
00521 if (p->ets_ < (unsigned int) now.sec_) {
00522 how_many++;
00523 acks_.erase(iter);
00524 delete p;
00525 iter = acks_.begin();
00526 } else
00527 iter++;
00528 }
00529 return how_many;
00530 }
00531
00532 size_t
00533 ProphetAckList::fetch(const EndpointIDPattern& eid,
00534 PointerList<ProphetAck>& list) const
00535 {
00536 oasys::ScopeLock l(lock_,"ProphetAckList::fetch");
00537 size_t retval = 0;
00538 palist::iterator iter = acks_.begin();
00539 while( iter != acks_.end() ) {
00540 if (eid.match((*iter)->dest_id_)) {
00541 list.push_back(new ProphetAck((*(*iter))));
00542 retval++;
00543 }
00544 iter++;
00545 }
00546 return retval;
00547 }
00548
00549 bool
00550 ProphetAckList::is_ackd(const EndpointID& eid, u_int32_t cts) const
00551 {
00552 oasys::ScopeLock l(lock_,"ProphetAckList::fetch");
00553 ProphetAck p(eid);
00554 palist::iterator iter = acks_.lower_bound(&p);
00555 while (iter != acks_.end())
00556 {
00557 if (!(*iter)->dest_id_.equals(eid))
00558 break;
00559 if ((*iter)->cts_ == cts)
00560 return true;
00561 }
00562 return false;
00563 }
00564
00565 ProphetStats::~ProphetStats()
00566 {
00567
00568 {
00569 oasys::ScopeLock l(lock_,"ProphetStats::destructor");
00570 iterator i = pstats_.begin();
00571 while( i != pstats_.end() ) {
00572 ProphetStatsEntry* pse = (*i).second;
00573 delete pse;
00574 i++;
00575 }
00576 }
00577
00578 pstats_.clear();
00579 delete lock_;
00580 }
00581
00582 ProphetStatsEntry*
00583 ProphetStats::find_entry(const Bundle* b)
00584 {
00585 ASSERT(lock_->is_locked_by_me());
00586 u_int32_t id = b->bundleid_;
00587 ProphetStatsEntry* pse = NULL;
00588 const_iterator it = (const_iterator) pstats_.find(id);
00589 if (it != pstats_.end())
00590 pse = (*it).second;
00591 else {
00592 pse = new ProphetStatsEntry();
00593 memset(pse,0,sizeof(ProphetStatsEntry));
00594 pstats_[id] = pse;
00595 }
00596 return pse;
00597 }
00598
00599 void
00600 ProphetStats::update_stats(const Bundle* b, double p)
00601 {
00602 oasys::ScopeLock l(lock_,"ProphetStats::update_stats");
00603 ProphetStatsEntry* pse = find_entry(b);
00604
00605 ASSERT(pse != NULL);
00606
00607 if (pse->p_max_ < p) {
00608 pse->p_max_ = p;
00609 }
00610
00611
00612 pse->mopr_ += (1 - pse->mopr_) * p;
00613
00614
00615 pse->lmopr_ += p;
00616
00617 pstats_[b->bundleid_] = pse;
00618 }
00619
00620 double
00621 ProphetStats::get_p_max(const Bundle* b)
00622 {
00623 oasys::ScopeLock l(lock_,"ProphetStats::get_p_max");
00624 ProphetStatsEntry* pse = find_entry(b);
00625 return pse->p_max_;
00626 }
00627
00628 double
00629 ProphetStats::get_mopr(const Bundle* b)
00630 {
00631 oasys::ScopeLock l(lock_,"ProphetStats::get_mopr");
00632 ProphetStatsEntry* pse = find_entry(b);
00633 return pse->mopr_;
00634 }
00635
00636 double
00637 ProphetStats::get_lmopr(const Bundle* b)
00638 {
00639 oasys::ScopeLock l(lock_,"ProphetStats::get_lmopr");
00640 ProphetStatsEntry* pse = find_entry(b);
00641 return pse->lmopr_;
00642 }
00643
00644 void
00645 ProphetStats::drop_bundle(const Bundle* b)
00646 {
00647 oasys::ScopeLock l(lock_,"ProphetStats::drop_bundle");
00648 ProphetStatsEntry* pse = NULL;
00649 iterator it = pstats_.find(b->bundleid_);
00650 if (it != pstats_.end())
00651 {
00652 pse = (*it).second;
00653 pstats_.erase(it);
00654 delete pse;
00655 dropped_++;
00656 }
00657 }
00658
00659 Bundle*
00660 ProphetBundleList::find(const BundleList& list,
00661 const EndpointID& dest,
00662 u_int32_t cts)
00663 {
00664 oasys::ScopeLock l(list.lock(), "ProphetBundleList::find");
00665 EndpointIDPattern route = Prophet::eid_to_route(dest);
00666 for(BundleList::const_iterator i =
00667 (BundleList::const_iterator) list.begin();
00668 i != list.end();
00669 i++)
00670 {
00671 if ((*i)->creation_ts_.seconds_ == cts &&
00672 route.match((*i)->dest_))
00673 {
00674 return *i;
00675 }
00676 }
00677 return NULL;
00678 }
00679
00680 }