simplecache.cc

动态路由协议dsr改进算法

	      dest.dump(), min_cache == 1 ? "secondary" : "primary",
	      route.dump());	
#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.subroute_find_count += route.length() - 1;
      stat.subroute_find_bad_count += bad;
#endif
      return true;
    }
  else
    {
      if (verbose_debug)
        trace("SRC %.9f _%s_ find-route [%d] %s->%s miss %d %.9f",
              Scheduler::instance().clock(), net_id.dump(),
              0, net_id.dump(), dest.dump(), 0, 0.0);
#ifdef DSR_CACHE_STATS
      stat.route_find_count += 1;
      if (for_me) stat.route_find_for_me += 1;
      stat.route_find_miss_count += 1;
#endif
      return false;
    }
}

/*===========================================================================
  class Cache routines
---------------------------------------------------------------------------*/

Cache::Cache(char *name, int size, MobiCache *rtcache)
{
  this->name = name;
  this->size = size;
  cache = new Path[size];
  routecache = rtcache;
  victim_ptr = 0;
}

Cache::~Cache() 
{
  delete[] cache;
}

bool 
Cache::searchRoute(const ID& dest, int& i, Path &path, int &index)
  // look for dest in cache, starting at index, 
  //if found, return true with path s.t. cache[index] == path && path[i] == dest
{
  for (; index < size; index++)
    for (int n = 0 ; n < cache[index].length(); n++)
      if (cache[index][n] == dest) 
	{
	  i = n;
	  path = cache[index];
	  return true;
	}
  return false;
}

Path*
Cache::addRoute(Path & path, int &common_prefix_len)
{
  int index, m, n;
  int victim;

  // see if this route is already in the cache
  for (index = 0 ; index < size ; index++)
    { // for all paths in the cache
      for (n = 0 ; n < cache[index].length() ; n ++)
	{ // for all nodes in the path
	  if (n >= path.length()) break;
	  if (cache[index][n] != path[n]) break;
	}
      if (n == cache[index].length()) 
	{ // new rt completely contains cache[index] (or cache[index] is empty)
          common_prefix_len = n;
          for ( ; n < path.length() ; n++)
            cache[index].appendToPath(path[n]);
	  if (verbose_debug)
	    routecache->trace("SRC %.9f _%s_ %s suffix-rule (len %d/%d) %s",
   	      Scheduler::instance().clock(), routecache->net_id.dump(),
              name, n, path.length(), path.dump());	
	  goto done;
	}
      else if (n == path.length())
	{ // new route already contained in the cache
          common_prefix_len = n;
	  if (verbose_debug)
	    routecache->trace("SRC %.9f _%s_ %s prefix-rule (len %d/%d) %s",
   	      Scheduler::instance().clock(), routecache->net_id.dump(),
	      name, n, cache[index].length(), cache[index].dump());	
	  goto done;
	}
      else 
	{ // keep looking at the rest of the cache 
	}
    } 

  // there are some new goodies in the new route
  victim = pickVictim();
  if(verbose_debug) {
    routecache->trace("SRC %.9f _%s_ %s evicting %s",
		      Scheduler::instance().clock(), routecache->net_id.dump(),
		      name, cache[victim].dump());	
    routecache->trace("SRC %.9f _%s_ while adding %s",
		      Scheduler::instance().clock(), routecache->net_id.dump(),
		      path.dump());	
  }
  cache[victim].reset();
  CopyIntoPath(cache[victim], path, 0, path.length() - 1);
  common_prefix_len = 0;
  index = victim; // remember which cache line we stuck the path into

done:

#ifdef DEBUG
  {
    Path &p = path;
    int c;
    char buf[1000];
    char *ptr = buf;
    ptr += sprintf(buf,"Sdebug %.9f _%s_ adding ", 
		   Scheduler::instance().clock(), routecache->net_id.dump());
    for (c = 0 ; c < p.length(); c++)
      ptr += sprintf(ptr,"%s [%d %.9f] ",p[c].dump(), p[c].link_type, p[c].t);
    routecache->trace(buf);
  }
#endif //DEBUG

  // freshen all the timestamps on the links in the cache
  for (m = 0 ; m < size ; m++)
    { // for all paths in the cache

#ifdef DEBUG
  {
    if (cache[m].length() == 0) continue;

    Path &p = cache[m];
    int c;
    char buf[1000];
    char *ptr = buf;
    ptr += sprintf(buf,"Sdebug %.9f _%s_ checking ", 
		   Scheduler::instance().clock(), routecache->net_id.dump());
    for (c = 0 ; c < p.length(); c++)
      ptr += sprintf(ptr,"%s [%d %.9f] ",p[c].dump(), p[c].link_type, p[c].t);
    routecache->trace(buf);
  }
#endif //DEBUG
      
      for (n = 0 ; n < cache[m].length() - 1 ; n ++)
	{ // for all nodes in the path
	  if (n >= path.length() - 1) break;
	  if (cache[m][n] != path[n]) break;
	  if (cache[m][n+1] == path[n+1])
	    { // freshen the timestamps and type of the link	      

#ifdef DEBUG
routecache->trace("Sdebug %.9f _%s_ freshening %s->%s to %d %.9f",
		  Scheduler::instance().clock(), routecache->net_id.dump(),
		  path[n].dump(), path[n+1].dump(), path[n].link_type,
		  path[n].t);
#endif //DEBUG

	      cache[m][n].t = path[n].t;
	      cache[m][n].link_type = path[n].link_type;
	      /* NOTE: we don't check to see if we're turning a TESTED
		 into an UNTESTED link.  Last change made rules -dam 5/19/98 */
	    }
	}
    }
  return &cache[index];
}


