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 // FIXME: In reality, you probably don't want this higher than 5
  34 //#define SAMPLEHOLD_PERCENTAGE (5)
  35 #define SAMPLEHOLD_PERCENTAGE (10)
  36 #define SAMPLEHOLD_OVERFACTOR (10)
  37 #define SAMPLEHOLD_BONUS_FACTOR (1.05)
  38
  39 /** In-table representation of a flow that has been sampled. */
  40 typedef struct sampled_flow {
  41
  42     /* Flow-specific values. */
  43
  44     /** The rate of the flow in the current estimate interval. */
  45     uint32_t rate;
  46
  47     /** The total number of bytes this flow has sent during this cleaning
  48      * interval.
  49      */
  50     uint32_t bytes;
  51
  52     /** The total number of bytes this flow had sent during this cleaning interval
  53      * as of the last rate estimate update. */
  54     uint32_t last_bytes;
  55
  56     /** The time at which this flow was last updated. */
  57     struct timeval last_update;
  58
  59     /* Identification information. */
  60
  61     /** The flow's source IP address. */
  62     uint32_t source_ip;
  63
  64     /** The flow's destination IP address. */
  65     uint32_t dest_ip;
  66
  67     /** The flow's source port. */
  68     uint16_t source_port;
  69
  70     /** The flow's destination port. */
  71     uint16_t dest_port;
  72
  73     /** The flow's protocol.  This corresponds to the protocol field of the IP
  74      * header. */
  75     uint8_t protocol;
  76
  77     /** Bookkeeping to keep track of the state of the flow in the table. */
  78     uint8_t state;
  79
  80 } sampled_flow;
  81
  82 /**
  83  * The structure in which flows are stored.
  84  */
  85 struct sampled_flow_table {
  86
  87     /** Pointer to the common flow information for the identity that owns this
  88      * sampled flow table.  This is updated with aggregate information. */
  89     common_accounting_t *common;
  90
  91     /* Table properties. */
  92
  93     /** The maximum capacity of the table. */
  94     uint32_t capacity;
  95
  96     /** The current size of the table. */
  97     uint32_t size;
  98
  99     /** Hash function pointer. */
 100     uint32_t (*hash_function)(const key_flow *key);
 101
 102     /** Pointer to the array that backs the flow table. */
 103     sampled_flow *backing;
 104
 105     /** Pointer to the flow in backing with the largest rate. */
 106     sampled_flow *largest;
 107
 108     /** The probability of sampling a byte. */
 109     double sample_prob;
 110
 111     /** Threshold for keeping things around during clean (bytes). */
 112     uint32_t threshold;
 113
 114 };
 115
 116 /** The type sampled_flow_table is really a pointer to a struct
 117  * sampled_flow_table. */
 118 typedef struct sampled_flow_table *sampled_flow_table;
 119
 120 /**** Table API ****/
 121
 122 /**
 123  * Creates a new table with the specified maximum byte count, percentage
 124  * of byte count to classify as an interesting flow, and an oversampling factor.
 125  *
 126  * Returns the new table or NULL on failure.
 127  */
 128 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);
 129
 130 /**
 131  * Destroys the specified table.
 132  */
 133 void sampled_table_destroy(sampled_flow_table table);
 134
 135 /**
 136  * Finds the data associated with the specified key.
 137  *
 138  * Returns a pointer to the sampled_flow or NULL if the key is not in the table.
 139  */
 140 sampled_flow *sampled_table_lookup(sampled_flow_table table, const key_flow *key);
 141
 142 /**
 143  * This is the function that should be called on every packet.  It will first
 144  * check to see if the flow is in the table.  If so, it updates the flow's
 145  * table information.  If not, it will probabilistically sample and add the
 146  * flow to the table.
 147  *
 148  * Returns 1 if, after the call, the flow is in the table.  0 If it is not
 149  * in the table.
 150  */
 151 int sampled_table_sample(sampled_flow_table table, const key_flow *key);
 152
 153 /**
 154  * Returns the number of elements in the table.
 155  */
 156 uint32_t sampled_table_size(const sampled_flow_table table);
 157
 158 /** Cleans the table by removing "small" flows and relocating the "big" ones
 159  * to their best hash locations. */
 160 int sampled_table_cleanup(sampled_flow_table table);
 161
 162 /**
 163  * Updates the rate information for all flows in the table according to the
 164  * specified current time and EWMA weight.
 165  */
 166 void sampled_table_update_flows(sampled_flow_table table, struct timeval now, double ewma_weight);
 167
 168 /** Returns the largest flow in the table or NULL if there isn't one. */
 169 sampled_flow *sampled_table_largest(sampled_flow_table table);
 170
 171 #endif  /* __SAMPLEHOLD__ */