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

Re: [RRG] Sceptically on compact interdomain routing (Modified by Victor Grishchenko)

On 18.10.2005, at 20:11, Joel M. Halpern wrote:
While theoretically hierarchical routing uses logarithmic space, there are several ways in which that turns out not to be the case: 1) Even with best case address allocation, we will probably have one entry per top level AS. For a sense of scale, we will exhaust toe 16 bit AS number space in the near future. 2) In practice there are far more than 1 prefix per AS. This occurs for many reasons. The reason thet folks like Geof Huston have indicated is largest is multi-homing.
OK. But, there are several ways in which that turns out to be radically better. E.g. RFC2374 proposes IX-based aggregation for IPv6 (i.e. IP numbering roots are IXes). So, the number of roots is rather limited (some other trick are possible to reduce that number even further).

Hence, a rough analysis indicates that if the compact routing research can be made practical (which is a major open question) then even if IDs were assigned to ever site on the net, we would still end up with a smaller table than we have now. That is a pretty good result.
It will remain to be another variant of splitted Dijkstra solution (see paper), i.e. there will be no difference in order, just a coefficient. (If I get your point right. There is also another way -- to apply CR on top of ASes. This second way dramatically reduces core routing tables but leads to further path inflation plus some other considerations.)

But I certainly am not asking not to continue investigating just because there are more hard problems further out.

PS: I am not a researcher with an account on arxiv, and it appears that accounts are intended for folks who will be submitting papers.
Sorry, I submitted it today. It takes some time to propagate to different mirrors, etc.
I think, this link will work tomorrow (after 00:00 GMT),




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