X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=drl%2Fstandard.h;fp=drl%2Fstandard.h;h=59c45f7d8c50aa14433be633bb542a55b1973024;hb=0be9704d6b24d09ebd55beedec52758cb88c570b;hp=0000000000000000000000000000000000000000;hpb=6747e89080a8265aa73320bd9f40a0fa6e1c161e;p=distributedratelimiting.git

diff --git a/drl/standard.h b/drl/standard.h
new file mode 100644
index 0000000..59c45f7
--- /dev/null
+++ b/drl/standard.h
@@ -0,0 +1,150 @@
+/* See the DRL-LICENSE file for this file's software license. */
+
+/*
+ * Defines the standard "perfect" flow accounting table.
+ *
+ */
+
+#ifndef _STANDARD_ACCOUNTING_H_
+#define _STANDARD_ACCOUNTING_H_
+
+#include <inttypes.h>
+
+/** The number of hash buckets in the table. */
+#define FLOW_HASH_SIZE 1024
+
+/** The number of seconds after which a flow is considered to be inactive.
+ * Inactive flows will be removed from the table during the next call to the
+ * cleanup function. */
+#define FLOW_IDLE_TIME 10
+
+/** Representation of a flow in a standard table. */
+typedef struct std_flow {
+    /* Flow information. */
+
+    /** The rate of the flow in the current estimate interval. */
+    uint32_t rate;
+
+    /** The rate of the flow in the previous estimate interval. */
+    uint32_t last_rate;
+
+    /** The number of bytes this flow has sent since the last update. */
+    uint32_t bytes_since;
+
+    /** The time at which this flow was last updated. */
+    struct timeval last_update;
+
+    /** The time at which the most recent packet in this flow was received. */
+    time_t last_packet;
+
+    /* 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;
+
+    /* Table state. */
+
+    /** Pointer to the next flow in the hash list. */
+    struct std_flow *nexth;
+
+    /** Pointers to the next flow in the linked list. */
+    struct std_flow *next;
+
+    /** Pointers to the previous flow in the linked list. */
+    struct std_flow *prev;
+
+} standard_flow;
+
+/**
+ * The "table" that stores the flows.  It's constructed of two main pieces.
+ *
+ * The first is an array of hash buckets.  Flows are classified into buckets
+ * by hashing the flow's values (key flow) using the table's hash function.
+ * Flows are chained together as a list in each bucket to deal with collisions.
+ *
+ * The second is a simple doubly linked list containing every flow in the table.
+ */
+struct std_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 structures. */
+
+    /** Hash buckets - each is a list of flows. */
+    struct std_flow *flows[FLOW_HASH_SIZE];
+
+    /** The head of the linked list of flows. */
+    struct std_flow *flows_head;
+    
+    /** The tail of the linked list of flows. */
+    struct std_flow *flows_tail;
+
+    /** Function pointer to the function that will yield the hash of a
+     * key_flow.
+     */
+    uint32_t (*hash_function)(const key_flow *key);
+
+};
+
+/** The type standard_flow_table is really a pointer to a struct
+ * std_flow_table. */
+typedef struct std_flow_table *standard_flow_table;
+
+/**
+ * Creates a new table that will use the specified hash function.
+ *
+ * Returns the new table or NULL on failure.
+ */
+standard_flow_table standard_table_create(uint32_t (*hash_function)(const key_flow *key), common_accounting_t *common);
+
+/**
+ * Destroys the specified table.
+ */
+void standard_table_destroy(standard_flow_table table);
+
+/**
+ * Looks for a flow that matches the given key in the specified table.  If a
+ * matching flow is not found, this function will allocate a new flow for the
+ * key.
+ *
+ * Returns a pointer to the flow that matches the key or NULL if there is no
+ * matching flow and a new flow couldn't be allocated.
+ */
+standard_flow *standard_table_lookup(standard_flow_table table, const key_flow *key);
+
+/**
+ * Updates the state of the table given a newly acquired packet.
+ *
+ * Returns 1 if the flow is in the table.  0 otherwise (indicating that memory
+ * could not be allocated to add a new flow to the table for the given key.
+ */
+int standard_table_sample(standard_flow_table table, const key_flow *key);
+
+/**
+ * Cleans the table by removing flow entires for any flow that hasn't seen a
+ * new packet in the interval specified by FLOW_IDLE_TIME seconds.
+ */
+int standard_table_cleanup(standard_flow_table table);
+
+/**
+ * Updates the rate information for all flows in the table according to the
+ * specified current time and EWMA weight.
+ */
+void standard_table_update_flows(standard_flow_table table, struct timeval now, double ewma_weight);
+
+#endif  /* _STANDARD_ACCOUNTING_H_ */