Overview

We would like to develop a recipe, likely multiple scripts. That will allow a users to identify the what caused a customer cone change between two dates for a target AS.

We will likely need to increase the set of files that are provided publicly. You will be workin on beamer.caida.org so yo have access to the full set of files. Keep a list of the files you need and we will make sure they are public when the recipe is released.

What we want to identify is root causes of the changes single in a single AS's customer cone. Find the set of ASes that where removed or added. Find the set of paths that contained the target AS and the added or removed ASes.

Identify common factors between the change:

• the path containing the customer was found in stable, but not paths
  • was it not stable?
  • was it cleaned?
• the path contain the customer was found in all-paths, but not in stable
  • why was it not copied to stable
• the lost/added ASes share the same set of collectors or peers.
• the lost/added ASes share the same AS across their paths
• a relationship changed which caused the paths to be changed
  • once we have the above working, we will move on to identify the reason
    the relationship changed.

These should be presented in a table sorted by the number of ASes effected. This is just the starting point. We will likely discover more root causes as we work.

Process

Here is a highlevel overview of the process we will follow.
1 script that identifies the set of paths from .paths.bz2 and .paths.bz that contain the target AS and ASes which where lost or gained between .ppdc-ases.txt.bz2 and .ppdc-ases.txt.bz2. and creates <AS_target>-paths.txt

• target paths: .... AS_target .... AS_lost/AS_gained ...

2. script that finds the original paths in <date*>all-paths.bz2 and annotate the path with the collector and peer that observed it.
   • you will need to use 20220901-path_info.jsonl to find the paths that were changed in the cleaning process
   • output format should be a JSONL ; only include original/tags if path was changed

   {
        "path":"4739|7545|45430|45458|38820",
        "peers":[ {"collector":"ripe/rrc00","peer":"161.129.152.2"} ]
        "tags":[{"link":"7545|45430","index":2,"type":"IX"}],
        "original":"4739|7545|24115|45430|45458|38820"
   }

3. script create two tree rooted at the collectors

• Lost Tree uses the paths from date1 for ASEs that where lost between date1 and date2
• Gained Tree uses paths from date1 for ASes that where gained between date1 and date2
• For each tree count the number of ASes below each node in the graph

4. script that identifies the root causes, ie the most important nodes that contributed the the gained/losts ASes

• this is going to be tricky, because we need to identify threshold for when to count a change to a child rather then a parent.
• in some cases this will be easy, if the node's change is split across multiple parents, in others it will be harder to identify

5. script that produces a table/report of the root causes

c-Z- A-B-C-D
c-Z- A-B-E-F
c- T- A-G
            / T(1) \             / G (1)
c (3) -  Z (2)-   A (3) - B (2) - C (1) - D (1)
                                                \ E (1) - F (1) 

Background

AS Rank combines multiple datasets, but this script will be examing the BGP paths that are used to infer the AS Relationships and Customer Cones. Reading material:

• https://catalog.caida.org/presentation/2016_as_intro_visualization_ucsd (start here)
• https://catalog.caida.org/paper/2013_asrank
  (paper, you will need to read)
  • https://catalog.caida.org/presentation/2013_as_relationships_imc
    
    (paper's presentation, review after the paper for a different view on the same material)

Reference code:

• https://github.com/CAIDA/as-relationships (for reference, code that generates the as relationships)
• https://github.com/CAIDA/asrank-tools/blob/master/data-preprocessing/count.pl (code that implements annotated files)

AS Rank data sources follows the follow:

1. Download the BGP RIB
   /data/external/as-rank-ribs/20220901/{ripe,routeviews}

2. combine all the paths
   /data/external/as-rank-ribs/20220901/20220901.all-paths.bz2
   ripe/rrc00|4 13830|3356|1299|9583|45769 1.186.170.0/24 i 161.129.152.2

   • org: ripe
   • collector: rrc00
   • frequency seen across 5 days: 4
   • asn path: 13830|3356|1299|9583|45769
   • prefix: 1.186.170.0/24
   • code: i
   • peer: 161.129.152.2
   • path: rrc00 - 161.129.152.2 - 13830|3356|1299|9583|45769 - 1.186.170.0/24

3. find the stable paths 47787|174|12389|42742
   /data/external/as-rank-ribs/20220901/20220901stable.paths.bz2

4. created the set of "clean" paths" 47787|174|12389|42742
   /data/external/as-rank-ribs/20220901/20220901.paths.bz2

5. infer the set of AS Relationships
   /data/external/as-rank-ribs/20220901/20220901.as-rel.txt.bz2

• 3356|2|-1 3356 is a provider of 2 : 3356 < 2
• 2|3356|1 2 is a customer of 3356 : 2 > 3356
• 2|3356|0 2 is peer of 3356 2 - 3356
• 4 > 5 - 10 < 99 < 23

1. infer AS customer cones using as-rel on paths
   /data/external/as-rank-ribs/20220901.ppdc-ases.txt.bz2
   3356 1 2 3 4 6 7 9 11 3356 this means 3356's customer cone includes 1 2 3 4 6 7 9 11 3356

You can find a set of annotated paths here:

• /data/external/topology-asdata/as-rank/20220901/20220901-path_info.jsonl
  • this contains the set of "changed" paths and why they where changed.
  • these files are created from the as-relationship-serial-1 files and used to populate AS rank.
    {"original":"34288|4637|1221|17819|138592","path":"34288|4637|1221|138592","tags":[{"link":"1221|138592","index":3,"type":"IX"}]}

/data/external/topology-asdata/as-rank/20220901/
To make sure you have access to the full set of files. We will

Inferring customer cone

A > B - C < E
             C < E  c.cone_add(e)
A > B > C < E
                    E
A > B < C < E
             C < E c.cone_add(e)

Rules for cleaning paths

cleaning

• remove IX from AS paths
  
  A IX B -> A B
• remove adjacent duplicates ASes
  
  A A C D -> A C D

rejecting, the whole path is throw out

• loops: An AS is repeated with a different AS inbetween the first and second occurance
  
  A B C D C -> rejected

• poisoned paths: If there is a non clique member between two clique members

  A_clique B_not_clique C_clique
  A B C1 C2 C3 D -> not rejected
  A B C1 C2 D C3 E -> rejected, because of C2 D C3