Simulation Simplified
19. A Distributed Encyclopedia, Part 2
Class P2Pedia07

import edu.rit.numeric.DoublePrng;
import edu.rit.numeric.ExponentialPrng;
import edu.rit.numeric.ListSeries;
import edu.rit.numeric.Series;
import edu.rit.numeric.UniformPrng;
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 P2Pedia07
   {
   // Knobs
   private static int N; // Number of nodes
   private static int K; // Number of extra connections per node
   private static double lambda; // Mean query arrival rate
   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 R; // Number of queries to simulate
   private static long seed; // PRNG seed

   // Global variables
   private static Random prng;
   private static DoublePrng queryPrng;
   private static DoublePrng txPrng;
   private static int queryCount;
   private static ListSeries elapsedTimes;
   private static int successCount;
   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;
         }

      public String toString()
         {
         return "Query " + 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)
            {
            System.out.printf ("%.3f %s received by %s%n",
               sim.time(), query, this);
            queryQueue.add (query);
            if (queryQueue.size() == 1) startServing();
            }
         else
            {
            System.out.printf ("%.3f %s dropped by %s%n",
               sim.time(), query, this);
            }
         }

      private void startServing()
         {
         final Query query = queryQueue.getFirst();
         if (priorQueries.contains (query))
            {
            System.out.printf ("%.3f %s previously seen by %s%n",
               sim.time(), query, this);
            removeFromQueue();
            }
         else if (query.matches (this))
            {
            System.out.printf ("%.3f %s matches at %s%n",
               sim.time(), query, this);
            elapsedTimes.add (query.elapsedTime());
            ++ successCount;
            removeFromQueue();
            }
         else
            {
            System.out.printf ("%.3f %s sent from %s to",
               sim.time(), query, this);
            double txTime = 0.0;
            for (Node nextNode : connectedNodes)
               {
               System.out.printf (" %s", nextNode);
               final Node nn = nextNode;
               txTime += txPrng.next();
               sim.doAfter (txTime, new Event()
                  {
                  public void perform()
                     {
                     nn.addToQueue (query);
                     }
                  });
               }
            System.out.println();
            sim.doAfter (txTime, new Event()
               {
               public void perform()
                  {
                  removeFromQueue();
                  }
               });
            }
         }

      private void removeFromQueue()
         {
         Query query = queryQueue.removeFirst();
         System.out.printf ("%.3f %s removed from %s%n",
            sim.time(), query, this);
         priorQueries.add (query);
         if (queryQueue.size() > 0) startServing();
         }

      public String toString()
         {
         return "Node " + id;
         }
      }

   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);
         System.out.printf
            ("%.3f %s generated, originating %s, matching %s%n",
             sim.time(), query, origNode, matchNode);
         origNode.addToQueue (query);
         if (queryCount < R)
            {
            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 != 8) usage();
      N = Integer.parseInt (args[0]);
      K = Integer.parseInt (args[1]);
      lambda = Double.parseDouble (args[2]);
      tx_L = Double.parseDouble (args[3]);
      tx_U = Double.parseDouble (args[4]);
      Q = Integer.parseInt (args[5]);
      R = Integer.parseInt (args[6]);
      seed = Long.parseLong (args[7]);

      // Global variables
      prng = Random.getInstance (seed);
      queryPrng = new ExponentialPrng (prng, lambda);
      txPrng = new UniformPrng (prng, tx_L, tx_U);
      queryCount = 0;
      elapsedTimes = new ListSeries();
      successCount = 0;
      sim = new Simulation();
      network = new Network();

      // Run simulation
      network.generateQuery();
      sim.run();
      Series.Stats etStats = elapsedTimes.stats();
      double ff = 1.0 - (double)successCount/(double)R;
      System.out.printf ("Elapsed time mean = %.3f%n",
         etStats.mean);
      System.out.printf ("Elapsed time stddev = %.3f%n",
         etStats.stddev);
      System.out.printf ("Failure fraction = %.3f%n", ff);
      }

   private static void usage()
      {
      System.err.println
         ("Usage: java P2Pedia07 <N> <K> <lambda> <tx_L> "+
             "<tx_U> <Q> <R> <seed>");
      System.exit (1);
      }
   }