RE: Toward Compact Interdomain Routing [Re: [RRG] recent progress in routing research]

["Dmitri Krioukov" <dima@caida.org>]

pekka, thanks for your comments. my comments on
your comments: :)

1) your comment #1:

you're right, of course, but the more you're right,
the better it is for the scalability argument in the
paper, since finer-than-AS routing control can only
*add* to the amount of state the IDR should keep. in
other words, our argument in this part of the paper
is that the scaling problem stays nearly the same
*even in the best possible case* when addresses are
ASs (as suggested in many proposals), while reality
can be only worse. you might ask then how the topology
of the network composed of a more realistic set of
'nodes' (that is, set of destinations finer than the
set of ASs) looks like. it's easy to see that this
topology is 'somewhere between' the AS- and router-level
graphs, i.e. it is only quantitatively, not qualitatively
different, since even though the router-level topology
is virtually unknown, all indicators are that it is also
small-world.

2) your comment #2:

i'm not sure what you mean. do you mean this other 'real'
topology from the previous point? we simply point out that
for the *real AS-level* topology, the routing table size
of the TZ scheme is ~50 entries of ~log(n) bits each, which
means that the average DFZ routing table size is below 100
bytes per node (that's why this type of routing is called
compact :) 

3) your comment #3:

thanks, but yes, we're talking about the worst case. we'll
see if we can extract any scaling estimate of the average
behavior from the paper you mention.
--
dima.
http://www.caida.org/~dima/

> -----Original Message-----
> From: Pekka Savola [mailto:pekkas@netcore.fi] 
> Sent: Wednesday, September 07, 2005 1:52 PM
> To: Dmitri Krioukov
> Cc: rrg@psg.com
> Subject: Toward Compact Interdomain Routing [Re: [RRG] recent 
> progress in routing research]
> 
> 
> I'll put this on the list in the interest of seeing if this would 
> generate wider discussion and/or comments.  I also trimmed the Cc: 
> list a bit..
> 
> On Sat, 20 Aug 2005, Dmitri Krioukov wrote:
> > For a list of most important papers on compact routing, see Section
> > 5 of http://arxiv.org/abs/cs.NI/0508021 Of course, there are much
> > more results in this area. One can find them following the reference
> > links. On the other hand, for a somewhat *shorter* version of the
> > compact routing reference list, see 'Compact routing background
> > reading' section at http://rr-fs.caida.org/
> 
> I read the "Toward Compact Interdomain Routing" paper 
> mentioned above. 
> I think it's a very good contribution in summarizing to the routing 
> community on what has been done elsewhere and adding quite a bit of 
> good analysis besides.
> 
> I noted two significant things worth of commenting:
> 
> 1) section 2 states "organization (AS) boundaries do offer a natural 
> level of aggregation and abstraction of routing information" and 
> similar other things.  Though I personally would like that to be the 
> case, it appears that at least in some cases it does not hold.  For 
> example, check out papers "A Measurement-Based Analysis of 
> Multihoming" and "A Comparison of Overlay Routing and Multihoming 
> Route Control" (from SIGCOMM's 2003 and 2004, respectively).
> 
> It seems that some want more fine-grained traffic optimization and/or 
> balancing than based on the AS -- for example, they want to do it on 
> per-prefix basis, with non-global propagation properties 
> (e.g., NOPEER 
> attribute).
> 
> In that light, it seems that while AS-level abstraction would work in 
> some cases (as an ISP, it would certainly work for us), it might be 
> insufficient in the more general case.  Though it being insufficient 
> might also be a GOOD thing, to avoid global routing table pollution.
> 
> But all in all, I think the paper needs to be a bit more analysis (or 
> refer to such) on whether AS-level abstraction is really a drop-in 
> replacement for the current model.
> 
> 2) In section 6, you mention that RT size for the real Internet 
> topology could be even as low as 50 entries.  It would be interesting 
> to see what that topology would look like.  Would this be 
> available in 
> a graph or some other format for study? (and comparison with the 
> current topology...)
> 
> 3) In section 6, you refer to BGP's convergence cost of O(n!) with 
> reference to Labovitz et al's "Delayed Internet Routing Convergence". 
> While algorithmically this might be true (if everyone gave transit to 
> everyone else), a better comparison point would be "The Impact of 
> Internet Policy and Topology on Delayed Routing Convergence" (Infocom 
> 2003).
> 
> -- 
> Pekka Savola                 "You each name yourselves king, yet the
> Netcore Oy                    kingdom bleeds."
> Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings
> 



--
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