routbsma.c

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

    }
    else c += tmpc;
    BSMAInfo(source, addr, tmp->nodePtr(), delay, cost, hops, via,
	     d_matrix, c_matrix, seCount, from, to, seCost, c, group);
    tmp = tmp->next();
    if (tmp != NULL) seCount++;
  };         
};  

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


  double pk, avg;
  //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();
  };
  pk = ss->source()->peak();
  avg = ss->source()->average();

  int i, j, k;
  double *d_matrix = new double[num*num];
  double *c_matrix = new double[num*num];
  NodeListEntry *tmp = nodeListHd;

  /*initialize the matrices*/
  for (i = 0; i < num; i++) {
    for (j = 0; j < num; j++) {
      (*(d_matrix + (i * num) + j)) = DBL_MAX;
      (*(c_matrix + (i * num) + j)) = DBL_MAX;
    };
  };

  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 saturated links*/
	if (adj->delay() < DELAYBOUND) {
	  *(d_matrix + (i * num) + j) = adj->delay();
	  *(c_matrix + (i * num) + j) = adj->peak();
	};
      }
      else if ((fn == AVERAGE) && (adj->average() <= 
			      ((adj->linkCapacity() * ADMITRATIO) - avg))) {
	/*in order to eliminate saturated links*/
	if (adj->delay() < DELAYBOUND) {
	  (*(d_matrix + (i * num) + j)) = adj->delay();
	  (*(c_matrix + (i * num) + j)) = adj->average();
	};
      };
      adj = adj->next();
    };
    tmp = tmp->next();
  };

  MCGroup *group;
  NodeListEntry *tree = NULL;
  double status = leastDelay(source, addr, &group, &tree, pk, avg);
  if (status == GOOD) {
    if ((group->count() == 1) && 
	(group->headm()->nodePtr()->name() == source->name())) {
      source->addRoutingEntry(addr, source);
      h = d = maxd = mind = 0;
      nodes = 1;
      delete [] d_matrix;
      delete [] c_matrix;
      return(0);
    };
    double *cost = new double[num+1];
    double *delay = new double[num+1];
    int *hops = new int[num+1];
    int *via = new int[num+1];

    int all = False;
    int unMarkAll = True;
    int *from, *to, *mark;
    from = new int[num+1];
    to = new int[num+1];
    mark = new int[num+1];
    *from = INT_MAX;
    double *seCost = new double[num+1];
    int seCount;

    while (all == False) {
      //Repeat until all edges are marked
      
     //scan tree to determine the superedges, and put superedges 
     //in an array
     if (unMarkAll == True) {
       for (i = 0; i <= num; i++) {
	 *(from + i) = INT_MAX;
	 *(to + i) = INT_MAX;
	 *(mark + i) = False;
	 *(seCost + i) = DBL_MAX;
	 *(delay + i) = DBL_MAX;
	 *(cost + i) = DBL_MAX;
	 *(hops + i) = INT_MAX;
	 *(via + i) = INT_MAX;
       };
       unMarkAll = False;
       double c = 0;
       seCount = 0;
       *(delay + source->name()) = 0;
       *(cost + source->name()) = 0;
       *(hops + source->name()) = 0;
       BSMAInfo(source, addr, source, delay, cost, hops, via,
		d_matrix, c_matrix, seCount, from, to, seCost, c, group);
       i = 0;
       while ((all == False) && (i < num)) {
	 if (((*(via + i)) != INT_MAX) && (*(delay + i) > DELAYBOUND))
	   all = True;
	 i++;
       };
     };
           
     //find the most expensive unmarked superedge
     int choose = INT_MAX;
     double c = -1;
     for (i = 0; i < num; i++) {
       if ((*(mark + i) == False) && (*(from + i) != INT_MAX) &&
	   (*(seCost + i) > c)) {
         c = *(seCost + i);
	 choose = i;
       };
     };
   
     //divide the tree into subtrees tree1 and tree2
     int srce = *(from + choose);
     int dest = *(to + choose);
     double cBound = *(seCost + choose);
     double delta1 = *(delay + dest);

     int *tree2 = new int[num];
     *tree2 = dest;
     j = 1;
     for (i = 0; i < num; i++) {
       k = i;
       found = False;
       while ((*(via + k) != INT_MAX) && (found == False)) {
	 if (*(via + k) == dest) found =True;
	 else k = *(via + k);
       };
       if (found == True) {
	 *(tree2 + j) = i;
	 j++;
       };
     };
     *(tree2 + j) = INT_MAX;

     int *tree1 = new int[num];
     j = 0;
     for (i = 0; i < num; i++) {
       if (*(cost + i) < DBL_MAX) {
	 k = 0;
	 while ((*(tree2 + k) != i) && (*(tree2 + k) != INT_MAX)) k++;
	 if (*(tree2 + k) == INT_MAX) {
	   k = *(via + dest);
	   while ((i != k) && (srce != k)) k = *(via + k);
	   if (k == srce) {
	     *(tree1 + j) = i;
	     j++;
	   };
	 };
       };
     };
     *(tree1 + j) = INT_MAX;

     //determine the max. delay in tree2
     double delta2 = 0;
     k = 0;
     while (*(tree2 + k) != INT_MAX) {
       if (*(delay + *(tree2 + k)) > delta2)
	 delta2 = *(delay + *(tree2 + k));
       k++;
     };

     //for each edge in tree1 find the constrained cheapest path to the root
     // of tree2. Such a path is not permitted to include any  nodes of either
     // tree1 or tree2.

     k = 0;
     kthPath *best = NULL;
     kthPath *tmp;
     while (*(tree1 + k) != INT_MAX) {
       tmp = kthShortest(*(tree1 + k), dest, 
		  DELAYBOUND - (delta2 - delta1) - *(delay + *(tree1 + k)), 
		  cBound, tree1, tree2, 
		  c_matrix, d_matrix, *(hops + *(tree1 + k)));
       if (tmp != NULL) {
	 if (best != NULL) {
	   if (tmp->cost < best->cost) {
	     delete best;
	     best = tmp;
	   }
	   else delete tmp; 
	 }
	 else best = tmp;
       };
       k++;
     }; 
     delete [] tree1;
     delete [] tree2;

      //If the cheapest path is cheaper than the superedge cost replace the 
      //superedge and unmark all edges, else mark the superedge and go back to
      if (best == NULL) *(mark + choose) = True;
      else {
	unMarkAll = True;
	//erase the previous superedge
        int via1, dest1;
	double av, pe;
	AdjacencyListEntry *adj;
	via1 = *(via + dest);
	dest1 = dest;
	Node *destNd = nodeOf(dest1);
	Node *viaNd = nodeOf(via1);
	viaNd->removeChild(addr, source, destNd);
	if (via1 != srce) viaNd->removeRoutingEntry(addr, source);
	adj = viaNd->adjacentNodes();
	while (adj->nodePtr() != destNd) adj = adj->next();
        pe = adj->peak() - pk; 
	adj->peak(pe);
        av = adj->average() - avg;
	adj->average(av);
	NodeListEntry *tr = tree;
	NodeListEntry *prtr = NULL;
	while (tr->nodePtr() != destNd) {
	  prtr = tr;
	  tr = tr->next();
	};
	if (tr == tree) tree = tr->next();
	else prtr->next(tr->next());
	delete tr;
	while (via1 != srce) {
	  dest1 = via1;
	  via1 = *(via + via1);
	  destNd = nodeOf(dest1);
	  viaNd = nodeOf(via1);
	  viaNd->removeChild(addr, source, destNd);
	  if (via1 != srce) viaNd->removeRoutingEntry(addr, source);
	  adj = viaNd->adjacentNodes();
	  while (adj->nodePtr() != destNd) adj = adj->next();
	  pe = adj->peak() - pk; 
	  adj->peak(pe);
	  av = adj->average() - avg;
	  adj->average(av);
	  tr = tree;
	  prtr = NULL;
	  while (tr->nodePtr() != destNd) {
	    prtr = tr;
	    tr = tr->next();
	  };
	  if (tr == tree) tree = tr->next();
	  else prtr->next(tr->next());
	  delete tr;
	};

	//Add the new superedge
	int *p = best->pth;
	via1 = *p;
	dest1 = *(p + 1);
	viaNd = nodeOf(via1);
	destNd = nodeOf(dest1);
	viaNd->addChild(addr, source, destNd);
	adj = viaNd->adjacentNodes();
	while (adj->nodePtr() != destNd) adj = adj->next();
        pe = adj->peak() + pk; 
	adj->peak(pe);
        av = adj->average() + avg;
	adj->average(av);
	tr = new NodeListEntry;
	tr->nodePtr(destNd);
	tr->next(tree);
	tree = tr;
	i = 2;
	while (dest1 != dest) {
	  via1 = dest1;
	  dest1 = *(p + i);
	  viaNd = nodeOf(via1);
	  destNd = nodeOf(dest1);
	  viaNd->addChild(addr, source, destNd);
	  adj = viaNd->adjacentNodes();
	  while (adj->nodePtr() != destNd) adj = adj->next();
	  pe = adj->peak() + pk; 
	  adj->peak(pe);
	  av = adj->average() + avg;
	  adj->average(av);
	  tr = new NodeListEntry;
	  tr->nodePtr(destNd);
	  tr->next(tree);
	  tree = tr;
	  i++;
	};
	delete best;
      };
      
      //Now check if all edges are marked
      if (unMarkAll == False) {
	i = 0;
	while ((*(from + i) != INT_MAX) && (*(mark + i) == True)) i++;
	if (*(from + i) == INT_MAX) all = True;
      };
    };
    delete [] cost;
    delete [] hops;
    delete [] delay;
    delete [] via;
    delete [] c_matrix;
    delete [] d_matrix;
    delete [] from;
    delete [] to;
    delete [] mark;
    delete [] seCost;

    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;
    
    double totalCost = 0;
    nodes = 0;
    //Calculate the total cost of the tree and delete the temp. tree
    NodeListEntry *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 {
    delete [] c_matrix;
    delete [] d_matrix;
    return(status);
  };
};