IPv4 CIDR(アドレスブロック)を高速に結合する

目的

• CIDR(IPv4アドレスブロック)を結合する。(=プレフィックス集約)
  • 例: 192.168.0.0/24 と 192.168.0.1/24 → 192.168.0.0/23
• 大量のCIDRを処理しても高速に動作する。
  • perl の Net::CIDR の cidradd() で大量の IPv4アドレスブロックを処理するととても遅かったため。

速度

• テスト方法: MaxMind GeoLite2 のCSVデータから任意に選んだ国のCIDR 98514 個を処理する。(67358 個に結合された)
• 処理時間: 2.45秒
• 実行環境:
  • CPU: AMD Ryzen 7 2700
  • OS: Debun GNU/Linux 10 (Buster) AMD64
  • perl: 5.28

ソース

• ipaddress-merge.pl

ライセンス

• GPL 2.0 (日本語訳)

実行例

    sort -t / -k 2 -n INPUT_FILE | perl ipaddress-merge.pl > OUTPUT_FILE

入力データについて

• x.x.x.x/x 形式の IPv4アドレスブロックが 1行に 1つ書いてあるテキストファイル。
• アルゴリズムの都合上 prefixの小さい順にソートされている必要がある。
  • 例: sort -t / -k 2 -n INPUT_FILE

参考: アルゴリズム

入力される各CIDRに対して、

• CIDR をIPアドレスレンジに変換する。
• リストに格納されている処理済みの IPアドレスレンジ群に対し、これから処理する CIDR がどこに位置するかをバイナリサーチで特定する。
• 特定した位置の前後に処理済みの IPアドレスレンジ群が隣接するかチェックする。(※)
  • 隣接していれば結合する。
  • 隣接していなければ新規CIDRとしてリストに挿入する。

最後にリスト上の IPアドレスレンジを CIDR に変換・出力する。

以下は※の処理の解説。

既に登録されているアドレスブロック群(A)に対して、処理対象アドレスブロック(B)が

・同じ
    | A |
    | B |

・隣接も包含もしない
    | A |
            | B |
                    | A'    |

・隣接する
    | A |
        | B |

・包含する (処理が常に新規で、入力をアドレスブロックサイズ順に
  ソートしておくと、この状況は発生しない)
        | A |
    | B         |

・包含される
    | A         |
        | B |

・(入力が範囲じゃなくてブロック単位なので、一部重なる、は考慮しない)
    | A     |
        | B     |

Aの各要素は、始点と終点の重複がない、と想定。
また処理によりそうなるはずだし、ならないといけない。

隣接する時は、以下の3通りがある。
・始点のみ隣接する
    | A |
        | B |
・終点のみ隣接する
        | A |
    | B |
・始点と終点の両方が隣接する
    | A |   | A'    |
        | B |

包含する時だけ、A が複数存在する場合がある。
        | A |   | A'    |
    | B                 |

(以上)