/* * CORR An implementation of the FlowMate, a protocol for partitioning * flows emerging from a busy sever and sharing bottlenecks. * * Definitions for the FlowMate module * * Version: @(#)corr.h 1.0 08/20/03 * * Authors: Ossama Younis, * * This program is free software; you can redistribute it and/or * modify it. */ #ifndef CORR_H #define CORR_H #define MAX_NUM_FLOWS 1000 // maximum number of flows to be clustered #define MAX_NUM_SAMPLES 300 // maximum number of samples per flow #define CORR_SUCCESS 1 // successful correlation state #define CORR_FAIL -1 // failed correlation state #define N_HASH_BITS 8 // number of bits in destination address // used in hashing #define HASH_TABLE_SIZE 256 // size of the flows hash table // based on destination addresses #define CROSS_CORRELATION 1 // to indicate cross correlation calculation #define AUTO_CORRELATION 2 // to indicate auto correlation calculation #define TRUE 1 #define FALSE 0 #define NORMAL_TCP 0 // correlation mode: no correlation #define FORWARD_DELAY 1 // correlation mode: use forward delays #define RTT 2 // correlation mode: use RTT #define MEAN_DEP 100 // mean departure rate for probes in msec #define MIN_THRESH 10 // min. # samples/flow to be considered // for correlation tests /* Methods used to arbitrate among ties, i.e., if a flow is successfully clustered with more than one group representative. One option is to cluster the flow with the representative that gives the highest cross coefficient with it. The other option is to simply merge the groups. */ #define HIGHEST_CORR 1 #define JOIN_METHOD 2 #include /***************************************************************** * general math function * to avoid linking the kernel with math library /usr/lib/libm.so *****************************************************************/ int floor_(double x); double fabs_(double x); double log_(double x); double sqrt_(double x); double uniform(double *seed); double expon(double *dseed, double xm); /******************************************************************* * sampleset structure used in calculating correlation coefficients * reference: Dan Rubenstein's code *******************************************************************/ typedef struct samplesettype { double sample_total; double sample_square_total; int num_samples; } sampleset; // sampleset methods void SS_Reset(sampleset *ss); // clear all samples void SS_init(sampleset *ss); // initialize sample set int SS_add(sampleset *ss, double sample); // return # samples received so far double SS_mean(sampleset ss); // compute the mean of the sample set double SS_meansquare(sampleset ss); // compute the mean square of the sample set double SS_variance(sampleset ss); // compute the variance of the sample set /* Correlation Coeff for pairwise comparisons: X_i * Y_i. joinset holds x_i * y_i entries as its samples */ double PairwiseCorrCoeff(sampleset joinset, sampleset s1, sampleset s2); /******************************************************************* * Computing Correlation Coefficients * reference: Dan Rubenstein's code (slightly modified by O. Younis) *******************************************************************/ typedef struct CorrelationCoeff { sampleset s1; sampleset s2; sampleset joinset; unsigned long fid1, fid2; double coeffVal; double autoSeed; struct CorrelationCoeff *next; } CorrelationCoeff; void CorrCoeff_init(CorrelationCoeff *cc, unsigned long f1, unsigned long f2); void CorrCoeff_destroy(CorrelationCoeff *cc); void CorrCoeff_Reset(CorrelationCoeff *cc); int CorrCoeff_add(CorrelationCoeff *cc, double sample1, double sample2); int CorrCoeff_CCReady(CorrelationCoeff *cc); double CorrCoeff_CC(CorrelationCoeff *cc); int NumSamples(CorrelationCoeff *cc); /******************************************************************* * Correlation information list, to be kept with each flow *******************************************************************/ typedef struct CorrSet { CorrelationCoeff *crossCoeff; CorrelationCoeff *autoCoeff; double sumDiff; // sum of difference between cross correlated samples int nSamples; // number of samples used to compute the average distance struct CorrSet *next; } CorrSet; void CorrSet_init(CorrSet *cs); void CorrSet_destroy(CorrSet *cs); typedef struct CCList { CorrSet *head, *tail; int nItems; } CCList; void CCList_init(CCList * ccl); void CCList_add(CCList * ccl, CorrSet *cor); CorrSet * CCList_find(CCList * ccl, unsigned long f1, unsigned long f2); CorrSet * CCList_getHead(CCList * ccl) ; int CCList_getNumItems(CCList * ccl); void CCList_destroy(CCList * ccl); /************************************************************* * Group Info *************************************************************/ typedef struct GroupNode { int gid; // group ID int nFlows; // number of flows for that group unsigned long *flowsList; // list of grouped flow ID's unsigned long rep_fid; // representative flow ID unsigned long rep_dst; // representative flow destination address struct GroupNode *next; // next group node } GroupNode; void GN_init(GroupNode *gn, int g, unsigned long f, unsigned long d); void GN_addFlow(GroupNode *gn, unsigned long fid); void GN_removeFlow(GroupNode *gn, unsigned long fid); int GN_isMember(GroupNode *gn, unsigned long fid); void GN_destroy(GroupNode *gn); /************************************************************** * Group List **************************************************************/ typedef struct GroupList { GroupNode *head; // head of group list int nGroups; // number of groups unsigned int max_gid; // used for assigning new group IDs } GroupList; void GL_init(GroupList *gl); void GL_addGroup(GroupList *gl, GroupNode *gn); GroupNode *GL_findGroup(GroupList *gl, unsigned long fid); void GL_deleteAllGroups(GroupList *gl); int GL_sameGroup(GroupList *gl, unsigned long fid1, unsigned long fid2); int GL_new_gid(GroupList *gl); GroupNode * GL_joinGroups(GroupList *gl, GroupNode *g1, GroupNode*g2); void GL_listGroups(GroupList *gl); void GL_destroy(GroupList *gl); /*************************************************************** * Sample Information ***************************************************************/ typedef struct SampleInfo /* Records the send time of the packet and receive time of the ack for a flow during the correlation window */ { unsigned long fid; unsigned long recv_time; unsigned long send_time; unsigned long rtt; int cancelled; } SampleInfo; void SI_init(SampleInfo *si, unsigned long f, unsigned long r, unsigned long t, unsigned long rt); /*************************************************************** * Sample Information List ***************************************************************/ typedef struct SampleInfoList { SampleInfo sampleInfo[MAX_NUM_SAMPLES]; unsigned long fid; // flow to which this list belongs int n_samples; // number of samples collected so far } SampleInfoList; void SIL_init(SampleInfoList *sil, unsigned long f); void SIL_append(SampleInfoList *sil, SampleInfo si); void SIL_enableAllSamples(SampleInfoList *sil); void SIL_deleteAllItems(SampleInfoList *sil); /************************************************************** * flow Information **************************************************************/ typedef struct FlowInfo { unsigned long fid; // flow ID unsigned long dst; // destination address int gid; // its group id (initially -1) int lastSampleSendTime; // to keep packet ordering SampleInfoList *sampleList; // latest Sample information list CCList *ccl; // Correlation coefficient lists struct FlowInfo *next; } FlowInfo; int FI_init(FlowInfo *fi, unsigned long f, unsigned long d); void FI_destroy(FlowInfo *fi); void FI_addSampleInfo(FlowInfo *fi, SampleInfo sampleInfo); /************************************************************* * Flow table (Destination address hash table) *************************************************************/ typedef struct FlowTable { FlowInfo *head[HASH_TABLE_SIZE]; int numFlows; } FlowTable; void FT_init(FlowTable *ft); FlowInfo *FT_addFlow(FlowTable *ft, unsigned long fid, unsigned long dst); void FT_removeFlow(FlowTable *ft, unsigned long fid, unsigned long dst); FlowInfo *FT_findFlow(FlowTable *ft, unsigned long fid, unsigned long dst, int is_dst_provided); int FT_sameGroup(FlowTable *ft, unsigned long fid1, unsigned long fid2); void FT_updateTable(FlowTable *ft); GroupList *FT_correlateFlows(FlowTable *ft); int FT_correlateTwoFlows(FlowTable *ft, FlowInfo *f1, FlowInfo *f2, CorrSet **cs); double FT_getAvgDist(FlowTable *ft, CorrSet *cs, SampleInfoList *si1, SampleInfoList *si2); void FT_AutoCorr(FlowTable *ft, SampleInfoList *sil, CorrelationCoeff *cc, double avg_t); void FT_CrossCorr(FlowTable *ft, SampleInfoList *si1, SampleInfoList *si2, CorrelationCoeff *cc); void FT_regroup(FlowTable *ft, GroupList *gl, GroupNode *newGN); void FT_listFlows(FlowTable *ft); void FT_destroy(FlowTable *ft); /*************************************************************** * Flow correlator ***************************************************************/ typedef struct FlowCorrelator { unsigned int win_sz; // correlation window in msec GroupList *groups; // output group list FlowTable *flowTable; // Flow table struct timer_list ctimer; // timer used to invoke the grouping process } FlowCorrelator; void FC_init(int win); void FC_gatherSamples(FlowCorrelator *fc,unsigned long fid, unsigned long dst, unsigned long recv_time, unsigned long send_time, unsigned long rtt); void FC_addFlow(FlowCorrelator *fc, unsigned long fid, unsigned long dst); void FC_removeFlow(FlowCorrelator *fc, unsigned long fid, unsigned long dst); void FC_updateFlowTable(FlowCorrelator *fc); GroupList *FC_buildGroups(FlowCorrelator *fc); void FC_destroy(FlowCorrelator *fc); /*************************************************************/ extern FlowCorrelator *fcorrelator; /* global flow correlator structure */ extern int corr_mode; /* FORWARD_DELAY / RTT / NORMAL_TCP */ extern int CorrCreated; /* Is FlowCorrelator created ? */ extern int ignore_history; /* Should history be ignored (0/1) ? */ #endif