Abstract
In this paper we introduce a new methodology to adjust link capacities in circuit switched networks taking into account the costing policy and reliability considerations. This methodology, which is an extension of previous work on reliability evaluation using routing models, is based on a cyclic decomposition algorithm which alternates between a routing subproblem and a link capacity adjustment subproblem. The proposed procedure, which is shown to converge to a global optimum for the dimensioning/routing problem, has been tested on a 14 undirected arc problem for various levels of link failure probability. The numerical results are extremely satisfactory and they demonstrate the usefulness of the proposed method for proper network dimensioning.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Girard and R. Pagé, Dimensioning of telephone networks with nonhierarchical routing and trunk reservation,Proc. IEEE 3rd Network Planning Symp., Innisbrook, Florida (1986).
L. Fratta, M. Gerla and L. Kleinrock, The flow deviation algorithm: an approach to store-and-forward computer communication network design, Networks 3 (1973) 97–133.
D.P. Bertsekas, A class of optimal routing algorithms for communication networks,Proc. Int. Conf. on Circuits and Computers, Atlanta, Georgia (1980).
B. Gavish and S.L. Hantler, An algorithm for optimal route selection in SNA networks, IEEE Trans. Commun. COM-31 (1983) 1154–1161.
M. Gerla and L. Kleinrock,, On the topological design of distributed computer networks, IEEE Trans. Commun. COM-25 (1977) 48–50.
K. Maruyanna and D.T. Tang, Discrete link capacity assignment in communication networks,3rd ICC, Toronto (1976) pp. 97–97.
B. Gavish and I. Newman, A system for routing and capacity assignment in computer communication networks, IEEE Trans. Commun. COM-37 (1989) 360–366.
B. Gavish, A general model for the topological design of computer networks,Proc. GLOBE-COM '86, IEEE Global Telecommunication Conf. (1986).
E. Rosenberg, A nonlinear programming heuristic for computing optimal link capacities in a multi-hours alternate routing communications network, Oper. Res. 3 (1987) 354–364.
L.J. Leblanc and R.V. Simmons, Continuous models for capacity design of large packet-switched telecommunication networks, ORSA J. Comput. 1 (1989) 271–286.
B. Gavish, P. Trudeau, M. Dror, M. Gendreau and L. Mason, Fiberoptic circuit network design under reliability constraints, IEEE J-SAC, Special issue on Telecommunications Network Design and Planning (1989) 1181–1187.
I. Newman and B. Gavish, A new approach to reliable routing in computer networks,CORS/TIMES/ORSA Joint National Meeting, Vancouver (1989).
B. Sansó, Fiabilité et routage dans un réseau de télécommunications, publication No. 605, Centre de recherche sur les transports, Université de Montréal (1988).
B. Sansó, F. Soumis and M. Gendreau, On the evaluation of telecommunications network reliability using routing models, publication No. 623, Centre de recherche sur les transports, Université de Montréal (1989).
A.A. Jagers and E.A. Van Doorn, On the continued Erlang loss function, Oper. Res. Lett. 5 (1986) 43–46.
C. Palme, Some observations on the Erlang formulae for busy-signal systems,TELE, English Edition, no. 1 (1957) pp. 1–168.
E. Hansler, G.K. Mcauliffe and R.S. Wilkov, Exact calculation of computer network reliability, Networks 4 (1974) 95–112.
L. Fratta and U.G. Montanari, A Boolean algebra method for computing the terminal reliability in a communication network, IEEE Trans. Circuit Theory CT-20 (1973) 203–211.
S. Provan and M.O. Ball, Computing network reliability in time polynomial in the number of cuts, Oper. Res. 2 (1984) 516–526.
M.O. Ball, Computing network reliability, Oper. Res. 27 (4) (1979) 823–838.
V.O.K. Li and J.A. Silvester, Performance analysis of networks with unreliable components, IEEE Trans. Commun. COM-32 (1984) 1105–1110.
R.F. Gaebler and R.J. Chen, An efficient algorithm for enumerating states of a system with multimode unreliable components, working paper presented at theORSA-TIMS, St-Louis meeting (1987) talk TC30.5.
R. Wong, Introduction and Recent Advances in network design: models and algorithms, in:Transportation Planning Models, ed. M. Florian (Elsevier Science/North-Holland, 1984) pp. 187–225.
D.L. Jagerman, Some properties of the Erlang loss function, Bell Sys. Tech. J. 53 (1974) 525–551.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sansó, B., Gendreau, M. & Soumis, F. An algorithm for network dimensioning under reliability considerations. Ann Oper Res 36, 263–274 (1992). https://doi.org/10.1007/BF02094333
Issue Date:
DOI: https://doi.org/10.1007/BF02094333