Note: Descriptions are shown in the official language in which they were submitted.
CA 02351352 2001-05-23
WO O1/Z6306 PCT/KR00/01099
-1-
ABR SERVICE ENGINE IN PACKET SWITCHING SYSTEM
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a packet switching system. More
particularly, the present invention relates to an Available Bit Rate (ABR)
service engine
in a packet switching system.
2. Description of the Related Art
Packet switching technology is utilized in the Asynchronous Transfer Mode
(ATM) networks and the Internet networks. One of the general traffic
management
problems lies in the congestion flow control of the packet switching networks
such as the
ATM.
The ATM layer provides the following four services: Constant Bit Rate (CBR),
Variable Bit Rate (VBR), Unspecified Bit Rate (UBR), and Available Bit Rate
(ABR).
In the ABR service, the source adapts its bit rate responsive to the changes
of the
network condition to transmit data at a bit rate available from the network.
The ABR
service was introduced to the ATM network in order to support data
applications with a
guaranteed bandwidth service, because such service was~not efficiently
supported by the
Variable Bit Rate (VBR) service. For more details and background information,
see S.
Sathaye, ATM forum Traffic Management Specification, Version 4.0, Feb. 1996;
F.
Bonomi and K. W. Fendick "The Rate-Based Flow Control Framework for the
Available
Bit Rate ATM Service", IEEE Network, vol. 9, no. 2, pp. 25-39, 1995; and, R.
Jain
"Congestion Control and Traffic Management in ATM Networks: Recent Advances
and
Survey", Computer Network and ISDN Systems, vol. 28, no. 13, pp. 1723-1738,
1996.
Most congestion occurs due to burst traffic, causing cell loss and
unpredictable
cell delays. Due to these characteristics, the network is designed to modify
its data
transfer rates according to the loading conditions of the network.
Accordingly, the
notion of elastic traffic services was introduced and the data transfer rates
are adjusted
according to the network bandwidth availability. A representative example of
the elastic
traffic services is the ABR service provided in the ATM networks.
The ATM forum has selected a closed-loop rate-based scheme as the flow
control scheme for the ABR service due to its simplicity. The closed-loop rate-
based
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-2-
flow control scheme uses the feed back information from the network to control
the rate
at which each source can transmit the cells into the network. The feed back
information
is conveyed to the source through specific control cells called resource
management
(RM) cells. For the rate-based flow control, information about the network
congestion is
written in the RM cell using mechanisms, such as explicit forward congestion
indication
(EFCI), relative rate (RR), and explicit rate (ER). The ABR service does not
require a
complex traffic characterization and a call admission control at the source
and at the
switches, respectively. Due to this simplicity, it has been expected that the
implementation and the deployment of the ABR service would be much easier than
other
bandwidth-guaranteed services, such as the CBR or the VBR service. In reality,
however, the implementation of ABR-capable switches appears to be much more
difficult than originally expected. The difficulty mainly lies in the
designing of a simple,
scalable, and stable ABR flow algorithm, more specifically an ER allocation
algorithm
in an asynchronous and distributed network environment.
Moreover, the long and diverse round trip delays (RTDs) involved in the closed
loop and the distributed bottle neck locations of ABR VCs (Virtual Circuits)
make it
difficult to design a high performance ER allocation algorithm. ABR queues in
the
network can hardly be stabilized when the transmission rates of ABR sources
are
determined based on the network state information at different time. In
particular, if
only a binary feed back mechanism (either EFCI or RR marking, or both) is
employed,
the ABR queues in a steady state inevitably exhibits persistent oscillation
with its
magnitude and period. For more details and background information, see E.
Hernandez-
Valencia, et al., "Rate Control Algorithms for the ATM ABR Service", European
Transactions on Telecommunications, vol. 8, no. 1, pp. 7-20, 1997, F. Bonomi,
D. Mitra,
and J. B. Serry "Adaptive Algorithms for Feedback-Based Flow Control in High-
Speed,
Wide-Area ATM Networks", IEEE J. Select. Areas on Communications, vol. 13, no.
7,
pp. 1267-1283, 1995, and K. K. Ratmarkrishnan and Jain "A Binary Feedback
Scheme
for Congestion Avoidance in Computer Networks with a Connectionless Network
Layer", Proc. ACM SIGCOMM'88, pp. 303-313, 1988.
The above-described oscillatory behavior of the ABR queues will increase the
likelihood of cell loss and link under-utilization due to a periodic buffer
overflow and
underflow. Thus, the ABR flow control scheme using the ER marking has been
introduced to realize aymptotic stability of the ABR queues to overcome the
drawbacks
of the binary feedback mechanisms. Yet, designing an asymptotically stable ER
allocation algorithm particularly in a simple form is a difficult problem.
This problem
naturally falls into a feed back control problem with the delay.
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-3-
L. Benmohanmed and S. M. Meerkov formulated the rate-based flow control
problem as a discrete-time feedback control problem with the delay, and
derived an ER
allocation algorithm that achieves the asymptotic stability and allows for the
arbitrary
control of the closed-loop performance. This is described in "Feedback Control
of
Congestion in Packet Switching Networks: The Case of Single Congested Node",
IEEE/ACM Trans. On Networking, vol. 1, no. 6, pp. 693-708, 1993, and "Feedback
Control of Congestion in Packet Switching Networks: The Case of Multiple
Congested
Nodes", International Journal of Communication Systems, vol. 10, no. S, pp.
227-246,
1997. Their ER allocation algorithm is represented as:
r[k+ 1]= r[k]- ~ ai(q[k- i]- qT)- ~ ~~r[k- j] . . . . . (1),
=o )=o
where r[k] is the ER calculated by the switch at the discrete time k, q[k] is
per-
class ABR queue length at the time k, qT is a target queue length, ai and (3j
are
controller gains, tmax is the largest RTD of an ABR VC, and I is an arbitrary
constant
greater than 0.
Despite its solid theoretical foundation, the practical use of the above
algorithm
is limited by its high degree of implementation complexity. The shortcomings
and the
limitations of the algorithm are described in A. Kolarov and G. Ramamurthy, "A
Control
Theoretic Approach to the Design of Close Loop Rate Based Flow Control for
High
Speed ATM Networks", Proc., IEEE INFOCOM'97, vol. l, pp. 293-301, 1997. It is
purported that in the ER allocation algorithm, the ER terms should be
maintained at
present and in the past, up to time lags imax, and the number of floating
point
multiplications should be performed in every discrete time slot.
Thereafter, S. Chong has proposed a simpler control-theoretic ER allocation
algorithm ("Second-Order RateOBased Flow Control with Dynamic Queue Threshold
for
High-Speed Wide-Area ATM Networks", preprint 1997). Also, A. Elwalid
("Analysis
of Adaptive Rate Based Congestion Control for High-Speed Wide-Area Networks",
Proc.
IEEE ICC'95, pp. 1948-1953, 1995) has proposed a continuous-time ER allocation
algorithm, which is represented by the following equation:
r(t) - _Ar(t)_B(q(t)-qT), A, B > 0 . . . . . (2),
and obtained the necessary and sufficient condition for the closed-loop system
to be
asymptotically stable when the RTDs of all the VCs are identical. Chong has
extended
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-4-
the stability analysis of this algorithm to the general case with arbitrary
RTDs.
Meanwhile, S. Chong, R. Nagarajan, and Y. T. Wang proposed a more
simplified ER allocation algorithm ("Designing Stable ABR Flow Control with
Rate
Feedback and Open-Loop Control: First-Order Control Case", Performance
Evaluation,
vol. 34, no. 4) that can readily achieve an asymptotically stable system,
which is
expressed by,
r(t) ° [-K(q(t)-qT)]~, K > 0 . . . . . (3)
where [X]; = max[x, 0] indicates that the greater of x and 0 should be
selected.
In the algorithm (2), two other stabilization conditions have been induced.
One
of them is a sufficient condition for a general case with heterogeneous RTDs
and the
other is a necessary and sufficient condition for a particular case with
homogeneous
RTDs. Yet, a common drawback of the algorithms (2) and (3), as compared to the
algorithm ( 1 ), is that unless controller gains and the queue length
threshold are properly
chosen according to the instantaneous knowledge on the available bandwidth to
the ABR
traffic and the fraction of the available bandwidth utilized by remotely
bottlenecked VCs,
the ABR queue length can converge to zero which is undesirable since at this
equilibrium point the link can not be fully utilized.
The remotely bottlenecked VCs cannot fairly share the link as the bottleneck
occurnng at another link if the transmission rates of the VCs are not limited
by their
PCRs (Peak Cell Rates). In contrast, if the algorithm (1) is applied, there
exists no such
an undesirable equilibrium point.
The applicant of the present invention also proposed an ABR service algorithm
which is described in the Provisional application No. 60/157,420 entitled, "A
Scalable
and Stable Explicit Method for Max-Min Flow Control with Guarantees", which
was
filed on October 2, 1999 with the United States Patent and Trademark Office.
The above algorithm needs to be implemented in hardware with a minimal
required memory capacity or hardware, and the operation accuracy is required
to make
the algorithm work.
SUMMARY OF THE INVENTION
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-5-
It is, therefore, an object of the present invention to provide an ABR service
engine in a packet switching system, for which the ABR service algorithm can
be
implemented with minimal hardware or memory requirements and produce accurate
operation results.
S The above object of the present invention can be achieved by providing an
ABR
(Available Bit Rate) service engine in a packet switching system. In the AVR
service
engine, a forward cell processing unit generates a first start signal and
extracts CCR
(Current Cell Rate) and MCR (Minimum Cell Rate) from a forward RM (Resource
Management) cell upon receipt of the forward RM cell. A locally bottlenecked
virtual
circuit number (~Q~) estimation unit determines whether (CCR-MCR) is less than
ER
(Explicit Rate) upon receipt of the first start signal, determines that the
received RM cell
contributes to ~Q~ if (CCR-MCR) is less than ER, accumulates the degree of
contribution
by dividing a forward RM cell transmission period by {first period x CCR) and
adding
the division result to a previous contribution degree, and calculates ~Q~ by
adding
(accumulated contribution degree x ( 1- low pass filtering parameter)) and
((previous ~Qf
+ total ~Q~) x low pass filtering parameter) upon receipt of a second start
signal. An ER
engine calculates the ER by subtracting (((average queue length - previous
average
queue length) x first gain) = calculated ~Q~) + ((average queue length -
target queue
length) x ({second gain x third start signal period) = calculated ~Q~)) from a
previous ER,
upon receipt of a third start signal. A backward cell processing unit
determines whether
the ER calculated by the ER engine is less than the sum of ER and MCR
extracted from
a backward RM cell upon receipt of the backward RM cell, then writes the
calculated ER
in the backward RM cell if the calculated ER is less than the sum of ER and
MCR. A
timer feeds the second start signal to the ~Q~ estimation unit every first
period and the
third start signal to the ER engine every second period.
BRIEF DESCRIPTION OF THE DRAWINGS
The above and other objects, features, and advantages of the present invention
will become more apparent from the following detailed description when taken
in
conjunction with the accompanying drawings in which:
FIG. 1 illustrates the configuration of a packet switching network according
to
the preferred embodiment of the present invention;
FIG. 2 is a block diagram of an I/O card for a switch shown in FIG. 1;
FIG. 3 is a block diagram of an ABR service engine according to the preferred
embodiment of the present invention;
FIG. 4 illustrates the structure of an RM cell;
FIG. S is a block diagram of a forward cell processing unit shown in FIG. 3;
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-6-
FIG. 6 is a block diagram of a forward cell decoder shown in FIG. 5;
FIG. 7 is a block diagram of a cell element counter shown in FIG. 6;
FIGS. 8 and 9 illustrate cell buffering;
FIG. 10 is a block diagram of an EFCI marker shown in FIG. 6;
FIG. 11 is a block diagram of a ~Q~ estimation unit shown in FIG. 3;
FIG. 12 is a flowchart illustrating the operation of a 8 computation decider
and
a S calculator shown in FIG. 11;
FIG. 13 is a flowchart illustrating the operation of the ~Q~ estimation unit
shown
in FIG. 11;
FIG. I 4 is a block diagram of an ER engine shown in FIG. 3;
FIG. I 5 is a block diagram of a gain selector shown in FIG. 14;
FIG. 16 is a flowchart illustrating the operation of the gain selector shown
in
FIG. 15;
FIG. 17 is a flowchart illustrating the operation of the ER engine shown in
FIG.
3;
FIG. I 8 is a block diagram of a backward cell processing unit shown in FIG.
3;
FIG. 19 is a block diagram of a backward cell decoder shown in FIG. 18; and
FIG. 20 is a block diagram of an Nr corrector.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
A preferred embodiment of the present invention will be described hereinbelow
with reference to the accompanying drawings. For the purpose of clarity, well-
known
functions or constructions are not described in detail since they would
obscure the
invention in unnecessary detail.
FIG. 1 illustrates the configuration of a packet switching network for
implementing the ABR service according to the preferred embodiment of the
present
invention. With reference to FIG. 1, the packet switching network includes a
plurality of
switches E1, E2, and E3. Each switch is connected to a plurality of sources.
In the
drawing, the first switch E1 is connected to a first through a Nth sources, S1
to SN.
Each source transmits/receives data through a switch connected thereto. Data
transmitted from the source reaches a destination in a so-called VC path
having a
plurality of nodes.
In the ABR service, information relating to the bandwidth availability of the
network is conveyed to the source through a RM cell. Here, the processing of
the
source-generated RM cells falls into the scope of the embodiment of the
present
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
invention. A source-generated RM cell is transmitted to a destination through
a VC path.
The transmission direction of the cell is forward. Upon receiving the forward
RM cell,
the destination processes the forward RM cell and transmits back to the source
through
the backward RM cell. Switches are provided to write the allowed bandwidth
information in the backward RM cell. Then, the source adapts its rate to
changing
network conditions based on the received bandwidth information. Here, the
bandwidth-
related information includes EFCI which provides information about the
available
bandwidth, CI (Congestion Indication) that allows a network element to
indicate that
there is congestion in the network, and NI (No Increase) that is used to
prevent a source
from increasing its ACR (Allowed Cell Rate). EFCI in a data cell indicates
congestion.
As described above, a switch calculates a bandwidth available for the ABR
service, writes the calculated available bandwidth information on a backward
RM cell,
then transmits the backward RM cell to a source. An ABR engine serving this
function
1 S is provided in an input/output (I/O) port card of the switch.
FIG. 2 is a block diagram of the I/O port card. As shown in FIG. 2, the I/O
port
card 100 includes an I/O buffer management unit 102, an ABR service engine
104, and
an output interface 106. The I/O buffer management unit 102 is connected to
the switch
and responsible for I/O queuing. According to the embodiment of the present
invention,
the I/O buffer management unit 102 applies a queue write signal to the ABR
service
engine 104 for queue writing and a queue read signal to the ABR service engine
104 for
queue reading. According to the embodiment of the present invention, the ABR
service
engine 104 processes the ABR algorithm and its related operations for the ABR
service
based on various parameters received from a microprocessor 108. The output
interface
106 acts as a user network interface at the ATM layer.
FIG. 3 is a block diagram of the ABR service engine 104. As shown in FIG. 3,
a forward cell processing unit 200 receives a forward RM cell and provides a
first start
signal to a ~Q~ estimation unit 202 (Q represents the number of locally
bottlenecked VCs
and ~Q~ represents the cardinality/number of Q) if it confirms that the
received RM cell is
forward, source-generated, and free of CRC errors. ~Q~ estimation unit 202
assumes the
queuing in the output port. The forward cell processing unit 200 extracts the
CCR
(Current Cell Rate) and the MCR (Minimum Cell Rate) from the forward RM cell
and
feeds them to the ~Q~ estimation unit 202. During EFCI congestion, the forward
cell
processing unit 200 marks the EFCI in a data cell among input forward cells.
It should
be noted that a floating-point number system is used to provide precision and
range in
obtaining ER. The floating-point number guarantees sufficient precision in
order to
prevent the problem associated with the feedback of ER value. Thus, the
floating-point
CA 02351352 2001-05-23
WO O1/Z6306 PCT/KR00/01099
_g_
number system includes all range of numbers that can be computed in the ER
engine.
Upon receipt of the first start signal, the (Q~ estimation unit 202 determines
whether the received RM cell contributes to ~Q~. That is, whether the
difference between
the CCR and the MCR retrieved from the received RM cell exceeds a current ER
(8)
received from the ER engine 208. If the condition is satisfied, the RM cell is
said to
contribute to the ~Q~. Then, the ~Q~ estimation unit 202 calculates its
contribution degree
(8), accumulates 8 for use in ~Q~ estimation until it receives a second start
signal, which
is generated periodically from a timer. Here, 8 represents the updated ER
measured by
the ER engine 208 at a predetermined time interval. The ~Q~ estimation unit
202
estimates ~Q~ upon receipt of the second start signal and feeds the estimated
~Q~ to the ER
engine 208. In estimating the ~Q~, the ~Q~ estimation unit 202 uses 8 received
from the
ER engine 208. 8 is the margin to avoid the underestimation of the number of
locally
bottlenecked VCs particularly near the steady state. As the system approaches
the steady
state, the CCR of a locally bottlenecked VC stays around the sum of the MCR
and the
common ER. Thus, without the margin 8 the VC could be counted wrongly as a
remotely bottlenecked VC even for a small perturbation in the CCR. By having
this
margin, however, this type of underestimation can effectively be avoided.
Through
simulations, it is found out that 8 = 0.9 is the recommended choice.
The embodiment of the present invention is characterized in that the node
keeps
updating the ER periodically regardless of arrival of RM cells. The benefit of
the
background calculation is that the latest ER prepared by the ER engine 208 is
directly
provided to the estimator unit 202, upon arrival of an RM cell in the
corresponding node.
The ER engine 208 calculates the ER upon receipt of a third start signal that
is
generated periodically from the timer 210 and feeds the calculated ER to a
backward cell
processing unit 212 so that the backward cell processing unit 212 can write
the
calculated ER in a backward RM cell.
A queue counter 206 provides the current queue length and the number of queue
variations to the ER engine 208 using the queue write signal and the queue
read signal
received from the I/O buffer management unit 102. The queue counter 206 feeds
the
queue length to the forward cell processing unit 200 to allow the forward cell
processing
unit 200 to detect the EFCI congestion and write the EFCI mark. Also, the
queue
counter 206 feeds the queue length to the backward cell processing unit 212 to
allow the
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-9-
backward cell processing unit 212 to detect "congestion" and "serious
congestion" for
RR service and to write NI (No Increase) and CI (Congestion Indication) marks
in the
backward RM cell.
The backward cell processing unit 212 determines whether the sum of the ER
and MCR of a received backward RM cell is less than the ER transmitted from
the ER
engine 208. If the sum is less than the ER delivered from the ER engine 208,
the
backward cell processing unit 212 writes the ER of the ER engine 208 in the
backward
RM cell. In addition, the backward cell processing unit 212 detects congestion
and
serious congestion based on the received queue length and the NI and CI marks
of the
backward RM cell when detecting the RM cell. After completing the ER writing
and NI
and CI markings, the backward cell processing unit 212 calculates CRC for the
backward RM cell and writes the CRC in the backward RM cell.
The timer 210 generates the second start signal every first predetermined
period
and provides it to the ~Q~ estimation unit 202. The timer 210 also generates
the third start
signal every second predetermined period and provides it to the ER engine 208.
A microprocessor interface 204 provides parameters received from the
microprocessor 108 to the ~Q~ estimation unit 202 and the ER engine 208. The
parameters are latched in registers, which is a well-known technique and will
not be
described herein.
Now a detailed description will be made of the ABR service engine 104 in the
following sections.
FIG. 4 illustrates the structure of an RM cell. As shown in FIG. 4, the RM
cell
is comprised of ATM Header, Protocol Identifier, Message Type, ER, CCR, MCR,
Queue Length, Sequence Number, and CRC. ATM Header has PTI (Payload Type
Identifier) that defines a payload type. One PTI bit is used for EFCI. In the
Message
Type field, DIR indicates which direction of data flow is associated with the
RM cell,
BN indicates whether the RM cell is a backward explicit congestion
notification (BECN)
cell (i.e., non-source generated) or not, CI (Congestion Indication) allows a
network
element to indicate that there is congestion in the network, and NI (No
Increase) is used
to prevent a source from increasing its ACR (Allowed Cell Rate). The CCR
(Current
Cell Rate) field is set by the source to its current ACR when the source
generates the RM
cell. The MCR (Minimum Cell Rate) field indicates the minimum allocated
bandwidth
of each VC when a source generates the RM cell. ER is an available bandwidth
written
in a backward source-generated RM cell by the ABR service engine as the RM
cell
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
- 10-
passes through the switch. Only when the calculated available bandwidth of the
ABR
service engine is less than the existing available bandwidth, the former value
is written
in the ER field. Therefore, the smallest available bandwidth in the VC path is
conveyed
to the source.
FIG. 5 is a block diagram of the forward cell processing unit 200 that deals
with
forward RM cells.
With reference to FIG. 5, a UTOPIA interface 300 of the forward cell
processing unit 200 provides the UTOPIA interfacing. The Universal Test &
Operations
Physical Layer Interface for ATM (UTOPIA) defines the interface between the
physical
layer and the upper layer module, such as the ATM layer, is followed in the
input of the
cell decoder and the output of the cell encoder. A forward cell decoder 302
receives a
forward cell and an SOC (Start of Cell) signal and checks whether the forward
cell is an
RM cell or a data cell.
If the input is a RM cell, the forward cell decoder 302 determines whether the
RM cell is source-generated or not. In the case of a source-generated RM cell,
the
forward cell decoder 302 performs CRC on the RM cell. If no CRC errors are
detected,
it generates a first start signal, extracts CCR and MCR from the RM cell, then
provides
the first start signal and the CCR & MCR to the ~Q~ estimation unit 202. A CRC
is
provided to check for the CRC of the forward cell and sends the CRC check
result to the
forward cell decoder 302. Upon receiving a congestion signal from a congestion
detector 306, the forward cell decoder 302 marks EFCI in the received forward
data cell.
The congestion detector 306 compares the current queue length with the EFCI
congestion threshold gEFCI value and generates the EFCI congestion signal to
the
forward cell decoder 302 if the current queue length is greater than gEFCI.
FIG. 6 is a detailed block diagram of the forward cell decoder 302. Referring
to
FIG. 6, a cell element counter 400 starts to count forward clock pulses when
the SOC
(Start of Cell) signal of UTOPIA is generated, outputs a cell count, and is
reset by a reset
signal generated whenever the cell count is completed for one RM cell. The
transfer of a
cell is synchronized by the SOC signal. A 4 or 5-byte header may be added
before the
cell. To make a cell count indicate PTI, DIR & BN, CCR, and MCR of the RM cell
in
position despite the header addition, the cell element counter 400 subtracts
cell type/2
from the cell count. A cell buffer multiplexer (MUX) 414 arranges input
forward cells
and outputs them.
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-11-
FIG. 7 is a detailed block diagram of the cell element counter 400. Referring
to
FIG. 7, a flip-flop D has an input terminal D connected to a power supply, a
clock
terminal for receiving the SOC signal, and a reset terminal for receiving the
reset signal.
The flip-flop D generates a cell start signal that becomes high upon receipt
of the SOC
signal and low upon receipt of the reset signal. The cell start signal and the
reset signal
are applied to an AND gate (AND). The AND gate generates a signal for
resetting a
counter (CNT) when both signals are low at the same time. The counter counts
forward
clock pulses and is reset when the cell start signal and the reset signal are
simultaneously
generated. The output of the counter and cell type/2 are applied to the input
of a
subtracter (AD). The subtracter subtracts the cell type/2 from the output of
the counter
and outputs the subtraction result as a cell count. The cell type/2 may be
provided by the
microprocessor 108.
Returning back to FIG. 6, the generated cell count by the cell element counter
400 is applied to a comparator 402. The comparator 402 generates a PTI clock
signal
when the cell count indicates the position of PTI in the forward RM cell, a
DIR BN
clock signal when it indicates the position of Message Type, a CCR clock
signal when it
indicates the position of CCR, and an MCR clock signal when it indicates the
position of
MCR. When the cell count indicates the end of the forward RM cell, an End
clock
signal is generated. The PTI, DIR_BN, CCR, MCR, and End clock signals are
synchronized to the forward clock signal through a first register unit 404. An
inverter
(INV) inverts the End clock signal received from the first register unit 404
and provides
the inverted signal as the reset signal to the cell element counter 400. The
PTI, DIR BN,
CCR, and MCR clock signals of the first register unit 404 are applied to a PTI
register
406, a DIR BN register 408, a CCR register 410, and an MCR register 412,
respectively.
If the added header is four bytes, the cell buffer MUX 414 reads 16 cell bits
from a second register 420, and if the added header is five bytes, it reads 8
cell bits from
the second register 420 and 8 bits from a first register 418. Thus, cells are
arranged
regardless of a 4-byte header or a 5-bit header.
FIGS. 8 and 9 illustrate RM cell buffering in the first and second registers
418
and 420. An RM cell is buffered in the first and second registers 418 and 419
at a byte
level. In the case of a 4-byte header, the first two bytes are buffered in the
registers in
alignment, as shown in FIG. 8. On the other hand, in the case of a 5-byte
header, the
first two bytes of the RM cell are buffered in non-alignment, as shown in FIG.
9.
Headers are identified by cell type. If cell type is 0100, this indicates that
the 4-byte
header is added. If cell type is O1 Ol,.this indicates that the 5-byte header
is added. That
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-12-
is, the header of the RM cell can be identified by checking the LSB (Least
Significant
Bit) of the cell type.
Thus, the cell buffer MUX 414 receives the LSB of the cell type. If the LSB is
0, the cell buffer MUX 414 reads 16 bits from the second register 420 and if
the LSB is l,
the cell buffer MUX 420 reads 8 bits from the second register 414 and 8 bits
from the
first register 418.
The cell buffer MUX 414 arranges the read RM cell bits and outputs the RM
cell to a second register unit 416. The second register unit 416 outputs the
received RM
cell in synchronization to the forward clock signal to the PTI register 406,
the DIR BN
register 408, the CCR register 410, and the MCR register 410. The PTI register
406, the
DIR BN register 408, the CCR register 410, and the MCR register 412 latch
corresponding data received at the time when the PTI, DIR BN, CCR, and MCR
clock
signals are respectively generated. As a result, the PTI register 406, the DIR
BN
register 408, the CCR register 410, and the MCR register 412 latch PTI,
Message Type,
CCR, and MCR of the RM cell and the CCR and MCR are fed to the ~Q) estimation
unit
202.
A RM cell detector 428 receives the Message Type and determines whether the
corresponding cell is a forward source-generated RM cell by checking the DIR
and BN
of Message Type. If the cell is a forward source-generated RM cell, the RM
cell detector
428 generates an RM start signal and feeds it to an EFCI marker 430 and an AND
gate.
The AND gate generates the first start signal when a CRC error detection
signal and the
RM start signal are concurrently generated and the generated first start
signal is provided
to the ~Q~ estimation unit 202.
On the other hand, if the input cell is a data cell (i.e., the RM start signal
is not
received) and the congestion signal and the cell start signal are generated,
the EFCI
marker 430 marks EFCI in the PTI of the cell header. If a header is added to
the cell, the
PTI may pass through the first to fifth registers 418 to 426 as lower eight
bits or upper
eight bits of the cell. In this case, the EFCI marker 430 adaptively marks the
EFCI,
which will be described with reference to FIG. 10. When a 4-byte header is
added to the
cell, the PTI passes through the first to fifth registers 418 to 426 as the
upper eight bits.
If a 5-byte header is added to the cell, the PTI passes through the first to
fifth registers
418 to 426 as the lower eight bits. A first AND gate (AND 1 ) of the EFCI
marker 430
provides 1 to a first OR gate (OR1 ) when the congestion signal and the LSB of
the cell
type are 1 s concurrently. The first OR gate OR-gates the EFCI bit of the PTI
with the
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-13-
output of the first AND gate. That is, the EFCI of the PTI that has passed as
the upper
eight bits is marked to 1 when the congestion signal and the LSB of the cell
type are 1 s
at the same time. A second AND gate (AND2) of the EFCI marker 430 provides 1
to a
second OR gate (OR2) when the congestion signal and the LSB of a cell type
inverted by
the inverter are 1 s at the same time. The second OR gate OR-gates the EFCI
bit of the
PTI with the output of the second AND gate. That is, when the congestion
signal is 1
and the LSB of the inverted cell type is 0, the EFCI of the PTI that has
passed as the
lower eight bits is marked to 1.
The first to fifth registers 418 to 426 buffer the received forward cell along
with
the SOC signal and an Empty signal.
Now, the structure and operation of the ~Q~ estimation unit 202 for estimating
~Q~ using the first start signal and the CCR & MCR will be described
hereinbelow with
1 S reference to FIG. 11.
The ~Q' estimation unit 202 is comprised of a 8 computation decider 500 for
deciding whether an RM cell contributes to ~Q~ upon receiving the first start
signal from
the forward cell processing unit 200, a 8 calculator 502 for calculating a
contribution
degree b when it is determined that the RM cell contributes to ~Q~ and
accumulates it to
the previous value, and a ~Q~ calculator 504 for calculating an estimated ~Q)
using the
accumulated S.
The b computation decider 500 checks whether K*ER received from the ER
engine 208 is less than the subtraction of the CCR (Current Cell Rate) and the
MCR
(Minimum Cell Rate). If the K*ER is less than the difference of CCR-MCR, it
determines that the RM cell contributes to ~Q~ and generates a control signal
S for
controlling 8 to be calculated. A first register 506 in the 8 computation
decider 500
provides the K*ER received from the ER engine 208 in synchronization with the
SOC
signal to a number system converter 508. The number system converter 508
converts
the K*ER to a 32-bit floating point number and outputs the floating point
number as ER
to an input terminal B of a first adder 510. The first adder 510 receives the
MCR and ER
respectively through its input terminals A and B, adds the MCR and ER, and
outputs the
sum to a B input terminal of a comparator 512 through its output terminal C.
The
comparator 512 receives the CCR and the sum of MCR and ER through its input
terminals A and B, respectively, compares the sum with CCR, then provides the
comparison result to an And gate 514. If the sum of MCR and ER is less than
CCR, the
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
- 14-
AND gate 514 outputs a high signal to a second register 516 upon receiving the
first start
signal. The second register 516 outputs the signal received from the AND gate
514 as
the signal S upon receipt of a signal END_I clk. That is, the signal S is l
and applied to
the 8 calculator 502 when there is no CRC error in a received cell and when
K*ER is
S less than CCR-MCR.
The 8 calculator 502 calculates and accumulates the contribution degree b of
RM cells received for the first period {i.e., a ~Q~ estimation period) to ~Q~
by:
N ~,
~ - ~PREV + ls~ period x CCR ~ ~ ~ ~ ~ ~ ~ {4)'
where Nrm is a forward RM cell transmission period negotiated upon
establishment of a
connection. Nrm/first period {being the period of the second start signal) may
be
provided by the microprocessor 108.
A number system converter 518 in the 8 calculator 502 converts the CCR
received from the forward cell processing unit 200 to a 32-bit floating point
number. A
divider 520 receives the converted CCR and the Nrm/second start signal period
upon the
generation of the MCR clock signal and divides the Nrm/second start signal
period by
the CCR. A third register 522 latches the output of the divider 520 on
receiving a DONE
signal from the divider 520. A second adder 524 adds the previous b 8prev and
the
output of the third register 522 upon receipt of the signal DONE from the
divider 520. A
fourth register 526 latches the output of the second adder 524 according to a
clock signal
from an AND gate 528 when a DONE signal received from the second adder 524 and
the
signal S received from the AND gate 528 are 1 s at the same time, and outputs
the latched
value as 8. The 8 is fed to the ~Q~ calculator 504 and as 8prev to the second
adder 524.
Upon receipt of the signal S, the 8 calculator 502 does not start to calculate
8 but outputs
the calculated 8, to thereby implement 8 computation in real time.
The divider 520 and the second adder 524 are reset by a reset signal generated
through an inverter 530 and an AND gate 532 when the reset signal and the
second start
signal are simultaneously generated. Therefore, the accumulated b is reset to
0 every
time the second start signal is generated.
Referring to FIG. 12, the operation of the 8 computation decider 500 and the 8
calculator 502 will be described. Upon receipt of a RM cell, the b computation
decider
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
- 15-
500 determines whether K*ER is less than CCR-MCR in step 600. If K*ER is less
than
CCR-MCR, the 8 calculator 502 calculates and then accumulates 8 in step 602.
Returning to FIG. 11 B, a controller 534 of the IQ~ calculator 504 activates
the
IQI calculator 504 upon receiving the second start signal and provides overall
control to
the ~QI calculator 504. A 1-a calculator 536 subtracts a low pass filtering
parameter a
of a IQI generation formula from 1. A register unit 538 latches nr being a
total IQ~, a,
1-a, a previous IQI IQIprev, and the computation results of a second selector
546. A first
selector 540 selects some of a plurality of values received from the register
unit 538 and
transmits the selected values to a multiplier 542 or a third adder 544 under
the control of
the controller 534. The multiplier 542 and the third adder 544 multiply and
add their
received outputs from the first selector 540 and transmit the operation
results to the
second selector 546. The second selector 546 provides the outputs of the
multiplier 542
and the third adder 544 to a Iimiter 548 or the register unit 538 under the
control of the
controller 534. The limiter 548 simply outputs a value received from the
second selector
546 as IQ~ if the received value is between 0 and nr. If the received value is
less than 0,
the limner 548 limits the value to 0 and outputs 0 as IQI. If the received
value is greater
than nr, the limner 548 limits the value to nr and outputs nr as IQI. The
output of the
limiter 548 is fed as ~Qlprev to the register unit 538.
The controller 534 controls the first and second selectors 540 and 546 to
compute ~QI by:
QI = (IQ~prev + nr) x a + b x (1-a) . . . . . (5)
This control operation will be described with reference to FIG. 13. In FIG.
13,
the controller 534 controls the first selector 540 to feed nr and ~Q~prev to
the third adder
544 and (1-a) and b to the multiplier 542 in step 1. The third adder 544 adds
nr and
IQlprev and feeds (IQlprev + nr) to the second selector 546. The multiplier
542
multiplies 8 by ( 1-a) and feeds 8 x ( 1-a) to the second selector 546. The
controller 534
controls the second selector 546 to feed back the outputs of the third adder
544 and the
multiplier 542 to the register unit 538.
In step 2, the controller 534 controls the first selector 540 to provide
(IQlprev +
nr) and a latched in the register unit 538 to the multiplier 542. Then, the
multiplier 542
multiplies (IQ~prev + nr) by a and provides (~Qlprev + nr) x a to the second
selector 546.
The controller 534 controls the second selector 546 to feed (IQlprev + nr) x a
to the
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
- 16-
register unit 538.
In step 3, the controller 534 controls the first selector 540 to provide
(~Q~prev +
nr) x a and 8 x (1-a) latched in the register unit 538 to the third adder 544.
Then, the
third adder 544 adds (~Q~prev + nr) x a and 8 x (1-a) and provides (~Q~prev +
nr) x a + 8
x (1-a) as ~Q~ to the second selector 546. The controller 534 controls the
second selector
546 to feed ~Q~ to the limner 548.
As stated above, since ~Q~ is computed not in real time but every first
period, the
controller 534 repeatedly reuses the third adder 544 and the multiplier 542 in
the above
steps in order to decrease hardware requirements.
The limiter 548 limits ~Q~ to a value between 0 and nr and outputs a final
~Q~.
The final ~Q~ is applied to the ER engine 208.
Arithmetic units for floating point calculation may be used as the first to
third
adders, 510, 522, and 544 and the multiplier 542 in the ~Q~ estimation unit
202 in order to
increase computation accuracy.
FIG. 14 is a block diagram of the ER engine 208. The ER computation using
the ~Q~ received from the ~Q~ estimation unit 202 will be described refernng
to FIG. 14.
In FIG. 14, a number system converter 700 in the ER engine 208 converts the
target queue length qT, the second period ~, and a comparison margin K to be
multiplied
by ER received from the microprocessor I 14 through the microprocessor
interface 204
to 32-bit floating point numbers and feeds them to a first selector 704. The
number
system converter 700 also converts ~Q~ received from the ~Q~ estimation unit
202, the
number of queue variations and queue length received from the queue counter
206, and
the variation of Nr received from an Nr corrector (not shown), ndiff to 32-bit
floating
point numbers and feeds them to the first selector 704.
A gain selector 702 receives a queue length gTH for gain selection and gains
A0, Al, B0, and B1 from the microprocessor 114 and the current queue length q
from a
register unit 714 and compares gTH with q. If q is less than gTH and Aland B1
have
never been selected as gains A and B, the gain selector 702 selects AO and BO
as A and
B and provides them to the first selector 704. If q is less than gTH, and
Aland B1 have
been selected as gains A and B, the gain selector 702 selects A 1 and B 1 as A
and B and
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
- 17-
provides them to the first selector 704. If q is greater than gTH, the gain
selector 702
selects A 1 and B 1 as A and B and provides them to the first selector 704.
FIG. 15 is a block diagram of the gain selector 702. The operation of the gain
selector 702 will be described with reference to FIG. 15.
In FIG. 1 S, a subtracter 800 subtracts gTH from q. A comparator 802
determines whether the subtraction result is less than 0. If the subtraction
result is less
than 0, the comparator 802 outputs 0 and if the subtraction result is greater
than 0, the
comparator $02 outputs I . The output of the comparator 802 is applied as a
clock signal
to a flip-flop 804. The flip-flop 804 is reset at an initialization state,
outputs Os, and then
outputs 1 s received through its input terminal through its output terminal at
rising edges
of a clock signal. Since q is increased from 0 gradually, the flip-flop 804
outputs Os until
q reaches gTH and then outputs I s regardless of q. The output of the flip-
flop 804 is
applied as a select signal to first and second selectors 806 and 808. The
first and second
selectors 806 and 808 receive AO & A 1 and BO & B 1, respectively. If the
output of the
flip-flop 804 is 0, they output AO and BO as A and B. If the output of the
flip-flop 804 is
1, they output Aland B1 as A and B.
The above operation of the gain selector 702 will be described with reference
to
FIG. 16.
In FIG. I 6, the gain selector 702 determines whether q is less than gTH in
step
900. If q is less than gTH, the gain selector 702 proceeds to step 902.
Otherwise, it
jumps to step 904. In step 902, the gain selector 702 checks whether the
current state is
an initialization state where Aland B1 are not selected as A and B. In the
initialization
state, the gain selector 902 selects AO and BO as A and B in step 906.
Different gains are used in an initialization state and a non-initialization
state in
order to bring ER to a steady state rapidly in the initialization state where
the ER is
unstable and then minimize the oscillation of the ER at the steady state.
In FIG. 14, the first selector 704 provides qr, D, ~Q~, queue variation
number,
queue length, and ndiff in the floating point format received from the number
system
converter 700, A and B received from the gain selector 702, and some of the
operation
results received from the register unit 714 to a multiplier 706, a divider
708, and an
adder 710 under the control of an ER engine controller 730. The multiplier
706, the
divider 708, and the adder 710 subject their received values to
multiplication, division,
and addition and output operation results to a second selector 712. The second
selector
CA 02351352 2001-05-23
WO 01/26306 PCT/IQt00/01099
- 18-
712 transmits the operation results of the multiplier 706, the divider 708,
and the adder
710 to the register unit 714 under the control of the ER engine controller
730. The
register unit 714 is comprised of a first register portion 716, a second
register portion
722, and a third register portion 728. The first register portion 716 includes
a first
register 718 for latching the average queue length q received from the second
selector
712 and outputting the latched q to the first selector 704 and the gain
selector 702 and a
second register 720 for latching the previous q qprev and outputting qprev to
the first
cell selector 704. The second register portion 722 includes feedsback
operation results
received from the second selector 712 to the first selector 704. The third
register portion
728 includes a third register 724 for latching ER delivered from the second
selector 712
and outputting the latched ER to the first selector 704 and a fourth register
726 for
transmitting the ER latched in the third register 724 as the previous ER
ERprev to the
first selector 704.
The ER engine controller 730 controls the first and second selectors 704 and
712 so that the multiplier 706, the divider 708, and the adder 710 compute ER
by:
A j B4
ER= ERpREV - ~~) X lq- qPREY~- IQ X ~q- qt~ . . . . . (6).
The control operation of the ER engine controller 730 for ER computation in
the multiplier 706, the divider 708, and the adder 710 will be described with
reference to
FIG. 17.
Referring to FIG. 17, in step l, the ER engine controller 730 controls the
first
selector 704 to send the queue variation number and the queue length received
from the
number system converter 700 to the divider 708 and ~Q~ and ndiff to the adder
710. Then,
the divider 708 divides the queue length by the queue variation number and
transmits the
division result as q to the second selector 712. The adder 710 adds ~Q~ and
ndiff and
sends (~Q~+ndiff) as corrected ~Q~ to the second selector 712. The ER engine
controller
730 controls the second selector 712 to feed back q received from the divider
708 to the
first selector 704 through the first register 714 and the corrected ~Q~
received from the
adder 710 to the first selector 704 through the second register portion 722.
Here, q is
provided to the gain selector 702 so that the gain selector 702 can select A
and B by
comparing q with gTH.
In step 2, the ER engine controller 730 controls the first selector 704 to
send O
received from the number system converter 700 and the gain B selectively
received from
the gain selector 702 to the multiplier 706. The multiplier 706 multiplies 0
by the gain
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
- 19-
B and transmits the product ( 1 ) to the second selector 712. The ER engine
controller
730 controls the second selector 712 to feed back ( 1 ) to the first selector
704 through the
second register portion 722.
In step 3, the ER engine controller 730 controls the first selector 704 to
provide
q latched in the first register 718 and qprev latched in the second register
720 to the
adder 710 and (1) and the corrected ~Q~ to the divider 708. Then, the adder
710 subtracts
qprev from q and provides the subtraction result (2) to the second selector
712. The
divider 708 divides ( 1 ) by the corrected ~Q~ and transmits ( 1 )/corrected
~Q~ to the second
selector 712. The ER engine controller 730 controls the second selector 712 to
feed back
{2) to the first selector 704 through the second register portion 722.
Computation time in the divider 708 is longer than that in the adder 710.
Hence,
although (2) is completed in the adder 710, the divider 708 continues its
operation.
In step 4, the ER engine controller 730 controls the first selector 704 to
provide
q latched in the first register 718 and qr received from the number system
converter 700
to the adder 710. Then, the adder 710 subtracts qr from q and transmits the
subtraction
result (3) to the second selector 712. The ER engine controller 730 controls
the second
selector 7I2 to feed back (3) to the first selector 704 through the second
register portion
722.
In step S, the ER engine controller 730 controls the first selector 704 to
provide
(3) latched in the second register 722 and the gain A received from the gain
selector 702
to the multiplier 706. The multiplier 706 multiplies (q-qprev) by A and
provides the
product (4) to the second selector 712. The ER engine controller 730 controls
the second
selector 712 to feed back (4) to the first selector 704 through the second
register portion
722.
In steps 2 through 5, the divider 708 divides (1) by corrected ~Q~ and
provides
the division result (5) to the second selector 712. The ER engine controller
730 controls
the second selector 712 to feed back (1)/~Q~ to the first selector 704 through
the second
register portion 722.
In step 6, the ER engine controller 730 controls the first selector 704 to
provide
(3) and (5) received from the second register portion 722 to the multiplier
706 and {4)
and the corrected ~Q~ received from the second register portion 722 to the
divider 708.
The multiplier 706 multiplies (3) by (5) and provides the product (6) to the
second
CA 02351352 2001-05-23
WO 01/26306 PCTlKR00/01099
-20-
selector 712. The divider 708 divides (4) by the corrected ~Q~ and provides
the division
result (7) to the second selector 712.
The ER engine controller 730 controls the second selector 712 to feed back (6)
and (7) to the first selector 704 through the second register portion 722.
In step 7, the ER engine controller 730 controls the first selector 704 to
provide
(6) and (7) received from the second register portion 722 to the adder 710.
The adder
710 adds (6) and (7) and feeds the sum (8) to the second selector 712. The ER
engine
controller 730 controls the second selector 712 to feed back (7) to the first
selector 704
through the second register portion 722.
In step 8, the ER engine controller 730 controls the first selector 704 to
provide
(8) received from the second register portion 722 and ERprev received from the
fourth
register 728 to the adder 710. The adder 710 subtracts (8) from ERprev and
outputs the
sum as ER to the second selector 712. The ER engine controller 730 controls
the second
selector 712 to feed back ER to the first selector 704 through the third
register 726.
In step 9, the ER engine controller 730 controls the first selector 704 to
provide
ER received from the third register 726 and K received from the number system
converter 700 to the multiplier 706. The multiplier 706 converts ER in the
floating point
format to a 16-bit integer by adding ER and K and outputs the integer as K*ER
through
the second register portion 722. Here, K*ER is the final ER output from the ER
engine
208.
As noted from the above description, ER computation is performed not in real
time but every interval period. Therefore, the multiplier 706, the divider
708, and the
adder 710 are repeatedly used in steps 1 through 9 to reduce hardware
requirements.
Arithmetic units for floating point computation are used as the multiplier
706,
the divider 708, and the adder 710 to increase computation accuracy.
FIG. 18 is a block diagram of the backward cell processing unit 212 for
processing backward RM cells. The configuration and operation of the backward
cell
processing unit 212 will be described referring to FIG. 18.
In FIG. 18, a UTOPIA interface 1000 in the backward cell processing unit 212
provides UTOPIA interfacing. A backward cell decoder 1002 receives the SOC
signal
and a backward cell from the UTOPIA interface 1000 and determines whether the
CA 02351352 2001-05-23
WO 01/26306 PCTIKR00/01099
-21 -
backward cell is a source-generated RM cell. If the received cell is a source-
generated
RM cell, the backward cell decoder 1002 reads ER and MCR from the RM cell and
feeds
them to an ER writing decider 1008. Upon receipt of the ER from the ER
writing, the
backward cell decoder 1002 writes the ER in the RM cell. Also, the backward
cell
decoder 1002 marks NI or CI in the RM cell according to the NI and CI received
from a
congestion detector 1006. The backward cell decoder 1002 receives CRC for the
RM
cell with ER and NI/CI marked from a CRC check and generation unit 1004 and
writes
the CRC in the RM cell. The CRC check and generation unit 1004 detects CRC
errors
from the received backward RM cell, generates CRC for the RM cell with ER and
NI/CI
marked, and transmits the CRC to the backward cell decoder 1002. The
congestion
detector 1006 receives a high queue threshold qHT and a low queue threshold
qLT from
the microprocessor 108. If a queue length is between qHT and qLT, the
congestion
detector 1006 determines that the network is congested and feeds NI=1 and CI=0
to the
backward cell decoder 1002. If the queue length is greater than qHT, the
congestion
1 S detector 1006 determines that the network is seriously congested and feeds
NI=1 and
CI+1 to the backward cell decoder 1002. If the queue length is less than qLT,
the
congestion detector 1006 determines that the network is not congested and
feeds NI=0
and CI=0 to the backward cell decoder 1002. The ER writing decider 1008
determines
whether the sum of the MCR of the input RM cell received from the backward
cell
decoder 1002 and ER received from the ER engine 208 is less than the ER of the
input
RM cell. If the sum is less than the ER of the input RM cell, the ER writing
decider 208
provides the ER delivered from the ER engine 208 to the backward cell decoder
1002.
FIG. 19 is a block diagram of the backward cell decoder 1002. Referring to
FIG. 19, a cell element counter 1100 starts to count backward clock pulses
when the
SOC signal is generated, outputs the count value as a cell count, and is reset
by a reset
signal that is generated when the cell count represents a whole RM cell. A
comparator
1102 generates the PTI clock signal every time the cell count indicates the
position of
the PTI in the RM cell, the DIR_BN clock signal every time the cell count
indicates the
position of Message Type, the ER clock signal every time the cell count
indicates the
position of ER, the MCR clock signal every time the cell count indicates the
position of
MCR, and the END clock signal when the cell count corresponds to the whole
length of
the cell. The PTI, DIR BN, ER, MCR, and END clock signals are output from the
comparator 1102 in synchronization to the backward clock signal through a
first register
unit 1104. An inverter (INV) inverts the EN clock signal received from the
first register
unit 1104 and outputs the inverted signal as the reset signal. The first
register unit 1104
applies the PTI, DIR_BN, ER, and MCR clock signals to a PTI register 1106, a
DIR_BN
register 1108, an ER register 1110, and an MCR register 1112, respectively.
CA 02351352 2001-05-23
WO 01/26306 PCT/KR00/01099
-22-
A cell buffer MUC 1114 reads 16 cell bits from the second register 1120 if a 4-
byte header is added, and 8 cell bits from the second register 1120 and 8 cell
bits from
the first register 1118 if a 5-byte header is added. A second register unit
1116 outputs a
received RM cell in synchronization to the backward clock signal to the PTI,
DIR BN,
ER, and MCR registers 1106, 1108, 1110, and 1112. The above registers latch
their
received data when the PTI, DIR N, ER, and MCR clock signals are generated,
separately. As a result, the registers latch PTI, Message Type, ER, and MCR of
the RM
cell, respectively. An RM cell detector 1132 receives PTI and Message Type to
determine whether the received backward cell is a source-generated backward RM
cell.
An ER writing decider 1008 receives ER and MCR to decide as to whether to
write ER
delivered from the ER engine 208 in the received RM cell.
The RM cell detector 1132 determines whether a corresponding cell is a source-
generated backward RM cell by checking the PTI and DIR & BN included in
Message
Type. In the case of a source-generated backward RM cell, the RM cell detector
1132
generates an RM start signal.
First to fifth registers 418 to 426 buffer receive forward cells and output
buffered SOC and Empty signals as SOC and Enable signals.
An NI & CI marker 1124 is interposed between the third register 1122 and the
fourth register 1126. The NI & and CI marker 1124 marks NI and CI of an RM
cell
buffered between the third and fourth registers 1122 and 1126 with NI and CI
information received from the congestion detector 1006. An ER writer 1128 is
interposed between the fourth and fifth registers 1128 and 1130. The ER writer
1128
writes the ER received from the ER writing decider 1008 in the ER field of an
RM cell
buffered between the fourth and fifth registers 1126 and 1130. NI and CI
markings and
the ER writing are well known and their detailed description is avoided here.
The reason for writing ER in an RM cell buffered between the fourth and fifth
registers 1126 and 1130 is that the RM cell should be buffered during the time
taken for
the ER writing decider 1008 to decide whether the ER is to be written or not
since the
decision is made after reading MCR despite MCR subsequent to ER in position.
In the
preferred embodiment of the present invention, a received backward RM cell is
buffered
using a few registers, thereby preventing unnecessary use of memory.
Meanwhile, the microprocessor 108 may vary Nr without prior notice and
variation of Nr has a great influence on each computation. Therefore, an Nr
corrector
CA 02351352 2001-05-23
WO 01/16306 PCT/KR00/01099
-23-
can be added to the ABR service engine 104.
FIG. 20 is a block diagram of the Nr corrector. Referring to FIG. 20, the
first
register 1200 latches Nr and provides it to a second register 1202 and a
subtracter 1204.
The second register 1202 latches the Nr received from the first register 1200
as the
previous Nr. The subtracter 1204 obtains the variation of Nr, Ndiff by
subtracting the Nr
received from the second register 1202 from the Nr received from the first
register 1200.
A comparator 1206 determines whether Ndiff is 0. If Ndiff is not 0, the
comparator
1206 enables an adder 1208 to add the previous Nr and Ndiff, thereby
correcting Nr.
The corrected Nr is fed as the previous Nr to the adder 1208 through a third
register 1210.
The corrected Nr is provided to the ~Q~ estimation unit 202 for ~Q~
estimation.
In accordance with the preferred embodiment of the present invention, the ABR
service engine implements an ABR service algorithm in such a way that (1)
maximal
link utilization and minimal cell loss are guaranteed regardless of RTDs in an
ABR
closed loop; (2) ABR queue size requirements are minimized by ensuring
asymptotical
stabilization of ABR queues: (3) the MAX-MIN fairness based on the ATM forum
standards is guaranteed by ensuring a fair share of an available bandwidth to
each user;
(4) communication network environmental change is fast reacted to such as
changes in
the number of ABR users and the ABR bandwidth; (5) all functions including
EFCI, RR,
and ER markings are provided as specified in the ATM forum traffic management
specification; (6) high utilization, low cell loss, and the MAX-MIN fair rate
allocation
are achieved through the existence of an asymptotically stable operating
point; (7) high
responsiveness to network loading changes is achieved at multiple time scales,
i.e., at the
cell level rate changes of VBR and ABR VCs and at the cell level arrivals and
departures
of VBR and ABR VCs; (8) the number of operations required to compute the
algorithm
is minimized; and (9) low and scalable degree of implementation complexity is
achieved
by virtually removing per-VC operations including per-VC queuing, per-VC
accounting,
and per-VC table access.
In the ABR service engine, ~Q~ estimation and ER computation are performed
not in real time but at every predetermined period. The periodical ~Q~
estimation and the
ER computation facilitate the control operation allow the ABR service engine
to reuse
arithmetic units, thereby minimizing the hardware requirements. Internal
floating point
computation is implemented using the floating point calculators so that
operation results
are more accurate.
Furthermore, the ABR service engine obviates the need for storing an input
backward RM cell by employing the scheme of deciding as to whether ER is to be
CA 02351352 2001-05-23
WO 01/2b306 PCT/KR00/01099
-24-
written in the RM cell while buffering the RM cell in a few registers. As a
result,
memory use is minimized.
While the invention has been shown and described with reference to a certain
preferred embodiment thereof, it will be understood by those skilled in the
art that
various changes in form and details may be made therein without departing from
the
spirit and the scope of the invention as defined by the appended claims.
