structure.h

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.
 *
 */
 
#ifndef _ALZOUBI_STRUCTURE_H_
#define _ALZOUBI_STRUCTURE_H_

#include "clustering-header.h"
#include <map>
#include <list>

//---------------------------------------------------------------------------------
// Tipi di messaggio
//---------------------------------------------------------------------------------
typedef enum
{
    ALZOUBI_COLOR = 0x0,		// Messaggio per segnalare il colore di un nodo.
	ALZOUBI_LAST = 0x1,
    ALZOUBI_REQUEST = 0x2,      // Richiesta di ritrasmissione.
    ALZOUBI_CONFIRM = 0x3,		// Mesaggio di conferma per l'avvenuta ricezione.
	ALZOUBI_DATA = 0x4
} AlzoubiMessageType;

//---------------------------------------------------------------------------------
// Informazioni sull'albero di appartenenza.
//---------------------------------------------------------------------------------
struct TreeInfo {
    NodeList childs;    	// Nodi figli.
    NodeAddress parent;         // Nodo genitore.
};

//---------------------------------------------------------------------------------
// Informazioni su di un frammento.
//---------------------------------------------------------------------------------
struct FragmentInfo {
    NodeAddress ID;		// Identita' del leader del frammento.
    int size;                   // Dimensione del frammento.

    // Un frammento e'minore di un'altro se e'di dimensione minore 
    // oppure se e'delle stesse dimensioni e ha un ID minore.
    bool operator< (const struct FragmentInfo & fragment) {
        if (size < fragment.size)
            return true;
    	return ((size == fragment.size) && 
                (ID < fragment.ID));
    }
};

//---------------------------------------------------------------------------------
// Lista di nodi, per round che richiede la conferma dei messaggi INFO inviati.
//---------------------------------------------------------------------------------
typedef map<int, NodeList> ConfirmationNodes;

//---------------------------------------------------------------------------------
// Messaggio INFO.
//---------------------------------------------------------------------------------
struct InfoMessage {
    struct FragmentInfo fragment;	// Frammento a cui appartiene il nodo mittente.
    struct FragmentInfo new_fragment;		// Frammento a cui il nodo dello stesso frammento 
    						// deve appartenere.
    NodeAddress parent;                         // Genitore del mittente.
    int round;                                  // Round del messaggio.
};

//---------------------------------------------------------------------------------
// Buffer per i messaggi di INFO inviati: uno per ogni round.
//---------------------------------------------------------------------------------
typedef map<int, struct InfoMessage> BufferInfoMessages;

//---------------------------------------------------------------------------------
// Messaggio FEEDBACK.
//---------------------------------------------------------------------------------
struct FeedbackMessage {
    struct FragmentInfo fragment;	// Frammento a cui appartiene il nodo mittente.
    bool maximal_fragment_available;            // Indica se il mittente conosce o no un frammento vicino massimale.
    struct FragmentInfo maximal_fragment;	// Informazioni sul frammento massimale.
    int node_count;				// Numero di nodi del sottoalbero radicato nel mittente.
    int round;					// Round del messaggio.
};

//---------------------------------------------------------------------------------
// Buffer per i messaggi di FEEDBACK inviati: uno per ogni round.
//---------------------------------------------------------------------------------
typedef map<int, struct FeedbackMessage> BufferFeedbackMessages;

//---------------------------------------------------------------------------------
// Messaggi memorizzati (per le ritrasmissioni).
//---------------------------------------------------------------------------------
struct StoredMessages {
    BufferInfoMessages info;		// Messaggi di INFO.
    BufferFeedbackMessages feedback;	// Messaggi di FEEDBACK.
};

//---------------------------------------------------------------------------------
// Messaggio ACTION.
//---------------------------------------------------------------------------------
struct ActionMessage {
    struct FragmentInfo current_fragment;	// Frammento del messaggio di ACTION.
	int round;
};

//---------------------------------------------------------------------------------
// Messaggio LEADER.
//---------------------------------------------------------------------------------
struct LeaderMessage {
    struct FragmentInfo leader;		// Informazioni sul leader e la grandezza del frammento globale.
    NodeAddress parent;                 // Genitore del mittente.
    int level;              		// Livello dell'albero del mittente.
    bool confirm;           		// True indica un messaggio ritrasmesso, richiede la ritrasmissione.
                            		// Non si usa il messaggio di request per specificare i dati del leader
                                        // perche'in questo modo, posso inviare le informazioni sul leader.
};

//---------------------------------------------------------------------------------
// Messaggio COLOR.
//---------------------------------------------------------------------------------
struct ColorMessage {
    bool dominator;			// True = DOMINATOR, False = DOMINATEE
    int round;				// Round del messaggio
};

//---------------------------------------------------------------------------------
// Messaggio LAST.
//---------------------------------------------------------------------------------
struct LastMessage {
	Color color;
};

