Mangrove: A Unified Framework for Internet Topology, Routing Abstraction, and Modeling
draft-mangrove-workgroup-mangrove-00

ALTO                                                          Y. R. Yang
Internet-Draft                                               B. L. Lewis
Intended status: Standards Track                            D. M. Mertus
Expires: 5 September 2024                                      A. S. Shi
                                                             J. Z. Zhang
                                                         Yale University
                                                            4 March 2024

      Mangrove: A Unified Framework for Internet Topology, Routing
                       Abstraction, and Modeling
                  draft-mangrove-workgroup-mangrove-00

Abstract

   This document describes a novel system called Mangrove for obtaining
   global visibility across the Internet.  It achieves this through
   constructing a comprehensive, unified representation of the
   Internet's topology and routing behavior by aggregating and indexing
   diverse data sources. he core challenge is obtaining an accurate, up-
   to-date model of how packets traverse the global Internet given the
   Internet's vast scale, dynamic nature, and fragmented visibility
   across multiple organizations collecting data in different formats.

   Mangrove addresses this by leveraging the hierarchical structure and
   natural abstractions of Internet architecture.  It collects and
   integrates data from traceroute measurements, BGP routing tables, IP
   allocation records, and active broadband measurements.  This multi-
   source data is partitioned and indexed across multiple granularity
   levels - geographic regions, autonomous systems, and IP prefixes -
   allowing effective storage, querying, and scalable processing.

   Mangrove constructs a unified topology and routing representation
   augmented with an extensible ruleset derived from Internet axioms and
   measured data.  For arbitrary source-destination pairs, it computes
   estimated packet paths and associated performance metrics at the
   highest feasible granularity level based on available information
   completeness.  The system handles real-time Internet dynamics through
   incremental rule refinement using detected changes in routing data
   and measurements.  This enables timely updates to the topology model
   without full recomputation.  Mangrove aims to provide researchers and
   operators an unprecedented unified Internet view for analysis,
   optimization, planning, security, and regulatory tasks.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

Yang, et al.            Expires 5 September 2024                [Page 1]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   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 5 September 2024.

Copyright Notice

   Copyright (c) 2024 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 and Motivation . . . . . . . . . . . . . . . . .   3
   2.  Problem Statement . . . . . . . . . . . . . . . . . . . . . .   4
   3.  Internet Structure Overview . . . . . . . . . . . . . . . . .   5
   4.  Existing Systems Overview . . . . . . . . . . . . . . . . . .   6
   5.  Mangrove: A Framework For Internet Abstraction and
           Modeling  . . . . . . . . . . . . . . . . . . . . . . . .   7
     5.1.  Methodology . . . . . . . . . . . . . . . . . . . . . . .   8
     5.2.  System Architecture . . . . . . . . . . . . . . . . . . .  10
     5.3.  Scalability . . . . . . . . . . . . . . . . . . . . . . .  11
       5.3.1.  Geographic  . . . . . . . . . . . . . . . . . . . . .  11
       5.3.2.  AS  . . . . . . . . . . . . . . . . . . . . . . . . .  11
       5.3.3.  Subnet/Prefix . . . . . . . . . . . . . . . . . . . .  12
   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  12
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  12
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  13

Yang, et al.            Expires 5 September 2024                [Page 2]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

