Given a list of ranges how can we find if the give

Question

I have aset of ip ranges and i need to find if the ip given by the user exists between the given list of ip ranges .

This is in continuation to this question

How to check if a given ip falls between a given ip range using node js

Jonas helped me get the ip exists or not. But i donot want to do a exhaustive iterative search , I want to go a fast performance intensive search as my list of ip ranges (or number ranges) will be huge.

I looked into bloom filters as pointed by jonas but i am not convinced bloom filter might help . Also i was looking at Interval Tree But i dnt think it can search interval it takes intervals as inputs.

My ip list ranges https://github.com/client9/ipcat/blob/master/datacenters.csv#L4

How to search it in a fast manner . I am using node js

Answer 1

Ive observated that many of your ips look like this:

123.123.123.0 - 123.123.123.255

So to filter them out, we just need to block every ip starting with:

123.123.123

Now there are just 16E6 ip ranges left for being blocked. However you will probably block just a few of them, which gives us the ability to store that in a Set. A bit of code:

const blockedRange = new Set();

function IPtoBlock(ip){
   return ip.split(".").slice(0,3).join(".");
}

//to block an ip range ( if youve got one ip of it):
blockedRange.add( IPtoBlock("192.168.2.48") );

//to check for an ip
blockedRange.has( IPtoBlock( someip ));

---

So now there are just a few ranges that are not a block, like:

 5.44.26.144 - 5.44.26.159

But hey, just 15 ips, which we can add to a ban by ip list:

const blockedIPs = new Set();

function NumtoIP(num){
  return (num+"").split("").reduce((res,char,i) =>
    res + (!i || i%3?"":".") + (char === "0"?"":char)
  ,"");
 }

function addRange(start,end){
 start = IPtoNum(start);
 end = IPtoNum(end);//include from last answer
 for(var i = start; i <= end; i++){
   blockedIPs.add( NumtoIP( i ) );
 }
}

---

So when iterating over our range list we can seperate:

ranges.forEach(([min,max]) => {
  if( min.substr(-1) === "0" && max.substr(-3) === "255" ){
      blockedRange.add( IPtoBlock( min ) );
  }else{
      addRange(min, max);
  }
});

To check if an ip fails the check

function isBlocked(ip){
  return blockedIPs.has(ip) && blockedRange.has( IPtoBlock(ip) );
 }