Abstract

We plan greenfield PON networks to minimize their total deployment costs. We propose an efficient heuristic called the Recursive Association and Relocation Algorithm (RARA) to solve the optimization problem. Our algorithm can significantly reduce PON network deployment costs compared to an intuitive random-cut sectoring approach. To further tune down the costs, we also exploit the opportunity of cable conduit sharing by proposing an extension to RARA. Our case studies show that there are saturating trends for the PON deployment costs with the increase of the three system parameters, including maximal optical split ratio, maximal transmission distance, and maximal differential distance. Also, to reduce computation time for large PON deployment scenarios, we propose a disintegration planning method to divide a large planning scenario into several small ones. The method is found to be effective to provide close performance, but require much less computation, compared to the situation without disintegration.

© 2009 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. Li, G. Shen, “Cost minimization planning for passive optical networks,” in Proc. OFC/NFOEC 2008, Feb 2008.
  2. G. Kramer, B. Mukherjee, G. Pesavento, “IPACT: a dynamic protocol for an Ethernet PON (EPON),” IEEE Commun. Mag., vol. 40, no. 2, pp. 74–80, Feb. 2002.
    [CrossRef]
  3. F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
    [CrossRef]
  4. “Ethernet in the First Mile,” IEEE 802.3ah, June 2004.
  5. ITU-T G.984.1, SG 15, “Gigabit-capable Passive Optical Networks (G-PON): General Characteristics,” March 2003.
  6. ITU-T G.984.4, SG 15, “Gigabit-capable Passive Optical Networks (G-PON): Transmission Convergence Layer Specification,” July 2005.
  7. C. M. Assi, Y. Ye, S. Dixit, M. A. Ali, “Dynamic bandwidth allocation for quality-of-service over Ethernet PONs,” IEEE J. Sel. Areas Commun., vol. 3, no. 9, pp. 1467–1477, Nov. 2003.
    [CrossRef]
  8. C. H. Foh, L. Andrew, E. Wong, M. Zukerman, “FULL-RCMA: a high utilization EPON,” IEEE J. Sel. Areas Commun., vol. 22, no. 8, pp. 1514–1524, 2004.
    [CrossRef]
  9. G. C. Gupta, M. Kashima, H. Iwamura, H. Tamai, T. Ushikubo, T. Kamijoh, “Over 100 km bidirectional, multi-channels COF-PON without optical amplifier,” in OFC 2006, paper PDP51.
  10. “10 GEPON IEEE Working Group,” http://www.ieee802.org/3/av/index.html, online on September 18, 2007.
  11. M. Hajduczenia, B. Lakic, H. J. A. Da Silva, P. P. Monteiro, “Optimized passive optical network deployment,” J. Opt. Netw., vol. 6, no. 9, pp. 1079–1104, 2007.
    [CrossRef]
  12. D. Cieslik, Steiner Minimal Trees, Kluwer Academic Publishers, 1998.
    [CrossRef]
  13. H. W. Kuhn, R. E. Kuenne, “An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics,” J. Regional Sci., vol. 4, no. 2, pp. 21–33, 1962.
    [CrossRef]
  14. L. Cooper, “Location-allocation problems,” Oper. Res., vol. 11, no. 3, pp. 331–343, 1963.
    [CrossRef]
  15. L. Cooper, “Heuristic methods for location-allocation problems,” SIAM Rev., vol. 6, no. 1, pp. 37–53, 1964.
    [CrossRef]
  16. R. Brown, “Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem,” Commun. ACM, vol. 31, no. 10, pp. 1220–1227, Oct. 1988.
    [CrossRef]
  17. C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.

2007 (2)

F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
[CrossRef]

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

2004 (1)

C. H. Foh, L. Andrew, E. Wong, M. Zukerman, “FULL-RCMA: a high utilization EPON,” IEEE J. Sel. Areas Commun., vol. 22, no. 8, pp. 1514–1524, 2004.
[CrossRef]

2003 (1)

C. M. Assi, Y. Ye, S. Dixit, M. A. Ali, “Dynamic bandwidth allocation for quality-of-service over Ethernet PONs,” IEEE J. Sel. Areas Commun., vol. 3, no. 9, pp. 1467–1477, Nov. 2003.
[CrossRef]

2002 (1)

G. Kramer, B. Mukherjee, G. Pesavento, “IPACT: a dynamic protocol for an Ethernet PON (EPON),” IEEE Commun. Mag., vol. 40, no. 2, pp. 74–80, Feb. 2002.
[CrossRef]

1988 (1)

R. Brown, “Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem,” Commun. ACM, vol. 31, no. 10, pp. 1220–1227, Oct. 1988.
[CrossRef]

1964 (1)

L. Cooper, “Heuristic methods for location-allocation problems,” SIAM Rev., vol. 6, no. 1, pp. 37–53, 1964.
[CrossRef]

1963 (1)

L. Cooper, “Location-allocation problems,” Oper. Res., vol. 11, no. 3, pp. 331–343, 1963.
[CrossRef]

1962 (1)

H. W. Kuhn, R. E. Kuenne, “An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics,” J. Regional Sci., vol. 4, no. 2, pp. 21–33, 1962.
[CrossRef]

Ali, M. A.

C. M. Assi, Y. Ye, S. Dixit, M. A. Ali, “Dynamic bandwidth allocation for quality-of-service over Ethernet PONs,” IEEE J. Sel. Areas Commun., vol. 3, no. 9, pp. 1467–1477, Nov. 2003.
[CrossRef]

Andrew, L.

C. H. Foh, L. Andrew, E. Wong, M. Zukerman, “FULL-RCMA: a high utilization EPON,” IEEE J. Sel. Areas Commun., vol. 22, no. 8, pp. 1514–1524, 2004.
[CrossRef]

Assi, C. M.

C. M. Assi, Y. Ye, S. Dixit, M. A. Ali, “Dynamic bandwidth allocation for quality-of-service over Ethernet PONs,” IEEE J. Sel. Areas Commun., vol. 3, no. 9, pp. 1467–1477, Nov. 2003.
[CrossRef]

Brown, R.

R. Brown, “Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem,” Commun. ACM, vol. 31, no. 10, pp. 1220–1227, Oct. 1988.
[CrossRef]

Calix, D. C.

F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
[CrossRef]

Cieslik, D.

D. Cieslik, Steiner Minimal Trees, Kluwer Academic Publishers, 1998.
[CrossRef]

Cooper, L.

L. Cooper, “Heuristic methods for location-allocation problems,” SIAM Rev., vol. 6, no. 1, pp. 37–53, 1964.
[CrossRef]

L. Cooper, “Location-allocation problems,” Oper. Res., vol. 11, no. 3, pp. 331–343, 1963.
[CrossRef]

Da Silva, H. J. A.

Dixit, S.

C. M. Assi, Y. Ye, S. Dixit, M. A. Ali, “Dynamic bandwidth allocation for quality-of-service over Ethernet PONs,” IEEE J. Sel. Areas Commun., vol. 3, no. 9, pp. 1467–1477, Nov. 2003.
[CrossRef]

Effenberger, F.

F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
[CrossRef]

Foh, C. H.

C. H. Foh, L. Andrew, E. Wong, M. Zukerman, “FULL-RCMA: a high utilization EPON,” IEEE J. Sel. Areas Commun., vol. 22, no. 8, pp. 1514–1524, 2004.
[CrossRef]

Gupta, G. C.

G. C. Gupta, M. Kashima, H. Iwamura, H. Tamai, T. Ushikubo, T. Kamijoh, “Over 100 km bidirectional, multi-channels COF-PON without optical amplifier,” in OFC 2006, paper PDP51.

Hajduczenia, M.

Iwamura, H.

G. C. Gupta, M. Kashima, H. Iwamura, H. Tamai, T. Ushikubo, T. Kamijoh, “Over 100 km bidirectional, multi-channels COF-PON without optical amplifier,” in OFC 2006, paper PDP51.

Kamijoh, T.

G. C. Gupta, M. Kashima, H. Iwamura, H. Tamai, T. Ushikubo, T. Kamijoh, “Over 100 km bidirectional, multi-channels COF-PON without optical amplifier,” in OFC 2006, paper PDP51.

Kashima, M.

G. C. Gupta, M. Kashima, H. Iwamura, H. Tamai, T. Ushikubo, T. Kamijoh, “Over 100 km bidirectional, multi-channels COF-PON without optical amplifier,” in OFC 2006, paper PDP51.

Kramer, G.

F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
[CrossRef]

G. Kramer, B. Mukherjee, G. Pesavento, “IPACT: a dynamic protocol for an Ethernet PON (EPON),” IEEE Commun. Mag., vol. 40, no. 2, pp. 74–80, Feb. 2002.
[CrossRef]

Kuenne, R. E.

H. W. Kuhn, R. E. Kuenne, “An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics,” J. Regional Sci., vol. 4, no. 2, pp. 21–33, 1962.
[CrossRef]

Kuhn, H. W.

H. W. Kuhn, R. E. Kuenne, “An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics,” J. Regional Sci., vol. 4, no. 2, pp. 21–33, 1962.
[CrossRef]

Lakic, B.

Li, J.

J. Li, G. Shen, “Cost minimization planning for passive optical networks,” in Proc. OFC/NFOEC 2008, Feb 2008.

Li, R.

F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
[CrossRef]

Monteiro, P. P.

Mukherjee, B.

G. Kramer, B. Mukherjee, G. Pesavento, “IPACT: a dynamic protocol for an Ethernet PON (EPON),” IEEE Commun. Mag., vol. 40, no. 2, pp. 74–80, Feb. 2002.
[CrossRef]

Oron, M.

F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
[CrossRef]

Papadimitriou, C. H.

C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.

Pesavento, G.

G. Kramer, B. Mukherjee, G. Pesavento, “IPACT: a dynamic protocol for an Ethernet PON (EPON),” IEEE Commun. Mag., vol. 40, no. 2, pp. 74–80, Feb. 2002.
[CrossRef]

Pfeiffer, T.

F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
[CrossRef]

Shen, G.

J. Li, G. Shen, “Cost minimization planning for passive optical networks,” in Proc. OFC/NFOEC 2008, Feb 2008.

Steiglitz, K.

C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.

Tamai, H.

G. C. Gupta, M. Kashima, H. Iwamura, H. Tamai, T. Ushikubo, T. Kamijoh, “Over 100 km bidirectional, multi-channels COF-PON without optical amplifier,” in OFC 2006, paper PDP51.

Ushikubo, T.

G. C. Gupta, M. Kashima, H. Iwamura, H. Tamai, T. Ushikubo, T. Kamijoh, “Over 100 km bidirectional, multi-channels COF-PON without optical amplifier,” in OFC 2006, paper PDP51.

Wong, E.

C. H. Foh, L. Andrew, E. Wong, M. Zukerman, “FULL-RCMA: a high utilization EPON,” IEEE J. Sel. Areas Commun., vol. 22, no. 8, pp. 1514–1524, 2004.
[CrossRef]

Ye, Y.

C. M. Assi, Y. Ye, S. Dixit, M. A. Ali, “Dynamic bandwidth allocation for quality-of-service over Ethernet PONs,” IEEE J. Sel. Areas Commun., vol. 3, no. 9, pp. 1467–1477, Nov. 2003.
[CrossRef]

Zukerman, M.

C. H. Foh, L. Andrew, E. Wong, M. Zukerman, “FULL-RCMA: a high utilization EPON,” IEEE J. Sel. Areas Commun., vol. 22, no. 8, pp. 1514–1524, 2004.
[CrossRef]

Commun. ACM (1)

R. Brown, “Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem,” Commun. ACM, vol. 31, no. 10, pp. 1220–1227, Oct. 1988.
[CrossRef]

IEEE Commun. Mag. (2)

G. Kramer, B. Mukherjee, G. Pesavento, “IPACT: a dynamic protocol for an Ethernet PON (EPON),” IEEE Commun. Mag., vol. 40, no. 2, pp. 74–80, Feb. 2002.
[CrossRef]

F. Effenberger, D. C. Calix, G. Kramer, R. Li, M. Oron, T. Pfeiffer, “An introduction to PON technologies,” IEEE Commun. Mag., vol. 45, no. 3, pp. S17–S25, Mar. 2007.
[CrossRef]

IEEE J. Sel. Areas Commun. (2)

C. M. Assi, Y. Ye, S. Dixit, M. A. Ali, “Dynamic bandwidth allocation for quality-of-service over Ethernet PONs,” IEEE J. Sel. Areas Commun., vol. 3, no. 9, pp. 1467–1477, Nov. 2003.
[CrossRef]

C. H. Foh, L. Andrew, E. Wong, M. Zukerman, “FULL-RCMA: a high utilization EPON,” IEEE J. Sel. Areas Commun., vol. 22, no. 8, pp. 1514–1524, 2004.
[CrossRef]

J. Opt. Netw. (1)

