Definitions - Revision history

Dimitri: /* Routing, Forwarding and Flooding */

2026-01-04T12:07:31Z

Routing, Forwarding and Flooding

← Older revision		Revision as of 12:07, 4 January 2026
Line 58:		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 group="note"> Proof of Equivalence: choose for <math>d</math> the length of the longest path between the corresponding vertices in <math>D</math>~~. This also proves it covers ''all'' algorithms, unless you find a path longer than the longest path..~~.</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:		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

Dimitri: /* Flow Identifiers */

2026-01-04T12:05:03Z

Flow Identifiers

← Older revision		Revision as of 12:05, 4 January 2026
Line 122:		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 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>This is similar in function to a UNIX file descriptor~~. A UNIX kernel space implementation of Ouroboros would probably use file descriptors for flow descriptors~~.</ref>.		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.

Dimitri: /* Flow */

2026-01-04T12:01:30Z

Flow

← Older revision		Revision as of 12:01, 4 January 2026
Line 122:		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 UNIX kernel space implementation of Ouroboros would probably use file descriptors for flow descriptors.</ref>.		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>This is similar in function to a UNIX file descriptor. A UNIX kernel space implementation of Ouroboros would probably use file descriptors for flow descriptors.</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.

Dimitri: /* Routing, Forwarding and Flooding */

2026-01-04T11:33:16Z

Routing, Forwarding and Flooding

← Older revision		Revision as of 11:33, 4 January 2026
Line 58:		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 group="note"> Proof of Equivalence: choose for <math>d</math> the length of the longest path between the corresponding vertices in <math>D.</math>. This also proves it covers ''all'' algorithms, unless you find a path longer than the longest path...</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:		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>. This also proves it covers ''all'' algorithms, unless you find a path longer than the longest path...</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

Dimitri: /* Routing, Forwarding and Flooding */

2026-01-04T11:30:04Z

Routing, Forwarding and Flooding

← Older revision		Revision as of 11:30, 4 January 2026
Line 58:		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 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:		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>. This also proves it covers ''all'' algorithms, unless you find a path longer than the longest path...</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

Dimitri: /* Flow Bounds */

2026-01-04T11:19:59Z

Flow Bounds

← Older revision		Revision as of 11:19, 4 January 2026
Line 110:		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).

Dimitri: /* Routing, Forwarding and Flooding */

2026-01-04T11:13:10Z

Routing, Forwarding and Flooding

← Older revision		Revision as of 11:13, 4 January 2026
Line 86:		Line 86:
	# <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>.		# <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 vertices in the network. Each vertex selects neighbors that are strictly farther from the source than itself, ensuring the flood propagates outward without backtracking.		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 ==

Dimitri: /* Routing, Forwarding and Flooding */

2026-01-04T11:09:00Z

Routing, Forwarding and Flooding

← Older revision		Revision as of 11:09, 4 January 2026
Line 77:		Line 77:
	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:		'''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		# 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

Dimitri: /* Routing and Forwarding */

2026-01-04T11:07:10Z

Routing and Forwarding

← Older revision		Revision as of 11:07, 4 January 2026
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 ~~Forwarding~~ ==		== 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.		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.
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 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 ==

Dimitri: /* Routing and Forwarding */

2026-01-04T11:03:36Z

Routing and Forwarding

← Older revision		Revision as of 11:03, 4 January 2026
Line 48:		Line 48:

	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.		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.

	~~=== Formal Definition of Routing in Ouroboros ===~~

	Let <math>G = (V, A)</math> be a network.		Let <math>G = (V, A)</math> be a network.
Line 70:		Line 68:

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

	~~=== Formal Definition of Forwarding ===~~

	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.