mobicache.cc

CBRP协议（移动adhoc中基于分簇的路由协议）ns2下的源码

/* mobicache.cc
   $Id: mobicache.cc,v 1.19 1998/09/22 13:20:32 dmaltz Exp $

   cache used in the mobicom 98 submission.  see the paper for a description
*/

extern "C" {
#include <stdio.h>
#include <stdarg.h>
};

#undef DEBUG

#include <god.h>
#include "path.h"
#include "routecache.h"
#ifdef DSR_CACHE_STATS
#include <cmu/dsr/cache_stats.h>
#endif


/* invariants

   - no path contains an id more than once
   - all paths start with the id of our node (MAC_id or net_id)
*/

#define fout stdout

static const int verbose = 0;
static const int verbose_debug = 0;

/*===============================================================
  function selectors
----------------------------------------------------------------*/
bool cache_ignore_hints = false;     // ignore all hints?
bool cache_use_overheard_routes = true; 
// if we are A, and we over hear a rt Z Y (X) W V U, do we add route
// A X W V U to the cache?


/*===============================================================
  Class declaration
----------------------------------------------------------------*/
class MobiCache;

class Cache {
friend class MobiCache;

public:
  Cache(char *name, int size, MobiCache *rtcache);
  ~Cache();

  int pickVictim(int exclude = -1);
  // returns the index of a suitable victim in the cache
  // will spare the life of exclude
  bool searchRoute(const ID& dest, int& i, Path &path, int &index);
  // look for dest in cache, starting at index, 
  //if found, rtn true with path s.t. cache[index] == path && path[i] == dest
  Path* addRoute(Path &route, int &prefix_len);
  // rtns a pointer the path in the cache that we added
  void noticeDeadLink(const ID&from, const ID& to);
  // the link from->to isn't working anymore, purge routes containing
  // it from the cache

private:
  Path *cache;
  int size;
  int victim_ptr;		// next victim for eviction
  MobiCache *routecache;
  char *name;
};

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

class MobiCache : public RouteCache {
friend class Cache;
friend class MobiHandler;

public:
  MobiCache(const ID& MAC_id, const ID& net_id,int psize = 30,int ssize = 34 );
  MobiCache();
  ~MobiCache();
  void noticeDeadLink(const ID&from, const ID& to, Time t);
  // the link from->to isn't working anymore, purge routes containing
  // it from the cache
  void noticeRouteUsed(const Path& route, Time t,
		       const ID& who_from);
  // tell the cache about a route we saw being used
  void addRoute(const Path& route, Time t, const ID& who_from);
  // add this route to the cache (presumably we did a route request
  // to find this route and don't want to lose it)
  bool findRoute(ID dest, Path& route, int for_use = 0);
  // if there is a cached path from us to dest returns true and fills in
  // the route accordingly. returns false otherwise
  // if for_use, then we assume that the node really wants to keep 
  // the returned route so it will be promoted to primary storage if not there
  // already
  int command(int argc, const char*const* argv);

protected:
  Cache *primary_cache;   /* routes that we are using, or that we have reason
			    to believe we really want to hold on to */
  Cache *secondary_cache; /* routes we've learned via a speculative process
			    that might not pan out */

#ifdef DSR_CACHE_STATS
  void periodic_checkCache(void);
  void checkRoute(Path *p, int action, int prefix_len);
  void checkRoute(Path &p, int&, int&, double&, int&, int&, double &);
#endif
};


RouteCache *
makeRouteCache()
{
  return new MobiCache();
}


/*===============================================================
  OTcl definition
----------------------------------------------------------------*/
static class MobiCacheClass : public TclClass {
public:
        MobiCacheClass() : TclClass("MobiCache") {}
        TclObject* create(int, const char*const*) {
                return (new MobiCache);
        }
} class_MobiCache;

/*===============================================================
 Constructors
----------------------------------------------------------------*/
MobiCache::MobiCache(): RouteCache()
{
  primary_cache = new Cache("primary", 30, this);
  secondary_cache = new Cache("secondary", 34, this);
  assert(primary_cache != NULL && secondary_cache != NULL);
#ifdef DSR_CACHE_STATS
	stat.reset();
#endif
}

MobiCache::~MobiCache()
{
  delete primary_cache;
  delete secondary_cache;
}

int
MobiCache::command(int argc, const char*const* argv)
{
  if(argc == 2 && strcasecmp(argv[1], "startdsr") == 0)
    { 
      if (ID(1,::IP) == net_id) 
	trace("Sconfig %.5f using MOBICACHE", Scheduler::instance().clock());
      // FALL-THROUGH
    }
  return RouteCache::command(argc, argv);
}

#ifdef DSR_CACHE_STATS

void
MobiCache::periodic_checkCache()
{
  int c;
  int route_count = 0;
  int route_bad_count = 0;
  int subroute_count = 0;
  int subroute_bad_count = 0;
  int link_bad_count = 0;
  double link_bad_time = 0.0;
  int link_bad_tested = 0;
  int link_good_tested = 0;

  for(c = 0; c < primary_cache->size; c++)
    {
      int x = 0;

      if (primary_cache->cache[c].length() == 0) continue;

      checkRoute(primary_cache->cache[c],
                 x,
                 link_bad_count,
                 link_bad_time,
                 link_bad_tested,
                 link_good_tested,
		 stat.link_good_time);

      route_count += 1;
      route_bad_count += x ? 1 : 0;
      
      subroute_count += primary_cache->cache[c].length() - 1;
      subroute_bad_count += x;
    }
  for(c = 0; c < secondary_cache->size; c++)
    {
      int x = 0;

      if (secondary_cache->cache[c].length() == 0) continue;

      checkRoute(secondary_cache->cache[c],
                 x,
                 link_bad_count,
                 link_bad_time,
                 link_bad_tested,
                 link_good_tested,
		 stat.link_good_time);

      route_count += 1;
      route_bad_count += x ? 1 : 0;

      subroute_count += secondary_cache->cache[c].length() - 1;
      subroute_bad_count += x;
    }

  // lifetime of good link is (total time) / (total num links - num bad links)
  stat.link_good_time = stat.link_good_time / (subroute_count - link_bad_count);

 if (verbose) 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 %.9f",
	Scheduler::instance().clock(), net_id.dump(),
        route_count,
        route_bad_count,
        subroute_count,
        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,
        stat.route_add_bad_count,
        stat.subroute_add_count,
        stat.subroute_add_bad_count,
        stat.link_add_tested,
             
        stat.route_notice_count,
        stat.route_notice_bad_count,
        stat.subroute_notice_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.link_good_time);
  stat.reset();
}

#endif /* DSR_CACHE_STATS */

/*===============================================================
  member functions
----------------------------------------------------------------*/

void
MobiCache::addRoute(const Path& route, Time t, const ID& who_from)
// add this route to the cache (presumably we did a route request
// to find this route and don't want to lose it)
// who_from is the id of the routes provider
{
  Path rt;

  if(pre_addRoute(route, rt, t, who_from) == 0)
    return;

  // must call addRoute before checkRoute
  int prefix_len = 0;

#ifdef DSR_CACHE_STATS
  Path *p = primary_cache->addRoute(rt, prefix_len);
  checkRoute(p, ACTION_ADD_ROUTE, prefix_len);
#else
  (void) primary_cache->addRoute(rt, prefix_len);
#endif
}

void
MobiCache::noticeDeadLink(const ID&from, const ID& to, Time)
  // the link from->to isn't working anymore, purge routes containing
  // it from the cache
{
  if(verbose_debug)
    trace("SRC %.9f _%s_ dead link %s->%s",
	  Scheduler::instance().clock(), net_id.dump(),
	  from.dump(), to.dump());
  
  primary_cache->noticeDeadLink(from, to);
  secondary_cache->noticeDeadLink(from, to);
  return;
}


void
MobiCache::noticeRouteUsed(const Path& p, Time t, const ID& who_from)
// tell the cache about a route we saw being used
{
  Path stub;
  if(pre_noticeRouteUsed(p, stub, t, who_from) == 0)
    return;

  int prefix_len = 0;

#ifdef DSR_CACHE_STATS
  Path *p0 = secondary_cache->addRoute(stub, prefix_len);
  checkRoute(p0, ACTION_NOTICE_ROUTE, prefix_len);
#else
  (void) secondary_cache->addRoute(stub, prefix_len);
#endif
}

bool
MobiCache::findRoute(ID dest, Path& route, int for_me)
// if there is a cached path from us to dest returns true and fills in
// the route accordingly. returns false otherwise
// if for_me, then we assume that the node really wants to keep 
// the returned route so it will be promoted to primary storage if not there
// already
{
  Path path;
  int min_index = -1;
  int min_length = MAX_SR_LEN + 1;
  int min_cache = 0;		// 2 == primary, 1 = secondary
  int index;
  int len;

  assert(!(net_id == invalid_addr));

  index = 0;
  while (primary_cache->searchRoute(dest, len, path, index))
    {
      min_cache = 2;
      if (len < min_length)
	{
	  min_length = len;
	  route = path;
	}
      index++;
    }
  
  index = 0;
  while (secondary_cache->searchRoute(dest, len, path, index))
    {
      if (len < min_length)
	{
	  min_index = index;
	  min_cache = 1;
	  min_length = len;
	  route = path;
	}
      index++;
    }

  if (min_cache == 1 && for_me)
    { // promote the found route to the primary cache
      int prefix_len;
 
      primary_cache->addRoute(secondary_cache->cache[min_index], prefix_len);

      // no need to run checkRoute over the Path* returned from
      // addRoute() because whatever was added was already in
      // the cache.

      //   prefix_len = 0
      //        - victim was selected in primary cache
      //        - data should be "silently" migrated from primary to the
      //          secondary cache
      //   prefix_len > 0
      //        - there were two copies of the first prefix_len routes
      //          in the cache, but after the migration, there will be
      //          only one.
      //        - log the first prefix_len bytes of the secondary cache
      //          entry as "evicted"
      if(prefix_len > 0)
        {
          secondary_cache->cache[min_index].setLength(prefix_len);
#ifdef DSR_CACHE_STATS
          checkRoute_logall(&secondary_cache->cache[min_index], 
                            ACTION_EVICT, 0);
#endif
        }
      secondary_cache->cache[min_index].setLength(0); // kill route