routbf.c

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

double TheNodeList::routerBF(Node *source, int addr,  double &d, 
			     double &maxd, double &mind, 
			     double &h, double &nodes) {

   //The complete Bellman-Ford least-cost routing algorithm

   //First delete any previous routing for the this group and source set.
   removeTree(source, addr);

   //Locate the source to get the peak rate
   SourceList *ss = source->sourceList();
   int found = False;
   while ((ss != NULL) && (found == False)) {
       if ((ss->source()->type() != Background) &&
           (ss->source()->address() == addr)) found = True;
       else ss = ss->next();
   };
   double pk = ss->source()->peak();
   double avg = ss->source()->average();

   //Locate the MC group that contains the destination set
   MCGroup *group = groupsHd;
   while ((group !=  NULL) && (group->address() != addr))   
      group = group->next();
   
   if (group != NULL)  {

      if ((group->count() == 1) && 
          (group->headm()->nodePtr()->name() == source->name())) {
            source->addRoutingEntry(addr, source);
	    h = d = maxd = mind = 0;
	    nodes = 1;
            return(0);
      };

     double *cost;
     cost = new double[num];
     int *hops;
     hops = new int[num];
     int *from;
     from = new int[num];
     int i, j, k;
     for (i = 0; i < num; i++) {
       *(cost + i) = DBL_MAX;
       *(from + i) = INT_MAX;
     };
     *(cost + source->name()) = 0;
     
     double *c_matrix;
     c_matrix = new double[num*num];
     for (i = 0; i < num; i++) {
       for (j = 0; j < num; j++) {
	 *(c_matrix + (i * num) + j) = DBL_MAX;
       };
     };
     
     /*The c_matrix contains link costs*/
     NodeListEntry *tmp = nodeListHd;
     while (tmp != NULL) {
       i = tmp->nodePtr()->name();
       AdjacencyListEntry *adj = tmp->nodePtr()->adjacentNodes();
       while (adj != NULL) {
	 j = adj->nodePtr()->name();
	 if ((fn == PEAK) && (adj->peak() <= 
	     ((adj->linkCapacity() * ADMITRATIO) - pk))) 
	                                            /*in order to eliminate
						      links saturated links*/
	   *(c_matrix + (i * num) + j) = adj->peak();
	 else if ((fn == AVERAGE) && (adj->average() <= 
                  ((adj->linkCapacity() * ADMITRATIO) - avg)))
 	                                            /*in order to eliminate
						      links saturated links*/
	   *(c_matrix + (i * num) + j) = adj->average();
	 adj = adj->next();
       };
       tmp = tmp->next();
     };

     int changed;
     do {
       changed = False;
       for (i = 0; i < num; i++) {
	 for (j = 0; j < num; j++) {
	   switch (obj) {
	   case PLAIN:
	     if ((*(cost + j) + *(c_matrix + (j * num) + i)) < (*(cost + i))) {
	       changed = True;
	       *(cost + i) = *(cost + j) + *(c_matrix + (j * num) + i);
printf("cost to %d = %.3e\n", i, *(cost +i));
	       *(from + i) = j;
	     };
	     break;
	   case MULT:
	     if ((*(cost + j) + 
		  *(c_matrix + (j * num) + i) * (*(hops + j) + 1))
		 < (*(cost + i))) {
	       changed = True;
	       *(cost + i) = *(cost + j) + 
		 *(c_matrix + (j * num) + i) * (*(hops + j) + 1);
	       *(hops +i) = *(hops +j) + 1;
	       *(from + i) = j;
	     };
	     break;
	   case ADD:
	     if ((*(cost + j) + *(c_matrix + (j * num) + i) +
		  *(hops + j) * ALPHA) < (*(cost + i))) {
	       changed = True;
	       *(cost + i) = *(cost + j) + *(c_matrix + (j * num) + i) +
		 *(hops + j) * ALPHA;
	       *(hops + i) = *(hops + j) + 1;
	       *(from + i) = j;
	     };
	     break;
	   };
	 };
       };
     } while (changed == True);
     delete [] cost;
     delete [] c_matrix;
     delete [] hops;

     //The source is the first member in the tree
     NodeListEntry *tree, *tmp1;
     tree = new NodeListEntry;
     tree->nodePtr(source);
     source->addRoutingEntry(addr, source);

     //Check if saturated links prevent the creation of the tree
     tmp1 = group->headm();
     while (tmp1 != NULL) {
       if ((*(from + tmp1->nodePtr()->name()) == INT_MAX) &&
	   (tmp1->nodePtr()->name() != source->name())) {
	 delete tree;
	 delete [] from;
	 return(LINKSAT);
       };
       tmp1 = tmp1->next();
     };

     //I will create a broadcast tree and prune it later
     for (i = 0; i < num; i++) {
       if ((i != source->name()) && (*(from + i) != INT_MAX)) {
	 Node *nd = nodeOf(i);
	 //Add the node to the tree
	 tmp1 = new NodeListEntry;
	 tmp1->nodePtr(nd);
	 tmp1->next(tree);
	 tree = tmp1;

	 Node *nd2 = nodeOf(*(from + i));
	 AdjacencyListEntry *adj = nd2->adjacentNodes();
	 while (adj->nodePtr() != nd) adj = adj->next();
	 //update the link cost
         double wght = adj->peak() + pk; //link costs are proportional
                                                 //to the peak rates of the 
                                                 //traffic crossing these
                                                 //links.
	 adj->peak(wght);
	 double average = adj->average() + avg;
	 adj->average(average);

	 //and add it to the routing table of the best connection node
	 nd2->addChild(addr, source, nd);

	 //create a new routing table entry for that node
	 nd->addRoutingEntry(addr, source);
       };
     };
     delete [] from;

     //prune nonmember leaves
     prune(group, &tree, source, source, addr, NULL, pk, avg);

     maxd = 0;
     mind = DBL_MAX;
     int dbViolation = False;
     //calculate the expected end-to-end delay and the average number of hops
     //and the cost per destination
     NodeListEntry *tmp2 = group->headm();
     double avgDelay = 0;
     double avgHops = 0;
     while (tmp2 != NULL) {
       int gotit = False;
       int hops = 0;
       double delay = 0;
       if (source != tmp2->nodePtr()) 
         results(source, addr, source, tmp2->nodePtr(), delay, hops, gotit);   
       if (delay >= DELAYBOUND) dbViolation = True;
       if (delay > maxd) maxd = delay;
       if (delay < mind) mind = delay;
       avgDelay += delay;
       avgHops += hops;
       tmp2 = tmp2->next();
     };
     avgDelay /= group->count();
     avgHops /= group->count();
     d = avgDelay;
     h = avgHops;

     //Calculate the total cost of the tree and delete the temp. tree
     double totalCost = 0;
     nodes = 0;
     tmp1 = tree;
     while (tmp1 != NULL) {
       nodes++;
       RoutingTableEntry *rout = tmp1->nodePtr()->routingTable();
       int found = False;
       while ((rout != NULL) && (found == False)) {
	 if ((rout->address() == addr) && (rout->source() == source)) 
	   found = True;
	 else rout = rout->next();
       };
       NodeListEntry *tmp = rout->children();
       while (tmp != NULL) {
	 AdjacencyListEntry *adj = tmp1->nodePtr()->adjacentNodes();
	 int found2 = False;
	 while ((adj != NULL) && (found2 == False)) {
	   if (adj->nodePtr() == tmp->nodePtr()) found2 = True;
	   else adj = adj->next();
	 };
	 if (adj != NULL) {
	   if (fn == PEAK) totalCost += (adj->peak() - pk);
	   else totalCost += (adj->average() - avg);
	 };
	 tmp = tmp->next();
       };
       tmp2 = tmp1->next();
       delete tmp1;
       tmp1 = tmp2;
     };
     if ((DBV == True) && (dbViolation == True)) {
       removeTree(source, addr);
       return(DBVIOL);
     }
     else return(totalCost);
   }
   else return(NOGROUP);
};