Note: Descriptions are shown in the official language in which they were submitted.
CA 02278317 1999-07-09
WO 98131156 PCT/LTS98/00781
METHOD AND SYSTEM FOR DYNAMIC ALLOCATION OF BANDWIDTH IN
ASYNCHRONOUS TRANSFER MODE (ATM) SWITCHING SYSTEMS
CA 02278317 1999-07-09
WO 98!31156 PCT/US98/00781
BACKGROUND OF THE INVENTION
The present invention relates generally to asynchronous transfer mode (ATM)
switching systems, and more particularly, to a method and system for
dynamically
allocating bandwidth to Available Bit Rate (ABRI virtual circuits in ATM
switching
systems.
In an ATM network, a virtual source (VS) transmits data in the form of fixed
sized cells to a virtual destination (VD) through a connection (referred to as
virtual
circuit) established between the virtual source and the virtual destination.
The virtual
source and virtual destination may be a telephone. video equipment, facsimile,
computer. edge-router, edge-switch, etc. The cells may include any type of
digitized
information. including audio. computer data, video, multimedia, Internet data,
etc.
For example, in a network that uses Transmission Control Protocol/Internet
Protocol
(TCP/IP) over ATM, a virtual source may be an edge-router at the entry to an
ATM
network. An entry edge-router segments the incoming TCP/IP data packets into
one
or more ATM cells before transmitting each cell to the ATM network. Similarly,
a
virtual destination may be an edge router at the exit of the ATM network. An
exit
edge-router reassembles incoming ATM cells into TCP/IP data packets before
transmitting each packet to its destination.
When establishing a virtual circuit through an ATM network, a virtual source
can select one of five different categories of service: Constant Bit rate
(CBR),
Variable Bit Rate - Real Time (VBR-RT), Variable Bit Rate - Non Real Time (VBR-
NRT), Available Bit Rate (ABR), and Unspecified Bit Rate (UBR). ATM Forum
Traffic Management Standard of tm-0056.00 describes each of these services.
The ABR service determines excess bandwidth in the network and uses
network management methods to reallocate the excess bandwidth among the
virtual
circuits in the network to reduce network congestion and cell loss. In
negotiating an
ABR virtual circuit, a virtual source negotiates a peak cell rate (PCR) and a
minimum
cell rate (MCR) with the ATM network. PCR is the maximum cell rate a virtual
circuit can support. MCR is the minimum cell rate that a virtual source
requires a
virtual circuit to support. The ABR service uses the negotiated PCR and MCR
parameters to provide a guaranteed quality of service concerning bandwidth
-2-
.r i
CA 02278317 1999-07-09
WO 98/31156 PCT/ITS98/00781
availability and cell loss in a virtual circuit.
When a virtual source selects the ABR service, the virtual source periodically
generates a resource management (RM) cell to get feedback from the network on
the
rate at which the virtual source can transmit cells on a virtual circuit
without causing
loss of cells due to network congestion. Typically, a virtual source generates
an RM
cell for every thirty-one cells it transmits or at the expiration of a fixed
time interval,
whichever occurs first. The network processes the RM cell, updates virtual
circuit
bandwidth information in the RM celi, and returns the RM cell to the virtual
source.
The virtual source then dynamically adjusts its rate of cell transmission
based on the
bandwidth information contained in the RM cell.
An RM cell generated by a virtual source is referred to as a Forward RM cell.
The Forward RM cell passes through one or more switching systems in the
network
before reaching a virtual destination. The virtual destination processes the
Forward
RM cell and returns a Backward RM cell to the virtual source. The Backward RM
cell passes through one or more switching systems in the network before
reaching the
virtual source.
A virtual source maintains the MCR, current Allowed Cell Rate (ACR), and
the PCR associated with the virtual circuit. ACR is the rate at which the
network
allows the virtual source to transmit cells on a virtual circuit. When a
virtual source
receives a Backward RM cell, based on the bandwidth information in the
Backward
RM cell, the virtual source computes a new ACR. Consequently, ACR dynamically
changes as the network traffic changes and as the virtual source receives
feedback
from the network.
A Forward RM cell includes an MCR field, can ent cell rate (CCR) field, and
an explicit rate (ER) field. CCR is the rate at which a virtual source is
transmitting
cells on a virtual circuit at the time the virtual source generates a Forward
RM cell.
ER is the rate at which the virtual source wishes to transmit cells on a
virtual circuit.
A virtual source cannot set the ER field in a Forward RM cell to be greater
than PCR.
After generating a Forward RM cell and setting the MCR, CCR, and ER fields in
the
Forward RM cell, the virtual source transmits the Forward RM cell to the
network.
When a virtual source transmits a Forward RM cell, the Forward RM cell
-3-
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
passes through each switching system on the path of the virtual circuit to the
virtual
destination. Each switching system on the path can either keep the ER in
Forward
RM cell the same or decrease the ER to a lower rate. However, according to ATM
Forum Traffic Management Standard of tm-0056.00, a switching system cannot
decrease the ER below the MCR for the virtual circuit. Furthermore, a
switching
system cannot increase the ER for the virtual circuit. A switching system that
allocates bandwidth to a virtual source by setting the ER field in an RM cell
is
referred to as an ABR Explicit Rate (ABR-ER) switching system.
When a Forward RM cell associated with a virtual circuit arnves at an ABR-
I 0 ER switching system, the switching system determines an upper threshold
(referred to
as "Cutoff ') for the bandwidth that can be made available to the virtual
circuit in the
switching system. If the switching system determines that the computed Cutoff
for
the virtual circuit sets the ACR in the virtual source (i.e, the switching
system
computes the smallest Cutoff among all of the switching systems on the path of
the
15 virtual circuit), then the switching system considers the virtual circuit
to be
"bottlenecked here" or bottlenecked in the switching system. If the switching
system
determines that the computed Cutoff does not set the ACR in the virtual source
(i.e,
the switching system does not compute the smallest Cutoff among all of the
switching
systems on the path of the virtual circuit), then the switching system
identifies the
20 virtual circuit as "bottlenecked elsewhere."
The switching system determines a new bandwidth that it can allocate to the
virtual circuit by determining a new ER for the virtual circuit and setting
the new ER
in the Forward RM cell. The switching system then determines an estimated rate
(Exp Rate) at which the switching system "expects" the virtual source to
transmit
25 data cells after the virtual source adjusts its ACR based on the newly set
ER. Finally,
the switching system sends the Forward RM cell to the next switching system on
the
path of the virtual circuit.
When the Forward RM cell reaches the virtual destination, the virtual
destination returns the Forward RM cell as a Backward RM cell. The Backward RM
30 cell passes through one or more switching systems on the path of the
virtual circuit
without any further modification to the bandwidth information set in the
Forward RM
-4-
.. ~. _.
CA 02278317 1999-07-09
WO 98/31156 PCT/L1S98/00781
cell. When the Backward RM cell reaches the virtual source, the virtual source
uses
the new ER in the RM cell to determine a new ACR. Based on the new ACR, the
virtual source adjusts the rate at which it transmits cells.
Every time a switching system determines a Cutoff and ER for a virtual
circuit, the switching system also recomputes certain global bandwidth
parameters for
the virtual circuits that the switching system handles. These global bandwidth
parameters include the total bandwidth available to all ABR-ER virtual
circuits, the
total Exp Rate for ABR-ER virtual circuits that are bottlenecked elsewhere,
the total
number of ABR-ER virtual circuits that are bottlenecked elsewhere, and the
total
number of ABR-ER virtual circuits that are bottlenecked at the switching
system.
Methods for determining and updating the global bandwidth parameters in an
ABR-ER switching system are known. However, these methods have the
disadvantage that every time a switching system recomputes the global
bandwidth
parameters that the switching system maintains on its virtual circuits, the
computations introduce errors in the form of round-off errors into the global
bandwidth parameters. Over the life of the virtual circuits, as the switching
system
recomputes the global bandwidth parameters, the round-off errors can
accumulate,
and as a result of the accumulated errors, the parameters gradually become
inaccurate.
When an ABR-ER switching system maintains inaccurate global bandwidth
parameters, the switching system fails to allocate an optimum bandwidth to
each
virtual circuit. Specifically, a switching system allocates an optimum
bandwidth to a
virtual circuit when the virtual source uses the entire or nearly the entire
bandwidth
allocated to the virtual circuit. If the global bandwidth parameters are
inaccurate, the
switching system may allocate an insufficient amount of bandwidth to a virtual
circuit, even though the switching system may in fact have sufficient
bandwidth
available. Similarly, the switching system may allocate an excessive amount of
bandwidth to a virtual circuit, even though the switching system may in fact
have
insufficient bandwidth available. In either case, the switching system would
fail to
allocate an optimum bandwidth to the virtual circuit.
The methods known prior to the present invention for determining and
updating the global bandwidth parameters in an ABR-ER switching system have
the
-S-
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
additional disadvantage that, when a virtual circuit does not use the entire
bandwidth a
switching system allocates to it, the switching system cannot dynamically
identify and
reallocate the unused bandwidth to other virtual circuits in the switching
system. For
example, when a virtual source stops transmitting cells on a virtual circuit
or transmits
cells at a much lower rate than the bandwidth allocated to the virtual circuit
permits,
the virtual source does not use the bandwidth allocated to the virtual circuit
in an
optimum fashion.
Furthermore, the methods known prior to the present invention for allocating
bandwidth to an ABR virtual circuit have the disadvantage that a switching
system
may allocate more bandwidth to the virtual circuit than a virtual source could
use. For
example, when a virtual source requests an ER that is below the MCR for a
virtual
circuit, the switching system cannot decrease the ER below the MCR.
Therefore, it is desirable to have a method and system for correcting, within
a
fixed time interval, the accumulation of computational errors in the global
bandwidth
parameters maintained in an ABR-ER switching system, identifying the unused
bandwidth in virtual circuits, allocating the identified unused bandwidth to
other
virtual circuits in the switching system, and increasing the total bandwidth
that the
switching system can make available to virtual circuits.
DESCRIPTION OF THE INVENTION
The present invention comprises a method and system for dynamically
adjusting the total bandwidth that an ABR-ER switching system can make
available to
ABR virtual circuits in the switching system by recomputing, at fixed time
intervals,
the total bandwidth that the switching system can make available to active ABR
virtual circuits that are bottlenecked in the switching system. The method and
system
classifies the ABR virtual circuits that are established through an output
port of the
switching system into three categories of "recently active," "active," and
"inactive"
virtual circuits. An ABR virtual circuit is "recently active" if an output
port receives
at least one RM cell for the virtual circuit since the most recent
recomputation of the
total bandwidth that the switching system can make available to active ABR
virtual
circuits that are bottlenecked in the switching system (hereinafter referred
to as
-6-
.,
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
"bandwidth allocation update"). An ABR virtual circuit is "active" if an
output port
receives at least one RM cell within the two most recent bandwidth allocation
updates. An ABR virtual circuit is "inactive" if an output port does not
receive at
least one RM cell within the two most recent bandwidth allocation updates.
The present invention further comprises a method and system for dynamically
adjusting the total bandwidth that an ABR_ER switching system can make
available to
ABR virtual circuits in the switching system by determining the total
bandwidth
allocated to inactive A.BR virtual circuits in the switching system without
explicitly
identifying the inactive ABR virtual circuits, and making available the
bandwidth
allocated to inactive ABR virtual circuits to active ABR virtual circuits that
are
established through the switching system. When transmission of cells resumes
in an
inactive A.BR virtual circuit, the switching system reallocates new bandwidth
to the
virtual circuit.
Specifically, at each fixed time interval, the switching system sets the total
1 S expected rate (Exp Rate) for active ABR virtual circuits that are
bottlenecked
elsewhere equal to the total expected rate for recently active ABR virtual
circuits that
are bottlenecked elsewhere, sets the total number of active ABR virtual
circuits that
are bottlenecked at an output port of the switching system equal to the total
number of
recently active ABR virtual circuits that are bottlenecked in the output port
of the
switching system, resets to zero the total expected rate for recently active
ABR virtual
circuits that are bottlenecked elsewhere, and resets to zero the total number
of recently
active ABR virtual circuits that are bottlenecked at the switching system.
The present invention further comprises a method and system for allocating
bandwidth to an ABR virtual circuit that is established through an ABR-ER
switching
system by allocating an explicit rate (ER) to the virtual circuit that is less
than the
minimum cell rate (MCR) for the virtual circuit, when the switching system
receives a
resource management (RM) cell with an explicit rate that is less than the
minimum
cell rate for the virtual circuit.
The description of the invention and the following description for carrying
out
the best mode of the invention should not restrict the scope of the claimed
invention.
Both provide examples and explanations to enable others to practice the
invention.
_7_
CA 02278317 1999-07-09
WO 98!31156 PCT/US98l00781
The accompanying drawings, which form part of the description for carrying out
the
best mode of the invention, show several embodiments of the invention, and
together
with the description, explain the principles of the invention.
BRIEF DESCRIPTION OF THE DRAWINGS
Figure la is a block diagram of an asynchronous transfer mode (ATM)
communications network.
Figure 1 b is a block diagram of an end-to-end path of a virtual circuit that
passes through N switching systems in an asynchronous transfer mode (ATM)
communications network.
Figure 2 is a block diagram of a switching system in accordance with an
embodiment of the invention.
Figure 3 is a block diagram of an output port in a switching system in
accordance with an embodiment of the invention.
Figure 4 is a flow chart of the steps a switching system performs to process a
resource management cell in accordance with an embodiment of the invention.
Figure 5 is a flow chart of the steps a switching system performs to process a
resource management cell in accordance with an embodiment of the invention.
Figure 6 is a flow chart of the steps a switching system performs to determine
bandwidth parameters for an output port and a virtual circuit in accordance
with an
embodiment of the invention.
Figure 7 is a flow chart of the steps a switching system performs to determine
a new explicit rate for a virtual circuit in accordance with an embodiment of
the
invention.
Figure 8 is a flow chart of the steps a switching system performs to determine
the total expected rate for active Available Bit Rate virtual circuits that
are
bottlenecked elsewhere in accordance with an embodiment of the invention.
Figure 9 is a flow chart of the steps a switching system performs to determine
a the total expected rate for recently active Available Bit Rate virtual
circuits that are
bottlenecked elsewhere in accordance with an embodiment of the invention.
Figure 10 is a flow chart of the steps a switching system performs to
determine
_g_
~r
CA 02278317 1999-07-09
WO 98/31156 PCT/LTS98/00781
the total number of active Available Bit Rate virtual circuits that are
bottlenecked at
an output port of the switching system in accordance with an embodiment of the
invention.
Figure 11 is a flow chart of the steps a switching system performs to
determine
the total number of recently active Available Bit Rate virtual circuits that
are
bottlenecked at an output port of the switching system in accordance with an
embodiment of the invention.
Figure 12 is a flow chart of the steps a switching system performs to
determine
the total bandwidth available to active Available Bit Rate virtual circuits
that are
bottlenecked at an output port of the switching system in accordance with an
embodiment of the invention.
Figure 13 is a flow chart of the steps a switching system performs to make
available a new total bandwidth to active Available Bit Rate virtual circuits
that are
bottlenecked at an output port of the switching system in accordance with an
embodiment of the invention.
BEST MODE FOR CARRYING OUT THE INVENTION
Reference will now be made in detail to the present preferred embodiments of
the invention, examples of which are illustrated in the accompanying drawings.
Wherever possible) the same reference numbers will be used throughout the
drawings
to refer to the same or like parts.
Figure 1 a illustrates a block diagram of an asynchronous transfer mode (ATM)
communications network in accordance with an embodiment of the invention.
Virtual
source (VS) 100 interfaces with ATM network 160 via transmission link 120.
Virtual
destination (VD) 110 interfaces with ATM network 160 via transmission link
125. In
establishing a connection between VS 100 and VD 110, ATM network 160 sets up a
virtual circuit (VC) (not shown) between VS 100 and VD 110. During the set-up
phase of the connection, VS 100 negotiates with ATM network 160 for an
Available
Bit Rate-Explicit Rate {ABR-ER) service.
After completion of the set-up phase of the connection, VS 100 generates
Forward resource management {RM) cell 130 and transmits it on transmission
link
-9-
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
120. Forward RM cell 130 passes through ATM network 160 and transmission link
125, and arnves at VD 110. VD 1 IO processes Forward RM cell 130, and
generates
Backward RM cell 140 in response to Forward RM cell 130. VD 110 then transmits
Backward RM cell I40 on transmission link I25. Backward RM cell 140 passes
through ATM network 160 and transmission /ink 120, and arrives at VS I00.
VS I00 generates data cell 150 and transmits it on transmission link 120. Data
cell 150 passes through ATM network 160 and transmission link 125, and arrives
at
VD 110. Similarly, VD 110 generates data cell 150 and transmits it on
transmission
link I25. Data cell 150 passes through ATM network I60 and transmission link
I20,
IO and arrives at VS 100.
Figure Ib illustrates a block diagram of the end-to-end path of VC in ATM
network 160 in accordance with an embodiment of the invention. The path of the
VC
established between VS 100 and VD 110 passes through N switching systems 105,
through I05,~. Accordingly, when VS 100 transmits Forward RM cell 130 on
transmission link 120, Forward RM cell passes through N switching systems 105,
through 105,. Each switching system 105, through 105N connects to its adjacent
switching system via a corresponding transmission link. For example, switching
system 105, connects to switching system I05z via transmission link 121.
Switching System
Figure 2 illustrates a block diagram of a switching system, for example
switching system 1052, in accordance with an embodiment of the invention. As
shown, switching system 1052 comprises M input ports 240, through 240,. Each
input port interfaces with an input line, which can carry K virtual circuits.
For
example, input port 240M interfaces with input line 121 M, which can carry K
virtual
circuits (not shown). Input ports 240, through 240,, preferably interface with
a cross-
point switch fabric 250 via input links 220, through 220M respectively.
Alternatively,
switch fabric 250 may be a Batcher-Banyan switch network, Sunshine switch, or
any
other switch fabric capable of switching ATM cells.
Switch fabric 250 interfaces with N output ports 260, through 260, via output
links 230, through 230, respectively. For example, output port 260; interfaces
with
- 10-
__. ~. ... _.. ..m ....
w, r
CA 02278317 1999-07-09
WO 98/31156 PCT/LTS98/00781
switch fabric 250 via output Iink 230,. Each output port interfaces with an
output
line, which can carry K virtual circuits. For example, output port 260N
interfaces with
output line 122N, which can carry K virtual circuits (not shown).
Output Ports
Figure 3 illustrates a preferred embodiment for each output port 260, through
260N in accordance with an embodiment of the invention. As shown, each output
port, for example output port 260N, preferably has access to central
processing unit
310 (CPU), memory unit 360, controller 390, secondary storage 380, and high
speed
buses 370, 371, and 372. CPU 310 interfaces with controller 390 via high speed
bus
372. Controller 390 interfaces with memory unit 360 and secondary storage 380
via
high speed buses 370 and 371 respectively.
Memory unit 360 preferably includes VC Handler 320, Port Handler 330,
Bandwidth Allocation Update 340, and Buffer 350. VC Handler 320, Port_Handler
330, Bandwidth Allocation Update 340, and Buffer 350 each preferably include a
set
of instructions in the form of software, which CPU 310 executes. VC_Handler
320
receives and processes RM cells for VCs in output port 260N. Specifically,
Port Handler 330 deterniines a new ER and Exp Rate for a VC, and recomputes
the
global bandwidth parameters for the VCs in output port 260;x, when a VC
receives an
RM cell. At fixed time intervals, Bandwidth Allocation Update 340_ recomputes
the
total bandwidth that output port 260y can make available to active VCs that
are
bottlenecked at output port 260N. Buffer 350 stores cells (i.e, data cells and
RM
cells) that arrive at output port 260N in queues (not shown), which are in
memory unit
360. Alternatively, each VC Handler 320, Port Handler 330,
Bandwidth Allocation Update 340, and Buffers 350 may be implemented in
hardware using hardware technology known to one of ordinary skill in the art.
Secondary storage 380 includes disk drive unit 382 and tape cartridge 381.
Stored in disk drive unit 382 are software and data for switching system 105,.
For
example, disk drive unit 382 contains software for VC Handler 320,
Port_Handler
330, Bandwidth Allocation Update 340, and Buffer 350. Secondary storage 380
can
copy software and data for switching system 105, from tape cartridge 381 into
disk
-11-
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
drive unit 382. Controller 390 can then upload the software and data from disk
drive
unit 382 into memory unit 360. Similarly, controller 390 can download software
and
data from memory unit 360 into disk drive unit 382. Secondary storage 380 can
then
copy the downloaded software and data from disk drive unit 382 into tape
cartridge
381.
VC Handler
A VC Handler processes and stores data specific to each VC in an output port.
Specifically, a VC Handler preferably stores for each VC a MCR, the time that
an
RM cell last arrived for the VC, an Exp Rate, and a Bottlenecked Elsewhere
indicator. VC,Handler sets Bottlenecked Elsewhere indicator to a logical value
of l,
when at the time VC Handler receives an RM cell for a VC, the VC is
bottlenecked
elsewhere. If the VC is instead bottlenecked at an output port of the
switching
system, then VC Handler sets Bottlenecked Elsewhere indicator to a logical
value of
0.
Figure 4 illustrates a flow chart of the steps a VC Handler, for example
VC Handler 320, preferably performs to process an- RM cell, for example RM
cell
130, for a VC. VC Handler 320 receives RM cell 130 VC from switch fabric 250
(step 400). VC Handler 320 then generates an RM Cell Request (step 405). An
RM-Cell Request includes a MCR, Bottlenecked_Elsewhere indicator, current
Exp'Rate for VC, CCR, and a current ER for VC.
VC Handler 320 then sends the RM Cell Request to Port Handler 330 (step
410). Port Handler 330 computes a new ER, Exp Rate, and Bottlenecked Elsewhere
indicator, and incorporates them in RM Cell Request.
VC Handler 320 waits until it receives the RM_Cell Request back from
Port Handler 330 (step 415). If VC Handler 320 does not receive the
RM_Cell Request back from Port_Handler 330 (step 415), then VC Handler
continues to wait until it receives the RM Cell Request from Port-Handler 330
(step
420). If VC Handler 320 receives the RM Cell Request back from Port Handier
330, then VC Handler 320 resumes the processing of the- RM-Cell Request
(step 425).
-12-
~Y ...
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
VC Handler 320 stores the new ER, Exp Rate, and the
Bottlenecked Elsewhere indicator in memory unit 360 (step 430}. Alternatively,
VC Handler 320 may store each of these values in a register. Finally,
VC_Handler
320 replaces the current ER in RM cell 130 with the new ER in RM_Ceil Request
(step 435). VC Handler 320 then sends RM cell 130 to Buffer 350 in output
port 260N (step 440).
Port Handler
A Port_Handler determines a new ER and Exp Rate for a VC, and recomputes
the global bandwidth parameters for VCs in an output port. Specifically, a
Port Handler preferably stores the time of the most recent bandwidth
allocation
update, the time of the second most recent bandwidth allocation update, the
total
bandwidth available to all VCs (i.e., CBR, VBR, ABR, and UBR VCs) in the
output
port, the total bandwidth available to all ABR VCs (i.e., active and inactive
ABR
VCs), the total Exp Rate for active ABR VCs bottlenecked elsewhere, total Exp
Rate
for recently active ABR VCs bottlenecked elsewhere, the total bandwidth
available to
ABR VCs bottlenecked at the output port, the total number of active ABR VCs
bottlenecked at the output port, and the total number of recently active ABR
VCs
bottlenecked at the output port. When the Port_Handler receives an
RM_Cell Request from a VC Handler, the Port Handler- _ recomputes the above
mentioned global bandwidth parameters.
Figure 5 illustrates a flow chart of the steps a Port_Handler, for example
Port_Handler 330, preferably performs to process an RM-Cell Request.
Pol-t_Handler 330 receives RM-Cell Request from VC Handler 320 (step 500).
Port Handler 330, as explained below,- recomputes global bandwidth parameters
for
output port 260N, and new ER and Exp'Rate for VC (step 505). Port_Handler 330
stores the new global bandwidth parameters for output port 260, in memory unit
360
(step 510). Port Handler 330 sets the global bandwidth parameters for VC in
the
RM Cell Request (step 515). Port Handler 330 then returns the updated
RM_Cell Request to VC Handler 320 (step 520).
Figure 6 illustrates a flow chart of the steps a Port Handler, for example
-I3-
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
Port-Handler 330, preferably performs to determine new global bandwidth
parameters
for an output port, for example output port 260N, and a VC. Port Handler 330
determines whether the last RM cell for VC arrived at output port 260N within
the two
most recent bandwidth allocation updates in output port 260N (step 600).
If Port Handler 330 determines that the last RM cell for VC arrived at output
port 260N before the two most recent bandwidth allocation updates in output
port 260N
(step 610), Port Handler 330 resets the current Exp Rate for VC to zero (step
615),
and determines that VC is bottlenecked elsewhere and sets the
Bottlenecked Elsewhere indicator in the RM Cell Request equal to a logical 1
(step 620). Port-Handler then determines whether VC is bottlenecked elsewhere
(step
625).
If Port_Handler 330 determines that the last RM cell for VC arrived at output
port 260, within the two most recent bandwidth allocation updates in output
port 260,
(step 605), then Port-Handler 330 determines whether VC is bottlenecked
elsewhere
(step 625).
If Port Handler 330 determines that VC is bottlenecked elsewhere (step 640),
then Port Handler 330 determines an upper threshold, namely "Cutoff," for the
amount of bandwidth that output port 260N can make available to VC. Port
Handler
330 preferably determines the Cutoff for VC by dividing the total bandwidth
available
to active ABR VCs bottlenecked at output port 260; plus the current Exp Rate
for
VC by the total number of active ABR VCs bottlenecked at output port 260, plus
one
(step 645). Step 645 may alternatively be expressed as follows:
Cutoff = (Total Bandwidth Available to Active ABR VCs at Output
Port 260N + Current Exp Rate for VC) / (Total Number
of Active ABR VCs Bottlenecked at Output Port 260N + 1 )
If Port Handler 330 determines that VC is bottlenecked at output port 260N
(step 630), Port Handler 330 sets the Cutoff for VC equal to the total
bandwidth
available to active ABR VCs bottlenecked at output port 260, divided by the
total
number of active ABR VCs bottlenecked at output port 260; (step 650).
Port Handler 330 then, as explained below, determines a new ER for VC (step
- 14-
~, ~
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
655), a new ExpTRate for VC (step 660), a new total Exp Rate for recently
active
ABR VCs bottlenecked elsewhere (step 665), a new total Exp Rate for active
A.BR
VCs bottlenecked elsewhere (step 670), a new total number of recently active
ABR
VCs bottlenecked at output port 260N (step 675), a new total bandwidth that
output
port 260N can make available to active ABR VCs bottlenecked at output port
260N
(step 680), and a new total number of active ABR VCs bottlenecked at output
port
260N (step 685).
Figure 7 illustrates a flow chart of the steps a Port_Handler, for example
Port Handler 330, preferably performs to determine a new ER for a VC.
Port_Handler 330 determines whether the Cutoff for VC is less than or equal to
MCR
for VC (step 700). If Port-Handler 330 deterTnines that Cutoff for VC is
greater than
MCR (step 710), Port_Handler 330 sets the new ER equal to the minimum of the
current ER and MCR (step 715). Port Handler 330 then determines that VC is
bottlenecked elsewhere, and sets the Bottlenecked Elsewhere indicator in the
1 S RM_Cell Request to a logical 1 (step 755).
If Port Handler 330 determines that Cutoff for VC is less than or equal to
MCR for VC (step 705), Port Handler 330 determines a most likely new Exp Rate
for VC (step 720). Port Handler 330 selects the maximum of CCR and MCR for VC,
and sets the most likely new Exp Rate to the minimum of that maximum value and
the current ER for VC.
Port-Handler 330 determines whether the Cutoff for VC is greater than the
most likely new Exp Rate for VC (step 725). If Port Handler 330 determines
that the
Cutoff is not greater than the most likely new Exp Rate (step 735), then
Port_Handler
330 sets the new ER for VC to the minimum of current ER and the Cutoff (step
740).
Port Handier 330 then determines that VC is bottlenecked elsewhere and sets
the
Bottlenecked Elsewhere indicator in the RM Cell Request to a logical 1 (step
755).
If Port Handler 330 determines that the Cutoff for VC is greater than the most
likely new Exp Rate (step 730), Port_Handler 330 sets the new ER equal to the
Cutoff (step 745). Port_Handler 330 then determines that VC is bottlenecked at
output port 260,x, and sets the Bottlenecked Elsewhere indicator in the
RM_Cell Request to a logical 0 (step 750).
-15-
CA 02278317 1999-07-09
WO 98/31156 PCTIUS98/00781
Figure 8 illustrates a flow chart of the steps a Port Handler, for example
Port Handler 330, preferably performs to determine a new total Exp Rate for
active
ABR VCs that are bottlenecked elsewhere. Port-Handler 330 determines whether a
VC is currently bottlenecked elsewhere (step 800). If Port-Handler 330
determines
that VC is bottlenecked at output port 260, (step 810), then Port Handler 330
determines whether, when last time output port 260N received an RM cell for
VC, VC
was bottlenecked elsewhere (step 815). If Port-Handler 33 determines that last
time
VC was bottlenecked at output port 260, (step 820), then Port Handler 330
determines that the total Exp Rate for active ABR VCs that are bottlenecked
elsewhere remains unchanged (step 82S).
If Port Handler 330 determines that, when last time output port 260, received
an RM cell for VC, VC was bottlenecked elsewhere (step 830), then Port Handler
330 decreases the total Exp Rate for active A.BR VCs that are bottlenecked
elsewhere
by the current Exp Rate for VC (step 835).
1 S If Port-Handler 330 determines that VC is currently bottlenecked elsewhere
(step 80S), then Port Handler 330 determines whether, when last time output
port
260N received an RM cell for VC, VC was bottlenecked elsewhere (step 840). If
Port Handler 330 determines that last time VC was bottlenecked at output port
260,
(step 84S), Por-t_Handler 330 increases the total Exp Rate for active ABR VCs
that
are bottlenecked elsewhere by the new Exp Rate for VC (step 8S0).
If Port-Handler 330 determines that last time VC was bottlenecked elsewhere
(step 85S), the Port Handler 330 decreases the total Exp Rate for active- ABR
VCs by
the current Exp Rate for VC and increases the total Exp Rate for active- ABR
VCs by
the new Exp Rate for VC (step 860).
2S Figure 9 illustrates a flow chart of the steps a Port Handler, for example
Port Handler 320, preferably performs to determine a new total Exp Rate for
recently
active. ABR VCs that are bottlenecked elsewhere. Port Handler 330 determines
whether the last RM cell for a V C arrived at output port 260; after the most
recent
bandwidth allocation update in output port 260N (step 900).
If Port Handler 330 determines that the last RM cell for VC arrived at output
port 260N before the most recent bandwidth allocation update in output port
260N (step
- 16-
*~
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
905), then Port_Handler 330 determines whether VC is currently bottlenecked
elsewhere (step 920). If Port_Handler determines that VC is currently
bottlenecked
elsewhere (step 920), the Port-Handler 330 increases the total Exp Rate for
recently
active ABR VCs that are bottlenecked elsewhere by the new Exp Rate for VC
(step
980).
If Port Handler 330 determines that VC is currently bottlenecked at output
port 260N (step 915), then Port Handler 330 determines that the total Exp Rate
for
recently active ABR VCs that are bottlenecked elsewhere remains unchanged
(step
925).
If Port Handler 330 determines that last- RM cell for VC arrived after the
most
recent bandwidth allocation update in output port 260v (step 930), then
Port_Handler
330 determines whether VC is currently bottlenecked elsewhere (step 935). If
Port_Handler 330 determines that VC is bottlenecked at output port 260N (step
940),
then Port Handler 330 determines whether, when last time output port 260N
received
an RM cell for VC, VC was bottlenecked elsewhere (step 950). If Port_Handler
330
determines that last time VC was bottlenecked at output port 260N (step 955),
then
Port Handler 330 determines that the total Exp Rate for recently active ABR
VCs
that are bottlenecked elsewhere remains unchanged (step 925).
If Port_Handler 330 determines that VC is bottlenecked at output port 260N
(step 940) and determines that, when last time output port 260N received an RM
cell
for VC, VC was bottlenecked elsewhere (step 960), then Port-Handler 330
decreases
the total Exp Rate for recently active ABR VCs that are bottlenecked elsewhere
by
the current Exp Rate for VC (step 965).
If Port Handler 330 determines that last RM cell for VC arrived after the most
recent bandwidth allocation update in output port 260N (step 930) and
determines that
VC is currently bottlenecked elsewhere (step 945), then Port_Handler 330
determines
whether, when last time output port 260N received an RM cell for VC, VC was
bottlenecked elsewhere (step 970). If Port_Handler determines that last time
VC was
bottlenecked at output port 260, (step 975), then Port_Handler 330 increases
the total
Exp Rate for recently active ABR VCs that are bottlenecked elsewhere by the
new
Exp Rate for VC (step 980).
- 17-
CA 02278317 1999-07-09
WO 98/31156 PCT/LTS98/00781
If Port-Handler 330 determines that last RM cell for VC arnved after the most
recent bandwidth allocation update in output port 260N (step 930), determines
that VC
is currently bottlenecked elsewhere (step 945), and determines that, when last
time
output port 260N received an RM cell for VC, VC was bottlenecked elsewhere
(step
985), then Port_Handler 330 decreases the total Exp Rate for recently active
ABR
VCs that are bottlenecked elsewhere by the current Exp Rate for VC and
increases
the total Exp Rate for recently active ABR VCs that are bottlenecked elsewhere
by
the new Exp Rate for VC (step 990).
Figure 10 illustrates a flow chart of the steps a Pol-t_Handler, for example
Port Handler 330, preferably performs to determine the new total number of
active
ABR VCs that are bottlenecked at an output port, for example output port 260N.
Port Handler 330 determines whether a VC is currently bottlenecked elsewhere
(step
1000). If Port-Handler 330 determines that VC is currently bottlenecked at
output
port 260, (step 1005), then Port Handler 330 determines whether, when last
time
output port 260N received an RM cell for VC, VC was bottlenecked elsewhere
(step
1015). If Port Handler 330 determines that last time VC was bottlenecked at
output
port 260N (step 1020), then Port Handler 330 determines that the total number
of
active ABR VCs that are bottlenecked at output port 260N remains unchanged
(step I050).
If Port Handler 330 determines that VC is currently bottlenecked elsewhere
(step 1010), then Port-Handler 330 determines whether, when last time output
port
260N received an RM cell for VC, VC was bottlenecked elsewhere (step 1030). If
Port Handler 330 determines that last time VC was bottlenecked at output port
260h
(step 1040), then Port Handler 330 decreases the total number of active- ABR
VCs
that are bottlenecked elsewhere by one (step 1045).
If Port-Handler 330 determines that VC is currently bottlenecked elsewhere
(step 1010) and determines that, when last time output port 260N received an
RM cell
for VC, VC was bottlenecked elsewhere (step 1035), then Port Handler 330
determines that the total number of active ABR VCs that are bottlenecked at
output
port 260, remains unchanged (step 1050).
Figure 11 illustrates a flow chart of the steps a Port Handler, for example
-18-
.,
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
Port_Handler 330, preferably performs to determine the new total number of
recently
active A.BR VCs that are bottlenecked at an output port, for example output
port 260N.
If Port Handler 330 determines that the last RM cell for a VC arrived before
the most
recent bandwidth allocation update (step 1105), then Port_Handler 330
determines
whether VC is currently bottlenecked elsewhere (step 1115). If Port_Handler
330
determines that VC is currently bottlenecked at output port 260, (step 1120),
then
Port Handler 330 determines that the total number of recently active- ABR VCs
that
are bottlenecked at output port 260N remains unchanged (step 1165).
If Port_Handler 330 determines that the last RM cell for VC arrived before the
most recent bandwidth allocation update (step 1105) and determines that VC is
currently bottlenecked elsewhere (step 1125), then Port Handler 330 increases
the
total number of recently active A.BR VCs that are bottlenecked at output port
260N by
one (step I 130).
If Port-Handler 330 determines that last RM cell for VC arrived after the most
recent bandwidth allocation update (step 1110), then Port_Handler 330
determines
whether, when last time output port 260N received an RM cell for VC, VC was
bottlenecked elsewhere (step 1135). If Port Handler 330 determines that last
time VC
was bottlenecked elsewhere (step I 140), then Port_Handler 330 determines
whether
VC is currently bottlenecked elsewhere (step 1115). If Port_Handler 330
determines
that VC is currently bottlenecked at output port 260N (step 1120), then
Port_Handler
330 determines that the total number of recently active ABR VCs that are
bottlenecked at output port 260N remains unchanged (step 1165).
If Port Handler 330 determines that, when last time output port 260N received
an RM cell for VC, VC was bottlenecked elsewhere (step 1140) and determines
that
VC is currently bottlenecked elsewhere (step 1125), then Port-Handler 330
increases
the total number of recently active ABR VCs that are bottlenecked at output
port 260.
by one (step 1130).
If Port Handler 330 determines that the last- RM cell for VC arrived after the
most recent bandwidth allocation update (step 11 IO) and determines that VC
was
bottlenecked at output port 260N (step 1145), then Port Handler 330 determines
whether VC is currently bottlenecked elsewhere (step 1150). If Port Handler
330
- I9-
CA 02278317 1999-07-09
WO 98/31156 PCT/US98100781
determines that VC is currently bottlenecked at output port 260N (step 1155),
then
Port Handler 330 determines that the total number of recently active ABR VCs
that
are bottlenecked at output port 260N remains unchanged (step 1165).
If Port Handler 330 determines that last RM cell for VC arrived after the most
recent bandwidth allocation update (step 1110), determines that, when last
time output
port 260, received an RM cell for VC, VC was bottlenecked at output port 260N
(step
1145), and determines that VC is currently bottlenecked elsewhere (step 1160),
then
Port-Handler 330 decreases the total number of active ABR VCs that are
bottlenecked
at output port 260N by one (step 1170).
Figure 12 illustrates a flow chart of the steps a Port_Handler, for example
Port Handler 330, preferably performs to determine the new total bandwidth
that an
output port, for example output port 260N, can make available to active ABR
VCs that
are bottlenecked at output port 260N. Port_Handler 330 determines whether a VC
is
currently bottlenecked elsewhere (step 1200). If Port_Handler 330 determines
that
VC is bottlenecked at output port 260, (step 1205), then Port Handler 330
determines
whether, when last time output port 260, received an RM cell for VC, VC was
bottlenecked elsewhere (step 1215). If Port Handler 330 determines that last
time VC
was bottlenecked at output port 260, (step 1220), then Port Handler 330
determines
that the total bandwidth that output port 260N can make available to active
ABR VCs
at output port 260, remains unchanged (step 1230).
If Port-Handler 330 determines that VC is bottlenecked at output port 260,
(step 1205) and determines that, when Iast time output port 260y received an
RM cell
for VC, VC was bottlenecked elsewhere (step 1225), then Port Handler 330
increases
the total bandwidth that output port 260N can make available to active ABR VCs
that
are bottlenecked at output port 260N by the current Exp Rate for VC (step
I235).
If Port_Handler 330 determines that VC is bottlenecked elsewhere (step 1210),
then Port Handler 330 determines whether, when last time output port 260N
received
an RM cell for VC, VC was bottlenecked elsewhere (step 1240). If Port Handler
determines that last time VC was bottlenecked at output port 260, (step 1245),
then
Port Handler 330 decreases the total bandwidth available to active ABR VCs
that are
bottlenecked at output port 260; by the new Exp Rate for VC (step 1255).
-20-
_,
CA 02278317 1999-07-09
WO 98/31156 PCT/US98I00781
If Port Handler 330 determines that VC is bottlenecked elsewhere (step 1210)
and determines that, when last time output port 260N received an RM cell for
VC, VC
was bottlenecked elsewhere (step 1250), then Port Handler 330 increases the
total
bandwidth that output port 260N can make available to active ABR VCs that are
bottlenecked at output port 260N by the current Exp Rate for VC and decreases
the
total bandwidth that output port 260N can make available to active ABR VCs
that are
bottlenecked at output port 260N by the new Exp Rate for VC (step 1260).
Bandwidth Allocation Update
An output port, for example output port 260N, invokes, at preferably fixed
time
intervals, Bandwidth Allocation Update 340. Bandwidth Allocation Update 340
preferably stores the time interval between each invocation in a static
memory. The
manufacturer of a switching system may set a default for the fixed time
interval,
which a switching system administrator or network administrator may
subsequently
reconfigure.
The time interval between each invocation may preferably be twice the upper
bound for the time interval between each RM cell generated by an active
virtual
source. The upper bound may preferably be in the range of 2'S milliseconds to
100
milliseconds. Alternatively, the time interval between each invocation may be
less
than twice the upper bound for the time interval between each RM cell, in
which case
the time interval between each invocation must still be sufficiently large to
allow for
arrival of at least one RM cell between two consecutive invocations of
Bandwidth Allocation Update 340.
Bandwidth Allocation Update 340 preferably has access to the global
bandwidth parameters stored in memory unit 360 by Port_Handler 330.
Specifically,
Bandwidth Allocation Update 340 has access to the time of the most recent
bandwidth allocation update, the time of a second most recent bandwidth
allocation
update, the total bandwidth available to all ABR VCs (i.e., active and
inactive ABR
VCs), the total Exp Rate for active ABR VCs bottlenecked elsewhere, the total
Exp Rate for recently active ABR VCs bottlenecked elsewhere, the total
bandwidth
available to active ABR VCs bottlenecked at output port 260N, the total number
of
-21 -
CA 02278317 1999-07-09
WO 98/31156 PCT/CTS98/00781
active ABR VCs bottlenecked at output port 260N, and the total number of
recently
active ABR VCs bottlenecked at the output port 260N.
Figure 13 illustrates a flow chart of the steps a Bandwidth Allocation Update,
for example Bandwidth Allocation Update 340, preferably performs to make
available a new total bandwidth to active ABR VCs that are bottlenecked at an
output
port, for example output port 260N. Bandwidth Allocation Update 340 sets the
total
Exp Rate for active ABR VCs that are bottlenecked elsewhere equal to the total
Exp Rate for recently active ABR VCs that are bottlenecked elsewhere (step
1300).
Next, Bandwidth Allocation Update 340 sets the total number of active- - ABR
VCs that are bottlenecked at output port 260N equal to the total number of
recently
active ABR VCs that are bottlenecked at output port 260, (step 1305).
Bandwidth Allocation Update 340 then sets the total bandwidth that output
port 260, can make available to active ABR VCs that are bottlenecked at output
port
260N equal to the difference between the total bandwidth available to all ABR
VCs
1 S (i.e., active and inactive ABR VCs) and the total Exp Rate for recently
active ABR
VCs that are bottlenecked elsewhere (step 1310).
Next, Bandwidth Allocation Update 340 resets the total Exp Rate for
recently active ABR VCs that are bottlenecked elsewhere (step I315).
Bandwidth Allocation Update 340 then resets the total number of recently
active
ABR VCs that are bottlenecked at output port 260N (step 1320). Finally,
Bandwidth Allocation Update 340 sets a timer for the next update to the total
bandwidth that output port 260N can make available to active ABR VCs that are
bottlenecked at output port 260N (step 1325).
To prevent reallocation of bandwidth from a VC when an RM cell for the VC
is lost, for example, due to network congestion for an extended period of
time, an
ATM network may assign a high priority to RM cells. Alternatively, by keeping
the
time interval between the updates to the global bandwidth parameters (i.e.,
invocation
of Bandwidth Allocation Update) sufficiently large, if an RM cell is lost due
to
network congestion, the impact to allocation of an optimum bandwidth to the VC
would be minimal.
While it has been illustrated and described what are at present considered to
be
-22-
,. f. ..
CA 02278317 1999-07-09
WO 98/31156 PCT/US98/00781
preferred embodiments and methods of the present invention, it will be
understood by
those skilled in the art that various changes and modifications may be made,
and
equivalents may be substituted for elements thereof without departing from the
true
scope of the invention.
In addition, many modifications may be made to adapt a particular element,
technique or implementation to the teachings of the present invention without
departing from the central scope of the invention. Therefore, it is intended
that this
invention not be limited to the particular embodiments and methods disclosed
herein,
but that the invention include all embodiments falling within the scope of the
appended claims.
-23-
