Abstract

Telecom mesh networks require periodic upgrades to support increasing traffic. Such upgrades, which are referred to as network engineering (NE), determine the additional network resources that must be provided to meet the network performance while minimizing the incremental network cost. To facilitate such network growth, considering dynamic routing, attention should be directed toward critical cut sets rather than individual links. Our analysis in this paper shows how capacity exhaustion of critical cut sets indicates urgency of the need for upgrading a mesh network. To handle traffic growth, we also introduce a new parameter called the network-cut exhaustion probability. This parameter is efficient and appropriate to assist incremental growth of the existing network as well as new network design. Finally, we provide an algorithm to calculate the urgency and the pointers to specific locations that require upgrade under desired performance constraints.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. B. Mukherjee, Optical WDM Networks. Springer, 2006.
  2. A. Girard, R. Page, “Dimensioning of telephone networks with nonhierarchical routing and trunk reservation,” in Proc. Network Planning Symp., June 1986, pp. 85–93.
  3. F. P. Kelly, “Routing and capacity allocation in networks with trunk reservation,” in Proc. Mathematics of Operations Research, 1990, pp. 771–793.
  4. M. Pioro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Elsevier, 2004.
  5. M. P. Pioro, “A uniform approach to the analysis and optimization of circuit switched communication networks,” in Proc. Int. Teletraffic Congr., 1983.
  6. R. J. Harris, “Comparison of network dimensioning models,” in Proc. Australian Telecommunication Research, 1984, pp. 59–69.
  7. T. K. Nayak, K. N. Sivaranjan, “A new approach to dimensioning optical networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 134–148, Jan. 2002.
    [CrossRef]
  8. T. K. Nayak, K. N. Sivaranjan, “Dimensioning optical networks under traffic growth models,” IEEE/ACM Trans. Netw., vol. 11, no. 6, pp. 935–947, Dec. 2003.
    [CrossRef]
  9. S. Tsukiyama, I. Shirakawa, H. Ozaki, H. Ariyoshi, “An algorithm to enumerate all cutsets of a graph in linear time per cutset,” J. ACM, vol. 27, no. 4, pp. 619–632, Oct. 1980.
    [CrossRef]
  10. K. Zhu, L. Sahasrabuddhe, B. Mukherjee, “Topology design and upgrade of an optical network by bottleneck-cut identification,” J. High Speed Networks, vol. 10, no. 4, pp. 293–301, Oct. 2001.
  11. W. Feller, An Introduction to Probability Theory and Its Applications. New York: Wiley, 1968.
  12. J. Kleinberg, E. Tardos, Algorithm Design. Addison Wesley, 2005.
  13. T. Leighton, S. Rao, “Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms,” J. ACM, vol. 46, no. 6, pp. 787–832, Nov. 1999.
    [CrossRef]
  14. R. Roy, M. Tornatore, “Cost-efficient non-blocking WDM network upgrade,” in Optical Fiber Communication Conf. and Expo., San Diego, Mar. 2009.

2003 (1)

T. K. Nayak, K. N. Sivaranjan, “Dimensioning optical networks under traffic growth models,” IEEE/ACM Trans. Netw., vol. 11, no. 6, pp. 935–947, Dec. 2003.
[CrossRef]

2002 (1)

T. K. Nayak, K. N. Sivaranjan, “A new approach to dimensioning optical networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 134–148, Jan. 2002.
[CrossRef]

2001 (1)

K. Zhu, L. Sahasrabuddhe, B. Mukherjee, “Topology design and upgrade of an optical network by bottleneck-cut identification,” J. High Speed Networks, vol. 10, no. 4, pp. 293–301, Oct. 2001.

1999 (1)

T. Leighton, S. Rao, “Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms,” J. ACM, vol. 46, no. 6, pp. 787–832, Nov. 1999.
[CrossRef]

1980 (1)

