Queue management system capable of controlling priority and...

Details Queue management system capable of controlling priority and... Queue management system capable of controlling priority and...

1998-04-28

2001-04-10

Kizou, Hassan (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S516000

Reexamination Certificate

active

06215791

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a queue management system; and, more particularly, to a queue management system capable of controlling jitter as well as cell priority.
BACKGROUND OF THE INVENTION
A broadband integrated service digital network (B-ISDN) provides an end-to-end transport for a broad spectrum of services flexibly and efficiently via an asynchronous transfer mode (ATM) technique. In the ATM, information is packetized and carried in fixed length “cells”. Each cell comprises of 53 octets consisting a 5-octet header and a 48-octet information field.
Among the broad spectrum of services, real-time communication services have become a necessity in the B-ISDN. Various QoSs (quality of services) including a receipt rate, a cell loss rate, a delay and a jitter are defined according to requests from various clients for the real time communication services, and, therefore, the B-ISDN network is expected to guarantee these QoS's. Particularly in the real-time communication services, the delay and the jitter exceeding certain bounds are treated as equivalent to a cell loss, and therefore, an appropriate queue management scheme for restraining the delay and the jitter becomes an important issue, wherein the jitter of a connection, also known as a cell delay variation, may be defined in terms of a maximum absolute difference in the delays experienced by any two cells on that connection.
Conventional queue management schemes may be broadly categorized into: work-conserving schemes and non-work-conserving schemes.
In the work-conserving schemes, a server always works as long as a queue holds cells; while, in the non-work-conserving schemes, the server does not always work even if there is a cell in the queue. Since an average receipt rate and an average delay have been regarded relatively important factors for the QoS's, the work-conserving scheme has been preferred. On the other hand, as importance on the cell delay and the jitter grows, the non-work-conserving scheme becomes more important.
The non-work-conserving scheme is inferior in terms of efficiency of the queue to the work-conserving scheme; however, it can significantly reduce burstiness of cell sequence, or simply, the jitter.
A queue management system according to the work-conserving scheme is proposed by Chao (see “A novel architecture for queue management in the ATM network”,
IEEE Journal on Selected Areas in Communications
, 9, No. 7, September, 1991). The system proposed by Chao will now be described with
FIGS. 1A
to
5
.
FIG. 1
exemplifies reference to how the departure sequence numbers can be used in rearranging cells in order to prevent burstiness.
For the sake of discussion, it is assumed that input X's average arrival rate (AR) is 0.1 cell per time slot and the mean burst length B is 2; and input Y's AR is 0.2 cell per time slot and B is 4. Initially, the real time is reset to zero. Immediately following the resetting, four consecutive cells arrive from input Y, and then two consecutive cells arrive from input X as shown in
FIG. 1A. A
DS
i
, a departure sequence number (DS) of an i-th arrived cell, is assigned to each cell as depicted below. The DS
i
, e.g., DS
1
, the DS of the first cell from the Y input, is assigned the real time's value (zero). The next cell is assigned a number according to the formula, DS
i
=maximum {real time, DS
i−1
+1/ARi}. Consequently, the cells that follow are assigned 5, 10 and 15, respectively. When a first cell of the X input arrives, the real time value is 4, which is then assigned to the cell. For a second cell of the input X, its DS is set to maximum {5, 4+10} or 14. As shown in
FIG. 1B
, cells are arranged in a queue
11
. Based on these DS values, a server
12
will sequentially transmit cells with smaller values first, as shown in FIG.
1
C.
For a queue management in an ATM switch, additional data is attached to the cell, which comprises an output port address and a priority field.
A packet including the priority field, which is routed in the B-ISDN, can be arranged like the one shown in FIG.
2
. The priority field consists of a service class and a departure sequence number. Both the output port address and the priority field in the packet could be assigned by an input port controller of the ATM switch.
A conventional queue management architecture proposed by Chao is illustrated in FIG.
3
. The conventional queue management architecture comprises a time division multiplexer (TDM)
31
, a cell pool
32
, a sequencer
33
, an idle-address FIFO
34
, a write controller
35
and a read controller
36
.
The TDM
31
multiplexes twelve inputs into one higher-speed channel. The cell pool
32
is made of memory storing cells from the TDM
31
. The sequencer
33
, a sorting memory, stores a pair of a packet's priority field and its corresponding address, the pair being denoted as P-A, wherein the address refers to a vacant section in the cell pool
32
, information on what is received from the idle-address FIFO
34
. The idle-address FIFO
34
stores addresses of all empty cells in the cell pool
32
. The write controller
35
and the read controller
36
generate proper control signals for all other functional blocks.
Packets from twelve inputs are time division multiplexed into one channel in the time division multiplexer (TDM)
31
and the cells in the packets are written into a cell pool
32
.
The P-A's are stored in the sequencer
33
in such a way that higher priority pairs are always at the right side of lower priority ones so that they will be accessed sooner by a read controller
36
. Once the pairs have been accessed, the address in the cell is used to read out a corresponding section in the cell pool
32
.
The concept of implementing the sequencer
33
will now be illustrated with reference to
FIGS. 4A and 4B
.
It is assumed that a value of P
n
is less than that of P
n+1
, and thus, has a higher priority. When a new cell with priority P
n
and the address An arrives, all pairs on the right of A
k
, including A
k
itself, remain at their positions while others are shifted to the left; the vacant position will be replaced with the pair comprised of the new cell's priority field (P
n
) and address (A
n
) as shown in FIG.
4
B.
If the cell pool
32
is full (i.e., the idle-address FIFO
34
is empty), the priority field at the left-most position of the sequencer (e.g., P
z
) will be compared with that of the newly arrived cell (P
n
). If P
n
is smaller than P
z
, the pair of P
z
and A
z
will be pushed out from the sequencer
33
as the new pair P
n
-A
n
is inserted in the sequencer
33
. Meanwhile, the cell with address A
z
in the cell pool
32
will be overwritten with the new cell. However, if P
n
is larger than or equal to P
z
, the new cell will be discarded instead.
FIG. 5
depicts a detailed structure of the sequencer
33
that processes the P-A pair. A module of a circuit in a box
50
is repeated side-by-side.
The new priority and address pair, P
n
-A
n
, is broadcast to every module. Based on the priority values of X, Y and Z, where X=P
i−1
, Y=P
i
, and Z=P
n
, a decision circuit
51
will generate proper signals, sn and sl, to shift the new pair P
n
-A
n
into a register
55
in the box
50
, shift the pair P
i−1
A
i−1
from the right to the register
55
, or obtain the original value P
i
-A
i
. Table 1 shows a truth table generating the sn and sl signals. For case (a) in Table 1, where the new pair P
n
-A
n
is to be latched in the register
55
, both the sn and sl signals are asserted to select the P
n
-A
n
for inputs to the register
55
and pass a shift-left-clock (slck) signal to the register's clock input. For case (b) in Table 1, only the sl signal is asserted, which results in the P
i−1
-A
i−1
being selected and latched into the register
55
with the clock signal slck. For case (c) in Table 1, the sl signal is deserted while the sn is “do not care”; thus, the register
55

Affiliated with

Also associated with

Rating

Queue management system capable of controlling priority and... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Queue management system capable of controlling priority and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queue management system capable of controlling priority and... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2465224