A heuristic to generate all best partially disjoint paths in a communications network

Author

Kist, Alexander A. ; Harris, Richard J.

Author_Institution

Univ. of Melbourne, Vic., Australia

Volume

1

fYear

2002

fDate

25-28 Nov. 2002

Firstpage

357

Abstract

This paper considers a directed graph G(N, A) with n nodes, m directed arcs and a cost value for each arc. The synthesis of a partially link disjoint pair of paths for a given OD-pair with the minimum total cost is investigated. An algorithm is presented that solves the all-best partially disjoint path problem. The expected worst case running time of the algorithm is O(n³). Possible applications include light path design and MPLS based traffic engineering. Partially disjoint path algorithms can also be used as intelligent alternatives to k-th shortest path algorithms.

Keywords

directed graphs; telecommunication network routing; telecommunication traffic; best partially disjoint paths; communications network; cost value; directed arcs; directed graph; heuristic; minimum total cost; partially link disjoint pair; traffic engineering; worst case running time; Algorithm design and analysis; Australia; Communication networks; Costs; Design engineering; Intelligent networks; Multiprotocol label switching; Network synthesis; Network topology; Telecommunication traffic;

fLanguage

English

Publisher

ieee

Conference_Titel

Communication Systems, 2002. ICCS 2002. The 8th International Conference on

Print_ISBN

0-7803-7510-6

Type

conf

DOI

10.1109/ICCS.2002.1182497

Filename

1182497