Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2002-02-26
2002-10-22
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S389000, C370S412000, C370S477000, C709S238000
Reexamination Certificate
active
06469983
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of data communication networks. More particularly, the present invention relates to methods and apparatus for scheduling data packets being sent within a data communication network.
BACKGROUND OF THE INVENTION
In a network that serves multiple user entities for various different purposes, it is important that the resources of the network are allocated appropriately. For example, it may be desired to dynamically allocate network resources between important or time-critical communications and those that are of lower importance or are less time-critical. This is to ensure that all communications reach their destinations when needed (or least to ensure that only low importance communications are subject to significant delays). For example, certain communications may be intolerant to delays, such as voice or video communications. In addition, certain network users may desire higher levels of network availability than others. Conversely, other users or other types of communications, such as batch file transfers, may be more tolerant of communication delays.
In network equipment, such as switches or routers, data packets are typically received and buffered prior to retransmission. The equipment then forwards the data packets to their appropriate destinations and may also perform other functions. For example, each piece of network equipment may allocate network resources to the various data communications it receives by appropriately scheduling its buffered packets before forwarding them. As computer networks evolve, there is an ever-increasing need to provide more bandwidth, lower latency, decreased costs and increased flexibility. Accordingly, there is a need to provide techniques for scheduling the retransmission of data packets that respond to these needs.
A conventional technique for scheduling retransmission of data packets involves the use of a heap data structure. Packets awaiting retransmission are placed in the heap and arranged in accordance with their priorities prior to retransmission. Further, network switches or routers typically provide multiple ports and/or transmission channels that may be used for re-transmitting packets received by the switch or router. Accordingly, what is needed is a technique for efficiently and flexibly scheduling retransmission of packets via several ports and communication channels. What is also needed is a technique for arranging the heap quickly and efficiently.
Aspects of the invention are variously directed to these ends.
SUMMARY OF THE INVENTION
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.
REFERENCES:
patent: 5699519 (1997-12-01), Shiobara
patent: 5844890 (1998-12-01), Delp et al.
patent: 5859835 (1999-01-01), Varma
patent: 6081507 (2000-06-01), Chao et al.
patent: 6115360 (2000-09-01), Quay et al.
patent: 6134217 (2000-10-01), Stiliadis
patent: 6173325 (2001-01-01), Kukreja
patent: 6205150 (2001-03-01), Rusczyk
patent: 6205151 (2001-03-01), Quay et al.
patent: 6256315 (2001-07-01), Barbas et al.
Davie, B. and Rekhter Y., “MPLS Technology and Applications,” Chapter 6 Quality of Service, Morgan Kaufman Publishers, pp. 147-170, (2000).
“Pipelined heap (priority queue) management for advanced scheduling in high-speed networks” by Ioannou, A.; Katevins, M. Communications, 2001. ICC 2001. IEEE International Conference on vol. 7, pages 2043-2047.*
“Design of a high-speed packet switch with fine-grained quality-of-service guarantees” by Bhagwan, R.; Lin, B. Communications, 2000. ICC 2000. 2000 IEEE International Conference on vol. 3, pp. 1430-1434.*
“Fast and scalable priority queue architecture for high-speed network switches” Bhagwan, R.; Lin, B. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, vol. 2, 2000, pp. 538-574.
Dharmapurikar Makarand
Narayana Pidugu
Hsu Alpus H.
Maple Optical Systems Inc.
Qureshi Afsar M.
Stevens & Westberg LLP
LandOfFree
Data packet transmission scheduling using a partitioned heap does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data packet transmission scheduling using a partitioned heap, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data packet transmission scheduling using a partitioned heap will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2929298