1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
#ifndef ident_tree_h
#define ident_tree_h
#include <stdlib.h>
#include <stdio.h>
#include "address.h"
#include "packet.h"
#include "ip.h"
#include "tcl.h"
#include "math.h"
#include "pushback-constants.h"
class AggSpec;
struct cluster {
int prefix_;
int bits_;
int count_;
};
class AggReturn {
public:
cluster * clusterList_;
double limit_;
int finalIndex_;
int totalCount_;
AggReturn(cluster * clusterList, double bottom, int finalIndex, int totalCount) {
clusterList_ = clusterList;
limit_ = bottom;
finalIndex_ = finalIndex;
totalCount_=totalCount;
}
~AggReturn() {
free(clusterList_);
}
};
class DropHashTable {
public:
Tcl_HashTable * hashTable_;
int count_;
char key[200]; //generous space for key
DropHashTable():count_(0) {
hashTable_ = new Tcl_HashTable;
Tcl_InitHashTable(hashTable_, TCL_STRING_KEYS);
}
void
packetToKey(Packet *p) {
hdr_ip * iph = hdr_ip::access(p);
ns_addr_t src = iph->src();
ns_addr_t dst = iph->dst();
int fid = iph->flowid();
sprintf(key,"%d.%d %d.%d %d",src.addr_, src.port_, dst.addr_, dst.port_, fid);
}
void
insert(Packet *p, int size) {
count_+=size;
int new_entry;
long oldValue;
packetToKey(p);
Tcl_HashEntry* he = Tcl_CreateHashEntry(hashTable_, (char*) key, &new_entry);
if (new_entry)
oldValue = 0;
else
oldValue = (long)Tcl_GetHashValue(he);
//printf("old value = %d", oldValue);
oldValue+=size;
Tcl_SetHashValue(he, oldValue);
}
void
traverse() {
printf("DropHash count = %d\n", count_);
Tcl_HashSearch searchPtr;
Tcl_HashEntry * he = Tcl_FirstHashEntry(hashTable_, &searchPtr);
while (he != NULL) {
char * key = (char *)Tcl_GetHashKey(hashTable_, he);
long value = (long)Tcl_GetHashValue(he);
printf("%s = %ld\n", key, value);
he = Tcl_NextHashEntry(&searchPtr);
}
}
void
reset() {
count_=0;
Tcl_DeleteHashTable(hashTable_);
Tcl_InitHashTable(hashTable_, TCL_STRING_KEYS);
}
};
class PrefixTree {
public:
int countArray[(1 << (NO_BITS+1)) - 1];
PrefixTree();
void reset();
void traverse();
void registerDrop(int address, int size);
static int getLastIndex() {return (1 << (NO_BITS+1)) - 2;}
static int getMaxAddress();
static int getBitI(int address, int i);
static int getIndexFromPrefix(int prefix, int noBits);
static int getIndexFromAddress(int address, int noBits);
static int getPrefixFromIndex(int index);
static int getNoBitsFromIndex(int index);
static int getFirstIndexOfBit(int noBits);
static int getLastIndexOfBit(int noBits);
static int getPrefixBits(int prefix, int noBits);
AggReturn * identifyAggregate(double arrRate, double linkBW);
void insertCluster(cluster * clusterList, int index, int count, int noBits);
void goDownCluster(cluster * clusterList, int index);
void sortCluster(cluster * clusterList, int lastIndex);
void swapCluster(cluster * clusterList, int id1, int id2);
AggReturn * calculateLowerBound();
};
class IdentStruct {
public:
PrefixTree * dstTree_;
PrefixTree * srcTree_;
DropHashTable* dropHash_;
double lowerBound_;
void setLowerBound(double newBound, int averageIt);
AggReturn * calculateLowerBound();
IdentStruct();
void reset();
void traverse();
void registerDrop(Packet *);
static unsigned int getMaxAddress();
static int getBitI(unsigned int, int);
AggReturn * identifyAggregate(double arrRate, double linkBW);
};
#endif
|
