Successive survivable routing for node failures

Author

Liu, Yu ; Tipper, David

Author_Institution

OPNET Technol. Inc., Cary, NC, USA

Volume

4

fYear

2001

fDate

6/23/1905 12:00:00 AM

Firstpage

2093

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Global Telecommunications Conference, 2001. GLOBECOM '01. IEEE

Print_ISBN

0-7803-7206-9

Type

conf

DOI

10.1109/GLOCOM.2001.966150

Filename

966150