International Journal of Wi reless Inform ation Networks, Vol. 4, No. 3, 1997
`
`A Bandwidth Reservation Multiple Access Protocol for
`W i reless ATM Local Networks
`
`Z. Zhang, 1 I. Habib,1 and T. Saadawi1
`
`A bandwidth reservation multiple access scheme (BRMA) is proposed to resolve contention and
`assign bandwidth among multiple users trying to gain access to a common channel such as in mobile
`users contending for resources in an ATM-based cellular network or a wireless local area network
`(LAN) with short propagation delays. The protocol is best suited to support variable-bit-rate (VBR)
`traf® c that exhibits high temporal ¯ uctuations. Each mobile user is connected end-to-end to another
`user over virtual channels via the base station that is connected to the wired ATM B-ISDN network.
`The channel capacity is modeled as a time frame with a ® xed duration. Each frame starts with
`minislots, to resolve contention and reserve bandwidth, followed by data-transm ission slots. Every
`contending user places a request for data slots in one of the minislots. If the request is granted
`by the base station through a downlink broadcast channel, the user then starts transmissio n in the
`assigned slot(s). The number of assigned slots varies according to the required quality of service
`(QoS), such as delay and packet loss probability. A speech activity detector is utilized in order to
`indicate the talkspurts to avoid wasting bandwidth. Due to its asynchronous nature, BRMA is rather
`insensitive to the burstiness of the traf® c. Since the assignment of the minislots is deterministic, the
`request channels are contention-free and the data channels are collision-free. Hence, in spite of the
`overhead (minislots) in each frame, BRMA provides higher throughput than Packet Reservation
`Multiple Access (PRMA) for the same QoS, especially for high-speed systems. A better delay
`performance is also achieved for data traf® c compared to Slotted Aloha reservation-type protocol
`PRMA. In addition, BRMA performs better in terms of bandwidth ef® ciency than the conventional
`TDMA or the Dynamic TDMA, where speech activity detectors are very dif® cult to implement.
`
`KEY W ORD S: WATM LANs; wireless access; dynamic channel assignment; TDMA.
`
`1. INTRODUCTION
`
`Wireless communications make it possible for users
`to access the advanced information services that include
`multimedia applications from virtually anywhere and at
`any time. The connection-oriented Asynchronous Trans-
`fer Mode (ATM ), a well-accepted concept in wired com-
`munications, has also established its position in wireless
`networks. The combination of these, i.e., the Wireless
`
`1Department of Electrical Engineering, City University of New
`York, City College, New York, New York; e-mail: {zzhang, eeiwh,
`eetns}@ee -mail.en gr.ccny.cuny.edu.
`
`ATM (WATM), has been one of the hottest topics in
`communications in the 19 90s.
`In a wireless system,
`the performance depends
`
`largely on the media access control (MAC) protocol. A
`
`MAC protocol of WATM should support ATM traf® c
`
`classes such as available bit rate (ABR), variable bit rate
`
`(VBR), constant bit rate (CBR), and unspeci® ed bit rate
`
`(UBR) while maintaining a high wireless channel uti-
`
`lization. This ® eld has been very active and many proto-
`
`cols have been proposed and studied [1± 7]. For example,
`
`D. Petras proposed a Dynamic Slot Assignment (DSA)
`
`protocol for Mobile Broadband Systems (MBS), which
`
`aims to be a mobile extension of an ATM -based network
`
`147
`
`1068-9605/ 97/ 0700-0147$12.50/ 0 Ó
`
`1997 Plenum Publishing Corporation
`
`IPR2020-00038
`MM EX1012, Page 1
`
`

`

`148
`
`Zhang, Habib, and Saadawi
`
`like B-ISDN. In DSA the distributed queueing informa-
`tion from each mobile station is included in the uplink
`data packets to help the base station to determine if addi-
`tional slots should be assigned to the mobile station [1].
`This protocol was evaluated in Ref. 2 and enhanced to
`DSA++ in Ref. 3. In recent years, there have already
`been some standardization activities to determine the
`MAC of wireless ATM LANs, such as Europe’s Mobile
`Broadband Systems (MBS) [8] and ETSI HIPERLAN
`MAC [9].
`TDMA technology has been well understood and is
`now widely used in many wireless networks, including
`the current European global system of mobile telecom-
`munications (GSM) [ 10± 14] . Originally designed for
`the circuit switching networks, most TDMA versions,
`including the multiservice dynamic reservation (MDR)
`TDMA scheme studied in Ref. 15, do not utilize
`the wireless bandwidth as ef® ciently as the wideband
`CDMA, especially under bursty traf® c conditions such
`as voice communications. One reason is that in these
`protocols, the exploitation of the speech activity factor
`for voice communication is very dif® cult [15] .
`To ef® ciently utilize the bandwidth, PRMA, a Slot-
`ted Aloha reservation type of TDMA, was proposed by
`Goodman et al.
`[16] and has been widely studied by
`many others [17± 21]. Unlike Slotted Aloha, contentions
`for a time slot in PRMA occur only at the beginning of
`each talkspurt of the conversation and unlike traditional
`TDMA, PRMA allows a voice user to reserve a slot only
`during each talkspurt rather than during the whole con-
`versation. For voice communications where the average
`talkspurt is on the order of 1 s, the utilization of the
`channel can reach 0.68 [ 17], higher than that of tradi-
`tional TDMA. Mitrou et al. [ 22] proposed and studied
`an improved version of PRMA in which a minimum por-
`tion of the available channel capacity is dedicated to the
`reservation channel. Slotted Aloha contentions occur in
`some slots that are further divided into minislots. As a
`result, the throughput performance under high load con-
`ditions is improved. We observe, however, that as the
`average length of talkspurt of the conversation decreases,
`the performance of this class of Slotted Aloha/ TDMA
`reservation protocols degrades due to more frequent col-
`lisions at the beginning of each talkspurt. In the extreme
`case, when the user transmits one packet each spurt, the
`above protocols perform just like Slotted Aloha. There-
`fore PRMA described in Refs. 16 and 17, though good
`for slow time-varying and long-burst traf® c such as voice
`traf® c, is not suitable for highly time-varying traf® c such
`as that encountered in ATM networks.
`
`Motivated by the highly bursty nature of the mul-
`timedia traf® c encountered in ATM networks and the
`requirements that the network must deliver different
`quality of services (QoS) for different types of traf® c,
`we propose a contention-free MAC protocol, referred
`to as Bandwidth Reservation Multiple Access Protocol
`(BRMA), that meets the needs to allocate and control
`the wireless channel bandwidth. It is designed to achieve
`two main goals:
`
`transmissions by
`contention-free
`1. To ensure
`avoiding collisions and retransmissions that are
`not suitable for high-speed real-time traf® c such
`as video or voice.
`2. To reserve bandwidth for each type of traf® c in
`order to maintain QoS requirements. For exam-
`ple, video or voice traf® c requires stringent delay
`requirements and would have priority over data
`traf® c. Hence, the protocol must be capable of
`allocating different amounts of bandwidth to dif-
`ferent types of traf® c.
`
`To achieve the ® rst goal, we implemented a frame
`that is divided into time slots. Attached to each frame
`is an overhead made of minislots. Users contending for
`an amount of bandwidth send their requests to the base
`station via those minislots. If the bandwidth is availab le,
`then the request is honored and an average number of
`slots is assigned to the user every frame such that the
`QoS is met.
`To achieve the second goal, we incorporate a band-
`width allocation algorithm into the base station. Simply
`stated, the algorithm ® rst reads the requested QoS from
`the request packet at the time of the call establishment.
`It then calculates the required bandwidth and, hence, the
`number of slots per frame. If those slots are availab le,
`the call is then accepted; otherwise it is rejected. The
`advantages of incorporating this admission control pol-
`icy are several: First, it harmonizes the protocol func-
`tionality with that of the ATM. Second, it avoids long-
`term congestion episodes due to overloading of the net-
`work’s resources by avoiding admitting calls for which
`no suf® cient resources are available. Hence, excessive
`packet loss due to prolonged delays or buffer overload-
`ing are minimized.
`The rest of this paper is arranged as follows. Sec-
`tion 2 describes the system overview and BRMA pro-
`tocol details. Performance analysis is given in Sec-
`tion 3, and simulation and numerical results are pro-
`vided in Section 4. Finally, the conclusions are given in
`Section 5.
`
`IPR2020-00038
`MM EX1012, Page 2
`
`

`

`BRMA for Wi reless ATM LANs
`
`149
`
`2. SYSTEM AND PROTOCOL DESCRIPTION
`
`In wireless TDMA schemes, time is usually divided
`into frames and slots. A guard time is needed between
`two consecutive slots or frames to accommodate the
`effect of the propagation delays [14, 15]. Partially for
`this reason, in a high-speed wireless LAN where TDMA
`is used, the propagation delay should be very small if
`high utilization is to be achieved. In other words, most
`high-speed wireless LANs are usually designed to cover
`small areas called microcells or even picocells. In fact,
`in some applications the con® nement of the signal to a
`small area is a desirable feature for wireless LANs [23] .
`In LANs that cover such small areas, practical propa-
`gation delay is on the order of a few microseconds and
`has no effect on the protocol performance. BRMA is a
`wireless protocol for such purposes.
`the
`Figure 1 shows a possible architecture of
`WATM LAN. Each end-to-end connection between two
`mobile stations is assigned a virtual channel. Multiple
`virtual channels may exist between two end stations. The
`base station acts as a central controller in the WATM
`LAN and a bridge to the B-ISDN network via a base sta-
`tion controller (BSC). The users of the WATM terminals
`request the same functionality and QoS as users of wired
`terminals. The QoS requirements include average and
`maximum cell rates, average and maximum cell delays,
`cell loss probability, handover and call teardown rates,
`etc. In this paper, for simplicity, we limit our discus-
`sion of QoS to only cell loss probability and cell delay
`where we evaluate the performance of BRM A within one
`microcell area.
`The call setup is established in a separate out-of-band
`signaling channel. A mobile station requesting connection
`sends its traf® c characteristic parameters and QoS require-
`ments to the base station. The admission control scheme
`sitting at the base station will evaluate whether there is
`enough bandwidth available to support the requested con-
`nection with QoS. A virtual channel will be assigned to
`the connection with a minimum and an average bandwidth
`in slots/ frame if such bandwidth is available. Otherwise
`the call is rejected. Examples of such admission schemes
`are provided in Refs. 24 and 25. Obviously, upper layer
`protocols (e.g., IP) must include the provisions for mobil-
`ity support, since mobile stations may change their loca-
`tions dynamically. Issues such as handover control and
`routings, among others, have been addressed by propos-
`als such as Dynamic Host Con® guration Protocol (DHCP)
`[ 26] and are beyond the scope of this paper.
`
`Fig. 1. Typical wired/ wireless network connectivi ty.
`
`Each mobile station utilizes its share of the uplink
`channel according to the frame-level dynamic assign-
`ment by the central base station. Users share the channel
`bandwidth via a time frame that is further divided into
`K smaller data slots. The duration of each slot equals
`one packet transmission time. Attached to each frame are
`N minislots that are deterministically assigned to the N
`mobile stations that have already established their con-
`nections to request data slots in each frame. This num-
`ber N is dynamically updated when a virtual channel is
`added or deleted due to new call admissions or call com-
`pletions. At the beginning of each frame, each station
`sends a minipacket in its assigned minislot. The mini-
`packet includes information such as the call ID and the
`number of data slots this call requests in this frame. At
`the end of the minislots the base station knows the total
`number of required slots for all stations in this frame,
`and immediately broadcasts the data slot assignments of
`the current frame. Each mobile station then transmits its
`data packets in its assigned data slot(s); see Fig. 2.
`The data slot assignments depend not only on the
`preassigned bandwidth, but also on the traf® c conditions.
`If the total requested data slots exceeds the available data
`slots in a frame, each mobile station will get at least its
`minimum number of slots in this frame. Packets that are
`not transmitted in this frame will have to wait in the
`user’ s own buffer and be transmitted in the following
`frame(s). Hence, the user will request slots for both new
`and old packets waiting in its buffer. When the system
`
`IPR2020-00038
`MM EX1012, Page 3
`
`

`

`150
`
`Zhang, Habib, and Saadawi
`
`tion channel by the base station. Note that in PRMA a
`channel is subject to possible packet collisions unless a
`reservation is made already. In PRMA, multiplexing for
`voice packets occur at talkspurt level. The duration of the
`frame is equal to the interarrival time of the voice pack-
`ets, and at most one data slot is assigned to each voice
`user every frame. For BRM A, multiplexing occurs at the
`frame level and the frame length does not have to be the
`interarrival time of voice packets. One user may have
`multiple data slots in a frame. Of course, BRM A cannot
`be used to replace PRMAÐ
`they suit different systems.
`For example, PRMA will generate smaller packet delays
`for voice traf® c when the system load is light.
`BRM A is also different from a collision-free pro-
`tocol called the bit-map method discussed in Ref. 28.
`Although the bit-map method also uses similar mini-
`slots and access frames, it is basically a protocol of dis-
`tributed control. Therefore, it does not have the potential
`to perform the functions of priority, guaranteeing differ-
`ent QoS and bandwidth allocation. Conversely, BRMA
`can perform all these functions because it is basically a
`protocol of central control. In Bit-Map, a user declares
`its request in minislot, then goes ahead and uses the data
`slots. In BRM A, a user is allocated data slots according
`to the base station’s assignment.
`BRM A is different from the dynamic TDMA in
`several aspects and functionality. First, in the dynamic
`TDMA [15] , voice activity detectors are dif® cult to
`implement; it assigns slots to voice users based on a
`ª circuit mode.º Second, in dynamic TDMA each voice
`user gets at most one data slot in each frame and frame
`length must therefore be the interarrival time of voice
`packets ( just like in PRMA). However, BRMA, as pre-
`viously indicated, assigns slots in a ª statistical multi-
`plexingº mode in the sense that every user gets a variable
`number of slots every frame.
`
`3. PROTOCOL AN ALY SIS
`
`Exact modeling of the multimedia traf® c is dif® cult
`since it involves the characterization of complex nonre-
`newal processes such as the one generated by variable-
`bit-rate (VBR) compressed video sources. In our study,
`we ® rst consider voice traf® c sources, and then the super-
`position of voice and data traf® c sources. To compare
`with PRMA, we use the same non-ATM voice packet
`and similar channel parameters as those used in the
`PRMA performance study [17]. We then show that, for
`ATM-based voice packets, the protocol works similarly.
`
`Fig. 2. Frame structure and an example of scheduling of packets in
`BRM A protocol.
`
`is temporarily overloaded, this scenario may result in
`packet loss if the packets are delay-sensitive. However,
`with proper admission control and bandwidth allocation,
`packet loss will be bounded by a maximum value.
`The above assignment procedure is repeated every
`frame. Hence the slot assignment is dynamic at the frame
`level. When voice communication is the main traf® c, this
`protocol can accommodate the activity factor detector
`naturally. This is a big advan tage over conventional ver-
`sions of TDMA, which have to assign bandwidth to the
`silent portion of each conversation.
`Under the control of BRM A, no two or more mobile
`stations in the same microcell will attempt to access the
`wireless channel at the same time. No packet collisions
`are possible; therefore the typical hidden terminal prob-
`lem does not exist here.
`Most functions of the ATM layer of the BISDN
`ATM reference model [27] are performed at the base
`station (e.g., (de)multiplexing, cell header addition and
`extraction, ¯ ow control, etc.) Therefore the base station
`contains an ATM header table for each admitted call.
`This table is updated dynamically. Packets directed from
`the wireless LAN through the base station to the ATM
`backbone network are therefore ATM cells.
`BRMA is different from PRMA mainly in fol-
`lowing aspects: In BRM A, the reservation channel is
`contention-free because each minislot is dedicated to
`each user. Also, the data channel is collision-free because
`the slot assignments are resolved during the reserva-
`
`IPR2020-00038
`MM EX1012, Page 4
`
`

