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

[Pekka Savola <pekkas@netcore.fi>]

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