Transcript PPT

Special Topics
on
Wireless Ad-hoc Networks
Lecture 11: Quality of Services on
Wireless Networks
University of Tehran
Dept. of EE and Computer Engineering
By:
Univ. of Tehran
Wireless Ad hoc
Dr. Nasser
Yazdani
NetworkingWireless Ad Hoc
Networks
1
Covered topics


How to support real-time applications on
wireless network?
References


Chapter 6 of the book
“Protection and Guarantee for Voice and
Video Traffic in IEEE 802.11e Wireless
LANs” by Yang Xiao, Haizhon Li and
Sunghyun Choi.
Univ. of Tehran
Wireless Ad hoc Networking
2
Outline


Quality of Service
QoS on IP networks:





Integrated Services
Differentiated Services
QoS on Wireless Link
QoS Routing
Cross layer Design
Univ. of Tehran
Wireless Ad hoc Networking
3
What is QoS?


Many views. User Satisfaction, etc.
Some applications require “deliver on time”
assurances
 must come from inside the network
Microphone
,
Sampler
,
Buffer
A D
converter
D
A
Speaker

Example application (audio)



sample voice once every 125us
each sample has a playback time
packets experience variable delay in network
Univ. of Tehran
Wireless Ad hoc Networking
4
Applications?

Elastic (delay-tolerant)



Non-elastic (Real-Time)


Needs some kind of guarantee from network
Main Question? How guarantee Delay and losses



Tolerate delays and losses
Can adapt to congestion
End to End, is it enough?
In the Network
QoS Parameters
Bandwidth
 Latency
 Jitter
of Tehran
 Univ.
Loss

Wireless Ad hoc Networking
5
Utility Curve Shapes
U
U
Elastic
BW
U
Hard real-time
BW
Delay-adaptive
BW
Univ. of Tehran
Wireless Ad hoc Networking
6
General view

QoS depends on all layers.


Cross layer problem?
It is a hard problem

It needs some kind of state maintenance in
contrast to IP design philosophy.
Univ. of Tehran
Wireless Ad hoc Networking
7
What we should do?


Maximize User Satisfaction (U)
Mechanism?


Best effort is not enough
Isolate traffics and flows



Active queue management
Policing
Say no for some traffics

Admission control
Univ. of Tehran
Wireless Ad hoc Networking
8
Two Broad Approach
Integrated Services
Differentiated Services
Univ. of Tehran
Wireless Ad hoc Networking
9
Integrated Service

Enhancing IP Service Model



Add QoS service classes
Explicit resource management at IP level
Per flow state maintained at routers which is



used for admission control and scheduling
set up by signaling protocol, users explicitly
request their needs.
This is done with RSVP protocol
Univ. of Tehran
Wireless Ad hoc Networking
10
Integrated Services Example

Achieve per-flow bandwidth and delay
guarantees

Sender
Example: guarantee 1MBps and < 100 ms delay to a
flow
Path RSVP Message
Receiver
Univ. of Tehran
Wireless Ad hoc Networking
11
Integrated Services Example

Allocate resources - perform per-flow
admission control
Receiver
Sender
Univ. of Tehran
RESV RSVP Message
Wireless Ad hoc Networking
12
Integrated Services Example

Install per-flow state
Receiver
Sender
Univ. of Tehran
Wireless Ad hoc Networking
13
Integrated Services Example

Install per flow state
Sender
Univ. of Tehran
RESV RSVP Message
Wireless Ad hoc Networking
Receiver
14
Integrated Services : Data Path

Per-flow classification
Receiver
Sender
Univ. of Tehran
Wireless Ad hoc Networking
15
Integrated Services : Data Path

Per-flow buffer management
Receiver
Sender
Univ. of Tehran
Wireless Ad hoc Networking
16
Integrated Services Example
• Per-flow scheduling
Receiver
Sender
Univ. of Tehran
Wireless Ad hoc Networking
17
Service Types


Multiple service classes
Service can be viewed as a contract between
network and communication client



