Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-07-02
2003-05-13
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395100
Reexamination Certificate
active
06563792
ABSTRACT:
FIELD OF THE INVENTION
The present invention discloses, in general, a method and apparatus for traffic monitoring and controlling of a connection in packet communication networks. More specifically, the present invention provides a fuzzy leaky bucket mechanism for improving the performance in terms of selectivity, responsiveness, and mean queueing delay in ATM networks.
BACKGROUND OF THE INVENTION
The emergence of multimedia services has diversified the bandwidth requirement for data communications. The asynchronous transfer mode (ATM) is considered as a suitable technique to meet the diverse bandwidth requirement since its design objectives are to support different types of traffic and multiple quality of services (QoS). To achieve the design objectives, several traffic control mechanisms are recommended for ATM networks [1]. Two of them are the call admission control (CAC) and the usage parameter control (UPC).
CAC is performed at the call setup phase of a new call to decide whether the new call can be accepted or not. It accepts the new call if the network can afford the required bandwidth and QoS of the new connection while the QoS of the already established connections can still be maintained. Then a traffic contract is made between the new connection and the network. The traffic contract contains traffic descriptors such as the peak cell rate (PCR), the sustainable cell rate (SCR) and the maximum burst size (MBS). For CAC to perform correctly, all the established connections must not violate their respective traffic contracts, which are of vital importance to the decision making of CAC. To make sure that the established connections conform to their respective traffic contracts, CAC is coupled with another traffic control mechanism, namely, UPC.
UPC is performed at the user-network interface (UNI) during the data transfer phase. It is defined as the set of actions taken by the network to monitor and control the offered traffic of a connection so that the corresponding traffic contract is respected. Its main purpose is to protect network resources from malicious as well as unintentional misbehavior, which can affect the QoS of other already, established connections. The wide variety of services with different traffic characteristics and QoS requirements makes UPC a difficult task. The difficulty lies in finding a simple, universal and effective UPC scheme, which is able to police any types of traffic ranging from video to data traffic. Several UPC schemes such as the jumping window, triggered jumping window, moving window, exponentially weighted moving average, and leaky bucket mechanisms were studied and compared [2-5]. The most popular and well-known policing scheme is the leaky bucket algorithm because of its simplicity and effectiveness.
Monitoring and controlling the peak cell rate of a connection is not difficult because we only have to determine if the peak emission interval is smaller than the reciprocal of the negotiated peak cell rate &Lgr;
PCR
. But monitoring and controlling the sustainable cell rate of a connection is much more complicated because the connection is eligible to transfer cells with a short-term mean rate higher than the negotiated sustainable cell rate &Lgr;
SCR
as long as the long-term mean rate of the connection conforms to &Lgr;
SCR
.
Usually, a traffic shaper (TS) is equipped within the customer premise equipment to regulate the cell stream of the traffic source so as to conform the negotiated SCR. The regulation is to alter the traffic characteristics of the cell stream to achieve a desired modification. The consequence of the modification is an increase in the mean cell transfer delay. The conjunction of TS and UPC, named as TS-UPC pair, should employ an identical scheme with same parameters settings so that any possible non-conforming cell that might have been detected as non-conforming by UPC will be detected ahead of time and saved in the queue by TS. In this way, the TS-UPC pair can guarantee zero cell loss ratio at UPC for a non-violating connection. Nevertheless, if a user intentionally or unintentionally changes the parameter settings in TS to enjoy a higher throughput there, UPC will detect the violation and take actions against it.
Three performance requirements have to be fulfilled by the TS-UPC pair:
(1.) High selectivity: UPC should detect the non-conforming cells of a violating connection as much as possible, while being transparent when the connection conforms to its traffic contract.
(2.) High responsiveness: the time for UPC to detect a violating connection should be rather short.
(3.) Low mean queueing delay: TS should not queue too many cells of a non-violating connection. However, the queueing delay introduced by TS on a violating connection is beyond the guarantee.
The primitive connection model with conventional TS-UPC pair is shown in FIG.
1
. In a customer premise equipment
10
, the component attached to the traffic source
12
is the TS
14
, which contains a queue
16
and a shaper
18
. The shaper
18
employs the conventional leaky bucket algorithm to determine the conformance of cells. It bypasses the conforming cells but stores the non-conforming cells in the queue for further legal transmission. The component at the entrance of the network
20
is the UPC
22
where a policer
24
is incorporated. The UPC
22
is connected to the customer premise equipment
10
through a UNI
30
. The policer
24
also employs the conventional leaky bucket algorithm as the shaper
18
does. It bypasses the conforming cells but drops or tags the non-conforming cells. Despite the fact that the conventional leaky bucket algorithm is simple and effective, the conventional TS-UPC pair has performance defects such as long response time, low selectivity, and large mean queueing delay. One reason for the defects is its lack of system information such as the long-term mean cell rate of the connection, and another is its crisp structure with two fixed parameters of the threshold and the increment, which will be described later.
As specified in the ITU-T Recommendation I.371 document [1], dated May 1996, the Generic Cell Rate Algorithm (GCRA) is recommended as a conformance test for the cell stream of a connection. GCRA has two equivalent versions, the virtual scheduling algorithm and the leaky bucket algorithm. The latter seems to be better comprehended since it can be pictured as a virtual leaky bucket whose content determines the conformance of a cell. As shown in
FIG. 2
, the leaky bucket is viewed as a finite capacity bucket whose real-valued content drains out at one unit rate but is increased by T units for each conforming cell. If a cell arrives at the time t
a
when the bucket content X′ is above the threshold value &tgr;, then the cell is non-conforming; otherwise, the cell is conforming and the bucket content is added by an increment T.
When the shaper
18
and the policer
24
in the TS-UPC pair shown in
FIG. 1
employ the leaky bucket algorithm shown in
FIG. 2
as their schemes to monitor the sustainable cell rate of a connection, the threshold value &tgr; is taken to be &tgr;
IBT
+&tgr;′
SCR
and the increment T is taken to be the reciprocal of the negotiated sustainable cell rate &Lgr;
SCR
of the connection, where &tgr;
IBT
is the intrinsic burst tolerance (IBT) used to limit the burst size to the negotiated maximum burst size (MBS) and &tgr;′
SCR
is an additional tolerance added to account for the cell delay variation (CDV) introduced by multiplexing schemes. Details of the two parameters &tgr;
IBT
and &tgr;′
SCR
can be found in the ITU-T Recommendation I.371 [1]. The sustainable cell rate is used to enforce the mean cell rate of a connection, so it is straight forward to set &Lgr;
SCR
=&Lgr;
mean
for the TS-UPC pair, where &Lgr;
mean
is the mean cell rate claimed by the connection.
If &Lgr;
SCR
is set to be &Lgr;
mean
for the TS-UPC pair, then the possible rate fluctuations of the connection around the claimed mean cell rate will
Chang Chung-Ju
Eul Zohn-Shiun
Lee Hong-Yuh
Accton Technology Corporation
Kizou Hassan
Ly Anh-Vu H
LandOfFree
Fuzzy leaky bucket method and apparatus for usage parameter... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fuzzy leaky bucket method and apparatus for usage parameter..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fuzzy leaky bucket method and apparatus for usage parameter... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3028179