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

#include "Separator.h"

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

int hdr_c_sparsifier::offset_;

int CSPARSIFIER_Agent::_DEBUG_;                // Attiva la modalita' di debug.

int CSPARSIFIER_Agent::virtual_neighbors;
double CSPARSIFIER_Agent::max_delay;
int CSPARSIFIER_Agent::max_timeout_connect;
double CSPARSIFIER_Agent::jitter_timeout_connect;
double CSPARSIFIER_Agent::timeout_connect;
int CSPARSIFIER_Agent::max_timeout_candidate;
double CSPARSIFIER_Agent::jitter_timeout_candidate;
double CSPARSIFIER_Agent::timeout_candidate;

static class CSparsifierClass : public TclClass {
public:
    CSparsifierClass() : TclClass("Agent/CSPARSIFIER") {}
    TclObject* create(int , const char*const* ) {
        return(new CSPARSIFIER_Agent());
    }
} class_c_sparsifier;

static class CSparsifierHeaderClass : public PacketHeaderClass {
public:
	CSparsifierHeaderClass() : PacketHeaderClass("PacketHeader/CSPARSIFIER",
					      sizeof(hdr_c_sparsifier)) {
		bind_offset(&hdr_c_sparsifier::offset_);
	}
} class_c_sparsifierhdr;

//
// Gestisce l'arrivo di un timeout segnalandolo
// opportunamente all'Agente.
//
void
CSparsifierTimer::handle(Event *e)
{
	//
	// Timeout CONNECT.
	//
    for (TimeoutMap::iterator i = connect_timeouts.begin(); i != connect_timeouts.end(); i++) {
        if (i->second.timeout == e) {
            i->second.num--;
            if (i->second.num <= 0) {
                agent->lastTimeout(i->first, TIMEOUT_CONNECT);
            }
            else {
                Scheduler::instance().schedule(this, e, 
                    CSPARSIFIER_Agent::timeout_connect + Random::uniform(CSPARSIFIER_Agent::jitter_timeout_connect));
                agent->timeout(i->first, TIMEOUT_CONNECT);
            }
        }
    }

	//
	// Timeout CANDIDATE.
	//
    for (TimeoutMap::iterator i = candidate_timeouts.begin(); i != candidate_timeouts.end(); i++) {
        if (i->second.timeout == e) {
            i->second.num--;
            if (i->second.num <= 0) {
                agent->lastTimeout(i->first, TIMEOUT_CANDIDATE);
            }
            else {
                Scheduler::instance().schedule(this, e, 
                    CSPARSIFIER_Agent::timeout_connect + Random::uniform(CSPARSIFIER_Agent::jitter_timeout_connect));
                agent->timeout(i->first, TIMEOUT_CANDIDATE);
            }
        }
    }

}

//
// Fa partire i timeout per i nodi che non hanno ancora risposto al
// messaggio di HELLO inviando la propria lista di vicini.
//        
void
CSparsifierTimer::launchConnectTimeouts(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 = CSPARSIFIER_Agent::max_timeout_connect;
        connect_timeouts[*i] = h;
        Scheduler::instance().schedule(this, h.timeout, 
            CSPARSIFIER_Agent::timeout_connect + Random::uniform(CSPARSIFIER_Agent::jitter_timeout_connect));
    }    
}

//
// L'agente segnala la ricezione di un messaggio di tipo HELLO:
// il timeout viene eliminato.
//
void 
CSparsifierTimer::receivedConnect(NodeAddress from)
{
    TimeoutMap::iterator i;
    for (i = connect_timeouts.begin(); i != connect_timeouts.end(); i++) {
        if (i->first == from) {
            Scheduler::instance().cancel(i->second.timeout);
            break;
        }
    }
    if (i != connect_timeouts.end())
        connect_timeouts.erase(i);
}

//
// Fa partire i timeout per i nodi che non hanno ancora risposto al
// messaggio di HELLO inviando la propria lista di vicini.
//        
void
CSparsifierTimer::launchCandidateTimeouts(NodeList & neighbors)
{
    for (NodeList::iterator i = neighbors.begin(); i != neighbors.end(); i++) {
        // Definisce i Timeout di tipo CANDIDATE
        struct Timeout h;
        h.timeout = new Event();
        h.num = CSPARSIFIER_Agent::max_timeout_candidate;
        candidate_timeouts[*i] = h;
        Scheduler::instance().schedule(this, h.timeout, 
            CSPARSIFIER_Agent::timeout_candidate + Random::uniform(CSPARSIFIER_Agent::jitter_timeout_candidate));
    }    
}

