[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [RRG] Sceptically on compact interdomain routing
On 19.10.2005, at 5:13, Dmitri Krioukov wrote:
First, hierarchical routing employs routing tables of logarithmical
what specific scheme do you refer to?
in fact, what specifically do you mean
by 'hierarchical routing'?
Generally, any scheme that aggregates hosts into areas, areas into
super-areas, super-areas into... etc etc -- and, thus employs routing
tables of logarithmical size.
I use only the latter fact, without focusing on details. (I don't
insist that I have practically applicable hierarchic scheme or that I
know about such a scheme.)
so ASes aren't technically necessary for hierarchical routing
in general. So, the unweighted AS graph topology is not
an argument against hierarchical routing (in general).
Second, the existing two-tier global routing system (BGP for inter-
domain routing, plus some another solution, say OSPF, for intra-
domain routing) is equivalent to name-dependent compact routing.
what specifically do you mean by 'compact routing'?
in fact, the semi-formal definition is: a routing
scheme is compact if its local memory space has a
sublinear upper bound and if its stretch has a
constant upper bound.
... and node labels of (at most) logarithmical size.
I focused on the "splitted Dijkstra" approach (
http://arxiv.org/abs/cs.NI/0510052 , page 2) when (in the simplest
case) path is divided into inter-vicinity path (Dijkstra N1) and
intra-vicinity path (Dijkstra N2). Exactly the case of e.g. BGP+OSPF or
Generally, it is relevant for any scheme that is unable to aggregate at
arbitrary level of detail (like in hierarchical approach). Again, this
ability depends on locality. Locality is lost in models you consider in
Quasi-hierarchical approach is to aggregate ASes into vicinities
("Compact routing for Internet-like graphs"). Although each level of
such stacked scheme is "compact" all the routing system becomes
to unsubscribe send a message to email@example.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