void
Cache::noticeDeadLink(const ID&from, const ID& to)
  // the link from->to isn't working anymore, purge routes containing
  // it from the cache
{  
  for (int p = 0 ; p < size ; p++)
    { // for all paths in the cache
      for (int n = 0 ; n < (cache[p].length()-1) ; n ++)
	{ // for all nodes in the path
	  if (cache[p][n] == from && cache[p][n+1] == to)
	    {
	      if(verbose_debug)
		routecache->trace("SRC %.9f _%s_ %s truncating %s %s",
                                  Scheduler::instance().clock(),
                                  routecache->net_id.dump(),
                                  name, cache[p].dump(),
                                  cache[p].owner().dump());
#ifdef DSR_CACHE_STATS
              routecache->checkRoute(&cache[p], ACTION_CHECK_CACHE, 0);
              routecache->checkRoute_logall(&cache[p], ACTION_DEAD_LINK, n);
#endif	      
	      if (n == 0)
		cache[p].reset();        // kill the whole path
	      else {
		cache[p].setLength(n+1); // truncate the path here
                cache[p][n].log_stat = LS_UNLOGGED;
              }

	      if(verbose_debug)
		routecache->trace("SRC %.9f _%s_ to %s %s",
		      Scheduler::instance().clock(), routecache->net_id.dump(),
		      cache[p].dump(), cache[p].owner().dump());

	      break;
	    } // end if this is a dead link
	} // end for all nodes
    } // end for all paths
  return;
}

int
Cache::pickVictim(int exclude)
// returns the index of a suitable victim in the cache
// never return exclude as the victim, but rather spare their life
{
  for(int c = 0; c < size ; c++)
    if (cache[c].length() == 0) return c;
  
  int victim = victim_ptr;
  while (victim == exclude)
    {
      victim_ptr = (victim_ptr+1 == size) ? 0 : victim_ptr+1;
      victim = victim_ptr;
    }
  victim_ptr = (victim_ptr+1 == size) ? 0 : victim_ptr+1;

#ifdef DSR_CACHE_STATS
  routecache->checkRoute(&cache[victim], ACTION_CHECK_CACHE, 0);
  int bad = routecache->checkRoute_logall(&cache[victim], ACTION_EVICT, 0);
  routecache->trace("SRC %.9f _%s_ evicting %d %d %s",
                    Scheduler::instance().clock(), routecache->net_id.dump(),
                    cache[victim].length() - 1, bad, name);
#endif
  return victim;
}

#ifdef DSR_CACHE_STATS

/*
 * Called only for the once-per-second cache check.
 */
