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

Eiji OKI  Naoaki YAMANAKA  

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

Full Text: PDF(411.8KB)>>
Buy this Article




Summary: 
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.