J. Regional Sci. (1)

H. W. Kuhn, R. E. Kuenne, “An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics,” J. Regional Sci., vol. 4, no. 2, pp. 21–33, 1962.
[CrossRef]

Oper. Res. (1)

L. Cooper, “Location-allocation problems,” Oper. Res., vol. 11, no. 3, pp. 331–343, 1963.
[CrossRef]

SIAM Rev. (1)

L. Cooper, “Heuristic methods for location-allocation problems,” SIAM Rev., vol. 6, no. 1, pp. 37–53, 1964.
[CrossRef]

Other (8)

D. Cieslik, Steiner Minimal Trees, Kluwer Academic Publishers, 1998.
[CrossRef]

C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.

J. Li, G. Shen, “Cost minimization planning for passive optical networks,” in Proc. OFC/NFOEC 2008, Feb 2008.

G. C. Gupta, M. Kashima, H. Iwamura, H. Tamai, T. Ushikubo, T. Kamijoh, “Over 100 km bidirectional, multi-channels COF-PON without optical amplifier,” in OFC 2006, paper PDP51.

“10 GEPON IEEE Working Group,” http://www.ieee802.org/3/av/index.html, online on September 18, 2007.

“Ethernet in the First Mile,” IEEE 802.3ah, June 2004.

ITU-T G.984.1, SG 15, “Gigabit-capable Passive Optical Networks (G-PON): General Characteristics,” March 2003.

ITU-T G.984.4, SG 15, “Gigabit-capable Passive Optical Networks (G-PON): Transmission Convergence Layer Specification,” July 2005.

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 (13)

Fig. 1
Fig. 1

Illustration of PON networks.

Fig. 2
Fig. 2

An example of the random-cut sectoring approach.

Fig. 3
Fig. 3

Flowchart of RARA [1].

Fig. 4
Fig. 4

Concept of cable conduit sharing in PON networks.

Fig. 5
Fig. 5

Total cost vs. number of ONUs, circular scenario, radius = 16 km , maximal split ratio = 1 : 16 .

Fig. 6
Fig. 6

Total cost vs. number of ONUs, annulus scenario, maximal split ratio = 1 : 16 .

Fig. 7
Fig. 7

Total cost vs. number of ONUs, circular scenario, radius = 50 km , maximal split ratio = 1 : 16 .

Fig. 8
Fig. 8

Average cost per user vs. split ratio, circular scenario, radius = 16 km , number of ONUs = 500 .

Fig. 9
Fig. 9

Average cost per user vs. split ratio, annulus scenario, number of ONUs = 700 .

Fig. 10
Fig. 10

Total cost vs. maximal PON transmission distance, circular scenario, radius = 16 km , ONU number = 400 .

Fig. 11
Fig. 11

Total cost vs. maximal differential distance, circular scenario, radius = 16 km , ONU number = 400 .

Fig. 12
Fig. 12

Comparison of the ONU-splitter association algorithm in RARA and the MILP model for the circular planning scenario with radius = 16 km , split ratio = 1 : 64 .

Fig. 13
Fig. 13

Total cost of the planning with disintegration and without disintegration, SR, split ratio

Tables (2)

Tables Icon

Table 1 Algorithm 1 Weiszfeld Algorithm [12]

Tables Icon

Table 1 Comparison of Computation Times (hours) of the Approaches With Disintegration and Without Disintegration (600 ONUs)

Equations (14)

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

α i S Φ i + β i S k T s Φ i T k π i k + ( γ + θ ) ( i S Φ i l i s + i S j U Ψ i j l i j ) .
i S Ψ i j = 1 , j U ;
Δ Φ i j U Ψ i j , i S ;
j U Ψ i j k T s T k π i k , i S ;
k T s π i k 1 Δ τ i , i S ;
1 k T s π i k Δ τ i , i S ;
Φ i Δ ( 1 τ i ) , i S ;
l i s = ( x i s x 0 ) 2 + ( y i s y 0 ) 2 , i S ;
l i j = ( x i s x j o ) 2 + ( y i s y j o ) 2 , i S , j U ;
( l i s + l i j ) l i max Δ ζ i j , i S , j U ;
l i min ( l i s + l i j ) Δ ζ i j , i S , j U ;
Ψ i j Δ ( 1 ζ i j ) , i S , j U ;
l i max l max total , i S ;
l i max l i min l max diff , i S .