linktable.cc

COPE the first practical network coding scheme which is developped on click

    /* why isn't there just push? */
    for (int i=reverse_route.size() - 1; i >= 0; i--) {
      route.push_back(reverse_route[i]);
    }
    return route;
  }

  return reverse_route;
}

String routes_to_string(Vector<Path> routes) {
  StringAccum sa;
  for (int x = 1; x < routes.size(); x++) {
    sa << path_to_string(routes[x]).cc() << "\n";
  }
  return sa.take_string();
}


String 
LinkTable::print_links() 
{
  StringAccum sa;
  struct timeval now;
  click_gettimeofday(&now);
  for (LTIter iter = _links.begin(); iter; iter++) {
    LinkInfo n = iter.value();
    sa << n._from.s().cc() << " " << n._to.s().cc();
    sa << " " << n._metric;
    sa << " " << n._seq << " " << n.age() << "\n";
  }
  return sa.take_string();
}

static int ipaddr_sorter(const void *va, const void *vb) {
    IPAddress *a = (IPAddress *)va, *b = (IPAddress *)vb;
    if (a->addr() == b->addr()) {
	return 0;
    } 
    return (ntohl(a->addr()) < ntohl(b->addr())) ? -1 : 1;
}


String 
LinkTable::print_routes(bool from_me) 
{
  StringAccum sa;

  Vector<IPAddress> ip_addrs;
  
  for (HTIter iter = _hosts.begin(); iter; iter++)
    ip_addrs.push_back(iter.key());
  
  click_qsort(ip_addrs.begin(), ip_addrs.size(), sizeof(IPAddress), ipaddr_sorter);
  
  for (int x = 0; x < ip_addrs.size(); x++) {
    IPAddress ip = ip_addrs[x];
    Vector <IPAddress> r = best_route(ip, from_me);
    if (valid_route(r)) {
      sa << ip.s().cc() << " ";
      for (int i = 0; i < r.size(); i++) {
	sa << " " << r[i] << " ";
	if (i != r.size()-1) {
	  IPPair pair = IPPair(r[i], r[i+1]);
	  LinkInfo *l = _links.findp(pair);
	  assert(l);
	  sa << l->_metric;
	  sa << " (" << l->_seq << "," << l->age() << ")";
	}
      }
      sa << "\n";
    }
  }
  return sa.take_string();
}


String 
LinkTable::print_hosts() 
{
  StringAccum sa;
  Vector<IPAddress> ip_addrs;
  
  for (HTIter iter = _hosts.begin(); iter; iter++)
    ip_addrs.push_back(iter.key());
  
  click_qsort(ip_addrs.begin(), ip_addrs.size(), sizeof(IPAddress), ipaddr_sorter);
  
  for (int x = 0; x < ip_addrs.size(); x++)
    sa << ip_addrs[x] << "\n";

  return sa.take_string();
}



void 
LinkTable::clear_stale() {

  LTable links;
  for (LTIter iter = _links.begin(); iter; iter++) {
    LinkInfo nfo = iter.value();
    if ((unsigned) _stale_timeout.tv_sec >= nfo.age()) {
      links.insert(IPPair(nfo._from, nfo._to), nfo);
    } else {
      if (0) {
	click_chatter("%{element} :: %s removing link %s -> %s metric %d seq %d age %d\n",
		      this,
		      __func__,
		      nfo._from.s().cc(),
		      nfo._to.s().cc(),
		      nfo._metric,
		      nfo._seq, 
		      nfo.age());
      }
    }
  }
  _links.clear();

  for (LTIter iter = links.begin(); iter; iter++) {
    LinkInfo nfo = iter.value();
    _links.insert(IPPair(nfo._from, nfo._to), nfo);
  }

}

Vector<IPAddress> 
LinkTable::get_neighbors(IPAddress ip) 
{
  Vector<IPAddress> neighbors;

  typedef HashMap<IPAddress, bool> IPMap;
  IPMap ip_addrs;

  for (HTIter iter = _hosts.begin(); iter; iter++) {
    ip_addrs.insert(iter.value()._ip, true);
  }

  for (IPMap::const_iterator i = ip_addrs.begin(); i; i++) {
    HostInfo *neighbor = _hosts.findp(i.key());
    assert(neighbor);
    if (ip != neighbor->_ip) {
      LinkInfo *lnfo = _links.findp(IPPair(ip, neighbor->_ip));
      if (lnfo) {
	neighbors.push_back(neighbor->_ip);
      }
    }
    
  }

  return neighbors;
}
void
LinkTable::dijkstra(bool from_me) 
{
  struct timeval start;
  struct timeval finish;
  click_gettimeofday(&start);
  IPAddress src = _ip;

  typedef HashMap<IPAddress, bool> IPMap;
  IPMap ip_addrs;

  for (HTIter iter = _hosts.begin(); iter; iter++) {
    ip_addrs.insert(iter.value()._ip, true);
  }
  
  for (IPMap::const_iterator i = ip_addrs.begin(); i; i++) {
    /* clear them all initially */
    HostInfo *n = _hosts.findp(i.key());
    n->clear(from_me);
  }
  HostInfo *root_info = _hosts.findp(src);
  
  
  assert(root_info);
  
  if (from_me) {
    root_info->_prev_from_me = root_info->_ip;
    root_info->_metric_from_me = 0;
  } else {
    root_info->_prev_to_me = root_info->_ip;
    root_info->_metric_to_me = 0;
  }
  
  IPAddress current_min_ip = root_info->_ip;

  while (current_min_ip) {
    HostInfo *current_min = _hosts.findp(current_min_ip);
    assert(current_min);
    if (from_me) {
      current_min->_marked_from_me = true;
    } else {
      current_min->_marked_to_me = true;
    }


    for (IPMap::const_iterator i = ip_addrs.begin(); i; i++) {
      HostInfo *neighbor = _hosts.findp(i.key());
      assert(neighbor);
      bool marked = neighbor->_marked_to_me;
      if (from_me) {
	marked = neighbor->_marked_from_me;
      }

      if (marked) {
	continue;
      }
      
      IPPair pair = IPPair(neighbor->_ip, current_min_ip);
      if (from_me) {
	pair = IPPair(current_min_ip, neighbor->_ip);
      }
      LinkInfo *lnfo = _links.findp(pair);
      if (!lnfo || !lnfo->_metric) {
	continue;
      }
      uint32_t neighbor_metric = neighbor->_metric_to_me;
      uint32_t current_metric = current_min->_metric_to_me;
      
      if (from_me) {
	neighbor_metric = neighbor->_metric_from_me;
	current_metric = current_min->_metric_from_me;
      }
      
      
      uint32_t adjusted_metric = current_metric + lnfo->_metric;
      if (!neighbor_metric || 
	  adjusted_metric < neighbor_metric) {
	if (from_me) {
	  neighbor->_metric_from_me = adjusted_metric;
	  neighbor->_prev_from_me = current_min_ip;
	} else {
	  neighbor->_metric_to_me = adjusted_metric;
	  neighbor->_prev_to_me = current_min_ip;
	}
	
      }
    }

    current_min_ip = IPAddress();
    uint32_t  min_metric = ~0;
    for (IPMap::const_iterator i = ip_addrs.begin(); i; i++) {
      HostInfo *nfo = _hosts.findp(i.key());
      uint32_t metric = nfo->_metric_to_me;
      bool marked = nfo->_marked_to_me;
      if (from_me) {
	metric = nfo->_metric_from_me;
	marked = nfo->_marked_from_me;
      }      
      if (!marked && metric && 
	  metric < min_metric) {
        current_min_ip = nfo->_ip;
        min_metric = metric;
      }
    }
    
    
  }
  
  click_gettimeofday(&finish);
  timersub(&finish, &start, &dijkstra_time);
  //StringAccum sa;
  //sa << "dijstra took " << finish - start;
  //click_chatter("%s: %s\n", id().cc(), sa.take_string().cc());
}


