Traffic Engineering (fwd)

Mailman List Mirror (Read Only)
1

How do you plan to accumulate a priori knowledge of
distant topology and connectivity using current routing
protocols and the current transport addressing scheme?

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.

> Idea: what about a search engine that understands a BGP
> table?

Whose BGP table? Remember that you want to determine what
is most local to the client or its proxies.

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.

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

> 1) perform the query.
> 2) if your query returns multiple places to get the same page
> a) look at the AS_PATH for the querying IP address
> b) look at the AS_PATHs for the found pages
> c) Determine and return the "closest" one - perhaps the one
> whose AS_PATH is most like that of the querying host.

(c) is full of landmines thanks to such nifty things as
aggregation, the single-view propagation feature,
deliberately non-unique addresses and change and
instability of intermediate topology from moment to
moment.

Agreed.

> Anybody out there have any spare venture capital? :slight_smile:

Since you are trying to get it to work correctly with an
addressing scheme which only very weakly encodes
topological information, the lossy DV approach to
propagating routing information (as opposed to a
map-exchanging scheme), three huge churny databases
(the mapping of information to URL, the mapping of
hostname to IP address and the mapping of IP addresses to
paths) and attempting to come up with a non existant
database or workable heuristics (the mapping of n observed
paths to a graph of connectivity among m endpoints), I
would say that you need the level of funding you could
only raise from such lucrative business as the Psychic
Friends Network.

Just for the record, I *was* kidding. I don't actually think I have the time
or expertise to make it work. However, I think the idea is worth looking at.
Two of the "three huge churny databases" (info to URL, url to IP) already are
in place, and I bet the overhead involved in an un-cached IP lookup is a lot
more than that of an SPF walk through a BGP tree.

Meanwhile, I suggest you look at Dave Clark's distributed
database work (I think I remember Van Jacobson commenting
in more detail than his "How to Kill the Internet"
viewgraphs on how to apply this to the WWW) and consider a
scheme where rather than a database which centralizes
searches for a weak data architechture, a better
architecture and a scheme which treats every reference
into it as a search for the most local copy would be a
better development direction.

Will do, thanks.

  Sean.

eric

2

map-exchanging scheme), three huge churny databases
(the mapping of information to URL, the mapping of
hostname to IP address and the mapping of IP addresses to
paths)

Just for the record, I *was* kidding. I don't actually think I have the time
or expertise to make it work. However, I think the idea is worth looking at.
Two of the "three huge churny databases" (info to URL, url to IP) already are
in place, and I bet the overhead involved in an un-cached IP lookup is a lot
more than that of an SPF walk through a BGP tree.

Some people already have a database of IP address to path that is used to
more effectively route traffic from caching proxy hierarchies over multiple
international connections.

3

<osborne@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.)

4

In article <ytafhal5xz.fsf@cesium.clock.org>,

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

You can get an interesting set of data by sending a few rounds of
pings of different sizes. Make a scatterplot of ping packet size
vs. delay and find the line that fits the data; its slope represents
the inverse of available bandwidth and the y-intercept represents the
raw latency. Standard deviation gives you an idea of congestion.

Is it crude? Yes, but I don't know of anything better. Is it ugly?
Yes, but no uglier than traceroute.

This isn't my idea; I saw it in "bing".

Once you have a metric coded up, you can have each potential data
source measure the quality of their connectivity to the endpoint.
After they have agreed amongst themselves (probably via an
intermediary server) which server is best they can cause the session
to be moved to the most probably optimal server.