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