Methods and apparatus for bus access arbitration of nodes organized into acyclic directed graph by cyclic token passing and alternatively propagating request to root node and grant signal to the child node

In a computer system comprising a plurality of components interconnected by a plurality of communications links, said plurality of components each having at least a first communications node wherein said communications nodes interface their associated component with a communications link through a node port, said nodes being capable of having a plurality of ports, said configuration of nodes and communications links comprising a directed acyclic 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 graph being designated branch nodes, said acyclic directed graph having established hierarchical parent-child relations ships 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 fair bus access arbitration comprising the steps of:

• transmitting a "Bus Denied" (BD) signal from a requesting node to all of its child nodes, said requesting node having a packet of information to propagate on said bus;
• transmitting a "Bus Request" (BR) signal from a requesting node to its parent node;
• all nodes receiving the BR signal forwarding the BR signal to their respective parent nodes and propagating a BD signal to all child nodes that were not the source of the BR signal;
• the root node, upon receiving a BR signal from one adjacent node, responding to said adjacent node with a "Bus Grant" (BG) signal, said root node propagating a BD signal to all other adjacent nodes;
• all nodes receiving the BG signal from a parent node then propagating BG signal to the child node which had previously forwarded the BR signal, unless the node is the requesting node;
• the requesting node, upon receiving the BG signal acknowledging said signal and propagating said packet of information;
• and
• the root node, upon determining that it requires access to the bus, propagating a BD signal to all adjacent nodes and granting itself access to the bus.

In a computer system comprising a plurality of components interconnected by a plurality of communications links, said plurality of components each having at least a first communications node wherein said communications nodes interface their associated component with a communications link through a node port, said nodes being capable of having a plurality of ports to which communications links to adjacent nodes couple, each node having a predetermined selection criterion established for selecting adjacent nodes coupled through its ports, said configuration of nodes and communications links comprising a directed acyclic 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 graph being designated branch nodes, said acyclic directed graph having established hierarchical parent-child relations ships 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 token passing bus access arbitration wherein a metaphorical token is passed from node to node in a cycle through the graph, the node having the token being the node with bus access, said method comprising the step of passing the token through the acyclic directed graph in an order determined by the predetermined selection criterion each node has established for selecting adjacent nodes .