Abstract:
There is provided a system and method of managing a multi-priority queue having a queue-fill reporter, a first predetermined queue-fill threshold for stopping the queue-fill reporter, a second and third predetermined queue-fill threshold for indicating that the queue-fill reporter can start reporting, and a first timer for allowing the queue-fill reporter to start reporting. Additional thresholds can be added for other priorities of traffic. A second clock can be linked to these additional thresholds. In one implementation only the second queue-fill threshold resets the timer and stars the reporter. In another implementation either the second queue-fill threshold or expiry of the timer can start the reporter and reset the timer.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    A claim of priority is made to U.S. Provisional Patent Application Ser. No. 60/824,880, entitled Method and Apparatus for Managing Queues, filed Sep. 7, 2006. 
     
     FIELD OF THE INVENTION 
       [0002]    The present invention relates to method and apparatus for managing queues and is particularly concerned with mitigating starvation of lower priority traffic. 
       BACKGROUND OF THE INVENTION 
       [0003]    Simulations of transactions between two peripheral component interconnect (PCI) blocks have shown that higher priority operations (writes) could starve lower priority operations (reads). This can be generalized to any network including a number of different buffers and a fabric or interconnect, feeding an egress buffer. A specific example of such a network is the input-buffered switch fabric (ISF). 
         [0004]    Referring to  FIG. 1   a  there is illustrated a known high/low priority queue. For the purposes of the present example assume a four-slot queue  10  having two priorities (High/Low). Two slots  12  are reserved for H or L priorities and two lots  14  are reserved for H priority packets only. The network  16  writes to the queue  10  and egress from the queue via an egress port  18 . 
         [0005]    Referring to  FIG. 1   b , when the egress port  18  is temporarily congested (no packets exit queue). The H or L slots  12  contain two L-priority packets  20  and  22  and the H-only slots  14  contain two H packets  24  and  26 . 
         [0006]    Referring to  FIG. 1   c , eventually egress flow resumes with sending highest priority packet  24  out of the queue. One H-priority packet  24  exits (labeled H 1 ). The network  16  sees one H-priority slot available. The network  16  feeding egress port  18  reorders its ingress or intermediate queues and refills the available slot with a H-priority packet  28  (H 3 ). Egress scheduling transmits packet  26  (H 2 ) out causing the network to send in another H-priority packet (not shown in the figure). Transmission of H-priority packets can continue for a long duration while L-packets are starved. 
         [0007]    Starvation happens because, in the present example, the egress arbitration scheme always chooses to send a High priority packet to fill an available slot in the queue  10 . 
         [0008]    Starvation depends on the protocol. 
         [0009]    SRIO
       If Receiver-based flow control, congestion causes retries. Retries cause egress queue re-ordering forcing transmission of high-priority packets.   If Transmitter-based flow control. Lack of available buffer at receiver will force re-ordering of transmitter egress queue. Because lack of retry, Transmitter based flow control will cause fewer re-ordering events, thus reducing the probability of starvation.       
 
         [0012]    PCI to PCI Block communication
       Current PCI block mapping: Posted operations=priority 2 (Highest) Responses=priority 1 Read Requests=priority 0 (Lowest)   When Highest priority buffers are filled, Egress arbitration selects posted packets to comply with PCI-SIG specifications   This causes starvation of responses and read requests       
 
         [0016]    Referring to  FIG. 2   a  there is illustrated a known apparatus for managing the queue of  FIG. 1 . A thermometer circuit is added to the queue to prevent starvation. The thermometer circuit uses a stop report threshold  30  and a resume report threshold  32 , while a watermark  34  indicates a boundary between the H only slots  14  and the H or L slots  12 , as in  FIG. 1 . 
         [0017]    In operation, when the queue fill-level reaches the STOP_REPORT threshold  30 . The queue  10  stops reporting any newly available slots to network  16 , even if H-priority packets have exited egress port  18 . The RESUME_REPORT threshold  32  is positioned within “H or L” region  12  of queue  10 . As packets drain out of egress port  18 , fill-level of queue  10  decreases. Once fill-level reaches the RESUME_REPORT threshold  32 , the queue  10  reports all empty queue slots to the network  16 . Since the fill-level is within the “H or L” region, the network  16  does not re-order ingress queues. If L packet is head of line (HOL) in an ingress/intermediate queue, it is allowed to progress to the egress queue  10 , consequently no starvation of L priority packets occurs. However, use of a thermometer circuit can result in a deadlock condition in normal operation. 
         [0018]    Referring to  FIG. 2   b  there is illustrated the apparatus of  FIG. 2   a  in a filled condition. The H or L slots  12  contain two L-priority packets  20  and  22  and the H-only slots  14  contain two H packets  24  and  26 . Assume the egress port  18  is temporarily blocked causing an accumulation of packets L 1 , L 2 , H 1  and H 2 . This condition triggers the STOP_REPORT threshold  30 . Any egress of packets is not reported to network  16  until a fill level is at or below the RESUME_REPORT threshold  32 . 
         [0019]    In operation, by way of example, the following happens:
       H 1  leaves the queue  10  but egress not reported to network  16 . ISF thinks that the egress queue is full and does not replenish it.   H 2  leaves queue  10  but egress is not reported to ISF  16 . ISF thinks that the egress queue is full and does not replenish it. The queue may now be deadlocked, because L 2  or L 1  must egress before ISF  16  can send another packet (of H or L priorities). If the link-partner connected to the egress port  18  has no L-priority buffers to receive L 2  or L 1 , the link is deadlocked.       
 
         [0022]    The above illustrated scenario is a classic deadlock behavior that is explicitly called out in the SRIO and the PCI specifications:
       RapidIO Part 6: 1x/4x LP-Serial Physical Layer Specification Rev. 1.3 Page 92 Rule #7 &amp; following discussion.   PCI-2.3 Spec:Appendix E, Page 294-285 Rules #5, #6       
 
         [0025]    Although the examples refer to buffers for shared buses, the same logic applies to buffers in switched topologies. For example one may think of PCI Delayed Requests as L-priority packets and Posted Writes as H-priority packets. 
       SUMMARY OF THE INVENTION 
       [0026]    An object of the present invention is to provide an improved method and apparatus for managing queues. 
         [0027]    According to an aspect of the present invention there is provided an apparatus for managing a queue comprising a queue-fill reporter having a report state and a stop state, a first predetermined queue-fill threshold for causing the queue-fill reporter to enter the stop state, a second predetermined queue-fill threshold for causing the queue-fill reporter to enter the report state and a timer for causing, on expiry of a predetermined time period, the queue-fill reporter to enter the report state. 
         [0028]    According to another aspect of the present invention there is provided an apparatus for managing a multi-priority queue comprising a queue-fill reporter, a first predetermined queue-fill threshold for stopping the queue-fill reporter, a second and third predetermined queue-fill threshold for indicating that the queue-fill reporter can start reporting; and a first timer for allowing the queue-fill reporter to start reporting. 
         [0029]    According to a further aspect of the present invention there is provided a method of managing a queue comprising reporting queue-fill, stopping the queue-fill reporting on reaching a first predetermined queue-fill threshold and timing for a predetermined time period, restarting queue-fill reporting either on reaching a second predetermined queue-fill threshold or on expiry of the predetermined time period. 
         [0030]    According to another aspect of the present invention there is provided a method of managing a multi-priority queue comprising reporting queue-fill, stopping the queue-fill reporting on reaching a first predetermined queue-fill threshold and timing for a predetermined time period and restarting queue-fill reporting either on reaching a second predetermined queue-fill threshold, a third predetermined queue-fill threshold or on expiry of the predetermined time period. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0031]    The present invention will be further understood from the following detailed description with reference to the drawings in which: 
           [0032]      FIGS. 1   a ,  1   b , and  1   c  illustrate a known queue; 
           [0033]      FIGS. 2   a  and  2   b  illustrate a known apparatus for managing the queue of  FIGS. 1   a ,  1   b , and  1   c ; and 
           [0034]      FIG. 3  illustrates in an apparatus for managing queues in accordance with an embodiment of the present invention; 
           [0035]      FIG. 4  illustrates a state diagram for the apparatus of  FIG. 3 ; 
           [0036]      FIG. 5  illustrates a queue with a multi-priority thermometer circuit in accordance with an embodiment of the present invention; 
           [0037]      FIG. 6  illustrates a state diagram for recovery from a stop report state for the queue of  FIG. 5  in accordance with another embodiment of the present invention; 
           [0038]      FIG. 7  illustrates a state diagram for recovery from a stop report state for the queue of  FIG. 5  in accordance with a further embodiment of the present invention; and 
           [0039]      FIG. 8  illustrates a queue with a multi-priority thermometer circuit in accordance with another embodiment of the present invention 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0040]    Referring to  FIG. 3  there is illustrated an apparatus for managing queues in accordance with an embodiment of the present invention. The apparatus of  FIG. 3  includes a STOP_REPORT count down timer  40 . 
         [0041]    Referring to  FIG. 4  there is illustrated a state diagram for the apparatus of  FIG. 3 . The apparatus has two states a report all available slots state  42  and a stop report state  44 . 
         [0042]    In operation, once the STOP_REPORT threshold  30  is reached  46  the queue  10  enters STOP_REPORT state  44  and does not report empty queue slots to network  16 . Once STOP_REPORT state  44  is entered, the count down timer  40  is loaded and starts counting down. Once the count down timer  40  reaches zero  48 , the queue  10  exits the STOP_REPORT state  44  even if RESUME_REPORT threshold  32  has not been achieved. Once the queue  10  exits the STOP_REPORT state  44 , it reports all empty queue slots to network  16 . If deadlock had occurred, the STOP_REPORT count down timer  40  allows the queue  10  to exit the deadlock state by exiting the STOP_REPORT state  44 . 
         [0043]    Choosing a duration of STOP_REPORT count down timer is system dependent, but the following should be considered. If the duration is too short, then the queue  10  does not have a chance to reach the Resume_REPORT threshold  32 , consequently starvation may occur. If the duration is too long, then performance of the system may degrade. A suggested timer length is equal to time required to transmit the number of packets between the STOP_REPORT threshold  30  and the RESUME_REPORT threshold  32 , assuming that these are maximum length packets. Preferably the timer duration is programmable. A maximum timer value is in the same order as time required to clear the entire queue. 
         [0044]    Referring to  FIG. 5 , there is illustrated a queue with a multi-priority thermometer. The queue  50  includes three priorities: P 2  (highest), P 1  (middle) and P 0  (lowest). The queue is divided into P 2  only  52 , P 1  or P 2  region  54  and an any priority region  56 . Watermarks  58  and  60  (WP 1  and WP 0 ) respectively mark last buffer available to P 1  and P 0 . No watermark is required for P 2 . 
         [0045]    In operation, the queue  50  enters the STOP_REPORT state  44  when the P 0 _STOP_REPORT threshold  62  for the lowest priority is reached. In this case, a P 0 _STOP_REPORT  62  is the lowest priority threshold. The queue exits the STOP_REPORT state  44 , if: Buffer fill drops to P 0 _Resume_Report threshold  64  OR the count-down timer  65  expires. Note regarding relationship between WP and thermometer threshold:
       STOP_REPORT=WP+1   RESUME_REPORT=WP−1.       
 
         [0048]    Since there is only one STOP threshold  62  and one RESUME threshold  64 , there is only need for one timer. The P 0  timer  65  protects the entire queue from deadlock. 
         [0049]    Choosing a value of RESUME_REPORT. The thermometer circuit frees the buffers back to two possible sources: network or preceding FIFO 
         [0050]    Freeing buffers to network:
       Only ONE “buffer available” can be signaled back to network per clock cycle.   network takes two cycles to schedule next packet (three cycles if re-ordering is required).   If RESUME_REPORT=WP−1 is used, then the network of preceding queues may see only one or two buffers being released when it is scheduling.   This would force network to send in a High priority packet which would then again block transmission of any low-priority packets.   So, in this case, use must set RESUME_REPORT to the lowest number possible without causing a gap in the output       
 
         [0056]    Freeing buffers to preceding Queue
       All buffers should be freed in a single clock cycle   Can set RESUME_REPORT=WP−1 with no fear of starvation.       
 
         [0059]    Referring to  FIG. 6 , there is illustrated a state diagram for recovery from a stop report state for the queue of  FIG. 5  in accordance with another embodiment of the present invention. The state diagram of  FIG. 6  has three states REPORT ACCURATELY  66 , REPORT ACCURATELY UNTIL fill level=P 0  Resume Report  67  and STOP REPORT  68 . The queue enters  70  the STOP_REPORT state  68  and activates count-down timer  65  when:
       currently in REPORT state  66 , AND   buffer_fill=(P 0 _STOP_REPORT−1) and push (with no pop on same clk)       
 
         [0062]    The queue  50  exits STOP_REPORT state  68  and clears count-down timer  65  when: timer expires  72  OR buffer_fill=RESUME_REPORT threshold  74 . If the count-down timer  65  expires prior to reaching P 0 _RESUME_REPORT  64  then enter state  67  and do not reactivate thermometer again until you have reached P 0 _RESUME_REPORT  64 . 
         [0063]    The thermometer circuit is meant to avoid, but not prevent starvation. If the count-down timer  65  expires and the queue  50  has not reached P 0 _RESUME_REPORT threshold  64 , then the down-stream link must be congested. We do not want to re-arm the thermometer state machine under congestion conditions because we want to continue sending the high priority traffic. Re-arming the state-machine slows that traffic down due to the timer. Sending the high priority traffic should clear up outstanding operations at the endpoints. Clearing these outstanding operations allows low-priority traffic to flow again. 
         [0064]    Referring to  FIG. 7 , there is illustrated a state diagram for recovery from a stop report state for the queue of  FIG. 5  in accordance with a further embodiment of the present invention. The queue  50  enters  76  STOP_REPORT state  68  and activates the count-down timer  65  when:
       Currently in REPORT state  66  &amp; buffer_fill&gt;=(P 0 _STOP_REPORT−1) &amp; push (with no pop on same clk)       
 
         [0066]    The queue  50  exits  78  STOP_REPORT state  68  and clears count-down timer when: timer expires  76  OR buffer_fill=P 0 _RESUME_REPORT  78 . This means that if the count-down timer  65  expires prior to reaching P 0 _RESUME_REPORT the thermometer re-activates again (including Count-down timer) when a packet insertion into the queue causes the fill level to increase. 
         [0067]    If we do not re-arm the thermometer circuit then we risk starving P 0  (and maybe P 1 ) when there is congestion in the down-stream devices that prevent forward progress. 
         [0068]    Referring to  FIG. 8 , there is illustrated a queue with a multi-priority thermometer. The queue  50  includes three priorities: P 2  (highest), P 1  (middle) and P 0  (lowest). The queue is divided into P 2  only  52 , P 1  or P 2  region  54  and an any priority region  56 . Watermarks  58  and  60  (WP 1  and WP 0 ) respectively mark last buffer available to P 1  and P 0 . No watermark is required for P 2 . In addition to the P 0  thresholds of  FIG. 5 ,  FIG. 8  includes P 1  thresholds, P 1 _STOP_REPORT  66  and P 1 _RESUME_REPORT  68  and P 1 _RESUME_REPORT countdown timer  69 . 
         [0069]    In operation, multiple thresholds allow P 1  and P 2  traffic to progress while starving P 0  traffic. Multiple thresholds also ensure P 0  and P 1  traffic progresses in the absence of P 2  traffic. This is achieved by setting the P 0 _STOP_REPORT threshold at a higher queue fill that the P 1 _STOP_REPORT. By letting P 0  traffic through after the P 0 _RESUME_REPORT has been reached and until the P 1 _RESUME_REPORT has been reached and both timers reset. 
         [0070]    Having a P 1 _STOP_REPORT may seem redundant because to reach that threshold, one needs to have crossed the P 0 _STOP_REPORT threshold. However, one may wish to have multiple stop states corresponding to traffic priority. Having a P 1 _RESUME_REPORT protects P 1  from starvation by P 2 , but may allow P 1  and P 2  to starve P 0 . 
         [0071]    Referring to  FIG. 9 , there is illustrated a queue with a multi-priority thermometer. The queue  50  includes three priorities: P 2  (highest), P 1  (middle) and P 0  (lowest). The queue is divided into P 2  only  52 , P 1  or P 2  region  54  and an any priority region  56 . Watermarks  58  and  60  (WP 1  and WP 0 ) respectively mark last buffer available to P 1  and P 0 . No watermark is required for P 2 .  FIG. 9  includes P 1  thresholds, P 1 _STOP_REPORT  66  and P 1 _RESUME_REPORT  68  and a single RESUME REPORT countdown timer  70 . Operation is similar to that of  FIG. 8  except that the stop report thresholds share one countdown timer  70 , which is activated by either stop report threshold. 
         [0072]    Numerous modifications, variations and adaptations may be made to the particular embodiments described above without departing from the scope patent disclosure, which is defined in the claims.