Data packet transmission scheduling

The method according to claim 4, further comprising performing a reinsert operation in the heap data structure comprising inserting a scheduling value in a position emptied by retransmission of a corresponding data packet and percolating the heap.

The method according to claim 5, wherein when a new scheduling value is available, said reinsert operation comprises inserting the new scheduling value into the emptied position.

A method of scheduling data packet transmission in a data communication network including, when a new scheduling value is available, performing a reinsert operation in a scheduling heap data structure, said reinsert operation comprising inserting the new scheduling value in a position emptied by retransmission of a corresponding data packet and percolating the heap, and when said new scheduling value is not available, said reinsert operation comprising moving a scheduling value at a position at the bottom of heap to the emptied position and percolating the heap.

A system for scheduling data packet transmission comprising:

• a scheduling heap data structure having a plurality of levels for storing scheduling values for data packets according to their relative priorities;
• and
• a queue controller coupled to the data structure for manipulating scheduling values in the heap wherein said queue controller performs an insert operation at a level in heap by comparing a scheduling value assigned to a first data packet to a scheduling value assigned to a second data packet at the level, placing a higher priority one of the compared values in the level, and retaining the lower priority of the compared values to be placed elsewhere in the heap and wherein said queue controller repeats said insert operation at the level by comparing a scheduling value assigned to a third data packet to the higher priority one of the compared values, while simultaneously comparing at a next lower level in the heap, the lower priority of the compared values to a scheduling value assigned to a fourth data packet at the lower level in the heap.

A system for scheduling data packet transmission comprising:

• a scheduling heap data structure having a plurality of levels for storing scheduling values for data packets according to their relative priorities;
• and
• a queue controller coupled to the data structure for manipulating scheduling values in the heap wherein when a new scheduling value is available said queue controller performs a reinsert operation in the heap, said reinsert operation comprising inserting the new scheduling value in a position emptied by retransmission of a corresponding data packet and percolating the heap, and when said new scheduling value is not available, said reinsert operation comprising moving a scheduling value at a position at the bottom of heap to the emptied position and percolating the heap.

A system for scheduling data packet transmission comprising

• a scheduling heap data structure having a plurality of levels for storing scheduling values for data packets according to their relative priorities, wherein a binary number is assigned to an empty position in the heap;
• and
• a queue controller coupled to the data structure for manipulating scheduling values in the heap, wherein the queue controller traverses the heap for comparing scheduling values by making a sequence of left and right directional moves according to a sequence of zeros and ones in the binary number.