// Copyright (c) 1999 by the University of Southern California				// Copyright (c) 1999 by the University of Southern California
// All rights reserved.									// All rights reserved.
//											//
// Permission to use, copy, modify, and distribute this software and its		// Permission to use, copy, modify, and distribute this software and its
// documentation in source and binary forms for non-commercial purposes			// documentation in source and binary forms for non-commercial purposes
// and without fee is hereby granted, provided that the above copyright			// and without fee is hereby granted, provided that the above copyright
// notice appear in all copies and that both the copyright notice and			// notice appear in all copies and that both the copyright notice and
// this permission notice appear in supporting documentation. and that			// this permission notice appear in supporting documentation. and that
// any documentation, advertising materials, and other materials related		// any documentation, advertising materials, and other materials related
// to such distribution and use acknowledge that the software was			// to such distribution and use acknowledge that the software was
// developed by the University of Southern California, Information			// developed by the University of Southern California, Information
// Sciences Institute.  The name of the University may not be used to			// Sciences Institute.  The name of the University may not be used to
// endorse or promote products derived from this software without			// endorse or promote products derived from this software without
// specific prior written permission.							// specific prior written permission.
//											//
// THE UNIVERSITY OF SOUTHERN CALIFORNIA makes no representations about			// THE UNIVERSITY OF SOUTHERN CALIFORNIA makes no representations about
// the suitability of this software for any purpose.  THIS SOFTWARE IS			// the suitability of this software for any purpose.  THIS SOFTWARE IS
// PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES,			// PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES,
// INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF				// INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.				// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//											//
// Other copyrights might apply to parts of this software and are so			// Other copyrights might apply to parts of this software and are so
// noted when applicable.								// noted when applicable.
//											//
// ew.h (Early warning system)								// ew.h (Early warning system)
//   by Xuan Chen (xuanc@isi.edu), USC/ISI						//   by Xuan Chen (xuanc@isi.edu), USC/ISI

#ifndef EW_H										#ifndef EW_H
#define EW_H										#define EW_H

#include "packet.h"									#include "packet.h"
#include "dsPolicy.h"									#include "dsPolicy.h"

#define EW_MAX_WIN 8									#define EW_MAX_WIN 8
#define EW_SWIN_SIZE 4									#define EW_SWIN_SIZE 4
// the max and min dropping probability							// the max and min dropping probability
#define EW_DETECT_RANGE 0.1								#define EW_DETECT_RANGE 0.1
#define EW_MIN_DROP_P 0.1								#define EW_MIN_DROP_P 0.1
#define EW_MAX_DROP_P 0.9								#define EW_MAX_DROP_P 0.9
#define EW_FLOW_TIME_OUT 10.0								#define EW_FLOW_TIME_OUT 10.0

#define EW_SAMPLE_INTERVAL 240								#define EW_SAMPLE_INTERVAL 240
#define EW_DETECT_INTERVAL 60								#define EW_DETECT_INTERVAL 60
#define EW_MIN_SAMPLE_INTERVAL 60							#define EW_MIN_SAMPLE_INTERVAL 60
#define EW_MIN_DETECT_INTERVAL 15							#define EW_MIN_DETECT_INTERVAL 15
#define EW_FADING_FACTOR 0.875								#define EW_FADING_FACTOR 0.875

#define PKT_ARRIVAL 1001								#define PKT_ARRIVAL 1001
#define PKT_DEPT 1002									#define PKT_DEPT 1002
#define PKT_DROP 1003									#define PKT_DROP 1003

#define EW_DT_INV 240									#define EW_DT_INV 240
#define EW_DB_INV EW_DT_INV								#define EW_DB_INV EW_DT_INV

#define EW_UNCHANGE -1									#define EW_UNCHANGE -1

// The default tocken-bucket size and tocken rate (in packet/byte)			// The default tocken-bucket size and tocken rate (in packet/byte)
#define DEFAULT_TB_SIZE 50								#define DEFAULT_TB_SIZE 50
#define DEFAULT_TB_RATE_P 5								#define DEFAULT_TB_RATE_P 5
#define DEFAULT_TB_RATE_B 1000								#define DEFAULT_TB_RATE_B 1000

// EW											// EW

// Record the number of packet arrived, departured, and dropped				// Record the number of packet arrived, departured, and dropped
struct PktRec {										struct PktRec {
  int arrival, dept, drop;								  int arrival, dept, drop;
};											};

// Record the detection result								// Record the detection result
struct AListEntry {									struct AListEntry {
  int src_id;										  int src_id;
  int dst_id;										  int dst_id;
  int f_id;										  int f_id;
  double last_update;									  double last_update;
  double avg_rate;									  double avg_rate;
  double t_front;									  double t_front;
  double win_length;									  double win_length;
  struct AListEntry *next;								  struct AListEntry *next;
};											};

// List of detection result for aggregates						// List of detection result for aggregates
struct AList {										struct AList {
  struct AListEntry *head, *tail;							  struct AListEntry *head, *tail;
  int count;										  int count;
};											};

// Record the request ratio								// Record the request ratio
struct SWinEntry {									struct SWinEntry {
  float weight;										  float weight;
  int rate;										  int rate;
  struct SWinEntry *next;								  struct SWinEntry *next;
};											};

// Data structure for sliding window							// Data structure for sliding window
struct SWin {										struct SWin {
  // counter of entries in the sliding window						  // counter of entries in the sliding window
  int count;										  int count;
  // current running average								  // current running average
  int ravg;										  int ravg;

  // List of SWin Entries								  // List of SWin Entries
  struct SWinEntry *head;								  struct SWinEntry *head;
  struct SWinEntry *tail;								  struct SWinEntry *tail;
};											};

// Data structure for High-low filter							// Data structure for High-low filter
// high(t) = alpha * high(t-1) + (1 - alpha) * o(t)					// high(t) = alpha * high(t-1) + (1 - alpha) * o(t)
// low(t) = (1 - alpha) * low(t-1) + alpha * o(t)					// low(t) = (1 - alpha) * low(t-1) + alpha * o(t)
class HLF {										class HLF {
 public:										 public:
  HLF();										  HLF();

  // configure the HLF									  // configure the HLF
  void setAlpha(double);								  void setAlpha(double);
  void reset(double value);								  void reset(double value);
  void reset();										  void reset();

  // Get the output of HLF								  // Get the output of HLF
  double getHigh();									  double getHigh();
  double getLow();									  double getLow();

  // update high-low filter								  // update high-low filter
  void update(double);									  void update(double);

 private:										 private:
  double alpha;										  double alpha;
  											  
  // the estimated value for the high-pass/low-pass filters				  // the estimated value for the high-pass/low-pass filters
  double high, low;									  double high, low;
};											};

// Definition for a tocken-bucket rate limitor						// Definition for a tocken-bucket rate limitor
class TBrateLimitor {									class TBrateLimitor {
 public:										 public:
  TBrateLimitor();									  TBrateLimitor();
  TBrateLimitor(double);								  TBrateLimitor(double);

  // set the rate									  // set the rate
  void setRate(double);									  void setRate(double);
  // adjust the rate									  // adjust the rate
  void adjustRate();									  void adjustRate();

  // parameters for a tocken bucket							  // parameters for a tocken bucket
  // the size of the token bucket (in bytes or packets)					  // the size of the token bucket (in bytes or packets)
  double bucket_size;             							  double bucket_size;             
  // number of tokens in the bucket (in bytes or packets)				  // number of tokens in the bucket (in bytes or packets)
  double tocken_num;									  double tocken_num;
  // the rate to generate tockens							  // the rate to generate tockens
  double tocken_rate, ini_tocken_rate, last_tocken_rate;				  double tocken_rate, ini_tocken_rate, last_tocken_rate;
  // last time when updating states							  // last time when updating states
  double last_time;									  double last_time;

  // in packet or byte mode (packet mode, by default)					  // in packet or byte mode (packet mode, by default)
  int pkt_mode;										  int pkt_mode;

  int run(double);									  int run(double);
  int run(double, double); 								  int run(double, double); 

  // states to determine the direction of increasing/decreasing rate			  // states to determine the direction of increasing/decreasing rate
  int n_score, p_score;									  int n_score, p_score;

  // adjust the score for increasing or decreasing scores				  // adjust the score for increasing or decreasing scores
  void resetScore();									  void resetScore();
  void adjustScore(int);								  void adjustScore(int);
};											};

// Definition for the EW detector							// Definition for the EW detector
class EWdetector {									class EWdetector {
 public:										 public:
  EWdetector();										  EWdetector();
  //virtual ~EWdetector() = 0;								  //virtual ~EWdetector() = 0;

  // Enable detecting and debugging rate (eg: pkt or bit rate)				  // Enable detecting and debugging rate (eg: pkt or bit rate)
  void setDb(int);									  void setDb(int);
  void setDt(int);									  void setDt(int);
  void setLink(int, int);								  void setLink(int, int);

  // set and clean alarm								  // set and clean alarm
  void setAlarm();									  void setAlarm();
  void resetAlarm();									  void resetAlarm();
  int testAlarm();									  int testAlarm();

  void setChange();									  void setChange();
  void resetChange();									  void resetChange();
  //private:										  //private:
  // The nodes connected by EW								  // The nodes connected by EW
  int ew_src, ew_dst;									  int ew_src, ew_dst;

  // The current time									  // The current time
  double now;										  double now;

