query.h

件主要用于帮助计算机爱好者学习蚁群算法时做有关蚁群算法的试验。蚁群算法作为一种优秀的新兴的算法

#ifndef CLASS_QUERY
#define CLASS_QUERY

#include <stdint.h>
#include <sys/time.h>
#include <assert.h>
#include <map>
#include <set>
#include "RingSet.h"
#include "Marshal.h"

extern "C" {
	#include <qhull/qhull.h>
	#include <atlas/cblas.h>	
}

class MeridianProcess;

#define MICRO_IN_MILLI	1000
#define MINI_IN_SECOND	1000
#define MICRO_IN_SECOND	1000000
#define MAX_RTT_MS		5000

class SchedObject {
public:
	virtual int runOnce() = 0;
	virtual ~SchedObject() {}
};

class SchedGossip : public SchedObject {
private:	
	MeridianProcess* meridProcess;
public:
	SchedGossip(MeridianProcess* in_process) : meridProcess(in_process) {}
	virtual int runOnce();
	virtual ~SchedGossip() {}
};

class SchedRingManage : public SchedObject {
private:	
	MeridianProcess* meridProcess;
public:
	SchedRingManage(MeridianProcess* in_process) : meridProcess(in_process) {}
	virtual int runOnce();
	virtual ~SchedRingManage() {}
};

//	Base interface class 
class Query {
protected:
	static void computeTimeout(
			u_int periodUS, struct timeval* nextTimeOut) {
		struct timeval curTime;
		gettimeofday(&curTime, NULL);	
		struct timeval offsetTV = 
				{ periodUS / MICRO_IN_SECOND, periodUS % MICRO_IN_SECOND}; 			
		timeradd(&curTime, &offsetTV, nextTimeOut);				
	}
	
public:
	virtual uint64_t getQueryID() const = 0;	
	virtual struct timeval timeOut() const = 0;
	virtual int init() = 0;
	virtual int handleEvent(
		const NodeIdent& in_remote, const char* inPacket, int packetSize) = 0;
	// Used primarily between queries
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes) = 0;
	virtual int handleTimeout() = 0;
	virtual bool isFinished() const = 0;
	virtual int subscribeLatency(uint64_t in_qid) 	{ 
		ERROR_LOG("Unhandled subscribeLatency call\n"); 
		return 0; 
	}
	virtual ~Query() {}	
};

class AddNodeQuery : public Query {
private:
	uint64_t			qid;
	NodeIdentRendv		remoteNode;
	bool 				finished;
	struct timeval		startTime;
	struct timeval		timeoutTV;
	MeridianProcess*	meridProcess;
	vector<uint64_t>	subscribers;	
public:
	AddNodeQuery(const NodeIdentRendv& in_remote, 
				MeridianProcess* in_process);
	virtual ~AddNodeQuery() {}	
	virtual uint64_t getQueryID() const				{ return qid;		}
	virtual struct timeval timeOut() const			{ return timeoutTV;	} 	
	virtual int handleEvent(
		const NodeIdent& in_remote, 
		const char* inPacket, int packetSize);
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes);
	virtual int handleTimeout();
	virtual bool isFinished() const					{ return finished;	}		
	virtual int init();
	virtual int subscribeLatency(uint64_t in_qid);
};

class GossipQuery : public Query {
private:
	uint64_t			qid;	
	//NodeIdent			remoteNode;
	NodeIdentRendv		remoteNode;
	bool 				finished;
	struct timeval		startTime;
	struct timeval		timeoutTV;
	MeridianProcess*	meridProcess;	
public:
	GossipQuery(NodeIdentRendv& in_remote, MeridianProcess* in_process);
	virtual ~GossipQuery() {}	
	virtual uint64_t getQueryID() const				{ return qid;		}
	virtual struct timeval timeOut() const			{ return timeoutTV;	} 	
	virtual int handleEvent(
		const NodeIdent& in_remote, 
		const char* inPacket, int packetSize)		{ return 0;			}
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes);
	virtual int handleTimeout();
	virtual bool isFinished() const					{ return finished;	}
	virtual int init();
	static int fillGossipPacket(GossipPacketGeneric& in_packet, 
		const NodeIdentRendv& in_target, MeridianProcess* in_merid);
};

