Token style arbitration on a serial bus by passing an unrequested bus grand signal and returning the token by a token refusal signal

• US 5,784,648 A
• Filed: 12/01/1995
• Issued: 07/21/1998
• Est. Priority Date: 12/01/1995
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Duckwall, William S.
• Primary Examiner(s): DINH, DUNG C
• Application Number:
  US08/565,986
• Time in Patent Office: 963 Days
• Field of Search: 395/200.06, 395/287, 395/856, 395/857, 395/728, 395/730, 395/731, 395/732, 395/860, 395/300, 370/450, 370/451, 370/453
• US Class Current: 710/40
• CPC Class Codes: G06F 13/37 using a physical-position-dependent priority, e.g. daisy chain, round robin or token passing
• CPC Class Codes: H04L 12/40058 Isochronous transmission
• CPC Class Codes: H04L 12/40084 Bus arbitration

Abstract

An electronic system comprises a plurality of components each having at least one communication node and being coupled together by communication links through the respective communication nodes so that the plurality of communication links and communication nodes form a bus which resembles an acyclic directed graph having established hierarchical parent-child relationships between adjacent nodes and a root node. Token passing style arbitration is implemented on the system, in one embodiment, in response to the root node sending out an unrequested bus grant, so that the node with the token has access to the bus.

Claims

1. In an electronic system comprising a plurality of components interconnected by a plurality of communication 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 criteria 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 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 token passing bus arbitration wherein a metaphorical token comprising an unrequested bus grant signal 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, said method further comprising a step of returning the token by transmitting a token-refusal signal.

2. A method of token passing bus arbitration as in claim 1 wherein at least one of said plurality of communications links comprises a twisted pair.

3. A method of token passing bus arbitration as in claim 1 wherein at least one of said plurality of communication links comprises an optical fiber.

4. A method of token passing bus arbitration as in claim 1 wherein at least one of said plurality of communication links comprises a wireless coupling.

5. A method of token passing bus arbitration as in claim 1 wherein at least one of said plurality of communication links comprises a cable, the cable carrying two signal pairs and signal ground.

6. A method of token passing bus arbitration as in claim 5 wherein the cable further carries a power pair.

7. A method of token passing bus arbitration as in claim 1 wherein:

the node end the data transmission by transmitting a data end signal, the data ends signal comprises a penultimate bit and an ultimate bit, wherein the penultimate bit is encoded to indicate whether a metaphorical token is being passed by the node such that when the penultimate bit is set by the node the token is passed and the node relinquishes control of the bus.

8. A data communication system comprising:

a plurality of communication nodes, each of the communication nodes having at least one communication port, at least two of the communication nodes being capable of operating in a token passing bus arbitration mode;

a plurality of communication links interconnecting logically adjacent communication nodes through associated communication ports so as to form a configuration of communication nodes and communication links, the configuration of communication nodes and communication links comprising a serial bus;

wherein each of the communication nodes having a predetermined selection criterion established for selecting logically adjacent nodes coupled through its communication ports via one of the communication links so that the configuration of communication nodes and communication links comprise an acyclic directed graph wherein one of the communication nodes is designated a root node and one of the communication nodes is designated a token master node, all communication nodes coupled to only one adjacent communication node being designated leaf nodes, all other communication nodes being designated branch nodes, the acyclic directed graph having established parent-child relationships between all logically adjacent coupled communication nodes proceeding from the root node down to any leaf node;

wherein said token master node generates a token which is passed between the communication nodes having the capability of operating in the token passing bus arbitration mode such that the communication node in possession of the token has access to the bus; and

wherein said token comprises an unrequested bus grant signal which may be returned by transmitting a token refusal signal.

9. A data communication system as in claim 8 wherein the communication node with access to the bus transmits information on the bus in the form of data packets and indicates that it has completed transmitting information by sending a data end signal.

10. A data communication system as in claim 9 wherein the node with access to the bus passes the token by transmitting a token-passing bit pattern as part of the data end signal.

11. A data communication system as in claim 10 wherein the token-passing bit pattern comprises penultimate bit encoding where the penultimate bit of the dribble bits is set so as to indicate that the token is being passed.

12. A data communication system as in claim 11 wherein when the penultimate bit of the dribble bits is set to a logical one the token is passed.

13. A data communication system as in claim 8 wherein said communications links comprising six conductor cables, said six conductors being arranged as two signal pairs and a power pair.

14. A data communication system as in claim 8 wherein each of said communications ports of said communications nodes are arranged as an A pair and a B pair and wherein said communications links are arranged between said communications nodes so as to couple the A pair of a child node'"'"'s communication port to the B pair of the child node'"'"'s parent node'"'"'s communication port and to couple the B pair of the child node'"'"'s communication port to the A pair of the child node'"'"'s parent node'"'"'s communication port.

15. A data communication system as in claim 8 wherein said communication links comprising twisted pairs.

16. A data communication system as in claim 8 wherein said communications links comprising optical fibers.

17. A data communication system as in claim 8 wherein said communication links comprising wireless coupling.

18. A data communication system as in claim 8 wherein the token master is the root node.

19. A data communication system comprising:

a plurality of communication nodes, each of the communication nodes having at least one communication port, at least two of the communication nodes being capable of operating in a token passing bus arbitration mode;

a plurality of communication links interconnecting logically adjacent communication nodes through associated communication ports so as to form a configuration of communication nodes and communication links, the configuration of communication nodes and communication links comprising a serial bus;

wherein each of the communication nodes having a predetermined selection criterion established for selecting logically adjacent nodes coupled through its communication ports via one of the communication links so that the configuration of communication nodes and communication links comprising an acyclic directed graph, the graph comprising a plurality of local clusters of said plurality of communication nodes, each of said plurality of local clusters of nodes having at least one of said communication nodes capable of operating in token passing bus arbitration mode, wherein one of the communication nodes is designated a root node and one of the communication nodes is designated a token master node, all communication nodes coupled to only one adjacent communication node being designated leaf nodes, all other communication nodes being designated branch nodes, the acyclic directed graph having established parent-child relationships between all logically adjacent coupled communication nodes proceeding from the root node down to any leaf node; and

wherein said token master node generates a token which is passed between the communication nodes having the capability of operating in the token passing bus arbitration mode such that the communication node in possession of the token operates as a local root node for an associated one of said local clusters of nodes, the local root node receiving bus access requests from nodes within said associated local cluster of nodes and generating bus grant signals in response thereto.