Method and apparatus for unique address assignment, node self-identification and topology mapping for a directed acyclic graph

• US 5,394,556 A
• Filed: 12/21/1992
• Issued: 02/28/1995
• Est. Priority Date: 12/21/1992
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Oprescu, Florin
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): AN, MENG AI T
• Application Number:
  US07/994,402
• Time in Patent Office: 799 Days
• Field of Search: 395/800, 395/200, 395/325, 370/60, 370/94.3, 340/825.02, 359/120
• US Class Current: 709/220
• CPC Class Codes: G06F 13/36 for access to common bus or bus system
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: H04L 12/40078 Bus configuration home automation networks H04L12/2803; arrangements for maintenance or administration H04L41/00
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 61/5038 for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use

Abstract

A node identification system is described for use in a computer system in which the various components of the system are interconnected via nodes on a communications bus. Once the topology of the nodes has been resolved into an acyclic directed graph, each node may be assigned a non-predetermined unique address. Each node having a plurality of ports has an apriori assigned priority for port selection. Each child node connected to a parent is allowed to respond in the predetermined sequence depending upon the port through which it is connected to its parent. Each node in the graph will announce its presence according to its location in the graph. Each receives an address incremented from the previous addresses assigned, thereby insuring uniqueness. The same mechanism may be implemented to allow each node in turn to broadcast information on the bus concerning the parameters of its local host. Likewise, additional information may be conveyed from each node concerning connections to other nodes thereby allowing a host system to generate a map of the resolved topology including any information about disabled links which may be used for redundancy purposes.

Claims

1. In a computer system having a bus, said computer system comprising a plurality of components interconnected by a plurality of communications links, said plurality of components each having a plurality of communications nodes wherein said nodes have at least one of a plurality of ports and interface with their associated components through a communications link which connects one port of one node with another port of another node, each port of each node having a predetermined selection criterion established for adjacent nodes that are coupled to that node, said nodes and communications links as interfaced together comprising an acyclic directed graph wherein one node is designated a root node, all nodes coupled to only one adjacent node are designated leaf nodes, all other nodes in the acyclic directed graph being designated branch nodes, all nodes initially having a status of being unidentified nodes, said acyclic directed graph having established hierarchical parent-child relationships between all adjacent nodes proceeding from the root node down to any leaf nodes wherein a leaf node has only one parent node and all nodes adjacent to the root node are child nodes with respect to the root node but parent nodes with respect to other adjacent nodes, the root node being defined as having no parent node, a method of assigning unique addresses to the nodes of the acyclic directed graph comprising the steps of:

each unidentified leaf node initially transmitting a "Bus Request" (BR) signal onto the bus;

each branch node waiting until all adjacent child nodes either propagate or forward a BR signal or are identified, then propagating the BR signal to a parent node;

the root node waiting until all adjacent nodes either propagate a BR signal or are identified then propagating a "Bus Grant" (BG) signal to one of the adjacent unidentified nodes based on said predetermined selection criterion for selecting adjacent nodes, said BG signal being propagated down through the acyclic directed graph through intervening nodes based on said predetermined selection criterion for selecting adjacent nodes until a node that initiated a BR signal receives the BG signal;

the node receiving the BG signal then broadcasting an address announcement to all nodes on the bus;

each node on the bus counting, as a number, how many address announcements are broadcast by other nodes;

each node setting a unique address, said unique address being a function of the number of address announcements broadcast by other nodes until the node receives a BG signal and subsequently broadcasts an address announcement, said node then attaining the status of being identified; and

repeating the above steps until all nodes are identified,

whereby each node will have counted a different number of address announcements broadcast by other nodes prior to setting the unique address identifying the node thus ensuring that each node acquires a unique address assignment.

2. The method of claim 1 further comprising the step of the node receiving the BG signal then broadcasting parameter information about the component associated with the node receiving the BG signal to all other nodes on the bus.

3. The method of claim 2 further comprising the step of the node receiving the BG signal then broadcasting topology information concerning the node receiving the BG signal to all other nodes on the bus.

4. The method of claim 3 wherein said topology information includes information about the nodes adjacent nodes and link status.

