A Theory for Analyzing Addressing Structures

Years ago, I described the “fundamental principle of routing” that “logical addresses correspond to physical locations”. This implies some kind of relationship between addressing structure and network topology. Using concepts from (mathematical) topology, we can make this relationship more precise, and obtain a theory for analyzing addressing structures. I use this theory particularly to note the inadequacy of CIDR and to establish a framework for analyzing possible extensions or replacements to CIDR.

BASIC CONCEPTS

Let’s begin with some defintions of terms. We need the concepts of a “set”, a “subset”, and a “set of subsets”. These terms are mostly, I hope, are self explanatory. To illustrate by example, consider the set FOUR={1,2,3,4}. Some subsets of FOUR are {1,2}, {3,4}, {1}, {1,3,4}, {1,2,3,4} (the set itself), and {} (the null subset). A set of subsets of FOUR might be ELEMENTS={{1}, {2}, {3}, {4}} (all subsets containing a single element) or PAIRS={{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}} (all subsets containing two elements).

The “union” of two or more subsets (written using “+”) is the subset of elements contained in at least one of the subsets. So, the union of {1} and {2}, {1}+{2}, is {1,2}, and the union of {1,2} and {2,3}, {1,2}+{2,3} is {1,2,3}.

A “topology” on a set S is a specified set of subsets of S. Either of the two sets of subsets in the example above could be used as a topology on FOUR, as could the “discrete topology”, which is the set of all possible subsets. Note: I’m using this term in a slightly different way than the mathematicians do. In particular, there is no requirement here that a union of subsets has to be contained in the topology. My definition of topology is more like what mathematicians would call a base for a topology.

An arbitrary subset X of a set can be “covered” by a topology if X can be expressed as the union of one or more subsets in the topology. For example (using FOUR again), the subset {1,2,3} can be covered by either ELEMENTS, since {1,2,3}={1}+{2}+{3}, or PAIRS, since {1,2,3}={1,2}+{2,3}, but the subset {1} can only be covered by ELEMENTS, not PAIRS.

A source topology S can be “mapped” into a destination topology D if all the subsets in S can be covered by D. A mapping is “injective” if each subset in S also appears identically in D; i.e, each subset in S can be covered by a single subset in D. ELEMENTS does not map into PAIRS, buts PAIRS maps into ELEMENTS, although the mapping is not injective. Both ELEMENTS and PAIRS map injectively (as do all topologies) into the discrete topology.

A topology S can map “almost injectively” into another topology D if “almost” all of the subsets if S appear in D (but not all of them). A topology can be said to be “more injective” or “less injective” accordingly as “more” or “less” of the subsets map injectively. These are loose terms and could be made precise, but that isn’t necessary to get the idea of this theory.

ROUTING TOPOLOGY

A network’s “routing topology” is formed as follows. For each node in the network, construct a shortest path to all other nodes. Group these shortest paths according to the first hop, i.e, how they would appear if they could all be summarized together in the node’s routing table. For each possible first hop, group together all nodes which route through it into a subset. Add this subset to the topology, if it isn’t present there already. Repeat for all nodes.

A network’s “failure topology” is formed by constructing the union of all possible routing topologies that result from deleting any number of links from the original topology. A failure topology probably also requires adding a new routing destionation, “unreachable”, to each node.

ADDRESSING TOPOLOGY

An addressing topology is the set of all subsets, each of which is the set of all nodes that can be exactly addressed by a single entry in a routing table.

FUNDAMENTAL PRINCIPLE

The fundamental principle of this theory is that the utility of an addressing scheme is directly related to the injectiveness of mapping the network topology into the addressing topology. A perfectly injective mapping would mean that each set of destination nodes to be routed via a next hop can be mapped to a single addressing entry, i.e, that optimal routing tables can be constructed throughout the network using single routing table entries for each next hop.

To handle possible link failures, we would also like the failure topology to map injectively into the addressings topology as well.

