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

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

> -----Original Message-----
> From: Pekka Savola [mailto:pekkas@netcore.fi] 
> Sent: Monday, September 19, 2005 9:01 AM
> To: Dmitri Krioukov
> Cc: rrg@psg.com
> Subject: RE: Toward Compact Interdomain Routing [Re: [RRG] 
> recent progress in routing research]
> 
> ...
> 
> > 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 :)
> 
> Either would be interesting.  If the size of table is something like 
> 50 entries, it should be something folks could examine (much better 
> than the current topology of 10,000+ entries..) and 
> understand better. 
> I for one certainly would be interested in seeing what it would look 
> like (also in comparison with the current routing table).

it's still unclear if you're asking about how topology *or* routing
table looks like: topology is the real AS-level topology (e.g.
extracted either from skitter or routeviews), while the routing
table at every node consists of two parts: global part = shortest
path routes to landmarks; and local part = shortest path routes
to nodes closer to the given node rather than to their closest
landmarks. both parts are upper-bounded by sqrt(n) in the worst
case and precise algorithms are given on how to select landmarks
s.t. these bounds are satisfied. for more details see refs in
the paper.
--
dima.
http://www.caida.org/~dima/




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