IP Address Set

[solonovamax]

I think that a dedicated class to represent a Set<IPAddress> would be quite useful.
It would be similar to a IPAddressSeqRange, however the ip addresses do not have to be sequential.

An example use case of this would be ip address blocking. You would add zero or more ip address ranges or ip addresses to it, and then you would have a method to check if an ip address is contained in that set.

If any addresses are added to it, which are already in a sequential range in the datastructure, then it would not add it.
further, if any of the sequential ranges in the set are end-to-end or overlap, it would join then (as an example, using integers, if it contains 4-8 and 7-12, these would be joined so that it only stores 4-12). the same applies to adding an individual ip address (ie. if it contains 4-7 and 8 is added, then instead of inserting a new element into the underlying list, it just expands the 4-7 range to instead be 4-8)

[seancfoley]

If you use CIDR blocks instead of sequential ranges, then this is already in the library, just use AddressTrie. If you wanted to have merging going on, you'd have to write some code to check if you wanted to merge an added block with an existing containing or contained block.

If you still want to use sequential ranges, then possibly you could wrap a java.util.TreeSet which is constructed with a comparator that compares the addresses in the compared ranges.

Adding or removing is trivial since the TreeSet is a SortedSet, so it could be sorted by address value, according to the comparator. When adding, you could use floor/ceiling or lower/higher methods to determine if merging ranges is possible, instead of just adding to the set.

Most people choose to work with CIDR blocks, not sequential ranges, since CIDR blocks have inherent advantages when testing for containment. So, I'm not sure if it's worthwhile to add something like this to the library. I will give it some thought.

[solonovamax]

If you use CIDR blocks instead of sequential ranges, then this is already in the library, just use AddressTrie. If you wanted to have merging going on, you'd have to write some code to check if you wanted to merge an added block with an existing containing or contained block.

If you still want to use sequential ranges, then possibly you could wrap a java.util.TreeSet which is constructed with a comparator that compares the addresses in the compared ranges.

Adding or removing is trivial since the TreeSet is a SortedSet, so it could be sorted by address value, according to the comparator. When adding, you could use floor/ceiling or lower/higher methods to determine if merging ranges is possible, instead of just adding to the set.

Most people choose to work with CIDR blocks, not sequential ranges, since CIDR blocks have inherent advantages when testing for containment. So, I'm not sure if it's worthwhile to add something like this to the library. I will give it some thought.

sorry I took a while to get back to you

I've looked into using the *AddressTrie classes, however I've noticed that they do come with a significant penalty cost.

for example, if I compare the size of test1 and test2 using JOL:

fun main() {
    val test1 = IPv4AddressTrie()
    val test2 = IPv4AddressTrie()

    for (i in 0..255)
        for (j in 0..255)
            test1.add("1.2.$i.$j")

    test2.add("1.2.0.0/16")

    test1.printSize("test1")
    println("===========================")
    test2.printSize("test2")
}

fun <T : Address> AddressTrie<T>.printSize(name: String) {
    val classnameAddress = "%s@%xd".format(this.javaClass.getName(), System.identityHashCode(this))
    println(GraphLayout.parseInstance(this).toFootprint().replace(classnameAddress, name))
    println("$name total size = " + GraphLayout.parseInstance(this).totalSize())
    println("size of $name = ${size()} Bytes")
}


fun <T : Address> AddressTrie<T>.add(address: String) {
    @Suppress("UNCHECKED_CAST")
    add(IPAddressString(address).address as T)
}

This should print something similar to the following (the exact values will depend on the jdk & platform OS):