1.  Introduction and Motivation

   The Internet is a vast and complex network of interconnected devices,
   spanning the globe and enabling communication between billions of
   users and systems.  Understanding the underlying topology and routing
   model of the Internet is crucial for researchers, network operators,
   and service providers to gain insights into routing dynamics,
   performance characteristics, and potential vulnerabilities.  However,
   the current state of Internet topology and routing mapping is
   fragmented, with multiple organizations and projects collecting data
   through various measurement techniques, such as traceroutes, BGP
   looking glass dumps, and performance metrics.  This data is often
   inconsistent in format, incomplete, and distributed across multiple
   sources, making it challenging to obtain a comprehensive and unified
   view of the Internet's topology.  We wish to build a system that
   unifies this information into a single representation of routing and
   topology models of the Internet at different points in time, allowing
   for queries to be performed against this representation.

   By creating a comprehensive model of the Internet’s topology and
   routing dynamics, this system will enable a wide range of
   applications and analysis, including:

   1.  Network monitoring/troubleshooting: The ability to detect and
       localize routing anomalies, such as loops, black holes, or
       performance degradation can aid in identifying and resolving
       network issues more efficiently.

   2.  Vulnerability assessment and security analysis: A unified view of
       the Internet's topology and routing can help identify potential
       vulnerabilities, such as single points of failure or routing
       hijacks, enabling proactive measures to enhance network security
       and resilience.

   3.  Traffic Engineering and Capacity Planning: By understanding the
       flow of traffic across the Internet, service providers can
       optimize resource allocation, load balancing, and capacity
       planning, improving overall network performance and efficiency.

   4.  Resilience and Disaster Recovery Planning: Modeling the impact of
       potential outages or failures on the Internet's topology and
       routing can inform disaster recovery strategies and contingency
       plans, ensuring business continuity and minimizing service
       disruptions.

Yang, et al.            Expires 5 September 2024                [Page 3]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   5.  Privacy and Regulatory Compliance Analysis: The ability to map
       data flows across the Internet can aid in identifying potential
       privacy violations or regulatory non-compliance, enabling
       organizations to take proactive measures to protect user data and
       comply with relevant regulations.

2.  Problem Statement

   Being able to construct a digital twin of a network as large as the
   Internet comes with unique requirements for our system.  These are,
   in no particular order:

   1.  Scalability: The sheer scale of the Internet poses a significant
       challenge for our system.  With over 17 billion devices connected
       and more than 60,000 networks or Autonomous Systems (ASes), each
       with its own internal topology, storing information about the
       paths interconnecting all these devices requires us to employ
       efficient indexing mechanisms and data structures that enable
       fast queries over large repositories of data.

   2.  Diverse Data Sources: The data required for topology mapping is
       scattered across multiple organizations, each with their own data
       collection methodologies, formats, and access methods (discussed
       below).  The diversity of formats, from traceroute data to BGP
       table dumps, coupled with varying updating cadences and access
       methods, presents a significant challenge.  Furthermore, the
       quality and completeness of the data can vary based on the
       vantage points of the collectors, leading to potential gaps or
       inconsistencies.  Our system must be capable of integrating data
       from these diverse sources in a way that is consistent and
       unified.

   3.  Partial Information: Many topology measurement techniques, such
       as traceroutes, can produce incomplete or missing information due
       to factors like firewalls, packet filters, or unresponsive
       devices.  This is often manifested as missing hops represented by
       asterisks (*) in the traceroute data.  Additionally, BGP routing
       data lacks granularity below the Autonomous System (AS) level
       paths.  IP geo-mapping databases, used to associate IP addresses
       with physical locations, also have inherent inaccuracies.
       Furthermore, performance data may be sampled or estimated
       statistically rather than being comprehensive.  As such, our
       system must be capable of producing the best-effort topology and
       routing representation for packets between two hosts, even when
       the input data is incomplete or partially missing.

Yang, et al.            Expires 5 September 2024                [Page 4]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   4.  Real-time, Dynamic Updates: The Internet is a highly dynamic
       environment, with routing changes, network outages, and topology
       shifts occurring continuously.  Events like outages, attacks, or
       policy changes can trigger changes in the routing behavior, with
       BGP convergence times ranging from seconds to minutes after an
       event.  New links and nodes are constantly being added, while
       others are going down.  Our system needs mechanisms to detect
       these relevant changes and incrementally update the topology
       representation in real-time or near real-time.  However, this
       requirement presents a trade-off between the cost of performing
       full recomputations versus maintaining and applying deltas or
       incremental updates.  Additionally, our system must meet the time
       window requirements for how current the topology view needs to
       be, depending on the specific use case or application.

