Abstract

The large investments required for deploying passive optical networks (PONs) render the disposal of appropriate planning tools for designing such networks in a cost-effective way a necessity. This paper addresses the problem of finding the least costly tree topology time-division multiplexing PON (TDM-PON) deployment configurations considering equipment and installation costs (CAPEX) and operational exploration costs. With this purpose, an integer linear programing model is developed, which is capable of designing not only common single-stage PON configurations, but also PONs with multiple stages of optical splitting. In order to reduce the computation time for problems of larger size, a two-stage heuristic is also proposed. The simulation results for the cases studied reveal that an optimal multistage splitting strategy can lead to cost savings of up to 15% in CAPEX expenditures in comparison with the traditional single-stage approach. Furthermore, the heuristic procedure proposed is shown to obtain results within acceptable bounds relative to the optimum solutions, hence validating its use for larger sized networks. The results also show that the average CAPEX cost savings between the two-stage and single-stage approaches are quite dependent on the strategies used to choose candidate locations for the splitters, with values ranging from 5 to 12% depending on whether random candidate placement or k-means-based placement is used.

© 2012 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. Nielsen, “Nielsen’s law of internet bandwidth,” 2010 [Online]. Available: http://www.useit.com/alertbox/980405.html.
  2. R. E. Wagner, J. R. Igel, R. Whitman, M. D. Vaughn, A. B. Ruffin, and S. Bickham, “Fiber-based broadband-access deployment in the United States,” J. Lightwave Technol., vol. 24, no. 12, pp. 4526–4540, 2006.
    [CrossRef]
  3. F. Effenberger, K. McCammon, and V. O’Byrne, “Passive optical network deployment in North America [invited],” J. Opt. Netw., vol. 6, no. 7, pp. 808–818, 2007.
    [CrossRef]
  4. “10 Gb/s Ethernet passive optical network,” IEEE Standard 802.3av, 2009.
  5. “Gigabit-capable passive optical networks (XG-PON): General Requirements,” ITU-T Recommendation G.987.1, 2010.
  6. S. Jain, F. Effenberger, A. Szabo, F. Zhishan, A. Forcucci, G. Wei, L. Yuanqiu, R. Mapes, Z. Yixin, and V. O’Byrne, “World’s first XG-PON field trial,” J. Lightwave Technol., vol. 29, no. 4, pp. 524–528, 2011.
    [CrossRef]
  7. J. Salgado, P. M. Cheia, C. Rodrigues, M. Bernardo, and J. Figueiredo, “Evolution of access networks from GPON to XGPON to WDM-PON from operator point-of-view,” in 15th European Conf. on Networks and Optical Communications (NOC), Faro, Portugal, 2010.
  8. G. Keiser, FTTX Concepts and Applications. John Wiley & Sons, New Jersey, 2006.
  9. S. U. Kahn, “Heuristics-based PON deployment,” IEEE Commun. Lett., vol. 9, no. 9, pp. 847–849, 2005.
    [CrossRef]
  10. B. Lakic and M. Hajduczenia, “On optimized passive optical network (PON) deployment,” in 2nd Int. Conf. on Access Networks (ACCESSNETS), Ottawa, Canada, 2007.
  11. B. Lakic, M. Hajduczenia, H. Silva, and P. Monteiro, “Using adapted visibility graphs for network planning,” in IEEE Symp. on Computers and Communications (ISCC), Marrakech, Morroco, 2008.
  12. M. Hajduczenia, B. Lakic, H. Silva, and P. Monteiro, “Optimized passive optical network deployment,” J. Opt. Netw., vol. 6, no. 9, pp. 1079–1104, 2007.
    [CrossRef]
  13. 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]
  14. M. Lv and X. Chen, “Heuristic based multi-hierarchy passive optical network planning,” in 5th Int. Conf. on Wireless Communications, Networking and Mobile Computing (WiCom), Beijing, China, 2009.
  15. C. Lam, Passive Optical Networks: Principles and Practice. Elsevier, 2007.
  16. R. Boorstyn and H. Frank, “Large-scale network topological optimization,” IEEE Trans. Commun., vol. 25, no. 1, pp. 29–47, 1977.
    [CrossRef]
  17. G. Schneider and M. Zastrov, “An algorithm for the design of multilevel concentrator networks,” Comput. Netw., vol. 6, no. 1, pp. 1–11, 1982.
  18. S. Narasimhan and H. Pirkul, “Hierarchical concentrator location problem,” Comput. Commun., vol. 15, no. 3, pp. 185–191, 1992.
    [CrossRef]
  19. A. Mirzaian and K. Steiglitz, “A note on the complexity of the star–star concentrator problem,” IEEE Trans. Commun., vol. 29, no. 10, pp. 1549–1552, 1981.
    [CrossRef]
  20. J. Chen, L. Wosinska, C. Mas Machuca, and M. Jaeger, “Cost vs. reliability performance study of fiber access network architectures,” IEEE Commun. Mag., vol. 48, no. 2, pp. 56–65, 2010.
    [CrossRef]
  21. S. Aleksic and A. Lovric, “Power consumption of wired access network technologies,” in 7th Int. Symp. on Communication Systems, Networks and Digital Signal Processing (CSNDSP), Newcastle, United Kingdom, 2010.
  22. J. B. Macqueen, “Some methods for classification and analysis of multivariate observations,” in 5th Berkeley Symp. on Mathematical Statistics and Probability, Berkeley, United States, 1967.
  23. C. Mas Machuca, J. Chen, and L. Wosinska, “Cost dependency on protection of optical access networks for dense urban areas,” in 13th Int. Conf. on Transparent Optical Networks (ICTON), Stockholm, Sweden, 2011.

