query.h

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

	ReqProbeTCP(const NodeIdentRendv& in_src_node,
				const set<NodeIdent, ltNodeIdent>& in_remote, 
				MeridianProcess* in_process) 
		: ReqProbeGeneric(in_src_node, in_remote, in_process) {} 	
		
	ReqProbeTCP(const NodeIdentRendv& in_src_node,
				const set<NodeIdentConst, ltNodeIdentConst>& in_remote, 
				MeridianProcess* in_process) 
		: ReqProbeGeneric(in_src_node, in_remote, in_process) {} 	
		
	virtual ~ReqProbeTCP() {}			
	virtual int init();
};


class ReqProbeDNS : public ReqProbeGeneric {
public:
	ReqProbeDNS(const NodeIdentRendv& in_src_node,
				const set<NodeIdent, ltNodeIdent>& in_remote, 
				MeridianProcess* in_process) 
		: ReqProbeGeneric(in_src_node, in_remote, in_process) {}

	ReqProbeDNS(const NodeIdentRendv& in_src_node,
				const set<NodeIdentConst, ltNodeIdentConst>& in_remote, 
				MeridianProcess* in_process) 
		: ReqProbeGeneric(in_src_node, in_remote, in_process) {} 
 		
	virtual ~ReqProbeDNS() {}			
	virtual int init();
};

class ReqProbePing : public ReqProbeGeneric {
public:
	ReqProbePing(const NodeIdentRendv& in_src_node,
				const set<NodeIdent, ltNodeIdent>& in_remote, 
				MeridianProcess* in_process) 
		: ReqProbeGeneric(in_src_node, in_remote, in_process) {}				
				
	ReqProbePing(const NodeIdentRendv& in_src_node,
				const set<NodeIdentConst, ltNodeIdentConst>& in_remote, 
				MeridianProcess* in_process) 				
		: ReqProbeGeneric(in_src_node, in_remote, in_process) {}
 		
	virtual ~ReqProbePing() {}			
	virtual int init();
};

#ifdef PLANET_LAB_SUPPORT
class ReqProbeICMP : public ReqProbeGeneric {
public:
	ReqProbeICMP(const NodeIdentRendv& in_src_node,
				const set<NodeIdent, ltNodeIdent>& in_remote, 
				MeridianProcess* in_process) 
		: ReqProbeGeneric(in_src_node, in_remote, in_process) {}				
				
	ReqProbeICMP(const NodeIdentRendv& in_src_node,
				const set<NodeIdentConst, ltNodeIdentConst>& in_remote, 
				MeridianProcess* in_process) 				
		: ReqProbeGeneric(in_src_node, in_remote, in_process) {}
 		
	virtual ~ReqProbeICMP() {}			
	virtual int init();
};
#endif

enum HandleClosest_SM { 
	HC_INIT, 
	HC_WAIT_FOR_DIRECT_PING, 
	HC_INDIRECT_PING,
	HC_WAIT_FOR_FIN
};

class HandleClosestGeneric : public Query {
private:
	uint64_t												qid;
	u_short													betaNumer;
	u_short													betaDenom;
	u_int													averageLatUS;
	NodeIdentRendv											srcNode;
	bool 													finished;
	NodeIdent												selectedMember;
	struct timeval											timeoutTV;
	MeridianProcess*										meridProcess;
	set<NodeIdent, ltNodeIdent>								remoteNodes;
	set<NodeIdentRendv, ltNodeIdentRendv> 					ringMembers;
	map<NodeIdent, u_int, ltNodeIdent>						remoteLatencies;	
	HandleClosest_SM										stateMachine;
	map<NodeIdent, 
		map<NodeIdent, u_int, ltNodeIdent>*, ltNodeIdent> 	ringLatencies;
	
	static int getMaxAndAverage(
		const map<NodeIdent, u_int, ltNodeIdent>& inMap, 
		u_int* maxValue, u_int* avgValue);

	static int getMaxAndMinAndAverage(
		const map<NodeIdent, u_int, ltNodeIdent>& inMap, 
		u_int* maxValue, u_int* minValue, u_int* avgValue);
		
	int handleForward();	
	int sendReqProbes();
protected:
	MeridianProcess* getMerid() { return meridProcess; 	}
	
	virtual ReqClosestGeneric* createReqClosest(uint64_t id, 
		u_short in_beta_num, u_short in_beta_den, u_int in_rendv_addr, 
		u_short in_rendv_port) = 0;
		
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
		MeridianProcess* in_process) = 0;
		
	virtual ReqProbeGeneric* createReqProbe(const NodeIdentRendv& in_src_node,
		const set<NodeIdent, ltNodeIdent>& in_remote, 
		MeridianProcess* in_process) = 0;
		
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS) = 0;		
	virtual char getQueryType() = 0;

public:
	HandleClosestGeneric(uint64_t id,
			u_short in_betaNumer, u_short in_betaDenom,
			const NodeIdentRendv& in_srcNode, 
			const vector<NodeIdent>& in_remote, 
			MeridianProcess* in_process);			
	virtual ~HandleClosestGeneric();
	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();	
};

class HandleClosestTCP : public HandleClosestGeneric {
protected:
	virtual ReqClosestGeneric* createReqClosest(uint64_t id, 
			u_short in_beta_num, u_short in_beta_den, u_int in_rendv_addr, 
			u_short in_rendv_port) {
		return (new ReqClosestTCP(id, in_beta_num, 
			in_beta_den, in_rendv_addr, in_rendv_port));
	};
		
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryTCP(in_remote, in_process));
	}
		
	virtual ReqProbeGeneric* createReqProbe(const NodeIdentRendv& in_src_node,
				const set<NodeIdent, ltNodeIdent>& in_remote, 
				MeridianProcess* in_process) {
		return (new ReqProbeTCP(in_src_node, in_remote, in_process));					
	}
	
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);
	
	virtual char getQueryType() {
		return REQ_CLOSEST_N_TCP;
	}
	
public:				
	HandleClosestTCP(uint64_t id, u_short in_betaNumer, u_short in_betaDenom,
		const NodeIdentRendv& in_srcNode, const vector<NodeIdent>& in_remote, 
		MeridianProcess* in_process) 
			:	HandleClosestGeneric(id, in_betaNumer, in_betaDenom, in_srcNode, 
				in_remote, in_process) {}
				
	virtual ~HandleClosestTCP() {}
};

class HandleClosestDNS : public HandleClosestGeneric {
protected:
	virtual ReqClosestGeneric* createReqClosest(uint64_t id, 
			u_short in_beta_num, u_short in_beta_den, u_int in_rendv_addr, 
			u_short in_rendv_port) {
		return (new ReqClosestDNS(id, in_beta_num, 
			in_beta_den, in_rendv_addr, in_rendv_port));
	};
		
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryDNS(in_remote, in_process));
	}
		
	virtual ReqProbeGeneric* createReqProbe(const NodeIdentRendv& in_src_node,
				const set<NodeIdent, ltNodeIdent>& in_remote, 
				MeridianProcess* in_process) {
		return (new ReqProbeDNS(in_src_node, in_remote, in_process));					
	}
	
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);
	
	virtual char getQueryType() {
		return REQ_CLOSEST_N_DNS;
	}	
	
public:				
	HandleClosestDNS(uint64_t id, u_short in_betaNumer, u_short in_betaDenom,
		const NodeIdentRendv& in_srcNode, const vector<NodeIdent>& in_remote, 
		MeridianProcess* in_process) 
			:	HandleClosestGeneric(id, in_betaNumer, in_betaDenom, in_srcNode, 
				in_remote, in_process) {}
				
	virtual ~HandleClosestDNS() {}
};


class HandleClosestPing : public HandleClosestGeneric {
protected:
	virtual ReqClosestGeneric* createReqClosest(uint64_t id, 
			u_short in_beta_num, u_short in_beta_den, u_int in_rendv_addr, 
			u_short in_rendv_port) {
		return (new ReqClosestMeridPing(id, in_beta_num, 
			in_beta_den, in_rendv_addr, in_rendv_port));
	};
		
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryPing(in_remote, in_process));
	}
		
	virtual ReqProbeGeneric* createReqProbe(const NodeIdentRendv& in_src_node,
				const set<NodeIdent, ltNodeIdent>& in_remote, 
				MeridianProcess* in_process) {
		return (new ReqProbePing(in_src_node, in_remote, in_process));					
	}
	
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);
	
	virtual char getQueryType() {
		return REQ_CLOSEST_N_MERID_PING;
	}
	
