Dear all,I work for an ISP, and we do not spend money on heavy routers, we use linux to do the routing tasks, even at core level. We use commercial Intel servers to do this job, but when such a router has come to handle ~1GBit/s traffic, and also update the routing table (from BGP), the route cache seemed to be the bottleneck, as upon every fib update the whole route cache is flushed, and sometimes it took as many cpu cycles to let some packets being dropped. Meanwhile i knew that *BSD systems do not use such a cache, and of course without it a router can provide a constant performance, not depending on the number of different ip flows, and updating the fib does not take such a long time.
For this to be solved, i have played with ipv4 routing in linux kernel a bit. I have done two separate things:
- developed a new fib algorithm in fib_trie's place for ipv4 - rewrote the kernel not to use it's dst cacheI named my work Linux Express Forwarding, I hope i will not get any trouble with this. :)
The fib algorithm is like cisco's CEF (at least if my knowledge is correct), but first I use a 16-branching tree, to look up the address by 4 bit steps, and each node in this tree contains a simple sub-tree which is a radix tree, of course with maximum possible height 4. I think this is very simple, and is nearly 3 times faster than fib_trie. Now it has a missing feature: it does not export the fib in /proc/net/route.
The second thing i have done to minimize the cpu cycles during the forwarding phase, rewriting ip_input.c, route.c and some others to lef.c, and having a minimal functionality. I mean, for example, when a packet gets through the lef functions, ipsec policies are not checked. And to be more efficient, I attached a neighbour pointer to each fib entry, and using this the lookup + forwarding code is very fast.
Of course, the route cache needs very little time to forward packets when there are a small number of different ip flows, but when dealing with traffic in an ISP at core level, this cannot be stated.
So I have done tests with LEF, and compared them to the original linux kernel's performance. With the worst case, LEF performed nearly 90% of the linux kernel with the most optimal case. Of course original linux performs poorly with the worst case.
I will list the features/bugs needed to be completed/fixed (a TODO list):
FIB:
- export data to /proc/net/route
LEF:
- support packet fragmentation
- support SMP
These are the most important. Of course some might decide not to use it at all
without these. LEF has been running on our routers for 3 months at all, and no
problems arised. Now it seems that the routers internal bus speed is the
bottleneck, but that could only be fixed with hardware. :)
The patches are for 2.6.19.1, i have not done an effort to apply them on the latest kernel.
So i send the patches, and please say something about it, may i hope that it gets into the kernel or not, or what more should i do.
The files should be applied in alphabetic order. Regards, Richard Kojedzinszky
lef.tgz
Description: GNU Unix tar archive
