routatm.c

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

            nd = nodeOf(tmp);

            //scan the adjacency list for the least delay link
            AdjacencyListEntry *adj = nd->adjacentNodes();
            while (adj != NULL) {
               if ((*(dbv + tmp) + adj->delay()) < 
		   bestDel) {

                   int tmp2 = *tree;
                   int j = 0;
                   found = False;
                   while ((tmp2 != INT_MAX) && (found == False)) {
                   //check if that adjacent node is already in the tree
                        if (tmp2 == adj->nodePtr()->name()) found = True;
                        else {
                           j++;
                           tmp2 = *(tree + j);
                        };
                   };
                   if (found == False) {
                   //if not update the bestCost ...etc.
		   //but first check for admission control
		     if (fn == PEAK) {
                       if (adj->peak() <= ((adj->linkCapacity() * ADMITRATIO) 
                                        - peak)) {
                          bestDel = *(dbv + tmp) + adj->delay();
                          bestHop = *(hops + tmp) + 1;
		          bestDest = adj->nodePtr()->name();
                          bestFrom = tmp;
                          switch (obj) {
                          case PLAIN:
                            bestCost =  *(cost + tmp) + adj->peak();
                            break;
                          case MULT:
                            bestCost = *(cost + tmp) + adj->peak() *
                                       (*(hops  + tmp) + 1);
                            break;
                          case ADD:
                            bestCost = *(cost + tmp) + adj->peak() +
                                       *(hops  + tmp) * ALPHA;
                            break;
                          };
                       };
                     }
		     else if (fn == AVERAGE) {
		       if (adj->average() <= 
                           ((adj->linkCapacity() * ADMITRATIO) - average)) {
                         bestDel = *(dbv + tmp) + adj->delay();
                         bestHop = *(hops + tmp) + 1;
         		 bestDest = adj->nodePtr()->name();
                         bestFrom = tmp;
                         switch (obj) {
                         case PLAIN:
                           bestCost =  *(cost + tmp) + adj->average();
                           break;
                         case MULT:
                           bestCost = *(cost + tmp) + adj->average() *
                                      (*(hops  + tmp) + 1);
                           break;
                         case ADD:
                           bestCost = *(cost + tmp) + adj->average() +
                                      *(hops  + tmp) * ALPHA;
                           break;
                         };
                       };
                     };
                   };
               };
               adj = adj->next(); //repeat for all nodes adjacent to tmp1
            };
            i++;
            tmp = *(tree + i);
         };

	 if (bestDest != INT_MAX) {
            //Add the least cost node to the tree
            *(tree + k + 1) = bestDest;
            *(dbv + bestDest) = bestDel;
            *(cost + bestDest) = bestCost;
            *(hops + bestDest) = bestHop;
            *(cost_matrix + (bestDest * num) + bestFrom) = bestCost;
            *(delay_matrix + (bestDest * num) + bestFrom) = bestDel;

            adj = (nodeOf(bestDest))->adjacentNodes();
            while (adj != NULL) {
              double weight;
	      if ((fn == PEAK) && (adj->peak() <= 
                  ((adj->linkCapacity() * ADMITRATIO) - peak)))
                weight = adj->peak();
	      else if ((fn == AVERAGE) && (adj->average() <= 
                       ((adj->linkCapacity() * ADMITRATIO) -
                       average))) weight = adj->average();
              else weight = DBL_MAX;
              if (weight != DBL_MAX) {
                *(delay_matrix + (adj->nodePtr()->name() * num) + bestDest)
                  = bestDel + adj->delay();
                if (alg == atm2) {
                  switch (obj) {
                  case PLAIN:
                    *(cost_matrix + (adj->nodePtr()->name() * num) + bestDest) 
                      = bestCost + weight;
                     break;
                  case MULT:
                    *(cost_matrix + (adj->nodePtr()->name() * num) + bestDest) 
                      = bestCost + weight * (bestHop + 1);
                     break;
                  case ADD:
                    *(cost_matrix + (adj->nodePtr()->name() * num) + bestDest) 
                      = bestCost + weight + bestHop * ALPHA;
                     break;
                  };
                }
                else {
                  switch (obj) {
                  case PLAIN:
                    *(cost_matrix + (adj->nodePtr()->name() * num) + bestDest) 
                      = weight;
                     break;
                  case MULT:
                    *(cost_matrix + (adj->nodePtr()->name() * num) + bestDest) 
                      = weight * (bestHop + 1);
                     break;
                  case ADD:
                    *(cost_matrix + (adj->nodePtr()->name() * num) + bestDest) 
                      = weight + bestHop * ALPHA;
                     break;
                  };
                };
              };
              adj = adj->next();
            };
         }
         else k = num; // to exit
      };
      delete [] tree;
      delete [] cost;
      delete [] hops;
};

