Transcript Slide 1

Data Dissemination for Spot Applications in
Ad-Hoc Networks
Alaeddine EL-FAWAL
Thesis director :
Jean-Yves Le Boudec
Private Defense, 3 April 2009, EPFL
Overview on the PhD Work
Supported by 2 projects:
 Haggle: European project in Situated and Autonomic Communications
 NCCR MICS: National Center of Competence in Research – Mobile
Information and Communication Systems
2 parts in my PhD work:
 Data dissemination for spot applications over WIFI technology (Haggle)
 Cross-layer optimization for UWB systems (MICS)
Dealing with different facets of uncoordinated ad-hoc wireless
networks and deals with challenges at all networking layers
OUTLINE
Introduction
SLEF: Our Data Dissemination Middleware
Performance Validation
Prototyping and Testbed
Conclusions
Achievements
3
Open-Ended Environment
Caused by:
Dramatic expansion of WIFI interfaces: laptops, PDAs, mobile phones, video
games and even with peripherals and vehicles.
Characteristics:
 Involves from few to thousands of nodes.
 Challenging circumstances:
 Highly dynamic
 Unpredictable
 Uncoordinated
 Short contact time
 Quickly changing from dense to sparse, non-congested to congested
4
Spot Applications
Description
 Destination: all nodes within the spot (multi-hop).
 The spot might be the entire network (campus).
 Example: ad applications, traffic info, support routing, resource discovery, 5
bootstrapping phases for application layer.
Spot Applications
Requirements:
 Efficient and reliable data dissemination service
 Trade-off: spread-application rate
 Spread: number of nodes within the application spot
(number of nodes that receive a packet).
 The spot size is variable according to the network conditions.
 Delivery ratio can not be used… instead, we talk about spread.
7
Open-Ended Envir. : Variation and Diversity of Scenarios
Transmission range
Relay
Source / Relay
 Density: average
 Few sources: little new injected traffic
8
Open-Ended Envir. : Variation and Diversity of Scenarios
Transmission range
Relay
Source / Relay
 Density: average
 almost all are sources: a lot of new injected traffic
9
Open-Ended Envir. : Variation and Diversity of Scenarios
Relay
Source / Relay
 Very high density (traffic jam)
 almost all are sources: a huge amount of
new injected traffic
 One hop: + 200 neighbors
10
Open-Ended Envir. : Variation and Diversity of Scenarios
 Density: very sparse.
Relay
 No communication without mobility
(opportunistic communication)
Source / Relay
An autonomic mechanism for data dissemination that adapts to
this diversity in scenarios is a must, otherwise
network failure
11
OUTLINE
Introduction
SLEF: Our Data Dissemination Middleware
Performance Validation
Prototyping and Testbed
Conclusions
Achievements
12
SLEF: Self Limiting Epidemic Forwarding
Data dissemination through limited epidemic forwarding :
 A source transmits packets in broadcast mode.
 Nodes forward each packet they receive Forwarding Factor times.
 Packets are forwarded within a limited hop count.
We propose the SLEF middleware.
 Delivers an efficient and reliable data dissemination service to the spot
applications
 Deals with the tradeoff: spread-application rate
 The network conditions define the TTL limit (spread control).
 Functional between the application and the transmission sockets (UDP
or raw sockets).
13
SLEF: Self Limiting Epidemic Forwarding
SLEF Features:
 Autonomic: Adapts itself to any change in the network.
 Density increases  forwarding factor decreases
 Traffic load increases  TTL limit decreases
 Complete design of a middleware
 Does not need / exchange any topology information. Uses only local
information to the node (very short contact time).
SLEF is designed to hold in all scenarios, in particular
in very dense and very sparse ones
14
Essential Functions for Multi-Hop Broadcast
SLEF implements 6 essential functions needed for a sustainable service
1. Congestion control: first mechanism proposed for broadcast in ad hoc
networks
2. Efficient use of MAC broadcast:
 802.11 broadcast does not implement any exclusion mechanism
(RTS/CTS) and it performs poorly (similar to Aloha). We replace it by a
new scheme that we call pseudo-broadcast.
 802.11 broadcast does not implement Ack. Pkts might be transmitted in
the vacuum. We implement a presence indicator that does not need any
message exchange.
3. Scheduler / fairness: A scheduler is needed to decide which packet to
serve. It is based on Source ID to ensure some level of fairness.
4. Spread control (adaptive TTL)
5. Forwarding factor control
6. Buffer management
15
Spread Control: Adaptive TTL
Trade-Off Spread vs. Application Rate
Spread: number of nodes that receive a packet.
N : Spread
How:
FF: Forwarding Factor
R0: Nominal Rate of MAC Layer
λ : Application Rate
 We use an Aging mechanism
 Adaptive TTL: Aging adapts locally the TTL to the different network
