×

Optimal wavelength-routed multicasting. (English) Zbl 0908.90122

Summary: Motivated by wavelength division multiplexing in all-optical networks, we consider the problem of finding a set of paths from a fixed source to a multiset of destinations, which can be coloured by the fewest number of colours so that paths of the same colour do not share an arc. We prove that this minimum number of colours (wavelengths) is equal to the maximum number of paths that share one arc (the load), minimized over all sets of paths from the source to the destinations. We do this by modeling the problems as network flows in two different networks and relating the structure of their minimum cuts. The problem can be efficiently solved (paths found and coloured) using network flow techniques.

MSC:

90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Beauquier, B., All-to-all communication for some wavelength-routed all-optical networks, (Technical report (1998), INRIA), Submitted to Networks · Zbl 0940.90018
[2] Beauquier, B.; Bermond, J.-C.; Gargano, L.; Hell, P.; Pérennes, S.; Vaccaro, U., Graph problems arising from wavelength-routing in all-optical networks, (Proc. 2nd Workshop on Optics and Computer Science. Proc. 2nd Workshop on Optics and Computer Science, Geneva (April 1997))
[3] Bermond, J.-C.; Gargano, L.; Pérennes, S.; Rescigno, A. A.; Vaccaro, U., Efficient collective communication in optical networks, (Lecture Notes in Computer Science, vol. 1099 (1996), Springer: Springer Berlin), 574-585 · Zbl 1045.90502
[4] Cheung, N. K.; Nosu, K.; Winzer, G., Special issue on dense WDM networks, J. Selected Areas Commun., 8 (1990)
[5] Ford, L. R.; Fulkerson, D. R., Maximal flow through a network, Can. J. Math., 8, 3, 399-404 (1956) · Zbl 0073.40203
[6] Frank, A., Connectivity and Network Flows, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics, vol. 1 (1995), Elsevier: Elsevier Amsterdam), 111-177 · Zbl 0846.05055
[7] L. Gargano, P. Hell, S. Pérennes, Colouring paths in directed symmetric trees with applications to WDM routing, in: Proc. ICALP, 1997. Extended version submitted to J. Graph Theory.; L. Gargano, P. Hell, S. Pérennes, Colouring paths in directed symmetric trees with applications to WDM routing, in: Proc. ICALP, 1997. Extended version submitted to J. Graph Theory. · Zbl 1401.68245
[8] Green, P. E., Fiber-Optic Communication Networks (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[9] Heydemann, M.-C.; Meyer, J.-C.; Sotteau, D., On forwarding indices of networks, Discrete Appl. Math., 23, 103-123 (1989) · Zbl 0681.90077
[10] Minoli, D., (Telecommunications Technology Handbook (1991), Artech House)
[11] Mukherjee, B., WDM-based local lightwave networks, Part 1: Single-hop systems, IEEE Network Mag., 6, 3, 12-27 (1992)
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.