Abstract

In this paper, a problem of rational splitter and OLT card installation in fiber-to-the-home (FTTH) networks is considered. We assume that the most tedious part of FTTH network deployment, i.e., trenching and cable installation, is completed, and the operator can start to connect customers to the network. The connecting process still requires expenditures for both passive (splitters) and active (ONUs, OLT cards) equipment. In this paper, we define the problem of rational splitter and OLT card deployment and present the multi-state optimization (MuSO) approach to handle it. MuSO minimizes the expected total cost of deployment using a stochastic model; thus, it optimizes under stochastic behavior. Finally, we compare MuSO to other rational methods, numerically validating its efficiency. We also investigate the impact of various factors—e.g., the take-up rates assumed when designing a network, delays in providing service to newly acquired customers, optimization time limits—on the final FTTH network deployment cost. The presented methodology not only can be used to minimize the deployment cost of FTTH networks, but also to assess the impact of uncertainty on network designs returned by automated methods.

© 2017 Optical Society of America

Full Article  |  PDF Article
OSA Recommended Articles
Techno-economic Evaluation of Open Access on FTTH Networks

Marlies Van der Wee, Koen Casier, Abhishek Dixit, Bart Lannoo, Sofie Verbrugge, Didier Colle, and Mario Pickavet
J. Opt. Commun. Netw. 7(5) 433-444 (2015)

Economics of Time and Wavelength Domain Multiplexed Passive Optical Networks

Theodoros Rokkas, Dimitris Katsianis, Thomas Kamalakis, and Dimitris Varoutas
J. Opt. Commun. Netw. 2(12) 1042-1051 (2010)

Hybrid Fiber-Wireless Network: An Optimization Framework for Survivable Deployment

Yinpeng Yu, Chathurika Ranaweera, Christina Lim, Lei Guo, Yejun Liu, Ampalavanapillai Nirmalathas, and Elaine Wong
J. Opt. Commun. Netw. 9(6) 466-478 (2017)

References

  • View by:
  • |
  • |
  • |

  1. J. Li and G. Shen, “Cost minimization planning for greenfield passive optical networks,” J. Opt. Commun. Netw., vol.  1, no. 1, pp. 17–29, 2009.
    [Crossref]
  2. M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FTTH network,” Eur. J. Oper. Res., vol.  222, pp. 430–440, 2012.
    [Crossref]
  3. C. Hervet and M. Chardy, “Passive optical network design under operations administration and maintenance considerations,” J. Appl. Oper. Res., vol.  222, no. 3, pp. 152–172, 2012.
  4. A. Bley, I. Ljubić, and O. Maurer, “Lagrangian decompositions for the two-level FTTx network design problem,” EURO J. Comput. Optim., vol.  1, no. 3, pp. 221–252, 2013.
    [Crossref]
  5. A. Mitcsenkov, G. Paksy, and T. Cinkler, “Geography- and infrastructure-aware topology design methodology for broadband access networks (FTTx),” Photon. Netw. Commun., vol.  21, no. 21, pp. 253–266, 2011.
    [Crossref]
  6. M. Żotkiewicz, M. Mycek, and A. Tomaszewski, “Profitable areas in large-scale FTTH network optimization,” Telecommun. Syst., vol.  61, no. 3, pp. 591–608, 2016.
    [Crossref]
  7. M. Grötschel, C. Raack, and A. Werner, “Towards optimizing the deployment of optical access networks,” EURO J. Comput. Optim., vol.  2, no. 1, pp. 17–53, 2013.
  8. J. Segarra, V. Sales, and J. Prat, “Planning and designing FTTH networks: Elements, tools and practical issues,” in 14th Int. Conf. on Transparent Optical Networks, Coventry, England, July 2012.
  9. K. F. Poon and A. Ouali, “A MILP based design tool for FTTH access networks with consideration of demand growth,” in 6th Int. Conf. on Internet Technology and Secured Transactions, Abu Dhabi, United Arab Emirates, Dec. 2011.
  10. C. Hervet, A. Faye, M.-C. Costa, M. Chardy, and S. Francfort, “Solving the two-stage robust FTTH network design problem under demand uncertainty,” in Int. Network Optimization Conf., Costa Adeje, Spain, May 2013.
  11. K. Casier, B. Lannoo, J. V. Ooteghem, S. Verbrugge, D. Colle, M. Pickavet, and P. Demeester, “Game-theoretic optimization of a fiber-to-the-home municipality network rollout,” J. Opt. Commun. Netw., vol.  1, no. 1, pp. 30–42, 2009.
    [Crossref]
  12. M. Żotkiewicz and M. Mycek, “Impact of demand uncertainty models on FTTH network design,” in 18th Int. Conf. on Transparent Optical Networks (ICTON), July10–14, 2016, pp. 1–4.
  13. R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. New York, New York: Plenum, 1972, pp. 85–103.
  14. M. Żotkiewicz, “Handling uncertain behavior of clients during FTTH splitter allocation,” in INFORMS Telecommunications Conf., Boca Raton, Florida, Mar.2016.
  15. E. Rogers, Diffusion of Innovations, 5th ed. New York, New York: Simon and Schuster, 2003.
  16. T. Dantzig, Numbers: The Language of Science.Hoboken, New Jersey: Wiley-Interscience, 1930.
  17. R. Andonov, V. Poirriez, and S. Rajopadhye, “Unbounded knapsack problem: Dynamic programming revisited,” Eur. J. Oper. Res., vol.  123, no. 2, pp. 394–407, 2000.
    [Crossref]

