Packet scheduling using dual weight single priority queue

Details Packet scheduling using dual weight single priority queue Packet scheduling using dual weight single priority queue

1999-08-28

2003-05-27

Olms, Douglas (Department: 2732)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S232000, C370S395400, C370S395420

Reexamination Certificate

active

06570883

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a packet switching network. More particularly, it relates to a packet switching device having a queuing system and a packet scheduler that together handle the traffic control and bandwidth management to support guaranteed quality of service.
2. Related Background Art
IP based networks have evolved from supporting traditional best effort, data centric services to support multiple service grades, multi-media networking services. There is an increased need for the packet-based networks to provide guaranteed quality of service. Providing guaranteed quality of service in packet-based networks requires the use of a packet scheduling system consisting of a queuing system and a packet scheduler. The queuing system allows different traffic streams to receive different service-quality treatments from the scheduler. There are many different kinds of scheduling systems today that support different flavors of quality of service. A desirable scheduling system has the following attributes, which are also indicators for quality of service (Quality of Service”):
(1) “Bandwidth Utilization”. The scheduling system must utilize bandwidth efficiently;
(2) “Traffic Flows Isolation”. Each traffic flow is isolated from the undesirable effect of other flows;
(3) “Scalability”. The scheduling system must support large number of traffic flows;
(4) “Real-time Priority”. Traffic flows with higher real time requirements should be forwarded before traffic flows with lower real time requirements; and
(5) “Fairness”. Priority and fairness are conflicting factors, yet a good scheduling system achieves a balance between Fairness and Priority.
Existing scheduling systems may be strong in one or more of the above five aspects, but none has been perfect in all five aspects. Round robin based scheduler has good fairness property, but lacks real-time priority, and the bandwidth utilization is potentially poor. Yet a simple priority based scheduler does not provide fairness, which will result in starvation. There are scheduling algorithms that address Bandwidth Efficiency, Flow Isolation, Fairness and Scalability such as Weighted Fair Queuing, Weighted Round Robin, Frame-Based Fair Queuing, and Starting Potential-Based Fair Queuing. But these algorithms do not address real-time support and neither do they provide flexibility in sharing excess bandwidth.
There are a few algorithms that address Real-Time support, along with Bandwidth Efficiency, Flow Isolation, Fairness and Scalability. Class Based Queuing is one of such algorithms. However, the issues of sharing available bandwidth are still not addressed. Class Based Queuing takes a hierarchical scheduling approach to provide a traffic control mechanism using Weighted Fair Queuing or Weighted Round Robin for guaranteed resource sharing on the base level. On a second level, it groups the flows into different priority categories, so that the flows queues with the highest priority are always considered first to be provided for bandwidth. This priority is important for a networking device to support multiple streams of data with different real time requirements such as voice, interactive data, and file transfer.
For example, U.S. Pat. No., 5,838,686 presents a scarce source allocating system as shown in FIG.
14
and
FIG. 15
that can well illustrate Class Based Queuing. As illustrated by the block diagram of a multiplexer system in
FIG. 14
, all signal paths are illustrated as single signal lines which however could carry multibit digital signals, either in parallel, in which case the signal paths would be composed of multiple signal lines, or serially, in which case the signal paths could be a single data line and/or include a data and clock signal line. A plurality of input terminals
5
are coupled to sources (not shown) of video signals (CHANNEL
1
-CHANNEL K) which are to be transmitted together over a data link. The plurality of input terminals
5
are coupled to respective data input terminals of a plurality of corresponding channel processors
10
. Respective data output terminals of the plurality of channel processors
10
are coupled to corresponding data input terminals
1
-K of a multiplexer (MUX)
20
. A data output terminal of the multiplexer
20
is coupled to an output terminal
15
of the multiplexer system. Output terminal
15
is coupled to utilization circuitry (not shown) for transmitting the multiplexed data stream over the transmission link.
Each of the plurality of channel processors
10
further includes a complexity output terminal and a control input terminal. The respective complexity output terminals of each of the plurality of channel processors are coupled to corresponding complexity input terminals of a bit rate allocator
30
, and respective quota output terminals of the bit rate allocator
30
are coupled to the corresponding control input terminals of the plurality of channel processors
10
.
In operation, each channel processor receives a signal at its control input terminal representing the bit rate allocated to it for the next quota period. The channel processor then encodes the signal at its data input terminal for the next quota period into a digitally encoded signal at the allocated bit rate. The encoded data signal is supplied to the corresponding input terminal of the multiplexer
20
. The multiplexer
20
operates in a known manner to combine the signals from all the channel processors into a multiplexed data stream. The multiplexed data stream is then supplied to the circuitry comprising the data link for transmission, also in a known manner.
During the encoding process, the channel processor
10
generates a signal at its complexity output terminal representing the coding complexity of the signal being encoded. The bit rate allocator
30
receives the signals from the complexity output terminals of the channel processors
10
, and, based on all of the complexity signals, dynamically adjusts the bit rate quotas for the next quota period among the plurality of channel processors
10
. More complex signals are dynamically allocated at a relatively higher bit rate than less complex signals. Different methods of determining the complexity of the video signal and for allocating bit rates based on the complexities are described below.
FIG. 15
is a block diagram of a channel processor which may be used in the multiplexer system illustrated in FIG.
14
. In
FIG. 15
, elements similar to those in
FIG. 14
are designated by the same reference number. In
FIG. 15
, a data input terminal
5
is coupled to a video signal source (not shown). Data input terminal
5
is coupled to a data input terminal of a constant bit rate encoder (CBR)
14
, and a complexity analyzer
16
. A data output terminal of the CBR encoder
14
is coupled to an input terminal of the multiplexer (MUX)
20
(of FIG.
14
). A control input terminal (CONTROL) of the channel processor
10
is coupled to a quota input terminal Q of the CBR encoder
10
. An output terminal of the complexity analyzer
16
is coupled to the complexity output terminal (COMPLEXITY) of the channel processor
10
.
In operation, the complexity analyzer
16
analyzes the complexity of the video signal at the data input terminal
5
. A signal is produced at the output terminal of the complexity analyzer
16
representative of the complexity of the input signal. The complexity representative signal is supplied to the bit rate allocator
30
(of FIG.
14
). In response to this complexity signal (and those of the other channel processors
10
), the bit rate allocator
30
provides a signal to the control input terminal (CONTROL) of this channel processor
10
(and the other channel processors
10
) representing the bit rate allocated to this channel processor
10
. The CBR encoder
14
is an encoder which compresses and encodes a video signal in accordance with a standard promulgated by the Moving Picture Expert Group (MPEG), termed an MPEG encoder. The CBR encoder
14
provides a data path between its data

Affiliated with

Also associated with

Rating

Packet scheduling using dual weight single priority queue does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Packet scheduling using dual weight single priority queue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet scheduling using dual weight single priority queue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3055104