Communications of the ACM

reach the destination, the host queries the local path server with the destination’s <ISD, AS> tuple. If the local path server has no cached down-segments, it will automatically query the destination AS’s core path server.

PCB and path-segment selection. The PCBs to propagate and path segments to register are selected by each AS based on a path-quality metric with the goal of identifying consistent, diverse, efficient, and policy-compliant paths. “Consistency” refers to the requirement that there exists at least one property along which the path is uniform (such as an AS capability like anonymous forwarding) or link property (such as low latency). “Diversity” refers to the set of paths that are announced over time, being as path-disjoint as possible to provide high-quality multipath options. “Efficiency” refers to the length, bandwidth, latency, utilization, and availability of a path, where more-efficient paths are naturally preferred.

ASes discover path segments leading to core ASes that enable an AS to communicate with the ISD core; Figure 2a outlines path segments from ASes A, B, C, D, and E to the core. The beaconing process is asynchronous; that is, the PCB generation is local, based on a per-AS timer, and PCBs are not propagated immediately upon arrival.

Paths are represented at AS-level granularity, which by itself is insufficient for fine-grain path diversity; ASes often have several diverse connection points, and a disjoint path is possible despite the AS sequence being identical. For this reason, SCION encodes AS ingress and egress interfaces as part of the path, exposing a finer level of path diversity. Figure 3 outlines this feature; AS F receives two different PCBs via two different links from the core. Moreover, AS F uses two different links to send two different PCBs to AS G, each with the respective egress interfaces. AS G extends the two PCBs, forwarding both over a single link to its customer.

An important requirement of the architecture is that SCION also supports peering links between ASes. Consistent with AS policies in the current Internet, PCBs do not traverse peering links, though peering links are announced, along with a regular path in a PCB. Figure 3 outlines how AS F includes its two peering links in the PCB. If the same peering link is announced in two path segments, then the peering link can be used to shortcut the end-to-end path without going through the core. SCION also supports peering links that cross ISD boundaries, highlighting the importance of SCION’s path-transpar-ency property; a source host knows the exact set of ASes and ISDs traversed during the delivery of each packet.

An AS typically receives several
PCBs representing path segments to
various core ASes. Figure 2a outlines
two path segments for AS D. We call a
path segment that leads toward an ISD
core an “up-segment” and a path seg-
ment that leads from the ISD core to
an AS a “down-segment,” though path
segments are typically bi-directional
and thus support packet forwarding
in both directions. More precisely,
up-segments and down-segments are
invertible; by flipping the sequence of
ASes, an up-segment is converted to
a down-segment and vice versa. Path
servers learn up-segments by extract-
ing them from PCBs they obtain from
the local beacon servers. Path servers
in core ASes also store core-segments
to reach other core ASes.
The beacon servers in an AS select
the down-segments through which the
AS prefers to be reached and register
them at the core path servers. When
links fail, segments expire or better
segments become available, the bea-
con servers keep updating the down-
segments registered for their AS.

Path lookup. To reach a remote destination, a host first queries a SCION name server to obtain the <ISD, AS, end-host address> triplet of the destination. The ISD and AS identifiers are needed to perform a path lookup, and the end-host address is used by the destination AS to deliver the packet to the destination host. To obtain up-segments to reach its ISD core, a host performs a path lookup at its local path server. To obtain down-segments to

Figure 3. Intra-ISD PCB propagation from the ISD core down to customer ASes. For the sake of illustration, the interfaces of each AS are numbered with consecutive integer values. In practice, each AS can choose any encoding for its interfaces; only the AS itself needs to understand its encoding.