summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorOthmar Gsenger <otti@anytun.org>2008-12-22 01:38:19 +0000
committerOthmar Gsenger <otti@anytun.org>2008-12-22 01:38:19 +0000
commitdd37bc54dae219e4d1975f014ec36c221ec4db20 (patch)
tree38e7f427b0ae736841f4193935e39aae500a16dd
parentadded route option to anytun (diff)
new routing system
supports ipv4 and ipv6 routing with subnetting
-rw-r--r--src/Makefile7
-rw-r--r--src/networkAddress.cpp22
-rw-r--r--src/networkAddress.h8
-rw-r--r--src/networkPrefix.cpp2
-rw-r--r--src/networkPrefix.h2
-rw-r--r--src/routingTable.cpp60
-rw-r--r--src/routingTable.h6
-rw-r--r--src/routingTreeNode.cpp64
-rw-r--r--src/routingTreeNode.h53
-rw-r--r--src/routingTreeWalker.hpp57
-rw-r--r--src/syncRouteCommand.h1
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_);
};
};