Routing Table Growth: AS-Path Length Evolution Over Time In this task you will measure if an AS is reachable over longer or shorter path lengths as time progresses. Towards this goal you will measure the AS path lengths, and how they evolve over time. Again, we consider IPv4 prefixes only. Using the data from the cache files, calculate the shortest path for each origin AS in each snapshot by completing the function shortest_path_by_origin_by_snapshot(). Make sure that your function returns the data structure exactly as specified in bgpm.py. For each snapshot, you will compute the shortest AS path length for each origin AS in the snapshot by following the steps below: - Identify each origin AS present in the snapshot. For example, given the path "11666 3356 3786", "3786" is the origin AS. - For each origin AS, identify all the paths for which it appears as the origin AS. - Compute the length of each path by considering each AS in the path only once. In other words, you want to remove the duplicate entries for the same AS in the same path and count the total number of unique AS in the path. - Example: Given the path "25152 2914 3786 2914 18313", "18313" is the origin AS and "2914" appears twice in the path. This is a path of length 4. - Among all the paths for an AS within the snapshot, compute the shortest path length. - Filter out all paths of length 1. - Corner cases: The data that we are working with are real data, which means that there may be few corner cases. In the vast majority of cases, paths have a straightforward form of "25152 2914 3786", but you might encounter corner cases such as: a. If an AS path has a single unique AS or a single repeated AS (e.g., "25152 25152 25152"), the path has length 1 and should be ignored b. If an AS path contains sets of multiple AS in brackets. This is related to aggregation which you can read more about in RFC 4271. Example: Given an AS path such as "25152 2914 18687 {2914,14265} 2945 18699", the set "{2914,14265}" is counted as one unique AS for the purpose of calculating the AS path length, even though "2914" is also present outside the brackets - "2914" and "{2914,14265}" are distinct, so the path length in this case is 6. Example: Given an AS path such as "25152 2914 18687 18687 {18687}", the path length is 4 after removing duplicates, because "18687" and "{18687}" are distinct. c. You can ignore all other corner cases.

  

# Task 2: Routing Table Growth: AS-Path Length Evolution Over Time def shortest_path_by_origin_by_snapshot(cache_files): """ Compute the shortest AS path length for every origin AS from input BGP data files. Retrieves the shortest AS path length for every origin AS for every input file. Your code should return a dictionary where every key is a string representing an AS name and every value is a list of the shortest path lengths for that AS. Note: If a given AS is not present in an input file, the corresponding entry for that AS and file should be zero (0) Every list value in the dictionary should have the same length. Args: cache_files: A chronologically sorted list of absolute (also called "fully qualified") path names Returns: A dictionary where every key is a string representing an AS name and every value is a list, containing one entry per file, of the shortest path lengths for that AS AS numbers are represented as strings. For example: {"455": [4, 2, 3], "533": [4, 1, 2]} corresponds to the AS "455" with the shortest path lengths 4, 2 and 3 and the AS "533" with the shortest path lengths 4, 1 and 2. """ return {}