end-to-end service
other service scopes possible
Three defined services
Best-Effort for (best-effort or elastic)
 Guaranteed Service for hard real-time (“RealTime applications”)
 Controlled Load for soft real-time (“tolerant”
Univ. of Tehran
Wireless Ad hoc Networking
applications)

18
Flowspec

Rspec: describes service requested from network



controlled-load: none
guaranteed: delay target
Tspec: describes flow’s traffic characteristics








average bandwidth + burstiness: token bucket filter
token rate r
bucket depth B
must have a token to send a byte
must have n tokens to send n bytes
start with no tokens
accumulate tokens at rate of r per second
can accumulate no more than B tokens
Univ. of Tehran
Wireless Ad hoc Networking
19
Per-Router Mechanisms

Admission Control




decide if a new flow can be supported
answer depends on service class and policy
not the same as policing
Packet Processing


classification: associate each packet with the
appropriate reservation
scheduling: manage queues so each packet
receives the requested service
Univ. of Tehran
Wireless Ad hoc Networking
20
What is the Problem?

Intserv can support QoS, but


Too complex
Not scalable




Queuing & scheduling
Classification speed
Hardware Restriction
DiffServ aims at providing QoS with simple
mechanisms so that it scales and can be deployed.


push the complexity to the “edges” of the network.
Provide weaker guarantee
Univ. of Tehran
Wireless Ad hoc Networking
21
DiffServ Architecture

Ingress routers (Edge Routers)



Perform per aggregate shaping or policing (Behavior Aggregate)
Mark packets with Code Points, each CP represent a Class of Service
(DSCP DiffServ Code Point)
Core routers


Implement Per Hop Behavior (PHB) for each DSCP
Process packets based on DSCP
DS-2
DS-1
Ingress
Ingress
Egress
Edge router
Univ. of Tehran
Egress
Core router
Wireless Ad hoc Networking
22
Differentiated Service (DS)
Field
0
5 6 7
DS Field
0
4
Version HLen
8
16
TOS
Identification
TTL
19
31
Length
Flags
Fragment offset
Protocol
Header checksum
Source address
Destination address
IP
header
Data
DS filed reuse the first 6 bits from the former
Type of Service (TOS) byte
 The other two bits are proposed to be used
Univ. of Tehran
Wireless Ad hoc Networking
by ECN

23
Per Hop Behavior (PHB)
Define behavior of individual routers
rather than end-to-end services
 Two PHBs

Assured Forwarding (AF, A type)
 Expedited Forwarding (EF, P type)
 Plus, best-effort service!

Univ. of Tehran
Wireless Ad hoc Networking
24
DiffServ Implementations

Two important proposals




RIO Mechanism (1 service)
The Scalable Share Differentiation
architecture (SSD)
Two-Bit architecture
RFC (2475)
Univ. of Tehran
Wireless Ad hoc Networking
25
Two-Bit Architecture

Proposes three different levels of service:




Premium Service.
Assured Service.
Best Effort Service.
Two-bit architecture:



Packets get differentiated by two bits in their
header.
Premium bit (P-bit)
Assured Service bit (A-bit)
Univ. of Tehran
Wireless Ad hoc Networking
26
RFC 2475: Overall
Architecture
Meter
Classifier
Marker
Shaper/
Dropper
Classifiers:
1. Multifield Classifier (MF)
2. Behavior Aggregate Classifier (BA)
Univ. of Tehran
Wireless Ad hoc Networking
27
Traffic Conditioning



Schedulers: Work-conserving or Non-workconserving
Traffic conditioning uses Non-workconserving ones
Implementations



Leaky Bucket
Token Bucket
Hybrid approaches


Leaky-Token Bucket
Dual Token Bucket
Univ. of Tehran
Wireless Ad hoc Networking
28
Leaky Bucket

Smoothes traffic and generates constant
rate
b bits
r b/s
Univ. of Tehran
Wireless Ad hoc Networking
29
Token Bucket Filter

Described by 2 parameters:



Token rate r: rate of tokens placed in the bucket
Bucket depth b: capacity of the bucket
Operation:




