9

Background

Some observations:

Now, 7 digits is enough to address ~107 (ten million) individual homes, which is several orders of magnitude larger than the population of my area code.

As of 2014, there are approximately 1010 (ten billion) devices connected to the internet, and only 232 (four billion) unique IPv4 addresses, but IPv4 exhaustion was a problem long before then.

The problem, in both cases, is that hierarchical allocation has built-in inefficiencies.

There are a number of meaningful advantages to hierarchical allocations (categorization and distribution of management chief among them), but it does have the major drawback of precluding 1:1 allocation of resources to consumers (or addresses to addressees, etc).

In fact, the inefficiency is exponential in the depth of the hierarchy, because trimming the tree at any level precludes assignment of that node and any of its children, down to the leaves (e.g. not permitting "911" to be an area code, or over-allocating large IPv4 blocks to individual institutions early on).

Questions

  • Is there a established term of art or industry which captures the inherent inefficiency of hierarchical allocation?

  • If not, how can I concisely describe it in a way that won't require further elaboration?

I'll upvote all useful answers; the answer which is best-recognized by the widest audience (for established terms) or requires the least elaboration (for novel coinings) will be accepted.


Note: The term sought does not have to be technical in nature, and in fact I'd prefer something with greater currency or historical support.

I'm sure governments or large organizations which allocate budget to states or departments, whence to middle-managers or cities, whence to ... have noticed this issue as well, and in that context it may well-studied already.

Possibly it's well-known in a martial context as well (distributions of rations and materiel to battalions, platoons, companies, regiments, squads..).

9
  • 2
    In case it's relevant, I once asked the same question on SO ... and earned the "Tumbleweed" badge.
    – Dan Bron
    Oct 21, 2014 at 19:40
  • Would 'systemic drawbacks' suggest what you have in mind?
    – user66974
    Oct 21, 2014 at 19:48
  • @Josh61, Not quite, because I'm looking for a word, term, or phrase which captures this specific type of systematic drawback.
    – Dan Bron
    Oct 21, 2014 at 19:49
  • 2
    This inefficiency is not necessarily from hierarchy, but from block allocation, although the two tend to be related. You get similar behavior in file systems, because files are allocated in units of disk blocks.
    – Barmar
    Oct 21, 2014 at 19:57
  • @Barmar, true and fair, and I would accept an answer coming from that direction (though I have a particular interest in the hierarchical situation, because of the exponential degradation).
    – Dan Bron
    Oct 21, 2014 at 19:59

4 Answers 4

4

Given Dan's request in the comments to provide some kind of justification to the term Route Exhaustion, I'll offer an anecdotal response.

Firstly, it's important to distinguish between hierarchies and routes. Hierarchies can be used for parent-child relationships without ever suffering the problem mentioned in the original question. It could be departments, relationships, or any number of things, and many of them will not suffer the issue outlined because they don't rely on routing.

Routing requires a set of rules that allows us to quickly locate an entity based on a set of hierarchical rules that allow us to quickly (and efficiently) locate something. They work because the rules are simple, and they are fast to process. This is when you type "google.com" in to your browser it knows where to go.

To keep things fast and efficient, routing hierarchies (such as DNS, IP addresses), need to have limits. Therefore, given any IP address range (Ipv4):

First
    Second
        Third
            Fourth

Obviously, given the explosion of the internet, and the range of numbers available (0-255), this was eventually going to be exhausted.

Now consider a hierarchy where I do not care about routing:

 United States Of America
     Arkansas
         Bentonville
             Walmart HQ
                  Finance
                       Commercial
                            Frank

"But wait!" You say, that's a route!

No, it's not.

FAO: Frank, Finance: Commercial
Walmart HQ
Bentonville, AR, 72712, USA

Humans can read that. But to do something efficiently, you need computers! (Actually, a computer could probably read that and figure it out, but I think that's beyond the scope of the question).

Let's call Walmart

1
    800
         925
             6278

This, is a route. 1 is the USA, 800 is a freephone number, and then we have 925 and 6278. Alas my knowledge of US telecommunications is unsure of whether they are separate nodes, but if they follow the rest of the area codes on the exchange, they're probably separate. Anyone can see now, that as great as this looks, you'll eventually run out of numbers to give out at a particular node.

To surmise, in the example of a departmental hierarchy, we rarely have to travel it, and we don't even have to travel it as address (though the zip-code may still play a part!), I don't have to route through many objects in my code.

But when you dial a number, and when you have an IP address, you have to route it.

When you run out, it's route exhaustion. You've exhausted all possible routes.

Wow, this answer really is a lot of waffle :)

3
  • 1
    +1 as promised for all helpful answers, and also 'cause I like waffles :)
    – Dan Bron
    Oct 21, 2014 at 21:16
  • 1
    your example 925 used to be the Local Exchange portion of the number, and was reliably mapped to a subdivision of the Area Code, so yes; it was, originally at least, part of the route. I don't know if they serve any sub-dividing purpose at all anymore.
    – Hellion
    Oct 21, 2014 at 22:15
  • 1
    800 is a poor example, as unlike normal area codes it isn't spatially grouped. So for Area Code 513, at first exchange 771 was a particular part of town. That's why you could dial fewer numbers for local numbers. 800 was always for business and as far as I know 800-925-0001 and -0002 might be anywhere in the USA relative to each other. These days more and more exchange numbers are ignoring space and are just allocated when needed.
    – Oldcat
    Oct 22, 2014 at 0:28
