Transcript Guerin-Wireless

Investigating Wireless Systems
Two Case Studies
Roch Guerin
University of Pennsylvania
Starting Point
• Wireless means no wire…
– Flexibility in using and allocating spectrum resources
• No wire means lots of unpredictable interactions
– User interferences, fluctuations in channel quality, e.g.,
fading, etc.
• What is the trade-off between flexibility and
predictability?
– A common theme at the “physical layer” (MIMO,
OFDM, etc.)
– But how does it play out at the link/network layer?
2
Broad Problem Setting
• Multiple distinct channels, e.g., different frequencies,
spreading codes, etc.
• One or more user seeks to transmit data
• How should data be transmitted to maximize “performance?”
– Which user transmits when on what channel
– What definition for performance (system centric versus user centric)
• Performance factors
–
–
–
–
–
Channel quality
Channel access schemes
Channel allocation and packet transmission strategies
User traffic patterns
User level coding for resiliency
3
Not an Easy Problem in General…
• M users and C (slotted) channels
– An idle user becomes active with probability p and
remains active for k1 slots
– Users can direct any transmission to any channel (no
channel switching cost)
– Basic slotted Aloha MAC and error-free channels
• What’s the best assignment of users to channels
– If CM, then obviously one user per channel is best
– If CM, the answer depends on p and k
– Analysis is possible based on standard Markov chain
formulation
• Nothing sophisticated, but complex state enumeration and
bookkeeping
4
Impact of Channel Allocation (k=1)
(M,C)
M =2
M
(4,2)
(6,3)
(8,4)
(16,8)
Throughput
(2,1)
M =32
Sharing pays only at
high loads
(32,16)
Load
5
Our Focus
• Two case studies within the broad framework we just
outlined
• Case study 1: Controlled diversity
– Channels: Variable quality with known open-loop “statistics”
– Channel access: No interferences/collisions between users
– Performance goals: Coding and transmission policies to improve
individual user throughput
• Case study 2: Distributed diversity
– Channels: Variable quality with closed control loop to equalize
channels across users
– Channel access: A CDMA setting with “controlled” interferences
between users
– Performance goals: Transmission policies that optimize trade-off
between system throughput and transmission flexibility of
individual users
6
Generic Outline for Both Case Studies
• Problem justification
– Why someone else should care about it…
• Problem formulation
– What parameters
• Prior work
– What others have done
• Problem solution
– What analytical tools and techniques
• Solution evaluation
– Methodology and scope
7
Our Focus
• Two case studies within the broad framework we just
outlined
• Case study 1: Controlled diversity
– Channels: Variable quality with known open-loop “statistics”
– Channel access: No interferences/collisions between users
– Performance goals: Coding and transmission policies to improve
individual user throughput
• Case study 2: Distributed diversity
– Channels: Variable quality with closed control loop to equalize
channels across users
– Channel access: A CDMA setting with “controlled” interferences
between users
– Performance goals: Transmission policies that optimize trade-off
between system throughput and transmission flexibility of
individual users
8
Case Study 1
• Should I do this?
• Or that?
• And if that, how and when?
9
Why the Question?
• Mobile devices are increasingly powerful
– They run pretty much the same range of applications as
wired devices
– Many of these applications are performance sensitive
• Wireless resources are subjected to random
fluctuations in quality that are outside the control
of users and network providers alike
• So it’s worth exploring what we can do to make
performance more predictable to users in spite of
our limited control on the resources they access
10
Why the Approach?
• Spreading transmissions across multiple channels
allows us to
– Avoid being stuck with a really bad channel
– Decrease the effective length of error bursts, which can
facilitate recovery (fewer consecutive lost packets)
• Potential for improvements, therefore, arises from
– A higher probability of successful message transmission
– The ability to lower coding overhead
• The questions are then how to realize the best
possible improvement, and how big it is
11
System Overview
• One user, C channels (remember perfect channel access…)
– User wants to transmit messages (data blocks) of size k packets
• Channel model is “known” – e.g., Gilbert-Elliot model
– Independent channels with known statistics
• Reliable transmissions through packet-level code
– Add redundant packets to achieve target probability of successful
message delivery Pmin
• Policy distributes packet transmissions across channels
– Deterministic and probabilistic policies
– No channel switching overhead
• Performance measure: Effective Rate (ER)
– Number of messages successfully delivered per unit of time (unit
of time is packet transmission time)
12
Channel Model
• Two-state Markov chain with Good and Bad states
– Packets are lost when channel is in bad state
Pe
– Long-term error rate LTER 
1  Pe  Pb
1
EBL

