Note: Descriptions are shown in the official language in which they were submitted.
CA 02334301 2006-11-30
Method for Dynamic Rate Allocation in a Communication Network, in
Particular a High Rate Network.
FIELD OF THE INVENTION
The invention concerns a method for dynamic rate allocation in a communication
network, in
particular, a high rate network such as an ATM (Asynchronous Transfer Mode)
network.
BACKGROUND OF THE INVENTION
ATM networks were designed to support the flow of multimedia information, such
as data,
sound, images and video. ATM technology permits the same infrastructure to
transmit data flow
coming at different rates and with different performance requirements. In
order to offer these
characteristics, ATM networks are anticipated to enable resource management
and guarantee
service quality.
Before being established, a network connection request, specifying the desired
characteristics, in
particular, the rate it will reserve and the necessary quality of service,
must be made. As needed,
the connection states, in its request, the minimum rate the network must
guarantee it. If the
network decides that it has sufficient resources to meet the request, it
establishes the connection
and also guarantees the rate and connection quality for the requested service.
Different classes of service have been defined which in turn, according to the
type of data source
and performance and quality required from the corresponding connection, define
the
connection's traffic control protocol. The classes usually considered are: the
class known as
CBR (Constant Bit Rate), the class known as VBR (Variable Bit Rate), the class
known as ABR
(Available Bit Rate), and a class related to ABR, the class known as ABT (ATM
Block
Transfer).
To simplify, it can be said that in the CBR class, high-quality service is
specified, whereas in the
ABR class, there are no explicit requirements for service quality with respect
to transfer time or
1
CA 02334301 2000-12-05
gigs. In the VBR class, a certain number of control parameters are defined at
the time of the
connection, and once defined, these limits are used by the network to
guarantee service quality.
The mechanisms which are generally implemented for the service classes ABR and
ABT, the
only ones considered here, are the following: for each active connection, a
specialized bit,
hereinafter referred to as the resource management bit, will run the entire
route followed by the
bits using the connection. When a network node receives this bit, a protocol
is implemented to
verify that the rate allocated between the node and the connection does not
exceed a value which
is determined by the other connections at the time. If this is the case, the
node will allocate a new
rate for the connection of which the value would be recorded in the resource
management bit.
When the resource management bit arrives at the end of the route followed by
the user bits, it is
returned to the source of the connection in question with the lowest rate
authorized along the
length of the route. The source must thus adjust its rate to this new value.
An allocation method is planned for implementation along the nodes of a
network. It permits the
allocation of a bit rate to each source of which the connections converge at a
network node, after
a rate request has been made by the source. The allocated bit rate will allow
the maximum band
offered by the output link of the said node to be shared.
A sample description of the traffic control mechanisms implemented for the ABR
class can be
taken from F. BONOMI and K.W. FENDICK in an article entitled "The rate-based
flow control
framework for the Available bit Rate Atm service" which was published in the
March/April
1995 issue of the IEEE Network.
Known rate allocation methods are generally implemented for connections which
support data
and use FIFO-type queues in the nodes, which cannot be envisaged for video
transmission as,
since video rate specifications are necessarily high, transmission delays
cannot be too great, etc.
2
CA 02334301 2006-11-30
The goal of this invention is thus to propose a rate allocation method which
enables equitable
sharing of the band used by different real-time sources, notably video
sources.
SUMMARY OF THE INVENTION
To that end, a method according to this invention is proposed which will, over
successive cycles,
do the following:
a) at the beginning of each cycle, assign a rate to each connection; and
b) during the cycle, on the one hand, allocate the assigned rate to each
connection whose
required rate is greater than that assigned, that connection is thus accounted
for and
marked as clipped; and. on the other hand, allocate to each connection whose
required
rate is less than that assigned, either the rate already allocated in the
preceding cycle if in
that previous cycle the said connection had not been marked as a clipped
connection, or
the rate required if in the preceding cycle the connection had been marked as
a clipped
connection. The difference between the assigned rate and the allocated rate is
thus
accounted for as unallc-cated rate; and
c) at the end of the cycle, calculate a new rate to assign to each of the
connections in
question for the following cycle, based on the unallocated rate accounted for
and the
number of clipped connections.
Another characteristic of the invention would be to assign to each source,
during an initial cycle,
a rate which corresponds to an. equitable share for each of the maximum band
sources offered by
the node output link.
Another characteristic of the invention would be to calculate the new rate in
order to assign to
each of the clipped connections in the following cycle, sharing the
unallocated rate equally
among the clipped connections.
3
CA 02334301 2000-12-05
Another characteristic of the invention would be to calculate the new rate to
assign to each of the
connections in the following cycle, sharing equally the unallocated rate,
minus the excess
assigned rate, among the said clipped connections.
Another characteristic of the invention would be to ensure that the duration
of each cycle is
greater than the renegotiation period implemented by the network equipment.
Another characteristic of the invention would be to ensure that the duration
of each cycle is
greater than the network equipment renegotiation period increased by the
maximum amount of
time taken by the resource management bits of the said connections to make the
complete trip
from the source in question to the other end of the network and back again to
the source.
Another characteristic of the invention would be to count the requests from
each source,
examining only requests that have an order number.
Another characteristic of the invention would be to mark a connection after it
receives the
request from the corresponding source, erasing the mark at the beginning of
each cycle, and
examining only requests from sources whose connections have already been
marked.
Another characteristic of the invention would be to weigh the rates assigned
to each source. Each
weight factor would depend on the minimum guaranteed rate requested by the
corresponding
source. For example, the weight factor could be equal to the minimum
guaranteed rate requested
by the source divided by the total minimum guaranteed rate requested by all
sources. The rate
assigned to a source may thus be equal to a rate common to all the sources
which are multiplied
by the weight factor.
Another characteristic of the invention would be when a request is received
from a source whose
connection has not been marked as clipped in the previous cycle, and when the
rate now
4
CA 02334301 2006-11-30
requested is greater than the rate which was allocated in the previous cycle,
to interrupt the
current cycle and begin a new cycle with this request, with the rate assigned
to each source being
either the current rate of the cannection in question or the rate shared
equally among all sources,
whichever is greater.
Another characteristic of the invention would be to assign a cycle
identification number to each
connection.
In accordance with a first aspect of the present invention there is provided a
method for dynamic
rate allocation for implementation in network nodes, each network node having
a plurality of
sources, each source having a connection to a network node, the method
comprising:
allocating to each connection, and in response to one of a plurality of
periodic rate
requests made by a source corresponding to the connection, a cell rate
selected from a lesser of a
request rate and a residual rate after allocation of requested rates to all
the other sources,
wherein, during successive cycles:
a) at the beginning of each cycle of receipt of requests originating from the
sources
corresponding to the connections, considering and assigning an assigned rate
(Rl, Ri) to each
connection; and
b) during the cycle,
b1) for each connection having a required rate (Rq) which exceeds the assigned
rate (R1, Ri) for the cycle, allocating the assigned rate (R1, Ri) to that and
marking it as a clipped connection for the cycle;
b2) for each connection having a required rate (Rq) which is less than the
assigned rate (Rl, Ri), determining whether that connection is marked as a
clipped connection from a previous cycle, and if so, allocating the difference
between the value of the assigned rate and the value of the rate allocated as
a non-
allocated rate value (0); and if not, allocating the rate already allocated to
the
connection in previous cycle; and
5
CA 02334301 2006-11-30
b3) after a rate has been allocated to each connection calculating the number
(m)
of clipped connections, and calculating a new value for the assigned rate (R1,
Ri)
for the subsequent cycle using the following relation:
R1 = R1 + C-N=R1 +p
m
wherein C is the rate value of the maximum band offered by the outgoing link
at the node, N is
the number of active connections on the node, 0 is the non-allocated rate and
m is the number of
clipped connections.
BRIEF DESCRIPTION OF THE DRAWINGS
The above-mentioned characteristics of the invention, and others, will become
more clear by
reading the following description of an example of this invention's
implementation
accompanied by the attached <irawing which illustrates the invention's method
as illustrated by
an arbitrary example.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
According to the invention, the method is based in each network node. For each
active
communication which enters the node in question, the node holds a Reg register
which stores
the rate that is allocated to each communication. At intervals of time
designated by T, the source
of each communication sends an RM resource management bit onto the
communication path. At
the beginning, the RM bit can-ies the rate requested by the source. At each
node, the RM
management bit rate and the rate stored in the node Reg register are compared.
If the rate stored
in the Reg register is less than. the RM management bit rate, then the RM
management bit rate is
changed to the rate stored in the Reg register. On the other hand, if the RM
management bit rate
is equal to or greater than the stored rate, it is not changed.
Once it arrives at the end of the network, the RM management bit returns to
the source. It has the
lowest communication rate al:located by the network which is therefore
authorized along the
entire length of the communication path. Thus the source adjusts its user bit
rate to the new rate.
5a
CA 02334301 2000-12-05
Note that we call the bits which carry data 'user bits', for example, image
and sound data sent by
the source to a requesting party.
This invention's method is thus concerned with the allocation of communication
rates. This
allocation is dynamic in the sense that there is a rate renegotiation carried
out over the RM
resource management bits' T intervals. Thus, for each communication which
arrives at a network
node, the node will receive, at T intervals, one and only one renegotiation
request and respond to
it, using this invention's procedure, by allocating a user bit rate to the
user bits.
The invention's method is thus used over successive cycles of T intervals. We
will now describe
the various steps of the method, as they appear in a cycle.
If we call the maximum band which can support the output link of the node in
question 'C', then
distributing the rate equally over the N connection sources which meet at this
node allocates to
each source a rate of C/N. Therefore, over an initial cycle, this value ofRi =
C/Nis placed in
each of the Reg registers linked to the active communications.
During each cycle, when the node receives the RM resource management bit sent
by the source
whose connection is converging on the node, two cases may arise.
In the first case, the Rq rate required by the source and carried by the RM
bit is less than the R1
rate. Thus an RD register accounting for the A quantity of band which has not
been allocated
during the current cycle is increased by the amount equal to R1 - Rq. In
addition, the
communication is marked as being unable to increase its rate beyond the Rq
value.
In the other case, the Rq required rate is greater than the Rl rate. The
source request is said to be
clipped at the R 1 rate and is thus marked as a result. In addition, the count
on the m counter
(which counts the number of clipped requests) is increased by increments.
6
CA 02334301 2000-12-05
At the end of a cycle, when all the sources have transmitted their resource
management bit RM,
that is to say, after a T interval corresponding to the time it takes for the
sources to send the RM
bits the situation is as follows.
The communications whose Rq rate requests are less than the R 1 rate are
marked as being unable
to increase their rate beyond that Rq rate. The others will be allocated a
rate which is for the
moment equal to the Rl rate. The total of the band left unallocated during the
cycle is stored in
the L register and the number of clipped communications is stored in the m
counter.
In this way, we know the number of connections which need to increase their
rate and the
remaining band available for that increase. With this invention, rate
increases can be authorized
for clipped connections in the next cycle. Rates would be increased by a value
corresponding to
the unallocated band of the node output link divided by the number m of the
clipped connections.
In the following cycle we can also re-implement the invention's method with a
new value ofRl
and authorize rate increases only for those connections previously marked as
clipped.
We will now explain the invention's method first by using an arbitrary example
as an
illustration. In this example, there are three communications, C1, C2, and C3
(see figure 1). The
first C1 requires a rate of two units, C2 requires a 6-unit rate and C3
requires nine units. The
maximum capacity C of the node output link is 15 units (C = 15).
After the initial cycle CYI, each communication will be assigned an equal
share of the R 1 rate,
the value of which is thus R 1= C/N where N is the number of active
communications converging
on the node in question. Here N= 3. Thus Rl = 5. The total assigned rate is N-
R1, or 15 units.
Using the terminology adopted here, the assignment of a rate to a
communication is not the
allocation. For a connection which was previously clipped, the assigned rate
is the maximum rate
7
CA 02334301 2000-12-05
which the node can allocate it. On the other hand, the assigned rate for a
connection which has
not been previously clipped bears no relation to the allocated rate. The
difference between the
assigned rate and the allocated rate is accounted for in unallocated band.
This communication C1 is allocated two units and there are three unallocated
units which are
accounted for in the RA register (L = 3). Communications C2 and C3 were
clipped at five units,
and are thus allocated only 5 units. For communications C2 and C3 only, the
allocated rate is
equal to the assigned rate.
At the end of the cycle, there are therefore A = 3 and m = 2 (number of
clipped communications
= 2).
In the next cycle CY2, the three units which were unallocated in the previous
CYl cycle will be
distributed equally to the clipped communications C2 and C3, L/m = 3/2 = 1.5
units per
conununication. To do this, we allocate an equally shared R1 rate of (5 + 1.5)
units, or 6.5 units,
to each active communication on the node in question. The total assigned rate
is thus N- R1-=
6.5x3=19.5units.
The Cl communication is allocated two units and there remains, with respect to
assigned units,
4.5 unallocated units. Communication C2 is allocated six units in compliance
with its request,
and there remain 0.5 unallocated units which, added to the 4.5 units already
unallocated from
conununication C l, totals five unallocated units.
Communication C3 is allocated 6.5 units. Communication C3 is the only
communication to have
been clipped during this cycle. At the end of the cycle therefore we have A 5
and
m=1.
8
CA 02334301 2000-12-05
To calculate the band to be shared in the next cycle, we must subtract the
assigned rate which
exceeds the maximum capacity C of the node output link from the five
unallocated units, that is
(N - Rl - C) =(19.5 - 15) = 4.5 units. The band to be shared in the following
cycle is thus equal
to: 5 - 4.5 = 0.5 units allowing the calculation of the new R1 value which now
equals 6.5 + 0.5 =
7 units.
In the CY3 cycle, each active communication will be assigned 7 units, which
corresponds to the
new R1 rate. The total assigned rate is thus 3 x 7 units, or 21 units. You
will notice that at the
end of the CY3 cycle, 0 will be equal to 6. The band to be shared in the next
cycle will thus be
A -(N=R1-C)=0.
The process continues in this way from cycle to cycle.
We will now formalize the invention's method.
The band available for all communications is the band available-0n the node
output link, which
is C.
The total equally assigned rate, to the rate of each cycle, is called Da and
its value is equal to
N- R 1, from which:
Da=N=Rl
However, the total assigned Da may be greater than the node output link's
maximum capacity C.
The result is an assigned rate which exceeds the maximum capacity of the node
output link. The
excess rate De thus has the value:
9
CA 02334301 2000-12-05
De=Da-C=N-RI-C.
Therefore the relationship can be expressed in this way:
C-Da-De =Da-(N=Rl - C) = Da + (C- N - RI)
At the end of each cycle, the total assigned rate Da was, in the first
portion, allocated, and in the
second portion, unallocated. In the allocated portion there is, in one
portion, the rate effectively
allocated to the clipped connections, or m.Rl, where m represents the number
of clipped
connections and R1 represents the rate assigned to each communication, and in
the other portion,
the total rate allocated to unclipped connections, or LZ 1uncripped rate.] The
second, unallocated
portion, was accounted for in the Rni register. This can be expressed in the
following manner:
Da = m= R 1+ E rate + A
unclipped
And so, replacing the previous expression:
C-m-Rl+(C-N-R1)+E rate + A
unclipped
Which can also be written as follows:
C = m =(R1+ C-N-Rl+p) + Yrate
m unclipped
CA 02334301 2000-12-05
Through this relationship, it can be seen that if, in the next cycle, the rate
included in parentheses
is attributed to the connections which were previously clipped, the band will
be shared equally,
and fully used.
This invention will proceed in the following manner. In the next cycle, the
invention's method
will be implemented again, authorizing only those connections which were
clipped to increase
their rate again. To do this, the R1 value is modified and now equals:
R 1= R 1+(C-N=R 1) +p
m
Thus, at the beginning of each cycle, there are a certain number of
connections which are not
authorized to increase their rate whereas others are authorized to do so up to
a value
corresponding to the value stored in the R 1 register. Since the connections
are examined
individually in the process explained above, at the end of the cycle, the
available unallocated rate
A and the number m of clipped connections may be determined. From that point,
the new value
ofRi which to be used for the examination of the next cycle is recalculated.
The process
continues to function in this way continually from cycle to cycle.
With this invention, if a connection that was not clipped in the previous
cycle wishes to increase
its rate in the current cycle, the current cycle is interrupted. The rate
stored in the R1 register is
modified and a new cycle is started based on this connection. The new Ri rate
equals the rate
previously allocated to the connection in question or the equally shared rate
C/N, whichever is
greater, C being the rate available on the node output link in question, and N
being the number of
active connections at the time the new R1 rate is being calculated.
According to one of this invention's first application methods, it is expected
that a counter will
be used to count the requests arising from each source. This will ensure that,
during a period, a
Il
CA 02334301 2000-12-05
rate renegotiation for each active connection converging on the node in
question does take place.
This process is used only for the examination of connections that have the
same order number.
According to another of this invention's application methods, it is predicted
that the time it takes
to change the R1 register will be greater than the network equipment
renegotiation period
allowed for that purpose.
Appropriately, this period is increased by the maximum time needed by the
active connections'
RM resource management bits to make the complete trip from the source to the
other end of the
network and back to the source again. In that way, it is ensured that all
sources have the time to
comply with the rates authorized by the various network nodes, a compliance
which cannot be
carried out until the RM resource management bit carrying information on
source rate allocation
has had the time to return to the source. This way of doing things allows the
process to have a
certain robustness with respect to the breakdown of certain trunks.
In the case where a connection makes two requests during the same period, the
second would not
be taken into account so that band sharing between sources is not disturbed.
To do this, each
connection is marked once it has made a request. This mark is erased at the
beginning of each
cycle. Thus, in a given cycle, a request is no longer accepted if it comes
from a connection which
is already marked.
According to another of this invention's application methods, to avoid
analyzing the same
connection twice in the same cycle, each cycle is assigned an order number
which is increased
by one unit in each new cycle. This order number is memorized by each
connection after it
analyzes the cycle. So let us say that we are in cycle Cy. In this cycle,
prior to analysis, a
particular connection memorizes the number Cy - 1. After analysis, the number
Cy is
memorized.
12
CA 02334301 2000-12-05
Before allocating a rate to a source, the memorized order number for the
connection in question
is verified to see if it is one unit lower than that of the current cycle. If
this is the case, the
allocation is implemented. Otherwise, it is not implemented, since this
indicates that the
connection in question has already been analyzed in the current cycle.
When cycle Cy is interrupted as a result of a rate request from a non-clipped
connection which is
greater than that which has been requested to date, and a new cycle is begun,
the new cycle will
be assigned a number equal to the number of the interrupted Cy cycle plus two
units. Thus each
verification results in a new allocation.
In the process which has just been described, the rate requested by the video
source
corresponding to its maximum requested rate is fixed for at least several
cycles. The user may
modify these parameters if so desired, but in practice, it will rarely be
done. If, however, for
reasons of network size, or for other considerations, the source requests must
be modified very
often, we were able to show that the invention's process tends to allocate
rates at a value of C/N
with the result that the benefit of being able to use the available band for
sharing between the
sources whose requirements are the highest is lost.
In the process just described, each source requests a maximum rate. But the
process can also be
applied in the case where sharing is based on the minimum rates guaranteed
from the sources is
taken into account. The following procedure accQmplishes this.
The C value of the rate available on the node output link in question is
divided by the sum of the
minimum guaranteed rate Dmg, (i = 1 to N). A factor is thus obtained which
allows the weighting
of each equally assigned rate, which we will call R; . We thus have:
R; =Dmg; - C/ I Dmg; =DMG; - C
i=(J...N)
13
_ _ _. ~ . .. _. . . _...~ _.,...~~,,..~...~ ~.~_.,.,..,..-.. _. . _ . _....
.. . . ._ _ _ _ _ .
CA 02334301 2000-12-05
where DMGi is the weight factor applied to the C; source.
Each Ci connection is thus clipped at the rate of Ri. If we take into
consideration the R register in
which is stored the total rate assigned to all connections, the R; rate
assigned to a connection
would equal:
Ri =DMGi =R
At the end of each cycle, the recalculated value of this register will be
given by the following
relationship which is analogous to the one mentioned above:
C-R= EDMGi +1~
R =R+ i= 1....N =R+C-R+Z~
EDMG; EDMGi
unclipped unclipped
where Y_DMGi = 1 represents the sum of weight factors, 0 represents the
unallocated rate
i = 1...,N
and YDMGi represents the sum of weight factors only for connections which have
been clipped.
unclipped
14
