Data packet transmission scheduling

Details Data packet transmission scheduling Data packet transmission scheduling

2002-02-26

2003-06-10

Kizou, Hassan (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S428000

Reexamination Certificate

active

06577635

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. Accordingly, what is needed is a technique for filling and emptying the heap quickly and efficiently. What is further needed is a technique for quickly and efficiently arranging the heap.
Aspects of the invention are variously directed to these ends.
SUMMARY OF THE INVENTION
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 scheduling heap data structure. Packets percolate up through the heap by comparing their assigned values in pairs. Operations in the heap may be pipelined so as to provide for high-speed sorting. Thus, a few relatively simple operations can be performed repeatedly to quickly percolate packets up through 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. A binary number may represent each position in the heap. To traverse the heap, the relative movements necessary to move from one position to another may be determined from the binary number. This is useful to quickly and efficiently traverse the heap.


REFERENCES:
patent: 5699519 (1997-12-01), Shiobara
patent: 5844890 (1998-12-01), Delp et al.
patent: 5859835 (1999-01-01), Varma et al.
patent: 6081507 (2000-06-01), Chao et al.
patent: 6115360 (2000-09-01), Quay et al.
patent: 6134217 (2000-10-01), Stiliadi et al.
patent: 6173325 (2001-01-01), Kukreja
patent: 6205150 (2001-03-01), Ruszczyk
patent: 6205151 (2001-03-01), Quay et al.
patent: 6256315 (2001-07-01), Barbas et al.
“Pipelined heap (priority queue) management for advanced scheduling in high-speed networks” by Ioannou, A.; Katevenis, M. Communications, 2001. ICC 2001. IEEE International Conference on, vol. 7, pp. 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, vol. 3, pp. 1430-1434.*
“Fast and scalable priority queue architecture for high-speed network switches” by Bhagwan, R. and Lin, B. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, vol.: 2, 2000 pp. 538-547 vol. 2.*
Davie, B. and Rekhter Y., “MPLS Technology and Applications,”Chapter 6 Quality of Service, Morgan Kaufman Publishers, pp. 147-170, (2000).

Affiliated with

Also associated with

Rating

Data packet transmission scheduling 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data packet transmission scheduling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3133700