Performance progression of IPv6 route lookup on Linux

In a previous article, I explained how Linux implements an IPv6 routing table. The following graph shows the performance progression of route lookups through Linux history:

IPv6 route lookup performance progression

All kernels are compiled with GCC 4.9 (from Debian Jessie). This version is able to compile older kernels as well as current ones. The kernel configuration is the default one with CONFIG_SMP, CONFIG_IPV6, CONFIG_IPV6_MULTIPLE_TABLES and CONFIG_IPV6_SUBTREES options enabled. Some other unrelated options are enabled to be able to boot them in a virtual machine and run the benchmark.

There are three notable performance changes:

  • In Linux 3.1, Eric Dumazet delays a bit the copy of route metrics to fix the undesirable sharing of route-specific metrics by all cache entries (commit 21efcfa0ff27). Each cache entry now gets its own metrics, which explains the performance hit for the non-/128 scenarios.
  • In Linux 3.9, Yoshifuji Hideaki removes the reference to the neighbor entry in struct rt6_info (commit 887c95cc1da5). This should have lead to a performance increase. The small regression may be due to cache-related issues.
  • In Linux 4.2, Martin KaFai Lau prevents the creation of cache entries for most route lookups. The Continue reading

IPv6 route lookup on Linux

TL;DR: With its implementation of IPv6 routing tables using radix trees, Linux offers subpar performance (450 ns for a full view — 40,000 routes) compared to IPv4 (50 ns for a full view — 500,000 routes) but fair memory usage (20 MiB for a full view).

In a previous article, we had a look at IPv4 route lookup on Linux. Let’s see how different IPv6 is.

Lookup trie implementation

Looking up a prefix in a routing table comes down to find the most specific entry matching the requested destination. A common structure for this task is the trie, a tree structure where each node has its parent as prefix.

With IPv4, Linux uses a level-compressed trie (or LPC-trie), providing good performances with low memory usage. For IPv6, Linux uses a more classic radix tree (or Patricia trie). There are three reasons for not sharing:

  • The IPv6 implementation (introduced in Linux 2.1.8, 1996) predates the IPv4 implementation based on LPC-tries (in Linux 2.6.13, commit 19baf839ff4a).
  • The feature set is different. Notably, IPv6 supports source-specific routing1 (since Linux 2. Continue reading

TextFSM Getting Started

Textfsm is a text parsing library written in python to turn plain text into structured data. Originally created by Google, the project seemed largely abandoned until recently being added to github and receiving a small update. This post will show how to extract interesting data from the...

On ISO standardization of blockchains

So ISO, the primary international standards organization, is seeking to standardize blockchain technologies. On the surface, this seems a reasonable idea, creating a common standard that everyone can interoperate with.

But it can be silly idea in practice. I mean, it should not be assumed that this is a good thing to do.

The value of official standards

You don't need the official imprimatur of a government committee for something to be a "standard". The Internet itself is a prime example of that.

In the 1980s, the ISO and the IETF (Internet Engineering Task Force) pursued competing standards for creating a world-wide "internet". The IETF was an informal group of technologist that had essentially no official standing.

The ISO version of the Internet failed. Their process was to bring multiple stakeholders from business, government, and universities together in committees to debate competing interests. The result was something so horrible that it could never work in practice.

The IETF succeeded. It consisted of engineers just building things. Rather than officially "standardized", these things were "described", so that others knew enough to build their own version that interoperated. Once lots of different people built interoperating versions of something, then it became a Continue reading

Announcement: IPS code

So after 20 years, IBM is killing off my BlackICE code created in April 1998. So it's time that I rewrite it.

BlackICE was the first "inline" intrusion-detection system, aka. an "intrusion prevention system" or IPS. ISS purchased my company in 2001 and replaced their RealSecure engine with it, and later renamed it Proventia. Then IBM purchased ISS in 2006. Now, they are formally canceling the project and moving customers onto Cisco's products, which are based on Snort.

So now is a good time to write a replacement. The reason is that BlackICE worked fundamentally differently than Snort, using protocol analysis rather than pattern-matching. In this way, it worked more like Bro than Snort. The biggest benefit of protocol-analysis is speed, making it many times faster than Snort. The second benefit is better detection ability, as I describe in this post on Heartbleed.

So my plan is to create a new project. I'll be checking in the starter bits into GitHub starting a couple weeks from now. I need to figure out a new name for the project, so I don't have to rip off a name from William Gibson like I did last time :).