– Expected burst length
1  Pb
• More complex channel models can be constructed using
higher order Markov chains
– Increased computational complexity (of transmission policies)
Pe
1-Pe
G
1-Pb
B
Pb
13
Transmission Model
• Fixed size message consisting of k packets
• Messages sent using (N,k) diversity code
– Corrects all patterns of i  N-k erasures
(erroneous or lost packets)
– N ≥ k is chosen to realize Pmin
• Policy A selects channel for each packet
transmission
14
Transmission Policies
• Probabilistic policies
– Before each packet transmission select channel
i, 1i C, with probability pi
– Policy specified by p = [p1 p2 … pC]
• Deterministic policies
– For N-packet messages, pre-determine the
channel ci that packet i, 1i N, is to be sent on
– Schedule S=[c1, c2,…,cN] specifies policy
15
Performance Metric
• Identify policy A and code length N that maximize
A
k  Psucc
(N, k)
ERA ( N , k ) 
N
A
P
where succ ( N , k ) is the probability of successful
message transmission given N and A, and N is the
smallest value that satisfies Pmin
• For two policies A and B, the relative gain in ER
of using B over A is given by
ERB ( N B , k B )  ERA ( N A , k A )
GER ( A, B) 
ERA ( N A , k A )
16
Related Works
1.
2.
3.
4.
5.
6.
L. Golubchik, J. C. Lui, T. Tung, A.L. Chow, W.-J. Lee, G. Franceschinis,
and C.Anglano, “Multi-path continuous media streaming: What are the
benefits?” Performance Evaluation, Vol. 39, Sept. 2002.
A. Tsirigos and Z. Haas, “Analysis of multipath routing-Part I: The effect
on the packet delivery ratio.” IEEE Trans. Wireless Commun., Vol. 3, No.
1, Jan. 2004.
B. Abdouni, W. Cheng, A. L. Chow, L. Golubchik, W.-J. Lee, and J. C. Lui,
“Multi-path streaming: Optimization and evaluation.” Proc. MMCN'05,
San Jose, CA, Jan. 2005.
E. Vergetis, R.Guerin, and S. Sarkar, “Improving performance through
channel diversity in the presence of bursty losses.” Proc. ITC 19, Beijing,
China, Aug. 2005.
E. Vergetis, R. Guerin, and S. Sarkar, “Realizing the benefits of user-level
channel diversity.” ACM Computer Communication Review, Vol. 35, No. 5,
Oct. 2005.
E. Vergetis, E. Pierce, M. Blanco, and R. Guerin, “Packet-Level Diversity:
From Theory to Practice. An 802.11-based Experimental Investigation.”
Proc. ACM MOBICOM 2006, Los Angeles, CA, Sept. 2006.
17
Identifying Optimal Policies
Probabilistic Policies
• Calculate PAsucc(N,k) given
the channel characteristics
– Recursive solution
– 4-state Markov Chain for
two independent GE
channels
– For C independent
channels, you end-up with a
Markov chain with 2C states
• Search through all policies to
find optimal selection
Deterministic Policies
• Deterministic schedule allows
each channel to be viewed
independently
– Compute statistics of the
associated embedded Markov
chains (one for each channel)
• Total number of errors is sum of
independent random variables
(number of errors when using
each channel)
– Use convolution to compute
overall probability of success
• Search through all policies to
find optimal selection
18
Probabilistic Policies
Two Independent GE Channels
• Two GE channels give rise to
a 4-state Markov Chain
– Denote the stationary
probability of state i as i
A
• Let Pij (m, n) be the
conditional probability of m
errors in n transmissions
under policy A, given that the
initial channel state was i and
the ending state was j
N k 4
A
succ
• We then have P
4
N , k    P
m 0 i 1 j 1
A
i ij
(m, N )
19
Recursive Computation Procedure
• For all n = 0,1,… and m = 0,1,…,n and for all
i,j{1,2,3,4}, we have
4
PijA (m, n)   PikA (m, n  1)  Pkj  P A{no error state is j}
k 1
4
  PikA (m  1, n  1)  Pkj  P A{error state is j} ,
