Transcript A Hybrid Approach to Effort-Limited Fair (ELF) Scheduling for 802.11

A Hybrid Approach to EffortLimited Fair (ELF) Scheduling for
802.11
By David Matsumoto
June 20th, 2003
Agenda
•
•
•
•
•
•
•
•
Introduction
Effort-Limited Fair (ELF) Scheduling
The Thesis
Integrate ELF into 802.11
Hybridize ELF
Simulation setup & results
Possible future research & recommendations
Conclusion
Introduction
• Applications on a network
– Different requirements
(bandwidth, timing,
reliability)
application
transport
network
data link
physical
• Network stack
– Underlying protocols (TCP,
UDP, IP, MAC, etc…)
• Providing quality of
service (QoS)
– Wired versus wireless
• Wireless: subject to
capacity loss
• “Effort” spent does not
always equal “outcome”
application
transport
network
data link
physical
application
transport
network
data link
physical
Earlier Work: Effort-Limited Fair
(ELF) Scheduling
• Motivation
– Applications have poor performance due to link errors
– Link errors reduce useful link throughput
• Solutions introduced: Swapping time slots, Adaptive forward
error control
• Capacity loss is a fundamental reality for wireless
schedulers.
• Questions
– Can we support reservations amidst capacity loss?
– How should we redistribute the remaining capacity
among flows?
Example: 50% Packet Loss
• Wireless cell capacity: 800 kilobits/second
• WFQ scheduler serves two guaranteed flows &
two best-effort flows
Client
Expected
Rate
(kbit/s)
Effort-fair
Preferable
rate (kbit/s) rate (kbit/s)
Audio
8
4
Video
FTP 1
FTP 2
350
221
221
175
110
110
× 8
√
× 350
21
21
√
Challenges in QoS
• Capacity loss should result in throughput
loss according to administrative controls
• What about location dependent errors?
– How should we regulate air-time?
• Conclusion:
– We must have a way to balance fidelity with
efficiency.
ELF Scheduling – Design Principles
• Wireless scheduler should be equivalent to wireline
•
•
•
•
scheduler in error-free environment
Capacity loss suffered per flow should be
administratively configurable
Administratively bound capacity lost due to locationdependent errors
Unless configured otherwise, flows with the same error
rate should experience the same capacity loss
Capacity unused by one flow should be distributed
“fairly” among other flows
The ELF Scheduler
User
Requests
Administrative
Controls
Application Protocols
Admission Control
Power factors
weights
Packet Scheduler
Effort/outcome
“next packet”
Link Layer
ELF Power factor
• Main Idea:
– Extend transmission time in a controlled fashion
– Allot a flow extra effort to meet its reservations, up to
some administrative bound  Power factor
• Adjusted Weight (Ai)
– Ai = min (Wi/1 – Ei , Pi X Wi)
• Effective throughput (Ti)
– Ti = ((Ai/∑j Aj) X B) x (1 – Ei)
• This effectively balances fidelity with efficiency.
The Thesis
It is possible to integrate an Effort-Limited
Fair scheduler (ELF) into a standard
802.11 implementation, and thus ensure
sensible outcomes for flows in response to
unrecoverable capacity loss.
Moreover, it is possible to improve on the
efficiency of ELF within an 802.11 MAC by
using a hybrid approach to regulate
stations within both a DCF & a PCF.
IEEE 802.11
• Standard for wireless Local Area Networks (LAN)
• Distributed Coordinator Function (DCF)
– Uses Carrier Sense Multiple Access with Collision Avoidance
(CSMA/CA)
• Point Coordinator Function (PCF)
– Centralized, polling-based mechanism requiring a base station
(Point Coordinator)
• DCF & PCF can co-exist
• Contention period (CP) under control of DCF
• Contention-free period (CFP) under control of PCF
• Both methods use explicit Acks
– Useful for PC tracking outcome
802.11 PCF/DCF Alternation
Integration of ELF scheduling into
802.11
• Core ELF algorithm remains the same
– Choose “most deserving” flow
– Flow is allocated effort as a function of its power factor
• Must have “effort” allocated to be chosen
– Separate best-effort flows from guaranteed flows
• Update each flow per clock “tick”
• ELF scheduling becomes the policy for the PCF
– Departs from existing protocol specifications
• Records “outcome” via returned Acks (or NULL frames)
• Charge a station for “effort” each time it is polled.
– Station charged even if packets are corrupted.
Extending ELF for DCF
• Motivation
– DCF is more efficient in general, when traffic load isn’t
high.
– Ideal: PCF could interject only when necessary to
bring flows into conformance with reservations.
• Design Principles
– DCF must remain completely distributed
– ELF-DCF should adhere to original ELF design
principles.
– Integration of ELF-DCF/PCF should be seamless
ELF-DCF: Implementation Design
• Continue using both “deserve”
& “effort” to (self) regulate
flows
• “Deserve” carries over from
CFP
• “Effort” allocated based on
past CP history
– Cannot force station to expend
effort
– Make use of power factor
– “Effort” is conserved (unused
effort plugged into CFP)
• No distinction between best-
effort versus guaranteed flows
– Reduce overhead in beacon
ELF Scheduler
(PC)
Collect
statistics
/Start
CFP
Send
Beacon
with ELF
data
Mobile
Nodes
Implementation for ns-2
• Build on top of CMU Monarch group’s work
– Basic mobile node functionality with 802.11 DCF
• Add semi-complete implementation of PCF.
– Beacon timer
– Bi-directional polling
– Poll list – integrated with ELF
• Implement Weighted Round Robin (WRR) instead of WFQ
– Measure throughput in frame slots (done for simplicity)
– Not concerned with complex based service characterizations (e.g. delay,
jitter guarantees)
• Administratively configure breakdown of superframe
– I.E. Percentage CFP/CP
• Assume admissions control module exists that can set appropriate
per-flow power factors.
Experimental setup
• One flow per station
– Two CBR flows & two FTP flows
(each with 25% weight)
• Flows chosen so aggregate
throughput consumes the entire
link ~ 1.4 Mbit/s
– CBR flow ~ 450 Kbit/s
– FTP flow ~ 250 Kbits/s (no errors)
• Relevant variables:
–
–
–
–
Percentage CFP/CP
ELF-DCF Boolean
Power factor
Error rate
• Error models
– Uniform, Markov, real-world
Traces
WLAN
Uniform – 50% (CBR-1 Error prone)
50% Error rate, 0% CFP, ELF-DCF disabled
Throughput (Mbit/s)
1.4
1.2
CBR(1)
1
CBR(2)
0.8
TCP(3)
0.6
TCP(4)
0.4
Total
0.2
30
27
24
21
18
15
12
9
6
3
0
0
Time (s)
• CBR-1 performs poorly while other stations operate normally
• No ELF intervention here.
Uniform – 50% (CBR-1 Error prone)
50% Error Rate, 100% CFP, ELF-DCF Disabled
Throughput (Mbit/s)
1.4
1.2
CBR(1)
1
CBR(2)
0.8
TCP(3)
0.6
TCP(4)
0.4
Total
0.2
30
27
24
21
18
15
12
9
6
3
0
0
Time (s)
• ELF-PCF effectively restores throughput to CBR-1 at the expense
of best-effort flows
Uniform – 50% (CBR-1 Error prone)
50% Error rate, 50% CFP, ELF-DCF Disabled
Throughput (Mbit/s)
1.4
1.2
CBR(1)
1
CBR(2)
0.8
TCP(3)
0.6
TCP(4)
0.4
Total
0.2
30
27
24
21
18
15
12
9
6
3
0
0
Time (s)
• ELF-PCF is only partially effective at restoring throughput
Uniform – 50% (CBR-1 Error prone)
50% Error rate, 50% CFP, ELF-DCF Enabled
Throughput (Mbit/s)
1.2
1
CBR(1)
0.8
CBR(2)
0.6
TCP(3)
0.4
TCP(4)
Total
0.2
30
27
24
21
18
15
12
9
6
3
0
0
Time (s)
• ELF-DCF effectively works with ELF-PCF to meet ELF design principles
Walls trace – (CBR-1 Error prone)
1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
0
CBR(1)
CBR(2)
TCP(3)
TCP(4)
30
27
24
21
18
15
12
9
6
Total
3
0
Throughput (Mbit/s)
Wall - 0% PCF, ELF-DCF Disabled
Time (s)
• No ELF intervention – other flows gain throughput as CBR-1 decreases
Walls trace – (CBR-1 Error prone)
Walls - 50% PCF, ELF-DCF Enabled
Throughput (Mbit/s)
1.4
1.2
CBR(1)
1
CBR(2)
0.8
TCP(3)
0.6
TCP(4)
0.4
Total
0.2
30
27
24
21
18
15
12
9
6
3
0
0
Time (s)
• ELF-PCF/DCF work together
• Other flows share throughput loss, up to administrative bound
• Capping (“deserve”) mechanism needed
Future Work & Recommendations
• Future work
– Provide a capping mechanism for flows that
accumulate large “deserve” values
– Can we “encourage” stations to spend effort during a
DCF (rather than just limiting the effort allotted)?
• Recommendations
– Incorporate a “policing” mechanism into beacons
– Change 802.11 specifications on how stations are
polled
– Allow polling of individual flows
Conclusions
• ELF scheduling can be implemented as the
policy for a PCF in 802.11
• ELF-DCF/PCF provides a hybrid
mechanism through we can achieve ELF’s
design principles
Acknowledgements
• Peter Steenkiste – Advisor
• David Eckhardt – Reader
• INI Staff & Professors
Questions