Technical Report TR 2019-04-1
Internetworking and Media Communications Research Laboratories
Department of Computer Science, Kent State University
http://medianet.kent.edu/technicalreports.html


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 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 any Linux distribution should work.

  1. We use Linux kernel 4.19.0-rc6+. In order to update your kernel, clone https://github.com/tamimcse/net-next
  2. cd net-next
  3. git checkout d80323fbd653b770597fa724272eff5318f576bf
  4. Now compile the kernel. If you are new to Linux kernel development, don't worry, it's not that hard. Just take a look at kernelnewbies.org
  5. After compiling and installing your kernel, you will need to restart your computer
  6. Congrats! Now you have Linux kernel 4.19.0-rc6+ on your machine
  7. But SAIL is not included in the kernel yet. Now we are going to include SAIL in our Kernel.
  8. clone https://github.com/tamimcse/kernel-patches/
  9. Now kernel-patches directory contains our SAIL_U and SAIL_L patches
  10. cd net-next
  11. Now use command git apply ../kernel-patches/sail-u.patch in order to include SAIL_U to your source code
  12. If you instead want to use SAIL_L, use the command git apply ../kernel-patches/sail-l.patch
  13. Now you have added SAIL to your source code. But this will not do anything. You want to add your test code to test SAIL. To do that, use the command git apply ../kernel-patches/test-fib-lookup.patch
  14. Now everything (both SAIL and corresponding test code) is added to your Linux kernel source code
  15. Now compile your kernel again, install it and restart your computer
  16. Now you should have SAIL running on your computer. Try command dmesg to see SAIL's ourput

If you have any issue, please email mislam4 AT kent DOT edu

Getting Started with SAIL in Domino

This experiment is performed on Ubuntu Gnome 16.04 however any Linux distribution should work.

  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 AT kent DOT 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