Subnetting (read "Logarithmic") Arithmetic

All networking types daily make use of arithmetical operations optimized to deal with a fixed number of digits in base-2. These operations are most often performed mentally, with little thought given to the underlying rules the optimized manipulations obey. This is not to say the mechanics of the operations are not considered--indeed, it is only by acute awareness of the binary structure that one may come to grok subnetting at all--but rather the leap from binary arithmetic to subnetting arithmetic is often only tacitly understood. However, in tutoring others on this topic, I've come to develop what I gather is a very clear picture of how we optimize our day-to-day calculations. And, most importantly, my insights are universal in that many others have independently arrived at the same conclusions I have. Therefore, I believe my attempts at developing rigorous notions of these optimizations can be of some value.

The Importance of Counting
Before I embark on paths less familiar (at least to me), permit me to make two assertions:

1. Subnetting (and, indeed, most everything, as computers have proven) is a function of counting
2. Counting, where exponential quantities are concerned, is made expedient by logarithms

This second point, I address first, as it is likely the most obvious, mathematically, but may be the least obvious for those who entered networking as a trade discipline.

To understand how logarithms facilitate counting, consider the humble yet ubiquitous decibel unit, most oft, and most fondly, expressed as the familiar 'dB'. This unit makes life easier by turning very large or very small base-10 numbers into those numbers we most commonly use when counting, i.e. 1, 2, 3, etc. The way the decibel does this is by expressing numbers in terms of base-10 exponents. For example, the number 1,000,000 equals 1,000 times 1,000, but, in decibels, this is equivalent to 60 dB = 30 dB + 30 dB. In fact, in bels (of which a decibel is one-tenth), this calculation is arguably simpler: 6 bels = 3 bels + 3 bels. The important thing to understand is that logarithms, in this respect, shift numbers from those magnitudes we find less intuitive back towards a more natural range, all the while turning problems requiring multiplication and division into problems of addition and subtraction.

As to why subnetting implies counting, I need only ask the networkers, "What three consecutive /24s occupy half of the third /23 in 192.168.12.0/21?" Giving this only a few seconds thought, I suspect most anyone well-acquainted with subnetting will undoubtedly spot a problem with the question as posed. My point to such a one is that they need only review the thoughts that manifested when parsing the question to realize how many different ways of counting are involved.

Waxing Metaphysical
One interesting thing about subnetting is how, when answering questions such as the one posed, the object of our search seems somehow more tangible than the question might otherwise suggest. It's as if you were asked to find the only three blue stones in a pile of grey ones: you need only move the stones you don't want so as to more clearly see the ones you do. At no point do you feel you must somehow "work out" the problem. The answer is right there; you need only reach your hand in and pull it out. At least, that's how it seems if you're a networker, by profession.

Permit me, then, to expose my thinking when answering the question, "What three consecutive /24s occupy half of the third /23 in 192.168.12.0/21?" (Two, four,) Eight means the first address of 192.168.12.0/21 is actually 192.168.8.0/21. The top of the third /23 is (two times three) six /24s up from the bottom, is 192.168.13.0/23. There are two answers: {192.168.13.0/24, 192.168.14.0/24, 192.168.15.0/24}; and {192.168.10.0/24, 192.168.11.0/24, 192.168.12.0/24}.

At no point do I perform any base conversions or binary arithmetic: all my calculations occur at the level of base-2 exponents--and all involve counting. If you aren't very familiar with subnetting, shorten addresses like "192.168.12.0/21" to the utterance "twelve-slash-twenty-one," and you may catch a flavor of how we instinctively focus on only the most crucial information.

Fundamental Operations
In very nearly (or, maybe, absolutely) all cases, subnetting arithmetic is limited to three types of operations:

1. Adding or subtracting base-2 exponents
2. Adding or subtracting 2ⁿ in series (nearly the same)
3. Finding "best-fit" allocations, given some desired number of IPs

What follows are examples of each type of operation.

The following questions may be answered by adding or subtracting base-2 exponents or 2ⁿ: "What is the network/broadcast address of a given /x?"; "How many /x are in /y?"; "What /x contains n · /y?"; "What fraction of /x is /y?". In all such cases, you are given some prefix-length (or a subnet mask, which merely requires you memorize the mapping {1<=>128, 2<=>192, 3<=>224, 4<=>240, 5<=>248, 6<=>252, 7<=>254, 8<=>255} or its inverse-mask counterpart) and are then asked to represent it in terms of some other prefix-length. If you're already capable of counting by 2ⁿ (2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, etc.), then these problems always come down to 2^a · 2^b or 2^a/2^b, which, given the laws of exponents, really only involve a + b and a - b.

Imagine you wish to know what fraction of one /24 a /26 is. In other words, what number multiplied by 2²⁶ equals 2²⁴? Though you may already know this to be 1/4, the arithmetic for this operation--depending on how you approach it--looks like this:

        2²⁴/2²⁶ = 2^-2 = 1/2² = 1/4

However, if base-2 logarithms and the laws of exponents are used to simplify the problem, it really looks like this:

        26 - 24 = 2
        1/(2 · 2) = 1/4

Easy, right? This same procedure is really used for all problems in this vein. Consider the problem, "How many IPs are in a /21?" Again, knowing how to count by 2ⁿ makes this quite easy if you start from /24:

        256 (0)... 512 (1)... 1024 (2)... 2048 (3)