`

`BRMA for Wi reless ATM LANs
`
`151
`
`We observe the arrival process from N homoge-
`neous voice sources at the beginning of each frame. This
`process can be characterized by a discrete-time Markov
`chain of dimension N + 1, where its state is de® ned
`by the number of conversations is talkspurt x. In many
`published papers [e.g., 29, 30] in which similar analyses
`were performed, the frame length was chosen to be the
`packet interarrival time tp . In our study, this case is not
`applicable since the frame length is different from the
`packet interarrival time.
`We use P(x1, x2 ) to represent the probability that at
`the beginning of the (n + 1)th frame there will be x1
`sources in a talkspurt given that at the beginning of the
`nth frame there are x2 sources in a talkspurt in the sys-
`tem.
`
`Let PA/ S be the transitional probability that a source
`will switch from talkspurt phase to silent phase during
`a single frame, and PS/ A be the transitional probabil-
`ity that a source switches from silent phase to talkspurt
`phase during the same time period. Noticing that both
`talkspurt and silent periods are exponentially distributed
`with means TA and TS, respectively, we have
`
`PA/ S
`PS/ A
`
`1
`
`1
`
`e Lf / TA
`e Lf / TS
`
`(3)
`
`Now we try to obtain an expression for P(x1, x2 ).
`Two cases arise:
`
`1. For x1 ‡ x2 , for the number of sources in a talk-
`spurt in the system to change from x2 to x1 , there must
`be exactly k sources in a talkspurt changing to silent and
`x2 + k silent sources changing to a talkspurt
`exactly x1
`in one frame, where k
`0, 1, 2, . . . , min(x2 , N x1 ).
`Hence we have
`
`P(x1, x2 )
`
`min(x2 , N x1 )
`
`1 x2
`
`k
`
`2 P k
`A/ S(1 PA/ S)x2
`
`k
`
`´ 1
`
`k 0
`
`N x2
`x2 + k
`
`x1
`
`2´ P x1
`
`S/ A
`
`x2 + k
`
`(1 PS/ A)N x1
`
`k
`
`(4)
`
`2. Similarly for x1 < x2 w e have
`
`We assume that a voice packet has v bits of payload,
`and that each packet has a header of h bits. Each mini-
`slot contains hm bits. Each voice source generates voice
`packets at the peak rate of Rp kbps during the talkspurts
`and no packets during silent periods. Both talkspurts and
`silent period are exponentially distributed with means of
`TA ms and TS ms, respectively. During talkspurts, voice
`packets arrive every tp ms and there are N stations con-
`nected through the base station. If the voice packets are
`not transmitted within D ms, they will be dropped. A sat-
`isfactory QoS here indicates a packet loss rate of under
`1%. Intuitively, very long frames will lead to excessive
`packet loss due to prolonged delays, thus limiting the
`number of stations that can be supported. On the other
`hand, very short frames may cause the total throughput
`to degrade due to excessive frame overhead. The opti-
`mal number of data slots in a frame is the one that can
`maximize the throughput and guarantee QoS for a cer-
`tain number of users.
`In the following analysis, we ® rst consider N homo-
`geneous voice sources connected to the base station over
`the wireless link in a single microcell. Each source gen-
`erates voice traf® c following an ON/ OFF model. We
`analyze the queue and obtain the average packet loss rate
`and average packet waiting time for different values of
`K . Second, we consider N 1 homogeneous voice users
`and one data user. We analyze the queue and obtain sim-
`ilar measurements.
`
`3.1. Queueing Analysis for Voice Traf® c Only
`
`Designating d as the data slot length, Lf as the
`length of a frame in ms, we have
`
`N ´ hm
`C
`
`Lf K ´ d +
`(h + v)/ C
`
`d
`
`(1)
`
`In order to simplify the analysis, we express the
`maximum delay limit in terms of a ® nite-size buffer.
`Considering that each buffer space is equivalent to a
`waiting time of one data slot d , and that each frame
`K ´
`d ) ms and that
`contains a minislot header of (Lf
`there are D/ Lf frames in time D, we obtain the equiva-
`lent buffer size limit B:
`
`(2)
`
`(Lf K ´ d )2 @
`
`dû
`
`D L
`
`f
`
`B ë 1 D
`
`IPR2020-00038
`MM EX1012, Page 5
`
`´
`å
`

`

`152
`
`Zhang, Habib, and Saadawi
`
`x2
`x1 + k
`
`x2
`
`A/ S
`
`2 P x2
`k1 N x2
`
`k
`
`x1 + k
`
`(5)
`
`min(x1 , N x2 )
`
`P(x1, x2 )
`
`k 0
`
`(1 PA/ S)x1
`
`2´ P k
`
`S/ A(1 PS/ A)N x2
`
`k
`
`For the N-state discrete-time Markov arrival pro-
`cess, we designate P(A/ x) as the conditional probability
`that there are exactly A packet arrivals during a frame,
`given that at the beginning of the frame there were x
`voice sources in the talkspurt. During time Lf , a source
`generates either q (q ë Lf / tpû ) or q + 1 packets with
`tp ´ q )/ tp and probability 1
`probability (L
`(L
`tp
`´ q )/ tp , respectively. For x sources in a talkspurt, we
`have
`
`Fig. 3. Two-state M arkov chain of the voice queueing model.
`
`P(A| x)
`
`ìíî 1
`
`0
`
`2 1 Lf
`
`x
`A q x
`
`tp q
`
`tp
`
`2 A q x1 1
`
`Lf
`
`tp q
`
`tp
`
`x (A q x)
`
`0 £ A q x £ x
`
`otherwise
`
`(6)
`
`is an exact integer mul-
`When the frame length Lf
`Lf/ tp , each source in a talkspurt will
`tiple of tp , i.e., q
`generate q packets during the frame. Therefore P(A/ x)
`is exactly
`
`P(A| x) { 1
`
`0
`
`A x ´ q
`otherwise
`
`total number of voice sources that are in a talkspurt at
`the beginning of the frame. It follows that the queueing
`process evolves from the nth frame to the (n +1)th frame
`according to
`
`(7)
`
`q n + 1 min[(qn K)+ + An, B]
`
`(8)
`
`Now, w e consider the queueing model. As in
`Refs. 29 and 30, the system observed at time units of
`is characterized by a two-dimensional discrete-time
`Lf
`Markov chain process (see Fig. 3). The state of this chain
`is de® ned by (q, x), where q is the total number of pack-
`ets in the queue at the beginning of a frame, and x is the
`
`where (.)+ denotes the larger of its content or 0, and An
`is the number of packets arriving during the nth frame.
`For
`the
`above
`two-dimensional discrete-time
`(q1, x1/ q 2, x2 ) be the transitional
`let a
`Markov chain,
`probability that the next state will be (q 1, x1 ), given that
`the present state is (q 2, x2 ).
`For B £ K :
`
`(q1, x1 | q 2, x2 )
`
`P(x1, x2 ) ´ P(q 1 | x2 ),
`¥å
`P(x1, x2 ) ´ P(A| x2 ),
`
`A B
`
`0 £ q1 < B
`q 1 B
`
`For B > K : If 0 £ q 1 < B K ,
`
`(q 1, x1 | q2, x2 ) { P(x1, x2 ) ´ P(q 1 | x2 ),
`
`P(x1, x2 ) ´ P(q 1 + K q2 | x2 ),
`0,
`
`0 £ q2 < K
`K £ q2 £ q1 + K
`q 1 + K < q2 £ B
`
`(9)
`
`(10)
`
`IPR2020-00038
`MM EX1012, Page 6
`
`å
`1
`´
`2
`a
`ìíî
`a
`

`

`BRMA for Wi reless ATM LANs
`
`If B K £ q 1 < B,
`
`(q 1, x1 | q2, x2) { P(x1, x2 ) ´ P(q1 | x2 )
`
`P(x1, x2 ) ´ P(q1 + K q 2 | x2),
`
`0 £ q 2 < K
`K £ q2 £ B
`
`If q1
`
`B,
`
`P(x1, x2 )
`
`¥å
`
`(q 1, x1 | q2, x2 )
`
`P(x1, x2 )
`
`A B
`
`P(A| x2 ),
`¥å
`
`P(A| x2 ),
`
`0 £ q2 < K
`K £ q2 £ B
`
`153
`
`(11)
`
`(12)
`
`A B + K q2
`
`Equations (9)± (11) assume that the system is mem-
`Lf / tp . However,
`oryless. This is accurate only when q
`for q < Lf/ tp , these equations are only approximations.
`(q, x) satis® es
`The steady-state probability p
`
`(q, x)
`
`Nå
`
`Bå
`
`x2
`
`0
`
`q2
`
`0
`
`(q2, x2 )a
`
`(q, x| q 2, x2 )
`
`(13)
`
`where the boundary condition is
`
`where A is the average number of packet arrivals in a
`frame and is given by
`
`A
`
`N ´ TA ´ Lf
`(TS + TA) ´
`tp
`
`(17)
`
`It is simple to see that the average queue length q
`at the beginning of each frame is then
`
`Nå
`
`Bå
`
`x 0
`
`q
`
`0
`
`(q, x)
`
`1
`
`(14)
`
`q B
`
`Nå
`
`q
`
`x 0
`
`q
`
`0
`
`(q, x) ´ q
`
`(18)
`
`The above equations can be solved using matrix-
`(q, x).
`geometric techniques [31] to obtain p
`To compute the probability of packet loss, we have,
`for B > K
`
`To obtain the average packet delay, we have to com-
`pute the average queue length Q during the frame as fol-
`lows.
`
`PLoss
`
`Nå
`
`Kå
`
`¥å
`
`x 0
`
`q 0
`
`A B + 1
`
`(q, x)P(A| x)(A B)
`
`Nå
`
`+
`
`Bå
`
`¥å
`
`x 0
`
`q K + 1
`
`A B + K q
`
`whereas for B £ k
`
`PLoss
`
`Nå
`
`Kå
`
`¥å
`
`x 0
`
`q 0
`
`A B + 1
`
`(q, x)P(A| x)(A B)2 @ A
`
`(16)
`
`(q, x)P(A| x)(q K + A B)2 @ A
`
`(15)
`
`For K £ q + 1, the average queue lengths at the 0th,
`1 + A/ K ,
`1st, 2nd, . . . , (K 1)th data slots are q, q
`1) ´ A/ K ,
`2 + 2 ´ A/ K , . . . , q
`(K
`1) + (K
`q
`
`IPR2020-00038
`MM EX1012, Page 7
`
`a
`a
`ìïïïíïïïî
`p
`p
`p
`å
`p
`1
`p
`p
`1
`p
`

`

`154
`
`Zhang, Habib, and Saadawi
`
`respectively. Averaging the above values, we have
`
`q + q
`
`1 + A/ K + q
`
`Q
`
`2 + 2 ´ A/ K + ´ ´ ´ + q
`K
`
`(K 1) + (K 1) ´ A/ K
`
`2q + [(K 1)/ K ] ´ A K + 1
`2K
`
`For K > q + 1, we similarly have
`
`(2q
`
`Q
`
`ë qû + ë qû ´ A/ K)( ë qû + 1) + ( ë qû ´ A/ K + A)(K ë qû
`2K
`
`1)
`
`(19)
`
`(20)
`
`Noticing that only (1 PLoss) ´ A of the arrival pack-
`ets contributes to queueing delay per frame, we apply
`Little’s formula [32] to obtain the average voice packet
`waiting time and obtain
`
`Wv
`
`Q ´ Lf
`(1 PLoss) ´ A
`
`d
`
`(21)
`
`3.2. Queueing Analysis for Voice and Data Traf ® c
`
`Now w e consider the superposition of data and
`voice traf® c. Since the voice packets have higher pri-
`ority than the data packets, their queueing performance
`is independent of the data traf® c. Data packets are not
`subject to packet loss. They are simply delayed for a
`longer time when bandwidth is not currently availab le.
`Therefore, we can use the method introduced previously
`to calculate the voice-packet loss rate and average voice
`packet delay without considering the data traf® c at all.
`Assuming that the packet loss rate for the voice packet
`is negligibly low (much less than 1%), we can use an
`in® nite buffer model to analyze average packet delay of
`the superposition of voice and data traf® c. Finally, the
`average delay of the data packets can be calculated. This
`independent treatment in the protocol performance anal-
`ysis for the voice traf® c is quite like the approach used
`by Wieselthier and Ephremides [33].
`The previous approach, which uses an N-state
`discrete-time Markov chain to model the arrival process,
`is entirely intractable when the system buffer size B is
`not very large. When an in® nite (or very large) buffer
`system is considered, the approach becomes infeasible
`due to the excessive requirement of computer memory
`needed for the calculation. In order to facilitate our cal-
`culation, we use a two-state discrete-time Markov mod-
`
`ulated Poisson process (MMPP) to model the superposi-
`tion of voice and data arrivals.
`The Markov modulated Poisson process was used in
`Refs. 34 and 35 to model superposition of voice packet
`arrivals by matching traf® c characteristics such as the
`mean packet arrival rate, the variance-to-mean ratio of
`the number of arrivals, the long-term variance-to-mean
`ratio of the number of arrivals, and the third moment of
`the number of arrivals. Data traf® c can easily be incor-
`porated into the MMPP model because the data arrival
`process is also Poisson.
`We consider that N 1 homogeneous mobile sta-
`tions generate voice traf® c as before, and one mobile
`station generates data packets randomly one at a time.
`The interarrival time of the data packets follows an expo-
`nential distribution with mean of 1/k d . Each data packet
`has the same size as the voice packets. This considera-
`tion that all data traf® c comes from one source does not
`result in loss of generality, since the superposition of data
`traf® c from different Poisson sources is still Poisson.
`We characterize the superposition arrival process
`by a simple two-state MM PP model [34]. The MMPP
`model alternates between a high state (H) and a low state
`(L). Let the mean sojourn time of each state be tH and
`tL, respectively. Packets arrive during each state accord-
`ing to a Poisson process with mean rate of k H and k L,
`respectively. Notice that the duration of a typical frame is
`on the order of tens of milliseconds, whereas the sojourn
`times of the MM PP states are on the order of 0.5 s [34] .
`Hence, it is reasonable to assume that during a typi-
`cal frame, the MMPP model is stationary (i.e., does not
`alternate between the two states).
`Let the transitional probabilities from high to low
`and from low to high states be PH and PL, respectively.
`
`IPR2020-00038
`MM EX1012, Page 8
`
`

`

`BRMA for Wi reless ATM LANs
`
`155
`
`It follows that
`
`PH
`PL
`
`1
`
`1
`
`e Lf / tH
`e Lf / tL
`
`Solving this queueing model as we did previously,
`(q, x).
`we obtain p
`Recall that the average packet arrivals in each frame
`for voice packets is evaluated by (17), and therefore we
`have
`
`(22)
`
`and P(A/ x), the probability that there are A arrivals in a
`frame, given that the arrival state is x (x H, L), is
`
`A
`
`(N 1) ´ TA ´ Lf
`(TS + TA) ´
`tp
`
`+ k d ´ Lf
`
`(25)
`
`P(A| H)
`
`P(A| L)
`
`e k H Lf (k H ´ Lf )A
`A!
`
`e k LLf (k L ´ Lf )A
`A!
`
`where we have added the term k d Lf to accommodate the
`data packets.
`We can then ® nd the average packet delay by apply-
`ing Little’s formula:
`
`(23)
`
`where k H and k L are the respective arrival rates of the
`Markov chain.
`Recall that PLoss is evaluated using formulas (15)
`and (16). This probability is not affected by the data traf-
`® c, as indicated in Ref. 33. Lost packets should be sub-
`tracted from our MMPP arrival model because in this
`MMPP queueing analysis no packet loss is considered,
`due to the in® nite buffer size. The arrival rates k H and
`k L of the ® nal MMPP arrival model are then
`
`W
`
`Q ´ Lf
`A
`
`d
`
`(26)
`
`where Q is evaluated from Eqs. (19) and (20).
`Using Eq. (26) to evaluate W and using Eq. (21) to
`evaluate Wv , we can then obtain the average delay for
`data packets Wd as follows:
`
`Wd
`
`W Wv ´
`Rd
`
`(1 Rd )
`
`(27)
`
`k H
`k L
`
`(1 PLoss)k
`(1 PLoss)k
`
`vH + k d
`vL + k d
`
`(24)
`
`where Rd is percentage of the data traf® c in the combined
`traf® c:
`
`where k
`v H and k
`v L are the arrival rates of the Markov
`model which does not include data traf® c.
`Now w e consider the resulting two-dimensional
`discrete-time queueing process at each frame length Lf .
`Let the state of the resulting Markov chain be (q, x),
`where q is the number of packets in the queue and x
`is the number of sources in the talkspurt observed at the
`(q, x) be the steady-state
`beginning of each frame. Let p
`probability. We notice that this Markov chain is similar
`to the one solved in the previous subsection. However,
`there are two differences:
`
`1. The buffer size is in® nite. However, it can be
`approximated by a ® nite buffer with very larg e
`size B.
`2. The arrival process has only two states.
`(q 1, x1/ q 2, x2 ) expressions remain the
`While the a
`same as those presented earlier, the P(x1, x2 ) and P(A/ x)
`equations are now given by (23) and (24) instead of
`equations (4)± (7).
`
`Rd
`
`k d ´
`k H ´
`
`(tH + tL)
`tH + k L ´
`
`tL
`
`(28)
`
`4. SIMULATIO NS AND NUMERIC AL RESULTS
`
`In our simulations, voice packets arrive from N (or
`N 1 when superposition of voice and data is considered)
`sources independently. Each source generates packets
`according to an ON/ OFF model. The silent (talkspurt)
`period of each source is an exponentially distributed ran-
`dom variable with mean TS (TA). During the talkspurt
`period, a packet arrives every tp ms. Since data packets
`are generated one at a time, the interarrival time for data
`packets follows an exponential distribution with mean of
`1/k d seconds.
`Our simulations are performed with C programing.
`Each simulation consists of two parts: the arrival process
`and the service process. The arrival process is indepen-
`dent of the service process. In the arrival process, each
`source (voice or data) generates packets independently as
`
`IPR2020-00038
`MM EX1012, Page 9
`
`

`

`156
`
`Zhang, Habib, and Saadawi
`
`mentioned above. A time stamp marks the arrival time of
`each generated packet. In the service process, all events
`are observed at the end of the minislots in each frame.
`Packets, new (generated in last frame) or old (gener-
`ated more than one frame ago), are served in an ® rst-in,
`® rst-out (FIFO) order. Each packet service time is one
`slot. In other words, this is a discrete time GI/ D/ 1/ FIFO
`queueing model. A departure time stamp is marked for
`each served packet. Therefore, the waiting time for each
`packet is de® ned as (departure time
`arrival time). If
`the waiting time for a voice packet is over the delay
`limit (32 ms here), the pa