×

Adaptive traffic routing in telephone networks. (English) Zbl 0574.90025

The paper deals with adaptive routing in large telephone networks subject to disturbances such as transmission failures and traffic overloads. Several solutions are reviewed considering items such as control structure, information pattern and traffic routing policy.
First, we consider the case of perfect information in which the microscopic state of the network is assumed to be known and available for making routing decisions: efficient algorithms such that successive approximations (White) or the dual method (Varaiya) can be used to solve that Markov routing decision problem. This approach is of course far from realistic but it can be used on small representative networks to help the design of good ”suboptimal” control policies.
Then, we attempt to state different routing problems based on an aggregate model describing the network. The control problem is to compute the best solution within a class of control parameters (load sharing, alternate routing) or to adapt the control parameters by a feedback policy. The load-sharing schemes are classified according to the information on which the routing scheme is elaborated: (1) Learning automata need only local information: the response of the environment for each call (success or rejection). (2) Other schemes need more elaborate information such as estimation of traffic and efficiencies of call flows. These schemes act periodically in a centralized or a decentralized way according to the amount of informations treated.
Concerning overflow, routing tables can be updated in a decentralized way according to some congestion index (residual capacity or stochastic residual capacity) or in a centralized approach (deterministic residual capacity with reserved capacities for direct traffic; generalized overflow policy).

MSC:

90B10 Deterministic network models in operations research
90C40 Markov and semi-Markov decision processes
PDFBibTeX XMLCite