routing-module.cc

/*
 * Copyright (c) 2008 Regents of the SIGNET lab, University of Padova.
 * 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. Neither the name of the University of Padova (SIGNET lab) nor the 
 *    names of its contributors may be used to endorse or promote products 
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER 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.
 */

#include "routing-module.h"
#include<ip.h>



RouteReachable::RouteReachable(int source) : ClMessage(ROUTEREACHABLE_VERBOSITY, CL_ROUTEMESSAGE, UNICAST, 0), info_(0), nInfo_(0), infoLen_(0), modules_(0), nModules_(0), myIP_(0), processed_(0)
{
        memset(addr_, 0, MRCL_ADDRESS_MAX_LEN);
        setSource(source);
}

RouteReachable::~RouteReachable()
{
        if(infoLen_)
                delete [] info_;
}

void RouteReachable::setAddress(char *a)
{
        MrclAddress::storeAddr(addr_, a);
}

char *RouteReachable::getAddress()
{
        return addr_;
}

void RouteReachable::addRouteInfo(RouteInfo *i)
{
        int id = i->getModuleId();
        if(id < nModules_ && modules_[id]>=0)
        {
                info_[modules_[id]] = i;
                return;
        }
        if(nInfo_ >= infoLen_)
        {
                RouteInfo **tmp = new RouteInfo*[infoLen_ + ROUTE_REACHABLE_ALLOC_INFO_PER_TIME];
                for(int j = 0; j < infoLen_; j++)
                {
                        if(j < nInfo_)
                                tmp[j] = info_[j];
                }
                if(infoLen_ > 0)
                        delete [] info_;
                info_ = tmp;
                infoLen_ += ROUTE_REACHABLE_ALLOC_INFO_PER_TIME;
        }
        //printf("ninfo %d infoLen %d Nmetric %d \n", nInfo_, infoLen_, i->getNMetric());
        info_[nInfo_++] = i;
        //int id = i->getModuleId();
        if(id >= nModules_)
        {
                int *tmp = new int[id + 1];
                for(int j = 0; j <= id; j++)
                {
                        if(j < nModules_)
                                tmp[j] = modules_[j];
                        else
                                tmp[j] = -1;
                }
                if(nModules_ > 0)
                        delete [] modules_;
                modules_ = tmp;
                nModules_ = id + 1;
        }
        modules_[id] = nInfo_ - 1;
        //printf("Updated modules[%d] = %d\n", id, nInfo_ -1);
}

int RouteReachable::length()
{
        return nInfo_;
}

RouteInfo *RouteReachable::getRouteInfo(int id)
{
//      printf("asks for routeInfo %d nModules_%d \n", id, nModules_);
        if(id >= nModules_)
                return 0;
        int i = modules_[id];
//      printf("module_[%d] %d\n", id, modules_[id]);
        if(i < 0)
                return 0;
//      printf("info_[i] %p\n", info_[i]);
        return info_[i];
}

RouteInfo **RouteReachable::getRouteInfo()
{
        return info_;
}

void RouteReachable::empty()
{
        memset(info_, 0, sizeof(RouteInfo) * nInfo_);
        myIP_ = 0;
        nInfo_ = 0;
        for(int j = 0; j < nModules_; j++)
                modules_[j] = -1;
}

void RouteReachable::setMyIP()
{
        myIP_ = 1;
}

int RouteReachable::isMyIP()
{
        return myIP_;
}

void RouteReachable::processed(int value)
{
        processed_ = value;
}

int RouteReachable::processed()
{
        return processed_;
}

int RouteReachable::getIndex(int id)
{
        if(id >= nModules_)
                return -1;
        return modules_[id];
}

// RouteReachableTracer::RouteReachableTracer() : ClMessageTracer(CL_ROUTEMESSAGE)
// {
// }
// 
// void RouteReachableTracer::format(ClMessage *m, ClSAP *sap)
// {
//      if (m->type()!=CL_ROUTEMESSAGE)
//              return;
//      
//      writeTrace(sap, " [CL_ROUTE_MSG] ");
// }




MrclRouting::MrclRouting() : rr_(0), lastGetConfiguration_(-1), delayUp_(0.0), delayDown_(0.0), nAddresses_(0)
{
        bind("overheadLength_", &overheadLength_);
}

MrclRouting::~MrclRouting()
{
        if(rr_)
                delete rr_;
}

