content: Add initial page on Ouroboros model

1 files changed, 235 insertions, 0 deletions

diff --git a/content/en/docs/Concepts/ouroboros-model.md b/content/en/docs/Concepts/ouroboros-model.md
new file mode 100644
index 0000000..3b6cc31
--- /dev/null
+++ b/content/en/docs/Concepts/ouroboros-model.md
@@ -0,0 +1,235 @@
+---
+title: "The Ouroboros model"
+author: "Dimitri Staessens"
+
+date:  2020-04-07
+weight: 2
+description: >
+   Computer Network fundamentals
+---
+
+```
+Computer science is as much about computers as astronomy is
+about telescopes.
+  -- Edsger Wybe Dijkstra
+```
+
+The model for computer networks underlying the Ouroboros prototype is
+the result of a long process of gradual increases in my understanding
+of the core principles that underly computer networks, starting from
+my work on traffic engineering packet-over-optical networks using
+Generalized Multi-Protocol Label Switching (G/MPLS) and Path
+Computation Element (PCE), then Software Defined Networks (SDN), the
+work with Sander investigating the Recursive InterNetwork Architecture
+(RINA) and finally our implementation of what would become the
+Ouroboros Prototype. The way it is presented here is not a reflection
+of this long process, but a crystalization of my current understanding
+of the Ouroboros model.
+
+During most of my PhD work at the engineering department, I spent my
+research time on modeling telecommunications networks and computer
+networks as _graphs_. The nodes represented some switch or router --
+either physical or virtual --, the links represented a cable or wire
+-- again either physical or virtual -- and then the behaviour of
+various technologies were simulated on those graphs to develop
+algorithms that analyze some behaviour or optimize some or other _key
+performance indicator_ (KPI). This line of reasoning, starting from
+_networked devices_ is how a lot of research on computer networks is
+conducted. But what happens if we turn this upside down, and develop a
+_universal_ model for computer networks starting from some very basic
+elements?
+
+### Two defining elements
+
+The Ouroboros model postulates that there are only 2 possible methods
+of distributing packets in a network layer: _FORWARDING_ packets based
+on some label identifying a node[^1], or _FLOODING_ packets on all
+links but the incoming link.
+
+We call an element that forwards a __forwarding element__,
+implementing a _packet forwarding function_ (PFF). The PFF has as
+input a destination label (in graph theory, a _vertex_), and as output
+a set of output links (in graph theory, _arcs_) on which the incoming
+packet with that label is to be forwarded on. The destination label
+needs to be in a packet header.
+
+We call an element that floods a __flooding element__, and it
+implements a packet flooding fuction. It is completely stateless, and
+has a input the incoming arc, and as output all non-incoming
+arcs. This is all local information, so packets on a broadcast layer
+do not need a header at all.
+
+Peering relationships are only allowed between forwarding elements, or
+between flooding elements, but never between a forwarding element and
+a flooding element. We call a connected graph consisting of nodes that
+hold forwarding elements a __unicast layer__, and similary we call a
+connected _tree_[^2] consisting of nodes that house a flooding element
+a __broadcast layer__.
+
+The objective for the Ouroboros model is to hold for _all_ packet
+networks; our __conjecture__ is that __all functioning packet-switched
+network technologies can be decomposed into finite sets of unicast and
+broadcast layers__. Unicast and broadcast layers can be easily found
+in TCP/IP, Recursive InterNetworking Architecture (RINA), Delay
+Tolerant Networks (DTN), Ethernet, VLANs, Loc/Id split (LISP),...
+[^3]. The Ouroboros _model_ by itself is not recursive. What is known
+as _recursive networking_ is a choice to use a single standard API to
+interact with all unicast layers and a single standard API to interact
+with all broadcast layers[^4].
+
+### The unicast layer
+
+A unicast is a collection of interconnected forwarding elements. A
+unicast layer provides a best-effort unicast packet service between
+two endpoints in the layer. We call the abstraction of this
+point-to-point unicast service a flow. A flow in itself has no
+guarantees in terms of reliability [^5].
+
+{{<figure width="70%" src="/docs/concepts/unicast_layer.png">}}
+
+A representation of a unicast layer is drawn above, with a flow
+between the _green_ (bottom left) and _red_ (top right) forwarding
+elements.
+
+The forwarding function operates in such a way that, given the label
+of the destination node (in the case of the figure, a _red_ label),
+the packet will move to the destination node (_red_) in a _deliberate_
+manner. The paper has a precise mathematical definition, but
+qualitatively, our definition of _FORWARDING_ ensures that the
+trajectory that packets follow through a network layer between source
+and destination
+
+* doesn't need to use the 'shortest' path
+* can use multiple paths
+* can use different paths for different packets
+* can involve packet duplication
+* will not have loops[^6] [^7]
+
+### The broadcast layer
+
+A broadcast layer is a collection of interconnected flooding
+elements. The nodes can have either, both or neither of the sender and
+receiver role. A broadcast layer provides a best-effort broadcast
+packet service from sender nodes to all (receiver) nodes in the layer.
+
+{{<figure width="70%" src="/docs/concepts/broadcast_layer.png">}}
+
+Our simple definition of _FLOODING_ -- given a set of adjacent links,
+send packets received on a link in the set on all other links in the
+set -- has a huge implication the properties of a fundamental
+broadcast layer: the graph always is a _tree_, or packets could travel
+along infinite trajectories with loops [^8].
+
+### Building layers
+
+We now define the fundamental operations on packet network
+layers. These operations can be implemented through manual
+configuration or automated protocol interactions. They can be skipped
+(no-operation, (nop)) or involve complex operations such as
+authentication.
+
+The construction of (unicast and broadcast) layers involves 2
+fundamental operations: adding a node to a layer is called
+_enrollment_. Enrollment prepares a node to act as a functioning
+element of the layer, exchanging the key parameters for a layer. It
+can involve authentication, and setting roles and permissions. After
+enrollment, we may add peering relationships by creating adjacencies
+between forwarding elements in a unicast layer or between flooding
+elements in a broadcast layer. We termed this _adjacency
+management_. The inverse operations are called _unenrollment_ and
+_tearing down_ adjacencies between elements.
+
+Operations such as merging and splitting layers can be decomposed into
+these two operations. This doesn't mean that merge operations
+shouldn't be researched. To the contrary, optimizing this is
+instrumental for creating networks practical on a global scale.
+
+It is immediately clear that these operations are very broadly
+defined, and can be implemented in a myriad of ways. The main
+objective of these definitions - and the Ouroboros model as a whole --
+is to separate __mechanism__ (the _what_) from __policy__ (the _how_)
+so that we have a _consistent_ framework for _reasoning_ about
+protocols and functionality in computer networks.
+
+### Under construction ...
+
+
+[^1]: This identifier can be thought of as an address, the identified
+      node is a _forwarding element_.
+
+[^2]: A tree is a connected graph with N vertices and N-1 edges.
+
+[^3]: I've already explored how some technologies map to the Ouroboros
+      model in my blog post on
+      [unicast vs multicast](/blog/2021/04/02/how-does-ouroboros-do-anycast-and-multicast/).
+
+[^4]: Of course, once the model is properly understood and a
+      green-field scenario is considered, recursive networking is the
+      obvious choice, and so the Ouroboros prototype _is_ a recursive
+      network.
+
+[^5]: This is where Ouroboros is similar to IP, and differs from RINA.
+      RINA layers (DIFs) aim to provide reliability as part of the
+      service (flow). We found this approach in RINA to be severely
+      flawed, preventing RINA to be a _universal_ model for all
+      networking and IPC. RINA can be modeled as an Ouroboros network,
+      but Ouroboros cannot be modeled as a RINA network. I've written
+      about this in more detail about this in my blog post on
+      [Ouroboros vs RINA](/blog/2021/03/20/how-does-ouroboros-relate-to-rina-the-recursive-internetwork-architecture/).
+
+[^6]: Transient loops are loops that occur due to forwarding functions
+      momentarily having different views of the network graph, for
+      instance due to delays in disseminating information on
+      unavailable links.
+
+[^7]: Some may think that it's possible to build a network layer that
+      forwards packets in a way that _deliberately_ takes a couple of
+      loops between a set of nodes and then continues forwarding to
+      the destination, violating the definition of _FORWARDING_. It's
+      not possible, because based on the destination address alone,
+      there is no way to know whether that packet came from the loop
+      or not. _"But if I add a token/identifier/cookie to the packet
+      header"_ -- yes, that is possible, and it may _look like that
+      packet is traversing a loop_ in the network, but it doesn't
+      violate the definition. The question is: what is that
+      token/identifier/cookie naming? It can be only one of a couple
+      of things: a node, a link or a layer. Adding a token and the
+      associated logic to process it, will be equivalent to adding
+      nodes to the layer (modifying the node name space to include
+      that token) or adding another layer. In essence, the
+      implementation of the nodes on the loop will be doing something
+      like this:
+
+      ```
+      if logic_based_on_token:
+          # behave like node (token, X)
+      else if logic_based_on_token:
+          # behave like node (token, Y)
+      else  # and so on
+      ```
+
+      When taking the transformation into account the resulting
+      layer(s) will follow the fundamental model as it is presented
+      above. Also observe that adding such tokens exponentially
+      increases the address space in the fundemental representation,
+      ensuring that such approaches inherently can't scale.
+
+[^8]: Some may think that it's possible to broadcast on a non-tree
+      graph by pruning in some way, shape or form. There are two
+      things to consider. First, if the pruning is done to eliminate
+      links in the graph, let's say in a way that STP prunes links on
+      an Ethernet or VLAN, then this is operation is equivalent
+      creating a new broadcast layer. We call this enrollment and
+      adjacency management. This will be explained in the next
+      sections. Second is adding the name of the (source) node plus a
+      token/identifier/cookie as a packet header in order to detect
+      packets that have traveled in a loop, and dropping them when
+      they do. This is pulling the wool over ones eyes in a similar
+      way as in [^6]. This solution can be transformed into a
+      fundamental broadcast layer by again considering the (token,
+      node name) space as the new name space and redrawing the graph,
+      in which the "cut off loops" will be arms in the tree. In the
+      same way as for unicast layers with loops, this will be an
+      exponential increase in the number of nodes in the representing
+      broadcast tree when compared to the starting graph, indicating
+      again that this kind of solution can not scale.