3.  Internet Structure Overview

   At a high level, the objective of our framework is to compute a
   digital twin of the Internet routing system, and this system is
   complex:

   The Internet is composed of several layers, each serving a distinct
   function:

   1.  Link Layer: Governs the transfer of data between directly
       connected nodes.

   2.  Internet Layer: Handles logical addressing and routing of data
       across the network.

   3.  Transport Layer: Manages end-to-end communication and ensures
       reliable data transfer.

   4.  Application Layer: Enables network services and applications to
       interface with the underlying transport protocols.

   Sitting on top of these layers, Autonomous Systems (ASes) and the
   Border Gateway Protocol (BGP) govern how packets traverse networks
   operated by different administrative entities.

   The behavior of the Internet can be characterized by two principal
   components: the underlying network topology and the routing policies
   enforced by the protocol ruleset.  Network topology delineates the
   physical connectivity constraints that determine the paths packets
   can traverse.  However, network infrastructure is in a constant state
   of flux as devices are continually added, removed, or reconfigured,
   posing challenges for comprehensive topology measurement outside an
   AS's purview.  Routing policies dictate how packets are forwarded

Yang, et al.            Expires 5 September 2024                [Page 5]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   along available paths in accordance with protocol rules.  Protocols
   like Equal-Cost Multi-Path (ECMP) routing introduce complexity,
   making the determination of single best paths more difficult.
   Furthermore, most devices do not expose their Forwarding Information
   Bases (FIBs), obscuring the precise ruleset implementations.

   Consequently, measurements provide the primary evidence of the
   effects induced by the combination of the underlying topology and the
   applied routing policies.  This abstraction of rule systems onto
   physical network elements results in observable path properties, such
   as latency, bandwidth, and jitter, which are crucial for
   characterizing end-to-end packet delivery performance between nodes.

4.  Existing Systems Overview

   Current solutions for internet visibility topology generally divide
   their focuses across two key categories: topology and routing
   inference and metadata measurement.  Additionally, these solutions
   further subdivide into consumer solutions and enterprise solutions
   providing a mix of both aggregate and granular data measured in
   varying units of time.

   Topology and routing measurement solutions employ a collection
   paradigm that includes:

   1.  Distributed Nodes: Operated either by the organization itself or
       external contributors, these nodes form the backbone of data
       collection efforts.

   2.  Periodic Traceroute Measurements: Using tools such as paris
       traceroute, measurements are periodically collected between nodes
       to infer network topology.

   3.  Data Inference: The collected data is analyzed to infer the
       network topology, relying on the information returned by
       traceroute measurements.

   Metadata measurement solutions diverge from topology measurement
   primarily in the nature of data collected.  Unlike topology
   measurement, which focuses on the structure of the network, metadata
   measurement seeks to understand the properties of network paths.
   This requires a significantly larger dataset, typically sourced from
   a wide user base employing network measurement tools.  The process
   involves:

   1.  Connection to a Local Server: Establishing a baseline for
       measurement by connecting to a server in close proximity to the
       user.

Yang, et al.            Expires 5 September 2024                [Page 6]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   2.  Connection Saturation: Maximizing the use of the connection to
       ensure comprehensive data collection.

   3.  Measurement Execution: Performing measurements to gather data on
       the connection.

   4.  Optional Traceroute Measurement: If feasible, supplementing the
       measurement with traceroute data for enhanced insight.

   5.  Statistical Inference: Applying statistical methods to the
       collected data to extrapolate insights on broadband measurements,
       with a focus on geographical specificity.

5.  Mangrove: A Framework For Internet Abstraction and Modeling

   The existing choice between focusing on traceroute data or broadband
   connection measurements presents a significant trade-off for
   organizations.  To generate an accurate topology, organizations need
   control: owning the network devices, collecting traceroute data on a
   consistent schedule, and sending as many traceroutes as possible in
   ways that maximize inference.  However, broadband measurement
   requires detail and quantity: distributing access nodes, collecting
   as much consumer information as possible, using traceroutes as only
   secondary sources of information.  This tradeoff in required
   infrastructure has made it difficult to bridge the gap between
   topology, path inference, and associated metadata.

   Topology and routing inference is done through the analysis of data
   retrieved from techniques including traceroute experiments and BGP
   Looking Glass dumps.  This raw data alone provides insight into the
   ‘real’ structure of the Internet; traceroute measurements form the
   backbone of most existing Internet topology mapping efforts, and when
   combined with Autonomous System routing data, can be used to infer
   the paths that exist throughout the internet.  The primary technique
   for collecting these involves deploying a distributed set of vantage
   points or measurement nodes across the Internet.  These nodes
   periodically initiate traceroute experiments towards predetermined
   destination IP addresses or prefixes.  Many topology mapping projects
   like CAIDA's Ark and RIPE Atlas have deployed large measurement
   infrastructures consisting of hundreds or thousands of vantage points
   globally.  These provide diverse perspectives into Internet paths
   from different edge networks.

   Most existing platforms focus on either traceroute data collection
   and analysis, or BGP/routing data.  Very few solutions currently
   attempt an integrated data fusion across measurements, routing,
   geolocation and performance data.

Yang, et al.            Expires 5 September 2024                [Page 7]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   We propose the engineering of a scalable system that aggregates and
   indexes data from various sources to construct a single, unified
   representation of Internet topology.  This representation would
   provide researchers and network operators with rich information about
   the connectivity between devices on the Internet, augmented by
   performance metrics that could inform them about connection quality
   between networks.

5.1.  Methodology

   To construct this unified representation, our system will leverage
   the natural abstractions offered by Internet architecture to provide
   the best level of estimates for topologies and routing decisions.
   The core methodology involves the following steps:

   1.  Data Aggregation: Collect and integrate data from multiple
       sources, including CAIDA Ark traceroute measurements, BGP looking
       glass dumps, Regional Internet Registry (RIR) records, and
       performance data from projects like M-Lab, Ookla, and perfSONAR.

   2.  Abstraction: Leverage the natural abstractions in Internet
       architecture, such as the Autonomous System (AS) level, to
       represent topology at different granularities.  This allows the
       system to handle incomplete data and provide estimates at varying
       resolutions.  Represent this as a multidimensional graph where
       nodes can aggregate, inherit, or point to other nodes on the
       graph depending on the abstraction layer.

   3.  Rule Generation: Use network axioms to generate an initial set of
       rules for AS pathing using BGP dumps, traceroute first hops, and
       business relationships.  The system then repeatedly generates and
       refines lower rule sets using axioms, AS pathing, FIBs, and known
       clustering policies for levels of resolution from subnet to
       devices.

   4.  Compression: Completed rules are grouped into sets for their
       particular header space.  The system stores such classes in a
       tree which represents IP prefixes and addresses.  Indexing into
       and moving down levels for a chosen destination determines the
       rule-set.  This allows for constant-time indexing, with a slight
       space tradeoff.

Yang, et al.            Expires 5 September 2024                [Page 8]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   5.  Path Inference: For a given source and destination IP address
       pair, the system will attempt to provide the highest certainty
       estimate of the path a packet would take, based on the aggregated
       data and rule trie.  If complete traceroute data is available, it
       will be used to provide a detailed IP-level path.  If not, the
       system will attempt to construct a path using the rule set for
       its IP prefix and graph edge weights.  The final fall back is to
       AS-level paths derived from BGP routing information.

   6.  Performance Enrichment: Augment the topology representation with
       performance metrics, such as bandwidth, latency, and throughput,
       obtained from sources like M-Lab and Ookla.  Such data can be
       added by matching consumer collected traceroutes with those of
       topology measurement solutions.  For AS-level paths, performance
       metrics can be averaged across nodes within each AS.

   With the above, we will provide users with an interface that they may
   use to query the path that a packet would take between any two
   arbitrary source and destination IP addresses.  Our system will
   leverage all of the information it has aggregated to provide a ‘best
   estimate’ of this path, while augmenting this with performance
   metrics at the highest level of resolution.

   To illustrate this, we consider a sample user query where a user
   wishes to know the path a packet would take between source IP address
   A and destination IP address B.

   At a high level, our system will do the following:

   1.  Map each IP address to their corresponding AS numbers: the system
       will maintain an IP address to AS lookup as a result of
       aggregating this data from several sources over time.  The most
       recent match for the IP address will be used.

   2.  Analyze BGP routing data for each corresponding AS: if the IP
       addresses lie in separate autonomous systems, we may query each
       of the corresponding BGP table representations for each AS to
       determine the AS path that a packet will use to get from A to B.

   3.  Infer AS-level Path: After determining the AS numbers for the
       source and destination IP addresses, and analyzing the BGP
       routing data for the corresponding ASes, the system can infer the
       AS-level path that a packet would take from the source AS to the
       destination AS.  This AS-level path would be a sequence of AS
       numbers, representing the path through different Autonomous
       Systems.

Yang, et al.            Expires 5 September 2024                [Page 9]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   4.  Retrieve Traceroute Data for Each AS Hop: For each AS hop in the
       inferred AS-level path, the system will attempt to retrieve
       relevant traceroute data to reconstruct the IP-level path within
       that AS.  This can be done by querying the indexed traceroute
       data based on the source and destination AS numbers for that
       particular hop.

   5.  Reconstruct IP-level Path Within Each AS: If traceroute data is
       available for an AS hop, the system will use that data to
       reconstruct the IP-level path within that AS.If no traceroute
       data is available, the system will treat that AS hop as a single
       hop in the final path, representing the AS-level transition.

   6.  Handle Missing Hops and Incomplete Paths: If there are missing
       hops (represented by *) within an AS hop, the system will group
       consecutive * hops and represent them as a single AS-level hop in
       the final path.  If no traceroute data is available for an entire
       AS hop, the system will represent that hop at the AS-level in the
       final path.  This illustrates our concept of ‘granularity’ -
       where there is missing data at a specific resolution, we may
       resort to using data at a lower resolution (the AS level) to
       still provide some insight into the path.

   7.  Associate Performance Metrics: The system can then associate
       relevant performance metrics, such as latency, bandwidth, or
       throughput, with each hop in the final path.  In cases where our
       system must resort to lower resolutions, we may use aggregation
       and averaging techniques to provide a rough estimate on
       connectivity statistics for that portion of the path.

5.2.  System Architecture

   The proposed system will consist of the following key components:

   1.  Data Collectors: Modules responsible for fetching and processing
       data from various sources, such as CAIDA Ark, BGP looking glass
       servers, RIRs, and performance measurement platforms.

   2.  Data Unification Engine: A central component that integrates and
       indexes the collected data into a unified representation,
       handling data format conversions, deduplication, and consistency
       checks.

   3.  Topology Database: A scalable and distributed data store designed
       to store and query the unified topology representation,
       supporting both IP-level and AS-level granularities.  The data
       will be represented as a multi-dimensional graph, its associated
       rule sets in equivalence classes, and a compressed trie.

Yang, et al.            Expires 5 September 2024               [Page 10]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   4.  Query Engine: An engine with a custom query language that can
       quickly join data at multiple levels of resolution depending on
       the user request.

   5.  Interface: An API or user interface that allows researchers and
       network operators to submit source-destination IP pairs and
       retrieve the corresponding estimated paths, along with associated
       performance metrics.

   6.  Real-time Update Handler: A component that monitors for changes
       in the underlying data sources and triggers updates to the
       topology representation, ensuring it remains current with the
       dynamic nature of the Internet.

