Internet Engineering Task Force                                   G. Ren
Internet-Draft                                                    S. Liu
Intended status: Standards Track                                  X. Yin
Expires: 28 June 2025                                Tsinghua University
                                                        25 December 2024


    Inter-domain Source Address Validation based on AS relationships
           draft-rly-savnet-inter-domain-as-relationships-02

Abstract

   This draft introduces a distributed inter-domain source address
   validation scheme based on AS relationships.  It mainly describes
   this method from five aspects: the research background in related
   fields, introduction to the AS relationship classification and
   acquisition methods, the SAV system's architecture, typical use
   cases, and 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 28 June 2025.

Copyright Notice

   Copyright (c) 2024 IETF Trust and the persons identified as the
   document authors.  All rights reserved.











Ren, et al.               Expires 28 June 2025                  [Page 1]

Internet-Draft              Inter-domain SAV               December 2024


   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
   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  . . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Introduction to AS Relationships  . . . . . . . . . . . . . .   4
     2.1.  Major AS relationships  . . . . . . . . . . . . . . . . .   5
     2.2.  Incidental AS Relationships . . . . . . . . . . . . . . .   7
     2.3.  AS relationship acquisition methods . . . . . . . . . . .   9
       2.3.1.  Inference Algorithms  . . . . . . . . . . . . . . . .   9
       2.3.2.  Querying approach . . . . . . . . . . . . . . . . . .  10
   3.  Architecture of inter-domain SAV System based on AS
           relationships . . . . . . . . . . . . . . . . . . . . . .  10
     3.1.  Validation Router (VR)  . . . . . . . . . . . . . . . . .  11
     3.2.  Address Mapping Server (AMS)  . . . . . . . . . . . . . .  12
     3.3.  Methodology . . . . . . . . . . . . . . . . . . . . . . .  12
   4.  BGP Extension for Inter-domain SAV  . . . . . . . . . . . . .  12
     4.1.  Feasibility of BGP Extension  . . . . . . . . . . . . . .  12
     4.2.  Implementation of BGP Extension . . . . . . . . . . . . .  14
   5.  Multi-homing Scenarios  . . . . . . . . . . . . . . . . . . .  15
     5.1.  Multipoint Interconnection Scenario . . . . . . . . . . .  15
     5.2.  Multi-homing Scenario . . . . . . . . . . . . . . . . . .  15
   6.  Dynamic Scenario  . . . . . . . . . . . . . . . . . . . . . .  17
     6.1.  AS Relationships Change . . . . . . . . . . . . . . . . .  17
     6.2.  AS Prefixes Change  . . . . . . . . . . . . . . . . . . .  18
     6.3.  AS Network Topologies Change  . . . . . . . . . . . . . .  19
     6.4.  BGP Attributes Change . . . . . . . . . . . . . . . . . .  19
   7.  Considerations on Deployability . . . . . . . . . . . . . . .  20
     7.1.  Utilize existing information as much as possible  . . . .  20
     7.2.  Prefer to use and exchange more abstract information  . .  20
     7.3.  Balance accuracy, time and cost . . . . . . . . . . . . .  21
   8.  Next Step . . . . . . . . . . . . . . . . . . . . . . . . . .  21
   9.  Security Considerations . . . . . . . . . . . . . . . . . . .  21
   10. IANA Considerations . . . . . . . . . . . . . . . . . . . . .  21
   11. References  . . . . . . . . . . . . . . . . . . . . . . . . .  22
     11.1.  Normative References . . . . . . . . . . . . . . . . . .  22
     11.2.  Informative References . . . . . . . . . . . . . . . . .  22
   Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . .  24
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  24





Ren, et al.               Expires 28 June 2025                  [Page 2]

Internet-Draft              Inter-domain SAV               December 2024


1.  Background

   Various attacks continue to pose significant security threats to the
   Internet, and IP spoofing is critical.  Attackers frequently employ
   IP spoofing to launch DDoS attacks and disguise their actual
   identities.  Source address validation (SAV) can greatly relieve IP
   spoofing and mitigate DDoS attacks.

   The Source Address Validation Architecture (short for SAVA) proposed
   by [RFC5210] divides its SAV architecture into three levels: the
   access network, intra-domain, and inter-domain.  In SAV at the access
   network level, many researchers have made considerable progress and
   established several standards through discussion and collaboration.

   Researchers also proposed algorithms for inter-domain SAV.
   [RFC2827], [RFC3704], and [RFC8704] proposed uRPF algorithms that
   reverse routers' forwarding tables as their SAV rules.  They further
   proposed several variants based on this core idea to fit different
   scenarios. uRPF algorithms exhibit high convergence speed and low
   cost.  The SAVNET working group is devoted to improving the inter-
   domain SAV mechanism [inter-domain-sav-ps] and designing an SAV
   architecture using various information [inter-domain-sav-archt].
   Their scheme exhibits high accuracy.  The SIDRops working group
   proposed the BAR-SAV algorithm [sidrops-bar-sav].  It generates a
   permissible prefix list as SAV rules using BGP UPDATE messages, ASPA,
   and ROA objects in the RPKI.  It has medium accuracy.

   Though all existing methods have advantages, they have yet to become
   an effective and deployable standard.  Aiming to fix this gap, we
   propose a scheme with moderate accuracy, convergence speed, and cost.
   To implement it, we use AS relationships to abstract the inter-domain
   routing information.

   At the AS level, each AS owns some address prefixes and advertises
   them to neighbor ASes.  Through its advertisement, neighbor ASes know
   they can route traffic to these prefixes through it.  What's more,
   neighbor ASes also determine whether to propagate the received routes
   to their neighbor ASes according to AS relationships.  Thus, we can
   estimate each prefix's propagation, and infer approximate inter-
   domain routes with AS relationships and address prefixes.











