Transcript PPTX - NDSL!

Practicalizing Delay-Tolerant
Mobile Apps with Cedos
YoungGyoun Moon, Donghwi Kim, Younghwan Go, Yeongjin Kim,
Yung Yi, Song Chong, and KyoungSoo Park
Dept. of Electrical Engineering, KAIST
Bandwidth-hungry Mobile Apps
Global Mobile Data Traffic Forecast
EB/month
10x increase
Source: Cisco VNI Mobile, 2015
2
Mobile Network Capacity Overload
 It is unclear if the physical capacity can meet the future demand
3
Cellular Data Offloading to Wi-Fi
 Wi-Fi as a secondary network interface in smartphones
Cellular Network (3G/LTE)
Wi-Fi
Wide coverage
Pros
Higher bandwidth
Expensive link cost
Cons
Limited coverage
4
Delayed Wi-Fi Offloading
 Delay-tolerance provides more Wi-Fi offloading opportunities
• Wiffler [MobiSys’10], DTap [CoNEXT’10]
Download
Completed
On-the-spot
offloading
Delayed
offloading
340MB
Time until Deadline
≤
LTE Transfer Time
How many mobile apps support
delayed offloading?
340MB
280MB
3G/4G
3G/4G
Download
Completed
3G/4G
PM 9:00
PM 3:00
Deadline
5
Challenges in Opportunistic Wi-Fi Usage
1. TCP connection failure at every disruption
Reconnecting…
110.89.47.114
143.90.7.20
 Behavior of mobile apps at network disruption
Load static webpage
Failed
Little system support for Stream
disruption
video handling
Failed
Stream video
Resume
Post comment
Failed
6
Challenges in Opportunistic Wi-Fi Usage
2. No complete support for delayed offloading
When there is no Wi-Fi connectivity,
Burden of handling network disruptions/delay
is placed solely on app developers.
7
Cedos: Cellular Data Offloading System
 Practical delay-tolerant mobile network access architecture
 The first comprehensive solution to development and
deployment of delay-tolerant mobile apps
Challenges
Our contributions
Handle disruptions and
long delays
Transport protocol which handles
disruptions and delays
Delayed Wi-Fi offloading
Delayed offloading schedulers
for static and dynamic files
Real-world mobile apps
8
Overall Architecture
Backward compatibility
D2Prox
Client application
D2TP
Handling disruption
D2TP
D2Sched
TCP server
D2BufMgr
TCP
TCP
Delayed offloading
D2TP
Disruption- and Delay-tolerant transport protocol
D2Sched
D2BufMgr
Delay-tolerant offloading scheduler
D2Prox
D2TP↔TCP translation proxy
9
D2TP
 D2TP allows disruption- and delay-tolerant transmission
• By handling the network disruptions/delays at mobility transparently
D2TP end host
D2TP end host
BSD socket-like API
D2TP
Handle disruptions/delays
BSD socket-like API
D2TP
10
D2TP
 TCP-like, reliable data transfer in stationary environments
 Hides the mobility events from the application layer
• Key enabler: “flow identifier (flow id)”
C
S
DATA (flow id = X, IP = A)
DATA (flow id = X, IP = B)
Authentication Process
Detect address
change
11
Validation
Continue data transfer
11
D2Sched and D2BufMgr
 D2Sched and D2BufMgr enable opportunistic Wi-Fi offloading
• Exploit users’ delay tolerance
D2TP client apps
D2TP
D2TP server
Opportunistic Wi-Fi offloading
D2Sched
D2BufMgr
(static contents)
(dynamic contents)
D2TP
12
D2Sched
 Cedos network API explicitly exposes how to handle delays
• “I want to complete a 1 GB file download at least within 6 hours.”
 D2Sched
• Delay-tolerant offloading scheduler for static files
• Goal: To meet QoE requirement with maximum Wi-Fi usage
13
D2BufMgr
Can we find any delay tolerance in real-time streaming apps?
14
D2BufMgr
 Usage scenario
LTE
Wi-Fi
LTE
1st st.
Wi-Fi
2nd st.
LTE
Wi-Fi
3rd st.
Wi-Fi data transfer is possible for small portion of time only
 D2BufMgr aims to
(1) Match minimal QoE to avoid buffer underrun
•
“I want to watch a 320 Kbps video without any buffer underrun.”
(2) Maximize Wi-Fi usage
15
D2BufMgr
 Delay transfer in 3G/LTE until buffer is going to be drained out
Amt. data
in buffer
Sufficient buffered data
 Stop using LTE
Th_high
Sufficient buffered data
 Stop using LTE
Buffer draining out
 Switch back to LTE
Guarantee QoE
Th_low
LTE
LTE
Time
16
D2Prox
 D2Prox works as a protocol translation proxy
