RFC 9198

Advanced Unidirectional Route Assessment (AURA)

📅 published May 2022, from ietf

Advanced Unidirectional Route Assessment (AURA) 🦋

Internet Engineering Task Force (IETF) · Request for Comments: 9198 · Updates: 2330 · Category: Standards Track · ISSN: 2070-1721 · May 2022

Authors: J. Alvarez-Hamelin (Universidad de Buenos Aires), A. Morton (AT&T Labs), J. Fabini (TU Wien), C. Pignataro (Cisco Systems, Inc.), and R. Geib (Deutsche Telekom)

okay so the important stuff up top: this is an Internet Standards Track doc 🎀 from the IETF, it's dated May 2022, and it updates RFC 2330 (it doesn't obsolete anything). the authors are a whole squad from universities, AT&T, Cisco, TU Wien and Deutsche Telekom, so this is serious networking energy 💅

Abstract

okay so this memo introduces a new metric called AURA (advanced unidirectional route assessment) 🌸 and a way to measure it, built on top of the IP Performance Metrics (IPPM) framework from RFC 2330. the main glow-up here is updating RFC 2330's path terminology and path description so they can handle parallel subpaths between a Source and Destination pair. that's a real thing now because of multipath technologies, so the old wording just wasn't cutting it anymore 🫶

Status of This Memo

this is an Internet Standards Track document 🔥

it's a product of the Internet Engineering Task Force (IETF), so it represents the consensus of the IETF community. it got public review and was approved for publication by the Internet Engineering Steering Group (IESG). if you want more on Internet Standards, check Section 2 of RFC 7841 📚

for the current status of this doc, any errata, and how to send feedback, go to:

https://www.rfc-editor.org/info/rfc9198

Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved. 💜

this document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication. please actually read those, bestie, because they explain your rights and restrictions for this doc 🙈

also, any Code Components pulled out of this document must include Revised BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, as described in the Revised BSD License.

Table of Contents 🗺️

1.  Introduction
  1.1.  Issues with Earlier Work to Define a Route Metric
  1.2.  Requirements Language
2.  Scope
3.  Route Metric Specifications
  3.1.  Terms and Definitions
  3.2.  Formal Name
  3.3.  Parameters
  3.4.  Metric Definitions
  3.5.  Related Round-Trip Delay and Loss Definitions
  3.6.  Discussion
  3.7.  Reporting the Metric
4.  Route Assessment Methodologies
  4.1.  Active Methodologies
    4.1.1.  Temporal Composition for Route Metrics
    4.1.2.  Routing Class Identification
    4.1.3.  Intermediate Observation Point Route Measurement
  4.2.  Hybrid Methodologies
  4.3.  Combining Different Methods
5.  Background on Round-Trip Delay Measurement Goals
6.  RTD Measurements Statistics
7.  Security Considerations
8.  IANA Considerations
9.  References
  9.1.  Normative References
  9.2.  Informative References
Appendix A.  MPLS Methods for Route Assessment
Acknowledgements
Authors' Addresses

1. Introduction ✨

okay so the IETF IP Performance Metrics (IPPM) Working Group originally built a framework for making metrics in [RFC2330] 💖 and honestly it has aged like fine wine, because it enabled a ton of fundamental metrics. it's been updated for metric composition in [RFC5835] and for active stream measurement of modern networks with reactive properties in [RFC7312] 🎀

the framework in [RFC2330] was all about "performance and reliability metrics for paths through the Internet." Section 5 of [RFC2330] defines the terms for describing a path under test. but metrics for assessing paths and related performance stuff had not been attempted in IPPM yet when that framework was written 🧚

so this memo takes on the Route measurement challenge 💅. it specifies a new Route metric, two practical frameworks for measurement methods (either active, or hybrid active-passive [RFC7799]), and Round-Trip Delay and link information discovery using the measurement results ✨.

all Route measurements are limited by how willing the Hosts along the path are to be discovered, to cooperate with the methods being used, or to recognize that a measurement is happening (for example, when tunnels are present). this is the reality check 🙈

1.1. Issues with Earlier Work to Define a Route Metric

okay so Section 7 of [RFC2330] gives a simple example of a "Route" metric, along with some other examples 📚. here's the example, with the reference pointing to Section 5 of [RFC2330]:

|  route:  The path, as defined in Section 5, from A to B at a given
|     time.

this example is a good starting point, but it needs a more complete definition of Route. the areas that need clarifying are:

Time: in practice, the Route gets assessed over a time interval, because active path detection methods like Paris-traceroute [PT] rely on Hop Limits to work and can't discover all Hosts with a single packet 🕐.

Type-P: the legacy Route definition has no option for packet-dependent routing 💀. in this memo, we assess the Route for a specific packet of Type-P and reflect that in the metric definition. the measurement methods decide which Type-P gets used.

Parallel Paths: parallel paths are a reality of the Internet and a strength of advanced Route assessment methods, so the metric has to acknowledge that they're possible 🍓. Equal-Cost Multipath (ECMP) and Unequal-Cost Multipath (UCMP) technologies are common sources of parallel subpaths.

Cloud Subpath: cloud subpaths may contain Hosts that don't decrement the Hop Limit, but they may have two or more exchange links connecting "discoverable" Hosts or routers 🌈. parallel subpaths inside clouds can't be discovered. the assessment methods only discover Hosts or routers on the path that decrement Hop Limit or cooperate with interrogation protocols. tunnels and nested tunnels make it even harder by hiding Hops 🙈.

Hop: the definition of Hop in [RFC2330] was a link-Host pair 🦋. but only Hosts that were discoverable and cooperated with interrogation protocols (which is where link information may be exposed) gave both link and Host information.

note that the actual definitions show up in Section 3.1 ✨.

1.2. Requirements Language

the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. 🎀

2. Scope 🌸

the purpose of this memo is to add new Route metrics and measurement methods to the existing set of IPPM metrics 💖.

the scope is to define Route metrics that can identify the path taken by a packet or a flow crossing the Internet between two Hosts 🧚. even though it's mainly meant for Hosts talking over the Internet, the definitions and metrics are built to work in other network domains too, if you want 🫶. the measurement methods might not discover all the Hosts that make up the path, but those omissions are usually deterministic and explainable sources of error ✨.

