Koster A., Munoz X. Graphs and Algorithms in Communication Networks

Подождите немного. Документ загружается.

2 Trafﬁc Grooming: Combinatorial Results and Practical Resolutions 87

2.5.3.8 Cross-layer Optimization: Considering Physical Impairments While

Routing

Often, in networks it is not enough to consider the available resources, but it is also

necessary to consider the impairments that affect the signal quality at the physical

layer and cause increased Bit Error Rate for services. This is a kind of cross-layer

optimization, where the services are optimized with physical layer constraints.

The ﬁrst use of grooming to repair the impaired signal was presented in [88]

where such VPNs were conﬁgured, where the signal quality was satisfactory since

the physical impairments were considered. In [120] the results were extended for

routing in general. [107, 119] present deeper results on the same topic, while [46]

gives an overview of the problem, and proposes an additional method for improving

the signal quality by increasing the power level of signals that have to go far while

decreasing the power levels of signals that go to closer destinations in order to avoid

the harmful effect of nonlinear distortions.

2.6 Conclusion

The objective of this chapter was to present an overview of trafﬁc grooming in

connection-oriented networks (mainly in WDM networks) and the wide variety of

mathematical tools used to address this issue. Trafﬁc grooming refers to techniques

used for an efﬁcient sharing of the bandwitdh offers by, e.g., a wavelength, using

Time Division Multiplexing. It is usually associated with the routing of the requests

and the survivability issue in single or multiple failure scenarios. Furthermore, traf-

ﬁc requests might be uni- or multicast, the trafﬁc pattern may evolve with time, and

the network could be multilayer. Therefore, trafﬁc grooming is only part of the con-

cerns addressed when designing and optimizing a network. But even when restricted

to simple physical topologies (unidirectional path or ring) where the routing is ﬁxed

and with small grooming factor, the trafﬁc grooming problem is difﬁcult to solve

and to approximate. Also, when all aspects have to be taken into account (trafﬁc

grooming, routing, survivability, and so on), problems to solve are so difﬁcult that

exact solutions are usually no longer expected, and it is essential to develop efﬁ-

cient heuristic algorithms. Some of them were presented in Section 2.5. Chapter 3

presents the state-of-the-art regarding exact approaches for this problem.

In this research area, several important questions are still open and further re-

search are needed. In particular, when optimizing only the number of ADMs in

SONET/SDH networks, practical values of the grooming factor are 3 and 4, but this

is reapeated several time from the slower 55 Mbit/s streams to the current 10 Gbit/s

wavelengths. So, it is important to develop efﬁcient optimization tools for grooming

factors 3 and 4, but also to consider hierarchical problems in which unitary requests

are combined by four into streams that are themselves combined by four, and so on.

In the general context, where trafﬁc grooming is associated with routing and sur-

vivability issues, existing heuristic algorithms provide upper bounds without guar-

88 T. Cinkler et al.

antee on the quality of the solution. Furthermore, the size of practical problems is

too huge for existing mathematical tools. Therefore, research effort has to be put into

the development of new mathematical tools allowing us to address large instances

and to obtain optimal or near-optimal solutions.

Acknowledgements This work was partially supported by EU COST action 293 – Graphs and

Algorithms in Communication Networks (GRAAL), COST action 291 – Towards Digital Optical

Networks, and IST FET AEOLUS.

The authors would like to thank speciﬁcally European Action COST 293 GRAAL, which of-

fered us a fruitful scientiﬁc framework to share ideas and expertise with other researchers.

References

1. Amini, O., Peleg, D., Perennes, S., Sau, I., Saurabh, S.: Degree-constrained subgraph prob-

lems: Hardness and approximation results. In: 6th Workshop on Approximation and Online

Algorithms (WAOA), Lecture Notes in Computer Science, vol. 5426, pp. 29–42. Springer

(2009)

2. Amini, O., P

erennes, S., Sau Valls, I.: Hardness and approximation of trafﬁc grooming. In:

The 18th International Symposium on Algorithms and Computation (ISAAC 2007). Sendai,

Japan (2007)

3. Beauquier, B., Bermond, J. C., Gargano, L., Hell, P., Perennes, S., Vaccaro, U.: Graph

problems arising from wavelength–routing in all–optical networks. In: Proc. Conference

WOCS97, Geneva,April 1997 (1997)

4. Bermond, J. C., Braud, L., Coudert, D.: Trafﬁc grooming on the path. Theoretical Computer

Science 384(2-3), 139–151 (2007)

5. Bermond, J. C., Ceroi, S.: Minimizing SONET ADMs in unidirectional WDM ring with

grooming ratio 3. Networks 41(2), 83–86 (2003)

