/* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
* Copyright (c) 1999 Regents of the University of California.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the MASH Research
* Group at the University of California Berkeley.
* 4. Neither the name of the University nor of the Research Group may be
* used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* Contributed by Tom Henderson, UCB Daedalus Research Group, June 1999
*/
#ifndef lint
static const char rcsid[] =
"@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/satellite/satroute.cc,v 1.13 2005/05/19 03:19:02 tomh Exp $";
#endif
#include "satroute.h"
#include "sattrace.h"
#include "satnode.h"
#include "satlink.h"
#include "route.h"
#include <address.h>
static class SatRouteClass:public TclClass
{
public:
SatRouteClass ():TclClass ("Agent/SatRoute") { }
TclObject *create (int, const char *const *) {
return (new SatRouteAgent ());
}
} class_satroute;
SatRouteAgent::SatRouteAgent (): Agent (PT_MESSAGE), maxslot_(0), nslot_(0), slot_(0)
{
bind ("myaddr_", &myaddr_);
}
SatRouteAgent::~SatRouteAgent()
{
if (slot_)
delete [] slot_;
}
void SatRouteAgent::alloc(int slot)
{
slot_entry *old = slot_;
int n = nslot_;
if (old == 0)
nslot_ = 32;
while (nslot_ <= slot)
nslot_ <<= 1;
slot_ = new slot_entry[nslot_];
memset(slot_, 0, nslot_ * sizeof(slot_entry));
for (int i = 0; i < n; ++i) {
slot_[i].next_hop = old[i].next_hop;
slot_[i].entry = old[i].entry;
}
delete [] old;
}
void SatRouteAgent::install(int slot, int nh, NsObject* p)
{
if (slot >= nslot_)
alloc(slot);
slot_[slot].next_hop = nh;
slot_[slot].entry = p;
if (slot >= maxslot_)
maxslot_ = slot;
}
void SatRouteAgent::clear_slots()
{
if (slot_)
delete [] slot_;
slot_ = 0;
nslot_ = 0;
maxslot_ = -1;
}
int SatRouteAgent::command (int argc, const char *const *argv)
{
Tcl& tcl = Tcl::instance();
if (argc == 2) {
}
if (argc == 3) {
if (strcmp(argv[1], "set_node") == 0) {
node_ = (SatNode *) TclObject::lookup(argv[2]);
if (node_ == 0) {
tcl.resultf("no such object %s", argv[2]);
return (TCL_ERROR);
}
return (TCL_OK);
}
}
return (Agent::command (argc, argv));
}
/*
* Find a target for the received packet
*/
void SatRouteAgent::forwardPacket(Packet * p)
{
hdr_ip *iph = hdr_ip::access(p);
hdr_cmn *hdrc = HDR_CMN (p);
NsObject *link_entry_;
hdrc->direction() = hdr_cmn::DOWN; // send it down the stack
int dst = Address::instance().get_nodeaddr(iph->daddr());
// Here we need to have an accurate encoding of the next hop routing
// information
if (myaddr_ == iph->daddr()) {
printf("Error: trying to forward a packet destined to self: %d\n", myaddr_);
Packet::free(p);
}
hdrc->addr_type_ = NS_AF_INET;
hdrc->last_hop_ = myaddr_; // for tracing purposes
if (SatRouteObject::instance().data_driven_computation())
SatRouteObject::instance().recompute_node(myaddr_);
if (SatNode::dist_routing_ == 0) {
if (slot_ == 0) { // No routes to anywhere
if (node_->trace())
node_->trace()->traceonly(p);
Packet::free(p);
return;
}
link_entry_ = slot_[dst].entry;
if (link_entry_ == 0) {
if (node_->trace())
node_->trace()->traceonly(p);
Packet::free(p);
return;
}
hdrc->next_hop_ = slot_[dst].next_hop;
link_entry_->recv(p, (Handler *)0);
return;
} else {
// DISTRIBUTED ROUTING LOOKUP COULD GO HERE
printf("Error: distributed routing not available\n");
exit(1);
}
}
void SatRouteAgent::recv (Packet * p, Handler *)
{
hdr_ip *iph = hdr_ip::access(p);
hdr_cmn *cmh = hdr_cmn::access(p);
if (iph->saddr() == myaddr_ && cmh->num_forwards() == 0) {
// Must be a packet I'm originating... add the IP header
iph->ttl_ = IP_DEF_TTL;
} else if (iph->saddr() == myaddr_) {
// I received a packet that I sent. Probably a routing loop.
Packet::free(p);
return;
} else {
// Packet I'm forwarding...
// Check the TTL. If it is zero, then discard.
if(--iph->ttl_ == 0) {
Packet::free(p);
return;
}
}
if ((iph->saddr() != myaddr_) && (iph->dport() == ROUTER_PORT)) {
// DISTRIBUTED ROUTING PROTOCOL COULD GO HERE
printf("Error: distributed routing not available\n");
exit(1);
} else {
forwardPacket(p);
}
}
//###########################################################################
static class SatRouteObjectClass:public TclClass
{
public:
SatRouteObjectClass ():TclClass ("SatRouteObject") { }
TclObject *create (int, const char *const *) {
return (new SatRouteObject ());
}
} class_satrouteobject;
SatRouteObject* SatRouteObject::instance_;
SatRouteObject::SatRouteObject() : suppress_initial_computation_(0)
{
bind_bool("wiredRouting_", &wiredRouting_);
bind_bool("metric_delay_", &metric_delay_);
bind_bool("data_driven_computation_", &data_driven_computation_);
}
int SatRouteObject::command (int argc, const char *const *argv)
{
if (instance_ == 0)
instance_ = this;
if (argc == 2) {
// While suppress_initial_computation_ may seem more
// appropriate as a bound variable, it is useful to
// implement the setting of this variable this way so that
// the ``instance_ = this'' assignment is made at the
// start of simulation.
if (strcmp(argv[1], "suppress_initial_computation") == 0) {
suppress_initial_computation_ = 1;
return (TCL_OK);
}
if (strcmp(argv[1], "compute_routes") == 0) {
recompute();
return (TCL_OK);
}
if (strcmp(argv[1], "dump") == 0) {
printf("Dumping\n");
dump();
return (TCL_OK);
}
}
return (RouteLogic::command(argc, argv));
}
// Wrapper to catch whether OTcl-based (wired-satellite) routing is enabled
void SatRouteObject::insert_link(int src, int dst, double cost)
{
if (wiredRouting_) {
Tcl::instance().evalf("[Simulator instance] sat_link_up %d %d %f", (src - 1), (dst - 1), cost);
} else
insert(src, dst, cost);
}
// Wrapper to catch whether OTcl-based (wired) routing is enabled
void SatRouteObject::insert_link(int src, int dst, double cost, void* entry)
{
SatLinkHead* slhp = (SatLinkHead*) entry;
if (wiredRouting_) {
// Here we do an upcall to an instproc in ns-sat.tcl
// that populates the link_(:) array
Tcl::instance().evalf("[Simulator instance] sat_link_up %d %d %f %s %s", (src - 1), (dst - 1), cost, slhp->name(), slhp->queue()->name());
} else
insert(src, dst, cost, entry); // base class insert()
}
void SatRouteObject::recompute_node(int node)
{
compute_topology();
node_compute_routes(node);
populate_routing_tables(node);
}
void SatRouteObject::recompute()
{
// For very large topologies (e.g., Teledesic), we don't want to
// waste a lot of time computing routes at the beginning of the
// simulation. This first if() clause suppresses route computations.
if (data_driven_computation_ ||
(NOW < 0.001 && suppress_initial_computation_) )
return;
else {
compute_topology();
if (wiredRouting_) {
Tcl::instance().evalf("[Simulator instance] compute-flat-routes");
} else {
compute_routes(); // base class function
}
populate_routing_tables();
}
}
// Derives link adjacency information from the nodes and gives the current
// topology information to the RouteLogic.
void SatRouteObject::compute_topology()
{
Node *nodep;
Phy *phytxp, *phyrxp, *phytxp2, *phyrxp2;
SatLinkHead *slhp;
Channel *channelp, *channelp2;
int src, dst;
double delay;
// wired-satellite integration
if (wiredRouting_) {
// There are two route objects being used
// a SatRouteObject and a RouteLogic (for wired)
// We need to also reset the RouteLogic one
Tcl::instance().evalf("[[Simulator instance] get-routelogic] reset");
}
reset_all();
// Compute adjacencies. Traverse linked list of nodes
for (nodep=Node::nodehead_.lh_first; nodep; nodep = nodep->nextnode()) {
// Cycle through the linked list of linkheads
if (!SatNode::IsASatNode(nodep->address()))
continue;
for (slhp = (SatLinkHead*) nodep->linklisthead().lh_first; slhp;
slhp = (SatLinkHead*) slhp->nextlinkhead()) {
if (slhp->type() == LINK_GSL_REPEATER)
continue;
if (!slhp->linkup_)
continue;
phytxp = (Phy *) slhp->phy_tx();
assert(phytxp);
channelp = phytxp->channel();
if (!channelp)
continue; // Not currently connected to channel
// Next, look for receive interfaces on this channel
phyrxp = channelp->ifhead_.lh_first;
for (; phyrxp; phyrxp = phyrxp->nextchnl()) {
if (phyrxp == phytxp) {
printf("Configuration error: a transmit interface \
is a channel target\n");
exit(1);
}
if (phyrxp->head()->type() == LINK_GSL_REPEATER) {
double delay_firsthop = ((SatChannel*)
channelp)->get_pdelay(phytxp->node(),
phyrxp->node());
if (!((SatLinkHead*)phyrxp->head())->linkup_)
continue;
phytxp2 = ((SatLinkHead*)phyrxp->head())->phy_tx();
channelp2 = phytxp2->channel();
if (!channelp2)
continue; // Not currently connected to channel
phyrxp2 = channelp2->ifhead_.lh_first;
for (; phyrxp2; phyrxp2 = phyrxp2->nextchnl()) {
if (phyrxp2 == phytxp2) {
printf("Config error: a transmit interface \
is a channel target\n");
exit(1);
}
// Found an adjacency relationship.
// Add this link to the RouteLogic
src = phytxp->node()->address() + 1;
dst = phyrxp2->node()->address() + 1;
if (src == dst)
continue;
if (metric_delay_)
delay = ((SatChannel*)
channelp2)->get_pdelay(phytxp2->node(),
phyrxp2->node());
else {
delay = 1;
delay_firsthop = 0;
}
insert_link(src, dst, delay+delay_firsthop, (void*)slhp);
}
} else {
// Found an adjacency relationship.
// Add this link to the RouteLogic
src = phytxp->node()->address() + 1;
dst = phyrxp->node()->address() + 1;
if (metric_delay_)
delay = ((SatChannel*)
channelp)->get_pdelay(phytxp->node(),
phyrxp->node());
else
delay = 1;
insert_link(src, dst, delay, (void*)slhp);
}
}
}
}
//dump();
}
void SatRouteObject::populate_routing_tables(int node)
{
SatNode *snodep = (SatNode*) Node::nodehead_.lh_first;
SatNode *snodep2;
int next_hop, src, dst;
NsObject *target;
if (wiredRouting_) {
Tcl::instance().evalf("[Simulator instance] populate-flat-classifiers [Node set nn_]");
return;
}
for (; snodep; snodep = (SatNode*) snodep->nextnode()) {
if (!SatNode::IsASatNode(snodep->address()))
continue;
// First, clear slots of the current routing table
if (snodep->ragent())
snodep->ragent()->clear_slots();
src = snodep->address();
if (node != -1 && node != src)
continue;
snodep2 = (SatNode*) Node::nodehead_.lh_first;
for (; snodep2; snodep2 = (SatNode*) snodep2->nextnode()) {
if (!SatNode::IsASatNode(snodep->address()))
continue;
dst = snodep2->address();
next_hop = lookup(src, dst);
if (next_hop != -1 && src != dst) {
// Here need to insert target into slot table
target = (NsObject*) lookup_entry(src, dst);
if (target == 0) {
printf("Error, routelogic target ");
printf("not populated %f\n", NOW);
exit(1);
}
((SatNode*)snodep)->ragent()->install(dst,
next_hop, target);
}
}
}
}
int SatRouteObject::lookup(int s, int d)
{
int src = s + 1;
int dst = d + 1;
if (src >= size_ || dst >= size_) {
return (-1); // Next hop = -1
}
return (route_[INDEX(src, dst, size_)].next_hop - 1);
}
void* SatRouteObject::lookup_entry(int s, int d)
{
int src = s + 1;
int dst = d + 1;
if (src >= size_ || dst >= size_) {
return (0); // Null pointer
}
return (route_[INDEX(src, dst, size_)].entry);
}
// This method is used for debugging only
void SatRouteObject::dump()
{
int i, src, dst;
for (i = 0; i < (size_ * size_); i++) {
if (adj_[i].cost != SAT_ROUTE_INFINITY) {
src = i / size_ - 1;
dst = i % size_ - 1;
printf("Found a link from %d to %d with cost %f\n", src, dst, adj_[i].cost);
}
}
}
void SatRouteObject::node_compute_routes(int node)
{
int n = size_;
int* parent = new int[n];
double* hopcnt = new double[n];
#define ADJ(i, j) adj_[INDEX(i, j, size_)].cost
#define ADJ_ENTRY(i, j) adj_[INDEX(i, j, size_)].entry
#define ROUTE(i, j) route_[INDEX(i, j, size_)].next_hop
#define ROUTE_ENTRY(i, j) route_[INDEX(i, j, size_)].entry
delete[] route_;
route_ = new route_entry[n * n];
memset((char *)route_, 0, n * n * sizeof(route_[0]));
/* compute routes only for node "node" */
int k = node + 1; // must add one to get the right offset in tables
int v;
for (v = 0; v < n; v++)
parent[v] = v;
/* set the route for all neighbours first */
for (v = 1; v < n; ++v) {
if (parent[v] != k) {
hopcnt[v] = ADJ(k, v);
if (hopcnt[v] != SAT_ROUTE_INFINITY) {
ROUTE(k, v) = v;
ROUTE_ENTRY(k, v) = ADJ_ENTRY(k, v);
}
}
}
for (v = 1; v < n; ++v) {
/*
* w is the node that is the nearest to the subtree
* that has been routed
*/
int o = 0;
/* XXX */
hopcnt[0] = SAT_ROUTE_INFINITY;
int w;
for (w = 1; w < n; w++)
if (parent[w] != k && hopcnt[w] < hopcnt[o])
o = w;
parent[o] = k;
/*
* update distance counts for the nodes that are
* adjacent to o
*/
if (o == 0)
continue;
for (w = 1; w < n; w++) {
if (parent[w] != k &&
hopcnt[o] + ADJ(o, w) < hopcnt[w]) {
ROUTE(k, w) = ROUTE(k, o);
ROUTE_ENTRY(k, w) =
ROUTE_ENTRY(k, o);
hopcnt[w] = hopcnt[o] + ADJ(o, w);
}
}
}
/*
* The route to yourself is yourself.
*/
ROUTE(k, k) = k;
ROUTE_ENTRY(k, k) = 0; // This should not matter
delete[] hopcnt;
delete[] parent;
}
syntax highlighted by Code2HTML, v. 0.9.1