k 1
where Pkj is the transition probability from state k to state j
• Initial conditions are defined as
PijA (0,0)  1 if i  j , and 0 otherwise;
PijA (m, n)  0 for all m  n and m  0 .
20
Deterministic Policies
• For each of the N packets, specify the channel used
– There are CN such policies…
• Focus on round-robin policy
– Maximizes return time to channel, i.e., every C slots.


C  step
e
Pe

1  ( Pb  Pe )C
1  Pb  Pe
C  step
b
1  Pb
 1
1  ( Pb  Pe )C
1  Pb  Pe
P
P


• Let vi be the number of errors when using channel i
– Distribution of vi is easy to calculate via a recursion
• Use convolution to calculate the distribution of
V= v1 + v2 + …+ vC and the performance of any (N,k) code.
21
Computational Challenges
• We have computational procedures to explore the space of
possible policies, but while identifying optimal policies is
feasible, it can be complex
• No computationally tractable “closed-form” solutions
– Caused in part by the discrete nature of the problem
– No consistent behavior of optimal policy
• Identical channels need not be used equally
• Bernoulli channels not always preferred over burstier channels
• More channels does not always improve performance
• What do we do next?
– Look for “heuristics” to identify what policies are good, when
22
Methodology and Results Summary
• Step 1: Initial information gathering
– Evaluate a broad range of channel combinations
• When does using multiple channels help?
• Common characteristics of the optimum policy?
• Step 2: Data analysis and further evaluation
– Most scenarios that yield “meaningful” (≥ 30%)
improvements use all channels roughly equally
– What channel combinations give rise to such behavior?
• Concept of equivalent channels
• Step 3: Distilling a simple heuristic to quickly
– Identify when and how using multiple channels helps
23
Step 1
• All possible 1540
channel pairs between
55 different channels
– LTER  [1%, 9%]
– EBL  [1.01, 20] pkts
• Different
combinations of
values for k and Pmin
• Initial findings
– Max. benefits when
channels are used
roughly equally
– Necessary but not
sufficient
24
The Cost of Using Channels Equally
• Define the loss in performance gain as
L = Gopt – Gequal
Average
1.28%
Std. Deviation 2.71%
Minimum
0.00%
Maximum
Median
L  5%
15.72%
0.03%
81.62% of cases
L  10%
L  15%
L  20%
98.77% of cases
99.04% of cases
100% of cases
25
A Different Look at the Data
26
Equal Channel Use
Focus on Deterministic Policies
Easier and better
27
Step 2
• Understanding when channels are used equally
– Holds for identical channels in most settings
– Any other scenarios?
• Classifying channel combinations
– Channels are used equally under the optimal policy
– Channels have identical individual performance (ER)
– Channels yield the highest gain when used together
• Simple test to identify “good” combinations
– All three above perspectives give similar answers
 Look for combinations of channels with similar
performance
28
“Equivalent” Channels – (1)
29
“Equivalent” Channels – (2)
• Optimal policy remains close to 0.5 for “equivalent” channels
30
Step 3 - Simple Heuristic
Given C channels
• Identify subsets of ~ equivalent channels
– Compute ERi, for each channel i, 1  i  C
– Group channels into |E| “equivalence classes”
• For each equivalence class eE with ne channels
(e)
– Compute ERequal
achieved by cycling through all channels
– If
(e)
ERequal
 max ( ERi )
1i  ne
max ( ERi )
1i  ne
– Else use channel  ( e )
– Set
ER
(e)
  , use all channels
 argmax ( ERi )
1i  ne
(e)
equal
 (e)
 max( ER
, ER
)
• Pick equivalence class eˆ  argmax ( ER (e ) )
e
31
Exploring Further When Using
Multiple Channels Helps
•
Three parameters of interest:
1. Channel characteristics, i.e., EBL and LTER
2. Performance target Pmin
3. Number of channels available
•
Focus on the case of two identical channels
32
Impact of Channel
• The gain is biggest for bad channels
33
Impact of Pmin
• The more
stringent the
performance,
the greater the
gains
• Relative
burstiness of
channel plays
a major role
Large gains until
relative burst size
decreases N 
Rapid transition
to 50/50 policy
No gain
34
Impact of Number of Channels
Biggest bang for the buck
with just a few channels
35
Shifting Focus
•
Better performance is great, but
–
How robust are the improvements?
•
–
•
Are we optimizing ourselves into a corner?
Explore sensitivity to errors in channel estimates
–
Different channel statistics
•
•
•
Sensitivity to measurement inaccuracies, non-stationary
channels, etc.
EBL and LTER
Distribution of duration of error bursts (not a GE channel!)
Can we trade-off optimality for robustness of
solution
–
Already do this to some extend with round-robin
policy
36
Sensitivity to Channel Quality
• Three users, three channels
– Two scenarios: (1) each user is assigned one channel; (2) all three users
share the three channels
– Both EBL and LTER are progressively made worse
• First on only one channel (left), then on all three channels (right)
• Better performance also comes with mostly greater robustness!
– Exception in the single bad channel case, when both EBL and LTER are
over 40% worse
37
Performance vs. Robustness (1)
• Explore trade-off by varying the code length N
– Bigger N  greater robustness, but lower performance gain
– Initial focus on basic channel statistics (LTER and EBL)
System
One channel (N=19)
Performance gain over Increase in both LTER and EBL
the one channel system before target Pmin is violated
0%
2%
Three channels (N=15)
27.6%
16%
Three channels (N=16)
20.7%
37%
Three channels (N=17)
14.2%
63%
Three channels (N=18)
8.2%
92%
Three channels (N=19)
2.7%
> 100%
38
Performance vs. Robustness (2)
• This time we vary the channel model (target Pmin=0.97)
– Ever burstier channel (variance of error burst )
One channel
Variance
Multiplier
Three channels
N = 19
N = 15
N = 16
N = 19
ER
Psucc
ER
Psucc
ER
Psucc
ER
Psucc
Original
1.534
0.971
1.956
0.978
1.850
0.987
1.574
0.997
x 0.25
1.555
0.985
1.947
0.973
1.840
0.982
1.574
0.997
x 0.5
1.547
0.980
1.942
0.971
1.837
0.980
1.568
0.993
x1
1.538
0.974
0
0.968
1.83
0.976
1.562
0.989
x2
0
0.963
0
0.962
0
0.968
1.552
0.986
x4
0
0.961
0
0.949
0
0.957
1.538
0.974
x8
0
0.953
0
0.941
0
0.949
0
0.966
39
Resting on our Laurels – Or Not?
• Theory tells us that we can have our cake and eat it!
– Both better and more robust performance
• But the theory is rife with holes and assumptions
– Independent, stationary channels, with known statistics
– No impact of user transmissions on channel statistics
– No channel switching overhead
• Putting it all to the harsh test of reality
– 802.11b environment
– Standard end-systems (PCs) without precise control of
transmission timings
– If it survives “that” then maybe there is some hope…
40
Surviving 802.11
• Performance is all over the place…
• There is no “average” 802.11 channel
– Stationary GE model not particularly accurate
– Significant time-of-day and location dependent variations
• Wild fluctuation across 10 minute intervals
– LTER can range from 0.01% to 70%
– EBL varies between 1 and 40 packets
• Actual error bursts between 1 and several hundred packets
• Similar observations made by others
• Does not bode too well for the “survival” of our theory
– Nevertheless
41
Experimental Setup
• Two 802.11b Access Points (APs)
–
–
–
–
–
–
Intel StarEast board, with one miniPCI NIC each
External omni-directional antennas
Assigned “non-overlapping” frequency bands
Located ~1m from each other
Transparent logging of all incoming packets on both systems
Within reach of other APs interfering in all 11 frequency bands
• Sender
– Standard laptop with two NICs
• One external PCMCIA NIC, and one internal miniPCI NIC
• Linux operating system
• Transmission speed set at 2Mbps
– Located between 2m and 10m away from the two APs
• Maintains association with both APs
• Line-of-sight (LoS) as well as non-LoS (indoor wall) transmissions
42
Some Other Implementation Issues
• Impact of 802.11 operation
– RTS/CTS handshake before transmissions
[Disabled - Large RTSThreshold value]
– “Feedback” mechanism: ACK packets
[Disabled - Broadcast packets ]
– Channel access control (untouched)
• Sensing and exponential backoff
• Inter-frame spaces (SIFS, DIFS, etc.)
• Processor and OS overhead vs. transmission
speed of the NICs
– Where is the bottleneck and how does it affect
transmission timings?
43
Transmission Timing Scenarios
• Single channel
NIC1
1
2
3
4
5
6
7
8
(S0)
• Interleaving on one
channel
NIC1
1
1’
2
2’
3
3’
4
4’
(S1)
• Perfect timing on two
channels
NIC1
1
3
2
NIC2
• Bandwidth limited on
two channels
NIC1
NIC2
1
2
• Processor limited on
two channels
NIC1
1
• Interleaving on two
bandwidth limited
channels
NIC1
4
3
4
5
6
6
2’
2
8
(S3)
(S4)
5
4
3
3’
(S2)
7
8
2
1
1’
7
3
NIC2
NIC2
5
4’
4
5
5’
6
6’
6
7
7’
8’
8
44
(S5)
Experimental Evaluation
• Generate extensive sets of traces
– “Continuous” transmissions on both NICs
• Traces of received packets (1,000 bytes) recorded at each AP
– Different configurations
• Sender location, time-of-day, selection of frequency bands
– With and without interferer in “intermediate” band
• Test for channel correlation
• Post-process traces to emulate different settings
– Different combinations of system parameters: N, k, Pmin
– Various packet inter-leaving strategies, transmission
timing policies, channel switching overhead, etc.
45
The Net of It
(see MOBICOM Paper for Details)
• Generic findings
– Channel correlation was not found to be a major issue, at least
when using non-overlapping channels
– Precise timing of transmissions does not appear to have a major
impact on performance
– With current technology, dynamic channel switching mandates the
use of multiple radio cards
• Cannot compensate for it through smart scheduling
• Performance/robustness findings
– Some benefits remain in spite of 802.11 channel “characteristics”
IF channel characteristics are known
• Unlikely to be of much use in practice given the erratic nature of the
802.11channel
– For unknown channels, meaningful benefits remain ONLY when
some of the channels are really bad
• Benefits are more as a performance stabilizer than an enhancer
46
Stabilizing Performance
• Two channels:
– LTER1 ~ 11.4%
– EBL1 ~ 10 pkts
– LTER2 ~ 29.2%
– EBL2 ~ 11 pkts
• Measure ER over a
200 messages sliding
window
– Mean value improves
by 6%/30%
– Variance decreases by
60%/90%
Channels 1+2
47
Wrapping Up Case Study 1
• When and how can using multiple wireless channels be of
benefit?
– Assumed no user interference (centralized control) and no channel
feedback (open-loop)
– Relied on packet-level diversity coding
– Ignored overhead in changing channel
• Analytical tools
– Basic Markov chain analysis (stationary probabilities, recursions)
– Elementary probability (convolution, etc.)
• Main results
– Cycling in a round-robin manner across channels is close to being
optimal in most cases
– Better performance is reasonably robust to errors in assumptions
– Even when most of the above assumptions don’t hold, e.g., 802.11,
there are advantages to spreading transmissions across channels
48
Our Focus
• Two case studies within the broad framework we just
outlined
• Case study 1: Controlled diversity
– Channels: Variable quality with known open-loop “statistics”
– Channel access: No interferences/collisions between users
– Performance goals: Coding and transmission policies to improve
individual user throughput
• Case study 2: Distributed diversity
– Channels: Variable quality with closed control loop to equalize
channels across users
– Channel access: A CDMA setting with “controlled” interferences
between users
– Performance goals: Transmission policies that optimize trade-off
between system throughput and transmission flexibility of
individual users
49
Case Study 2
• What is the cost of
going from this?
• To that?
• And what’s the
best trade-off?
50
Why the Question?
• Mobile devices are increasingly powerful
– They run pretty much the same range of applications as wired
devices
– These applications exhibit a broad range of resources and
performance requirements
• Tight centralized control can optimize overall system
performance, but may be a very poor match to individual
user needs
• So it’s worth exploring the trade-off associated with giving
user more independence in their transmission decisions
and the impact this has on overall system throughput
51
System Overview
Base Station
Internet
Gateway
Internet
Base Station
Controller
Mobile
Switching
Center
Telephone
Network
52
Our Focus
53
Overview of CDMA Uplink
• CDMA uplink is interference limited
– Each user has a spreading “orthogonal” code
• Allows simultaneous transmissions
• However, users interfere due to multi-path effects
• Users can select among multiple (discrete)
transmission rates
– Control loop based on pilot signal equalizes channel
among users
– Transmitted power is proportional to pilot strength
AND selected rate
54
Uplink Operation
• Pilot Pi transmitted by device i=1,...,n+1
– Pilot signals are power controlled by BS to all be received
with the same target SINR 1/Ф
i
2
Gloss
Pi
1

