Transcript Redes Inalámbricas

Tema 5.- Redes inalámbricas Ad Hoc.
Quality of Service (QoS)
Introducción
QoS in IP based Networks
QoS in MANETs
Propuestas del Grupo GRC
 Arquitectura DACME
QoS
QoS in
in
MANETs
MANETs
Redes Inalámbricas
Máster Ingeniería de Computadores 2008/2009
2
MIC 2008/2009
Introduction

The evolution of the Multimedia Technology and the Commercial Interest of
Companies to reach civilian applications have made QoS in MANETs an unavoidable
task.

QoS and Overhead are synonyms !. The idea of providing QoS in MANETs is not to
extinct Overhead but to keep it as low as possible.

MANETs : 3 new problems!


Redes Inalámbricas


Dynamic Topology.
Bandwidth Constrains.
Limited Processing & Storing capabilities of Devices.
What happens with QoS in Wire-based Networks?. Can we port ideas / protocols to
MANETs?
A Glance At QoS in Mobile Ad-Hoc Networks: http:/www.cs.ucr.edu/~csyiazti/cs260.html
3
MIC 2008/2009
The QoS Metrics
How do we measure the QoS ?
 Some mostly used QoS attributes






Redes Inalámbricas

Available Bandwidth
Probability of packet loss
Delay variance (jitter, unpredictable delay)
end-to-end delay (Accumulation of jitter along the path)
Power consumption or battery charge
Service coverage area
QoS Metrics can be defined in terms of one of the parameters or a
set of parameters in varied proportions
4
MIC 2008/2009
QoS Definition

QoS definition

“The collective effect of service performance which determines the
degree of satisfaction of a user of a service”.
Redes Inalámbricas
The United Nations Consultative Committee for International Telephony and
Telegraph (CCITT) Recommendation E.800
Video frame without QoS Support
Video frame with QoS Support
5
MIC 2008/2009
Principles for QOS Guarantees (I)

Consider a phone application at 1Mbps and an FTP application
sharing a 1.5 Mbps link.


Redes Inalámbricas

Bursts of FTP can congest the router and cause audio packets to be dropped.
Want to give priority to audio over FTP.
PRINCIPLE 1: Marking of packets is needed for router to
distinguish between different classes; and new router policy
to treat packets accordingly.
6
MIC 2008/2009
Principles for QOS Guarantees (II)

PRINCIPLE 2: provide protection (isolation) for one class
from other classes.

Redes Inalámbricas

Applications misbehave (audio sends packets at a rate higher than 1Mbps
assumed above).
Require Policing Mechanisms to ensure sources adhere to bandwidth
requirements; Marking and Policing need to be done at the edges:
7
MIC 2008/2009
Redes Inalámbricas
Principles for QOS Guarantees (III)

PRINCIPLE 3: While providing isolation, it is desirable to use
resources as efficiently as possible.

Alternative to Marking and Policing: allocate a set portion of
bandwidth to each application flow; can lead to inefficient use of
bandwidth if one of the flows does not use its allocation.
8
MIC 2008/2009
Principles for QOS Guarantees (IV)

PRINCIPLE 4: Need a Call Admission Process; application
flow declares its needs, network may block call if it cannot
satisfy the needs .
Redes Inalámbricas

Remember: Cannot support traffic beyond link capacity
9
MIC 2008/2009
QoS in IP Based Networks

How is QoS achieved?

“Over Provisioning”. Add plentiful capacity to the network.
 Easy! (e.g. upgrade from 10Mb to 100Mb)
 Can be done gradually.
 But we remain at 1 service class (best effort) again.

“Network Traffic Engineering”. Make the Network more sophisticated!
(e.g. Traffic Classes, Connection Admission Control, Policy Managers,…)
 Reservation-based Engineering. (e.g. RSVP/IntServ, ATM)
 Reservation-less Engineering. (e.g. DiffServ)
– Used in today’s Differentiated Services
Redes Inalámbricas
» IPv4 TOS octect
» IPv6 traffic Class octect
10
MIC 2008/2009
Integrated Services


Attempt to modify Internet service model to support diverse
application requirements
Any data flow that desires better than best-effort delivery requests
and reserves resources at routers along the path



