Method and apparatus for preventing loops in a full-duplex bus

• US 6,985,981 B1
• Filed: 10/11/2002
• Issued: 01/10/2006
• Est. Priority Date: 11/05/1999
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Whitby-Strevens, Colin, Hauck, Jerrold V.
• Primary Examiner(s): Myers, Paul R.
• Application Number:
  US10/269,915
• Time in Patent Office: 1,187 Days
• Field of Search: 710/100, 710300-306, 710/104, 710/107, 370216-222, 370241-242, 370254-256, 709/224, 709/232, 709/235, 709/238, 709/243
• US Class Current: 710/107
• CPC Class Codes: G06F 13/426 using an embedded synchronisation, e.g. Firewire bus, Fibre Channel bus, SSA bus
• 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/40117 Interconnection of audio or video/imaging devices home automation networks H04L12/2803; bitstream network arrangements specially adapted for distribution of digital video signals H04N7/24
• CPC Class Codes: H04L 12/40123 Interconnection of computers and peripherals printer information exchange with computer G06F3/1293
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 43/50 Testing arrangements

Abstract

A method and device for preventing loops in a high performance serial bus is disclosed. One aspect includes selecting an untested connection by at least one of the plurality of nodes to the bus; establishing dominance of the bus by one of the nodes which selected the untested connection; testing for loops through the connection by the nodes; and joining the untested connection to the bus if no loops are found in the bus.

Claims

1. In a system having at least one full-duplex bus having a plurality of nodes, wherein at least one of the nodes has an untested connection, a method for preventing loops comprising the acts of:

selecting an untested connection by at least one of the plurality of nodes to join said at least one bus;

establishing dominance of said at least one full-duplex bus by said one of said plurality of nodes which selected said untested connection;

testing for loops through said untested connection by said at least one of said plurality of nodes; and

joining said untested connection to said at least one of said full-duplex bus by said at least one of said plurality nodes if no loops are found in said bus.

2. The method of claim 1, wherein the act of selecting an untested connection by at least one of the plurality of nodes to join the bus further comprises selecting, by all nodes with at least one untested connection, at least one untested connection.

3. The method of claim 1, wherein said act of joining a candidate further comprises:

remotely arbitrating for control of a bus segment to join with said bus;

waiting for a predetermined period of time;

issuing a short bus reset if said arbitration is won within said predetermined period of time; and

issuing a long bus reset if arbitration is not won within said predetermined period of time.

4. The method of claim 3, wherein said predetermined period of time is less than or equal to the time period of one asynchronous packet on said bus.

5. The method of claim 1, wherein said act of joining a candidate further comprises:

instructing a PHY on a remote end of a candidate connection to arbitrate for control of a bus segment to join with said bus;

determining whether said remote PHY wins arbitration within a predetermined period of time;

issuing a short bus reset if said arbitration is won within said predetermined period of time; and

issuing a long bus reset if arbitration is not won within said predetermined period of time.

6. The method of claim 1, wherein said act of establishing dominance of said bus by said candidates further comprises:

selecting a candidate by arbitrating for control of said bus;

transmitting a packet containing a unique identifier on said bus;

listening for packets received on said bus;

establishing dominance if the received packet meets a first condition;

dropping transmission of packets if said received packets meet a second condition; and

re-transmitting packets a predetermined number of times if the received packets meet a third condition.

7. The method of claim 6, wherein said first condition is met if said unique identifier contained within said transmitted packet is greater than said unique identifier contained within said received packet.

8. The method of claim 6, wherein said first condition is met if said unique identifier contained within said transmitted packet is less than said unique identifier contained within said received packet.

9. The method of claim 6, wherein said first condition is met if said unique identifier contained within said transmitted packet is equal to said unique identifier contained within said received packet.

10. The method of claim 6, wherein said predetermined number of tries is less than or equal to seven.

11. The method of claim 6, said method further comprising the act of transmitting a join request on said bus when said first condition has been met.

14. The device of claim 1, wherein said means for joining a candidate further comprises:

means for remotely arbitrating for control of a bus segment to join with said bus;

means for waiting for a predetermined period of time;

means for issuing a short bus reset if said arbitration is won within said predetermined period of time; and

means for issuing a long bus reset if arbitration is not won within said predetermined period of time.

15. The device of claim 14, wherein said predetermined period of time is less than or equal to the time period of one asynchronous packet on said bus.

12. In a system having at least one full-duplex bus having a plurality of nodes, wherein at least one of the nodes has an untested connection, a device for preventing loops comprising:

means for selecting an untested connection by at least one of the plurality of nodes to join said at least one bus;

means for establishing dominance of said at least one full-duplex bus by said one of said plurality of nodes which selected said untested connection;

means for testing for loops through said untested connection by said at least one of said plurality of nodes; and

means for joining said untested connection to said at least one of said full-duplex bus by said at least one of said plurality nodes if no loops are found in said bus.

13. The device of claim 12, further comprising means for selecting, by all nodes with at least one untested connection, at least one untested connection.

16. The device of claim 12, wherein said means for joining a candidate further comprises:

means for instructing a PHY on a remote end of a candidate connection to arbitrate for control of a bus segment to join with said bus;

means for determining whether said remote PHY wins arbitration within a predetermined period of time;

means for issuing a short bus reset if said arbitration is won within said predetermined period of time; and

means for issuing a long bus reset if arbitration is not won within said predetermined period of time.

17. The device of claim 12, wherein said means for establishing dominance of said bus by said candidates further comprises:

means for selecting a candidate by arbitrating for control of said bus;

means for transmitting a packet containing a unique identifier on said bus;

means for listening for packets received on said bus;

means for establishing dominance if the received packet meets a first condition;

means for dropping transmission of packets if said received packets meet a second condition; and

means for re-transmitting packets a predetermined number of times if the received packets meet a third condition.

18. The device of claim 17, wherein said first condition is met if said unique identifier contained within said transmitted packet is greater than said unique identifier contained within said received packet.

19. The device of claim 17, wherein said first condition is met if said unique identifier contained within said transmitted packet is less than said unique identifier contained within said received packet.

20. The device of claim 17, wherein said first condition is met if said unique identifier contained within said transmitted packet is equal to said unique identifier contained within said received packet.

21. The device of claim 17, wherein said predetermined number of tries is less than or equal to seven.

22. The device of claim 17, said method further comprising the act of transmitting a join request on said bus when said first condition has been met.

23. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to prevent loops on a full-duplex bus, said program comprising the acts of:

selecting an untested connection by at least one of the plurality of nodes to join said at least one bus;

establishing dominance of said at least one full-duplex bus by said one of said plurality of nodes which selected said untested connection;

testing for loops through said untested connection by said at least one of said plurality of nodes; and

joining said untested connection to said at least one of said full-duplex bus by said at least one of said plurality nodes if no loops are found in said bus.

24. The device of claim 23, wherein said act of joining a candidate further comprises:

remotely arbitrating for control of a bus segment to join with said bus;

waiting for a predetermined period of time;

issuing a short bus reset if said arbitration is won within said predetermined period of time; and

issuing a long bus reset if arbitration is not won within said predetermined period of time.

25. The device of claim 23, wherein said act of joining a candidate further comprises:

instructing a PHY on a remote end of a candidate connection to arbitrate for control of a bus segment to join with said bus;

determining whether said remote PHY wins arbitration within a predetermined period of time;

issuing a short bus reset if said arbitration is won within said predetermined period of time; and

issuing a long bus reset if arbitration is not won within said predetermined period of time.

26. The device of claim 23, wherein said act of establishing dominance of said bus by said candidates further comprises:

selecting a candidate by arbitrating for control of said bus;

transmitting a packet containing a unique identifier on said bus;

listening for packets received on said bus;

establishing dominance if the received packet meets a first condition;

dropping transmission of packets if said received packets meet a second condition; and

re-transmitting packets a predetermined number of times if the received packets meet a third condition.

27. The device of claim 26, wherein said first condition is met if said unique identifier contained within said transmitted packet is greater than said unique identifier contained within said received packet.

28. The device of claim 27, wherein said first condition is met if said unique identifier contained within said transmitted packet is less than said unique identifier contained within said received packet.

29. The device of claim 27, wherein said first condition is met if said unique identifier contained within said transmitted packet is equal to said unique identifier contained within said received packet.

30. The device of claim 27, wherein said predetermined number of tries is less than or equal to seven.