Transcript
Chapter I Queueing Delay Analysis of Multi-Radio Multi-Channel Wireless Mesh Networks Chengzhi Li University of Houston, Houston, TX 77204, USA Wei Zhao University of Macau, Macau, China ABSTRACT Wireless mesh networking is becoming an economical means to provide ubiquitous Internet connectivity. In this chapter, we study wireless communications over multi-radio and multi-channel wireless mesh networks with IEEE 802.11e based ingress access points for local clients and point-to-point wireless links over non-overlapping channels for wireless mesh network backbones. We provide a set of algorithms to analyze the performance of such wireless mesh networks with wideband fading channels in various office building and open space environments and commonly-used Regulated and Markov On-Off traffic sources. Our goal is to establish a theoretical framework to predict the probabilistic end-to-end delay bounds for real-time applications over such wireless mesh networks.
I. INTRODUCTION Wireless mesh networking is a new technology that complements infrastructure-based wired networks to provide ubiquitous Internet connectivity. Generally, wireless mesh networks (WMNs) are composed of wireless mesh routers and clients. The mesh routers with gateway/routing functions form wireless mesh backbones and provide multi-hop connectivity between clients and the Internet or between clients. Unlike nodes in traditional wireless networks such as mobile ad hoc networks (MANETs), mesh routers are static and have no power constraint and their locations can be carefully selected. The unique features and characteristics of WMNs, which distinguish WMNs from wired networks, include a) low initial investment; b) extensive coverage areas; c) ease of deployment and expansion; d) fault tolerance. With extensive research efforts on wireless mesh networking by academic and industrial communities (Akyildiz, Wang, & Wang, 2005; Bruno, Conti, Gregori, Wijting, Kneckt, & Damle, 2005; Faccin, Wijting, Kneckt, & Damle, 2006; Kyasanur, So, Chereddi, & Vaidya, 2006; Lee, Zheng, Ko, & Shrestha, 2006) as well as the commercial deployments of wireless mesh networks (WMNs) around the world, wireless mesh networking technology is becoming a vital component of our daily life. In wireless communications, wireless channels are error-prone and their capacities are physically limited. There are many factors that affect the performance of wireless channels, e.g., signal power attenuation, inter-channel and co-channel interference, thermal noise, Doppler frequency, shadowing, and multipath channel fading. Therefore, QoS provisioning for many applications, which have diverse performance requirements in terms of minimum data rate, delay/delay jitter bound, and packet loss rate over wireless networks, poses a very difficult challenge. Moreover, it has been revealed (Gupta & Kumar, 2000) that the throughput of per source-destination pair in a multihop wireless network with a single shared channel scales with the number of network nodes n as O(1/n0.5). It has also been demonstrated (Ganguly, Navda, Kim, Kashyap, Niculescu, Izmailov, Hong, & Das, 2006; Niculescu, Ganguly, Kim, & Izmailov, 2006) that the performance of VoIP applications over single channel WMNs degrades quickly as the lengths of
2 VoIP traffic routes increase. Thus, the QoS capability of multihop wireless networks with a single shared channel is very limited. With the rapid evolution of radio technologies, commercial multi-radio products have emerged in the market, e.g., BelAir Networks` BelAir200 mesh router with up to four radios and Motorola`s Motomesh node with up to four radios and Strix`s OWS mesh router with up to six radios. Moreover, there are 27 non-overlapping channels for IEEE 802.11 based wireless networks, i.e., 3 non-overlapping channels for IEEE 802.11b/g standards in 2.4 GHz frequency band and 24 non-overlapping channels with IEEE 802.11a standard in 5 GHz frequency band. These factors make it natural to consider WMNs with multiradio and multi-channel mesh routers as a feasible solution to mitigate the inherent capacity limitation of conventional single channel wireless networks for QoS provisioning. It is worth noting that the asymptotic capacity of multi-channel and multi-radio wireless mesh networks has been theoretically characterized (Kyasanur & Vaidya, 2005) and experimentally verified (Kodialam & Nandagopal, 2005). Generally, one of crucial performance metrics for QoS provisioning over multihop wireless networks is the end-to-end delay experienced by traffic flows. Following the seminal work (Gupta & Kumar, 2000), the wireless communication and networking research community has made extensive efforts to understand the throughput-delay scaling law. The results provided in (Bansal & Liu, 2003; Gamal, Mammen, Prabhakar, & Shah, 2004; Needly & Modiano, 2005; Moraes, Sadjadpour, & Garcia-LunaAceves, 2004; Moraes, Sadjadpour, & Garcia-Luna-Aceves, 2004; Lin, Sharma, Mazumdar, & Shroff, 2006; Perevalov & Blum, 2003; Perevalov & Blum, 2006) have established the asymptotic relationship between the average delay and maximum feasible throughput of per source-destination pair in wireless networks with network nodes extending to infinity. While these elegant results shed light on the deployment of wireless networks as well as the design of protocols and algorithms from a high level perspective, the asymptotic features may not match real wireless networks that usually have finite nodes. Therefore, they may not be suitable for practical WMNs. There exist two papers (Chen & Yang, 2006; Bisnik & Abouzeid, 2006) that address the multihop delay analysis for WMNs with finite nodes. In (Bisnik & Abouzeid, 2006), WMNs are modeled as G/G/1 queueing networks. Based on the diffusion approximation approach to characterize the traffic arrivals at each mesh router, the average multihop delay and maximum achievable throughput, which is similar to the well known asymptotic capacity of wireless multihop wireless ad-hoc networks provided in (Gupta & Kumar, 2000), are derived for WMNs. It is worth noting that the performance metrics, such as the average multihop delay and maximum achievable throughput, cannot be used for design and analysis of algorithms and protocols for supporting applications such as VoIP and real-time video streaming with the bounded delay or minimum date rate requirements. In (Chen & Yang, 2006), the authors extend the effective capacity model developed in (Wu & Negi, 2003) to multihop wireless communications and derive a probabilistic bound on delays experienced by traffic flows over multiple point-to-point wireless links. It is worth noting that the results developed in (Chen & Yang, 2006) rely on two assumptions, i.e., the traffic distortion due to multihop traveling can be ignored, and the delays experienced by traffic flows at each hop are independent and identically distributed (i.i.d.) random variables, which may not be true in realistic WMNs. By now, to the best of authors’ knowledge, no analytic algorithms and models exist for predicting the probabilistic bounds (not average values) on the end-to-end delays experienced by traffic flows over wireless mesh backbones consisted of static multi-radio mesh routers. Hence, new algorithms and models are needed. This motivates us to write this chapter that is based on our preliminary results described in (Li & Zhao, 2008). In this chapter, we consider multi-radio and multi-channel WMNs with IEEE 802.11 HCCA MAC based ingress access points for local clients and enough non-overlapping channels for point-to-point wireless links of wireless mesh backbones. In Section II, we briefly describe several components of multi-radio and multi-channel WMNs and some theoretical background about large deviations technique. In Section III, we estimate the probabilistic bound on the delays experienced by a traffic flow at an IEEE 802.11
3 HCCA MAC based ingress access point. We analyze the multihop delays experienced by various traffic flows over the backbones of multi-radio and multi-channel WMNs. By leveraging the large deviations technique, we turn probabilistic problems into deterministic optimization problems and derive a set of algorithms to evaluate the probabilistic bounds on the end-to-end delays experienced by traffic flows. In Section IV, we present the experimental results to demonstrate the feasibility of the proposed theoretical framework described in Section III. Finally, we offer our conclusion and point out potential future research directions in Section V.
II. BACKGROUND
Wired Network Mesh Router with Gateway
(24)
2 MR
3
7
21
(3)
MR
16
19
18
(24)
MR
17
16
MR
9
5
(10)
(12)
9
12 MR
MR
MR (22)
(11)
14
23 6
MR
(14) 20
(15)
19
Mesh Router with Gateway
(4)
(13)
21
5
1
Mesh Router with Gateway
Mesh Router with Gateway
17
MR
(1) 13
(21)
10
(2)
8
MR
22
MR
4
15 (14)
4 (7)
20
10
20
MR
MR MR
24
(22)
18
13
23
MR MR (11)
MR 6
15
(2)
(1)
(8) Mesh Router
denotes channel 2 assigned for ingress access of local clients denotes channel 20 dedicated to point-to-point wireless link
Figure 1. A Static Mesh Network Backbone
WMN Model Figure 1 shows an example with 21 wireless mesh routers for the backbones of broadband (high data rate) WMNs considered in this Chapter. Without loss of generality, we assume that each mesh router has multiple radios as the commercial multi-radio mesh router OWS or BelAir200. One of the radios is configured to communicate with local clients and the others are dedicated to forward traffic over the wireless backbone. In Figure 1, the number in a bracket denotes the channel assigned for local clients to access the wireless backbone, while the number above or under a dash line denotes the channel dedicated to the point-to-point wireless link between two adjacent mesh routers. By now, many routing protocols (Draves, Padhye, & Zill, 2004; Tang, Xue, & Zhang, 2005; Kodialam & Nandagopal, 2003) and channel assignment algorithms (Ramachandran, Belding, Almeroth, & Buddhikot 2006; Das, Alazemi, Vijayakumar, & Roy, 2005; Alicherry, Bhatia, & Li, 2005; Vedantham, Kakumanu, Lakshmanan, &
4 Sivakumar, 2006; Kodialam & Nandagopal, 2005; Kyasanur & Vaidya, 2005; Xing, Chen, Ma, & Liang, 2007) have been proposed to migrate or eliminate contention and interference from wireless communications over backbones of multi-radio and multi-channel WMNs. Therefore, we make the following assumptions: 1) There are enough non-overlapping wireless channels such as 27 non-overlapping IEEE 802.11 channels and a channel assignment algorithm such as that described in (Xing, Chen, Ma, & Liang, 2007); 2) All radios in each mesh router operate in different non-overlapping channels and can transmit or receive simultaneously without interference from each other. It is worth noting that the interference between radios of a mesh router operating at non-adjacent channels can be alleviated or eliminated by the elaborate wireless card shielding and antenna separations (Adya, Bahl, Padhye, Wolman, & Zhou, 2004; Robinson, Papagiannaki, Diot, Guo, & Krishnamurthy, 2005). For example, it has been exhibited (Adya, Bahl, Padhye, Wolman, & Zhou, 2004) that two Netgear WAB501 cards for IEEE 802.11a with a separation 6 inches in the same box and operating at non-adjacent channels (e.g., 56 and 64, 52 and 60) do not interfere each other. Similar empirical results for IEEE 802.11a radios can also be found in (Ramachandran, Sheriff, Belding-Royer, & Almeroth, 2006). Thus, considering the rapid innovation in wireless technologies, this assumption is reasonable for coming commercial multi-radio mesh routers; 3) The wireless mesh backbone is built from multiple point-to-point wireless links and each of these links uses the full spectrum of a channel to carry traffic flows without contention from other wireless links. Contrary to mobile nodes in an ad-hoc wireless network, the locations of static mesh routers can be carefully selected. Therefore, this assumption is reasonable for well planned WMN backbones with enough of non-overlapping channels; 4) There exists a routing algorithm such as that described in (Draves, Padhye, & Zill, 2004) to provide routes for traffic flows from their sources to the corresponding destinations; 5) All mesh routers of WMNs are identical. It is worth to point out that this assumption is for notational simplification. All results described in this chapter can be extended to WMNs with non-identical mesh routers without any technical difficulty.
MAC at Access Point
MAC Extent
Required for Contention−Free Service
Required for DiffServ
Required for Predictable QoS
Hybrid Coordination Function (HCF) Point Coordination Function (PCF)
HCF Contention Access (EDCA)
HCF Controlled Access (HCCA)
Used for Contention Service (basis for PCF & HCF)
Distributed Coordination Function (DCF)
Figure 2 . IEEE 802.11 MAC Architecture (IEEE Std, 2007) Figure 2 exhibits the functions of the IEEE 802.11 medium access control (MAC) protocol that has been specified in the IEEE 802.11 standard (IEEE Std, 2007) and widely used in wireless networks. These functions can be categorized into two classes. One is the distributed contention-based class based on the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism and includes the Distributed Coordination Function (DCF) and the enhanced Distributed Channel Access (EDCA). The
5 other is the centralized contention-free class based on polling scheme and includes the Point Coordination Function (PCF) and the Hybrid-Coordination-Function Controlled Channel Access (HCCA). The DCF and PCF were originally proposed for the legacy IEEE 802.11 wireless networks for data transmission (IEEE Std, 1999), while the EDCA and HCCA are the QoS enhancements of the DCF and PCF respectively. Generally, the DCF is unsuitable for applications with QoS requirements, while the EDCA only provides service differentiation, not delay or throughput guarantees. In addition, the PCF may not be able to provide predictable services, because of the unpredictable beacon delays and unknown transmission durations of the polled stations. It has been exhibited that for G729 codec with 40 ms packetization interval, a single IEEE 802.11a access point with the HCCA can support more than 295 VoIP calls (Trad, Munir, & Afifi, 2006), while the same access point with the DCF only supports no more than 126 VoIP calls (Garg & Kappes, 2003). This significant advantage of the HCCA over the contention-based channel access functions such as the DCF or EDCA is due to its contention-free nature that mitigates the packet collisions and random backoff idle time. Thus, in this chapter, we assume that the radio of each mesh router, which is dedicated to the AP for local clients, is supported by the IEEE 802.11 MAC with the HCCA. The HCCA channel access scheme is illustrated in Figure 3. More details about the HCCA can be found from (IEEE Std, 2007) and is omitted in this Chapter.
SI TXOP i : transmission opportunity for node i
SI SI : service interval
TXOP n
TXOP 2
TXOP n
EDCA
TXOP 1
CAP
TXOP 2
EDCA
TXOP 1
TXOP n
CAP
TXOP 2
TXOP 1
CAP
EDCA
SI CAP : controlled access period
Figure 3. IEEE 802.11 HCCA Channel Access Scheme (IEEE Std, 2007)
Point-to-Point Wireless Link IEEE 802.11a/g and IEEE 802.16 are well known standards that have been adopted by WMNs for high data rate wireless communications. These standards use Orthogonal Frequency Division Multiplexing (OFDM), which is a bandwidth-efficient parallel data transmission technique, to combat the frequency selective multipath fading of wideband channels. In OFDM scheme, a wideband channel is divided into multiple narrowband sub-channels, and a high rate data stream is split into multiple lower-rate data streams that are transmitted simultaneously and in parallel over these narrowband sub-channels. For example, IEEE 802.11a standard (IEEE Std, 1999) can provide data rate up to 54 Mbps over a channel of 20 MHz bandwidth in the 5-GHz unlicensed national information infrastructure (UNII) band. The 20 MHz bandwidth channel is divided into 52 sub-channels of about 300 KHz bandwidth. Since the symbol duration substantially increases for narrowband sub-channels, the relative amount of time dispersion caused by multipath delay spread is decreased and the frequency selective multipath fading is mitigated or eliminated. In this chapter, we consider OFDM-based broadband wireless mesh network backbones with stationary and ergodic frequency selective fading channels that vary at a rate much slower than the symbol rate, so each channel condition remains roughly constant over each packet transmitting time. Wireless Channel Models: Wireless mesh networks will be deployed in various environments. In this chapter, we consider five channel types proposed in (Medbo & Schramm, 1998) for these environments. The first type is Rayleigh fading channels with 50 ms root mean square (RMS) delay spread for the typical office environment. The second type is Rayleigh fading channels with 100 ms RMS delay spread for the large open space and office environment. The third type is Rayleigh fading channels with 150 ms RMS delay spread for the large open space environment. The forth type is Rician fading channels with 140 ms RMS delay spread for the large open space environment. The fifth type is Rayleigh fading
6 channels with 250 ms RMS delay spread for the large open space environment. Since the impulse response of a wireless channel contains all information necessary to analyze or simulate any type of radio transmission through the wireless channel (Rappaport, 2002), we use the following exponentially decaying finite impulse response (FIR) filter, proposed in (Chayat, 1997), to characterize slowly fading frequency selective Rayleigh channels.
∑ h δ (t − kT ) , k max
h(t ) =
k
(1)
s
k =0
where kmax = the minimum integer that is not smaller than 10/ψ ; ψ =Ts /τrms; Ts is the sampling rate; τrms is the RMS delay spread of the frequency selective fading channel; hk ~ CN (0, σ k2 / 2) , k=0,1,……,kmax, are independent circular symmetric complex Gaussian random variables with zero mean and variance
σ k2 / 2 =
1 − e −ψ e− kψ ; and δ is the Dirac delta function. Similarly, we use the following − k maxψ 2(1 − e )
exponentially decaying FIR filter to characterize slowly fading frequency selective Rician channels. )
h (t ) =
K 1+ K
eθ
−1
+
1 1+ K
h(t ) ,
(2)
where K is the Rician factor and θ ∈ [0,2π ] ;
K θ e 1+ K
−1
characterizes the direct line-of-sight (LOS) path
with phase θ between the transmitter and the receiver; and h(t) is defined by Equation (1). When K=0, Rician channels become Rayleigh channels and Equation (2) degenerates to Equation (1). Furthermore, the background noise is modeled as the additive white Gaussian noise (AWGN) and the transmission power is assumed to be constant. Thus, the signal to noise ratio (SNR) at time t can be determined by
SNR (t ) = SNR× | h(t ) |2 ,
(3)
where SNR is the average SNR, and h(t) is determined by Equation (1) or Equation (2). Data Frame Burst SIFS Transmitter Data Frame
Receiver
SIFS
SIFS
SIFS
Data Frame
ACK
SIFS
SIFS Data Frame
Data Frame
ACK
SIFS
ACK
ACK
Figure 4. Continuous Data Frame Transmissions Over A Point-to-Point Wireless Link (IEEE Std, 2007) Wireless Channel Capacity Process: To characterize the capacity process of a point-to-point link over a wireless channel with a stop-and-go ARQ protocol, let {C[t],t>0} denote the total amount of traffic that can be successfully transmitted over the wireless channel during the time interval [0,t]. Based on the mechanism of a stop-and-go ARQ protocol, a successfully transmitted data packet means that the data packet and the corresponding ACK packet are successfully received. Moreover,
C[t ] = F (t , mc, Ldata , SNRdata ( x) x ∈ [0, t ], mc* , Lack , SNRack ( x) x ∈ [0, t ]) , where Ldata and Lack are the lengths for data packet and ACK packet, respectively; mc and mc* are the modulation and coding schemes used for data packet and ACK packet, respectively. Wireless Link Effective Capacity: To evaluate probabilistic bounds on the delays experienced by traffic arrivals over a point-to-point wireless link, we use the effective channel capacity model defined in (Li, Che, &Li, 2007) to probabilistically lower bound the available channel capacity of the wireless point-
7 to-point link. An effective channel capacity function for a point-to-point link over a fading channel is a non-negative real function Sε such that for any time interval with length x
S ε ( x ) = sup{X ∈ [0, ∞ ) | Pr{C[t + x ] − C[t ] < X }, ∀ t ≥ 0} ,
(4) For IEEE 802.11a channels, an OFDM PHY layer simulator has been provided in (Heiskala & Terry, 2001) to simulate packet transmissions under various channel environments. By an extension of this OFDM simulator, the corresponding channel capacity process C[t] can be simulated under various channel environments. From the obtained channel capacity process C[t], Sε (x) can be estimated; see Section IV for more details.
Moment Bound In this chapter, we adopt the following moment bound approach to evaluate the tail probability of a random variable X such as delay or backlog length experienced by traffic arrivals.
Pr{X ≥ a} ≤
E[ X k ] , ∀a ≥ 0 and k =1, 2, ak
L.
(5)
Several well known properties for the moment of independent random variables have been described in (Bucklew, 1990). Proposition 1: Let X be a random variable, if 0 is an interior point in {s : E[e sX ] < ∞},
d k E[e sX ] E[ X ] = , for k = 1,2, ds k s =0 k
L.
(6)
∑ X . If E[ X n
Let X1,……,Xn be independent random variables and X =
0 ≤ k i ≤ k , i = 1,
E[ X k ] =
∑
L, n, then
L
k1 + + k n = k
n
k!∏ i =1
i
ki i
] exists for all
i =1
E[ X iki ] . ki !
(7)
Traffic Models Now, we study the commonly-used regulated and on-off Markov traffic models. Let {Ai,0[t], t > 0} denote flow-i source traffic process, i.e., Ai,0[t] is the total traffic generated by the traffic source during [0,t]. Without loss of generality, we make two basic assumptions about traffic sources. I. Stationary: For any flow i and any non-negative numbers t1, t2,τ, and x, the traffic source process Ai,0 satisfies Pr{Ai ,0 [t1 + τ ] − Ai ,0 [t1 ] > x} = Pr{Ai ,0 [t 2 + τ ] − Ai ,0 [t 2 ] > x}. II. Independence: Traffic source processes Ai,0 and Aj,0 are stochastically independent for i ≠ j . Regulated Traffic: A traffic flow Ai,0 is regulated by a nondecreasing, nonnegative, sub-additive function Ai* if
∀ t , τ ≥ 0 : Ai , 0 [t + τ ] − Ai , 0 [t ] ≤ Ai* (τ ) .
(8)
One example for such traffic is the leaky bucket controlled traffic with Ai*(τ) = β + ρτ, where β is the bucket size and ρ is the token generation rate. Let Xi(τ) = Ai,0[t+τ] − Αi,0[t], according to (Kelly 1996), the moment-generating function of Xi(τ) is given as:
8 ρi (e sA (τ ) − 1), Ai* (τ ) * i
E[e sX i (τ ) ] = 1 +
(9)
where
ρ i = lim
Ai* (τ )
τ
τ →∞
.
For n identical and independent traffic sources with a regulated function A* and an average traffic arriving rate ρ , let Xˆ (τ ) denote the total traffic arrivals from these n traffic sources during a time interval with length τ. Based on Formula (9), ˆ
E[e sX (τ ) ] = [1 +
ρτ (e sA (τ ) − 1)]n . A* (τ ) *
By Proposition 1 and simple calculus manipulations, we have a formula for the kth moment of Xˆ (τ ) as follows:
(
∑
i
)
k
n! A* (τ ) ρτ ρτ ˆ 1 − * E X (τ ) = i = 0 (n − i )!i! A (τ ) A* (τ )
(
n −1
)
k
n−i
(n − i ) k .
(10)
Markov On-Off Traffic: A stationary On-Off traffic source is generally characterized as a two-state 1 − p1 p and the Markov chain which is described in terms of the probability transition matrix Ρ = 1 1 −
p2
p2
stationary distribution vector π = (π 1 , π 2 ). Here, 1- p1 and 1- p2 are the transition probabilities from state `On' to state `Off' and from state `Off' to state `On', respectively. p1 and p2 are the probabilities for staying in state `On' and in state `Off', respectively. π satisfies π = π Ρ. In state `On', the traffic arrival is generated at the peak rate R, while in state `Off', no traffic arrival occurs. Let {A[t], t > 0} denote an on-off traffic source process, i.e., A[t] is the total traffic generated by the onoff source in [0, t]. Let Y(τ ) = A[t +τ]-A[t], according to (Chang, 2000), the moment-generating function of Y(τ) is given as:
E[e sY (τ ) ] = π [Φ ( s )Ρ ]τ −1 Φ ( s )Ι, e
where Φ ( s ) =
[
]
0
E (Y (τ ) ) = R k π 1 k
(11)
1 0 and Ι = . By simple calculus manipulations, we have 1 1
Rs
∑a τ −1
∑b τ −1
k τ −1. h ( h + 1) + π 2
h=0
τ −1, h
hk ,
h =1
(12)
where coefficients aτ-1, h and bτ-1,h, h = 0, ……,τ-1, are determined by the following iterative equations: a 0, 0 = 1; b0, 0 = 0;
a1, 0 = 1 − p1, a1,1 = p1 ;
M
a j , 0 = (1 − p1 )b j −1, 0 ,
b1, 0 = p 2 , b1,1 = 1 − p 2 ;
L, a
M aτ −1, 0 = (1 − p1 )bτ − 2, 0 ,
j ,h
= p1 a j −1, h −1 + (1 − p1 )b j −1, h ,
b j , 0 = p 2 b j −1, 0 ,
L, a
τ −1, h
L, b
j ,h
L, a
L, b
= p1 a j −1, j −1 ;
= (1 − p 2 )a j −1, h −1 + p 2 b j −1, h ,
= p1 aτ − 2, h −1 + (1 − p1 )bτ − 2, h ,
bτ −1, 0 = p 2 bτ − 2, 0 ,
j, j
τ −1, h
L, a
τ −1,τ −1
L, b
j, j
= (1 − p 2 )a j −1, j −1 ;
= p1 aτ − 2,τ − 2 ;
= (1 − p 2 )aτ − 2, h −1 + p 2 bτ − 2, h ,
L, b
τ −1,τ −1
= (1 − p 2 )aτ − 2 ,τ − 2 .
9
For n identical and independent Markov On-Off traffic sources, let Yˆ (τ ), denote the total traffic arrivals from these n traffic sources during a time interval with lengthτ. Based on Formula (11),
[
τ −1
]
n
E[esY(τ ) ] = π[Φ(s)Ρ] Φ(s)Ι . ˆ
By Proposition 1 and the generalized Leibniz’s law, we have a formula for the kth moment of Yˆ (τ ) as the following:
E[(Yˆ (τ )) k ] =
∑
L
q1 + + qn = k n
k!∏
E[(Y (τ )) qi ] , qi !
(13)
where E[(Y(τ)) ] is defined by Formula (12).
A Challenge Problem Consider traffic flow i with the path [mesh router i1, mesh router i2, ……, mesh router ip+1] over a WMN and let Ai,j[t] denote the total flow-i traffic arriving at its jth hop, i.e., mesh router ij, during [0,t]. To simplify notations, we also use [l(i,1), l(i,2), ……, l(i, p)] to denote flow-i path, where l(i, j) is the wireless link from mesh router ij to mesh router ij+1, j=1,2,……,p. A challenge for supporting delay-sensitive applications such as VoIP, video streaming, and interactive gaming over WMNs, is to predict the end-toend delay experienced by traffic flow i, i.e., for ε in (0,1), to find ε,i such that for all t >0,
D
end to end delay suffered by ≤ε . ε ,i any tagged flow i arrival > D
Pr
III. A THEORETIC FRAMEWORK FOR PREDICTING END-TO-END DELAY Now, we provide a set of algorithms for predicting the end-to-end delays experienced by traffic flows over multi-radio and multi-channel WMNs.
Ingress Access Point Delay To analyze the delays experienced by traffic at ingress access points, we need to study the packet drop probability experienced by traffic flows at an ingress access point and the capacity of an ingress access point. Packet Drop Probability: Generally, the packet transmission error probability depends on the adopted modulation and coding scheme (mc), the packet size (L), and the SNR. Without loss of generality, we denote it as PER(SNR, mc, L). It is worth noting that two experiment-based packet error probability formulas for OFDM system are recently derived in (Awoniyi, 2005). In this chapter, according to the time and space diversity, we assume that at each ingress access point, packet transmission error events during one SI time interval are independent. Let
pi,1 = PER(SNRi , mci1 , LCF _ Poll) be the transmission error probability of a CF_Poll frame with size LCF_Poll for flow i. Let
pi,2 = PER(SNRi , mci2 , Li,data ) be the transmission error probability of a data frame with size Li,data for flow i. Let
pi,3 = PER(SNRi , mci3 , Lack ) be the transmission error probability of an ACK packet with size LACK for flow i. The probability for a flow-i data packet needed to be retransmitted is bounded by
10
pi = 1 − (1 − pi,1 )(1 − pi,2 )(1 − pi,3 ) . If the number of retransmissions of a packet at each ingress access point is limited by ndrop, the probability of a flow-i packet being dropped is given as: n
p i , drop = pi drop
+1
.
(14)
In this chapter, we use ndrop= 4. The obtained results can be extended to ndrop > 4 or ndrop < 4 without any technical difficulty. Capacity of Ingress Access Point: Based on the reference admission control algorithm provided in (IEEE std, 2007) for IEEE 802.11 MAC with the HCCA, n traffic flows can be supported by an ingress access point if the following inequality holds: n T TXOPi TXOPretrans. (15) + ≤ 1 − cp , SI SI T i =1 where TXOPi is the time duration reserved for flow i and includes the transmission time for the data, ACK and CF_Poll frames, as well as the required inter frame spaces; SI denotes the length of a service interval; Tcp denotes the available contention-based channel access time during each beacon interval; T is the beacon interval length; and TXOPretrans. is the time reserved for the retransmissions of corrupted packets during each SI time interval.
∑
Due to the space and time diversity, it is a rare event that all transmissions during one SI time interval fail. Thus, we can exploit the multi-user diversity and stochastic multiplexing gains to compute TXOPretrans.. Without loss of generality, we assume that the packet size of a traffic flow is a constant, but the different traffic flows may have different packet sizes. Also, based on the sizes of TXOPs, we categorized these n traffic flows into M classes, S1, S2,……, SM such that TXOPi1 = TXOPi2 if i1 , i 2 ∈ S i for some i in {1,2,…,M}. Therefore, for a given ε 0 ∈ (0,1) and during one SI time interval, the number ε
of class-i data packets that corrupt in their first transmission is not larger than ni ,10 with probability
1 − ε 0 , where niε,10 is given as follows: |Si | (16) ni ,1 = min k | ph ∏ (1 − ph ) ≤ ε 0 . ∏ j = k + 1 S ⊂ S h ∈ S h ∉ S \ S i i |S |= j ε0 h Furthermore, let S i denote the set of these ni , h class-i packets that are needed to be retransmitted after
∑∑
ε0
their hth retransmissions, where h=1,……, ndrop. Then, with probability 1 − ε 0 , the number of class-i data ε
ε
packets that corrupt in their hth transmissions is not larger than ni ,0h +1 , where ni ,0h +1 is given as follows: ε0
ni , h
= min k |
pm ∏ (1 − pl ) ≤ ε 0 , ∏ h h j = k +1 S ⊆ S i m∈S l∈S i \ S | S |= j
∑∑ | S ih |
Therefore TXOPretrans. =
∑ ∑n M n drop
ε0 i,h
× TXOPk i , where k i ∈ S i .
i =1 h =1
After the above discussion, we begin to evaluate the probabilistic bound on the delays experienced by traffic flows at ingress access points.
(17)
11
Ingress Access Delay: According to the HCCA channel access scheme, during any time interval
[t,t+τ],
τ
SI
× Li ,data amount of flow-i traffic will be either successfully delivered or dropped. A dropped
packet can be treated as experiencing an infinite delay. In the following lemma, we provide a formula to ε
evaluate the probabilistic bound Dl (ii,,00) on the delays experienced by flow-i traffic at the ingress access point. ε
Lemma 1: Dl (ii,,00) is given as follows:
n E (Ai , 0 [t ] − Ai , 0 [ x]) = inf d | sup inf n n≥0 x∈[ 0, t ] t − x + d L i , data SI
≤ η , ∀t > 0, = pi , drop + η + ndrop × ε 0 ; pi , drop is the probability of a flow-i
[
ε
Dl (ii,,00)
where Li,data is the packet size of flow i; ε i , 0
]
packet being dropped at the ingress access point after experiencing ndrop retransmissions and can be determined by Formula (14); ndrop × ε 0 is the probability of a flow-i packet being dropped before ndrop retransmissions. Proof: The proof is similar to and much simpler than that of Theorem 1 in the following, and omitted.
Point-to-Point Wireless Link Delay Now, we consider the jth hop of flow i, i.e., the point-to-point wireless link l(i, j) from mesh router ij to mesh router ij+1. For a tagged traffic arrival of flow i arriving at mesh router ij at time t, let τ(t) denote the last time before time t when there is no traffic arrival at mesh router ij to traverse wireless link l(i, j). To simplify notations, let A l (i , j ) [τ (t ), t ] denote all traffic arrivals that arrive at mesh router ij during [τ(t), t] to traverse over wireless link l(i,j), i.e., (18) A l (i , j ) [τ (t ), t ] = Ag , g m [t ] − Ag , g m [τ (t )] ,
∑(
)
g∈Ql ( i , j )
where Ql ( i , j ) denotes the set of all traffic flows traversing wireless link l(i,j), and for g ∈ Ql ( i , j ) , gm is defined by l(g, gm) = l(i, j), i.e., l(i, j) is the g mth hop of flow g. Hence, the tagged traffic arrival is successfully received or dropped before time t+d if the total traffic arriving at mesh router ij during [τ(t),t] to traverse l(i, j) are successfully received or dropped by mesh router ij+1 before time t+d. Moreover, the available channel capacity during [τ(t), t+d] for wireless link l(i,j) is C[t+d] - C[τ(t)], where C[t] is characterized by Formula (4). Thus, a sufficient condition for the tagged traffic arrival being successfully transmitted before time t+d is the following: CumulativeTraffic Arrivals HAve To Be Transmitted During [τ (t ),t ]
4 48 4 64474448 647 Available Channel Capacity During [τ ( t ),t + d ]
C[t + d ] − C[τ (t )] − A l (i , j ) [τ (t ), t ] ≥ 0 . εi, j l (i , j )
Let D
(19)
denote a probabilistic bound with violation probability εi ,j for delays experienced by traffic
flow i when traversing wireless link l(i,j). That is, for all t >0
{(
ε
)
ε
}
Pr C[t + Dl (ii,,jj ) ] − C[τ (t )] − Al (i , j ) [τ (t ), t + Dl (ii,,jj ) ] ≥ 0 ≥ 1 − ε i , j .
12
By the large deviation technique, we provide the following theorem to estimate the probabilistic bound on the delays experienced by traffic arrivals at the point-point wireless link l(i,j). ε
Theorem 1: Dl (ii,,j j ) is given as follows: εi, j
Dl ( i , j )
[(
) ] ≤ η )
E A l (i , j ) [ x, t ] n = inf d | sup inf n x∈[ 0 ,t ] n ≥ 0 S η1 (t − x + d )
(
2
, ∀t > 0,
(20)
where ε i , j = η1 + η 2 + pl ( i , j ),drop ; pl (i , j ), drop is the probability of a traffic arrival being dropped at the point-to-point wireless link l(i,j) and can be determined by a formula that is similar to Formula (14); η1 is related with S η1 (t − x + d ) that is defined in Formula (4); and A l (i , j ) [ x, t ] is defined in Formula (18). Proof: Consider a tagged traffic arrival of flow i arriving to the transmitter of wireless link l(i,j) at time t .
First, if this tagged traffic arrival will not dropped due to multiple transmission errors, according to Inequality (19), the probability of violating a delay bound D lε(ii, ,j j ) for this tagged traffic arrival is upper bounded by the following: ε Pr C[t + Dl (i , j ) ] − C[τ (t )] − A l (i , j ) [τ (t ), t ] < 0
{(
(a)
)
i, j
{{(
)
ε
}
}I {(C[t + D ] − C[τ (t )])− S (t − τ (t ) + D ) ≥ 0}} (t − τ (t ) + D ) < 0} ) > 0}+ Pr{(C[t + D ] − C[τ (t )]) − S (t − τ (t ) + D ) < 0} ) ] > 0 + Pr sup [(C[t + D ] − C[τ (t )]) − S (t − τ (t ) + D ) ] < 0 εi , j
≤ Pr C[t + Dl (ii,,j j ) ] − C[τ (t )] − A l ( i , j ) [τ (t ), t ] < 0
{(
)
ε
+ Pr C[t + Dl (ii,,j j ) ] − C[τ (t )] − S η1 (b)
{
ε
ε ≤ Pr sup A l (i , j ) [ x, t ] − S η1 (t − x + Dl (ii,,j j ) x∈[ 0,t ]
[
(d )
{[
ε
l (i , j )
εi, j
l (i, j )
εi, j
≤ Pr A l (i , j ) [τ (t ), t ] − S η1 (t − τ (t ) + Dl (ii,,j j )
(c )
εi , j
η1
l (i , j )
εi, j
η1
l (i, j )
l (i, j )
εi, j
] }
l (i, j )
x∈[ 0,t ]
{(
ε
l (i, j )
)
(21)
εi, j
η1
}
ε
≈ sup Pr A l ( i , j ) [ x, t ] − S η1 (t − x + Dl (ii,,j j ) ) > 0 + sup Pr C[t + Dl (ii,,j j ) ] − C[ x] − S η1 (t − x + Dl (ii,,j j ) ) < 0 x∈[ 0 ,t ]
≤ sup inf x∈[ 0 ,t ] n≥0
[(
)]
E A l ( i , j ) [ x, t ]
(e)
(S
η1
ε
x∈[ 0 ,t ]
n
(t − x + Dl (ii,,j j ) )
)
n
+ η1
(f)
≤ η1 + η 2 ,
where (a) is supported by that for any two random events X and Y, Pr{X } ≤ Pr{X I Y }+ Pr Y c , where Yc denotes the complement of Y; (b) is based on that {(C[t + Dlε(i, j ) ] − C[τ (t )]) < A l (i, j ) [τ (t ), t ]}I {(C[t + Dlε(i, j ) ] − C[τ (t )]) ≥ S η (t − τ (t ) + Dlε(i, j ) )}⊆ {A l (i, j ) [τ (t ), t ] > S η (t − τ (t ) + Dlε(i, j ) )}; (c) comes from τ (t ) ∈ [0, t ] ; (d) follows the approximation described in Equation (11) in (Knight & Shroff, 1999); (e) is due to Formula (4) and Inequality (5); (f) is obtained from Formula (20). i, j
{ }
i, j
1
i, j
i, j
1
Second, considering that this tagged traffic arrival is dropped after ndrop transmission errors. Since a dropped traffic arrival can be treated as experiencing an infinite delay, the delay bound violation probability for the tagged traffic arrival in this case is the dropped probability
pl ( i , j ),drop . ε
Therefore, combining aforementioned cases, the probability of violating delay bound Dl (ii,,j j ) for the tagged traffic arrival experiencing at the point-to-point wireless link l(i,j) is
ε i , j = η1 + η 2 + pl (i , j ),drop .
13
ε
ε
Remark: Dl (ii,,j j ) = Dl (ig, j, g m ) for l (i , j ) = l ( g , g m ) , i.e., the traffic flows that traverse the same point-to-
point wireless link with the first come first serve scheduling discipline share the same probabilistic delay bound.
Characterization of Down Stream Traffic To apply Theorem 1 to estimate probabilistic bounds on delays experienced by traffic arrivals at down stream mesh routers, the traffic characteristics such as moments at down stream mesh routers are needed. Usually, traffic flows will be distorted after traversing one hop. Without reshaping the distorted traffic at down stream mesh routers, the characteristics of down stream traffic arrivals are not the same as that of upstream traffic arrivals. According to the IEEE 802.11 MAC with the HCCA medium access mechanism at ingress access points and the probabilistic bounds for delays experienced by traffic flows at upstream mesh routers, i.e., Dlε(i , h ) , h = 1, , j − 1,
L
i ,h
delay suffered by any traffic arrival Pr ≤ ε i ,h , ε of flow i over l (i, h) > Dl (ii,,hh ) we provide the following algorithms to characterize traffic flows at downstream mesh routers. Based on Lemma 1, we have the following algorithm to characterize traffic flows at their first hop (ingress access points). Lemma 2: For any flow i, ∀t > x ≥ 0 ,
{
(
)}
Pr ( Ai ,1[t ] − Ai ,1 [ x]) > Ai ,0 [t ] − Ai ,0 [ x − Dl (ii,,00) ] ≤ ε i ,0 , ε
(22)
ε
where Dl (ii,,00) and ε i ,0 are determined in Lemma 1. Proof: The proof is similar to that of Lemma 3. Remark: For a Markov On-Off traffic source, if SI equals the minimum packet inter-arrival time, e.g., SI = packetization time of voice signal, we have a simpler characterization of Ai,1[t] - Ai,1[x] as follows:
Ai ,1 [t ] − Ai ,1 [ x ] ≤ Ai , 0 [t ] − Ai , 0 [ x − SI ] . Considering the point-to-point wireless link l(i,j) that is on the jth hop of flow-i path. Since there may be other traffic flows that share this link with flow i, according to traffic flows` paths, we partition all flows, which traverse wireless link l(i, j) and are denoted by Ql ( i , j ) , into K sets, i.e., Wm m = 1,2, , K , with
L
the following properties. 1) All flows in Wm share the same path [mesh router q1, mesh router q2,……, mesh router qkm], i.e., mesh router qh is the hth hop for all flows in Wm for h=1,2,……,km; 2)
Wm1 ∩ Wm2 is empty if m1 ≠ m2 and for any integer m ≤ K ;
3)
Mesh router qk m = mesh router ij and l(q, km) = l(i, j) for q ∈ W m ;
4)
Ql ( i , j ) =
UW K
m
.
m =1
Lemma 3: For any given Wm , ∀t > x ≥ 0 ,
14
Pr{
∑ (A
q, km
∑(A
)
[t ] − Aq , k m [ x] >
q∈Wm
∑D
k m −1
[t ] − Aq ,1[ x −
q ,1
q∈Wm
ε q,h
l (q, h)
∑ε
k m −1
])} ≤
h =1
q, h
(23)
,
h =1
where Dlε( q, h ) and ε q, h are determined by Theorem 1. q ,h
Proof: Consider the first traffic arrival (tagged traffic arrival) at mesh router qk m from flows in Wm
during [x, t]. Let κ (x) and s(x) denote its arrival times at mesh router qk m and mesh router q1 , respectively. So κ ( x ) ≥ x and no traffic arrival at mesh router qk m from flows in Wm during [ x, κ ( x )) . It is worth noting that at each mesh router, the traffic arrivals from flows in Wm are served in the first-in first-out order. Hence, at mesh router qk m , for the traffic arrivals of flows in Wm with arriving times in [x, t], their corresponding arriving times at mesh router q1 are not earlier than s(x). So
∑ (A
q, km
)
[t ] − Aa , k m [ x] =
q∈Wm
∑ (A
q, k m
∑ (A
)
[t ] − Aq , k m [κ ( x)] ≤
q∈Wm
[t ] − Aq ,1[ s( x)]) .
q ,1
q∈Wm
ε
According to the aforementioned definition of Dl (qq,h, h ) and the fact that κ ( x) − s ( x) is the total delay experienced by the tagged traffic arrival before arriving at mesh router qk m , we have
∑
∑
∑
k m −1 k m −1 delay suffered by the tagged k m −1 ε Pr s( x) < κ ( x) − Dl (qq,,hh ) ≤ Pr ε q, h , ε q ,h ≤ th arrival at its h hop > D l ( q , h ) h = 1 h = 1 h = 1
(24)
Thus, we have k m −1 ε Pr Aq ,k m [t ] − Aq ,k m [ x] > ( Aq ,1 [t ] − Aq ,1 [ x − Dl (qq, h,h ) ]) q∈Wm h =1 q∈Wm
∑(
∑
)
∑(
)
∑(
)
∑
∑
∑
k m −1 ε = Pr Aq ,k m [t ] − Aq ,k m [κ ( x)] > ( Aq ,1 [t ] − Aq ,1 [ x − Dl (qq, h,h ) ]) q∈Wm h =1 q∈Wm
(a)
∑
∑
k m −1 ε ≤ Pr Aq ,k m [t ] − Aq ,km [κ ( x)] > ( Aq ,1 [t ] − Aq ,1 [κ ( x) − Dl (qq, h,h ) ]) q∈Wm h =1 q∈Wm
(b )
∑(
∑
(25)
∑
k m −1 ε ≤ Pr Aq ,k m [t ] − Aq ,1 [ s ( x)] > ( Aq ,1 [t ] − Aq ,1 [κ ( x) − Dl (qq, h,h ) ]) q∈Wm h =1 q∈Wm
(c )
)
∑
k m −1 ε ≤ Pr s ( x) < κ ( x) − Dl (qq, h,h ) h =1
(d )
∑ε
( e ) k m −1
≤
q ,h ,
h =1
where (a) is due to no traffic arriving at mesh router qk m from flows in Wm during [ x, κ ( x)) ; (b) comes from κ ( x) ≥ x ;(c) is supported by the definition of s(x) and the fact that all traffic arriving at mesh router q1 from flows in Wm during [0, s(x)) have arrived at mesh router qk m at time κ ( x ) , i.e.,
∑A
q ,km
q∈Wm
[κ ( x)] ≥
∑A
q ,1
[s( x)] ; (d) is based on that Aq , k [t ] ≤ Aq ,1[t ] and m
q∈Wm
∑
k m −1
Aq ,1[ s ( x)] ≥ Aq ,1[κ ( x ) −
h =1
∑D
k m −1 ε q ,h
Dl ( q ,h ) ] , if s ( x) ≥ κ ( x ) −
ε q ,h
l ( q, h)
h =1
; (e) follows Inequality (24).
15
According to Lemma 3, the aggregated traffic arrivals at the point-to-point wireless link l(i, j), which is denoted by A l ( i , j ) [ x, t ] and defined in Equation (18) and used in Theorem 1, can be probabilistically characterized by the corresponding traffic flows in their ingress mesh routers as follows: Corollary 1:
{
Pr A
l (i , j )
} ∑∑ε
[ x, t ] > Aˆ l ( i , j ) [ x, t ] ≤
K
km
q,h
m =1 h =1
where q ∈ M m ; km is determined by l(q,km)=l(i,j) and Aˆ l ( i , j ) [ x, t ] =
∑
∑
k m −1 ε Aq ,1 [t ] − Aq ,1 [ x − Dl (qq,,hh) ] q∈Ql ( i , j ) h =1
.
(26)
Proof: The proof is based on Formulas (18) and (26), and Lemma 3, and is simple and omitted.
Now, according to the above results, the probabilistic bounds on the delays experienced by traffic flows at the downstream wireless links can be evaluated only based on the characteristics of their traffic sources as follows. ε
Corollary 2: For wireless link l(i,j) with traffic arrivals from upstream mesh routers, Dl (ii,,j j ) is given as
follows: ε
Dl (ii,,j j )
E Aˆ l ( i , j ) [ x, t ] n ≤ η 2 , ∀t > 0 = inf d | sup inf , n η n≥0 x∈[ 0,t ] S 1 (t − x + d )
(
)
(
)
∑∑ε K
where ε i , j = η1 + η 2 + d l ( i , j ), drop +
km
q, h
; q ∈ Wm and km is determined by l(q,km)=l(i,j);
m =1 h =1
η1 and d l ( i , j ), drop are the same as that in Theorem 1. Proof: The proof is similar to that of Theorem 1 and Corollary 1 and omitted.
Probabilistic Bound on End-to-End Delay After obtaining probabilistic bounds on local delays experienced by traffic arrivals at ingress access points and point-to-point wireless links, a probabilistic bound on the end-to-end delays experienced by flow-i traffic arrivals traversing through the path [mesh router i1,mesh router i2,……,mesh router ip+1 ] is given in the following. ε ,i
Theorem 2: A bound D with violation probability ε for the end-to-end delays experienced by flow-i traffic is given as follows:
D
ε ,i
ε i ,0
= Dl ( i , 0 ) +
∑D ip
ε i,h l (i ,h)
∑ε ip
, ε = ε i ,0 +
h =1
ε
i ,h
,
h =1
ε
where Dl (ii,,00 ) and εi,0 are determined by Lemma 1, while Dl (ii,,hh ) and εi,h are determined by Theorem 1 and Corollary 2. Proof: The proof is simple and omitted.
IV. APPLICATIONS In this section, we present several examples based on the theoretical framework described in the previous sections. Our goal is to show how to apply the obtained results to predict the probabilistic bounds on the end-to-end delays experienced by traffic flows over WMNs.
16
System Setting: We consider an IEEE 802.11a based WMN backbone with the parameters of PHY and MAC layers provided in (IEEE Std, 1999). We assume the existence of a routing and channel assignment algorithm, such as those proposed in (Draves, Padhye, & Zill, 2004; Xing, Chen, Ma, & Liang, 2007), as well as enough of non-overlapping wideband channels and radios per mesh router for interference free multihop wireless communications over this WMN backbone. Overhead of MAC and PHY Layers: Continuous data frame transmissions between two adjacent mesh routers over an IEEE 802.11a channel are illustrated in Figure 4. As described in the specifications of PHY and MAC layers of IEEE 802.11a standard, the overhead of MAC and PHY layers for a data packet is 33 bytes and 6 bits, while overhead of PHY layer for an ACK packet is 46 bits. Traffic Parameters: We consider the Regulated and Markov On-Off traffic. For Markov On-Off traffic, we consider the output traffic from a G729 encoder with 40 ms packetization interval which digitizes every 40 ms voice signal sample into a data packet with 40 bytes. Thus, the corresponding peak rate is 8 Kbps. Without loss of generality, we assume that a voice activity detector that stops sending data during silence durations is used and the average talkspurt and silence durations of a speaker are 1.34 s and 1.67 s, respectively. Thus, based on the relationships, i.e., average talkspurt duration =(packetization interval)/(1-p1) and average silence duration = (packetization interval)/(1-p2) , the probability transition matrix P and the stationary distribution vector π can be determined for the discrete-time On-Off Markov traffic model described in Section II-E. For the Regulated traffic, we assume that the peak rate is 6 Mbps, the average rate is 0.15 Mbps, and the burst size is 8.192 kb. Note that the overhead of RTP/UTP/IP protocols for a data packet is 40 bytes.
Effective Channel Capacity For each of the non-overlapping IEEE 802.11a wideband channels between adjacent mesh routers, based on its channel capacity process C[t] obtained by a system-level simulator built on the top of the OFDM simulator for IEEE 802.1a PHY provided in (Heiskala & Terry, 2001), we estimate the effective capacity defined by Equation (4). Figure 5 depicts the obtained effective channel capacity of an IEEE 802.11a wideband channel with 64QAM modulation and 3/4 coding rate versus the time interval length for five fading channel types, three average SNR values, various packet sizes, and three violation probabilities ε =10-1, 10-2, 10-3. For each effective channel capacity curve in these figures, 103 random realizations of the IEEE 802.11a fading channel with 103 ms burst transmission period per realization are performed. For a given time interval length x and ε =10-1,10-2,10-3, about 104 sample points for C[t+x]-C[t] are collected from different time interval [t, t+x] and different channel realization. Let J denote the set of all sample points and sort J in the increasing order. Thus, Sε (x) can be estimated as the kth sample point of the sorted set J, where k is the largest integer bounded by ε.|J|. As a benchmark, we also include the corresponding channel nominal capacity determined by time x nominal data rate in Figure 5(a)~(d) and the average channel capacity in Figure 5(b), where the nominal data rate is the maximum channel data rate after taking into account of the PHY and MAC layer overhead. We make the following observations. First, according to Figure 5(a), the impact of the rms delay spread of an IEEE 802.11a fading channel on the effective capacity is significant. For any given time interval length, the effective channel capacity decreases with the increase of the rms delay spread. The larger the rms delay spread, the more severe the inter symbol interference becomes and, consequently, the more that decoding errors will occur. In addition, it is worth noting that Channel D outperforms other channels in Figure 5(a). This is due to the line-of-sight path of Rician channels. Second, from Figure 5(b), the impact of the required violation probability on the effective channel capacity is visible. The effective channel
17
capacity decreases as the required violation probability decreases. The essential reason for this scenario is apparent. The smaller the violation probability, the more conservative the available channel capacity lower bound, and thus the smaller the effective channel capacity. Third, according to Figure 5(c), the impact of the average SNR on the effective channel capacity is substantial. The effective channel capacity increases with the increase of the average SNR. The larger the SNR, the smaller the probability of packet transmission error and consequently, the higher the channel capacity. Finally, according to Figure 5(d), the impact of packet payload size on the effective channel capacity is significant due to the overheads of network, MAC, and PHY layers. Overall, the effective channel capacity increases with the increase of the average SNR value and the packet payload size, but decreases as the required violation probability decreases. Effective Channel Capacity (Mbits)
10
D
nel
n Cha
city
apa el C
7.5
n
r
No
5
nel B Chan
nel A Chan
2.5
0
han al C min
0
50
100
150
200
250 Time (ms)
300
Channel
C
350
400
Channel E
450
500
(a) Effective Capacities with SNR = 20 dB, Packet Size=512 Bytes and ε =10-3. (Rician factor K = 5 dB for Channel D). Effective Channel Capacity (Mbits)
10
apa
7.5
city
C nel
han
lC
N
5
ina orm
Cha erage
nnel
city
Capa
Av 2.5
ε=0.001 ε=0.01
ε=0.1 0
0
50
100
150
200
250 Time (ms)
300
350
400
450
500
(b) Effective Capacities for Channel C with SNR = 20 dB and Packet Size = 512 Bytes. Effective Channel Capacity (Mbits)
10
ty
ci apa
7.5
lC nne
= NR
ha lC
5d
R SN 2.5
SNR = 0
0
50
100
=2
dB
S
ina
rm No
5
30
B
20 dB
150
200
250 Time (ms)
300
350
-3
400
450
500
(c) Effective Capacities for Channel C with ε = 10 and Packet Size =512Bytes.
18
Effective Channel Capacity (Mbits)
15
24 = 10
12.5
s Size Byte ket 512 = Pac e z et Si Pack Bytes e = 256 iz S t e k Pac ytes e = 128 B Packet SIz
Packet Size = 20 Bytes Packet Size = 40 Bytes Packet Size = 60 Bytes Packet SIze = 80 Bytes
10 7.5 5 2.5 0
0
50
100
150
200
es
Byt
250 Time (ms)
300
350
400
450
500
(d) Effective Capacities for Channel C with SNR = 25 dB and ε = 10-3. Figure 5. Effective Channel Capacities for IEEE 802.11a with 64-QAM and 3/4 Coding Rate.
Probabilistic Delay Bounds Wired Network Mesh Router with Gateway
Mesh Router with Gateway
Mesh Router with Gateway
Mesh Router with Gateway
Hop 4 Mesh Router
Mesh Router
ter
ou
hR es
M Mesh Router
r Route
Other Flows Mesh Router
Other Flows Mesh Router
Hop 2 Mesh Router
Hop 1
e out
r
Me
sh
ou
Ro
ute r
R esh
Mesh Router
uter
ter
r
Mesh Ro
Route
Hop 3 r Route Mesh
Mesh
Mesh
Mesh Router
hR es
M
Mesh Router
M
Other Flows Tagged Flows
Figure 6. Traffic Flows in A Mesh Network Backbone.
In this subsection, we apply Theorem 2 obtained in Section III to predict the end-to-end delays experienced by traffic flows over a WMN. We consider a simple WMN depicted in Figure 6. We focus on the end-to-end delays experienced by the tagged flows that traverse four hops. To simplify experimental study, we assume that if the number of total flows finally entering the wired network is N, there are N/4 flows entering the wireless mesh backbone at hop k, k = 1,2,3,4. In addition, for Markov On-Off traffic, we set the beacon interval length T = 200 ms and the service interval length SI = 40 ms. For Regulated traffic, we set T = 200 ms and SI = 20 ms. To make our examples succinct, we assume that all wireless channels are the IEEE 802.11a channels with 64-QAM modulation and 3/4 coding rate in environment type C and the average SNR = 25 dB, which are the same as those discussed in the previous subsection. We also assume that there only exists one traffic class, i.e., M=1 and S1=n. Moreover, by the system-level simulator, when the average SNR = 25 dB, pi,1 = pi,3 = 0.05, pi,2= 0.06 for a data frame with size = 40 bytes, and pi,1 = pi,3 = 0.05, pi,2= 0.09 for a data frame with size = 512 bytes. Thus, based on Formula (14), we obtained pi,drop = 0.000082 for a data frame with size = 40 bytes and pi,drop = 0.000182 for a data frame with size = 512 bytes. According to IEEE 802.11a standard, TXOPi = 0.056407 ms for Markov On-Off traffic flows and TXOPi = 0.12633 ms for Regulated traffic flows. According to Formulas (16) and (17), the bounds with violation probability ε0=10-4 on the numbers of the data frames that corrupt in their hth transmission during a service interval are obtained and listed in Table I.
19
Regulated Traffic Source n
n10,1.0001
n 10,.20001
n10,.30001
n10,.40001
5 3 1 0 0 10 5 3 1 0 15 6 3 1 0 20 7 4 2 0 Markov On-Off Traffic Source n n10,1.0001 n 10,.20001 n10,.30001 n10,.40001 25 50 75 100
6 3 1 10 4 2 13 4 2 15 5 2 Table I: Retransmissions.
0 0 0 0
Figure 7 describes the relationship between the probabilistic delay bounds which are evaluated by using Theorem 2 and the number of total Markov On-Off or Regulated traffic flows that finally enter the wired network. From this figure, we can see that the probabilistic delay bound increases as the required violation probability decreases. The smaller the violation probability, the more conservative the delay bound. 150 Probabilistic Delay Bound (ms)
ε = 0.01 125
ε = 0.05 100
ε = 0.1
75 50 25 0 250
275
300 325 350 Number of Total Traffic Flows
375
400
(a) Markov On-Off Traffic (Packet Payload Size = 40 Bytes)
Probabilistic Delay Bound (ms)
150
ε = 0.01
125
ε = 0.05 ε = 0.1
100 75 50 25 0
25
30
35 40 Number of Total Traffic Flows
45
50
20
(b) Regulated Traffic (Packet Payload Size = 512 Bytes) Figure 7. Probabilistic Delay Bounds (Channel Type C with SNR = 25 dB).
V. CONCLUSION AND FUTURE RESEARCH DIRECTION In this Chapter, we focus on the wireless communications over multi-radio and multi-channel WMNs with IEEE 802.11 HCCA MAC based ingress access points and enough non-overlapping channels for point-to-point wireless links without co-channel interference. We develop a theoretic model for the endto-end performance analysis of such WMNs. By leveraging the large deviations technique, we turn probabilistic problems into deterministic optimization problems and derive a set of algorithms to analyze the end-to-end delays experienced by traffic flows. Consequently, we provide a theoretic framework to predict the probabilistic delay bounds for real-time applications over multi-radio and multi-channel WMNs with enough non-overlapping channels. The success of the wireless communication technology such as the IEEE 802.11 wireless networks has generated an explosive demand for the wireless spectrum and creates a shortage of spectrum resource. Currently, by governmental agencies such as the Federal Communication Commission (FCC) in USA and the European Telecommunications Standards Institute (ETSI) in Europe, the spectrum is divided into distinct frequency bands for various telecommunication services/users. Generally, all frequency bands can be categorized into licensed bands for licensees with exclusive use and unlicensed bands for public use. For example, there are 27 unlicensed non-overlapping channels for all IEEE 802.11 based wireless networks. However, the measurements obtained by the FCC Spectrum Policy Task Force reveal that at any location, many of the licensed frequency bands between 300 MHz and 3GHz such as TV bands are used sporadically. Recently, a new kind of WMNs, named cognitive WMNs, has been proposed to exploit the idle licensed frequency bands for unlicensed users and enhance the performance of WMNs. Roughly, a cognitive wireless mesh network consists of mesh routers equipped with multiple cognitive radios. Each cognitive radio is able to sense the external environment, learn from the history, and intelligently select available frequency channels for operating. Since the opportunities, i.e., unused licensed bands, vary with time and location and the active licensees of licensed bands need to be protected from harmful interference, the behavior of cognitive WMNs, which depends on the idle patterns of licensed bands as well as the related network topology and traffic load, are much complicated. Therefore, to model cognitive WMNs and predict their performance including queueing delays experienced by traffic flows is an open and very important research topic.
REFERENCES Adya, A., Bahl, P., Padhye, J., Wolman, A., & Zhou, L. (2004). A Multi-Radio Unification Protocol for IEEE 802.11 Wireless Networks. In Proceedings of IEEE BROADNETS 2004. Akyildiz, I. F., Wang, X., & Wang, W. (2005). Wireless mesh networks: A survey. Computer Networks and ISDN Systems, 47(4), 445-487. Alicherry, M., Bhatia, R., & Li, L. (2005). Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In Proceedings of ACM MOBICOM 2005. Awoniyi, O. (2005). Packet Error Rate in OFDM-based Wireless Networks and Its Impact on VoIP and TCP-Based Data Applications. Doctoral dissertation, Stanford University, California. Bansal, N., & Liu, Z. (2003). Capacity, Delay and Mobility in Wireless Ad-Hoc Networks, In Proceedings of IEEE INFOCOM 2003.
21
Bisnik, N., & Abouzeid, A. (2006). Delay and Throughput in Random Access Wireless Mesh Networks. In Proceedings of IEEE ICC 2006. Bruno, R., Conti, M., Gregori, E., Wijting, C., Kneckt, J., & Damle, A. (2005). Mesh Networks: Commodity Multihop Ad-Hoc Networks. IEEE Communications Magazine, 43(3), 123-131. Bucklew, J. A. (1990). Large Deviation Techniques in Decision, Simulation and Estimation. New York: John Wiley. Chang, C. S. (2000). Performance guarantees in communication networks. Springer. Chayat, N. (1997). Tentative Criteria for Comparison of Modulation Methods. IEEE P802.11-97/96. Chen, J., & Yang, Y. (2006). Multi-Hop Delay Performance in Wireless Mesh Networks. In Proceedings of IEEE GLOBECOM 2006. Das, A. K., Alazemi, H. M. K., Vijayakumar, R., & Roy, S. (2005). Optimization models for fixed channel assignment in wireless mesh networks with multiple radio. In Proceedings of IEEE SECON 2005. de Moraes, R. M., Sadjadpour, H. R., & Garcia-Luna-Aceves, J. J. (2004). Throughput Delay Analysis of Mobile Ad-Hoc Networks with a Multi-Copy Relaying Strategy. In Proceedings of IEEE SECON 2004. de Moraes, R. M., Sadjadpour, H. R., & Garcia-Luna-Aceves, J. J. (2006), Mobility-Capacity-Delay Trade-Off in Wireless Ad-Hoc Networks. Journal of Ad-Hoc Networks, 4(5), 607-620. Draves, R., Padhye, J., & Zill, B. (2004). Routing in multi-radio,multi-hop wireless mesh networks. In Proceedings of ACM MOBICOM 2004. Faccin, S. M., Wijting, C., Kneckt, J., & Damle, A. (2006). Wireless mesh networks: Concept and system design. IEEE Wireless Communications, 13(2), 10-17. Gamal, A., Mammen, J., Prabhakar, B., & Shah, D. (2004), Throughput-Delay Trade-Off in Wireless Networks. In Proceedings of IEEE INFOCOM 2004. Ganguly, S., Navda, V., Kim, K., Kashyap, A., Niculescu, D., Izmailov, R., Hong, S., & Das, S. R. (2006). Performance optimizations for deploying voip services in mesh networks. IEEE Journal on Selected Areas in Communications, 24(11), 2147-2158. Garg, S., & Kappes, M. (2003). Can I add a VoIP Call? In Proceedings of IEEE ICC 2003. Gupta, P., & Kumar, P. R. (2000). The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2), 388-404. Heiskala, J., & Terry, J. (2001). OFDM Wireless Lans: A Theoretical and Practical Guide. Sams. IEEE Std (1999). Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. ANSI/IEEE Std 802.11. IEEE Std (2000). Part 11: Wireless LAN MAC and PHY Specifications: Higher-Speed Physical Layer in the 5 GHz Band. ANSI/IEEE Std 802.11a.
22
IEEE Std (2007). Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. ANSI/IEEE Std 802.11. Kelly, F. (1996). Notes on effective bandwidths. In F. P. Kelly, S. Zachary, & I. B. Ziedins (Ed.), Stochastic Networks: Theory and Applications (pp. 141-168). Oxford University Press. Knightly, E., & Shroff, N. (1999). Admission control for statistical QoS: Theory and practice. IEEE Network, 13,(2), 20-29. Kodialam, M., & Nandagopal, T. (2003). Characterizing achievable rates in multi-hop wireless networks: The joint routing and scheduling problem. In Proceedings of ACM MOBICOM 2003. Kodialam, M., & Nandagopal, T. (2005). Characterizing the capacity region in multi-radio multi-channel wireless mesh networks. In Proceedings of ACM MOBICOM 2005. Kodialam, M., & Nandagopal, T. (2005). On the capacity region of multi-radio multi-channel wireless mesh networks. In Proceedings of IEEE WIMESH 2005. Kyasanur, P., & Vaidya, N. H. (2005). Capacity of multi-channel wireless networks: Impact of number of channels and interference. In Proceedings of ACM MOBICOM 2005. Kyasanur, P., So, J., Chereddi, C., & Vaidya, N. H. (2006). Wireless mesh networks: A challenge and protocols. IEEE Wireless Communications, 13(2), 30-36. Lee, M. J., Zheng, J., Ko, Y. B., & Shrestha, D. M. (2006). Emerging standards for wireless mesh technology. IEEE Wireless Communications, 43(4), 56-63. Li, C., Che, H.,& Li, S. (2007). A Wireless Channel Capacity Model for Quality of Service. IEEE Transactions on Wireless Communications, 6(1), 356--366.
，
Li C., & Zhao, W. (2008). Stochastic Performance Analysis of Multi-Radio Multi-Channel Wireless Mesh Networks. In Proceedings of the Fourth Internal Conference on Wireless and Mobile Communications 2008. Lin, X., Sharma, G., Mazumdar, R. R., & Shroff,N. B. (2006). Degenerate Delay-Capacity TradeOffs in Ad-Hoc Networks with Brownian Mobility. IEEE Transactions on Information Theory, 52(6), 2777-2784. Medbo, J., & Schramm, P. (1998). Channel Models for HIPERLAN/2. ETSI/BRAN doc. No. 3ERIO85B. Neely, M. J., & Modiano, E. (2005). Capacity and delay tradeoffs for ad-hoc mobile networks. IEEE Transactions on Information Theory, 51(6), 1917-1936. Niculescu, D., Ganguly, S., Kim, K., & Izmailov, R. (2006). Performance of VoIP in a 802.11 Wireless Mesh Network. In Proceedings of IEEE INFOCOM 2006. Perevalov, E., & Blum, R. (2003). Delay Limited Capacity of Ad-Hoc Networks: Asymptotically Optimal Transmission and Relaying Strategy. In Proceedings of IEEE INFOCOM 2003. Perevalov, E., & Blum, R. (2006). Capacity Region, Minimum Energy and Delay for a Mobile Ad-Hoc Network. In Proceedings of IEEE Internal Symposiumon Modeling and Optimization in Mobile Ad-Hoc Wireless Networks 2006.
23
Ramachandran, K. N., Belding, E. M., Almeroth, K. C., & Buddhikot, M. M. (2006). Interference-aware channel assignment in multi-radio wireless mesh networks. In Proceedings of IEEE INFOCOM 2006. Ramachandran, K., Sheriff, I., Belding-Royer, E., & Almeroth, K. (2008). A Multi-Radio 802.11 Mesh Network Architecture. Journal of Mobile Networks & Applications, 13(1), 132-146. Rappaport, T. S. (2002). Wireless Communications Principles and Practice, 2nd edition. Prentice-Hall, Englewood Cliffs, NJ. Robinson, J., Papagiannaki, K., Diot, C., Guo, X., & Krishnamurthy, L. (2005). Experimenting with a Multi-Radio Mesh Networking Testbed. In Proceedings of IEEE WINMEE 2005. Sharma, G., Mazumdar, R., & Shroff, N. (2007). Delay and capacity trade-offs in mobile ad hoc networks: A global perspective. IEEE/ACM Transactions On Networking, 15(2), 981-992. Tang, J., Xue, G., & Zhang, W. (2005). Interference-aware topology control and QoS routing in multichannel wireless mesh networks. In Proceedings of ACM MOBIHOC 2005. Trad, A., Munir, F., & Afifi, H. (2006). Capacity Evaluation of VoIP in IEEE 802.11e WLAN Environment. In Proceedings of IEEE CCNC 2006. Vedantham, R.,Kakumanu, S., Lakshmanan, S., & Sivakumar, R. (2006). Component based channel assignment in single radio, multi-channel ad-hoc networks. In Proceedings of ACM MOBICOM 2006. Xing, K., Chen, X., Ma, L., & Liang, Q. (2007). Superimposed code based channel assignment in multiradio multi-channel wireless mesh networks. In Proceedings of ACM MOBICOM 2007. Wu, D., & Negi, R. (2003). Effective capacity: A wireless link model for support of quality of service. IEEE Transactions on Wireless Communications, 2(4), 630-643.
ADDITIONAL READING Anastasopoulos, M. P., Panagopoulos, A. D., & Cottis, P. G. (2008). A distributed routing protocol for providing QoS in Wireless Mesh Networks operating above 10 GHz. Wireless Communications and Mobile Computing, 8(10), 1233-1245. Andreopoulos, Y., Mastronarde, N., & Van Der Schaar, M. (2006). Cross-layer optimized video streaming over wireless multihop mesh networks. IEEE Journal on Selected Areas in Communications, 24(11), 2104-2115. Baumann, R., Heimlicher, S., & Plattner, B. (2008). Routing in large-scale wireless mesh networks using temperature fields. IEEE Network, 22(1), 25-31. Hu, H., Zhang, Y., & Chen H. H. (2008). An effective QoS differentiation scheme for wireless mesh networks. IEEE Network, 22(1), 66-73. Huang, J. H., Wang, L. C., & Chang, C. J. (2008). QoS provisioning in a scalable wireless mesh network for intelligent transportation systems. IEEE Transactions on Vehicular Technology, 57(5), 3121-3135.
24
Lam, R. K., Chiu, D. M., & Lui, J. C. S. (2007). On the access pricing and network scaling issues of wireless mesh networks. IEEE Transactions on Computer, 56(11), 1456-1469. Liu, T., & Liao, W. (2008). Location-Dependent Throughput and Delay in Wireless Mesh Networks. IEEE Transactions on Vehicular Technology, 57(2), 1188-1198. Koksal, C. E., & Balakrishnan, H. (2006). Quality-Aware Routing Metrics for Time-Varying Wireless Mesh Networks. IEEE Journal on Selected Areas in Communications, 24(11), 1984-1994. Park, B. N., Lee, W., Ahn, S., & Ahn, S. (2006). QoS-driven wireless broadband home networking based on multihop wireless mesh networks. IEEE Transactions on Consumer Electronics, 52(4), 1220-1228.
KEY TERMS & DEFINITIONS Network traffic: In telecommunication, network traffic is data in a network. Usually, the data is encapsulated in packets. Effective channel capacity: the effective capacity with violation probability ε of a point-to-point wireless link over a given channel during a time interval is the amount of information that can successfully be transmitted through the wireless link during the time interval with probability larger than 1- ε. Queueing delay: In wireless communications, the queueing delay is the time a packet waits in a transmitter until it has successfully been received by a receiver. It is a key component of wireless network delay. Probabilistic delay bound: A probabilistic delay bound consists of two components, i.e., a delay bound D and a violation probability ε, such that the experienced delay is no larger than D with probability 1-ε. Real-time communications: Real-time communications is any mode of telecommunications in which all users can exchange information instantly or with tolerable latency. Wireless mesh router: It is a combination base station (access point) and router in one device. Also wireless mesh routers are called mesh nodes and typically installed on street light poles, from which they obtain their power. Wireless mesh network: A wireless mesh network is a communications network made up of wireless mesh routers organized in a mesh topology. Moreover, a wireless mesh network can be seen as a type of wireless ad hoc network, where all radio nodes are static and doesn't experience direct mobility.
