Google Summer of Code 2016 wrap-up: Linux XIA

Friday, November 18, 2016

We're sharing guest posts from students, mentors and organization administrators who participated in Google Summer of Code 2016. This is the fifth post in that series and there are more on the way.

Linux XIA is the native implementation of XIA, a meta network architecture that supports evolution of all of its components, which we call “principals,” and promotes interoperability between these principals. It is the second year that our organization, Boston University / XIA, has participated in Google Summer of Code (GSoC), and this year we received 31 proposals from 8 countries.

Our ideas list this year focused on upgrading key forwarding data structures to their best known versions. Our group chose the most deserving students for each of the following projects:

Accelerating the forwarding speed of the LPM principal with poptrie

Student André Ferreira Eleuterio and mentor Cody Doucette implemented the first version of the LPM principal in Linux XIA for GSoC 2015. The LPM principal enables Linux XIA to leverage routing tables derived from BGP, OSPF, IS-IS and any other IP routing protocol to forward XIA packets natively, that is, without encapsulation in IP. For GSoC 2016, student Vaibhav Raj Gupta from India partnered with mentor Cody Doucette to speed up the LPM principal by employing a state-of-the-art data structure to find the longest prefix matching using general purpose processors: poptrie.

Upgrading the FIB hash table of principals to the relativistic hash table

Principals that rely on routing flat names have used a resizable hash table that supports lockless readers since 2011. While this data structure was unique in 2011, in the same year, relativistic hash tables were published. The appeal to upgrade to relativistic hash tables was twofold: reduced memory footprint per hashed element, and the fact they were implemented in the Linux kernel in 2014. Student Sachin Paryani, also from India, worked with mentor Qiaobin Fu to replace our resizable hash table with the relativistic hash table.

Google Summer of Code nurtures a brighter future. Thanks to GSoC, our project has received important code contributions, and our community has been enlarged. It was rewarding to learn that two of our GSoC students have decided to pursue graduate school after their GSoC experience with us: Pranav Goswami (2015) and Sachin Paryani (2016). We hope these examples will motivate other students to do their best because the world is what we make of it.

By Michel Machado, Boston University / XIA organization administrator