enum {H_BLACKLIST, 
      H_BLACKLIST_CLEAR, 
      H_BLACKLIST_ADD, 
      H_BLACKLIST_REMOVE,
      H_LINKS,
      H_ROUTES_FROM,
      H_ROUTES_TO,
      H_HOSTS,
      H_CLEAR,
      H_DIJKSTRA,
      H_DIJKSTRA_TIME};

static String 
LinkTable_read_param(Element *e, void *thunk)
{
  LinkTable *td = (LinkTable *)e;
    switch ((uintptr_t) thunk) {
    case H_BLACKLIST: {
      StringAccum sa;
      typedef HashMap<IPAddress, IPAddress> IPTable;
      typedef IPTable::const_iterator IPIter;
  

      for (IPIter iter = td->_blacklist.begin(); iter; iter++) {
	sa << iter.value() << " ";
      }
      return sa.take_string() + "\n";
    }
    case H_LINKS:  return td->print_links();
    case H_ROUTES_TO: return td->print_routes(false);
    case H_ROUTES_FROM: return td->print_routes(true);
    case H_HOSTS:  return td->print_hosts();
    case H_DIJKSTRA_TIME: {
      StringAccum sa;
      sa << td->dijkstra_time << "\n";
      return sa.take_string();
    }
    default:
      return String();
    }
}
static int 
LinkTable_write_param(const String &in_s, Element *e, void *vparam,
		      ErrorHandler *errh)
{
  LinkTable *f = (LinkTable *)e;
  String s = cp_uncomment(in_s);
  switch((int)vparam) {
  case H_BLACKLIST_CLEAR: {
    f->_blacklist.clear();
    break;
  }
  case H_BLACKLIST_ADD: {
    IPAddress m;
    if (!cp_ip_address(s, &m)) 
      return errh->error("blacklist_add parameter must be ipaddress");
    f->_blacklist.insert(m, m);
    break;
  }
  case H_BLACKLIST_REMOVE: {
    IPAddress m;
    if (!cp_ip_address(s, &m)) 
      return errh->error("blacklist_add parameter must be ipaddress");
    f->_blacklist.remove(m);
    break;
  }
  case H_CLEAR: f->clear(); break;
  case H_DIJKSTRA: f->dijkstra(true); f->dijkstra(false); break;
  }
  return 0;
}


void
LinkTable::add_handlers() {
  add_default_handlers(false);
  add_read_handler("routes", LinkTable_read_param, (void *)H_ROUTES_FROM);
  add_read_handler("routes_from", LinkTable_read_param, (void *)H_ROUTES_FROM);
  add_read_handler("routes_to", LinkTable_read_param, (void *)H_ROUTES_TO);
  add_read_handler("links", LinkTable_read_param, (void *)H_LINKS);
  add_read_handler("hosts", LinkTable_read_param, (void *)H_HOSTS);
  add_read_handler("blacklist", LinkTable_read_param, (void *)H_BLACKLIST);
  add_read_handler("dijkstra_time", LinkTable_read_param, (void *)H_DIJKSTRA_TIME);

  add_write_handler("clear", LinkTable_write_param, (void *)H_CLEAR);
  add_write_handler("blacklist_clear", LinkTable_write_param, (void *)H_BLACKLIST_CLEAR);
  add_write_handler("blacklist_add", LinkTable_write_param, (void *)H_BLACKLIST_ADD);
  add_write_handler("blacklist_remove", LinkTable_write_param, (void *)H_BLACKLIST_REMOVE);
  add_write_handler("dijkstra", LinkTable_write_param, (void *)H_DIJKSTRA);


  add_write_handler("update_link", static_update_link, 0);


}



#include <click/bighashmap.cc>
#include <click/hashmap.cc>
#include <click/vector.cc>
#if EXPLICIT_TEMPLATE_INSTANCES
template class HashMap<IPAddress, IPAddress>;
template class HashMap<IPPair, LinkTable::LinkInfo>;
template class HashMap<IPAddress, LinkTable::HostInfo>;
#endif
EXPORT_ELEMENT(LinkTable)
CLICK_ENDDECLS