i
 2

G
, i  1, , n  1
loss Pi   
j
    Pilot  Gloss Pj
  n Pilot
j i
• Giloss : Path loss; θPilot: Orthogonality factor; σ2 : Noise
• User i transmit power = Pi · TxT2P[R]
– R : Target data rate from discrete set 
– TxT2P[R] : Proportionality factor relative to Pilot
• User spends TxT2P[R] power tokens to transmit at rate R
55
Sample TxT2P[R] Values
Target Data Rate
TxT2P[R] dB
0
-∞
9.6 kbps
4.5
19.2 kbps
6.75
38.4 kbps
9.75
76.8 kbps
13.25
153.6 kbps
18.5
56
CDMA Uplink Interference Model
i
G ( Ri )  Gloss
 PDi ( Ri )
SINRi ( Ri )  2
, : Data orthogonal ity factor
j
j
    Gloss  PD ( R j )
j i
W
G ( Ri )  : Processing Gain and PDi ( Ri )  Pi  TxT 2 P[ Ri ]
Ri
G ( Ri )  TxT 2 P[ Ri ]  
2
 SINRi ( Ri )  2
, 
    TxT 2 P[ R j ]  
  n Pilot
j i
• Interferences from other users
– The higher the rate a user chooses, the more
interference it creates!
No Channel Effects
(Perfect Power Control)
57
Our Problem
G( Ri )  TxT 2 P[ Ri ]  
SINRi ( Ri )  2
, i  1,, n  1
    TxT 2P[ R j ]  