5. In a computer system having a bus, said computer system comprising a plurality of components interconnected by a plurality of communications links, said plurality of components each having a plurality of communications nodes wherein said nodes have at least one of a plurality of ports and interface with their associated components through a communications link which connects one port of one node with another port of another node, each port of each node having a predetermined selection criterion established for adjacent nodes that are coupled to that node, said nodes and communications links as interfaced together comprising an acyclic directed graph wherein one node is designated a root node, all nodes coupled to only one adjacent node are designated leaf nodes, all other nodes in the acyclic directed graph being designated branch nodes, all nodes initially having a status of being unidentified nodes, said acyclic directed graph having established hierarchical parent-child relationships between all adjacent nodes proceeding from the root node down to any leaf nodes wherein a leaf node has only one parent node and all nodes adjacent to the root node are child nodes with respect to the root node but parent nodes with respect to other adjacent nodes, the root node being defined as having no parent node, a method of assigning unique addresses to the nodes of the acrylic directed graph comprising the steps of:

each unidentified leaf node initially transmitting a "Bus Request" (BR) signal onto the bus;

each branch node waiting until all adjacent child nodes either propagate or forward a BR signal or are identified, then propagating the BR signal to a parent node;

the root node waiting until all adjacent nodes either propagate a BR signal or are identified then propagating a "Bus Grant" (BG) signal to one of the adjacent unidentified nodes based on said predetermined selection criterion for selecting adjacent nodes, said BG signal being propagated down through the acyclic directed graph through intervening nodes based on said predetermined selection criterion for selecting adjacent nodes until a node that initiated a BR signal receives the BG signal;

the node receiving the BG signal then broadcasting an address announcement to all nodes on the bus;

the node receiving the BG signal then broadcasting parameter information about the component associated with the node receiving the BG signal to all other nodes on the bus;

each node on the bus counting, as a number, how many address announcements are broadcast by other nodes;

each node setting a unique address, said unique address being a function of the number of address announcements broadcast by other nodes until the node receives a BG signal and subsequently broadcasts an address announcement, said node then attaining the status of being identified; and

repeating the above steps until all nodes are identified,

whereby each node will have counted a different number of address announcements broadcast by other nodes prior to setting the unique address identifying the node thus ensuring that each node acquires a unique address assignment.

6. In a computer system having a bus, said computer system comprising a plurality of components interconnected by a plurality of communications links, said plurality of components each having a plurality of communications nodes wherein said nodes have at least one of a plurality of ports and interface with their associated components through a communications link which connects one port of one node with another port of another node, each port of each node having a predetermined selection criterion established for adjacent nodes that are coupled to that node, said nodes and communications links as interfaced together comprising an acyclic directed graph wherein one node is designated a root node, all nodes coupled to only one adjacent node are designated leaf nodes, all other nodes in the acyclic directed graph being designated branch nodes, all nodes initially having a status of being unidentified nodes, said acyclic directed graph having established hierarchical parent-child relationships between all adjacent nodes proceeding from the root node down to any leaf nodes wherein a leaf node has only one parent node and all nodes adjacent to the root node are child nodes with respect to the root node but parent nodes with respect to other adjacent nodes, the root node being defined as having no parent node, a method of assigning unique addresses to the nodes of the acyclic directed graph comprising the steps of:

each unidentified leaf node initially transmitting a "Bus Request" (BR) signal onto the bus;

each branch node waiting until all adjacent child nodes either propagate or forward a BR signal or are identified, then propagating the BR signal to a parent node;

the root node waiting until all adjacent nodes either propagate a BR signal or are identified then propagating a "Bus Grant" (BG) signal to one of the adjacent unidentified nodes based on said predetermined selection criterion for selecting adjacent nodes, said BG signal being propagated down through the acyclic directed graph through intervening nodes based on said predetermined selection criterion for selecting adjacent nodes until a node that initiated a BR signal receives the BG signal;

the node receiving the BG signal then broadcasting an address announcement to all nodes on the bus;

the node receiving the BG signal then broadcasting topology information concerning the node receiving the BG signal to all other nodes on the bus

each node on the bus counting, as a number, how many address announcements are broadcast by other nodes;

each node setting a unique address, said unique address being a function of the number of address announcements broadcast by other nodes until the node receives a BG signal and subsequently broadcasts an address announcement, said node then attaining the status of being identified; and

repeating the above steps until all nodes are identified,

whereby each node will have counted a different number of address announcements broadcast by other nodes prior to setting the unique address identifying the node thus ensuring that each node acquires a unique address assignment.

7. The method of claim 6 wherein said topology information includes information about the nodes adjacent nodes and link status.