A Recursive Matrix-Calculation Method for Disjoint Path Search with Hop Link Number Constraints

Eiji OKI

IEICE TRANSACTIONS on Communications   Vol.E78-B    No.5    pp.769-774
Publication Date: 1995/05/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Communication Networks and Service
disjoint path,  reliability,  matrix calculation,  network design,  

Full Text: PDF>>
Buy this Article

A new approximation calculation method, named the Recursive Matrix-calculation (RM) method, is proposed. It uses matrix calculation to determine the number of link disjoint paths under a hop link number constraint, i.e. hop limit. The RM method does not overestimate the number of link disjoint paths. When networks are designed by this method, network reliability is perfectly guaranteed. Moreover, the RM method is based on matrix calculation, so CPU time can be reduced by using super-computers equipped with vector processors. Simulation results confirm that the RM method yields rapid approximations that are conservative. Thus the proposed method is very useful for designing reliable multimedia networks.