vs.cc

题描述的是一个旅行商要到几个城市去

/* $Id: vs.cc,v 1.3 2006-08-21 15:02:00 jonathan Exp $
 * Jonathan Ledlie, Harvard University.
 * Copyright 2006.  All rights reserved.
 */

#include "node.h"

int lineCount = 0;
char *outputFormat = NULL;

int FRAME_INTERVAL = 1000;
char *outputPrefix = NULL;
int lastFrameStamp = 0;
bool flushSecFP = true;

float **distanceMatrixSys = NULL;
float **errorMatrixSys = NULL;
float **distanceMatrixApp = NULL;
float **errorMatrixApp = NULL;

FILE *sysCoordFP = NULL;
FILE *appCoordFP = NULL;
FILE *reFP = NULL;
FILE *sumreFP = NULL;
FILE *nodeFP = NULL;
FILE *ralpFP = NULL;

void perSecondOutput (int stamp);
bool isNeighbor (int myId, int yourId);

void printUsage () {

  cout << "vivaldi\n"
       << " -n nodeCount\n"
       << " -f sampleFile\n"
       << " -e error fraction (= " << ERROR_FRACTION << ")\n"
       << " -u dampening fraction (= " << DAMPENING_FRACTION << ")\n"
       << " -o measurement error (overhead) (= "<< measurement_error <<"ms)\n"
       << " -h ping history count (sample memory per node) (= "<<PING_HISTORY_COUNT<<")\n"
       << "    -1 uses an EWMA instead of a moving percentile filter\n"
       << "    and -p as alpha\n"
       << " -i min ping history count before using sample (= "<<MIN_HISTORY_COUNT<<")\n"
       << " -p percentile to use in moving percentile filter (0..1) (="<<PING_SAMPLE_PERCENTILE<<")\n"
       << " -g [ocsrlap] specialize output to... \n"
       << "   o: change with each observation\n"
       << "   S: sys coords at end of run\n"
       << "   A: app coords at end of run\n"
       << "   n: node statistics\n"
       << "   r: print relative error using median link latency file\n"
       << "   R: print summary of relative error using median link latency file\n"
       << "   p: print RRL, NARL, and RALP using median link latency file\n"
       << "   g: print coords every second (for gnuplot)\n"
       << "   s: print system-wide summary at -I interval (default=1000)\n"
       << " -k neighbor count\n"
       << " -x dimensions (= "<<DIMENSIONS<< ")\n"
       << " -d [debug] ("<<debug<<")\n"
       << " -m [e|l|s|a] ("<<Node::appCoordUpdateMethod<<"\n"
       << "   e: measure energy between two windows\n"
       << "   l: local relative distance between centroid of two windows\n"
       << "   s: measure change in system-level coordinate\n"
       << "   a: measure change in application-level coordinate\n"
       << "   c: measure change in application-level coordinate, \n"
       << "      and update it to centroid\n"
       << " -t threshold for updating application-level coordinate (="<<Node::appCoordUpdateThreshold<<")\n"
       << " -w window size (="<<Node::windowSize<<")\n"
       << " -l true latency matrix\n"
       << " -r rounds, choose randomly from latency matrix file\n"

       << " -b true latency matrix is full, e.g. allows asymetric links (=false)\n"

       << " -j sample expiration (in rounds or ms), if negative, no expiration\n"
       << " -I frequency for system-wide summary output\n"
       << " -O output prefix\n"
       << " -z use height\n"
       << " -s seed\n";
  exit (-1);
}

