Multi-drop path model for multicast routing and wavelength assignment

Shuguang Yan, Jitender Deogun

Research output: Contribution to journalArticle

3 Scopus citations

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 languageEnglish (US)
Pages (from-to)113-134
Number of pages22
JournalInformation Sciences
Volume149
Issue number1-3
DOIs
StatePublished - Jan 2003

Keywords

  • Maximum flow
  • Multi-drop path model
  • Multicast
  • Routing
  • Wavelength assignment

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Multi-drop path model for multicast routing and wavelength assignment'. Together they form a unique fingerprint.

  • Cite this