Transcript Slide 1

A measurement study of vehicular
internet access using in situ Wi-Fi
networks
Vladimir Bychkovsky, Bret Hull, Allen Miu,
Hari Balakrishnan and Samuel Madden
http://cartel.csail.mit.edu
Personal information
• Name: Esteban Orduno
• Degree: Master of Science
• Major: Computer science
Abstract
• 802.11 based wireless networks are widely spread
in many metropolitan areas around the world.
• There is an opportunity for a grassroots wireless
internet service provided by users who open up their
802.11 access point to mobile clients.
• Can such an unplanned network service provide
reasonable performance to network clients moving in
cars at vehicular speeds?
Abstract
The paper study carried over 290 hours with a few cars in Boston and
Seattle.
With some caching optimization to speed-up IP address acquisition,
the following was found:
Median duration of link-layer connectivity at vehicular speeds is 13
seconds.
Median connection upload is 30 Kbytes/s
Mean duration between successful association is 75 seconds.
Connections are equally probable to speeds up to 60 km/hour.
Introduction
Home 802.11 wireless networks acts as a micro-ISPs.
Paper question is:
“What is the expected performance of open Wi-Fi networks for mobile
users, particularly for users in automobiles, as they move in urban
and suburban areas where AP are currently widely deployed?
1. What is the distribution of the duration of connectivity per
AP and the time between associations to different APs)?
How long does it take for a client to scan, associate, and obtain
an IP address?
2. What is the distribution of the coverage region of an AP?
3. What is the distribution of packet loss and data transfer rates?
4. What is the effect of a car’s speed on these metrics?
Related work
Previous studies:
• Used of careful planned test bed,
one in a lab,
a second on with two AP deployment.
The TCP connection has entry, production and exit phases.
Once a car enters the production phase within 200 meter, throughput rises.
Authors believe that with small changes to protocol, performance can be
improved.
• Another study uses off-the-shelf IEEE 802.11b wireless networks .
The study is done in the California desert where there is no interference.
Authors concluded packet loss are minimal within 150 m of the AP and
for a wide speed range, 5 to 75 mph.
A server was added to the AP and the bandwidth and delay of the link were changed.
With a 100 mS delay, the performance degraded.
Boston map with popular cells
Experimental method and data summary
• 9 cars were used that belong to people that work at
MIT.
• Cars were instrumented with an embedded
computer running CarTel system software.
• CarTel includes Scanping used to measure Wi-Fi
performance.
• Cars maintain normal driving patterns.
• 290 total hours of driving.
• 232 distinct days.
Measurement rig placed on each car
Figure 2
The experiments
The CarTel embedded computer has
a high-powered 802.11b miniPCI Wi-Fi card
a 5.5 dBi gain omni-directional rubber-duck antenna,
a Rayming TN200 GPS unit,
128 Mbytes of RAM,
1 GByte of flash memory for storage.
It runs Linux 2.4.31.
The Wi-Fi card was used solely to perform measurements and
not for any other communication.
Scanping probes the GPS device 1/sec to get the current latitude, longitude,
altitude, and speed
Scanping loop
ScanPing loops through the following 5 sequence operation:
• 1. Scan sends probe requests and wait for responses over all 11
802.11b channels.
When at least one AP is detected, proceeds to the next step.
• 2. Association issues a command to the Wi-Fi interface to associate
with an AP that responded to its probe.
Scanping logs the success or failure status along with the start time
and the duration of this operation.
Scanping then jumps back to Scan if the association fails.
Otherwise, it launches tcpdump to monitor and log all networking
activity involving Scanping, and proceeds to the next step.
Address configuration
• 3. Address configuration - dhcpcd is used to obtain an IP address.
An IP cache mechanism uses the AP’s BSSID value,
a 48-bit bit-string that uniquely identifies the AP,
to query a local cache for the AP’s IP configuration information obtained
from previous drive.
If it has not expired to the previous DHCP lease,
Scanping uses the cached parameters, and proceeds to the next stage.
Otherwise, it invokes dhcpcd to obtain a DHCP lease from the DHCP server
running on the AP’s network.
If dhcpcd fails to get an address,
the client times out after 5 seconds and returns to scan.
Single end-to-end ping
• 4. Single end-to-end ping - The AP may give association
rights and DHCP addresses to any client,
but refuse to forward traffic without proper authentication.
Examples are MAC address filters or firewalls.
Time can be wasted when connecting to these devices.
The connectivity pings the central server’s IP address.
This end-to-end ping is attempted every 200 ms or until the
first successful one, or until 2 seconds elapse.
In estimating end-to-end connectivity durations,
Scanping only considers APs for which this end-to-end test
succeeds.
Connectivity and uploads
5. Connectivity and uploads.
Scanping starts two separate processes in parallel:
(a). AP pings. To measure the properties of the wireless channel,
Scanping sends ping packets to the first-hop router every 100 ms.
Scanping logs the time at which each AP ping was done and
whether the ping succeeded or failed.
(b) TCP uploads - Scanping opens a TCP connection to the central server and delivers
data.
If the connection is lost,
Scanping terminates the connection so it can discover new APs.
Scanping uses pinging to determine the status of connection.
If no responses are heard for 3 seconds, the TCP connection is terminated.
Scanping logs the time at which each TCP upload was done,
the total number of bytes uploaded,
and the duration of the connection.
Data summary
Number of cars
9
Drive hours analyzed
290
Start date of analyzed data
July 29, 2005
End date of analyzed data
July 20, 2006
No. distinct days analyzed
232
No. of traces or drives
1605
Traces with non-empty scans
1176
No. of non-empty scans
154, 981
No. of APs discovered
32 111
No. of join attempts
75 334
Successful join attempts
19 576
Joins that acquired IP address
6 410
Joins responding to e2e ping
4 997
Distinct APs joined
5 112
Distinct APs that gave IP
2 259
Distinct APs that responded to AP ping
793
Distinct APs that responded to e2e ping
1023
End-to-end association
Figure 4 shows the same information
as the previous table,
but displayed as CDF of successful
pings grouped by smaller cells of
size 260 m × 270 m.
This size is the “typical” AP range.
The CDF shows that our data set
Samples about 700 total cells,
corresponding to an 49 square kilometers.
50% of the successful pings come from 42 cells (about 15 km of
distinct linear distance).
Experiment methodology
Scanping stores collected data in a Postgres database on each car;
Other process sends data to a back-end database when no experiments are being
done.
The back-end also uses Postgres and
includes a map-based visualization framework that produces graphs and locationbased pictures over Google maps.
The database stores information about all non-empty scans and
association attempts in corresponding tables.
Information about observed access points is normalized out of the scan records and
stored in a separate table.
Location information produced by the GPS is also stored into a separate table.
Wi-Fi and GPS data is cross-referenced through time stamps.
Lessons learned
•
It was found that the experimental setup stretches the limits of software and hardware.
They are not designed to operate in a challenging environment
where power disruption is frequent and
where operations of scanning and association
are controlled by a user-level process and occur at such high rates.
• Second, the CarTel embedded computer has a high process overhead;
it often takes multiple seconds to start new processes when the rest of the system is running.
On the positive side, CarTel database allowed easy analysis of the data.
All graphs were made through short , declarative SQL statements.
Data analysis proved time consuming to make data consisted and to remove a variety of outliers.
GPS acquiring satellite fix, if in the middle of a connection, causes the connection to be longer.
Outliers were generated by AP associations that partially complete or timeout.
The database had to be filtered out.
Connectivity results
Figure 5 shows the latency after a
successful association to:
(1) acquire an IP address,
(2) receive a response to the
end-to-end ping,
(3) receive the first successful
AP ping response
(4) receive the last successful AP
ping response.
Only data that completed
the corresponding phase of the association is used.
The figure shows that the median time between AP association and IP
address acquisition is about 3 seconds .
Connectivity results cont.
The time from association to first AP ping is:
median
8 seconds
minimum 5 seconds
The minimum is high due to having to start a separate process,
and it was taking a long time to start.
The platform has only 128 Mbytes,
and other processes are running at the same time.
Figure 5 also shows CDF of the time at which Scanping receives the last successful AP ping.
The median is about 24 seconds.
The setup is not able to probe or to transfer data during the first few seconds,
But the performance is characterized over the remainder of the association.
The distribution of overall association times has a heavy tail and
ranges from just a few seconds to several minutes.
Presumably representing times when cars were connected at stop lights or in heavy traffic.
Scan and association time latency
Figure 6
The scanning times:
minimum is 120 mS,
mean is 750 mS, and
maximum is 7030 mS.
The association times:
minimum time is 50 mS
mean is 560 mS,
maximum is 8970 mS.
Both distributions don’t have heavy tails,
95th percentile is not significantly higher
than the median.
Outliers in the scan times are probably anomalies,
association outliers are due to failures to associate.
Scan duration are consistent with benchmarks,
Association times are higher due to network conditions are less controlled and harsher
DHCP latency
The time to acquire an IP address is
often higher than the scanning and
association latencies.
The figure 7 shows the CDF of the time
to acquire an IP address after a
successful association when using DHCP,
without the caching optimization.
The relatively high median and tail DHCP
latencies may be due to the car being
in the edge of the area
when associating with an AP.
Some link-layer frames corresponding to the DHCP request or
its response may be lost.
The figure shows that when a car encounters an AP for the first time,
it takes time before it can send or receive data using that AP.
Accelerating initialization
To reduce scan and association latency,
cache mappings scheme between GPS coordinates and a set of APs
based on past drives is used to avoid re-scanning
when the car is near the same location again.
GPS coordinates are obtained once per second.
Caching the mapping between an AP’s MAC address (“BSSID”) and an
IP address granted by the corresponding DHCP server from the
previous drive should be a eliminate the DHCP delay.
The “IP cached” line of Figure 7 shows that successful cache hit greatly
reduces IP address acquisition latency for the median from 1.83
seconds to 346 milliseconds.
The cache hit rate was between 17% and 22%.
Connectivity duration
Figure 8 displays the duration of
connectivity,
which is calculated as the time duration
between the first and last successful AP
pings for each association.
The duration of connectivity times:
median is 13 seconds
mean is 24 seconds.
Figure 9 show that the number of
associations is uniform from 0 to 60
km/hour.
Few associations were made at speeds
above 70 km/hour.
Reasons:
AP are often distanced from highways.
Another reason is that measurements are
not optimized for sub-second association
that would improve highway connectivity.
Duration versus speed
Figure 10 shows that even though the
success of association is not affected
by speed,
associations made at lower speeds
tend to have longer durations .
This result is expected,
and implies that more data
would be transferred per AP
at lower speeds.
Period without connectivity
Figure 11 shows the inter-arrival time between
connectivity events for different
types of connectivity.
The mean time between successful
end-to-end pings is 260 seconds.
The median is lower than the mean,
and the CDF shows that end-to-end
connectivity events occur in clusters.
The standard deviation of this duration is 642 sec.
Intervals without connectivity are long ,
but when successful connectivity occurs,
it does so in quick succession.
Long durations with no connectivity correspond
to times when drivers are in areas of low human
population or traveling at high speeds
Join attempts and success
Join success in figure 11 combines nodes that successfully associated
and obtained a local IP address.
If all APs were to be used, the mean time between connections is just 23 secs.
Paper concludes that even when restricted to the number of APs that currently
were found,
permit associations or
those that provide local IP connectivity,
cars traveling in areas in and around cities will encounter many usable APS on any
drive that lasts more than a few minutes.
It implies that it is possible to get updates from vehicles in urban areas using an
unplanned open Wi-Fi.
If 20% of the available APs would allow associations today,
this would reduce the mean time between connectivity events by a factor of over 3×.
AP coverage
Figure 12 shows the number of APs
discovered per successful AP scan.
Two or more APs are discovered
over 65% of the time.
This is a lower bound because Scanping does
not scan when associating with AP or pinging.
Figure 13 shows a CDF of the fraction
of all associations that were made to each
of the 5112 APs that the experiment
associated with.
The APs are sorted in descending order of the
number of associations.
The top 100 APs account for about 20%
of all associations
AP coverage area
Figure 14 shows the complementary CDF of the
AP coverage area observed in the collected data.
The median AP has a coverage of 96 meters
and the top 10% of associations have a coverage
of more than 300 meters.
This is the lower bound on the true coverage
of the APs,
because the experiment does not try to find
the maximal coverage.
Two notes:
The mobile nodes transmit at power level of 200 mW.
The coverage would be also reduced at higher radio bit-rates.
The findings suggest that a small number of APs can cover a large area,
if willing to tolerate some holes with no coverage.
For example, the city of Boston is about 130 square km, so in theory,
the entire city could be covered with just 2,000 (properly placed) APs.
Wi-Fi packet loss rates
Figure 15 shows a complementary CDF of the
probability of successful AP ping over all connections,
for connections in which at least one end-to-end
ping succeeded.
The median connection has a delivery rate of 78%,
or an unidirectional delivery rate of about 90%.
The loss rate of our AP pings in different phases of
connections was studied.
10% at the time AP pings begin,
10% within the range of the AP,
80% when the car moves out of range of the AP.
An initial address acquisition delay or end-to-end ping is used,
otherwise, high rates would occur at the beginning of the connection.
Wi-Fi packet loss rates at different speeds
Figure 16 plots the mean AP ping
Success rate observed at different
speeds.
Limited data is available at higher
speeds, which is why some
speeds do not have points.
There appears to be no correlation between speed and
packet delivery rates.
Because the car-to-AP latency is only a few milliseconds,
the distance traveled by a car in this time is small.
TCP throughput
The TCP uploads are analyzed next.
Uploads were done only on a small
subset of all AP associations.
The time from initial association until
the first TCP ACK is used.
Figure 17 shows the time taken
for short single-packet reliable transfers.
The minimum time until any data is transmitted is 5 seconds,
which is an artifact of the resource constrained implementation platform.
This time includes other overheads,
Including first-hop router address resolution using ARP and DHCP (if used).
End-to-end throughput
Figure 18 shows the complementary CDF of the
per-connection end-to-end throughput.
Median connection throughput is 30 KBytes/s.
80% of all the connections have TCP performance
between 10 KBytes/s and 50 KBytes/s.
Most urban Wi-Fi networks have cable modems
or DSL links.
Cable modem or DSL links offer about the values obtained above.
The study uses 1 Mbit/s radio rate,
so any throughput higher than 100 Kbytes/s is not seen.
The middle of the connection, when most data is sent,
has a lower packet loss rate than the end.
Bytes transferred via TCP
Figure 19 shows the CDF the total number
of bytes transferred via TCP per connection.
The median connection transfers
216 KBytes of data,
which at 30 KBytes/sec,
it is connection duration of about 8 seconds.
This consistent with server logs
that show a connection
has packets arriving for about this time.
Some connections (about 10%) transfer only one packet,
and in some of those cases the TCP ACK was not received by the mobile unit.
The CDF of the number of bytes delivered has a heavy tail,
presumably corresponding to times when a car is at a stop light or is in heavy traffic.
Discussion
The measurements shown that there is a good amount of connectivity
in metropolitan areas even with small fraction of APs that are currently open.
Data suggests that the idea of individual users banding this connectivity together
to form a home-grown,
community-based,
everywhere-present network holds much promise.
There are number of technological, social and legal questions, though:
• How can we incentivize users to open their networks and opt into such a service
• How do we convince ISPs to allow this?
• What will connectivity in such networks look like as more APs join?
• How will the network capacity scale as more mobile clients (e.g., cars) participate?
• What transport protocol features will such a network require?
• How do we prevent roaming mobile users from monopolizing the resources of users
who donate their Internet connections?
Toward open Wi-Fi networks
In order for open Wi-Fi to become reality, both users and service provider should receive incentives.
Two potential incentives: promising participants free service, and giving participants money.
The proposed Fon network provides users who open their APs free access to all other users’ APs,
but charges users who have not opened their APs to use the system.
Fon then keeps some of the money and proposes to redistribute the rest to the ISPs involved.
Fon does not target highly mobile users moving in cars, which is the main focus of this paper.
A tiered security model for Wi-Fi APs would also be a good idea;
home users should be able to encrypt their traffic, while leaving APs usable by subscribers.
A simple approach would be to use three tiers,
one for the owners, one for subscribers and one for everyone else.
AP’s owner should be set data rate limits, so his/her data rate is not affected.
There are some optimization that can be made to reduce the impact of greedy mobile users.
Toward open Wi-Fi networks
ISPs will be willing to participate in such an arrangement provided
they are given sufficient financial incentives.
An ISP’s primary concern is users will use the open network
rather than paying for an Internet connection of their own.
A proper fee schedule or connection time limits on the open network can obviate
these concerns.
Legal issues favor open networks, at least in US.
Safe harbor laws protects participants for the actions of users of their access points.
As an alternative to community-driven open networks,
municipalities will install a large number of APs.
It may be free, but it is most likely that cities will charge some fee to subside the cost.
Municipal APs are likely to be only on dense cores of cities, rather then suburban
areas.
Then, it is more likely that the future metropolis will be a mix of commercial and
municipal Wi-Fi networks as well as community-driven open models.
Connectivity and network transport in open WiFi networks
The connectivity from the point of view of the mobile user possibly will be continuous.
Based on this paper analysis,
it is unlikely that at vehicular speeds it will be possible to maintain connectivity with at least one AP.
The transport layer solutions will consist of Mobile IP with some techniques for fast connection handoff.
If connectivity is discontinuous, there are a number of open issues:
The API that applications use to connect to each other will change,
since disconnectivity suggests that connection-oriented protocols are no longer appropriate.
A natural solution is to expose the non-continuous nature of the underlying connectivity
by means of application level framing ,
where applications express their transmissions in application defined data units ADUs.)
Fast, friendly connection establishment
Regardless of continuous or intermittent,
the future network stack for mobile environments must provide fair sharing of bandwidth:
We explore three possible optimizations in this area, related to:
(1) timing of TCP connection initiation,
(2) time-based fairness, and
(3) aggregating bandwidth across multiple access points.
Connection initiation timing:
There has been substantial work on using TCP over wireless.
Most of this work focused on wireless clients with little or no mobility.
As previous work suggests [15], wireless LAN connections at vehicular speeds go
through a set of phases as the client moves relative to the AP.
High losses at the beginning of a TCP connection could dramatically reduce
the overall throughput of the connection.
In this paper experiments,
TCP connections start only a few seconds after a successful association.
Optimizations to the transport protocol might be able to better address this issue.
Fairness
One way to improve fairness and avoid over-utilizing the connections of users who donate their APs is
to use rate limiting at APs or on clients,
or to use cooperative transport protocols like TCP Nice (tuned for wireless access).
Other fairness related issue is most Wi-Fi interfaces are designed
to adapt their bit-rates according to the link condition,
selecting lower bit-rates to overcome frame errors and signal-to-noise ratio in a bad link.
Our experiments show that a significant fraction of connections suffer from high loss rates.
Wi-Fi interfaces on the urban network clients are likely to operate in low bit-rates most of the time.
Lower bit-rates help reduce link losses, but they also reduce the capacity of Wi-Fi networks.
A home client’s throughput might reduce to 1/8th of its original value as a result of an urban client’s
connection.
Such anomalies can occur even when there are no packet losses in any of the links.
Using similar mechanism for Wi-Fi clients will limit the bit-rate differences on open Wi-FI throughput.
Aggregating bandwidth over Multiple Access
Points
Aggregation can provide a several-fold improvement in TCP throughput.
In 65% of the AP scans, we find at least two APs.
When an urban network client finds multiple APs after a scan,
it can use a multiple wireless interfaces to associate with different APs and use them.
The concurrent uplink transmissions would be serialized at the link-layer,
as the multiple interfaces contend to use the same or overlapping radio channel.
Serialized transmissions, connecting to multiple APs,
improve throughput as long as the connections sharing the overlapping channels do
not saturate the wireless link.
This paper showed that the median throughput of 30 Kbytes/sec remains
well below 802.11b’s saturation point for a TCP connection at the lowest bit-rate of
1 Mbit/s .
Conclusion
This paper wanted to know,
if given the proliferation of Wi-Fi networks in residential and around cities,
an unplanned,
community driven “open Wi Fi” network made up of in situ APs would be
feasible and perform well.
Clients moving at vehicular speeds in and around the cities is the main
interest.
This paper found that if only 3.2% of the currently found 32111 APs that were
able to obtain connectivity,
then clients can potentially remain connected for 24 seconds on average
and send tens of kilobytes of data per second each time.
The mean period of no connectivity in our data set was 260 seconds,
a number that will reduce dramatically with higher participation.
Conclusion
This paper also found that the number of connection at
different speeds was the same from 0 to 60 km/hour.
There are commercial, legal, and policy issues to be ironed out
for this open Wi-Fi network to become reality.
The technical conclusion is that such grassroots Wi-Fi
networks are viable for a variety of vehicular applications,
particularly ones that can tolerate some intermittent
connectivity
including:
mobile sensor networks with cars,
e-mail,
messaging applications,
Web access using pre-fetching and caching, etc