Tokens are placed in bucket at rate r
If bucket fills, tokens are discarded
Sending a packet of size P uses P tokens
If bucket has P tokens, packet sent at max rate,
else must wait for tokens to accumulate
Univ. of Tehran
Wireless Ad hoc Networking
30
Token Bucket Operation
Tokens
Tokens
Tokens
Overflow
Packet
Enough tokens 
packet goes through,
tokens removed
Univ. of Tehran
Wireless Ad hoc Networking
Packet
Not enough tokens
 wait for tokens to
accumulate
31
Token Bucket



On the long run, rate is limited to r
On the short run, a burst of size b can be
sent
Token Bucket 3 possible uses

Shaping


Policing


Delay pkts from entering net (shaping)
Drop pkts that arrive without tokens
Metering (Marking)

Let all pkts pass through, mark ones without tokens
Univ. of Tehran
Wireless Ad hoc Networking
32
QoS Issues on wireless







Dynamically varying network topology
Imprecise state information
Lack of central coordination
Error-prone shared radio channel
Hidden terminal problem
Limited resource availability
Insecure medium
Univ. of Tehran
Wireless Ad hoc Networking
33
Different approaches



MAC layer
Network Layer
Cross Layer
Univ. of Tehran
Wireless Ad hoc Networking
34
Flexible QoS Model for MANETs
(FQMM)


FQMM is the first QoS Model proposed in 2000
for MANETs by Xiao et al.
The model can be characterized as a “hybrid”
IntServ/DiffServ Model since



the highest priority is assigned per-flow provisioning.
the rest is assigned per-class provisioning.
Three types of nodes
again defined



Ingress (transmit)
Core (forward)
Egress (receive)
Univ. of Tehran
core
core
ingress
2
ingress
4
2
3
1
3
1
Wireless Ad hoc Networking
4
egress
6
5
egress
7
6
5
7
35
QoS Signaling


Signaling is used to reserve and release resources.
Prerequisites of QoS Signaling




Reliable transfer of signals between routers
Correct Interpretation and activation of the appropriate
mechanisms to handle the signal.
Signaling can be divided into “In-band” and “Out-ofband”.
Most papers support that “In-band” Signaling is more
appropriate for MANETs.
Univ. of Tehran
Wireless Ad hoc Networking
36
Signaling

In-band Signaling, network control information is
encapsulated in data packets
+ Lightweight
 Not Flexible for defining
newHdrService
Version
Len
Prec Classes.
TOS
Identification
TTL
Flags
Protocol
Total Length
Fragment Offset
Header CheckSum
Source Address
Destination Address
Options
Padding
32 bits
(Shaded fields are absent from IPv6 header)

Out-of-band Signaling, network control information is
carried in separate packets using explicit control packets.
Heavyweight
 signaling packets must have higher priority to achieve on time
notification => can lead to complex systems.
+ Scalability. Signal packets don’t rely on data packets
+ We can have rich set of services, since we don’t need to “steal“ bits
from data packets

Univ. of Tehran
Wireless Ad hoc Networking
37
INSIGNIA – MANETs QoS
Signaling