• For incremental real-world deployment
Client apps
TCP server
D2Prox
D2TP
D2Sched
D2BufMgr
(static contents)
(dynamic contents)
D2TP
TCP
TCP
17
Cedos
 Motivation
 Design
• D2TP
• D2Sched and D2BufMgr
• D2Prox
 Implementation
• Cedos socket API
• Portability
 Evaluation
• Real-world Applications
18
Cedos Socket API
/* BSD
int
int
int
int
int
int
int
int
socket-like APIs */
d2tp_socket();
d2tp_bind(fd, &addr, addr_len)
d2tp_connect(fd, &addr, addr_len);
d2tp_accept(fd, &addr, &addr_len);
d2tp_close(fd);
d2tp_read(fd, buf, count);
d2tp_write(fd, buf, count);
d2tp_select(nfds, readfds, writefds, exceptfds, timeout);
/* Cedos-specific APIs
d2tp_setsockopt(fd,
d2tp_setsockopt(fd,
d2tp_setsockopt(fd,
(for delayed offloading) */
D2TP_SO_RCVBUFTH, &th, sizeof(th));
D2TP_SO_DEADLINE, &th, sizeof(th));
D2TP_SO_ESIZE, &th, sizeof(th));
19
D2Prox and Real-world Applications
 D2Prox implementation based on nginx (v1.2.6)
• By porting its web proxy module to use D2TP socket functions
 Real-world applications
Implementation
Total (LoC)
Modified (LoC)
D2Prox
129,340
55
Cedos-Firefox
8,851,611
123
Cedos-VLC
3,733,651
61
ReadyCast
9,868
-
Migration effort ↓
a delay-tolerant podcast downloader built on Cedos
20
Evaluation with Real-world Apps
 Opportunistic data offloading (Cedos-VLC with D2BufMgr)
• Video streaming in a subway train
 Delayed data offloading (ReadyCast with D2Sched)
• User study with delay-tolerant podcast app
21
Opportunistic Data Offloading with VLC
 Test environment
• Client: Nexus 5
– Watch a 640 Kbps streaming video
– Take a round trip for 22 stations in Daejeon subway Line 1
LTE
Wi-Fi
1st st.
LTE
Wi-Fi
2nd st.
LTE
Wi-Fi
3rd st.
Wi-Fi data transfer is possible only at stations
22
Opportunistic Data Offloading with VLC
 D2BufMgr’s low and high threshold = 200 KB and 3 MB
• Enough to cover 0.3 second of interface switching time
 Results
• Not a single video pause during the playback
Wi-Fi temporal coverage
Wi-Fi offloading ratio
11%
48%
23
Delayed Data Offloading with ReadyCast
24
Delayed Data Offloading with ReadyCast
25
Delayed Data Offloading with ReadyCast
 User study with 50 podcast users for 8 weeks
KAIST campus
D2Prox
Monitoring
server
Wi-Fi AP
Client
Internet
Server
Server
Server
26
Delayed Data Offloading with ReadyCast
Wi-Fi Offloading Ratio(%)
 Offloading ratios by user-configured delays
100
93.4%
96.2%
99.5%
92.4%
90
80
79.5%
70
60
On-the-spot
Delayed
(short)
Delayed
(long)
Delayed
(long)
Total
Allowed
delay
0
0 – 1 hr
1 – 3 hr
3 – 6 hr
-
# Downloads
974
362
330
1,168
2,834
Users allowed delay for
65% of their downloads
27
Delayed Data Offloading with ReadyCast
 Delay selection by users
Fraction of Data Transmitted (%)
100%
People allow more delays as they
16%
become accustomed
to delayed transmission
28%
80%
60%
39%
8%
13%
21%
40%
71%
53%
51%
Week 1
Week 2
20%
On-the-spot
Delayed (Short)
Delayed (Long)
0%
Week 3 - 8
28
Related Works
TCP migrate
DTN Protocols
(e.g., Bundle)
Handling disruption
V
V
Handling long delay
‒
V
API
BSD
custom
Delayed offloading
N/A
N/A
Wiffler
(done by apps)
(done by apps)
custom
(static files only)
Cedos provides a comprehensive solution
for delayed offloading applications
29
Conclusion
 Delay-tolerant Wi-Fi offloading is known to be a great idea,
but is not widely adopted in real-world mobile apps
 Cedos bridges the gap between theory and practice in Wi-Fi
offloading by providing a platform for delay-tolerant apps
 We hope Cedos can further reduce the cost in providing
data-intensive mobile services to users.
30
Thank you!
http://cedos.kaist.edu
Backup Slides
D2BufMgr
 D2BufMgr algorithm
