Created
January 25, 2022 15:16
-
-
Save AlexAvlonitis/e102267c8991a08c83bb80687de8be69 to your computer and use it in GitHub Desktop.
IP address longest prefix matching algorithm in ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# IP address longest prefix matching algorithm in ruby | |
# Used manual conversions methods, instead of ruby's built in methods | |
# Given the router receives a destination ip address "ip" | |
# It has to find out on which network it should forward it to, from its routing table. | |
# To find the network we need to do an AND operation of the binary representation of the dest IP and the | |
# destination subnet mask of our routing table "ip" AND "dest_mask" | |
# https://community.cisco.com/t5/switching/please-explain-how-the-longest-prefix-matching-works/td-p/2891235 | |
### routing table example | |
# | network | mask | | |
# | 10.0.0.0 | 255.0.0.0| | |
BITS = [128, 64, 32, 16, 8, 4, 2, 1].freeze | |
def to_bin(int) | |
BITS.map do |bit| | |
if int < bit | |
'0' | |
else | |
int -= bit | |
'1' | |
end | |
end.join | |
end | |
def to_dec_ip(bin) | |
ip = [] | |
bin.scan(/.{1,8}/).each do |bin_group| | |
temp = 0 | |
bin_group.split('').each.with_index { |bit, i| temp += BITS[i] if bit == '1' } | |
ip << temp.to_s | |
end | |
ip.join('.') | |
end | |
def ip_to_bin(ip_string) | |
ip_string.split('.').map { |ip_group| to_bin(ip_group.to_i) }.join | |
end | |
def ip_anding(ip1, ip2) | |
ip1.split('').map.with_index { |bit, i| (bit.to_i & ip2[i].to_i).to_s }.join | |
end | |
ip = '10.10.10.1' # destination ip address in decimal | |
dest_mask = '255.0.0.0' # possible network mask in decimal | |
dest_ip_bin = ip_to_bin(ip) # convert dest ip to binary string | |
dest_network_ip_bin = ip_to_bin(dest_mask) # convert dest mask to binary string | |
valid_dest_network_ip_bin = ip_anding(dest_ip_bin, dest_network_ip_bin) # perform an AND operation | |
# The result is the network address, that should match the routing table's network | |
# if there are more than 1 networks matching, the longest prefix takes precedence, | |
# or if the routing is in prefix order, then the first match wins. | |
puts to_dec_ip(valid_dest_network_ip_bin) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment