Discovering AS Path confederation...
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. :) Chris Rapier
On Wed, 25 Jul 2001, Chris Rapier 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. 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
Vijay Gill wrote:
On Wed, 25 Jul 2001, Chris Rapier 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
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
-----Original Message----- From: owner-nanog@merit.edu [mailto:owner-nanog@merit.edu]On Behalf Of Chris Rapier Sent: Thursday, July 26, 2001 11:45 AM To: Vijay Gill Cc: nanog@merit.edu Subject: Re: Discovering AS Path confederation...
Vijay Gill wrote:
On Wed, 25 Jul 2001, Chris Rapier 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
On Wed, 25 Jul 2001, Chris Rapier wrote: <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
From what I understand often the difference between the de jure path and
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. 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
participants (4)
-
Chris Rapier -
Daniel Golding -
Steve Schaefer -
Vijay Gill