class SearchQuery : public Query {
private:
	uint64_t qid;
public :
	SearchQuery(uint64_t id) : qid(id) {}
	virtual ~SearchQuery() {}	
	virtual uint64_t getQueryID() const				{ return qid;		}
	virtual struct timeval timeOut() const			{ assert(false);	}	
	virtual int handleEvent(
		const NodeIdent& in_remote, 
		const char* inPacket, int packetSize) 		{ assert(false);	}	
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes)	{ assert(false); 	}
	virtual int handleTimeout()						{ assert(false); 	}
	virtual bool isFinished() const					{ assert(false);	}
	virtual int init()								{ assert(false);	}	
};


class QueryScheduler : public Query {
private:	
	uint64_t			qid;
	SchedObject*		schedObj;
	struct timeval		timeoutTV;
	u_int				initInterval_MS;
	u_int				numInitInterval;
	u_int				ssInterval_MS;
	MeridianProcess* 	meridProcess;	
	bool				finished;	
	void computeSchedTimeout();
public:
	QueryScheduler(u_int in_initInterval_MS, u_int in_numInitInterval, 
				u_int in_ssInterval_MS, MeridianProcess* in_process, 
				SchedObject* in_schedObj);
	virtual ~QueryScheduler() {}	 
	virtual uint64_t getQueryID() const				{ return qid;		}
	virtual struct timeval timeOut() const			{ return timeoutTV;	}	
	virtual int handleEvent(
		const NodeIdent& in_remote, 
		const char* inPacket, int packetSize) 		{ return 0;			}	
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes)	{ return 0;			}
	virtual int handleTimeout();
	virtual bool isFinished() const					{ return finished;	}
	virtual int init() 								{ return 0;			}
	int removeScheduler();
};

class RingManageQuery : public Query {
private:
	uint64_t						qid;
	int								ringNum;
	set<NodeIdent, ltNodeIdent>		remoteNodes;	
	bool 							finished;
	struct timeval					startTime;
	struct timeval					timeoutTV;
	MeridianProcess*				meridProcess;
	map<NodeIdent, map<NodeIdent, u_int, ltNodeIdent>*, ltNodeIdent> RetNodeMap;
	
	int performReplacement();
	double* createLatencyMatrix(); 		
	int removeCandidateNode(const NodeIdent& in_node);
	double getVolume(coordT* points, int dim, int numpoints);
	double calculateHV(
		const int N,					// Physical size of the latencyMatrix
		const int NPrime,				// Size of the latencyMatrix in use
		double* latencyMatrix);			// Pointer to latencyMatrix
	double reduceSetByN(
		vector<NodeIdent>& inVector,	// Vector of nodes
		vector<NodeIdent>& deletedNodes,
		int numReduction,				// How many nodes to remove
		double* latencyMatrix);			// Pointer to latencyMatrix			
public:
	RingManageQuery(int in_ringNum,	MeridianProcess* in_process);
	virtual ~RingManageQuery() {
		map<NodeIdent, map<NodeIdent, u_int, ltNodeIdent>*, ltNodeIdent>::
			iterator it = RetNodeMap.begin();
		for (; it != RetNodeMap.end(); it++) {
			if (it->second != NULL) {
				delete it->second;	// Delete all entries
			}
		}				
	}	
	virtual uint64_t getQueryID() const				{ return qid;		}
	virtual struct timeval timeOut() const			{ return timeoutTV;	} 	
	virtual int handleEvent(
		const NodeIdent& in_remote, 
		const char* inPacket, int packetSize);	
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes)	{ return 0;			}
	virtual int handleTimeout();
	virtual bool isFinished() const					{ return finished;	}
	virtual int init();		
};


