topology.cpp

模拟P2P各种网络环境的,适合新手们的学习,不错的源码.

		if(debug)
		cout << "band generation on" << endl;
		for(map<string, Link>::iterator it = mLink.begin(); it != mLink.end(); it++)
		{
			if(bandGenerateMethod == "CONST")
			{
				if((*it).second.getType() == STU_STU)
					if(congestEstimation == "ON")
						(*it).second.setBandwidth((unsigned long)calculateBandwidth(mss, rtt, loss, c, minSSB));
					else
						(*it).second.setBandwidth(minSSB);
				if((*it).second.getType() == STU_TRA)
					if(congestEstimation == "ON")
						(*it).second.setBandwidth((unsigned long)calculateBandwidth(mss, rtt, loss, c, minSTB));
					else				
						(*it).second.setBandwidth(minSTB);
				else if((*it).second.getType() == TRA_TRA_INTRA)
					if(congestEstimation == "ON")
						(*it).second.setBandwidth((unsigned long)calculateBandwidth(mss, rtt, loss, c, minIntraTTB));
					else
						(*it).second.setBandwidth(minIntraTTB);
				else if((*it).second.getType() == TRA_TRA_INTER)
					if(congestEstimation == "ON")
						(*it).second.setBandwidth((unsigned long)calculateBandwidth(mss, rtt, loss, c, minInterTTB));
					else
						(*it).second.setBandwidth(minInterTTB);
				else {
					cout << "unkown edge type encountered when configure topology object" << endl;
					exit(-1);
				}
			}
			else if(bandGenerateMethod == "UNIFORM")
			{
				double band;
				double k = random();
				if((*it).second.getType() == STU_STU) {
					unsigned long interval = maxSSB - minSSB;
					band = minSSB + k / RAND_MAX * interval;
				}
				else if((*it).second.getType() == STU_TRA) {
					unsigned long interval = maxSTB - minSTB;
					band = minSTB + k / RAND_MAX * interval;
				}
				else if((*it).second.getType() == TRA_TRA_INTRA) {
					unsigned long interval = maxIntraTTB - minIntraTTB;
					band = minIntraTTB + k / RAND_MAX * interval;
				}
				else if((*it).second.getType() == TRA_TRA_INTER) {
					unsigned long interval = maxInterTTB - minInterTTB;
					band = minInterTTB + k / RAND_MAX * interval;
				}
				else {
					cout << "unkown edge type encountered when initialize topology object" << endl;
					exit(-1);
				}
				if(congestEstimation == "ON")
					(*it).second.setBandwidth((unsigned long)calculateBandwidth(mss, rtt, loss, c, band));
				else
					(*it).second.setBandwidth((unsigned long)band);
			}
			else if(bandGenerateMethod == "EXPONENT") {
				double band;
				double p = (double)random() / RAND_MAX;
				if(p < PMIN)
					p = PMIN;
				else if(p > PMAX)
					p = PMAX;
				band = 0 - log(1 - p) / beta;
				if((*it).second.getType() == STU_STU)
					band += minSSB;
				else if((*it).second.getType() == STU_TRA)
					band += minSTB;
				else if((*it).second.getType() == TRA_TRA_INTRA)
					band += minIntraTTB;
				else if((*it).second.getType() == TRA_TRA_INTER)
					band += minInterTTB;
				else {
					cout << "unkown edge type encountered when initialize topology object" << endl;
					exit(-1);
				}
				if(congestEstimation == "ON")
					(*it).second.setBandwidth((unsigned long)calculateBandwidth(mss, rtt, loss, c, band));
				else
					(*it).second.setBandwidth((unsigned long)band);
			}
			else {
				cout << "band generation method aren't support" << endl;
				exit(-1);
			}
		}
	}
	else if(bandGenerateMethod == "OFF" && congestEstimation == "ON") {
		for(it = mLink.begin(); it != mLink.end(); it++)
			(*it).second.setBandwidth((unsigned long)calculateBandwidth(mss, rtt, loss, c, (*it).second.getProperty().getBandwidth()));
	}

	/* configure the whole domain */
	for(map<string, Link>::iterator it = mLink.begin(); it != mLink.end(); it++) {
		mPredecessorMatrix[(*it).second.from()][(*it).second.to()] = 1;
		mPredecessorMatrix[(*it).second.to()][(*it).second.from()] = 1;
		mDelayMatrix[(*it).second.from()][(*it).second.to()] = (*it).second.getProperty().getDelay();
		mDelayMatrix[(*it).second.to()][(*it).second.from()] = (*it).second.getProperty().getDelay();
	}

	/* configure mDomain */
	/* configure stub domain */
	for(it = mLink.begin(); it != mLink.end(); it++)
	{
		/* note: in our graph id = mNode[id].getID() */
		int from = (*it).second.from();
		int to = (*it).second.to();
		int aidFrom = mNode[from].getAID();
		int aidTo = mNode[to].getAID();
		if(aidFrom != aidTo)
			continue;
		int indexFrom = mDomain[aidFrom].reverseMapTable[from];
		int indexTo = mDomain[aidTo].reverseMapTable[to];
		mDomain[aidFrom].predecessorMatrix[indexFrom][indexTo] = 1;
		mDomain[aidFrom].predecessorMatrix[indexTo][indexFrom] = 1;
		mDomain[aidFrom].delayMatrix[indexFrom][indexTo] = (*it).second.getProperty().getDelay();
		mDomain[aidFrom].delayMatrix[indexTo][indexFrom] = (*it).second.getProperty().getDelay();
	}

	/* configure transit domain */
	for(it = mLink.begin(); it != mLink.end(); it++)
	{
		int from = (*it).second.from();
		int to = (*it).second.to();
		int typeFrom = mNode[from].getType();
		int typeTo = mNode[to].getType();
		if(typeFrom != TRANSIT || typeTo != TRANSIT)
			continue;
		int indexFrom = mDomain[mAsNumber].reverseMapTable[from];
		int indexTo = mDomain[mAsNumber].reverseMapTable[to];
		mDomain[mAsNumber].predecessorMatrix[indexFrom][indexTo] = 1;
		mDomain[mAsNumber].predecessorMatrix[indexTo][indexFrom] = 1;
		mDomain[mAsNumber].delayMatrix[indexFrom][indexTo] = (*it).second.getProperty().getDelay();
		mDomain[mAsNumber].delayMatrix[indexTo][indexFrom] = (*it).second.getProperty().getDelay();
	}

	if(debug)
		cout <<mDomain[mAsNumber].delayMatrix << endl;

	if(debug && dataFile != "OFF")
		cout << "floyd algoritm" << endl;


	if(dataFile == "OFF")
	{	
		/* calculate delay matrix and predecessor matrix of each domain and delay matrix of the whole graph*/
		/* predecessor matrix of the whole graph is not in use here and it's function is subsituted by each domain predecessor matrix */
		for(i = 0; i <= (unsigned int)mAsNumber; i++)
			FloydWarshall(mDomain[i].number, mDomain[i].predecessorMatrix, mDomain[i].delayMatrix);
		for(i = 0; i < (unsigned int)mNodeNumber; i++)
			for(j = i + 1; j < (unsigned int)mNodeNumber; j++)
			{
				if(i == j)
					continue;
				int aidi = mNode[i].getAID();
				int aidj = mNode[j].getAID();
				int typei = mNode[i].getType();
				int typej = mNode[j].getType();

				if(aidi == aidj)
				{
					int indexi = mDomain[aidi].reverseMapTable[i];
					int indexj = mDomain[aidj].reverseMapTable[j];
					mDelayMatrix[i][j] = mDomain[aidi].delayMatrix[indexi][indexj];
					mDelayMatrix[j][i] = mDomain[aidi].delayMatrix[indexi][indexj];
					continue;
				}
				
				if(typei == typej && typei == TRANSIT)
				{
					int indexi = mDomain[mAsNumber].reverseMapTable[i];
					int indexj = mDomain[mAsNumber].reverseMapTable[j];
					mDelayMatrix[i][j] = mDomain[mAsNumber].delayMatrix[indexi][indexj];
					mDelayMatrix[j][i] = mDomain[mAsNumber].delayMatrix[indexj][indexi];
					continue;
				}
				
				int indexi = mDomain[aidi].reverseMapTable[i];
				int indexj = mDomain[aidj].reverseMapTable[j];

				set<int> &transitTablei = mDomain[aidi].transitTable;
				set<int> &transitTablej = mDomain[aidj].transitTable;
				set<int>::iterator iti;
				set<int>::iterator itj;

				unsigned long delay = UINT_MAX;

				for(iti = transitTablei.begin(); iti != transitTablei.end(); iti++)
				{
					int ida = mDomain[aidi].mapTable[*iti];
					int indexa = mDomain[mAsNumber].reverseMapTable[ida];	
					unsigned long delayItoA = mDomain[aidi].delayMatrix[indexi][*iti];
					for(itj = transitTablej.begin(); itj != transitTablej.end(); itj++)
					{
						int idb = mDomain[aidj].mapTable[*itj];
						int indexb = mDomain[mAsNumber].reverseMapTable[idb];
						unsigned long delayAtoB = mDomain[mAsNumber].delayMatrix[indexa][indexb];
						unsigned long delayBtoJ = mDomain[aidj].delayMatrix[*itj][indexj];
						if(delay > delayItoA + delayAtoB + delayBtoJ)
							delay = delayItoA + delayAtoB + delayBtoJ;
					}
					mDelayMatrix[i][j] = delay;
					mDelayMatrix[j][i] = delay;
				}
			}
		/*FloydWarshall(mNodeNumber, mPredecessorMatrix, mDelayMatrix);*/
	}
	else {
		FILE *fp;
		if(!(fp = fopen(dataFile.c_str(), "r")))
		{
			cout << "open for reading error" << endl;
			exit(-1);
		}
		for(i = 0; i <= (unsigned int)mAsNumber; i++)
		{
			if(ReadData(mDomain[i].predecessorMatrix, fp) == -1)
			{
				cout << "ReadData() failed" << endl;
				exit(-1);
			}
			if(ReadData(mDomain[i].delayMatrix, fp) == -1)
			{
				cout << "ReadData() failed" << endl;
				exit(-1);
			}
		}
		if(ReadData(mDelayMatrix, fp) == -1)
		{
			cout << "ReadData() failed" << endl;
			exit(-1);
		}
		fclose(fp);
/*
		if(ReadData(mDelayMatrix, mPredecessorMatrix, dataFile.c_str()) == -1) {
			cout << "ReadData() failed" << endl;
			exit(-1);
		}
*/
	}
	if(debug)
	{
		cout << "matix information" << endl;
		cout << "******************************************************" << endl;
		
		cout << "node = " << mNodeNumber << endl;
		cout << "edge = " << mLinkNumber << endl;
		cout << "******************************************************" << endl;

		cout << mNode << endl;
		cout << "******************************************************" << endl;

		cout << mLink << endl;
		cout << "******************************************************" << endl;
		
		cout << mPredecessorMatrix << endl;
		cout << "******************************************************" << endl;

		cout << mDelayMatrix << endl;
		cout << "******************************************************" << endl;

		
	}
}

