EWdetectorB Class Reference

#include <ew.h>

Inheritance diagram for EWdetectorB:

[legend]Collaboration diagram for EWdetectorB:

[legend]List of all members.

Public Member Functions
	EWdetectorB ()
virtual	~EWdetectorB ()
void	init (int)
int	exFlow (Packet *)
void	setDb (int)
void	setDt (int)
void	setLink (int, int)
void	setAlarm ()
void	resetAlarm ()
int	testAlarm ()
void	setChange ()
void	resetChange ()
void	run (Packet *)
Public Attributes
int	ew_src
int	ew_dst
double	now
int	db_timer
int	dt_timer
int	dt_inv
int	db_inv
double	cur_rate
double	avg_rate
int	alarm
int	change
HLF	hlf
Private Member Functions
void	measure (Packet *)
void	updateCur ()
void	updateAvg ()
void	detect ()
void	updateAList (Packet *)
AListEntry *	getMaxAList ()
void	sortAList ()
void	timeoutAList ()
AListEntry *	searchAList (int, int, int)
AListEntry *	newAListEntry (int, int, int)
int	getMedianAList (int, int)
int	getRateAList (int)
void	resetAList ()
void	printAListEntry (struct AListEntry *, int)
void	printAList ()
int	computeARR ()
void	computeDropP ()
void	decSInv ()
void	incSInv ()
void	trace ()
void	updateSWin (int)
void	ravgSWin ()
void	resetSWin ()
void	printSWin ()
void	printSWinEntry (struct SWinEntry *, int)
Private Attributes
float	adjustor
float	drop_p
int	arr_count
AList	alist
SWin	swin

---

Constructor & Destructor Documentation

EWdetectorB::EWdetectorB (   )

