Discovering AS Path confederation...

Mailman List Mirror (Read Only)
1

I was wondering if anyone knew how to do as path confederation
discovery.

Let me explain...

I'm plotting observed traffic against BGP reported AS paths to get a
logical view of traffic flow in a smallish network (I2). However, it was
pointed out to me (by Bradley Huffaker) that the BGP reported path does
not always correspond to the ASes a packet actually traverses. He
provided me with some skitter data and routing table archives and I was
able to confirm this on both his data and my own data.

My contention is that the vast majority of this seeming divergence is
the result of AS confederation and not any specific failure of the
protocol (or implementation) as a whole. However, in light of what I am
trying to do for my research, its important that I have more than a gut
feeling to back up this claim.

What I was thinking of doing was to collect a large number of traces and
their corresponding traversed ASes and run statistical analysis on it to
infer the confederations. If these confederations are mostly stable then
I can say the observed divergence corresponds to this previously seen
path. E.g.... I run a trace and find it traverses 701 702 8414 2912 7262
101 while the route table indicates its path should be 701 7262 101. If
I know that 701 is confederating 8414 and 2912 then I know that the
actual path corresponds to the routing table. However, I first need to
determine that UUnet if actually doing that.

At this point I'm stuck on that step and could use any pointers or
insights people might have. Obviously, the best thing would be a paper
that has already done exactly this so I can move on but I'll take
anything. :slight_smile:

Chris Rapier

2

I think you're confusing confederations with something else entirely. For
example, the confederated paths are not visible outside a confederated AS.
Eg, some paths will show up like 1 2 3 4 5 6

and 2 may have an internal as path of (65518 655025 655123 23) but for all
intents and purposes, the internal structure of 2 is completely opaque to
entities not in the same AS.

/vijay

3

<snip>

I'm plotting observed traffic against BGP reported AS paths to get a
logical view of traffic flow in a smallish network (I2). However, it was
pointed out to me (by Bradley Huffaker) that the BGP reported path does
not always correspond to the ASes a packet actually traverses.

Propagation of a route in BGP requires that the network actually use that
route. On the surface, this would seem to ensure that the actual path
must match the BGP path. This assumes, however, that the packet follows
the same route from end to end.

If there is any route filtering, the packet may follow a short prefix
until it reaches a network which has a longer prefix in its routing table.
In that case, the packet will then follow the longer prefix. Someone
looking at the BGP tables from the source would only see the route for the
short prefix and may infer the wrong AS path.

<snip>

My contention is that the vast majority of this seeming divergence is
the result of AS confederation and not any specific failure of the
protocol (or implementation) as a whole.

<snip>

I haven't thought through this one. Can you enlighten me offline?

What I was thinking of doing was to collect a large number of traces and
their corresponding traversed ASes and run statistical analysis on it to
infer the confederations.

<snip>

Contact me offline. We may be able to help configure and run some tests.

Steve Schaefer

Dashbit - The Leader In Internet Topology
www.dashbit.com www.traceloop.com

4

Vijay Gill wrote:

> I can say the observed divergence corresponds to this previously seen
> path. E.g.... I run a trace and find it traverses 701 702 8414 2912 7262
> 101 while the route table indicates its path should be 701 7262 101. If
> I know that 701 is confederating 8414 and 2912 then I know that the
> actual path corresponds to the routing table. However, I first need to
> determine that UUnet if actually doing that.

I think you're confusing confederations with something else entirely.

Confusing the the concept of confederation with something else is
entirely possible. This is an aspect of the work I didn't think I'd have
to get into and have been struggling to catch up in.

Let me see if I can get some examples of what I am seeing...

Here we go...

trace -> 144.9.158.8 : 5050 701
bgp -> 144.9.158.8 : 5050 701 701 701 701 6334

t 147.128.68.22 : 5050 11536
b 147.128.68.22 : 5050 701 11536

t 148.245.167.130 : 5050 701 6503 3561
b 148.245.167.130 : 5050 701 6503

t 194.85.129.80 : 5050 701 702 8350
b 194.85.129.80 : 5050 701 702 8350

t 199.183.24.200 : 5050 701 702 2551
b 199.183.24.200 : 5050 701

t 200.186.247.25 : 5050 701 702 209 11415
b 200.186.247.25 : 5050 701 4230 11415

What I am looking for is a way to explaion the differences between the
ASes reported traveresed during the traceroute and the path as reported
by our local BGP routing tables.
Some of them makes sense as 701 - 705 inclusive is UUNet. And in
something like this:
t 199.183.24.200 : 5050 701 702 2551
b 199.183.24.200 : 5050 701

I am going with the assumption that UUNet provides
transit/network/whatrever services for AS 2551. Therefore, UUNet doesn't
actually have externally announce that route because it is still,
essentailly, part of the UUnet network. I don't know if that assumption
is warranted though so I'm looking to see how I can prove that
assumption.

I am having more difficulty trying to explain something like...
t 200.186.247.25 : 5050 701 702 209 11415
b 200.186.247.25 : 5050 701 4230 1141

Where it seemingly traverses an AS thats nowhere close to the BGP
reported path. I've some guesses such as the routing table is out of
date (but how often would we see something like this), something is
misconfigured at UUnet, or there is some administrative stuff going on
(like 209 is the same or owned by 4230).

The reason why I am doing this is because I'm planning on dropping some
monitors at a few locations in the I2 network and mapping traffic to the
AS mesh. Mostly I just want to see what it tells me at this point (but
there are some other aspects of it as well which might actually prove to
be useful). My initial assumption was that the BGP reported paths
conformed to reality closely enough that I wouldn't have to do
independent path discovery (like using the nikhef traceroute or
something). However, I need to prove that. Ya know?

For
example, the confederated paths are not visible outside a confederated AS.
Eg, some paths will show up like 1 2 3 4 5 6

and 2 may have an internal as path of (65518 655025 655123 23) but for all
intents and purposes, the internal structure of 2 is completely opaque to
entities not in the same AS.

Will all of the internal paths always correspond to private ASes? Or can
they be pretty much any AS (or series of ASes) controlled or otherwise
serviced by that primary AS? When I read the RFC my impression was that
they didn't have to be private.

Chris Rapier
PSC/NCNE/NLANR

5

Chris,

It appears your speaking of a somewhat well known phenomenon -

- Route A is learned via path 1-2-3-4 in a BGP confederation
- The best path is 1-6-4 due to any number of reasons, including metrics and
traffic engineering.
- The 1-6-4 path could be learned from numerous connected sub-AS's, all of
which have a different AS-Path and AS-Set towards 4.

From my experience this is only observable from inside the confederated

network, and is because path selection is not based on AS-Set length.

This can occur in a steady-state condition in a BGP confederation network.
It is more likely to be seen in especially well-connected sub-AS's, as they
have more neighbors to learn paths from.

- Dan

6

I just wanted to take a moment to thank everyone for helping me out with
this. I've a much better handle on the nature of the problem and likely
issues associated with it.

From what I understand often the difference between the de jure path and

the de facto path are due to a combination of:
1) Interfaces belonging to one AS that sit in a router belonging to
another AS.
2) A router not announcing an AS that sits behind it.
3) Adminitsrative issues (eg, purely human failures to keep the ASes
updated properly).
4) Network topology (peer to peer links between ASes and such).
5) Hand of fate.

All in all I've come to the conclusion that my initial assumption (which
is that the BGP tables provide a relatively accurate macroscopic map of
network topology) is correct. I'll probably need to exapnd on this more
if I ever write a paper on my work but I'm still not sure I'm doing
anything really useful yet.

Chris Rapier
PSC/NCNE/NLANR