5.3.  Scalability

   With regards to discussion about scalabiltiy, the partitioning and
   distribution of data across different levels can be structured as
   follows:

5.3.1.  Geographic

   At the geographic level, the system can partition the data based on
   geographic regions or clusters.  This level is responsible for
   storing and managing the BGP routing data for the Autonomous Systems
   (ASes) within each geographic cluster.  The primary function of this
   level is to handle AS-level path inference and resolution based on
   the BGP routing data.

5.3.2.  AS

   Within each geographic partition, the system can further partition
   the data by individual AS.  At this level, each AS is responsible for
   storing and managing its own internal routing topology and traceroute
   data.  This level is designed to handle IP-level path reconstruction
   and inference within the boundaries of a single AS.

   The AS-level partitions can maintain the following data:

   1.  Internal Routing Topology: This includes the router-level
       topology within the AS, representing the interconnections between
       routers and network devices.

   2.  Traceroute Data: Traceroute measurements conducted within the AS,
       capturing the IP-level paths between different ingress and egress
       points or subnets.

Yang, et al.            Expires 5 September 2024               [Page 11]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   3.  Performance Metrics: Performance data (e.g., latency, bandwidth)
       associated with links or paths within the AS, obtained from
       sources like M-Lab or Ookla.

5.3.3.  Subnet/Prefix

   To further enhance granularity and scalability, the system can
   introduce an additional level of partitioning at the subnet or IP
   prefix level.  This level can store traceroute data and performance
   metrics specific to individual subnets or IP prefixes within an AS.

   By partitioning the data at these multiple levels, the system can
   distribute the workload and storage requirements across different
   components, allowing for parallel processing and improved
   scalability.

   The workflow for resolving a path between a source and destination IP
   address would involve the following steps:

   1.  The geographic partition responsible for the source and
       destination ASes is identified, and the AS-level path is
       determined using the BGP routing data.

   2.  For each AS hop in the inferred AS-level path, the corresponding
       AS partition is queried to retrieve traceroute data and
       reconstruct the IP-level path within that AS.

   3.  If further granularity is required or available, the subnet/
       prefix level partitions can be consulted to obtain more detailed
       traceroute data and performance metrics for specific IP prefixes
       or subnets along the path.

6.  IANA Considerations

   This document has no actions for IANA.

7.  Security Considerations

   The collection, distribution of MoWIE information should consider the
   security requirements on information privacy and information
   integration protection and authentication in both sides.  Since the
   network status is not directly related to any special user, there is
   currently no any privacy issue.  But the information transmitted to
   the application can pass through a lot of middle box and can be
   changed by the man in the middle.  To protect the network
   information, an end to end encryption and integration is needed.
   Also, the network needs to authenticate the information exposure
   provided to right applications.  These security requirements can be

Yang, et al.            Expires 5 September 2024               [Page 12]
Internet-Draft  Mangrove: A Unified Framework for Intern      March 2024

   implemented by the TLS and other security mechanisms.

Authors' Addresses

   Y. Richard Yang
   Yale University
   Watson 208A, 51 Prospect Street
   New Haven, CT 06511
   United States of America
   Email: yang.r.yang@yale.edu

   Bradley Lewis
   Yale University
   33 Lynwood Pl
   New Haven, CT 06511
   United States of America
   Email: bradley.lewis@yale.edu

   Daniel Mertus
   Yale University
   Unit 404, 367 Elm Street
   New Haven, CT 06511
   United States of America
   Email: daniel.mertus@yale.edu

   Alex Shi
   Yale University
   33 Lynwood Pl
   New Haven, CT 06511
   United States of America
   Email: alex.shi@yale.edu

   Joseph Zhang
   Yale University
   33 Lynwood Pl
   New Haven, CT 06511
   United States of America
   Email: joseph.zhang@yale.edu

Yang, et al.            Expires 5 September 2024               [Page 13]