j i
• Users make independent transmission and rate selection
decisions
– Greedy behavior by individual users can affect overall
performance
• What guidelines to mitigate negative impact of
independent decisions
58
Related Works
7.
8.
9.
10.
11.
12.
K. Kumaran, L. Qian, “Uplink Scheduling in CDMA Packet-Data
Systems.” Proc. INFOCOM 2003, San Francisco, CA, April 2003.
R. Cruz, A. Santhanam, “Optimal Routing, Link Scheduling and
Power Control in Multi-Hop Wireless Networks.” Proc. INFOCOM
2003 , San Francisco, CA, April 2003.
P. Venkitasubramaniam, S. Adireddy, and L. Tong, “Opportunistic
ALOHA and cross-layer design in sensor networks.” Proc. IEEE
MILCOM, Boston, MA, October 2003.
P. Venkitasubramaniam, Q. Zhao, and L. Tong, “Sensor networks with
multiple mobile access points.” Proc. 38th Annual Conference on
Information Systems and Sciences, Princeton, NJ, March 2004.
X. Qin and R. A. Berry, “Distributed approaches for exploiting
multiuser diversity in wireless networks.” Trans. Infor. Theory, vol.
52, no. 2, pp. 392-413, February 2006.
A. Sridharan, R. Subbaraman, and R. Guerin, “Distributed Uplink
Scheduling in CDMA Networks.” Proc. Networking'2007, Atlanta,
GA, May 2007. (Extended version – Sprint Research Report).
59
Our Initial Model
• Homogenous, unconstrained users
– All users (n+1 users in a sector) employ the same policy
– Users always have data and are able to transmit whenever the
policy schedules a transmission
• Probabilistic On-Off transmission policy
– Transmit at rate R in a slot with probability p
• Transmit power is therefore 0 with probability 1-p and
~TxT2P[R] with probability p
• Simple but useful model
– Similar to Aloha
– But with a contention model based on soft interferences (CDMA)
rather than “collisions”
• Questions
– At what rate R should a user transmit?
– How often (what p value) should a user transmit?
60
Revisiting our CDMA Uplink Model
G( Ri )  K i  
, K i  TxT 2 P[ Ri ]
• We have SINRi ( Ri )  2
    Ki  
j i
 SINRi ( Ri )  ˆ
• Achieved rate Ci  min  Ri ,
Ri , C ( p)  E[Ci ]
S0


• On-Off policy with parameters R and p
n
  n Pilot
Wp
1  n j
n i
ˆ
  p (1  p) ,  
 C ( p) 

