linkcache.cc

NS2的dsr-ocean仿真代码,对学习研究NS2的人非常有研究价值

			last = rpath[roff-v-1];
		}
	}
#endif //GOD_STABILITY 


#ifndef REALTIME_EXPIRE
	int last = net_id.addr;
	for (v=1;v<roff;v++) {
		Link *l = findLink(last, rpath[roff-v-1]);
		bool godsays = God::instance()->hops(last, rpath[roff-v-1])==1;
		last = rpath[roff-v-1];
		assert(l);
		if (l->expired()) {
			expirestats[CALLED_BAD + (godsays?IS_GOOD:IS_BAD)]++;
			LIST_REMOVE(l, ln_link);
			delete l;
			dirty = CURRENT_TIME;
			return findRoute(dest, route, for_me);
		} else {
			expirestats[CALLED_GOOD + (godsays?IS_GOOD:IS_BAD)]++;
		}
	}
#endif

	/*
	 * Build the path that we need...
	 */
	ID id;

	route.reset();

	id.addr = net_id.addr;  // source route is rooted at "us"
	id.type = ::IP;
	id.link_type = LT_NONE;
	id.log_stat = LS_NONE;
	route.appendToPath(id);

	for(v = 1; v < roff ; v++) {
		assert((int) (roff - v - 1) >= 0 && (roff - v - 1) < MAX_SR_LEN);

		Link *l = findLink(route[v-1].addr, rpath[roff - v - 1]);

		assert(l && !l->expired());

		if (for_me)
			l->ln_timeout += lc_gen_use_bonus;

		if (lc_exppolicy == EXPPOLICY_EXP) {
			exptable[route[v-1].addr] += lc_exp_add_amt;
			exptable[rpath[roff - v - 1]] += lc_exp_add_amt;
		}

		id.addr = rpath[roff - v - 1];
		id.type = ::IP;
		id.link_type = LT_NONE;
		id.log_stat = LS_NONE;
		route.appendToPath(id);

		route[v-1].t = l->ln_t;
		route[v-1].link_type = l->ln_linktype;
		route[v-1].log_stat = l->ln_logstat;
	}
	
#ifdef DSR_CACHE_STATS
	int bad = checkRoute_logall(&route, ACTION_FIND_ROUTE, 0);
	stat.route_find_count += 1; 
	if (for_me) stat.route_find_for_me += 1;     
	stat.route_find_bad_count += bad ? 1 : 0;
	stat.link_find_count += route.length() - 1;
	stat.link_find_bad_count +=  bad;
#endif
	return true;
}


void
LinkCache::Link_to_ID(Link *l, ID& id)
{
	id.addr = l->ln_dst;
	id.type = ::IP;
	id.t = l->ln_t;
	id.link_type = l->ln_linktype;
	id.log_stat = l->ln_logstat;
}

///////////////////////////////////////////////////////////////////////////

/*
 * Dijkstra's algorithm taken from CLR.
 */

void
LinkCache::init_single_source(int s)
{
	int v;

	for(v = 1; v <= LC_MAX_NODES; v++) {
		d[v] = INFINITY;
#ifdef LONGEST_LIVED_ROUTE
		dl[v] = 0; // dies immediately
#endif
		pi[v] = 0; // invalid node ID

		S[v] = false;
	}
	d[s] = 0;
#ifdef LONGEST_LIVED_ROUTE
	dl[s] = MAX_SIMTIME;
#endif
}

void
#ifdef LONGEST_LIVED_ROUTE
LinkCache::relax(u_int32_t u, u_int32_t v, u_int32_t w, double timeout)
#else
LinkCache::relax(u_int32_t u, u_int32_t v, u_int32_t w)
#endif
{
	assert(d[u] < INFINITY);
	assert(w == 1); /* make sure everything's working how I expect */

	if(d[v] > d[u] + w
#ifdef LONGEST_LIVED_ROUTE
	   || (d[v] == d[u] + w && dl[v] < dl[u] && dl[v] < timeout)
#endif
	   ) {
		d[v] = d[u] + w;
#ifdef LONGEST_LIVED_ROUTE
		dl[v] = (dl[u] > timeout) ? timeout : dl[u];
#endif
		pi[v] = u;
	}
}


int
LinkCache::extract_min_q()
{
	int u;
	int min_u = 0;

	for(u = 1; u <= LC_MAX_NODES; u++) {
		if(S[u] == false && d[u] < INFINITY && 
		   (min_u == 0 || d[u] < d[min_u] 
#ifdef LONGEST_LIVED_ROUTE
		    || (d[u] == d[min_u] && dl[u] > dl[min_u])
#endif
		   )) {
			min_u = u;
		}
	}
	return min_u; // (min_u == 0) ==> no valid link
}

