Path Metadata in Beacons

Introduction

When selecting end-to-end SCION paths, it is useful to have information about the properties of the available paths, such as information about the expected latency or the “type” of the traversed links.

This document describes how metadata can be included in an optional extension of the Path Construction Beacons (PCBs), called StaticInfoExtension, so that it can be used by applications on the end hosts in the path selection process.

Static properties

We distinguish between static and dynamic properties of a path. Static properties remain valid over the course of its announced lifetime. The lifetime of a path typically is on the order of minutes to hours. Properties that can vary more quickly are considered dynamic.

As an example, the maximum possible bandwidth on each link of a path is static, as it will not change unless the underlying network infrastructure is modified. On the other hand, the bandwidth available to an application over this path is dynamic, as it depends on the current load on the network infrastructure along the path.

In the PCBs, we can naturally only include information about the static properties of a path.

Symmetry

SCION paths and path segments are reversible. The system described here does not allow representing values differing depending on the usage direction. Instead, we require that all metadata items represent quantities that are symmetric. If a path hop has e.g. different latency in the two directions we can just pick the more conservative estimate.

Path Segments with Metadata

SCION end-to-end paths are obtained by combining up to three (up, core and down) path segments which correspond directly to a PCB. A path segment consists of a series of ASEntrys, one for each AS. An ASEntry describes the traversal of an AS for a specific pair of “ingress” and “egress” interfaces (where ingress/egress refer to the dissemination direction of the beacon).

To describe the properties of all hops of a path, we will have to include information about the links between the ASes (inter-AS hops), and also for the hops from the ingress to the egress inside an AS (intra-AS hops). For the intra-AS hops, it is however not enough to include only information about the hop between the beacon ingress and egress interfaces – where two path segments can be “joined” together, we have to ensure that the information about the resulting intra-AS hop is contained in (at least) one of the ASEntrys.

The figures below illustrate the various ways in which segments can be combined to form end-to-end paths:

Path Combinations — Combination of path segments to paths: the blue circles represent the end hosts; the shaded gray circles represent core ASes, possibly in different ISDs; blue lines without arrow heads denote hops of created forwarding paths; the dashed blue line denotes a peering link (labeled “p”); orange lines with arrows stand for PCBs and indicate their dissemination direction; dashed orange lines represent core beacons exchanged over core links (labeled “c”). All created forwarding paths in cases 1a-1e traverse the ISD core(s), whereas the paths in cases 2-4 do not enter the ISD core.

Representation in StaticInfoExtension

We use the following scheme, to ensure that each hop is described by (at least) one ASEntry. We rely on symmetry and avoid some redundancy. Each ASEntry includes information about:

the inter-AS hop at the egress interface
the intra-AS hop between egress and any (other) CHILD-link interface with ID smaller than the egress interface, for shortcuts.
the intra-AS hop between egress and any (other) CORE-link interface, for up-core or core-down segment cross-over
the intra-AS hop between egress and any PEER-link interface, and the inter-AS hop at any PEER-interface

Illustration of the information included in the individual `ASEntry`s in path segments and how this information is used in path segment combinations. The black circles represent ASes, the shaded circles are core ASes. Solid black lines connecting the ASes represent parent-child or core links, the dashed black line is a peering link. Each color represents an `ASEntry`. Entries in the up segments are **blue**, core segments are **red** and down segments **green**. Dotted lines represent information about links that is included in the PCBs, but not used in this path segment combination.
Path from 111 to 211, through core. Case 1a, above.	Path from 111 to 211, via peering link. Case 2, above.
Path from 111 to 112, with shortcut at 110. Case 3, above.

Wire format

In the PCBs, the per-hop information is represented using the following structure (extracted from proto/control_plane/v1/seg_extensions.proto): This is the generalized Protocol Buffers-like description for a per-link metadata item of type T (but Protocol Buffers does not actually have a templates).

message HopMetadata<T> {
    // Information about the hop between construction-egress interface and the relevant other
    // interfaces. These are:
    // - construction-ingress interface (if any)
    // - sibling child interfaces,
    // - core interfaces, at start or end of a segment
    // - peer interfaces
    // The key is the interface identifier of the other interface.
    map<uint64, T> intra = 1;
    // Information about the hop between the local interface and the interface in the neighbor AS
    // for the relevant links. These are:
    // - link at construction-egress interface (if any)
    // - peer links
    // The key is the interface identifier of the local interface associated
    // with the link.
    map<uint64, T> inter = 2;
}

Note that some of the metadata types discussed below do not describe per-hop information but e.g. per-AS notes. These are much simpler to represent in the PCBs and don’t need to be discussed here.

Conflicts

When combining the information from all the path segments, information may be available from more than one ASEntry. Therefore, it is possible to have conflicting information, which must be considered when combining path segments.

The conflicts are resolved by selecting the most conservative value.

This conflict resolution procedure allows an AS to announce a more conservative value for the metadata of inter-AS links if it disagrees with the value announced by the upstream AS.

Authenticity, Integrity and Accuracy

The responsibility for providing all of this metadata lies with the individual ASes. There is no mechanism to enforce that this information is complete or accurate.

The beacon extensions are signed/verified based on the control plane PKI. This provides integrity and accountability for the provided metadata.

No AS can tamper with the metadata included in a beacon
The source of the metadata is visible and non-repudiable. Thus, if an AS was detected to be including false information, it can be held accountable by e.g. being added to a block list.

Metadata types

Latency

Latency describes the propagation delay between any two hops on the path. The advertised information describes the latency for an ideal idle state of the network infrastructure, i.e. it does not account for any variable delay due to queuing or processing.