routcao.c

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

class edge {

 public:
  edge(int srce, int snk, double c, double d, int h) {
    source =srce; sink = snk; cost =c; key = d; hops = h; next = NULL;
  };
  ~edge() {};
  double cost;
  double key;
  int source;
  int sink;
  int hops;
  edge *next;
};

class edgeQueue {

 public:
  edge *head;
  edge *tail;
  edgeQueue() { head = tail = NULL; };
  ~edgeQueue();
  void insert(edge *e);
  edge *dequeue();
};

void edgeQueue::insert(edge *e) {
   short stop = 0;
   edge *dum;
   e->next = head;
   if (head == NULL)
      head = tail = e;
   else if (head->key > e->key) head = e;
   else while(!stop) {
      dum = e->next;
      e->next = e->next->next;
      if (e->next == NULL) {
         tail->next = e;
         tail = e;
         stop = 1;
      }      
      else if (e->next->key > e->key) {
         dum->next = e;
         stop = 1;
      };
   };
};

edge *edgeQueue::dequeue() {
  edge *e;
  if (head != NULL) {
    e = head;
    head = head->next;
    return(e);
  }
  else return(NULL);
};

edgeQueue::~edgeQueue() {
  edge *e;
  while (head != NULL) {
    e = head;
    head = head->next;
    delete e;
  };
};

class path {

 public:
  path(int *p, int pp, double c, double d);
  ~path() { delete [] pred; };
  int *pred; //This is different than the original algorithm. I will
             //save the entire path not just one predecessor.
  double cost;
  double key;
  path *next;
};

path::path(int *p, int pp, double c, double d) {
  cost = c;
  key = d;
  int i = 0;
  while (*(p + i) != INT_MAX) i++;
  pred = new int[i+2];
  i = 0;
  while (*(p + i) != INT_MAX) {
    *(pred + i) = *(p + i);
    i++;
  };
  *(pred + i) = pp;
  *(pred + i + 1) = INT_MAX;
};

class pathList {

 public:
  pathList(int num);
  ~pathList();
  int dim;
  path **pl;
  path *list(int i) { return(*(pl + i)); };
  void removeHead(int i);
  void prepend(int i, path *p);
};

pathList::pathList(int num) {
  pl = new path*[num];
  int i;
  dim = num;
  for (i = 0; i < num; i++) *(pl + i) = NULL;
};

pathList::~pathList() {
  int i;
  for (i = 0; i < dim; i++) {
    path *tmp1, *tmp2;
    tmp1 = *(pl + i);
    while (tmp1 != NULL) {
      tmp2 = tmp1;
      tmp1 = tmp1->next;
      delete tmp2;
    };
  };
  delete [] pl;
};

void pathList::removeHead(int i) {
  path *p = *(pl + i);
  *(pl + i) = p->next;
  delete p;
};

void pathList::prepend(int i, path *p) {
  p->next = *(pl + i);
  *(pl + i) = p;
};

pathList *TheNodeList::CBF(int source, double *c_matrix, double *d_matrix) {

  pathList *pl = new pathList(num);
  edgeQueue *eq = new edgeQueue;
  double cummDelay = 0;
  edge *e, *ee;
  
  int i;
  for (i = 0; i < num; i++) {
    if (*(d_matrix + (source * num) + i) < DELAYBOUND) {
      e = new edge(source, i, *(c_matrix + (source * num) + i), 
			 *(d_matrix + (source * num) + i), 0);
      eq->insert(e);
    };
  };

  while ((cummDelay < DELAYBOUND) && (eq->head != NULL)) {
    e = eq->dequeue();
    if (relaxed(pl, e, c_matrix, source) == True) {
      for (i = 0; i < num; i++) {
	if (*(d_matrix + (e->sink * num) + i) < DELAYBOUND) {
	  switch (obj) {
	  case PLAIN:
	    ee = new edge(e->sink, i, 
			  e->cost + *(c_matrix + (e->sink * num) + i), 
			  e->key + *(d_matrix + (e->sink * num) + i),
			  e->hops + 1);
	    break;
	  case MULT:
	    ee = new edge(e->sink, i, 
			  e->cost + 
			  *(c_matrix + (e->sink * num) + i) * (e->hops + 1), 
			  e->key + *(d_matrix + (e->sink * num) + i),
			  e->hops + 1);
	    break;
	  case ADD:
	    ee = new edge(e->sink, i, 
			  e->cost + *(c_matrix + (e->sink * num) + i) +
			  e->hops * ALPHA, 
			  e->key + *(d_matrix + (e->sink * num) + i),
			  e->hops + 1);
	    break;
	  };
	  eq->insert(ee);
	};
      };
    };
    cummDelay = e->key;
    delete e;
  };
  delete eq;
  return(pl);
};

