SAIL Based FIB Lookup in a Programmable Pipeline Based Linux Router by MD Iftakharul Islam and Javed I. Khan Kent State University (IEEE HPSR, 2019).

This paper presents SAIL [1] based routing table lookup in Linux kernel and in Domino. This enables Linux to work as a high-speed router. Here Linux kernel works as a control plane and Domino based VLIW processor works as a dataplane. One major drawback of SAIL is its high memory consumption. Here we use Population Counting [2] to reduce memory consumption of SAIL by up to 80%. We implemented both variant of SAIL namely SAIL_L and SAIL_U in Linux kernel and in Domino. We compared their performance in Linux kernel and in Domino.

Getting Started with SAIL in Linux kernel

This experiment is performed on Ubuntu Gnome 16.04 however it should work on any other Linux distributions. Here we assume that you are already familier with Linux kernel development. If you are new to Linux kernel developement. please take a look at following resources at the beginning

• kernelnewbies.org
• Linux Kernel Development (by Robert Love)
• Linux TCP/IP Networking for Embedded Systems (by Thomas Herbert)

Now that you are familiar with Linux kernel development, let's get started with SAIL in Linux kernel

1. Check out our Linux kernel source code from https://github.com/tamimcse/net-next
2. Check out our Linux kernel patches from https://github.com/tamimcse/kernel-patches/
3. Now you have two directories net-next and kernel-patches
4. cd net-next
5. git checkout d80323fbd653b770597fa724272eff5318f576bf (This will switch your code to Linux kernel 4.19.0-rc6+)
6. Now use command git apply ../kernel-patches/sail-u.patch in order to include SAIL_U to your source code
7. If you instead want to use SAIL_L, use the command git apply ../kernel-patches/sail-l.patch
8. Now you have added SAIL to your source code. But this will not do anything. You will want to add your test code to test SAIL. To do that, use the command git apply ../kernel-patches/test-fib-lookup.patch
9. Now everything (both SAIL and corresponding test code) is added to your Linux kernel source code
10. Now compile your kernel, install it and restart your computer
11. Congrats! Now you should have SAIL running on your computer. Try command dmesg to see SAIL's ourput
12. Check out https://github.com/tamimcse/parse-bgpdump. It contains routing tables of backbone routers obtained from RouteView project. It also contain necessary scripts to the add the routes to kernel
13. cd parse-bgpdump
14. sudo sh addroutes.sh (This will begin inserting the routing tables in to Linux kernel)

If you have any issue, please email mislam4@kent.edu

Getting Started with SAIL in Domino

This experiment is performed on Ubuntu Gnome 16.04 however it should work on any other Linux distributions.

1. Install Domino according to their website
2. clone https://github.com/tamimcse/domino-examples/
3. Enable permission to your tmp directory (sudo chmod a+rwx -R /tmp/). This directory will be used by Domino.
4. You will find sail-u.c and sail-l.c in our domino-examples directory. This is our implementation. Now compile SAIL_U using the command sh compile.sh domino-programs/sail-u.c banzai_atoms/raw.sk 15 5 true
5. Also compile SAIL_L using the command sh compile.sh domino-programs/sail-l.c banzai_atoms/raw.sk 32 6 true

If you have any issue, please email mislam4@kent.edu

References

1. Yang, Tong, et al. "Guarantee IP lookup performance with FIB explosion." ACM SIGCOMM, 2014
2. Asai, Hirochika, et al. "Poptrie: A compressed trie with population count for fast and scalable software IP routing table lookup." ACM SIGCOMM, 2015