a moveable beast

A Note on Networks

Because an address is a natural number, the CIDR (Classless Inter-Domain Routing) notation x/l actually denotes an equivalence relation induced by f(x) = x - x mod 2^{n - l} defined on the set A = Z/2ⁿZ where l and n are natural numbers and 0 <= l <= n. In the case of IPv4, the equivalence relation induced by f(x) is defined on the set A = {0, …, 2³²-1} where 0 <= l <= 32.

The resulting equivalence class for a given x (i.e the set of all addresses to which x is equivalent under the equivalence relation) is commonly referred to as a prefix. A given CIDR x/l denotes a prefix iff x = x - x mod 2^{n - l}, in which case l is called the prefix-length. This is a stronger requirement than equivalence because only the lowest address in the equivalence class can be used to denote a prefix. When any other address from the same equivalence class is given in CIDR format, the corresponding prefix may be inferred, but the two objects are not the same. The special prefix x/n always denotes the one address it contains.

A route is an ordered tuple (d, h) containing a prefix d and an address h, where d is the route’s destination and h is the route’s next-hop. In a router, a routing process keeps a table of such routes. Upon receipt of a packet, the routing process applies the aforementioned equivalence relation to the packet’s destination address for all prefix-lengths when searching its routes for the longest (most specific; largest prefix-length) matching route destination. If a matching destination is found, the corresponding next-hop address is used to determine over which interface the packet should be forwarded, as well as the data-link header in which to encapsulate it.

A route for which the next-hop is zero is called a connected route, and the destination of such a route is called a directly-connected subnet or a directly-connected network. A route for which the destination has a prefix-length of zero (the trivial equivalence relation) is called a default route. A connected route that is also a default route is commonly referred to as the discard or catch-all route. A route for which the destination contains only one address is called a host route. A host route in which the destination is equal to the next-hop is called a point-to-point route.

All addresses bound to a routing process are assigned to interfaces, whether physical or virtual. Unsurprisingly, assignment also binds a given interface to a corresponding prefix, which means overlapping prefix bindings cannot exist in the same routing process.

Because a router will necessarily have multiple interfaces, no single address uniquely identifies the corresponding routing process. This is also true of multi-homed end-hosts having multiple interfaces, where the inadequacies of this architecture are even more pronounced (e.g DNS must be used for failover because there are no identifiers which designate the end-host, the application, or the application instance). As John Day would say, TCP/IP has a physical memory space but not a virtual one.