[e2e] determining ingress interface?

[Rajesh Talpade]

> would recommend against assumptions of either symmetric paths
> or bgp reflecting actual traffic flow
> unless you're writing science fiction

always wondered about what new career i could launch into! :-)

seriously, what's a good reference for your second point about bgp not
reflecting actual traffic flow?

if, for one brief fleeting moment, we can suspend your point about bgp,
here's an approach for determining ingress interfaces. btw, it doesn't
require the assumption about symmetric paths.

ciao.
rajesh.



Problem statement:

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? 


Approach:

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
4.2.101.20 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
*  4.0.0.0          193.0.0.56          3333 9057 3356 1 i
.... (some lines deleted)
*                   217.75.96.60        16150 8434 286 1 1
.... (some lines deleted)
*                   141.142.12.1        1224 38 10514 3356 1 i
.... (some lines deleted)
*  4.2.101.0/24     141.142.12.1        1224 38 6325 1 i
*                   202.249.2.86        7500 2497 1 i
*                   203.194.0.5         9942 1 i
*                   66.203.205.62       852 1 i
*                   167.142.3.6         5056 1 e
*                   206.220.240.95      10764 1 i
*                   157.130.182.254     19092 1 i
*                   203.62.252.26       1221 4637 1 i
*                   202.232.1.91        2497 1 i
*>                  4.0.4.90            1 i

Destination IP address: 4.2.101.20
Destination AS: 1
Relevant IP address blocks: 4.0.0.0, 4.2.101.0/24
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. 
*  4.0.0.0          141.142.12.1             0 1224 38 10514 3356 1 i
The "best" path for local traffic of 1224 to 4.0.0.0 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.