Abstract

The construction of light-trees is one of the principal subproblems for all-optical multicast routing in sparse splitting wavelength division multiplexing (WDM) networks. Due to the light splitting constraint and the absence of wavelength converters, several light-trees may be required to establish a multicast session. However, the computation of the cost-optimal multicast light-trees is NP-hard. In this paper, first we study the cost bounds of the light-trees built for a multicast session in unweighted WDM networks. Then, partially based on this result, the approximation ratios of some classical multicast light-tree computation algorithms, i.e., the reroute-to-source (R2S) and member-only (MO) algorithms, are derived in both unweighted and non-equally-weighted WDM networks. Moreover, integer linear programming formulations are introduced and carried out to search the optimal light-trees for multicast routing. The cost bounds and approximation ratios of the R2S and MO algorithms in some candidate WDM backbone networks are examined through simulations.

© 2011 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Hamad, T. Wu, A. E. Kamal, and A. K. Somani, "On multicasting in wavelength-routing mesh networks," Comput. Netw. 50, (15), 3105‒3164 (2006).
    [CrossRef]
  2. L. H. Sahasrabuddhe and B. Mukherjee, "Light-trees: optical multicasting for improved performance in wavelength-routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
    [CrossRef]
  3. R. Malli, X. Zhang, and C. Qiao, "Benefit of multicasting in all-optical networks," Proc. SPIE 3531, 209‒220 (1998).
  4. M. Ali and J. S. Deogun, "Cost-effective implementation of multicasting in wavelength-routed networks," J. Lightwave Technol. 18, (12), 1628‒1638 (2000).
    [CrossRef]
  5. X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001).
    [CrossRef]
  6. B. Mukherjee, "WDM optical communication networks: progress and challenges," IEEE J. Sel. Areas Commun. 18, (10), 1810‒1824 (2000).
    [CrossRef]
  7. X. Zhang, J. Wei, and C. Qiao, "Constrained multicast routing in WDM networks with sparse splitting," J. Lightwave Technol. 18, (12), 1917‒1927 (2000).
    [CrossRef]
  8. F. Zhou, M. Molnár, and B. Cousin, "Avoidance of multicast incapable branching nodes in WDM netwoks," Photonic Network Commun. 18, (3), 378‒392 (2009).
    [CrossRef]
  9. F. Zhou, M. Molnár, and B. Cousin, "Is light-tree structure optimal for multicast routing in sparse light splitting WDM networks?," 18th Int. Conf. on Computer Communications and Networks (IC3N’09), 2009, San Francisco, CA, pp. 1‒7.
  10. C.-Y. Hsieh and W. Liao, "All-optical multicast routing in sparse splitting WDM networks," IEEE J. Sel. Areas Commun. 25, (6), 51‒62 (2007).
    [CrossRef]
  11. H. Lin and S. Wang, "Splitter placement in all-optical WDM networks," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 306‒310.
  12. F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Cost bounds of multicast light-trees in WDM networks," 9th IFIP Int. Conf. on Networking (Networking 10), 2010, Chennai, India, pp. 94‒105.
  13. H. Takahashi and A. Matsuyama, "An approximate solution for the Steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).
  14. P. Winter, "Steiner problem in networks: a survey," Networks 17, (2), 129‒167 (1987).
    [CrossRef]
  15. F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Approximation ratios of multicast light-trees in WDM networks," IEEE Global Communications Conf. (GLOBECOM10), 2010, Miami, FL, pp. 1‒6.
  16. L. Kou, G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," Acta Inf. 15, (2), 141‒145 (1981).
    [CrossRef]
  17. M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Multicasting in a WDM-upgraded resilient packet ring," J. Opt. Netw. 6, (5), 415‒421 (2006).
    [CrossRef]
  18. M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Shortest path routing in optical WDM ring networks under multicast traffic," IEEE Commun. Lett. 10, (7), 564‒566 (2006).
  19. O. Yu and Y. Cao, "Mathematical formulation of optical multicast with loss-balanced light-forest," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 1788‒1792.
  20. M.-T. Chen, B. M. T. Lin, and S.-S. Tseng, "Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities," J. Netw. Comput. Appl. 31, (1), 47‒65 (2008).
    [CrossRef]
  21. http://www.ilog.com/products/cplex/
  22. http://www.algorithmic-solutions.com/leda/index.htm

2009

F. Zhou, M. Molnár, and B. Cousin, "Avoidance of multicast incapable branching nodes in WDM netwoks," Photonic Network Commun. 18, (3), 378‒392 (2009).
[CrossRef]

2008

M.-T. Chen, B. M. T. Lin, and S.-S. Tseng, "Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities," J. Netw. Comput. Appl. 31, (1), 47‒65 (2008).
[CrossRef]

2007

C.-Y. Hsieh and W. Liao, "All-optical multicast routing in sparse splitting WDM networks," IEEE J. Sel. Areas Commun. 25, (6), 51‒62 (2007).
[CrossRef]

2006

A. Hamad, T. Wu, A. E. Kamal, and A. K. Somani, "On multicasting in wavelength-routing mesh networks," Comput. Netw. 50, (15), 3105‒3164 (2006).
[CrossRef]

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Multicasting in a WDM-upgraded resilient packet ring," J. Opt. Netw. 6, (5), 415‒421 (2006).
[CrossRef]

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Shortest path routing in optical WDM ring networks under multicast traffic," IEEE Commun. Lett. 10, (7), 564‒566 (2006).

2001

X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001).
[CrossRef]

2000

1999

L. H. Sahasrabuddhe and B. Mukherjee, "Light-trees: optical multicasting for improved performance in wavelength-routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
[CrossRef]

1998

R. Malli, X. Zhang, and C. Qiao, "Benefit of multicasting in all-optical networks," Proc. SPIE 3531, 209‒220 (1998).

1987

P. Winter, "Steiner problem in networks: a survey," Networks 17, (2), 129‒167 (1987).
[CrossRef]

1981

L. Kou, G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," Acta Inf. 15, (2), 141‒145 (1981).
[CrossRef]

1980

H. Takahashi and A. Matsuyama, "An approximate solution for the Steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).

Ali, M.

Berman, L.

L. Kou, G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," Acta Inf. 15, (2), 141‒145 (1981).
[CrossRef]

Cao, Y.

O. Yu and Y. Cao, "Mathematical formulation of optical multicast with loss-balanced light-forest," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 1788‒1792.

Chen, M.-T.

M.-T. Chen, B. M. T. Lin, and S.-S. Tseng, "Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities," J. Netw. Comput. Appl. 31, (1), 47‒65 (2008).
[CrossRef]

Cousin, B.

F. Zhou, M. Molnár, and B. Cousin, "Avoidance of multicast incapable branching nodes in WDM netwoks," Photonic Network Commun. 18, (3), 378‒392 (2009).
[CrossRef]

F. Zhou, M. Molnár, and B. Cousin, "Is light-tree structure optimal for multicast routing in sparse light splitting WDM networks?," 18th Int. Conf. on Computer Communications and Networks (IC3N’09), 2009, San Francisco, CA, pp. 1‒7.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Cost bounds of multicast light-trees in WDM networks," 9th IFIP Int. Conf. on Networking (Networking 10), 2010, Chennai, India, pp. 94‒105.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Approximation ratios of multicast light-trees in WDM networks," IEEE Global Communications Conf. (GLOBECOM10), 2010, Miami, FL, pp. 1‒6.

Deogun, J. S.

Du, D.

X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001).
[CrossRef]

Gu, J.

X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001).
[CrossRef]

Hamad, A.

A. Hamad, T. Wu, A. E. Kamal, and A. K. Somani, "On multicasting in wavelength-routing mesh networks," Comput. Netw. 50, (15), 3105‒3164 (2006).
[CrossRef]

Hsieh, C.-Y.

C.-Y. Hsieh and W. Liao, "All-optical multicast routing in sparse splitting WDM networks," IEEE J. Sel. Areas Commun. 25, (6), 51‒62 (2007).
[CrossRef]

Hu, X.

X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001).
[CrossRef]

Jia, X.

X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001).
[CrossRef]

Kamal, A. E.

A. Hamad, T. Wu, A. E. Kamal, and A. K. Somani, "On multicasting in wavelength-routing mesh networks," Comput. Netw. 50, (15), 3105‒3164 (2006).
[CrossRef]

Kou, L.