If insufficient resources are available, the flow is denied admission
into the network
Each router


Redes Inalámbricas


Maintains reservation state for each flow
Classifies every packet and decides forwarding behavior
Monitors the flow to ensure that it does not consume more than the reserved
resources
Advantages


RSVP is the recommended reservation protocol
Enables fine-grained QoS and resource guarantees
Disadvantages

Not scalable, harder to administer
11
MIC 2008/2009
Service Interface & Call Admission




Redes Inalámbricas

Session must first declare its QoS requirement and characterize the
traffic it will send through the network
R-spec: defines the QoS being requested by receiver (e.g., rate r)
T-spec: defines the traffic characteristics of sender (e.g., leaky
bucket with rate r and buffer size b).
A signaling protocol is needed to carry the R-spec and T-spec to the
routers where reservation is required; RSVP is a leading candidate for
such signaling protocol.
Call Admission: routers will admit calls based on their R-spec
and T-spec and base on the current resource allocated at the
routers to other calls.
12
MIC 2008/2009
Differentiated Services


Moves admission control and flow monitoring to the edge of the
network
Edge nodes classify and mark packets to receive a particular type of
service

Diff Serv Code Point (DSCP)
 Packet is marked in the Type of Service (TOS) in IPv4, and Traffic Class in IPv6.



Interior nodes determine the type of service for forwarded packets
based on their DSCP values
Advantages


Redes Inalámbricas


More scalable
No per-flow state
Easier to administer
BIG ADVANTAGE:


Finite set of DSCPs defined
No state info to be maintained by routers!
Disadvantages

Cannot provide the same per-flow guarantees as IntServ
13
MIC 2008/2009
Edge Router/Host Functions



Redes Inalámbricas

Classification: marks packets according to classification rules to
be specified.
Metering: checks whether the traffic falls within the negotiated
profile.
Marking: marks traffic that falls within profile.
Conditioning: delays and then forwards, discards, or remarks
other traffic.
14
MIC 2008/2009
QoS in MANETs





A lot of work has been done in supporting QoS in the Internet, but
unfortunately none of them can be directly used in MANETs because
of the bandwidth constraints and dynamic network topology of
MANETs.
To support QoS, the link state information such as delay, bandwidth,
cost, loss rate, and error rate in the network should be available and
manageable.
However, getting and managing the link state information in MANETs
is very difficult because the quality of a wireless link is apt to change
with the surrounding circumstances.
The resource limitations and the mobility of hosts make things more
complicated.
Hard QoS guarantee is not possible in MANETs
Redes Inalámbricas


Adaptive QoS
Service Differentiation
15
MIC 2008/2009
Why QoS is Hard in Mobile Ad Hoc Network?

Dynamic Network Topology



Imprecise state information






Redes Inalámbricas
Link state changes continuously
Flow states change over time
No central control for coordination
Error-Probe shared medium
Hidden terminal problem
Limited resources availability


Flow stop receiving QoS provisions due to path disconnections
New paths must be established, causing data loss and delays
Bandwidth, battery Life, Storage, processing capabilities
Insecure medium
16
MIC 2008/2009
Effects of congestion and mobility: PSNR
degradation due to mobility
 Bursty losses
 Several consecutive
frames lost (video
freezed)
degradation due to congestion
 Random losses
Redes Inalámbricas
 More uniform
distortion decay
Video at 10Hz  200 seconds interval
PSNR: The phrase peak signal-to-noise ratio, often abbreviated PSNR, is an engineering term for the ratio between the
maximum possible power of a signal and the power of corrupting noise that affects the fidelity of its representation.
The PSNR is most commonly used as a measure of quality of reconstruction in image compression
17
MIC 2008/2009
Effects of congestion and mobility: jitter
Congestion jitter:
 relatively small
 frequent variations
Mobility jitter:
 very large peaks
Redes Inalámbricas
 occasional
occurrences on route
change
jitter is an abrupt and unwanted variation of one or more signal characteristics
18
MIC 2008/2009
Main issues

The main issues to consider to achieve good quality are:
MAC level QoS: IEEE 802.11e required to differentiate from
bandwidth greedy best-effort traffic
 Admission control: to avoid more connections than the MANET
