wuli.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 "wuli.h"
#include "random.h"
#include "gridkeeper.h"
#include <algorithm>
#include <typeinfo>

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

int hdr_wuli::offset_;

int WULI_Agent::degree;
int WULI_Agent::stojmenovic;
int WULI_Agent::_DEBUG_;

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

static class WuliClass : public TclClass {
public:
    WuliClass() : TclClass("Agent/WULI") {}
    TclObject* create(int argc, const char*const* argv) {
        return(new WULI_Agent());
    }
} class_wuli;


static class WuliHeaderClass : public PacketHeaderClass {
public:
	WuliHeaderClass() : PacketHeaderClass("PacketHeader/WULI",
					      sizeof(hdr_wuli)) {
		bind_offset(&hdr_wuli::offset_);                   
	}
} class_wulihdr;

//
// Verifica che il timeout sia di tipo HELLO.
//
bool
WuliTimer::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(WULI_STATUS_HELLO, i->first);
            }
            else {
                Scheduler::instance().schedule(this, e, 
                    WULI_Agent::timeout_hello + Random::uniform(WULI_Agent::jitter_timeout_hello));
                agent->timeout(WULI_STATUS_HELLO, i->first);
            }
            return true;
        }
    }
    return false;
}

//
// Verifica che il timeout sia di tipo FIRST DECISION.
//
bool
WuliTimer::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(WULI_STATUS_FIRST_DECISION, i->first);
            }
            else {
                Scheduler::instance().schedule(this, e, 
                    WULI_Agent::timeout_first_decision + Random::uniform(WULI_Agent::jitter_timeout_first_decision));
                agent->timeout(WULI_STATUS_FIRST_DECISION, i->first);
            }
            return true;
        }
    }    
    return false;
}

//
// Verifica che il timeout sia di tipo LAST DECISION.
//
bool
WuliTimer::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(WULI_STATUS_LAST_DECISION, i->first);
            }
            else {
                Scheduler::instance().schedule(this, e, 
                    WULI_Agent::timeout_last_decision + Random::uniform(WULI_Agent::jitter_timeout_last_decision));
                agent->timeout(WULI_STATUS_LAST_DECISION, i->first);
            }
            return true;
        }
    }    
    return false;
}

//
// Gestisce l'arrivo di un timeout segnalandolo
// opportunamente all'Agente.
//
void
WuliTimer::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
WuliTimer::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 = WULI_Agent::max_timeout_hello;
        hello_timeouts[*i] = h;

        // Definisce i Timeout di tipo FIRST DECISION
        struct Timeout f;
        f.timeout = new Event();
        f.num = WULI_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 = WULI_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
WuliTimer::launchHelloTimeouts()
{
    for (TimeoutMap::iterator i = hello_timeouts.begin(); i != hello_timeouts.end(); i++) {
        Scheduler::instance().schedule(this, i->second.timeout, 
            WULI_Agent::timeout_hello + Random::uniform(WULI_Agent::jitter_timeout_hello));
    }    
}

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

//
// Fa partire i timeout per i nodi che non hanno ancora inviato
// il proprio colore (finale).
//        
void 
WuliTimer::launchLastDecisionTimeouts()
{
    for (TimeoutMap::iterator i = last_decision_timeouts.begin(); i != last_decision_timeouts.end(); i++) {
        Scheduler::instance().schedule(this, i->second.timeout, 
            WULI_Agent::timeout_last_decision + Random::uniform(WULI_Agent::jitter_timeout_last_decision));
    }
}
     
//
// L'agente segnala la ricezione di un messaggio di tipo HELLO:
// il timeout viene eliminato.
//
void 
WuliTimer::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 
WuliTimer::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 
WuliTimer::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
//
WULI_Agent::WULI_Agent() : ClusteringModule(PT_WULI)
{
    timer = new WuliTimer(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 
WULI_Agent::receive(Packet *p, Handler *h) 
{
    struct hdr_wuli *wulih = HDR_WULI(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 (wulih->msg_type) {
        case WULI_NEIGHBORS :
            receive_NEIGHBORS(sender_address, *(wulih->node_list));
            break;
            
        case WULI_COLOR :
            receive_COLOR(sender_address, wulih->status, wulih->color);
            break;
                        
        case WULI_REQUEST :
            receive_REQUEST(sender_address, wulih->status);
            break;
        default:
            break;
    }
	
}

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

    Packet* p = allocpkt();
	
    struct hdr_wuli * wulih = HDR_WULI(p);
	
    wulih->msg_type = WULI_REQUEST;
    wulih->status = _status_;

	sendDown(p, sizeof(WuliMessageType) + sizeof(WuliStatus), to, WULI_Agent::max_delay);
}

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

    Packet* p = allocpkt();
    
    struct hdr_wuli * wulih = HDR_WULI(p);
    
    wulih->msg_type = WULI_NEIGHBORS;
    wulih->node_list = & neighbors;

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

//
// Messaggio usato per comunicare il colore del nodo in una certa fase dell'algoritmo.
//
void
WULI_Agent::send_COLOR(WuliStatus _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_wuli * wulih = HDR_WULI(p);
    
    wulih->msg_type = WULI_COLOR;
    wulih->status = _status_;
    wulih->color = color;

	sendDown(p, sizeof(WuliMessageType) + sizeof(WuliStatus) + sizeof(Color), to, WULI_Agent::max_delay);
}

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

//
// Procedura per verificare se esistono due vicini del nodo 
// non collegati fra loro.
//
bool
WULI_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