routcdks.c

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

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

  //Sun constrained 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 *costlc, *delaylc, *delayld;
    costlc = new double[num];
    delaylc = new double[num];
    delayld = new double[num];
    int *fromlc, *fromld;
    fromlc = new int[num];
    fromld = new int[num];
    int i, j, k;
    for (i = 0; i < num; i++) {
      *(costlc + i) = DBL_MAX;
      *(delaylc + i) = DBL_MAX;
      *(fromlc + i) = INT_MAX;
      *(delayld + i) = DBL_MAX;
      *(fromld + i) = INT_MAX;
    };
    *(costlc + source->name()) = 0;
    *(delaylc + source->name()) = 0;
    *(delayld + source->name()) = 0;
     
    double *c_matrix, *d_matrix;
    c_matrix = new double[num*num];
    d_matrix = new double[num*num];
    for (i = 0; i < num; i++) {
      for (j = 0; j < num; j++) {
        *(c_matrix + (i * num) + j) = DBL_MAX;
        *(d_matrix + (i * num) + j) = DBL_MAX;
      };
    };
     
    /*The c_matrix contains link costs*/
    /*The d_matrix contains link delays*/
    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();
	  *(d_matrix + (i * num) + j) = adj->delay();
	}
        else if ((fn == AVERAGE) && (adj->average() <= 
                 ((adj->linkCapacity() * ADMITRATIO) - avg))) {
 	                  /*in order to eliminate links saturated links*/
	  *(c_matrix + (i * num) + j) = adj->average();
	  *(d_matrix + (i * num) + j) = adj->delay();
	};
        adj = adj->next();
      };
      tmp = tmp->next();
    };

    int *remaining = new int[num];
    for (i = 0; i < num; i++) *(remaining + i) = INT_MAX;
    int done = False;
    int notComplete = False;
    while (done == False) {

      double bestCost = DBL_MAX;   //infinity
      int bestAdj = INT_MAX;
      int bestFrom = INT_MAX;
      for (i = 0; i < num; i++) {
        if (*(costlc + i) < DBL_MAX) {
          for (j = 0; j < num; j++) {
            if ((*(costlc + j) == DBL_MAX) &&
                ((*(costlc + i) + *(c_matrix + (i *num) +j)) < bestCost) &&
                ((*(delaylc + i) + *(d_matrix + (i *num) +j)) < DELAYBOUND)) {
              bestCost = *(costlc + i) + *(c_matrix + (i *num) +j);
              bestAdj = j;
              bestFrom = i;
            };
          };
        };
      };

      if (bestAdj == INT_MAX) {
        NodeListEntry *tmp2 = group->headm();
        i = 0;
        while (tmp2 != NULL) {
          if (*(costlc + tmp2->nodePtr()->name()) == DBL_MAX) {
            *(remaining + i) = tmp2->nodePtr()->name();
            i++;
          };
          tmp2 = tmp2->next();
        };
        done = True;
        notComplete = True;
      }
      else {
        *(costlc + bestAdj) = bestCost;
        *(delaylc + bestAdj) = *(delaylc + bestFrom) + 
                               *(d_matrix + (bestFrom *num) + bestAdj);
        *(fromlc + bestAdj) = bestFrom;
      };

      //Check if the tree contains all group members
      NodeListEntry *tmp2 = group->headm();
      int quit = False;
      while ((tmp2 != NULL) && (quit == False)) {
        if (*(costlc + tmp2->nodePtr()->name()) == DBL_MAX) quit = True;
        tmp2 = tmp2->next();
      };
      if (quit == False) done = True;
    };

    if (notComplete == True) {
      done = False;
      while (done == False) {

        double bestDelay = DBL_MAX;   //infinity
        int bestAdj = INT_MAX;
        int bestFrom = INT_MAX;
        for (i = 0; i < num; i++) {
          if (*(delayld + i) < DBL_MAX) {
            for (j = 0; j < num; j++) {
              if ((*(delayld + j) == DBL_MAX) &&
                ((*(delayld + i) + *(d_matrix + (i *num) +j)) < bestDelay) &&
                ((*(delayld + i) + *(d_matrix + (i *num) +j)) < DELAYBOUND)) {
                bestDelay = *(delayld + i) + *(d_matrix + (i *num) +j);
                bestAdj = j;
                bestFrom = i;
              };
            };
          };
        };

        if (bestAdj == INT_MAX) {
          delete [] c_matrix;
          delete [] d_matrix;
          delete [] costlc;
          delete [] delaylc;
          delete [] fromlc;
          delete [] delayld;
          delete [] fromld;
          delete [] remaining;
          return(SATORDB);
        }
        else {
          *(delayld + bestAdj) = bestDelay;
          *(fromld + bestAdj) = bestFrom;
        };

        //Check if the tree contains all remaining group members
        int quit = False;
        i = 0;
        while ((*(remaining + i) != INT_MAX) && (quit == False)) {
          if (*(delayld + *(remaining + i)) == DBL_MAX) quit = True;
          i++;
        };
        if (quit == False) done = True;
      };
    };
    delete [] c_matrix;
    delete [] d_matrix;
    delete [] costlc;
    delete [] delaylc;
    delete [] delayld;

    //merge the two trees;
    int *from = new int[num];
    for (i = 0; i < num; i++) *(from + i) = INT_MAX;

    i = 0;
    while (*(remaining + i) != INT_MAX) {
      *(from + *(remaining + i)) = *(fromld + *(remaining + i));
      int curr = *(fromld + *(remaining + i));
      while (curr != source->name()) {
        *(from + curr) = *(fromld + curr);
        curr = *(fromld + curr);
      };
      i++;
    };
      
    for (i = 0; i < num; i++) {
      if (*(from + i) == INT_MAX) *(from + i) = *(fromlc + i);
    };
    delete [] remaining;
    delete [] fromlc;
    delete [] fromld;

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

    //Now construct the tree;
    NodeListEntry *tmp1;
    for (i = 0; i < num; i++) {
      if (*(from + i) != INT_MAX) {
          
        Node *nd = nodeOf(i);
        Node *fromNd = nodeOf(*(from + i));

        //Add that node to the tree
        tmp1 = new NodeListEntry;
        tmp1->nodePtr(nd);
        tmp1->next(tree);
        tree = tmp1;
        nd->addRoutingEntry(addr, source);

	//update the link cost
        AdjacencyListEntry *adj = fromNd->adjacentNodes();
        while (adj->nodePtr() != nd) adj = adj->next();
	double wght = adj->peak() + pk; 
        adj->peak(wght);
        double average = adj->average() + avg;
        adj->average(average);

        //and add it to the routing table
        fromNd->addChild(addr, source, nd);
      };
    };
    delete [] from;

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

    int dbViolation = False;
    maxd = 0;
    mind = DBL_MAX;
    //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);
};