ProphetLists.cc

Go to the documentation of this file.
00001 /*
00002  *    Copyright 2006 Baylor University
00003  * 
00004  *    Licensed under the Apache License, Version 2.0 (the "License");
00005  *    you may not use this file except in compliance with the License.
00006  *    You may obtain a copy of the License at
00007  * 
00008  *        http://www.apache.org/licenses/LICENSE-2.0
00009  * 
00010  *    Unless required by applicable law or agreed to in writing, software
00011  *    distributed under the License is distributed on an "AS IS" BASIS,
00012  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  *    See the License for the specific language governing permissions and
00014  *    limitations under the License.
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     // grab an iterator to insertion point in rib_table
00072     rib_table::iterator lb = table_.lower_bound(eid);
00073 
00074     // if this is an update to an existing key
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     // otherwise shove it in, right here
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                                       // no arg means, use current time
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         // print out SID -> EndpointID
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     // By definition, sender of SYN is 0 and sender of SYNACK is 1
00215     if (sender.equals(EndpointID::NULL_EID()) == false)
00216     {
00217         ribd_[sender] = 0; // by definition
00218         rribd_[0] = sender;
00219     }
00220     if (receiver.equals(EndpointID::NULL_EID()) == false)
00221     {
00222         ribd_[receiver] = 1; // by definition
00223         rribd_[1] = receiver;
00224     }
00225     // neither sender nor receiver gets encoded into RIBDTLV
00226     // so no call to update_guess
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     // validate internal state
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     // first attempt to insert into forward lookup
00294     bool res = ribd_.insert(
00295                             std::pair<EndpointID,u_int16_t>(eid,sid)
00296                             ).second;
00297     if ( ! res )
00298         return false;
00299     // next attempt to insert into reverse lookup
00300     res = rribd_.insert(std::pair<u_int16_t,EndpointID>(sid,eid)).second;
00301     if ( ! res ) {
00302         ribd_.erase(eid);
00303     } else {
00304         // update on success
00305         // skip sender/receiver peer endpoints
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     // get rid of the old dictionary
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     // cts_ defaults to 0
00479     // non-end() should point to the first matching ACK
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;  // keep ACK for one day unless spec'd otherwise
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(); // erase() invalidates, we get to start again
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     // For each member of pstats, delete the new'd memory
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     // Section 3.7, equation 7
00612     pse->mopr_ += (1 - pse->mopr_) * p;
00613 
00614     // Section 3.7, equation 8
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 } // namespace dtn

Generated on Sat Sep 8 08:43:32 2007 for DTN Reference Implementation by  doxygen 1.5.3