SCION Control Plane

1.1. Terminology

Autonomous System (AS): An autonomous system is a network under a common administrative control. For example, the network of an Internet service provider, company, or university can constitute an AS.¶

Beaconing: The control-plane process where an AS discovers paths to other ASes.¶

Control Plane: The SCION control plane is responsible for the propagation and discovery of network paths, i.e., for the exchange of routing information between network nodes. The control plane thus determines where traffic can be sent and deals with questions such as how paths are discovered, which paths exist, what quality individual links offer, etc. Within a SCION AS, such functionalities are carried out by the control service. Packet forwarding is instead a task pertaining to the data plane.¶

Control Service: The control service is the main control-plane infrastructure component within a SCION AS. It is responsible for the path exploration and registration processes that take place within the control plane.¶

Core AS: Each isolation domain (ISD) is administered by a set of distinguished autonomous systems (ASes) called core ASes, which are responsible for initiating the path-discovery and -construction process (in SCION called "beaconing").¶

Endpoint: An endpoint is the start- or the endpoint of a SCION path. For example, an endpoint can be a host as defined in [RFC1122], or a gateway bridging a SCION and an IP domain. This definition is based on the definition in [I-D.path-properties-voc].¶

Forwarding Path: A forwarding path is a complete end-to-end path between two SCION hosts, which is used to transmit packets in the data plane and can be created with a combination of up to three path segments (an up-segment, a core-segment, and a down-segment).¶

Hop Field (HF): As they traverse the network, path-segment construction beacons (PCBs) accumulate cryptographically protected AS-level path information in the form of hop fields. In the data plane, hop fields are used for packet forwarding: they contain the incoming and outgoing interface IDs of the ASes on the forwarding path.¶

Info Field (INF): Each path-segment construction beacon (PCB) contains a single info field, which provides basic information about the PCB. Together with hop fields (HFs), info fields are used to create forwarding paths.¶

Isolation Domain (ISD): In SCION, autonomous systems (ASes) are organized into logical groups called isolation domains or ISDs. Each ISD consists of ASes that span an area with a uniform trust environment (i.e., a common jurisdiction). A possible model is for ISDs to be formed along national boundaries or federations of nations.¶

Leaf AS: An AS at the "edge" of an ISD, with no other downstream ASes.¶

Packet-Carried Forwarding State (PCFS): Rather than relying on costly inter-domain forwarding tables, SCION data packets contain all the necessary path information. We refer to this property as packet-carried forwarding state or PCFS.¶

Path Segment: Path segments are derived from path-segment construction beacons (PCBs) and registered at control services. A path segment can be (1) an up-segment (i.e., a path between a non-core AS and a core AS in the same ISD), (2) a down-segment (i.e., the same as an up-segment, but in the opposite direction), or (3) a core-segment (i.e., a path between core ASes). Up to three path segments can be used to create a forwarding path.¶

Path-Segment Construction Beacon (PCB): Core ASes generate PCBs to explore paths within their isolation domain (ISD) and among different ISDs. ASes further propagate selected PCBs to their neighboring ASes. As a PCB traverses the network, it carries path segments, which can subsequently be used for traffic forwarding.¶

Trust Root Configuration (TRC): A trust root configuration or TRC is a signed collection of certificates pertaining to an isolation domain (ISD). TRCs also contain ISD-specific policies.¶

1.2. Conventions and Definitions

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

1.3. Paths and Links

SCION routers and endpoints connect to each other via links. A SCION path between two endpoints essentially traverses one or more links.¶

In SCION, autonomous systems (ASes) are organized into logical groups called isolation domains or ISDs. Each ISD consists of ASes that span an area with a uniform trust environment (i.e., a common jurisdiction). An ISD is administered by a set of distinguished ASes called core ASes. Within and between ISDs, SCION supports three types of links: (1) core links, (2) parent-child links, and (3) peering links.¶

• A core link always connects two core ASes, which are either within the same or in a different ISD. Core links can exist for various underlying business relationships, including provider-customer (where the customer pays the provider for traffic) and peering relationships.¶
• Parent-child links create a hierarchy between the parent and the child. ASes with a parent-child link typically have a provider-customer relationship.¶
• Peering links exist between ASes with a (settlement-free or paid) peering relationship. Peering links can only be used to reach destinations within or downstream of the peering AS. They can be established between any two core or non-core ASes, and between core and non-core ASes. Peering links can also cross ISD boundaries.¶

The following figure shows the three types of links for one small ISD with the two core ASes A and C, and the four non-core ASes D,E,F, and G.¶