double Topology::calculateBandwidth(double mss, double rtt, double p, double c, double band)
{ return mss * c * 1000 / (rtt * sqrt(p)); }



void Topology::writeData(const char *file)
{
	int i;
	FILE *fp;
	
	if(!(fp = fopen(file, "w")))
	{
		cout << "you can not create or truncate file to zero" << endl;
		exit(-1);
	}
	fclose(fp);
	
	for(i = 0; i <= mAsNumber; i++)
	{
		if(WriteData(mDomain[i].predecessorMatrix, file) == -1)
		{
			cout << "WriteData failed" << endl;
			exit(-1);
		}
		if(WriteData(mDomain[i].delayMatrix, file) == -1)
		{
			cout << "WriteData failed" << endl;
			exit(-1);
		}
	}
	if(WriteData(mDelayMatrix, file) == -1)
	{
		cout << "WriteData failed" << endl;
		exit(-1);
	}
/*
	if(WriteData(mDelayMatrix, mPredecessorMatrix, file) == -1)
	{
		cout << "WriteData() failed" << endl;
		exit(-1);
	}
*/
}




/*
 * FloydWarshall algorithm to calculate all pairs delay and predecessor matrix.
 * Originally written by Rahul Simha
 */
#define MAX_VALUE RAND_MAX
static void FloydWarshall(int n, vector< vector<int> >&Pk, vector< vector<unsigned long> > &Dk)
{
	int i, j;
	int k;
	/* Matrices used in dynamic programming */
	vector< vector<int> > Pk_minus_one = Pk;

	/* Adjacent Matrix */
	vector< vector<int> > adjMatrix = Pk;

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			if(Pk[i][j] == 1)
				adjMatrix[i][j] = 1;
			else
				adjMatrix[i][j] = 0;

	/* Matrices used in dynamic programming */
	vector< vector<unsigned long> > Dk_minus_one = Dk; 


	/* initialization matrix */
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			Pk[i][j] = -1;
			Pk_minus_one[i][j] = -1;
		}

	/* calculates all pairs delay
	 * param PK: first is adjacent matrix and later is predecessor matrix
	 * param Dk: stores all pairs delay matrix
	 */
	/* Dk_minus_one = weights when k = -1 */
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			if(adjMatrix[i][j] == 1) {
				Dk_minus_one[i][j] = Dk[i][j];
				Pk_minus_one[i][j] = i;
			}
			else {
				Dk_minus_one[i][j] = DELAY_MAX;
				Pk_minus_one[i][j] = -1;
			}
		}
	}
	/* NOTE: we have set the value to infinity and will exploit */
	/* this to avoid a comparison. */
	/* Now iterate over k. */

	for(k=0; k < n; k++) {
		/* Compute Dk[i][j], for each i, j */
		for(i = 0; i < n; i++) {
			for(j=0; j < n; j++) {
				if(i != j) {

					/* D_k[i][j] = min ( D_k-1[i][j], D_k-1[i][k] + D_k-1[k][j]. */
					if(Dk_minus_one[i][j] <= Dk_minus_one[i][k] + Dk_minus_one[k][j]) {
						Dk[i][j] = Dk_minus_one[i][j];
						Pk[i][j] = Pk_minus_one[i][j];
					}
					else {
						Dk[i][j] = Dk_minus_one[i][k] + Dk_minus_one[k][j];
						Pk[i][j] = Pk_minus_one[k][j];
					}
				}
				else
					Pk[i][j] = -1;
			}
		}

		/* Now store current Dk into D_k-1 */
		for (int i=0; i < n; i++) {
			for (int j=0; j < n; j++) {
				Dk_minus_one[i][j] = Dk[i][j];
				Pk_minus_one[i][j] = Pk[i][j];
			}
		}
	}   
	for (int i=0; i < n; i++) {
		for (int j=0; j < n; j++) {
			if(Pk[i][j] < 0)
				Pk[i][j] = -1;
			}
		}
}


