util.hh
No OneTemporary
Actions

Subscribers

None

File Metadata

Created: Sun, Jul 6, 12:37

util.hh
View Options

	/*
	* Useful headers for Access Networks (ACNE)
	*/

	#ifndef UTIL_HH
	#define UTIL_HH

	//#ifndef __linux__ // this is just a trick for having the code nice in C++ editor (Qt creator)
	//#ifndef CLICK_USERLEVEL
	//#define CLICK_USERLEVEL
	//#endif
	//#ifndef CLICK_LINUXMODULE
	//#define CLICK_LINUXMODULE
	//#endif
	//#endif

	#include <click/element.hh>
	#include <click/string.hh>
	#include <click/vector.hh>
	#include <click/etheraddress.hh>
	#include <click/ipaddress.hh>
	#include <click/hashtable.hh>
	#include <click/integers.hh>
	#include <click/timestamp.hh>
	#include <click/args.hh>
	#include <click/tokenbucket.hh>
	#include <click/error.hh>

	#ifdef CLICK_USERLEVEL
	#include <click/fromfile.hh>
	#include <stdio.h>
	#include<assert.h>
	#include<errno.h>
	#include<ifaddrs.h>
	#include<netdb.h>
	#include<stddef.h>
	#include <string.h>
	#include <time.h>
	#include <unistd.h>

	#ifdef __linux__
	#include <sys/socket.h>
	#include <asm/types.h>

	//NOTE: should add -I/opt/aziala/openWrt_bb/openwrt/staging_dir/target-i386_geode_eglibc-2.19/usr/include/libnl3 to CPPFLAGS in configure.in
	#include <linux/rtnetlink.h>
	#include <netlink/netlink.h>
	#include <netlink/msg.h>
	#include <netlink/cache.h>
	#include <netlink/socket.h>
	#include <netlink/genl/genl.h>
	#include <netlink/genl/ctrl.h>

	#include <stdlib.h>
	#include <linux/nl80211.h>
	#include <net/if.h> // NOTE: incompatibility with linux/if.h, must configure click with --disable-grid
	#endif // __linux__
	#endif //CLICK_USERLEVEL

	#ifdef CLICK_LINUXMODULE
	#include <click/cxxprotect.h>
	CLICK_CXX_PROTECT
	#include <linux/fs.h>
	#include <asm/segment.h>
	#include <asm/uaccess.h>
	#include <linux/kmod.h>
	//#include <linux/buffer_head.h>
	CLICK_CXX_UNPROTECT
	#include <click/cxxunprotect.h>
	#endif //CLICK_LINUXMODULE

	#include <clicknet/wifi.h>
	#include <clicknet/ether.h>
	#include <clicknet/ip.h>
	#include <click/packet_anno.hh>

	#include "hybridMAC.h"
	//#include <assert.h>

	//#include <sstream>

	////////////////////// PROTOCOL PARAMETERS /////////////////////////////////////
	#define HDR_ROUTE_SIZE 6 //Size in #Hops of a route in the header. Byte size is HDR_ROUTE_SIZE*NB_BYTES_HOP
	#define NB_BYTES_HOP 2 //nb of Bytes that describe a hop. default: 2 last bytes of MAC
	#define INITIAL_ROUTE_RATE 10240u //default sending rate in kbps
	#define ROUTE_TIMEOUT 10 //time in sec after which a route rate reach timeout when not used
	#define DEFAULT_WEIGHT 10000u
	//#define ACK_PERIOD_MS 100u //time in ms between acks at dst
	#define PROTO_IP_TEST 157
	#define MIN_SENDING_RATE 125000u // send at least 125000 B/s (1Mb/s)
	#define UINT32_MAX (0xffffffff)
	#define BEGIN_DURATION 820
	#define AGGRESSIVE_ALPHA 0.2



	///////////////////// ALGORITHM PARAMETERS /////////////////////////////////////
	//#define ALPHA 0.2 //momentum ratio in the derivation of the rate. (1-alpha) is the proportion of the ratio that is inherited from the previous state. increase this in case of oscillatory behavior between routes

	///////////////////// MAXIMUM SEQUENCE NUMBER /////////////////////////////////
	#define MAX_SEQ 65535u // to be changed if the size of the field _seq of the acne header changes



	CLICK_DECLS


	///////////////////////////////////////////////// STATIC FUNCTIONS /////////////////////////////////////////////////


	template<typename T>
	static const T mymin(T a, T b) {
	if(a<=b)
	return a;
	else
	return b;
	}

	template<typename T>
	static const T mymax(T a, T b) {
	if(a>=b)
	return a;
	else
	return b;
	}

	template<typename T>
	static const T myabs(T a) {
	if(a>=0)
	return a;
	else
	return -a;
	}

	static const uint16_t dist_mod_maxseq( uint16_t a, uint16_t b ) {
	uint32_t a32 = (uint32_t) a;
	uint32_t b32 = (uint32_t) b;
	uint32_t diff = (MAX_SEQ+a32-b32)% MAX_SEQ;
	return diff <= MAX_SEQ/2 ? diff : MAX_SEQ-diff;
	}

	template<typename T>
	static bool equals_vector(Vector<T> a, Vector<T> b) {
	if(a.size() == b.size()) {
	for(int i=0;i<a.size();i++) {
	if(a[i] != b[i]) {
	return false;
	}
	}
	return true;
	}
	else {
	return false;
	}
	}

	template<typename T>
	static bool equals_set(Vector<T> a, Vector<T> b) {
	if(a.size() != b.size())
	return false;
	for(int i=0;i<a.size();i++) {
	if(!is_in_vector(b,a[i])) {
	return false;
	}
	if(!is_in_vector(a,b[i])) {
	return false;
	}
	}
	return true;

	}

	template<typename T>
	static bool equals_vector(Vector<Vector<T> > a, Vector<Vector<T> > b) {
	if(a.size() == b.size()) {
	for(int i=0;i<a.size();i++) {
	if(!equals_vector(a[i], b[i])) {
	return false;
	}
	}
	return true;
	}
	else {
	return false;
	}
	}



	template<typename T>
	static int find_in_vector(const Vector<T> vec, const T element) {
	for (int i=0;i<vec.size();i++) {
	if (element == vec[i]) {
	return i;
	}
	}
	return -1;
	}

	template<typename T>
	static int find_in_vector(const Vector<Vector<T> > vec, const Vector<T> element) {
	for (int i=0;i<vec.size();i++) {
	if (equals_vector(element, vec[i])) {
	return i;
	}
	}
	return -1;
	}

	template<typename T>
	static Vector<T> sub_vec(Vector<T> vec, Vector<int> ind) {
	Vector<T> res;
	for (int i=0;i<ind.size();i++)
	res.push_back(vec[ind[i]]);
	return res;
	}

	template<typename T>
	static bool is_in_vector(const Vector<Vector<T> > vec, const Vector<T> element) {
	return (find_in_vector(vec, element) != -1);
	}

	template<typename T>
	static bool is_in_vector(const Vector<T> vec, const T element) {
	return (find_in_vector(vec, element) != -1);
	}

	template<typename T>
	static bool is_in_vector(const Vector<Vector<T> > vec, const T element) {
	for(int i=0;i<vec.size();i++) {
	for(int j=0;j<vec[i].size();j++) {
	if (vec[i][j] == element)
	return true;
	}
	}
	return false;
	}


	template<typename T>
	static bool is_in_hash_table(const HashTable<T,int> table, const T element) {
	const int *ptr = table.get_pointer(element);
	return ptr!=0;
	}

	template<typename T>
	static bool is_in_hash_table(const HashTable<T,float> table, const T element) {
	const float *ptr = table.get_pointer(element);
	return ptr!=0;
	}

	template<typename T>
	static bool is_in_hash_table(const HashTable<T,double> table, const T element) {
	const double *ptr = table.get_pointer(element);
	return ptr!=0;
	}

	template<typename T>
	static bool is_in_hash_table(const HashTable<T,uint32_t> table, const T element) {
	const uint32_t *ptr = table.get_pointer(element);
	return ptr!=0;
	}

	template<typename T>
	static bool is_in_hash_table(const HashTable<T,uint16_t> table, const T element) {
	const uint16_t *ptr = table.get_pointer(element);
	return ptr!=0;
	}

	template<typename T>
	static bool is_in_hash_table(const HashTable<T,uint8_t> table, const T element) {
	const uint8_t *ptr = table.get_pointer(element);
	return ptr!=0;
	}

	template<typename T>
	static bool is_in_hash_table(const HashTable<T,bool> table, const T element) {
	const bool *ptr = table.get_pointer(element);
	return ptr!=0;
	}

	template<typename T, typename V>
	static bool is_in_hash_table(const HashTable<T,V> table, const T element) {
	const V val = table.get(element);
	return val!=V();
	}


	template<typename T, typename V>
	static bool is_in_hash_table(const HashTable<T,Vector<V> > table, const T element) {
	const Vector<V> val = table.get(element);
	return !val.empty();
	}

	template<typename T1, typename T2, typename V>
	static bool is_in_hash_table(const HashTable<T1,HashTable<T2,V> > table, const T1 element) {
	const HashTable<T2,V> val = table.get(element);
	return !val.empty();
	}



	static const String print_vector(const Vector<int> vec) {
	String s="";
	for(int i=0;i<vec.size();i++) {
	s+=String(vec[i]);
	if(i!=(vec.size()-1))
	s+=" ";
	}
	return s;
	}

	static const String print_vector(const Vector<uint64_t> vec) {
	String s="";
	for(int i=0;i<vec.size();i++) {
	s+=String(vec[i]);
	if(i!=(vec.size()-1))
	s+=" ";
	}
	return s;
	}

	static const String print_vector(const Vector<uint32_t> vec) {
	String s="";
	for(int i=0;i<vec.size();i++) {
	s+=String(vec[i]);
	if(i!=(vec.size()-1))
	s+=" ";
	}
	return s;
	}

	static const String print_vector(const Vector<uint16_t> vec) {
	String s="";
	for(int i=0;i<vec.size();i++) {
	s+=String(vec[i]);
	if(i!=(vec.size()-1))
	s+=" ";
	}
	return s;
	}

	template<typename T>
	static const String print_vector(const Vector<T> vec) {
	String s="";
	for(int i=0;i<vec.size();i++) {
	s+=vec[i].unparse();
	if(i!=(vec.size()-1))
	s+=" ";
	}
	return s;
	}

	static const String print_sparse_vector(const Vector<uint32_t> vec) {
	String s="";
	for(int i=0;i<vec.size();i++) {
	if(vec[i] > 0) {
	s+=String(i)+":"+String(vec[i]);
	s+=",";
	}
	}
	if(s=="")
	return s;
	return s.substring(0,s.length()-1);
	}

	static const String print_sparse_vector(const Vector<int> vec) {
	String s="";
	for(int i=0;i<vec.size();i++) {
	if(vec[i] > 0) {
	s+=String(i)+":"+String(vec[i]);
	s+=",";
	}
	}
	if(s=="")
	return s;
	return s.substring(0,s.length()-1);
	}


	static Vector<String> parse_string(String s, String del) {
	int ind;
	Vector<String> result;
	while((ind=s.find_left(del)) >= 0) {
	if (ind>0) {
	result.push_back(s.substring(0,ind));
	}
	s=s.substring(ind+del.length());
	}

	if(s.length() >= 1) {
	if((ind = s.find_left('\n')) != -1) {
	if(ind>0)
	result.push_back(s.substring(0,ind)); // we need to strip the end line \n
	}
	else
	result.push_back(s);
	}

	return result;
	}

	static uint64_t usec_timestamp(Timestamp t) {
	return (t.sec()*1000000 + t.usec());
	}



	template<typename T>
	static Vector<T> concat_vectors(Vector<T> first, Vector<T> last) {
	Vector<T> total = first;
	for (int i=0;i<last.size();i++)
	total.push_back(last[i]);

	return total;
	}

	static int find_min(Vector<uint32_t> vec) {
	uint32_t min_loc = UINT_MAX;
	int ind_min = -1;

	for (int i=0;i<vec.size();i++) {
	if (vec[i] < min_loc) {
	min_loc = vec[i];
	ind_min = i;
	}
	}

	return ind_min;
	}

	template<typename T>
	static bool add_in_vector_unique(Vector<T> &vec, T a) {
	if (!is_in_vector(vec, a)) {
	vec.push_back(a);
	return true;
	}
	return false;
	}

	template<typename T>
	static bool insert_in_sorted_descent_vector(Vector<T> &vec, T a) {
	for(typename Vector<T>::iterator it=vec.begin();it != vec.end();++it) {
	if(a > *it) {
	vec.insert(it,a);
	return true;
	}
	else if(!(a < *it)) {
	if(a!=*it) {
	vec.insert(it,a);
	return true;
	}
	return false;
	}
	}
	assert(vec.size() == 0 \|\| (!vec.empty() && a < vec[vec.size()-1]));
	vec.push_back(a);
	return true;
	}

	#ifdef CLICK_LINUXMODULE
	static struct file* file_open(const char* path, int flags, int rights) {
	struct file* filp = NULL;
	mm_segment_t oldfs;
	int err = 0;

	oldfs = get_fs();
	set_fs(get_ds());
	filp = filp_open(path, flags, rights);
	set_fs(oldfs);
	if(IS_ERR(filp)) {
	err = PTR_ERR(filp);
	return NULL;
	}
	return filp;
	}

	static void file_close(struct file* file) {
	filp_close(file, NULL);
	}

	static int file_read(struct file* file, unsigned long long offset, unsigned char* data, unsigned int size) {
	mm_segment_t oldfs;
	int ret;

	oldfs = get_fs();
	set_fs(get_ds());

	ret = vfs_read(file, data, size, &offset);

	set_fs(oldfs);
	return ret;
	}
	#endif

	static String exec(char* cmd) {
	String result = "";
	#ifdef CLICK_USERLEVEL
	FILE* pipe = popen(cmd, "r");
	if (!pipe) return "ERROR";
	char buffer[128];
	while(!feof(pipe)) {
	if(fgets(buffer, 128, pipe) != NULL)
	result += buffer;
	}
	pclose(pipe);
	#else
	char * envp[] = { "HOME=/", NULL };
	char *argv[] = { "/bin/bash", "-c", (String(cmd)+String("> /tmp/cmd.tmp")).data(), NULL};
	call_usermodehelper(argv[0], argv, envp, UMH_WAIT_EXEC);
	struct file *filp = file_open("/tmp/cmd.tmp", O_RDONLY, 0);
	char buffer[128];
	int data_read;
	int offset=0;
	while((data_read=file_read(filp, offset, buffer, sizeof(buffer))) > 0) {
	result += buffer;
	offset += data_read;
	}
	file_close(filp);
	#endif
	return result;
	}

	#ifdef CLICK_USERLEVEL
	static String exec_file(const char* cmd, ErrorHandler *errh) {
	String cmd_str = String(cmd);
	cmd_str += " > /tmp/click_exec_output.log";
	system(cmd_str.c_str());
	FromFile ff = FromFile();
	if (!FilenameArg().parse("/tmp/click_exec_output.log", ff.filename()))
	return "ERROR";
	if(ff.initialize(errh) < 0)
	return "ERROR";
	String result = "";
	String line;
	while(1) {
	if (ff.read_line(line, errh, true) <= 0) {
	break;
	}
	result+=line;
	}
	return result;
	}
	#endif

	static String print_last_byte(EtherAddress eth) {
	String str = String::make_garbage(2);
	if (char *x = str.mutable_c_str()) {
	const unsigned char *p = eth.data();
	sprintf(x, "%02X", p[5]);
	}
	return str;
	}

	template<typename T>
	static bool is_vector_min(Vector<T> vec1, Vector<T> vec2) {
	if(vec1.size()!=vec2.size()) {
	click_chatter("util.hh::is_vector_min called with different size vectors");
	return false;
	}
	for(int i=0;i<vec1.size();i++) {
	if(vec1[i] > vec2[i])
	return false;
	}
	return true;
	}

	template<typename T>
	Vector<T> insertion_sort(const Vector<T> vec)
	{
	int length = vec.size();

	Vector<T> copy = Vector<T>(vec);

	for (int i = 1; i < length; ++i)
	{
	bool inplace = true;
	int j = 0;
	for (; j < i; ++j)
	{
	if (copy[i] < copy[j])
	{
	inplace = false;
	break;
	}
	}

	if (!inplace)
	{
	T save = copy[i];
	for (int k = i; k > j; --k)
	{
	copy[k] = copy[k-1];
	}
	copy[j] = save;
	}
	}

	return copy;
	}

	template<typename T>
	T vector_sum(const Vector<T> vec) {
	T sum = 0;
	for(int i=0;i<vec.size();i++)
	sum+=vec[i];
	return sum;
	}


	extern HashTable<EtherAddress, bool> _wifi_addresses_static;
	extern void set_wifi_addr(EtherAddress addr);
	extern bool is_wifi_addr(EtherAddress addr);


	extern HashTable<EtherAddress, bool> _plc_addresses_static;
	extern void set_plc_addr(EtherAddress addr);
	extern bool is_plc_addr(EtherAddress addr);


	#ifndef DEFINE_POWER_UINT32
	#define DEFINE_POWER_UINT32
	static uint64_t power(uint32_t x, uint32_t n) {
	uint64_t res = 1;
	uint64_t a = x;
	while (n) {
	if (n & 1)
	res *= a;
	a *= a;
	n >>= 1;
	}
	return res;
	}
	#endif

	static uint32_t log10(uint64_t v) {
	uint32_t r = (v >= 1000000000000000000) ? 18 : (v >= 100000000000000000) ? 17 :
	(v >= 10000000000000000) ? 16 : (v >= 1000000000000000) ? 15 : (v >= 100000000000000) ? 14 :
	(v >= 10000000000000) ? 13 : (v >= 1000000000000) ? 12 : (v >= 100000000000) ? 11 :
	(v >= 10000000000) ? 10 : (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 :
	(v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 :
	(v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0;

	return r;
	}

	static int64_t int64_divide(int64_t a, int64_t b) {
	int64_t num = a;
	int64_t den = b; // will need to be uint32_t at the end
	if(den<0) {
	num = -num;
	den = -den;
	}
	// den is > 0 here
	if(den > UINT32_MAX) {
	// approximate den by multiplication of two uint32
	uint64_t den1 = power(10,log10((uint64_t)den)/2);
	uint32_t den1_32 = (uint32_t) den1;
	if( ((uint64_t) den1_32) != den1) {
	click_chatter("WARNING: ((uint64_t) den1_32) != den1 in uint64_divide, den1_32=%s,(uint64_t) den1_32=%s, den1=%s",
	String(den1_32).c_str(),String((uint64_t)den1_32).c_str(),String(den1).c_str());
	return 0;
	}
	uint64_t den2 = int_divide((uint64_t)den, den1_32);
	uint32_t den2_32 = (uint32_t) den2;
	if( ((uint64_t) den2_32) != den2) {
	click_chatter("WARNING: ((uint64_t) den2_32) != den2 in uint64_divide, den2_32=%s,(uint64_t) den2_32=%s, den2=%s",
	String(den2_32).c_str(),String((uint64_t)den2_32).c_str(),String(den2).c_str());
	return 0;
	}
	int64_t temp_div = int_divide(num, den1_32);
	return int_divide(temp_div, den2_32);
	}
	else {
	uint32_t den_32 = (uint32_t) den;
	assert( ((int64_t) den_32) == den );
	return int_divide(num, (uint32_t) den);
	}

	}

	static uint64_t uint64_divide(uint64_t num, uint64_t den) {
	if(den > UINT32_MAX) {
	// approximate den by multiplication of two uint32
	uint64_t den1 = power(10,log10(den)/2);
	uint32_t den1_32 = (uint32_t) den1;
	if( ((uint64_t) den1_32) != den1) {
	click_chatter("WARNING: ((uint64_t) den1_32) != den1 in uint64_divide, den1_32=%s,(uint64_t) den1_32=%s, den1=%s",
	String(den1_32).c_str(),String((uint64_t)den1_32).c_str(),String(den1).c_str());
	return 0;
	}
	uint64_t den2 = int_divide(den, den1_32);
	uint32_t den2_32 = (uint32_t) den2;
	if( ((uint64_t) den2_32) != den2) {
	click_chatter("WARNING: ((uint64_t) den2_32) != den2 in uint64_divide, den2_32=%s,(uint64_t) den2_32=%s, den2=%s",
	String(den2_32).c_str(),String((uint64_t)den2_32).c_str(),String(den2).c_str());
	return 0;
	}
	uint64_t temp_div = int_divide(num, den1_32);
	return int_divide(temp_div, den2_32);
	}
	else {
	uint32_t den_32 = (uint32_t) den;
	assert( ((uint64_t) den_32) == den );
	return int_divide(num, den_32);
	}
	}



	static uint32_t log2(uint64_t v) {
	const unsigned long long b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000};
	const unsigned int S[] = {1, 2, 4, 8, 16, 32};
	int i;

	register unsigned int r = 0; // result of log2(v) will go here
	for (i = 5; i >= 0; i--) // unroll for speed...
	{
	if (v & b[i])
	{
	v >>= S[i];
	r \|= S[i];
	}
	}

	return r;
	}



	static uint32_t logE(uint64_t v) {
	uint64_t lp2 = log2(power(v,2));
	uint32_t r = (uint32_t) int_divide(1000000lp2,21442695); // log2(e) = 1.442695

	return r;
	}













	///////////////////////////////////////////////// OBJECTS /////////////////////////////////////////////////




	/*
	* This class describes an object that desires
	* to be notified by Neighbors when a change occurs in the
	* neighborhood. The function neighborsChanged() must
	* be overriden. It will be called upon a change
	* (without any argument).
	*/
	class NeighborsListener
	{
	public:
	virtual ~NeighborsListener() {}
	virtual void neighborsChanged() = 0;
	};


	struct LinkRouting {
	EtherAddress src;
	EtherAddress dst;
	uint32_t weight;

	LinkRouting() {}

	LinkRouting(EtherAddress _src, EtherAddress _dst, uint32_t _weight) {
	src = _src;
	dst = _dst;
	weight = _weight;
	}

	String unparse() const {
	String s="(";
	s+=src.unparse();
	s+=">";
	s+=dst.unparse();
	s+=";";
	s+=String(weight);
	s+=")";
	return s;
	}
	/*
	*Bernard : get the NB_BYTES_HOP (2) last bytes of this link for both src & dst
	* @return a table of 2*NB_BYTES_HOP (4) Bytes containing the src & dst addr.
	*/
	void unparseByteVal(unsigned char* byteRoute) const {
	//unsigned char* byteRoute = new unsigned char[2*NB_BYTES_HOP];
	// for (int i =0;i<NB_BYTES_HOP;++i){
	// byteRoute[i]= (src.data())[6-NB_BYTES_HOP+i];
	// }
	for (int i =0;i<NB_BYTES_HOP;++i){
	byteRoute[NB_BYTES_HOP+i]= (dst.data())[6-NB_BYTES_HOP+i];
	}
	//return byteRoute;
	}

	inline bool operator==(const LinkRouting a) const
	{
	return (a.src == src && a.dst == dst);
	}

	inline bool operator!=(const LinkRouting a) const
	{
	return (a.src != src \|\| a.dst != dst);
	}

	inline uint32_t hashcode() const {
	return src.hashcode()+dst.hashcode();
	}

	inline bool operator>(const LinkRouting a) const
	{
	return (a!=*this && this->hashcode() > a.hashcode());
	}

	LinkRouting reverse() {
	return LinkRouting(dst, src, weight);
	}
	};


	struct UndirectedLinkRouting {
	EtherAddress src;
	EtherAddress dst;
	Timestamp last_update;

	UndirectedLinkRouting() {
	}

	UndirectedLinkRouting(EtherAddress _src, EtherAddress _dst) {
	src = _src;
	dst = _dst;
	}

	UndirectedLinkRouting(LinkRouting a) {
	src = a.src;
	dst = a.dst;
	}

	String unparse() const {
	String s="(";
	s+=src.unparse();
	s+=">";
	s+=dst.unparse();
	s+=")";
	return s;
	}


	inline bool operator==(const UndirectedLinkRouting a) const
	{
	return ((a.src == src && a.dst == dst) \|\|
	(a.src == dst && a.dst == src));
	}

	inline bool operator!=(const UndirectedLinkRouting a) const
	{
	return !((a.src == src && a.dst == dst) \|\|
	(a.src == dst && a.dst == src));
	}

	inline uint32_t hashcode() const {
	return src.hashcode()+dst.hashcode();
	}
	};

	/**
	* Route abstraction
	*/
	struct Route {
	Vector<LinkRouting> links;
	uint32_t weight;
	IPAddress ip;
	uint32_t max_capa; // kb/s
	uint32_t max_capa_alone; // kb/s

	Route() {
	links = Vector<LinkRouting>();
	weight = 0;
	}

	int is_in_route_src(EtherAddress eth) {
	for (int i=0;i<links.size();i++) {
	if (links[i].src == eth)
	return i;
	}
	return -1;
	}

	inline bool operator==(const Route a) const
	{
	return equals_vector(links, a.links);
	}

	inline bool operator!=(const Route a) const
	{
	return !(equals_vector(links, a.links));
	}

	inline bool operator<(const Route a) const
	{
	return (max_capa < a.max_capa);
	}

	inline bool operator>(const Route a) const
	{
	return (max_capa > a.max_capa);
	}

	inline uint32_t hashcode() const {
	uint32_t hash = 0;
	for(int i=0;i<links.size();i++)
	hash+=links[i].hashcode();
	return hash;
	}

	String unparse() const {
	String s;
	s+=print_vector(links);
	s+=", weight ";
	s+=String(weight);
	s+=", capacity ";
	s+=String(max_capa);
	s+="/";
	s+=String(max_capa_alone);
	return s;
	}

	Route reverse_route() {
	Route reversed_route;
	for (int i=(links.size()-1);i>=0;i--)
	reversed_route.links.push_back(links[i].reverse());
	reversed_route.weight = weight;
	reversed_route.max_capa = max_capa;
	reversed_route.max_capa_alone = max_capa_alone;
	return reversed_route;
	}

	};


	/**
	* The route, as transmitted in the headers and stored in the table
	*/
	struct FormatedRoute {
	// the route consists in last bytes of all the hops
	unsigned char _route[HDR_ROUTE_SIZE*NB_BYTES_HOP];

	//the last bytes of the mac addr of the source (we need it to send the ACKs)
	unsigned char _src[NB_BYTES_HOP];

	// the last bytes of the mac address of the destination
	unsigned char _dst[NB_BYTES_HOP];
	//uint8_t _route_length;

	FormatedRoute() {
	memset(this,0,sizeof(FormatedRoute));
	// for(uint8_t i=0; i<HDR_ROUTE_SIZE; i++) {
	// for(uint8_t b=0; b<NB_BYTES_HOP; b++){
	// _route[NB_BYTES_HOP*i+b] = 0;
	// }
	// }
	// for(uint8_t i=0; i<NB_BYTES_HOP; i++){
	// _src[i] = 0;
	// _dst[i] = 0;
	// }
	}

	/**
	* ctor : creates FormatedRoute from Route object
	*
	**/
	FormatedRoute(Route const &r){
	uint32_t route_length = r.links.size();
	for(uint8_t i=0; i<HDR_ROUTE_SIZE; i++) {
	if(i<route_length){
	unsigned char data = (unsigned char )r.links[i].dst.data();
	for(uint8_t b=0; b<NB_BYTES_HOP; b++){
	_route[NB_BYTES_HOP*i+b] = data[6-NB_BYTES_HOP+b];
	}
	} else {
	for(uint8_t b=0; b<NB_BYTES_HOP; b++){
	_route[NB_BYTES_HOP*i+b] = 0;
	}
	}
	}
	EtherAddress src;
	EtherAddress dst;
	if(route_length > 0) {
	src = r.links.front().src;
	dst = r.links.back().dst;
	}
	for(uint8_t i=0; i<NB_BYTES_HOP; i++){
	_src[i] = src.data()[6-NB_BYTES_HOP+i];
	_dst[i] = dst.data()[6-NB_BYTES_HOP+i];
	}
	}


	bool is_one_hop() {
	// is one hop if second hop in route is 0
	for(uint8_t b=0; b<NB_BYTES_HOP; b++){
	if(_route[NB_BYTES_HOP + b] != 0)
	return false;
	}
	return true;
	}

	int number_hops() {
	int nb_hops = 0;
	for(int i=0;i<HDR_ROUTE_SIZE;i++) {
	bool cont = false;
	for(uint8_t b=0; b<NB_BYTES_HOP; b++){
	if(_route[i*NB_BYTES_HOP + b] != 0) {
	nb_hops++;
	cont = true;
	break;
	}
	}
	if(!cont)
	return nb_hops;
	}
	return nb_hops;
	}

	/**
	* Checks equality. Two FormatedRoute objects are equal iff all their bytes are equal
	*/
	inline bool operator==(FormatedRoute const& a) const {

	if(_src[0] != a._src[0] \|\| _src[1] != a._src[1])
	return false;
	for (int i = 0; i<HDR_ROUTE_SIZE*NB_BYTES_HOP; ++i) {
	if ( a._route[i] != _route[i]) {
	return false;
	}
	}
	return true;
	}

	inline bool operator!=(FormatedRoute const& a) const {
	if(_src[0] != a._src[0] \|\| _src[1] != a._src[1])
	return true;
	for (int i = 0; i<HDR_ROUTE_SIZE*NB_BYTES_HOP; ++i) {
	if ( a._route[i] != _route[i]) {
	return true;
	}
	}
	return false;
	}

	String unparse() const {
	String str;
	String s_src = String::make_garbage(4);
	const unsigned char *p = _src;
	if (char *x = s_src.mutable_c_str()) {
	sprintf(x, "%02X%02X", p[0], p[1]);
	}
	str = ("("+s_src+":)");
	for(int i=0;i<HDR_ROUTE_SIZE;i++) {
	String s = String::make_garbage(4);
	const unsigned char *p = _route;
	if(p[iNB_BYTES_HOP] > 0 && p[(iNB_BYTES_HOP)+1] > 0) {
	if (char *x = s.mutable_c_str()) {
	sprintf(x, "%02X%02X", p[iNB_BYTES_HOP], p[(iNB_BYTES_HOP)+1]);
	}
	}
	else {
	if(i==0)
	return "empty";
	return str;
	}
	if(i==0)
	str+=s;
	else
	str+=(":"+s);

	}
	return str;
	}

	inline size_t hashcode() const {
	/uint32_t ptr1 = (uint32_t*)_route;
	uint32_t ptr2 = (uint32_t)(&_route[4]);
	uint32_t ptr3 = (uint32_t)(&_route[8]);
	return (size_t)(ptr1 \| ptr2 \| ptr3);/
	return ( ((size_t)_route[1]) \| ((size_t) _route[3] << 8))
	\| ((size_t) _route[5] << 16 \| ((size_t) _route[7] << 24))
	\| ((size_t) _route[9] << 12 \| ((size_t)_route[11] << 20)) \|
	((size_t) _src[0] << 4 \| ((size_t)_src[1] << 6));
	}
	};

	struct FlowTuple {
	IPAddress _src;
	IPAddress _dst;

	uint16_t _sport;
	uint16_t _dport;

	// local information (uses WiFi and/or PLC)
	bool _uses_int1_loc;
	bool _uses_int2_loc;

	FlowTuple() {
	_uses_int1_loc = false;
	_uses_int2_loc = false;
	}

	FlowTuple(IPAddress src, IPAddress dst) {
	_src = src;
	_dst = dst;
	_sport = 0;
	_dport = 0;
	}

	FlowTuple(IPAddress src, IPAddress dst, uint16_t sport, uint16_t dport) {
	_src = src;
	_dst = dst;
	_sport = sport;
	_dport = dport;
	}

	void set_addresses(IPAddress src, IPAddress dst) {
	_src = src;
	_dst = dst;
	}

	void set_int1_use(bool b) {
	_uses_int1_loc = b;
	}

	void set_int2_use(bool b) {
	_uses_int2_loc = b;
	}

	inline bool operator==(const FlowTuple a) const
	{
	return _src == a._src && _dst == a._dst && _sport == a._sport && _dport == a._dport;
	}

	inline bool operator!=(const FlowTuple a) const
	{
	return _src != a._src \|\| _dst != a._dst \|\| _sport != a._sport \|\| _dport != a._dport;
	}

	String unparse() const {
	return (_src.unparse()+":"+String(_sport)+"->"+_dst.unparse()+":"+String(_dport));
	}

	inline size_t hashcode() const {
	return unparse().hashcode();
	}


	};

	/*
	* The header of our 2.5 layer. Get the length using sizeof(acne_header)
	* The multiflow dispatcher currently relies on the fact that the route is a 12-byte array one byte after the beginning of the header.
	*/
	struct acne_header {

	#define ETHERTYPE_ACNE 0x08FA

	#define REGULAR_TRAFFIC 0
	#define ROUTING_CTRL 1
	#define ACK_RTE_PRICES 2
	#define INT2_LOAD_NBOR 3
	#define INT1_LOAD_NBOR 4
	#define HELLO_INT2 5
	#define HELLO_INT1 6
	#define EMPTY_FRAME 7
	#define MAB_ACK 8
	#define MAB_CONTROL 9
	#define SPECIAL_TRAFFIC 10
	#define TRAFFIC_FORCED 11 // for packets that should not be blocked by any element (ie MFLB)
	#define DUMMY_TRAFFIC_MAB 12
	#define FLOW_BROADCAST_INT1 13
	#define FLOW_BROADCAST_INT2 14
	#define NACK_ORDER 15
	#define NACK_RETRANSMISSION 16

	//0: regular IP traffic, 1: routing control, 2: ACK (route prices), 3: plc load neighbor, 4: wifi load neighbor, 5 HELLO (plc), 6 HELLO (wifi)
	uint8_t _type;

	//route data, use last NB_BYTES_HOP Bytes of each route (also contains destination)
	FormatedRoute _route;

	//the current route price qr along the path (=SUM(r:r in l){x_r*d_l})
	#ifdef CLICK_USERLEVEL
	float _route_price;
	#else
	uint32_t _route_price;
	#endif

	uint32_t _rate_demand;

	//for reordering at dst
	uint16_t _seq;
	uint16_t _previous_seq_route;

	//curent hop counter
	uint8_t _hop;

	Timestamp _ts;


	// fields for aggregation of control packets
	//uint16_t _seq_aggreg;
	//uint32_t _length;

	// id that changes when rate sent changes (for Mab)
	uint16_t _id_rate_mab;
	bool _is_last = false; // if last packet of a burst (force burst to be sent)
	};

	struct hello_pkt{
	EtherAddress src_addr;
	EtherAddress plc_chip_addr;
	//uint16_t seq_num;
	};

	struct nack_order{
	IPAddress flow_src_addr;
	IPAddress flow_dst_addr;

	uint16_t last_seq;

	int nb_nacks;
	uint16_t nacks[];
	};


	/**
	* The acne ACK packet containing the computed path along a route.
	* This is a payload (it comes with an ACNE header)
	*/
	struct acne_ack{
	//the target route for which the rate applies0
	FormatedRoute _target_route;

	// used to stop flow with CountBytes
	FlowTuple _flow;
	bool _stop_flow;

	//route price
	#ifdef CLICK_USERLEVEL
	float _route_price;
	#else
	uint32_t _route_price; //this is qr
	#endif
	};


	#ifdef CLICK_USERLEVEL
	typedef float gamma_type;
	#define GAMMA_SCALE 1000
	// saturated threshold (value after which a link is considered saturated)
	#define SATURATED_THRES 1000
	#else
	typedef int gamma_type;
	#define GAMMA_SCALE 1000
	// saturated threshold (value after which a link is considered saturated)
	#define SATURATED_THRES 1000
	#endif

	/**
	* The Mab ACK packet containing the computed path along a route.
	*/
	struct mab_ack{
	//the target route for which the gammas apply
	FormatedRoute _target_route;

	IPAddress _dst;

	IPAddress _flow_src;
	IPAddress _flow_dst;

	//route rate
	uint32_t _route_rate; //B/s

	uint8_t _max_nb_flows;

	int8_t _current_index_in_route;

	Timestamp _ctrl_id; // serve to identify which CTRL it responds to

	//field for flow hash
	uint32_t _flow_hash;

	//field for gammas
	gamma_type _gammas[HDR_ROUTE_SIZE];



	};




	/**
	* Mab control packet
	*/
	struct mab_control {
	#define MAB_CTRL_BEGIN 0u // begin of a trial (useful to get timestamp)
	#define MAB_CTRL_END 1u // to trigger computation of busy time, and ack at destination
	#define FLOW_INFORMATION 2u // send control message to get info on the flow
	#define TRIGGER_CLEAR 3u // to trigger clearing of queues before an exploration slot

	uint8_t _type;
	Timestamp _ts;
	IPAddress _flow_src;
	IPAddress _flow_dst;
	bool _first_message;
	uint8_t _nb_missing_acks;
	uint8_t _max_nb_flows;
	uint32_t _flow_hash;
	uint16_t _missing_acks[];
	};


	/**
	* Structure for broadcasting flow information
	*/

	struct flow_broadcast{
	//the target route for which the gammas apply
	IPAddress _src;

	uint8_t _interface;
	uint32_t _new_flow;
	uint8_t _nb_flow_ids;

	//fields for flow ids (hashs)
	uint32_t _flow_ids[];

	};




	struct test_time_header {
	Timestamp _ts_cc;
	Timestamp _ts_fwd;
	Timestamp _ts_mfl;
	Timestamp _ts_price;
	Timestamp _ts_queue;
	Timestamp _ts_out;
	};


	/**
	* The rates elements in Cc's rate table, maintained at each node
	*/
	struct rateTuple_entry{
	uint32_t _rate; //in kbps
	uint32_t _moment;
	uint32_t _timeout; //since when we didn't hear an ACK
	int _no_traffic ; // keep track of number of slots no traffic sent (remove route after some time)
	Timestamp _last_sent;
	bool _incr_timeout;

	rateTuple_entry() {
	}

	inline bool operator==(const rateTuple_entry& a) const
	{
	return (a._rate == _rate && a._moment == _moment && a._timeout==_timeout);
	}

	inline bool operator!=(const rateTuple_entry& a) const
	{
	return (a._rate != _rate \|\| a._moment != _moment \|\| a._timeout!=_timeout);
	}
	};

	static bool are_last_bytes_in_addr(unsigned char *data, EtherAddress addr){
	const unsigned char *data_addr = addr.data();
	for(uint8_t b=0; b<NB_BYTES_HOP; b++) {
	if (data[b] != data_addr[6-NB_BYTES_HOP+b])
	return false;
	}
	return true;
	};

	struct LastAddrBytes {
	//used by neighbors, as key for quick mapping
	//stores a hash of last bytes (unique for up to 4 bytes)

	unsigned char _lastbytes[NB_BYTES_HOP];
	uint32_t hash;

	LastAddrBytes() {

	}

	LastAddrBytes(EtherAddress addr) {
	for(uint8_t i=0; i<NB_BYTES_HOP; i++){
	_lastbytes[i] = addr.data()[6-NB_BYTES_HOP+i];
	}
	set_hash();
	}

	LastAddrBytes(unsigned char *bytes) {
	for(uint8_t i=0; i<NB_BYTES_HOP; i++){
	_lastbytes[i] = bytes[i];
	}
	set_hash();
	}

	inline bool operator==(const LastAddrBytes a) const {
	//iterate from the end, should be faster in case of false
	for(uint8_t iter=0; iter<NB_BYTES_HOP; ++iter) {
	if (_lastbytes[NB_BYTES_HOP-iter-1] != a._lastbytes[NB_BYTES_HOP-iter-1])
	return false;
	}
	return true;
	}
	inline bool operator!=(const LastAddrBytes a) const {
	//iterate from the end, should be faster in case of true
	for(uint8_t iter=0; iter<NB_BYTES_HOP; ++iter) {
	if (_lastbytes[NB_BYTES_HOP-iter-1] != a._lastbytes[NB_BYTES_HOP-iter-1])
	return true;
	}
	return false;
	}
	inline uint32_t hashcode() const {
	return hash;
	}
	void set_hash(){
	//simple hash that care about up to 4 bytes (without collision)
	hash = 0;
	for(uint8_t iter=0; iter<NB_BYTES_HOP; ++iter){
	if(iter < 4){
	hash += _lastbytes[iter] << (8*iter);
	}
	}
	}
	String unparse() const {
	String str;
	for(uint8_t iter=0; iter<NB_BYTES_HOP; ++iter) {
	String byte_str = String::make_garbage(2);
	if (char *x = byte_str.mutable_c_str())
	sprintf(x, "%02X",_lastbytes[iter]);
	str+=byte_str;
	}
	return str;
	}
	};


	struct NodeRouting {
	IPAddress ip;
	Timestamp last_time_seen_node;
	Vector<EtherAddress> interfaces;
	Vector<bool> is_wifi;
	Vector<EtherAddress> ordered_interfaces;
	Vector<Timestamp> last_time_seen_interfaces;
	Vector<Timestamp> last_time_cont_links;
	uint8_t unique_interface;
	bool unique_interface_wifi;


	#define INTERFACE1 1
	#define INTERFACE2 0 // INTERFACE2 is PLC or Wifi2; in acne scripts, corresponds to port 0

	NodeRouting() {
	interfaces = Vector<EtherAddress>();
	unique_interface = -1;
	ordered_interfaces = Vector<EtherAddress>(2,EtherAddress());
	}

	NodeRouting(IPAddress _ip) {
	ip=_ip;
	interfaces = Vector<EtherAddress>();
	unique_interface = -1;
	ordered_interfaces = Vector<EtherAddress>(2,EtherAddress());
	}

	NodeRouting(IPAddress _ip, Vector<EtherAddress> addr) {
	interfaces = addr;
	ip = _ip;
	unique_interface = -1;
	ordered_interfaces = Vector<EtherAddress>(2,EtherAddress());
	}

	EtherAddress get_wifi_interface() {
	if(ordered_interfaces[INTERFACE2] != EtherAddress())
	return ordered_interfaces[INTERFACE2];
	for(int i=0;i<interfaces.size();i++) {
	if(is_wifi_addr(interfaces[i])) {
	ordered_interfaces[INTERFACE2] = interfaces[i];
	break;
	}
	}
	return ordered_interfaces[INTERFACE2];
	}

	EtherAddress get_plc_interface() {
	if(ordered_interfaces[INTERFACE1] != EtherAddress())
	return ordered_interfaces[INTERFACE1];
	for(int i=0;i<interfaces.size();i++) {
	if(is_plc_addr(interfaces[i])) {
	ordered_interfaces[INTERFACE1] = interfaces[i];
	break;
	}
	}
	return ordered_interfaces[INTERFACE1];
	}


	uint32_t
	hashcode() const {
	return ip.hashcode();
	}

	inline bool operator==(const NodeRouting a) const
	{
	return a.ip == ip;
	}

	inline bool operator!=(const NodeRouting a) const
	{
	return a.ip != ip;
	}

	inline bool operator<(const NodeRouting a) const
	{
	return ip.unparse() < a.ip.unparse();
	}




	};


	template<typename T>
	struct Ring {
	Vector<T> vector;
	int index;
	T default_value;

	Ring() {
	}

	Ring(int size, T def) {
	vector = Vector<T>(size,def);
	index = -1;
	default_value = def;
	}

	void add(T n) {
	index = (index+1) % vector.size();
	vector[index] = n;
	}

	void change(T n) {
	if(index >= 0 && index < vector.size())
	vector[index] = n;
	}

	void set_all(T n) {
	for(int i=0;i<vector.size();i++)
	vector[i]=n;
	}

	bool all_equal(T n) {
	for(int i=0;i<vector.size();i++) {
	if(vector[i]!=n)
	return false;
	}
	return true;
	}

	int size_equal(T n) {
	int count=0;
	for(int i=0;i<vector.size();i++) {
	if(vector[i]==n)
	count++;
	}
	return count;
	}

	int size_not_equal(T n) {
	int count=0;
	for(int i=0;i<vector.size();i++) {
	if(vector[i]!=n)
	count++;
	}
	return count;
	}

	T sum() {
	T sum=0;
	for (int i=0;i<vector.size();i++) {
	if(vector[i]!=default_value)
	sum+=vector[i];
	}
	return sum;
	}

	void erase(T n) {
	for(int i=0;i<vector.size();i++) {
	if(vector[i]==n)
	vector[i]=default_value;
	}
	}

	T size() {
	return vector.size();
	}

	String unparse() {
	Vector<T> ordered_vector;
	for(int i=(index+1);i<vector.size();i++)
	ordered_vector.push_back(vector[i]);
	for(int i=0;i<=index;i++)
	ordered_vector.push_back(vector[i]);
	return print_vector(ordered_vector);
	}

	void scale(int scale_mult, int scale_div) {
	for(int i=0;i<=index;i++) {
	vector[i] = (vector[i]*scale_mult)/scale_div;
	}
	}

	};



	/*
	* Represents a link towards a neighbor
	* (as used by the element Neighbors)
	*/
	struct NeighborLink {
	EtherAddress eth_addr;


	uint8_t interface;
	uint32_t capa_th; //moving average in kbps (without taking success proba into account)
	uint32_t capa; //acutal capa estimate, with success proba taken into account
	Timestamp last_time_heard; //last time we heard a HELLO on that link
	Timestamp last_time_sent; // last time we sent a HELLO unicast frame
	uint16_t last_seq_number; //seq number of the last received HELLO
	#define MAX_SEQ_NUMBER_HELLO 60000
	///// used to estimate success proba:
	uint32_t nr_period_elapsed;
	uint32_t nr_hello_rcvd;
	uint32_t success_proba; //moving average
	bool initialized;
	bool traffic_sent;
	Timestamp last_update; //time of last update
	Ring<uint64_t> *last_capa_measurements;

	/////

	NeighborLink(){
	Timestamp now;
	now.assign_now();
	capa_th = 0;
	capa = 0;
	last_time_heard = now;
	success_proba = 1000;
	nr_period_elapsed = 0;
	nr_hello_rcvd = 0;
	initialized = false;
	traffic_sent = false;
	}

	NeighborLink(EtherAddress addr, int inter, int alpha){
	Timestamp now;
	now.assign_now();
	eth_addr = addr;
	interface = (uint8_t)inter;
	capa_th = 0;
	capa = 0;
	last_time_heard = now;
	success_proba = 1000;
	nr_period_elapsed = 0;
	nr_hello_rcvd = 0;
	initialized = false;
	traffic_sent = false;
	if (alpha>0) {
	last_capa_measurements = new Ring<uint64_t>(1000/alpha,0);
	}
	}

	inline bool operator ==(const NeighborLink nl) const {
	return (nl.eth_addr == eth_addr);
	}
	inline bool operator !=(const NeighborLink nl) const {
	return (nl.eth_addr != eth_addr);
	}

	//Period of update can change: multiply ALPHA_EWMA_PER_SEC by period (max alpha: 0.05)
	//#define ALPHA_EWMA_PER_SEC 10u // divide by 1000
	#define ALPHA_EWMA_SUCCESS_PROBA 50u // divide by 1000
	#define UPDATE_AFTER_SEC 30

	#define CORRECTION_PLC 59u // divide by 100
	//#define CORRECTION_WIFI 33u // divide by 100 // approximative value, needs to be refined
	#define CORRECTION_WIFI 80u // divide by 100
	//void update_wifi(uint32_t phy_rate, uint8_t retry){


	void update_wifi(uint32_t phy_rate, int alpha_per_sec){
	//Update wifi capacity
	Timestamp now;
	now.assign_now();
	uint32_t period = mymin(10, (now-last_update).sec());
	update_capa(phy_rate, mymin(100u,alpha_per_sec*period), CORRECTION_WIFI);

	//update success stats:
	//nr_packets++;
	//if(retry != 0) nr_retx++;
	}

	void update_plc(uint32_t phy_rate, int alpha_per_sec){
	//Update PLC capacity
	Timestamp now;
	now.assign_now();
	uint32_t period = mymin(10, (now-last_update).sec());
	update_capa(phy_rate, mymin(300u,alpha_per_sec*period), CORRECTION_PLC);
	}

	void update_capa(uint32_t new_capa, uint32_t alpha, uint32_t correction){
	if(last_capa_measurements->size() == 0) {
	if(capa_th == 0)
	capa_th = new_capa;
	else
	capa_th = int_divide((1000 - alpha)capa_th + alpha new_capa,1000);

	//capa = capa_th; // without weighting by success proba
	capa = int_divide(capa_th * success_proba, 1000); // with weighting by success proba
	capa = int_divide(capa*correction, 100);
	}
	else {
	uint64_t capa64= (uint64_t) new_capa;
	if(capa64==0)
	capa64=1; // 0 is no value
	last_capa_measurements->add(capa64);
	capa_th=(uint32_t) int_divide(last_capa_measurements->sum(),last_capa_measurements->size_not_equal(0u));
	capa = int_divide(capa_th * success_proba, 1000); // with weighting by success proba
	capa = int_divide(capa*correction, 100);
	}

	last_update.assign_now();
	}

	void reset_capa() {
	capa_th = 0;
	capa = 0;
	}

	//called each time a HELLO is parsed
	void update_success_proba(uint16_t seq, bool debug){
	int seq_i = (int) seq;
	int last_seq_i = (int) last_seq_number;
	int diff = (seq_i - last_seq_i);
	int elapsed;
	if (diff >=0)
	elapsed = diff;
	else
	elapsed = diff + MAX_SEQ_NUMBER_HELLO;
	nr_period_elapsed+=elapsed;
	nr_hello_rcvd++;
	last_seq_number = seq;

	//if we have enough statistics:
	if((initialized && nr_period_elapsed > 10) \|\| (!initialized && nr_period_elapsed > 30)){
	//pr is in [0,1000]:
	uint32_t pr = int_divide(1000*nr_hello_rcvd,nr_period_elapsed);
	if(pr > 1000) pr = 1000;

	uint32_t old_proba = success_proba;

	if (!initialized) {
	success_proba = pr;
	initialized = true;
	}
	else
	success_proba = int_divide((1000 - ALPHA_EWMA_SUCCESS_PROBA)success_proba + ALPHA_EWMA_SUCCESS_PROBA pr,1000);

	if(debug)
	click_chatter(" Proba updated: was %d, is %d (pr=%d)", old_proba, success_proba, pr);
	//update actual capa:
	//capa = int_divide(capa_th * success_proba,1000);
	nr_period_elapsed = 0;
	nr_hello_rcvd = 0;

	}
	}

	void update_success_proba(bool retry, bool debug) {
	nr_period_elapsed++;
	if(!retry)
	nr_hello_rcvd++;

	if(nr_period_elapsed > 10){
	//pr is in [0,1000]:
	uint32_t pr = int_divide(1000*nr_hello_rcvd,nr_period_elapsed);
	if(pr > 1000) pr = 1000;

	uint32_t old_proba = success_proba;

	if (!initialized) {
	success_proba = pr;
	initialized = true;
	}
	else
	success_proba = int_divide((1000 - ALPHA_EWMA_SUCCESS_PROBA)success_proba + ALPHA_EWMA_SUCCESS_PROBA pr,1000);

	if(debug)
	click_chatter(" Proba updated: was %d, is %d (pr=%d)", old_proba, success_proba, pr);
	//update actual capa:
	//capa = int_divide(capa_th * success_proba,1000);
	nr_period_elapsed = 0;
	nr_hello_rcvd = 0;

	}

	}

	};

	struct RealNeighbor {
	EtherAddress true_neighbor; // not mandatory
	EtherAddress neighbor;
	uint32_t weight;

	RealNeighbor() {}

	RealNeighbor(EtherAddress interface) {
	neighbor = interface;
	weight = 0;
	}

	RealNeighbor(EtherAddress interface, uint32_t w) {
	neighbor = interface;
	weight = w;
	}

	RealNeighbor(EtherAddress interface, EtherAddress true_interface) {
	neighbor = interface;
	true_neighbor = true_interface;
	weight = 0;
	}

	RealNeighbor(EtherAddress interface, EtherAddress true_interface, uint32_t w) {
	neighbor = interface;
	true_neighbor = true_interface;
	weight = w;
	}

	inline bool operator==(const RealNeighbor a) const
	{
	EtherAddress empty = EtherAddress();
	return (a.neighbor == neighbor) &&
	(a.true_neighbor == empty \|\| true_neighbor == empty \|\| a.true_neighbor == true_neighbor);
	}

	inline bool operator!=(const RealNeighbor a) const
	{
	EtherAddress empty = EtherAddress();
	return (a.neighbor!=neighbor) \|\|
	(a.true_neighbor != empty && true_neighbor != empty && a.true_neighbor != true_neighbor);
	}

	String unparse() const {
	String s="(";
	s+=neighbor.unparse();
	s+=";";
	s+=String(weight);
	s+=") ";
	return s;
	}
	};


	struct FlowInfoLB{
	uint32_t rate; //Byte per sec
	uint32_t sent; //Byte
	TokenBucket _tb; //tokenbucket to control rate sent
	Timestamp last;
	Timestamp last_packet;

	FlowInfoLB() {
	sent = 0;
	_tb.set_full();
	}

	FlowInfoLB(Timestamp ts) {
	last = ts;
	sent = 0;
	//_tb.set_full();
	}


	FlowInfoLB(uint32_t r) {
	rate = r;
	_tb.assign(rate,mymax(rate/100,10000u));
	//_tb.set_full();
	sent = 0;
	}

	FlowInfoLB(uint32_t r, Timestamp ts) {
	rate = r;
	_tb.assign(rate,mymax(rate/100,10000u));
	//_tb.set_full();
	last = ts;
	sent = 0;
	}

	void reinitialize(Timestamp now) {
	sent = 0;
	last = now;
	}

	void reinitialize_full(Timestamp now) {
	sent = 0;
	last = now;
	_tb.set_full();
	}

	void set_rate(uint32_t r) {
	rate = r;
	_tb.assign_adjust(rate,mymax(rate/100,10000u));
	sent = 0;
	}

	void set_rate_full(uint32_t r) {
	rate = r;
	_tb.assign_adjust(rate,mymax(rate/100,10000u));
	sent = 0;
	_tb.set_full();
	}

	String unparse() const {
	return String(rate);
	}
	};


	#define MAX_POSSIBLE_RATE 25000000
	#define MIN_AIRTIME_COMPUTATION_TIME_MS 100

	struct MabArmInfo {
	// structure for an arm (set of paths) in Multi-Armed-Bandit

	IPAddress _dst; // address of the destination of the flow
	Vector<Route> _routes; // routes used for this flow
	Vector<FormatedRoute> _froutes; // formated routes used for this flow
	HashTable<uint16_t, Vector<uint32_t> > _sent_rates_table; // table id / sent rates in B/s
	HashTable<LinkRouting, HashTable<uint16_t, gamma_type> > _gammas_table; // table with gammas for each link, each id
	HashTable<uint16_t, HashTable<FormatedRoute,int> > _routes_unacked;
	HashTable<uint16_t, int> _saturated;
	Vector<Ring<uint64_t> > _last_best_rates;
	Vector<uint32_t> _current_best_rate; //store the current best rate in B/s
	Vector<uint32_t> _current_best_rate_alone; //store the current best rate in B/s
	Vector<FlowInfoLB> _current_sending_rate; //flow info for the current rate
	uint32_t _current_total_rate; // current total rate sent at this trial
	uint32_t _current_best_rate_total; // current total best rate
	uint32_t _scaling_rate;
	Vector<FlowInfoLB> _current_sent_rate; // maintain stats about rate actually sent
	HashTable<uint16_t, Vector<uint16_t> > _explore_ids;
	HashTable<uint16_t, Vector<uint16_t> > _explore_ids_persistent;
	size_t _hashcode;
	int _explore;
	uint32_t _num_explore;
	int _missed_explore;
	TokenBucket _tb;
	Ring<int> _missed_acks_explore; // to keep track of missed explore
	int _nb_cons_picked;
	int _consecutive_high_error;
	int _min_proba;

	//int _min_proba;

	MabArmInfo() {

	}

	MabArmInfo(IPAddress ip, Vector<Route> routes, int alpha) { // use alpha to compute ring size
	_dst = ip;
	_routes = routes;
	_hashcode = _dst.hashcode();
	_current_total_rate = 0;
	_missed_explore = 0;
	int size_ring = 1000/alpha;
	for(int i=0;i<routes.size();i++) {
	FormatedRoute froute = FormatedRoute(routes[i]);
	_froutes.push_back(froute);
	_hashcode+=10(i+1)froute.hashcode();
	assert(size_ring>0);
	_last_best_rates.push_back(Ring<uint64_t>(size_ring,0));
	_current_best_rate.push_back(routes[i].max_capa*128/2); // one half of computed rate at beginning
	_current_best_rate_alone.push_back(routes[i].max_capa_alone*128/2);
	_current_sending_rate.push_back(FlowInfoLB(mymax((routes[i].max_capa_alone)*128/2, MIN_SENDING_RATE))); // max_capa in kb/s
	_current_sent_rate.push_back(FlowInfoLB());
	_current_total_rate += routes[i].max_capa*128;
	}
	_num_explore = 0;
	_missed_acks_explore = Ring<int>(5,-1);
	_missed_acks_explore.set_all(1);
	_current_best_rate_total = 0;
	_nb_cons_picked = 1;
	_consecutive_high_error = 0;
	//_min_proba = 0;
	}

	MabArmInfo(MabArmInfo *arm) {
	_dst = arm->_dst;
	_routes = arm->_routes;
	_froutes = arm->_froutes;
	_sent_rates_table = arm->_sent_rates_table;
	_gammas_table = arm->_gammas_table;
	_routes_unacked = arm->_routes_unacked;
	_last_best_rates = arm->_last_best_rates;
	_current_best_rate = arm->_current_best_rate;
	_current_best_rate_alone = arm->_current_best_rate_alone;
	_current_sending_rate = arm->_current_sending_rate;
	_current_total_rate = arm->_current_total_rate;
	_current_best_rate_total = arm->_current_best_rate_total;
	_scaling_rate = arm->_scaling_rate;
	_current_sent_rate = arm->_current_sent_rate;
	_explore_ids = arm->_explore_ids;
	_explore_ids_persistent = arm->_explore_ids_persistent;
	_hashcode = arm->_hashcode;
	_explore = arm->_explore;
	_num_explore = arm->_num_explore;
	_missed_explore = arm->_missed_explore;
	_tb = arm->_tb;
	_missed_acks_explore = arm->_missed_acks_explore;
	_saturated = arm->_saturated;
	_nb_cons_picked = arm->_nb_cons_picked;
	_consecutive_high_error = 0;
	//_min_proba = arm->_min_proba;
	}

	void update_current_best_rate(Vector<uint32_t> rate, int alpha) {
	if(_num_explore == 0) {
	_current_best_rate = rate;
	_num_explore = 1;
	_current_best_rate_total = 0;
	_missed_explore--;
	_missed_acks_explore = Ring<int>(5,-1);
	_missed_acks_explore.set_all(1);
	for(int i=0;i<rate.size();i++)
	_current_best_rate_total+=rate[i];
	}
	else {
	if(rate.size()!=_current_best_rate.size()) {
	click_chatter("MabArmInfo::update_current_best_rate Different vector sizes");
	return;
	}
	_current_best_rate_total = 0;
	for(int i=0;i<rate.size();i++) {

	if(_num_explore < 10) {
	_last_best_rates[i].add((uint64_t)rate[i]);
	_current_best_rate[i] = (_num_explore*_current_best_rate[i] + rate[i])/(_num_explore+1); // computes mean on all first
	}
	else {
	if(alpha > 0) {
	uint64_t new_best_rate_1000 = (1000 - alpha)*((uint64_t) _current_best_rate[i]) +
	alpha*((uint64_t) rate[i]);
	_current_best_rate[i] = (uint32_t) int_divide(new_best_rate_1000,1000);
	}
	else {
	_last_best_rates[i].add((uint64_t)rate[i]);
	_current_best_rate[i] = (uint32_t) int_divide(_last_best_rates[i].sum(),_last_best_rates[i].size());
	}
	}

	_current_best_rate_total+=_current_best_rate[i];
	}
	_num_explore++;
	_missed_explore--;
	_missed_acks_explore.change(1);
	}
	}

	void reset_rates() {
	for(int i=0;i<_froutes.size();i++) {
	_current_best_rate[i] = _routes[i].max_capa*128/2;
	_current_best_rate_alone[i] = _routes[i].max_capa_alone*128/2;
	}
	_current_best_rate_total = 0;
	_num_explore = 0;
	}

	void reset_rates_missed() {
	reset_rates();
	_missed_explore = 50; // to avoid reexploring immediately whereas we know it's not good, set high number of missed (50: 2% proba to explore)
	}

	void scale_last_best_rates(int scale_mult, int scale_div) {
	for(int i=0;i<_last_best_rates.size();i++) {
	_last_best_rates[i].scale(scale_mult,scale_div);
	}
	}


	inline bool operator==(const MabArmInfo a) const
	{
	return equals_vector(_routes, a._routes);
	}

	inline bool operator!=(const MabArmInfo a) const
	{
	return !equals_vector(_routes, a._routes);
	}

	inline size_t hashcode() const {
	return _hashcode;
	}
	};



	enum Interface{WIFI, PLC};

	static String interface_to_string(Interface interface) {
	if (interface == WIFI)
	return "WiFi";
	if (interface == PLC)
	return "PLC";
	}

	class IntIdCouple {
	uint16_t _id;
	Interface _interface;
	FlowTuple _flow;

	public:
	IntIdCouple(uint16_t id, Interface interface, FlowTuple flow) {
	_id = id;
	_interface = interface;
	_flow = flow;
	}

	inline bool operator==(IntIdCouple const& a) const {
	return (_id == a._id && _interface == a._interface && _flow == a._flow);
	}

	inline size_t hashcode() const {
	return (String(_id)+interface_to_string(_interface)+_flow.unparse()).hashcode();
	}
	};


	class Measurements : public Element {
	public:
	#define MAX_NB_NGHBRS_BIANCHI 10
	#define MIN_NB_PACKET_PERSEC 20

	virtual gamma_type get_airtime(int) = 0;

	virtual gamma_type get_busytime_us(int) = 0;

	virtual void init_airtime(int, int) = 0;

	virtual void reinitialize_counters() = 0;

	virtual void reinitialize_counters(int) = 0;

	virtual void compute_airtime(int) = 0;

	virtual Timestamp get_delay_first_packet(int) = 0;

	};


	struct Multipath {
	Vector<Route> _routes;
	uint32_t _total_capacity;

	Multipath () {
	_routes = Vector<Route>();
	_total_capacity = 0;
	}

	Multipath (Vector<Route> routes) {
	_routes = routes;
	_total_capacity = 0;
	}

	void add_route(Route route) {
	insert_in_sorted_descent_vector(_routes, route);
	_total_capacity += route.max_capa;
	}

	inline bool operator==(const Multipath a) const
	{
	return equals_set(_routes, a._routes);
	}

	inline bool operator!=(const Multipath a) const
	{
	return !equals_vector(_routes, a._routes);
	}

	inline bool operator<(const Multipath a) const
	{
	return _total_capacity < a._total_capacity;
	}

	inline bool operator>(const Multipath a) const
	{
	return _total_capacity > a._total_capacity;
	}

	inline uint32_t hashcode() const {
	uint32_t hash = 0;
	for(int i=0;i<_routes.size();i++)
	hash+=_routes[i].hashcode();
	return hash;
	}

	String unparse() const {
	String s = "";
	for (int i=0;i<_routes.size();i++)
	s += (_routes[i].unparse() + " ; \n ");
	s+= ("total capacity " + String(_total_capacity) + ".");

	return s;
	}

	};






	typedef HashTable<EtherAddress, Vector<RealNeighbor> > Links;
	typedef HashTable<EtherAddress, NeighborLink> LinksTable;
	typedef HashTable<uint16_t, Packet*> PacketTable;

	CLICK_ENDDECLS


	#endif

util.hhNo OneTemporaryActions

File Metadata

util.hhView Options

Event Timeline

util.hh
No OneTemporary
Actions

util.hh
View Options