routcst.c

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

#define START -1

class Via {
 public:
  Via() {};
  int name;
  int slot;
};

double TheNodeList::routerCST(int alg, Node *source, int addr, double &d,
			      double &maxd, double &mind, double &h, 
			      double &nodes) {
  
  /*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 *delay_matrix;
    delay_matrix = new double[num*num];
    double *d_matrix;
    d_matrix = new double[num*num];
    double *cost_matrix;
    cost_matrix = new double[num*num];
    int **via_matrix;
    via_matrix = new (int *)[num*num];

    /*initialize the matrices*/
    int i, j, k, l;
    for (i = 0; i < num; i++) {
      for (j = 0; j < num; j++) {
	*(delay_matrix + (i * num) + j) = DBL_MAX;
	*(d_matrix + (i * num) + j) = DBL_MAX;
	*(cost_matrix + (i * num) + j) = DBL_MAX;
	*(via_matrix + (i * num) + j) = NULL;
      };
    };
    
    int steps = (int)(DELAYBOUND / DELAYSTEP) + 1;
    double *delay_m, *cost_m;
    Via *via_m;
    delay_m = new double[steps*num*num];
    cost_m = new double[steps*num*num];
    via_m = new Via[steps*num*num];
    for (i = 0; i < steps; i++) {
      for (j = 0; j < num; j++) {
	for (k = 0; k < num; k++) {
	  (*(delay_m + (i*num*num) + (j*num) + k)) = DBL_MAX;
	  (*(cost_m + (i*num*num) + (j*num) + k)) = DBL_MAX;
	  (via_m + (i*num*num) + (j*num))->name = INT_MAX;
	};
	(*(delay_m + (i*num*num) + (j*num) + j)) = 0;
	(*(cost_m + (i*num*num) + (j*num) + j)) = 0;	
      };
    };

    NodeListEntry *tmp = nodeListHd;
    int slot;
    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*/
	  if (adj->delay() < DELAYBOUND) {
	    *(delay_matrix + (i * num) + j) = adj->delay();
	    *(d_matrix + (i * num) + j) = adj->delay();
	    *(cost_matrix + (i * num) + j) = adj->peak();
	    slot = (int)(adj->delay() / DELAYSTEP);
	    *(delay_m + slot*num*num + i*num + j) = adj->delay();
	    *(cost_m + slot*num*num + i*num + j) = adj->peak();
	    (via_m + slot*num*num + i*num + j)->name = START;
	  };
	}
	else if ((fn == AVERAGE) && (adj->average() <= 
			       ((adj->linkCapacity() * ADMITRATIO) - avg))) {
 	                                            /*in order to eliminate
						      links saturated links*/
	  if (adj->delay() < DELAYBOUND) {
	    (*(delay_matrix + (i * num) + j)) = adj->delay();
	    (*(d_matrix + (i * num) + j)) = adj->delay();
	    (*(cost_matrix + (i * num) + j)) = adj->average();
	    slot = (int)(adj->delay() / DELAYSTEP);
	    *(delay_m + slot*num*num + i*num + j) = adj->delay();
	    *(cost_m + slot*num*num + i*num + j) = adj->average();
	    (via_m + slot*num*num + i*num + j)->name = START;
	  };
	};
	adj = adj->next();
      };
      tmp = tmp->next();
    };

    /*Now find the all-pairs constrained cheapest paths using a dynamic 
      programming approach*/
    for (l = 0; l < steps; l++) {
      double currentBound;
      if (l == (steps - 1)) currentBound = DELAYBOUND;
      else currentBound = (l + 1) * DELAYSTEP;
      for (k = 0; k < num; k++) {
	for (i = 0; i < num; i++) {
	  for (j = 0; j < num; j++) {

	    double tmpBound = currentBound - 
	      (*(delay_matrix + (k * num) + j));
	    double tmpDelay, tmpCost;
	    int viaName, viaSlot;
	    if (tmpBound > DELAYSTEP) {

	      int tmp1 = (int)(tmpBound / DELAYSTEP);
	      int tmp2 = tmp1 - 1;
	      double tmpDelay1 = (*(delay_m + (tmp1*num*num) + 
		(i*num) + k)) + (*(delay_matrix + (k*num) + j));
	      double tmpCost1 =  (*(cost_m + (tmp1*num*num) + 
	        (i*num) + k)) + (*(cost_matrix + (k * num) + j));
    	      double tmpDelay2 = (*(delay_m + (tmp2*num*num) + 
	  	(i*num) + k)) + (*(delay_matrix + (k * num) + j));
	      double tmpCost2 = (*(cost_m + (tmp2*num*num) + (i*num) + k))
	        + (*(cost_matrix + (k * num) + j));

	      if (tmpDelay1 < currentBound)  {
		if (tmpDelay2 >= (currentBound - DELAYSTEP)) {
		  if (tmpCost2 <= tmpCost1) {
		    tmpCost = tmpCost2;
		    tmpDelay = tmpDelay2;
		    viaName = k;
		    viaSlot = tmp2;
		  }
		  else {
		    tmpCost = tmpCost1;
		    tmpDelay = tmpDelay1;
		    viaName = k;
		    viaSlot = tmp1;
		  };
		}
		else {
		  tmpCost = tmpCost1;
		  tmpDelay = tmpDelay1;
		  viaName = k;
		  viaSlot = tmp1;
		};
	      }
	      else if ((tmpDelay2 >= (currentBound - DELAYSTEP)) &&
		       (tmpDelay2 < currentBound)) {
		tmpCost = tmpCost2;
		tmpDelay = tmpDelay2;
		viaName = k;
		viaSlot = tmp2;
	      }
	      else tmpDelay = DBL_MAX;
	    }
	    else if (tmpBound > 0) {
	      tmpDelay = (*(delay_m + 
		(i*num) + k)) + (*(delay_matrix + (k*num) + j));
	      tmpCost =  (*(cost_m + 
	        (i*num) + k)) + (*(cost_matrix + (k * num) + j));
	      viaName = k;
	      viaSlot = 0;

	      if ((tmpDelay > currentBound) || 
                  (tmpDelay <= (currentBound - DELAYSTEP))) tmpDelay = DBL_MAX;
	      if ((l == (steps - 1)) && (tmpDelay > DELAYBOUND)) 
		tmpDelay = DBL_MAX;
	    }
	    else tmpDelay = DBL_MAX;

	    if ((tmpDelay <= currentBound) && 
		(tmpDelay > (currentBound - DELAYSTEP))) {
	      int change = False;
	      if (tmpCost < (*(cost_m + (l*num*num) + (i*num) + j))) 
		change = True;
	      else if ((tmpCost == (*(cost_m + (l*num*num) + 
				      (i*num) + j))) &&
		       (tmpDelay < (*(delay_m + (l*num*num) +
				      (i*num) + j)))) change = True;
	      if (change == True) {
		(*(cost_m + (l*num*num) + (i*num) + j)) = tmpCost;
		(*(delay_m + (l*num*num) + (i*num) + j)) = tmpDelay;
		(via_m + (l*num*num) + (i*num) + j)->name = viaName;
		(via_m + (l*num*num) + (i*num) + j)->slot = viaSlot;
	      };
	    };
	  };
	};
      };
    };

    /*Reinitialize the matrices*/
    for (i = 0; i < num; i++) {
      for (j = 0; j < num; j++) {
	(*(delay_matrix + (i * num) + j)) = DBL_MAX;
	(*(cost_matrix + (i * num) + j)) = DBL_MAX;
      };
    };

    Via *tmpVia;
    int *tmpPath = new int[num+1];
    for (i = 0; i < num; i++) {
      tmp = group->headm();
      while ((tmp != NULL) && (tmp->nodePtr()->name() != i)) tmp = tmp->next();
      if (((tmp != NULL) || (source->name() == i))) {
	for (j = 0; j < num; j++) {
	  tmp = group->headm();
	  while ((tmp != NULL) && (tmp->nodePtr()->name() != j)) 
	    tmp = tmp->next();
	  if ((tmp != NULL) && (source->name() != j) && (i != j)) {
	    int bestL = -1;
	    double bestCost = DBL_MAX;
	    for (l = 0; l < steps; l++) {
	      if (*(cost_m + (l*num*num) + (i*num) + j) < bestCost) {
		bestL = l;
		bestCost = *(cost_m + (l*num*num) + (i*num) + j);
	      };
	    };
	    if (bestL != -1) {
	      *(cost_matrix + (i*num) + j) = bestCost;
	      *(delay_matrix + (i*num) + j) = 
		*(delay_m + (bestL*num*num) + (i*num) + j);
	      tmpVia = (via_m + (bestL*num*num) + (i*num) + j);
	      k = 0;
	      while (tmpVia->name != START) {
		*(tmpPath + k) = tmpVia->name;
		k++;
		tmpVia = 
		  (via_m + (tmpVia->slot*num*num) + (i*num) + tmpVia->name);
	      };
	      int m = 0;
	      *(via_matrix + (i*num) + j) = new int[k+2];
	      while (k > 0) {
		k--;
		*(*(via_matrix + (i*num) + j) + m) = *(tmpPath + k);
		m++;
	      };
	      *(*(via_matrix + (i*num) + j) + m) = j;
	      *(*(via_matrix + (i*num) + j) + m + 1) = INT_MAX;
	    };
	  };
	};
      };
    };
    delete [] tmpPath;
    delete [] cost_m;
    delete [] delay_m;
    delete [] via_m;

   /*The above matrices describe a complete directed graph that includes
      the multicast group members and the source only.
      The next step is to create a minimum spanning tree on that graph
      using a greedy approach, and starting at the source*/

    int *member = new int[group->count() + 1];
    int *from = new int[group->count() + 1];
    int *hops = new int[num];
    double *delay = new double[group->count() + 1];
    for (i = 1; i < (group->count() + 1); i++) {
      *(member + i) = INT_MAX;
      *(from + i) = INT_MAX;
      *(delay + i) = DBL_MAX;
    };

    *member = source->name();
    *from = INT_MAX;
    *(hops + source->name()) = 0;
    *delay = 0;
    for (i = 0; i < num; i++) {
      (*(cost_matrix + (i * num) + *member)) = DBL_MAX;
      (*(delay_matrix + (i * num) + *member)) = DBL_MAX;
    };