class ProbeQueryGeneric : public Query {
private:
	int					sockFD;
	uint64_t 			qid;
	NodeIdent			remoteNode;
	bool 				finished;
	struct timeval		startTime;
	struct timeval		timeoutTV;
	MeridianProcess*	meridProcess;
	vector<uint64_t>	subscribers;	
protected:
	NodeIdent getRemoteNode() const		{ return remoteNode;				}
	void setSockFD(int fd)				{ sockFD = fd;						}
	int getSockFD()	const				{ return sockFD;					}
	struct timeval getStartTime() const	{ return startTime;					}
	void setStartTime() 				{ gettimeofday(&startTime, NULL); 	}		
	MeridianProcess* getMerid() 		{ return meridProcess; 				}
	void setFinished(bool flag)			{ finished = flag;					}

	virtual void insertCache(const NodeIdent& inNode, uint32_t latencyUS) = 0;
	
public:
	ProbeQueryGeneric(const NodeIdent& in_remote, MeridianProcess* in_process);				
	virtual ~ProbeQueryGeneric() {}	
	virtual uint64_t getQueryID() const				{ return qid;		}
	virtual struct timeval timeOut() const			{ return timeoutTV;	} 	
	virtual int handleEvent(
		const NodeIdent& in_remote, 
		const char* inPacket, int packetSize);
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes);
	virtual int handleTimeout() = 0;
	virtual bool isFinished() const					{ return finished;	}		
	virtual int init() = 0;					
	virtual int subscribeLatency(uint64_t in_qid);
};

class ProbeQueryTCP : public ProbeQueryGeneric {
protected:
	virtual void insertCache(const NodeIdent& inNode, uint32_t latencyUS);
public:
	ProbeQueryTCP(const NodeIdent& in_remote, MeridianProcess* in_process)
		: ProbeQueryGeneric(in_remote, in_process) {}				
	virtual ~ProbeQueryTCP() {}	
	virtual int handleTimeout();			
	virtual int init();					
};

class ProbeQueryDNS : public ProbeQueryGeneric {
protected:	
	virtual void insertCache(const NodeIdent& inNode, uint32_t latencyUS);
public:
	ProbeQueryDNS(const NodeIdent& in_remote, MeridianProcess* in_process)
		: ProbeQueryGeneric(in_remote, in_process) {}				
	virtual ~ProbeQueryDNS() {}	
	virtual int handleTimeout();			
	virtual int init();					
};

class ProbeQueryPing : public ProbeQueryGeneric {
protected:	
	virtual void insertCache(const NodeIdent& inNode, uint32_t latencyUS);	
public:
	ProbeQueryPing(const NodeIdent& in_remote, MeridianProcess* in_process)
		: ProbeQueryGeneric(in_remote, in_process) {}				
	virtual ~ProbeQueryPing() {}	
	virtual int handleTimeout();			
	virtual int init();					
};

#ifdef PLANET_LAB_SUPPORT
class ProbeQueryICMP : public ProbeQueryGeneric {
protected:	
	virtual void insertCache(const NodeIdent& inNode, uint32_t latencyUS);	
public:
	ProbeQueryICMP(const NodeIdent& in_remote, MeridianProcess* in_process)
		: ProbeQueryGeneric(in_remote, in_process) {}				
	virtual ~ProbeQueryICMP() {}	
	virtual int handleTimeout();			
	virtual int init();					
};
#endif


class HandleReqGeneric : public Query {
private:		
	uint64_t							qid;	
	NodeIdentRendv						srcNode;
	bool 								finished;
	//struct timeval						startTime;
	struct timeval						timeoutTV;
	MeridianProcess*					meridProcess;
	set<NodeIdent, ltNodeIdent>			remoteNodes;	
	map<NodeIdent, u_int, ltNodeIdent>	remoteLatencies;
protected:
	NodeIdentRendv getSrcNode()						{ return srcNode;		}
	set<NodeIdent, ltNodeIdent>* getRemoteNodes() 	{ return &remoteNodes; 	}
	MeridianProcess* getMerid() 					{ return meridProcess; 	}
	void setFinished(bool flag)						{ finished = flag;		}
	//void setStartTime() 				{ gettimeofday(&startTime, NULL); 	}
	
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
		MeridianProcess* in_process) = 0;
		
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS) = 0;
		