void
LinkCache::dijkstra()
{
	int u;	
	Link *v;

	dirty = MAX_SIMTIME;  // all of the info is up-to-date

#ifdef REALTIME_EXPIRE
	for (u=1; u <= LC_MAX_NODES; u++) {
		v = lcache[u].lh_first;
		while (v) {
			if(v->ln_timeout <= CURRENT_TIME) {
				Link *tmp;
				tmp = v->ln_link.le_next;
				LIST_REMOVE(v, ln_link);
				delete v;
				v = tmp;
			} else {
				if (v->ln_timeout < dirty)
					dirty = v->ln_timeout;
				v = v->ln_link.le_next;
			}
		}
	}
#endif

	init_single_source(net_id.addr);

	while((u = extract_min_q()) != 0) {
		S[u] = true;
		v = lcache[u].lh_first;
		for( ; v; v = v->ln_link.le_next) {
			if(v->ln_flags & LINK_FLAG_UP) {
#ifdef LONGEST_LIVED_ROUTE
				relax(u, v->ln_dst, v->ln_cost, v->ln_timeout);
#else
				relax(u, v->ln_dst, v->ln_cost);
#endif
			}
		}
	}
}

void
LinkCache::dump_dijkstra(int dst)
{
	static char tbuf[512];
	u_int32_t u, toff = 0;

	bzero(tbuf, sizeof(tbuf));
	sprintf(tbuf, "SRC %.9f _%s_ dijkstra *%d* ",
		CURRENT_TIME, net_id.dump(), dst);
	toff = strlen(tbuf);

	for(u = 1; u <= LC_MAX_NODES; u++) {
		if(d[u] < INFINITY) {
			sprintf(tbuf+toff, "%d,%d,%d ", u, d[u], pi[u]);
			toff = strlen(tbuf);
			assert(toff < sizeof(tbuf));
		}
	}

	trace("%s", tbuf);
}
	

///////////////////////////////////////////////////////////////////////////

int
LinkCache::addLink(const ID& from, const ID& to,
		   int flags, double timeout, int cost)
{
	Link *l;
	int rc = 0;

	if((l = findLink(from.addr, to.addr)) == 0) {
		l = new Link(to.addr);
		assert(l);
		LIST_INSERT_HEAD(&lcache[from.addr], l, ln_link);
		dirty = CURRENT_TIME;
		l->ln_insert = CURRENT_TIME;
		rc = 1;
	} else if ((l->ln_flags & flags) != flags) {
		// we want to set flags
		dirty = CURRENT_TIME;
		l->ln_insert = CURRENT_TIME;
	}

	l->ln_t = CURRENT_TIME;
	l->ln_linktype = from.link_type;
	l->ln_flags |= flags;
	l->ln_cost = cost;
	l->ln_timeout = timeout;

	if(lc_bidirectional_links == false)
		return rc;

	/*
	 * Add the "other" direction of the link...
	 */
	if((l = findLink(to.addr, from.addr)) == 0) {
		l = new Link(from.addr);
		assert(l);
		l->ln_insert = CURRENT_TIME;
		LIST_INSERT_HEAD(&lcache[to.addr], l, ln_link);
		dirty = CURRENT_TIME;
	} else if ((l->ln_flags & flags) != flags) {
		// we want to set flags
		dirty = CURRENT_TIME;
		l->ln_insert = CURRENT_TIME;
	}
	l->ln_t = CURRENT_TIME;
	l->ln_linktype = from.link_type;
	l->ln_flags |= flags;
	l->ln_cost = cost;
	l->ln_timeout = timeout;

	return rc;
}

int
LinkCache::delLink(const ID& from, const ID& to)
{
	Link *l;
	int rc = 0;

	if((l = findLink(from.addr, to.addr))) {
		LIST_REMOVE(l, ln_link);
		delete l;
		dirty = CURRENT_TIME;
		rc = 1;
	}

	if(lc_bidirectional_links == false)
		return rc;

	/*
	 * Remove the "other" direction of the link...
	 */
	if((l = findLink(to.addr, from.addr))) {
		LIST_REMOVE(l, ln_link);
		delete l;
		dirty = CURRENT_TIME;
	}

	return rc;
}

Link*
LinkCache::findLink(int from, int to)
{
	Link *l;

	for(l = lcache[from].lh_first; l; l = l->ln_link.le_next) {
		if(l->ln_dst == to) {
			return l;
		}
	}
	return 0;
}

void
LinkCache::purgeLink()
{
	int u;
	Link *l;

	for(u = 1; u <= LC_MAX_NODES; u++) {
		if(d[u] == INFINITY) {
			ID from, to;

			from.addr = u;
			from.type = ::IP;
			from.link_type = LT_NONE;
			from.log_stat = LS_NONE;

			l = lcache[u].lh_first;
			for( ; l; l = l->ln_link.le_next) {
				Link_to_ID(l, to);
#ifdef DSR_CACHE_STATS
				checkLink_logall(from, to, ACTION_EVICT);
#endif
				(void) delLink(from, to);
			}
		}
	}
}


void
LinkCache::dumpLink()
{
	Link *l;
	int i;
	static char tbuf[512];
	u_int32_t toff = 0;

	bzero(tbuf, sizeof(tbuf));
	sprintf(tbuf, "SRC %.9f _%s_ dump-link ", CURRENT_TIME, net_id.dump());
	toff = strlen(tbuf);

	for(i = 1; i <= LC_MAX_NODES; i++) {
		for(l = lcache[i].lh_first; l; l = l->ln_link.le_next) {
			sprintf(tbuf+toff, "%d->%d, ", i, l->ln_dst);
			toff = strlen(tbuf);
			assert(toff < sizeof(tbuf));
		}
	}

	trace("%s", tbuf);
}

#ifdef DSR_CACHE_STATS

/*
 * Called only from "purgeLink"
 */
void
LinkCache::checkLink_logall(const ID& from, const ID& to, int action)
{
	Link *l = findLink(from.addr, to.addr);

	assert(action == ACTION_EVICT);
	assert(l);

	if(God::instance()->hops(from.addr, to.addr) != 1) {
		trace("SRC %.9f _%s_ %s [%d %d] %s->%s dead %d %.9f",
		      CURRENT_TIME, net_id.dump(),
		      action_name[action], 0, 0,
		      from.dump(), to.dump(),
		      l->ln_linktype, l->ln_t);
	}
}

void
LinkCache::checkLink(const ID& from, const ID& to, int action)
{
	Link *l = findLink(from.addr, to.addr);
	int alive = 0;

	assert(l);

	if(God::instance()->hops(from.addr, to.addr) != 1) {
		if(l->ln_logstat == LS_UNLOGGED) {
			trace("SRC %.9f _%s_ %s [%d %d] %s->%s dead %d %.9f",
				CURRENT_TIME, net_id.dump(),
				action_name[action], 0, 0,
				from.dump(), to.dump(),
				l->ln_linktype, l->ln_t);
			l->ln_logstat = LS_LOGGED;
		}
	} else {
		alive = 1;
		if(l->ln_logstat == LS_LOGGED) {
			trace("SRC %.9f _%s_ resurrected-link [%d %d] %s->%s dead %d %.9f",
				CURRENT_TIME, net_id.dump(), 0, 0,
				from.dump(), to.dump(),
				l->ln_linktype, l->ln_t);
			l->ln_logstat = LS_UNLOGGED;
		}
        }

	switch(action) {
	case ACTION_ADD_ROUTE:
		stat.link_add_count += 1;
		if(alive == 0){
		        stat.link_add_bad_count += 1;
		}
		if(l->ln_linktype == LT_TESTED)
			stat.link_add_tested += 1;
		break;

	case ACTION_NOTICE_ROUTE:
		stat.link_notice_count += 1;
		if(alive == 0){
			stat.link_notice_bad_count += 1;
		}
		if(l->ln_linktype == LT_TESTED)
			stat.link_notice_tested += 1;
		break;
	}
}

void
LinkCache::periodic_checkCache()
{
  int c;
  int link_count = 0;
  int link_bad_count = 0;
  double link_bad_time = 0.0;
  int link_bad_tested = 0;
  int link_good_tested = 0;

#ifndef REALTIME_EXPIRE
  if (ID(1,::IP) == net_id) 
    trace("SRC %.9f _%s_ cache-expire-bits %d %d %d %d",
	  CURRENT_TIME, net_id.dump(), expirestats[0], expirestats[1], 
	  expirestats[2], expirestats[3]);
#endif

  for(c = 1; c <= LC_MAX_NODES; c++) {
	Link *v = lcache[c].lh_first;
	for( ; v; v = v->ln_link.le_next) {
		link_count += 1;
		if(God::instance()->hops(c, v->ln_dst) != 1) {
			link_bad_count += 1;
			link_bad_time += CURRENT_TIME - v->ln_t;
			if(v->ln_linktype == LT_TESTED)
				link_bad_tested += 1;
		} else {
			if(v->ln_linktype == LT_TESTED)
				link_good_tested += 1;
		}
	}
  }

  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",
	CURRENT_TIME, net_id.dump(),
        0, //route_count,
        0, // route_bad_count,
        link_count, // subroute_count,
        0, // subroute_bad_count,

        link_bad_count,
        link_bad_count ? link_bad_time/link_bad_count : 0.0,
        link_bad_tested,
        link_good_tested,

        stat.route_add_count,     // always 0 -- not increment
        stat.route_add_bad_count, // always 0 -- not increment
        stat.link_add_count, // stat.subroute_add_count,
        stat.link_add_bad_count, // stat.subroute_add_bad_count,
        stat.link_add_tested,
             
        stat.route_notice_count,
        stat.route_notice_bad_count,
        stat.link_notice_count, // stat.subroute_notice_count,
        stat.link_notice_bad_count, // stat.subroute_notice_bad_count,
        stat.link_notice_tested,
             
        stat.route_find_count,
	stat.route_find_for_me,
        stat.route_find_bad_count,
        stat.route_find_miss_count,
        stat.subroute_find_count,
        stat.subroute_find_bad_count);
  stat.reset();
}

#endif
#endif //DSR_LINKCACHE