Coordinated queuing between upstream and downstream queues in a network device

Abstract

A system determines a scheduling value based on a current length of a downstream queue in a network device. The system sends the scheduling value from the downstream queue to an upstream queue and schedules dequeuing of one or more data units, destined for the downstream queue, from the upstream queue based on the scheduling value.

What is claimed: 
     
       1. A device comprising:
 a first upstream queue to queue a first data unit and a second data unit; 
 a first downstream queue; and 
 a scheduler to:
 determine a first scheduling value, associated with the first downstream queue, based on:
 a first priority value associated with the first downstream queue, 
 a maximum size of the first downstream queue, and 
 a fill level of the first downstream queue prior to the first upstream queue dequeuing the first data unit or the second data unit, 
 
 cause, based on the first scheduling value, the first data unit to be transferred from the first upstream queue to the first downstream queue via an interconnect,
 the first downstream queue buffering the first data unit for transmission toward a destination, 
 
 determine an updated first scheduling value based on:
 the first priority value associated with the first downstream queue, 
 the maximum size of the first downstream queue, and 
 an updated fill level of the first downstream queue after the first downstream queue buffers the first data unit and prior to the transmission of the first data unit toward the destination, and cause 
 the second data unit to be transferred, via the interconnect, from the first upstream queue to the first downstream queue when a difference between the updated first scheduling value and the first scheduling value is greater than a particular threshold, or 
 the second data unit to be transferred, via the interconnect, from the first upstream queue to the first downstream queue, when:
 the difference between the updated first scheduling value and the first scheduling value is not greater than the particular threshold, and 
 a last notification, associated with the first downstream queue receiving data, is not associated with a timeout. 
 
 
 
 
     
     
       2. The device of  claim 1 , further comprising:
 a second upstream queue to queue a third data unit, 
 where the scheduler is further to:
 cause, based on the first scheduling value, the third data unit to be transferred, via the interconnect, from the second upstream queue to the first downstream queue, and 
 where the updated fill level of the first downstream queue is further based on the first downstream queue buffering the third data unit. 
 
 
     
     
       3. The device of  claim 1 , further comprising:
 a second downstream queue, 
 where the scheduler is further to:
 determine a second scheduling value based on:
 a priority value associated with the second downstream queue, 
 a maximum size of the second downstream queue, and 
 a fill level of the second downstream queue prior to the first upstream queue dequeuing the first data unit, and 
 
 
 where the scheduler, when causing the first data unit to be transferred, is further to:
 determine to transfer the first data unit to the first downstream queue and not to the second downstream queue based on the first scheduling value and the second scheduling value. 
 
 
     
     
       4. The device of  claim 1 , where:
 the first upstream queue is associated with an ingress card, and 
 the first downstream queue is associated with an egress card. 
 
     
     
       5. The device of  claim 1 , where the scheduler is further to:
 monitor the fill level associated with the first downstream queue, and 
 determine the updated fill level of the first downstream queue based on monitoring the fill level. 
 
     
     
       6. The device of  claim 3 , where the second scheduling value is associated with a particular value when the fill level of the second downstream queue indicates that the second downstream queue is substantially full, and
 where the scheduler, when determining to transfer the first data unit to the first downstream queue and not to the second downstream queue, is further to:
 bypass the second downstream queue based on determining that the second scheduling value is associated with the particular value. 
 
 
     
     
       7. The device of  claim 3 , where the scheduler, when determining to transfer the first data unit to the first downstream queue and not the second downstream queue, is further to:
 compare the first scheduling value and the second scheduling value, and 
 determine, based on comparing the first scheduling value and the second scheduling value, that the second downstream queue is more full than the first downstream queue. 
 
     
     
       8. A method comprising:
 determining, by a network device, a first scheduling value, associated with a first downstream queue, based on:
 a first priority value associated with the first downstream queue, 
 a maximum size of the first downstream queue, and 
 a fill level of the first downstream queue prior to a first upstream queue dequeuing a first data unit; 
 
 causing, by the network device and based on the first scheduling value, the first data unit to be transferred from the first upstream queue to the first downstream queue via an interconnect,
 the first downstream queue buffering the first data unit for transmission toward a destination; 
 
 determining, by the network device, an updated first scheduling value based on:
 the first priority value associated with the first downstream queue, 
 the maximum size of the first downstream queue, and 
 an updated fill level of the first downstream queue after the first downstream queue buffers the first data unit and prior to the transmission of the first data unit toward the destination; and 
 
 causing, by the network device, a second data unit enqueued in the first upstream queue to be transferred, via the interconnect, from the first upstream queue to the first downstream queue when:
 a difference between the updated first scheduling value and the first scheduling value is greater than a particular threshold; or 
 the difference between the updated first scheduling value and the first scheduling value is not greater than the particular threshold, and a last notification, associated with the first downstream queue receiving data, is not associated with a timeout. 
 
 
     
     
       9. The method of  claim 8 , further comprising:
 causing, based on the first scheduling value, a third data unit, enqueued at a second upstream queue, to be transferred from the second upstream queue to the first downstream queue,
 the updated fill level of the first downstream queue being further based on the first downstream queue buffering the third data unit. 
 
 
     
     
       10. The method of  claim 8 , further comprising:
 determining a second scheduling value, associated with a second downstream queue, based on:
 a priority value associated with the second downstream queue, 
 a maximum size of the second downstream queue, and 
 a fill level of the second downstream queue prior to the first upstream queue dequeuing the first data unit, and 
 
 where causing the first data unit to be transferred further includes:
 determining to transfer the first data unit to the first downstream queue and not to the second downstream queue based on the first scheduling value and the second scheduling value. 
 
 
     
     
       11. The method of  claim 10 , where the second scheduling value is associated with a particular value when the fill level of the second downstream queue indicates that the second downstream queue is substantially full, and
 where determining to transfer the first data unit to the first downstream queue and not to the second downstream queue includes:
 bypassing the second downstream queue based on determining that the second scheduling value is associated with the particular value. 
 
 
     
     
       12. The method of  claim 10 , where the first scheduling value is associated with a particular value when the fill level of the first downstream queue indicates that the first downstream queue is substantially empty, and
 where determining to transfer the first data unit to the first downstream queue and not to the second downstream queue includes:
 transferring the first data unit to the first downstream queue based on determining that the first scheduling value is associated with the particular value. 
 
 
     
     
       13. The method of  claim 10 , where determining to transfer the first data unit to the first downstream queue and not to the second downstream queue includes:
 comparing the first scheduling value and the second scheduling value, and 
 determining, based on comparing the first scheduling value and the second scheduling value, that the second downstream queue is more full than the first downstream queue. 
 
     
     
       14. The method of  claim 8 , where:
 the first upstream queue is associated with an ingress card, and 
 the first downstream queue is associated with an egress card. 
 
     
     
       15. A non-transitory computer-readable medium to store instructions, the instructions comprising:
 one or more instructions that, when executed by one or more devices, cause the one or more devices to:
 determine a first scheduling value, associated with a first downstream queue, based on:
 a first priority value associated with the first downstream queue, 
 a maximum size of the first downstream queue, and 
 a fill level of the first downstream queue prior to a first upstream queue dequeuing a first data unit; 
 
 cause, based on the first scheduling value, the first data unit to be transferred from the first upstream queue to the first downstream queue via an interconnect,
 the first downstream queue buffering the first data unit for transmission toward a destination; 
 
 determine an updated first scheduling value based on:
 the first priority value associated with the first downstream queue, 
 the maximum size of the first downstream queue, and 
 an updated fill level of the first downstream queue after the first downstream queue buffers the first data unit and prior to the transmission of the first data unit toward the destination; and 
 
 cause a second data unit enqueued in the first upstream queue to be transferred, via the interconnect, from the first upstream queue to the first downstream queue when:
 a difference between the updated first scheduling value and the first scheduling value is greater than a particular threshold; or 
 the difference between the updated first scheduling value and the first scheduling value is not greater than the particular threshold, and a last notification, associated with the first downstream queue receiving data, is not associated with a timeout. 
 
 
 
     
     
       16. The non-transitory computer-readable medium of  claim 15 , where the instructions further comprise:
 one or more instructions to:
 cause, based on the first scheduling value, a third data unit, enqueued at a second upstream queue, to be transferred from the second upstream queue to the first downstream queue, 
 where the updated fill level of the first downstream queue is further based on the first downstream queue buffering the third data unit. 
 
 
     
     
       17. The non-transitory computer-readable medium of  claim 15 , where the instructions further comprise:
 one or more instructions to:
 determine a second scheduling value, associated with a second downstream queue, based on:
 a priority value associated with the second downstream queue, 
 a maximum size of the second downstream queue, and 
 a fill level of the second downstream queue prior to the first upstream queue dequeuing the first data unit, and 
 
 
 where the one or more instructions to cause the first data unit to be transferred further include:
 one or more instructions to determine to transfer the first data unit to the first downstream queue and not to the second downstream queue based on the first scheduling value and the second scheduling value. 
 
 
     
     
       18. The non-transitory computer-readable medium of  claim 17 , where the second scheduling value is associated with a particular value when the fill level of the second downstream queue indicates that the second downstream queue is substantially full, and
 where the one or more instructions to determine to transfer the first data unit to the first downstream queue and not to the second downstream queue include:
 one or more instructions to bypass the second downstream queue based on determining that the second scheduling value is associated with the particular value. 
 
 
     
     
       19. The non-transitory computer-readable medium of  claim 17 , where the first scheduling value is associated with a particular value when the fill level of the first downstream queue indicates that the first downstream queue is substantially empty, and
 where the one or more instructions to determine to transfer the first data unit to the first downstream queue and not to the second downstream queue include:
 one or more instructions to transfer the first data unit to the first downstream queue based on determining that the first scheduling value is associated with the particular value. 
 
 
     
     
       20. The non-transitory computer-readable medium of  claim 17 , where the one or more instructions to determine to transfer the first data unit to the first downstream queue and not to the second downstream queue include:
 one or more instructions to:
 compare the first scheduling value and the second scheduling value, and 
 determine, based on comparing the first scheduling value and the second scheduling value, that the second downstream queue is more full than the first downstream queue.