If the network topology can not map at all into the addressing topology, then it is not possible to construct optimal routing tables using this addressing scheme. If the mapping exists but is not injective, then optimal routing tables can be constructed but at least one will require multiple entries for a single next hop.

EXAMPLE: CIDR’S ADDRESSING TOPOLOGY

We want to know CIDR’s addressing topology. Certainly all addresses that share a common bit prefix form subsets in the addressing topology. Thus, all nodes with addresses of the form 10.1.1.X form a subset in the CIDR topology, because 10.1.1.0/24 matches all 256 of these addresses. On the other hand, {10.1.1.1, 10.1.1.100} is not a subset in the CIDR topology (but read on), because this pair of addresses can not be exactly matched by a single CIDR prefix.

We’ll write CIDR prefixes with holes in them using one or more minus signs. Ex: 10.0.0.0/8 – 10.1.0.0/16 is a subset in the CIDR addressing topoogy meaning all addresses beginning with 10 in their first eight bits, except those that begin 10.1 in their first sixteen bits.

Now the longest-match rule complicates things quite a bit. In addition to pure common bit prefix subsets, we can also construct subsets consisting of common bit prefixes with “holes” punched in them corresponding to longer, overriding, prefixes. But these holes don’t appear randomly. They have to correspond to other entries in the routing table. This leads to a bizarre interaction between CIDR’s addressing topology and a particular routing topology it might be used in. A prefix with “holes” (in the addressing topology) can map to a particular subset in the routing topology only if the holes correspond exactly to the union of other subsets in a particular node’s routing subsets.

Consider these prefixes:

A: 10.1.0.0/16 - 10.1.1.0/24 - 10.1.100.0/24
B: 10.1.0.0/16 - everything in 10.1.0.0/16
                      other than 10.1.1.0/24 and 10.1.100.0/24, i.e:
    10.1.0.0/16 - 10.1.128.0/17
 	       - 10.1.32.0/19 - 10.1.64.0/19
 	       - 10.1.16.0/20 - 10.1.112.0/20
 	       - 10.1.8.0/21 - 10.1.104.0/21
 	       - 10.1.4.0/22 - 10.1.96.0/22
 	       - 10.1.2.0/23 - 10.1.102.0/23
 	       - 10.1.0.0/24 - 10.1.101.0/24

Now A could be used with a routing table that had routes to 10.1.1.0/24 and 10.1.100.0/24 on two other links, but if those two routes went out the same link, they wouldn’t be injective. In particular, you couldn’t use prefix B to address them both out the same link, though you could use prefix B (injectively) on a node with, let’s see, 13 other links. In this case, you _could_ address 10.1.1.0/24 and 10.1.100.0/24, injectively, out the same link, using a single prefix (10.1.0.0/16) and letting longer match routes for the other 13 links override everything except 10.1.1.0 and 10.1.100.0.

Now this all might seem pedantic, but the objective is to determine when a network topology can be injectively addressed (i.e, using a single routing table entry for each next hop) using a particular addressing scheme, and the point here is that if you allow arbitrary holes to be punched in a CIDR prefix, then you can “address” just about anything.

EXAMPLE: A TREE TOPOLOGY

Consider a basic tree topology, perhaps:

                             A
                             / \\ 
                            /   \\
                           /     \\
                         B       C
                         / \\     / \\
                        /   \\   /   \\
                       D   E   F   G

Now, what is its network topology? Well, consider first node A. Nodes B, D, and E all route through node B, so {B,D,E} is in the network topology, as is {C,F,G}. Considering node B, we conclude that {A,C,F,G} is in the network topology (because all these nodes route via A) and also that {D} and {E} are there, because each routes to itself. D contributes a single subset, consisting of all other nodes in the network (they all route through D’s single like to B). Continuing like this, we construct the following network topology:

	{B,D,E}, {C,F,G}, {A,C,F,G}, {D}, {E}, {A,B,D,E}, {F}, {G},
 	{A,B,C,E,F,G}, {A,B,C,D,F,G}, {A,B,C,D,E,G}, {A,B,C,D,E,F}