Ren, et al.               Expires 28 June 2025                  [Page 3]

Internet-Draft              Inter-domain SAV               December 2024


   This scheme's inaccuracy comes from ignoring fine-grained routing
   information, such as BGP path attributes.  Ignoring them may cause
   routes to propagate beyond the intended scope, allowing more spoofed
   packets to pass.  Even one dropped legitimate packet may lead to
   serious Internet interruption, but a few passed forged packets cannot
   cause large-scale attacks.  As our scheme does not block more
   legitimate packets, it does not violate requirements for inter-domain
   SAV.

   This draft introduces a distributed inter-domain SAV scheme based on
   AS relationships.  Considering suggestions from other researchers,
   our scheme adopts a distributed SAV architecture without a
   centralized server in each AS or a newly designed protocol.  Instead,
   we extend the current BGP protocol and directly implement our SAV
   system on existing AS border routers.  Compared to the original
   scheme in [RFC5210], our scheme turns to a distributed system based
   on BGP extension due to considerations about upgrade costs.  We
   modified it to cover more AS relationships and analyze them in
   different scenarios.  We will explain its details in the following
   sections.

2.  Introduction to AS Relationships

   AS relationships are essentially business relationships between
   autonomous systems.  Some major relationships occupy the maximal
   proportion of all AS relationships, while other incidental
   relationships exist in particular situations.

   To formally describe AS relationships, we define some symbols in
   Table 1.





















Ren, et al.               Expires 28 June 2025                  [Page 4]

Internet-Draft              Inter-domain SAV               December 2024


      +===============+=============================================+
      |     Symbol    |                Symbol Meaning               |
      +===============+=============================================+
      |   Cus(AS_u)   |             Customer AS of AS_u             |
      +---------------+---------------------------------------------+
      |   Pro(AS_u)   |             Provider AS of AS_u             |
      +---------------+---------------------------------------------+
      |   Peer(AS_u)  |               Peer AS of AS_u               |
      +---------------+---------------------------------------------+
      |   Sib(AS_u)   |              Sibling AS of AS_u             |
      +---------------+---------------------------------------------+
      |  Hybrid(AS_u) | AS connected to AS_u in hybrid relationship |
      +---------------+---------------------------------------------+
      | PartCus(AS_u) |    Customer AS of AS_u in Partial Transit   |
      |               |                 relationship                |
      +---------------+---------------------------------------------+
      | PartPro(AS_u) |    Provider AS of AS_u in Partial Transit   |
      |               |                 relationship                |
      +---------------+---------------------------------------------+
      |     AS_uA     |              Position A of AS_u             |
      +---------------+---------------------------------------------+
      |    RI(AS_u)   |         Routing Information of AS_u         |
      +---------------+---------------------------------------------+
      |   EXRI(AS_1,  |  Routing Information exported from AS_1 to  |
      |     AS_2)     |                     AS_2                    |
      +---------------+---------------------------------------------+

             Table 1: Symbol definitions of formal descriptions

2.1.  Major AS relationships

   The major AS relationships include three different types: Provider-
   to-customer, Peer-to-peer, and Sibling-to-sibling relationships.  The
   definitions and descriptions of them are as follows.

   I    Provider-to-customer Relationship (Transit Relationship, P2C
        Relationship)

        The provider AS and the customer AS usually do not belong to the
        same organization, and a customer AS pays its provider AS for
        connectivity to the rest of the Internet.  Therefore, a provider
        AS does transit traffic for its customer ASes [infer-relatsh].
        The provider AS exports all its 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 the P2C relationship is as follows.




Ren, et al.               Expires 28 June 2025                  [Page 5]

Internet-Draft              Inter-domain SAV               December 2024


        EXRI(AS, Pro(AS)) = RI(AS) U RI(Cus(AS)) U RI(Sib(AS))

        EXRI(AS, Cus(AS)) = RI(AS) U RI(Cus(AS)) U RI(Sib(AS)) U
        RI(Peer(AS)) U RI(Pro(AS))

   II   Peer-to-peer Relationship (P2P Relationship)

        A pair of peer ASes usually do not belong to the same
        organization but agree to exchange traffic between their
        customers free of charge [infer-relatsh].  Each peer AS only
        exports the routing information of its customer ASes, its
        sibling ASes, and itself to the other AS.  The formal
        description of the P2P relationship is as follows.

        EXRI(AS, Peer(AS)) = RI(AS) U RI(Cus(AS)) U RI(Sib(AS))

   III  Sibling-to-sibling Relationship (S2S Relationship)

        Two sibling ASes are operated by the same institution.  The most
        common anomalies stem from recent acquisitions and mergers,
        suggesting that some AS pairs may have a sibling relationship.
        Each AS exports all its routes to its sibling ASes
        [charact-inet].  The formal description of the S2S relationship
        is as follows.

        EXRI(AS, Sib(AS)) = RI(AS) U RI(Cus(AS)) U RI(Sib(AS)) U
        RI(Peer(AS)) U RI(Pro(AS))

   Based on the above descriptions of the three major AS relationships,
   we can summarize their export rules in Table 2

       +=============+======+==========+==========+=========+======+
       |             | Peer | Provider | Customer | Sibling | Self |
       +=============+======+==========+==========+=========+======+
       |   to Peer   |      |          |    +     |    +    |  +   |
       +-------------+------+----------+----------+---------+------+
       | to Provider |      |          |    +     |    +    |  +   |
       +-------------+------+----------+----------+---------+------+
       | to Customer |  +   |    +     |    +     |    +    |  +   |
       +-------------+------+----------+----------+---------+------+
       |  to Sibling |  +   |    +     |    +     |    +    |  +   |
       +-------------+------+----------+----------+---------+------+

                      Table 2: Major Export Rule Table







