linktable.cc

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

    }
  }


  if (from_me) {
	  Vector<IPAddress> route;
	  /* 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
LinkTable::print_links()
{
  StringAccum sa;
  for (LTIter iter = _links.begin(); iter.live(); iter++) {
    LinkInfo n = iter.value();
    sa << n._from.unparse() << " " << n._to.unparse();
    sa << " " << n._metric;
    sa << " " << n._seq << " " << n.age() << "\n";
  }
  return sa.take_string();
}

static int ipaddr_sorter(const void *va, const void *vb, void *) {
    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, bool pretty)
{
  StringAccum sa;

  Vector<IPAddress> ip_addrs;

  for (HTIter iter = _hosts.begin(); iter.live(); 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)) {
	    if (pretty) {
		    sa << route_to_string(r) << "\n";
	    } else {
		    sa << r[r.size()-1] << "  ";
		    for (int a = 0; a < r.size(); a++) {
			    sa << r[a];
			    if (a < r.size() - 1) {
				    sa << " " << get_link_metric(r[a],r[a+1]);
				    sa << " (" << get_link_seq(r[a],r[a+1])
				       << "," << get_link_age(r[a],r[a+1])
				       << ") ";
			    }
		    }
		    sa << "\n";
	    }
    }
  }
  return sa.take_string();
}


String
LinkTable::print_hosts()
{
  StringAccum sa;
  Vector<IPAddress> ip_addrs;

  for (HTIter iter = _hosts.begin(); iter.live(); 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.live(); iter++) {
    LinkInfo nfo = iter.value();
    if ((unsigned) _stale_timeout.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.unparse().c_str(),
		      nfo._to.unparse().c_str(),
		      nfo._metric,
		      nfo._seq,
		      nfo.age());
      }
    }
  }
  _links.clear();

  for (LTIter iter = links.begin(); iter.live(); 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.live(); iter++) {
    ip_addrs.insert(iter.value()._ip, true);
  }

  for (IPMap::const_iterator i = ip_addrs.begin(); i.live(); 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)
{
  Timestamp start = Timestamp::now();
  IPAddress src = _ip;

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

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

  for (IPMap::const_iterator i = ip_addrs.begin(); i.live(); 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.live(); 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.live(); 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;
      }
    }


  }

  dijkstra_time = Timestamp::now() - start;
  //StringAccum sa;
  //sa << "dijstra took " << finish - start;
  //click_chatter("%s: %s\n", name().c_str(), sa.take_string().c_str());
}


enum {H_BLACKLIST,
      H_BLACKLIST_CLEAR,
      H_BLACKLIST_ADD,
      H_BLACKLIST_REMOVE,
      H_LINKS,
      H_ROUTES_OLD,
      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.live(); 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, true);
    case H_ROUTES_FROM: return td->print_routes(true, true);
    case H_ROUTES_OLD: return td->print_routes(true, false);
    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((intptr_t)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.erase(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_read_handler("routes", LinkTable_read_param, (void *)H_ROUTES_FROM);
  add_read_handler("routes_old", LinkTable_read_param, (void *)H_ROUTES_OLD);
  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);


}

EXPORT_ELEMENT(LinkTable)
CLICK_ENDDECLS