1 /* See the DRL-LICENSE file for this file's software license. */
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).
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
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.
22 #ifndef __SAMPLEHOLD__
23 #define __SAMPLEHOLD__
28 #define FLOW_DELETED 1
31 #define RANDOM_GRANULARITY (1000)
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)
39 /** In-table representation of a flow that has been sampled. */
40 typedef struct sampled_flow {
42 /* Flow-specific values. */
44 /** The rate of the flow in the current estimate interval. */
47 /** The total number of bytes this flow has sent during this cleaning
52 /** The total number of bytes this flow had sent during this cleaning interval
53 * as of the last rate estimate update. */
56 /** The time at which this flow was last updated. */
57 struct timeval last_update;
59 /* Identification information. */
61 /** The flow's source IP address. */
64 /** The flow's destination IP address. */
67 /** The flow's source port. */
70 /** The flow's destination port. */
73 /** The flow's protocol. This corresponds to the protocol field of the IP
77 /** Bookkeeping to keep track of the state of the flow in the table. */
83 * The structure in which flows are stored.
85 struct sampled_flow_table {
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;
91 /* Table properties. */
93 /** The maximum capacity of the table. */
96 /** The current size of the table. */
99 /** Hash function pointer. */
100 uint32_t (*hash_function)(const key_flow *key);
102 /** Pointer to the array that backs the flow table. */
103 sampled_flow *backing;
105 /** Pointer to the flow in backing with the largest rate. */
106 sampled_flow *largest;
108 /** The probability of sampling a byte. */
111 /** Threshold for keeping things around during clean (bytes). */
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;
120 /**** Table API ****/
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.
126 * Returns the new table or NULL on failure.
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);
131 * Destroys the specified table.
133 void sampled_table_destroy(sampled_flow_table table);
136 * Finds the data associated with the specified key.
138 * Returns a pointer to the sampled_flow or NULL if the key is not in the table.
140 sampled_flow *sampled_table_lookup(sampled_flow_table table, const key_flow *key);
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
148 * Returns 1 if, after the call, the flow is in the table. 0 If it is not
151 int sampled_table_sample(sampled_flow_table table, const key_flow *key);
154 * Returns the number of elements in the table.
156 uint32_t sampled_table_size(const sampled_flow_table table);
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);
163 * Updates the rate information for all flows in the table according to the
164 * specified current time and EWMA weight.
166 void sampled_table_update_flows(sampled_flow_table table, struct timeval now, double ewma_weight);
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);
171 #endif /* __SAMPLEHOLD__ */