/* See the DRL-LICENSE file for this file's software license. */

/**
 * Implements the Sample and hold accounting mechanism as described in "New
 * Directions in Traffic Measurement and Accounting" by Cristian Estan and
 * George Varghese (SIGCOMM 2002).
 *
 * Basic idea:
 * Randomly sample packets with some probability.  For every sampled packet,
 * if it isn't already in our flow table, add it.  Once a flow is in the table,
 * EVERY packet belonging to the flow subsequently updates the table
 * information.
 *
 */

/* My notes:
 * Let p be the probability of samping a BYTE.
 * Let s be the size of a packet.
 * Then we approximate the probability of samping the entire packet as p * s.
 */

#ifndef __SAMPLEHOLD__
#define __SAMPLEHOLD__

#include <inttypes.h>

#define FLOW_FREE 0
#define FLOW_DELETED 1
#define FLOW_USED 2

#define RANDOM_GRANULARITY (1000)

/* For simple S&H testing. */
#define SAMPLEHOLD_PERCENTAGE (5)
#define SAMPLEHOLD_OVERFACTOR (1.25)

//#define SAMPLEHOLD_PERCENTAGE (5)
//#define SAMPLEHOLD_OVERFACTOR (10)
#define SAMPLEHOLD_BONUS_FACTOR (1.05)

/** In-table representation of a flow that has been sampled. */
typedef struct sampled_flow {

    /* Flow-specific values. */

    /** The rate of the flow in the current estimate interval. */
    uint32_t rate;

    /** The total number of bytes this flow has sent during this cleaning
     * interval.
     */
    uint32_t bytes;
    
    /** The total number of bytes this flow had sent during this cleaning interval
     * as of the last rate estimate update. */
    uint32_t last_bytes;

    /** The time at which this flow was last updated. */
    struct timeval last_update;
    
    /* Identification information. */

    /** The flow's source IP address. */
    uint32_t source_ip;

    /** The flow's destination IP address. */
    uint32_t dest_ip;

    /** The flow's source port. */
    uint16_t source_port;

    /** The flow's destination port. */
    uint16_t dest_port;

    /** The flow's protocol.  This corresponds to the protocol field of the IP
     * header. */
    uint8_t protocol;

    /** Bookkeeping to keep track of the state of the flow in the table. */
    uint8_t state;

} sampled_flow;

/**
 * The structure in which flows are stored.
 */
struct sampled_flow_table {

    /** Pointer to the common flow information for the identity that owns this
     * sampled flow table.  This is updated with aggregate information. */
    common_accounting_t *common;

    /* Table properties. */

    /** The maximum capacity of the table. */
    uint32_t capacity;

    /** The current size of the table. */
    uint32_t size;

    /** Hash function pointer. */
    uint32_t (*hash_function)(const key_flow *key);

    /** Pointer to the array that backs the flow table. */
    sampled_flow *backing;

    /** Pointer to the flow in backing with the largest rate. */
    sampled_flow *largest;

    /** The probability of sampling a byte. */
    double sample_prob;

    /** Threshold for keeping things around during clean (bytes). */
    uint32_t threshold;

};

/** The type sampled_flow_table is really a pointer to a struct
 * sampled_flow_table. */
typedef struct sampled_flow_table *sampled_flow_table;

/**** Table API ****/

/** 
 * Creates a new table with the specified maximum byte count, percentage
 * of byte count to classify as an interesting flow, and an oversampling factor.
 *
 * Returns the new table or NULL on failure.
 */
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);

/**
 * Destroys the specified table.
 */
void sampled_table_destroy(sampled_flow_table table);

/**
 * Finds the data associated with the specified key.
 *
 * Returns a pointer to the sampled_flow or NULL if the key is not in the table.
 */
sampled_flow *sampled_table_lookup(sampled_flow_table table, const key_flow *key);

/**
 * This is the function that should be called on every packet.  It will first
 * check to see if the flow is in the table.  If so, it updates the flow's
 * table information.  If not, it will probabilistically sample and add the
 * flow to the table.
 *
 * Returns 1 if, after the call, the flow is in the table.  0 If it is not
 * in the table.
 */
int sampled_table_sample(sampled_flow_table table, const key_flow *key);

/**
 * Returns the number of elements in the table.
 */
uint32_t sampled_table_size(const sampled_flow_table table);

/** Cleans the table by removing "small" flows and relocating the "big" ones
 * to their best hash locations. */
int sampled_table_cleanup(sampled_flow_table table);

/**
 * Updates the rate information for all flows in the table according to the
 * specified current time and EWMA weight.
 */
void sampled_table_update_flows(sampled_flow_table table, struct timeval now, double ewma_weight);

/** Returns the largest flow in the table or NULL if there isn't one. */
sampled_flow *sampled_table_largest(sampled_flow_table table);

#endif  /* __SAMPLEHOLD__ */