Next, now we want to see if CIDR can efficiently address this network topology. Let’s try a straightforward assignment of addresses:

                             A  10.1.1.1
                             / \\
                            /   \\
                           /     \\
           10.2.1.1 B       C 10.3.1.1
                         / \\     / \\
                        /   \\   /   \\
                       D   E   F   G

D=10.2.2.1      F=10.3.2.1
E=10.2.3.1      G=10.3.3.1

{B,D,E} = 10.0.0.0/8 - 10.1.0.0/16 - 10.2.0.0/16
{C,F,G} = 10.0.0.0/8 - 10.1.0.0/16 - 10.3.0.0/16
{A,B,D,E} = 10.0.0.0/8 - 10.2.0.0/16
{A,C,F,G} = 10.0.0.0/8 - 10.3.0.0/16
{D} = 10.2.2.1/32   etc.
{A,B,C,E,F,G} = 10.0.0.0/8 - 10.2.2.1/32   etc.

So, yes, this CIDR addressing scheme is injective, and therefore all routing tables can be constructed using single entries for each next hop.

TODO: show that CIDR addresses can be (mis)assigned so the network can’t be addressed efficiently

TODO: show that CIDR can injectively address any tree topology

EXAMPLE: A RING TOPOLOGY

Now consider a ring topology:

                            A
                            / \\
                           /   \\
                          /     \\
                         B       E
                         |       |
                         |       |
                       C-------D

A contributes {B,C} and {D,E} to the routing topology. Reasoning likewise for the remaining nodes, we conclude that the routing topology is:

{B,C}, {D,E}, {C,D}, {A,E}, {A,B}

In other words, the routing topology consists of all pairs of adjacent nodes.

Can CIDR injectively address this topology? It cannot, and here’s a proof:

Each pair of adjacent nodes shares a common bit prefix. Now, of these common bit prefixes of adjacent nodes, there is a shortest length, though several of the common bit prefixes may all be of this length. Without loss of generality, we can rename our nodes so that A and B share a shortest common bit prefix. Call the length of this bit prefix ‘n’. Now since all pairs of adjacent nodes share a common bit prefix, at least as long as ‘n’, we conclude that all the nodes must share the same common ‘n’-bit prefix as A and B.

Furthermore, there has to be at least one other pair of adjacent nodes whose common bit prefix is also of length ‘n’. Why? Well, consider what would happen if there wasn’t; if all the other pairs of adjacent nodes shared bit prefixes longer than ‘n’. Then, starting at A, you could head around the ring in the _opposite_ direction from B, and going all the way around the ring conclude that A and B must share a common bit prefix longer than ‘n’. This is a contradiction. So in addition to A and B, there has to be at least one other pair of adjacent nodes whose common bit prefix is exactly ‘n’.

There are two cases to consider. We’ll handle the easier one first – one of the other ‘n’-bit prefixes is not adjacent to either A or B. So let’s assume that C/D is another ‘n’-bit prefix (it could just as well be D/E). Now the problem is to construct E’s routing table; it has to address both {A,B} and {C,D}. Since both pairs share only the common ‘n’-bit prefix, any single prefix that matched the one pair would also match the other. Therefore, it’s impossible to construct E’s routing table injectively; at least one of either {A,B} or {C,D} would require multiple entries in the routing table.

So we conclude that the other ‘n’-bit prefixes can only be adjacent to A or B. In fact, there can only be one other ‘n’-bit prefix, since if both B/C and A/E were ‘n’-bit prefixes, then we’d have two non-adjacent ‘n’-bit prefixes and the same argument as above would apply (relative to D’s routing table this time). Let’s say the other pair is B/C (it could just as easily be A/E), so that A, B, and C all share a common n-bit prefix (and no longer). Obviously, B has to differ from both A and C in the n+1 bit.

