サブネットマスクを集合論で理解しよう

概要

サブネットマスクの計算や実際にやっていることを数学の集合論で理解するための記事です。集合の非交差分割や同値関係について事前知識を持っていると、本記事が読みやすいと思います（一応記事の中でも定義や例については説明しています）。

背景

自分は初めてサブネットマスクを勉強したとき「なるほど、わからん」状態でした。インフラエンジニアとして恥ずかしい限りですが、現在も具体的な計算については時間をかけないと分からないといった状態です。

そんな折「サブネットマスクを集合論的に捉えてみると、理解が深まるのでは」と思い、いろいろ計算をしてみました。結果、ある程度見通しの良い定式化ができたので、本記事を投稿するに至りました。

本記事については、集合論の知識（特に同値関係の知識）があるといくらか読みやすい記事かと思います。

サブネットマスクについて

サブネットマスクをおさらいしておきましょう。

IPアドレスはネットワークアドレスとホストアドレスに分かれています。どこまでがネットワークアドレスで、どこまでがホストアドレスかを示すものがサブネットマスクになります。

サブネットマスクは以下のように、IPアドレスの横に/xxx.xxx.xxx.xxxと書くことで表現します。

192.168.10.5/255.255.255.0

これの意味としては「192.168.10.5の上位24ビットがネットワークアドレスで、それ以下はホストアドレスだよ」ということを意味してます。この24ビットが何を表しているかというと、サブネットマスク255.255.255.0を2進数表示するとわかります。

255.255.255.0 = 11111111.11111111.11111111.00000000

つまり、この1が並んでる部分がネットワークアドレスを示していて、0が並んでる部分がホストアドレスを示しているということになります。

そのため、192.168.10.5も2進数表記して並べると…

11000000.10101000.00001010.00000101
11111111.11111111.11111111.00000000

つまり、上位24ビットの部分である11000000.10101000.00001010がネットワークアドレス、00000101がホストアドレスということになります。ただ、正確には切り捨てた部分については0で埋める決まりになっているため、ネットワークアドレスは11000000.10101000.00001010.00000000、つまり 192.168.10.0 がネットワークアドレスになります。また、同じネットワークアドレスであるIPアドレス同士を、同じサブネットに所属するといったりします。

ここで、次のような問題が考えられます。

サブネットマスクを固定して、2つのIPアドレスが与えられたとき、それらが同じサブネットに所属しているかはどう判定すればいい？

定義に立ち返ると…

同じサブネットに所属する = ネットワークアドレスが同じ

となります。これをなんとか計算で求めることができないか考えます。

サブネットマスクは、上位ビットがすべて1で埋まっていることを鑑みると、与えられた2つのIPアドレスそれぞれを2進数表示し、各桁毎に2進数表示したサブネットマスクと論理積を取ってあげると、ちょうどそれぞれのIPのネットワークアドレス部のみが取り出せます！

具体例を見てみましょう。192.168.10.5と192.168.10.50を考えます。これらを2進数表示すると以下のようになります。

192.168.10.5: 11000000.10101000.00001010.00000101
192.168.10.50: 11000000.10101000.00001010.00110010

それぞれを11111111.11111111.11111111.00000000と各桁ごとに論理積を取ると、11000000.10101000.00001010が出てくるため、これらのIPアドレスは同じサブネットに属していることになります。

一方、192.168.10.5と192.168.9.5はどうでしょうか。これらを2進数表示すると次のようになります。

192.168.10.5: 11000000.10101000.00001010.00000101
192.168.9.5: 11000000.10101000.00001001.00000101

11111111.11111111.11111111.00000000と論理積を取ると、片方は11000000.10101000.00001010.00000000であり、もう片方は11000000.10101000.00001001.00000000となって一致しません。つまり、サブネットマスク255.255.255.0においては、これらのIPアドレスは同じサブネットに属さないことがわかります。

ただし、サブネットマスクを変更すると同じサブネットに属すこともあります。例えば、255.255.0.0をサブネットマスクとすると、これら2つのIPアドレスは同じサブネットに属します（もしお時間がある方は計算してみてください）。

今回の記事の目的は「サブネットマスクによる分類を数学的に理解できないか」です。これを説明するために、集合論の基本的な知識が必要になるので、次の節からはその説明を行います。

集合論概説

本記事で扱う集合論について、ざっとにはなりますが触れたいと思います。

集合の定義と直積

まず、集合とは範囲の定まったものの集まりのことです。以下が典型的な集合です。

\(\{n\ |\ n\text{は偶数}\}\): 偶数全体の集合,
\(\{x\ |\ x\text{は無理数}\}\): 無理数全体の集合,
\(\{p\ |\ p \text{は日本人}\}\): 日本人全体の集合。

複数の集合\(A_1,\ A_2,\ \ldots,\ A_n\)が与えられたとき、それぞれの集合の要素のタプル全体の集合というものを考えることができます:

\[
A_1 \times A_2 \times \cdots \times A_n:=\{(a_1,a_2,\ldots,a_n)\ |\ a_i \in A_i\ (1 \leq i \leq n)\}.
\]

これを、\(A_1,\ A_2,\ \ldots,\ A_n\) の直積といいます。特にすべての \(i\) について、\(A_i = A\) (すべて同じ集合)の場合、\(A^n\) と書きます。

同値関係

集合が与えられると、その中の元同士の関係が考えられることができます。例えば、整数全体の集合 \(\mathbb{Z}\) において、3で割ったあまりが等しい元同士を \(a \equiv b \mod 3 \) と書くことにすると、これは一種の関係です（この例は、3を法とする合同関係といいます）。

