node2.c

一个linux下的各种组播路由算法编程

  Node *nd1, *nd2;
  int *connected = new int[num];
  for (i = 0; i < num; i++) *(connected + i) = 0;
  n1 = 0;
  nd1 = nodeOf(n1);

  while (links < 2) {
    n2 = (int)(ran() * num);
    if (n2 != n1) {
      nd2 = nodeOf(n2);
      AdjacencyListEntry *adj = nd1->adjacentNodes();
      int found = False;
      while ((adj != NULL) && (found == False)) {
	if (adj->nodePtr() == nd2) found = True;
	else adj = adj->next();
      };
      if (found == False) {
	d = distance(nd1, nd2);
	p1 = edgeProb(alpha, beta, L, d);
	p2 = ran();
	if (p2 <= p1) { 
	  //an edge exists;
	  links++;
	  nd1->addNeighbor(nd2, defaultCapacity);
	  nd2->addNeighbor(nd1, defaultCapacity);
	  *(connected + n2) = 1;
	};
      };
    };
  };
  *connected = 2;

  int j, quit = False;
  j = 0;
  while (quit == False) {
    quit = True;
    for (i = 0; i < num; i++) {
      n1 = i;
      nd1 = nodeOf(n1);
      int conn = False;
      if (*(connected + n1) < 1) {
	while ((j < num) && (conn == False)) {
	  n2 = j;
	  if ((n2 != n1) && (*(connected + n2) >= 1)) {
	    nd2 = nodeOf(n2);
	    d = distance(nd1, nd2);
	    p1 = edgeProb(alpha, beta, L, d);
	    p2 = ran();
	    if (p2 <= p1) { 
	      //an edge exists;
	      links++;
	      nd1->addNeighbor(nd2, defaultCapacity);
	      nd2->addNeighbor(nd1, defaultCapacity);
	      *(connected + n1) = 1;
	      *(connected + n2) += 1;
	      conn = True;
	    };
	  };
	  j++;
	  if (j == num) j = 0;
	};
      };
      if (conn == True) quit = False;
	  
      if (*(connected + n1) == 1) {
	while ((j < num) && (conn == False)) {
	  n2 = j;
	  if (n2 != n1) {
	    nd2 = nodeOf(n2);
	    AdjacencyListEntry *adj = nd1->adjacentNodes();
	    int found = False;
	    while ((adj != NULL) && (found == False)) {
	      if (adj->nodePtr() == nd2) found = True;
	      else adj = adj->next();
	    };
	    if (found == False) {
	      d = distance(nd1, nd2);
	      p1 = edgeProb(alpha, beta, L, d);
	      p2 = ran();
	      if (p2 <= p1) { 
		//an edge exists;
		links++;
		nd1->addNeighbor(nd2, defaultCapacity);
		nd2->addNeighbor(nd1, defaultCapacity);
		*(connected + n1) = 2;
		*(connected + n2) += 1;
		conn = True;
	      };
	    };
	  };
	  j++;
	  if (j == num) j = 0;
	};
      };
      if (conn == True) quit = False;
    };
  };

  while ((2 * links / (float)num) < nodeDegree) {
    n1 = (int)(ran() * num);
    n2 = (int)(ran() * num);
    if (n1 != n2) {
      nd1 = nodeOf(n1);
      nd2 = nodeOf(n2);
      AdjacencyListEntry *adj = nd1->adjacentNodes();
      int found = False;
      while ((adj != NULL) && (found == False)) {
	if (adj->nodePtr() == nd2) found = True;
	else adj = adj->next();
      };
      if (found == False) {
	d = distance(nd1, nd2);
	p1 = edgeProb(alpha, beta, L, d);
	p2 = ran();
	if (p2 <= p1) { 
	  //an edge exists;
	  links++;
	  nd1->addNeighbor(nd2, defaultCapacity);
	  nd2->addNeighbor(nd1, defaultCapacity);
	};
      };
    };
  };
  degree = 2 * links / (float)num;
  return(nodeListHd);
};

void TheNodeList::addMuxedBackgroundTrafficSources(double minPeak, 
						   double maxPeak, 
                                double minRho, double maxRho, double minBurst, 
						   double maxBurst) {

   //generates random uniformly distributed background traffic for each node
   //in the network

   //For the time being each background source will be video sources 

   NodeListEntry *n = nodeListHd;
   double peak, rho, burst, pk, avg;
   AdjacencyListEntry *tmp;

   while (n != NULL) {
      tmp = n->nodePtr()->adjacentNodes();
      while (tmp != NULL) {
         int i;
         for (i = 0; i < PRIORITYLEVELS; i++) {
            if (i == (PRIORITYLEVELS - 1)) {
               peak = ran() * (maxPeak - minPeak) + minPeak;
               rho = ran() * (maxRho - minRho) + minRho;
               burst = ran() * (maxBurst - minBurst) + minBurst;
            }
            else {
               peak = ran() * (tmp->linkCapacity() * ADMITRATIO);
               rho = ran() * (maxRho - minRho) + minRho;
               burst = ran() * (maxBurst - minBurst) + minBurst;
            };
            double sum = 0;
            while (sum < peak) {
               Source *s = n->nodePtr()->addSource(VIDEO, 0, i, 1.5e6, 
                                       rho, burst, tmp->nodePtr()->name());
               sum += 1.5e6;
               if (i == PRIORITYLEVELS - 1) {
                  pk = tmp->peak() + 1.5e6;
                  tmp->peak(pk);
                  avg = tmp->average() + s->average();
                  tmp->average(avg);
               };
               srceCount++;
            };
         };
         tmp = tmp->next();
      };
      n = n->next();
   };
};