L. Kou, G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," Acta Inf. 15, (2), 141‒145 (1981).
[CrossRef]

Lee, M.

X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001).
[CrossRef]

Liao, W.

C.-Y. Hsieh and W. Liao, "All-optical multicast routing in sparse splitting WDM networks," IEEE J. Sel. Areas Commun. 25, (6), 51‒62 (2007).
[CrossRef]

Lin, B. M. T.

M.-T. Chen, B. M. T. Lin, and S.-S. Tseng, "Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities," J. Netw. Comput. Appl. 31, (1), 47‒65 (2008).
[CrossRef]

Lin, H.

H. Lin and S. Wang, "Splitter placement in all-optical WDM networks," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 306‒310.

Maier, M.

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Shortest path routing in optical WDM ring networks under multicast traffic," IEEE Commun. Lett. 10, (7), 564‒566 (2006).

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Multicasting in a WDM-upgraded resilient packet ring," J. Opt. Netw. 6, (5), 415‒421 (2006).
[CrossRef]

Malli, R.

R. Malli, X. Zhang, and C. Qiao, "Benefit of multicasting in all-optical networks," Proc. SPIE 3531, 209‒220 (1998).

Markowsky, G.

L. Kou, G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," Acta Inf. 15, (2), 141‒145 (1981).
[CrossRef]

Matsuyama, A.

H. Takahashi and A. Matsuyama, "An approximate solution for the Steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).

Molnár, M.

F. Zhou, M. Molnár, and B. Cousin, "Avoidance of multicast incapable branching nodes in WDM netwoks," Photonic Network Commun. 18, (3), 378‒392 (2009).
[CrossRef]

F. Zhou, M. Molnár, and B. Cousin, "Is light-tree structure optimal for multicast routing in sparse light splitting WDM networks?," 18th Int. Conf. on Computer Communications and Networks (IC3N’09), 2009, San Francisco, CA, pp. 1‒7.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Cost bounds of multicast light-trees in WDM networks," 9th IFIP Int. Conf. on Networking (Networking 10), 2010, Chennai, India, pp. 94‒105.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Approximation ratios of multicast light-trees in WDM networks," IEEE Global Communications Conf. (GLOBECOM10), 2010, Miami, FL, pp. 1‒6.

Mukherjee, B.

B. Mukherjee, "WDM optical communication networks: progress and challenges," IEEE J. Sel. Areas Commun. 18, (10), 1810‒1824 (2000).
[CrossRef]

L. H. Sahasrabuddhe and B. Mukherjee, "Light-trees: optical multicasting for improved performance in wavelength-routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
[CrossRef]

Qiao, C.

X. Zhang, J. Wei, and C. Qiao, "Constrained multicast routing in WDM networks with sparse splitting," J. Lightwave Technol. 18, (12), 1917‒1927 (2000).
[CrossRef]

R. Malli, X. Zhang, and C. Qiao, "Benefit of multicasting in all-optical networks," Proc. SPIE 3531, 209‒220 (1998).

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Cost bounds of multicast light-trees in WDM networks," 9th IFIP Int. Conf. on Networking (Networking 10), 2010, Chennai, India, pp. 94‒105.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Approximation ratios of multicast light-trees in WDM networks," IEEE Global Communications Conf. (GLOBECOM10), 2010, Miami, FL, pp. 1‒6.

Reisslein, M.

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Multicasting in a WDM-upgraded resilient packet ring," J. Opt. Netw. 6, (5), 415‒421 (2006).
[CrossRef]

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Shortest path routing in optical WDM ring networks under multicast traffic," IEEE Commun. Lett. 10, (7), 564‒566 (2006).

Sahasrabuddhe, L. H.

L. H. Sahasrabuddhe and B. Mukherjee, "Light-trees: optical multicasting for improved performance in wavelength-routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
[CrossRef]

Scheutzow, M.

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Multicasting in a WDM-upgraded resilient packet ring," J. Opt. Netw. 6, (5), 415‒421 (2006).
[CrossRef]

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Shortest path routing in optical WDM ring networks under multicast traffic," IEEE Commun. Lett. 10, (7), 564‒566 (2006).