public:
	HandleReqGeneric(uint64_t id, const NodeIdentRendv& in_srcNode, 
					const vector<NodeIdent>& in_remote, 
					MeridianProcess* in_process);
	virtual ~HandleReqGeneric() {}	
	virtual uint64_t getQueryID() const				{ return qid;		}
	virtual struct timeval timeOut() const			{ return timeoutTV;	} 	
	virtual int handleEvent(
		const NodeIdent& in_remote, 
		const char* inPacket, int packetSize)		{ return 0;			}		
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes);
	virtual int handleTimeout();
	virtual bool isFinished() const					{ return finished;	}	
	virtual int init();		
	int sendReturnPacket();
};

class HandleReqPing : public HandleReqGeneric {
protected:
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryPing(in_remote, in_process));	
	}
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);
public:
	HandleReqPing(uint64_t id, const NodeIdentRendv& in_srcNode, 
					const vector<NodeIdent>& in_remote, 
					MeridianProcess* in_process) 
		: HandleReqGeneric(id, in_srcNode, in_remote, in_process) {}
	virtual ~HandleReqPing() {}		
	//virtual int init();
};

class HandleReqTCP : public HandleReqGeneric {
protected:
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryTCP(in_remote, in_process));	
	}
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);
public:
	HandleReqTCP(uint64_t id, const NodeIdentRendv& in_srcNode, 
					const vector<NodeIdent>& in_remote, 
					MeridianProcess* in_process)
		: 	HandleReqGeneric(id, in_srcNode, in_remote, in_process) {}
	virtual ~HandleReqTCP() {}
	//virtual int init();		
};

class HandleReqDNS : public HandleReqGeneric {
protected:
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryDNS(in_remote, in_process));	
	}
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);
public:
	HandleReqDNS(uint64_t id, const NodeIdentRendv& in_srcNode, 
					const vector<NodeIdent>& in_remote, 
					MeridianProcess* in_process)
		: 	HandleReqGeneric(id, in_srcNode, in_remote, in_process) {}
	virtual ~HandleReqDNS() {}
	//virtual int init();		
};

#ifdef PLANET_LAB_SUPPORT
class HandleReqICMP : public HandleReqGeneric {
protected:
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryICMP(in_remote, in_process));	
	}
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);
public:
	HandleReqICMP(uint64_t id, const NodeIdentRendv& in_srcNode, 
					const vector<NodeIdent>& in_remote, 
					MeridianProcess* in_process) 
		: HandleReqGeneric(id, in_srcNode, in_remote, in_process) {}
	virtual ~HandleReqICMP() {}		
	//virtual int init();
};
#endif

class ReqProbeGeneric : public Query {
private:
	uint64_t					qid;
	NodeIdentRendv				srcNode;
	set<NodeIdent, ltNodeIdent>	remoteNodes;
	bool 						finished;
	struct timeval				timeoutTV;
	MeridianProcess*			meridProcess;
	vector<uint64_t>			subscribers;
protected:
	NodeIdentRendv getSrcNode()						{ return srcNode;		}
	set<NodeIdent, ltNodeIdent>* getRemoteNodes() 	{ return &remoteNodes; 	}
	MeridianProcess* getMerid() 					{ return meridProcess; 	}
	void setFinished(bool flag)						{ finished = flag;		}
	
public:
	ReqProbeGeneric(const NodeIdentRendv& in_src_node,
					const set<NodeIdent, ltNodeIdent>& in_remote, 
					MeridianProcess* in_process);
					
	ReqProbeGeneric(const NodeIdentRendv& in_src_node,
					const set<NodeIdentConst, ltNodeIdentConst>& in_remote, 
					MeridianProcess* in_process);	
					
	virtual ~ReqProbeGeneric() {}	
	virtual uint64_t getQueryID() const				{ return qid;		}
	virtual struct timeval timeOut() const			{ return timeoutTV;	} 	
	virtual int handleEvent(
		const NodeIdent& in_remote, 
		const char* inPacket, int packetSize);		
	virtual int handleLatency(
		const vector<NodeIdentLat>& in_remoteNodes)	{ return 0;			}
	virtual int handleTimeout();	
	virtual bool isFinished() const					{ return finished;	}		
	virtual int init() = 0;	
	virtual int subscribeLatency(uint64_t in_qid);
};

class ReqProbeTCP : public ReqProbeGeneric {
public: