/*
* gridroutetable.{cc,hh} -- Grid local neighbor and route tables element
* Douglas S. J. De Couto
*
* Copyright (c) 2000 Massachusetts Institute of Technology
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, subject to the conditions
* listed in the Click LICENSE file. These conditions include: you must
* preserve this copyright notice, and you cannot mention the copyright
* holders in advertising related to the Software without their permission.
* The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
* notice is a summary of the Click LICENSE file; the license in that file is
* legally binding.
*/
#include <click/config.h>
#include "timeutils.hh" /* includes <cmath> which may #undef NULL, so
must become before <cstddef> */
#include <click/confparse.hh>
#include <click/error.hh>
#include <clicknet/ether.h>
#include <clicknet/ip.h>
#include <click/standard/scheduleinfo.hh>
#include <click/router.hh>
#include <click/element.hh>
#include <click/glue.hh>
#include "gridroutetable.hh"
#include "gridlogger.hh"
CLICK_DECLS
#define NEXT_HOP_ETH_FIXUP 0
bool
GridRouteTable::get_one_entry(const IPAddress &dest_ip, RouteEntry &entry)
{
RTEntry *r = _rtes.findp(dest_ip);
if (r == 0)
return false;
entry = RouteEntry(dest_ip, r->loc_good, r->loc_err, r->loc,
r->next_hop_eth, r->next_hop_ip,
0, // ignore interface number info
r->seq_no(), r->num_hops());
return true;
}
void
GridRouteTable::get_all_entries(Vector<RouteEntry> &vec)
{
for (RTIter iter = _rtes.begin(); iter; iter++) {
const RTEntry &rte = iter.value();
vec.push_back(RouteEntry(rte.dest_ip, rte.loc_good, rte.loc_err, rte.loc,
rte.next_hop_eth, rte.next_hop_ip, 0, // ignore interface info
rte.seq_no(), rte.num_hops()));
}
}
GridRouteTable::GridRouteTable() :
_log(0), _dump_tick(0),
_seq_no(0), _fake_seq_no(0), _bcast_count(0),
_seq_delay(1),
_max_hops(3),
_expire_timer(expire_hook, this),
_hello_timer(hello_hook, this),
_metric_type(MetricEstTxCount),
_max_metric(0), _min_metric(0),
_est_type(EstBySigQual),
_frozen(false)
{
}
GridRouteTable::~GridRouteTable()
{
}
void *
GridRouteTable::cast(const char *n)
{
if (strcmp(n, "GridRouteTable") == 0)
return (GridRouteTable *) this;
else if (strcmp(n, "GridGenericRouteTable") == 0)
return (GridGenericRouteTable *) this;
else
return 0;
}
void
GridRouteTable::log_route_table ()
{
char str[80];
for (RTIter i = _rtes.begin(); i; i++) {
const RTEntry &f = i.value();
snprintf(str, sizeof(str),
"%s %s %s %d %c %u\n",
f.dest_ip.s().c_str(),
f.loc.s().c_str(),
f.next_hop_ip.s().c_str(),
f.num_hops(),
(f.is_gateway ? 'y' : 'n'),
f.seq_no());
_extended_logging_errh->message(str);
}
_extended_logging_errh->message("\n");
}
int
GridRouteTable::configure(Vector<String> &conf, ErrorHandler *errh)
{
String chan("routelog");
String metric("est_tx_count");
int res = cp_va_parse(conf, this, errh,
cpInteger, "entry timeout (msec)", &_timeout,
cpInteger, "route broadcast period (msec)", &_period,
cpInteger, "route broadcast jitter (msec)", &_jitter,
cpEthernetAddress, "source Ethernet address", &_eth,
cpIPAddress, "source IP address", &_ip,
cpElement, "GridGatewayInfo element", &_gw_info,
cpElement, "LinkTracker element", &_link_tracker,
cpElement, "LinkStat element", &_link_stat,
cpKeywords,
"MAX_HOPS", cpInteger, "max hops", &_max_hops,
"LOGCHANNEL", cpString, "log channel name", &chan,
"METRIC", cpString, "route metric", &metric,
"LOG", cpElement, "GridLogger element", &_log,
cpEnd);
if (res < 0)
return res;
// convert msecs to jiffies
if (_timeout == 0)
_timeout = -1;
if (_timeout > 0) {
_timeout_jiffies = msec_to_jiff(_timeout);
if (_timeout_jiffies < 1)
return errh->error("timeout interval is too small");
}
else
click_chatter("%s: not timing out table entries", name().c_str());
if (_period <= 0)
return errh->error("period must be greater than 0");
if (_jitter < 0)
return errh->error("period must be positive");
if (_jitter > _period)
return errh->error("jitter is bigger than period");
if (_max_hops < 0)
return errh->error("max hops must be greater than 0");
_extended_logging_errh = router()->chatter_channel(chan);
assert(_extended_logging_errh);
_metric_type = check_metric_type(metric);
if (_metric_type < 0)
return errh->error("Unknown metric type ``%s''", metric.c_str());
return res;
}
int
GridRouteTable::initialize(ErrorHandler *)
{
_hello_timer.initialize(this);
_hello_timer.schedule_after_msec(_period); // Send periodically
_expire_timer.initialize(this);
if (_timeout > 0)
_expire_timer.schedule_after_msec(EXPIRE_TIMER_PERIOD);
return 0;
}
bool
GridRouteTable::current_gateway(RouteEntry &entry)
{
for (RTIter i = _rtes.begin(); i; i++) {
const RTEntry &f = i.value();
if (f.is_gateway) {
entry = RouteEntry(f.dest_ip, f.loc_good, f.loc_err, f.loc,
f.next_hop_eth, f.next_hop_ip, 0, // ignore interface info
f.seq_no(), f.num_hops());
return true;
}
}
return false;
}
unsigned int
GridRouteTable::qual_to_pct(int q)
{
/* smaller quality is better, so should be a higher pct when closer to min quality */
if (q > _max_metric)
return 0;
else if (q < _min_metric)
return 100;
int delta = _max_metric - _min_metric;
return (100 * (_max_metric - q)) / delta;
}
unsigned int
GridRouteTable::sig_to_pct(int s)
{
/* large signal is better, so should be a higher pct when closer to max sig */
if (s > _max_metric)
return 100;
else if (s < _min_metric)
return 0;
int delta = _max_metric - _min_metric;
return (100 * (s - _min_metric)) / delta;
}
// #define h(x) click_chatter("XXXX %d", x);
#define h(x)
bool
GridRouteTable::est_forward_delivery_rate(const IPAddress ip, double &rate)
{
switch (_est_type) {
case EstBySig:
case EstByQual:
case EstBySigQual: {
int sig = 0;
int qual = 0;
struct timeval last;
bool res = _link_tracker->get_stat(ip, sig, qual, last);
if (!res) {
h(1);
return false;
}
if (_est_type == EstByQual) {
return false;
}
else if (_est_type == EstBySig) {
return false;
}
else if (_est_type == EstBySigQual) {
h(2);
#if 0
click_chatter("XXX %s", ip.s().c_str());
#endif
/*
* use jinyang's parameters, based on 1sec broadcast loss rates
* with 50-byte UDP packets.
*
* good = delivery rate > 80%.
*
* these parameters are chosen to correctly classify 85% of good
* links as good, while only classifying 2% of bad links as
* good.
*/
res = _link_tracker->get_bcast_stat(ip, rate, last);
double z = 9.4519 + 0.0391 * sig + 0.5518 * qual;
double z2 = 1 / (1 + exp(z));
double thresh = 0.8;
bool link_good = z2 > thresh;
/* paper fuckedness: */
if (link_good)
rate = 1;
else
rate = 0.1;
return true;
h(3);
if (!link_good && !res) {
h(4);
return false;
}
else if (link_good && !res) {
h(5);
rate = 0.8;
return true;
}
else if (!link_good && res) {
h(6);
return true; /* rate was set in call to get_bcast_stat */
}
else /* link_good && res */ {
h(7);
if (rate < 0.8) {
h(8);
rate = 0.8;
}
return true;
}
h(9);
}
else {
h(10);
return false;
}
}
case EstByMeas: {
h(11);
struct timeval last;
bool res = _link_tracker->get_bcast_stat(ip, rate, last);
return res;
break;
}
default:
h(12);
return false;
}
}
bool
GridRouteTable::est_reverse_delivery_rate(const IPAddress ip, double &rate)
{
switch (_est_type) {
case EstBySig:
case EstByQual:
h(101);
return false;
break;
case EstBySigQual: {
h(102);
RTEntry *r = _rtes.findp(ip);
if (r == 0 || r->num_hops() > 1) {
h(103);
return false;
}
#if 0
struct timeval last;
#if 0
LinkStat::stat_t *s = _link_stat->_stats.findp(r->next_hop_eth);
#else
struct {
int qual;
int sig;
struct timeval when;
} *s = 0;
#endif
if (s == 0) {
return false;
h(104);
}
double z = 9.4519 + 0.0391 * s->sig + 0.5518 * s->qual;
double z2 = 1 / (1 + exp(z));
double thresh = 0.8;
bool link_good = z2 > thresh;
/* paper fuckedness: */
if (link_good)
rate = 1;
else
rate = 0.1;
return true;
unsigned int window = 0;
unsigned int num_rx = 0;
unsigned int num_expected = 0;
bool res = false;_link_stat->get_bcast_stats(r->next_hop_eth, last, window, num_rx, num_expected);
if (res && num_expected > 1) {
h(105);
double num_rx_ = num_rx;
/* we assume all nodes have same hello period */
double num_expected_ = num_expected;
rate = (num_rx_ - 0.5) / num_expected_;
}
else {
h(107);
rate = 0;
}
if (!link_good && !res) {
h(108);
return false;
}
else if (link_good && !res) {
h(109);
rate = 0.8;
return true;
}
else if (!link_good && res) {
h(110);
return true; /* rate was set in call to get_bcast_stats */
}
else /* link_good && res */ {
h(111);
if (rate < 0.8) {
h(112);
rate = 0.8;
}
return true;
}
#else
rate = 0;
return false;
#endif
}
h(113);
case EstByMeas: {
#if 0
struct timeval last;
RTEntry *r = _rtes.findp(ip);
if (r == 0 || r->num_hops() > 1)
return false;
unsigned int window = 0;
unsigned int num_rx = 0;
unsigned int num_expected = 0;
bool res = _link_stat->get_bcast_stats(r->next_hop_eth, last, window, num_rx, num_expected);
if (!res || num_expected <= 1)
return false;
double num_rx_ = num_rx;
double num_expected_ = num_expected;
if (num_rx > num_expected)
click_chatter("WARNING: est_reverse_delivery_rate: num_rx (%d) > num_expected (%d) for %s",
num_rx, num_expected, r->next_hop_eth.s().c_str());
rate = (num_rx_ - 0.5) / num_expected_;
#endif
return true;
break;
}
default:
return false;
}
}
void
GridRouteTable::init_metric(RTEntry &r)
{
assert(r.num_hops() == 1);
switch (_metric_type) {
case MetricHopCount:
r.metric = r.num_hops();
r.metric_valid = true;
break;
case MetricMinDeliveryRate:
case MetricCumulativeDeliveryRate:
assert(0);
/* code to estimate our delivery rate to this 1-hop nbr goes here */
r.metric_valid = true;
break;
case MetricMinSigStrength:
case MetricMinSigQuality:
case MetricCumulativeQualPct:
case MetricCumulativeSigPct: {
int sig = 0;
int qual = 0;
struct timeval last;
bool res = _link_tracker->get_stat(r.dest_ip, sig, qual, last);
if (!res) {
click_chatter("GridRouteTable: no link sig/qual stats from 1-hop neighbor %s; not initializing metric\n",
r.dest_ip.s().c_str());
r.metric = _bad_metric;
r.metric_valid = false;
return;
}
struct timeval now;
gettimeofday(&now, 0);
now = now - last;
int delta_ms = 1000 * now.tv_sec + (now.tv_usec / 1000);
if (delta_ms > _timeout) {
click_chatter("GridRouteTable: link sig/qual stats from 1-hop neighbor %s are too old; not initializing metric\n",
r.dest_ip.s().c_str());
r.metric = _bad_metric;
r.metric_valid = false;
return;
}
if (_metric_type == MetricMinSigQuality)
r.metric = (unsigned int) qual;
else if (_metric_type == MetricMinSigStrength)
r.metric = (unsigned int) -sig; // deal in -dBm
else if (_metric_type == MetricCumulativeQualPct)
r.metric = qual_to_pct(qual);
else // _metric_type == MetricCumulativeSigPct
r.metric = sig_to_pct(sig);
r.metric_valid = true;
}
break;
case MetricEstTxCount: {
#if 0
click_chatter("XXX");
#endif
double fwd_rate = 0;
double rev_rate = 0;
bool res = est_forward_delivery_rate(r.next_hop_ip, fwd_rate);
bool res2 = est_reverse_delivery_rate(r.next_hop_ip, rev_rate);
#if 0
char buf[255];
snprintf(buf, 255, "YYY %s %s -- res: %s, res2: %s, fwd: %f, rev: %f",
r.dest_ip.s().c_str(), r.next_hop_ip.s().c_str(),
res ? "true" : "false", res2 ? "true" : "false",
fwd_rate, rev_rate);
click_chatter(buf);
#endif
if (res && res2 && fwd_rate > 0 && rev_rate > 0) {
if (fwd_rate >= 1) {
click_chatter("init_metric ERROR: fwd rate %d is too high for %s",
(int) (100 * fwd_rate), r.next_hop_ip.s().c_str());
fwd_rate = 1;
}
if (rev_rate >= 1) {
click_chatter("init_metric ERROR: rev rate %d is too high for %s",
(int) (100 * rev_rate), r.next_hop_ip.s().c_str());
rev_rate = 1;
}
r.metric = (int) (100 / (fwd_rate * rev_rate));
if (r.metric < 100)
click_chatter("init_metric WARNING: metric too small (%d) for %s",
r.metric, r.next_hop_ip.s().c_str());
r.metric_valid = true;
h(201);
}
else {
r.metric = _bad_metric;
r.metric_valid = false;
h(202);
}
break;
}
default:
assert(0);
}
}
void
GridRouteTable::update_metric(RTEntry &r)
{
if (r.num_hops() == 0)
return; // is broken route ad
RTEntry *next_hop = _rtes.findp(r.next_hop_ip);
if (!next_hop) {
click_chatter("GridRouteTable: ERROR updating metric for %s; no information for next hop %s; invalidating metric",
r.dest_ip.s().c_str(), r.next_hop_ip.s().c_str());
r.metric_valid = false;
return;
}
if (!r.metric_valid)
return;
if (!next_hop->metric_valid) {
r.metric_valid = false;
return;
}
switch (_metric_type) {
case MetricHopCount:
if (next_hop->metric > 1)
click_chatter("GridRouteTable: WARNING metric type is hop count but next-hop %s metric is > 1 (%u)",
next_hop->dest_ip.s().c_str(), next_hop->metric);
case MetricEstTxCount:
if (_metric_type == MetricEstTxCount) {
if (r.metric < (unsigned) 100 * (r.num_hops() - 1))
click_chatter("update_metric WARNING received metric (%d) too low for %s (%d hops)",
r.metric, r.dest_ip.s().c_str(), r.num_hops());
if (next_hop->metric < 100)
click_chatter("update_metric WARNING next hop %s for %s metric is too low (%d)",
next_hop->dest_ip.s().c_str(), r.dest_ip.s().c_str(), next_hop->metric);
}
r.metric += next_hop->metric;
break;
case MetricCumulativeDeliveryRate:
case MetricCumulativeQualPct:
case MetricCumulativeSigPct:
r.metric = (r.metric * next_hop->metric) / 100;
break;
case MetricMinDeliveryRate:
r.metric = (next_hop->metric < r.metric) ? next_hop->metric : r.metric;
break;
case MetricMinSigStrength:
case MetricMinSigQuality:
// choose weakest signal, which is largest -dBm
// *or* choose worst quality, which is smaller numbers
r.metric = (next_hop->metric > r.metric) ? next_hop->metric : r.metric;
break;
default:
assert(0);
}
r.metric_valid = true;
}
bool
GridRouteTable::metric_is_preferable(const RTEntry &r1, const RTEntry &r2)
{
assert(r1.metric_valid && r2.metric_valid);
switch (_metric_type) {
case MetricHopCount:
case MetricEstTxCount:
return r1.metric < r2.metric;
case MetricCumulativeDeliveryRate:
case MetricMinDeliveryRate:
return r1.metric > r2.metric;
case MetricMinSigQuality:
case MetricMinSigStrength:
// smaller -dBm is stronger signal
// *or* prefer smaller quality number
return r1.metric < r2.metric;
case MetricCumulativeQualPct:
case MetricCumulativeSigPct:
default:
assert(0);
}
return false;
}
bool
GridRouteTable::should_replace_old_route(const RTEntry &old_route, const RTEntry &new_route)
{
/* prefer a strictly newer route */
if (old_route.seq_no() > new_route.seq_no())
return false;
if (old_route.seq_no() < new_route.seq_no())
return true;
/*
* routes have same seqno, choose based on metric
*/
/* prefer a route with a valid metric */
if (old_route.metric_valid && !new_route.metric_valid)
return false;
if (!old_route.metric_valid && new_route.metric_valid)
return true;
/* if neither metric is valid, just keep the route we have -- to aid
* in stability -- as if I have any notion about that....
*
* actually, that's fucked. would you prefer a 5-hop route or a
* 2-hop route, given that you don't have any other information about
* them? duh. fall back to hopcount.
* bwahhhaaaahahaha!!! */
if (!old_route.metric_valid && !new_route.metric_valid) {
// return false;
return new_route.num_hops() < old_route.num_hops();
}
// both metrics are valid
/* update is from same node as last update, we should accept it to avoid unwarranted timeout */
if (old_route.next_hop_ip == new_route.next_hop_ip)
return true;
/* update route if the metric is better */
return metric_is_preferable(new_route, old_route);
}
/*
* expects grid LR packets, with ethernet and grid hdrs
*/
Packet *
GridRouteTable::simple_action(Packet *packet)
{
assert(packet);
unsigned int jiff = click_jiffies();
/*
* sanity check the packet, get pointers to headers
*/
click_ether *eh = (click_ether *) packet->data();
if (ntohs(eh->ether_type) != ETHERTYPE_GRID) {
click_chatter("GridRouteTable %s: got non-Grid packet type", name().c_str());
packet->kill();
return 0;
}
grid_hdr *gh = (grid_hdr *) (eh + 1);
if (gh->type != grid_hdr::GRID_LR_HELLO) {
click_chatter("GridRouteTable %s: received unknown Grid packet; ignoring it", name().c_str());
packet->kill();
return 0;
}
IPAddress ipaddr((unsigned char *) &gh->tx_ip);
EtherAddress ethaddr((unsigned char *) eh->ether_shost);
// this should be redundant (see HostEtherFilter in grid.click)
if (ethaddr == _eth) {
click_chatter("GridRouteTable %s: received own Grid packet; ignoring it", name().c_str());
packet->kill();
return 0;
}
grid_hello *hlo = (grid_hello *) (gh + 1);
// extended logging
Timestamp ts = Timestamp::now();
_extended_logging_errh->message("recvd %u from %s %d %d", ntohl(hlo->seq_no), ipaddr.s().c_str(), ts.sec(), ts.usec());
if (_log)
_log->log_start_recv_advertisement(ntohl(hlo->seq_no), ipaddr, ts);
if (_frozen) {
if (_log)
_log->log_end_recv_advertisement();
packet->kill();
return 0;
}
/*
* add 1-hop route to packet's transmitter; perform some sanity
* checking if entry already existed
*/
RTEntry *r = _rtes.findp(ipaddr);
if (!r)
click_chatter("GridRouteTable %s: adding new 1-hop route %s -- %s",
name().c_str(), ipaddr.s().c_str(), ethaddr.s().c_str());
else if (r->num_hops() == 1 && r->next_hop_eth != ethaddr)
click_chatter("GridRouteTable %s: ethernet address of %s changed from %s to %s",
name().c_str(), ipaddr.s().c_str(), r->next_hop_eth.s().c_str(), ethaddr.s().c_str());
/*
* well, for now we'll just do the ping-pong on route ads. ideally
* we would piggyback the ping-pong data for a destination on any
* unicast packet to that destination, using the latest info from
* that destination. we sould still do the ping-ponging in route
* ads as well, in case we aren't sending data to that destination.
* this would probably entail adding two elements: one to fill in
* outgoing packets with the right stats, and another to pick up the
* stats from incoming packets. there would probably be a third
* element which is a table to hold these stats and take care of the
* averaging. this could be the same as either the first or second
* element, and should have a hook so that the routing table (*this*
* element) can add information gleaned from the route ads. one
* drag is that we can't properly do the averaging -- each new
* reading comes at a different time, not neccessarily evenly
* spaced. we should use some time-weighted average, instead of the
* usual sample-based average. the node measuring at the other end
* of the link needs to timestamp when packet come in and it takes
* the readings.
*/
/*
* individual link metric smoothing, or route metric smoothing? we
* will only smooth the ping-pong measurements on individual links;
* we won't smooth metrics at the route level. that's because we
* can't even be sure that as the metrics change for a route to some
* destination, the metric are even for the same route, i.e. same
* set of links.
*/
int entry_sz = hlo->nbr_entry_sz;
char *entry_ptr = (char *) (hlo + 1);
/* look for ping-pong link stats about us */
#ifndef SMALL_GRID_HEADERS
for (int i = 0; i < hlo->num_nbrs; i++, entry_ptr += entry_sz) {
grid_nbr_entry *curr = (grid_nbr_entry *) entry_ptr;
if (_ip == curr->ip && curr->num_hops == 1) {
struct timeval tv;
tv = ntoh(curr->measurement_time);
_link_tracker->add_stat(ipaddr, ntohl(curr->link_sig), ntohl(curr->link_qual), tv);
tv = ntoh(curr->last_bcast);
_link_tracker->add_bcast_stat(ipaddr, curr->num_rx, curr->num_expected, tv);
break;
}
}
#endif
if (ntohl(hlo->ttl) > 0) {
RTEntry new_r(ipaddr, ethaddr, gh, hlo, jiff);
init_metric(new_r);
if (r == 0 || should_replace_old_route(*r, new_r)) {
if (_log)
_log->log_added_route(GridLogger::WAS_SENDER, make_generic_rte(new_r));
_rtes.insert(ipaddr, new_r);
if (new_r.num_hops() > 1 && r && r->num_hops() == 1) {
/* clear old 1-hop stats */
_link_tracker->remove_all_stats(r->dest_ip);
}
}
if (r)
r->dest_eth = ethaddr;
}
/*
* loop through and process other route entries in hello message
*/
Vector<RTEntry> triggered_rtes;
Vector<IPAddress> broken_dests;
entry_ptr = (char *) (hlo + 1);
for (int i = 0; i < hlo->num_nbrs; i++, entry_ptr += entry_sz) {
grid_nbr_entry *curr = (grid_nbr_entry *) entry_ptr;
RTEntry route(ipaddr, ethaddr, curr, jiff);
/* ignore route if ttl has run out */
if (route.ttl <= 0)
continue;
/* ignore route to ourself */
if (route.dest_ip == _ip)
continue;
/* pseudo-split-horizon: ignore routes from nbrs that go back
through us */
if (curr->next_hop_ip == (unsigned int) _ip)
continue;
update_metric(route);
RTEntry *our_rte = _rtes.findp(curr->ip);
/*
* broken route advertisement
*/
if (curr->num_hops == 0) {
if ((route.seq_no() & 1) == 0) {
// broken routes should have odd seq_no
click_chatter("ignoring invalid broken route entry from %s for %s: num_hops was 0 but seq_no was even\n",
ipaddr.s().c_str(), route.dest_ip.s().c_str());
continue;
}
/* if we don't have a route to this destination, ignore it */
if (!our_rte)
continue;
/*
* if our next hop to the destination is this packet's sender,
* AND if the seq_no is newer than any information we have.
* remove the broken route.
*/
if (our_rte->next_hop_ip == ipaddr &&
route.seq_no() > our_rte->seq_no()) {
broken_dests.push_back(route.dest_ip);
/* generate triggered broken route advertisement */
triggered_rtes.push_back(route);
if (_log)
_log->log_expired_route(GridLogger::BROKEN_AD, route.dest_ip);
}
/*
* otherwise, triggered advertisement: if we have a good route
* to the destination with a newer seq_no, advertise our new
* information.
*/
else if (route.seq_no() < our_rte->seq_no()) {
assert(!(our_rte->seq_no() & 1)); // valid routes have even seq_no
if (our_rte->ttl > 0 && our_rte->metric_valid) {
triggered_rtes.push_back(*our_rte);
if (_log)
_log->log_triggered_route(our_rte->dest_ip);
}
}
continue;
}
/* skip routes with too many hops */
// this would change if using proxies
if (route.num_hops() + 1 > _max_hops)
continue;
/*
* regular route entry -- should we stick it in the table?
*/
if (our_rte == 0 || should_replace_old_route(*our_rte, route)) {
_rtes.insert(route.dest_ip, route);
if (route.num_hops() > 1 && our_rte && our_rte->num_hops() == 1) {
/* clear old 1-hop stats */
_link_tracker->remove_all_stats(our_rte->dest_ip);
#if NEXT_HOP_ETH_FIXUP
/* fix up route entries for which this dest had been the next hop */
Vector<RTEntry> changed_next_hop;
for (RTIter i = _rtes.begin(); i; i++) {
if (i.value().next_hop_ip == route.dest_ip) {
RTEntry r = i.value();
/* some skoochy stuff here, this will make it very hard to keep track of things... */
r.next_hop_ip = route.next_hop_ip;
r.next_hop_eth = route.next_hop_eth;
// XXX how to calculate num_hops???, metric, etc.
// XXX also, last_updated_jiffies, etc.
}
}
for (int i = 0; i < changed_next_hop.size(); i++)
_rtes.insert(changed_next_hop[i].dest_ip, changed_next_hop[i]);
#endif
}
if (_log)
_log->log_added_route(GridLogger::WAS_ENTRY, make_generic_rte(route));
}
}
/* delete broken routes */
for (int i = 0; i < broken_dests.size(); i++) {
bool removed = _rtes.remove(broken_dests[i]);
assert(removed);
}
log_route_table(); // extended logging
if (_log)
_log->log_end_recv_advertisement();
/* send triggered updates */
if (triggered_rtes.size() > 0)
send_routing_update(triggered_rtes, false); // XXX should seq_no get incremented for triggered routes -- probably?
packet->kill();
return 0;
}
String
GridRouteTable::print_rtes_v(Element *e, void *)
{
GridRouteTable *n = (GridRouteTable *) e;
String s;
for (RTIter i = n->_rtes.begin(); i; i++) {
const RTEntry &f = i.value();
s += f.dest_ip.s()
+ " next=" + f.next_hop_ip.s()
+ " hops=" + String((int) f.num_hops())
+ " gw=" + (f.is_gateway ? "y" : "n")
+ " loc=" + f.loc.s()
+ " err=" + (f.loc_good ? "" : "-") + String(f.loc_err) // negate loc if invalid
+ " seq=" + String(f.seq_no())
+ " metric_valid=" + (f.metric_valid ? "yes" : "no")
+ " metric=" + String(f.metric)
+ "\n";
}
return s;
}
String
GridRouteTable::print_rtes(Element *e, void *)
{
GridRouteTable *n = (GridRouteTable *) e;
String s;
for (RTIter i = n->_rtes.begin(); i; i++) {
const RTEntry &f = i.value();
s += f.dest_ip.s()
+ " next=" + f.next_hop_ip.s()
+ " hops=" + String((int) f.num_hops())
+ " gw=" + (f.is_gateway ? "y" : "n")
// + " loc=" + f.loc.s()
// + " err=" + (f.loc_good ? "" : "-") + String(f.loc_err) // negate loc if invalid
+ " seq=" + String(f.seq_no())
+ "\n";
}
return s;
}
String
GridRouteTable::print_nbrs_v(Element *e, void *)
{
GridRouteTable *n = (GridRouteTable *) e;
String s;
for (RTIter i = n->_rtes.begin(); i; i++) {
/* only print immediate neighbors */
if (i.value().num_hops() != 1)
continue;
s += i.key().s();
s += " eth=" + i.value().next_hop_eth.s();
char buf[300];
snprintf(buf, 300, " metric_valid=%s metric=%d",
i.value().metric_valid ? "yes" : "no", i.value().metric);
s += buf;
s += "\n";
}
return s;
}
String
GridRouteTable::print_nbrs(Element *e, void *)
{
GridRouteTable *n = (GridRouteTable *) e;
String s;
for (RTIter i = n->_rtes.begin(); i; i++) {
/* only print immediate neighbors */
if (i.value().num_hops() != 1)
continue;
s += i.key().s();
s += " eth=" + i.value().next_hop_eth.s();
s += "\n";
}
return s;
}
String
GridRouteTable::print_ip(Element *e, void *)
{
GridRouteTable *n = (GridRouteTable *) e;
return n->_ip.s();
}
String
GridRouteTable::print_eth(Element *e, void *)
{
GridRouteTable *n = (GridRouteTable *) e;
return n->_eth.s();
}
String
GridRouteTable::metric_type_to_string(MetricType t)
{
switch (t) {
case MetricHopCount: return "hopcount"; break;
case MetricCumulativeDeliveryRate: return "cumulative_delivery_rate"; break;
case MetricMinDeliveryRate: return "min_delivery_rate"; break;
case MetricMinSigStrength: return "min_sig_strength"; break;
case MetricMinSigQuality: return "min_sig_quality"; break;
case MetricCumulativeQualPct: return "cumulative_qual_pct"; break;
case MetricCumulativeSigPct: return "cumulative_sig_pct"; break;
case MetricEstTxCount: return "est_tx_count"; break;
default:
return "unknown_metric_type";
}
}
String
GridRouteTable::print_metric_type(Element *e, void *)
{
GridRouteTable *n = (GridRouteTable *) e;
return metric_type_to_string(n->_metric_type) + "\n";
}
GridRouteTable::MetricType
GridRouteTable::check_metric_type(const String &s)
{
String s2 = s.lower();
if (s2 == "hopcount")
return MetricHopCount;
else if (s2 == "cumulative_delivery_rate")
return MetricCumulativeDeliveryRate;
else if (s2 == "min_delivery_rate")
return MetricMinDeliveryRate;
else if (s2 == "min_sig_strength")
return MetricMinSigStrength;
else if (s2 == "min_sig_quality")
return MetricMinSigQuality;
else if (s2 == "cumulative_qual_pct")
return MetricCumulativeQualPct;
else if (s2 == "cumulative_sig_pct")
return MetricCumulativeSigPct;
else if (s2 == "est_tx_count")
return MetricEstTxCount;
else
return MetricUnknown;
}
int
GridRouteTable::write_metric_type(const String &arg, Element *el,
void *, ErrorHandler *errh)
{
GridRouteTable *rt = (GridRouteTable *) el;
MetricType type = check_metric_type(arg);
if (type < 0)
return errh->error("unknown metric type ``%s''", ((String) arg).c_str());
if (type != rt->_metric_type) {
rt->_metric_type = type;
if (type == MetricCumulativeSigPct) {
rt->_max_metric = _max_sig;
rt->_min_metric = _min_sig;
}
else if (type == MetricCumulativeQualPct) {
rt->_max_metric = _max_qual;
rt->_min_metric = _min_qual;
}
else
rt->_max_metric = rt->_min_metric = 0;
/* make sure we don't try to use the old metric for a route */
Vector<RTEntry> entries;
for (RTIter i = rt->_rtes.begin(); i; i++) {
/* skanky, but there's no reason for this to be quick. i guess
the HashMap doesn't let you change its values. */
RTEntry e = i.value();
e.metric_valid = false;
entries.push_back(e);
}
for (int i = 0; i < entries.size(); i++)
rt->_rtes.insert(entries[i].dest_ip, entries[i]);
}
return 0;
}
String
GridRouteTable::print_metric_range(Element *e, void *)
{
GridRouteTable *rt = (GridRouteTable *) e;
return "max=" + String(rt->_max_metric) + " min=" + String(rt->_min_metric) + "\n";
}
int
GridRouteTable::write_metric_range(const String &arg, Element *el,
void *, ErrorHandler *errh)
{
GridRouteTable *rt = (GridRouteTable *) el;
int max, min;
int res = cp_va_space_parse(arg, rt, errh,
cpInteger, "metric range max", &max,
cpInteger, "metric range min", &min,
cpEnd);
if (res < 0)
return -1;
if (max < min) {
int t = max;
max = min;
min = t;
}
rt->_max_metric = max;
rt->_min_metric = min;
return 0;
}
String
GridRouteTable::print_est_type(Element *e, void *)
{
GridRouteTable *rt = (GridRouteTable *) e;
return String(rt->_est_type) + "\n";
}
int
GridRouteTable::write_est_type(const String &arg, Element *el,
void *, ErrorHandler *)
{
GridRouteTable *rt = (GridRouteTable *) el;
rt->_est_type = atoi(((String) arg).c_str());
return 0;
}
String
GridRouteTable::print_seq_delay(Element *e, void *)
{
GridRouteTable *rt = (GridRouteTable *) e;
return String(rt->_seq_delay) + "\n";
}
int
GridRouteTable::write_seq_delay(const String &arg, Element *el,
void *, ErrorHandler *)
{
GridRouteTable *rt = (GridRouteTable *) el;
rt->_seq_delay = atoi(((String) arg).c_str());
return 0;
}
String
GridRouteTable::print_frozen(Element *e, void *)
{
GridRouteTable *rt = (GridRouteTable *) e;
return (rt->_frozen ? "true\n" : "false\n");
}
int
GridRouteTable::write_frozen(const String &arg, Element *el,
void *, ErrorHandler *)
{
GridRouteTable *rt = (GridRouteTable *) el;
rt->_frozen = atoi(((String) arg).c_str());
click_chatter("GridRouteTable: setting _frozen to %s", rt->_frozen ? "true" : "false");
return 0;
}
String
GridRouteTable::print_links(Element *e, void *)
{
GridRouteTable *rt = (GridRouteTable *) e;
String s = "Metric type: " + metric_type_to_string(rt->_metric_type) + "\n";
for (RTIter i = rt->_rtes.begin(); i; i++) {
const RTEntry &r = i.value();
if (r.num_hops() > 1)
continue;
/* get our measurements of the link *from* this neighbor */
#if 0
#if 0
LinkStat::stat_t *s1 = rt->_link_stat->_stats.findp(r.next_hop_eth);
#else
struct {
int qual;
int sig;
struct timeval when;
} *s1 = 0;
#endif
struct timeval last;
unsigned int window = 0;
unsigned int num_rx = 0;
unsigned int num_expected = 0;
bool res1 = rt->_link_stat->get_bcast_stats(r.next_hop_eth, last, window, num_rx, num_expected);
/* get estimates of our link *to* this neighbor */
int tx_sig = 0;
int tx_qual = 0;
bool res2 = rt->_link_tracker->get_stat(r.dest_ip, tx_sig, tx_qual, last);
double bcast_rate = 0;
bool res3 = rt->_link_tracker->get_bcast_stat(r.dest_ip, bcast_rate, last);
char buf[255];
double tx_rate = num_rx;
tx_rate -= 0.5;
tx_rate /= num_expected;
snprintf(buf, 255, "%s %s metric=%u (%s) rx_sig=%d rx_qual=%d rx_rate=%d tx_sig=%d tx_qual=%d tx_rate=%d\n",
r.dest_ip.s().c_str(), r.next_hop_eth.s().c_str(), r.metric, r.metric_valid ? "valid" : "invalid",
s1 ? s1->sig : -1, s1 ? s1->qual : -1, res1 ? ((int) (100 * tx_rate)) : -1,
res2 ? tx_sig : -1, res2 ? tx_qual : -1, res3 ? (int) (100 * bcast_rate) : -1);
s += buf;
#endif
}
return s;
}
void
GridRouteTable::add_handlers()
{
add_read_handler("nbrs_v", print_nbrs_v, 0);
add_read_handler("nbrs", print_nbrs, 0);
add_read_handler("rtes_v", print_rtes_v, 0);
add_read_handler("rtes", print_rtes, 0);
add_read_handler("ip", print_ip, 0);
add_read_handler("eth", print_eth, 0);
add_read_handler("links", print_links, 0);
add_read_handler("metric_type", print_metric_type, 0);
add_write_handler("metric_type", write_metric_type, 0);
add_read_handler("metric_range", print_metric_range, 0);
add_write_handler("metric_range", write_metric_range, 0);
add_read_handler("est_type", print_est_type, 0);
add_write_handler("est_type", write_est_type, 0);
add_read_handler("seq_delay", print_seq_delay, 0);
add_write_handler("seq_delay", write_seq_delay, 0);
add_read_handler("frozen", print_frozen, 0);
add_write_handler("frozen", write_frozen, 0);
}
void
GridRouteTable::expire_hook(Timer *, void *thunk)
{
GridRouteTable *n = (GridRouteTable *) thunk;
n->expire_routes();
n->_expire_timer.schedule_after_msec(EXPIRE_TIMER_PERIOD);
}
Vector<GridRouteTable::RTEntry>
GridRouteTable::expire_routes()
{
/*
* remove expired routes from the routing table. return a vector of
* expired routes which is suitable for inclusion in a broken route
* advertisement.
*/
/* overloading this timer function to occasionally dump full route table to log */
_dump_tick++;
if (_dump_tick == 50) {
_dump_tick = 0;
if (_log) {
Vector<RouteEntry> vec;
get_all_entries(vec);
_log->log_route_dump(vec, Timestamp::now());
}
}
assert(_timeout > 0);
unsigned int jiff = click_jiffies();
Vector<RTEntry> retval;
if (_frozen)
return retval;
typedef HashMap<IPAddress, bool> xip_t; // ``expired ip''
xip_t expired_rtes;
xip_t expired_next_hops;
Timestamp ts = Timestamp::now();
if (_log)
_log->log_start_expire_handler(ts);
bool table_changed = false;
/* 1. loop through RT once, remembering destinations which have been
in our RT too long (last_updated_jiffies too old) or have
exceeded their ttl. Also note those expired 1-hop entries --
they may be someone's next hop. */
for (RTIter i = _rtes.begin(); i; i++) {
if (jiff - i.value().last_updated_jiffies > _timeout_jiffies ||
decr_ttl(i.value().ttl, jiff_to_msec(jiff - i.value().last_updated_jiffies)) == 0) {
expired_rtes.insert(i.value().dest_ip, true);
_extended_logging_errh->message ("expiring %s %d %d", i.value().dest_ip.s().c_str(), ts.sec(), ts.usec()); // extended logging
table_changed = true;
if (_log)
_log->log_expired_route(GridLogger::TIMEOUT, i.value().dest_ip);
if (i.value().num_hops() == 1) {
/* may be another route's next hop */
expired_next_hops.insert(i.value().dest_ip, true);
/* clear link stats */
_link_tracker->remove_all_stats(i.value().dest_ip);
}
}
}
/* 2. Loop through RT a second time, picking up any multi-hop
entries whose next hop is expired, and are not yet expired. */
for (RTIter i = _rtes.begin(); i; i++) {
// don't re-expire 1-hop routes, they are their own next hop
if (i.value().num_hops() > 1 &&
expired_next_hops.findp(i.value().next_hop_ip) &&
!expired_rtes.findp(i.value().dest_ip)) {
expired_rtes.insert(i.value().dest_ip, true);
_extended_logging_errh->message("next to %s expired %d %d", i.value().dest_ip.s().c_str(), ts.sec(), ts.usec()); // extended logging
if (_log)
_log->log_expired_route(GridLogger::NEXT_HOP_EXPIRED, i.value().dest_ip);
}
}
/* 3. Then, push all expired entries onto the return vector and
erase them from the RT. */
for (xip_t::iterator i = expired_rtes.begin(); i; i++) {
RTEntry *r = _rtes.findp(i.key());
assert(r);
r->invalidate();
r->ttl = grid_hello::MAX_TTL_DEFAULT;
retval.push_back(*r);
}
for (xip_t::iterator i = expired_rtes.begin(); i; i++) {
bool removed = _rtes.remove(i.key());
assert(removed);
}
if (table_changed)
log_route_table(); // extended logging
if (_log)
_log->log_end_expire_handler();
return retval;
}
void
GridRouteTable::hello_hook(Timer *, void *thunk)
{
GridRouteTable *n = (GridRouteTable *) thunk;
/* XXX is this a bug? we expire some routes, but don't advertise
them as broken anymore... */
n->expire_routes();
Vector<RTEntry> rte_entries;
for (RTIter i = n->_rtes.begin(); i; i++) {
/* because we called expire_routes() at the top of this function,
* we know we are not propagating any route entries with ttl of 0
* or that have timed out */
/* if (i.value().metric_valid) */
// have to advertise routes even if they have invalid metrics, to
// kick-start the ping-pong link stats exchange
rte_entries.push_back(i.value());
}
// make and send the packet
n->send_routing_update(rte_entries);
int r2 = random();
double r = (double) (r2 >> 1);
int jitter = (int) (((double) n->_jitter) * r / ((double) 0x7FffFFff));
if (r2 & 1)
jitter *= -1;
n->_hello_timer.schedule_after_msec(n->_period + (int) jitter);
}
void
GridRouteTable::send_routing_update(Vector<RTEntry> &rtes_to_send,
bool update_seq, bool check_ttls)
{
/*
* build and send routing update packet advertising the contents of
* the rte_info vector. iff update_seq, increment the sequence
* number before sending. The calling function must fill in each
* nbr entry. If check_ttls, decrement and check ttls before
* building the packet.
*/
if (_frozen)
return;
unsigned int jiff = click_jiffies();
Vector<RTEntry> rte_info = Vector<RTEntry>();
/*
* if requested by caller, calculate the ttls each route entry
* should be sent with. Each entry's ttl must be decremented by a
* minimum amount. Only send the routes with valid ttls (> 0).
*/
for (int i = 0; i < rtes_to_send.size(); i++) {
RTEntry &r = rtes_to_send[i];
if (check_ttls) {
unsigned int age = jiff_to_msec(jiff - r.last_updated_jiffies);
unsigned int new_ttl = decr_ttl(r.ttl, (age > grid_hello::MIN_TTL_DECREMENT ? age : grid_hello::MIN_TTL_DECREMENT));
if (new_ttl > 0) {
r.ttl = new_ttl;
rte_info.push_back(r);
}
} else {
rte_info.push_back(r);
}
}
int hdr_sz = sizeof(click_ether) + sizeof(grid_hdr) + sizeof(grid_hello);
int max_rtes = (1500 - hdr_sz) / sizeof(grid_nbr_entry);
int num_rtes = (max_rtes < rte_info.size() ? max_rtes : rte_info.size()); // min
int psz = hdr_sz + sizeof(grid_nbr_entry) * num_rtes;
assert(psz <= 1500);
if (num_rtes < rte_info.size())
click_chatter("GridRouteTable %s: too many routes, truncating route advertisement",
name().c_str());
/* allocate and align the packet */
WritablePacket *p = Packet::make(psz + 2); // for alignment
if (p == 0) {
click_chatter("in %s: cannot make packet!", name().c_str());
assert(0);
}
ASSERT_ALIGNED(p->data());
p->pull(2);
memset(p->data(), 0, p->length());
/* fill in the timestamp */
p->set_timestamp_anno(Timestamp::now());
/* fill in ethernet header */
click_ether *eh = (click_ether *) p->data();
memset(eh->ether_dhost, 0xff, 6); // broadcast
eh->ether_type = htons(ETHERTYPE_GRID);
memcpy(eh->ether_shost, _eth.data(), 6);
/* fill in the grid header */
grid_hdr *gh = (grid_hdr *) (eh + 1);
ASSERT_ALIGNED(gh);
gh->hdr_len = sizeof(grid_hdr);
gh->total_len = htons(psz - sizeof(click_ether));
gh->type = grid_hdr::GRID_LR_HELLO;
gh->ip = gh->tx_ip = _ip;
grid_hello *hlo = (grid_hello *) (gh + 1);
assert(num_rtes <= 255);
hlo->num_nbrs = (unsigned char) num_rtes;
hlo->nbr_entry_sz = sizeof(grid_nbr_entry);
hlo->seq_no = htonl(_seq_no);
hlo->is_gateway = _gw_info->is_gateway ();
/* extended logging */
Timestamp now = Timestamp::now();
_extended_logging_errh->message("sending %u %ld %ld", _seq_no, now.sec(), now.usec());
if (_log)
_log->log_sent_advertisement(_seq_no, now);
/*
* Update the sequence number for periodic updates, but not for
* triggered updates. originating sequence numbers are even,
* starting at 0. odd numbers are reserved for other nodes to
* advertise broken routes
*/
assert(!(_seq_no & 1));
if (update_seq) {
_fake_seq_no++;
if ((_fake_seq_no % _seq_delay) == 0)
_seq_no += 2;
}
_bcast_count++;
grid_hdr::set_pad_bytes(*gh, htonl(_bcast_count));
hlo->ttl = htonl(grid_hello::MAX_TTL_DEFAULT);
grid_nbr_entry *curr = (grid_nbr_entry *) (hlo + 1);
char str[80];
for (int i = 0; i < num_rtes; i++, curr++) {
const RTEntry &f = rte_info[i];
snprintf(str, sizeof(str),
"%s %s %s %d %c %u %u\n",
f.dest_ip.s().c_str(),
f.loc.s().c_str(),
f.next_hop_ip.s().c_str(),
f.num_hops(),
(f.is_gateway ? 'y' : 'n'),
f.seq_no(),
f.metric);
_extended_logging_errh->message(str);
rte_info[i].fill_in(curr, _link_stat);
}
_extended_logging_errh->message("\n");
output(0).push(p);
}
void
GridRouteTable::RTEntry::fill_in(grid_nbr_entry *nb, LinkStat *ls)
{
check();
nb->ip = dest_ip;
nb->next_hop_ip = next_hop_ip;
nb->num_hops = num_hops();
nb->loc = loc;
nb->loc_err = htons(loc_err);
nb->loc_good = loc_good;
nb->seq_no = htonl(seq_no());
nb->metric = htonl(metric);
nb->metric_valid = metric_valid;
nb->is_gateway = is_gateway;
nb->ttl = htonl(ttl);
/* ping-pong link stats back to sender */
#ifndef SMALL_GRID_HEADERS
nb->link_qual = 0;
nb->link_sig = 0;
nb->measurement_time.tv_sec = nb->measurement_time.tv_usec = 0;
if (ls && num_hops() == 1) {
#if 0
LinkStat::stat_t *s = ls->_stats.findp(next_hop_eth);
#else
struct {
int qual;
int sig;
struct timeval when;
} *s = 0;
#endif
if (s) {
nb->link_qual = htonl(s->qual);
nb->link_sig = htonl(s->sig);
nb->measurement_time.tv_sec = htonl(s->when.tv_sec);
nb->measurement_time.tv_usec = htonl(s->when.tv_usec);
}
else
click_chatter("GridRouteTable: error! unable to get signal strength or quality info for one-hop neighbor %s\n",
IPAddress(dest_ip).s().c_str());
nb->num_rx = 0;
nb->num_expected = 0;
nb->last_bcast.tv_sec = nb->last_bcast.tv_usec = 0;
unsigned int window = 0;
unsigned int num_rx = 0;
unsigned int num_expected = 0;
bool res = ls->get_bcast_stats(next_hop_eth, nb->last_bcast, window, num_rx, num_expected);
if (res) {
if (num_rx > 255 || num_expected > 255) {
click_chatter("GridRouteTable: error! overflow on broadcast loss stats for one-hop neighbor %s",
IPAddress(dest_ip).s().c_str());
num_rx = num_expected = 255;
}
nb->num_rx = num_rx;
nb->num_expected = num_expected;
nb->last_bcast = hton(nb->last_bcast);
}
}
#else
ls = 0; // supress compiler warning
#endif
}
ELEMENT_REQUIRES(userlevel)
EXPORT_ELEMENT(GridRouteTable)
ELEMENT_PROVIDES(GridGenericRouteTable)
#include <click/bighashmap.cc>
#include <click/vector.cc>
template class HashMap<IPAddress, GridRouteTable::RTEntry>;
template class HashMap<IPAddress, bool>;
template class Vector<IPAddress>;
template class Vector<GridRouteTable::RTEntry>;
template class Vector<GridGenericRouteTable::RouteEntry>;
CLICK_ENDDECLS
syntax highlighted by Code2HTML, v. 0.9.1