Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-04-29
2001-06-05
Olms, Douglas (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S412000, C370S429000
Reexamination Certificate
active
06243359
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the allocation of bandwidth in an ATM (Asynchronous Transfer Mode) network. More particularly, the invention relates to methods and apparatus for controlling traffic and congestion via queuing structures.
2. State of the Art
A properly constructed ATM network must manage traffic fairly and provide effective allocation of the network capacity for different types of traffic such as voice, video, and data. The ATM network must also provide cost effective operations relative to the quality of service (QOS) level specified by each network user and must be able to support different delay requirements for different applications. Most importantly, the network must be able to adapt to unforseen traffic patterns, in particular unforseen bursts of traffic from various network users, i.e. network congestion.
The only way to manage network congestion, short of increasing the bandwidth of the network, is to manage the network traffic. According to various ATM standards, traffic management is largely based on QOS levels negotiated between the network operator and the network users. In general, QOS levels specify the maximum amount of traffic which each user may submit to the network in a measured period of time, i.e. a bit rate. A digital voice connection requires no more than about 32 kbits/s whereas a high definition television signal may require more than 6 Mbit/s. These predicted requirements in bandwidth are sometimes referred to as the “natural bit rate” for an application. The natural bit rate required by non-specific data transmissions may vary widely over time from as low as a few kbits/s to as high as several hundred kbits/s. This type of variable natural bit rate is said to be “bursty”. The challenge to the ATM network is to support the natural bit rate of all the applications being serviced. Due to statistical bursts, it is inefficient to simply allocate bandwidth for the maximum bit rate required by the application. Because of variable traffic profiles, it may be necessary to discard traffic from certain users when the network experiences congestion.
As suggested above, congestion refers to a condition that exists at the ATM layer in the network elements such as switches, transmission links, or cross-connects where the network is not able to meet a stated and negotiated performance objective (the QOS levels specified by the network users). Traffic control, on the other hand, refers to a set of actions which are taken by the network to avoid congestion. Thus, “congestion control” is the result of QOS planning and “traffic control”.
The actions which may be taken by the network to control traffic are limited by the QOS levels negotiated with the network users. In the ATM network, traffic control includes five types of actions: (1) Connection Admission Control (CAC) to determine at the time of call setup whether a user connection will be accepted or rejected; (2) Usage Parameter Control (UPC) to monitor and regulate traffic at the User Network Interface (UNI); (3) Cell Loss Priority (CLP) control to establish priorities for different types of traffic; (4) traffic shaping mechanisms to alter the nature of traffic at the UNI based on the three previously stated controls; and (5) traffic discarded based on specified policies using information from actions (1) through (4) above.
A core mechanism utilized in the ATM network is the establishment of queues at the inlet to an ATM node. Prior art
FIG. 1
illustrates the simple concept of queues for different types of traffic entering a multiplexer
10
having an outlet
12
with a maximum bandwidth of, e.g., 155 mbits/s. The multiplexer has a number of inlets shown as
14
,
16
,
18
,
20
,
22
, . . . , n, and each is provided with a corresponding queue (FIFO buffer)
14
′,
16
′,
18
′,
20
′,
22
′, . . , n′. Regardless of the bandwidth of the network, the aggregate bit rate of all of the inlets n must not exceed the bandwidth of the outlet
12
for more than a short period of time (e.g. a few milliseconds) during which the queues may prevent data loss. According to the ATM standard, each inlet queue must be serviced in a fair and equitable manner. Queue servicing operations should result in appropriate delays and acceptable data loss for each application. For example, if the queue for inlet 14 in
FIG. 1
receives a constant bit rate (CBR) video signal (50-100 kbits/s), it must be serviced every 1-2 milliseconds in order to prevent data loss. On the other hand, if inlet
18
services variable bit rate voice, it may tolerate a data loss of between 1-10% of the samples and the queue for this inlet may be serviced less frequently. The highest priority queue may be the one servicing the signalling channel which contains information for managing the network, including traffic shaping controls to prevent congestion. Other data channels may receive different priority handling depending on the agreed QOS for these channels. The lowest priority queues are those carrying data which is not sensitive to delay, e.g. email.
Those skilled in the art will appreciate that the number of queues and the type of traffic being handled at any node such as the multiplexer
10
in
FIG. 1
changes over time and that the node must constantly monitor the state of queues, opening new queues, closing old queues, and assuring that all queues are timely serviced. According to general principles, after the signalling channel is serviced, delay-sensitive queues are serviced for T
1
ms or until the delay-sensitive queues are empty if before T
1
ms. Next, the delay-insensitive queues are serviced for T
2
ms or until they are empty if before T
2
ms. If during the servicing times T
1
and T
2
, the signalling channel queue needs to be serviced, the servicing of the queues is suspended and resumed when servicing of the signalling channel queue is completed.
There are three well known equations used to compute the parameters for servicing queues. The first equation, listed as Equation 1 below, assures that for each q
i
, a fraction f
i
of the output link bandwidth is available where T
i
is the time parameter for servicing queue q
i
.
f
i
=
T
i
∑
i
=
0
n
T
i
,
0
≤
i
≤
n
(
1
)
The second equation, listed below as Equation 2, assures that all of the bandwidth assigned to all of the queues does not exceed a fraction of (1−f
0
) for the output link capacity.
∑
i
=
0
n
f
i
≤
1
-
f
0
(
2
)
The third equation, listed below as Equation 3, shows that the cycle time for all queues should be from 1-2 milliseconds in order to guarantee consistent service to delay sensitive traffic.
∑
i
=
0
n
T
i
≤
D
c
ms
=
M
c
t
,
(
D
c
≈
1
to
2
ms
)
(
3
)
In Equation 3, M
c
is the number of cells withdrawn from the queue during the service cycle time and t is the cell transmission time on the link.
Those skilled in the art will appreciate that one of the most difficult aspects of traffic management are related to variable delays in traffic. Traffic management operations must occur at the source UNI and at the destination UNI in order to account for traffic delays. In other words, data flowing from the network to the UNI must be buffered and data flowing from the users to the network must be buffered. Further, at each device through which data passes from a source to a destination, data must be buffered at the inlet and the outlet of the device. The nature of the traffic will determine how it is buffered and whether or not data is discarded in order to avoid congestion.
Prior art
FIG. 2
illustrates the inlet and outlet buffers in a state of the art ATM device at a UNI. As shown in
FIG. 2
, a plurality of xDSL line inlets
30
enter a user side inlet multiplexer
32
via a plurality of user inlet queues
34
in a manner similar to that discussed above with reference to FIG.
1
. The multiplexer
32
services the queues
34
Bricca Alberto
Lipp William B.
Roy Subhash C.
Upp Daniel C.
Gallagher Thomas A.
Gordon David P.
Hom Shick
Jacobson David S.
Olms Douglas
LandOfFree
Methods and apparatus for managing traffic in an atm network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for managing traffic in an atm network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for managing traffic in an atm network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2481277