test1 footprint:
     COUNT       AVG       SUM   DESCRIPTION
    260860        29   7803112   [B
     65541       271  17826216   [I
         4       152       608   [Linet.ipaddr.ipv4.IPv4Address;
    131082        32   4197672   [Linet.ipaddr.ipv4.IPv4AddressSegment;
         1        56        56   [[Linet.ipaddr.ipv4.IPv4AddressSegment;
         1        24        24   inet.ipaddr.AddressStringParameters$RangeParameters
         1        24        24   inet.ipaddr.IPAddress$IPVersion
         5        32       160   inet.ipaddr.IPAddressSection$PrefixCache
     65537        32   2097184   inet.ipaddr.IPAddressString
         2        32        64   inet.ipaddr.IPAddressStringParameters
         1        16        16   inet.ipaddr.format.util.BinaryTreeNode$ChangeTracker
         1        24        24   inet.ipaddr.format.util.BinaryTreeNode$ChangeTracker$Change
         2        40        80   inet.ipaddr.format.validate.ParsedHostIdentifierStringQualifier
     65537        88   5767256   inet.ipaddr.format.validate.ParsedIPAddress
     65537        80   5242960   inet.ipaddr.format.validate.ParsedIPAddress$1
    131077        40   5243080   inet.ipaddr.ipv4.IPv4Address
         1        48        48   inet.ipaddr.ipv4.IPv4AddressNetwork
         1        24        24   inet.ipaddr.ipv4.IPv4AddressNetwork$IPv4AddressCreator
         1        32        32   inet.ipaddr.ipv4.IPv4AddressNetwork$IPv4AddressCreator$Cache
    131078        72   9437616   inet.ipaddr.ipv4.IPv4AddressSection
    131072        64   8388608   inet.ipaddr.ipv4.IPv4AddressSection$IPv4StringCache
     65794        48   3158112   inet.ipaddr.ipv4.IPv4AddressSegment
         2        32        64   inet.ipaddr.ipv4.IPv4AddressStringParameters
         1        32        32   inet.ipaddr.ipv4.IPv4AddressTrie
    131072        40   5242880   inet.ipaddr.ipv4.IPv4AddressTrie$IPv4TrieNode
     65536        32   2097152   inet.ipaddr.ipv4.IPv4AddressTrie$IPv4TrieNode$IPv4TrieKeyData
         2        40        80   inet.ipaddr.ipv6.IPv6AddressStringParameters
         2        16        32   java.lang.Boolean
     65564        16   1049024   java.lang.Integer
    260860        24   6260640   java.lang.String
         2        40        80   java.math.BigInteger
   1636177            83812960   (total)


test1 total size = 83812960 Bytes
size of test1 = 65536
===========================
test2 footprint:
     COUNT       AVG       SUM   DESCRIPTION
       776        24     18656   [B
         6       116       696   [I
         4       152       608   [Linet.ipaddr.ipv4.IPv4Address;
        13       266      3464   [Linet.ipaddr.ipv4.IPv4AddressSegment;
         1        56        56   [[Linet.ipaddr.ipv4.IPv4AddressSegment;
         1        24        24   inet.ipaddr.AddressStringParameters$RangeParameters
         1        24        24   inet.ipaddr.IPAddress$IPVersion
         6        32       192   inet.ipaddr.IPAddressSection$PrefixCache
         2        32        64   inet.ipaddr.IPAddressString
         2        32        64   inet.ipaddr.IPAddressStringParameters
         1        16        16   inet.ipaddr.format.util.BinaryTreeNode$ChangeTracker
         1        24        24   inet.ipaddr.format.util.BinaryTreeNode$ChangeTracker$Change
         2        40        80   inet.ipaddr.format.validate.ParsedHostIdentifierStringQualifier
         2        88       176   inet.ipaddr.format.validate.ParsedIPAddress
         2        80       160   inet.ipaddr.format.validate.ParsedIPAddress$1
         7        40       280   inet.ipaddr.ipv4.IPv4Address
         1        48        48   inet.ipaddr.ipv4.IPv4AddressNetwork
         1        24        24   inet.ipaddr.ipv4.IPv4AddressNetwork$IPv4AddressCreator
         1        32        32   inet.ipaddr.ipv4.IPv4AddressNetwork$IPv4AddressCreator$Cache
         9        72       648   inet.ipaddr.ipv4.IPv4AddressSection
         2        64       128   inet.ipaddr.ipv4.IPv4AddressSection$IPv4StringCache
       516        48     24768   inet.ipaddr.ipv4.IPv4AddressSegment
         2        32        64   inet.ipaddr.ipv4.IPv4AddressStringParameters
         1        32        32   inet.ipaddr.ipv4.IPv4AddressTrie
         2        40        80   inet.ipaddr.ipv4.IPv4AddressTrie$IPv4TrieNode
         1        32        32   inet.ipaddr.ipv4.IPv4AddressTrie$IPv4TrieNode$IPv4TrieKeyData
         2        40        80   inet.ipaddr.ipv6.IPv6AddressStringParameters
         2        16        32   java.lang.Boolean
         7        16       112   java.lang.Integer
       776        24     18624   java.lang.String
         2        40        80   java.math.BigInteger
      2152               69368   (total)


test2 total size = 69368 Bytes
size of test2 = 1

as you can see, test1 is significantly larger than test2, by several orders of magnitude.
test2 is only ~67.7 KiB, however test1 ends up being a whole ~80.0 MiB.

this can also be seen in the huge difference in tree sizes if you run toString() on them.

I don't particularly care about the following things:

• iterating over the specific elements that were added (ie. address vs prefixed address)
• iterating over it at all
• the number of elements in the trie
• even removing elements

really all I care about right now is just checking if the trie contains the ip address or not. (I don't care about removing elements because instead I'm just re-creating the entire thing every n hours.)

is there any way to compact an *AddressTrie such that it becomes the smallest possible representation while still returning the exact same response for the contains method?

[seancfoley]

I am looking into implementing a data structure something like what you've described.

Whether or not the cost in size would improve depends a lot on the data set, in my opinion.

However, there can be other advantages to using sequential ranges over tries, one being cache coherency, which generally has a negative impact on the performance of tries (and similar data structures like linked lists).

[solonovamax]

Whether or not the cost in size would improve depends a lot on the data set, in my opinion.

yeah, definitely

if you're storing very sparse data then it wouldn't have significant impact.
it would be best for dealing with blocking many ip addresses, for example handling attacks from large botnets (which may have several contiguous ranges of ip addresses, especially in the ipv4 address space)

from some quick research datastructures that were suggested were

• R-Tree
• Interval Tree
• Radix Trie
  • HAT Tries (which is a type of Radix Trie that is cache-friendly: Askitis, N., & Sinha, R. (2007). HAT-trie: A Cache-conscious Trie-based Data Structure for Strings. Proceedings of the Thirtieth Australasian Conference on Computer Science - Volume 62, 97–105. doi:10.5555/1273749.1273761)
    • Hybrid HAT Trie: Slower but uses less memory
    • Pure HAT Trie: Faster but uses more memory
• Segment Tree

but from what I can tell, there isn't really any pre-existing datastructure that does range merging, so you'd probably want to choose one of those existing ones and then add range-merging right above the leaf level (ie. if any given node has children which are only leaves and all of them form a contiguous range, then it can merge them).

I'm not entirely sure of the advantages of each one so that would need to be assessed, but perhaps some kind of mix between a Segment Tree and a HAT Trie would be best? Though a Segment Tree also seems to also store which ranges a single point matches, so it might not be best?
Unsure.

However, there can be other advantages to using sequential ranges over tries, one being cache coherency, which generally has a negative impact on the importance of tries (and similar data structures like linked lists).

you could also get better cache coherency by using a HAT Trie, read the paper here: Askitis, N., & Sinha, R. (2007). HAT-trie: A Cache-conscious Trie-based Data Structure for Strings. Proceedings of the Thirtieth Australasian Conference on Computer Science - Volume 62, 97–105. doi:10.5555/1273749.1273761.
While looking at that paper, the acm website also recommended me these other two papers which may be interesting:

• Askitis, N., & Sinha, R. (2010). Engineering scalable, cache and space efficient tries for strings. The VLDB Journal, 19(5), 633–660. doi:10.1007/s00778-010-0183-9
• Askitis, N., & Zobel, J. (2010). Redesigning the string hash table, burst trie, and BST to exploit cache. Journal of Experimental Algorithmics, 15, 1.1. doi:10.1145/1671970.1921704