new routing system

supports ipv4 and ipv6 routing with subnetting

11 files changed, 268 insertions, 14 deletions

diff --git a/src/Makefile b/src/Makefile
index dda6f0d..adbf1ea 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -75,6 +75,7 @@ OBJS = tunDevice.o \
        syncConnectionCommand.o \
 			 rtpSessionTable.o \
 			 rtpSession.o \
+			 routingTreeNode.o \
        anyrtpproxy/callIdQueue.o
 
 SYNCOBJS= syncServer.o \
@@ -98,6 +99,7 @@ ANYCONFOBJS = log.o \
 						 connectionParam.o \
 						 rtpSessionTable.o \
 						 rtpSession.o \
+						 routingTreeNode.o \
 						 anyrtpproxy/callIdQueue.o \
 						 syncRtpCommand.o \
 						 anyConfOptions.o \
@@ -164,6 +166,9 @@ rtpSessionTable.o: rtpSessionTable.cpp rtpSessionTable.h
 rtpSession.o: rtpSession.cpp rtpSession.h
 	$(CXX) $(CXXFLAGS) $< -c
 
+routingTreeNode.o: routingTreeNode.cpp routingTreeNode.h
+	$(CXX) $(CXXFLAGS) $< -c
+
 plainPacket.o: plainPacket.cpp plainPacket.h buffer.h
 	$(CXX) $(CXXFLAGS) $< -c
 
@@ -200,7 +205,7 @@ authAlgoFactory.o: authAlgoFactory.cpp authAlgoFactory.h authAlgo.h
 keyDerivationFactory.o: keyDerivationFactory.cpp keyDerivationFactory.h keyDerivation.h
 	$(CXX) $(CXXFLAGS) $< -c
 
-routingTable.o: routingTable.cpp routingTable.h
+routingTable.o: routingTable.cpp routingTable.h routingTreeWalker.hpp
 	$(CXX) $(CXXFLAGS) $< -c
 
 syncCommand.o: syncCommand.cpp syncCommand.h
diff --git a/src/networkAddress.cpp b/src/networkAddress.cpp
index 49ae704..f922c00 100644
--- a/src/networkAddress.cpp
+++ b/src/networkAddress.cpp
@@ -119,6 +119,28 @@ std::string NetworkAddress::toString() const
   return std::string("");
 }
 
