ttnetwork.cpp

一个很棒的网络控制系统仿真软件

#include "mex.h"
#include "mexhelp.h"
#include "linkedlist.cpp"

#include <math.h>

#include "ttnetwork.h"

#define EPS 0.0000001  // 0.1 us
#define INF 1000000.0

// ----- Main data structure ------

RTnetwork *nwsys;  

// ------- Network functions -------

// returns a uniformly distributed random number between a and b (inclusive)
// (assumes b >= a and a >= 0)
int urand(int a, int b) {
  return a + rand() % (b-a+1);
}

// computes the remaining transmission time of the current frame
double remxtime(NWmsg *m) {
  switch (nwsys->type) {
  case FDMA:
    return m->remaining / (nwsys->bandwidths[m->sender] * nwsys->datarate + EPS);
  default:
    return m->remaining / nwsys->datarate;
  }
}

// allocates switch memory, if possible
bool switchmalloc(int sender, int receiver, int length) {
  int i;
  if (nwsys->buftype == OUTPUTBUF) {
    if (receiver == -1) { // broadcast
      // make sure there is memory in each buffer first
      bool ok = true;
      for (i=0; i<nwsys->nbrOfNodes; i++) {
	if (sender != i) {
	  if (nwsys->nwnodes[i]->switchmem < length) {
	    ok = false;
	    break;
	  }
	}
      }
      if (!ok) return false;
      // allocate memory
      for (i=0; i<nwsys->nbrOfNodes; i++) {
	if (sender != i) {
	  nwsys->nwnodes[i]->switchmem -= length;
	  //printf("Broadcast: %d bytes allocated in output buffer %d, remaining %d\n", length, i, nwsys->nwnodes[i]->switchmem);
	}
      }
      return true;
    } else {
      if (nwsys->nwnodes[receiver]->switchmem < length) return false;
      nwsys->nwnodes[receiver]->switchmem -= length;
      //printf("%d bytes allocated in output buffer %d, remaining %d\n", length, receiver, nwsys->nwnodes[receiver]->switchmem);
      return true;
    }
  } else {
    if (receiver == -1) { // broadcast
      if (nwsys->switchmem < (nwsys->nbrOfNodes-1)*length) return false;
      nwsys->switchmem -= (nwsys->nbrOfNodes-1)*length;
      //printf("Broadcast: %d bytes allocated in common buffer, remaining %d\n", (nwsys->nbrOfNodes-1)*length, nwsys->switchmem);
      return true;
    } else {
      if (nwsys->switchmem < length) return false;
      nwsys->switchmem -= length;
      //printf("%d bytes allocated in common buffer, remaining %d\n", length, nwsys->switchmem);      
      return true;
    }
  }
}

// frees switch memory
void switchfree(int receiver, int length) {
  if (nwsys->buftype == OUTPUTBUF) {
    nwsys->nwnodes[receiver]->switchmem += length;
    //printf("%d freed in output buffer %d, remaining %d\n", length, receiver, nwsys->nwnodes[receiver]->switchmem);    
  } else {
    nwsys->switchmem += length;
    //printf("%d bytes freed in common buffer, remaining %d\n", length, nwsys->switchmem);      
   }
}


