[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Architectural approaches to multi6

On vrijdag, maa 28, 2003, at 23:35 Europe/Amsterdam, Dmitri Krioukov wrote:

http://citeseer.nj.nec.com/gavoille01routing.html



With these definitions, I guess more
people would agree with my initial
assertion since the multihomer is
necessarily a node on the graph and
the shortest path routing was found
to be incompressible on generic graphs
(see the above link but note that it
deals with the ideal world (static
and centralized), yet it provides
valuable information on the fundamental
limitations of any routing (even
not yet invented)).




I'm not so sure. I'm sure the math guys are really good at what they 
do, however it often doesn't have much to do with the real world. I 
have to admit that I can't decode a good deal of the math, but 
regardless of what omega is here, the following doesn't make sense:



"The current lower bound is only ¥Ø(¡în) bits for strategies optimizing 
shortest paths" (talking about local memory)



I believe that in a strictly hierarchical routing system it's possible 
to suffice with d+log(d)+3*log(3) bits of memory. Sure, you need 
something like n*log(n) routers that way, but that's another story...



In a hierarchical system, you can aggregate away more and more 
information as you get higher in the hierarchy. However, when a node 
moves to another part of the hierarchy, you break aggregation for part 
of the tree. The farther the node moves, the more aggregation suffers. 
But we can move nodes short distances in the hierarchy without causing 
many problems. So if we align our addressing hierarchy with the 
possible movements of nodes and/or the other way around, routing-based 
and scalable multihoming becomes possible. Hence my proposal for 
geographic aggregation. Then, when a site moves from one ISP to another 
as the result of a rehoming event, aggregation is still intact from the 
closest place where the ISPs interconnect and up.