void TheNodeList::addBatchBackgroundTrafficSources(double minPeak, 
						   double maxPeak, 
                                double minRho, double maxRho, double minBurst, 
						   double maxBurst) {

   //generates random uniformly distributed background traffic for each node
   //in the network

   //For the time being each background source will be video sources 

   NodeListEntry *n = nodeListHd;
   double peak, rho, burst, pk, avg;
   AdjacencyListEntry *tmp;

   while (n != NULL) {
      tmp = n->nodePtr()->adjacentNodes();
      while (tmp != NULL) {
         int i;
         for (i = 0; i < PRIORITYLEVELS; i++) {
            if (i == (PRIORITYLEVELS - 1)) {
               peak = ran() * (maxPeak - minPeak) + minPeak;
               rho = ran() * (maxRho - minRho) + minRho;
               burst = ran() * (maxBurst - minBurst) + minBurst;
            }
            else {
               peak = ran() * (tmp->linkCapacity() * ADMITRATIO);
               rho = ran() * (maxRho - minRho) + minRho;
               burst = ran() * (maxBurst - minBurst) + minBurst;
            };
	    Source *s = n->nodePtr()->addSource(BACKGROUND, 0, i, peak, 
				      rho, burst, tmp->nodePtr()->name());
	    if (i == PRIORITYLEVELS - 1) {
	      pk = tmp->peak() + peak;
	      tmp->peak(pk);
	      avg = tmp->average() + s->average();
	      tmp->average(avg);
	    };
	    srceCount++;
         };
         tmp = tmp->next();
      };
      n = n->next();
   };
};

void TheNodeList::addMuxedSymmetricBackgroundTrafficSources(double minPeak, 
                  double maxPeak, double minRho, double maxRho, 
                              double minBurst, double maxBurst) {

   NodeListEntry *n = nodeListHd;
   double peak, rho, burst, pk, avg;
   AdjacencyListEntry *tmp;

   while (n != NULL) {
      tmp = n->nodePtr()->adjacentNodes();
      while (tmp != NULL) {
         if (n->nodePtr()->name() < tmp->nodePtr()->name()) {
            NodeListEntry *n2 = nodeListHd;
            while (n2->nodePtr()->name() != tmp->nodePtr()->name()) 
                                                    n2 = n2->next();
            AdjacencyListEntry *tmp2 = n2->nodePtr()->adjacentNodes();
            while (tmp2->nodePtr() != n->nodePtr()) tmp2 = tmp2->next();
            int i;
            for (i = 0; i < PRIORITYLEVELS; i++) {
               if (i == (PRIORITYLEVELS - 1)) {
                  peak = ran() * (maxPeak - minPeak) + minPeak;
                  rho = ran() * (maxRho - minRho) + minRho;
                  burst = ran() * (maxBurst - minBurst) + minBurst;
               }
               else {
                  peak = ran() * (tmp->linkCapacity() * ADMITRATIO);
                  rho = ran() * (maxRho - minRho) + minRho;
                  burst = ran() * (maxBurst - minBurst) + minBurst;
               };
               double sum = 0;
               while (sum < peak) {
                  Source *s1 = n->nodePtr()->addSource(VIDEO, 0, i, 
                               1.5e6, rho, burst, tmp->nodePtr()->name());
                  Source *s2 = n2->nodePtr()->addSource(VIDEO, 0, i, 
                               1.5e6, rho, burst, n->nodePtr()->name());
                  sum += 1.5e6;
                  if (i == PRIORITYLEVELS - 1) {
                     pk = tmp->peak() + 1.5e6;
                     tmp->peak(pk);
                     pk = tmp2->peak() + 1.5e6;
                     tmp2->peak(pk);
                     avg = tmp->average() + s1->average();
                     tmp->average(avg);
                     avg = tmp2->average() + s2->average();
                     tmp2->average(avg);
                  };
                  srceCount += 2;
               };
            };
         };
         tmp = tmp->next();
      };
      n = n->next();
   };
};

