aboutsummaryrefslogtreecommitdiff
path: root/content/en
diff options
context:
space:
mode:
authorDimitri Staessens <dimitri@ouroboros.rocks>2021-04-25 13:38:59 +0200
committerDimitri Staessens <dimitri@ouroboros.rocks>2021-04-25 13:38:59 +0200
commit05d1e0e0205aeb7b9bcb17523e1cc0fc502d81ea (patch)
tree13b6290b7ad5178186370bf385ec697d571f19b1 /content/en
parent30dc3e40922463b5531204c7d20d8abd56893e71 (diff)
downloadwebsite-05d1e0e0205aeb7b9bcb17523e1cc0fc502d81ea.tar.gz
website-05d1e0e0205aeb7b9bcb17523e1cc0fc502d81ea.zip
content: Add initial page on Ouroboros model
Diffstat (limited to 'content/en')
-rw-r--r--content/en/docs/Concepts/broadcast_layer.pngbin0 -> 176866 bytes
-rw-r--r--content/en/docs/Concepts/dependencies.jpgbin12970 -> 0 bytes
-rw-r--r--content/en/docs/Concepts/elements.md90
-rw-r--r--content/en/docs/Concepts/layers.jpgbin104947 -> 0 bytes
-rw-r--r--content/en/docs/Concepts/model_elements.pngbin0 -> 27515 bytes
-rw-r--r--content/en/docs/Concepts/ouroboros-model.md235
-rw-r--r--content/en/docs/Concepts/rec_netw.jpgbin63370 -> 0 bytes
-rw-r--r--content/en/docs/Concepts/unicast_layer.pngbin0 -> 206355 bytes
-rw-r--r--content/en/docs/Concepts/what.md78
9 files changed, 235 insertions, 168 deletions
diff --git a/content/en/docs/Concepts/broadcast_layer.png b/content/en/docs/Concepts/broadcast_layer.png
new file mode 100644
index 0000000..01079c0
--- /dev/null
+++ b/content/en/docs/Concepts/broadcast_layer.png
Binary files differ
diff --git a/content/en/docs/Concepts/dependencies.jpg b/content/en/docs/Concepts/dependencies.jpg
deleted file mode 100644
index eaa9e79..0000000
--- a/content/en/docs/Concepts/dependencies.jpg
+++ /dev/null
Binary files differ
diff --git a/content/en/docs/Concepts/elements.md b/content/en/docs/Concepts/elements.md
deleted file mode 100644
index a803065..0000000
--- a/content/en/docs/Concepts/elements.md
+++ /dev/null
@@ -1,90 +0,0 @@
----
-title: "Elements of a recursive network"
-author: "Dimitri Staessens"
-date: 2019-07-11
-weight: 2
-description: >
- The building blocks for recursive networks.
----
-
-This section describes the high-level concepts and building blocks are
-used to construct a decentralized [recursive network](/docs/what):
-layers and flows. (Ouroboros has two different kinds of layers, but
-we will dig into all the fine details in later posts).
-
-A __layer__ in a recursive network embodies all of the functionalities
-that are currently in layers 3 and 4 of the OSI model (along with some
-other functions). The difference is subtle and takes a while to get
-used to (not unlike the differences in the term *variable* in
-imperative versus functional programming languages). A recursive
-network layer handles requests for communication to some remote
-process and, as a result, it either provides a handle to a
-communication channel -- a __flow__ endpoint --, or it raises some
-error that no such flow could be provided.
-
-A layer in Ouroboros is built up from a bunch of (identical) programs
-that work together, called Inter-Process Communication (IPC) Processes
-(__IPCPs__). The name "IPCP" was first coined for a component of the
-[LINCS]
-(https://www.osti.gov/biblio/5542785-delta-protocol-specification-working-draft)
-hierarchical network architecture built at Lawrence Livermore National
-Laboratories and was taken over in the RINA architecture. These IPCPs
-implement the core functionalities (such as routing, a dictionary) and
-can be seen as small virtual routers for the recursive network.
-
-{{<figure width="60%" src="/docs/concepts/rec_netw.jpg">}}
-
-In the illustration, a small 5-node recursive network is shown. It
-consists of two hosts that connect via edge routers to a small core.
-There are 6 layers in this network, labelled __A__ to __F__.
-
-On the right-hand end-host, a server program __Y__ is running (think a
-mail server program), and the (mail) client __X__ establishes a flow
-to __Y__ over layer __F__ (only the endpoints are drawn to avoid
-cluttering the image).
-
-Now, how does the layer __F__ get the messages from __X__ to __Y__?
-There are 4 IPCPs (__F1__ to __F4__) in layer __F__, that work
-together to provide the flow between the applications __X__ and
-__Y__. And how does __F3__ get the info to __F4__? That is where the
-recursion comes in. A layer at some level (its __rank__), will use
-flows from another layer at a lower level. The rank of a layer is a
-local value. In the hosts, layer __F__ is at rank 1, just above layer
-__C__ or layer __E_. In the edge router, layer __F__ is at rank 2,
-because there is also layer __D__ in that router. So the flow between
-__X__ and __Y__ is supported by flows in layer __C__, __D__ and __E__,
-and the flows in layer __D__ are supported by flows in layers __A__
-and __B__.
-
-Of course these dependencies can't go on forever. At the lowest level,
-layers __A__, __B__, __C__ and __E__ don't depend on a lower layer
-anymore, and are sometimes called 0-layers. They only implement the
-functions to provide flows, but internally, they are specifically
-tailored to a transmission technology or a legacy network
-technology. Ouroboros supports such layers over (local) shared memory,
-over the User Datagram Protocol, over Ethernet and a prototype that
-supports flows over an Ethernet FPGA device. This allows Ouroboros to
-integrate with existing networks at OSI layers 4, 2 and 1.
-
-If we then complete the picture above, when __X__ sends a packet to
-__Y__, it passes it to __F3__, which uses a flow to __F1__ that is
-implemented as a direct flow between __C2__ and __C1__. __F1__ then
-forwards the packet to __F2__ over a flow that is supported by layer
-__D__. This flow is implemented by two flows, one from __D2__ to
-__D1__, which is supported by layer A, and one from __D1__ to __D3__,
-which is supported by layer __B__. __F2__ will forward the packet to
-__F4__, using a flow provided by layer __E__, and __F4__ then delivers
-the packet to __Y__. So the packet moves along the following chain of
-IPCPs: __F3__ --> __C2__ --> __C1__ --> __F1__ --> __D2__ --> __A1__
---> __A2__ --> __D1__ --> __B1__ --> __B2__ --> __D3__ --> __F2__ -->
-__E1__ --> __E2__ --> __F4__.
-
-{{<figure width="40%" src="/docs/concepts/dependencies.jpg">}}
-
-A recursive network has __dependencies__ between layers in the
-network, and between IPCPs in a __system__. These dependencies can be
-represented as a directed acyclic graph (DAG). To avoid problems,
-these dependencies should never contain cycles (so a layer I should
-not directly or indirectly depend on itself). The rank of a layer is
-defined (either locally or globally) as the maximum depth of this
-layer in the DAG.
diff --git a/content/en/docs/Concepts/layers.jpg b/content/en/docs/Concepts/layers.jpg
deleted file mode 100644
index 5d3020c..0000000
--- a/content/en/docs/Concepts/layers.jpg
+++ /dev/null
Binary files differ
diff --git a/content/en/docs/Concepts/model_elements.png b/content/en/docs/Concepts/model_elements.png
new file mode 100644
index 0000000..bffbca8
--- /dev/null
+++ b/content/en/docs/Concepts/model_elements.png
Binary files differ
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.
diff --git a/content/en/docs/Concepts/rec_netw.jpg b/content/en/docs/Concepts/rec_netw.jpg
deleted file mode 100644
index bddaca5..0000000
--- a/content/en/docs/Concepts/rec_netw.jpg
+++ /dev/null
Binary files differ
diff --git a/content/en/docs/Concepts/unicast_layer.png b/content/en/docs/Concepts/unicast_layer.png
new file mode 100644
index 0000000..c77ce48
--- /dev/null
+++ b/content/en/docs/Concepts/unicast_layer.png
Binary files differ
diff --git a/content/en/docs/Concepts/what.md b/content/en/docs/Concepts/what.md
deleted file mode 100644
index ac87754..0000000
--- a/content/en/docs/Concepts/what.md
+++ /dev/null
@@ -1,78 +0,0 @@
----
-title: "Recursive networks"
-author: "Dimitri Staessens"
-
-date: 2020-01-11
-weight: 2
-description: >
- The recursive network paradigm
----
-
-The functional repetition in the network stack is discussed in
-detail in the book __*"Patterns in Network Architecture: A Return to
-Fundamentals"*__. From the observations in the book, a new architecture
-was proposed, called the "__R__ecursive __I__nter__N__etwork
-__A__rchitecture", or [__RINA__](http://www.pouzinsociety.org).
-
-__Ouroboros__ follows the recursive principles of RINA, but deviates
-quite a bit from its internal design. There are resources on the
-Internet explaining RINA, but here we will focus
-on its high level design and what is relevant for Ouroboros.
-
-Let's look at a simple scenario of an employee contacting an internet
-corporate server over a Layer 3 VPN from home. Let's assume for
-simplicity that the corporate LAN is not behind a NAT firewall. All
-three networks perform (among some other things):
-
-__Addressing__: The VPN hosts receive an IP address in the VPN, let's
-say some 10.11.12.0/24 address. The host will also have a public IP
-address, for instance in the 20.128.0.0/16 range . Finally that host
-will have an Ethernet MAC address. Now the addresses __differ in
-syntax and semantics__, but for the purpose of moving data packets,
-they have the same function: __identifying a node in a network__.
-
-__Forwarding__: Forwarding is the process of moving packets to a
-destination __with intent__: each forwarding action moves the data
-packet __closer__ to its destination node with respect to some
-__metric__ (distance function).
-
-__Network discovery__: Ethernet switches learn where the endpoints are
-through MAC learning, remembering the incoming interface when it sees
-a new soure address; IP routers learn the network by exchanging
-informational packets about adjacency in a process called *routing*;
-and a VPN proxy server relays packets as the central hub of a network
-connected as a star between the VPN clients and the local area
-network (LAN) that is provides access to.
-
-__Congestion management__: When there is a prolonged period where a
-node receives more traffic than can forward forward, for instance
-because there are incoming links with higher speeds than some outgoing
-link, or there is a lot of traffic between different endpoints towards
-the same destination, the endpoints experience congestion. Each
-network could handle this situation (but not all do: TCP does
-congestion control for IP networks, but Ethernet just drops traffic
-and lets the IP network deal with it. Congestion management for
-Ethernet never really took off).
-
-__Name resolution__: In order not having to remember addresses of the
-hosts (which are in a format that make it easier for a machine to deal
-with), each network keeps a mapping of a name to an address. For IP
-networks (which includes the VPN in our example), this is done by the
-Domain Name System (DNS) service (or, alternatively, other services
-such as *open root* or *namecoin*). For Ethernet, the Address
-Resolution Protocol maps a higher layer name to a MAC (hardware)
-address.
-
-{{<figure width="50%" src="/docs/concepts/layers.jpg">}}
-
-Recursive networks take all these functions to be part of a network
-layer, and layers are mostly defined by their __scope__. The lowest
-layers span a link or the reach of some wireless technology. Higher
-layers span a LAN or the network of a corporation e.g. a subnetwork or
-an Autonomous System (AS). An even higher layer would be a global
-network, followed by a Virtual Private Network and on top a tunnel
-that supports the application. Each layer being the same in terms of
-functionality, but different in its choice of algorithm or
-implementation. Sometimes the function is just not implemented
-(there's no need for routing in a tunnel!), but logically it could be
-there.