Ren, et al.               Expires 28 June 2025                  [Page 6]

Internet-Draft              Inter-domain SAV               December 2024


2.2.  Incidental AS Relationships

   The major AS relationships introduced in Section 2.1 cannot cover all
   practical scenarios, and researchers have discovered other incidental
   AS relationships.  This draft illustrates only two relatively common
   incidental AS relationships, hybrid and partial transit
   relationships, as representatives.  However, it is significant to
   note that more incidental AS relationships may appear with the
   further development of Internet applications.

   I   Hybrid Relationship

       Two ASes with the hybrid relationship have different
       relationships at different interconnection points (e.g., P2C in
       one location and P2P elsewhere) [inferring-complex].  According
       to the definition, the AS relationship at a pair of
       interconnection points decides their export rules.

       To explain it clearly, we take an example of the hybrid of P2C
       and P2P.  We assume that AS 1 and AS 2 are in a hybrid
       relationship, and AS 1 is a customer of AS 2 at point A while
       they are peers at point B, as shown in Figure 1.


                               +------------------+
                               |       AS 1       |
                               +--+/A\+----+/B\+--+
                                    |        |
                              (P2C) |        | (P2P)
                                    |        |
                               +------------------+
                               |       AS 2       |
                               +------------------+

                  Figure 1: An example of Hybrid Relationships

       The formal descriptions of the hybrid relationship at points A
       and B are as follows.

       EXRI(AS_1A, Hybrid(AS_1A)) = RI(AS_1A) U RI(Cus(AS_1A)) U
       RI(Sib(AS_1A)) U RI(Peer(AS_1A)) U RI(Pro(AS_1A))

       EXRI(AS_1B, Hybrid(AS_1B)) = RI(AS_1B) U RI(Cus(AS_1B)) U
       RI(Sib(AS_1B))







Ren, et al.               Expires 28 June 2025                  [Page 7]

Internet-Draft              Inter-domain SAV               December 2024


       This example describes the route export rules between ASes in a
       hybrid relationship using the formal description of different AS
       relationships.  The key idea is to discuss and process different
       interconnection points separately.

   II  Partial Transit Relationship

       The Partial Transit relationship restricts the scope of a typical
       P2C relationship to the provider AS's peer ASes and customer ASes
       (but not provider ASes) [inferring-complex].  The formal
       description of the AS that provides partial connection services
       in the partial transit relationship is as follows.

       EXRI(AS, PartCus(AS)) = RI(AS) U RI(Cus(AS)) U RI(Sib(AS)) U
       RI(Peer(AS))

       The export rules of this AS to its customer ASes in the partial
       transit relationship are described in Table 3.

       +==================+====+==========+==========+=========+======+
       |                  |Peer| Provider | Customer | Sibling | Self |
       +==================+====+==========+==========+=========+======+
       |   to Partial-    | +  |          |    +     |    +    |  +   |
       |     Customer     |    |          |          |         |      |
       +------------------+----+----------+----------+---------+------+

                 Table 3: Exporting Rule of Partial-Customer

       According to the definition, the formal description of the AS
       that uses partial connection services as a customer in the
       partial transit relationship is as follows.  It is consistent
       with customer ASes' export rules in a typical P2C relationship.

       EXRI(AS, PartPro(AS)) = RI(AS) U RI(Cus(AS)) U RI(Sib(AS))

       The export rules of this ASto its provider ASes in the partial
       transit relationship are described in Table 4.

       +==================+====+==========+==========+=========+======+
       |                  |Peer| Provider | Customer | Sibling | Self |
       +==================+====+==========+==========+=========+======+
       |   to Partial-    |    |          |    +     |    +    |  +   |
       |     Provider     |    |          |          |         |      |
       +------------------+----+----------+----------+---------+------+

                 Table 4: Exporting Rule of Partial-Provider





Ren, et al.               Expires 28 June 2025                  [Page 8]

Internet-Draft              Inter-domain SAV               December 2024


2.3.  AS relationship acquisition methods

   Several methods can obtain AS relationships with existing data, such
   as BGP route information, IXP information, IRR database, and ASPA
   objects in RPKI et al.  Researchers divide these methods into two
   categories.  One is to infer relationships between ASes using
   specific network data, and the other is to query data directly to
   obtain AS relationships.

