Abstract
The rapid progress of communications technology has created new opportunities for modeling and optimizing the design of local telecommunication systems. The complexity, diversity, and continuous evolution of these networks pose several modeling challenges. In this paper, we present an overview of the local telephone network environment, and discuss possible modeling approaches. In particular, we (i) discuss the engineering characteristics of the network, and introduce terminology that is commonly used in the communications industry and literature; (ii) describe a general local access network planning model and framework, and motivate different possible modeling assumptions; (iii) summarize various existing planning models in the context of this framework; and (iv) describe some new modeling approaches. The discussion in this paper is directed both to researchers interested in modeling local telecommunications systems and to planners interested in using such models. Our goal is to present relevant aspects of the engineering environment for local access telecommunication networks, and to discuss the relationship between engineering issues and the formulation of economic decision models. We indicate how changes in the underlying switching and transmission technology affect the modeling of the local telephone network. We also review various planning issues and discuss possible optimization approaches for treating them.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Anderson, Fiber optics for loop applications: A techno-economical analysis,Proc. Int. Symp. on Subscriber Loops and Services (1988), pp. 213–216.
R. Araque, L.A. Hall and T.L. Magnanti, Capacitated trees, capacitated routing, and associated polyhedra, Working Paper OR-232-90, Operations Research Center, M.I.T., Cambridge (1990).
AT&T Bell Laboratories,Engineering and Operations in the Bell System, Murray Hill, NJ (1986).
L.R. Bahl and D.T. Tang, Optimization of concentrator locations in teleprocessing networks,Proc. Symp. on Computer Communication Networks and Teletraffic (1972).
A. Balakrishnan, T.L. Magnanti and R.T. Wong, A dual ascent procedure for large-scale uncapacitated network design, Oper. Res. 37(1989)716–740.
A. Balakrishnan, T.L. Magnanti and R.T. Wong, Local access telecommunication network expansion: Modeling and polyhedral characterization (1990), in preparation.
A. Balakrishnan, T.L. Magnanti and R.T. Wong, A decomposition approach for expanding local access telecommunication networks (1990), in preparation.
I. Barany, J. Edmonds and L.A. Wolsey, Packing and covering a tree by subtrees, Combinatorica 6(1986)221–233.
J. Billheimer and P. Gray, Network design with fixed and variable cost elements, Trans. Sci. 7(1973)49–74.
T.B. Boffey and A.I. Hinxman, Solving the optimal network problem, Eur. J. Oper. Res. 3(1979)386–393.
R.B. Boorstyn and H. Frank, Large-scale network topological optimization, IEEE Trans. Comm. COM-25(1977)29–47.
D.E. Boyce, A. Farhi and R. Weischedel, Optimal network problem: A branch-and-bound algorithm, Environ. Planning 5(1973)519–533.
B. Bulcha, L.E. Kodrich, D.B. Luber, W.J. Mitchell, M.A. Schwartz and F.N. Woomer, Feeder planning methods for digital loop carrier, The Bell Sys. Tech. J. 61(1982)2129–2141.
L.H. Campbell, The evolution from narrowband to broadband customer access,Proc. Int. Symp. on Subscriber Loops and Services (1988), pp. 144–148.
G.D. Carse, New and future technologies in the local telephone network: The Victoria system,Proc. IEEE 1986 Int. Communications Conf. (1986), pp. 410–412.
K.M. Chandy and T. Lo, The capacitated minimum spanning tree, Networks 3(1973)173–182.
K.M. Chandy and R.A. Russell, The design of multipoint linkages in a teleprocessing tree network, IEEE Trans. Computers C-21(1972)1062–1066.
A.J. Ciesielka and D.C. Douglas, Electronics in the suburban and light urban loop networks, The Bell Sys. Tech. J. 59(1980)417–439.
A.J. Ciesielka and N.G. Long, New technology for loops — A plan for the '80's, IEEE Trans. Comm. COM-28(1980)923–930.
L. Coathup, J.-P. Poirier, D. Poirier and D. Kahn, Fiber to the home — Technology and architecture drives,Proc. Int. Symp. on Subscriber Loops and Services (1988), pp. 281–285.
J.-P. Combot and N. Epstein, The introduction of digital switching to the local network, IEEE Trans. Comm. COM-27(1979)1056–1064.
J.-P. Combot, M.S.C. Tsui and R. Weihmayer, Optimal digital switching introduction into the local network, IEEE Trans. Comm. COM-29(1981)1446–1454.
G. Cornuejols, R. Sridharan and J.M. Thizy, A comparison of heuristics and relaxations for the capacitated plant location problem, Working Paper, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh (1987).
C.S. Dawson, R.B. Murphy and E. Wolman, A history of operations research at Bell Laboratories (1925–1975), AT&T Bell Laboratories Report, NJ (1984).
R. Dettmer, The integrated services digital network: Bringing home the bits, Electronics and Power (1985)25–28.
R. Dionne and M. Florian, Exact and approximate algorithms for optimal network design, Networks 9(1979)37–59.
H. Direlten and R.W. Donaldson, Topological design of teleprocessing networks using linear regression clustering, IEEE Trans. Comm. COM-24(1976)1152–1159.
T.R. Elken, The application of mathematical programming to loop feeder allocation, The Bell Sys. Tech. J. 59(1980)479–500.
W.E. Ensdorf, M.L. Keller and C.R. Kowal, Economic considerations of fiber in the loop plant,Proc. Int. Symp. on Subscriber Loops and Services (1988), pp. 291–296.
L.R. Esau and K.C. Williams, On teleprocessing system design: Part II, IBM Sys. J. 5(1966)142–147.
M.L. Fisher and D.S. Hochbaum, Database location in computer networks, J. ACM 27(1980)718–735.
Fortune, ISDN: The new telephone network (November 1988).
R.L. Francis and P.B. Mirchandani (eds.),Discrete Location Theory (Wiley-Interscience, New York, 1990).
J. Freidenfelds and C.D. McLaughlin, A heuristic branch-and-bound algorithm for telephone feeder capacity expansion, Oper. Res. 27(1979)567–582.
L.F. Garbanati and J.R. Palladino, Fiber optics to the subscriber: Objectives, costs and technology assessment,Proc. Int. Symp. on Subscriber Loops and Services (1988), pp. 286–290.
B. Gavish, Formulations and algorithms for the capacitated minimal directed tree, J. ACM 30(1983)118–132.
B. Gavish and K. Altinkemer, Parallel savings heuristic for the topological design of local access tree networks,Proc. IEEE INFOCOM '86 (1986), pp. 130–139.
A.E. Gibson and D.B. Luber, Critical section methods for loop plant allocation, The Bell Sys. Tech. J. 59(1980)99–117.
J.M. Griffiths,Local Telecommunications 2: Into the Digital Era (P. Peregrinus, London, 1988).
M. Groetschel and C.L. Monma, Integer polyhedra arising from certain network design problems with connectivity constraints, Report No. 104, Institut für Mathematik, Universität Augsburg, Augsburg, Germany (1988).
M. Haimovich and T.L. Magnanti, Extremum properties of hexagonal partitioning and the uniform distribution in Euclidean location, SIAM J. Discr. Math. 1(1988)50–64.
L.A. Hall, Polyhedral structure of capacitated trees and approximation methods for deterministic scheduling, Ph.D. Thesis, Operations Research Center, MIT (1989).
M.P. Helme, C. Jack and A. Shulman, Planning for new services in the local loop,Proc. Int. Telecommunication Conf. 12 (1988), pp. 5.2B.1.1–5.2.B.1.12.
H.H. Hoang, A computational approach to the selection of an optimal network, Manag. Sci. 19(1973)488–498.
H.H. Hoang and H.T. Lau, Optimizing the evolution of digital switching in a local telephone network,Proc. IEEE Int. Conf. on Communications (1984), pp. 179–184.
D.S. Johnson, J.K. Lenstra and A.H.G. Rinnooy Kan, The complexity of the network design problem, Networks 8(1978)279–285.
O. Kariv and S.L. Hakimi, An algorithmic approach to network location problems II: Thep-medians, SIAM J. Appl. Math. 27(1979)539–560.
A. Kershenbaum and R.B. Boorstyn, Centralized teleprocessing network design,Proc. Nat. Telecommunications Conf. (1975), pp. 27.11–27.14.
A. Kershenbaum and W. Chou, A unified algorithm for designing multidrop teleprocessing networks, IEEE Trans. Comm. COM-22(1974)1762–1772.
A. Kershenbaum and S. Peng, Neighbor finding algorithms for CMST calculation,Proc. IEEE INFOCOM '86 (1986), pp. 140–147.
V.K. Konangi, T. Aidja and C.R. Dhas, On the multilevel concentrator location problem for local access networks,Proc. IEEE Globecom '84 (1984), pp. 912–915.
W.L.G. Koontz, Economic evaluation of loop feeder relief alternatives, The Bell Sys. Tech. J. 59(1980)277–293.
P. Kopp, A family of solution procedures for the routing problem in medium-term planning of mixed analog-digital transmission networks,Proc. 3rd Int. Networks Symp. (1986), pp. 138–142.
D.J. Kostas, Transition to ISDN — An overview, IEEE Comm. Magazine 22(1984)11–17.
P. Kubat, Models for allocation of remote switching units to a local area access network, Internal Report, GTE Laboratories, Inc., Waltham, MA (1985).
J.S. Lavin, Optimally rehoming local serving offices to a new point of presence, AT&T Tech. J. 66(1987)50–54.
P. Lemke and R.T. Wong, Characterizations and descriptions of facets for thek-median location problem (1990), in preparation.
J. Leung and T.L. Magnanti, Valid inequalities and facets for capacitated plant location problems, Math. Progr. 44(1989)271–292.
H.P.L. Luna, N. Ziviani and R.H.B. Cabral, The telephonic switching centre network problem: Formalization and computational experience, Discr. Appl. Math. 18(1987)199–210.
T.L. Magnanti and R.T. Wong, Network design and transportation planning: Models and algorithms, Trans. Sci. 18(1984)1–55.
L.G. Mason, Network modernization with capital budget constraints,Network Planning Symp., Brighton, UK (1983), pp. 5–9.
L.G. Mason, An aggregate model for network modernization with constraints, IEEE Trans. Comm. COM-32(1984)1073–1079.
L.G. Mason and J.-P. Combot, Optimal modernization policies for telecommunications facilities, IEEE Trans. Comm. COM-28(1980)317–324.
U. Mazzei, C. Mazzetti and G. Roso, Economics of digital carriers and fiber optic systems in subscriber loops,Proc. Int. Symp. on Subscriber Loops and Services (1988), pp. 133–137.
P. McGregor and D. Shen, Network design: An algorithm for the access facility location problem, IEEE Trans. Comm. COM-25(1977)61–73.
M. Minoux, Network synthesis and dynamic network optimization, Ann. Discr. Math. 31(1987)283–324.
M. Minoux, Network synthesis and optimum network design problems: Models, solution methods and applications, Networks 19(1989)313–360.
A. Mirzaian, Lagrangian relaxation for the star-star concentrator location problem, Networks 15(1985)1–20.
C.L. Monma and D.F. Shallcross, Methods for designing communication networks with certain two-connected survivability constraints, Oper. Res. 37(1989)531–541.
G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (Wiley-Interscience, New York, 1988).
C.H. Papadimitriou, Worst case and probabilistic analysis of a geometric location problem, SIAM J. Comput. 10(1981)542–557.
H. Pirkul, Location of concentrators in designing local access networks,Proc. IEEE INFOCOM '86 (1986), pp. 148–154.
H. Pirkul, S. Narasimhan and P. De, Locating concentrators for primary and secondary coverage in a computer communication network, IEEE Trans. Comm. 36(1988)450–458.
G. Rousset and H. Cameron, Design and optimization of private data networks,Proc. 3rd Int. Network Planning Symp. (1986), pp. 50–54.
G.M. Schneider and M.N. Zastrow, An algorithm for the design of multilevel concentrator networks, Computer Networks 6(1982)1–11.
S. Sen, R.D. Doverspike and M.S. Dunatunga, Unified facilities optimizer, Working Paper, Systems and Industrial Engineering Department, University of Arizona, Tucson (1989).
R.L. Sharma, Design of an economical multidrop network topology with capacity constraints, IEEE Trans. Comm. COM-31(1983)590–591.
A. Shulman and R. Vachani, An algorithm for capacity expansion of local access networks,Proc. IEEE INFOCOM '90 (1990), pp. 221–230.
M.A. Sirbu and D.P. Reed, An optimal investment strategy model for fiber to the home,Proc. Int. Symp. on Subscriber Loops and Services (1988), pp. 149–155.
R.K. Snelling and K.W. Kaplan, Current and future fiber optics applications — Operating telephone company perspective,Proc. IEEE Globecom '84 (1984), pp. 604–607.
D.T. Tang, L.S. Woo and L.R. Bahl, Optimization of teleprocessing networks with concentrators and multiple connected terminals, IEEE Trans. Comput. C-27(1978)594–604.
The Economist, A survey of telecommunications: New lines for old (October, 1987), pp. 3–34.
A.G. Toth, E. Colombini, P.J. MacLaren and R.K. Yates, Fiber in the local exchange network: A planning overview,Proc. IEEE Int. Communications Conf. (1985), pp. 520–526.
J.E. Ward, R.T. Wong, P. Lemke and A. Oudjit, Properties of the treek-median linear programming relaxations, Working Paper, Krannert Graduate School of Management, Purdue University, West Lafayette (1988).
P.E. White, The broadband ISDN — The next generation telecommunications network,Proc. IEEE 1986 Int. Communications Conf. (1986), pp. 385–390.
L.S. Woo and D.T. Tang, Optimization of teleprocessing networks with concentrators,Proc. Nat. Telecommunications Conf. (1973), pp. 37C1–37C5.
Y. Yamamoto, H. Yamamoto and H. Oikawa, Access network design with optical fibers,Proc. IEEE Globecom '84 (1984), pp. 637–641.
Author information
Authors and Affiliations
Additional information
This research was initiated through a grant from GTE Laboratories, Incorporated
Supported in part by an AT&T research award.
Supported in part by Grant No. ECS-8316224 from the Systems Theory and Operations Research Program of the National Science Foundation.
Rights and permissions
About this article
Cite this article
Balakrishnan, A., Magnanti, T.L., Shulman, A. et al. Models for planning capacity expansion in local access telecommunication networks. Ann Oper Res 33, 237–284 (1991). https://doi.org/10.1007/BF02071976
Issue Date:
DOI: https://doi.org/10.1007/BF02071976