SCION Control Plane

1.4.1. Path Segments

As described previously, the main goal of SCION's control plane is to create and manage path segments, which can then be combined into forwarding paths to transmit packets in the data plane. SCION distinguishes the following types of path segments:¶

• A path segment from a non-core AS to a core AS is an up-segment.¶

• A path segment from a core AS to a non-core AS is a down-segment.¶

• A path segment between core ASes is a core-segment.¶

So each path segment either ends at a core AS, or starts at a core AS, or both.¶

All path segments are invertible: A core-segment can be used bidirectionally, and an up-segment can be converted into a down-segment, or vice versa, depending on the direction of the end-to-end path. This means that all path segments can be used to send data traffic in both directions.¶

The cryptographic protection of PCBs / path segments is based on the Control-Plane PKI. The signatures are structured such that the entire message sequence constituting the path segment can be authenticated. The authenticity can be verified by anyone with access to this PKI. For fast validation of the path information carried in individual packets during packet forwarding, symmetric key cryptography is used instead. For this purpose, the hop fields contain a MAC. These MACs are structured to allow verifying the sequence of hops, reflecting the structure of the PCBs, but, in contrast to the PCBs, this can only be validated by the border routers of the respective AS.¶

1.5.1. ISD Numbers

An ISD number is the 16-bit global identifier for an ISD. It MUST be globally unique. The following table gives an overview of the ISD number allocation.¶

Currently, ISD numbers are allocated by Anapaya, the Swiss-based provider of SCION-based networking software and solutions (see Anapaya ISD AS assignments).¶

1.5.2. SCION AS Numbers

A SCION AS number is the 48-bit identifier for an AS. Although they play a similar role, there is no relationship between SCION AS numbers and BGP ASNs as defined by RFC4893. For historical reasons some SCION autonomous systems use a SCION AS number where the first 16 bits are 0, and the remaining 32 bits are identical to their BGP ASN. There is no technical requirement for such an equality.¶

1.5.3. Wildcard Addressing

SCION allows endpoints to use wildcard addresses in the control-plane routing, to designate any core AS, e.g., to place requests for core- or down-segments during path lookup. These wildcard addresses are of the form I-0, to designate any AS in ISD I. Here, "0" is the wildcard for the AS. For more information, see Section 4.2.1.¶

1.6.1. Partition and Healing

Besides inter-dependencies, another threat to the Internet is network partition. Partition occurs when one network is split into two because of a link failure. However, partition of the global SCION inter-domain network is much less likely to happen: During normal operation, the full network fabric is available, offering multiple paths between all ASes. Even during failures there is no special failure mode required, as SCION-enabled ASes could always switch to otherwise unused links.¶

Recovering (also called healing) from a partitioned network is also seamless, as only coarse time synchronization between the partitions is required to resume normal operation and move forward with updates of the cryptographic material.¶

2.1.1. Peering Links

PCBs do not traverse peering links. Instead, peering links are announced along with a regular path in a PCB. If both ASes at either end of a peering link have registered path segments that include this specific peering link, then it is possible to use this peering link during segment combination to create the end-to-end path.¶

2.1.2. Extending a PCB

Every propagation period (as configured by the AS), the control service:¶

• selects the best combinations of PCBs and interfaces connecting to a neighboring AS (i.e., a child AS or a core AS), and¶

• sends each selected PCB to the selected egress interface(s) associated with it.¶

For every selected PCB and egress interface combination, the AS extends the PCB by adding a so-called AS entry to the selected PCB. Such an AS entry includes a hop field that specifies the incoming (ingress) and outgoing (egress) interface for the packet forwarding through this AS, in the beaconing direction. The AS entry can also contain peer entries.¶

• For the specification of one PCB, see Section 2.2¶

• For more details on selecting PCBs, see Section 2.3.1¶

• For more details on propagating PCBs, see Section 2.3.2¶

2.1.3. PCB Propagation - Illustrated Examples

The following three figures show how intra-ISD PCB propagation works, from the ISD's core AS down to child ASes. For the sake of illustration, the interfaces of each AS are numbered with integer values.¶

In Figure 3 below, core AS X sends the two different PCBs "a" and "b" via two different links to child AS Y: PCB "a" leaves core AS X via egress interface "2", whereas PCB "b" is sent over egress interface "1". Core AS X adds the respective egress information to the PCBs when sending them off, as can be seen in the figure (the entries "Core - Out:2" and "Core - Out:1", respectively).¶

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

AS Y receives the two PCBs "a" and "b" through two different (ingress) interfaces, namely "2" and "3", respectively (see Figure 4 below). Additionally, AS Y forwards to AS Z four PCBs that were previously sent by core AS X. For this, AS Y uses the two different (egress) links "5" and "6". AS Y extends the four PCBs with the corresponding ingress and egress interface information. As can be seen in the figure, AS Y also has two peering links to its neighboring peers V and W, through the interfaces "1" and "4", respectively - AS Y includes this information in the PCBs, as well. Thus, each forwarded PCB cumulates path information on its way "down" from core AS X.¶

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

The following figure shows how the four PCBs "c", "d", "e", and "f", coming from AS Y, are received by AS Z over two different links: PCBs "c" and "e" reach AS Z over ingress interface "5", whereas PCBs "d" and "f" enter AS Z via ingress interface "1". Additionally, AS Z propagates PCBs "g", "h", "i", and "j" further down, all over the same link (egress interface "3"). AS Z extends the PCBs with the relevant information, so that each of these PCBs now includes AS hop entries from core AS X, AS Y, and 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

Based on the figures above, one could say that a PCB represents a single path segment. However, there is a difference between a PCB and a (registered) path segment. A PCB is a so-called "travelling path segment" that accumulates AS entries when traversing the Internet. A (registered) path segment, instead, is a "snapshot" of a travelling PCB at a given time T and from the vantage point of a particular AS A. This is illustrated by Figure 6. This figure shows several possible path segments to reach AS Z, based on the PCBs "g", "h", "i", and "j" from Figure 5 above. It is up to AS Z to use all of these path segments or just a selection of them.¶

                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.1. Components of a PCB in Message Format

Figure 7 graphically represents the PCB message format:¶

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

The following sections provide detailed specifications of the PCB messages, starting with the top-level message of one PCB, and then diving deeper into each of the PCB's message components.¶

Note: For a full example of one PCB in the Protobuf message format, please see Appendix "Control Service gRPC API".¶

+-------------+-------------+------------+------+------------+
|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.2.2. PCB Extensions

In addition to basic routing information like hop entries and peer entries, PCBs can be used to communicate additional metadata, in its extensions. Extensions can be signed and unsigned. Signed extensions are protected by the AS signature, whereas unsigned extensions are not.¶

On code-level and in Protobuf message format, extensions are specified as follows:¶

• Unsigned extensions PathSegmentUnsignedExtensions are part of the AS entry component (the ASEntry message, see also Section 2.2.1.3).¶

• Signed extensions PathSegmentExtensions are part of the signed body component of an AS entry (the ASEntrySignedBody message, see also Section 2.2.1.4.2).¶

Note: SCION also supports so-called "detachable extensions". The detachable extension itself is part of a PCB's unsigned extensions, but a cryptographic hash of the detachable extension data is added to the signed extensions. Thus, a PCB with a detachable extension can be signed and verified without actually including the detachable extension in the signature. This prevents a possible processing overhead caused by large cryptographically-protected extensions.¶

2.2.3. PCB Validity

To be valid (that is, usable to construct a valid path), a PCB MUST:¶

• Contain valid AS Entry signatures (Section 2.2.1.4.3).¶

• Have a timestamp (Section 2.2.1.2) that is not in the future.¶

• Contain only unexpired hops (Section 2.2.1.6).¶

For the purpose of validation, a timestamp is considered "future" if it is later than the current time at the point of validation plus the minimum expiration time of a hop field (337.5 seconds, see Section 2.2.1.6).¶

For the purpose of validation, a hop is considered expired if its absolute expiration time, calculated as defined in Section 2.2.1.6, is later than the current time at the point of validation.¶

2.2.4. Configuration

For the purpose of constructing and propagating path segments, an AS control service MUST be configured with links to neighboring ASes. Such information may be conveyed to the control service in an out of band fashion (e.g in a configuration file). For each link, these values MUST be configured:¶

• Local interface ID¶

• Neighbor type (core, parent, child, peer), depending on link type (see Section 1.3). Link type depends on mutual agreements between the organizations operating the ASes at each end of each link.¶

• Neighbor ISD-AS number¶

• Neighbor interface underlay address¶

2.3.1. Selection of PCBs to Propagate

As an AS receives a series of intra-ISD or core PCBs, it MUST select the PCBs it will use to continue beaconing. Each AS specifies a local policy on the basis of which PCBs are evaluated, selected, or eliminated. The selection process can inspect and compare the properties of the candidate PCBs (e.g., length, disjointness across different paths, age, expiration time) and/or take into account which PCBs have been propagated in the past.¶

Naturally, an AS's policy selects PCBs corresponding to paths that are commercially or otherwise operationally viable. From these viable PCBs, only a relatively small subset SHOULD be propagated, to avoid excessive overhead of the path discovery system in bigger networks. The goal of the AS SHOULD be to propagate those candidate PCBs with the highest probability of collectively meeting the needs of the endpoints that will perform path construction. As SCION does not provide any in-band signal about the intentions of endpoints nor about the policies of downstream ASes, the policy will typically select a somewhat diverse set optimized for multiple, generic parameters.¶

 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  #-------#
             `---'

2.3.2. Propagation of Selected PCBs

As mentioned above, once per propagation period (determined by each AS), an AS propagates selected PCBs to its neighboring ASes. This happens on the level of both intra-ISD beaconing and core beaconing. This section describes both processes in more detail.¶

To bootstrap the initial communication with a neighboring beacon service, ASes use so-called one-hop paths. This special kind of path handles beaconing between neighboring ASes for which no forwarding path may be available yet. In fact, it is the task of beaconing to discover such forwarding paths. The purpose of one-hop paths is thus to break this circular dependency. The One-Hop Path Type is described in more detail in [I-D.dekater-scion-dataplane].¶

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

   message BeaconRequest {
       PathSegment segment = 1;
   }

   message BeaconResponse {}

2.3.3. Effects of Clock Inaccuracy

A PCB originated by a given control service is validated by all the control services that receive it. All have different clocks. Their differences affect the validation process:¶

• A fast clock at origination or a slow clock at reception will yield a lengthened expiration time for hops, and possibly an origination time in the future.¶

• A slow clock at origination or a fast clock at reception will yield a shortened expiration time for hops, and possibly an expiration time in the past.¶

This bias comes in addition to a structural delay: PCBs are propagated at a configurable interval (typically, around one minute). As a result of this and the way they are iteratively constructed, PCBs with N hops may be validated up to N intervals (so maximally N minutes) after origination. This creates a constraint on the expiration of hops. Hops of the minimal expiration time (337.5 seconds - see Section 2.2.1.6) would render useless any PCB describing a path longer than 5 hops. For this reason, it is unadvisable to create hops with a short expiration time, that should be around 6 hours.¶

The control service and its clients authenticate each-other according to their respective AS's certificate. Path segments are authenticated based on the certificates of the ASes that they refer to. The expiration of a SCION AS certificate typically ranges from 3h to 5 years. In comparison to these time scales, clock offsets in the order of minutes are immaterial.¶

Each administrator of a SCION control service is responsible for maintaining sufficient clock accuracy. No particular method is assumed by this specification.¶

2.4.1. Intra-ISD Beaconing

In the intra-ISD beaconing, PCBs are propagated top-down, along parent-child links, from core to leaf ASes. Each AS discovers path segments from itself to the core ASes of its ISD.¶

Typically, this directed, acyclic graph is narrow at the top, widens towards the leafs, and is relatively shallow; intermediate provider ASes have a large number of children, while they only have a small number of parents. The chain of intermediate providers from a leaf AS to a core AS is typically not long (e.g. local, regional, national provider, then core).¶

Each AS potentially receives PCBs for all down-path segments from the core to itself. While the number of distinct provider chains to the core is typically moderate, the multiplicity of links between provider ASes has multiplicative effect on the number of PCBs. Once this number grows above the maximum recommended best PCBs set size of 50, ASes trim the set of PCBs propagated. As the choice is among different ways to transit the local AS, operators are well equipped to choose among this set of PCBs. Ultimately, the number of PCBs received by an AS per propagation interval remains bounded by 50 for each parent link of an AS, and at most 50 PCBs per child link are propagated. The length of these PCBs, and thus the number of AS entries to be processed and stored, is expected to be moderate and not grow considerably with network size. The total resource overhead for beacon propagation is easily manageable even for highly connected ASes.¶

To illustrate this with some numbers, an AS with a rather large number of 100 parent links receives at most 5000 PCBs during a propagation interval. Assuming a generous average length of 10 AS entries for these PCBs, this corresponds to 50000 AS entries. Due to the variable length fields in AS entries, the sizes for storage and transmission cannot be predicted exactly, and we'll assume an average of 250 bytes per AS entry. At the shortest, and thus chattiest, recommended propagation interval of 5 seconds, this corresponds to an average bandwidth of around 2.5MB/s, and processing 10000 signature verifications per second. If the same AS has 1000 child links, the propagation of the beacons will require signing one new AS entry for each of the propagated PCBs for each link (at most 50 per link), that is at most 50000 signatures per propagation event. The total bandwidth for the propagation of these PCBs for all 1000 child links would, again very roughly, be around 25MB/s. All of these are manageable with even modest consumer hardware.¶

On a cold start of the network, path segments to each AS are discovered within a number of propagation steps proportional to the longest path. With a 5 second propagation period and a generous longest path of length 10, all path segments are discovered after 25 seconds on average. When all ASes start propagation interval just after they've received the first PCBs from any of their upstreams (see 'fast recovery'), the construction of a first path to connect each AS to the ISD core is accelerated.¶

When a new parent-child link is added to the network, the parent AS will propagate the available PCBs in the next propagation event. If the AS on the child side of the new link is a leaf AS, path discovery is thus complete after at most one propagation interval. Otherwise, child ASes at distance D below the new link, learn of the new link after at worst D further propagation intervals.¶

2.4.2. Inter-ISD Beaconing

In the inter-ISD core beaconing, PCBs are propagated omnidirectionally along core links. Each AS discovers path segments from itself to any other core AS. The number of distinct paths through the core network is typically very large. To keep the overhead manageable, at most 5 path segments to every destination AS are discovered, and the propagation frequency is slower than in the intra-ISD beaconing (at least 60 seconds between propagation events).¶

Without making strong assumptions on the topology of the core network, we can assume that shortest paths through real world, internet-like networks are relatively short; for example, the Barabási-Albert random graph model predicts a diameter of log(N)/log(log(N)) for a network with N nodes [BollRio-2000]. The average distance scales in the same way. We cannot assume that the selected PCBs are strictly shortest paths through the network, but it's reasonable to assume that they will not be very much longer than the shortest paths either.¶

With N the number of participating core ASes, an AS receives up to 5 * N PCBs per propagation interval per core link interface. For highly connected ASes, the number of PCBs received thus becomes rather large. In a network of 1000 ASes, a highly connected AS with 300 core links receives up to 1.5 million PCBs per propagation interval. Assuming an average PCB length of 6 and the shortest propagation interval of 60 seconds, this corresponds to roughly 150 thousand signature validations per second. In terms of bandwidth, this corresponds to very roughly 38MB/s. All of these are manageable on a present day small server or desktop machine. For much larger, more highly connected ASes, the path-discovery tasks of the control service can be distributed over many instances in order to increase the PCB throughput.¶

On a cold start of the network, full connectivity is obtained after a number of propagation steps corresponding to the diameter of the network. Assuming a network diameter of 6, this corresponds to roughly 3 minutes on average.¶

When a new link is added to the network, it will be available to connect two ASes at distances D1 and D2 from the link, respectively, at worst after a mean time (D1+D2)*T/2.¶

3.1.1. Terminating a PCB

Both the up- and down-segments end at the AS. One could therefore say that by transforming a PCB into a path segment, an AS "terminates" the PCB for this AS ingress interface and at this moment in time.¶

The control service of a non-core AS MUST perform the following steps to "terminate" a PCB:¶

1. The control service adds a new AS entry to the PCB. This new AS entry MUST be defined as follows:¶

   • The next AS MUST NOT be specified.¶

     • In Protobuf message format, this means that the value of the next_isd_as field in the ASEntrySignedBody component MUST be "0".¶

   • The egress interface in the hop field component MUST NOT be specified.¶

     • In Protobuf message format, this means that the value of the egress field in the HopField component MUST be "0".¶

2. If the AS has peering links, the control service MAY add corresponding peer entry components to the signed body of the AS entry - one peer entry component for each peering link that the AS wants to advertise. The egress interface ID in the hop field component of each added peer entry MUST NOT be specified.¶

   • In Protobuf message format, this means that the value of the egress field in the HopField component MUST be "0".¶

3. As a last step, the control service MUST sign the modified PCB and append the computed signature.¶

Note:¶

• For more information on the signed body component of an AS entry, see Section 2.2.1.4.2.¶

• For more information on a peer entry, see Section 2.2.1.7.¶

• For more information on the hop field component, see Section 2.2.1.6.¶

• For more information on signing an AS entry, see Section 2.2.1.4.3.¶

3.1.2. Transforming a PCB into an Up-Segment

Every registration period, the control service of a non-core AS performs the following steps to transform PCBs into up-segments:¶

1. The control service selects the PCBs that it wants to transform into up-segments from the candidate PCBs in the beacon store.¶

2. The 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 up-segments.¶

3. The control service now adds the newly created up-segments to its own path database.¶

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

3.1.3. Transforming a PCB into a Down-Segment

Every registration period, the control service of a non-core AS performs the following steps to transform PCBs into down-segments:¶

1. The control service selects the PCBs that it wants to transform into down-segments from the candidate PCBs in the beacon store.¶

2. The 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 down-segments.¶

3. The control service now registers the newly created down-segments with the control services of the core ASes that originated the corresponding PCBs. This is done by invoking the SegmentRegistrationService.SegmentsRegistration remote procedure call (RPC) in the control services of the relevant core ASes (see also Section 3.3).¶

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

4.1.1. Sequence of Lookup Requests

The overall sequence of requests to resolve a path SHOULD be as follows:¶

1. Request up-segments for the source endpoint at the control service of the source AS.¶

2. Request core-segments, which start at the core ASes that are reachable with up-segments, and end at the core ASes in the destination ISD. If the destination ISD coincides with the source ISD, this step requests core segments to core ASes that the source endpoint cannot directly reach with an up-segment.¶

3. Request down-segments starting at core ASes in the destination ISD.¶

4.1.2. Caching

For the sake of efficiency, the control service of the source AS SHOULD cache each returned path segment request. Caching ensures that path lookups are fast for frequently used destinations. The use of caching is also essential to ensure that the path-lookup process is scalable and can be performed with low latency.¶

In general, to improve overall efficiency, the control services of all ASes SHOULD do the following:¶

• Cache the returned path segments.¶

• Send requests in parallel when requesting path segments from other control services.¶

4.2.1. Use of Wildcard Addresses in the Lookup Process

Endpoints can use wildcard addresses to designate any core AS in path-segment requests. The segment-request handlers MUST expand these wildcard addresses and translate them into one or more actual addresses. Table 4 below shows who is responsible for what.¶

Note: For general information on the use of wildcard addresses in SCION, see Section 1.5.3.¶

1) Includes all core ASes for which an up-segment from the source AS exists.
2) Includes all core ASes in destination ISD with a down-segment to destination AS.¶

4.2.2. Segment-Request Handler of a Non-Core Source AS

When the segment-request handler of the control service of a non-core source AS receives a path segment request, it MUST proceed as follows:¶

1. Determine the requested segment type.¶

2. In the case of an up-segment request, look up matching up-segments in the path database and return them.¶

3. In the case of a core-segment request from a source core AS to a destination core AS:¶

   • Expand the source wildcard into separate requests for each reachable core AS in the source ISD.¶

   • For each core-segment request,¶

     • If possible, return matching core-segments from cache;¶

     • otherwise, request the core-segments from the control services of each reachable core AS at the source (start) of the core-segment. Add the retrieved core-segments to the cache.¶

4. In the case of a down-segment request:¶

   • Expand the source wildcard into separate requests for every core AS in the destination ISD (destination ISD refers to the ISD to which the destination endpoint belongs).¶

   • For each segment request,¶

     • If possible, return matching down-segments from cache;¶

     • otherwise, request the down-segment from the control services of the core ASes at the source (start) of the down-segment. Sending the request may require looking up core-segments to the source core AS of the down-segment. Add the retrieved down-segments to the cache.¶

4.2.3. Segment-Request Handler of a Core AS

When the segment-request handler of a core AS control service receives a path segment request, it MUST proceed as follows:¶

1. Validate the request:¶

   • The source of the path segment MUST be this core AS.¶

   • The request MUST either be¶

     • for a core-segment to a core AS in this ISD or another ISD, or¶

     • for a down-segment to an AS in this ISD.¶

2. If the destination is a core or wildcard address, then load matching core-segments from the path database and return.¶

3. Otherwise, load the matching down-segments from the path database and return.¶

Appendix "Path-Lookup Examples" shows by means of an illustration how the lookup of path segments in SCION works.¶

5.2.1. Path Hijacking through Interposition

An malicious AS M might try to manipulate the beaconing process between two neighbor ASes A and B, with the goal to hijack traffic to flow via M. If M can interpose itself on the path between A and B, then it could attempt several potential attacks:¶

• The adversary M could intercept and disseminate a PCB on its way from A to the neighboring AS B, and inject its own AS entry into the PCB toward downstream ASes.¶

• The adversary could modify the hop fields of an already existing path, in order to insert its own AS in the path.¶

• The adversary could fully block traffic between AS A and AS B, in order to force traffic redirection through an alternate path that includes its own AS.¶

The first type of attack is detectable and blocked by downstream ASes (e.g. B), because a PCB disseminated by AS A towards AS B contains the "Next ISD AS" field in the entry of AS A, pointing to AS B, and protected by A's signature. If M manipulates the PCB while in flight from A to B, then verification of the manipulated inbound PCBs will fail at AS B, as the adversary's PCBs cannot contain A's correct signature. The second type of attack is made impossible by the hop field's MAC, which protects the hop field's integrity and chains it with the previous hop fields on the path. The third type of attack generally cannot be prevented, however the alternate path would be immediately visible to endpoints, as traffic MUST include hop fields from AS M.¶

5.2.2. Creation of Spurious ASes and ISDs

An alternative scenario is when an adversary tries to introduce and spoof a nonexistent ASes. This would enable the adversary to send traffic with the spoofed AS as a source, allowing the adversary to complicate the detection of its attack and to plausibly deny the misbehavior.¶

However, spoofing a new AS requires a registration of that AS with the ISD core to obtain a valid AS certificate; otherwise the adversary cannot construct valid PCBs. As this registration includes a thorough check and authentication by a CA, this cannot be done stealthily, which defeats the original purpose.¶

Similarly to creating a fake AS, an adversary could try to introduce a new, malicious ISD. This involves the generation of its own TRC, finding core ASes to peer with, and convincing other ISDs of its legitimacy to accept the new TRC. Although this setup is not entirely impossible, it requires substantial time and effort, and may need the involvement of more than one malicious entity. Here, the "costs" of setting up the fake ISD may outweigh the benefits.¶

5.2.3. Peering Link Misuse

The misuse of a peering link by an adversary represents another type of attack. Consider the case where AS A wants to share its peering link only with one of its downstream neighbors, AS B, and therefore selectively includes the peering link only in PCBs sent to B. An adversary may now try to gain access to this peering link by prepending the relevant PCBs to its own path. For this, the adversary needs to be able to (1) eavesdrop on the link from A to B, and (2) obtain the necessary hop fields by querying a control service and extracting the hop fields from registered paths.¶

Even if an adversary succeeds in misusing a peering link as described above, SCION is able to mitigate this kind of attack: Each AS includes an egress interface as well as specific “next hop” information to the PCB before disseminating it further downstream. If a malicious entity tries to misuse a stolen PCB by adding it to its own segments, verification will fail upstream as the egress interface mismatches. Therefore, the peering link can only be used by the intended AS.¶

5.2.4. Manipulation of the Path-Selection Process

Endpoint path control is one of the main benefits of SCION compared to the current Internet, as SCION endpoints can select inter-domain forwarding paths for each packet. However, with the benefits of path selection comes the risk of endpoints selecting non-optimal paths. This section discusses some mechanisms with which an adversary can attempt to trick endpoints downstream (in the direction of beaconing) into choosing non-optimal paths. The goal of such attacks is to make paths that are controlled by the adversary more attractive than other available paths.¶

In SCION, overall path selection is the result of three steps. First, each AS selects which PCBs are further forwarded to its neighbors. Second, each AS chooses the paths it wants to register at the local control service (as up-segments) and at the core control service (as down-segments). Third, the endpoint performs path selection among all available paths resulting from a path lookup process. The following text describes attacks that aim at influencing the path-selection process.¶

These attacks are only successful if the adversary is located within the same ISD and upstream relative to the victim AS. It is not possible to attract traffic away from the core as traffic travels upstream towards the core. Furthermore, the attack may either be discovered downstream (e.g., by seeing large numbers of paths becoming available), or during path registrations. After detection, non-core ASes will be able to identify paths traversing the adversary AS and avoid these paths.¶

Announcing Large Numbers of Path Segments
This attack is possible if the adversary controls multiple (at least two) ASes. The adversary can create a large number of links between the ASes under its control, which do not necessarily correspond to physical links. This allows the adversary to multiply the number of PCBs forwarded to its downstream neighbor ASes. This in turn increases the chance that one or several of these forwarded PCBs are selected by the downstream ASes.¶

In general, the number of PCBs that an adversary can announce this way scales exponentially with the number of consecutive ASes the adversary controls. However, this also decreases their chance of being chosen by a downstream AS for PCB dissemination or by an endpoint for path construction, as these relatively long paths have to compete with other, shorter paths. Furthermore, both endpoints and downstream ASes can detect poorer quality paths in the data plane and switch to better paths.¶

Wormhole Attack
A malicious AS M1 can send a PCB not only to their downstream neighbor ASes, but also out-of-band to another, non-neighbor colluding malicious AS M2. This creates new segments to M2 and M2's downstream neighbor ASes, simulating a link between M1 and M2 which may not correspond to an actual link in the network topology.¶

Similarly, a fake path can be announced through a fake peering link between two colluding ASes, even if in different ISDs. An adversary can advertise fake peering links between the two colluding ASes, thus offering short paths to many destination ASes. Downstream ASes might have a policy of preferring paths with many peering links and thus are more likely to disseminate PCBs from the adversary. Similarly, endpoints are more likely to choose short paths that make use of peering links. In the data plane, whenever the adversary receives a packet containing a fake peering link, it can transparently exchange the fake peering hop fields with valid hop fields to the colluding AS. To avoid detection of the path alteration by the receiver, the colluding AS can replace the added hop fields with the fake peering link hop fields the sender inserted.¶

To defend against this attack, methods to detect the wormhole attack are needed. Per link or path latency measurements can help reveal the wormhole and render the fake peering link suspicious or unattractive. Without specific detection mechanisms these so-called wormhole attacks are unavoidable in routing.¶