2016 (1)

M. Żotkiewicz, M. Mycek, and A. Tomaszewski, “Profitable areas in large-scale FTTH network optimization,” Telecommun. Syst., vol.  61, no. 3, pp. 591–608, 2016.
[Crossref]

2013 (2)

M. Grötschel, C. Raack, and A. Werner, “Towards optimizing the deployment of optical access networks,” EURO J. Comput. Optim., vol.  2, no. 1, pp. 17–53, 2013.

A. Bley, I. Ljubić, and O. Maurer, “Lagrangian decompositions for the two-level FTTx network design problem,” EURO J. Comput. Optim., vol.  1, no. 3, pp. 221–252, 2013.
[Crossref]

2012 (2)

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FTTH network,” Eur. J. Oper. Res., vol.  222, pp. 430–440, 2012.
[Crossref]

C. Hervet and M. Chardy, “Passive optical network design under operations administration and maintenance considerations,” J. Appl. Oper. Res., vol.  222, no. 3, pp. 152–172, 2012.

2011 (1)

A. Mitcsenkov, G. Paksy, and T. Cinkler, “Geography- and infrastructure-aware topology design methodology for broadband access networks (FTTx),” Photon. Netw. Commun., vol.  21, no. 21, pp. 253–266, 2011.
[Crossref]

2009 (2)

2000 (1)

R. Andonov, V. Poirriez, and S. Rajopadhye, “Unbounded knapsack problem: Dynamic programming revisited,” Eur. J. Oper. Res., vol.  123, no. 2, pp. 394–407, 2000.
[Crossref]

Andonov, R.

R. Andonov, V. Poirriez, and S. Rajopadhye, “Unbounded knapsack problem: Dynamic programming revisited,” Eur. J. Oper. Res., vol.  123, no. 2, pp. 394–407, 2000.
[Crossref]

Bley, A.

A. Bley, I. Ljubić, and O. Maurer, “Lagrangian decompositions for the two-level FTTx network design problem,” EURO J. Comput. Optim., vol.  1, no. 3, pp. 221–252, 2013.
[Crossref]

Casier, K.

Chardy, M.

C. Hervet and M. Chardy, “Passive optical network design under operations administration and maintenance considerations,” J. Appl. Oper. Res., vol.  222, no. 3, pp. 152–172, 2012.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FTTH network,” Eur. J. Oper. Res., vol.  222, pp. 430–440, 2012.
[Crossref]

C. Hervet, A. Faye, M.-C. Costa, M. Chardy, and S. Francfort, “Solving the two-stage robust FTTH network design problem under demand uncertainty,” in Int. Network Optimization Conf., Costa Adeje, Spain, May 2013.

Cinkler, T.