2011 (1)

2010 (1)

J. Chen, L. Wosinska, C. Mas Machuca, and M. Jaeger, “Cost vs. reliability performance study of fiber access network architectures,” IEEE Commun. Mag., vol. 48, no. 2, pp. 56–65, 2010.
[CrossRef]

2009 (1)

2007 (2)

2006 (1)

2005 (1)

S. U. Kahn, “Heuristics-based PON deployment,” IEEE Commun. Lett., vol. 9, no. 9, pp. 847–849, 2005.
[CrossRef]

1992 (1)

S. Narasimhan and H. Pirkul, “Hierarchical concentrator location problem,” Comput. Commun., vol. 15, no. 3, pp. 185–191, 1992.
[CrossRef]

1982 (1)

G. Schneider and M. Zastrov, “An algorithm for the design of multilevel concentrator networks,” Comput. Netw., vol. 6, no. 1, pp. 1–11, 1982.

1981 (1)

A. Mirzaian and K. Steiglitz, “A note on the complexity of the star–star concentrator problem,” IEEE Trans. Commun., vol. 29, no. 10, pp. 1549–1552, 1981.
[CrossRef]

1977 (1)

R. Boorstyn and H. Frank, “Large-scale network topological optimization,” IEEE Trans. Commun., vol. 25, no. 1, pp. 29–47, 1977.
[CrossRef]

Aleksic, S.

S. Aleksic and A. Lovric, “Power consumption of wired access network technologies,” in 7th Int. Symp. on Communication Systems, Networks and Digital Signal Processing (CSNDSP), Newcastle, United Kingdom, 2010.

Bernardo, M.

J. Salgado, P. M. Cheia, C. Rodrigues, M. Bernardo, and J. Figueiredo, “Evolution of access networks from GPON to XGPON to WDM-PON from operator point-of-view,” in 15th European Conf. on Networks and Optical Communications (NOC), Faro, Portugal, 2010.

Bickham, S.

Boorstyn, R.

R. Boorstyn and H. Frank, “Large-scale network topological optimization,” IEEE Trans. Commun., vol. 25, no. 1, pp. 29–47, 1977.
[CrossRef]

Cheia, P. M.

J. Salgado, P. M. Cheia, C. Rodrigues, M. Bernardo, and J. Figueiredo, “Evolution of access networks from GPON to XGPON to WDM-PON from operator point-of-view,” in 15th European Conf. on Networks and Optical Communications (NOC), Faro, Portugal, 2010.

Chen, J.

J. Chen, L. Wosinska, C. Mas Machuca, and M. Jaeger, “Cost vs. reliability performance study of fiber access network architectures,” IEEE Commun. Mag., vol. 48, no. 2, pp. 56–65, 2010.
[CrossRef]

C. Mas Machuca, J. Chen, and L. Wosinska, “Cost dependency on protection of optical access networks for dense urban areas,” in 13th Int. Conf. on Transparent Optical Networks (ICTON), Stockholm, Sweden, 2011.

Chen, X.

M. Lv and X. Chen, “Heuristic based multi-hierarchy passive optical network planning,” in 5th Int. Conf. on Wireless Communications, Networking and Mobile Computing (WiCom), Beijing, China, 2009.