this memo also specifies a framework for active measurement methods that use the techniques described in [PT] 🔥. it also specifies a framework for hybrid active-passive measurement methods, like the Hybrid Type I method [RFC7799] described in [RFC9197]. methods using [RFC9197] are only intended for single administrative domains that offer a protocol for explicit interrogation of Nodes on a path 🦋. combinations of active methods and hybrid active-passive methods are in scope too.

further, this memo does extra analysis of the Round-Trip Delay measurements that the methods make possible, to dig up more details about the path, like what link technology is in use 🔍.

this memo updates Section 5 of [RFC2330] in the areas of path-related terminology and path description 💅. mainly, it includes the possibility of parallel subpaths between a given Source and Destination address pair (which can come from ECMP and UCMP technologies).

there are a few simple non-goals of this memo 🙈. there's no attempt to assess the reverse path from any Host on the path back to the Host running the path measurement. the reverse path contribution to delay is what ICMP packets experience (in active methods), and it may be different from the delays UDP or TCP packets experience. also, the Round-Trip Delay includes an unknown contribution of processing time at the Host that generates the ICMP response.

so, bestie: the ICMP-based active methods are not supposed to yield accurate, reproducible estimations of the Round-Trip Delay that UDP or TCP packets will experience. don't use them to predict your app's latency 💀

3. Route Metric Specifications 👑

this section sets requirements for the components of the route metric 🎀.

Part 1 of 6 done! 💖 more parts coming, so stay tuned, bestie 🫶

3.1. Terms and Definitions ✨

okay bestie, let's get into the vocab, because these definitions are the foundation for everything else 💅

Host 🖥️

A Host (as defined in [RFC2330]) is a computer capable of IP communication, including routers (aka an RFC 2330 Host). 💖

Node 🌸

A Node is any network function on the path capable of IP-layer Communication, including RFC 2330 Hosts. ✨

Node Identity 🦋

The Node identity is the unique address for Nodes communicating within the network domain. For Nodes communicating on the Internet with IP, it is the globally routable IP address that the Node uses when communicating with other Nodes under normal or error conditions. The Node identity revealed (and its connection to a Node name through reverse DNS) determines whether interfaces to parallel links can be associated with a single Node or appear to identify unique Nodes. 👑

Discoverable Node 🔍

Discoverable Nodes are Nodes that convey their Node identity according to the requirements of their network domain, such as when error conditions are detected by that Node. For Nodes communicating with IP packets, compliance with Section 3.2.2.4 of [RFC1122], when discarding a packet due to TTL or Hop Limit Exceeded condition, MUST result in sending the corresponding Time Exceeded message (containing a form of Node identity) to the source. This requirement is also consistent with Section 5.3.1 of [RFC1812] for routers. 🎀

Cooperating Node 🤝

Cooperating Nodes are Nodes that respond to direct queries for their Node identity as part of a previously established and agreed upon interrogation protocol. Nodes SHOULD also provide information such as arrival/departure interface identification, arrival timestamp, and any relevant information about the Node or specific link that delivered the query to the Node. 🫶

Hop specification 🍓

A Hop specification MUST contain a Node identity and MAY contain arrival and/or departure interface identification, Round-Trip Delay, and an arrival timestamp. 🧚

Routing Class 💜

Routing Class is a Route that treats a class of different types of packets, designated "C" (unrelated to address classes of the past) equally ([RFC2330] [RFC8468]). Knowledge of such a class allows any one of the types of packets within that class to be used for subsequent measurement of the Route. The designator "class C" is used for historical reasons; see [RFC2330]. 🌈

3.2. Formal Name 🎀

The formal name of the metric is:

Type-P-Route-Ensemble-Method-Variant

abbreviated as Route Ensemble. 💅

Note that Type-P depends heavily on the chosen method and variant. 👀

3.3. Parameters 📋

This section lists the REQUIRED input factors to define and measure a Route metric, as specified in this memo. ✨

  • Src: the address of a Node (such as the globally routable IP address).
  • Dst: the address of a Node (such as the globally routable IP address).
  • i: the limit on the number of Hops a specific packet may visit as it traverses from the Node at Src to the Node at Dst (such as the TTL or Hop Limit).
  • MaxHops: the maximum value of i used (i=1,2,3,...MaxHops).
  • T0: a time (start of measurement interval).
  • Tf: a time (end of measurement interval).
  • MP(address): the Measurement Point at address, such as Src or Dst, usually at the same Node stack layer as "address".
  • T: the Node time of a packet as measured at MP(Src), meaning Measurement Point at the Source.
  • Ta: the Node time of a reply packet's arrival as measured at MP(Src), assigned to packets that arrive within a "reasonable" time (see parameter below).
  • Tmax: a maximum waiting time for reply packets to return to the source, set sufficiently long to disambiguate packets with long delays from packets that are discarded (lost), such that the distribution of Round-Trip Delay is not truncated.
  • F: the number of different flows simulated by the method and variant.
  • flow: the stream of packets with the same n-tuple of designated header fields that (when held constant) result in identical treatment in a multipath decision (such as the decision taken in load balancing). Note: The IPv6 flow label MAY be included in the flow definition if the MP(Src) is a Tunnel Endpoint (TEP) complying with the guidelines in [RFC6438]. 🦋
  • Type-P: the complete description of the packets for which this assessment applies (including the flow-defining fields). 🌸

3.4. Metric Definitions 📏

This section defines the REQUIRED measurement components of the Route metrics (unless otherwise indicated): 💖

  • M: the total number of packets sent between T0 and Tf.
  • N: the smallest value of i needed for a packet to be received at Dst (sent between T0 and Tf).
  • Nmax: the largest value of i needed for a packet to be received at Dst (sent between T0 and Tf). Nmax may be equal to N.

