Как получить все IP-адреса, которые не находятся в заданном диапазоне IP-адресов

Question

Мне нужно иметь возможность выводить все диапазоны IP-адресов, которые не входят в данный список диапазонов IP-адресов.

Есть какой-то алгоритм, который я могу использовать для такого рода задач, который я могу преобразовать в рабочий код?

• В основном я буду использовать код Salesforce Apex, поэтому любой язык, подобный JAVA, подойдет, если данный пример возможен.

Answer 1

Во-первых, то, что вы описываете, может быть упрощено до:

• у вас есть интервалы вида x.x.x.x - y.y.y.y
• вы хотите вывести интервалы, которые еще не «взяты» в этом диапазоне.
• вы хотите иметь возможность эффективно добавлять или удалять интервалы

Я бы предложил использовать дерево интервалов , где каждый узел хранит интервал, и вы можете эффективно вставлять и удалять узлы; и запросить перекрытия в данной точке (= IP-адрес).

Если вы можете гарантировать, что совпадений не будет, вы можете вместо этого использовать простой TreeSet<String>, где вы должны, однако, гарантировать (для правильной сортировки), что все строки используют формат xxx.xxx.xxx.xxx-yyy.yyy.yyy.yyy с добавлением нуля.

Как только ваши интервалы находятся в дереве, вы можете генерировать желаемый результат, предполагая, что интервалы не перекрываются, выполняя предварительный обход вашего дерева по глубине и сохраняя начало и конец каждого посещенного узла в список. Учитывая этот список,

• до начала 0.0.0.0 в начале
• добавьте 255.255.255.255 в конце
• удалить все дублирующиеся ips (которые будут принудительно находиться рядом друг с другом в списке)
• возьмите их парами (число всегда будет четным), и там у вас есть интервалы свободных IP-адресов, отлично отсортированные.

Обратите внимание, что 0.0.0.0 и 255.255.255.255 не являются действительными маршрутизируемыми IP-адресами. Вы должны прочитать соответствующие RFC, если вам действительно нужно выводить реальные IP-ориентированные IP.

Answer 2

Я думаю, что ключом к простому решению является помнить, что IP-адреса могут рассматриваться как число типа long, и поэтому они могут быть отсортированы.

Я предположил, что исключенные диапазоны задаются «хорошим» способом, то есть без перекрытий, без частичных перекрытий с глобальным диапазоном и так далее. Конечно, вы можете добавить такие проверки ввода позже.

В этом примере я буду использовать все диапазоны сети (глобальные, включенные, исключенные) как экземпляры класса NetworkRange.

Ниже приведена реализация NetworkRange. Обратите внимание на методы splitByExcludedRange и includes.

public class NetworkRange {

    private long startAddress;
    private long endAddress;

    public NetworkRange(String start, String end) {
        startAddress = addressRepresentationToAddress(start);
        endAddress = addressRepresentationToAddress(end);
    }

    public NetworkRange(long start, long end) {
        startAddress = start;
        endAddress   = end;
    }

    public String getStartAddress() {
        return addressToAddressRepresentation(startAddress);
    }

    public String getEndAddress() {
        return addressToAddressRepresentation(endAddress);
    }

    static String addressToAddressRepresentation(long address) {
        String result = String.valueOf(address % 256);

        for (int i = 1; i < 4; i++) {
            address = address / 256;
            result = String.valueOf(address % 256) + "." + result;
        }

        return result;
    }

    static long addressRepresentationToAddress(String addressRep) {
        long result = 0L;
        String[] tokens = addressRep.split("\\.");

        for (int i = 0; i < 4; i++) {

            result += Math.pow(256, i) * Long.parseLong(tokens[3-i]);
        }

        return result;
    }

    public List<NetworkRange> splitByExcludedRange(NetworkRange excludedRange) {
        if (this.startAddress == excludedRange.startAddress && this.endAddress == excludedRange.endAddress)
            return Arrays.asList();

        if (this.startAddress == excludedRange.startAddress)
            return Arrays.asList(new NetworkRange(excludedRange.endAddress+1, this.endAddress));

        if (this.endAddress == excludedRange.endAddress)
            return Arrays.asList(new NetworkRange(this.startAddress, excludedRange.startAddress-1));

        return Arrays.asList(new NetworkRange(this.startAddress, excludedRange.startAddress-1),
                             new NetworkRange(excludedRange.endAddress+1, this.endAddress));
    }

