initializer.cc

clustering for ns-2 simulation

/**
 * Copyright (c) 2006 Michele Mastrogiovanni.
 *
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 *
 */
 
////////////////
// NS Headers //
////////////////
#include "BackboneUtility.h"
#include "Separator.h"

#include "initializer.h"
#include "random.h"
#include "gridkeeper.h"
#include <algorithm>
#include <typeinfo>

///////////////////////////////////
// Parte di dichiarazione comune //
///////////////////////////////////

int hdr_initializer::offset_;

int INITIALIZER_Agent::degree;
int INITIALIZER_Agent::stojmenovic;
int INITIALIZER_Agent::_DEBUG_;

int INITIALIZER_Agent::limit;
double INITIALIZER_Agent::max_delay;
int INITIALIZER_Agent::max_timeout_hello;
double INITIALIZER_Agent::jitter_timeout_hello;
double INITIALIZER_Agent::timeout_hello;
int INITIALIZER_Agent::max_timeout_first_decision;
double INITIALIZER_Agent::jitter_timeout_first_decision;
double INITIALIZER_Agent::timeout_first_decision;
int INITIALIZER_Agent::max_timeout_last_decision;
double INITIALIZER_Agent::jitter_timeout_last_decision;
double INITIALIZER_Agent::timeout_last_decision;

static class InitializerClass : public TclClass {
public:
    InitializerClass() : TclClass("Agent/INITIALIZER") {}
    TclObject* create(int argc, const char*const* argv) {
        return(new INITIALIZER_Agent());
    }
} class_initializer;


static class InitializerHeaderClass : public PacketHeaderClass {
public:
	InitializerHeaderClass() : PacketHeaderClass("PacketHeader/INITIALIZER",
					      sizeof(hdr_initializer)) {
		bind_offset(&hdr_initializer::offset_);                   
	}
} class_initializerhdr;

//
// Verifica che il timeout sia di tipo HELLO.
//
bool
InitializerTimer::isHelloTimeout(Event * e)
{
    for (TimeoutMap::iterator i = hello_timeouts.begin(); i != hello_timeouts.end(); i++) {
        if (i->second.timeout == e) {
            i->second.num--;
            if (i->second.num <= 0) {
                agent->lastTimeout(INITIALIZER_STATUS_HELLO, i->first);
            }
            else {
                Scheduler::instance().schedule(this, e, 
                    INITIALIZER_Agent::timeout_hello + Random::uniform(INITIALIZER_Agent::jitter_timeout_hello));
                agent->timeout(INITIALIZER_STATUS_HELLO, i->first);
            }
            return true;
        }
    }
    return false;
}

//
// Verifica che il timeout sia di tipo FIRST DECISION.
//
bool
InitializerTimer::isFirstDecisionTimeout(Event * e)
{
    for (TimeoutMap::iterator i = first_decision_timeouts.begin(); i != first_decision_timeouts.end(); i++) {
        if (i->second.timeout == e) {
            i->second.num--;
            if (i->second.num <= 0) {
                agent->lastTimeout(INITIALIZER_STATUS_FIRST_DECISION, i->first);
            }
            else {
                Scheduler::instance().schedule(this, e, 
                    INITIALIZER_Agent::timeout_first_decision + Random::uniform(INITIALIZER_Agent::jitter_timeout_first_decision));
                agent->timeout(INITIALIZER_STATUS_FIRST_DECISION, i->first);
            }
            return true;
        }
    }    
    return false;
}

//
// Verifica che il timeout sia di tipo LAST DECISION.
//
bool
InitializerTimer::isLastDecisionTimeout(Event * e)
{
    for (TimeoutMap::iterator i = last_decision_timeouts.begin(); i != last_decision_timeouts.end(); i++) {
        if (i->second.timeout == e) {
            i->second.num--;
            if (i->second.num <= 0) {
                agent->lastTimeout(INITIALIZER_STATUS_LAST_DECISION, i->first);
            }
            else {
                Scheduler::instance().schedule(this, e, 
                    INITIALIZER_Agent::timeout_last_decision + Random::uniform(INITIALIZER_Agent::jitter_timeout_last_decision));
                agent->timeout(INITIALIZER_STATUS_LAST_DECISION, i->first);
            }
            return true;
        }
    }    
    return false;
}

//
// Gestisce l'arrivo di un timeout segnalandolo
// opportunamente all'Agente.
//
void
InitializerTimer::handle(Event *e)
{
    if (isHelloTimeout(e))
        return;
        
    if (isFirstDecisionTimeout(e))
        return;

    if (isLastDecisionTimeout(e))
        return;
}