Next, define a singleton for a Node on the path with sufficient indexes to identify all Nodes identified in a measurement interval (where singleton is part of the IPPM Framework [RFC2330]).

  • singleton: A Hop specification, designated h(i,j), the IP address and/or identity of Discoverable Nodes (or Cooperating Nodes) that are i Hops away from the Node with address = Src and part of Route j during the measurement interval T0 to Tf. As defined here, a Hop singleton measurement MUST contain a Node identity, hid(i,j), and MAY contain one or more of the following attributes:
    • a(i,j) Arrival Interface ID (e.g., when [RFC5837] is supported)
    • d(i,j) Departure Interface ID (e.g., when [RFC5837] is supported)
    • t(i,j) arrival timestamp, where t(i,j) is ideally supplied by the Hop (note that t(i,j) might be approximated from the sending time of the packet that revealed the Hop, e.g., when the round-trip response time is available and divided by 2)
    • Measurements of Round-Trip Delay (for each packet that reveals the same Node identity and flow attributes, then this attribute is computed; see next section)

Node identities and related information can be ordered by their distance from the Node with address Src in Hops h(i,j). Based on this, two forms of Routes are distinguished: 🗺️

A Route Ensemble is defined as the combination of all Routes traversed by different flows from the Node at Src address to the Node at Dst address. A single Route traversed by a single flow (determined by an unambiguous tuple of addresses Src and Dst and other identical flow criteria) is a member of the Route Ensemble and called a Member Route. ✨

Using h(i,j) and components and parameters further define: 💅

When considering the set of Hops in the context of a single flow, a Member Route j is an ordered list {h(1,j), ... h(Nj, j)} where h(i-1, j) and h(i, j) are one Hop away from each other and Nj satisfying h(Nj,j)=Dst is the minimum count of Hops needed by the packet on member Route j to reach Dst. Member Routes MUST be unique. The uniqueness property requires that any two Member Routes, j and k, that are part of the same Route Ensemble differ either in terms of minimum Hop count Nj and Nk to reach the destination Dst or, in the case of identical Hop count Nj=Nk, they have at least one distinct Hop: h(i,j) != h(i,k) for at least one i (i=1..Nj). 🔥

All the optional information collected to describe a Member Route, such as the arrival interface, departure interface, and Round-Trip Delay at each Hop, turns each list item into a rich structure. There may be information on the links between Hops, possible information on the routing (arrival interface and departure interface), an estimate of distance between Hops based on Round-Trip Delay measurements and calculations, and a timestamp indicating when all these additional details were measured. 🌷

The Route Ensemble from Src to Dst, during the measurement interval T0 to Tf, is the aggregate of all m distinct Member Routes discovered between the two Nodes with Src and Dst addresses. More formally, with the Node having address Src omitted:

Route Ensemble = {
{h(1,1), h(2,1), h(3,1), ... h(N1,1)=Dst},
{h(1,2), h(2,2), h(3,2),..., h(N2,2)=Dst},
...
{h(1,m), h(2,m), h(3,m), ....h(Nm,m)=Dst}
}

where the following conditions apply: i <= Nj <= Nmax (j=1..m) 🧠

Note that some h(i,j) may be empty (null) in the case that systems do not reply (not discoverable or not cooperating). 🙈

h(i-1,j) and h(i,j) are the Hops on the same Member Route one Hop away from each other. 💜

Hop h(i,j) may be identical with h(k,l) for i!=k and j!=l, which means there may be portions shared among different Member Routes (parts of Member Routes may overlap). 🌈

3.5. Related Round-Trip Delay and Loss Definitions ⏱️

RTD(i,j,T) is defined as a singleton of the [RFC2681] Round-Trip Delay between the Node with address = Src and the Node at Hop h(i,j) at time T. 🦋

RTL(i,j,T) is defined as a singleton of the [RFC6673] Round-Trip Loss between the Node with address = Src and the Node at Hop h(i,j) at time T. 🌸

3.6. Discussion 💬

Depending on the way that the Node identity is revealed, it may be difficult to determine parallel subpaths between the same pair of Nodes (i.e., multiple parallel links). It is easier to detect parallel subpaths involving different Nodes. 🫶

  • If a pair of discovered Nodes identify two different addresses (IP or not), then they will appear to be different Nodes. See item below.
  • If a pair of discovered Nodes identify two different IP addresses and the IP addresses resolve to the same Node name (in the DNS), then they will appear to be the same Node.
  • If a discovered Node always replies using the same network address, regardless of the interface a packet arrives on, then multiple parallel links cannot be detected in that network domain. This condition may apply to traceroute-style methods but may not apply to other hybrid methods based on In situ Operations, Administration, and Maintenance (IOAM). For example, if the ICMP extension mechanism described in [RFC5837] is implemented, then parallel links can be detected with the discovery traceroute-style methods. 🍓
  • If parallel links between routers are aggregated below the IP layer, then, from the Node's point of view, all these links share the same pair of IP addresses. The existence of these parallel links can't be detected at the IP layer. This applies to other network domains with layers below them as well. This condition may apply to traceroute-style methods but may not apply to other hybrid methods based on IOAM. 🧚

