shiva.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 _SHIVA_H_
#define _SHIVA_H_

#include "ClusteringModule.h"
#include "CyclesFinder.h"
#include "ShivaUtility.h"
// #include "BackboneUtility.h"

// #include "dca_mastro.h"
// #include "connector_mastro.h"

#include <fstream>
#include <sstream>
#include <string>
#include <iostream>

#include <map>

////////////////
// Definition //
////////////////
#define CLUSTER_HEAD		0
#define NORMAL				1
#define GATEWAY				2

/////////////////////
/// Stato del nodo //
/////////////////////
typedef enum {

	SHIVA_STATUS_DISCOVER   = 0x0,	// Discover dei vicini BLACK a distanza minore uguale a MAX_LENGTH
									// e creazione del grafo virtual di grado massimo MAX_LENGTH.
	SHIVA_STATUS_CONNECTING = 0x1,  // Colorazione dei nodi di connessione del backbone dopo
									// l'eliminazione dei cicli.
	SHIVA_STATUS_END		= 0x2   // Fine algoritmo.
	
} ShivaStatus;

//////////////////////
// Tipi di messaggi //
//////////////////////
typedef enum
{
	SHIVA_DISCOVER		 = 0x0,			// Scopre i nodi BLACK vicini, i percorsi e i cicli.
	SHIVA_TURN_ON		 = 0x1,			// Rende BLACK un nodo WHITE sul backbone.
	SHIVA_TURN_OFF		 = 0x2,			// Rende BLACK un nodo WHITE sul backbone.
	SHIVA_CONFIRM		 = 0x3,			// Messaggio DISCOVER finale.
	SHIVA_DATA			 = 0x4			// DATA message.
} ShivaMessageType;

//
// Struttura del messaggio di discovery.
//
struct DiscoveryMessage {

	int my_seq;							// Numero di sequenza del messaggio
										//
	int ack_seq;						// Numero di sequenza del pacchetto che ha scatenato la
										// trasmissione (serve per conferma).
	NodeAddress parent;					// Nodo che ha scatenato la trasmissione.
										//
	Path path1;                         // Percorso di nodi BLACK: contiene i nodi BLACK presenti
										// dal primo (in testa) all'ultimo
	Path path2;                         // Percorso di nodi WHITE dal vicino dell'ultimo nodo 
										// BLACK al nodo WHITE precedente.
	bool dummy;							// True se il messaggio e'di tipo DUMMY (e quindi i 
										// path sono vuoti).
};

//////////////////////////
// Header del pacchetto //
//////////////////////////
struct hdr_shiva 
{
	ShivaMessageType msg_type;		// Tipo di messaggio.
	
	struct DiscoveryMessage discovery_message;
	ShivaMessageType confirm;

	/////////////////
	/// Addressing //
	/////////////////
	static int offset_;
	inline static int& offset() { return offset_; }
	inline static hdr_shiva* access(const Packet* p) {
		return (hdr_shiva*) p->access(offset_);
	}
};

struct ShivaArc {
	int length;
	NodeAddress begin;
	NodeAddress end;
};

bool isBetterThan(ShivaArc arc1, ShivaArc arc2) {
	if (arc1.length > arc2.length)
		return true;
	if (arc1.length < arc2.length)
		return false;
	int max1 = (arc1.begin > arc1.end ? arc1.begin : arc1.end);
	int max2 = (arc2.begin > arc2.end ? arc2.begin : arc2.end);
	int other_max1 = (arc1.begin > arc1.end ? arc1.end : arc1.begin);
	int other_max2 = (arc2.begin > arc2.end ? arc2.end : arc2.begin);
	
	if (max1 < max2)
		return true;
		
	if (max1 > max2)
		return false;
		
	return other_max1 < other_max2;
}

///////////
// Timer //
///////////
class ShivaTimer;

///////////
// Agent //
///////////
class SHIVA_Agent : public ClusteringModule
{
public:
	SHIVA_Agent();
	
	// Parsing dei comandi TCL.
	// virtual int command(int argc, const char * const * argv);
	
	// Funzione di ricezione dell'algoritmo di clustering.
	virtual void receive(Packet * p, Handler * h);

	// Fa partire il modulo.
	virtual void startModule();
	
	// Termine del lavoro del modulo.
	virtual void endModule();

	void beginBackboneFormation();
	
	void endCycleDiscover();
	
	// Callback from timer to signal a timeout
	void timeout(ShivaMessageType type, NodeAddress from, int seq);
	
	// Reach max number of retransmissions
	void lastTimeout(ShivaMessageType type, NodeAddress from, int seq);

	// Verifica che un pacchetto sia di tipo DATA.
	virtual bool isDataPacket(Packet * p);
	
	// Preparazione all'invio di un messaggio al layer inferiore
	virtual void prepareSendDataDown(Packet * p);
	
	virtual Color getColor(NodeAddress node) { return NO_COLOR; }
	
	void copy(Path & path1, Path & path2);

	void savePath(NodeAddress begin, NodeAddress end, ReachPath path);
	void savePaths(Path path1, Path path2);

	ReachPath higherPath(ReachPath path1, ReachPath path2);
	
protected:
		
	Paths paths;                    // Percorsi per calcolare i cicli (tabella).
	ShivaStatus status;				// Stato del nodo.
	
	Reachbility reach;              // Percorso per raggiungere un altro nodo BLACK (solo clusterHead).
	// Source, Destination, Reach Path.
	map<NodeAddress, map<NodeAddress, ReachPath> > reachComplete;
	
	NodeList neighbors_on_route;	// Vicini di un nero che sono su almeno una rotta.
	NodeList node_to_turn_off;		
	
	map<NodeAddress, NodeList> forward_path;		// Path di forward (solo nodi gateway).

	int seq;						// Sequence number dei messaggi di Discovery.
	ShivaTimer * timer;				// Gestore dei timeout.
	
	//
	// Buffer dei messaggi di DISCOVERY (per le ritrasmissioni).
	//
	map<int, struct DiscoveryMessage>   myDiscoveryMessages;
	map<NodeAddress, NodeAddress>		myTurnedOn;
	map<NodeAddress, set<int> >			receivedMessagesFrom;
	NodeList							turnOnMessages;		// Vicini che non mi hanno inviato ancora il turn ON.
	map<NodeAddress, bool>				turnOnValues;
	
	NodeAddress							finalClusterHead;   // ClusterHead finale.

	int with_bottom_router;
	
protected:
		
	//////////////
	// Messages //
	//////////////
		
	// Invio di un discover.
	void send_DISCOVER(NodeAddress to, struct DiscoveryMessage message);
	
	// Invio di un TURN ON.
	void send_TURN_ON(NodeAddress to);

	// Invia di una conferma a un messaggio di TURN ON.
	void send_CONFIRM_TURN_ON(NodeAddress to);

	// Ricezione di un pacchetto di DISCOVER: vengono specificati: la provenienza 
	void receive_DISCOVER(NodeAddress from, struct DiscoveryMessage message);
	
	// Ricezione di un pacchetto di TURN ON: viene specificata la provenienza.
	void receive_TURN_ON(NodeAddress from, bool on);
	
	struct DiscoveryMessage createDiscover(int ack_seq, Path path1, Path path2, NodeAddress parent);
	struct DiscoveryMessage createDummyDiscover(int ack_seq, NodeAddress parent);
	
	// Verifica che in un percorso non sia gia'presente un certo nodo nero.
	bool alreadyPresentBlack(Path & path1, Path & path2, NodeAddress node);
	
	NodeAddress greaterCluster();

	void processPhase();
	
private:
		
	// double initialTime;
	
	map<NodeAddress, bool> neighborTurnOn;
	
public:

	static int _DEBUG_;

	static int max_length;							// 3;   // Lunghezza massima dei cicli 
													// (di nodi BLACK) da tagliare
	
	static double max_delay;					// 0.2; // Delay di una broadcast
	
	static double jitter_timeout_destruction;
	static double timeout_destruction;
	
	static int max_timeout_discover;			// 4;   // Numero massimo di timeout al messaggio DISCOVER
	static double jitter_timeout_discover;		// 0.2;	// Jitter per il messaggio DISCOVER.
	static double timeout_discover;			// 1.0;	// Durata timeout messaggio DISCOVER.
	
	static int max_timeout_turn_on;			// 4;   // Numero massimo di timeout al messaggio DISCOVER
	static double jitter_timeout_turn_on;		// 0.2;	// Jitter per il messaggio DISCOVER.
	static double timeout_turn_on;				// 1.0;	// Durata timeout messaggio DISCOVER.
	
};

typedef map<NodeAddress, struct Timeout> FromTimeout;
typedef map<int, FromTimeout> SeqFromTimeout;

/////////////////////////////////
// Timer per le ritrasmissioni //
/////////////////////////////////
class ShivaTimer: public Handler {
public:
	
	ShivaTimer(SHIVA_Agent * a) : Handler(), agent(a) {}
	
	void launchDiscover(NodeAddress to, int seq);
	void cancelDiscover(NodeAddress from, int seq);
	void cancelAllDiscover();
	
	void launchTurnOn(NodeAddress to);
	bool cancelTurnOn(NodeAddress from);
	
	void beginDestruction();
	
	void handle(Event* e);
	
protected:
		
	SHIVA_Agent * agent;
	
	SeqFromTimeout seqFromTimeouts;
	TimeoutMap turn_on_messages;
	Event * begin_cycle_destruction;
	
};

#endif