• If buffered data is smaller than the low threshold Thlow,
start filling up the buffer using LTE up to the high threshold Thhigh
• If buffered data becomes larger than the high threshold,
switch to Wi-Fi interface and try downloading
• Calculating low and high threshold
– Thlow = (bitrate) * (time to switch Wi-Fi-to-LTE & start download)
– Thhigh = Thlow + (bitrate) * (time to switch LTE-to-Wi-Fi & start download)
 Guarantees no buffer underrun with minimal LTE usage
33
Wi-Fi is Nuisance
 Smartphone user survey result
• Half (48%) of smartphone users usually keep Wi-Fi interface off
Increased battery consumption,
enough cellular data cap, etc..
Frequent connection closure
due to network disruption
72%
Reasons for turning off Wi-Fi interface
34
Delayed Data Offloading with ReadyCast
 Delay selection by monthly data cap
0
5GB
1GB
Delayed download:
Delayed download:
Delayed download:
63%
52%
48%
35
Cedos: Cellular Data Offloading System
 Practical delay-tolerant mobile network access architecture
 Contributions
• The first comprehensive solution to the development and
deployment of delay-tolerant mobile apps
– Hide network disruptions and maximize Wi-Fi usage opportunities
• Easy to port existing mobile apps to support cellular data offloading
– Both for streaming and delay-tolerant apps
• Backward compatible to existing TCP-based servers
– For incremental real-world deployment
36
Initialization of D2TP Connection
 TCP-like 3-way handshake + shared key exchange
C
S
SYN (flow id = X) + Public-Key
Create/encrypt secret key
SYN+ACK + ENC(key)
Extract secret key via decryption
ACK
Both hosts now share the same secret key and flow id
37
D2TP Flow Handling at Mobility Events
 Authentication process to prevent connection hijacking
C
S
DATA (flow id = X, IP = A)
DATA (flow id = X, IP = B)
CHG (nonce)
Detect address change
RSP (HMAC-SHA1_key{nonce})
Validation
AUTH
Continue data transfer
38
D2Sched
 D2TP flow scheduler for deadline-based flow management
• Delay data transfer in cellular network until deadline approaches
 D2Sched aims to
(1) Complete all flows within user-specified deadline
(2) Maximize Wi-Fi usage
 D2Sched should support multiple concurrent D2TP flows
• Sequential scheduling in an earliest deadline first (EDF) manner
– An urgent flow has less data transfer opportunities than others
39
D2Sched
 Scheduling algorithm
