/*
* dsdvroutetable.{cc,hh} -- DSDV routing element
* Douglas S. J. De Couto
*
* Copyright (c) 2002 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 <stddef.h>
#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 <click/straccum.hh>
#include <click/packet_anno.hh>
#include <elements/grid/dsdvroutetable.hh>
#include <elements/grid/linkstat.hh>
#include <elements/grid/gridgatewayinfo.hh>
#include <elements/grid/timeutils.hh>
// #include <elements/wifi/txfeedbackstats.hh>
CLICK_DECLS
#define DBG 0
#define DBG2 0
#define DBG3 0
#define FULL_DUMP_ON_TRIG_UPDATE 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define dsdv_assert(e) ((e) ? (void) 0 : dsdv_assert_(__FILE__, __LINE__, #e))
bool
DSDVRouteTable::get_one_entry(const IPAddress &dest_ip, RouteEntry &entry)
{
RTEntry r;
bool res = lookup_route(dest_ip, r);
if (res)
entry = r;
return res;
}
bool
DSDVRouteTable::lookup_route(const IPAddress &dest_ip, RTEntry &entry)
{
#if ENABLE_PAUSE
if (_paused) {
RTEntry *r =_snapshot_rtes.findp(dest_ip);
if (r == 0)
return false;
#if USE_OLD_SEQ
if (use_old_route(dest_ip, _snapshot_jiffies))
r = _snapshot_old_rtes.findp(dest_ip);
#endif
entry = *r;
return true;
}
#endif
RTEntry *r = _rtes.findp(dest_ip);
if (r == 0)
return false;
#if USE_OLD_SEQ
if (use_old_route(dest_ip, dsdv_jiffies()))
r = _old_rtes.findp(dest_ip);
#endif
entry = *r;
return true;
}
void
DSDVRouteTable::get_all_entries(Vector<RouteEntry> &vec)
{
#if ENABLE_PAUSE
if (_paused) {
for (RTIter iter = _snapshot_rtes.begin(); iter; iter++) {
const RTEntry &rte = iter.value();
#if USE_OLD_SEQ
if (use_old_route(rte.dest_ip, _snapshot_jiffies))
vec.push_back(_snapshot_old_rtes[rte.dest_ip]);
else
vec.push_back(rte);
#else
vec.push_back(rte);
#endif
return;
}
}
#endif
#if USE_OLD_SEQ
unsigned jiff = dsdv_jiffies();
#endif
for (RTIter iter = _rtes.begin(); iter; iter++) {
const RTEntry &rte = iter.value();
#if USE_OLD_SEQ
if (use_old_route(rte.dest_ip, jiff))
vec.push_back(_old_rtes[rte.dest_ip]);
else
vec.push_back(rte);
#else
vec.push_back(rte);
#endif
}
}
unsigned
DSDVRouteTable::get_number_direct_neigbors()
{
Vector<RouteEntry> v;
// delegate to avoid repeating all the pause/old seq logic
get_all_entries(v);
// assume all direct neighbors are one-hop neighbors, and count
// those instead
int num_nbrs = 0;
for (int i = 0; i < v.size(); i++)
if (v[i].num_hops() == 1 && v[i].good())
num_nbrs++;
return num_nbrs;
}
#if USE_OLD_SEQ
bool
DSDVRouteTable::use_old_route(const IPAddress &dst, unsigned jiff)
{
if (!_use_old_route)
return false;
RTEntry *real = _rtes.findp(dst);
RTEntry *old = _old_rtes.findp(dst);
#if ENABLE_PAUSE
if (_paused) {
real = _snapshot_rtes.findp(dst);
old = _snapshot_old_rtes.findp(dst);
}
#endif
#if USE_GOOD_NEW_ROUTES
// never use an old route if the new one is better
if (_use_good_new_route && real && old && metric_preferable(*real, *old))
return false;
#endif
return
(real && real->good() && // if real route is bad, don't use good but old route
old && old->good() && // if old route is bad, don't use it
real->advertise_ok_jiffies > jiff); // if ok to advertise real route, don't use old route
}
#endif
DSDVRouteTable::DSDVRouteTable() :
#if SEQ_METRIC
_use_seq_metric(false),
#endif
_gw_info(0), _metric(0), _log(0),
_seq_no(0), _mtu(2000), _bcast_count(0),
_max_hops(3), _alpha(88), _wst0(6000),
_last_periodic_update(0),
_last_triggered_update(0),
_ignore_invalid_routes(false),
_hello_timer(static_hello_hook, this),
_log_dump_timer(static_log_dump_hook, this),
_verbose(true)
{
}
DSDVRouteTable::~DSDVRouteTable()
{
for (TMIter i = _expire_timers.begin(); i; i++) {
if (i.value()->scheduled())
i.value()->unschedule();
delete i.value();
}
for (TMIter i = _trigger_timers.begin(); i; i++) {
if (i.value()->scheduled())
i.value()->unschedule();
delete i.value();
}
for (HMIter i = _expire_hooks.begin(); i; i++)
delete i.value();
for (HMIter i = _trigger_hooks.begin(); i; i++)
delete i.value();
}
void *
DSDVRouteTable::cast(const char *n)
{
if (strcmp(n, "DSDVRouteTable") == 0)
return (DSDVRouteTable *) this;
else if (strcmp(n, "GridGenericRouteTable") == 0)
return (GridGenericRouteTable *) this;
else
return 0;
}
int
DSDVRouteTable::configure(Vector<String> &conf, ErrorHandler *errh)
{
String logfile;
int res = cp_va_parse(conf, this, errh,
cpUnsigned, "entry timeout (msec)", &_timeout,
cpUnsigned, "route broadcast period (msec)", &_period,
cpUnsigned, "route broadcast jitter (msec)", &_jitter,
cpUnsigned, "minimum triggered update period (msec)", &_min_triggered_update_period,
cpEthernetAddress, "source Ethernet address", &_eth,
cpIPAddress, "source IP address", &_ip,
cpKeywords,
"VERBOSE", cpBool, "verbose warnings and messages?", &_verbose,
"GW", cpElement, "GridGatewayInfo element", &_gw_info,
"MAX_HOPS", cpUnsigned, "max hops", &_max_hops,
"METRIC", cpElement, "GridGenericMetric element", &_metric,
"LOG", cpElement, "GridGenericLogger element", &_log,
"WST0", cpUnsigned, "initial weight settling time, wst0 (msec)", &_wst0,
"ALPHA", cpUnsigned, "alpha parameter for settling time computation, in percent (0 <= ALPHA <= 100)", &_alpha,
"SEQ0", cpUnsigned, "initial sequence number (must be even)", &_seq_no,
"MTU", cpUnsigned, "interface MTU", &_mtu,
"IGNORE_INVALID_ROUTES", cpBool, "ignore routes with invalid metrics?", &_ignore_invalid_routes,
#if SEQ_METRIC
"USE_SEQ_METRIC", cpBool, "use `dsdv_seqs' metric?", &_use_seq_metric,
#endif
cpEnd);
if (res < 0)
return res;
if (_seq_no & 1)
return errh->error("initial sequence number must be even");
if (_timeout == 0)
return errh->error("timeout interval must be greater than 0");
if (_period == 0)
return errh->error("period must be greater than 0");
// _jitter is allowed to be 0
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");
if (_alpha > 100)
return errh->error("alpha must be between 0 and 100 inclusive");
if (_mtu < sizeof(click_ether) + sizeof(grid_hdr) + sizeof(grid_hello))
return errh->error("mtu is too small to send a route ads");
if (_log && _log->cast("GridGenericLogger") == 0)
return errh->error("LOG element is not a GridGenericLogger");
if (_gw_info && _gw_info->cast("GridGatewayInfo") == 0)
return errh->error("GW element is not a GridGatewayInfo");
if (_metric && _metric->cast("GridGenericMetric") == 0)
return errh->error("METRIC element is not a GridGenericMetric");
if (_gw_info == 0 && _verbose)
errh->warning("No GridGatewayInfo element specified, will default to not advertising as gateway");
if (_metric == 0 && _verbose)
errh->warning("No metric elements specified, will default to minimum hop-count");
#if SEQ_METRIC
if (_metric && _use_seq_metric)
errh->warning("USE_SEQ_METRIC has been specified, the specified METRIC element will be ignored");
#endif
return res;
}
int
DSDVRouteTable::initialize(ErrorHandler *)
{
_hello_timer.initialize(this);
_hello_timer.schedule_after_msec(_period);
_log_dump_timer.initialize(this);
_log_dump_timer.schedule_after_msec(_log_dump_period);
check_invariants();
#if ENABLE_PAUSE
_paused = false;
#endif
#if USE_OLD_SEQ
_use_old_route = false;
#if USE_GOOD_NEW_ROUTES
_use_good_new_route = false;
#endif
#endif
#if ENABLE_SEEN
_use_seen = false;
#endif
return 0;
}
bool
DSDVRouteTable::current_gateway(RouteEntry &gw)
{
RTEntry best;
bool found_gateway = false;
Vector<IPAddress> gw_addrs;
RTIter i = _rtes.begin();
#if ENABLE_PAUSE
if (_paused)
i = _snapshot_rtes.begin();
#endif
for ( ; i; i++) {
if (i.value().is_gateway)
gw_addrs.push_back(i.value().dest_ip);
}
for (Vector<IPAddress>::const_iterator i = gw_addrs.begin(); i != gw_addrs.end(); i++) {
RTEntry r;
bool res = lookup_route(*i, r);
dsdv_assert(res);
if (r.is_gateway && r.good() && (!found_gateway || metric_preferable(r, best))) {
best = r;
found_gateway = true;
}
}
if (found_gateway) {
gw = best;
}
return found_gateway;
}
void
DSDVRouteTable::insert_route(const RTEntry &r, const GridGenericLogger::reason_t why)
{
check_invariants();
r.check();
dsdv_assert(!_ignore_invalid_routes || r.metric.good());
RTEntry *old_r = _rtes.findp(r.dest_ip);
// invariant check: running timers exist for all current good
// routes. no timers or bogus timer entries exist for bad routes.
// hook objects exist for each timer.
Timer **old = _expire_timers.findp(r.dest_ip);
HookPair **oldhp = _expire_hooks.findp(r.dest_ip);
if (old_r && old_r->good())
dsdv_assert(old && *old && (*old)->scheduled() && oldhp && *oldhp);
else {
dsdv_assert(old == 0);
dsdv_assert(oldhp == 0);
}
// get rid of old expire timer
if (old) {
(*old)->unschedule();
delete *old;
delete *oldhp;
_expire_timers.remove(r.dest_ip);
_expire_hooks.remove(r.dest_ip);
}
// Note: ns dsdv only schedules a timeout for the sender of each
// route ad, relying on the next-hop expiry logic to get all routes
// via that next hop. However, that won't work for general metrics,
// so we install a timeout for *every* newly installed good route.
if (r.good()) {
HookPair *hp = new HookPair(this, r.dest_ip);
Timer *t = new Timer(static_expire_hook, (void *) hp);
t->initialize(this);
t->schedule_after_msec(min(r.ttl, _timeout));
_expire_timers.insert(r.dest_ip, t);
_expire_hooks.insert(r.dest_ip, hp);
}
#if USE_OLD_SEQ
// if we are getting new seqno, save route for old seqno
if (old_r && old_r->seq_no() < r.seq_no())
_old_rtes.insert(r.dest_ip, *old_r);
#endif
_rtes.insert(r.dest_ip, r);
// note, we don't change any pending triggered update for this
// updated dest. ... but shouldn't we postpone it? -- shouldn't
// matter if timer fires too early, since the advertise_ok_jiffies
// should tell us it's too early.
if (_log)
_log->log_added_route(why, make_generic_rte(r), (unsigned int) r.wst);
check_invariants();
}
void
DSDVRouteTable::expire_hook(const IPAddress &ip)
{
check_invariants(&ip);
// invariant check:
// 1. route to expire should exist
RTEntry *r = _rtes.findp(ip);
dsdv_assert(r != 0);
// 2. route to expire should be good
dsdv_assert(r->good() && (r->seq_no() & 1) == 0);
// 3. the expire timer for this dest should exist, but should not be
// running.
Timer **old = _expire_timers.findp(ip);
HookPair **oldhp = _expire_hooks.findp(ip);
dsdv_assert(old && *old && !(*old)->scheduled() && oldhp && *oldhp);
if (_log) {
_log->log_start_expire_handler(Timestamp::now());
_log->log_expired_route(GridGenericLogger::TIMEOUT, ip);
}
// Note that for metrics other than hopcount the loop (copied from
// the dsdv ns code) may not actually expire the dest (ip) whose
// timeout called this hook. That's because a node may not be its
// own next hop in that case. So we explicitly note that ip is
// expired before the loop.
Vector<IPAddress> expired_dests;
expired_dests.push_back(ip);
// Do next-hop expiration checks, but only if this node is actually
// its own next hop. With hopcount, it is always the case that if a
// node n1 is some node n2's next hop, then n1 is its own next hop;
// therefore the if() will be true. For other metrics, there can be
// cases where we should not expire n2 just because n1 expires, if
// n1 is not its own next hop.
if (r->num_hops() == 1) {
dsdv_assert(r->next_hop_ip == r->dest_ip);
for (RTIter i = _rtes.begin(); i; i++) {
RTEntry r = i.value();
if (r.dest_ip == ip)
continue; // don't expire this dest twice!
if (r.good() &&
r.next_hop_ip == ip) {
expired_dests.push_back(r.dest_ip);
if (_log)
_log->log_expired_route(GridGenericLogger::NEXT_HOP_EXPIRED, r.dest_ip);
}
}
}
unsigned int jiff = dsdv_jiffies();
for (int i = 0; i < expired_dests.size(); i++) {
RTEntry *r = _rtes.findp(expired_dests[i]);
dsdv_assert(r);
// invariant check:
// 1. route to expire must be good, and thus should have existing
// expire timer and hook object.
Timer **exp_timer = _expire_timers.findp(r->dest_ip);
dsdv_assert(exp_timer && *exp_timer);
HookPair **hp = _expire_hooks.findp(r->dest_ip);
dsdv_assert(hp && *hp);
// 2. that existing timer should still be scheduled, except for
// the timer whose expiry called this hook
dsdv_assert(r->dest_ip != ip ? (*exp_timer)->scheduled() : true);
// cleanup pending timers
if ((*exp_timer)->scheduled())
(*exp_timer)->unschedule();
delete *exp_timer;
delete *hp;
_expire_timers.remove(r->dest_ip);
_expire_hooks.remove(r->dest_ip);
// mark route as broken
r->invalidate(jiff);
#if USE_OLD_SEQ
RTEntry *old_r = _old_rtes.findp(r->dest_ip);
if (old_r && old_r->good())
old_r->invalidate(jiff);
#endif
r->ttl = grid_hello::MAX_TTL_DEFAULT;
// set up triggered ad
r->advertise_ok_jiffies = jiff;
r->need_seq_ad = true;
r->need_metric_ad = true;
schedule_triggered_update(r->dest_ip, jiff);
}
if (_log)
_log->log_end_expire_handler();
check_invariants();
}
void
DSDVRouteTable::schedule_triggered_update(const IPAddress &ip, unsigned int when)
{
check_invariants();
// get rid of outstanding triggered request (if any)
Timer **old = _trigger_timers.findp(ip);
HookPair **oldhp = _trigger_hooks.findp(ip);
if (old) {
dsdv_assert(*old && (*old)->scheduled() && oldhp && *oldhp);
(*old)->unschedule();
delete *old;
delete *oldhp;
}
// set up new timer
HookPair *hp = new HookPair(this, ip);
Timer *t = new Timer(static_trigger_hook, (void *) hp);
t->initialize(this);
unsigned int jiff = dsdv_jiffies();
t->schedule_after_msec(jiff_to_msec(jiff > when ? 0 : when - jiff));
_trigger_timers.insert(ip, t);
_trigger_hooks.insert(ip, hp);
check_invariants();
}
void
DSDVRouteTable::trigger_hook(const IPAddress &ip)
{
check_invariants(&ip);
// invariant: the trigger timer must exist for this dest, but must
// not be running
Timer **old = _trigger_timers.findp(ip);
HookPair **oldhp = _trigger_hooks.findp(ip);
dsdv_assert(old && *old && !(*old)->scheduled() && oldhp && *oldhp);
unsigned int jiff = dsdv_jiffies();
unsigned int next_trigger_jiff = _last_triggered_update + msec_to_jiff(_min_triggered_update_period);
#if DBG
click_chatter("%s: XXX trigger_hoook(%s)\n", name().c_str(), ip.s().c_str());
#endif
if (jiff >= next_trigger_jiff) {
// It's ok to send a triggered update now. Cleanup expired timer.
delete *old;
delete *oldhp;
_trigger_timers.remove(ip);
_trigger_hooks.remove(ip);
send_triggered_update(ip);
#if DBG
click_chatter("%s: XXX sent triggered update\n", name().c_str());
#endif
}
else {
#if DBG
click_chatter("%s: XXX too early to send triggered update (jiff=%d, next_trigger_jiff=%d, _min_triggered_update_period=%d)\n", name().c_str(), jiff, next_trigger_jiff, _min_triggered_update_period);
#endif
// it's too early to send this update, so cancel all oustanding
// triggered updates that would also be too early
Vector<IPAddress> remove_list;
for (TMIter i = _trigger_timers.begin(); i; i++) {
if (i.key() == ip)
continue; // don't touch this timer, we'll reschedule it
Timer *old2 = i.value();
dsdv_assert(old2 && old2->scheduled());
HookPair **oldhp = _trigger_hooks.findp(i.key());
dsdv_assert(oldhp && *oldhp);
RTEntry *r = _rtes.findp(i.key());
if (r->advertise_ok_jiffies < next_trigger_jiff) {
delete old2;
delete *oldhp;
remove_list.push_back(i.key());
}
}
for (int i = 0; i < remove_list.size(); i++) {
_trigger_timers.remove(remove_list[i]);
_trigger_hooks.remove(remove_list[i]);
}
// reschedule this timer to earliest possible time -- when it
// fires, its update will also include updates that would have
// fired before then but were cancelled just above.
(*old)->schedule_after_msec(jiff_to_msec(next_trigger_jiff - jiff));
}
check_invariants();
}
void
DSDVRouteTable::init_metric(RTEntry &r)
{
dsdv_assert(r.num_hops() == 1);
#if SEQ_METRIC
if (_use_seq_metric) {
r.metric = metric_t(r.num_hops());
DEQueue<unsigned> *q = _seq_history.findp(r.dest_ip);
if (!q || q->size() < MAX_BCAST_HISTORY)
r.metric = _bad_metric;
else {
dsdv_assert(q->size() == MAX_BCAST_HISTORY);
unsigned num_missing = q->back() - (q->front() + MAX_BCAST_HISTORY - 1);
if (num_missing > MAX_BCAST_HISTORY - OLD_BCASTS_NEEDED)
r.metric = _bad_metric;
}
return;
}
#endif
if (_metric)
r.metric = _metric->get_link_metric(r.dest_eth, true);
else
r.metric = _bad_metric;
}
void
DSDVRouteTable::update_wst(RTEntry *old_r, RTEntry &new_r, unsigned int jiff)
{
if (old_r) {
old_r->check();
dsdv_assert(old_r->last_updated_jiffies <= new_r.last_updated_jiffies);
}
if (old_r == 0) {
new_r.wst = _wst0;
new_r.last_seq_jiffies = jiff;
new_r.check();
}
else if (old_r->seq_no() == new_r.seq_no()) {
new_r.wst = old_r->wst;
new_r.last_seq_jiffies = old_r->last_seq_jiffies;
new_r.check();
}
else if (old_r->seq_no() < new_r.seq_no()) {
dsdv_assert(old_r->last_updated_jiffies >= old_r->last_seq_jiffies); // XXX failed!
new_r.wst = _alpha * old_r->wst +
(100 - _alpha) * jiff_to_msec(old_r->last_updated_jiffies - old_r->last_seq_jiffies);
new_r.wst /= 100; // since _alpha is 0-100 percent
new_r.last_seq_jiffies = jiff;
new_r.check();
}
else {
dsdv_assert(old_r->seq_no() > new_r.seq_no());
// Do nothing. We will never accept this route anyway. Well,
// almost never. See the reboot/wraparound handling in
// the handle_update() function.
}
// XXX when our current route is broken, and the new route is good,
// what happens to wst?
// from dsdv ns code: Note that we don't touch the changed_at time,
// so that when wst is computed, it doesn't consider the infinte
// metric the best one at that sequence number.
}
void
DSDVRouteTable::update_metric(RTEntry &r)
{
dsdv_assert(r.num_hops() > 1);
RTEntry *next_hop = _rtes.findp(r.next_hop_ip);
if (!next_hop) {
click_chatter("DSDVRouteTable %s: ERROR updating metric for %s; no information for next hop %s; invalidating metric",
name().c_str(), r.dest_ip.s().c_str(), r.next_hop_ip.s().c_str());
r.metric = _bad_metric;
return;
}
#if ENABLE_SEEN
if (_use_seen && next_hop->metric.val() == _metric_seen) {
r.metric = metric_t(_metric_seen, false);
return;
}
#endif
#if SEQ_METRIC
if (_use_seq_metric) {
r.metric = metric_t(r.metric.val() + next_hop->metric.val());
return;
}
#endif
if (_metric)
r.metric = _metric->prepend_metric(r.metric, next_hop->metric);
else
r.metric = _bad_metric;
}
bool
DSDVRouteTable::metric_preferable(const RTEntry &r1, const RTEntry &r2)
{
// true if r1 is preferable to r2
#if DBG2
click_chatter("%s: XXX metric_preferable valid? 1:%s 2:%s 1 < 2? %s", name().c_str(),
(r1.metric.good() ? "yes" : "no"), (r2.metric.good() ? "yes" : "no"),
(metric_val_lt(r1.metric.val(), r2.metric.val()) ? "yes" : "no"));
click_chatter("\tr1.metric=%u, r2.metric=%u", r1.metric.val(), r2.metric.val());
#endif
// prefer a route with a valid metric
if (r1.metric.good() && !r2.metric.good())
return true;
if (!r1.metric.good() && r2.metric.good())
return false;
// If neither metric is valid, fall back to hopcount. Would you
// prefer a 5-hop route or a 2-hop route, given that you don't have
// any other information about them? duh.
if (!r1.metric.good() && !r2.metric.good())
return r1.num_hops() < r2.num_hops();
dsdv_assert(r1.metric.good() && r2.metric.good());
return metric_val_lt(r1.metric, r2.metric);
}
bool
DSDVRouteTable::metric_val_lt(const metric_t &m1, const metric_t &m2)
{
assert(m1.good() && m2.good());
// Better metric should be ``less''
#if SEQ_METRIC
if (_use_seq_metric)
return m1.val() < m2.val();
#endif
if (_metric)
return _metric->metric_val_lt(m1, m2);
else
return false;
}
bool
DSDVRouteTable::metrics_differ(const metric_t &m1, const metric_t &m2)
{
if (!m1.good() && !m2.good()) return false;
if (m1.good() && !m2.good()) return true;
if (!m1.good() && m2.good()) return true;
dsdv_assert(m1.good() && m2.good());
return metric_val_lt(m1, m2) || metric_val_lt(m2, m1);
}
void
DSDVRouteTable::send_full_update()
{
check_invariants();
#if DBG
click_chatter("%s: XXX sending full update\n", name().c_str());
#endif
unsigned int jiff = dsdv_jiffies();
Vector<RTEntry> routes;
for (RTIter i = _rtes.begin(); i; i++) {
const RTEntry &r = i.value();
if (r.advertise_ok_jiffies <= jiff)
routes.push_back(r);
#if DBG
else
click_chatter("%s: XXX excluding %s\n", name().c_str(), r.dest_ip.s().c_str());
#endif
}
// send out ads and reset ``need advertisement'' flag
Vector<RTEntry> ad_routes;
for (int i = 0; i < routes.size() && i < max_rtes_per_ad(); i++) {
if (ad_routes.size() == max_rtes_per_ad()) {
build_and_tx_ad(ad_routes);
ad_routes.clear();
#if DBG
click_chatter("%s: too many routes; sending out partial full dump (%d)\n",
name().c_str(), i);
#endif
}
ad_routes.push_back(routes[i]);
RTEntry *r = _rtes.findp(routes[i].dest_ip);
dsdv_assert(r);
r->need_seq_ad = false;
r->need_metric_ad = false;
r->last_adv_metric = r->metric;
}
build_and_tx_ad(ad_routes);
/*
* 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
*/
_seq_no += 2;
_last_periodic_update = jiff;
_last_triggered_update = jiff;
check_invariants();
}
void
DSDVRouteTable::send_triggered_update(const IPAddress &ip)
{
check_invariants();
// Check that there is actually a route to the destination which
// prompted this trigger. There ought to be since we never actually
// take entries out of the route table; we only mark them as
// expired.
RTEntry *r = _rtes.findp(ip);
dsdv_assert(r);
unsigned int jiff = dsdv_jiffies();
Vector<RTEntry> triggered_routes;
for (RTIter i = _rtes.begin(); i; i++) {
const RTEntry &r = i.value();
if ((r.need_seq_ad || r.need_metric_ad) &&
r.advertise_ok_jiffies <= jiff)
triggered_routes.push_back(r);
}
#if FULL_DUMP_ON_TRIG_UPDATE
// ns implementation of dsdv has this ``heuristic'' to decide when
// to just do a full update. slightly bogus, i mean, why > 3?
if (3*triggered_routes.size() > _rtes.size() && triggered_routes.size() > 3) {
send_full_update();
return;
}
#endif
if (triggered_routes.size() == 0)
return;
// send out ads and reset ``need advertisement'' flag
Vector<RTEntry> ad_routes;
for (int i = 0; i < triggered_routes.size(); i++) {
if (ad_routes.size() == max_rtes_per_ad()) {
build_and_tx_ad(ad_routes);
ad_routes.clear();
#if DBG
click_chatter("%s: too many routes; sending out partial triggered update (%d)\n",
name().c_str(), i);
#endif
}
ad_routes.push_back(triggered_routes[i]);
RTEntry *r = _rtes.findp(triggered_routes[i].dest_ip);
dsdv_assert(r);
r->need_seq_ad = false; // XXX why not reset need_metric_ad flag as well?
r->last_adv_metric = r->metric;
}
build_and_tx_ad(ad_routes);
_last_triggered_update = jiff;
check_invariants();
}
bool
DSDVRouteTable::handle_update(RTEntry new_r, const bool was_sender, const unsigned int jiff)
{
check_invariants();
new_r.check();
dsdv_assert(was_sender ? new_r.num_hops() == 1 : new_r.num_hops() != 1);
if (new_r.good() && new_r.num_hops() >_max_hops)
return false; // ignore ``non-local'' routes
if (was_sender)
init_metric(new_r);
else if (new_r.good())
update_metric(new_r);
if (_ignore_invalid_routes && !new_r.metric.good())
return false; // don't keep routes with invalid metrics
RTEntry *old_r = _rtes.findp(new_r.dest_ip);
update_wst(old_r, new_r, jiff);
// If the new route is good, and the old route (if any) was good,
// wait for the settling time to pass since we first heard this
// sequence number before advertising. Otherwise, propagate the
// route immediately (e.g. a newly appearing node, or broken route).
//
// Note: I think the DSDV code in the ns simulator has this wrong.
// See line 652 in file cmu/dsdv/dsdv.cc. That code sets the time
// it's ok to advertise at to the current time + 2 * wst, which
// would be as if we were adding jiff instead of
// new_r.last_seq_jiffies in the code below.
if (new_r.good() && (!old_r || old_r->good())) // XXX comment implies: new_r.good() && old_r && old_r->good()
new_r.advertise_ok_jiffies = new_r.last_seq_jiffies + msec_to_jiff((unsigned int) (2 * new_r.wst));
else
new_r.advertise_ok_jiffies = jiff;
#if DBG
click_chatter("%s: XXX dest=%s advertise_ok_jiffies=%u wst=%u jiff=%d\n",
name().c_str(), new_r.dest_ip.s().c_str(),
new_r.advertise_ok_jiffies, new_r.wst, jiff);
#endif
if (!old_r) {
// Never heard of this destination before
if (new_r.good()) {
new_r.need_metric_ad = true;
schedule_triggered_update(new_r.dest_ip, new_r.advertise_ok_jiffies);
#if DBG
click_chatter("%s: XXX scheduled brand-new route to %s to be advertised in %d jiffies from now\n", name().c_str(),
new_r.dest_ip.s().c_str(), new_r.advertise_ok_jiffies - jiff);
#endif
}
insert_route(new_r, was_sender ? GridGenericLogger::NEW_DEST_SENDER : GridGenericLogger::NEW_DEST);
}
else if (old_r->seq_no() == new_r.seq_no()) {
// Accept if better route
dsdv_assert(new_r.good() ? old_r->good() : old_r->broken()); // same seq ==> same broken state
#if DBG2
click_chatter("%s: XXX checking for better route to %s from %s with same seqno %u",
name().c_str(), new_r.dest_ip.s().c_str(), new_r.next_hop_ip.s().c_str(), new_r.seq_no());
click_chatter("%s: XXX good=%s preferable=%s", name().c_str(), new_r.good() ? "yes" : "no",
metric_preferable(new_r, *old_r) ? "yes" : "no");
#endif
if (new_r.good() && metric_preferable(new_r, *old_r)) {
if (metrics_differ(new_r.metric, new_r.last_adv_metric)) {
new_r.need_metric_ad = true;
schedule_triggered_update(new_r.dest_ip, new_r.advertise_ok_jiffies);
}
insert_route(new_r, was_sender ? GridGenericLogger::BETTER_RTE_SENDER : GridGenericLogger::BETTER_RTE);
}
}
else if (old_r->seq_no() < new_r.seq_no()) {
// Must *always* accept newer info
new_r.need_seq_ad = true; // XXX this may not be best, see bake-off paper
schedule_triggered_update(new_r.dest_ip, new_r.advertise_ok_jiffies);
if (metrics_differ(new_r.metric, new_r.last_adv_metric))
new_r.need_metric_ad = true;
insert_route(new_r, was_sender ? GridGenericLogger::NEWER_SEQ_SENDER : GridGenericLogger::NEWER_SEQ);
}
else {
dsdv_assert(old_r->seq_no() > new_r.seq_no());
if (new_r.broken() && old_r->good()) {
// Someone has stale info, give them good info
old_r->advertise_ok_jiffies = jiff;
old_r->need_metric_ad = true;
schedule_triggered_update(old_r->dest_ip, jiff);
check_invariants();
return false;
}
else if (new_r.good() && old_r->broken()) {
// Perhaps a node rebooted? This case is not handled by ns
// simulator DSDV code.
dsdv_assert(jiff >= old_r->last_expired_jiffies);
unsigned age = jiff_to_msec(jiff - old_r->last_expired_jiffies);
if (age > 2 * grid_hello::MAX_TTL_DEFAULT || was_sender) {
// Assume we got a new entry, not a stale entry that has been
// floating around the network. Treat as newer sequence number,
// but slightly differently: reboot implies everything could
// be different.
new_r.need_seq_ad = true;
new_r.need_metric_ad = true;
new_r.last_seq_jiffies = jiff; // not done by update_wst() becaue seq is less, so do it here
dsdv_assert(new_r.last_updated_jiffies == new_r.last_seq_jiffies);
schedule_triggered_update(new_r.dest_ip, new_r.advertise_ok_jiffies);
insert_route(new_r, was_sender ? GridGenericLogger::REBOOT_SEQ_SENDER : GridGenericLogger::REBOOT_SEQ);
}
}
}
check_invariants();
return true;
}
Packet *
DSDVRouteTable::simple_action(Packet *packet)
{
check_invariants();
dsdv_assert(packet);
unsigned int jiff = dsdv_jiffies();
/*
* sanity check the packet, get pointers to headers. These should
* be redundant due to classifiers etc. in the Grid Click
* configuration, but don't dis paranoia.
*/
click_ether *eh = (click_ether *) packet->data();
if (ntohs(eh->ether_type) != ETHERTYPE_GRID) {
click_chatter("DSDVRouteTable %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("DSDVRouteTable %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);
if (ethaddr == _eth) {
click_chatter("DSDVRouteTable %s: received own Grid packet; ignoring it", name().c_str());
packet->kill();
return 0;
}
grid_hello *hlo = (grid_hello *) (gh + 1);
if (_log)
_log->log_start_recv_advertisement(ntohl(hlo->seq_no), ipaddr, Timestamp::now());
// assume CheckGridHeader was used to check for truncated packets
// and bad checksums. Sanity check number of entries.
int entry_sz = hlo->nbr_entry_sz;
char *entry_ptr = (char *) (hlo + 1);
unsigned max_entries = (ntohs(gh->total_len) - sizeof(*gh) - sizeof(*hlo)) / entry_sz;
unsigned num_entries = hlo->num_nbrs;
if (num_entries > max_entries) {
click_chatter("DSDVRouteTable %s: route ad from %s contains fewer routes than claimed; want %u, have no more than %u",
name().c_str(), ipaddr.s().c_str(), num_entries, max_entries);
num_entries = max_entries;
}
// maybe add new route for message transmitter, sanity check existing entry
RTEntry *r = _rtes.findp(ipaddr);
if (!r)
click_chatter("DSDVRouteTable %s: new 1-hop nbr %s -- %s",
name().c_str(), ipaddr.s().c_str(), ethaddr.s().c_str());
else if (r->dest_eth && r->dest_eth != ethaddr)
click_chatter("DSDVRouteTable %s: ethernet address of %s changed from %s to %s",
name().c_str(), ipaddr.s().c_str(), r->dest_eth.s().c_str(), ethaddr.s().c_str());
#if SEQ_METRIC
// track last few broadcast numbers we heard directly from this node
DEQueue<unsigned> *q = _seq_history.findp(ipaddr);
if (!q) {
_seq_history.insert(ipaddr, DEQueue<unsigned>());
q = _seq_history.findp(ipaddr);
}
unsigned bcast_num = ntohl(grid_hdr::get_pad_bytes(*gh));
q->push_back(bcast_num);
while (q->size() > MAX_BCAST_HISTORY)
q->pop_front();
#endif
RTEntry new_r(ipaddr, ethaddr, gh, hlo, PAINT_ANNO(packet), jiff);
bool inserted_new_r;
#if ENABLE_SEEN
bool sender_saw_us = false;
const char *c = entry_ptr;
for (unsigned i = 0; i < num_entries; i++, c += entry_sz) {
const grid_nbr_entry *e = (const grid_nbr_entry *) c;
if (e->ip == _ip.addr() && e->num_hops == 1) {
sender_saw_us = true;
break;
}
}
new_r.last_seen_jiffies = sender_saw_us ? jiff : 0;
RTEntry *old = _rtes.findp(new_r.dest_ip);
// If the sending node didn't see us, and has never seen us, or
// hasn't seen us in a while, mark the sender as `seen' instead of
// giving it a proper metric.
#if 0
if (old)
click_chatter("XXX %s %s snd_saw %s old metric %u old last seen %u\n",
name().c_str(), ipaddr.s().c_str(), sender_saw_us ? "y" : "n", old->metric.val, old->last_seen_jiffies);
else
click_chatter("XXX %s %s snd_saw %s\n",
name().c_str(), ipaddr.s().c_str(), sender_saw_us ? "y" : "n");
#endif
if (_use_seen && !sender_saw_us &&
(!old || old->metric.val() == _metric_seen || (jiff - old->last_seen_jiffies) > 3*msec_to_jiff(_period))) {
new_r.metric = metric_t(_metric_seen, false);
new_r.advertise_ok_jiffies = jiff;
new_r.need_metric_ad = true;
schedule_triggered_update(new_r.dest_ip, jiff);
insert_route(new_r, GridGenericLogger::NEW_DEST_SENDER);
inserted_new_r = true;
goto after_sender_update;
}
#endif // ENABLE_SEEN
// insert 1-hop route
inserted_new_r = handle_update(new_r, true, jiff);
#if ENABLE_SEEN
after_sender_update:
#endif
// update this dest's eth, if we inserted it into the route table
if (inserted_new_r) {
r = _rtes.findp(ipaddr);
dsdv_assert(r);
r->dest_eth = ethaddr;
}
// handle each entry in message
bool need_full_update = false;
for (unsigned i = 0; i < num_entries; i++, entry_ptr += entry_sz) {
grid_nbr_entry *curr = (grid_nbr_entry *) entry_ptr;
RTEntry route(ipaddr, ethaddr, curr, PAINT_ANNO(packet), jiff);
if (route.ttl == 0) // ignore expired ttl
continue;
if (route.dest_ip == _ip) { // ignore route to self
if (route.broken()) // override broken route to us with new ad
need_full_update = true;
continue;
}
if (curr->next_hop_ip == (unsigned int) _ip)
continue; // pseudo split-horizon
handle_update(route, false, jiff);
}
if (_log)
_log->log_end_recv_advertisement();
if (need_full_update)
send_full_update();
packet->kill();
check_invariants();
return 0;
}
String
DSDVRouteTable::jiff_diff_string(unsigned int j1, unsigned int j2) {
bool neg;
unsigned int d = jiff_diff_as_msec(j1, j2, neg);
String ret(d);
if (neg)
ret = "-" + ret;
return ret;
}
unsigned int
DSDVRouteTable::jiff_diff_as_msec(unsigned int j1, unsigned int j2, bool &neg)
{
neg = j2 > j1;
return jiff_to_msec(neg ? j2 - j1 : j1 - j2);
}
String
DSDVRouteTable::print_rtes_v(Element *e, void *)
{
DSDVRouteTable *n = (DSDVRouteTable *) e;
unsigned int jiff = dsdv_jiffies();
String s;
for (RTIter i = n->_rtes.begin(); i; i++) {
#if USE_OLD_SEQ
RTEntry f = i.value();
if (n->use_old_route(f.dest_ip, jiff))
f = n->_old_rtes[f.dest_ip];
#else
const RTEntry &f = i.value();
#endif
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.dest_loc.s()
+ " err=" + (f.loc_good ? "" : "-") + String(f.loc_err) // negate loc if invalid
+ " seq=" + String(f.seq_no())
+ " metric_valid=" + (f.metric.good() ? "yes" : "no")
+ " metric=" + String(f.metric.val())
+ " ttl=" + String(f.ttl)
+ " wst=" + String((unsigned long) f.wst)
+ " need_seq_ad=" + (f.need_seq_ad ? "yes" : "no")
+ " need_metric_ad=" + (f.need_metric_ad ? "yes" : "no")
+ " last_expired=" + jiff_diff_string(f.last_expired_jiffies, jiff)
+ " last_updated=" + jiff_diff_string(f.last_updated_jiffies, jiff)
+ " last_seq=" + jiff_diff_string(f.last_seq_jiffies, jiff)
+ " advertise_ok=" + jiff_diff_string(f.advertise_ok_jiffies, jiff);
#if ENABLE_SEEN
s += " last_seen=" + jiff_diff_string(f.last_seen_jiffies, jiff);
#endif
s += "\n";
}
return s;
}
String
DSDVRouteTable::print_rtes(Element *e, void *)
{
DSDVRouteTable *n = (DSDVRouteTable *) e;
String s;
for (RTIter i = n->_rtes.begin(); i; i++) {
#if USE_OLD_SEQ
unsigned jiff = dsdv_jiffies();
RTEntry f = i.value();
if (n->use_old_route(f.dest_ip, jiff))
f = n->_old_rtes[f.dest_ip];
#else
const RTEntry &f = i.value();
#endif
s += f.dest_ip.s()
+ " next=" + f.next_hop_ip.s()
+ " hops=" + String((int) f.num_hops())
+ " gw=" + (f.is_gateway ? "y" : "n")
+ " metric=" + String(f.metric.val())
+ " seq=" + String(f.seq_no())
+ "\n";
}
return s;
}
String
DSDVRouteTable::print_nbrs_v(Element *e, void *)
{
DSDVRouteTable *n = (DSDVRouteTable *) e;
String s;
for (RTIter i = n->_rtes.begin(); i; i++) {
// only print immediate neighbors
if (!i.value().dest_eth)
continue;
s += i.key().s();
s += " eth=" + i.value().dest_eth.s();
char buf[300];
snprintf(buf, 300, " metric_valid=%s metric=%d if=%d",
i.value().metric.good() ? "yes" : "no",
i.value().metric.val(), (int) i.value().next_hop_interface);
s += buf;
s += "\n";
}
return s;
}
String
DSDVRouteTable::print_nbrs(Element *e, void *)
{
DSDVRouteTable *n = (DSDVRouteTable *) e;
String s;
for (RTIter i = n->_rtes.begin(); i; i++) {
// only print immediate neighbors
if (!i.value().dest_eth)
continue;
s += i.key().s();
s += " eth=" + i.value().dest_eth.s();
s += " if=" + String((int) i.value().next_hop_interface);
s += "\n";
}
return s;
}
String
DSDVRouteTable::print_ip(Element *e, void *)
{
DSDVRouteTable *n = (DSDVRouteTable *) e;
return n->_ip.s();
}
String
DSDVRouteTable::print_eth(Element *e, void *)
{
DSDVRouteTable *n = (DSDVRouteTable *) e;
return n->_eth.s();
}
String
DSDVRouteTable::print_seqno(Element *e, void *)
{
DSDVRouteTable *rt = (DSDVRouteTable *) e;
return String(rt->_seq_no) + "\n";
}
int
DSDVRouteTable::write_seqno(const String &arg, Element *el,
void *, ErrorHandler *errh)
{
DSDVRouteTable *rt = (DSDVRouteTable *) el;
unsigned u;
if (!cp_unsigned(arg, &u))
return errh->error("sequence number must be unsigned");
if (u & 1)
return errh->error("sequence number must be even");
rt->_seq_no = u;
return 0;
}
#if ENABLE_PAUSE
String
DSDVRouteTable::print_paused(Element *e, void *)
{
DSDVRouteTable *rt = (DSDVRouteTable *) e;
return (rt->_paused ? "true\n" : "false\n");
}
int
DSDVRouteTable::write_paused(const String &arg, Element *el,
void *, ErrorHandler *errh)
{
DSDVRouteTable *rt = (DSDVRouteTable *) el;
bool was_paused = rt->_paused;
if (!cp_bool(arg, &rt->_paused))
return errh->error("`paused' must be a boolean");
click_chatter("DSDVRouteTable %s: %s",
rt->name().c_str(), rt->_paused ? "pausing packet routes (_paused = true)" :
"unpausing packet routes (_paused = false)");
if (!was_paused && rt->_paused) {
// if we are switching from unpaused to paused, take a snapshot of
// the route table.
rt->_snapshot_jiffies = dsdv_jiffies();
rt->_snapshot_rtes.clear();
for (RTIter i = rt->_rtes.begin(); i; i++)
rt->_snapshot_rtes.insert(i.key(), i.value());
#if USE_OLD_SEQ
rt->_snapshot_old_rtes.clear();
for (RTIter i = rt->_old_rtes.begin(); i; i++)
rt->_snapshot_old_rtes.insert(i.key(), i.value());
#endif
}
return 0;
}
#endif
String
DSDVRouteTable::print_use_old_route(Element *e, void *)
{
DSDVRouteTable *rt = (DSDVRouteTable *) e;
#define pb(x) ((x) ? "true" : "false")
StringAccum sa;
#if USE_OLD_SEQ
sa << "use old routes: " << pb(rt->_use_old_route)
<< (rt->_use_old_route ? " (don't use until advertised)" : " (use new sequence numbers immediately)") << "\n";
#endif
#if USE_GOOD_NEW_ROUTES
sa << "use good new routes: " << pb(rt->_use_good_new_route)
<< (rt->_use_good_new_route ? " (use good new routes immediately)" : " (wait to use good new routes)") << "\n";
#endif
#if ENABLE_SEEN
sa << "use seen: " << pb(rt->_use_seen)
<< (rt->_use_seen ? " (check for `seen' handshake)" : " (ignore asymmetry)") << "\n";
#endif
return sa.take_string();
#undef pb
}
int
DSDVRouteTable::write_use_old_route(const String &arg, Element *el,
void *, ErrorHandler *errh)
{
DSDVRouteTable *rt = (DSDVRouteTable *) el;
unsigned u;
if (!cp_unsigned(arg, &u))
return errh->error("`use_old_route' must be an unsigned integer");
bool use_good = false;
bool use_old = false;
bool use_seen = false;
if (u & 1)
use_old = true;
if (u & 2)
use_old = use_good = true;
if (u & 4)
use_seen = true;
#if USE_OLD_SEQ
rt->_use_old_route = use_old;
click_chatter("DSDVRouteTable %s: setting _use_old_route to %s",
rt->name().c_str(), rt->_use_old_route ? "true" : "false");
#endif
#if USE_GOOD_NEW_ROUTES
rt->_use_good_new_route = use_good;
click_chatter("DSDVRouteTable %s: setting _use_good_new_route to %s",
rt->name().c_str(), rt->_use_good_new_route ? "true" : "false");
#endif
#if ENABLE_SEEN
rt->_use_seen = use_seen;
click_chatter("DSDVRouteTable %s: setting _use_seen to %s",
rt->name().c_str(), rt->_use_seen ? "true" : "false");
#endif
return 0;
}
String
DSDVRouteTable::print_dump(Element *e, void *)
{
DSDVRouteTable *rt = (DSDVRouteTable *) e;
StringAccum sa;
for (RTIter i = rt->_rtes.begin(); i; i++) {
sa << i.value().dump() << "\n";
}
return sa.take_string();
}
void
DSDVRouteTable::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("seqno", print_seqno, 0);
add_write_handler("seqno", write_seqno, 0);
#if ENABLE_PAUSE
add_read_handler("paused", print_paused, 0);
add_write_handler("paused", write_paused, 0);
#endif
add_read_handler("use_old_route", print_use_old_route, 0);
add_write_handler("use_old_route", write_use_old_route, 0);
add_read_handler("dump", print_dump, 0);
}
void
DSDVRouteTable::hello_hook()
{
unsigned int msecs_to_next_ad = _period;
unsigned int jiff = dsdv_jiffies();
dsdv_assert(jiff >= _last_periodic_update);
unsigned int msec_since_last = jiff_to_msec(jiff - _last_periodic_update);
if (msec_since_last < 2 * _period / 3) {
// a full periodic update was sent ahead of schedule (because
// there were so many triggered updates to send). reschedule this
// period update to one period after the last periodic update
unsigned int jiff_period = msec_to_jiff(_period);
msecs_to_next_ad = jiff_to_msec(_last_periodic_update + jiff_period - jiff);
}
else {
send_full_update();
_last_periodic_update = jiff;
_last_triggered_update = jiff;
}
// reschedule periodic update
long r2 = random();
long r = (r2 >> 1);
unsigned int jitter = (unsigned int) (r % (_jitter + 1));
if (r2 & 1) {
if (jitter <= msecs_to_next_ad) // hello can only happen in the future
msecs_to_next_ad -= jitter;
}
else
msecs_to_next_ad += jitter;
_hello_timer.schedule_after_msec(msecs_to_next_ad);
}
void
DSDVRouteTable::build_and_tx_ad(Vector<RTEntry> &rtes_to_send)
{
/*
* Build and send routing update packet advertising the contents of
* the rtes_to_send vector. Requires that the nuber of entries in
* rtes_to_send is <= the maximum number of routes that fit into a
* single route advertisement.
*/
int num_rtes = rtes_to_send.size();
dsdv_assert(num_rtes <= max_rtes_per_ad());
unsigned int hdr_sz = sizeof(click_ether) + sizeof(grid_hdr) + sizeof(grid_hello);
unsigned int psz = hdr_sz + sizeof(grid_nbr_entry) * num_rtes;
dsdv_assert(psz <= _mtu);
/* allocate and align the packet */
WritablePacket *p = Packet::make(psz + 2); // for alignment
if (p == 0) {
click_chatter("DSDVRouteTable %s: cannot make packet!", name().c_str());
dsdv_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);
dsdv_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 ? _gw_info->is_gateway() : false;
if (_log)
_log->log_sent_advertisement(_seq_no, p->timestamp_anno());
_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);
for (int i = 0; i < num_rtes; i++, curr++)
rtes_to_send[i].fill_in(curr);
output(0).push(p);
}
void
DSDVRouteTable::RTEntry::fill_in(grid_nbr_entry *nb) const
{
check();
nb->ip = dest_ip;
nb->next_hop_ip = next_hop_ip;
nb->num_hops = num_hops();
nb->loc = dest_loc;
nb->loc_err = htons(loc_err);
nb->loc_good = loc_good;
nb->seq_no = htonl(seq_no());
nb->metric = htonl(metric.val());
nb->metric_valid = metric.good();
nb->is_gateway = is_gateway;
unsigned int jiff = dsdv_jiffies();
unsigned int ttl_decrement = jiff_to_msec(good() ? jiff - last_updated_jiffies : jiff - last_expired_jiffies);
nb->ttl = htonl(decr_ttl(ttl, max(ttl_decrement, grid_hello::MIN_TTL_DECREMENT)));
/* 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;
#endif
}
void
DSDVRouteTable::log_dump_hook(bool reschedule)
{
if (_log) {
Vector<RouteEntry> vec;
get_all_entries(vec);
_log->log_route_dump(vec, Timestamp::now());
}
if (reschedule)
_log_dump_timer.schedule_after_msec(_log_dump_period);
}
String
DSDVRouteTable::RTEntry::dump() const
{
check();
unsigned int jiff = dsdv_jiffies();
StringAccum sa;
sa << " curr jiffies: " << jiff << "\n"
<< " dest_ip: " << dest_ip.s().c_str() << "\n"
<< " dest_eth: " << dest_eth.s().c_str() << "\n"
<< " next_hop_ip: " << next_hop_ip.s().c_str() << "\n"
<< " next_hop_eth: " << next_hop_eth.s().c_str() << "\n"
<< "next_hop_iface: " << next_hop_interface << "\n"
<< " seq_no: " << seq_no() << "\n"
<< " num_hops: " << (unsigned int) num_hops() << "\n"
<< " last_updated: " << jiff_diff_string(last_updated_jiffies, jiff).c_str() << "\n"
<< " last_expired: " << jiff_diff_string(last_expired_jiffies, jiff).c_str() << "\n"
<< " last_seq: " << jiff_diff_string(last_seq_jiffies, jiff).c_str() << "\n"
<< " advertise_ok: " << jiff_diff_string(advertise_ok_jiffies, jiff).c_str() << "\n"
<< " metric: " << metric.val() << "\n"
<< "need_metric_ad: " << need_metric_ad << "\n"
<< " need_seq_ad: " << need_seq_ad << "\n"
<< " wst: " << (unsigned int) wst << "\n";
return sa.take_string();
}
void
DSDVRouteTable::check_invariants(const IPAddress *ignore) const
{
for (RTIter i = _rtes.begin(); i; i++) {
const RTEntry &r = i.value();
r.check();
dsdv_assert(!_ignore_invalid_routes || r.metric.good());
if (ignore && *ignore == i.key())
continue;
// check expire timer invariants
Timer **t = _expire_timers.findp(r.dest_ip);
HookPair **hp = _expire_hooks.findp(r.dest_ip);
if (r.good()) {
dsdv_assert(t);
dsdv_assert(*t);
dsdv_assert((*t)->scheduled());
dsdv_assert(hp);
dsdv_assert(*hp);
dsdv_assert((*hp)->obj == this);
dsdv_assert((*hp)->ip == (unsigned int) r.dest_ip);
}
else {
dsdv_assert(!t);
dsdv_assert(!hp);
}
// check trigger timer invariants
t = _trigger_timers.findp(r.dest_ip);
hp = _trigger_hooks.findp(r.dest_ip);
if (t) {
dsdv_assert(*t);
dsdv_assert((*t)->scheduled());
dsdv_assert(hp);
dsdv_assert(*hp);
dsdv_assert((*hp)->obj == this);
dsdv_assert((*hp)->ip == (unsigned int) r.dest_ip);
// dsdv_assert(r.need_seq_ad || r.need_metric_ad); // see note for trigger invariants
}
else {
dsdv_assert(!hp);
}
}
}
void
DSDVRouteTable::dsdv_assert_(const char *file, int line, const char *expr) const
{
click_chatter("DSDVRouteTable %s assertion \"%s\" failed: file %s, line %d",
name().c_str(), expr, file, line);
click_chatter("Routing table state:");
for (RTIter i = _rtes.begin(); i; i++) {
click_chatter("%s\n", i.value().dump().c_str());
}
#ifdef CLICK_USERLEVEL
abort();
#else
click_chatter("Continuing execution anyway, hold on to your hats!\n");
#endif
}
ELEMENT_PROVIDES(GridGenericRouteTable)
EXPORT_ELEMENT(DSDVRouteTable)
#include <click/hashmap.cc>
#include <click/vector.cc>
template class HashMap<IPAddress, DSDVRouteTable::RTEntry>;
template class HashMap<IPAddress, Timer *>;
template class Vector<DSDVRouteTable::RTEntry>;
#include <click/dequeue.cc>
template class DEQueue<unsigned>;
CLICK_ENDDECLS
syntax highlighted by Code2HTML, v. 0.9.1