node2.c

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

/*
 * Copyright (c) 1995 Center for Advanced Computing and Communications (CACC),
 * North Carolina State University at Raleigh.
  * All rights reserved.
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted, provided
 * that the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation.  The CACC makes no representations about the
 * suitability of this software for any purpose.  It is provided "as is"
 * without express or implied warranty.
 */

/*****************************************************************************
***                      Author: Hussein F. Salama                         ***
***                       Date: September 9, 1994                          ***
***                            File: node2.c                               ***
***         A library defining node, routing tables, sources,              ***
***         adajacency lists and networks management operations            ***
***      This file contains the function simulation and the random graph   ***
***      and the random link generator and functions to read from file     ***
***      and write to file and other functions                             *** 
*****************************************************************************/

#include "node2.h"
#include "traf.c"
#include "rout.c"
#include "routATM.c"
#include "routCST.c"
#include "routLD.c"
#include "routKMB.c"
#include "routBF.c"
#include "routCAO.c"
#include "routBSMA.c"
#include "routDCDIMST.c"
#include "routOPT.c"
#include "routDVMRP.c"
#include "routBFNOADM.c"
#include "routCDKS.c"
#include "source.c"
#include "additional.c"


double ran() {                    // returns a random number in [0 1]
     return(rand() / RAND_REF);
};

Source *Node::addSource(int model, int type, int pr, double peak, 
                        double avg_rho, double burstiness, int addr) {

   SourceList *temp1;
   Source *s;

   if (model == IBP) 
   s = new IBPSource(type, pr, this, addr, peak, avg_rho, burstiness);
   else if (model == VOICE)
   s = new VoiceSource(type, pr, this, addr, peak, avg_rho, burstiness);
   else if (model == VIDEO)
   s = new VideoSource(type, pr, this, addr, peak, avg_rho, burstiness);
   else if (model == BACKGROUND)
   s = new BackgroundSource(type, pr, this, addr, peak, avg_rho, burstiness);

   temp1 = new SourceList;
   temp1->source(s);
   if (sl == NULL) sl = temp1; 
   else {
      temp1->next(sl);
      sl = temp1;
   };
   return(s);
};

int Node::removeSource(int type, int priority, int addr) {

// removes a source from the source list of a node

   SourceList *temp1, *temp2;

   temp1 = sl;
   int found = False;
   while ((temp1 != NULL) && (found == False)) {
      if ((temp1->source()->address() == addr) && 
          (temp1->source()->priority() == priority) &&
          (temp1->source()->type() == type)) found = True;
      else {
          temp2 = temp1;
          temp1 = temp1->next();
      };
   };
   if (found == True) {
      if (temp1 == sl) sl = temp1->next();
      else temp2->next(temp1->next());
      delete temp1;
      return(True);
   }
   else return(False);
};

void RoutingTableEntry::addDestination(Node *nd) {

// add a destination to the routing table entry for a given address

   NodeListEntry *tmp = new NodeListEntry;

   tmp->nodePtr(nd);
   tmp->next(d);
   d = tmp;
};

void RoutingTableEntry::removeDestination(Node *nd) {
 
// remove a destination from the routing table entry for a given address

   NodeListEntry *tmp1, *tmp2;

   tmp1 = d;
   tmp2 = NULL;
   int found = False;

   while ((tmp1 != NULL) && (found == False)) {
      if (tmp1->nodePtr() == nd) found = True;
      else {
         tmp2 = tmp1; 
         tmp1 = tmp1->next();
      };
   };
   if (found == True) {
      if (tmp1 == d) d = tmp1->next();
      else tmp2->next(tmp1->next());
      delete tmp1;
   };     
};

void Node::addChild(int addr, Node *source, Node *child) {
// adds a child to the routing table of a node

   RoutingTableEntry *temp1;

   temp1 = rte;
   int found = 0;
   while ((temp1 !=NULL) && (found == 0)) { 
       if ((temp1->address() == addr) && (temp1->source() == source)) 
                     found = 1;
       else temp1 = temp1->next();
   };
   if (temp1 == NULL) {
      temp1 = new RoutingTableEntry(addr, source);
      temp1->next(rte);
      rte = temp1;
   };
   temp1->addDestination(child);
};

void Node::addRoutingEntry(int addr, Node *source) {

   RoutingTableEntry *temp1 =rte;
   int found = 0;
   while ((temp1 != NULL) && (found == 0)) { 
       if ((temp1->address() == addr) && (temp1->source() == source)) 
                     found = 1;
       else temp1 = temp1->next();
   };
   if (temp1 == NULL) {
      temp1 = new RoutingTableEntry(addr, source);
      temp1->next(rte);
      rte = temp1;
   };
};
   
void Node::removeChild(int addr, Node *source, Node *child) {

// removes a child from the routing table of a node

   RoutingTableEntry *temp1;

   temp1 =rte;
   int found = 0;
   while ((temp1 !=NULL) && (found == 0)) { 
       if ((temp1->address() == addr) && (temp1->source() == source)) 
                     found = 1;
       else temp1 = temp1->next();
   };
   if (temp1 != NULL) temp1->removeDestination(child);  
};

void Node::removeRoutingEntry(int addr, Node *source) {

// removes an entry from the routing table of a node

   RoutingTableEntry *temp1, *temp2;

   temp1 = rte;
   temp2 = NULL;
   int found = 0;
   while ((temp1 != NULL) && (found == 0)) { 
       if ((temp1->address() == addr) && (temp1->source() == source)) 
                     found = 1;
       else {
	 temp2 = temp1;
	 temp1 = temp1->next();
       };
   };
   if (found == True) {
     if (temp2 == NULL) rte = temp1->next();
     else temp2->next(temp1->next());
     delete temp1;
   };
};

AdjacencyListEntry::AdjacencyListEntry(Node *nn, double x, double y, 
				       double c) {

   nd = nn;
   n = NULL;

   if (QTYPE == FIFO) q = new FIFOQueue();
   else q = new PriorityQueue(PRIORITYLEVELS);
   dist = sqrt((nd->X() - x) * (nd->X() - x) + (nd->Y() - y) * (nd->Y() - y));
   del = dist * Tpropagation + Tswitching;
   bsy = False;
   avg  = pk = 0.0;
   cpcty = c;
};


int Node::addNeighbor(Node *nbor, double capacity, double pk, double avg) {
                                                // future: check to see if 
                                                // nbor is already in the list

// adds a neighbor to the adjacency list of a node

   AdjacencyListEntry *temp1, *temp2;

   temp1 =ale;

   while ((temp1 != NULL) && (temp1->nodePtr()->name() != nbor->name()))
   temp1 = temp1->next();
   if (temp1 == NULL) {
      temp2 = new AdjacencyListEntry(nbor, x, y, capacity);
      temp2->peak(pk);
      temp2->average(avg);
      temp2->next(ale);
      ale = temp2;
      return(1);
   }
   else return(0);
};

int Node::removeNeighbor(Node *nbor) {

// removes a neighbor from the adjacency list of a node

   AdjacencyListEntry *temp1, *temp2;

   temp2 = ale;
   while ((temp2 != NULL) && (temp2->nodePtr()->name() != nbor->name())) { 
      temp1 = temp2;
      temp2 = temp2->next();
   };
   if (temp2 != NULL) {
      if ((temp2 != ale) && (temp2->nodePtr()->name() == nbor->name())) {
         temp1->next(temp2->next());
         delete temp2;
      }
      else if ((temp2 == ale) && (temp2->nodePtr()->name() == nbor->name())) {
         ale = temp2->next();
         delete temp2;
      };
      return(1);
   }
   else return(0);   
};

RoutingTableEntry::~RoutingTableEntry() {

   NodeListEntry *tmp1, *tmp2;

   tmp1 = d;
   while (tmp1 != NULL) {
      tmp2 = tmp1->next();
      delete tmp1;
      tmp1 = tmp2;
   };
};   

Node::~Node() {

   AdjacencyListEntry *adj1, *adj2, *adj3, *adj4;
   RoutingTableEntry  *rout1, *rout2;
   SourceList *s1, *s2;
   Node *nd;

   adj1 = ale;
   while (adj1 != NULL) {
      adj2 = adj1->next();
      nd = adj1->nodePtr();
      adj3 = nd->adjacentNodes();
      adj4 = NULL;
      while (adj3->nodePtr() != this) {
          adj4 = adj3;
          adj3 = adj3->next();
      };
      if (adj4 != NULL) adj4->next(adj3->next());
      else nd->adjacentNodes(adj3->next());
      delete adj3;
      delete adj1;
      adj1 = adj2;
   };
   rout1 = rte;
   while (rout1 != NULL) {
       rout2 = rout1->next();
       delete rout1;
       rout1 = rout2;
   };

   s1 = sl;
   while (s1 != NULL) {
       s2 = s1->next();
       delete s1;
       s1 = s2;
   };
};   

void TheNodeList::addNode(NodeListEntry *n) {

// adds a node to the node list

   n->next(NULL);
   n->previous(NULL);
   n->nodePtr()->name(maxName);
   if (nodeListHd != NULL) {
      nodeListTl->next(n);
      n->previous(nodeListTl);
      nodeListTl = n;
   }
   else {
      nodeListHd = nodeListTl = n;
   };
   maxName++;   
   num++;
};

int TheNodeList::removeSubtree(Node *source, int addr, Node *root) {

   int status = False;

   //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();
   };
   if (found == False) return(status);
   double pk = ss->source()->peak();
   double avg = ss->source()->average();

   //First locate the routing table entry corresponding to the given group and
   //source
   RoutingTableEntry *rout = root->routingTable();
   RoutingTableEntry *prout = NULL;
   found = False;
   while ((rout != NULL) && (found == False)) {
     if ((rout->address() == addr) && (rout->source() == source)) found = True;
     else {
       prout = rout;
       rout = rout->next();
     };
   };
      
  if (found == True) {
      NodeListEntry *tmp = rout->children();
      NodeListEntry *prev = NULL;
      while (tmp != NULL) {

          AdjacencyListEntry *adj = root->adjacentNodes();
          int found2 = 0;
          while ((adj != NULL) && (found2 == 0)) {
                if (adj->nodePtr() == tmp->nodePtr()) found2 = 1;
                else adj = adj->next();
          };
          if (adj != NULL) {
             double peak = adj->peak() - pk;
             adj->peak(peak);
             double average = adj->average() - avg;
             adj->average(average);
          }; 

          int nme = tmp->nodePtr()->name();
          int state = removeSubtree(source, addr, tmp->nodePtr());
          if (state == False) {
              prev = tmp;
              tmp = tmp->next();
          }
          else {
               rout->removeDestination(tmp->nodePtr());
               if (prev == NULL) tmp = rout->children();
               else tmp = prev->next();
          };
      };
   
      if (prout == NULL) root->routingTable(rout->next());
      else prout->next(rout->next()); 
      delete rout;

      status = True;
   };
   return(status);
};