int TheNodeList::pathWaters(Node *source, int addr, int name, 
                            double *delay_matrix, 
                            double *cost_matrix, double db, 
                            NodeListEntry **tree, double peak, double avg,
                            NodeListEntry **path) {

      //Add the node name to the path
      Node *to = nodeOf(name);
      NodeListEntry *tmp2 = new NodeListEntry;
      tmp2->nodePtr(to);
      tmp2->next(*path);
      *path = tmp2;

      Node *from;
      AdjacencyListEntry *adj;
      int srce, j;
      int done = False;
      double bound = -20;
      int prevSrce = -1;
      while (done == False) {
         double cost = DBL_MAX;
         for (j = 0; j < num; j++) {
            if (((*(cost_matrix + (name * num) + j)) < cost ) &&
                ((*(cost_matrix + (name * num) + j)) > bound )) {
                cost = (*(cost_matrix + (name * num) + j));
                srce = j;
            };
            if (((*(cost_matrix + (name * num) + j)) < cost ) &&
                ((*(cost_matrix + (name * num) + j)) == bound ) &&
                (j > prevSrce)) {
                cost = (*(cost_matrix + (name * num) + j));
                srce = j;
            };
         };
         if (srce == prevSrce) {
            NodeListEntry *tmp2 = *path;
            *path = tmp2->next();
            delete(tmp2);
            return(False);
         };
         bound = cost;
         prevSrce = srce;

         if ((*(delay_matrix + (name * num) + srce)) <= (db + DBL_EPSILON)) { 
         //The comparison doesn't work correctly without this DBL_EPSILON due to
         //imprecise arithmetic
           int found = False;
           if (*path != NULL) {
              NodeListEntry *tmp = *path;
              while ((tmp != NULL) && (tmp->nodePtr()->name() != srce)) 
              tmp = tmp->next();
              if (tmp != NULL) found = True;
           };

           //check if the node from is already in the tree
           if (found == False) {
              from = nodeOf(srce);
              adj = from->adjacentNodes();
              while (adj->nodePtr() != to) adj = adj->next();

              NodeListEntry *tmp1 = *tree;
              while ((tmp1 != NULL) && (done == False)) {
                  if (tmp1->nodePtr() == from) done = True;
                  else tmp1 = tmp1->next();
              };
           };

           if ((found == False) && (done == False)) {
               AdjacencyListEntry *adj = from->adjacentNodes();
               while (adj->nodePtr() != to) adj = adj->next();
               double delay = adj->delay();
               done = pathWaters(source, addr, from->name(), delay_matrix, 
                      cost_matrix, (db - delay), tree, peak, avg, path);
           };
         };
      };

      if (done == True) {
         //add to to the routing table of the best connection node
         from->addChild(addr, source, to);

         //update the link cost
         double delay = adj->delay();
         double wght = adj->peak() + peak; //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);

         //Add the node to to the tree
         NodeListEntry *tmp1 = new NodeListEntry;
         tmp1->nodePtr(to);
         tmp1->next(*tree);
         *tree = tmp1;
         return(True);
      }
      else {
         NodeListEntry *tmp2 = *path;
         *path = tmp2->next();
         delete(tmp2);
         return(False);
      };
};