6 ms·
IPv4 route lookup on Linux
- betaby 9y agoUnfortunately IPv6 stack doesn't match IPv4 one on features and optimizations. IPv6 is still using regular radix tree and a route cache.
- Thaxll 9y agoWasn't it possible to re-implement the same IPv4 model?
- bogomipz 9y agoDo you have any insight into why this is?
- slackingoff2017 9y agoNot a Linux networking expert... But one thing could be that you can fit entire IPV4 address space in ram easily and this obviously can't be done for IPV6. Might make some design compromises slower and more complex, such as storing routes in Bloom filters rather than simple cache.
- bogomipz 9y agoNo? Doesn't compress nicely with the empty octets and colon substitution?
- slackingoff2017 9y agoRouters don't store IP addresses as strings... They use 32 bit and 2X64 bit unsigned ints usually. And you can't compress something when measuring cardinality. Each route takes up an entry and the minimum space you can use with a non probabilistic structure is 1 bit per entry in a bit map. There's compressed bitmaps but the random nature of routes will not compress well.
- vbernat 9y agoAuthor here. The weaknesses are known (see for example http://www.netdevconf.org/1.1/proceedings/slides/kubecek-ipv6-route-lookup-performance-scaling.pdf http://www.netdevconf.org/1.1/proceedings/slides/kubecek-ipv...). IPv6 doesn't have the same features as IPv4 (notably, IPv6 can do a route lookup using both source and destination addresses). Therefore, it's not just a matter of reusing what is done with IPv4.
- bogomipz 9y agoI guess you are referring to scoped addresses then in ipV6? That would makes sense. Thanks for the interesting link.
- vbernat 9y agoYes. But IPv6 doesn't really have a route cache either. However, it handles exceptions differently than IPv4. With IPv6, exceptions are put in the tree along regular entries (there has been some bugs, like /128 routes disappearing due to a "cached" entry being expired) while IPv4 stores the exceptions with the next-hop information. EDIT: I stand corrected: before 4.2, route entries were created for almost any destination, so it was essentially a route cache. After that, the entry is created only when it is really needed (MTU lower than the default MTU).
- ladzoppelin 9y agoWhy is this image https://d1g3mdmxf8zbo9.cloudfront.net/images/linux/lpc-trie-struct.svg https://d1g3mdmxf8zbo9.cloudfront.net/images/linux/lpc-trie-... jumbled in Firefox beta?
- eriknstr 9y agoSubmit a bug report to Mozilla. https://bugzilla.mozilla.org/enter_bug.cgi https://bugzilla.mozilla.org/enter_bug.cgi
- vbernat 9y agoAuthor here. I am also using Firefox (on Linux) and the image is displayed fine. I don't know exactly what you mean by jumbled, but I don't hard-code fonts in the SVG: it uses the default sans-serif font of your system. May this explain what you get? I am usually careful with the anchor points and leave some additional space to ensure it is displayed correctly with whatever font is used. A solution would be to convert the text to paths, but I didn't find any tool that would do that efficiently. With Inkscape, there is a serious size bump when doing that.
- dom0 9y ago> With Inkscape, there is a serious size bump when doing that. Yes, you can't really avoid that when converting text to path objects, there is no way to do something similar to PDF's subset embedding AFAIK. I've tried to get SVG diagrams with text to work, but they just always fall apart somewhere. High-resolution PNG or inflated SVG seem the only viable methods. svgz (svg+gz) helps with the size inflation, but is not supported by Firefox when accessing local files. It's kinda a shame that web browsers can't display single-page PDF documents in-line, as images. http://i.imgur.com/x0TuCMC.png http://i.imgur.com/x0TuCMC.png
- vbernat 9y agoSVG can be served gzipped transparently. Ideally, when converting text to path, each letter (or group of letters) should be put in a group which can be referred with <use>. Thanks for the example. Is the text in other figures OK?
- xiconfjs 9y agoHow does this 50ns compare to commercial hardware routers like Brocade, which have dedicated memory (TCAM) for their routing table, which should be extra fast memory - as e.x. Brocade claims?!
- vbernat 9y agoHardware usually scales at line rate without any issue, something Linux cannot. From a pure latency point of view, a medium-range router (using the latest Broadcom Tomahawk chipset) takes around 500ns to route a packet (note that such a chipset cannot handle a full view). It doesn't seem unlikely that Linux can do the same job in certain configuration in about 100ns (notably, no netfilter rules). However, this takes a whole core to do that. If you have 24 of them, you get 12Gbps of transfer rate. With an hardware platform, packets are pipelined, so with some relatively small buffers, you can still achieve several hundreds of Gbps of traffic (per chip), something Linux cannot do in software. I can't say about TCAM performance alone. Are there super fast or are there able to perform parallel lookup?
- yusyusyus 9y ago> I can't say about TCAM performance alone. Are there super fast or are there able to perform parallel lookup? I think this doc[0] helps to understand the parallelism/performance from a TCAM perspective. [0] https://www.renesas.com/pt-br/doc/products/memory/r10an0013eu0100-memory.pdf https://www.renesas.com/pt-br/doc/products/memory/r10an0013e...
- erikb 9y agoWe seriously need more articles like this. As someone who would really like to understand more about the kernel source code, but without prior kernel knowledge (no classes in that direction) and barely any C knowledge the kernel is not the easiest part to read oneself into. Articles like this one help a lot, since they already provide an abstract model of what the code does and intends to do and why.
- majke 9y agoTechnical articles get downvoted on HN a lot these days. It became super hard to promote technical stuff here. Just look at this article - it's successful (on the front page) but it's hovering around 20th place, without any chances of raise: http://hnrankings.info/14631808/ http://hnrankings.info/14631808/
- throwawaye 9y agoMaybe it should renaming its title to "Rewriting IPv4 route lookup on Linux in VR using Rust and CSS"
- dom0 9y ago> articles get downvoted You can't downvote articles. (You can flag them, but flagging fine submissions is obviously abusive).
- erikb 9y agoflagging is basically downvoting
- comice 9y agoThe removal of the route cache caused a notable change in behaviour for equal cost routes. When there was a cache, you got a kind of session stickiness for free. Which meant you could do some fairly good load balancing at the network layer by advertising multiple routes to the same IP locally. The router would choose one of the routes when it saw the first packet, cache the decision and send the rest of the packets to it (the cache key was configurable and could include src address, amongst other things). Now you just get round robin between all the advertised paths - no good for tcp load balancing.