Note: Descriptions are shown in the official language in which they were submitted.
CA 02256341 1998-11-19
96 P 1499 P - 1 _
Fi ~ i . ',=---; ~ ~'~ "~ ~ ,
Description ~~~ ...,:.;:L~., .;.. ~;
Method for optimization of the utilization of
connecting sections in systems in which information
is transmitted in data packets.
The invention relates to a method as claimed in
the precharacterizing clause of patent claim 1.
In modern packet switching systems, information
is transmitted in data packets . One example - of this is
ATM cells . These have a header part and an information
part. The header part is used to store connection infor-
mation, and the information part to store the wanted data
to be transmitted. As a rule, the actual transmission
takes place via connecting sections between the trans-
mitter and receiver. In this case, there may be a
requirement to utilize the connecting sections in such a
manner that a plurality of transmitting devices transmit
the cell streams originating from these devices via the
same connecting section.
In order to allow the transmission of the respec
tive cell streams to be carried out in accordance with
the requirements of the individual cell streams, a so
called WEIGHTED FAIR QUEUEING SCHEDULING method has
become generally accepted in the prior art. The corres
ponding relationships are described, for example, in the
document "Virtual Spacing for Flexible Traffic Control",
J.W. Roberts, International Journal of Communication
Systems, Vol. 7, 307-318 (1994). In this case, the
individual cell streams are assigned different weighting
factors, which are used to control the actual trans-
mission process on the individual connecting sections.
Reference should be made to Figure 3 to assist under-
standing.
CA 02256341 1998-11-19
- 2 -
By way of example, this shows cell streams 1 ...
n. The n cell streams are passed from a transmitting
device DEMUR in the direction of one or more receivers.
In practice, only one common connecting section is used
in this case . The n cell streams are furthermore assigned
weighting factors r1 .., rn. To assist understanding, it
is assumed that it is intended to pass only two cell
streams, namely the cell streams 1, 2, via a connecting
section. The connecting section is furthermore intended
to have a maximum transmission capacity of.150 Mbit/s.
The two cell streams 1 and 2 are assigned weightings r1 =
2 and r2 - 1. This results in the cell stream 1 being
transmitted at a transmission rate of 100 Mbit/s, and the
cell stream 2 at only 50 Mbit/s, if cells for both cell
streams are present for transmission. If only one of the
two cell streams has cells to transmit, this cell stream
is assigned the total transmission capacity of
15o Mbit/s.
Figure 2 shows how the theoretical considerations
addressed above are implemented in practice in the prior
art. This shows how data packets, or ATM cells, are dealt
with using the weighted fair queueing scheduling
algorithm. In this case, incoming cells are supplied to
the input device EE, are passed on to the demultiplexing
device DEMUR and are stored there with the aid of a
demultiplexing function, which is implemented here, and
with the assistance of an identifier QID in a logic
queue. The identifier QID is in this case contained in
the cell header of each cell.
At the same time, control data which are deter-
mined in the input device EE are for this purpose
supplied to a scheduler device S. A scheduling algorithm
which is known per se is executed in this device.
CA 02256341 1998-11-19
- 3 -
This may be, for example, the weighted fair queueing
scheduling algorithm or any other algorithm. This
algorithm determines, for example, the sequence in which
or the time at which it is intended to read the cells
which are stored in the buffer stores P1...Pn. The result
of the assessment of the control data by this algorithm
is supplied to the output device AE. The cells stored in
the buffer stores P1...Pn are now read, on the basis of
the result of the assessment, by the algorithm which is
being executed in the scheduling device S. Furthermore,
an acknowledgement signal is fed back to the input device
EE. After this and when a new cell with an identifier QID
arrives in the input device EE and when an acknowledge-
ment 'selected QID' is present, the input device EE uses
the buffer filling level for QID - i as well as the
scheduling method to decide whether the message "SCHEDULE
QID" is generated. This message indicates to the
scheduler device S that it should carry out initial
planning for the next transmission time for this identi
fier QID, in some way.
A problematic feature of such a procedure is
that, although the weighted fair queueing scheduling
algorithm guarantees minimum cell rates, a maximum cell
rate limiting cannot be carried out here. However, this
is a major factor since, in practice, both minimum and
maximum cell rates often have to be complied with - for
example in the case of ABR (available bit rate) traffic.
The invention is based on the object of indicat
ing a way in which the weighted fair queueing scheduling
algorithm can be modified in such a way that optimized
transmission is ensured here as well.
CA 02256341 2002-10-09
20365-3952
4
The object is achieved on the basis of the
features specified in the precharacterizing clause of patent
claim 1, by means of the features in the characterizing
part.
An advantageous feature of the invention is that a
two-stage scheduling method may be carried out depending on
an identifier which is contained in the packet header. In
this case, the result of the first stage is used as an input
signal for the second stage. This results in particular in
the capability to control both a lower limit and an upper
limit of the cell rate. In particular, this method is not
limited to the use of a specific algorithm.
In accordance with this invention, there is
provided a method for optimization of the utilization of
connecting sections in systems in which information is
transmitted in data packets, having a scheduling method (S2)
by means of which connection parameters, which are
representative of lower transmission rates of the data
packets, are guaranteed during the transmission process, and
having a queue identifier (QID) which is stored in the
packet header, characterized in that a further scheduling
method (S1) may precede the scheduling method (Sz) depending
on the queue identifier (QID), by means of which further
scheduling method (S1) the connection parameters which are
representative of upper transmission rates of the data
packets are limited during the transmission process.
Further refinements of the invention are provided
in the dependent claims.
Claim 2 provides that the connection parameters
are limited during the transmission process, by means of the
first stage of the two-stage scheduling method. This is
CA 02256341 2002-10-09
20365-3952
4a
intended, in particular, to control limiting of the cell
rate. This results in the cells not being transmitted at
higher cell rates during the transmission process.
Claim 3 provides that the second stage of the two-
s stage scheduling method is the weighted fair queuing
scheduling algorithm. This is linked to the advantage that
a proven method can be used. A further advantage of this is
that this algorithm guarantees lower limiting of the cell
rate.
Claim 4 provides for an input device to contain a
table which contains the current filling levels of the
buffer stores. This is linked to the advantage that a
current map of these filling levels is stored here at all
times.
CA 02256341 1998-11-19
- 5 -
Claim 5 provides that, depending on the control
data obtained from the scheduler device, the output
device takes cells from at least one of the buffer stores
and acknowledges this process to the input device. As a
result of the feedback, the reading process has a direct
influence on the first stage of the two-stage method. The
two stages of the two-stage scheduling method thus do not
operate independently of one another. The way in which
the first stage operates is influenced by the way in
which the second stage operates. The identifier or the
packet length may be used, for example, as feedback
parameters.
Claim 6 provides that the identifier is entered
while the connection is being set up.
Claim 7 provides that the data packets are ATM
cells. The invention can thus be applied in particular to
ATM networks.
In the figures:
Figure 1 shows the method according to the invention,
Figure 2 shows the practical application of the prior
art,
Figure 3 shows theoretical considerations relating to
the prior art.
Figure 1 shows the method according to the
invention. In this case, it is assumed that the infor-
mation is transmitted in ATM cells, using an asynchronous
transfer method (ATM).
CA 02256341 1998-11-19
- 6 -
The cells are supplied to the input device EE in
a cell stream. The routing information is stored in the
header part of each cell. Furthermore, an identifier QID
has been stored here while the connection is being set
up. This identifier is a cell stream identifier which is
entered in the cell header on a connection-specific basis
or for a group of connections. As a rule, the identifier
QID is assigned simple numerical values. In the present
exemplary embodiment, the identifier QID is intended to
have the values 1...N. Originating from the input device
EE, the cells themselves are supplied to the demultiplex
ing device DEMUR where they are written into buffer
stores P1...Pn, designed as a logic queue, with the aid
of a demultiplexing function, which is implemented here,
and with the assistance of the identifier QID.
The input device EE furthermore contains a table
T as to which of the connections require the connection
parameters to be limited during the transmission process .
In the present exemplary embodiment, it is assumed that
limiting of the cell rate is controlled in the sense of
limiting the connection parameters. In order to verify
the connection, the identifier QID is taken from each of
the incoming cells and is compared with the entries in
the table T.
If it is not intended to limit the cell rate for
a connection, corresponding control data are supplied via
the connecting section B to the scheduler device S2,
bypassing the scheduler device S1. There, the control
data are used in a scheduling algorithm which is known
per se. In the present exemplary embodiment, this is
intended to be weighted fair queueing scheduling method,
which has already been described in the introduction.
Such an algorithm results in a lower cell rate being
guaranteed, in the sense of guaranteeing the connection
parameters of the cells during the transmission process.
CA 02256341 1998-11-19
According to the present exemplary embodiment,
the cell rate for one of the connections is limited, for
example for the connection with the number 8 (QID=8?. In
this case, the control data are supplied via the connect-
s ing section A to the scheduler device S1. Here, an
algorithm starts to be executed, which controls an upper
limit on the cell rate. This is done by a function
implemented here using the identifier QID for initial
planning of the control data supplied from the input
device EE, such that the individual cells do not exceed
a predetermined rate. At the time at which the scheduler
device S1 would read a cell, it produces, however, a
control signal itself for initial planning of the read
time, corresponding to the general scheduling algorithm
being executed in the scheduler device S2. No initial
planning of the next event takes place in the scheduler
device S1 for the same identifier QID. Thus, stimulated
by the scheduler device S1, the scheduler device S2 plans
the sequence for the indicated identifier QID, corres-
ponding to the scheduling algorithm being executed here.
The cells initially planned by the scheduler device S1
may thus experience an additional delay. The peak bit
rate set in the scheduler device S1 may thus be different
from that used to read the cells.
By way of example, the weighted fair queueing
scheduling algorithm is intended to be used in the
scheduler device SZ in the present exemplary embodiment,
although other algorithms can also be used. The method
according to the invention is not limited to the use of
a specific algorithm.
The result of the evaluation of the algorithm
being executed in the scheduler device Sz is passed to
the output device AE.
CA 02256341 1998-11-19
g _
Whenever it is intended to read the next cell from a
buffer store Pl...Pn with a specific identifier QID, this
is indicated to the output device AE. This reads the
first cell with the indicated identifier QID from the
buffer store P1...Pn in question, and reports this
together with the corresponding identifier QID to the
input device EE. The latter then checks whether a further
cell with this QID is stored in the buffer store. If this
is the case, a corresponding signal (SCHEDULE QID) is
sent to the scheduler device S1. If this is not the case,
no further action takes place in the sense of initial
planning (reading) in the scheduler device S1 for this
identifier QID.
This method means that an event for an identifier
QID can be initially planned only in the scheduler device
S1 or S2, but not at the same time in both devices.
Furthermore, the two function blocks S1 and Sz are not
linked to a specific implementation. This two-stage
algorithm is thus used to determine the sequence in which
and the time at which it is intended to read the cells
which are stored in the buffer stores P1...Pn.
Finally, it should also be mentioned that the
above exemplary embodiment has been described using the
example of ATM cells. However, the invention is not just
limited to this. The method according to the invention
can likewise be used for the transmission of information
in data packets as such. However, in this case it is
necessary to ensure that the packet length is added to
the control data.
