System and method for determining the topology of a reconfigurable multi-nodal network

• US 5,732,086 A
• Filed: 09/21/1995
• Issued: 03/24/1998
• Est. Priority Date: 09/21/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tung, Roberta T., Liang, Song-Chyau S.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US08/531,724
• Time in Patent Office: 915 Days
• Field of Search: 370/410, 370/402, 370/403, 370/217, 370/221, 370/351, 395/200.01, 395/200.11, 395/200.12, 395/200.06, 395/200.2, 395/200.3, 395/200.15
• US Class Current: 370/410
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A multi-node network manifests a changing topology of individual data processing nodes. An originating node transmits an initial identifier (ID) message over each interconnect link that emanates from itself. A receiver in the originating node receives an acknowledgement (ACK) message from each neighbor node, each ACK message including a neighbor node'"'"'s link identifier for the link over which the ACK message was transmitted. The originating node constructs and stores a topology table entry which includes data from received ACK messages. Each entry includes a node identifier, an originating node link identifier and a neighbor node identifier from which an ACK message was received and a neighbor node link identifier for the link. An update procedure causes the transmitter to transmit to all other nodes, the originating node entry and further causes the topology table entries received from other nodes to be entered in the topology table of the originating node, so that all nodes in the system are enabled to thereafter identify the topology of the system.

Claims

1. A system manifesting a reconfigurable topology of individual data processing nodes, each node connectable to plural other nodes via full duplex interconnect links, a node directly connected to another node via a link hereafter referred to as a neighbor node, each node including processor means, memory and programming means for enabling discovery of said reconfigurable topology, an originating node further comprising:

transmitter means for transmitting an initial identifier message ID msg over each interconnect link emanating from said originating node, each ID msg including an originating node link identifier for the link over which said ID msg is transmitted;

receiver means for receiving an acknowledgement message ACK msg from each neighbor node, each ACK msg including a neighbor node link identifier for the link over which said ACK msg was transmitted to said originating node;

first logic means for constructing and storing in said memory, a topology table to include data from received ACK msgs, said topology table including an originating node entry, said originating node entry including an originating node identifier, an originating node link identifier associated with a neighbor node identifier from which an Ack msg is received, and a neighbor node link identifier for said link that is identified by said originating node link identifier; and

update means for causing said transmitter means to transmit to all other nodes, said originating node entry and for causing topology table entries received from other nodes to be entered in said topology table of said originating node, said originating node retransmitting a received topology table entry from another node to a further node only if said received topology table entry differs from a corresponding entry in the topology table of said originating node, whereby all nodes in said system are enabled to thereafter identify the topology of said system.

2. The system as recited in claim 1, further comprising:

means in said first logic means for providing a link timeout signal at an expiration of a first time interval, and for associating a null value in said topology table for any link over which no ACK msg is received prior to said link timeout signal.

3. The system as recited in claim 2, wherein said link timeout signal is issued upon expiration of a time period for said ACK msg to be received from a neighbor node in response to an ID msg.

4. The system as recited in claim 2, wherein each ACK msg includes a copy of at least a portion of said ID msg from said originating node to enable said originating node to determine over which link said ACK msg was received.

5. The system as recited in claim 1, wherein said update means is further responsive to an event in said system which causes a topology of nodes connected to links of said originating node to change, to cause ID msgs to be transmitted by said transmitter means and to cause retransmission of said originating node entry to all other nodes after making any changes to said originating node entry as a result of received ACK msgs, if any.

6. A method for enabling individual data processing nodes in a multi-node data processing system to derive and update a topology for said system, without requiring initial information regarding said topology, a node directly connected to another node via a communication link hereafter referred to as a neighbor node, each node including processor means, memory and programming means for enabling discovery of said topology, said method comprising:

transmitting an initial identifier message ID msg over each interconnect link emanating from an originating node, each ID msg including originating node link identifier for the link over which said ID msg is transmitted;

receiving an acknowledgement message ACK msg from each connected and operable neighbor node, each ACK msg including a neighbor node link identifier for the link over which said ACK msg was transmitted to said originating node;

constructing and storing in said memory, a topology table to include data from received ACK msgs, said topology table including an originating node entry and at least a neighbor node entry for each operable neighbor node from which an ACK msg is received, each entry including a node identifier, an originating node link identifier associated with a neighbor node identifier from which an Ack msg is received via said link that is identified by said originating node link identifier, and a neighbor node link identifier for said link that is identified by said originating node link identifier; and

transmitting to all other nodes, said originating node entry and causing topology table entries received from other nodes to be entered in said topology table of said originating node, said originating node retransmitting a received topology table entry from another node to a further node only if said received topology table entry differs from a corresponding entry in the topology table of said originating node, whereby nodes in said system are enabled to thereafter identify the topology of said system.

7. The method as recited in claim 6, further comprising the steps of:

providing a link timeout signal at an expiration of a first time interval; and

associating a null value in said topology table for any link over which no ACK msg is received prior to said link timeout signal.

8. The method as recited in claim 7, wherein said link timeout signal is provided upon expiration of a time period for an ACK msg to be received from a neighbor node in response to an ID msg.

9. The method as recited in claim 7, wherein each ACK msg includes a copy of at least a portion of said ID msg from said originating node to enable said originating node to determine over which link said ACK msg was received.

10. The method as recited in claim 6, comprising the further steps of:

responding to an event in said system which causes a topology of nodes connected to links of said originating node to change, by causing ID msgs to again be transmitted; and

retransmitting said originating node entry to all other nodes after making any changes to said originating node entry as a result of received ACK msgs, if any.