setting, based on the send/receive events.
 The idea is as follows:
TTL limit= 2
With fixed TTL
 Density => Spread
Rate
With SLEF
 Density =>TTL
traffic jam: TTL = 1
: In a
 Density => TTL : In a very
sparse network: TTL = 10 16
Aging




New created pkt: Age = 0
Pkt received for the first time: Age = 255 – TTL
Age manipulated locally.
when transmitting: TTL = 255 -Age
Age
hop count
Send/receive the same pkt
Age = Age + K0
adaptive Age
receive any pkt
Age = Age + K1
Real time Age
Constant increase
by time: 8h -> 255
Age > 255
Drop packet
 Hop count: plays the role of a fixed TTL (=255/K0) if the network is
not congested.
Adaptive Age: adapts the TTL to the network activity, which reflects
the density and the traffic load
17
Real time Age: A pkt lives at most 8 hours (work cycle).
Spread-Rate Balance
 SLEF maintains a spread-rate balance
 2 parameters to adjust: K0, K1
 Once Adjusted, they work well with all settings
Adjusting the spread-rate
balance according to the
application needs
Default values for K0
and K1 are computed in
the thesis
18
Forwarding Factor Control
Why: To Minimize redundancy (save resources)
How:
 Inhibit nodes from transmitting over sent/received pkts.
 We compute a virtual rate for each packet based on the send/receive events.
 Adaptive: the virtual rate Adapts locally the Forwarding Factor to the
different network settings
One send/receive event
Two send/receive events:
The green nodes are inhibited:
smaller forwarding factor
Transmission would be
redundant
19
Virtual Rate
Virtual Rate: The max rate a packet is transmitted with
For each send / receive event on a given pkt:
1- The virtual rate is computed as follows:
R0 : nominal MAC rate [pkts/s]
RcvCount : number of times the pkt is received
SendCount : number of times the pkt is sent
a and b : are coefficient less than 1: a=0.1, b=0.01
2- vRate decreases exponentially with send/receive events.
3- The pkt is allowed to be transmitted only after: current time +
(similar to a back-off system)
The smaller the vRate is, the longer the back-off time is:
The pkt might be dropped before being transmitted
Unlike other mechanisms, the virtual rate based forwarding factor control
20
allows transmitting the pkt multiple times if needed.
Buffer Management
 Cleans the buffer in order to keep space for new incoming packets.
 Based on Aging.
 Drops packets with the highest age
Highest age
Lived the highest number of send/receive events
21
OUTLINE
Introduction
SLEF: Our Data Dissemination Middleware
Performance Validation
Prototyping and Testbed
Conclusions
Achievements
22
Setting
Scenarios:
• Vehicular networks.
• Different network settings: node density, traffic load…
Network Simulator: JIST-SWANS, A JAVA simulator for Ad Hoc
networks
Vehicular Mobility Simulator: STRAW, an extension of JIST-SWANS. It
provides a mobility model based on the operation of the real vehicular
traffic.
Topo
: 2-lanes road, speed limit 80Km/h
MAC
: 802.11/b
Channel : Fading
K0 = 25
Range
K1 = 0.1
: 300 m in average
23
Adaptation of the Spread to the Rate
Density: 12 vehicles/Km
Adaptive TTL
Rate
Spread
24
Adaptation of the Forwarding Factor to the Density
Very sparse
(Death Valley)
Very dense (Traffic jam)
+200 neighbors
25
Importance of the Pseudo-Broadcast
Very dense (Traffic jam): +200 neighbors
Idea: implement a mutual exclusion mechanism for broadcast
in order to avoid collision
26
OUTLINE
Introduction
SLEF: Our Data Dissemination Middleware
Performance Validation
Prototyping and Testbed
Conclusions
Achievements
27
SLEF Prototyping
2 architectures:
Spot application
SLEF
Spot application
UDP
SLEF
IP
MAC
MAC
Raw sockets
UDP sockets
+ It is independent of the IP address
+ Practical in the absence of a
– IP networking needs to be initialized
– Complex with Windows
+Straightforward with all platforms
centralized coordination where assigning
IP @ is challenging
28
SLEF Prototyping
4 platforms:
 Windows XP: J2SE, C++
 Windows Mobile: J2ME, C++
 Linux: J2SE, C++
 OpenWrt (Linux-like firmware for embedded system): C++