can handle
 Increase routing effectiveness: even by using layer-2 aware
routing protocols such as AODV or DSR, video transmission gaps
are still too large to be handled by a video codec


For video streaming
Redes Inalámbricas

Also  H.264 codec tuning:
19
MIC 2008/2009
QoS in MANETs

The first QoS Model proposed in 2000 for MANETs


QoS Signalling





QoS enabled routing (AODV/OLSR)
CEDAR(Core-Extraction Distributed Ad-hoc Routing)
Ticket based Probing (distributed QoS routing)
QoS MAC


Redes Inalámbricas
INSIGNIA (in-band signalling)
dRSVP(dynamic RSVP)
QoS Routing


FQMM (Flexible QoS Model for Manet QoS Signalling)
IEEE 802.11e
MACA/PR
 (Multiple Access Collision Avoidance
with Piggyback Reservation)


prioritised binary countdown (PBC)
... and

SWAN: integrated proposal
Mona Ghassemian, King’s College, September 2003
QoS in
MANETs
20
MIC 2008/2009
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 as




the highest priority is assigned per-flow provisioning.
the rest is assigned per-class provisioning.
Three types of nodes:
Ingress (transmit)
 Core (forward)
 Egress (receive)
Redes Inalámbricas

The role of each node
change according to the
node mobility

Only works with TCP traffic
Mona Ghassemian, King’s College, September 2003
core
2
4
ingress
3
1
egress
6
5
7
21
MIC 2008/2009
QoS Signalling Terminology

Signaling is used to reserve and release resources.

Prerequisites of QoS Signalling


Reliable transfer of signals between routers
Correct Interpretation and activation of the appropriate mechanisms to handle
the signal.
 It means that signaling must be understandable and implemented by the rest of the
nodes

Signaling can be divided into “In-band” and “Out-of-band”


In-band: integrated in data packets
Out-of-band: explicit use of control packets. Performance?
Redes Inalámbricas
 This packets should have higher priority
 RSVP is an example of out-of-band signaling
– Is the facto signaling protocol for IntServ

Most papers support that “In-band” Signaling is more appropriate for
MANETs.
22
MIC 2008/2009
In-band VS Out-of Band Signaling

In-band Signaling, network control information is encapsulated in data
packets
Lightweight
 Not Flexible for defining new Service Classes.

Version
Hdr Len
Prec
TOS
Identification
Flags
TTL
Protocol
Source Address
Destination Address
Options
Total Length
Fragment Offset
Header CheckSum
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
Redes Inalámbricas

23
MIC 2008/2009
INSIGNIA

INSIGNIA is the first signaling protocol designed solely for MANETs
by Ahn et al. 1998.


Can be characterized as an “In-band RSVP” protocol.



Redes Inalámbricas

Lee, S.B., Ahn, G.S., Campbell, A.T., "Improving UDP and TCP Performance in
Mobile Ad Hoc Networks with INSIGNIA", June 2001, IEEE Communication
Magazine.
It encapsulates control info in the IP Option field (called now INSIGNIA Option
field). (IN-BAND)
It keeps flow state for the real time (RT) flows. (RSVP)
It is “Soft State”. The argument is that assurance that resources are released
is more important than overhead that anyway exists. (RSVP)
INSIGNA tries to provide something better than best effort service for
some flows, e.g., video, voice.

QoS insensitive flows can be serviced in best effort manner: e-mail

QoS sensitive flows should be treated in better than best effort manner
Mona Ghassemian, King’s College, September 2003
24
MIC 2008/2009
INSIGNIA Review

INSIGNIA is just the signaling protocol of a complete QoS
Architecture.

To realize a complete QoS Architecture we also need many other
components
 A Routing Protocol (e.g. DSR, AODV, TORA) to track changes of routes
 An Admission Control Module to allocate requests according to the requested
resources
 A Packet Scheduling Module
 A Medium Access Controller Module

INSIGNIA Drawbacks.


Redes Inalámbricas

Only 2 classes of services (RT) and (BE).
Flow state information must be kept in mobile hosts.
Georgiadis, Jacquet, and Mans proved that bandwidth reservation on
ad-hoc networks is an np-hard problem [1]
[1] “Bandwidth Reservation in Multihop Wireless Networks: Complexity and Mechanisms”. ICDCSW'04,
Hachioji - Tokyo, Japan, March 2004.
25
MIC 2008/2009
Redes Inalámbricas
QoS in MANETs, an Integrated Vision