/*for (i = 0; i < num; i++) {
for (j = 0; j < num; j++) {
printf("%.2e\t", *(delay_matrix +(i*num) + j));
};
printf("\n");
};
printf("\n");
for (i = 0; i < num; i++) {
for (j = 0; j < num; j++) {
printf("%.2e\t", *(cost_matrix +(i*num) + j));
};
printf("\n");
};
printf("\n");
*/

    int done = False;
    while (done == False) {
      
      double minCost = DBL_MAX;
      int bestFrom = INT_MAX;
      int bestChoice = INT_MAX;
      int quit = False;
      int current = *member;
      int bestI = INT_MAX;
      int bestHop;
      i = 0;
      while (quit == False) {
	for (j = 0; j < num; j++) {
	  if (((*(delay + i)) + (*(delay_matrix + (current * num) + j))) <
	      DELAYBOUND) {
	    if (alg == cstc) {
	      switch (obj) {
	      case PLAIN:
		if ((*(cost_matrix + (current * num) + j)) < minCost) {
		  minCost = (*(cost_matrix + (current * num) + j));
		  bestFrom = current;
		  bestChoice = j;
		  bestHop = *(hops + current) + 1;
		  bestI = i;
		};
		break;
	      case MULT:
		if ((*(cost_matrix + (current * num) + j) *
		     (*(hops + current) + 1)) < minCost) {
		  minCost = (*(cost_matrix + (current * num) + j)) *