void
MobiCache::checkRoute(Path & p,
                      int & subroute_bad_count,
                      int & link_bad_count,
                      double & link_bad_time,
                      int & link_bad_tested,
                      int & link_good_tested,
		      double & link_good_time)
{
  int c;
  int flag = 0;

  if(p.length() == 0)
    return;
  assert(p.length() >= 2);

  for (c = 0; c < p.length() - 1; c++)
    {
      assert(LS_UNLOGGED == p[c].log_stat || LS_LOGGED == p[c].log_stat );
      if (God::instance()->hops(p[c].getNSAddr_t(), p[c+1].getNSAddr_t()) != 1)
	{ // the link's dead
          if(p[c].log_stat == LS_UNLOGGED)
	    {
	      trace("SRC %.9f _%s_ check-cache [%d %d] %s->%s dead %d %.9f",
		    Scheduler::instance().clock(), net_id.dump(),
		    p.length(), c, p[c].dump(), p[c+1].dump(),
                    p[c].link_type, p[c].t);
	      p[c].log_stat = LS_LOGGED;
	    }
          if(flag == 0)
            {
              subroute_bad_count += p.length() - c - 1;
              flag = 1;
            }
          link_bad_count += 1;
          link_bad_time += Scheduler::instance().clock() - p[c].t;
          link_bad_tested += (p[c].link_type == LT_TESTED) ? 1 : 0;
	}
      else
        {
	  
	  link_good_time += Scheduler::instance().clock() - p[c].t;
	  
          if(p[c].log_stat == LS_LOGGED)
            {
              trace("SRC %.9f _%s_ resurrected-link [%d %d] %s->%s dead %d %.9f",
                    Scheduler::instance().clock(), net_id.dump(),
                    p.length(), c, p[c].dump(), p[c+1].dump(),
                    p[c].link_type, p[c].t);
              p[c].log_stat = LS_UNLOGGED;
            }
          link_good_tested += (p[c].link_type == LT_TESTED) ? 1 : 0;
        }
    }
}

void
MobiCache::checkRoute(Path *p, int action, int prefix_len)
{
  int c;
  int subroute_bad_count = 0;
  int tested = 0;

  if(p->length() == 0)
    return;
  assert(p->length() >= 2);

  assert(action == ACTION_ADD_ROUTE ||
         action == ACTION_CHECK_CACHE ||
         action == ACTION_NOTICE_ROUTE);

  for (c = 0; c < p->length() - 1; c++)
    {
      if (God::instance()->hops((*p)[c].getNSAddr_t(),
                                (*p)[c+1].getNSAddr_t()) != 1)
	{ // the link's dead
          if((*p)[c].log_stat == LS_UNLOGGED)
            {
              trace("SRC %.9f _%s_ %s [%d %d] %s->%s dead %d %.9f",
                    Scheduler::instance().clock(), net_id.dump(),
                    action_name[action], p->length(), c,
                    (*p)[c].dump(), (*p)[c+1].dump(),
                    (*p)[c].link_type, (*p)[c].t);

              (*p)[c].log_stat = LS_LOGGED;
            }

          if(subroute_bad_count == 0)
            subroute_bad_count = p->length() - c - 1;
	}
      else
        {
          if((*p)[c].log_stat == LS_LOGGED)
            {
              trace("SRC %.9f _%s_ resurrected-link [%d %d] %s->%s dead %d %.9f",
                    Scheduler::instance().clock(), net_id.dump(),
                    p->length(), c, (*p)[c].dump(), (*p)[c+1].dump(),
                    (*p)[c].link_type, (*p)[c].t);
              (*p)[c].log_stat = LS_UNLOGGED;
            }
        }
      tested += (*p)[c].link_type == LT_TESTED ? 1 : 0;
    }

  /*
   * Add Route or Notice Route actually did something
   */
  if(prefix_len < p->length())
    {
      switch(action)
        {
        case ACTION_ADD_ROUTE:
          stat.route_add_count += 1;
          stat.route_add_bad_count += subroute_bad_count ? 1 : 0;
          stat.subroute_add_count += p->length() - prefix_len - 1;
          stat.subroute_add_bad_count += subroute_bad_count;
          stat.link_add_tested += tested;
          break;

        case ACTION_NOTICE_ROUTE:
          stat.route_notice_count += 1;
          stat.route_notice_bad_count += subroute_bad_count ? 1 : 0;
          stat.subroute_notice_count += p->length() - prefix_len - 1;
          stat.subroute_notice_bad_count += subroute_bad_count;
          stat.link_notice_tested += tested;
          break;
        }
    }
}
#endif /* DSR_CACHE_STATS */

#endif /* DSR_SIMPLECACHE */