Reduce list of cidrs by a defined limit

Question

I got the following implementation to parse a bunch of ips into multiple range of cidrs. I'm limited by a maximum of 50 cidrs. I need to add that restriction somehow. I was thinking about calculating the distance between each cidr to group them until I reach the 50 limit in a sort of recursive algorithm.

Any suggestion?

    public static IEnumerable<string> Parse(IEnumerable<string> ipCollection)
    {
        var ips = ipCollection as IList<string> ?? ipCollection.ToList();

        if (!ips.Any()) return Enumerable.Empty<string>();

        var parsedIps = new List<IPNetwork>();

        foreach (var ip in ips)
        {
            IPNetwork ipNetwork;
            if (IPNetwork.TryParse(ip, out ipNetwork)) parsedIps.Add(ipNetwork);
        }

        // unable to parse any ips
        if (!parsedIps.Any()) return Enumerable.Empty<string>();

        return parsedIps.Count == 1
            ? ips.Select(ip => $"{ip}/32")
            : IPNetwork.Supernet(parsedIps.ToArray()).Select(x => x.ToString());
    }

Response ie:

Answer 1

A new hope

I found a better way to generate my cidrs. The approach I used is group by the first two octets of the ips provided basically because providers always have a range of these ips.

    public static IEnumerable<string> Parse(IEnumerable<string> ipCollection)
    {
        var parsedIpAddresses = new List<IPAddress>();

        ipCollection.ForEach(ip =>
        {
            IPAddress validIp;
            if (IPAddress.TryParse(ip, out validIp)) parsedIpAddresses.Add(validIp);
        });

        return SplitCidrs(parsedIpAddresses);
    }

    private static IEnumerable<string> SplitCidrs(List<IPAddress> ips)
    {
        var cidrs = new List<IPNetwork>();

        foreach (var mask in GetOrderedMasks(ips))
        {
            var filterIps = ips.Where(
                    x => x.ToString().StartsWith(mask)
                )
                .OrderBy(x => x.Address)
                .Select(x => x.ToString())
                .ToList();

            var newCidr = IPNetwork.WideSubnet(filterIps.First(), filterIps.Last());

            if (!cidrs.Contains(newCidr))
            {
                cidrs.Add(newCidr);
            }

            if (cidrs.Count >= AwsSgLimit - 1)
            {
                throw new AmazonSgLimitReached();
            }
        }

        return cidrs.Select(x => x.ToString());
    }

    private static IEnumerable<string> GetOrderedMasks(IEnumerable<IPAddress> ips)
    {
        return ips
            .Where(x => !x.ToString().StartsWith("10."))
            .GroupBy(
                x => string.Join(".", x.GetAddressBytes().Take(2))
            )
            .OrderByDescending(x => x.Count())
            .Select(group => group.Key.ToString() + ".");
    }

Tests

In the following algorithm, I use a completely different approach which I've tested with different IP populations. In one of the test, I passed into the function 55 inconsistent ips (remember my limit is 50 cidrs) which using the original code above ends up returning very wide cidrs (/8, /16). With the new algorithm, I only get /32, which is 100% optimisation update. I know 5 are wasted but this scenario is not real under an Internet provider subnet environment.

In a second test, I passed again real production data. The result is very good as I get rid of all the the "/7" and the nine "/8" (161 millions of ips) and now I only get one "/16" (65k ips) as the worst cidr. This is also a huge improvement considering this is real data and I'm basically getting the same result.

The rest are real ranges but still small (21, 24, 28) and orphaned ips (32). Still room for improvement as we don't reach the AWS limit of 50 by 28 free slots.

Results

Conclusion

I definitely recommend this algorithm to generate cidrs based on ips assigned by a particular provider as these providers typically move in a certain range.