Method and apparatus for loop breaking on a serial bus

• US 6,628,607 B1
• Filed: 07/09/1999
• Issued: 09/30/2003
• Est. Priority Date: 07/09/1999
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Hauck, Jerrold Von, Whitby-Strevens, Colin
• Primary Examiner(s): Yao, Kwang Bin
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/350,583
• Time in Patent Office: 1,544 Days
• Field of Search: 370/216-222, 370/912, 370/282, 370/419, 370/403, 370/242, 370/241, 370/259, 370/237, 370/254-256, 370/457, 370/228, 370/401, 370/468, 370/389-397, 370/355, 370/431, 709/224, 709/232, 709/235, 709/238, 709/243, 714/732
• US Class Current: 370/216
• CPC Class Codes: H04L 12/40078 Bus configuration home automation networks H04L12/2803; arrangements for maintenance or administration H04L41/00
• CPC Class Codes: H04L 12/6418 Hybrid transport

Abstract

A method for loop breaking includes selecting a first port of a node, transmitting a first packet containing a first identifier from the first port of the node, listening for a second packet containing a second identifier for a period of time on a second port of the node, joining the first port and the node if the second identifier meets a first criteria with respect to the first identifier and quarantining the first port when the second identifier meets a second criteria with respect to the first identifier.

Claims

1. In an electronics system including at least one bus, each said bus including at least one node, each said node including at least one port, a method for loop breaking, said method comprising:

selecting a first port of a node;

transmitting a first packet on a bus attached to said first port of said node, said first packet containing a unique identifier;

listening for a second packet for a period of time on a second port of said node, said second packet containing said unique identifier;

joining said first port to said node if said second packet is not received within said period of time; and

quarantining said first port if said second packet is received within said period of time.

3. The method of claim 1, further comprising unquarantining a quarantined port if an unquarantined port is rendered inoperative.

4. The method of claim 1, further comprising determining whether other ports of said node have been tested for loops.

5. The method of claim 4 wherein

said bus is compatible with the IEEE1394-1995 standard; and

said method further comprises;

resuming loop testing if a bus disconnect is detected;

removing said first port from said bus if a tree-ID timeout is detected; and

attempting to join said first port to said bus if a tree-ID timeout is detected.

2. In an electronics system including at least one bus, each said bus including at least one node, each said node including at least one port, a method for loop breaking, said method comprising:

selecting a first port of a node, said first port operatively coupled to a first bus and a node;

transmitting a first packet on said first bus from said first port of said node, said first packet containing a unique identifier;

listening for a second packet for a period of time on a second port of said node, said second port operatively coupled to a second bus, said second port not operatively coupled to said node, said second packet containing said unique identifier;

joining said second port to said node if said second packet is not received within said period of time; and

quarantining said second port if said second packet is received within said period of time.

6. In an electronics system including at least one bus, each said bus including at least one node, each said node including at least one port, a method for loop breaking, comprising:

selecting a first port of a node, said first port operatively coupled to a first bus;

transmitting a first packet on said first bus from said first port of said node, said first packet including a first identifier;

listening for a second packet for a first amount of time on a second port of said node, said second packet including a second identifier;

joining said first port and said node if said second identifier meets a first criteria with respect to said first identifier;

surrendering control of said first bus if said second identifier meets a second criteria with respect to said first identifier; and

quarantining said first port if said second identifier meets a third criteria with respect to said first identifier.

7. The method of claim 6 wherein

said first criteria is met if said second identifier is less than said first identifier;

said second criteria is met if said second identifier is greater than said first identifier; and

said third criteria is met if said second identifier is equivalent to said first identifier.

8. In an electronics system including at least two buses, each of said two buses including at least one node, each said node including at least one port, a method for loop breaking, comprising:

selecting a first port of a node, said first port operatively coupled to a first bus;

transmitting a first packet on said first bus from said first port of said node;

listening for a second packet for a first amount of time on a second port of said node, said second port operatively coupled to a second bus;

joining said first port to said node if said second packet meets a first criteria with respect to said first packet;

surrendering control of said first bus if said second packet meets a second criteria with respect to said first packet;

transmitting a third packet on said first bus from said first port of said node if said second packet meets a third criteria with respect to said first packet;

listening for a fourth packet for a second amount of time on said second port of said node;

joining said first port to said node if said fourth packet meets a fourth criteria with respect to said third packet;

surrendering control of said first bus if said fourth packet meets a fifth criteria with respect to said third packet; and

quarantining said first port if said fourth packet meets a sixth criteria with respect to said third packet.

