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 /** In-table representation of a flow that has been sampled. */
34 typedef struct sampled_flow {
36 /* Flow-specific values. */
38 /** The rate of the flow in the current estimate interval. */
41 /** The total number of bytes this flow has sent during this cleaning
46 /** The total number of bytes this flow had sent during this cleaning interval
47 * as of the last rate estimate update. */
50 /** The time at which this flow was last updated. */
51 struct timeval last_update;
53 /* Identification information. */
55 /** The flow's source IP address. */
58 /** The flow's destination IP address. */
61 /** The flow's source port. */
64 /** The flow's destination port. */
67 /** The flow's protocol. This corresponds to the protocol field of the IP
71 /** Bookkeeping to keep track of the state of the flow in the table. */
77 * The structure in which flows are stored.
79 struct sampled_flow_table {
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;
85 /* Table properties. */
87 /** The maximum capacity of the table. */
90 /** The current size of the table. */
93 /** Hash function pointer. */
94 uint32_t (*hash_function)(const key_flow *key);
96 /** Pointer to the array that backs the flow table. */
97 sampled_flow *backing;
99 /** Pointer to the flow in backing with the largest rate. */
100 sampled_flow *largest;
102 /** The probability of sampling a byte. */
105 /** Threshold for keeping things around during clean (bytes). */
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;
114 /**** Table API ****/
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.
120 * Returns the new table or NULL on failure.
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);
125 * Destroys the specified table.
127 void sampled_table_destroy(sampled_flow_table table);
130 * Finds the data associated with the specified key.
132 * Returns a pointer to the sampled_flow or NULL if the key is not in the table.
134 sampled_flow *sampled_table_lookup(sampled_flow_table table, const key_flow *key);
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
142 * Returns 1 if, after the call, the flow is in the table. 0 If it is not
145 int sampled_table_sample(sampled_flow_table table, const key_flow *key);
148 * Returns the number of elements in the table.
150 uint32_t sampled_table_size(const sampled_flow_table table);
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);
157 * Updates the rate information for all flows in the table according to the
158 * specified current time and EWMA weight.
160 void sampled_table_update_flows(sampled_flow_table table, struct timeval now, double ewma_weight);
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);
165 #endif /* __SAMPLEHOLD__ */