ostream &operator<<(ostream &os, const vector< vector<int> > &vec)
{
	for(unsigned int i = 0; i < vec.size(); i++)
		for(unsigned int j = 0; j < vec.size(); j++)
				os << '(' << i << ", " << j << "): " << vec[i][j] << ((j == vec.size() -1) ? '\n' : '\t');
		return os;
}

ostream &operator<<(ostream &os, const vector< vector<unsigned long> > &vec)
{
	for(unsigned int i = 0; i < vec.size(); i++)
		for(unsigned int j = 0; j < vec.size(); j++)
				os << '(' << i << ", " << j << ") = " << vec[i][j] << ((j == vec.size() - 1) ? '\n' : ' ');
	return os;
}

ostream &operator<<(ostream &os, const vector<Node> &vec)
{
	for(unsigned int i = 0; i < vec.size(); i++)		
			os << vec[i] << endl;
	return os;
}

ostream &operator<<(ostream &os, map<string, Link> &vec)
{
	for(map<string, Link>::iterator it = vec.begin(); it != vec.end(); it++)		
		os << (*it).second << endl;
	return os;
}

static string intToString(int i, int j)
{
	char buf[BUFSIZ];
	string temp;
	
	snprintf(buf, BUFSIZ, "%4.4x%4.4x", i, j);
	temp = buf;
	return temp;
}