QoS Routing
QoS enabled routing (AODV/OLSR)
 CEDAR(Core-Extraction Distributed Ad-hoc Routing)
 Ticket based Probing (distributed QoS routing)
 Predictive Location-Based QoS Routing Protocol
 Bandwidth Routing Protocol
 Trigger-Based Distributed QoS Routing Protocol
 On-Demand QoS Routing Protocol
 QoS-Enabled Ad Hoc On-Demand Distance Vector Routing
Protocol
 On-Demand Link-state Multipath QoS Routing Protocol
 Asynchronous Slot Allocation Strategies
 …

26
MIC 2008/2009
Redes Inalámbricas
QoS Routing
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 on-demand 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).

Mona Ghassemian, King’s College, September 2003
27
MIC 2008/2009
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.



AODV new fields. (4 new fields)
1.
Redes Inalámbricas
Destination Sequence Number, Interface, Hop Count, Next Hop, List of Precursors
2.
3.
4.
Maximum Delay,
Minimum Available Bandwidth,
List of Sources Requesting Delay Guarantees and
List of Sources Requesting Bandwidth Guarantees
28
MIC 2008/2009
QoS-Extensions of AODV: Basic Idea

QoS information is added to the
RREQ packet

Intermediate nodes forward the
RREQ only if they have
sufficient resources to meet the
QoS requirement
Resource information is
updated in the RREQ by
intermediate nodes

Redes Inalámbricas

Destination sends resource
information back to source in
the RREP message
D
S
RREQ
RREP
29
MIC 2008/2009
QoS for AODV - Delay

Handling Delay with the Maximum Delay extension and the List of Sources
Requesting Delay Guarantees.
RREQ includes delay
 Each node has its NODE_TRANSVERSAL_TIME


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
Redes Inalámbricas
delay=100
ingress
A
2
RREQ2
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
egress
D
=TraversalTime
+ delay
RREP1
delay=0
30
MIC 2008/2009
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
Redes Inalámbricas
1
ingress
A
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
egress
D
min{INF,50}
RREP1
bandwidth=INF
31
MIC 2008/2009
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?
Redes Inalámbricas

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
QOS_LOST
egress
D
32
MIC 2008/2009
QoS in MANETs, an Integrated Vision

QoS MAC




Redes Inalámbricas

IEEE 802.11e
Cluster TDMA
MACA/PR. (Multiple Access Collision Avoidance with Piggyback Reservation)
Prioritised binary countdown (PBC)
…
33
MIC 2008/2009
... and
SWAN: integrated proposal

Stateless Wireless Ad-hoc Networks

intermediate nodes don’t keep per-flow or aggregate state
information
differentiate real-time and best-effort traffic
 QoS-capable MAC not needed
 AIMD algorithm (+ *  - like TCP window)
 Uses feedback information (ECN – explicit congestion
notification)

Redes Inalámbricas

Principles:
Rate control: per-hop MAC delay measurements
 Source-based admission control
 implemented in ns-2 and Linux/AODV

http://comet.ctr.columbia.edu/swan/
34
MIC 2008/2009
Propuestas del Grupo GRC: Arquitectura DACME

Previous proposals have strong requirements:




None of the previous proposals has taken into consideration that:




Redes Inalámbricas
All terminals must be equipped with the same software and similar hardware
All terminals must perform QoS related tasks
If some of the terminals do not offer QoS support, the whole QoS framework
fails or there is severe malfunctioning
The bandwidth reservation process is NP-hard
QoS at the MAC layer is fundamental
Multipath routing algorithms can offer important benefits
The MANET paradigm is based on user cooperation, but in most cases we can
not force users to cooperate
35
MIC 2008/2009
Propuestas del Grupo GRC: Arquitectura DACME
 Propuestas del Grupo GRC
 Arquitectura DACME
IP
Redes Inalámbricas
Multipath
routing
algorithm [1]
DACME
TCP/UDP
Distributed admission
control
MDSR
IEEE 802.11e
IEEE 802.11g
Prioritized channel
access
36
MIC 2008/2009
Redes Inalámbricas
DACME - Requirements

