Simulation Simplified
20. Encyclopedia: Scalable?
Class P2Pedia08

import edu.rit.numeric.DoublePrng;
import edu.rit.numeric.ExponentialPrng;
import edu.rit.numeric.ListSeries;
import edu.rit.numeric.ListXYSeries;
import edu.rit.numeric.Series;
import edu.rit.numeric.UniformPrng;
import edu.rit.numeric.plot.Plot;
import edu.rit.sim.Event;
import edu.rit.sim.Simulation;
import edu.rit.util.Random;
import edu.rit.util.RandomSubset;
import java.util.HashSet;
import java.util.LinkedList;
public class P2Pedia08
   {
   // Knobs
   private static int N; // Number of nodes
   private static int K; // Number of extra connections per node
   private static double lambda_L; // First mean query arrival rate
   private static double lambda_U; // Last mean query arrival rate
   private static double lambda_D; // Mean query arrival rate increment
   private static double tx_L; // Query transmit time lower bound
   private static double tx_U; // Query transmit time upper bound
   private static int Q; // Maximum queries in query queue
   private static int R1; // Number of topologies per arrival rate
   private static int R2; // Number of queries per topology
   private static long seed; // PRNG seed

   // Global variables
   private static ListXYSeries meanElapsedTimeVsLambda;
   private static ListXYSeries failureFractionVsLambda;
   private static Random prng;
   private static DoublePrng txPrng;
   private static DoublePrng queryPrng;
   private static ListSeries elapsedTimes;
   private static int successCount;
   private static int queryCount;
   private static Simulation sim;
   private static Network network;

   private static class Query
      {
      private int id;
      private Node matchingNode;
      private double startTime;

      public Query
         (int id,
          Node matchingNode)
         {
         this.id = id;
         this.matchingNode = matchingNode;
         this.startTime = sim.time();
         }

      public boolean matches
         (Node node)
         {
         return node == matchingNode;
         }

      public double elapsedTime()
         {
         return sim.time() - startTime;
         }

      public boolean equals
         (Object obj)
         {
         return
            obj instanceof Query &&
            ((Query) obj).id == this.id;
         }

      public int hashCode()
         {
         return id;
         }
      }

   private static class Node
      {
      private int id;
      private LinkedList<Node> connectedNodes =
         new LinkedList<Node>();
      private LinkedList<Query> queryQueue =
         new LinkedList<Query>();
      private HashSet<Query> priorQueries =
         new HashSet<Query>();

      public Node
         (int id)
         {
         this.id = id;
         }

      public void connectTo
         (Node node)
         {
         connectedNodes.add (node);
         }

      public void addToQueue
         (Query query)
         {
         if (queryQueue.size() < Q)
            {
            queryQueue.add (query);
            if (queryQueue.size() == 1) startServing();
            }
         }

      private void startServing()
         {
         final Query query = queryQueue.getFirst();
         if (priorQueries.contains (query))
            {
            removeFromQueue();
            }
         else if (query.matches (this))
            {
            elapsedTimes.add (query.elapsedTime());
            ++ successCount;
            removeFromQueue();
            }
         else
            {
            double txTime = 0.0;
            for (Node nextNode : connectedNodes)
               {
               final Node nn = nextNode;
               txTime += txPrng.next();
               sim.doAfter (txTime, new Event()
                  {
                  public void perform()
                     {
                     nn.addToQueue (query);
                     }
                  });
               }
            sim.doAfter (txTime, new Event()
               {
               public void perform()
                  {
                  removeFromQueue();
                  }
               });
            }
         }

      private void removeFromQueue()
         {
         Query query = queryQueue.removeFirst();
         priorQueries.add (query);
         if (queryQueue.size() > 0) startServing();
         }
      }

   private static class Network
      {
      private Node[] node;

      public Network()
         {
         node = new Node[N];
         for (int i = 0; i < N; ++ i) node[i] = new Node (i);
         for (int i = 0; i < N; ++ i)
            {
            node[i].connectTo (node[(i + 1)%N]);
            RandomSubset rs = new RandomSubset (prng, N)
               .remove (i) .remove ((i + 1)%N);
            for (int j = 0; j < K; ++ j)
               {
               node[i].connectTo (node[rs.next()]);
               }
            }
         }

      public void generateQuery()
         {
         Node origNode = randomNode();
         Node matchNode = randomNode();
         Query query = new Query (++ queryCount, matchNode);
         origNode.addToQueue (query);
         if (queryCount < R2)
            {
            sim.doAfter (queryPrng.next(), new Event()
               {
               public void perform()
                  {
                  generateQuery();
                  }
               });
            }
         }

      private Node randomNode()
         {
         return node[prng.nextInt (node.length)];
         }
      }

   public static void main
      (String[] args)
      {
      // Knobs
      if (args.length != 11) usage();
      N = Integer.parseInt (args[0]);
      K = Integer.parseInt (args[1]);
      lambda_L = Double.parseDouble (args[2]);
      lambda_U = Double.parseDouble (args[3]);
      lambda_D = Double.parseDouble (args[4]);
      tx_L = Double.parseDouble (args[5]);
      tx_U = Double.parseDouble (args[6]);
      Q = Integer.parseInt (args[7]);
      R1 = Integer.parseInt (args[8]);
      R2 = Integer.parseInt (args[9]);
      seed = Long.parseLong (args[10]);

      // Global variables
      meanElapsedTimeVsLambda = new ListXYSeries();
      failureFractionVsLambda = new ListXYSeries();
      prng = Random.getInstance (seed);
      txPrng = new UniformPrng (prng, tx_L, tx_U);

      // Loop over all mean arrival rates.
      System.out.printf ("        -Elapsed Time-  Failure%n");
      System.out.printf ("Lambda  Mean    Stddev  Fraction%n");
      double lambda;
      for (int i = 0; (lambda = lambda_L + i*lambda_D) <= lambda_U;
            ++ i)
         {
         // Global variables
         queryPrng = new ExponentialPrng (prng, lambda);
         elapsedTimes = new ListSeries();
         successCount = 0;

         // Loop over R1 random topologies.
         for (int j = 0; j < R1; ++ j)
            {
            queryCount = 0;
            sim = new Simulation();
            network = new Network();

            // Run simulation
            network.generateQuery();
            sim.run();
            }

         // Print statistics.
         Series.Stats etStats = elapsedTimes.stats();
         double ff = 1.0 - (double)successCount/(double)(R1*R2);
         System.out.printf ("%-8.3f%-8.3f%-8.3f%-8.3f%n",
            lambda, etStats.mean, etStats.stddev, ff);
         meanElapsedTimeVsLambda.add (lambda, etStats.mean);
         failureFractionVsLambda.add (lambda, ff);
         }

      // Plot results.
      new Plot()
         .plotTitle ("P2Pedia08")
         .xAxisTitle ("Mean arrival rate \u03BB")
         .yAxisTitle ("Mean elapsed time")
         .xySeries (meanElapsedTimeVsLambda)
         .getFrame()
         .setVisible (true);
      new Plot()
         .plotTitle ("P2Pedia08")
         .xAxisTitle ("Mean arrival rate \u03BB")
         .yAxisTitle ("Failure fraction")
         .xySeries (failureFractionVsLambda)
         .getFrame()
         .setVisible (true);
      }

   private static void usage()
      {
      System.err.println
         ("Usage: java P2Pedia08 <N> <K> <lambda_L> <lambda_U> "+
          "<lambda_D> <tx_L> <tx_U> <Q> <R1> <R2> <seed>");
      System.exit (1);
      }
   }