+-------------------------+
|                         |       #
|        ISD Core         |       |      parent-child
|  .---.           .---.  |       |      link
| (  A  )*-------*(  C  ) |       |
|  `-#-'           `-#-'  |       0
|    |               |    |
+----|---------------|----+   *-------*  core link
     |               |
     |               |        < - - - >  peering link
   .-0-.           .-0-.
  (  D  )< - - - >(  E  )
   `-#-'           `-#-'
     |               |
     |               |
     |               |
   .-0-.           .-0-.
  (  G  )         (  F  )
   `---'           `---'

Each link connecting SCION routers is bidirectional and identified by its corresponding egress and ingress interface IDs. These interface IDs only need to be unique within each AS. Therefore, they can be chosen and encoded by each AS independently and without any need for coordination.¶

1.4. Routing

SCION provides path-aware inter-domain routing between ASes across the Internet. The SCION control plane is responsible for discovering these inter-domain paths and making them available to the endpoints within the ASes. SCION inter-domain routing operates on two levels: Within a SCION isolation domain (ISD), which is called intra-ISD routing, and between ISDs, called inter-ISD routing. Both levels use the so-called path-segment construction beacons (PCBs) to explore network paths. A PCB is initiated by a core AS and then disseminated either within an ISD to explore intra-ISD paths, or among core ASes, to explore core paths across different ISDs.¶

The PCBs accumulate cryptographically protected path and forwarding information on AS-level, and store this information in the form of hop fields. Endpoints use information from these hop fields to create end-to-end forwarding paths for data packets, who carry this information in their packet headers. This concept is called packet-carried forwarding state. The concept also supports multi-path communication among endpoints.¶

The creation of an end-to-end forwarding path consists of the following processes:¶

1. Path exploration (or beaconing): This is the process where an AS discovers paths to other ASes. See also Section 2.¶
2. Path registration: This is the process where an AS selects a few PCBs, according to defined policies, turns the selected PCBs into path segments, and adds these path segments to the relevant path infrastructure, thus making them available to other ASes. See also Section 3.¶
3. Path resolution: This is the process of actually creating an end-to-end forwarding path from the source endpoint to the destination. For this, an endpoint performs (a) a path lookup step, to obtain path segments, and (b) a path combination step, to combine the forwarding path from the segments. This last step takes place in the data plane. See also Section 4.¶

All processes operate concurrently.¶

Figure 2 below shows the SCION routing processes and their relation to each other.¶

+-------------------------+       +-------------------------+
| Exploration (Beaconing) |------>|      Registration       |
+-------------------------+       +-----------+-------------+
                                              |
                              +---------------+
                              |
     +------------------------v------------------------+
     |                 Path Resolution                 |
     |                                                 |
     |   +----------------+       +----------------+   |
     |   |     Lookup     +------>|  Combination   |   |
     |   |                |       |    (Data Plane)|   |
     |   +----------------+       +----------------+   |
     +-------------------------------------------------+

The control service is responsible for the path exploration and registration processes in the control plane. It is the main control-plane infrastructure component within each SCION AS. The control service of an AS has the following tasks:¶

• Generating, receiving, and propagating PCBs. Periodically, the control service of a core AS generates a set of PCBs, which are forwarded to the child ASes or neighboring core ASes. In the latter case, the PCBs are sent over policy-compliant paths to discover multiple paths between any pair of core ASes.¶
• Selecting and registering the set of path segments via which the AS wants to be reached.¶
• Managing certificates and keys to secure inter-AS communication. Each PCB contains signatures of all on-path ASes. Every time the control service of an AS receives a PCB, it validates the PCB's authenticity. When the control service lacks an intermediate certificate, it can query the control service of the neighboring AS that sent the PCB.¶

Note: The control service of an AS must not be confused with a border router. The control service of a specific AS is part of the control plane and responsible for finding and registering suitable paths. It can be deployed anywhere inside the AS. A border router belongs to the data plane; its main task is to forward data packets. Border routers are deployed at the edge of an AS.¶

1.5. Addressing

The inter-domain SCION routing is based on the <ISD, AS> tuple. Although a complete SCION address is composed of the <ISD, AS, endpoint address> 3-tuple, the endpoint address is not used for inter-domain routing or forwarding. The endpoint address can be of variable length, does not need to be globally unique, and can thus be an IPv4, IPv6, or MAC address, for example - in fact, the endpoint address is the "normal", currently used, non-SCION-specific endpoint address.¶

However, the ISD-AS number is a SCION-specific number. It consists of 64-bits, with the top 16 bits indicating the ISD, and the bottom 48 bits indicating the AS. The text representation uses a dash-separator between the ISD and AS numbers, for example: 4-ff00:1:f. This section provides more details about the numbering scheme for SCION ISD and AS numbers.¶

Note: As a consequence of the fact that SCION relies on existing routing protocols (e.g., IS-IS, OSPF, SR) and communication fabric (e.g., IP, MPLS) for intra-domain forwarding, existing internal routers do not need to be changed to support SCION.¶

1.6. Avoiding Circular Dependencies and Partitioning

A secure and reliable routing architecture must be designed specifically to avoid circular dependencies during network initialization. One goal of SCION is that the Internet can start up even after large outages or attacks, in addition to avoiding cascades of outages caused by fragile interdependencies. This section lists the concepts SCION uses to prevent circular dependencies.¶

• Neighbor-based path discovery: Path discovery in SCION is performed by the beaconing mechanism. In order to participate in this process, an AS only needs to be aware of its direct neighbors. As long as no path segments are available, communicating with the neighboring ASes is possible with the one-hop path type, which does not rely on any path information. SCION uses these one-hop paths to propagate PCBs to neighboring ASes to which no forwarding path is available yet. The One-Hop Path Type will be described in more detail in the SCION Data Plane specification (this document will be available later this year).¶
• Path segment types: SCION uses different types of path segments to compose end-to-end paths. Notably, a single path segment already enables intra-ISD communication. For example, a non-core AS can reach the core of the local ISD simply by using an up-segment fetched from the local path storage, which is populated during the beaconing process.¶
• Path reversal: In SCION, every path is reversible—i.e., the receiver of a packet can reverse the path in the packet header to send back a reply packet without having to perform a path lookup.¶
• Availability of certificates: In SCION, every entity is required to be in possession of all cryptographic material (including the ISD's Trust Root Configuration TRC and certificates) that is needed to verify any message it sends. This (together with the path reversal) means that the receiver of a message can always obtain all this necessary material by contacting the sender.
  Note: For a detailed description of a TRC and more information on the availability of certificates and TRCs, see the SCION Control-Plane PKI Internet-Draft [I-D.scion-cppki].¶

1.7. Communication Protocol

All communication between the control services in different ASes is expressed in terms of gRPC remote procedure calls (for details, see [gRPC]). Service interfaces and messages are defined in the Protocol Buffer "proto3" interface definition language (for details, see [proto3]).¶

Note: The details of how gRPC is mapped to the SCION data plane will be described in a separate document.¶

2.1. Introduction and Overview

Path exploration is the process where an AS discovers paths to other ASes. In SCION, this process is referred to as beaconing. This section gives a detailed explanation of the SCION beaconing process.¶

In SCION, the control service of each AS is responsible for the beaconing process. The control service generates, receives, and propagates so-called path-segment construction beacons (PCBs) on a regular basis, to iteratively construct path segments. PCBs contain topology and authentication information, and can also include additional metadata that helps with path management and selection. The beaconing process itself is divided into routing processes on two levels, where inter-ISD or core beaconing is based on the (selective) sending of PCBs without a defined direction, and intra-ISD beaconing on top-to-bottom propagation.¶

• Inter-ISD or core beaconing is the process of constructing path segments between core ASes in the same or in different ISDs. During core beaconing, the control service of a core AS either initiates PCBs or propagates PCBs received from neighboring core ASes to other neighboring core ASes. Core beaconing is periodic; PCBs are sent over policy-compliant paths to discover multiple paths between any pair of core ASes.¶
• Intra-ISD beaconing creates path segments from core ASes to non-core ASes. For this, the control service of a core AS creates PCBs and sends them to the non-core child ASes (typically customer ASes). The control service of a non-core child AS receives these PCBs and forwards them to its child ASes, and so on. This procedure continues until the PCB reaches an AS without any customer (leaf AS). As a result, all ASes within an ISD receive path segments to reach the core ASes of their ISD.¶

On its way, a PCB accumulates cryptographically protected path- and forwarding information per traversed AS. At every AS, metadata as well as information about the AS's ingress and egress interfaces are added to the PCB.¶

                            +-------------+
                            | Core AS X   |
                            |             |
                            |    2   1    |
                            +----#---#----+
          +--------+             |   |             +--------+
          |PCB     |     +-----+ |   | +-----+     |PCB     |
          |========|-----|PCB a| |   | |PCB b|=====|++++++++|
          |Core    |     +-----+ |   | +-----+     |Core    |
          |- Out:2 |        |    |   |    |        |- Out:1 |
          +--------+        v    |   |    v        +--------+
                                 v   v
                            +----#---#----+
                            |     AS Y    |

                        +-----+ |   | +-----+
                        |PCB a| |   | |PCB b|
                        +-----+ |   | +-----+
                           |    |   |    |
                           v    |   |    v
                                v   v
                           +----#---#----+
                 .---.     |    2   3    |
                (  V  )- --# 1           |
                 `---'     |     AS Y    |     .---.
                           |           4 #- --(  W  )
                           |             |     `---'
                           |    6   5    |
            +--------+     +----#---#----+     +--------+
            |PCB     |          |   |          |PCB     |
            |========|          |   |          |========|
            |Core X  |          |   |          |Core X  |
            |- Out:2 |          |   |          |- Out:2 |
+--------+  |--------|  +-----+ |   | +-----+  |--------|  +--------+
|PCB     |  |AS Y    |--|PCB c| |   | |PCB d|--|AS Y    |  |PCB     |
|++++++++|  |-In:2   |  +-----+ |   | +-----+  |-In:2   |  |++++++++|
|Core X  |  |-Out:6  |     |    |   |    |     |-Out:5  |  |Core X  |
|- Out:1 |  |-PeerV:1|     v    |   |    v     |-PeerV:1|  |- Out:1 |
|--------|  |-PeerW:4|          |   |          |-PeerW:4|  |--------|
|AS Y    |  +--------+          |   |          +--------+  |AS Y    |
|-In:3   |              +-----+ |   | +-----+              |-In:3   |
|-Out:6  |==============|PCB e| |   | |PCB f|==============|-Out:5  |
|-PeerV:1|              +-----+ |   | +-----+              |-PeerV:1|
|-PeerW:4|                 |    |   |    |                 |-PeerW:4|
+--------+                 v    |   |    v                 +--------+
                                v   v
                           +----#---#----+
                           |    AS Z     |

                   +-----+      |   |      +-----+
                   |PCB c|      |   |      |PCB d|
                   +-----+      |   |      +-----+
                     |  +-----+ |   | +-----+  |
                     v  |PCB e| |   | |PCB f|  v
                        +-----+ |   | +-----+
                           |    |   |    |
                           v    |   |    v
                                v   v
                         +------#---#------+
                         |      5   1      |
                         |                 |
                         | AS Z            |
            +--------+   |        3        |   +--------+
            |PCB     |   +--------#--------+   |PCB     |
            |========|            |            |========|
            |Core X  |            |            |Core X  |
+--------+  |- Out:2 |            |            |- Out:2 |  +--------+
|PCB     |  |--------|            |            |--------|  |PCB     |
|++++++++|  |AS Y    |            |            |AS Y    |  |++++++++|
|Core X  |  |-In:2   |            |            |-In:2   |  |Core X  |
|- Out:1 |  |-Out:6  |   +-----+  |  +-----+   |-Out:5  |  |- Out:1 |
|--------|  |-PeerV:1|---|PCB g|  |  |PCB h|---|-PeerV:1|  |--------|
|AS Y    |  |-PeerW:4|   +-----+  |  +-----+   |-PeerW:4|  |AS Y    |
|-In:3   |  |--------|      |     |     |      |--------|  |-In:3   |
|-Out:6  |  |AS Z    |      v     |     v      |AS Z    |  |-Out:5  |
|-PeerV:1|  |-In:5   |            |            |-In:1   |  |-PeerV:1|
|-PeerW:4|  |-Out:3  |            |            |-Out:3  |  |-PeerW:4|
|--------|  +--------+            |            +--------+  |--------|
|AS Z    |               +-----+  |  +-----+               |AS Z    |
|-In:5   |===============|PCB i|  |  |PCB j|===============|-In:1   |
|-Out:3  |               +-----+  |  +-----+               |-Out:3  |
+--------+                  |     |     |                  +--------+
                            v     |     v
                                  v

                AS Entry Core         AS Entry Y          AS Entry Z

               +-------------+     +-------------+     +-------------+
               |  Core AS X  |     |    AS Y     |     |     AS Z    |
path segment 1 |            1#     #3            5     #1            |
               |             |     |             |     |             |
               |            2#-----#2----------- 6-----#5            |
               |             |     |             |     |             |
               +-------------+     +-------------+     +-------------+
                 egress 2       ingress 2 - egress 6      ingress 5

----------------------------------------------------------------------

               +-------------+     +-------------+     +-------------+
               |  Core AS X  |     |    AS Y     |     |     AS Z    |
               |            1#     #3     +-----5#-----#1            |
path segment 2 |             |     |      |      |     |             |
               |            2#-----#2-----+     6#     #5            |
               |             |     |             |     |             |
               +-------------+     +-------------+     +-------------+
                 egress 2       ingress 2 - egress 5      ingress 1

------------------------------------------------------------------------

               +-------------+     +-------------+     +-------------+
               |  Core AS X  |     |    AS Y     |     |     AS Z    |
               |            1#-----#3-----+     5#     #1            |
path segment 3 |             |     |      |      |     |             |
               |            2#     #2     +-----6#-----#5            |
               |             |     |             |     |             |
               +-------------+     +-------------+     +-------------+
                 egress 1       ingress 3 - egress 6      ingress 5

------------------------------------------------------------------------

               +-------------+     +-------------+     +-------------+
               |  Core AS X  |     |   AS Y      |     |     AS Z    |
               |            1#-----#3-----------5#-----#1            |
path segment 4 |             |     |             |     |             |
               |            2#     #2           6#     #5            |
               |             |     |             |     |             |
               +-------------+     +-------------+     +-------------+
                 egress 1       ingress 3 - egress 5      ingress 1

2.2. Path-Segment Construction Beacons (PCBs)

This section provides a detailed specification of a single PCB and its message format.¶

Note: The SCION open-source implementation makes use of Protobuf (Protocol Buffers), a free and open-source cross-platform data format developed by Google and used to serialize structured data. The messages and remote procedure calls described below are in "proto3" language. For more information on Protobuf, see the official "Protocol Buffers Documentation".¶

                              PCB / PATH SEGMENT

+-------------+------------+------------+--------+--------------------+
|Segment Info | AS Entry 0 | AS Entry 1 |  ...   |     AS Entry N     |
+-------------+------------+------------+--------+--------------------+
*- - - - # - -*            *- - - # - - *
         |                        |
*- - - - v - - - *                |
+---------+------+                |
|Timestamp|Seg ID|                |
+---------+------+                |
                                  |
*- - - - - - - - - - - - - - - - -v- - - - - - - - - - - - - - - - - - *
+-----------------------+----------------------------------------------+
|    Unsigned Ext.      |               Signed AS Entry                |
+-----------------------+----------------------------------------------+
                        *- - - - - - - - - - - - # - - - - - - - - - - *
                                                 |
                                                 |
*- - - - - - - - - - - - - - - - - - - - - - - - v - - - - - - - - - - *
+--------------------+-----------------++------------------------------+
|     Signature      |    Header       ||                    Body      |
+--------------------+-----------------++------------------------------+
                     *- - - - # - - - -**- - - - - - - - # - - - - - - *
                              |                          |
*- - - - - - - - - - - - - - -v- - - - *                 |
+----------------+---------------------+                 |
| Signature Alg. | Verification Key ID |                 |
+----------------+---------------------+                 |
                 *- - - - - # - - - - -*                 |
                            |                            |
*- - - - - - - - - - - - - -v- - - - - - - - - -*        |
+---------+---------+------------+--------------+        |
| ISD-AS  |TRC Base | TRC Serial |Subject Key ID|        |
+---------+---------+------------+--------------+        |
                                                         |
*- - - - - - - - - - - - - - - - - - - - - - - - - - - - v - - - - - - *
+------+-----------+---------++------------+----+------------++---+----+
|ISD-AS|Next ISD-AS|Hop Entry||Peer Entry 0| ...|Peer Entry N||MTU|Ext.|
+------+-----------+---------++------------+----+------------++---+----+
                   *- - # - -**- - - # - - *
                        |            |
                        |            |
*- - - - - - - - - - - -v- *  *- - - v - - - - - - - - - - - - - - - - *
+-------------+------------+  +--------+--------+----------+-----------+
| Ingress MTU | Hop Field  |  |HopField|PeerMTU |PeerISD-AS|PeerInterf.|
+-------------+--------+---+  +----+---+--------+----------+-----------+
                       *- - -#- - -*
                             |
                             |
*- - - - - - - - - - - - - - v - - - - - - - - - - - - - - *
+------------+-------------+-------------------+-----------+
|  Ingress   |    Egress   |  Expiration Time  |   MAC     |
+------------+-------------+-------------------+-----------+

+-------------+-------------+------------+------+------------+
|Segment Info | AS Entry 0  | AS Entry 1 |  ... | AS Entry N |
+-------------+-------------+------------+------+------------+

   message PathSegment {
       bytes segment_info = 1;
       repeated ASEntry as_entries = 2;
   }

+----------------------------+
|         Segment Info       |
+----------------------------+
*- - - - - - - # - - - - - - *
               |
               |
*- - - - - - - v - - - - - - *
+--------------+-------------+
|   Timestamp  |   Seg ID    |
+--------------+-------------+

   message SegmentInformation {
       int64 timestamp = 1;
       uint32 segment_id = 2;
   }

                           +--------------+
                           |  AS Entry    |
                           +--------------+
                           *- - - -#- - - *
                                   |
                                   |
                                   |
*- - - - - - - - - - - - - - - - - v - - - - - - - - - - - - - - - *
+-----------------------+------------------------------------------+
|    Unsigned Ext.      |          Signed AS Entry                 |
+-----------------------+------------------------------------------+

   message ASEntry {
       SignedMessage signed = 1;
       PathSegmentUnsignedExtensions unsigned = 2;
   }

        +------------------------------------------------------+
        |                   Signed AS Entry                    |
        +------------------------------------------------------+
        *- - - - - - - - - - - - -#- - - - - - - - - - - - - - *
                                  |
                                  |
*- - - - - - - - - - - - - - - - -v- - - - - - - - - - - - - - - - - -*
+--------------------+-----------------+------------------------------+
|      Header        |     Body        |            Signature         |
+--------------------+-----------------+------------------------------+

   message SignedMessage {
       bytes header_and_body = 1;
       bytes signature = 2;
   }

   message HeaderAndBodyInternal {
       // Encoded header suitable for signature computation.
       bytes header = 1;
       // Raw payload suitable for signature computation.
       bytes body = 2;
   }

           +-----------------+
           |     Header      |
           +-----------------+
           *- - - - # - - - -*
                    |
 - - - - - - - - - -v- - - - - - - - - *
+----------------+---------------------+
| Signature Alg. | Verification Key ID |
+----------------+---------------------+
                 *- - - - - # - - - - -*
                            |
 - - - - - - - - - - - - - -v- - - - - - - - - -
+---------+---------+------------+--------------+
| ISD-AS  |TRC Base | TRC Serial |Subject Key ID|
+---------+---------+------------+--------------+

   message Header {
       SignatureAlgorithm signature_algorithm = 1;
       bytes verification_key_id = 2;
       // Optional
       google.protobuf.Timestamp timestamp = 3;
       // Optional
       bytes metadata = 4;
       int32 associated_data_length = 5;
   }

   message VerificationKeyID {
       uint64 isd_as = 1;
       bytes subject_key_id = 2;
       uint64 trc_base = 3;
       uint64 trc_serial = 4;
   }

                +--------------------------------------+
                |                 Body                 |
                +--------------------------------------+
                *- - - - - - - - - -#- - - - - - - - - *
                                    |
                                    |
*- - - - - - - - - - - - - - - - - -v- - - - - - - - - - - - - - - - -*
+------+-----------+---------++------------+---+------------++---+----+
|ISD-AS|Next ISD-AS|Hop Entry||Peer Entry 0|...|Peer Entry N||MTU|Ext.|
+------+-----------+---------++------------+---+------------++---+----+

   message ASEntrySignedBody {
       uint64 isd_as = 1;
       uint64 next_isd_as = 2;
       HopEntry hop_entry = 3;
       repeated PeerEntry peer_entries = 4;
       uint32 mtu = 5;
       PathSegmentExtensions extensions = 6;
   }

input(ps, i) = signed.header_and_body || associated_data(ps, i)

associated_data(ps, i) = ps.segment_info ||
                         ps.as_entries[1].signed.header_and_body ||
                         ps.as_entries[1].signed.signature ||
                         ...
                         ps.as_entries[i-1].signed.header_and_body ||
                         ps.as_entries[i-1].signed.signature

       +-----------+
       | Hop Entry |
       +-----------+
       *- - -#- - -*
             |
 - - - - - - v - - - - - - *
+-------------+------------+
| Ingress MTU | Hop Field  |
+-------------+------------+

   message HopEntry {
       HopField hop_field = 1;
       uint32 ingress_mtu = 2;
   }

                      +-----------+
                      | Hop Field |
                      +-----------+
                      *- - -#- - -*
                            |
                            |
*- - - - - - - - - - - - - -v- - - - - - - - - - - - - - - *
+-------------+-------------+-------------------+----------+
|   Ingress   |    Egress   |  Expiration Time  |   MAC    |
+-------------+-------------+-------------------+----------+

   message HopField {
       uint64 ingress = 1;
       uint64 egress = 2;
       uint32 exp_time = 3;
       bytes mac = 4;
   }

                      +--------------+
                      |  Peer Entry  |
                      +--------------+
                      *- - - -#- - - *
                              |
*- - - - - - - - - - - - - - -v- - - - - - - - - - - - - - *
+-------------+------------+--------------+----------------+
|  Hop Field  |  Peer MTU  | Peer ISD-AS  | Peer Interface |
+-------------+------------+--------------+----------------+

   message PeerEntry {
       uint64 peer_isd_as = 1;
       uint64 peer_interface = 2;
       uint32 peer_mtu = 3;
       HopField hop_field = 4;
   }

   +-----------+
   |           |
   | parent AS |
   |           |
   +-----------+
         |
         |
         | ASE.HF.ingress_interface
+--------#-----------+                  +-----------------+
|        |           |         PE.peer_ |                 |
|                    |         interface|                 |
|        | + - - - - #------------------#     peer AS     |
|                    |PE.HF.ingress_    |                 |
|        | |         |interface         |                 |
|                    |                  +-----------------+
|        v v         |
+---------#----------+
          | PE.HF.egress_interface
          | ASE.HF.egress_interface
          |
          |
    +-----------+
    |           |
    |  child AS |
    |           |
    +-----------+

2.3. Propagation of PCBs

This section describes how PCBs are selected and propagated in the path exploration process.¶

 Selected path segment: #------# or *------*
 Peering Link: PL

   ISD A: Path Length                 ISD B: Peering Links
+----------------------+          +---------------------------+
|      ISD Core        |          |        ISD Core           |
| .---.         .---.  |          |  .---.             .---.  |
|(  A  ) - - - (  C  ) |          | (  A  ) - - - - - (  C  ) |
| `-#-'         `---'  |       + --- `---'             `---'  |
|   ||   .---.   | |   |          |      |  .---. - - - - -   |
|   | - (  B  ) -      |       |  |    |  -(  B  )            |
|   |    `-+-'     |   |          |         `-#-||            |
+---|--------------|---+       |  |    |      |   - - - - - - - - +
    |      |       |           |  |           | |             |
    |                          |  +----|------|-|-------------+   |
    |      |     .-+-.                        | + - - - - +
    |    .-+-.  (  E  )        |       |      |                   |
    |   (  D  )  `---'                        |           |
    |    `-+-'     |         .-+-.     |    .-#-.       .-+-.     |
    |            .-+-.      (  D  )-PL-----(  E  )--PL-(  F  )
    |      |    (  F  )      `---'     |    `-#-'       `-+-'   .-+-.
  .-#-.          `-+-'                        |                (  G  )
 (  G  ) - +       |               - - +      |           |     `-+-'
  `---- - - - - - -               |           |
                                .---.       .-#-.       .-+-.     |
                               (  H  )-PL--(  I  )--PL-(  J  )
                                `---'       `-#-'       `---'   .-+-.
                                              |           |    (  K  )
       ISD C: Disjointness                    |                 `---'
  +---------------------------+             .-#-.         |       |
  |          ISD Core         |            (  L  ) - - - -
  |                           |             `---' - - - - - - - - +
  | .---.               .---. |
  |(  A  ) - - - - - - (  C  )|
  | `-*-'               `-#-' |
  |   | |     .---.     | |   |
  |   |  - - (  B  ) - -  |   |
  |   |       `---'       |   |
  +---|-------------------|---+
      |                   |
 .----*.                .-#---.
(   D   )              (   E   )
 `----*'                `-#---'
 |    |                   |   |
    #---------------------#
 |  | |                       |
    | *------------------*
 |  |                    |    |
 .--#--.                .*----.
(   F   #-------#      (   G   )
 `-----'        |       `*----|
 |          *------------*
            |   |             |
 |-----.    |   |       .-----.
(   H  *----*   #------#   I   )
 `---*-'                `-#---'
     |                    |
     |       .---.        |
     *------*  J  #-------#
             `---'

   service SegmentCreationService {
       rpc Beacon(BeaconRequest) returns (BeaconResponse) {}
   }

   message BeaconRequest {
       PathSegment segment = 1;
   }

   message BeaconResponse {}

3.1. Intra-ISD Path-Segment Registration

Every registration period (determined by each AS), the AS's control service selects two sets of PCBs to transform into two types of path segments:¶

• Up-segments, which allow the infrastructure entities and endpoints in this AS to communicate with core ASes; and¶
• down-segments, which allow remote entities to reach this AS.¶

The up- and down-segments do not have to be equal. An AS may want to communicate with core ASes via one or more up-segments that differ from the down-segment(s) through which it wants to be reached. Therefore, an AS can define different selection policies for the up- and down-segment sets. Also, the processes of transforming a PCB in an up-segment or a down-segment differ slightly. Both processes are described below.¶

3.2. Core Path-Segment Registration

The core beaconing process creates path segments from core AS to core AS. These core-segments are then added to the control service path database of the core AS that created the segment, so that local and remote endpoints can obtain and use these core-segments. In contrast to the intra-ISD registration procedure, there is no need to register core-segments with other core ASes (as each core AS will receive PCBs originated from every other core AS).¶

In every registration period, the control service of a core AS performs the following operations:¶

1. The core control service selects the best PCBs towards each core AS observed so far.¶
2. The core control service "terminates" the selected PCBs by performing the steps described in Section 3.1.1. From this moment on, the modified PCBs are called core-segments.¶
3. As a final step, the control service adds the newly created core-segments to its own path database.¶

Note: For more information on possible selection strategies of PCBs, see Section 2.3.1.¶

3.3. Path-Segment Registration on Code-Level

The control service of a non-core AS has to register the newly created down-segments with the control services of the core ASes that originated the corresponding PCBs. This registration step is implemented as follows in Protobuf message format:¶

   enum SegmentType {
       SEGMENT_TYPE_UNSPECIFIED = 0;
       SEGMENT_TYPE_UP = 1;
       SEGMENT_TYPE_DOWN = 2;
       SEGMENT_TYPE_CORE = 3;
   }

   service SegmentRegistrationService {
       rpc SegmentsRegistration(SegmentsRegistrationRequest) returns (SegmentsRegistrationResponse) {}
   }

   message SegmentsRegistrationRequest {
       message Segments {
           repeated PathSegment segments = 1;
       }

       map<int32, Segments> segments = 1;
   }

   message SegmentsRegistrationResponse {}

• SegmentType: Specifies the type of the path segment that must be registered. Currently, only the following type is used:¶

  • SEGMENT_TYPE_DOWN: Specifies a down-segment.¶
• map<int32, Segments> segments: Represents a separate list of segments for each path segment type. The key is the integer representation of the corresponding SegmentType.¶

4.1. Lookup Process

An endpoint (source) that wants to start communication with another endpoint (destination), requires up to three path segments:¶

• An up-path segment to reach the core of the source ISD (only if the source endpoint is a non-core AS),¶

• a core-path segment to reach¶

  • another core AS in the source ISD, in case the destination AS is in the same source ISD, or¶
  • a core AS in a remote ISD, if the destination AS is in another ISD, and¶
• a down-path segment to reach the destination AS.¶

Note: The actual number of required path segments depends on the location of the destination AS as well as on the availability of shortcuts and peering links. More information on combining and constructing paths will be provided by the SCION Data Plane Specification document.¶

The process to look up and fetch path segments consists of the following steps:¶

1. First, the source endpoint queries the control service in its own AS (i.e., the source AS) for the required segments. The control service has up-path segments stored in its path database. Additionally, the control service checks if it has appropriate core- and down-path segments in store as well; in this case it returns them immediately.¶
2. If there are no appropriate core-segments and down-segments, the control service in the source AS queries the control services of the reachable core ASes in the source ISD, for core-path segments to core ASes in the destination ISD (which is either the own or a remote ISD). To reach the core control services, the control service of the source AS uses the locally stored up-path segments.¶
3. Next, the control service of the source AS combines up-path segments with the newly retrieved core-path segments. The control service then queries the control services of the remote core ASes in the destination ISD, to fetch down-path segments to the destination AS. To reach the remote core ASes, the control service of the source AS uses the previously obtained and combined up- and core segments.¶
4. Finally, the control service of the source AS returns all retrieved path segments to the source endpoint.¶
5. Once it has obtained all path segments, the endpoint combines them into an end-to-end path in the data plane.¶

Table 3 below shows which control service provides the source endpoint with which type of path segment.¶

4.2. Behavior of Actors in the Lookup Process

As described above, the source endpoint resolves paths with a sequence of segment requests to the control service of the source AS. The control service in the source AS answers directly, or forwards these requests to the responsible control services of core ASes. In SCION, the instances that handle these segment requests at the control services are called source AS segment-request handler and core AS segment-request handler, respectively. This section specifies the behavior of the segment-request handlers in the lookup process. First, the use of wildcards in the lookup process is briefly addressed.¶