特に大事な関係が、次に示す同値関係というものです。上記の3を法とする合同関係も同値関係です。

証明はしませんが、同値関係があると集合を分割することができます。先程の3を法とする合同関係を例に出すと、整数の集合 \(\mathbb{Z}\) はこの同値関係について以下の3つの部分集合で分割されます:

\[
[0]:=\{3n\ |\ n\text{は整数}\},\ [1]:=\{3n+1\ |\ n\text{は整数}\},\ [2]:=\{3n+2\ |\ n\text{は整数}\}
\]

このように、同値であるような元たちを寄せ集めたもの(\([0],\ [1],\ [2]\))を同値類と呼びます。

そして、この同値類を元とみなして新しく集合を作ることができます。そのような集合のことを、その同値関係による商集合と呼びます。つまり、商集合は、集合を元とする集合になります。

同値類は[]で表すことが多く、その中に記載する文字は所属する元を代表させて記載します（このような元を代表元と呼びます）。そのため、\([0]\) の代表元を3や-6に置き換えることもでき \([0] = [3] = [-6]\) です。

先の3を法とする合同関係を例に取ると、この同値関係による商集合は次のような集合です:

\[
\{[0],\ [1],\ [2]\}
\]

サブネットマスクによるグループ化を集合論で捉えよう

本題の「サブネットマスクによるグループ化を集合論で理解する」パートに入りたいと思います！

準備

まず、2進数表示したIPv4アドレスの全体の集合を以下で定義します。

\[
\mathrm{IPv4} := \{0,1\}^{32}
\]

これは各要素が0または1の32個の数のペア全体になります。そのため、この集合には以下のような元が含まれます。

\[
(1,1,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,1) \in \mathrm{IPv4}
\]

上の元を10進数表示した場合 192.168.10.5 になります。IPv4アドレスは各桁が0か1の32桁の数全体と見れるため、\(\mathrm{IPv4}\)は0.0.0.0 ~ 255.255.255.255までのIPアドレス全体の集合と考えられます。以下簡単のために、\(IPv4\)の各元については、普段の2進数表示のIPアドレスの表記のように、8桁区切りで以下のように表します。

\[
11000000.10101000.00001010.00000101
\]

\(\mathrm{IPv4}\) の元 \(a,\ b\) において、各桁ごとに論理積を取った\(\mathrm{IPv4}\) の元を \(a \wedge b\) と定義します。

\(\mathrm{IPv4}\) の部分集合 \(\mathrm{Mask}\) を以下のように定義します。

\[
\mathrm{Mask}:=\{m \in \mathrm{IPv4} \ |\ \text{上位 \(r\) bitのみが 1 である}, \ 0 \leq r \leq 32\}
\]

集合 \(\mathrm{Mask}\) は2進表示したサブネットマスクの全体になります。

本題

\(m \in \mathrm{Mask}\) として \(\mathrm{IPv4}\) 上の関係 \(R_m\) を次で定義します。

\[
a R_m b \iff a\wedge m = b \wedge m \hspace{5mm} (a,\ b \in \mathrm{IPv4})
\]

これが同値関係になることを証明しておきましょう。

(反射律) \(a \wedge m = a \wedge m\) より \(a R_m a\)。
(対照律) \(a R_m b\) とする。このとき \(a \wedge m = b \wedge m\) なら \(b \wedge m = a \wedge m\) より \(b R_m a\)。
(推移律) \(a R_m b\) かつ \(b R_m c\) とする。このとき、 \(a \wedge m = b \wedge m\) かつ \(b \wedge m = c \wedge m\) より \(a \wedge m = c \wedge m\) となり \(a R_m c\)。

以上で、関係 \(R_m\) は \(\mathrm{IPv4}\) 上の同値関係であることがわかりました。
これにより、集合 \(\mathrm{IPv4}\) の同値関係 \(R_m\) による商集合を得ることができます:

\[
\mathrm{IPv4}/R_m = \{[a]_m \ |\ a \in \mathrm{IPv4}\}.
\]

ここで、\([a]_m = \{b \in \mathrm{IPv4}\ |\ a R_m b\}\) であり、\(a\) と\(R_m\) の意味で同値な \(\mathrm{IPv4}\) の元の全体となります。

そして、この商集合 \(\mathrm{IPv4}/R_m\) がサブネットマスク \(m\) によるサブネット全体の集合であり、各 \([a]_m\) はサブネットマスク \(m\) によるサブネットということになります！

サブネットマスクの振り返りの章で出した 192.168.10.5/24 を例に考えると、

\[
m=11111111.11111111.11111111.00000000
\]

であり、192.168.10.5 の同値関係 \(R_m\)による同値類は \([192.168.10.5]_m\)になります。ところで、同値類の代表元は、同じ同値類に所属する別の元に置き換えても良かったので、

\[
[192.168.10.5]_m = [192.168.10.0]_m
\]

となります。このように考えると、ネットワークアドレスというのは、この同値類における標準的な代表元とも見ることができますね。

まとめ

今回の記事は「サブネットマスクを数学的な視点（特に集合論）で捉え直そう」というコンセプトで書いてみました。数学に慣れていないと大変な内容だったかと思いますが、一つのことをいろいろな視点で捉え直すというのは、その概念をより深く理解するうえで大切なことと考えます。

今後もこういった捉え直す系の記事は書いていきたいと思っているので、引き続きよろしくお願いします。ここまで読んでいただきありがとうございました！