When a Route assessment employs IP packets (for example), the reality of flow assignment to parallel subpaths involves layers above IP. Thus, the measured Route Ensemble is applicable to IP and higher layers (as described in the methodology's packet of Type-P and flow parameters). 👑

3.7. Reporting the Metric 💌

Okay so, there's this whole Information Model and XML Data Model for storing traceroute measurements over in [RFC5388] 📚. Right now, the info at each Hop is four things: a one-dimensional Hop index, the Node's symbolic address, the Node's IP address, and the RTD for each response 🦋.

But this memo collects way more dimensions, as defined in Section 3.4 ✨. The Hop index is two-dimensional so it can capture the complexity of a Route Ensemble, and it has the matching Node identities at a minimum 💅. The models need to grow to include all of this, plus Arrival Interface ID, Departure Interface ID, and arrival timestamp when they're available 🎀. And the original sending Timestamp from the Src Node anchors a particular measurement in time, so everything gets pinned to a moment 💖.

4. Route Assessment Methodologies ✨

Okay so there are two classes of methods in this section 🧚. First up, active methods that rely on the reaction to a TTL or Hop Limit Exceeded condition to discover Nodes on a path. Then there are hybrid active-passive methods that involve direct interrogation of Cooperating Nodes (usually within a single domain) 💜. Let's get into it!

4.1. Active Methodologies 💅

This section describes the method used by current open-source tools, which gives us a practical framework for more advanced techniques to be added as method variants 🔥. This method works across multiple administrative domains, so it's not stuck in one lane 🌈.

Internet routing is complex because it depends on the policies of thousands of Autonomous Systems (ASes) 🌸. Most routers do load balancing on flows using a form of ECMP. [RFC2991] describes a bunch of flow-based or hashed approaches (like Modulo-N Hash, Hash-Threshold, and Highest Random Weight (HRW)) and makes some really good suggestions 👑. Flow-based ECMP avoids increased packet Delay Variation and possibly overwhelming levels of packet reordering in flows 🫶.

A few routers still split the workload with packet-based techniques, like a round-robin scheme that sends every new outgoing packet to multiple links, as explained in [RFC2991] 🙈. The methods in this section assume flow-based ECMP.

Taking into account that the Internet protocol was designed under the "end-to-end" principle, the IP payload and its header don't give any information about the Routes or path needed to reach some destination 💀. So the popular tool, traceroute, was developed to gather the IP addresses of each Hop along a path using ICMP [RFC0792] ✨. Traceroute also measures RTD from each Hop. However, the growing complexity of the Internet makes it harder to build an accurate traceroute implementation 😭. For instance, the early traceroute tools would be inaccurate on today's network, mainly because they weren't designed to retain a flow state 🙈. Evolved traceroute tools like Paris-traceroute ([PT] [MLB]) and Scamper ([SCAMPER]) expect to run into ECMP and get more accurate results when they do. Scamper ensures traceroute packets follow the same path in 98% of cases ([SCAMPER]) 🔥.

Today's traceroute tools send Type-P packets, which are ICMP, UDP, or TCP 🦋. UDP and TCP are used when a particular characteristic needs checking, like filtering or traffic shaping on specific ports (i.e., services) 🎀. UDP and TCP traceroute are also used when ICMP responses don't come back. [SCAMPER] supports IPv6 traceroute measurements and keeps the Flow Label constant in all packets 🧚.

Paris-traceroute lets its users measure the RTD to every Node on the path for a particular flow 💖. Also, either Paris-traceroute or Scamper can uncover the many available paths between a source and destination (the ones visible to active methods) 👀. They do this by repeating complete traceroute measurements with different flow parameters each time. Paris-traceroute has an "exhaustive" mode, and Scamper has "tracelb" (short for "traceroute load balance") 💜. "Framework for IP Performance Metrics" [RFC2330], updated by [RFC7312], is flexible enough to require that the Round-Trip Delay measurement [RFC2681] uses packets with constraints that make every packet in one measurement look like the same flow ✨. That flexibility covers ICMP, UDP, and TCP. The accompanying methodology of [RFC2681] needs to be expanded to report the sequential Hop identifiers along with RTD measurements, but no new metric definition is needed 🌈.

The advanced Route assessment methods in Paris-traceroute [PT] keep the critical fields constant for every packet so they still look like the same flow 🫶. For IPv6 headers, the IP Source and Destination addresses and the Flow Label must stay constant. Note that many routers still ignore the Flow Label field right now, so see [RFC6437] 🙈. Using IPv6 Extension Headers may add critical fields, and they SHOULD be avoided 🚫. For IPv4, certain fields of the IP header and the first 4 bytes of the IP payload should stay constant within a flow. In the IPv4 header, the IP Source and Destination addresses, protocol number, and Diffserv fields identify flows. The first 4 payload bytes include the UDP and TCP ports and the ICMP type, code, and checksum fields 🎀.

Keeping the ICMP checksum constant in IPv4 is the most challenging part, because the ICMP sequence number or identifier fields will usually change between probes of the same path 😩. Probes should use arbitrary bytes in the ICMP data field to offset those changes to the sequence number and identifier, which keeps the checksum constant 🧩.

Finally, it's also essential to Route the resulting ICMP Time Exceeded messages along a consistent path 💅. In IPv6, the fields above are enough. In IPv4, the ICMP Time Exceeded message contains the IP header and the first 8 bytes of the IP payload, and both of those affect its ICMP checksum calculation. The TCP sequence number, UDP length, and UDP checksum all affect this value, so they should stay constant too 🍓.

Formally, to keep the same flow in measurements to a particular Hop, the Type-P-Route-Ensemble-Method-Variant packets should have the following attributes (see [PT]) 📜:

  • TCP case: For IPv4, the fields Src, Dst, port-Src, port_Dst, sequence number, and Diffserv SHOULD be the same. For IPv6, the fields Flow Label, Src, and Dst SHOULD be the same.
  • UDP case: For IPv4, the fields Src, Dst, port-Src, port-Dst, and Diffserv should be the same, and the UDP checksum SHOULD change to keep the IP checksum of the ICMP Time Exceeded reply constant. Then, the data length should be fixed, and the data field is used to make it so. Consider that the ICMP checksum uses its data field, which contains the original IP header plus 8 bytes of UDP, where TTL, IP identification, IP checksum, and UDP checksum change. For IPv6, the Flow Label field and the Source and Destination addresses SHOULD be the same.
  • ICMP case: For IPv4, the data field SHOULD compensate for variations in TTL or Hop Limit, IP identification, and IP checksum for every packet. There's no need to consider ICMPv6, because only the Flow Label of IPv6 and the Source and Destination addresses are used, and all of them SHOULD be constant 🙌.

Then, here's how to identify different Hops and attempts of the same IPv4 flow 🔍:

  • TCP case: The IP identification field.
  • UDP case: The IP identification field.
  • ICMP case: The IP identification field and ICMP sequence number.

4.1.1. Temporal Composition for Route Metrics ⏳

The active Route assessment methods above can find portions of a path where ECMP load balancing is present. You can see this when two or more unique Member Routes have one or more distinct Hops that are part of the Route Ensemble 🌀. Likewise, when you deliberately vary the flow characteristics to discover all Member Routes, you'll reveal the portions of the path that are flow invariant 🦋.

Section 9.2 of [RFC2330] describes the Temporal Composition of metrics and introduces the possibility of a relationship between earlier measurement results and the results for a measurement taken now (for a given metric) 💜. There's value in setting up a Temporal Composition relationship for Route metrics. However, this relationship is not a forecast of future Route conditions in any way, so don't go reading the future in it 🔮.

For Route-metric measurements, the point of Temporal Composition is to cut down on the measurement iterations needed with repeated measurements 💅. You can reduce iterations by inferring that current measurements using fixed and previously measured flow characteristics:

  • will have many common Hops with previous measurements.
  • will have relatively time-stable results at the ingress and egress portions of the path when measured from user locations, as opposed to measurements of backbone networks and across inter-domain gateways.
  • may have greater potential for time variation in path portions where ECMP load balancing is observed (because increasing or decreasing the pool of links changes the hash calculations).

Optionally, measurement systems may use the inferences above to cut down on measurement iterations once exhaustive measurements show that the time-stable properties are there ✨. Repetitive active Route measurement systems:

  1. SHOULD occasionally check path portions that have shown stable results over time, particularly the ingress and egress portions of the path (e.g., daily checks if you're measuring many times a day) 🌅.
  2. SHOULD keep testing portions of the path that have previously shown ECMP load balancing 🔁.
  3. SHALL trigger reassessment of the complete path and Route Ensemble if any change in Hops is observed for a specific (and previously tested) flow 🚨. No cap, this one's a must-do 💀.

4.1.2. Routing Class Identification 🎀

Okay bestie, so there's a lowkey iconic opportunity to use the idea from [RFC2330] of equal treatment for a class of packets 🦋. The quote is "...very useful to know if a given Internet component treats equally a class C of different types of packets", and it applies to Route measurements. The notion of class C got a deeper glow-up in [RFC8468], where it was about load-balancing flows over parallel paths, which is exactly the case we're building here 💅. Knowing the class C parameters on a path (and no, not the old address classes, different thing 🙈) can potentially cut down how many flows you need for a given method to assess a Route Ensemble over time ✨.

First, recognize that each Member Route of a Route Ensemble will have a corresponding class C 💖. Class C can be discovered by testing with multiple flows, all of which traverse the unique set of Hops that make up a specific Member Route.

Second, recognize that the different classes depend primarily on the hash functions used at each instance of ECMP load balancing on the path 🌈.

Third, recognize the synergy with Temporal Composition methods (described above), where evaluation intends to discover time-stable portions of each Member Route so that more emphasis can be placed on ECMP portions that also determine class C 👑.

The methods to assess the various class C characteristics benefit from the following measurement capabilities:

  • flows designed to determine which n-tuple header fields are considered by a given hash function and ECMP Hop on the path and which are not. This operation immediately narrows the search space, where possible, and partially defines a class C 🧚.
  • a priori knowledge of the possible types of hash functions in use also helps to design the flows for testing (major router vendors publish information about these hash functions; examples are in [LOAD_BALANCE]) 📚.
  • ability to direct the emphasis of current measurements on ECMP portions of the path, based on recent past measurement results (the Routing Class of some portions of the path is essentially "all packets") 🍓.

4.1.3. Intermediate Observation Point Route Measurement 🔍

There are so many examples where passive monitoring of a flow at an Observation Point within the network can detect unexpected Round-Trip Delay or Delay Variation 😭. But how can the cause of the anomalous delay be investigated further from the Observation Point when it's possibly sitting at an intermediate point on the path? 🤔

In this case, knowing that the flow of interest belongs to a specific Routing Class C will enable measurement of the Route where the anomalous delay was observed ✨. Specifically, Round-Trip Delay assessment to each Hop on the path between the Observation Point and the Destination for the flow of interest may discover high or variable delay on a specific link and Hop combination 🎀.

The determination of a Routing Class C that includes the flow of interest works the way described in the section above, aided by computing the relevant hash function output as the target 🦋.

4.2. Hybrid Methodologies 🌸

The Hybrid Type I methods give you an alternative for Route assessment 💅. The "Scope, Applicability, and Assumptions" section of [RFC9197] provides one possible set of data fields that would support Route identification.

In general, Nodes in the measured domain would be equipped with specific abilities:

  • Store the identity of Nodes that a packet has visited in header data fields, in the order the packet visited the Nodes 🧚.
  • Support of a "Loopback" capability where a copy of the packet is returned to the encapsulating Node, and the packet is processed like any other IOAM packet on the return transfer 🔁.

In addition to Node identity, Nodes may also identify the ingress and egress interfaces utilized by the tracing packet, the absolute time when the packet was processed, and other generic data (as described in Section 3 of [RFC9197]) ⏰. Interface identification isn't necessarily limited to IP, i.e., different links in a bundle (Link Aggregation Control Protocol (LACP)) could be identified 🍓. Equally well, links without explicit IP addresses can be identified (like with unnumbered interfaces in an IGP deployment) 💜.

Note that the Type-P packet specification for this method will likely be a partial specification, because most of the packet fields are determined by the user traffic 🙈. The packet encapsulation header or headers added by the hybrid method can certainly be specified in Type-P, in unpopulated form ✨.

4.3. Combining Different Methods 🫶

In principle, there are advantages if the entity conducting Route measurements can utilize both forms of advanced methods (active and hybrid) and combine the results 🔥. For example, if there are Nodes involved in the path that qualify as Cooperating Nodes but not as Discoverable Nodes, then a more complete view of Hops on the path is possible when a hybrid method (or interrogation protocol) is applied and the results are combined with the active method results collected across all other domains 🌈.

In order to combine the results of active and hybrid/interrogation methods, the network Nodes that are part of a domain supporting an interrogation protocol have the following attributes:

  1. Nodes at the ingress to the domain SHOULD be both Discoverable and Cooperating 💖.
  2. Any Nodes within the domain that are both Discoverable and Cooperating SHOULD reveal the same Node identity in response to both active and hybrid methods 👑.
  3. Nodes at the egress to the domain SHOULD be both Discoverable and Cooperating and SHOULD reveal the same Node identity in response to both active and hybrid methods 🧚.

When Nodes follow these requirements, it becomes a simple matter to match single-domain measurements with the overlapping results from a multidomain measurement ✨.

In practice, Internet users don't typically have the ability to use the Operations, Administrations, and Maintenance (OAM) capabilities of the networks their packets traverse, so the results from a remote domain supporting an interrogation protocol wouldn't normally be accessible 😭. However, a network operator could combine interrogation results from their access domain with other measurements revealing the path outside their domain 💅.

5. Background on Round-Trip Delay Measurement Goals 🎀

The aim of this method is to use packet probes to unveil the paths between any two End-Nodes of the network 🔍. Moreover, information derived from RTD measurements might be meaningful for identifying:

  1. Intercontinental submarine links 🌊
  2. Satellite communications 🛰️
  3. Congestion 🚦
  4. Inter-domain paths 🌸

This categorization is widely accepted in the literature and among operators alike, and it can be trusted with empirical data and several sources as ground truth (e.g., [RTTSub]). It is an inference measurement nonetheless [bdrmap] [IDCong] 🙈.

The first two categories correspond to the physical distance dependency on RTD. The next one binds RTD with queuing delay on routers, and the last one helps to identify different ASes using traceroutes 🦋. Due to the significant contribution of propagation delay in long-distance Hops, RTD will be on the order of 100 ms on transatlantic Hops, depending on the geolocation of the vantage points ✈️. Moreover, RTD is typically higher than 480 ms when two Hops are connected using geostationary satellite technology (i.e., their orbit is at 36000 km) 🛰️. Detecting congestion with latency implies deeper mathematical understanding, since network traffic load is not stationary 📈. Nonetheless, as the first approach, a link seems to be congested if observing different or varying statistical results after sending several traceroute probes (e.g., see [IDCong]) 🚦. Finally, recognizing distinctive ASes in the same traceroute path is challenging, because more data is needed, like AS relationships and Regional Internet Registry (RIR) delegations among others (for more details, please consult [bdrmap]) 🥹.

6. RTD Measurements Statistics ✨

okay so, several articles have shown that network traffic is self-similar [SSNT] [MLRM], and that's the thing responsible for filling up router queues 😭. Routers are built to handle traffic bursts, which is honestly one of the most iconic features of self-similarity 💅. So when the queue gets longer, the delay to get through it gets longer too, and that pushes RTD up 📈. Bursts cause short-term overflow on buffers (think spiky patterns), which means each RTD only tells you the queue status at the exact moment that probe was in transit 🦋. That's why a bunch of RTD measurements over one time window can start to show the random behavior of latency. And loss has to be accounted for in the methodology too, bestie, don't forget it 🫶.

To understand what's going on, quartiles are a nonparametric way to analyze it 🎀. A quartile set is made of five values: the minimum RTD (m), the RTD value at 25% of the Empirical Cumulative Distribution Function (ECDF) (Q1), the median (Q2), the RTD value at 75% of the ECDF (Q3), and the maximum RTD (M). When RTD measurements are spread apart, congestion can be inferred 👀. So the Interquartile Range (IQR), which is just the distance between Q3 and Q1, goes up.

This procedure needs the algorithm presented in [P2] so the quartile values can be computed "on the fly" ⚡.

The best part is that this procedure lets us update the quartile values every time a new measurement arrives. That's radically different from classic quartile methods, which need the whole dataset to compute anything 🍓. Because of that, it saves memory and computing time 💜.

To sum it up, the measurement procedure is: run traceroutes several times to collect samples of the RTD for every Hop on a path during a time window (W), then compute the quartiles for every Hop ✨. This can be done for a single Member Route flow, for a non-exhaustive search with parameter E (defined below) set to False, or for every detected Route Ensemble flow (E=True) 🌈.

Now, how do we even identify a specific Hop in a traceroute? 🧚 It's based on the IP origin address of the returned ICMP Time Exceeded packet, plus the distance set by the TTL (or Hop Limit) field that traceroute inserted. Since one Hop can be reached by different paths, you also have to record the IP Source and Destination addresses of the traceroute packet. Different return paths are told apart by checking the TTL (or Hop Limit) of the ICMP Time Exceeded reply: if that value is constant across different paths containing the same Hop, those return paths have the same distance 🔍. You can also estimate this distance, since the TTL (or Hop Limit) is normally initialized to 64, 128, or 255. Altogether, the 5-tuple (origin IP, destination IP, reply IP, distance, and response TTL or Hop Limit) uniquely identifies every measurement 🔥.

This algorithm runs at the origin of the traceroute, and it returns the Qs quartiles for every Hop and Alt (alternative paths because of balancing) 💅. Heads up: the "Alt" parameter condenses the 5-tuple parameters (origin IP, destination IP, reply IP, distance, and response TTL), so there's one for each possible combination 🎀.

================================================================
0  input:   W (window time of the measurement)
1           i_t (time between two measurements, set the i_t time
2                long enough to avoid incomplete results)
3           E (True: exhaustive, False: a single path)
4           Dst (destination IP address)
5  output:  Qs (quartiles for every Hop and Alt)
----------------------------------------------------------------
6  T := start_timer(W)
7  while T is not finished do:
8  |       start_timer(i_t)
9  |       RTD(Hop,Alt) = advanced-traceroute(Dst,E)
10 |       for each Hop and Alt in RTD do:
11 |       |     Qs[Dst,Hop,Alt] := ComputeQs(RTD(Hop,Alt))
12 |       done
13 |       wait until i_t timer is expired
14 done
15  return (Qs)
================================================================

Here's how the loop works 🌸. During the time W, lines 6 and 7 make sure the measurement loop keeps going. Lines 8 and 13 set a timer for each measurement cycle. A cycle covers the traceroute packets for every possible Hop and the alternative paths in the Alt variable, which lines 9 through 12 take care of 🫶. On line 9, the advanced-traceroute can be either Paris-traceroute or Scamper. If E is set to True, they use the "exhaustive" mode or the "tracelb" option respectively 🦋. The procedure returns a list of tuples (m, Q1, Q2, Q3, and M) for each intermediate Hop, or each "Alt" as a function of the 5-tuple, along the path toward Dst ✨. Finally, lines 10 through 12 store each measurement into the real-time quartile computation 💜.

Also, there are cases where, even with a unique Hop at distance h from the Src to Dst, the return path could have several possibilities, which gives different total paths. In that situation, the algorithm returns another "Alt" for that particular Hop 👑.

7. Security Considerations 🔐

The security considerations that apply to any active measurement of live paths apply here too. See [RFC4656] and [RFC5357].

The active measurement process of changing several fields so the checksums of different packets stay identical doesn't need any special security considerations 🎀. That's because it's part of synthetic traffic generation, and it's designed to have minimal to zero impact on network processing (to process the packets for ECMP) 🧚.

Some of the protocols used (e.g., ICMP) don't provide cryptographic protection for the requested or returned data. There are also risks in processing untrusted data in general, but these are limitations of the existing protocols that we're applying the new methods to 😬.

For applicable hybrid methods, the security considerations in [RFC9197] apply 💜.

Now for privacy 🙈. When you think about the privacy of the people involved in measurement, or the people whose traffic is measured, the sensitive information available to potential observers is greatly reduced when you use the active techniques in this scope of work ✨. Passive observation of user traffic for measurement purposes raises a lot of privacy issues 💀. For the privacy considerations, see the Large-scale Measurement of Broadband Performance (LMAP) Framework [RFC7594], which covers both active and passive techniques.

8. IANA Considerations 🌈

This document has no IANA actions 💅.

9. References 📚

9.1. Normative References

9.2. Informative References ✨

Okay bestie, these are the extra-credit reads 📚 Lowkey the best rabbit holes on the internet, so bookmark them 🔖

   [bdrmap]   Luckie, M., Dhamdhere, A., Huffaker, B., Clark, D., and
              KC. Claffy, "bdrmap: Inference of Borders Between IP
              Networks", Proceedings of the 2016 ACM on Internet
              Measurement Conference, pp. 381-396,
              DOI 10.1145/2987443.2987467, November 2016,
              <https://doi.org/10.1145/2987443.2987467>.

   [IDCong]   Luckie, M., Dhamdhere, A., Clark, D., and B. Huffaker,
              "Challenges in Inferring Internet Interdomain Congestion",
              Proceedings of the 2014 Conference on Internet Measurement
              Conference, pp. 15-22, DOI 10.1145/2663716.2663741,
              November 2014, <https://doi.org/10.1145/2663716.2663741>.

   [LOAD_BALANCE]
              Sanguanpong, S., Pittayapitak, W., and K. Kasom Koht-Arsa,
              "COMPARISON OF HASH STRATEGIES FOR FLOW-BASED LOAD
              BALANCING", International Journal of Electronic Commerce
              Studies, Vol.6, No.2, pp.259-268, DOI 10.7903/ijecs.1346,
              December 2015, <https://doi.org/10.7903/ijecs.1346>.

   [MLB]      Augustin, B., Friedman, T., and R. Teixeira, "Measuring
              load-balanced paths in the internet", Proceedings of the
              7th ACM SIGCOMM conference on Internet measurement, pp.
              149-160, DOI 10.1145/1298306.1298329, October 2007,
              <https://doi.org/10.1145/1298306.1298329>.

   [MLRM]     Fontugne, R., Mazel, J., and K. Fukuda, "An empirical
              mixture model for large-scale RTT measurements", 2015 IEEE
              Conference on Computer Communications (INFOCOM), pp.
              2470-2478, DOI 10.1109/INFOCOM.2015.7218636, April 2015,
              <https://doi.org/10.1109/INFOCOM.2015.7218636>.

   [P2]       Jain, R. and I. Chlamtac, "The P 2 algorithm for dynamic
              calculation of quartiles and histograms without storing
              observations", Communications of the ACM 28.10 (1985):
              1076-1085, DOI 10.1145/4372.4378, October 1985,
              <https://doi.org/10.1145/4372.4378>.

   [PT]       Augustin, B., Cuvellier, X., Orgogozo, B., Viger, F.,
              Friedman, T., Latapy, M., Magnien, C., and R. Teixeira,
              "Avoiding traceroute anomalies with Paris traceroute",
              Proceedings of the 6th ACM SIGCOMM conference on Internet
              measurement, pp. 153-158, DOI 10.1145/1177080.1177100,
              October 2006, <https://doi.org/10.1145/1177080.1177100>.

   [RFC2991]  Thaler, D. and C. Hopps, "Multipath Issues in Unicast and
              Multicast Next-Hop Selection", RFC 2991,
              DOI 10.17487/RFC2991, November 2000,
              <https://www.rfc-editor.org/info/rfc2991>.

   [RFC5357]  Hedayat, K., Krzanowski, R., Morton, A., Yum, K., and J.
              Babiarz, "A Two-Way Active Measurement Protocol (TWAMP)",
              RFC 5357, DOI 10.17487/RFC5357, October 2008,
              <https://www.rfc-editor.org/info/rfc5357>.

   [RFC5835]  Morton, A., Ed. and S. Van den Berghe, Ed., "Framework for
              Metric Composition", RFC 5835, DOI 10.17487/RFC5835, April
              2010, <https://www.rfc-editor.org/info/rfc5835>.

   [RFC5837]  Atlas, A., Ed., Bonica, R., Ed., Pignataro, C., Ed., Shen,
              N., and JR. Rivers, "Extending ICMP for Interface and
              Next-Hop Identification", RFC 5837, DOI 10.17487/RFC5837,
              April 2010, <https://www.rfc-editor.org/info/rfc5837>.

   [RFC6437]  Amante, S., Carpenter, B., Jiang, S., and J. Rajahalme,
              "IPv6 Flow Label Specification", RFC 6437,
              DOI 10.17487/RFC6437, November 2011,
              <https://www.rfc-editor.org/info/rfc6437>.

   [RFC7312]  Fabini, J. and A. Morton, "Advanced Stream and Sampling
              Framework for IP Performance Metrics (IPPM)", RFC 7312,
              DOI 10.17487/RFC7312, August 2014,
              <https://www.rfc-editor.org/info/rfc7312>.

   [RFC7325]  Villamizar, C., Ed., Kompella, K., Amante, S., Malis, A.,
              and C. Pignataro, "MPLS Forwarding Compliance and
              Performance Requirements", RFC 7325, DOI 10.17487/RFC7325,
              August 2014, <https://www.rfc-editor.org/info/rfc7325>.

   [RFC7594]  Eardley, P., Morton, A., Bagnulo, M., Burbridge, T.,
              Aitken, P., and A. Akhter, "A Framework for Large-Scale
              Measurement of Broadband Performance (LMAP)", RFC 7594,
              DOI 10.17487/RFC7594, September 2015,
              <https://www.rfc-editor.org/info/rfc7594>.

   [RFC8403]  Geib, R., Ed., Filsfils, C., Pignataro, C., Ed., and N.
              Kumar, "A Scalable and Topology-Aware MPLS Data-Plane
              Monitoring System", RFC 8403, DOI 10.17487/RFC8403, July
              2018, <https://www.rfc-editor.org/info/rfc8403>.

   [RTTSub]   Bischof, Z., Rula, J., and F. Bustamante, "In and out of
              Cuba: Characterizing Cuba's Connectivity", Proceedings of
              the 2015 ACM Conference on Internet Measurement
              Conference, pp. 487-493, DOI 10.1145/2815675.2815718,
              October 2015, <https://doi.org/10.1145/2815675.2815718>.

   [SCAMPER]  Matthew Luckie, M., "Scamper: a scalable and extensible
              packet prober for active measurement of the internet",
              Proceedings of the 10th ACM SIGCOMM conference on Internet
              measurement, pp. 239-245, DOI 10.1145/1879141.1879171,
              November 2010, <https://doi.org/10.1145/1879141.1879171>.

   [SSNT]     Park, K. and W. Willinger, "Self-Similar Network Traffic
              and Performance Evaluation (1st ed.)",
              DOI 10.1002/047120644X,  John Wiley & Sons, Inc., New
              York, NY, USA, August 2000,
              <https://doi.org/10.1002/047120644X>.

Appendix A. MPLS Methods for Route Assessment 🧚

Okay so first things first: a Node assessing an MPLS path must be part of the MPLS domain where that path is implemented 🏠 Once you're in the domain, [RFC8029] gives you a seriously powerful toolkit to check "correct operation of the data plane, as well as a mechanism to verify the data plane against the control plane" 💅

MPLS routing depends on having a Forwarding Equivalence Class (FEC) Stack in every visited Node 📦 Picking one of several Equal-Cost Multipaths (ECMPs), though, depends on info buried deeper in the stack 🕳️ Newer deployments may use a so-called "Entropy label" for this 🌈 State-of-the-art deployments base their ECMP choice on the complete MPLS label stack and on IP addresses, all the way up to the complete 5-tuple IP header information (see Section 2.4 of [RFC7325]) 🔥 Load sharing based on IP information decouples this from the actual MPLS routing information, which is the whole point 🙌 So an MPLS traceroute can check how packets with a contiguous run of ECMP-relevant IP addresses (and an identical MPLS label stack) get forwarded by a particular router 🦋 The minimum number of equivalent MPLS paths traceable at a router should be 32 ✨ Implementations that support more paths are out there too 💖

The MPLS echo request and reply messages that offer this feature must support the Downstream Detailed Mapping TLV 🎀 (It used to be Downstream Mapping, but that one has been deprecated 🙈) The MPLS echo response includes the incoming interface where a router received the MPLS echo request 📍 The MPLS echo reply also tells you which of the n addresses relevant for the load-sharing decision leads to a particular next-hop interface, and it includes that next hop's interface address (if available) 🧭 This makes sure the next hop gets a properly coded MPLS echo request in the next step of the route assessment 🫶

[RFC8403] explains how a central Path Monitoring System could detect arbitrary MPLS paths between any routers within a single MPLS domain 🛰️ Put MPLS forwarding, Segment Routing, and MPLS traceroute together and you get a simple architecture plus a powerful mechanism to detect and validate (segment-routed) MPLS paths 👑

Acknowledgements 🫶

The original three authors (Ignacio, Al, Joachim) thank Ruediger Geib for his penetrating comments on the initial document and for his initial text for the appendix on MPLS 💜 Carlos Pignataro challenged the authors to consider a wider scope and brought his substantial expertise with many technologies and their measurement features to his extensive comments 🌸 Frank Brockners also shared useful comments, and so did Footer Foote 🍓 We thank them all! 💖

Authors' Addresses 🎀

   J. Ignacio Alvarez-Hamelin
   Universidad de Buenos Aires
   Av. Paseo Colón 850
   C1063ACV Buenos Aires
   Argentina
   Phone: +54 11 5285-0716
   Email: ihameli@cnet.fi.uba.ar
   URI:   http://cnet.fi.uba.ar/ignacio.alvarez-hamelin/


   Al Morton
   AT&T Labs
   200 Laurel Avenue South
   Middletown, NJ 07748
   United States of America
   Phone: +1 732 420 1571
   Email: acm@research.att.com


   Joachim Fabini
   TU Wien
   Gusshausstrasse 25/E389
   1040 Vienna
   Austria
   Phone: +43 1 58801 38813
   Email: Joachim.Fabini@tuwien.ac.at
   URI:   http://www.tc.tuwien.ac.at/about-us/staff/joachim-fabini/


   Carlos Pignataro
   Cisco Systems, Inc.
   7200-11 Kit Creek Road
   Research Triangle Park, NC 27709
   United States of America
   Email: cpignata@cisco.com


   Ruediger Geib
   Deutsche Telekom
   Heinrich Hertz Str. 3-7
   64295 Darmstadt
   Germany
   Phone: +49 6151 5812747
   Email: Ruediger.Geib@telekom.de
📦 where this page comes from