Internet DRAFT - draft-rly-savnet-inter-domain-as-relationships
draft-rly-savnet-inter-domain-as-relationships
Internet Engineering Task Force G. Ren
Internet-Draft S. Liu
Intended status: Standards Track X. Yin
Expires: 25 April 2024 Tsinghua University
23 October 2023
Inter-domain Source Address Validation based on AS relationships
draft-rly-savnet-inter-domain-as-relationships-01
Abstract
This draft introduces an inter-domain source address validation
scheme based on relationships between interconnected ASes. This
scheme is mainly described from four aspects, namely the research
background in fields of source address validation and AS
relationships, introduction to the classification and acquisition
methods of AS relationships, the specific architecture of our inter-
domain source address validation system based on AS relationships,
and the considerations on deployability.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 25 April 2024.
Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
Ren, et al. Expires 25 April 2024 [Page 1]
Internet-Draft Inter-domain SAV October 2023
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Background . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Introduction to AS Relationships . . . . . . . . . . . . . . 5
2.1. Major AS relationships . . . . . . . . . . . . . . . . . 5
2.2. Incidental AS Relationships . . . . . . . . . . . . . . . 6
2.3. AS relationship acquisition methods . . . . . . . . . . . 7
2.3.1. Inference Algorithms . . . . . . . . . . . . . . . . 8
2.3.2. Querying approach . . . . . . . . . . . . . . . . . . 9
3. Architecture of Source Address Validation System . . . . . . 9
3.1. Static Architecture . . . . . . . . . . . . . . . . . . . 9
3.1.1. Validation Rules Generation Server (VRGS) . . . . . . 9
3.1.2. Validation Router (VRR) . . . . . . . . . . . . . . . 11
3.1.3. Resource Public Key Infrastructure (RPKI) . . . . . . 12
3.2. Update Circumstance . . . . . . . . . . . . . . . . . . . 12
3.2.1. Change of the AS relationship . . . . . . . . . . . . 12
3.2.2. Change of the topology of the network . . . . . . . . 15
3.2.3. Change of the routing information . . . . . . . . . . 17
3.2.4. Change of the prefixes of AS . . . . . . . . . . . . 19
4. Considerations on Deployability . . . . . . . . . . . . . . . 20
4.1. Utilize existing information as much as possible . . . . 20
4.2. Prefer to use and exchange more abstract information . . 20
4.3. Balance accuracy, time and cost . . . . . . . . . . . . . 21
5. Next Step . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6. Security Considerations . . . . . . . . . . . . . . . . . . . 22
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.1. Normative References . . . . . . . . . . . . . . . . . . 22
8.2. Informative References . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25
1. Background
Inter-domain Source Address Validation plays a significant role in
relieving the source IP address spoofing. Several algorithms with
different ideas have been proposed previously, some of which are
being applied nowadays. The major idea of the series of uRPF
algorithms [RFC2827] [RFC3704] [RFC8704], which have been written in
RFCs and become standard methods, is to reverse the existing
forwarding tables for source address validation, and then complement
and specify this scheme gradually based on different scenarios. The
SAVNET working group, which is devoted to improving the inter-domain
address validation mechanism now
[I-D.wu-savnet-inter-domain-problem-statement], mainly designs a
Ren, et al. Expires 25 April 2024 [Page 2]
Internet-Draft Inter-domain SAV October 2023
source address validation scheme based on detailed inter-domain
forwarding information [I-D.wu-savnet-inter-domain-architecture].
The BAR-SAV algorithm proposed by the SIDROPS working group generates
the permissible prefix list for SAV with BGP UPDATE messages, ASPA
and ROA objects in RPKI [I-D.sriram-sidrops-bar-sav]. Different from
all schemes above, this draft primarily introduces an inter-domain
source address validation solution based on AS relationships, with
the initial idea mentioned in [RFC5210].
[RFC5210] proposes Source Address Validation Architecture (short for
SAVA) which divides validation architecture into three different
levels, namely subnetwork access, intra-domain and inter-domain. Up
to now, progress have been made in validation mechanisms of all three
levels. Meanwhile, the original idea of our proposed inter-domain
source address validation scheme based on AS relationships has also
been proposed in [RFC5210]. With the development and progress of
technology, RPKI can serve as the server which provides the mapping
from AS numbers to IP prefixes in the design of [RFC5210]. There is
also more research support for AS relationship acquisition methods
and incidental AS relationship analysis. On the basis of these
technologies, we complete the refined scheme which covers some
typical incidental AS relationships, and analyze its handling method
in dynamic situations from some major network changes.
In absence of an effective RFC standard for inter-domain source
address validation which is easy to deploy, we hope to propose a
solution that meets requirements, has strong practicality and high
deployability. We hope the scheme can prevent most spoofing attacks
in a relatively concise way, and meet the requirements for effective
validation in most scenarios. The forwarding and backward tracing of
data packets are similar, so we propose a validation mechanism for
"best effort validation" referring to "best effort forwarding"
scheme, and an evaluation metric "validation cost-effectiveness".
Our scheme is expected to overcome the dilemma that some existing
schemes are too complex to deploy while some existing methods are
simple with high error rates, and achieve a compromise between
accuracy and simplicity. To this end, we propose an inter-domain
source address validation scheme based on AS relationships, which
extends single-point validation to multi-point collaboration to
obtain more abundant information so as to improve accuracy, and
selects AS level as the main analysis level to greatly reduce amount
of data processing so as to simplify the solution and improve
efficiency. We will explain the detailed evaluation metrics and
validation methods in the following sections.
The relationship between two ASes determines the export rules between
them. The export rules between two ASes , combined with the address
prefixes owned by each AS, nearly determine the routing information
Ren, et al. Expires 25 April 2024 [Page 3]
Internet-Draft Inter-domain SAV October 2023
exchanged between them. (Some BGP attributes affect whether to
export some information). This means the relationship between two
ASes nearly determines the routing information. Therefore, with the
AS relationships, we can design a framework for inter-domain address
validation at a more abstract level, to improve the simplicity of the
implementation of SAV mechanism. With the continuous advancement of
the Internet, many existing research provides feasibility support for
the study on inter-domain source address validation based on AS
relationships. With the current development of studies on AS
relationship, there are many methods to obtain the relationship
between two ASes. One is to derive AS relationships from existing
data with various algorithms. The other is to query ASPA objects in
RPKI directly for obtaining the P2C/C2P relationships. In this
draft, as several ASes volunteer to participate in inter-domain
source address validation, we assume that the relationships between
every two ASes are known to each other. And the existence of RPKI
provides a mapping from AS numbers to IP prefixes owned by the AS.
The studies mentioned above make it possible to infer routing
information between ASes directly.
Analyze the existing source address validation algorithms from four
aspects: accuracy, convergence speed, cost and whether to realize the
validation at a single point. uRPF algorithm has high convergence
speed and low cost, and is mainly performed at a single point, while
a multi-point collaborative expansion scheme is proposed. The scheme
of SAVNET using multiple information shows high accuracy, while it is
fulfilled with multi-point collaboration. BAR-SAV proposed by
SIDROPS is an algorithm with medium accuracy with multi-point
collaboration. On this basis, this draft hopes to propose a multi-
point validation scheme with moderate accuracy, speed of convergence
and cost , so we propose the source address validation scheme based
on AS relationships.
When performing inter-domain source address validation, we have a
higher tolerance for false filtering, because several illegal packets
with forged source address which are forwarded mistakenly won't cause
large-scale attacks. However, we have lower acceptance for false
blocking in order to prevent legitimate packets from being discarded,
which may cause communication interrupt. The inter-domain source
address validation scheme based on AS relationships proposed in this
draft, compared with algorithms with high accuracy, aims not to
increase false blocking rate, not to increase false filtering rate
greatly, but to save the deployment cost and validation cost
effectively and improve the convergence speed under dynamic
circumstances.
Ren, et al. Expires 25 April 2024 [Page 4]
Internet-Draft Inter-domain SAV October 2023
2. Introduction to AS Relationships
AS relationships are typically congruent with the business
relationships between the autonomous systems, so the definitions of
AS relationships are basically based on the business relationships.
Nowadays, some major relationships occupy the largest proportion of
all the AS relationships, while other incidental relationships exist
in special situations. In order to describe AS relationships
formally, some symbols are defined as follows.
As AS represents one autonomous system, Ori(AS), Cus(AS), Pro(AS),
Peer(AS), Sib(AS) represents itself, its customer AS, its provider
AS, its peer AS, its sibling AS respectively. PartCus(AS) and
PartPro(AS) represents the customer AS and the provider AS of AS in
partial transit relationship respectively. What's more, RI(AS)
represents the routing information of the autonomous system AS while
EXRI(AS1, AS2) represents the routing information exported to AS2
from AS1. The symbol U represents union operation.
2.1. Major AS relationships
Major AS relationships include three types of relationships, namely
P2C relationship, P2P relationship and S2S relationship. The
specific definitions and descriptions of them are as follows.
I Provider to customer relationship (Transit Relationship, P2C
Relationship)
A customer pays its provider for connectivity to the rest of the
Internet. Therefore, a provider does transit traffic for its
customers.[inferring-relationships] The provider and the
customer usually do not belong to the same organization. The
provider AS exports its all routing information to its customer
because its customer will pay for all the traffic, while the
customer AS only exports the routing information of its
customers, its siblings and itself to its provider. The formal
description of provider to customer relationship is as follows.
EXRI(AS,Pro(AS))=RI(Ori(AS)) U RI(Cus(AS)) U RI(Sib(AS))
EXRI(AS,Cus(AS))=RI(Ori(AS)) U RI(Cus(AS)) U RI(Pro(AS)) U
RI(Peer(AS)) U RI(Sib(AS))
II Peer to peer relationship (P2P Relationship)
A pair of peers agree to exchange traffic between their
respective customers free of charge.[inferring-relationships]
Two peers usually do not belong to the same organization. Each
Ren, et al. Expires 25 April 2024 [Page 5]
Internet-Draft Inter-domain SAV October 2023
peer AS exports only the routing information of its customers,
its siblings and itself to the other AS. The formal description
of peer to peer relationship is as follows.
EXRI(AS,Peer(AS))=RI(Ori(AS)) U RI(Cus(AS)) U RI(Sib(AS))
III Sibling to Sibling relationship (S2S Relationship)
Two siblings are operated by the same institution. The most
common anomalies seem to stem from recent acquisitions and
mergers, suggesting that some AS pairs may have a sibling
relationship. Each AS exports all of its routes to the other
AS. [characterizing-internet] The formal description of sibling
to sibling relationship is as follows.
EXRI(AS,Sib(AS))=RI(Ori(AS)) U RI(Cus(AS)) U RI(Pro(AS)) U
RI(Peer(AS)) U RI(Sib(AS))
Based on the description of the three relationships above, we can
summarize the export rule table for major AS relationships (shown in
Table 1).
+====================+======+==========+==========+=========+======+
| | Peer | Provider | Customer | Sibling | Self |
+====================+======+==========+==========+=========+======+
| Export to Peer | | | + | + | + |
+--------------------+------+----------+----------+---------+------+
| Export to Provider | | | + | + | + |
+--------------------+------+----------+----------+---------+------+
| Export to Customer | + | + | + | + | + |
+--------------------+------+----------+----------+---------+------+
| Export to Sibling | + | + | + | + | + |
+--------------------+------+----------+----------+---------+------+
Table 1: Major Exporting Rule Table
2.2. Incidental AS Relationships
The diverse interconnection scenarios in practice cannot be covered
completely by the major AS relationships introduced in Section 2.1,
and other incidental relationships also exist in the AS
interconnection network. Currently, we only illustrate hybrid
relationship and partial transit relationship which are relatively
common in this draft. But in fact, as Internet applications develop
further, and the specific applications become more complex, there may
be more types of incidental AS relationships.
I Hybrid relationship
Ren, et al. Expires 25 April 2024 [Page 6]
Internet-Draft Inter-domain SAV October 2023
Two ASes have different relationships at different
interconnection points (e.g. p2c in one location and p2p
elsewhere). [inferring-complex] So from the AS level, the routing
information exported from each other between ASes with hybrid
relationships, is the union of the routing information which
would be exported within each single relationship in the
relationship set which hybrid relationships contain.
II Partial transit relationship
This relationship restricts the scope of a p2c relationship to
the provider's peers and customers (but not providers).
[inferring-complex] The formal description with export rule table
of partial transit relationship is as follows.
EXRI(AS,PartCus(AS))=RI(Ori(AS)) U RI(Cus(AS)) U RI(Peer(AS)) U
RI(Sib(AS))
+==================+====+==========+==========+=========+======+
| |Peer| Provider | Customer | Sibling | Self |
+==================+====+==========+==========+=========+======+
| Export to | + | | + | + | + |
| Partial-Customer | | | | | |
+------------------+----+----------+----------+---------+------+
Table 2: Exporting Rule of Partial-Customer
EXRI(AS,PartPro(AS))=EXRI(AS,Peer(AS))=RI(Ori(AS)) U RI(Cus(AS))
U RI(Sib(AS))
+==================+====+==========+==========+=========+======+
| |Peer| Provider | Customer | Sibling | Self |
+==================+====+==========+==========+=========+======+
| Export to | | | + | + | + |
| Partial-Provider | | | | | |
+------------------+----+----------+----------+---------+------+
Table 3: Exporting Rule of Partial-Provider
2.3. AS relationship acquisition methods
There are several methods to obtain AS relationships with different
existed data, such as BGP route information, IXP information, IRR
database, ASPA information of RPKI and so on. These methods can be
divided into two categories. One is to infer relationships between
ASes using specific data in the network, and the other is to query
data directly to obtain AS relationships.
Ren, et al. Expires 25 April 2024 [Page 7]
Internet-Draft Inter-domain SAV October 2023
2.3.1. Inference Algorithms
Currently, according to the different strategies used by algorithms,
AS relationship inferring algorithms can be mainly divided into three
types, namely Network feature ranking Algorithms, Combinatorial
optimization Algorithms and Local determination
algorithms.[inference-classification]
The Network feature ranking Algorithms mainly use some
characteristics of the Internet to infer the relationships between
ASes. These methods first extract features of all the autonomous
domains, and ranks them according to the features from the largest to
the smallest. Then the methods determine all AS relationships using
the rule that high-ranking ASes are the providers of low-ranking
ASes, while ASes with similar rank are peers. Among all these
methods, the representative ones are Gao algorithm
[inferring-relationships], which utilizes the degree of AS in the
network topology as the feature, and Subramanian algorithm
[characterizing-internet]. This kind of algorithms are simple to
implement with low time complexity and low accuracy. What's more,
the extracting of representative features and the setting of
empirical parameters are key difficulties.
The Combinatorial optimization Algorithms are principally based on
the undirected graph abstracted from the Internet topology whose
nodes are abstracted from ASes and edges are from connections between
ASes. These algorithms usually solve combinatorial optimization
problems using mathematical approaches to assign values of
relationships between interconnected ASes. However, owing to the
high theoretical complexity of the accurate solutions, approximate
algorithms or random methods are commonly utilized to obtain the
approximate solutions. Erlebach algorithm [classifying-c2p] and
Battista algorithm [computing-relationships] are two examples of The
Combinatorial optimization Algorithms. This type of algorithms
basically have high theoretical complexity, and are complex to
implement with high time complexity and low accuracy.
The Local determination Algorithms mainly utilize a portion of the
determined AS relationships which already exist in the public
database or can be monitored by the monitor, combined with the
features of AS relationships and AS paths to deduce the rest AS
relationships of the Internet. This strategy is adopted by Xia
Algorithm [evaluation-inferences], which first filters out invalid
paths using Valley-Free principle and then speculates relationships
on the AS paths, and Shavitt algorithm [near-deterministic]. This
kind of methods are relatively simple to implement with relatively
low time complexity and high accuracy, with one premise that accurate
and available priori information has been extracted.
Ren, et al. Expires 25 April 2024 [Page 8]
Internet-Draft Inter-domain SAV October 2023
2.3.2. Querying approach
Apart from above inference algorithms, AS relationships can also be
obtained directly by querying the ASPA objects in RPKI. The ASPA
object is a cryptographically signed attestation by a Customer AS
(CAS) that another AS listed in the ASPA is a Provider. The content
of an ASPA identifies the Customer AS (CAS) as well as the Set of
Provider ASes (SPAS) that are authorized by the CAS to be its
Providers. [I-D.ietf-sidrops-aspa-profile] Therefore, we can get the
set of ASes which are in P2C/C2P relationship with one AS straightly
from ASPA objects in RPKI. On the basis of ASPA, some researchers
proposed [ASRA] (Autonomous System Relationship Authorization)
object, which can record more complex information of various AS
relationships. ASRA objects may provide support for us to obtain
accurate AS relationships directly in the future.
In this draft, as several ASes try to implement SAV together, we
suppose that the relationship between every two ASes can be known.
But it is apparent that even if the AS relationships are unknown,
they can be obtained using algorithms mentioned above.
3. Architecture of Source Address Validation System
3.1. Static Architecture
In this section, we will propose the architecture design of the
inter-domain source address validation system based on AS
relationships. The main validation idea of this system is to deploy
the prefix validation rule table on the boundary router of one AS and
use the rules to verify the source address of the forwarding packets.
And the prefix validation rule table is generated by the server
within the AS and then deployed on the boundary router. The
validation system designed by this draft mainly consists of three
parts with diverse functions, which are Validation Rules Generation
Server, Validation Router and Resource Public Key
Infrastructure(RPKI). Every AS has its own Validation Rules
Generation Server and Validation Router, while the Resource Public
Key Infrastructure is a global security infrastructure.
3.1.1. Validation Rules Generation Server (VRGS)
The Validation Rules Generation Server (VRGS for short) is
responsible for communicating with the VRGS of its connected ASes to
exchange their validation rules. VRGS also communicates with the
RPKI to obtain the IPv6 address prefix corresponding to the AS
number, and then generates the prefix validation rule table based on
the AS number validation rule table. What's more, VRGS communicates
with the Validation Router and sends the prefix validation rule table
Ren, et al. Expires 25 April 2024 [Page 9]
Internet-Draft Inter-domain SAV October 2023
to it for deployment. The VRGS stores the following data structure
so as to generate and record rules.
3.1.1.1. Neighbor AS Table
This table stores all the relevant information of the AS connected to
this AS. Each record in the table includes the AS number of the
neighbor AS, the relationship between it and this AS, and the AS
number validation rule set exported to this AS from it. The AS
number validation rule set actually records the valid source AS
number, that is, the source AS number of the packets which are
permitted to be delivered. This storage method of AS number
validation rules may cause the data redundance, but is more
convenient for VRGS to manage and update the validation rules. This
data structure is only stored in VRGS, and will change dynamically.
When any change occurs to the complete AS number validation rules of
this AS, which are actually the union of all the AS number validation
rule sets in this table, it is necessary to update the prefix
validation rule table stored in VRGS. The detailed information of a
specific example of one neighbor AS table is as follows.
+===========+=================+=======================+
| AS Number | AS Relationship | Permissible AS Number |
+===========+=================+=======================+
| ASN1 | P2P | ASN4 |
+-----------+-----------------+-----------------------+
| ASN2 | P2C | ASN5 |
+-----------+-----------------+-----------------------+
Table 4: An example of Neighbor AS Table
3.1.1.2. Static Exporting Rule Table
This table stores the export rules of major relationships between
different ASes. For this table, VRGS can first select the row based
on the relationship between this AS and the interconnected AS, and
then select the column based on the source of currently discussed
rules, so as to read out the value of the target cell quickly and
determine whether to export the discussed rules to the interconnected
AS. This data structure is only stored in VRGS, and is static data
which will not change with time. The detailed table content is as
follows.
Ren, et al. Expires 25 April 2024 [Page 10]
Internet-Draft Inter-domain SAV October 2023
+=============+======+==========+==========+=========+
| | Peer | Provider | Customer | Sibling |
+=============+======+==========+==========+=========+
| to Peer | | | + | + |
+-------------+------+----------+----------+---------+
| to Provider | | | + | + |
+-------------+------+----------+----------+---------+
| to Customer | + | + | + | + |
+-------------+------+----------+----------+---------+
| to Sibling | + | + | + | + |
+-------------+------+----------+----------+---------+
Table 5: Static Exporting Rule Table
3.1.1.3. Prefix Validation Rule Table
This table stores the set of valid source address prefixes, that is,
the set of the source address prefixes of packets which are allowed
to be delivered. The VRGS applies to the RPKI for the set of
prefixes corresponding to some AS numbers, and obtains the prefix
validation rule table with the AS number validation rule table. This
data structure is stored in both VRGS and VRR, and will change with
time dynamically. When the prefix validation rule table stored in
VRGS changes, VRGS should communicate with VRR and notify it to
update its prefix validation rule table accordingly. The detailed
information of a specific example of one neighbor AS table is as
follows.
+----------------------+---------------+
| Permissible Prefixes | Prefixes Set1 |
+----------------------+---------------+
Table 6: An example of Prefix
Validation Rule Table
3.1.2. Validation Router (VRR)
Validation Router (VRR for short) is a boundary router between two
interconnected ASes, with prefix validation rule table deployed on it
so as to verify the source address of the forwarding packets. VRR
needs to communicate with VRGS and update its validation rule table
to maintain the accuracy of validation. Prefix rule table is stored
in the VRR for validation, and the detailed description of it is made
above.
Ren, et al. Expires 25 April 2024 [Page 11]
Internet-Draft Inter-domain SAV October 2023
3.1.3. Resource Public Key Infrastructure (RPKI)
Resource Public Key Infrastructure (RPKI for short) records the
current mapping from AS numbers to IP address prefixes owned by the
AS. VRGS will communicate with RPKI and obtain the address prefixes
corresponding to some AS numbers, so as to generate the prefix
validation rule table in VRGS.
3.2. Update Circumstance
In this section, we will discuss the corresponding response and
possible problems of the architecture we design when some changes
occur to the inter-domain network. Four different change scenarios
will be discussed, namely the scenarios when AS relationships change,
the scenarios when the network topology changes, the scenarios when
the routing information of AS changes and the scenarios when the
prefixes one AS owns change. To facilitate a clear explanation on
the detailed situation, we will elaborate on it using representative
examples. The legends which will be used in the discussion are as
follows.
+--+ represents the border of one autonomous system, while ++++
represents the border of RPKI. The +||+ at the edge of one AS
represents a boundary router, that is, a validation router (VRR).
The |VRGS| written inside one AS represents a validation rules
generate server (VRGS). The line with an arrow which points from AS1
to AS2 means the connection from AS1 to AS2, while the text beside
the line shows the relationship from AS1 to AS2.
3.2.1. Change of the AS relationship
With occurrence of some business events between ASes, the
interconnected relationship between ASes may also change
correspondingly, though AS relationships do not change frequently.
When changes occur to the relationships between two ASes, VRGSs of
the two ASes both need to update the AS number validation rule set
recorded in Neighbor AS Table gradually. After updating the AS
number rule set, the VRGS regenerates the prefix rule table
accordingly. So when we discuss this scenario when AS relationships
change, we only focus on the analysis of changes in the AS number
validation rule set. In addition to the narrow sense of AS
relationship changes, the addition and reduction of connections
between ASes can both be considered as the board sense of AS
relationship changes and analyzed similarly.
Ren, et al. Expires 25 April 2024 [Page 12]
Internet-Draft Inter-domain SAV October 2023
+------------------+
| AS1 |VRGS1| |
+-+| |+------+| |+-+
/\ /\
/ ++++++ \
(C2P) / |RPKI| \ (C2P)
/ ++++++ \
+----+| |+----+ +----+| |+----+
| AS2 |VRGS2| | | AS3 |VRGS3| |
+-------------+ +-------------+
Figure 1: A specific AS network 1
+===========+=================+=======================+
| AS Number | AS Relationship | Permissible AS Number |
+===========+=================+=======================+
| ASN1 | self | ASN1 |
+-----------+-----------------+-----------------------+
| ASN2 | P2C | ASN2 |
+-----------+-----------------+-----------------------+
| ASN3 | P2C | ASN3 |
+-----------+-----------------+-----------------------+
Table 7: Neighbor AS Table of AS1
+===========+=================+=======================+
| AS Number | AS Relationship | Permissible AS Number |
+===========+=================+=======================+
| ASN2 | self | ASN2 |
+-----------+-----------------+-----------------------+
| ASN1 | C2P | ASN1,ASN3 |
+-----------+-----------------+-----------------------+
Table 8: Neighbor AS Table of AS2
+===========+=================+=======================+
| AS Number | AS Relationship | Permissible AS Number |
+===========+=================+=======================+
| ASN3 | self | ASN3 |
+-----------+-----------------+-----------------------+
| ASN1 | C2P | ASN1,ASN2 |
+-----------+-----------------+-----------------------+
Table 9: Neighbor AS Table of AS3
Ren, et al. Expires 25 April 2024 [Page 13]
Internet-Draft Inter-domain SAV October 2023
+------------------+
| AS1 |VRGS1| |
+-+| |+------+| |+-+
/\ /\
/ ++++++ \
(P2P) / |RPKI| \ (C2P)
/ ++++++ \
+----+| |+----+ +----+| |+----+
| AS2 |VRGS2| | | AS3 |VRGS3| |
+-------------+ +-------------+
Figure 2: AS network 1 after changes of relationships
+===========+=================+=======================+
| AS Number | AS Relationship | Permissible AS Number |
+===========+=================+=======================+
| ASN2 | self | ASN2 |
+-----------+-----------------+-----------------------+
| ASN1 | P2P | ASN1 |
+-----------+-----------------+-----------------------+
Table 10: Neighbor AS Table of AS2 after Updating
Then let's assume a scenario, and the detailed connections of all
ASes are displayed as Figure 1. Initially, the interconnection
relationship between AS1 and AS2 is P2C relationship, while the
interconnection relationship between AS1 and AS3 is P2C relationship.
After the convergence of validation rules, the Neighbor AS
Table stored in the VRGS of AS1, AS2 and AS3 are respectively shown
in Table 7, Table 8 and Table 9. After the change of relationship,
the interconnection relationship between AS1 and AS2 is transformed
to P2P relationship, and the interconnection relationship between AS1
and AS3 remains unchanged. According to the exporting rule table,
one AS won't export the validation rules of its customer AS to its
provider AS, so the exporting relationship between AS1 and AS2 has
changed, and relative validation rule tables need to be updated
gradually. After the update and convergence of validation rules, the
Neighbor AS Table in VRGS of AS2 is shown in Table 10, while the
Neighbor AS Table in VRGS of AS1 and AS3 remains the same in Table 7
and Table 9.
Ren, et al. Expires 25 April 2024 [Page 14]
Internet-Draft Inter-domain SAV October 2023
3.2.2. Change of the topology of the network
If the change of the topology of the network leads to a change of AS
relationships, then this scenario needs to be analyzed like the first
case. Therefore, we mainly discuss the scenario when the topology
changes but the AS relationships don't change in this section. Under
this circumstance, validation rules recorded in relative ASes won't
change, which means that the validation architecture ignores the
changes caused by changes in network topology granularity.
+------------------+
| AS1 |VRGS1| |
+-+|1|+------+|2|+-+
/\ /\
/ ++++++ \
(C2P) / |RPKI| \ (C2P)
/ ++++++ \
+----+| |+----+ +----+| |+----+
| AS2 |VRGS2| | | AS3 |VRGS3| |
+-------------+ +-------------+
Figure 3: A specific AS network 2
+------------------+
| AS1 |VRGS1| |
+-+|1|+------+|2|+-+
/\ /\
/ ++++++ \
(C2P) / |RPKI| \ (C2P)
/ ++++++ \
+----+| |+----+ +----+| |+----+
| AS3 |VRGS3| | | AS2 |VRGS2| |
+-------------+ +-------------+
Figure 4: AS network 2 after changes of network topology
Ren, et al. Expires 25 April 2024 [Page 15]
Internet-Draft Inter-domain SAV October 2023
+===========+=================+=======================+
| AS Number | AS Relationship | Permissible AS Number |
+===========+=================+=======================+
| ASN1 | self | ASN1 |
+-----------+-----------------+-----------------------+
| ASN2 | P2C | ASN2 |
+-----------+-----------------+-----------------------+
| ASN3 | P2C | ASN3 |
+-----------+-----------------+-----------------------+
Table 11: Neighbor AS Table of AS1
Now we assume such a specific scenario for analysis, whose detailed
connections of all ASes are shown in Figure 3. Initially, AS1 is
interconnected with AS2 through boundary router VRR1, while AS1 is
interconnected with AS3 through boundary router VRR2. At this point,
VRR1 should allow the address prefixes owned by AS2 to pass
theoretically, and VRR2 should allow the address prefixes of AS3 to
pass theoretically. But according to our design, the validation
rules deployed on VRR1and VRR2 permit address prefixes of AS2 and AS3
to be delivered. After the change of topology, AS2 is connected to
VRR2 and AS3 is connected to VRR1. And after this change, VRR1
should allow the address prefixes of AS3 to pass theoretically, and
VRR2 should allow the address prefixes of AS2 to pass theoretically.
But because the VRR corresponding to different connections are not
recorded, the Neighbor AS Table in VRGS of AS1 remains unchanged
(shown in Table 11) and the validation rules deployed on VRR1 and
VRR2 do not change.
Ren, et al. Expires 25 April 2024 [Page 16]
Internet-Draft Inter-domain SAV October 2023
In this scenario when the topology changes but the AS relationships
don't change, the AS number validation rules won't change in the
architecture designed in this draft. Based on the analysis of this
scenario, we find the reason which causes this result is that, one AS
may be connected to multiple ASes through multiple different boundary
routers, and as the AS topology connected to each VRR is different,
validation rules deployed on these VRRs are not the same
theoretically. However, in our validation scheme, VRGS won't bind
different AS interconnection relationships to its different VRRs, so
it won't store the prefix validation rule table corresponding to each
VRR. Instead, the VRGS will only record the prefix validation rule
table of the entire AS, and deploy the same validation rules on each
VRR. So in fact, the VRGS stores the union of all prefix validation
rule tables which should be deployed on each VRR respectively. Such
processing method makes our validation scheme ignore the changes of
network topology which do not cause the changes of AS relationships
without blocking legitimate traffic additionally, and allow some
forged traffic to pass. At the same time, because the method
decreases the frequency of updating validation rules, it also reduces
the update cost of our source address validation scheme.
3.2.3. Change of the routing information
When the routing information of one AS changes, if the root of this
change also causes the change of certain AS relationships, then the
ASes whose relationships with neighbor ASes have changed or ASes
which are affected indirectly by the change of AS relationships, need
to be analyzed like the first case. As for the ASes under the
situation when the AS relationships remain unchanged, or ASes which
are not affected by such changes in AS relationships, their
forwarding tables may change due to the influence, but their AS
number validation rule set don't change. We will mainly discuss the
second situations next.
Ren, et al. Expires 25 April 2024 [Page 17]
Internet-Draft Inter-domain SAV October 2023
+-------------------+
| External Network |
+-------+| |+-------+
/\
Forwarding Table 1 |
| |
+--+--------------+| |+-+
| AS1 |VRGS1| |
+-+| |+-----------+| |+-+
/\ /\
/ ++++++ \
(C2P) / |RPKI| \ (C2P)
/ ++++++ \
+----+| |+----+ +----+| |+----+
| AS2 |VRGS2| | | AS3 |VRGS3| |
+--+----------+ +----------+--+
| |
Forwarding Table 2 Forwarding Table 3
Figure 5: A specific AS network 3
+-------------------+
| External Network' |
+-------+| |+-------+
/\
Forwarding Table 1' |
| |
+--+--------------+| |+-+
| AS1 |VRGS1| |
+-+| |+-----------+| |+-+
/\ /\
/ ++++++ \
(C2P) / |RPKI| \ (C2P)
/ ++++++ \
+----+| |+----+ +----+| |+----+
| AS2 |VRGS2| | | AS3 |VRGS3| |
+--+----------+ +----------+--+
| |
Forwarding Table 2' Forwarding Table 3'
Figure 6: A specific AS network 3
Then we assume such a specific scenario for analysis, and its
detailed connections of all ASes are shown in Figure 5. Initially,
AS1 is connected to an external network whose forwarding table is
represented as Forwarding Table1, and the forwarding tables of AS2
and AS3 are represented as Forwarding Table2 and Forwarding Table3
Ren, et al. Expires 25 April 2024 [Page 18]
Internet-Draft Inter-domain SAV October 2023
respectively. The change of the external network makes the
forwarding table of AS1 change to Forwarding Table1'. Because AS1 is
connected to AS2 and AS3 respectively, the Forwarding tables of AS2
and AS3 are updated to Forwarding Table2' and Forwarding Table3'
under the influence of AS1. But in addition, because the change of
external network does not cause the changes in validation rules of
AS1, the validation rules of AS2 and AS3 won't change owing to the
influence.
Under the circumstance when the network routing information changes,
whether the validation rules of one AS change or not mainly depends
on whether it is affected by the change of AS relationships.
Therefore, even if one AS needs to update its validation rules, the
essence of the update actually comes from the change of AS
relationships, and the changes of routing information are only a
reflection in one aspect of the impact of the changes in AS
relationships.
3.2.4. Change of the prefixes of AS
A change in the set of address prefixes owned by one AS, means that
the mapping from AS numbers to sets of prefixes stored in RPKI
changes. When this change happens, the VRGS of each AS needs to
regenerate the prefix validation rule table based on the new mapping,
and deploy the new rule table on the VRR. Our scheme adopts the
polling update method. The VRGS within one AS initiatively queries
the RPKI at regular intervals, for the address prefix sets
corresponding to the AS numbers in the AS number validation rule set.
If the union of all these prefix sets change, the VRGS will update
its prefix validation rule table.
With RPKI, we can obtain the mapping of address prefixes. And in the
current RPKI architecture, whenever a holder of IP address space
wants to authorize an AS to announce, it first issues an end-entity
certificate with its own private key, and then issues a Route Origin
Authorization (short for ROA) with the private key of that EE
certificate, finishing the binding of the IP address prefixes to this
AS.[RFC6480] A ROA records the AS number and its authorized address
prefixes.[RFC6482] The ROA objects are stored in the repository of
RPKI [RFC6481] to facilitate the data synchronization by the relying
parties (short for RP) through rsync [RFC5781] or RRDP protocols
[RFC8182]. So the VRGS can utilize RPKI validator to obtain the
certificates, ROA objects and other data regularly from the
distributed repository to generate a local cache of RPKI data.
Therefore, the ROA objects of one target AS can be queried using the
AS number of it, and the set of IP address prefixes owned by this AS
can be obtained.
Ren, et al. Expires 25 April 2024 [Page 19]
Internet-Draft Inter-domain SAV October 2023
In summary, our design of inter-domain source address validation can
deal with the four circumstances of changing discussed above. In
some cases which can not be handled correctly, such as the scenarios
when the network topology changes, our design will only allow some
forged traffic to pass through mistakenly, but won't block legitimate
traffic additionally. The handle of the design meets our target that
the method should not increase false blocking rate or increase false
filtering rate greatly. And when changes occur, changes that are
more fine-grained than changes of AS relationships won't cause the
change of AS number validation rules, which can reduce the frequency
of rule changing effectively and improve the efficiency of
maintaining validation rules.
4. Considerations on Deployability
4.1. Utilize existing information as much as possible
Using information beyond existing that will inevitably incur
additional costs due to its need for global upgrades. At the same
time, it will improve the deployment requirements, which is not
conducive to the large-scale promotion of the validation scheme.
Therefore, a source address validation scheme which is easy to be
widely deployed in real networks always tends to utilize existing
information as much as possible. Similarly, when existing facilities
can provide certain services, deployable solutions always prefer to
utilize existing facilities. For the source address validation
schemes, existing information includes routing information, business
relationships between different ASes, and the mapping from AS numbers
to IP prefixes provided by RPKI. Our solution is to utilize the
existing AS relationship information to generate validation rules,
and use the mapping from AS numbers to IP prefixes provided by RPKI.
4.2. Prefer to use and exchange more abstract information
Compared to more fine-grained and concrete information, abstract
information, although distorted in details, can fundamentally
simplify and quickly solve problems. When using abstract information
to simplify problems, it is often possible to reduce the
computational cost of a solution while improving its efficiency,
which is more conducive to promoting the deployment of validation
solutions. In this case, when multiple nodes collaborate, fine-
grained rule information may not be transmitted among them, and each
node may not necessarily have fine-grained rule information from
other nodes. Ultimately, specific validation rules can be generated
using the abstract information. As stated earlier, AS relationships
basically determines the routing information between ASes. On this
basis, our scheme uses AS relationships which is more abstract
instead of routing information, perform validation rule calculation
Ren, et al. Expires 25 April 2024 [Page 20]
Internet-Draft Inter-domain SAV October 2023
at the granularity of AS relationships, passes AS numbers between
ASes instead of IP prefixes, and only generates prefix filtering
rules based on AS number validation rules at the end.
4.3. Balance accuracy, time and cost
When the Internet routing remains stable, generating the most
accurate filtering rules directly during the process of forwarding
table establishment is the best validation scheme. However, today's
Internet often undergoes various levels of changes, which will
trigger fluctuations in validation rules of different schemes until
they converge again, such as various changes and their impacts in
Section 3.2. Long convergence time is not conducive for a scheme to
providing effective validation support in a constantly changing
network. Therefore, in the dynamic network, an easily deployable
validation scheme requires a good balance between convergence time
and accuracy.
On the other hand, when the calculation and deployment of rules cause
almost no additional consumption, the most effective validation
schemes tend to use the most complex and accurate schemes. However,
in real networks, validation schemes which require more data and
complex computational processes often have higher costs. Trading
excessive expenses for a slight improvement in accuracy is an
inappropriate choice. Therefore, in practical situations, an easily
deployable validation scheme requires a good balance between the
computational cost and accuracy.
The analysis of above two examples indicates that there may be
contradictions, which are difficult to optimize simultaneously,
between different evaluation metrics due to the hidden correlation in
practical networks.
A new metric should be designed that can be called "validation cost-
effectiveness". Calculate the ratio of total accuracy and average
deployment cost, to reflect the validation cost-effectiveness in the
cost dimension. Calculate the ratio of total accuracy and average
convergence time under various changing scenarios, to reflect the
validation cost-effectiveness in the time dimension.
5. Next Step
In the current discussion and design, there are still some details
that have not been covered. We discuss the major and incidental AS
relationships in Section 2, but there are some more complex and minor
AS relationships which haven't been discussed. What's more, with the
rapid development of Internet applications, there may be other new
incidental AS relationships which are not covered in this draft. In
Ren, et al. Expires 25 April 2024 [Page 21]
Internet-Draft Inter-domain SAV October 2023
future research, we will further discuss this issue and work to
propose solutions that can incrementally handle incidental AS
relationships.
6. Security Considerations
The security considerations of our inter-domain source address
validation scheme based on AS relationships are similar to those of
[I-D.wu-savnet-inter-domain-architecture].
7. IANA Considerations
This document has no IANA requirements.
8. References
8.1. Normative References
[RFC8182] Bruijnzeels, T., Muravskiy, O., Weber, B., and R. Austein,
"The RPKI Repository Delta Protocol (RRDP)", RFC 8182,
DOI 10.17487/RFC8182, July 2017,
<https://www.rfc-editor.org/info/rfc8182>.
[RFC6481] Huston, G., Loomans, R., and G. Michaelson, "A Profile for
Resource Certificate Repository Structure", RFC 6481,
DOI 10.17487/RFC6481, February 2012,
<https://www.rfc-editor.org/info/rfc6481>.
[RFC6482] Lepinski, M., Kent, S., and D. Kong, "A Profile for Route
Origin Authorizations (ROAs)", RFC 6482,
DOI 10.17487/RFC6482, February 2012,
<https://www.rfc-editor.org/info/rfc6482>.
[RFC2827] Ferguson, P. and D. Senie, "Network Ingress Filtering:
Defeating Denial of Service Attacks which employ IP Source
Address Spoofing", BCP 38, RFC 2827, DOI 10.17487/RFC2827,
May 2000, <https://www.rfc-editor.org/info/rfc2827>.
[RFC3704] Baker, F. and P. Savola, "Ingress Filtering for Multihomed
Networks", BCP 84, RFC 3704, DOI 10.17487/RFC3704, March
2004, <https://www.rfc-editor.org/info/rfc3704>.
[RFC8704] Sriram, K., Montgomery, D., and J. Haas, "Enhanced
Feasible-Path Unicast Reverse Path Forwarding", BCP 84,
RFC 8704, DOI 10.17487/RFC8704, February 2020,
<https://www.rfc-editor.org/info/rfc8704>.
8.2. Informative References
Ren, et al. Expires 25 April 2024 [Page 22]
Internet-Draft Inter-domain SAV October 2023
[RFC5210] Wu, J., Bi, J., Li, X., Ren, G., Xu, K., Williams, M., and
RFC Editor, "A Source Address Validation Architecture
(SAVA) Testbed and Deployment Experience",
DOI 10.17487/rfc5210, June 2008,
<http://dx.doi.org/10.17487/rfc5210>.
[RFC5781] Weiler, S., Ward, D., and R. Housley, "The rsync URI
Scheme", RFC 5781, DOI 10.17487/RFC5781, February 2010,
<https://www.rfc-editor.org/info/rfc5781>.
[RFC6480] Lepinski, M. and S. Kent, "An Infrastructure to Support
Secure Internet Routing", RFC 6480, DOI 10.17487/RFC6480,
February 2012, <https://www.rfc-editor.org/info/rfc6480>.
[I-D.wu-savnet-inter-domain-problem-statement]
Wu, J., Li, D., Liu, L., Huang, M., Sriram, K., Qin, L.,
and N. Geng, "Source Address Validation in Inter-domain
Networks Gap Analysis, Problem Statement, and
Requirements", Work in Progress, Internet-Draft, draft-wu-
savnet-inter-domain-problem-statement-09, 27 June 2023,
<https://datatracker.ietf.org/doc/html/draft-wu-savnet-
inter-domain-problem-statement-09>.
[I-D.wu-savnet-inter-domain-architecture]
Wu, J., Li, D., Huang, M., Chen, L., Geng, N., Liu, L.,
and L. Qin, "Inter-domain Source Address Validation
(SAVNET) Architecture", Work in Progress, Internet-Draft,
draft-wu-savnet-inter-domain-architecture-04, 30 September
2023, <https://datatracker.ietf.org/doc/html/draft-wu-
savnet-inter-domain-architecture-04>.
[I-D.sriram-sidrops-bar-sav]
Sriram, K., Lubashev, I., and D. Montgomery, "Source
Address Validation Using BGP UPDATEs, ASPA, and ROA (BAR-
SAV)", Work in Progress, Internet-Draft, draft-sriram-
sidrops-bar-sav-02, 17 December 2022,
<https://datatracker.ietf.org/doc/html/draft-sriram-
sidrops-bar-sav-02>.
[I-D.ietf-sidrops-aspa-profile]
Azimov, A., Uskov, E., Bush, R., Snijders, J., Housley,
R., and B. Maddison, "A Profile for Autonomous System
Provider Authorization", Work in Progress, Internet-Draft,
draft-ietf-sidrops-aspa-profile-16, 10 July 2023,
<https://datatracker.ietf.org/doc/html/draft-ietf-sidrops-
aspa-profile-16>.
Ren, et al. Expires 25 April 2024 [Page 23]
Internet-Draft Inter-domain SAV October 2023
[inferring-relationships]
Gao, L., "On inferring autonomous system relationships in
the Internet", December 2001,
<https://ieeexplore.ieee.org/document/974527>.
[characterizing-internet]
Subramanian, L., Agarwal, S., Rexford, J., and R. H. Katz,
"Characterizing the Internet hierarchy from multiple
vantage points", June 2002,
<https://ieeexplore.ieee.org/document/1019307>.
[inferring-complex]
Giotsas, V., Luckie, M., Huffaker, B., and K. claffy,
"Inferring complex AS relationships", November 2014,
<https://dl.acm.org/doi/10.1145/2663716.2663743>.
[classifying-c2p]
Thomas, E., Alexander, H., and S. Thomas, "Classifying
customer-provider relationships in the Internet", July
2002, <https://www.research-collection.ethz.ch/
handle/20.500.11850/146759>.
[computing-relationships]
Battista, G. D., Patrignani, M., and M. Pizzonia,
"Computing the types of the relationships between
autonomous systems", July 2003,
<https://ieeexplore.ieee.org/document/1208668>.
[evaluation-inferences]
Xia, J. and L. Gao, "On the evaluation of AS relationship
inferences", November 2004,
<https://ieeexplore.ieee.org/document/1378209>.
[near-deterministic]
Weinsberg, U., Shavitt, Y., and E. Shir, "Near-
deterministic inference of AS relationships", June 2009,
<https://ieeexplore.ieee.org/document/5206358>.
[inference-classification]
Fan, Q., Yin, H., Lin, C., Dong, J., and W. Song,
"Inference Algorithm for Business Relationships in
Internet Autonomous Systems", April 2014,
<https://d.wanfangdata.com.cn/periodical/jsjxb201404019>.
[ASRA] Geng, N., "Autonomous System Relationship Authorization",
September 2023,
<https://conference.apnic.net/56/assets/files/APJS642/
autonomous-system-re_1694481446.pdf>.
Ren, et al. Expires 25 April 2024 [Page 24]
Internet-Draft Inter-domain SAV October 2023
Authors' Addresses
Gang Ren
Tsinghua University
Beijing
China
Email: rengang@cernet.edu.cn
Shuqi Liu
Tsinghua University
Beijing
China
Email: liu-sq23@mails.tsinghua.edu.cn
Xia Yin
Tsinghua University
Beijing
China
Email: yxia@tsinghua.edu.cn
Ren, et al. Expires 25 April 2024 [Page 25]
