Optimal wavelength-routed multicasting

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 are (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. (C) 1998 Elsevier Science B.V. All rights reserved.