Re: [RRG] Geoff Huston's article on BGP stability, update statistics and damping

[jnc@mercury.lcs.mit.edu (Noel Chiappa)]

    > From: Geoff Huston <gih@apnic.net>

    > If you will forgive me for hastily responding to just one observation
    > in your response

Forgiven in general, but your particular point might have benefitted from a
more complete read... (see below :-).

    >> Not just degree of interconnection; as I mentioned above, as the
    >> network grows, the average path length grows, so intuitively ..
    >> there's a slow growth in the likelihood that any particular
    >> connectivity change will impact any given path.

    > This is the comment I'd like to quickly respond to
    > ...
    > Since 1998 the network was grown from 50,000 entries to 225,000 entries
    > ..
    > BUT the average path length has remained pretty steady - most Route
    > Views peers see the entire network at an average AS path length of
    > around 3.4, and have done so since 1998.
    > i.e. as the network grows it gets more interconnected, and not longer
    > and stringer.

In my original message, I did indicate that I was aware that increased
connectivity had held down path length growth:

    >> in actuality average paths lengths in the Internet aren't growing as
    >> fast as they would in a random graph which is growing at the rate the
    >> Internet is, but to achieve that we are seeing higher connectivity
    >> levels

I wasn't aware that the average AS path length was actually static, though,
so that's interesting.

Of course, this is the AS path length, not the number of actual forwarding
steps; it would be interesting to know if the actual forwarding path length
had remained the same as well.

However, for the purposes of analyzing BGP's operational behaviour in
response to connectivity changes, the AS path length is probably at least
as important...


    > As the network grows, the density of interconnection increases. i.e we
    > are seeing higher inter-connectivity levels

Right. There's actually been a fair amount of work in the graph theory world
on this topic (and also in various applied fields), covering what are called
"small-world" graphs, which have this property (that the average path length
doesn't grow as the graph grows - which is true of true random graphs).

    > which I would see as one of the major factors that contribute to the
    > BGP behaviours we see today.

It's hard to say exactly how this change in connectivity patterns is affecting
BGP's behaviour. My off-the-cuff intuition says that there are effects in both
directions, and it's not clear which dominates.

For example, in the helping direction, the diameter of the graph is not
growing as fast as it normally would, and that's probably (but not
definitely, sometimes surface analyses are wrong) having a positive impact.
(Plus to which there's a second-order effect which is the negation of the
effect which started this thread.) In the other direction, I think that the
graph has more cycles in it, and I suspect (as I gather you do) that that's
probably a negative.

The whole situation is complex enough that I suspect the only way to say for
sure what the truth is is to do some pretty hairy simulations.

Remember, the actual recorded data-set we have from the operation of the
Internet includes two different things going on at the same time: a) overall
growth (in sheer size) as well as b) increased connectivity. I'm not sure we
can look at the recorded data (in terms of the growth of the update rate) and
sort out which part of the change is due to one, and which is due to the
other.

Hence the need for simulations to give us better data (since we're unlikely
to be able to modify the Internet's connectivity to give us actual data on
how the routing algorithm would operate in a a network of the same size, but
with different connection patterns :-).

	Noel

--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg