7

このようなCIDR形式のファイルがあり192.168.1.0/24、この2列の構造に変換されます

3232236030 3232235777

各文字列の IP アドレス変換は、次のコードで行われます。

String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);

Inet4Address a = (Inet4Address) InetAddress.getByName(utils.getInfo().getHighAddress());
long high = bytesToLong(a.getAddress());
Inet4Address b = (Inet4Address) InetAddress.getByName(utils.getInfo().getLowAddress());
long low = bytesToLong(b.getAddress());

private static long bytesToLong(byte[] address) {
   long ipnum = 0;
   for (int i = 0; i < 4; ++i) {
       long y = address[i];
       if (y < 0) {
           y += 256;
       }
       ipnum += y << ((3 - i) * 8);
   }
   return ipnum;
}

の 500 万を超えるエントリがあると考えてください(low high : 3232236030 3232235777)。
また、交差するため、IP は複数の範囲から発信できます。最初のものだけでOKです。
データは読み取り専用です。が属する
範囲を見つけるための最速の方法は何ですか? ipToBefiltered構造は完全にメモリ内にあるため、データベース ルックアップはありません。

アップデート：

このPeerblockプロジェクトを見つけました(100 万回以上ダウンロードされているので、高速なアルゴリズムが必要だと思います): http://code.google.com/p/peerblock/source/browse/trunk/src/pbfilter/filter_wfp。 c

プロジェクトが範囲のリストを作成し、それらを検索するために使用している手法を知っている人はいますか?

4

5 に答える 5

7

結局のところ、IPが5Mの範囲のいずれかに存在するかどうかを知る必要があります。

n = 256のn-aryツリーを検討し、変換された整数ではなく、点線のアドレスから機能します。

トップレベルは256個のオブジェクトの配列になります。nullエントリは「いいえ」を意味します。アドレスを含む範囲がないため、例のarray 192.168.1.0/24[192]にはオブジェクトが含まれますが、100.xxx / nに範囲が定義されていないため、array[100]はnullになる可能性があります。

保存されたオブジェクトには、別の配列[256]と範囲指定子（への参照）が含まれ、2つのうち1つだけが設定されるため、192.0.0.0/8その範囲内のすべてのアドレスがフィルタリングされることを示す範囲指定子になります。これ192.255.0.0/10により、アドレスの最初の10ビットが重要である場合などが可能になり1100 0000 11xx xxxxます。それ以外の場合は、第2レベルの配列の次のオクテットをチェックする必要があります。

最初に、重複する範囲がある場合は、より大きな範囲に合体します...たとえば3 .. 10、次のように7 .. 16なります...特定のIPを、それを定義した範囲3 .. 16に関連付ける必要がないため、これが可能になります。

これには、8つ以下の比較が必要です。各オクテットは、最初はインデックスとして直接使用され、続いてnullの比較、ターミナルノードの比較（範囲または次のツリーレベルへのポインター）が続きます。

最悪の場合、すべての(256 ^ 4)IPアドレスがフィルタリング範囲内にある場合のメモリ消費量は理論的には4 GBですが、もちろんそれは単一の範囲に合体するため、実際には1つの範囲オブジェクトになります。より現実的なワーストケースは、おそらく16.7MBに近いでしょう。実際の使用法では、おそらく各レベルのarray[256]ノードの大部分が空になります。(256 ^ 3)

これは基本的にハフマン/プレフィックスコーディングに似ています。最短の個別のプレフィックスは、回答（範囲）が見つかるとすぐに終了する可能性があるため、多くの場合、< 4比較の平均があります。

于 2011-11-29T22:02:52.503 に答える
1

私はこのバイナリチョップアルゴリズムをVuze（別名azureus）プロジェクトで見つけました：

