Importing all of DRL, including ulogd and all of its files.

[distributedratelimiting.git] / drl / samplehold.h

diff --git a/drl/samplehold.h b/drl/samplehold.h
new file mode 100644 (file)
index 0000000..5a554ef
--- /dev/null
+++ b/drl/samplehold.h
@@ -0,0 +1,165 @@
+/* See the DRL-LICENSE file for this file's software license. */
+
+/**
+ * Implements the Sample and hold accounting mechanism as described in "New
+ * Directions in Traffic Measurement and Accounting" by Cristian Estan and
+ * George Varghese (SIGCOMM 2002).
+ *
+ * Basic idea:
+ * Randomly sample packets with some probability.  For every sampled packet,
+ * if it isn't already in our flow table, add it.  Once a flow is in the table,
+ * EVERY packet belonging to the flow subsequently updates the table
+ * information.
+ *
+ */
+
+/* My notes:
+ * Let p be the probability of samping a BYTE.
+ * Let s be the size of a packet.
+ * Then we approximate the probability of samping the entire packet as p * s.
+ */
+
+#ifndef __SAMPLEHOLD__
+#define __SAMPLEHOLD__
+
+#include <inttypes.h>
+
+#define FLOW_FREE 0
+#define FLOW_DELETED 1
+#define FLOW_USED 2
+
+#define RANDOM_GRANULARITY 1000
+
+/** In-table representation of a flow that has been sampled. */
+typedef struct sampled_flow {
+
+    /* Flow-specific values. */
+
+    /** The rate of the flow in the current estimate interval. */
+    uint32_t rate;
+
+    /** The total number of bytes this flow has sent during this cleaning
+     * interval.
+     */
+    uint32_t bytes;
+    
+    /** The total number of bytes this flow had sent during this cleaning interval
+     * as of the last rate estimate update. */
+    uint32_t last_bytes;
+
+    /** The time at which this flow was last updated. */
+    struct timeval last_update;
+    
+    /* Identification information. */
+
+    /** The flow's source IP address. */
+    uint32_t source_ip;
+
+    /** The flow's destination IP address. */
+    uint32_t dest_ip;
+
+    /** The flow's source port. */
+    uint16_t source_port;
+
+    /** The flow's destination port. */
+    uint16_t dest_port;
+
+    /** The flow's protocol.  This corresponds to the protocol field of the IP
+     * header. */
+    uint8_t protocol;
+
+    /** Bookkeeping to keep track of the state of the flow in the table. */
+    uint8_t state;
+
+} sampled_flow;
+
+/**
+ * The structure in which flows are stored.
+ */
+struct sampled_flow_table {
+
+    /** Pointer to the common flow information for the identity that owns this
+     * sampled flow table.  This is updated with aggregate information. */
+    common_accounting_t *common;
+
+    /* Table properties. */
+
+    /** The maximum capacity of the table. */
+    uint32_t capacity;
+
+    /** The current size of the table. */
+    uint32_t size;
+
+    /** Hash function pointer. */
+    uint32_t (*hash_function)(const key_flow *key);
+
+    /** Pointer to the array that backs the flow table. */
+    sampled_flow *backing;
+
+    /** Pointer to the flow in backing with the largest rate. */
+    sampled_flow *largest;
+
+    /** The probability of sampling a byte. */
+    double sample_prob;
+
+    /** Threshold for keeping things around during clean (bytes). */
+    uint32_t threshold;
+
+};
+
+/** The type sampled_flow_table is really a pointer to a struct
+ * sampled_flow_table. */
+typedef struct sampled_flow_table *sampled_flow_table;
+
+/**** Table API ****/
+
+/** 
+ * Creates a new table with the specified maximum byte count, percentage
+ * of byte count to classify as an interesting flow, and an oversampling factor.
+ *
+ * Returns the new table or NULL on failure.
+ */
+sampled_flow_table sampled_table_create(uint32_t (*hash_function)(const key_flow *key), uint32_t max_bytes, uint32_t flow_percentage, uint32_t oversampling_factor, common_accounting_t *common);
+
+/**
+ * Destroys the specified table.
+ */
+void sampled_table_destroy(sampled_flow_table table);
+
+/**
+ * Finds the data associated with the specified key.
+ *
+ * Returns a pointer to the sampled_flow or NULL if the key is not in the table.
+ */
+sampled_flow *sampled_table_lookup(sampled_flow_table table, const key_flow *key);
+
+/**
+ * This is the function that should be called on every packet.  It will first
+ * check to see if the flow is in the table.  If so, it updates the flow's
+ * table information.  If not, it will probabilistically sample and add the
+ * flow to the table.
+ *
+ * Returns 1 if, after the call, the flow is in the table.  0 If it is not
+ * in the table.
+ */
+int sampled_table_sample(sampled_flow_table table, const key_flow *key);
+
+/**
+ * Returns the number of elements in the table.
+ */
+uint32_t sampled_table_size(const sampled_flow_table table);
+
+/** Cleans the table by removing "small" flows and relocating the "big" ones
+ * to their best hash locations. */
+int sampled_table_cleanup(sampled_flow_table table);
+
+/**
+ * Updates the rate information for all flows in the table according to the
+ * specified current time and EWMA weight.
+ */
+void sampled_table_update_flows(sampled_flow_table table, struct timeval now, double ewma_weight);
+
+/** Returns the largest flow in the table or NULL if there isn't one. */
+sampled_flow *sampled_table_largest(sampled_flow_table table);
+
+#endif  /* __SAMPLEHOLD__ */