Data packet transmission scheduling using a partitioned heap

摘要

The present invention is directed toward methods and apparatus for data packet transmission scheduling using a partitioned scheduling heap data structure. The scheduling heap data structure has a plurality of levels for storing scheduling values for data packets according to their relative priorities. A highest level in the heap has a single position and each succeeding lower level has twice the number of positions as the preceding level. The data structure may be adapted to store a plurality of logical heaps within the heap data structure by assigning a highest level of each logical heap to a level in the heap data structure that is lower than the highest level. Thus, a single physical memory may be adapted to store plural logical heaps. This is useful because a single physical memory can be adapted to prioritize packets of various different transmission protocols and speeds.