Application-Layer Traffic Optimization J. Ros-Giralt Internet-Draft Qualcomm Europe, Inc. Intended status: Informational S. Yellamraju Expires: 27 April 2023 Qualcomm Technologies, Inc. Q. Wu Huawei L. M. Contreras Telefonica R. Yang Yale University K. Gao Sichuan University 24 October 2022 Bottleneck Structure Graphs in Multidomain Networks: Introduction and Requirements for ALTO draft-giraltyellamraju-alto-bsg-multidomain-00 Abstract This document proposes an extension to the base Application-Layer Traffic Optimization(ALTO) protocol to support the computation of bottleneck structure graphs [I-D.draft-giraltyellamraju-alto-bsg-requirements] under partial information. A primary application corresponds to the case of multi- domain networks, whereby each network domain is administered separately and lacks information about the other domains. A proposed border protocol is introduced that ensures each domain's independent convergence to the correct bottleneck substructure graph without the need to know private flow and topology information from other domains. Initial discussions are presented on the necessary requirements to integrate the proposed capability into the ALTO standard. About This Document This note is to be removed before publishing as an RFC. The latest revision of this draft can be found at https://giralt.github.io/draft-ietf-alto-gradientgraph-multidomain/ draft-giraltyellamraju-alto-bsg-multidomain.html. Status information for this document may be found at https://datatracker.ietf.org/doc/ draft-giraltyellamraju-alto-bsg-multidomain/. Ros-Giralt, et al. Expires 27 April 2023 [Page 1] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 Discussion of this document takes place on the Application-Layer Traffic Optimization Working Group mailing list (mailto:alto@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/alto/. Subscribe at https://www.ietf.org/mailman/listinfo/alto/. Source for this draft and an issue tracker can be found at https://github.com/giralt/draft-ietf-alto-gradientgraph-multidomain. 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 27 April 2023. Copyright Notice Copyright (c) 2022 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 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. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 4 3. Distributed Protocol to Compute the Bottleneck Structure of an AS . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . 4 3.2. Base Protocol Definitions . . . . . . . . . . . . . . . . 5 Ros-Giralt, et al. Expires 27 April 2023 [Page 2] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 3.3. Description of The Distributed Protocol . . . . . . . . . 7 3.4. Example: Global Convergence to the Correct Bottleneck Substructures . . . . . . . . . . . . . . . . . . . . . . 10 4. Requirements . . . . . . . . . . . . . . . . . . . . . . . . 18 4.1. Requirement 1: Computation of Bottleneck Substructures . 18 4.2. Requirement 2: Communication Between Neighboring ASs . . 18 5. Security Considerations . . . . . . . . . . . . . . . . . . . 19 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 7.1. Normative References . . . . . . . . . . . . . . . . . . 20 7.2. Informative References . . . . . . . . . . . . . . . . . 21 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 1. Introduction Bottleneck structures have been recently introduced in [G2-SIGCOMM] and [G2-SIGMETRICS] as efficient computational graphs that embed information about the topology, routing and flow information of a network. These computational graphs allow network operators and application service providers to compute network derivatives that can be used to make traffic optimization decisions. For instance, using the bottleneck structure of a network, a real-time communication (RTC) application can efficiently estimate the multi-hop end-to-end available bandwidth, and use that information to tune the encoder's transmission rate and optimize the user's Quality of Experience (QoE). Bottleneck structures can be used by the application to address a wide variety of communication optimization problems, including routing, flow control, flow scheduling, bandwidth prediction, and network slicing, among others. The ALTO draft [I-D.draft-giraltyellamraju-alto-bsg-requirements] introduces a new abstraction called Bottleneck Structure Graph (BSG) and the necessary initial requirements to integrate it into the existing ALTO services (Network Map, Cost Map, Entity Property Map and Endpoint Cost Map) exposing the properties of the bottleneck structure to help optimize application performance. When the ALTO server has full visibility of the network (i.e., all of its links, routes, and flows), the bottleneck structure can be computed using the algorithm introduced in [G2-SIGCOMM] [G2-SIGMETRICS]. In many scenarios, however, flows traverse multiple autonomous systems (ASs), and thus an ALTO server deployed in one AS may not have access to topological and flow information from the other domains. In this document, we describe a border protocol that allows ALTO servers in each AS to share their local path metrics dictionary (obtained via their local computation of the bottleneck structure graph) with their neighbouring ASs. Using the algorithm introduced in this document, this information alone is enough to ensure independent convergence by each AS to the correct bottleneck structure. This cooperative Ros-Giralt, et al. Expires 27 April 2023 [Page 3] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 solution presents similar properties as those found in well-known IETF protocols such as BGP, including the properties of scalability (since metrics only need to be shared on a per-path rather than per- flow basis, and only between neighboring ASs) and privacy (since no sensitive flow or topology information needs to be shared). We also present initial discussions on the necessary requirements to integrate the proposed capability into the ALTO standard. 2. Conventions and Definitions The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. 3. Distributed Protocol to Compute the Bottleneck Structure of an AS 3.1. Motivation In many real-world communication problems, data flows need to traverse multiple network domains, each one administered by a different operator that is responsible for (1) maintaining its own (and only its own) domain and (2) ensuring interoperability with the other domains. The quintessential example of multi-domain networks is the Internet, designed as a "network of interconnected networks", commonly known as _autonomous systems_ (ASs). In multi-domain networking environments, the operator in each domain only has visibility of its own network. In particular, the operator may know with precision the topology, the capacity of each link, the classes of quality of service (QoS) to serve, and the flows currently active in their network, but usually has no knowledge about the structure and state of any other network in the multi-domain environment. For instance, a data flow may need to cross two network domains, one operated by Operator O1 and another one operated by Operator O2. O1 has no visibility into the network operated by O2, while O2 has no visibility into the network operated by O1. Yet both networks need to cooperate in order to ensure the end-to-end QoS required by the flow. Bottleneck structures ([G2-SIGCOMM], [G2-SIGMETRICS]) are computational graphs that characterize the state of a communication network allowing human operators and machines to compute network derivatives very fast. These derivatives are core building blocks that enable the optimization of networks in a variety of problems including traffic engineering, routing, flow scheduling, capacity Ros-Giralt, et al. Expires 27 April 2023 [Page 4] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 planning, resilience analysis and network design. In order to compute the bottleneck structure of a network, information of the set of links traversed by each flow and the capacity of the links is required. In a multi-domain networking environment, however, such information is only known partially. For instance, in the example above, operator O1 can know the set of links traversed by a flow that reside in its own network, but may not know the set of links traversed by a flow that reside in the operator O2 network. Moreover, in many cases, such information is considered confidential for security, privacy and competitiveness reasons. In this document, we introduce a distributed protocol that addresses the above problem, enabling the computation of bottleneck structures under the scenario of partial information. In particular, an algorithm to compute the bottleneck structure of a network domain-- referred as the _bottleneck substructure_--is introduced that only requires a simple, scalable, and secure cooperative exchange of a path metric between neighboring autonomous systems to ensure global convergence to the correct state. Because network operators do have the ability to cooperate (provided that the exchange is simple, secure and guarantees privacy), the algorithm provides a practical methodology to optimize system-wide flow performance in a multi- domain network. 3.2. Base Protocol Definitions In this section, we briefly state the basic definition of bottleneck structure and introduce a few simple additional definitions that are necessary to understand the proposed protocol. For a more thorough description of the bottleneck structure framework, please refer to [I-D.draft-giraltyellamraju-alto-bsg-requirements]. Let L and F be the set of links and flows of a network, respectively. Its bottleneck structure is defined as follows: * Links and flows are represented by vertices in the graph. * There is a directed edge from a link l to a flow f if and only if flow f is bottlenecked at link l. * There is a directed edge from a flow f to a link l if and only if flow f traverses link l. Since the above definition corresponds to a graph, we use the terms _bottleneck structure_ and _bottleneck structure graph_ (BSG) interchangeably. Ros-Giralt, et al. Expires 27 April 2023 [Page 5] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 As shown in [I-D.draft-giraltyellamraju-alto-bsg-requirements], the BSG explains how perturbations in a network (e.g., the arrival or departure of a flow, the change in link capacity of a network, a link failure, etc.) propagate through the network. Mathematically, these perturbations can be understood as network derivatives. Because these derivates can be computed in the graph as simple delta calculations, the BSG enables a computationally scalable mechanism to optimize a network for a variety of use cases such as optimal path computation, bandwidth prediction, service placement, or network topology reconfiguration, among others ([G2-SIGCOMM], [G2-SIGMETRICS]). To achieve scalability, the protocol proposed in this document uses a version of the bottleneck structure graph called _Path Gradient Graph_ (PGG) (see [I-D.draft-giraltyellamraju-alto-bsg-requirements]). The PGG significantly reduces the size of the bottleneck structure graph by collapsing all the vertices of the flows that follow the same path into a single vertex called the _path vertex_. This technique leads to a more compact representation of the bottleneck structure graph (thus, significantly reducing computational complexity and memory storage) without affecting its accuracy. The following table introduces additional conventions and definitions that are used in the description of the distributed protocol in the next section: +=============+=====================================================+ | Notation|Description | +=============+=====================================================+ | A|The set of autonomous systems (ASs). | +-------------+-----------------------------------------------------+ | A_i|An AS in A, for i = 1, ..., |A|. | +-------------+-----------------------------------------------------+ | P(A_i) =|The set of active paths found in A_i. These are | | {p_1, ...,|paths for which there exist 0traffic flowing through | | p_|P(A_i)|}|them. | +-------------+-----------------------------------------------------+ | L(A_i) =|The set of active links found in A_i. These are | | {l_1, ...,|links for which there exists traffic flowing through | | l_|L(A_i)|}|them. | +-------------+-----------------------------------------------------+ | B|The global bottleneck structure graph. The form of | | |bottleneck structure used by the distributed | | |algorithm introduced in this document is the Path | | |Gradient Graph | | |[I-D.draft-giraltyellamraju-alto-bsg-requirements]. | +-------------+-----------------------------------------------------+ Ros-Giralt, et al. Expires 27 April 2023 [Page 6] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 | B.BW(p)|The bandwidth available to path p according to the | | |global bottleneck structure. This is always the | | |globally correct available bandwidth for path p. | +-------------+-----------------------------------------------------+ | B(A_i)|The bottleneck substructure of A_i, corresponding to | | |the subgraph of B that includes (1) the vertices | | |corresponding to the paths in P(A_i), (2) the | | |vertices corresponding to the links in L(A_i) and (3)| | |all the edges in B that connect them. If a path p in| | |P(A_i) is bottlenecked at a link not in L(A_i), then | | |B(P, L) includes a virtual link v with capacity equal| | |to B.BW(p) and a directed edge from v to p. | +-------------+-----------------------------------------------------+ | B(A_i).BW(p)|The bandwidth available to path p according to the | | |bottleneck substructure of A_i. This value is equal | | |to B.BW(p) when the distributed algorithm terminates.| +-------------+-----------------------------------------------------+ | PL(A_i)|A dictionary mapping every path in P(A_i) with the | | |subset of links in L(A_i) that it traverses. Note | | |that a path p can traverse one or more links not in | | |L(A_i). This reflects the notion of partial | | |information inherent to multi-domain networking | | |environments. That is, A_i may not know all the | | |links traversed by its active paths; in particular, | | |it only knows the subset of links that are in A_i. | +-------------+-----------------------------------------------------+ | C(A_i)|A dictionary mapping each link in A_i with its | | |capacity (in bps). | +-------------+-----------------------------------------------------+ | N(A_i)|The set of ASs that are neighbors of A_i. | +-------------+-----------------------------------------------------+ | PM(A_i)(p)|The current bandwidth available to path p as computed| | |by A_i. This is also known as the path metric of p | | |according to A_i. | +-------------+-----------------------------------------------------+ Table 1: Conventions and definitions used in the description of the distributed protocol. 3.3. Description of The Distributed Protocol The algorithm run by each autonomous system AS_i, 1 <= i <= |A|, consists of two independently executed events as follows: *Event: TIMER* Ros-Giralt, et al. Expires 27 April 2023 [Page 7] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 - Every s seconds, perform the following tasks: 1. B(A_i) = COMPUTE_BOTTLENECK_SUBSTRUCTURE(L(A_i), PL(A_i), C(A_i), PM(A_i)); 2. PM(A_i)(p) = B(A_i).BW(p), for all p in P(A_i); 3. For all A_j in N(A_i): 3.1 Send to A_j a PATH_METRIC_ANNOUNCEMENT message including (AS_i, PM(A_i)); *Event: PATH_METRIC_EXCHANGE* - Upon receiving a PATH_METRIC_ANNOUNCEMENT from AS_j carrying (AS_j, PM(A_j)): 1. PM(A_i)(p) = min{PM(A_i)(p), PM(A_j)(p)}, for all p in P(A_i) and p in P(A_j); As shown above, using a PATH_METRIC_ANNOUNCEMENT message, each AS periodically shares local path metric information with its neighbor ASs. It can be shown that this information alone is enough to ensure the convergence of all the participating ASs to their correct bottleneck substructure. (This is similar to the way BGP [RFC4271] sends _Update Messages_ to converge to a globally correct routing table by only exchanging local knowledge between neighbor ASs.) The procedure COMPUTE_BOTTLENECK_SUBSTRUCTURE is called from the TIMER event, and it is responsible for computing the bottleneck substructure. It can be proven that this procedure converges to the correct bottleneck substructure within a finite number of PATH_METRIC_ANNOUNCEMENT messages: *Procedure: COMPUTE_BOTTLENECK_SUBSTRUCTURE(L, PL, C, PM):* Ros-Giralt, et al. Expires 27 April 2023 [Page 8] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 1. i = 0; L_0 = L; PL_0 = PL; 2. While True: 2.1. B_i = COMPUTE_BOTTLENECK_STRUCTURE(L_i, PL_i, C); 2.2. If B_i.BW(p) == PM(p) for all path p in PL_i: 2.2.1. Break; 2.3. For all path p in PL_i such that B_i.BW(p) > PM(p): 2.3.1. If PL_i[p] has no virtual link: 2.3.1.1. Add a new virtual link v to the set of links PL_i[p]; 2.3.1.2. Add virtual link v to the set L_i; 2.3.2. Set C(v) = PM(p); 2.2. i = i + 1; 2.5. L_i = L_{i-1}; 2.6. PL_i = PL_{i-1}; 3. Return B_i; In the above procedure, the function COMPUTE_BOTTLENECK_STRUCTURE corresponds to the GradientGraph algorithm introduced in [G2-TREP]. The termination condition of this procedure is found in line 2.2.1: B_i.BW(p) == PM(p) for all path p in PL_i When the distributed algorithm converges to a final solution, the invocation of the procedure COMPUTE_BOTTLENECK_SUBSTRUCTURE returns immediately at this condition, and the path metric dictionaries for all the autonomous systems (PM(A_i) for 1 <= i <= |A|) no longer change, provided that the network state does not change. Further, upon termination, the distributed algorithm ensures that all the path metric values for all the autonomous systems are in agreement: PM(A_i)(p) == PM(A_j)(p) for all p in A_i, p in A_j, A_i in A and A_j in A We call this the _convergence condition_, to denote the fact that upon termination, all the path metrics from all the ASs are in agreement. Ros-Giralt, et al. Expires 27 April 2023 [Page 9] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 3.4. Example: Global Convergence to the Correct Bottleneck Substructures Figure 1 shows an example of a multidomain network with two autonomous systems, AS1 (the upper subdomain) and AS2 (the lower subdomain). Each link li is represented by a squared box and has a capacity ci. For instance, link l1 is represented by the top most squared box and has a capacity of c1=25 units of bandwidth. In addition, each path is represented by a line that passes through the set of links it traverses. For instance, path p6 traverses links l1, l2 and l3. Ros-Giralt, et al. Expires 27 April 2023 [Page 10] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 p3 p6 p1 | | | | | | +--+-+-+---+ | | | | | | | | +---+--- l1 | | | | c1=25 | | | | +--+-+-----+ | | | | +----- p2 | | | +--+-+-+---+ | | | | | ----+--+ | | | l2 | | | | c2=50 p4 ----+--+ | | | | | | | +--+-+-+---+ | | | AS1 | | | ............................................. AS2 | | | | | +----- | | +--+-+-----+ | | | | ----+--+ +-----+---- l3 | | c3=100 ----+----+ | | | | +----+-----+ | | +----+-----+ | | | l4 p5 ---+----+ | c4=75 | | | | +----------+ Figure 1: Multi-domain network example with two autonomous systems. The global bottleneck structure of this network corresponds to the following digraph (see [I-D.draft-giraltyellamraju-alto-bsg-requirements] for details on how a bottleneck structure is computed): Ros-Giralt, et al. Expires 27 April 2023 [Page 11] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 +------+ +------+ +------+ | | | | | | | p1 <--> l1 <---------------> p6 | | | | | +------------+ | +------+ +--^---+ | +---+--+ | | | | | | +--v---+ | | | | | | | p3 | | | | | | | +--+---+ | | | | | | | | +--v---+ | +------+ +--v---+ +------+ | <--+ | | | | | | | l2 <---->| p4 +---> l3 | | l4 | | | | | | | | | +--^---+ +------+ +--^---+ +---^--+ | | | +--v---+ | +------+ | | | | | | | | p2 | +-> p5 <-+ | | | | +------+ +------+ Figure 2: Global bottleneck structure of the network in Figure 1. Using the definitions introduced in Table 1, we have that the bottleneck substructure for AS1 and AS2 (that is, B(AS1) and B(AS2)) are as shown in Figure 3 and Figure 4, respectively. Ros-Giralt, et al. Expires 27 April 2023 [Page 12] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 +------+ +------+ +------+ | | | | | | | p1 <--> l1 <---------------> p6 | | | | | +------------+ | +------+ +--^---+ | +------+ | | | | +--v---+ | | | | | p3 | | | | | +--+---+ | | | | | +--v---+ | +------+ | <--+ | | | l2 <---->| p4 | | | | | +--^---+ +------+ | +--v---+ | | | p2 | | | +------+ Figure 3: B(AS1): Bottleneck substructure of AS1. +------+ +------+ | | | | | v1 <---------------> p6 | | | | | +------+ +--+---+ | | +------+ +------+ +--v---+ +------+ | | | | | | | | | v2 <--->| p4 +---> l3 | | l4 | | | | | | | | | +------+ +------+ +--^---+ +---^--+ | | | +------+ | | | | | +-> p5 <-+ | | +------+ Figure 4: B(AS2): Bottleneck substructure of AS2. Ros-Giralt, et al. Expires 27 April 2023 [Page 13] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 Note that according to the definition in Table 1, the bottleneck substructure of each AS corresponds to the subgraph of the global bottleneck structure B that includes all the vertices and edges in B that correspond to paths and vertices observed in the AS, plus an additional virtual link for each path that is bottlenecked outside the AS. In particular, AS2 has two virtual links v1 and v2 associated with paths p6 and p4, respectively, since these two paths are bottlenecked outside AS2. Similarly, AS1 has no virtual links because all of its paths are bottlenecked in its own domain. The objective consists in computing the bottleneck substructure of all the ASs in a distributed manner when each AS only has local information about the state of its links and paths. The distributed protocol introduced in this document provides a solution to this problem. Figure 5 and Figure 6 present the step-by-step execution of the distributed protocol as run by AS1 and AS2, respectively. For each iteration of the protocol, the state of the local path metric dictionary PM(AS) and of the bottleneck substructure B(AS) are presented. Ros-Giralt, et al. Expires 27 April 2023 [Page 14] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 Iteration 1: ------------ State of the path metric dictionary PM(AS1): +====================+ | PM(AS1)(p1) = 8.3 | +--------------------+ | PM(AS1)(p2) = 16.6 | +--------------------+ | PM(AS1)(p3) = 8.3 | +--------------------+ | PM(AS1)(p4) = 16.6 | +--------------------+ | PM(AS1)(p6) = 8.3 | +====================+ State of the bottleneck substructure B(AS1): +------+ +------+ +------+ | | | | | | | p1 <--> l1 <---------------> p6 | | | | | +------------+ | +------+ +--^---+ | +---+--+ | | | | +--v---+ | | | | | p3 | | | | | +--+---+ | | | | | +--v---+ | +------+ | <--+ | | | l2 <---->| p4 + | | | | +--^---+ +------+ | +--v---+ | | | p2 | | | +------+ Figure 5: Execution of the distributed protocol by AS1. Ros-Giralt, et al. Expires 27 April 2023 [Page 15] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 Iteration 1: ------------ State of the path metric dictionary PM(AS2): +====================+ | PM(AS2)(p4) = 33.3 | +--------------------+ | PM(AS2)(p5) = 33.3 | +--------------------+ | PM(AS2)(p6) = 33.3 | +====================+ State of the bottleneck substructure B(AS2): +------+ +------+ +------+ | | | | | | | p4 <--> l3 <---> p6 | | | | | + | +------+ +--^---+ +---+--+ | | +--v---+ | | | p5 | | | +--+---+ | | +--v---+ | | | l4 | | | +------+ Iteration 2: ------------ State of the path metric dictionary PM(AS2): +====================+ | PM(AS2)(p4) = 16.6 | +--------------------+ | PM(AS2)(p5) = 75 | +--------------------+ | PM(AS2)(p6) = 8.3 | +====================+ Ros-Giralt, et al. Expires 27 April 2023 [Page 16] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 State of the bottleneck substructure B(AS2): +------+ +------+ | | | | | v1 <--------------> p6 | | | | | +------+ +---+--+ | | +------+ +------+ +--v---+ +------+ | | | | | | | | | v2 <--->| p4 +---> l3 | | l4 | | | | | | | | | +------+ +------+ +--^---+ +---^--+ | | | +------+ | | | | | +-> p5 <-+ | | +------+ Figure 6: Execution of the distributed protocol by AS2. Note that at the end of the execution of the distributed algorithm, the convergence condition PM(A_i)(p) = PM(A_j)(p) for all p in A_i, p in A_j, A_i in A and A_j in A is satisfied, as shown in Table 2. +====+===========+===========+ | p | PM(A1)(p) | PM(A2)(p) | +====+===========+===========+ | p1 | 8.3 | -- | +----+-----------+-----------+ | p2 | 16.6 | -- | +----+-----------+-----------+ | p3 | 8.3 | -- | +----+-----------+-----------+ | p4 | 16.6 | 16.6 | +----+-----------+-----------+ | p5 | -- | 75 | +----+-----------+-----------+ | p6 | 8.3 | 8.3 | +----+-----------+-----------+ Table 2: Verification of the convergence condition. Ros-Giralt, et al. Expires 27 April 2023 [Page 17] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 4. Requirements This section provides a discussion on the necessary requirements to integrate the proposed distributed protocol into the ALTO standard. Throughout this discussion, we assume without loss of generality that each AS is managed by an ALTO server, and that each server only has visibility of the topology, links and flow state of the AS it is managing. We also assume that the TIMER and the PATH_METRIC_EXCHANGE events are executed by each ALTO server. An alternative architecture could consider executing these events in a separated engine, and have the ALTO server query this engine to obtain the final bottleneck structures, decoupling the distributed protocol from the ALTO standard. While this approach might be desirable in some cases, we currently omit it from this discussion since it is relatively simpler from an integration requirements standpoint. To implement the proposed distributed protocol using ALTO, two broad requirements are necessary: * Requirement 1: The capability for each ALTO server to compute bottleneck substructures of its own AS. * Requirement 2: The capability for each ALTO server to communicate with its neighboring ASs. 4.1. Requirement 1: Computation of Bottleneck Substructures The requirements for an ALTO server to compute the bottleneck substructure of its associated AS are the same as the requirements to compute the bottleneck structure in the case the network consists of a single autonomous system. These requirements are discussed in the Requirements Section of [I-D.draft-giraltyellamraju-alto-bsg-requirements]. Refer to this document for further details. 4.2. Requirement 2: Communication Between Neighboring ASs The TIMER event executed by each ALTO server needs to periodically transmit a PATH_METRIC_ANNOUNCEMENT message to its neighboring ASs. This leads to the following requirement: * Requirement 2.1: ALTO servers managing neighboring ASs need to be reachable to each other. * Requirement 2.2: The sharing of algorithmic state between ALTO servers requires extending the base ALTO protocol to support server-to-server communication semantics. Ros-Giralt, et al. Expires 27 April 2023 [Page 18] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 This requirement constitutes a new capability, since the current ALTO standard only supports client-to-server communication semantics [RFC7285]. We note that [I-D.draft-zhang-alto-oam-yang] discusses mechanisms for cross-ALTO server communication with the objective to facilitate Operations and Management (OAM) of multi-server deployments. The distributed protocol proposed in this document could be used as a use case to help drive the specifications of the inter-server communication protocol discussed in [I-D.draft-zhang-alto-oam-yang] or in any future ALTO RFCs that may focus on sharing of algorithmic state. 5. Security Considerations Future versions of this document may extend the base ALTO protocol, so the Security Considerations [RFC7285] of the base ALTO protocol fully apply when this proposed extension is provided by an ALTO server. The Bottleneck Structure Graph extension requires additional scrutiny on three security considerations discussed in the base protocol: Confidentiality of ALTO information (Section 15.3 of [RFC7285]), potential undesirable guidance from authenticated ALTO information (Section 15.2 of [RFC7285]), and availability of ALTO service (Section 15.5 of [RFC7285]). For confidentiality of ALTO information, a network operator should be aware that this extension may introduce a new risk: As the Bottleneck Structure information may reveal more fine-grained internal network structures than the base protocol, an attacker may identify the bottleneck link and start a distributed denial-of-service (DDoS) attack involving minimal flows to conduct in-network congestion. Given the potential risk of leaking sensitive information, the BSG extension is mainly applicable in scenarios where: * The properties of the Bottleneck Structure Graph do not impose security risks to the ALTO service provider; e.g., by not carrying sensitive information. * The ALTO server and client have established a reliable trust relationship, for example, operated in the same administrative domain, or managed by business partners with legal contracts and proper authentication and privacy protocols. * The ALTO server implements protection mechanisms to reduce information exposure or obfuscate the real information. Implementations involving reduction or obfuscation of the Ros-Giralt, et al. Expires 27 April 2023 [Page 19] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 Bottleneck Structure information SHOULD consider reduction/ obfuscation mechanisms that can preserve the integrity of ALTO information, for example, by using minimal feasible region compression algorithms [NOVA] or obfuscation protocols RESA [MERCATOR]. We note that these obfuscation methods are experimental and their practical applicability to the generic capability provided by this extension is not fully assessed. We note that for operators that are sensitive about disclosing flow- level information (even if it is anonymized), then they SHOULD consider using the Path Gradient Graph (PGG) or the QoS-Path Gradient Graph (Q-PGG) since these objects provide the additional security advantage of hiding flow-level information from the graph. For undesirable guidance, the ALTO server must be aware that, if information reduction/obfuscation methods are implemented, they may lead to potential misleading information from Authenticated ALTO Information. In such cases, the Protection Strategies described in Section 15.2.2 of [RFC7285] MUST be considered. For availability of ALTO service, an ALTO server should be cognizant that using Bottleneck Structures might have a new risk: frequently querying the BSG service might consume intolerable amounts of computation and storage on the server side. For example, if an ALTO server implementation dynamically computes the Bottleneck Structure for each request, the BSG service may become an entry point for denial-of-service attacks on the availability of an ALTO server. To mitigate this risk, an ALTO server may consider using optimizations such as precomputation-and-projection mechanisms [MERCATOR] to reduce the overhead for processing each query. An ALTO server may also protect itself from malicious clients by monitoring the behaviors of clients and stopping serving clients with suspicious behaviors (e.g., sending requests at a high frequency). 6. IANA Considerations Future versions of this document may register new entries to the ALTO Cost Metric Registry, the ALTO Cost Mode Registry, the ALTO Domain Entity Type Registry and the ALTO Entity Property Type Registry. 7. References 7.1. Normative References [I-D.draft-giraltyellamraju-alto-bsg-requirements] Ros-Giralt, J., Yellamraju, S., Wu, Q., Contreras, L. M., Yang, Y. R., and K. Gao, "Supporting Bottleneck Structure Graphs in ALTO: Use Cases and Requirements", Work in Ros-Giralt, et al. Expires 27 April 2023 [Page 20] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 Progress, Internet-Draft, draft-giraltyellamraju-alto-bsg- requirements-03, 23 September 2022, . [I-D.draft-zhang-alto-oam-yang] Zhang, J., Dhody, D., Gao, K., and R. Schott, "A Yang Data Model for OAM and Management of ALTO Protocol", Work in Progress, Internet-Draft, draft-zhang-alto-oam-yang-02, 7 March 2022, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [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, . [RFC7285] Alimi, R., Ed., Penno, R., Ed., Yang, Y., Ed., Kiesel, S., Previdi, S., Roome, W., Shalunov, S., and R. Woundy, "Application-Layer Traffic Optimization (ALTO) Protocol", RFC 7285, DOI 10.17487/RFC7285, September 2014, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 7.2. Informative References [G2-SIGCOMM] Ros-Giralt, J., Amsel, N., Yellamraju, S., Ezick, J., Lethin, R., Jiang, Y., Feng, A., Tassiulas, L., Wu, Z., and K. Bergman, "Designing data center networks using bottleneck structures", ACM SIGCOMM , 2021. [G2-SIGMETRICS] Ros-Giralt, J., Bohara, A., Yellamraju, S., Langston, H., Lethin, R., Jiang, Y., Tassiulas, L., Li, J., Tan, Y., and M. Veeraraghavan, "On the Bottleneck Structure of Congestion-Controlled Networks", ACM SIGMETRICS , 2020. Ros-Giralt, et al. Expires 27 April 2023 [Page 21] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 [G2-TREP] Ros-Giralt, J., Amsel, N., Yellamraju, S., Ezick, J., Lethin, R., Jiang, Y., Feng, A., Tassiulas, L., Wu, Z., and K. Bergman, "A Quantitative Theory of Bottleneck Structures for Data Networks", Qualcomm Technologies Inc., Technical Report , 2021. [MERCATOR] Xiang, Q., Zhang, J., Wang, X., Guok, C., Le, F., MacAuley, J., Newman, H., and Y. Yang, "Toward Fine- Grained, Privacy-Preserving, Efficient Multi-Domain Network Resource Discovery", IEEE/ACM IEEE/ACM IEEE Journal on Selected Areas of Communication 37(8): 1924-1940, 2019, . [NOVA] Gao, K., Xiang, Q., Wang, X., Yang, Y., and J. Bi, "An objective-driven on-demand network abstraction for adaptive applications", IEEE/ACM IEEE/ACM Transactions on Networking (TON) Vol 27, no. 2 (2019): 805-818., 2019, . Authors' Addresses Jordi Ros-Giralt Qualcomm Europe, Inc. Email: jros@qti.qualcomm.com Sruthi Yellamraju Qualcomm Technologies, Inc. Email: yellamra@qti.qualcomm.com Qin Wu Huawei Email: bill.wu@huawei.com Luis Miguel Contreras Telefonica Email: luismiguel.contrerasmurillo@telefonica.com Richard Yang Yale University Email: yry@cs.yale.edu Ros-Giralt, et al. Expires 27 April 2023 [Page 22] Internet-Draft Bottleneck Structure Graphs in Multidoma October 2022 Kai Gao Sichuan University Email: kaigao@scu.edu.cn Ros-Giralt, et al. Expires 27 April 2023 [Page 23]