routdvmrp.c

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

int TheNodeList::routAlgBF(double *dist_vect, int *parent_vect) {

/* This version of Bellman Ford algorithm will find the least-cost broadcast
   from any source node to all nodes in the network and the puts those costs in
   a routing table. it runs the traditional Bellman Ford algorithm once with 
   every node as the source.
*/
  
  int i, j, k;
  double *c_matrix;
  c_matrix = new double[num*num];
  for (i = 0; i < num; i++) {
    for (j = 0; j < num; j++) {
      *(dist_vect + (i * num) + j) = DBL_MAX;
      *(parent_vect + (i * num) + j) = INT_MAX;
      *(c_matrix + (i * num) + j) = DBL_MAX;
    };
    *(dist_vect + (i * num) + i) = 0;
  };
     
  /*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();
      double weight;
      if (fn == PEAK) weight = adj->peak();
      else if (fn == AVERAGE) weight = adj->average();
      else weight = DBL_MAX;
      if (weight < 0) {
	delete [] c_matrix;
	return(False);
      };
      *(c_matrix + (i * num) + j) = weight;
      adj = adj->next();
    };
    tmp = tmp->next();
  };

  for (k = 0; k < num; k++) {
    int changed;
    do {
      changed = False;
      for (i = 0; i < num; i++) {
	for (j = 0; j < num; j++) {
	  if ((*(dist_vect + (k * num) + j) + *(c_matrix + (j * num) + i)) < 
	      (*(dist_vect + (k * num) + i))) {
	    changed = True;
	    *(dist_vect +  (k * num) + i) = *(dist_vect +  (k * num) + j) + 
	      *(c_matrix + (j * num) + i);
	    if (k != j)
	      *(parent_vect + (k * num) + i) = *(parent_vect + (k * num) + j);
	    else *(parent_vect + (k * num) + i) = i;
	  };
	};
      };
    } while (changed == True);
  };
  delete [] c_matrix;
  return(True);
};

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

/* The DVMRP protocol uses the shortest paths calculated by the Bellman-Ford 
   algorithm to create a reverse shortest path MC tree. DVMRP doesn't
   make any resource reservations
*/

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

  double *dist_vect;
  dist_vect = new double[num*num];
  int *parent_vect;
  parent_vect = new int[num*num];

  //Locate the source to get the average rate;
  SourceList *ss = srce->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() == srce->name())) {
      srce->addRoutingEntry(addr, srce);
      delete [] dist_vect;
      delete [] parent_vect;
      h = d = maxd = mind = 0;
      nodes = 1;
      return(0);
    };

    //Calculate the new distance vectors;
    routAlgBF(dist_vect, parent_vect);

    //The source node must have a routing entry;
    srce->addRoutingEntry(addr, srce);
    
    NodeListEntry *tree = new NodeListEntry;
    tree->nodePtr(srce);

    // Now expand the tree;
    AdjacencyListEntry *adj = srce->adjacentNodes();
    while (adj != NULL) {
      if (srce->name() == 
	  *(parent_vect + (adj->nodePtr()->name() * num) + srce->name())) {
	srce->addChild(addr, srce, adj->nodePtr());
	double wght = adj->peak() + pk;
	adj->peak(wght);
	double average = adj->average() + avg;
	adj->average(average);
	forward(adj->nodePtr(), srce, srce, addr, 
		&tree, pk, avg, parent_vect);
      };
      adj = adj->next();
    };

    delete [] dist_vect;
    delete [] parent_vect;

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


    int dbViolation = False;
    int admissionCtrl = True;
    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 (srce != tmp2->nodePtr()) { 
	int state = 
	  results(srce, addr, srce, tmp2->nodePtr(), delay, hops, gotit);
	if (state == False) admissionCtrl = False;
      };
      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;
    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() == srce)) 
	  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 (admissionCtrl == False) {
      removeTree(srce, addr);
      return(LINKSAT);
    };
    if ((DBV == True) && (dbViolation == True)) {
      removeTree(srce, addr);
      return(DBVIOL);
    }
    else return(totalCost);
  }
  else return(NOGROUP);
};

  
void TheNodeList::forward(Node *nd, Node *from, Node *srce, 
			  int addr, NodeListEntry **tree, double pk,
			  double avg, int *parent_vect) {

  NodeListEntry *tmp = *tree;
  while ((tmp != NULL) && (tmp->nodePtr() != nd)) tmp = tmp->next();
 
  if (tmp == NULL) {
    nd->addRoutingEntry(addr, srce);
    tmp =new NodeListEntry;
    tmp->nodePtr(nd);
    tmp->next(*tree);
    *tree = tmp;
    AdjacencyListEntry *adj = nd->adjacentNodes();
    while (adj != NULL) {
      if (nd->name() == *(parent_vect + (adj->nodePtr()->name() * num) 
			  + srce->name())) {
	nd->addChild(addr, srce, adj->nodePtr());
	double wght = adj->peak() + pk;
	adj->peak(wght);
	double average = adj->average() + avg;
	adj->average(average);

//printf("connect from %d to %d\n", nd->name(), adj->nodePtr()->name());
	forward(adj->nodePtr(), nd, srce, addr, tree, pk, avg,
		parent_vect);
      };
      adj = adj->next();
    };
  }
  else if (from != NULL) {
//printf("remove from %d to %d\n", from->name(), nd->name());
    from->removeChild(addr, srce, nd);
  };
};