Here, the non-parenthetical numbers are "spoken" and the parenthetical numbers are "understood." That is, when making such calculations, I mentally say "256, 512, 1024, 2048" while keeping track of how many numbers I've rattled off in my head. Not everyone needs this crutch: some choose to simply memorize 2048 as the number of IPs in a /21. But I have a severe deficiency in basic arithmetic, and I prefer to count out the amounts. Someone just learning to subnet will likely do the same.

And what of "best-fit" allocations? These I consider unique because of the way in which multiple constraints may be imposed, affecting the precise allocation strategy. Nevertheless, certain patterns prove particuarly useful. Consider the requirement, "365 users, plus 20 reserved IPs, plus network/broadcast addresses need public IPs." This amounts to 387 IPs, altogether, and one best fit, notwithstanding various other constraints, might be calculated as follows:

        256... 512 (> 387) - 387 = 125 left over
        256 - 125 = 191 left over
        /23 + /24 is a "best fit" allocation

Of course, one could instead choose to route a /23 and a /25 for a "tighter" allocation, but blocks in the public ranges must be "globally" routable, and there is surely no ISP in the world willing to advertise a block smaller than /24. Nevertheless, this pattern--/n + /(n+1) + /(n+2) etc.--is sufficiently common to be considered its own operation. And yet, common though it may be, the explicit definition of this operation and the mathematical proof of its correctness are not common at all. In fact, mine is the only such attempt at a rigorous definition I've found.

What follows is my best shot at providing a complete justification for the use of this pattern--1/2 of, plus 1/2 of 1/2 of, plus 1/2 of 1/2 of 1/2 of...

Pudding, Therefore Proof
Let s denote the bit-length of an IP address such that 2^s∈ ℕ. A system S_s denotes the set of all addresses of bit-length s. For example, the system S₃₂ is the set of all addresses in IPv4. We shall not always indicate the bit-length of a given system, choosing instead to refer to an address in S or all systems S, and so on. Indeed, for any system S, a valid operation for an address of bit-length s is also said to be in S, but the intended sense of this convention will always be made clear.

A subnet mask for an address of length s consists of l binary 1s and s - l binary 0s, where l ∈ ℕ, 0 ≤ l ≤ s, and, by extension, 2^l · 2^{s - l} = 2^s produces the total number of addresses in S_s, which we denote |S_s|. Let us then introduce the mathematically awkward, albeit relevant, notation /l := 2^{s - l} (pronounced "slash ell") to be the prefix-length of some addresses in S_s.

Theorem: (1/2ⁿ) · /l = /(l + n), n ∈ ℕ, 1 ≤ 2ⁿ ≤ 2^{s - l}
Proof.   Let us define a number n ∈ ℕ such that 1 ≤ 2ⁿ ≤ 2^{s - l}. It follows that 0 ≤ n ≤ s - l, or l ≤ l + n ≤ s, and certainly 0 ≤ l + n ≤ s. Consequently, we may construct a prefix-length /(l + n) = 2^{s - (l + n)} which, by applying the algebraic properties of logarithms and exponents and substituting the definition of /l, readily becomes (1/2ⁿ) · /l, as claimed.

□

By extension of the preceding theorem, the case (a/2ⁿ) · /l = a · /(l + n), a ∈ ℕ, is trivial. However, it is useful to prove a unique formulation for the special case (2ⁿ - 1)/2ⁿ · /l, and in so doing, we must first establish that (2ⁿ - 1)/2ⁿ = (1/2) + (1/4) + (1/8) + · · · + (1/2ⁿ) for all n ∈ ℕ, which we here show by induction.

Lemma: \(\frac{2^n - 1}{2^n} = \sum_{k=1}^{n} \frac{1}{2^k} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots + \frac{1}{2^n}\), n ∈ ℕ, n ≥ 1
Proof.   Let n ∈ ℕ and n ≥ 1. Given a proposition P(n) = \(\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots + \frac{1}{2^n} = \frac{2^n - 1}{2^n}\), we take P(1) to be \(\frac{1}{2} = \frac{2^{1} - 1}{2^{1}}\), which clearly holds. We therefore assume P(n) and express P(n + 1) as

\[\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots + \frac{1}{2^{n+1}} = \frac{2^{n+1} - 1}{2^{n+1}}\]

                                                                                  \[= \frac{2^{n+1} - 2}{2^{n+1}} + \frac{1}{2^{n+1}}\]

                                                                             \[= \frac{2^{n} - 1}{2^{n}} + \frac{1}{2^{n+1}}\]

Thus P(n + 1) is proven. Therefore, it follows by induction that P(n) is indeed true for all n ∈ ℕ, n ≥ 1.

□

Theorem:  \(\frac{2^{n}-1}{2^n} \cdot /l = \sum_{k=1}^{n} /(l+k) = /(l + 1) + /(l + 2) + \cdots + /(l + n)\), n ∈ ℕ, n ≥ 1

Proof.   Given the preceding lemma, we may write

\[\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots + \frac{1}{2^n} = \frac{2^n - 1}{2^n}\]

Multiplying both sides by 2^{s - l}, we obtain

\[2^{s-(l+1)} + 2^{s-(l+2)} + 2^{s-(l+3)} + \cdots + 2^{s-(l+n)}= \frac{2^n - 1}{2^{n}} \cdot 2^{s-l}\]

And by definition /l := 2^{s - l}, we substitute to obtain

\[/(l + 1) + /(l + 2) + /(l + 3) + \cdots + /(l + n) = \frac{2^n - 1}{2^{n}} \cdot /l\]

Which is what we sought to prove.

□