public:				
	HandleClosestPing(uint64_t id, u_short in_betaNumer, u_short in_betaDenom,
		const NodeIdentRendv& in_srcNode, const vector<NodeIdent>& in_remote, 
		MeridianProcess* in_process) 
			:	HandleClosestGeneric(id, in_betaNumer, in_betaDenom, in_srcNode, 
				in_remote, in_process) {}
				
	virtual ~HandleClosestPing() {}
};


#ifdef PLANET_LAB_SUPPORT
class HandleClosestICMP : public HandleClosestGeneric {
protected:
	virtual ReqClosestGeneric* createReqClosest(uint64_t id, 
			u_short in_beta_num, u_short in_beta_den, u_int in_rendv_addr, 
			u_short in_rendv_port) {
		return (new ReqClosestICMP(id, in_beta_num, 
			in_beta_den, in_rendv_addr, in_rendv_port));
	};
		
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryICMP(in_remote, in_process));
	}
		
	virtual ReqProbeGeneric* createReqProbe(const NodeIdentRendv& in_src_node,
				const set<NodeIdent, ltNodeIdent>& in_remote, 
				MeridianProcess* in_process) {
		return (new ReqProbeICMP(in_src_node, in_remote, in_process));					
	}
	
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);
	
	virtual char getQueryType() {
		return REQ_CLOSEST_N_ICMP;
	}
	
public:				
	HandleClosestICMP(uint64_t id, u_short in_betaNumer, u_short in_betaDenom,
		const NodeIdentRendv& in_srcNode, const vector<NodeIdent>& in_remote, 
		MeridianProcess* in_process) 
			:	HandleClosestGeneric(id, in_betaNumer, in_betaDenom, in_srcNode, 
				in_remote, in_process) {}
				
	virtual ~HandleClosestICMP() {}
};
#endif

enum HandleMultiConstraint_SM { 
	HMC_INIT, 
	HMC_WAIT_FOR_DIRECT_PING, 
	HMC_INDIRECT_PING,
	HMC_WAIT_FOR_FIN
};

class HandleMCGeneric : public Query {
private:
	uint64_t												qid;
	u_short													betaNumer;
	u_short													betaDenom;
	u_int													averageLatUS;
	NodeIdentRendv											srcNode;
	bool 													finished;
	NodeIdent												selectedMember;
	struct timeval											timeoutTV;
	MeridianProcess*										meridProcess;
	set<NodeIdentConst, ltNodeIdentConst>					remoteNodes;
	set<NodeIdentRendv, ltNodeIdentRendv> 					ringMembers;
	map<NodeIdent, u_int, ltNodeIdent>						remoteLatencies;	
	HandleMultiConstraint_SM								stateMachine;
	map<NodeIdent, 
		map<NodeIdent, u_int, ltNodeIdent>*, ltNodeIdent> 	ringLatencies;
	
	// Returns the maximum feasible solution that can be within the
	// solution space
	int getMaxSolution(const map<NodeIdent, u_int, ltNodeIdent>& inMap,
			u_int* maxSolution, bool subtract) {
		long long maxSol_LL = 0;
		set<NodeIdentConst, ltNodeIdentConst>::iterator it 
			= remoteNodes.begin();
		for (; it != remoteNodes.end(); it++) {
			NodeIdent tmp = {it->addr, it->port};
			map<NodeIdent, u_int, ltNodeIdent>::const_iterator findIt
				= inMap.find(tmp);
			if (findIt == inMap.end()) {
				ERROR_LOG("Only partial information available");
				return -1;		
			}						
			long long tmpLL = ((long long)findIt->second);
			if (subtract) {
				tmpLL = MAX(0, tmpLL - 
					(((long long)(it->latencyConstMS)) * 1000));
			} else {
				tmpLL += (((long long)(it->latencyConstMS)) * 1000);
			}
			if (tmpLL > maxSol_LL) {
				maxSol_LL = tmpLL;				
			}			
		}
		assert(maxSol_LL >= 0);
		if (maxSol_LL > UINT_MAX) {
			*maxSolution = UINT_MAX;
		} else {
			*maxSolution = (u_int) maxSol_LL; 	
		}
		return 0;
	}	
	
