Browse Prior Art Database

Method For Dynamic Distributed Generation Of Explicit Routes

IP.com Disclosure Number: IPCOM000048702D
Original Publication Date: 1982-Mar-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 5 page(s) / 28K

Publishing Venue

IBM

Related People

Bharath-Kumar, K: AUTHOR [+3]

Abstract

A method is presented for the dynamic distributed creation and deletion of explicit routes in a computer network. The properties of the routes created are optimized according to session type to use the routes.

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 32% of the total text.

Page 1 of 5

Method For Dynamic Distributed Generation Of Explicit Routes

A method is presented for the dynamic distributed creation and deletion of explicit routes in a computer network. The properties of the routes created are optimized according to session type to use the routes.

In explicit path routing, multiple end-to-end paths, called explicit routes (ERs), are defined between pairs of nodes in the network. This concept is introduced in
(1), and an implementation is presented in (2). Each route is identified by the triplet (origin node, destination node, explicit route number), and routing tables contained in the nodes are used to indicate the next node for each ER. Sessions are assigned to an ER at the origin node, and every message contains a header which specifies the ER to be traversed by the message.

In order to facilitate the process of failure notification to both ends of a session, the implementation of explicit routing presented in (2) imposes a "reversibility" condition on ERs. This condition stipulates that if (N(1)N(2),...,N(n- 1),N(n)) is a sequence of nodes comprising an ER from N(1) to N(n), the reverse sequence (N(n),N(n),...,N(2),N(1)) also must define an ER from N(n) to N(1).

The implementation of explicit routing presented in (2) involves statically defining the complete set of ERs (up to 8) between all node pairs along with the assignment of session types to ERs at system generation time. This is a cumbersome procedure and has the following additional drawbacks: (i) The entire set of ERs must be re-defined when a node or a link is added or deleted from the network. (ii) Since the ERs are defined at system generation time, they are insensitive to changing network conditions. (iii) A given failure may bring down all 8 ERs defined between twc nodes even though the nodes are not physically disconnected.

A method is presented here for dynamically generating reversible explicit routes in such a way as to maintain all of the basic advantages of explicit routes and also to eliminate the disadvantages. The method involves distributed execution among the nodes of the network and is suited to implementation in large networks.

Assume the network provides m Session Types 1,2,,...,m. Then associated with every link in the network at any given time are m non-negative numbers, called link weights, where each weight is a measure of the quality of the link with respect to a given Session Type. Denote by W.(see article) the weight of link (see article) with respect to Session Type i. Lower values of link weights indicate higher quality with respect to the respective Session Types.

We do not indicate here how the link weights are determined.

Associated with each path through the network at a given time are m non- negative numbers, called Path Weights, where each Path Weight is a measure of the quality of the path with respect to the respective Session Types. Denote by PW(i) (p) the weight of path p with respect to Session Type i. PW.(i)...