bgp

- research & experiments with border gateway protocol
git clone git://git.acid.vegas/bgp.git
build-cone.py (5642B)
      1 #!/usr/bin/env python2
      2 __author__ = "Bradley Huffaker"
      3 __email__ = "<bradley@caida.org>"
      4 # This software is Copyright (C) 2022 The Regents of the University of
      5 # California. All Rights Reserved. Permission to copy, modify, and
      6 # distribute this software and its documentation for educational, research
      7 # and non-profit purposes, without fee, and without a written agreement is
      8 # hereby granted, provided that the above copyright notice, this paragraph
      9 # and the following three paragraphs appear in all copies. Permission to
     10 # make commercial use of this software may be obtained by contacting:
     11 #
     12 # Office of Innovation and Commercialization
     13 # 9500 Gilman Drive, Mail Code 0910
     14 # University of California
     15 # La Jolla, CA 92093-0910
     16 # (858) 534-5815
     17 #
     18 # invent@ucsd.edu
     19 #
     20 # This software program and documentation are copyrighted by The Regents of
     21 # the University of California. The software program and documentation are
     22 # supplied $B!H(Bas is$B!I(B, without any accompanying services from The Regents. The
     23 # Regents does not warrant that the operation of the program will be
     24 # uninterrupted or error-free. The end-user understands that the program
     25 # was developed for research purposes and is advised not to rely
     26 # exclusively on the program for any reason.
     27 #
     28 # IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
     29 # DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
     30 # INCLUDING LOST PR OFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
     31 # DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF
     32 # THE POSSIBILITY OF SUCH DAMAGE. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY
     33 # DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
     34 # WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE
     35 # SOFTWARE PROVIDED HEREUNDER IS ON AN $B!H(BAS IS$B!I(B BASIS, AND THE UNIVERSITY OF
     36 # CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
     37 # ENHANCEMENTS, OR MODIFICATIONS.
     38 #
     39 
     40 #import the low level _pybgpsteam library and other necessary libraries
     41 from pybgpstream import BGPStream
     42 from datetime import date
     43 from datetime import timedelta
     44 import argparse
     45 
     46 import sys
     47 import bz2
     48 
     49 parser = argparse.ArgumentParser()
     50 parser.add_argument("link_file", nargs=1, type=str)
     51 parser.add_argument("-d", "--debug", type=int, default=-1)
     52 args = parser.parse_args()
     53 
     54 def main():
     55     sys.stderr.write("This is going to take some time\n")
     56 
     57     # Handle debug option
     58     debug_count = args.debug
     59 
     60     peer_provider = download_links(args.link_file[0])
     61     asn__cone = download_paths(peer_provider, debug_count)
     62 
     63     print "# ASN followed by ASNs in it's customer cone"
     64     print "# '1 23 4' means  ASN 1's customer cone includes ASN 23 and ASN 4"
     65     for asn,cone in sorted(asn__cone.items(), key=lambda a_c: len(a_c[1]),reverse=True):
     66         print asn + " "+" ".join(sorted(cone,key=lambda a: int(a.lstrip('{').rstrip('}'))))
     67 
     68 # Find the set of AS Relationships that are 
     69 # peer to peer or provider to customer.
     70 def download_links(filename):
     71     sys.stderr.write("loading relationships\n")
     72     first = 1000
     73     offset = 0
     74     hasNextPage = True
     75 
     76     peer_provider = set()
     77     with bz2.BZ2File(filename, mode='r') as fin:
     78         for line in fin:
     79             # skip comments
     80             if len(line) == 0 or line[0] == "#":
     81                 continue
     82             asn0, asn1, rel = line.rstrip().split("|")
     83 
     84             # peers work in both directions
     85             if rel == 0:
     86                 peer_provider.add(asn1+" "+asn0)
     87                 peer_provider.add(asn0+" "+asn1)
     88 
     89             # store the link from provider to customer 
     90             elif rel == -1:
     91                 peer_provider.add(asn1+" "+asn0)
     92             else:
     93                 peer_provider.add(asn0+" "+asn1)
     94 
     95     return peer_provider
     96 
     97 # download the AS paths from BGPStream
     98 # crop the path to the section after the 
     99 # first peer or provider link, then add
    100 # all the remaining ASes to the preceeding 
    101 # ASes in the cropped path
    102 def download_paths(peer_provider, debug_count):
    103     # The set of ASes reachable through an AS's customers
    104     asn__cone = {}
    105 
    106     sys.stderr.write("downloading paths\n")
    107 
    108     # Return a rib from yesterday's first second
    109     from_time = date.today() - timedelta(days=1)
    110     until_time = from_time + timedelta(seconds=1)
    111     stream = BGPStream(
    112         from_time=from_time.strftime("%Y-%m-%d %H:%M:%S"), until_time=until_time.strftime("%Y-%m-%d %H:%M:%S"),
    113         record_type="ribs"
    114     )
    115     stream.add_rib_period_filter(86400) # This should limit BGPStream to download the full first BGP dump
    116 
    117     # counter
    118     count = 0
    119     for elem in stream:
    120         # Break when debug mode activated and count equals debug count
    121         if (debug_count >= 0) and (count >= debug_count):
    122             break
    123 
    124         asns = elem.fields['as-path'].split(" ")
    125 
    126         # Skip until the first peer-peer or provider->customer link
    127         i = 0
    128         while i+1 < len(asns):
    129             link = asns[i]+" "+asns[i+1] 
    130             i += 1
    131             if link in peer_provider:
    132                 break
    133 
    134         # Since an AS only announces it's customer cone to it's peer or provider,
    135         # the remaining ASes in the path are in the preciding ASes customer cone.
    136         while i+1 < len(asns):
    137             if asns[i] not in asn__cone:
    138                 asn__cone[asns[i]] = set()
    139             cone = asn__cone[asns[i]]
    140             j = i+1
    141             while j < len(asns):
    142                 print (">",i,j,asns[i], asns[j])
    143                 cone.add(asns[j])
    144                 j += 1
    145             i += 1
    146 
    147         # Increment count
    148         count += 1
    149 
    150     return asn__cone
    151 
    152 #run the main method
    153 main()