Given a set of IP address ranges, which all the ranges which contain the given IP address

Question

I have a set of IP address ranges, which correspond to some conditions.

Given an input IP address, I want to know all the sets of the IP ranges which contain this input IP address.

So far a segment tree seems to be suitable https://github.com/toberndo/go-stree but it takes only integers whereas I need IPv4 and IPv6 ranges.

Any suggestions on the algorithm suitable for this kind of a problem? Maybe an extension to Go/GoLang check IP address in range

You could work with the ordered IPs converted to numbers, take a look to this question http://stackoverflow.com/questions/26296761/check-if-a-number-exists-in-a-given-set-of-ranges — Jaime Soriano, Apr 08 '15 at 21:07
The link specifies that it just finds whether the number is present in the range. I would like all the ranges which have this number. The segment tree seems to be right, but it just does integers, whereas IPv6 is much larger than an int — Kartik Sura, Apr 08 '15 at 21:21
Umm, I see, in any case ordering the ranges would speed up the searches, it is more or less what the stree does. Maybe you can adapt this stree library to use bigint https://golang.org/pkg/math/big/, or byte arrays. In any case yes, you're right, the stree looks as the way to do it. — Jaime Soriano, Apr 08 '15 at 21:37
Some clarification of how the definition of the ranges. given 192.168.0.50 - 192.168.0.150 then 192.168.0.100 would be in the range. However, 192.168.0.90 - 192.168.10.100, then depending on the definition, 192.168.5.80 may or may not be in the range. if it is in range, then you can treat IPv4 as a 4 digit base 256 number, otherwise will have to treat it as 4 discreet ranges (192-192, 168-168, 0-10 and 90-100) — Xetius, Apr 08 '15 at 22:40

Sean F · Answer 1 · 2022-03-28T12:46:53.893

The IPAddress Go library can do this a couple of different ways with code that is polymorphic, working with both IPv4 and IPv6 addresses. Repository here. Disclaimer: I am the project manager.

I'll show both ways to do it, using sample IPv4 addresses. Either way is not much code.

Here's 28 random sample IPv4 ranges and a single address to check what ranges it lies within:

ipRangeStrs := [][2]string{
    {"26.154.36.255", "82.200.127.52"},
    {"26.154.36.255", "192.250.200.250"},
    {"37.99.32.76", "62.192.232.40"},
    {"37.99.32.76", "141.101.231.182"},
    {"37.99.32.144", "185.148.82.122"},
    {"37.99.32.144", "194.59.250.237"},
    {"46.56.236.163", "186.169.171.32"},
    {"46.56.236.163", "195.231.4.217"},
    {"62.109.3.240", "91.87.64.89"},
    {"62.109.11.226", "62.192.232.40"},
    {"82.200.127.52", "103.192.63.244"},
    {"88.250.248.235", "188.18.253.203"},
    {"88.250.248.235", "212.74.202.30"},
    {"91.87.64.89", "209.97.191.87"},
    {"103.192.63.244", "212.253.90.11"},
    {"109.197.13.33", "109.197.13.149"},
    {"109.197.13.33", "141.101.231.203"},
    {"109.197.13.33", "195.231.4.217"},
    {"109.197.13.33", "212.253.90.11"},
    {"109.197.13.149", "212.253.90.11"},
    {"122.114.118.63", "186.169.171.32"},
    {"122.114.118.63", "188.18.253.203"},
    {"141.101.231.182", "185.148.82.122"},
    {"141.101.231.203", "212.74.202.30"},
    {"192.250.200.250", "212.253.90.111"},
    {"194.59.250.237", "212.253.90.11"},
    {"195.231.4.132", "209.97.191.87"},
    {"195.231.4.132", "212.253.90.111"},
}
// candidate to check
candidate := "88.255.1.1"

One way is to use sequential ranges, iterating through each. This is O(n).

var ipRanges []*ipaddr.IPAddressSeqRange
for _, strs := range ipRangeStrs {
    addr1, addr2 := ipaddr.NewIPAddressString(strs[0]).GetAddress(),
        ipaddr.NewIPAddressString(strs[1]).GetAddress()
    rng := addr1.SpanWithRange(addr2)
    ipRanges = append(ipRanges, rng)
}

