CATEGORY: NETWORK

ルート集約のアルゴリズム - 線形編

ルート集約を扱う。本稿では、CIDR表記のIPアドレスを集約するアルゴリズムを整理する。

IPアドレスをまとめなくてはいけない場面がどうしてもよく出てくる。本稿ではそんなときに備えて、IPアドレス、ネットワークアドレスをまとめる方法を整理する。

キーワード: ルート集約、ルートアグリゲーション、経路集約、CIDR集約、プレフィックス集約、スーパーネット化

本稿では “ルート集約” を使用する。呼称はなんでもいい。

ルート集約とは

複数の詳細なネットワーク経路をまとめて、一つの代表的な経路として扱う技術である。ルータが持つルーティングテーブルの項目数を減らし、メモリの節約や処理負荷の軽減を実現する。IPアドレスの共通部分に着目し、CIDR表記でプレフィックス長を調整することで経路をまとめることを指す。

本稿では、CIDR表記のIPアドレス、ネットワークをまとめる。経路の話は対象外である。

モチベーション

Q. どうして、CIDRのIPアドレス、ネットワークアドレスをまとめたいか？ A. とにかくまとめる必要があるからであり、それ以上でもそれ以下でもない。

集約の例

では、本稿でいう集約の例を見ていく。集約の例は以下のものになる。

入力

例えば、入力として次のCIDRリストがあるとする。

192.168.0.0/25
192.168.0.128/25
192.168.1.0/24
10.0.0.0/24
10.0.0.128/25

これを集約すると、次のようになるものを想定とする。

想定の出力結果

192.168.0.0/23
10.0.0.0/24

アプローチ

本稿のCIDR集約のアプローチは、線形のアプローチを取る。リスト内のIPアドレスが、包含するか、マージ可能か、それ以外かを1つずつ繰り返し判定していき、CIDRをまとめていく手法を取る。

ここでいう"線形"というのは便宜上、線形と呼んでいるだけであり、コンピューターネットワークで正式な呼称ではないことに注意してほしい。

その他のアプローチとして、2分木を使用するアプローチがある。どんなCIDRリストでも、計算量を抑えた、または一定に保つアプローチも存在する。

集約アルゴリズム

集約対象のリストから、CIDRを1つずつ取り出して、その時点での最終候補とした正規化されたCIDR一覧全部と比較しながら、吸収・マージを繰り返す。

  • 入力：CIDRのリスト
  • 出力：正規化されたCIDRのリスト

集約フローの全体像

このアルゴリズムは、「現在処理中のCIDR(current)を、すでに正規化済みの集合 (out) に統合していく」 ことを繰り返すものである。 currentは比較の途中でより大きなCIDRへと変化する可能性があるため、マージが発生したら比較を最初からやり直す。これにより、例えば /25 → /24 → /23 のような段階的なマージも1回の走査の中で実現できる。 外側のloopは、こうした統合の結果としてさらに新たなマージが可能になる場合に備え、全体が安定するまで繰り返すために存在する。

簡単な擬似コードに落とすと以下のようになる。この擬似コードも実装するにあたっては、足りない部分があるが、アルゴリズムの流れは理解できると思う。

repeat
    before = 件数

    input(Array)をソートする
    out = 空

    for current in input(Array)

        for existing in out(Array)

            if existingがcurrentを包含する *1
                currentを捨てる
                次のcurrentへ

            if currentがexistingを包含する *1
                existingを削除する
                比較を続ける

            if existingとcurrentがマージ可能 *2
                current = merged
                existingを削除する
                outの先頭から比較し直す(continueのように、forやり直し)

        currentをoutに追加する

    input = out(Array)

until 件数が変化しなくなる
  1. inputを1つずつ取り上げ、outの要素それぞれとマージできないかチェックし、outに追記する。マージできるときは、マージしたものがoutの要素とマージできないか繰り返しチェックを行なっていく。
  2. outの内容をすべて、inputに移動して、前工程を繰り返す。
  3. 数が変化しなくなるまで繰り返す。

数が変化しなくなったら、ルート集約完了となる。

アルゴリズム内のIPアドレスに関する取り扱いのアルゴリズムについては、これより下に記載する。

*1 包含チェックの方法

AとBのCIDRの包含をチェックする方法：AがB を包含するかは、

Aのプレフィックス長 ≦ Bのプレフィックス長であり

かつ

BのネットワークアドレスをAのプレフィックス長でマスクするとAのネットワークアドレスになる

が、真であるとき、AがBを包含すると判断できる。

たとえば、以下のとき

A = 192.168.0.0/24
B = 192.168.0.100/32
  • プレフィックス長A:24 ≦ B:32を満たし、
  • B:192.168.0.100をAのプレフィックス24でマスクすると、192.168.0.0となり、Aのネットワークアドレスと合致する。そのため、AがBを包含する、BはAの範囲の中にあるといえる。

集約アルゴリズム中では、AとBをひっくり返して同じチェックを行う。

*2 マージ（兄弟チェック）の方法

CIDR表記、XとYのマージを考える。

  • XとY のプレフィックス長が同じであること
  • ネットワークアドレスが隣接していること：つまりXとYでそれぞれ、プレフィックス長を1つ短くして、短くしたネットワークアドレスが同じであること

の両方が真ならば、兄弟であり、マージできると言える。例えば、

X = 192.168.0.0/25
Y = 192.168.0.128/25

に関して、プレフィックス長が同じであり、24(=25-1)でマスクをかけると、ネットワークアドレス部が両方とも192.168.0.0となり、兄弟といえる。2つは、192.168.0.0/24にマージできる。

本当に？漏れが無いか？余計なものを含んでいないかと思うところがあるが、これは前提条件として、実質的にプレフィックス長が同じで、包含関係ではないことが前提となっているため、このチェックのみを行えば、2つのCIDRが兄弟であることを示せる。

さらに補足として、マージできるのはプレフィックス長が同じのときであるから、つまり同じアドレス数を持つときである。当たり前の話。 また、第4オクテット128の半分ではなくとも、たとえば、192.168.0.0~3の時も一緒である。プレフィックス31で、2(192.168.0.0/31), 2(192.168.0.2/31)に分けられていた時、その2つは兄弟であり、192.168.0.0/30に集約できる。全部当たり前の話。

線形版のメリット、デメリット

メリットは、アルゴリズム/実装がシンプルである点が挙げられる。 デメリットは、CIDRのデータ量が増えると比較回数が急増するという点がある。最悪、計算回数がO(N²)に達する。実際は、隣接するIPアドレスのみ確認するだけで十分なのだが、アルゴリズム自体が、集約対象のIPアドレスすべてをなめる仕組みとなっている。

線形版はどういう時に使うべきか

  • 集約対象のCIDR数が数千〜数万程度のとき
    • IPアドレスの連続性、ランダム性、数など諸条件は、あるものの数が少ないときに有利となる。
  • 集約対象のCIDRを一度だけ正規化するとき
    • CIDRのリストに変更が無く、処理のなかで最後、一度集約を行うときに有利となる（更新頻度が高い場合は、不向き）。
  • 実装をシンプルに保ちたいとき
    • 得意な言語を使用できない場合に、比較的シンプルに実装できる可能性がある。

関連記事

Rustを用いた関数実装

実装は、タイトル：AddressSet in ips::addressset - Rustにて行なっている。

まとめ

CIDR表記のIPアドレス、ネットワークアドレスを線形版で、集約する方法を示した。総当たりで、包含、兄弟関係、それ以外かを繰り返しチェックすることで、集約することができる。