drl/samplehold.h

   1 /* See the DRL-LICENSE file for this file's software license. */
   2
   3 /**
   4  * Implements the Sample and hold accounting mechanism as described in "New
   5  * Directions in Traffic Measurement and Accounting" by Cristian Estan and
   6  * George Varghese (SIGCOMM 2002).
   7  *
   8  * Basic idea:
   9  * Randomly sample packets with some probability.  For every sampled packet,
  10  * if it isn't already in our flow table, add it.  Once a flow is in the table,
  11  * EVERY packet belonging to the flow subsequently updates the table
  12  * information.
  13  *
  14  */
  15
  16 /* My notes:
  17  * Let p be the probability of samping a BYTE.
  18  * Let s be the size of a packet.
  19  * Then we approximate the probability of samping the entire packet as p * s.
  20  */
  21
  22 #ifndef __SAMPLEHOLD__
  23 #define __SAMPLEHOLD__
  24
  25 #include <inttypes.h>
  26
  27 #define FLOW_FREE 0
  28 #define FLOW_DELETED 1
  29 #define FLOW_USED 2
  30
  31 #define RANDOM_GRANULARITY (1000)
  32
  33 #define SAMPLEHOLD_PERCENTAGE (5)
  34 #define SAMPLEHOLD_OVERFACTOR (10)
  35
  36 /** In-table representation of a flow that has been sampled. */
  37 typedef struct sampled_flow {
  38
  39     /* Flow-specific values. */
  40
  41     /** The rate of the flow in the current estimate interval. */
  42     uint32_t rate;
  43
  44     /** The total number of bytes this flow has sent during this cleaning
  45      * interval.
  46      */
  47     uint32_t bytes;
  48
  49     /** The total number of bytes this flow had sent during this cleaning interval
  50      * as of the last rate estimate update. */
  51     uint32_t last_bytes;
  52
  53     /** The time at which this flow was last updated. */
  54     struct timeval last_update;
  55
  56     /* Identification information. */
  57
  58     /** The flow's source IP address. */
  59     uint32_t source_ip;
  60
  61     /** The flow's destination IP address. */
  62     uint32_t dest_ip;
  63
  64     /** The flow's source port. */
  65     uint16_t source_port;
  66
  67     /** The flow's destination port. */
  68     uint16_t dest_port;
  69
  70     /** The flow's protocol.  This corresponds to the protocol field of the IP
  71      * header. */
  72     uint8_t protocol;
  73
  74     /** Bookkeeping to keep track of the state of the flow in the table. */
  75     uint8_t state;
  76
  77 } sampled_flow;
  78
  79 /**
  80  * The structure in which flows are stored.
  81  */
  82 struct sampled_flow_table {
  83
  84     /** Pointer to the common flow information for the identity that owns this
  85      * sampled flow table.  This is updated with aggregate information. */
  86     common_accounting_t *common;
  87
  88     /* Table properties. */
  89
  90     /** The maximum capacity of the table. */
  91     uint32_t capacity;
  92
  93     /** The current size of the table. */
  94     uint32_t size;
  95
  96     /** Hash function pointer. */
  97     uint32_t (*hash_function)(const key_flow *key);
  98
  99     /** Pointer to the array that backs the flow table. */
 100     sampled_flow *backing;
 101
 102     /** Pointer to the flow in backing with the largest rate. */
 103     sampled_flow *largest;
 104
 105     /** The probability of sampling a byte. */
 106     double sample_prob;
 107
 108     /** Threshold for keeping things around during clean (bytes). */
 109     uint32_t threshold;
 110
 111 };
 112
 113 /** The type sampled_flow_table is really a pointer to a struct
 114  * sampled_flow_table. */
 115 typedef struct sampled_flow_table *sampled_flow_table;
 116
 117 /**** Table API ****/
 118
 119 /**
 120  * Creates a new table with the specified maximum byte count, percentage
 121  * of byte count to classify as an interesting flow, and an oversampling factor.
 122  *
 123  * Returns the new table or NULL on failure.
 124  */
 125 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);
 126
 127 /**
 128  * Destroys the specified table.
 129  */
 130 void sampled_table_destroy(sampled_flow_table table);
 131
 132 /**
 133  * Finds the data associated with the specified key.
 134  *
 135  * Returns a pointer to the sampled_flow or NULL if the key is not in the table.
 136  */
 137 sampled_flow *sampled_table_lookup(sampled_flow_table table, const key_flow *key);
 138
 139 /**
 140  * This is the function that should be called on every packet.  It will first
 141  * check to see if the flow is in the table.  If so, it updates the flow's
 142  * table information.  If not, it will probabilistically sample and add the
 143  * flow to the table.
 144  *
 145  * Returns 1 if, after the call, the flow is in the table.  0 If it is not
 146  * in the table.
 147  */
 148 int sampled_table_sample(sampled_flow_table table, const key_flow *key);
 149
 150 /**
 151  * Returns the number of elements in the table.
 152  */
 153 uint32_t sampled_table_size(const sampled_flow_table table);
 154
 155 /** Cleans the table by removing "small" flows and relocating the "big" ones
 156  * to their best hash locations. */
 157 int sampled_table_cleanup(sampled_flow_table table);
 158
 159 /**
 160  * Updates the rate information for all flows in the table according to the
 161  * specified current time and EWMA weight.
 162  */
 163 void sampled_table_update_flows(sampled_flow_table table, struct timeval now, double ewma_weight);
 164
 165 /** Returns the largest flow in the table or NULL if there isn't one. */
 166 sampled_flow *sampled_table_largest(sampled_flow_table table);
 167
 168 #endif  /* __SAMPLEHOLD__ */