2.3.1.  Inference Algorithms

   Previous researchers have proposed various AS relationship inference
   algorithms using different strategies.

   The earliest AS relationship inferring algorithm was proposed by Gao,
   which speculates on AS relationships based on the Valley Free
   principle and observation of network phenomena [infer-relatsh].  Gao
   algorithm believes that the scale of provider AS is usually more
   immense than that of customer AS.  It also supposes that the scale of
   one AS is generally proportional to its degree in the AS topology
   graph.  Therefore, the Gao algorithm sorts all ASes according to
   their degrees and assigns each AS connection a relationship based on
   the sorting results.  Overall, the Gao algorithm is easy to implement
   and has low time complexity, but its accuracy is also low.  Threshold
   parameters used in the algorithm will affect the inference results of
   AS relationships.  Therefore, manual parameter selection requires
   much experience.  Many subsequent AS relationship inferring
   algorithms are also based on Gao's Valley Free principle.

   The AS Rank algorithm [as-rank] proposed by Luckie et al. does not
   rely on Gao's Valley Free principle but proposes three hypotheses as
   the algorithm foundation: firstly, multiple large provider ASes form
   peer-to-peer networks to provide global connectivity, building a set
   of ASes at the top of the hierarchy; Secondly, provider ASes will
   export its client ASes' routes to its provider ASes, and ASes outside
   the peer-to-peer network composed of large provider ASes need to
   connect with provider ASes to obtain global connectivity; Thirdly,
   the topological connections of AS can be represented using directed
   acyclic graphs.  Based on the three assumptions, the AS Rank
   algorithm can infer P2C and P2P relationships but cannot handle other
   complex AS relationships.  The AS Rank algorithm exhibits high
   accuracy and recall and can correctly infer 99.6% of P2C
   relationships and 98.7% of P2P relationships in validation
   experiments.  The AS relationships inferred with the AS Rank
   algorithm are still continuously updated on CAIDA.






Ren, et al.               Expires 28 June 2025                  [Page 9]

Internet-Draft              Inter-domain SAV               December 2024


   As the AS Rank algorithm has shown excessively high inferring
   accuracy on public datasets, the probabilistic algorithm Problink
   proposed by Jin et al. aims to improve the inferring accuracy in some
   complex situations [problink].  The Problink algorithm is based on a
   naive Bayesian framework and reveals crucial AS connection features
   derived from stochastically informative signals.  Problink exhibits a
   lower error rate than the AS Rank algorithm on the whole dataset,
   especially in complex AS relationship inferring situations.

   With the development and progress of AI technology, some researchers
   also attempted to apply advanced AI technologies to AS relationship
   inferring.  Varghese et al. use machine learning algorithms to train
   one AdaBoost model for inferring AS relationships [ml-pred].  The
   BGP2Vec algorithm embeds ASes in a vector space for relationship
   classification, referring to the NLP word embedding method Word2Vec
   [bgp2vec].  However, these methods have relatively low accuracy and
   interpretability, so they do not receive much attention.

2.3.2.  Querying approach

   Apart from the inference algorithms in Section 2.3.1, we can also
   directly obtain AS relationships by querying ASPA objects in RPKI.
   An ASPA object is a cryptographically verifiable attestation by a
   Customer AS (CAS) containing a list of its authorized provider ASes
   [sidrops-aspa].  Therefore, we can directly get an AS's provider ASes
   and customer ASes from ASPA objects.  Some researchers proposed the
   [ASRA] (Autonomous System Relationship Authorization) object based on
   ASPA.  ASRA objects can record more information about more complex AS
   relationships and may help us directly obtain accurate AS
   relationships in the future.

   In this draft, as several ASes implement inter-domain SAV together,
   we suppose all AS relationships are known.  However, it is apparent
   that even if the AS relationships are unknown, we can attain them
   using the above algorithms.

3.  Architecture of inter-domain SAV System based on AS relationships

   In this section, we propose the architecture of the inter-domain SAV
   system based on AS relationships.  In this SAV system, border routers
   in each AS generate, exchange, and update ASN validation rules until
   convergence.  These routers then generate prefix validation rules
   using the mapping from ASNs to address prefixes and use these rules
   to validate forwarding packets' source addresses.







Ren, et al.               Expires 28 June 2025                 [Page 10]

Internet-Draft              Inter-domain SAV               December 2024


   The proposed SAV system consists of two main components with
   different functions: the Validation Router (VR) and the Address
   Mapping Server (AMS).  Border routers in one AS act as its VRs, while
   AMS is a global infrastructure working for all ASes.  An example of
   our SAV system is shown in Figure 2.


                        +---------------------+
                        |         AS 1        |
                        +--+/\+---------+/\+--+
                            /             \
                           /    +++++++    \
                    (C2P) /     | AMS |     \ (C2P)
                         /      +++++++      \
                        /                     \
                  +------------+       +------------+
                  |    AS 2    |       |    AS 3    |
                  +------------+       +------------+

              Figure 2: An example of inter-domain SAV system

3.1.  Validation Router (VR)

   The Validation Routers (VR) are actually AS border routers.  They are
   responsible for generating validation rules and then using them to
   verify forwarding packets.  VRs communicate with AMS regularly,
   translating ASN validation rules into prefix rules.  They use the
   Neighbor Validation Rule Table as their prime data structure to
   implement these SAV functions.

   One VR's Neighbor Validation Rule Table stores all its neighbor ASes'
   helpful information, including their AS numbers, relationships with
   it, connected interfaces, corresponding ASN validation rules, and
   prefix rules.  The ASN and prefix validation rules record those
   permitted forwarding packets' source ASNs and IP addresses,
   respectively.  Therefore, VRs can use them to filter forged packets
   at the AS and prefix level.  Table 5 shows one specific example of
   the Neighbor Validation Rule Table.













Ren, et al.               Expires 28 June 2025                 [Page 11]

Internet-Draft              Inter-domain SAV               December 2024


    +===========+=====+=================+================+===========+
    | Interface | ASN | AS Relationship | Permitted ASNs | Permitted |
    |           |     |                 |                |  Prefixes |
    +===========+=====+=================+================+===========+
    |   Int 1   | ASN |       P2P       |     ASN 4      |   P4, P5  |
    |           |  1  |                 |                |           |
    +-----------+-----+-----------------+----------------+-----------+
    |   Int 2   | ASN |       P2C       |     ASN 5      |     P6    |
    |           |  2  |                 |                |           |
    +-----------+-----+-----------------+----------------+-----------+

          Table 5: An example of Neighbor Validation Rule Table

