Definitions

Definitions: Flow, Routing, and Forwarding

This document contains formal definitions used in the Ouroboros architecture. The graph definitions follow Dieter Jungnickel's excellent Graph, Networks and Algorithms.

Basic Graph Definitions

A graph is a pair $G=(V,E)$ consisting of a set of vertices $V$ and a set of edges $E\subset V^{2}$ of two-element subsets of $V$. An edge $e=(v_{i},v_{j})$ has (distinct) end vertices $v_{i}$ and $v_{j}$.

A directed graph or digraph is a pair $G=(V,A)$ consisting of a set $V$ of vertices and a set $A$ of ordered pairs $(v_{i},v_{j})$ (called arcs) where $v_{i}\neq v_{j}$.

A network is a digraph $G=(V,A)$ on which a mapping $w:A\to \mathbb {R}$ from the edgeset to the reals is defined; the number $w(a)$ is called the weight of the arc $a$.

If $a=(v_{i},v_{j})\in A$, then $v_{i}$ is adjacent to $v_{j}$ and incident with $a$. The set of neighbors $N$ of a vertex $v$ is the set of vertices that are adjacent to $v$, where $N(v)$ contains all $u\in V$ such that $(v,u)\in A$.

Walks, Paths, and Cycles

A walk is a sequence of vertices ${\mathcal {W}}=(v_{0},v_{1},\dots ,v_{n})$ so that $a_{i}=(v_{i-1},v_{i})\in A,i=1,\dots ,n$. So each walk also implies a sequence of edges. We define the weight of a walk ${\mathcal {W}}$ as the sum of the weights of its arcs, $w({\mathcal {W}})=\sum _{i=1}^{n}w(a_{i})$.

If the source $v_{0}$ and destination $v_{n}$ are the same ($v_{0}=v_{n}$), the walk is closed.

A walk where each of the arcs $a_{i}$ is distinct is called a trail.

A path is a trail for which each of the $v_{i}$ are distinct.

A closed trail for which the $v_{i}$ are distinct is called a cycle.

A directed acyclic graph (DAG) is a digraph that does not contain any cycles.

If for every pair of vertices $v_{s},v_{d}\in V$ there is at least one path ${\mathcal {P}}=(v_{s},\dots ,v_{d})$, we call the (di)graph connected.

Distance and Metrics

The distance function defined by the weight of the shortest path between two vertices in a network (or $\infty$ if no such path exists) is called the geodesic distance.

A metric is a (distance) function $d:X^{2}\to [0,+\infty )$ fulfilling positivity, symmetry and triangle inequality:

$\forall x,y,z\in X:d(x,y)\geq 0\land d(x,y)=d(y,x)\land d(x,z)\leq d(x,y)+d(y,z)$

A geodesic distance is in general not a metric since it doesn't always fulfill the positivity and symmetry requirements in a digraph.

Routing, Forwarding and Flooding

With routing we typically mean the process of selecting a path for traffic in a network. In computer science literature, there are two main groups of approaches to routing.

On the one hand there are the hierarchical routing solutions. This is the approach taken in IP networks, where a set of subnetworks is defined using prefixes or subnet masks. A scalability issue with IP stems from not following the partial ordering implied by the subnetting in the delegation of IP addresses, causing fragmentation of the IP address space and making prefix aggregration in routers increasingly inefficient.

On the other hand we have geographic or geometric routing, where each node is assigned a coordinate so next hops can be calculated making use of the coordinates of the direct neighbors.

The examples above illustrate that the concept of routing encompasses both the dissemination and gathering of information about the network, and the algorithms for calculation and selection of the paths. We will now define the concepts underpinning "routing" more formally. The reasoning behind it is similar to the reasoning commonly used in formulating (integer) linear programming solutions to problems in graph theory.

Let $G=(V,A)$ be a network.

ROUTING is any algorithm that, given source and destination vertices $v_{s}$ and $v_{d}$, for each vertex $v$ in $V$ returns a subset $H(v)\subseteq N(v)$ of neighbors with the associated set of arcs $L(v)$, so that the following 4 conditions are met:

1. The graph $D=(V',A')=(\cup _{v\in V}H(v),\cup _{v\in V}L(v))$ is a directed acyclic subgraph of $G$;
2. $v_{s}$ is the only vertex in $D$ with only outgoing arcs;
3. $v_{d}$ is the only vertex in $D$ with only incoming arcs; and
4. $A'=\emptyset$ if and only if there is no path ${\mathcal {P}}$ between $v_{s}$ and $v_{d}$ in $G$.

Equivalently, ROUTING is any algorithm that, given source and destination vertices $v_{s}$ and $v_{d}$, for each vertex $v$ in $V$ returns a subset $H(v)\subseteq N(v)$ of neighbors so that:

1. $\forall u\in H(v):d(u,v_{d})<d(v,v_{d})$ for any chosen distance function $d$ on $G$; and
2. $\cup _{v\in V}H(v)=\emptyset$ if and only if there is no path ${\mathcal {P}}$ between $v_{s}$ and $v_{d}$ in $G$.

