Determining the ingress interfaces


I asked the following question here a few weeks back, and got suggestions
to use "traceroute -g," traffic filters, and assume bi-directional paths
are same.

How do we determine the appropriate peer AS, and hence ingress interface(s)
at an ISP's border routers, for traffic arriving _from_ IP address blocks
not allocated to the ISP, and destined _to_ specific IP address(es)
within the ISP's network ? In other words, how do we create a mapping
between non-ISP-owned address blocks and the ISP's peer ASs, such that
given a non-ISP-owned address block, we can determine the peer AS thru
which traffic from the address block enters the ISP's network?

So do you BGP-gurus think that the following approach answers the
question? I would greatly appreciate your feedback.


Use data from BGP tables of as many ASs as possible. One candidate that
can provide such data is the routeviews project at Univ of Oregon run by
Dave Meyer. The routeviews server maintains eBGP sessions with about 63
BGP speakers, and dumps "sh ip bgp" every 2 hours.

Filter out all entries from latest routeviews data with destination IP
address(es) that we care about listed as "Network." May need to include
larger address blocks belonging to ISP as well, since destination IP
address(es) may have been aggregated into them by some ASs.

  For each address block filtered above, determine all ASs that are
  peers with the ISP's AS. This can done by creating a set of all ASs
  that appear immediately to left of ISP's AS for each path listed to
  address block, making sure there are no repetitions of ASs in the set.

  For each peer AS, create many-to-one mapping from source ASs to peer AS.
  (source ASs are all ASs on each AS path, except peer AS and ISP's AS;
   check that no source AS maps to multiple peer AS).

Associate IP address blocks with each source AS (partly using routeviews
data, partly thru ARIN d/b, etc), thus creating mapping from non-ISP-owned
IP address blocks to peer ASs.
Use network topology info for ISP's network to determine mapping between
peer AS and ingress interface(s).

Example usage of approach:

Determine mapping of source ASs to peer ASs for destination IP address on Genuity's network. (Genuity only used as an example here)

Relevant data from routeviews oix-full-snapshot-2002-06-23-1000.dat in
"sh ip bgp" format:
   Network Next Hop Path
* 3333 9057 3356 1 i
.... (some lines deleted)
* 16150 8434 286 1 1
.... (some lines deleted)
* 1224 38 10514 3356 1 i
.... (some lines deleted)
* 1224 38 6325 1 i
* 7500 2497 1 i
* 9942 1 i
* 852 1 i
* 5056 1 e
* 10764 1 i
* 19092 1 i
* 1221 4637 1 i
* 2497 1 i
*> 1 i

Destination IP address:
Destination AS: 1
Relevant IP address blocks:,
Peer ASs: 3356, 286, 6325, 2497, 9942, 852, 5056, 10764, 19092, 1221, 2497
Source ASs: 3333, 9057, 16150, 8434, 1224, 38, 10514, 7500, 1221
Mapping from source ASs to peer ASs:
Peer AS Source AS
3356 3333, 9057, 10514
286 16150, 8434
6325 1224, 38
2497 7500
4637 1221

The approach is based on the observation that each AS only advertises to
its peers the "best" route it knows to a specific destination network.
So given an AS path to a destination network in the routeviews data, the
"best" path that traffic from each of the source ASs on the path would
take to the destination network can be determined. e.g.
* 0 1224 38 10514 3356 1 i
The "best" path for local traffic of 1224 to is 38-10514-3356-1;
"best" path for local traffic of 38 is 10514-3356-1; "best" path for local
traffic of 10514 is 3356-1;
Hence the peer AS to use for getting to destination network can be
determined for local and transit traffic of each source AS. (Is this true?)

The effectiveness of the approach is dependent on the
number of views captured in the "sh IP bgp" data. i.e. the more paths
that are listed for a destination network, the more mappings from source
ASs to peer ASs can be determined.