A. Mitcsenkov, G. Paksy, and T. Cinkler, “Geography- and infrastructure-aware topology design methodology for broadband access networks (FTTx),” Photon. Netw. Commun., vol.  21, no. 21, pp. 253–266, 2011.
[Crossref]

Colle, D.

Costa, M.-C.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FTTH network,” Eur. J. Oper. Res., vol.  222, pp. 430–440, 2012.
[Crossref]

C. Hervet, A. Faye, M.-C. Costa, M. Chardy, and S. Francfort, “Solving the two-stage robust FTTH network design problem under demand uncertainty,” in Int. Network Optimization Conf., Costa Adeje, Spain, May 2013.

Dantzig, T.

T. Dantzig, Numbers: The Language of Science.Hoboken, New Jersey: Wiley-Interscience, 1930.

Demeester, P.

Faye, A.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FTTH network,” Eur. J. Oper. Res., vol.  222, pp. 430–440, 2012.
[Crossref]

C. Hervet, A. Faye, M.-C. Costa, M. Chardy, and S. Francfort, “Solving the two-stage robust FTTH network design problem under demand uncertainty,” in Int. Network Optimization Conf., Costa Adeje, Spain, May 2013.

Francfort, S.

C. Hervet, A. Faye, M.-C. Costa, M. Chardy, and S. Francfort, “Solving the two-stage robust FTTH network design problem under demand uncertainty,” in Int. Network Optimization Conf., Costa Adeje, Spain, May 2013.

Grötschel, M.

M. Grötschel, C. Raack, and A. Werner, “Towards optimizing the deployment of optical access networks,” EURO J. Comput. Optim., vol.  2, no. 1, pp. 17–53, 2013.

Hervet, C.

C. Hervet and M. Chardy, “Passive optical network design under operations administration and maintenance considerations,” J. Appl. Oper. Res., vol.  222, no. 3, pp. 152–172, 2012.

C. Hervet, A. Faye, M.-C. Costa, M. Chardy, and S. Francfort, “Solving the two-stage robust FTTH network design problem under demand uncertainty,” in Int. Network Optimization Conf., Costa Adeje, Spain, May 2013.

Karp, R. M.

R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. New York, New York: Plenum, 1972, pp. 85–103.

Lannoo, B.

Li, J.

Ljubic, I.

A. Bley, I. Ljubić, and O. Maurer, “Lagrangian decompositions for the two-level FTTx network design problem,” EURO J. Comput. Optim., vol.  1, no. 3, pp. 221–252, 2013.
[Crossref]

Maurer, O.

A. Bley, I. Ljubić, and O. Maurer, “Lagrangian decompositions for the two-level FTTx network design problem,” EURO J. Comput. Optim., vol.  1, no. 3, pp. 221–252, 2013.
[Crossref]

Mitcsenkov, A.

A. Mitcsenkov, G. Paksy, and T. Cinkler, “Geography- and infrastructure-aware topology design methodology for broadband access networks (FTTx),” Photon. Netw. Commun., vol.  21, no. 21, pp. 253–266, 2011.
[Crossref]

Mycek, M.

M. Żotkiewicz, M. Mycek, and A. Tomaszewski, “Profitable areas in large-scale FTTH network optimization,” Telecommun. Syst., vol.  61, no. 3, pp. 591–608, 2016.
[Crossref]

M. Żotkiewicz and M. Mycek, “Impact of demand uncertainty models on FTTH network design,” in 18th Int. Conf. on Transparent Optical Networks (ICTON), July10–14, 2016, pp. 1–4.

Ooteghem, J. V.

Ouali, A.

K. F. Poon and A. Ouali, “A MILP based design tool for FTTH access networks with consideration of demand growth,” in 6th Int. Conf. on Internet Technology and Secured Transactions, Abu Dhabi, United Arab Emirates, Dec. 2011.

Paksy, G.

A. Mitcsenkov, G. Paksy, and T. Cinkler, “Geography- and infrastructure-aware topology design methodology for broadband access networks (FTTx),” Photon. Netw. Commun., vol.  21, no. 21, pp. 253–266, 2011.
[Crossref]

Pickavet, M.

Poirriez, V.

