Fuzzy Congestion Control and Policing in ATM Networks: Ming-Chang Huang
Fuzzy Congestion Control and Policing in ATM Networks: Ming-Chang Huang
Fuzzy Congestion Control and Policing in ATM Networks: Ming-Chang Huang
Ming-Chang Huang
Department of Math & Information Systems University of Phoenix at Charlotte Charlotte, NC 28270
K. Vairavan
Department of Electrical Engineering and Computer Science University of Wisconsin-Milwaukee, P.O. Box 784 Milwaukee, Wisconsin 53201
Hui Lan
Department of Electrical Engineering and Computer Science University of Wisconsin-Milwaukee, P.O. Box 784 Milwaukee, Wisconsin 53201
ABSTRACT
In this paper, usage parameter control (UPC) is presented to ensure that each source conforms to its negotiated parameters in ATM networks. To meet the requirements for the policing function, a fuzzy logic-based system is proposed to deal with the congestion control and policing problem in ATM networks. There are four types of different mechanisms, Jump Window (JW), Exponentially Weighted Moving Average (EWMA), Leaky Bucket (LB) and modified Fuzzy Leaky Bucket (FLB) techniques to be identified, analyzed and simulated by the traffic parameters. The Fuzzy Leaky Bucket (FLB) modifies the token rate in accordance with the peak rate, mean rate and the burst time, which characterize the source behavior. Simulation results show that FLB system is transparent to the sources with the parameter values which are negotiated at the call setup and effective in detecting source violation with low response time. The performance of FLB is significantly better than other mechanisms, in terms of both dynamic behaviors of responsiveness and selectivity.
Keywords: ATM, Fuzzy Logic, Leaky Bucket, Jump Window, Exponentially Weighted Moving Average
1. INTRODUCTION
Based on todays telecommunication system and potential requirements, it is easy to predict that the future is the time of network. To support the futures applications, telecommunication should have the following characteristics: broadband, multimedia, and economical implementation for the diversities of services. Broadband integrated services and digital networks (B-ISDN) provide what are in need at present and in the future. Asynchronous Transfer Mode (ATM) is a targeted
65
technology for meeting these requirements [3, 4, 15, 14, 25]. In ATM network, the information is transmitted by using short fixed-length cells (cell switch) - which reduces the delay variance makes it suitable for transmission in new high-speed integrated service networks, such as voice, video and data. Meanwhile, ATM can ensure efficient operation to process the flexibility which is invited to support services with different rates, qualities of service (QoS) and characteristics. The asynchronous statistical multiplexing may also improve the utilization of the bandwidth for the traffic flows. In ATM network, a proper traffic control management is required to guarantee a certain QoS in terms of delay and cell-loss probability. The fluctuation of random traffic would cause a serious congestion problem for the network if the network exists (runs) without proper policing mechanism. An effective control mechanism is imperative to maintain a balance between the QoS and network utilization both at the time of call setup and during the progress of the calls across the ATM network. The control mechanism that allocates resources and judges rejection or acceptance of the connection is usually called Connection Admission Control (CAC) [3,4], and the control mechanism that monitors and smoothes the rate of the traffic during the call setup phase is normally called policing or Usage Parameter Control (UPC) [3, 4]. Policing is used to ensure the sources to stay between their declared rate limits (traffic contract); thus, it will not affect the performance of the network. In the case that a source disobeys its contract, the network provider would block the source or selectively drop packets by tagging packets (set CLP=1), which will be selectively dropped by priority bit if necessary when congestion occurs in the network. The traditional ATM networks use Leaky Bucket method as one of its policing mechanism. In this mechanism, it uses fixed threshold buffer size for store the tokens for traffic control purpose. In order to improve the performance of ATM networks, we use a virtual leaky bucket with fuzzy logic control to control the depletion rate in the bucket. We compare this Fuzzy Leaky Bucket mechanism with other policing mechanisms - Jump Window (JW), Exponentially Weighted Moving Average (EWMA), and traditional Leaky Bucket (LB). We have the simulations for comparing the results of these four mechanisms. This paper is organized as follows. Section 2 introduces the traffic management in an ATM network. Section 3 addresses conventional policing mechanism in ATM network and Section 4 presents the Fuzzy Leaky Bucket Algorithm (FLB). Section 5 shows the comparison, simulation results and analysis. Section 6 is our conclusion.
66
medium is complicated and it is hard to predict what the upcoming performance will be for these two network. Especially, the QoS of real time service can be easily harmed. 5. Different traffic characteristic should be studied and analyzed. As long as the transfer speed increases, call-waiting time vs. cell transmit time will increase simultaneously, which requires a higher level. Since high-speed data link has broad transfer delay, there will be huge cells moving at any point in the network. Furthermore compared with the submitting time, when the congestion occurs, the bigger the transfer delay is, the longer it will take for the network to detect what the congestion components are. High transfer speed also limits the processing time among the internal node for processing the congestion. Due to the high transfer speed, the congestion method should be an easy implementation for the hardware. For each connection, the QoS parameters should be supported and satisfied from the beginning of call setup to the end, in spite of other connections traffic characteristics and sources behaviors in the network. At most time the traffic source (customer) may not describe its traffic characteristics accurately enough. So, the good control technique should not only use these sample source traffic characteristics but also be steady enough to reduce the influence from the inaccurate traffic characteristics. In this environment, it is not an appropriate idea to use manual ways to limit user traffic characteristic. For example, the cell speed may be reduced before the call set-up and transfer to decrease the connection peak cell rate. Unfortunately, it is unacceptable for the time-delay sensitive application, though it may smooth the traffic in the network and make it easier to manage. An improper congestion control design may decrease the utilization of network. ATM network, as it is required, is designed to support not only the current but also the future applications, such as high bandwidth multi-media applications. A properly constructed ATM network should manage traffic fairly, provide effective allocations of the network capacity for different sorts of applications, and perform cost effective operations at the relative service level (QoS) stipulated by the network users. Meanwhile the network should support the different delay requirements of the applications, an important support function known as cell delay variation (CDV) management. ATM network is required to be able to adapt to unforeseen traffic patterns, for example, unusual bursts of traffic from the various end-user devices or applications. The network also should have the ability to shed traffic in certain conditions to keep it from or react to congestion. For protection, network must be able to enforce an allowable peak cell rate for each VPI/VCI connection. That is to say, it may be discarded on the occasion when a user's traffic load submitted to the network goes beyond the maximum peak rate. In addition to these responsibilities, the network should be able to monitor traffic, and all VPI/VCI connections, and verify their behaviors. The network must also detect problems, and emit alarms when they happen. An effective ATM network is designed with an understanding for both the user and network to assume responsibility for QoS operations between them. The user should agree with the service contract that ATM network stipulates the rules, such as the amount of traffic that can be submitted in a measured time period. On the other hand, the network assumes the responsibility of supporting the user QoS requirements. The fuzzy logic control method has been used in different ways. Lekcharoen et. Al, [11, 12] use the fuzzy logic control in QoS in wireless networks and in QoS sensitive backoff schemes. They use FLC in the buffer size and the fixed leak rate. It also uses it in Triggered Jumping Window(TJW). Lekcharoen, S. and Jittawiriyanukoon also discuss the policing mechanisms in deadlock of avoidance backoff schemes. Koutsakis, P and Paterakis, M. [30] use policing mechanisms in ATM networks the video-conference traffic in wireless ATM. Fuzzy logic control has also been used in the management of ATM networks [1, 2, 21]. In this paper, we add a virtual leaky bucket based on fuzzy logic control in controlling the buffer size and the leaky rate of tokens.
67
DROPPING SWITCH
TO THE NETWORK
CONTROL SIGNAL
The basic idea about token leaky bucket is that before a cell enters a network, the cell must obtain a token from a token pool. Upon consuming a token, the cell will immediately leave the leaky bucket. Tokens are constantly generated and placed in the token pool. There is a maximum number of tokens waiting in the pool. The size of the token pool will impose an upper bound on the burst length and determine the number of cells that can be transmitted to control the burst. As long as the queue is not empty, the cells are transmitted with the constant rate of the service rate. So the LB algorithm can receive burst traffic and control the output rate. If excess traffic
68
makes the buffer overflow, the algorithm can choose to discard the cells or tag them with CLP = 1 and transmit them into network. In this token bucket algorithm, choosing appropriate values of service rate and buffer size can control PCR or SCR. From another viewpoint, the LB mechanism consists of a counter, which is increased by 1 each time a cell is generated by the source and decreased in a fixed interval as long as the counter value is positive. At that time, cell arrival rate exceeds the decreased (leak/drain) rate; the counter value starts to increase. It is assumed that the source expects admissible parameter range on the occasion the counter reaches a predefined limit. The suitable actions (e.g. discard or tag cells) are taken on all subsequently generated cells until the counter has fallen below its limit again. This mechanism is quite easy to be implemented. Two important parameters for LB are the threshold N and depletion (leak/drain) rate d. In principle, in enforcing the mean cell rate to equal the negotiated mean cell rate, that is, d = n, the parameter N plays a very important role. Threshold N values can control the burstiness degree of LB. When N values are high, the allowance of burstiness degree and reaction time of the mechanism grows excessively; the cell loss ratio gets lower. Vice versa, the cell loss ratio turns higher. Since a cell has burstiness characteristic, in order to achieve greater flexibility in buffer size and reduce the probability of false alarms, it is necessary to introduce an over dimension bursty detective scope factor C (C1) between the negotiated cell rate n, and really policed cell rate p. It follows that d = p = Cn. On the other hand, it may reduce the capacity to detect violation over a long term. Especially in an extreme case of a deterministic source, the traffic generates cells may even exceed the negotiated cell rate up to a scope factor C without any cell being detected. In spite of its drawback, the LB mechanism is still popular and in wide use due to its simple implementation. 3.2 Jump Window Algorithm (JW) Other control methods are the window-based policing mechanism that regulates the traffic flow submitted to the network. In simple terms, window methods can be described as a method limiting the number of cells in a time window. Basically, the Jumping Window scheme imposes an upper bound on the number of cells accepted from a source during a fixed time interval referred to as the window. The new interval starts immediately after the end of the processing interval (jumping window) and the associated counter is restarted again with an initial value of zero. Once the upper bound is reached, all consecutively arriving cells are dropped and are not allowed to enter the network. These excessive cells then can be marked as low-loss priority using cell loss priority (CLP) bit [14, 7, 19]. Therefore, the length of the window is fundamental for the performance of mechanism. The time interval during specific cell influences the counter value varies from zero to window width N. Since JW does not have a queue mechanism, it is normal for JW to ask for a big window size; consequently JW does not have a good detective ability. 3.3 Exponentially Weighted Moving Average Algorithm (EWMA) Another well known window-based mechanism is the Exponentially Weighted Moving Average [14, 7, 19]. This scheme is similar to jumping window in which the window size is permanent and a new window is triggered immediately after the proceeding one ends. The difference between this scheme and the jumping window is that the number of cells accepted during one window varies from another. The EWMA mechanism uses fixed consecutive-time windows like the JW mechanism. However, unlike the JW, the limit of the max number (window size) is unfixed. For EWMA, the big difference is that the maximum number of accepted cells in the ith window (Ni) is a function that allows the mean number of cells per interval (windows), N, to be dynamically updated. An exponentially weighted sum of the number of accepted cells in preceding intervals (Xi) are significantly relate to the past amount (burstiness of cell rate), i.e., the number of accepted cells in the previous intervals. To calculate the max Ni in the ith window, the formula can use as below:
69
Ni =
N S i 1 1
<1
Ni =
where S0 is the initial value of the EWMA measurement; it is a constant given at random, which is usually set at S0 = 0. Ni is the max number of cell that can be received in ith window; N is the mean number of cell that can be received in each window; Xi is the number of cell already received in ith window. The constant weighting factor controls the flexibility more or less of the traffic burst. is a coefficient given randomly between the range of [0,1]. If = 0, Ni is constant and the algorithm is the same as the traditional JW mechanism. EWMA performance depends greatly on the value chosen for : for respectful sources, a high value is required; on the other hand, for violating sources it has to be low. The limit of this mechanism is its static nature and the prior choice of the value of . The implementation complexity of the mechanism EWMA is more complex than that of the previous mechanisms. The formula above may lead to a conclusion that, for different ; the changing degree of Ni is different. Ni is related to the number of the real arriving cells in the previous window, and the degree of influence on Ni is different in every window as well. The closer it is to the current window, the more influence on Ni will be present, and vice versa. EWMA mechanism is derived from JW. In EWMA, the monitor window can be changed based on the cell bursty condition. However, cell bursty situation can only be reflected from the formula and cell traffic can only be shown in a certain degree.
70
Fuzzy logic derives much of its power from its ability to draw conclusions and generates responses based on vague, ambiguous, incomplete or imprecise information. Upon this respect, fuzzy systems have a reasoning ability similar to that of humans. In fact, the behavior of a fuzzy system is represented in a simple and natural way. In this paper, a fuzzy logic-based system, fuzzy leaky bucket (FLB), is presented to deal with the congestion control problem in the ATM networks. FLB is based on a fuzzy logic implementation of virtual leaky bucket (VLB) and also on the fuzzy control theory [17, 20, 10] with rules such as: Rule: If the cell number in leaky bucket buffer is high and virtual leaky bucket counter number is medium then reduce the token rate and drop violating cells Where high and medium are linguistic labels of fuzzy sets in a given universe of discourse. In the synthesis of fuzzy leaky bucket controller, the control goal and strategy are stated linguistically but mapped into fuzzy sets and manipulated mathematically. The objective is to control the cell rate by fuzzy expert knowledge in the ATM congestion control, rather than depend on the mathematical formulation of classical control theory. This paper is organized as follows: ATM traffic control issues, source traffic models, and introduction of the fuzzy logic control (FLB) mechanism. The simulation results and conclusion are provided at the end. 4.1 ATM Traffic Fuzzy Control Issues The wide range of service characteristics, bit rates, and burstiness factors in the broadband networks combined with the need for flexible control procedures makes the traditional control methods very difficult to apply. It is impossible to analyze all the involved different traffic cases and traffic situations arising in an ATM network. Moreover, it is also difficult to update if there are new services introduced. Non-traditional control methods, on the other hand, contain the ideas and techniques of neural networks and fuzzy logic may use adaptive learning and are flexible enough to support a variety of criteria and wide range of parameters. Fuzzy logic has rapidly been developed as one of the most successful technologies today in the field of sophisticated control systems. It makes the control much smoother based on the linguistic variables. The reason is simple. Fuzzy logic processes some applications perfectly. For example, it may resemble or simulate human decision by developing an ability to generate precise solutions for certain or approximate information. It fills an important gap in engineering design methods that are left vacant by purely mathematical approaches (e.g. linear control design) and purely logic-based approaches (e.g. expert systems) in system design [17, 26, 20]. 4.2 Fuzzy Control for ATM Policing In order to give an example of how fuzzy inference rules can be defined in a typical ATM control, this section presents the fuzzy control for UPC purposes. The fuzzy policer is a mechanism, a threshold token rate R updated dynamically by the inference rules based on fuzzy logic. The goal of this fuzzy policer is to make the source respect to the negotiated contract, which is the mean cell rate over the duration of the connection. According to the expected behavior of an ideal policing mechanism, short-term fluctuations should be allowed as long as the long-term negotiated parameter is respected, and it should also be able to recognize a violation immediately. More specifically, the control mechanism grants credit to a source, which has respected to the parameter negotiated in the past, by increasing its control threshold token rate R as long as it maintains with non-violating behavior. Vice versa, if the source behavior is violating or risky, the mechanism reduces the credit by decreasing the threshold token rate value. In the fuzzy control system, the parameters describing the source behavior and the policing control variables are made up of linguistic variables and fuzzy sets. Then action of control is
71
expressed by a set of fuzzy conditional rules. The rules reflect the cognitive processes and knowledge that an expert in the field would apply. 4.3 Fuzzy Logic Control FLB Mechanism The Leaky Bucket (LB) mechanism is considered an effective method of UPC in ATM networks, but the conventional LB algorithm is difficult to be implemented on some conflicting requirements such as cell loss probability and mean time delay. It is difficult to monitor the mean rate and the peak rate at the same time. It is known that token rate should be around in the neighborhood of the peak rate and the buffer length has to be low for the mechanism to react effectively to the peak cell rate variations. In other words, in order to control the mean rate, the token rate has to be around mean rate and the buffer length is high. An ideal control mechanism is fast to act on cells violating the contract and limit the influence of an "ill-behaving" source on the quality of service provided for all connections sharing the network resources. More specifically, it should be transparent to connections with the traffic contract. Fuzzy logic based system has demonstrated the abilities to make intelligent decisions, perform calculations on imprecise quantities and model linguistic rules where precise mathematical models are impractical or unavailable. The inherited capacity formalize approximate reasoning processes offered by fuzzy logic is exploited to build a dynamic control mechanism, which is expected to smooth the rate of the traffic and improve the utilization efficiency of bandwidth [6, 17, 26, 20]. It should be pointed out that the token rate R and leaky bucket buffer length are crucial to cell loss rate and mean time delay. It is difficult to change the leaky bucket buffer length, but it is a proper choice to modify the token rate R. When the source has gained credit, R would be high to improve the utilization efficiency of bandwidth and decrease the time delay. Vice versa, if the source begins to violate, the R would be low to detect the long statistical fluctuation quickly. The FLB controller belongs to a general fuzzy control system in which control variables are transformed into fuzzy sets (Fuzzification) manipulated by a collection of IF-THEN fuzzy rules, and assembled in what is known as the fuzzy inference engine. These rules are derived from the knowledge of experts with substantial experience in the leaky bucket mechanism and ATM traffics. The FLB is a rule-based expert system. However, unlike expert systems, the FLB uses the membership function to generate approximate control actions to deal with different scenarios. This capability allows the FLB controller to compensate for ambiguities in the control rules; and it is common in the bursty environment that characterizes the ATM traffic cells. The modified LB technique has been combined in this paper to identify the traffic parameters. The modified FLB in our implementation is dimensioned for mean cell rate. The mean cell rate determines the long-term average transmission rate. Traffic falling under this rate will always be conformed, and the amount of the cells in the LB shows the burst time. The Fuzzy Leaky Bucket (FLB) modifies the token rate according to the mean rate and the burst time, which characterize the source behavior. The model of FLB is shown as Figure 1. This fuzzy leaky Bucket system is on the basis of fuzzy logic control. The virtual leaky bucket is designed to monitor the mean cell rate as cells pass through the ATM switch node and actually enter the network. Virtual leaky bucket leak speed Rv is equal to the negotiated mean cell rate Rneg. In another viewpoint, virtual leaky bucket can be considered as a cell number counter. Virtual leaky bucket is assigned an initial number Ni; the number that is related to the traffic flow characteristic. After traffic passes through the ATM switch node and gets into the network, each cell generates a virtual cell to get into the virtual leaky bucket. When a virtual cell comes out in the virtual leaky bucket, the virtual leaky bucket will keep leaking virtual cell at the rate Rv. Consequently, when the number of virtual cells in the virtual leaky bucket is greater than the initial number Ni, means the real mean cell rate getting into the network is higher. When the number of counter goes up, the deviation of cell gets bigger simultaneously, that means the mean cell rate is too high. On the other hand, when the number of virtual cells in the virtual leaky bucket is less than the initial
72
number Ni that means the mean cell rate getting into the network is low. The degree or deviation of lower value varies according to the number of counter. As shown in Figure 1, FLB consists of two fuzzy logic inputs: virtual leaky bucket counter number N and cell number in the leaky bucket buffer X. Virtual leaky bucket counter number N shows the cell burstiness. Meanwhile it also indicates its current behavior. Cell number in the leaky bucket buffer X is not fixed; it is based on the mean cell rate, current burst and up to negotiate peak cell rate. It may be greatly changed in a short period of time and give an indication of the long-term trend of the source. So, one type of corresponding relationship exists between the virtual leaky bucket counter number N and the cell number X in the leaky bucket buffer. However, this corresponding relation is hard to be described accurately in a conventional math model. Therefore, the traditional control method would not work well and efficiently. However, in this area fuzzy logic control does not require an accurate math model. The sample control rules are applied for controlling the system.
Sources
Network
CAC
Leaky Bucket Virtual Leaky Bucket Token Buffer N X R Token Rate Control K Fuzzy Reference Defuzzification
Rv
Fuzzification
Fuzzy Logic Leaky Bucket (FLB) Controller FIGURE 1: The Model of Fuzzy Control System (FLB)
The work principle of the FLB is: FLB chooses the cell number X in the leaky bucket buffer and virtual cell number N in the virtual leaky bucket (cell counter) as the crisp input parameters. After the three-step procedures: fuzzification, rules evaluation (make decision) and defuzzification, FLB gets the crisp output value K, K (0,1), then adjusts the token rate R=K h (h =PCR). After testing the membership functions chosen for the fuzzy sets, the above parameters are fuzzified by linguistic values shown in Figure 2~4. The input and output variables are divided into five fuzzy subsets: Very Low (VL), Low (L), Medium (M), High (H), Very High (VH).
73
1.0 VL L M H VH 1.0
VL L M H VH
0.25 M
0.5 M 0.75 M X
0.8 N
0.9 N N
1.1 N
1.2 N
1.0 VL L M H VH
M: the length of leaky bucket buffer. N: the number of virtual cells in VLB.
0.25
0.5 K
0.75
1.0
Fuzzy conditional rules for the policer are given in Table 1. The case will be discussed in which the source is fully respectful. When cell in leaky bucket buffer X is Low, thus, if N, the number of cells in virtual leaky bucket, is Low or Medium, that is, the source continues a non-violating behavior; its credit is increased and token rate K will be increased. If N is High, a sign of a possible violation on the part of source, K will be reduced to Medium correspond to the X is L. The other rules can be interpreted analogously.
X M VH H M L VL
N VL L M H VH
VL VH VH VH H M
L VH VH H M L
H H M L VL VL
VH L L VL VL VL
The Max-Min (Mamdani) inference and Centroid (center of gravity) defuzzification are used in this paper. The output value is the weight average of the individual outputs of the rules. The output can be calculated as follows:
Z* =
(Z )Z (Z )
i i
where
( Z i ) is the fitness value of the ith fuzzy rule, Z i is the center value of the output
*
membership functions of the ith item of the output linguistic variable, Z means the defuzzification output K in this paper. The Flb_3D_Surface curve of output K is shown in Figure 5. The Flb_3D_Surface curve of output K is a control surface. With two inputs N and X and one output Z, the input-output mapping is a surface. Its a mesh plot of an example of the relationship between N and X on the input side, and FLB controller output Z on the output side. The plot is based upon 25 rules. The 3D-output curve also shows the relationship between the output and
74
input and their fuzzy rules. For example, if X and N are very low, it can be seen from the output curve that Z is very high. For further improvements, FLB is only required to simply turn and reset up those control rules for changing the sharp degree of curve so as to make the system run more efficiently.
0.2
H 32 kbit/s
M 11.2 kbit/s
Ton
650 ms
Toff
352 ms
4 5
Where H is the peak rate, M is the mean rate. 5.1.2 Packetized Video Traffic
The general form of cell arrival process from video traffic sources characteristic is the MMPP model [23, 19, 22, 28, 18]. Variable rate coding using 1/30 s frame, the intergeneration time
75
distribution of video cells depends on the codec. A number of cells, which correspond to the amount of information conveyed in a one-frame interval, arrive at the maximum available rate for a codec from the frames start time. This paper uses a continuous state AR Markov model to evaluate the proposed mechanism. The Autoregressive Markov model (AR) was described in [23, 6, 8]. The model can be represented as follows: yt = ayt-1 + bwt where y is the data rate at time t, a and b are constant and w is the Gaussian white noise. This model has been proposed to approximate to a single video source. It is suitable for simulating the output bit rate of a VBR video source to a certain extent, when a = 0.87881, b = 0.1108, and w with a mean equal to 0.572 and a variance equal to 1. The lag time, Tb, is 1/30 seconds. This model attempts to characterize the bit rate in each separate frame interval of video traffic. The speed at which the frame information is transmitted does not change over time. The cells are generated from 60 other multiplexed video sources by sending gray 640 480 pixels MPEG traffic [9, 10]. 5.2 Simulation Results 6 In this section, in order to evaluate the efficiency of the fuzzy policer (FLB), the performances of FLB are compared to JB, EWMA and LB. The figures of values show the selectivity and responsiveness of the mechanisms; simulation is developed in Matlab. More specifically, to evaluate the fuzzy inferences, an inferential engine is implemented by using MAX-MIN (Mamdani) as the inference method and center of gravity as the defuzzification technique.
To compare these four mechanisms, assume that the peak cell rate (PCR) is not violated. The long term actual mean cell rate is violated to the negotiated average cell rate, indicating violation ratio = m/mneg, where m is the long-term real mean cell rate and mneg is the negotiation average cell rate. Detective factor also can be assigned as the detective burst factor. It used to monitor burst behavior which source may send cells with violated high peak speed in a very short burst period. It is defined that the ideal loss possibility = 1-1/(C* mean cell violation rate), C (is constant) = negotiated peak cell rate / negotiated mean cell rate, mean cell violation rate = actually cell rate from the source / negotiated mean cell rate. In LB mechanism, the leaky bucket capacity N = 60, detective scope factor C = 1.42; in JW mechanism window size W = 550, C=1.42; in EWMA mechanism W = 60, C =1.42, = 0.80, S0 = 0. For the fuzzy leaky bucket, the bucket capacity N = 45, C=1.42. The idea-CLP is the idea cell loss possibility, which can be obtained from (m - mneg)/m, m mneg. In addition, the ideal traffic congestion control philosophy and goal are fair for all customers. Customers are required to obey their traffic contracts with the network provider. When disobeying the contract and sending violate cells into network, the ideal traffic congestion control mechanism would discard all the violated cells to protect the network from congestion. However, for improving the network source utilization, network provider may allow some violated cells to enter network. In this case, if congestion occurs in the switch node, violated cells will be selectively discarded first (with CLP = 1) and other customers who obey its traffic contract will not be affected. Since ATM sends cells asynchronously, relative cells are queued in a buffer before being statistically multiplexed over the transmission path. Furthermore, its also a safe and fair mechanism to alarm those customers who do not know their traffic characteristics and intentionally send violated traffic to the network. To simulate the worst violation, 1- 1/1.2 (enlarge cell violation) is designed to simulate the performance results in this paper.
76
When violation ratio 1, the mean real cell rate is less or equal to the average violation cell rate, there is no cell violation. The policing mechanism should exhibit transparency for these respectful sources. In the ideal condition, CLR = 0 in the policing mechanism, but normally the real policing mechanism will lead to cell loss. It is known that it is better when CLR is lower, but in the same policing mechanisms, the detection factors will decrease when it is required to lower cell loss probability; and therefore more violated cells will get into network. So, when < 1, mechanism will decrease detection factors to reduce the cell loss probability; when > 1, in the case of violating sources, the mechanism should increase detection factors to prevent violated cell from getting into network. Sometimes it may be necessary to negotiate to get a best tradeoff. Normally when = 1, the cell loss probability should meet the QoS of different customers. The requirement for the cell loss probability also varies according to different services. 7 5.2.1 Performance of Selectivity versus Cell Rate Variation
In this paper, the performance of fuzzy logic leaky bucket mechanism (FLB) is evaluated in terms of selectivity and response time to cell violations compared to that of the most popular policing mechanisms: the leaky bucket (LB) and jump window (JW). It is also compared with the most effective window based mechanism: the exponential weighted moving average window (EWMA). First, the performance of selectivity is analyzed. The two windows based on policing mechanism are compared first. In Figure 4.5, compared with JW, EWMA curve is closer to the ideal curve. It means EWMA has a better performance of selectivity than JW because JW has a fixed window size which it could not adjusted following the bursty source condition and characteristics. On the other hand, EWMA has a changeable window size that can be re-adjusted the bursty source traffic condition and characteristics. This result shows that EWMA has a better flexibility and adaptability. The result also shows to that LB policing mechanism is better than JW but lightly worse than EWMA. The best policing mechanism so far is FLB. The FLB curve is very close to the ideal one and certainly FLB performs better than other traditional policing methods. (For simplicity, the CLP is assumed equal to 1.0 e 5.) FLB has a better selectivity performance and it can take a quicker action on a violating source for both the short and long term. When some sources intentionally send violated cells to the network, FLB will discard more violate cells as an alarm or penalty to make the sources obey their traffic contracts. The result for video traffic is shown in Figure 6 and the similar result is shown in Figure 7 for voice traffic.
8 9
10
10
-1
10
Cell loss probability
11 12 13 14
10
-2
10
-3
10
-4
Ideal LB EWMA FLB JW 1 1.2 1.4 1.6 Mean rate variation 1.8 2
10
-5
FIGURE 6: Performance of Selectivity versus Cell Rate Variations for Video Traffic International Journal of Engineering (IJE), Volume (3) : Issue (1) 77
15 16 17
C ell loss probability
10
10
-1
10
-2
18
10
-3
10
-4
10
-5
1.2
1.8
FIGURE 7: Performance of Selectivity versus Cell Rate Variations for Voice Traffic with C =1.2
19
A good policing mechanism should not only control source traffic violation correctly but also detect violated cell with a quick response. With the assumption of violated cell rate, the dynamic behavior may be defined as the ability to detect cell violation after receiving a few violated cells. The closer the detective proportion is to the real violated cell proportion, the better the dynamic behavior. The dynamic behavior reflects the response time. In comparing the dynamic behavior of FLB to that of the traditional mechanisms, Figure 8 and Figure 9 shows that FLB has the best dynamic behavior since FLB can detect source violation with the quickest response time by decreasing the token rate. FLB curve is very close to the ideal curve and in the steady state corresponds to a better decision than those of other traditional mechanisms do. This conforms to fact that conventional policing mechanisms are not able to work efficiently with the conflicting requirements of an ideal policing for the transparency and low response time. However, this problem does not exist in FLB. The reason is that FLB has the capacity to detect the violating cells with the shortest amount of time, then make a quick adjustable reaction to maintain a smooth control. FLB also allows short lighter violation cells to pass through the network for the purpose to improve the network resource utilization, and does not influence all network system such as the backbone and other users connection. It can be imagined that when the congestion happens, too many violate cells get into the network, it will cause a lot of data to be lost and to resend these data will make the situation
78
even worse. Therefore, a good policing mechanism such as FLB will make the system more efficient, steady and fair to all customers.
0.4 0.35 Violation cells detected ratio 0.3 0.25 0.2 0.15 0.1 0.05 0 LB EWMA FLB JW
500
1000
3500
4000
0.35 0.3 Violation cells detected ratio 0.25 0.2 0.15 0.1 0.05 0
LB EWMA FLB JW
500
1000
3500
4000
79
5.2.3 Performance Comparison between FLB and LB Systems Finally, since the fuzzy leaky bucket shows improvement over leaky bucket, emphasized to compare the performance of these two policing mechanisms. By using the ON-OFF traffic model, packetized voice is simulated with parameters shown above in Table 2. Video traffic is simulated second. The generated traffic is fed through FLB and LB, when source does not respect to the negotiated parameters (cell violation), the simulation result shows that FLB is better than LB because FLB system modifies the token rate adaptively and decreases the need for buffer length. As seen in Figure 10~11, when ATM network switch node gets into congestion, i.e., traffic disobeys its traffic contract and sends more violated cells into network, FLB can deal with these violating cells in a smaller buffer size and still have the same controlling ability compared with LB. The figure is produced when C=1.4. It is because that at the same buffer size for both policing methods, FLB has a larger cell loss probability which means it allows less violated cells to enter the network by controlling for the leaking speed (token rate). FLB discards more violated cells with a higher cell loss probability (CLP=1) when traffic which does not follow the traffic contract.
10
0
10
-1
10
-2
10
20
30
40
50 60 Buffer size
70
80
90
FIGURE 10: Performance of Cell Loss Probability (cell violation with C =1.4) vs. Buffer Size for Video Traffic
0
10
LB FLB
Loss probability
10
-1
10 International Journal of Engineering (IJE), Volume (3) : Issue (1) 0 20 40 60 80 Buffer size
-2
100
120
80
FIGURE 11: Performance of Cell Loss Probability (cell violation with C =1.4) vs. Buffer Size for
At the same time, for other performance characteristics, FLB can detect source violation with a shorter response time by decreasing the token rate. FLB is much better than LB in the dynamic detective behavior. It is clear that FLB shows a higher response capability for detecting and controlling violations in real time. Furthermore, the fuzzy logic would be combined with neural network to build an adaptive fuzzy control system and the relative parameters and fuzzy rules can be changed through adaptive learning to fit for different services. Till now, all the work is based on the analysis of the traffic and congestion control on the ATM switch node level. What is being done is to develop FLB policing mechanism based on the fuzzy logic combined with leaky bucket to protect and deal with the violating traffic in the UPC. The objective or goal of FLB policing mechanism is to lead the customers to obey their traffic contract, to prevent the violating traffic from getting into the main (backbone) network to violate network performance. In addition, all the analysis of this paper is on the cell level. Analysis on all level of the network, such as routing will greatly improve the network performance.
6. CONCLUSION
In this paper, a modified Leaky Bucket (LB) technique policing mechanism based on fuzzy logic system is presented to deal with the congestion control problem in ATM networks. Leaky Bucket mechanism (LB) is simple and easy to be implemented. However, its disadvantage is that the leaking rate is a constant so when there is mean cell rate violation, LB cannot reduce the high pressure for the main network. Therefore, a function is applied to control the leaking (token) rate. The main idea of FLB policing mechanism is to apply a fuzzy function to control the leaking rate. Fuzzy Leaky Bucket (FLB) identifies the traffic parameters and modifies the token rate based on the peak rate and the burst time, which characterize the source behavior. Due to the potential function offered by fuzzy logic, the FLB algorithm with an adaptive adjustment factor will balance the cell loss probability and the mean time delay, and also restrict the behavior of the traffic source to the traffic contract. From the above analysis and simulation results, FLB policing mechanism exhibits a good dynamic detective behavior, a high flexibility in selectivity performance and a fair capacity to meet the statistical properties of several B-ISDN traffic sources. The performance of the mechanism has been evaluated through several simulations and compared to some of the most popular policing mechanisms, such as the LB, JW and EWMA. The results show that the performance of FLB policer is much better than those of conventional policing mechanisms, in terms of both responsiveness and selectivity. The good performance is a result of the fuzzy feedback control mechanism since the token rate is adjusted on the fuzzy feedback control. EWMA can adjust the window size depending on the formula that reflects only a certain degree of few characteristics of cells in the network. However, FLB is based on the virtual leaky bucket and fuzzy logic. The mechanism monitors the real mean cell rate which gets into the network, then uses rules based fuzzy inference engine and defuzzification to adjust the token rate dynamically. Also, the control depends on its fuzzy characteristics. In the UPC parameter, mean cell rate is the average cell rate of the negotiated cells. It is detected in CAC; its a mean cell rate in the period between set-up and disconnecting a call connection. However,
81
UPC can only monitor the cell behavior periodically. For example, a period starts from one point in time and ends after a certain cell arrival. During this time period the mean cell rate may be greater than the negotiated cell rate, at that time the cell is violated. As long as time goes on, there is no cell coming in the next period, and the average cell rate may be lower than the negotiated cell rate. Consequently, that cell which violated at the beginning will not violate again. However, it takes a certain period of time to judge whether a cell is violated or not, but this time is not predetermined, and has a fuzzy characteristic. In addition, the relationship between virtual cell counter number N in virtual leaky bucket and cell number in the leaky bucket buffer X is also an un-determined fuzzy relationship. In the end, there are some final remarks that should be made about the prospects of the proposed approach. The problem should be solved with the choice of parameters describing the statistical properties of the various kinds of traffic. FLB mechanism shows a higher efficiency than others when the parameters are policed with the average cell rate for a long term. FLB is only good for less violation and quick response. What is important is to monitor and control the mean cell rate variation. This is why FLB may not be the best method for the cases in which the simulation time is very short. For the future work, an approach based on artificial intelligence techniques supported by the hypothesis with the neural network - Adaptive Neural-Fuzzy System may be improved to be more appropriate for the policing of other parameter characteristics of the traffic sources in the ATM network. Also, newer technologies such as genetic algorithm can be integrated to further enhance the performance of the hybrid systems. Overall, this paper emphasizes on ATM network fuzzy congestion control and policing. The fuzzy leaky bucket (FLB) method developed in this paper is good at cell violation controlling and shows better performance behaviors than other conventional policing mechanisms.
7. REFERENCES
1. G. Ascia, V. Catania, and Daniela Panno, "An Efficient Buffer Management Policy Based on an Integrated Fuzzy-GA Approach", IEEE INFOCOM 2: 1042-1048, 2002. G. Ascia, V. Catania, and Daniela Panno. "A Fuzzy Buffer Management Scheme for ATM and IP Networks", IEEE INFOCOM 3: 1539-1547, 2001. Uyles Black, ATM: Foundation for Broadband Networks, Prentice Hall, 1995. Uyles Black, Emerging Communications Technologies 2nd Edition, Prentice Hall, 1997. Milena Butto, Elisa Cavallero and Alberto Tonietti, Effectiveness of the Leaky Bucket Policing Mechanism in ATM Networks, IEEE Journal on Selected Areas in Communications, vol. 9, No. 3, pp335-341, April 1991. Ray-Guang Cheng and Chung-Ju Chang, Design of Fuzzy Traffic Controller for ATM Networks, IEEE/ACM Transactions on Networking, vol. 4, No. 3, pp460-469, June 1996. Walter J. Goralski, Introduction to ATM Networking, McGraw Hall, Publishing House of Electronics Industry, 1999. Harry Heffes and David M. Lucantoni, A Markov Modulated Characterization of Packetizd Voice and Data Traffic and Related Statistical Multiplexer Performance, IEEE Journal on Selected Areas in Communications, vol. Sac-4, No. 6, September Aug 1998. Raj Jain, The Art of Computer Systems Performance Analysis, John Wiley & Sons, Inc., 1991.
2. 3. 4. 5.
6.
7. 8.
9.
82
10. Jan Jantzen, Design of Fuzzy Controllers, Tech. Report no 98-E 864 (design), Technical University of Denmark, Department of Automation, Aug, 1998. 11. Somchai Lekcharoen, Chalida Chaochanchaikul and Chanintorn Jittawiriyanukoon. A design fuzzy control policing mechanisms on quality of service support in wireless networks, Proceedings of the 3rd ACM International Conference on Mobile Technology, Applications & Systems (Mobility 06), pp1-6, Bangkok, Thailand, Oct. 2527, 2006, 12. Somchai Lekcharoen and Chanintorn Jittawiriyanukoon. QoS Sensitive Fuzzy Backoff Schemes in Policing Mechanisms, IEE Proceedings of the International Mobility Conference (MobiCon'05), 2005, 1--6. 13. Somchai Lekcharoen and Chanintorn Jittawiriyanukoon. C. Deadlock of Avoidance Backoff Schemes in Policing Mechanisms, IEE Proceedings of the International Mobility Conference (MobiCon '05), 2005, pp.1--5. 14. Houming Liu, Computer Networks, Publishing House of Electronics Industry, 1997. 15. Shiwen Lu, Data Communications and ATM Network, Tsing Hua University Press, 1998. 16. Basil Maglaris, Dimitris Anastassiou, Prodip Sen, Gunnar Karlsson and John D. Robbins. Performance Models of Statistical Multiplexing in Packet Video Communications, IEEE Transactions on Communications, vol. 36, No. 7, July 1988. 17. Hung T. Nguyen and Elbert A. Walker, A First Course in Fuzzy Logic Second Edition, Chapman & Hall/CRC, 1999. 18. Naohisa Ohta, Packet Video Modeling and Signal Processing, Artech House, Inc., 1994. 19. Erwin P. Rathgeb, Modeling and Performance Comparison of Policing Mechanism for ATM Networks", IEEE Journal on Selected Areas in Communications, vol. 9, No. 3, pp325-333, April 1991. 20. Timothy J. Ross, Fuzzy Logic with Engineering Applications, McGraw-Hill, 1995. 21. R. Royand, S.S. Panwar, "Efficient Buffer Sharing inShared Memory ATM Systems with Space Priority Traffic", IEEECommunications Letters 6: 162-164, 2002. 22.] Hiroshi Saito, Masatoshi Kawarasaki, Hiroshi Yamada, An Analysis of Statistical Multiplexing in an ATM Transport Network, IEEE Journal on Selected Areas in Communications, vol. 9, No. 3, pp359-367, April 1991. 23. Mischa Schwartz, Broadband Integrated Networks, Prentice Hall, 1996. 24. William Stallings, High Speed Networks TCP/IP and ATM Design Principles, Prentice Hall, 1998. 25. Andrew S. Tanenbaum, Computer Networks, Prentice Hall Inc., 2004. 26. Hank B. Verbruggen and Robert Babuska, Fuzzy Logic Control Advances in Applications, World Scientific Series in Robotics and Intelligent Systems Vol. 23, World Scientific Publishing Co. Pte. Ltd., 1999. 27. Huigang Wang, Computer System Simulation Theory and Applications, University of National Defense Technology Press, 1994.
83
28. Hiroshi Yamada, Shuichi Sumita, A Traffic Measurement Method and its Application for Cell Loss Probability Estimation in ATM Network, IEEE Journal on Selected Areas in Communications, vol. 9, No. 3, pp315-323, April 1991. 29. Huiling Zhao, Guohong Zhang, Lin Hu and Youkang Shi, ATM, Frame Relay, IP Techniques and Application, Publishing House of Electronics Industry, 1998. 30. P Koutsakis and M. Paterakis, Call-Admission-Control and traffic-policing mechanisms for the transmission of videoconference traffic From MPEG-4 and H.263 video coders in wireless ATM networks, IEEE transactions on vehicular technology, vol. 53, no. 5, 2004, 1525--1530.
84