int MrclRouting::command(int argc, const char *const* argv)
{
        Tcl& tcl = Tcl::instance();
        if(argc == 3)
        {
                if(strcasecmp(argv[1], "id_") == 0)
                {
                        int id = atoi(argv[2]);
                        rr_ = new RouteReachable(id);
                }
                else if (strcasecmp(argv[1],"getAddr")==0)
                {
                        int addrNum = atoi(argv[2]);
                        if (addrNum-1>nAddresses())
                        {
                                printf("Error AodvModule %s command, ask for an unexisting address (%d, while max is %d)\n", argv[1], addrNum, nAddresses());
                                return TCL_ERROR;
                        }
                        MrclAddress *addr = getAddress(addrNum-1);
                        if (addr==0)
                                return TCL_ERROR;
                        int len = addr->strlen() + 2;
                        char *str = new char[len];
                        addr->toString(str, len);
                        tcl.resultf("%s", str);
                        return TCL_OK;
                }
                else    if (strcasecmp(argv[1],"setAddr")==0)
                {
                        MrclAddress *addr = (MrclAddress *)(TclObject::lookup(argv[2]));
                        if (addr==0)
                        {
                                printf("AodvModule::command(%s), error in address lookup\n", argv[1]);
                                return TCL_ERROR;
                        }
                        int len = addr->strlen() + 2;
                        char *str = new char[len];
                        addr->toString(str, len);
                        addAddress(addr);
                        if(debug_>5)
                        {
                                printf("AodvModule::command(%s) -- setAddr(%d) = %s\n", argv[1], nAddresses(), str);
                        }
                        return TCL_OK;
                }
        }
        return Module::command(argc, argv);
}

int MrclRouting::getConfiguration(char *a, int source)
{
        for(int i = 0; i < nAddresses_; i++)
        {
                if(MrclAddress::areEqual(a, addresses_[i]->getAddr()))
                {
                        return -1;
                }
        }
        if(source < 0)
                rr_->empty();
        rr_->setAddress(a);
        Metric **m;
        int r = canIReach(a, &m);
        RouteInfo *i = new RouteInfo();
        i->setModuleId(getId());
        if(r != 0)
        {
                if(r > 0)
                {
                        i->setReachability(REACHABLE);
                }
                else
                {
                        i->setReachability(MAYBE);
                        r *= -1;
                }

                for(int j = 0; j < r; j++)
                {
                        i->addMetric(m[j]);
                }
        }
        else
        {
                i->setReachability(UNREACHABLE);        
        }
        //printf("Module %d addRouteInfo\n", getId());
        rr_->addRouteInfo(i);
        for(int j = 0; j < getUpLaySAPnum(); j++)
        {
                int id = getUpLaySAP(j)->getModuleUpId();
//              printf("Try to upSAP %d module %d source %d\n", j, id, source);
                if(id != source)
                {
                        rr_->processed(0);
//                      printf("Try to send to %d\n", id);
                        rr_->setDest(id);
                        sendSyncClMsgUp(rr_);
                        if(rr_->isMyIP())
                        {
                                return -1;
                        }
                }
                if(rr_->processed() || (id >= 0 && id == source))
                {
                        printf("\t\t\tmodule %d addfather %d (source=%d) %p\n",getId(),id,source, rr_->getRouteInfo(id));
                        rr_->getRouteInfo(getId())->addFather(rr_->getRouteInfo(id));
                }
//              else
//              {
//                      printf("RM %d module %d is not a father :-(\n", getId(), getDownLaySAP(j)->getModuleUpId());
//              }
        }
        for(int j = 0; j < getDownLaySAPnum(); j++)
        {
                int id = getDownLaySAP(j)->getModuleDownId();
                if(id != source)
                {
                        rr_->processed(0);
                        rr_->setDest(id);
                        sendSyncClMsgDown(rr_);
                        if(rr_->isMyIP())
                        {
                                return -1;
                        }
                }
                if(rr_->processed() || (id >= 0 && id == source))
                {
                        //printf("\t\t\tmodule %d addchild %d (source=%d)\n",getId(),id,source);
                        rr_->getRouteInfo(getId())->addChild(rr_->getRouteInfo(id));
                }
//              else
//              {
//                      printf("RM %d Module %d is not child :-(\n", getId(), getDownLaySAP(j)->getModuleDownId());
//              }
        }
        return rr_->length();

}

int MrclRouting::recvSyncClMsg(ClMessage *m)
{
        if(m->type() == CL_ROUTEMESSAGE)
        {
                RouteReachable *r = (RouteReachable *)m;
                r->processed(1);
                RouteInfo **info = r->getRouteInfo();
                rr_->empty();
                for(int i = 0; i < r->length(); i++)
                {
                        printf("crLay.... addRouteInfo %d\n", info[i]->getModuleId());
                        rr_->addRouteInfo(info[i]);
                }
                //printf("RoutingModule %d has rx a CL_ROUTEMESSAGE\n", getId());
                int nInfo = getConfiguration(((RouteReachable *)m)->getAddress(), m->getSource());
                if(nInfo < 0)
                {
                        ((RouteReachable *)m)->setMyIP();
                }
                else
                {
                        for(int i = 0; i < nInfo; i++)
                        {
                                ((RouteReachable *)m)->addRouteInfo((rr_->getRouteInfo())[i]);
                        }
                }
                return 0;
        }
        return Module::recvSyncClMsg(m);
}

