RadixIPLookup + performance
Brecht Vermeulen
brecht.vermeulen at rug.ac.be
Tue Jan 15 01:37:03 EST 2002
Hi,
(I added Teng Fei because he mailed also a question regarding this
element last week and could be interested)
* I didn't understand how to use the RadixIPLookup: you can't give any
configuration with it when you install a click configuration, but you
can't create extra output ports afterwards. So, how can you use the
element as a routing table with multiple inputs ?
Therefore I adapted the element, so it can understand a configuration as
the StaticIPLookup element (and later on, one can change routes via the
ctrl handler, I haven't tried this yet, although you can't create extra
ports, only extra routes to the same output ports as already exist). I
wanted the element because I was attracted by the possible higher
performance (and I need also a modifiable routing table, so I had to
adapt StaticIPLookup or RadixIPLookup) indicated by lib/iptable2.cc
(this is not used, but uses also a radix tree) :
/*
* iptable2.{cc,hh} -- a fast IP routing table. Uses a radix tree for
fast
* routing table lookup.
*
I also inserted route caching in this element (also stolen from
StaticIPLookup), see patch in attachment (maybe some typos in it,
because I changed some naming without recompiling before I made the
patch, but the idea should be clear, it is also a patch against CVS
click of 01/11/02, where radixiplookup already inherits from
iproutetable instead of element).
* there is still a bug in it which I haven't solved yet (but had a fast
work around): the following routing table
10.0.3.103/32 0,
10.0.3.255/32 0,
10.0.3.0/32 0,
10.0.4.103/32 0,
10.0.4.255/32 0,
10.0.4.0/32 0,
10.0.5.103/32 0,
10.0.5.255/32 0,
10.0.5.0/32 0,
10.0.3.0/255.255.255.0 1,
10.0.4.0/255.255.255.0 2,
10.0.5.0/255.255.255.0 3,
255.255.255.255/32 0.0.0.0 0,
0.0.0.0/32 0,
0.0.0.0/0 10.10.10.12 1);
doesn't work e.g. if the address 10.0.5.14 has to be looked up.
10.0.5.255/32 is returned as match by the radix algorithm, but the
RadixIPLookup::lookup method sees it is not correct:
if((dst & _v[index]->mask) == (_v[index]->dst & _v[index]->mask))
{
the work around is to use the following routing table (not 100% correct,
but worked for my tests) :
10.0.3.103/32 0,
10.0.4.103/32 0,
10.0.5.103/32 0,
10.0.3.0/255.255.255.0 1,
10.0.4.0/255.255.255.0 2,
10.0.5.0/255.255.255.0 3,
255.255.255.255/32 0.0.0.0 0,
0.0.0.0/32 0,
0.0.0.0/0 10.10.10.12 1);
* I did some performance tests with an AMD K6, 500 MHz router (3 used
interfaces, streams generated by Smartbits). With streams from eth1 to
eth3, eth2 to eth1 and eth3 to eth2 (to mislead the caching in the
elements).
The streams are gradually increased in steps of 10 Mbit/s. (packets were
64 bytes).
I also tested with a bigger routing table (inserted 7 dummy routes).
The results of the delay are attached and I don't see much difference
between the different numbers.
Is there anybody else (e.g. creator of the RadixIPLookup element) which
has similar or other results ?
Or is this element not used anywhere ? Why is it created ?
And what about iptable2.cc ?
thanks for any answer,
regards,
Brecht
-------------- next part --------------
diff -c /remov_ext/click/cvs/click/elements/ip/iproutetable.cc ./iproutetable.cc
*** /remov_ext/click/cvs/click/elements/ip/iproutetable.cc Fri Aug 31 00:26:32 2001
--- ./iproutetable.cc Tue Jan 15 01:01:09 2002
***************
*** 92,104 ****
IPAddress a = p->dst_ip_anno();
IPAddress gw;
int port = -1;
!
if ((port = lookup_route(a, gw)) >= 0) {
if (gw)
p->set_dst_ip_anno(gw);
output(port).push(p);
} else {
! click_chatter("IPRouteTable: no route for %x", a.addr());
p->kill();
}
}
--- 92,129 ----
IPAddress a = p->dst_ip_anno();
IPAddress gw;
int port = -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 (_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();
}
}
diff -c /remov_ext/click/cvs/click/elements/ip/iproutetable.hh ./iproutetable.hh
*** /remov_ext/click/cvs/click/elements/ip/iproutetable.hh Fri Aug 31 00:26:32 2001
--- ./iproutetable.hh Tue Jan 15 01:00:33 2002
***************
*** 53,58 ****
--- 53,60 ----
#include <click/glue.hh>
#include <click/element.hh>
+ #define IP_RT_CACHE2 1
+
class IPRouteTable : public Element {
public:
IPRouteTable();
***************
*** 76,81 ****
--- 78,94 ----
(const String &conf, Element *e, void *, ErrorHandler *errh);
static String look_handler(Element *, void *);
void add_handlers();
+
+ 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
diff -c /remov_ext/click/cvs/click/elements/ip/radixiplookup.cc ./radixiplookup.cc
*** /remov_ext/click/cvs/click/elements/ip/radixiplookup.cc Sun Sep 2 05:25:56 2001
--- ./radixiplookup.cc Tue Jan 15 01:08:17 2002
***************
*** 27,34 ****
: _entries(0)
{
MOD_INC_USE_COUNT;
! add_input();
! add_output();
_radix = new Radix;
}
--- 27,34 ----
: _entries(0)
{
MOD_INC_USE_COUNT;
! // add_input();
! // add_output();
_radix = new Radix;
}
***************
*** 38,43 ****
--- 38,85 ----
uninitialize();
}
+ int
+ RadixIPLookup::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) {
+ add_route_uint32(dst, mask, gw, output_num);
+ // _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;
+ }
+
+
void
RadixIPLookup::uninitialize()
{
***************
*** 80,86 ****
--- 122,135 ----
unsigned dst = d.addr();
unsigned mask = m.addr();
unsigned gw = g.addr();
+
+ add_route_uint32(dst, mask, gw, port);
+ }
+
+ void
+ RadixIPLookup::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)) {
***************
*** 121,133 ****
unsigned dst = d.addr();
int index;
! if(!_entries || !_radix->lookup(dst, index))
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;
return _v[index]->port;
}
nomatch:
--- 170,189 ----
unsigned dst = d.addr();
int index;
! if(!_entries || !_radix->lookup(dst, index)) {
! click_chatter("RadixIPLookup::lookup_route : no match in radix table");
goto nomatch;
+ } /*else {
+ click_chatter("index in table : %d", index);
+ }*/
// 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:
diff -c /remov_ext/click/cvs/click/elements/ip/radixiplookup.hh ./radixiplookup.hh
*** /remov_ext/click/cvs/click/elements/ip/radixiplookup.hh Fri Jan 11 13:47:30 2002
--- ./radixiplookup.hh Tue Jan 15 01:02:42 2002
***************
*** 55,64 ****
--- 55,66 ----
const char *class_name() const { return "RadixIPLookup"; }
const char *processing() const { return AGNOSTIC; }
RadixIPLookup *clone() const { return new RadixIPLookup; }
+ 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 &);
***************
*** 76,81 ****
--- 78,84 ----
Vector<Entry *> _v;
int _entries;
Radix *_radix;
+
};
inline
-------------- next part --------------
A non-text attachment was scrubbed...
Name: performance.tar.gz
Type: application/x-gzip
Size: 102445 bytes
Desc: not available
Url : https://amsterdam.lcs.mit.edu/pipermail/click/attachments/20020115/d97b2d70/performance.tar.bin
More information about the click
mailing list