Implementing IP LPM in Pandas

Longest Prefix Match (LPM) is the algorithm used in IP networks to forward packets. The algorithm is used to select the one entry in the routing table (for those that know, I really mean the FIB — forwarding information base — here when I say routing table) that best matches the destination address in the IP packet that the router is forwarding. I am an old school systems programmer, used to programming in C or even Python, not the new style method chaining model used in the popular Python data analysis package, Pandas. This post is a description of my experiments in implementing LPM in pandas. The goal obviously is to ensure that LPM completed as fast as possible on the full Internet feed, but potentially much larger.

Longest Prefix Match (LPM)

Any IP address consists of two parts: the network part and the host specific part. The network part is also called the subnet. The network part is often written as a combination of 2 pieces: the IP network address and the prefix length. An example of an IP subnet written this way is: 192.168.0.0/24, where the network address is 192.168.0.0 and the prefix length is 24. The prefix length, 24 in this case, represents the number of bits used by the network part of the address. The remaining bits in the IP address is used to construct the host part. IPv4 addresses are 32 bits in length. So, in the IPv4 subnet 192.168.0.0/24, 24 bits are used to represent the network part and the remaining 8 bits are used to assign to hosts. Thus, the subnet 192.168.0.0/24 can contain upto 256…