Effenberger, F.

Figueiredo, J.

J. Salgado, P. M. Cheia, C. Rodrigues, M. Bernardo, and J. Figueiredo, “Evolution of access networks from GPON to XGPON to WDM-PON from operator point-of-view,” in 15th European Conf. on Networks and Optical Communications (NOC), Faro, Portugal, 2010.

Forcucci, A.

Frank, H.

R. Boorstyn and H. Frank, “Large-scale network topological optimization,” IEEE Trans. Commun., vol. 25, no. 1, pp. 29–47, 1977.
[CrossRef]

Hajduczenia, M.

M. Hajduczenia, B. Lakic, H. Silva, and P. Monteiro, “Optimized passive optical network deployment,” J. Opt. Netw., vol. 6, no. 9, pp. 1079–1104, 2007.
[CrossRef]

B. Lakic and M. Hajduczenia, “On optimized passive optical network (PON) deployment,” in 2nd Int. Conf. on Access Networks (ACCESSNETS), Ottawa, Canada, 2007.

B. Lakic, M. Hajduczenia, H. Silva, and P. Monteiro, “Using adapted visibility graphs for network planning,” in IEEE Symp. on Computers and Communications (ISCC), Marrakech, Morroco, 2008.

Igel, J. R.

Jaeger, M.

J. Chen, L. Wosinska, C. Mas Machuca, and M. Jaeger, “Cost vs. reliability performance study of fiber access network architectures,” IEEE Commun. Mag., vol. 48, no. 2, pp. 56–65, 2010.
[CrossRef]

Jain, S.

Kahn, S. U.

S. U. Kahn, “Heuristics-based PON deployment,” IEEE Commun. Lett., vol. 9, no. 9, pp. 847–849, 2005.
[CrossRef]

Keiser, G.

G. Keiser, FTTX Concepts and Applications. John Wiley & Sons, New Jersey, 2006.

Lakic, B.

M. Hajduczenia, B. Lakic, H. Silva, and P. Monteiro, “Optimized passive optical network deployment,” J. Opt. Netw., vol. 6, no. 9, pp. 1079–1104, 2007.
[CrossRef]

B. Lakic, M. Hajduczenia, H. Silva, and P. Monteiro, “Using adapted visibility graphs for network planning,” in IEEE Symp. on Computers and Communications (ISCC), Marrakech, Morroco, 2008.

B. Lakic and M. Hajduczenia, “On optimized passive optical network (PON) deployment,” in 2nd Int. Conf. on Access Networks (ACCESSNETS), Ottawa, Canada, 2007.

Lam, C.

C. Lam, Passive Optical Networks: Principles and Practice. Elsevier, 2007.

Li, J.

Lovric, A.

S. Aleksic and A. Lovric, “Power consumption of wired access network technologies,” in 7th Int. Symp. on Communication Systems, Networks and Digital Signal Processing (CSNDSP), Newcastle, United Kingdom, 2010.

Lv, M.

M. Lv and X. Chen, “Heuristic based multi-hierarchy passive optical network planning,” in 5th Int. Conf. on Wireless Communications, Networking and Mobile Computing (WiCom), Beijing, China, 2009.

Macqueen, J. B.

J. B. Macqueen, “Some methods for classification and analysis of multivariate observations,” in 5th Berkeley Symp. on Mathematical Statistics and Probability, Berkeley, United States, 1967.

Mapes, R.

Mas Machuca, C.

J. Chen, L. Wosinska, C. Mas Machuca, and M. Jaeger, “Cost vs. reliability performance study of fiber access network architectures,” IEEE Commun. Mag., vol. 48, no. 2, pp. 56–65, 2010.
[CrossRef]

C. Mas Machuca, J. Chen, and L. Wosinska, “Cost dependency on protection of optical access networks for dense urban areas,” in 13th Int. Conf. on Transparent Optical Networks (ICTON), Stockholm, Sweden, 2011.

McCammon, K.

Mirzaian, A.

A. Mirzaian and K. Steiglitz, “A note on the complexity of the star–star concentrator problem,” IEEE Trans. Commun., vol. 29, no. 10, pp. 1549–1552, 1981.
[CrossRef]

Monteiro, P.

M. Hajduczenia, B. Lakic, H. Silva, and P. Monteiro, “Optimized passive optical network deployment,” J. Opt. Netw., vol. 6, no. 9, pp. 1079–1104, 2007.
[CrossRef]

