Browse Prior Art Database

Experimental multiple-path routing algorithm (RFC0981)

IP.com Disclosure Number: IPCOM000004979D
Original Publication Date: 1986-Mar-01
Included in the Prior Art Database: 2001-Jul-13
Document File: 23 page(s) / 58K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

D.L. Mills: AUTHOR

Abstract

This document introduces wiretap algorithms, which are a class of routing algorithms that compute quasi-optimum routes for stations sharing a broadcast channel, but with some stations hidden from others. The wiretapper observes the paths (source routes) used by other stations sending traffic on the channel and, using a heuristic set of factors and weights, constructs speculative paths for its own traffic. A prototype algorithm, called here the Wiretap Algorithm, has been designed for the AX.25 packet-radio channel. Its design is similar in many respects to the shortest-path-first (spf) algorithm used in the ARPANET and elsewhere, and is in fact a variation in the class of algorithms, including the Viterbi Algorithm, that construct optimum paths on a graph according to a distance computed as a weighted sum of factors assigned to the nodes and edges.

This text was extracted from a ASCII Text document.
This is the abbreviated version, containing approximately 7% of the total text.

Network Working Group D. L. Mills Request for Comments: 981 M/A-COM Linkabit

March 1986

An Experimental Multiple-Path Routing Algorithm

Status of This Memo

This RFC describes an experimental, multiple-path routing algorithm designed for a packet-radio broadcast channel and discusses the design and testing of a prototype implementation. It is presented as an example of a class of routing algorithms and data-base management techniques that may find wider application in the Internet community. Of particular interest may be the mechanisms to compute, select and rank a potentially large number of speculative routes with respect to the limited cumputational resources available. Discussion and suggestions for improvements are welcomed. Distribution of this memo is unlimited.

Abstract

This document introduces wiretap algorithms, which are a class of routing algorithms that compute quasi-optimum routes for stations sharing a broadcast channel, but with some stations hidden from others. The wiretapper observes the paths (source routes) used by other stations sending traffic on the channel and, using a heuristic set of factors and weights, constructs speculative paths for its own traffic. A prototype algorithm, called here the Wiretap Algorithm, has been designed for the AX.25 packet-radio channel. Its design is similar in many respects to the shortest-path-first (spf) algorithm used in the ARPANET and elsewhere, and is in fact a variation in the class of algorithms, including the Viterbi Algorithm, that construct optimum paths on a graph according to a distance computed as a weighted sum of factors assigned to the nodes and edges.

The Wiretap Algorithm differs from conventional algorithms in that it computes not only the primary route (a minimum-distance path), but also additional paths ordered by distance, which serve as alternate routes should the primary route fail. This feature is also useful for the discovery of new paths not previously observed on the channel.

Since the amateur AX.25 packet-radio channel is very active in the Washington, DC, area and carries a good deal of traffic under punishing conditions, it was considered a sufficiently heroic environment for a convincing demonstration of the prototype algorithm. It was implemented as part of an IP/TCP driver for the LSI-11 processor running the "fuzzball" operating system. The driver is connected via serial line to a 6809-based TAPR-1 processor running the WA8DED firmware, which controls the radio equipmnet in both

Mills [Page 1]

RFC 981 March 1986 An Experimental Multiple-Path Routing Algorithm

virtual-circuit and datagram modes. The prototype implementation provides primary and alternate routes, can route around congested areas and can change routes during a connection. This document describes the design, implementation and initial testing of the algorithm.

1. Introduction

This document describes the design, implementation and initial testing of the Wiretap Algorithm, a dynamic routing algorithm for the AX...