vivaldi.cc

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

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

#include "node.h"

FILE *runLogFP = NULL;
FILE *secFP = NULL;
vector<double> sec_sysRawRE_list;
double sec_sysDD_sum;
vector<double> sec_appRawRE_list;
double sec_appDD_sum;

void Node::processSample (int o_stamp, int myId, int o_yourId, float o_rawLatency) {

  // o_ refers to this observation
  // s_ refers to the sample being processed,
  //    as we go through our samples

  // distance refers to metric space distance
  // latency to actual observations

  if (debug)
    cout << "\n\nLINE: "<< o_stamp << " me " << myId << " you " 
	 << o_yourId << " s " << o_rawLatency << endl;

  if (myId >= nodeCount || o_yourId >= nodeCount) {
    printf ("id out of range, mine %d, yours %d\n", myId, o_yourId);
    exit (-1);
  }

  // remember samples from this node
  node[myId].addSample
    (o_yourId, o_rawLatency, node[o_yourId].vec, node[o_yourId].weightedError,
     node[o_yourId].appVector, o_stamp);

  // retrieve our idea of the underlying latency for this link
  double o_latency = node[myId].getSample (o_yourId);

  // remember when we last exchanged info with this guy
  node[myId].lastUpdateFrom = o_stamp;
  node[o_yourId].lastUpdateTo = o_stamp;

  if (o_latency > 0) {

    if (debug)
      cout << "my coord" << node[myId].vec << endl;

    double o_distance = node[myId].vec->getEuclideanDistance (node[o_yourId].vec);
    while (o_distance == 0) {
      node[myId].vec->bump();
      o_distance = node[myId].vec->getEuclideanDistance (node[o_yourId].vec);
    }
    if (o_distance == 0) {
      cout << "my coord " << node[myId].vec
	   << "your coord " << node[o_yourId].vec << endl;
    }
    assert (!isnan(o_distance));

    double o_relativeError = fabs(o_distance - o_latency) / o_latency;
    assert (!isnan(o_relativeError));

    double o_rawRelativeError = fabs(o_distance - o_rawLatency) / o_rawLatency;
    assert (!isnan(o_rawRelativeError));

    // EMWA on weightedError, based on how much we trust this current sample
    // update our confidence based on the confidence in this sample
    assert (node[myId].weightedError + node[o_yourId].weightedError > 0);

    double o_weight = node[myId].weightedError /
      (node[myId].weightedError + node[o_yourId].weightedError);
    assert (!isnan(o_weight));

    double o_alphaWeightedError = ERROR_FRACTION * o_weight;
    assert (!isnan(o_alphaWeightedError));

    // update our confidence
    node[myId].weightedError = (o_relativeError * o_alphaWeightedError) +
      (node[myId].weightedError * (1. - (o_alphaWeightedError)));

    if (debug) {
      printf ("weightedError = %f\n", node[myId].weightedError);
    }
    if (node[myId].weightedError > 1.) node[myId].weightedError = 1.;
    if (node[myId].weightedError < 0.) node[myId].weightedError = 0.;

    assert (!isnan(node[myId].weightedError));

    Point o_force;
    int measurementsUsed = 0;
    int o_oldestSample = o_stamp;

    // randomize processing of our neighbors
    // when SAMPLE_EXPIRATION == 0, we only process the most recent sample

    vector<int> validNodes;
    for (map<int,Samples*>::iterator samplesIter =
           node[myId].node2samples.begin(); 
         samplesIter != node[myId].node2samples.end(); samplesIter++) {

      int s_yourId = samplesIter->first;
      Samples *sample = samplesIter->second;


      if (sample->stamp < o_stamp - SAMPLE_EXPIRATION &&
	  SAMPLE_EXPIRATION >= 0) {
        if (debug)
          cout << "Expired id " << s_yourId << " sample " << sample << endl;
      } else {
        if (debug)
          cout << "Valid id " << s_yourId << " sample " << sample << endl;
        validNodes.push_back (s_yourId);
	if (o_oldestSample > sample->stamp) {
	  o_oldestSample = sample->stamp;
	}
      }
    }

    random_shuffle(validNodes.begin(),
                   validNodes.end());
    double o_sampleWeightSum = 0.;

    // let o_sampleWeightSum be sum of
    // relative age of each sample.
    // Then weigh each sample by its weight/o_sampleWeightSum
    for (int validNodeIndex = 0; validNodeIndex < validNodes.size();
         validNodeIndex++) {
      int s_yourId = validNodes[validNodeIndex];
      Samples *sample = node[myId].node2samples[s_yourId];
      o_sampleWeightSum += sample->stamp - o_oldestSample;
    }
    assert (o_sampleWeightSum >= 0);

    for (int validNodeIndex = 0; validNodeIndex < validNodes.size();
         validNodeIndex++) {

      int s_yourId = validNodes[validNodeIndex];
      Samples *sample = node[myId].node2samples[s_yourId];

      double s_distance = node[myId].vec->getEuclideanDistance
        (sample->vec);
      while (s_distance == 0.) {
	node[myId].vec->bump();
	s_distance = node[myId].vec->getEuclideanDistance (sample->vec);
      }
      assert (!isnan(o_distance));

      // find direction
      Point *s_unitVector = node[myId].vec->getDirection (sample->vec);
      if (s_unitVector == NULL) {
        s_unitVector = Point::getRandomUnitVector();
      }

      double s_latency = node[myId].getSample (s_yourId);
      if (debug)
        cout << "unitVector to id "<< s_yourId << " = "<<s_unitVector <<endl;

      // how much to weigh this sample
      // are his coords more reliable than mine?

      if (!(node[myId].weightedError + sample->weightedError > 0.)) {
	printf ("me %d you %d meas %d myWE %f yourWE %f\n",
		myId, s_yourId, measurementsUsed, node[myId].weightedError,
		sample->weightedError);
	exit (0);
      }

      assert (node[myId].weightedError + sample->weightedError > 0.);

      double s_weight = node[myId].weightedError /
        (node[myId].weightedError + sample->weightedError);


      if (debug) {
        printf ("sample weighted error = %f\n", s_weight);
        printf ("predicted distance = %f\n", s_distance);
        printf ("smoothed distance =    %f\n", s_latency);
      }

      // Meant to account for blips in very low latency links
      // When measurement_error == 0, this doesn't do anything

      // e_{s}
      if ( (s_distance < s_latency &&
            s_distance + measurement_error >= s_latency) ||
           (s_distance > s_latency &&
            s_distance - measurement_error <= s_latency)) {
        printf ("within measurement error\n");
        s_distance = s_latency;
        withinMeasurementError++;
      }


      // error of sample
      double s_error = s_distance - s_latency;
    
      // delta
      double s_dampening = s_weight;
      if (debug) {
        printf ("dampening = %f for vector adjustment\n", s_dampening);
      }

      // If you don't have this weight and have a bunch of neighbors
      // coords spin out of control (i.e. there is too much change
      // and they don't converge

      // Can also be achieved with 1/num neighbors
      // but this decays based on age of last sample to neighbor

      double s_sampleWeight = 1.;
      if (o_sampleWeightSum > 0) {
	s_sampleWeight = (sample->stamp - o_oldestSample)/o_sampleWeightSum;
      }

      s_unitVector->scale (s_error * s_dampening * s_sampleWeight);
      if (debug)
        cout << "scaled unitVector "<<s_unitVector <<endl;
      o_force.add (s_unitVector);
      if (debug)
        cout << "total force "<<&o_force <<endl;
      delete s_unitVector;
      measurementsUsed++;
    }
    
    // Update the local coordinate
    o_force.height = -o_force.height;
    o_force.scale (DAMPENING_FRACTION);

    if (debug) {
      cout << "before update "<< node[myId].vec << endl;
      cout << "force " << &o_force << endl;
    }

    node[myId].vec->add(&o_force);
    node[myId].vec->checkHeight();

    if (debug) {
      cout << "after update "<< node[myId].vec << endl;
    }

    double o_distanceDelta = fabs(o_force.length());
    node[myId].addDistanceDelta (o_distanceDelta);

    // Note: sometimes this happens toward the beginning of a large sim
    if (o_distanceDelta > 500) {
      fprintf (stderr, "large distance delta %.3f\n", o_distanceDelta);
    }

    if (debug) {
      cout << "dd " << o_distanceDelta << endl;
    }

    if (debug) {
      double o_distance = node[myId].vec->getEuclideanDistance (node[o_yourId].vec);
      cout << "new dist " << o_distance << endl;
    }

    double o_appCoordDistance = node[myId].appVector->getEuclideanDistance
      (node[o_yourId].appVector);
    Point *o_oldAppPosition = new Point (node[myId].appVector);

    // update nearest neighbor after changing our coordinate,
    // and before thinking about updating the appVector
    node[myId].addToNearestNeighbor (node[o_yourId].vec, o_stamp);

    double o_appComparison = 0.;
    bool o_updatedAppVector = node[myId].updateAppVector
      (o_distanceDelta, o_stamp,
       o_appComparison);

    if (debug)
      cout << "appCoordDistance " << o_appCoordDistance << endl;
    double o_appDistanceDelta =
      o_oldAppPosition->getAbsoluteDistance (node[myId].appVector);
    double o_appRawRelativeError = 
      fabs(o_appCoordDistance - o_rawLatency) / o_rawLatency;   
    double o_appRelativeError = 
      fabs(o_appCoordDistance - o_latency) / o_latency;   
    delete o_oldAppPosition;

    if (secFP) {
      sec_sysRawRE_list.push_back (o_rawRelativeError);
      sec_sysDD_sum += o_distanceDelta;
      sec_appRawRE_list.push_back (o_appRawRelativeError);
      sec_appDD_sum += o_appDistanceDelta;
    }

    if (runLogFP) {
      fprintf (runLogFP, "%d me %3d you %3d s %7.2f ss %7.2f confi %4.3f dd %6.3f re %5.3f sA %d ",
               o_stamp, myId, o_yourId, o_rawLatency, o_latency,
               node[myId].weightedError, o_distanceDelta,
               o_relativeError, o_oldestSample);
      fprintf (runLogFP, " [ ");
      node[myId].printCoord(runLogFP);
      fprintf (runLogFP, " ]\n");
    }
  }

  if (debug) {
    printf ("\n\n\n");
  }
}