//---------------------------------------------------------------------------------
// Messaggio REQUEST.
//---------------------------------------------------------------------------------
struct RequestMessage {
    AlzoubiMessageType type;			// Tipo i messaggio richiesto.
    int round;                          // Round del messaggio.
};

//---------------------------------------------------------------------------------
// Messaggio CONFIRM.
//---------------------------------------------------------------------------------
struct ConfirmMessage {
    AlzoubiMessageType type;			// Tipo di messaggio da confermare.
    bool send;				// True se il messaggio e'l'invio, False se e'la risposta.
    int round;				// Round del messaggio.
};

//---------------------------------------------------------------------------------
// Collezione principale di dati sulla leader election phase.
//---------------------------------------------------------------------------------
struct LeaderElectionData {
    bool candidate;								// True se il nodo e'un candidato.
    struct TreeInfo tree;						// Informazioni sull'albero interno 
												// al frammento a cui il nodo appartiene.
    struct FragmentInfo fragment;				// Informazioni sul frammento a cui il nodo appartiene.
    map<int, bool> maximal_fragment_available;	// True se si conosce un frammento massimale
    map<int, struct FragmentInfo> maximal_fragment;	// Il frammento massimale
    map<int, NodeAddress> maximal_fragment_node;	// Nodo a cui legarsi.
    map<int, NodeAddress> stored_path;			// Vicino verso il quale si raggiunge l'edge node massimale.
                                                // -1 indica che il nodo corrente e'l'edge node.

	// Messaggio INFO proveniente dal nodo di JOIN memorizzato: serve perche'il messaggio di ACTION
	// puo'giungere dopo la ricezione del messaggio di INFO da parte del nodo del frammento massimale 
	// che darebbe il via alla propagazione dell'INFO anche nel frammento del nodo.
	map<int, struct InfoMessage> maximal_fragment_node_info_message;
	
	// Memorizza la ricezione di un messaggio di action per un certo round.
	map<int, bool> action_for_round;
	
    NodeAddress old_fragment_identity;			// Vecchia identita'del frammento.
    NodeAddress new_fragment_identity;          // Identita'del frammento a cui legarsi.
    NodeList info_messages;						// Vicini che ancora devono inviare il messaggio di INFO.
    NodeList feedback_messages;					// Vicini che ancora devono inviare il messaggio di FEEDBACK.
    NodeList leader_messages;					// Vicini che devono ancora inviare il messaggio di LEADER.
    int sub_tree_partial_count;					// Conteggio dei nodi del sottoalbero radicato nel nodo corrente.
    
    //------------------
    // Buffers.
    //------------------
    list<pair<NodeAddress, struct InfoMessage> > buffer_info;		// Messaggi di INFO inviati dai vicini.
    list<pair<NodeAddress, struct FeedbackMessage> > buffer_feedback;	// Messaggi di FEEDBACK inviati dai vicini.
	map<int, pair<NodeAddress, NodeAddress> > buffer_action;
    ConfirmationNodes confirmation_nodes_info;				// Nodi dai quali ci si aspetta un INFO message.
    
    //------------------
    // Messaggi inviati.
    //------------------
    struct StoredMessages stored_messages;

    //------------------
    // Round dell'algoritmo.
    //------------------
    int round;

};



struct CDSConstructionData {
    
    Color color;
    
    //==========================//
    // Second phase of algorithm //
    //==========================//
    
    NodeAddress parent;
    NodeAddress leader;
    int tree_size;
    int level;
    NodeList childs;
    
    NodeList white_neighbors;		// Lista di vicini WHITE.
    NodeList childs_no_dominatee;	// Lista dei vicini che non hanno mai inviato un
									// messaggio di tipo DOMINATEE.
    NodeList black_neighbors;		// Lista dei vicini BLACK.
    NodeList lower_rank;			// Lista dei vicini di rango inferiore che non hanno
									// mai inviato un messaggio di tipo DOMINATEE.
    int lower_rank_size;			// Numero di vicini di rango inferiore.
    NodeList gray_neighbors;		// Vicini GRAY.
    NodeList childs_gray_or_black;	// Nodi figli GRAY o BLACK.
    
    map<NodeAddress, int> levels;	// Livello di un vicino.
	
	map<NodeAddress, Color> lastColor;		// Ultimo colore di un vicino.
    
    //=========//
    // Buffers //
    //=========//
    
    map<NodeAddress, struct ColorMessage> messages[2];		// Messaggi CDS dai vicini.
    int round;												// Numero di round.
    struct ColorMessage myFirstColor;						// Buffer di messaggi inviati.
    struct ColorMessage mySecondColor;						// Buffer di messaggi inviati.
	Color myLastColor;										// Ultimo colore del nodo.

	NodeList last_messages;					// Vicini che devono inviare il messaggio di LAST.

    bool endFirstCDSBufferization;			// E'true se il buffer