Automatic feedback of network topology data

• US 4,825,206 A
• Filed: 05/03/1988
• Issued: 04/25/1989
• Est. Priority Date: 11/04/1985
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Brice, Frank W. Jr., Weingarten, Robert A.
• Primary Examiner(s): Griffin, Robert L.
• Assistant Examiner(s): Smith, Ralph E.
• Application Number:
  US07/191,757
• Time in Patent Office: 357 Days
• Field of Search: 340/825.02, 340/825.03, 340/827, 370/54, 370/60, 370/89, 370/94, 370/95, 370/16
• US Class Current: 370/216
• CPC Class Codes: G06F 15/161 Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning casings, cabinets, racks or drawers for data centers H05K5/00
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G11C 29/006 at wafer scale level, i.e. wafer scale integration [WSI]
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

An automatic feedback mechanism in a communications network having dynamic routing. The invention detects the failure of an element in a route that is either in the process of being created or has been created and is being used. The invention provides a means for sending information as to the failure of the element back to the node originating the communication and, if the route had been established, to the destination node as well. The information sent back is used to update the network topology data base of the receiving node for subsequent route creation decisions by that node. In this way, proliferation of status messages in a communications network is avoided.

Claims

1. A digital data message transmission network, comprising:

(a) a plurality of network elements comprising message transmitting/receiving nodes and communication links interconnecting said nodes;

(b) means associated with each node for storing data corresponding to the availability of said network elements to communicate;

(c) means associated with each node for using said stored data to select a communication path made up of selected elements interconnecting that node with another node in said network;

(d) means for establishing said communication path between an origin node and a destination node;

(e) means, associated with said means for establishing said communication path, for storing data identifying all of said communication path if said communication path is completed, or if completion of the said communication path is prevented because of an unavailable element, the segment of said communication path between said origin node and the node adjacent the unavailable element; and

(f) means, responsive to the detection of the unavailability of an element in said communication path, for using data from said means for storing data identifying said path or path segment, as the case may be, to generate and selectively send data as to the unavailability of said unavailable element along the segment of said path between the node adjacent said unavailable element and said origin node.

2. A digital data message transmission network according to claim 1, wherein:

(a) said means for using said stored data to select a communication path comprises means for generating a ROUTE-SETUP message including information as to the communication originating node (the "origin node"), information as to the communication destination node (the "destination node"), information as to the identity of each element in said communication path, and a route identifier ("route ID");

(b) said means for establishing said communication path comprises

(i) means for sending said ROUTE-SETUP message to the first node in said route using the first link in the route, and

(ii) means at each node in said route for receiving said ROUTE-SETUP message, for creating a table in such node identifying the inbound and outbound links of such node for said route to permit the subsequent receipt of messages and transmission on the proper links for said route thereafter, and for sending said ROUTE-SETUP message to the next node in said route; and

(c) said means for using data from said means for storing data comprises

(i) means associated with each node for detecting the inoperative condition of the communication links connected thereto,

(ii) means for sending back to said origin node information as to the inoperative condition of a communication link connected thereto by way of the table entries set up by said ROUTE-SETUP message in the nodes intermediate the node detecting the inoperative condition and the origin node, and

(iii) means for detecting the operative condition of a previously inoperative communication link and for sending back to said origin node information as to the operative condition of said previously inoperative communication link by way of the table entries set up by said ROUTE-SETUP message in the nodes intermediate the node detecting the operative condition and the origin node.

3. A network according to claim 2 in which said means for sending back to said origin node information as to the inoperative condition of a communication link is responsive to the receipt of a ROUTE-SETUP message.

4. A network according to claim 2 in which said means for sending back to said origin node information as to the inoperative condition of a communication link is responsive to the detection of said inoperative condition.

5. A network as set forth in claim 1, wherein said means for storing data identifying said communication path, or said segment of said communication path, as the case may be, comprises a set of entries in tables in each node in said path or path segment identifying the nodes in said path or path segment.

6. A network as set forth in claim 1, wherein said means for using data from said means for storing further comprises means, responsive to the detection of the availability of said previously unavailable element, for using data from said means for storing data identifying said path or path segment, as the case may be, to generate and selectively send data as to the availability of said previously unavailable element, when said element becomes available, along the segment of said path between the node adjacent said previously unavailable element and said origin node.

7. A method for establishing a communication path between nodes in a digital message transmission network including a plurality of network elements comprising message transmitting/receiving nodes and communication links interconnecting said nodes, and for gathering data as to the availability of network elements to communication, comprising the steps of:

(a) storing data, corresponding to those network elements potentially available to communicate, in a storage element associated with each node that may attempt to establish a communication path;

(b) using said stored data to select a communication path made up of selected elements interconnecting an origin node originating a communication path with another node in said network;

(c) attempting to establish said communication path;

(d) storing data identifying all of said communication path, if said communication path is completed, or if said communication path is prevented because of an unavailable element in the segment of said communication path between said origin node and the node adjacent the unavailable element; and

(e) responsive to the detection of the unavailability of an element in said communication path, using data from said means for storing data identifying said path or path segment, as the case may be, to generate and selectively send data as to the unavailability of said unavailable element along the segment of said path between the node adjacent said unavailable element and said origin node.

8. A method for establishing a communication path between nodes in a digital data message transmission network including a plurality of network elements comprising message transmitting/receiving nodes and communication links interconnecting said nodes, and for gathering data as to the availability of network elements to communicate, comprising the step of:

(a) storing data, corresponding to those network elements potentially available to communicate, in a storage element associated with each node that may attempt to establish a communication path;

(b) selecting a communication path made up of selected elements interconnecting an origin node with a destination node based upon said stored data;

(c) attempting to establish said communication path by testing each of said selected elements to determine its availability for said communication path;

(d) storing data identifying completed segments of said communication path;

(e) responsive to the determination that an element in said communication path is unavailable, generating data indicating said element is unavailable and selectively sending said data along the completed segments of said communication path between the node adjacent said unavailable element and said origin node.

9. The method of claim 8 further comprising the steps of:

(f) periodically testing said unavailable element to determine its availability for said communication path;

(g) responsive to the determination that said element is available, generating data indicating said element is available and selectively sending said data along the completed segments of said communication path between said mode adjacent said element and said origin node.

10. The method of claim 9 further comprising the step of:

removing data identifying said completed segment of said communication path from storage after selectively sending said data along said segments.