SSGRR - 2002W, JANUARY 21-27, 2002
1
A Fuzzy Logic-based Resource Management Scheme for High-quality Broadband Wireless Access Systems Romano Fantacci, Giovanni Giambene Abstract— This paper deals with the Radio Resource Management (RRM) layer of future Broadband Wireless Access System (BWAS). The interest here is in designing an efficient scheme able to integrate highly demanding traffics, such as high-quality real-time streaming video and interactive Web traffics. Many medium access protocols have been proposed in the literature for BWAS systems, but the fair sharing of resources and the achievement of a high throughput combined with good Quality of Service (QoS) levels are still open issues. We consider the traffic managed by an access point that coordinates video and interactive traffic terminals. These traffic sources notify the access point their transmission needs by means of a random access channel or a piggybacking scheme. In this paper we refer to a time division multiple access air interface and we propose an original solution where a medium access protocol and a usage parameter control technique are jointly adopted at the RRM layer. In particular, we adopt a cyclic assignment scheme with a novel traffic policer based on fuzzy logic for video sources and on a token-bucket approach for Web sources. Our scheme has been named Fuzzy Logic-Based Multiple Access (FLBMA) to remark the central function of the fuzzy policer. FLBMA performance has been derived through simulations. FLBMA achieves the following interesting results: (i) very high capacity of video traffic sources in comparison with alternative RRM schemes; (ii) fair service for video traffics; (iii) video traffic QoS independent of Web traffic load. This work represents the output of a research activity carried out under the financial support of MIUR and CNIT. Keywords— Computer Communications, Intelligent Systems, Newly Emerging Technologies, Mobile Personal Communications, Fuzzy Logic.
I. Introduction
T
HE management of radio resources is a challenging task for future Broadband Wireless Access Systems (BWASs) [1]. Medium Access Control (MAC) protocols and Usage Parameter Control (UPC) prorating techniques need to be jointly adopted to guarantee different Quality of Service (QoS) levels to competing traffics. Several MAC schemes have been proposed in the literature for managing multimedia traffics in BWASs [2]. Moreover, some examples of UPC techniques can be found in [3]. Aim of this paper is proposing a new Radio Resource Management (RRM) scheme integrating a MAC protocol and a UPC policer both operated by the Access Point (AP) to achieve good QoS levels and high resource utilization. In Dr. Giovanni Giambene (corresponding author) is with Dipartimento di Ingegneria dell’Informazione - Universit` a degli Studi di Siena, Via Roma, 56 - 53100 Siena, Italy. E-mail:
[email protected]. Prof. Romano Fantacci is with Dipartimento di Elettronica e Telecomunicazioni - Universit` a degli Studi di Firenze, Via S. Marta, 3 50139 Firenze, Italy.
what follows, we envisage a high bit-rate Time Division Multiple Access (TDMA) system with Frequency Division Duplexing (FDD), but the proposed RRM scheme could be also applied to a time division duplexing air interface. We consider real-time video (streaming class) and Web browsing (interactive class) as two challenging traffic classes in BWASs. The UPC policer decides the traffic admitted for the different sources on a frame basis by adopting a tokenbucket approach [3] for Web sources and a fuzzy logic-based regulator for video sources. The management of competing video traffics is a complex task, since a video stream exhibits unpredictable bitrate fluctuations and complex time-correlation. We propose the adoption of a policer based on Fuzzy Logic Controllers (FLCs) for video sources [4]. The fuzzy policer controls resource allocations according to the contractual QoS to be guaranteed to each video traffic flow. Hence, our proposed RRM scheme has been named Fuzzy Logic-Based Multiple Access (FLBMA). We consider the Mamdani’s FLC that is based on fuzzy rules of the type “IF antecedent THEN consequent”, utilizing linguistic variables to characterize both system status (FLC input) in the antecedents and the decision to be taken (FLC output, i.e., the control action operated on the system) in the consequents. A linguistic variable has possible “values” that belong to the language comprehensible to humans. All the “values” of a linguistic variable form the term set. Each “value” corresponds to a fuzzy set that is characterized by a Membership Function (MF) [4]. Antecedents and consequents are characterized by a symbolic expression of the type “linguistic variable is value”; AND, OR and NOT operators can be used to combine these expressions. IF and THEN parts of a given rule are related by means of the fuzzy implication; then, the outputs of different rules are aggregated according to an inference process and elaborated to produce a crisp output value that represents the controller decision. See the Appendix and [4],[5],[6] for more details. Although fuzzy logic is a powerful tool for traffic policing, it has not been extensively studied jointly with MAC schemes to evaluate the QoS experienced by different traffic sources. Moreover, there is not a univocal definition of the fuzzy rules to be adopted for achieving a fair UPC prorating scheme [7]. This is the reason why we propose here the FLBMA protocol, referring to a connection-oriented protocol stack on the air interface. In this paper we assume: (i ) a channel bit-rate Bc , equal to both 10 and 20 Mbit/s; (ii )
SSGRR - 2002W, JANUARY 21-27, 2002
a TDMA slot (duration Tslot ) allowing the transmission of a 54-byte packet (with a payload of Lp = 48 bytes for ATM standard compatibility, with a header and a trailer): Tslot = 8 × 54/Bc . II. Review of RRM Protocols for BWASs Several RRM protocols have been proposed in the literature for BWASs based on TDMA air interfaces [2],[8]. We provide below a concise survey of Dynamic Slot Assignment++ (DSA++) [8] and Prioritized Regulated Allocation Delay Oriented Scheduling (PRADOS) [2], since they have entailed developments for BWAS standards [9]. In the DSA++ scheme, a variable-length frame is considered with first a downlink transmission period and, then, an uplink one. The downlink interval has a signaling phase and, then, information slots. Whereas, the uplink part contains information slots and random access slots (where minipackets are transmitted). The AP dynamically shares resources between uplink and downlink on the basis of the related traffic loads and schedules transmissions according to a priority index that accounts for both the queue length and the deadline of the most urgent packet in the buffer of each traffic source. The PRADOS protocol is based on a variable-length frame formed by a downlink period, an uplink period and a contention interval. The AP defines the durations of these intervals at the beginning of each frame and dynamically schedules transmissions on the basis of priority class, traffic characteristics and QoS requirements (e.g., maximum packet delay) declared by a connection in the set-up phase. Terminal transmission needs are notified to the AP by means of requests (sent through the contention phase or piggybacked in the transmitted packets) that specify both the traffic type and the number of packets in the terminal buffer. A leaky-bucket regulator is used for every uplink and downlink source. Within a service class, traffic sources are served according to a round robin scheme. The protocol initially schedules the transmission of a packet just before its deadline; after having allocated all the packets, the scheduler anticipates the packet transmission time if some slots are idle. The FLBMA protocol is based on a different RRM scheme with respect to both DSA++ and PRADOS. In fact, FLBMA adopts a cyclic service discipline on a packet basis (MAC), according to the requests made by the terminals and decides resource allocations depending on the current QoS level experienced by each traffic source (UPC). III. Traffic Models We focus on a cell, where MV video and MW Web traffic sources produce variable bit-rate traffics, according to the models described below.
2
PRADOS and DSA++; the second traffic model derives from [11] and is more realistic, since it allows distinguishing between different images produced by an MPEG-1 codec, i.e., I (Intracoded ), P (Predicted ) and B (Bidirectional ) pictures. Let us summarize the basic characteristics of the fluid flow video traffic model shown in [10]. Each video source can be considered as the aggregation of M minisources, each alternating between ON and OFF states. A minisource in the ON state produces traffic at a constant rate of Υ bit/s; whereas in the OFF state no traffic is generated. The time intervals (in slots) spent in ON and OFF states are geometrically distributed with mean values p and q, respectively. Parameters p, q and Υ result as [10]: 2 m + σm bit , Υ= M s
p=
2
m 1+ M σ2
ξTslot
[slots] , q =
2
σ 1+ M m2
ξTslot
(1)
[slots]
where m (σ 2 ) is the mean (variance) of the bit-rate produced by a video source and parameter ξ characterizes the slope of the auto-covariance function of the bit-rate produced by a video source. We use the following parameters: m = 512 kbit/s, σ = 256 kbit/s, M = 10 minisources and ξ = 3.9 s−1 [10]. Correspondingly, Υ = 179.2 kbit/s, p = 8310 slots and q = 20800 slots. The activity factor for a minisource is = p/(p + q) = 0.285. The bits produced by this source are packetized with the format considered in Section I. In this traffic model, each packet must be transmitted within a maximum Packet Transmission Delay, P T Dmax (otherwise it is dropped by the source). We have adopted P T Dmax = 90 ms [12]. Let us now describe the characteristics of the video traffic model proposed in [11]. In a typical MPEG-1 (12,3) coding scheme, there is a periodic IBBPBBPBBPBB sequence of 12 pictures that is named Group of Pictures (GoP). The I-picture is based on an intra-coding of the image, without any reference to previous or following pictures. Whereas, a P-picture is obtained by coding the motion with respect to a previous I or P image, thus obtaining a high compression degree. Finally, a B-picture is coded by considering the differences with both the previous and the following picture. Of course, I-pictures are the most important ones for the video quality. In order to simplify our traffic generator, we will adopt the same model for both P- and B-pictures, since P-pictures typically entail more traffic than B ones (conservative approach). The following hypotheses have been considered for this video traffic model [13]: The number of packets generated in a P-picture is independent of the number of packets in the previous I-picture; •
A. Traffic Models for Video Sources In this paper we use two distinct video traffic models: the first one is a simple approach that derives from [10] and has been used since it permits an easy performance comparison of FLBMA with the following RRM schemes:
The number of packets generated in an I-picture is independent of the number of packets in the previous picture. •
The first assumption is due to the fact that the coding of
SSGRR - 2002W, JANUARY 21-27, 2002
3
into account that we have one I-picture and 11 other pictures in a GoP and that packets are lost due to deadline expiration according to the Packet Loss Rates P LRV −I and P LRV −P , respectively: AP Rav =
Fig. 1. Markov chain models for the generation of I- and P-pictures.
the P-picture is different from the coding of the I-picture. The second hypothesis has been adopted to account for the fact that I-pictures have an intra-coding that does not refer to previous pictures. We consider a traffic generator based on two Markov chains: one for I-pictures and the other for non-I-pictures (practically, P-pictures). The generations in these chains are independent, according to the previous assumptions. When a given source is in a state, it emits at a constant bit-rate. Every 40 ms, the bits produced by a chain or by the other (depending on the type of picture that has to be generated in the GoP) are collected to form a given picture; all the packets of a picture must be transmitted within P T Dmax , otherwise they are dropped. We assume a stringent constraint for this traffic model: P T Dmax = 45 ms [12]. During simulations, we have considered that the different video sources in a cell are not synchronized (i.e., their GoP have random shifts). The traffics produced by the Markov chains of I (or P) pictures can be thought as the aggregate generation of MI (MP ) ON-OFF equal and independent minisources. State sojourn times are evaluated in τI units for the I-minisource and in τP units for the P-minisource (we will have that τI and τP are both greater than Tslot , i.e., the packet transmission time, adopted as a basis for simulations). The following derivations apply to both I and P minisources; thus, we have omitted subscripts for the different symbols. Let 1 - α denote the transition probability from the ON state to the OFF state in a τ time; let 1 - β denote the transition probability from the OFF state to the ON state in a τ time. A minisource in the OFF state does not generate packets; whereas, in the ON state one packet is generated every τ seconds [14]. The minisource activity factor is 1−β = 2−α−β . The superposition of the minisources gives the Markov modulating process shown in Fig. 1, where for the I source we have: M = MI , β = βI , α = αI , = I , τ = τI and Υ = ΥI (when the source is in the state i, 0 ≤ i ≤ MI , it generates iΥI bit/s corresponding to i/τI packets/s); whereas, for a P-source we must consider: M = MP , β = βP , α = αP , = P , τ = τP and Υ = ΥP . For an aggregated I-source (P-source) the Average Packet Rate (APR), AP RI (AP RP ), is equal to MI I /τI (MP P /τP ). The total traffic load produced by a given video source, ηV , is: packets ηV = AP Rav Tslot (2) slot where AP Rav is the average of AP RI and AP RP taking
AP RI (1 − P LRV −I ) + 11AP RP (1 − P LRV −P ) . 12 (3)
On the basis of [13],[14], we obtain the following parameter values by assuming MI = 10 minisources and MP = 5 minisources (the I-source has more states to model its expected higher traffic variability): AP RI = 9237.59 packets/slot, AP RP = 2376 packets/slot, τI = 4.96×10−4 s, τP = 5.78×10−4 s, αI = 0.70, αP = 0.80, βI = 0.80, βP = 0.92. Let P LRV denote the video packet loss rate averaged over all the pictures. P LRV cannot exceed P LRV M AX to avoid excessive video QoS degradation. We use P LRV M AX = 10−4 for both video traffic models. B. Web Source Traffic Model A simplified model derived from [15] is considered that characterizes the traffic produced at the session level: a Web source alternates between a packet call state during which IP datagrams are generated and a reading time state where no traffic is produced. The number of datagrams per packet call is geometrically distributed with expected value mN d = 25. The datagram interarrival time and the reading time are exponentially distributed with mean values mDd = 0.5 s and mDpc = 4 s, respectively. The source activity factor is ψW = mN d mDd / (mN d mDd + mDpc ) ≈ 0.76. Each datagram has a random length in bytes according to the truncated Pareto probability density function (pdf) shown in [15]. Before transmitting datagrams, they are packetized with the packet format described in Section I. From the pdf shown in [15], we obtain the following distribution of the datagram length in packets, lW : P rob.{lW = j packets} =
=
1 −
κυ [jLp +1]υ ,
κυ [(j−1)Lp +1]υ κυ [(j−1)Lp +1]υ ,
−
κυ [jLp +1]υ ,
j =2 2 < j < LW.max j = LW.max (4)
where υ = 1.1, κ = 81.5 bytes, Lp = 48 bytes in the packet payload, LW.max = dlW.byte.max /Lp e, being lW.byte.max = 66666 bytes and d.e the ceiling function. From (4), the mean datagram length is LW = 10.5 packets. The total traffic load produced by Web sources, ηW , is: ψW packets ηW = LW Tslot MW (5) mDd slot where ψW /mDd represents the mean datagram arrival rate. During a packet call, a Web source produces a mean bitrate of about 7.6 kbit/s. We consider that each Web source
SSGRR - 2002W, JANUARY 21-27, 2002
Fig. 2. Variable-length frame structure for the FLBMA scheme.
needs to have guaranteed a minimum bit-rate Bmin = 4 kbit/s. Before accepting another Web traffic session in the cell, the connection admission control has to verify whether its minimum bit-rate requirement can be met. Moreover, the maximum number of Web sources that can be supported in a cell depends on the buffer stability constraint, detailed in sub-Section IV-E. The performance for Web traffic sources can be measured in terms of the 95-percentile of the datagram transmission delay, DW 95 .
4
transmission request is transported by a minipacket (access burst) that is practically obtained by eliminating the payload from a normal packet (i.e., a 6-byte minipacket is used to convey essential information for the FLBMA protocol, e.g., source identifier and datagram/picture length). Accordingly, we can determine the number of minislots per slot, Nm . By leaving a given margin to compensate for different propagation delays and timing advance errors in the access phase, we consider Nm = 8 minislots/slot. The number of minislotted slots C (≥ 1) is frame-by-frame updated, as explained in the following sub-Section B. Since the AP receives the transmission requests for the different video pictures specifying their lengths, the AP can evaluate a provisional frame length, Tˆf , so that each video source can transmit one picture in the frame. Hence, the AP considers an RT part of the frame with provisional M PV length Vˆ = Li , where Li denotes the mean picture i=1
length in packets (averaged over the last 12 pictures) for the i-th video source. Hence, we have:
IV. The FLBMA Resource Management Scheme The FLBMA protocol is centrally managed by the AP to share resources among video and Web traffics. FLBMA updates slot assignments on a frame basis, according to the requests made by the Mobile Terminals (MTs). A detailed description of the proposed RRM scheme is provided below. A. Frame Length Selection In our TDMA-FDD air interface, the structure of the generic uplink frame is illustrated in Fig. 2, where the fields denoted by FH, RT, NRT, CP are described below: • FH (Frame Header ): time interval (F slots) during which the AP transmits signaling information to MTs (e.g., frame preamble, slot assignment commands, frame length, starting instant of the next contention phase);
RT (Real-Time): time interval of variable length devoted to video traffics; •
NRT (Non Real-Time): variable-length time interval for Web traffics; its minimum duration is equal to W slots. The value of W depends on both Bmin and the maximum number of Web traffic sources that we want to admit in a cell, MW.max , as: Bmin Tf Tslot W = MW.max [slots] (6) 8Lp •
where Tf is the frame length in slots. From (6), W depends on Tf ; but Tf depends in turn on W . Hence, the AP runs an iterative method (based on (6) and the following equation (8)) to determine Tf and W . Thus, W is updated on a frame basis, as shown in the following sub-Section D. CP (Contention Period ): variable-length time interval (C slots) updated on a frame basis that is used for the random access channel. This interval is minislotted: each •
Tˆf = F + C + W + Vˆ [slots]
.
(7)
In the case of the video traffic model shown in [10], there is not the generation of pictures, but a fluid flow packet generation process is considered where each packet has a deadline that expires a time P T Dmax after its generation. In order to adapt the above definition of the provisional frame length to this case, we consider that a given video source produces a transmission request update every 40 ms, containing the number of packets generated in the meantime. Hence, in the definition of Tˆf , Li denotes the number of packets generated by the i-th video source during a 40 ms interval. The actual frame length, Tf , is variable between a minimum Tf min and a maximum Tf max : Tf min : it is the minimum time interval to guarantee FH, CP fields and the minimum capacity of W slots for Web sources (i.e., Tf min = C + F + W |min slots). •
Tf max is selected to allow a correct behavior (for the management of video sources) of the piggybacking scheme (see the next sub-Section) adopted by the FLBMA protocol for allowing an MT to update its transmission needs when it is already sending data to the AP. In fact, since a video picture is produced every 40 ms and all its packets have the same deadline P T Dmax (for the video traffic model in [11]), also the deadlines of subsequent pictures occur every 40 ms. Hence, if Tf < 40 ms, we cannot have that two consecutive pictures have deadlines expiring in the same frame; thus, a given picture can piggyback the transmission request for the next picture. If Tf > 40 ms, the AP could not receive the piggybacked request in time. Practically, we assume for Tf max the value in slots that corresponds to 40 ms: Tf max = b0.040/Tslot c, where b.c is the floor function. •
SSGRR - 2002W, JANUARY 21-27, 2002
In conclusion, the actual frame length is obtained as: n o Tf = min Tf max , Tˆf [slots] .
5
(8)
B. Notification of Transmission Requests to the AP An MT needing to transmit new data to the AP (but with no active request at the AP) waits for the next CP (the MT knows when the CP starts from the FH) and randomly selects one minislot to transmit its access burst that contains the MT identifier and the following data: inst.gen field that specifies the generation instant of a picture (datagram) for a video source (for a Web source); •
priority field that envisages three different priority levels (from the highest to the lowest): I-picture, P-picture, datagram;
•
leng.msg field that denotes the length of the new picture (or datagram) in packets.
•
When sending an access burst, there are two possible outcomes: Only one MT transmits in the selected minislot. Hence, the AP correctly receives the access request (we neglect here channel impairment effects) and sends the acknowledgment/assignment message to the interested MT in the next FH period. •
More MTs transmit in the same minislot: a collision occurs and the AP is unable to correctly decode any request (we neglect the capture effect). Consequently, the involved MTs do not receive any acknowledgement in the next FH period and, therefore, they retry in the next CP phase. •
The number of minislotted slots of the CP phase, C, is made variable, depending on the number of MTs that have not a transmission request at the AP, Nuof f . Ideally, we should have a number of minislots in the CP, Nms , equal to the number of MTs that need to send access requests in order to maximize the throughput of requests successfully sent per minislot. Since the AP does not know at the beginning of a frame how many MTs will attempt transmissions, the following worst-case is assumed: all the Nuof f MTs need to access the AP in the same CP. Correspondingly, Nms is obtained as follows: minislots Nms = CNm (9) f rame m l max{Nm ,Nuof f } where C = . Nm An MT needing to transmit new data does not use the random access phase if it has an active request at the AP: this MT piggybacks a new transmission request by filling inst.gen, priority and lung.msg fields in the header of the last packet sent to the AP with the previous request. According to the models described in Section III, video sources continuously transmit to the AP (they almost always send piggybacked transmission requests to the AP).
Thus, video sources do not practically contribute to Nuof f . This is important to reduce the number of slots that must be minislotted for the CP. Hence, the mean number of CP slots per frame can be approximated as: max {Nm , MW (1 − ψW )} E [C] ≈ [slots] . (10) Nm C. Management of Video Traffic Sources The AP schedules the different transmissions on the basis of the requests coming from MTs (by means of either random access or the piggybacking scheme). We assume that slot allocations are computed at the very beginning of the frame so that they can be broadcast in the FH period. It is important that the V resources of the frame are fairly assigned to the different video traffics. For instance, an excessive slot allocation to a given video source may cause a P LRV increase for all the other video sources. Otherwise, an insufficient allocation to a given video source may lead to the increase of its P LRV value. Hence, a trade-off solution needs to be reached. This is a complex task that can be solved by adopting a UPC prorating scheme based on fuzzy logic. In particular, the number of slots assigned to each video traffic source in a frame is regulated by a fuzzy policer. Moreover, the allocation of slots in the frame to the different video sources is obtained according to a cyclic service policy. We give below a detailed description of the RRM scheme adopted for video sources. Let U denote the total number of packets (among all the active video sources) whose deadline expires in the current frame (= urgent packets). Let Ui denote the number of urgent packets belonging to the i-th video source. The following cases are possible: 1) U ≤ V 2) U > V . In case 1) there is room in the current frame to transmit all the urgent video packets1 and V - U slots are also available to serve non-urgent video packets and Web traffic packets. Whereas, in case 2) there is an excess of urgent packets, Nurg = U - V , that cannot be transmitted in time. Hence, a fuzzy policer is used to decide how many slots can be assigned to the different video traffic sources in the frame. It is based on five steps, each managed by an FLC per video source (Fig. 3), that progressively increase the number of urgent packets that cannot be served in the frame (thus they are dropped) among all the video sources; the number of dropped packets at the (j + 1)-th step is Ndrop(j+1) > Ndrop(j) , j = 1, 2, 3, 4. In particular, at the j-th step, the AP uses an FLC policer for the i-th video source (Fig. 4) whose crisp input values are: 1 Even if there is room in a frame to serve all the urgent packets, we could still have dropped packets; this could occur when two urgent pictures have close deadlines. However, video sources are not synchronized in their traffic generations, so that the cyclic service discipline allows negligible dropping due to this phenomenon (especially when P LRV ≤ 10−4 ), that, anyway, has been evaluated during simulations.
SSGRR - 2002W, JANUARY 21-27, 2002
6
since these sources can tolerate some dropped packets without degrading their QoS. At the end of this first step, the Ndrop(1) value is identified: If Ndrop(1) ≥ Nurg , the policing process is stopped at the first step; if Ndrop(1) > Nurg , we reduce the number of dropped packets by cyclically reassigning slots to the video sources (in order of decreasing P LRV i values) so that the 1 condition Ndrop(1) = Nurg is met with the updated Nall,i values. •
Fig. 3. Flowchart for the five levels of the fuzzy policer for video traffic sources.
Fig. 4. FLC scheme for the i-th video source at the j-th step.
• P LRV i , the percentage of dropped packets estimated by the AP for the i-th video source (2 ). The P LRV value for each video source can be classified by means of a linguistic variable with possible values (from the highest to the lowest quality): excellent, good, minimum acceptable and bad (see below the definition of the input fuzzy sets).
typePi, related to the type of picture to be transmitted3 . An I-picture (P-picture) has typePi = 1 (typePi = 0). The value of parameter typePi is notified to the AP by the video source itself in the priority field included in the transmission request. •
The output of the FLC policer at the j-th step for the i-th video source is the percentage of urgent packets transmitj ted in the frame for this source, Nall,i ; the number of urNj
all,i . Thus, we have: Ndrop(j) = gent packets served is Ui 100 j M PV Nall,i Ui 1 − 100 . The behavior of the video fuzzy po-
i=1
licer can be explained as follows. At the first step, the FLCs (i.e., one FLC for each video source) assign small j numbers of lost packets (i.e., Nall,i < 100%) only to video sources currently experiencing an excellent P LRV value, 2 This value can be continuously evaluated by the AP as the difference between the number of packets to be sent (according to the requests) and the actual number of packets transmitted by the source for each request. 3 Since T ≤ 40 ms, each video source can have at most one urgent f picture in a frame (i.e., a picture whose deadline expires in the frame). Hence, all the urgent packets of a video source belong to a single picture (of I or P type).
• If Ndrop(1) < Nurg , the first step is not sufficient to determine the number of dropped packets among all the video sources. Hence, the second step is performed. In this case, FLCs adopt more stringent criteria to determine the number of dropped packets for the video sources. In particular, a greater number of lost packets is assigned to video sources with an excellent P LRV value and dropped packets are also assigned to video sources with a good P LRV value. At the end of this step, the total number Ndrop(2) (> Ndrop(1) ) of dropped packets is determined. If Ndrop(2) ≥ Nurg , the policer stops at the second level, otherwise it goes to the third level or further.
If at the end of the fifth step, Ndrop(5) < Nurg , Nurg Ndrop(5) packets are de-allocated (with respect to the assignment of the fifth step) from the video sources according to a cyclic discipline, starting from those video sources experiencing the best P LRV i values. For a quick policing action, all the steps can be performed in parallel. Let us describe the fuzzy formulation for the video policer. The Universe of Discourse (UoD) is the range of possible values for an FLC input/output fuzzy set. The UoD related to P LRV i is continuous: [0 , 1]; whereas, the UoD related to typePi is characterized by crisp values: {0, 1}. The P LRV i UoD is divided into the following input fuzzy sets: VF (Very Few ), F (Few ), M (Marginal ) and Mu (Much); their MFs (see the Appendix) have been heuristically identified so as to characterize different P LRV “values”. In fact, we consider the Z-, Λ- and S-type MFs shown in Fig. 5 that have the following supports: VF = [0 , 10−5 ] (“diamond” marked curve) for the MF that characterizes cases where P LRV i is extremely small so that the video QoS is excellent.
•
F = [10−6 , 10−4 ] (“square” marked curve) for the MF related to very small P LRV i values so that the video QoS is good. •
M = [10−5 , 10−3 ] (“triangle” marked curve) for the MF that characterizes P LRV i values close to the minimum threshold for an acceptable video quality (the video QoS is at the minimum acceptable level). •
Mu = [10−4 , 1] (“x” marked curve) for the MF related to very high P LRV i values, so that the video QoS is bad. •
The MFs of the previous fuzzy sets have been selected for allowing an accurate classification of the P LRV status experienced by each video source.
SSGRR - 2002W, JANUARY 21-27, 2002
7
j Fig. 7. Membership functions of the output fuzzy sets for Nall,i .
Fig. 5. Membership functions of the input fuzzy sets for P LRV i .
following fuzzy rules. In fact, eight fuzzy rules have been adopted for each FLC at each step (see Table 1), according to a heuristic approach based on priorities in allocating resources depending on both the P LRV i value and the type of picture (typePi ). In particular, video sources having I-pictures and/or experiencing a bad P LRV i value are prioritized. The choices made by the rules in Table 1 can be explained by means of the following example that refers to the first fuzzy rule of step 1: Fig. 6. Membership functions of the input fuzzy singletons for typePi.
The fuzzy sets defined in the typePi UoD are the fuzzy singletons CL (Clearable) and NCL (Non-Clearable) shown in Fig. 6, where: CL = 0 denotes that a picture has a low priority (e.g., Ppicture) and that it is clearable if the number of resources is insufficient, as explained later in this sub-Section; •
•
NCL = 1 identifies the high priority of an I-picture.
j Nall,i belongs to the output UoD Y = [0 , 100]%, where we define output fuzzy sets characterized by Λ-type MFs (see Fig. 7) with the supports detailed below: •
VF (Very Few ) = [50, 70]% line with “square” markers;
•
F (Few ) = [60, 80]% line with “triangle” markers;
•
AF (Almost Few ) =[70, 90]% line with “circle” markers;
•
AA (Almost All ) = [80, 100]% line with “x” markers;
•
A (All ) = [90, 100]% line with “+” markers.
Note that the MFs defined in the output UoD are equal to 0 j for Nall,i < 50%. This choice relies on the video coding process and on the error concealment techniques: if a received picture is corrupted, it can be reconstructed on the basis of the correct information in it and in the preceding pictures [16]. However, we assume that it is preferable not to transmit pictures experiencing an excessive (i.e., greater than 50%) packet dropping. This entails a saving in resources (particularly important in conditions of traffic congestion) that can be beneficial for transmitting completely pictures of other high-priority video sources, as considered in the
“if P LRV i belongs to the input fuzzy set VF and typePi belongs to the input fuzzy singleton CL, then the percentage of urgent packets that the i-th video source is enabled to transmit belongs to the output fuzzy set AA”. If the following steps are considered, the fuzzy output of the first rule progressively belongs to the sets AF, F, VF and VF, so that the number of dropped packets increases. For a given step j, each of the height fuzzy rules for the i-th video source yields an output MF through a mininference method [6]; then, the output MFs of all the rules are aggregated by means of the max-composition scheme [6] to obtain the output MF µjout,i (y), where y belongs to the output UoD Y ; more details are given in the Appendix. In Fig. 8 (a) and (b) we show an example of output MFs µjout,i (y) for j equal to 1 and 2 that result from Table 1, the definition of the related fuzzy sets and the following crisp input values: P LRV i = 6.34×10−6 and typePi = 0. The crisp output value for the i-th video source at the j j-th step, Nall,i , is obtained from µjout,i (y) through defuzzification by means of the center of mass method [5],[6]: R j Nall,i = YR
yµjout,i (y) dy µjout,i (y) dy
.
(11)
Y
At the end of this policing process, the AP identifies the number of packets to be transmitted for each video source in the frame. Slots are not sequentially assigned to a given video source, but they are cyclically distributed within the frame among all the video sources; this cyclic assignment avoids that a given video source receives service with a significantly greater delay than other sources. The AP broadcasts the resulting slot allocation pattern to the different video sources in the FH period.
SSGRR - 2002W, JANUARY 21-27, 2002
8
TABLE I Fuzzy rules adopted by the different steps of the video traffic policer.
Fuzzy rules j 1) IF P LRV i is VF and typePi is CL THEN Nall,i is j 2) IF P LRV i is VF and typePi is NCL THEN Nall,i is j 3) IF P LRV i is F and typePi is CL THEN Nall,i is j 4) IF P LRV i is F and typePi is NCL THEN Nall,i is j 5) IF P LRV i is M and typePi is CL THEN Nall,i is j 6) IF P LRV i is M and typePi is NCL THEN Nall,i is j 7) IF P LRV i is Mu and typePi is CL THEN Nall,i is j 8) IF P LRV i is Mu and typePi is NCL THEN Nall,i is
step 1 AA A A A A A A A
step 2 AF A AA A A A A A
step 3 F A AF A AA A A A
step 4 VF A F A AF A AA A
step 5 VF AA VF AA F A AF A
minimum allocation is guaranteed by the definition of W in (6). The remaining available slots to complete Tf (if any) are cyclically assigned to Web sources on the basis of their transmission requests and starting from the source with the highest number of tokens (weighted round robin). Sources that have exhausted their tokens or that have transmitted all the packets of the datagrams are removed from the cycle. The information on the slots assigned to each Web traffic source is broadcast in the FH period. E. System Throughput
Fig. 8. Examples of video policer fuzzy output MFs µjout,i (y), for j = 1 (case a) and j = 2 (case b), with the following crisp input values: P LRV i = 6.3×10−6 and typePi = 0.
D. Management of Web Traffic Sources The remaining slots within V (if any) after having assigned video traffics plus W slots are cyclically assigned to Web sources. According to [17], a round robin scheme (actually, its ideal version called processor sharing) is more convenient than the First-Input First-Output (FIFO) discipline to manage the transmission of Poisson arrivals when the distribution of their transmission times, T , permits to have E[T 2 ] > 2E[T ]2 . This condition is strongly verified for the heavy-tailed Pareto distribution of datagrams (Section III). Thus, we have considered that a round robin approach is a particularly effective solution also for the Web traffic modeled in Section III. The AP generates tokens (= permissions to transmit a packet) for each Web source with a rate equal to the mean packet arrival rate declared by the source in the session set-up phase. Tokens are put in a suitable bucket (one for each data source). One token is drained from the bucket when the AP enables the transmission on a slot for a given Web source. First of all, the AP estimates the minimum number of slots that a Web source needs to have assigned in the frame in order to fulfill its Bmin requirement; this
The utilization of a slot (i.e., the total throughput, ηtot ) has been expressed in the following formula that also includes the stability condition for the buffers of Web sources (video source buffers have no stability problems, since they drop the packets experiencing an excessive access delay): packets ηtot = ηV + ηW + ηO < 1 (12) slot where ηV is given in (2), ηW is expressed in (5) and the total overhead load, ηO , is evaluated as the ratio between the average number of slots destined per frame to CP and FH and the average total number of slots per frame, E[Tf ]. V. Results Each simulation result shown in this Section has been obtained by repeating 10 times a simulation of 40 millions of slots to achieve reliable results. All examined cases fulfill the stability condition (12). We have considered Nm = 8 minislots/slot for the CP slots and a frame header length of F = 10 slots. We have performed simulations in order to compare FLBMA with PRADOS [2] and DSA++ [8] in the presence of video traffics according to the model in [10]. The results are in Fig. 9, where we show P LRV as a function of the number of video sources per cell for Bc = 10 Mbit/s. We can note that FLBMA significantly outperforms both PRADOS and DSA++. In fact, FLBMA can manage up to 11 video sources per cell guaranteeing P LRV ≤ 10−4 ; whereas, DSA++ and PRADOS cannot permit to support more than 5 video sources. These good results are due to the cyclic service discipline for the different video sources
SSGRR - 2002W, JANUARY 21-27, 2002
9
Fig. 11. PLR values for I-pictures, P-pictures and the resulting average value as a function of the number of video sources, MV .
averaged over all the video sources.
Fig. 9. P LRV comparison between FLBMA, PRADOS and DSA++ as a function of the number of video sources, MV .
Fig. 10. P LRV values experienced by three different video sources as a function of time for both FLBMA (solid lines) and this scheme without fuzzy policer (dashed lines) with MV = 15 video sources.
that has been implemented in the FLBMA technique. In the literature, P LRV is typically evaluated as a mean of the P LRV values experienced by the different sources, without any attention to the fluctuations of P LRV from one source to another. This is the reason why Fig. 10 compares the P LRV behavior (as a function of time) experienced by three different video sources (for MV = 15) with both FLBMA (solid curves with square markers) and a simplified version of this scheme (dashed curves with circular markers) without the fuzzy video policer, but where the excess of urgent packets in each frame is cyclically divided among all the video sources. The video model is that in [10] and Bc = 10 Mbit/s. For obtaining the results shown in Fig. 10 for both the previous schemes, we have used the same video traffic sequences. From Fig. 10 we note that all the FLBMA curves are close each other. Whereas, this is not true for the simplified protocol without fuzzy policer. In order to quantify these differences, we introduce the fairness parameter ϕ defined as [18]: v u MV uX (P LRV i − P LRV )2 ϕ=t . (13) MV i=1 where P LRV i denotes the mean packet loss rate of the ith video source and P LRV represents the packet loss rate
On the basis of (13) and considering the results in Fig. 10, we have obtained that ϕ is equal to 2×10−5 and to 8×10−3 , respectively for FBLMA and the simplified scheme. Hence, FLBMA fairly regulates the access of different sources. This is an interesting result for future BWASs. Let us now consider the FLBMA results for the video traffic model shown in [11] with Bc = 20 Mbit/s. In Fig. 11 we show P LRV (mean value between I and P pictures), the PLR value of I-pictures, P LRV −I , and the PLR value of P-pictures, P LRV −P , as functions of the number of video sources per cell, MV . These results highlight that the prioritization of I-pictures with respect to P-pictures operated by the fuzzy video policer allows that P LRV −I is much lower than P LRV −P , a desirable feature to guarantee a better QoS for the most important pictures in the GoP. From Fig. 11 we have that FLBMA is able to manage up to 9 video sources per cell (with P LRV −I ≤ 10−4 and P LRV −P ≤ 10−4 ); in this case, the video throughput ηV is about equal to 52%. The remaining resources can be used to support Web traffics. We have also carried out simulations to measure the mean P LRV value as a function of the number of Web sources, MW , for MV = 7 video sources with the model in [11] and Bc = 20 Mbit/s. We have obtained that P LRV (≈ 1.5 × 10−5 ) is insensitive to the increase in MW ; this is an interesting feature of our FLBMA technique. Finally, Fig. 12 shows the histograms for the datagram transmission delay for MW = 10 Web sources with Bc = 20 Mbit/s and the video traffic model shown in [11] in two cases: MV = 7 and MV = 11 video sources. These results highlight that there are significant tails in the datagram delay distributions, thus reflecting the characteristics of the datagram length. Of course, higher datagram delays are more probable for MV = 11 than for MV = 7. In fact, the 95-percentile datagram transfer delay, DW 95 , is 120 ms and 300 ms, respectively for MV = 7 and MV = 11. VI. Conclusions Future BWASs will support different traffic classes, guaranteeing high capacity, high utilization of resources and the fulfillment of contractual QoS levels. We have proposed the new FLBMA protocol, an RRM scheme that achieves the following results: (i ) better performance than other techniques previously appeared in the literature; (ii ) man-
SSGRR - 2002W, JANUARY 21-27, 2002
10
action to be operated on the system) on the basis of the output MF µC (c) according to the center of mass method: R cµC (c)dc cpar = RY . (14) µ (c)dc Y C
Acknowledgments The authors would like to acknowledge Ing. Gianluca Nistic`o for his comments and support.
References Fig. 12. Histogram of the datagram transmission delay and related cumulative distribution function for MW = 10 Web sources in two cases: MV = 7 and MV = 11 video sources.
agement of different priorities among video traffic packets accounting for the video coding process and the QoS experienced by the video sources; (iii ) video traffic QoS insensitive to the Web traffic load; (iv ) fair sharing of slots among video traffic sources. On the basis of these characteristics, the FLBMA scheme can be considered as an interesting approach for future BWASs.
Appendix: The Fuzzy Logic Controller While in the classic logic, an element belongs or not to a set, fuzzy logic uses an MF function µA (x) that measures the membership degree of x to the fuzzy set A [4],[5],[6]. Function µA (x) can have different shapes, including Z-type, Λ-type (triangular), Π-type (trapezoidal) and S-type. Without loss of generality, we consider a single-inputsingle-output Mamdani’s FLC. The input UoD of the FLC, X, is related to the status of the controlled system; the output UoD, Y, is related to all the possible values of the output control variable of the FLC. The fuzzyfication is a process according to which the input and the output UoDs are “divided” among different fuzzy sets (and related MFs). The fuzzy rules (in the simplest case) have the following form: “IF x is A THEN y is B”, where x is an input parameter (x ∈ X), A is an input fuzzy set (A ⊂ X) with MF µA (x), B is an output fuzzy set (B ⊂ Y) with MF µB (y) and y belongs to the output UoD (y ∈ Y). In this paper we adopt the max-min inference method, summarized as follows. Let us assume that the input to the FLC is the crisp value x = x∗ . Then, we evaluate the output fuzzy set (i.e., the related MF) corresponding to each fuzzy rule with the input value x∗ , by relating the IF-part to the THEN-part through the fuzzy implication operator (i.e., A → B): µA→B (y) = min[µA (x∗ ) , µB (y)], ∀ y ∈ Y. Then, we aggregate the output MFs of the fuzzy rules by taking the maximum (composition of fuzzy rules). Thus, we obtain the output MF µC (c), c ∈ Y. Finally, the defuzzyfication process provides a crisp output value cpar (i.e., the control
[1] S. Ohmori, Y. Y. Yamao, N. Nakajima, “The Future Generations of Mobile Communications Based on Broadband Access Methods,” Wireless Personal Communications - Kluwer Academic Publ., Vol. 17, No. 2-3, pp. 175-190, 2001. [2] N. Passas, L. Merakos, D. Skyrianoglou, F. Bauchot, S. Decrauzat, “MAC Protocol and Traffic Scheduling for Wireless ATM Networks,” Mobile Networks and Applications, pp. 275-292, 1998. [3] A. S. Tanenbaum. Computer Networks. Prentice-Hall International, Inc., New Jersey, 1996. [4] Chuen Chien Lee, “Fuzzy Logic in Control Systems: Fuzzy Logic Controller - part I,” IEEE Trans. on Syst., MAN and Cybernetics, Vol. 20, No. 2, pp. 404-418, March/April 1990. [5] Chuen Chien Lee, “Fuzzy Logic in Control Systems: Fuzzy Logic Controller, part II,” IEEE Trans. on Syst., MAN and Cybernetics, Vol. 20, No. 2, pp. 419-435, March/April 1990. [6] Mohammad Jamshidi, Nader Vadiee, Timothy J. Ross. Fuzzy Logic and Control. Prentice Hal, Englewood Cliffs, New Jersey, 1993. [7] K. Dimyati, Y. T. Chin, “Policing Mechanism and Cell Loss Priority Control on Voice Cells in ATM Networks Using Fuzzy Logic,” IEEE Proc.-Comm., Vol. 147, No. 4, August 2000. [8] A. Kramling, G. Seidel, M. Radimirsch and W. Detlefsen, “Perfomance Evaluation of MAC Schemes for Wireless ATM Systems with Centralised Control Considering Processing Delays,” Proc. of The Second European Personal Mobile Comm. Conf. (EPMCC’97), pp. 173-180, Bonn, Germany, September 1997. [9] Web sites with address: http://www.etsi.org/bran and http://www.arib.or.jp/mmac/what.com. [10] C. Blondia, O. Casals, “Performance Analysis of Statistical Multiplexing of VBR Sources,” Proc. of INFOCOM’92, pp. 828-838, 1992. [11] Byeong-hee Roh, Hee-june Ahn, Jae-kyoon Kim, “Connection Admission Control with Picture-type Dependent Effective Bandwidths for VBR MPEG Video Traffic ATM Networks,” Electronics Letters, Vol. 33, No. 23, pp. 165-166, November 1997. [12] “WAND design requirements”, CEC Deliverable, n. 1D3, available at Web address: http://www.tik.ee.ethz.ch/ wand. [13] Byeong-hee Roh, Jae-kyoon Kim, “An Efficient Traffic Control Framework for VBR MPEG Video Sources in ATM Networks,” Proc. of IEEE ICC 1997, pp. 518-522, Montreal 1997. [14] San-Qi Li, Hong-Dah Sheng, “Discrete Queueing Analysis of Multi-media Traffic with Diversity of Correlation and Burstiness Properties,” Proc. of INFOCOM’91, pp. 368-381, 1991. [15] A. E. Brand, A. H. Aghvami, “Multidimensional PRMA with Prioritized Bayesian Broadcast - A MAC Strategy for Multiservice Traffic over UMTS,” IEEE Trans. Veh. Tech., Vol. 47, No. 4, pp. 1148-1161, November 1998. [16] P. Salama, N. B. Shroff, E. J. Delp, “Error Concealment in MPEG Video Streams Over ATM Networks,” IEEE Journal Sel. Areas Comm., Vol. 18, No. 6, pp. 1129-1144, June 2000. [17] L. Kleinrock. Queuing Systems. J. Wiley & Sons, N.Y.,1976. [18] W. F. Poon, K. T. Lo, J. Feng, “Scheduling Policy for Multicast video-on-demand System,” Electronics Letters, Vol. 37, No. 2, pp. 138-140, January 2001.