3.2.  Address Mapping Server (AMS)

   The Address Mapping Server (AMS) records the mapping from ASNs to IP
   address prefixes owned by ASes.  AMS responds to VRs' queries for
   ASNs' corresponding prefixes, helping them generate their prefix
   validation rules.  The mapping of IP address prefixes that AMS should
   maintain is now available from the Resource Public Key Infrastructure
   (RPKI).

3.3.  Methodology

   Neighbor VRs complete validation rule exchanges by advertising their
   rules and receiving others' rules.  Like route advertisement, VRs
   advertise their SAV rules to their neighbors when establishing
   connections or updating SAV rules.  Each VR initially advertises the
   origin ASNs of all legitimate packets it can send.  When receiving
   ASNs advertised by neighbors, VRs check whether its Neighbor
   Validation Rule Table needs updating.  If VRs update some rules, they
   advertise new rules to related neighbors according to export rules
   between different AS relationships.  Besides, VRs in the same AS need
   to communicate validation rules towards different neighbor ASes with
   each other through intra-domain connections.  In these ways, SAV
   rules in VRs gradually converge and build up filters for spoofing
   packets.

4.  BGP Extension for Inter-domain SAV

4.1.  Feasibility of BGP Extension

   As [RFC4271] states, the primary function of a BGP speaking system is
   to exchange network reachability information with other BGP systems.
   Each router advertises route paths to networks it can reach.  After
   further propagation, each router establishes a routing table with BGP
   routes to its reachable networks.  Our SAV system uses BGP forwarding
   routes to approximate the reverse routes.  Those VRs can deploy it to



Ren, et al.               Expires 28 June 2025                 [Page 12]

Internet-Draft              Inter-domain SAV               December 2024


   calculate networks that can reach them.

   Routers do not regularly announce their routing tables but
   incrementally advertise them using BGP UPDATE messages when they are
   updated.  Our scheme calculates and updates SAV rules at the AS
   level, taking AS relationships as the abstract of inter-domain
   routing information.  After convergence, only when increases,
   decreases, or changes occur to their AS relationships with neighbor
   VRs do SAV update rules and advertise the updates to neighbor VRs.
   At this time, changes also occur to their routing tables, and they
   should send UPDATE messages to neighbor VRs.  Therefore, VRs can
   advertise SAV updates with BGP UPDATE messages.

   All these allow us to implement the SAV system with the existing
   route mechanism and use BGP UPDATE messages to advertise SAV rule
   updates.

                 +-----------+        +-----------+
                 | AS 1 (P1) |<--P2C--| AS 2 (P2) |
                 +-----------+        +-----------+

                        Figure 3: Initial AS network

   Take the simple network displayed in Figure 3 as an example.
   Initially, a BGP connection is established between AS 1 and AS 2's
   VRs.  Then, AS 1 and AS 2 advertise their routes for prefixes P1 and
   P2 with BGP UPDATE messages.  If deploying our SAV system, AS 1 and
   AS 2 also advertise that they can send data packets originating from
   AS 1 and AS 2 in these UPDATE messages.

                 +-----------+        +-----------+
                 | AS 1 (P1) |<--P2C--| AS 2 (P2) |
                 +-----------+        +-----------+
                       |
                       | (P2C)
                       V
                 +-----------+
                 | AS 3 (P3) |
                 +-----------+

                        Figure 4: Updated AS network










Ren, et al.               Expires 28 June 2025                 [Page 13]

Internet-Draft              Inter-domain SAV               December 2024


   If AS 3 is newly added and connected to AS 1, like in Figure 4, AS 1
   will have a new route for P3 through AS 3 and a new SAV rule from AS
   3.  We discuss the connection between AS 1 and AS 2, considering
   export rules and their AS relationships.  AS 1's routing table is
   updated, so it advertises updated routes for P3 to AS 2 with an
   UPDATE message.  AS 1's SAV rules also change, so it advertises
   updated SAV rules from AS 3 to AS 2 with this UPDATE message.

   Therefore, while BGP UPDATE messages propagate the inter-domain
   routes, our SAV system can utilize it to complete the advertisement
   of SAV rules.

4.2.  Implementation of BGP Extension

   To achieve the goal, we can slightly modify BGP UPDATE messages,
   enabling it to complete the advertisement of SAV rules when
   advertising updated routes.

   Every BGP UPDATE message contains withdrawn routes, path attributes,
   and Network Layer Reachability Information.  The path attribute part
   is a sequence of BGP path attributes and can carry many attributes in
   one message.  Each path attribute is recorded as a variable-length
   triple <Type, Length, Value>, allowing for various information
   transfers.  What's more, new path attributes can be registered after
   IANA allocates new type codes to them.

   All these above allow us to design a new BGP path attribute to
   exchange SAV rules between AS border routers in the form of ASN sets.
   With this attribute, an AS border router deploying SAV can use BGP
   UPDATE messages to advertise corresponding SAV rule updates while
   updating routing information.  We name it SAV_INFO for now.

   SAV_INFO is a triple <attribute type, attribute length, attribute
   value> referring to the format proposed in [RFC4271].  The attribute
   type is a two-octet field containing some flags and an allocated type
   code.  The value field records SAV rules containing one or more AS
   numbers, each encoded as a 2-octet length field.  The length field is
   the length of the value field in octets, occupying one or two octets.

   We will discuss more details of the modified message format in
   follow-up drafts.










Ren, et al.               Expires 28 June 2025                 [Page 14]

Internet-Draft              Inter-domain SAV               December 2024


