Network Science: Reducing Entropy, for a Given Capability, With a Desired Outcome, Through Space
The art of revealing and using what is missing
Image source: Wikimedia Commons
The Important
Networking is:
The science of reducing missing information / entropy for a given capability, with respect to copying information (classical networking) or transferring information (quantum networking) from one point in space (spacetime) to another, through one or more transmit/receive functions, with respect to desired outcomes.
What information is missing / necessary
What different routing protocols are capable of, is a function of the questions they answer, manifest in the information they exchange.
BGP answers the question, what information needs to be sent to another router so it knows the best path to a network prefix.
OSPF/IS-IS answer the question: what information does each router require, to determine by itself, the best path through a topology, based on shortest path, least cost, and/or other traffic engineering information.
Where should missing information be exchanged
A generic label, for example MPLS, facilitates hardware that can transition without change through multiple significant control plane and end user data plane changes, for example IP/MPLS to SR MPLS; IPv4 to IPv6. The “cost” of that capability is the complexity of a mapping function.
Self-describing protocols, with respect to destination address, for example IPv4 & IPv6, do not require the additional complexity of a mapping function. The situation with respect to SRv6 is a little more complicated, see: IS-IS extensions and OSPF extensions.
Another important question is how efficiently can information be exchanged and what impact does that efficiency have on control plane processing.
Routing, in the foreseeable future, will lack perfect information, and will always involve some uncertainty, and likely some packet loss/looping, when network events occur.
Routing/networking is a hard problem, not perfectly solved.
Routing/networking is a hard problem, that imperfectly delivers significant value, as evidenced by Internet activity.
Networks have control plane protocols optimized for inter-AS and intra-AS routing based on varying administrative conditions and varying preferences for capacity, capability, and quality.
Networking Science
Networking is the science of reducing missing information / entropy for a given capability, with respect to copying information (classical networking) or transferring information (quantum networking) from one point in space (spacetime) to another.
‘Shannon replied that the theory was in excellent shape except that he needed a good name for "missing information". "Why don’t you call it entropy?" von Neumann suggested…Shannon took his advice.’ Information Theory and Predictability.
‘In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent in the variable's possible outcomes’ Wikipedia, “Entropy (information theory”
If you are attempting to do something, you need the information necessary to do it. If you do not have the necessary information, you may have enough information to increase probability, but you are still rolling the dice, with the outcome being uncertain.
More simply:
If A + B = C
You cannot know:
C, unless you know A & B
A, unless you know B & C
B, unless yo know A & C
One of the most distinctive properties of the universe we live in / can perceive, is space. Information is distributed in space. Networks overcome the challenges of space by copying and/or transferring information through space. Latency is the unavoidable consequence of space, a universal speed limit (the speed of light) and uncertainty. Networking / network science is concerned with the movement of information, through space.
The Critical Question: What Information is Missing / Necessary
Networking control plane problems are largely information problems. To some extent, forwarding plane problems are as well. To achieve desired outcomes, networks often use information in both the control plane and information embedded in packets themselves. Information necessary to compute a result sometimes requires information from both.
If we start from a blank state, where we know nothing about anything, engineers must ask “what information is necessary so that a function can be computed”. Answers with good fit, start with good questions, to which optimizations are applied to address constraints and desired outcomes.
BGP answers the question, what information does another router need to know, to understand the best route. (speculation: original design intent not referenced).
OSPF/IS-IS answer the question, what information does each router need to know, to understand the entire topology, from which the best route can be selected. (speculation: original design intent not referenced).
Through extensions. OSPF/IS-IS answer the question, what information does each router need to know, to make routing decisions, based on properties other than the number of hops / least cost. These extensions are referred to as traffic engineering extensions.
In contrast to BGP, OSPF / IS-IS have:
Less missing information about the entire topology
Less uncertainty about the entire topology
Necessary information for a wider scope of route selection criteria
Necessary information for a wider scope of traffic engineering capabilities
Different routing protocols answer different questions. Different routing protocol control planes exchange different information. Different routing protocols exchange the necessary information for different capabilities, to answer different questions.
What different routing protocols are capable of, is a function of the questions they answer, manifest in the information they exchange (the presumed engineering answer).
Should BGP be replaced with OSPF/IS-IS?
The capabilities provided by OSPF/IS-IS are predicated on the assumption that information exchanged will not be deliberately and explicitly tampered with for the purposes of effecting a different intent. More simply, a single administrative domain where it is assumed all routers are working towards a common administrative goal.
The same is not true for inter-Autonomous system (AS) routing. ASs have conflicting objectives/behavior based on their for-profit goals, not-for-profit goals and operations philosophies. In the presence of these conditions, some OSPF/IS-IS capabilities would not be realized if used for inter-AS routing.
Additionally, some BGP capabilities commonly used, are currently not well developed in OSPF/IS-IS.
The question of OSPF/IS-IS scale limits changes over time.
This article does not rule out the possibility of partnering/cooperating ASs using OSPF/IS-IS (probably with new extensions) in new ways. No shift in this direction was known at the time of writing.
Should OSPF/IS-IS be replaced with BGP
BGP has policy/tagging capabilities not well developed in OSPF/IS-IS, that have been useful in inter-AS routing. Some of these can be repurposed for intra-AS routing, as has been the case, notably, in some data center networks.
Overall, the question comes down to what optionality a network operator desires, and what tradeoffs between network infrastructure, operations, and service capacity, capability, and quality, an operator wishes to make. The answer is, it depends.
The knowledge OSPF/IS-IS have of the complete topology and extended traffic engineering information, makes them a good fit for:
Routing based on properties other than number of hops / least cost
Source routing
The tradeoff is increased state. Increased state has equipment cost implications (which vary over time) and control plane interaction implications.
QED
Networks have control plane protocols optimized for inter-AS and intra-AS routing based on varying administrative conditions and varying preferences for capacity, capability, and quality.
The Critical Question: Where Should Missing Information be Communicated
An IP packet has more information than many tunnel headers, for example, an MPLS label. An IP packet contains both the source and the destination address as well as the upper-layer protocol. A common MPLS label, representing a network prefix mapping, does not - the interpretation of the MPLS label is known by the control plane.
An MPLS label is mapped within the control plane to network prefixes, in the case of IP/MPLS, and to network segments, in the case of SR MPLS (segment routing for MPLS). More information is added in the control plane in response to the forwarding plane / MPLS label having missing information, compared to an IP packet. The missing information includes the destination address.
Both IP/MPLS and SR MPLS require information to be mapped. IP/MPLS uses separate control plane protocols to perform the mapping: LDP & RSVP-TE. SR MPLS integrates the mapping into the IGP (OSPF or IS-IS). SRv6 uses IP addressing in the forwarding plane, including segment lists. Some IGP extensions are still required for SRv6, see: IS-IS extensions and OSPF extensions.
A generic label, for example MPLS, facilitates hardware that can transition without change:
Through multiple significant control plane changes, for example IP/MPLS to SR MPLS. The “cost” of that capability includes the complexity of a mapping function.
Through multiple significant and concurrent user planes, for example IPv4 and IPv6. Where user plane refers to the format of information entering a network / administrative domain.
Through multiple layer 2 or layer 3 networking user plane services, in addition to other capabilities, for example ECMP entropy reduction.
A self-describing packet header, for example IPv4 or IPv6, does not require a mapping function, but the hardware is:
Either limited to a specific user plane or has to be engineered for multiple different user planes.
IPv4 and IPv6 user planes can be routed over networks that utilize different tunneling options.
The above are just some considerations. There are other consequences of using labels or IP packet headers for routing capabilities, discussed elsewhere, for example: SRv6 Deployment Consideration.
Efficiency of Information Exchange
While the necessary information for a compute function does not change, how the necessary information is exchanged can be more or less efficient, both at the symbol transmission level, as well as the overall protocol design level.
See information theory and the Shannon limit for symbol exchange.
Example of control plane protocol design: ‘So, instead of saying “here’s a route and these are its attributes…” for every NLRI advertised the Update message basically says “here’s a group of path attributes and here are the routes that these apply to…” This cuts down on the number of messages that needs to be sent across the network. In this way, each Update message forms a unit of its own and has no further fragmentation concerns.’ ScienceDirect.
The efficiency of information exchange had critical importance when low-speed links were used. The efficiency of information exchange may still have implications for control plane protocol processing, either in the processing of uncompressed/explicit information for each network prefix and/or the decompression of compressed information/implicit information. However, the necessary information for the compute function, does not change.
Vexing Challenges In Networking
Today, there is no known method for copying and/or transferring information, instantaneously, with certainty/without delay inducing error correction (quantum error correction). As a result, information within a network of routers is relative: different routers have different information at different times, and the sequence of events is different for different routers due to varying distances from multiple events.
It is possible to reduce time uncertainty by using time stamps. An approach that is already used in some computer/networking protocols.
It is possible to further reduce uncertainty by using timestamps based on a common / synchronized highly precise atomic clock, referenced by all routers, for example GPS. An approach not widely deployed, or maybe even significantly leveraged at all, with respect to Internet routing control plane protocols.
Without instantaneous copy/transfer with certainty, it may never be possible to dictate the sequence in which event information is received, without delaying network convergence (holding back all event information copy/transfer to an agreed future time).
Routing, in the foreseeable future, will lack perfect information, always involve some uncertainty, and likely some packet loss/looping/desired outcome degradation, when network events occur.
Routing/networking is a hard problem, not perfectly solved.
Routing/networking is a hard problem, that imperfectly delivers significant value, as evidenced by Internet activity.
Focusing on an (unattainable) perfect, delays the realization of a good.
Conclusion
The more capabilities we desire in networks:
The more missing information is required
To decrease uncertainty
With respect to a desired capability / outcome
Network engineering has a great deal to do with missing information, whether it is in the forwarding plane or the control plane. This point is both obvious and intuitive, however it is worth emphasizing.
If a network needs to do something, the first engineering question should often be “what information is missing?”. Uncertainty is decreased, and routing decision accuracy is increased when necessary information is not missing.
A second critical question is “how missing information should be exchanged?”; through the control, forwarding, management planes, and/or other mechanisms.
A third interesting question is how efficiently can information be exchanged and what impact does that efficiency have on control plane processing.
As information is relative, today, there continues to be exploration of how best to design/operationalize routing, in the presence of significant and/or marginal uncertainty.