Abstract
We investigate the problem of multicast routing and wavelength assignment under the multi-drop path model (MRWA-MP). In a multi-drop path model, multiple paths are employed to establish a multicast session and each path can drop signals at no more than a predefined number of destination nodes. Given a network topology and a multicast session, the MRWA-MP problem is to minimize the number of wavelengths used to establish the multicast session and, as an auxiliary objective, minimize the number of fibers used. We derive bounds for both objectives. The lower bound on the number of wavelengths derived is tighter and thus more accurate than that in recent papers. To gain an insight into the complexity of the MRWA-MP problem, we formulate it as a mixed integer linear programming (MILP) problem and solve it using CPLEX integer optimizer. Our experience indicates that this problem can easily overwhelm even a state-of-the-art computing facility. To solve the MRWA-MP problem efficiently, we develop a heuristic, MFBH, based on the Edmonds-Karp maximum flow algorithm. Through experiments, we show that the MFBH heuristic achieves the lower bound on the number of wavelengths in almost all instances of the real-life and randomly generated networks that we tested. Furthermore, MFBH tends to use fewer fibers when the maximum number of drops allowed on a single path decreases, the number of destination nodes in a multicast session increases, or the connectivity of the network decreases.
Original language | English (US) |
---|---|
Pages (from-to) | 113-134 |
Number of pages | 22 |
Journal | Information Sciences |
Volume | 149 |
Issue number | 1-3 |
DOIs | |
State | Published - Jan 2003 |
Keywords
- Maximum flow
- Multi-drop path model
- Multicast
- Routing
- Wavelength assignment
ASJC Scopus subject areas
- Theoretical Computer Science
- Software
- Control and Systems Engineering
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence