New LookupIPRoute3 and adapted RadixIPLookup
Brecht Vermeulen
brecht.vermeulen at rug.ac.be
Thu Jan 17 23:31:51 EST 2002
Hi,
in attachment you can find:
* a new element called LookupIPRoute3 (I hadn't more inspiration :-) )
combined with an adapted iptable3 :
- basically the same as staticiplookup, but
- this element sorts its routing entries according the longest prefix
rule so that the route for a destination is found when the first
matching entry is reached
- it is possible to add and remove routes via the handler (inspired on
iproutetable)
* an adapted radixiplookup2 combined with iproutetable2 :
- route caching is inserted inspired on staticiplookup
- some bugs are fixed, so it works now (a.o. configure is added so
that routes can be added on startup)
- only adding routes doesn't work because the entry is inserted
wrongly I think (but I haven't dived in the radix algorithm, because for
small tables (e.g. 16 entries) lookupiproute3 is faster and that's where
we will use it. So if someone else could fix this ?
* the generated manpages for these elements
Maybe RadixIPLookup2 can be renamed to RadixIPLookup and substitute the
buggy version in CVS ?
Are there known other measurements with routing tables in click ?
regards,
Brecht
-------------- next part --------------
.\" -*- mode: nroff -*-
.\" Generated by `click-elem2man' from `iproutetable2.hh'
.de M
.IR "\\$1" "(\\$2)\\$3"
..
.de RM
.RI "\\$1" "\\$2" "(\\$3)\\$4"
..
.TH "IPROUTETABLE" n "17/Jan/2002" "Click"
.SH "NAME"
IPRouteTable - Click element;
ip routing table super class
.SH "SYNOPSIS"
\fBIPRouteTable\fR
.br
.SH "DESCRIPTION"
\fBIPRouteTable\fR defines the interface each IP routing table lookup
element must implement.
.PP
\fBIPRouteTable\fR expects IP packets with dest IP addr annotations. for
each packet, it looks up the dest IP addr annotation in the routing
table, replaces the dest IP addr annotation with the new gateway,
and pushes the packet out on one of the outputs.
.PP
Subclasses of \fBIPRouteTable\fR needs to implement four routines:
add_route, remove_route, lookup_route, and dump_routes. Replacing
annotation and pushing packets around are all taken care of by
\fBIPRouteTable\fR. the signatures for the routines that need to be
written are:
.PP
void add_route(IPAddress dst, IPAddress mask, IPAddress gw, int port);
void remove_route(IPAddress dst, IPAddress mask);
int lookup_route(IPAddress dst, IPAddress &gw); // returns port
String dump_routes();
.PP
.SH "ELEMENT HANDLERS"
.IP "\fBctrl\fR (write)" 5
Take in changes to the routing table, in the format of
.IP "" 5
.nf
\& add ip/mask [gw] output
\& remove ip/mask
.fi
.IP "" 5
for example,
.IP "" 5
.nf
\& add 18.26.4.0/24 18.26.4.1 0
.fi
.IP "" 5
says all packets to 18.26.4.0/24 subnet should use gateway
18.26.4.1, and go out on output port 0. and
.IP "" 5
.nf
\& remove 18.26.4.0/24
.fi
.IP "" 5
removes the route.
.IP "" 5
.IP "\fBlook\fR (read-only)" 5
Returns the contents of the routing table.
.IP "" 5
.PP
.SH "SEE ALSO"
.M LookupIPRoute n ,
.M RadixIPLookup n
-------------- next part --------------
/*
* iproutetable.{cc,hh} -- looks up next-hop address in route table
* Benjie Chen
*
* Copyright (c) 2001 Massachusetts Institute of Technology
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, subject to the conditions listed in the Click LICENSE
* file. These conditions include: you must preserve this copyright
* notice, and you cannot mention the copyright holders in advertising
* related to the Software without their permission. The Software is
* provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This notice is a
* summary of the Click LICENSE file; the license in that file is
* legally binding.
*/
#include <click/config.h>
#include <click/ipaddress.hh>
#include <click/confparse.hh>
#include <click/error.hh>
#include <click/glue.hh>
#include "iproutetable2.hh"
IPRouteTable2::IPRouteTable2()
{
MOD_INC_USE_COUNT;
add_input();
add_output();
}
IPRouteTable2::~IPRouteTable2()
{
MOD_DEC_USE_COUNT;
}
int
IPRouteTable2::ctrl_handler
(const String &conf, Element *e, void *, ErrorHandler *errh)
{
unsigned int dst, mask, gw=0;
int output_num;
bool ok = false;
IPRouteTable2 *r = reinterpret_cast<IPRouteTable2*>(e);
Vector<String> words;
cp_spacevec(conf, words);
if (words[0] == "add") {
if ((words.size() == 3 || words.size() == 4)
&& cp_ip_prefix(words[1], (unsigned char *)&dst,
(unsigned char *)&mask, true, r)
&& cp_integer(words.back(), &output_num)) {
if (words.size() == 4)
ok = cp_ip_address(words[2], (unsigned char *)&gw, r);
else
ok = true;
}
if (ok && output_num >= 0 && output_num < r->noutputs())
r->add_route(dst, mask, gw, output_num);
else if (output_num < 0 || output_num >= r->noutputs())
return
errh->error("output number must be between 0 and %d", r->noutputs());
else
return
errh->error("add arguments should be `daddr/mask [gateway] output'");
}
else if (words[0] == "remove") {
click_chatter("remove in iproutetable2 : words.size() %d", words.size() );
if (words.size() == 2 &&
cp_ip_prefix
(words[1], (unsigned char *)&dst, (unsigned char *)&mask, true, r))
r->remove_route(dst, mask);
// cleaning cache, otherwise for the cached destination, the route won't
// be deleted (ideally, we should only clean the cache if the cached
// destination is implied by the route, but ...)
r->clean_cache();
}
else
return errh->error("command must be add or remove");
return 0;
}
void
IPRouteTable2::clean_cache()
{
_last_addr = 0;
#ifdef IP_RT_CACHE2
_last_addr2 = 0;
#endif
}
String
IPRouteTable2::look_handler(Element *e, void *)
{
IPRouteTable2 *r = reinterpret_cast<IPRouteTable2*>(e);
return r->dump_routes();
}
void
IPRouteTable2::push(int, Packet *p)
{
IPAddress a = p->dst_ip_anno();
IPAddress gw;
int port = -1;
if (a) {
if (a == _last_addr) {
// click_chatter("jieho, cached");
if (_last_gw)
p->set_dst_ip_anno(_last_gw);
output(_last_output).push(p);
return;
}
#ifdef IP_RT_CACHE2
else if (a == _last_addr2) {
if (_last_gw2)
p->set_dst_ip_anno(_last_gw2);
output(_last_output2).push(p);
return;
}
#endif
}
if ((port = lookup_route(a, gw)) >= 0) {
#ifdef IP_RT_CACHE2
_last_addr2 = _last_addr;
_last_gw2 = _last_gw;
_last_output2 = _last_output;
#endif
_last_addr = a;
_last_gw = gw;
_last_output = port;
if (gw)
p->set_dst_ip_anno(gw);
output(port).push(p);
} else {
click_chatter("IPRouteTable: no route for %x,"+a.unparse(), a.addr());
p->kill();
}
}
void
IPRouteTable2::add_handlers()
{
add_write_handler("ctrl", ctrl_handler, 0);
add_read_handler("look", look_handler, 0);
}
EXPORT_ELEMENT(IPRouteTable2)
-------------- next part --------------
#ifndef IPROUTETABLE2_HH
#define IPROUTETABLE2_HH
/*
* =c
* IPRouteTable
* =s IP, classification
* ip routing table super class
* =d
*
* IPRouteTable defines the interface each IP routing table lookup
* element must implement.
*
* IPRouteTable expects IP packets with dest IP addr annotations. for
* each packet, it looks up the dest IP addr annotation in the routing
* table, replaces the dest IP addr annotation with the new gateway,
* and pushes the packet out on one of the outputs.
*
* Subclasses of IPRouteTable needs to implement four routines:
* add_route, remove_route, lookup_route, and dump_routes. Replacing
* annotation and pushing packets around are all taken care of by
* IPRouteTable. the signatures for the routines that need to be
* written are:
*
* void add_route(IPAddress dst, IPAddress mask, IPAddress gw, int port);
* void remove_route(IPAddress dst, IPAddress mask);
* int lookup_route(IPAddress dst, IPAddress &gw); // returns port
* String dump_routes();
*
* =h ctrl write
* Take in changes to the routing table, in the format of
*
* add ip/mask [gw] output
* remove ip/mask
*
* for example,
*
* add 18.26.4.0/24 18.26.4.1 0
*
* says all packets to 18.26.4.0/24 subnet should use gateway
* 18.26.4.1, and go out on output port 0. and
*
* remove 18.26.4.0/24
*
* removes the route.
*
* =h look read-only
* Returns the contents of the routing table.
*
* =a LookupIPRoute, RadixIPLookup
*/
#include <click/glue.hh>
#include <click/element.hh>
#define IP_RT_CACHE2 1
class IPRouteTable2 : public Element {
public:
IPRouteTable2();
~IPRouteTable2();
const char *class_name() const { return "IPRouteTable2"; }
const char *processing() const { return PUSH; }
virtual int initialize(ErrorHandler *){ return 0; }
virtual IPRouteTable2 *clone() const { return new IPRouteTable2; }
virtual int configure(const Vector<String> &, ErrorHandler *)
{ return 0; }
virtual String dump_routes() { return ""; }
virtual void add_route(IPAddress, IPAddress, IPAddress, int) {}
virtual void remove_route(IPAddress, IPAddress) {}
virtual int lookup_route(IPAddress, IPAddress &) { return -1; }
virtual void uninitialize() {}
void push(int port, Packet *p);
static int ctrl_handler
(const String &conf, Element *e, void *, ErrorHandler *errh);
static String look_handler(Element *, void *);
void add_handlers();
void clean_cache();
private:
IPAddress _last_addr;
IPAddress _last_gw;
int _last_output;
#ifdef IP_RT_CACHE2
IPAddress _last_addr2;
IPAddress _last_gw2;
int _last_output2;
#endif
};
#endif
-------------- next part --------------
// -*- c-basic-offset: 2; related-file-name: "../include/click/iptable.hh" -*-
/*
* iptable.{cc,hh} -- a stupid IP routing table, best for small routing tables
* Robert Morris
* Brecht Vermeulen, Jan. 2002, slightly optimised and made dynamic
*
* Copyright (c) 1999-2000 Massachusetts Institute of Technology
* Copyright (c) 2002 Ghent University, Belgium
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, subject to the conditions
* listed in the Click LICENSE file. These conditions include: you must
* preserve this copyright notice, and you cannot mention the copyright
* holders in advertising related to the Software without their permission.
* The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
* notice is a summary of the Click LICENSE file; the license in that file is
* legally binding.
*/
#include <click/config.h>
#include "iptable3.hh"
IPTable3::IPTable3()
{
_v = new Vector<Entry>();
}
IPTable3::~IPTable3()
{
delete _v;
}
bool
IPTable3::lookup(IPAddress dst, IPAddress &gw, int &index) const
{
int best = -1;
// longest prefix match
for (int i = 0; i < _v->size(); i++)
if (dst.matches_prefix( (*_v)[i].dst, (*_v)[i].mask)) {
gw = (*_v)[i].gw;
index = (*_v)[i].index;
return true;
}
return false;
}
void
IPTable3::add(IPAddress dst, IPAddress mask, IPAddress gw, int index)
{
dst &= mask;
struct Entry e;
e.dst = dst;
e.mask = mask;
e.gw = gw;
e.index = index;
if (_v->size() == 0) { //table empty
_v->push_back(e);
return;
}
// default route
if (dst == 0 && mask == 0) {
if ( _v->back().dst == 0 && _v->back().mask == 0)
click_chatter("default route exists already");
else
_v->push_back(e);
return;
};
for (unsigned int i = 0; i < _v->size(); i++) {
// algorithm : the new entry is compared with those in the table and
// only if the new entry is in the subnet of an existing route (and thus more
// specific (longer netmask) it is inserted in the table, otherwise it is put
// at the end (but before the default route). If the entry already exists (can also
// be with other gateway) it is thrashed
if (dst == (*_v)[i].dst & mask == (*_v)[i].mask ) {
click_chatter("destination/mask exists already");
return;
}
if (mask.mask_more_specific( (*_v)[i].mask) ) {
// 'mask' is longer than the mask of the list entry i or equal
if ( dst.matches_prefix( (*_v)[i].dst, (*_v)[i].mask ) ) {
// okay, the new entry is in the subnet of the entry in the table but has a longer mask
// so insert e before the existing entry (on position i)
insert(i, e);
return;
}
}
}
// there wasn't an appropriate place in the list
if ( _v->back().dst == 0 && _v->back().mask == 0)
// last entry is default route, so it must be on the one but the last position
insert(_v->size()-1,e);
else
_v->push_back(e);
return;
}
void
IPTable3::insert(unsigned int position, struct Entry e)
{
if (position == _v->size() ) {
_v->push_back(e);
return;
}
Vector<Entry> *tmp = _v;
_v = new Vector<Entry>();
for(int i=0; i < position;i++) {
_v->push_back( (*tmp)[i] );
}
_v->push_back(e);
for(int i=position; i < tmp->size();i++) {
_v->push_back( (*tmp)[i] );
}
delete tmp;
}
void
IPTable3::del(IPAddress dst, IPAddress mask)
{
Vector<Entry> *tmp = _v;
_v = new Vector<Entry>();
for(int i=0; i < tmp->size();i++) {
if ( (*tmp)[i].dst != dst || (*tmp)[i].mask != mask)
_v->push_back( (*tmp)[i] );
}
if (_v->size() == tmp->size() )
click_chatter("route "+dst.unparse() + mask.unparse()+" to remove, not found !");
delete tmp;
}
String
IPTable3::dump_routes() {
String ret;
ret = "Entries: " + String(_v->size()) + "\nDST/MASK\tGW\tPORT\n";
if(_v->size() == 0)
return ret;
for(int i = 0; i < _v->size(); i++)
ret += (*_v)[i].dst.unparse() +"/" + \
(*_v)[i].mask.unparse() +"\t" + \
(*_v)[i].gw.unparse() +"\t" + \
String((*_v)[i].index) +"\n";
return ret;
}
// generate Vector template instance
#include <click/vector.cc>
// must always generate the whole instance! LookupIPRoute demands it
template class Vector<IPTable3::Entry>;
-------------- next part --------------
// -*- c-basic-offset: 2; related-file-name: "../../lib/iptable3.cc" -*-
#ifndef CLICK_IPTABLE3_HH
#define CLICK_IPTABLE3_HH
#include <click/glue.hh>
#include <click/vector.hh>
#include <click/ipaddress.hh>
// IP routing table.
// Lookup by longest prefix.
// Each entry contains a gateway and an output index.
// The entries are sorted according longest prefix in the table
// so the first entry in the list which matches a destination is okay
// So it is based on the standard iptable.{hh,cc}, but there all entries
// are run through to match a destination. Here you can put
// the most used routes in front and it should be faster.
class IPTable3 { public:
IPTable3();
~IPTable3();
bool lookup(IPAddress dst, IPAddress &gw, int &index) const;
void add(IPAddress dst, IPAddress mask, IPAddress gw, int index);
void del(IPAddress dst, IPAddress mask);
String dump_routes();
void clear() { _v->clear(); }
private:
struct Entry {
IPAddress dst;
IPAddress mask;
IPAddress gw;
int index;
};
Vector<Entry> *_v;
void insert(unsigned int position, struct Entry e);
};
#endif
-------------- next part --------------
/*
* lookupiproute3.{cc,hh} -- element looks up next-hop address in static
* routing table
* Robert Morris
* Brecht Vermeulen, Jan. 2002: slight performance improvement and made it
* dynamic
*
* Copyright (c) 1999-2000 Massachusetts Institute of Technology
* Copyright (c) 2002 Ghent University, Belgium
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, subject to the conditions
* listed in the Click LICENSE file. These conditions include: you must
* preserve this copyright notice, and you cannot mention the copyright
* holders in advertising related to the Software without their permission.
* The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
* notice is a summary of the Click LICENSE file; the license in that file is
* legally binding.
*/
#include <click/config.h>
#include "lookupiproute3.hh"
#include <click/ipaddress.hh>
#include <click/confparse.hh>
#include <click/error.hh>
#include <click/glue.hh>
LookupIPRoute3::LookupIPRoute3()
{
MOD_INC_USE_COUNT;
add_input();
}
LookupIPRoute3::~LookupIPRoute3()
{
MOD_DEC_USE_COUNT;
}
LookupIPRoute3 *
LookupIPRoute3::clone() const
{
return new LookupIPRoute3;
}
int
LookupIPRoute3::configure(const Vector<String> &conf, ErrorHandler *errh)
{
int maxout = -1;
_t.clear();
int before = errh->nerrors();
for (int i = 0; i < conf.size(); i++) {
uint32_t dst, mask, gw = 0;
int32_t output_num;
bool ok = false;
Vector<String> words;
cp_spacevec(conf[i], words);
if ((words.size() == 2 || words.size() == 3)
&& cp_ip_prefix(words[0], (unsigned char *)&dst, (unsigned char *)&mask, true, this) // allow base IP addresses
&& cp_integer(words.back(), &output_num)) {
if (words.size() == 3)
ok = cp_ip_address(words[1], (unsigned char *)&gw, this);
else
ok = true;
}
if (ok && output_num >= 0) {
_t.add(dst, mask, gw, output_num);
if (output_num > maxout)
maxout = output_num;
} else
errh->error("argument %d should be `DADDR/MASK [GATEWAY] OUTPUT'", i+1);
}
if (errh->nerrors() != before)
return -1;
if (maxout < 0)
errh->warning("no routes");
set_noutputs(maxout + 1);
return 0;
}
int
LookupIPRoute3::live_reconfigure(const Vector<String> &conf, ErrorHandler *errh)
{
_t.clear();
int before = errh->nerrors();
for (int i = 0; i < conf.size(); i++) {
uint32_t dst, mask, gw = 0;
int32_t output_num;
bool ok = false;
Vector<String> words;
cp_spacevec(conf[i], words);
if ((words.size() == 2 || words.size() == 3)
&& cp_ip_prefix(words[0], (unsigned char *)&dst, (unsigned char *)&mask, true, this) // allow base IP addresses
&& cp_integer(words.back(), &output_num)) {
if (words.size() == 3)
ok = cp_ip_address(words[1], (unsigned char *)&gw, this);
else
ok = true;
}
if (ok && output_num >= 0) {
if (output_num > noutputs() )
errh->error("argument %d has a bad output port !", i+1);
else
_t.add(dst, mask, gw, output_num);
} else
errh->error("argument %d should be `DADDR/MASK [GATEWAY] OUTPUT'", i+1);
}
if (errh->nerrors() != before)
return -1;
return 0;
}
int
LookupIPRoute3::initialize(ErrorHandler *)
{
_last_addr = IPAddress();
#ifdef IP_RT_CACHE2
_last_addr2 = _last_addr;
#endif
return 0;
}
void
LookupIPRoute3::push(int, Packet *p)
{
#define EXCHANGE(a,b,t) { t = a; a = b; b = t; }
IPAddress a = p->dst_ip_anno();
IPAddress gw;
int ifi = -1;
if (a) {
if (a == _last_addr) {
if (_last_gw)
p->set_dst_ip_anno(_last_gw);
output(_last_output).push(p);
return;
}
#ifdef IP_RT_CACHE2
else if (a == _last_addr2) {
#if 0
IPAddress tmpa;
int tmpi;
EXCHANGE(_last_addr, _last_addr2, tmpa);
EXCHANGE(_last_gw, _last_gw2, tmpa);
EXCHANGE(_last_output, _last_output2, tmpi);
#endif
if (_last_gw2)
p->set_dst_ip_anno(_last_gw2);
output(_last_output2).push(p);
return;
}
#endif
}
if (_t.lookup(a, gw, ifi) == true) {
#ifdef IP_RT_CACHE2
_last_addr2 = _last_addr;
_last_gw2 = _last_gw;
_last_output2 = _last_output;
#endif
_last_addr = a;
_last_gw = gw;
_last_output = ifi;
if (gw)
p->set_dst_ip_anno(IPAddress(gw));
output(ifi).push(p);
} else {
click_chatter("LookupIPRoute3: no gw for %x", a.addr());
p->kill();
}
}
int
LookupIPRoute3::ctrl_handler
(const String &conf, Element *e, void *, ErrorHandler *errh)
{
unsigned int dst, mask, gw=0;
int output_num;
bool ok = false;
LookupIPRoute3 *r = reinterpret_cast<LookupIPRoute3*>(e);
Vector<String> words;
cp_spacevec(conf, words);
if (words[0] == "add") {
if ((words.size() == 3 || words.size() == 4)
&& cp_ip_prefix(words[1], (unsigned char *)&dst,
(unsigned char *)&mask, true, r)
&& cp_integer(words.back(), &output_num)) {
if (words.size() == 4)
ok = cp_ip_address(words[2], (unsigned char *)&gw, r);
else
ok = true;
}
if (ok && output_num >= 0 && output_num < r->noutputs()) // we cannot create extra outputs!
r->_t.add(dst, mask, gw, output_num);
else if (output_num < 0 || output_num >= r->noutputs())
return
errh->error("output number must be between 0 and %d", r->noutputs());
else
return
errh->error("add arguments should be `daddr/mask [gateway] output'");
}
else if (words[0] == "remove") {
if (words.size() == 2 && //dest/mask = 1 word
cp_ip_prefix
(words[1], (unsigned char *)&dst, (unsigned char *)&mask, true, r)) {
r->_t.del(dst, mask);
// cleaning cache, otherwise for the cached destination, the route won't
// be deleted (we only clean the cache if the cached destination suits the route
// (it is possible that there is still another route which was cached of course)
if (r->_last_addr.matches_prefix( dst, mask)) {
r->_last_addr = IPAddress();
r->_last_gw = IPAddress();
r->_last_output = 0;
}
if (r->_last_addr2.matches_prefix( dst, mask)) {
r->_last_addr2 = IPAddress();
r->_last_gw2 = IPAddress();
r->_last_output2 = 0;
}
}
}
else
return errh->error("command must be add or remove");
return 0;
}
String
LookupIPRoute3::look_handler(Element *e, void *)
{
LookupIPRoute3 *r = reinterpret_cast<LookupIPRoute3*>(e);
return r->_t.dump_routes();
}
void
LookupIPRoute3::add_handlers()
{
add_write_handler("ctrl", ctrl_handler, 0);
add_read_handler("showroutes", look_handler, 0);
}
EXPORT_ELEMENT(LookupIPRoute3)
-------------- next part --------------
#ifndef LOOKUPIPROUTE3_HH
#define LOOKUPIPROUTE3_HH
/*
* =c
* LookupIPRoute3(DST1/MASK1 [GW1] OUT1, DST2/MASK2 [GW2] OUT2, ...)
* =s IP, classification
* simple dynamic IP routing table
* =d
* Input: IP packets (no ether header).
* Expects a destination IP address annotation with each packet.
* Looks up the address, sets the destination annotation to
* the corresponding GW (if specified), and emits the packet
* on the indicated OUTput.
*
* Each comma-separated argument is a route, specifying
* a destination and mask; optionally, a gateway IP address;
* and an output index. The entries are sorted in the longest prefix way,
* so, you can specify routes in the sequence you want (but
* the first routes are kept as high as possible, so you can put frequently
* used routes in front).
*
* Difference with standard StaticIPLookup is a slight performance
* improvement (the route table is sorted on insertion, so for a lookup
* the table is only checked till the first matching entry) and routes
* can be added and removed from this table (without creating new
* output ports of course)
*
* This element is faster on smaller routing tables (tested with 16 entries
* and smaller) than radixiplookup. Not tested yet for more entries.
*
* =e
* This example delivers broadcasts and packets addressed to the local
* host (18.26.4.24) to itself, packets to net 18.26.4 to the
* local interface, and all others via gateway 18.26.4.1:
*
* ... -> GetIPAddress(16) -> rt;
* rt :: LookupIPRoute3(18.26.4.24/32 0,
* 18.26.4.255/32 0,
* 18.26.4.0/32 0,
* 18.26.4.0/24 1,
* 0.0.0.0/0 18.26.4.1 1);
* rt[0] -> ToLinux;
* rt[1] -> ... -> ToDevice(eth0);
*
* =h ctrl write-only
* Take in changes to the routing table, in the format of
*
* add ip/mask [gw] output
* remove ip/mask
*
* for example,
*
* add 18.26.4.0/24 18.26.4.1 0
*
* says all packets to 18.26.4.0/24 subnet should use gateway
* 18.26.4.1, and go out on output port 0. and
*
* remove 18.26.4.0/24
*
* removes the route.
* =h showroutes read-only
* Returns the (sorted) contents of the routing table.
*
* =n
* If you need a dynamic routing
* protocol such as RIP, run it at user-level and let it talk via the
* ctrl handler
*
* =a StaticIPLookup, RadixIPLookup
*/
#include <click/element.hh>
#include <iptable3.hh>
#define IP_RT_CACHE2 1
class LookupIPRoute3 : public Element {
public:
LookupIPRoute3();
~LookupIPRoute3();
const char *class_name() const { return "LookupIPRoute3"; }
const char *processing() const { return PUSH; }
LookupIPRoute3 *clone() const;
int configure(const Vector<String> &, ErrorHandler *);
bool can_live_reconfigure() const { return true; }
int live_reconfigure(const Vector<String> &, ErrorHandler *);
int initialize(ErrorHandler *);
void push(int port, Packet *p);
static int ctrl_handler
(const String &conf, Element *e, void *, ErrorHandler *errh);
static String look_handler(Element *, void *);
void add_handlers();
private:
IPTable3 _t;
// route caching 1 or 2 addresses
IPAddress _last_addr;
IPAddress _last_gw;
int _last_output;
#ifdef IP_RT_CACHE2
IPAddress _last_addr2;
IPAddress _last_gw2;
int _last_output2;
#endif
};
#endif
-------------- next part --------------
.\" -*- mode: nroff -*-
.\" Generated by `click-elem2man' from `lookupiproute3.hh'
.de M
.IR "\\$1" "(\\$2)\\$3"
..
.de RM
.RI "\\$1" "\\$2" "(\\$3)\\$4"
..
.TH "LOOKUPIPROUTE3" n "17/Jan/2002" "Click"
.SH "NAME"
LookupIPRoute3 - Click element;
simple dynamic IP routing table
.SH "SYNOPSIS"
\fBLookupIPRoute3\fR(DST1/MASK1 [GW1] OUT1, DST2/MASK2 [GW2] OUT2, ...)
.br
.SH "PROCESSING TYPE"
Push
.SH "DESCRIPTION"
Input: IP packets (no ether header).
Expects a destination IP address annotation with each packet.
Looks up the address, sets the destination annotation to
the corresponding GW (if specified), and emits the packet
on the indicated OUTput.
.PP
Each comma-separated argument is a route, specifying
a destination and mask; optionally, a gateway IP address;
and an output index. The entries are sorted in the longest prefix way,
so, you can specify routes in the sequence you want (but
the first routes are kept as high as possible, so you can put frequently
used routes in front).
.PP
Difference with standard
.M StaticIPLookup "n"
is a slight performance
improvement (the route table is sorted on insertion, so for a lookup
the table is only checked till the first matching entry) and routes
can be added and removed from this table (without creating new
output ports of course)
.PP
This element is faster on smaller routing tables (tested with 16 entries
and smaller) than radixiplookup. Not tested yet for more entries.
.PP
.SH "EXAMPLES"
This example delivers broadcasts and packets addressed to the local
host (18.26.4.24) to itself, packets to net 18.26.4 to the
local interface, and all others via gateway 18.26.4.1:
.PP
.nf
\& ... -> GetIPAddress(16) -> rt;
\& rt :: LookupIPRoute3(18.26.4.24/32 0,
\& 18.26.4.255/32 0,
\& 18.26.4.0/32 0,
\& 18.26.4.0/24 1,
\& 0.0.0.0/0 18.26.4.1 1);
\& rt[0] -> ToLinux;
\& rt[1] -> ... -> ToDevice(eth0);
.fi
.PP
.SH "ELEMENT HANDLERS"
.IP "\fBctrl\fR (write-only)" 5
Take in changes to the routing table, in the format of
.IP "" 5
.nf
\& add ip/mask [gw] output
\& remove ip/mask
.fi
.IP "" 5
for example,
.IP "" 5
.nf
\& add 18.26.4.0/24 18.26.4.1 0
.fi
.IP "" 5
says all packets to 18.26.4.0/24 subnet should use gateway
18.26.4.1, and go out on output port 0. and
.IP "" 5
.nf
\& remove 18.26.4.0/24
.fi
.IP "" 5
removes the route.
.IP "" 5
.IP "\fBshowroutes\fR (read-only)" 5
Returns the (sorted) contents of the routing table.
.IP "" 5
.PP
.SH "NOTES"
If you need a dynamic routing
protocol such as RIP, run it at user-level and let it talk via the
ctrl handler
.PP
.SH "SEE ALSO"
.M StaticIPLookup n ,
.M RadixIPLookup n
-------------- next part --------------
/*
* radixiplookup2.{cc,hh} -- looks up next-hop address in radix table
* Thomer M. Gil
* Brecht Vermeulen, Jan. 2002 : introduced configure + route cache
*
* Copyright (c) 1999-2001 Massachusetts Institute of Technology
* Copyright (c) 2002 Ghent University, Belgium
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, subject to the conditions listed in the Click LICENSE
* file. These conditions include: you must preserve this copyright
* notice, and you cannot mention the copyright holders in advertising
* related to the Software without their permission. The Software is
* provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This notice is a
* summary of the Click LICENSE file; the license in that file is
* legally binding.
*/
#include <click/config.h>
#include <click/ipaddress.hh>
#include <click/confparse.hh>
#include <click/error.hh>
#include <click/glue.hh>
#include "radixiplookup2.hh"
RadixIPLookup2::RadixIPLookup2()
: _entries(0)
{
MOD_INC_USE_COUNT;
_radix = new Radix2;
}
RadixIPLookup2::~RadixIPLookup2()
{
MOD_DEC_USE_COUNT;
uninitialize();
}
int
RadixIPLookup2::configure(const Vector<String> &conf, ErrorHandler *errh)
{
int maxout = -1;
int before = errh->nerrors();
for (int i = 0; i < conf.size(); i++) {
uint32_t dst, mask, gw = 0;
int32_t output_num;
bool ok = false;
Vector<String> words;
cp_spacevec(conf[i], words);
if ((words.size() == 2 || words.size() == 3)
&& cp_ip_prefix(words[0], (unsigned char *)&dst, (unsigned char *)&mask, true, this) // allow base IP addresses
&& cp_integer(words.back(), &output_num)) {
if (words.size() == 3)
ok = cp_ip_address(words[1], (unsigned char *)&gw, this);
else
ok = true;
}
if (ok && output_num >= 0) {
add_route_uint32(dst, mask, gw, output_num);
if (output_num > maxout)
maxout = output_num;
} else
errh->error("argument %d should be `DADDR/MASK [GATEWAY] OUTPUT'", i+1);
}
if (errh->nerrors() != before)
return -1;
if (maxout < 0)
errh->warning("no routes");
set_noutputs(maxout + 1);
return 0;
}
void
RadixIPLookup2::uninitialize()
{
for(int i=0; i < _v.size(); i++) {
if (_v[i])
delete _v[i];
_v[i] = 0;
}
if (_radix)
delete _radix;
_radix = 0;
}
String
RadixIPLookup2::dump_routes()
{
String ret;
unsigned dst, mask, gw, port;
ret = "Entries: " + String(_entries) + "\nDST/MASK\tGW\tPORT\n";
if(_entries == 0)
return ret;
int seen = 0; // # of valid entries handled
for(int i = 0; seen < _entries; i++) {
if (get(i, dst, mask, gw, port)) {
ret += IPAddress(dst).s() + "/" + \
IPAddress(mask).s()+ "\t" + \
IPAddress(gw).s() + "\t" + \
String(port)+ "\n";
seen++;
}
}
return ret;
}
void
RadixIPLookup2::add_route(IPAddress d, IPAddress m, IPAddress g, int port)
{
unsigned dst = d.addr();
unsigned mask = m.addr();
unsigned gw = g.addr();
add_route_uint32(dst, mask, gw, port);
}
void
RadixIPLookup2::add_route_uint32(uint32_t dst, uint32_t mask, uint32_t gw, int port)
{
dst &= mask;
for(int i = 0; i < _v.size(); i++)
if(_v[i]->valid && (_v[i]->dst == dst) && (_v[i]->mask == mask)) {
_v[i]->gw = gw;
_v[i]->port = port;
return;
}
struct Entry *e = new Entry;
e->dst = dst;
e->mask = mask;
e->gw = gw;
e->port = port;
e->valid = true;
_v.push_back(e);
_entries++;
_radix->insert((dst & mask), _v.size()-1);
}
void
RadixIPLookup2::remove_route(IPAddress d, IPAddress m)
{
unsigned dst = d.addr();
unsigned mask = m.addr();
click_chatter("remove_route "+d.unparse()+" "+m.unparse() );
for(int i = 0; i < _v.size(); i++){
if(_v[i]->valid && (_v[i]->dst == dst) && (_v[i]->mask == mask)) {
_v[i]->valid = 0;
_entries--;
_radix->del(dst & mask);
click_chatter("radix remove : %d %d %d", dst, mask, dst & mask);
return;
}
}
}
int
RadixIPLookup2::lookup_route(IPAddress d, IPAddress &gw)
{
unsigned dst = d.addr();
int index;
if(!_entries || !_radix->lookup(dst, index)) {
click_chatter("RadixIPLookup::lookup_route : no match in radix table");
goto nomatch;
}
// consider this a match if dst is part of range described by routing table
if((dst & _v[index]->mask) == (_v[index]->dst & _v[index]->mask)) {
gw = _v[index]->gw;
//click_chatter("output port found in table %d",_v[index]->port);
return _v[index]->port;
} else {
click_chatter("entry not found in routing table");
}
nomatch:
gw = 0;
return -1;
}
bool
RadixIPLookup2::get
(int i, unsigned &dst, unsigned &mask, unsigned &gw, unsigned &port)
{
assert(i >= 0 && i < _v.size());
if(i < 0 || i >= _v.size() || _v[i]->valid == 0) {
dst = mask = gw = port = 0;
return false;
}
dst = _v[i]->dst;
mask = _v[i]->mask;
gw = _v[i]->gw;
port = _v[i]->port;
return true;
}
// generate Vector template instance
#include <click/vector.cc>
template class Vector<RadixIPLookup2::Entry>;
EXPORT_ELEMENT(RadixIPLookup2)
-------------- next part --------------
#ifndef RADIXIPLOOKUP2_HH
#define RADIXIPLOOKUP2_HH
/*
* =c
* RadixIPLookup2(DST1/MASK1 [GW1] OUT1, DST2/MASK2 [GW2] OUT2, ...)
* =s IP, classification
* IP lookup using a radix table
* =d
*
* Performs IP lookup using a radix table, using the IPRouteTable2
* interface.
*
* Each comma-separated argument is a route, specifying
* a destination and mask; optionally, a gateway IP address;
* and an output index.
*
* =e
* This example delivers broadcasts and packets addressed to the local
* host (18.26.4.24) to itself, packets to net 18.26.4 to the
* local interface, and all others via gateway 18.26.4.1:
*
* ... -> GetIPAddress(16) -> rt;
* rt :: RadixIPLookup2(18.26.4.24/32 0,
* 18.26.4.255/32 0,
* 18.26.4.0/32 0,
* 18.26.4.0/24 1,
* 0.0.0.0/0 18.26.4.1 1);
* rt[0] -> ToLinux;
* rt[1] -> ... -> ToDevice(eth0);
*
* =h ctrl write-only
* Take in changes to the routing table, in the format of
*
* add ip/mask [gw] output
* remove ip/mask
*
* for example,
*
* add 18.26.4.0/24 18.26.4.1 0
* (NOTE: add doesn't work, the entry is inserted at the back and
* doesn't work)
*
* says all packets to 18.26.4.0/24 subnet should use gateway
* 18.26.4.1, and go out on output port 0. and
*
* remove 18.26.4.0/24
*
* removes the route.
* =h showroutes read-only
* Returns the (sorted) contents of the routing table.
* =a StaticIPLookup, LookupIPRoute3
*/
#include <click/glue.hh>
#include <click/element.hh>
#include "iproutetable2.hh"
class Radix2 {
// implementation take from Sedgewick
public:
Radix2();
~Radix2();
void insert(unsigned v, int info);
void del(unsigned v);
bool lookup(unsigned v, int &info);
private:
struct RadixNode {
unsigned key;
int bit_idx;
RadixNode *left;
RadixNode *right;
bool valid;
int info;
RadixNode() : left(0), right(0), valid(false) { }
void kill();
};
struct RadixNode *root;
static unsigned bits(unsigned x, unsigned y, unsigned char idx);
RadixNode *node_lookup(unsigned v);
static const int KEYSIZE = 32;
};
class RadixIPLookup2 : public IPRouteTable2 {
public:
RadixIPLookup2();
~RadixIPLookup2();
const char *class_name() const { return "RadixIPLookup2"; }
const char *processing() const { return AGNOSTIC; }
RadixIPLookup2 *clone() const { return new RadixIPLookup2; }
int configure(const Vector<String> &, ErrorHandler *);
void uninitialize();
String dump_routes();
void add_route(IPAddress, IPAddress, IPAddress, int);
void add_route_uint32(uint32_t dst, uint32_t mask, uint32_t gw, int port);
void remove_route(IPAddress, IPAddress);
int lookup_route(IPAddress, IPAddress &);
private:
bool get(int i, unsigned &dst, unsigned &mask, unsigned &gw, unsigned &port);
// Simple routing table
struct Entry {
unsigned dst;
unsigned mask;
unsigned gw;
unsigned port;
bool valid;
};
Vector<Entry *> _v;
int _entries;
Radix2 *_radix;
};
inline
Radix2::Radix2()
{
root = new RadixNode;
root->info = root->key = 0;
root->bit_idx = KEYSIZE-1;
root->valid = false;
root->left = root->right = root;
}
inline void
Radix2::RadixNode::kill()
{
if (bit_idx >= 0) {
bit_idx = -1;
if (left) left->kill();
if (right) right->kill();
delete this;
}
}
inline
Radix2::~Radix2()
{
root->kill();
}
inline void
Radix2::insert(unsigned v, int info)
{
RadixNode *t, *p;
int i;
t = node_lookup(v);
if(v == t->key)
return;
// Find bit for which v and t-> key differ
i = KEYSIZE-1;
while(bits(v, i, 1) == bits(t->key, i, 1))
i--;
// Descend to that level
RadixNode *x = root;
do {
p = x;
if(bits(v, x->bit_idx, 1) == 0)
x = x->left;
else
x = x->right;
if((x->bit_idx <= i) || (p->bit_idx <= x->bit_idx))
break;
} while(1);
// ... and instert node
t = new RadixNode;
t->key = v;
t->bit_idx = i;
t->info = info;
t->valid = true;
if(bits(v, t->bit_idx, 1) == 0) {
t->left = t;
t->right = x;
} else {
t->right = t;
t->left = x;
}
if(bits(v, p->bit_idx, 1) == 0)
p->left = t;
else
p->right = t;
}
// returns info based on key
inline bool
Radix2::lookup(unsigned v, int &info)
{
RadixNode *t;
t = node_lookup(v);
if(t->valid) {
info = t->info;
return(true);
} else
return(false);
}
inline void
Radix2::del(unsigned v)
{
RadixNode *t;
t = node_lookup(v);
// only delete if this is an exact match
if(t->key == v)
t->valid = false;
}
// returns node based on key
inline Radix2::RadixNode *
Radix2::node_lookup(unsigned v)
{
RadixNode *p, *x = root;
do {
p = x;
if(bits(v, x->bit_idx, 1) == 0)
x = x->left;
else
x = x->right;
} while(x->bit_idx < p->bit_idx);
return x;
}
// returns j bytes which appear k from rhe right. Rightmost bit has index 0.
inline unsigned
Radix2::bits(unsigned x, unsigned k, unsigned char j)
{
return (x >> k) & (0xffffffff >> (KEYSIZE-j));
}
#endif
-------------- next part --------------
.\" -*- mode: nroff -*-
.\" Generated by `click-elem2man' from `radixiplookup2.hh'
.de M
.IR "\\$1" "(\\$2)\\$3"
..
.de RM
.RI "\\$1" "\\$2" "(\\$3)\\$4"
..
.TH "RADIXIPLOOKUP2" n "17/Jan/2002" "Click"
.SH "NAME"
RadixIPLookup2 - Click element;
IP lookup using a radix table
.SH "SYNOPSIS"
\fBRadixIPLookup2\fR(DST1/MASK1 [GW1] OUT1, DST2/MASK2 [GW2] OUT2, ...)
.br
.SH "PROCESSING TYPE"
Agnostic
.SH "DESCRIPTION"
Performs IP lookup using a radix table, using the IPRouteTable2
interface.
.PP
Each comma-separated argument is a route, specifying
a destination and mask; optionally, a gateway IP address;
and an output index.
.PP
.SH "EXAMPLES"
This example delivers broadcasts and packets addressed to the local
host (18.26.4.24) to itself, packets to net 18.26.4 to the
local interface, and all others via gateway 18.26.4.1:
.PP
.nf
\& ... -> GetIPAddress(16) -> rt;
\& rt :: RadixIPLookup2(18.26.4.24/32 0,
\& 18.26.4.255/32 0,
\& 18.26.4.0/32 0,
\& 18.26.4.0/24 1,
\& 0.0.0.0/0 18.26.4.1 1);
\& rt[0] -> ToLinux;
\& rt[1] -> ... -> ToDevice(eth0);
.fi
.PP
.SH "ELEMENT HANDLERS"
.IP "\fBctrl\fR (write-only)" 5
Take in changes to the routing table, in the format of
.IP "" 5
.nf
\& add ip/mask [gw] output
\& remove ip/mask
.fi
.IP "" 5
for example,
.IP "" 5
.nf
\& add 18.26.4.0/24 18.26.4.1 0
\& (NOTE: add doesn't work, the entry is inserted at the back and
\& doesn't work)
.fi
.IP "" 5
says all packets to 18.26.4.0/24 subnet should use gateway
18.26.4.1, and go out on output port 0. and
.IP "" 5
.nf
\& remove 18.26.4.0/24
.fi
.IP "" 5
removes the route.
.IP "" 5
.IP "\fBshowroutes\fR (read-only)" 5
Returns the (sorted) contents of the routing table.
.IP "" 5
.PP
.SH "SEE ALSO"
.M StaticIPLookup n ,
.M LookupIPRoute3 n
More information about the click
mailing list