R. Andonov, V. Poirriez, and S. Rajopadhye, “Unbounded knapsack problem: Dynamic programming revisited,” Eur. J. Oper. Res., vol.  123, no. 2, pp. 394–407, 2000.
[Crossref]

Poon, K. F.

K. F. Poon and A. Ouali, “A MILP based design tool for FTTH access networks with consideration of demand growth,” in 6th Int. Conf. on Internet Technology and Secured Transactions, Abu Dhabi, United Arab Emirates, Dec. 2011.

Prat, J.

J. Segarra, V. Sales, and J. Prat, “Planning and designing FTTH networks: Elements, tools and practical issues,” in 14th Int. Conf. on Transparent Optical Networks, Coventry, England, July 2012.

Raack, C.

M. Grötschel, C. Raack, and A. Werner, “Towards optimizing the deployment of optical access networks,” EURO J. Comput. Optim., vol.  2, no. 1, pp. 17–53, 2013.

Rajopadhye, S.

R. Andonov, V. Poirriez, and S. Rajopadhye, “Unbounded knapsack problem: Dynamic programming revisited,” Eur. J. Oper. Res., vol.  123, no. 2, pp. 394–407, 2000.
[Crossref]

Rogers, E.

E. Rogers, Diffusion of Innovations, 5th ed. New York, New York: Simon and Schuster, 2003.

Sales, V.

J. Segarra, V. Sales, and J. Prat, “Planning and designing FTTH networks: Elements, tools and practical issues,” in 14th Int. Conf. on Transparent Optical Networks, Coventry, England, July 2012.

Segarra, J.

J. Segarra, V. Sales, and J. Prat, “Planning and designing FTTH networks: Elements, tools and practical issues,” in 14th Int. Conf. on Transparent Optical Networks, Coventry, England, July 2012.

Shen, G.

Tomaszewski, A.

M. Żotkiewicz, M. Mycek, and A. Tomaszewski, “Profitable areas in large-scale FTTH network optimization,” Telecommun. Syst., vol.  61, no. 3, pp. 591–608, 2016.
[Crossref]

Trampont, M.

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FTTH network,” Eur. J. Oper. Res., vol.  222, pp. 430–440, 2012.
[Crossref]

Verbrugge, S.

Werner, A.

M. Grötschel, C. Raack, and A. Werner, “Towards optimizing the deployment of optical access networks,” EURO J. Comput. Optim., vol.  2, no. 1, pp. 17–53, 2013.

Zotkiewicz, M.

M. Żotkiewicz, M. Mycek, and A. Tomaszewski, “Profitable areas in large-scale FTTH network optimization,” Telecommun. Syst., vol.  61, no. 3, pp. 591–608, 2016.
[Crossref]

M. Żotkiewicz, “Handling uncertain behavior of clients during FTTH splitter allocation,” in INFORMS Telecommunications Conf., Boca Raton, Florida, Mar.2016.

M. Żotkiewicz and M. Mycek, “Impact of demand uncertainty models on FTTH network design,” in 18th Int. Conf. on Transparent Optical Networks (ICTON), July10–14, 2016, pp. 1–4.

Eur. J. Oper. Res. (2)

M. Chardy, M.-C. Costa, A. Faye, and M. Trampont, “Optimizing splitter and fiber location in a multilevel optical FTTH network,” Eur. J. Oper. Res., vol.  222, pp. 430–440, 2012.
[Crossref]

R. Andonov, V. Poirriez, and S. Rajopadhye, “Unbounded knapsack problem: Dynamic programming revisited,” Eur. J. Oper. Res., vol.  123, no. 2, pp. 394–407, 2000.
[Crossref]

EURO J. Comput. Optim. (2)

A. Bley, I. Ljubić, and O. Maurer, “Lagrangian decompositions for the two-level FTTx network design problem,” EURO J. Comput. Optim., vol.  1, no. 3, pp. 221–252, 2013.
[Crossref]

M. Grötschel, C. Raack, and A. Werner, “Towards optimizing the deployment of optical access networks,” EURO J. Comput. Optim., vol.  2, no. 1, pp. 17–53, 2013.

J. Appl. Oper. Res. (1)

