Method and system for arbitrating path contention in a crossbar interconnect network

• US 6,230,229 B1
• Filed: 12/19/1997
• Issued: 05/08/2001
• Est. Priority Date: 12/19/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Storage Technologies Corporation (Oracle Corporation)
• Inventors: Van Krevelen, Christopher J., Nelson, Reed S., Hodapp, Don J. Jr., Hamre, John D.
• Primary Examiner(s): Beausoleil, Robert
• Assistant Examiner(s): PHAN, RAYMOND NGAN
• Application Number:
  US08/994,527
• Time in Patent Office: 1,236 Days
• Field of Search: 395/306-312, 395/282-283, 395/284-285, 395/287-298, 395/840-848, 395/856-861, 710/240-244
• US Class Current: 710/317
• CPC Class Codes: G06F 13/36 for access to common bus or bus system

Abstract

A method and system for transmitting data among a plurality of cards in a crossbar interconnect network having a plurality of cards each having source paths and destination paths utilizes a plurality of source arbitrators and a plurality of destination arbitrators each associated with the cards. The source arbitrators generate connection request commands from the source paths requesting access to a desired destination path and broadcasts the request for receipt by all of the destination arbitrators. The destination arbitrator associated with the desired destination path captures the connection request command and processes the command based on whether or not the desired destination path is busy. If the desired destination path is not busy, the destination arbitrator generates a connection command requesting a connection be made between the source path and the desired destination path. If the desired destination path is busy, the destination arbitrator stores the connection request command in one of a plurality of buffers until the desired destination path becomes available.

Claims

1. A method for transmitting data among a plurality of cards in a crossbar interconnect network, each of the plurality of cards having source paths for originating the data and destination paths for receiving the data, the method comprising:

generating a connection request command from one of the source paths requesting access to a desired one of the destination paths;

capturing the connection request command at the desired destination path;

generating a connection command from the desired destination path for connecting the one of the source paths to the desired destination path if the desired destination path is not busy;

storing the connection request command from each of the source paths associated with each of the plurality of cards at the desired destination path if the desired destination path is busy;

continuously monitoring the desired destination path to determine when the desired destination path is no longer busy; and

generating a second connection command from the desired destination path based on the connection request command when the desired destination path is no longer busy.

2. The method as recited in claim 1 wherein generating the connection command further includes transmitting the data from the one of the source paths to the desired destination path.

3. The method as recited in claim 1 wherein generating the second connection command includes determining a priority of the connection request command stored in the request buffer.

4. The method as recited in claim 2 wherein the method further comprises:

determining if any additional connection requests relating to the data exist prior to transmitting the data; and

if so, generating corresponding connection request commands from the one of the source paths requesting access to additional destination paths.

5. The method as recited in claim 1 wherein the connection request command is stored in a first-in first-out manner.

6. The method as recited in claim 2 wherein transmitting the data includes:

determining if the desired destination path is almost full; and

if so, generating a pause command for receipt by the one of the source paths instructing the one of the source paths to stop transmitting the data.

7. The method as recited in claim 2 wherein transmitting the data further includes:

determining if a second one of the source paths is requesting access to the desired destination path upon completion of transmitting the data; and

if so, terminating the connection between the one of the source paths and the desired destination path so as to allow the second one of the source paths access to the desired destination path.

8. The method as recited in claim 6 further comprising generating a resume command for receipt by the one of the source paths when the desired destination path is no longer almost full, the resume command instructing the one of the source paths to resume transmitting the data.

9. The method as recited in claim 7 wherein the step of determining if a second one of the source paths is requesting access to the desired destination path occurs when the end of a frame of data is encountered.

10. The method as recited in claim 7 further comprising holding the connection between the one of the source paths and the desired destination path if it is determined that no other source paths are requesting access to the desired destination path.

11. A system for transmitting data among a plurality of cards in a crossbar interconnect network, each of the plurality of cards having source paths for originating the data and destination paths for receiving the data, the system comprising:

a source arbitrator associated with each of the cards and in communication with each of the source paths of the associated card for generating a connection request command from one of the source paths requesting access to a desired destination path;

a destination arbitrator associated with each of the cards and in communication with each of the destination paths for capturing the connection request command at the desired destination path, processing the connection request command based on whether or not the desired destination path is busy, and continuously monitoring the desired destination path to determine when the desired destination path is no longer busy; and

a plurality of request buffers corresponding to each of the destination paths, wherein the destination arbitrator, in processing the connection request command, stores the connection request command in the request buffer corresponding to the desired destination path if the desired destination path is busy.

12. The system as recited in claim 11 further comprising a switch in communication with each of the destination arbitrators and wherein the destination arbitrator, in processing the connection request command, is further operative to generate a connection command for receipt by the switch if the desired destination path is not busy, and wherein the switch connects the one of the source paths to the desired destination path in response to the connection command so as to allow the one of the source paths to transmit the data.

13. The system as recited in claim 11 wherein each of the request buffers has a depth large enough to store the connection request commands from each of the source paths associated with each of the plurality of cards so as to fairly allocate the desired destination path.