	int getAvgSolution(const map<NodeIdent, u_int, ltNodeIdent>& inMap,
			u_int* latSolution) {
		double totalSolution = 0.0;
		set<NodeIdentConst, ltNodeIdentConst>::iterator it 
			= remoteNodes.begin();
		for (; it != remoteNodes.end(); it++) {
			NodeIdent tmp = {it->addr, it->port};
			map<NodeIdent, u_int, ltNodeIdent>::const_iterator findIt
				= inMap.find(tmp);
			if (findIt == inMap.end()) {
				ERROR_LOG("Only partial information available");
				return -1;		
			}
			long long tmpLL = MAX(0, ((long long)findIt->second) -
				(((long long)(it->latencyConstMS)) * 1000));
			totalSolution += (double)(tmpLL * tmpLL);			
		}
		totalSolution = sqrt(totalSolution) / (remoteNodes.size());
		if (totalSolution > UINT_MAX) {
			*latSolution = UINT_MAX;			
		} else if (totalSolution < 0.0) {
			WARN_LOG("Solution less than 0, shouldn't be possible\n");
			*latSolution = 0;	//	This shouldn't actually happen				
		} else {
			*latSolution = (u_int) totalSolution;	
		}
		return 0;
	}	
	int sendReqProbes();		
	int handleForward();
protected:
	MeridianProcess* getMerid()  { return meridProcess; }

	virtual ReqConstraintGeneric* createReqConstraint(uint64_t id, 
		u_short in_beta_num, u_short in_beta_den, u_int in_rendv_addr, 
		u_short in_rendv_port) = 0;
		
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
		MeridianProcess* in_process) = 0;
		
	virtual ReqProbeGeneric* createReqProbe(const NodeIdentRendv& in_src_node,
		const set<NodeIdentConst, ltNodeIdentConst>& in_remote, 
		MeridianProcess* in_process) = 0;
			
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS) = 0;		
	virtual char getQueryType() = 0;
	
public:
	HandleMCGeneric::HandleMCGeneric(uint64_t id,
			u_short in_betaNumer, u_short in_betaDenom,
			const NodeIdentRendv& in_srcNode, 
			const vector<NodeIdentConst>& in_remote, 
			MeridianProcess* in_process);			
	virtual ~HandleMCGeneric();
	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();	
};

class HandleMCTCP : public HandleMCGeneric {
protected:
	virtual ReqConstraintGeneric* createReqConstraint(uint64_t id, 
			u_short in_beta_num, u_short in_beta_den, u_int in_rendv_addr, 
			u_short in_rendv_port)  {
		return (new ReqConstraintTCP(id, in_beta_num, 
			in_beta_den, in_rendv_addr, in_rendv_port));			
	}
		
	virtual ProbeQueryGeneric* createProbeQuery(const NodeIdent& in_remote, 
			MeridianProcess* in_process) {
		return (new ProbeQueryTCP(in_remote, in_process));	
	}
		
	virtual ReqProbeGeneric* createReqProbe(const NodeIdentRendv& in_src_node,
			const set<NodeIdentConst, ltNodeIdentConst>& in_remote, 
			MeridianProcess* in_process) {
		return (new ReqProbeTCP(in_src_node, in_remote, in_process));		
	}
	
	virtual int getLatency(const NodeIdent& inNode, uint32_t* latencyUS);

	virtual char getQueryType() {
		return REQ_CONSTRAINT_N_TCP;
	}
	
public:				
	HandleMCTCP(uint64_t id, u_short in_betaNumer, u_short in_betaDenom,
		const NodeIdentRendv& in_srcNode, 
		const vector<NodeIdentConst>& in_remote, MeridianProcess* in_process) 
			:	HandleMCGeneric(id, in_betaNumer, in_betaDenom, in_srcNode, 
				in_remote, in_process) {}
				
	virtual ~HandleMCTCP() {}
};

class HandleMCPing : public HandleMCGeneric {
protected:
	virtual ReqConstraintGeneric* createReqConstraint(uint64_t id, 
			u_short in_beta_num, u_short in_beta_den, u_int in_rendv_addr, 
			u_short in_rendv_port)  {
		return (new ReqConstraintPing(id, in_beta_num, 
			in_beta_den, in_rendv_addr, in_rendv_port));			
	}