MPATH: A Loop-free Multipath Routing Algorithm

reportActive / Technical Report | Accession Number: ADA457391 | Open PDF

Abstract:

We present a distributed routing algorithm for computing multiple paths between each source-destination pair in a computer network, such that the paths are loop-free at all times and are not necessarily of equal length. In this algorithm, routers exchange second-to-last hop on the shortest path to destinations in addition to shortest distances, which are used to prevent the well-know count-to-infinity problem. The safety and liveness properties of the algorithm are proved and its performance is analyzed.

Author(s):
Vutukury, Srinivas ; Garcia-luna-aceves, J. J.
Author Organization(s):
CALIFORNIA UNIV SANTA CRUZ DEPT OF COMPUTER ENGINEERING
Descriptive Note:
Journal article
Supplementary Note:
Published in Microprocessors and Microsystems, v24 n6 p319-327, 15 Oct 2000.
Pagination:
0007

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release
Distribution Statement:
Approved For Public Release; Distribution Is Unlimited. This Document Is Not Available From Dtic In Microfiche.

RECORD

Collection: TR
Identifying Numbers
Contract/Grant Number(s):
F30602-97-1-0291, F19628-96-C-0038
Monitor Series:
DARPA
 Subject Terms
Joint Capability Areas:
JCA_6.1.3_Switching and Routing; JCA_6_Net Centric; JCA_6.1_Information Transport; JCA_5_Command and Control; JCA_5.2.3_Share Knowledge and Situational Awareness; JCA_5.2_Understand; JCA_1.2.5_Lessons Learned; JCA_1.2_Force Preparation; JCA_1_Force Support; JCA_8_Building Partnerships
Communities of Interest:
Materials and Manufacturing Processes
Descriptor(s):
*ALGORITHMS, *ROUTING, *MULTIPATH TRANSMISSION, COMPUTER NETWORKS, NETWORK TOPOLOGY
Field(s)/Group(s):
Computer Systems, Computer Systems Management and Standards
Keyword(s):
PATH FINDING ALGORITHMS, SCALABILITY, SHORTEST PATH ALGORITHMS, LOOP FREE
Report Date:
2000 Oct 01
Creation Date:
2006 Dec 06