In other words, either the distance function bounds the routing solution, or the routing solution bounds the distance function.

The formal definition says that a routing algorithm is equivalent a tree-like structure where every node along any valid path selects one or more neighbors that are strictly "closer" to the destination than itself. This structure can contain multiple paths from source to destination, allowing routing solution that move different packets (or fragments) along different routes through the network. The key guarantee is that all these paths always make progress toward their destination and can not contain (permanent) loops - think of it like water flowing downhill where it may split into multiple streams, but each stream always flows to a lower elevation and can never flow back uphill.

This definition is very broad "one or more neighbors" selection allows solutions that send duplicates, erasure coding packet fragments etc.

We define FORWARDING as any algorithm that, for each vertex $v$ in $V$ returns the set of arcs $L(v)$. FORWARDING is often implemented as ROUTING with an additional edge selection step.

The necessary and sufficient condition for ROUTING is full knowledge of the graph $G=(V,A)$ and a valid geodesic distance $d$. For a given vertex $v$, the necessary and sufficient set of information to obtain $L(v)$ is knowledge of its neighbor set $N(v)$ and the subset of the geodesic distances originating at its neighbors, $d_{v}\subset d:N(v)\times V\to \mathbb {R}$.

In less formal terms, ROUTING and FORWARDING provide a set of vertices and arcs, respectively, so that there are never loops if one travels to a next vertex or along an arc in the set. If implemented in a centralized way, ROUTING and FORWARDING roughly need to know the full network. When implemented in a distributed way, a node roughly needs to know its neighbors and the distances to the destination from itself and from all its neighbors.

The definitions above show what information needs to be disseminated in a network to allow FORWARDING. Let's assume that vertices know their neighbors or incident outgoing arcs, then what is needed is a dissemination procedure for the (geodesic) distance function $d$. This is implemented in a class of dissemination protocols, called link-state routing protocols.

FLOODING is any algorithm that, for each vertex $v$ in $V$ returns a subset $H(v)\subseteq N(v)$ of neighbors (with the associated set of arcs $L(v)$) so that:

1. The graph $D=(V',A')=(\cup _{v\in V}H(v),\cup _{v\in V}L(v))$ is a connected subgraph of $G$; and
2. $v_{s}$ is the only vertex in $D$ with only outgoing arcs.

Equivalently, FLOODING is any algorithm that, for each vertex $v$ in $V$ returns a subset $H(v)\subseteq N(v)$ of neighbors so that:

1. $\forall u\in H(v):d(v_{s},u)>d(v_{s},v)$ for any chosen distance function $d$ on $G$.

In other words, FLOODING creates a connected tree rooted at $v_{s}$ that reaches all (reachable) vertices in the network. Each vertex selects neighbors that are strictly farther from the source than itself, ensuring the flood propagates outward without backtracking.

Flow

A flow is the abstraction of a collection of resources within a network layer that allow bidirectional communications using packets between two processes that are clients of this layer. A flow enables a point-to-point packet delivery service and can be viewed as a bidirectional pipe that has a number of observable quantities associated with it that describe the probability $p(S,t,\ldots )\in [0,1]$ of a packet of given size $S$ being transferred within a certain period of time $[t_{x},t_{x}+t]$. The maximum probability for error-free transfer depends on the packet-drop-rate (PDR) and bit-error-rate (BER) of the flow.

The Ouroboros architecture ensures that flows are content neutral, i.e. the probability $p(S,t,\ldots )$ above is independent of the bits that make up the packets sent along a flow.

Flow Characteristics

The delay or latency describes how long packets take to traverse the flow, and the variation on the delay is called jitter, or more precisely, packet delay variation. The delay for a flow has four main components:

• Propagation delay
• Queuing delay
• Transmission delay
• Processing delay

Flow Bounds

There are 2 upper bounds:

• The Maximum Packet Lifetime (MPL) is the maximum amount of time that a packet can take to transfer over the flow
• The Maximum Packet Size (MPS) is the maximum length for a packet to be acceptable for transfer

In other words, the probability for a packet to arrive after MPL expires should be close to 0, and the probability for a packet to arrive that exceeds the MPS is equal to 0.

Similarly, there can be lower bounds such as Minimum Packet Lifetime (mPL) and Minimum Packet Size (mPS).

Flow Resources

The resources that make up a layer are finite, limiting the total number of packets that can traverse the network layer in a given period of time. Flows provide the mechanism to put a network layer fully in control of its own resources. The resources that constitute the flow can either be shared with other flows or dedicated (reserved) for this particular flow.

Other externally measureable quantities can be associated with a flow, such as bandwidth and load for flows with reserved resources. The probability function may depend on these quantities (e.g. if the load reaches a certain threshold, delay could increase).

Flow Identifiers

A flow endpoint is identified in a system by a flow ID (FID), which defines the layer boundary. For security reasons, a process has no direct access to the flow, but rather accesses the flow through a Flow Descriptor (FD) to read and write from a flow. Flow identifiers are unique within the scope of a system, flow descriptors are unique within the scope of a process.

Flows are an important concept for enabling Quality-of-Service (QoS) in a layer.