Definition at line 303 of file ew.cc. References adjustor, alist, arr_count, SWin::count, AList::count, drop_p, SWin::head, AList::head, SWin::ravg, swin, SWin::tail, and AList::tail. : EWdetector() { drop_p = 0; arr_count = 0; adjustor = 1.0; // Initialize ALIST alist.head = alist.tail = NULL; alist.count = 0; swin.head = swin.tail = NULL; swin.count = swin.ravg = 0; }

EWdetectorB::~EWdetectorB (   )  [virtual]

Definition at line 318 of file ew.cc. References resetAList(), and resetSWin(). { resetAList(); resetSWin(); }

Here is the call graph for this function:

---

Member Function Documentation

int EWdetectorB::computeARR (   )  [private]

Definition at line 423 of file ew.cc. References alist, arr_count, AList::count, getRateAList(), sortAList(), and timeoutAList(). Referenced by trace(), and updateCur(). { int i, agg_rate; // Explicit garbage collection first // before both choosing HBFs and searching AList //printf("before timeout "); timeoutAList(); //printf("after timeout "); // do nothing if no entry exists if (!alist.count) return 0; // Pick the 10% highest bandwidth flows arr_count = (int) (alist.count * 0.1 + 1); // Sort AList first sortAList(); // Calculate the ARR for HBFs // Use mean agg_rate = 0; for (i = 0; i < arr_count; i++) { agg_rate += getRateAList(i); } if (i) agg_rate = (int) (agg_rate / i); else { printf("No MAX returned from ALIST!!!\n"); } // Use median (the median for the list or median for HBFs?) //agg_rate = getMedianAList(0, k); //printf("%f %d %d %d\n", now, k, agg_rate, getMedianAList(0, k)); return(agg_rate); }

Here is the call graph for this function:

void EWdetectorB::computeDropP (   )  [private]

Definition at line 732 of file ew.cc. References adjustor, EWdetector::alarm, EWdetector::avg_rate, EWdetector::cur_rate, drop_p, EW_FADING_FACTOR, EW_MAX_DROP_P, and EW_MIN_DROP_P. { double p = 0; if (alarm) { // Compute the dropping probability as a linear function of current rate // p is computed towards the current measurement. p = 1; if (cur_rate) p = (avg_rate - cur_rate) * adjustor / cur_rate; // p could be greater than 1 if (p > 1) p = 1; // p could also be negative if (p < 0) p = 0; // Compute the actual drop probability drop_p = EW_FADING_FACTOR * drop_p + (1 - EW_FADING_FACTOR) * p; // adjust drop_p if (drop_p < EW_MIN_DROP_P) drop_p = EW_MIN_DROP_P; if (drop_p > EW_MAX_DROP_P) drop_p = EW_MAX_DROP_P; } else { // Fade out the drop_p when no alarm if (drop_p > 0) { if (drop_p <= EW_MIN_DROP_P) drop_p = 0; else { drop_p = EW_FADING_FACTOR * drop_p; } } } }

void EWdetectorB::decSInv (   )  [private]

Definition at line 769 of file ew.cc. { // Need some investigation for the min allowed detection interval // if (s_inv / 2 > EW_MIN_SAMPLE_INTERVAL) { // s_inv = s_inv / 2; //printf("SINV decreased by 2.\n"); //} }

void EWdetectorB::detect (   )  [private, virtual]

Implements EWdetector. Definition at line 703 of file ew.cc. References EWdetector::alarm, EWdetector::avg_rate, EWdetector::cur_rate, drop_p, EW_DETECT_RANGE, EW_MAX_DROP_P, EWdetector::resetAlarm(), and EWdetector::setAlarm(). { // When ALARM: // detect if it is the time to release the alarm // When NO ALARM: // detect if it is the time to trigger the alarm if (alarm) { // Determine if an alarm should be released if (cur_rate > avg_rate * (1 + EW_DETECT_RANGE)) { // reset alarm resetAlarm(); } } else { // Determine if an alarm should be triggered // need to be conservative! if (cur_rate < avg_rate) { setAlarm(); // Initial drop_p to the MAX value whenever alarm triggered if (drop_p < EW_MAX_DROP_P) drop_p = EW_MAX_DROP_P; } else { } } // Determine the dropping probability //computeDropP(); }

Here is the call graph for this function:

int EWdetectorB::exFlow (  Packet *   )

Definition at line 345 of file ew.cc. { // Should check SYN packets to protect existing connections // need to use FullTCP return(0); }

struct AListEntry * EWdetectorB::getMaxAList (   )  [private]

Definition at line 513 of file ew.cc. References alist, AList::head, and max. Referenced by sortAList(). { struct AListEntry *p, *pp, *max, *pm; //printAList(); // find the max entry and remove p = pp = alist.head; max = pm = p; while (p) { if (p->avg_rate > max->avg_rate) { pm = pp; max = p; } pp = p; p = p->next; } // remove max from AList if (alist.head == max) alist.head = max->next; if (pm != max) pm->next = max->next; max->next = NULL; //printAList(); return(max); }

int EWdetectorB::getMedianAList (  int  , int  )  [private]

Definition at line 386 of file ew.cc. References getRateAList(), and sortAList(). Referenced by trace(). { int m; if (!count) return 0; sortAList(); //printAList(); // Pick the entry with median avg_rate m = (int) (count / 2); if (2 * m == count) { return((getRateAList(index + m - 1) + getRateAList(index + m)) / 2); } else { return(getRateAList(index + m)); } }

Here is the call graph for this function:

int EWdetectorB::getRateAList (  int   )  [private]

Definition at line 405 of file ew.cc. References alist, AList::head, and AListEntry::next. Referenced by computeARR(), and getMedianAList(). { struct AListEntry *p; //printf("%d\n", index); p = alist.head; for (int i = 0; i < index; i++) { if (p) p = p->next; } if (p) return ((int)p->avg_rate); printf("Error in AList!\n"); return(0); }

void EWdetectorB::incSInv (   )  [private]

Definition at line 779 of file ew.cc. { //if(s_inv * 2 <= init_s_inv) { // s_inv = s_inv * 2; //printf("SINV increased by 2.\n"); // } }

void EWdetectorB::init (  int   )

Definition at line 324 of file ew.cc. References adjustor. Referenced by EWPolicy::detectBr(). { // EW adjustor (g = resp rate / request rate) adjustor = ew_adj; }

void EWdetectorB::measure (  Packet *   )  [private, virtual]

Implements EWdetector. Definition at line 330 of file ew.cc. References updateAList(). { //printf(" before UA"); // Conduct detection continously updateAList(pkt); //printf(" after UA"); }

Here is the call graph for this function:

struct AListEntry * EWdetectorB::newAListEntry (  int  , int  , int  )  [private]

Definition at line 484 of file ew.cc. References alist, AListEntry::avg_rate, AList::count, AListEntry::dst_id, AListEntry::f_id, AList::head, AListEntry::last_update, AListEntry::next, EWdetector::now, AListEntry::src_id, AListEntry::t_front, AList::tail, and AListEntry::win_length. Referenced by updateAList(). { AListEntry *p; p = new AListEntry; p->src_id = src_id; p->dst_id = dst_id; p->f_id = f_id; p->last_update = now; p->avg_rate = 0; // Since we are doing random sampling, // the t_front should set to the beginning of this period instead of 0. p->t_front = now; p->win_length = 1; p->next = NULL; // Add new entry to AList if (alist.tail) alist.tail->next = p; alist.tail = p; if (!alist.head) alist.head = p; alist.count++; return(p); }

void EWdetectorB::printAList (   )  [private]

Definition at line 818 of file ew.cc. References alist, AList::count, AList::head, EWdetector::now, and printAListEntry(). { struct AListEntry *p; printf("%f AList(%d):\n", now, alist.count); p = alist.head; int i = 0; while (p) { printAListEntry(p, i); i++; p = p->next; } p = NULL; printf("\n"); }

Here is the call graph for this function:

void EWdetectorB::printAListEntry (  struct AListEntry *  , int  )  [private]

Definition at line 808 of file ew.cc. References AListEntry::avg_rate, AListEntry::dst_id, AListEntry::f_id, AListEntry::last_update, and AListEntry::src_id. Referenced by printAList(). { if (!p) return; printf("[%d] %d (%d %d) %.2f %.2f\n", i, p->f_id, p->src_id, p->dst_id, p->avg_rate, p->last_update); }

void EWdetectorB::printSWin (   )  [private]

Definition at line 788 of file ew.cc. References SWin::count, SWin::head, EWdetector::now, printSWinEntry(), SWin::ravg, and swin. { struct SWinEntry *p; printf("%f SWIN[%d, %d]", now, swin.ravg, swin.count); p = swin.head; int i = 0; while (p) { printSWinEntry(p, i++); p = p->next; } p = NULL; printf("\n"); }

Here is the call graph for this function:

void EWdetectorB::printSWinEntry (  struct SWinEntry *  , int  )  [private]

Definition at line 802 of file ew.cc. References SWinEntry::rate, and SWinEntry::weight. Referenced by printSWin(). { if (p) printf("[%d: %d %.2f] ", i, p->rate, p->weight); }

void EWdetectorB::ravgSWin (   )  [private]

Definition at line 677 of file ew.cc. References SWin::head, SWinEntry::rate, SWin::ravg, and swin. { struct SWinEntry *p; float sum = 0; float t_weight = 0; //printf("Calculate running average over the sliding window:\n"); p = swin.head; //printf("after p\n"); while (p) { //printSWinEntry(p, i++); sum += p->rate * p->weight; t_weight += p->weight; p = p->next; } p = NULL; //printf("\n"); swin.ravg = (int)(sum / t_weight); // printf("Ravg: %d\n", swin.ravg); }

void EWdetector::resetAlarm (   )  [inherited]

Definition at line 213 of file ew.cc. References EWdetector::alarm, EWdetector::avg_rate, EWdetector::hlf, and HLF::reset(). Referenced by EWdetectorP::detect(), detect(), and EWdetector::EWdetector(). { alarm = 0; // Reset low and high gain filters' input values to the long-term avg // Actually, there is no change to low gain filter hlf.reset(avg_rate); };

Here is the call graph for this function:

void EWdetectorB::resetAList (   )  [private]

Definition at line 617 of file ew.cc. References alist, AList::count, AList::head, AListEntry::next, and AList::tail. Referenced by ~EWdetectorB(). { struct AListEntry *ap, *aq; ap = aq = alist.head; while (ap) { aq = ap; ap = ap->next; free(aq); } ap = aq = NULL; alist.head = alist.tail = NULL; alist.count = 0; }

void EWdetector::resetChange (   )  [inherited]

Definition at line 226 of file ew.cc. References EWdetector::change. Referenced by EWPolicy::detect(), and EWdetector::EWdetector(). { change = 0; }

void EWdetectorB::resetSWin (   )  [private]

Definition at line 635 of file ew.cc. References SWin::count, SWin::head, SWinEntry::next, SWin::ravg, swin, and SWin::tail. Referenced by ~EWdetectorB(). { struct SWinEntry *p, *q; p = q = swin.head; while (p) { q = p; p = p->next; free(q); } p = q = NULL; swin.head = swin.tail = NULL; swin.count = swin.ravg = 0; }

void EWdetector::run (  Packet *   )  [inherited]

Definition at line 261 of file ew.cc. References EWdetector::change, Scheduler::clock(), EWdetector::db_inv, EWdetector::db_timer, EWdetector::detect(), EWdetector::dt_inv, EWdetector::dt_timer, Scheduler::instance(), EWdetector::measure(), EWdetector::now, EWdetector::trace(), EWdetector::updateAvg(), and EWdetector::updateCur(). Referenced by EWPolicy::applyPolicer(). { // get the time now = Scheduler::instance().clock(); //printf("EW[%d:%d] run ", ew_src, ew_dst); // update the measurement measure(pkt); // There is a timeout! if (now >= dt_timer) { // Start detection //printf("Detection timeout(%d)\n", (int)now); // 1. Update the current rate from measurement updateCur(); // 2. Detect change and Trigger alarm if necessary // Compare the current rate with the long term average detect(); // 3. Update the long term averages updateAvg(); // setup the sleeping timer dt_timer = (int)now + dt_inv; //printf("%d\n", dt_inv); change = 1; } // Schedule debug if (db_inv && now >= db_timer) { //printf("debugB "); trace(); db_timer = (int)now + db_inv; } }

Here is the call graph for this function:

struct AListEntry * EWdetectorB::searchAList (  int  , int  , int  )  [private]

Definition at line 463 of file ew.cc. References alist, AListEntry::dst_id, AListEntry::f_id, AList::head, AListEntry::next, AListEntry::src_id, and timeoutAList(). Referenced by updateAList(). { AListEntry *p; // Explicit garbage collection first. //printf("before timeout "); timeoutAList(); //printf("after timeout "); // Use src and dest pair and flow id: // aggregate flows within the same request-response exchange // Timeout need to be set to a very small value in order to // seperate different exchanges. p = alist.head; while (p && (p->f_id != f_id || p->src_id != src_id || p->dst_id != dst_id)) { p = p->next; } return(p); }

Here is the call graph for this function:

void EWdetector::setAlarm (   )  [inherited]

Definition at line 205 of file ew.cc. References EWdetector::alarm, EWdetector::avg_rate, EWdetector::hlf, and HLF::reset(). Referenced by EWdetectorP::detect(), and detect(). { alarm = 1; // Reset low and high gain filters' input values to the long-term avg // Actually, there is no change to high gain filter hlf.reset(avg_rate); };

Here is the call graph for this function:

void EWdetector::setChange (   )  [inherited]

Definition at line 222 of file ew.cc. References EWdetector::change. { change = 1; }

void EWdetector::setDb (  int   )  [inherited]

Definition at line 194 of file ew.cc. References EWdetector::db_inv. Referenced by EWPolicy::detectBr(), and EWPolicy::detectPr(). { db_inv = inv; //printf("DB: %d\n", db_inv); };

void EWdetector::setDt (  int   )  [inherited]

Definition at line 190 of file ew.cc. References EWdetector::dt_inv. Referenced by EWPolicy::detectBr(), and EWPolicy::detectPr(). { dt_inv = inv; //printf("DT: %d\n", dt_inv); };

void EWdetector::setLink (  int  , int  )  [inherited]

Definition at line 199 of file ew.cc. References EWdetector::ew_dst, and EWdetector::ew_src. Referenced by EWPolicy::detectBr(), and EWPolicy::detectPr(). { ew_src = src; ew_dst = dst; //printf("EW: (%d:%d)\n", ew_src, ew_dst); };

void EWdetectorB::sortAList (   )  [private]

Definition at line 545 of file ew.cc. References alist, getMaxAList(), AList::head, max, and AList::tail. Referenced by computeARR(), and getMedianAList(). { struct AListEntry *max, *head, *tail; if (!alist.head) return; //printAList(); head = tail = NULL; while (alist.head) { // Get the entry with the max avg_rate max = getMaxAList(); //printAListEntry(max, i); if (max) { // Add max to the tail of the new list if (tail) tail->next = max; tail = max; if (!head) head = max; } } alist.head = head; alist.tail = tail; //printAList(); }

Here is the call graph for this function:

int EWdetector::testAlarm (   )  [inherited]

Definition at line 231 of file ew.cc. References EWdetector::alarm, EWdetector::change, and EW_UNCHANGE. Referenced by EWPolicy::detect(). { if (!change) return(EW_UNCHANGE); else return(alarm); }

void EWdetectorB::timeoutAList (   )  [private]

Definition at line 577 of file ew.cc. References alist, AList::count, EWdetector::dt_inv, EW_FLOW_TIME_OUT, AList::head, AListEntry::last_update, AListEntry::next, EWdetector::now, and AList::tail. Referenced by computeARR(), searchAList(), and trace(). { AListEntry *p, *q; float to; to = EW_FLOW_TIME_OUT; if (dt_inv) to = dt_inv; // Expire the old entries in AList p = q = alist.head; while (p) { // Garbage collection if (p->last_update + to < now){ // The coresponding flow is expired. if (p == alist.head){ if (p == alist.tail) { alist.head = alist.tail = NULL; free(p); p = q = NULL; } else { alist.head = p->next; free(p); p = q = alist.head; } } else { q->next = p->next; if (p == alist.tail) alist.tail = q; free(p); p = q->next; } alist.count--; } else { q = p; p = q->next; } } }

void EWdetectorB::trace (   )  [private, virtual]

Implements EWdetector. Definition at line 834 of file ew.cc. References EWdetector::alarm, alist, arr_count, EWdetector::avg_rate, computeARR(), AList::count, EWdetector::cur_rate, getMedianAList(), EWdetector::now, and timeoutAList(). { double db_rate = 0; double m_rate = 0; timeoutAList(); m_rate = getMedianAList(0, alist.count); //printf("B "); db_rate = computeARR(); if (!m_rate || !db_rate); //printAList(); printf("B %d %.2f %.2f %d %d %.2f %.2f\n", (int)now, cur_rate, avg_rate, arr_count, alarm, db_rate, m_rate); }

Here is the call graph for this function:

void EWdetectorB::updateAList (  Packet *   )  [private]

Definition at line 352 of file ew.cc. References hdr_ip::access(), hdr_cmn::access(), AListEntry::avg_rate, hdr_ip::daddr(), AListEntry::dst_id, AListEntry::f_id, hdr_ip::flowid(), newAListEntry(), EWdetector::now, hdr_ip::saddr(), searchAList(), hdr_cmn::size(), AListEntry::src_id, AListEntry::t_front, and AListEntry::win_length. Referenced by measure(). { hdr_cmn* hdr = hdr_cmn::access(pkt); hdr_ip* iph = hdr_ip::access(pkt); int dst_id = iph->daddr(); int src_id = iph->saddr(); int f_id = iph->flowid(); // Get the corresponding id. //printf("EW[%d:%d] in detector\n", ew_src, ew_dst); AListEntry *p; p = searchAList(src_id, dst_id, f_id); // Add new entry to AList // keep the bytes sent by each aggregate in AList if (!p) { p = newAListEntry(src_id, dst_id, f_id); } // update the existing (or just created) entry in AList assert(p && p->f_id == f_id && p->src_id == src_id && p->dst_id == dst_id); // update the flow's arrival rate using TSW double bytesInTSW, newBytes; bytesInTSW = p->avg_rate * p->win_length; newBytes = bytesInTSW + (double) hdr->size(); p->avg_rate = newBytes / (now - p->t_front + p->win_length); p->t_front = now; //printAListEntry(p, 0); }

Here is the call graph for this function:

void EWdetectorB::updateAvg (   )  [private]

Reimplemented from EWdetector.

void EWdetectorB::updateCur (   )  [private, virtual]

Implements EWdetector. Definition at line 338 of file ew.cc. References computeARR(), and EWdetector::cur_rate. { //printAList(); // Record current aggregated response rate cur_rate = computeARR(); }

Here is the call graph for this function:

void EWdetectorB::updateSWin (  int   )  [private]

Definition at line 651 of file ew.cc. References SWin::count, EW_SWIN_SIZE, SWin::head, SWinEntry::next, swin, and SWin::tail. { struct SWinEntry *p, *new_entry; new_entry = new SWinEntry; new_entry->rate = rate; new_entry->weight = 1; new_entry->next = NULL; if (swin.tail) swin.tail->next = new_entry; swin.tail = new_entry; if (!swin.head) swin.head = new_entry; // Reset current rate. if (swin.count < EW_SWIN_SIZE) { swin.count++; } else { p = swin.head; swin.head = p->next; free(p); } }

---

Member Data Documentation

float EWdetectorB::adjustor [private]

Definition at line 265 of file ew.h. Referenced by computeDropP(), EWdetectorB(), and init().

int EWdetector::alarm [inherited]

Definition at line 201 of file ew.h. Referenced by computeDropP(), EWdetectorP::detect(), detect(), EWdetector::resetAlarm(), EWdetector::setAlarm(), EWdetector::testAlarm(), EWdetectorP::trace(), trace(), and EWdetector::updateAvg().

struct AList EWdetectorB::alist [private]

Definition at line 271 of file ew.h. Referenced by computeARR(), EWdetectorB(), getMaxAList(), getRateAList(), newAListEntry(), printAList(), resetAList(), searchAList(), sortAList(), timeoutAList(), and trace().

int EWdetectorB::arr_count [private]

Definition at line 268 of file ew.h. Referenced by computeARR(), EWdetectorB(), and trace().

double EWdetector::avg_rate [inherited]

Definition at line 198 of file ew.h. Referenced by computeDropP(), EWdetectorP::detect(), detect(), EWdetector::EWdetector(), EWdetector::resetAlarm(), EWdetector::setAlarm(), EWdetectorP::trace(), trace(), and EWdetector::updateAvg().

int EWdetector::change [inherited]

Definition at line 203 of file ew.h. Referenced by EWdetector::resetChange(), EWdetector::run(), EWdetector::setChange(), and EWdetector::testAlarm().

double EWdetector::cur_rate [inherited]

Definition at line 198 of file ew.h. Referenced by computeDropP(), EWdetectorP::detect(), detect(), EWdetector::EWdetector(), EWdetectorP::getRate(), EWdetectorP::trace(), trace(), EWdetector::updateAvg(), EWdetectorP::updateCur(), and updateCur().

int EWdetector::db_inv [inherited]

Definition at line 195 of file ew.h. Referenced by EWdetector::run(), and EWdetector::setDb().

int EWdetector::db_timer [inherited]

Definition at line 193 of file ew.h. Referenced by EWdetector::EWdetector(), and EWdetector::run().

float EWdetectorB::drop_p [private]

Definition at line 266 of file ew.h. Referenced by computeDropP(), detect(), and EWdetectorB().

int EWdetector::dt_inv [inherited]

Definition at line 195 of file ew.h. Referenced by EWdetector::run(), EWdetector::setDt(), timeoutAList(), and EWdetectorP::updateCur().

int EWdetector::dt_timer [inherited]

Definition at line 193 of file ew.h. Referenced by EWdetector::EWdetector(), and EWdetector::run().

int EWdetector::ew_dst [inherited]

Definition at line 187 of file ew.h. Referenced by EWdetector::EWdetector(), and EWdetector::setLink().

int EWdetector::ew_src [inherited]

Definition at line 187 of file ew.h. Referenced by EWdetector::EWdetector(), and EWdetector::setLink().

HLF EWdetector::hlf [inherited]

Definition at line 206 of file ew.h. Referenced by EWdetector::EWdetector(), EWdetector::resetAlarm(), EWdetector::setAlarm(), and EWdetector::updateAvg().

double EWdetector::now [inherited]

Definition at line 190 of file ew.h. Referenced by newAListEntry(), printAList(), printSWin(), EWdetector::run(), timeoutAList(), EWdetectorP::trace(), trace(), and updateAList().

struct SWin EWdetectorB::swin [private]

Definition at line 273 of file ew.h. Referenced by EWdetectorB(), printSWin(), ravgSWin(), resetSWin(), and updateSWin().

---

The documentation for this class was generated from the following files:

• ew.h
• ew.cc

---