6. Bermond, J. C., Colbourn, C., Coudert, D., Ge, G., Ling, A., Mu

noz, X.: Trafﬁc grooming in

unidirectional WDM rings with grooming ratio C=6. SIAM Journal on Discrete Mathematics

19(2), 523–542 (2005). DOI 10.1137/S0895480104444314

7. Bermond, J. C., Colbourn, C., Ling, A., Yu, M. L.: Grooming in unidirectional rings: k

−e

designs. Discrete Mathematics, Lindner’s Volume 284(1-3), 57–62 (2004)

8. Bermond, J. C., Cosnard, M., Coudert, D., Perennes, S.: Optimal solution of the maximum

all request path grooming problem. In: Advanced International Conference on Telecommu-

nications (AICT). IEEE (2006)

9. Bermond, J. C., Coudert, D.: Trafﬁc grooming in unidirectional WDM ring networks using

design theory. In: IEEE ICC, vol. 2, pp. 1402–1406. Anchorage, Alaska (2003). ON07-3

10. Bermond, J. C., Coudert, D.: Handbook of Combinatorial Designs (2nd edition), Discrete

Mathematics and Applications, vol. 42, chap. VI.27, Grooming, pp. 494–496. Chapman &

Hall- CRC Press, editors C. J. Colbourn and J. H. Dinitz (2006)

11. Bermond, J. C., Coudert, D., Mu

noz, X.: Trafﬁc grooming in unidirectional WDM ring net-

works: The all-to-all unitary case. In: The 7th IFIP Working Conference on Optical Network

Design & Modelling – ONDM, pp. 1135–1153. Budapest, Hongrie (2003)

12. Bermond, J. C., Coudert, D., Mu

noz, X., Sau Valls, I.: Trafﬁc grooming in bidirectional

WDM ring networks. In: IEEE-LEOS ICTON / COST 293 GRAAL, vol. 3, pp. 19–22

(2006)

13. Bermond, J. C., Coudert, D., Yu, M. L.: On DRC-Covering of K

by cycles. Journal of

Combinatorial Designs 11(2), 100–112 (2003)

14. Bil

o, V., Flammini, M., Moscardelli, L.: On nash equilibria in non-cooperative all-optical

networks. In: STACS, Lecture Notes in Computer Science, vol. 3404, pp. 448–459. Springer

(2005)

2 Trafﬁc Grooming: Combinatorial Results and Practical Resolutions 89

15. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge Uni-

versity Press (1998)

16. Brehon, Y., Kofman, D.: Bus-label switched paths, an approach to reduce the cost of mul-

tilayer networks. In: IEEE International Conference on Communication (ICC), vol. 5, pp.

2401 – 2406. Istanbul (2006). DOI 10.1109/ICC.2006.255129

17. Brehon, Y., Kofman, D., Pioro, M., Diallo, M.: Optimal virtual topology design using bus-

label switched paths. IEEE Journal on Selected Areas in Communications 25(5), 1001 –

1010 (2007). DOI 10.1109/JSAC.2007.364261

18. Cao, X., Anand, V., Qiao, C.: Waveband switching for dynamic trafﬁc demands in multigran-

ular optical networks. IEEE/ACM Transactions on Networking (2007). DOI 10.1109/TNET.

2007.896234

19. Chen, L. W., Modiano, E., Saengudomlert, P.: Optimal waveband switching in WDM net-

works. In: IEEE International Conference on Communication (ICC), pp. 1604 – 1608. Paris,

France (2004). DOI 10.1109/ICC.2004.1312781

20. Chen, L. W., Modiano, E., Saengudomlert, P.: Uniform versus non-uniform band switching

in WDM networks. Computer Networks 50(2), 149–167 (2006). DOI doi:10.1016/j.comnet.

2005.05.017

21. Chiu, A. L., Modiano, E. H.: Trafﬁc grooming algorithms for reducing electronic multiplex-

ing costs in WDM ring networks. IEEE/OSA Journal of Lightwave Technology 18(1), 2–12

(2000)

22. Chlamtac, I., Farag

o, A., Zhang, T.: Lightpath (wavelength) routing in large WDM networks.

IEEE Journal on Select. Areas Commun. 14, 909–913 (1996)

23. Chow, T. Y., Lin, P. J.: The Ring Grooming Problem. Networks 44, 194–202 (2004)

24. Cinkler, T.: Heuristic algorithms for conﬁguration of the ATM-layer over optical networks.

In: ICC’97, IEEE International Conference on Communications, pp. 1164–1168. Montreal,

Canada (1997)

25. Cinkler, T.: ILP formulation of grooming over wavelength routing with protection. In:

ONDM 2001, IFIP ONDM 5th Conference on Optical Network Design and Modeling, pp.

25–48. Kluwer, Vienna (2001)

26. Cinkler, T.: ILP formulation of grooming over wavelength routing with protection. In:

A. Jukan (ed.) Towards an Optical Internet, New Visions in Optical Network Design and

Modelling, pp. 25–48. Kluwer (2002)

27. Cinkler, T.: Trafﬁc- and

-grooming. IEEE Network 17(2), 16–21 (2003)

28. Cinkler, T.: Conﬁguring trafﬁc grooming VP

Ns. Special Issue of the Photonic Network

Communications on Optical Virtual Private Networks (oVPNs) 7(3), 239–253 (2004)

29. Cinkler, T.: Routing, TE and resilience in heterogeneous GMPLS networks. In:

MPLS/GMPLS Workshop. Girona, Spain (2006)

30. Cinkler, T.: On ‘a priori’ and ‘a posteriori’ multi-layer trafﬁc engineering schemes. In: IEEE

ICC 2007, IEEE International Conference on Communications – WorkShop on Trafﬁc Engi-

neering in Next-Generation IP Networks. Glasgow, Scotland (2007)

31. Cinkler, T., Ast, L., Farag

o, A., Henk, T.: Conﬁguration of the ATM-layer over optical net-

works. In: Fifth International Conference on Telecommunication Systems Modelling and

Analysis. Nashville, TN (1997)

32. Cinkler, T., Castro, R., Johansson, S.: Conﬁguration and re-conﬁguration of WDM net-

works. In: NOC’98, European Conference on Networks & Optical Communications, pp.

6–13. Manchester, UK (1998)

33. Cinkler, T., Cinkler, K., Tr

on, T., Hal

asz, E.: On almost-all-optical ATM networks. In: Eighth

IEEE Workshop on Local and Metropolitan Area Networks. Potsdam (1996)

34. Cinkler, T., G

asp

ar, C.: Fairness issues of routing with grooming and shared protection.

In: ONDM 2004, 8th Conference on Optical Network Design and Modelling, pp. 665–684.

Ghent, Belgium (2004)

35. Cinkler, T., Geleji, G., Asztalos, M., Hegyi, P., Kern, A., Szigeti, J.: Lambda-path fragmen-

tation and de-fragmentation through dynamic grooming. In: IEEE ICTON 2005, 7th Inter-

national Conference on Transparent Optical Networks. Barcelona, Spain (2005)

90 T. Cinkler et al.

36. Cinkler, T., Hegyi, P., Asztalos, M., Geleji, G., Szigeti, J., Kern, A.: Multi-layer trafﬁc en-

gineering through adaptive

-path fragmentation and de-fragmentation. In: F. Boavida,

T. Plagemann, B. Stiller, C. Westphal, E. Monteiro (eds.) Networking, Lecture Notes in Com-

puter Science, vol. 3976 / 2006, pp. 715–726. Springer, Berlin/Heidelberg (2006)

37. Cinkler, T., Hegyi, P., Asztalos, M., Geleji, G., Szigeti, J., Kern, A.: Multi-layer trafﬁc engi-

neering through adaptive lambda-path fragmentation and de-fragmentation: The “grooming-

graph” and the “shadow-capacities”. In: IFIP Networking. Coimbra, Portugal (2006)

38. Cinkler, T., Hegyi, P., Geleji, G., Szigeti, J.: Conﬁgured vs. switched underlying wavelength

system for trafﬁc engineering with grooming. In: TelFor 2006, 14th Telecommunications

Forum. Belgrade, Serbia (2006)

39. Cinkler, T., Hegyi, P., Geleji, G., Szigeti, J.: Multi-layer trafﬁc engineering: Should only the

upper-most layer be switched? In: ONDM 2006. Copenhagen, Danemark (2006)

40. Cinkler, T., Hegyi, P., Geleji, G., Szigeti, J.: Fairness issues of AMLTE: Adaptive multi-

layer trafﬁc engineering with grooming. In: ICTON 2007, 9th International Conference on

Transparent Optical Networks. Rome, Italy (2007)

41. Cinkler, T., Hegyi, P., Geleji, G., Szigeti, J.: Protection for adaptive multi-layer trafﬁc engi-

neering. In: DRCN 2007, 6th International Workshop on the Design of Reliable Communi-

cation Networks. La Rochelle, France (2007)

42. Cinkler, T., Hegyi, P., Geleji, G., Szigeti, J.: Adaptive multi-layer trafﬁc engineering with

shared risk group protection. In: ICC2008, IEEE International Conference on Communica-

tions, Optical Networks and Systems Symposium. Beijing, China (2008)

43. Cinkler, T., Larsen, C. P.: Integer linear programming (ILP) formulation of the optimal light-

path conﬁguration problem in wavelength-routing WDM networks. In: ONDM’99, Third

Working Conference on Optical Network Design and Modelling, IFIP TC6/WG 6.10 (Task

Group on Photonic Communication Networks). Paris, France (1999)

44. Cinkler, T., Marx, D., Larsen, C. P., Fogaras, D.: Heuristic algorithms for joint conﬁgura-

tion of the optical and electrical layer in multi-hop wavelength routing networks. In: IEEE

INFOCOM 2000, pp. 1000–1009. Tel Aviv (2000)

45. Cinkler, T., Per

enyi, M., Soproni, P.: Restoration of multi-cast trees in optical-beared

grooming-capable two-layer networks. In: ICTON 2008, 10th Aniversary International Con-

ference on Transparent Optical Networks, pp. 14–18. Athens, Greece (2008)

46. Cinkler, T., Zsigmond, S., Per

enyi, M.: Trafﬁc grooming and power level tuning for physical

impairment constrained routing. In: ICTON 2008, 10th Aniversary International Conference

on Transparent Optical Networks, pp. 162–165. Athens, Greece (2008)

47. Colbourn, C., Dinitz, J. (eds.): Handbook of Combinatorial Designs, 2 edn. Chapman &

Hall/CRC (2006)

48. Colbourn, C., Fu, H. L., Ge, G., Ling, A., Lu, H. C.: Minimizing SONET ADMs in uni-

directional WDM rings with grooming ratio seven. SIAM J. Discrete Mathematics 23(1),

109–122 (2008)

49. Colbourn, C., Ling, A.: Trafﬁc grooming algorithms for reducing electronic multiplexing

costs in WDM ring networks. Discrete Mathematics 261(1-3), 141–156 (2003)

50. Colbourn, C., Wan, P. J.: Minimzing drop cost for SONET/WDM networks with

wave-

length requirements. Networks 37(2), 107–116 (2001)

51. Crouser, R., Rice, B., Sampson, A.: On-line distributed trafﬁc grooming. In: IEEE Inter-

national Conference on Communication (ICC), pp. 5239 – 5246. Beijing (2008). DOI

10.1109/ICC.2008.984

52. C

alinescu, G., Frieder, O., Wan, P. J.: Minimizing electronic line terminals for automatic ring

protection in general WDM optical networks. IEEE Journal of Selected Area on Communi-

cations 20(1), 183–189 (2002)

53. C

alinescu, G., Wan, P. J.: Splitable trafﬁc partition in WDM/SONET rings to minimize

SONET ADMs. Theoretical Computer Science 276(1-2), 33–50 (2002)

54. Di Giannantonio, S., Flammini, M., Monaco, G., Moscardelli, L., Shalom, M., Zaks, S.:

Selﬁshness, collusion and power of local search for the ADMs minimization problem. In:

S. B.. Heidelberg (ed.) WINE, Lecture Notes in Computer Science (2007)

2 Trafﬁc Grooming: Combinatorial Results and Practical Resolutions 91

55. Dutta, R., Kamal, A. E., Rouskas, G. N. (eds.): Trafﬁc Grooming for Optical Networks:

Foundations, Techniques and Frontiers. Optical Networks. Springer (2008)

56. Dutta, R., Rouskas, N.: A survey of virtual topology design algorithms for wavelength routed

optical networks. Optical Networks 1(1), 73–89 (2000)

57. Dutta, R., Rouskas, N.: Trafﬁc grooming in WDM networks: Past and future. IEEE Network

16(6), 46–56 (2002)

58. Eilam, T., Moran, S., Zaks, S.: Lightpath arrangement in survivable rings to minimize the

switching cost. IEEE Journal of Selected Area on Communications 20(1), 172–182 (2002)

59. Epstein, L., Levin, A.: Better bounds for minimizing SONET ADMs. In: S. B.. Heidelberg

(ed.) 2nd Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in

Computer Science, vol. 3351, pp. 281–294. Bergen, Norway (2004). DOI 10.1007/b106130

60. Epstein, L., Levin, A.: SONET ADMs minimization with divisible paths. In: S. B..

Heidelberg (ed.) 3rd International Workshop on Approximation and Online Algorithms

–WAOA,Lecture Notes in Computer Science, vol. 3879, pp. 119–132 (2005). DOI

10.1007/11671411

61. Feige, U., Peleg, D., Kortsarz, G.: The Dense k-Subgraph Problem. Algorithmica 29(3),

410–421 (2001)

62. Flammini, M., Monaco, G., Moscardelli, L., Shalom, M., Zaks, S.: Approximating the trafﬁc

grooming problem in tree and star networks. In: WG, Lecture Notes in Computer Science,

vol. 4271, pp. 147–158. Springer (2006)

63. Flammini, M., Moscardelli, L., Shalom, M., Zaks, S.: Approximating the trafﬁc grooming

problem. Journal of Discrete Algorithms 6(3), 472–479 (2008)

64. Flammini, M., Shalom, M., Zaks, S.: On minimizing the number of ADMs – tight bounds for

an algorithm without preprocessing. Journal of Parallel and Distributed Computing 67(4),

448–455 (2007). Also in Proceedings of the 3rd Workshop on Combinatorial and Algorith-

mic Aspects of Networking (CAAN), Chester, United Kingdom, July 2006

65. Flammini, M., Shalom, M., Zaks, S.: On minimizing the number of ADMs in a general

topology optical network. Discrete Applied Mathematics 157, 2701–2717 (2009). Also in

Proceedings of 20th International Workshop on Distributed Algorithms (DISC), Stockholm,

Sweden, September 2006

66. F

op, L., Cinkler, T.: Algorithms for grooming over wavelength routing with protection.

In: DRCN 3rd Conference on Design of Reliable Communication Networks, pp. 160–167.

Budapest (2001)

67. G

asp

ar, C., Mak

acs, G., Cinkler, T., Tapolcai, J.: Wavelength routing with grooming and pro-

tection. In: IFIP ONDM 2003, 7th Conference on Optical Network Design and Modelling.

Budapest, Hungary (2003)

68. G

asp

ar, C., Szentes, S., Tapolcai, J., Cinkler, T.: Approximative algorithms for conﬁguration

of multi-layer networks with protection. In: A. Jukan (ed.) DRCN 3rd Conference on Design

of Reliable Communications Networks, pp. 228–235. Budapest (2001)

69. Gerstel, O., Lin, P., Sasaki, G.: Wavelength assignment in a WDM ring to minimize cost of

embedded SONET rings. In: IEEE INFOCOM, pp. 94–101 (1998)

70. Gerstel, O., Ramaswani, R., Sasaki, G.: Cost-effective trafﬁc grooming in WDM rings.

IEEE/ACM Transactions on Networking 8(5), 618–630 (2000)

71. Goldschmidt, O., Hochbaum, D., Levin, A., Olinick, E.: The SONET edge-partition problem.

Networks 41(1), 13–23 (2003)

72. Hong-Hsu, Y., Lee, S., Mukherjee, B.: Trafﬁc grooming and delay constrained multicast

routing in IP over WDM networks. In: IEEE International Conference on Communication

(ICC), pp. 5246 – 5251. Beijing (2008). DOI 10.1109/ICC.2008.985

73. Hu, J.: Optimal trafﬁc grooming for wavelength-division-multiplexing rings with all-to-all

uniform trafﬁc. OSA Journal of Optical Networks 1(1), 32–42 (2002)

74. Huang, S., Dutta, R., Rouskas, G.: Trafﬁc grooming in path, star, and tree networks: Com-

plexity, bounds, and algorithms. IEEE Journal on Selected Areas in Communications 24(4),

66–82 (2006)

92 T. Cinkler et al.

75. Huiban, G., P

erennes, S., Syska, M.: Trafﬁc grooming in WDM networks with multi-layer

switches. In: IEEE International Conference on Communication (ICC), vol. 5, pp. 2896–

2901 (2002). DOI 10.1109/ICC.2002.997370

76. Architecture for the automatically switched optical network (ASON) (2006). URL

http://www.itu.int/rec/T-REC-G.8080/en

77. Jimenez, J., Gonzalez, O., Puype, B., Cinkler, T., Hegyi, P., Munoz, R., Martinez, R., Galan,

F., Morro, R.: Multilayer trafﬁc engineering experimental demonstrator in the Nobel-II

project. In: BroadBand Europe. Antwerpen, Belgium (2007)

78. Kern, A., Moldov

an, I., Hegyi, P., Cinkler, T.: Ethernet over WDM: Optimization for re-

silience and scalability. In: DRCN 2007, 6th International Workshop on the Design of Reli-

able Communication Networks. La Rochelle, France (2007)

79. Kern, A., Somogyi, G., Cinkler, T.: On the gain of statistical multiplexing over trafﬁc groom-

ing. In: ICTON 2006, 8th International Conference on Transparent Optical Networks. Not-

tingham, United Kingdom (2006)

80. Kodialam, M. S., Lakshman, T. V.: Integrated dynamic IP and wavelength routing in IP over

WDM networks. In: INFOCOM, pp. 358–366 (2001)

81. K

ohn, M.: A new efﬁcient online-optimization approach for SDH/SONET-WDM multi layer

networks. In: OFC. Anaheim/CA, USA (2006)

82. Koutsoupias, E., Papadimitriou, C. H.: Worst-case equilibria. In: 16th Annual Symposium

on Theoretical Aspects of Computer Science, pp. 404–413 (1999)

83. Lad

anyi, A., Cinkler, T., Hegyi, P., Szigeti, J.: SD-MLTE: State-dependent multi-layer trafﬁc

engineering. In: GMPLS WorkShop. Girona, Spain (2007)

84. Liu, L., Li, X., Wan, P. J., Frieder, O.: Wavelength assignment in a WDM rings to minimize

SONET ADMs. In: INFOCOM’2000, Nineteenth Annual Joint Conference of the IEEE

Computer and Communications Societies, Tel-Aviv, Israel, pp. 1020–1025 (2000)

85. Maliosz, M., Cinkler, T.: Methods for optical VPN design over multiﬁber wavelength rout-

ing networks. In: IFIP ONDM 7th Conference on Optical Network Design and Modelling.

Budapest, Hungary (2003)

86. Mannie (Ed.), E.: Generalized Multi-Protocol Label Switching (GMPLS) Architecture

(2004). URL http://www.ietf.org/rfc/rfc3945.txt

87. Megyer, B., Cinkler, T., Szombat:, Z.: Setting up oVPNs with trafﬁc grooming and protec-

tion. In: IFIP ONDM 2003, 7th Conference on Optical Network Design and Modelling.

Budapest, Hungary (2003)

88. Megyer, B., Zsigmond, S., Sz

enyi, A., Cinkler, T.: Design of trafﬁc grooming optical vpns

obeying physical limitations. In: IEEE IFIP WOCN 2005. Dubai, UAE, March (2005)

89. Modiano, E., Lin, P.: Trafﬁc grooming in WDM networks. IEEE Communications Magazine

39(7), 124–129 (2001)

90. Mu

noz, X., Sau, I.: Trafﬁc Grooming in Unidirectional WDM Rings with Bounded Degree

Request Graph. In: 34th International Workshop on Graph-Theoretic Concepts in Computer

Science (WG) (2008)

91. Nash, J. F.: Equilibrium points in n-person games. In: Proceedings of the National Academy

of Sciences, vol. 36, pp. 48–49 (1950)

92. Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.): Algorithmic Game Theory. Cam-

bridge University Press (2007)

93. Papadimitriou, D., Vigoureux, M., Shiomoto, K., Brungard, D., Roux, J. L. L.:

Generalized multi-protocol label switching (GMPLS) protocol extensions

for multi-layer and multi-region networks (MLN/MRN) (2008). URL

http://www.ietf.org/internet-drafts/draft-ietf-ccamp-gmpls-ml

n-extensions-03.txt

94. Per

enyi, M., Breuer, J., Cinkler, T., G

asp

ar, C.: Grooming node placement in multilayer

networks. In: 9th Conference on Optical Network Design and Modelling (ONDM). Milano,

Italy (2005)

95. Per

enyi, M., Cinkler, T.: Joint grooming capability and wavelength number optimization. In:

WTC 2006, World Telecommunications Congress. Budapest, Hungary (2006)

2 Trafﬁc Grooming: Combinatorial Results and Practical Resolutions 93

96. Per

enyi, M., Lad

anyi, A., Cinkler, T.: Joint grooming capability and wavelength number

optimization. In: IEEE ICTON 2005, 7th International Conference on Transparent Optical

Networks. Barcelona, Spain (2005)

97. Per

enyi, M., Soproni, P., Cinkler, T., Larrabeiti, D.: Regular reconﬁguration of light-trees in

multilayer optical networks. In: ONDM 2008, The 12th International Conference on Optical

Networking Design and Modeling. Vilanova i la Geltru, Catalonia, Spain (2008)

98. Rajagopalan, B., Luciani, J., Awduche, D.: IP over optical networks: A framework, RFC

3717 (2004). URL http://www.ietf.org/rfc/rfc3717.txt

99. R

etv

ari, G., Fodor, P., Tapolcai, J., Cinkler, T.: Challenges of multi-layer trafﬁc engineering

in gmpls networks. In: 7th IEEE International Conference on Transparent Optical Networks

(ICTON). Barcelona, Spain (2005)

100. Roughgarden, T.: Selﬁsh Routing and the Price of Anarchy. MIT Press (2005)

101. Shalom, M., Unger, W., Zaks, S.: On the complexity of the trafﬁc grooming problem in

optical networks. In: 4th International Conference on Fun With Algorithms, Castiglioncello

(LI), Tuscany, Italy (2007)

102. Shalom, M., Wong, P. W. H., Zaks, S.: Optimal on-line colorings for minimizing the number

of ADMs in optical networks. In: Proceedings of the 21st Distributed Algorithms (DISC),

pp. 435–449 (2007)

103. Shalom, M., Zaks, S.: A 10/7 +

approximation scheme for minimizing the number of

ADMs in SONET rings. In: First Annual International Conference on Broadband Networks,

San-Jos

e, California, USA, pp. 254–262 (2004)

104. Shiomoto, K., Papadimitriou, D., Roux, J. L. L., Vigoureux, M., Brungard:, D.: Require-

ments for GMPLS-based multi-region and multi-layer networks (MRN/MLN) (2008). URL

http://www.ietf.org/internet-drafts/draft-ietf-ccamp-gmpls-ml

n-reqs-11.txt

105. Solano, F., Caro, L., de Oliveira, J. C., Fabregat, R., Marzo, J. L.: G+: Enhanced trafﬁc

grooming in WDM mesh networks using lighttours. IEEE Journal on Selected Areas in

Communications 25(5), 1034–1047 (2007)

106. Somani, A.: Survivability and Trafﬁc Grooming in WDM Optical Networks. Cambridge

Press (2006)

107. Soproni, P., Per

enyi, M., Cinkler, T.: Grooming-enhanced multicast in multilayer networks.

In: Optical Network Design and Modeling, Lecture Notes in Computer Science, vol. 4534,

pp. 279–288. Springer, Athens, Greece (2007)

108. Su, D. H., Grifﬁth., D. W.: Standards activities for MPLS over WDM networks. Optical

Networks Magazine 1(3) (2000)

109. Szigeti, J., Tapolcai, J., Cinkler, T., Henk, T., Sallai, G.: Stalled information based routing in

multidomain multilayer networks. In: NETWORKS 2004, 11th International Telecommuni-

cation Network Planning Symposium. Vienna, Austria (2004)

110. Tapolcai, J., Cinkler, T.: Iterative multihop wavelength routing through decomposition. In:

9th International Telecommunication Network Planning Symposium (Networks). Toronto,

Canada (2000)

111. Vigoureux, M., Berde, B., Andersson, L., Cinkler, T., Levrau, L., Colle, D., Fdez-Palacios, J.,

Jaeger, M.: Multilayer trafﬁc engineering for GMPLS-enabled networks. Communications

Magazine 43(7), 44–50 (2005)

112. Wan, P. J., Calinescu, G., Liu, L., Frieder, O.: Grooming of arbitrary trafﬁc in SONET/WDM

BLSRs. IEEE Journal of Selected Areas in Communications 18(10), 1995–2003 (2000)

113. Wang, J., Cho, W., Vemuri, V. R., Mukherjee, B.: Improved approaches for cost-effective

trafﬁc grooming in WDM ring networks: ILP formulations and single-hop and multihop

connections. IEEE/OSA Journal of Lightwave Technology 19(11), 1645–1653 (2001)

114. Ye, Y., Woesner, H., Chlamtac, I.: Waveband switching in light trail optical networks with

dynamic trafﬁc. OSA Journal of Optical Networking (2006). DOI 10.1364/JON.5.000701

115. Zhang, X., Qiao, C.: An effective and comprehensive approach for trafﬁc grooming and

wavelength assignment in SONET/WDM rings. IEEE/ACM Transactions on Networking

8(5), 608–617 (2000)

94 T. Cinkler et al.

116. Zheng, J., Jue, J.: Waveband switching, routing, and grooming: introduction to the feature

issue. OSA Journal of Optical Networking 6(2), 217–218 (2007). DOI 10.1364/JON.6.

000217

117. Zhu, K., Mukherjee, B.: A review of trafﬁc grooming in WDM optical networks: Architec-

tures and challenges. Optical Networks Magazine 4(2), 55–64 (2003)

118. Zhu, K., Zhu, H., Mukherjee, B.: Trafﬁc Grooming in Optical WDM Mesh Networks.

Springer (2005)

119. Zsigmond, S., N

emeth, G., Cinkler, T.: Mutual impact of physical impairments and groom-

ing in multilayer networks. In: Optical Network Design and Modeling, Lecture Notes in

Computer Science, vol. 4534, pp. 279–288. Springer, Athens, Greece (2007)

120. Zsigmond, S., Sz

enyi, A., Megyer, B., Cinkler, T., Tzanakaki, A., Tomkos, I.: A new

method for considering physical impairments in multilayer routing. In: COST 291 - GBOU

ONNA. Gent, Belgium (2006)

Chapter 3

Branch-and-Cut Techniques for Solving

Realistic Two-Layer Network Design Problems

Sebastian Orlowski, Christian Raack, Arie M. C. A. Koster, Georg Baier, Thomas

Engel, and Pietro Belotti

Abstract We study a planning problem arising in SDH/WDM multilayer tele-

communication network design. The goal is to ﬁnd a minimum cost installation

of link and node hardware of both network layers such that trafﬁc demands can be

realized via grooming and a survivable routing. We present a mixed-integer pro-

gramming formulation for a predeﬁned set of admissible logical links that takes

many practical side constraints into account, including node hardware, several bit

rates, and survivability against single physical node or link failures. This model is

solved using a branch-and-cut approach with problem-speciﬁc preprocessing, MIP-

based heuristics, and cutting planes based on either of the two layers. On several

realistic two-layer planning scenarios, we show that these ingredients can be very

useful to reduce the optimality gaps in the multilayer context.

Key words: telecommunication networks, multilayer network design, preprocess-

ing, integer linear programming, cutting planes, MIP-based heuristics

Sebastian Orlowski

atesio GmbH, Sophie-Taeuber-Arp-Weg 27, D-12205 Berlin, Germany, e-mail:

orlowski@atesio.de

Christian Raack

Zuse Institute Berlin (ZIB), Takustr. 7, D-14195 Berlin, Germany, e-mail: raack@zib.de

Arie M. C. A. Koster

Lehrstuhl II f

ur Mathematik, RWTH Aachen University, W

ullnerstr. zwischen 5 und 7, D-52062

Aachen, Germany, e-mail: koster@math2.rwth-aachen.de

Georg Baier

Siemens AG, Munich, Germany, e-mail: georg.baier@siemens.com

Thomas Engel

Nokia Siemens Networks GmbH & Co. KG, Munich, Germany, e-mail:

thomas.1.engel@nsn.com

Pietro Belotti

Dept. of Industrial & Systems Engineering, Lehigh University, Bethlehem, PA, USA, e-mail:

belotti@lehigh.edu

A.M.C.A. Koster, X. Mu

noz (eds.), Graphs and Algorithms in Communication 95

Networks, Texts in Theoretical Computer Science. An EATCS Series,

DOI 10.1007/978-3-642-02250-0

 Springer-Verlag Berlin Heidelberg 2010

96 S. Orlowski et al.

3.1 Introduction

Planning a telecommunication network is a nontrivial task. For a single network

layer such as MPLS, SDH, or WDM, many mathematical models and algorithmic

approaches have been proposed during the last 15 years. Links in an SDH network,

for instance, may be equipped with a bandwidth of, say, 2.5 Gbit/s or 10 Gbit/s. This

bandwidth is used to route several communication demands of lower granularity,

like 155 Mbit/s. Dimensioning the links and routing the communication demands in

the resulting network is a classical network design problem.

A practical telecommunication network, however, consists of several network

layers which are embedded in each other. The bandwidth of an SDH link, for in-

stance, can actually be realized by a capacitated lightpath in an underlying optical

ﬁber network. The SDH and the WDM layer are highly interdependent: ﬁrst, only

a limited number of SDH links can traverse a given optical ﬁber, and second, the

failure of a single optical ﬁber can disrupt many SDH links, and even more demand

connections. In order to get a survivable network in practice, it is indispensible to

plan both layers together.

More generally, the two-layer network design problem considered in this paper

can be summarized as follows. Given is a set of network nodes together with po-

tential connections between them. This network is called the physical layer and

corresponds to the optical ﬁber network. On every ﬁber, a limited number of light-

path channels can be transmitted simultaneously, each of them corresponding to a

capacitated path in the physical network. The nodes together with the lightpath con-

nections form a so-called logical network on top of the physical one, as illustrated in

Figure 3.1. In principle, any path in the physical network can be used for a lightpath,

which leads to many parallel logical links. Even if the set of admissible lightpaths is

often restricted to several short paths between each node-pair in practice, the result-

ing logical network is still much denser than a simple complete graph, which makes

the network design problem hard to solve.

logical

physical

Fig. 3.1 Upper layer logical links (solid) correspond to paths (dashed) in the lower physical layer

Similar settings occur in many other technologies. An MPLS path, for example,

can consist of links which are MPLS paths themselves. In an ATM/SDH setting,

capacitated ATM links may be realized by an SDH radio link. Even if that radio

link seems “less physical” than an optical ﬁber, it is called a physical link as well

to indicate that it serves as part of a logical link. Similarly, the term “logical link”

illustrates the fact that it looks like a direct link to its end nodes: ﬁrst, it can be

equipped with a discrete capacity, and second, trafﬁc with lower granularity is sent