Browse Prior Art Database

Explicit Path Routing for Switching Network

IP.com Disclosure Number: IPCOM000085126D
Original Publication Date: 1976-Feb-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 4 page(s) / 42K

Publishing Venue

IBM

Related People

Jueneman, RR: AUTHOR [+2]

Abstract

A method is described whereby individual messages in a store and forward or packet switching network can be routed over an explicitly determined path, from an origination node or message concentrator to a destination node. By using an appropriate path selection scheme at the origin node many variations of alternate and parallel paths are possible.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 4

Explicit Path Routing for Switching Network

A method is described whereby individual messages in a store and forward or packet switching network can be routed over an explicitly determined path, from an origination node or message concentrator to a destination node. By using an appropriate path selection scheme at the origin node many variations of alternate and parallel paths are possible.

The algorithm provides most of the virtues of a stochastic, adaptive (e.g., Advanced Research Project (ARPA)-like) routing algorithm while permitting very simple alternate path schemes, which usually preserve the first-in first-out (FIFO) arrival of messages without precluding recovery from path outage conditions.

The method described involves a message header, which contains at least the identification number of the destination node (and the origin node, for use in the event of an error), plus two routing fields. The first of these will be called the Path Indicator (PIN), which will be set once at the origin node to indicate the original path choice. The second field, called the Next Node Index (NNI), is used to steer the table look-up routing algorithm, and is updated at each node along the path.

In each node there exists a set of precomputer, static routing tables, one for every destination node in the network. In operation, the Destination Node Number (DNN) is extracted from the message header and used to select the set of explicit path routing tables associated with that DNN. The NNI is then used to select the particular next link/station to which the message should be routed next, along with an updated NNI value for use at that next node. The algorithm thus routes the message to and through the next node, until it arrives at the destination node.

Thus the routing is accomplished by a very simple table look-up operation, probably requiring fewer than a dozen instructions.

In the event that a message can not be delivered to the destination via the indicated path due to some link or node failure, that fact must be reported to the originating node so that the path can be marked as unavailable. Some form of a LOST PATH message must be sent, which must include at least the Origin Node Number (ONN), the DNN, and the PIN. Usually it would be convenient to include the entire message header of the message which could not be delivered.

It is necessary to construct the tables on a global basis, in order to insure the consistency of all of the paths and tables.

The construction algorithm begins by generating a tree of all possible nonlooping paths rooted at a particular node. Based on a connectivity matrix, a path from the root node is extended by catenating all nodes that connect to the last node in the path, but excluding any nodes already in the path. If multiple nodes can connect to the last node, then the path branches and a new path identification (ID) is assigned to the new leg.

1

Page 2 of 4

At the end of each expansion loop, each path in the...