5.  Multi-homing Scenarios

   In this section, we utilize some use cases as examples to show that
   our inter-domain SAV system performs well in multi-homing scenarios.
   Our SAV scheme performs a lower false positive rate than existing
   mechanisms, filling the research gap proposed in
   [inter-domain-sav-ps].

5.1.  Multipoint Interconnection Scenario

   In other particular multi-homing scenarios, our scheme can complete
   inter-domain SAV at the AS level.  Figure 5 presents a scenario of
   multipoint interconnection between ASes.  In this example, AS 1
   connects with AS 2 through two pairs of VRs.  AS 1 and AS 2 are in a
   hybrid relationship, and AS 2 is the customer of AS 2 at point 1
   while they are peers at point 2.

                   +----------------------+
                   |         AS 1         |
                   +---+/1\+------+/2\+---+
                         |          |            +-----+
                   (C2P) |    (P2P) |            | AMS |
                         |          |            +-----+
                   +----------------------+
                   |         AS 2         |
                   +----------------------+

             Figure 5: An example of multipoint interconnection

   If AS 1 has deployed the inter-domain SAV system based on AS
   relationships, VRs at points 1 and 2 will add AS 2 to their allowlist
   at the AS level.  Meanwhile, according to AS 2's address prefixes
   recorded in AMS, they will add all these prefixes to their allowlist
   at the prefix level.  At their interfaces facing AS 2, VRs at points
   1 and 2 use the prefix allowlists to filter incoming packets.

5.2.  Multi-homing Scenario

   In multi-homing scenarios, the SAV system based on AS relationships
   improves the validation accuracy in customer interfaces, filling the
   gap of false positives proposed in [inter-domain-sav-ps].










Ren, et al.               Expires 28 June 2025                 [Page 15]

Internet-Draft              Inter-domain SAV               December 2024


   We take Figure 6 as an example to analyze how our scheme solves the
   limited propagation of prefixes.  This figure presents a multi-homing
   scenario where uRPF mechanisms may lead to the problem.  In this
   scenario, AS 2 and AS 1 are providers of AS 3, and AS 1 is the
   provider of AS 2.  AS 3 adds the NO_EXPORT community attribute to all
   BGP advertisements to AS 2, preventing AS 2 from further propagating
   its prefixes.

                           +--------------------+
                           |        AS 1        |
                           +--+/\+--------+/\+--+
                               /           |
                       (C2P)  /            |
                 +--------------+          |       +-----+
                 |     AS 2     |          |       | AMS |
                 +--------+/\+--+          |       +-----+
                            \              |
                      (C2P)  \             |  (C2P)
                  NO_EXPORT   \            |
                           +--------------------+
                           |        AS 3        |
                           +--------------------+

               Figure 6: An example of multi-homing scenario

   When deploying uRPF mechanisms, the VR facing AS 2 in AS 1 may
   improperly block packets originating from AS 3.  If it deploys the
   SAV system based on AS relationships, it will generate validation
   rules using ASNs transmitted between VRs.  The NO_EXPORT attribute
   can not limit AS 2's propagation of AS 3 rules.  Therefore, the VR
   will allow those packets to pass, avoiding false positives.

   As for the problem of hidden prefixes, we solve it by specially
   setting the initial ASN sets advertised by each AS.  Under some
   circumstances, one AS may have particular settings and send packets
   with source addresses that it does not advertise, like direct server
   return (DSR).  If deploying our scheme, its VRs initially advertise
   the origin ASNs of all possible legitimate packets it can send.
   Therefore, these VRs will allow packets that match the specific
   configurations to pass, effectively avoiding false positives.











Ren, et al.               Expires 28 June 2025                 [Page 16]

Internet-Draft              Inter-domain SAV               December 2024


   Besides false positives, [inter-domain-sav-ps] also points out false
   negatives within AS customer cones.  Our scheme does not propose a
   targeted solution for this gap but does propose some ideas.  A system
   on the data plane for traffic monitoring and management may help with
   limiting attacks within customer cones.  What's more, in the SAVA
   architecture proposed in [RFC5210], access network and intra-domain
   SAV can prevent source address spoofing within AS and help to reduce
   attacks within customer cones.

6.  Dynamic Scenario

   This section utilizes some designed use cases to show how our inter-
   domain SAV system performs in different dynamic scenarios.  This SAV
   system handles updates at the AS level and ignores more fine-grained
   route updates.  It reduces rule update frequency at the cost of tiny
   false negatives, cutting down the SAV system's update overhead.

   We take the network shown in Figure 7 as an example before all
   changes happen.  In this example, AS 1 is AS 2 and AS 3's provider,
   and all ASes have deployed the inter-domain SAV system based on AS
   relationships.  When diverse changes occur to this network, we show
   the network after changes and discuss the updates of our inter-domain
   SAV system.


                         +------------------+
                         |     AS 1(P1)     |
                         +--+/\+------+/\+--+
                             /          \              +-----+
                     (C2P)  /            \  (C2P)      | AMS |
                           /              \            +-----+
               +--------------+        +--------------+
               |   AS 2(P2)   |        |   AS 3(P3)   |
               +--------------+        +--------------+

             Figure 7: An example network before changes happen

6.1.  AS Relationships Change

   Figure 8 displays the example network after AS relationships change.
   If the AS relationship between AS 1 and AS 2 changes from C2P to P2P,
   the VR in AS 1 facing AS 2 and the VR in AS 2 facing AS 1 will modify
   the AS relationships in their Neighbor Validation Rule Tables and
   remove previous SAV rules.  These VRs will actively advertise their
   new SAV rules to neighbors.  VRs further propagate the rules through
   VR connections until they come to a new convergence in the changed
   network.