Seeling, P.

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Shortest path routing in optical WDM ring networks under multicast traffic," IEEE Commun. Lett. 10, (7), 564‒566 (2006).

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Multicasting in a WDM-upgraded resilient packet ring," J. Opt. Netw. 6, (5), 415‒421 (2006).
[CrossRef]

Somani, A. K.

A. Hamad, T. Wu, A. E. Kamal, and A. K. Somani, "On multicasting in wavelength-routing mesh networks," Comput. Netw. 50, (15), 3105‒3164 (2006).
[CrossRef]

Takahashi, H.

H. Takahashi and A. Matsuyama, "An approximate solution for the Steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).

Tseng, S.-S.

M.-T. Chen, B. M. T. Lin, and S.-S. Tseng, "Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities," J. Netw. Comput. Appl. 31, (1), 47‒65 (2008).
[CrossRef]

Wang, S.

H. Lin and S. Wang, "Splitter placement in all-optical WDM networks," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 306‒310.

Wei, J.

Winter, P.

P. Winter, "Steiner problem in networks: a survey," Networks 17, (2), 129‒167 (1987).
[CrossRef]

Wu, T.

A. Hamad, T. Wu, A. E. Kamal, and A. K. Somani, "On multicasting in wavelength-routing mesh networks," Comput. Netw. 50, (15), 3105‒3164 (2006).
[CrossRef]

Yu, O.

O. Yu and Y. Cao, "Mathematical formulation of optical multicast with loss-balanced light-forest," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 1788‒1792.

Zhang, X.

X. Zhang, J. Wei, and C. Qiao, "Constrained multicast routing in WDM networks with sparse splitting," J. Lightwave Technol. 18, (12), 1917‒1927 (2000).
[CrossRef]

R. Malli, X. Zhang, and C. Qiao, "Benefit of multicasting in all-optical networks," Proc. SPIE 3531, 209‒220 (1998).

Zhou, F.

F. Zhou, M. Molnár, and B. Cousin, "Avoidance of multicast incapable branching nodes in WDM netwoks," Photonic Network Commun. 18, (3), 378‒392 (2009).
[CrossRef]

F. Zhou, M. Molnár, and B. Cousin, "Is light-tree structure optimal for multicast routing in sparse light splitting WDM networks?," 18th Int. Conf. on Computer Communications and Networks (IC3N’09), 2009, San Francisco, CA, pp. 1‒7.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Cost bounds of multicast light-trees in WDM networks," 9th IFIP Int. Conf. on Networking (Networking 10), 2010, Chennai, India, pp. 94‒105.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Approximation ratios of multicast light-trees in WDM networks," IEEE Global Communications Conf. (GLOBECOM10), 2010, Miami, FL, pp. 1‒6.

Acta Inf.

L. Kou, G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," Acta Inf. 15, (2), 141‒145 (1981).
[CrossRef]

Comput. Netw.

A. Hamad, T. Wu, A. E. Kamal, and A. K. Somani, "On multicasting in wavelength-routing mesh networks," Comput. Netw. 50, (15), 3105‒3164 (2006).
[CrossRef]

IEEE Commun. Lett.

M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Shortest path routing in optical WDM ring networks under multicast traffic," IEEE Commun. Lett. 10, (7), 564‒566 (2006).

IEEE Commun. Mag.

L. H. Sahasrabuddhe and B. Mukherjee, "Light-trees: optical multicasting for improved performance in wavelength-routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999).
[CrossRef]

IEEE J. Sel. Areas Commun.

B. Mukherjee, "WDM optical communication networks: progress and challenges," IEEE J. Sel. Areas Commun. 18, (10), 1810‒1824 (2000).
[CrossRef]

C.-Y. Hsieh and W. Liao, "All-optical multicast routing in sparse splitting WDM networks," IEEE J. Sel. Areas Commun. 25, (6), 51‒62 (2007).
[CrossRef]

IEEE Trans. Commun.

X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001).
[CrossRef]

J. Lightwave Technol.

J. Netw. Comput. Appl.

M.-T. Chen, B. M. T. Lin, and S.-S. Tseng, "Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities," J. Netw. Comput. Appl. 31, (1), 47‒65 (2008).
[CrossRef]

J. Opt. Netw.

Math. Japonica

H. Takahashi and A. Matsuyama, "An approximate solution for the Steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).

Networks

P. Winter, "Steiner problem in networks: a survey," Networks 17, (2), 129‒167 (1987).
[CrossRef]

Photonic Network Commun.

F. Zhou, M. Molnár, and B. Cousin, "Avoidance of multicast incapable branching nodes in WDM netwoks," Photonic Network Commun. 18, (3), 378‒392 (2009).
[CrossRef]

Proc. SPIE

R. Malli, X. Zhang, and C. Qiao, "Benefit of multicasting in all-optical networks," Proc. SPIE 3531, 209‒220 (1998).

Other

F. Zhou, M. Molnár, and B. Cousin, "Is light-tree structure optimal for multicast routing in sparse light splitting WDM networks?," 18th Int. Conf. on Computer Communications and Networks (IC3N’09), 2009, San Francisco, CA, pp. 1‒7.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Approximation ratios of multicast light-trees in WDM networks," IEEE Global Communications Conf. (GLOBECOM10), 2010, Miami, FL, pp. 1‒6.

H. Lin and S. Wang, "Splitter placement in all-optical WDM networks," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 306‒310.

F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Cost bounds of multicast light-trees in WDM networks," 9th IFIP Int. Conf. on Networking (Networking 10), 2010, Chennai, India, pp. 94‒105.

O. Yu and Y. Cao, "Mathematical formulation of optical multicast with loss-balanced light-forest," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 1788‒1792.

http://www.ilog.com/products/cplex/

http://www.algorithmic-solutions.com/leda/index.htm

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) An example sparse splitting WDM network.

Fig. 2
Fig. 2

(Color online) A contradictory example with a loop in the resulting light-tree: (a) network topology, (b) result.

Fig. 3
Fig. 3

(Color online) The cost bound of multicast light-trees when the number of destinations K varies.

Fig. 4
Fig. 4

(Color online) (a) The best case, (b) the worst case when K < N 2 , (c) the worst case when K N 2 . All the branching nodes are MI nodes.

Fig. 5
Fig. 5

(Color online) The gaps in a WDM ring.

Fig. 6
Fig. 6

(Color online) Illustration of Theorem 3.

Fig. 7
Fig. 7

(Color online) Illustration of Lemma 5.

Fig. 8
Fig. 8

(Color online) Demonstration of the worst case of the MO algorithm.

Tables (4)

Tables Icon

Table I Summary of the Approximation Ratios Obtained in Sparse Splitting WDM Networks

Tables Icon

Table II Comparison of Cost Bounds in the NSF Network

Tables Icon

Table III Comparison of Approximation Ratios in the NSF Network

Tables Icon

Table IV New Approximation Ratios of R2S and MO in the NSF Network

Equations (65)

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

c ( L P ( u , v ) ) = e L P ( u , v ) c ( e ) .
1 k K N 1 .
D = i = 1 k D i .
i , j [ 1 , k ] and i j , D i D j = Ø .
i = 1 k K i = | D | = K .
C ( m s ( s , D ) ) = i = 1 k c [ L T i ( s , D i ) ] = i = 1 k e L T i ( s , D i ) c ( e ) .
c ( e ) = 1 unit hop-count-cost .
C ( m s ( s , D ) ) = i = 1 k e L T i ( s , D i ) 1 .
K C ( m s ( s , D ) ) N 1 .
C m s ( s , D ) 2 1 1 K + 1 × C O p t ,
K j = | D j | c ( L T j ( s , D j ) ) N k .
K C ( m s ( s , D ) ) K ( N K ) , K < N 2 N 2 4 , K N 2 .
K C ( m s ( s , D ) ) N 1 .
K C ( m s ( s , D ) ) N N K + 1 .
1 C ( H ) C O p t ρ ( H ) , m s ( s , D )  in  G .
ρ ( A O M R ) N K 1 K < N 2 N 2 4 K N 2 K N .
ρ ( R 2 S ) K 1 K < N 2 N 2 4 K N 2 K N 1 .
ρ ( MO ) 1 4 ( K 2 + 3 K ) 1 K < 16 N + 49 7 2 N K 16 N + 49 7 2 K < N 2 N 2 4 K N 2 K N 1 .
Minimize : λ W m V n I n ( m ) L n , m ( λ ) c n , m .
λ W n I n ( s ) L n , s ( λ ) = 0 ,
1 λ W n O u t ( s ) L s , n ( λ ) | D | .
1 λ W n I n ( d ) L n , d ( λ ) | D | , d D .
n I n ( m ) L n , m ( λ ) 1 , λ W ,  and  m V .
n O u t ( m ) L m , n ( λ ) n I n ( m ) L n , m ( λ ) λ W , m V ,  and  m D .
n O u t ( m ) L m , n ( λ ) R × n I n ( m ) L n , m ( λ ) λ W , m V ,  and  m s ,
R = 1 , if  m  is an MI node R = D e g ( m ) 1 , if  m  is an MC node.
n I n ( s ) U n , s d ( λ ) = 0 , λ W ,  and  d D ,
1 λ W n O u t ( s ) U s , n d ( λ ) | D | , d D .
n O u t ( d ) U d , n d ( λ ) = 0 , λ W ,  and  d D ,
n I n ( d ) U n , d d ( λ ) 1 , λ W ,  and  d D ,
1 λ W n I n ( d ) U n , d d ( λ ) | D | 1 , d D .
n O u t ( m ) U m , n d ( λ ) = n I n ( m ) U n , m d ( λ ) 1 λ W , d D , m V ,  and  m s , d ,
λ W n O u t ( m ) U m , n d ( λ ) | D | λ W , d D , m V ,  and  m s , d .
L m , n ( λ ) d D U m , n d ( λ ) , λ W ,  and  m , n V ,
U m , n d ( λ ) L m , n ( λ ) , λ W , m , n V ,  and  d D .
c ( L F ) K × Diam ( G ) .
ρ ( L F ) K × Diam ( G ) / K = Diam ( G ) .
K j c ( L T j ( s , D j ) ) N k .
C ( m s ( s , D ) ) i = 1 k ( N k ) k ( N k ) k N 2 2 + N 2 4 .
C ( m s ( s , D ) ) K ( N K ) , K < N 2 N 2 4 , K N 2  and  N  is even N 2 1 4 , K N 2  and  N  is odd.
C ( m s ( s , D ) ) i = 1 k K i = K .
i = 1 K + 1 g i = N .
C ( m s ( s , D ) ) = N max 1 i K + 1 g i .
max 1 i K + 1 g i N K + 1 .
C ( m s ( s , D ) ) N N K + 1 .
C ( m s ( s , D ) ) K .
r max = max d i D c [ S P ( s , d i ) ] .
C O p t r max .
ρ ( R 2 S ) = C ( R 2 S ) / C O p t d i D c ( S P ( s , d i ) ) / C O p t | D | r max / r max K .
C ( R 2 S ) = K r + K 1 2 ,
C O p t = r + ( K 1 ) ( 1 + δ ) .
ρ ( R 2 S ) = K 1 1 2 r ( K 1 ) ( 1 + 2 δ ) + 2 ( 1 + δ ) 1 + 2 δ .
l C P 1 2 ( l A B + l A C + l B C ) .
l A B = l A P + l B P .
l C P l A C + l A P ,
l C P l B C + l B P .
2 l C P ( l A P + l B P ) + l A C + l B C .
l max = max m i , m j s D c [ S P ( m i , m j ) ] .
l 3 1 2 ( c [ S P ( A 2 , d 3 ) ] + c ( S P ( d 2 , d 3 ) ) + l 2 ) 1 2 ( l 2 m + l max + l 2 ) l 2 m + 1 2 l max .
l 3 m = l 2 m + 1 2 l max .
l i m = l i 1 m + 1 2 l max .
l i + 1 1 2 ( c [ S P ( A i , d i + 1 ) ] + c ( S P ( d i , d i + 1 ) ) + l i ) = 1 2 ( l i m + l max + l i ) l i m + 1 2 l max .
c ( L T i ) = i = 1 | D i | l i i = 1 | D i | l i m 1 4 ( D i 2 + 3 | D i | ) l max .
C ( MO ) = i = 1 k c ( L T i ) i = 1 k 1 4 ( D i 2 + 3 | D i | ) l max 1 4 3 | D | + i = 1 k D i 2 l max 1 4 ( 3 | D | + D 2 ) l max .
ρ ( MO ) = C ( MO ) / C O p t C ( MO ) / l max 1 4 ( 3 K + K 2 ) .