Data packet transmission scheduling using a partitioned heap

• US 6,469,983 B2
• Filed: 02/26/2002
• Issued: 10/22/2002
• Est. Priority Date: 02/26/2001
• Status: Expired due to Fees

• Current Assignee: Maple Optical Systems, Inc.
• Original Assignee: Maple Optical Systems, Inc.
• Inventors: Dharmapurikar, Makarand, Narayana, Pidugu
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US10/083,965
• Publication Number:
  US 20020118645A1
• Time in Patent Office: 238 Days
• Field of Search: 370/229, 370/131-232, 370/235, 370/389-392, 370/394, 370/399, 370/395.2, 370/395.41, 370/395.52, 370/395.53, 370/401-412, 370/419, 370/477, 340/825.02, 709/234, 709/238, 709/240
• US Class Current: 370/231
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

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.

Claims

1. A method of scheduling data packet transmission in a data communication network, comprising:

forming a scheduling heap data structure having a plurality of levels for storing scheduling values for data packets according to their relative priorities in which a highest level has a single position and each succeeding lower level has twice the number of positions as the preceding level; and

forming 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 of the heap data structure.

2. The method according to claim 1, further comprising assigning each logical heap to one of a plurality of communication channels.

3. The method according to claim 2, further comprising inserting a scheduling value for a received data packet into one of the logical heaps according the communication channel by which the data packet is received.

4. The method according to claim 1, further comprising performing an insert operation at a level in the heap data structure 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.

5. 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.

6. 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.

7. The method according to claim 5, wherein when a new scheduling value is not available, said reinsert operation comprises moving a scheduling value at a position at the bottom of heap to the emptied position.

8. The method according to claim 5, further comprising performing said reinsert and insert operations in accordance with a pipelined sequence at each level in the heap.

9. The method according to claim 8, comprising allocating operations in the pipelined sequence to each of the plurality of logical heaps based on a communication bandwidth assigned to the corresponding logical heap.

10. The method according to claim 9, wherein said operations are allocated in proportion to the bandwidth assigned to the corresponding logical heap.

11. The method according to claim 9, said pipelined sequence comprising at least one cycle for the reinsert operation, at least one cycle for the insert operation and at least one no-operation cycle.

12. The method according to claim 11, wherein when conditions for performing an insert or a reinsert operation are not satisfied, the operation is skipped during its corresponding cycle.

13. 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 in which a highest level has a single position and each succeeding lower level has twice the number of positions as the preceding level, the heap data structure including a plurality of logical heaps within the heap data structure, wherein a highest level of each logical heap is assigned to a level in the heap data structure that is lower than the highest level of the heap data structure;

and

a queue controller coupled to the data structure for manipulating scheduling values in the heap data structure.

14. The system according to claim 13, wherein each logical heap is assigned to one of a plurality of communication channels.

15. The system according to claim 14, wherein the queue controller inserts a scheduling value for a received data packet into one of the logical heaps according the communication channel by which the data packet is received.

16. The system according to claim 13, the queue controller performs an insert operation at a level in the heap data structure 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.

17. The system according to claim 16, wherein the queue controller performs a reinsert operation in the heap data structure by inserting a scheduling value in a position emptied by retransmission of a corresponding data packet and percolating the heap.

18. The system according to claim 17, wherein when a new scheduling value is available, said reinsert operation includes the queue controller inserting the new scheduling value into the emptied position.

19. The system according to claim 17, wherein when a new scheduling value is not available, said reinsert operation includes the queue controller moving a scheduling value at a position at the bottom of heap to the emptied position.

20. The system according to claim 17, wherein the queue controller performs said reinsert and insert operations in accordance with a pipelined sequence at each level in the heap.

21. The system according to claim 20, wherein the queue controller allocates operations in the pipelined sequence to each of the plurality of logical heaps based on a communication bandwidth assigned to the corresponding logical heap.

22. The method according to claim 21, wherein said operations are allocated in proportion to the bandwidth assigned to the corresponding logical heap.

23. The system according to claim 21, said pipelined sequence comprising at least one cycle for the reinsert operation, at least one cycle for the insert operation and at least one no-operation cycle.

24. The system according to claim 23, wherein when conditions for performing an insert or a reinsert operation are not satisfied, the operation is skipped during its corresponding cycle.