二分探索による高速なIPアドレスマッチングのアルゴリズム

はじめに Scutumには他の多くのWAFと同じようにIPアドレスを使ったアクセス制御の仕組みが備わっています。例えば特定のネットワークからのアクセスを拒否したり、逆に特定のネットワークやアドレスからのみアクセスを許可する、という設定が可能です。 このとき、例えば「日本の国内のIPアドレスからのみアクセスを許可したい」のような要求がある場合など、数千〜数万くらいの大量のネットワークアドレスのエントリが列挙されて設定されることがあります。 実際にアクセスを制御する場面では、そのとき接続してきたある1つのIPアドレスが、上記の大量のネットワークアドレスの中の「いずれかにマッチするか、あるいはまったくマッチしないか」を高速に判定する必要があります。 Scutumではこの処理に二分探索を使うことで高速なマッチングを実現しました。今回はこのアルゴリズムを紹介します。 このアルゴリズムの要点 実際には

[ryuichi1208]

なるほど

[cakephper]

“Scutumではこの処理に二分探索を使うことで高速なマッチングを実現しました。今回はこのアルゴリズムを紹介します。”