Some notes:

Worth Reading: DNS query name minimization

One new thing you need to add your DNS security policies is “query name minimizations” (RFC 7816). I thought I’d mention it since many haven’t heard about it. Right now, when DNS resolvers lookup a name like “www.example.com.”, they send the entire name to the root server (like a.root-servers.net.). When it gets back the answer to the .com DNS server a.gtld-servers.net), it then resends the full “www.example.com” query to that server. This is obviously unnecessary. The first query should be just .com. to the root server, then example.com. to the next server — the minimal amount needed for each query, not the full query. —Robert Graham @ Errata Security

The post Worth Reading: DNS query name minimization appeared first on rule 11 reader.

Securing Bitcoins with TREZOR

TREZOR is a hard wallet for securely storing crypto assets such as Bitcoin, Ethereum, and Litecoin. Protection mechanisms like a mnemonic recovery seed, PIN, and encryption passphrase safeguard your assets (private keys) by requiring your physical interaction in order to make transactions. For those crypto noobies, I think it’s easiest to describe the TREZOR functionality […]

The post Securing Bitcoins with TREZOR appeared first on Overlaid.

App Highlight: Hardenize

Hardenize is a comprehensive security tool that continuously monitors the security and configuration of your domain name, email, and website. Ivan Ristić, the author of Hardenize, gave a demo of his app at our Cloudflare London HQ.



Do you know how secure your site is? View a Hardenize report on your website by clicking this button:



Interested in sharing a demo of your app at a meetup? We can help coordinate. Drop a line to [email protected].

Broken packets: IP fragmentation is flawed

As opposed to the public telephone network, the internet has a Packet Switched design. But just how big can these packets be?

CC BY 2.0 image by ajmexico, inspired by

This is an old question and the IPv4 RFCs answer it pretty clearly. The idea was to split the problem into two separate concerns:

  • What is the maximum packet size that can be handled by operating systems on both ends?

  • What is the maximum permitted datagram size that can be safely pushed through the physical connections between the hosts?

When a packet is too big for a physical link, an intermediate router might chop it into multiple smaller datagrams in order to make it fit. This process is called "forward" IP fragmentation and the smaller datagrams are called IP fragments1.

Image by Geoff Huston, reproduced with permission

The IPv4 specification defines the minimal requirements. From the RFC791:

Every internet destination must be able to receive a datagram
of 576 octets either in one piece or in fragments to
be reassembled. [...]

Every internet module must be able to forward a datagram of 68
octets without further fragmentation. [...]

The first value - Continue reading

Got my number!

After a week of waiting (why this is taking so long? this wasn’t a particularly pleasant week), I finally got my number.

Brand new JNCIE-DC #31 !!!

The main note about the lab – time management is the most important thing on the exam. Don’t rush to the keyboard, read and understand all the tasks and it’s interdependencies. Have a plan regarding order of tasks – not all tasks can be completed in order in which they written. Don’t be affraid to skip some tasks if it takes a long time.

I am quite pleased with the level of my preparation for the lab – there were no unexpected or incomprehensible tasks. General feeling about JNCIE-DC lab – this is interesting, pretty complex but fair exam. Lot of tasks on various themes, I think all themes from blueprint are covered in the lab in some ways.

As the proctor told me, the main difficulty of this exam is that it’s something new, and people are afraid of a new and unexpected. I want to tell you – don’t be afraid! If you’re interested in learning a Juniper way of building Data Center networks, and also want to earn one more pretty Continue reading

1 … 1,953 1,954 1,955 1,956 1,957 … 3,858