Note: Descriptions are shown in the official language in which they were submitted.
CA 02301630 2000-02-25
GR 97 P 2266 P - 1 -
Method and circuit arrangement for the transmission of
message units in message streams of different priority
The invention relates to a method and a circuit
arrangement as claimed in the precharacterizing clause
of patent claim 1 and 4, respectively. Such a method
and such a circuit arrangement are already known from
Patent Application 197 05 789.6-31, which was not
published before this.
This method and this circuit arrangement are
intended to solve the problem of allowing the
transmission lines in an ATM system and the buffer
stores respectively associated with them to be utilized
efficiently. To this end, the invention provides that,
in the case of a buffer store which is filled to a
specific level, when a message cell which is associated
with a virtual connection of relatively high priority
arrives on the respective transmission line, one or
more of the message cells (which are currently stored
in the buffer store) of a selected virtual connection
of low priority is or are discarded as a function of
the number of lower priority stored message cells for
this virtual connection.
US Patent Specification 5,268,900 discloses a
method for the transmission of message units which are
associated with message streams of different priority
and traffic class, jointly via one transmission
channel, in which
- the message units associated with the
respective message stream each pass through a queue
which is specific to the priority and traffic class,
- the queues are combined on the basis of their
traffic classes to form queue groups,
AMENDED SHEET
CA 02301630 2000-02-25
GR 97 P 2266 P - lA-
- the queue groups are each controlled by a
separate queue control device in such a manner that
queues are combined to form partner queue groups that
are specific to the traffic class, where they have
priorities that differ for the same traffic class.
K.Sriram, "Methodologies for bandwidth
allocation, transmission scheduling, and congestion
avoidance in broadband ATM networks", Computer Networks
and ISDN 26, 1993, pages 43-59 discloses an operating
strategy for message streams of different priority via
a joint transmission channel, in which a plurality of
queues are controlled on the basis of their priority in
such a manner that one queue is exclusively prioritized
with respect to the remaining queues, in that
transmission of message units from one of the remaining
message units is allowed only in the situation where no
message units can be transmitted from this queue with
maximum priority.
In contrast to this, the object of the present
invention is now to describe a way in which a method
and a circuit arrangement according to the
precharacterizing clause of patent claim 1 and 4,
respectively, can be formed, in order additionally to
ensure throughput guarantees while taking account of
priorities for the message streams.
In the case of a method and a circuit
arrangement according to the precharacterizing clause
of patent claim 1
AMENDED SHEET
CA 02301630 2000-02-25
GR 97 P 2266 - 2 -
and 4, respectively, this object is achieved by the
method features and the circuit features specified in
these patent claims.
The invention in this case results in the
advantage that the following performance features can
be provided with relatively little control complexity
and with relatively little circuit complexity:
1. Individual minimum bit rates are guaranteed for
each message cell stream irrespective of its priority.
2. A bit rate which exceeds the sum of the
throughput guarantees is allocated strictly on the
basis of the priority of the message cell streams, that
is to say the message cell streams of high priority (1)
are assigned first, and if there are none of these to
be transmitted, only then are the message cell streams
of lower priority (2) assigned.
3. If the minimum bit rate is not fully utilized
by one of the message cell streams, then this bit rate
can be made available to other message cell streams.
Advantageous refinements of the method
according to the present invention result from the
dependent claims which refer back to patent claim 1.
The present invention will now be described in
more detail in the following text with reference to a
drawing.
As an example, the drawing shows schematically
a line device LE which is inserted between two
transmission line sections L1 and L2 in an ATM system
operating using an asynchronous transfer mode. In this
case, the only circuit elements of the line device LE
which are shown are those which are required for
understanding of the present invention. Furthermore,
this line device is shown as being representative of
other
CA 02301630 2000-02-25
GR 97 P 2266 - 3 -
line devices inserted into transmission line sections
in the ATM system.
In general, the following text does not
describe the general ATM principle in any more detail,
since this is well known.
Message cells occur on the transmission line
section L1 and, in a known manner, have an external
header in addition to an information part (user part) .
In this case, among other details, such an external
header contains the association with a specific virtual
connection. A virtual connection may either be a
virtual channel connection (individual connection) or a
virtual path connection (bundle of a plurality of
individual connections). A virtual channel connection
is in this case assigned a virtual channel number VCI
(virtual channel identifier) while, in contrast, a
virtual path connection is assigned a virtual path
number VPI (virtual path identifier) in the external
header of the respective message cell. In the case of a
virtual path connection, a virtual channel number VCI
is also specified in the external cell header, in order
to allow the individual virtual channel connections
carried within the virtual path connection to be
identified.
The input of the line device LE (FIGURE 1) is
formed by a conversion device CONY. This conversion
device CONY now places an internal cell header in front
of each message cell that occurs on the transmission
line section L1, in order to allow the respective
message cell to be passed on within the ATM system.
This internal cell header is formed on the basis of the
content of the external cell header contained in each
of the message cells. In this case, one of m queue
identifications QID is assigned statistically on the
basis, inter alia, of the VCI or VPI/VCI contained in
the respective external cell header. The respective
queue identification QID results in
CA 02301630 2000-02-25
GR 97 P 2266 - 4 -
an address reduction with respect to the associated VCI
or VPI/VCI, and is included in the associated internal
cell header.
The message cells, which have had an internal
cell header added to them in this way, are fed
successively to a demultiplexing device DEMUR which is
connected to a buffer store PS via m demultiplexing
outputs. The demultiplexing outputs are individually
assigned to the said queue identifications QID.
The buffer store TS has a large number of
memory locations from which a maximum of m logic queues
can be formed, as will be explained in more detail in
the following text. These logic queues, which are
denoted by Q1 to Qm in the drawing, are actuated
individually by the demultiplexing device DEMUR with
the aid of the queue identifications QID contained in
the received message cells. On such actuation of a
logic queue, the message cell provided with the current
queue identification is transferred to this logic
queue. The individual logic queues are in this case
each formed by a FIFO memory (first-in-first-out
memory) which can simultaneously buffer-store a
plurality of message cells.
The logic queues, Q1 to Qm are combined to form
queue groups, for example on the basis of the
priorities defined for the virtual connections. These
queue groups, which are denoted by WG1 to WGn in the
drawing are, for example, each assigned to one of n
priorities, and are actuated by a queue control device
SC. However, since this queue control device SC is not
the subject matter of the present invention, it will
not be described in any more detail.
CA 02301630 2000-02-25
GR 97 P 2266 - 5 -
Each of these queue groups is in this case controlled
by a separate queue control device SCx where
n = 1,...,n ("Scheduler"). In this case, queues which
have been combined to form a queue group X are actuated
by the associated queue control device SCx on the basis
of predetermined cell scheduling. In the process, one
message cell is taken from each logic queue in such a
control cycle, and is passed on in the direction of the
transmission line section L2 shown in the drawing.
Furthermore, in the exemplary embodiment, a
plurality of queue groups are in each case combined to
form a partner queue group. As an example, the drawing
in this case shows the queue groups WGl to WGn jointly
forming such a partner queue group PWG. In general, the
queue groups which are assigned to one partner queue
group in this case have different priorities, but this
is not a requirement.
Each queue group (WG1 to WGn) in a partner
queue group (PWG) is activated by a high-level control
device, which is not shown in the drawing, to transmit
message cells at a bit rate (cell rate) Rx in the
direction of the transmission section L2. At least two
of these bit rates Rx are not equal to zero.
Furthermore, the queue groups (WG1 to WGn)
associated with a partner queue group (PWG) are jointly
assigned a monitoring device KE, in which case
bidirectional communication links for control purposes
that have not yet been mentioned exist between this
monitoring device KE and each of the queue groups, as
is indicated in the drawing by a dashed connection
line.
CA 02301630 2000-02-25
GR 97 P 2266 - 6 -
The object of the monitoring device KE, in the
situation where a queue group cannot currently transmit
a message cell, even though this queue group has been
activated to do so by a higher-level device which is
not shown in more detail in the drawing, is to transfer
this transmission capability in accordance with a
predetermined priority algorithm to another queue group
within the partner queue group. In general, the
situation where a queue group cannot currently transmit
a message cell may be due to the fact that there are no
more message cells stored in the queues assigned to
this queue group or, based on the scheduling of the
queue control device (SC1...SCn) assigned to the
relevant queue group, it is not permissible to transmit
a message cell since, otherwise, a message cell stream
would exceed a maximum permissible peak bit rate, for
example.
The following text shows how the following
transmission characteristics can be implemented, as an
example, using the method according to the invention
and the line device LE according to the invention and
illustrated in the drawing:
1. Individual minimum bit rates are guaranteed for
each message cell stream irrespective of its priority.
2. A bit rate which exceeds the sum of the
throughput guarantees is allocated strictly on the
basis of the priority of the message cell streams, that
is to say the message cell streams of high priority (1)
are assigned first, and if there are none of these to
be transmitted, only then are the message cell streams
of lower priority (2) assigned.
3. If the minimum bit rate is not fully utilized
by one of the message cell streams, then this bit rate
can be made available to other message cell streams,
CA 02301630 2000-02-25
GR 97 P 2266 - 7
which can also be assigned to another queue group.
The following assumptions are made in order to
illustrate this example:
1. There are only two queue groups, with the queue
group WG1 having a high priority, while the queue group
WG2, on the other hand, has a low priority.
2. R1 - 50 Mbit/s is greater than the sum of the
throughput guarantees for the high-priority message
cell streams.
3. R2 - 20 Mbit/s is identical to the sum of the
throughput guarantees for the low-priority message cell
streams.
4. Both queue groups WG1 and WG2 operate using the
"Weighted Fair Queuing (WFQ)~~ method.
5. If WG1 has no more buffered message cells, the
capability to transmit a message cell is transferred to
WG2, and vice versa.
This results in the following behavior, that is
to say a group WGx is assigned a minimum rate Rx as a
transmission capability. The resultant arrival rate of
all high-priority and low-priority message cell
streams, respectively, together is in this case denoted
by A1 and A2, respectively:
1. A1 > R1, A2 > R2: high-priority cell streams are
jointly assigned R1 - 50 Mb/s, and low-priority cell
streams are assigned R2 = 20 Mb/s
2. A1 > R1, A2 < R2: high-priority cell streams are
jointly assigned R1 + (R2-A2), and low-priority cell
streams are assigned A2
3. A1 < R1, A2 > R2: high-priority cell streams are
jointly assigned A1, and low-priority cell streams are
assigned R2 + (R1-A1)
4. A1 < R1, A2 < R2: high-priority cell streams are
jointly assigned A1, and low-priority cell streams are
assigned A2
The present invention has been described above
using the example of a line device in an ATM system.
CA 02301630 2000-02-25
GR 97 P 2266 - 7a -
However, this invention is not limited to such systems.
In fact, it can be used generally in systems in which
message units which are associated with message streams
CA 02301630 2000-02-25
GR 97 P 2266 - 8 -
of different priority are transmitted jointly via a
physical or logic transmission channel, and, in doing
so, the message units associated with the respective
message stream pass through a queue which is specific
to the message stream. As an example other than an ATM
system as mentioned above, a system operating using the
packet-switching principle should be mentioned here, in
which message units are transmitted in the form of data
packets.