void TheNodeList::addBatchSymmetricBackgroundTrafficSources(double minPeak, 
                  double maxPeak, double minRho, double maxRho, 
                              double minBurst, double maxBurst) {

   NodeListEntry *n = nodeListHd;
   double peak, rho, burst, pk, avg;
   AdjacencyListEntry *tmp;

   while (n != NULL) {
      tmp = n->nodePtr()->adjacentNodes();
      while (tmp != NULL) {
         if (n->nodePtr()->name() < tmp->nodePtr()->name()) {
            NodeListEntry *n2 = nodeListHd;
            while (n2->nodePtr()->name() != tmp->nodePtr()->name()) 
                                                    n2 = n2->next();
            AdjacencyListEntry *tmp2 = n2->nodePtr()->adjacentNodes();
            while (tmp2->nodePtr() != n->nodePtr()) tmp2 = tmp2->next();
            int i;
            for (i = 0; i < PRIORITYLEVELS; i++) {
               if (i == (PRIORITYLEVELS - 1)) {
                  peak = ran() * (maxPeak - minPeak) + minPeak;
                  rho = ran() * (maxRho - minRho) + minRho;
                  burst = ran() * (maxBurst - minBurst) + minBurst;
               }
               else {
                  peak = ran() * (tmp->linkCapacity() * ADMITRATIO);
                  rho = ran() * (maxRho - minRho) + minRho;
                  burst = ran() * (maxBurst - minBurst) + minBurst;
               };
	       Source *s1 = n->nodePtr()->addSource(VIDEO, 0, i, 
                               peak, rho, burst, tmp->nodePtr()->name());
	       Source *s2 = n2->nodePtr()->addSource(VIDEO, 0, i, 
                               peak, rho, burst, n->nodePtr()->name());
	       if (i == PRIORITYLEVELS - 1) {
		 pk = tmp->peak() + peak;
		 tmp->peak(pk);
		 pk = tmp2->peak() + peak;
		 tmp2->peak(pk);
		 avg = tmp->average() + s1->average();
		 tmp->average(avg);
		 avg = tmp2->average() + s2->average();
		 tmp2->average(avg);
	       };
	       srceCount += 2;
            };
         };
         tmp = tmp->next();
      };
      n = n->next();
   };
};

void TheNodeList::removeBackgroundTrafficSources() {

   NodeListEntry *n = nodeListHd;
   AdjacencyListEntry *tmp;
   SourceList *s;
   int i;
   while (n != NULL) {
      tmp = n->nodePtr()->adjacentNodes();
      while (tmp != NULL) {
         for (i = 0; i < PRIORITYLEVELS; i++) {
           do {
              srceCount--;
              if (i == (PRIORITYLEVELS - 1)) {
                 s = n->nodePtr()->sourceList();
                 int found = False;
                 while ((s != NULL) && (found == False)) {
                     if ((s->source()->type() == Background) && 
                         (s->source()->address() == tmp->nodePtr()->name()) &&
                         (s->source()->priority() == i)) found = True;
                     else s = s->next();
                 };
                 if (found == True) {
                     double pk = tmp->peak() - s->source()->peak();
                     tmp->peak(pk);
                     double avg = tmp->average() - s->source()->average();
                     tmp->average(avg);
                 };              
              };
           } while (n->nodePtr()->removeSource(Background, 
				  i, tmp->nodePtr()->name()) == True);
           srceCount++; 
         };
         tmp = tmp->next();
      };
      n = n->next();
   };
};

void TheNodeList::addRandomMCGroup(int n, int addr) {

   MCGroup *tmp = groupsHd;
   int found = False;
   while ((tmp != NULL) && (found == False)) {
      if (tmp->address() == addr) found = True;
      else tmp = tmp->next();
   }; 

   if (found == False) {
      ++grCount;
      MCGroup *g = new MCGroup(addr);

      MCGroup *tmp2 = groupsHd;

      if (tmp2 == NULL) groupsHd = g;
      else {
       g->next(groupsHd);
       groupsHd = g;
      };

      int rnd = (int)(ran() * num);
      NodeListEntry *tmp1 = nodeListHd;
      for (int i = 0; i < rnd ; i++) {
         if (tmp1 != nodeListTl) tmp1 = tmp1->next();
         else tmp1 = nodeListHd; //this condition should never happen here
      };

      int j = 0;
      while (j < n) {
         j = g->addMember(tmp1->nodePtr()); 
         rnd = (int)(ran() * num);
         for (int i = 0; i < rnd ; i++) {
           if (tmp1 != nodeListTl) tmp1 = tmp1->next();
           else tmp1 = nodeListHd; 
         };
      };
   };      
};
         
int MCGroup::addMember(Node *nd) {

   NodeListEntry *tmp1 = firstm;
   while ((tmp1 != NULL) && (tmp1->nodePtr() != nd)) tmp1 = tmp1->next();