addrToCheck := ipaddr.NewIPAddressString(candidate).GetAddress()
counter := 0
for _, rng := range ipRanges {
    if rng.Contains(addrToCheck) {
        counter++
        fmt.Printf("range %d %v contains %v\n", counter, rng, addrToCheck)
    }
}

Output:

range 1 26.154.36.255 -> 192.250.200.250 contains 88.255.1.1
range 2 37.99.32.76 -> 141.101.231.182 contains 88.255.1.1
range 3 37.99.32.144 -> 185.148.82.122 contains 88.255.1.1
range 4 37.99.32.144 -> 194.59.250.237 contains 88.255.1.1
range 5 46.56.236.163 -> 186.169.171.32 contains 88.255.1.1
range 6 46.56.236.163 -> 195.231.4.217 contains 88.255.1.1
range 7 62.109.3.240 -> 91.87.64.89 contains 88.255.1.1
range 8 82.200.127.52 -> 103.192.63.244 contains 88.255.1.1
range 9 88.250.248.235 -> 188.18.253.203 contains 88.255.1.1
range 10 88.250.248.235 -> 212.74.202.30 contains 88.255.1.1

Now for the other way.

The following algorithm is a constant time operation O(1) for each search candidate, no matter how many ranges are used. Building the trie is O(n). So this is best for cases where you may be doing multiple searches to find the containing ranges, and the list of ranges is not changing much.

Convert each range to spanning CIDR prefix blocks that can be added to an address trie. Map each trie entry to the original range. Look up the containing blocks in the trie. This is a constant time operation. It requires at most 32 comparisons no matter how many ranges are used, because IPv4 address bit size is 32. On average, it will do log(n) comparisons where n is the number of items in the trie. So in this example, the average is 9 comparisons (trie size is 421), less than the 28 required with the previous code.

I'll also note that this code is polymorphic, it also works with IPv6 addresses.

The ipRanges slice and the addrToCheck address carry over from the previous example.

trie := ipaddr.AssociativeAddressTrie{}
for _, rng := range ipRanges {
    blocks := rng.SpanWithPrefixBlocks()
    for _, block := range blocks {
        trie.Remap(block.ToAddressBase(), 
            func(existing ipaddr.NodeValue) ipaddr.NodeValue {
                // make the node point to the original range(s)
                if existing == nil {
                    return []*ipaddr.IPAddressSeqRange{rng}
                } else {
                    return append(existing.([]*ipaddr.IPAddressSeqRange), rng)
                }
            })
    }
}
fmt.Printf("The trie has %d blocks\n", trie.Size())
//print the trie with: fmt.Println(trie)

trieNode := trie.ElementsContaining(addrToCheck.ToAddressBase())
 
// ElementsContaining returns a linked list in trie form of containing blocks.
// The mapped values of each in the list are the containing ranges.
var result []*ipaddr.IPAddressSeqRange
for trieNode != nil {
    ranges := trieNode.GetValue().([]*ipaddr.IPAddressSeqRange)
    result = append(result, ranges...)
    if trieNode.GetUpperSubNode() != nil {
        trieNode = trieNode.GetUpperSubNode()
    } else {
        trieNode = trieNode.GetLowerSubNode()
    }
}
fmt.Printf("The %d containing ranges are: %v", len(result), result)

Output:

The trie has 421 blocks
The 10 containing ranges are: [26.154.36.255 -> 192.250.200.250 37.99.32.76 -> 141.101.231.182 37.99.32.144 -> 185.148.82.122 37.99.32.144 -> 194.59.250.237 46.56.236.163 -> 186.169.171.32 46.56.236.163 -> 195.231.4.217 82.200.127.52 -> 103.192.63.244 62.109.3.240 -> 91.87.64.89 88.250.248.235 -> 188.18.253.203 88.250.248.235 -> 212.74.202.30]

Given a set of IP address ranges, which all the ranges which contain the given IP address

1 Answers1