// Returns the time of the next invocation (nextHit)
double runNetwork() {
  
  int i, j;
  NWmsg *m, *m2;  // m is our message, m2 is contending message
  NWmsg *next;
  double timeElapsed;
  double nextHit = INF;
  double waittime;

  timeElapsed = nwsys->time - nwsys->prevHit; // time since last invocation
  nwsys->prevHit = nwsys->time;

  //printf("Running network at %f\n", nwsys->time);

  // Check if messages have finished waiting in the preprocQ's

  for (i=0; i<nwsys->nbrOfNodes; i++) {
    m = (NWmsg *)nwsys->nwnodes[i]->preprocQ->getFirst();
    while (m != NULL) {
      if (m->waituntil - nwsys->time < EPS) {
	//printf("moving message from preprocQ to inputQ at %f\n", nwsys->time);
	m->remaining = max(m->length, nwsys->minsize);
	nwsys->nwnodes[i]->preprocQ->removeNode(m);
	nwsys->nwnodes[i]->inputQ->appendNode(m);
      } else {
	// update nextHit?
	if (m->waituntil < nextHit) {
	  nextHit = m->waituntil;
	}
      }
      m = (NWmsg *)m->getNext();
    }
  }
  
  // Do the main processing of different protocols
  switch (nwsys->type) {

  case CSMACD:
    if (nwsys->sending != -1) { // not been idle
      //printf("Node %d has been sending\n", nwsys->sending);
	m = (NWmsg *)nwsys->nwnodes[nwsys->sending]->inputQ->getFirst();
	// decrease remaining number of bytes in current frame
	m->remaining -= (nwsys->datarate * timeElapsed);
	// frame finished?
	if (m->remaining < EPS) {
	  nwsys->nwnodes[nwsys->sending]->nbrcollisions = 0; // reset coll. counter
	  // transmission is finished, move to outputQ
	  //printf("Transmission finished\n");
	  nwsys->nwnodes[nwsys->sending]->inputQ->removeNode(m);
	  if (m->receiver == -1) {
	    // Broadcast
	    for (j=0; j<nwsys->nbrOfNodes; j++) {
	      if (j != m->sender) {
		nwsys->nwnodes[j]->outputQ->appendNode(m);
	      }
	    } 
	  } else {
	    nwsys->nwnodes[m->receiver]->outputQ->appendNode(m);
	  }
	    
	  m->waituntil = nwsys->time + nwsys->postdelay;
	  nwsys->nwnodes[nwsys->sending]->state = 0; // idle
	  nwsys->sending = -1;
	  // update nextHit?
	  if (m->waituntil < nextHit && nwsys->postdelay > 0.0) {
	    nextHit = m->waituntil;
	  }
	} else {
	  if (nwsys->time + remxtime(m) < nextHit) {
	    nextHit = nwsys->time + remxtime(m);
	  }	  
	}
    }
    
    // check if some node has finished waiting after a collision
    for (i=0; i<nwsys->nbrOfNodes; i++) {
      if (nwsys->nwnodes[i]->state == 3) {
	if (nwsys->time >= nwsys->nwnodes[i]->waituntil) {
	  //printf("Node %d has finished waiting\n", i);
	  nwsys->nwnodes[i]->state = 0; // idle again
	} else if (nwsys->nwnodes[i]->waituntil < nextHit) {
	  nextHit = nwsys->nwnodes[i]->waituntil;
	}
      }
    }

    // if network appears idle, check if any new nodes want to transmit
    if (nwsys->sending == -1 || nwsys->time < nwsys->lasttime + COLLISION_WINDOW) {
      //printf("The network *appears* to be idle\n");
      // do any nodes want to transmit?
      for (i=0; i<nwsys->nbrOfNodes; i++) {
	// not sending already and anything to send?
	if (nwsys->nwnodes[i]->state == 0 && (m = (NWmsg *)nwsys->nwnodes[i]->inputQ->getFirst()) != NULL) {
	  //printf("Node %d wants to transmit...\n", i);
	  if (nwsys->sending == -1) { // really idle?
	    //printf("Medium is idle at time %f, node %d starts to transmit...\n", nwsys->time, i);
	    //printf("Remaining: %f\n", m->remaining);
	    nwsys->lasttime = nwsys->time;
	    nwsys->nwnodes[i]->state = 1; // sending
	    nwsys->sending = i;
	    // update nextHit?
	    if (nwsys->time + remxtime(m) < nextHit) {
	      nextHit = nwsys->time + remxtime(m);
	    }
	  } else { // collision!
	    //printf("Collision when node %d tried to send at time %f!\n", i, nwsys->time);
	    // mark both nodes as colliding
	    nwsys->nwnodes[i]->state = 2; // colliding
	    nwsys->nwnodes[nwsys->sending]->state = 2; // colliding
	    // abort the currently transmitted frame
	    m = (NWmsg *)nwsys->nwnodes[nwsys->sending]->inputQ->getFirst();
	    m->remaining = max(m->length, nwsys->minsize);  // restore remaining
	  }
	}
      }
    }

    // move nodes from colliding to waiting state
    for  (i=0; i<nwsys->nbrOfNodes; i++) {
      if (nwsys->nwnodes[i]->state == 2) {
	nwsys->sending = -1;
	nwsys->nwnodes[i]->state = 3;
	nwsys->nwnodes[i]->nbrcollisions += 1;
	//printf("node %d has now collided %d times in a row\n", i, nwsys->nwnodes[i]->nbrcollisions);
	if (nwsys->nwnodes[i]->nbrcollisions > 10) {
	  nwsys->nwnodes[i]->nbrcollisions = 10;
	  // printf("max number of collisions reached!\n");
	}
	// compute random back-off time
	waittime = urand(0, (1 << nwsys->nwnodes[i]->nbrcollisions) - 1) * nwsys->minsize / nwsys->datarate;
	nwsys->nwnodes[i]->waituntil = nwsys->time + max(waittime, 2.0*COLLISION_WINDOW);
	//printf("Will reattempt at %f\n", nwsys->nwnodes[i]->waituntil);
	if (nwsys->nwnodes[i]->waituntil < nextHit) {
	  nextHit = nwsys->nwnodes[i]->waituntil;
	}
      }
    }
    break;

  case CSMAAMP:
    if (nwsys->sending != -1) { // not been idle
      // printf("Node %d has been sending\n", nwsys->sending);
	m = (NWmsg *)nwsys->nwnodes[nwsys->sending]->inputQ->getFirst();
	// decrease remaining number of bytes in current frame
	m->remaining -= (nwsys->datarate * timeElapsed);
	// frame finished?
	if (m->remaining < EPS) {
	  // transmission is finished, move to outputQ
	  // printf("Transmission finished\n");
	  nwsys->nwnodes[nwsys->sending]->inputQ->removeNode(m);

	  if (m->receiver == -1) {
	    // Broadcast
	    for (j=0; j<nwsys->nbrOfNodes; j++) {
	      if (j != m->sender) {
		nwsys->nwnodes[j]->outputQ->appendNode(m);
	      }
	    }
	  } else {
	    nwsys->nwnodes[m->receiver]->outputQ->appendNode(m);
	  }
	  
	  m->waituntil = nwsys->time + nwsys->postdelay;
	  nwsys->nwnodes[nwsys->sending]->state = 0; // idle
	  nwsys->sending = -1;
	  // update nextHit?
	  if (m->waituntil < nextHit && nwsys->postdelay > 0.0) {
	    nextHit = m->waituntil;
	  }
	} else {
	  if (nwsys->time + remxtime(m) < nextHit) {
	    nextHit = nwsys->time + remxtime(m);
	  }	  
	}
    }
    
    if (nwsys->sending == -1 || nwsys->time < nwsys->lasttime + COLLISION_WINDOW) {
      // printf("The network *appears* to be idle\n");
      // do any nodes want to transmit?
      for (i=0; i<nwsys->nbrOfNodes; i++) {
	// not sending already and anything to send?
	if (nwsys->nwnodes[i]->state == 0 && (m = (NWmsg *)nwsys->nwnodes[i]->inputQ->getFirst()) != NULL) {
	  // printf("Node %d wants to transmit...\n", i);
	  if (nwsys->sending == -1) { // still idle?
	    // printf("Medium is idle, node %d starts to transmit...\n", i);
	    nwsys->lasttime = nwsys->time;
	    nwsys->nwnodes[i]->state = 1; // sending
	    nwsys->sending = i;
	    // update nextHit?
	    if (nwsys->time + remxtime(m) < nextHit) {
	      nextHit = nwsys->time + remxtime(m);
	    }
	  } else { // collision!
	    // printf("Medium was not idle - collision!\n");
	    m2 = (NWmsg *)nwsys->nwnodes[nwsys->sending]->inputQ->getFirst();
	    // printf("Sending message has priority %f, our message has priority %f\n", m2->prio, m->prio);
	    if (m->prio > m2->prio) { // we have lower prio?
	      // printf("We lose the contention, will try again later\n");
	      if (nwsys->time + remxtime(m2) < nextHit) {
		nextHit = nwsys->time + remxtime(m2);
	      }
	    } else { // we have higher prio
	      // printf("We win the contention, other message aborted!\n");
	      m2->remaining = max(m2->length, nwsys->minsize); // restore remaining
	      nwsys->nwnodes[nwsys->sending]->state = 0;
	      nwsys->nwnodes[i]->state = 1;
	      nwsys->sending = i;
	      if (nwsys->time + remxtime(m) < nextHit) {
		nextHit = nwsys->time + remxtime(m);
	      }
	    }
	  }
	}
      }
    }
    break;

  case RR:
    if (nwsys->sending == -1) {
      // printf("The network has been idle\n");
      // ready for the next transmission?
      if (nwsys->time >= nwsys->waituntil) {
	nwsys->rrturn = (nwsys->rrturn + 1) % nwsys->nbrOfNodes;
	// printf("Token passed to node %d at time %f,\n", nwsys->rrturn, nwsys->time);
	if ((m = (NWmsg *)nwsys->nwnodes[nwsys->rrturn]->inputQ->getFirst()) != NULL) {
	  // printf("  node %d starts to transmit\n", nwsys->rrturn);
	  nwsys->sending = nwsys->rrturn;
	  nwsys->nwnodes[nwsys->rrturn]->state = 1; // we're sending
	  // update nextHit?
	  if (nwsys->time + remxtime(m) < nextHit) {
	    nextHit = nwsys->time + remxtime(m);
	  }
	} else {
	  // printf("  node %d has nothing to send, will idle...\n", nwsys->rrturn);
	  nwsys->waituntil = nwsys->time + nwsys->minsize / nwsys->datarate;
	  // update nextHit?
	  if (nwsys->waituntil > nwsys->time && nwsys->waituntil < nextHit) {
	    nextHit = nwsys->waituntil;
	  }
	}
      } else {// wait some more
	// update nextHit?
	if (nwsys->waituntil < nextHit) {
	  nextHit = nwsys->waituntil;
	}
      }
    } else {
      // printf("Node %d has been sending\n", nwsys->sending);
      m = (NWmsg *)nwsys->nwnodes[nwsys->sending]->inputQ->getFirst();
      // count down remaining transmission length
      m->remaining -= (nwsys->datarate * timeElapsed);
      // frame finished?
      if (m->remaining < EPS) { // yes
	// finished transmission, move to outputQ
	// printf("Transmission finished\n");
	nwsys->nwnodes[nwsys->sending]->inputQ->removeNode(m);
	
	if (m->receiver == -1) {
	  // Broadcast
	  for (j=0; j<nwsys->nbrOfNodes; j++) {
	    if (j != m->sender) {
	      nwsys->nwnodes[j]->outputQ->appendNode(m);
	    }
	  }
	} else {
	  nwsys->nwnodes[m->receiver]->outputQ->appendNode(m);
	}
	
	m->waituntil = nwsys->time + nwsys->postdelay;
	// update nextHit?