This project aims at improval of the Linux GRE-over-IPv6 driver. The students taking on this assignment will be working on Linux kernel source code, albeit isolated clean code, and they have a good opportunity of showing performance improvements on a very important tunneling protocol.

Skills needed: C programming, Linux kernel experience, networking.

GRE means Generic Routing Encapsulation, and it is a tunnel that can be used to carry many different kinds of traffic between IP networks. It is used intensively to connect large amounts of traffic between locations. For ARPA2, we intend to use GRE to connect local IPv6 realms of users of hosting solutions.

The Linux kernel has a separate driver for GRE over IPv4, and over IPv6. The latter is working, but it has limited scalability, because it uses a hash table with a fixed number of entries. Storing 16 million entries in 16 hash table slots means that an average packet delivery requires searching through half a million possible tunnel end points! With an adaptive hash table size, the number of end points to consider could be a low, fixed number, thus leading to much faster delivery.

Perhaps millions of tunnel endpoints sounds extreme -- but take a look at applications like SIXXS to see how important a scalable tunneling infrastructure can be. And note that scaling takes time only while adding or removing tunnels; the mainstream process, which is routing of packets, is improved by it, which is always a good design choice. Given that, it should be easy to get this patch accepted in the mainstream kernel. Also note that GRE has an explicit "key" header which is 32-bits large; clearly, incredibly large numbers of tunnels are foreseen in the official protocol definition!

In this assignment, these two (rather clean) code bases could be combined to form an improved GRE driver over IPv6:

So, the hash tables for GRE over IPv6 should adapt their size to ensure that the number of lookups is a fixed, small number -- regardless of the number of GRE tunnels created over IPv6. In fact, GRE allows a number of alternative configurations, so there will be a few hash tables to cover each of these, but they are all the same in structure and can share the same code.

Project Results

The students undertaking this project will be guided, and are expected to deliver the following:

  • A patch to the GRE-over-IPv6 tunnel, giving it adaptive hash tables;
  • An informal explanation how the code is thread safe;
  • A comparison of the performance between the old and new driver.

Research Question

There is one central research question related to this work:

What is the performance difference between hash tables of fixed and adaptive size?

To establish this, you can make measurements of the average network latency with the original GRE-over-IPv6 driver and your patched driver. You should probably create a growing number of tunnel endpoints, up to millions, and plot the network latency on a logarithmic scale. Your measurements will have to be taken on many tunnel endpoints to avoid influence by one tunnel being the first in a hash table entry's search list. The expectation is that you will find dramatic improvements, especially if you are able to remove most other sources of latency from the path. Not only the latency should drop, but the variations in the latency between tunnel endpoints should, too.

In addition to the latency measurements, it would be useful to measure how busy a kernel is with deliverying packets over GRE; many parallel "flood ping" sessions may help to test this, and see what it takes to saturate a CPU, or part thereof. You might even work towards saturation and simply count the number of delivered packets.