int MrclRouting::findNextLeaf(int i)
{
        RouteInfo **info = rr_->getRouteInfo();
        for(int j = i + 1; j < rr_->length(); j++)
        {
                //printf("\t\ti=%d, j=%d, id=%d, nch=%d\n", i, j, info[j]->getModuleId(), info[j]->getNChild());
                if(info[j]->getNChild() == 0)
                        return info[j]->getModuleId();
        }
        return -1;
}

class MetricComparator : public Comparator
{
public:
        virtual int isLess(void *a, void *b)
        {
                ModuleRoute *ma = (ModuleRoute *)a;
                ModuleRoute *mb = (ModuleRoute *)b;
                return (ma->w < mb->w);
        }
};

int MrclRouting::getRoute(MrclAddress *a, Packet *p, int i)
{
        getRoute(a->getAddr(), p, i);
}

int MrclRouting::getRoute(char *a, Packet *p, int i)
{
        if(lastGetConfiguration_ == Scheduler::instance().clock() && MrclAddress::areEqual(a, rr_->getAddress()))
        {
                //if we have already compute the path
                if(rr_->isMyIP())
                {
                        RoutingHdr *rhdr = HDR_ROUTING(p);
                        rhdr->setSendup();
                        return -1;
                }
                if(i < routes_.count())
                {
                        RoutingHdr *rhdr = HDR_ROUTING(p);
                        rhdr->clearModuleRoute();
                        ModuleRoute *mr = (ModuleRoute *)routes_.get(i);
                        for(int k = mr->modules.count() - 1; k >= 0; k--)
                        {
                                RouteInfo *info = (RouteInfo *)(mr->modules.get(k));
                                rhdr->addModuleRoute(mr->modules.count() - 1 - k, info->getModuleId());
                        }
                }

                return routes_.count();
        }
        //else
        //getConfiguration(a, getId());
        getConfiguration(a);
        lastGetConfiguration_ = Scheduler::instance().clock();
        
        if(rr_->isMyIP())
        {
                RoutingHdr *rhdr = HDR_ROUTING(p);
                rhdr->setSendup();
                return -1;
        }
        int j = findNextLeaf();
        //printf("HERE (%d) rr->length = %d\n", getId(), rr_->length());
        // Dealloc
        for(int k = 0; k < routes_.count(); k++)
        {
                ModuleRoute *tmp = (ModuleRoute *)routes_.get(k);
                delete tmp;
        }
        routes_.clear();
        int c = 0;
        while(j >= 0)
        {
                RouteInfo *info = rr_->getRouteInfo(j);
                if(info->reachability() != UNREACHABLE)
                {
                        RouteInfo *f = info->getFather();
                        MetricList l;
                        ModuleRoute *mr = new ModuleRoute;
                        mr->modules.set(0,(void *)info);
                        for(int k = 0; k < info->getNMetric(); k++)
                        {
                                l.addMetric(info->getMetric(k));
                        }
                        int d = 1;
                        while(f)
                        {
                                mr->modules.set(d++,(void *)f);
//                              printf("\tFIND A FATHER %d (%i)\n", f->getModuleId(), mr->modules.count());
                                if(f->getNMetric() > 0)
                                {
                                        for(int k = 0; k < f->getNMetric(); k++)
                                        {
                                                f->getMetric(k)->clearParam();
                                                f->getMetric(k)->insertParam(&l);
                                        }
                                        l.empty();
                                        for(int k = 0; k < f->getNMetric(); k++)
                                        {
                                                l.addMetric(f->getMetric(k));
                                        }
                                }
                                f = f->getFather();
                        }
                        double w = 0.0;
                        for(int k = 0; k < l.length(); k++)
                        {
                                w += l.getMetric(k)->value(p);
                        }
                        mr->w = w;
                        mr->reachability = info->reachability();
                        if (debug_>10)
                                printf("[RoutingModule] Module %d Add new route %d (j=%d) metric %f\n", getId(), c, j, mr->w);
                        routes_.set(c++,(void *)mr);
                }
                //printf("\t\trr_-getIndex(%d)=%d ",j, rr_->getIndex(j));
                j = findNextLeaf(rr_->getIndex(j));
                //printf("j=%d\n",j);
        }
        // Resort Routes
        MetricComparator comp;
//      for(int k = 0; k< routes_.count(); k++)
//              printf("BEFORE_SORT route %d etric %f\n", k, ((ModuleRoute *)routes_.get(k))->w);
        routes_.sort(&comp);
//      for(int k = 0; k< routes_.count(); k++)
//              printf("AFTER_SORT route %d etric %f (%d)\n", k, ((ModuleRoute *)routes_.get(k))->w, ((ModuleRoute *)routes_.get(k))->modules.count());
        // Return the modules
        int ret = routes_.count();
        if(i < ret)
        {
                RoutingHdr *rhdr = HDR_ROUTING(p);
                rhdr->clearModuleRoute();
                rhdr->setSendup();
                ModuleRoute *mr = (ModuleRoute *)routes_.get(i);
                for(int k = mr->modules.count() - 1; k >= 0; k--)
                {
                        RouteInfo *info = (RouteInfo *)(mr->modules.get(k));
                        rhdr->addModuleRoute(mr->modules.count() - 1 - k, info->getModuleId());
                        if (debug_>10)
                                printf("[RoutingModule::getRoute] - ADDMODULEROUTE %d (%d)\n", info->getModuleId(), mr->modules.count());
                }
                if (mr->reachability==MAYBE) ret *= -1;
        }

        return ret;
}