//
// Inizializza i timeout che si possono lanciare in base ai vicini del nodo.
// 
void
InitializerTimer::initTimeouts(NodeList & neighbors) 
{
    for (NodeList::iterator i = neighbors.begin(); i != neighbors.end(); i++) {

        // Definisce i Timeout di tipo HELLO
        struct Timeout h;
        h.timeout = new Event();
        h.num = INITIALIZER_Agent::max_timeout_hello;
        hello_timeouts[*i] = h;

        // Definisce i Timeout di tipo FIRST DECISION
        struct Timeout f;
        f.timeout = new Event();
        f.num = INITIALIZER_Agent::max_timeout_first_decision;
        first_decision_timeouts[*i] = f;

        // Definisce i Timeout di tipo LAST DECISION
        struct Timeout s;
        s.timeout = new Event();
        s.num = INITIALIZER_Agent::max_timeout_last_decision;
        last_decision_timeouts[*i] = s;
        
    }
}

//
// Fa partire i timeout per i nodi che non hanno ancora risposto al
// messaggio di HELLO inviando la propria lista di vicini.
//        
void
InitializerTimer::launchHelloTimeouts()
{
    for (TimeoutMap::iterator i = hello_timeouts.begin(); i != hello_timeouts.end(); i++) {
        Scheduler::instance().schedule(this, i->second.timeout, 
            INITIALIZER_Agent::timeout_hello + Random::uniform(INITIALIZER_Agent::jitter_timeout_hello));
    }    
}

//
// Fa partire i timeout per i nodi che non hanno ancora inviato
// il proprio colore (iniziale).
//        
void 
InitializerTimer::launchFirstDecisionTimeouts()
{
    for (TimeoutMap::iterator i = first_decision_timeouts.begin(); i != first_decision_timeouts.end(); i++) {
        Scheduler::instance().schedule(this, i->second.timeout, 
            INITIALIZER_Agent::timeout_first_decision + Random::uniform(INITIALIZER_Agent::jitter_timeout_first_decision));
    }
}

//
// Fa partire i timeout per i nodi che non hanno ancora inviato
// il proprio colore (finale).
//        
void 
InitializerTimer::launchLastDecisionTimeouts()
{
    for (TimeoutMap::iterator i = last_decision_timeouts.begin(); i != last_decision_timeouts.end(); i++) {
        Scheduler::instance().schedule(this, i->second.timeout, 
            INITIALIZER_Agent::timeout_last_decision + Random::uniform(INITIALIZER_Agent::jitter_timeout_last_decision));
    }
}
     
//
// L'agente segnala la ricezione di un messaggio di tipo HELLO:
// il timeout viene eliminato.
//
void 
InitializerTimer::receivedHello(NodeAddress from)
{
    TimeoutMap::iterator i;
    for (i = hello_timeouts.begin(); i != hello_timeouts.end(); i++) {
        if (i->first == from) {
            Scheduler::instance().cancel(i->second.timeout);
            break;
        }
    }
    if (i != hello_timeouts.end())
        hello_timeouts.erase(i);
}

//
// L'agente segnala la ricezione di un messaggio di tipo FIRST DECISION:
// il timeout viene eliminato.
//
void 
InitializerTimer::receivedFirstDecision(NodeAddress from)
{
    TimeoutMap::iterator i;
    for (i = first_decision_timeouts.begin(); i != first_decision_timeouts.end(); i++) {
        if (i->first == from) {
            Scheduler::instance().cancel(i->second.timeout);
            break;
        }
    }
    if (i != first_decision_timeouts.end())
        first_decision_timeouts.erase(i);
}
    
//
// L'agente segnala la ricezione di un messaggio di tipo LAST DECISION:
// il timeout viene eliminato.
//
void 
InitializerTimer::receivedLastDecision(NodeAddress from)
{
    TimeoutMap::iterator i;
    for (i = last_decision_timeouts.begin(); i != last_decision_timeouts.end(); i++) {
        if (i->first == from) {
            Scheduler::instance().cancel(i->second.timeout);
            break;
        }
    }
    if (i != last_decision_timeouts.end())
        last_decision_timeouts.erase(i);
}