• Flows are indexed in an increasing order of time until deadline
– e.g., flow 1 (earliest deadline), …, flow N (latest deadline)
• At each scheduling epoch,
0. If the data transfer was allowed, update the estimated throughput
For k = 1 to N,
1. Pick a flow whose time until deadline (D) is the k-th earliest one
2. Calculate the potential completion time (PCT) of the flow
• 𝑃𝐶𝑇 =
𝑟𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 𝑓𝑖𝑙𝑒 𝑠𝑖𝑧𝑒
) 𝑓𝑜𝑟
𝑒𝑥𝑝𝑒𝑐𝑡𝑒𝑑 𝑐𝑒𝑙𝑙𝑢𝑙𝑎𝑟 𝑡ℎ𝑟𝑜𝑢𝑔ℎ𝑝𝑢𝑡
(
𝑓𝑙𝑜𝑤 1, 2, … , 𝑘
3-1. If PCT <= D, start transferring flow 1 only if connected to Wi-Fi
3-2. If PCT > D, start transferring flow 1 using faster interface
• Either cellular or Wi-Fi network
40
Cedos Components
 D2TP socket API
 D2Prox
 Real-world Cedos applications
 D-Lock
41
D2TP Socket API
 BSD socket-like API for developers’ minimal migration effort
 Example
• Streaming app (opportunistic Wi-Fi offloading)
fd = socket();
fd = d2tp_
th.low = 20*1024;
// low threshold = 2KB
th.high = 1000*1024;
// high threshold = 1MB
d2tp_setsockopt(fd, D2TP_SO_RCVBUFTH, &th, sizeof(th));
d2tp_connect(fd, &serv_addr, sizeof(serv_addr);
d2tp_write(fd, request_buf, BUFSIZE);
d2tp_read(fd, response_buf, BUFSIZE);
d2tp_close(fd);
42
D2TP Socket API
 BSD socket-like API for developers’ minimal migration effort
 Example
• Non-interactive app (delayed data offloading)
fd = socket();
fd = d2tp_
d2tp_setsockopt(fd, D2TP_SO_DEADLINE, &t, sizeof(t));
d2tp_setsockopt(fd, D2TP_SO_ESIZE, &size, sizeof(size));
d2tp_connect(fd, &serv_addr, sizeof(serv_addr);
d2tp_write(fd, request_buf, BUFSIZE);
d2tp_read(fd, response_buf, BUFSIZE);
d2tp_close(fd);
43
D-Lock
 CPU sleep or Wi-Fi “no-attach” mode on idle state
• To minimize the battery consumption
• D2TP flows would stop even if Wi-Fi exists
 Android WakeLock and WifiLock
• Battery would be drained out quickly
 D-Lock is a power efficient CPU/Wi-Fi wakeup module
• Acquires CPU/Wi-Fi lock only when requested by D2TP
– Periodically wakes up CPU to probe nearby Wi-Fi APs
– D2Sched allows data transfer when a preferred network is available
44
Microbenchmark
 Test environment
• Client
– Galaxy S3 (1.4 GHz quadcore CPU, 2 GB RAM, and Android 4.1.2.)
– Nexus 5 (2.3 GHz quadcore CPU, 2 GB RAM, and Android 4.4.2.)
• Server machine (TCP/D2TP server or D2Prox)
– Intel Xeon E5-2650v2 octacore CPU, 32 GB RAM, and Ubuntu 12.04
• Wi-Fi AP
– ipTIME N8004R 802.11n (using 5GHz channel)
45
Throughput and Fairness
 TCP/D2TP client ↔ TCP/D2TP server
• Client: Nexus 5
• Comparable per-flow bandwidth fairness to that of TCP
Protocol (# conns)
Aggregate Throughput
JFI**
TCP (100)
95.1 Mbps
0.99
D2TP (100)
96.3 Mbps
0.99
TCP (50) + D2TP (50)
95.0 Mbps
0.98
 D2TP client ↔ D2Prox ↔ TCP server
• Client and D2Prox: E5-2650v2 machines
– 64K concurrent flows (each downloads a 1GB file)
– Change idle flow ratio from 0% to 100%, and back to 0%
• D2Prox keeps 10 Gbps line rate (with JFI >= 0.9) throughout the test
** JFI = Jain’s Fairness Index
46
Power Usage at Idle States
 D2TP client ↔ D2Prox ↔ TCP server
• Client: Galaxy S3
– No active connection (connections are waiting for Wi-Fi opportunity)
– Turn on Wi-Fi module for periodic scanning
Power (mW)
250
231.9
200
Battery consumption
reduced by 76%
150
100
50
67.5
43.0
55.1
45.2
D-Lock
(2min)
D-Lock
(10min)
0
Sleep
WakeLock
(2min)
D-Lock
(1min)
47
Video Streaming in a Subway Train
Current Streaming Apps
LTE
Wi-Fi
Wolpyeong (KAIST)
LTE
Wi-Fi
Government Complex Daejon
LTE
Wi-Fi
City Hall
Limitations of current streaming applications
• Unable to fully utilize Wi-Fi due to short periods of connectivity
• Wi-Fi signal strength can be unstable for continuous streaming
48
Video Streaming in a Subway Train
Cedos-based Streaming App (VLC using D2BufMgr)
LTE
Wi-Fi
Wolpyeong (KAIST)
LTE
Wi-Fi
Government Complex Daejon
LTE
Wi-Fi
City Hall
Consume
the prefetched chunks
Prefetch chunks
via Wi-Fi
Benefits of Cedos application
• Real-time buffer management exploiting opportunistic Wi-Fi connections
• Prevent buffer underrun by switching back to LTE if Wi-Fi is too slow
49
Related Works
 Mobility for IP networks
• Mobile IP [JACS’95], i3 [SIGCOMM’02], HIP [RFC4423]
– Separate host identity with location by relaying to ID
– Require additional infrastructure support
• Migrate TCP option [MobiCom’00]
– Reuse connection after IP address change
– Cannot handle large disruption delays
 Existing DTN protocols
• Bundle Protocol [RFC5050], LTP [RFC5325-5327]
– Designed as transport protocols in multi-hop opportunistic networks
– Unsuitable for sending dynamically generated data
– Programming API is largely different from BSD-socket API
 e.g., require endpoint IP starting with “dtn://”
50
Related Works
 Wi-Fi offloading with delay
• TUBE [SIGCOMM’12], DTap [CoNEXT’10]
– Show the potential of Wi-Fi offloading through mobility studies
– No practical system design
• Wiffler [MobiSys’10]
– Wi-Fi offloading system leveraging the delay tolerance
– Focus only on fixed-sized files, no multi-flow consideration
51
Cellular Network vs. Wi-Fi
• Cost savings by Wi-Fi deployment
• Simulation analysis result in New York City [1]
• By deploying 33,000 APs (density of 42 APs/km2),
44.7% of network facility cost can be saved.
LTE spots
Wi-Fi APs
Total CapEx
LTE Only
1,879
0
$514M
LTE + Wi-Fi
432
33,000
$284M
[1] White Paper: Building a Business Case for Carrier WiFi Offload – March 2012, Wireless 20/20
(http://www.wireless2020.com/docs/CarrierWiFiOffloadWhitePaper03202012.pdf)
52