Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

An efficient heuristic for calculating a protected path with specified nodes

Martins, L and Gomes, T and Tipper, D (2016) An efficient heuristic for calculating a protected path with specified nodes. Proceedings of 2016 8th International Workshop on Resilient Networks Design and Modeling, RNDM 2016. 150 - 157.

[img]
Preview
PDF
Available under License : See the attached license file.

Download (642kB) | Preview
[img] Plain Text (licence)
Available under License : See the attached license file.

Download (1kB)

Abstract

The problem of determining a path between two nodes in a network that must visit specific intermediate nodes arises in a number of contexts. For example, one might require traffic to visit nodes where it can be monitored by deep packet inspection for security reasons. In this paper a new recursive heuristic is proposed for finding the shortest loopless path, from a source node to a target node, that visits a specified set of nodes in a network. In order to provide survivability to failures along the path, the proposed heuristic is modified to ensure that the calculated path can be protected by a node-disjoint backup path. The performance of the heuristic, calculating a path with and without protection, is evaluated by comparing with an integer linear programming (ILP) formulation for each of the considered problems. The ILP solver may fail to obtain a solution in a reasonable amount of time, especially in large networks, which justifies the need for effective, computationally efficient heuristics for solving these problems. Our numerical results are also compared with previous heuristics in the literature.


Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: Article
Status: Published
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Martins, L
Gomes, T
Tipper, Ddtipper@pitt.eduDTIPPER0000-0002-9429-6425
Date: 21 October 2016
Date Type: Publication
Journal or Publication Title: Proceedings of 2016 8th International Workshop on Resilient Networks Design and Modeling, RNDM 2016
Page Range: 150 - 157
Event Type: Conference
DOI or Unique Handle: 10.1109/rndm.2016.7608281
Schools and Programs: School of Information Sciences > Telecommunications
Refereed: Yes
ISBN: 9781467390231
Date Deposited: 30 Jun 2017 15:05
Last Modified: 30 Mar 2021 10:55
URI: http://d-scholarship.pitt.edu/id/eprint/32581

Metrics

Monthly Views for the past 3 years

Plum Analytics

Altmetric.com


Actions (login required)

View Item View Item