00001 #ifndef ident_tree_h
00002 #define ident_tree_h
00003
00004 #include <stdlib.h>
00005 #include <stdio.h>
00006 #include "address.h"
00007 #include "packet.h"
00008 #include "ip.h"
00009 #include "tcl.h"
00010 #include "math.h"
00011
00012 #include "pushback-constants.h"
00013
00014 class AggSpec;
00015
00016 struct cluster {
00017 int prefix_;
00018 int bits_;
00019 int count_;
00020 };
00021
00022 class AggReturn {
00023 public:
00024 cluster * clusterList_;
00025 double limit_;
00026 int finalIndex_;
00027 int totalCount_;
00028
00029 AggReturn(cluster * clusterList, double bottom, int finalIndex, int totalCount) {
00030 clusterList_ = clusterList;
00031 limit_ = bottom;
00032 finalIndex_ = finalIndex;
00033 totalCount_=totalCount;
00034 }
00035
00036 ~AggReturn() {
00037 free(clusterList_);
00038 }
00039 };
00040
00041 class DropHashTable {
00042
00043 public:
00044 Tcl_HashTable * hashTable_;
00045 int count_;
00046 char key[200];
00047
00048 DropHashTable():count_(0) {
00049 hashTable_ = new Tcl_HashTable;
00050 Tcl_InitHashTable(hashTable_, TCL_STRING_KEYS);
00051 }
00052
00053 void
00054 packetToKey(Packet *p) {
00055 hdr_ip * iph = hdr_ip::access(p);
00056 ns_addr_t src = iph->src();
00057 ns_addr_t dst = iph->dst();
00058 int fid = iph->flowid();
00059 sprintf(key,"%d.%d %d.%d %d",src.addr_, src.port_, dst.addr_, dst.port_, fid);
00060 }
00061
00062 void
00063 insert(Packet *p, int size) {
00064 count_+=size;
00065
00066 int new_entry;
00067 long oldValue;
00068 packetToKey(p);
00069 Tcl_HashEntry* he = Tcl_CreateHashEntry(hashTable_, (char*) key, &new_entry);
00070 if (new_entry)
00071 oldValue = 0;
00072 else
00073 oldValue = (long)Tcl_GetHashValue(he);
00074
00075
00076 oldValue+=size;
00077 Tcl_SetHashValue(he, oldValue);
00078 }
00079
00080 void
00081 traverse() {
00082 printf("DropHash count = %d\n", count_);
00083 Tcl_HashSearch searchPtr;
00084 Tcl_HashEntry * he = Tcl_FirstHashEntry(hashTable_, &searchPtr);
00085 while (he != NULL) {
00086 char * key = Tcl_GetHashKey(hashTable_, he);
00087 long value = (long)Tcl_GetHashValue(he);
00088 printf("%s = %ld\n", key, value);
00089 he = Tcl_NextHashEntry(&searchPtr);
00090 }
00091 }
00092
00093 void
00094 reset() {
00095 count_=0;
00096 Tcl_DeleteHashTable(hashTable_);
00097 Tcl_InitHashTable(hashTable_, TCL_STRING_KEYS);
00098 }
00099
00100 };
00101
00102
00103 class PrefixTree {
00104
00105 public:
00106 int countArray[(1 << (NO_BITS+1)) - 1];
00107
00108 PrefixTree();
00109 void reset();
00110 void traverse();
00111 void registerDrop(int address, int size);
00112
00113 static int getLastIndex() {return (1 << (NO_BITS+1)) - 2;}
00114 static int getMaxAddress();
00115 static int getBitI(int address, int i);
00116 static int getIndexFromPrefix(int prefix, int noBits);
00117 static int getIndexFromAddress(int address, int noBits);
00118 static int getPrefixFromIndex(int index);
00119 static int getNoBitsFromIndex(int index);
00120 static int getFirstIndexOfBit(int noBits);
00121 static int getLastIndexOfBit(int noBits);
00122 static int getPrefixBits(int prefix, int noBits);
00123
00124 AggReturn * identifyAggregate(double arrRate, double linkBW);
00125 void insertCluster(cluster * clusterList, int index, int count, int noBits);
00126 void goDownCluster(cluster * clusterList, int index);
00127 void sortCluster(cluster * clusterList, int lastIndex);
00128 void swapCluster(cluster * clusterList, int id1, int id2);
00129
00130 AggReturn * calculateLowerBound();
00131 };
00132
00133 class IdentStruct {
00134
00135 public:
00136 PrefixTree * dstTree_;
00137 PrefixTree * srcTree_;
00138 DropHashTable* dropHash_;
00139
00140 double lowerBound_;
00141 void setLowerBound(double newBound, int averageIt);
00142 AggReturn * calculateLowerBound();
00143
00144 IdentStruct();
00145
00146 void reset();
00147 void traverse();
00148
00149 void registerDrop(Packet *);
00150
00151 static unsigned int getMaxAddress();
00152 static int getBitI(unsigned int, int);
00153
00154 AggReturn * identifyAggregate(double arrRate, double linkBW);
00155
00156 };
00157
00158 #endif