More on 'Number of Tiers' Discussion

Sun Apr 14 04:00:50 UTC 1996

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   |
|                                    |				         |
+------------------------------------------------------------------------+