void MrclRouting::recv(Packet *p)
{
        if (controlPacket(p))
        {
                // this is a control packet of this routing module -> just processed it -> drop it
                //drop(p, CTRL_PKT_DROP_VERBOSITY, CTRL_PKT_DROP_MSG);
                return;
        }
        RoutingHdr* mrhdr = HDR_ROUTING(p);
        hdr_cmn* ch = hdr_cmn::access(p);
        int nModule = mrhdr->moduleRouteCount();
        if (debug_>10)
                printf("\t\tModule %d - recv - nmodule=%d\n", getId(), nModule);
        if (nModule==0)
        {
                if (mrhdr->sendup()==0)
                {
                        // Packet has not been yet solved -> try to solve it
                        // here the packet has to be solved for the 1st time
                        if(ch->direction() == hdr_cmn::DOWN)
                        {
                                // first routing module which processes the packet set the source address
                                assert(nAddresses()>0);
                                MrclAddress::storeAddr(mrhdr->saddr(), addresses_[0]->getAddr());
                        }
                        forward(p);
                }
                else
                {
                        // Packet has been solved -> not for me -> send Up
                        sendUp(p, delayUp_);
                }
        }
        else
        {
                // go through the Module Id list
                int nextModule = -1;
                for(int i=0; i<nModule; i++)
                {
                        if (mrhdr->getModuleRoute(i)==getId())
                        {
                                if (i < nModule-1)
                                {
                                        // get the next ModuleId in the path
                                        nextModule = mrhdr->getModuleRoute(i+1);
                                }
                                else
                                {
                                        // this is the last Routing Module: clean the Module Id list in the packet header and solve the routing
                                        nextModule = mrhdr->getModuleRoute(i);
                                        mrhdr->clearModuleRoute();
                                        char *nextHop = getNextHop(p);
                                        if(nextHop)
                                        {
                                                MrclAddress::storeAddr(mrhdr->nexthop(), nextHop);
//                                              setOldAddresses(p);
                                                // here the packet has to be solved from the leaf module
                                        }
                                        else
                                        {
                                                // maybe someone has chosen this module when he said that the destination is MAYBE reacheable
                                                resolve(p);
                                        }
                                        
                                }
                                break;
                        }
                }
                if (debug_>10)
                        printf("\t\tModule %d - recv - nextModule=%d\n",getId(), nextModule);
                if (nextModule==-1)
                {
                        //      intermediate node -> send the packet to upper module
                        sendUp(p, delayUp_);
                }
                else if(nextModule == getId())
                {
                        sendDown(p, delayDown_);
                }
                else
                {
                        // Send the packet to the next Module in the path -> try with the above modules
                        sendDown(nextModule, p, delayDown_);
                } // end nextModule==-1
        } // end nModule==0
}

void MrclRouting::addAddress(MrclAddress *a)
{
        addresses_ = (MrclAddress **)realloc(addresses_, nAddresses_ * sizeof(MrclAddress *), (nAddresses_ + 1) * sizeof(MrclAddress *));
        addresses_[nAddresses_++] = a;
}

MrclAddress *MrclRouting::getAddress(int i)
{
        if(i < 0 || i >= nAddresses_)
                return 0;
        return addresses_[i];
}

int MrclRouting::nAddresses()
{
        return nAddresses_;
}

int MrclRouting::isMyAddress(char *addr)
{
        for(int i = 0; i < nAddresses();i++)
        {
                if(getAddress(i)->isEqual(addr))
                        return 1;
        }
        return 0;
}

---