Resource-constrained devices:
 Smartphone
HTC S620:
SLEF is practical
and performs well on very resource-limited devices
 Windows Mobile
 64MB RAM, 128 ROM
 201 MHz
 ASUS WL-500 GP wireless router
 OpenWrt
 32MB RAM, 8MB Flash
 266MHz
29
Testbed
Stress test:
 More than 50 devices communicating with each other for long time.
Performance evaluation of SLEF through measurements
Testbed features:
 Wireless router: ASUS WL-500GP
 Technical specifications: 8MB Flash, 32MB
RAM, 266MHz, 2 USB 2.0 ports
 Firmware: OpenWrt
 Configurable wireless interface: using Atheros
card with MadWIFI driver (setting RTS/CTS
Th, Tx power, promiscuous mode, monitor
mode, Tx queue length…).
 Mobility: using plumb batteries, +4 hrs lifetime
with full power transmission at full rate
 Robustness.
30
Measurement Design
Nodes are distributed over 12 buildings in EPFL
31
Measurement Design
 Application: injects packets at fixed rate.
 Application rate: can be reduced by the congestion control mechanism.
 Comparison: SLEF vs. fixed-TTL
 Fixed-TTL:
 Implements all functions of SLEF, otherwise it is not functional.
 Spread control is replaced by TTL (decremented by one for each hop)
 TTL limit is fixed
 Buffer management is based on the TTL and not on the age: packets with
the smallest TTL are dropped first when the buffer is full
 Fixed-TTL limits the spread through 2 parameters: TTL limit and the
buffer size.
 Buffer size of fixed-TTL:
 Small buffer size: We ran SLEF and we use the average buffer
occupation obtained (620 packets).
 Large buffer size: 10 000 packets.
32
Measurement Results
Higher redundancy
Lower rate
Smaller spread
With fixed TTL:
 Setting the buffer size per scenario is needed:
 Large buffer size  radundancy and low rate
 Small buffer size  small spread even in non-congested network
 TTL based buffer management does not perform well.
33
Measurement Conclusions
SLEF
 2 parameters to adjust: K0, K1
 Once adjusted, they work well with all
settings
 Aging based buffer management
performs well
 Max Buffer size is 255/K1 (little
formula)
Fixed-TTL
 2 parameters to adjust: MaxTTL
and buffer size
 Needs to adjust whenever the
network setting (density, traffic load,
mobility,…) changes
 TTL based buffer management
performs poorly.
34
OUTLINE
Introduction
SLEF: Our Data Dissemination Middleware
Performance Validation
Prototyping and Testbed
Conclusions
Achievements
35
Conclusions
We propose SLEF: data dissemination middleware for spot applications
Autonomic: Adapts itself to any change in the network.
 Complete middleware
 Does not need/exchange any topology information. Uses only local
information to the node.
 Works even in extreme scenarios (very dense/sparse…)
 Performs well on resource constrained devices
Prototyping SLEF for 4 platforms
Building a testbed for wireless networks protocols
SLEF performs better than fixed-TTL:
 Fixed-TTL is not adaptive
 TTL-based bufer management performs poorly
36
Perspectives
Performance evaluation of SLEF:
 Factorial analysis applied on measurement results.
 Measurements will consider varying scenarios: mobility, intermittent
connectivity, different traffic load and density.
 Comparison with different variants of data dissemination protocols
Collaboration with LCA3: Prof. Patrick Thiran and Adel
Aziz
 Extensive series of measurements for wireless network protocols
37
OUTLINE
Introduction
SLEF: Our Data Dissemination Middleware
Performance Validation
Prototyping and Testbed
Conclusions
Achievements
38
Achievements
Data Dissemination for Spot Applications (Haggle)
 Multi-Hop Broadcast Middleware (SLEF):
 One conference paper.
 Vulnerabilities in Epidemic Forwarding:
 One conference paper.
 SLEF Prototyping and Experimental Testbed.
Cross-Layer Optimization for UWB IR Networks (MICS)
 Robust Signal Acquisition in UWB Ad Hoc Networks:
 One journal paper, one conference paper and one patent (adopted by
MICS).
 Sleeping Mode for UWB IR Ad-hoc Networks:
 One journal paper.
39
Robust Signal Acquisition in UWB Ad Hoc Networks:
Problem:
Conventional detection method
 assume power control, otherwise it fails.
S1
 Power control impractical in the absence of
