From 05d1e0e0205aeb7b9bcb17523e1cc0fc502d81ea Mon Sep 17 00:00:00 2001 From: Dimitri Staessens Date: Sun, 25 Apr 2021 13:38:59 +0200 Subject: content: Add initial page on Ouroboros model --- content/en/docs/Concepts/broadcast_layer.png | Bin 0 -> 176866 bytes content/en/docs/Concepts/dependencies.jpg | Bin 12970 -> 0 bytes content/en/docs/Concepts/elements.md | 90 ---------- content/en/docs/Concepts/layers.jpg | Bin 104947 -> 0 bytes content/en/docs/Concepts/model_elements.png | Bin 0 -> 27515 bytes content/en/docs/Concepts/ouroboros-model.md | 235 +++++++++++++++++++++++++++ content/en/docs/Concepts/rec_netw.jpg | Bin 63370 -> 0 bytes content/en/docs/Concepts/unicast_layer.png | Bin 0 -> 206355 bytes content/en/docs/Concepts/what.md | 78 --------- 9 files changed, 235 insertions(+), 168 deletions(-) create mode 100644 content/en/docs/Concepts/broadcast_layer.png delete mode 100644 content/en/docs/Concepts/dependencies.jpg delete mode 100644 content/en/docs/Concepts/elements.md delete mode 100644 content/en/docs/Concepts/layers.jpg create mode 100644 content/en/docs/Concepts/model_elements.png create mode 100644 content/en/docs/Concepts/ouroboros-model.md delete mode 100644 content/en/docs/Concepts/rec_netw.jpg create mode 100644 content/en/docs/Concepts/unicast_layer.png delete mode 100644 content/en/docs/Concepts/what.md 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 Binary files /dev/null and b/content/en/docs/Concepts/broadcast_layer.png differ diff --git a/content/en/docs/Concepts/dependencies.jpg b/content/en/docs/Concepts/dependencies.jpg deleted file mode 100644 index eaa9e79..0000000 Binary files a/content/en/docs/Concepts/dependencies.jpg and /dev/null 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. - -{{
}} - -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__. - -{{
}} - -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 Binary files a/content/en/docs/Concepts/layers.jpg and /dev/null 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 Binary files /dev/null and b/content/en/docs/Concepts/model_elements.png 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]. + +{{
}} + +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. + +{{
}} + +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 Binary files a/content/en/docs/Concepts/rec_netw.jpg and /dev/null 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 Binary files /dev/null and b/content/en/docs/Concepts/unicast_layer.png 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. - -{{
}} - -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. -- cgit v1.2.3