System and method for self-identifying and configuring the nodes of a network

• US 6,188,675 B1
• Filed: 08/23/1996
• Issued: 02/13/2001
• Est. Priority Date: 08/23/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Perkins, Charles Bertram Jr., Gregg, Thomas Anthony, Ocheltree, Kenneth Blair, Casper, Daniel Francis, Nation, George Wayne
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US08/702,778
• Time in Patent Office: 1,635 Days
• Field of Search: 370/254-258, 370/238, 370/351, 370/389, 370/400, 370/401, 370/453, 370/475
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A system and method for progressively identifying and configuring the nodes of a network having an unknown or partially unknown topology are presented. A special all-node address indicator is designated for insertion in a packet to be sent from a given node with known node address to a next adjacent node with unknown node address. Each node contains a port control register for each port of the node which when set instructs the node to insert the all-node address indicator into a packet to be forwarded to a next adjacent node in the network with unknown node address. The port control registers are remotely selectively set by one or more managing nodes of the network. Race condition is avoided by provision of a set count register associated with an address node register and managing node address register within each node of the network. A node can be configured only if the previously read set count value remains unchanged between reading of and writing to the address node register or managing node address register. Provision for identifying additions, deletions and other changes to the network automatically is also provided.

Claims

1. A system for use in identifying the topology of a network having a plurality of nodes, each node having a port for transfer of a packet to a next adjacent node in the network, said system comprising:

an all-node address indicator for selective insertion in a field of the packet according to whether a node address of the next adjacent node is known, wherein when inserted in the field of the packet, said all-node address indicator causes the packet to be received by the next adjacent node in the network notwithstanding that said node address of the next adjacent node in the network is unknown when forwarding the packet;

means for selectively inserting the all-node address indicator into said field of said packet at each node in the network with a known node address when said node with a known address has a next adjacent node in the network with an unknown node address to address and thereby identify said next adjacent node; and

wherein said means for selectively inserting comprises means for not inserting the all-node address indicator when said node with a known address has a next adjacent node with a known address.

2. The system of claim 1, wherein said means for selectively inserting comprises means for progressing stepwise through the network to identify each node of said plurality of nodes.

3. The system of claim 1, wherein at least one node of said plurality of nodes comprises a managing node, and wherein said means for selectively inserting comprises control means disposed at said managing node for remotely employing the all-node address indicator to identify in stepwise progression each next adjacent node in the network with unknown node address connected to a node in the network with known node address.

4. The system of claim 1, wherein the all-node address indicator for selective insertion in the field of the packet comprises a universal indicator for selective insertion in either the destination address field of the packet or the routing field of the packet.

5. The system of claim 1, wherein said plurality of nodes includes multiple switch nodes, each switch node having multiple ports, each port having a different next adjacent node connected thereto, and wherein said means for selectively employing comprises means for selectively inserting the all-node address indicator at each port of each switch node with known node address having a next adjacent node in the network connected thereto with an unknown node address.

6. The system of claim 1, wherein the network comprises an interconnection network within a computer system, and wherein said plurality of nodes comprises a managing node, multiple switch nodes, and multiple end nodes, said managing node comprising a processor node, and said multiple end nodes comprising storage and communication device connection nodes.

7. A system for use in identifying the topology of a network having a plurality of interconnected nodes, each node having a port for transfer of a packet to a next adjacent node in the network, said system comprising:

an all-node address indicator for selective insertion in a field of the packet according to whether a node address of the next adjacent node is known, wherein when inserted in the field, the all-node address indicator causes the packet to be received by the next adjacent node in the network;

each node having a port control register associated with said port which when set instructs the node to insert the all-node address indicator into the field of the packet before forwarding the packet to the next adjacent node in the network wherein said port control register is set when the next adjacent node has an unknown address;

means for remotely, selectively setting the port control registers associated with the ports of the plurality of interconnected nodes, wherein said all-node address indicator causes the packet to be received by the next adjacent node in the network notwithstanding that said node address of the next adjacent node in the network is unknown when forwarding the packet; and