//
// L'agente segnala la ricezione di un messaggio di tipo CONNECT:
// il timeout viene eliminato.
//
void 
CSparsifierTimer::receivedCandidate(NodeAddress from)
{
    TimeoutMap::iterator i;
    for (i = candidate_timeouts.begin(); i != candidate_timeouts.end(); i++) {
        if (i->first == from) {
            Scheduler::instance().cancel(i->second.timeout);
            break;
        }
    }
    if (i != candidate_timeouts.end())
        candidate_timeouts.erase(i);
}

//
// Costruttore
//
CSPARSIFIER_Agent::CSPARSIFIER_Agent() : ClusteringModule(PT_CSPARSIFIER)
{
    timer = new CSparsifierTimer(this);
	
	bind_bool("debug", &_DEBUG_);

	bind("virtual-neighbors", &virtual_neighbors);
	bind("max-delay", &max_delay);

	bind("max-timeout-connect", &max_timeout_connect);
	bind("jitter-timeout-connect", &jitter_timeout_connect);
	bind("timeout-connect", &timeout_connect);
	
	bind("max-timeout-candidate", &max_timeout_candidate);
	bind("jitter-timeout-candidate", &jitter_timeout_candidate);
	bind("timeout-candidate", &timeout_candidate);
	
}

void 
CSPARSIFIER_Agent::receive(Packet *p, Handler *h) 
{
    struct hdr_c_sparsifier *csparsifierh = HDR_CSPARSIFIER(p);    

    // Mittente.
    NodeAddress sender_address = csparsifierh->sender_address;
    // Destinazione.
    NodeAddress destination_address = csparsifierh->destination_address;
		
    switch (csparsifierh->msg_type) {
        case CSPARSIFIER_CANDIDATE :
		
			if (status != CSPARISFIER_STATUS_CANDIDATE)
				return;

			if (_DEBUG_) {
				printf("%d receive CANDIDATE: FROM %d (", myAddress, sender_address);
				for (NodeList::iterator node = (csparsifierh->selectedNodes)->begin(); node != (csparsifierh->selectedNodes)->end(); node++)
					printf("%d  ", *node);
				printf(")\n");
			}
				
			// Memorizza i nodi selezionati dal vicino
			selectedNodes[sender_address] = *(csparsifierh->selectedNodes);

			// Cancella il timeout.
			timer->receivedCandidate(sender_address);

			if (selectedNodes.size() == neighbors.size()) {
				if (_DEBUG_)
					printf("%d receive ALL CANDIDATE\n", myAddress);
			
				status = CSPARISFIER_STATUS_CONNECT;
				
				// Crea la lista dei vicini finali aggiungendo a quelli candidati,
				// i nodi vicini che hanno richiesto la connessione col nodo corrente.
				sparseNeighbors = candidateNeighbors;
				for (map<NodeAddress, NodeList>::iterator it = selectedNodes.begin(); it != selectedNodes.end(); it++) {
					if (find((it->second).begin(), (it->second).end(), myAddress) != (it->second).end())
						sparseNeighbors.insert(it->first);
				}

				// Invia il messaggio di connessione a tutti i nodi a cui non l'ha gia'mandato.
				for (NodeList::iterator it = sparseNeighbors.begin(); it != sparseNeighbors.end(); it++) {
					if (find(connect_nodes.begin(), connect_nodes.end(), *it) == connect_nodes.end())
						send_CONNECT(*it);
				}
					
				timer->launchConnectTimeouts(sparseNeighbors);
				
				// Elimina dai timeout i nodi che hanno gia'inviato il messaggio di connessione.
				for (NodeList::iterator it = connect_nodes.begin(); it != connect_nodes.end(); it++)
					timer->receivedConnect(*it);
					
				if (connect_nodes.size() == sparseNeighbors.size())
					endModule();
				
			}
			
            break;
			
		case CSPARSIFIER_CONNECT :

			if (_DEBUG_)
				printf("%d receive CONNECT: FROM %d\n", myAddress, sender_address);
		
			// Aggiunge il nodo alla lista di quelli che sono connessi
			connect_nodes.insert(sender_address);

			// Risponde al messaggio di connessione.
			if (status == CSPARISFIER_STATUS_CANDIDATE)
				send_CONNECT(sender_address);
			else {
				timer->receivedConnect(sender_address);
				if (connect_nodes.size() == sparseNeighbors.size())
					endModule();
			}
				
			break;
			
		case CSPARSIFIER_REQUEST :

			if (_DEBUG_)
				printf("%d receive REQUEST: FROM %d ", myAddress, sender_address);
		
			switch (csparsifierh->request) {
			
				case CSPARISFIER_STATUS_CANDIDATE : 

					if (_DEBUG_)
						printf("[CANDIDATE]\n");

					send_CANDIDATE(sender_address);
					break;