int TheNodeList::relaxed(pathList *pl, edge *e, double *c_matrix, int srce) {
  path *currPath = pl->list(e->sink);
  path *p;
  if (currPath != NULL) {
    if (currPath->cost <= e->cost) {
      return(False);
    }
    else if (currPath->key == e->key) pl->removeHead(e->sink);
  };
  if (e->source != srce) {
    path *prevPath = pl->list(e->source);
//The following is used temporarily unitl I understand floating point precision
    while ((prevPath->cost < (e->cost - *(c_matrix +(e->source * num)+e->sink)
			      - 1)) &&   //-1 for floating point precision
	    (prevPath->next != NULL)) {
      prevPath = prevPath->next;
    };
    p = new path(prevPath->pred, e->source, e->cost, e->key);
  }
  else {
    int *tmpi;
    tmpi = new int;
    *tmpi = INT_MAX;
    p = new path(tmpi, srce, e->cost, e->key);
    delete tmpi;
  };
  pl->prepend(e->sink, p);
  return(True);
};

double TheNodeList::routerCAO(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();
   int srce = source->name();

   //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 the source is the only member in the group
     if ((group->count() == 1) && (group->headm()->nodePtr() == source)) {
       source->addRoutingEntry(addr, source);
       h = d = maxd = mind = 0;
       nodes = 1;
       return(0);
     };

     int gCount = group->count();
     int i, j, k;
     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
       and 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 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 srceMember = False;
     tmp = group->headm();
     while ((tmp != NULL) && (tmp->nodePtr() != source)) tmp = tmp->next();
     if (tmp != NULL) srceMember = True;

     pathList *pl;
     path *p1, *pBest;
     int best;
     int *member;
     member = new int[gCount];
     path **mPath;
     mPath = new path*[gCount];
     for (i = 0; i < gCount; i++) {
       *(member + i) = INT_MAX;
       *(mPath + i) = NULL;
     };
     int done = False;
     k = 0;
     while (done == False) {
       pl = CBF(srce, c_matrix, d_matrix);
       pBest = NULL;
       tmp = group->headm();
       while (tmp != NULL) {
	 if (tmp->nodePtr()->name() != srce) {
	   i = 0;
	   while ((i < k) && 
		  (*(member + i) != tmp->nodePtr()->name())) i++;
	   if (i == k) {
	     p1 = pl->list(tmp->nodePtr()->name()); 
	     while ((p1 != NULL) && (p1->key >= DELAYBOUND)) {
	       p1 = p1->next;
	     };
	     if (p1 != NULL) {
	       if (pBest == NULL) {
		 pBest = p1;
		 best = tmp->nodePtr()->name();
	       }
	       else if ((p1->cost < pBest->cost) ||
		       ((p1->cost == pBest->cost) && (p1->key < pBest->key))) {
		 pBest = p1;
		 best =  tmp->nodePtr()->name();
	       };
	     };
	   };
	 };
	 tmp = tmp->next();
       };

       if (pBest == NULL) {
	 delete [] member;
	 delete pl;
	 delete [] c_matrix;
	 delete [] d_matrix;
	 for (i = 0; i < gCount; i++) delete (*(mPath + i));
	 delete [] mPath;
	 return(SATORDB);
       }
       else {
	 *(member + k) = best;
	 p1 = new path(pBest->pred, best, pBest->cost, pBest->key);
	 *(mPath + k) = p1;
	 int from, to;
	 i = 1;
	 int *prev = p1->pred;
	 from = *prev;
	 to = *(prev + 1);
	 while (to != INT_MAX) {
	   *(c_matrix + (from * num) + to) = 0;
	   i++;
	   from = to;
	   to = *(prev + i);
	 };
       };
       delete pl;

       k++;
       if ((k == (group->count() - 1)) && (srceMember == True)) done = True;
       else if (k == group->count()) done = True;      
     };
     delete [] c_matrix;

     //The merge algorithm

     //First determine the number of paths traversing each node
     int *occur, *encountered, *pth;
     occur = new int[num];
     encountered = new int[num];
     for  (i = 0; i < num; i++) {
       *(occur + i) = 0;
       *(encountered + i) = 0;
     };
     for (i = 0; i < gCount; i++) {
       if (*(member + i) != INT_MAX) {
	 pth = (*(mPath + i))->pred;
	 j = 0;
	 while (*(pth + j) != INT_MAX) {
	   *(occur + *(pth + j)) += 1;