Definitions: Difference between revisions
| (15 intermediate revisions by the same user not shown) | |||
| Line 39: | Line 39: | ||
A geodesic distance is in general not a metric since it doesn't always fulfill the positivity and symmetry requirements in a digraph. | A geodesic distance is in general not a metric since it doesn't always fulfill the positivity and symmetry requirements in a digraph. | ||
== Routing and | == 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 | 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'''.<ref>RFC 4632: Classless Inter-domain Routing (CIDR): The Internet Address Assignment and Aggregation Plan.</ref> 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.<ref group="note">Rekhter's Law: Addressing can follow topology or topology can follow addressing. Choose one. RFC 4984.</ref> | ||
On the other hand we have '''geographic''' or '''geometric''' routing,<ref>Kuhn, F., Wattenhofer, R., and Zollinger, A. (2003). Worst-case optimal and average-case efficient geometric ad-hoc routing.</ref> where each node is assigned a coordinate so next hops can be calculated making use of the coordinates of the direct neighbors.<ref>Geographic coordinates are a compound name, consisting of latitudes and longitudes, but there is no order implied between these two coordinate spaces. Hence the partial ordering in our definition of an address.</ref> | On the other hand we have '''geographic''' or '''geometric''' routing,<ref>Kuhn, F., Wattenhofer, R., and Zollinger, A. (2003). Worst-case optimal and average-case efficient geometric ad-hoc routing.</ref> where each node is assigned a coordinate so next hops can be calculated making use of the coordinates of the direct neighbors.<ref group="note">Geographic coordinates are a compound name, consisting of latitudes and longitudes, but there is no order implied between these two coordinate spaces. Hence the partial ordering in our definition of an address.</ref> | ||
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 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 <math>G = (V, A)</math> be a network. | Let <math>G = (V, A)</math> be a network. | ||
| Line 60: | Line 58: | ||
# <math>A' = \emptyset</math> if and only if there is no path <math>\mathcal{P}</math> between <math>v_s</math> and <math>v_d</math> in <math>G</math>. | # <math>A' = \emptyset</math> if and only if there is no path <math>\mathcal{P}</math> between <math>v_s</math> and <math>v_d</math> in <math>G</math>. | ||
Equivalently,<ref> | Equivalently,<ref group="note"> Proof of Equivalence: choose for <math>d</math> the length of the longest path between the corresponding vertices in <math>D</math>.</ref> '''ROUTING''' is any algorithm that, given source and destination '''vertices''' <math>v_s</math> and <math>v_d</math>, for each vertex <math>v</math> in <math>V</math> returns a subset <math>H(v) \subseteq N(v)</math> of neighbors so that: | ||
# <math>\forall u \in H(v): d(u, v_d) < d(v, v_d)</math> for any chosen distance function <math>d</math> on <math>G</math>; and | # <math>\forall u \in H(v): d(u, v_d) < d(v, v_d)</math> for any chosen distance function <math>d</math> on <math>G</math>; and | ||
| Line 67: | Line 65: | ||
In other words, either the distance function bounds the routing solution, or the routing solution bounds the distance function. | 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 <math>v</math> in <math>V</math> returns the set of arcs <math>L(v)</math>. '''FORWARDING''' is often implemented as '''ROUTING''' with an additional edge selection step. | We define '''FORWARDING''' as any algorithm that, for each vertex <math>v</math> in <math>V</math> returns the set of arcs <math>L(v)</math>. '''FORWARDING''' is often implemented as '''ROUTING''' with an additional edge selection step. | ||
| Line 76: | Line 76: | ||
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 <math>d</math>. This is implemented in a class of dissemination protocols, called '''link-state routing protocols'''. | 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 <math>d</math>. This is implemented in a class of dissemination protocols, called '''link-state routing protocols'''. | ||
'''FLOODING''' is any algorithm that, for each vertex <math>v</math> in <math>V</math> returns a subset <math>H(v) \subseteq N(v)</math> of neighbors (with the associated set of arcs <math>L(v)</math>) so that: | |||
# The graph <math>D = (V', A') = (\cup_{v \in V}H(v), \cup_{v \in V}L(v))</math> is a connected subgraph of <math>G</math>; and | |||
# <math>v_s</math> is the only vertex in <math>D</math> with only outgoing arcs. | |||
Equivalently, '''FLOODING''' is any algorithm that, for each vertex <math>v</math> in <math>V</math> returns a subset <math>H(v) \subseteq N(v)</math> of neighbors so that: | |||
# <math>\forall u \in H(v): d(v_s, u) > d(v_s, v)</math> for any chosen distance function <math>d</math> on <math>G</math>. | |||
In other words, '''FLOODING''' creates a connected tree rooted at <math>v_s</math> 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 == | == Flow == | ||
| Line 99: | Line 110: | ||
* The '''Maximum Packet Size''' (MPS) is the maximum length for a packet to be acceptable for transfer | * 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 0,<ref>This may be hard to guarantee with 100 percent certainty, so MPL should be large enough so that this probability is 0 in practice. IP has a bound on the Maximum Datagram Lifetime (MDL) via the Time-To-Live or Hop Limit decrement in each router to a maximum of 255 seconds (RFC 791), with a recommended value of 64 seconds (RFC 1700). In addition, TCP defines the Maximum Segment Lifetime (MSL) as 120s (RFC 793).</ref> and the probability for a packet to arrive that exceeds the MPS is equal to 0. | In other words, the probability for a packet to arrive after MPL expires should be close to 0,<ref group="note">This may be hard to guarantee with 100 percent certainty, so MPL should be large enough so that this probability is 0 in practice. Ouroboros estimates MPL based on the Layer characteristics. IP has a bound on the Maximum Datagram Lifetime (MDL) via the Time-To-Live (v4) or Hop Limit (v6) decrement in each router to a maximum of 255 seconds (RFC 791), with a recommended value of 64 seconds (RFC 1700). In addition, TCP defines the Maximum Segment Lifetime (MSL) as 120s (RFC 793).</ref> 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). | Similarly, there can be lower bounds such as Minimum Packet Lifetime (mPL) and Minimum Packet Size (mPS). | ||
| Line 111: | Line 122: | ||
=== Flow Identifiers === | === Flow Identifiers === | ||
A flow endpoint is identified in a system by a '''flow ID''' (FID), which defines the '''layer boundary'''<ref>In this respect, a flow id is similar to an OSI '''Service Access Point''' (SAP) or RINA '''port id'''.</ref>. 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<ref>This is similar in function to a UNIX file descriptor | A flow endpoint is identified in a system by a '''flow ID''' (FID), which defines the '''layer boundary'''<ref group="note">In this respect, a flow id is similar to an OSI '''Service Access Point''' (SAP) or RINA '''port id'''.</ref>. 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<ref group="note">This is similar in function to a UNIX file descriptor.</ref>. | ||
Flows are an important concept for enabling Quality-of-Service (QoS) in a layer. | Flows are an important concept for enabling Quality-of-Service (QoS) in a layer. | ||
Latest revision as of 12:07, 4 January 2026
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[1].
Basic Graph Definitions
A graph is a pair consisting of a set of vertices and a set of edges of two-element subsets of . An edge has (distinct) end vertices and .
A directed graph or digraph is a pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V, A)} consisting of a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} of vertices and a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} of ordered pairs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (v_i, v_j)} (called arcs) where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i \neq v_j} .
A network is a digraph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,A)} on which a mapping Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w: A \to \mathbb{R}} from the edgeset to the reals is defined; the number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(a)} is called the weight of the arc Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} [note 1].
If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = (v_i,v_j) \in A} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} is adjacent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_j} and incident with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} . The set of neighbors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} of a vertex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} is the set of vertices that are adjacent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N(v)} contains all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u \in V} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (v, u) \in A} .
Walks, Paths, and Cycles
A walk is a sequence of vertices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{W} = (v_0, v_1, \dots , v_n)} so that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{W}} as the sum of the weights of its arcs, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(\mathcal{W}) = \sum_{i=1}^n w(a_i)} .
If the source Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_0} and destination Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_n} are the same (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_0 = v_n} ), the walk is closed.
A walk where each of the arcs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i} is distinct is called a trail.
A path is a trail for which each of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} are distinct.
A closed trail for which the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} are distinct is called a cycle[note 2].
A directed acyclic graph (DAG) is a digraph that does not contain any cycles.
If for every pair of vertices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_s, v_d \in V} there is at least one path , 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \infty} if no such path exists) is called the geodesic distance.
A metric is a (distance) function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d: X^2 \to [0, +\infty)} fulfilling positivity, symmetry and triangle inequality:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.[2] 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.[note 3]
On the other hand we have geographic or geometric routing,[3] where each node is assigned a coordinate so next hops can be calculated making use of the coordinates of the direct neighbors.[note 4]
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V, A)} be a network.
ROUTING is any algorithm that, given source and destination vertices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_s} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_d} , for each vertex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} returns a subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(v) \subseteq N(v)} of neighbors with the associated set of arcs , so that the following 4 conditions are met:
- The graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = (V', A') = (\cup_{v \in V}H(v), \cup_{v \in V}L(v))} is a directed acyclic subgraph of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} ;
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_s} is the only vertex in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} with only outgoing arcs;
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_d} is the only vertex in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} with only incoming arcs; and
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A' = \emptyset} if and only if there is no path Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}} between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_s} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_d} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} .
Equivalently,[note 5] ROUTING is any algorithm that, given source and destination vertices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_s} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_d} , for each vertex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} returns a subset of neighbors so that:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall u \in H(v): d(u, v_d) < d(v, v_d)} for any chosen distance function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} ; and
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cup_{v \in V} H(v) = \emptyset} if and only if there is no path Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}} between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_s} and in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} returns the set of arcs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V, A)} and a valid geodesic distance Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} . For a given vertex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} , the necessary and sufficient set of information to obtain Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(v)} is knowledge of its neighbor set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N(v)} and the subset of the geodesic distances originating at its neighbors, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} . This is implemented in a class of dissemination protocols, called link-state routing protocols.
FLOODING is any algorithm that, for each vertex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} returns a subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(v) \subseteq N(v)} of neighbors (with the associated set of arcs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(v)} ) so that:
- The graph is a connected subgraph of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} ; and
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_s} is the only vertex in with only outgoing arcs.
Equivalently, FLOODING is any algorithm that, for each vertex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} returns a subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(v) \subseteq N(v)} of neighbors so that:
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall u \in H(v): d(v_s, u) > d(v_s, v)} for any chosen distance function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} .
In other words, FLOODING creates a connected tree rooted at 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(S,t, \ldots) \in [0, 1]} of a packet of given size being transferred within a certain period of time . The maximum probability for error-free transfer depends on the packet-drop-rate (PDR) and bit-error-rate (BER) of the flow.
![{\displaystyle [t_{x},t_{x}+t]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56c17030ff15c90d9d5c36f35368314fb0471bfd)
The Ouroboros architecture ensures that flows are content neutral, i.e. the probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.[4] 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,[note 6] 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[note 7]. 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[note 8].
Flows are an important concept for enabling Quality-of-Service (QoS) in a layer.
Footnotes
- ↑ The weight of an edge is often called a metric in computer science literature (e.g. BGP metric). To avoid confusion, we use the term metric only in its mathematical meaning.
- ↑ A Hamiltonian cycle is a special case of a closed walk that includes every vertex in the graph exactly once. This is necessarily also a closed trail.
- ↑ Rekhter's Law: Addressing can follow topology or topology can follow addressing. Choose one. RFC 4984.
- ↑ Geographic coordinates are a compound name, consisting of latitudes and longitudes, but there is no order implied between these two coordinate spaces. Hence the partial ordering in our definition of an address.
- ↑ Proof of Equivalence: choose for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} the length of the longest path between the corresponding vertices in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} .
- ↑ This may be hard to guarantee with 100 percent certainty, so MPL should be large enough so that this probability is 0 in practice. Ouroboros estimates MPL based on the Layer characteristics. IP has a bound on the Maximum Datagram Lifetime (MDL) via the Time-To-Live (v4) or Hop Limit (v6) decrement in each router to a maximum of 255 seconds (RFC 791), with a recommended value of 64 seconds (RFC 1700). In addition, TCP defines the Maximum Segment Lifetime (MSL) as 120s (RFC 793).
- ↑ In this respect, a flow id is similar to an OSI Service Access Point (SAP) or RINA port id.
- ↑ This is similar in function to a UNIX file descriptor.
References
- ↑ Jungnickel, D. (2007). Graphs, Networks and Algorithms.
- ↑ RFC 4632: Classless Inter-domain Routing (CIDR): The Internet Address Assignment and Aggregation Plan.
- ↑ Kuhn, F., Wattenhofer, R., and Zollinger, A. (2003). Worst-case optimal and average-case efficient geometric ad-hoc routing.
- ↑ RFC 3393: IP Packet Delay Variation Metric for IP Performance Metrics (IPPM).