commented files and added some analysis

dairui777 · Dec 31, 2015 · 77ae42c · 77ae42c
1 parent dae7609
commit 77ae42c
Show file tree

Hide file tree

Showing 21 changed files with 120 additions and 16 deletions.
diff --git a/Analysis/400 Flows error for different tablesizes 1.png b/Analysis/400 Flows error for different tablesizes 1.png
diff --git a/Analysis/400 Flows error for different tablesizes 2.png b/Analysis/400 Flows error for different tablesizes 2.png
diff --git a/Analysis/500 Flows Basic Dleft.xlsx b/Analysis/500 Flows Basic Dleft.xlsx
diff --git a/Analysis/500 Flows Error for different tablesizes 1.png b/Analysis/500 Flows Error for different tablesizes 1.png
diff --git a/Analysis/500 Flows Error for different tablesizes 2.png b/Analysis/500 Flows Error for different tablesizes 2.png
diff --git a/Analysis/Heuristic Comparison with Normal 1.png b/Analysis/Heuristic Comparison with Normal 1.png
diff --git a/Analysis/Heuristic Comparison with Normal 2.png b/Analysis/Heuristic Comparison with Normal 2.png
diff --git a/Analysis/Workspace.xlsx b/Analysis/Workspace.xlsx
diff --git a/code/AssymetricHashTableSimulation.java b/code/AssymetricHashTableSimulation.java
@@ -1,5 +1,15 @@
 import java.util.*;
 