Ren, et al.               Expires 28 June 2025                 [Page 17]

Internet-Draft              Inter-domain SAV               December 2024


                           +------------------+
                           |     AS 1(P1)     |
                           +--+/\+------+/\+--+
                               /          \              +-----+
                       (P2P)  /            \  (C2P)      | AMS |
                             /              \            +-----+
                 +--------------+        +--------------+
                 |   AS 2(P2)   |        |   AS 3(P3)   |
                 +--------------+        +--------------+

        Figure 8: The example network after AS relationships change

6.2.  AS Prefixes Change

   Figure 9 displays the example network after AS prefixes change.  If
   AS 3's IP address prefixes change from P3 to P4, VRs will modify the
   SAV information about AS 3 in their Neighbor Validation Rule Tables.
   Under this circumstance, VRs' ASN validation rules remain unchanged,
   but they will adjust prefix validation rules according to the new
   mapping recorded in AMS.

   In our inter-domain SAV system, VRs use ASNs as advertised validation
   rules.  VRs translate ASN rules into prefix rules with the mapping
   provided by AMS and do not further propagate prefix ones.  Therefore,
   AS prefixes change won't break achieved convergence.  In this
   example, the change of AS 3's prefixes does cause VRs to update their
   SAV information about AS 3.  However, all ASN rules remain unchanged,
   and VRs only update prefix rules about AS 3.


                           +------------------+
                           |     AS 1(P1)     |
                           +--+/\+------+/\+--+
                               /          \              +-----+
                       (C2P)  /            \  (C2P)      | AMS |
                             /              \            +-----+
                 +--------------+        +--------------+
                 |   AS 2(P2)   |        |   AS 3(P4)   |
                 +--------------+        +--------------+

           Figure 9: The example network after AS prefixes change










Ren, et al.               Expires 28 June 2025                 [Page 18]

Internet-Draft              Inter-domain SAV               December 2024


6.3.  AS Network Topologies Change

   Figure 10 displays the example network after the AS network topology
   changes.  If the AS connections change and AS 3 becomes AS 2's peer
   from AS 1's customer, AS 2 will add one new VR, and AS 3 will adjust
   its original VR.  After reconfigurations, added VR in AS 2 and
   adjusted VR in AS 3 will fill in their Neighbor Validation Rule
   Tables according to the latest network situation.  These VRs will
   actively advertise their new SAV rules to neighbors.  VRs further
   propagate the rules through VR connections until they come to a new
   convergence in the changed network.


                           +------------------+
                           |     AS 1(P1)     |
                           +--+/\+------------+
                               /                   +-----+
                       (C2P)  /                    | AMS |
                             /                     +-----+
                 +--------------+           +--------------+
                 |   AS 2(P2)   |-----------|   AS 3(P4)   |
                 +--------------+   (P2P)   +--------------+

     Figure 10: The example network after AS network topologies change

6.4.  BGP Attributes Change

   Figure 11 displays the example network after BGP attributes change.
   If the BGP attributes between AS 1 and AS 2 change while other
   information does not, all VRs in the network needn't update their SAV
   information.  In this example, AS 2 adds the NO_EXPORT community
   attribute to all BGP advertisements from it to AS 1, preventing AS 1
   from further propagating its prefixes.  Routing information
   propagated from AS 1 to AS 3 changes and no longer contains routes to
   AS 2.  However, our SAV system does not restrain the propagation of
   ASN validation rules from AS 3 to AS 2, so AS 3's ASN and prefix
   rules remain unchanged, as do other ASes'.

   The results indicate that our SAV scheme ignores fine-grained routing
   information changes because it handles AS connections rather than BGP
   routes.  As such processing neglects restrictions on BGP route
   advertisement, it may allow some forged traffic to pass but will not
   additionally block legitimate traffic. which meets SAV requirements.
   Such processing also improves our SAV system's stability and lessens
   SAV update overhead.






Ren, et al.               Expires 28 June 2025                 [Page 19]

Internet-Draft              Inter-domain SAV               December 2024


                           +------------------+
                           |     AS 1(P1)     |
                           +--+/\+------+/\+--+
                               /          \              +-----+
                       (C2P)  /            \  (C2P)      | AMS |
                   NO_EXPORT /              \            +-----+
                 +--------------+        +--------------+
                 |   AS 2(P2)   |        |   AS 3(P3)   |
                 +--------------+        +--------------+

         Figure 11: The example network after BGP attributes change

7.  Considerations on Deployability

7.1.  Utilize existing information as much as possible

   Using information beyond existing will inevitably incur additional
   costs due to its need for upgrades.  At the same time, it will
   improve the deployment requirements, which prevent SAV schemes'
   large-scale promotion.  Therefore, an easily deployable SAV scheme in
   real networks always utilizes existing information as much as
   possible.  Similarly, when existing facilities can provide certain
   services, deployable solutions always prefer to use them rather than
   establish new ones.

   For SAV schemes, existing information includes routing information,
   business relationships between different ASes, and the mapping from
   ASNs to IP address prefixes provided.  Existing facilities include
   RPKI and AS border routers.  Our scheme establishes the SAV system
   with these existing information and devices.

7.2.  Prefer to use and exchange more abstract information

   Unlike fine-grained concrete information, abstract information lacks
   details but fundamentally simplifies problems.  However, it can
   reduce computational costs and improve efficiency, which is more
   conducive to promoting SAV deployment.  When multiple SAV nodes
   collaborate, they can exchange abstract rules and generate fine-
   grained ones when setting prefix filters.

   As discussed above, AS relationships determine the routing
   information between ASes and are more abstract than that.  Therefore,
   our inter-domain SAV scheme uses AS relationships instead of routing
   information to calculate validation rules at the AS level.  It
   transmits ASNs between ASes instead of IP address prefixes and only
   generates prefix filtering rules with ASN validation rules at the
   end.




