Title :
Successive survivable routing for node failures
Author :
Liu, Yu ; Tipper, David
Author_Institution :
OPNET Technol. Inc., Cary, NC, USA
fDate :
6/23/1905 12:00:00 AM
Abstract :
This paper addresses the spare capacity allocation (SCA) problem considering any single node failure in mesh networks. The SCA node failure problem aims at finding backup routes and providing sufficient spare capacity to protect traffic when any single node fails in a communication network. Here, we introduce our novel matrix formulation of the arc-flow SCA node failure model. In this model, working paths are given before pre-planned backup paths are routed and reserved. Because backup paths can not be guaranteed if general shortest path routing of working paths is used, we give a graph algorithm to find the working path which has at least one node-disjoint backup path. We extend our recent approximation algorithm, successive survivable routing (SSR), to solve the above SCA model. Numerical comparison shows that SSR has the best trade-off between solution optimality and computation speed
Keywords :
directed graphs; optimisation; telecommunication network planning; telecommunication network reliability; telecommunication network routing; SCA problem; arc-flow node failure model; backup routes; communication network; computation speed; graph algorithm; matrix formulation; mesh networks; network planning; network survivability; node failures; node-disjoint backup path; optimality; optimization; spare capacity allocation problem; successive survivable routing; Approximation algorithms; Capacity planning; Communication networks; Costs; Information science; Mesh networks; Protection; Routing; Telecommunication traffic; Traffic control;
Conference_Titel :
Global Telecommunications Conference, 2001. GLOBECOM '01. IEEE
Print_ISBN :
0-7803-7206-9
DOI :
10.1109/GLOCOM.2001.966150
