Abstract
With the advent of non-hierarchical routing in circuit-switched telecommunication networks, on-line routing policies have been developed with the objective of optimizing some measure of gain or performance. These policies are decentralized. However, traditional planning models are centralized models. We present a decentralized routing model to be used in network planning. We compare it theoretically and empirically with a centralized multicommodity flow model previously presented. The two models are solved by the same type of algorithm, a convex simplex implementation, adapted differently according to the model. Comparative results between planning models reproducing the two policies are discussed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.M. Akinpelu, The overload performance of engineered networks with non-hierarchical and hierarchical routing,Int. Teletraffic Congress 10(1983), pp. 3.2.4.1–3.2.4.7.
A.A. Assad, Multicommodity network flows. A survey, Networks 8(1978)37–91.
V.E. Benes, Programming and control problems arising from optimal routing in telephone networks, Bell. Syst. Tech. J (1966).
S. Dafermos and F.T. Sparrow, The traffic assignment problem for a general network, J. Res. National Bureau of Standards — B. Math. Sci. 73B(1969)91–118.
P.J. Deschamps, Analytic approximation of blocking probabilities in circuit switched communication networks, IEEE Trans. Commun. COM-27(1979)603–606.
Z. Dziong, M. Pioro, U. Korner and T. Wickberg, On adaptative call routing strategies in circuit switched networks. Maximum revenue approach,Proc. Int. Teletraffic Congress 12(1988), pp. 3.1A5–3.1A8.
L. Fratta, M. Gerla and L. Kleinrock, The flow deviation method: An approach to store-and-forward communication network design, Networks 3(1973)97–133.
R.G. Gallager, A minimum delay routing algorithm using distributed computation, IEEE Trans. Commun. COM-25(1977)73–85.
B. Gavish and L. Hantler, An algorithm for optimal route selection in SNA networks, IEEE Trans. Commun. COM 31(1983)1154–1159.
A. Girad and R. Pagé, Dimensioning of telephone networks with non-hierarchical routing and trunk reservation,Proc. IEEE 3rd Network Planning Symp., Innisbrok, FL (1986).
A. Girard,Routing and Dimensioning in Circuit Switched Networks (Addison-Wesley, 1990).
J.H. Hammond and L. Magnanti, Generalized descent methods for asymmetric systems of equations, Math. Oper. Res. 12(1987)678–699.
A. Harel, Convexity properties of the Erlang loss formula, Oper. Res. 38(1990)499–505.
A.A. Jagers and E.A. Van Doorn, On the continued Erlang loss function, Oper. Res. Lett. 5(1986)43–46.
F.P. Kelly, Routing in circuit-switched networks: Optimization, shadow prices and decentralization, Adv. Appl. Prob. 20(1988)122–144.
K.R. Krishnan, Routing of telephone traffic to minimize network blocking,IEEE Proc. Conf. on Decision and Control 21(1982), pp. 375–377.
L.G. Mason and A. Girard, Control techniques and performance models for circuit switched networks,IEEE Proc. Conf. on Decision and Control 21(1982), pp. 1374–1383.
L.G. Mason, Equilibrium flows, routing patterns and algorithms for store-and-forward network, Large Scale Syst. 8(1985)187–208.
L.G. Mason, On the stability of circuit-switched networks with non-hierarchical routing,Proc. Conf. on Decision and Control, Athens (1986), pp. 1345–1347.
E.J. Messerli, Proof of a convexity property of the Erlang B formula, Bell. Syst. Tech. J. 51(1972)951–953.
Y. Nakagome and H. Mori, Flexible routing in a global communication network,Int. Teletraffic Congress 7(1973), pp. 426.1–426.8.
S. Nguyen, Une approche unifiée des méthodes d'équilibre pour l'affectation du trafic, Ph.D. Dissertation, Université de Montréal (1973).
J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, 1970).
C. Palm, Some observations on the Erlang formulae for busy-signal systems, TELE 1 (1957) (English ed.).
B. Sansó, Fiabilité et routage dans un réseau de télécommunications, Ph.D. Dissertation, Department of Applied Mathematics, Ecole Polytechnique de Montréal (1988).
B. Sansó, F. Soumis and G. Gendreau, On the evaluation of telecommunication networks reliability using routing models, IEEE Trans. Commun. COM-39(1991)1494–1501.
B. Sansó, M. Gendreau and F. Soumis, An algorithm for network dimensioning under reliability considerations, Ann. Oper. Res. 36(1992)263–274.
M. Sauvé, Résolution numérique du problème de multiflot compatible à coût minimum, Centre de recherche sur les transports, publication 409 (1984).
J.G. Wardrop, Some theoretical aspects of road traffic research, Proc. Institute of Civil Engineers, Part II (1952), pp. 325–378.
R.J. Wilkinson, Theories for toll traffic engineering in the USA, Bell Syst. Tech. J. 35(1956)421–514.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sansó, B., Soumis, F. & Gendreau, M. Centralized and decentralized stochastic routing models in telecommunication networks. Telecommunication Systems 1, 133–148 (1993). https://doi.org/10.1007/BF02136158
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02136158