satroute.cc

Go to the documentation of this file.

/* -*-  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.12 2001/11/06 06:21:47 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 != 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] != 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] = 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;
}

---