INSIGNIA is the first signaling protocol
designed solely for MANETs by Ahn et al.
1998.
Can be characterized as an “In-band RSVP”
In-band {
protocol.

RSVP
{



It encapsulates control info in the IP Option
field (called now INSIGNIA Option field).
It keeps flow state for the real time (RT) flows.
It is “Soft State”. The argument is that
assurance that resources are released is more
important than overhead that anyway exists.
Univ. of Tehran
Wireless Ad hoc Networking
38
INSIGNIA – OPTION Field

Reservation Mode (REQ/RES): indicates whether
there is already a reservation for this packet.



If “no”, the packet is forwarded to INSIGNIA Module
which in coordination with a AC may either:
grant resources  Service Type = RT (real-time).
deny resources Service Type = BE (best-effort).
If “yes”, the packet will be forwarded with the allowed
resources.
Bandwidth Request (MAX/MIN): indicates the
requested amount of bandwidth.
Reservation
Mode
Service
Type
Payload
Indicator
Bandwith
Indicator
REQ/RES
RT/BE
RT/BE
MAX/MIN
1 bit
1 bit
1 bit
1 bit
Bandwith Request
MAX
MIN
16 bits
The INSIGNIA OPTION field
Univ. of Tehran
Wireless Ad hoc Networking
39
INSIGNIA – Bottleneck Node

During the flow
reservation process
a node may be a
bottleneck:
The service will
degrade from
RT/MAX -> RT/MIN.
reservation/service/bandwidth
bottleneck node
REQ/RT/MAX
REQ/RT/MIN
MD
REQ/RT/MAX
Ms
M2
M1
M3
REQ/RT/MIN
M4
M5

If M2 is heavy-loaded it may also degrade the
service level to BE/MIN where there is actually
no QoS.
Univ. of Tehran
Wireless Ad hoc Networking
40
INSIGNIA


INSIGNIA is just the signaling protocol of a
complete QoS Architecture.
INSIGNIA Drawbacks.



Only 2 classes of services (RT) and (BE).
Flow state information must be kept in mobile hosts.
To realize a complete QoS Architecture we also
need many other components as well as a
Routing Protocol (e.g. DSR, AODV, TORA).
Univ. of Tehran
Wireless Ad hoc Networking
41
QoS Routing and QoS for AODV



Routing is an essential component for QoS. It
can inform a source node of the bandwidth and
QoS availability of a destination node
We know that AODV is a successful an ondemand routing protocol based on the ideas of
both DSDV and DSR.
We also know that when a node in AODV
desires to send a message to some destination
node it initiates a Route Discovery Process
(RREQ).
Univ. of Tehran
Wireless Ad hoc Networking
42
QoS for AODV





QoS for AODV was proposed in 2000 by C. Perkins and E.
Royer.
The main idea of making AODV QoS enabled is to add
extensions to the route messages (RREQ, RREP).
A node that receives a RREQ + QoS Extension must be
able to meet the service requirement in order to
rebroadcast the RREQ (if not in cache).
In order to handle the QoS extensions some changes need
to be on the routing tables
AODV current fields.
Destination Sequence Number, Interface, Hop Count, Next Hop, List of
Precursors

AODV new fields. (4 new fields)
1) Maximum Delay, 2) Minimum Available Bandwidth, 3) List of
Sources Requesting Delay Guarantees and 4) List of Sources
Requesting Bandwidth Guarantees
Univ. of Tehran
Wireless Ad hoc Networking
43
QoS for AODV - Delay


Handling Delay with the Maximum Delay extension and
the List of Sources Requesting Delay Guarantees.
Example shows how the with the Maximum Delay
extension and the List of Sources Requesting Delay
Guarantees are utilized during route discovery process.
1
RREQ1
delay=100
ingress
A
RREQ2
2
delay=10
x
RREQ1
RREQ1
delay=70
delay=20
core B
core C
Traversal_time= 3 0
Traversal_time= 5 0
cache
delay(B->D)=80
cache
delay(C->D)=50
RREP1
RREP1
delay=80
delay=50
Univ. of Tehran
Wireless Ad hoc Networking
egress
D
=TraversalTime
+ delay
RREP1
delay=0
44
QoS for AODV - Bandwidth



Handling Bandwidth is similar to handling Delay requests.
Actually a RREQ can include both types.
Example shows how the with the Minimum Available
Bandwidth extension and the List of Sources Requesting
Bandwidth Guarantees are utilized during route discovery
process.
RREQ1
min_bandwidth=10Kbps
1
ingress
A
Univ. of Tehran
RREQ2
2
minband=80K
x
RREQ1
RREQ1
min_bandwidth=10Kbps
min_bandwidth=10Kbps
core B
core C
Available_Bandwidth
= 100K
Available_Bandwidth
= 50K
cache
band(B->D)=50
cache
band(C->D)=50
RREP1
RREP1
bandwidth=50
bandwidth=50
Wireless Ad hoc Networking
egress
D
min{INF,50}
RREP1
bandwidth=INF
45
QoS for AODV - Loosing QoS

