Readme for the documents on PTE algorithm:


File lists:
===========
    infer-batch.pl
        :: main program.
    tools-preprocess_shipbgp.pl
        :: extract AS paths from RouteView routing table.
    tools-preprocess_bview.pl
        :: extract AS paths from RipeRRC routing table.
    infer-filter-transient-misconf.pl
        :: filter transient AS paths.
    infer-filter-policy-misconf.pl
        :: filter non-valley-free AS paths.
    infer-by-valley-free.pl
        :: infer AS relationships, including Prof. Gao's algorithm.
    infer-remove-loops.pl
        :: remove all possible AS relationship loops.
    tier1as.txt
        :: well-known Tier 1 ASes.
    readme.txt
        :: README document.

Functions:
==========
    These perl scripts are used for inferring AS relationship
    from parital information.

    The algorithm in this tool is implemented based on J. Xia and L.Gao's paper,
    "On the Evaluation of AS Relationship Inferences", IEEE Globecom 2004.


Usages:
=======
    0.  put these programs in the default folder, ~/bin/infer-exec/inferas_PTE/.
        (If you put in another folder, please change the default pathname in the code.)
    1.  download the routing table(s) from RouteView and/or Ripe RRC and unzip the files
    2.  run infer-batch.pl to infer AS relationship.

        FORMAT: perl infer-batch.pl initial.dat tier1.txt ratio asrelationship.txt tempdir RIPE00 pattern OREGON pattern

        INPUT:
                a. partial information file
                b. well known Tier 1 ASes
                b. presence ratio to determine transient AS path.
                d. routing tables from RIPE and/or Oregon RouteView
        OUTPUT:
                a.  AS relationship inferences.
        Examples:
                perl infer-batch.pl initial.dat tier1.txt 0.4 output.txt tmpdir RIPE00 table/rrc00-rt OREGON table/routeview-rt
        Notes:
                a. all routing tables are in "table" folder.
                    The files that begin with "rrc00-rt" are from RIPE RRC00,
                    and the files that begin with "routeview-rt" are from
                    Oregon RouteView. If there are routing tables from more
                    vantage points, please don't use infer-batch.pl file and
                    follow the detailed stages of PTE algorithm.
                b. the partial information is in "initial.dat".
                    The format of initial.dat is
                        1111 2222 E
                        3333 4444 P
                        5555 6666 C
                        ... ...
                    where,
                        E denotes AS1111 and AS2222 has peer-to-peer relationship.
                        P denotes AS3333 is a provider of AS4444
                        C denotes AS5555 is a customer of AS6666
                c. Well known Tire 1 ASes is in tier1.txt
                    The format of initial.dat is
                        701     UUNET
                        1239    SPRINT
                        7018    AT&T
                        1       GENUITY
                        ... ... ... ...
                d. the ratio 0.4 means that any AS path that does not appear in
                   40% routing tables from that router could be a transient one.
                e. the inference result is "output.txt". The format of output
                   file is as below:
                        12 34 E
                        45 67 P
                        25 34 C
                        ... ...
                   In order to reduce the redundant information, we only print out the first AS number is always less than the second AS number.


Detailed Stages on PTE Algorithm:
=================================
    Documents on Inferring AS Relationship for PTE problem
    (PTE:  partialness-to-entireness)

    1. Download routing tables from RIPE NCC rrc00 and RouteViews
       Extract the AS paths from routing tables
        1.1 How to get AS paths from RIPE00 bview data
            route_btoa -i -m ripe00/bview.20030710.0000 | cut -f7 -d'|' > ripe00/bview.20030710.0000.aspath
        1.2 How to get AS paths from RouteView's oix-full-snapshot data
            program:  perl tools-preprocess_shipbgp.pl

    2. filter transient misconfiguration from these AS paths
       program:  perl infer-filter-transit-misconf.pl

    3. filter policy misconfiguration from these AS paths
       program:   perl infer-filter-policy-misconf.pl

    4. infer remaining AS relationships
       (including Prof. Gao's degree-based heuristic algorithm)
       program: perl infer-by-valley-free.pl

    5. remove AS relationship loops (cycles) in our inferences
       program: perl infer-remove-loops.pl