S0 j 0 j    j 
K
where for simplicity we have assumed SINRi(R)S0
(more on this later)
61
Rate-SINR Model
Achieved Rate
No matter how good the channel, you
cannot get more bits out than you put in…
Linear Model
Ri
Bounded Model
S0
SINR
62
Main Results
• There exists an optimal p* (maximizes Cˆ ( p))
  n Pilot
– If   1 then p*=1

*
– If  < 1 then p < 1
 K
– In both cases p* satisfies the following equality
n
1  n j
1
n j
  p * (1  p*) 

(n  1) p * 1  
j 0 j    j 
– With few (many) users, and/or low (high) target rate R,
users should transmit (in)frequently
• Higher target rates always achieve higher
throughput, i.e., Cˆ ( p1* , R1 )  Cˆ ( p2* , R2 ), if R1  R2
– In the absence of other constraints
63
Impact of 
64
Hybrid Slotted/CDMA
65
Distributed Control
• Token bucket mechanism available in EV-DO
Rev. A and HSUPA to “control” device
transmissions
– Token bucket depth  and token fill rate  are
controlled by Base Station
– A device needs TxT2P[R] tokens to transmit at rate R
– Aimed at limiting peak and average power to satisfy
fairness and QoS constraints
• Question: How does the presence of a token
bucket affect the choice of “good” transmission
decisions by devices?
66
Accounting for Token Buckets
•
Given a token bucket configuration (,)
– What are the optimal p* and K values?
•
Two-step formulation
1. Account for impact of token bucket on transmission
decisions
•
Transmissions conditioned on having at least K tokens
2. Explore possible combinations of p and K values
– Note that optimality of higher rates need not hold any more
because of token constraints (token efficiency)
67
Token Efficiency
• With 24 users
transmission at
153.6kbps yields a
higher throughput
but a lower token
efficiency than
transmission at
76.8kbps
68
Impact of Token Bucket
Token Bucket parameters:
σ = 21.5dB;  = 7dB
More frequent transmissions at
76.8kbps yield a better throughput
because of higher token efficiency
Conditional Transmission Probability
69
Token Bucket Formulation
• Let p and ptok denote conditional and unconditional
transmission probabilities
– Token bucket evolution governed by simple Markov chain
1
1
0
1
p
1-p
K
K+1
p
1-p
1-p
1-p
σ-K
σ
1-p
p
 K 1 
– So that ptok  p  1    i ,0  ptok  1
 i 1 
• Optimal (K,p*) value satisfies non-linear program N1
N
W
1 n j
ˆ
ˆ
  ptok (1  ptok ) n  j
max C ( p, K ), where C ( p, K ) 
ptok 
p,K
S0
j 1 j    j 
70
Solving Program N1
• Step 1: For each value of K, solve the unconstrained
problem, i.e., look for actual transmission probability
pu*(K) that maximizes throughput
– Solved based on value of δ and fact that
1  n j
1
n j


p * (1  p*) 



(n  1) p * 1  
j 0 j    j 
• Step 2: For each value of K compute p*(K) that satisfies
 K 1 
*
p * ( K )  arg min pu ( K )  p( K )  1    i 
p
 i 1 
• Step 3: Choose the pair (K,p*(K)) that yields the largest
throughput
n
71
Analysis vs. Reality
Token Bucket: σ = 21.5dB;  = 7dB
Rate
(kbps)
Analysis
p *A
C*A
Simulations
(bounded rate model)
p*sim
C*sim Csim(p*A)
76.8
1.0
26.4
0.35
17.84
16.56
153.6
0.21
42.9
0.25
10.63
10.59
• Expected inaccuracies because of bounded rate
– But actual impact on throughput is small
72
Related Results and Extensions
• Recent results
– Similar results also hold for the bounded rate model
– Characterized optimum centralized schedule
• A benchmark against to compare distributed policies
• A combinatorial problem because of discrete rate values
• Extensions
– Investigating the impact/use of token bucket for its
“original” purpose, namely, service differentiation
• Rate vs. delay performance targets
73
Summarizing Case Study 2
• What is the impact on the throughput of CDMA uplinks of
uncoordinated user transmissions?
– Used simple probabilistic policies to probe the effect of distributed
transmission decision
– Extended the investigation to account for the effect for token
constraints imposed by the base station to “control” device
transmissions
• Analytical tools
– Algebraic manipulations and basic real analysis
– Optimization techniques and Markov chains
• Main results
– Identified optimal transmission strategy function of system load
– Results also hold in more realistic setting of bounded rate model
74