Ren, et al.               Expires 28 June 2025                 [Page 20]

Internet-Draft              Inter-domain SAV               December 2024


7.3.  Balance accuracy, time and cost

   When the network remains stable, directly generating the most
   accurate filtering rules during forwarding table establishment is the
   best idea.  However, the Internet often changes at different levels,
   which triggers validation rule fluctuations until they reconverge.
   We have discussed some changes and their impacts in Section 6.  Long
   convergence time is not conducive to providing validation support in
   a constantly changing network.  Therefore, an easily deployable
   validation scheme in the dynamic network should balance convergence
   time and accuracy.

   When rule calculation and deployment do not bring additional costs,
   using the most accurate algorithms is the most effective.  However,
   SAV schemes that need more data and calculations often have higher
   costs in real networks.  Trading excessive expenses for a slight
   accuracy improvement is an inappropriate choice.  Therefore, an
   easily deployable SAV scheme in practical situations should balance
   computational cost and accuracy.

   The above analyses of two examples indicate that different evaluation
   metrics may have hidden contradictions in practical networks, making
   it difficult to optimize them simultaneously.  Our scheme tries to
   balance accuracy, time, and cost.

8.  Next Step

   The current discussion and design have not covered some details.  We
   discuss the major and incidental AS relationships in Section 2 but do
   not consider other complex and minor ones.  With the rapid
   development of Internet applications, researchers may discover more
   incidental AS relationships that this draft does not cover.  In
   future research, we will further discuss this issue and work to
   propose incremental solutions for incidental AS relationships.

9.  Security Considerations

   The security considerations of our inter-domain source address
   validation scheme based on AS relationships are similar to those of
   [inter-domain-sav-archt].

10.  IANA Considerations

   This draft proposes using a new BGP attribute to carry SAV rules.
   The new BGP attribute needs an attribute type code assigned by IANA.
   We will put forward specific IANA considerations in a further draft
   about the BGP attribute implementation.




Ren, et al.               Expires 28 June 2025                 [Page 21]

Internet-Draft              Inter-domain SAV               December 2024


11.  References

11.1.  Normative References

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

   [RFC4271]  Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A
              Border Gateway Protocol 4 (BGP-4)", RFC 4271,
              DOI 10.17487/RFC4271, January 2006,
              <https://www.rfc-editor.org/info/rfc4271>.

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

11.2.  Informative References

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

   [inter-domain-sav-ps]
              Li, D., Wu, J., Liu, L., Huang, M., and K. Sriram, "Source
              Address Validation in Inter-domain Networks Gap Analysis,
              Problem Statement, and Requirements", Work in Progress,
              Internet-Draft, draft-ietf-savnet-inter-domain-problem-
              statement-05, 8 September 2024,
              <https://datatracker.ietf.org/doc/html/draft-ietf-savnet-
              inter-domain-problem-statement-05>.

   [inter-domain-sav-archt]
              Li, D., Wu, J., 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-11, 6 August
              2024, <https://datatracker.ietf.org/doc/html/draft-wu-
              savnet-inter-domain-architecture-11>.




Ren, et al.               Expires 28 June 2025                 [Page 22]

Internet-Draft              Inter-domain SAV               December 2024


   [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-ietf-
              sidrops-bar-sav-04, 1 September 2024,
              <https://datatracker.ietf.org/doc/html/draft-ietf-sidrops-
              bar-sav-04>.

   [sidrops-aspa]
              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-18, 25 June 2024,
              <https://datatracker.ietf.org/doc/html/draft-ietf-sidrops-
              aspa-profile-18>.

   [infer-relatsh]
              Gao, L., "On inferring autonomous system relationships in
              the Internet", December 2001,
              <https://ieeexplore.ieee.org/document/974527>.

   [as-rank]  Luckie, M., Huffaker, B., Dhamdhere, A., Giotsas, V., and
              K. claffy, "AS relationships, customer cones, and
              validation", October 2013,
              <https://dl.acm.org/doi/10.1145/2504730.2504735>.

   [problink] Jin, Y., Scott, C., Dhamdhere, A., Giotsas, V.,
              Krishnamurthy, A., and S. Shenker, "Stable and Practical
              AS Relationship Inference with ProbLink", February 2019,
              <https://www.usenix.org/system/files/nsdi19-jin.pdf>.

   [ml-pred]  Varghese, J. S. and L. Ruan, "A machine learning approach
              to edge type inference in Internet AS graphs", April 2016,
              <https://ieeexplore.ieee.org/document/7562048>.

   [bgp2vec]  Shapira, T. and Y. Shavitt, "Unveiling the Type of
              Relationship Between Autonomous Systems Using Deep
              Learning", June 2020,
              <https://ieeexplore.ieee.org/document/9110358>.

   [charact-inet]
              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>.






Ren, et al.               Expires 28 June 2025                 [Page 23]

Internet-Draft              Inter-domain SAV               December 2024


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

   [ASRA]     Geng, N., "Autonomous System Relationship Authorization",
              September 2023,
              <https://conference.apnic.net/56/assets/files/APJS642/
              autonomous-system-re_1694481446.pdf>.

Acknowledgements

   Thanks to Aijun Wang for his valuable comments and suggestions on
   this draft.

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 28 June 2025                 [Page 24]