C. Hervet and M. Chardy, “Passive optical network design under operations administration and maintenance considerations,” J. Appl. Oper. Res., vol.  222, no. 3, pp. 152–172, 2012.

J. Opt. Commun. Netw. (2)

Photon. Netw. Commun. (1)

A. Mitcsenkov, G. Paksy, and T. Cinkler, “Geography- and infrastructure-aware topology design methodology for broadband access networks (FTTx),” Photon. Netw. Commun., vol.  21, no. 21, pp. 253–266, 2011.
[Crossref]

Telecommun. Syst. (1)

M. Żotkiewicz, M. Mycek, and A. Tomaszewski, “Profitable areas in large-scale FTTH network optimization,” Telecommun. Syst., vol.  61, no. 3, pp. 591–608, 2016.
[Crossref]

Other (8)

J. Segarra, V. Sales, and J. Prat, “Planning and designing FTTH networks: Elements, tools and practical issues,” in 14th Int. Conf. on Transparent Optical Networks, Coventry, England, July 2012.

K. F. Poon and A. Ouali, “A MILP based design tool for FTTH access networks with consideration of demand growth,” in 6th Int. Conf. on Internet Technology and Secured Transactions, Abu Dhabi, United Arab Emirates, Dec. 2011.

C. Hervet, A. Faye, M.-C. Costa, M. Chardy, and S. Francfort, “Solving the two-stage robust FTTH network design problem under demand uncertainty,” in Int. Network Optimization Conf., Costa Adeje, Spain, May 2013.

M. Żotkiewicz and M. Mycek, “Impact of demand uncertainty models on FTTH network design,” in 18th Int. Conf. on Transparent Optical Networks (ICTON), July10–14, 2016, pp. 1–4.

R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. New York, New York: Plenum, 1972, pp. 85–103.

M. Żotkiewicz, “Handling uncertain behavior of clients during FTTH splitter allocation,” in INFORMS Telecommunications Conf., Boca Raton, Florida, Mar.2016.

E. Rogers, Diffusion of Innovations, 5th ed. New York, New York: Simon and Schuster, 2003.

T. Dantzig, Numbers: The Language of Science.Hoboken, New Jersey: Wiley-Interscience, 1930.

Cited By

OSA participates in Crossref's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (8)

Fig. 1.
Fig. 1. Two MDUs connected to a central office.
Fig. 2.
Fig. 2. Take-up rate probability mass functions.
Fig. 3.
Fig. 3. Equipment set E divided into subsets.
Fig. 4.
Fig. 4. Number of access points in considered FTTH tree instances. (a) FTTH tree instances obtained for 30% take-up rate and (b) FTTH tree instances obtained for 50% take-up rate.
Fig. 5.
Fig. 5. Obtained gain compared to the local (naive) solution; 100% gain is for the oracle.
Fig. 6.
Fig. 6. Impact of using different numbers of final states.
Fig. 7.
Fig. 7. Runtime: (a) final states and (b) time periods.
Fig. 8.
Fig. 8. Gain obtained for different distributions.

Tables (4)

Tables Icon

TABLE I Splitter and OLT Port Costs

Tables Icon

Algorithm 1: Dynamic equipment allocation process

Tables Icon

Algorithm 2: Multi-state optimization

Tables Icon

Algorithm 3: Trimming results

Equations (14)

Equations on this page are rendered with MathJax. Learn more.

min e E , t = max T x e t ξ ( e ) ,
e E a x e t o ( e ) c C : t ( c ) t d ( c , a )    a A ,    t T ,
x e t o ( e ) e E e x e t    e E ,    t T ,
x e t u ( e )    e E ,    t T ,
x e t x e t    e E ,    t , t T : t < t .
min e E , s S y e s ξ ( e ) p ( s ) ,
e E a y e s o ( e ) b ( a , s )    a A ,    s S ,
y e s o ( e ) e E e y e s    e E ,    s S ,
y e s u ( e )    e E ,    s S ,
y e s x e t    e E ,    s S ,
e E a x e t o ( e ) g ( a )    a A ,
x e t l ( e )    e E .
n ( e ) = min s S y e s l ( e ) .
m ( a ) = g ( a ) e E a l ( e ) o ( e ) .