开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
linkcache.cc
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：24k
源码类别：

通讯编程

开发平台：

Visual C++

linkcache.cc：源码内容
  2. /*
  3.  * linkcache.cc
  4.  * Copyright (C) 2000 by the University of Southern California
  5.  * $Id: linkcache.cc,v 1.2 2005/08/25 18:58:05 johnh Exp $
  6.  *
  7.  * This program is free software; you can redistribute it and/or
  8.  * modify it under the terms of the GNU General Public License,
  9.  * version 2, as published by the Free Software Foundation.
  10.  *
  11.  * This program is distributed in the hope that it will be useful,
  12.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.  * GNU General Public License for more details.
  15.  *
  16.  * You should have received a copy of the GNU General Public License along
  17.  * with this program; if not, write to the Free Software Foundation, Inc.,
  18.  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
  19.  *
  20.  *
  21.  * The copyright of this module includes the following
  22.  * linking-with-specific-other-licenses addition:
  23.  *
  24.  * In addition, as a special exception, the copyright holders of
  25.  * this module give you permission to combine (via static or
  26.  * dynamic linking) this module with free software programs or
  27.  * libraries that are released under the GNU LGPL and with code
  28.  * included in the standard release of ns-2 under the Apache 2.0
  29.  * license or under otherwise-compatible licenses with advertising
  30.  * requirements (or modified versions of such code, with unchanged
  31.  * license).  You may copy and distribute such a system following the
  32.  * terms of the GNU GPL for this module and the licenses of the
  33.  * other code concerned, provided that you include the source code of
  34.  * that other code when and as the GNU GPL requires distribution of
  35.  * source code.
  36.  *
  37.  * Note that people who make modified versions of this module
  38.  * are not obligated to grant this special exception for their
  39.  * modified versions; it is their choice whether to do so.  The GNU
  40.  * General Public License gives permission to release a modified
  41.  * version without this exception; this exception also makes it
  42.  * possible to release a modified version which carries forward this
  43.  * exception.
  44.  *
  45.  */
  46. //
  47. // Other copyrights might apply to parts of this software and are so
  48. // noted when applicable.
  49. //
  50. // Ported from CMU/Monarch's code, appropriate copyright applies.  
  51. #ifdef DSR_LINKCACHE
  53. #include <god.h>
  54. #include "path.h"
  55. #include "routecache.h"
  56. #include <list.h>
  57. #ifdef DSR_CACHE_STATS
  58. #include "cache_stats.h"
  59. #endif
  61. #define CURRENT_TIME Scheduler::instance().clock()
  62. #define MAX_SIMTIME  86400
  64. bool cache_ignore_hints = false;     // ignore all hints?
  65. bool cache_use_overheard_routes = true; 
  67. // Specifies whether or not to retain links after they go bad
  68. // I don't think this is implemented.
  69. static const bool lc_cache_negative_links = false;
  70. static const double lc_neg_cache_life = 1.0;
  72. // When inserting/deleting link A->B, also insert/delete B->A.
  73. static const bool lc_bidirectional_links = true;
  75. // Evict "unreachable" links from the cache.
  76. static const bool lc_evict_unreachable_links = false;
  78. // do we expire in realtime? or do we wait for use?
  79. //#define REALTIME_EXPIRE
  81. // The maximum number of nodes supported by the cache.
  82. #define LC_MAX_NODES 200
  84. // General generational stuff...
  85. static const double lc_gen_use_bonus = 300;
  87. // Static stuff
  88. static const double lc_static_discover_life = 5.0;
  89. static const double lc_static_overhear_life = 5.0;
  91. // Table stuff
  92. static const double lc_table_init_val = 50.0;
  93. static const double lc_table_mult_by  = 0.5;
  94. static const double lc_linear_alpha   = 1.0/8.0;
  95. static const double lc_exp_add_amt    = 2.0;
  96. static const double lc_exp_div_amt    = 2.0;
  97. static const double lc_minlifetime    = 2.0;
  99. // types of linkgens
  100. #define EXPPOLICY_INFINITE  0
  101. #define EXPPOLICY_STATIC    1
  102. #define EXPPOLICY_LINEAR    2
  103. #define EXPPOLICY_EXP       3
  104. #ifdef GOD_STABILITY
  105. #define EXPPOLICY_GOD_OMNI  4
  106. #define EXPPOLICY_GOD_TABLE 5
  107. #endif
  108. #define LONGEST_LIVED_ROUTE
  110. static const int lc_exppolicy = EXPPOLICY_EXP;
  112. #ifdef GOD_STABILITY
  113. extern double *godavglife;
  114. #endif
  116. #ifndef REALTIME_EXPIRE
  117. // statistics...
  118. #define IS_GOOD     0
  119. #define IS_BAD      1
  120. #define CALLED_GOOD 0
  121. #define CALLED_BAD  2
  122. static int expirestats[4];
  123. #endif
  125. static int verbose_debug = 0;
  127. // *****************************************************
  129. class Link {
  130. public:
  131. Link(nsaddr_t dst) {
  132. ln_dst = dst;
  133. ln_flags = ln_cost = 0;
  134. ln_timeout = 0.0;
  135. ln_insert = 0.0;
  136. ln_t = 0.0;
  137. ln_linktype = LT_NONE;
  138. ln_logstat = LS_UNLOGGED;
  139. }
  141. inline bool expired() {
  142. return (ln_timeout <= CURRENT_TIME);
  143. }
  145. LIST_ENTRY(Link) ln_link;
  146. nsaddr_t   ln_dst;
  147. int        ln_flags;       // link status information
  148. #define LINK_FLAG_UP 0x01
  150. /*
  151.  * Right now all links have the same cost (1). - josh
  152.  */
  153. int        ln_cost;        // cost of using the link
  155. /*
  156.  * the use of ln_timeout to expire links from the
  157.  * cache has not yet been implemented. - josh
  158.  * Implemented. - yihchun
  159.  */
  160. double     ln_timeout;     // when the link expires
  161. double     ln_insert;      // when the link expires
  163. #define LINK_TIMEOUT MAX_SIMTIME
  165. // mirror the values kept in class ID
  166. Time    ln_t;
  167. Link_Type  ln_linktype;
  168. Log_Status ln_logstat;
  169. };
  171. LIST_HEAD(dsrLinkHead, Link);
  173. class LinkCache : public RouteCache {
  174. friend class MobiHandler;
  176. public:
  177. LinkCache();
  179. void noticeDeadLink(const ID&from, const ID& to, Time t);
  180. // the link from->to isn't working anymore, purge routes containing
  181. // it from the cache
  183. void noticeRouteUsed(const Path& route, Time t,
  184.      const ID& who_from);
  185. // tell the cache about a route we saw being used
  187. void addRoute(const Path& route, Time t, const ID& who_from);
  188. // add this route to the cache (presumably we did a route request
  189. // to find this route and don't want to lose it)
  191. bool findRoute(ID dest, Path& route, int for_me = 0);
  192. // if there is a cached path from us to dest returns true and fills in
  193. // the route accordingly. returns false otherwise
  194. // if for_use, then we assume that the node really wants to keep 
  195. // the returned route so it will be promoted to primary storage
  196. // if not there already
  197. int command(int argc, const char*const* argv);
  199. protected:
  200. dsrLinkHead lcache[LC_MAX_NODES + 1];
  201. // note the zeroth index is not used
  203. int addLink(const ID& from, const ID& to,
  204.     int flags, double timeout = LINK_TIMEOUT, int cost = 1);
  205. int delLink(const ID& from, const ID& to);
  206. Link* findLink(int from, int to);
  207. void purgeLink(void);
  208. void dumpLink(void);
  210. void Link_to_ID(Link* l, ID& id);
  212. #ifdef DSR_CACHE_STATS
  213. void checkLink_logall(const ID& from, const ID& to, int action);
  214. void checkLink(const ID& from, const ID& to, int action);
  215. void periodic_checkCache();
  217. struct cache_stats stat;
  218. #endif
  219. private:
  220. ////////////////////////////////////////////////////////////
  221. // Dijkstra's Algorithm
  223. double dirty; // the next time it gets dirty
  224. #ifdef LONGEST_LIVED_ROUTE
  225. double dl[LC_MAX_NODES + 1];
  226. #endif
  227. u_int32_t d[LC_MAX_NODES + 1];
  228. u_int32_t pi[LC_MAX_NODES + 1];
  229. bool S[LC_MAX_NODES + 1];
  230. double exptable[LC_MAX_NODES + 1];
  231. #define INFINITY 0x7fffffff
  233. void init_single_source(int s);
  234. #ifdef LONGEST_LIVED_ROUTE
  235. void relax(u_int32_t u, u_int32_t v, u_int32_t w, double);
  236. #else
  237. void relax(u_int32_t u, u_int32_t v, u_int32_t w);
  238. #endif
  239. int  extract_min_q(void);
  240. void dijkstra(void);
  241. void dump_dijkstra(int dst);
  242. double find_timeout(ID a, ID b, bool discovered);
  243. };
  245. ///////////////////////////////////////////////////////////////////////////
  247. double LinkCache::find_timeout(ID a, ID b, bool discovered) {
  248. double lifetime = 0.0;
  249. switch (lc_exppolicy) {
  250. case EXPPOLICY_INFINITE:
  251. #ifdef GOD_STABILITY
  252.         case EXPPOLICY_GOD_OMNI:
  253. #endif
  254. return MAX_SIMTIME;
  255. case EXPPOLICY_LINEAR: case EXPPOLICY_EXP:
  256. lifetime = exptable[a.addr] > exptable[b.addr] ? 
  257.   exptable[b.addr] : exptable[a.addr];
  258. lifetime *= lc_table_mult_by;
  259. break;
  260. #ifdef GOD_STABILITY
  261. case EXPPOLICY_GOD_TABLE:
  262. lifetime = godavglife[a.addr] > godavglife[b.addr] ? 
  263.   godavglife[b.addr] : godavglife[a.addr];
  264. lifetime *= lc_table_mult_by;
  265. break;
  266. #endif
  267. case EXPPOLICY_STATIC:
  268. lifetime = discovered ? lc_static_discover_life :
  269.   lc_static_overhear_life;
  270. break;
  271. default:
  272. assert(0);
  273. }
  275. if (lifetime < lc_minlifetime)
  276. lifetime = lc_minlifetime;
  278. return CURRENT_TIME + lifetime;
  279. }
  281. RouteCache *
  282. makeRouteCache()
  283. {
  284.   return new LinkCache();
  285. }
  287. LinkCache::LinkCache() : RouteCache()
  288. {
  289. int i = 0;
  291. for(i = 0; i <= LC_MAX_NODES; i++) {
  292. LIST_INIT(&lcache[i]);
  293. exptable[i] = lc_table_init_val;
  294. }
  296. #ifdef DSR_CACHE_STATS
  297. stat.reset();
  298. #endif
  299. dirty = -1;
  300. }
  303. int
  304. LinkCache::command(int argc, const char*const* argv)
  305. {
  306.   if(argc == 2 && strcasecmp(argv[1], "startdsr") == 0)
  307.     { 
  308.       if (ID(1,::IP) == net_id) 
  309. trace("Sconfig %.5f using LINKCACHE %d", Scheduler::instance().clock(),
  310. lc_exppolicy);
  311.       // FALL-THROUGH
  312.     }
  314.   if(argc == 3)
  315.     {   
  316.       if (strcasecmp(argv[1], "ip-addr") == 0)
  317.         {
  318.           assert(atoi(argv[2]) <= LC_MAX_NODES);
  320. #ifndef REALTIME_EXPIRE
  321.   if (atoi(argv[2]) == 1)
  322.     bzero(expirestats, sizeof(expirestats));
  323. #endif
  325.           // don't return
  326.         } 
  327.     }
  328.   return RouteCache::command(argc, argv);
  329. }
  332. void
  333. LinkCache::noticeDeadLink(const ID& from, const ID& to, Time)
  334. {
  335. Link *l = findLink(from.addr, to.addr);
  337. if (l && (l->ln_flags & LINK_FLAG_UP) &&
  338.     (lc_exppolicy == EXPPOLICY_LINEAR || 
  339.      lc_exppolicy == EXPPOLICY_EXP)) {
  340. if (lc_exppolicy == EXPPOLICY_LINEAR) {
  341. exptable[from.addr]=lc_linear_alpha*exptable[from.addr]
  342.   +(CURRENT_TIME-l->ln_insert)*(1-lc_linear_alpha);
  343. exptable[to.addr]=lc_linear_alpha*exptable[to.addr]
  344.   +(CURRENT_TIME-l->ln_insert)*(1-lc_linear_alpha);
  345. } else {
  346. exptable[from.addr] /= lc_exp_div_amt;
  347. exptable[to.addr] /= lc_exp_div_amt;
  348. }
  349. }
  351. if(lc_cache_negative_links == true) {
  352. if(l) {
  353. l->ln_flags &= ~LINK_FLAG_UP;
  354. l->ln_insert = CURRENT_TIME;
  355. l->ln_timeout = CURRENT_TIME + lc_neg_cache_life;
  356. dirty = CURRENT_TIME;
  357. } else {
  358. addLink(from, to, 0, CURRENT_TIME + lc_neg_cache_life);
  359. }
  360. }
  361. else {
  362. if(l) {
  363. #ifdef DSR_CACHE_STATS
  364. checkLink(from, to, ACTION_DEAD_LINK);
  365. #endif
  366. (void) delLink(from, to);
  367. }
  368. }
  369. }
  371. void
  372. LinkCache::noticeRouteUsed(const Path& p, Time t, const ID& who_from)
  373. {
  374.   Path stub;
  375.   int c;
  377.   if(pre_noticeRouteUsed(p, stub, t, who_from) == 0)
  378.   return;
  379.   
  380. #ifdef DSR_CACHE_STATS
  381.   int link_notice_count = stat.link_notice_count; 
  382.   int link_notice_bad_count = stat.link_notice_bad_count;   
  383. #endif
  385.   /*
  386.    * Add each link in the "path" to the route cache.
  387.    */
  388.   for(c = 0; c < stub.length() - 1; c++) {
  389.   if(addLink(stub[c], stub[c+1], LINK_FLAG_UP, 
  390.      find_timeout(stub[c], stub[c+1], false))) {
  391. #ifdef DSR_CACHE_STATS
  392. checkLink(stub[c], stub[c+1], ACTION_NOTICE_ROUTE);
  393. #endif
  394.   }
  395.   }
  397. #ifdef DSR_CACHE_STATS
  398.   if(stat.link_notice_count > link_notice_count)
  399.   stat.route_notice_count++;
  400.   if(stat.link_notice_bad_count > link_notice_bad_count)
  401.   stat.route_notice_bad_count++;
  402. #endif
  403. }
  405. void
  406. LinkCache::addRoute(const Path& route, Time t, const ID& who_from)
  407. {
  408.   Path rt;
  409.   int c;
  411.   if(pre_addRoute(route, rt, t, who_from) == 0)
  412.   return;
  413.   
  414. #ifdef DSR_CACHE_STATS
  415.   int link_add_count = stat.link_add_count; 
  416.   int link_add_bad_count = stat.link_add_bad_count;   
  417. #endif
  419.   for(c = 0; c < rt.length() - 1; c++) {
  420.   if(addLink(rt[c], rt[c+1], LINK_FLAG_UP,
  421.      find_timeout(rt[c], rt[c+1], true))) {
  422. #ifdef DSR_CACHE_STATS
  423.   checkLink(rt[c], rt[c+1], ACTION_ADD_ROUTE);
  424. #endif
  425.   }
  426.   }
  428. #ifdef DSR_CACHE_STATS
  429.   if(stat.link_add_count > link_add_count)
  430.   stat.route_add_count++;
  431.   if(stat.link_add_bad_count > link_add_bad_count)
  432.   stat.route_add_bad_count++;
  433. #endif
  434. }
  436. bool
  437. LinkCache::findRoute(ID dest, Path& route, int for_me = 0)
  438. {
  439. u_int32_t v;
  440. int rpath[MAX_SR_LEN];
  441. u_int32_t roff = 0;
  443. if(verbose_debug) dumpLink();
  445. /*
  446.  * Compute all of the shortest paths...
  447.  */
  448. if(dirty <= CURRENT_TIME) {
  449. dijkstra();
  451. // remove all of the links for nodes that are unreachable
  452. if(lc_evict_unreachable_links == true) {
  453. purgeLink();
  454. }
  455. }
  456. if(verbose_debug) dump_dijkstra(dest.addr);
  458. /*
  459.  * Trace backwards to figure out the path to DEST
  460.  */
  461. for(v = dest.addr; d[v] < INFINITY; v = pi[v]) {
  462.   //assert(v >= 1 && v <= LC_MAX_NODES);
  463. if (roff >= MAX_SR_LEN) {
  464.           // path between us and dest is too long to be useful
  465.         break;
  466. }
  468. rpath[roff] = v;
  469. roff++;
  471. if(v == net_id.addr)
  472. break;
  473. }
  475. if(roff < 2 || d[v] == INFINITY || roff >= MAX_SR_LEN) {
  476. #ifdef DSR_CACHE_STATS
  477. stat.route_find_count += 1;
  478. if (for_me) stat.route_find_for_me += 1; 
  479. stat.route_find_miss_count += 1;
  480. #endif
  481. return false; // no path
  482. }
  485. #ifdef GOD_STABILITY
  486. /* The logic for God's omniscient expiration policy:
  487.  *   if we expire in realtime, kill dead links immediately, and
  488.  *     goto top. XXX this could create unnecessary overhead.
  489.  *   if we expire on the fly, we set the timeout to an appropriate
  490.  *     value, depending on whether or not the link is valid.
  491.  */
  492. if (lc_exppolicy == EXPPOLICY_GOD_OMNI) {
  493. int last = net_id.addr;
  494. for (v=1;v<roff;v++) {
  495. Link *l = findLink(last, rpath[roff-v-1]);
  496. #ifdef REALTIME_EXPIRE
  497. if (God::instance()->hops(last, rpath[roff-v-1])!=1) {
  498. LIST_REMOVE(l, ln_link);
  499. delete l;
  500. dirty = CURRENT_TIME;
  501. return findRoute(dest, route, for_me);
  502. }
  503. #else
  504. if (God::instance()->hops(last, rpath[roff-v-1])!=1) {
  505. l->ln_timeout = CURRENT_TIME;
  506. } else {
  507. l->ln_timeout = MAX_SIMTIME;
  508. }
  509. #endif
  510. last = rpath[roff-v-1];
  511. }
  512. }
  513. #endif //GOD_STABILITY 
  516. #ifndef REALTIME_EXPIRE
  517. int last = net_id.addr;
  518. for (v=1;v<roff;v++) {
  519. Link *l = findLink(last, rpath[roff-v-1]);
  520. bool godsays = God::instance()->hops(last, rpath[roff-v-1])==1;
  521. last = rpath[roff-v-1];
  522. assert(l);
  523. if (l->expired()) {
  524. expirestats[CALLED_BAD + (godsays?IS_GOOD:IS_BAD)]++;
  525. LIST_REMOVE(l, ln_link);
  526. delete l;
  527. dirty = CURRENT_TIME;
  528. return findRoute(dest, route, for_me);
  529. } else {
  530. expirestats[CALLED_GOOD + (godsays?IS_GOOD:IS_BAD)]++;
  531. }
  532. }
  533. #endif
  535. /*
  536.  * Build the path that we need...
  537.  */
  538. ID id;
  540. route.reset();
  542. id.addr = net_id.addr;  // source route is rooted at "us"
  543. id.type = ::IP;
  544. id.link_type = LT_NONE;
  545. id.log_stat = LS_NONE;
  546. route.appendToPath(id);
  548. for(v = 1; v < roff ; v++) {
  549. assert((int) (roff - v - 1) >= 0 && (roff - v - 1) < MAX_SR_LEN);
  551. Link *l = findLink(route[v-1].addr, rpath[roff - v - 1]);
  553. assert(l && !l->expired());
  555. if (for_me)
  556. l->ln_timeout += lc_gen_use_bonus;
  558. if (lc_exppolicy == EXPPOLICY_EXP) {
  559. exptable[route[v-1].addr] += lc_exp_add_amt;
  560. exptable[rpath[roff - v - 1]] += lc_exp_add_amt;
  561. }
  563. id.addr = rpath[roff - v - 1];
  564. id.type = ::IP;
  565. id.link_type = LT_NONE;
  566. id.log_stat = LS_NONE;
  567. route.appendToPath(id);
  569. route[v-1].t = l->ln_t;
  570. route[v-1].link_type = l->ln_linktype;
  571. route[v-1].log_stat = l->ln_logstat;
  572. }
  574. #ifdef DSR_CACHE_STATS
  575. int bad = checkRoute_logall(&route, ACTION_FIND_ROUTE, 0);
  576. stat.route_find_count += 1; 
  577. if (for_me) stat.route_find_for_me += 1;     
  578. stat.route_find_bad_count += bad ? 1 : 0;
  579. stat.link_find_count += route.length() - 1;
  580. stat.link_find_bad_count +=  bad;
  581. #endif
  582. return true;
  583. }
  586. void
  587. LinkCache::Link_to_ID(Link *l, ID& id)
  588. {
  589. id.addr = l->ln_dst;
  590. id.type = ::IP;
  591. id.t = l->ln_t;
  592. id.link_type = l->ln_linktype;
  593. id.log_stat = l->ln_logstat;
  594. }
  596. ///////////////////////////////////////////////////////////////////////////
  598. /*
  599.  * Dijkstra's algorithm taken from CLR.
  600.  */
  602. void
  603. LinkCache::init_single_source(int s)
  604. {
  605. int v;
  607. for(v = 1; v <= LC_MAX_NODES; v++) {
  608. d[v] = INFINITY;
  609. #ifdef LONGEST_LIVED_ROUTE
  610. dl[v] = 0; // dies immediately
  611. #endif
  612. pi[v] = 0; // invalid node ID
  614. S[v] = false;
  615. }
  616. d[s] = 0;
  617. #ifdef LONGEST_LIVED_ROUTE
  618. dl[s] = MAX_SIMTIME;
  619. #endif
  620. }
  622. void
  623. #ifdef LONGEST_LIVED_ROUTE
  624. LinkCache::relax(u_int32_t u, u_int32_t v, u_int32_t w, double timeout)
  625. #else
  626. LinkCache::relax(u_int32_t u, u_int32_t v, u_int32_t w)
  627. #endif
  628. {
  629. assert(d[u] < INFINITY);
  630. assert(w == 1); /* make sure everything's working how I expect */
  632. if(d[v] > d[u] + w
  633. #ifdef LONGEST_LIVED_ROUTE
  634.    || (d[v] == d[u] + w && dl[v] < dl[u] && dl[v] < timeout)
  635. #endif
  636.    ) {
  637. d[v] = d[u] + w;
  638. #ifdef LONGEST_LIVED_ROUTE
  639. dl[v] = (dl[u] > timeout) ? timeout : dl[u];
  640. #endif
  641. pi[v] = u;
  642. }
  643. }
  646. int
  647. LinkCache::extract_min_q()
  648. {
  649. int u;
  650. int min_u = 0;
  652. for(u = 1; u <= LC_MAX_NODES; u++) {
  653. if(S[u] == false && d[u] < INFINITY && 
  654.    (min_u == 0 || d[u] < d[min_u] 
  655. #ifdef LONGEST_LIVED_ROUTE
  656.     || (d[u] == d[min_u] && dl[u] > dl[min_u])
  657. #endif
  658.    )) {
  659. min_u = u;
  660. }
  661. }
  662. return min_u; // (min_u == 0) ==> no valid link
  663. }
  665. void
  666. LinkCache::dijkstra()
  667. {
  668. int u;
  669. Link *v;
  671. dirty = MAX_SIMTIME;  // all of the info is up-to-date
  673. #ifdef REALTIME_EXPIRE
  674. for (u=1; u <= LC_MAX_NODES; u++) {
  675. v = lcache[u].lh_first;
  676. while (v) {
  677. if(v->ln_timeout <= CURRENT_TIME) {
  678. Link *tmp;
  679. tmp = v->ln_link.le_next;
  680. LIST_REMOVE(v, ln_link);
  681. delete v;
  682. v = tmp;
  683. } else {
  684. if (v->ln_timeout < dirty)
  685. dirty = v->ln_timeout;
  686. v = v->ln_link.le_next;
  687. }
  688. }
  689. }
  690. #endif
  692. init_single_source(net_id.addr);
  694. while((u = extract_min_q()) != 0) {
  695. S[u] = true;
  696. v = lcache[u].lh_first;
  697. for( ; v; v = v->ln_link.le_next) {
  698. if(v->ln_flags & LINK_FLAG_UP) {
  699. #ifdef LONGEST_LIVED_ROUTE
  700. relax(u, v->ln_dst, v->ln_cost, v->ln_timeout);
  701. #else
  702. relax(u, v->ln_dst, v->ln_cost);
  703. #endif
  704. }
  705. }
  706. }
  707. }
  709. void
  710. LinkCache::dump_dijkstra(int dst)
  711. {
  712. static char tbuf[512];
  713. u_int32_t u, toff = 0;
  715. bzero(tbuf, sizeof(tbuf));
  716. sprintf(tbuf, "SRC %.9f _%s_ dijkstra *%d* ",
  717. CURRENT_TIME, net_id.dump(), dst);
  718. toff = strlen(tbuf);
  720. for(u = 1; u <= LC_MAX_NODES; u++) {
  721. if(d[u] < INFINITY) {
  722. sprintf(tbuf+toff, "%d,%d,%d ", u, d[u], pi[u]);
  723. toff = strlen(tbuf);
  724. assert(toff < sizeof(tbuf));
  725. }
  726. }
  728. trace("%s", tbuf);
  729. }
  732. ///////////////////////////////////////////////////////////////////////////
  734. int
  735. LinkCache::addLink(const ID& from, const ID& to,
  736.    int flags, double timeout, int cost)
  737. {
  738. Link *l;
  739. int rc = 0;
  741. if((l = findLink(from.addr, to.addr)) == 0) {
  742. l = new Link(to.addr);
  743. assert(l);
  744. LIST_INSERT_HEAD(&lcache[from.addr], l, ln_link);
  745. dirty = CURRENT_TIME;
  746. l->ln_insert = CURRENT_TIME;
  747. rc = 1;
  748. } else if ((l->ln_flags & flags) != flags) {
  749. // we want to set flags
  750. dirty = CURRENT_TIME;
  751. l->ln_insert = CURRENT_TIME;
  752. }
  754. l->ln_t = CURRENT_TIME;
  755. l->ln_linktype = from.link_type;
  756. l->ln_flags |= flags;
  757. l->ln_cost = cost;
  758. l->ln_timeout = timeout;
  760. if(lc_bidirectional_links == false)
  761. return rc;
  763. /*
  764.  * Add the "other" direction of the link...
  765.  */
  766. if((l = findLink(to.addr, from.addr)) == 0) {
  767. l = new Link(from.addr);
  768. assert(l);
  769. l->ln_insert = CURRENT_TIME;
  770. LIST_INSERT_HEAD(&lcache[to.addr], l, ln_link);
  771. dirty = CURRENT_TIME;
  772. } else if ((l->ln_flags & flags) != flags) {
  773. // we want to set flags
  774. dirty = CURRENT_TIME;
  775. l->ln_insert = CURRENT_TIME;
  776. }
  777. l->ln_t = CURRENT_TIME;
  778. l->ln_linktype = from.link_type;
  779. l->ln_flags |= flags;
  780. l->ln_cost = cost;
  781. l->ln_timeout = timeout;
  783. return rc;
  784. }
  786. int
  787. LinkCache::delLink(const ID& from, const ID& to)
  788. {
  789. Link *l;
  790. int rc = 0;
  792. if((l = findLink(from.addr, to.addr))) {
  793. LIST_REMOVE(l, ln_link);
  794. delete l;
  795. dirty = CURRENT_TIME;
  796. rc = 1;
  797. }
  799. if(lc_bidirectional_links == false)
  800. return rc;
  802. /*
  803.  * Remove the "other" direction of the link...
  804.  */
  805. if((l = findLink(to.addr, from.addr))) {
  806. LIST_REMOVE(l, ln_link);
  807. delete l;
  808. dirty = CURRENT_TIME;
  809. }
  811. return rc;
  812. }
  814. Link*
  815. LinkCache::findLink(int from, int to)
  816. {
  817. Link *l;
  819. for(l = lcache[from].lh_first; l; l = l->ln_link.le_next) {
  820. if(l->ln_dst == to) {
  821. return l;
  822. }
  823. }
  824. return 0;
  825. }
  827. void
  828. LinkCache::purgeLink()
  829. {
  830. int u;
  831. Link *l;
  833. for(u = 1; u <= LC_MAX_NODES; u++) {
  834. if(d[u] == INFINITY) {
  835. ID from, to;
  837. from.addr = u;
  838. from.type = ::IP;
  839. from.link_type = LT_NONE;
  840. from.log_stat = LS_NONE;
  842. l = lcache[u].lh_first;
  843. for( ; l; l = l->ln_link.le_next) {
  844. Link_to_ID(l, to);
  845. #ifdef DSR_CACHE_STATS
  846. checkLink_logall(from, to, ACTION_EVICT);
  847. #endif
  848. (void) delLink(from, to);
  849. }
  850. }
  851. }
  852. }
  855. void
  856. LinkCache::dumpLink()
  857. {
  858. Link *l;
  859. int i;
  860. static char tbuf[512];
  861. u_int32_t toff = 0;
  863. bzero(tbuf, sizeof(tbuf));
  864. sprintf(tbuf, "SRC %.9f _%s_ dump-link ", CURRENT_TIME, net_id.dump());
  865. toff = strlen(tbuf);
  867. for(i = 1; i <= LC_MAX_NODES; i++) {
  868. for(l = lcache[i].lh_first; l; l = l->ln_link.le_next) {
  869. sprintf(tbuf+toff, "%d->%d, ", i, l->ln_dst);
  870. toff = strlen(tbuf);
  871. assert(toff < sizeof(tbuf));
  872. }
  873. }
  875. trace("%s", tbuf);
  876. }
  878. #ifdef DSR_CACHE_STATS
  880. /*
  881.  * Called only from "purgeLink"
  882.  */
  883. void
  884. LinkCache::checkLink_logall(const ID& from, const ID& to, int action)
  885. {
  886. Link *l = findLink(from.addr, to.addr);
  888. assert(action == ACTION_EVICT);
  889. assert(l);
  891. if(God::instance()->hops(from.addr, to.addr) != 1) {
  892. trace("SRC %.9f _%s_ %s [%d %d] %s->%s dead %d %.9f",
  893.       CURRENT_TIME, net_id.dump(),
  894.       action_name[action], 0, 0,
  895.       from.dump(), to.dump(),
  896.       l->ln_linktype, l->ln_t);
  897. }
  898. }
  900. void
  901. LinkCache::checkLink(const ID& from, const ID& to, int action)
  902. {
  903. Link *l = findLink(from.addr, to.addr);
  904. int alive = 0;
  906. assert(l);
  908. if(God::instance()->hops(from.addr, to.addr) != 1) {
  909. if(l->ln_logstat == LS_UNLOGGED) {
  910. trace("SRC %.9f _%s_ %s [%d %d] %s->%s dead %d %.9f",
  911. CURRENT_TIME, net_id.dump(),
  912. action_name[action], 0, 0,
  913. from.dump(), to.dump(),
  914. l->ln_linktype, l->ln_t);
  915. l->ln_logstat = LS_LOGGED;
  916. }
  917. } else {
  918. alive = 1;
  919. if(l->ln_logstat == LS_LOGGED) {
  920. trace("SRC %.9f _%s_ resurrected-link [%d %d] %s->%s dead %d %.9f",
  921. CURRENT_TIME, net_id.dump(), 0, 0,
  922. from.dump(), to.dump(),
  923. l->ln_linktype, l->ln_t);
  924. l->ln_logstat = LS_UNLOGGED;
  925. }
  926.         }
  928. switch(action) {
  929. case ACTION_ADD_ROUTE:
  930. stat.link_add_count += 1;
  931. if(alive == 0){
  932.         stat.link_add_bad_count += 1;
  933. }
  934. if(l->ln_linktype == LT_TESTED)
  935. stat.link_add_tested += 1;
  936. break;
  938. case ACTION_NOTICE_ROUTE:
  939. stat.link_notice_count += 1;
  940. if(alive == 0){
  941. stat.link_notice_bad_count += 1;
  942. }
  943. if(l->ln_linktype == LT_TESTED)
  944. stat.link_notice_tested += 1;
  945. break;
  946. }
  947. }
  949. void
  950. LinkCache::periodic_checkCache()
  951. {
  952.   int c;
  953.   int link_count = 0;
  954.   int link_bad_count = 0;
  955.   double link_bad_time = 0.0;
  956.   int link_bad_tested = 0;
  957.   int link_good_tested = 0;
  959. #ifndef REALTIME_EXPIRE
  960.   if (ID(1,::IP) == net_id) 
  961.     trace("SRC %.9f _%s_ cache-expire-bits %d %d %d %d",
  962.   CURRENT_TIME, net_id.dump(), expirestats[0], expirestats[1], 
  963.   expirestats[2], expirestats[3]);
  964. #endif
  966.   for(c = 1; c <= LC_MAX_NODES; c++) {
  967. Link *v = lcache[c].lh_first;
  968. for( ; v; v = v->ln_link.le_next) {
  969. link_count += 1;
  970. if(God::instance()->hops(c, v->ln_dst) != 1) {
  971. link_bad_count += 1;
  972. link_bad_time += CURRENT_TIME - v->ln_t;
  973. if(v->ln_linktype == LT_TESTED)
  974. link_bad_tested += 1;
  975. } else {
  976. if(v->ln_linktype == LT_TESTED)
  977. link_good_tested += 1;
  978. }
  979. }
  980.   }
  982.   trace("SRC %.9f _%s_ cache-summary %d %d %d %d | %d %.9f %d %d | %d %d %d %d %d | %d %d %d %d %d | %d %d %d %d %d %d",
  983. CURRENT_TIME, net_id.dump(),
  984.         0, //route_count,
  985.         0, // route_bad_count,
  986.         link_count, // subroute_count,
  987.         0, // subroute_bad_count,
  989.         link_bad_count,
  990.         link_bad_count ? link_bad_time/link_bad_count : 0.0,
  991.         link_bad_tested,
  992.         link_good_tested,
  994.         stat.route_add_count,     // always 0 -- not increment
  995.         stat.route_add_bad_count, // always 0 -- not increment
  996.         stat.link_add_count, // stat.subroute_add_count,
  997.         stat.link_add_bad_count, // stat.subroute_add_bad_count,
  998.         stat.link_add_tested,
  999.              
  1000.         stat.route_notice_count,
  1001.         stat.route_notice_bad_count,
  1002.         stat.link_notice_count, // stat.subroute_notice_count,
  1003.         stat.link_notice_bad_count, // stat.subroute_notice_bad_count,
  1004.         stat.link_notice_tested,
  1005.              
  1006.         stat.route_find_count,
  1007. stat.route_find_for_me,
  1008.         stat.route_find_bad_count,
  1009.         stat.route_find_miss_count,
  1010.         stat.subroute_find_count,
  1011.         stat.subroute_find_bad_count);
  1012.   stat.reset();
  1013. }
  1015. #endif
  1016. #endif //DSR_LINKCACHE