Approximating the traffic grooming problem. (English) Zbl 1160.90342
Summary: The problem of grooming is central in studies of optical networks. In graph-theoretic terms, this can be viewed as assigning colors to the lightpaths so that at most \(g\) of them (\(g\) being the grooming factor) can share one edge. The cost of a coloring is the number of optical switches (ADMs); each lightpath uses two ADMs, one at each endpoint, and in case \(g\) lightpaths of the same wavelength enter through the same edge to one node, they can all use the same ADM (thus saving \(g - 1\) ADMs). The goal is to minimize the total number of ADMs. This problem was shown to be NP-complete for \(g=1\) and for a general \(g\). Exact solutions are known for some specific cases, and approximation algorithms for certain topologies exist for \(g=1\). We present an approximation algorithm for this problem. For every value of \(g\) the running time of the algorithm is polynomial in the input size, and its approximation ratio for a wide variety of network topologies-including the ring topology-is shown to be 2\(\ln g+o(\ln g)\). This is the first approximation algorithm for the grooming problem with a general grooming factor \(g\).
MSC:
| 90B20 | Traffic problems in operations research |
| 90B80 | Discrete location and assignment |
| 90C35 | Programming involving graphs or networks |
Keywords:
wavelength assignment; wavelength division multiplexing (WDM); optical networks; add-drop multiplexer (ADM); traffic groomingReferences:
| [1] | J.-C. Bermond, L. Braud, D. Coudert, Traffic grooming on the path, in: 12th Colloquium on Structural Information and Communication Complexity, Le Mont Saint-Michel, France, May 2005, pp. 34-48; J.-C. Bermond, L. Braud, D. Coudert, Traffic grooming on the path, in: 12th Colloquium on Structural Information and Communication Complexity, Le Mont Saint-Michel, France, May 2005, pp. 34-48 · Zbl 1085.68503 |
| [2] | B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Perennes, U. Vaccaro, Graph problems arising from wavelength-routing in all-optical networks, INRIA, Research Report No: 3165, May 1997; B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Perennes, U. Vaccaro, Graph problems arising from wavelength-routing in all-optical networks, INRIA, Research Report No: 3165, May 1997 |
| [3] | J.-C. Bermond, D. Coudert, Traffic grooming in unidirectional WDM ring networks using design theory, in: IEEE ICC, Anchorage, Alaska, May 2003, pp. 1402-1406; J.-C. Bermond, D. Coudert, Traffic grooming in unidirectional WDM ring networks using design theory, in: IEEE ICC, Anchorage, Alaska, May 2003, pp. 1402-1406 |
| [4] | Brackett, C. A., Dense wavelength division multiplexing networks: principles and applications, IEEE Journal on Selected Areas in Communications, 8, 948-964 (1990) |
| [5] | Chvátal, V., A greedy heuristic for the set-covering problem, Mathematics of Operations Research, 4, 3, 233-235 (1979) · Zbl 0443.90066 |
| [6] | Chiu, A. L.; Modiano, E. H., Traffic grooming algorithms for reducing electronic multiplexing costs in wdm ring networks, Journal of Lightwave Technology, 18, 1, 2-12 (January 2000) |
| [7] | Chung, N. K.; Nosu, K.; Winzer, G., Special issue on dense wdm networks, IEEE Journal on Selected Areas in Communications, 8, 6, 1214-1215 (1990) |
| [8] | Dutta, R.; Rouskas, G. N., Traffic grooming in wdm networks: Past and future, IEEE Network, 16, 6, 46-56 (2002) |
| [9] | D.H.C. Du, R.J. Vetter, Distributed computing with high-speed optical networks, in: Proceeding of IEEE Computer, vol. 26, 1993, pp. 8-18; D.H.C. Du, R.J. Vetter, Distributed computing with high-speed optical networks, in: Proceeding of IEEE Computer, vol. 26, 1993, pp. 8-18 |
| [10] | 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 (January 2002) |
| [11] | Goldschmidt, O.; Hochbaum, D.; Levin, A.; Olinick, E., The SONET edge-partition problem, Networks, 41, 1, 13-23 (2003) · Zbl 1026.90076 |
| [12] | Green, P. E., Fiber-Optic Communication Networks (1992), Prentice Hall |
| [13] | Gerstel, O.; Ramaswami, R.; Sasaki, G., Cost effective traffic grooming in wdm rings, IEEE/ACM Transactions on Networking, 8, 5, 618-630 (2000) |
| [14] | Gargano, L.; Vaccaro, U., Routing in all-optical networks: Algorithmic and graph-theoretic problems, (Numbers, Information and Complexity (2000), Kluwer Academic) · Zbl 0980.05046 |
| [15] | Hinton, H. S., Architectural considerations for photonic switching networks, IEEE Journal on Selected Areas in Communications, 6, 1209-1226 (1988) |
| [16] | R. Klasing, Methods and problems of wavelength-routing in all-optical networks, in: Proceeding of the MFCS’98 Workshop on Communication, August 24-25, Brno, Czech Republic, 1998, pp. 1-9; R. Klasing, Methods and problems of wavelength-routing in all-optical networks, in: Proceeding of the MFCS’98 Workshop on Communication, August 24-25, Brno, Czech Republic, 1998, pp. 1-9 |
| [17] | Personik, S., Review of fundamentals of optical fiber systems, IEEE Journal on Selected Areas in Communications, 3, 373-380 (1983) |
| [18] | Ramaswami, R., Multi-wavelength lightwave networks for computer communication, IEEE Communications Magazine, 31, 78-88 (1993) |
| [19] | Shalom, M.; Unger, W.; Zaks, S., On the complexity of the traffic grooming problem in optical networks, (Fun with Algorithms, 4th International Conference, FUN 2007, Proceedings. Fun with Algorithms, 4th International Conference, FUN 2007, Proceedings, Castiglioncello, Italy, June 3-5, 2007. Fun with Algorithms, 4th International Conference, FUN 2007, Proceedings. Fun with Algorithms, 4th International Conference, FUN 2007, Proceedings, Castiglioncello, Italy, June 3-5, 2007, Lecture Notes in Computer Science, vol. 4475 (2007), Springer), 262-271 · Zbl 1201.68021 |
| [20] | Wan, P.-J.; Calinescu, G.; Liu, L.; Frieder, O., Grooming of arbitrary traffic in SONET/WDM BLSRs, Journal of Selected Areas in Communications, 18, 10, 1995-2003 (October 2000) |
| [21] | Zhu, K.; Mukherjee, B., A review of traffic grooming in wdm optical networks: Architecture and challenges, Optical Networks Magazine, 4, 2, 55-64 (March-April 2003) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