S. Tsukiyama, I. Shirakawa, H. Ozaki, H. Ariyoshi, “An algorithm to enumerate all cutsets of a graph in linear time per cutset,” J. ACM, vol. 27, no. 4, pp. 619–632, Oct. 1980.
[CrossRef]

Ariyoshi, H.

S. Tsukiyama, I. Shirakawa, H. Ozaki, H. Ariyoshi, “An algorithm to enumerate all cutsets of a graph in linear time per cutset,” J. ACM, vol. 27, no. 4, pp. 619–632, Oct. 1980.
[CrossRef]

Feller, W.

W. Feller, An Introduction to Probability Theory and Its Applications. New York: Wiley, 1968.

Girard, A.

A. Girard, R. Page, “Dimensioning of telephone networks with nonhierarchical routing and trunk reservation,” in Proc. Network Planning Symp., June 1986, pp. 85–93.

Harris, R. J.

R. J. Harris, “Comparison of network dimensioning models,” in Proc. Australian Telecommunication Research, 1984, pp. 59–69.

Kelly, F. P.

F. P. Kelly, “Routing and capacity allocation in networks with trunk reservation,” in Proc. Mathematics of Operations Research, 1990, pp. 771–793.

Kleinberg, J.

J. Kleinberg, E. Tardos, Algorithm Design. Addison Wesley, 2005.

Leighton, T.

T. Leighton, S. Rao, “Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms,” J. ACM, vol. 46, no. 6, pp. 787–832, Nov. 1999.
[CrossRef]

Medhi, D.

M. Pioro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Elsevier, 2004.

Mukherjee, B.

K. Zhu, L. Sahasrabuddhe, B. Mukherjee, “Topology design and upgrade of an optical network by bottleneck-cut identification,” J. High Speed Networks, vol. 10, no. 4, pp. 293–301, Oct. 2001.

B. Mukherjee, Optical WDM Networks. Springer, 2006.

Nayak, T. K.

T. K. Nayak, K. N. Sivaranjan, “Dimensioning optical networks under traffic growth models,” IEEE/ACM Trans. Netw., vol. 11, no. 6, pp. 935–947, Dec. 2003.
[CrossRef]

T. K. Nayak, K. N. Sivaranjan, “A new approach to dimensioning optical networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 134–148, Jan. 2002.
[CrossRef]

Ozaki, H.

S. Tsukiyama, I. Shirakawa, H. Ozaki, H. Ariyoshi, “An algorithm to enumerate all cutsets of a graph in linear time per cutset,” J. ACM, vol. 27, no. 4, pp. 619–632, Oct. 1980.
[CrossRef]

Page, R.

A. Girard, R. Page, “Dimensioning of telephone networks with nonhierarchical routing and trunk reservation,” in Proc. Network Planning Symp., June 1986, pp. 85–93.

Pioro, M.

M. Pioro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Elsevier, 2004.

Pioro, M. P.

M. P. Pioro, “A uniform approach to the analysis and optimization of circuit switched communication networks,” in Proc. Int. Teletraffic Congr., 1983.

Rao, S.

T. Leighton, S. Rao, “Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms,” J. ACM, vol. 46, no. 6, pp. 787–832, Nov. 1999.
[CrossRef]

Roy, R.

R. Roy, M. Tornatore, “Cost-efficient non-blocking WDM network upgrade,” in Optical Fiber Communication Conf. and Expo., San Diego, Mar. 2009.

Sahasrabuddhe, L.

K. Zhu, L. Sahasrabuddhe, B. Mukherjee, “Topology design and upgrade of an optical network by bottleneck-cut identification,” J. High Speed Networks, vol. 10, no. 4, pp. 293–301, Oct. 2001.

Shirakawa, I.

S. Tsukiyama, I. Shirakawa, H. Ozaki, H. Ariyoshi, “An algorithm to enumerate all cutsets of a graph in linear time per cutset,” J. ACM, vol. 27, no. 4, pp. 619–632, Oct. 1980.
[CrossRef]

Sivaranjan, K. N.

T. K. Nayak, K. N. Sivaranjan, “Dimensioning optical networks under traffic growth models,” IEEE/ACM Trans. Netw., vol. 11, no. 6, pp. 935–947, Dec. 2003.
[CrossRef]

T. K. Nayak, K. N. Sivaranjan, “A new approach to dimensioning optical networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 134–148, Jan. 2002.
[CrossRef]

Tardos, E.

J. Kleinberg, E. Tardos, Algorithm Design. Addison Wesley, 2005.

Tornatore, M.

R. Roy, M. Tornatore, “Cost-efficient non-blocking WDM network upgrade,” in Optical Fiber Communication Conf. and Expo., San Diego, Mar. 2009.

Tsukiyama, S.

S. Tsukiyama, I. Shirakawa, H. Ozaki, H. Ariyoshi, “An algorithm to enumerate all cutsets of a graph in linear time per cutset,” J. ACM, vol. 27, no. 4, pp. 619–632, Oct. 1980.
[CrossRef]

Zhu, K.

K. Zhu, L. Sahasrabuddhe, B. Mukherjee, “Topology design and upgrade of an optical network by bottleneck-cut identification,” J. High Speed Networks, vol. 10, no. 4, pp. 293–301, Oct. 2001.

IEEE J. Sel. Areas Commun. (1)

T. K. Nayak, K. N. Sivaranjan, “A new approach to dimensioning optical networks,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 134–148, Jan. 2002.
[CrossRef]

IEEE/ACM Trans. Netw. (1)

T. K. Nayak, K. N. Sivaranjan, “Dimensioning optical networks under traffic growth models,” IEEE/ACM Trans. Netw., vol. 11, no. 6, pp. 935–947, Dec. 2003.
[CrossRef]

J. ACM (2)

S. Tsukiyama, I. Shirakawa, H. Ozaki, H. Ariyoshi, “An algorithm to enumerate all cutsets of a graph in linear time per cutset,” J. ACM, vol. 27, no. 4, pp. 619–632, Oct. 1980.
[CrossRef]

T. Leighton, S. Rao, “Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms,” J. ACM, vol. 46, no. 6, pp. 787–832, Nov. 1999.
[CrossRef]

J. High Speed Networks (1)

K. Zhu, L. Sahasrabuddhe, B. Mukherjee, “Topology design and upgrade of an optical network by bottleneck-cut identification,” J. High Speed Networks, vol. 10, no. 4, pp. 293–301, Oct. 2001.

Other (9)

W. Feller, An Introduction to Probability Theory and Its Applications. New York: Wiley, 1968.

J. Kleinberg, E. Tardos, Algorithm Design. Addison Wesley, 2005.

B. Mukherjee, Optical WDM Networks. Springer, 2006.

A. Girard, R. Page, “Dimensioning of telephone networks with nonhierarchical routing and trunk reservation,” in Proc. Network Planning Symp., June 1986, pp. 85–93.

F. P. Kelly, “Routing and capacity allocation in networks with trunk reservation,” in Proc. Mathematics of Operations Research, 1990, pp. 771–793.

M. Pioro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. Elsevier, 2004.

M. P. Pioro, “A uniform approach to the analysis and optimization of circuit switched communication networks,” in Proc. Int. Teletraffic Congr., 1983.

R. J. Harris, “Comparison of network dimensioning models,” in Proc. Australian Telecommunication Research, 1984, pp. 59–69.

R. Roy, M. Tornatore, “Cost-efficient non-blocking WDM network upgrade,” in Optical Fiber Communication Conf. and Expo., San Diego, Mar. 2009.

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

Example network with network cut.

Fig. 2
Fig. 2

Cut-to-link transformation.

Fig. 3
Fig. 3

Markov chain of the busy-wavelength distribution over a network cut.

Fig. 4
Fig. 4

Cut-exhaustion probability under different traffic-growth models: (a) linear traffic growth, (b) exponential traffic growth.

Fig. 5
Fig. 5

r-drop Markov chain of the busy-wavelength distribution over a network cut.

Fig. 6
Fig. 6

Time-varying ( N + r + 1 ) × ( N + r + 1 ) matrix A ( t ) .

Fig. 7
Fig. 7

r-drop cut-exhaustion probability under different traffic growth models: (a) constant traffic, (b) linear traffic growth.

Fig. 8
Fig. 8

Sample network topology.

Fig. 9
Fig. 9

Exhaustion probability under constant traffic model.

Fig. 10
Fig. 10

Percentage of blocked connections for one-, two-, three-, four-, five-, and six-hop routes due to cut C 1 .

Fig. 11
Fig. 11

Exhaustion probability of cuts C 1 and C 2 in Fig. 8 under linear traffic-growth model.

Fig. 12
Fig. 12

Exhaustion probability for cut C ( S , T ) of the topology in Fig. 2 under linear traffic-growth model.

Fig. 13
Fig. 13

Capacity assignment of critical cuts (a) C 1 and (b) C 2 under a linear traffic-growth model.

Tables (1)

Tables Icon

Table 1 Traffic Demand Matrix

Equations (26)

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

x 1 , 3 + x 2 , 3 + x 2 , 4 λ 1 , 4 + λ 1 , 3 + λ 2 , 4 + λ 2 , 3 ,
x 3 , 1 + x 3 , 2 + x 4 , 2 λ 3 , 1 + λ 3 , 2 + λ 4 , 1 + λ 4 , 2 ,
e S , T C ( e ) i | s i S t i T D i ,
x 1 , 3 + x 2 , 3 + x 2 , 4 75 ,
x 1 , 2 + x 3 , 2 + x 3 , 4 90 ,
x 1 , 2 + x 1 , 3 + x 4 , 2 + x 4 , 3 90 ,
x 1 , 3 + x 1 , 2 45 ,
x 2 , 1 + x 2 , 3 + x 2 , 4 80 ,
x 3 , 1 + x 3 , 2 + x 3 , 4 65 ,
x 4 , 2 + x 4 , 3 65 .
i j x i , j b i , j ,
P n ( t ) = [ λ ( t ) + n μ ] P n ( t ) + λ ( t ) P n 1 ( t ) + ( n + 1 ) μ P n + 1 ( t )
P 0 ( t ) = λ ( t ) P 0 ( t ) + μ P 1 ( t ) ,
P N ( t ) = [ λ ( t ) + N μ ] P N ( t ) + λ ( t ) P N 1 ( t ) ,
P N + 1 ( t ) = λ ( t ) P N ( t ) ,
P i ( 0 ) = 1 , P n ( 0 ) = 0 for n i .
P n ( t ) = [ λ ( t ) + n μ ] P n ( t ) + λ ( t ) P n 1 ( t ) + ( n + 1 ) μ P n + 1 ( t )
P 0 ( t ) = λ ( t ) P 0 ( t ) + μ P 1 ( t ) ,
P N 1 ( t ) = [ λ ( t ) + N μ ] P N 1 ( t ) + λ ( t ) P N 2 ( t ) + N μ i = 0 r 1 P N + i ( t ) ,
P n ( t ) = [ λ ( t ) + N μ ] P n ( t ) + λ ( t ) P n 1 ( t )
P N + r ( t ) = λ ( t ) P N + r 1 ( t ) ,
P i ( 0 ) = 1 , P n ( 0 ) = 0 for n i .
P ( t ) = { P 0 ( t ) P 1 ( t ) P 2 ( t ) P N + r ( t ) } T .
Γ = min U V log [ C ( U , U ¯ ) D ( U , U ¯ ) ] ,
C ( U , U ¯ ) = e U , U ¯ C ( e )
D ( U , U ¯ ) = i | s i U t i U ¯ or t i U s i U ¯ D i