Consider A’s routing table. It has to address both {B,C} and {D,E}. Since all the nodes share the common ‘n’-bit prefix, and B and C share nothing longer than ‘n’ bits, the only way to injectively construct A’s routing table is for {B,C} to be matched by an ‘n’-bit prefix and for {D,E} to override it with a longer match. Let’s say this match is ‘m’ bits long. Now C and D have to share a common prefix shorter than ‘m’ bits, because otherwise C would be included in the ‘m’-bit {D,E} match that has to override the ‘n’-bit {B,C} match.

Likewise, considering C’s routing table with the same logic leads to the conclusion that A and E also have to share a prefix shorter than ‘m’ bits. So the picture must look like this: A, B, and C share an ‘n’ bit prefix, D and E share an ‘m’ (> ‘n’) bit prefix, and both C/D and A/E share prefixes shorter than ‘m’ bits.

But now it is impossible to injectively construct B’s routing table! It has to address both {C,D} and {A,E}. Since C/D’s prefix is shorter than D/E’s ‘m’ bit prefix, any single entry addressing {C,D} would also include E, so we’d have to address {C,D} with a shorter match and then override it with a longer match for {A,E}. But by the same logic, since A/E’s prefix is also shorter than D/E’s, anything matching {A,E} would also match D! This is impossible, so therefore B/C can not be the other pair with an ‘n’-bit prefix, nor can any other pair, and we conclude that it is impossible for CIDR to injectively address a five-element ring.

TODO: rework this for per-interface instead of per-node addresses

On the other hand, there is a simple addressing scheme that _can_ injectively address this loop: the mod-5 number system!

Number the nodes around the loop 0, 1, 2, 3, 4, and construct routing tables based on modulo arithmetic. A routing table entry for ‘2-4’ would match 2, 3, and 4, while an entry for 4-1 would match 4, 0, and 1. Now it is a trivial exercise to injectively address the topology. Let’s say A=0, B=1, and so on:

                             A 0
                            / \\
                           /   \\
                          /     \\
                      1 B       E 4
                        |       |
                        |       |
                      2 C-------D 3

Now our injective routing entries are simply:

	{B,C} = 1-2 	{D,E} = 3-4 	{C,D} = 2-3 	{A,E} = 4-0 	{A,B} = 0-1

I don’t think it’s that hard to see that no loop can be injectively addresses by CIDR, by exactly the same argument: there have to be at least two common prefixes of shortest length, and they can not be non-adjacent, nor can they be adjacent. On the other hand, a loop of any size can be injectively addressed using a modulo numbering scheme.

CONCLUSION: THE CHALLENGE

By this point, perhaps you’re beginning to wonder the utility of all this. After all, couldn’t we design an addressing system consisting of a bitmask with one bit for every node in the network? Then it would be possible to injectively address any topology, right? The answer, of course, is yes, but such an addressing scheme would be completely unwieldly. Another measure of the cost of any addressing scheme is size of the routing table entries. CIDR requires a single address (32 or 128 bits, if you’re using IPv4 or IPv6) plus enough additional bits (5 or 8, respectively) to hold a prefix length. A modulo-based addressing scheme would require two addresses. The bitmask scheme suggested earlier in this paragraph would require 2^32 bits = 2^29 bytes > a trillion trillion bytes for each addressing entry.

On the other hand, I hold a deep set (but rigorously unproven) suspicion that a purely random network topology could not be injectively addressed by much of anything less than the bitmap scheme. Fortunely, we don’t have a random network topology – our network topology is ultimately based on real physical devices, interconnected by real physical cables, or at least in close enough proximity for real physical radio waves to propagate between them.

The challenge, therefore, is to design an addressing scheme that can injectively or near-injectively address the Internet topology. CIDR clearly can’t cut it; it can’t injectively address anything with loops, but since modulo addressing can address loops, there is hope that something can be designed that could injectively address a mixed loop/tree topology. I’d suggest modeling the Internet as the failure topology of a tree imposed on top of a torus, and try to find an injective addressing scheme for this.