wherein said port control register is not set when the next adjacent node has a known address.

8. The system of claim 7, wherein said all-node address indicator comprises a universal destination address and said field comprises a destination address field in the packet.

9. The system of claim 7, wherein at least some nodes of said plurality of interconnected nodes comprise switch nodes, each switch node having at least two ports, and wherein each node of said plurality of interconnected nodes includes a node address register, and said packet comprises a request packet for reading a node address stored in the node address register of the next adjacent node in the network with unknown node address.

10. The system of claim 7, wherein at least some nodes of said plurality of interconnected nodes comprise switch nodes, each switch node having multiple ports, each port having a port control register associated therewith, and wherein said means for remotely, selectively setting the port control registers comprises means for remotely, selectively setting each port control register associated with the multiple ports of each switch node with known node address having a next adjacent node in the network connected thereto with an unknown node address.

11. The system of claim 7, wherein at least one node of said plurality of interconnected nodes comprises a managing node, said means for remotely, selectively setting the port control registers including control means disposed at the managing node for progressively identifying each node of the network.

12. The system of claim 11, wherein the plurality of interconnected nodes of the network further comprises multiple switch nodes, each switch node having a managing node address register associated therewith, and said system further comprises means for reading and configuring the managing node address register of each switch node of the multiple switch nodes in the network from the managing node.

13. The system of claim 7, wherein the plurality of interconnected nodes includes multiple managing nodes, at least two managing nodes containing control means for progressively identifying each node of the network employing said means for remotely, selectively setting the port control registers, and said system further comprises means for avoiding race condition between said at least two managing nodes in identifying the topology of said network.

14. The system of claim 13, wherein the plurality of interconnected nodes of the network further comprises multiple switch nodes, each switch node having a managing node address register associated therewith, and said means for avoiding race condition comprises multiple set count registers, each set count register being associated with a different managing node address register of the multiple switch nodes.

15. The system of claim 14, wherein said means for avoiding race condition further comprises means for reading a set count value from the set count register associated with each managing node address register when identifying the next adjacent node in the network with unknown node address and for writing a managing node address into said managing node address register only if the set count value of the associated set count register is unchanged from the set count value read from the set count register.

16. A self-identifying network comprising:

a plurality of interconnected nodes, each node having a port for transfer of a packet to a next adjacent node in the network;

an all-node address indicator for selective insertion in a field of the packet according to whether a node address of the next adjacent node is known, wherein when inserted in the field, said all-node address indicator causes the packet to be received by a next adjacent node in the network notwithstanding that the next adjacent node has an unknown node address;

automatic means for selectively inserting the all-node address indicator into said field of said packet at each node of the network with a known node address when said node with a known address has a next adjacent node with an unknown node address to access said next adjacent node and hence identify topology of the network; and

wherein said automatic means for selectively inserting comprises means for not inserting the all-node address indicator when said node with a known address has a next adjacent node with a known address.

17. The self-identifying network of claim 16, wherein said automatic means for selectively inserting the all-node address indicator comprises means for stepwise progressing through the network to identify each node of the plurality of interconnected nodes.

18. The self-identifying network of claim 16, wherein the plurality of interconnected nodes comprises at least one managing node, multiple switch nodes and multiple end nodes, said at least one managing node being coupled to said multiple end nodes through said multiple switch nodes, each switch node having a port with a port control register field associated therewith which when set instructs the switch node to insert the all-node address indicator into the field of the packet before forwarding the packet to the next adjacent node in the network connected to said port, and wherein said automatic means for selectively inserting the all-node address indicator comprises means disposed at the at least one managing node for remotely, selectively setting the port control register fields associated with the ports of the switch nodes having a next adjacent node connected thereto with unknown node address.

19. The self-identifying network of claim 18, wherein said all-node address indicator comprises a universal destination address and said field of the packet comprises a destination address field in the packet.

20. The self-identifying network of claim 18, wherein said all-node address indicator comprises a universal routing indicator and said field of the packet comprises a routing field in the packet.