Only two:

All stations that have IEEE 802.11e interfaces should map the IP
packet's TOS to a MAC-level Access Category (basic requirement
to achieve good performance)

Sources and destinations of QoS traffic should implement DACME
(Distributed Admission Control for MANET Environments)
37
MIC 2008/2009
DACME - Admission control


DACME makes periodic end-to-end network measurements using
probes
Intermediate stations are not aware of DACME's tasks

Redes Inalámbricas

DACME uses UDP/IP
Decisions on whether to admit, maintain or drop a QoS flow are
based on DACME's periodic measurements and the QoS requirements
of each specific flow
38
MIC 2008/2009
DACME architecture

destination port, the destination's IP address and the QoS requirements



Redes Inalámbricas
1. The application registers with DACME, indicating the source and
2. DACME periodically sends probes to assess available bandwidth on
the path
3. The port state is set to up or down according to current network
conditions
4. The packet filter module is responsible for enforcing accept/reject
decisions, and also for changing the packet's TOS field if accepted
39
MIC 2008/2009
End-to-end bandwidth estimation
Is based on measurements made every 3 seconds (±0.5 s of jitter)
 each probe consists of 10 back-to-back packets with the same
TOS/AC as the application's packets to avoid the stolen bandwidth
problem (Breslau et al., SIGCOMM 2000)

Source
Destination
Δt→0
X
2
.....
...
Probe
1
Δtrec
Redes Inalámbricas
n
timeout
Probe reply
Adjustment of these values at
the source (over-estimation)
40
MIC 2008/2009
Performance evaluation

General simulation setup:







Redes Inalámbricas

ns-2 discrete event simulator
Radio interfaces are IEEE 802.11g/e enabled
Scenarios are sized 1900x400 m2 and composed by 50 nodes
Radio range is of 250 meters (4 hops between nodes on average)
Nodes move according to the random way-point model at a
constant speed of 5 m/s
Comparison between DSR & MDSR routing protocols
Simulation time is of 300 seconds for each experiment
DACME source/destination pairs have a DACME agent attached
41
MIC 2008/2009
Traffic

4 Video sources and 3 Voice sources regulated by DACME


Video sources generate CBR traffic at 1 Mbit/s in the Video AC
Voice sources:
 VoIP streams simulated using a Pareto On/Off distribution
 both burst and idle time set to 500 ms
 shaping factor used is 1.5, average data rate is of 100 kbit/s


4 background traffic sources



Redes Inalámbricas
Sources are turned off in the same order they were turned on
Traffic is negative-exponentially distributed
Variable traffic loads; load share per AC is: 50% to the Video AC, 25% to Besteffort AC, 25% to Background AC
These sources are active all the time
42
MIC 2008/2009
Redes Inalámbricas
Performance in terms of throughput/losses

On average the throughput of DACME-regulated sources is much
more stable (always close to the source data rate of 1 Mbit/s)

Voice sources do not generate constant data-rate traffic
In terms of packet losses we achieve very significant improvements

43
MIC 2008/2009
Redes Inalámbricas
Performance in terms of end-to-end delay

In terms of average end-to-end delay, DACME allows achieving much
lower values than its non-DACME counterpart
44
MIC 2008/2009
Routing overhead and traffic acceptance rate

In terms of routing overhead, DACME reduces it by avoiding routing
collapse situations

In terms of traffic acceptance rate:
Redes Inalámbricas

high data-rate sources (video) are more penalized
45
MIC 2008/2009
Conclusions and future work


We introduced a new paradigm of QoS architecture for MANETs
based on distributed admission control that is able to adapt to the
different constrains of MANET environments
Simulation results show that DACME:




In the future we plan to develop a version of DACME for the Linux
operating system to deploy an IEEE 802.11e-based real-life testbed

Redes Inalámbricas
Improves the support of multimedia applications by achieving more stable
throughput, fewer packet losses and reduced end-to-end delay
Does not misbehave when combined with a multipath routing protocol (MDSR)
Promotes routing stability and efficient usage of the radio channel
In linux system DACME can be implemented using Iptables