DATA PACKET TRANSMISSION SCHEDULING

摘要

The present invention is directed toward data packet transmission scheduling. Scheduling values, such as priority or other scheduling criteria assigned to data packets, are placed in a heap data structure(700). Packets percolate up through the heap by comparing their assigned values in pairs(816). Operations in the heap may be pipelined so as to provide for high-speed sorting(1000). Thus, a few relatively simple operations can be performed repeatedly to quickly percolate packets up trough the heap. Another aspect of the invention provides for fast traversal of the scheduling heap data structure. The hierarchical heap may include a highest level having a single position and each succeeding lower level having twice the number of positions as the preceding level(700). A binary number may represent each position in the heap(806). To traverse the heap, the relative movements necessary to move from one position to another may be determined from the binary number(818).