Loosing Quality of Service Parameters
if after establishment a node detects that the QoS can’t be maintained any
more it originates a ICMP QOS_LOST message, to all depending nodes.
== > Reason why we keep a List of Sources Requesting Delay/Bandwidth
Guarantees.

Reasons for loosing QoS Parameters.


Increased Load of a node.
Why would a node take over more jobs that it can handle?
ingress
A
core B
core C
Traversal_time= 3 0
Traversal_time= 5 0
cache
delay(B->D)=80
cache
delay(B->D)=80
cache
delay(C->D)=50
QOS_LOST
Univ. of Tehran
egress
D
QOS_LOST
Wireless Ad hoc Networking
46
Protection and Guarantee for Voice
and Video Traffic in IEEE 802.11e
Wireless LANs
•Yang Xiao
•Haizhon Li
•Sunghyun Choi
Univ. of Tehran
Goal: Provide two level mechanism to
enhance IEEE 802.11e (QoS)
1. First Level
A. Tried-and-known Method (ETD)
B. Early protection method (ENB)
• That is to enhance admission control of 802.11e
• Protect the existing voice and video flow from
the new and other existing voice and video flows
2. The Second Level
•
•
That is to reduce influences on collisions by data
traffic, and more fully utilize the channel capacity
To protect the existing voice and video flow from
the best effort traffic
Univ. of Tehran
Motivation

Admission control is not good enough


Admission control is good only when the
traffic load is not heavy
Data traffics have influences on QoS flows
due to collisions

Even though much of the channel capacity
can be used many best-effort traffic degrade
the existing voice/video flow since many data
transmissions cause many collisions
Univ. of Tehran
IEEE 802.11 DCF
Each station check whether the medium is idle before attempting to
transmit
if (idle for DISF period)
transmit immediately
else (busy for the medium)
a. wait until the medium becomes idle
b. id the channel stays idle during DIFS period
start a backoff process by selecting a backoff counter (BC)
Backoff Process
For (each slot time)
if (medium is idle)
BC is decremented
else
frozen backoff process
if(BC == 0)
the frame is transmitted
Univ. of Tehran
802.11 Distributed co-ordination
function
Univ. of Tehran
IEEE 802.11e EDCF

Hybrid Coordination function to support QoS

Contention based channel access


Enhanced Distributed Coordination Function
Considered in this paper due to:



Simplicity
Can support many QoS applications
Centrally controlled channel access schemes

Not considered in the paper
Univ. of Tehran
EDCF: TXOP (transmission opportunity)


TXOP is a time period when a station has
the right to initiate the transmission
Defined by:




Starting time
Maximum duration
Station cannot transmit a frame beyond
TXOP
In case of larger frames, fragmentation
may be required
Univ. of Tehran
EDCS: Access categories and
priorities



Four access categories
Eight different priorities
Differentiated ACs are
achieved by differentiatin:




AIFS (Arbitration Inter
Frame Space)
CWmin
CWmax
If one AC has a smaller
AIGS or CWmin or CWmax,
the ACs traffic has a
better chance to access
the medium
Univ. of Tehran
EDCF: medium control in a nutshell



Each queue acts as a independent MAC
entity with a different AIFS, different initial
window and different max. window size.
Each queue has its own backoff counter
BO[i]
If more than one queue finishes the
backoff at the same time higher AC is
preferred by the virtual collision handler
Univ. of Tehran
EDCF timing diagram
Univ. of Tehran
First Level Protection and Guarantee

Goal:


Components



To protect existing QoS flows, whether a new flow can enter the
system or not
QAP
QSTA
Work as follows

QAP calculates budget[AC] and announces via beacon



The budget is allowable transmission time per AC in beacon interval
If budget == 0 then new flows wont be allowed to gain medium
QSTA calculates its local transmission limit per AC

The real transmission time per AC <= transmission limit per AC
Univ. of Tehran
DAC: Procedure at QAP

