On 19.10.2005, at 5:13, Dmitri Krioukov wrote:
First, hierarchical routing employs routing tables of logarithmical size,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 Thorup-Zwick.
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 "Towards...".
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 hierarchical.
-- Victor -- 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