Cannot reduce complexity beyond necessary information and function

A Simple Function

a = b + c

If a is unknown, then the function cannot be performed without knowing both b & c. This is the necessary information required, to have any reasonable certainty as to what a is.

If only b is known, then c can be guessed, but the level of certainty would be very low.

Could a machine learning algorithm make a good guess about the value of c based on past values of c? Yes, but that would require much more information than the current value of c, and hence, more complexity both in the information and the machine language function. Complexity has not been reduced. Certainty is still highly probabilistic, dependent on the amount of data, and the accuracy of the algorithm.

Thus

  • If a is unknown
  • b & c are both required, in order to have minimal complexity, and good certainty, as to the value of a (assuming b & c are without error and are not falsehoods).

A simple but slightly more complex function

For function:

a = b + c

Certainty as to all values is only achieved by having at least two values:

  • a,b
  • a,c
  • b,c

If any of the above two values are known, with certainty, then the third value is also known (information theory: information reduces uncertainty).

The minimum information necessary for this information function is two of the variables. Complexity cannot be reduced lower than the input of these two values, and a function to derive the third value.

  • If a & b are known, then c = a – b
  • if a & c are known, then b = a – c
  • of b & c are known, then a = b + c

Thus

  • Two input values is the minimum information that must be acquired
  • The simplest equation of the above options is the minimum function complexity
  • Beyond these, complexity cannot be reduced

Determining the best path

To determine the best path from source to destination in a network, requires:

  • A definition of best path
  • A way to understand all paths (typically all links and all routers)

If router A tells router B what the best path is, router B does not know what router A’s definition of best path is, or how it was determined. Router B might trust by convention that Router A has used a well-known definition of best path. What though if router B has its own definition of best path?

For example, say router A defines best path as the lowest number of routers between a source and a destination, but router B defines best path as the highest aggregate bandwidth between source and destination with the least number of routers. Router A would be advising router B of a best path that does not match router B’s definition of best path.

If on the other hand, router B has knowledge of all the links and routers in a network, and all the capacities and performance metrics of each link, router B can determine for itself, according to its own definition, what the best path is. The same of course would be true of a centralized controller / path computation engine (PCE).

The above discussion approximates, in a very abstract way, the difference between BGP and a link state protocol (OSPF or IS-IS). BGP tells other routers what the best path is. OSPF allows each router to determine for itself what the best path is. In BGP, an assumption of what the best path is not present in the routing information exchanged, but is implicit in the agreements between implementors of the routing protocol.

Not only do link state protocols use a wide scope (& scale) of information to determine the best path, they also support each router determining for itself what the best path is, and hence, source routing models like segment routing are supported by link state protocols (when there is a mechanism to insert into packets, the description of a path – more information/complexity).

BGP does not support the scope of criteria for best path, or the self-determination by each router as to the best path, because the information it exchanges is less than that of a link state protocol.

  • BGP is a simpler protocol, with less state/information, and less capability (in this context only).
  • OSPF/IS-IS are more complex protocols, with more state/information, and more capability (in this context only)

Thus:

  • Complexity cannot be reduced beyond that of a link state protocol to achieve the same capability (assuming minimalist information and computation in the design and implementation of a link state protocol). 
  • BGP is less complex, in this context, but does not have the same capability (in this context).

If the inputs for a best path calculation are stored, then storage complexity would be part of the consideration as well.

This site uses Akismet to reduce spam. Learn how your comment data is processed.