Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-10-21
2002-08-20
Yao, Kwang Bin (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06438135
ABSTRACT:
TECHNICAL FIELD
The present invention generally relates to network communications and, more particularly, to a method for the prioritized delivery of data packets from a queuing switch.
BACKGROUND ART
There is an ever present demand for the efficient delivery of data packets over computer networks and communication networks to establish a variety of quality of service (QOS) objectives. One QOS objective is to deliver high priority data packets either before or more efficiently than normal and low priority data packets. To achieve this goal, packet traffic shaping techniques and prioritization schemes have been developed.
Transport layer switches, or layer
4
switches, are typically used to implement most prioritization schemes. One common prioritization scheme is round robin (RR) queuing. In round robin queuing, a set of queues, or buffers, are established for temporarily holding data packets while the data packets await delivery. As an example, four queues may be established, including a high priority queue, a normal/high priority queue, a normal/low priority queue and a low priority queue. Each data packet is assigned to one of the queues based on a predetermined algorithm. The switch delivers messages from the queues based on a round robin approach. The round robin approach entails delivering a predetermined number of data packets from one of the queues, then delivering the same number of data packets from each of the other queues in descending order of priority before returning to the initial queue and repeating the process. Since the same number of packets are sent from each queue, the service ratio between queues is 1:1. This means that the high priority queue may not be serviced enough to deliver all the high priority packets while meeting QOS expectations.
Another common prioritization scheme is weighted round robin (WRR) queuing. Weighted round robin queuing uses the same basic structure as round robin queuing, but services the higher priority queues more frequently than the lower priority queues. A common implementation of WRR is to send a greater number of data packets from the higher priority queues than are sent from the lower priority queues for each round through the priority queues. It is common to have a service ratio between the high priority queue and the low priority queue of the foregoing round robin example to be set to 4:1, meaning that four packets are sent from the high priority queue for each packet sent from the low priority queue. However, in most actual data network environments, high priority data packets may constitute only about 20% of all data packets. The remaining 80% of the data packets have lower priorities. The result is that high priority data packets in this example are serviced with a priority which is effectively 16 times the priority of low priority packets. As a result, the lower priority queues are not serviced enough and the lower priority data packets may experience significant delay before being delivered. This means that QOS expectations for the lower priority data packets are not met.
Round robin and weighted round robin queuing schemes are usually implemented using hardware having a fixed procedure for delivering packets. Therefore, round robin and weighted round robin techniques are not able to adapt to any one particular network to optimize the packet delivery efficiency of the network.
SUMMARY OF THE INVENTION
The present invention provides a method for transmitting a plurality of data packets through a network. Each data packet is assigned to one of a plurality of priority queues and each priority queue has a service weight. A priority weight is assigned to each of the data packets and each priority weight has a value. Data packets are delivered from one of the priority queues until a service satisfied condition is met. The service satisfied condition is met when a combination of the values of the priority weights for each of the delivered data packets is equal to or is greater than the service weight assigned to the priority queue.
In accordance with another aspect of the invention, a queuing switch is provided. The queuing switch includes an incoming data packet processor which derives a queue assignment and a priority weight for each of a plurality of incoming data packets. Each priority weight has a value. The queuing switch also includes a plurality of priority queues and each priority queue has a service weight. The incoming data packet processor directs each data packet to one of the priority queues based on the queue assignment for each data packet. Data packets are delivered from a first one of the priority queues until a service satisfied condition is met. The service satisfied condition is met when a combination of the values of the priority weights for each of the delivered data packets is equal to or is greater than the service weight assigned to the first priority queue.
REFERENCES:
patent: 5487061 (1996-01-01), Bray
patent: 5870629 (1999-02-01), Borden et al.
patent: 5917822 (1999-06-01), Lyles et al.
patent: 5926459 (1999-07-01), Lyles et al.
patent: 6157654 (2000-12-01), Davis
patent: 6198723 (2001-03-01), Parruck et al.
patent: 6260073 (2001-07-01), Walker et al.
patent: 6317416 (2001-11-01), Giroux et al.
patent: 6385168 (2002-05-01), Davis et al.
Jones Prenell
Yao Kwang Bin
LandOfFree
Dynamic weighted round robin queuing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic weighted round robin queuing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic weighted round robin queuing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960314