Feature request: IPNetwork Subtract

[HunterMitchell]

Looking at the source code, I see a method called: TrySubstractNetwork. I attempted to use a slightly modified version of this function and it was extremely slow.

I am trying to take two lists IncludedRanages and ExcludedRanges and have something consolidate adjacent and overlapping ranges/networks. Is this something easily added?

[lduchosal]

TrySubstractNetwork is really slow, we need to find a fast algorithm to substract two big subnets.

[fravelgue]

Not sure, it's same requirement. But I'm using RangeTree [1] to store ranges of IPs, and searching for IPs in it.
[1] https://github.com/mbuchetics/RangeTree

[lduchosal]

Thanks for pointing this out. I'll have a look when time permits.

[sakib1361]

Rather than trying to subtract ip address via range, I found that adding subnet via binary elimination might be faster. The idea is to split network into two until all the split networks are free of the subtract target. These subnets can be farther split to subtract multiple networks. Finally the split parts free from subtract networks can be joined together.
A sample has been shown here. Currently it fits my project needs. Not sure it is fully correct though. Dont like the idea of recursion. If I find a better idea, will update the code.
https://github.com/sakib1361/IPTest

[agowa]

I don't know why one wants to subtract IP addresses, but it could easily be done using something like this:

#powershell

$minuend = ([System.Net.IPAddress]"192.168.2.27").MapToIPv6()
$subtrahend = ([System.Net.IPAddress]"0.0.2.0").MapToIPv6()

$difference = [System.Net.IPAddress]([bigint]($minuend.GetAddressBytes()) - [bigint]($subtrahend.GetAddressBytes())).ToByteArray()

$displayAddress = ($difference.IsIPv4MappedToIPv6) ? $difference.MapToIPv4().IPAddressToString : $difference.IPAddressToString
Write-Host "Next usable ip is: $displayAddress"

[lduchosal]

192.168.0.0/24 - 192.168.0.128/26 = [ 192.168.0.0/25 , 192.168.0.192/26 ]

How would you solve the following ?
0.0.0.0/0 - 10.0.0.1/32 =

[lduchosal]

0.0.0.0/0 - 10.0.0.1/32 = [

0.0.0.0/5,
8.0.0.0/7,
10.0.0.0/32,
10.0.0.2/31,
10.0.0.4/30,
10.0.0.8/29,
10.0.0.16/28,
10.0.0.32/27,
10.0.0.64/26,
10.0.0.128/25,
10.0.1.0/24,
10.0.2.0/23,
10.0.4.0/22,
10.0.8.0/21,
10.0.16.0/20,
10.0.32.0/19,
10.0.64.0/18,
10.0.128.0/17,
10.1.0.0/16,
10.2.0.0/15,
10.4.0.0/14,
10.8.0.0/13,
10.16.0.0/12,
10.32.0.0/11,
10.64.0.0/10,
10.128.0.0/9,
11.0.0.0/8,
12.0.0.0/6,
16.0.0.0/4,
32.0.0.0/3,
64.0.0.0/2,
128.0.0.0/1

]

[agowa]

oh, you mean getting the symmetric difference of the address space and not to subtract the addresses (aka. there binary values) from each other.

Than a more logical representation would be to take two lists of ip prefixes and return a list with the actual symmetrical difference.

[RobThree]

Rather than trying to subtract ip address via range, I found that adding subnet via binary elimination might be faster. The idea is to split network into two until all the split networks are free of the subtract target. These subnets can be farther split to subtract multiple networks. Finally the split parts free from subtract networks can be joined together.

Exactly. This is how it's supposed to be done and can be very fast since all you do is split recursively. I have implemented the algorithm here (disclaimer, stating the obvious: author here).

For an example:

var network = NetworkHelper.Parse("192.168.0.0/16");
var desired = NetworkHelper.Parse("192.168.10.16/28");
var result = network.Extract(desired);

// Result:
// 192.168.0.0/21
// 192.168.8.0/23
// 192.168.10.0/28
// 192.168.10.16/28
// 192.168.10.32/27
// 192.168.10.64/26
// 192.168.10.128/25
// 192.168.11.0/24
// 192.168.12.0/22
// 192.168.16.0/20
// 192.168.32.0/19
// 192.168.64.0/18
// 192.168.128.0/17

You can also pass "0.0.0.0/28" to 'extract' any /28 from the given network. Works with IPv6 as well. What may help is using a visual subnet calculator like this one (no affiliation) to help visualize the concept. @lduchosal's exampe would be done as:

var network = NetworkHelper.Parse("0.0.0.0/0");
var desired = NetworkHelper.Parse("10.0.0.1/32");

var result = network.Extract(desired);
var resulttext = string.Join("\n", result.Select(n => $"{n.Prefix}/{n.PrefixLength}"));

[lduchosal]

@RobThree thanks, I'll dig into your proposal.