3

This is not a question of hierarchy. @Moo-Juice gives a good example that contrasts hierarchy with a route, showing that hierarchy is not the question. But neither is routing. Non-North American international telephone numbers have a much easier time routing:

  • 00 + country code + city code + local number

When the city grows, the city code may be able to be shortened, and the local numbers can always be made longer, up to any needed number of digits. The number of available telephone numbers never runs out.

The trouble comes when the number of digits must be restricted.

Thus the issue is neither one of hierarchy nor routing, it is one of encoding: how do I get all the information needed into a fixed set of codes? In this case, a fixed number of digits in a certain format.

Thus, the question is answered by Information Theory, created by Claude Shannon. The issue you bring up is described as [Shannon entropy][1].

[1]: http://en.wikipedia.org/wiki/Entropy_(information_theory) "Shannon entropy".

Read especially the second paragraph, where it says, "the entropy (thought of as the average information) received from non-uniformly distributed data is less than log2(n)."

2
  • This is definitely helpful and informative from a theoretical perspective, but doesn't lend any insight into how I can describe or communicate this limitation to others. If you add a suggestion on a concise term or phrase I can use to characterize the limitations imposed by Shannon's theory to a non-information-theorist in a way that doesn't require significant elaboration or education, I'll upvote this answer as well.
    – Dan Bron
    Oct 21, 2014 at 23:15
  • I thought about this long and hard before I answered, and these are my thoughts. First, the very concept is difficult, as this thread shows. So probably no concise expression of it will convey the right idea. Second, I believe that "Shannon entropy" is the precise name for what you are looking for; so to use that term is to state it concisely, but the information theory page is difficult for the layman to read. So since a discussion is necessary, perhaps the best solution is simply to reference this discussion?
    – shipr
    Oct 22, 2014 at 6:39
2

The costs of hierarchy is an expression that may suggest the concept of the inefficiencies derived from hierarchical allocations.

The following study shows that hierarchical organisations are less inefficient that it is generally expected, but systematic weaknesses and distortions appear to be unavoidable.

  • Some two-fifths of principals did not delegate even when income-maximization required it. This suggests that people get a non-pecuniary buzz from being in control, and seek this benefit at the cost of economic payoffs to themselves and others.

  • This is consistent with the findings of other experiments by Fehr and colleagues, which suggests that hierarchy facilitates exploitation rather than pure economic efficiency.

1
  • 1
    +1 for the link to the study, which is a good starting point for further research. Thanks Josh.
    – Dan Bron
    Oct 21, 2014 at 21:17
1
+100

This issue of compounding inefficiencies seems to be an endemic feature of any hierarchical system because its nature is exponential by definition.

That said, several hours of research led to interesting results from various sources and systems that experience the multiplicative deleterious effects resultant from a multi-leveled system.

I think some of these disadvantages could be summarized with terms like tier-degraded (from the perspective that additional steps in the chain compound the problem) or vertically-challenged utilization (in more of a corporate tone relating to stratum-enhanced challenges of properly apportioning resources evenly). Additionally, depth-compounded decay may indicate the exponential worsening of a particular property in a system.

However, as has been presented earlier, the appropriateness of the term you select may vary with the reason for presenting hierarchy as a disadvantage -

  • From the perspective of the inefficiency to manage or disburse resources on a 1:1 basis, concepts around organizational inequality and artificial scarcity start to take on meaning.
  • Alternatively, if examined from the approach where the forcing of hierarchy results in the stratification (and subsequent limitation) of significant routes or signals required to satisfy all stakeholders in the system, things such as distinctive path deficiency or lack of discrete channels may suffice to demonstrate unique insufficiency, such as in the area code/IP4 case presented above.

Interestingly, it's worth noting that there are additional disadvantageous results from hierarchical systems, such as exponential communication difficulty (for highly structured hierarchies) and limitations to modeling complexity which may not be immediately obvious but are surely no less significant.

Certainly a fascinating topic; its real-world implications (and realizations) are most intriguing!

2
  • +1 for for a useful answer, and awarded the bounty because this answer demonstrates meaningful research, and gives me a number of solid jumping-off points to continue my quest. But I'm going to have to withold the ✓, because none of the proposed descriptions are quite comprehensive or crisp enough for my purposes. You have my thanks.
    – Dan Bron
    Oct 30, 2014 at 15:32
  • 1
    Thanks for the bounty, Dan! Much appreciated. And I completely understand with lack of a more concise term for this phenomenon - I was surprised myself that even in my brief look at higher academic research, no distinct terms emerged for this pattern. From my searches, I wonder if the realizations of this phenomenon are either discipline specific or under-acknowledged on the whole. I think graph theory, computational efficiency/embedded systems, and network topology would also be interesting research origins in the math/tech fields, but I'm uncertain about similar terms in other industries.
    – Derezzed
    Oct 30, 2014 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.