Traffic Engineering (fwd)

Thu Sep 18 20:31:36 UTC 1997

<osborne at terra.net> writes:

> AS_PATH was the first idea - other such tools could include ping times and
> traceroute hop counts.  It's been pointed out to me that IBM supposedly did
> something like this for the '96 Olympics.  

Perhaps you could explain to me how you can find the
shortest path between A and B using ping times, traceroute
hop counts, and AS_PATHS observed at C, assuming that
traffic between A and B is not exchanged through C?

> True - having a search engine look at its own BGP table is not the best 
> indicator of distance, especially if the search client is "distant" (many
> AS's away) from the engine.  However, given the prevalence of things like
> the Merit tools that show the BGP exchanges at major NAPs, it's conceivable
> that a search engine could grabe these tables on a regular basis, and from
> there it becomes pretty much an SPF tree through AS's.

An AS_PATH does not describe a connectivity graph.
It is attached to reachability information to avoid
looping NLRI propagation; in essence, it is an audit trail
of who has already seen the route and passed it on.

That is, when you look at an AS path like 1239 1800 1755 19999
you are trying to discover who has already apparently seen
the announcement, and therefore, who should not see it
again from you.

Any modern use or understanding of the AS path beyond this
is an overloading of the attribute and is probably a bad
idea.  (I expect some disagreement over this, particularly
as a BGP-talking router is expected to tell the truth about which
path it actually is using.)

Unfortunately, a popular modern use is in using the length
of the AS_PATH to influence routing policy by guessing
what other ASes will do with the AS_PATH length in the
route selection process.  This leads to the belief that
the AS_PATH can be used as a primitive metric, but this is
unreliable, and depends on the prevalence of a particular
selection process which hopefully someday will be dead, as
has been talked about for more than a year.  (Hi Paul, hi
Ravi, where's the code?)

Also unfortunately, a popular modern misunderstanding of
the AS_PATH is that it describes the current best (or even
ANY) path from somewhere back to the origin.  While
as-path prepending and the like has side effects on a
certain path-selection scheme, it also has a more
interesting side effect in the sense that you may scope
an advertisement by enumerating ASes that should not hear
the announcement.

That is, if I stuffed 9999 into the AS_PATH of an
announcement I generated or learned from elsewhere, AS
9999 would never hear the announcement from anyone who
heard it only from me.

The presence of 9999 in the AS_PATH does not indicate
connectivity between the surrounding ASes in this case.

There are two simple things to observe:
 * an editable AS_PATH guarantees that the AS_PATH 
   cannot reliably be used to determine which ASes
   will carry traffic towards the advertised prefix
   nor that any two adjacent ASes in the path are
   directly connected with one able and willing to send
   traffic directly to the other for that prefix
 * the reason one wants to edit an AS_PATH is almost
   always to make up for the fact that the AS_PATH length
   is commonly used as a primitive sort of metric, and
   without breaking the loop-prevention scheme, one cannot
   usually DECREASE the length of the AS_PATH except by
   playing icky games with AS_SETs.

To calm fears about the first point, anyone who advertises
a prefix to you declares that the prefix is reachable
through that neighbour.  (Although you should worry about
whether what you reach is a _local_ version of that
prefix that is routed to Null0 and the like, but that's a
social problem regarding trust, which of course is the
scary detail of using BGP for global dynamic routing).

The primary reason sed(1) was never implemented in OFRV's
code for a long time was that the AS_PATH was understood
to be an audit trail primarily to prevent announcement
loops, and that the formation of an announcement loop was
the obvious Bad Thing sed(1) could lead to.

> I do concur, though, that ping and traceroute are probably more sensible 
> metrics to use.

Why?  ping and traceroute are poor predictors of locality
and available bandwidth between the originator and target
of those tools.  

	Sean. (who had a long dinner break in the middle
		of this and probably left many loose ends.  sorry.)