From dd37bc54dae219e4d1975f014ec36c221ec4db20 Mon Sep 17 00:00:00 2001 From: Othmar Gsenger Date: Mon, 22 Dec 2008 01:38:19 +0000 Subject: new routing system supports ipv4 and ipv6 routing with subnetting --- src/Makefile | 7 +++++- src/networkAddress.cpp | 22 ++++++++++++++++ src/networkAddress.h | 8 ++++++ src/networkPrefix.cpp | 2 +- src/networkPrefix.h | 2 +- src/routingTable.cpp | 60 ++++++++++++++++++++++++++++++++++++-------- src/routingTable.h | 6 ++++- src/routingTreeNode.cpp | 64 +++++++++++++++++++++++++++++++++++++++++++++++ src/routingTreeNode.h | 53 +++++++++++++++++++++++++++++++++++++++ src/routingTreeWalker.hpp | 57 +++++++++++++++++++++++++++++++++++++++++ src/syncRouteCommand.h | 1 + 11 files changed, 268 insertions(+), 14 deletions(-) create mode 100644 src/routingTreeNode.cpp create mode 100644 src/routingTreeNode.h create mode 100644 src/routingTreeWalker.hpp 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 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 #include +#include + +typedef boost::array 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 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 routes_; + boost::array 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 + * + * 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 . + */ +#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 << " -> " <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 + * + * 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 . + */ + +#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 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 +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 +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;levelnodes_[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_); }; }; -- cgit v1.2.3