    public boolean includes(NetworkRange excludedRange) {
        return this.startAddress <= excludedRange.startAddress && this.endAddress >= excludedRange.endAddress;
    }

    public String toString() {
        return "[" + getStartAddress() + "-" + getEndAddress() + "]";
    }
}

Теперь прибывает класс, который вычисляет оставленные включенные диапазоны сети. Он принимает глобальный диапазон в конструкторе.

public class RangeProducer {

    private NetworkRange global;

    public RangeProducer(NetworkRange global) {
     this.global = global;
    }

    public List<NetworkRange> computeEffectiveRanges(List<NetworkRange> excludedRanges) {
        List<NetworkRange> effectiveRanges = new ArrayList<>();
        effectiveRanges.add(global);
        List<NetworkRange> effectiveRangesSplitted = new ArrayList<>();

        for (NetworkRange excludedRange : excludedRanges) {
            for (NetworkRange effectiveRange : effectiveRanges) {
                if (effectiveRange.includes(excludedRange)) {
                    effectiveRangesSplitted.addAll(effectiveRange.splitByExcludedRange(excludedRange));
                } else {
                    effectiveRangesSplitted.add(effectiveRange);
                }
            }

            effectiveRanges = effectiveRangesSplitted;
            effectiveRangesSplitted = new ArrayList<>();
        }
        return effectiveRanges;
    }
}

Вы можете запустить следующий пример:

public static void main(String[] args) {
        NetworkRange global = new NetworkRange("10.0.0.0", "10.255.255.255");

        NetworkRange ex1 = new NetworkRange("10.0.0.0", "10.0.1.255");
        NetworkRange ex2 = new NetworkRange("10.1.0.0", "10.1.1.255");
        NetworkRange ex3 = new NetworkRange("10.6.1.0", "10.6.2.255");
        List<NetworkRange> excluded = Arrays.asList(ex1, ex2, ex3);

        RangeProducer producer = new RangeProducer(global);

        for (NetworkRange effective : producer.computeEffectiveRanges(excluded)) {
            System.out.println(effective);
        }
    }

Вывод должен быть:

[10.0.2.0-10.0.255.255]
[10.1.2.0-10.6.0.255]
[10.6.3.0-10.255.255.255]

Answer 3

Во-первых, я предполагаю, что вы имеете в виду, что вы получаете один или несколько непересекающихся диапазонов CIDR в качестве входных данных, и вам необходимо создать список всех диапазонов CIDR, не включая ни один из указанных в качестве входных данных. Для удобства давайте далее предположим, что входные данные не включают в себя все пространство IP-адресов: то есть 0.0.0.0/0. (Это может быть учтено в одном особом случае, но не представляет особого интереса.)

Я уже писал код, аналогичный этому, и, хотя я не вправе делиться кодом, я могу описать методологию. По сути, это алгоритм двоичного поиска, в котором вы постоянно делите пополам адресное пространство до тех пор, пока не выделите один интересующий вас диапазон.

Думайте о пространстве IP-адресов как о бинарном дереве: в корне находится полное адресное пространство IPv4 0.0.0.0/0. Каждый его дочерний элемент представляет половину адресного пространства: 0.0.0.0/1 и 128.0.0.0/1. Те, в свою очередь, могут быть подразделены для создания дочерних элементов 0.0.0.0/2 / 64.0.0.0/2 и 128.0.0.0/2 / 192.0.0.0/2, соответственно. Продолжайте до конца, и у вас останется 2**32 листьев, каждый из которых представляет один /32 (то есть один адрес).

Теперь рассмотрим это дерево как части адресного пространства, которые исключены из вашего входного списка. Итак, ваша задача - пройти по этому дереву, найти каждый диапазон из вашего входного списка в дереве и вырезать все части дерева, которые находятся на вашем входе, оставляя оставшиеся части адресного пространства.

К счастью, вам не нужно создавать все листы 2**32. Можно предположить, что каждый узел в CIDR N включает все узлы в CIDR N+1 и выше, если для него не было создано дочерних элементов (вам понадобится флаг, чтобы помнить, что он уже был подразделен - , т.е. больше не лист - смотри ниже, почему).

Итак, для начала, все адресное пространство присутствует в дереве, но все может быть представлено одним конечным узлом. Вызовите дерево excluded, и инициализируйте его одним узлом 0.0.0.0/0.