+ipv4_bytes_type	NetworkAddress::to_bytes_v4() const
+{
+	return ipv4_address_.to_bytes();
+}
+
+ipv6_bytes_type	NetworkAddress::to_bytes_v6() const
+{
+	return ipv6_address_.to_bytes();
+}
+
+ethernet_bytes_type	NetworkAddress::to_bytes_ethernet() const
+{
+	boost::array<unsigned char,6> result;
+	u_int64_t ether=ethernet_address_;
+	for (int i = 0; i < 6; i++)
+	{
+		result[i] = (unsigned char) (ether && 0xff);
+			ether >>= 8;
+	}
+	return result;
+}
+
 bool NetworkAddress::operator<(const NetworkAddress &right) const
 {
 	if (network_address_type_!=right.network_address_type_)
diff --git a/src/networkAddress.h b/src/networkAddress.h
index 3eb0b51..f866cca 100644
--- a/src/networkAddress.h
+++ b/src/networkAddress.h
@@ -39,6 +39,11 @@
 
 #include <string>
 #include <boost/asio.hpp>
+#include <boost/array.hpp>
+
+typedef boost::array<unsigned char,6> ethernet_bytes_type;
+typedef boost::asio::ip::address_v4::bytes_type ipv4_bytes_type;
+typedef boost::asio::ip::address_v6::bytes_type ipv6_bytes_type;
 
 enum network_address_type_t
 {
@@ -62,6 +67,9 @@ public:
 	network_address_type_t getNetworkAddressType() const;
   std::string toString() const;
 	bool operator<(const NetworkAddress &s) const;
+	ipv4_bytes_type to_bytes_v4() const;	
+	ipv6_bytes_type to_bytes_v6() const;	
+	ethernet_bytes_type to_bytes_ethernet() const;	
 protected:
   Mutex mutex_;
 	boost::asio::ip::address_v4 ipv4_address_;
diff --git a/src/networkPrefix.cpp b/src/networkPrefix.cpp
index f72dc01..3efdcdd 100644
--- a/src/networkPrefix.cpp
+++ b/src/networkPrefix.cpp
@@ -52,7 +52,7 @@ void NetworkPrefix::setNetworkPrefixLength(u_int8_t length )
 	length_ = length;
 }
 
-u_int8_t NetworkPrefix::getNetworkPrefixLength()
+u_int8_t NetworkPrefix::getNetworkPrefixLength() const
 {
 	return length_;
 }
diff --git a/src/networkPrefix.h b/src/networkPrefix.h
index 53ebf0c..5a0a69a 100644
--- a/src/networkPrefix.h
+++ b/src/networkPrefix.h
@@ -46,7 +46,7 @@ public:
 	NetworkPrefix(const NetworkAddress &, u_int8_t length);
 	NetworkPrefix(const NetworkPrefix &);
 	void setNetworkPrefixLength(u_int8_t length );
-	u_int8_t getNetworkPrefixLength();
+	u_int8_t getNetworkPrefixLength() const;
   bool operator<(const NetworkPrefix &s) const;
 
 private:
diff --git a/src/routingTable.cpp b/src/routingTable.cpp
index b3aae6e..a1f8d67 100644
--- a/src/routingTable.cpp
+++ b/src/routingTable.cpp
@@ -33,6 +33,7 @@
 #include "datatypes.h"
 
 #include "routingTable.h"
+#include "routingTreeWalker.hpp"
 
 RoutingTable* RoutingTable::inst = NULL;
 Mutex RoutingTable::instMutex;
@@ -57,6 +58,34 @@ RoutingTable::~RoutingTable()
 {
 } 
 
+void RoutingTable::updateRouteTree(const NetworkPrefix & pref)
+{
+	u_int8_t length=pref.getNetworkPrefixLength();
+	network_address_type_t type=pref.getNetworkAddressType();
+	u_int16_t mux = routes_[pref.getNetworkAddressType()].find(pref)->second;
+	RoutingTreeNode * node = &(root_[type]);
+	if (type==ipv4)
+	{
+		ipv4_bytes_type bytes(pref.to_bytes_v4());
+		if (length>32)
+			length=32;
+		routingTreeWalker(bytes, node, length, mux);
+	} else if  (type==ipv6) {
+		ipv6_bytes_type bytes(pref.to_bytes_v6());
+		if (length>128)
+			length=128;
+		routingTreeWalker(bytes, node, length, mux);
+	} else if (type==ethernet) {
+		ethernet_bytes_type bytes(pref.to_bytes_ethernet());
+		if (length>48)
+			length=48;
+		routingTreeWalker(bytes, node, length, mux);
+	} else {
+		throw std::runtime_error("illegal protocoll type");	
+	}
+	//root_[type].print(0);
+}
+
 void RoutingTable::addRoute(const NetworkPrefix & pref,u_int16_t mux )
 {
 	if ( pref.getNetworkAddressType()!=ipv4 && pref.getNetworkAddressType() != ipv6)
@@ -70,6 +99,7 @@ void RoutingTable::addRoute(const NetworkPrefix & pref,u_int16_t mux )
     routes_[pref.getNetworkAddressType()].erase(ret.first);
     routes_[pref.getNetworkAddressType()].insert(RoutingMap::value_type(pref,mux));
   }
+	updateRouteTree(pref);
 }
 
 
@@ -83,16 +113,26 @@ void RoutingTable::delRoute(const NetworkPrefix & pref )
 u_int16_t  RoutingTable::getRoute(const NetworkAddress & addr)
 {
 	Lock lock(mutex_);
-	if (routes_[addr.getNetworkAddressType()].empty())
-  	return 0;
-	//TODO Routing algorithem isnt working!!!
-	NetworkPrefix prefix(addr,128);
-	RoutingMap::iterator it = routes_[addr.getNetworkAddressType()].lower_bound(prefix);
-//	it--;
-	if (it!=routes_[addr.getNetworkAddressType()].end())
-		return it->second;
-	it=routes_[addr.getNetworkAddressType()].begin();
-	return it->second;
+	network_address_type_t type=addr.getNetworkAddressType();
+	
+	if (routes_[type].empty())
+  	throw std::runtime_error("no route");
+
+	if (type==ipv4)
+	{
+		ipv4_bytes_type bytes(addr.to_bytes_v4());
+		return routingTreeFinder(bytes, root_[type]);
+	} else if  (type==ipv6) {
+		ipv6_bytes_type bytes(addr.to_bytes_v6());
+		return routingTreeFinder(bytes, root_[type]);
+	} else if (type==ethernet) {
+		//TODO Our model wont fit to ethernet addresses well.
+		// maybe use hashmap or something like that instead
+		ethernet_bytes_type bytes(addr.to_bytes_ethernet());
+		return routingTreeFinder(bytes, root_[type]);
+	} else {
+		throw std::runtime_error("illegal protocoll type");	
+	}
 }
 
 u_int16_t* RoutingTable::getOrNewRoutingTEUnlocked(const NetworkPrefix & addr)