  // The timer for detection and debugging						  // The timer for detection and debugging
  int db_timer, dt_timer;								  int db_timer, dt_timer;
  // Detecting interval									  // Detecting interval
  int dt_inv, db_inv;									  int dt_inv, db_inv;

  // Current rate and long term average							  // Current rate and long term average
  double cur_rate, avg_rate;								  double cur_rate, avg_rate;

  // The alarm flag and proposed dropping probability					  // The alarm flag and proposed dropping probability
  int alarm;										  int alarm;

  int change;										  int change;

  // High-low filter									  // High-low filter
  HLF hlf;										  HLF hlf;

  // Detecting engine									  // Detecting engine
  void run(Packet *);									  void run(Packet *);
  // Conduct measurement								  // Conduct measurement
  virtual void measure(Packet *) = 0;							  virtual void measure(Packet *) = 0;
  // Detect changes									  // Detect changes
  virtual void detect() = 0;								  virtual void detect() = 0;
  // Update current measurement 							  // Update current measurement 
  virtual void updateCur() = 0;								  virtual void updateCur() = 0;
  // Update long term average								  // Update long term average
  void updateAvg();									  void updateAvg();

  // Trace function									  // Trace function
  virtual void trace() = 0;								  virtual void trace() = 0;

};											};

class EWdetectorP : public EWdetector {							class EWdetectorP : public EWdetector {
 public:										 public:
  EWdetectorP();									  EWdetectorP();
  virtual ~EWdetectorP();								  virtual ~EWdetectorP();

  // update packet stats								  // update packet stats
  void updateStats(int);								  void updateStats(int);
  // get the current request rate							  // get the current request rate
  double getRate();									  double getRate();

 private:										 private:
  // keep the packet rate stats								  // keep the packet rate stats
  PktRec cur_p, last_p, last_p_db;							  PktRec cur_p, last_p, last_p_db;

  // Conduct measurement								  // Conduct measurement
  void measure(Packet *);								  void measure(Packet *);
  // Detect changes									  // Detect changes
  void detect();									  void detect();
  // Update current measurement 							  // Update current measurement 
  void updateCur();									  void updateCur();
  // Update long term average								  // Update long term average
  void updateAvg();									  void updateAvg();

  // Trace function									  // Trace function
  void trace();										  void trace();
};											};

// EW											// EW
class EWdetectorB : public EWdetector {							class EWdetectorB : public EWdetector {
 public:										 public:
  EWdetectorB();									  EWdetectorB();
  virtual ~EWdetectorB();								  virtual ~EWdetectorB();

  // Initialize EW									  // Initialize EW
  void init(int);									  void init(int);

  // Check if the packet belongs to existing flow					  // Check if the packet belongs to existing flow
  int exFlow(Packet *);									  int exFlow(Packet *);

 private:										 private:
  // Adjustor										  // Adjustor
  float adjustor;									  float adjustor;
  float drop_p;										  float drop_p;
  // keep the count of flows for ARR							  // keep the count of flows for ARR
  int arr_count;									  int arr_count;

  // List to keep the detection results							  // List to keep the detection results
  struct AList alist;									  struct AList alist;
  // The sliding window for running average on the aggregated response rate		  // The sliding window for running average on the aggregated response rate
  struct SWin swin;									  struct SWin swin;
  											  
  // Conduct measurement								  // Conduct measurement
  void measure(Packet *);								  void measure(Packet *);
  // Update current measurement 							  // Update current measurement 
  void updateCur();									  void updateCur();
  // Update long term average								  // Update long term average
  void updateAvg();									  void updateAvg();
  // Change detection:									  // Change detection:
  // detect the traffic change in aggregated response rate				  // detect the traffic change in aggregated response rate
  void detect();									  void detect();
  											  
  // Measurement:									  // Measurement:
  // Conduct the measurement and update AList						  // Conduct the measurement and update AList
  void updateAList(Packet *);								  void updateAList(Packet *);
  // Find the max value in AList							  // Find the max value in AList
  struct AListEntry *getMaxAList();							  struct AListEntry *getMaxAList();
  // Sort AList based on the avg_rate							  // Sort AList based on the avg_rate
  void sortAList();									  void sortAList();
  // Timeout AList entries								  // Timeout AList entries
  void timeoutAList();									  void timeoutAList();
  // Find the matched AList entry							  // Find the matched AList entry
  struct AListEntry * searchAList(int, int, int);					  struct AListEntry * searchAList(int, int, int);
  // Add new entry to AList								  // Add new entry to AList
  struct AListEntry * newAListEntry(int, int, int);					  struct AListEntry * newAListEntry(int, int, int);
  // Get the median of AList								  // Get the median of AList
  int getMedianAList(int, int);								  int getMedianAList(int, int);
  // Get the rate given the index in the list						  // Get the rate given the index in the list
  int getRateAList(int);								  int getRateAList(int);
  // Reset AList									  // Reset AList
  void resetAList();									  void resetAList();
  // Print one entry in AList								  // Print one entry in AList
  void printAListEntry(struct AListEntry *, int);					  void printAListEntry(struct AListEntry *, int);
  // output contents in AList								  // output contents in AList
  void printAList();									  void printAList();

  // Calculate the aggragated response rate for high-bandwidth flows			  // Calculate the aggragated response rate for high-bandwidth flows
  int computeARR();									  int computeARR();

  // Determine the dropping probability based on current measurement			  // Determine the dropping probability based on current measurement
  void computeDropP();									  void computeDropP();

  // Increase/decrease the sample interval to adjust the detection latency.		  // Increase/decrease the sample interval to adjust the detection latency.
  void decSInv();									  void decSInv();
  void incSInv();									  void incSInv();

  // Trace bit rate (resp rate)								  // Trace bit rate (resp rate)
  void trace();										  void trace();

  // update swin with the latest measurement for one HTab entry.			  // update swin with the latest measurement for one HTab entry.
  void updateSWin(int);									  void updateSWin(int);
  // compute the running average on the sliding window					  // compute the running average on the sliding window
  void ravgSWin();									  void ravgSWin();
  // Reset SWin										  // Reset SWin
  void resetSWin();									  void resetSWin();
  // output contents in SWin								  // output contents in SWin
  void printSWin();									  void printSWin();
  // Print one entry in SWin								  // Print one entry in SWin
  void printSWinEntry(struct SWinEntry *, int);						  void printSWinEntry(struct SWinEntry *, int);
};											};

// Eearly warning policy: 								// Eearly warning policy: 
//  basically queueing stuffs								//  basically queueing stuffs
class EWPolicy : public Policy {							class EWPolicy : public Policy {
 public:										 public:
  EWPolicy();										  EWPolicy();
  ~EWPolicy();										  ~EWPolicy();

  void init(int, int, int);								  void init(int, int, int);
  											  
  // Metering and policing methods:							  // Metering and policing methods:
  void applyMeter(policyTableEntry *policy, Packet *pkt);				  void applyMeter(policyTableEntry *policy, Packet *pkt);
  int applyPolicer(policyTableEntry *policy, policerTableEntry *policer, Packet *pkt)	  int applyPolicer(policyTableEntry *policy, policerTableEntry *policer, Packet *pkt)

  //  make packet drop decisions							  //  make packet drop decisions
  int dropPacket(Packet *);								  int dropPacket(Packet *);
  // detect if there is an alarm triggered						  // detect if there is an alarm triggered
  void detect(Packet *pkt);								  void detect(Packet *pkt);
  											  
  // Enable detecting and debugging packet rate (eg: req rate)				  // Enable detecting and debugging packet rate (eg: req rate)
  void detectPr();									  void detectPr();
  void detectPr(int);									  void detectPr(int);
  void detectPr(int, int);								  void detectPr(int, int);

  // Enable detecting and debugging bit rate (eg: resp rate)				  // Enable detecting and debugging bit rate (eg: resp rate)
  void detectBr();									  void detectBr();
  void detectBr(int);									  void detectBr(int);
  void detectBr(int, int);								  void detectBr(int, int);
 											 
  // Rate limitor: packet rate								  // Rate limitor: packet rate
  void limitPr();									  void limitPr();
  void limitPr(double);									  void limitPr(double);
  // Rate limitor: bit rate								  // Rate limitor: bit rate
  void limitBr();									  void limitBr();
  void limitBr(double);									  void limitBr(double);

  // couple EW detector									  // couple EW detector
  void coupleEW(EWPolicy *);								  void coupleEW(EWPolicy *);
  void coupleEW(EWPolicy *, double);							  void coupleEW(EWPolicy *, double);

  //protected:										  //protected:
  EWdetectorB *ewB, *cewB;								  EWdetectorB *ewB, *cewB;
  EWdetectorP *ewP, *cewP;								  EWdetectorP *ewP, *cewP;

  TBrateLimitor *rlP, *rlB;								  TBrateLimitor *rlP, *rlB;
  											  
 private:										 private:
  // The current time									  // The current time
  double now;										  double now;
  											  
  // indicator for detecting and debugging						  // indicator for detecting and debugging
  int ew_adj, qsrc, qdst;								  int ew_adj, qsrc, qdst;

  // rate limits									  // rate limits
  int max_p, max_b;									  int max_p, max_b;

  // ew alarm										  // ew alarm
  int alarm, pre_alarm;									  int alarm, pre_alarm;
  int change;										  int change;
};											};
#endif											#endif