a centralized coordination (CDMA).
D2
Solution:
Near-far scenario
D1
S2
Power independent detection method.
Performance Evaluation:
10 users, LOS Indoor Office Channel model by IEEE P802.15.4a
Total Error: Et=PMD + PFA
PMD
Proba of Misdetection: PMD
40
Issues Addressed for the First Time
 Spot Applications (introduced for the first time).
 Trade-off: Spread – Application rate.
 Spread control.
 Congestion control in ad-hoc networks in broadcast mode.
 Fairness with epidemic forwarding.
 Identifying vulnerabilities that are specific to epidemic forwarding.
 First prototype of network coding for ad-hoc networks.
 Power independent signal acquisition for UWB in uncoordinated wireless adhoc networks (problem identification and solution).
 Identifying key design elements for power saving with UWB IR systems.
41
Used Expertise
 Queuing theory
 Performance evaluation tools
 Wireless networks
 Security
 All layers of TCP/IP stack, mainly:
 MAC (Medium Access Control)
 Physical Layer (UWB IR and 802.11)
 Vehicular networks
 Network coding
 Different channel models
 Signal processing.
 Simulation
 ns-2, Jist-Swans, Straw (vehicular traffic simulator), Matlab.
 System programming
 Windows XP, Windows Mobile, Linux, OpenWrt
 C++, J2SE, J2ME, raw sockets
42
Demo: Ad-Hoc Ventes Flash
 Spot application
 Needs SLEF
 Windows platform: XP and Mobile
 C++
Client
Sender (shop)
Injects ads:
Receive ads:
 Shop name
 Filtering at the application level:
 Product features:
 Name
 Category
 Shop name
 Category
 Vote
 Price
 …
43
Demo: Ad-Hoc Ventes Flash
Scenario:
Persistent broadcast in presence of intermittent connectivity
Shop
Client 1
Client 2
Application on
X
X
X
Application off
Application on
X
X
X
Application off
Application on
44
List of Publications at EPFL
Journal Articles:
El Fawal, Alaeddine ; Le Boudec, Jean-Yves: A Robust Signal Detection Method for Ultra Wide Band
(UWB) Networks with Uncontrolled Interference. In: IEEE Transactions on Microwave Theory and
Techniques (MTT,) 2006.
El Fawal, Alaeddine ; Le Boudec, Jean-Yves et al. Tradeoff Analysis of PHY-aware MAC in Low-Rate,
Low-Power UWB networks. In: IEEE Communications Magazine, vol. 43, num. 12, 2005, p. 147.
Raya, Maxim ; Aad, Imad ; Hubaux, Jean-Pierre ; El Fawal, Alaeddine DOMINO: Detecting MAC layer
greedy behavior in IEEE 802.11 hotspots. In: IEEE Transactions on Mobile Computing, December 2006
Proceedings:
El Fawal, Alaeddine ; Le Boudec, Jean-Yves ; Salamatian, Kave Multi-hop Broadcast from Theory to
Reality: Practical Design for Ad Hoc Networks. In: First International Conference on Autonomic
Computing and Communication Systems, October 2007.
El Fawal, Alaeddine ; Le Boudec, Jean-Yves ; Salamatian, Kave Vulnerabilities in Epidemic Forwarding In:
The First IEEE WoWMoM Workshop on Autonomic and Opportunistic Communications (AOC2007), 2007
Merz, Ruben ; El Fawal, Alaeddine ; Le Boudec, Jean-Yves ; Radunovic, Bozidar et al. The Optimal MAC
Layer for Low-Power UWB is Non-Coordinated. In: IEEE International Symposium on Circuits and
Systems (ISCAS 2006), 2006
El Fawal, Alaeddine ; Le Boudec, Jean-Yves A Power Independent Detection Method for UltraWide Band
(UWB) Impulse Radio Networks. In: IEEE International Conference on Ultra-Wideband (ICU 2005), 2005
Pending Patent:
El Fawal, Alaeddine ; Le Boudec, Jean-Yves
Synchronizing Method for Impulse Radio Networks, Date: 2005
Demo
45
El Fawal, Alaeddine ; Salamatian, Kave et al. A framework for network coding in challenged wireless
network. Presented at: MobiSys 2006, Uppsala - Sweden, June 19-22, 2006.
46
Testbed
Testbed features:
Wireless router: ASUS WL-500GP
Technical specifications: 8MB Flash, 32MB RAM, 266MHz, 2 USB 2.0
ports
Firmware: OpenWrt
Configurable wireless interface: using Atheros card with MadWIFI driver
(setting RTS/CTS Th, Tx power, Tx queue length…).
Mobility: using plumb batteries, +4 hrs lifetime with full power
transmission at full rate
Robustness.
49