Work-conserving packet scheduling in network devices
US8230110B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 13, 2010 |
| Grant date | Jul 24, 2012 |
| Priority date | — |
| Expiry date | Jan 28, 2031 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L47/6275
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
In general, techniques are described for performing work conserving packet scheduling in network devices. For example, a network device comprising queues that store packets and a control unit may implement these techniques. The control unit stores data defining hierarchically-ordered nodes, which include leaf nodes from which one or more of the queues depend. The control unit executes first and second dequeue operations concurrently to traverse the hierarchically-ordered nodes and schedule processing of packets stored to the queues. During execution, the first dequeue operation masks at least one of the selected ones of the leaf nodes from which one of the queues depends based on scheduling data stored by the control unit. The scheduling data indicates valid child node counts in some instances. The masking occurs to exclude the node from consideration by the second dequeue operation concurrently executing with the first dequeue operation, which may preserve work in certain instances.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.