FastSurv: a new efficient local search algorithm for survivable routing in WDM networks
Published 5 April 2005
Frederick Ducatelle, Luca Maria Gambardella
Citations11
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents FastSurv, a local search algorithm for survivable routing, which works in an iterated way: after each iteration it learns more about the structure of the logical graph and in the next iteration it uses this information to improve its solution.
Abstract
In IP-over-WDM networks, a logical IP network has to be routed on top of a physical optical fiber network. An important challenge is to make this routing survivable. We call a routing survivable if no single physical link failure can disconnect the logical topology. In this paper we present FastSurv, a local search algorithm for survivable routing. FastSurv works in an iterated way: after each iteration it learns more about the structure of the logical graph and in the next iteration it uses this information to improve its solution. We also extend the algorithm to take link capacity constraints into account. We show that our simple algorithm can produce better and faster results than current state-of-the-art algorithms.
Keywords
Computer ScienceEngineering
A Review of Routing and Wavelength Assignment Approaches for Wavelength- Routed Optical WDM Networks
1,593 Citations2000Hui Zang, Jason P. Jue +1 more
A new wavelengthassignment scheme is proposed, called Distributed Relative Capacity Loss (DRCL), which works well in distributed-controlled networks, and the performance of DRCL is demonstrated through simulation.
Encyclopedia of Wireless and Mobile CommunicationsOptical Communication Networks
792 Citations2007N.K. Singhal, A. Gencata +1 more
A comprehensive explanation of the newest developments in optical networks in the MCGRAW-HILL COMPUTER COMMUNICATIONS series.
IEEE Journal on Selected Areas in CommunicationsFault management in IP-over-WDM networks: WDM protection versus IP restoration
233 Citations2002L.H. Sahasrabuddhe, S. Ramamurthy +1 more
This paper considers an IP-over-WDM network in which network nodes employ optical crossconnects and IP routers, and formulate fault-management problems mathematically, develop heuristics to find efficient solutions in typical networks, and analyze their characteristics relative to each other.
IEEE Journal on Selected Areas in CommunicationsSurvivable lightpath routing: a new approach to the design of WDM-based networks
219 Citations2002Eytan Modiano, Aradhana Narula‐Tam
This work proves necessary and sufficient conditions for a routing to be survivable and develops algorithms for survivable routing of a logical topology and establishes conditions on the physical topology for routing logical rings in a survivable manner.
IEEE Journal on Selected Areas in CommunicationsDesign protection for WDM optical networks
150 Citations1998O. Crochat, J.-Y. Le Boudec
This work presents the disjoint alternate path (DAP) algorithm which places optical channels in order to maximize design protection and shows the result on various network examples.
Choice Reviews OnlineWiley encyclopedia of telecommunications
137 Citations2003
Engineers have long required a comprehensive yet concise resource to turn to for reliable, up-to-date information on the continually evolving field of telecommunications.
Survivable routing of logical topologies in WDM networks
130 Citations2002Eytan Modiano, Aradhana Narula‐Tam
This work proves necessary and sufficient conditions for a routing to be survivable and develops algorithms for survivable routing of a logical topology and uses this new formulation to route various logical topologies over a number of different physical topologies.
IEEE/ACM Transactions on NetworkingProtection interoperability for WDM optical networks
98 Citations2000O. Crochat, J.-Y. Le Boudec +1 more
This work analyzes three types of failure propagation, called "bottleneck," "connectivity," and "multiple groups," and presents a solution based on the definition of appropriate requirements at network design and a WDM channel placement algorithm, protection interoperability for WDM (PIW).
Design of a survivable WDM photonic network
71 Citations2002J.R. Armitage, O. Crochat +1 more
This work presents the disjoint alternate path (DAP) algorithm which places optical channels in order to maximise design protection, and shows the result on the example of the ARPA-2 network.
Survivable routing in WDM networks - logical ring in arbitrary physical topology
31 Citations2003Arunabha Sen, Bin Hao +2 more
This work establishes the necessary and sufficient condition for a ring logical topology to withstand failure of a single physical link and shows that the testing of this necessary andsufficient condition is an NP-complete problem.
Design of fault-tolerant logical topologies in wavelength-routed optical IP networks
20 Citations2002A. Nucci, Brunilde Sansò +3 more
An approach to protection and restoration generalizes the "design protection" concepts, and relies on the dynamic capabilities of IP routing to re-route IP datagrams when faults occur, thus leading to high-performance cost-effective fault-tolerant logical topologies.
Electronics and Communications in Japan (Part I Communications)Number of wavelengths required for constructing large‐scale optical path networks
19 Citations1995Naohide Nagatsu, Y. Hamazumi +1 more
It is elucidate, for the first time, that the wavelength requirements for the WP and VWP schemes are almost the same regardless of physical network topologies and path demand distribution patterns.