cyrus3459
February 7th, 2006, 05:25 PM
i was given a code by my project supervisor which i dont understand. i know it simulates a wireless routing protocol known as DSDV (direct sequence distance vector) and small pieces of the code but generally i dont understand the code. i am asking if the code could be translated into and algorithm or some understandable level. this is a copy of the code:
extern "C" {
#include <stdarg.h>
#include <float.h>
};
#include "dsdv.h"
#include "priqueue.h"
#include <random.h>
#include <cmu-trace.h>
#include <address.h>
#include <mobilenode.h>
#define DSDV_STARTUP_JITTER 2.0
#define DSDV_ALMOST_NOW 0.1
#define DSDV_BROADCAST_JITTER 0.01
#define DSDV_MIN_TUP_PERIOD 1.0 updates
#define IP_DEF_TTL 32
#undef TRIGGER_UPDATE_ON_FRESH_SEQNUM
jitter (double max, int be_random_)
{
return (be_random_ ? Random::uniform(max) : 0);
}
void DSDV_Agent::
trace (char *fmt,...)
{
va_list ap;
if (!tracetarget)
return;
va_start (ap, fmt);
vsprintf (tracetarget->pt_->buffer (), fmt, ap);
tracetarget->pt_->dump ();
va_end (ap);
}
void
DSDV_Agent::tracepkt (Packet * p, double now, int me, const char *type)
{
char buf[1024];
unsigned char *walk = p->accessdata ();
int ct = *(walk++);
int seq, dst, met;
snprintf (buf, 1024, "V%s %.5f _%d_ [%d]:", type, now, me, ct);
while (ct--)
{
dst = *(walk++);
dst = dst << 8 | *(walk++);
dst = dst << 8 | *(walk++);
dst = dst << 8 | *(walk++);
met = *(walk++);
seq = *(walk++);
seq = seq << 8 | *(walk++);
seq = seq << 8 | *(walk++);
seq = seq << 8 | *(walk++);
snprintf (buf, 1024, "%s (%d,%d,%d)", buf, dst, met, seq);
}
if (verbose_)
trace ("%s", buf);
}
void
DSDV_Agent::output_rte(const char *prefix, rtable_ent * prte, DSDV_Agent * a)
{
TAKEN OUT CAUSE IT COULDNT FIT}
class DSDVTriggerHandler : public Handler {
public:
DSDVTriggerHandler(DSDV_Agent *a_) { a = a_; }
virtual void handle(Event *e);
private:
DSDV_Agent *a;
};
void
DSDVTriggerHandler::handle(Event *e)
{
Scheduler & s = Scheduler::instance ();
Time now = s.clock ();
rtable_ent *prte;
int update_type;
Time next_possible = a->lasttup_ + DSDV_MIN_TUP_PERIOD;
for (a->table_->InitLoop(); (prte = a->table_->NextLoop());)
if (prte->trigger_event == e) break;
assert(prte && prte->trigger_event == e);
if (now < next_possible)
{
s.schedule(a->trigger_handler, e, next_possible - now);
a->cancelTriggersBefore(next_possible);
return;
}
update_type = 0;
Packet * p = a->makeUpdate(update_type);
if (p != NULL)
{
if (update_type == 1)
{
s.cancel(a->periodic_callback_);
s.schedule (a->helper_, a->periodic_callback_,
a->perup_ * (0.75 + jitter (0.25, a->be_random_)));
if (a->verbose_) a->tracepkt (p, now, a->myaddr_, "PU");
}
else
{
if (a->verbose_) a->tracepkt (p, now, a->myaddr_, "TU");
}
assert (!HDR_CMN (p)->xmit_failure_);
s.schedule (a->target_, p, jitter(DSDV_BROADCAST_JITTER, a->be_random_));
a->lasttup_ = now;
}
for (a->table_->InitLoop (); (prte = a->table_->NextLoop ());)
if (prte->trigger_event && prte->trigger_event == e)
{
prte->trigger_event = 0;
delete e;
}
}
void
DSDV_Agent::cancelTriggersBefore(Time t)
{TAKEN OUT CAUSE IT COULDNT FIT }
void
DSDV_Agent::needTriggeredUpdate(rtable_ent *prte, Time t)
{
TAKEN OUT CAUSE IT COULDNT FIT
}
void
DSDV_Agent::helper_callback (Event * e)
{
TAKEN OUT CAUSE IT COULDNT FIT}
void
DSDV_Agent::lost_link (Packet *p)
{
hdr_cmn *hdrc = HDR_CMN (p);
rtable_ent *prte = table_->GetEntry (hdrc->next_hop_);
if(use_mac_ == 0) {
drop(p, DROP_RTR_MAC_CALLBACK);
return;
}
if (verbose_ && hdrc->addr_type_ == NS_AF_INET)
trace("VLL %.8f %d->%d lost at %d",
Scheduler::instance().clock(),
hdr_ip::access(p)->saddr(), hdr_ip::access(p)->daddr(),
myaddr_);
if (!use_mac_ || !prte || hdrc->addr_type_ != NS_AF_INET)
return;
if (verbose_)
trace ("VLP %.5f %d:%d->%d:%d lost at %d [hop %d]",
Scheduler::instance ().clock (),
hdr_ip::access (p)->saddr(),
hdr_ip::access (p)->sport(),
hdr_ip::access (p)->daddr(),
hdr_ip::access (p)->dport(),
myaddr_, prte->dst);
if (prte->timeout_event)
{
Scheduler::instance ().cancel (prte->timeout_event);
helper_callback (prte->timeout_event);
}
else if (prte->metric != BIG)
{
assert(prte->timeout_event == 0);
prte->timeout_event = new Event ();
helper_callback (prte->timeout_event);
}
recv(p, 0);
#if 0
while (p2 = ((PriQueue *) target_)->filter (prte->dst))
{
if (verbose_)
trace ("VRS %.5f %d:%d->%d:%d lost at %d", Scheduler::instance ().clock (),
hdr_ip::access (p2)->saddr(),
hdr_ip::access (p2)->sport(),
hdr_ip::access (p2)->daddr(),
hdr_ip::access (p2)->dport(), myaddr_);
recv(p2, 0);
}
while (p2 = ll_queue->filter (prte->dst))
{
if (verbose_)
trace ("VRS %.5f %d:%d->%d:%d lost at %d", Scheduler::instance ().clock (),
hdr_ip::access (p2)->saddr(),
hdr_ip::access (p2)->sport(),
hdr_ip::access (p2)->daddr(),
hdr_ip::access (p2)->dport(), myaddr_);
recv (p2, 0);
}
#endif
}
static void
mac_callback (Packet * p, void *arg)
{
((DSDV_Agent *) arg)->lost_link (p);
}
Packet *
DSDV_Agent::makeUpdate(int& periodic)
{
Packet *p = allocpkt ();
hdr_ip *iph = hdr_ip::access(p);
hdr_cmn *hdrc = HDR_CMN (p);
double now = Scheduler::instance ().clock ();
rtable_ent *prte;
unsigned char *walk;
int change_count;
int rtbl_sz;
int unadvertiseable;
hdrc->next_hop_ = IP_BROADCAST;
hdrc->addr_type_ = NS_AF_INET;
iph->daddr() = IP_BROADCAST << Address::instance().nodeshift();
iph->dport() = ROUTER_PORT;
change_count = 0;
rtbl_sz = 0;
unadvertiseable = 0;
for (table_->InitLoop ();
(prte = table_->NextLoop ()); )
{
rtbl_sz++;
if ((prte->advert_seqnum || prte->advert_metric)
&& prte->advertise_ok_at <= now)
change_count++;
if (prte->advertise_ok_at > now) unadvertiseable++;
}
if (change_count * 3 > rtbl_sz && change_count > 3)
{
periodic = 1;
}
if (periodic)
{
change_count = rtbl_sz - unadvertiseable;
rtable_ent rte;
bzero(&rte, sizeof(rte));
seqno_ += 2;
rte.dst = myaddr_;
rte.hop = Address::instance().get_nodeaddr(iph->saddr());
rte.metric = 0;
rte.seqnum = seqno_;
rte.advertise_ok_at = 0.0;
rte.advert_seqnum = true;
rte.changed_at = now;
rte.new_seqnum_at = now;
rte.wst = 0;
rte.timeout_event = 0;
rte.q = 0;
table_->AddEntry (rte);
}
if (change_count == 0)
{
Packet::free(p);
return NULL;
}
p->allocdata((change_count * 9) + 1);
walk = p->accessdata ();
*(walk++) = change_count;
hdrc->size_ = change_count * 12 + IP_HDR_LEN;
for (table_->InitLoop (); (prte = table_->NextLoop ());)
{
if (periodic && prte->advertise_ok_at > now)
{ }
if (periodic ||
((prte->advert_seqnum || prte->advert_metric)
&& prte->advertise_ok_at <= now))
{
if (!periodic && verbose_)
trace ("VCT %.5f _%d_ %d", now, myaddr_, prte->dst);
*(walk++) = prte->dst >> 24;
*(walk++) = (prte->dst >> 16) & 0xFF;
*(walk++) = (prte->dst >> 8) & 0xFF;
*(walk++) = (prte->dst >> 0) & 0xFF;
*(walk++) = prte->metric;
*(walk++) = (prte->seqnum) >> 24;
*(walk++) = ((prte->seqnum) >> 16) & 0xFF;
*(walk++) = ((prte->seqnum) >> 8) & 0xFF;
*(walk++) = (prte->seqnum) & 0xFF;
prte->last_advertised_metric = prte->metric;
prte->advert_seqnum = false;
if (periodic)
{
prte->advert_seqnum = false;
prte->advert_metric = false;
}
change_count--;
}
}
assert(change_count == 0);
return p;
}
void
DSDV_Agent::updateRoute(rtable_ent *old_rte, rtable_ent *new_rte)
{
int negvalue = -1;
assert(new_rte);
Time now = Scheduler::instance().clock();
char buf[1024];
snprintf (buf, 1024, "%c %.5f _%d_ (%d,%d->%d,%d->%d,%d->%d,%f)",
(new_rte->metric != BIG
&& (!old_rte || old_rte->metric != BIG)) ? 'D' : 'U',
now, myaddr_, new_rte->dst,
old_rte ? old_rte->metric : negvalue, new_rte->metric,
old_rte ? old_rte->seqnum : negvalue, new_rte->seqnum,
old_rte ? old_rte->hop : -1, new_rte->hop,
new_rte->advertise_ok_at);
table_->AddEntry (*new_rte);
if (trace_wst_)
trace ("VWST %.12lf frm %d to %d wst %.12lf nxthp %d [of %d]",
now, myaddr_, new_rte->dst, new_rte->wst, new_rte->hop,
new_rte->metric);
if (verbose_)
trace ("VS%s", buf);
}
void
DSDV_Agent::processUpdate (Packet * p)
{
hdr_ip *iph = HDR_IP(p);
Scheduler & s = Scheduler::instance ();
double now = s.clock ();
int i;
unsigned char *d = p->accessdata ();
unsigned char *w = d + 1;
rtable_ent rte;
rtable_ent *prte;
for (i = *d; i > 0; i--)
{
bool trigger_update = false;
nsaddr_t dst;
prte = NULL;
dst = *(w++);
dst = dst << 8 | *(w++);
dst = dst << 8 | *(w++);
dst = dst << 8 | *(w++);
if ((prte = table_->GetEntry (dst)))
{
bcopy(prte, &rte, sizeof(rte));
}
else
{
bzero(&rte, sizeof(rte));
}
rte.dst = dst;
rte.hop = Address::instance().get_nodeaddr(iph->saddr());
rte.metric = *(w++);
rte.seqnum = *(w++);
rte.seqnum = rte.seqnum << 8 | *(w++);
rte.seqnum = rte.seqnum << 8 | *(w++);
rte.seqnum = rte.seqnum << 8 | *(w++);
rte.changed_at = now;
if (rte.metric != BIG) rte.metric += 1;
if (rte.dst == myaddr_)
{
if (rte.metric == BIG && periodic_callback_)
{
s.cancel (periodic_callback_);
s.schedule (helper_, periodic_callback_, 0);
}
}
if (prte)
{
if (prte->seqnum == rte.seqnum)
{ rte.wst = prte->wst;
rte.new_seqnum_at = prte->new_seqnum_at;
}
else
{
rte.wst = alpha_ * prte->wst +
(1.0 - alpha_) * (prte->changed_at - prte->new_seqnum_at);
rte.new_seqnum_at = now;
}
}
else
{
rte.wst = wst0_;
rte.new_seqnum_at = now;
}
if (rte.metric != BIG && (!prte || prte->metric != BIG))
rte.advertise_ok_at = now + (rte.wst * 2);
else
rte.advertise_ok_at = now;
if (!prte)
{
if (rte.metric < BIG)
{
rte.advert_metric = true;
trigger_update = true;
}
updateRoute(prte,&rte);
}
else if ( prte->seqnum == rte.seqnum )
{
if (rte.metric < prte->metric)
{
if (rte.metric == prte->last_advertised_metric)
{ advertised
rte.advert_metric = false;
trigger_update = false;
}
else
{
rte.advert_metric = true;
trigger_update = true;
}
updateRoute(prte,&rte);
}
else
{
}
}
else if ( prte->seqnum < rte.seqnum )
{ rte.advert_seqnum = true;
if (rte.metric == prte->last_advertised_metric)
{
rte.advert_metric = false;
}
else
{
rte.advert_metric = true;
}
updateRoute(prte,&rte);
#ifdef TRIGGER_UPDATE_ON_FRESH_SEQNUM
trigger_update = true;
#else
trigger_update = false;
#endif
}
else if ( prte->seqnum > rte.seqnum )
{
if (rte.metric == BIG && prte->metric != BIG)
{
prte->advertise_ok_at = now;
prte->advert_metric = true;
needTriggeredUpdate(prte,now);
}
else
{
}
}
else
{
fprintf(stderr,
"%s DFU: unhandled adding a route entry?\n", __FILE__);
abort();
}
if (trigger_update)
{
prte = table_->GetEntry (rte.dst);
assert(prte != NULL && prte->advertise_ok_at == rte.advertise_ok_at);
needTriggeredUpdate(prte, prte->advertise_ok_at);
}
if (rte.q && rte.metric != BIG)
{
Packet *queued_p;
while ((queued_p = rte.q->deque()))
recv(queued_p, 0);
delete rte.q;
rte.q = 0;
table_->AddEntry(rte);
}
}
prte = table_->GetEntry(Address::instance().get_nodeaddr(iph->saddr()));
if (prte)
{
if (prte->timeout_event)
s.cancel (prte->timeout_event);
else
{
prte->timeout_event = new Event ();
}
s.schedule (helper_, prte->timeout_event, min_update_periods_ * perup_);
}
else
{
bzero(&rte, sizeof(rte));
rte.dst = Address::instance().get_nodeaddr(iph->saddr());
rte.hop = Address::instance().get_nodeaddr(iph->saddr());
rte.metric = 1;
rte.seqnum = 0;
rte.advertise_ok_at = now + 604800;
rte.changed_at = now;
rte.new_seqnum_at = now;
rte.wst = wst0_;
rte.timeout_event = new Event ();
rte.q = 0;
updateRoute(NULL, &rte);
s.schedule(helper_, rte.timeout_event, min_update_periods_ * perup_);
}
Packet::free (p);
}
int
DSDV_Agent::diff_subnet(int dst)
{TAKEN OUT CAUSE IT COULDNT FIT}
void
DSDV_Agent::forwardPacket (Packet * p)
{
hdr_ip *iph = HDR_IP(p);
Scheduler & s = Scheduler::instance ();
double now = s.clock ();
hdr_cmn *hdrc = HDR_CMN (p);
int dst;
rtable_ent *prte;
hdrc->direction() = hdr_cmn::DOWN;
dst = Address::instance().get_nodeaddr(iph->daddr());
if (diff_subnet(iph->daddr())) {
prte = table_->GetEntry (dst);
if (prte && prte->metric != BIG)
goto send;
dst = node_->base_stn();
prte = table_->GetEntry (dst);
if (prte && prte->metric != BIG)
goto send;
else {
fprintf(stderr, "warning: Route to base_stn not known: dropping pkt\n");
Packet::free(p);
return;
}
}
prte = table_->GetEntry (dst);
if (prte && prte->metric != BIG)
{
goto send;
}
else if (prte)
{
if (!prte->q)
{
prte->q = new PacketQueue ();
}
prte->q->enque(p);
if (verbose_)
trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->saddr(),
iph->sport(), iph->daddr(), iph->dport());
while (prte->q->length () > MAX_QUEUE_LENGTH)
drop (prte->q->deque (), DROP_RTR_QFULL);
return;
}
else
{
rtable_ent rte;
double now = s.clock();
bzero(&rte, sizeof(rte));
rte.dst = dst;
rte.hop = dst;
rte.metric = BIG;
rte.seqnum = 0;
rte.advertise_ok_at = now + 604800;
rte.changed_at = now;
rte.new_seqnum_at = now;
rte.wst = wst0_;
rte.timeout_event = 0;
rte.q = new PacketQueue();
rte.q->enque(p);
assert (rte.q->length() == 1 && 1 <= MAX_QUEUE_LENGTH);
table_->AddEntry(rte);
if (verbose_)
trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_,
iph->saddr(), iph->sport(), iph->daddr(), iph->dport());
return;
}
send:
hdrc->addr_type_ = NS_AF_INET;
hdrc->xmit_failure_ = mac_callback;
hdrc->xmit_failure_data_ = this;
if (prte->metric > 1)
hdrc->next_hop_ = prte->hop;
else
hdrc->next_hop_ = dst;
if (verbose_)
trace ("Routing pkts outside domain:
VFP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->saddr(),
iph->sport(), iph->daddr(), iph->dport());
assert (!HDR_CMN (p)->xmit_failure_ ||
HDR_CMN (p)->xmit_failure_ == mac_callback);
target_->recv(p, (Handler *)0);
return;
}
void
DSDV_Agent::sendOutBCastPkt(Packet *p)
{
Scheduler & s = Scheduler::instance ();
s.schedule (target_, p, jitter(DSDV_BROADCAST_JITTER, be_random_));
}
void
DSDV_Agent::recv (Packet * p, Handler *)
{
hdr_ip *iph = HDR_IP(p);
hdr_cmn *cmh = HDR_CMN(p);
int src = Address::instance().get_nodeaddr(iph->saddr());
if(src == myaddr_ && cmh->num_forwards() == 0) {
cmh->size() += IP_HDR_LEN;
iph->ttl_ = IP_DEF_TTL;
}
else if(src == myaddr_) {
drop(p, DROP_RTR_ROUTE_LOOP);
return;
}
else {
if(--iph->ttl_ == 0) {
drop(p, DROP_RTR_TTL);
return;
}
}
if ((src != myaddr_) && (iph->dport() == ROUTER_PORT))
{
processUpdate(p);
}
else if (iph->daddr() == ((int)IP_BROADCAST) &&
(iph->dport() != ROUTER_PORT))
{
if (src == myaddr_) {
sendOutBCastPkt(p);
}
else {
port_dmux_->recv(p, (Handler*)0);
}
}
else
{
forwardPacket(p);
}
}
static class DSDVClass:public TclClass
{
public:
DSDVClass ():TclClass ("Agent/DSDV")
{
}
TclObject *create (int, const char *const *)
{
return (new DSDV_Agent ());
}
} class_dsdv;
DSDV_Agent::DSDV_Agent (): Agent (PT_MESSAGE), ll_queue (0), seqno_ (0),
myaddr_ (0), subnet_ (0), node_ (0), port_dmux_(0),
periodic_callback_ (0), be_random_ (1),
use_mac_ (0), verbose_ (1), trace_wst_ (0), lasttup_ (-10),
alpha_ (0.875), wst0_ (6), perup_ (15),
min_update_periods_ (3)
{
table_ = new RoutingTable ();
helper_ = new DSDV_Helper (this);
trigger_handler = new DSDVTriggerHandler(this);
bind_time ("wst0_", &wst0_);
bind_time ("perup_", &perup_);
bind ("use_mac_", &use_mac_);
bind ("be_random_", &be_random_);
bind ("alpha_", &alpha_);
bind ("min_update_periods_", &min_update_periods_);
bind ("verbose_", &verbose_);
bind ("trace_wst_", &trace_wst_);
address = 0;
}
void
DSDV_Agent::startUp()
{TAKEN OUT CAUSE IT COULDNT FIT}
int
DSDV_Agent::command (int argc, const char *const *argv)
{
if (argc == 2)
{
if (strcmp (argv[1], "start-dsdv") == 0)
{
startUp();
return (TCL_OK);
}
else if (strcmp (argv[1], "dumprtab") == 0)
{
Packet *p2 = allocpkt ();
hdr_ip *iph2 = HDR_IP(p2);
rtable_ent *prte;
printf ("Table Dump %d[%d]\n---\n",
iph2->saddr(), iph2->sport());
trace ("VTD %.5f %d:%d\n", Scheduler::instance ().clock (),
iph2->saddr(), iph2->sport());
Packet::free (p2);
for (table_->InitLoop (); (prte = table_->NextLoop ());)
output_rte ("\t", prte, this);
printf ("\n");
return (TCL_OK);
}
else if (strcasecmp (argv[1], "ll-queue") == 0)
{
if (!(ll_queue = (PriQueue *) TclObject::lookup (argv[2])))
{
fprintf (stderr, "DSDV_Agent: ll-queue lookup of %s failed\n", argv[2]);
return TCL_ERROR;
}
return TCL_OK;
}
}
else if (argc == 3)
{
if (strcasecmp (argv[1], "addr") == 0) {
int temp;
temp = Address::instance().str2addr(argv[2]);
myaddr_ = temp;
return TCL_OK;
}
TclObject *obj;
if ((obj = TclObject::lookup (argv[2])) == 0)
{
fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__, argv[1],
argv[2]);
return TCL_ERROR;
}
if (strcasecmp (argv[1], "tracetarget") == 0)
{
tracetarget = (Trace *) obj;
return TCL_OK;
}
else if (strcasecmp (argv[1], "node") == 0) {
node_ = (MobileNode*) obj;
return TCL_OK;
}
else if (strcasecmp (argv[1], "port-dmux") == 0) {
port_dmux_ = (NsObject *) obj;
return TCL_OK;
}
}
return (Agent::command (argc, argv));
}
extern "C" {
#include <stdarg.h>
#include <float.h>
};
#include "dsdv.h"
#include "priqueue.h"
#include <random.h>
#include <cmu-trace.h>
#include <address.h>
#include <mobilenode.h>
#define DSDV_STARTUP_JITTER 2.0
#define DSDV_ALMOST_NOW 0.1
#define DSDV_BROADCAST_JITTER 0.01
#define DSDV_MIN_TUP_PERIOD 1.0 updates
#define IP_DEF_TTL 32
#undef TRIGGER_UPDATE_ON_FRESH_SEQNUM
jitter (double max, int be_random_)
{
return (be_random_ ? Random::uniform(max) : 0);
}
void DSDV_Agent::
trace (char *fmt,...)
{
va_list ap;
if (!tracetarget)
return;
va_start (ap, fmt);
vsprintf (tracetarget->pt_->buffer (), fmt, ap);
tracetarget->pt_->dump ();
va_end (ap);
}
void
DSDV_Agent::tracepkt (Packet * p, double now, int me, const char *type)
{
char buf[1024];
unsigned char *walk = p->accessdata ();
int ct = *(walk++);
int seq, dst, met;
snprintf (buf, 1024, "V%s %.5f _%d_ [%d]:", type, now, me, ct);
while (ct--)
{
dst = *(walk++);
dst = dst << 8 | *(walk++);
dst = dst << 8 | *(walk++);
dst = dst << 8 | *(walk++);
met = *(walk++);
seq = *(walk++);
seq = seq << 8 | *(walk++);
seq = seq << 8 | *(walk++);
seq = seq << 8 | *(walk++);
snprintf (buf, 1024, "%s (%d,%d,%d)", buf, dst, met, seq);
}
if (verbose_)
trace ("%s", buf);
}
void
DSDV_Agent::output_rte(const char *prefix, rtable_ent * prte, DSDV_Agent * a)
{
TAKEN OUT CAUSE IT COULDNT FIT}
class DSDVTriggerHandler : public Handler {
public:
DSDVTriggerHandler(DSDV_Agent *a_) { a = a_; }
virtual void handle(Event *e);
private:
DSDV_Agent *a;
};
void
DSDVTriggerHandler::handle(Event *e)
{
Scheduler & s = Scheduler::instance ();
Time now = s.clock ();
rtable_ent *prte;
int update_type;
Time next_possible = a->lasttup_ + DSDV_MIN_TUP_PERIOD;
for (a->table_->InitLoop(); (prte = a->table_->NextLoop());)
if (prte->trigger_event == e) break;
assert(prte && prte->trigger_event == e);
if (now < next_possible)
{
s.schedule(a->trigger_handler, e, next_possible - now);
a->cancelTriggersBefore(next_possible);
return;
}
update_type = 0;
Packet * p = a->makeUpdate(update_type);
if (p != NULL)
{
if (update_type == 1)
{
s.cancel(a->periodic_callback_);
s.schedule (a->helper_, a->periodic_callback_,
a->perup_ * (0.75 + jitter (0.25, a->be_random_)));
if (a->verbose_) a->tracepkt (p, now, a->myaddr_, "PU");
}
else
{
if (a->verbose_) a->tracepkt (p, now, a->myaddr_, "TU");
}
assert (!HDR_CMN (p)->xmit_failure_);
s.schedule (a->target_, p, jitter(DSDV_BROADCAST_JITTER, a->be_random_));
a->lasttup_ = now;
}
for (a->table_->InitLoop (); (prte = a->table_->NextLoop ());)
if (prte->trigger_event && prte->trigger_event == e)
{
prte->trigger_event = 0;
delete e;
}
}
void
DSDV_Agent::cancelTriggersBefore(Time t)
{TAKEN OUT CAUSE IT COULDNT FIT }
void
DSDV_Agent::needTriggeredUpdate(rtable_ent *prte, Time t)
{
TAKEN OUT CAUSE IT COULDNT FIT
}
void
DSDV_Agent::helper_callback (Event * e)
{
TAKEN OUT CAUSE IT COULDNT FIT}
void
DSDV_Agent::lost_link (Packet *p)
{
hdr_cmn *hdrc = HDR_CMN (p);
rtable_ent *prte = table_->GetEntry (hdrc->next_hop_);
if(use_mac_ == 0) {
drop(p, DROP_RTR_MAC_CALLBACK);
return;
}
if (verbose_ && hdrc->addr_type_ == NS_AF_INET)
trace("VLL %.8f %d->%d lost at %d",
Scheduler::instance().clock(),
hdr_ip::access(p)->saddr(), hdr_ip::access(p)->daddr(),
myaddr_);
if (!use_mac_ || !prte || hdrc->addr_type_ != NS_AF_INET)
return;
if (verbose_)
trace ("VLP %.5f %d:%d->%d:%d lost at %d [hop %d]",
Scheduler::instance ().clock (),
hdr_ip::access (p)->saddr(),
hdr_ip::access (p)->sport(),
hdr_ip::access (p)->daddr(),
hdr_ip::access (p)->dport(),
myaddr_, prte->dst);
if (prte->timeout_event)
{
Scheduler::instance ().cancel (prte->timeout_event);
helper_callback (prte->timeout_event);
}
else if (prte->metric != BIG)
{
assert(prte->timeout_event == 0);
prte->timeout_event = new Event ();
helper_callback (prte->timeout_event);
}
recv(p, 0);
#if 0
while (p2 = ((PriQueue *) target_)->filter (prte->dst))
{
if (verbose_)
trace ("VRS %.5f %d:%d->%d:%d lost at %d", Scheduler::instance ().clock (),
hdr_ip::access (p2)->saddr(),
hdr_ip::access (p2)->sport(),
hdr_ip::access (p2)->daddr(),
hdr_ip::access (p2)->dport(), myaddr_);
recv(p2, 0);
}
while (p2 = ll_queue->filter (prte->dst))
{
if (verbose_)
trace ("VRS %.5f %d:%d->%d:%d lost at %d", Scheduler::instance ().clock (),
hdr_ip::access (p2)->saddr(),
hdr_ip::access (p2)->sport(),
hdr_ip::access (p2)->daddr(),
hdr_ip::access (p2)->dport(), myaddr_);
recv (p2, 0);
}
#endif
}
static void
mac_callback (Packet * p, void *arg)
{
((DSDV_Agent *) arg)->lost_link (p);
}
Packet *
DSDV_Agent::makeUpdate(int& periodic)
{
Packet *p = allocpkt ();
hdr_ip *iph = hdr_ip::access(p);
hdr_cmn *hdrc = HDR_CMN (p);
double now = Scheduler::instance ().clock ();
rtable_ent *prte;
unsigned char *walk;
int change_count;
int rtbl_sz;
int unadvertiseable;
hdrc->next_hop_ = IP_BROADCAST;
hdrc->addr_type_ = NS_AF_INET;
iph->daddr() = IP_BROADCAST << Address::instance().nodeshift();
iph->dport() = ROUTER_PORT;
change_count = 0;
rtbl_sz = 0;
unadvertiseable = 0;
for (table_->InitLoop ();
(prte = table_->NextLoop ()); )
{
rtbl_sz++;
if ((prte->advert_seqnum || prte->advert_metric)
&& prte->advertise_ok_at <= now)
change_count++;
if (prte->advertise_ok_at > now) unadvertiseable++;
}
if (change_count * 3 > rtbl_sz && change_count > 3)
{
periodic = 1;
}
if (periodic)
{
change_count = rtbl_sz - unadvertiseable;
rtable_ent rte;
bzero(&rte, sizeof(rte));
seqno_ += 2;
rte.dst = myaddr_;
rte.hop = Address::instance().get_nodeaddr(iph->saddr());
rte.metric = 0;
rte.seqnum = seqno_;
rte.advertise_ok_at = 0.0;
rte.advert_seqnum = true;
rte.changed_at = now;
rte.new_seqnum_at = now;
rte.wst = 0;
rte.timeout_event = 0;
rte.q = 0;
table_->AddEntry (rte);
}
if (change_count == 0)
{
Packet::free(p);
return NULL;
}
p->allocdata((change_count * 9) + 1);
walk = p->accessdata ();
*(walk++) = change_count;
hdrc->size_ = change_count * 12 + IP_HDR_LEN;
for (table_->InitLoop (); (prte = table_->NextLoop ());)
{
if (periodic && prte->advertise_ok_at > now)
{ }
if (periodic ||
((prte->advert_seqnum || prte->advert_metric)
&& prte->advertise_ok_at <= now))
{
if (!periodic && verbose_)
trace ("VCT %.5f _%d_ %d", now, myaddr_, prte->dst);
*(walk++) = prte->dst >> 24;
*(walk++) = (prte->dst >> 16) & 0xFF;
*(walk++) = (prte->dst >> 8) & 0xFF;
*(walk++) = (prte->dst >> 0) & 0xFF;
*(walk++) = prte->metric;
*(walk++) = (prte->seqnum) >> 24;
*(walk++) = ((prte->seqnum) >> 16) & 0xFF;
*(walk++) = ((prte->seqnum) >> 8) & 0xFF;
*(walk++) = (prte->seqnum) & 0xFF;
prte->last_advertised_metric = prte->metric;
prte->advert_seqnum = false;
if (periodic)
{
prte->advert_seqnum = false;
prte->advert_metric = false;
}
change_count--;
}
}
assert(change_count == 0);
return p;
}
void
DSDV_Agent::updateRoute(rtable_ent *old_rte, rtable_ent *new_rte)
{
int negvalue = -1;
assert(new_rte);
Time now = Scheduler::instance().clock();
char buf[1024];
snprintf (buf, 1024, "%c %.5f _%d_ (%d,%d->%d,%d->%d,%d->%d,%f)",
(new_rte->metric != BIG
&& (!old_rte || old_rte->metric != BIG)) ? 'D' : 'U',
now, myaddr_, new_rte->dst,
old_rte ? old_rte->metric : negvalue, new_rte->metric,
old_rte ? old_rte->seqnum : negvalue, new_rte->seqnum,
old_rte ? old_rte->hop : -1, new_rte->hop,
new_rte->advertise_ok_at);
table_->AddEntry (*new_rte);
if (trace_wst_)
trace ("VWST %.12lf frm %d to %d wst %.12lf nxthp %d [of %d]",
now, myaddr_, new_rte->dst, new_rte->wst, new_rte->hop,
new_rte->metric);
if (verbose_)
trace ("VS%s", buf);
}
void
DSDV_Agent::processUpdate (Packet * p)
{
hdr_ip *iph = HDR_IP(p);
Scheduler & s = Scheduler::instance ();
double now = s.clock ();
int i;
unsigned char *d = p->accessdata ();
unsigned char *w = d + 1;
rtable_ent rte;
rtable_ent *prte;
for (i = *d; i > 0; i--)
{
bool trigger_update = false;
nsaddr_t dst;
prte = NULL;
dst = *(w++);
dst = dst << 8 | *(w++);
dst = dst << 8 | *(w++);
dst = dst << 8 | *(w++);
if ((prte = table_->GetEntry (dst)))
{
bcopy(prte, &rte, sizeof(rte));
}
else
{
bzero(&rte, sizeof(rte));
}
rte.dst = dst;
rte.hop = Address::instance().get_nodeaddr(iph->saddr());
rte.metric = *(w++);
rte.seqnum = *(w++);
rte.seqnum = rte.seqnum << 8 | *(w++);
rte.seqnum = rte.seqnum << 8 | *(w++);
rte.seqnum = rte.seqnum << 8 | *(w++);
rte.changed_at = now;
if (rte.metric != BIG) rte.metric += 1;
if (rte.dst == myaddr_)
{
if (rte.metric == BIG && periodic_callback_)
{
s.cancel (periodic_callback_);
s.schedule (helper_, periodic_callback_, 0);
}
}
if (prte)
{
if (prte->seqnum == rte.seqnum)
{ rte.wst = prte->wst;
rte.new_seqnum_at = prte->new_seqnum_at;
}
else
{
rte.wst = alpha_ * prte->wst +
(1.0 - alpha_) * (prte->changed_at - prte->new_seqnum_at);
rte.new_seqnum_at = now;
}
}
else
{
rte.wst = wst0_;
rte.new_seqnum_at = now;
}
if (rte.metric != BIG && (!prte || prte->metric != BIG))
rte.advertise_ok_at = now + (rte.wst * 2);
else
rte.advertise_ok_at = now;
if (!prte)
{
if (rte.metric < BIG)
{
rte.advert_metric = true;
trigger_update = true;
}
updateRoute(prte,&rte);
}
else if ( prte->seqnum == rte.seqnum )
{
if (rte.metric < prte->metric)
{
if (rte.metric == prte->last_advertised_metric)
{ advertised
rte.advert_metric = false;
trigger_update = false;
}
else
{
rte.advert_metric = true;
trigger_update = true;
}
updateRoute(prte,&rte);
}
else
{
}
}
else if ( prte->seqnum < rte.seqnum )
{ rte.advert_seqnum = true;
if (rte.metric == prte->last_advertised_metric)
{
rte.advert_metric = false;
}
else
{
rte.advert_metric = true;
}
updateRoute(prte,&rte);
#ifdef TRIGGER_UPDATE_ON_FRESH_SEQNUM
trigger_update = true;
#else
trigger_update = false;
#endif
}
else if ( prte->seqnum > rte.seqnum )
{
if (rte.metric == BIG && prte->metric != BIG)
{
prte->advertise_ok_at = now;
prte->advert_metric = true;
needTriggeredUpdate(prte,now);
}
else
{
}
}
else
{
fprintf(stderr,
"%s DFU: unhandled adding a route entry?\n", __FILE__);
abort();
}
if (trigger_update)
{
prte = table_->GetEntry (rte.dst);
assert(prte != NULL && prte->advertise_ok_at == rte.advertise_ok_at);
needTriggeredUpdate(prte, prte->advertise_ok_at);
}
if (rte.q && rte.metric != BIG)
{
Packet *queued_p;
while ((queued_p = rte.q->deque()))
recv(queued_p, 0);
delete rte.q;
rte.q = 0;
table_->AddEntry(rte);
}
}
prte = table_->GetEntry(Address::instance().get_nodeaddr(iph->saddr()));
if (prte)
{
if (prte->timeout_event)
s.cancel (prte->timeout_event);
else
{
prte->timeout_event = new Event ();
}
s.schedule (helper_, prte->timeout_event, min_update_periods_ * perup_);
}
else
{
bzero(&rte, sizeof(rte));
rte.dst = Address::instance().get_nodeaddr(iph->saddr());
rte.hop = Address::instance().get_nodeaddr(iph->saddr());
rte.metric = 1;
rte.seqnum = 0;
rte.advertise_ok_at = now + 604800;
rte.changed_at = now;
rte.new_seqnum_at = now;
rte.wst = wst0_;
rte.timeout_event = new Event ();
rte.q = 0;
updateRoute(NULL, &rte);
s.schedule(helper_, rte.timeout_event, min_update_periods_ * perup_);
}
Packet::free (p);
}
int
DSDV_Agent::diff_subnet(int dst)
{TAKEN OUT CAUSE IT COULDNT FIT}
void
DSDV_Agent::forwardPacket (Packet * p)
{
hdr_ip *iph = HDR_IP(p);
Scheduler & s = Scheduler::instance ();
double now = s.clock ();
hdr_cmn *hdrc = HDR_CMN (p);
int dst;
rtable_ent *prte;
hdrc->direction() = hdr_cmn::DOWN;
dst = Address::instance().get_nodeaddr(iph->daddr());
if (diff_subnet(iph->daddr())) {
prte = table_->GetEntry (dst);
if (prte && prte->metric != BIG)
goto send;
dst = node_->base_stn();
prte = table_->GetEntry (dst);
if (prte && prte->metric != BIG)
goto send;
else {
fprintf(stderr, "warning: Route to base_stn not known: dropping pkt\n");
Packet::free(p);
return;
}
}
prte = table_->GetEntry (dst);
if (prte && prte->metric != BIG)
{
goto send;
}
else if (prte)
{
if (!prte->q)
{
prte->q = new PacketQueue ();
}
prte->q->enque(p);
if (verbose_)
trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->saddr(),
iph->sport(), iph->daddr(), iph->dport());
while (prte->q->length () > MAX_QUEUE_LENGTH)
drop (prte->q->deque (), DROP_RTR_QFULL);
return;
}
else
{
rtable_ent rte;
double now = s.clock();
bzero(&rte, sizeof(rte));
rte.dst = dst;
rte.hop = dst;
rte.metric = BIG;
rte.seqnum = 0;
rte.advertise_ok_at = now + 604800;
rte.changed_at = now;
rte.new_seqnum_at = now;
rte.wst = wst0_;
rte.timeout_event = 0;
rte.q = new PacketQueue();
rte.q->enque(p);
assert (rte.q->length() == 1 && 1 <= MAX_QUEUE_LENGTH);
table_->AddEntry(rte);
if (verbose_)
trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_,
iph->saddr(), iph->sport(), iph->daddr(), iph->dport());
return;
}
send:
hdrc->addr_type_ = NS_AF_INET;
hdrc->xmit_failure_ = mac_callback;
hdrc->xmit_failure_data_ = this;
if (prte->metric > 1)
hdrc->next_hop_ = prte->hop;
else
hdrc->next_hop_ = dst;
if (verbose_)
trace ("Routing pkts outside domain:
VFP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->saddr(),
iph->sport(), iph->daddr(), iph->dport());
assert (!HDR_CMN (p)->xmit_failure_ ||
HDR_CMN (p)->xmit_failure_ == mac_callback);
target_->recv(p, (Handler *)0);
return;
}
void
DSDV_Agent::sendOutBCastPkt(Packet *p)
{
Scheduler & s = Scheduler::instance ();
s.schedule (target_, p, jitter(DSDV_BROADCAST_JITTER, be_random_));
}
void
DSDV_Agent::recv (Packet * p, Handler *)
{
hdr_ip *iph = HDR_IP(p);
hdr_cmn *cmh = HDR_CMN(p);
int src = Address::instance().get_nodeaddr(iph->saddr());
if(src == myaddr_ && cmh->num_forwards() == 0) {
cmh->size() += IP_HDR_LEN;
iph->ttl_ = IP_DEF_TTL;
}
else if(src == myaddr_) {
drop(p, DROP_RTR_ROUTE_LOOP);
return;
}
else {
if(--iph->ttl_ == 0) {
drop(p, DROP_RTR_TTL);
return;
}
}
if ((src != myaddr_) && (iph->dport() == ROUTER_PORT))
{
processUpdate(p);
}
else if (iph->daddr() == ((int)IP_BROADCAST) &&
(iph->dport() != ROUTER_PORT))
{
if (src == myaddr_) {
sendOutBCastPkt(p);
}
else {
port_dmux_->recv(p, (Handler*)0);
}
}
else
{
forwardPacket(p);
}
}
static class DSDVClass:public TclClass
{
public:
DSDVClass ():TclClass ("Agent/DSDV")
{
}
TclObject *create (int, const char *const *)
{
return (new DSDV_Agent ());
}
} class_dsdv;
DSDV_Agent::DSDV_Agent (): Agent (PT_MESSAGE), ll_queue (0), seqno_ (0),
myaddr_ (0), subnet_ (0), node_ (0), port_dmux_(0),
periodic_callback_ (0), be_random_ (1),
use_mac_ (0), verbose_ (1), trace_wst_ (0), lasttup_ (-10),
alpha_ (0.875), wst0_ (6), perup_ (15),
min_update_periods_ (3)
{
table_ = new RoutingTable ();
helper_ = new DSDV_Helper (this);
trigger_handler = new DSDVTriggerHandler(this);
bind_time ("wst0_", &wst0_);
bind_time ("perup_", &perup_);
bind ("use_mac_", &use_mac_);
bind ("be_random_", &be_random_);
bind ("alpha_", &alpha_);
bind ("min_update_periods_", &min_update_periods_);
bind ("verbose_", &verbose_);
bind ("trace_wst_", &trace_wst_);
address = 0;
}
void
DSDV_Agent::startUp()
{TAKEN OUT CAUSE IT COULDNT FIT}
int
DSDV_Agent::command (int argc, const char *const *argv)
{
if (argc == 2)
{
if (strcmp (argv[1], "start-dsdv") == 0)
{
startUp();
return (TCL_OK);
}
else if (strcmp (argv[1], "dumprtab") == 0)
{
Packet *p2 = allocpkt ();
hdr_ip *iph2 = HDR_IP(p2);
rtable_ent *prte;
printf ("Table Dump %d[%d]\n---\n",
iph2->saddr(), iph2->sport());
trace ("VTD %.5f %d:%d\n", Scheduler::instance ().clock (),
iph2->saddr(), iph2->sport());
Packet::free (p2);
for (table_->InitLoop (); (prte = table_->NextLoop ());)
output_rte ("\t", prte, this);
printf ("\n");
return (TCL_OK);
}
else if (strcasecmp (argv[1], "ll-queue") == 0)
{
if (!(ll_queue = (PriQueue *) TclObject::lookup (argv[2])))
{
fprintf (stderr, "DSDV_Agent: ll-queue lookup of %s failed\n", argv[2]);
return TCL_ERROR;
}
return TCL_OK;
}
}
else if (argc == 3)
{
if (strcasecmp (argv[1], "addr") == 0) {
int temp;
temp = Address::instance().str2addr(argv[2]);
myaddr_ = temp;
return TCL_OK;
}
TclObject *obj;
if ((obj = TclObject::lookup (argv[2])) == 0)
{
fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__, argv[1],
argv[2]);
return TCL_ERROR;
}
if (strcasecmp (argv[1], "tracetarget") == 0)
{
tracetarget = (Trace *) obj;
return TCL_OK;
}
else if (strcasecmp (argv[1], "node") == 0) {
node_ = (MobileNode*) obj;
return TCL_OK;
}
else if (strcasecmp (argv[1], "port-dmux") == 0) {
port_dmux_ = (NsObject *) obj;
return TCL_OK;
}
}
return (Agent::command (argc, argv));
}