QAP transmits Qos Parameter Set Element
(QPSE) to QSTAs via beacons




CWmin[i], CWmax[i], AIFS[i] (i = 0 … 3)
TXOPBudget[i] & surplusFactor[i] (i = 1,2,3)
TXOPBudget[i]: additional amount of time
available for AC i during next interval
surplusFactor[i]: ratio of over-the-air bandwidth
reserved for AC i to the bandwidth of
transported frames required for successful
transmission.
Univ. of Tehran
DAC: Procedure at QAP



TXOPBudget[i] = Max(ATL[i] – TxTime[i] *
surplusFactor[i] , 0)
ATL[i]: max amount of time that may be used
for transmission of AC i, per beacon.
TxTime[i]: time occupied by transmissions from
each AC during the beacon period, including
SIFS and ACK times


Set to zero immediately following transmission of a
beacon
For each data transmission QAP adds the time equal
to frame transmission time and all overhead involved
(SIFS and ACK) to TxTime counter.
Univ. of Tehran
DAC: procedure at each QSTA

When a transmission budget for an AC is
depleted:



New QSTAs cannot gain transmission time
Existing QSTAs cannot increase transmission
time per beacon interval
Thus above mechanism protects existing
flows
Univ. of Tehran
DAC: local variables maitained by
each QSTA




TxUsed[i]: time occupied by transmission
irrespective of success or not
TxSuccess[i]: transmission time for successful
transmission
TxLimit[i]: station shall not transmit if doing so
=> TxUsed[i] > TxLimit[i]
TxRemainder[i] = TxLimit[i] – TxUsed[i]



Carry over to next beacon if station cant transmit
TxMemory[i]: resources utilized during a beacon
interval.
f: damping function
Univ. of Tehran
DAC: procedure at each QSTA at
each target beacon time

For new QSTAs which start transmission with this AC in
the next interval

If TXOPBudget[i] = 0


If TXOPBudget[i] > 0


If TXOPBudget[i] = 0


TxMemory[i] is unchanged
If TXOPBudget[i] > 0


TxMemory = [0, TXOPBudget[i] / SurplusFactor[i]]
For other QSTAs:


TxMemory[i] = TxRemainder = 0
TxMemory[i] = f*TxMemory[i] + (I - f)*(TxSuccess[i] *
SurplusFactor[i] + TXOPBudget[i])
TxSuccess[i] = 0
TxLimit = TxMemory[i] + TxRemainder[i]
Univ. of Tehran
Enhancements

Enhancement with required throughputs and/or
delays (tried-and-known)



By observing several beacon intervals, the information
whether the currently available capacity can accept a
new flow can be determined
DAC + ETD
Enhancements with a non-zero budget values
(early-protection)


When the budget is below some threshold, new flows
are not allowed to enter.
DAC + ENB
Univ. of Tehran
The Second Level Protection and
Guarantee




Data traffic will affect existing voice and
video flow
Goal is to reduce the number of collisions
or collision probability, caused by data
traffic
Dynamically control data traffic
parameters
Window increasing factor changes with
the backoff stage.
Univ. of Tehran
Fast backoff


σi:window increasing factor (any real no >
1) for backoff stage i (i = 1 … Lretry)
Fast Backoff


2 <= σ1 < … <σretry
Fast backoff achieves a larger window size
much quicker and becomes faster when
backoff stage is large
Univ. of Tehran
Dynamically adjusting parameters
when fail / consecutive success

When a frame reaches retry limit and is dropped



When station successfully transmits m
consecutive frames:



CWmin[0] = Θ * CWmin[0] (Θ > 1)
AIFS[0] = AIFS[0] / ψ (ψ > 1)
CWmin[0] = CWmin[0] / Θ (Θ > 1)
AIFS[0] = AIFS[0] / ψ (ψ > 1)
Fast Backoff plus dynamic adjustments

BF + DAFS
Univ. of Tehran
With or without DAC
Univ. of Tehran
Voice, video and data traffic
Univ. of Tehran