int main (int argc, char **argv) {
  char c =  0;
  char *sampleFile = NULL;
  char *trueLatencyMatrixFile = NULL;
  int seed = getpid();
  int ROUNDS = 0;

  FILE *fp;
  while ((c = getopt(argc,argv,"I:bf:n:e:u:s:o:x:h:p:dg:m:t:w:i:l:zr:j:O:k:")) >= 0) {
    switch (c) {
    case 'O':
      outputPrefix = optarg;
      break;
    case 'I':
      FRAME_INTERVAL = atoi(optarg);
      break;
    case 'f':
      sampleFile = optarg;
      break;
    case 'l':
      trueLatencyMatrixFile = optarg;
      break;
    case 'k':
      neighborCount = atoi(optarg);
      break;
    case 'z':
      USE_HEIGHT = true;
      break;
    case 'b':
      FULL_LATENCY_MATRIX = true;
      break;
    case 'j':
      SAMPLE_EXPIRATION = atoi (optarg);
      break;
    case 'h':
      PING_HISTORY_COUNT = atoi(optarg);
      break;
    case 'i':
      MIN_HISTORY_COUNT = atoi(optarg);
      break;
    case 'r':
      ROUNDS = atoi(optarg);
      break;
    case 'n':
      nodeCount = atoi(optarg);
      break;
    case 's':
      seed = atoi(optarg);
      break;
    case 'x':
      DIMENSIONS = atoi(optarg);
      break;
    case 'g':
      outputFormat = optarg;
      break;
    case 'm':
      Node::appCoordUpdateMethod = *optarg;
      break;
    case 'w':
      Node::windowSize = atoi(optarg);
      break;
    case 't':
      Node::appCoordUpdateThreshold = atof(optarg);
      break;
    case 'd':
      debug = true;
      break;
    case 'e':
      ERROR_FRACTION = atof(optarg);
      break;
    case 'p':
      PING_SAMPLE_PERCENTILE = atof(optarg);
      break;
    case 'o':
      measurement_error = atof(optarg);
      break;
    case 'u':
      DAMPENING_FRACTION = atof(optarg);
      break;
    default:
      printUsage ();
      break;
    }
  }

  srandom (seed);
  SRand (seed);

  if (outputPrefix == NULL) {
    printf("Output file prefix is required.\n");
    printUsage ();
  }

  if (outputFormat == NULL) {
    printf("Output format is required.\n");
    printUsage ();
  }

  if (nodeCount <= 0) {
    printf ("Bad sample file or node count\n");
    printUsage ();
  }

  if (trueLatencyMatrixFile != NULL && neighborCount < 0) {
    // assign neighbors
    printf ("Invalid neighbor count: %d\n", neighborCount);
    printUsage ();
  }
  // at this point, neighbor count is ignored if we are only using the samples file

  int myId, yourId;
  int stamp = 0;
  float rawLatencySample; 
  bool *validNode;

  // parse medians file, if available
  if (trueLatencyMatrixFile != NULL) {

    if ((fp = fopen (trueLatencyMatrixFile, "r")) == NULL) {
      printf ("Cannot open file %s", trueLatencyMatrixFile);
      exit (-1);
    }

    rtts = new float* [nodeCount];
    distanceMatrixSys = new float* [nodeCount];
    errorMatrixSys = new float* [nodeCount];
    distanceMatrixApp = new float* [nodeCount];
    errorMatrixApp = new float* [nodeCount];
    neighbors = new int* [nodeCount];
    validNode = new bool[nodeCount];

    // these temp variables stop compiler from complaining
    for (int myIdT = 0; myIdT < nodeCount; myIdT++) {
      rtts[myIdT] = new float[nodeCount];
      distanceMatrixSys[myIdT] = new float[nodeCount];
      errorMatrixSys[myIdT] = new float[nodeCount];
      distanceMatrixApp[myIdT] = new float[nodeCount];
      errorMatrixApp[myIdT] = new float[nodeCount];
      neighbors[myIdT] = new int[neighborCount];
      validNode[myIdT] = true;
      for (int yourIdT = 0; yourIdT < nodeCount; yourIdT++) {
	rtts[myIdT][yourIdT] = 0;
	distanceMatrixSys[myIdT][yourIdT] = 0;
	errorMatrixSys[myIdT][yourIdT] = 0;
	distanceMatrixApp[myIdT][yourIdT] = 0;
	errorMatrixApp[myIdT][yourIdT] = 0;
      }
      for (int yourIdT = 0; yourIdT < neighborCount; yourIdT++) {
	neighbors[myIdT][yourIdT] = -1;
      }
    }

    int badLatencySampleCount = 0;
    int totalLatencySampleCount = 0;
    while (fscanf (fp, "%d %d %f\n", &myId, &yourId, &rawLatencySample) > 0) {   
      if (rawLatencySample > 0.) {
        totalLatencySampleCount++;
	ASSERT (myId >= 0 && myId < nodeCount);
	ASSERT (yourId >= 0 && yourId < nodeCount);
        rtts[myId][yourId] = rawLatencySample;
        if (!FULL_LATENCY_MATRIX) {
          rtts[yourId][myId] = rawLatencySample;
        }
      } else {
        badLatencySampleCount++;
      }
    }
    fclose (fp);
    if (badLatencySampleCount > 0) {
      fprintf (stderr,"Input file contained %.3f%% bad samples\n",
	       (badLatencySampleCount/(double)totalLatencySampleCount));
    }

    //printf ("lat 0 1739 = 516.241 check %f\n", rtts[1739][0]);
    
    for (int myId = 0; myId < nodeCount; myId++) {
      // verify that everybody has enough neighbors
      int myNeighborCount = 0;
      for (int yourId = 0; yourId < nodeCount; yourId++) {
	if (rtts[myId][yourId] > 0.) {
	  myNeighborCount++;
	}
      }
      if (myNeighborCount < neighborCount) {
        //fprintf (stderr, "id %d nc %d\n", myId, myNeighborCount);
        validNode[myId] = false;
        //assert (myNeighborCount >= neighborCount);
      } else {

        if (neighborCount > 0) {

      for (int neighborId = 0; neighborId < neighborCount; neighborId++) {
	int yourId = myId;
	while (yourId == myId || rtts[myId][yourId] <= 0.
	       || isNeighbor(myId,yourId)) {
	  yourId = unifRand (0, nodeCount);
	}
	neighbors[myId][neighborId] = yourId;
	//if (myId == 1739) {
                //printf ("me %d neighborIndex %d you %d\n", myId, neighborId, yourId);
	//}
      }
        } else {
          ASSERT (neighborCount == 0);


      }
      }
    }

    int validNodeCount = 0;
    for (int myId = 0; myId < nodeCount; myId++) {
      if (validNode[myId]) {
	validNodeCount++;
      }
    }
    printf ("pct of nodes with at least %d neighbors: %.3f\n",
	    neighborCount, validNodeCount/(double)nodeCount);

  } else if (sampleFile == NULL) {
    printf ("Bad sample file or node count\n");
    printUsage ();
  }

  if (PING_SAMPLE_PERCENTILE < 0 || PING_SAMPLE_PERCENTILE > 1) {
    printf ("Bad ping sample percentile\n");
    printUsage ();
  }

  /*
  if (SAMPLE_EXPIRATION < 0)  {
    printf ("Sample expiration must be greater or equal to 0\n");
    printUsage ();
  }
  */

  if (PING_HISTORY_COUNT != -1 && 
      PING_HISTORY_COUNT < 0) {
    printf ("Bad ping history count\n");
    printUsage ();
  }

  if ((Node::appCoordUpdateMethod == 'l' ||
       Node::appCoordUpdateMethod == 'e') &&
      Node::windowSize <= 0) {
    printUsage ();
  }

  if (strchr(outputFormat,'o') != NULL)
    openOutputFile (runLogFP, outputPrefix, ".log");
  if (strchr(outputFormat,'S') != NULL)
    openOutputFile (sysCoordFP, outputPrefix, ".syscoord");
  if (strchr(outputFormat,'A') != NULL)
    openOutputFile (appCoordFP, outputPrefix, ".appcoord");
  if (strchr(outputFormat,'r') != NULL)
    openOutputFile (reFP, outputPrefix, ".re");
  if (strchr(outputFormat,'R') != NULL)
    openOutputFile (sumreFP, outputPrefix, ".sumre");
  if (strchr(outputFormat,'n') != NULL)
    openOutputFile (nodeFP, outputPrefix, ".node");
  if (strchr(outputFormat,'p') != NULL)
    openOutputFile (ralpFP, outputPrefix, ".ralp");
  if (strchr(outputFormat,'s') != NULL)
    openOutputFile (secFP, outputPrefix, "sec.log");

  // Finished checking user input
  // Start processing either the median file
  // or a ping trace

  node = new Node[nodeCount];

  if (sampleFile != NULL) {
    if ((fp = fopen (sampleFile, "r")) == NULL) {
      printf ("Cannot open file %s", sampleFile);
    }

    while (fscanf (fp, "%d %d %d %f\n", &stamp, &myId, &yourId,
                   &rawLatencySample) > 0) { 

      //if (stamp % 100) {
	//fprintf (stderr, "stamp %d\n", stamp);
      //}

      bool toss = false;
      if (trueLatencyMatrixFile != NULL) {
        if (!validNode[myId]) {
          fprintf (stderr, "tossing sample id %d\n", myId);
          toss = true;
        }
        // could add in neighbor checks here if neighbors were assigned on the fly
      }

      if (!toss) {
        node[myId].processSample (stamp, myId, yourId, rawLatencySample);
        perSecondOutput (stamp);