Food for Thought. Last week or so there was a suggestion here that 'we' adopt a four level tier model for hierarchical routing. I wanted to follow up, just a little, to explain to 'anyone interested' what is the generally accepted 'thinking' on hierarchical routing in large networks today. Kamoun and Kleinrock published an authoritative work on hierarchical routing and came to the interesting discovery: The optimal number of levels (tiers was used recently) is the natural log of the number of routed subnets, or just simply: ln(N) which reduces the routing table to the theoretical optimal number: e*ln(N) If we assume 'the four tier model' as suggested by a poster last week on NANOG, an upper bound is placed on the optimal number of routed subnets in a hierarchical model, basically: 4 = ln(N) or 54 subnets, in the K&K optimal case ;-) Which, BTW would be good for the routing table for an Inter-Hierarchy Routing Protocol (IHRP, for fun :-) .... for 148 entries ! If we, for fun, take the old class of IPv4 address space and simplify the numbers, without worrying about nits; 128 + (191-128)*2^8 + (255-193)*2^16 yields a ballpark number of 123+16128+4063232 ~= 4080 K Hence, ln(4080K) equals 15. So 15 is the optimal number of 'tiers' or levels in the current IPv4 address space (not taking into account distance-path vectors and other fun stuff). Now, of course, we can argue path-length trade offs vs. number-of-levels until our fingers are tired of typing e-mail, but why? The simple idea for illumination in this post is simply; It is not A Good Idea to propose a concrete, structured four-level superstructure for the Internet (and we have not begin to look at IPv6, BTW). This is all just theoretical mumbo-jumbo, BTW. Path length trade-offs, religion, the phase of the moon, greed, genetics, and every other conceivable human condition make ln(N) unobtainable. Our great^N grandchildren will be living in total peace and harmony before humankind will ever see ln(N). But, IMO, 'a four-tier model' is not What We Want, or WWW (note 1). Best Regards, Tim note 1: (a new image for WWW, the old one is getting stale, don't you think?) +------------------------------------------------------------------------+ | Tim Bass | | | Principal Network Systems Engineer | "Never underestimate the bandwidth| | The Silk Road Group, Ltd. | of a station wagon full of tapes | | | hurling down the highway." | | http://www.silkroad.com/ | -Andrew Tanenbaum | | | | +------------------------------------------------------------------------+
On Sun, 14 Apr 1996, Tim Bass wrote:
The simple idea for illumination in this post is simply; It is not A Good Idea to propose a concrete, structured four-level superstructure for the Internet (and we have not begin to look at IPv6, BTW).
Not proposing a 4-level hierarchical routing technology. Just describing the existing operational ecology using a 4-level metaphor as a proposed informational RFC. Have a look at http://www.sidhe.memra.com/rough.txt if you want to see the rough draft. Comments please. Michael Dillon Voice: +1-604-546-8022 Memra Software Inc. Fax: +1-604-546-3049 http://www.memra.com E-mail: michael@memra.com
Michael, There is little doubt that the 'existing operational ecology' is a very suboptimal paradigm (4,5, or whatever-level). It is suboptimal for IPv4 and extremely suboptimal for IPv6. Kamoun and Klienrock were specific ) and Tanenbaum in his latest and greatest third edition agreed ) that a ln(N) hierarchical superstructure is optimal for large networks. They also conclude that path-length is 'not a real problem', just to be complete. BTW, and please do not take this in a negative way and I offer my apologies for the following diatribe: \begin{diatribe} Documenting 'the way things are' is nice for 'informational and historical' purposes. But, building new paradigms and structures on top of highly suboptimal and outdated architectures just added to the problem and does little to move society toward progress. Using the 'information RFC' logic below; we could easily apply the same logic to humankind. Crime, hatred, envy, greed, selfishness, etc. is 'the way human society exists' suboptimal and problematic. Why strive to build a better 'human network' when the 'informational human RFC' (IHRFC maybe ;-) clearly documents a very suboptimal civilization. Anyway, as I once had to learn and still learn every day, _opinions_ are not unique and everyone has at least five thousand of them, making _opinions_ noise with knowledge. Doing the background research, going back to the body of knowledge in the field and adding foundation to vision and opinion significantly decreases the noise level. \end{diatribe} Just think how effective NANOG or any group could be if all the working members took the time to learn the body of background knowledge others have left around as 'clues'. Best Regards, Tim
On Sun, 14 Apr 1996, Tim Bass wrote:
The simple idea for illumination in this post is simply; It is not A Good Idea to propose a concrete, structured four-level superstructure for the Internet (and we have not begin to look at IPv6, BTW).
Not proposing a 4-level hierarchical routing technology. Just describing the existing operational ecology using a 4-level metaphor as a proposed informational RFC.
Have a look at http://www.sidhe.memra.com/rough.txt if you want to see the rough draft.
Comments please.
Michael Dillon Voice: +1-604-546-8022 Memra Software Inc. Fax: +1-604-546-3049 http://www.memra.com E-mail: michael@memra.com
participants (2)
-
Michael Dillon
-
Tim Bass