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?)