[e2e] topological locality of Internet communication?

[Dmitri Krioukov]

lars,

although not precisely what you're looking for,
but the AS hop length distributions (or simply
distance distributions) derived from BGP and
*traceroute* data are not drastically different:
http://www.caida.org/analysis/topology/as_topo_comparisons/master.xml
(the associated text is in
http://www.caid.org/~dima/pub/ccr-ivs_as-topo-comparisons.pdf ).

also note that the average distance from ASs
of degree-k exhibits *very slow* power-law
decrease with k.

finally, check this paper:
http://arxiv.org/abs/cs/0411051

the above observations suggest that the AS hop length
distribution in the "average host communication
pattern" is unlikely to differ drastically from
the distance distribution in the whole AS graph.
--
dima.
http://www.caida.org/~dima/

> -----Original Message-----
> From: end2end-interest-bounces at postel.org
> [mailto:end2end-interest-bounces at postel.org]On Behalf Of Lars Eggert
> Sent: Friday, November 05, 2004 4:40 AM
> To: Panos TRIMINTZIOS
> Cc: end2end-interest at postel.org
> Subject: Re: [e2e] topological locality of Internet communication?
> 
> 
> Panos TRIMINTZIOS wrote:
> > Information about AS Paths from routes advertised with BGP on the
> > average/maximum AS path length (maybe also taking into account AS Path
> > prepending statistics) is an indication of the "AS hops" a typical
> > connection may cross in the Internet. Currently I the average AS Path
> > size is around 3.5 AS hops, while the maximum 11-12.
> 
> Thanks to Panos and others for providing these BGP-based numbers!
> 
> However, they're not exactly what I was looking for. Knowing that the 
> average BGP path is around 3.5 hops is useful *if* the "average" host 
> starts connections to random other hosts in the Internet. I'm pretty 
> sure that the latter doesn't hold, i.e., that the communication pattern 
> of hosts isn't random.
> 
> Jennifer's work on an AS-level traceroute is also interesting and 
> relevant; thanks for pointing me at it. However, I'm not completely sure 
> whether her tool can be run against an existing dump or requires live 
> traces. If the latter, I fear that those measurements could take up the 
> student's entire thesis time to be reasonably accurate.
> 
> Thanks again to all who responded!
> 
> Lars
> -- 
> Lars Eggert                                     NEC Network Laboratories
>