mpr.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 "Separator.h"
#include "BackboneUtility.h"

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

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

int hdr_mpr::offset_;

int MPR_Agent::_DEBUG_;
int MPR_Agent::enhanced;
int MPR_Agent::enhanced_2;

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

static class MprClass : public TclClass {
public:
    MprClass() : TclClass("Agent/MPR") {}
    TclObject* create(int argc, const char*const* argv) {
        return(new MPR_Agent());
    }
} class_mpr;


static class MprHeaderClass : public PacketHeaderClass {
public:
	MprHeaderClass() : PacketHeaderClass("PacketHeader/MPR",
					      sizeof(hdr_mpr)) {
		bind_offset(&hdr_mpr::offset_);                   
	}
} class_mprhdr;

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

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

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

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

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

//
// Fa partire i timeout per i nodi che non hanno ancora inviato
// il proprio colore (iniziale).
//        
void 
MprTimer::launchFirstDecisionTimeout(NodeAddress node)
{
	// Definisce i Timeout di tipo FIRST DECISION
	struct Timeout f;
	f.timeout = new Event();
	f.num = MPR_Agent::max_timeout_first_decision;
	first_decision_timeouts[node] = f;

	Scheduler::instance().schedule(this, f.timeout, MPR_Agent::timeout_first_decision + Random::uniform(MPR_Agent::jitter_timeout_first_decision));
}

//
// Fa partire i timeout per i nodi che non hanno ancora inviato
// il proprio colore (finale).
//        
void 
MprTimer::launchLastDecisionTimeouts()
{
    for (TimeoutMap::iterator i = last_decision_timeouts.begin(); i != last_decision_timeouts.end(); i++) {
        Scheduler::instance().schedule(this, i->second.timeout, 
            MPR_Agent::timeout_last_decision + Random::uniform(MPR_Agent::jitter_timeout_last_decision));
    }
}
     
//
// L'agente segnala la ricezione di un messaggio di tipo HELLO:
// il timeout viene eliminato.
//
void 
MprTimer::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 
MprTimer::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 
MprTimer::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
//
MPR_Agent::MPR_Agent() : ClusteringModule(PT_MPR)
{
    timer = new MprTimer(this);
	
	bind_bool("debug", &_DEBUG_);
	bind_bool("enhanced", &enhanced);
	bind_bool("enhanced-2", &enhanced_2);

	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 
MPR_Agent::receive(Packet *p, Handler *h) 
{
    struct hdr_mpr *mprh = HDR_MPR(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 (mprh->msg_type) {
        case MPR_NEIGHBORS :
            receive_NEIGHBORS(sender_address, *(mprh->node_list));
            break;
            
        case MPR_COLOR :
            receive_COLOR(sender_address, mprh->color);
            break;

        case MPR_SELECTION :
            receive_MPR(sender_address, mprh->mpr_selected);
            break;
                        
        case MPR_REQUEST :
            receive_REQUEST(sender_address, mprh->status);
            break;
        default:
            break;
    }
	
}

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

    Packet* p = allocpkt();
	
    struct hdr_mpr * mprh = HDR_MPR(p);
	
    mprh->msg_type = MPR_REQUEST;
    mprh->status = _status_;

	sendDown(p, sizeof(MprMessageType) + sizeof(MprStatus), to, MPR_Agent::max_delay);
}

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

    Packet* p = allocpkt();
    
    struct hdr_mpr * mprh = HDR_MPR(p);
    
    mprh->msg_type = MPR_NEIGHBORS;
    mprh->node_list = & neighbors;

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

//
// Messaggio usato per comunicare il colore del nodo in una certa fase dell'algoritmo.
//
void
MPR_Agent::send_COLOR(NodeAddress to, Color color) 
{
	/*
	if (_DEBUG_)
		printf("%d send COLOR\n", myAddress);
	*/
		
    Packet* p = allocpkt();
	
    struct hdr_mpr * mprh = HDR_MPR(p);
    
    mprh->msg_type = MPR_COLOR;
    mprh->color = color;

	sendDown(p, sizeof(MprMessageType) + sizeof(Color), to, MPR_Agent::max_delay);
}

//
// Messaggio usato per comunicare il colore del nodo in una certa fase dell'algoritmo.
//
void
MPR_Agent::send_MPR(NodeAddress to, bool selected) 
{
	/*
	if (_DEBUG_)
		printf("%d send MPR to %d: %d\n", myAddress, to, selected ? 1 : 0);
	*/
		
    Packet* p = allocpkt();
	
    struct hdr_mpr * mprh = HDR_MPR(p);
    
    mprh->msg_type = MPR_SELECTION;
    mprh->mpr_selected = selected;

	sendDown(p, sizeof(MprMessageType) + sizeof(bool), to, MPR_Agent::max_delay);
}

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

//
// Procedura per verificare se esistono due vicini del nodo 
// non collegati fra loro.
//
bool
MPR_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 esiste un sottoinsieme di nodi di grandezza specificata
// che abbia le seguenti caratteristiche:
// 1) L'insieme dei nodi