Programming and Control Problems Arising from Optimal Routing in Telephone Networks

A telephone connecting network invariably provides many paths on which a particular telephone call can be completed. One of the operational problems faced by the control unit of a telephone system is then to assign to each accepted and completable call a path and, in particular, to choose these assigned paths in the best way. This is the problem of optimal routing of telephone calls. Thus, in the theory of telephone traffic there naturally arise mathematical problems of optimal routing, that is, of making choices of routes in probabilistic models for operating networks so as to achieve extrema of well-defined measures of system performance, such as the probability of blocking (loss). Unfortunately, it is not unfair to state that the voluminous probabilistic theory of telephone traffic, now some sixty years old, still has rather little to say about how routes for calls should be chosen. We are speaking here of the mathematical theory of traffic. Naturally, a wealth of useful information about routing has accumulated over the years from experience in the telephone field; recently it has been buttressed and extended by many simulation studies. This information, nevertheless, still lies largely outside the province of the existing theory of telephone traffic. It is the aim of this work to formulate, study, and (in part) solve a