21. The self-identifying network of claim 18, wherein each node of said plurality of interconnected nodes includes a node address register and a managing node address register, and wherein said self-identifying network further comprises means for configuring said multiple switch nodes and multiple end nodes from said at least one managing node by writing a specific node address into said address node register and a managing node address into said managing node address register of each switch node and end node having unconfigured address node and managing node address registers.

22. The self-identifying network of claim 21, wherein said at least one managing node comprises multiple managing nodes and said automatic means for selectively inserting the all-node address indicator comprises means disposed at at least two managing nodes of said multiple managing nodes for remotely, selectively setting the port control registers associated with the ports of the switch nodes having a next adjacent node connected thereto with unknown node address, and wherein said self-identifying network further comprises means for avoiding race condition between said at least two managing nodes in identifying topology of the network.

23. The self-identifying network of claim 22, wherein said means for avoiding race condition comprises multiple set count registers, each set count register being associated with a different managing node address register of the multiple switch nodes and multiple end nodes.

24. The self-identifying network of claim 23, wherein said means for avoiding race condition comprises means for writing a managing node address into a managing node address register of one node of said multiple switch nodes and multiple end nodes only if a previously read set count value in the associated set count register is unchanged, and means for incrementing the set count value upon writing the managing node address into the managing node address register.

25. The self-identifying network of claim 18, further comprising means for automatically notifying the at least one managing node of a change in the topology of the network after the at least one managing node has identified topology of the network.

26. The self-identifying network of claim 18, wherein said plurality of interconnected nodes are interconnected by bidirectional links having two ends, each end of each bidirectional link being coupled to a port of a node of the plurality of interconnected nodes, each port containing both transmitting logic and receiving logic for communicating packets across the bidirectional link coupled thereto.

27. A method for identifying topology of a network having a plurality of interconnected nodes, each node having a port for transfer of a packet to a next adjacent node in the network, a given node of the plurality of interconnected nodes having a known node address and being connected to a next adjacent node, said method comprising:

(a) sending a packet to the given node with known node address for output to the next adjacent node;

(b) upon receipt of the packet at said given node, providing in the packet an all-node address indicator when said next adjacent node of said given node has an unknown node address, said all-node address indicator directing the packet to be received by any node of the plurality of interconnected nodes;

(c) forwarding the packet from the given node to the next adjacent node with unknown node address, said packet having the all-node address indicator provided therein pursuant to said providing step (b), wherein upon receipt of the packet by the next adjacent node with unknown node address, the next adjacent node with unknown node address can be identified; and

wherein said providing step (b) further comprises not providing the all-node address indicator in said packet when said next adjacent node has a known address.

28. The method of claim 27, wherein the packet comprises a request packet to read address node information from the next adjacent node with unknown node address, and wherein said method further comprises sending a response packet back to a node originating the request packet, said node originating the request packet comprising one node of said plurality of interconnected nodes, said response packet containing the node address of the next adjacent node with unknown node address.

29. The method of claim 27, wherein each port has a port control register field associated therewith which when set instructs the node to insert the all-node address indictor into a field of the packet before forwarding the packet to the next adjacent node in the network, and wherein said method further comprises selectively setting the port control register field associated with the port of said given node prior to said forwarding step (c), wherein said given node responds to setting of the port control register field by inserting the all-node address indicator into the packet prior to said forwarding step (c).

30. The method of claim 29, wherein at least one node of said plurality of interconnected nodes comprises a managing node, and wherein said method further comprises directing said selectively setting of the port control register fields from the at least one managing node of the plurality of interconnected nodes.

31. The method of claim 30, further comprising repeating steps (a)-(c) for multiple given nodes of the plurality of interconnected nodes such that topology of the network is progressively identified from said at least one managing node.

32. The method of claim 31, wherein said at least one managing node comprises multiple managing nodes, and wherein said method further comprises identifying topology of the network from at least two managing nodes of said multiple managing nodes, and automatically avoiding race condition between said at least two managing nodes in identifying the topology of the network.

33. The method of claim 31, further comprising monitoring the network for changes after identifying topology of the network, and automatically notifying the at least one managing node of a change in the topology of the network.