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

• US 7,194,564 B2
• Filed: 12/21/2004
• Issued: 03/20/2007
• 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:
  US11/021,337
• Publication Number:
  US 20050117528A1
• Time in Patent Office: 819 Days
• Field of Search: 709220-222, 709/224, 709/232, 709/235, 709/238, 709/243, 710/100, 710300-302, 710/104, 710/107, 710305-306, 370216-222, 370241-242, 370254-256
• US Class Current: 710/104
• 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 apparatus is disclosed for preventing loops in a full-duplex bus. One method has the acts of: selecting at least two candidates to join said bus; establishing a dominant candidate from one of said at least two candidates; testing for loops in said bus; and joining said dominant candidate if no loops are found in said bus.

Another method has the acts of: selecting a plurality candidates to join said bus; establishing at least one dominant candidate; testing for loops in said bus; and joining said at least one dominant candidate if no loops are found in said bus. Alternative embodiments are shown that utilize unique identifiers to facilitate candidate selection and to establish dominance on the bus.

Claims

1. In a network of a plurality of nodes, each node in communication with other nodes in the network via a full-duplex communications bus, a method for performing loop breaking, the method comprising:

detecting which nodes from said plurality select an untested connection;

wherein said act of selecting comprises;

transmitting a request containing a unique identifier;

receiving requests transmitted by other candidates;

ignoring said received requests that meet a first condition;

abandoning the transmittal of further requests if said received requests meet a second condition and acknowledging the existence of said received requests; and

challenging the request if said received request meets a third condition;

testing for loops through said untested connection by said detected nodes; and

joining said untested connection to said full-duplex bus by said detected nodes if no loops are found in said bus.

2. The method of claim 1, wherein said first condition is met if said unique identifier contained within said transmitted request is greater than said unique identifier contained within said received request.

3. The method of claim 1, wherein said first condition is met if said unique identifier contained within said transmitted request is less than said unique identifier contained within said received request.

4. The method of claim 1, wherein said first condition is met if said unique identifier contained within said transmitted request is equal to said unique identifier contained within said received request.

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

arbitrating for control of 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.

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

7. In a network of a plurality of nodes, each node in communication with other nodes in the network via a full-duplex communications bus, a method for performing loop breaking, the method comprising:

detecting which nodes from said plurality select an untested connection;

wherein said act of detecting nodes 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;

designating the selected candidate as a dominant node 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;

testing for loops through said untested connection by said detected nodes; and

joining said untested connection to said full-duplex bus by said detected nodes if no loops are found in said bus.

8. The method of claim 7, 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.

9. The method of claim 7, 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.

10. The method of claim 7, 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.

11. The method of claim 7, wherein said predetermined number of tries is less than or equal to ten.

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

13. In a network comprising a plurality of nodes present in a full-duplex bus, a method for building a loop free bus, comprising:

determining which nodes from said plurality comprise an untested connection;

testing for loops if said detected nodes were to be joined to said full-duplex bus; and

joining said detected nodes to said full-duplex bus if no loops are found during said act of testing.

14. The method of claim 13, wherein said full-duplex bus comprises a serial communications bus.

15. The method of claim 13, wherein said act of determining which nodes from said plurality comprises an untested connection further comprises:

transmitting a candidate identifier message from a candidate node to a peer node;

transmitting a peer identifier message from said peer node to said candidate node; and

determining a relationship between a candidate identifier number present within said candidate identifier message and a peer identifier number present within said peer identifier message.

16. The method of claim 15, wherein said candidate identifier message further comprises an outbound service request.

17. The method of claim 16, wherein if said relationship indicates that said peer identifier number is greater than said candidate identifier number then said candidate node abandons any outbound service requests.

18. The method of claim 15, wherein if said relationship indicates that said peer identifier number is equal to said candidate identifier number then a random challenge is invoked.

19. In a network comprising a plurality of nodes in a full-duplex bus, at least one node comprising computer instructions which when executed, perform loop breaking, according to the method comprising:

selecting an untested connection in said plurality of nodes;

establishing at least one dominant node in said full-duplex bus;

testing for loops through said untested connection by said at least one dominant node; and

joining said untested connection to said full-duplex bus by said at least one dominant node if no loops are found during said act of testing.

20. The at least one node of claim 19, wherein said act of establishing at least one dominant node further comprises:

selecting a candidate by arbitrating for control of said bus;

transmitting a packet containing a transmitted unique identifier on said bus;

listening for one or more packets, each comprising a received unique identifier received on said bus;

establishing said candidate as a dominant node 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.

21. The at least one node of claim 20, 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.

22. The at least one node of claim 20, 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.

23. The at least one node of claim 20, 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.

24. The at least one node of claim 20, wherein said predetermined number of tries is less than or equal to ten.

25. The at least one node of claim 20, further comprising transmitting a join request on said bus when said first condition has been met.

26. A device, comprising a plurality of instructions which when executed by said device prevents loops in a full-duplex bus by performing the method, comprising:

selecting a plurality of candidate nodes to join said bus;

establishing at least one dominant candidate node;

testing for loops in said bus; and

joining said at least one dominant candidate node if no loops are found in said bus.

27. The device of claim 26, wherein said act of establishing at least one dominant candidate node comprises:

selecting a candidate by arbitrating for control of said bus;

transmitting a packet containing a transmitted unique identifier on said bus;

listening for packets containing a received unique identifier on said bus; and

establishing said candidate as said at least one dominant node if the received packet meets a first condition.

28. The device of claim 27, 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.

29. 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.

30. 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.

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

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

33. The device of claim 26, wherein said act of joining a candidate further comprises:

arbitrating for control of 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.

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