B. Lakic, M. Hajduczenia, H. Silva, and P. Monteiro, “Using adapted visibility graphs for network planning,” in IEEE Symp. on Computers and Communications (ISCC), Marrakech, Morroco, 2008.

Narasimhan, S.

S. Narasimhan and H. Pirkul, “Hierarchical concentrator location problem,” Comput. Commun., vol. 15, no. 3, pp. 185–191, 1992.
[CrossRef]

O’Byrne, V.

Pirkul, H.

S. Narasimhan and H. Pirkul, “Hierarchical concentrator location problem,” Comput. Commun., vol. 15, no. 3, pp. 185–191, 1992.
[CrossRef]

Rodrigues, C.

J. Salgado, P. M. Cheia, C. Rodrigues, M. Bernardo, and J. Figueiredo, “Evolution of access networks from GPON to XGPON to WDM-PON from operator point-of-view,” in 15th European Conf. on Networks and Optical Communications (NOC), Faro, Portugal, 2010.

Ruffin, A. B.

Salgado, J.

J. Salgado, P. M. Cheia, C. Rodrigues, M. Bernardo, and J. Figueiredo, “Evolution of access networks from GPON to XGPON to WDM-PON from operator point-of-view,” in 15th European Conf. on Networks and Optical Communications (NOC), Faro, Portugal, 2010.

Schneider, G.

G. Schneider and M. Zastrov, “An algorithm for the design of multilevel concentrator networks,” Comput. Netw., vol. 6, no. 1, pp. 1–11, 1982.

Shen, G.

Silva, H.

M. Hajduczenia, B. Lakic, H. Silva, and P. Monteiro, “Optimized passive optical network deployment,” J. Opt. Netw., vol. 6, no. 9, pp. 1079–1104, 2007.
[CrossRef]

B. Lakic, M. Hajduczenia, H. Silva, and P. Monteiro, “Using adapted visibility graphs for network planning,” in IEEE Symp. on Computers and Communications (ISCC), Marrakech, Morroco, 2008.

Steiglitz, K.

A. Mirzaian and K. Steiglitz, “A note on the complexity of the star–star concentrator problem,” IEEE Trans. Commun., vol. 29, no. 10, pp. 1549–1552, 1981.
[CrossRef]

Szabo, A.

Vaughn, M. D.

Wagner, R. E.

Wei, G.

Whitman, R.

Wosinska, L.

J. Chen, L. Wosinska, C. Mas Machuca, and M. Jaeger, “Cost vs. reliability performance study of fiber access network architectures,” IEEE Commun. Mag., vol. 48, no. 2, pp. 56–65, 2010.
[CrossRef]

C. Mas Machuca, J. Chen, and L. Wosinska, “Cost dependency on protection of optical access networks for dense urban areas,” in 13th Int. Conf. on Transparent Optical Networks (ICTON), Stockholm, Sweden, 2011.

Yixin, Z.

Yuanqiu, L.

Zastrov, M.

G. Schneider and M. Zastrov, “An algorithm for the design of multilevel concentrator networks,” Comput. Netw., vol. 6, no. 1, pp. 1–11, 1982.

Zhishan, F.

Comput. Commun. (1)

S. Narasimhan and H. Pirkul, “Hierarchical concentrator location problem,” Comput. Commun., vol. 15, no. 3, pp. 185–191, 1992.
[CrossRef]

Comput. Netw. (1)

G. Schneider and M. Zastrov, “An algorithm for the design of multilevel concentrator networks,” Comput. Netw., vol. 6, no. 1, pp. 1–11, 1982.

IEEE Commun. Lett. (1)

S. U. Kahn, “Heuristics-based PON deployment,” IEEE Commun. Lett., vol. 9, no. 9, pp. 847–849, 2005.
[CrossRef]

IEEE Commun. Mag. (1)

J. Chen, L. Wosinska, C. Mas Machuca, and M. Jaeger, “Cost vs. reliability performance study of fiber access network architectures,” IEEE Commun. Mag., vol. 48, no. 2, pp. 56–65, 2010.
[CrossRef]

IEEE Trans. Commun. (2)

R. Boorstyn and H. Frank, “Large-scale network topological optimization,” IEEE Trans. Commun., vol. 25, no. 1, pp. 29–47, 1977.
[CrossRef]

A. Mirzaian and K. Steiglitz, “A note on the complexity of the star–star concentrator problem,” IEEE Trans. Commun., vol. 29, no. 10, pp. 1549–1552, 1981.
[CrossRef]

J. Lightwave Technol. (2)