public IpRange isInRange(long address_long) {
    checkRebuild();

    if (mergedRanges.length == 0) {
        return (null);
    }

    // assisted binary chop

    int bottom = 0;
    int top = mergedRanges.length - 1;
    int current = -1;

    while (top >= 0 && bottom < mergedRanges.length && bottom <= top) {

        current = (bottom + top) / 2;

        IpRange e = mergedRanges[current];

        long this_start = e.getStartIpLong();
        long this_end = e.getMergedEndLong();

        if (address_long == this_start) {
            break;
        } else if (address_long > this_start) {

            if (address_long <= this_end) {
                break;
            }

            // lies to the right of this entry

            bottom = current + 1;

        } else if (address_long == this_end) {
            break;
        } else {
            // < this_end

            if (address_long >= this_start) {
                break;
            }
            top = current - 1;
        }
    }

    if (top >= 0 && bottom < mergedRanges.length && bottom <= top) {

        IpRange e = mergedRanges[current];

        if (address_long <= e.getEndIpLong()) {
            return (e);
        }

        IpRange[] merged = e.getMergedEntries();

        if (merged == null) {
            //inconsistent merged details - no entries
            return (null);
        }

        for (IpRange me : merged) {
            if (me.getStartIpLong() <= address_long && me.getEndIpLong() >= address_long) {
                return (me);
            }
        }
    }
    return (null);
}

かなりうまく機能しているようです。もっと速いことを知っているなら、私に知らせてください。

于 2011-11-30T19:25:41.027 に答える
1

ソートされたintの配列（ベースアドレス）と同じサイズの別の配列（終了アドレス）を使用します。これは5M*8 =40MBを使用します。最初のIPはベースで、2番目のIPは範囲内の最後のアドレスです。交差点を削除する必要があります。

アドレスが二分探索O（log N）にフィルタリングされているかどうかを確認し、完全に一致していない場合は、上限よりも小さい（または等しい）かどうかを確認します。

于 2011-11-29T19:42:23.763 に答える
1

CIDR アドレス (またはそれらのリスト) があり、その CIDR (または CIDR のリスト) の範囲内に ipAddress があるかどうかを確認したい場合は、SubnetUtils オブジェクトの Set を定義するだけです。

非常に大きな N 個のアドレスをフィルタリングしない限り、これはすべて文字列の比較であり、非常に高速に実行されます。上位/下位ビットと複雑な Jazz のすべてに基づいてバイナリ ツリーを構築する必要はありません。

String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);
//...
//for each subnet, create a SubnetUtils object
Set<SubnetUtils> subnets = getAllSubnets();
//...

Guava Predicate を使用して、一連のサブネットの範囲にない ipAddresses をフィルタリングします。

   Set<String> ipAddresses = getIpAddressesToFilter();
   Set<String> ipAddressesInRange = 
       Sets.filter(ipAddresses, filterIpsBySubnet(subnets))


   Predicate<String> filterIpsBySubnet(final Set<SubnetUtils> subnets){
       return new Predicate<String>() {
            @Override
            public boolean apply(String ipAddress) {
                for (SubnetUtils subnet : subnets) {
                    if (subnet.getInfo().isInRange(ipAddress)) {
                        return true;
                    }
                }
                return false;
            }
        };
   }

これで、IP がいずれかのサブネットにある場合、単純なフィルターが作成され、単体テストが必要なデータ構造を構築する必要がなくなります。これで十分なパフォーマンスが得られない場合は、最適化に進みます。時期尚早に最適化しないでください:)

于 2013-03-08T18:44:30.837 に答える
0

これが答えの始まりです、また暇ができたら戻ってきます

設定：

  1. 範囲を開始番号で並べ替えます。
  2. これらは IP アドレスであるため、重複する範囲はないと想定しています。オーバーラップがある場合は、リストを実行して範囲をマージし、不要な範囲をトリミングする必要があります (たとえば、範囲が 1 ～ 10 の場合は、範囲 5 ～ 7 をトリミングできます)。
    1. マージまたはトリムするには、次のようにします (範囲 a が範囲 b の直前にあると仮定します)。
      1. b.end < a.end の場合、範囲 b は範囲 a のサブセットであり、範囲 b を削除できます。
      2. b.start < b.end および b.end > a.end の場合、範囲 a と b をマージできます。a.end = b.end を設定し、範囲 b を削除します。
于 2011-11-29T20:03:30.270 に答える