Combinatorial Solution to the Problem of Optimal Routing in Progressive Gradings

The term 'hierarchical' has often been used to describe connecting networks in which the possible routes for a call are ordered, with the S65 866 TI-IE BELL SYSTEM TECHNICAL JOURNAL, M A Y - J U N E 19(57 order determining the routing decisions in that the earlier routes are hunted over before the later. The Bell System's toll network is often cited as an example of a hierarchical network. Recently, J. H. Weber has used the word 'hierarchical' in a more technical sense to describe trunking networks ". . . in which at least some of the trunk groups are high usage; i.e., traffic which is not carried can be overflowed to other groups, at least some of which are finals, which have no alternate route."1 In this paper, we consider some ways in which the concept of a hierarchy of routes is relevant to the problem of optimal routing as formulated in previous work.2 Naturally, such a hierarchy can be relevant to routing only if it is in a suitable way related to those combinatorial properties of the network which distinguish the 'good' from the 'poor' ways of completing calls. (Examples of such properties were given in Ref. 2.) It shall be shown that natural hierarchies associated with certain gradings hold the key to the routing problem in these one-stage networks. It is now known2 that if a network possesses one of certain combinatorial properties, then this property can be used to describe in a simple way the optimal choices of routes for accepted calls so as to minimize the loss under perfect information.