J. Opt. Commun. Netw. (1)

J. Opt. Netw. (2)

Other (12)

S. Aleksic and A. Lovric, “Power consumption of wired access network technologies,” in 7th Int. Symp. on Communication Systems, Networks and Digital Signal Processing (CSNDSP), Newcastle, United Kingdom, 2010.

J. B. Macqueen, “Some methods for classification and analysis of multivariate observations,” in 5th Berkeley Symp. on Mathematical Statistics and Probability, Berkeley, United States, 1967.

C. Mas Machuca, J. Chen, and L. Wosinska, “Cost dependency on protection of optical access networks for dense urban areas,” in 13th Int. Conf. on Transparent Optical Networks (ICTON), Stockholm, Sweden, 2011.

B. Lakic and M. Hajduczenia, “On optimized passive optical network (PON) deployment,” in 2nd Int. Conf. on Access Networks (ACCESSNETS), Ottawa, Canada, 2007.

B. Lakic, M. Hajduczenia, H. Silva, and P. Monteiro, “Using adapted visibility graphs for network planning,” in IEEE Symp. on Computers and Communications (ISCC), Marrakech, Morroco, 2008.

M. Lv and X. Chen, “Heuristic based multi-hierarchy passive optical network planning,” in 5th Int. Conf. on Wireless Communications, Networking and Mobile Computing (WiCom), Beijing, China, 2009.

C. Lam, Passive Optical Networks: Principles and Practice. Elsevier, 2007.

J. Nielsen, “Nielsen’s law of internet bandwidth,” 2010 [Online]. Available: http://www.useit.com/alertbox/980405.html.

“10 Gb/s Ethernet passive optical network,” IEEE Standard 802.3av, 2009.

“Gigabit-capable passive optical networks (XG-PON): General Requirements,” ITU-T Recommendation G.987.1, 2010.

J. Salgado, P. M. Cheia, C. Rodrigues, M. Bernardo, and J. Figueiredo, “Evolution of access networks from GPON to XGPON to WDM-PON from operator point-of-view,” in 15th European Conf. on Networks and Optical Communications (NOC), Faro, Portugal, 2010.

G. Keiser, FTTX Concepts and Applications. John Wiley & Sons, New Jersey, 2006.

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

(Color online) Architecture of a multistage PON.

Fig. 2
Fig. 2

(Color online) Splitter cascade with maximum splitting ratio of 64.

Fig. 3
Fig. 3

(Color online) Concept of the RSR, originating variable ci.

Fig. 4
Fig. 4

(Color online) Example of a scenario with 25 ONUs and 6 potential splitter sites.

Fig. 5
Fig. 5

Flowchart of two-stage heuristic algorithm.

Fig. 6
Fig. 6

(Color online) Layout for 100 ONUs and 10 splitters using the two-stage heuristic.

Fig. 7
Fig. 7

CAPEX for the single-stage ILP and the two-stage heuristic with random and k-means-based splitter location.

Fig. 8
Fig. 8

Total network cost variation by cost component for single-stage and two-stage architectures.

Tables (3)

Tables Icon

Table I Costs and Simulation Times for Various Scenarios

Tables Icon

Table II CAPEX Comparison Between the Multistage ILP Model and the Two-stage Heuristic

Tables Icon

Table III Comparative CAPEX Between the Two-stage Heuristic and the Single-stage ILP.

Equations (18)

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

mini=1Nj=1Maijxij+i=1Mbi0yi0+i=1Mj=1jiMbijyij+k=1Sj=1Mdkzjk
subject to:
j=1Mxij=1,i=1,,N
j=0jiMyij1,i=1,,M
i=1ijMyij+i=1Nxijk=1S2kzjk,j=1,,M
cicj+Δ(1yij)1,i=1,,M;j=0,,M;ij
ciSj=0jiMyij,i=1,,M
Δ(1yij)+k=1Skzikcjci,i=1,,M;j=0,,M;ij
Δ(1yij)+k=1Skzikcjci,i=1,,M;j=0,,M;ij
i=1Nxij+i=1ijMyijΔi=0ijMyji,j=1,,M
j=0jiMyijci,i=1,,M
k=1Szik1,i=1,,M.
i=1Nxij2Syj0j=1,,M.
mini=1Mbi0yi0+i=1Mj=1jiMbijyij
subject to:
j=0jiMyij1,i=1,,M
i=1Myi0NPON
yijyj0,i=1,,M;j=1,,M;ij.