Dynamically Adjustable Arbitration Scheme

• US 20100064072A1
• Filed: 09/09/2008
• Published: 03/11/2010
• Est. Priority Date: 09/09/2008
• Status: Abandoned Application

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Emulex Design & Manufacturing Corp. (Broadcom, Inc.)
• Inventors: Tang, John Sui-kei, Su, Sam Shan-Jan, Liu, Michael Yu, Jin, Daming
• Application Number:
  US12/207,380
• Publication Number:
  US 20100064072A1
• Time in Patent Office: Days
• US Class Current: 710/39
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence

Abstract

A network arbitration scheme is disclosed that manages device access fairness by selectively and dynamically increasing a requestor queue'"'"'s likelihood of being serviced. A requestor queue increases its service priority by duplicating a request entry onto a set of priority rings maintained by arbitration hardware in a host bus adapter. Duplication occurs when (1) a requestor'"'"'s queue fill count (the number of descriptors stored in the queue) exceeds a watermark level or (2) a requestor'"'"'s queue timer times out. In the case of time-out, the requester in the lower priority ring will duplicate itself in the higher priority ring. Because the arbitration hardware services requesters using a round robin selection scheme, the likelihood of a requestor queue being serviced increases as the number of its duplicate request entries on a priority ring increases. Upon being serviced, the requester is able to perform the requested action.

Claims

1. A method for managing device access fairness in a storage area network, comprising:

maintaining a plurality of requestor queues, each requester queue for storing descriptors representing access requests through a link associated with that requestor queue;

maintaining one or more priority rings, each priority ring containing a plurality of requestor slots for storing request entries from the requestor queues and managing device access fairness;

measuring a queue fill count of a particular requestor queue and comparing it to a watermark level; and

duplicating a request entry for the particular requestor queue on a priority ring if the queue depth exceeds the watermark level.

2. The method as recited in claim 1, further comprising:

maintaining a timer associated with particular requestor queue; and

duplicating a request entry for the particular requestor queue on a higher priority ring if the timer has timed out.

3. The method as recited in claim 2, wherein maintaining a timer associated with a particular requestor queue further comprises:

periodically decrementing the timer so long as the particular requestor queue contains at least one unserviced descriptor; and

determining that the timer has timed out when the timer'"'"'s value is equal to zero.

4. The method as recited in claim 2, wherein duplicating a request entry for the particular requester queue on the priority ring further comprises inserting a request entry into a first vacant slot of a lowest priority ring.

5. The method as recited in claim 2, further comprising:

locating a highest priority ring containing a duplicate request entry; and

selecting request entries in the located ring for servicing in a round robin manner.

6. The method as recited in claim 5, further comprising:

servicing a selected request entry;

eliminating any additional instantiations of the serviced request entry from any of the one or more priority rings;

moving a read pointer in the requestor queue associated with the serviced request entry to another unserviced descriptor, if any; and

resetting a timer associated with the requestor queue associated with the serviced request entry to a user-specified value if there is at least one unserviced descriptor still in the requestor queue.

7. A computer-readable storage medium storing program code for managing device access fairness in a storage area network, the program code for causing performance of a method comprising:

maintaining a plurality of requestor queues, each requester queue for storing descriptors representing access requests through a link associated with that requester queue;

maintaining one or more priority rings, each priority ring containing a plurality of requestor slots for storing request entries from the requester queues and managing device access fairness;

measuring a queue fill count of a particular requestor queue and comparing it to a watermark level; and

duplicating a request entry for the particular requestor queue on a priority ring if the queue depth exceeds the watermark level.

8. The computer-readable storage medium as recited in claim 7, the program code further for causing performance of a method comprising:

maintaining a timer associated with particular requestor queue; and

duplicating a request entry for the particular requester queue on a higher priority ring if the timer has timed out.

9. The computer-readable storage medium as recited in claim 8, wherein maintaining a timer associated with a particular requester queue further comprises:

periodically decrementing the timer so long as the particular requestor queue contains at least one unserviced descriptor; and

determining that the timer has timed out when the timer'"'"'s value is equal to zero.

10. The computer-readable storage medium as recited in claim 8, wherein duplicating a request entry for the particular requestor queue on the priority ring further comprises inserting a request entry into a first vacant slot of a lowest priority ring.

11. The computer-readable storage medium as recited in claim 8, the program code further for causing performance of a method comprising:

locating a highest priority ring containing a duplicate request entry; and

selecting request entries in the located ring for servicing in a round robin manner.

12. The computer-readable storage medium as recited in claim 11, the program code further for causing performance of a method comprising:

servicing a selected request entry;

eliminating any additional instantiations of the serviced request entry from any of the one or more priority rings;

moving a read pointer in the requester queue associated with the serviced request entry to another unserviced descriptor, if any; and

resetting a timer associated with the requestor queue associated with the serviced request entry to a user-specified value if there is at least one unserviced descriptor still in the requestor queue.

13. A system for managing device access fairness in a storage area network, comprising:

a plurality of requester queues, each requester queue configured for storing descriptors representing access requests through a link associated with that requestor queue;

an arbiter containing one or more priority rings, each priority ring containing a plurality of requester slots and configured for storing request entries from the requester queues and managing device access fairness; and

logic within each of the plurality of requestor queues, the logic configured for measuring a queue depth of the requestor queue, comparing the queue depth to a watermark level, and duplicating a request entry for the particular requestor queue on a priority ring if the queue depth exceeds the watermark level.

14. The system as recited in claim 13, each requestor queue further comprising a timer, and wherein the logic within each requester queue is configured for duplicating a request entry for the requester queue on a higher priority ring if the timer has timed out.

15. The system as recited in claim 14, wherein the logic within each requestor queue is further configured for:

periodically decrementing the timer so long as the requestor queue contains at least one unserviced descriptor; and

determining that the timer has timed out when the timer'"'"'s value is equal to zero.

16. The system as recited in claim 14, wherein the logic within each requestor queue is further configured for inserting a request entry into a first vacant slot of a lowest priority ring.

17. The system as recited in claim 14, wherein the arbiter is configured for:

locating a highest priority ring containing a duplicate request entry; and

selecting request entries in the located ring for servicing in a round robin manner.

18. The system as recited in claim 17, the logic within each requestor queue further configured for, after servicing a selected request entry:

eliminating any additional instantiations of the serviced request entry from any of the one or more priority rings;

moving a read pointer in the requester queue associated with the serviced request entry to another unserviced descriptor, if any; and

resetting a timer associated with the requestor queue associated with the serviced request entry to a user-specified value if there is at least one unserviced descriptor still in the requester queue.

19. The system as recited in claim 13, the system incorporated into a host bus adapter (HBA).

20. The system as recited in claim 19, the HBA incorporated into a server.

21. The system as recited in claim 20, the server incorporated into a storage area network (SAN).