//
// Costruttore
//
INITIALIZER_Agent::INITIALIZER_Agent() : ClusteringModule(PT_INITIALIZER)
{
    timer = new InitializerTimer(this);
	
	bind_bool("debug", &_DEBUG_);
	bind_bool("degree", &degree);
	bind_bool("stojmenovic", &stojmenovic);

	bind("limit", &limit);

	bind("max-delay", &max_delay);
	bind("max-timeout-hello", &max_timeout_hello);
	bind("jitter-timeout-hello", &jitter_timeout_hello);
	bind("timeout-hello", &timeout_hello);
	bind("max-timeout-first-decision", &max_timeout_first_decision);
	bind("jitter-timeout-first-decision", &jitter_timeout_first_decision);
	bind("timeout-first-decision", &timeout_first_decision);
	bind("max-timeout-last-decision", &max_timeout_last_decision);
	bind("jitter-timeout-last-decision", &jitter_timeout_last_decision);
	bind("timeout-last-decision", &timeout_last_decision);
	
}

void 
INITIALIZER_Agent::receive(Packet *p, Handler *h) 
{
    struct hdr_initializer *initializerh = HDR_INITIALIZER(p);    
    struct hdr_ip *iph = HDR_IP(p);
    
    // Mittente.
    NodeAddress sender_address = iph->saddr(); //dcah->my_status.node_ID;
    // Destinazione.
    NodeAddress destination_address = iph->daddr(); // dcah->destination_address;

    switch (initializerh->msg_type) {
        case INITIALIZER_NEIGHBORS :
            receive_NEIGHBORS(sender_address, *(initializerh->node_list));
            break;
            
        case INITIALIZER_COLOR :
            receive_COLOR(sender_address, initializerh->status, initializerh->color);
            break;
                        
        case INITIALIZER_REQUEST :
            receive_REQUEST(sender_address, initializerh->status);
            break;
        default:
            break;
    }
	
}

//
// Richiede un messaggio che forse e'stato perduto.
//
void
INITIALIZER_Agent::send_REQUEST(InitializerStatus _status_, NodeAddress to) 
{
	if (_DEBUG_)
		printf("%d send REQUEST\n", myAddress);

    Packet* p = allocpkt();
	
    struct hdr_initializer * initializerh = HDR_INITIALIZER(p);
	
    initializerh->msg_type = INITIALIZER_REQUEST;
    initializerh->status = _status_;

	sendDown(p, sizeof(InitializerMessageType) + sizeof(InitializerStatus), to, INITIALIZER_Agent::max_delay);
}

//
// Messaggio usato per cumunicare la propria lista dei vicini ad un nodo vicino
//
void
INITIALIZER_Agent::send_NEIGHBORS(NodeAddress to) 
{
	if (_DEBUG_)
		printf("%d send NEIGHBORS\n", myAddress);

    Packet* p = allocpkt();
    
    struct hdr_initializer * initializerh = HDR_INITIALIZER(p);
    
    initializerh->msg_type = INITIALIZER_NEIGHBORS;
    initializerh->node_list = & neighbors;

	sendDown(p, sizeof(InitializerMessageType) + sizeof(nsaddr_t) * neighbors.size(), to, INITIALIZER_Agent::max_delay);
}

//
// Messaggio usato per comunicare il colore del nodo in una certa fase dell'algoritmo.
//
void
INITIALIZER_Agent::send_COLOR(InitializerStatus _status_, NodeAddress to, Color color) 
{
	if (_DEBUG_)
		printf("%d send COLOR\n", myAddress);
		
    // Attention: set status of Agent BEFORE send GATEWAY message
    Packet* p = allocpkt();
	
    struct hdr_initializer * initializerh = HDR_INITIALIZER(p);
    
    initializerh->msg_type = INITIALIZER_COLOR;
    initializerh->status = _status_;
    initializerh->color = color;

	sendDown(p, sizeof(InitializerMessageType) + sizeof(InitializerStatus) + sizeof(Color), to, INITIALIZER_Agent::max_delay);
}

////////////////////
// Interrogazioni //
////////////////////

//
// Procedura per verificare se esistono due vicini del nodo 
// non collegati fra loro.
//
bool
INITIALIZER_Agent::twoNeighborsAreUnlinked()
{    
    NodeList tmp;

    // Il nodo A punta ad un vicino.
    for (NodeList::iterator A = neighbors.begin(); A != neighbors.end(); A++) {
        NodeList & nlA = nodeNeighbors[*A];
        // Il nodo B punta all'altro vicino.
        for (NodeList::iterator B = A; B != neighbors.end(); B++)
            // Se i vicini sono diversi
            if (A != B) {
                tmp.clear();
                tmp.insert(*B);
                // Se fra i vicini di A non c'e' B allora i due vicini sono scollegati.
                if (!includes(nlA.begin(), nlA.end(), tmp.begin(), tmp.end()))
                    return true;
            }
    }

    // Tutti i vicini sono collegati fra loro
    return false;
}

//
// Verifica se l'insieme dei vicini passato come parametro
// costituisce un insieme connesso.
// Viene effettuata una visita in profondit