Теперь возьмем первый входной диапазон для рассмотрения - мы назовем это trial (я буду использовать 14.27.34.0/24 в качестве начального trial значения только для того, чтобы предоставить конкретное значение для демонстрации). Задача состоит в том, чтобы удалить trial из excluded, оставив остальное адресное пространство.

Начните с указателя узла current, установленного на корневой узел excluded.

Начало:

Сравните trial CIDR с current. Если он идентичен, все готово (но этого не должно происходить, если ваши входные диапазоны не пересекаются и вы исключили 0.0.0.0/0 из входных данных).

В противном случае, если current является листовым узлом (не был подразделен, то есть он представляет все адресное пространство на этом уровне CIDR и ниже), установите его флаг подразделенного разделения и создайте для него два дочерних элемента: a left указатель на первую половину его адресного пространства и right указатель на вторую половину. Отметьте каждый из них соответствующим образом (для дочерних узлов корневого узла это будет 0.0.0.0/1 и 128.0.0.0/1).

Определите, находится ли trial CIDR в левой или правой стороне current. Для нашего начального значения trial это слева. Теперь, если указатель на этой стороне уже NULL, снова все готово (хотя, опять же, это не может произойти, если ваши входные диапазоны не пересекаются).

Если trial CIDR точно эквивалентен CIDR в узле на этой стороне, то просто освободите узел (и любые дочерние элементы, которые у него могут быть, что опять-таки не должно быть ни одного, если у вас есть только разделить входы), установите указатель на эту сторону NULL и все готово. Вы только что исключили весь этот диапазон, вырезав этот лист из дерева.

Если пробное значение не совсем эквивалентно CIDR в узле на этой стороне, установите current в эту сторону и начните сначала (то есть перейдите к Start label выше).

Итак, с начальным диапазоном ввода 14.27.34.0/24 вы сначала разделите 0.0.0.0/0 на 0.0.0.0/1 и 128.0.0.0/1. Затем вы опуститесь вниз с левой стороны и разделите 0.0.0.0/1 на 0.0.0.0/2 и 64.0.0.0/2.. Затем вы снова опуститесь вниз влево, чтобы создать 0.0.0.0/3 и 32.0.0.0/3. и т. Д., Пока после 23 разбиений вы не затем разделит 14.27.34.0/23 на 14.27.34.0/24 и 14.27.35.0/24. Затем вы удалите левый 14.27.34.0/24 дочерний узел и установите его указатель на NULL, оставив другой.

Это оставит вас с редким деревом, содержащим 24 листовых узла (после того, как вы уронили целевой). Оставшиеся листовые узлы отмечены *:

                             (ROOT)
                           0.0.0.0/0
                            /     \
                      0.0.0.0/1  128.0.0.0/1*
                        /    \
                 0.0.0.0/2  64.0.0.0/2*
                  /     \
            0.0.0.0/3  32.0.0.0.0/3*
              /    \
       0.0.0.0/4  16.0.0.0/4*
           /  \
  *0.0.0.0/5  8.0.0.0/5
               /    \
       *8.0.0.0/6  12.0.0.0/6
                      /    \
             *12.0.0.0/7  14.0.0.0/7
                             /    \
                     14.0.0.0/8  15.0.0.0/8*
                        /    \
                     ...
                /       \
     *14.27.32.0/23  14.27.34.0/23
                      /       \
                  (null)     14.27.35.0/24*
          (14.27.34.0/24)

Для каждого оставшегося входного диапазона вы снова будете проходить по дереву, разделяя узлы листьев, когда это необходимо, часто приводя к большему количеству листьев, но всегда вырезая некоторую часть адресного пространства.

В конце вы просто проходите результирующее дерево в любом удобном порядке, собирая CIDR оставшихся листьев. Обратите внимание, что на этом этапе вы должны исключить те, которые были ранее подразделены. Рассмотрим, например, в приведенном выше дереве, если вы в следующий раз обработали входной диапазон 14.27.35.0/24, вы бы оставили 14.27.34.0/23 без дочерних элементов, но обе его половины были обрезаны по отдельности и не должны быть включены в выходные данные. (С некоторыми дополнительными сложностями вы можете, конечно, свернуть узлы над ним, чтобы приспособить и этот сценарий, но проще просто оставить флаг в каждом узле.)