9. The method of claim 8 wherein joining said first port to said node comprises:

initiating arbitration for said first bus and said second bus;

issuing a relatively short bus reset if arbitration of said first bus and said second bus is won before a period of time has elapsed; and

issuing a relatively long bus reset if arbitration of said first bus and said second bus is not won before said period of time has elapsed.

10. The method of claim 9 wherein said selecting comprises:

determining the number of ports that have been joined; and

choosing a first port to be tested for loops if at least one other port has been joined.

11. The method of claim 10 wherein each of said first packet, said second packet, said third packet and said fourth packet includes a unique identifier.

12. The method of claim 11 wherein each unique identifier comprises a node ID and a port ID of the transmitting port, a node ID and port ID of the receiving port, the speed of the untested port and a GUID.

13. The method of claim 11 wherein each unique identifier comprises a node ID and a port ID of the first port, a node ID and port ID of the second port, the speed of the first port and a random number.

14. The method of claim 9 wherein said arbitrating further comprises:

initiating arbitration simultaneously on said first bus and said second bus if both said first bus and said second bus are multi-node buses;

initiating arbitration on the multi-node bus before initiating arbitration on a single-node bus if one of said first bus and said second bus is a multi-node bus and the other bus is a single-node bus;

initiating arbitration simultaneously on said first bus and said second bus if both said first bus and said second bus are single-node buses; and

said method further comprises initiating loop testing on whatever bus is granted arbitration first.

15. The method of claim 9 wherein said selecting further comprises choosing the untested port attached to the bus having the highest speed with respect to other buses attached to untested ports.

16. The method of claim 9 wherein

said first criteria is met if said second packet is less than said first packet;

said second criteria is met if said second packet is greater than said first packet;

said third criteria is met if said second packet is equivalent to said first packet;

said fourth criteria is met if said fourth packet is less than said third packet;

said fifth criteria is met if said fourth packet is greater than said third packet; and

said sixth criteria is met if said fourth packet is equivalent to said third packet.

17. In an electronics 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 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 one node that is designated a root node, all nodes coupled to only one adjacent node are designated leaf nodes, all other nodes in the configuration being designated branch nodes, said nodes 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 the other nodes, the root node being defined as having no parent node, a method of loop breaking, comprising:

selecting a first port of a node;

joining said first port to a communications link attached to said first port of said node;

transmitting a first packet on said communications link from said first port of said node, said first packet containing a unique identifier;

listening for a second packet for a first amount of time on a second port of said node, said second packet containing a unique identifier;

joining said first port to said node if said second packet is not received within said first amount of time; and

quarantining said first port if said second packet is received within said first amount of time.

18. The method of claim 17, further comprising determining whether other ports of said node have been tested for loops.

19. In an electronic system, a method for loop breaking on a serial bus compatible with the IEEE1394-1995 standard, the method comprising:

selecting a first port of a node;

joining said first port to a bus attached to said first port of said node;

transmitting a first packet on the bus from said first port of said node, said first packet containing a unique identifier;

listening for a second packet for a first amount of time on a second port of said node, said second packet containing a unique identifier;

joining said first port to said node if said second packet is not received within said first amount of time; and

quarantining said first port if said second packet is received within said first amount of time.

20. A serial bus compatible with the IEEE1394-1995 standard and comprising:

a plurality of nodes; and

a plurality of communications links interconnecting the nodes,

wherein a loop passing through a node is broken by internally isolating at least one port from said node, such that all ports of said node remain connected to their neighbors.

21. A serial bus comprising:

a plurality of nodes; and

a plurality of communications links interconnecting the nodes, each communications link being coupled between two nodes in a manner such that each node is coupled to every other node via one or more communications links, wherein at least one of said plurality of nodes comprises;

at least one port coupled to a communications link and operative to transmit and receive data via the communications link, wherein a loop passing through a node is broken by internally isolating at least one port from the node, such that all ports of the node remain connected to their neighbors.

22. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to break loops in an electronics system including at least one bus, each bus including at least one node, each node including at least one port, the program storage device comprising:

code for causing a machine to select a first port of a node, said first port operatively coupled to a first bus and a node;

code for causing a machine to transmit a first packet on said first bus from said first port of said node, said first packet containing a unique identifier;

code for causing a machine to listen for a second packet for a period of time on a second port of said node, said second packet operatively coupled to said node, said second packet containing said unique identifier;

code for causing a machine to join said first port to said node if said second packet is not received within said period of time; and

code for causing a machine to quarantine said second port if said second packet is received within said period of time.

23. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to break loops in an electronics system including at least one bus, each bus including at least one node, each node including at least one port, the program storage device comprising:

code for causing a machine to select a first port of a node, said first port operatively coupled to a first bus and a node;

code for causing a machine to transmit a first packet on said first bus from said first port of said node, said first packet containing a unique identifier;

code for causing a machine to listen for a second packet for a period of time on a second port of said node, said second port operatively coupled to a second bus, said second port not operatively coupled to said node, said second packet containing said unique identifier;

code for causing a machine to join said second port to said node if said second packet is not received within said period of time; and

code for causing a machine to quarantine said second port if said second packet is received within said period of time.

24. A program storage device readable by a machine, tangibly embodying a program instructions executable by the machine to break loops in an electronics system

including at least one bus, each bus including at least one node, each node including at least one port, the program storage device comprising:

code for causing a machine to select a first port of a node, said first port operatively coupled to a first bus;

code for causing a machine to transmit a first packet on said first bus from said first port of said node;

code for causing a machine to listen for a second packet for a first amount of time on a second port of said node, said second packet including a second identifier;

code for causing a machine to join said first port and said node if said second identifier meets a first criteria with respect to said first identifier;

code for causing a machine to surrender control of said second bus if said second identifier meets a second criteria with respect to said first identifier; and

code for causing a machine to quarantine said first port if said second identifier meets a third criteria with respect to said first identifier.

25. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to break loops in an electronics system including at least one bus, each bus including at least one node, each node including at least one port, the program storage device comprising:

code for causing a machine to select a first port of a node, said first port operatively coupled to a first bus;

code for causing a machine to transmit a first packet on said first bus from said first port of said node;

code for causing a machine to listen for a second packet for a first amount of time on a second port of said node;

code for causing a machine to join said first port and said node if said second packet meets a first criteria with respect to said first packet;

code for causing a machine to surrender control of said second bus if said second packet meets a second criteria with respect to said first packet;

code for causing a machine to transmit a third packet on said first bus from said first port of said node if said second packet meets a third criteria with respect to said first packet;

code for causing a machine to listen for a fourth packet for a second amount of time on said second port of said node;

code for causing a machine to join said first port and said node if said fourth packet meets a fourth criteria with respect to said third packet;

code for causing a machine to surrender control of said second bus if said fourth packet meets a fifth criteria with respect to said third packet; and

code for causing a machine to quarantine said first port if said fourth packet meets a sixth criteria with respect to said third packet.

26. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to break loops in an electronics 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 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 one node that 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 nodes 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 the other nodes, the root node being defined as having no parent node, the program storage device comprising:

code for causing a machine to select a first port of a node;

code for causing a machine to transmit a first packet on said communications link from said first port of said node;

code for causing a machine to listen for a second packet for a first amount of time on a second port of said node;

code for causing a machine to join said first port to said node if said second packet is not received within said first amount of time; and

code for causing a machine to quarantine said first port if said second packet is received within said first amount of time.

27. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to break loops in an electronic system, a method for loop breaking on a serial bus compatible with the EEEE1394-1995 standard, the program storage device comprising:

code for causing a machine to select a first port of a node;

code for causing a machine to transmit a first packet on the bus from said first port of said node;

code for causing a machine to listen for a second packet for first amount of time on a second port of said node, said second packet containing a unique identifier;

a fourth module comprising code for causing a machine to join said first port to said node if said second packet is not received within said first amount of time; and

a fifth module comprising code for causing a machine to quarantine said first port if said second packet is received within said first amount of time.

28. An electronic device having a serial bus for interconnecting said device with another device, said bus comprising:

means for selecting a first port of a node;

means for transmitting a first packet on a bus attached to said first port of said node, said first packet containing a unique identifier;

means for listening for a second packet for a period of time on a second port of said node, said second packet containing said unique identifier;

means for joining said first port to said node if said second packet is not received within said period of time; and

means for quarantining said first port if said second packet is received within said period of time.

29. An electronic device having a serial bus for interconnecting said device with another device, said bus comprising:

means for selecting a first port of a node, said first port operatively coupled to a first bus and a node;

means for transmitting a first packet on said first bus from said first port of said node, said first packet containing a unique identifier;

means for listening for a second packet for a period of time on a second port of said node, said second port operatively coupled to a second bus, said second port not operatively coupled to said node, said second packet containing said unique identifier;

means for joining said second port to said node if said second packet is not received within said period of time; and

means for quarantining said second port if said second packet is received within said period of time.