diff --git a/src/routingTable.h b/src/routingTable.h
index e73deea..85de0fa 100644
--- a/src/routingTable.h
+++ b/src/routingTable.h
@@ -39,6 +39,8 @@
 #include "datatypes.h"
 #include "networkAddress.h"
 #include "networkPrefix.h"
+#include "routingTreeNode.h"
+#include "boost/array.hpp"
 typedef std::map<NetworkPrefix,u_int16_t> RoutingMap;
 
 class RoutingTable
@@ -48,6 +50,7 @@ public:
 	RoutingTable();
 	~RoutingTable();
 	void addRoute(const NetworkPrefix & ,u_int16_t);
+	void updateRouteTree(const NetworkPrefix & pref);
 	void delRoute(const NetworkPrefix & );
 	u_int16_t getRoute(const NetworkAddress &);
 	bool empty(network_address_type_t type);
@@ -69,7 +72,8 @@ private:
 	};
 	RoutingTable(const RoutingTable &s);
   void operator=(const RoutingTable &s);
-	RoutingMap routes_[3];
+	boost::array<RoutingMap,3> routes_;
+	boost::array<RoutingTreeNode,3> root_;
   Mutex mutex_;
 };
 
diff --git a/src/routingTreeNode.cpp b/src/routingTreeNode.cpp
new file mode 100644
index 0000000..47dc0fc
--- /dev/null
+++ b/src/routingTreeNode.cpp
@@ -0,0 +1,64 @@
+/*
+ *  anytun
+ *
+ *  The secure anycast tunneling protocol (satp) defines a protocol used
+ *  for communication between any combination of unicast and anycast
+ *  tunnel endpoints.  It has less protocol overhead than IPSec in Tunnel
+ *  mode and allows tunneling of every ETHER TYPE protocol (e.g.
+ *  ethernet, ip, arp ...). satp directly includes cryptography and
+ *  message authentication based on the methodes used by SRTP.  It is
+ *  intended to deliver a generic, scaleable and secure solution for
+ *  tunneling and relaying of packets of any protocol.
+ *
+ *
+ *  Copyright (C) 2007-2008 Othmar Gsenger, Erwin Nindl, 
+ *                          Christian Pointner <satp@wirdorange.org>
+ *
+ *  This file is part of Anytun.
+ *
+ *  Anytun is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License version 3 as
+ *  published by the Free Software Foundation.
+ *
+ *  Anytun is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with anytun.  If not, see <http://www.gnu.org/licenses/>.
+ */
+#include "routingTreeNode.h"
+
+RoutingTreeNode::RoutingTreeNode():mux_(0),valid_(false)
+{
+	for(int i=0; i<256; i++)
+		nodes_[i]=NULL;
+}
+
+void RoutingTreeNode::print(int level) const
+{
+	if (valid_)
+	{	
+		std::cout << " -> " <<mux_ ;
+	}
+	std::cout  << std::endl;
+  for(int i=0; i<256; i++)
+	{
+		if ( nodes_[i])
+		{
+			for(int l=0;l<level;l++)
+				std::cout << " ";
+			std::cout << (int) i;
+			nodes_[i]->print(level+1);
+		}
+	}
+}
+
+
+RoutingTreeNode::~RoutingTreeNode()
+{
+	for(int i=0; i<256; i++)
+		if(nodes_[i])
+			delete nodes_[i];
+} 
diff --git a/src/routingTreeNode.h b/src/routingTreeNode.h
new file mode 100644
index 0000000..c09f2c9
--- /dev/null
+++ b/src/routingTreeNode.h
@@ -0,0 +1,53 @@
+/*
+ *  anytun
+ *
+ *  The secure anycast tunneling protocol (satp) defines a protocol used
+ *  for communication between any combination of unicast and anycast
+ *  tunnel endpoints.  It has less protocol overhead than IPSec in Tunnel
+ *  mode and allows tunneling of every ETHER TYPE protocol (e.g.
+ *  ethernet, ip, arp ...). satp directly includes cryptography and
+ *  message authentication based on the methodes used by SRTP.  It is
+ *  intended to deliver a generic, scaleable and secure solution for
+ *  tunneling and relaying of packets of any protocol.
+ *
+ *
+ *  Copyright (C) 2007-2008 Othmar Gsenger, Erwin Nindl, 
+ *                          Christian Pointner <satp@wirdorange.org>
+ *
+ *  This file is part of Anytun.
+ *
+ *  Anytun is free software: you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License version 3 as
+ *  published by the Free Software Foundation.
+ *
+ *  Anytun is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with anytun.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef _ROUTINGTREENODE_H
+#define _ROUTINGTREENODE_H
+
+
+#include "threadUtils.hpp"
+#include "datatypes.h"
+#include "networkAddress.h"
+#include "networkPrefix.h"
+
+class RoutingTreeNode
+{
+public:
+	RoutingTreeNode();
+	~RoutingTreeNode();
+	u_int16_t mux_;
+	bool valid_;
+	boost::array<RoutingTreeNode *,256> nodes_;
+	void print(int) const;
+private:
+  Mutex mutex_;
+};
+#endif
diff --git a/src/routingTreeWalker.hpp b/src/routingTreeWalker.hpp
new file mode 100644
index 0000000..0989a8a
--- /dev/null
+++ b/src/routingTreeWalker.hpp
@@ -0,0 +1,57 @@
+#ifndef __ROUTING_TREE_WALKER_
+#define __ROUTING_TREE_WALKER_
+template <class BinaryType>
+void routingTreeWalker(BinaryType bytes ,RoutingTreeNode * node,u_int8_t length,u_int16_t mux)
+{
+	for (int i=0; i<(length/8); i++)
+	{
+		if (!node->nodes_[bytes[i]])
+			node->nodes_[bytes[i]] = new RoutingTreeNode;
+		node=node->nodes_[bytes[i]];
+	}
+	if (length%8)
+	{
+		unsigned char idx=0xff;
+		idx <<=8-(length%8);
+		idx &= bytes[length/8];
+		unsigned char maxidx=0xff;
+		maxidx>>=(length%8);
+		maxidx|=idx;
+		for (unsigned char i=idx; i<=maxidx; i++)
+		{
+			if (!node->nodes_[i])
+				node->nodes_[i] = new RoutingTreeNode;
+			node->nodes_[i]->valid_=true;
+			node->nodes_[i]->mux_=mux;
+		}
+	} else {
+		node->valid_=true;
+		node->mux_=mux;
+	}
+}
+
+template <class BinaryType>
+u_int16_t routingTreeFinder(BinaryType bytes ,RoutingTreeNode & root )
+{
+	bool valid=0;
+	u_int16_t mux;
+	RoutingTreeNode * node = &root;
+	if (root.valid_)
+		mux=root.mux_;
+	for (size_t level=0;level<bytes.size();level++)
+	{
+		if (node->nodes_[bytes[level]])
+		{
+			node=node->nodes_[bytes[level]];
+			if(node->valid_)
+				mux=node->mux_;
+		} else {
+		 break;
+		}
+	}
+	if(!valid)
+		throw std::runtime_error("no route");
+	return mux;
+}
+#endif
+
diff --git a/src/syncRouteCommand.h b/src/syncRouteCommand.h
index 349ae93..2f64987 100644
--- a/src/syncRouteCommand.h
+++ b/src/syncRouteCommand.h
@@ -57,6 +57,7 @@ private:
 //		u_int16_t & mux (gRoutingTable.getOrNewRoutingTEUnlocked(addr_));
 //		ar & mux;
 		ar & (*(gRoutingTable.getOrNewRoutingTEUnlocked(addr_)));
+		gRoutingTable.updateRouteTree(addr_);
 	};
 };