14. The system as recited in claim 11 wherein the destination arbitrator, in continuously monitoring the desired destination path, is further operative to generate a second connection command based on the connection request command stored in the request buffer associated with the desired destination path when the desired destination path is no longer busy.

15. The system as recited in claim 11 wherein each of the request buffers is a first-in first-out buffer.

16. The system as recited in claim 12 wherein the source arbitrator generates additional connection request commands from the one of the source paths requesting access to additional desired destination paths prior to transmitting the data.

17. The system as recited in claim 12 further comprising a destination buffer corresponding to each of the destination paths and wherein the destination arbitrator is further operative to determine if the destination buffer associated with the desired destination path is almost full and, if so, generate a pause command for receipt by the one of the source paths instructing the one of the source paths to stop transmitting the data.

18. The system as recited in claim 14 wherein the destination arbitrator, in generating the second connection command is further operative to determine a priority of the connection request command stored in the request buffer associated with the desired destination path.

19. The system as recited in claim 12 wherein the source arbitrator is further operative to determine if a second one of the source paths is requesting access to the desired destination path after transmission of the data and to generate a connection termination command if a second one of the source paths is requesting access to the desired destination path.

20. The system as recited in claim 17 wherein the destination arbitrator is further operative to generate a pause command for receipt by the one of the source paths when the destination buffer is no longer almost full, the resume command instructing the one of the source paths to resume transmitting the data.

21. The system as recited in claim 18 wherein each of the request buffers include a high priority request buffer for storing high priority requests.

22. The system as recited in claim 18 wherein each of the request buffers include a low priority request buffer for storing low priority requests.

23. The system as recited in claim 18 wherein each of the request buffers include a free path request buffer for storing free path requests requesting access to any available destination path on a particular card.

24. A scaleable apparatus for transmitting data among a plurality of cards in a crossbar interconnect network, each of the plurality of cards having source paths for originating the data and destination paths for receiving the data, the apparatus comprising:

each of the cards including a source arbitrator in communication with each of the source paths and a destination arbitrator in communication with each of the destination paths, each of the destination arbitrators including a request buffer for each of the destination paths, the source arbitrators generating a connection request command for each of the source paths requesting access to a desired one of the destination paths, and the destination arbitrators capturing the connection request commands directed to any of the destination paths associated with its respective card, storing the connection request commands in the request buffer associated with the desired destination path if the desired destination path is busy, continuously monitoring the desired destination path to determine when the desired destination path is no longer busy, and generating connection commands when the desired destination path is not busy so that data may be transmitted;

a communication bus coupling each of the source arbitrators with each of the destination arbitrators, the communication bus for receiving the connection request commands from each of the source arbitrators and broadcasting the connection request commands for receipt by each of the destination arbitrators and for receiving and broadcasting the connection commands from each of the destination arbitrators; and

a switch connected to each of the source paths and each of the destination paths and the communication bus for connecting each of the source paths with a corresponding desired destination path upon receipt of a corresponding connection command.

25. The apparatus as recited in claim 24 wherein the communication bus includes:

a request bus for receiving and broadcasting the connection request commands; and

a connect bus for receiving and broadcasting the connection commands.

26. The apparatus as recited in claim 24 further comprising:

an arbitration bus controller coupled to each of the source arbitrators and each of the destination arbitrators for determining when each of the source arbitrators and each of the destination arbitrators may transmit a connection request command and a connection command, respectively.

27. The apparatus as recited in claim 24 wherein each of the request buffers has a depth large enough to store the connection request commands from each of the source paths associated with each of the plurality of cards so as to fairly allocate the desired destination path.

28. The apparatus as recited in claim 24 wherein each of the request buffers include priority buffers to determine a priority of the stored connection command associated with the desired destination buffer.

29. The apparatus as recited in claim 24 wherein the source arbitrators generate additional connection request commands for each of the source paths requesting access to additional destination paths prior to transmitting the data.

30. The apparatus as recited in claim 24 wherein each of the destination paths include a destination buffer and wherein each of the destination arbitrators are operative to determine if the destination buffer associated with the desired destination path is almost full and, if so, generate a pause command by receipt by the source path transmitting the data instructing the source path to stop transmitting data.

31. The apparatus as recited in claim 24 wherein each of the source arbitrators is further operative to determine if another one of the source paths is requesting access to the desired destination path based on the connection request commands broadcast by the communication bus and, if so, to generate a connection termination command after transmitting the data.

32. The apparatus as recited in claim 28 wherein the priority buffers include a high priority request buffer for storing high priority requests.

33. The apparatus as recited in claim 28 wherein the priority buffers include a low priority request buffer for storing low priority requests.

34. The apparatus as recited in claim 28 wherein the priority buffers include a free path request buffer for storing free path requests requesting access to any available destination path.

35. The apparatus as recited in claim 28 wherein each of the request buffers is a first-in first-out buffer.

36. The apparatus as recited in claim 30 wherein each of the destination arbitrators are further operative to transmit a resume command to the source path upon the destination buffer no longer being almost full.