+/* hash table simulation to track the unique flows experiencing loss
+	using the D-Left hashing procedure where each flow id is hashed exactly
+	d times to generate d locations where the flow and its loss might be
+	stored
+
+	runs experiments on a certain number of flows and for a given table size
+	across multiple thresholds and averages out the results across a preset
+	number of trials and reports the results in a csv format
+*/
+
 public class AssymetricHashTableSimulation{
 	public static void main(String[] args){
 		final int numberOfTrials = 1000;
@@ -63,7 +73,7 @@ public static void main(String[] args){
 					double cumErrorMargin = 0;
 					int errorInBinaryAnswer = 0;
 					for (int i = 0; i < numberOfTrials; i++){
-						Collections.shuffle(packets);
+						//Collections.shuffle(packets); - don't shuffle for worst case scenario of all big losers being at the end
 						FlowWithCount.reset(buckets);
 						droppedPacketInfoCount = 0;
 						totalNumberOfPackets = 0; // needed for the denominator to compute the threshold for loss count

diff --git a/code/CountMinLossyFlowIdentifier.java b/code/CountMinLossyFlowIdentifier.java
@@ -1,5 +1,12 @@
 import java.util.*;
 
+ /* incomplete code and hasn't been used */
+
+/* Data Structure that identifies the big losers
+   by maintaining a count-min sketch and a heap that
+   is updated for every incoming packet by checking
+   if the flow it belongs to has exceeded the threshold*/
+
 public class CountMinLossyFlowIdentifier{
 	public TreeMap<Long, Integer> heavyhitters; 
 	public final Comparator lossyFlowComparator;

diff --git a/code/EvictingHashTableSimulation.java b/code/EvictingHashTableSimulation.java
@@ -1,5 +1,12 @@
 import java.util.*;
 
+/* eviction heuristic (compare the incoming flow's loss against that of
+	the flow at the last of the d locations) added to the standard 
+	hash table simulation to track the unique flows experiencing loss
+	using the D-Left hashing procedure where each flow id is hashed exactly
+	d times to generate d locations where the flow and its loss might be
+	stored*/
+
 public class EvictingHashTableSimulation{
 	public static void main(String[] args){
 		int numberOfTrials = Integer.parseInt(args[0]);
@@ -97,8 +104,8 @@ public static void main(String[] args){
 				if (k == D) {
 					if (countMinSketch.estimateLossCount(buckets[index].flowid) < countMinSketch.estimateLossCount(packets.get(j))){
 						packetsInfoDroppedAtFlow[packets.get(j) - 1] = 0;
-						packetsInfoDroppedAtFlow[buckets[index].flowid - 1] = buckets[index].count;
-						droppedPacketInfoCount = droppedPacketInfoCount + buckets[index].count - (int) countMinSketch.estimateLossCount(packets.get(j));
+						packetsInfoDroppedAtFlow[buckets[index].flowid - 1] = (int) buckets[index].count;
+						droppedPacketInfoCount = droppedPacketInfoCount + (int) buckets[index].count - (int) countMinSketch.estimateLossCount(packets.get(j));
 						buckets[index].flowid = packets.get(j);
 						buckets[index].count = (int) countMinSketch.estimateLossCount(packets.get(j));
 					}

diff --git a/code/EvictingMinFlowIdHashTableSimulation.java b/code/EvictingMinFlowIdHashTableSimulation.java
@@ -1,5 +1,14 @@
 import java.util.*;
 
+/* eviction heuristic (compare the incoming flow's loss against that of
+	the flow  with minimum loss amongst flows at all d locations) 
+	added to the standard hash table simulation to track 
+	the unique flows experiencing loss using the D-Left hashing procedure */
+
+/* version of hash table simulation that uses the eviction heuristic
+ but only stores the flow id in the hash table
+ and uses the count-min sketch to estimate the loss count*/
+
 public class EvictingMinFlowIdHashTableSimulation{
 	public static void main(String[] args){
 		int numberOfTrials = Integer.parseInt(args[0]);

diff --git a/code/EvictingMinHashTableSimulation.java b/code/EvictingMinHashTableSimulation.java
@@ -1,5 +1,13 @@
 import java.util.*;
 
+/* version of hash table simulation that stores both flow id and count
+ in the hash table, but uses the count-min sketch to estimate the loss 
+ for a flow that is not yet in the hash table and just came in; this is
+ used to perform the eviction heuristic */
+
+ /* NOTE: Accuracy isn't better than just maintaining the flow id in
+ the hash table - simulations are in Smart Eviction Simulation file*/
+
 public class EvictingMinHashTableSimulation{
 	public static void main(String[] args){
 		int numberOfTrials = Integer.parseInt(args[0]);
@@ -75,7 +83,7 @@ public static void main(String[] args){
 				// keep track of which of the d locations has the minimum lost packet count
 				// use this location to place the incoming flow if there is a collision
 				int minIndex = 0;
-				int minValue = -1;
+				long minValue = -1;
 
 				for (k = 0; k < D; k++){
 					index = ((hashA[k]*packets.get(j) + hashB[k]) % P) % (tableSize/D) + (k*tableSize/D);
@@ -103,14 +111,13 @@ public static void main(String[] args){
 				// none of the D locations were free - hash collission
 				// decide if one of them is worth evicting
 
-				// TODO: figure out if the incoming flow has a higher loss than one of the existing flows in the table
-				// find a way of tracking the information of the incoming flow because it isnt the hash table
-				// so we don't have information on what its loss count is nd the very first time it comes in, loss is 0
+				// figure out if the incoming flow has a higher loss than the flow that has the minimum loss amongst
+				// the d existing flows in the table
 				if (k == D) {
 					if (countMinSketch.estimateLossCount(buckets[minIndex].flowid) < countMinSketch.estimateLossCount(packets.get(j))){
 						packetsInfoDroppedAtFlow[packets.get(j) - 1] = 0;
-						packetsInfoDroppedAtFlow[buckets[minIndex].flowid - 1] = buckets[minIndex].count;
-						droppedPacketInfoCount = droppedPacketInfoCount + buckets[minIndex].count - (int) countMinSketch.estimateLossCount(packets.get(j));
+						packetsInfoDroppedAtFlow[buckets[minIndex].flowid - 1] = (int) buckets[minIndex].count;
+						droppedPacketInfoCount = droppedPacketInfoCount + (int) buckets[minIndex].count - (int) countMinSketch.estimateLossCount(packets.get(j));
 						buckets[minIndex].flowid = packets.get(j);
 						buckets[minIndex].count = (int) countMinSketch.estimateLossCount(packets.get(j));
 					}

diff --git a/code/FlowWithCount.java b/code/FlowWithCount.java
@@ -1,8 +1,11 @@
+/*Data Structure used as a building block for the hash table
+ that tracks the lossy packets*/
+
 public class FlowWithCount{
-		int count;
+		long count;
 		int flowid;
 
-		public FlowWithCount(int flowid ,int count){
+		public FlowWithCount(int flowid ,long count){
 			this.count = count;
 			this.flowid = flowid;
 		}

diff --git a/code/HashTableSimulation.java b/code/HashTableSimulation.java
@@ -1,5 +1,10 @@
 import java.util.*;
 
+/* hash table simulation to track the unique flows experiencing loss
+	using the standard technique where each flow id is hashed exactly
+	once to generate one location where the flow and its loss are
+	stored*/
+
 public class HashTableSimulation{
 	public static void main(String[] args){
 		int numberOfTrials = Integer.parseInt(args[0]);
@@ -25,6 +30,7 @@ public static void main(String[] args){
 			buckets[j] = new FlowWithCount(0, 0);
 		}
 
+		// create a set of lost packets which consists of i lost packets of flow i
 		List<Integer> packets = new ArrayList<>();
 		// add i packets of  flowid i
 		for (int i = 1; i <= numberOfFlows; i++)

diff --git a/code/LossInducer.java b/code/LossInducer.java
@@ -1,5 +1,8 @@
 import java.util.*;
 
+/* 	class that facilitates loss creation on a stream of packets
+	by choosing flow(s) to be loss and returning all packets but
+	those belonging to the flow*/
 public class LossInducer{
 	private int numberOfLossyFlows;
 	private int granularity;

diff --git a/code/LossyFlowIdentifier.java b/code/LossyFlowIdentifier.java
@@ -1,5 +1,12 @@
 import java.util.*;
 
+/* high level procedure that uses packet info from a csv file, parses it,
+   induces loss on it, and produces a sketch for the lost packet on which
+   the big loser identification process is performed 
+
+   initially written for the sketches to all be reversible so that the 
+   reversibility procedure would identify the lossy buckets - unused 
+   code in the context of the hash table approach*/
 public class LossyFlowIdentifier{
 	public static PriorityQueue<LossyFlow> HeapOfLossyFlows; 
 	private class BucketMatrixIndex{

diff --git a/code/Packet.java b/code/Packet.java
@@ -1,5 +1,7 @@
 import java.util.*;
 
+/* abstraction for Packets in a network that helps retrieve 
+   the key fields from the packet*/
 public class Packet{
 	private long srcip;
 	private long dstip;

diff --git a/code/Sketch.java b/code/Sketch.java
@@ -1,5 +1,15 @@
 import java.*;
 
+/* count min sketch that is used to maintain a summary data structure
+   to estimate the frequency of occurence of certain items in a data
+   stream
+
+   used in this context to count the number of packets per flow that
+   have been lost
+
+	initially used to simulate reversible sketches too - hence, there
+	is some commented out code that belongs to that technique
+*/
 public class Sketch{
 	private int size;							// K or the max number of buckets in a hash table
 	private int numberOfHashFunctions; 		 	// H

diff --git a/code/SmartEvictionHashTableWithCountSimulation.java b/code/SmartEvictionHashTableWithCountSimulation.java
@@ -1,5 +1,24 @@
 import java.util.*;
 
+
+/* eviction heuristic (compare the incoming flow's loss against that of
+	the flow  with minimum loss amongst flows at all d locations) 
+	added to the standard hash table simulation to track 
+	the unique flows experiencing loss using the D-Left hashing procedure */
+
+ /* NOTE: Accuracy isn't better than just maintaining the flow id in
+ the hash table - simulations are in Smart Eviction Simulation file*/
+
+ /* version of hash table simulation that stores both flow id and count
+ 	in the hash table, but uses the count-min sketch to estimate the loss 
+ 	for a flow that is not yet in the hash table and just came in; this is
+ 	used to perform the eviction heuristic
+
+ 	runs experiments on a certain number of flows and for a given table size
+	across multiple thresholds and averages out the results across a preset
+	number of trials and reports the results in a csv format
+*/
+
 public class SmartEvictionHashTableWithCountSimulation{
 	public static void main(String[] args){
 		final int numberOfTrials = 1000;
@@ -87,7 +106,7 @@ public static void main(String[] args){
 							// keep track of which of the d locations has the minimum lost packet count
 							// use this location to place the incoming flow if there is a collision
 							int minIndex = 0;
-							int minValue = -1;
+							long minValue = -1;
 
 							for (k = 0; k < D; k++){
 								int index = ((hashA[k]*packets.get(j) + hashB[k]) % P) % (tableSize[tableSize_index]/D) + (k*tableSize[tableSize_index]/D);
@@ -118,8 +137,8 @@ public static void main(String[] args){
 							if (k == D) {
 								if (countMinSketch.estimateLossCount(buckets[minIndex].flowid) < countMinSketch.estimateLossCount(packets.get(j))){
 									packetsInfoDroppedAtFlow[packets.get(j) - 1] = 0;
-									packetsInfoDroppedAtFlow[buckets[minIndex].flowid - 1] = buckets[minIndex].count;
-									droppedPacketInfoCount = droppedPacketInfoCount + buckets[minIndex].count - (int) countMinSketch.estimateLossCount(packets.get(j));
+									packetsInfoDroppedAtFlow[buckets[minIndex].flowid - 1] = (int) buckets[minIndex].count;
+									droppedPacketInfoCount = droppedPacketInfoCount + (int) buckets[minIndex].count - (int) countMinSketch.estimateLossCount(packets.get(j));
 									buckets[minIndex].flowid = packets.get(j);
 									buckets[minIndex].count = (int) countMinSketch.estimateLossCount(packets.get(j));
 								}

diff --git a/code/SmartEvictionHashTableWithoutCountSimulation.java b/code/SmartEvictionHashTableWithoutCountSimulation.java
@@ -1,5 +1,19 @@
 import java.util.*;
 
+/* eviction heuristic (compare the incoming flow's loss against that of
+	the flow  with minimum loss amongst flows at all d locations) 
+	added to the standard hash table simulation to track 
+	the unique flows experiencing loss using the D-Left hashing procedure */
+
+/* version of hash table simulation that uses the eviction heuristic
+ but only stores the flow id in the hash table
+ and uses the count-min sketch to estimate the loss count
+
+ 	runs experiments on a certain number of flows and for a given table size
+	across multiple thresholds and averages out the results across a preset
+	number of trials and reports the results in a csv format
+*/
+
 public class SmartEvictionHashTableWithoutCountSimulation{
 	public static void main(String[] args){
 		final int numberOfTrials = 1000;
@@ -30,7 +44,7 @@ public static void main(String[] args){
 
 
 					/*Sketch that maintains the loss of each flow* --- CHANGE THIS SIZE TOO */
-					Sketch countMinSketch = new Sketch(100, 3, numberOfFlows[flowSize_index]);
+					Sketch countMinSketch = new Sketch((int) tableSize[tableSize_index]/3, 3, numberOfFlows[flowSize_index]);
 
 					// create a set of lost packets which consists of i lost packets of flow i
 					ArrayList<Integer> packets = new ArrayList<Integer>();
@@ -61,7 +75,7 @@ public static void main(String[] args){
 					double cumErrorMargin = 0;
 					int errorInBinaryAnswer = 0;
 					for (int i = 0; i < numberOfTrials; i++){
-						Collections.shuffle(packets);
+						//Collections.shuffle(packets);
 						countMinSketch.reset();						
 
 						//FlowWithCount.reset(buckets);